diff options
| -rw-r--r-- | dx/src/com/android/dx/ssa/back/FirstFitLocalCombiningAllocator.java | 120 | ||||
| -rw-r--r-- | dx/tests/091-ssa-const-collector/expected.txt | 8 |
2 files changed, 106 insertions, 22 deletions
diff --git a/dx/src/com/android/dx/ssa/back/FirstFitLocalCombiningAllocator.java b/dx/src/com/android/dx/ssa/back/FirstFitLocalCombiningAllocator.java index b9e0e8bf3..d99ad5822 100644 --- a/dx/src/com/android/dx/ssa/back/FirstFitLocalCombiningAllocator.java +++ b/dx/src/com/android/dx/ssa/back/FirstFitLocalCombiningAllocator.java @@ -538,7 +538,7 @@ public class FirstFitLocalCombiningAllocator extends RegisterAllocator { int category = ssaSpec.getCategory(); // Find a rop reg that does not interfere - int ropReg = findNextUnreservedRopReg(0, category); + int ropReg = paramRangeEnd; while (!canMapReg(ssaSpec, ropReg)) { ropReg = findNextUnreservedRopReg(ropReg + 1, category); } @@ -976,44 +976,128 @@ public class FirstFitLocalCombiningAllocator extends RegisterAllocator { /** * Attempts to map the sources and result of a phi to a common register. - * Will only try if a mapping already exists for one of the registers, - * and if this mapping is compatible with all the other registers. + * Will try existing mappings first, from most to least common. If none + * of the registers have mappings yet, a new mapping is created. */ private void processPhiInsn(PhiInsn insn) { RegisterSpec result = insn.getResult(); int resultReg = result.getReg(); int category = result.getCategory(); + + RegisterSpecList sources = insn.getSources(); + int sourcesSize = sources.size(); + + // List of phi sources / result that need mapping ArrayList<RegisterSpec> ssaRegs = new ArrayList<RegisterSpec>(); - ssaRegs.add(result); - // If the result of the phi has an existing mapping, get it - int mapReg = -1; + // Track how many times a particular mapping is found + Multiset mapSet = new Multiset(sourcesSize + 1); + + /* + * If the result of the phi has an existing mapping, get it. + * Otherwise, add it to the list of regs that need mapping. + */ if (ssaRegsMapped.get(resultReg)) { - mapReg = mapper.oldToNew(resultReg); + mapSet.add(mapper.oldToNew(resultReg)); + } else { + ssaRegs.add(result); } - RegisterSpecList sources = insn.getSources(); - for (int i = 0; i < sources.size(); i++) { + for (int i = 0; i < sourcesSize; i++) { RegisterSpec source = sources.get(i); int sourceReg = source.getReg(); - ssaRegs.add(source); - // If a source of the phi has an existing mapping, get it + /* + * If a source of the phi has an existing mapping, get it. + * Otherwise, add it to the list of regs that need mapping. + */ if (ssaRegsMapped.get(sourceReg)) { - int mapSourceReg = mapper.oldToNew(sourceReg); + mapSet.add(mapper.oldToNew(sourceReg)); + } else { + ssaRegs.add(source); + } + } + + // Try all existing mappings, with the most common ones first + for (int i = 0; i < mapSet.getSize(); i++) { + int maxReg = mapSet.getAndRemoveHighestCount(); + tryMapRegs(ssaRegs, maxReg, category, false); + } + + // Map any remaining unmapped regs with whatever fits + int mapReg = findNextUnreservedRopReg(0, category); + while (!tryMapRegs(ssaRegs, mapReg, category, false)) { + mapReg = findNextUnreservedRopReg(mapReg + 1, category); + } + } - // If the source mapping differs from an existing one, give up - if (mapReg != -1 && mapReg != mapSourceReg) { + // A set that tracks how often elements are added to it. + private static class Multiset { + private final int[] reg; + private final int[] count; + private int size; + + /** + * Constructs an instance. + * + * @param maxSize the maximum distinct elements the set may have + */ + public Multiset(int maxSize) { + reg = new int[maxSize]; + count = new int[maxSize]; + size = 0; + } + + /** + * Adds an element to the set. + * + * @param element element to add + */ + public void add(int element) { + for (int i = 0; i < size; i++) { + if (reg[i] == element) { + count[i]++; return; } + } + + reg[size] = element; + count[size] = 1; + size++; + } - mapReg = mapSourceReg; + /** + * Searches the set for the element that has been added the most. + * In the case of a tie, the element that was added first is returned. + * Then, it clears the count on that element. The size of the set + * remains unchanged. + * + * @return element with the highest count + */ + public int getAndRemoveHighestCount() { + int maxIndex = -1; + int maxReg = -1; + int maxCount = 0; + + for (int i = 0; i < size; i++) { + if (maxCount < count[i]) { + maxIndex = i; + maxReg = reg[i]; + maxCount = count[i]; + } } + + count[maxIndex] = 0; + return maxReg; } - // If a common mapping exists, try to map it to all regs in the phi - if (mapReg != -1) { - tryMapRegs(ssaRegs, mapReg, category, false); + /** + * Gets the number of distinct elements in the set. + * + * @return size of the set + */ + public int getSize() { + return size; } } } diff --git a/dx/tests/091-ssa-const-collector/expected.txt b/dx/tests/091-ssa-const-collector/expected.txt index 1d5a87cd8..b1c855adb 100644 --- a/dx/tests/091-ssa-const-collector/expected.txt +++ b/dx/tests/091-ssa-const-collector/expected.txt @@ -310,11 +310,11 @@ block 003b pred 0093 Blort.java:43@003b: Rop{invoke-virtual . <- Ljava/io/PrintStream; Ljava/lang/ String; call throws <any>}(java.io.PrintStream.println:(Ljava/lang/String;)V - catch) . <- v2:Ljava/io/PrintStream; v3:Ljava/lang/String;="foo" + catch) . <- v0:Ljava/io/PrintStream; v2:Ljava/lang/String;="foo" next 007f block 007e pred 0094 - Blort.java:33@0000: move-param-object(0) v4:"this"LBlort; <- . + Blort.java:33@0000: move-param-object(0) v3:"this"LBlort; <- . Blort.java:33@0000: goto . <- . next 0000 block 007f @@ -367,12 +367,12 @@ block 0090 block 0092 pred 0035 Blort.java:43@0036: Rop{move-result-pseudo Ljava/io/PrintStream; <- . flows} - v2:Ljava/io/PrintStream; <- . + v0:Ljava/io/PrintStream; <- . Blort.java:43@0036: goto . <- . next 0039 block 0093 pred 0039 - Blort.java:43@0039: Rop{move-result-pseudo Ljava/lang/String; <- . flows} v3: + Blort.java:43@0039: Rop{move-result-pseudo Ljava/lang/String; <- . flows} v2: Ljava/lang/String;="foo" <- . Blort.java:43@0039: goto . <- . next 003b |