Support for inlining virtual and interface calls.

Also had to change the pass order to get reference type propagation
before the inliner.

Change-Id: I4bf3bbb2d17c7d9cab632cfdd96adad8368bdfea
diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc
index 83f8d83..b26afd1 100644
--- a/compiler/optimizing/inliner.cc
+++ b/compiler/optimizing/inliner.cc
@@ -27,6 +27,7 @@
 #include "mirror/class_loader.h"
 #include "mirror/dex_cache.h"
 #include "nodes.h"
+#include "reference_type_propagation.h"
 #include "register_allocator.h"
 #include "ssa_phi_elimination.h"
 #include "scoped_thread_state_change.h"
@@ -57,7 +58,7 @@
     next_block = (i == blocks.Size() - 1) ? nullptr : blocks.Get(i + 1);
     for (HInstruction* instruction = block->GetFirstInstruction(); instruction != nullptr;) {
       HInstruction* next = instruction->GetNext();
-      HInvokeStaticOrDirect* call = instruction->AsInvokeStaticOrDirect();
+      HInvoke* call = instruction->AsInvoke();
       // As long as the call is not intrinsified, it is worth trying to inline.
       if (call != nullptr && call->GetIntrinsic() == Intrinsics::kNone) {
         // We use the original invoke type to ensure the resolution of the called method
@@ -76,6 +77,79 @@
   }
 }
 
