Snap for 12955189 from effe894aabea3f670902a5686673b82a76a182ba to 25Q2-release

Change-Id: I4c62f44ddc72b7f9c03b8d085946fa12018d9523

6 files changed, 500 insertions, 14 deletions

diff --git a/compiler/optimizing/code_flow_simplifier_test.cc b/compiler/optimizing/code_flow_simplifier_test.cc
index dc4268a0aa..a382f0f6f6 100644
--- a/compiler/optimizing/code_flow_simplifier_test.cc
+++ b/compiler/optimizing/code_flow_simplifier_test.cc
@@ -71,4 +71,44 @@ TEST_F(CodeFlowSimplifierTest, testSelectWithAdd) {
   EXPECT_TRUE(phi->GetBlock() == nullptr);
 }
 
+// Test `HSelect` optimization in an irreducible loop.
+TEST_F(CodeFlowSimplifierTest, testSelectInIrreducibleLoop) {
+  HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
+  auto [split, left_header, right_header, body] = CreateIrreducibleLoop(return_block);
+
+  HParameterValue* split_param = MakeParam(DataType::Type::kBool);
+  HParameterValue* bool_param = MakeParam(DataType::Type::kBool);
+  HParameterValue* n_param = MakeParam(DataType::Type::kInt32);
+
+  MakeIf(split, split_param);
+
+  HInstruction* const0 = graph_->GetIntConstant(0);
+  HInstruction* const1 = graph_->GetIntConstant(1);
+  HPhi* right_phi = MakePhi(right_header, {const0, /* placeholder */ const0});
+  HPhi* left_phi = MakePhi(left_header, {const1, right_phi});
+  HAdd* add = MakeBinOp<HAdd>(body, DataType::Type::kInt32, left_phi, const1);
+  right_phi->ReplaceInput(add, 1u);  // Update back-edge input.
+  HCondition* condition = MakeCondition(left_header, kCondGE, left_phi, n_param);
+  MakeIf(left_header, condition);
+
+  auto [if_block, then_block, else_block] = CreateDiamondPattern(body, bool_param);
+  HPhi* phi = MakePhi(body, {const1, const0});
+
+  EXPECT_TRUE(CheckGraphAndTryCodeFlowSimplifier());
+  HLoopInformation* loop_info = left_header->GetLoopInformation();
+  ASSERT_TRUE(loop_info != nullptr);
+  ASSERT_TRUE(loop_info->IsIrreducible());
+
+  EXPECT_TRUE(phi->GetBlock() == nullptr);
+  ASSERT_TRUE(if_block->GetFirstInstruction()->IsSelect());
+
+  ASSERT_EQ(if_block, add->GetBlock());  // Moved when merging blocks.
+
+  for (HBasicBlock* removed_block : {then_block, else_block, body}) {
+    uint32_t removed_block_id = removed_block->GetBlockId();
+    ASSERT_TRUE(removed_block->GetGraph() == nullptr) << removed_block_id;
+    ASSERT_FALSE(loop_info->GetBlocks().IsBitSet(removed_block_id)) << removed_block_id;
+  }
+}
+
 }  // namespace art
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index a0ec99ffc3..a8d487e51a 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -512,6 +512,8 @@ class HGraphVisualizerPrinter final : public HGraphDelegateVisitor {
 
   void VisitCondition(HCondition* condition) override {
     StartAttributeStream("bias") << condition->GetBias();
+    StartAttributeStream("emitted_at_use_site")
+        << std::boolalpha << condition->IsEmittedAtUseSite() << std::noboolalpha;
   }
 
   void VisitIf(HIf* if_instr) override {
diff --git a/compiler/optimizing/nodes_x86.h b/compiler/optimizing/nodes_x86.h
index 71c4f7aeeb..491045de99 100644
--- a/compiler/optimizing/nodes_x86.h
+++ b/compiler/optimizing/nodes_x86.h
@@ -59,6 +59,8 @@ class HX86LoadFromConstantTable final : public HExpression<2> {
     return InputAt(1)->AsConstant();
   }
 
+  bool CanBeMoved() const override { return true; }
+
   DECLARE_INSTRUCTION(X86LoadFromConstantTable);
 
  protected:
diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h
index 018ffce196..8115ea035d 100644
--- a/compiler/optimizing/optimizing_unit_test.h
+++ b/compiler/optimizing/optimizing_unit_test.h
@@ -389,6 +389,56 @@ class OptimizingUnitTestHelper {
     return {pre_header, loop};
   }
 
+  // Insert blocks for an irreducible loop before the `loop_exit`:
+  //
+  //      <loop_exit's old predecessor>
+  //                    |
+  //                  split
+  //                 /     \
+  //   left_preheader       right_preheader
+  //         |                     |
+  //    left_header <------- right_header <-+
+  //     |  |                               |
+  //     |  +------------> body ------------+
+  //     |
+  //    loop_exit
+  //
+  // Note that `left_preheader`, `right_preheader` and `body` are needed to avoid critical edges.
+  //
+  // `HGoto` instructions are added to `left_preheader`, `right_preheader`, `body`
+  // and `right_header`. To complete the control flow, the caller should add `HIf`
+  // to `split` and `left_header`.
+  //
+  // Returns `{split, left_header, right_header, body}`.
+  std::tuple<HBasicBlock*, HBasicBlock*, HBasicBlock*, HBasicBlock*> CreateIrreducibleLoop(
+      HBasicBlock* loop_exit) {
+    HBasicBlock* split = AddNewBlock();
+    HBasicBlock* left_preheader = AddNewBlock();
+    HBasicBlock* right_preheader = AddNewBlock();
+    HBasicBlock* left_header = AddNewBlock();
+    HBasicBlock* right_header = AddNewBlock();
+    HBasicBlock* body = AddNewBlock();
+
+    HBasicBlock* predecessor = loop_exit->GetSinglePredecessor();
+    predecessor->ReplaceSuccessor(loop_exit, split);
+
+    split->AddSuccessor(left_preheader);  // true successor
+    split->AddSuccessor(right_preheader);  // false successor
+    left_preheader->AddSuccessor(left_header);
+    right_preheader->AddSuccessor(right_header);
+    left_header->AddSuccessor(loop_exit);  // true successor
+    left_header->AddSuccessor(body);  // false successor
+    body->AddSuccessor(right_header);
+    right_header->AddSuccessor(left_header);
+
+    MakeGoto(left_preheader);
+    MakeGoto(right_preheader);
+    MakeGoto(body);
+    MakeGoto(right_header);
+
+    return {split, left_header, right_header, body};
+  }
+
   HBasicBlock* AddNewBlock() {
     HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph_);
     graph_->AddBlock(block);
diff --git a/compiler/optimizing/prepare_for_register_allocation.cc b/compiler/optimizing/prepare_for_register_allocation.cc
index 1eb340a9b4..c5dbab5f79 100644
--- a/compiler/optimizing/prepare_for_register_allocation.cc
+++ b/compiler/optimizing/prepare_for_register_allocation.cc
@@ -42,7 +42,8 @@ class PrepareForRegisterAllocationVisitor final : public HGraphDelegateVisitor {
   void VisitBoundType(HBoundType* bound_type) override;
   void VisitArraySet(HArraySet* instruction) override;
   void VisitClinitCheck(HClinitCheck* check) override;
-  void VisitCondition(HCondition* condition) override;
+  void VisitIf(HIf* if_instr) override;
+  void VisitSelect(HSelect* select) override;
   void VisitConstructorFence(HConstructorFence* constructor_fence) override;
   void VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) override;
   void VisitDeoptimize(HDeoptimize* deoptimize) override;
@@ -50,6 +51,7 @@ class PrepareForRegisterAllocationVisitor final : public HGraphDelegateVisitor {
 
   bool CanMoveClinitCheck(HInstruction* input, HInstruction* user) const;
   bool CanEmitConditionAt(HCondition* condition, HInstruction* user) const;
+  void TryToMoveConditionToUser(HInstruction* maybe_condition, HInstruction* user);
 
   const CompilerOptions& compiler_options_;
 };
@@ -108,6 +110,7 @@ void PrepareForRegisterAllocationVisitor::VisitDeoptimize(HDeoptimize* deoptimiz
     deoptimize->ReplaceWith(deoptimize->GuardedInput());
     deoptimize->RemoveGuard();
   }
+  TryToMoveConditionToUser(deoptimize->InputAt(0), deoptimize);
 }
 
 void PrepareForRegisterAllocationVisitor::VisitBoundsCheck(HBoundsCheck* check) {
@@ -206,37 +209,114 @@ void PrepareForRegisterAllocationVisitor::VisitClinitCheck(HClinitCheck* check)
   }
 }
 
