| Methods Summary |
|---|
| public static SsaMethod | convertToSsaMethod(com.android.dx.rop.code.RopMethod rmeth, int paramWidth, boolean isStatic)returns an SSA representation, edge-split and with phi functions placed
SsaMethod result;
result = SsaMethod.newFromRopMethod(rmeth, paramWidth, isStatic);
edgeSplit(result);
LocalVariableInfo localInfo = LocalVariableExtractor.extract(result);
placePhiFunctions(result, localInfo);
new SsaRenamer(result).run();
/*
* Exit block, added here, is not considered for edge splitting
* or phi placement since no actual control flows to it.
*/
result.makeExitBlock();
return result;
|
| private static void | edgeSplit(SsaMethod result)See Appel section 19.1
Converts CFG into "edge-split" form, such that each node either a
unique successor or unique predecessor.
In addition, the SSA form we use enforces a further constraint,
requiring each block with a final instruction that returns a
value to have a primary successor that has no other
predecessor. This ensures move statements can always be
inserted correctly when phi statements are removed.
edgeSplitPredecessors(result);
edgeSplitMoveExceptionsAndResults(result);
edgeSplitSuccessors(result);
|
| private static void | edgeSplitMoveExceptionsAndResults(SsaMethod ssaMeth)In ROP form, move-exception must occur as the first insn in a block
immediately succeeding the insn that could thrown an exception.
We may need room to insert move insns later, so make sure to split
any block that starts with a move-exception such that there is a
unique move-exception block for each predecessor.
ArrayList<SsaBasicBlock> blocks = ssaMeth.getBlocks();
// New blocks are added to the end of the block list during
// this iteration
for (int i = blocks.size() - 1; i >= 0; i-- ) {
SsaBasicBlock block = blocks.get(i);
// Any block that starts with a move-exception and has more than
// one predecessor...
if (!block.isExitBlock()
&& block.getPredecessors().cardinality() > 1
&& block.getInsns().get(0).isMoveException()) {
// block.getPredecessors() is changed in the loop below
BitSet preds = (BitSet)block.getPredecessors().clone();
for (int j = preds.nextSetBit(0); j >= 0;
j = preds.nextSetBit(j + 1)) {
SsaBasicBlock predecessor = blocks.get(j);
SsaBasicBlock zNode = predecessor.insertNewSuccessor(block);
// Make sure to place the move-exception as the
// first insn...
zNode.getInsns().add(0, block.getInsns().get(0).clone());
}
// remove the move-exception from the original block...
block.getInsns().remove(0);
}
}
|
| private static void | edgeSplitPredecessors(SsaMethod result)Inserts Z nodes as new predecessors for every node that has multiple
successors and multiple predecessors.
ArrayList<SsaBasicBlock> blocks = result.getBlocks();
// New blocks are added to the end of the block list during
// this iteration
for (int i = blocks.size() - 1; i >= 0; i-- ) {
SsaBasicBlock block = blocks.get(i);
if (nodeNeedsUniquePredecessor(block)) {
block.insertNewPredecessor();
}
}
|
| private static void | edgeSplitSuccessors(SsaMethod result)Inserts Z nodes for every node that needs a new
successor.
ArrayList<SsaBasicBlock> blocks = result.getBlocks();
// New blocks are added to the end of the block list during
// this iteration
for (int i = blocks.size() - 1; i >= 0; i-- ) {
SsaBasicBlock block = blocks.get(i);
// successors list is modified in loop below
BitSet successors = (BitSet)block.getSuccessors().clone();
for(int j = successors.nextSetBit(0);
j >= 0; j = successors.nextSetBit(j+1)) {
SsaBasicBlock succ = blocks.get(j);
if (needsNewSuccessor(block, succ)) {
block.insertNewSuccessor(succ);
}
}
}
|
| private static boolean | needsNewSuccessor(SsaBasicBlock block, SsaBasicBlock succ)Returns true if block and successor need a Z-node between them.
Presently, this is true if the final instruction has any sources
or results and the current successor block has more than one
predecessor.
ArrayList<SsaInsn> insns = block.getInsns();
SsaInsn lastInsn = insns.get(insns.size() - 1);
return ((lastInsn.getResult() != null)
|| (lastInsn.getSources().size() > 0))
&& succ.getPredecessors().cardinality() > 1;
|
| private static boolean | nodeNeedsUniquePredecessor(SsaBasicBlock block)
/*
* Any block with that has both multiple successors and multiple
* predecessors needs a new predecessor node.
*/
int countPredecessors = block.getPredecessors().cardinality();
int countSuccessors = block.getSuccessors().cardinality();
return (countPredecessors > 1 && countSuccessors > 1);
|
| private static void | placePhiFunctions(SsaMethod ssaMeth, LocalVariableInfo localInfo)See Appel algorithm 19.6
Place Phi functions in appropriate locations.
ArrayList<SsaBasicBlock> ssaBlocks;
int regCount;
int blockCount;
ssaBlocks = ssaMeth.getBlocks();
blockCount = ssaBlocks.size();
regCount = ssaMeth.getRegCount();
DomFront df = new DomFront(ssaMeth);
DomFront.DomInfo[] domInfos = df.run();
// Bit set of registers vs block index "definition sites"
BitSet[] defsites = new BitSet[regCount];
// Bit set of registers vs block index "phi placement sites"
BitSet[] phisites = new BitSet[regCount];
for (int i = 0; i < regCount; i++) {
defsites[i] = new BitSet(blockCount);
phisites[i] = new BitSet(blockCount);
}
/*
* For each register, build a set of all basic blocks where
* containing an assignment to that register.
*/
for (int bi = 0, s = ssaBlocks.size(); bi < s; bi++) {
SsaBasicBlock b = ssaBlocks.get(bi);
for (SsaInsn insn: b.getInsns()) {
RegisterSpec rs = insn.getResult();
if (rs != null) {
defsites[rs.getReg()].set(bi);
}
}
}
if (DEBUG) {
System.out.println("defsites");
for (int i = 0; i < regCount; i++) {
StringBuilder sb = new StringBuilder();
sb.append('v").append(i).append(": ");
sb.append(defsites[i].toString());
System.out.println(sb);
}
}
BitSet worklist;
/*
* For each register, compute all locations for phi placement
* based on dominance-frontier algorithm.
*/
for (int reg = 0, s = ssaMeth.getRegCount() ; reg < s ; reg++ ) {
int workBlockIndex;
/* Worklist set starts out with each node where reg is assigned */
worklist = (BitSet)(defsites[reg].clone());
while (0 <= (workBlockIndex = worklist.nextSetBit(0))) {
worklist.clear(workBlockIndex);
IntIterator dfIterator
= domInfos[workBlockIndex]
.dominanceFrontiers.iterator();
while (dfIterator.hasNext()) {
int dfBlockIndex = dfIterator.next();
if (!phisites[reg].get(dfBlockIndex)) {
phisites[reg].set(dfBlockIndex);
RegisterSpec rs
= localInfo.getStarts(dfBlockIndex).get(reg);
if (rs == null) {
ssaBlocks.get(dfBlockIndex).addPhiInsnForReg(reg);
} else {
ssaBlocks.get(dfBlockIndex).addPhiInsnForReg(rs);
}
if (!defsites[reg].get(dfBlockIndex)) {
worklist.set(dfBlockIndex);
}
}
}
}
}
if (DEBUG) {
System.out.println("phisites");
for (int i = 0; i < regCount; i++) {
StringBuilder sb = new StringBuilder();
sb.append('v").append(i).append(": ");
sb.append(phisites[i].toString());
System.out.println(sb);
}
}
|
| public static SsaMethod | testEdgeSplit(com.android.dx.rop.code.RopMethod rmeth, int paramWidth, boolean isStatic)Returns an SSA represention with only the edge-splitter run.
SsaMethod result;
result = SsaMethod.newFromRopMethod(rmeth, paramWidth, isStatic);
edgeSplit(result);
return result;
|
| public static SsaMethod | testPhiPlacement(com.android.dx.rop.code.RopMethod rmeth, int paramWidth, boolean isStatic)Returns an SSA represention with only the steps through the
phi placement run.
SsaMethod result;
result = SsaMethod.newFromRopMethod(rmeth, paramWidth, isStatic);
edgeSplit(result);
LocalVariableInfo localInfo = LocalVariableExtractor.extract(result);
placePhiFunctions(result, localInfo);
return result;
|
