Align 64-bits registers on even dalvik registers

The following alignments are done during register allocation
- Align 64-bit registers that are not parameters by modifying the method
giving the next free register to take into account alignment constraints.
- Align the first register of a range to maximize the number of 64-bit
registers that will be aligned into the range

The following alignments are done during instruction massaging
- Mov instructions inserted to transfer registers which are not compatible
with the selected instruction will use even registers for 64-bit registers
- Insert the right number of registers during instruction massaging in order
not to break alignment done by the register allocator
- Align parameters to maximize the number of 64-bit register aligned

Change-Id: Iafd85eb8455701595845803e503896247a1927bd

11 files changed, 375 insertions, 53 deletions

diff --git a/dx/src/com/android/jack/dx/dex/DexOptions.java b/dx/src/com/android/jack/dx/dex/DexOptions.java
index 2fda5c1..b089325 100644
--- a/dx/src/com/android/jack/dx/dex/DexOptions.java
+++ b/dx/src/com/android/jack/dx/dex/DexOptions.java
@@ -20,6 +20,12 @@ package com.android.jack.dx.dex;
  * Container for options used to control details of dex file generation.
  */
 public class DexOptions {
+
+  /**
+   * Enable alignment of 64-bit registers on Dalvik even registers.
+   */
+  public static final boolean ALIGN_64BIT_REGS = true;
+
   /** target API level */
   public int targetApiLevel = DexFormat.API_NO_EXTENDED_OPCODES;
 
diff --git a/dx/src/com/android/jack/dx/dex/code/HighRegisterPrefix.java b/dx/src/com/android/jack/dx/dex/code/HighRegisterPrefix.java
index 8f9b185..53daad3 100644
--- a/dx/src/com/android/jack/dx/dex/code/HighRegisterPrefix.java
+++ b/dx/src/com/android/jack/dx/dex/code/HighRegisterPrefix.java
@@ -16,6 +16,7 @@
 
 package com.android.jack.dx.dex.code;
 
+import com.android.jack.dx.dex.DexOptions;
 import com.android.jack.dx.rop.code.RegisterSpec;
 import com.android.jack.dx.rop.code.RegisterSpecList;
 import com.android.jack.dx.rop.code.SourcePosition;
@@ -87,10 +88,34 @@ public final class HighRegisterPrefix extends VariableSizeInsn {
 
     insns = new SimpleInsn[sz];
 
-    for (int i = 0, outAt = 0; i < sz; i++) {
-      RegisterSpec src = registers.get(i);
-      insns[i] = moveInsnFor(src, outAt);
-      outAt += src.getCategory();
+    if (DexOptions.ALIGN_64BIT_REGS) {
+      int outAt = 0;
+
+      // Insert mov instructions to transfer registers which are not compatible with an instruction
+      // into compatible registers. Compatible registers start at 0 until registers.getWordCount().
+      // 64-bit registers are low numbered in order to align them on even registers, and numbering
+      // of 32-bit registers start after the last number of 64-bit register.
+      for (int i = 0; i < sz; i++) {
+        RegisterSpec src = registers.get(i);
+        if (src.isCategory2()) {
+          insns[i] = moveInsnFor(src, outAt);
+          outAt += src.getCategory();
+        }
+      }
+
+      for (int i = 0; i < sz; i++) {
+        RegisterSpec src = registers.get(i);
+        if (src.isCategory1()) {
+          insns[i] = moveInsnFor(src, outAt);
+          outAt += src.getCategory();
+        }
+      }
+    } else {
+      for (int i = 0, outAt = 0; i < sz; i++) {
+        RegisterSpec src = registers.get(i);
+        insns[i] = moveInsnFor(src, outAt);
+        outAt += src.getCategory();
+      }
     }
   }
 
diff --git a/dx/src/com/android/jack/dx/dex/code/OutputCollector.java b/dx/src/com/android/jack/dx/dex/code/OutputCollector.java
index 6c12f4c..c5ae3d6 100644
--- a/dx/src/com/android/jack/dx/dex/code/OutputCollector.java
+++ b/dx/src/com/android/jack/dx/dex/code/OutputCollector.java
@@ -46,13 +46,13 @@ public final class OutputCollector {
    *
    * @param dexOptions {@code non-null;} options for dex output
    * @param initialCapacity {@code >= 0;} initial capacity of the output list
-   * @param suffixInitialCapacity {@code >= 0;} initial capacity of the output
-   * suffix
+   * @param suffixInitialCapacity {@code >= 0;} initial capacity of the output suffix
    * @param regCount {@code >= 0;} register count for the method
+   * @param paramSize size, in register units, of all the parameters for this method
    */
   public OutputCollector(DexOptions dexOptions, int initialCapacity, int suffixInitialCapacity,
-      int regCount) {
-    this.finisher = new OutputFinisher(dexOptions, initialCapacity, regCount);
+      int regCount, int paramSize) {
+    this.finisher = new OutputFinisher(dexOptions, initialCapacity, regCount, paramSize);
     this.suffix = new ArrayList<DalvInsn>(suffixInitialCapacity);
   }
 
diff --git a/dx/src/com/android/jack/dx/dex/code/OutputFinisher.java b/dx/src/com/android/jack/dx/dex/code/OutputFinisher.java
index ac3923d..b549982 100644
--- a/dx/src/com/android/jack/dx/dex/code/OutputFinisher.java
+++ b/dx/src/com/android/jack/dx/dex/code/OutputFinisher.java
@@ -29,6 +29,7 @@ import com.android.jack.dx.rop.cst.CstMemberRef;
 import com.android.jack.dx.rop.cst.CstString;
 import com.android.jack.dx.rop.cst.CstType;
 import com.android.jack.dx.rop.type.Type;
+import com.android.jack.dx.ssa.BasicRegisterMapper;
 import com.android.jack.dx.util.DexException;
 
 import java.util.ArrayList;
@@ -68,20 +69,31 @@ public final class OutputFinisher {
   private int reservedCount;
 
   /**
+   * {@code >= 0;} the count of reserved registers just before parameters in order to align them.
+   */
+  private int reservedParameterCount;
+
+  /**
+   * Size, in register units, of all the parameters to this method
+   */
+  private final int paramSize;
+
+  /**
    * Constructs an instance. It initially contains no instructions.
    *
    * @param dexOptions {@code non-null;} options for dex output
+   * @param initialCapacity {@code >= 0;} initial capacity of the instructions list
    * @param regCount {@code >= 0;} register count for the method
-   * @param initialCapacity {@code >= 0;} initial capacity of the
-   * instructions list
+   * @param paramSize size, in register units, of all the parameters for this method
    */
-  public OutputFinisher(DexOptions dexOptions, int initialCapacity, int regCount) {
+  public OutputFinisher(DexOptions dexOptions, int initialCapacity, int regCount, int paramSize) {
     this.dexOptions = dexOptions;
     this.unreservedRegCount = regCount;
     this.insns = new ArrayList<DalvInsn>(initialCapacity);
     this.reservedCount = -1;
     this.hasAnyPositionInfo = false;
     this.hasAnyLocalInfo = false;
+    this.paramSize = paramSize;
   }
 
   /**
@@ -359,10 +371,14 @@ public final class OutputFinisher {
 
     Dop[] opcodes = makeOpcodesArray();
     reserveRegisters(opcodes);
+    if (DexOptions.ALIGN_64BIT_REGS) {
+      align64bits(opcodes);
+    }
     massageInstructions(opcodes);
     assignAddressesAndFixBranches();
 
-    return DalvInsnList.makeImmutable(insns, reservedCount + unreservedRegCount);
+    return DalvInsnList.makeImmutable(insns, reservedCount + unreservedRegCount
+        + reservedParameterCount);
   }
 
   /**
@@ -392,8 +408,10 @@ public final class OutputFinisher {
    *
    * @param opcodes {@code non-null;} array of per-instruction
    * opcode selections
+   * @return true if reservedCount is expanded, false otherwise
    */
-  private void reserveRegisters(Dop[] opcodes) {
+  private boolean reserveRegisters(Dop[] opcodes) {
+    boolean reservedCountExpanded = false;
     int oldReservedCount = (reservedCount < 0) ? 0 : reservedCount;
 
     /*
@@ -406,6 +424,8 @@ public final class OutputFinisher {
         break;
       }
 
+      reservedCountExpanded = true;
+
       int reservedDifference = newReservedCount - oldReservedCount;
       int size = insns.size();
 
@@ -431,6 +451,8 @@ public final class OutputFinisher {
     }
 
     reservedCount = oldReservedCount;
+
+    return reservedCountExpanded;
   }
 
   /**
@@ -772,4 +794,104 @@ while (guess != null) {
 
     return anyFixed;
   }
+
+  private void shiftAllRegisters(int delta) {
+    int insnSize = insns.size();
+
+    for (int i = 0; i < insnSize; i++) {
+      DalvInsn insn = insns.get(i);
+      if (!(insn instanceof CodeAddress)) {
+        insns.set(i, insn.withRegisterOffset(delta));
+      }
+    }
+  }
+
+  private void shiftParameters(int delta) {
+    int insnSize = insns.size();
+    int lastParameter = unreservedRegCount + reservedCount + reservedParameterCount;
+    int firstParameter = lastParameter - paramSize;
+
+    BasicRegisterMapper mapper = new BasicRegisterMapper(lastParameter);
+    for (int i = 0; i < lastParameter; i++) {
+      if (i >= firstParameter) {
+        mapper.addMapping(i, i + delta, 1);
+      } else {
+        mapper.addMapping(i, i, 1);
+      }
+    }
+
+    for (int i = 0; i < insnSize; i++) {
+      DalvInsn insn = insns.get(i);
+      if (!(insn instanceof CodeAddress)) {
+        insns.set(i, insn.withRegisters(mapper.map(insn.getRegisters())));
+      }
+    }
+  }
+
+  private void align64bits(Dop[] opcodes) {
+    while (true) {
+      int notAligned64bitRegAccess = 0;
+      int aligned64bitRegAccess = 0;
+      int notAligned64bitParamAccess = 0;
+      int aligned64bitParamAccess = 0;
+      int lastParameter = unreservedRegCount + reservedCount + reservedParameterCount;
+      int firstParameter = lastParameter - paramSize;
+
+      // Collects the number of time that 64-bit registers are accessed aligned or not.
+      for (DalvInsn insn : insns) {
+        RegisterSpecList regs = insn.getRegisters();
+        for (int usedRegIdx = 0; usedRegIdx < regs.size(); usedRegIdx++) {
+          RegisterSpec reg = regs.get(usedRegIdx);
+          if (reg.isCategory2()) {
+            boolean isParameter = reg.getReg() >= firstParameter;
+            if (reg.isEvenRegister()) {
+              if (isParameter) {
+                aligned64bitParamAccess++;
+              } else {
+                aligned64bitRegAccess++;
+              }
+            } else {
+              if (isParameter) {
+                notAligned64bitParamAccess++;
+              } else {
+                notAligned64bitRegAccess++;
+              }
+            }
+          }
+        }
+      }
+
+      if (notAligned64bitParamAccess > aligned64bitParamAccess
+          && notAligned64bitRegAccess > aligned64bitRegAccess) {
+        addReservedRegisters(1);
+      } else if (notAligned64bitParamAccess > aligned64bitParamAccess) {
+        addReservedParameters(1);
+      } else if (notAligned64bitRegAccess > aligned64bitRegAccess) {
+        addReservedRegisters(1);
+
+        // Need to shift parameters if they exist and if number of unaligned is greater than
+        // aligned. We test the opposite because we previously shift all registers by one,
+        // so the number of aligned become the number of unaligned.
+        if (paramSize != 0 && aligned64bitParamAccess > notAligned64bitParamAccess) {
+          addReservedParameters(1);
+        }
+      } else {
+        break;
+      }
+
+      if (!reserveRegisters(opcodes)) {
+        break;
+      }
+    }
+  }
+
+  private void addReservedParameters(int delta) {
+    shiftParameters(delta);
+    reservedParameterCount += delta;
+  }
+
+  private void addReservedRegisters(int delta) {
+    shiftAllRegisters(delta);
+    reservedCount += delta;
+  }
 }
diff --git a/dx/src/com/android/jack/dx/dex/code/RopTranslator.java b/dx/src/com/android/jack/dx/dex/code/RopTranslator.java
index ef0b7f6..9399117 100644
--- a/dx/src/com/android/jack/dx/dex/code/RopTranslator.java
+++ b/dx/src/com/android/jack/dx/dex/code/RopTranslator.java
@@ -152,7 +152,7 @@ public final class RopTranslator {
      */
     this.regCount = blocks.getRegCount() + (paramsAreInOrder ? 0 : this.paramSize);
 
-    this.output = new OutputCollector(dexOptions, maxInsns, bsz * 3, regCount);
+    this.output = new OutputCollector(dexOptions, maxInsns, bsz * 3, regCount, paramSize);
 
     if (locals != null) {
       this.translationVisitor = new LocalVariableAwareTranslationVisitor(output, locals);
diff --git a/dx/src/com/android/jack/dx/dex/file/CodeItem.java b/dx/src/com/android/jack/dx/dex/file/CodeItem.java
index 2dbaed9..5cf8c40 100644
--- a/dx/src/com/android/jack/dx/dex/file/CodeItem.java
+++ b/dx/src/com/android/jack/dx/dex/file/CodeItem.java
@@ -207,8 +207,7 @@ public final class CodeItem extends OffsettedItem implements Code {
      * unit, post-code padding if necessary, and however much
      * space the catches need.
      */
-
-int insnsSize = code.getInsns().codeSize();
+    int insnsSize = code.getInsns().codeSize();
     if ((insnsSize & 1) != 0) {
       insnsSize++;
     }
diff --git a/dx/src/com/android/jack/dx/rop/code/RegisterSpec.java b/dx/src/com/android/jack/dx/rop/code/RegisterSpec.java
index e9f1474..61ef330 100644
--- a/dx/src/com/android/jack/dx/rop/code/RegisterSpec.java
+++ b/dx/src/com/android/jack/dx/rop/code/RegisterSpec.java
@@ -555,6 +555,12 @@ public final class RegisterSpec implements TypeBearer, ToHuman, Comparable<Regis
     return makeLocalOptional(reg, type, local);
   }
 
+  /**
+   * @return boolean specifying if this instance is an even register or not.
+   */
+  public boolean isEvenRegister() {
+    return ((getReg() & 1) == 0);
+  }
 
   /**
    * Helper for {@link #toString} and {@link #toHuman}.
diff --git a/dx/src/com/android/jack/dx/rop/code/RegisterSpecList.java b/dx/src/com/android/jack/dx/rop/code/RegisterSpecList.java
index 9f270ba..cd488aa 100644
--- a/dx/src/com/android/jack/dx/rop/code/RegisterSpecList.java
+++ b/dx/src/com/android/jack/dx/rop/code/RegisterSpecList.java
@@ -16,6 +16,7 @@
 
 package com.android.jack.dx.rop.code;
 
+import com.android.jack.dx.dex.DexOptions;
 import com.android.jack.dx.rop.type.Type;
 import com.android.jack.dx.rop.type.TypeList;
 import com.android.jack.dx.util.FixedSizeList;
@@ -358,15 +359,15 @@ public final class RegisterSpecList extends FixedSizeList implements TypeList {
 
   /**
    * Returns an instance that is identical to this one, except that
-   * all incompatible register numbers are renumbered sequentially from
+   * all incompatible register numbers are renumbered from
    * the given base, with the first number duplicated if indicated. If
-   * a null BitSet is given, it indicates all registers are compatible.
+   * a null BitSet is given, it indicates all registers are incompatible.
    *
    * @param base the base register number
    * @param duplicateFirst whether to duplicate the first number
    * @param compatRegs {@code null-ok;} either a {@code non-null} set of
    * compatible registers, or {@code null} to indicate all registers are
-   * compatible
+   * Incompatible
    * @return {@code non-null;} an appropriately-constructed instance
    */
   public RegisterSpecList withExpandedRegisters(int base, boolean duplicateFirst,
@@ -378,30 +379,77 @@ public final class RegisterSpecList extends FixedSizeList implements TypeList {
       return this;
     }
 
-    RegisterSpecList result = new RegisterSpecList(sz);
+    Expander expander = new Expander(this, compatRegs, base, duplicateFirst);
 
-    for (int i = 0; i < sz; i++) {
-      RegisterSpec one = (RegisterSpec) get0(i);
-      boolean replace = (compatRegs == null) ? true : !compatRegs.get(i);
+    if (DexOptions.ALIGN_64BIT_REGS) {
+      // Numbering done into HighRegisterPrefix starts by allocating 64-bit registers and
+      // thereafter adding 32-bit registers. Since the number of the first 32-bit register is
+      // unknown, 64-bit registers must be managed first.
+      for (int regIdx = 0; regIdx < sz; regIdx++) {
+        RegisterSpec reg = (RegisterSpec) get0(regIdx);
+        if (reg.isCategory2()) {
+          expander.expandRegister(regIdx, reg);
+        }
+      }
+
+      for (int regIdx = 0; regIdx < sz; regIdx++) {
+        RegisterSpec reg = (RegisterSpec) get0(regIdx);
+        if (reg.isCategory1()) {
+          expander.expandRegister(regIdx, reg);
+        }
+      }
+    } else {
+      for (int regIdx = 0; regIdx < sz; regIdx++) {
+        expander.expandRegister(regIdx);
+      }
+    }
+
+    return expander.getResult();
+  }
+
+  private static class Expander {
+    private BitSet compatRegs;
+    private RegisterSpecList regSpecList;
+    private int base;
+    private RegisterSpecList result;
+    private boolean duplicateFirst;
+
+    private Expander(RegisterSpecList regSpecList, BitSet compatRegs, int base,
+        boolean duplicateFirst) {
+      this.regSpecList = regSpecList;
+      this.compatRegs = compatRegs;
+      this.base = base;
+      this.result = new RegisterSpecList(regSpecList.size());
+      this.duplicateFirst = duplicateFirst;
+    }
+
+    private void expandRegister(int regIdx) {
+      expandRegister(regIdx, (RegisterSpec) regSpecList.get0(regIdx));
+    }
+
+    private void expandRegister(int regIdx, RegisterSpec registerToExpand) {
+      boolean replace = (compatRegs == null) ? true : !compatRegs.get(regIdx);
+      RegisterSpec expandedReg;
 
       if (replace) {
-        result.set0(i, one.withReg(base));
+        expandedReg = registerToExpand.withReg(base);
         if (!duplicateFirst) {
-          base += one.getCategory();
+          base += expandedReg.getCategory();
         }
+        duplicateFirst = false;
       } else {
-        result.set0(i, one);
+        expandedReg = registerToExpand;
       }
 
-      if (duplicateFirst) {
-        duplicateFirst = false;
-      }
+      result.set0(regIdx, expandedReg);
     }
 
-    if (isImmutable()) {
-      result.setImmutable();
-    }
+    private RegisterSpecList getResult() {
+      if (regSpecList.isImmutable()) {
+        result.setImmutable();
+      }
 
-    return result;
+      return result;
+    }
   }
 }
diff --git a/dx/src/com/android/jack/dx/ssa/back/FirstFitAllocator.java b/dx/src/com/android/jack/dx/ssa/back/FirstFitAllocator.java
index 3795077..5497096 100644
--- a/dx/src/com/android/jack/dx/ssa/back/FirstFitAllocator.java
+++ b/dx/src/com/android/jack/dx/ssa/back/FirstFitAllocator.java
@@ -71,7 +71,7 @@ public class FirstFitAllocator extends RegisterAllocator {
        * space.
        */
 
-nextNewRegister = ssaMeth.getParamWidth();
+      nextNewRegister = ssaMeth.getParamWidth();
     }
 
     for (int i = 0; i < oldRegCount; i++) {
diff --git a/dx/src/com/android/jack/dx/ssa/back/FirstFitLocalCombiningAllocator.java b/dx/src/com/android/jack/dx/ssa/back/FirstFitLocalCombiningAllocator.java
index 837bee3..ff17fe9 100644
--- a/dx/src/com/android/jack/dx/ssa/back/FirstFitLocalCombiningAllocator.java
+++ b/dx/src/com/android/jack/dx/ssa/back/FirstFitLocalCombiningAllocator.java
@@ -16,6 +16,7 @@
 
 package com.android.jack.dx.ssa.back;
 
+import com.android.jack.dx.dex.DexOptions;
 import com.android.jack.dx.rop.code.CstInsn;
 import com.android.jack.dx.rop.code.LocalItem;
 import com.android.jack.dx.rop.code.RegOps;
@@ -45,6 +46,49 @@ import java.util.TreeMap;
  * kept together if possible.
  */
 public class FirstFitLocalCombiningAllocator extends RegisterAllocator {
+
+  /**
+   * Alignment constraint that can be used during search of free registers.
+   */
+  private enum Alignment {
+    EVEN {
+      @Override
+      int nextClearBit(BitSet bitSet, int startIdx) {
+        int bitNumber = bitSet.nextClearBit(startIdx);
+        while (!isEven(bitNumber)) {
+          bitNumber = bitSet.nextClearBit(bitNumber + 1);
+        }
+        return bitNumber;
+      }
+    },
+    ODD {
+      @Override
+      int nextClearBit(BitSet bitSet, int startIdx) {
+        int bitNumber = bitSet.nextClearBit(startIdx);
+        while (isEven(bitNumber)) {
+          bitNumber = bitSet.nextClearBit(bitNumber + 1);
+        }
+        return bitNumber;
+      }
+    },
+    UNSPECIFIED {
+      @Override
+      int nextClearBit(BitSet bitSet, int startIdx) {
+        return bitSet.nextClearBit(startIdx);
+      }
+    };
+
+    /**
+     * Returns the index of the first bit that is set to {@code false} that occurs on or after the
+     * specified starting index and that respect {@link Alignment}.
+     *
+     * @param bitSet bitSet working on.
+     * @param startIdx {@code >= 0;} the index to start checking from (inclusive).
+     * @return the index of the next clear bit respecting alignment.
+     */
+    abstract int nextClearBit(BitSet bitSet, int startIdx);
+  }
+
   /** local debug flag */
   private static final boolean DEBUG = false;
 
@@ -355,16 +399,48 @@ public class FirstFitLocalCombiningAllocator extends RegisterAllocator {
   }
 
   /**
+   * Return the register alignment constraint to have 64-bits registers that will be align on even
+   * dalvik registers after that parameter registers are move up to the top of the frame to match
+   * the calling convention.
+   *
+   * @param regCategory category of the register that will be aligned.
+   * @return the register alignment constraint.
+   */
+  private Alignment getAlignment(int regCategory) {
+    Alignment alignment = Alignment.UNSPECIFIED;
+
+    if (DexOptions.ALIGN_64BIT_REGS && regCategory == 2) {
+      if (isEven(paramRangeEnd)) {
+        alignment = Alignment.EVEN;
+      } else {
+        alignment = Alignment.ODD;
+      }
+    }
+
+    return alignment;
+  }
+
+  /**
+   * Finds unreserved rop registers with a specific category.
+   *
+   * @param startReg {@code >= 0;} a rop register to start the search at
+   * @param regCategory {@code > 0;} category of the searched registers.
+   * @return {@code >= 0;} start of available registers.
+   */
+  private int findNextUnreservedRopReg(int startReg, int regCategory) {
+    return findNextUnreservedRopReg(startReg, regCategory, getAlignment(regCategory));
+  }
+
+  /**
    * Finds a range of unreserved rop registers.
    *
    * @param startReg {@code >= 0;} a rop register to start the search at
    * @param width {@code > 0;} the width, in registers, required.
+   * @param alignment the alignment constraint.
    * @return {@code >= 0;} start of available register range.
    */
-  private int findNextUnreservedRopReg(int startReg, int width) {
-    int reg;
-
-    reg = reservedRopRegs.nextClearBit(startReg);
+  private int findNextUnreservedRopReg(int startReg, int width, Alignment alignment) {
+    int reg = alignment.nextClearBit(reservedRopRegs, startReg);
 
     while (true) {
       int i = 1;
@@ -377,36 +453,35 @@ public class FirstFitLocalCombiningAllocator extends RegisterAllocator {
         return reg;
       }
 
-      reg = reservedRopRegs.nextClearBit(reg + i);
+      reg = alignment.nextClearBit(reservedRopRegs, reg + i);
     }
   }
 
   /**
-   * Finds a range of rop regs that can be used for local variables.
+   * Finds rop registers that can be used for local variables.
    * If {@code MIX_LOCALS_AND_OTHER} is {@code false}, this means any
    * rop register that has not yet been used.
    *
    * @param startReg {@code >= 0;} a rop register to start the search at
-   * @param width {@code > 0;} the width, in registers, required.
-   * @return {@code >= 0;} start of available register range.
+   * @param category {@code > 0;} the register category required.
+   * @return {@code >= 0;} start of available registers.
    */
-  private int findRopRegForLocal(int startReg, int width) {
-    int reg;
-
-    reg = usedRopRegs.nextClearBit(startReg);
+  private int findRopRegForLocal(int startReg, int category) {
+    Alignment alignment = getAlignment(category);
+    int reg = alignment.nextClearBit(usedRopRegs, startReg);
 
     while (true) {
       int i = 1;
 
-      while (i < width && !usedRopRegs.get(reg + i)) {
+      while (i < category && !usedRopRegs.get(reg + i)) {
         i++;
       }
 
-      if (i == width) {
+      if (i == category) {
         return reg;
       }
 
-      reg = usedRopRegs.nextClearBit(reg + i);
+      reg = alignment.nextClearBit(usedRopRegs, reg + i);
     }
   }
 
@@ -837,7 +912,7 @@ public class FirstFitLocalCombiningAllocator extends RegisterAllocator {
      * registers we can move the range into.
      */
 
-if (resultRangeStart == -1) {
+    if (resultRangeStart == -1) {
       resultMovesRequired = new BitSet(szSources);
 
       resultRangeStart =
@@ -848,7 +923,7 @@ if (resultRangeStart == -1) {
      * Now, insert any moves required.
      */
 
-for (int i = resultMovesRequired.nextSetBit(0); i >= 0;
+    for (int i = resultMovesRequired.nextSetBit(0); i >= 0;
         i = resultMovesRequired.nextSetBit(i + 1)) {
       insn.changeOneSource(i, insertMoveBefore(insn, sources.get(i)));
     }
@@ -872,9 +947,44 @@ for (int i = resultMovesRequired.nextSetBit(0); i >= 0;
    */
   private int findAnyFittingRange(NormalSsaInsn insn, int rangeLength, int[] categoriesForIndex,
       BitSet outMovesRequired) {
+    Alignment alignment = Alignment.UNSPECIFIED;
+
+    if (DexOptions.ALIGN_64BIT_REGS) {
+      int regNumber = 0;
+      int p64bitsAligned = 0;
+      int p64bitsNotAligned = 0;
+      for (int category : categoriesForIndex) {
+        if (category == 2) {
+          if (isEven(regNumber)) {
+            p64bitsAligned++;
+          } else {
+            p64bitsNotAligned++;
+          }
+          regNumber += 2;
+        } else {
+          regNumber += 1;
+        }
+      }
+
+      if (p64bitsNotAligned > p64bitsAligned) {
+        if (isEven(paramRangeEnd)) {
+          alignment = Alignment.ODD;
+        } else {
+          alignment = Alignment.EVEN;
+        }
+      } else if (p64bitsAligned > 0) {
+        if (isEven(paramRangeEnd)) {
+          alignment = Alignment.EVEN;
+        } else {
+          alignment = Alignment.ODD;
+        }
+      }
+    }
+
     int rangeStart = paramRangeEnd;
     while (true) {
-      rangeStart = findNextUnreservedRopReg(rangeStart, rangeLength);
+      rangeStart = findNextUnreservedRopReg(rangeStart, rangeLength, alignment);
+
       int fitWidth = fitPlanForRange(rangeStart, insn, categoriesForIndex, outMovesRequired);
 
       if (fitWidth >= 0) {
@@ -883,9 +993,14 @@ for (int i = resultMovesRequired.nextSetBit(0); i >= 0;
       rangeStart++;
       outMovesRequired.clear();
     }
+
     return rangeStart;
   }
 
+  private static boolean isEven(int regNumger) {
+    return ((regNumger & 1) == 0);
+  }
+
   /**
    * Attempts to build a plan for fitting a range of sources into rop
    * registers.
@@ -943,7 +1058,7 @@ for (int i = resultMovesRequired.nextSetBit(0); i >= 0;
          *     overlapping moves, which we can't presently handle)
          */
 
-outMovesRequired.set(i);
+        outMovesRequired.set(i);
       } else {
         fitWidth = -1;
         break;
diff --git a/dx/src/com/android/jack/dx/ssa/back/RegisterAllocator.java b/dx/src/com/android/jack/dx/ssa/back/RegisterAllocator.java
index 9a13b8b..0b44412 100644
--- a/dx/src/com/android/jack/dx/ssa/back/RegisterAllocator.java
+++ b/dx/src/com/android/jack/dx/ssa/back/RegisterAllocator.java
@@ -36,6 +36,7 @@ import java.util.ArrayList;
  * Base class of all register allocators.
  */
 public abstract class RegisterAllocator {
+
   /** method being processed */
   protected final SsaMethod ssaMeth;