diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
index add6578..a3a329e 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -1008,6 +1008,7 @@
     public static boolean UNKNOWN_INITIALIZER_ENABLING_JAVA_ASSERTIONS = false;
     public static ParameterUsagesInfo UNKNOWN_PARAMETER_USAGE_INFO = null;
     public static boolean UNKNOWN_MAY_HAVE_SIDE_EFFECTS = true;
+    public static boolean UNKNOWN_RETURN_VALUE_ONLY_DEPENDS_ON_ARGUMENTS = false;
     public static BitSet NO_NULL_PARAMETER_OR_THROW_FACTS = null;
     public static BitSet NO_NULL_PARAMETER_ON_NORMAL_EXITS_FACTS = null;
 
@@ -1143,6 +1144,11 @@
     }
 
     @Override
+    public boolean returnValueOnlyDependsOnArguments() {
+      return UNKNOWN_RETURN_VALUE_ONLY_DEPENDS_ON_ARGUMENTS;
+    }
+
+    @Override
     public boolean returnValueHasBeenPropagated() {
       return false;
     }
@@ -1161,6 +1167,8 @@
     private int returnedArgument = DefaultMethodOptimizationInfoImpl.UNKNOWN_RETURNED_ARGUMENT;
     private boolean mayHaveSideEffects =
         DefaultMethodOptimizationInfoImpl.UNKNOWN_MAY_HAVE_SIDE_EFFECTS;
+    private boolean returnValueOnlyDependsOnArguments =
+        DefaultMethodOptimizationInfoImpl.UNKNOWN_RETURN_VALUE_ONLY_DEPENDS_ON_ARGUMENTS;
     private boolean neverReturnsNull = DefaultMethodOptimizationInfoImpl.UNKNOWN_NEVER_RETURNS_NULL;
     private boolean neverReturnsNormally =
         DefaultMethodOptimizationInfoImpl.UNKNOWN_NEVER_RETURNS_NORMALLY;
@@ -1369,6 +1377,11 @@
     }
 
     @Override
+    public boolean returnValueOnlyDependsOnArguments() {
+      return returnValueOnlyDependsOnArguments;
+    }
+
+    @Override
     public void setParameterUsages(ParameterUsagesInfo parametersUsages) {
       this.parametersUsages = parametersUsages;
     }
@@ -1421,6 +1434,11 @@
     }
 
     @Override
+    public void markReturnValueOnlyDependsOnArguments() {
+      returnValueOnlyDependsOnArguments = true;
+    }
+
+    @Override
     public void markNeverReturnsNull() {
       neverReturnsNull = true;
     }
diff --git a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
index cb9d725..d5ebf00 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -47,6 +47,7 @@
 import java.util.concurrent.ConcurrentHashMap;
 import java.util.function.Consumer;
 import java.util.function.Function;
