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
diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h
index 484e444..792c9db 100644
--- a/compiler/optimizing/optimizing_unit_test.h
+++ b/compiler/optimizing/optimizing_unit_test.h
@@ -292,6 +292,60 @@
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_