src/main/java/com/android/tools/r8/ir/analysis/ValueMayDependOnEnvironmentAnalysis.java

// 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.analysis;

import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexEncodedMethod.TrivialInitializer;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.ir.code.ArrayPut;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.InvokeDirect;
import com.android.tools.r8.ir.code.InvokeMethod;
import com.android.tools.r8.ir.code.InvokeNewArray;
import com.android.tools.r8.ir.code.NewArrayEmpty;
import com.android.tools.r8.ir.code.NewArrayFilledData;
import com.android.tools.r8.ir.code.StaticPut;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.utils.LongInterval;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Sets;
import java.util.Set;

public class ValueMayDependOnEnvironmentAnalysis {

  private final AppView<?> appView;
  private final IRCode code;
  private final DexType context;

  public ValueMayDependOnEnvironmentAnalysis(AppView<?> appView, IRCode code) {
    this.appView = appView;
    this.code = code;
    this.context = code.method.method.holder;
  }

  public boolean valueMayDependOnEnvironment(Value value) {
    Value root = value.getAliasedValue();
    if (root.isConstant()) {
      return false;
    }
    if (isConstantArrayThroughoutMethod(root)) {
      return false;
    }
    if (isNewInstanceWithoutEnvironmentDependentFields(root)) {
      return false;
    }
    return true;
  }

  public boolean isConstantArrayThroughoutMethod(Value value) {
    Value root = value.getAliasedValue();
    if (root.isPhi()) {
      // Would need to track the aliases, just give up.
      return false;
    }

    Instruction definition = root.definition;

    // Check that it is a constant array with a known size at this point in the IR.
    long size;
    if (definition.isInvokeNewArray()) {
      InvokeNewArray invokeNewArray = definition.asInvokeNewArray();
      for (Value argument : invokeNewArray.arguments()) {
        if (!argument.isConstant()) {
          return false;
        }
      }
      size = invokeNewArray.arguments().size();
    } else if (definition.isNewArrayEmpty()) {
      NewArrayEmpty newArrayEmpty = definition.asNewArrayEmpty();
      Value sizeValue = newArrayEmpty.size().getAliasedValue();
      if (!sizeValue.hasValueRange()) {
        return false;
      }
      LongInterval sizeRange = sizeValue.getValueRange();
      if (!sizeRange.isSingleValue()) {
        return false;
      }
      size = sizeRange.getSingleValue();
    } else {
      // Some other array creation.
      return false;
    }

    if (size < 0) {
      // Check for NegativeArraySizeException.
      return false;
    }

    if (size == 0) {
      // Empty arrays are always constant.
      return true;
    }

    // Allow array-put and new-array-filled-data instructions that immediately follow the array
    // creation.
    Set<Instruction> consumedInstructions = Sets.newIdentityHashSet();

    for (Instruction instruction : definition.getBlock().instructionsAfter(definition)) {
      if (instruction.isArrayPut()) {
        ArrayPut arrayPut = instruction.asArrayPut();
        Value array = arrayPut.array().getAliasedValue();
        if (array != root) {
          // This ends the chain of array-put instructions that are allowed immediately after the
          // array creation.
          break;
        }

        LongInterval indexRange = arrayPut.index().getValueRange();
        if (!indexRange.isSingleValue()) {
          return false;
        }

        long index = indexRange.getSingleValue();
        if (index < 0 || index >= size) {
          return false;
        }

        if (!arrayPut.value().isConstant()) {
          return false;
        }

        consumedInstructions.add(arrayPut);
        continue;
      }

      if (instruction.isNewArrayFilledData()) {
        NewArrayFilledData newArrayFilledData = instruction.asNewArrayFilledData();
        Value array = newArrayFilledData.src();
        if (array != root) {
          break;
        }

        consumedInstructions.add(newArrayFilledData);
        continue;
      }

      if (instruction.instructionMayHaveSideEffects(appView, context)) {
        // This ends the chain of array-put instructions that are allowed immediately after the
        // array creation.
        break;
      }
    }

    // Check that the array is not mutated before the end of this method.
    //
    // Currently, we only allow the array to flow into static-put instructions that are not
    // followed by an instruction that may have side effects. Instructions that do not have any
    // side effects are ignored because they cannot mutate the array.
    return !valueMayBeMutatedBeforeMethodExit(root, consumedInstructions);
  }

  private boolean isNewInstanceWithoutEnvironmentDependentFields(Value value) {
    assert !value.hasAliasedValue();

    if (value.isPhi() || !value.definition.isNewInstance()) {
      return false;
    }

    // Find the single constructor invocation.
    InvokeMethod constructorInvoke = null;
    for (Instruction instruction : value.uniqueUsers()) {
      if (!instruction.isInvokeDirect()) {
        continue;
      }

      InvokeDirect invoke = instruction.asInvokeDirect();
      if (!appView.dexItemFactory().isConstructor(invoke.getInvokedMethod())) {
        continue;
      }

      if (invoke.getReceiver().getAliasedValue() != value) {
        continue;
      }

      if (constructorInvoke == null) {
        constructorInvoke = invoke;
      } else {
        // Not a single constructor invocation, give up.
        return false;
      }
    }

    if (constructorInvoke == null) {
      // Didn't find a constructor invocation, give up.
      return false;
    }

    // Check that it is a trivial initializer (otherwise, the constructor could do anything).
    DexEncodedMethod constructor = appView.definitionFor(constructorInvoke.getInvokedMethod());
    if (constructor == null) {
      return false;
    }

    TrivialInitializer initializerInfo =
        constructor.getOptimizationInfo().getTrivialInitializerInfo();
    if (initializerInfo == null || !initializerInfo.isTrivialInstanceInitializer()) {
      return false;
    }

    // Check that none of the arguments to the constructor depend on the environment.
    for (int i = 1; i < constructorInvoke.arguments().size(); i++) {
      Value argument = constructorInvoke.arguments().get(i);
      if (valueMayDependOnEnvironment(argument)) {
        return false;
      }
    }

    // Finally, check that the object does not escape.
    return !valueMayBeMutatedBeforeMethodExit(value, ImmutableSet.of(constructorInvoke));
  }

  private boolean valueMayBeMutatedBeforeMethodExit(Value value, Set<Instruction> whitelist) {
    assert !value.hasAliasedValue();

    if (value.numberOfPhiUsers() > 0) {
      // Could be mutated indirectly.
      return true;
    }

    Set<Instruction> visited = Sets.newIdentityHashSet();
    for (Instruction user : value.uniqueUsers()) {
      if (whitelist.contains(user)) {
        continue;
      }

      if (user.isStaticPut()) {
        StaticPut staticPut = user.asStaticPut();
        if (visited.contains(staticPut)) {
          // Already visited previously.
          continue;
        }
        for (Instruction instruction : code.getInstructionsReachableFrom(staticPut)) {
          if (!visited.add(instruction)) {
            // Already visited previously.
            continue;
          }
          if (instruction.isStaticPut()) {
            StaticPut otherStaticPut = instruction.asStaticPut();
            if (otherStaticPut.getField().holder == staticPut.getField().holder
                && instruction.instructionInstanceCanThrow(appView, context).cannotThrow()) {
              continue;
            }
            return true;
          }
          if (instruction.instructionMayTriggerMethodInvocation(appView, context)) {
            return true;
          }
        }
        continue;
      }

      // Other user than static-put, just give up.
      return false;
    }

    return false;
  }
}