-bool PrepareForRegisterAllocationVisitor::CanEmitConditionAt(HCondition* condition,
-                                                             HInstruction* user) const {
-  if (condition->GetNext() != user) {
+// Determine if moving `condition` to `user` would observably extend the lifetime of a reference.
+// By "observably" we understand that the reference would need to be visible to the GC for longer.
+// We're not concerned with the lifetime for the purposes of register allocation here.
+static bool ConditionMoveWouldExtendReferenceLifetime(HCondition* condition, HInstruction* user) {
+  HInstruction* lhs = condition->InputAt(0);
+  if (lhs->GetType() != DataType::Type::kReference) {
+    return false;
+  }
+  HInstruction* rhs = condition->InputAt(1);
+  DCHECK_EQ(rhs->GetType(), DataType::Type::kReference);
+  if (lhs->IsNullConstant() && rhs->IsNullConstant()) {
+    return false;
+  }
+  // Check if the last instruction with environment before `user` has all non-null
+  // inputs in the environment. If so, we would not be extending the lifetime.
+  HInstruction* instruction_with_env = user->GetPrevious();
+  while (instruction_with_env != nullptr &&
+         instruction_with_env != condition &&
+         instruction_with_env->GetEnvironment() == nullptr) {
+    DCHECK(!instruction_with_env->GetSideEffects().Includes(SideEffects::CanTriggerGC()));
+    instruction_with_env = instruction_with_env->GetPrevious();
+  }
+  if (instruction_with_env == nullptr) {
+    // No env use in the user's block. Do not search other blocks. Conservatively assume that
+    // moving the `condition` to the `user` would indeed extend the lifetime of a reference.
+    return true;
+  }
+  if (instruction_with_env == condition) {
+    // There is no instruction with an environment between `condition` and `user`, so moving
+    // the condition before the user shall not observably extend the lifetime of the reference.
     return false;
   }
+  DCHECK(instruction_with_env->HasEnvironment());
+  auto env_inputs = instruction_with_env->GetEnvironment()->GetEnvInputs();
+  auto extends_lifetime = [&](HInstruction* instruction) {
+    return !instruction->IsNullConstant() &&
+           std::find(env_inputs.begin(), env_inputs.end(), instruction) == env_inputs.end();
+  };
+  return extends_lifetime(lhs) || extends_lifetime(rhs);
+}
+
+bool PrepareForRegisterAllocationVisitor::CanEmitConditionAt(HCondition* condition,
+                                                             HInstruction* user) const {
+  DCHECK(user->IsIf() || user->IsDeoptimize() || user->IsSelect());
 
   if (GetGraph()->IsCompilingBaseline() && compiler_options_.ProfileBranches()) {
     // To do branch profiling, we cannot emit conditions at use site.
     return false;
   }
 
-  if (user->IsIf() || user->IsDeoptimize()) {
-    return true;
+  // Move only a single-user `HCondition` to the `user`.
+  if (!condition->HasOnlyOneNonEnvironmentUse()) {
+    return false;
   }
+  DCHECK(condition->GetUses().front().GetUser() == user);
 
-  if (user->IsSelect() && user->AsSelect()->GetCondition() == condition) {
-    return true;
+  if (condition->GetNext() != user) {
+    // Avoid moving across blocks if the graph has any irreducible loops.
+    if (condition->GetBlock() != user->GetBlock() && GetGraph()->HasIrreducibleLoops()) {
+      return false;
+    }
+    // Avoid extending the lifetime of references by moving the condition.
+    if (ConditionMoveWouldExtendReferenceLifetime(condition, user)) {
+      return false;
+    }
   }
 
-  return false;
+  return true;
 }
 
-void PrepareForRegisterAllocationVisitor::VisitCondition(HCondition* condition) {
-  if (condition->HasOnlyOneNonEnvironmentUse()) {
-    HInstruction* user = condition->GetUses().front().GetUser();
-    if (CanEmitConditionAt(condition, user)) {
-      condition->MarkEmittedAtUseSite();
+void PrepareForRegisterAllocationVisitor::TryToMoveConditionToUser(HInstruction* maybe_condition,
+                                                                   HInstruction* user) {
+  DCHECK(user->IsIf() || user->IsDeoptimize() || user->IsSelect());
+  if (maybe_condition->IsCondition() && CanEmitConditionAt(maybe_condition->AsCondition(), user)) {
+    if (maybe_condition->GetNext() != user) {
+      maybe_condition->MoveBefore(user);
+#ifdef ART_ENABLE_CODEGEN_x86
+      for (HInstruction* input : maybe_condition->GetInputs()) {
+        if (input->IsEmittedAtUseSite()) {
+          DCHECK(input->IsX86LoadFromConstantTable());
+          input->MoveBefore(maybe_condition);
+          HInstruction* inputs_input = input->InputAt(0);
+          DCHECK(inputs_input->IsX86ComputeBaseMethodAddress());
+          if (inputs_input->HasOnlyOneNonEnvironmentUse()) {
+            inputs_input->MoveBefore(input);
+          }
+        }
+      }
+#else  // ART_ENABLE_CODEGEN_x86
+      if (kIsDebugBuild) {
+        for (HInstruction* input : maybe_condition->GetInputs()) {
+          CHECK(!input->IsEmittedAtUseSite()) << input->DebugName() << "#" << input->GetId();
+        }
+      }
+#endif
     }
+    maybe_condition->MarkEmittedAtUseSite();
   }
 }
 
+void PrepareForRegisterAllocationVisitor::VisitIf(HIf* if_instr) {
+  TryToMoveConditionToUser(if_instr->InputAt(0), if_instr);
+}
+
+void PrepareForRegisterAllocationVisitor::VisitSelect(HSelect* select) {
+  TryToMoveConditionToUser(select->GetCondition(), select);
+}
+
 void PrepareForRegisterAllocationVisitor::VisitConstructorFence(
     HConstructorFence* constructor_fence) {
   // Trivially remove redundant HConstructorFence when it immediately follows an HNewInstance
diff --git a/compiler/optimizing/prepare_for_register_allocation_test.cc b/compiler/optimizing/prepare_for_register_allocation_test.cc
new file mode 100644
index 0000000000..a5bbae19a2
--- /dev/null
+++ b/compiler/optimizing/prepare_for_register_allocation_test.cc
@@ -0,0 +1,312 @@
+/*
+ * Copyright (C) 2025 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.
+ */
+
+#include "prepare_for_register_allocation.h"
+
+#include <gtest/gtest.h>
+
+#include "base/macros.h"
+#include "optimizing_unit_test.h"
+
+namespace art HIDDEN {
+
+class PrepareForRegisterAllocationTest
+    : public CommonCompilerTest, public OptimizingUnitTestHelper {
+ protected:
+  void RunPass() {
+    graph_->BuildDominatorTree();
+    PrepareForRegisterAllocation(graph_, *compiler_options_).Run();
+  }
+};
+
+TEST_F(PrepareForRegisterAllocationTest, MergeConditionToSelect) {
+  HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid();
+
+  HInstruction* param = MakeParam(DataType::Type::kInt32);
+  HInstruction* zero_const = graph_->GetIntConstant(0);
+  HCondition* condition = MakeCondition(ret, kCondLT, param, zero_const);
+  HSelect* select = MakeSelect(ret, condition, zero_const, param);
+
+  RunPass();
+
+  ASSERT_TRUE(condition->IsEmittedAtUseSite());
+  ASSERT_EQ(condition->GetNext(), select);
+}
+
+TEST_F(PrepareForRegisterAllocationTest, MergeConditionToDeoptimize) {
+  HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid();
+
+  HInstruction* param = MakeParam(DataType::Type::kInt32);
+  HInstruction* zero_const = graph_->GetIntConstant(0);
+  HCondition* condition = MakeCondition(ret, kCondLT, param, zero_const);
+  HDeoptimize* deopt = new (GetAllocator()) HDeoptimize(
+      GetAllocator(), condition, DeoptimizationKind::kAotInlineCache, /*dex_pc=*/ 0u);
+  AddOrInsertInstruction(ret, deopt);
+
+  RunPass();
+
+  ASSERT_TRUE(condition->IsEmittedAtUseSite());
+  ASSERT_EQ(condition->GetNext(), deopt);
+}
+
+TEST_F(PrepareForRegisterAllocationTest, MergeConditionToIf) {
+  HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid();
+  auto [start, left, right] = CreateDiamondPattern(ret);
+
+  HInstruction* param = MakeParam(DataType::Type::kInt32);
+  HInstruction* zero_const = graph_->GetIntConstant(0);
+  HCondition* condition = MakeCondition(start, kCondLT, param, zero_const);
+  HIf* start_if = MakeIf(start, condition);
+
+  RunPass();
+
+  ASSERT_TRUE(condition->IsEmittedAtUseSite());
+  ASSERT_EQ(condition->GetNext(), start_if);
+}
+
+TEST_F(PrepareForRegisterAllocationTest, MergeConditionToIfWithMove) {
+  HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid();
+  auto [start, left, right] = CreateDiamondPattern(ret);
+
+  HInstruction* param = MakeParam(DataType::Type::kInt32);
+  HInstruction* zero_const = graph_->GetIntConstant(0);
+  HCondition* condition = MakeCondition(start, kCondLT, param, zero_const);
+  HInstruction* add = MakeBinOp<HAdd>(start, DataType::Type::kInt32, param, param);
+  HIf* start_if = MakeIf(start, condition);
+
+  ASSERT_EQ(condition->GetNext(), add);
+  ASSERT_EQ(add->GetNext(), start_if);
+
+  RunPass();
+
+  ASSERT_TRUE(condition->IsEmittedAtUseSite());
+  ASSERT_EQ(add->GetNext(), condition);
+  ASSERT_EQ(condition->GetNext(), start_if);
+}
+
+TEST_F(PrepareForRegisterAllocationTest, MergeConditionToIfWithMoveFromPredecessor) {
+  HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid();
+  auto [start, left, right_end] = CreateDiamondPattern(ret);
+  auto [right_start, right_left, right_right] = CreateDiamondPattern(right_end);
+
+  HInstruction* cond_param = MakeParam(DataType::Type::kBool);
+  HInstruction* param = MakeParam(DataType::Type::kInt32);
+  HInstruction* zero_const = graph_->GetIntConstant(0);
+  HCondition* condition = MakeCondition(start, kCondLT, param, zero_const);
+  MakeIf(start, cond_param);
+  // Note: The condition for this `HIf` is in the predecessor block.
+  HIf* right_start_if = MakeIf(right_start, condition);
+
+  ASSERT_NE(condition->GetBlock(), right_start_if->GetBlock());
+
+  RunPass();
+
+  ASSERT_TRUE(condition->IsEmittedAtUseSite());
+  ASSERT_EQ(condition->GetBlock(), right_start_if->GetBlock());
+  ASSERT_EQ(condition->GetNext(), right_start_if);
+}
+
+TEST_F(PrepareForRegisterAllocationTest, MergeConditionPreventedByOtherUse) {
+  HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid();
+  auto [start, left, right] = CreateDiamondPattern(ret);
+
+  HInstruction* param = MakeParam(DataType::Type::kInt32);
+  HInstruction* zero_const = graph_->GetIntConstant(0);
+  HCondition* condition = MakeCondition(start, kCondLT, param, zero_const);
+  HIf* start_if = MakeIf(start, condition);
+
+  // Other use.
+  MakeBinOp<HAdd>(ret, DataType::Type::kInt32, param, condition);
+
+  RunPass();
+
+  ASSERT_TRUE(!condition->IsEmittedAtUseSite());
+  ASSERT_EQ(condition->GetNext(), start_if);
+}
+
+TEST_F(PrepareForRegisterAllocationTest, MergeConditionPreventedByEnvUse) {
+  HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid();
+  auto [start, left, right] = CreateDiamondPattern(ret);
+
+  HInstruction* param = MakeParam(DataType::Type::kInt32);
+  HInstruction* zero_const = graph_->GetIntConstant(0);
+  HCondition* condition = MakeCondition(start, kCondLT, param, zero_const);
+  HIf* start_if = MakeIf(start, condition);
+
+  // Environment use.
+  MakeInvokeStatic(ret, DataType::Type::kVoid, /*args=*/ {}, /*env=*/ {condition});
+
+  RunPass();
+
+  ASSERT_TRUE(!condition->IsEmittedAtUseSite());
+  ASSERT_EQ(condition->GetNext(), start_if);
+}
+
+TEST_F(PrepareForRegisterAllocationTest, MergeConditionPrevented_RefNoEnvInBlock) {
+  ScopedObjectAccess soa(Thread::Current());
+  VariableSizedHandleScope vshs(soa.Self());
+  HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid(&vshs);
+  auto [start, left, right_end] = CreateDiamondPattern(ret);
+  auto [right_start, right_left, right_right] = CreateDiamondPattern(right_end);
+
+  HInstruction* cond_param = MakeParam(DataType::Type::kBool);
+  HInstruction* param = MakeParam(DataType::Type::kReference);
+  HInstruction* null_const = graph_->GetNullConstant();
+  HCondition* condition = MakeCondition(start, kCondEQ, param, null_const);
+  MakeIf(start, cond_param);
+  // Note: The condition for this `HIf` is in the predecessor block.
+  HIf* right_start_if = MakeIf(right_start, condition);
+
+  RunPass();
+
+  ASSERT_TRUE(!condition->IsEmittedAtUseSite());
+  ASSERT_NE(condition->GetBlock(), right_start_if->GetBlock());  // Not moved to the `HIf`.
+}
+
+TEST_F(PrepareForRegisterAllocationTest, MergeCondition_RefsInEnv) {
+  ScopedObjectAccess soa(Thread::Current());
+  VariableSizedHandleScope vshs(soa.Self());
+  HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid(&vshs);
+  auto [start, left, right_end] = CreateDiamondPattern(ret);
+
+  HInstruction* param1 = MakeParam(DataType::Type::kReference);
+  HInstruction* param2 = MakeParam(DataType::Type::kReference);
+  HCondition* condition = MakeCondition(start, kCondEQ, param1, param2);
+
+  // This invoke's environment already contains `param1` and `param2`, so reordering
+  // the `condition` after the invoke would not extend their lifetime for the purpose of GC.
+  HInvoke* invoke =
+      MakeInvokeStatic(start, DataType::Type::kVoid, /*args=*/ {}, /*env=*/ {param1, param2});
+
+  HIf* start_if = MakeIf(start, condition);
+
+  ASSERT_EQ(condition->GetNext(), invoke);
+  ASSERT_EQ(invoke->GetNext(), start_if);
+
+  RunPass();
+
+  ASSERT_TRUE(condition->IsEmittedAtUseSite());
+  ASSERT_EQ(invoke->GetNext(), condition);
+  ASSERT_EQ(condition->GetNext(), start_if);
+}
+
+TEST_F(PrepareForRegisterAllocationTest, MergeCondition_RefLhsInEnv) {
+  ScopedObjectAccess soa(Thread::Current());
+  VariableSizedHandleScope vshs(soa.Self());
+  HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid(&vshs);
+  auto [start, left, right_end] = CreateDiamondPattern(ret);
+
+  HInstruction* param = MakeParam(DataType::Type::kReference);
+  HInstruction* null_const = graph_->GetNullConstant();
+  HCondition* condition = MakeCondition(start, kCondEQ, param, null_const);
+
+  // This invoke's environment already contains `param`, so reordering the `condition`
+  // after the invoke would not extend its lifetime for the purpose of GC.
+  HInvoke* invoke = MakeInvokeStatic(start, DataType::Type::kVoid, /*args=*/ {}, /*env=*/ {param});
+
+  HIf* start_if = MakeIf(start, condition);
+
+  ASSERT_EQ(condition->GetNext(), invoke);
+  ASSERT_EQ(invoke->GetNext(), start_if);
+
+  RunPass();
+
+  ASSERT_TRUE(condition->IsEmittedAtUseSite());
+  ASSERT_EQ(invoke->GetNext(), condition);
+  ASSERT_EQ(condition->GetNext(), start_if);
+}
+
+TEST_F(PrepareForRegisterAllocationTest, MergeCondition_RefRhsInEnv) {
+  ScopedObjectAccess soa(Thread::Current());
+  VariableSizedHandleScope vshs(soa.Self());
+  HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid(&vshs);
+  auto [start, left, right_end] = CreateDiamondPattern(ret);
+
+  HInstruction* param = MakeParam(DataType::Type::kReference);
+  HInstruction* null_const = graph_->GetNullConstant();
+  HCondition* condition = MakeCondition(start, kCondEQ, null_const, param);
+
+  // This invoke's environment already contains `param`, so reordering the `condition`
+  // after the invoke would not extend its lifetime for the purpose of GC.
+  HInvoke* invoke = MakeInvokeStatic(start, DataType::Type::kVoid, /*args=*/ {}, /*env=*/ {param});
+
+  HIf* start_if = MakeIf(start, condition);
+
+  ASSERT_EQ(condition->GetNext(), invoke);
+  ASSERT_EQ(invoke->GetNext(), start_if);
+
+  RunPass();
+
+  ASSERT_TRUE(condition->IsEmittedAtUseSite());
+  ASSERT_EQ(invoke->GetNext(), condition);
+  ASSERT_EQ(condition->GetNext(), start_if);
+}
+
+TEST_F(PrepareForRegisterAllocationTest, MergeConditionPrevented_RefLhsNotInEnv) {
+  ScopedObjectAccess soa(Thread::Current());
+  VariableSizedHandleScope vshs(soa.Self());
+  HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid(&vshs);
+  auto [start, left, right_end] = CreateDiamondPattern(ret);
+
+  HInstruction* param1 = MakeParam(DataType::Type::kReference);
+  HInstruction* param2 = MakeParam(DataType::Type::kReference);
+  HCondition* condition = MakeCondition(start, kCondEQ, param1, param2);
+
+  // This invoke's environment does not contain `param1`, so reordering the `condition`
+  // after the invoke would need to extend the lifetime of `param1` for the purpose of GC.
+  // We do not want to extend lifetime of references, therefore the optimization is skipped.
+  HInvoke* invoke = MakeInvokeStatic(start, DataType::Type::kVoid, /*args=*/ {}, /*env=*/ {param2});
+
+  HIf* start_if = MakeIf(start, condition);
+
+  ASSERT_EQ(condition->GetNext(), invoke);
+  ASSERT_EQ(invoke->GetNext(), start_if);
+
+  RunPass();
+
+  ASSERT_TRUE(!condition->IsEmittedAtUseSite());
+  ASSERT_EQ(condition->GetNext(), invoke);
+  ASSERT_EQ(invoke->GetNext(), start_if);
+}
+
+TEST_F(PrepareForRegisterAllocationTest, MergeConditionPrevented_RefRhsNotInEnv) {
+  ScopedObjectAccess soa(Thread::Current());
+  VariableSizedHandleScope vshs(soa.Self());
+  HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid(&vshs);
+  auto [start, left, right_end] = CreateDiamondPattern(ret);
+
+  HInstruction* param1 = MakeParam(DataType::Type::kReference);
+  HInstruction* param2 = MakeParam(DataType::Type::kReference);
+  HCondition* condition = MakeCondition(start, kCondEQ, param1, param2);
+
+  // This invoke's environment does not contain `param2`, so reordering the `condition`
+  // after the invoke would need to extend the lifetime of `param2` for the purpose of GC.
+  // We do not want to extend lifetime of references, therefore the optimization is skipped.
+  HInvoke* invoke = MakeInvokeStatic(start, DataType::Type::kVoid, /*args=*/ {}, /*env=*/ {param1});
+
+  HIf* start_if = MakeIf(start, condition);
+
+  ASSERT_EQ(condition->GetNext(), invoke);
+  ASSERT_EQ(invoke->GetNext(), start_if);
+
+  RunPass();
+
+  ASSERT_TRUE(!condition->IsEmittedAtUseSite());
+  ASSERT_EQ(condition->GetNext(), invoke);
+  ASSERT_EQ(invoke->GetNext(), start_if);
+}
+
+}  // namespace art