summaryrefslogtreecommitdiff
path: root/dx/src/com/android/dx/ssa/SsaRenamer.java
diff options
context:
space:
mode:
Diffstat (limited to 'dx/src/com/android/dx/ssa/SsaRenamer.java')
-rw-r--r--dx/src/com/android/dx/ssa/SsaRenamer.java662
1 files changed, 662 insertions, 0 deletions
diff --git a/dx/src/com/android/dx/ssa/SsaRenamer.java b/dx/src/com/android/dx/ssa/SsaRenamer.java
new file mode 100644
index 0000000..58e4142
--- /dev/null
+++ b/dx/src/com/android/dx/ssa/SsaRenamer.java
@@ -0,0 +1,662 @@
+/*
+ * 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;
+
+import com.android.dx.rop.code.LocalItem;
+import com.android.dx.rop.code.PlainInsn;
+import com.android.dx.rop.code.RegisterSpec;
+import com.android.dx.rop.code.RegisterSpecList;
+import com.android.dx.rop.code.Rops;
+import com.android.dx.rop.code.SourcePosition;
+import com.android.dx.rop.type.Type;
+import com.android.dx.util.IntList;
+
+import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.HashMap;
+import java.util.HashSet;
+
+/**
+ * Complete transformation to SSA form by renaming all registers accessed.<p>
+ *
+ * See Appel algorithm 19.7<p>
+ *
+ * Unlike the original algorithm presented in Appel, this renamer converts
+ * to a new flat (versionless) register space. The "version 0" registers,
+ * which represent the initial state of the Rop registers and should never
+ * actually be meaningfully accessed in a legal program, are represented
+ * as the first N registers in the SSA namespace. Subsequent assignments
+ * are assigned new unique names. Note that the incoming Rop representation
+ * has a concept of register widths, where 64-bit values are stored into
+ * two adjoining Rop registers. This adjoining register representation is
+ * ignored in SSA form conversion and while in SSA form, each register can be e
+ * either 32 or 64 bits wide depending on use. The adjoining-register
+ * represention is re-created later when converting back to Rop form. <p>
+ *
+ * But, please note, the SSA Renamer's ignoring of the adjoining-register ROP
+ * representation means that unaligned accesses to 64-bit registers are not
+ * supported. For example, you cannot do a 32-bit operation on a portion of
+ * a 64-bit register. This will never be observed to happen when coming
+ * from Java code, of course.<p>
+ *
+ * The implementation here, rather than keeping a single register version
+ * stack for the entire method as the dom tree is walked, instead keeps
+ * a mapping table for the current block being processed. Once the
+ * current block has been processed, this mapping table is then copied
+ * and used as the initial state for child blocks.<p>
+ */
+public class SsaRenamer implements Runnable {
+ /** debug flag */
+ private static final boolean DEBUG = false;
+
+ /** method we're processing */
+ private final SsaMethod ssaMeth;
+
+ /** next available SSA register */
+ private int nextSsaReg;
+
+ /** the number of original rop registers */
+ private final int ropRegCount;
+
+ /** work only on registers above this value */
+ private int threshold;
+
+ /**
+ * indexed by block index; register version state for each block start.
+ * This list is updated by each dom parent for its children. The only
+ * sub-arrays that exist at any one time are the start states for blocks
+ * yet to be processed by a {@code BlockRenamer} instance.
+ */
+ private final RegisterSpec[][] startsForBlocks;
+
+ /** map of SSA register number to debug (local var names) or null of n/a */
+ private final ArrayList<LocalItem> ssaRegToLocalItems;
+
+ /**
+ * maps SSA registers back to the original rop number. Used for
+ * debug only.
+ */
+ private IntList ssaRegToRopReg;
+
+ /**
+ * Constructs an instance of the renamer
+ *
+ * @param ssaMeth {@code non-null;} un-renamed SSA method that will
+ * be renamed.
+ */
+ public SsaRenamer(SsaMethod ssaMeth) {
+ ropRegCount = ssaMeth.getRegCount();
+
+ this.ssaMeth = ssaMeth;
+
+ /*
+ * Reserve the first N registers in the SSA register space for
+ * "version 0" registers.
+ */
+ nextSsaReg = ropRegCount;
+ threshold = 0;
+ startsForBlocks = new RegisterSpec[ssaMeth.getBlocks().size()][];
+
+ ssaRegToLocalItems = new ArrayList<LocalItem>();
+
+ if (DEBUG) {
+ ssaRegToRopReg = new IntList(ropRegCount);
+ }
+
+ /*
+ * Appel 19.7
+ *
+ * Initialization:
+ * for each variable a // register i
+ * Count[a] <- 0 // nextSsaReg, flattened
+ * Stack[a] <- 0 // versionStack
+ * push 0 onto Stack[a]
+ *
+ */
+
+ // top entry for the version stack is version 0
+ RegisterSpec[] initialRegMapping = new RegisterSpec[ropRegCount];
+ for (int i = 0; i < ropRegCount; i++) {
+ // everyone starts with a version 0 register
+ initialRegMapping[i] = RegisterSpec.make(i, Type.VOID);
+
+ if (DEBUG) {
+ ssaRegToRopReg.add(i);
+ }
+ }
+
+ // Initial state for entry block
+ startsForBlocks[ssaMeth.getEntryBlockIndex()] = initialRegMapping;
+ }
+
+ /**
+ * Constructs an instance of the renamer with threshold set
+ *
+ * @param ssaMeth {@code non-null;} un-renamed SSA method that will
+ * be renamed.
+ * @param thresh registers below this number are unchanged
+ */
+ public SsaRenamer(SsaMethod ssaMeth, int thresh) {
+ this(ssaMeth);
+ threshold = thresh;
+ }
+
+ /**
+ * Performs renaming transformation, modifying the method's instructions
+ * in-place.
+ */
+ public void run() {
+ // Rename each block in dom-tree DFS order.
+ ssaMeth.forEachBlockDepthFirstDom(new SsaBasicBlock.Visitor() {
+ public void visitBlock (SsaBasicBlock block,
+ SsaBasicBlock unused) {
+ new BlockRenamer(block).process();
+ }
+ });
+
+ ssaMeth.setNewRegCount(nextSsaReg);
+ ssaMeth.onInsnsChanged();
+
+ if (DEBUG) {
+ System.out.println("SSA\tRop");
+ /*
+ * We're going to compute the version of the rop register
+ * by keeping a running total of how many times the rop
+ * register has been mapped.
+ */
+ int[] versions = new int[ropRegCount];
+
+ int sz = ssaRegToRopReg.size();
+ for (int i = 0; i < sz; i++) {
+ int ropReg = ssaRegToRopReg.get(i);
+ System.out.println(i + "\t" + ropReg + "["
+ + versions[ropReg] + "]");
+ versions[ropReg]++;
+ }
+ }
+ }
+
+ /**
+ * Duplicates a RegisterSpec array.
+ *
+ * @param orig {@code non-null;} array to duplicate
+ * @return {@code non-null;} new instance
+ */
+ private static RegisterSpec[] dupArray(RegisterSpec[] orig) {
+ RegisterSpec[] copy = new RegisterSpec[orig.length];
+
+ System.arraycopy(orig, 0, copy, 0, orig.length);
+
+ return copy;
+ }
+
+ /**
+ * Gets a local variable item for a specified register.
+ *
+ * @param ssaReg register in SSA name space
+ * @return {@code null-ok;} Local variable name or null if none
+ */
+ private LocalItem getLocalForNewReg(int ssaReg) {
+ if (ssaReg < ssaRegToLocalItems.size()) {
+ return ssaRegToLocalItems.get(ssaReg);
+ } else {
+ return null;
+ }
+ }
+
+ /**
+ * Records a debug (local variable) name for a specified register.
+ *
+ * @param ssaReg non-null named register spec in SSA name space
+ */
+ private void setNameForSsaReg(RegisterSpec ssaReg) {
+ int reg = ssaReg.getReg();
+ LocalItem local = ssaReg.getLocalItem();
+
+ ssaRegToLocalItems.ensureCapacity(reg + 1);
+ while (ssaRegToLocalItems.size() <= reg) {
+ ssaRegToLocalItems.add(null);
+ }
+
+ ssaRegToLocalItems.set(reg, local);
+ }
+
+ /**
+ * Returns true if this SSA register is below the specified threshold.
+ * Used when most code is already in SSA form, and renaming is needed only
+ * for registers above a certain threshold.
+ *
+ * @param ssaReg the SSA register in question
+ * @return {@code true} if its register number is below the threshold
+ */
+ private boolean isBelowThresholdRegister(int ssaReg) {
+ return ssaReg < threshold;
+ }
+
+ /**
+ * Returns true if this SSA register is a "version 0"
+ * register. All version 0 registers are assigned the first N register
+ * numbers, where N is the count of original rop registers.
+ *
+ * @param ssaReg the SSA register in question
+ * @return true if it is a version 0 register.
+ */
+ private boolean isVersionZeroRegister(int ssaReg) {
+ return ssaReg < ropRegCount;
+ }
+
+ /**
+ * Returns true if a and b are equal or are both null.
+ *
+ * @param a null-ok
+ * @param b null-ok
+ * @return Returns true if a and b are equal or are both null
+ */
+ private static boolean equalsHandlesNulls(Object a, Object b) {
+ return a == b || (a != null && a.equals(b));
+ }
+
+ /**
+ * Processes all insns in a block and renames their registers
+ * as appropriate.
+ */
+ private class BlockRenamer implements SsaInsn.Visitor{
+ /** {@code non-null;} block we're processing. */
+ private final SsaBasicBlock block;
+
+ /**
+ * {@code non-null;} indexed by old register name. The current
+ * top of the version stack as seen by this block. It's
+ * initialized from the ending state of its dom parent,
+ * updated as the block's instructions are processed, and then
+ * copied to each one of its dom children.
+ */
+ private final RegisterSpec[] currentMapping;
+
+ /**
+ * contains the set of moves we need to keep to preserve local
+ * var info. All other moves will be deleted.
+ */
+ private final HashSet<SsaInsn> movesToKeep;
+
+ /**
+ * maps the set of insns to replace after renaming is finished
+ * on the block.
+ */
+ private final HashMap<SsaInsn, SsaInsn> insnsToReplace;
+
+ private final RenamingMapper mapper;
+
+ /**
+ * Constructs a block renamer instance. Call {@code process}
+ * to process.
+ *
+ * @param block {@code non-null;} block to process
+ */
+ BlockRenamer(final SsaBasicBlock block) {
+ this.block = block;
+ currentMapping = startsForBlocks[block.getIndex()];
+ movesToKeep = new HashSet<SsaInsn>();
+ insnsToReplace = new HashMap<SsaInsn, SsaInsn>();
+ mapper = new RenamingMapper();
+
+ // We don't need our own start state anymore
+ startsForBlocks[block.getIndex()] = null;
+ }
+
+ /**
+ * Provides a register mapping between the old register space
+ * and the current renaming mapping. The mapping is updated
+ * as the current block's instructions are processed.
+ */
+ private class RenamingMapper extends RegisterMapper {
+ public RenamingMapper() {
+ // This space intentionally left blank.
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public int getNewRegisterCount() {
+ return nextSsaReg;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public RegisterSpec map(RegisterSpec registerSpec) {
+ if (registerSpec == null) return null;
+
+ int reg = registerSpec.getReg();
+
+ // For debugging: assert that the mapped types are compatible.
+ if (DEBUG) {
+ RegisterSpec newVersion = currentMapping[reg];
+ if (newVersion.getBasicType() != Type.BT_VOID
+ && registerSpec.getBasicFrameType()
+ != newVersion.getBasicFrameType()) {
+
+ throw new RuntimeException(
+ "mapping registers of incompatible types! "
+ + registerSpec
+ + " " + currentMapping[reg]);
+ }
+ }
+
+ return registerSpec.withReg(currentMapping[reg].getReg());
+ }
+ }
+
+ /**
+ * Renames all the variables in this block and inserts appriopriate
+ * phis in successor blocks.
+ */
+ public void process() {
+ /*
+ * From Appel:
+ *
+ * Rename(n) =
+ * for each statement S in block n // 'statement' in 'block'
+ */
+
+ block.forEachInsn(this);
+
+ updateSuccessorPhis();
+
+ // Delete all move insns in this block.
+ ArrayList<SsaInsn> insns = block.getInsns();
+ int szInsns = insns.size();
+
+ for (int i = szInsns - 1; i >= 0 ; i--) {
+ SsaInsn insn = insns.get(i);
+ SsaInsn replaceInsn;
+
+ replaceInsn = insnsToReplace.get(insn);
+
+ if (replaceInsn != null) {
+ insns.set(i, replaceInsn);
+ } else if (insn.isNormalMoveInsn()
+ && !movesToKeep.contains(insn)) {
+ insns.remove(i);
+ }
+ }
+
+ // Store the start states for our dom children.
+ boolean first = true;
+ for (SsaBasicBlock child : block.getDomChildren()) {
+ if (child != block) {
+ // Don't bother duplicating the array for the first child.
+ RegisterSpec[] childStart = first ? currentMapping
+ : dupArray(currentMapping);
+
+ startsForBlocks[child.getIndex()] = childStart;
+ first = false;
+ }
+ }
+
+ // currentMapping is owned by a child now.
+ }
+
+ /**
+ * Enforces a few contraints when a register mapping is added.
+ *
+ * <ol>
+ * <li> Ensures that all new SSA registers specs in the mapping
+ * table with the same register number are identical. In effect, once
+ * an SSA register spec has received or lost a local variable name,
+ * then every old-namespace register that maps to it should gain or
+ * lose its local variable name as well.
+ * <li> Records the local name associated with the
+ * register so that a register is never associated with more than one
+ * local.
+ * <li> ensures that only one SSA register
+ * at a time is considered to be associated with a local variable. When
+ * {@code currentMapping} is updated and the newly added element
+ * is named, strip that name from any other SSA registers.
+ * </ol>
+ *
+ * @param ropReg {@code >= 0;} rop register number
+ * @param ssaReg {@code non-null;} an SSA register that has just
+ * been added to {@code currentMapping}
+ */
+ private void addMapping(int ropReg, RegisterSpec ssaReg) {
+ int ssaRegNum = ssaReg.getReg();
+ LocalItem ssaRegLocal = ssaReg.getLocalItem();
+
+ currentMapping[ropReg] = ssaReg;
+
+ /*
+ * Ensure all SSA register specs with the same reg are identical.
+ */
+ for (int i = currentMapping.length - 1; i >= 0; i--) {
+ RegisterSpec cur = currentMapping[i];
+
+ if (ssaRegNum == cur.getReg()) {
+ currentMapping[i] = ssaReg;
+ }
+ }
+
+ // All further steps are for registers with local information.
+ if (ssaRegLocal == null) {
+ return;
+ }
+
+ // Record that this SSA reg has been associated with a local.
+ setNameForSsaReg(ssaReg);
+
+ // Ensure that no other SSA regs are associated with this local.
+ for (int i = currentMapping.length - 1; i >= 0; i--) {
+ RegisterSpec cur = currentMapping[i];
+
+ if (ssaRegNum != cur.getReg()
+ && ssaRegLocal.equals(cur.getLocalItem())) {
+ currentMapping[i] = cur.withLocalItem(null);
+ }
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ *
+ * Phi insns have their result registers renamed.
+ */
+ public void visitPhiInsn(PhiInsn phi) {
+ /* don't process sources for phi's */
+ processResultReg(phi);
+ }
+
+ /**
+ * {@inheritDoc}
+ *
+ * Move insns are treated as a simple mapping operation, and
+ * will later be removed unless they represent a local variable
+ * assignment. If they represent a local variable assignement, they
+ * are preserved.
+ */
+ public void visitMoveInsn(NormalSsaInsn insn) {
+ /*
+ * For moves: copy propogate the move if we can, but don't
+ * if we need to preserve local variable info and the
+ * result has a different name than the source.
+ */
+
+ RegisterSpec ropResult = insn.getResult();
+ int ropResultReg = ropResult.getReg();
+ int ropSourceReg = insn.getSources().get(0).getReg();
+
+ insn.mapSourceRegisters(mapper);
+ int ssaSourceReg = insn.getSources().get(0).getReg();
+
+ LocalItem sourceLocal
+ = currentMapping[ropSourceReg].getLocalItem();
+ LocalItem resultLocal = ropResult.getLocalItem();
+
+ /*
+ * A move from a register that's currently associated with a local
+ * to one that will not be associated with a local does not need
+ * to be preserved, but the local association should remain.
+ * Hence, we inherit the sourceLocal where the resultLocal is null.
+ */
+
+ LocalItem newLocal
+ = (resultLocal == null) ? sourceLocal : resultLocal;
+ LocalItem associatedLocal = getLocalForNewReg(ssaSourceReg);
+
+ /*
+ * If we take the new local, will only one local have ever
+ * been associated with this SSA reg?
+ */
+ boolean onlyOneAssociatedLocal
+ = associatedLocal == null || newLocal == null
+ || newLocal.equals(associatedLocal);
+
+ /*
+ * If we're going to copy-propogate, then the ssa register
+ * spec that's going to go into the mapping is made up of
+ * the source register number mapped from above, the type
+ * of the result, and the name either from the result (if
+ * specified) or inherited from the existing mapping.
+ *
+ * The move source has incomplete type information in null
+ * object cases, so the result type is used.
+ */
+ RegisterSpec ssaReg
+ = RegisterSpec.makeLocalOptional(
+ ssaSourceReg, ropResult.getType(), newLocal);
+
+ if (!Optimizer.getPreserveLocals() || (onlyOneAssociatedLocal
+ && equalsHandlesNulls(newLocal, sourceLocal)) &&
+ threshold == 0) {
+ /*
+ * We don't have to keep this move to preserve local
+ * information. Either the name is the same, or the result
+ * register spec is unnamed.
+ */
+
+ addMapping(ropResultReg, ssaReg);
+ } else if (onlyOneAssociatedLocal && sourceLocal == null &&
+ threshold == 0) {
+ /*
+ * The register was previously unnamed. This means that a
+ * local starts after it's first assignment in SSA form
+ */
+
+ RegisterSpecList ssaSources = RegisterSpecList.make(
+ RegisterSpec.make(ssaReg.getReg(),
+ ssaReg.getType(), newLocal));
+
+ SsaInsn newInsn
+ = SsaInsn.makeFromRop(
+ new PlainInsn(Rops.opMarkLocal(ssaReg),
+ SourcePosition.NO_INFO, null, ssaSources),block);
+
+ insnsToReplace.put(insn, newInsn);
+
+ // Just map as above.
+ addMapping(ropResultReg, ssaReg);
+ } else {
+ /*
+ * Do not copy-propogate, since the two registers have
+ * two different local-variable names.
+ */
+ processResultReg(insn);
+
+ movesToKeep.add(insn);
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ *
+ * All insns that are not move or phi insns have their source registers
+ * mapped ot the current mapping. Their result registers are then
+ * renamed to a new SSA register which is then added to the current
+ * register mapping.
+ */
+ public void visitNonMoveInsn(NormalSsaInsn insn) {
+ /* for each use of some variable X in S */
+ insn.mapSourceRegisters(mapper);
+
+ processResultReg(insn);
+ }
+
+ /**
+ * Renames the result register of this insn and updates the
+ * current register mapping. Does nothing if this insn has no result.
+ * Applied to all non-move insns.
+ *
+ * @param insn insn to process.
+ */
+ void processResultReg(SsaInsn insn) {
+ RegisterSpec ropResult = insn.getResult();
+
+ if (ropResult == null) {
+ return;
+ }
+
+ int ropReg = ropResult.getReg();
+ if (isBelowThresholdRegister(ropReg)) {
+ return;
+ }
+
+ insn.changeResultReg(nextSsaReg);
+ addMapping(ropReg, insn.getResult());
+
+ if (DEBUG) {
+ ssaRegToRopReg.add(ropReg);
+ }
+
+ nextSsaReg++;
+ }
+
+ /**
+ * Updates the phi insns in successor blocks with operands based
+ * on the current mapping of the rop register the phis represent.
+ */
+ private void updateSuccessorPhis() {
+ PhiInsn.Visitor visitor = new PhiInsn.Visitor() {
+ public void visitPhiInsn (PhiInsn insn) {
+ int ropReg;
+
+ ropReg = insn.getRopResultReg();
+ if (isBelowThresholdRegister(ropReg)) {
+ return;
+ }
+
+ /*
+ * Never add a version 0 register as a phi
+ * operand. Version 0 registers represent the
+ * initial register state, and thus are never
+ * significant. Furthermore, the register liveness
+ * algorithm doesn't properly count them as "live
+ * in" at the beginning of the method.
+ */
+
+ RegisterSpec stackTop = currentMapping[ropReg];
+ if (!isVersionZeroRegister(stackTop.getReg())) {
+ insn.addPhiOperand(stackTop, block);
+ }
+ }
+ };
+
+ BitSet successors = block.getSuccessors();
+ for (int i = successors.nextSetBit(0); i >= 0;
+ i = successors.nextSetBit(i + 1)) {
+ SsaBasicBlock successor = ssaMeth.getBlocks().get(i);
+ successor.forEachPhiInsn(visitor);
+ }
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-23 18:53:43 +0000