Fix array location aliasing checks in LSE.

Test: New tests in load_store_elimination_test.
Test: New test in 539-checker-lse.
Test: m test-art-host-gtest
Test: testrunner.py --host --optimizing
Bug: 187487955
Change-Id: Iff66d5406cf1b36c3bebbce1d48117f83bb50553

7 files changed, 415 insertions, 48 deletions

diff --git a/compiler/optimizing/block_namer.cc b/compiler/optimizing/block_namer.cc
index 9936bf1c48..d30448cd23 100644
--- a/compiler/optimizing/block_namer.cc
+++ b/compiler/optimizing/block_namer.cc
@@ -21,7 +21,13 @@
 namespace art {
 
 std::ostream& BlockNamer::PrintName(std::ostream& os, HBasicBlock* blk) const {
-  return os << "B" << blk->GetBlockId();
+  os << "B";
+  if (blk != nullptr) {
+    os << blk->GetBlockId();
+  } else {
+    os << "<none>";
+  }
+  return os;
 }
 
 }  // namespace art
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 5a264b7a70..716fee4d3e 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -656,9 +656,10 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor {
     } else {
       StartAttributeStream("dex_pc") << "n/a";
     }
+    HBasicBlock* block = instruction->GetBlock();
     if (IsPass(kDebugDumpName)) {
       // Include block name for logcat use.
-      StartAttributeStream("block") << namer_.GetName(instruction->GetBlock());
+      StartAttributeStream("block") << namer_.GetName(block);
     }
     instruction->Accept(this);
     if (instruction->HasEnvironment()) {
@@ -710,7 +711,7 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor {
       }
     }
 
-    HLoopInformation* loop_info = instruction->GetBlock()->GetLoopInformation();
+    HLoopInformation* loop_info = (block != nullptr) ? block->GetLoopInformation() : nullptr;
     if (loop_info == nullptr) {
       StartAttributeStream("loop") << "none";
     } else {
diff --git a/compiler/optimizing/load_store_analysis.h b/compiler/optimizing/load_store_analysis.h
index e81572743e..5fda8dfabe 100644
--- a/compiler/optimizing/load_store_analysis.h
+++ b/compiler/optimizing/load_store_analysis.h
@@ -417,20 +417,7 @@ class HeapLocationCollector : public HGraphVisitor {
     }
   }
 
