summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
author Vladimir Marko <vmarko@google.com> 2025-01-14 09:13:32 +0000
committer VladimĂ­r Marko <vmarko@google.com> 2025-01-22 01:19:58 -0800
commit6d6d26f1febbfe50abe7eec7e8496375532369b9 (patch)
tree4b5b35b40daf4eaa61d05b05dcc94ec8fed557a7
parent8d38ee1b7abefff2de3da7492ebee4cd468868a3 (diff)
Optimizing: Allow moving `HCondition` to use site.
Test: m test-art-host-gtest Test: testrunner.py --host --optimizing Bug: 358519867 Change-Id: I5b49f27c09582dc42eba8b6650a7032fad0ff14d
-rw-r--r--compiler/Android.bp1
-rw-r--r--compiler/optimizing/graph_visualizer.cc2
-rw-r--r--compiler/optimizing/nodes_x86.h2
-rw-r--r--compiler/optimizing/prepare_for_register_allocation.cc108
-rw-r--r--compiler/optimizing/prepare_for_register_allocation_test.cc312
-rw-r--r--test/735-checker-condition-merging/expected-stderr.txt0
-rw-r--r--test/735-checker-condition-merging/expected-stdout.txt20
-rw-r--r--test/735-checker-condition-merging/info.txt1
-rw-r--r--test/735-checker-condition-merging/src/Main.java285
9 files changed, 717 insertions, 14 deletions
diff --git a/compiler/Android.bp b/compiler/Android.bp
index 0a1af65a97..c904746435 100644
--- a/compiler/Android.bp
+++ b/compiler/Android.bp
@@ -479,6 +479,7 @@ art_cc_defaults {
"optimizing/nodes_test.cc",
"optimizing/nodes_vector_test.cc",
"optimizing/parallel_move_test.cc",
+ "optimizing/prepare_for_register_allocation_test.cc",
"optimizing/pretty_printer_test.cc",
"optimizing/reference_type_propagation_test.cc",
"optimizing/side_effects_test.cc",
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/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
diff --git a/test/735-checker-condition-merging/expected-stderr.txt b/test/735-checker-condition-merging/expected-stderr.txt
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/test/735-checker-condition-merging/expected-stderr.txt
diff --git a/test/735-checker-condition-merging/expected-stdout.txt b/test/735-checker-condition-merging/expected-stdout.txt
new file mode 100644
index 0000000000..4071f36257
--- /dev/null
+++ b/test/735-checker-condition-merging/expected-stdout.txt
@@ -0,0 +1,20 @@
+IfXLtzAElseB(-7): A
+IfXLtzAElseB(42): B
+IfXLtzAElseB_Move(-7): A
+IfXLtzAElseB_Move(42): B
+IfXLtzAElseB_EnvUse(-7): A
+IfXLtzAElseB_EnvUse(42): B
+IfXNullAElseB(null): A
+IfXNullAElseB(new Object()): B
+IfXNullAElseB_Move(null): A
+IfXNullAElseB_Move(new Object()): B
+IfXNullAElseB_EnvUse(null): A
+IfXNullAElseB_EnvUse(new Object()): B
+IfXNullAElseB_RefNoEnvInBlock(null, true): A
+IfXNullAElseB_RefNoEnvInBlock(new Object(), true): B
+IfXNullAElseB_RefNoEnvInBlock(null, false): C
+IfXNullAElseB_RefNoEnvInBlock(new Object(), false): C
+IfLt7_0AElseB_86LoadFromConstantTable(2.0, true): A
+IfLt7_0AElseB_86LoadFromConstantTable(10.0, true): B
+IfLt7_0AElseB_86LoadFromConstantTable(2.0, false): C
+IfLt7_0AElseB_86LoadFromConstantTable(10.0, false): C
diff --git a/test/735-checker-condition-merging/info.txt b/test/735-checker-condition-merging/info.txt
new file mode 100644
index 0000000000..30790ab52f
--- /dev/null
+++ b/test/735-checker-condition-merging/info.txt
@@ -0,0 +1 @@
+Test for merging `HCondition` to the user with the "emited at use site" approach.
diff --git a/test/735-checker-condition-merging/src/Main.java b/test/735-checker-condition-merging/src/Main.java
new file mode 100644
index 0000000000..98e9c4cdfe
--- /dev/null
+++ b/test/735-checker-condition-merging/src/Main.java
@@ -0,0 +1,285 @@
+/*
+ * 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.
+ */
+
+public class Main {
+ private int intField;
+
+ public static void main(String[] args) {
+ System.out.print("IfXLtzAElseB(-7): ");
+ $noinline$IfXLtzAElseB(-7);
+ System.out.print("IfXLtzAElseB(42): ");
+ $noinline$IfXLtzAElseB(42);
+
+ System.out.print("IfXLtzAElseB_Move(-7): ");
+ new Main().$noinline$IfXLtzAElseB_Move(-7);
+ System.out.print("IfXLtzAElseB_Move(42): ");
+ new Main().$noinline$IfXLtzAElseB_Move(42);
+
+ System.out.print("IfXLtzAElseB_EnvUse(-7): ");
+ $noinline$IfXLtzAElseB_EnvUse(-7);
+ System.out.print("IfXLtzAElseB_EnvUse(42): ");
+ $noinline$IfXLtzAElseB_EnvUse(42);
+
+ System.out.print("IfXNullAElseB(null): ");
+ $noinline$IfXNullAElseB(null);
+ System.out.print("IfXNullAElseB(new Object()): ");
+ $noinline$IfXNullAElseB(new Object());
+
+ System.out.print("IfXNullAElseB_Move(null): ");
+ new Main().$noinline$IfXNullAElseB_Move(null);
+ System.out.print("IfXNullAElseB_Move(new Object()): ");
+ new Main().$noinline$IfXNullAElseB_Move(new Object());
+
+ System.out.print("IfXNullAElseB_EnvUse(null): ");
+ new Main().$noinline$IfXNullAElseB_EnvUse(null);
+ System.out.print("IfXNullAElseB_EnvUse(new Object()): ");
+ new Main().$noinline$IfXNullAElseB_EnvUse(new Object());
+
+ System.out.print("IfXNullAElseB_RefNoEnvInBlock(null, true): ");
+ new Main().$noinline$IfXNullAElseB_RefNoEnvInBlock(null, true);
+ System.out.print("IfXNullAElseB_RefNoEnvInBlock(new Object(), true): ");
+ new Main().$noinline$IfXNullAElseB_RefNoEnvInBlock(new Object(), true);
+ System.out.print("IfXNullAElseB_RefNoEnvInBlock(null, false): ");
+ new Main().$noinline$IfXNullAElseB_RefNoEnvInBlock(null, false);
+ System.out.print("IfXNullAElseB_RefNoEnvInBlock(new Object(), false): ");
+ new Main().$noinline$IfXNullAElseB_RefNoEnvInBlock(new Object(), false);
+
+ System.out.print("IfLt7_0AElseB_86LoadFromConstantTable(2.0, true): ");
+ new Main().$noinline$IfLt7_0AElseB_86LoadFromConstantTable(2.0, true);
+ System.out.print("IfLt7_0AElseB_86LoadFromConstantTable(10.0, true): ");
+ new Main().$noinline$IfLt7_0AElseB_86LoadFromConstantTable(10.0, true);
+ System.out.print("IfLt7_0AElseB_86LoadFromConstantTable(2.0, false): ");
+ new Main().$noinline$IfLt7_0AElseB_86LoadFromConstantTable(2.0, false);
+ System.out.print("IfLt7_0AElseB_86LoadFromConstantTable(10.0, false): ");
+ new Main().$noinline$IfLt7_0AElseB_86LoadFromConstantTable(10.0, false);
+
+ // Note: We do not test the code paths where `ConditionMoveWouldExtendReferenceLifetime()`
+ // in the "prepare_for_register_allocation" pass finds an instruction with environment
+ // between the `HCondition` and its user in this run-test. These are difficult to create
+ // from Java code and changes to other passes can easily invalidate such tests. Therefore
+ // we defer to using gtests for these cases.
+ }
+
+ private static void $noinline$A() {
+ System.out.println("A");
+ }
+
+ private static void $noinline$B() {
+ System.out.println("B");
+ }
+
+ private static void $noinline$C() {
+ System.out.println("C");
+ }
+
+ private static boolean $inline$XLtz(int x) {
+ // After inlining, this shall be turned to a `HSelect` and then simplified as `HLessThan`.
+ return x < 0;
+ }
+
+ private static boolean $inline$XNull(Object x) {
+ // After inlining, this shall be turned to a `HSelect` and then simplified as `HEqual`.
+ return x == null;
+ }
+
+ private static boolean $inline$XLt7_0(double x) {
+ return x < 7.0;
+ }
+
+ private static void $noinline$ignore(int ignored) {}
+
+ /// CHECK-START: void Main.$noinline$IfXLtzAElseB(int) prepare_for_register_allocation (before)
+ /// CHECK: <<Cond:z\d+>> {{GreaterThanOrEqual|LessThan}} emitted_at_use_site:false
+ /// CHECK-NEXT: If [<<Cond>>]
+
+ /// CHECK-START: void Main.$noinline$IfXLtzAElseB(int) prepare_for_register_allocation (after)
+ /// CHECK: <<Cond:z\d+>> {{GreaterThanOrEqual|LessThan}} emitted_at_use_site:true
+ /// CHECK-NEXT: If [<<Cond>>]
+
+ public static void $noinline$IfXLtzAElseB(int x) {
+ if (x < 0) {
+ $noinline$A();
+ } else {
+ $noinline$B();
+ }
+ }
+
+ /// CHECK-START: void Main.$noinline$IfXLtzAElseB_Move(int) prepare_for_register_allocation (before)
+ /// CHECK: <<Cond:z\d+>> LessThan emitted_at_use_site:false
+ /// CHECK-NEXT: InstanceFieldGet
+ // On X86, there can be also X86ComputeBaseMethodAddress here.
+ /// CHECK: If [<<Cond>>]
+
+ /// CHECK-START: void Main.$noinline$IfXLtzAElseB_Move(int) prepare_for_register_allocation (after)
+ /// CHECK: InstanceFieldGet
+ // On X86, there can be also X86ComputeBaseMethodAddress here.
+ /// CHECK: <<Cond:z\d+>> LessThan emitted_at_use_site:true
+ /// CHECK-NEXT: If [<<Cond>>]
+
+ public void $noinline$IfXLtzAElseB_Move(int x) {
+ boolean cond = $inline$XLtz(x);
+
+ int value = intField;
+ if (cond) {
+ cond = false; // Avoid environment use below.
+ $noinline$A();
+ } else {
+ cond = false; // Avoid environment use below.
+ $noinline$B();
+ }
+ $noinline$ignore(value);
+ }
+
+ /// CHECK-START: void Main.$noinline$IfXLtzAElseB_EnvUse(int) prepare_for_register_allocation (before)
+ /// CHECK: LessThan emitted_at_use_site:false
+
+ /// CHECK-START: void Main.$noinline$IfXLtzAElseB_EnvUse(int) prepare_for_register_allocation (after)
+ /// CHECK-DAG: <<Cond:z\d+>> LessThan emitted_at_use_site:false
+ // Match an environment use. Use the fact that the <<Cond>> is in vreg 0. Otherwise we'd
+ // need to add a regex to match the earlier vregs which is difficult due to a regex eagerly
+ // consuming as much as possible but it could be curtailed by using the fact that there
+ // are no other boolean (`z`) values in the graph, for example with `{{([^z,]+,)*}}`. This
+ // would be much easier if we could put a variable inside the regex and make the entire
+ // env uses a single regex, `env:[[{{([^,]+,)*<<Cond>>(,[^,\]]+)*}}]]`.
+ /// CHECK-DAG: InvokeStaticOrDirect env:[[<<Cond>>{{(,[^,\]]+)*}}]]
+
+ public static void $noinline$IfXLtzAElseB_EnvUse(int x) {
+ boolean cond = $inline$XLtz(x);
+ if (cond) {
+ $noinline$A();
+ } else {
+ $noinline$B();
+ }
+ }
+
+ /// CHECK-START: void Main.$noinline$IfXNullAElseB(java.lang.Object) prepare_for_register_allocation (before)
+ /// CHECK: <<Cond:z\d+>> {{Equal|NotEqual}} emitted_at_use_site:false
+ /// CHECK-NEXT: If [<<Cond>>]
+
+ /// CHECK-START: void Main.$noinline$IfXNullAElseB(java.lang.Object) prepare_for_register_allocation (after)
+ /// CHECK: <<Cond:z\d+>> {{Equal|NotEqual}} emitted_at_use_site:true
+ /// CHECK-NEXT: If [<<Cond>>]
+
+ public static void $noinline$IfXNullAElseB(Object x) {
+ if (x == null) {
+ $noinline$A();
+ } else {
+ $noinline$B();
+ }
+ }
+
+ /// CHECK-START: void Main.$noinline$IfXNullAElseB_Move(java.lang.Object) prepare_for_register_allocation (before)
+ /// CHECK: <<Cond:z\d+>> Equal emitted_at_use_site:false
+ /// CHECK-NEXT: InstanceFieldGet
+ // On X86, there can be also X86ComputeBaseMethodAddress here.
+ /// CHECK: If [<<Cond>>]
+
+ /// CHECK-START: void Main.$noinline$IfXNullAElseB_Move(java.lang.Object) prepare_for_register_allocation (after)
+ /// CHECK: InstanceFieldGet
+ // On X86, there can be also X86ComputeBaseMethodAddress here.
+ /// CHECK: <<Cond:z\d+>> Equal emitted_at_use_site:true
+ /// CHECK-NEXT: If [<<Cond>>]
+
+ public void $noinline$IfXNullAElseB_Move(Object x) {
+ boolean cond = $inline$XNull(x);
+
+ int value = intField;
+ if (cond) {
+ cond = false; // Avoid environment use below.
+ $noinline$A();
+ } else {
+ cond = false; // Avoid environment use below.
+ $noinline$B();
+ }
+ $noinline$ignore(value);
+ }
+
+ /// CHECK-START: void Main.$noinline$IfXNullAElseB_EnvUse(java.lang.Object) prepare_for_register_allocation (before)
+ /// CHECK: Equal emitted_at_use_site:false
+
+ /// CHECK-START: void Main.$noinline$IfXNullAElseB_EnvUse(java.lang.Object) prepare_for_register_allocation (after)
+ /// CHECK: Equal emitted_at_use_site:false
+
+ public static void $noinline$IfXNullAElseB_EnvUse(Object x) {
+ boolean cond = $inline$XNull(x);
+ if (cond) {
+ $noinline$A();
+ } else {
+ $noinline$B();
+ }
+ }
+
+ /// CHECK-START: void Main.$noinline$IfXNullAElseB_RefNoEnvInBlock(java.lang.Object, boolean) prepare_for_register_allocation (before)
+ /// CHECK: <<Cond:z\d+>> {{Equal|NotEqual}} emitted_at_use_site:false
+ /// CHECK: If [<<Cond>>]
+
+ /// CHECK-START: void Main.$noinline$IfXNullAElseB_RefNoEnvInBlock(java.lang.Object, boolean) prepare_for_register_allocation (after)
+ /// CHECK: <<Cond:z\d+>> {{Equal|NotEqual}} emitted_at_use_site:false
+ /// CHECK: If [<<Cond>>]
+
+ public static void $noinline$IfXNullAElseB_RefNoEnvInBlock(Object x, boolean otherCond) {
+ boolean cond = $inline$XNull(x);
+ if (otherCond) {
+ if (cond) {
+ cond = false; // Avoid environment use below.
+ $noinline$A();
+ } else {
+ cond = false; // Avoid environment use below.
+ $noinline$B();
+ }
+ } else {
+ cond = false; // Avoid environment use below.
+ $noinline$C();
+ }
+ }
+
+ /// CHECK-START: void Main.$noinline$IfLt7_0AElseB_86LoadFromConstantTable(double, boolean) prepare_for_register_allocation (before)
+ /// CHECK: <<Cond:z\d+>> {{LessThan|GreaterThanOrEqual}} emitted_at_use_site:false
+ /// CHECK: If [<<Cond>>]
+
+ /// CHECK-START: void Main.$noinline$IfLt7_0AElseB_86LoadFromConstantTable(double, boolean) prepare_for_register_allocation (after)
+ /// CHECK: <<Cond:z\d+>> {{LessThan|GreaterThanOrEqual}} emitted_at_use_site:true
+ /// CHECK-NEXT: If [<<Cond>>]
+
+ /// CHECK-START-X86: void Main.$noinline$IfLt7_0AElseB_86LoadFromConstantTable(double, boolean) prepare_for_register_allocation (after)
+ /// CHECK: X86ComputeBaseMethodAddress
+ // Note: X86ComputeBaseMethodAddress is not moved before X86LoadFromConstantTable because
+ // it has additional uses in all the `$noinline$` invokes.
+ /// CHECK: X86LoadFromConstantTable
+ /// CHECK-NEXT: <<Cond:z\d+>> {{LessThan|GreaterThanOrEqual}} emitted_at_use_site:true
+ /// CHECK-NEXT: If [<<Cond>>]
+
+ /// CHECK-START-X86: void Main.$noinline$IfLt7_0AElseB_86LoadFromConstantTable(double, boolean) prepare_for_register_allocation (after)
+ /// CHECK-DAG: <<MA:i\d+>> X86ComputeBaseMethodAddress
+ /// CHECK-DAG: InvokeStaticOrDirect [<<MA>>]
+
+ public static void $noinline$IfLt7_0AElseB_86LoadFromConstantTable(
+ double x, boolean otherCond) {
+ boolean cond = $inline$XLt7_0(x);
+ if (otherCond) {
+ if (cond) {
+ cond = false; // Avoid environment use below.
+ $noinline$A();
+ } else {
+ cond = false; // Avoid environment use below.
+ $noinline$B();
+ }
+ } else {
+ cond = false; // Avoid environment use below.
+ $noinline$C();
+ }
+ }
+}