Run RTP after GVN to remove more NullCheck instructions

After GVN, we deduplicate instructions and we might have more
information regarding the nullability of the SSA variable. We can
run RTP to insert the BoundType instructions, which will later be
used by InstructionSimplifier to remove the NullCheck. RTP will be
run conditionally, only if GVN did at least one replacement.

It improves ~0.1% of odex size for speed compiled apps.

Bug: 369206455
Test: art/test/testrunner/testrunner.py --host --64 -b --optimizing
Change-Id: I0a4a104690b3fe9ac4118642ab9e9916dc30a9c5

9 files changed, 114 insertions, 2 deletions

diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc
index cd3b07065c..8a5a4742ba 100644
--- a/compiler/optimizing/gvn.cc
+++ b/compiler/optimizing/gvn.cc
@@ -359,7 +359,8 @@ class GlobalValueNumberer : public ValueObject {
         side_effects_(side_effects),
         sets_(graph->GetBlocks().size(), nullptr, allocator_.Adapter(kArenaAllocGvn)),
         visited_blocks_(
-            &allocator_, graph->GetBlocks().size(), /* expandable= */ false, kArenaAllocGvn) {}
+            &allocator_, graph->GetBlocks().size(), /* expandable= */ false, kArenaAllocGvn),
+        did_optimization_(false) {}
 
   bool Run();
 
@@ -403,6 +404,9 @@ class GlobalValueNumberer : public ValueObject {
   // visited/unvisited Boolean.
   ArenaBitVector visited_blocks_;
 
+  // True if GVN did at least one removal.
+  bool did_optimization_;
+
   DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer);
 };
 
@@ -415,7 +419,7 @@ bool GlobalValueNumberer::Run() {
   for (HBasicBlock* block : graph_->GetReversePostOrder()) {
     VisitBasicBlock(block);
   }
-  return true;
+  return did_optimization_;
 }
 
 void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) {
@@ -508,6 +512,7 @@ void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) {
         // Or current is used by a phi, and we don't do OrderInputs() on a phi anyway.
         current->ReplaceWith(existing);
         current->GetBlock()->RemoveInstruction(current);
+        did_optimization_ = true;
       } else {
         set->Kill(current->GetSideEffects());
         set->Add(current);
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index abc5dae016..931050855c 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -709,6 +709,9 @@ bool InstructionSimplifierVisitor::TryReplaceWithRotateRegisterSubPattern(HBinar
 
 void InstructionSimplifierVisitor::VisitNullCheck(HNullCheck* null_check) {
   HInstruction* obj = null_check->InputAt(0);
+  // Note we don't do `CanEnsureNotNullAt` here. If we do that, we may get rid of a NullCheck but
+  // what we should do instead is coalesce them. This is what GVN does, and so InstructionSimplifier
+  // doesn't do this.
   if (!obj->CanBeNull()) {
     null_check->ReplaceWith(obj);
     null_check->GetBlock()->RemoveInstruction(null_check);
diff --git a/compiler/optimizing/optimization.cc b/compiler/optimizing/optimization.cc
index ef1f36ab08..bd8fbdf1d2 100644
--- a/compiler/optimizing/optimization.cc
+++ b/compiler/optimizing/optimization.cc
@@ -55,6 +55,7 @@
 #include "licm.h"
 #include "load_store_elimination.h"
 #include "loop_optimization.h"
+#include "reference_type_propagation.h"
 #include "scheduler.h"
 #include "select_generator.h"
 #include "sharpening.h"
@@ -98,6 +99,8 @@ const char* OptimizationPassName(OptimizationPass pass) {
       return CodeSinking::kCodeSinkingPassName;
     case OptimizationPass::kConstructorFenceRedundancyElimination:
       return ConstructorFenceRedundancyElimination::kCFREPassName;
+    case OptimizationPass::kReferenceTypePropagation:
+      return ReferenceTypePropagation::kReferenceTypePropagationPassName;
     case OptimizationPass::kScheduling:
       return HInstructionScheduling::kInstructionSchedulingPassName;
     case OptimizationPass::kWriteBarrierElimination:
@@ -154,6 +157,7 @@ OptimizationPass OptimizationPassByName(const std::string& pass_name) {
   X(OptimizationPass::kInvariantCodeMotion);
   X(OptimizationPass::kLoadStoreElimination);
   X(OptimizationPass::kLoopOptimization);
+  X(OptimizationPass::kReferenceTypePropagation);
   X(OptimizationPass::kScheduling);
   X(OptimizationPass::kSelectGenerator);
   X(OptimizationPass::kSideEffectsAnalysis);
@@ -287,6 +291,10 @@ ArenaVector<HOptimization*> ConstructOptimizations(
       case OptimizationPass::kLoadStoreElimination:
         opt = new (allocator) LoadStoreElimination(graph, stats, pass_name);
         break;
+      case OptimizationPass::kReferenceTypePropagation:
+        opt = new (allocator) ReferenceTypePropagation(
+            graph, dex_compilation_unit.GetDexCache(), /* is_first_run= */ false, pass_name);
+        break;
       case OptimizationPass::kWriteBarrierElimination:
         opt = new (allocator) WriteBarrierElimination(graph, stats, pass_name);
         break;
diff --git a/compiler/optimizing/optimization.h b/compiler/optimizing/optimization.h
index 8bc9da49fc..abc4361b44 100644
--- a/compiler/optimizing/optimization.h
+++ b/compiler/optimizing/optimization.h
@@ -81,6 +81,7 @@ enum class OptimizationPass {
   kInvariantCodeMotion,
   kLoadStoreElimination,
   kLoopOptimization,
+  kReferenceTypePropagation,
   kScheduling,
   kSelectGenerator,
   kSideEffectsAnalysis,
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 89edbed54d..b15657355f 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -665,6 +665,9 @@ void OptimizingCompiler::RunOptimizations(HGraph* graph,
       OptDef(OptimizationPass::kSideEffectsAnalysis,
              "side_effects$before_gvn"),
       OptDef(OptimizationPass::kGlobalValueNumbering),
+      OptDef(OptimizationPass::kReferenceTypePropagation,
+             "reference_type_propagation$after_gvn",
+             OptimizationPass::kGlobalValueNumbering),
       // Simplification (TODO: only if GVN occurred).
       OptDef(OptimizationPass::kSelectGenerator),
       OptDef(OptimizationPass::kConstantFolding,
diff --git a/test/2283-checker-remove-null-check/expected-stderr.txt b/test/2283-checker-remove-null-check/expected-stderr.txt
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/test/2283-checker-remove-null-check/expected-stderr.txt
diff --git a/test/2283-checker-remove-null-check/expected-stdout.txt b/test/2283-checker-remove-null-check/expected-stdout.txt
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/test/2283-checker-remove-null-check/expected-stdout.txt
diff --git a/test/2283-checker-remove-null-check/info.txt b/test/2283-checker-remove-null-check/info.txt
new file mode 100644
index 0000000000..909b15166c
--- /dev/null
+++ b/test/2283-checker-remove-null-check/info.txt
@@ -0,0 +1 @@
+Tests we remove null checks for known-not-null SSA variables after GVN
diff --git a/test/2283-checker-remove-null-check/src/Main.java b/test/2283-checker-remove-null-check/src/Main.java
new file mode 100644
index 0000000000..cbc7ed02d8
--- /dev/null
+++ b/test/2283-checker-remove-null-check/src/Main.java
@@ -0,0 +1,91 @@
+/*
+ * Copyright (C) 2024 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.
+ */
+
+public class Main {
+    public static void main(String[] args) {
+        $noinline$testReturnValueOrDefault();
+    }
+
+    private class InnerObject {
+        int value;
+    }
+
+    static InnerObject inner_obj;
+
+    // GVN removes the second `inner_obj` get.
+    /// CHECK-START: int Main.$noinline$returnValueOrDefault() GVN (before)
+    /// CHECK: StaticFieldGet field_name:Main.inner_obj
+    /// CHECK: StaticFieldGet field_name:Main.inner_obj
+
+    /// CHECK-START: int Main.$noinline$returnValueOrDefault() GVN (after)
+    /// CHECK:     StaticFieldGet field_name:Main.inner_obj
+    /// CHECK-NOT: StaticFieldGet field_name:Main.inner_obj
+
+    // Consistency check: No BoundTypes existed before.
+    /// CHECK-START: int Main.$noinline$returnValueOrDefault() reference_type_propagation$after_gvn (before)
+    /// CHECK-NOT: BoundType
+
+    // Consistency check: Only one null check.
+    /// CHECK-START: int Main.$noinline$returnValueOrDefault() reference_type_propagation$after_gvn (before)
+    /// CHECK:     NullCheck
+    /// CHECK-NOT: NullCheck
+
+    // RTP will add a BoundType between the `StaticFieldGet` and `NullCheck`.
+
+    /// CHECK-START: int Main.$noinline$returnValueOrDefault() reference_type_propagation$after_gvn (before)
+    /// CHECK: <<SFG:l\d+>> StaticFieldGet field_name:Main.inner_obj
+    /// CHECK:              NullCheck [<<SFG>>]
+
+    /// CHECK-START: int Main.$noinline$returnValueOrDefault() reference_type_propagation$after_gvn (after)
+    /// CHECK: <<SFG:l\d+>> StaticFieldGet field_name:Main.inner_obj
+    /// CHECK: <<BT:l\d+>>  BoundType [<<SFG>>]
+    /// CHECK:              NullCheck [<<BT>>]
+
+    // Finally, InstructionSimplifier can remove the NullCheck
+
+    /// CHECK-START: int Main.$noinline$returnValueOrDefault() instruction_simplifier$after_gvn (before)
+    /// CHECK:     NullCheck
+    /// CHECK-NOT: NullCheck
+
+    /// CHECK-START: int Main.$noinline$returnValueOrDefault() instruction_simplifier$after_gvn (after)
+    /// CHECK-NOT: NullCheck
+    static int $noinline$returnValueOrDefault() {
+        if (inner_obj != null) {
+            return inner_obj.value;
+        } else {
+            return -123;
+        }
+    }
+
+    static void $noinline$testReturnValueOrDefault() {
+        inner_obj = null;
+        $noinline$assertIntEquals(-123, $noinline$returnValueOrDefault());
+
+        Main m = new Main();
+        inner_obj = m.new InnerObject();
+        inner_obj.value = 0;
+        $noinline$assertIntEquals(0, $noinline$returnValueOrDefault());
+
+        inner_obj.value = 1000;
+        $noinline$assertIntEquals(1000, $noinline$returnValueOrDefault());
+    }
+
+    public static void $noinline$assertIntEquals(int expected, int result) {
+        if (expected != result) {
+            throw new Error("Expected: " + expected + ", found: " + result);
+        }
+    }
+}