src/main/java/com/android/tools/r8/ir/optimize/IdempotentFunctionCallCanonicalizer.java

// 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 com.android.tools.r8.graph.DexItemFactory;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexString;
import com.android.tools.r8.graph.DexType;
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.InstructionListIterator;
import com.android.tools.r8.ir.code.Invoke;
import com.android.tools.r8.ir.code.InvokeMethod;
import com.android.tools.r8.ir.code.Value;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Maps;
import it.unimi.dsi.fastutil.Hash.Strategy;
import it.unimi.dsi.fastutil.objects.Object2ObjectLinkedOpenCustomHashMap;
import it.unimi.dsi.fastutil.objects.Object2ObjectSortedMap.FastSortedEntrySet;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

/**
 * Canonicalize idempotent function calls.
 *
 * <p>For example,
 *
 *   v1 <- const4 0x0
 *   ...
 *   vx <- invoke-static { v1 } Ljava/lang/Boolean;->valueOf(Z)Ljava/lang/Boolean;
 *   ...
 *   vy <- invoke-static { v1 } Ljava/lang/Boolean;->valueOf(Z);Ljava/lang/Boolean;
 *   ...
 *   vz <- invoke-static { v1 } Ljava/lang/Boolean;->valueOf(Z);Ljava/lang/Boolean;
 *   ...
 *
 * ~>
 *
 *   v1 <- const4 0x0
 *   v2 <- invoke-static { v1 } Ljava/lang/Boolean;->valueOf(Z);Ljava/lang/Boolean;
 *   // Update users of vx, vy, and vz.
 */
public class IdempotentFunctionCallCanonicalizer {
  private static final int MAX_CANONICALIZED_CALL = 7;

  private final Set<DexMethod> idempotentMethods;

  public IdempotentFunctionCallCanonicalizer(DexItemFactory factory) {
    ImmutableSet.Builder<DexMethod> idempotentMethodsBuilder = ImmutableSet.builder();
    // Boxed Boxed#valueOf(Primitive), e.g., Boolean Boolean#valueOf(B)
    for (Entry<DexType, DexType> entry : factory.primitiveToBoxed.entrySet()) {
      DexType primitive = entry.getKey();
      DexType boxed = entry.getValue();
      idempotentMethodsBuilder.add(
          factory.createMethod(
              boxed.descriptor,
              factory.valueOfMethodName,
              boxed.descriptor,
              new DexString[] {primitive.descriptor}));
    }
    // TODO(b/119596718): More idempotent methods? Any singleton accessors? E.g.,
    // java.util.Calendar#getInstance(...) // 4 variants
    // java.util.Locale#getDefault() // returns JVM default locale.
    // android.os.Looper#myLooper() // returns the associated Looper instance.
    idempotentMethods = idempotentMethodsBuilder.build();
  }