+import java.util.stream.Collectors;
 
 public class DexItemFactory {
 
@@ -94,6 +95,8 @@
 
   public DexItemFactory() {
     this.kotlin = new Kotlin(this);
+    assert libraryMethodsWithoutSideEffects
+        .containsAll(libraryMethodsWithReturnValueDependingOnlyOnArguments);
   }
 
   public static boolean isInternalSentinel(DexItem item) {
@@ -349,6 +352,43 @@
 
   public final ServiceLoaderMethods serviceLoaderMethods = new ServiceLoaderMethods();
 
+  public final BiMap<DexType, DexType> primitiveToBoxed = HashBiMap.create(
+      ImmutableMap.<DexType, DexType>builder()
+          .put(booleanType, boxedBooleanType)
+          .put(byteType, boxedByteType)
+          .put(charType, boxedCharType)
+          .put(shortType, boxedShortType)
+          .put(intType, boxedIntType)
+          .put(longType, boxedLongType)
+          .put(floatType, boxedFloatType)
+          .put(doubleType, boxedDoubleType)
+          .build());
+
+  public DexType getBoxedForPrimitiveType(DexType primitive) {
+    assert primitive.isPrimitiveType();
+    return primitiveToBoxed.get(primitive);
+  }
+
+  public DexType getPrimitiveFromBoxed(DexType boxedPrimitive) {
+    return primitiveToBoxed.inverse().get(boxedPrimitive);
+  }
+
+  // Boxed Boxed#valueOf(Primitive), e.g., Boolean Boolean#valueOf(B)
+  private Set<DexMethod> boxedValueOfMethods() {
+    return primitiveToBoxed.entrySet().stream()
+        .map(
+            entry -> {
+              DexType primitive = entry.getKey();
+              DexType boxed = entry.getValue();
+              return createMethod(
+                  boxed.descriptor,
+                  valueOfMethodName,
+                  boxed.descriptor,
+                  new DexString[] {primitive.descriptor});
+            })
+        .collect(Collectors.toSet());
+  }
+
   public final DexMethod metafactoryMethod =
       createMethod(
           metafactoryType,
@@ -414,6 +454,18 @@
           .addAll(classMethods.getNames)
           .addAll(stringBufferMethods.constructorMethods)
           .addAll(stringBuilderMethods.constructorMethods)
+          .addAll(boxedValueOfMethods())
+          .build();
+
+  // 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.
+  // Note that this set is used for canonicalization of method invocations, together with a set of
+  // library methods that do not have side effects.
+  public Set<DexMethod> libraryMethodsWithReturnValueDependingOnlyOnArguments =
+      ImmutableSet.<DexMethod>builder()
+          .addAll(boxedValueOfMethods())
           .build();
 
   public Set<DexType> libraryTypesAssumedToBePresent =
@@ -436,27 +488,6 @@
     return dexMethod == metafactoryMethod || dexMethod == metafactoryAltMethod;
   }
 
-  public final BiMap<DexType, DexType> primitiveToBoxed = HashBiMap.create(
-      ImmutableMap.<DexType, DexType>builder()
-          .put(booleanType, boxedBooleanType)
-          .put(byteType, boxedByteType)
-          .put(charType, boxedCharType)
-          .put(shortType, boxedShortType)
-          .put(intType, boxedIntType)
-          .put(longType, boxedLongType)
-          .put(floatType, boxedFloatType)
-          .put(doubleType, boxedDoubleType)
-          .build());
-
-  public DexType getBoxedForPrimitiveType(DexType primitive) {
-    assert primitive.isPrimitiveType();
-    return primitiveToBoxed.get(primitive);
-  }
-
-  public DexType getPrimitiveFromBoxed(DexType boxedPrimitive) {
-    return primitiveToBoxed.inverse().get(boxedPrimitive);
-  }
-
   public class LongMethods {
 
     public final DexMethod compare;
diff --git a/src/main/java/com/android/tools/r8/graph/MethodOptimizationInfo.java b/src/main/java/com/android/tools/r8/graph/MethodOptimizationInfo.java
index 213bb11..108779c 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodOptimizationInfo.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodOptimizationInfo.java
@@ -69,6 +69,8 @@
 
   boolean mayHaveSideEffects();
 
+  boolean returnValueOnlyDependsOnArguments();
+
   boolean returnValueHasBeenPropagated();
 
   UpdatableMethodOptimizationInfo mutableCopy();
diff --git a/src/main/java/com/android/tools/r8/graph/UpdatableMethodOptimizationInfo.java b/src/main/java/com/android/tools/r8/graph/UpdatableMethodOptimizationInfo.java
index 5791733..da39812 100644
--- a/src/main/java/com/android/tools/r8/graph/UpdatableMethodOptimizationInfo.java
+++ b/src/main/java/com/android/tools/r8/graph/UpdatableMethodOptimizationInfo.java
@@ -28,6 +28,8 @@
 
   void markMayNotHaveSideEffects();
 
+  void markReturnValueOnlyDependsOnArguments();
+
   void markNeverReturnsNull();
 
   void markNeverReturnsNormally();
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/DeterminismAnalysis.java b/src/main/java/com/android/tools/r8/ir/analysis/DeterminismAnalysis.java
new file mode 100644
index 0000000..b8e6950
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/DeterminismAnalysis.java
@@ -0,0 +1,73 @@
+// 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.ir.code.IRCode;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+
+// Determine whether the given method generates the deterministic output for the given same input.
+// For now, this analysis is very conservative in the sense that it only allows methods that depend
+// on arguments. To that end, the followings are not allowed.
+//   1) any non-argument access, e.g., static-get, may result in different outputs.
+//   2) even for argument access, states of instance or array can be different in any way.
+//   3) if the current method invokes another method that is not deterministic, neither is it.
+public class DeterminismAnalysis {
+
+  public static boolean returnValueOnlyDependsOnArguments(
+      AppView<AppInfoWithLiveness> appView, IRCode code) {
+    for (Instruction instr : code.instructions()) {
+      if (instr.outValue() == null || !instr.outValue().isUsed()) {
+        continue;
+      }
+      if (instr.isStaticGet()) {
+        // Unless we model the heap and take into account the snapshot per call site.
+        return false;
+      }
+      if (instr.isInstanceGet()) {
+        // Unless we trace the state of the instance.
+        return false;
+      }
+      if (instr.isArrayGet() || instr.isArrayLength()) {
+        // Unless we trace the state of the array.
+        return false;
+      }
+      if (instr.isInvokeMethod()) {
+        DexEncodedMethod target =
+            instr.asInvokeMethod().lookupSingleTarget(appView, code.method.method.holder);
+        if (target != null && target.getOptimizationInfo().returnValueOnlyDependsOnArguments()) {
+          continue;
+        }
+        return false;
+      }
+      if (instr.isInvokeCustom() || instr.isInvokePolymorphic()) {
+        // Unless we can nail down the single target for these invocations.
+        return false;
+      }
+      if (instr.isCreatingInstanceOrArray()) {
+        // Unless we determine the new instance/array is local.
+        return false;
+      }
+      if (instr.isMoveException()) {
+        return false;
+      }
+      // isArrayPut and isFieldPut are missed as they don't have out value.
+      assert instr.isArgument()
+          || instr.isAssume()
+          || instr.isBinop()
+          || instr.isUnop()
+          || instr.isMonitor()
+          || instr.isMove()
+          || instr.isCheckCast()
+          || instr.isInstanceOf()
+          || instr.isConstInstruction()
+          || instr.isJumpInstruction()
+          || instr.isDebugInstruction()
+          : "Instruction that impacts determinism: " + instr;
+    }
+    return true;
+  }
+}
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 cc54a60..e6249ff 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
@@ -1014,4 +1014,27 @@
       }
     }
   }
