| // Copyright (c) 2018, 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.optimize; |
| |
| import static com.google.common.base.Predicates.alwaysTrue; |
| |
| import com.android.tools.r8.graph.AppInfoWithClassHierarchy; |
| import com.android.tools.r8.graph.AppView; |
| import com.android.tools.r8.graph.DexEncodedField; |
| import com.android.tools.r8.graph.DexEncodedMethod; |
| import com.android.tools.r8.graph.DexField; |
| import com.android.tools.r8.ir.analysis.type.TypeAnalysis; |
| import com.android.tools.r8.ir.analysis.type.TypeElement; |
| import com.android.tools.r8.ir.code.Assume; |
| import com.android.tools.r8.ir.code.Assume.NonNullAssumption; |
| import com.android.tools.r8.ir.code.BasicBlock; |
| import com.android.tools.r8.ir.code.BasicBlockIterator; |
| import com.android.tools.r8.ir.code.DominatorTree; |
| import com.android.tools.r8.ir.code.FieldInstruction; |
| import com.android.tools.r8.ir.code.IRCode; |
| 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.InstructionListIterator; |
| import com.android.tools.r8.ir.code.InvokeMethod; |
| import com.android.tools.r8.ir.code.LazyDominatorTree; |
| import com.android.tools.r8.ir.code.Phi; |
| import com.android.tools.r8.ir.code.Value; |
| import com.android.tools.r8.ir.optimize.info.FieldOptimizationInfo; |
| import com.android.tools.r8.ir.optimize.info.MethodOptimizationInfo; |
| import com.android.tools.r8.utils.Timing; |
| import com.android.tools.r8.utils.TriConsumer; |
| import com.google.common.collect.Sets; |
| import it.unimi.dsi.fastutil.ints.IntArrayList; |
| import it.unimi.dsi.fastutil.ints.IntList; |
| import it.unimi.dsi.fastutil.ints.IntListIterator; |
| import java.util.ArrayList; |
| import java.util.BitSet; |
| import java.util.IdentityHashMap; |
| import java.util.Iterator; |
| import java.util.LinkedHashMap; |
| import java.util.List; |
| import java.util.Map; |
| import java.util.Map.Entry; |
| import java.util.Set; |
| import java.util.function.BiFunction; |
| import java.util.function.BiPredicate; |
| import java.util.function.Predicate; |
| |
| public class AssumeInserter implements Assumer { |
| |
| private final AppView<? extends AppInfoWithClassHierarchy> appView; |
| |
| public AssumeInserter(AppView<? extends AppInfoWithClassHierarchy> appView) { |
| this.appView = appView; |
| } |
| |
| @Override |
| public void insertAssumeInstructions(IRCode code, Timing timing) { |
| insertAssumeInstructionsInBlocks(code, code.listIterator(), alwaysTrue(), timing); |
| } |
| |
| @Override |
| public void insertAssumeInstructionsInBlocks( |
| IRCode code, |
| BasicBlockIterator blockIterator, |
| Predicate<BasicBlock> blockTester, |
| Timing timing) { |
| timing.begin("Insert assume instructions"); |
| internalInsertAssumeInstructionsInBlocks(code, blockIterator, blockTester, timing); |
| timing.end(); |
| } |
| |
| private void internalInsertAssumeInstructionsInBlocks( |
| IRCode code, |
| BasicBlockIterator blockIterator, |
| Predicate<BasicBlock> blockTester, |
| Timing timing) { |
| timing.begin("Part 1: Compute assumed values"); |
| AssumedValues assumedValues = computeAssumedValues(code, blockIterator, blockTester); |
| timing.end(); |
| if (assumedValues.isEmpty()) { |
| return; |
| } |
| |
| timing.begin("Part 2: Remove redundant assume instructions"); |
| removeRedundantAssumeInstructions(assumedValues); |
| timing.end(); |
| |
| timing.begin("Part 3: Compute dominated users"); |
| Map<Instruction, Set<Value>> redundantKeys = |
| computeDominanceForAssumedValues(code, assumedValues); |
| timing.end(); |
| if (assumedValues.isEmpty()) { |
| return; |
| } |
| |
| timing.begin("Part 4: Remove redundant dominated assume instructions"); |
| removeRedundantDominatedAssumeInstructions(assumedValues, redundantKeys); |
| timing.end(); |
| if (assumedValues.isEmpty()) { |
| return; |
| } |
| |
| timing.begin("Part 5: Materialize assume instructions"); |
| materializeAssumeInstructions(code, assumedValues); |
| timing.end(); |
| } |
| |
| private AssumedValues computeAssumedValues( |
| IRCode code, BasicBlockIterator blockIterator, Predicate<BasicBlock> blockTester) { |
| AssumedValues.Builder assumedValuesBuilder = new AssumedValues.Builder(); |
| while (blockIterator.hasNext()) { |
| BasicBlock block = blockIterator.next(); |
| if (blockTester.test(block)) { |
| computeAssumedValuesInBlock(code, blockIterator, block, assumedValuesBuilder); |
| } |
| } |
| return assumedValuesBuilder.build(); |
| } |
| |
| private void computeAssumedValuesInBlock( |
| IRCode code, |
| BasicBlockIterator blockIterator, |
| BasicBlock block, |
| AssumedValues.Builder assumedValuesBuilder) { |
| // Add non-null after |
| // 1) instructions that implicitly indicate receiver/array is not null. |
| // 2) invocations that are guaranteed to return a non-null value. |
| // 3) parameters that are not null after the invocation. |
| // 4) field-get instructions that are guaranteed to read a non-null value. |
| InstructionListIterator instructionIterator = block.listIterator(code); |
| while (instructionIterator.hasNext()) { |
| Instruction current = instructionIterator.next(); |
| boolean needsAssumeInstruction = false; |
| |
| // Case (1), instructions that implicitly indicate receiver/array is not null. |
| if (current.throwsOnNullInput()) { |
| Value inValue = current.getNonNullInput(); |
| if (assumedValuesBuilder.isMaybeNull(inValue) |
| && isNullableReferenceTypeWithOtherNonDebugUsers(inValue, current)) { |
| assumedValuesBuilder.addNonNullValueWithUnknownDominance(current, inValue); |
| needsAssumeInstruction = true; |
| } |
| } |
| |
| Value outValue = current.outValue(); |
| if (current.isInvokeMethod()) { |
| InvokeMethod invoke = current.asInvokeMethod(); |
| if (invoke.hasOutValue() || !invoke.getInvokedMethod().proto.parameters.isEmpty()) { |
| // Case (2) and (3). |
| needsAssumeInstruction |= |
| computeAssumedValuesFromSingleTarget(code, invoke, assumedValuesBuilder); |
| } |
| } else if (current.isFieldGet()) { |
| // Case (4), field-get instructions that are guaranteed to read a non-null value. |
| FieldInstruction fieldInstruction = current.asFieldInstruction(); |
| DexField field = fieldInstruction.getField(); |
| if (isNullableReferenceTypeWithNonDebugUsers(outValue)) { |
| DexEncodedField encodedField = appView.appInfo().resolveField(field).getResolvedField(); |
| if (encodedField != null) { |
| FieldOptimizationInfo optimizationInfo = encodedField.getOptimizationInfo(); |
| if (optimizationInfo.getDynamicUpperBoundType() != null |
| && optimizationInfo.getDynamicUpperBoundType().isDefinitelyNotNull()) { |
| assumedValuesBuilder.addNonNullValueKnownToDominateAllUsers(current, outValue); |
| needsAssumeInstruction = true; |
| } |
| } |
| } |
| } |
| |
| // If we need to insert an assume instruction into a block with catch handlers, we split the |
| // block such that the IR is ready for the insertion of the assume instruction. |
| // |
| // This splitting could in principle be deferred until we materialize the assume instructions, |
| // but then we would need to rewind the basic block iterator to the beginning, and scan over |
| // the instructions another time, splitting the blocks as needed. |
| if (block.hasCatchHandlers()) { |
| if (needsAssumeInstruction) { |
| BasicBlock insertionBlock = instructionIterator.split(code, blockIterator); |
| assert !instructionIterator.hasNext(); |
| assert instructionIterator.peekPrevious().isGoto(); |
| assert blockIterator.peekPrevious() == insertionBlock; |
| computeAssumedValuesInBlock(code, blockIterator, insertionBlock, assumedValuesBuilder); |
| return; |
| } |
| if (current.instructionTypeCanThrow()) { |
| break; |
| } |
| } |
| } |
| |
| If ifInstruction = block.exit().asIf(); |
| if (ifInstruction != null && ifInstruction.isNonTrivialNullTest()) { |
| Value lhs = ifInstruction.lhs(); |
| if (assumedValuesBuilder.isMaybeNull(lhs) |
| && isNullableReferenceTypeWithOtherNonDebugUsers(lhs, ifInstruction) |
| && ifInstruction.targetFromNonNullObject().getPredecessors().size() == 1) { |
| assumedValuesBuilder.addNonNullValueWithUnknownDominance(ifInstruction, lhs); |
| } |
| } |
| } |
| |
| private boolean computeAssumedValuesFromSingleTarget( |
| IRCode code, InvokeMethod invoke, AssumedValues.Builder assumedValuesBuilder) { |
| DexEncodedMethod singleTarget = invoke.lookupSingleTarget(appView, code.context()); |
| if (singleTarget == null) { |
| return false; |
| } |
| |
| boolean needsAssumeInstruction = false; |
| MethodOptimizationInfo optimizationInfo = singleTarget.getOptimizationInfo(); |
| |
| // Case (2), invocations that are guaranteed to return a non-null value. |
| Value outValue = invoke.outValue(); |
| if (outValue != null |
| && optimizationInfo.neverReturnsNull() |
| && isNullableReferenceTypeWithNonDebugUsers(outValue)) { |
| assumedValuesBuilder.addNonNullValueKnownToDominateAllUsers(invoke, outValue); |
| needsAssumeInstruction = true; |
| } |
| |
| // Case (3), parameters that are not null after the invocation. |
| BitSet nonNullParamOnNormalExits = optimizationInfo.getNonNullParamOnNormalExits(); |
| if (nonNullParamOnNormalExits != null) { |
| int start = invoke.isInvokeMethodWithReceiver() ? 1 : 0; |
| for (int i = start; i < invoke.arguments().size(); i++) { |
| if (nonNullParamOnNormalExits.get(i)) { |
| Value argument = invoke.getArgument(i); |
| if (assumedValuesBuilder.isMaybeNull(argument) |
| && isNullableReferenceTypeWithOtherNonDebugUsers(argument, invoke)) { |
| assumedValuesBuilder.addNonNullValueWithUnknownDominance(invoke, argument); |
| needsAssumeInstruction = true; |
| } |
| } |
| } |
| } |
| return needsAssumeInstruction; |
| } |
| |
| private void removeRedundantAssumeInstructions(AssumedValues assumedValues) { |
| assumedValues.removeIf( |
| (instruction, assumedValue) -> { |
| if (assumedValue.isPhi()) { |
| return false; |
| } |
| Instruction definition = assumedValue.definition; |
| return definition != instruction && assumedValues.contains(definition, assumedValue); |
| }); |
| } |
| |
| private Map<Instruction, Set<Value>> computeDominanceForAssumedValues( |
| IRCode code, AssumedValues assumedValues) { |
| Map<Instruction, Set<Value>> redundantKeys = new IdentityHashMap<>(); |
| LazyDominatorTree lazyDominatorTree = new LazyDominatorTree(code); |
| Map<BasicBlock, Set<BasicBlock>> dominatedBlocksCache = new IdentityHashMap<>(); |
| assumedValues.computeDominance( |
| (instruction, assumedValue) -> { |
| Set<Value> alreadyAssumedValues = redundantKeys.get(instruction); |
| if (alreadyAssumedValues != null && alreadyAssumedValues.contains(assumedValue)) { |
| // Returning redundant() will cause the entry (instruction, assumedValue) to be removed. |
| return AssumedDominance.redundant(); |
| } |
| |
| // If this value is non-null since its definition, then it is known to dominate all users. |
| if (assumedValue == instruction.outValue()) { |
| return AssumedDominance.everything(); |
| } |
| |
| // If we learn that this value is known to be non-null in the same block as it is defined, |
| // and it is not used between its definition and the instruction that performs the null |
| // check, then the non-null-value is known to dominate all other users than the null check |
| // itself. |
| BasicBlock block = instruction.getBlock(); |
| if (assumedValue.getBlock() == block |
| && block.exit().isGoto() |
| && !instruction.getBlock().hasCatchHandlers()) { |
| InstructionIterator iterator = instruction.getBlock().iterator(); |
| if (!assumedValue.isPhi()) { |
| iterator.nextUntil(x -> x != assumedValue.definition); |
| iterator.previous(); |
| } |
| boolean isUsedBeforeInstruction = false; |
| while (iterator.hasNext()) { |
| Instruction current = iterator.next(); |
| if (current == instruction) { |
| break; |
| } |
| if (current.inValues().contains(assumedValue) |
| || current.getDebugValues().contains(assumedValue)) { |
| isUsedBeforeInstruction = true; |
| break; |
| } |
| } |
| if (!isUsedBeforeInstruction) { |
| return AssumedDominance.everythingElse(); |
| } |
| } |
| |
| // Otherwise, we need a dominator tree to determine which users are dominated. |
| BasicBlock insertionBlock = getInsertionBlock(instruction); |
| |
| assert assumedValue.hasPhiUsers() |
| || assumedValue.uniqueUsers().stream().anyMatch(user -> user != instruction) |
| || assumedValue.isArgument(); |
| |
| // Find all users of the original value that are dominated by either the current block |
| // or the new split-off block. Since NPE can be explicitly caught, nullness should be |
| // propagated through dominance. |
| DominatorTree dominatorTree = lazyDominatorTree.get(); |
| Set<BasicBlock> dominatedBlocks = |
| dominatedBlocksCache.computeIfAbsent( |
| insertionBlock, x -> dominatorTree.dominatedBlocks(x, Sets.newIdentityHashSet())); |
| |
| AssumedDominance.Builder dominance = AssumedDominance.builder(assumedValue); |
| for (Instruction user : assumedValue.uniqueUsers()) { |
| if (user != instruction && dominatedBlocks.contains(user.getBlock())) { |
| if (user.getBlock() == insertionBlock && insertionBlock == block) { |
| Instruction first = block.iterator().nextUntil(x -> x == instruction || x == user); |
| assert first != null; |
| if (first == user) { |
| continue; |
| } |
| } |
| dominance.addDominatedUser(user); |
| |
| // Record that there is no need to insert an assume instruction for the non-null-value |
| // after the given user in case the user is also a null check for the non-null-value. |
| redundantKeys |
| .computeIfAbsent(user, ignore -> Sets.newIdentityHashSet()) |
| .add(assumedValue); |
| } |
| } |
| for (Phi user : assumedValue.uniquePhiUsers()) { |
| IntList dominatedPredecessorIndices = |
| findDominatedPredecessorIndexesInPhi(user, assumedValue, dominatedBlocks); |
| if (!dominatedPredecessorIndices.isEmpty()) { |
| dominance.addDominatedPhiUser(user, dominatedPredecessorIndices); |
| } |
| } |
| return dominance.build(); |
| }); |
| return redundantKeys; |
| } |
| |
| private void removeRedundantDominatedAssumeInstructions( |
| AssumedValues assumedValues, Map<Instruction, Set<Value>> redundantKeys) { |
| assumedValues.removeAll(redundantKeys); |
| } |
| |
| private void materializeAssumeInstructions(IRCode code, AssumedValues assumedValues) { |
| Set<Value> affectedValues = Sets.newIdentityHashSet(); |
| Map<BasicBlock, Map<Instruction, List<Instruction>>> pendingInsertions = |
| new IdentityHashMap<>(); |
| assumedValues.forEach( |
| (instruction, assumedValue, assumedValueInfo) -> { |
| BasicBlock block = instruction.getBlock(); |
| BasicBlock insertionBlock = getInsertionBlock(instruction); |
| |
| AssumedDominance dominance = assumedValueInfo.getDominance(); |
| Value newValue = |
| code.createValue( |
| assumedValue.getType().asReferenceType().asMeetWithNotNull(), |
| assumedValue.getLocalInfo()); |
| if (dominance.isEverything()) { |
| assumedValue.replaceUsers(newValue); |
| } else if (dominance.isEverythingElse()) { |
| assumedValue.replaceSelectiveInstructionUsers(newValue, user -> user != instruction); |
| assumedValue.replacePhiUsers(newValue); |
| } else if (dominance.isSomething()) { |
| SomethingAssumedDominance somethingDominance = dominance.asSomething(); |
| somethingDominance |
| .getDominatedPhiUsers() |
| .forEach( |
| (user, indices) -> { |
| IntListIterator iterator = indices.iterator(); |
| while (iterator.hasNext()) { |
| Value operand = user.getOperand(iterator.nextInt()); |
| if (operand != assumedValue) { |
| assert operand.isDefinedByInstructionSatisfying( |
| Instruction::isAssumeNonNull); |
| iterator.remove(); |
| } |
| } |
| }); |
| assumedValue.replaceSelectiveUsers( |
| newValue, |
| somethingDominance.getDominatedUsers(), |
| somethingDominance.getDominatedPhiUsers()); |
| } |
| affectedValues.addAll(newValue.affectedValues()); |
| |
| Assume assumeInstruction = |
| Assume.createAssumeNonNullInstruction(newValue, assumedValue, instruction, appView); |
| assumeInstruction.setPosition(instruction.getPosition()); |
| if (insertionBlock != block) { |
| insertionBlock.listIterator(code).add(assumeInstruction); |
| } else { |
| pendingInsertions |
| .computeIfAbsent(block, ignore -> new IdentityHashMap<>()) |
| .computeIfAbsent(instruction, ignore -> new ArrayList<>()) |
| .add(assumeInstruction); |
| } |
| }); |
| pendingInsertions.forEach( |
| (block, pendingInsertionsPerInstruction) -> { |
| InstructionListIterator instructionIterator = block.listIterator(code); |
| while (instructionIterator.hasNext() && !pendingInsertionsPerInstruction.isEmpty()) { |
| Instruction instruction = instructionIterator.next(); |
| List<Instruction> pendingAssumeInstructions = |
| pendingInsertionsPerInstruction.remove(instruction); |
| if (pendingAssumeInstructions != null) { |
| pendingAssumeInstructions.forEach(instructionIterator::add); |
| } |
| } |
| }); |
| if (!affectedValues.isEmpty()) { |
| new TypeAnalysis(appView).narrowing(affectedValues); |
| } |
| } |
| |
| private BasicBlock getInsertionBlock(Instruction instruction) { |
| if (instruction.isIf()) { |
| return instruction.asIf().targetFromNonNullObject(); |
| } |
| BasicBlock block = instruction.getBlock(); |
| if (block.hasCatchHandlers()) { |
| return block.exit().asGoto().getTarget(); |
| } |
| return block; |
| } |
| |
| private IntList findDominatedPredecessorIndexesInPhi( |
| Phi user, Value assumedValue, Set<BasicBlock> dominatedBlocks) { |
| assert user.getOperands().contains(assumedValue); |
| List<Value> operands = user.getOperands(); |
| List<BasicBlock> predecessors = user.getBlock().getPredecessors(); |
| assert operands.size() == predecessors.size(); |
| |
| IntList predecessorIndexes = new IntArrayList(); |
| int index = 0; |
| Iterator<Value> operandIterator = operands.iterator(); |
| Iterator<BasicBlock> predecessorIterator = predecessors.iterator(); |
| while (operandIterator.hasNext() && predecessorIterator.hasNext()) { |
| Value operand = operandIterator.next(); |
| BasicBlock predecessor = predecessorIterator.next(); |
| // When this phi is chosen to be known-to-be-non-null value, |
| // check if the corresponding predecessor is dominated by the block where non-null is added. |
| if (operand == assumedValue && dominatedBlocks.contains(predecessor)) { |
| predecessorIndexes.add(index); |
| } |
| |
| index++; |
| } |
| return predecessorIndexes; |
| } |
| |
| private static boolean isNullableReferenceType(Value value) { |
| TypeElement type = value.getType(); |
| return type.isReferenceType() && type.asReferenceType().isNullable(); |
| } |
| |
| private static boolean isNullableReferenceTypeWithNonDebugUsers(Value value) { |
| return isNullableReferenceType(value) && value.numberOfAllNonDebugUsers() > 0; |
| } |
| |
| private static boolean isNullableReferenceTypeWithOtherNonDebugUsers( |
| Value value, Instruction ignore) { |
| if (isNullableReferenceType(value)) { |
| if (value.hasPhiUsers()) { |
| return true; |
| } |
| for (Instruction user : value.uniqueUsers()) { |
| if (user != ignore) { |
| return true; |
| } |
| } |
| } |
| return false; |
| } |
| |
| static class AssumedValueInfo { |
| |
| AssumedDominance dominance; |
| NonNullAssumption nonNullAssumption; |
| |
| AssumedValueInfo(AssumedDominance dominance) { |
| this.dominance = dominance; |
| } |
| |
| AssumedDominance getDominance() { |
| return dominance; |
| } |
| |
| void setDominance(AssumedDominance dominance) { |
| this.dominance = dominance; |
| } |
| |
| void setNotNull() { |
| nonNullAssumption = NonNullAssumption.get(); |
| } |
| } |
| |
| static class AssumedValues { |
| |
| /** |
| * A mapping from each instruction to the (in and out) values that are guaranteed to be non-null |
| * by the instruction. Each non-null value is subsequently mapped to the set of users that it |
| * dominates. |
| */ |
| Map<Instruction, Map<Value, AssumedValueInfo>> assumedValues; |
| |
| public AssumedValues(Map<Instruction, Map<Value, AssumedValueInfo>> assumedValues) { |
| this.assumedValues = assumedValues; |
| } |
| |
| public static Builder builder() { |
| return new Builder(); |
| } |
| |
| void computeDominance(BiFunction<Instruction, Value, AssumedDominance> function) { |
| Iterator<Entry<Instruction, Map<Value, AssumedValueInfo>>> outerIterator = |
| assumedValues.entrySet().iterator(); |
| while (outerIterator.hasNext()) { |
| Entry<Instruction, Map<Value, AssumedValueInfo>> outerEntry = outerIterator.next(); |
| Instruction instruction = outerEntry.getKey(); |
| Map<Value, AssumedValueInfo> dominancePerValue = outerEntry.getValue(); |
| Iterator<Entry<Value, AssumedValueInfo>> innerIterator = |
| dominancePerValue.entrySet().iterator(); |
| while (innerIterator.hasNext()) { |
| Entry<Value, AssumedValueInfo> innerEntry = innerIterator.next(); |
| Value assumedValue = innerEntry.getKey(); |
| AssumedValueInfo assumedValueInfo = innerEntry.getValue(); |
| AssumedDominance dominance = assumedValueInfo.dominance; |
| if (dominance.isEverything()) { |
| assert assumedValue.isDefinedByInstructionSatisfying( |
| definition -> definition.outValue() == assumedValue); |
| continue; |
| } |
| assert dominance.isUnknown(); |
| dominance = function.apply(instruction, assumedValue); |
| if ((dominance.isNothing() && !assumedValue.isArgument()) || dominance.isUnknown()) { |
| innerIterator.remove(); |
| } else { |
| assumedValueInfo.setDominance(dominance); |
| } |
| } |
| if (dominancePerValue.isEmpty()) { |
| outerIterator.remove(); |
| } |
| } |
| } |
| |
| boolean contains(Instruction instruction, Value assumedValue) { |
| Map<Value, AssumedValueInfo> dominancePerValue = assumedValues.get(instruction); |
| return dominancePerValue != null && dominancePerValue.containsKey(assumedValue); |
| } |
| |
| boolean isEmpty() { |
| return assumedValues.isEmpty(); |
| } |
| |
| void forEach(TriConsumer<Instruction, Value, AssumedValueInfo> consumer) { |
| assumedValues.forEach( |
| (instruction, dominancePerValue) -> |
| dominancePerValue.forEach( |
| (assumedValue, assumedValueInfo) -> |
| consumer.accept(instruction, assumedValue, assumedValueInfo))); |
| } |
| |
| void removeAll(Map<Instruction, Set<Value>> keys) { |
| keys.forEach( |
| (instruction, values) -> { |
| Map<Value, AssumedValueInfo> dominancePerValue = assumedValues.get(instruction); |
| if (dominancePerValue != null) { |
| values.forEach(dominancePerValue::remove); |
| if (dominancePerValue.isEmpty()) { |
| assumedValues.remove(instruction); |
| } |
| } |
| }); |
| } |
| |
| void removeIf(BiPredicate<Instruction, Value> predicate) { |
| Iterator<Entry<Instruction, Map<Value, AssumedValueInfo>>> outerIterator = |
| assumedValues.entrySet().iterator(); |
| while (outerIterator.hasNext()) { |
| Entry<Instruction, Map<Value, AssumedValueInfo>> outerEntry = outerIterator.next(); |
| Instruction instruction = outerEntry.getKey(); |
| Map<Value, AssumedValueInfo> dominancePerValue = outerEntry.getValue(); |
| Iterator<Entry<Value, AssumedValueInfo>> innerIterator = |
| dominancePerValue.entrySet().iterator(); |
| while (innerIterator.hasNext()) { |
| Value assumedValue = innerIterator.next().getKey(); |
| if (predicate.test(instruction, assumedValue)) { |
| innerIterator.remove(); |
| } |
| } |
| if (dominancePerValue.isEmpty()) { |
| outerIterator.remove(); |
| } |
| } |
| } |
| |
| static class Builder { |
| |
| private final Map<Instruction, Map<Value, AssumedValueInfo>> assumedValues = |
| new LinkedHashMap<>(); |
| |
| // Used to avoid unnecessary block splitting during phase 1. |
| private final Set<Value> assumedValuesKnownToDominateAllUsers = Sets.newIdentityHashSet(); |
| |
| private void addNonNullValue( |
| Instruction instruction, Value nonNullValue, AssumedDominance dominance) { |
| assumedValues |
| .computeIfAbsent(instruction, ignore -> new LinkedHashMap<>()) |
| .computeIfAbsent(nonNullValue, ignore -> new AssumedValueInfo(dominance)) |
| .setNotNull(); |
| if (dominance.isEverything()) { |
| assumedValuesKnownToDominateAllUsers.add(nonNullValue); |
| } |
| } |
| |
| void addNonNullValueKnownToDominateAllUsers(Instruction instruction, Value nonNullValue) { |
| addNonNullValue(instruction, nonNullValue, AssumedDominance.everything()); |
| } |
| |
| void addNonNullValueWithUnknownDominance(Instruction instruction, Value nonNullValue) { |
| addNonNullValue(instruction, nonNullValue, AssumedDominance.unknown()); |
| } |
| |
| public boolean isMaybeNull(Value value) { |
| return !assumedValuesKnownToDominateAllUsers.contains(value); |
| } |
| |
| public AssumedValues build() { |
| return new AssumedValues(assumedValues); |
| } |
| } |
| } |
| |
| abstract static class AssumedDominance { |
| |
| boolean isEverything() { |
| return false; |
| } |
| |
| boolean isEverythingElse() { |
| return false; |
| } |
| |
| boolean isNothing() { |
| return false; |
| } |
| |
| boolean isSomething() { |
| return false; |
| } |
| |
| SomethingAssumedDominance asSomething() { |
| return null; |
| } |
| |
| boolean isUnknown() { |
| return false; |
| } |
| |
| public static Builder builder(Value assumedValue) { |
| return new Builder(assumedValue); |
| } |
| |
| public static EverythingAssumedDominance everything() { |
| return EverythingAssumedDominance.getInstance(); |
| } |
| |
| public static EverythingElseAssumedDominance everythingElse() { |
| return EverythingElseAssumedDominance.getInstance(); |
| } |
| |
| public static NothingAssumedDominance nothing() { |
| return NothingAssumedDominance.getInstance(); |
| } |
| |
| public static UnknownAssumedDominance redundant() { |
| return unknown(); |
| } |
| |
| public static SomethingAssumedDominance something( |
| Set<Instruction> dominatedUsers, Map<Phi, IntList> dominatedPhiUsers) { |
| return new SomethingAssumedDominance(dominatedUsers, dominatedPhiUsers); |
| } |
| |
| public static UnknownAssumedDominance unknown() { |
| return UnknownAssumedDominance.getInstance(); |
| } |
| |
| static class Builder { |
| |
| private final Value assumedValue; |
| |
| private final Set<Instruction> dominatedUsers = Sets.newIdentityHashSet(); |
| private final Map<Phi, IntList> dominatedPhiUsers = new IdentityHashMap<>(); |
| |
| private Builder(Value assumedValue) { |
| this.assumedValue = assumedValue; |
| } |
| |
| void addDominatedUser(Instruction user) { |
| assert assumedValue.uniqueUsers().contains(user); |
| assert !dominatedUsers.contains(user); |
| dominatedUsers.add(user); |
| } |
| |
| void addDominatedPhiUser(Phi user, IntList dominatedPredecessorIndices) { |
| assert assumedValue.uniquePhiUsers().contains(user); |
| assert !dominatedPhiUsers.containsKey(user); |
| dominatedPhiUsers.put(user, dominatedPredecessorIndices); |
| } |
| |
| AssumedDominance build() { |
| if (dominatedUsers.isEmpty() && dominatedPhiUsers.isEmpty()) { |
| return nothing(); |
| } |
| assert dominatedUsers.size() < assumedValue.uniqueUsers().size() |
| || dominatedPhiUsers.size() < assumedValue.uniquePhiUsers().size(); |
| return something(dominatedUsers, dominatedPhiUsers); |
| } |
| } |
| } |
| |
| static class EverythingAssumedDominance extends AssumedDominance { |
| |
| private static final EverythingAssumedDominance INSTANCE = new EverythingAssumedDominance(); |
| |
| private EverythingAssumedDominance() {} |
| |
| public static EverythingAssumedDominance getInstance() { |
| return INSTANCE; |
| } |
| |
| @Override |
| boolean isEverything() { |
| return true; |
| } |
| } |
| |
| static class EverythingElseAssumedDominance extends AssumedDominance { |
| |
| private static final EverythingElseAssumedDominance INSTANCE = |
| new EverythingElseAssumedDominance(); |
| |
| private EverythingElseAssumedDominance() {} |
| |
| public static EverythingElseAssumedDominance getInstance() { |
| return INSTANCE; |
| } |
| |
| @Override |
| boolean isEverythingElse() { |
| return true; |
| } |
| } |
| |
| static class NothingAssumedDominance extends AssumedDominance { |
| |
| private static final NothingAssumedDominance INSTANCE = new NothingAssumedDominance(); |
| |
| private NothingAssumedDominance() {} |
| |
| public static NothingAssumedDominance getInstance() { |
| return INSTANCE; |
| } |
| |
| @Override |
| boolean isNothing() { |
| return true; |
| } |
| } |
| |
| static class SomethingAssumedDominance extends AssumedDominance { |
| |
| private final Set<Instruction> dominatedUsers; |
| private final Map<Phi, IntList> dominatedPhiUsers; |
| |
| SomethingAssumedDominance( |
| Set<Instruction> dominatedUsers, Map<Phi, IntList> dominatedPhiUsers) { |
| this.dominatedUsers = dominatedUsers; |
| this.dominatedPhiUsers = dominatedPhiUsers; |
| } |
| |
| public Set<Instruction> getDominatedUsers() { |
| return dominatedUsers; |
| } |
| |
| public Map<Phi, IntList> getDominatedPhiUsers() { |
| return dominatedPhiUsers; |
| } |
| |
| @Override |
| boolean isSomething() { |
| return true; |
| } |
| |
| @Override |
| SomethingAssumedDominance asSomething() { |
| return this; |
| } |
| } |
| |
| static class UnknownAssumedDominance extends AssumedDominance { |
| |
| private static final UnknownAssumedDominance INSTANCE = new UnknownAssumedDominance(); |
| |
| private UnknownAssumedDominance() {} |
| |
| public static UnknownAssumedDominance getInstance() { |
| return INSTANCE; |
| } |
| |
| @Override |
| boolean isUnknown() { |
| return true; |
| } |
| } |
| } |