dx/src/com/android/dx/ssa/SsaConverter.java - platform/dalvik - Git at Google

 /*
  * 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);
             }
         }
     }
 }
	/*
	* 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);
	}
	}
	}
	}