+
+  public Position findFirstNonNonePosition() {
+    Instruction rightAfterArguments =
+        entryBlock().listIterator().nextUntil(instr -> !instr.isArgument());
+    Position firstNonArgumentPosition = rightAfterArguments.getPosition();
+    Set<BasicBlock> visitedBlocks = new HashSet<>();
+    while (rightAfterArguments != null) {
+      // Make sure we are not looping.
+      if (visitedBlocks.contains(rightAfterArguments.getBlock())) {
+        break;
+      }
+      visitedBlocks.add(rightAfterArguments.getBlock());
+      // The very first non-argument instruction can be chained via goto.
+      if (rightAfterArguments.isGoto()) {
+        rightAfterArguments = rightAfterArguments.asGoto().getTarget().getInstructions().getFirst();
+      } else if (rightAfterArguments.getPosition().isSome()) {
+        return rightAfterArguments.getPosition();
+      } else {
+        break;
+      }
+    }
+    return firstNonArgumentPosition;
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
index e1863b2..dbdc2dc 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
@@ -26,6 +26,7 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.DexTypeList;
 import com.android.tools.r8.graph.GraphLense;
+import com.android.tools.r8.ir.analysis.DeterminismAnalysis;
 import com.android.tools.r8.ir.analysis.InitializedClassesOnNormalExitAnalysis;
 import com.android.tools.r8.ir.analysis.TypeChecker;
 import com.android.tools.r8.ir.analysis.constant.SparseConditionalConstantPropagation;
@@ -245,8 +246,7 @@
           options.enableNestBasedAccessDesugaring ? new D8NestBasedAccessDesugaring(appView) : null;
     }
     this.deadCodeRemover = new DeadCodeRemover(appView, codeRewriter);
-    this.idempotentFunctionCallCanonicalizer =
-        new IdempotentFunctionCallCanonicalizer(appView.dexItemFactory());
+    this.idempotentFunctionCallCanonicalizer = new IdempotentFunctionCallCanonicalizer(appView);
   }
 
   public Set<DexCallSite> getDesugaredCallSites() {
@@ -612,6 +612,9 @@
     }
 
     if (Log.ENABLED) {
+      if (idempotentFunctionCallCanonicalizer != null) {
+        idempotentFunctionCallCanonicalizer.logResults();
+      }
       if (libraryMethodOverrideAnalysis != null) {
         libraryMethodOverrideAnalysis.logResults();
       }
@@ -1157,6 +1160,7 @@
         computeDynamicReturnType(feedback, method, code);
         computeInitializedClassesOnNormalExit(feedback, method, code);
         computeMayHaveSideEffects(feedback, method, code);
+        computeReturnValueOnlyDependsOnArguments(feedback, method, code);
         computeNonNullParamOrThrow(feedback, method, code);
       }
     }
@@ -1295,11 +1299,25 @@
                       instruction ->
                           instruction.instructionMayHaveSideEffects(appView, method.method.holder));
       if (!mayHaveSideEffects) {
+        // If the method is native, we don't know what could happen.
+        assert !method.accessFlags.isNative();
         feedback.methodMayNotHaveSideEffects(method);
       }
     }
   }
 
