dx/src/com/android/dx/ssa/Dominators.java - platform/dalvik2 - 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 java.util.ArrayList;
 import java.util.BitSet;
 import java.util.HashSet;

 /**
  * This class computes dominator and post-dominator information using the
  * Lengauer-Tarjan method.
  *
  * See A Fast Algorithm for Finding Dominators in a Flowgraph
  * T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141.
  *
  * This implementation runs in time O(n log n).  The time bound
  * could be changed to O(n * ack(n)) with a small change to the link and eval,
  * and an addition of a child field to the DFS info. In reality, the constant
  * overheads are high enough that the current method is faster in all but the
  * strangest artificially constructed examples.
  *
  * The basic idea behind this algorithm is to perform a DFS walk, keeping track
  * of various info about parents.  We then use this info to calculate the
  * dominators, using union-find structures to link together the DFS info,
  * then finally evaluate the union-find results to get the dominators.
  * This implementation is m log n because it does not perform union by
  * rank to keep the union-find tree balanced.
  */
 public final class Dominators {
     /* postdom is true if we want post dominators */
     private final boolean postdom;

     /* {@code non-null;} method being processed */
     private final SsaMethod meth;

     /* Method's basic blocks. */
     private final ArrayList<SsaBasicBlock> blocks;

     /** indexed by basic block index */
     private final DFSInfo[] info;

     private final ArrayList<SsaBasicBlock> vertex;

     /** {@code non-null;} the raw dominator info */
     private final DomFront.DomInfo domInfos[];

     /**
      * Constructs an instance.
      *
      * @param meth {@code non-null;} method to process
      * @param domInfos {@code non-null;} the raw dominator info
      * @param postdom true for postdom information, false for normal dom info
      */
     private Dominators(SsaMethod meth, DomFront.DomInfo[] domInfos,
             boolean postdom) {
         this.meth = meth;
         this.domInfos = domInfos;
         this.postdom = postdom;
         this.blocks = meth.getBlocks();
         this.info = new DFSInfo[blocks.size() + 2];
         this.vertex = new ArrayList<SsaBasicBlock>();
     }

     /**
      * Constructs a fully-initialized instance. (This method exists so as
      * to avoid calling a large amount of code in the constructor.)
      *
      * @param meth {@code non-null;} method to process
      * @param domInfos {@code non-null;} the raw dominator info
      * @param postdom true for postdom information, false for normal dom info
      */
     public static Dominators make(SsaMethod meth, DomFront.DomInfo[] domInfos,
             boolean postdom) {
         Dominators result = new Dominators(meth, domInfos, postdom);

         result.run();
         return result;
     }

     private BitSet getSuccs(SsaBasicBlock block) {
         if (postdom) {
             return block.getPredecessors();
         } else {
             return block.getSuccessors();
         }
     }

     private BitSet getPreds(SsaBasicBlock block) {
         if (postdom) {
             return block.getSuccessors();
         } else {
             return block.getPredecessors();
         }
     }

     /**
      * Performs path compress on the DFS info.
      *
      * @param in Basic block whose DFS info we are path compressing.
      */
     private void compress(SsaBasicBlock in) {
         DFSInfo bbInfo = info[in.getIndex()];
         DFSInfo ancestorbbInfo = info[bbInfo.ancestor.getIndex()];

         if (ancestorbbInfo.ancestor != null) {
             ArrayList<SsaBasicBlock> worklist = new ArrayList<SsaBasicBlock>();
             HashSet<SsaBasicBlock> visited = new HashSet<SsaBasicBlock>();
             worklist.add(in);

             while (!worklist.isEmpty()) {
                 int wsize = worklist.size();
                 SsaBasicBlock v = worklist.get(wsize - 1);
                 DFSInfo vbbInfo = info[v.getIndex()];
                 SsaBasicBlock vAncestor = vbbInfo.ancestor;
                 DFSInfo vabbInfo = info[vAncestor.getIndex()];

                 // Make sure we process our ancestor before ourselves.
                 if (visited.add(vAncestor) && vabbInfo.ancestor != null) {
                     worklist.add(vAncestor);
                     continue;
                 }
                 worklist.remove(wsize - 1);

                 // Update based on ancestor info.
                 if (vabbInfo.ancestor == null) {
                     continue;
                 }
                 SsaBasicBlock vAncestorRep = vabbInfo.rep;
                 SsaBasicBlock vRep = vbbInfo.rep;
                 if (info[vAncestorRep.getIndex()].semidom
                         < info[vRep.getIndex()].semidom) {
                     vbbInfo.rep = vAncestorRep;
                 }
                 vbbInfo.ancestor = vabbInfo.ancestor;
             }
         }
     }

     private SsaBasicBlock eval(SsaBasicBlock v) {
         DFSInfo bbInfo = info[v.getIndex()];

         if (bbInfo.ancestor == null) {
             return v;
         }

         compress(v);
         return bbInfo.rep;
     }

     /**
      * Performs dominator/post-dominator calculation for the control
      * flow graph.
      *
      * @param meth {@code non-null;} method to analyze
      */
     private void run() {
         SsaBasicBlock root = postdom
                 ? meth.getExitBlock() : meth.getEntryBlock();

         if (root != null) {
             vertex.add(root);
             domInfos[root.getIndex()].idom = root.getIndex();
         }

         /*
          * First we perform a DFS numbering of the blocks, by
          * numbering the dfs tree roots.
          */

         DfsWalker walker = new DfsWalker();
         meth.forEachBlockDepthFirst(postdom, walker);

         // the largest semidom number assigned
         int dfsMax = vertex.size() - 1;

         // Now calculate semidominators.
         for (int i = dfsMax; i >= 2; --i) {
             SsaBasicBlock w = vertex.get(i);
             DFSInfo wInfo = info[w.getIndex()];

             BitSet preds = getPreds(w);
             for (int j = preds.nextSetBit(0);
                  j >= 0;
                  j = preds.nextSetBit(j + 1)) {
                 SsaBasicBlock predBlock = blocks.get(j);
                 DFSInfo predInfo = info[predBlock.getIndex()];

                 /*
                  * PredInfo may not exist in case the predecessor is
                  * not reachable.
                  */
                 if (predInfo != null) {
                     int predSemidom = info[eval(predBlock).getIndex()].semidom;
                     if (predSemidom < wInfo.semidom) {
                         wInfo.semidom = predSemidom;
                     }
                 }
             }
             info[vertex.get(wInfo.semidom).getIndex()].bucket.add(w);

             /*
              * Normally we would call link here, but in our O(m log n)
              * implementation this is equivalent to the following
              * single line.
              */
             wInfo.ancestor = wInfo.parent;

             // Implicity define idom for each vertex.
             ArrayList<SsaBasicBlock> wParentBucket;
             wParentBucket = info[wInfo.parent.getIndex()].bucket;

             while (!wParentBucket.isEmpty()) {
                 int lastItem = wParentBucket.size() - 1;
                 SsaBasicBlock last = wParentBucket.remove(lastItem);
                 SsaBasicBlock U = eval(last);
                 if (info[U.getIndex()].semidom
                         < info[last.getIndex()].semidom) {
                     domInfos[last.getIndex()].idom = U.getIndex();
                 } else {
                     domInfos[last.getIndex()].idom = wInfo.parent.getIndex();
                 }
             }
         }

         // Now explicitly define the immediate dominator of each vertex
         for (int i =  2; i <= dfsMax; ++i) {
             SsaBasicBlock w = vertex.get(i);
             if (domInfos[w.getIndex()].idom
                     != vertex.get(info[w.getIndex()].semidom).getIndex()) {
                 domInfos[w.getIndex()].idom
                         = domInfos[domInfos[w.getIndex()].idom].idom;
             }
         }
     }

     /**
      * Callback for depth-first walk through control flow graph (either
      * from the entry block or the exit block). Records the traversal order
      * in the {@code info}list.
      */
     private class DfsWalker implements SsaBasicBlock.Visitor {
         private int dfsNum = 0;

         public void visitBlock(SsaBasicBlock v, SsaBasicBlock parent) {
             DFSInfo bbInfo = new DFSInfo();
             bbInfo.semidom = ++dfsNum;
             bbInfo.rep = v;
             bbInfo.parent = parent;
             vertex.add(v);
             info[v.getIndex()] = bbInfo;
         }
     }

     private static final class DFSInfo {
         public int semidom;
         public SsaBasicBlock parent;

         /**
          * rep(resentative) is known as "label" in the paper. It is the node
          * that our block's DFS info has been unioned to.
          */
         public SsaBasicBlock rep;

         public SsaBasicBlock ancestor;
         public ArrayList<SsaBasicBlock> bucket;

         public DFSInfo() {
             bucket = new ArrayList<SsaBasicBlock>();
         }
     }
 }
	/*
	* 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 java.util.ArrayList;
	import java.util.BitSet;
	import java.util.HashSet;

	/**
	* This class computes dominator and post-dominator information using the
	* Lengauer-Tarjan method.
	*
	* See A Fast Algorithm for Finding Dominators in a Flowgraph
	* T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141.
	*
	* This implementation runs in time O(n log n). The time bound
	* could be changed to O(n * ack(n)) with a small change to the link and eval,
	* and an addition of a child field to the DFS info. In reality, the constant
	* overheads are high enough that the current method is faster in all but the
	* strangest artificially constructed examples.
	*
	* The basic idea behind this algorithm is to perform a DFS walk, keeping track
	* of various info about parents. We then use this info to calculate the
	* dominators, using union-find structures to link together the DFS info,
	* then finally evaluate the union-find results to get the dominators.
	* This implementation is m log n because it does not perform union by
	* rank to keep the union-find tree balanced.
	*/
	public final class Dominators {
	/* postdom is true if we want post dominators */
	private final boolean postdom;

	/* {@code non-null;} method being processed */
	private final SsaMethod meth;

	/* Method's basic blocks. */
	private final ArrayList<SsaBasicBlock> blocks;

	/** indexed by basic block index */
	private final DFSInfo[] info;

	private final ArrayList<SsaBasicBlock> vertex;

	/** {@code non-null;} the raw dominator info */
	private final DomFront.DomInfo domInfos[];

	/**
	* Constructs an instance.
	*
	* @param meth {@code non-null;} method to process
	* @param domInfos {@code non-null;} the raw dominator info
	* @param postdom true for postdom information, false for normal dom info
	*/
	private Dominators(SsaMethod meth, DomFront.DomInfo[] domInfos,
	boolean postdom) {
	this.meth = meth;
	this.domInfos = domInfos;
	this.postdom = postdom;
	this.blocks = meth.getBlocks();
	this.info = new DFSInfo[blocks.size() + 2];
	this.vertex = new ArrayList<SsaBasicBlock>();
	}

	/**
	* Constructs a fully-initialized instance. (This method exists so as
	* to avoid calling a large amount of code in the constructor.)
	*
	* @param meth {@code non-null;} method to process
	* @param domInfos {@code non-null;} the raw dominator info
	* @param postdom true for postdom information, false for normal dom info
	*/
	public static Dominators make(SsaMethod meth, DomFront.DomInfo[] domInfos,
	boolean postdom) {
	Dominators result = new Dominators(meth, domInfos, postdom);

	result.run();
	return result;
	}

	private BitSet getSuccs(SsaBasicBlock block) {
	if (postdom) {
	return block.getPredecessors();
	} else {
	return block.getSuccessors();
	}
	}

	private BitSet getPreds(SsaBasicBlock block) {
	if (postdom) {
	return block.getSuccessors();
	} else {
	return block.getPredecessors();
	}
	}

	/**
	* Performs path compress on the DFS info.
	*
	* @param in Basic block whose DFS info we are path compressing.
	*/
	private void compress(SsaBasicBlock in) {
	DFSInfo bbInfo = info[in.getIndex()];
	DFSInfo ancestorbbInfo = info[bbInfo.ancestor.getIndex()];

	if (ancestorbbInfo.ancestor != null) {
	ArrayList<SsaBasicBlock> worklist = new ArrayList<SsaBasicBlock>();
	HashSet<SsaBasicBlock> visited = new HashSet<SsaBasicBlock>();
	worklist.add(in);

	while (!worklist.isEmpty()) {
	int wsize = worklist.size();
	SsaBasicBlock v = worklist.get(wsize - 1);
	DFSInfo vbbInfo = info[v.getIndex()];
	SsaBasicBlock vAncestor = vbbInfo.ancestor;
	DFSInfo vabbInfo = info[vAncestor.getIndex()];

	// Make sure we process our ancestor before ourselves.
	if (visited.add(vAncestor) && vabbInfo.ancestor != null) {
	worklist.add(vAncestor);
	continue;
	}
	worklist.remove(wsize - 1);

	// Update based on ancestor info.
	if (vabbInfo.ancestor == null) {
	continue;
	}
	SsaBasicBlock vAncestorRep = vabbInfo.rep;
	SsaBasicBlock vRep = vbbInfo.rep;
	if (info[vAncestorRep.getIndex()].semidom
	< info[vRep.getIndex()].semidom) {
	vbbInfo.rep = vAncestorRep;
	}
	vbbInfo.ancestor = vabbInfo.ancestor;
	}
	}
	}

	private SsaBasicBlock eval(SsaBasicBlock v) {
	DFSInfo bbInfo = info[v.getIndex()];

	if (bbInfo.ancestor == null) {
	return v;
	}

	compress(v);
	return bbInfo.rep;
	}

	/**
	* Performs dominator/post-dominator calculation for the control
	* flow graph.
	*
	* @param meth {@code non-null;} method to analyze
	*/
	private void run() {
	SsaBasicBlock root = postdom
	? meth.getExitBlock() : meth.getEntryBlock();

	if (root != null) {
	vertex.add(root);
	domInfos[root.getIndex()].idom = root.getIndex();
	}

	/*
	* First we perform a DFS numbering of the blocks, by
	* numbering the dfs tree roots.
	*/

	DfsWalker walker = new DfsWalker();
	meth.forEachBlockDepthFirst(postdom, walker);

	// the largest semidom number assigned
	int dfsMax = vertex.size() - 1;

	// Now calculate semidominators.
	for (int i = dfsMax; i >= 2; --i) {
	SsaBasicBlock w = vertex.get(i);
	DFSInfo wInfo = info[w.getIndex()];

	BitSet preds = getPreds(w);
	for (int j = preds.nextSetBit(0);
	j >= 0;
	j = preds.nextSetBit(j + 1)) {
	SsaBasicBlock predBlock = blocks.get(j);
	DFSInfo predInfo = info[predBlock.getIndex()];

	/*
	* PredInfo may not exist in case the predecessor is
	* not reachable.
	*/
	if (predInfo != null) {
	int predSemidom = info[eval(predBlock).getIndex()].semidom;
	if (predSemidom < wInfo.semidom) {
	wInfo.semidom = predSemidom;
	}
	}
	}
	info[vertex.get(wInfo.semidom).getIndex()].bucket.add(w);

	/*
	* Normally we would call link here, but in our O(m log n)
	* implementation this is equivalent to the following
	* single line.
	*/
	wInfo.ancestor = wInfo.parent;

	// Implicity define idom for each vertex.
	ArrayList<SsaBasicBlock> wParentBucket;
	wParentBucket = info[wInfo.parent.getIndex()].bucket;

	while (!wParentBucket.isEmpty()) {
	int lastItem = wParentBucket.size() - 1;
	SsaBasicBlock last = wParentBucket.remove(lastItem);
	SsaBasicBlock U = eval(last);
	if (info[U.getIndex()].semidom
	< info[last.getIndex()].semidom) {
	domInfos[last.getIndex()].idom = U.getIndex();
	} else {
	domInfos[last.getIndex()].idom = wInfo.parent.getIndex();
	}
	}
	}

	// Now explicitly define the immediate dominator of each vertex
	for (int i = 2; i <= dfsMax; ++i) {
	SsaBasicBlock w = vertex.get(i);
	if (domInfos[w.getIndex()].idom
	!= vertex.get(info[w.getIndex()].semidom).getIndex()) {
	domInfos[w.getIndex()].idom
	= domInfos[domInfos[w.getIndex()].idom].idom;
	}
	}
	}

	/**
	* Callback for depth-first walk through control flow graph (either
	* from the entry block or the exit block). Records the traversal order
	* in the {@code info}list.
	*/
	private class DfsWalker implements SsaBasicBlock.Visitor {
	private int dfsNum = 0;

	public void visitBlock(SsaBasicBlock v, SsaBasicBlock parent) {
	DFSInfo bbInfo = new DFSInfo();
	bbInfo.semidom = ++dfsNum;
	bbInfo.rep = v;
	bbInfo.parent = parent;
	vertex.add(v);
	info[v.getIndex()] = bbInfo;
	}
	}

	private static final class DFSInfo {
	public int semidom;
	public SsaBasicBlock parent;

	/**
	* rep(resentative) is known as "label" in the paper. It is the node
	* that our block's DFS info has been unioned to.
	*/
	public SsaBasicBlock rep;

	public SsaBasicBlock ancestor;
	public ArrayList<SsaBasicBlock> bucket;

	public DFSInfo() {
	bucket = new ArrayList<SsaBasicBlock>();
	}
	}
	}