diff options
-rw-r--r-- | compiler/optimizing/induction_var_analysis.cc | 240 | ||||
-rw-r--r-- | compiler/optimizing/induction_var_analysis.h | 13 | ||||
-rw-r--r-- | test/669-checker-break/expected.txt | 1 | ||||
-rw-r--r-- | test/669-checker-break/info.txt | 1 | ||||
-rw-r--r-- | test/669-checker-break/src/Main.java | 328 |
5 files changed, 565 insertions, 18 deletions
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc index ad29ba56ab..d270c6a28e 100644 --- a/compiler/optimizing/induction_var_analysis.cc +++ b/compiler/optimizing/induction_var_analysis.cc @@ -93,6 +93,136 @@ static DataType::Type ImplicitConversion(DataType::Type type) { } } +/** + * Returns true if loop is guarded by "a cmp b" on entry. + */ +static bool IsGuardedBy(HLoopInformation* loop, + IfCondition cmp, + HInstruction* a, + HInstruction* b) { + // Chase back through straightline code to the first potential + // block that has a control dependence. + // guard: if (x) bypass + // | + // entry: straightline code + // | + // preheader + // | + // header + HBasicBlock* guard = loop->GetPreHeader(); + HBasicBlock* entry = loop->GetHeader(); + while (guard->GetPredecessors().size() == 1 && + guard->GetSuccessors().size() == 1) { + entry = guard; + guard = guard->GetSinglePredecessor(); + } + // Find guard. + HInstruction* control = guard->GetLastInstruction(); + if (!control->IsIf()) { + return false; + } + HIf* ifs = control->AsIf(); + HInstruction* if_expr = ifs->InputAt(0); + if (if_expr->IsCondition()) { + IfCondition other_cmp = ifs->IfTrueSuccessor() == entry + ? if_expr->AsCondition()->GetCondition() + : if_expr->AsCondition()->GetOppositeCondition(); + if (if_expr->InputAt(0) == a && if_expr->InputAt(1) == b) { + return cmp == other_cmp; + } else if (if_expr->InputAt(1) == a && if_expr->InputAt(0) == b) { + switch (cmp) { + case kCondLT: return other_cmp == kCondGT; + case kCondLE: return other_cmp == kCondGE; + case kCondGT: return other_cmp == kCondLT; + case kCondGE: return other_cmp == kCondLE; + default: LOG(FATAL) << "unexpected cmp: " << cmp; + } + } + } + return false; +} + +/* Finds first loop header phi use. */ +HInstruction* FindFirstLoopHeaderPhiUse(HLoopInformation* loop, HInstruction* instruction) { + for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) { + if (use.GetUser()->GetBlock() == loop->GetHeader() && + use.GetUser()->IsPhi() && + use.GetUser()->InputAt(1) == instruction) { + return use.GetUser(); + } + } + return nullptr; +} + +/** + * Relinks the Phi structure after break-loop rewriting. + */ +bool FixOutsideUse(HLoopInformation* loop, + HInstruction* instruction, + HInstruction* replacement, + bool rewrite) { + // Deal with regular uses. + const HUseList<HInstruction*>& uses = instruction->GetUses(); + for (auto it = uses.begin(), end = uses.end(); it != end; ) { + HInstruction* user = it->GetUser(); + size_t index = it->GetIndex(); + ++it; // increment prior to potential removal + if (user->GetBlock()->GetLoopInformation() != loop) { + if (replacement == nullptr) { + return false; + } else if (rewrite) { + user->ReplaceInput(replacement, index); + } + } + } + // Deal with environment uses. + const HUseList<HEnvironment*>& env_uses = instruction->GetEnvUses(); + for (auto it = env_uses.begin(), end = env_uses.end(); it != end;) { + HEnvironment* user = it->GetUser(); + size_t index = it->GetIndex(); + ++it; // increment prior to potential removal + if (user->GetHolder()->GetBlock()->GetLoopInformation() != loop) { + if (replacement == nullptr) { + return false; + } else if (rewrite) { + user->RemoveAsUserOfInput(index); + user->SetRawEnvAt(index, replacement); + replacement->AddEnvUseAt(user, index); + } + } + } + return true; +} + +/** + * Test and rewrite the loop body of a break-loop. Returns true on success. + */ +bool RewriteBreakLoopBody(HLoopInformation* loop, + HBasicBlock* body, + HInstruction* cond, + HInstruction* index, + HInstruction* upper, + bool rewrite) { + // Deal with Phis. Outside use prohibited, except for index (which gets exit value). + for (HInstructionIterator it(loop->GetHeader()->GetPhis()); !it.Done(); it.Advance()) { + HInstruction* exit_value = it.Current() == index ? upper : nullptr; + if (!FixOutsideUse(loop, it.Current(), exit_value, rewrite)) { + return false; + } + } + // Deal with other statements in header. + for (HInstruction* m = cond->GetPrevious(), *p = nullptr; m && !m->IsSuspendCheck(); m = p) { + p = m->GetPrevious(); + if (rewrite) { + m->MoveBefore(body->GetFirstInstruction(), false); + } + if (!FixOutsideUse(loop, m, FindFirstLoopHeaderPhiUse(loop, m), rewrite)) { + return false; + } + } + return true; +} + // // Class methods. // @@ -754,6 +884,10 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveConversion( return nullptr; } +// +// Loop trip count analysis methods. +// + void HInductionVarAnalysis::VisitControl(HLoopInformation* loop) { HInstruction* control = loop->GetHeader()->GetLastInstruction(); if (control->IsIf()) { @@ -774,15 +908,16 @@ void HInductionVarAnalysis::VisitControl(HLoopInformation* loop) { if (a == nullptr || b == nullptr) { return; // Loop control is not a sequence. } else if (if_true->GetLoopInformation() != loop && if_false->GetLoopInformation() == loop) { - VisitCondition(loop, a, b, type, condition->GetOppositeCondition()); + VisitCondition(loop, if_false, a, b, type, condition->GetOppositeCondition()); } else if (if_true->GetLoopInformation() == loop && if_false->GetLoopInformation() != loop) { - VisitCondition(loop, a, b, type, condition->GetCondition()); + VisitCondition(loop, if_true, a, b, type, condition->GetCondition()); } } } } void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop, + HBasicBlock* body, InductionInfo* a, InductionInfo* b, DataType::Type type, @@ -790,11 +925,11 @@ void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop, if (a->induction_class == kInvariant && b->induction_class == kLinear) { // Swap condition if induction is at right-hand-side (e.g. U > i is same as i < U). switch (cmp) { - case kCondLT: VisitCondition(loop, b, a, type, kCondGT); break; - case kCondLE: VisitCondition(loop, b, a, type, kCondGE); break; - case kCondGT: VisitCondition(loop, b, a, type, kCondLT); break; - case kCondGE: VisitCondition(loop, b, a, type, kCondLE); break; - case kCondNE: VisitCondition(loop, b, a, type, kCondNE); break; + case kCondLT: VisitCondition(loop, body, b, a, type, kCondGT); break; + case kCondLE: VisitCondition(loop, body, b, a, type, kCondGE); break; + case kCondGT: VisitCondition(loop, body, b, a, type, kCondLT); break; + case kCondGE: VisitCondition(loop, body, b, a, type, kCondLE); break; + case kCondNE: VisitCondition(loop, body, b, a, type, kCondNE); break; default: break; } } else if (a->induction_class == kLinear && b->induction_class == kInvariant) { @@ -802,24 +937,30 @@ void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop, InductionInfo* lower_expr = a->op_b; InductionInfo* upper_expr = b; InductionInfo* stride_expr = a->op_a; - // Constant stride? + // Test for constant stride and integral condition. int64_t stride_value = 0; if (!IsExact(stride_expr, &stride_value)) { - return; + return; // unknown stride + } else if (type != DataType::Type::kInt32 && type != DataType::Type::kInt64) { + return; // not integral } - // Rewrite condition i != U into strict end condition i < U or i > U if this end condition - // is reached exactly (tested by verifying if the loop has a unit stride and the non-strict - // condition would be always taken). + // Since loops with a i != U condition will not be normalized by the method below, first + // try to rewrite a break-loop with terminating condition i != U into an equivalent loop + // with non-strict end condition i <= U or i >= U if such a rewriting is possible and safe. + if (cmp == kCondNE && RewriteBreakLoop(loop, body, stride_value, type)) { + cmp = stride_value > 0 ? kCondLE : kCondGE; + } + // If this rewriting failed, try to rewrite condition i != U into strict end condition i < U + // or i > U if this end condition is reached exactly (tested by verifying if the loop has a + // unit stride and the non-strict condition would be always taken). if (cmp == kCondNE && ((stride_value == +1 && IsTaken(lower_expr, upper_expr, kCondLE)) || (stride_value == -1 && IsTaken(lower_expr, upper_expr, kCondGE)))) { cmp = stride_value > 0 ? kCondLT : kCondGT; } - // Only accept integral condition. A mismatch between the type of condition and the induction - // is only allowed if the, necessarily narrower, induction range fits the narrower control. - if (type != DataType::Type::kInt32 && type != DataType::Type::kInt64) { - return; // not integral - } else if (type != a->type && - !FitsNarrowerControl(lower_expr, upper_expr, stride_value, a->type, cmp)) { + // A mismatch between the type of condition and the induction is only allowed if the, + // necessarily narrower, induction range fits the narrower control. + if (type != a->type && + !FitsNarrowerControl(lower_expr, upper_expr, stride_value, a->type, cmp)) { return; // mismatched type } // Normalize a linear loop control with a nonzero stride: @@ -984,6 +1125,69 @@ bool HInductionVarAnalysis::FitsNarrowerControl(InductionInfo* lower_expr, IsAtMost(upper_expr, &value) && value <= max; } +bool HInductionVarAnalysis::RewriteBreakLoop(HLoopInformation* loop, + HBasicBlock* body, + int64_t stride_value, + DataType::Type type) { + // Only accept unit stride. + if (std::abs(stride_value) != 1) { + return false; + } + // Simple terminating i != U condition, used nowhere else. + HIf* ifs = loop->GetHeader()->GetLastInstruction()->AsIf(); + HInstruction* cond = ifs->InputAt(0); + if (ifs->GetPrevious() != cond || !cond->HasOnlyOneNonEnvironmentUse()) { + return false; + } + int c = LookupInfo(loop, cond->InputAt(0))->induction_class == kLinear ? 0 : 1; + HInstruction* index = cond->InputAt(c); + HInstruction* upper = cond->InputAt(1 - c); + // Safe to rewrite into i <= U? + IfCondition cmp = stride_value > 0 ? kCondLE : kCondGE; + if (!index->IsPhi() || !IsFinite(LookupInfo(loop, upper), stride_value, type, cmp)) { + return false; + } + // Body consists of update to index i only, used nowhere else. + if (body->GetSuccessors().size() != 1 || + body->GetSingleSuccessor() != loop->GetHeader() || + !body->GetPhis().IsEmpty() || + body->GetInstructions().IsEmpty() || + body->GetFirstInstruction() != index->InputAt(1) || + !body->GetFirstInstruction()->HasOnlyOneNonEnvironmentUse() || + !body->GetFirstInstruction()->GetNext()->IsGoto()) { + return false; + } + // Always taken or guarded by enclosing condition. + if (!IsTaken(LookupInfo(loop, index)->op_b, LookupInfo(loop, upper), cmp) && + !IsGuardedBy(loop, cmp, index->InputAt(0), upper)) { + return false; + } + // Test if break-loop body can be written, and do so on success. + if (RewriteBreakLoopBody(loop, body, cond, index, upper, /*rewrite*/ false)) { + RewriteBreakLoopBody(loop, body, cond, index, upper, /*rewrite*/ true); + } else { + return false; + } + // Rewrite condition in HIR. + if (ifs->IfTrueSuccessor() != body) { + cmp = (cmp == kCondLE) ? kCondGT : kCondLT; + } + HInstruction* rep = nullptr; + switch (cmp) { + case kCondLT: rep = new (graph_->GetAllocator()) HLessThan(index, upper); break; + case kCondGT: rep = new (graph_->GetAllocator()) HGreaterThan(index, upper); break; + case kCondLE: rep = new (graph_->GetAllocator()) HLessThanOrEqual(index, upper); break; + case kCondGE: rep = new (graph_->GetAllocator()) HGreaterThanOrEqual(index, upper); break; + default: LOG(FATAL) << cmp; UNREACHABLE(); + } + loop->GetHeader()->ReplaceAndRemoveInstructionWith(cond, rep); + return true; +} + +// +// Helper methods. +// + void HInductionVarAnalysis::AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info) { diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h index 8737b890d9..acad77d35f 100644 --- a/compiler/optimizing/induction_var_analysis.h +++ b/compiler/optimizing/induction_var_analysis.h @@ -195,9 +195,14 @@ class HInductionVarAnalysis : public HOptimization { HInstruction* entry_phi, HTypeConversion* conversion); + // + // Loop trip count analysis methods. + // + // Trip count information. void VisitControl(HLoopInformation* loop); void VisitCondition(HLoopInformation* loop, + HBasicBlock* body, InductionInfo* a, InductionInfo* b, DataType::Type type, @@ -219,6 +224,14 @@ class HInductionVarAnalysis : public HOptimization { int64_t stride_value, DataType::Type type, IfCondition cmp); + bool RewriteBreakLoop(HLoopInformation* loop, + HBasicBlock* body, + int64_t stride_value, + DataType::Type type); + + // + // Helper methods. + // // Assign and lookup. void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info); diff --git a/test/669-checker-break/expected.txt b/test/669-checker-break/expected.txt new file mode 100644 index 0000000000..b0aad4deb5 --- /dev/null +++ b/test/669-checker-break/expected.txt @@ -0,0 +1 @@ +passed diff --git a/test/669-checker-break/info.txt b/test/669-checker-break/info.txt new file mode 100644 index 0000000000..3408b3b238 --- /dev/null +++ b/test/669-checker-break/info.txt @@ -0,0 +1 @@ +Test optimizations of "break" loops. diff --git a/test/669-checker-break/src/Main.java b/test/669-checker-break/src/Main.java new file mode 100644 index 0000000000..e59061b1aa --- /dev/null +++ b/test/669-checker-break/src/Main.java @@ -0,0 +1,328 @@ +/* + * Copyright (C) 2017 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * Tests for optimizations of break-loops, i.e. loops that break + * out of a while-true loop when the end condition is satisfied. + * In particular, the tests focus on break-loops that can be + * rewritten into regular countable loops (this may improve certain + * loops generated by the Kotlin compiler for inclusive ranges). + */ +public class Main { + + /// CHECK-START: int Main.breakLoop(int[]) induction_var_analysis (before) + /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none + /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none + /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none + /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none + /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Zero>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none + /// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<One>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<NE:z\d+>> NotEqual [{{i\d+}},<<Phi>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: If [<<NE>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none + // + /// CHECK-START: int Main.breakLoop(int[]) induction_var_analysis (after) + /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none + /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none + /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none + /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none + /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Zero>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none + /// CHECK-DAG: <<LE:z\d+>> LessThanOrEqual [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: If [<<LE>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<One>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none + // + /// CHECK-START-ARM64: int Main.breakLoop(int[]) loop_optimization (after) + /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none + /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none + /// CHECK-DAG: <<Four:i\d+>> IntConstant 4 loop:none + /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none + /// CHECK-DAG: <<Rep:d\d+>> VecReplicateScalar [<<One>>] loop:none + /// CHECK-DAG: VecStore [<<Nil>>,<<Phi:i\d+>>,<<Rep>>] loop:<<Loop:B\d+>> outer_loop:none + /// CHECK-DAG: Add [<<Phi>>,<<Four>>] loop:<<Loop>> outer_loop:none + static int breakLoop(int[] a) { + int l = 0; + int u = a.length - 1; + int i = l; + if (l <= u) { + while (true) { + a[i] = 1; + if (i == u) break; + i++; + } + } + return i; + } + + /// CHECK-START: int Main.breakLoopDown(int[]) induction_var_analysis (before) + /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none + /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none + /// CHECK-DAG: <<MOne:i\d+>> IntConstant -1 loop:none + /// CHECK-DAG: <<Two:i\d+>> IntConstant 2 loop:none + /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none + /// CHECK-DAG: <<Phi:i\d+>> Phi [{{i\d+}},<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none + /// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<Two>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<NE:z\d+>> NotEqual [<<Phi>>,<<Zero>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: If [<<NE>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<MOne>>] loop:<<Loop>> outer_loop:none + // + /// CHECK-START: int Main.breakLoopDown(int[]) induction_var_analysis (after) + /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none + /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none + /// CHECK-DAG: <<MOne:i\d+>> IntConstant -1 loop:none + /// CHECK-DAG: <<Two:i\d+>> IntConstant 2 loop:none + /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none + /// CHECK-DAG: <<Phi:i\d+>> Phi [{{i\d+}},<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none + /// CHECK-DAG: <<GE:z\d+>> GreaterThanOrEqual [<<Phi>>,<<Zero>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: If [<<GE>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<Two>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<MOne>>] loop:<<Loop>> outer_loop:none + static int breakLoopDown(int[] a) { + int l = 0; + int u = a.length - 1; + int i = u; + if (u >= l) { + while (true) { + a[i] = 2; + if (i == l) break; + i--; + } + } + return i; + } + + /// CHECK-START: int Main.breakLoopSafeConst(int[]) induction_var_analysis (before) + /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none + /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none + /// CHECK-DAG: <<Three:i\d+>> IntConstant 3 loop:none + /// CHECK-DAG: <<L1:i\d+>> IntConstant 2147483631 loop:none + /// CHECK-DAG: <<L2:i\d+>> IntConstant 2147483646 loop:none + /// CHECK-DAG: <<Phi:i\d+>> Phi [<<L1>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none + /// CHECK-DAG: <<Sub:i\d+>> Sub [<<Phi>>,<<L1>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Sub>>,{{i\d+}}] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<Three>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<NE:z\d+>> NotEqual [<<Phi>>,<<L2>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: If [<<NE>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none + // + /// CHECK-START: int Main.breakLoopSafeConst(int[]) induction_var_analysis (after) + /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none + /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none + /// CHECK-DAG: <<Three:i\d+>> IntConstant 3 loop:none + /// CHECK-DAG: <<L1:i\d+>> IntConstant 2147483631 loop:none + /// CHECK-DAG: <<L2:i\d+>> IntConstant 2147483646 loop:none + /// CHECK-DAG: <<Phi:i\d+>> Phi [<<L1>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none + /// CHECK-DAG: <<LE:z\d+>> LessThanOrEqual [<<Phi>>,<<L2>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Sub:i\d+>> Sub [<<Phi>>,<<L1>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Sub>>,{{i\d+}}] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<Three>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none + // + /// CHECK-START-ARM64: int Main.breakLoopSafeConst(int[]) loop_optimization (after) + /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none + /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none + /// CHECK-DAG: <<Three:i\d+>> IntConstant 3 loop:none + /// CHECK-DAG: <<Four:i\d+>> IntConstant 4 loop:none + /// CHECK-DAG: <<Rep:d\d+>> VecReplicateScalar [<<Three>>] loop:none + /// CHECK-DAG: VecStore [<<Par>>,<<Phi:i\d+>>,<<Rep>>] loop:<<Loop:B\d+>> outer_loop:none + /// CHECK-DAG: Add [<<Phi>>,<<Four>>] loop:<<Loop>> outer_loop:none + static int breakLoopSafeConst(int[] a) { + int l = Integer.MAX_VALUE - 16; + int u = Integer.MAX_VALUE - 1; + int i = l; + if (l <= u) { // will be removed by simplifier + while (true) { + a[i - l] = 3; + if (i == u) break; + i++; + } + } + return i; + } + + /// CHECK-START: int Main.breakLoopUnsafeConst(int[]) induction_var_analysis (before) + /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none + /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none + /// CHECK-DAG: <<Four:i\d+>> IntConstant 4 loop:none + /// CHECK-DAG: <<L1:i\d+>> IntConstant 2147483632 loop:none + /// CHECK-DAG: <<L2:i\d+>> IntConstant 2147483647 loop:none + /// CHECK-DAG: <<Phi:i\d+>> Phi [<<L1>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none + /// CHECK-DAG: <<Sub:i\d+>> Sub [<<Phi>>,<<L1>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Sub>>,{{i\d+}}] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<Four>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<NE:z\d+>> NotEqual [<<Phi>>,<<L2>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: If [<<NE>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none + // + /// CHECK-START: int Main.breakLoopUnsafeConst(int[]) induction_var_analysis (after) + /// CHECK-DAG: NotEqual + /// CHECK-NOT: LessThanOrEqual + static int breakLoopUnsafeConst(int[] a) { + int l = Integer.MAX_VALUE - 15; + int u = Integer.MAX_VALUE; + int i = l; + if (l <= u) { // will be removed by simplifier + while (true) { + a[i - l] = 4; + if (i == u) break; // rewriting exit not safe! + i++; + } + } + return i; + } + + /// CHECK-START: int Main.breakLoopNastyPhi(int[]) induction_var_analysis (before) + /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none + /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none + /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none + /// CHECK-DAG: <<Five:i\d+>> IntConstant 5 loop:none + /// CHECK-DAG: <<M123:i\d+>> IntConstant -123 loop:none + /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none + /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Zero>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none + /// CHECK-DAG: <<Wrap:i\d+>> Phi [<<M123>>,<<Phi>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<Five>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<NE:z\d+>> NotEqual [{{i\d+}},<<Phi>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: If [<<NE>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Comb:i\d+>> Phi [<<M123>>,<<Wrap>>] loop:none + /// CHECK-DAG: Return [<<Comb>>] loop:none + // + /// CHECK-START: int Main.breakLoopNastyPhi(int[]) induction_var_analysis (after) + /// CHECK-DAG: NotEqual + /// CHECK-NOT: LessThanOrEqual + static int breakLoopNastyPhi(int[] a) { + int l = 0; + int u = a.length - 1; + int x = -123; + if (l <= u) { + int i = l; + while (true) { + a[i] = 5; + if (i == u) break; + x = i; + i++; + } + } + return x; // keep another phi live + } + + /// CHECK-START: int Main.breakLoopReduction(int[]) induction_var_analysis (before) + /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none + /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none + /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none + /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none + /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Zero>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none + /// CHECK-DAG: <<Red:i\d+>> Phi [<<Zero>>,<<RedI:i\d+>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Get:i\d+>> ArrayGet [<<Nil>>,<<Bnd>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<RedI>> Add [<<Red>>,<<Get>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<NE:z\d+>> NotEqual [{{i\d+}},<<Phi>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: If [<<NE>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Comb:i\d+>> Phi [<<Zero>>,<<RedI>>] loop:none + /// CHECK-DAG: Return [<<Comb>>] loop:none + // + /// CHECK-START: int Main.breakLoopReduction(int[]) induction_var_analysis (after) + /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none + /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none + /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none + /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none + /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Zero>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none + /// CHECK-DAG: <<Red:i\d+>> Phi [<<Zero>>,<<RedI:i\d+>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<LE:z\d+>> LessThanOrEqual [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: If [<<LE>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Get:i\d+>> ArrayGet [<<Nil>>,<<Bnd>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<RedI>> Add [<<Red>>,<<Get>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Comb:i\d+>> Phi [<<Zero>>,<<Red>>] loop:none + /// CHECK-DAG: Return [<<Comb>>] loop:none + // + /// CHECK-START-ARM64: int Main.breakLoopReduction(int[]) loop_optimization (after) + /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none + /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none + /// CHECK-DAG: <<Exp:d\d+>> VecSetScalars [<<Zero>>] loop:none + /// CHECK-DAG: <<VPhi:d\d+>> Phi [<<Exp>>,<<VAdd:d\d+>>] loop:<<Loop:B\d+>> outer_loop:none + /// CHECK-DAG: <<VLoad:d\d+>> VecLoad loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<VAdd>> VecAdd [<<VPhi>>,<<VLoad>>] loop:<<Loop>> outer_loop:none + static int breakLoopReduction(int[] a) { + int l = 0; + int u = a.length - 1; + int x = 0; + if (l <= u) { + int i = l; + while (true) { + x += a[i]; + if (i == u) break; + i++; + } + } + return x; + } + + // + // Test driver. + // + + public static void main(String[] args) { + int[] a = new int[100]; + + expectEquals(99, breakLoop(a)); + for (int i = 0; i < a.length; i++) { + expectEquals(1, a[i]); + } + + expectEquals(0, breakLoopDown(a)); + for (int i = 0; i < a.length; i++) { + expectEquals(2, a[i]); + } + + expectEquals(Integer.MAX_VALUE - 1, breakLoopSafeConst(a)); + for (int i = 0; i < a.length; i++) { + int e = i < 16 ? 3 : 2; + expectEquals(e, a[i]); + } + + expectEquals(Integer.MAX_VALUE, breakLoopUnsafeConst(a)); + for (int i = 0; i < a.length; i++) { + int e = i < 16 ? 4 : 2; + expectEquals(e, a[i]); + } + + expectEquals(98, breakLoopNastyPhi(a)); + for (int i = 0; i < a.length; i++) { + expectEquals(5, a[i]); + } + + expectEquals(500, breakLoopReduction(a)); + + System.out.println("passed"); + } + + private static void expectEquals(int expected, int result) { + if (expected != result) { + throw new Error("Expected: " + expected + ", found: " + result); + } + } +} |