blob: d7abfac7fd09ca49b7cd0e0e878dd87fa7e99236 [file] [log] [blame]
// Copyright (c) 2016, the R8 project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.ir.code;
import com.android.tools.r8.cf.TypeVerificationHelper;
import com.android.tools.r8.errors.CompilationError;
import com.android.tools.r8.errors.InvalidDebugInfoException;
import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DebugLocalInfo;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.ir.analysis.type.Nullability;
import com.android.tools.r8.ir.analysis.type.TypeElement;
import com.android.tools.r8.ir.code.BasicBlock.EdgeType;
import com.android.tools.r8.ir.conversion.IRBuilder;
import com.android.tools.r8.ir.conversion.TypeConstraintResolver;
import com.android.tools.r8.origin.Origin;
import com.android.tools.r8.utils.CfgPrinter;
import com.android.tools.r8.utils.DequeUtils;
import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.Reporter;
import com.android.tools.r8.utils.SetUtils;
import com.android.tools.r8.utils.StringUtils;
import com.google.common.collect.Sets;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.function.Predicate;
public class Phi extends Value implements InstructionOrPhi {
public enum RegisterReadType {
NORMAL,
DEBUG,
}
private final BasicBlock block;
private final List<Value> operands = new ArrayList<>();
private RegisterReadType readType;
private boolean isStackPhi;
// Trivial phis are eliminated during IR construction. When a trivial phi is eliminated
// we need to update all references to it. A phi can be referenced from phis, instructions
// and current definition mappings. This list contains the current definitions mappings that
// contain this phi.
private List<Map<Integer, Value>> definitionUsers = new ArrayList<>();
public Phi(
int number,
BasicBlock block,
TypeElement type,
DebugLocalInfo local,
RegisterReadType readType) {
super(number, type, local);
this.block = block;
this.readType = readType;
block.addPhi(this);
}
@Override
public boolean isDefinedByInstructionSatisfying(Predicate<Instruction> predicate) {
return false;
}
@Override
public boolean isPhi() {
return true;
}
@Override
public Phi asPhi() {
return this;
}
@Override
public BasicBlock getBlock() {
return block;
}
@Override
public void constrainType(
ValueTypeConstraint constraint, DexMethod method, Origin origin, Reporter reporter) {
if (readType == RegisterReadType.DEBUG) {
abortOnInvalidDebugInfo(constraint);
}
super.constrainType(constraint, method, origin, reporter);
}
private void abortOnInvalidDebugInfo(ValueTypeConstraint constraint) {
if (constrainedType(constraint) == null) {
// If the phi has been requested from local info, throw out locals and retry compilation.
throw new InvalidDebugInfoException(
"Type information in locals-table is inconsistent."
+ " Cannot constrain type: "
+ type
+ " for value: "
+ this
+ " by constraint "
+ constraint
+ ".");
}
}
public void addOperands(IRBuilder builder, int register) {
// Phi operands are only filled in once to complete the phi. Some phis are incomplete for a
// period of time to break cycles. When the cycle has been resolved they are completed
// exactly once by adding the operands.
assert operands.isEmpty();
if (block.getPredecessors().size() == 0) {
throwUndefinedValueError();
}
ValueTypeConstraint readConstraint = TypeConstraintResolver.constraintForType(type);
List<Value> operands = new ArrayList<>(block.getPredecessors().size());
for (BasicBlock pred : block.getPredecessors()) {
EdgeType edgeType = pred.getEdgeType(block);
Value operand = builder.readRegister(register, readConstraint, pred, edgeType, readType);
operands.add(operand);
}
if (readType == RegisterReadType.DEBUG) {
for (Value operand : operands) {
TypeElement type = operand.getType();
ValueTypeConstraint constraint = TypeConstraintResolver.constraintForType(type);
abortOnInvalidDebugInfo(constraint);
}
}
for (Value operand : operands) {
builder.constrainType(operand, readConstraint);
appendOperand(operand);
}
removeTrivialPhi(builder, null);
}
public void addOperands(List<Value> operands) {
addOperands(operands, true);
}
public void addOperands(List<Value> operands, boolean removeTrivialPhi) {
// Phi operands are only filled in once to complete the phi. Some phis are incomplete for a
// period of time to break cycles. When the cycle has been resolved they are completed
// exactly once by adding the operands.
assert this.operands.isEmpty();
if (operands.size() == 0) {
throwUndefinedValueError();
}
for (Value operand : operands) {
appendOperand(operand);
}
if (removeTrivialPhi) {
removeTrivialPhi();
}
}
@Override
public void markNonDebugLocalRead() {
readType = RegisterReadType.NORMAL;
}
private void throwUndefinedValueError() {
throw new CompilationError(
"Undefined value encountered during compilation. "
+ "This is typically caused by invalid dex input that uses a register "
+ "that is not defined on all control-flow paths leading to the use.");
}
public void appendOperand(Value operand) {
operands.add(operand);
operand.addPhiUser(this);
}
public Value getOperand(int predIndex) {
return operands.get(predIndex);
}
public List<Value> getOperands() {
return operands;
}
public void removeOperand(int index) {
operands.get(index).removePhiUser(this);
operands.remove(index);
}
public void removeOperandsByIndex(List<Integer> operandsToRemove) {
if (operandsToRemove.isEmpty()) {
return;
}
List<Value> copy = new ArrayList<>(operands);
operands.clear();
int current = 0;
for (int i : operandsToRemove) {
operands.addAll(copy.subList(current, i));
copy.get(i).removePhiUser(this);
current = i + 1;
}
operands.addAll(copy.subList(current, copy.size()));
}
public void replaceOperandAt(int predIndex, Value newValue) {
Value current = operands.get(predIndex);
operands.set(predIndex, newValue);
newValue.addPhiUser(this);
current.removePhiUser(this);
}
void replaceOperand(Value current, Value newValue) {
for (int i = 0; i < operands.size(); i++) {
if (operands.get(i) == current) {
operands.set(i, newValue);
newValue.addPhiUser(this);
}
}
}
public boolean isTrivialPhi() {
Value same = null;
for (Value op : operands) {
if (op == same || op == this) {
// Have only seen one value other than this.
continue;
}
if (same != null) {
// Merged at least two values and is therefore not trivial.
return false;
}
same = op;
}
return true;
}
public boolean removeTrivialPhi() {
return removeTrivialPhi(null, null);
}
public boolean removeTrivialPhi(IRBuilder builder, Set<Value> affectedValues) {
Value same = null;
for (Value op : operands) {
if (op == same || op == this) {
// Have only seen one value other than this.
continue;
}
if (same != null) {
// Merged at least two values and is therefore not trivial.
assert !isTrivialPhi();
return false;
}
same = op;
}
assert isTrivialPhi();
if (same == null) {
// When doing if-simplification we remove blocks and we can end up with cyclic phis
// of the form v1 = phi(v1, v1) in dead blocks. If we encounter that case we just
// leave the phi in there and check at the end that there are no trivial phis.
return false;
}
if (getLocalInfo() != same.getLocalInfo()) {
if (getLocalInfo() == null) {
// The to-be replaced phi has no local info, so all is OK.
} else if (same.getLocalInfo() == null) {
// Move the local info to the replacement phi.
same.setLocalInfo(getLocalInfo());
} else {
// The phi's define distinct locals and are not trivially the same.
assert hasLocalInfo() && same.hasLocalInfo();
return false;
}
}
// Ensure that the value that replaces this phi is constrained to the type of this phi.
if (builder != null && type.isPreciseType() && !type.isBottom()) {
builder.constrainType(same, ValueTypeConstraint.fromTypeLattice(type));
}
if (affectedValues != null) {
affectedValues.addAll(this.affectedValues());
}
// Removing this phi, so get rid of it as a phi user from all of the operands to avoid
// recursively getting back here with the same phi. If the phi has itself as an operand
// that also removes the self-reference.
for (Value op : operands) {
op.removePhiUser(this);
}
// If IR construction is taking place, update the definition users.
if (definitionUsers != null) {
for (Map<Integer, Value> user : definitionUsers) {
for (Entry<Integer, Value> entry : user.entrySet()) {
if (entry.getValue() == this) {
entry.setValue(same);
if (same.isPhi()) {
same.asPhi().addDefinitionsUser(user);
}
}
}
}
}
{
Set<Phi> phiUsersToSimplify = uniquePhiUsers();
// Replace this phi with the unique value in all users.
replaceUsers(same);
// Try to simplify phi users that might now have become trivial.
for (Phi user : phiUsersToSimplify) {
user.removeTrivialPhi(builder, affectedValues);
}
}
// Get rid of the phi itself.
block.removePhi(this);
return true;
}
public void removeDeadPhi() {
// First, make sure it is indeed dead, i.e., no non-phi users.
assert !hasUsers();
// Then, manually clean up this from all of the operands.
for (Value operand : getOperands()) {
operand.removePhiUser(this);
}
// And remove it from the containing block.
getBlock().removePhi(this);
}
public String printPhi() {
StringBuilder builder = new StringBuilder();
builder.append("v");
builder.append(number);
if (hasLocalInfo()) {
builder.append("(").append(getLocalInfo()).append(")");
}
builder.append(" <- phi");
StringUtils.append(builder, ListUtils.map(operands, Value::toString));
builder.append(" : ").append(getType());
return builder.toString();
}
public void print(CfgPrinter printer) {
int uses = numberOfPhiUsers() + numberOfUsers();
printer
.print("0 ") // bci
.append(uses) // use
.append(" v").append(number) // tid
.append(" Phi");
for (Value operand : operands) {
printer.append(" v").append(operand.number);
}
}
public void addDefinitionsUser(Map<Integer, Value> currentDefinitions) {
definitionUsers.add(currentDefinitions);
}
public void removeDefinitionsUser(Map<Integer, Value> currentDefinitions) {
definitionUsers.remove(currentDefinitions);
}
public void clearDefinitionsUsers() {
definitionUsers = null;
}
@Override
public boolean isConstant() {
return false;
}
@Override
public boolean isValueOnStack() {
assert verifyIsStackPhi(Sets.newIdentityHashSet());
return isStackPhi;
}
public void setIsStackPhi(boolean isStackPhi) {
this.isStackPhi = isStackPhi;
}
private boolean verifyIsStackPhi(Set<Phi> seenPhis) {
seenPhis.add(this);
operands.forEach(
v -> {
if (v.isPhi()) {
assert seenPhis.contains(v) || v.asPhi().verifyIsStackPhi(seenPhis);
} else {
assert v.isValueOnStack() == isStackPhi;
}
});
return true;
}
@Override
public boolean needsRegister() {
return !isValueOnStack();
}
public boolean usesValueOneTime(Value usedValue) {
return operands.indexOf(usedValue) == operands.lastIndexOf(usedValue);
}
public DexType computeVerificationType(AppView<?> appView, TypeVerificationHelper helper) {
assert outType().isObject();
Set<DexType> operandTypes = new HashSet<>(operands.size());
for (Value operand : operands) {
DexType operandType = helper.getDexType(operand);
if (operandType != null) {
operandTypes.add(operandType);
}
}
return helper.join(operandTypes);
}
// Type of phi(v1, v2, ..., vn) is the least upper bound of all those n operands.
public TypeElement computePhiType(AppView<?> appView) {
TypeElement result = TypeElement.getBottom();
for (Value operand : getOperands()) {
result = result.join(operand.getType(), appView);
}
return result;
}
@Override
public TypeElement getDynamicUpperBoundType(
AppView<? extends AppInfoWithClassHierarchy> appView) {
Set<Phi> reachablePhis = SetUtils.newIdentityHashSet(this);
Deque<Phi> worklist = DequeUtils.newArrayDeque(this);
while (!worklist.isEmpty()) {
Phi phi = worklist.removeFirst();
assert reachablePhis.contains(phi);
for (Value operand : phi.getOperands()) {
Phi candidate = operand.getAliasedValue().asPhi();
if (candidate != null && reachablePhis.add(candidate)) {
worklist.addLast(candidate);
}
}
}
Set<Value> visitedOperands = Sets.newIdentityHashSet();
TypeElement result = TypeElement.getBottom();
for (Phi phi : reachablePhis) {
for (Value operand : phi.getOperands()) {
if (!operand.getAliasedValue().isPhi() && visitedOperands.add(operand)) {
result = result.join(operand.getDynamicUpperBoundType(appView), appView);
}
}
}
if (getType().isReferenceType() && getType().isDefinitelyNotNull()) {
return result.asReferenceType().asMeetWithNotNull();
}
return result;
}
// TODO(b/169120386) This class is added to ensure we do not narrow or widen the type of phi's
// in D8 when having stack map information. We do allow for narrowing on nullable information.
// It should be removed when we are certain to never widen or narrowing phi's in D8.
public static class StackMapPhi extends Phi {
public StackMapPhi(
int number,
BasicBlock block,
TypeElement type,
DebugLocalInfo local,
RegisterReadType readType) {
super(number, block, type, local, readType);
}
@Override
public DexType computeVerificationType(AppView<?> appView, TypeVerificationHelper helper) {
assert !appView.enableWholeProgramOptimizations();
if (type.isPrimitiveType()) {
return type.asPrimitiveType().toDexType(appView.dexItemFactory());
} else if (type.isArrayType()) {
return type.asArrayType().toDexType(appView.dexItemFactory());
} else {
assert type.isClassType();
return type.asClassType().getClassType();
}
}
@Override
public TypeElement computePhiType(AppView<?> appView) {
assert !appView.enableWholeProgramOptimizations();
if (type.isPrimitiveType()) {
return type;
}
assert type.isReferenceType();
Nullability nullability = Nullability.bottom();
for (Value operand : getOperands()) {
nullability = nullability.join(operand.type.nullability());
}
return type.asReferenceType().getOrCreateVariant(nullability);
}
@Override
public boolean isStackMapPhi() {
return true;
}
}
}