  public void canonicalize(IRCode code) {
    Object2ObjectLinkedOpenCustomHashMap<InvokeMethod, List<Value>> returnValues =
        new Object2ObjectLinkedOpenCustomHashMap<>(
            new Strategy<InvokeMethod>() {
              @Override
              public int hashCode(InvokeMethod o) {
                return o.getInvokedMethod().hashCode() * 31 + o.inValues().hashCode();
              }

              @Override
              public boolean equals(InvokeMethod a, InvokeMethod b) {
                assert a == null || !a.outValue().hasLocalInfo();
                assert b == null || !b.outValue().hasLocalInfo();
                return a == b
                    || (a != null && b != null && a.identicalNonValueNonPositionParts(b)
                        && a.inValues().equals(b.inValues()));
              }
            });

    // Collect invocations along with arguments.
    for (BasicBlock block : code.blocks) {
      InstructionListIterator it = block.listIterator();
      while (it.hasNext()) {
        Instruction current = it.next();
        if (!current.isInvokeMethod()) {
          continue;
        }
        InvokeMethod invoke = current.asInvokeMethod();
        // Interested in known-to-be idempotent method call.
        if (!idempotentMethods.contains(invoke.getInvokedMethod())) {
          continue;
        }
        // If the out value of the current invocation is not used and removed, we don't care either.
        if (invoke.outValue() == null) {
          continue;
        }
        // Invocations with local info cannot be canonicalized.
        if (current.outValue().hasLocalInfo()) {
          continue;
        }
        assert !current.inValues().isEmpty();
        // TODO(b/119596718): Use dominant tree to extend it to non-canonicalized in values?
        // For now, interested in inputs that are also canonicalized constants.
        boolean invocationCanBeMovedToEntryBlock = true;
        for (Value in : current.inValues()) {
          if (in.isPhi()
              || !in.definition.isConstInstruction()
              || in.definition.getBlock().getNumber() != 0) {
            invocationCanBeMovedToEntryBlock = false;
            break;
          }
        }
        if (!invocationCanBeMovedToEntryBlock) {
          continue;
        }
        List<Value> oldReturnValues = returnValues.computeIfAbsent(invoke, k -> new ArrayList<>());
        oldReturnValues.add(current.outValue());
      }
    }

    if (returnValues.isEmpty()) {
      return;
    }

    // InvokeMethod is not treated as dead code explicitly, i.e., cannot rely on dead code remover.
    Map<InvokeMethod, Value> deadInvocations = Maps.newHashMap();

    FastSortedEntrySet<InvokeMethod, List<Value>> entries = returnValues.object2ObjectEntrySet();
    entries.stream()
        .filter(a -> a.getValue().size() > 1)
        .sorted((a, b) -> Integer.compare(b.getValue().size(), a.getValue().size()))
        .limit(MAX_CANONICALIZED_CALL)
        .forEach((entry) -> {
          InvokeMethod invoke = entry.getKey();
          Value canonicalizedValue = code.createValue(
              invoke.outValue().getTypeLattice(), invoke.outValue().getLocalInfo());
          Invoke canonicalizedInvoke =
              Invoke.create(
                  invoke.getType(),
                  invoke.getInvokedMethod(),
                  null,
                  canonicalizedValue,
                  invoke.inValues());
          insertCanonicalizedInvoke(code, canonicalizedInvoke);
          for (Value oldOutValue : entry.getValue()) {
            deadInvocations.put(oldOutValue.definition.asInvokeMethod(), canonicalizedValue);
          }
        });

    if (!deadInvocations.isEmpty()) {
      for (BasicBlock block : code.blocks) {
        InstructionListIterator it = block.listIterator();
        while (it.hasNext()) {
          Instruction current = it.next();
          if (!current.isInvokeMethod()) {
            continue;
          }
          InvokeMethod invoke = current.asInvokeMethod();
          if (deadInvocations.containsKey(invoke)) {
            Value newOutValue = deadInvocations.get(invoke);
            assert newOutValue != null;
            invoke.outValue().replaceUsers(newOutValue);
            it.removeOrReplaceByDebugLocalRead();
          }
        }
      }
    }

    code.removeAllTrivialPhis();
    assert code.isConsistentSSA();
  }

  private static void insertCanonicalizedInvoke(IRCode code, Invoke canonicalizedInvoke) {
    BasicBlock entryBlock = code.entryBlock();
    // Insert the canonicalized invoke after in values.
    int numberOfInValuePassed = 0;
    InstructionListIterator it = entryBlock.listIterator();
    while (it.hasNext()) {
      Instruction current = it.next();
      if (current.hasOutValue() && canonicalizedInvoke.inValues().contains(current.outValue())) {
        numberOfInValuePassed++;
      }
      if (numberOfInValuePassed == canonicalizedInvoke.inValues().size()) {
        canonicalizedInvoke.setPosition(current.getPosition());
        break;
      }
    }
    it.add(canonicalizedInvoke);
  }
}