summaryrefslogtreecommitdiff
path: root/compiler/optimizing
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/optimizing')
-rw-r--r--compiler/optimizing/induction_var_analysis.cc42
-rw-r--r--compiler/optimizing/induction_var_analysis.h7
-rw-r--r--compiler/optimizing/induction_var_analysis_test.cc92
-rw-r--r--compiler/optimizing/induction_var_range.cc2
-rw-r--r--compiler/optimizing/loop_optimization.cc1
-rw-r--r--compiler/optimizing/optimizing_compiler.cc9
6 files changed, 132 insertions, 21 deletions
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index 55fcb12fa8..38937bf488 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -286,8 +286,11 @@ void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) {
update = SolveAddSub(
loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kSub, true);
} else if (instruction->IsXor()) {
- update = SolveXor(
- loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), true);
+ update = SolveXor(loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1));
+ } else if (instruction->IsEqual()) {
+ update = SolveTest(loop, phi, instruction, 0);
+ } else if (instruction->IsNotEqual()) {
+ update = SolveTest(loop, phi, instruction, 1);
} else if (instruction->IsTypeConversion()) {
update = SolveCnv(instruction->AsTypeConversion());
}
@@ -560,19 +563,34 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveXor(HLoopInfor
HInstruction* entry_phi,
HInstruction* instruction,
HInstruction* x,
- HInstruction* y,
- bool is_first_call) {
- InductionInfo* b = LookupInfo(loop, y);
- // Solve within a tight cycle on x = x ^ c.
- if (b != nullptr && b->induction_class == kInvariant) {
- if (x == entry_phi && entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) {
- InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
+ HInstruction* y) {
+ // Solve within a tight cycle on x = c ^ x or x = x ^ c.
+ if (entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) {
+ InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
+ InductionInfo* a = LookupInfo(loop, x);
+ if (a != nullptr && a->induction_class == kInvariant && entry_phi == y) {
+ return CreateInduction(kPeriodic, CreateInvariantOp(kXor, a, initial), initial, type_);
+ }
+ InductionInfo* b = LookupInfo(loop, y);
+ if (b != nullptr && b->induction_class == kInvariant && entry_phi == x) {
return CreateInduction(kPeriodic, CreateInvariantOp(kXor, initial, b), initial, type_);
}
}
- // Try the other way around if considered for first time.
- if (is_first_call) {
- return SolveXor(loop, entry_phi, instruction, y, x, false);
+ return nullptr;
+}
+
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveTest(HLoopInformation* loop,
+ HInstruction* entry_phi,
+ HInstruction* instruction,
+ int64_t opposite_value) {
+ // Detect hidden XOR construction in tight cycles on x = (x == 0) or x = (x != 1).
+ int64_t value = -1;
+ HInstruction* x = instruction->InputAt(0);
+ HInstruction* y = instruction->InputAt(1);
+ if (IsExact(LookupInfo(loop, x), &value) && value == opposite_value) {
+ return SolveXor(loop, entry_phi, instruction, graph_->GetIntConstant(1), y);
+ } else if (IsExact(LookupInfo(loop, y), &value) && value == opposite_value) {
+ return SolveXor(loop, entry_phi, instruction, x, graph_->GetIntConstant(1));
}
return nullptr;
}
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index 06aee31b88..d19078248c 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -177,8 +177,11 @@ class HInductionVarAnalysis : public HOptimization {
HInstruction* entry_phi,
HInstruction* instruction,
HInstruction* x,
- HInstruction* y,
- bool is_first_call); // possibly swaps x and y to try again
+ HInstruction* y);
+ InductionInfo* SolveTest(HLoopInformation* loop,
+ HInstruction* entry_phi,
+ HInstruction* instruction,
+ int64_t oppositive_value);
InductionInfo* SolveCnv(HTypeConversion* conversion);
// Trip count information.
diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
index 7c467f6c94..7599c8fd79 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -527,22 +527,108 @@ TEST_F(InductionVarAnalysisTest, FindXorPeriodicInduction) {
EXPECT_STREQ("periodic((1), (0)):PrimInt", GetInductionInfo(x, 0).c_str());
}
+TEST_F(InductionVarAnalysisTest, FindXorConstantLeftPeriodicInduction) {
+ // Setup:
+ // k = 1;
+ // for (int i = 0; i < 100; i++) {
+ // k = 1 ^ k;
+ // }
+ BuildLoopNest(1);
+ HPhi* k = InsertLoopPhi(0, 0);
+ k->AddInput(constant1_);
+
+ HInstruction* x = InsertInstruction(
+ new (&allocator_) HXor(Primitive::kPrimInt, constant1_, k), 0);
+ k->AddInput(x);
+ PerformInductionVarAnalysis();
+
+ EXPECT_STREQ("periodic(((1) ^ (1)), (1)):PrimInt", GetInductionInfo(x, 0).c_str());
+}
+
TEST_F(InductionVarAnalysisTest, FindXor100PeriodicInduction) {
// Setup:
- // k = 100;
+ // k = 1;
// for (int i = 0; i < 100; i++) {
// k = k ^ 100;
// }
BuildLoopNest(1);
HPhi* k = InsertLoopPhi(0, 0);
- k->AddInput(constant100_);
+ k->AddInput(constant1_);
HInstruction* x = InsertInstruction(
new (&allocator_) HXor(Primitive::kPrimInt, k, constant100_), 0);
k->AddInput(x);
PerformInductionVarAnalysis();
- EXPECT_STREQ("periodic(((100) ^ (100)), (100)):PrimInt", GetInductionInfo(x, 0).c_str());
+ EXPECT_STREQ("periodic(((1) ^ (100)), (1)):PrimInt", GetInductionInfo(x, 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindBooleanEqPeriodicInduction) {
+ // Setup:
+ // k = 0;
+ // for (int i = 0; i < 100; i++) {
+ // k = (k == 0);
+ // }
+ BuildLoopNest(1);
+ HPhi* k = InsertLoopPhi(0, 0);
+ k->AddInput(constant0_);
+
+ HInstruction* x = InsertInstruction(new (&allocator_) HEqual(k, constant0_), 0);
+ k->AddInput(x);
+ PerformInductionVarAnalysis();
+
+ EXPECT_STREQ("periodic((1), (0)):PrimBoolean", GetInductionInfo(x, 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindBooleanEqConstantLeftPeriodicInduction) {
+ // Setup:
+ // k = 0;
+ // for (int i = 0; i < 100; i++) {
+ // k = (0 == k);
+ // }
+ BuildLoopNest(1);
+ HPhi* k = InsertLoopPhi(0, 0);
+ k->AddInput(constant0_);
+
+ HInstruction* x = InsertInstruction(new (&allocator_) HEqual(constant0_, k), 0);
+ k->AddInput(x);
+ PerformInductionVarAnalysis();
+
+ EXPECT_STREQ("periodic((1), (0)):PrimBoolean", GetInductionInfo(x, 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindBooleanNePeriodicInduction) {
+ // Setup:
+ // k = 0;
+ // for (int i = 0; i < 100; i++) {
+ // k = (k != 1);
+ // }
+ BuildLoopNest(1);
+ HPhi* k = InsertLoopPhi(0, 0);
+ k->AddInput(constant0_);
+
+ HInstruction* x = InsertInstruction(new (&allocator_) HNotEqual(k, constant1_), 0);
+ k->AddInput(x);
+ PerformInductionVarAnalysis();
+
+ EXPECT_STREQ("periodic((1), (0)):PrimBoolean", GetInductionInfo(x, 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindBooleanNeConstantLeftPeriodicInduction) {
+ // Setup:
+ // k = 0;
+ // for (int i = 0; i < 100; i++) {
+ // k = (1 != k);
+ // }
+ BuildLoopNest(1);
+ HPhi* k = InsertLoopPhi(0, 0);
+ k->AddInput(constant0_);
+
+ HInstruction* x = InsertInstruction(new (&allocator_) HNotEqual(constant1_, k), 0);
+ k->AddInput(x);
+ PerformInductionVarAnalysis();
+
+ EXPECT_STREQ("periodic((1), (0)):PrimBoolean", GetInductionInfo(x, 0).c_str());
}
TEST_F(InductionVarAnalysisTest, FindDerivedPeriodicInduction) {
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index 663cbaf2de..7cc8b1ea4c 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -862,7 +862,7 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info,
}
// Verify type safety.
Primitive::Type type = Primitive::kPrimInt;
- if (info->type != type) {
+ if (info->type != Primitive::kPrimInt && info->type != Primitive::kPrimBoolean) {
return false;
}
// Handle current operation.
diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
index 703a10402d..b88e73b979 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -221,6 +221,7 @@ void HLoopOptimization::TraverseLoopsInnerToOuter(LoopNode* node) {
if (current_induction_simplification_count != induction_simplication_count_) {
induction_range_.ReVisit(node->loop_info);
}
+ SimplifyBlocks(node);
SimplifyInduction(node);
SimplifyBlocks(node);
if (node->inner == nullptr) {
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 6ba0963720..532ea43043 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -743,8 +743,10 @@ void OptimizingCompiler::RunOptimizations(HGraph* graph,
HLoopOptimization* loop = new (arena) HLoopOptimization(graph, induction);
HSharpening* sharpening = new (arena) HSharpening(graph, codegen, dex_compilation_unit, driver);
InstructionSimplifier* simplify2 = new (arena) InstructionSimplifier(
- graph, stats, "instruction_simplifier$after_bce");
+ graph, stats, "instruction_simplifier$after_inlining");
InstructionSimplifier* simplify3 = new (arena) InstructionSimplifier(
+ graph, stats, "instruction_simplifier$after_bce");
+ InstructionSimplifier* simplify4 = new (arena) InstructionSimplifier(
graph, stats, "instruction_simplifier$before_codegen");
IntrinsicsRecognizer* intrinsics = new (arena) IntrinsicsRecognizer(graph, stats);
@@ -764,6 +766,7 @@ void OptimizingCompiler::RunOptimizations(HGraph* graph,
// redundant suspend checks to recognize empty blocks.
select_generator,
fold2, // TODO: if we don't inline we can also skip fold2.
+ simplify2,
side_effects,
gvn,
licm,
@@ -771,13 +774,13 @@ void OptimizingCompiler::RunOptimizations(HGraph* graph,
bce,
loop,
fold3, // evaluates code generated by dynamic bce
- simplify2,
+ simplify3,
lse,
dce2,
// The codegen has a few assumptions that only the instruction simplifier
// can satisfy. For example, the code generator does not expect to see a
// HTypeConversion from a type to the same type.
- simplify3,
+ simplify4,
};
RunOptimizations(optimizations2, arraysize(optimizations2), pass_observer);
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-10-21 10:21:47 +0000