Changed dx register allocator to place more phis and reuse locals.

This change makes the register allocator try to place all phis earlier,
by using whichever register is most common among its sources and result.

In addition, the code tries much harder to reuse registers originally
reserved for locals if they are no longer live. This leads to fewer
registers in many methods.

Change-Id: I5f69320686184f784384f5cf3a1d9c97e44ec19d

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