/*
* 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.RegisterSpec;
import com.android.dx.rop.code.RopMethod;
import com.android.dx.util.IntIterator;
import java.util.ArrayList;
import java.util.BitSet;
/**
* Converts ROP methods to SSA Methods
*/
public class SsaConverter {
public static boolean DEBUG = false;
/**
* returns an SSA representation, edge-split and with phi functions placed
* @param rmeth input
* @param paramWidth the total width, in register-units, of the method's
* parameters
* @param isStatic true if this method has no 'this'
* pointer argument
* @return output in SSA form
*/
public static SsaMethod convertToSsaMethod(RopMethod rmeth,
int paramWidth, boolean isStatic) {
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;
}
/**
* Returns an SSA represention with only the edge-splitter run.
* @param rmeth method to process
* @param paramWidth width of all arguments in the method
* @param isStatic true if this method has no 'this' pointer argument
* @return an SSA represention with only the edge-splitter run.
*/
public static SsaMethod testEdgeSplit (RopMethod rmeth, int paramWidth,
boolean isStatic) {
SsaMethod result;
result = SsaMethod.newFromRopMethod(rmeth, paramWidth, isStatic);
edgeSplit(result);
return result;
}
/**
* Returns an SSA represention with only the steps through the
* phi placement run.
* @param rmeth method to process
* @param paramWidth width of all arguments in the method
* @param isStatic true if this method has no 'this' pointer argument
* @return an SSA represention with only the edge-splitter run.
*/
public static SsaMethod testPhiPlacement (RopMethod rmeth, int paramWidth,
boolean isStatic) {
SsaMethod result;
result = SsaMethod.newFromRopMethod(rmeth, paramWidth, isStatic);
edgeSplit(result);
LocalVariableInfo localInfo = LocalVariableExtractor.extract(result);
placePhiFunctions(result, localInfo);
return result;
}
/**
* See Appel section 19.1
* Converts CFG into "edge-split" form, such that each node either a
* unique successor or unique predecessor.<p>
*
* 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.
*
* @param result method to process
*/
private static void edgeSplit(SsaMethod result) {
edgeSplitPredecessors(result);
edgeSplitMoveExceptionsAndResults(result);
edgeSplitSuccessors(result);
}
/**
* Inserts Z nodes as new predecessors for every node that has multiple
* successors and multiple predecessors.
* @param result non-null; method to process
*/
private static void edgeSplitPredecessors(SsaMethod result) {
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();
}
}
}
/**
* @param block non-null; block in question
* @return true if this node needs to have a unique predecessor created for
* it.
*/
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);
}
/**
* 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.
* @param ssaMeth method to process
*/
private static void edgeSplitMoveExceptionsAndResults(SsaMethod ssaMeth) {
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);
}
}
}
/**
* Inserts Z nodes for every node that needs a new
* successor.
* @param result non-null; method to process
*/
private static void edgeSplitSuccessors(SsaMethod result) {
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);
}
}
}
}
/**
* 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.
* @param block predecessor node
* @param succ successor node
* @return true if a Z node is needed
*/
private static boolean needsNewSuccessor(SsaBasicBlock block,
SsaBasicBlock succ) {
ArrayList<SsaInsn> insns = block.getInsns();
SsaInsn lastInsn = insns.get(insns.size() - 1);
return ((lastInsn.getResult() != null)
|| (lastInsn.getSources().size() > 0))
&& succ.getPredecessors().cardinality() > 1;
}
/**
* See Appel algorithm 19.6
* Place Phi functions in appropriate locations.
*
* @param ssaMeth non-null; method to process. Modifications made in-place
* @param localInfo non-null; Local variable info, used when placing phis
*/
private static void placePhiFunctions (SsaMethod ssaMeth,
LocalVariableInfo localInfo) {
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);
}
}
}
}
|
