Enable last value generation of periodic sequence.
Rationale:
This helps to eliminate more dead induction. For example,
CaffeineLogic when compiled with latest Jack improves with
a 1.3 speedup (2900us -> 2200us) due to eliminating first
loop (second loop can be removed also, but for a later
case). The currently benchmarks.dex has a different construct
for the periodics, however, still to be recognized.
Test: test-art-host
Change-Id: Ia81649a207a2b1f03ead0855436862ed4e4f45e0
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index 140c7f0..663cbaf 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -162,17 +162,17 @@
/*out*/bool* needs_taken_test) {
bool is_last_value = false;
int64_t stride_value = 0;
- return GenerateCode(context,
- instruction,
- is_last_value,
- nullptr,
- nullptr,
- nullptr,
- nullptr,
- nullptr, // nothing generated yet
- &stride_value,
- needs_finite_test,
- needs_taken_test)
+ return GenerateRangeOrLastValue(context,
+ instruction,
+ is_last_value,
+ nullptr,
+ nullptr,
+ nullptr,
+ nullptr,
+ nullptr, // nothing generated yet
+ &stride_value,
+ needs_finite_test,
+ needs_taken_test)
&& (stride_value == -1 ||
stride_value == 0 ||
stride_value == 1); // avoid wrap-around anomalies.
@@ -187,17 +187,17 @@
bool is_last_value = false;
int64_t stride_value = 0;
bool b1, b2; // unused
- if (!GenerateCode(context,
- instruction,
- is_last_value,
- graph,
- block,
- lower,
- upper,
- nullptr,
- &stride_value,
- &b1,
- &b2)) {
+ if (!GenerateRangeOrLastValue(context,
+ instruction,
+ is_last_value,
+ graph,
+ block,
+ lower,
+ upper,
+ nullptr,
+ &stride_value,
+ &b1,
+ &b2)) {
LOG(FATAL) << "Failed precondition: CanGenerateRange()";
}
}
@@ -209,17 +209,17 @@
bool is_last_value = false;
int64_t stride_value = 0;
bool b1, b2; // unused
- if (!GenerateCode(context,
- context,
- is_last_value,
- graph,
- block,
- nullptr,
- nullptr,
- &taken_test,
- &stride_value,
- &b1,
- &b2)) {
+ if (!GenerateRangeOrLastValue(context,
+ context,
+ is_last_value,
+ graph,
+ block,
+ nullptr,
+ nullptr,
+ &taken_test,
+ &stride_value,
+ &b1,
+ &b2)) {
LOG(FATAL) << "Failed precondition: CanGenerateRange()";
}
return taken_test;
@@ -230,17 +230,17 @@
int64_t stride_value = 0;
bool needs_finite_test = false;
bool needs_taken_test = false;
- return GenerateCode(instruction,
- instruction,
- is_last_value,
- nullptr,
- nullptr,
- nullptr,
- nullptr,
- nullptr, // nothing generated yet
- &stride_value,
- &needs_finite_test,
- &needs_taken_test)
+ return GenerateRangeOrLastValue(instruction,
+ instruction,
+ is_last_value,
+ nullptr,
+ nullptr,
+ nullptr,
+ nullptr,
+ nullptr, // nothing generated yet
+ &stride_value,
+ &needs_finite_test,
+ &needs_taken_test)
&& !needs_finite_test && !needs_taken_test;
}
@@ -251,17 +251,17 @@
bool is_last_value = true;
int64_t stride_value = 0;
bool b1, b2; // unused
- if (!GenerateCode(instruction,
- instruction,
- is_last_value,
- graph,
- block,
- &last_value,
- &last_value,
- nullptr,
- &stride_value,
- &b1,
- &b2)) {
+ if (!GenerateRangeOrLastValue(instruction,
+ instruction,
+ is_last_value,
+ graph,
+ block,
+ &last_value,
+ &last_value,
+ nullptr,
+ &stride_value,
+ &b1,
+ &b2)) {
LOG(FATAL) << "Failed precondition: CanGenerateLastValue()";
}
return last_value;
@@ -280,6 +280,12 @@
}
}
+bool InductionVarRange::IsFinite(HLoopInformation* loop) const {
+ HInductionVarAnalysis::InductionInfo *trip =
+ induction_analysis_->LookupInfo(loop, GetLoopControl(loop));
+ return trip != nullptr && !IsUnsafeTripCount(trip);
+}
+
//
// Private class methods.
//
@@ -732,17 +738,17 @@
return Value();
}
-bool InductionVarRange::GenerateCode(HInstruction* context,
- HInstruction* instruction,
- bool is_last_value,
- HGraph* graph,
- HBasicBlock* block,
- /*out*/HInstruction** lower,
- /*out*/HInstruction** upper,
- /*out*/HInstruction** taken_test,
- /*out*/int64_t* stride_value,
- /*out*/bool* needs_finite_test,
- /*out*/bool* needs_taken_test) const {
+bool InductionVarRange::GenerateRangeOrLastValue(HInstruction* context,
+ HInstruction* instruction,
+ bool is_last_value,
+ HGraph* graph,
+ HBasicBlock* block,
+ /*out*/HInstruction** lower,
+ /*out*/HInstruction** upper,
+ /*out*/HInstruction** taken_test,
+ /*out*/int64_t* stride_value,
+ /*out*/bool* needs_finite_test,
+ /*out*/bool* needs_taken_test) const {
HLoopInformation* loop = nullptr;
HInductionVarAnalysis::InductionInfo* info = nullptr;
HInductionVarAnalysis::InductionInfo* trip = nullptr;
@@ -760,12 +766,17 @@
*needs_taken_test = IsBodyTripCount(trip);
// Handle last value request.
if (is_last_value) {
- if (info->induction_class != HInductionVarAnalysis::kLinear) {
- return false;
- } else if (*stride_value > 0) {
- lower = nullptr;
+ if (info->induction_class == HInductionVarAnalysis::kLinear) {
+ if (*stride_value > 0) {
+ lower = nullptr;
+ } else {
+ upper = nullptr;
+ }
+ } else if (info->induction_class == HInductionVarAnalysis::kPeriodic) {
+ DCHECK(!in_body);
+ return GenerateLastValuePeriodic(info, trip, graph, block, lower, needs_taken_test);
} else {
- upper = nullptr;
+ return false;
}
}
// Code generation for taken test: generate the code when requested or otherwise analyze
@@ -787,6 +798,56 @@
GenerateCode(info, trip, graph, block, upper, in_body, /* is_min */ false);
}
+bool InductionVarRange::GenerateLastValuePeriodic(HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ HGraph* graph,
+ HBasicBlock* block,
+ /*out*/HInstruction** result,
+ /*out*/bool* needs_taken_test) const {
+ DCHECK(info->induction_class == HInductionVarAnalysis::kPeriodic);
+ // Count period.
+ int32_t period = 1;
+ for (HInductionVarAnalysis::InductionInfo* p = info;
+ p->induction_class == HInductionVarAnalysis::kPeriodic;
+ p = p->op_b, ++period) {}
+ // Handle periodic(x, y) case for restricted types.
+ if (period != 2 ||
+ trip->op_a->type != Primitive::kPrimInt ||
+ (info->type != Primitive::kPrimInt && info->type != Primitive::kPrimBoolean)) {
+ return false; // TODO: easy to generalize
+ }
+ HInstruction* x_instr = nullptr;
+ HInstruction* y_instr = nullptr;
+ HInstruction* trip_expr = nullptr;
+ if (GenerateCode(info->op_a, nullptr, graph, block, graph ? &x_instr : nullptr, false, false) &&
+ GenerateCode(info->op_b, nullptr, graph, block, graph ? &y_instr : nullptr, false, false) &&
+ GenerateCode(trip->op_a, nullptr, graph, block, graph ? &trip_expr : nullptr, false, false)) {
+ // During actual code generation (graph != nullptr),
+ // generate is_even ? x : y select instruction.
+ if (graph != nullptr) {
+ HInstruction* is_even = Insert(block, new (graph->GetArena()) HEqual(
+ Insert(block, new (graph->GetArena()) HAnd(
+ Primitive::kPrimInt, trip_expr, graph->GetIntConstant(1))),
+ graph->GetIntConstant(0), kNoDexPc));
+ *result = Insert(block, new (graph->GetArena()) HSelect(is_even, x_instr, y_instr, kNoDexPc));
+ }
+ // Guard select with taken test if needed.
+ if (*needs_taken_test) {
+ HInstruction* taken_test = nullptr;
+ if (!GenerateCode(
+ trip->op_b, nullptr, graph, block, graph ? &taken_test : nullptr, false, false)) {
+ return false;
+ } else if (graph != nullptr) {
+ *result = Insert(block,
+ new (graph->GetArena()) HSelect(taken_test, *result, x_instr, kNoDexPc));
+ }
+ *needs_taken_test = false; // taken care of
+ }
+ return true;
+ }
+ return false;
+}
+
bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
HGraph* graph, // when set, code is generated
@@ -812,6 +873,7 @@
// Invariants.
switch (info->operation) {
case HInductionVarAnalysis::kAdd:
+ case HInductionVarAnalysis::kXor:
case HInductionVarAnalysis::kLT:
case HInductionVarAnalysis::kLE:
case HInductionVarAnalysis::kGT:
@@ -823,6 +885,8 @@
switch (info->operation) {
case HInductionVarAnalysis::kAdd:
operation = new (graph->GetArena()) HAdd(type, opa, opb); break;
+ case HInductionVarAnalysis::kXor:
+ operation = new (graph->GetArena()) HXor(type, opa, opb); break;
case HInductionVarAnalysis::kLT:
operation = new (graph->GetArena()) HLessThan(opa, opb); break;
case HInductionVarAnalysis::kLE:
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index 8951300..2f70046 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -139,6 +139,11 @@
induction_analysis_->VisitLoop(loop);
}
+ /**
+ * Checks if header logic of a loop terminates.
+ */
+ bool IsFinite(HLoopInformation* loop) const;
+
private:
/*
* Enum used in IsConstant() request.
@@ -218,17 +223,24 @@
* success. With values nullptr, the method can be used to determine if code generation
* would be successful without generating actual code yet.
*/
- bool GenerateCode(HInstruction* context,
- HInstruction* instruction,
- bool is_last_val,
- HGraph* graph,
- HBasicBlock* block,
- /*out*/ HInstruction** lower,
- /*out*/ HInstruction** upper,
- /*out*/ HInstruction** taken_test,
- /*out*/ int64_t* stride_value,
- /*out*/ bool* needs_finite_test,
- /*out*/ bool* needs_taken_test) const;
+ bool GenerateRangeOrLastValue(HInstruction* context,
+ HInstruction* instruction,
+ bool is_last_val,
+ HGraph* graph,
+ HBasicBlock* block,
+ /*out*/ HInstruction** lower,
+ /*out*/ HInstruction** upper,
+ /*out*/ HInstruction** taken_test,
+ /*out*/ int64_t* stride_value,
+ /*out*/ bool* needs_finite_test,
+ /*out*/ bool* needs_taken_test) const;
+
+ bool GenerateLastValuePeriodic(HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ HGraph* graph,
+ HBasicBlock* block,
+ /*out*/HInstruction** result,
+ /*out*/ bool* needs_taken_test) const;
bool GenerateCode(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
index 33fa87d..703a104 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -20,17 +20,37 @@
namespace art {
-// TODO: Generalize to cycles, as found by induction analysis?
+// Detects a potential induction cycle. Note that the actual induction
+// information is queried later if its last value is really needed.
static bool IsPhiInduction(HPhi* phi, ArenaSet<HInstruction*>* iset) {
DCHECK(iset->empty());
HInputsRef inputs = phi->GetInputs();
- if (inputs.size() == 2 && (inputs[1]->IsAdd() || inputs[1]->IsSub())) {
- HInstruction* addsub = inputs[1];
- if (addsub->InputAt(0) == phi || addsub->InputAt(1) == phi) {
- if (addsub->GetUses().HasExactlyOneElement()) {
- iset->insert(phi);
- iset->insert(addsub);
- return true;
+ if (inputs.size() == 2) {
+ HLoopInformation* loop_info = phi->GetBlock()->GetLoopInformation();
+ HInstruction* op = inputs[1];
+ if (op->GetBlock()->GetLoopInformation() == loop_info) {
+ // Chase a simple chain back to phi.
+ while (!op->IsPhi()) {
+ // Binary operation with single use in same loop.
+ if (!op->IsBinaryOperation() || !op->GetUses().HasExactlyOneElement()) {
+ return false;
+ }
+ // Chase back either through left or right operand.
+ iset->insert(op);
+ HInstruction* a = op->InputAt(0);
+ HInstruction* b = op->InputAt(1);
+ if (a->GetBlock()->GetLoopInformation() == loop_info && b != phi) {
+ op = a;
+ } else if (b->GetBlock()->GetLoopInformation() == loop_info) {
+ op = b;
+ } else {
+ return false;
+ }
+ }
+ // Closed the cycle?
+ if (op == phi) {
+ iset->insert(phi);
+ return true;
}
}
}
@@ -62,16 +82,23 @@
return false;
}
+// Does the loop-body consist of induction cycle and direct control flow only?
static bool IsEmptyBody(HBasicBlock* block, ArenaSet<HInstruction*>* iset) {
- HInstruction* phi = block->GetFirstPhi();
- HInstruction* i = block->GetFirstInstruction();
- return phi == nullptr && iset->find(i) != iset->end() &&
- i->GetNext() != nullptr && i->GetNext()->IsGoto();
+ if (block->GetFirstPhi() == nullptr) {
+ for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
+ HInstruction* instruction = it.Current();
+ if (!instruction->IsGoto() && iset->find(instruction) == iset->end()) {
+ return false;
+ }
+ }
+ return true;
+ }
+ return false;
}
+// Remove the instruction from the graph. A bit more elaborate than the usual
+// instruction removal, since there may be a cycle in the use structure.
static void RemoveFromCycle(HInstruction* instruction) {
- // A bit more elaborate than the usual instruction removal,
- // since there may be a cycle in the use structure.
instruction->RemoveAsUserOfAllInputs();
instruction->RemoveEnvironmentUsers();
instruction->GetBlock()->RemoveInstructionOrPhi(instruction, /*ensure_safety=*/ false);
@@ -196,7 +223,9 @@
}
SimplifyInduction(node);
SimplifyBlocks(node);
- RemoveIfEmptyLoop(node);
+ if (node->inner == nullptr) {
+ RemoveIfEmptyInnerLoop(node);
+ }
}
}
@@ -233,7 +262,7 @@
block->RemoveInstruction(instruction);
}
}
- // Remove trivial control flow blocks from the loop body, again usually resulting
+ // Remove trivial control flow blocks from the loop-body, again usually resulting
// from eliminating induction cycles.
if (block->GetPredecessors().size() == 1 &&
block->GetSuccessors().size() == 1 &&
@@ -252,9 +281,13 @@
}
}
-void HLoopOptimization::RemoveIfEmptyLoop(LoopNode* node) {
+void HLoopOptimization::RemoveIfEmptyInnerLoop(LoopNode* node) {
HBasicBlock* header = node->loop_info->GetHeader();
HBasicBlock* preheader = node->loop_info->GetPreHeader();
+ // Ensure loop header logic is finite.
+ if (!induction_range_.IsFinite(node->loop_info)) {
+ return;
+ }
// Ensure there is only a single loop-body (besides the header).
HBasicBlock* body = nullptr;
for (HBlocksInLoopIterator it(*node->loop_info); !it.Done(); it.Advance()) {
diff --git a/compiler/optimizing/loop_optimization.h b/compiler/optimizing/loop_optimization.h
index 9c4b462..4113357 100644
--- a/compiler/optimizing/loop_optimization.h
+++ b/compiler/optimizing/loop_optimization.h
@@ -62,7 +62,7 @@
void SimplifyInduction(LoopNode* node);
void SimplifyBlocks(LoopNode* node);
- void RemoveIfEmptyLoop(LoopNode* node);
+ void RemoveIfEmptyInnerLoop(LoopNode* node);
bool IsOnlyUsedAfterLoop(HLoopInformation* loop_info,
HInstruction* instruction,