+  private void computeReturnValueOnlyDependsOnArguments(
+      OptimizationFeedback feedback, DexEncodedMethod method, IRCode code) {
+    if (!options.enableDeterminismAnalysis) {
+      return;
+    }
+    boolean returnValueOnlyDependsOnArguments =
+        DeterminismAnalysis.returnValueOnlyDependsOnArguments(appView.withLiveness(), code);
+    if (returnValueOnlyDependsOnArguments) {
+      feedback.methodReturnValueOnlyDependsOnArguments(method);
+    }
+  }
+
   // Returns true if `method` is an initializer and the enclosing class overrides the method
   // `void java.lang.Object.finalize()`.
   private boolean hasNonTrivialFinalizeMethod(DexType type) {
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedback.java b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedback.java
index bf7e94f..752f35e 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedback.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedback.java
@@ -32,6 +32,8 @@
 
   void methodMayNotHaveSideEffects(DexEncodedMethod method);
 
+  void methodReturnValueOnlyDependsOnArguments(DexEncodedMethod method);
+
   void methodNeverReturnsNull(DexEncodedMethod method);
 
   void methodNeverReturnsNormally(DexEncodedMethod method);
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDelayed.java b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDelayed.java
index 4ca780d..82f6391 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDelayed.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDelayed.java
@@ -85,6 +85,11 @@
   }
 
   @Override
+  public synchronized void methodReturnValueOnlyDependsOnArguments(DexEncodedMethod method) {
+    getOptimizationInfoForUpdating(method).markReturnValueOnlyDependsOnArguments();
+  }
+
+  @Override
   public synchronized void markAsPropagated(DexEncodedMethod method) {
     getOptimizationInfoForUpdating(method).markAsPropagated();
   }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackIgnore.java b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackIgnore.java
index 7eb3549..c0655df 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackIgnore.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackIgnore.java
@@ -48,6 +48,9 @@
   public void methodMayNotHaveSideEffects(DexEncodedMethod method) {}
 
   @Override
+  public void methodReturnValueOnlyDependsOnArguments(DexEncodedMethod method) {}
+
+  @Override
   public void methodNeverReturnsNull(DexEncodedMethod method) {}
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackSimple.java b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackSimple.java
index 44639e3..1fc7a91 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackSimple.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackSimple.java
@@ -54,6 +54,11 @@
   }
 
   @Override
+  public void methodReturnValueOnlyDependsOnArguments(DexEncodedMethod method) {
+    // Ignored.
+  }
+
+  @Override
   public void methodNeverReturnsNull(DexEncodedMethod method) {
     // Ignored.
   }
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 085137f..3ff6074 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
@@ -18,15 +18,13 @@
 import it.unimi.dsi.fastutil.objects.Object2ObjectLinkedOpenCustomHashMap;
 import it.unimi.dsi.fastutil.objects.Object2ObjectSortedMap.FastSortedEntrySet;
 import java.util.ArrayList;
-import java.util.HashSet;
 import java.util.List;
