Fix LSE-array overlap issue

In cases where an array has overlapping accesses on separate
iterations LSE could get confused and incorrectly believe removing
array stores is safe even when later iterations rely on the store
occurring. For example consider the following code:

```
int do_cal(int len) {
  if (len < 5) {
    return -1;
  }
  int w[] = new w[len];
  int t = 0;
  for (int i = 5; i < w.length; i++) {
    w[i] = please_interleave(w[i - 1], w[i - 5]);
    t = please_select(w[i], i);
  }
  return t;
}
```

We would either need to materialize 5 PHIs to hold the values
`w[i - 1], ..., w[i - 5]` or avoid removing the write to `w[i]`. Our
LSE pass is unable to do the former and would (incorrectly) fail to
recognize that, by not being able to determine the values of `w[i -
1]` and `w[i-5]` that the later store to `w[i]` must be preserved.

Bug: 168446366
Test: ./test.py --host
Change-Id: I89772c8bf49ebf6de70f86bd68484e14bd189406

1 files changed, 54 insertions, 0 deletions

diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h
index 484e444d6d..792c9db1af 100644
--- a/compiler/optimizing/optimizing_unit_test.h
+++ b/compiler/optimizing/optimizing_unit_test.h
@@ -292,6 +292,60 @@ inline bool IsRemoved(HInstruction* instruction) {
   return instruction->GetBlock() == nullptr;
 }
 
+class AdjacencyListGraph {
+ public:
+  using Edge = std::pair<const std::string_view, const std::string_view>;
+  AdjacencyListGraph(
+      HGraph* graph,
+      ArenaAllocator* alloc,
+      const std::string_view entry_name,
+      const std::string_view exit_name,
+      const std::vector<Edge>& adj) : graph_(graph) {
+    auto create_block = [&]() {
+      HBasicBlock* blk = new (alloc) HBasicBlock(graph_);
+      graph_->AddBlock(blk);
+      return blk;
+    };
+    HBasicBlock* entry = create_block();
+    HBasicBlock* exit = create_block();
+    graph_->SetEntryBlock(entry);
+    graph_->SetExitBlock(exit);
+    name_to_block_.Put(entry_name, entry);
+    name_to_block_.Put(exit_name, exit);
+    for (const auto& [src, dest] : adj) {
+      HBasicBlock* src_blk = name_to_block_.GetOrCreate(src, create_block);
+      HBasicBlock* dest_blk = name_to_block_.GetOrCreate(dest, create_block);
+      src_blk->AddSuccessor(dest_blk);
+    }
+    graph_->ComputeDominanceInformation();
+    for (auto [name, blk] : name_to_block_) {
+      block_to_name_.Put(blk, name);
+    }
+  }
+
+  bool HasBlock(const HBasicBlock* blk) {
+    return block_to_name_.find(blk) != block_to_name_.end();
+  }
+
+  std::string_view GetName(const HBasicBlock* blk) {
+    return block_to_name_.Get(blk);
+  }
+
+  HBasicBlock* Get(const std::string_view& sv) {
+    return name_to_block_.Get(sv);
+  }
+
+  AdjacencyListGraph(AdjacencyListGraph&&) = default;
+  AdjacencyListGraph(const AdjacencyListGraph&) = default;
+  AdjacencyListGraph& operator=(AdjacencyListGraph&&) = default;
+  AdjacencyListGraph& operator=(const AdjacencyListGraph&) = default;
+
+ private:
+  HGraph* graph_;
+  SafeMap<const std::string_view, HBasicBlock*> name_to_block_;
+  SafeMap<const HBasicBlock*, const std::string_view> block_to_name_;
+};
+
 }  // namespace art
 
 #endif  // ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_