+static bool IsMethodOrDeclaringClassFinal(ArtMethod* method)
+    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  return method->IsFinal() || method->GetDeclaringClass()->IsFinal();
+}
+
+/**
+ * Given the `resolved_method` looked up in the dex cache, try to find
+ * the actual runtime target of an interface or virtual call.
+ * Return nullptr if the runtime target cannot be proven.
+ */
+static ArtMethod* FindVirtualOrInterfaceTarget(HInvoke* invoke, ArtMethod* resolved_method)
+    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  if (IsMethodOrDeclaringClassFinal(resolved_method)) {
+    // No need to lookup further, the resolved method will be the target.
+    return resolved_method;
+  }
+
+  HInstruction* receiver = invoke->InputAt(0);
+  if (receiver->IsNullCheck()) {
+    // Due to multiple levels of inlining within the same pass, it might be that
+    // null check does not have the reference type of the actual receiver.
+    receiver = receiver->InputAt(0);
+  }
+  ReferenceTypeInfo info = receiver->GetReferenceTypeInfo();
+  if (info.IsTop()) {
+    // We have no information on the receiver.
+    return nullptr;
+  } else if (!info.IsExact()) {
+    // We currently only support inlining with known receivers.
+    // TODO: Remove this check, we should be able to inline final methods
+    // on unknown receivers.
+    return nullptr;
+  } else if (info.GetTypeHandle()->IsInterface()) {
+    // Statically knowing that the receiver has an interface type cannot
+    // help us find what is the target method.
+    return nullptr;
+  }
+
+  ClassLinker* cl = Runtime::Current()->GetClassLinker();
+  size_t pointer_size = cl->GetImagePointerSize();
+  if (invoke->IsInvokeInterface()) {
+    resolved_method = info.GetTypeHandle()->FindVirtualMethodForInterface(
+        resolved_method, pointer_size);
+  } else {
+    DCHECK(invoke->IsInvokeVirtual());
+    resolved_method = info.GetTypeHandle()->FindVirtualMethodForVirtual(
+        resolved_method, pointer_size);
+  }
+
+  if (resolved_method == nullptr) {
+    // The information we had on the receiver was not enough to find
+    // the target method. Since we check above the exact type of the receiver,
+    // the only reason this can happen is an IncompatibleClassChangeError.
+    return nullptr;
+  } else if (resolved_method->IsAbstract()) {
+    // The information we had on the receiver was not enough to find
+    // the target method. Since we check above the exact type of the receiver,
+    // the only reason this can happen is an IncompatibleClassChangeError.
+    return nullptr;
+  } else if (IsMethodOrDeclaringClassFinal(resolved_method)) {
+    // A final method has to be the target method.
+    return resolved_method;
+  } else if (info.IsExact()) {
+    // If we found a method and the receiver's concrete type is statically
+    // known, we know for sure the target.
+    return resolved_method;
+  } else {
+    // Even if we did find a method, the receiver type was not enough to
+    // statically find the runtime target.
+    return nullptr;
+  }
+}
+
 bool HInliner::TryInline(HInvoke* invoke_instruction,
                          uint32_t method_index,
                          InvokeType invoke_type) const {
@@ -83,19 +157,34 @@
   const DexFile& caller_dex_file = *caller_compilation_unit_.GetDexFile();
   VLOG(compiler) << "Try inlining " << PrettyMethod(method_index, caller_dex_file);
 
-  StackHandleScope<3> hs(soa.Self());
-  Handle<mirror::DexCache> dex_cache(
-      hs.NewHandle(caller_compilation_unit_.GetClassLinker()->FindDexCache(caller_dex_file)));
-  Handle<mirror::ClassLoader> class_loader(hs.NewHandle(
-      soa.Decode<mirror::ClassLoader*>(caller_compilation_unit_.GetClassLoader())));
-  ArtMethod* resolved_method(compiler_driver_->ResolveMethod(
-      soa, dex_cache, class_loader, &caller_compilation_unit_, method_index, invoke_type));
+  ArtMethod* resolved_method = nullptr;
+  {
+    // Don't keep this handle scope on stack, otherwise we cannot do a reference type
+    // propagation while inlining.
+    StackHandleScope<2> hs(soa.Self());
+    Handle<mirror::DexCache> dex_cache(
+        hs.NewHandle(caller_compilation_unit_.GetClassLinker()->FindDexCache(caller_dex_file)));
+    Handle<mirror::ClassLoader> class_loader(hs.NewHandle(
+        soa.Decode<mirror::ClassLoader*>(caller_compilation_unit_.GetClassLoader())));
+    resolved_method = compiler_driver_->ResolveMethod(
+        soa, dex_cache, class_loader, &caller_compilation_unit_, method_index, invoke_type);
+  }
 
   if (resolved_method == nullptr) {
     VLOG(compiler) << "Method cannot be resolved " << PrettyMethod(method_index, caller_dex_file);
     return false;
   }
 
+  if (!invoke_instruction->IsInvokeStaticOrDirect()) {
+    resolved_method = FindVirtualOrInterfaceTarget(invoke_instruction, resolved_method);
+    if (resolved_method == nullptr) {
+      VLOG(compiler) << "Interface or virtual call to "
+                     << PrettyMethod(method_index, caller_dex_file)
+                     << "could not be statically determined";
+      return false;
+    }
+  }
+
   bool same_dex_file = true;
   const DexFile& outer_dex_file = *outer_compilation_unit_.GetDexFile();
   if (resolved_method->GetDexFile()->GetLocation().compare(outer_dex_file.GetLocation()) != 0) {
@@ -238,11 +327,13 @@
   // Run simple optimizations on the graph.
   HDeadCodeElimination dce(callee_graph, stats_);
   HConstantFolding fold(callee_graph);
+  ReferenceTypePropagation type_propagation(callee_graph, handles_);
   InstructionSimplifier simplify(callee_graph, stats_);
 
   HOptimization* optimizations[] = {
     &dce,
     &fold,
+    &type_propagation,
     &simplify,
   };
 
@@ -256,6 +347,7 @@
                      outer_compilation_unit_,
                      dex_compilation_unit,
                      compiler_driver_,
+                     handles_,
                      stats_,
                      depth_ + 1);
     inliner.Run();
diff --git a/compiler/optimizing/inliner.h b/compiler/optimizing/inliner.h
index b86c1ed..ca71332 100644
--- a/compiler/optimizing/inliner.h
+++ b/compiler/optimizing/inliner.h
@@ -34,13 +34,15 @@
            const DexCompilationUnit& outer_compilation_unit,
            const DexCompilationUnit& caller_compilation_unit,
            CompilerDriver* compiler_driver,
+           StackHandleScopeCollection* handles,
            OptimizingCompilerStats* stats,
            size_t depth = 0)
       : HOptimization(outer_graph, true, kInlinerPassName, stats),
         outer_compilation_unit_(outer_compilation_unit),
         caller_compilation_unit_(caller_compilation_unit),
         compiler_driver_(compiler_driver),
-        depth_(depth) {}
+        depth_(depth),
+        handles_(handles) {}
 
   void Run() OVERRIDE;
 
@@ -57,6 +59,7 @@
   const DexCompilationUnit& caller_compilation_unit_;
   CompilerDriver* const compiler_driver_;
   const size_t depth_;
+  StackHandleScopeCollection* const handles_;
 
   DISALLOW_COPY_AND_ASSIGN(HInliner);
 };
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index f6ef2f7..bf0b9fa 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -326,7 +326,7 @@
   InstructionSimplifier simplify1(graph, stats);
   HBooleanSimplifier boolean_simplify(graph);
 
-  HInliner inliner(graph, dex_compilation_unit, dex_compilation_unit, driver, stats);
+  HInliner inliner(graph, dex_compilation_unit, dex_compilation_unit, driver, handles, stats);
 
   HConstantFolding fold2(graph, "constant_folding_after_inlining");
   SideEffectsAnalysis side_effects(graph);
@@ -335,6 +335,8 @@
   BoundsCheckElimination bce(graph);
   ReferenceTypePropagation type_propagation(graph, handles);
   InstructionSimplifier simplify2(graph, stats, "instruction_simplifier_after_types");
+  InstructionSimplifier simplify3(graph, stats, "last_instruction_simplifier");
+  ReferenceTypePropagation type_propagation2(graph, handles);
 
   IntrinsicsRecognizer intrinsics(graph, driver);
 
@@ -343,7 +345,12 @@
     &dce1,
     &fold1,
     &simplify1,
+    &type_propagation,
+    &simplify2,
     &inliner,
+    // Run another type propagation phase: inlining will open up more opprotunities
+    // to remove checkast/instanceof and null checks.
+    &type_propagation2,
     // BooleanSimplifier depends on the InstructionSimplifier removing redundant
     // suspend checks to recognize empty blocks.
     &boolean_simplify,
@@ -352,8 +359,7 @@
     &gvn,
     &licm,
     &bce,
-    &type_propagation,
-    &simplify2,
+    &simplify3,
     &dce2,
   };
 
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index 4f1f457..4edadef 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -166,31 +166,34 @@
   }
 }
 
