Recognize countable "break" loops
Rationale:
A particular break loop is generated by e.g. Kotlin
(or it can be expressed in Java as well) if the upper
(or lower) bound is inclusive, but a comparison test
would be too dangerous. The ART compiler often has
better range analysis (e.g. after inlining) to convert
such constructs back to countable loops, which are
more amenable to optimizations. For instance, we get
more than 200% improvement on the KotlinMicroLoops
benchmark, while close to 70 loops are recognized
in the Kotlin support library itself.
Bug: 67601686
Test: test-art-host test-art-target
Change-Id: I67e5c832df57e096efe2cf43a8579d9c10ca33e6
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index ad29ba5..d270c6a 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -93,6 +93,136 @@
}
}
+/**
+ * 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 @@
return nullptr;
}
+//
+// Loop trip count analysis methods.
+//
+
void HInductionVarAnalysis::VisitControl(HLoopInformation* loop) {
HInstruction* control = loop->GetHeader()->GetLastInstruction();
if (control->IsIf()) {
@@ -774,15 +908,16 @@
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 @@
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 @@
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 @@
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 8737b89..acad77d 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -195,9 +195,14 @@
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 @@
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 0000000..b0aad4d
--- /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 0000000..3408b3b
--- /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 0000000..e59061b
--- /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);
+ }
+ }
+}