| Methods Summary |
|---|
| private com.android.dx.rop.code.RopMethod | convert()
interference = LivenessAnalyzer.constructInterferenceGraph(ssaMeth);
if (DEBUG) {
interference.dumpToStdout();
}
RegisterAllocator allocator;
RegisterMapper mapper;
// These are other allocators for debugging or historical comparison
//allocator = new NullRegisterAllocator(ssaMeth, interference);
//allocator = new FirstFitAllocator(ssaMeth, interference);
allocator = new FirstFitLocalCombiningAllocator(ssaMeth, interference,
minimizeRegisters);
mapper = allocator.allocateRegisters();
if (DEBUG) {
System.out.println("Printing reg map");
System.out.println(((BasicRegisterMapper)mapper).toHuman());
}
ssaMeth.setBackMode();
ssaMeth.mapRegisters(mapper);
removePhiFunctions();
if (allocator.wantsParamsMovedHigh()) {
moveParametersToHighRegisters();
}
removeEmptyGotos();
RopMethod ropMethod;
ropMethod = convertToRop();
ropMethod = new IdenticalBlockCombiner(ropMethod).process();
return ropMethod;
|
| private com.android.dx.rop.code.BasicBlock | convertBasicBlock(com.android.dx.ssa.SsaBasicBlock block)Converts a single basic block to rop form.
BasicBlock result;
IntList successorList = block.getRopLabelSuccessorList();
int primarySuccessorLabel = block.getPrimarySuccessorRopLabel();
// Filter out any reference to the SSA form's exit block
// exit block may be null
SsaBasicBlock exitBlock = ssaMeth.getExitBlock();
int exitRopLabel = (exitBlock == null) ? -1 : exitBlock.getRopLabel();
if (successorList.contains(exitRopLabel)) {
if (successorList.size() > 1) {
throw new RuntimeException (
"Exit predecessor must have no other successors"
+ Hex.u2(block.getRopLabel()));
} else {
successorList = IntList.EMPTY;
primarySuccessorLabel = -1;
verifyValidExitPredecessor(block);
}
}
successorList.setImmutable();
result = new BasicBlock(
block.getRopLabel(), convertInsns(block.getInsns()),
successorList,
primarySuccessorLabel);
return result;
|
| private com.android.dx.rop.code.BasicBlockList | convertBasicBlocks()
ArrayList<SsaBasicBlock> blocks = ssaMeth.getBlocks();
// Exit block may be null
SsaBasicBlock exitBlock = ssaMeth.getExitBlock();
int ropBlockCount = ssaMeth.getCountReachableBlocks();
// Don't count the exit block, if it exists
ropBlockCount -= (exitBlock == null) ? 0 : 1;
BasicBlockList result = new BasicBlockList(ropBlockCount);
// Convert all the reachable blocks except the exit block
int ropBlockIndex = 0;
for(SsaBasicBlock b : blocks) {
if (b.isReachable() && b != exitBlock) {
result.set(ropBlockIndex++, convertBasicBlock(b));
}
}
// The exit block, which is discarded, must do nothing.
if (exitBlock != null && exitBlock.getInsns().size() != 0) {
throw new RuntimeException
("Exit block must have no insns when leaving SSA form");
}
return result;
|
| private com.android.dx.rop.code.InsnList | convertInsns(java.util.ArrayList ssaInsns)Converts an insn list to rop form
InsnList result;
int insnCount;
insnCount = ssaInsns.size();
result = new InsnList (insnCount);
for (int i = 0; i < insnCount; i++) {
result.set(i, ssaInsns.get(i).toRopInsn());
}
result.setImmutable();
return result;
|
| private com.android.dx.rop.code.RopMethod | convertToRop()
return new RopMethod(convertBasicBlocks(),
ssaMeth.blockIndexToRopLabel(ssaMeth.getEntryBlockIndex()));
|
| public static com.android.dx.rop.code.RopMethod | convertToRopMethod(com.android.dx.ssa.SsaMethod ssaMeth, boolean minimizeRegisters)Converts a method in SSA form to ROP form.
return new SsaToRop(ssaMeth, minimizeRegisters).convert();
|
| public int[] | getRegistersByFrequency()This method is not presently used.
int regCount = ssaMeth.getRegCount();
Integer[] ret = new Integer[ssaMeth.getRegCount()];
for (int i = 0; i < regCount; i++) {
ret[i] = i;
}
java.util.Arrays.sort(ret, new java.util.Comparator<Integer>() {
public int compare (Integer o1, Integer o2) {
return ssaMeth.getUseListForRegister(o2).size()
- ssaMeth.getUseListForRegister(o1).size();
}
public boolean equals(Object o) {
return o == this;
}
});
int result[] = new int[regCount];
for (int i = 0; i < regCount; i++) {
result[i] = ret[i];
}
return result;
|
| private void | moveParametersToHighRegisters()Moves the parameter registers, which allocateRegisters() places
at the bottom of the frame, up to the top of the frame to match
Dalvik calling convention.
int paramWidth = ssaMeth.getParamWidth();
BasicRegisterMapper mapper
= new BasicRegisterMapper(ssaMeth.getRegCount());
int regCount = ssaMeth.getRegCount();
for (int i = 0; i < regCount; i++) {
if (i < paramWidth) {
mapper.addMapping(i, regCount - paramWidth + i, 1);
} else {
mapper.addMapping(i, i - paramWidth, 1);
}
}
if (DEBUG) {
System.out.printf("Moving %d registers from 0 to %d\n",
paramWidth, regCount - paramWidth);
}
ssaMeth.mapRegisters(mapper);
|
| private void | removeEmptyGotos()Removes all blocks containing only GOTOs from the control flow. Although
much of this work will be done later when converting from rop to dex,
not all simplification cases can be handled there. Furthermore, any no-op
block between the exit block and blocks containing the real return or
throw statements must be removed.
final ArrayList<SsaBasicBlock> blocks = ssaMeth.getBlocks();
ssaMeth.forEachBlockDepthFirst(false, new SsaBasicBlock.Visitor() {
public void visitBlock(SsaBasicBlock b, SsaBasicBlock parent) {
ArrayList<SsaInsn> insns = b.getInsns();
if ((insns.size() == 1)
&& (insns.get(0).getOpcode() == Rops.GOTO)) {
BitSet preds = (BitSet)b.getPredecessors().clone();
for (int i = preds.nextSetBit(0); i >= 0;
i = preds.nextSetBit(i + 1)) {
SsaBasicBlock pb = blocks.get(i);
pb.replaceSuccessor(b.getIndex(),
b.getPrimarySuccessorIndex());
}
}
}
});
|
| private void | removePhiFunctions()See Appel 19.6
To remove the phi instructions in an edge-split SSA representation
we know we can always insert a move in a predecessor block
for (SsaBasicBlock block: ssaMeth.getBlocks()) {
// Add moves in all the pred blocks for each phi insn`
block.forEachPhiInsn(new PhiVisitor(block));
// Delete the phi insns
block.removeAllPhiInsns();
}
/*
* After all move insns have been added: sort them so they don't
* destructively interfere
*/
for (SsaBasicBlock block: ssaMeth.getBlocks()) {
block.scheduleMovesFromPhis();
}
|
| private void | verifyValidExitPredecessor(com.android.dx.ssa.SsaBasicBlock b)Validates that a basic block is a valid end predecessor. It must
end in a RETURN or a THROW. Throws a runtime exception on error.
ArrayList<SsaInsn> insns = b.getInsns();
SsaInsn lastInsn = insns.get(insns.size() - 1);
Rop opcode = lastInsn.getOpcode();
if (opcode.getBranchingness() != Rop.BRANCH_RETURN
&& opcode != Rops.THROW) {
throw new RuntimeException("Exit predecessor must end"
+ " in valid exit statement.");
}
|
