| Methods Summary |
|---|
| void | addDomChild(com.android.dx.ssa.SsaBasicBlock child)Adds a basic block as a dom child for this block. Used when constructing
the dom tree.
domChildren.add(child);
|
| void | addInsnToHead(com.android.dx.rop.code.Insn insn)Adds an insn to the head of this basic block, just after any phi
insns.
SsaInsn newInsn = SsaInsn.makeFromRop(insn, this);
insns.add(getCountPhiInsns(), newInsn);
parent.onInsnAdded(newInsn);
|
| public void | addLiveIn(int regV)Adds regV to the live-in list for this block.
Called by the liveness analyzer.
if (liveIn == null) {
liveIn = SetFactory.makeLivenessSet(parent.getRegCount());
}
liveIn.add(regV);
|
| public void | addLiveOut(int regV)Adds regV to the live-out list for this block.
Called by the liveness analyzer.
if (liveOut == null) {
liveOut = SetFactory.makeLivenessSet(parent.getRegCount());
}
liveOut.add(regV);
|
| public void | addMoveToBeginning(com.android.dx.rop.code.RegisterSpec result, com.android.dx.rop.code.RegisterSpec source)Add a move instruction after the phi insn block.
if (result.getReg() == source.getReg()) {
// Sometimes we end up with no-op moves. Ignore them here.
return;
}
RegisterSpecList sources;
sources = RegisterSpecList.make(source);
NormalSsaInsn toAdd;
toAdd = new NormalSsaInsn(
new PlainInsn(Rops.opMove(result.getType()),
SourcePosition.NO_INFO, result, sources), this);
insns.add(getCountPhiInsns(), toAdd);
movesFromPhisAtBeginning++;
|
| public void | addMoveToEnd(com.android.dx.rop.code.RegisterSpec result, com.android.dx.rop.code.RegisterSpec source)Adds a move instruction to the end of this basic block, just
before the last instruction. If the result of the final instruction
is the source in question, then the move is placed at the beginning of
the primary successor block. This is for unversioned registers.
if (result.getReg() == source.getReg()) {
// Sometimes we end up with no-op moves. Ignore them here.
return;
}
/*
* The last Insn has to be a normal SSA insn: a phi can't branch
* or return or cause an exception, etc.
*/
NormalSsaInsn lastInsn;
lastInsn = (NormalSsaInsn)insns.get(insns.size()-1);
if (lastInsn.getResult() != null || lastInsn.getSources().size() > 0) {
/*
* The final insn in this block has a source or result register,
* and the moves we may need to place and schedule may interfere.
* We need to insert this instruction at the
* beginning of the primary successor block instead. We know
* this is safe, because when we edge-split earlier, we ensured
* that each successor has only us as a predecessor.
*/
for (int i = successors.nextSetBit(0)
; i >= 0
; i = successors.nextSetBit(i + 1)) {
SsaBasicBlock succ;
succ = parent.getBlocks().get(i);
succ.addMoveToBeginning(result, source);
}
} else {
/*
* We can safely add a move to the end of the block
* just before the last instruction because
* the final insn does not assign to anything.
*/
RegisterSpecList sources;
sources = RegisterSpecList.make(source);
NormalSsaInsn toAdd;
toAdd = new NormalSsaInsn(
new PlainInsn(Rops.opMove(result.getType()),
SourcePosition.NO_INFO, result, sources), this);
insns.add(insns.size() - 1, toAdd);
movesFromPhisAtEnd++;
}
|
| void | addPhiInsnForReg(int reg)Adds a phi insn to the beginning of this block. The result type of
the phi will be set to void, to indicate that it's currently unknown.
insns.add(0, new PhiInsn(reg, this));
|
| void | addPhiInsnForReg(com.android.dx.rop.code.RegisterSpec resultSpec)Adds a phi insn to the beginning of this block. This is to be used
when the result type or local-association can be determined at phi
insert time.
insns.add(0, new PhiInsn(resultSpec, this));
|
| private static boolean | checkRegUsed(java.util.BitSet regsUsed, com.android.dx.rop.code.RegisterSpec rs)Checks to see if the register is used in a bitset, taking
into account its category/width.
int reg = rs.getReg();
int category = rs.getCategory();
return regsUsed.get(reg)
|| (category == 2 ? regsUsed.get(reg + 1) : false);
|
| public void | exitBlockFixup(com.android.dx.ssa.SsaBasicBlock exitBlock)Attaches block to an exit block if necessary. If this block
is not an exit predecessor or is the exit block, this block does
nothing. For use by {@link com.android.dx.ssa.SsaMethod#makeExitBlock}
if (this == exitBlock) {
return;
}
if (successorList.size() == 0) {
/*
* This is an exit predecessor.
* Set the successor to the exit block
*/
successors.set(exitBlock.index);
successorList.add(exitBlock.index);
primarySuccessor = exitBlock.index;
exitBlock.predecessors.set(this.index);
}
|
| public void | forEachInsn(SsaInsn.Visitor visitor)Visit all insns in this block
for (SsaInsn insn: insns) {
insn.accept(visitor);
}
|
| public void | forEachPhiInsn(PhiInsn.Visitor v)Visits each phi insn
int sz = insns.size();
for (int i = 0; i < sz; i++) {
SsaInsn insn = insns.get(i);
if (insn instanceof PhiInsn) {
v.visitPhiInsn((PhiInsn) insn);
} else {
/*
* Presently we assume PhiInsn's are in a continuous
* block at the top of the list
*/
break;
}
}
|
| private int | getCountPhiInsns()Gets the number of phi insns at the top of this basic block.
int countPhiInsns;
int sz = insns.size();
for (countPhiInsns = 0; countPhiInsns < sz; countPhiInsns++) {
SsaInsn insn = insns.get(countPhiInsns);
if (!(insn instanceof PhiInsn)) {
break;
}
}
return countPhiInsns;
|
| java.util.ArrayList | getDomChildren()Gets the dom children for this node. Don't modify this list.
return domChildren;
|
| public int | getIndex()
return index;
|
| public java.util.ArrayList | getInsns()
return insns;
|
| public com.android.dx.util.IntSet | getLiveInRegs()Returns the set of live-in registers. Valid after register
interference graph has been generated, otherwise empty.
if (liveIn == null) {
liveIn = SetFactory.makeLivenessSet(parent.getRegCount());
}
return liveIn;
|
| public com.android.dx.util.IntSet | getLiveOutRegs()Returns the set of live-out registers. Valid after register
interference graph has been generated, otherwise empty.
if (liveOut == null) {
liveOut = SetFactory.makeLivenessSet(parent.getRegCount());
}
return liveOut;
|
| public SsaMethod | getParent()
return parent;
|
| public java.util.List | getPhiInsns()
return insns.subList(0, getCountPhiInsns());
|
| public java.util.BitSet | getPredecessors()
return predecessors;
|
| public com.android.dx.ssa.SsaBasicBlock | getPrimarySuccessor()
if (primarySuccessor < 0) {
return null;
} else {
return parent.getBlocks().get(primarySuccessor);
}
|
| public int | getPrimarySuccessorIndex()
return primarySuccessor;
|
| public int | getPrimarySuccessorRopLabel()
return parent.blockIndexToRopLabel(primarySuccessor);
|
| public int | getRopLabel()
return ropLabel;
|
| public java.lang.String | getRopLabelString()
return Hex.u2(ropLabel);
|
| public com.android.dx.util.IntList | getRopLabelSuccessorList()
IntList result = new IntList(successorList.size());
int sz = successorList.size();
for (int i = 0; i < sz; i++) {
result.add(parent.blockIndexToRopLabel(successorList.get(i)));
}
return result;
|
| public com.android.dx.util.IntList | getSuccessorList()
return successorList;
|
| public java.util.BitSet | getSuccessors()
return successors;
|
| public com.android.dx.ssa.SsaBasicBlock | insertNewPredecessor()Inserts a new empty GOTO block as a predecessor to this block.
All previous predecessors will be predecessors to the new block.
SsaBasicBlock newPred = parent.makeNewGotoBlock();
// Update the new block
newPred.predecessors = predecessors;
newPred.successors.set(index) ;
newPred.successorList.add(index);
newPred.primarySuccessor = index;
// Update us
predecessors = new BitSet(parent.getBlocks().size());
predecessors.set(newPred.index);
// Update our (soon-to-be) old predecessors
for (int i = newPred.predecessors.nextSetBit(0); i >= 0;
i = newPred.predecessors.nextSetBit(i + 1)) {
SsaBasicBlock predBlock = parent.getBlocks().get(i);
predBlock.replaceSuccessor(index, newPred.index);
}
return newPred;
|
| public com.android.dx.ssa.SsaBasicBlock | insertNewSuccessor(com.android.dx.ssa.SsaBasicBlock other)Constructs and inserts a new empty GOTO block Z between
this block (A) and a current successor block
(B). The new block will replace B as A's successor and
A as B's predecessor. A and B will no longer be directly connected.
If B is listed as a successor multiple times, all references
are replaced.
SsaBasicBlock newSucc = parent.makeNewGotoBlock();
if (!successors.get(other.index)) {
throw new RuntimeException("Block " + other.getRopLabelString()
+ " not successor of " + getRopLabelString());
}
// Update the new block
newSucc.predecessors.set(this.index);
newSucc.successors.set(other.index) ;
newSucc.successorList.add(other.index);
newSucc.primarySuccessor = other.index;
// Update us
for (int i = successorList.size() - 1 ; i >= 0; i--) {
if(successorList.get(i) == other.index) {
successorList.set(i, newSucc.index);
}
}
if (primarySuccessor == other.index) {
primarySuccessor = newSucc.index;
}
successors.clear(other.index);
successors.set(newSucc.index);
// Update "other"
other.predecessors.set(newSucc.index);
other.predecessors.set(index, successors.get(other.index));
return newSucc;
|
| public boolean | isExitBlock()
return index == parent.getExitBlockIndex();
|
| public boolean | isReachable()Returns true if this block is reachable (that is, it hasn't been
unlinked from the control flow of this method). This currently tests
that it's either the start block or it has predecessors, which suffices
for all current control flow transformations.
return index == parent.getEntryBlockIndex()
|| predecessors.cardinality() > 0;
|
| public static com.android.dx.ssa.SsaBasicBlock | newFromRop(com.android.dx.rop.code.RopMethod rmeth, int basicBlockIndex, SsaMethod parent)Creates a new SSA basic block from a ROP form basic block.
BasicBlockList ropBlocks;
SsaBasicBlock result;
InsnList ropInsns;
BasicBlock bb;
ropBlocks = rmeth.getBlocks();
bb = ropBlocks.get(basicBlockIndex);
result = new SsaBasicBlock(basicBlockIndex, bb.getLabel(), parent);
ropInsns = bb.getInsns();
result.insns.ensureCapacity(ropInsns.size());
for (int i = 0, sz = ropInsns.size() ; i < sz ; i++) {
result.insns.add(new NormalSsaInsn (ropInsns.get(i), result));
}
result.predecessors = SsaMethod.bitSetFromLabelList(
ropBlocks,
rmeth.labelToPredecessors(bb.getLabel()));
result.successors
= SsaMethod.bitSetFromLabelList(ropBlocks, bb.getSuccessors());
result.successorList
= SsaMethod.indexListFromLabelList(ropBlocks,
bb.getSuccessors());
if (result.successorList.size() != 0) {
int primarySuccessor = bb.getPrimarySuccessor();
result.primarySuccessor = (primarySuccessor < 0)
? -1 : ropBlocks.indexOfLabel(primarySuccessor);
}
return result;
|
| public void | removeAllPhiInsns()Deletes all phi insns. Do this after adding appropriate move insns.
/*
* Presently we assume PhiInsn's are in a continuous
* block at the top of the list
*/
insns.subList(0, getCountPhiInsns()).clear();
|
| void | replaceLastInsn(com.android.dx.rop.code.Insn insn)Replaces the last insn in this block. The provided insn must have
some branchingness.
if (insn.getOpcode().getBranchingness() == Rop.BRANCH_NONE) {
throw new IllegalArgumentException("last insn must branch");
}
SsaInsn oldInsn = insns.get(insns.size() - 1);
SsaInsn newInsn = SsaInsn.makeFromRop(insn, this);
insns.set(insns.size() - 1, newInsn);
parent.onInsnRemoved(oldInsn);
parent.onInsnAdded(newInsn);
|
| public void | replaceSuccessor(int oldIndex, int newIndex)Replace an old successor with a new successor.
Throws RuntimeException if oldIndex was not a successor.
if (oldIndex == newIndex) {
return;
}
// Update us
successors.set(newIndex);
if (primarySuccessor == oldIndex) {
primarySuccessor = newIndex;
}
for (int i = successorList.size() - 1 ; i >= 0; i--) {
if(successorList.get(i) == oldIndex) {
successorList.set(i, newIndex);
}
}
successors.clear(oldIndex);
// Update new successor
parent.getBlocks().get(newIndex).predecessors.set(index);
// Update old successor
parent.getBlocks().get(oldIndex).predecessors.clear(index);
|
| public void | scheduleMovesFromPhis()Sorts move instructions added via addMoveToEnd during
phi removal so that results don't overwrite sources that are used.
For use after all phis have been removed and all calls to
addMoveToEnd() have been made.
This is necessary because copy-propogation may have left us in a state
where the same basic block has the same register as a phi operand
and a result. In this case, the register in the phi operand always
refers value before any other phis have executed.
if (movesFromPhisAtBeginning > 1) {
List<SsaInsn> toSchedule;
toSchedule = insns.subList(0, movesFromPhisAtBeginning);
scheduleUseBeforeAssigned(toSchedule);
SsaInsn firstNonPhiMoveInsn = insns.get(movesFromPhisAtBeginning);
//TODO it's actually possible that this case never happens,
//because a move-exception block, having only one predecessor
//in SSA form, perhaps is never on a dominance frontier.
if (firstNonPhiMoveInsn.isMoveException()) {
if (true) {
/*
* We've yet to observe this case, and if it can
* occur the code written to handle it probably
* does not work.
*/
throw new RuntimeException(
"Unexpected: moves from "
+"phis before move-exception");
} else {
// A move-exception insn must be placed first in this block
// We need to move it there, and deal with possible
// interference.
boolean moveExceptionInterferes = false;
int moveExceptionResult
= firstNonPhiMoveInsn.getResult().getReg();
// Does the move-exception result reg interfere with the
// phi moves?
for(SsaInsn insn: toSchedule) {
if (insn.isResultReg(moveExceptionResult)
|| insn.isRegASource(moveExceptionResult)) {
moveExceptionInterferes = true;
break;
}
}
if (!moveExceptionInterferes) {
// The easy case
insns.remove(movesFromPhisAtBeginning);
insns.add(0, firstNonPhiMoveInsn);
} else {
// We need to move the result to a spare reg and move it
// back.
int spareRegister;
RegisterSpec originalResultSpec;
originalResultSpec = firstNonPhiMoveInsn.getResult();
spareRegister = parent.borrowSpareRegister(
originalResultSpec.getCategory());
// We now move it to a spare register
firstNonPhiMoveInsn.changeResultReg(spareRegister);
RegisterSpec tempSpec = firstNonPhiMoveInsn.getResult();
insns.add(0, firstNonPhiMoveInsn);
// And here we move it back
NormalSsaInsn toAdd;
toAdd = new NormalSsaInsn(
new PlainInsn(Rops.opMove(
tempSpec.getType()),
SourcePosition.NO_INFO,
originalResultSpec,
RegisterSpecList.make(tempSpec)),
this);
// Place it immediately after the phi-moves,
// overwriting the move-exception that was there.
insns.set(movesFromPhisAtBeginning + 1, toAdd);
}
}
}
}
if (movesFromPhisAtEnd > 1) {
scheduleUseBeforeAssigned(
insns.subList(insns.size() - movesFromPhisAtEnd - 1,
insns.size() - 1));
}
// Return registers borrowed here and in scheduleUseBeforeAssigned()
parent.returnSpareRegisters();
|
| private void | scheduleUseBeforeAssigned(java.util.List toSchedule)Ensures that all move operations in this block occur such that
reads of any register happen before writes to that register.
NOTE: caller is expected to returnSpareRegisters()!
TODO See Briggs, et al "Practical Improvements to the Construction and
Destruction of Static Single Assignment Form" section 5. a) This can
be done in three passes.
BitSet regsUsedAsSources = new BitSet(parent.getRegCount());
// TODO get rid of this
BitSet regsUsedAsResults = new BitSet(parent.getRegCount());
int sz = toSchedule.size();
int insertPlace = 0;
while (insertPlace < sz) {
int oldInsertPlace = insertPlace;
// Record all registers used as sources in this block.
for (int i = insertPlace; i < sz; i++) {
setRegsUsed(regsUsedAsSources,
toSchedule.get(i).getSources().get(0));
setRegsUsed(regsUsedAsResults,
toSchedule.get(i).getResult());
}
/*
* If there are no circular dependencies, then there exists
* n instructions where n > 1 whose result is not used as a source.
*/
for (int i = insertPlace; i <sz; i++) {
SsaInsn insn = toSchedule.get(i);
/*
* Move these n registers to the front, since they overwrite
* nothing.
*/
if (!checkRegUsed(regsUsedAsSources, insn.getResult())) {
Collections.swap(toSchedule, i, insertPlace++);
}
}
// If we've made no progress in this iteration, there's a
// circular dependency. Split it using the temp reg.
if (oldInsertPlace == insertPlace) {
SsaInsn insnToSplit = null;
// Find an insn whose result is used as a source.
for (int i = insertPlace; i < sz; i++) {
SsaInsn insn = toSchedule.get(i);
if (checkRegUsed(regsUsedAsSources, insn.getResult())
&& checkRegUsed(regsUsedAsResults,
insn.getSources().get(0))) {
insnToSplit = insn;
// We're going to split this insn--move it to the
// front
Collections.swap(toSchedule, insertPlace, i);
break;
}
}
// At least one insn will be set above
RegisterSpec result = insnToSplit.getResult();
RegisterSpec tempSpec = result.withReg(
parent.borrowSpareRegister(result.getCategory()));
NormalSsaInsn toAdd;
toAdd = new NormalSsaInsn(
new PlainInsn(Rops.opMove(result.getType()),
SourcePosition.NO_INFO,
tempSpec,
insnToSplit.getSources()), this);
toSchedule.add(insertPlace++, toAdd);
NormalSsaInsn toReplace;
RegisterSpecList newSources;
newSources = RegisterSpecList.make(tempSpec);
toReplace = new NormalSsaInsn(
new PlainInsn(Rops.opMove(result.getType()),
SourcePosition.NO_INFO,
result,
newSources), this);
toSchedule.set(insertPlace, toReplace);
// size has changed
sz = toSchedule.size();
}
regsUsedAsSources.clear();
regsUsedAsResults.clear();
}
|
| private static void | setRegsUsed(java.util.BitSet regsUsed, com.android.dx.rop.code.RegisterSpec rs)Sets the register as used in a bitset, taking into account its
category/width.
regsUsed.set(rs.getReg());
if (rs.getCategory() > 1) {
regsUsed.set(rs.getReg() + 1);
}
|
| public java.lang.String | toString()
return "{" + index + ":" + Hex.u2(ropLabel) + '}";
|
