Optimize more easy multiplications by constants.

Rather than make these changes in the libraries (*10 being a common case),
let's do them once and for all in the JIT.

The 2^n-1 case could be better if we generated RSB instructions, but the
current "fake" RSB is still better than a full multiply.

Thumb doesn't support reg/reg/reg/shift instructions, so we can't optimize
the "population count <= 2" cases (such as *10) there.

Tested on sholes, passion, and passion-running-sapphire (and visually
inspected to check we weren't trying to generate Thumb2 instructions there).
Also tested with the self-verifier.

1 files changed, 70 insertions, 20 deletions

diff --git a/vm/compiler/codegen/arm/CodegenDriver.c b/vm/compiler/codegen/arm/CodegenDriver.c
index 4048c0a6d..f117de8f1 100644
--- a/vm/compiler/codegen/arm/CodegenDriver.c
+++ b/vm/compiler/codegen/arm/CodegenDriver.c
@@ -1844,20 +1844,75 @@ static bool handleFmt21t(CompilationUnit *cUnit, MIR *mir, BasicBlock *bb,
     return false;
 }
 
-/* Positive power of 2?  Return shiftCount if so, -1 if not */
-static int mulToShift(int val) {
-    int shiftCount;
-    if (val > 0 && ((val & (val - 1)) == 0)) {
-        shiftCount = 0;
-        val = ~val & (val - 1);
-        while (val) {
-            shiftCount++;
-            val >>= 1;
-        }
+static bool isPowerOfTwo(int x)
+{
+    return (x & (x - 1)) == 0;
+}
+
+// Returns true if no more than two bits are set in 'x'.
+static bool isPopCountLE2(unsigned int x)
+{
+    x &= x - 1;
+    return (x & (x - 1)) == 0;
+}
+
+// Returns the index of the lowest set bit in 'x'.
+static int lowestSetBit(unsigned int x) {
+    int bit_posn = 0;
+    while ((x & 0xf) == 0) {
+        bit_posn += 4;
+        x >>= 4;
+    }
+    while ((x & 1) == 0) {
+        bit_posn++;
+        x >>= 1;
+    }
+    return bit_posn;
+}
+
+// Returns true if it added instructions to 'cUnit' to multiply 'rlSrc' by 'lit'
+// and store the result in 'rlDest'.
+static bool handleEasyMultiply(CompilationUnit *cUnit,
+                               RegLocation rlSrc, RegLocation rlDest, int lit)
+{
+    // Can we simplify this multiplication?
+    bool powerOfTwo = false;
+    bool popCountLE2 = false;
+    bool powerOfTwoMinusOne = false;
+    if (lit < 2) {
+        // Avoid special cases.
+        return false;
+    } else if (isPowerOfTwo(lit)) {
+        powerOfTwo = true;
+    } else if (isPopCountLE2(lit)) {
+        popCountLE2 = true;
+    } else if (isPowerOfTwo(lit + 1)) {
+        powerOfTwoMinusOne = true;
+    } else {
+        return false;
+    }
+    rlSrc = loadValue(cUnit, rlSrc, kCoreReg);
+    RegLocation rlResult = dvmCompilerEvalLoc(cUnit, rlDest, kCoreReg, true);
+    if (powerOfTwo) {
+        // Shift.
+        opRegRegImm(cUnit, kOpLsl, rlResult.lowReg, rlSrc.lowReg,
+                    lowestSetBit(lit));
+    } else if (popCountLE2) {
+        // Shift and add and shift.
+        int firstBit = lowestSetBit(lit);
+        int secondBit = lowestSetBit(lit ^ (1 << firstBit));
+        genMultiplyByTwoBitMultiplier(cUnit, rlSrc, rlResult, lit,
+                                      firstBit, secondBit);
     } else {
-        shiftCount = -1;
+        // Reverse subtract: (src << (shift + 1)) - src.
+        assert(powerOfTwoMinusOne);
+        // TODO: rsb dst, src, src lsl#lowestSetBit(lit + 1)
+        int tReg = dvmCompilerAllocTemp(cUnit);
+        opRegRegImm(cUnit, kOpLsl, tReg, rlSrc.lowReg, lowestSetBit(lit + 1));
+        opRegRegReg(cUnit, kOpSub, rlResult.lowReg, tReg, rlSrc.lowReg);
     }
-    return shiftCount;
+    storeValue(cUnit, rlDest, rlResult);
+    return true;
 }
 
 static bool handleFmt22b_Fmt22s(CompilationUnit *cUnit, MIR *mir)
@@ -1896,15 +1951,10 @@ static bool handleFmt22b_Fmt22s(CompilationUnit *cUnit, MIR *mir)
             break;
         case OP_MUL_INT_LIT8:
         case OP_MUL_INT_LIT16: {
-            // TUNING: General shift & add for small constants
-            int shiftCount = mulToShift(lit);
-            if (shiftCount >= 0) {
-                op = kOpLsl;
-                lit = shiftCount;
-                shiftOp = true;
-            } else {
-                op = kOpMul;
+            if (handleEasyMultiply(cUnit, rlSrc, rlDest, lit)) {
+                return false;
             }
+            op = kOpMul;
             break;
         }
         case OP_AND_INT_LIT8: