summaryrefslogtreecommitdiff
path: root/compiler/optimizing
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/optimizing')
-rw-r--r--compiler/optimizing/code_generator_mips.cc20
-rw-r--r--compiler/optimizing/constant_folding.cc53
-rw-r--r--compiler/optimizing/constant_folding_test.cc232
-rw-r--r--compiler/optimizing/induction_var_analysis.cc74
-rw-r--r--compiler/optimizing/induction_var_analysis.h22
-rw-r--r--compiler/optimizing/induction_var_analysis_test.cc4
-rw-r--r--compiler/optimizing/induction_var_range.cc10
-rw-r--r--compiler/optimizing/induction_var_range_test.cc2
-rw-r--r--compiler/optimizing/intrinsics_mips64.cc88
-rw-r--r--compiler/optimizing/nodes.cc11
-rw-r--r--compiler/optimizing/nodes.h6
-rw-r--r--compiler/optimizing/reference_type_propagation.cc16
12 files changed, 419 insertions, 119 deletions
diff --git a/compiler/optimizing/code_generator_mips.cc b/compiler/optimizing/code_generator_mips.cc
index 6aed4447f7..e6b9273d24 100644
--- a/compiler/optimizing/code_generator_mips.cc
+++ b/compiler/optimizing/code_generator_mips.cc
@@ -3118,15 +3118,25 @@ void InstructionCodeGeneratorMIPS::VisitInvokeVirtual(HInvokeVirtual* invoke) {
}
void LocationsBuilderMIPS::VisitLoadClass(HLoadClass* cls) {
- LocationSummary::CallKind call_kind = cls->CanCallRuntime() ? LocationSummary::kCallOnSlowPath
- : LocationSummary::kNoCall;
- LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(cls, call_kind);
- locations->SetInAt(0, Location::RequiresRegister());
- locations->SetOut(Location::RequiresRegister());
+ InvokeRuntimeCallingConvention calling_convention;
+ CodeGenerator::CreateLoadClassLocationSummary(
+ cls,
+ Location::RegisterLocation(calling_convention.GetRegisterAt(0)),
+ Location::RegisterLocation(V0));
}
void InstructionCodeGeneratorMIPS::VisitLoadClass(HLoadClass* cls) {
LocationSummary* locations = cls->GetLocations();
+ if (cls->NeedsAccessCheck()) {
+ codegen_->MoveConstant(locations->GetTemp(0), cls->GetTypeIndex());
+ codegen_->InvokeRuntime(QUICK_ENTRY_POINT(pInitializeTypeAndVerifyAccess),
+ cls,
+ cls->GetDexPc(),
+ nullptr,
+ IsDirectEntrypoint(kQuickInitializeTypeAndVerifyAccess));
+ return;
+ }
+
Register out = locations->Out().AsRegister<Register>();
Register current_method = locations->InAt(0).AsRegister<Register>();
if (cls->IsReferrersClass()) {
diff --git a/compiler/optimizing/constant_folding.cc b/compiler/optimizing/constant_folding.cc
index e0aa4ff489..57452cc076 100644
--- a/compiler/optimizing/constant_folding.cc
+++ b/compiler/optimizing/constant_folding.cc
@@ -27,6 +27,11 @@ class InstructionWithAbsorbingInputSimplifier : public HGraphVisitor {
private:
void VisitShift(HBinaryOperation* shift);
+ void VisitAbove(HAbove* instruction) OVERRIDE;
+ void VisitAboveOrEqual(HAboveOrEqual* instruction) OVERRIDE;
+ void VisitBelow(HBelow* instruction) OVERRIDE;
+ void VisitBelowOrEqual(HBelowOrEqual* instruction) OVERRIDE;
+
void VisitAnd(HAnd* instruction) OVERRIDE;
void VisitCompare(HCompare* instruction) OVERRIDE;
void VisitMul(HMul* instruction) OVERRIDE;
@@ -105,6 +110,54 @@ void InstructionWithAbsorbingInputSimplifier::VisitShift(HBinaryOperation* instr
}
}
+void InstructionWithAbsorbingInputSimplifier::VisitAbove(HAbove* instruction) {
+ if (instruction->GetLeft()->IsConstant() &&
+ instruction->GetLeft()->AsConstant()->IsZero()) {
+ // Replace code looking like
+ // ABOVE dst, 0, src // unsigned 0 > src is always false
+ // with
+ // CONSTANT false
+ instruction->ReplaceWith(GetGraph()->GetConstant(Primitive::kPrimBoolean, 0));
+ instruction->GetBlock()->RemoveInstruction(instruction);
+ }
+}
+
+void InstructionWithAbsorbingInputSimplifier::VisitAboveOrEqual(HAboveOrEqual* instruction) {
+ if (instruction->GetRight()->IsConstant() &&
+ instruction->GetRight()->AsConstant()->IsZero()) {
+ // Replace code looking like
+ // ABOVE_OR_EQUAL dst, src, 0 // unsigned src >= 0 is always true
+ // with
+ // CONSTANT true
+ instruction->ReplaceWith(GetGraph()->GetConstant(Primitive::kPrimBoolean, 1));
+ instruction->GetBlock()->RemoveInstruction(instruction);
+ }
+}
+
+void InstructionWithAbsorbingInputSimplifier::VisitBelow(HBelow* instruction) {
+ if (instruction->GetRight()->IsConstant() &&
+ instruction->GetRight()->AsConstant()->IsZero()) {
+ // Replace code looking like
+ // BELOW dst, src, 0 // unsigned src < 0 is always false
+ // with
+ // CONSTANT false
+ instruction->ReplaceWith(GetGraph()->GetConstant(Primitive::kPrimBoolean, 0));
+ instruction->GetBlock()->RemoveInstruction(instruction);
+ }
+}
+
+void InstructionWithAbsorbingInputSimplifier::VisitBelowOrEqual(HBelowOrEqual* instruction) {
+ if (instruction->GetLeft()->IsConstant() &&
+ instruction->GetLeft()->AsConstant()->IsZero()) {
+ // Replace code looking like
+ // BELOW_OR_EQUAL dst, 0, src // unsigned 0 <= src is always true
+ // with
+ // CONSTANT true
+ instruction->ReplaceWith(GetGraph()->GetConstant(Primitive::kPrimBoolean, 1));
+ instruction->GetBlock()->RemoveInstruction(instruction);
+ }
+}
+
void InstructionWithAbsorbingInputSimplifier::VisitAnd(HAnd* instruction) {
HConstant* input_cst = instruction->GetConstantRight();
if ((input_cst != nullptr) && input_cst->IsZero()) {
diff --git a/compiler/optimizing/constant_folding_test.cc b/compiler/optimizing/constant_folding_test.cc
index 2feb75cc9f..e469c8d6d0 100644
--- a/compiler/optimizing/constant_folding_test.cc
+++ b/compiler/optimizing/constant_folding_test.cc
@@ -29,50 +29,70 @@
namespace art {
-static void TestCode(const uint16_t* data,
- const std::string& expected_before,
- const std::string& expected_after_cf,
- const std::string& expected_after_dce,
- std::function<void(HGraph*)> check_after_cf,
- Primitive::Type return_type = Primitive::kPrimInt) {
- ArenaPool pool;
- ArenaAllocator allocator(&pool);
- HGraph* graph = CreateCFG(&allocator, data, return_type);
- ASSERT_NE(graph, nullptr);
-
- graph->TryBuildingSsa();
-
- StringPrettyPrinter printer_before(graph);
- printer_before.VisitInsertionOrder();
- std::string actual_before = printer_before.str();
- ASSERT_EQ(expected_before, actual_before);
-
- std::unique_ptr<const X86InstructionSetFeatures> features_x86(
- X86InstructionSetFeatures::FromCppDefines());
- x86::CodeGeneratorX86 codegenX86(graph, *features_x86.get(), CompilerOptions());
- HConstantFolding(graph).Run();
- SSAChecker ssa_checker_cf(graph);
- ssa_checker_cf.Run();
- ASSERT_TRUE(ssa_checker_cf.IsValid());
-
- StringPrettyPrinter printer_after_cf(graph);
- printer_after_cf.VisitInsertionOrder();
- std::string actual_after_cf = printer_after_cf.str();
- ASSERT_EQ(expected_after_cf, actual_after_cf);
-
- check_after_cf(graph);
-
- HDeadCodeElimination(graph).Run();
- SSAChecker ssa_checker_dce(graph);
- ssa_checker_dce.Run();
- ASSERT_TRUE(ssa_checker_dce.IsValid());
-
- StringPrettyPrinter printer_after_dce(graph);
- printer_after_dce.VisitInsertionOrder();
- std::string actual_after_dce = printer_after_dce.str();
- ASSERT_EQ(expected_after_dce, actual_after_dce);
-}
-
+/**
+ * Fixture class for the constant folding and dce tests.
+ */
+class ConstantFoldingTest : public testing::Test {
+ public:
+ ConstantFoldingTest() : pool_(), allocator_(&pool_) {
+ graph_ = CreateGraph(&allocator_);
+ }
+
+ void TestCode(const uint16_t* data,
+ const std::string& expected_before,
+ const std::string& expected_after_cf,
+ const std::string& expected_after_dce,
+ std::function<void(HGraph*)> check_after_cf,
+ Primitive::Type return_type = Primitive::kPrimInt) {
+ graph_ = CreateCFG(&allocator_, data, return_type);
+ TestCodeOnReadyGraph(expected_before,
+ expected_after_cf,
+ expected_after_dce,
+ check_after_cf);
+ }
+
+ void TestCodeOnReadyGraph(const std::string& expected_before,
+ const std::string& expected_after_cf,
+ const std::string& expected_after_dce,
+ std::function<void(HGraph*)> check_after_cf) {
+ ASSERT_NE(graph_, nullptr);
+ graph_->TryBuildingSsa();
+
+ StringPrettyPrinter printer_before(graph_);
+ printer_before.VisitInsertionOrder();
+ std::string actual_before = printer_before.str();
+ EXPECT_EQ(expected_before, actual_before);
+
+ std::unique_ptr<const X86InstructionSetFeatures> features_x86(
+ X86InstructionSetFeatures::FromCppDefines());
+ x86::CodeGeneratorX86 codegenX86(graph_, *features_x86.get(), CompilerOptions());
+ HConstantFolding(graph_).Run();
+ SSAChecker ssa_checker_cf(graph_);
+ ssa_checker_cf.Run();
+ ASSERT_TRUE(ssa_checker_cf.IsValid());
+
+ StringPrettyPrinter printer_after_cf(graph_);
+ printer_after_cf.VisitInsertionOrder();
+ std::string actual_after_cf = printer_after_cf.str();
+ EXPECT_EQ(expected_after_cf, actual_after_cf);
+
+ check_after_cf(graph_);
+
+ HDeadCodeElimination(graph_).Run();
+ SSAChecker ssa_checker_dce(graph_);
+ ssa_checker_dce.Run();
+ ASSERT_TRUE(ssa_checker_dce.IsValid());
+
+ StringPrettyPrinter printer_after_dce(graph_);
+ printer_after_dce.VisitInsertionOrder();
+ std::string actual_after_dce = printer_after_dce.str();
+ EXPECT_EQ(expected_after_dce, actual_after_dce);
+ }
+
+ ArenaPool pool_;
+ ArenaAllocator allocator_;
+ HGraph* graph_;
+};
/**
* Tiny three-register program exercising int constant folding on negation.
@@ -84,7 +104,7 @@ static void TestCode(const uint16_t* data,
* v1 <- -v0 1. neg-int v1, v0
* return v1 2. return v1
*/
-TEST(ConstantFolding, IntConstantFoldingNegation) {
+TEST_F(ConstantFoldingTest, IntConstantFoldingNegation) {
const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
Instruction::CONST_4 | 0 << 8 | 1 << 12,
Instruction::NEG_INT | 1 << 8 | 0 << 12,
@@ -141,7 +161,7 @@ TEST(ConstantFolding, IntConstantFoldingNegation) {
* (v2, v3) <- -(v0, v1) 1. neg-long v2, v0
* return (v2, v3) 2. return-wide v2
*/
-TEST(ConstantFolding, LongConstantFoldingNegation) {
+TEST_F(ConstantFoldingTest, LongConstantFoldingNegation) {
const int64_t input = INT64_C(4294967296); // 2^32
const uint16_t word0 = Low16Bits(Low32Bits(input)); // LSW.
const uint16_t word1 = High16Bits(Low32Bits(input));
@@ -205,7 +225,7 @@ TEST(ConstantFolding, LongConstantFoldingNegation) {
* v2 <- v0 + v1 2. add-int v2, v0, v1
* return v2 4. return v2
*/
-TEST(ConstantFolding, IntConstantFoldingOnAddition1) {
+TEST_F(ConstantFoldingTest, IntConstantFoldingOnAddition1) {
const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
Instruction::CONST_4 | 0 << 8 | 1 << 12,
Instruction::CONST_4 | 1 << 8 | 2 << 12,
@@ -271,7 +291,7 @@ TEST(ConstantFolding, IntConstantFoldingOnAddition1) {
* v2 <- v0 + v1 6. add-int v2, v0, v1
* return v2 8. return v2
*/
-TEST(ConstantFolding, IntConstantFoldingOnAddition2) {
+TEST_F(ConstantFoldingTest, IntConstantFoldingOnAddition2) {
const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
Instruction::CONST_4 | 0 << 8 | 1 << 12,
Instruction::CONST_4 | 1 << 8 | 2 << 12,
@@ -357,7 +377,7 @@ TEST(ConstantFolding, IntConstantFoldingOnAddition2) {
* v2 <- v0 - v1 2. sub-int v2, v0, v1
* return v2 4. return v2
*/
-TEST(ConstantFolding, IntConstantFoldingOnSubtraction) {
+TEST_F(ConstantFoldingTest, IntConstantFoldingOnSubtraction) {
const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
Instruction::CONST_4 | 0 << 8 | 3 << 12,
Instruction::CONST_4 | 1 << 8 | 2 << 12,
@@ -421,7 +441,7 @@ TEST(ConstantFolding, IntConstantFoldingOnSubtraction) {
* (v0, v1) + (v1, v2) 4. add-long v4, v0, v2
* return (v4, v5) 6. return-wide v4
*/
-TEST(ConstantFolding, LongConstantFoldingOnAddition) {
+TEST_F(ConstantFoldingTest, LongConstantFoldingOnAddition) {
const uint16_t data[] = SIX_REGISTERS_CODE_ITEM(
Instruction::CONST_WIDE_16 | 0 << 8, 1,
Instruction::CONST_WIDE_16 | 2 << 8, 2,
@@ -486,7 +506,7 @@ TEST(ConstantFolding, LongConstantFoldingOnAddition) {
* (v0, v1) - (v1, v2) 4. sub-long v4, v0, v2
* return (v4, v5) 6. return-wide v4
*/
-TEST(ConstantFolding, LongConstantFoldingOnSubtraction) {
+TEST_F(ConstantFoldingTest, LongConstantFoldingOnSubtraction) {
const uint16_t data[] = SIX_REGISTERS_CODE_ITEM(
Instruction::CONST_WIDE_16 | 0 << 8, 3,
Instruction::CONST_WIDE_16 | 2 << 8, 2,
@@ -560,7 +580,7 @@ TEST(ConstantFolding, LongConstantFoldingOnSubtraction) {
* L3: v2 <- v1 + 8 11. add-int/lit16 v2, v1, #+8
* return v2 13. return v2
*/
-TEST(ConstantFolding, IntConstantFoldingAndJumps) {
+TEST_F(ConstantFoldingTest, IntConstantFoldingAndJumps) {
const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
Instruction::CONST_4 | 0 << 8 | 1 << 12,
Instruction::CONST_4 | 1 << 8 | 2 << 12,
@@ -656,7 +676,6 @@ TEST(ConstantFolding, IntConstantFoldingAndJumps) {
check_after_cf);
}
-
/**
* Three-register program with a constant (static) condition.
*
@@ -670,7 +689,7 @@ TEST(ConstantFolding, IntConstantFoldingAndJumps) {
* L1: v2 <- v0 + v1 5. add-int v2, v0, v1
* return-void 7. return
*/
-TEST(ConstantFolding, ConstantCondition) {
+TEST_F(ConstantFoldingTest, ConstantCondition) {
const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
Instruction::CONST_4 | 1 << 8 | 1 << 12,
Instruction::CONST_4 | 0 << 8 | 0 << 12,
@@ -732,4 +751,109 @@ TEST(ConstantFolding, ConstantCondition) {
check_after_cf);
}
+/**
+ * Unsigned comparisons with zero. Since these instructions are not present
+ * in the bytecode, we need to set up the graph explicitly.
+ */
+TEST_F(ConstantFoldingTest, UnsignedComparisonsWithZero) {
+ graph_ = CreateGraph(&allocator_);
+ HBasicBlock* entry_block = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(entry_block);
+ graph_->SetEntryBlock(entry_block);
+ HBasicBlock* block = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(block);
+ HBasicBlock* exit_block = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(exit_block);
+ graph_->SetExitBlock(exit_block);
+ entry_block->AddSuccessor(block);
+ block->AddSuccessor(exit_block);
+
+ // Make various unsigned comparisons with zero against a parameter.
+ HInstruction* parameter = new (&allocator_) HParameterValue(
+ graph_->GetDexFile(), 0, 0, Primitive::kPrimInt, true);
+ entry_block->AddInstruction(parameter);
+ HInstruction* zero = graph_->GetIntConstant(0);
+ HInstruction* last;
+ block->AddInstruction(last = new (&allocator_) HAbove(zero, parameter));
+ block->AddInstruction(new (&allocator_) HDeoptimize(last, 0));
+ block->AddInstruction(last = new (&allocator_) HAbove(parameter, zero));
+ block->AddInstruction(new (&allocator_) HDeoptimize(last, 0));
+ block->AddInstruction(last = new (&allocator_) HAboveOrEqual(zero, parameter));
+ block->AddInstruction(new (&allocator_) HDeoptimize(last, 0));
+ block->AddInstruction(last = new (&allocator_) HAboveOrEqual(parameter, zero));
+ block->AddInstruction(new (&allocator_) HDeoptimize(last, 0));
+ block->AddInstruction(last = new (&allocator_) HBelow(zero, parameter));
+ block->AddInstruction(new (&allocator_) HDeoptimize(last, 0));
+ block->AddInstruction(last = new (&allocator_) HBelow(parameter, zero));
+ block->AddInstruction(new (&allocator_) HDeoptimize(last, 0));
+ block->AddInstruction(last = new (&allocator_) HBelowOrEqual(zero, parameter));
+ block->AddInstruction(new (&allocator_) HDeoptimize(last, 0));
+ block->AddInstruction(last = new (&allocator_) HBelowOrEqual(parameter, zero));
+ block->AddInstruction(new (&allocator_) HDeoptimize(last, 0));
+
+ entry_block->AddInstruction(new (&allocator_) HGoto());
+ block->AddInstruction(new (&allocator_) HReturn(zero));
+ exit_block->AddInstruction(new (&allocator_) HExit());
+
+ const std::string expected_before =
+ "BasicBlock 0, succ: 1\n"
+ " 0: ParameterValue [16, 14, 12, 10, 8, 6, 4, 2]\n"
+ " 1: IntConstant [19, 16, 14, 12, 10, 8, 6, 4, 2]\n"
+ " 18: Goto 1\n"
+ "BasicBlock 1, pred: 0, succ: 2\n"
+ " 2: Above(1, 0) [3]\n"
+ " 3: Deoptimize(2)\n"
+ " 4: Above(0, 1) [5]\n"
+ " 5: Deoptimize(4)\n"
+ " 6: AboveOrEqual(1, 0) [7]\n"
+ " 7: Deoptimize(6)\n"
+ " 8: AboveOrEqual(0, 1) [9]\n"
+ " 9: Deoptimize(8)\n"
+ " 10: Below(1, 0) [11]\n"
+ " 11: Deoptimize(10)\n"
+ " 12: Below(0, 1) [13]\n"
+ " 13: Deoptimize(12)\n"
+ " 14: BelowOrEqual(1, 0) [15]\n"
+ " 15: Deoptimize(14)\n"
+ " 16: BelowOrEqual(0, 1) [17]\n"
+ " 17: Deoptimize(16)\n"
+ " 19: Return(1)\n"
+ "BasicBlock 2, pred: 1\n"
+ " 20: Exit\n";
+
+ const std::string expected_after_cf =
+ "BasicBlock 0, succ: 1\n"
+ " 0: ParameterValue [16, 10, 6, 4]\n"
+ " 1: IntConstant [13, 3, 19, 16, 10, 6, 4]\n"
+ " 21: IntConstant [15, 9]\n"
+ " 18: Goto 1\n"
+ "BasicBlock 1, pred: 0, succ: 2\n"
+ " 3: Deoptimize(1)\n"
+ " 4: Above(0, 1) [5]\n"
+ " 5: Deoptimize(4)\n"
+ " 6: AboveOrEqual(1, 0) [7]\n"
+ " 7: Deoptimize(6)\n"
+ " 9: Deoptimize(21)\n"
+ " 10: Below(1, 0) [11]\n"
+ " 11: Deoptimize(10)\n"
+ " 13: Deoptimize(1)\n"
+ " 15: Deoptimize(21)\n"
+ " 16: BelowOrEqual(0, 1) [17]\n"
+ " 17: Deoptimize(16)\n"
+ " 19: Return(1)\n"
+ "BasicBlock 2, pred: 1\n"
+ " 20: Exit\n";
+
+ const std::string expected_after_dce = expected_after_cf;
+
+ auto check_after_cf = [](HGraph* graph) {
+ CHECK(graph != nullptr);
+ };
+
+ TestCodeOnReadyGraph(expected_before,
+ expected_after_cf,
+ expected_after_dce,
+ check_after_cf);
+}
+
} // namespace art
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index 8968a44da8..fdf8cc9c1f 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -20,19 +20,6 @@
namespace art {
/**
- * Returns true if instruction is invariant within the given loop.
- */
-static bool IsLoopInvariant(HLoopInformation* loop, HInstruction* instruction) {
- HLoopInformation* other_loop = instruction->GetBlock()->GetLoopInformation();
- if (other_loop != loop) {
- // If instruction does not occur in same loop, it is invariant
- // if it appears in an outer loop (including no loop at all).
- return other_loop == nullptr || loop->IsIn(*other_loop);
- }
- return false;
-}
-
-/**
* Since graph traversal may enter a SCC at any position, an initial representation may be rotated,
* along dependences, viz. any of (a, b, c, d), (d, a, b, c) (c, d, a, b), (b, c, d, a) assuming
* a chain of dependences (mutual independent items may occur in arbitrary order). For proper
@@ -601,15 +588,16 @@ void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop,
// an unsigned entity, for example, as in the following loop that uses the full range:
// for (int i = INT_MIN; i < INT_MAX; i++) // TC = UINT_MAX
// (2) The TC is only valid if the loop is taken, otherwise TC = 0, as in:
- // for (int i = 12; i < U; i++) // TC = 0 when U >= 12
+ // for (int i = 12; i < U; i++) // TC = 0 when U < 12
// If this cannot be determined at compile-time, the TC is only valid within the
- // loop-body proper, not the loop-header unless enforced with an explicit condition.
+ // loop-body proper, not the loop-header unless enforced with an explicit taken-test.
// (3) The TC is only valid if the loop is finite, otherwise TC has no value, as in:
// for (int i = 0; i <= U; i++) // TC = Inf when U = INT_MAX
// If this cannot be determined at compile-time, the TC is only valid when enforced
- // with an explicit condition.
+ // with an explicit finite-test.
// (4) For loops which early-exits, the TC forms an upper bound, as in:
// for (int i = 0; i < 10 && ....; i++) // TC <= 10
+ InductionInfo* trip_count = upper_expr;
const bool is_taken = IsTaken(lower_expr, upper_expr, cmp);
const bool is_finite = IsFinite(upper_expr, stride_value, type, cmp);
const bool cancels = (cmp == kCondLT || cmp == kCondGT) && std::abs(stride_value) == 1;
@@ -617,26 +605,36 @@ void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop,
// Convert exclusive integral inequality into inclusive integral inequality,
// viz. condition i < U is i <= U - 1 and condition i > U is i >= U + 1.
if (cmp == kCondLT) {
- upper_expr = CreateInvariantOp(kSub, upper_expr, CreateConstant(1, type));
+ trip_count = CreateInvariantOp(kSub, trip_count, CreateConstant(1, type));
} else if (cmp == kCondGT) {
- upper_expr = CreateInvariantOp(kAdd, upper_expr, CreateConstant(1, type));
+ trip_count = CreateInvariantOp(kAdd, trip_count, CreateConstant(1, type));
}
// Compensate for stride.
- upper_expr = CreateInvariantOp(kAdd, upper_expr, stride);
+ trip_count = CreateInvariantOp(kAdd, trip_count, stride);
}
- InductionInfo* trip_count
- = CreateInvariantOp(kDiv, CreateInvariantOp(kSub, upper_expr, lower_expr), stride);
+ trip_count = CreateInvariantOp(kDiv, CreateInvariantOp(kSub, trip_count, lower_expr), stride);
// Assign the trip-count expression to the loop control. Clients that use the information
// should be aware that the expression is only valid under the conditions listed above.
- InductionOp tcKind = kTripCountInBodyUnsafe;
+ InductionOp tcKind = kTripCountInBodyUnsafe; // needs both tests
if (is_taken && is_finite) {
- tcKind = kTripCountInLoop;
+ tcKind = kTripCountInLoop; // needs neither test
} else if (is_finite) {
- tcKind = kTripCountInBody;
+ tcKind = kTripCountInBody; // needs taken-test
} else if (is_taken) {
- tcKind = kTripCountInLoopUnsafe;
+ tcKind = kTripCountInLoopUnsafe; // needs finite-test
}
- AssignInfo(loop, loop->GetHeader()->GetLastInstruction(), CreateTripCount(tcKind, trip_count));
+ InductionOp op = kNop;
+ switch (cmp) {
+ case kCondLT: op = kLT; break;
+ case kCondLE: op = kLE; break;
+ case kCondGT: op = kGT; break;
+ case kCondGE: op = kGE; break;
+ default: LOG(FATAL) << "CONDITION UNREACHABLE";
+ }
+ InductionInfo* taken_test = CreateInvariantOp(op, lower_expr, upper_expr);
+ AssignInfo(loop,
+ loop->GetHeader()->GetLastInstruction(),
+ CreateTripCount(tcKind, trip_count, taken_test));
}
bool HInductionVarAnalysis::IsTaken(InductionInfo* lower_expr,
@@ -707,7 +705,7 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::LookupInfo(HLoopInf
return loop_it->second;
}
}
- if (IsLoopInvariant(loop, instruction)) {
+ if (loop->IsLoopInvariant(instruction, true)) {
InductionInfo* info = CreateInvariantFetch(instruction);
AssignInfo(loop, instruction, info);
return info;
@@ -829,12 +827,16 @@ std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) {
std::string inv = "(";
inv += InductionToString(info->op_a);
switch (info->operation) {
- case kNop: inv += " @ "; break;
- case kAdd: inv += " + "; break;
+ case kNop: inv += " @ "; break;
+ case kAdd: inv += " + "; break;
case kSub:
- case kNeg: inv += " - "; break;
- case kMul: inv += " * "; break;
- case kDiv: inv += " / "; break;
+ case kNeg: inv += " - "; break;
+ case kMul: inv += " * "; break;
+ case kDiv: inv += " / "; break;
+ case kLT: inv += " < "; break;
+ case kLE: inv += " <= "; break;
+ case kGT: inv += " > "; break;
+ case kGE: inv += " >= "; break;
case kFetch:
DCHECK(info->fetch);
if (IsIntAndGet(info, &value)) {
@@ -843,10 +845,10 @@ std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) {
inv += std::to_string(info->fetch->GetId()) + ":" + info->fetch->DebugName();
}
break;
- case kTripCountInLoop: inv += "TC-loop:"; break;
- case kTripCountInBody: inv += "TC-body:"; break;
- case kTripCountInLoopUnsafe: inv += "TC-loop-unsafe:"; break;
- case kTripCountInBodyUnsafe: inv += "TC-body-unsafe:"; break;
+ case kTripCountInLoop: inv += " (TC-loop) "; break;
+ case kTripCountInBody: inv += " (TC-body) "; break;
+ case kTripCountInLoopUnsafe: inv += " (TC-loop-unsafe) "; break;
+ case kTripCountInBodyUnsafe: inv += " (TC-body-unsafe) "; break;
}
inv += InductionToString(info->op_b);
return inv + ")";
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index 7ab80cd676..cf354093f2 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -65,11 +65,16 @@ class HInductionVarAnalysis : public HOptimization {
kMul,
kDiv,
kFetch,
- // Trip counts (valid in full loop or only body proper; unsafe implies loop may be infinite).
- kTripCountInLoop,
- kTripCountInBody,
- kTripCountInLoopUnsafe,
- kTripCountInBodyUnsafe
+ // Trip-counts.
+ kTripCountInLoop, // valid in full loop; loop is finite
+ kTripCountInBody, // valid in body only; loop is finite
+ kTripCountInLoopUnsafe, // valid in full loop; loop may be infinite
+ kTripCountInBodyUnsafe, // valid in body only; loop may be infinite
+ // Comparisons for trip-count tests.
+ kLT,
+ kLE,
+ kGT,
+ kGE
};
/**
@@ -85,7 +90,7 @@ class HInductionVarAnalysis : public HOptimization {
* (4) periodic
* nop: a, then defined by b (repeated when exhausted)
* (5) trip-count:
- * tc: defined by b
+ * tc: defined by a, taken-test in b
*/
struct InductionInfo : public ArenaObject<kArenaAllocInductionVarAnalysis> {
InductionInfo(InductionClass ic,
@@ -119,8 +124,9 @@ class HInductionVarAnalysis : public HOptimization {
return new (graph_->GetArena()) InductionInfo(kInvariant, kFetch, nullptr, nullptr, f);
}
- InductionInfo* CreateTripCount(InductionOp op, InductionInfo* b) {
- return new (graph_->GetArena()) InductionInfo(kInvariant, op, nullptr, b, nullptr);
+ InductionInfo* CreateTripCount(InductionOp op, InductionInfo* a, InductionInfo* b) {
+ DCHECK(a != nullptr);
+ return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr);
}
InductionInfo* CreateInduction(InductionClass ic, InductionInfo* a, InductionInfo* b) {
diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
index f16da2a3f7..b7262f6b29 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -234,7 +234,7 @@ TEST_F(InductionVarAnalysisTest, FindBasicInduction) {
EXPECT_STREQ("((1) * i + (1))", GetInductionInfo(increment_[0], 0).c_str());
// Trip-count.
- EXPECT_STREQ("(TC-loop:(100))",
+ EXPECT_STREQ("((100) (TC-loop) ((0) < (100)))",
GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str());
}
@@ -552,7 +552,7 @@ TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) {
}
EXPECT_STREQ("((1) * i + (1))", GetInductionInfo(increment_[d], d).c_str());
// Trip-count.
- EXPECT_STREQ("(TC-loop:(100))",
+ EXPECT_STREQ("((100) (TC-loop) ((0) < (100)))",
GetInductionInfo(loop_header_[d]->GetLastInstruction(), d).c_str());
}
}
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index f4842f9696..5530d261d2 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -152,7 +152,7 @@ InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction,
}
} else if (is_min) {
// Special case for finding minimum: minimum of trip-count in loop-body is 1.
- if (trip != nullptr && in_body && instruction == trip->op_b->fetch) {
+ if (trip != nullptr && in_body && instruction == trip->op_a->fetch) {
return Value(1);
}
}
@@ -185,14 +185,14 @@ InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::Induct
return GetFetch(info->fetch, trip, in_body, is_min);
case HInductionVarAnalysis::kTripCountInLoop:
if (!in_body && !is_min) { // one extra!
- return GetVal(info->op_b, trip, in_body, is_min);
+ return GetVal(info->op_a, trip, in_body, is_min);
}
FALLTHROUGH_INTENDED;
case HInductionVarAnalysis::kTripCountInBody:
if (is_min) {
return Value(0);
} else if (in_body) {
- return SubValue(GetVal(info->op_b, trip, in_body, is_min), Value(1));
+ return SubValue(GetVal(info->op_a, trip, in_body, is_min), Value(1));
}
break;
default:
@@ -428,7 +428,7 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info,
return true;
case HInductionVarAnalysis::kTripCountInLoop:
if (!in_body && !is_min) { // one extra!
- return GenerateCode(info->op_b, trip, graph, block, result, in_body, is_min);
+ return GenerateCode(info->op_a, trip, graph, block, result, in_body, is_min);
}
FALLTHROUGH_INTENDED;
case HInductionVarAnalysis::kTripCountInBody:
@@ -438,7 +438,7 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info,
}
return true;
} else if (in_body) {
- if (GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) {
+ if (GenerateCode(info->op_a, trip, graph, block, &opb, in_body, is_min)) {
if (graph != nullptr) {
*result = Insert(block,
new (graph->GetArena())
diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc
index 8fbc59fb4a..ce8926ad72 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -125,7 +125,7 @@ class InductionVarRangeTest : public testing::Test {
/** Constructs a trip-count. */
HInductionVarAnalysis::InductionInfo* CreateTripCount(int32_t tc) {
- return iva_->CreateTripCount(HInductionVarAnalysis::kTripCountInLoop, CreateConst(tc));
+ return iva_->CreateTripCount(HInductionVarAnalysis::kTripCountInLoop, CreateConst(tc), nullptr);
}
/** Constructs a linear a * i + b induction. */
diff --git a/compiler/optimizing/intrinsics_mips64.cc b/compiler/optimizing/intrinsics_mips64.cc
index 0ab0b80396..05c7eb02d9 100644
--- a/compiler/optimizing/intrinsics_mips64.cc
+++ b/compiler/optimizing/intrinsics_mips64.cc
@@ -1227,6 +1227,91 @@ void IntrinsicCodeGeneratorMIPS64::VisitUnsafePutLongVolatile(HInvoke* invoke) {
GenUnsafePut(invoke->GetLocations(), Primitive::kPrimLong, true, false, codegen_);
}
+static void CreateIntIntIntIntIntToInt(ArenaAllocator* arena, HInvoke* invoke) {
+ LocationSummary* locations = new (arena) LocationSummary(invoke,
+ LocationSummary::kNoCall,
+ kIntrinsified);
+ locations->SetInAt(0, Location::NoLocation()); // Unused receiver.
+ locations->SetInAt(1, Location::RequiresRegister());
+ locations->SetInAt(2, Location::RequiresRegister());
+ locations->SetInAt(3, Location::RequiresRegister());
+ locations->SetInAt(4, Location::RequiresRegister());
+
+ locations->SetOut(Location::RequiresRegister());
+}
+
+static void GenCas(LocationSummary* locations, Primitive::Type type, CodeGeneratorMIPS64* codegen) {
+ Mips64Assembler* assembler = codegen->GetAssembler();
+ GpuRegister base = locations->InAt(1).AsRegister<GpuRegister>();
+ GpuRegister offset = locations->InAt(2).AsRegister<GpuRegister>();
+ GpuRegister expected = locations->InAt(3).AsRegister<GpuRegister>();
+ GpuRegister value = locations->InAt(4).AsRegister<GpuRegister>();
+ GpuRegister out = locations->Out().AsRegister<GpuRegister>();
+
+ DCHECK_NE(base, out);
+ DCHECK_NE(offset, out);
+ DCHECK_NE(expected, out);
+
+ // do {
+ // tmp_value = [tmp_ptr] - expected;
+ // } while (tmp_value == 0 && failure([tmp_ptr] <- r_new_value));
+ // result = tmp_value != 0;
+
+ Label loop_head, exit_loop;
+ __ Daddu(TMP, base, offset);
+ __ Sync(0);
+ __ Bind(&loop_head);
+ if (type == Primitive::kPrimLong) {
+ __ Lld(out, TMP);
+ } else {
+ __ Ll(out, TMP);
+ }
+ __ Dsubu(out, out, expected); // If we didn't get the 'expected'
+ __ Sltiu(out, out, 1); // value, set 'out' to false, and
+ __ Beqzc(out, &exit_loop); // return.
+ __ Move(out, value); // Use 'out' for the 'store conditional' instruction.
+ // If we use 'value' directly, we would lose 'value'
+ // in the case that the store fails. Whether the
+ // store succeeds, or fails, it will load the
+ // correct boolean value into the 'out' register.
+ if (type == Primitive::kPrimLong) {
+ __ Scd(out, TMP);
+ } else {
+ __ Sc(out, TMP);
+ }
+ __ Beqzc(out, &loop_head); // If we couldn't do the read-modify-write
+ // cycle atomically then retry.
+ __ Bind(&exit_loop);
+ __ Sync(0);
+}
+
+// boolean sun.misc.Unsafe.compareAndSwapInt(Object o, long offset, int expected, int x)
+void IntrinsicLocationsBuilderMIPS64::VisitUnsafeCASInt(HInvoke* invoke) {
+ CreateIntIntIntIntIntToInt(arena_, invoke);
+}
+
+void IntrinsicCodeGeneratorMIPS64::VisitUnsafeCASInt(HInvoke* invoke) {
+ GenCas(invoke->GetLocations(), Primitive::kPrimInt, codegen_);
+}
+
+// boolean sun.misc.Unsafe.compareAndSwapLong(Object o, long offset, long expected, long x)
+void IntrinsicLocationsBuilderMIPS64::VisitUnsafeCASLong(HInvoke* invoke) {
+ CreateIntIntIntIntIntToInt(arena_, invoke);
+}
+
+void IntrinsicCodeGeneratorMIPS64::VisitUnsafeCASLong(HInvoke* invoke) {
+ GenCas(invoke->GetLocations(), Primitive::kPrimLong, codegen_);
+}
+
+// boolean sun.misc.Unsafe.compareAndSwapObject(Object o, long offset, Object expected, Object x)
+void IntrinsicLocationsBuilderMIPS64::VisitUnsafeCASObject(HInvoke* invoke) {
+ CreateIntIntIntIntIntToInt(arena_, invoke);
+}
+
+void IntrinsicCodeGeneratorMIPS64::VisitUnsafeCASObject(HInvoke* invoke) {
+ GenCas(invoke->GetLocations(), Primitive::kPrimNot, codegen_);
+}
+
// char java.lang.String.charAt(int index)
void IntrinsicLocationsBuilderMIPS64::VisitStringCharAt(HInvoke* invoke) {
LocationSummary* locations = new (arena_) LocationSummary(invoke,
@@ -1502,9 +1587,6 @@ void IntrinsicCodeGeneratorMIPS64::Visit ## Name(HInvoke* invoke ATTRIBUTE_UNUSE
UNIMPLEMENTED_INTRINSIC(MathRoundDouble)
UNIMPLEMENTED_INTRINSIC(MathRoundFloat)
-UNIMPLEMENTED_INTRINSIC(UnsafeCASInt)
-UNIMPLEMENTED_INTRINSIC(UnsafeCASLong)
-UNIMPLEMENTED_INTRINSIC(UnsafeCASObject)
UNIMPLEMENTED_INTRINSIC(StringEquals)
UNIMPLEMENTED_INTRINSIC(ReferenceGetReferent)
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 348026551e..8b28ff91d4 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -574,6 +574,17 @@ bool HLoopInformation::IsIn(const HLoopInformation& other) const {
return other.blocks_.IsBitSet(header_->GetBlockId());
}
+bool HLoopInformation::IsLoopInvariant(HInstruction* instruction, bool must_dominate) const {
+ HLoopInformation* other_loop = instruction->GetBlock()->GetLoopInformation();
+ if (other_loop != this && (other_loop == nullptr || !other_loop->IsIn(*this))) {
+ if (must_dominate) {
+ return instruction->GetBlock()->Dominates(GetHeader());
+ }
+ return true;
+ }
+ return false;
+}
+
size_t HLoopInformation::GetLifetimeEnd() const {
size_t last_position = 0;
for (HBasicBlock* back_edge : GetBackEdges()) {
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 6028d4b6fa..7df586692b 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -551,6 +551,12 @@ class HLoopInformation : public ArenaObject<kArenaAllocLoopInfo> {
// Note that `other` *must* be populated before entering this function.
bool IsIn(const HLoopInformation& other) const;
+ // Returns true if instruction is not defined within this loop or any loop nested inside
+ // this loop. If must_dominate is set, only definitions that actually dominate the loop
+ // header can be invariant. Otherwise, any definition outside the loop, including
+ // definitions that appear after the loop, is invariant.
+ bool IsLoopInvariant(HInstruction* instruction, bool must_dominate) const;
+
const ArenaBitVector& GetBlocks() const { return blocks_; }
void Add(HBasicBlock* block);
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index 26a05da4cb..659da068a9 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -373,12 +373,18 @@ void RTPVisitor::SetClassAsTypeInfo(HInstruction* instr,
if (instr->IsInvokeStaticOrDirect() && instr->AsInvokeStaticOrDirect()->IsStringInit()) {
// Calls to String.<init> are replaced with a StringFactory.
if (kIsDebugBuild) {
- ScopedObjectAccess soa(Thread::Current());
+ HInvoke* invoke = instr->AsInvoke();
ClassLinker* cl = Runtime::Current()->GetClassLinker();
- mirror::DexCache* dex_cache = cl->FindDexCache(
- soa.Self(), instr->AsInvoke()->GetDexFile(), false);
- ArtMethod* method = dex_cache->GetResolvedMethod(
- instr->AsInvoke()->GetDexMethodIndex(), cl->GetImagePointerSize());
+ ScopedObjectAccess soa(Thread::Current());
+ StackHandleScope<2> hs(soa.Self());
+ Handle<mirror::DexCache> dex_cache(
+ hs.NewHandle(cl->FindDexCache(soa.Self(), invoke->GetDexFile(), false)));
+ // Use a null loader. We should probably use the compiling method's class loader,
+ // but then we would need to pass it to RTPVisitor just for this debug check. Since
+ // the method is from the String class, the null loader is good enough.
+ Handle<mirror::ClassLoader> loader;
+ ArtMethod* method = cl->ResolveMethod(
+ invoke->GetDexFile(), invoke->GetDexMethodIndex(), dex_cache, loader, nullptr, kDirect);
DCHECK(method != nullptr);
mirror::Class* declaring_class = method->GetDeclaringClass();
DCHECK(declaring_class != nullptr);
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-12-09 14:05:22 +0000