-void ReferenceTypePropagation::SetClassAsTypeInfo(HInstruction* instr, mirror::Class* klass) {
+void ReferenceTypePropagation::SetClassAsTypeInfo(HInstruction* instr,
+                                                  mirror::Class* klass,
+                                                  bool is_exact) {
   if (klass != nullptr) {
     ScopedObjectAccess soa(Thread::Current());
     MutableHandle<mirror::Class> handle = handles_->NewHandle(klass);
-    instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(handle, true));
+    instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(handle, is_exact));
   }
 }
 
 void ReferenceTypePropagation::UpdateReferenceTypeInfo(HInstruction* instr,
                                                        uint16_t type_idx,
-                                                       const DexFile& dex_file) {
+                                                       const DexFile& dex_file,
+                                                       bool is_exact) {
   DCHECK_EQ(instr->GetType(), Primitive::kPrimNot);
 
   ScopedObjectAccess soa(Thread::Current());
   mirror::DexCache* dex_cache = Runtime::Current()->GetClassLinker()->FindDexCache(dex_file);
   // Get type from dex cache assuming it was populated by the verifier.
-  SetClassAsTypeInfo(instr, dex_cache->GetResolvedType(type_idx));
+  SetClassAsTypeInfo(instr, dex_cache->GetResolvedType(type_idx), is_exact);
 }
 
 void ReferenceTypePropagation::VisitNewInstance(HNewInstance* instr) {
-  UpdateReferenceTypeInfo(instr, instr->GetTypeIndex(), instr->GetDexFile());
+  UpdateReferenceTypeInfo(instr, instr->GetTypeIndex(), instr->GetDexFile(), /* is_exact */ true);
 }
 
 void ReferenceTypePropagation::VisitNewArray(HNewArray* instr) {
-  UpdateReferenceTypeInfo(instr, instr->GetTypeIndex(), instr->GetDexFile());
+  UpdateReferenceTypeInfo(instr, instr->GetTypeIndex(), instr->GetDexFile(), /* is_exact */ true);
 }
 
 void ReferenceTypePropagation::UpdateFieldAccessTypeInfo(HInstruction* instr,
@@ -206,7 +209,7 @@
   ArtField* field = cl->GetResolvedField(info.GetFieldIndex(), dex_cache);
   DCHECK(field != nullptr);
   mirror::Class* klass = field->GetType<false>();
-  SetClassAsTypeInfo(instr, klass);
+  SetClassAsTypeInfo(instr, klass, /* is_exact */ false);
 }
 
 void ReferenceTypePropagation::VisitInstanceFieldGet(HInstanceFieldGet* instr) {
diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h
index 74e425f..0a1d4c4 100644
--- a/compiler/optimizing/reference_type_propagation.h
+++ b/compiler/optimizing/reference_type_propagation.h
@@ -46,14 +46,17 @@
   void VisitPhi(HPhi* phi);
   void VisitBasicBlock(HBasicBlock* block);
   void UpdateFieldAccessTypeInfo(HInstruction* instr, const FieldInfo& info);
-  void SetClassAsTypeInfo(HInstruction* instr, mirror::Class* klass);
+  void SetClassAsTypeInfo(HInstruction* instr, mirror::Class* klass, bool is_exact);
 
   void UpdateBoundType(HBoundType* bound_type) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
   void UpdatePhi(HPhi* phi) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   void BoundTypeForIfNotNull(HBasicBlock* block);
   void BoundTypeForIfInstanceOf(HBasicBlock* block);
-  void UpdateReferenceTypeInfo(HInstruction* instr, uint16_t type_idx, const DexFile& dex_file);
+  void UpdateReferenceTypeInfo(HInstruction* instr,
+                               uint16_t type_idx,
+                               const DexFile& dex_file,
+                               bool is_exact);
   void VisitInstanceFieldGet(HInstanceFieldGet* instr);
   void VisitStaticFieldGet(HStaticFieldGet* instr);
 
diff --git a/test/444-checker-nce/src/Main.java b/test/444-checker-nce/src/Main.java
index 6ac0cad..32122e4 100644
--- a/test/444-checker-nce/src/Main.java
+++ b/test/444-checker-nce/src/Main.java
@@ -27,37 +27,37 @@
     return m.g();
   }
 
-  /// CHECK-START: Main Main.thisTest() instruction_simplifier (before)
+  /// CHECK-START: Main Main.thisTest() ssa_builder (after)
   /// CHECK:         NullCheck
   /// CHECK:         InvokeStaticOrDirect
 
-  /// CHECK-START: Main Main.thisTest() instruction_simplifier (after)
+  /// CHECK-START: Main Main.thisTest() instruction_simplifier_after_types (after)
   /// CHECK-NOT:     NullCheck
   /// CHECK:         InvokeStaticOrDirect
   public Main thisTest() {
     return g();
   }
 
-  /// CHECK-START: Main Main.newInstanceRemoveTest() instruction_simplifier (before)
+  /// CHECK-START: Main Main.newInstanceRemoveTest() ssa_builder (after)
   /// CHECK:         NewInstance
   /// CHECK:         NullCheck
   /// CHECK:         InvokeStaticOrDirect
   /// CHECK:         NullCheck
   /// CHECK:         InvokeStaticOrDirect
 
-  /// CHECK-START: Main Main.newInstanceRemoveTest() instruction_simplifier (after)
+  /// CHECK-START: Main Main.newInstanceRemoveTest() instruction_simplifier_after_types (after)
   /// CHECK-NOT:     NullCheck
   public Main newInstanceRemoveTest() {
     Main m = new Main();
     return m.g();
   }
 
-  /// CHECK-START: Main Main.newArrayRemoveTest() instruction_simplifier (before)
+  /// CHECK-START: Main Main.newArrayRemoveTest() ssa_builder (after)
   /// CHECK:         NewArray
   /// CHECK:         NullCheck
   /// CHECK:         ArrayGet
 
