src/main/java/com/android/tools/r8/ir/code/DominatorTree.java - r8 - Git at Google

 // Copyright (c) 2016, the R8 project authors. Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.

 package com.android.tools.r8.ir.code;

 import static com.android.tools.r8.ir.code.DominatorTree.Assumption.MAY_HAVE_UNREACHABLE_BLOCKS;

 import com.android.tools.r8.ir.code.BasicBlock.BasicBlockChangeListener;
 import com.google.common.collect.ImmutableList;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Iterator;
 import java.util.List;

 public class DominatorTree implements BasicBlockChangeListener {

   public enum Assumption {
     NO_UNREACHABLE_BLOCKS,
     MAY_HAVE_UNREACHABLE_BLOCKS
   }

   public enum Inclusive {
     YES,
     NO
   }

   private final BasicBlock[] sorted;
   private BasicBlock[] doms;
   private final BasicBlock normalExitBlock = new BasicBlock();

   private final int unreachableStartIndex;

   private boolean obsolete = false;

   public DominatorTree(IRCode code) {
     this(code, Assumption.NO_UNREACHABLE_BLOCKS);
   }

   public DominatorTree(IRCode code, Assumption assumption) {
     assert assumption != null;
     assert assumption == MAY_HAVE_UNREACHABLE_BLOCKS || code.getUnreachableBlocks().isEmpty();

     ImmutableList<BasicBlock> blocks = code.topologicallySortedBlocks();
     // Add the internal exit block to the block list.
     for (BasicBlock block : blocks) {
       if (block.exit().isReturn()) {
         normalExitBlock.getMutablePredecessors().add(block);
       }
     }
     int numberOfBlocks = code.blocks.size();
     if (assumption == MAY_HAVE_UNREACHABLE_BLOCKS) {
       // Unreachable blocks have been removed implicitly by the topological sort.
       sorted = new BasicBlock[numberOfBlocks + 1];
       // Move topologically sorted blocks into `sorted`.
       int color = code.reserveMarkingColor();
       int i = 0;
       for (BasicBlock block : blocks) {
         sorted[i] = block;
         block.mark(color);
         i++;
       }
       sorted[i] = normalExitBlock;
       i++;
       // Move unreachable blocks into the end of `sorted`.
       unreachableStartIndex = i;
       for (BasicBlock block : code.blocks) {
         if (!block.isMarked(color)) {
           sorted[i] = block;
           i++;
         }
       }
       code.returnMarkingColor(color);
     } else {
       sorted = blocks.toArray(new BasicBlock[numberOfBlocks + 1]);
       sorted[numberOfBlocks] = normalExitBlock;
       unreachableStartIndex = numberOfBlocks + 1;
     }
     numberBlocks();
     build();

     // This is intentionally implemented via an `assert` so that we do not attach listeners to all
     // basic blocks when running without assertions.
     assert recordChangesToControlFlowEdges(code.blocks);
   }

   /**
    * Get the immediate dominator block for a block.
    */
   public BasicBlock immediateDominator(BasicBlock block) {
     assert !obsolete;
     return doms[block.getNumber()];
   }

   /**
    * Check if one basic block is dominated by another basic block.
    *
    * @param subject subject to check for domination by {@param dominator}
    * @param dominator dominator to check against
    * @return whether {@param subject} is dominated by {@param dominator}
    */
   public boolean dominatedBy(BasicBlock subject, BasicBlock dominator) {
     assert !obsolete;
     if (subject == dominator) {
       return true;
     }
     return strictlyDominatedBy(subject, dominator);
   }

   /**
    * Checks if one basic block dominates a collection of other basic blocks.
    *
    * @param dominator dominator to check against
    * @param subjects subjects to check for domination by {@param dominator}
    * @return whether {@param subjects} are all dominated by {@param dominator}
    */
   public boolean dominatesAllOf(BasicBlock dominator, Iterable<BasicBlock> subjects) {
     for (BasicBlock subject : subjects) {
       if (!dominatedBy(subject, dominator)) {
         return false;
       }
     }
     return true;
   }

   /**
    * Check if one basic block is strictly dominated by another basic block.
    *
    * @param subject subject to check for domination by {@param dominator}
    * @param dominator dominator to check against
    * @return whether {@param subject} is strictly dominated by {@param dominator}
    */
   public boolean strictlyDominatedBy(BasicBlock subject, BasicBlock dominator) {
     assert !obsolete;
     if (subject.getNumber() == 0 || subject == normalExitBlock) {
       return false;
     }
     while (true) {
       BasicBlock idom = immediateDominator(subject);
       if (idom.getNumber() < dominator.getNumber()) {
         return false;
       }
       if (idom == dominator) {
         return true;
       }
       subject = idom;
     }
   }

   /**
    * Use the dominator tree to find the dominating block that is closest to a set of blocks.
    *
    * @param blocks the block for which to find a dominator
    * @return the closest dominator for the collection of blocks
    */
   public BasicBlock closestDominator(Collection<BasicBlock> blocks) {
     assert !obsolete;
     if (blocks.size() == 0) {
       return null;
     }
     Iterator<BasicBlock> it = blocks.iterator();
     BasicBlock dominator = it.next();
     while (it.hasNext()) {
       dominator = intersect(dominator, it.next());
     }
     return dominator;
   }

   /** Returns the blocks dominated by dominator, including dominator itself. */
   public List<BasicBlock> dominatedBlocks(BasicBlock dominator) {
     return dominatedBlocks(dominator, new ArrayList<>());
   }

   public <T extends Collection<BasicBlock>> T dominatedBlocks(
       BasicBlock dominator, T dominatedBlocks) {
     assert !obsolete;
     for (int i = dominator.getNumber(); i < unreachableStartIndex; ++i) {
       BasicBlock block = sorted[i];
       if (dominatedBy(block, dominator)) {
         dominatedBlocks.add(block);
       }
     }
     return dominatedBlocks;
   }

   /**
    * Returns an iterator over all dominator blocks of <code>dominated</code>.
    *
    * Iteration order is always the immediate dominator of the previously returned block. The
    * iteration starts by returning <code>dominated</code>.
    */
   public Iterable<BasicBlock> dominatorBlocks(BasicBlock dominated, Inclusive inclusive) {
     assert !obsolete;
     return () -> {
       Iterator<BasicBlock> iterator =
           new Iterator<BasicBlock>() {
             private BasicBlock current = dominated;

             @Override
             public boolean hasNext() {
               return current != null;
             }

             @Override
             public BasicBlock next() {
               if (!hasNext()) {
                 return null;
               } else {
                 BasicBlock result = current;
                 if (current.getNumber() == 0) {
                   current = null;
                 } else {
                   current = immediateDominator(current);
                   assert current != result;
                 }
                 return result;
               }
             }
           };
       if (inclusive == Inclusive.NO) {
         BasicBlock block = iterator.next();
         assert block == dominated;
       }
       return iterator;
     };
   }

   public Iterable<BasicBlock> normalExitDominatorBlocks() {
     assert !obsolete;
     // Do not include the `normalExitBlock`, since this is a synthetic block created here in the
     // DominatorTree.
     return dominatorBlocks(normalExitBlock, Inclusive.NO);
   }

   public BasicBlock[] getSortedBlocks() {
     return sorted;
   }

   private void numberBlocks() {
     for (int i = 0; i < sorted.length; i++) {
       sorted[i].setNumber(i);
     }
   }

   private boolean postorderCompareLess(BasicBlock b1, BasicBlock b2) {
     // The topological sort is reverse postorder.
     return b1.getNumber() > b2.getNumber();
   }

   // Build dominator tree based on the algorithm described in this paper:
   //
   // A Simple, Fast Dominance Algorithm
   // Cooper, Keith D.; Harvey, Timothy J.; and Kennedy, Ken (2001).
   // http://www.cs.rice.edu/~keith/EMBED/dom.pdf
   private void build() {
     doms = new BasicBlock[sorted.length];
     doms[0] = sorted[0];
     boolean changed = true;
     while (changed) {
       changed = false;
       // Run through all nodes in reverse postorder (except start node).
       for (int i = 1; i < sorted.length; i++) {
         BasicBlock b = sorted[i];
         // Pick one processed predecessor.
         BasicBlock newIDom = null;
         int picked = -1;
         for (int j = 0; newIDom == null && j < b.getPredecessors().size(); j++) {
           BasicBlock p = b.getPredecessors().get(j);
           if (doms[p.getNumber()] != null) {
             picked = j;
             newIDom = p;
           }
         }
         // Run through all other predecessors.
         for (int j = 0; j < b.getPredecessors().size(); j++) {
           BasicBlock p = b.getPredecessors().get(j);
           if (j == picked) {
             continue;
           }
           if (doms[p.getNumber()] != null) {
             newIDom = intersect(p, newIDom);
           }
         }
         if (doms[b.getNumber()] != newIDom) {
           doms[b.getNumber()] = newIDom;
           changed = true;
         }
       }
     }
   }

   private BasicBlock intersect(BasicBlock b1, BasicBlock b2) {
     BasicBlock finger1 = b1;
     BasicBlock finger2 = b2;
     while (finger1 != finger2) {
       while (postorderCompareLess(finger1, finger2)) {
         finger1 = doms[finger1.getNumber()];
       }
       while (postorderCompareLess(finger2, finger1)) {
         finger2 = doms[finger2.getNumber()];
       }
     }
     return finger1;
   }

   @Override
   public String toString() {
     StringBuilder builder = new StringBuilder();
     builder.append("Dominators\n");
     for (BasicBlock block : sorted) {
       builder.append(block.getNumber());
       builder.append(": ");
       builder.append(doms[block.getNumber()].getNumber());
       builder.append("\n");
     }
     return builder.toString();
   }

   private boolean recordChangesToControlFlowEdges(List<BasicBlock> blocks) {
     for (BasicBlock block : blocks) {
       block.addControlFlowEdgesMayChangeListener(this);
     }
     return true;
   }

   @Override
   public void onSuccessorsMayChange(BasicBlock block) {
     obsolete = true;
   }

   @Override
   public void onPredecessorsMayChange(BasicBlock block) {
     obsolete = true;
   }
 }
	// Copyright (c) 2016, the R8 project authors. Please see the AUTHORS file
	// for details. All rights reserved. Use of this source code is governed by a
	// BSD-style license that can be found in the LICENSE file.

	package com.android.tools.r8.ir.code;

	import static com.android.tools.r8.ir.code.DominatorTree.Assumption.MAY_HAVE_UNREACHABLE_BLOCKS;

	import com.android.tools.r8.ir.code.BasicBlock.BasicBlockChangeListener;
	import com.google.common.collect.ImmutableList;
	import java.util.ArrayList;
	import java.util.Collection;
	import java.util.Iterator;
	import java.util.List;

	public class DominatorTree implements BasicBlockChangeListener {

	public enum Assumption {
	NO_UNREACHABLE_BLOCKS,
	MAY_HAVE_UNREACHABLE_BLOCKS
	}

	public enum Inclusive {
	YES,
	NO
	}

	private final BasicBlock[] sorted;
	private BasicBlock[] doms;
	private final BasicBlock normalExitBlock = new BasicBlock();

	private final int unreachableStartIndex;

	private boolean obsolete = false;

	public DominatorTree(IRCode code) {
	this(code, Assumption.NO_UNREACHABLE_BLOCKS);
	}

	public DominatorTree(IRCode code, Assumption assumption) {
	assert assumption != null;
	assert assumption == MAY_HAVE_UNREACHABLE_BLOCKS \|\| code.getUnreachableBlocks().isEmpty();

	ImmutableList<BasicBlock> blocks = code.topologicallySortedBlocks();
	// Add the internal exit block to the block list.
	for (BasicBlock block : blocks) {
	if (block.exit().isReturn()) {
	normalExitBlock.getMutablePredecessors().add(block);
	}
	}
	int numberOfBlocks = code.blocks.size();
	if (assumption == MAY_HAVE_UNREACHABLE_BLOCKS) {
	// Unreachable blocks have been removed implicitly by the topological sort.
	sorted = new BasicBlock[numberOfBlocks + 1];
	// Move topologically sorted blocks into `sorted`.
	int color = code.reserveMarkingColor();
	int i = 0;
	for (BasicBlock block : blocks) {
	sorted[i] = block;
	block.mark(color);
	i++;
	}
	sorted[i] = normalExitBlock;
	i++;
	// Move unreachable blocks into the end of `sorted`.
	unreachableStartIndex = i;
	for (BasicBlock block : code.blocks) {
	if (!block.isMarked(color)) {
	sorted[i] = block;
	i++;
	}
	}
	code.returnMarkingColor(color);
	} else {
	sorted = blocks.toArray(new BasicBlock[numberOfBlocks + 1]);
	sorted[numberOfBlocks] = normalExitBlock;
	unreachableStartIndex = numberOfBlocks + 1;
	}
	numberBlocks();
	build();

	// This is intentionally implemented via an `assert` so that we do not attach listeners to all
	// basic blocks when running without assertions.
	assert recordChangesToControlFlowEdges(code.blocks);
	}

	/**
	* Get the immediate dominator block for a block.
	*/
	public BasicBlock immediateDominator(BasicBlock block) {
	assert !obsolete;
	return doms[block.getNumber()];
	}

	/**
	* Check if one basic block is dominated by another basic block.
	*
	* @param subject subject to check for domination by {@param dominator}
	* @param dominator dominator to check against
	* @return whether {@param subject} is dominated by {@param dominator}
	*/
	public boolean dominatedBy(BasicBlock subject, BasicBlock dominator) {
	assert !obsolete;
	if (subject == dominator) {
	return true;
	}
	return strictlyDominatedBy(subject, dominator);
	}

	/**
	* Checks if one basic block dominates a collection of other basic blocks.
	*
	* @param dominator dominator to check against
	* @param subjects subjects to check for domination by {@param dominator}
	* @return whether {@param subjects} are all dominated by {@param dominator}
	*/
	public boolean dominatesAllOf(BasicBlock dominator, Iterable<BasicBlock> subjects) {
	for (BasicBlock subject : subjects) {
	if (!dominatedBy(subject, dominator)) {
	return false;
	}
	}
	return true;
	}

	/**
	* Check if one basic block is strictly dominated by another basic block.
	*
	* @param subject subject to check for domination by {@param dominator}
	* @param dominator dominator to check against
	* @return whether {@param subject} is strictly dominated by {@param dominator}
	*/
	public boolean strictlyDominatedBy(BasicBlock subject, BasicBlock dominator) {
	assert !obsolete;
	if (subject.getNumber() == 0 \|\| subject == normalExitBlock) {
	return false;
	}
	while (true) {
	BasicBlock idom = immediateDominator(subject);
	if (idom.getNumber() < dominator.getNumber()) {
	return false;
	}
	if (idom == dominator) {
	return true;
	}
	subject = idom;
	}
	}

	/**
	* Use the dominator tree to find the dominating block that is closest to a set of blocks.
	*
	* @param blocks the block for which to find a dominator
	* @return the closest dominator for the collection of blocks
	*/
	public BasicBlock closestDominator(Collection<BasicBlock> blocks) {
	assert !obsolete;
	if (blocks.size() == 0) {
	return null;
	}
	Iterator<BasicBlock> it = blocks.iterator();
	BasicBlock dominator = it.next();
	while (it.hasNext()) {
	dominator = intersect(dominator, it.next());
	}
	return dominator;
	}

	/** Returns the blocks dominated by dominator, including dominator itself. */
	public List<BasicBlock> dominatedBlocks(BasicBlock dominator) {
	return dominatedBlocks(dominator, new ArrayList<>());
	}

	public <T extends Collection<BasicBlock>> T dominatedBlocks(
	BasicBlock dominator, T dominatedBlocks) {
	assert !obsolete;
	for (int i = dominator.getNumber(); i < unreachableStartIndex; ++i) {
	BasicBlock block = sorted[i];
	if (dominatedBy(block, dominator)) {
	dominatedBlocks.add(block);
	}
	}
	return dominatedBlocks;
	}

	/**
	* Returns an iterator over all dominator blocks of <code>dominated</code>.
	*
	* Iteration order is always the immediate dominator of the previously returned block. The
	* iteration starts by returning <code>dominated</code>.
	*/
	public Iterable<BasicBlock> dominatorBlocks(BasicBlock dominated, Inclusive inclusive) {
	assert !obsolete;
	return () -> {
	Iterator<BasicBlock> iterator =
	new Iterator<BasicBlock>() {
	private BasicBlock current = dominated;

	@Override
	public boolean hasNext() {
	return current != null;
	}

	@Override
	public BasicBlock next() {
	if (!hasNext()) {
	return null;
	} else {
	BasicBlock result = current;
	if (current.getNumber() == 0) {
	current = null;
	} else {
	current = immediateDominator(current);
	assert current != result;
	}
	return result;
	}
	}
	};
	if (inclusive == Inclusive.NO) {
	BasicBlock block = iterator.next();
	assert block == dominated;
	}
	return iterator;
	};
	}

	public Iterable<BasicBlock> normalExitDominatorBlocks() {
	assert !obsolete;
	// Do not include the `normalExitBlock`, since this is a synthetic block created here in the
	// DominatorTree.
	return dominatorBlocks(normalExitBlock, Inclusive.NO);
	}

	public BasicBlock[] getSortedBlocks() {
	return sorted;
	}

	private void numberBlocks() {
	for (int i = 0; i < sorted.length; i++) {
	sorted[i].setNumber(i);
	}
	}

	private boolean postorderCompareLess(BasicBlock b1, BasicBlock b2) {
	// The topological sort is reverse postorder.
	return b1.getNumber() > b2.getNumber();
	}

	// Build dominator tree based on the algorithm described in this paper:
	//
	// A Simple, Fast Dominance Algorithm
	// Cooper, Keith D.; Harvey, Timothy J.; and Kennedy, Ken (2001).
	// http://www.cs.rice.edu/~keith/EMBED/dom.pdf
	private void build() {
	doms = new BasicBlock[sorted.length];
	doms[0] = sorted[0];
	boolean changed = true;
	while (changed) {
	changed = false;
	// Run through all nodes in reverse postorder (except start node).
	for (int i = 1; i < sorted.length; i++) {
	BasicBlock b = sorted[i];
	// Pick one processed predecessor.
	BasicBlock newIDom = null;
	int picked = -1;
	for (int j = 0; newIDom == null && j < b.getPredecessors().size(); j++) {
	BasicBlock p = b.getPredecessors().get(j);
	if (doms[p.getNumber()] != null) {
	picked = j;
	newIDom = p;
	}
	}
	// Run through all other predecessors.
	for (int j = 0; j < b.getPredecessors().size(); j++) {
	BasicBlock p = b.getPredecessors().get(j);
	if (j == picked) {
	continue;
	}
	if (doms[p.getNumber()] != null) {
	newIDom = intersect(p, newIDom);
	}
	}
	if (doms[b.getNumber()] != newIDom) {
	doms[b.getNumber()] = newIDom;
	changed = true;
	}
	}
	}
	}

	private BasicBlock intersect(BasicBlock b1, BasicBlock b2) {
	BasicBlock finger1 = b1;
	BasicBlock finger2 = b2;
	while (finger1 != finger2) {
	while (postorderCompareLess(finger1, finger2)) {
	finger1 = doms[finger1.getNumber()];
	}
	while (postorderCompareLess(finger2, finger1)) {
	finger2 = doms[finger2.getNumber()];
	}
	}
	return finger1;
	}

	@Override
	public String toString() {
	StringBuilder builder = new StringBuilder();
	builder.append("Dominators\n");
	for (BasicBlock block : sorted) {
	builder.append(block.getNumber());
	builder.append(": ");
	builder.append(doms[block.getNumber()].getNumber());
	builder.append("\n");
	}
	return builder.toString();
	}

	private boolean recordChangesToControlFlowEdges(List<BasicBlock> blocks) {
	for (BasicBlock block : blocks) {
	block.addControlFlowEdgesMayChangeListener(this);
	}
	return true;
	}

	@Override
	public void onSuccessorsMayChange(BasicBlock block) {
	obsolete = true;
	}

	@Override
	public void onPredecessorsMayChange(BasicBlock block) {
	obsolete = true;
	}
	}