Use an intrusive linked list for BasicBlock instructions
* Encapsulates all Instruction.setBlock() and IRMetadata.record()
calls within InstructionList so they cannot be missed.
* Updates passes that added the same instruction (temporarily) to two
different blocks (or to the same block twice).
* Instructions can now belong to only one list, so must be removed
before added again.
* Switches a handful of iterator uses to for loops (get a feel for
the style)
* I think many spots would benefit from using this style over
iterators, as it means you do not need worry about invalidating
iterators, or rewinding them.
* Changes semantics of Block.listIterator(Instruction) to match
Block.listIterator(index)
* E.g. The given instruction will be the first to be returned by
a call to next().
* Moves some instruction mutating helper logic from
BasicBlockInstructionListIterator to InstructionList & Instruction,
so that they can be used without an iterator.
* Likely makes sense to do more of this going forward, or to capture
these helpers in an InstructionUtil class.
* Leaves in some TODOs for trivial follow-up refactors in order to
not make this even larger of a change than it is.
Bug: b/376663044
Change-Id: I11005b74efbbda9fe2b463a5f848c0f486868d59diff --git a/src/main/java/com/android/tools/r8/cf/CfRegisterAllocator.java b/src/main/java/com/android/tools/r8/cf/CfRegisterAllocator.java
index 418fcea..a23ee09 100644
--- a/src/main/java/com/android/tools/r8/cf/CfRegisterAllocator.java
+++ b/src/main/java/com/android/tools/r8/cf/CfRegisterAllocator.java
@@ -521,10 +521,11 @@
private void applyInstructionsBackwardsToRegisterLiveness(
BasicBlock block, IntSet liveRegisters, int suffixSize) {
- InstructionIterator iterator = block.iterator(block.getInstructions().size());
- int instructionsLeft = suffixSize;
- while (--instructionsLeft >= 0 && iterator.hasPrevious()) {
- Instruction current = iterator.previous();
+ int i = 0;
+ for (var current = block.getLastInstruction(); current != null; current = current.getPrev()) {
+ if (++i > suffixSize) {
+ break;
+ }
Value outValue = current.outValue();
if (outValue != null && outValue.needsRegister()) {
int register = getRegisterForValue(outValue);
diff --git a/src/main/java/com/android/tools/r8/cf/LoadStoreHelper.java b/src/main/java/com/android/tools/r8/cf/LoadStoreHelper.java
index 9139e16..a92f931 100644
--- a/src/main/java/com/android/tools/r8/cf/LoadStoreHelper.java
+++ b/src/main/java/com/android/tools/r8/cf/LoadStoreHelper.java
@@ -213,7 +213,7 @@
storeBlock = it.split(this.code, this.blockIterator);
it = storeBlock.listIterator(code);
}
- add(store, storeBlock, instruction.getPosition(), it);
+ add(store, instruction.getPosition(), it);
if (hasCatchHandlers && !instruction.instructionTypeCanThrow()) {
splitAfterStoredOutValue(it);
}
@@ -242,7 +242,7 @@
it = insertBlock.listIterator(code);
}
instruction.swapOutValue(newOutValue);
- add(new Pop(newOutValue), insertBlock, instruction.getPosition(), it);
+ add(new Pop(newOutValue), instruction.getPosition(), it);
}
private static class PhiMove {
@@ -261,7 +261,7 @@
List<StackValue> temps = new ArrayList<>(moves.size());
for (PhiMove move : moves) {
StackValue tmp = createStackValue(move.phi, topOfStack++);
- add(load(tmp, move.operand), move.phi.getBlock(), position, it);
+ add(load(tmp, move.operand), position, it);
temps.add(tmp);
move.operand.removePhiUser(move.phi);
}
@@ -269,7 +269,7 @@
PhiMove move = moves.get(i);
StackValue tmp = temps.get(i);
FixedLocalValue out = new FixedLocalValue(move.phi);
- add(new Store(out, tmp), move.phi.getBlock(), position, it);
+ add(new Store(out, tmp), position, it);
move.phi.replaceUsers(out);
}
}
@@ -296,12 +296,11 @@
private static void add(
Instruction newInstruction, Instruction existingInstruction, InstructionListIterator it) {
- add(newInstruction, existingInstruction.getBlock(), existingInstruction.getPosition(), it);
+ add(newInstruction, existingInstruction.getPosition(), it);
}
private static void add(
- Instruction newInstruction, BasicBlock block, Position position, InstructionListIterator it) {
- newInstruction.setBlock(block);
+ Instruction newInstruction, Position position, InstructionListIterator it) {
newInstruction.setPosition(position);
it.add(newInstruction);
}
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/code/ClassInitializerMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/code/ClassInitializerMerger.java
index adf8f89..ccffd96 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/code/ClassInitializerMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/code/ClassInitializerMerger.java
@@ -149,7 +149,7 @@
NumberGenerator blockNumberGenerator = new NumberGenerator();
NumberGenerator valueNumberGenerator = new NumberGenerator();
- BasicBlock block = new BasicBlock();
+ BasicBlock block = new BasicBlock(metadata);
block.setNumber(blockNumberGenerator.next());
// Add "invoke-static <clinit>" for each of the class initializers to the exit block.
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/escape/EscapeAnalysis.java b/src/main/java/com/android/tools/r8/ir/analysis/escape/EscapeAnalysis.java
index fc21b02..99f161e 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/escape/EscapeAnalysis.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/escape/EscapeAnalysis.java
@@ -131,9 +131,8 @@
if (user.getBlock() == block) {
// When the value of interest has the definition
if (!root.isPhi()) {
- List<Instruction> instructions = block.getInstructions();
// Make sure we're not considering instructions prior to the value of interest.
- if (instructions.indexOf(user) < instructions.indexOf(root.definition)) {
+ if (user.comesBefore(root.definition)) {
continue;
}
}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/fieldvalueanalysis/InstanceFieldValueAnalysis.java b/src/main/java/com/android/tools/r8/ir/analysis/fieldvalueanalysis/InstanceFieldValueAnalysis.java
index c60e298..ac5a053 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/fieldvalueanalysis/InstanceFieldValueAnalysis.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/fieldvalueanalysis/InstanceFieldValueAnalysis.java
@@ -287,7 +287,7 @@
// TODO(b/279877113): Extend this analysis to analyze the full remainder of this method.
if (instancePut.getBlock().getSuccessors().isEmpty()) {
InstructionListIterator instructionIterator =
- instancePut.getBlock().listIterator(code, instancePut);
+ instancePut.getBlock().listIterator(code, instancePut.getNext());
while (instructionIterator.hasNext()) {
Instruction instruction = instructionIterator.next();
if (instruction.readSet(appView, context).contains(field)) {
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/inlining/SimpleInliningConstraintAnalysis.java b/src/main/java/com/android/tools/r8/ir/analysis/inlining/SimpleInliningConstraintAnalysis.java
index fa31549..70eafed 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/inlining/SimpleInliningConstraintAnalysis.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/inlining/SimpleInliningConstraintAnalysis.java
@@ -20,7 +20,6 @@
import com.android.tools.r8.ir.code.If;
import com.android.tools.r8.ir.code.IfType;
import com.android.tools.r8.ir.code.Instruction;
-import com.android.tools.r8.ir.code.InstructionIterator;
import com.android.tools.r8.ir.code.InvokeVirtual;
import com.android.tools.r8.ir.code.JumpInstruction;
import com.android.tools.r8.ir.code.StringSwitch;
@@ -78,21 +77,18 @@
// Run a bounded depth-first traversal to collect the path constraints that lead to early
// returns.
- InstructionIterator instructionIterator =
- code.entryBlock().iterator(code.getNumberOfArguments());
- return analyzeInstructionsInBlock(code.entryBlock(), 0, 0, instructionIterator);
+ BasicBlock block = code.entryBlock();
+ Instruction firstNonArgument = block.getInstructions().getNth(code.getNumberOfArguments());
+ return analyzeInstructionsInBlock(block, 0, 0, firstNonArgument);
}
private SimpleInliningConstraintWithDepth analyzeInstructionsInBlock(
BasicBlock block, int branchDepth, int instructionDepth) {
- return analyzeInstructionsInBlock(block, branchDepth, instructionDepth, block.iterator());
+ return analyzeInstructionsInBlock(block, branchDepth, instructionDepth, block.entry());
}
private SimpleInliningConstraintWithDepth analyzeInstructionsInBlock(
- BasicBlock block,
- int branchDepth,
- int instructionDepth,
- InstructionIterator instructionIterator) {
+ BasicBlock block, int branchDepth, int instructionDepth, Instruction instruction) {
if (!seen.add(block)
|| block.hasCatchHandlers()
|| block.exit().isThrow()
@@ -102,7 +98,6 @@
// Move the instruction iterator forward to the block's jump instruction, while incrementing the
// instruction depth of the depth-first traversal.
- Instruction instruction = instructionIterator.next();
SimpleInliningConstraint blockConstraint = AlwaysSimpleInliningConstraint.getInstance();
while (!instruction.isJumpInstruction()) {
assert !instruction.isArgument();
@@ -116,7 +111,7 @@
} else {
blockConstraint = blockConstraint.meet(instructionConstraint);
}
- instruction = instructionIterator.next();
+ instruction = instruction.getNext();
}
// If we have exceeded the threshold, then all paths from this instruction will not lead to any
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedExtensionRegistryShrinker.java b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedExtensionRegistryShrinker.java
index 3dce430..84bf5e1 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedExtensionRegistryShrinker.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedExtensionRegistryShrinker.java
@@ -154,7 +154,7 @@
// Already removed.
continue;
}
- IRCodeUtils.removeInstructionAndTransitiveInputsIfNotUsed(code, instruction);
+ IRCodeUtils.removeInstructionAndTransitiveInputsIfNotUsed(instruction);
}
code.removeRedundantBlocks();
assert code.isConsistentSSA(appView);
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteShrinker.java b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteShrinker.java
index 1b3837a..4919305 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteShrinker.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteShrinker.java
@@ -341,7 +341,8 @@
ProtoMessageInfo protoMessageInfo) {
// Position iterator immediately before the call to newMessageInfo().
BasicBlock block = newMessageInfoInvoke.getBlock();
- InstructionListIterator instructionIterator = block.listIterator(code, newMessageInfoInvoke);
+ InstructionListIterator instructionIterator =
+ block.listIterator(code, newMessageInfoInvoke.getNext());
Instruction previous = instructionIterator.previous();
instructionIterator.setInsertionPosition(newMessageInfoInvoke.getPosition());
assert previous == newMessageInfoInvoke;
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 59fde05..5e5c563 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
@@ -47,7 +47,6 @@
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
-import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
@@ -173,9 +172,8 @@
// Catch handler information about which successors are catch handlers and what their guards are.
private CatchHandlers<Integer> catchHandlers = CatchHandlers.EMPTY_INDICES;
- // TODO(b/270398965): Replace LinkedList.
- @SuppressWarnings("JdkObsolete")
- private LinkedList<Instruction> instructions = new LinkedList<>();
+ // Linked list of instructions belonging to this block.
+ private final InstructionList instructions = new InstructionList(this);
private int number = -1;
private List<Phi> phis = new ArrayList<>();
@@ -202,6 +200,23 @@
// Map of registers to current SSA value. Used during SSA numbering and cleared once filled.
private Map<Integer, Value> currentDefinitions = new HashMap<>();
+ // Metadata shared by all blocks of an IRCode.
+ // TODO(b/376663044): Remove |metadata| parameter from methods in this class.
+ private IRMetadata metadata;
+
+ public BasicBlock(IRMetadata metadata) {
+ this.metadata = metadata;
+ }
+
+ public IRMetadata getMetadata() {
+ return metadata;
+ }
+
+ // Required when moving a block between code objects (inlining).
+ void setMetadata(IRMetadata metadata) {
+ this.metadata = metadata;
+ }
+
public <BT, CT> TraversalContinuation<BT, CT> traverseNormalPredecessors(
BiFunction<? super BasicBlock, ? super CT, TraversalContinuation<BT, CT>> fn,
CT initialValue) {
@@ -524,7 +539,8 @@
} else if (exit().isIf()) {
if (indexOfNewBlock >= successors.size() - 2 && indexOfOldBlock >= successors.size() - 2) {
// New and old are true target and fallthrough, replace last instruction with a goto.
- Instruction instruction = getInstructions().removeLast();
+ Instruction instruction = instructions.getLast();
+ instructions.removeIgnoreValues(instruction);
// Iterate in reverse order to ensure that POP instructions are inserted in correct order.
for (int i = instruction.inValues().size() - 1; i >= 0; i--) {
Value value = instruction.inValues().get(i);
@@ -536,7 +552,6 @@
} else {
assert !(value instanceof StackValues);
Pop pop = new Pop(value);
- pop.setBlock(this);
pop.setPosition(instruction.getPosition());
getInstructions().addLast(pop);
}
@@ -546,7 +561,6 @@
}
}
Instruction exit = new Goto();
- exit.setBlock(this);
exit.setPosition(instruction.getPosition());
getInstructions().addLast(exit);
} else if (indexOfOldBlock >= successors.size() - 2) {
@@ -738,7 +752,7 @@
return nextInstructionNumber;
}
- public LinkedList<Instruction> getInstructions() {
+ public InstructionList getInstructions() {
return instructions;
}
@@ -797,22 +811,24 @@
}
public Instruction entry() {
- return instructions.get(0);
+ return instructions.getFirst();
}
public JumpInstruction exit() {
assert filled;
- assert instructions.get(instructions.size() - 1).isJumpInstruction();
- return instructions.get(instructions.size() - 1).asJumpInstruction();
+ assert instructions.getLast().isJumpInstruction();
+ return instructions.getLast().asJumpInstruction();
+ }
+
+ public Instruction getLastInstruction() {
+ return instructions.getLast();
}
public Instruction exceptionalExit() {
assert hasCatchHandlers();
- InstructionIterator it = iterator(instructions.size());
- while (it.hasPrevious()) {
- Instruction instruction = it.previous();
- if (instruction.instructionTypeCanThrow()) {
- return instruction;
+ for (Instruction ins = getLastInstruction(); ins != null; ins = ins.getPrev()) {
+ if (ins.instructionTypeCanThrow()) {
+ return ins;
}
}
return null;
@@ -892,15 +908,9 @@
phis.removeAll(phisToRemove);
}
- public void add(Instruction next, IRCode code) {
- add(next, code.metadata());
- }
-
- public void add(Instruction next, IRMetadata metadata) {
+ public void add(Instruction next, IRMetadata unused_metadata) {
assert !isFilled();
- instructions.add(next);
- metadata.record(next);
- next.setBlock(this);
+ instructions.addLast(next);
}
public void close(IRBuilder builder) {
@@ -1493,49 +1503,11 @@
return builder.toString();
}
- public void addPhiMove(Move move) {
- // TODO(ager): Consider this more, is it always the case that we should add it before the
- // exit instruction?
- Instruction branch = exit();
- instructions.set(instructions.size() - 1, move);
- instructions.add(branch);
- }
-
- public void setInstructions(LinkedList<Instruction> instructions) {
- this.instructions = instructions;
- }
-
- /**
- * Remove a number of instructions. The instructions to remove are given as indexes in the
- * instruction stream.
- */
- // TODO(b/270398965): Replace LinkedList.
- @SuppressWarnings("JdkObsolete")
- public void removeInstructions(List<Integer> toRemove) {
- if (!toRemove.isEmpty()) {
- LinkedList<Instruction> newInstructions = new LinkedList<>();
- int nextIndex = 0;
- for (Integer index : toRemove) {
- assert index >= nextIndex; // Indexes in toRemove must be sorted ascending.
- newInstructions.addAll(instructions.subList(nextIndex, index));
- instructions.get(index).clearBlock();
- nextIndex = index + 1;
- }
- if (nextIndex < instructions.size()) {
- newInstructions.addAll(instructions.subList(nextIndex, instructions.size()));
- }
- assert instructions.size() == newInstructions.size() + toRemove.size();
- setInstructions(newInstructions);
- }
- }
-
/**
* Remove an instruction.
*/
public void removeInstruction(Instruction toRemove) {
- int index = instructions.indexOf(toRemove);
- assert index >= 0;
- removeInstructions(Collections.singletonList(index));
+ instructions.removeIgnoreValues(toRemove);
}
/**
@@ -1563,7 +1535,7 @@
*/
public static BasicBlock createGotoBlock(
int blockNumber, Position position, IRMetadata metadata) {
- BasicBlock block = new BasicBlock();
+ BasicBlock block = new BasicBlock(metadata);
block.add(new Goto(), metadata);
block.close(null);
block.setNumber(blockNumber);
@@ -1580,7 +1552,7 @@
* @param theIf the if instruction
*/
public static BasicBlock createIfBlock(int blockNumber, If theIf, IRMetadata metadata) {
- BasicBlock block = new BasicBlock();
+ BasicBlock block = new BasicBlock(metadata);
block.add(theIf, metadata);
block.close(null);
block.setNumber(blockNumber);
@@ -1598,7 +1570,7 @@
*/
public static BasicBlock createIfBlock(
int blockNumber, If theIf, IRMetadata metadata, Instruction... instructions) {
- BasicBlock block = new BasicBlock();
+ BasicBlock block = new BasicBlock(metadata);
for (Instruction instruction : instructions) {
block.add(instruction, metadata);
}
@@ -1610,7 +1582,7 @@
public static BasicBlock createSwitchBlock(
int blockNumber, IntSwitch theSwitch, IRMetadata metadata) {
- BasicBlock block = new BasicBlock();
+ BasicBlock block = new BasicBlock(metadata);
block.add(theSwitch, metadata);
block.close(null);
block.setNumber(blockNumber);
@@ -1621,14 +1593,14 @@
IRCode code, Position position, DexType guard, AppView<?> appView) {
TypeElement guardTypeLattice =
TypeElement.fromDexType(guard, Nullability.definitelyNotNull(), appView);
- BasicBlock block = new BasicBlock();
+ BasicBlock block = new BasicBlock(code.metadata());
MoveException moveException =
new MoveException(code.createValue(guardTypeLattice), guard, appView.options());
moveException.setPosition(position);
Throw throwInstruction = new Throw(moveException.outValue);
throwInstruction.setPosition(position);
- block.add(moveException, code);
- block.add(throwInstruction, code);
+ block.instructions.addLast(moveException);
+ block.instructions.addLast(throwInstruction);
block.close(null);
block.setNumber(code.getNextBlockNumber());
return block;
@@ -1779,9 +1751,9 @@
// visible to exceptional successors.
private boolean verifyNoValuesAfterThrowingInstruction() {
if (hasCatchHandlers()) {
- InstructionIterator iterator = iterator(instructions.size());
- while (iterator.hasPrevious()) {
- Instruction instruction = iterator.previous();
+ for (Instruction instruction = getLastInstruction();
+ instruction != null;
+ instruction = instruction.getPrev()) {
if (instruction.instructionTypeCanThrow()) {
return true;
}
@@ -1791,58 +1763,53 @@
return true;
}
- public BasicBlockInstructionIterator iterator() {
- return new BasicBlockInstructionIterator(this);
+ public InstructionIterator iterator() {
+ return instructions.iterator();
}
- public BasicBlockInstructionIterator iterator(int index) {
- return new BasicBlockInstructionIterator(this, index);
+ public InstructionIterator iterator(Instruction instruction) {
+ return instructions.iterator(instruction);
}
- public BasicBlockInstructionIterator iterator(Instruction instruction) {
- return new BasicBlockInstructionIterator(this, instruction);
+ public BasicBlockInstructionListIterator listIterator(IRCode unused_code) {
+ return listIterator();
}
- public BasicBlockInstructionListIterator listIterator(IRCode code) {
- return listIterator(code.metadata());
+ public BasicBlockInstructionListIterator listIterator() {
+ return new BasicBlockInstructionListIterator(this);
}
- public BasicBlockInstructionListIterator listIterator(IRMetadata metadata) {
- return new BasicBlockInstructionListIterator(metadata, this);
+ public BasicBlockInstructionListIterator listIterator(IRCode unused_code, int index) {
+ // TODO(b/376663044): Convert uses of index to use Instruction instead.
+ return new BasicBlockInstructionListIterator(this, index);
}
- public BasicBlockInstructionListIterator listIterator(IRCode code, int index) {
- return new BasicBlockInstructionListIterator(code.metadata(), this, index);
- }
-
- /**
- * Creates an instruction list iterator starting at <code>instruction</code>.
- *
- * <p>The cursor will be positioned after <code>instruction</code>. Calling <code>next</code> on
- * the returned iterator will return the instruction after <code>instruction</code>. Calling
- * <code>previous</code> will return <code>instruction</code>.
- */
- public BasicBlockInstructionListIterator listIterator(IRCode code, Instruction instruction) {
- return new BasicBlockInstructionListIterator(code.metadata(), this, instruction);
+ /** Creates an instruction list iterator starting at <code>firstInstructionToReturn</code>. */
+ public BasicBlockInstructionListIterator listIterator(
+ IRCode unused_code, Instruction firstInstructionToReturn) {
+ return new BasicBlockInstructionListIterator(this, firstInstructionToReturn);
}
/**
* Creates a new empty block as a successor for this block.
*
- * The new block will have all the normal successors of the original block.
+ * <p>The new block will have all the normal successors of the original block.
*
- * The catch successors are either on the original block or the new block depending on the
+ * <p>The catch successors are either on the original block or the new block depending on the
* value of <code>keepCatchHandlers</code>.
*
- * The current block still has all the instructions, and the new block is empty instruction-wise.
+ * <p>The current block still has all the instructions, and the new block is empty
+ * instruction-wise.
*
* @param blockNumber block number for new block
* @param keepCatchHandlers keep catch successors on the original block
+ * @param firstInstructionOfNewBlock this and all following are moved to the new block
* @return the new block
*/
- BasicBlock createSplitBlock(int blockNumber, boolean keepCatchHandlers) {
+ BasicBlock createSplitBlock(
+ int blockNumber, boolean keepCatchHandlers, Instruction firstInstructionOfNewBlock) {
boolean hadCatchHandlers = hasCatchHandlers();
- BasicBlock newBlock = new BasicBlock();
+ BasicBlock newBlock = new BasicBlock(metadata);
newBlock.setNumber(blockNumber);
// Copy all successors including catch handlers to the new block, and update predecessors.
@@ -1862,6 +1829,10 @@
// Link the two blocks
link(newBlock);
+ if (firstInstructionOfNewBlock != null) {
+ newBlock.instructions.severFrom(firstInstructionOfNewBlock);
+ }
+
// Mark the new block filled and sealed.
newBlock.filled = true;
newBlock.sealed = true;
@@ -1936,7 +1907,7 @@
exceptionTypeLattice = move.getOutType();
exceptionType = move.getExceptionType();
assert move.getDebugValues().isEmpty();
- getInstructions().remove(0);
+ instructions.removeIgnoreValues(move);
}
// Create new predecessor blocks.
List<BasicBlock> newPredecessors = new ArrayList<>(predecessors.size());
@@ -1946,19 +1917,19 @@
throw new CompilationError(
"Invalid block structure: catch block reachable via non-exceptional flow.");
}
- BasicBlock newBlock = new BasicBlock();
+ BasicBlock newBlock = new BasicBlock(metadata);
newBlock.setNumber(code.getNextBlockNumber());
newPredecessors.add(newBlock);
if (hasMoveException) {
Value value = code.createValue(exceptionTypeLattice, move.getLocalInfo());
values.add(value);
MoveException newMove = new MoveException(value, exceptionType, options);
- newBlock.add(newMove, code);
+ newBlock.instructions.addLast(newMove);
newMove.setPosition(position);
}
Goto next = new Goto();
next.setPosition(position);
- newBlock.add(next, code);
+ newBlock.instructions.addLast(next);
newBlock.close(null);
newBlock.getMutableSuccessors().add(this);
newBlock.getMutablePredecessors().add(predecessor);
diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java
deleted file mode 100644
index f0771c3..0000000
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java
+++ /dev/null
@@ -1,45 +0,0 @@
-// Copyright (c) 2019, 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 java.util.ListIterator;
-
-public class BasicBlockInstructionIterator implements InstructionIterator {
-
- private final ListIterator<Instruction> instructionIterator;
-
- BasicBlockInstructionIterator(BasicBlock block) {
- this.instructionIterator = block.getInstructions().listIterator();
- }
-
- BasicBlockInstructionIterator(BasicBlock block, int index) {
- this.instructionIterator = block.getInstructions().listIterator(index);
- }
-
- BasicBlockInstructionIterator(BasicBlock block, Instruction instruction) {
- this(block);
- nextUntil(x -> x == instruction);
- }
-
- @Override
- public boolean hasPrevious() {
- return instructionIterator.hasPrevious();
- }
-
- @Override
- public Instruction previous() {
- return instructionIterator.previous();
- }
-
- @Override
- public boolean hasNext() {
- return instructionIterator.hasNext();
- }
-
- @Override
- public Instruction next() {
- return instructionIterator.next();
- }
-}
diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionListIterator.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionListIterator.java
index d1fc0ed..af87309 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionListIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionListIterator.java
@@ -33,35 +33,33 @@
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
+import java.util.NoSuchElementException;
import java.util.Set;
import java.util.function.Consumer;
import java.util.function.UnaryOperator;
public class BasicBlockInstructionListIterator implements InstructionListIterator {
- protected final BasicBlock block;
- protected final ListIterator<Instruction> listIterator;
+ private Instruction next;
protected Instruction current;
- private Position position = null;
+ protected final BasicBlock block;
+ private final InstructionList instructionList;
+ private Position position;
- private final IRMetadata metadata;
-
- BasicBlockInstructionListIterator(IRMetadata metadata, BasicBlock block) {
- this.block = block;
- this.listIterator = block.getInstructions().listIterator();
- this.metadata = metadata;
+ BasicBlockInstructionListIterator(BasicBlock block) {
+ this(block, 0);
}
- BasicBlockInstructionListIterator(IRMetadata metadata, BasicBlock block, int index) {
- this.block = block;
- this.listIterator = block.getInstructions().listIterator(index);
- this.metadata = metadata;
+ BasicBlockInstructionListIterator(BasicBlock block, int index) {
+ // TODO(b/376663044): Convert uses of index to use Instruction instead.
+ this(block, index == block.size() ? null : block.getInstructions().getNth(index));
}
- BasicBlockInstructionListIterator(
- IRMetadata metadata, BasicBlock block, Instruction instruction) {
- this(metadata, block);
- nextUntil(x -> x == instruction);
+ BasicBlockInstructionListIterator(BasicBlock block, Instruction firstInstructionToReturn) {
+ this.block = block;
+ this.instructionList = block.getInstructions();
+ this.current = firstInstructionToReturn == null ? null : firstInstructionToReturn.getPrev();
+ this.next = firstInstructionToReturn;
}
public BasicBlock getBlock() {
@@ -70,54 +68,59 @@
@Override
public boolean hasNext() {
- return listIterator.hasNext();
+ return next != null;
}
@Override
public Instruction next() {
- current = listIterator.next();
- return current;
+ Instruction ret = next;
+ if (ret == null) {
+ throw new NoSuchElementException();
+ }
+ assert ret.block == block : "Iterator invalidated: " + ret;
+ current = ret;
+ next = ret.next;
+ return ret;
}
@Override
public int nextIndex() {
- return listIterator.nextIndex();
+ throw new UnsupportedOperationException();
}
@Override
public Instruction peekNext() {
- // Reset current since listIterator.remove() changes based on whether next() or previous() was
- // last called.
- // E.g.: next() -> current=C
- // peekNext(): next() -> current=D, previous() -> current=D
- current = null;
- return IteratorUtils.peekNext(listIterator);
+ assert next == null || next.block == block : "Iterator invalidated: " + next;
+ return next;
}
@Override
public boolean hasPrevious() {
- return listIterator.hasPrevious();
+ return next == null ? !instructionList.isEmpty() : next.prev != null;
}
@Override
public Instruction previous() {
- current = listIterator.previous();
- return current;
+ Instruction ret = next == null ? instructionList.getLastOrNull() : next.prev;
+ if (ret == null) {
+ throw new NoSuchElementException();
+ }
+ assert ret.block == block : "Iterator invalidated: " + next;
+ current = ret;
+ next = ret;
+ return ret;
}
@Override
public int previousIndex() {
- return listIterator.previousIndex();
+ throw new UnsupportedOperationException();
}
@Override
public Instruction peekPrevious() {
- // Reset current since listIterator.remove() changes based on whether next() or previous() was
- // last called.
- // E.g.: previous() -> current=B
- // peekPrevious(): previous() -> current=A, next() -> current=A
- current = null;
- return IteratorUtils.peekPrevious(listIterator);
+ Instruction ret = next == null ? instructionList.getLastOrNull() : next.prev;
+ assert ret == null || ret.block == block : "Iterator invalidated: " + next;
+ return ret;
}
@Override
@@ -153,13 +156,10 @@
*/
@Override
public void add(Instruction instruction) {
- instruction.setBlock(block);
- assert instruction.getBlock() == block;
if (!instruction.hasPosition() && hasInsertionPosition()) {
instruction.setPosition(getInsertionPosition());
}
- listIterator.add(instruction);
- metadata.record(instruction);
+ instructionList.addBefore(instruction, next);
}
private boolean hasPriorThrowingInstruction() {
@@ -239,10 +239,14 @@
*/
@Override
public void set(Instruction instruction) {
- instruction.setBlock(block);
- assert instruction.getBlock() == block;
- listIterator.set(instruction);
- metadata.record(instruction);
+ if (current == null) {
+ throw new IllegalStateException();
+ }
+ instructionList.replace(current, instruction);
+ if (current == next) {
+ next = instruction;
+ }
+ current = instruction;
}
@Override
@@ -253,6 +257,19 @@
}
}
+ /** Updates |current| and |next|, and returns the old |current|. */
+ private Instruction removeHelper() {
+ Instruction target = current;
+ if (target == null) {
+ throw new IllegalStateException();
+ }
+ if (target == next) {
+ next = target.next;
+ }
+ current = null;
+ return target;
+ }
+
/**
* Remove the current instruction (aka the {@link Instruction} returned by the previous call to
* {@link #next}.
@@ -264,74 +281,31 @@
*/
@Override
public void remove() {
- if (current == null) {
- throw new IllegalStateException();
- }
- assert current.outValue() == null || !current.outValue().isUsed();
- assert current.getDebugValues().isEmpty();
- for (int i = 0; i < current.inValues().size(); i++) {
- Value value = current.inValues().get(i);
- value.removeUser(current);
- }
- // These needs to stay to ensure that an optimization incorrectly not taking debug info into
- // account still produces valid code when run without enabled assertions.
- for (Value value : current.getDebugValues()) {
- value.removeDebugUser(current);
- }
- if (current.getLocalInfo() != null) {
- for (Instruction user : current.outValue().debugUsers()) {
- user.removeDebugValue(current.outValue());
- }
- }
- listIterator.remove();
- current = null;
+ instructionList.removeAndDetachInValues(removeHelper());
}
@Override
public void removeInstructionIgnoreOutValue() {
- if (current == null) {
- throw new IllegalStateException();
- }
- listIterator.remove();
- current = null;
+ instructionList.removeIgnoreValues(removeHelper());
}
@Override
public void removeOrReplaceByDebugLocalRead() {
- if (current == null) {
- throw new IllegalStateException();
- }
- if (current.getDebugValues().isEmpty()) {
- remove();
- } else {
- replaceCurrentInstruction(new DebugLocalRead());
- }
+ instructionList.removeOrReplaceByDebugLocalRead(removeHelper());
}
@Override
- public void replaceCurrentInstruction(Instruction newInstruction, Set<Value> affectedValues) {
+ public void replaceCurrentInstruction(Instruction newInstruction, AffectedValues affectedValues) {
if (current == null) {
throw new IllegalStateException();
}
- for (Value value : current.inValues()) {
- value.removeUser(current);
+ if (current == next) {
+ // TODO(b/376663044): This should not advance the cursor. Prior implementation used remove()
+ // and add() rather than set(), which causes replaced item to appear when iterating backwards.
+ // E.g.: Should be: next = newInstruction;
+ next = next.next;
}
- if (current.hasUsedOutValue()) {
- assert newInstruction.outValue() != null;
- if (affectedValues != null && !newInstruction.getOutType().equals(current.getOutType())) {
- current.outValue().addAffectedValuesTo(affectedValues);
- }
- current.outValue().replaceUsers(newInstruction.outValue());
- }
- current.moveDebugValues(newInstruction);
- newInstruction.setBlock(block);
- if (!newInstruction.hasPosition()) {
- newInstruction.setPosition(current.getPosition());
- }
- listIterator.remove();
- listIterator.add(newInstruction);
- current.clearBlock();
- metadata.record(newInstruction);
+ instructionList.replace(current, newInstruction, affectedValues);
current = newInstruction;
}
@@ -508,7 +482,7 @@
@Override
public void replaceCurrentInstructionWithStaticGet(
- AppView<?> appView, IRCode code, DexField field, Set<Value> affectedValues) {
+ AppView<?> appView, IRCode code, DexField field, AffectedValues affectedValues) {
if (current == null) {
throw new IllegalStateException();
}
@@ -691,22 +665,17 @@
// Get the position at which the block is being split.
Position position = getPreviousPosition();
- // Prepare the new block, placing the exception handlers on the block with the throwing
- // instruction.
- BasicBlock newBlock = block.createSplitBlock(code.getNextBlockNumber(), keepCatchHandlers);
-
// Add a goto instruction.
- Goto newGoto = new Goto(block);
- listIterator.add(newGoto);
+ Goto newGoto = new Goto();
+ instructionList.addBefore(newGoto, next);
newGoto.setPosition(position);
- // Move all remaining instructions to the new block.
- while (listIterator.hasNext()) {
- Instruction instruction = listIterator.next();
- newBlock.getInstructions().addLast(instruction);
- instruction.setBlock(newBlock);
- listIterator.remove();
- }
+ // Prepare the new block, placing the exception handlers on the block with the throwing
+ // instruction.
+ BasicBlock newBlock =
+ block.createSplitBlock(code.getNextBlockNumber(), keepCatchHandlers, next);
+ next = null;
+ current = null;
// Insert the new block in the block list right after the current block.
if (blocksIterator == null) {
@@ -917,10 +886,8 @@
entryBlockIterator = entryBlock.listIterator(code);
// Insert cast instruction into the new block.
inlineEntry.listIterator(code).add(castInstruction);
- castInstruction.setBlock(inlineEntry);
assert castInstruction.getBlock().getInstructions().size() == 2;
} else {
- castInstruction.setBlock(entryBlock);
entryBlockIterator = entryBlock.listIterator(code);
entryBlockIterator.add(castInstruction);
}
@@ -1011,9 +978,12 @@
assert IteratorUtils.peekNext(blocksIterator) == invokeBlock;
// Insert inlinee blocks into the IR code of the callee, before the invoke block.
+ IRMetadata ourMetadata = block.getMetadata();
+ ourMetadata.merge(inlineEntry.getMetadata());
for (BasicBlock bb : inlinee.blocks) {
bb.setNumber(code.getNextBlockNumber());
blocksIterator.add(bb);
+ bb.setMetadata(ourMetadata);
}
// If the invoke block had catch handlers copy those down to all inlined blocks.
@@ -1057,7 +1027,7 @@
it.previous();
return it;
}
- BasicBlock newExitBlock = new BasicBlock();
+ BasicBlock newExitBlock = new BasicBlock(code.metadata());
newExitBlock.setNumber(code.getNextBlockNumber());
Return newReturn;
if (normalExits.get(0).exit().asReturn().isReturnVoid()) {
@@ -1090,7 +1060,7 @@
}
// The newly constructed return will be eliminated as part of inlining so we set position none.
newReturn.setPosition(Position.none());
- newExitBlock.add(newReturn, metadata);
+ newExitBlock.add(newReturn, code.metadata());
for (BasicBlock exitBlock : normalExits) {
InstructionListIterator it = exitBlock.listIterator(code, exitBlock.getInstructions().size());
Instruction oldExit = it.previous();
diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlockIterator.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlockIterator.java
index 0b9c54c..0411cd2 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlockIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlockIterator.java
@@ -105,12 +105,10 @@
throw new IllegalStateException();
}
// Remove all instructions from the block before removing the block.
- InstructionListIterator iterator = current.listIterator(code);
- while (iterator.hasNext()) {
- Instruction instruction = iterator.next();
- instruction.clearDebugValues();
- iterator.remove();
+ for (Instruction ins = current.entry(); ins != null; ins = ins.getNext()) {
+ ins.detachInValues();
}
+ current.getInstructions().clear();
listIterator.remove();
current = null;
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/DominatorTree.java b/src/main/java/com/android/tools/r8/ir/code/DominatorTree.java
index 20eadc9..e04ff68 100644
--- a/src/main/java/com/android/tools/r8/ir/code/DominatorTree.java
+++ b/src/main/java/com/android/tools/r8/ir/code/DominatorTree.java
@@ -27,7 +27,7 @@
private final BasicBlock[] sorted;
private BasicBlock[] doms;
- private final BasicBlock normalExitBlock = new BasicBlock();
+ private final BasicBlock normalExitBlock;
private final int unreachableStartIndex;
@@ -40,6 +40,7 @@
public DominatorTree(IRCode code, Assumption assumption) {
assert assumption != null;
assert assumption == MAY_HAVE_UNREACHABLE_BLOCKS || code.getUnreachableBlocks().isEmpty();
+ normalExitBlock = new BasicBlock(code.metadata());
ImmutableList<BasicBlock> blocks = code.topologicallySortedBlocks();
// Add the internal exit block to the block list.
diff --git a/src/main/java/com/android/tools/r8/ir/code/Goto.java b/src/main/java/com/android/tools/r8/ir/code/Goto.java
index 9beaff7..3c5a357 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Goto.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Goto.java
@@ -8,25 +8,10 @@
import com.android.tools.r8.ir.conversion.CfBuilder;
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.lightir.LirBuilder;
-import com.android.tools.r8.utils.ListUtils;
import java.util.List;
import java.util.ListIterator;
public class Goto extends JumpInstruction {
-
- public Goto() {
- super();
- }
-
- public Goto(BasicBlock block) {
- this();
- setBlock(block);
- }
-
- public static Builder builder() {
- return new Builder();
- }
-
@Override
public int opcode() {
return Opcodes.GOTO;
@@ -77,7 +62,7 @@
// Avoids BasicBlock.exit(), since it will assert when block is invalid.
if (myBlock != null
&& !myBlock.getSuccessors().isEmpty()
- && ListUtils.last(myBlock.getInstructions()) == this) {
+ && myBlock.getInstructions().getLastOrNull() == this) {
return super.toString() + "block " + getTarget().getNumberAsString();
}
return super.toString() + "block <unknown>";
@@ -129,24 +114,4 @@
public void buildLir(LirBuilder<Value, ?> builder) {
builder.addGoto(getTarget());
}
-
- public static class Builder extends BuilderBase<Builder, Goto> {
-
- private BasicBlock target;
-
- public Builder setTarget(BasicBlock target) {
- this.target = target;
- return self();
- }
-
- @Override
- public Goto build() {
- return amend(new Goto(target));
- }
-
- @Override
- public Builder self() {
- return this;
- }
- }
}
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 307acdf..cbf7075 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
@@ -383,10 +383,10 @@
if (hasSeenThrowingInstruction) {
List<BasicBlock> successors = block.getSuccessors();
if (successors.size() == 1 && ListUtils.first(successors).getPredecessors().size() > 1) {
- BasicBlock splitBlock = block.createSplitBlock(getNextBlockNumber(), true);
- Goto newGoto = new Goto(block);
+ BasicBlock splitBlock = block.createSplitBlock(getNextBlockNumber(), true, null);
+ Goto newGoto = new Goto();
newGoto.setPosition(Position.none());
- splitBlock.listIterator(this).add(newGoto);
+ splitBlock.getInstructions().addLast(newGoto);
blockIterator.add(splitBlock);
}
}
@@ -1202,10 +1202,10 @@
}
public Argument getLastArgument() {
- InstructionIterator instructionIterator = entryBlock().iterator(getNumberOfArguments() - 1);
- Argument lastArgument = instructionIterator.next().asArgument();
+ Instruction lastArgInstr = entryBlock().getInstructions().getNth(getNumberOfArguments() - 1);
+ Argument lastArgument = lastArgInstr.asArgument();
assert lastArgument != null;
- assert !instructionIterator.peekNext().isArgument();
+ assert !lastArgInstr.getNext().isArgument();
return lastArgument;
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCodeInstructionListIterator.java b/src/main/java/com/android/tools/r8/ir/code/IRCodeInstructionListIterator.java
index 13e393a..6eb4a80 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCodeInstructionListIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCodeInstructionListIterator.java
@@ -104,7 +104,7 @@
@Override
public void replaceCurrentInstructionWithStaticGet(
- AppView<?> appView, IRCode code, DexField field, Set<Value> affectedValues) {
+ AppView<?> appView, IRCode code, DexField field, AffectedValues affectedValues) {
instructionIterator.replaceCurrentInstructionWithStaticGet(
appView, code, field, affectedValues);
}
@@ -278,7 +278,7 @@
}
@Override
- public void replaceCurrentInstruction(Instruction newInstruction, Set<Value> affectedValues) {
+ public void replaceCurrentInstruction(Instruction newInstruction, AffectedValues affectedValues) {
instructionIterator.replaceCurrentInstruction(newInstruction, affectedValues);
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCodeUtils.java b/src/main/java/com/android/tools/r8/ir/code/IRCodeUtils.java
index e918ad4..4bb02dd 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCodeUtils.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCodeUtils.java
@@ -100,7 +100,7 @@
} else {
assert false;
}
- internalRemoveInstructionAndTransitiveInputsIfNotUsed(code, worklist);
+ internalRemoveInstructionAndTransitiveInputsIfNotUsed(worklist);
}
/**
@@ -109,14 +109,12 @@
*
* <p>Use with caution!
*/
- public static void removeInstructionAndTransitiveInputsIfNotUsed(
- IRCode code, Instruction instruction) {
- internalRemoveInstructionAndTransitiveInputsIfNotUsed(
- code, DequeUtils.newArrayDeque(instruction));
+ public static void removeInstructionAndTransitiveInputsIfNotUsed(Instruction instruction) {
+ internalRemoveInstructionAndTransitiveInputsIfNotUsed(DequeUtils.newArrayDeque(instruction));
}
private static void internalRemoveInstructionAndTransitiveInputsIfNotUsed(
- IRCode code, Deque<InstructionOrPhi> worklist) {
+ Deque<InstructionOrPhi> worklist) {
Set<InstructionOrPhi> removed = Sets.newIdentityHashSet();
while (!worklist.isEmpty()) {
InstructionOrPhi instructionOrPhi = worklist.removeFirst();
@@ -145,7 +143,7 @@
} else {
Instruction current = instructionOrPhi.asInstruction();
if (!current.hasOutValue() || !current.outValue().hasAnyUsers()) {
- current.getBlock().listIterator(code, current).removeOrReplaceByDebugLocalRead();
+ current.removeOrReplaceByDebugLocalRead();
for (Value inValue : current.inValues()) {
worklist.add(inValue.isPhi() ? inValue.asPhi() : inValue.definition);
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/Instruction.java b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
index d55ada3..2773951 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Instruction.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
@@ -28,6 +28,7 @@
import com.android.tools.r8.ir.conversion.CfBuilder;
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.ir.conversion.MethodConversionOptions;
+import com.android.tools.r8.ir.optimize.AffectedValues;
import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
import com.android.tools.r8.ir.optimize.InliningConstraints;
@@ -48,13 +49,15 @@
public abstract class Instruction
implements AbstractInstruction, InstructionOrPhi, MaterializingInstructionsInfo {
-
- protected Value outValue = null;
+ // Package-private to be used by InstructionList.
+ BasicBlock block;
+ Instruction prev;
+ Instruction next;
+ protected Value outValue;
protected final List<Value> inValues = new ArrayList<>();
- private BasicBlock block = null;
private int number = -1;
- private Set<Value> debugValues = null;
- private Position position = null;
+ private Set<Value> debugValues;
+ private Position position;
protected Instruction(Value outValue) {
setOutValue(outValue);
@@ -82,6 +85,14 @@
return position != null;
}
+ public Instruction getPrev() {
+ return prev;
+ }
+
+ public Instruction getNext() {
+ return next;
+ }
+
@Override
public final Position getPosition() {
assert position != null;
@@ -341,32 +352,56 @@
return block;
}
- /**
- * Set the basic block of this instruction. See IRBuilder.
- */
- public void setBlock(BasicBlock block) {
- assert block != null;
- this.block = block;
+ /** Prepares instruction for removal by removing its in-values. */
+ public Instruction detachInValues() {
+ for (Value value : inValues) {
+ value.removeUser(this);
+ }
+ // These needs to stay to ensure that an optimization incorrectly not taking debug info into
+ // account still produces valid code when run without enabled assertions.
+ if (debugValues != null) {
+ for (Value value : debugValues) {
+ value.removeDebugUser(this);
+ }
+ }
+ if (getLocalInfo() != null) {
+ for (Instruction user : outValue.debugUsers()) {
+ user.removeDebugValue(outValue);
+ }
+ }
+ return this;
}
- /**
- * Clear the basic block of this instruction. Use when removing an instruction from a block.
- */
- public void clearBlock() {
- assert block != null;
- block = null;
+ public void removeOrReplaceByDebugLocalRead() {
+ block.getInstructions().removeOrReplaceByDebugLocalRead(this);
}
- public void removeOrReplaceByDebugLocalRead(IRCode code) {
- getBlock().listIterator(code, this).removeOrReplaceByDebugLocalRead();
+ // TODO(b/376663044): Delete.
+ public void removeOrReplaceByDebugLocalRead(IRCode unused_code) {
+ block.getInstructions().removeOrReplaceByDebugLocalRead(this);
}
- public void replace(Instruction newInstruction, IRCode code) {
- replace(newInstruction, code, null);
+ public void removeIgnoreValues() {
+ block.getInstructions().removeIgnoreValues(this);
}
- public void replace(Instruction newInstruction, IRCode code, Set<Value> affectedValues) {
- getBlock().listIterator(code, this).replaceCurrentInstruction(newInstruction, affectedValues);
+ public void replace(Instruction newInstruction) {
+ block.getInstructions().replace(this, newInstruction);
+ }
+
+ // TODO(b/376663044): Delete.
+ public void replace(Instruction newInstruction, IRCode unused_code) {
+ block.getInstructions().replace(this, newInstruction);
+ }
+
+ public void replace(Instruction newInstruction, AffectedValues affectedValues) {
+ block.getInstructions().replace(this, newInstruction, affectedValues);
+ }
+
+ // TODO(b/376663044): Delete.
+ public void replace(
+ Instruction newInstruction, IRCode unused_code, AffectedValues affectedValues) {
+ block.getInstructions().replace(this, newInstruction, affectedValues);
}
/**
@@ -1630,6 +1665,20 @@
// Intentionally empty.
}
+ /** Returns whether the given instruction is encountered via continuous calls to getNext(). */
+ public boolean comesBefore(Instruction target) {
+ assert target != this;
+ assert target.block == block; // Probably a bug if this does not hold.
+ Instruction cur = next;
+ while (cur != null) {
+ if (cur == target) {
+ return true;
+ }
+ cur = cur.next;
+ }
+ return false;
+ }
+
public static class SideEffectAssumption {
public static final SideEffectAssumption NONE = new SideEffectAssumption();
diff --git a/src/main/java/com/android/tools/r8/ir/code/InstructionList.java b/src/main/java/com/android/tools/r8/ir/code/InstructionList.java
new file mode 100644
index 0000000..f95b67a
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/code/InstructionList.java
@@ -0,0 +1,302 @@
+// Copyright (c) 2024, 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 com.android.tools.r8.ir.optimize.AffectedValues;
+import java.util.Spliterator;
+import java.util.function.Consumer;
+import java.util.stream.Stream;
+import java.util.stream.StreamSupport;
+
+/**
+ * Linked list of instructions using Instruction.prev and Instruction.next fields.
+ *
+ * <pre>
+ * Design notes:
+ * - There is a 1:1 relationship between a BasicBlock and InstructionList.
+ * - We might want to just merge this into BasicBlock.
+ * - Updates IRMetadata and sets Instruction.block fields when instructions are added.
+ * - Does not implement Collection / List interfaces to better reflect that this is a
+ * special-purpose collection, where operations sometimes mutate the state of elements.
+ * - Does not implement a non-assert "contains" method. Use Instruction.block to check containment.
+ * - Does not clear next/prev fields upon removal.
+ * - Because there has not yet been a need to reuse instructions (except for the special case of
+ * block splitting).
+ * - |block| is cleared, and asserts prevent instructions from being added that already have a
+ * block set.
+ * </pre>
+ */
+public class InstructionList implements Iterable<Instruction> {
+ private final BasicBlock ownerBlock;
+ private Instruction head;
+ private Instruction tail;
+ private int size;
+
+ public InstructionList(BasicBlock ownerBlock) {
+ this.ownerBlock = ownerBlock;
+ }
+
+ public int size() {
+ return size;
+ }
+
+ public boolean isEmpty() {
+ return head == null;
+ }
+
+ public Instruction getFirst() {
+ assert !isEmpty();
+ return head;
+ }
+
+ public Instruction getFirstOrNull() {
+ return head;
+ }
+
+ /** Returns the instruction at the given index. This is O(n). */
+ public Instruction getNth(int n) {
+ assert n >= 0 && n < size : "n=" + n + " size=" + size;
+ if (n > size / 2) {
+ Instruction ret = tail;
+ n = size - n - 1;
+ for (int i = 0; i < n; ++i) {
+ ret = ret.prev;
+ }
+ return ret;
+ }
+ Instruction ret = head;
+ for (int i = 0; i < n; ++i) {
+ ret = ret.next;
+ }
+ return ret;
+ }
+
+ public Instruction getLast() {
+ assert !isEmpty();
+ return tail;
+ }
+
+ public Instruction getLastOrNull() {
+ return tail;
+ }
+
+ public void addFirst(Instruction newInstruction) {
+ addBefore(newInstruction, head);
+ }
+
+ public void addLast(Instruction newInstruction) {
+ addBefore(newInstruction, null);
+ }
+
+ /**
+ * Inserts newInstruction before existingInstruction. If existingInstruction is null, adds at the
+ * end.
+ */
+ public void addBefore(Instruction newInstruction, Instruction existingInstruction) {
+ assert newInstruction.block == null;
+ if (existingInstruction != null) {
+ assert linearScanFinds(existingInstruction);
+ }
+ if (size == 0) {
+ assert existingInstruction == null;
+ head = newInstruction;
+ tail = newInstruction;
+ } else if (existingInstruction == null) {
+ // Add to end.
+ newInstruction.prev = tail;
+ tail.next = newInstruction;
+ tail = newInstruction;
+ } else {
+ Instruction prevInstruction = existingInstruction.prev;
+ newInstruction.prev = prevInstruction;
+ newInstruction.next = existingInstruction;
+ existingInstruction.prev = newInstruction;
+ if (prevInstruction == null) {
+ assert head == existingInstruction;
+ head = newInstruction;
+ } else {
+ prevInstruction.next = newInstruction;
+ }
+ }
+
+ size += 1;
+ newInstruction.block = ownerBlock;
+ ownerBlock.getMetadata().record(newInstruction);
+ }
+
+ /** Adopt all instructions from another list (use this to split blocks). */
+ public void severFrom(Instruction firstInstructionToMove) {
+ assert isEmpty();
+ BasicBlock sourceBlock = firstInstructionToMove.block;
+ InstructionList sourceList = sourceBlock.getInstructions();
+ // So far no need to sever between methods.
+ assert sourceBlock.getMetadata() == ownerBlock.getMetadata();
+
+ head = firstInstructionToMove;
+ tail = sourceList.tail;
+
+ Instruction lastInstructionToRemain = firstInstructionToMove.prev;
+ sourceList.tail = lastInstructionToRemain;
+ if (lastInstructionToRemain == null) {
+ sourceList.head = null;
+ } else {
+ lastInstructionToRemain.next = null;
+ firstInstructionToMove.prev = null;
+ }
+
+ int count = 0;
+ BasicBlock newBlock = ownerBlock;
+ for (Instruction current = firstInstructionToMove; current != null; current = current.next) {
+ count += 1;
+ current.block = newBlock;
+ }
+ size = count;
+ sourceList.size -= count;
+ }
+
+ public void replace(Instruction oldInstruction, Instruction newInstruction) {
+ replace(oldInstruction, newInstruction, null);
+ }
+
+ /**
+ * Replace the oldInstruction with newInstruction.
+ *
+ * <p>Removes in-values from oldInstruction.
+ *
+ * <p>If the current instruction produces an out-value the new instruction must also produce an
+ * out-value, and all uses of the current instructions out-value will be replaced by the new
+ * instructions out-value.
+ *
+ * <p>The debug information of the current instruction will be attached to the new instruction.
+ */
+ public void replace(
+ Instruction target, Instruction newInstruction, AffectedValues affectedValues) {
+ for (Value value : target.inValues()) {
+ value.removeUser(target);
+ }
+ if (target.hasUsedOutValue()) {
+ assert newInstruction.outValue() != null;
+ if (affectedValues != null && !newInstruction.getOutType().equals(target.getOutType())) {
+ target.outValue().addAffectedValuesTo(affectedValues);
+ }
+ target.outValue().replaceUsers(newInstruction.outValue());
+ }
+ target.moveDebugValues(newInstruction);
+ if (!newInstruction.hasPosition()) {
+ newInstruction.setPosition(target.getPosition());
+ }
+
+ addBefore(newInstruction, target);
+ removeIgnoreValues(target);
+ }
+
+ /**
+ * Safe removal function that will insert a DebugLocalRead to take over the debug values if any
+ * are associated with the current instruction.
+ */
+ public void removeOrReplaceByDebugLocalRead(Instruction target) {
+ if (target.getDebugValues().isEmpty()) {
+ removeAndDetachInValues(target);
+ } else {
+ replace(target, new DebugLocalRead());
+ }
+ }
+
+ /**
+ * Remove the given instruction.
+ *
+ * <p>The instruction will be removed and uses of its in-values removed.
+ *
+ * <p>If the current instruction produces an out-value this out value must not have any users.
+ */
+ public void removeAndDetachInValues(Instruction target) {
+ assert target.outValue() == null || !target.outValue().isUsed();
+ removeIgnoreValues(target.detachInValues());
+ }
+
+ /** Removes without doing any validation of in / out values. */
+ public void removeIgnoreValues(Instruction target) {
+ assert linearScanFinds(target);
+ target.block = null;
+ Instruction prev = target.prev;
+ Instruction next = target.next;
+ if (head == target) {
+ head = next;
+ }
+ if (tail == target) {
+ tail = prev;
+ }
+ if (prev != null) {
+ prev.next = next;
+ }
+ if (next != null) {
+ next.prev = prev;
+ }
+ size -= 1;
+ }
+
+ /** Removes all instructions. Instructions removed in this way may not be reused. */
+ public void clear() {
+ head = null;
+ tail = null;
+ size = 0;
+ }
+
+ // Non-assert uses should check instruction.block for containment. */
+ private boolean linearScanFinds(Instruction instruction) {
+ for (Instruction cur = head; cur != null; cur = cur.next) {
+ if (cur == instruction) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public Stream<Instruction> stream() {
+ return StreamSupport.stream(new SpliteratorImpl(), false);
+ }
+
+ @Override
+ public BasicBlockInstructionListIterator iterator() {
+ return new BasicBlockInstructionListIterator(ownerBlock);
+ }
+
+ public BasicBlockInstructionListIterator iterator(Instruction firstInstructionToReturn) {
+ return new BasicBlockInstructionListIterator(ownerBlock, firstInstructionToReturn);
+ }
+
+ private class SpliteratorImpl implements Spliterator<Instruction> {
+ Instruction next = head;
+
+ @Override
+ public boolean tryAdvance(Consumer<? super Instruction> action) {
+ if (next == null) {
+ return false;
+ }
+ action.accept(next);
+ next = next.next;
+ return true;
+ }
+
+ @Override
+ public Spliterator<Instruction> trySplit() {
+ return null;
+ }
+
+ @Override
+ public long estimateSize() {
+ return size;
+ }
+
+ @Override
+ public long getExactSizeIfKnown() {
+ return size;
+ }
+
+ @Override
+ public int characteristics() {
+ return SIZED | DISTINCT | NONNULL;
+ }
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/code/InstructionListIterator.java b/src/main/java/com/android/tools/r8/ir/code/InstructionListIterator.java
index c1e8aa6..b9c54f1 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InstructionListIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InstructionListIterator.java
@@ -98,7 +98,7 @@
next();
}
- /** See {@link #replaceCurrentInstruction(Instruction, Set)}. */
+ /** See {@link #replaceCurrentInstruction(Instruction, AffectedValues)}. */
default void replaceCurrentInstruction(Instruction newInstruction) {
replaceCurrentInstruction(newInstruction, null);
}
@@ -119,7 +119,7 @@
* @param newInstruction the instruction to insert instead of the current.
* @param affectedValues if non-null, all users of the out value will be added to this set.
*/
- void replaceCurrentInstruction(Instruction newInstruction, Set<Value> affectedValues);
+ void replaceCurrentInstruction(Instruction newInstruction, AffectedValues affectedValues);
// Do not show a deprecation warning for InstructionListIterator.remove().
@SuppressWarnings("deprecation")
@@ -229,7 +229,7 @@
void replaceCurrentInstructionWithNullCheck(AppView<?> appView, Value object);
void replaceCurrentInstructionWithStaticGet(
- AppView<?> appView, IRCode code, DexField field, Set<Value> affectedValues);
+ AppView<?> appView, IRCode code, DexField field, AffectedValues affectedValues);
void replaceCurrentInstructionWithThrow(
AppView<?> appView,
diff --git a/src/main/java/com/android/tools/r8/ir/code/LinearFlowInstructionListIterator.java b/src/main/java/com/android/tools/r8/ir/code/LinearFlowInstructionListIterator.java
index 0885e72..99b0a1b 100644
--- a/src/main/java/com/android/tools/r8/ir/code/LinearFlowInstructionListIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/LinearFlowInstructionListIterator.java
@@ -64,7 +64,7 @@
}
@Override
- public void replaceCurrentInstruction(Instruction newInstruction, Set<Value> affectedValues) {
+ public void replaceCurrentInstruction(Instruction newInstruction, AffectedValues affectedValues) {
currentBlockIterator.replaceCurrentInstruction(newInstruction, affectedValues);
}
@@ -133,7 +133,7 @@
@Override
public void replaceCurrentInstructionWithStaticGet(
- AppView<?> appView, IRCode code, DexField field, Set<Value> affectedValues) {
+ AppView<?> appView, IRCode code, DexField field, AffectedValues affectedValues) {
currentBlockIterator.replaceCurrentInstructionWithStaticGet(
appView, code, field, affectedValues);
}
@@ -322,7 +322,7 @@
if (target == null || target.size() < 2) {
return null;
}
- return target.getInstructions().get(target.size() - 2);
+ return target.getLastInstruction().getPrev();
}
@Override
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java
index 2d4b2ee..480be85 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java
@@ -41,6 +41,7 @@
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Inc;
import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.InstructionList;
import com.android.tools.r8.ir.code.InstructionListIterator;
import com.android.tools.r8.ir.code.InvokeDirect;
import com.android.tools.r8.ir.code.JumpInstruction;
@@ -69,7 +70,6 @@
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
-import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
@@ -79,7 +79,6 @@
private static final int PEEPHOLE_OPTIMIZATION_PASSES = 2;
private static final int SUFFIX_SHARING_OVERHEAD = 30;
- private static final int IINC_PATTERN_SIZE = 4;
public final AppView<?> appView;
private final ProgramMethod method;
@@ -234,15 +233,13 @@
Set<UninitializedThisLocalRead> uninitializedThisLocalReads = Sets.newIdentityHashSet();
for (BasicBlock exitBlock : code.blocks) {
if (exitBlock.exit().isThrow() && !exitBlock.hasCatchHandlers()) {
- LinkedList<Instruction> instructions = exitBlock.getInstructions();
- Instruction throwing = instructions.removeLast();
+ InstructionList instructions = exitBlock.getInstructions();
+ Instruction throwing = instructions.getLast();
assert throwing.isThrow();
UninitializedThisLocalRead read = new UninitializedThisLocalRead(code.getThis());
read.setPosition(throwing.getPosition());
uninitializedThisLocalReads.add(read);
- read.setBlock(exitBlock);
- instructions.addLast(read);
- instructions.addLast(throwing);
+ instructions.addBefore(read, throwing);
}
}
return uninitializedThisLocalReads;
@@ -322,7 +319,6 @@
it.previous();
Value constValue = code.createValue(inValue.getType());
Instruction newInstruction = new ConstNumber(constValue, -1);
- newInstruction.setBlock(block);
newInstruction.setPosition(current.getPosition());
it.add(newInstruction);
it.next();
@@ -473,44 +469,43 @@
@SuppressWarnings("ReferenceEquality")
private void rewriteIincPatterns() {
for (BasicBlock block : code.blocks) {
- InstructionListIterator it = block.listIterator(code);
- // Test that we have enough instructions for iinc.
- while (IINC_PATTERN_SIZE <= block.getInstructions().size() - it.nextIndex()) {
- Instruction loadOrConst1 = it.next();
- if (!loadOrConst1.isLoad() && !loadOrConst1.isConstNumber()) {
+ InstructionList instructions = block.getInstructions();
+ for (Instruction ins = instructions.getFirst(); ins != null; ins = ins.getNext()) {
+ boolean isLoad = ins.isLoad();
+ if (!isLoad && !ins.isConstNumber()) {
continue;
}
Load load;
ConstNumber constNumber;
- if (loadOrConst1.isLoad()) {
- load = loadOrConst1.asLoad();
- constNumber = it.next().asConstNumber();
+ Instruction nextInstruction = ins.getNext();
+ if (isLoad) {
+ load = ins.asLoad();
+ constNumber = nextInstruction.asConstNumber();
} else {
- load = it.next().asLoad();
- constNumber = loadOrConst1.asConstNumber();
+ load = nextInstruction.asLoad();
+ constNumber = ins.asConstNumber();
}
- Instruction add = it.next().asAdd();
- Instruction store = it.next().asStore();
- // Reset pointer to load.
- it.previous();
- it.previous();
- it.previous();
- it.previous();
if (load == null
|| constNumber == null
- || add == null
- || store == null
|| constNumber.getOutType() != TypeElement.getInt()) {
- it.next();
+ continue;
+ }
+ Instruction add = nextInstruction.getNext();
+ if (add == null) {
+ break;
+ }
+ Instruction store = add.getNext();
+ if (store == null) {
+ break;
+ }
+ if (!add.isAdd() || !store.isStore()) {
continue;
}
int increment = constNumber.getIntValue();
if (increment < Byte.MIN_VALUE || Byte.MAX_VALUE < increment) {
- it.next();
continue;
}
if (getLocalRegister(load.src()) != getLocalRegister(store.outValue())) {
- it.next();
continue;
}
Position position = add.getPosition();
@@ -519,16 +514,15 @@
|| position != store.getPosition()) {
continue;
}
- it.removeInstructionIgnoreOutValue();
- it.next();
- it.removeInstructionIgnoreOutValue();
- it.next();
- it.removeInstructionIgnoreOutValue();
- it.next();
+
Inc inc = new Inc(store.outValue(), load.inValues().get(0), increment);
inc.setPosition(position);
- inc.setBlock(block);
- it.set(inc);
+ instructions.addBefore(inc, store);
+
+ load.removeIgnoreValues();
+ constNumber.removeIgnoreValues();
+ add.removeIgnoreValues();
+ store.removeIgnoreValues();
}
}
}
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/DexBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/DexBuilder.java
index e9785ee..6f835bd 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/DexBuilder.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/DexBuilder.java
@@ -58,6 +58,7 @@
import com.android.tools.r8.ir.code.If;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.InstructionIterator;
+import com.android.tools.r8.ir.code.InstructionList;
import com.android.tools.r8.ir.code.InstructionListIterator;
import com.android.tools.r8.ir.code.IntSwitch;
import com.android.tools.r8.ir.code.JumpInstruction;
@@ -74,7 +75,6 @@
import com.android.tools.r8.utils.InternalOutputMode;
import com.google.common.collect.BiMap;
import com.google.common.collect.HashBiMap;
-import com.google.common.collect.Lists;
import com.google.common.collect.Sets;
import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
@@ -947,8 +947,7 @@
item = tryItems.get(i);
coalescedTryItems.add(item);
// Trim the range start for non-throwing instructions when starting a new range.
- List<com.android.tools.r8.ir.code.Instruction> instructions = blocksWithHandlers.get(i)
- .getInstructions();
+ InstructionList instructions = blocksWithHandlers.get(i).getInstructions();
for (com.android.tools.r8.ir.code.Instruction insn : instructions) {
if (insn.instructionTypeCanThrow()) {
item.start = getInfo(insn).getOffset();
@@ -1033,10 +1032,9 @@
private int trimEnd(BasicBlock block) {
// Trim the range end for non-throwing instructions when end has been computed.
- List<com.android.tools.r8.ir.code.Instruction> instructions = block.getInstructions();
- for (com.android.tools.r8.ir.code.Instruction insn : Lists.reverse(instructions)) {
- if (insn.instructionTypeCanThrow()) {
- Info info = getInfo(insn);
+ for (Instruction ins = block.getLastInstruction(); ins != null; ins = ins.getPrev()) {
+ if (ins.instructionTypeCanThrow()) {
+ Info info = getInfo(ins);
return info.getOffset() + info.getSize();
}
}
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
index 2c84747..8e0b85a 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
@@ -282,9 +282,8 @@
}
}
- public static class BlockInfo {
-
- BasicBlock block = new BasicBlock();
+ public class BlockInfo {
+ BasicBlock block = new BasicBlock(metadata);
IntSet normalPredecessors = new IntArraySet();
IntSet normalSuccessors = new IntArraySet();
IntSet exceptionalPredecessors = new IntArraySet();
@@ -697,14 +696,13 @@
// Insert definitions for all uninitialized local values.
if (uninitializedDebugLocalValues != null) {
Position position = entryBlock.getPosition();
- InstructionListIterator it = entryBlock.listIterator(metadata);
+ InstructionListIterator it = entryBlock.listIterator();
it.nextUntil(i -> !i.isArgument());
it.previous();
for (List<Value> values : uninitializedDebugLocalValues.values()) {
for (Value value : values) {
if (value.isUsed()) {
Instruction def = new DebugLocalUninitialized(value);
- def.setBlock(entryBlock);
def.setPosition(position);
it.add(def);
}
@@ -797,7 +795,7 @@
return;
}
for (BasicBlock block : blocks) {
- InstructionListIterator it = block.listIterator(metadata);
+ InstructionListIterator it = block.listIterator();
Position current = null;
while (it.hasNext()) {
Instruction instruction = it.next();
@@ -1760,8 +1758,7 @@
}
public void addMoveResult(int dest) {
- List<Instruction> instructions = currentBlock.getInstructions();
- Invoke invoke = instructions.get(instructions.size() - 1).asInvoke();
+ Invoke invoke = currentBlock.getInstructions().getLast().asInvoke();
assert invoke.outValue() == null;
assert invoke.instructionTypeCanThrow();
DexType outType = invoke.getReturnType();
@@ -2410,7 +2407,7 @@
Set<BasicBlock> moveExceptionTargets = Sets.newIdentityHashSet();
catchHandlers.forEach(
(exceptionType, targetOffset) -> {
- BasicBlock header = new BasicBlock();
+ BasicBlock header = new BasicBlock(currentBlock.getMetadata());
header.incrementUnfilledPredecessorCount();
ssaWorklist.add(
new MoveExceptionWorklistItem(
@@ -2669,7 +2666,7 @@
}
private static BasicBlock createSplitEdgeBlock(BasicBlock source, BasicBlock target) {
- BasicBlock splitBlock = new BasicBlock();
+ BasicBlock splitBlock = new BasicBlock(source.getMetadata());
splitBlock.incrementUnfilledPredecessorCount();
splitBlock.getMutablePredecessors().add(source);
splitBlock.getMutableSuccessors().add(target);
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java b/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
index e8b022d..e9b1aa4 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
@@ -1079,7 +1079,7 @@
AffectedValues affectedValues = new AffectedValues();
for (UnusedArgument unusedArgument : unusedArguments) {
InstructionListIterator instructionIterator =
- unusedArgument.getBlock().listIterator(code, unusedArgument);
+ unusedArgument.getBlock().listIterator(code, unusedArgument.getNext());
if (unusedArgument.outValue().hasAnyUsers()) {
// This is an unused argument with a default value. The unused argument is an operand of the
// phi. This use is eliminated after constant propagation + branch pruning. We eliminate the
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/BranchSimplifier.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/BranchSimplifier.java
index 221adce..990257e 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/passes/BranchSimplifier.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/BranchSimplifier.java
@@ -28,6 +28,7 @@
import com.android.tools.r8.ir.code.IfType;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.InstructionIterator;
+import com.android.tools.r8.ir.code.InstructionList;
import com.android.tools.r8.ir.code.InstructionListIterator;
import com.android.tools.r8.ir.code.IntSwitch;
import com.android.tools.r8.ir.code.InvokeStatic;
@@ -525,21 +526,20 @@
ConstNumber cstToUse = trueNumber.isIntegerOne() ? trueNumber : falseNumber;
BasicBlock phiBlock = phi.getBlock();
Position phiPosition = phiBlock.getPosition();
- int insertIndex = 0;
+ InstructionList instructions = phiBlock.getInstructions();
+ Instruction prevHead = instructions.getFirst();
if (cstToUse.getBlock() == trueBlock || cstToUse.getBlock() == falseBlock) {
// The constant belongs to the block to remove, create a new one.
cstToUse = ConstNumber.copyOf(code, cstToUse);
- cstToUse.setBlock(phiBlock);
cstToUse.setPosition(phiPosition);
- phiBlock.getInstructions().add(insertIndex++, cstToUse);
+ instructions.addBefore(cstToUse, prevHead);
}
phi.replaceUsers(newOutValue);
Instruction newInstruction =
Xor.create(NumericType.INT, newOutValue, testValue, cstToUse.outValue());
- newInstruction.setBlock(phiBlock);
// The xor is replacing a phi so it does not have an actual position.
newInstruction.setPosition(phiPosition);
- phiBlock.listIterator(code, insertIndex).add(newInstruction);
+ instructions.addBefore(newInstruction, prevHead);
deadPhis++;
}
}
@@ -565,7 +565,7 @@
int instructionSize = b.getInstructions().size();
if (b.exit().isGoto() && (instructionSize == 2 || instructionSize == 3)) {
- Instruction constInstruction = b.getInstructions().get(instructionSize - 2);
+ Instruction constInstruction = b.getInstructions().getLast().getPrev();
if (constInstruction.isConstNumber()) {
if (!constInstruction.asConstNumber().isIntegerOne()
&& !constInstruction.asConstNumber().isIntegerZero()) {
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/DexConstantOptimizer.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/DexConstantOptimizer.java
index a213f7f..2bb1a5a 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/passes/DexConstantOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/DexConstantOptimizer.java
@@ -143,7 +143,7 @@
ConstNumber newConstant =
ConstNumber.copyOf(code, constValue.definition.asConstNumber());
newConstant.setPosition(currentInstruction.getPosition());
- newConstant.setBlock(currentInstruction.getBlock());
+ currentInstruction.getBlock();
currentInstruction.replaceValue(constValue, newConstant.outValue());
constValue.removeUser(currentInstruction);
instructionIterator.previous();
@@ -274,9 +274,7 @@
for (Instruction user : constantValue.uniqueUsers()) {
ConstNumber newCstNum = ConstNumber.copyOf(code, constNumber);
newCstNum.setPosition(user.getPosition());
- InstructionListIterator iterator = user.getBlock().listIterator(code, user);
- iterator.previous();
- iterator.add(newCstNum);
+ user.getBlock().getInstructions().addBefore(newCstNum, user);
user.replaceValue(constantValue, newCstNum.outValue());
}
constantValue.clearUsers();
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/FilledNewArrayRewriter.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/FilledNewArrayRewriter.java
index e408515..f2f808e 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/passes/FilledNewArrayRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/FilledNewArrayRewriter.java
@@ -517,14 +517,13 @@
assert !instructionIterator.getBlock().hasCatchHandlers();
for (Value inValue : copy.asNewArrayFilled().inValues()) {
instructionIterator.add(inValue.getDefinition());
- inValue.getDefinition().setBlock(instructionIterator.getBlock());
+ inValue.getDefinition();
inValue.getDefinition().setPosition(newArrayEmpty.getPosition());
}
} else {
assert false;
return elementValue;
}
- copy.setBlock(instructionIterator.getBlock());
copy.setPosition(newArrayEmpty.getPosition());
instructionIterator.add(copy);
addToRemove(elementValue.getDefinition());
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/NaturalIntLoopRemover.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/NaturalIntLoopRemover.java
index 1e327f8..69fb225 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/passes/NaturalIntLoopRemover.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/NaturalIntLoopRemover.java
@@ -413,11 +413,11 @@
private void patchControlFlow(IRCode code, BasicBlock comparisonBlock) {
assert loopExit.getPhis().isEmpty(); // Edges should be split.
- comparisonBlock.replaceLastInstruction(new Goto(loopBodyEntry), code);
+ comparisonBlock.replaceLastInstruction(new Goto(), code);
comparisonBlock.removeSuccessor(loopExit);
backPredecessor.replaceSuccessor(comparisonBlock, loopExit);
- backPredecessor.replaceLastInstruction(new Goto(loopExit), code);
+ backPredecessor.replaceLastInstruction(new Goto(), code);
comparisonBlock.removePredecessor(backPredecessor);
loopExit.replacePredecessor(comparisonBlock, backPredecessor);
}
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/ParentConstructorHoistingCodeRewriter.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/ParentConstructorHoistingCodeRewriter.java
index 43d249f..7b74732 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/passes/ParentConstructorHoistingCodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/ParentConstructorHoistingCodeRewriter.java
@@ -23,7 +23,6 @@
import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.TraversalContinuation;
import com.android.tools.r8.utils.WorkList;
-import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterables;
import java.util.ArrayDeque;
import java.util.Deque;
@@ -96,15 +95,14 @@
return;
}
// Change the instruction order and continue the hoisting.
- List<Instruction> newInstructionOrder =
- ImmutableList.<Instruction>builderWithExpectedSize(constants.size() + 2)
- .addAll(constants)
- .add(invoke)
- .add(previousInstruction)
- .build();
- instructionIterator.next();
- instructionIterator.set(newInstructionOrder);
- IteratorUtils.skip(instructionIterator, -newInstructionOrder.size() - 1);
+ int numInstructions = constants.size() + 2;
+ for (int i = 0; i < numInstructions; ++i) {
+ instructionIterator.next().removeIgnoreValues();
+ }
+ instructionIterator.addAll(constants);
+ instructionIterator.add(invoke);
+ instructionIterator.add(previousInstruction);
+ IteratorUtils.skip(instructionIterator, -numInstructions);
}
}
@@ -121,8 +119,10 @@
}
// Remove the constants and the invoke from the block.
- constants.forEach(constant -> block.getInstructions().removeFirst());
- block.getInstructions().removeFirst();
+ int numToRemove = constants.size() + 1;
+ for (int i = 0; i < numToRemove; ++i) {
+ block.entry().removeIgnoreValues();
+ }
// Add the constants and the invoke before the exit instruction in the predecessor block.
InstructionListIterator predecessorInstructionIterator =
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/RedundantConstNumberRemover.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/RedundantConstNumberRemover.java
index f031b5c..07b007c 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/passes/RedundantConstNumberRemover.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/RedundantConstNumberRemover.java
@@ -103,11 +103,10 @@
if (ifInstruction.isZeroTest()) {
changed |=
- replaceDominatedConstNumbers(0, lhs, trueTarget, constantsByValue, code, dominatorTree);
+ replaceDominatedConstNumbers(0, lhs, trueTarget, constantsByValue, dominatorTree);
if (lhs.knownToBeBoolean()) {
changed |=
- replaceDominatedConstNumbers(
- 1, lhs, falseTarget, constantsByValue, code, dominatorTree);
+ replaceDominatedConstNumbers(1, lhs, falseTarget, constantsByValue, dominatorTree);
}
} else {
assert rhs != null;
@@ -119,7 +118,6 @@
rhs,
trueTarget,
constantsByValue,
- code,
dominatorTree);
if (lhs.knownToBeBoolean() && rhs.knownToBeBoolean()) {
changed |=
@@ -128,7 +126,6 @@
rhs,
falseTarget,
constantsByValue,
- code,
dominatorTree);
}
} else {
@@ -140,7 +137,6 @@
lhs,
trueTarget,
constantsByValue,
- code,
dominatorTree);
if (lhs.knownToBeBoolean() && rhs.knownToBeBoolean()) {
changed |=
@@ -149,7 +145,6 @@
lhs,
falseTarget,
constantsByValue,
- code,
dominatorTree);
}
}
@@ -202,7 +197,6 @@
Value newValue,
BasicBlock dominator,
LazyBox<Long2ReferenceMap<List<ConstNumber>>> constantsByValueSupplier,
- IRCode code,
LazyBox<DominatorTree> dominatorTree) {
if (newValue.hasLocalInfo()) {
// We cannot replace a constant with a value that has local info, because that could change
@@ -254,7 +248,7 @@
if (dominatorTree.computeIfAbsent().dominatedBy(block, dominator)) {
if (newValue.getType().lessThanOrEqual(value.getType(), appView)) {
value.replaceUsers(newValue);
- block.listIterator(code, constNumber).removeOrReplaceByDebugLocalRead();
+ constNumber.removeOrReplaceByDebugLocalRead();
constantWithValueIterator.remove();
changed = true;
} else if (value.getType().isNullType()) {
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/StringSwitchRemover.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/StringSwitchRemover.java
index 74fa808..4eb842c 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/passes/StringSwitchRemover.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/StringSwitchRemover.java
@@ -280,7 +280,7 @@
newBlocksWithStrings.add(newBlock);
if (previous == null) {
// Replace the string-switch instruction by a goto instruction.
- block.exit().replace(new Goto(newBlock), code);
+ block.exit().replace(new Goto(), code);
block.link(newBlock);
} else {
// Set the fallthrough block for the previously added if-instruction.
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/SwitchCaseEliminator.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/SwitchCaseEliminator.java
index 4a1a1d4..5b95f17 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/passes/SwitchCaseEliminator.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/SwitchCaseEliminator.java
@@ -23,7 +23,6 @@
class SwitchCaseEliminator {
private final BasicBlock block;
- private final BasicBlock defaultTarget;
private final InstructionListIterator iterator;
private final Switch theSwitch;
@@ -35,7 +34,6 @@
SwitchCaseEliminator(Switch theSwitch, InstructionListIterator iterator) {
this.block = theSwitch.getBlock();
- this.defaultTarget = theSwitch.fallthroughBlock();
this.iterator = iterator;
this.theSwitch = theSwitch;
}
@@ -147,8 +145,7 @@
private void replaceSwitchByGoto() {
assert !hasAlwaysHitCase() || alwaysHitTarget != null;
- BasicBlock target = hasAlwaysHitCase() ? alwaysHitTarget : defaultTarget;
- iterator.replaceCurrentInstruction(new Goto(target));
+ iterator.replaceCurrentInstruction(new Goto());
}
private void replaceSwitchByOptimizedSwitch(
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/TrivialCheckCastAndInstanceOfRemover.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/TrivialCheckCastAndInstanceOfRemover.java
index 4a2d298..3b1d253 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/passes/TrivialCheckCastAndInstanceOfRemover.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/TrivialCheckCastAndInstanceOfRemover.java
@@ -115,7 +115,7 @@
typeAnalysis -> typeAnalysis.setKeepRedundantBlocksAfterAssumeRemoval(true));
}
if (block.size() != blockSizeBeforeAssumeRemoval) {
- it = previous != null ? block.listIterator(code, previous) : block.listIterator(code);
+ it = block.listIterator(code, previous != null ? previous.getNext() : block.entry());
}
}
} else if (current.isInstanceOf()) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/AssertionsRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/AssertionsRewriter.java
index d002613..92fd99c 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/AssertionsRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/AssertionsRewriter.java
@@ -495,7 +495,7 @@
dexItemFactory.createMethod(configuration.getAssertionHandler()),
null,
ImmutableList.of(throwInstruction.exception())));
- Goto gotoBlockAfterAssertion = new Goto(throwingBlock);
+ Goto gotoBlockAfterAssertion = new Goto();
gotoBlockAfterAssertion.setPosition(throwInstruction.getPosition());
throwingBlock.link(throwSuccessorAfterHandler.get(throwInstruction));
iterator.add(gotoBlockAfterAssertion);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/BasicBlockInstructionsEquivalence.java b/src/main/java/com/android/tools/r8/ir/optimize/BasicBlockInstructionsEquivalence.java
index b57fd9b..cf599a6 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/BasicBlockInstructionsEquivalence.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/BasicBlockInstructionsEquivalence.java
@@ -7,12 +7,12 @@
import com.android.tools.r8.ir.code.CatchHandlers;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.InstructionList;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.conversion.MethodConversionOptions;
import com.android.tools.r8.ir.regalloc.RegisterAllocator;
import com.google.common.base.Equivalence;
import java.util.Arrays;
-import java.util.Iterator;
import java.util.List;
class BasicBlockInstructionsEquivalence extends Equivalence<BasicBlock> {
@@ -30,19 +30,19 @@
}
private boolean hasIdenticalInstructions(BasicBlock first, BasicBlock second) {
- List<Instruction> instructions0 = first.getInstructions();
- List<Instruction> instructions1 = second.getInstructions();
+ InstructionList instructions0 = first.getInstructions();
+ InstructionList instructions1 = second.getInstructions();
if (instructions0.size() != instructions1.size()) {
return false;
}
- Iterator<Instruction> it0 = instructions0.iterator();
- Iterator<Instruction> it1 = instructions1.iterator();
- while (it0.hasNext()) {
- Instruction i0 = it0.next();
- Instruction i1 = it1.next();
+ Instruction i0 = instructions0.getFirstOrNull();
+ Instruction i1 = instructions1.getFirstOrNull();
+ while (i0 != null) {
if (!i0.identicalAfterRegisterAllocation(i1, allocator, conversionOptions)) {
return false;
}
+ i0 = i0.getNext();
+ i1 = i1.getNext();
}
if (!allocator.hasEqualTypesAtEntry(first, second)) {
@@ -93,21 +93,21 @@
}
private int computeHash(BasicBlock basicBlock) {
- List<Instruction> instructions = basicBlock.getInstructions();
+ InstructionList instructions = basicBlock.getInstructions();
int hash = instructions.size();
int i = 0;
- for (Instruction instruction : instructions) {
+ for (Instruction inst = instructions.getFirstOrNull(); inst != null; inst = inst.getNext()) {
if (++i > MAX_HASH_INSTRUCTIONS) {
break;
}
int hashPart = 0;
- if (instruction.outValue() != null && instruction.outValue().needsRegister()) {
- hashPart += allocator.getRegisterForValue(instruction.outValue(), instruction.getNumber());
+ if (inst.outValue() != null && inst.outValue().needsRegister()) {
+ hashPart += allocator.getRegisterForValue(inst.outValue(), inst.getNumber());
}
- for (Value inValue : instruction.inValues()) {
+ for (Value inValue : inst.inValues()) {
hashPart = hashPart << 4;
if (inValue.needsRegister()) {
- hashPart += allocator.getRegisterForValue(inValue, instruction.getNumber());
+ hashPart += allocator.getRegisterForValue(inValue, inst.getNumber());
}
}
hash = hash * 3 + hashPart;
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 0e8ca85..f204dae 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
@@ -14,7 +14,6 @@
import com.android.tools.r8.ir.code.DebugLocalsChange;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Instruction;
-import com.android.tools.r8.ir.code.InstructionIterator;
import com.android.tools.r8.ir.code.InstructionListIterator;
import com.android.tools.r8.ir.code.Move;
import com.android.tools.r8.ir.code.Position;
@@ -259,15 +258,13 @@
IntSet clobberedRegisters = new IntOpenHashSet();
// Backwards instruction scan collecting the registers used by actual instructions.
boolean inEntrySpillMoves = false;
- InstructionIterator it = block.iterator(block.getInstructions().size());
- while (it.hasPrevious()) {
- Instruction instruction = it.previous();
- if (instruction == postSpillLocalsChange) {
+ for (Instruction ins = block.getLastInstruction(); ins != null; ins = ins.getPrev()) {
+ if (ins == postSpillLocalsChange) {
inEntrySpillMoves = true;
}
// If this is a move in the block-entry spill moves check if it is unneeded.
- if (inEntrySpillMoves && instruction.isMove()) {
- Move move = instruction.asMove();
+ if (inEntrySpillMoves && ins.isMove()) {
+ Move move = ins.asMove();
int dst = allocator.getRegisterForValue(move.dest(), move.getNumber());
int src = allocator.getRegisterForValue(move.src(), move.getNumber());
if (!usedRegisters.contains(dst) && !clobberedRegisters.contains(src)) {
@@ -275,18 +272,17 @@
continue;
}
}
- if (instruction.outValue() != null && instruction.outValue().needsRegister()) {
- int register =
- allocator.getRegisterForValue(instruction.outValue(), instruction.getNumber());
+ if (ins.outValue() != null && ins.outValue().needsRegister()) {
+ int register = allocator.getRegisterForValue(ins.outValue(), ins.getNumber());
// The register is defined anew, so uses before this are on distinct values.
usedRegisters.remove(register);
// Mark it clobbered to avoid any uses in locals after this point to become invalid.
clobberedRegisters.add(register);
}
- if (!instruction.inValues().isEmpty()) {
- for (Value inValue : instruction.inValues()) {
+ if (!ins.inValues().isEmpty()) {
+ for (Value inValue : ins.inValues()) {
if (inValue.needsRegister()) {
- int register = allocator.getRegisterForValue(inValue, instruction.getNumber());
+ int register = allocator.getRegisterForValue(inValue, ins.getNumber());
// Record the register as being used.
usedRegisters.add(register);
}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/ConstantCanonicalizer.java b/src/main/java/com/android/tools/r8/ir/optimize/ConstantCanonicalizer.java
index 7a18075..a4e941c 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/ConstantCanonicalizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/ConstantCanonicalizer.java
@@ -252,10 +252,7 @@
for (Instruction oldInstruction : entry.getValue()) {
if (oldInstruction != newInstruction) {
oldInstruction.outValue().replaceUsers(newInstruction.outValue());
- oldInstruction
- .getBlock()
- .listIterator(code, oldInstruction)
- .removeOrReplaceByDebugLocalRead();
+ oldInstruction.removeOrReplaceByDebugLocalRead();
// If the removed instruction is an insertion point for another constant, then record that
// the constant should instead be inserted at the point where the removed instruction has
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java b/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
index d73ab2a..add17fb 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
@@ -660,7 +660,7 @@
code.prepareBlocksForCatchHandlers();
// Create a block for holding the monitor-exit instruction.
- BasicBlock monitorExitBlock = new BasicBlock();
+ BasicBlock monitorExitBlock = new BasicBlock(code.metadata());
monitorExitBlock.setNumber(code.getNextBlockNumber());
// For each block in the code that may throw, add a catch-all handler targeting the
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/PeepholeOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/PeepholeOptimizer.java
index 84fe7f8..3f22277 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/PeepholeOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/PeepholeOptimizer.java
@@ -11,7 +11,7 @@
import com.android.tools.r8.ir.code.Goto;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Instruction;
-import com.android.tools.r8.ir.code.InstructionIterator;
+import com.android.tools.r8.ir.code.InstructionList;
import com.android.tools.r8.ir.code.InstructionListIterator;
import com.android.tools.r8.ir.code.Position;
import com.android.tools.r8.ir.code.Value;
@@ -26,7 +26,6 @@
import java.util.Collection;
import java.util.HashMap;
import java.util.IdentityHashMap;
-import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
@@ -157,17 +156,15 @@
// Remove the instruction from the normal successors.
for (BasicBlock normalSuccessor : normalSuccessors) {
- normalSuccessor.getInstructions().removeFirst();
+ normalSuccessor.entry().removeIgnoreValues();
}
// Move the instruction into the predecessor.
if (instruction.isJumpInstruction()) {
// Replace jump instruction in predecessor with the jump instruction from the normal
// successors.
- LinkedList<Instruction> instructions = block.getInstructions();
- instructions.removeLast();
- instructions.add(instruction);
- instruction.setBlock(block);
+ block.getLastInstruction().removeIgnoreValues();
+ block.getInstructions().addLast(instruction);
// Take a copy of the old normal successors before performing a destructive update.
List<BasicBlock> oldNormalSuccessors = new ArrayList<>(normalSuccessors);
@@ -191,8 +188,7 @@
}
} else {
// Insert instruction before the jump instruction in the predecessor.
- block.getInstructions().listIterator(block.getInstructions().size() - 1).add(instruction);
- instruction.setBlock(block);
+ block.getInstructions().addBefore(instruction, block.getLastInstruction());
// Update locals-at-entry if needed.
if (instruction.isDebugLocalsChange()) {
@@ -238,7 +234,7 @@
BasicBlock normalExit = null;
List<BasicBlock> normalExits = code.computeNormalExitBlocks();
if (normalExits.size() > 1) {
- normalExit = new BasicBlock();
+ normalExit = new BasicBlock(code.metadata());
normalExit.getMutablePredecessors().addAll(normalExits);
blocks = new ArrayList<>(code.blocks);
blocks.add(normalExit);
@@ -259,8 +255,7 @@
if (pred.exit().isGoto()
&& pred.getSuccessors().size() == 1
&& pred.getInstructions().size() > 1) {
- List<Instruction> instructions = pred.getInstructions();
- Instruction lastInstruction = instructions.get(instructions.size() - 2);
+ Instruction lastInstruction = pred.getLastInstruction().getPrev();
List<BasicBlock> value = lastInstructionToBlocks.computeIfAbsent(
equivalence.wrap(lastInstruction), (k) -> new ArrayList<>());
value.add(pred);
@@ -297,7 +292,7 @@
}
BasicBlock newBlock =
createAndInsertBlockForSuffix(
- code.getNextBlockNumber(),
+ code,
commonSuffixSize,
predsWithSameLastInstruction,
block == normalExit ? null : block,
@@ -318,7 +313,7 @@
}
private static BasicBlock createAndInsertBlockForSuffix(
- int blockNumber,
+ IRCode code,
int suffixSize,
List<BasicBlock> preds,
BasicBlock successorBlock,
@@ -326,49 +321,57 @@
BasicBlock first = preds.get(0);
assert (successorBlock != null && first.exit().isGoto())
|| (successorBlock == null && first.exit().isReturn());
- BasicBlock newBlock = new BasicBlock();
- newBlock.setNumber(blockNumber);
- InstructionIterator from = first.iterator(first.getInstructions().size());
+ BasicBlock newBlock = new BasicBlock(code.metadata());
+ newBlock.setNumber(code.getNextBlockNumber());
Int2ReferenceMap<DebugLocalInfo> newBlockEntryLocals = null;
if (first.getLocalsAtEntry() != null) {
newBlockEntryLocals = new Int2ReferenceOpenHashMap<>(first.getLocalsAtEntry());
int prefixSize = first.getInstructions().size() - suffixSize;
- InstructionIterator it = first.iterator();
+ Instruction instruction = first.entry();
for (int i = 0; i < prefixSize; i++) {
- Instruction instruction = it.next();
if (instruction.isDebugLocalsChange()) {
instruction.asDebugLocalsChange().apply(newBlockEntryLocals);
}
+ instruction = instruction.getNext();
}
}
allocator.addNewBlockToShareIdenticalSuffix(newBlock, suffixSize, preds);
boolean movedThrowingInstruction = false;
+ Instruction instruction = first.getLastInstruction();
for (int i = 0; i < suffixSize; i++) {
- Instruction instruction = from.previous();
movedThrowingInstruction = movedThrowingInstruction || instruction.instructionTypeCanThrow();
- newBlock.getInstructions().addFirst(instruction);
- instruction.setBlock(newBlock);
+ instruction = instruction.getPrev();
}
+ newBlock
+ .getInstructions()
+ .severFrom(instruction == null ? first.entry() : instruction.getNext());
if (movedThrowingInstruction && first.hasCatchHandlers()) {
newBlock.transferCatchHandlers(first);
}
+
for (BasicBlock pred : preds) {
- Position lastPosition = pred.getPosition();
- LinkedList<Instruction> instructions = pred.getInstructions();
- for (int i = 0; i < suffixSize; i++) {
- instructions.removeLast();
+ Position lastPosition;
+ InstructionList instructions = pred.getInstructions();
+ if (pred == first) {
+ // Already removed from first via severFrom().
+ lastPosition = newBlock.getPosition();
+ } else {
+ lastPosition = pred.getPosition();
+ for (int i = 0; i < suffixSize; i++) {
+ instructions.removeIgnoreValues(instructions.getLast());
+ }
}
- for (Instruction instruction : pred.getInstructions()) {
- if (instruction.getPosition().isSome()) {
- lastPosition = instruction.getPosition();
+ for (Instruction ins = instructions.getLastOrNull(); ins != null; ins = ins.getPrev()) {
+ if (ins.getPosition().isSome()) {
+ lastPosition = ins.getPosition();
+ break;
}
}
Goto jump = new Goto();
- jump.setBlock(pred);
jump.setPosition(lastPosition);
- instructions.add(jump);
+ instructions.addLast(jump);
newBlock.getMutablePredecessors().add(pred);
if (successorBlock != null) {
pred.replaceSuccessor(successorBlock, newBlock);
@@ -411,15 +414,15 @@
if (!Objects.equals(localsAtBlockExit(block0), localsAtBlockExit(block1))) {
return 0;
}
- InstructionIterator it0 = block0.iterator(block0.getInstructions().size());
- InstructionIterator it1 = block1.iterator(block1.getInstructions().size());
+ Instruction i0 = block0.getLastInstruction();
+ Instruction i1 = block1.getLastInstruction();
int suffixSize = 0;
- while (it0.hasPrevious() && it1.hasPrevious()) {
- Instruction i0 = it0.previous();
- Instruction i1 = it1.previous();
+ while (i0 != null && i1 != null) {
if (!i0.identicalAfterRegisterAllocation(i1, allocator, code.getConversionOptions())) {
return suffixSize;
}
+ i0 = i0.getPrev();
+ i1 = i1.getPrev();
suffixSize++;
}
return suffixSize;
@@ -464,9 +467,8 @@
assert !otherPred.getPredecessors().contains(pred);
otherPred.getMutablePredecessors().add(pred);
Goto exit = new Goto();
- exit.setBlock(pred);
exit.setPosition(otherPred.getPosition());
- pred.getInstructions().add(exit);
+ pred.getInstructions().addLast(exit);
} else {
blockToIndex.put(wrapper, predIndex);
}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/PhiOptimizations.java b/src/main/java/com/android/tools/r8/ir/optimize/PhiOptimizations.java
index 9a5e3b9..ec3a5a4 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/PhiOptimizations.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/PhiOptimizations.java
@@ -7,7 +7,6 @@
import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Instruction;
-import com.android.tools.r8.ir.code.InstructionIterator;
import com.android.tools.r8.ir.code.Load;
import com.android.tools.r8.ir.code.Phi;
import com.android.tools.r8.ir.code.Store;
@@ -86,10 +85,8 @@
private static int getStackHeightAtInstructionBackwards(Instruction instruction) {
int stackHeight = 0;
BasicBlock block = instruction.getBlock();
- InstructionIterator it = block.iterator(block.getInstructions().size() - 1);
- while (it.hasPrevious()) {
- Instruction current = it.previous();
- if (current == instruction) {
+ for (Instruction ins = block.exit().getPrev(); ins != null; ins = ins.getPrev()) {
+ if (ins == instruction) {
break;
}
stackHeight -= PeepholeHelper.numberOfValuesPutOnStack(instruction);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/RuntimeWorkaroundCodeRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/RuntimeWorkaroundCodeRewriter.java
index bcb57ce..06f3c5f 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/RuntimeWorkaroundCodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/RuntimeWorkaroundCodeRewriter.java
@@ -65,7 +65,6 @@
// Split out the last recursive call in its own block.
InstructionListIterator splitIterator =
lastSelfRecursiveCall.getBlock().listIterator(code, lastSelfRecursiveCall);
- splitIterator.previous();
BasicBlock newBlock = splitIterator.split(code, 1);
// Generate rethrow block.
DexType guard = appView.dexItemFactory().throwableType;
@@ -251,7 +250,6 @@
&& target.getNormalPredecessors().size() > 1
&& target.getNormalSuccessors().size() > 1) {
Instruction fixit = new AlwaysMaterializingNop();
- fixit.setBlock(handler);
fixit.setPosition(handler.getPosition());
handler.getInstructions().addFirst(fixit);
}
@@ -362,12 +360,10 @@
// Forced definition of const-zero
Value fixitValue = code.createValue(TypeElement.getInt());
Instruction fixitDefinition = new AlwaysMaterializingDefinition(fixitValue);
- fixitDefinition.setBlock(addBefore.getBlock());
fixitDefinition.setPosition(addBefore.getPosition());
it.add(fixitDefinition);
// Forced user of the forced definition to ensure it has a user and thus live range.
Instruction fixitUser = new AlwaysMaterializingUser(fixitValue);
- fixitUser.setBlock(addBefore.getBlock());
fixitUser.setPosition(addBefore.getPosition());
it.add(fixitUser);
}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/FieldValueHelper.java b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/FieldValueHelper.java
index 0e185da..a7cf6e1 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/FieldValueHelper.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/FieldValueHelper.java
@@ -14,7 +14,6 @@
import com.android.tools.r8.ir.code.ConstNumber;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Instruction;
-import com.android.tools.r8.ir.code.InstructionIterator;
import com.android.tools.r8.ir.code.InstructionListIterator;
import com.android.tools.r8.ir.code.Phi;
import com.android.tools.r8.ir.code.Phi.RegisterReadType;
@@ -125,14 +124,9 @@
@SuppressWarnings("ReferenceEquality")
private Value getValueDefinedInTheBlock(BasicBlock block, Instruction stopAt) {
- InstructionIterator iterator =
- stopAt == null ? block.iterator(block.getInstructions().size()) : block.iterator(stopAt);
-
Instruction valueProducingInsn = null;
- while (iterator.hasPrevious()) {
- Instruction instruction = iterator.previous();
- assert instruction != null;
-
+ Instruction instruction = stopAt != null ? stopAt : block.getLastInstruction();
+ do {
if (instruction == root
|| (instruction.isInstancePut()
&& instruction.asInstancePut().getField() == field
@@ -140,7 +134,8 @@
valueProducingInsn = instruction;
break;
}
- }
+ instruction = instruction.getPrev();
+ } while (instruction != null);
if (valueProducingInsn == null) {
return null;
@@ -151,7 +146,7 @@
assert root == valueProducingInsn;
if (defaultValue == null) {
- InstructionListIterator it = block.listIterator(code, root);
+ InstructionListIterator it = block.listIterator(code, root.getNext());
// If we met newInstance it means that default value is supposed to be used.
if (field.type.isPrimitiveType()) {
defaultValue =
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/InlineCandidateProcessor.java b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/InlineCandidateProcessor.java
index 403719e..da709f6 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/InlineCandidateProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/InlineCandidateProcessor.java
@@ -36,7 +36,6 @@
import com.android.tools.r8.ir.code.AliasedValueConfiguration;
import com.android.tools.r8.ir.code.AssumeAndCheckCastAliasedValueConfiguration;
import com.android.tools.r8.ir.code.BasicBlock;
-import com.android.tools.r8.ir.code.BasicBlockInstructionListIterator;
import com.android.tools.r8.ir.code.BasicBlockIterator;
import com.android.tools.r8.ir.code.CheckCast;
import com.android.tools.r8.ir.code.IRCode;
@@ -634,7 +633,7 @@
if (user.isInstanceOf()) {
InstanceOf instanceOf = user.asInstanceOf();
InstructionListIterator instructionIterator =
- user.getBlock().listIterator(code, instanceOf);
+ user.getBlock().listIterator(code, instanceOf.getNext());
instructionIterator.replaceCurrentInstructionWithConstBoolean(
code, appView.appInfo().isSubtype(eligibleClass.getType(), instanceOf.type()));
continue;
@@ -802,8 +801,7 @@
affectedValues.addAll(newValue.affectedValues());
}
if (replacement != null) {
- BasicBlockInstructionListIterator it = fieldRead.getBlock().listIterator(code, fieldRead);
- it.replaceCurrentInstruction(replacement, affectedValues);
+ fieldRead.replace(replacement, affectedValues);
} else {
removeInstruction(fieldRead);
}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumValueOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumValueOptimizer.java
index 8b566cf..5452d6e 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumValueOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumValueOptimizer.java
@@ -296,8 +296,7 @@
}
if (ordinalToTargetMap.isEmpty()) {
- switchInsn.replace(
- Goto.builder().setTarget(block.getUniqueNormalSuccessor()).build(), code);
+ switchInsn.replace(new Goto(), code);
} else {
int[] keys = ordinalToTargetMap.keySet().toIntArray();
Arrays.sort(keys);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/outliner/OutlinerImpl.java b/src/main/java/com/android/tools/r8/ir/optimize/outliner/OutlinerImpl.java
index caf6e7e..0a54d91 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/outliner/OutlinerImpl.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/outliner/OutlinerImpl.java
@@ -1305,16 +1305,12 @@
returnValue = null;
}
Invoke outlineInvoke = new InvokeStatic(outlineMethod, returnValue, in);
- outlineInvoke.setBlock(lastInstruction.getBlock());
+ lastInstruction.getBlock();
outlineInvoke.setPosition(
positionBuilder.hasOutlinePositions()
? positionBuilder.build()
: Position.syntheticNone());
- InstructionListIterator endIterator =
- lastInstruction.getBlock().listIterator(code, lastInstruction);
- Instruction instructionBeforeEnd = endIterator.previous();
- assert instructionBeforeEnd == lastInstruction;
- endIterator.set(outlineInvoke);
+ lastInstruction.replace(outlineInvoke);
if (outlineInvoke.hasOutValue()
&& returnValue.getType().isReferenceType()
&& returnValue.getType().nullability().isDefinitelyNotNull()) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/peepholes/PeepholeHelper.java b/src/main/java/com/android/tools/r8/ir/optimize/peepholes/PeepholeHelper.java
index 5fef766..c0ea809 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/peepholes/PeepholeHelper.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/peepholes/PeepholeHelper.java
@@ -58,18 +58,12 @@
InstructionListIterator it, List<Instruction> instructions) {
assert !instructions.isEmpty();
for (Instruction instruction : instructions) {
+ // Add duplicate users to offset the users being removed by removeOrReplaceByDebugLocalRead().
for (Value inValue : instruction.inValues()) {
inValue.addUser(instruction);
}
+ instruction.removeOrReplaceByDebugLocalRead();
it.add(instruction);
}
- Instruction current = it.nextUntil(i -> i == instructions.get(0));
- for (int i = 0; i < instructions.size(); i++) {
- assert current == instructions.get(i);
- it.removeOrReplaceByDebugLocalRead();
- current = it.next();
- }
- it.previousUntil(i -> i == instructions.get(instructions.size() - 1));
- it.next();
}
}
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java b/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
index 3cc749b..58af88f 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
@@ -354,7 +354,6 @@
while (it.hasNext()) {
Instruction instruction = it.next();
if (instruction.isDebugLocalRead()) {
- instruction.clearDebugValues();
it.remove();
}
}
@@ -3166,9 +3165,9 @@
}
}
LinkedHashSetUtils.addAll(live, phiOperands);
- List<Instruction> instructions = block.getInstructions();
+ int numInstructionsDelta = block.getInstructions().size() * INSTRUCTION_NUMBER_DELTA;
for (Value value : live) {
- int end = block.entry().getNumber() + instructions.size() * INSTRUCTION_NUMBER_DELTA;
+ int end = block.entry().getNumber() + numInstructionsDelta;
// Make sure that phi operands do not overlap the phi live range. The phi operand is
// not live until the next instruction, but only until the gap before the next instruction
// where the phi value takes over.
@@ -3177,10 +3176,8 @@
}
addLiveRange(value, block, end, liveIntervals, code);
}
- InstructionIterator iterator = block.iterator(block.getInstructions().size());
- while (iterator.hasPrevious()) {
- Instruction instruction = iterator.previous();
- Value definition = instruction.outValue();
+ for (Instruction ins = block.getLastInstruction(); ins != null; ins = ins.getPrev()) {
+ Value definition = ins.outValue();
if (definition != null) {
// For instructions that define values which have no use create a live range covering
// the instruction. This will typically be instructions that can have side effects even
@@ -3193,23 +3190,23 @@
addLiveRange(
definition,
block,
- instruction.getNumber() + INSTRUCTION_NUMBER_DELTA - 1,
+ ins.getNumber() + INSTRUCTION_NUMBER_DELTA - 1,
liveIntervals,
code);
- assert !code.getConversionOptions().isGeneratingClassFiles() || instruction.isArgument()
+ assert !code.getConversionOptions().isGeneratingClassFiles() || ins.isArgument()
: "Arguments should be the only potentially unused local in CF";
}
live.remove(definition);
}
- for (Value use : instruction.inValues()) {
+ for (Value use : ins.inValues()) {
if (use.needsRegister()) {
- assert unconstrainedForCf(instruction.maxInValueRegister(), code);
+ assert unconstrainedForCf(ins.maxInValueRegister(), code);
if (!live.contains(use)) {
live.add(use);
- addLiveRange(use, block, instruction.getNumber(), liveIntervals, code);
+ addLiveRange(use, block, ins.getNumber(), liveIntervals, code);
}
if (code.getConversionOptions().isGeneratingDex()) {
- int inConstraint = instruction.maxInValueRegister();
+ int inConstraint = ins.maxInValueRegister();
LiveIntervals useIntervals = use.getLiveIntervals();
// Arguments are always kept in their original, incoming register. For every
// unconstrained use of an argument we therefore use its incoming register.
@@ -3223,11 +3220,9 @@
// it in the argument register, the register allocator would use two registers for the
// argument but in reality only use one.
boolean isUnconstrainedArgumentUse =
- use.isArgument()
- && inConstraint == Constants.U16BIT_MAX
- && !isInvokeRange(instruction);
+ use.isArgument() && inConstraint == Constants.U16BIT_MAX && !isInvokeRange(ins);
if (!isUnconstrainedArgumentUse) {
- useIntervals.addUse(new LiveIntervalsUse(instruction.getNumber(), inConstraint));
+ useIntervals.addUse(new LiveIntervalsUse(ins.getNumber(), inConstraint));
}
}
}
@@ -3239,24 +3234,20 @@
// 'r1 <- check-cast r0' maps to 'move r1, r0; check-cast r1' and when that
// happens r1 could be clobbered on the exceptional edge if r1 initially contained
// a value that is used in the exceptional code.
- if (instruction.instructionTypeCanThrow()) {
+ if (ins.instructionTypeCanThrow()) {
for (Value use : liveAtThrowingInstruction) {
if (use.needsRegister() && !live.contains(use)) {
live.add(use);
addLiveRange(
- use,
- block,
- getLiveRangeEndOnExceptionalFlow(instruction, use),
- liveIntervals,
- code);
+ use, block, getLiveRangeEndOnExceptionalFlow(ins, use), liveIntervals, code);
}
}
}
if (appView.options().debug || code.context().isReachabilitySensitive()) {
// In debug mode, or if the method is reachability sensitive, extend the live range
// to cover the full scope of a local variable (encoded as debug values).
- int number = instruction.getNumber();
- List<Value> sortedDebugValues = new ArrayList<>(instruction.getDebugValues());
+ int number = ins.getNumber();
+ List<Value> sortedDebugValues = new ArrayList<>(ins.getDebugValues());
sortedDebugValues.sort(Value::compareTo);
for (Value use : sortedDebugValues) {
assert use.needsRegister();
diff --git a/src/main/java/com/android/tools/r8/lightir/Lir2IRConverter.java b/src/main/java/com/android/tools/r8/lightir/Lir2IRConverter.java
index 27f4575..fd08861 100644
--- a/src/main/java/com/android/tools/r8/lightir/Lir2IRConverter.java
+++ b/src/main/java/com/android/tools/r8/lightir/Lir2IRConverter.java
@@ -356,7 +356,7 @@
return blocks.computeIfAbsent(
instructionIndex,
k -> {
- BasicBlock block = new BasicBlock();
+ BasicBlock block = new BasicBlock(irMetadata);
block.setNumber(basicBlockNumberGenerator.next());
return block;
});
@@ -424,9 +424,7 @@
int index = toInstructionIndexInIR(peekNextInstructionIndex());
advanceInstructionState();
instruction.setPosition(currentPosition);
- currentBlock.getInstructions().add(instruction);
- irMetadata.record(instruction);
- instruction.setBlock(currentBlock);
+ currentBlock.getInstructions().addLast(instruction);
int[] debugEndIndices = code.getDebugLocalEnds(index);
if (debugEndIndices != null) {
for (int encodedDebugEndIndex : debugEndIndices) {
@@ -471,9 +469,7 @@
// which would otherwise advance the state.
Argument argument = new Argument(dest, currentBlock.size(), isBooleanType);
argument.setPosition(currentPosition);
- currentBlock.getInstructions().add(argument);
- irMetadata.record(argument);
- argument.setBlock(currentBlock);
+ currentBlock.getInstructions().addLast(argument);
return argument;
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FieldReadBeforeWriteDfsAnalysis.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FieldReadBeforeWriteDfsAnalysis.java
index 1fdfb27..36ca4f0 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FieldReadBeforeWriteDfsAnalysis.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FieldReadBeforeWriteDfsAnalysis.java
@@ -23,7 +23,6 @@
import com.android.tools.r8.graph.ProgramField;
import com.android.tools.r8.ir.code.Assume;
import com.android.tools.r8.ir.code.BasicBlock;
-import com.android.tools.r8.ir.code.BasicBlockInstructionIterator;
import com.android.tools.r8.ir.code.CheckCast;
import com.android.tools.r8.ir.code.ConstNumber;
import com.android.tools.r8.ir.code.ConstString;
@@ -142,9 +141,8 @@
}
}
- AnalysisContinuation applyInstructions(BasicBlockInstructionIterator instructionIterator) {
- while (instructionIterator.hasNext()) {
- Instruction instruction = instructionIterator.next();
+ AnalysisContinuation applyInstructions(Instruction instruction) {
+ for (; instruction != null; instruction = instruction.getNext()) {
assert !instruction.hasOutValue() || !isMaybeInstance(instruction.outValue());
AnalysisContinuation continuation;
// TODO(b/339210038): Extend this to many other instructions, such as ConstClass,
@@ -354,11 +352,9 @@
}
addBlockToStack(block);
addInstanceAlias(getNewInstance().outValue());
- BasicBlockInstructionIterator instructionIterator = block.iterator(uniqueConstructorInvoke);
// Start the analysis from the invoke-direct instruction. This is important if we can tell
// that the constructor definitely writes some fields.
- instructionIterator.previous();
- return applyInstructions(instructionIterator).toTraversalContinuation();
+ return applyInstructions(uniqueConstructorInvoke).toTraversalContinuation();
}
}
@@ -379,7 +375,7 @@
}
addBlockToStack(block);
applyPhis(block);
- AnalysisContinuation continuation = applyInstructions(block.iterator());
+ AnalysisContinuation continuation = applyInstructions(block.entry());
assert continuation.isAbortOrContinue();
return TraversalContinuation.breakIf(continuation.isAbort());
}
diff --git a/src/test/java/com/android/tools/r8/cf/TryRangeTestRunner.java b/src/test/java/com/android/tools/r8/cf/TryRangeTestRunner.java
index 21ee0fc..10abbeb 100644
--- a/src/test/java/com/android/tools/r8/cf/TryRangeTestRunner.java
+++ b/src/test/java/com/android/tools/r8/cf/TryRangeTestRunner.java
@@ -120,9 +120,7 @@
add = it.next();
}
it.removeInstructionIgnoreOutValue();
- constNumber.setBlock(tryBlock);
- add.setBlock(tryBlock);
- tryBlock.getInstructions().add(0, add);
- tryBlock.getInstructions().add(0, constNumber);
+ tryBlock.getInstructions().addFirst(add);
+ tryBlock.getInstructions().addFirst(constNumber);
}
}
diff --git a/src/test/java/com/android/tools/r8/ir/SplitBlockTest.java b/src/test/java/com/android/tools/r8/ir/SplitBlockTest.java
index 484aca5..dbbec8e 100644
--- a/src/test/java/com/android/tools/r8/ir/SplitBlockTest.java
+++ b/src/test/java/com/android/tools/r8/ir/SplitBlockTest.java
@@ -18,6 +18,7 @@
import com.android.tools.r8.ir.code.ConstNumber;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.InstructionList;
import com.android.tools.r8.ir.code.InstructionListIterator;
import com.android.tools.r8.ir.code.NumericType;
import com.android.tools.r8.ir.code.Position;
@@ -97,7 +98,8 @@
assertEquals(argumentInstructions, test.countArgumentInstructions());
assertEquals(firstBlockInstructions, block.getInstructions().size());
- assertTrue(!block.getInstructions().get(i).isArgument());
+ InstructionList instructionList = block.getInstructions();
+ assertTrue(!instructionList.getNth(i).isArgument());
InstructionListIterator iterator = test.listIteratorAt(block, i);
BasicBlock newBlock = iterator.split(code);
@@ -132,7 +134,8 @@
assertEquals(argumentInstructions, test.countArgumentInstructions());
assertEquals(firstBlockInstructions, block.getInstructions().size());
- assertTrue(!block.getInstructions().get(i).isArgument());
+ InstructionList instructionList = block.getInstructions();
+ assertTrue(!instructionList.getNth(i).isArgument());
InstructionListIterator iterator = test.listIteratorAt(block, i);
BasicBlock newBlock = iterator.split(code, 1);
@@ -337,7 +340,8 @@
assertEquals(argumentInstructions, test.countArgumentInstructions());
assertEquals(firstBlockInstructions, block.getInstructions().size());
- assertTrue(!block.getInstructions().get(i).isArgument());
+ InstructionList instructionList = block.getInstructions();
+ assertTrue(!instructionList.getNth(i).isArgument());
InstructionListIterator iterator = test.listIteratorAt(block, i);
BasicBlock newBlock = iterator.split(code);
@@ -459,7 +463,8 @@
assertEquals(argumentInstructions, test.countArgumentInstructions());
assertEquals(firstBlockInstructions, block.getInstructions().size());
- assertTrue(!block.getInstructions().get(i).isArgument());
+ InstructionList instructionList = block.getInstructions();
+ assertTrue(!instructionList.getNth(i).isArgument());
InstructionListIterator iterator = test.listIteratorAt(block, i);
BasicBlock newBlock = iterator.split(code);
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/ConstantRemovalTest.java b/src/test/java/com/android/tools/r8/ir/optimize/ConstantRemovalTest.java
index eff9d7a..adc7fb7 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/ConstantRemovalTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/ConstantRemovalTest.java
@@ -87,11 +87,11 @@
//
// Then test that peephole optimization realizes that the last const number
// is needed and the value 10 is *not* still in register 0 at that point.
+ IRMetadata metadata = IRMetadata.unknown();
final NumberGenerator basicBlockNumberGenerator = new NumberGenerator();
- BasicBlock block = new BasicBlock();
+ BasicBlock block = new BasicBlock(metadata);
block.setNumber(basicBlockNumberGenerator.next());
- IRMetadata metadata = IRMetadata.unknown();
Position position = SyntheticPosition.builder().disableMethodCheck().setLine(0).build();
Value v3 = new Value(3, TypeElement.getLong(), null);
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/TrivialGotoEliminationTest.java b/src/test/java/com/android/tools/r8/ir/optimize/TrivialGotoEliminationTest.java
index 997f0e0..275c0e3 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/TrivialGotoEliminationTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/TrivialGotoEliminationTest.java
@@ -69,10 +69,10 @@
// return
final NumberGenerator basicBlockNumberGenerator = new NumberGenerator();
Position position = SyntheticPosition.builder().setLine(0).disableMethodCheck().build();
- BasicBlock block2 = new BasicBlock();
+ BasicBlock block2 = new BasicBlock(metadata);
BasicBlock block0 =
BasicBlock.createGotoBlock(basicBlockNumberGenerator.next(), position, metadata, block2);
- BasicBlock block1 = new BasicBlock();
+ BasicBlock block1 = new BasicBlock(metadata);
block1.setNumber(basicBlockNumberGenerator.next());
block2.setNumber(basicBlockNumberGenerator.next());
block0.setFilledForTesting();
@@ -133,9 +133,9 @@
// goto block3
final NumberGenerator basicBlockNumberGenerator = new NumberGenerator();
Position position = SyntheticPosition.builder().setLine(0).disableMethodCheck().build();
- BasicBlock block0 = new BasicBlock();
+ BasicBlock block0 = new BasicBlock(metadata);
block0.setNumber(basicBlockNumberGenerator.next());
- BasicBlock block2 = new BasicBlock();
+ BasicBlock block2 = new BasicBlock(metadata);
BasicBlock block1 =
BasicBlock.createGotoBlock(basicBlockNumberGenerator.next(), position, metadata);
block2.setNumber(basicBlockNumberGenerator.next());
@@ -144,7 +144,7 @@
block2.add(ret, metadata);
block2.setFilledForTesting();
- BasicBlock block3 = new BasicBlock();
+ BasicBlock block3 = new BasicBlock(metadata);
block3.setNumber(basicBlockNumberGenerator.next());
Instruction instruction = new Goto();
instruction.setPosition(position);
@@ -196,8 +196,8 @@
IRMetadata.unknown(),
MethodConversionOptions.forD8(appView));
new TrivialGotosCollapser(appView).run(code, Timing.empty());
- assertTrue(block0.getInstructions().get(1).isIf());
- assertEquals(block1, block0.getInstructions().get(1).asIf().fallthroughBlock());
+ assertTrue(block0.getInstructions().getFirst().getNext().isIf());
+ assertEquals(block1, block0.getInstructions().getFirst().getNext().asIf().fallthroughBlock());
assertTrue(blocks.containsAll(ImmutableList.of(block0, block1, block2, block3)));
}
}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/classinliner/ClassInlinerPhiDirectUserAfterInlineTest.java b/src/test/java/com/android/tools/r8/ir/optimize/classinliner/ClassInlinerPhiDirectUserAfterInlineTest.java
index 269b2f9..9ef01cc 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/classinliner/ClassInlinerPhiDirectUserAfterInlineTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/classinliner/ClassInlinerPhiDirectUserAfterInlineTest.java
@@ -169,7 +169,7 @@
// and block 4 to have:
// vY : phi(v3, vX)
BasicBlock basicBlock = irCode.blocks.get(0);
- Argument argument = basicBlock.getInstructions().get(0).asArgument();
+ Argument argument = basicBlock.getInstructions().getFirst().asArgument();
assertNotNull(argument);
Value argumentValue = argument.outValue();
@@ -203,7 +203,7 @@
secondPhi.addOperands(ImmutableList.of(argumentValue, firstPhi));
// Replace the invoke to use the phi
- InstanceGet instanceGet = block1.getInstructions().get(0).asInstanceGet();
+ InstanceGet instanceGet = block1.getInstructions().getFirst().asInstanceGet();
assertNotNull(instanceGet);
assertEquals(A.class.getTypeName(), instanceGet.getField().holder.toSourceString());
instanceGet.replaceValue(0, firstPhi);
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/ifs/IfThrowNullPointerExceptionTest.java b/src/test/java/com/android/tools/r8/ir/optimize/ifs/IfThrowNullPointerExceptionTest.java
index b9c24d6..11fb04d 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/ifs/IfThrowNullPointerExceptionTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/ifs/IfThrowNullPointerExceptionTest.java
@@ -102,8 +102,10 @@
assertTrue(entryBlock.getInstructions().getFirst().isArgument());
assertTrue(entryBlock.getInstructions().getLast().isReturn());
- Instruction nullCheckInstruction =
- entryBlock.getInstructions().get(1 + BooleanUtils.intValue(isNPEWithMessage));
+ Instruction nullCheckInstruction = entryBlock.getInstructions().getFirst().getNext();
+ if (isNPEWithMessage) {
+ nullCheckInstruction = nullCheckInstruction.getNext();
+ }
assertFalse(isNPEWithMessage);
assertTrue(nullCheckInstruction.isInvokeVirtual());
assertEquals(
diff --git a/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java b/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java
index ed272e7..fab0924 100644
--- a/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java
+++ b/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java
@@ -56,7 +56,8 @@
}
@Override
- public void replaceCurrentInstruction(Instruction newInstruction, Set<Value> affectedValues) {
+ public void replaceCurrentInstruction(
+ Instruction newInstruction, AffectedValues affectedValues) {
throw new Unimplemented();
}
@@ -121,7 +122,7 @@
@Override
public void replaceCurrentInstructionWithStaticGet(
- AppView<?> appView, IRCode code, DexField field, Set<Value> affectedValues) {
+ AppView<?> appView, IRCode code, DexField field, AffectedValues affectedValues) {
throw new Unimplemented();
}
diff --git a/src/test/java/com/android/tools/r8/smali/CatchSuccessorFallthroughTest.java b/src/test/java/com/android/tools/r8/smali/CatchSuccessorFallthroughTest.java
index 4ce22fc..55b0158 100644
--- a/src/test/java/com/android/tools/r8/smali/CatchSuccessorFallthroughTest.java
+++ b/src/test/java/com/android/tools/r8/smali/CatchSuccessorFallthroughTest.java
@@ -106,8 +106,7 @@
if (defBlock.canThrow()) {
// Found the invoke instruction / block.
assertEquals(2, defBlock.getSuccessors().size());
- assertTrue(
- defBlock.getInstructions().get(defBlock.getInstructions().size() - 2).isInvoke());
+ assertTrue(defBlock.getInstructions().getLast().getPrev().isInvoke());
for (BasicBlock returnPredecessor : block.getPredecessors()) {
if (defBlock.hasCatchSuccessor(returnPredecessor)) {
hasExceptionalPredecessor = true;
