| Methods Summary |
|---|
| public 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);
|
| public 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 {@code regV} to the live-in list for this block. This is
called by the liveness analyzer.
if (liveIn == null) {
liveIn = SetFactory.makeLivenessSet(parent.getRegCount());
}
liveIn.add(regV);
|
| public void | addLiveOut(int regV)Adds {@code regV} to the live-out list for this block. This is 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)Adds 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 = RegisterSpecList.make(source);
NormalSsaInsn 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 = RegisterSpecList.make(source);
NormalSsaInsn toAdd = new NormalSsaInsn(
new PlainInsn(Rops.opMove(result.getType()),
SourcePosition.NO_INFO, result, sources), this);
insns.add(insns.size() - 1, toAdd);
movesFromPhisAtEnd++;
}
|
| public 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));
|
| public 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)Visits all insns in this block.
// This gets called a LOT, and not using an iterator
// saves a lot of allocations and reduces memory usage
int len = insns.size();
for (int i = 0; i < len; i++) {
insns.get(i).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;
|
| public 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 {@code Z} between
this block ({@code A}) and a current successor block
({@code 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 was last calculated to be reachable.
Recalculates reachability if value has never been computed.
if (reachable == -1) {
parent.computeReachability();
}
return (reachable == 1);
|
| 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 = rmeth.getBlocks();
BasicBlock bb = ropBlocks.get(basicBlockIndex);
SsaBasicBlock result =
new SsaBasicBlock(basicBlockIndex, bb.getLabel(), parent);
InsnList 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();
|
| public void | removeSuccessor(int oldIndex)Removes a successor from this block's successor list.
int removeIndex = 0;
for (int i = successorList.size() - 1; i >= 0; i--) {
if (successorList.get(i) == oldIndex) {
removeIndex = i;
} else {
primarySuccessor = successorList.get(i);
}
}
successorList.removeIndex(removeIndex);
successors.clear(oldIndex);
parent.getBlocks().get(oldIndex).predecessors.clear(index);
|
| public 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)Replaces an old successor with a new successor. This will throw
RuntimeException if {@code 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 {@code 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) {
// This is 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.
*/
RegisterSpec originalResultSpec
= firstNonPhiMoveInsn.getResult();
int 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 = 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 = new NormalSsaInsn(
new PlainInsn(Rops.opMove(result.getType()),
SourcePosition.NO_INFO,
tempSpec,
insnToSplit.getSources()), this);
toSchedule.add(insertPlace++, toAdd);
RegisterSpecList newSources = RegisterSpecList.make(tempSpec);
NormalSsaInsn toReplace = new NormalSsaInsn(
new PlainInsn(Rops.opMove(result.getType()),
SourcePosition.NO_INFO,
result,
newSources), this);
toSchedule.set(insertPlace, toReplace);
// The size changed.
sz = toSchedule.size();
}
regsUsedAsSources.clear();
regsUsedAsResults.clear();
}
|
| public void | setReachable(int reach)Sets reachability of block to specified value
reachable = reach;
|
| 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(){@inheritDoc}
return "{" + index + ":" + Hex.u2(ropLabel) + '}";
|
