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, 364 insertions, 0 deletions

diff --git a/compiler/optimizing/execution_subgraph.cc b/compiler/optimizing/execution_subgraph.cc
new file mode 100644
index 0000000000..5045e8db0b
--- /dev/null
+++ b/compiler/optimizing/execution_subgraph.cc
@@ -0,0 +1,364 @@
+/*
+ * Copyright (C) 2020 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "execution_subgraph.h"
+
+#include <algorithm>
+#include <unordered_set>
+
+#include "android-base/macros.h"
+#include "base/arena_allocator.h"
+#include "base/arena_bit_vector.h"
+#include "base/globals.h"
+#include "base/scoped_arena_allocator.h"
+#include "nodes.h"
+
+namespace art {
+
+ExecutionSubgraph::ExecutionSubgraph(HGraph* graph,
+                                     bool analysis_possible,
+                                     ScopedArenaAllocator* allocator)
+    : graph_(graph),
+      allocator_(allocator),
+      allowed_successors_(analysis_possible ? graph_->GetBlocks().size() : 0,
+                          ~(std::bitset<kMaxFilterableSuccessors> {}),
+                          allocator_->Adapter(kArenaAllocLSA)),
+      unreachable_blocks_(
+          allocator_, analysis_possible ? graph_->GetBlocks().size() : 0, false, kArenaAllocLSA),
+      valid_(analysis_possible),
+      needs_prune_(false),
+      finalized_(false) {
+  if (valid_) {
+    DCHECK(std::all_of(graph->GetBlocks().begin(), graph->GetBlocks().end(), [](HBasicBlock* it) {
+      return it == nullptr || it->GetSuccessors().size() <= kMaxFilterableSuccessors;
+    }));
+  }
+}
+
+void ExecutionSubgraph::RemoveBlock(const HBasicBlock* to_remove) {
+  if (!valid_) {
+    return;
+  }
+  uint32_t id = to_remove->GetBlockId();
+  if (unreachable_blocks_.IsBitSet(id)) {
+    if (kIsDebugBuild) {
+      // This isn't really needed but it's good to have this so it functions as
+      // a DCHECK that we always call Prune after removing any block.
+      needs_prune_ = true;
+    }
+    return;
+  }
+  unreachable_blocks_.SetBit(id);
+  for (HBasicBlock* pred : to_remove->GetPredecessors()) {
+    std::bitset<kMaxFilterableSuccessors> allowed_successors {};
+    // ZipCount iterates over both the successors and the index of them at the same time.
+    for (auto [succ, i] : ZipCount(MakeIterationRange(pred->GetSuccessors()))) {
+      if (succ != to_remove) {
+        allowed_successors.set(i);
+      }
+    }
+    LimitBlockSuccessors(pred, allowed_successors);
+  }
+}
+
+// Removes sink nodes.
+void ExecutionSubgraph::Prune() {
+  if (UNLIKELY(!valid_)) {
+    return;
+  }
+  needs_prune_ = false;
+  // This is the record of the edges that were both (1) explored and (2) reached
+  // the exit node.
+  {
+    // Allocator for temporary values.
+    ScopedArenaAllocator temporaries(graph_->GetArenaStack());
+    ScopedArenaVector<std::bitset<kMaxFilterableSuccessors>> results(
+        graph_->GetBlocks().size(), temporaries.Adapter(kArenaAllocLSA));
+    unreachable_blocks_.ClearAllBits();
+    // TODO We should support infinite loops as well.
+    if (UNLIKELY(graph_->GetExitBlock() == nullptr)) {
+      // Infinite loop
+      valid_ = false;
+      return;
+    }
+    // Fills up the 'results' map with what we need to add to update
+    // allowed_successors in order to prune sink nodes.
+    bool start_reaches_end = false;
+    // This is basically a DFS of the graph with some edges skipped.
+    {
+      const size_t num_blocks = graph_->GetBlocks().size();
+      constexpr ssize_t kUnvisitedSuccIdx = -1;
+      ArenaBitVector visiting(&temporaries, num_blocks, false, kArenaAllocLSA);
+      // How many of the successors of each block we have already examined. This
+      // has three states.
+      // (1) kUnvisitedSuccIdx: we have not examined any edges,
+      // (2) 0 <= val < # of successors: we have examined 'val' successors/are
+      // currently examining successors_[val],
+      // (3) kMaxFilterableSuccessors: We have examined all of the successors of
+      // the block (the 'result' is final).
+      ScopedArenaVector<ssize_t> last_succ_seen(
+          num_blocks, kUnvisitedSuccIdx, temporaries.Adapter(kArenaAllocLSA));
+      // A stack of which blocks we are visiting in this DFS traversal. Does not
+      // include the current-block. Used with last_succ_seen to figure out which
+      // bits to set if we find a path to the end/loop.
+      ScopedArenaVector<uint32_t> current_path(temporaries.Adapter(kArenaAllocLSA));
+      // Just ensure we have enough space. The allocator will be cleared shortly
+      // anyway so this is fast.
+      current_path.reserve(num_blocks);
+      // Current block we are examining. Modified only by 'push_block' and 'pop_block'
+      const HBasicBlock* cur_block = graph_->GetEntryBlock();
+      // Used to note a recur where we will start iterating on 'blk' and save
+      // where we are. We must 'continue' immediately after this.
+      auto push_block = [&](const HBasicBlock* blk) {
+        DCHECK(std::find(current_path.cbegin(), current_path.cend(), cur_block->GetBlockId()) ==
+               current_path.end());
+        if (kIsDebugBuild) {
+          std::for_each(current_path.cbegin(), current_path.cend(), [&](auto id) {
+            DCHECK_GT(last_succ_seen[id], kUnvisitedSuccIdx) << id;
+            DCHECK_LT(last_succ_seen[id], static_cast<ssize_t>(kMaxFilterableSuccessors)) << id;
+          });
+        }
+        current_path.push_back(cur_block->GetBlockId());
+        visiting.SetBit(cur_block->GetBlockId());
+        cur_block = blk;
+      };
+      // Used to note that we have fully explored a block and should return back
+      // up. Sets cur_block appropriately. We must 'continue' immediately after
+      // calling this.
+      auto pop_block = [&]() {
+        if (UNLIKELY(current_path.empty())) {
+          // Should only happen if entry-blocks successors are exhausted.
+          DCHECK_GE(last_succ_seen[graph_->GetEntryBlock()->GetBlockId()],
+                    static_cast<ssize_t>(graph_->GetEntryBlock()->GetSuccessors().size()));
+          cur_block = nullptr;
+        } else {
+          const HBasicBlock* last = graph_->GetBlocks()[current_path.back()];
+          visiting.ClearBit(current_path.back());
+          current_path.pop_back();
+          cur_block = last;
+        }
+      };
+      // Mark the current path as a path to the end. This is in contrast to paths
+      // that end in (eg) removed blocks.
+      auto propagate_true = [&]() {
+        for (uint32_t id : current_path) {
+          DCHECK_GT(last_succ_seen[id], kUnvisitedSuccIdx);
+          DCHECK_LT(last_succ_seen[id], static_cast<ssize_t>(kMaxFilterableSuccessors));
+          results[id].set(last_succ_seen[id]);
+        }
+      };
+      ssize_t num_entry_succ = graph_->GetEntryBlock()->GetSuccessors().size();
+      // As long as the entry-block has not explored all successors we still have
+      // work to do.
+      const uint32_t entry_block_id = graph_->GetEntryBlock()->GetBlockId();
+      while (num_entry_succ > last_succ_seen[entry_block_id]) {
+        DCHECK(cur_block != nullptr);
+        uint32_t id = cur_block->GetBlockId();
+        DCHECK((current_path.empty() && cur_block == graph_->GetEntryBlock()) ||
+               current_path.front() == graph_->GetEntryBlock()->GetBlockId())
+            << "current path size: " << current_path.size()
+            << " cur_block id: " << cur_block->GetBlockId() << " entry id "
+            << graph_->GetEntryBlock()->GetBlockId();
+        DCHECK(!visiting.IsBitSet(id))
+            << "Somehow ended up in a loop! This should have been caught before now! " << id;
+        std::bitset<kMaxFilterableSuccessors>& result = results[id];
+        if (cur_block == graph_->GetExitBlock()) {
+          start_reaches_end = true;
+          propagate_true();
+          pop_block();
+          continue;
+        } else if (last_succ_seen[id] == kMaxFilterableSuccessors) {
+          // Already fully explored.
+          if (result.any()) {
+            propagate_true();
+          }
+          pop_block();
+          continue;
+        }
+        // NB This is a pointer. Modifications modify the last_succ_seen.
+        ssize_t* cur_succ = &last_succ_seen[id];
+        std::bitset<kMaxFilterableSuccessors> succ_bitmap = GetAllowedSuccessors(cur_block);
+        // Get next successor allowed.
+        while (++(*cur_succ) < static_cast<ssize_t>(kMaxFilterableSuccessors) &&
+               !succ_bitmap.test(*cur_succ)) {
+          DCHECK_GE(*cur_succ, 0);
+        }
+        if (*cur_succ >= static_cast<ssize_t>(cur_block->GetSuccessors().size())) {
+          // No more successors. Mark that we've checked everything. Later visits
+          // to this node can use the existing data.
+          DCHECK_LE(*cur_succ, static_cast<ssize_t>(kMaxFilterableSuccessors));
+          *cur_succ = kMaxFilterableSuccessors;
+          pop_block();
+          continue;
+        }
+        const HBasicBlock* nxt = cur_block->GetSuccessors()[*cur_succ];
+        DCHECK(nxt != nullptr) << "id: " << *cur_succ
+                               << " max: " << cur_block->GetSuccessors().size();
+        if (visiting.IsBitSet(nxt->GetBlockId())) {
+          // This is a loop. Mark it and continue on. Mark allowed-successor on
+          // this block's results as well.
+          result.set(*cur_succ);
+          propagate_true();
+        } else {
+          // Not a loop yet. Recur.
+          push_block(nxt);
+        }
+      }
+    }
+    // If we can't reach the end then there is no path through the graph without
+    // hitting excluded blocks
+    if (UNLIKELY(!start_reaches_end)) {
+      valid_ = false;
+      return;
+    }
+    // Mark blocks we didn't see in the ReachesEnd flood-fill
+    for (const HBasicBlock* blk : graph_->GetBlocks()) {
+      if (blk != nullptr &&
+          results[blk->GetBlockId()].none() &&
+          blk != graph_->GetExitBlock() &&
+          blk != graph_->GetEntryBlock()) {
+        // We never visited this block, must be unreachable.
+        unreachable_blocks_.SetBit(blk->GetBlockId());
+      }
+    }
+    // write the new data.
+    memcpy(allowed_successors_.data(),
+           results.data(),
+           results.size() * sizeof(std::bitset<kMaxFilterableSuccessors>));
+  }
+  RecalculateExcludedCohort();
+}
+
+void ExecutionSubgraph::RemoveConcavity() {
+  if (UNLIKELY(!valid_)) {
+    return;
+  }
+  DCHECK(!needs_prune_);
+  for (const HBasicBlock* blk : graph_->GetBlocks()) {
+    if (blk == nullptr || unreachable_blocks_.IsBitSet(blk->GetBlockId())) {
+      continue;
+    }
+    uint32_t blkid = blk->GetBlockId();
+    if (std::any_of(unreachable_blocks_.Indexes().begin(),
+                    unreachable_blocks_.Indexes().end(),
+                    [&](uint32_t skipped) { return graph_->PathBetween(skipped, blkid); }) &&
+        std::any_of(unreachable_blocks_.Indexes().begin(),
+                    unreachable_blocks_.Indexes().end(),
+                    [&](uint32_t skipped) { return graph_->PathBetween(blkid, skipped); })) {
+      RemoveBlock(blk);
+    }
+  }
+  Prune();
+}
+
+void ExecutionSubgraph::RecalculateExcludedCohort() {
+  DCHECK(!needs_prune_);
+  excluded_list_.emplace(allocator_->Adapter(kArenaAllocLSA));
+  ScopedArenaVector<ExcludedCohort>& res = excluded_list_.value();
+  // Make a copy of unreachable_blocks_;
+  ArenaBitVector unreachable(allocator_, graph_->GetBlocks().size(), false, kArenaAllocLSA);
+  unreachable.Copy(&unreachable_blocks_);
+  // Split cohorts with union-find
+  while (unreachable.IsAnyBitSet()) {
+    res.emplace_back(allocator_, graph_);
+    ExcludedCohort& cohort = res.back();
+    // We don't allocate except for the queue beyond here so create another arena to save memory.
+    ScopedArenaAllocator alloc(graph_->GetArenaStack());
+    ScopedArenaQueue<const HBasicBlock*> worklist(alloc.Adapter(kArenaAllocLSA));
+    // Select an arbitrary node
+    const HBasicBlock* first = graph_->GetBlocks()[unreachable.GetHighestBitSet()];
+    worklist.push(first);
+    do {
+      // Flood-fill both forwards and backwards.
+      const HBasicBlock* cur = worklist.front();
+      worklist.pop();
+      if (!unreachable.IsBitSet(cur->GetBlockId())) {
+        // Already visited or reachable somewhere else.
+        continue;
+      }
+      unreachable.ClearBit(cur->GetBlockId());
+      cohort.blocks_.SetBit(cur->GetBlockId());
+      // don't bother filtering here, it's done next go-around
+      for (const HBasicBlock* pred : cur->GetPredecessors()) {
+        worklist.push(pred);
+      }
+      for (const HBasicBlock* succ : cur->GetSuccessors()) {
+        worklist.push(succ);
+      }
+    } while (!worklist.empty());
+  }
+  // Figure out entry & exit nodes.
+  for (ExcludedCohort& cohort : res) {
+    DCHECK(cohort.blocks_.IsAnyBitSet());
+    auto is_external = [&](const HBasicBlock* ext) -> bool {
+      return !cohort.blocks_.IsBitSet(ext->GetBlockId());
+    };
+    for (const HBasicBlock* blk : cohort.Blocks()) {
+      const auto& preds = blk->GetPredecessors();
+      const auto& succs = blk->GetSuccessors();
+      if (std::any_of(preds.cbegin(), preds.cend(), is_external)) {
+        cohort.entry_blocks_.SetBit(blk->GetBlockId());
+      }
+      if (std::any_of(succs.cbegin(), succs.cend(), is_external)) {
+        cohort.exit_blocks_.SetBit(blk->GetBlockId());
+      }
+    }
+  }
+}
+
+std::ostream& operator<<(std::ostream& os, const ExecutionSubgraph::ExcludedCohort& ex) {
+  ex.Dump(os);
+  return os;
+}
+
+void ExecutionSubgraph::ExcludedCohort::Dump(std::ostream& os) const {
+  auto dump = [&](BitVecBlockRange arr) {
+    os << "[";
+    bool first = true;
+    for (const HBasicBlock* b : arr) {
+      if (!first) {
+        os << ", ";
+      }
+      first = false;
+      os << b->GetBlockId();
+    }
+    os << "]";
+  };
+  auto dump_blocks = [&]() {
+    os << "[";
+    bool first = true;
+    for (const HBasicBlock* b : Blocks()) {
+      if (!entry_blocks_.IsBitSet(b->GetBlockId()) && !exit_blocks_.IsBitSet(b->GetBlockId())) {
+        if (!first) {
+          os << ", ";
+        }
+        first = false;
+        os << b->GetBlockId();
+      }
+    }
+    os << "]";
+  };
+
+  os << "{ entry: ";
+  dump(EntryBlocks());
+  os << ", interior: ";
+  dump_blocks();
+  os << ", exit: ";
+  dump(ExitBlocks());
+  os << "}";
+}
+
+}  // namespace art