From 9abf894ad0e5a6a1594ee1fa3924965e25e5f86f Mon Sep 17 00:00:00 2001 From: Aart Bik Date: Fri, 14 Oct 2016 09:49:42 -0700 Subject: 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 --- compiler/optimizing/induction_var_range.cc | 206 +++++++++++++++++++---------- compiler/optimizing/induction_var_range.h | 34 +++-- compiler/optimizing/loop_optimization.cc | 67 +++++++--- compiler/optimizing/loop_optimization.h | 2 +- 4 files changed, 209 insertions(+), 100 deletions(-) (limited to 'compiler/optimizing') diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc index 140c7f0c40..663cbaf2de 100644 --- a/compiler/optimizing/induction_var_range.cc +++ b/compiler/optimizing/induction_var_range.cc @@ -162,17 +162,17 @@ bool InductionVarRange::CanGenerateRange(HInstruction* context, /*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 @@ void InductionVarRange::GenerateRange(HInstruction* context, 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 @@ HInstruction* InductionVarRange::GenerateTakenTest(HInstruction* context, 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 @@ bool InductionVarRange::CanGenerateLastValue(HInstruction* instruction) { 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 @@ HInstruction* InductionVarRange::GenerateLastValue(HInstruction* instruction, 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 @@ void InductionVarRange::Replace(HInstruction* instruction, } } +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 @@ InductionVarRange::Value InductionVarRange::MergeVal(Value v1, Value v2, bool is 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 @@ bool InductionVarRange::GenerateCode(HInstruction* context, *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 @@ bool InductionVarRange::GenerateCode(HInstruction* context, 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 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, // Invariants. switch (info->operation) { case HInductionVarAnalysis::kAdd: + case HInductionVarAnalysis::kXor: case HInductionVarAnalysis::kLT: case HInductionVarAnalysis::kLE: case HInductionVarAnalysis::kGT: @@ -823,6 +885,8 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, 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 895130064a..2f70046a27 100644 --- a/compiler/optimizing/induction_var_range.h +++ b/compiler/optimizing/induction_var_range.h @@ -139,6 +139,11 @@ class InductionVarRange { 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 @@ class InductionVarRange { * 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 33fa87d568..703a10402d 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* 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 @@ static bool IsEmptyHeader(HBasicBlock* block, ArenaSet* iset) { return false; } +// Does the loop-body consist of induction cycle and direct control flow only? static bool IsEmptyBody(HBasicBlock* block, ArenaSet* 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 @@ void HLoopOptimization::TraverseLoopsInnerToOuter(LoopNode* node) { } SimplifyInduction(node); SimplifyBlocks(node); - RemoveIfEmptyLoop(node); + if (node->inner == nullptr) { + RemoveIfEmptyInnerLoop(node); + } } } @@ -233,7 +262,7 @@ void HLoopOptimization::SimplifyBlocks(LoopNode* node) { 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::SimplifyBlocks(LoopNode* node) { } } -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 9c4b462a1f..4113357035 100644 --- a/compiler/optimizing/loop_optimization.h +++ b/compiler/optimizing/loop_optimization.h @@ -62,7 +62,7 @@ class HLoopOptimization : public HOptimization { void SimplifyInduction(LoopNode* node); void SimplifyBlocks(LoopNode* node); - void RemoveIfEmptyLoop(LoopNode* node); + void RemoveIfEmptyInnerLoop(LoopNode* node); bool IsOnlyUsedAfterLoop(HLoopInformation* loop_info, HInstruction* instruction, -- cgit v1.2.3-59-g8ed1b