Partial LSE analysis & store removal

This is the first piece of partial LSE for art. This CL adds analysis
tools needed to implement partial LSE. More immediately, it improves
LSE so that it will remove stores that are provably non-observable
based on the location they occur. For example:

```
Foo o = new Foo();
if (xyz) {
  check(foo);
  foo.x++;
} else {
  foo.x = 12;
}
return foo.x;
```

The store of 12 can be removed because the only escape in this method
is unreachable and was not executed by the point we reach the store.

The main purpose of this CL is to add the analysis tools needed to
implement partial Load-Store elimination. Namely it includes tracking
of which blocks are escaping and the groups of blocks that we cannot
remove allocations from.

The actual impact of this change is incredibly minor, being triggered
only once in a AOSP code. go/lem shows only minor effects to
compile-time and no effect on the compiled code. See
go/lem-allight-partial-lse-2 for numbers. Compile time shows an
average of 1.4% regression (max regression is 7% with 0.2 noise).

This CL adds a new 'reachability' concept to the HGraph. If this has
been calculated it allows one to quickly query whether there is any
execution path containing two blocks in a given order. This is used to
define a notion of sections of graph from which the escape of some
allocation is inevitable.

Test: art_compiler_tests
Test: treehugger
Bug: 67037140
Change-Id: I0edc8d6b73f7dd329cb1ea7923080a0abe913ea6

1 files changed, 5 insertions, 3 deletions

diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h
index 792c9db1af..71acdacdb4 100644
--- a/compiler/optimizing/optimizing_unit_test.h
+++ b/compiler/optimizing/optimizing_unit_test.h
@@ -317,21 +317,23 @@ class AdjacencyListGraph {
       HBasicBlock* dest_blk = name_to_block_.GetOrCreate(dest, create_block);
       src_blk->AddSuccessor(dest_blk);
     }
+    graph_->ClearReachabilityInformation();
     graph_->ComputeDominanceInformation();
+    graph_->ComputeReachabilityInformation();
     for (auto [name, blk] : name_to_block_) {
       block_to_name_.Put(blk, name);
     }
   }
 
-  bool HasBlock(const HBasicBlock* blk) {
+  bool HasBlock(const HBasicBlock* blk) const {
     return block_to_name_.find(blk) != block_to_name_.end();
   }
 
-  std::string_view GetName(const HBasicBlock* blk) {
+  std::string_view GetName(const HBasicBlock* blk) const {
     return block_to_name_.Get(blk);
   }
 
-  HBasicBlock* Get(const std::string_view& sv) {
+  HBasicBlock* Get(const std::string_view& sv) const {
     return name_to_block_.Get(sv);
   }