content: /*
   * 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.taobao.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>();
          }
      }
  }
  