-import java.util.Set;
 
 /**
  * Canonicalize constants.
  */
 public class ConstantCanonicalizer {
-
+  // Threshold to limit the number of constant canonicalization.
   private static final int MAX_CANONICALIZED_CONSTANT = 15;
 
   public static void canonicalize(AppView<?> appView, IRCode code) {
@@ -104,7 +102,7 @@
     // Double-check the entry block does not have catch handlers.
     // Otherwise, we need to split it before moving canonicalized const-string, which may throw.
     assert !code.entryBlock().hasCatchHandlers();
-    Position firstNonNonePosition = findFirstNonNonePosition(code);
+    final Position firstNonNonePosition = code.findFirstNonNonePosition();
     FastSortedEntrySet<ConstInstruction, List<Value>> entries =
         valuesDefinedByConstant.object2ObjectEntrySet();
     // Sort the most frequently used constant first and exclude constant use only one time, such
@@ -156,30 +154,6 @@
     it.add(canonicalizedConstant);
   }
 
-  private static Position findFirstNonNonePosition(IRCode code) {
-    BasicBlock entryBlock = code.entryBlock();
-    Instruction rightAfterArguments =
-        entryBlock.listIterator().nextUntil(instr -> !instr.isArgument());
-    Position firstNonArgumentPosition = rightAfterArguments.getPosition();
-    Set<BasicBlock> visitedBlocks = new HashSet<>();
-    while (rightAfterArguments != null) {
-      // Make sure we are not looping.
-      if (visitedBlocks.contains(rightAfterArguments.getBlock())) {
-        break;
-      }
-      visitedBlocks.add(rightAfterArguments.getBlock());
-      // The very first non-argument instruction can be chained via goto.
-      if (rightAfterArguments.isGoto()) {
-        rightAfterArguments = rightAfterArguments.asGoto().getTarget().getInstructions().getFirst();
-      } else if (rightAfterArguments.getPosition().isSome()) {
-        return rightAfterArguments.getPosition();
-      } else {
-        break;
-      }
-    }
-    return firstNonArgumentPosition;
-  }
-
   private static boolean constantUsedByInvokeRange(ConstInstruction constant) {
     for (Instruction user : constant.outValue().uniqueUsers()) {
       if (user.isInvoke() && user.asInvoke().requiredArgumentRegisters() > 5) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/IdempotentFunctionCallCanonicalizer.java b/src/main/java/com/android/tools/r8/ir/optimize/IdempotentFunctionCallCanonicalizer.java
index 2e31219..9b04a16 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/IdempotentFunctionCallCanonicalizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/IdempotentFunctionCallCanonicalizer.java
@@ -3,9 +3,12 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.optimize;
 
+import static com.android.tools.r8.optimize.MemberRebindingAnalysis.isMemberVisibleFromOriginalContext;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexEncodedMethod;
 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;
@@ -13,17 +16,19 @@
 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.Position;
 import com.android.tools.r8.ir.code.Value;
-import com.google.common.collect.ImmutableSet;
+import com.android.tools.r8.logging.Log;
+import com.android.tools.r8.utils.StringUtils;
 import com.google.common.collect.Maps;
 import it.unimi.dsi.fastutil.Hash.Strategy;
+import it.unimi.dsi.fastutil.objects.Object2IntArrayMap;
+import it.unimi.dsi.fastutil.objects.Object2IntMap;
 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.
@@ -46,28 +51,36 @@
  *   // Update users of vx, vy, and vz.
  */
 public class IdempotentFunctionCallCanonicalizer {
-  private static final int MAX_CANONICALIZED_CALL = 7;
+  // Threshold to limit the number of invocation canonicalization.
+  private static final int MAX_CANONICALIZED_CALL = 15;
 
-  private final Set<DexMethod> idempotentMethods;
+  private final AppView<?> appView;
+  private final DexItemFactory factory;
 
-  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}));
+  private int numberOfLibraryCallCanonicalization = 0;
+  private int numberOfProgramCallCanonicalization = 0;
+  private Object2IntMap<Long> histogramOfCanonicalizationCandidatesPerMethod = null;
+
+  public IdempotentFunctionCallCanonicalizer(AppView<?> appView) {
+    this.appView = appView;
+    this.factory = appView.dexItemFactory();
+    if (Log.ENABLED) {
+      histogramOfCanonicalizationCandidatesPerMethod = new Object2IntArrayMap<>();
     }
-    // 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 logResults() {
+    assert Log.ENABLED;
+    Log.info(getClass(),
+        "# invoke canonicalization (library): %s", numberOfLibraryCallCanonicalization);
+    Log.info(getClass(),
+        "# invoke canonicalization (program): %s", numberOfProgramCallCanonicalization);
+    assert histogramOfCanonicalizationCandidatesPerMethod != null;
+    Log.info(getClass(), "------ histogram of invoke canonicalization candidates ------");
+    histogramOfCanonicalizationCandidatesPerMethod.forEach((length, count) -> {
+      Log.info(getClass(),
+          "%s: %s (%s)", length, StringUtils.times("*", Math.min(count, 53)), count);
+    });
   }
 
   public void canonicalize(IRCode code) {
@@ -89,6 +102,7 @@
               }
             });
 
+    DexType context = code.method.method.holder;
     // Collect invocations along with arguments.
     for (BasicBlock block : code.blocks) {
       InstructionListIterator it = block.listIterator();
@@ -98,10 +112,6 @@
           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;
@@ -110,7 +120,36 @@
         if (current.outValue().hasLocalInfo()) {
           continue;
         }
-        assert !current.inValues().isEmpty();
+        DexMethod invokedMethod = invoke.getInvokedMethod();
+        // Interested in known-to-be idempotent methods.
+        if (!factory.libraryMethodsWithReturnValueDependingOnlyOnArguments.contains(invokedMethod)
+            || !factory.libraryMethodsWithoutSideEffects.contains(invokedMethod)) {
+          if (!appView.enableWholeProgramOptimizations()) {
+            // Give up in D8
+            continue;
+          }
+          assert appView.appInfo().hasLiveness();
+          // Check if the call has a single target; that target is side effect free; and
+          // that target's output depends only on arguments.
+          DexEncodedMethod target = invoke.lookupSingleTarget(appView.withLiveness(), context);
+          if (target == null
+              || target.getOptimizationInfo().mayHaveSideEffects()
+              || !target.getOptimizationInfo().returnValueOnlyDependsOnArguments()) {
+            continue;
+          }
+          // Verify that the target method is accessible in the current context.
+          if (!isMemberVisibleFromOriginalContext(
+              appView, context, target.method.holder, target.accessFlags)) {
+            continue;
+          }
+          // Check if the call could throw a NPE as a result of the receiver being null.
+          if (current.isInvokeMethodWithReceiver()) {
+            Value receiver = current.asInvokeMethodWithReceiver().getReceiver().getAliasedValue();
+            if (receiver.getTypeLattice().isNullable()) {
+              continue;
+            }
+          }
+        }
         // 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;
@@ -134,16 +173,32 @@
       return;
     }
 
