Merge "Improved subscript and data dependence analysis."
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index c0ec58f..f35aace 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -373,21 +373,23 @@
bool InductionVarRange::IsUnitStride(HInstruction* context,
HInstruction* instruction,
+ HGraph* graph,
/*out*/ HInstruction** offset) const {
HLoopInformation* loop = nullptr;
HInductionVarAnalysis::InductionInfo* info = nullptr;
HInductionVarAnalysis::InductionInfo* trip = nullptr;
if (HasInductionInfo(context, instruction, &loop, &info, &trip)) {
if (info->induction_class == HInductionVarAnalysis::kLinear &&
- info->op_b->operation == HInductionVarAnalysis::kFetch &&
!HInductionVarAnalysis::IsNarrowingLinear(info)) {
int64_t stride_value = 0;
if (IsConstant(info->op_a, kExact, &stride_value) && stride_value == 1) {
int64_t off_value = 0;
- if (IsConstant(info->op_b, kExact, &off_value) && off_value == 0) {
- *offset = nullptr;
- } else {
+ if (IsConstant(info->op_b, kExact, &off_value)) {
+ *offset = graph->GetConstant(info->op_b->type, off_value);
+ } else if (info->op_b->operation == HInductionVarAnalysis::kFetch) {
*offset = info->op_b->fetch;
+ } else {
+ return false;
}
return true;
}
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index a8ee829..ab1772b 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -163,6 +163,7 @@
*/
bool IsUnitStride(HInstruction* context,
HInstruction* instruction,
+ HGraph* graph,
/*out*/ HInstruction** offset) const;
/**
diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc
index d01d314..67d2093 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -770,8 +770,8 @@
EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc));
EXPECT_EQ(1000, tc);
HInstruction* offset = nullptr;
- EXPECT_TRUE(range_.IsUnitStride(phi, phi, &offset));
- EXPECT_TRUE(offset == nullptr);
+ EXPECT_TRUE(range_.IsUnitStride(phi, phi, graph_, &offset));
+ ExpectInt(0, offset);
HInstruction* tce = range_.GenerateTripCount(
loop_header_->GetLoopInformation(), graph_, loop_preheader_);
ASSERT_TRUE(tce != nullptr);
@@ -826,7 +826,7 @@
EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc));
EXPECT_EQ(1000, tc);
HInstruction* offset = nullptr;
- EXPECT_FALSE(range_.IsUnitStride(phi, phi, &offset));
+ EXPECT_FALSE(range_.IsUnitStride(phi, phi, graph_, &offset));
HInstruction* tce = range_.GenerateTripCount(
loop_header_->GetLoopInformation(), graph_, loop_preheader_);
ASSERT_TRUE(tce != nullptr);
@@ -908,8 +908,8 @@
EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc));
EXPECT_EQ(0, tc); // unknown
HInstruction* offset = nullptr;
- EXPECT_TRUE(range_.IsUnitStride(phi, phi, &offset));
- EXPECT_TRUE(offset == nullptr);
+ EXPECT_TRUE(range_.IsUnitStride(phi, phi, graph_, &offset));
+ ExpectInt(0, offset);
HInstruction* tce = range_.GenerateTripCount(
loop_header_->GetLoopInformation(), graph_, loop_preheader_);
ASSERT_TRUE(tce != nullptr);
@@ -994,7 +994,7 @@
EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc));
EXPECT_EQ(0, tc); // unknown
HInstruction* offset = nullptr;
- EXPECT_FALSE(range_.IsUnitStride(phi, phi, &offset));
+ EXPECT_FALSE(range_.IsUnitStride(phi, phi, graph_, &offset));
HInstruction* tce = range_.GenerateTripCount(
loop_header_->GetLoopInformation(), graph_, loop_preheader_);
ASSERT_TRUE(tce != nullptr);
diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
index 32f4002..b61d7b8 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -620,12 +620,15 @@
// Conservatively assume a potential loop-carried data dependence otherwise, avoided by
// generating an explicit a != b disambiguation runtime test on the two references.
if (x != y) {
- // For now, we reject after one test to avoid excessive overhead.
- if (vector_runtime_test_a_ != nullptr) {
- return false;
+ // To avoid excessive overhead, we only accept one a != b test.
+ if (vector_runtime_test_a_ == nullptr) {
+ // First test found.
+ vector_runtime_test_a_ = a;
+ vector_runtime_test_b_ = b;
+ } else if ((vector_runtime_test_a_ != a || vector_runtime_test_b_ != b) &&
+ (vector_runtime_test_a_ != b || vector_runtime_test_b_ != a)) {
+ return false; // second test would be needed
}
- vector_runtime_test_a_ = a;
- vector_runtime_test_b_ = b;
}
}
}
@@ -842,7 +845,7 @@
HInstruction* offset = nullptr;
if (TrySetVectorType(type, &restrictions) &&
node->loop_info->IsDefinedOutOfTheLoop(base) &&
- induction_range_.IsUnitStride(instruction, index, &offset) &&
+ induction_range_.IsUnitStride(instruction, index, graph_, &offset) &&
VectorizeUse(node, value, generate_code, type, restrictions)) {
if (generate_code) {
GenerateVecSub(index, offset);
@@ -900,7 +903,7 @@
HInstruction* offset = nullptr;
if (type == instruction->GetType() &&
node->loop_info->IsDefinedOutOfTheLoop(base) &&
- induction_range_.IsUnitStride(instruction, index, &offset)) {
+ induction_range_.IsUnitStride(instruction, index, graph_, &offset)) {
if (generate_code) {
GenerateVecSub(index, offset);
GenerateVecMem(instruction, vector_map_->Get(index), nullptr, offset, type);
@@ -1216,7 +1219,8 @@
void HLoopOptimization::GenerateVecSub(HInstruction* org, HInstruction* offset) {
if (vector_map_->find(org) == vector_map_->end()) {
HInstruction* subscript = vector_index_;
- if (offset != nullptr) {
+ int64_t value = 0;
+ if (!IsInt64AndGet(offset, &value) || value != 0) {
subscript = new (global_allocator_) HAdd(Primitive::kPrimInt, subscript, offset);
if (org->IsPhi()) {
Insert(vector_body_, subscript); // lacks layout placeholder
diff --git a/test/656-checker-simd-opt/src/Main.java b/test/656-checker-simd-opt/src/Main.java
index 0d0885c..794c9b6 100644
--- a/test/656-checker-simd-opt/src/Main.java
+++ b/test/656-checker-simd-opt/src/Main.java
@@ -46,6 +46,37 @@
}
}
+ /// CHECK-START: void Main.stencil(int[], int[], int) loop_optimization (before)
+ /// CHECK-DAG: <<CP1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<CM1:i\d+>> IntConstant -1 loop:none
+ /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Add1:i\d+>> Add [<<Phi>>,<<CM1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [{{l\d+}},<<Add1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Get2:i\d+>> ArrayGet [{{l\d+}},<<Phi>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Add2:i\d+>> Add [<<Get1>>,<<Get2>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Add3:i\d+>> Add [<<Phi>>,<<CP1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Get3:i\d+>> ArrayGet [{{l\d+}},<<Add3>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Add4:i\d+>> Add [<<Add2>>,<<Get3>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet [{{l\d+}},<<Phi>>,<<Add4>>] loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-START-ARM64: void Main.stencil(int[], int[], int) loop_optimization (after)
+ /// CHECK-DAG: <<CP1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<CP2:i\d+>> IntConstant 2 loop:none
+ /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Add1:i\d+>> Add [<<Phi>>,<<CP1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Get1:d\d+>> VecLoad [{{l\d+}},<<Phi>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Get2:d\d+>> VecLoad [{{l\d+}},<<Add1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Add2:d\d+>> VecAdd [<<Get1>>,<<Get2>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Add3:i\d+>> Add [<<Phi>>,<<CP2>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Get3:d\d+>> VecLoad [{{l\d+}},<<Add3>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Add4:d\d+>> VecAdd [<<Add2>>,<<Get3>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: VecStore [{{l\d+}},<<Add1>>,<<Add4>>] loop:<<Loop>> outer_loop:none
+ private static void stencil(int[] a, int[] b, int n) {
+ for (int i = 1; i < n - 1; i++) {
+ a[i] = b[i - 1] + b[i] + b[i + 1];
+ }
+ }
+
public static void main(String[] args) {
float[] x = new float[100];
float[] y = new float[100];
@@ -58,6 +89,18 @@
expectEquals(5.0f, x[i]);
expectEquals(2.0f, y[i]);
}
+ int[] a = new int[100];
+ int[] b = new int[100];
+ for (int i = 0; i < 100; i++) {
+ a[i] = 0;
+ b[i] = i;
+ }
+ stencil(a, b, 100);
+ for (int i = 1; i < 99; i++) {
+ int e = i + i + i;
+ expectEquals(e, a[i]);
+ expectEquals(i, b[i]);
+ }
System.out.println("passed");
}