Recognize XOR-based periodic induction.
Rationale:
This is a commonly used construct (e.g. x = !x for booleans
and x ^= 1 for integers). This CL prepares some upcoming
optimizations that exploit such inductions.
Change-Id: I46edffb9de1075a836995daf5c2dfff7891f3034
Test: 530-checker-loops2 and induction_var_analysis_test
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index c501ccf..55fcb12 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -87,11 +87,12 @@
: HOptimization(graph, kInductionPassName),
global_depth_(0),
stack_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)),
- scc_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)),
map_(std::less<HInstruction*>(),
graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)),
+ scc_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)),
cycle_(std::less<HInstruction*>(),
graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)),
+ type_(Primitive::kPrimVoid),
induction_(std::less<HLoopInformation*>(),
graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)) {
}
@@ -103,7 +104,6 @@
for (HReversePostOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) {
HBasicBlock* graph_block = it_graph.Current();
// Don't analyze irreducible loops.
- // TODO(ajcbik): could/should we remove this restriction?
if (graph_block->IsLoopHeader() && !graph_block->GetLoopInformation()->IsIrreducible()) {
VisitLoop(graph_block->GetLoopInformation());
}
@@ -121,7 +121,7 @@
HBasicBlock* loop_block = it_loop.Current();
DCHECK(loop_block->IsInLoop());
if (loop_block->GetLoopInformation() != loop) {
- continue; // Inner loops already visited.
+ continue; // Inner loops visited later.
}
// Visit phi-operations and instructions.
for (HInstructionIterator it(loop_block->GetPhis()); !it.Done(); it.Advance()) {
@@ -285,6 +285,9 @@
} else if (instruction->IsSub()) {
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);
} else if (instruction->IsTypeConversion()) {
update = SolveCnv(instruction->AsTypeConversion());
}
@@ -553,6 +556,27 @@
return nullptr;
}
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveXor(HLoopInformation* loop,
+ 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));
+ 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::SolveCnv(HTypeConversion* conversion) {
Primitive::Type from = conversion->GetInputType();
Primitive::Type to = conversion->GetResultType();
@@ -850,8 +874,8 @@
int64_t value = -1;
if (IsExact(a, &value)) {
if (value == 0) {
- // Simplify 0 + b = b, 0 * b = 0.
- if (op == kAdd) {
+ // Simplify 0 + b = b, 0 ^ b = b, 0 * b = 0.
+ if (op == kAdd || op == kXor) {
return b;
} else if (op == kMul) {
return a;
@@ -867,8 +891,8 @@
}
if (IsExact(b, &value)) {
if (value == 0) {
- // Simplify a + 0 = a, a - 0 = a, a * 0 = 0, -0 = 0.
- if (op == kAdd || op == kSub) {
+ // Simplify a + 0 = a, a - 0 = a, a ^ 0 = a, a * 0 = 0, -0 = 0.
+ if (op == kAdd || op == kSub || op == kXor) {
return a;
} else if (op == kMul || op == kNeg) {
return b;
@@ -939,6 +963,7 @@
case kNeg: inv += " - "; break;
case kMul: inv += " * "; break;
case kDiv: inv += " / "; break;
+ case kXor: inv += " ^ "; break;
case kLT: inv += " < "; break;
case kLE: inv += " <= "; break;
case kGT: inv += " > "; break;