+    // Double-check the entry block does not have catch handlers.
+    assert !code.entryBlock().hasCatchHandlers();
+
     // 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();
+    if (Log.ENABLED) {
+      Long numOfCandidates = entries.stream().filter(a -> a.getValue().size() > 1).count();
+      int count = histogramOfCanonicalizationCandidatesPerMethod.getOrDefault(numOfCandidates, 0);
+      histogramOfCanonicalizationCandidatesPerMethod.put(numOfCandidates, count + 1);
+    }
     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();
+          if (Log.ENABLED) {
+            if (factory.libraryMethodsWithReturnValueDependingOnlyOnArguments
+                .contains(invoke.getInvokedMethod())) {
+              numberOfLibraryCallCanonicalization += entry.getValue().size() - 1;
+            } else {
+              numberOfProgramCallCanonicalization += entry.getValue().size() - 1;
+            }
+          }
           Value canonicalizedValue = code.createValue(
               invoke.outValue().getTypeLattice(), invoke.outValue().getLocalInfo());
           Invoke canonicalizedInvoke =
@@ -153,7 +208,16 @@
                   null,
                   canonicalizedValue,
                   invoke.inValues());
-          insertCanonicalizedInvoke(code, canonicalizedInvoke);
+          // Note that it is fine to use any position, since the invoke has no side effects, which
+          // is guaranteed not to throw. That is, we will never have a stack trace with this call.
+          // Nonetheless, here we pick the position of the very first invocation.
+          Position firstInvocationPosition = entry.getValue().get(0).definition.getPosition();
+          canonicalizedInvoke.setPosition(firstInvocationPosition);
+          if (invoke.inValues().size() > 0) {
+            insertCanonicalizedInvokeWithInValues(code, canonicalizedInvoke);
+          } else {
+            insertCanonicalizedInvokeWithoutInValues(code, canonicalizedInvoke);
+          }
           for (Value oldOutValue : entry.getValue()) {
             deadInvocations.put(oldOutValue.definition.asInvokeMethod(), canonicalizedValue);
           }
@@ -182,7 +246,8 @@
     assert code.isConsistentSSA();
   }
 
