ART: Enable scalar loop peeling and unrolling.
Turn on scalar loop peeling and unrolling by default.
Test: 482-checker-loop-back-edge-use, 530-checker-peel-unroll
Test: test-art-host, test-art-target, boot-to-gui
Change-Id: Ibfe1b54f790a97b281e85396da2985e0f22c2834
diff --git a/compiler/optimizing/loop_analysis.cc b/compiler/optimizing/loop_analysis.cc
index a0760ef..a212445 100644
--- a/compiler/optimizing/loop_analysis.cc
+++ b/compiler/optimizing/loop_analysis.cc
@@ -35,6 +35,9 @@
for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
HInstruction* instruction = it.Current();
+ if (it.Current()->GetType() == DataType::Type::kInt64) {
+ analysis_results->has_long_type_instructions_ = true;
+ }
if (MakesScalarPeelingUnrollingNonBeneficial(instruction)) {
analysis_results->has_instructions_preventing_scalar_peeling_ = true;
analysis_results->has_instructions_preventing_scalar_unrolling_ = true;
@@ -61,34 +64,29 @@
return false;
}
-class Arm64LoopHelper : public ArchDefaultLoopHelper {
+// Default implementation of loop helper; used for all targets unless a custom implementation
+// is provided. Enables scalar loop peeling and unrolling with the most conservative heuristics.
+class ArchDefaultLoopHelper : public ArchNoOptsLoopHelper {
public:
// Scalar loop unrolling parameters and heuristics.
//
// Maximum possible unrolling factor.
- static constexpr uint32_t kArm64ScalarMaxUnrollFactor = 2;
+ static constexpr uint32_t kScalarMaxUnrollFactor = 2;
// Loop's maximum instruction count. Loops with higher count will not be peeled/unrolled.
- static constexpr uint32_t kArm64ScalarHeuristicMaxBodySizeInstr = 40;
+ static constexpr uint32_t kScalarHeuristicMaxBodySizeInstr = 17;
// Loop's maximum basic block count. Loops with higher count will not be peeled/unrolled.
- static constexpr uint32_t kArm64ScalarHeuristicMaxBodySizeBlocks = 8;
+ static constexpr uint32_t kScalarHeuristicMaxBodySizeBlocks = 6;
- // SIMD loop unrolling parameters and heuristics.
- //
- // Maximum possible unrolling factor.
- static constexpr uint32_t kArm64SimdMaxUnrollFactor = 8;
- // Loop's maximum instruction count. Loops with higher count will not be unrolled.
- static constexpr uint32_t kArm64SimdHeuristicMaxBodySizeInstr = 50;
-
- bool IsLoopTooBigForScalarPeelingUnrolling(LoopAnalysisInfo* loop_analysis_info) const OVERRIDE {
- size_t instr_num = loop_analysis_info->GetNumberOfInstructions();
- size_t bb_num = loop_analysis_info->GetNumberOfBasicBlocks();
- return (instr_num >= kArm64ScalarHeuristicMaxBodySizeInstr ||
- bb_num >= kArm64ScalarHeuristicMaxBodySizeBlocks);
+ bool IsLoopNonBeneficialForScalarOpts(LoopAnalysisInfo* loop_analysis_info) const OVERRIDE {
+ return loop_analysis_info->HasLongTypeInstructions() ||
+ IsLoopTooBig(loop_analysis_info,
+ kScalarHeuristicMaxBodySizeInstr,
+ kScalarHeuristicMaxBodySizeBlocks);
}
uint32_t GetScalarUnrollingFactor(HLoopInformation* loop_info ATTRIBUTE_UNUSED,
uint64_t trip_count) const OVERRIDE {
- uint32_t desired_unrolling_factor = kArm64ScalarMaxUnrollFactor;
+ uint32_t desired_unrolling_factor = kScalarMaxUnrollFactor;
if (trip_count < desired_unrolling_factor || trip_count % desired_unrolling_factor != 0) {
return kNoUnrollingFactor;
}
@@ -98,6 +96,38 @@
bool IsLoopPeelingEnabled() const OVERRIDE { return true; }
+ protected:
+ bool IsLoopTooBig(LoopAnalysisInfo* loop_analysis_info,
+ size_t instr_threshold,
+ size_t bb_threshold) const {
+ size_t instr_num = loop_analysis_info->GetNumberOfInstructions();
+ size_t bb_num = loop_analysis_info->GetNumberOfBasicBlocks();
+ return (instr_num >= instr_threshold || bb_num >= bb_threshold);
+ }
+};
+
+// Custom implementation of loop helper for arm64 target. Enables heuristics for scalar loop
+// peeling and unrolling and supports SIMD loop unrolling.
+class Arm64LoopHelper : public ArchDefaultLoopHelper {
+ public:
+ // SIMD loop unrolling parameters and heuristics.
+ //
+ // Maximum possible unrolling factor.
+ static constexpr uint32_t kArm64SimdMaxUnrollFactor = 8;
+ // Loop's maximum instruction count. Loops with higher count will not be unrolled.
+ static constexpr uint32_t kArm64SimdHeuristicMaxBodySizeInstr = 50;
+
+ // Loop's maximum instruction count. Loops with higher count will not be peeled/unrolled.
+ static constexpr uint32_t kArm64ScalarHeuristicMaxBodySizeInstr = 40;
+ // Loop's maximum basic block count. Loops with higher count will not be peeled/unrolled.
+ static constexpr uint32_t kArm64ScalarHeuristicMaxBodySizeBlocks = 8;
+
+ bool IsLoopNonBeneficialForScalarOpts(LoopAnalysisInfo* loop_analysis_info) const OVERRIDE {
+ return IsLoopTooBig(loop_analysis_info,
+ kArm64ScalarHeuristicMaxBodySizeInstr,
+ kArm64ScalarHeuristicMaxBodySizeBlocks);
+ }
+
uint32_t GetSIMDUnrollingFactor(HBasicBlock* block,
int64_t trip_count,
uint32_t max_peel,
@@ -126,8 +156,8 @@
}
};
-ArchDefaultLoopHelper* ArchDefaultLoopHelper::Create(InstructionSet isa,
- ArenaAllocator* allocator) {
+ArchNoOptsLoopHelper* ArchNoOptsLoopHelper::Create(InstructionSet isa,
+ ArenaAllocator* allocator) {
switch (isa) {
case InstructionSet::kArm64: {
return new (allocator) Arm64LoopHelper;
diff --git a/compiler/optimizing/loop_analysis.h b/compiler/optimizing/loop_analysis.h
index ece9858..c09d3ff 100644
--- a/compiler/optimizing/loop_analysis.h
+++ b/compiler/optimizing/loop_analysis.h
@@ -35,6 +35,7 @@
exits_num_(0),
has_instructions_preventing_scalar_peeling_(false),
has_instructions_preventing_scalar_unrolling_(false),
+ has_long_type_instructions_(false),
loop_info_(loop_info) {}
size_t GetNumberOfBasicBlocks() const { return bb_num_; }
@@ -49,6 +50,10 @@
return has_instructions_preventing_scalar_unrolling_;
}
+ bool HasLongTypeInstructions() const {
+ return has_long_type_instructions_;
+ }
+
const HLoopInformation* GetLoopInfo() const { return loop_info_; }
private:
@@ -62,6 +67,9 @@
bool has_instructions_preventing_scalar_peeling_;
// Whether the loop has instructions which make scalar loop unrolling non-beneficial.
bool has_instructions_preventing_scalar_unrolling_;
+ // Whether the loop has instructions of primitive long type; unrolling these loop will
+ // likely introduce spill/fills on 32-bit targets.
+ bool has_long_type_instructions_;
// Corresponding HLoopInformation.
const HLoopInformation* loop_info_;
@@ -117,22 +125,21 @@
// To support peeling/unrolling for a new architecture one needs to create new helper class,
// inherit it from this and add implementation for the following methods.
//
-class ArchDefaultLoopHelper : public ArenaObject<kArenaAllocOptimization> {
+class ArchNoOptsLoopHelper : public ArenaObject<kArenaAllocOptimization> {
public:
- virtual ~ArchDefaultLoopHelper() {}
+ virtual ~ArchNoOptsLoopHelper() {}
// Creates an instance of specialised helper for the target or default helper if the target
// doesn't support loop peeling and unrolling.
- static ArchDefaultLoopHelper* Create(InstructionSet isa, ArenaAllocator* allocator);
+ static ArchNoOptsLoopHelper* Create(InstructionSet isa, ArenaAllocator* allocator);
- // Returns whether the loop is too big for loop peeling/unrolling by checking its total number of
- // basic blocks and instructions.
+ // Returns whether the loop is not beneficial for loop peeling/unrolling.
//
- // If the loop body has too many instructions then peeling/unrolling optimization will not bring
- // any noticeable performance improvement however will increase the code size.
+ // For example, if the loop body has too many instructions then peeling/unrolling optimization
+ // will not bring any noticeable performance improvement however will increase the code size.
//
// Returns 'true' by default, should be overridden by particular target loop helper.
- virtual bool IsLoopTooBigForScalarPeelingUnrolling(
+ virtual bool IsLoopNonBeneficialForScalarOpts(
LoopAnalysisInfo* loop_analysis_info ATTRIBUTE_UNUSED) const { return true; }
// Returns optimal scalar unrolling factor for the loop.
diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
index 1ce3524..eda6bd1 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -33,9 +33,6 @@
// Enables vectorization (SIMDization) in the loop optimizer.
static constexpr bool kEnableVectorization = true;
-// Enables scalar loop unrolling in the loop optimizer.
-static constexpr bool kEnableScalarPeelingUnrolling = false;
-
//
// Static helpers.
//
@@ -457,7 +454,7 @@
vector_header_(nullptr),
vector_body_(nullptr),
vector_index_(nullptr),
- arch_loop_helper_(ArchDefaultLoopHelper::Create(compiler_driver_ != nullptr
+ arch_loop_helper_(ArchNoOptsLoopHelper::Create(compiler_driver_ != nullptr
? compiler_driver_->GetInstructionSet()
: InstructionSet::kNone,
global_allocator_)) {
@@ -761,7 +758,7 @@
bool HLoopOptimization::TryUnrollingForBranchPenaltyReduction(LoopNode* node) {
// Don't run peeling/unrolling if compiler_driver_ is nullptr (i.e., running under tests)
// as InstructionSet is needed.
- if (!kEnableScalarPeelingUnrolling || compiler_driver_ == nullptr) {
+ if (compiler_driver_ == nullptr) {
return false;
}
@@ -781,9 +778,9 @@
LoopAnalysis::CalculateLoopBasicProperties(loop_info, &loop_analysis_info);
// Check "IsLoopClonable" last as it can be time-consuming.
- if (arch_loop_helper_->IsLoopTooBigForScalarPeelingUnrolling(&loop_analysis_info) ||
+ if (loop_analysis_info.HasInstructionsPreventingScalarUnrolling() ||
+ arch_loop_helper_->IsLoopNonBeneficialForScalarOpts(&loop_analysis_info) ||
(loop_analysis_info.GetNumberOfExits() > 1) ||
- loop_analysis_info.HasInstructionsPreventingScalarUnrolling() ||
!PeelUnrollHelper::IsLoopClonable(loop_info)) {
return false;
}
@@ -807,7 +804,7 @@
bool HLoopOptimization::TryPeelingForLoopInvariantExitsElimination(LoopNode* node) {
// Don't run peeling/unrolling if compiler_driver_ is nullptr (i.e., running under tests)
// as InstructionSet is needed.
- if (!kEnableScalarPeelingUnrolling || compiler_driver_ == nullptr) {
+ if (compiler_driver_ == nullptr) {
return false;
}
@@ -821,8 +818,8 @@
LoopAnalysis::CalculateLoopBasicProperties(loop_info, &loop_analysis_info);
// Check "IsLoopClonable" last as it can be time-consuming.
- if (arch_loop_helper_->IsLoopTooBigForScalarPeelingUnrolling(&loop_analysis_info) ||
- loop_analysis_info.HasInstructionsPreventingScalarPeeling() ||
+ if (loop_analysis_info.HasInstructionsPreventingScalarPeeling() ||
+ arch_loop_helper_->IsLoopNonBeneficialForScalarOpts(&loop_analysis_info) ||
!LoopAnalysis::HasLoopAtLeastOneInvariantExit(loop_info) ||
!PeelUnrollHelper::IsLoopClonable(loop_info)) {
return false;
diff --git a/compiler/optimizing/loop_optimization.h b/compiler/optimizing/loop_optimization.h
index 7807da1..191a93d 100644
--- a/compiler/optimizing/loop_optimization.h
+++ b/compiler/optimizing/loop_optimization.h
@@ -28,7 +28,7 @@
namespace art {
class CompilerDriver;
-class ArchDefaultLoopHelper;
+class ArchNoOptsLoopHelper;
/**
* Loop optimizations. Builds a loop hierarchy and applies optimizations to
@@ -308,7 +308,7 @@
HInstruction* vector_index_; // normalized index of the new loop
// Helper for target-specific behaviour for loop optimizations.
- ArchDefaultLoopHelper* arch_loop_helper_;
+ ArchNoOptsLoopHelper* arch_loop_helper_;
friend class LoopOptimizationTest;
diff --git a/test/482-checker-loop-back-edge-use/src/Main.java b/test/482-checker-loop-back-edge-use/src/Main.java
index 4782340..8311d8c 100644
--- a/test/482-checker-loop-back-edge-use/src/Main.java
+++ b/test/482-checker-loop-back-edge-use/src/Main.java
@@ -18,26 +18,28 @@
public class Main {
/// CHECK-START: void Main.loop1(boolean) liveness (after)
- /// CHECK: <<Arg:z\d+>> ParameterValue liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgLoopUse:\d+>>)} uses:[<<ArgUse:\d+>>,<<ArgLoopUse>>]
- /// CHECK: If [<<Arg>>] liveness:<<IfLiv:\d+>>
- /// CHECK: Goto liveness:<<GotoLiv:\d+>>
- /// CHECK: Exit
+ /// CHECK-DAG: <<Arg:z\d+>> ParameterValue liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgUse:\d+>>)} uses:[<<ArgUse>>]
+ /// CHECK-DAG: If [<<Arg>>] liveness:<<IfLiv:\d+>> loop:none
+ /// CHECK-DAG: Goto loop:B{{\d+}}
+ /// CHECK-DAG: Exit
/// CHECK-EVAL: <<IfLiv>> + 1 == <<ArgUse>>
- /// CHECK-EVAL: <<GotoLiv>> + 2 == <<ArgLoopUse>>
+ //
+ // Loop invariant exit check is hoisted from the loop by peeling.
public static void loop1(boolean incoming) {
while (incoming) {}
}
/// CHECK-START: void Main.loop2(boolean) liveness (after)
- /// CHECK: <<Arg:z\d+>> ParameterValue liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgLoopUse2:\d+>>)} uses:[<<ArgUse:\d+>>,<<ArgLoopUse1:\d+>>,<<ArgLoopUse2>>]
- /// CHECK: If [<<Arg>>] liveness:<<IfLiv:\d+>>
- /// CHECK: Goto liveness:<<GotoLiv1:\d+>>
- /// CHECK: Goto liveness:<<GotoLiv2:\d+>>
+ /// CHECK-DAG: <<Arg:z\d+>> ParameterValue liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgLoopUse:\d+>>)} uses:[<<ArgUse:\d+>>,<<ArgLoopUse>>]
+ /// CHECK-DAG: If [<<Arg>>] liveness:<<IfLiv:\d+>> loop:<<Loop1:B\d+>>
+ /// CHECK-DAG: Goto liveness:<<GotoLiv1:\d+>> loop:<<Loop1>>
+ /// CHECK-DAG: Goto liveness:<<GotoLiv2:\d+>> loop:<<Loop2:B\d+>>
/// CHECK-EVAL: <<IfLiv>> + 1 == <<ArgUse>>
/// CHECK-EVAL: <<GotoLiv1>> < <<GotoLiv2>>
- /// CHECK-EVAL: <<GotoLiv1>> + 2 == <<ArgLoopUse1>>
- /// CHECK-EVAL: <<GotoLiv2>> + 2 == <<ArgLoopUse2>>
+ /// CHECK-EVAL: <<GotoLiv1>> + 2 == <<ArgLoopUse>>
+ //
+ // Loop invariant exit check is hoisted from the loop by peeling.
public static void loop2(boolean incoming) {
// Add some code at entry to avoid having the entry block be a pre header.
@@ -122,17 +124,18 @@
}
/// CHECK-START: void Main.loop7(boolean) liveness (after)
- /// CHECK: <<Arg:z\d+>> ParameterValue liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgLoopUse2:\d+>>)} uses:[<<ArgUse1:\d+>>,<<ArgUse2:\d+>>,<<ArgLoopUse1:\d+>>,<<ArgLoopUse2>>]
- /// CHECK: InvokeVirtual [{{l\d+}},<<Arg>>] method_name:java.io.PrintStream.println liveness:<<InvokeLiv:\d+>>
- /// CHECK: If [<<Arg>>] liveness:<<IfLiv:\d+>>
- /// CHECK: Goto liveness:<<GotoLiv1:\d+>>
- /// CHECK: Goto liveness:<<GotoLiv2:\d+>>
- /// CHECK: Exit
+ /// CHECK-DAG: <<Arg:z\d+>> ParameterValue liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgLoopUse:\d+>>)} uses:[<<ArgUse1:\d+>>,<<ArgUse2:\d+>>,<<ArgLoopUse>>]
+ /// CHECK-DAG: InvokeVirtual [{{l\d+}},<<Arg>>] method_name:java.io.PrintStream.println liveness:<<InvokeLiv:\d+>>
+ /// CHECK-DAG: If [<<Arg>>] liveness:<<IfLiv:\d+>> loop:<<Loop1:B\d+>>
+ /// CHECK-DAG: Goto liveness:<<GotoLiv1:\d+>> loop:<<Loop1>>
+ /// CHECK-DAG: Goto liveness:<<GotoLiv2:\d+>> loop:<<Loop2:B\d+>>
+ /// CHECK-DAG: Exit
/// CHECK-EVAL: <<InvokeLiv>> == <<ArgUse1>>
/// CHECK-EVAL: <<IfLiv>> + 1 == <<ArgUse2>>
/// CHECK-EVAL: <<GotoLiv1>> < <<GotoLiv2>>
- /// CHECK-EVAL: <<GotoLiv1>> + 2 == <<ArgLoopUse1>>
- /// CHECK-EVAL: <<GotoLiv2>> + 2 == <<ArgLoopUse2>>
+ /// CHECK-EVAL: <<GotoLiv1>> + 2 == <<ArgLoopUse>>
+ //
+ // Loop invariant exit check is hoisted from the loop by peeling.
public static void loop7(boolean incoming) {
// 'incoming' must have a use at both back edges.
@@ -144,15 +147,16 @@
}
/// CHECK-START: void Main.loop8() liveness (after)
- /// CHECK: <<Arg:z\d+>> StaticFieldGet liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgLoopUse2:\d+>>)} uses:[<<ArgUse:\d+>>,<<ArgLoopUse1:\d+>>,<<ArgLoopUse2>>]
- /// CHECK: If [<<Arg>>] liveness:<<IfLiv:\d+>>
- /// CHECK: Goto liveness:<<GotoLiv1:\d+>>
- /// CHECK: Goto liveness:<<GotoLiv2:\d+>>
- /// CHECK: Exit
+ /// CHECK-DAG: <<Arg:z\d+>> StaticFieldGet liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgLoopUse:\d+>>)} uses:[<<ArgUse:\d+>>,<<ArgLoopUse>>]
+ /// CHECK-DAG: If [<<Arg>>] liveness:<<IfLiv:\d+>> loop:<<Loop1:B\d+>>
+ /// CHECK-DAG: Goto liveness:<<GotoLiv1:\d+>> loop:<<Loop1>>
+ /// CHECK-DAG: Goto liveness:<<GotoLiv2:\d+>> loop:<<Loop2:B\d+>>
+ /// CHECK-DAG: Exit
/// CHECK-EVAL: <<IfLiv>> + 1 == <<ArgUse>>
/// CHECK-EVAL: <<GotoLiv1>> < <<GotoLiv2>>
- /// CHECK-EVAL: <<GotoLiv1>> + 2 == <<ArgLoopUse1>>
- /// CHECK-EVAL: <<GotoLiv2>> + 2 == <<ArgLoopUse2>>
+ /// CHECK-EVAL: <<GotoLiv1>> + 2 == <<ArgLoopUse>>
+ //
+ // Loop invariant exit check is hoisted from the loop by peeling.
public static void loop8() {
// 'incoming' must have a use at both back edges.
@@ -171,14 +175,15 @@
}
/// CHECK-START: void Main.loop9() liveness (after)
- /// CHECK: <<Arg:z\d+>> StaticFieldGet liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgLoopUse:\d+>>)} uses:[<<ArgUse:\d+>>,<<ArgLoopUse>>]
- /// CHECK: If [<<Arg>>] liveness:<<IfLiv:\d+>>
- /// CHECK: Goto liveness:<<GotoLiv1:\d+>>
- /// CHECK-DAG: Goto liveness:<<GotoLiv2:\d+>>
+ /// CHECK-DAG: <<Arg:z\d+>> StaticFieldGet liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgUse:\d+>>)} uses:[<<ArgUse>>]
+ /// CHECK-DAG: If [<<Arg>>] liveness:<<IfLiv:\d+>> loop:<<Loop1:B\d+>>
+ /// CHECK-DAG: Goto liveness:<<GotoLiv1:\d+>> loop:<<Loop1>>
+ /// CHECK-DAG: Goto liveness:<<GotoLiv2:\d+>> loop:<<Loop2:B\d+>>
/// CHECK-DAG: Exit
/// CHECK-EVAL: <<IfLiv>> + 1 == <<ArgUse>>
/// CHECK-EVAL: <<GotoLiv1>> < <<GotoLiv2>>
- /// CHECK-EVAL: <<GotoLiv1>> + 2 == <<ArgLoopUse>>
+ //
+ // Loop invariant exit check is hoisted from the loop by peeling.
public static void loop9() {
// Add some code at entry to avoid having the entry block be a pre header.
diff --git a/test/530-checker-peel-unroll/expected.txt b/test/530-checker-peel-unroll/expected.txt
new file mode 100644
index 0000000..b0aad4d
--- /dev/null
+++ b/test/530-checker-peel-unroll/expected.txt
@@ -0,0 +1 @@
+passed
diff --git a/test/530-checker-peel-unroll/info.txt b/test/530-checker-peel-unroll/info.txt
new file mode 100644
index 0000000..0e10b36
--- /dev/null
+++ b/test/530-checker-peel-unroll/info.txt
@@ -0,0 +1 @@
+Test on loop optimizations, peeling and unrolling.
diff --git a/test/530-checker-peel-unroll/src/Main.java b/test/530-checker-peel-unroll/src/Main.java
new file mode 100644
index 0000000..2051b47
--- /dev/null
+++ b/test/530-checker-peel-unroll/src/Main.java
@@ -0,0 +1,822 @@
+/*
+ * Copyright (C) 2018 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.
+ */
+
+//
+// Test loop optimizations, in particular scalar loop peeling and unrolling.
+public class Main {
+
+ static final int LENGTH = 4 * 1024;
+ int[] a = new int[LENGTH];
+ int[] b = new int[LENGTH];
+
+ private static final int LENGTH_A = LENGTH;
+ private static final int LENGTH_B = 16;
+ private static final int RESULT_POS = 4;
+
+ double[][] mA;
+ double[][] mB;
+ double[][] mC;
+
+ public Main() {
+ mA = new double[LENGTH_A][];
+ mB = new double[LENGTH_B][];
+ mC = new double[LENGTH_B][];
+ for (int i = 0; i < LENGTH_A; i++) {
+ mA[i] = new double[LENGTH_B];
+ }
+
+ for (int i = 0; i < LENGTH_B; i++) {
+ mB[i] = new double[LENGTH_A];
+ mC[i] = new double[LENGTH_B];
+ }
+ }
+
+ private static final void initMatrix(double[][] m) {
+ for (int i = 0; i < m.length; i++) {
+ for (int j = 0; j < m[i].length; j++) {
+ m[i][j] = (double) (i * LENGTH / (j + 1));
+ }
+ }
+ }
+
+ private static final void initIntArray(int[] a) {
+ for (int i = 0; i < LENGTH; i++) {
+ a[i] = i % 4;
+ }
+ }
+
+ /// CHECK-START: void Main.unrollingLoadStoreElimination(int[]) loop_optimization (before)
+ /// CHECK-DAG: <<Array:l\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4094 loop:none
+ /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi>>,<<Limit>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Get0:i\d+>> ArrayGet [<<Array>>,<<Phi>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<IndAdd:i\d+>> Add [<<Phi>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [<<Array>>,<<IndAdd>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Add:i\d+>> Add [<<Get0>>,<<Get1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet [<<Array>>,<<Phi>>,<<Add>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-NOT: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-NOT: ArraySet loop:<<Loop>> outer_loop:none
+
+ /// CHECK-START: void Main.unrollingLoadStoreElimination(int[]) loop_optimization (after)
+ /// CHECK-DAG: <<Array:l\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4094 loop:none
+ /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi>>,<<Limit>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Get0:i\d+>> ArrayGet [<<Array>>,<<Phi>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<IndAdd:i\d+>> Add [<<Phi>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [<<Array>>,<<IndAdd>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Add:i\d+>> Add [<<Get0>>,<<Get1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet [<<Array>>,<<Phi>>,<<Add>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-DAG: <<CheckA:z\d+>> GreaterThanOrEqual [<<IndAdd>>,<<Limit>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<IfA:v\d+>> If [<<Const0>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Get0A:i\d+>> ArrayGet [<<Array>>,<<IndAdd>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<IndAddA:i\d+>> Add [<<IndAdd>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Get1A:i\d+>> ArrayGet [<<Array>>,<<IndAddA>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<AddA:i\d+>> Add [<<Get0A>>,<<Get1A>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet [<<Array>>,<<IndAdd>>,<<AddA>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-NOT: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-NOT: ArraySet loop:<<Loop>> outer_loop:none
+ private static final void unrollingLoadStoreElimination(int[] a) {
+ for (int i = 0; i < LENGTH - 2; i++) {
+ a[i] += a[i + 1];
+ }
+ }
+
+ /// CHECK-START: void Main.unrollingWhile(int[]) loop_optimization (before)
+ /// CHECK-DAG: <<Array:l\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Const2:i\d+>> IntConstant 2 loop:none
+ /// CHECK-DAG: <<Const128:i\d+>> IntConstant 128 loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4094 loop:none
+ /// CHECK-DAG: <<PhiI:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<PhiS:i\d+>> Phi [<<Const128>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<AddI:i\d+>> Add [<<PhiI>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<PhiI>>,<<Limit>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Rem:i\d+>> Rem [<<AddI>>,<<Const2>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<NE:z\d+>> NotEqual [<<Rem>>,<<Const0>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: If [<<NE>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<AddS:i\d+>> Add [<<PhiS>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Phi [<<PhiS>>,<<AddS>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-NOT: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-NOT: ArraySet loop:<<Loop>> outer_loop:none
+
+ /// CHECK-START: void Main.unrollingWhile(int[]) loop_optimization (after)
+ /// CHECK-DAG: <<Array:l\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Const2:i\d+>> IntConstant 2 loop:none
+ /// CHECK-DAG: <<Const128:i\d+>> IntConstant 128 loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4094 loop:none
+ /// CHECK-DAG: <<PhiI:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<PhiS:i\d+>> Phi [<<Const128>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<AddI:i\d+>> Add [<<PhiI>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<PhiI>>,<<Limit>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Rem:i\d+>> Rem [<<AddI>>,<<Const2>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<NE:z\d+>> NotEqual [<<Rem>>,<<Const0>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: If [<<NE>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<AddS:i\d+>> Add [<<PhiS>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet [{{l\d+}},{{i\d+}},<<PhiS>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<PhiSM:i\d+>> Phi [<<PhiS>>,<<AddS>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-DAG: <<AddIA:i\d+>> Add [<<AddI>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<CheckA:z\d+>> GreaterThanOrEqual [<<AddI>>,<<Limit>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<IfA:v\d+>> If [<<Const0>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<RemA:i\d+>> Rem [<<AddIA>>,<<Const2>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<NEA:z\d+>> NotEqual [<<RemA>>,<<Const0>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: If [<<NEA>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<AddSA:i\d+>> Add [<<PhiSM>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet [{{l\d+}},{{i\d+}},<<PhiSM>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Phi [<<AddSA>>,<<PhiSM>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-NOT: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-NOT: ArraySet loop:<<Loop>> outer_loop:none
+ private static final void unrollingWhile(int[] a) {
+ int i = 0;
+ int s = 128;
+ while (i++ < LENGTH - 2) {
+ if (i % 2 == 0) {
+ a[i] = s++;
+ }
+ }
+ }
+
+ // Simple check that loop unrolling has happened.
+ //
+ /// CHECK-START: void Main.unrollingSwitch(int[]) loop_optimization (before)
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4096 loop:none
+ /// CHECK-DAG: <<PhiI:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<PhiI>>,<<Limit>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Add [<<PhiI>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-NOT: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-NOT: ArraySet loop:<<Loop>> outer_loop:none
+
+ /// CHECK-START: void Main.unrollingSwitch(int[]) loop_optimization (after)
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4096 loop:none
+ /// CHECK-DAG: <<PhiI:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<PhiI>>,<<Limit>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<AddI:i\d+>> Add [<<PhiI>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-DAG: <<CheckA:z\d+>> GreaterThanOrEqual [<<AddI>>,<<Limit>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<IfA:v\d+>> If [<<Const0>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Add [<<AddI>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-NOT: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-NOT: ArraySet loop:<<Loop>> outer_loop:none
+ private static final void unrollingSwitch(int[] a) {
+ for (int i = 0; i < LENGTH; i++) {
+ switch (i % 3) {
+ case 2:
+ a[i]++;
+ break;
+ default:
+ break;
+ }
+ }
+ }
+
+ // Simple check that loop unrolling has happened.
+ //
+ /// CHECK-START: void Main.unrollingSwapElements(int[]) loop_optimization (before)
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4094 loop:none
+ /// CHECK-DAG: <<PhiI:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<PhiI>>,<<Limit>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Add [<<PhiI>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-NOT: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-NOT: ArraySet loop:<<Loop>> outer_loop:none
+
+ /// CHECK-START: void Main.unrollingSwapElements(int[]) loop_optimization (after)
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4094 loop:none
+ /// CHECK-DAG: <<PhiI:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<PhiI>>,<<Limit>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<AddI:i\d+>> Add [<<PhiI>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-DAG: <<CheckA:z\d+>> GreaterThanOrEqual [<<AddI>>,<<Limit>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<IfA:v\d+>> If [<<Const0>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Add [<<AddI>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-NOT: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-NOT: ArraySet loop:<<Loop>> outer_loop:none
+ private static final void unrollingSwapElements(int[] array) {
+ for (int i = 0; i < LENGTH - 2; i++) {
+ if (array[i] > array[i + 1]) {
+ int temp = array[i + 1];
+ array[i + 1] = array[i];
+ array[i] = temp;
+ }
+ }
+ }
+
+ // Simple check that loop unrolling has happened.
+ //
+ /// CHECK-START: void Main.unrollingRInnerproduct(double[][], double[][], double[][], int, int) loop_optimization (before)
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> IntConstant 16 loop:none
+ /// CHECK-DAG: <<PhiI:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<PhiI>>,<<Limit>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Add [<<PhiI>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-NOT: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-NOT: ArraySet loop:<<Loop>> outer_loop:none
+
+ /// CHECK-START: void Main.unrollingRInnerproduct(double[][], double[][], double[][], int, int) loop_optimization (after)
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> IntConstant 16 loop:none
+ /// CHECK-DAG: <<PhiI:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<PhiI>>,<<Limit>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<AddI:i\d+>> Add [<<PhiI>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-DAG: <<CheckA:z\d+>> GreaterThanOrEqual [<<AddI>>,<<Limit>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<IfA:v\d+>> If [<<Const0>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Add [<<AddI>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-NOT: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-NOT: ArraySet loop:<<Loop>> outer_loop:none
+ private static final void unrollingRInnerproduct(double[][] result,
+ double[][] a,
+ double[][] b,
+ int row,
+ int column) {
+ // computes the inner product of A[row,*] and B[*,column]
+ int i;
+ result[row][column] = 0.0f;
+ for (i = 0; i < LENGTH_B; i++) {
+ result[row][column] = result[row][column] + a[row][i] * b[i][column];
+ }
+ }
+
+ // nested loop
+ // [[[]]]
+
+ /// CHECK-START: void Main.unrollingInTheNest(int[], int[], int) loop_optimization (before)
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> IntConstant 128 loop:none
+ /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop1:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop2:B\d+>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: <<Phi3:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop3:B\d+>> outer_loop:<<Loop2>>
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi3>>,<<Limit>>] loop:<<Loop3>> outer_loop:<<Loop2>>
+ /// CHECK-DAG: If [<<Check>>] loop:<<Loop3>> outer_loop:<<Loop2>>
+ /// CHECK-DAG: ArrayGet loop:<<Loop3>> outer_loop:<<Loop2>>
+ /// CHECK-DAG: ArraySet loop:<<Loop3>> outer_loop:<<Loop2>>
+ /// CHECK-DAG: ArrayGet loop:<<Loop3>> outer_loop:<<Loop2>>
+ /// CHECK-DAG: ArraySet loop:<<Loop3>> outer_loop:<<Loop2>>
+ /// CHECK-DAG: Add [<<Phi3>>,<<Const1>>] loop:<<Loop3>> outer_loop:<<Loop2>>
+ //
+ /// CHECK-NOT: ArrayGet
+ /// CHECK-NOT: ArraySet
+ /// CHECK-NOT: If
+
+ /// CHECK-START: void Main.unrollingInTheNest(int[], int[], int) loop_optimization (after)
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> IntConstant 128 loop:none
+ /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop1:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop2:B\d+>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: <<Phi3:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop3:B\d+>> outer_loop:<<Loop2>>
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi3>>,<<Limit>>] loop:<<Loop3>> outer_loop:<<Loop2>>
+ /// CHECK-DAG: If [<<Check>>] loop:<<Loop3>> outer_loop:<<Loop2>>
+ /// CHECK-DAG: ArrayGet loop:<<Loop3>> outer_loop:<<Loop2>>
+ /// CHECK-DAG: ArraySet loop:<<Loop3>> outer_loop:<<Loop2>>
+ /// CHECK-DAG: ArrayGet loop:<<Loop3>> outer_loop:<<Loop2>>
+ /// CHECK-DAG: ArraySet loop:<<Loop3>> outer_loop:<<Loop2>>
+ /// CHECK-DAG: <<AddI:i\d+>> Add [<<Phi3>>,<<Const1>>] loop:<<Loop3>> outer_loop:<<Loop2>>
+ //
+ /// CHECK-DAG: If [<<Const0>>] loop:<<Loop3>> outer_loop:<<Loop2>>
+ /// CHECK-DAG: ArrayGet loop:<<Loop3>> outer_loop:<<Loop2>>
+ /// CHECK-DAG: ArraySet loop:<<Loop3>> outer_loop:<<Loop2>>
+ /// CHECK-DAG: ArrayGet loop:<<Loop3>> outer_loop:<<Loop2>>
+ /// CHECK-DAG: ArraySet loop:<<Loop3>> outer_loop:<<Loop2>>
+ //
+ /// CHECK-NOT: ArrayGet
+ /// CHECK-NOT: ArraySet
+ /// CHECK-NOT: If
+ private static final void unrollingInTheNest(int[] a, int[] b, int x) {
+ for (int k = 0; k < 16; k++) {
+ for (int j = 0; j < 16; j++) {
+ for (int i = 0; i < 128; i++) {
+ b[x]++;
+ a[i] = a[i] + 1;
+ }
+ }
+ }
+ }
+
+ // nested loop:
+ // [
+ // if [] else []
+ // ]
+
+ /// CHECK-START: void Main.unrollingTwoLoopsInTheNest(int[], int[], int) loop_optimization (before)
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> IntConstant 128 loop:none
+ /// CHECK-DAG: <<XThres:i\d+>> IntConstant 100 loop:none
+ /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop1:B\d+>> outer_loop:none
+ //
+ /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop2:B\d+>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: <<Check2:z\d+>> GreaterThanOrEqual [<<Phi2>>,<<Limit>>] loop:<<Loop2>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: If [<<Check2>>] loop:<<Loop2>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: ArrayGet loop:<<Loop2>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: ArraySet loop:<<Loop2>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: <<AddI2:i\d+>> Add [<<Phi2>>,<<Const1>>] loop:<<Loop2>> outer_loop:<<Loop1>>
+ //
+ /// CHECK-DAG: <<Phi3:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop3:B\d+>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: <<Check3:z\d+>> GreaterThanOrEqual [<<Phi3>>,<<Limit>>] loop:<<Loop3>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: If [<<Check3>>] loop:<<Loop3>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: ArrayGet loop:<<Loop3>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: ArraySet loop:<<Loop3>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: <<AddI3:i\d+>> Add [<<Phi3>>,<<Const1>>] loop:<<Loop3>> outer_loop:<<Loop1>>
+ //
+ /// CHECK-NOT: ArrayGet
+ /// CHECK-NOT: ArraySet
+ /// CHECK-NOT: If
+
+ /// CHECK-START: void Main.unrollingTwoLoopsInTheNest(int[], int[], int) loop_optimization (after)
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> IntConstant 128 loop:none
+ /// CHECK-DAG: <<XThres:i\d+>> IntConstant 100 loop:none
+ /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop1:B\d+>> outer_loop:none
+ //
+ /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop2:B\d+>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: <<Check2:z\d+>> GreaterThanOrEqual [<<Phi2>>,<<Limit>>] loop:<<Loop2>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: If [<<Check2>>] loop:<<Loop2>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: ArrayGet loop:<<Loop2>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: ArraySet loop:<<Loop2>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: <<AddI2:i\d+>> Add [<<Phi2>>,<<Const1>>] loop:<<Loop2>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: If [<<Const0>>] loop:<<Loop2>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: ArrayGet loop:<<Loop2>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: ArraySet loop:<<Loop2>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: Add [<<AddI2>>,<<Const1>>] loop:<<Loop2>> outer_loop:<<Loop1>>
+ //
+ /// CHECK-DAG: <<Phi3:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop3:B\d+>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: <<Check3:z\d+>> GreaterThanOrEqual [<<Phi3>>,<<Limit>>] loop:<<Loop3>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: If [<<Check3>>] loop:<<Loop3>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: ArrayGet loop:<<Loop3>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: ArraySet loop:<<Loop3>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: <<AddI3:i\d+>> Add [<<Phi3>>,<<Const1>>] loop:<<Loop3>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: If [<<Const0>>] loop:<<Loop3>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: ArrayGet loop:<<Loop3>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: ArraySet loop:<<Loop3>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: Add [<<AddI3>>,<<Const1>>] loop:<<Loop3>> outer_loop:<<Loop1>>
+ //
+ /// CHECK-NOT: ArrayGet
+ /// CHECK-NOT: ArraySet
+ /// CHECK-NOT: If
+ private static final void unrollingTwoLoopsInTheNest(int[] a, int[] b, int x) {
+ for (int k = 0; k < 128; k++) {
+ if (x > 100) {
+ for (int j = 0; j < 128; j++) {
+ a[x]++;
+ }
+ } else {
+ for (int i = 0; i < 128; i++) {
+ b[x]++;
+ }
+ }
+ }
+ }
+
+ /// CHECK-START: void Main.noUnrollingOddTripCount(int[]) loop_optimization (before)
+ /// CHECK-DAG: <<Array:l\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4095 loop:none
+ /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi>>,<<Limit>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Get0:i\d+>> ArrayGet [<<Array>>,<<Phi>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<IndAdd:i\d+>> Add [<<Phi>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [<<Array>>,<<IndAdd>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Add:i\d+>> Add [<<Get0>>,<<Get1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet [<<Array>>,<<Phi>>,<<Add>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-NOT: Phi
+ /// CHECK-NOT: If
+ /// CHECK-NOT: ArrayGet
+ /// CHECK-NOT: ArraySet
+
+ /// CHECK-START: void Main.noUnrollingOddTripCount(int[]) loop_optimization (after)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: If loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-NOT: Phi
+ /// CHECK-NOT: If
+ /// CHECK-NOT: ArrayGet
+ /// CHECK-NOT: ArraySet
+ private static final void noUnrollingOddTripCount(int[] a) {
+ for (int i = 0; i < LENGTH - 1; i++) {
+ a[i] += a[i + 1];
+ }
+ }
+
+ /// CHECK-START: void Main.noUnrollingNotKnownTripCount(int[], int) loop_optimization (before)
+ /// CHECK-DAG: <<Array:l\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi>>,<<Limit>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Get0:i\d+>> ArrayGet [<<Array>>,<<Phi>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<IndAdd:i\d+>> Add [<<Phi>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [<<Array>>,<<IndAdd>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Add:i\d+>> Add [<<Get0>>,<<Get1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet [<<Array>>,<<Phi>>,<<Add>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-NOT: Phi
+ /// CHECK-NOT: ArrayGet
+ /// CHECK-NOT: ArraySet
+
+ /// CHECK-START: void Main.noUnrollingNotKnownTripCount(int[], int) loop_optimization (after)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: If loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-NOT: Phi
+ /// CHECK-NOT: ArrayGet
+ /// CHECK-NOT: ArraySet
+ private static final void noUnrollingNotKnownTripCount(int[] a, int n) {
+ for (int i = 0; i < n; i++) {
+ a[i] += a[i + 1];
+ }
+ }
+
+ /// CHECK-START: void Main.peelingSimple(int[], boolean) loop_optimization (before)
+ /// CHECK-DAG: <<Param:z\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4096 loop:none
+ /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi>>,<<Limit>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: If [<<Check>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: If [<<Param>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<IndAdd:i\d+>> Add [<<Phi>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-NOT: If
+ /// CHECK-NOT: ArraySet
+
+ /// CHECK-START: void Main.peelingSimple(int[], boolean) loop_optimization (after)
+ /// CHECK-DAG: <<Param:z\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4096 loop:none
+ /// CHECK-DAG: <<CheckA:z\d+>> GreaterThanOrEqual [<<Const0>>,<<Limit>>] loop:none
+ /// CHECK-DAG: If [<<CheckA>>] loop:none
+ /// CHECK-DAG: If [<<Param>>] loop:none
+ /// CHECK-DAG: ArrayGet loop:none
+ /// CHECK-DAG: ArraySet loop:none
+ /// CHECK-DAG: <<IndAddA:i\d+>> Add [<<Const0>>,<<Const1>>] loop:none
+ /// CHECK-DAG: <<Phi:i\d+>> Phi [<<IndAddA>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi>>,<<Limit>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: If [<<Check>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: If [<<Const0>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<IndAdd:i\d+>> Add [<<Phi>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-NOT: If
+ /// CHECK-NOT: ArraySet
+
+ /// CHECK-START: void Main.peelingSimple(int[], boolean) dead_code_elimination$final (after)
+ /// CHECK-DAG: <<Param:z\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4096 loop:none
+ /// CHECK-DAG: If [<<Param>>] loop:none
+ /// CHECK-DAG: ArrayGet loop:none
+ /// CHECK-DAG: ArraySet loop:none
+ /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Const1>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi>>,<<Limit>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: If [<<Check>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<IndAdd:i\d+>> Add [<<Phi>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-NOT: GreaterThanOrEqual
+ /// CHECK-NOT: If
+ /// CHECK-NOT: ArrayGet
+ /// CHECK-NOT: ArraySet
+ private static final void peelingSimple(int[] a, boolean f) {
+ for (int i = 0; i < LENGTH; i++) {
+ if (f) {
+ break;
+ }
+ a[i] += 1;
+ }
+ }
+
+ // Often used idiom that, when not hoisted, prevents BCE and vectorization.
+ //
+ /// CHECK-START: void Main.peelingAddInts(int[]) loop_optimization (before)
+ /// CHECK-DAG: <<Param:l\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<ConstNull:l\d+>> NullConstant loop:none
+ /// CHECK-DAG: <<Eq:z\d+>> Equal [<<Param>>,<<ConstNull>>] loop:none
+ /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: If [<<Eq>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: If [<<Check>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+
+ /// CHECK-START: void Main.peelingAddInts(int[]) dead_code_elimination$final (after)
+ /// CHECK-DAG: <<Param:l\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<ConstNull:l\d+>> NullConstant loop:none
+ /// CHECK-DAG: <<Eq:z\d+>> Equal [<<Param>>,<<ConstNull>>] loop:none
+ /// CHECK-DAG: If [<<Eq>>] loop:none
+ /// CHECK-DAG: ArraySet loop:none
+ /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: If [<<Check>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-NOT: If [<<Eq>>] loop:<<Loop>> outer_loop:none
+ private static final void peelingAddInts(int[] a) {
+ for (int i = 0; a != null && i < a.length; i++) {
+ a[i] += 1;
+ }
+ }
+
+ /// CHECK-START: void Main.peelingBreakFromNest(int[], boolean) loop_optimization (before)
+ /// CHECK-DAG: <<Param:z\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4096 loop:none
+ /// CHECK-DAG: <<Phi0:i\d+>> Phi [<<Const1>>,{{i\d+}}] loop:<<Loop0:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop1:B\d+>> outer_loop:<<Loop0>>
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi1>>,<<Limit>>] loop:<<Loop1>> outer_loop:<<Loop0>>
+ /// CHECK-DAG: If [<<Check>>] loop:<<Loop1>> outer_loop:<<Loop0>>
+ /// CHECK-DAG: If [<<Param>>] loop:<<Loop1>> outer_loop:<<Loop0>>
+ /// CHECK-DAG: ArrayGet loop:<<Loop1>> outer_loop:<<Loop0>>
+ /// CHECK-DAG: ArraySet loop:<<Loop1>> outer_loop:<<Loop0>>
+ /// CHECK-DAG: <<IndAdd1:i\d+>> Add [<<Phi1>>,<<Const1>>] loop:<<Loop1>> outer_loop:<<Loop0>>
+ /// CHECK-DAG: <<IndAdd0:i\d+>> Add [<<Phi0>>,<<Const1>>] loop:<<Loop0>> outer_loop:none
+ //
+ /// CHECK-NOT: If
+ /// CHECK-NOT: ArraySet
+
+ /// CHECK-START: void Main.peelingBreakFromNest(int[], boolean) dead_code_elimination$final (after)
+ /// CHECK-DAG: <<Param:z\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4096 loop:none
+ /// CHECK-DAG: <<Phi0:i\d+>> Phi [<<Const1>>,{{i\d+}}] loop:<<Loop0:B\d+>> outer_loop:none
+ /// CHECK-DAG: If [<<Param>>] loop:<<Loop0>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop0>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop0>> outer_loop:none
+ /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Const1>>,{{i\d+}}] loop:<<Loop1:B\d+>> outer_loop:<<Loop0>>
+ /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi1>>,<<Limit>>] loop:<<Loop1>> outer_loop:<<Loop0>>
+ /// CHECK-DAG: If [<<Check>>] loop:<<Loop1>> outer_loop:<<Loop0>>
+ /// CHECK-DAG: ArrayGet loop:<<Loop1>> outer_loop:<<Loop0>>
+ /// CHECK-DAG: ArraySet loop:<<Loop1>> outer_loop:<<Loop0>>
+ /// CHECK-DAG: <<IndAdd1:i\d+>> Add [<<Phi1>>,<<Const1>>] loop:<<Loop1>> outer_loop:<<Loop0>>
+ /// CHECK-DAG: <<IndAdd0:i\d+>> Add [<<Phi0>>,<<Const1>>] loop:<<Loop0>> outer_loop:none
+ //
+ /// CHECK-NOT: If
+ /// CHECK-NOT: ArraySet
+ private static final void peelingBreakFromNest(int[] a, boolean f) {
+ outer:
+ for (int i = 1; i < 32; i++) {
+ for (int j = 0; j < LENGTH; j++) {
+ if (f) {
+ break outer;
+ }
+ a[j] += 1;
+ }
+ }
+ }
+
+ /// CHECK-START: int Main.peelingHoistOneControl(int) loop_optimization (before)
+ /// CHECK-DAG: <<Param:i\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Check:z\d+>> NotEqual [<<Param>>,<<Const0>>] loop:none
+ /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: If [<<Check>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<IndAdd:i\d+>> Add [<<Phi>>,<<Const1>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-NOT: If
+
+ /// CHECK-START: int Main.peelingHoistOneControl(int) dead_code_elimination$final (after)
+ /// CHECK-DAG: <<Param:i\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Check:z\d+>> NotEqual [<<Param>>,<<Const0>>] loop:none
+ /// CHECK-DAG: If [<<Check>>] loop:none
+ /// CHECK-DAG: SuspendCheck loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: Goto loop:<<Loop>> outer_loop:none
+ //
+ // Check that the loop has no instruction except SuspendCheck and Goto (indefinite loop).
+ /// CHECK-NOT: loop:<<Loop>> outer_loop:none
+ /// CHECK-NOT: If
+ /// CHECK-NOT: Phi
+ /// CHECK-NOT: Add
+ private static final int peelingHoistOneControl(int x) {
+ int i = 0;
+ while (true) {
+ if (x == 0)
+ return 1;
+ i++;
+ }
+ }
+
+ /// CHECK-START: int Main.peelingHoistOneControl(int, int) loop_optimization (before)
+ /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: If loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: If loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-START: int Main.peelingHoistOneControl(int, int) dead_code_elimination$final (after)
+ /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: If loop:<<Loop>> outer_loop:none
+ /// CHECK-NOT: If loop:<<Loop>> outer_loop:none
+ private static final int peelingHoistOneControl(int x, int y) {
+ while (true) {
+ if (x == 0)
+ return 1;
+ if (y == 0) // no longer invariant
+ return 2;
+ y--;
+ }
+ }
+
+ /// CHECK-START: int Main.peelingHoistTwoControl(int, int, int) loop_optimization (before)
+ /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: If loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: If loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: If loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-START: int Main.peelingHoistTwoControl(int, int, int) dead_code_elimination$final (after)
+ /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: If loop:<<Loop>> outer_loop:none
+ /// CHECK-NOT: If loop:<<Loop>> outer_loop:none
+ private static final int peelingHoistTwoControl(int x, int y, int z) {
+ while (true) {
+ if (x == 0)
+ return 1;
+ if (y == 0)
+ return 2;
+ if (z == 0) // no longer invariant
+ return 3;
+ z--;
+ }
+ }
+
+ private static void expectEquals(int expected, int result) {
+ if (expected != result) {
+ throw new Error("Expected: " + expected + ", found: " + result);
+ }
+ }
+
+ public void verifyUnrolling() {
+ initIntArray(a);
+ initIntArray(b);
+
+ initMatrix(mA);
+ initMatrix(mB);
+ initMatrix(mC);
+
+ int expected = 174291419;
+ int found = 0;
+
+ unrollingWhile(a);
+ unrollingLoadStoreElimination(a);
+ unrollingSwitch(a);
+ unrollingSwapElements(a);
+ unrollingRInnerproduct(mC, mA, mB, RESULT_POS, RESULT_POS);
+ unrollingInTheNest(a, b, RESULT_POS);
+ unrollingTwoLoopsInTheNest(a, b, RESULT_POS);
+
+ noUnrollingOddTripCount(b);
+ noUnrollingNotKnownTripCount(b, 128);
+
+ for (int i = 0; i < LENGTH; i++) {
+ found += a[i];
+ found += b[i];
+ }
+ found += (int)mC[RESULT_POS][RESULT_POS];
+
+ expectEquals(expected, found);
+ }
+
+ public void verifyPeeling() {
+ expectEquals(1, peelingHoistOneControl(0)); // anything else loops
+ expectEquals(1, peelingHoistOneControl(0, 0));
+ expectEquals(1, peelingHoistOneControl(0, 1));
+ expectEquals(2, peelingHoistOneControl(1, 0));
+ expectEquals(2, peelingHoistOneControl(1, 1));
+ expectEquals(1, peelingHoistTwoControl(0, 0, 0));
+ expectEquals(1, peelingHoistTwoControl(0, 0, 1));
+ expectEquals(1, peelingHoistTwoControl(0, 1, 0));
+ expectEquals(1, peelingHoistTwoControl(0, 1, 1));
+ expectEquals(2, peelingHoistTwoControl(1, 0, 0));
+ expectEquals(2, peelingHoistTwoControl(1, 0, 1));
+ expectEquals(3, peelingHoistTwoControl(1, 1, 0));
+ expectEquals(3, peelingHoistTwoControl(1, 1, 1));
+
+ initIntArray(a);
+ peelingSimple(a, false);
+ peelingSimple(a, true);
+ peelingAddInts(a);
+ peelingAddInts(null); // okay
+ peelingBreakFromNest(a, false);
+ peelingBreakFromNest(a, true);
+
+ int expected = 141312;
+ int found = 0;
+ for (int i = 0; i < a.length; i++) {
+ found += a[i];
+ }
+
+ expectEquals(expected, found);
+ }
+
+ public static void main(String[] args) {
+ Main obj = new Main();
+
+ obj.verifyUnrolling();
+ obj.verifyPeeling();
+
+ System.out.println("passed");
+ }
+}