-  /// CHECK-START: Main Main.newArrayRemoveTest() instruction_simplifier (after)
+  /// CHECK-START: Main Main.newArrayRemoveTest() instruction_simplifier_after_types (after)
   /// CHECK:         NewArray
   /// CHECK-NOT:     NullCheck
   /// CHECK:         ArrayGet
@@ -178,10 +178,10 @@
     return n.g();
   }
 
-  /// CHECK-START: Main Main.scopeRemoveTest(int, Main) instruction_simplifier (before)
+  /// CHECK-START: Main Main.scopeRemoveTest(int, Main) ssa_builder (after)
   /// CHECK:         NullCheck
 
-  /// CHECK-START: Main Main.scopeRemoveTest(int, Main) instruction_simplifier (after)
+  /// CHECK-START: Main Main.scopeRemoveTest(int, Main) instruction_simplifier_after_types (after)
   /// CHECK-NOT:     NullCheck
   public Main scopeRemoveTest(int count, Main a) {
     Main m = null;
diff --git a/test/458-checker-instruction-simplification/src/Main.java b/test/458-checker-instruction-simplification/src/Main.java
index ad5fc8e..ef18f64 100644
--- a/test/458-checker-instruction-simplification/src/Main.java
+++ b/test/458-checker-instruction-simplification/src/Main.java
@@ -933,18 +933,18 @@
    * remove the second.
    */
 
-  /// CHECK-START: boolean Main.NotNotBool(boolean) instruction_simplifier_after_types (before)
+  /// CHECK-START: boolean Main.NotNotBool(boolean) last_instruction_simplifier (before)
   /// CHECK-DAG:     <<Arg:z\d+>>       ParameterValue
   /// CHECK-DAG:     <<NotArg:z\d+>>    BooleanNot [<<Arg>>]
   /// CHECK-DAG:     <<NotNotArg:z\d+>> BooleanNot [<<NotArg>>]
   /// CHECK-DAG:                        Return [<<NotNotArg>>]
 
-  /// CHECK-START: boolean Main.NotNotBool(boolean) instruction_simplifier_after_types (after)
+  /// CHECK-START: boolean Main.NotNotBool(boolean) last_instruction_simplifier (after)
   /// CHECK-DAG:     <<Arg:z\d+>>       ParameterValue
   /// CHECK-DAG:                        BooleanNot [<<Arg>>]
   /// CHECK-DAG:                        Return [<<Arg>>]
 
-  /// CHECK-START: boolean Main.NotNotBool(boolean) instruction_simplifier_after_types (after)
+  /// CHECK-START: boolean Main.NotNotBool(boolean) last_instruction_simplifier (after)
   /// CHECK:                            BooleanNot
   /// CHECK-NOT:                        BooleanNot
 
diff --git a/test/490-checker-inline/expected.txt b/test/490-checker-inline/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/490-checker-inline/expected.txt
diff --git a/test/490-checker-inline/info.txt b/test/490-checker-inline/info.txt
new file mode 100644
index 0000000..0e42d77
--- /dev/null
+++ b/test/490-checker-inline/info.txt
@@ -0,0 +1 @@
+Check that we inline virtual and interface calls.
diff --git a/test/490-checker-inline/src/Main.java b/test/490-checker-inline/src/Main.java
new file mode 100644
index 0000000..21a0189
--- /dev/null
+++ b/test/490-checker-inline/src/Main.java
@@ -0,0 +1,52 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+interface Itf {
+  public void invokeInterface();
+}
+
+public class Main implements Itf {
+
+  public void invokeInterface () {
+  }
+
+  public void invokeVirtual() {
+  }
+
+  public static Main createMain() {
+    return new Main();
+  }
+
+  public static Itf createItf() {
+    return new Main();
+  }
+
+  /// CHECK-START: void Main.testMethod() inliner (before)
+  /// CHECK-DAG:     InvokeVirtual
+  /// CHECK-DAG:     InvokeInterface
+
+  /// CHECK-START: void Main.testMethod() inliner (after)
+  /// CHECK-NOT:     Invoke{{.*}}
+
+  public static void testMethod() {
+    createMain().invokeVirtual();
+    createItf().invokeInterface();
+  }
+
+  public static void main(String[] args) {
+    testMethod();
+  }
+}