Merge "Make usage of basic block marks more explicit"
diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
index dbc3e90..1e076dd 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
@@ -414,29 +414,22 @@
}
}
- public void mark() {
- assert color == 0;
- color = 1;
+ public void mark(int color) {
+ assert color != 0;
+ assert !isMarked(color);
+ this.color |= color;
+ assert isMarked(color);
}
- public void clearMark() {
- color = 0;
+ public void clearMark(int color) {
+ assert color != 0;
+ this.color &= ~color;
+ assert !isMarked(color);
}
- public boolean isMarked() {
- return color == 1;
- }
-
- public void setColor(int color) {
- this.color = color;
- }
-
- public int getColor() {
- return color;
- }
-
- public boolean hasColor(int color) {
- return this.color == color;
+ public boolean isMarked(int color) {
+ assert color != 0;
+ return (this.color & color) != 0;
}
public void incrementUnfilledPredecessorCount() {
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCode.java b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
index 9595f5c..4862d70 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCode.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
@@ -33,6 +33,7 @@
public LinkedList<BasicBlock> blocks;
public final ValueNumberGenerator valueNumberGenerator;
+ private int usedMarkingColors = 0;
private boolean numbered = false;
private int nextInstructionNumber = 0;
@@ -157,17 +158,17 @@
public void traceBlocks() {
// Get the blocks first, as calling topologicallySortedBlocks also sets marks.
ImmutableList<BasicBlock> sorted = topologicallySortedBlocks();
- clearMarks();
+ int color = reserveMarkingColor();
int nextBlockNumber = blocks.size();
LinkedList<BasicBlock> tracedBlocks = new LinkedList<>();
for (BasicBlock block : sorted) {
- if (!block.isMarked()) {
- block.mark();
+ if (!block.isMarked(color)) {
+ block.mark(color);
tracedBlocks.add(block);
BasicBlock current = block;
BasicBlock fallthrough = block.exit().fallthroughBlock();
- while (fallthrough != null && !fallthrough.isMarked()) {
- fallthrough.mark();
+ while (fallthrough != null && !fallthrough.isMarked(color)) {
+ fallthrough.mark(color);
tracedBlocks.add(fallthrough);
current = fallthrough;
fallthrough = fallthrough.exit().fallthroughBlock();
@@ -177,12 +178,14 @@
current.exit().setFallthroughBlock(newFallthrough);
newFallthrough.getPredecessors().add(current);
fallthrough.replacePredecessor(current, newFallthrough);
- newFallthrough.mark();
+ newFallthrough.mark(color);
tracedBlocks.add(newFallthrough);
}
}
}
blocks = tracedBlocks;
+ returnMarkingColor(color);
+ assert verifyNoColorsInUse();
}
private void ensureBlockNumbering() {
@@ -206,22 +209,32 @@
return builder.toString();
}
- public void clearMarks() {
+ public void clearMarks(int color) {
for (BasicBlock block : blocks) {
- block.clearMark();
+ block.clearMark(color);
}
}
- public void removeMarkedBlocks() {
+ public void removeMarkedBlocks(int color) {
ListIterator<BasicBlock> blockIterator = listIterator();
while (blockIterator.hasNext()) {
BasicBlock block = blockIterator.next();
- if (block.isMarked()) {
+ if (block.isMarked(color)) {
blockIterator.remove();
}
}
}
+ private boolean verifyNoBlocksMarked(int color) {
+ for (BasicBlock block : blocks) {
+ if (block.isMarked(color)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+
public void removeBlocks(List<BasicBlock> blocksToRemove) {
blocks.removeAll(blocksToRemove);
}
@@ -268,6 +281,7 @@
}
public boolean isConsistentGraph() {
+ assert verifyNoColorsInUse();
assert consistentBlockNumbering();
assert consistentPredecessorSuccessors();
assert consistentCatchHandlers();
@@ -588,4 +602,27 @@
}
}
}
+
+ public int reserveMarkingColor() {
+ int color = 1;
+ while ((usedMarkingColors & color) == color) {
+ assert color <= 0x40000000;
+ color <<= 1;
+ }
+ // TODO(sgjesse): Remove this assert if more colors will be required.
+ assert color == 1;
+ assert verifyNoBlocksMarked(color);
+ usedMarkingColors |= color;
+ return color;
+ }
+
+ public void returnMarkingColor(int color) {
+ assert (usedMarkingColors | color) == color;
+ clearMarks(color);
+ usedMarkingColors &= ~color;
+ }
+
+ public boolean verifyNoColorsInUse() {
+ return usedMarkingColors == 0;
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
index 8684c75..eeb843c 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
@@ -628,7 +628,7 @@
BasicBlock nextBlock;
// The marks will be used for cycle detection.
- code.clearMarks();
+ int color = code.reserveMarkingColor();
do {
nextBlock = iterator.hasNext() ? iterator.next() : null;
if (block.isTrivialGoto()) {
@@ -657,6 +657,7 @@
} while (block != null);
code.removeBlocks(blocksToRemove);
}
+ code.returnMarkingColor(color);
assert removedTrivialGotos(code);
assert code.isConsistentGraph();
}
@@ -1701,16 +1702,16 @@
public void simplifyIf(IRCode code) {
Supplier<DominatorTree> dominatorTreeMemoization = Suppliers
.memoize(() -> new DominatorTree(code));
- code.clearMarks();
+ int color = code.reserveMarkingColor();
for (BasicBlock block : code.blocks) {
- if (block.isMarked()) {
+ if (block.isMarked(color)) {
continue;
}
if (block.exit().isIf()) {
// First rewrite zero comparison.
rewriteIfWithConstZero(block);
- if (simplifyKnownBooleanCondition(code, dominatorTreeMemoization, block)) {
+ if (simplifyKnownBooleanCondition(code, dominatorTreeMemoization, block, color)) {
continue;
}
@@ -1756,10 +1757,11 @@
BasicBlock target = theIf.targetFromCondition(cond);
BasicBlock deadTarget =
target == theIf.getTrueTarget() ? theIf.fallthroughBlock() : theIf.getTrueTarget();
- rewriteIfToGoto(dominatorTreeMemoization, block, theIf, target, deadTarget);
+ rewriteIfToGoto(dominatorTreeMemoization, block, theIf, target, deadTarget, color);
}
}
- code.removeMarkedBlocks();
+ code.removeMarkedBlocks(color);
+ code.returnMarkingColor(color);
assert code.isConsistentSSA();
}
@@ -1795,7 +1797,7 @@
* by an xor instruction which is smaller.
*/
private boolean simplifyKnownBooleanCondition(IRCode code,
- Supplier<DominatorTree> dominatorTreeMemoization, BasicBlock block) {
+ Supplier<DominatorTree> dominatorTreeMemoization, BasicBlock block, int color) {
If theIf = block.exit().asIf();
Value testValue = theIf.inValues().get(0);
if (theIf.isZeroTest() && testValue.knownToBeBoolean()) {
@@ -1857,7 +1859,7 @@
// If all phis were removed, there is no need for the diamond shape anymore
// and it can be rewritten to a goto to one of the branches.
if (deadPhis == targetBlock.getPhis().size()) {
- rewriteIfToGoto(dominatorTreeMemoization, block, theIf, trueBlock, falseBlock);
+ rewriteIfToGoto(dominatorTreeMemoization, block, theIf, trueBlock, falseBlock, color);
return true;
}
}
@@ -1900,11 +1902,11 @@
}
private void rewriteIfToGoto(Supplier<DominatorTree> dominatorTreeMemoization, BasicBlock block,
- If theIf, BasicBlock target, BasicBlock deadTarget) {
+ If theIf, BasicBlock target, BasicBlock deadTarget, int color) {
List<BasicBlock> removedBlocks = block.unlink(deadTarget, dominatorTreeMemoization.get());
for (BasicBlock removedBlock : removedBlocks) {
- if (!removedBlock.isMarked()) {
- removedBlock.mark();
+ if (!removedBlock.isMarked(color)) {
+ removedBlock.mark(color);
}
}
assert theIf == block.exit();
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/DeadCodeRemover.java b/src/main/java/com/android/tools/r8/ir/optimize/DeadCodeRemover.java
index fc9a16b..88f9e63 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/DeadCodeRemover.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/DeadCodeRemover.java
@@ -25,47 +25,49 @@
Queue<BasicBlock> worklist = new LinkedList<>();
Supplier<DominatorTree> dominatorTreeMemoization = Suppliers
.memoize(() -> new DominatorTree(code));
- code.clearMarks();
+ int color = code.reserveMarkingColor();
worklist.addAll(code.blocks);
for (BasicBlock block = worklist.poll(); block != null; block = worklist.poll()) {
- if (block.isMarked()) {
+ if (block.isMarked(color)) {
// Ignore marked blocks, as they are scheduled for removal.
continue;
}
- removeDeadInstructions(worklist, code, block, options);
- removeDeadPhis(worklist, block, options);
- removeUnneededCatchHandlers(worklist, block, dominatorTreeMemoization);
+ removeDeadInstructions(worklist, code, block, options, color);
+ removeDeadPhis(worklist, block, options, color);
+ removeUnneededCatchHandlers(worklist, block, dominatorTreeMemoization, color);
}
- code.removeMarkedBlocks();
+ code.removeMarkedBlocks(color);
+ code.returnMarkingColor(color);
assert code.isConsistentSSA();
codeRewriter.rewriteMoveResult(code);
}
// Add the block from where the value originates to the worklist.
- private static void updateWorklist(Queue<BasicBlock> worklist, Value value) {
+ private static void updateWorklist(Queue<BasicBlock> worklist, Value value, int color) {
BasicBlock block;
if (value.isPhi()) {
block = value.asPhi().getBlock();
} else {
block = value.definition.getBlock();
}
- if (!block.isMarked()) {
+ if (!block.isMarked(color)) {
worklist.add(block);
}
}
// Add all blocks from where the in/debug-values to the instruction originates.
- private static void updateWorklist(Queue<BasicBlock> worklist, Instruction instruction) {
+ private static void updateWorklist(
+ Queue<BasicBlock> worklist, Instruction instruction, int color) {
for (Value inValue : instruction.inValues()) {
- updateWorklist(worklist, inValue);
+ updateWorklist(worklist, inValue, color);
}
for (Value debugValue : instruction.getDebugValues()) {
- updateWorklist(worklist, debugValue);
+ updateWorklist(worklist, debugValue, color);
}
}
private static void removeDeadPhis(Queue<BasicBlock> worklist, BasicBlock block,
- InternalOptions options) {
+ InternalOptions options, int color) {
Iterator<Phi> phiIt = block.getPhis().iterator();
while (phiIt.hasNext()) {
Phi phi = phiIt.next();
@@ -73,14 +75,15 @@
phiIt.remove();
for (Value operand : phi.getOperands()) {
operand.removePhiUser(phi);
- updateWorklist(worklist, operand);
+ updateWorklist(worklist, operand, color);
}
}
}
}
private static void removeDeadInstructions(
- Queue<BasicBlock> worklist, IRCode code, BasicBlock block, InternalOptions options) {
+ Queue<BasicBlock> worklist, IRCode code, BasicBlock block, InternalOptions options,
+ int color) {
InstructionListIterator iterator = block.listIterator(block.getInstructions().size());
while (iterator.hasPrevious()) {
Instruction current = iterator.previous();
@@ -101,7 +104,7 @@
continue;
}
- updateWorklist(worklist, current);
+ updateWorklist(worklist, current, color);
// All users will be removed for this instruction. Eagerly clear them so further inspection
// of this instruction during dead code elimination will terminate here.
outValue.clearUsers();
@@ -110,17 +113,17 @@
}
private static void removeUnneededCatchHandlers(Queue<BasicBlock> worklist, BasicBlock block,
- Supplier<DominatorTree> dominatorTreeMemoization) {
+ Supplier<DominatorTree> dominatorTreeMemoization, int color) {
if (block.hasCatchHandlers() && !block.canThrow()) {
CatchHandlers<BasicBlock> handlers = block.getCatchHandlers();
for (BasicBlock target : handlers.getUniqueTargets()) {
for (BasicBlock unlinked : block.unlink(target, dominatorTreeMemoization.get())) {
- if (!unlinked.isMarked()) {
+ if (!unlinked.isMarked(color)) {
Iterator<Instruction> iterator = unlinked.iterator();
while (iterator.hasNext()) {
- updateWorklist(worklist, iterator.next());
+ updateWorklist(worklist, iterator.next(), color);
}
- unlinked.mark();
+ unlinked.mark(color);
}
}
}
