/* * 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.
* * See Appel algorithm 19.7
* * 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.
* * 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.
* * 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.
*/
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
*
*
* @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);
}
}
}
}