From 9dec90a069386a5e538f5cfb9ff7ef789bdbafdb Mon Sep 17 00:00:00 2001
From: Alex Light <allight@google.com>
Date: Mon, 14 Sep 2020 17:58:28 -0700
Subject: 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
---
 compiler/optimizing/optimizing_unit_test.h | 54 ++++++++++++++++++++++++++++++
 1 file changed, 54 insertions(+)

(limited to 'compiler/optimizing/optimizing_unit_test.h')

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_
-- 
cgit v1.2.3-59-g8ed1b