| /* |
| * 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.*; |
| import com.android.dx.rop.type.Type; |
| import com.android.dx.util.IntList; |
| |
| import java.util.ArrayList; |
| import java.util.BitSet; |
| import java.util.HashSet; |
| import java.util.HashMap; |
| |
| /** |
| * 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> |
| */ |
| class SsaRenamer implements Runnable { |
| |
| 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; |
| |
| /** |
| * 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</code> 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 non-null; un-renamed SSA method that will |
| * be renamed. |
| */ |
| SsaRenamer (final SsaMethod ssaMeth) { |
| ropRegCount = ssaMeth.getRegCount(); |
| |
| this.ssaMeth = ssaMeth; |
| /* |
| * Reserve the first N registers in the SSA register space for |
| * "version 0" registers |
| */ |
| nextSsaReg = ropRegCount; |
| 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; |
| } |
| |
| /** |
| * 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 non-null; array to duplicate |
| * @return 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 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 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{ |
| /** non-null; block we're processing. */ |
| private final SsaBasicBlock block; |
| |
| /** |
| * 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</code> |
| * to process. |
| * |
| * @param block 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 { |
| |
| RenamingMapper() { |
| } |
| |
| /** {@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) { |
| RegisterSpec[] childStart; |
| |
| // don't bother duplicating the array for the first child |
| 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</code> is updated and the newly added element |
| * is named, strip that name from any other SSA registers. |
| * </ol> |
| * |
| * @param ropReg >= 0 Rop register number |
| * @param ssaReg non-null; An SSA register that has just |
| * been added to <code>currentMapping</code> |
| */ |
| 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))) { |
| /* |
| * 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) { |
| |
| /* |
| * The register was previously unnamed. This means that a |
| * local starts after it's first assignment in SSA form |
| */ |
| |
| RegisterSpecList ssaSources; |
| |
| 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(); |
| |
| 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(); |
| |
| /* |
| * 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); |
| } |
| } |
| } |
| } |