-  private static void insertCanonicalizedInvoke(IRCode code, Invoke canonicalizedInvoke) {
+  private static void insertCanonicalizedInvokeWithInValues(
+      IRCode code, Invoke canonicalizedInvoke) {
     BasicBlock entryBlock = code.entryBlock();
     // Insert the canonicalized invoke after in values.
     int numberOfInValuePassed = 0;
@@ -193,7 +258,26 @@
         numberOfInValuePassed++;
       }
       if (numberOfInValuePassed == canonicalizedInvoke.inValues().size()) {
-        canonicalizedInvoke.setPosition(current.getPosition());
+        // If this invocation uses arguments and this iteration ends in the middle of Arguments,
+        // proceed further so that Arguments can be packed first (as per entry block's properties).
+        if (it.hasNext() && it.peekNext().isArgument()) {
+          it.nextUntil(instr -> !instr.isArgument());
+        }
+        break;
+      }
+    }
+    it.add(canonicalizedInvoke);
+  }
+
+  private static void insertCanonicalizedInvokeWithoutInValues(
+      IRCode code, Invoke canonicalizedInvoke) {
+    BasicBlock entryBlock = code.entryBlock();
+    // Insert the canonicalized invocation at the start of the block right after the argument
+    // instructions.
+    InstructionListIterator it = entryBlock.listIterator();
+    while (it.hasNext()) {
+      if (!it.next().isArgument()) {
+        it.previous();
         break;
       }
     }
diff --git a/src/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index 0964666..b456b95 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -163,6 +163,7 @@
   public boolean enableClassStaticizer = true;
   public boolean enableInitializedClassesAnalysis = true;
   public boolean enableSideEffectAnalysis = true;
+  public boolean enableDeterminismAnalysis = true;
   public boolean enableServiceLoaderRewriting = true;
   // TODO(b/120138731): Enable this when it is worthwhile, e.g., combined with Class#forName.
   public boolean enableNameReflectionOptimization = false;
diff --git a/src/test/java/com/android/tools/r8/ir/analysis/DeterminismAnalysisTest.java b/src/test/java/com/android/tools/r8/ir/analysis/DeterminismAnalysisTest.java
new file mode 100644
index 0000000..1ea789d
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/analysis/DeterminismAnalysisTest.java
@@ -0,0 +1,99 @@
+// 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 static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.ir.code.IRCode;
+import java.util.function.Consumer;
+import org.junit.Test;
+
+public class DeterminismAnalysisTest extends AnalysisTestBase {
+
+  public DeterminismAnalysisTest() throws Exception {
+    super(TestClass.class.getTypeName(), TestClass.class);
+  }
+
+  @Test
+  public void testMax() throws Exception {
+    buildAndCheckIR("max", checkAnalysisResult(true));
+  }
+
+  @Test
+  public void testSget() throws Exception {
+    buildAndCheckIR("sget", checkAnalysisResult(false));
+  }
+
+  @Test
+  public void testIget() throws Exception {
+    buildAndCheckIR("iget", checkAnalysisResult(false));
+  }
+
+  @Test
+  public void testAget() throws Exception {
+    buildAndCheckIR("aget", checkAnalysisResult(false));
+  }
+
+  @Test
+  public void testAlength() throws Exception {
+    buildAndCheckIR("alength", checkAnalysisResult(false));
+  }
+
+  @Test
+  public void testCreateInstance() throws Exception {
+    buildAndCheckIR("createInstance", checkAnalysisResult(false));
+  }
+
+  @Test
+  public void testCreateArray() throws Exception {
+    buildAndCheckIR("createArray", checkAnalysisResult(false));
+  }
+
+  private Consumer<IRCode> checkAnalysisResult(boolean expectedResult) {
+    return code -> {
+      assertEquals(expectedResult,
+          DeterminismAnalysis.returnValueOnlyDependsOnArguments(appView.withLiveness(), code));
+    };
+  }
+
+  static class TestClass {
+
+    static int ID;
+    Object field;
+
+    static int max(int x, int y) {
+      return x > y ? x : y;
+    }
+
+    static int sget() {
+      return ID;
+    }
+
+    static Object iget(TestClass instance) {
+      return instance != null ? instance.field : null;
+    }
+
+    static TestClass aget(TestClass[] args, int i) {
+      return args != null ? args[i] : null;
+    }
+
+    static int alength(TestClass[] args) {
+      return args.length;
+    }
+
+    static TestClass createInstance(Object field) {
+      TestClass instance = new TestClass();
+      instance.field = field;
+      return instance;
+    }
+
+    static TestClass[] createArray(int size, Object[] fields) {
+      TestClass[] array = new TestClass[size];
+      for (int i = 0; i < size; i++) {
+        array[i].field = fields[i];
+      }
+      return array;
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/IdempotentFunctionCallCanonicalizationTest.java b/src/test/java/com/android/tools/r8/ir/optimize/IdempotentFunctionCallCanonicalizationTest.java
index 1cc0288..52c0a70 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/IdempotentFunctionCallCanonicalizationTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/IdempotentFunctionCallCanonicalizationTest.java
@@ -9,6 +9,7 @@
 import static org.junit.Assume.assumeTrue;
 
 import com.android.tools.r8.D8TestRunResult;
+import com.android.tools.r8.NeverInline;
 import com.android.tools.r8.R8TestRunResult;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
@@ -29,7 +30,40 @@
 import org.junit.runners.Parameterized;
 
 class IdempotentFunctionMain {
+  static int SEED;
+
+  @NeverInline
+  static int random(int arg) {
+    return SEED * arg;
+  }
+
+  @NeverInline
+  static int max(int x, int y) {
+    return x > y ? x : y;
+  }
+
   public static void main(String[] args) {
+    {
+      SEED = 0;
+      System.out.print(random(2));
+      SEED = 1;
+      // Should not be canonicalized.
+      System.out.print(random(2));
+
+      System.out.print(max(1, 2));
+
+      System.out.print(max(3, 2));
+      // Different order of arguments. Not canonicalized.
+      System.out.print(max(2, 3));
+      // Canonicalized.
+      System.out.print(max(3, 2));
+
+      // Canonicalized.
+      System.out.print(max(1, 2));
+
+      System.out.println();
+    }
+
     // Primitive will be boxed automatically.
     {
       Map<String, Boolean> map = new HashMap<>();
@@ -82,6 +116,7 @@
 public class IdempotentFunctionCallCanonicalizationTest extends TestBase {
   private static final Class<?> MAIN = IdempotentFunctionMain.class;
   private static final String JAVA_OUTPUT = StringUtils.lines(
+      "0223332",
       "true",
       "false",
       "8",
@@ -94,6 +129,8 @@
   private static final int EXPECTED_BOOLEAN_VALUE_OF = 2;
   private static final int EXPECTED_INTEGER_VALUE_OF = 2;
   private static final int EXPECTED_LONG_VALUE_OF = 7;
+  private static final int EXPECTED_MAX_CALLS = 3;
+  private static final int TOTAL_MAX_CALLS = 5;
 
   @Parameterized.Parameters(name = "{0}")
   public static TestParametersCollection data() {
@@ -122,7 +159,7 @@
         && method.name.toString().equals("valueOf");
   }
 
-  private long countValueOf(MethodSubject method, String descriptor) {
+  private static long countValueOf(MethodSubject method, String descriptor) {
     return Streams.stream(method.iterateInstructions(instructionSubject -> {
       if (instructionSubject.isInvoke()) {
         return isValueOf(instructionSubject.getMethod(), descriptor);
@@ -131,8 +168,18 @@
     })).count();
   }
 
+  private static long countMaxCall(MethodSubject method) {
+    return Streams.stream(method.iterateInstructions(instructionSubject -> {
+      if (instructionSubject.isInvoke()) {
+        return instructionSubject.getMethod().name.toString().equals("max");
+      }
+      return false;
+    })).count();
+  }
+
   private void test(
       TestRunResult result,
+      int expectedMaxCount,
       int expectedBooleanValueOfCount,
       int expectedIntValueOfCount,
       int expectedLongValueOfCount) throws Exception {
@@ -140,6 +187,7 @@
     ClassSubject mainClass = codeInspector.clazz(MAIN);
     MethodSubject mainMethod = mainClass.mainMethod();
     assertThat(mainMethod, isPresent());
+    assertEquals(expectedMaxCount, countMaxCall(mainMethod));
     assertEquals(expectedBooleanValueOfCount, countValueOf(mainMethod, BOOLEAN_DESCRIPTOR));
     assertEquals(expectedIntValueOfCount, countValueOf(mainMethod, INTEGER_DESCRIPTOR));
     assertEquals(expectedLongValueOfCount, countValueOf(mainMethod, LONG_DESCRIPTOR));
@@ -156,7 +204,12 @@
             .setMinApi(parameters.getRuntime())
             .run(parameters.getRuntime(), MAIN)
             .assertSuccessWithOutput(JAVA_OUTPUT);
-    test(result, EXPECTED_BOOLEAN_VALUE_OF, EXPECTED_INTEGER_VALUE_OF, EXPECTED_LONG_VALUE_OF);
+    test(
+        result,
+        TOTAL_MAX_CALLS,
+        EXPECTED_BOOLEAN_VALUE_OF,
+        EXPECTED_INTEGER_VALUE_OF,
+        EXPECTED_LONG_VALUE_OF);
 
     result =
         testForD8()
@@ -165,7 +218,12 @@
             .setMinApi(parameters.getRuntime())
             .run(parameters.getRuntime(), MAIN)
             .assertSuccessWithOutput(JAVA_OUTPUT);
-    test(result, EXPECTED_BOOLEAN_VALUE_OF, EXPECTED_INTEGER_VALUE_OF, EXPECTED_LONG_VALUE_OF);
+    test(
+        result,
+        TOTAL_MAX_CALLS,
+        EXPECTED_BOOLEAN_VALUE_OF,
+        EXPECTED_INTEGER_VALUE_OF,
+        EXPECTED_LONG_VALUE_OF);
   }
 
   @Test
@@ -175,12 +233,19 @@
             .addProgramClasses(MAIN)
             .enableInliningAnnotations()
             .addKeepMainRule(MAIN)
+            .noMinification()
             .setMinApi(parameters.getRuntime())
             .run(parameters.getRuntime(), MAIN)
             .assertSuccessWithOutput(JAVA_OUTPUT);
+    int expectedMaxCount = parameters.isCfRuntime() ? TOTAL_MAX_CALLS : EXPECTED_MAX_CALLS;
     int expectedBooleanValueOfCount = parameters.isCfRuntime() ? 6 : EXPECTED_BOOLEAN_VALUE_OF;
     int expectedIntValueOfCount = parameters.isCfRuntime() ? 5 : EXPECTED_INTEGER_VALUE_OF;
     int expectedLongValueOfCount = parameters.isCfRuntime() ? 10 : EXPECTED_LONG_VALUE_OF;
-    test(result, expectedBooleanValueOfCount, expectedIntValueOfCount, expectedLongValueOfCount);
+    test(
+        result,
+        expectedMaxCount,
+        expectedBooleanValueOfCount,
+        expectedIntValueOfCount,
+        expectedLongValueOfCount);
   }
 }