- private:
-  // An allocation cannot alias with a name which already exists at the point
-  // of the allocation, such as a parameter or a load happening before the allocation.
-  bool MayAliasWithPreexistenceChecking(ReferenceInfo* ref_info1, ReferenceInfo* ref_info2) const {
-    if (ref_info1->GetReference()->IsNewInstance() || ref_info1->GetReference()->IsNewArray()) {
-      // Any reference that can alias with the allocation must appear after it in the block/in
-      // the block's successors. In reverse post order, those instructions will be visited after
-      // the allocation.
-      return ref_info2->GetPosition() >= ref_info1->GetPosition();
-    }
-    return true;
-  }
-
-  bool CanReferencesAlias(ReferenceInfo* ref_info1, ReferenceInfo* ref_info2) const {
+  static bool CanReferencesAlias(ReferenceInfo* ref_info1, ReferenceInfo* ref_info2) {
     if (ref_info1 == ref_info2) {
       return true;
     } else if (ref_info1->IsSingleton()) {
@@ -444,6 +431,19 @@ class HeapLocationCollector : public HGraphVisitor {
     return true;
   }
 
+ private:
+  // An allocation cannot alias with a name which already exists at the point
+  // of the allocation, such as a parameter or a load happening before the allocation.
+  static bool MayAliasWithPreexistenceChecking(ReferenceInfo* ref_info1, ReferenceInfo* ref_info2) {
+    if (ref_info1->GetReference()->IsNewInstance() || ref_info1->GetReference()->IsNewArray()) {
+      // Any reference that can alias with the allocation must appear after it in the block/in
+      // the block's successors. In reverse post order, those instructions will be visited after
+      // the allocation.
+      return ref_info2->GetPosition() >= ref_info1->GetPosition();
+    }
+    return true;
+  }
+
   bool CanArrayElementsAlias(const HInstruction* idx1,
                              const size_t vector_length1,
                              const HInstruction* idx2,
diff --git a/compiler/optimizing/load_store_elimination.cc b/compiler/optimizing/load_store_elimination.cc
index 6f8e441545..fe2cdef5c3 100644
--- a/compiler/optimizing/load_store_elimination.cc
+++ b/compiler/optimizing/load_store_elimination.cc
@@ -929,6 +929,8 @@ class LSEVisitor final : private HGraphDelegateVisitor {
     kPartialElimination,
   };
 
+  bool MayAliasOnBackEdge(HBasicBlock* loop_header, size_t idx1, size_t idx2) const;
+
   bool TryReplacingLoopPhiPlaceholderWithDefault(
       PhiPlaceholder phi_placeholder,
       DataType::Type type,
@@ -1848,6 +1850,34 @@ void LSEVisitor::VisitBasicBlock(HBasicBlock* block) {
   HGraphVisitor::VisitBasicBlock(block);
 }
 
+bool LSEVisitor::MayAliasOnBackEdge(HBasicBlock* loop_header, size_t idx1, size_t idx2) const {
+  DCHECK_NE(idx1, idx2);
+  DCHECK(loop_header->IsLoopHeader());
+  if (heap_location_collector_.MayAlias(idx1, idx2)) {
+    return true;
+  }
+  // For array locations with index defined inside the loop, include
+  // all other locations in the array, even those that LSA declares
+  // non-aliasing, such as `a[i]` and `a[i + 1]`, as they may actually
+  // refer to the same locations for different iterations. (LSA's
+  // `ComputeMayAlias()` does not consider different loop iterations.)
+  HeapLocation* loc1 = heap_location_collector_.GetHeapLocation(idx1);
+  HeapLocation* loc2 = heap_location_collector_.GetHeapLocation(idx2);
+  if (loc1->IsArray() &&
+      loc2->IsArray() &&
+      HeapLocationCollector::CanReferencesAlias(loc1->GetReferenceInfo(),
+                                                loc2->GetReferenceInfo())) {
+    HLoopInformation* loop_info = loop_header->GetLoopInformation();
+    if (loop_info->Contains(*loc1->GetIndex()->GetBlock()) ||
+        loop_info->Contains(*loc2->GetIndex()->GetBlock())) {
+      // Consider the locations aliasing. Do not optimize the case where both indexes
+      // are loop invariants defined inside the loop, rely on LICM to pull them out.
+      return true;
+    }
+  }
+  return false;
+}
+
 bool LSEVisitor::TryReplacingLoopPhiPlaceholderWithDefault(
     PhiPlaceholder phi_placeholder,
     DataType::Type type,
@@ -1972,6 +2002,12 @@ bool LSEVisitor::TryReplacingLoopPhiPlaceholderWithSingleInput(
         replacement = value.GetInstruction();
       }
     }
+    // While `TryReplacingLoopPhiPlaceholderWithDefault()` has special treatment
+    // for back-edges, it is not needed here. When looking for a single input
+    // instruction coming from before the loop, the array index must also be
+    // defined before the loop and the aliasing analysis done by LSA is sufficient.
+    // Any writes of a different value with an index that is not loop invariant
+    // would invalidate the heap location in `VisitSetLocation()`.
   }
 
   // Record replacement and report success.
@@ -2033,6 +2069,7 @@ std::optional<LSEVisitor::PhiPlaceholder> LSEVisitor::FindLoopPhisToMaterialize(
       // default values or Phis, i.e. for vector loads, as we can only replace the Phi
       // placeholder with a single instruction defined before the loop.
       if (!can_use_default_or_phi) {
+        DCHECK(index != nullptr);  // Vector operations are array operations.
         if (TryReplacingLoopPhiPlaceholderWithSingleInput(current_phi_placeholder,
                                                           phi_placeholders_to_materialize)) {
           continue;
@@ -2042,11 +2079,26 @@ std::optional<LSEVisitor::PhiPlaceholder> LSEVisitor::FindLoopPhisToMaterialize(
       }
     }
     for (HBasicBlock* predecessor : current_block->GetPredecessors()) {
-      Value value = ReplacementOrValue(heap_values_for_[predecessor->GetBlockId()][idx].value);
+      ScopedArenaVector<ValueRecord>& heap_values = heap_values_for_[predecessor->GetBlockId()];
+      Value value = ReplacementOrValue(heap_values[idx].value);
       if (value.IsUnknown()) {
         // We cannot create a Phi for this loop Phi placeholder.
         return current_phi_placeholder;  // Report the loop Phi placeholder.
       }
+      // For arrays, the location may have been clobbered by writes to other locations
+      // in a loop that LSA does not consider aliasing, such as `a[i]` and `a[i + 1]`.
+      if (current_block->IsLoopHeader() &&
+          predecessor != current_block->GetLoopInformation()->GetPreHeader() &&
+          heap_location_collector_.GetHeapLocation(idx)->GetIndex() != nullptr) {
+        for (size_t i = 0, size = heap_values.size(); i != size; ++i) {
+          if (i != idx &&
+              !heap_values[i].stored_by.IsUnknown() &&
+              MayAliasOnBackEdge(current_block, idx, i)) {
+            // We cannot create a Phi for this loop Phi placeholder.
+            return current_phi_placeholder;
+          }
+        }
+      }
       if (value.NeedsLoopPhi()) {
         // Visit the predecessor Phi placeholder if it's not visited yet.
         if (!phi_placeholders_to_materialize->IsBitSet(PhiPlaceholderIndex(value))) {
@@ -2574,7 +2626,6 @@ void LSEVisitor::SearchPhiPlaceholdersForKeptStores() {
       ScopedArenaVector<ValueRecord>& heap_values = heap_values_for_[predecessor->GetBlockId()];
       // For loop back-edges we must also preserve all stores to locations that
       // may alias with the location `idx`.
-      // TODO: Review whether we need to keep stores to aliased locations from pre-header.
       // TODO: Add tests cases around this.
       bool is_back_edge =
           block->IsLoopHeader() && predecessor != block->GetLoopInformation()->GetPreHeader();
@@ -2582,31 +2633,7 @@ void LSEVisitor::SearchPhiPlaceholdersForKeptStores() {
       size_t end = is_back_edge ? heap_values.size() : idx + 1u;
       for (size_t i = start; i != end; ++i) {
         Value stored_by = heap_values[i].stored_by;
-        auto may_alias = [this, block, idx](size_t i) {
-            DCHECK_NE(i, idx);
-            DCHECK(block->IsLoopHeader());
-            if (heap_location_collector_.MayAlias(i, idx)) {
-              return true;
-            }
-            // For array locations with index defined inside the loop, include
-            // all other locations in the array, even those that LSA declares
-            // non-aliasing, such as `a[i]` and `a[i + 1]`, as they may actually
-            // refer to the same locations for different iterations. (LSA's
-            // `ComputeMayAlias()` does not consider different loop iterations.)
-            HeapLocation* heap_loc = heap_location_collector_.GetHeapLocation(idx);
-            HeapLocation* other_loc = heap_location_collector_.GetHeapLocation(i);
-            if (heap_loc->IsArray() &&
-                other_loc->IsArray() &&
-                heap_loc->GetReferenceInfo() == other_loc->GetReferenceInfo() &&
-                block->GetLoopInformation()->Contains(*heap_loc->GetIndex()->GetBlock())) {
-              // If one location has index defined inside and the other index defined outside
-              // of the loop, LSA considers them aliasing and we take an early return above.
-              DCHECK(block->GetLoopInformation()->Contains(*other_loc->GetIndex()->GetBlock()));
-              return true;
-            }
-            return false;
-        };
-        if (!stored_by.IsUnknown() && (i == idx || may_alias(i))) {
+        if (!stored_by.IsUnknown() && (i == idx || MayAliasOnBackEdge(block, idx, i))) {
           if (stored_by.NeedsPhi()) {
             size_t phi_placeholder_index = PhiPlaceholderIndex(stored_by);
             if (is_partial_kept_merged_unknown) {
diff --git a/compiler/optimizing/load_store_elimination_test.cc b/compiler/optimizing/load_store_elimination_test.cc
index 87ccd1a180..56cc769062 100644
--- a/compiler/optimizing/load_store_elimination_test.cc
+++ b/compiler/optimizing/load_store_elimination_test.cc
@@ -1679,6 +1679,196 @@ TEST_F(LoadStoreEliminationTest, ArrayMergeDefault) {
   EXPECT_INS_REMOVED(alloc_w);
 }
 
+// Regression test for b/187487955.
+// We previusly failed to consider aliasing between an array location
+// with index `idx` defined in the loop (such as a loop Phi) and another
+// array location with index `idx + constant`. This could have led to
+// replacing the load with, for example, the default value 0.
+TEST_F(LoadStoreEliminationTest, ArrayLoopAliasing1) {
+  VariableSizedHandleScope vshs(Thread::Current());
+  CreateGraph(&vshs);
+  AdjacencyListGraph blocks(graph_,
+                            GetAllocator(),
+                            "entry",
+                            "exit",
+                            { { "entry", "preheader" },
+                              { "preheader", "loop" },
+                              { "loop", "body" },
+                              { "body", "loop" },
+                              { "loop", "ret" },
+                              { "ret", "exit" } });
+#define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
+  GET_BLOCK(entry);
+  GET_BLOCK(preheader);
+  GET_BLOCK(loop);
+  GET_BLOCK(body);
+  GET_BLOCK(ret);
+  GET_BLOCK(exit);
+#undef GET_BLOCK
+  HInstruction* n = MakeParam(DataType::Type::kInt32);
+  HInstruction* c0 = graph_->GetIntConstant(0);
+  HInstruction* c1 = graph_->GetIntConstant(1);
+
+  // entry
+  HInstruction* cls = MakeClassLoad();
+  HInstruction* array = new (GetAllocator()) HNewArray(
+      cls, n, /*dex_pc=*/ 0u, DataType::SizeShift(DataType::Type::kInt32));
+  HInstruction* entry_goto = new (GetAllocator()) HGoto();
+  entry->AddInstruction(cls);
+  entry->AddInstruction(array);
+  entry->AddInstruction(entry_goto);
+  ManuallyBuildEnvFor(cls, {});
+  ManuallyBuildEnvFor(array, {});
+
+  HInstruction* preheader_goto = new (GetAllocator()) HGoto();
+  preheader->AddInstruction(preheader_goto);
+
+  // loop
+  HPhi* i_phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
+  HInstruction* loop_suspend_check = new (GetAllocator()) HSuspendCheck();
+  HInstruction* loop_cond = new (GetAllocator()) HLessThan(i_phi, n);
+  HIf* loop_if = new (GetAllocator()) HIf(loop_cond);
+  loop->AddPhi(i_phi);
+  loop->AddInstruction(loop_suspend_check);
+  loop->AddInstruction(loop_cond);
+  loop->AddInstruction(loop_if);
+  CHECK(loop_if->IfTrueSuccessor() == body);
+  ManuallyBuildEnvFor(loop_suspend_check, {});
+
+  // body
+  HInstruction* body_set =
+      new (GetAllocator()) HArraySet(array, i_phi, i_phi, DataType::Type::kInt32, /*dex_pc=*/ 0u);
+  HInstruction* body_add = new (GetAllocator()) HAdd(DataType::Type::kInt32, i_phi, c1);
+  HInstruction* body_goto = new (GetAllocator()) HGoto();
+  body->AddInstruction(body_set);
+  body->AddInstruction(body_add);
+  body->AddInstruction(body_goto);
+
+  // i_phi inputs
+  i_phi->AddInput(c0);
+  i_phi->AddInput(body_add);
+
+  // ret
+  HInstruction* ret_sub = new (GetAllocator()) HSub(DataType::Type::kInt32, i_phi, c1);
+  HInstruction* ret_get =
+      new (GetAllocator()) HArrayGet(array, ret_sub, DataType::Type::kInt32, /*dex_pc=*/ 0);
+  HInstruction* ret_return = new (GetAllocator()) HReturn(ret_get);
+  ret->AddInstruction(ret_sub);
+  ret->AddInstruction(ret_get);
+  ret->AddInstruction(ret_return);
+
+  // exit
+  SetupExit(exit);
+
+  graph_->ClearDominanceInformation();
+  graph_->ClearLoopInformation();
+  PerformLSE();
+
+  EXPECT_INS_RETAINED(cls);
+  EXPECT_INS_RETAINED(array);
+  EXPECT_INS_RETAINED(body_set);
+  EXPECT_INS_RETAINED(ret_get);
+}
+
+// Regression test for b/187487955.
+// Similar to the `ArrayLoopAliasing1` test above but with additional load
+// that marks a loop Phi placeholder as kept which used to trigger a DCHECK().
+// There is also an LSE run-test for this but it relies on BCE eliminating
+// BoundsCheck instructions and adds extra code in loop body to avoid
+// loop unrolling. This gtest does not need to jump through those hoops
+// as we do not unnecessarily run those optimization passes.
+TEST_F(LoadStoreEliminationTest, ArrayLoopAliasing2) {
+  VariableSizedHandleScope vshs(Thread::Current());
+  CreateGraph(&vshs);
+  AdjacencyListGraph blocks(graph_,
+                            GetAllocator(),
+                            "entry",
+                            "exit",
+                            { { "entry", "preheader" },
+                              { "preheader", "loop" },
+                              { "loop", "body" },
+                              { "body", "loop" },
+                              { "loop", "ret" },
+                              { "ret", "exit" } });
+#define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
+  GET_BLOCK(entry);
+  GET_BLOCK(preheader);
+  GET_BLOCK(loop);
+  GET_BLOCK(body);
+  GET_BLOCK(ret);
+  GET_BLOCK(exit);
+#undef GET_BLOCK
+  HInstruction* n = MakeParam(DataType::Type::kInt32);
+  HInstruction* c0 = graph_->GetIntConstant(0);
+  HInstruction* c1 = graph_->GetIntConstant(1);
+
+  // entry
+  HInstruction* cls = MakeClassLoad();
+  HInstruction* array = new (GetAllocator()) HNewArray(
+      cls, n, /*dex_pc=*/ 0u, DataType::SizeShift(DataType::Type::kInt32));
+  HInstruction* entry_goto = new (GetAllocator()) HGoto();
+  entry->AddInstruction(cls);
+  entry->AddInstruction(array);
+  entry->AddInstruction(entry_goto);
+  ManuallyBuildEnvFor(cls, {});
+  ManuallyBuildEnvFor(array, {});
+
+  HInstruction* preheader_goto = new (GetAllocator()) HGoto();
+  preheader->AddInstruction(preheader_goto);
+
+  // loop
+  HPhi* i_phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
+  HInstruction* loop_suspend_check = new (GetAllocator()) HSuspendCheck();
+  HInstruction* loop_cond = new (GetAllocator()) HLessThan(i_phi, n);
+  HIf* loop_if = new (GetAllocator()) HIf(loop_cond);
+  loop->AddPhi(i_phi);
+  loop->AddInstruction(loop_suspend_check);
+  loop->AddInstruction(loop_cond);
+  loop->AddInstruction(loop_if);
+  CHECK(loop_if->IfTrueSuccessor() == body);
+  ManuallyBuildEnvFor(loop_suspend_check, {});
+
+  // body
+  HInstruction* body_set =
+      new (GetAllocator()) HArraySet(array, i_phi, i_phi, DataType::Type::kInt32, /*dex_pc=*/ 0u);
+  HInstruction* body_add = new (GetAllocator()) HAdd(DataType::Type::kInt32, i_phi, c1);
+  HInstruction* body_goto = new (GetAllocator()) HGoto();
+  body->AddInstruction(body_set);
+  body->AddInstruction(body_add);
+  body->AddInstruction(body_goto);
+
+  // i_phi inputs
+  i_phi->AddInput(c0);
+  i_phi->AddInput(body_add);
+
+  // ret
+  HInstruction* ret_sub = new (GetAllocator()) HSub(DataType::Type::kInt32, i_phi, c1);
+  HInstruction* ret_get1 =
+      new (GetAllocator()) HArrayGet(array, ret_sub, DataType::Type::kInt32, /*dex_pc=*/ 0);
+  HInstruction* ret_get2 =
+      new (GetAllocator()) HArrayGet(array, i_phi, DataType::Type::kInt32, /*dex_pc=*/ 0);
+  HInstruction* ret_add = new (GetAllocator()) HAdd(DataType::Type::kInt32, ret_get1, ret_get2);
+  HInstruction* ret_return = new (GetAllocator()) HReturn(ret_add);
+  ret->AddInstruction(ret_sub);
+  ret->AddInstruction(ret_get1);
+  ret->AddInstruction(ret_get2);
+  ret->AddInstruction(ret_add);
+  ret->AddInstruction(ret_return);
+
+  // exit
+  SetupExit(exit);
+
+  graph_->ClearDominanceInformation();
+  graph_->ClearLoopInformation();
+  PerformLSE();
+
+  EXPECT_INS_RETAINED(cls);
+  EXPECT_INS_RETAINED(array);
+  EXPECT_INS_RETAINED(body_set);
+  EXPECT_INS_RETAINED(ret_get1);
+  EXPECT_INS_RETAINED(ret_get2);
+}
+
 // // ENTRY
 // obj = new Obj();
 // // ALL should be kept
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 215fa3e143..17080f0056 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -27,6 +27,7 @@
 #include "base/bit_vector.h"
 #include "base/iteration_range.h"
 #include "base/logging.h"
+#include "base/malloc_arena_pool.h"
 #include "base/scoped_arena_allocator.h"
 #include "base/scoped_arena_containers.h"
 #include "base/stl_util.h"
@@ -1314,14 +1315,25 @@ void HEnvironment::ReplaceInput(HInstruction* replacement, size_t index) {
 }
 
 std::ostream& HInstruction::Dump(std::ostream& os, bool dump_args) {
-  HGraph* graph = GetBlock()->GetGraph();
+  // Note: Handle the case where the instruction has been removed from
+  // the graph to support debugging output for failed gtests.
+  HGraph* graph = (GetBlock() != nullptr) ? GetBlock()->GetGraph() : nullptr;
   HGraphVisualizer::DumpInstruction(&os, graph, this);
   if (dump_args) {
     // Allocate memory from local ScopedArenaAllocator.
-    ScopedArenaAllocator allocator(graph->GetArenaStack());
+    std::optional<MallocArenaPool> local_arena_pool;
+    std::optional<ArenaStack> local_arena_stack;
+    if (UNLIKELY(graph == nullptr)) {
+      local_arena_pool.emplace();
+      local_arena_stack.emplace(&local_arena_pool.value());
+    }
+    ScopedArenaAllocator allocator(
+        graph != nullptr ? graph->GetArenaStack() : &local_arena_stack.value());
     // Instructions that we already visited. We print each instruction only once.
-    ArenaBitVector visited(
-        &allocator, graph->GetCurrentInstructionId(), /* expandable= */ false, kArenaAllocMisc);
+    ArenaBitVector visited(&allocator,
+                           (graph != nullptr) ? graph->GetCurrentInstructionId() : 0u,
+                           /* expandable= */ (graph == nullptr),
+                           kArenaAllocMisc);
     visited.ClearAllBits();
     visited.SetBit(GetId());
     // Keep a queue of instructions with their indentations.
diff --git a/test/530-checker-lse/src/Main.java b/test/530-checker-lse/src/Main.java
index 23e1d53e98..35f1dc2ee4 100644
--- a/test/530-checker-lse/src/Main.java
+++ b/test/530-checker-lse/src/Main.java
@@ -3455,6 +3455,134 @@ public class Main {
     return sum;
   }
 
+  /// CHECK-START: int Main.testLoop36(int) load_store_elimination (before)
+  /// CHECK-DAG:                 ArraySet
+  /// CHECK-DAG:                 Deoptimize
+  /// CHECK-DAG:                 ArrayGet
+  /// CHECK-DAG:                 ArrayGet
+  /// CHECK-DAG:                 ArrayGet
+  /// CHECK-DAG:                 ArrayGet
+
+  /// CHECK-START: int Main.testLoop36(int) load_store_elimination (before)
+  /// CHECK-NOT:                 BoundsCheck
+
+  /// CHECK-START: int Main.testLoop36(int) load_store_elimination (after)
+  /// CHECK-DAG:                 ArraySet
+  /// CHECK-DAG:                 Deoptimize
+  /// CHECK-DAG:                 ArrayGet
+  /// CHECK-DAG:                 ArrayGet
+  /// CHECK-DAG:                 ArrayGet
+  /// CHECK-DAG:                 ArrayGet
+
+  // Regression test for b/187487955.
+  // We previously failed a DCHECK() during the search for kept stores when
+  // we encountered two array locations for the same array and considered
+  // non-aliasing by LSA when only one of the array locations had index
+  // defined inside the loop. Note that this situation requires that BCE
+  // eliminates BoundsCheck instructions, otherwise LSA considers those
+  // locations aliasing.
+  private static int testLoop36(int n) {
+    int[] a = new int[n];
+    int zero = 0;
+    int i = 0;
+    for (; i < n; ++i) {
+      a[i] = i;
+      // Extra instructions to avoid loop unrolling.
+      zero = (((zero ^ 1) + 2) ^ 1) - 2;
+      zero = (((zero ^ 4) + 8) ^ 4) - 8;
+    }
+    // Use 4 loads with consecutive fixed offsets from the loop Phi for `i`.
+    // BCE shall replace BoundsChecks with Deoptimize, so that indexes here are
+    // the Phi plus/minus a constant, something that LSA considers non-aliasing
+    // with the Phi (LSA does not take different loop iterations into account)
+    // but LSE must consider aliasing across dfferent loop iterations.
+    return a[i - 1] + a[i - 2] + a[i - 3] + a[i - 4] + zero;
+  }
+
+  /// CHECK-START: int Main.testLoop37(int) load_store_elimination (before)
+  /// CHECK-DAG:                 ArraySet
+  /// CHECK-DAG:                 Deoptimize
+  /// CHECK-DAG:                 ArrayGet
+  /// CHECK-DAG:                 ArrayGet
+  /// CHECK-DAG:                 ArrayGet
+  /// CHECK-DAG:                 ArrayGet
+
+  /// CHECK-START: int Main.testLoop37(int) load_store_elimination (before)
+  /// CHECK-NOT:                 BoundsCheck
+
+  /// CHECK-START: int Main.testLoop37(int) load_store_elimination (after)
+  /// CHECK-DAG:                 ArraySet
+  /// CHECK-DAG:                 Deoptimize
+  /// CHECK-DAG:                 ArrayGet
+  /// CHECK-DAG:                 ArrayGet
+  /// CHECK-DAG:                 ArrayGet
+  /// CHECK-DAG:                 ArrayGet
+
+  // Similar to testLoop36 but the writes are done via a different reference to the same array.
+  // We previously used a reference comparison for back-edge aliasing analysis but this test
+  // has different references and therefore needs `HeapLocationCollector::CanReferencesAlias()`.
+  private static int testLoop37(int n) {
+    int[] a = new int[n];
+    int[] b = $noinline$returnArg(a);
+    int zero = 0;
+    int i = 0;
+    for (; i < n; ++i) {
+      b[i] = i;
+      // Extra instructions to avoid loop unrolling.
+      zero = (((zero ^ 1) + 2) ^ 1) - 2;
+      zero = (((zero ^ 4) + 8) ^ 4) - 8;
+    }
+    // Use 4 loads with consecutive fixed offsets from the loop Phi for `i`.
+    // BCE shall replace BoundsChecks with Deoptimize, so that indexes here are
+    // the Phi plus/minus a constant, something that LSA considers non-aliasing
+    // with the Phi (LSA does not take different loop iterations into account)
+    // but LSE must consider aliasing across dfferent loop iterations.
+    return a[i - 1] + a[i - 2] + a[i - 3] + a[i - 4] + zero;
+  }
+
+  private static int[] $noinline$returnArg(int[] a) {
+    return a;
+  }
+
+  /// CHECK-START: int Main.testLoop38(int, int[]) load_store_elimination (before)
+  /// CHECK-DAG:                 ArraySet
+  /// CHECK-DAG:                 Deoptimize
+  /// CHECK-DAG:                 ArrayGet
+  /// CHECK-DAG:                 ArrayGet
+  /// CHECK-DAG:                 ArrayGet
+  /// CHECK-DAG:                 ArrayGet
+
+  /// CHECK-START: int Main.testLoop38(int, int[]) load_store_elimination (before)
+  /// CHECK-NOT:                 BoundsCheck
+
+  /// CHECK-START: int Main.testLoop38(int, int[]) load_store_elimination (after)
+  /// CHECK-DAG:                 ArraySet
+  /// CHECK-DAG:                 Deoptimize
+
+  /// CHECK-START: int Main.testLoop38(int, int[]) load_store_elimination (after)
+  /// CHECK-NOT:                 ArrayGet
+
+  // Similar to testLoop37 but writing to a different array that exists before allocating `a`,
+  // so that `HeapLocationCollector::CanReferencesAlias()` returns false and all the ArrayGet
+  // instructions are actually eliminated.
+  private static int testLoop38(int n, int[] b) {
+    int[] a = new int[n];
+    int zero = 0;
+    int i = 0;
+    for (; i < n; ++i) {
+      b[i] = i;
+      // Extra instructions to avoid loop unrolling.
+      zero = (((zero ^ 1) + 2) ^ 1) - 2;
+      zero = (((zero ^ 4) + 8) ^ 4) - 8;
+    }
+    // Use 4 loads with consecutive fixed offsets from the loop Phi for `i`.
+    // BCE shall replace BoundsChecks with Deoptimize, so that indexes here are
+    // the Phi plus/minus a constant, something that LSA considers non-aliasing
+    // with the Phi (LSA does not take different loop iterations into account)
+    // but LSE must consider aliasing across dfferent loop iterations.
+    return a[i - 1] + a[i - 2] + a[i - 3] + a[i - 4] + zero;
+  }
+
   /// CHECK-START: int Main.testNestedLoop1(TestClass, int) load_store_elimination (before)
   /// CHECK-DAG:                 InstanceFieldSet
   /// CHECK-DAG:                 InstanceFieldGet
@@ -4445,6 +4573,9 @@ public class Main {
     assertIntEquals(testLoop35(1), 1);
     assertIntEquals(testLoop35(2), 3);
     assertIntEquals(testLoop35(3), 6);
+    assertIntEquals(testLoop36(4), 6);
+    assertIntEquals(testLoop37(4), 6);
+    assertIntEquals(testLoop38(4, new int[4]), 0);
 
     assertIntEquals(testNestedLoop1(new TestClass(), 0), 1);
     assertIntEquals(testNestedLoop1(new TestClass(), 1), 1);