Improve array index analysis in LSA.
This CL improves analysis on array index in load store analysis.
Test: m test-art-host
Test: m test-art-target
Test: m test-art-host-gtest-load_store_analysis_test
Change-Id: Id5e5aa8b396c68e082db95809659494107985fa2
diff --git a/compiler/optimizing/load_store_analysis.cc b/compiler/optimizing/load_store_analysis.cc
index f2ee345..5a8ac59 100644
--- a/compiler/optimizing/load_store_analysis.cc
+++ b/compiler/optimizing/load_store_analysis.cc
@@ -22,6 +22,117 @@
// The number of heap locations for most of the methods stays below this threshold.
constexpr size_t kMaxNumberOfHeapLocations = 32;
+// Check if array indices array[idx1 +/- CONST] and array[idx2] MAY alias.
+static bool BinaryOpAndIndexMayAlias(const HBinaryOperation* idx1, const HInstruction* idx2) {
+ DCHECK(idx1 != nullptr);
+ DCHECK(idx2 != nullptr);
+
+ if (!idx1->IsAdd() && !idx1->IsSub()) {
+ // We currently only support Add and Sub operations.
+ return true;
+ }
+
+ HConstant* cst = idx1->GetConstantRight();
+ if (cst == nullptr || cst->IsArithmeticZero()) {
+ return true;
+ }
+
+ if (idx1->GetLeastConstantLeft() == idx2) {
+ // for example, array[idx1 + 1] and array[idx1]
+ return false;
+ }
+
+ return true;
+}
+
+// Check if Add and Sub MAY alias when used as indices in arrays.
+static bool BinaryOpsMayAlias(const HBinaryOperation* idx1, const HBinaryOperation* idx2) {
+ DCHECK(idx1!= nullptr);
+ DCHECK(idx2 != nullptr);
+
+ HConstant* idx1_cst = idx1->GetConstantRight();
+ HInstruction* idx1_other = idx1->GetLeastConstantLeft();
+ HConstant* idx2_cst = idx2->GetConstantRight();
+ HInstruction* idx2_other = idx2->GetLeastConstantLeft();
+
+ if (idx1_cst == nullptr || idx1_other == nullptr ||
+ idx2_cst == nullptr || idx2_other == nullptr) {
+ // We only analyze patterns like [i +/- CONST].
+ return true;
+ }
+
+ if (idx1_other != idx2_other) {
+ // For example, [j+1] and [k+1] MAY alias.
+ return true;
+ }
+
+ if ((idx1->IsAdd() && idx2->IsAdd()) ||
+ (idx1->IsSub() && idx2->IsSub())) {
+ return idx1_cst->AsIntConstant()->GetValue() == idx2_cst->AsIntConstant()->GetValue();
+ }
+
+ if ((idx1->IsAdd() && idx2->IsSub()) ||
+ (idx1->IsSub() && idx2->IsAdd())) {
+ // [i + CONST1] and [i - CONST2] MAY alias iff CONST1 == -CONST2.
+ // By checking CONST1 == -CONST2, following cases are handled:
+ // - Zero constants case [i+0] and [i-0] is handled.
+ // - Overflow cases are handled, for example:
+ // [i+0x80000000] and [i-0x80000000];
+ // [i+0x10] and [i-0xFFFFFFF0].
+ // - Other cases [i+CONST1] and [i-CONST2] without any overflow is handled.
+ return idx1_cst->AsIntConstant()->GetValue() == -(idx2_cst->AsIntConstant()->GetValue());
+ }
+
+ // All other cases, MAY alias.
+ return true;
+}
+
+// The following array index cases are handled:
+// [i] and [i]
+// [CONST1] and [CONST2]
+// [i] and [i+CONST]
+// [i] and [i-CONST]
+// [i+CONST1] and [i+CONST2]
+// [i-CONST1] and [i-CONST2]
+// [i+CONST1] and [i-CONST2]
+// [i-CONST1] and [i+CONST2]
+// For other complicated cases, we rely on other passes like GVN and simpilfier
+// to optimize these cases before this pass.
+// For example: [i+j+k+10] and [i+k+10+j] shall be optimized to [i7+10] and [i7+10].
+bool HeapLocationCollector::CanArrayIndicesAlias(const HInstruction* idx1,
+ const HInstruction* idx2) const {
+ DCHECK(idx1 != nullptr);
+ DCHECK(idx2 != nullptr);
+
+ if (idx1 == idx2) {
+ // [i] and [i]
+ return true;
+ }
+ if (idx1->IsIntConstant() && idx2->IsIntConstant()) {
+ // [CONST1] and [CONST2]
+ return idx1->AsIntConstant()->GetValue() == idx2->AsIntConstant()->GetValue();
+ }
+
+ if (idx1->IsBinaryOperation() && !BinaryOpAndIndexMayAlias(idx1->AsBinaryOperation(), idx2)) {
+ // [i] and [i+/-CONST]
+ return false;
+ }
+ if (idx2->IsBinaryOperation() && !BinaryOpAndIndexMayAlias(idx2->AsBinaryOperation(), idx1)) {
+ // [i+/-CONST] and [i]
+ return false;
+ }
+
+ if (idx1->IsBinaryOperation() && idx2->IsBinaryOperation()) {
+ // [i+/-CONST1] and [i+/-CONST2]
+ if (!BinaryOpsMayAlias(idx1->AsBinaryOperation(), idx2->AsBinaryOperation())) {
+ return false;
+ }
+ }
+
+ // By default, MAY alias.
+ return true;
+}
+
void LoadStoreAnalysis::Run() {
for (HBasicBlock* block : graph_->GetReversePostOrder()) {
heap_location_collector_.VisitBasicBlock(block);