1 files changed, 197 insertions, 0 deletions
diff --git a/dx/src/com/android/dx/ssa/back/RegisterAllocator.java b/dx/src/com/android/dx/ssa/back/RegisterAllocator.java
new file mode 100644
index 0000000..1f9f70f
--- /dev/null
+++ b/dx/src/com/android/dx/ssa/back/RegisterAllocator.java
@@ -0,0 +1,197 @@
+/*
+ * Copyright (C) 2007 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.dx.ssa.back;
+
+import com.android.dx.rop.code.RegOps;
+import com.android.dx.rop.code.RegisterSpec;
+import com.android.dx.rop.code.PlainInsn;
+import com.android.dx.rop.code.Rops;
+import com.android.dx.rop.code.SourcePosition;
+import com.android.dx.rop.code.RegisterSpecList;
+import com.android.dx.ssa.NormalSsaInsn;
+import com.android.dx.ssa.RegisterMapper;
+import com.android.dx.ssa.SsaInsn;
+import com.android.dx.ssa.SsaMethod;
+import com.android.dx.ssa.SsaBasicBlock;
+import com.android.dx.util.IntSet;
+import com.android.dx.util.IntIterator;
+
+import java.util.BitSet;
+import java.util.ArrayList;
+
+/**
+ * Base class of all register allocators.
+ */
+public abstract class RegisterAllocator {
+    /** method being processed */
+    protected final SsaMethod ssaMeth;
+
+    /** interference graph, indexed by register in both dimensions */
+    protected final InterferenceGraph interference;
+
+    /**
+     * Creates an instance. Call {@code allocateRegisters} to run.
+     * @param ssaMeth method to process.
+     * @param interference Interference graph, indexed by register in both
+     * dimensions.
+     */
+    public RegisterAllocator(SsaMethod ssaMeth,
+            InterferenceGraph interference) {
+        this.ssaMeth = ssaMeth;
+        this.interference = interference;
+    }
+
+    /**
+     * Indicates whether the method params were allocated at the bottom
+     * of the namespace, and thus should be moved up to the top of the
+     * namespace after phi removal.
+     *
+     * @return {@code true} if params should be moved from low to high
+     */
+    public abstract boolean wantsParamsMovedHigh();
+
+    /**
+     * Runs the algorithm.
+     *
+     * @return a register mapper to apply to the {@code SsaMethod}
+     */
+    public abstract RegisterMapper allocateRegisters();
+
+    /**
+     * Returns the category (width) of the definition site of the register.
+     * Returns {@code 1} for undefined registers.
+     *
+     * @param reg register
+     * @return {@code 1..2}
+     */
+    protected final int getCategoryForSsaReg(int reg) {
+        SsaInsn definition = ssaMeth.getDefinitionForRegister(reg);
+
+        if (definition == null) {
+            // an undefined reg
+            return 1;
+        } else {
+            return definition.getResult().getCategory();
+        }
+    }
+
+    /**
+     * Returns the RegisterSpec of the definition of the register.
+     *
+     * @param reg {@code >= 0;} SSA register
+     * @return definition spec of the register or null if it is never defined
+     * (for the case of "version 0" SSA registers)
+     */
+    protected final RegisterSpec getDefinitionSpecForSsaReg(int reg) {
+        SsaInsn definition = ssaMeth.getDefinitionForRegister(reg);
+
+        return definition == null ? null : definition.getResult();
+    }
+
+    /**
+     * Returns true if the definition site of this register is a
+     * move-param (ie, this is a method parameter).
+     *
+     * @param reg register in question
+     * @return {@code true} if this is a method parameter
+     */
+    protected boolean isDefinitionMoveParam(int reg) {
+        SsaInsn defInsn = ssaMeth.getDefinitionForRegister(reg);
+
+        if (defInsn instanceof NormalSsaInsn) {
+            NormalSsaInsn ndefInsn = (NormalSsaInsn) defInsn;
+
+            return ndefInsn.getOpcode().getOpcode() == RegOps.MOVE_PARAM;
+        }
+
+        return false;
+    }
+
+    /**
+     * Inserts a move instruction for a specified SSA register before a
+     * specified instruction, creating a new SSA register and adjusting the
+     * interference graph in the process. The insn currently must be the
+     * last insn in a block.
+     *
+     * @param insn {@code non-null;} insn to insert move before, must
+     * be last insn in block
+     * @param reg {@code non-null;} SSA register to duplicate
+     * @return {@code non-null;} spec of new SSA register created by move
+     */
+    protected final RegisterSpec insertMoveBefore(SsaInsn insn,
+            RegisterSpec reg) {
+        SsaBasicBlock block = insn.getBlock();
+        ArrayList<SsaInsn> insns = block.getInsns();
+        int insnIndex = insns.indexOf(insn);
+
+        if (insnIndex < 0) {
+            throw new IllegalArgumentException (
+                    "specified insn is not in this block");
+        }
+
+        if (insnIndex != insns.size() - 1) {
+            /*
+             * Presently, the interference updater only works when
+             * adding before the last insn, and the last insn must have no
+             * result
+             */
+            throw new IllegalArgumentException(
+                    "Adding move here not supported:" + insn.toHuman());
+        }
+
+        /*
+         * Get new register and make new move instruction.
+         */
+
+        // The new result must not have an associated local variable.
+        RegisterSpec newRegSpec = RegisterSpec.make(ssaMeth.makeNewSsaReg(),
+                reg.getTypeBearer());
+
+        SsaInsn toAdd = SsaInsn.makeFromRop(
+                new PlainInsn(Rops.opMove(newRegSpec.getType()),
+                        SourcePosition.NO_INFO, newRegSpec,
+                        RegisterSpecList.make(reg)), block);
+
+        insns.add(insnIndex, toAdd);
+
+        int newReg = newRegSpec.getReg();
+
+        /*
+         * Adjust interference graph based on what's live out of the current
+         * block and what's used by the final instruction.
+         */
+
+        IntSet liveOut = block.getLiveOutRegs();
+        IntIterator liveOutIter = liveOut.iterator();
+
+        while (liveOutIter.hasNext()) {
+            interference.add(newReg, liveOutIter.next());
+        }
+
+        // Everything that's a source in the last insn interferes.
+        RegisterSpecList sources = insn.getSources();
+        int szSources = sources.size();
+
+        for (int i = 0; i < szSources; i++) {
+            interference.add(newReg, sources.get(i).getReg());
+        }
+
+        ssaMeth.onInsnsChanged();
+
+        return newRegSpec;
+    }
+}