Revert^2 "Partial LSE analysis & store removal"
A ScopedArenaAllocator in a single test was accidentally loaded using
operator new which is not supported. This caused a memory leak.
This reverts commit fe270426c8a2a69a8f669339e83b86fbf40e25a1.
This unreverts commit bb6cda60e4418c0ab557ea4090e046bed8206763.
Bug: 67037140
Reason for revert: Fixed memory leak in
LoadStoreAnalysisTest.PartialEscape test case
Test: SANITIZE_HOST=address ASAN_OPTIONS=detect_leaks=0 m test-art-host-gtest-dependencies
Run art_compiler_tests
Change-Id: I34fa2079df946ae54b8c91fa771a44d56438a719
diff --git a/compiler/Android.bp b/compiler/Android.bp
index e91700b..523aab6 100644
--- a/compiler/Android.bp
+++ b/compiler/Android.bp
@@ -48,6 +48,7 @@
"optimizing/data_type.cc",
"optimizing/dead_code_elimination.cc",
"optimizing/escape.cc",
+ "optimizing/execution_subgraph.cc",
"optimizing/graph_checker.cc",
"optimizing/graph_visualizer.cc",
"optimizing/gvn.cc",
@@ -414,6 +415,7 @@
"jni/jni_cfi_test.cc",
"optimizing/codegen_test.cc",
+ "optimizing/execution_subgraph_test.cc",
"optimizing/load_store_analysis_test.cc",
"optimizing/load_store_elimination_test.cc",
"optimizing/optimizing_cfi_test.cc",
diff --git a/compiler/optimizing/execution_subgraph.cc b/compiler/optimizing/execution_subgraph.cc
new file mode 100644
index 0000000..5045e8d
--- /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
diff --git a/compiler/optimizing/execution_subgraph.h b/compiler/optimizing/execution_subgraph.h
new file mode 100644
index 0000000..dac938e
--- /dev/null
+++ b/compiler/optimizing/execution_subgraph.h
@@ -0,0 +1,321 @@
+/*
+ * 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.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_EXECUTION_SUBGRAPH_H_
+#define ART_COMPILER_OPTIMIZING_EXECUTION_SUBGRAPH_H_
+
+#include <algorithm>
+#include <sstream>
+
+#include "base/arena_allocator.h"
+#include "base/arena_bit_vector.h"
+#include "base/arena_containers.h"
+#include "base/array_ref.h"
+#include "base/bit_vector-inl.h"
+#include "base/globals.h"
+#include "base/iteration_range.h"
+#include "base/scoped_arena_allocator.h"
+#include "base/scoped_arena_containers.h"
+#include "base/stl_util.h"
+#include "base/transform_iterator.h"
+#include "nodes.h"
+
+namespace art {
+
+// Helper for transforming block ids to blocks.
+class BlockIdToBlockTransformer {
+ public:
+ BlockIdToBlockTransformer(BlockIdToBlockTransformer&&) = default;
+ BlockIdToBlockTransformer(const BlockIdToBlockTransformer&) = default;
+ explicit BlockIdToBlockTransformer(const HGraph* graph) : graph_(graph) {}
+
+ inline const HGraph* GetGraph() const {
+ return graph_;
+ }
+
+ inline HBasicBlock* GetBlock(uint32_t id) const {
+ DCHECK_LT(id, graph_->GetBlocks().size()) << graph_->PrettyMethod();
+ HBasicBlock* blk = graph_->GetBlocks()[id];
+ DCHECK(blk != nullptr);
+ return blk;
+ }
+
+ inline HBasicBlock* operator()(uint32_t id) const {
+ return GetBlock(id);
+ }
+
+ private:
+ const HGraph* const graph_;
+};
+
+// A representation of a particular section of the graph. The graph is split
+// into an excluded and included area and is used to track escapes.
+//
+// This object is a view of the graph and is not updated as the graph is
+// changed.
+//
+// This is implemented by removing various escape points from the subgraph using
+// the 'RemoveBlock' function. Once all required blocks are removed one will
+// 'Finalize' the subgraph. This will extend the removed area to include:
+// (1) Any block which inevitably leads to (post-dominates) a removed block
+// (2) any block which is between 2 removed blocks
+//
+// This allows us to create a set of 'ExcludedCohorts' which are the
+// well-connected subsets of the graph made up of removed blocks. These cohorts
+// have a set of entry and exit blocks which act as the boundary of the cohort.
+// Since we removed blocks between 2 excluded blocks it is impossible for any
+// cohort-exit block to reach any cohort-entry block. This means we can use the
+// boundary between the cohort and the rest of the graph to insert
+// materialization blocks for partial LSE.
+class ExecutionSubgraph : public ArenaObject<kArenaAllocLSA> {
+ public:
+ using BitVecBlockRange =
+ IterationRange<TransformIterator<BitVector::IndexIterator, BlockIdToBlockTransformer>>;
+
+ // A set of connected blocks which are connected and removed from the
+ // ExecutionSubgraph. See above comment for explanation.
+ class ExcludedCohort : public ArenaObject<kArenaAllocLSA> {
+ public:
+ ExcludedCohort(ExcludedCohort&&) = default;
+ ExcludedCohort(const ExcludedCohort&) = delete;
+ explicit ExcludedCohort(ScopedArenaAllocator* allocator, HGraph* graph)
+ : graph_(graph),
+ entry_blocks_(allocator, graph_->GetBlocks().size(), false, kArenaAllocLSA),
+ exit_blocks_(allocator, graph_->GetBlocks().size(), false, kArenaAllocLSA),
+ blocks_(allocator, graph_->GetBlocks().size(), false, kArenaAllocLSA) {}
+
+ ~ExcludedCohort() = default;
+
+ // All blocks in the cohort.
+ BitVecBlockRange Blocks() const {
+ return BlockIterRange(blocks_);
+ }
+
+ // Blocks that have predecessors outside of the cohort. These blocks will
+ // need to have PHIs/control-flow added to create the escaping value.
+ BitVecBlockRange EntryBlocks() const {
+ return BlockIterRange(entry_blocks_);
+ }
+
+ // Blocks that have successors outside of the cohort. The successors of
+ // these blocks will need to have PHI's to restore state.
+ BitVecBlockRange ExitBlocks() const {
+ return BlockIterRange(exit_blocks_);
+ }
+
+ bool operator==(const ExcludedCohort& other) const {
+ return blocks_.Equal(&other.blocks_);
+ }
+
+ bool ContainsBlock(const HBasicBlock* blk) const {
+ return blocks_.IsBitSet(blk->GetBlockId());
+ }
+
+ // Returns true if there is a path from 'blk' to any block in this cohort.
+ // NB blocks contained within the cohort are not considered to be succeeded
+ // by the cohort (i.e. this function will return false).
+ bool SucceedsBlock(const HBasicBlock* blk) const {
+ if (ContainsBlock(blk)) {
+ return false;
+ }
+ auto idxs = entry_blocks_.Indexes();
+ return std::any_of(idxs.begin(), idxs.end(), [&](uint32_t entry) -> bool {
+ return blk->GetGraph()->PathBetween(blk->GetBlockId(), entry);
+ });
+ }
+
+ // Returns true if there is a path from any block in this cohort to 'blk'.
+ // NB blocks contained within the cohort are not considered to be preceded
+ // by the cohort (i.e. this function will return false).
+ bool PrecedesBlock(const HBasicBlock* blk) const {
+ if (ContainsBlock(blk)) {
+ return false;
+ }
+ auto idxs = exit_blocks_.Indexes();
+ return std::any_of(idxs.begin(), idxs.end(), [&](uint32_t exit) -> bool {
+ return blk->GetGraph()->PathBetween(exit, blk->GetBlockId());
+ });
+ }
+
+ void Dump(std::ostream& os) const;
+
+ private:
+ BitVecBlockRange BlockIterRange(const ArenaBitVector& bv) const {
+ auto indexes = bv.Indexes();
+ BitVecBlockRange res = MakeTransformRange(indexes, BlockIdToBlockTransformer(graph_));
+ return res;
+ }
+
+ ExcludedCohort() = delete;
+
+ HGraph* graph_;
+ ArenaBitVector entry_blocks_;
+ ArenaBitVector exit_blocks_;
+ ArenaBitVector blocks_;
+
+ friend class ExecutionSubgraph;
+ friend class LoadStoreAnalysisTest;
+ };
+
+ // The number of successors we can track on a single block. Graphs which
+ // contain a block with a branching factor greater than this will not be
+ // analysed. This is used to both limit the memory usage of analysis to
+ // reasonable levels and ensure that the analysis will complete in a
+ // reasonable amount of time. It also simplifies the implementation somewhat
+ // to have a constant branching factor.
+ static constexpr uint32_t kMaxFilterableSuccessors = 8;
+
+ // Instantiate a subgraph. analysis_possible controls whether or not to even
+ // attempt partial-escape analysis. It should be false if partial-escape
+ // analysis is not desired (eg when being used for instruction scheduling) or
+ // when the branching factor in the graph is too high. This is calculated once
+ // and passed down for performance reasons.
+ ExecutionSubgraph(HGraph* graph, bool analysis_possible, ScopedArenaAllocator* allocator);
+
+ void Invalidate() {
+ valid_ = false;
+ }
+
+ // A block is contained by the ExecutionSubgraph if it is reachable. This
+ // means it has not been removed explicitly or via pruning/concavity removal.
+ // Finalization is needed to call this function.
+ // See RemoveConcavity and Prune for more information.
+ bool ContainsBlock(const HBasicBlock* blk) const {
+ DCHECK(!finalized_ || !needs_prune_) << "finalized: " << finalized_;
+ if (!valid_) {
+ return false;
+ }
+ return !unreachable_blocks_.IsBitSet(blk->GetBlockId());
+ }
+
+ // Mark the block as removed from the subgraph.
+ void RemoveBlock(const HBasicBlock* to_remove);
+
+ // Called when no more updates will be done to the subgraph. Calculate the
+ // final subgraph
+ void Finalize() {
+ Prune();
+ RemoveConcavity();
+ finalized_ = true;
+ }
+
+ BitVecBlockRange UnreachableBlocks() const {
+ auto idxs = unreachable_blocks_.Indexes();
+ return MakeTransformRange(idxs, BlockIdToBlockTransformer(graph_));
+ }
+
+ // Returns true if all allowed execution paths from start eventually reach the
+ // graph's exit block (or diverge).
+ bool IsValid() const {
+ return valid_;
+ }
+
+ ArrayRef<const ExcludedCohort> GetExcludedCohorts() const {
+ DCHECK(!valid_ || !needs_prune_);
+ if (!valid_ || !unreachable_blocks_.IsAnyBitSet()) {
+ return ArrayRef<const ExcludedCohort>();
+ } else {
+ return ArrayRef<const ExcludedCohort>(*excluded_list_);
+ }
+ }
+
+ // Helper class to create reachable blocks iterator.
+ class ContainsFunctor {
+ public:
+ bool operator()(HBasicBlock* blk) const {
+ return subgraph_->ContainsBlock(blk);
+ }
+
+ private:
+ explicit ContainsFunctor(const ExecutionSubgraph* subgraph) : subgraph_(subgraph) {}
+ const ExecutionSubgraph* const subgraph_;
+ friend class ExecutionSubgraph;
+ };
+ // Returns an iterator over reachable blocks (filtered as we go). This is primarilly for testing.
+ IterationRange<
+ FilterIterator<typename ArenaVector<HBasicBlock*>::const_iterator, ContainsFunctor>>
+ ReachableBlocks() const {
+ return Filter(MakeIterationRange(graph_->GetBlocks()), ContainsFunctor(this));
+ }
+
+ static bool CanAnalyse(HGraph* graph) {
+ // If there are any blocks with more than kMaxFilterableSuccessors we can't
+ // analyse the graph. We avoid this case to prevent excessive memory and
+ // time usage while allowing a simpler algorithm with a fixed-width
+ // branching factor.
+ return std::all_of(graph->GetBlocks().begin(), graph->GetBlocks().end(), [](HBasicBlock* blk) {
+ return blk == nullptr || blk->GetSuccessors().size() <= kMaxFilterableSuccessors;
+ });
+ }
+
+ private:
+ std::bitset<kMaxFilterableSuccessors> GetAllowedSuccessors(const HBasicBlock* blk) const {
+ DCHECK(valid_);
+ return allowed_successors_[blk->GetBlockId()];
+ }
+
+ void LimitBlockSuccessors(const HBasicBlock* block,
+ std::bitset<kMaxFilterableSuccessors> allowed) {
+ needs_prune_ = true;
+ allowed_successors_[block->GetBlockId()] &= allowed;
+ }
+
+ // Remove nodes which both precede and follow any exclusions. This ensures we don't need to deal
+ // with only conditionally materializing objects depending on if we already materialized them
+ // Ensure that for all blocks A, B, C: Unreachable(A) && Unreachable(C) && PathBetween(A, B) &&
+ // PathBetween(A, C) implies Unreachable(B). This simplifies later transforms since it ensures
+ // that no execution can leave and then re-enter any exclusion.
+ void RemoveConcavity();
+
+ // Removes sink nodes. Sink nodes are nodes where there is no execution which
+ // avoids all removed nodes.
+ void Prune();
+
+ void RecalculateExcludedCohort();
+
+ HGraph* graph_;
+ ScopedArenaAllocator* allocator_;
+ // The map from block_id -> allowed-successors.
+ // This is the canonical representation of this subgraph. If a bit in the
+ // bitset is not set then the corresponding outgoing edge of that block is not
+ // considered traversable.
+ ScopedArenaVector<std::bitset<kMaxFilterableSuccessors>> allowed_successors_;
+ // Helper that holds which blocks we are able to reach. Only valid if
+ // 'needs_prune_ == false'.
+ ArenaBitVector unreachable_blocks_;
+ // A list of the excluded-cohorts of this subgraph. This is only valid when
+ // 'needs_prune_ == false'
+ std::optional<ScopedArenaVector<ExcludedCohort>> excluded_list_;
+ // Bool to hold if there is at least one known path from the start block to
+ // the end in this graph. Used to short-circuit computation.
+ bool valid_;
+ // True if the subgraph is consistent and can be queried. Modifying the
+ // subgraph clears this and requires a prune to restore.
+ bool needs_prune_;
+ // True if no more modification of the subgraph is permitted.
+ bool finalized_;
+
+ friend class ExecutionSubgraphTest;
+ friend class LoadStoreAnalysisTest;
+
+ DISALLOW_COPY_AND_ASSIGN(ExecutionSubgraph);
+};
+
+std::ostream& operator<<(std::ostream& os, const ExecutionSubgraph::ExcludedCohort& ex);
+
+} // namespace art
+
+#endif // ART_COMPILER_OPTIMIZING_EXECUTION_SUBGRAPH_H_
diff --git a/compiler/optimizing/execution_subgraph_test.cc b/compiler/optimizing/execution_subgraph_test.cc
new file mode 100644
index 0000000..1fc00d9
--- /dev/null
+++ b/compiler/optimizing/execution_subgraph_test.cc
@@ -0,0 +1,831 @@
+/*
+ * 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_test.h"
+
+#include <array>
+#include <sstream>
+#include <string_view>
+#include <unordered_map>
+#include <unordered_set>
+
+#include "base/scoped_arena_allocator.h"
+#include "base/stl_util.h"
+#include "class_root.h"
+#include "dex/dex_file_types.h"
+#include "dex/method_reference.h"
+#include "entrypoints/quick/quick_entrypoints_enum.h"
+#include "execution_subgraph.h"
+#include "gtest/gtest.h"
+#include "handle.h"
+#include "handle_scope.h"
+#include "nodes.h"
+#include "optimizing/data_type.h"
+#include "optimizing_unit_test.h"
+#include "scoped_thread_state_change.h"
+
+namespace art {
+
+using BlockSet = std::unordered_set<const HBasicBlock*>;
+
+// Helper that checks validity directly.
+bool ExecutionSubgraphTestHelper::CalculateValidity(HGraph* graph, const ExecutionSubgraph* esg) {
+ bool reached_end = false;
+ std::queue<const HBasicBlock*> worklist;
+ std::unordered_set<const HBasicBlock*> visited;
+ worklist.push(graph->GetEntryBlock());
+ while (!worklist.empty()) {
+ const HBasicBlock* cur = worklist.front();
+ worklist.pop();
+ if (visited.find(cur) != visited.end()) {
+ continue;
+ } else {
+ visited.insert(cur);
+ }
+ if (cur == graph->GetExitBlock()) {
+ reached_end = true;
+ continue;
+ }
+ bool has_succ = false;
+ for (const HBasicBlock* succ : cur->GetSuccessors()) {
+ DCHECK(succ != nullptr) << "Bad successors on block " << cur->GetBlockId();
+ if (!esg->ContainsBlock(succ)) {
+ continue;
+ }
+ has_succ = true;
+ worklist.push(succ);
+ }
+ if (!has_succ) {
+ // We aren't at the end and have nowhere to go so fail.
+ return false;
+ }
+ }
+ return reached_end;
+}
+
+class ExecutionSubgraphTest : public OptimizingUnitTest {
+ public:
+ ExecutionSubgraphTest() : graph_(CreateGraph()) {}
+
+ AdjacencyListGraph SetupFromAdjacencyList(const std::string_view entry_name,
+ const std::string_view exit_name,
+ const std::vector<AdjacencyListGraph::Edge>& adj) {
+ return AdjacencyListGraph(graph_, GetAllocator(), entry_name, exit_name, adj);
+ }
+
+ bool IsValidSubgraph(const ExecutionSubgraph* esg) {
+ return ExecutionSubgraphTestHelper::CalculateValidity(graph_, esg);
+ }
+
+ bool IsValidSubgraph(const ExecutionSubgraph& esg) {
+ return ExecutionSubgraphTestHelper::CalculateValidity(graph_, &esg);
+ }
+
+ HGraph* graph_;
+};
+
+// Some comparators used by these tests to avoid having to deal with various set types.
+template <typename BLKS, typename = std::enable_if_t<!std::is_same_v<BlockSet, BLKS>>>
+bool operator==(const BlockSet& bs, const BLKS& sas) {
+ std::unordered_set<const HBasicBlock*> us(sas.begin(), sas.end());
+ return bs == us;
+}
+template <typename BLKS, typename = std::enable_if_t<!std::is_same_v<BlockSet, BLKS>>>
+bool operator==(const BLKS& sas, const BlockSet& bs) {
+ return bs == sas;
+}
+template <typename BLKS, typename = std::enable_if_t<!std::is_same_v<BlockSet, BLKS>>>
+bool operator!=(const BlockSet& bs, const BLKS& sas) {
+ return !(bs == sas);
+}
+template <typename BLKS, typename = std::enable_if_t<!std::is_same_v<BlockSet, BLKS>>>
+bool operator!=(const BLKS& sas, const BlockSet& bs) {
+ return !(bs == sas);
+}
+
+// +-------+ +-------+
+// | right | <-- | entry |
+// +-------+ +-------+
+// | |
+// | |
+// | v
+// | + - - - - - +
+// | ' removed '
+// | ' '
+// | ' +-------+ '
+// | ' | left | '
+// | ' +-------+ '
+// | ' '
+// | + - - - - - +
+// | |
+// | |
+// | v
+// | +-------+
+// +---------> | exit |
+// +-------+
+TEST_F(ExecutionSubgraphTest, Basic) {
+ AdjacencyListGraph blks(SetupFromAdjacencyList(
+ "entry",
+ "exit",
+ { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
+ ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
+ ExecutionSubgraph esg(graph_, true, GetScopedAllocator());
+ esg.RemoveBlock(blks.Get("left"));
+ esg.Finalize();
+ ASSERT_TRUE(esg.IsValid());
+ ASSERT_TRUE(IsValidSubgraph(esg));
+ std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
+ esg.ReachableBlocks().end());
+
+ ASSERT_EQ(contents.size(), 3u);
+ ASSERT_TRUE(contents.find(blks.Get("left")) == contents.end());
+
+ ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
+ esg.RemoveBlock(blks.Get("right"));
+ esg.Finalize();
+ std::unordered_set<const HBasicBlock*> contents_2(esg.ReachableBlocks().begin(),
+ esg.ReachableBlocks().end());
+ ASSERT_EQ(contents_2.size(), 0u);
+}
+
+// +-------+ +-------+
+// | right | <-- | entry |
+// +-------+ +-------+
+// | |
+// | |
+// | v
+// | + - - - - - - - - - - - - - - - - - - - -+
+// | ' indirectly_removed '
+// | ' '
+// | ' +-------+ +-----+ '
+// | ' | l1 | -------------------> | l1r | '
+// | ' +-------+ +-----+ '
+// | ' | | '
+// | ' | | '
+// | ' v | '
+// | ' +-------+ | '
+// | ' | l1l | | '
+// | ' +-------+ | '
+// | ' | | '
+// | ' | | '
+// | ' | | '
+// + - - - - - - - -+ | +- - - | | '
+// ' ' | +- v | '
+// ' +-----+ | +----------------+ | '
+// ' | l2r | <---------+-------------- | l2 (removed) | <-------------+ '
+// ' +-----+ | +----------------+ '
+// ' | ' | +- | '
+// ' | - - -+ | +- - - | - - - - - - - - - - - - - -+
+// ' | ' | ' | '
+// ' | ' | ' | '
+// ' | ' | ' v '
+// ' | ' | ' +-------+ '
+// ' | ' | ' | l2l | '
+// ' | ' | ' +-------+ '
+// ' | ' | ' | '
+// ' | ' | ' | '
+// ' | ' | ' | '
+// ' | - - -+ | +- - - | '
+// ' | ' | +- v '
+// ' | | +-------+ '
+// ' +---------------+-------------> | l3 | '
+// ' | +-------+ '
+// ' ' | +- '
+// + - - - - - - - -+ | +- - - - - - - - - +
+// | |
+// | |
+// | v
+// | +-------+
+// +-----------> | exit |
+// +-------+
+TEST_F(ExecutionSubgraphTest, Propagation) {
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
+ "exit",
+ { { "entry", "l1" },
+ { "l1", "l1l" },
+ { "l1", "l1r" },
+ { "l1l", "l2" },
+ { "l1r", "l2" },
+ { "l2", "l2l" },
+ { "l2", "l2r" },
+ { "l2l", "l3" },
+ { "l2r", "l3" },
+ { "l3", "exit" },
+ { "entry", "right" },
+ { "right", "exit" } }));
+ ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
+ ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
+ esg.RemoveBlock(blks.Get("l2"));
+ esg.Finalize();
+ ASSERT_TRUE(esg.IsValid());
+ ASSERT_TRUE(IsValidSubgraph(esg));
+ std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
+ esg.ReachableBlocks().end());
+
+ // ASSERT_EQ(contents.size(), 3u);
+ // Not present, no path through.
+ ASSERT_TRUE(contents.find(blks.Get("l1")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("l2")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("l3")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("l1l")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("l1r")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("l2l")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("l2r")) == contents.end());
+
+ // present, path through.
+ ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
+}
+
+// +------------------------------------+
+// | |
+// | +-------+ +-------+ |
+// | | right | <-- | entry | |
+// | +-------+ +-------+ |
+// | | | |
+// | | | |
+// | | v |
+// | | +-------+ +--------+
+// +----+---------> | l1 | --> | l1loop |
+// | +-------+ +--------+
+// | |
+// | |
+// | v
+// | +- - - - - -+
+// | ' removed '
+// | ' '
+// | ' +-------+ '
+// | ' | l2 | '
+// | ' +-------+ '
+// | ' '
+// | +- - - - - -+
+// | |
+// | |
+// | v
+// | +-------+
+// +---------> | exit |
+// +-------+
+TEST_F(ExecutionSubgraphTest, PropagationLoop) {
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
+ "exit",
+ { { "entry", "l1" },
+ { "l1", "l2" },
+ { "l1", "l1loop" },
+ { "l1loop", "l1" },
+ { "l2", "exit" },
+ { "entry", "right" },
+ { "right", "exit" } }));
+ ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
+ ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
+ esg.RemoveBlock(blks.Get("l2"));
+ esg.Finalize();
+ ASSERT_TRUE(esg.IsValid());
+ ASSERT_TRUE(IsValidSubgraph(esg));
+ std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
+ esg.ReachableBlocks().end());
+
+ ASSERT_EQ(contents.size(), 5u);
+
+ // Not present, no path through.
+ ASSERT_TRUE(contents.find(blks.Get("l2")) == contents.end());
+
+ // present, path through.
+ // Since the loop can diverge we should leave it in the execution subgraph.
+ ASSERT_TRUE(contents.find(blks.Get("l1")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("l1loop")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
+}
+
+// +--------------------------------+
+// | |
+// | +-------+ +-------+ |
+// | | right | <-- | entry | |
+// | +-------+ +-------+ |
+// | | | |
+// | | | |
+// | | v |
+// | | +-------+ +--------+
+// +----+---------> | l1 | --> | l1loop |
+// | +-------+ +--------+
+// | |
+// | |
+// | v
+// | +-------+
+// | | l2 |
+// | +-------+
+// | |
+// | |
+// | v
+// | +-------+
+// +---------> | exit |
+// +-------+
+TEST_F(ExecutionSubgraphTest, PropagationLoop2) {
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
+ "exit",
+ { { "entry", "l1" },
+ { "l1", "l2" },
+ { "l1", "l1loop" },
+ { "l1loop", "l1" },
+ { "l2", "exit" },
+ { "entry", "right" },
+ { "right", "exit" } }));
+ ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
+ ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
+ esg.RemoveBlock(blks.Get("l1"));
+ esg.Finalize();
+ ASSERT_TRUE(esg.IsValid());
+ ASSERT_TRUE(IsValidSubgraph(esg));
+ std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
+ esg.ReachableBlocks().end());
+
+ ASSERT_EQ(contents.size(), 3u);
+
+ // Not present, no path through.
+ ASSERT_TRUE(contents.find(blks.Get("l1")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("l1loop")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("l2")) == contents.end());
+
+ // present, path through.
+ ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
+}
+
+// +--------------------------------+
+// | |
+// | +-------+ +-------+ |
+// | | right | <-- | entry | |
+// | +-------+ +-------+ |
+// | | | |
+// | | | |
+// | | v |
+// | | +-------+ +--------+
+// +----+---------> | l1 | --> | l1loop |
+// | +-------+ +--------+
+// | |
+// | |
+// | v
+// | +-------+
+// | | l2 |
+// | +-------+
+// | |
+// | |
+// | v
+// | +-------+
+// +---------> | exit |
+// +-------+
+TEST_F(ExecutionSubgraphTest, PropagationLoop3) {
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
+ "exit",
+ { { "entry", "l1" },
+ { "l1", "l2" },
+ { "l1", "l1loop" },
+ { "l1loop", "l1" },
+ { "l2", "exit" },
+ { "entry", "right" },
+ { "right", "exit" } }));
+ ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
+ ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
+ esg.RemoveBlock(blks.Get("l1loop"));
+ esg.Finalize();
+ ASSERT_TRUE(esg.IsValid());
+ ASSERT_TRUE(IsValidSubgraph(esg));
+ std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
+ esg.ReachableBlocks().end());
+
+ ASSERT_EQ(contents.size(), 3u);
+
+ // Not present, no path through. If we got to l1 loop then we must merge back
+ // with l1 and l2 so they're bad too.
+ ASSERT_TRUE(contents.find(blks.Get("l1loop")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("l1")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("l2")) == contents.end());
+
+ // present, path through.
+ ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
+}
+
+TEST_F(ExecutionSubgraphTest, Invalid) {
+ AdjacencyListGraph blks(SetupFromAdjacencyList(
+ "entry",
+ "exit",
+ { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
+ ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
+ ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
+ esg.RemoveBlock(blks.Get("left"));
+ esg.RemoveBlock(blks.Get("right"));
+ esg.Finalize();
+
+ ASSERT_FALSE(esg.IsValid());
+ ASSERT_FALSE(IsValidSubgraph(esg));
+ std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
+ esg.ReachableBlocks().end());
+
+ ASSERT_EQ(contents.size(), 0u);
+}
+// Sibling branches are disconnected.
+TEST_F(ExecutionSubgraphTest, Exclusions) {
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
+ "exit",
+ { { "entry", "a" },
+ { "entry", "b" },
+ { "entry", "c" },
+ { "a", "exit" },
+ { "b", "exit" },
+ { "c", "exit" } }));
+ ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
+ ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
+ esg.RemoveBlock(blks.Get("a"));
+ esg.RemoveBlock(blks.Get("c"));
+ esg.Finalize();
+ ASSERT_TRUE(esg.IsValid());
+ ASSERT_TRUE(IsValidSubgraph(esg));
+ std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
+ esg.ReachableBlocks().end());
+
+ ASSERT_EQ(contents.size(), 3u);
+ // Not present, no path through.
+ ASSERT_TRUE(contents.find(blks.Get("a")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("c")) == contents.end());
+
+ // present, path through.
+ ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("b")) != contents.end());
+
+ ArrayRef<const ExecutionSubgraph::ExcludedCohort> exclusions(esg.GetExcludedCohorts());
+ ASSERT_EQ(exclusions.size(), 2u);
+ std::unordered_set<const HBasicBlock*> exclude_a({ blks.Get("a") });
+ std::unordered_set<const HBasicBlock*> exclude_c({ blks.Get("c") });
+ ASSERT_TRUE(std::find_if(exclusions.cbegin(),
+ exclusions.cend(),
+ [&](const ExecutionSubgraph::ExcludedCohort& it) {
+ return it.Blocks() == exclude_a;
+ }) != exclusions.cend());
+ ASSERT_TRUE(std::find_if(exclusions.cbegin(),
+ exclusions.cend(),
+ [&](const ExecutionSubgraph::ExcludedCohort& it) {
+ return it.Blocks() == exclude_c;
+ }) != exclusions.cend());
+}
+
+// Sibling branches are disconnected.
+// +- - - - - - - - - - - - - - - - - - - - - - +
+// ' remove_c '
+// ' '
+// ' +-----------+ '
+// ' | c_begin_2 | -------------------------+ '
+// ' +-----------+ | '
+// ' | '
+// +- - - - - - - - - - - - - - - - - - | '
+// ^ ' | '
+// | ' | '
+// | ' | '
+// + - - - - - -+ ' | '
+// ' remove_a ' ' | '
+// ' ' ' | '
+// ' +--------+ ' +-----------+ +---+' | '
+// ' | **a** | ' <-- | entry | --> | b |' | '
+// ' +--------+ ' +-----------+ +---+' | '
+// ' ' ' | '
+// + - - - - - -+ ' | '
+// | | | ' | '
+// | | | ' | '
+// | v | ' | '
+// | +- - - - - - - -+ | ' | '
+// | ' ' | ' | '
+// | ' +-----------+ ' | ' | '
+// | ' | c_begin_1 | ' | ' | '
+// | ' +-----------+ ' | ' | '
+// | ' | ' | ' | '
+// | ' | ' | ' | '
+// | ' | ' | ' | '
+// + - - - - - - - - -+ | + - - - | - - - - - - - + | ' | '
+// ' ' | + v ' | + | '
+// ' +---------+ | +-----------+ | | '
+// ' | c_end_2 | <-------+--------------- | **c_mid** | <-----------------+------+ '
+// ' +---------+ | +-----------+ | '
+// ' ' | + | ' | + '
+// + - - - - - - - - -+ | + - - - | - - - - - - - + | + - - - +
+// | | ' | ' |
+// | | ' | ' |
+// | | ' v ' |
+// | | ' +-----------+ ' |
+// | | ' | c_end_1 | ' |
+// | | ' +-----------+ ' |
+// | | ' ' |
+// | | +- - - - - - - -+ |
+// | | | |
+// | | | |
+// | | v v
+// | | +---------------------------------+
+// | +------------> | exit |
+// | +---------------------------------+
+// | ^
+// +------------------------------------+
+TEST_F(ExecutionSubgraphTest, ExclusionExtended) {
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
+ "exit",
+ { { "entry", "a" },
+ { "entry", "b" },
+ { "entry", "c_begin_1" },
+ { "entry", "c_begin_2" },
+ { "c_begin_1", "c_mid" },
+ { "c_begin_2", "c_mid" },
+ { "c_mid", "c_end_1" },
+ { "c_mid", "c_end_2" },
+ { "a", "exit" },
+ { "b", "exit" },
+ { "c_end_1", "exit" },
+ { "c_end_2", "exit" } }));
+ ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
+ ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
+ esg.RemoveBlock(blks.Get("a"));
+ esg.RemoveBlock(blks.Get("c_mid"));
+ esg.Finalize();
+ ASSERT_TRUE(esg.IsValid());
+ ASSERT_TRUE(IsValidSubgraph(esg));
+ std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
+ esg.ReachableBlocks().end());
+
+ ASSERT_EQ(contents.size(), 3u);
+ // Not present, no path through.
+ ASSERT_TRUE(contents.find(blks.Get("a")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("c_begin_1")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("c_begin_2")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("c_mid")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("c_end_1")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("c_end_2")) == contents.end());
+
+ // present, path through.
+ ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("b")) != contents.end());
+
+ ArrayRef<const ExecutionSubgraph::ExcludedCohort> exclusions(esg.GetExcludedCohorts());
+ ASSERT_EQ(exclusions.size(), 2u);
+ BlockSet exclude_a({ blks.Get("a") });
+ BlockSet exclude_c({ blks.Get("c_begin_1"),
+ blks.Get("c_begin_2"),
+ blks.Get("c_mid"),
+ blks.Get("c_end_1"),
+ blks.Get("c_end_2") });
+ ASSERT_TRUE(std::find_if(exclusions.cbegin(),
+ exclusions.cend(),
+ [&](const ExecutionSubgraph::ExcludedCohort& it) {
+ return it.Blocks() == exclude_a;
+ }) != exclusions.cend());
+ ASSERT_TRUE(
+ std::find_if(
+ exclusions.cbegin(), exclusions.cend(), [&](const ExecutionSubgraph::ExcludedCohort& it) {
+ return it.Blocks() == exclude_c &&
+ BlockSet({ blks.Get("c_begin_1"), blks.Get("c_begin_2") }) == it.EntryBlocks() &&
+ BlockSet({ blks.Get("c_end_1"), blks.Get("c_end_2") }) == it.ExitBlocks();
+ }) != exclusions.cend());
+}
+
+// ┌───────┐ ┌────────────┐
+// ┌─ │ right │ ◀── │ entry │
+// │ └───────┘ └────────────┘
+// │ │
+// │ │
+// │ ▼
+// │ ┌────────────┐
+// │ │ esc_top │
+// │ └────────────┘
+// │ │
+// │ │
+// │ ▼
+// │ ┌────────────┐
+// └──────────────▶ │ middle │ ─┐
+// └────────────┘ │
+// │ │
+// │ │
+// ▼ │
+// ┌────────────┐ │
+// │ esc_bottom │ │
+// └────────────┘ │
+// │ │
+// │ │
+// ▼ │
+// ┌────────────┐ │
+// │ exit │ ◀┘
+// └────────────┘
+TEST_F(ExecutionSubgraphTest, InAndOutEscape) {
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
+ "exit",
+ { { "entry", "esc_top" },
+ { "entry", "right" },
+ { "esc_top", "middle" },
+ { "right", "middle" },
+ { "middle", "exit" },
+ { "middle", "esc_bottom" },
+ { "esc_bottom", "exit" } }));
+
+ ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
+ ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
+ esg.RemoveBlock(blks.Get("esc_top"));
+ esg.RemoveBlock(blks.Get("esc_bottom"));
+ esg.Finalize();
+
+ std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
+ esg.ReachableBlocks().end());
+ ASSERT_EQ(contents.size(), 0u);
+ ASSERT_FALSE(esg.IsValid());
+ ASSERT_FALSE(IsValidSubgraph(esg));
+
+ ASSERT_EQ(contents.size(), 0u);
+}
+
+// Test with max number of successors and no removals.
+TEST_F(ExecutionSubgraphTest, BigNodes) {
+ std::vector<std::string> mid_blocks;
+ for (auto i : Range(ExecutionSubgraph::kMaxFilterableSuccessors)) {
+ std::ostringstream oss;
+ oss << "blk" << i;
+ mid_blocks.push_back(oss.str().c_str());
+ }
+ ASSERT_EQ(mid_blocks.size(), ExecutionSubgraph::kMaxFilterableSuccessors);
+ std::vector<AdjacencyListGraph::Edge> edges;
+ for (const auto& mid : mid_blocks) {
+ edges.emplace_back("entry", mid);
+ edges.emplace_back(mid, "exit");
+ }
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry", "exit", edges));
+ ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
+ ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
+ esg.Finalize();
+ ASSERT_TRUE(esg.IsValid());
+ ASSERT_TRUE(IsValidSubgraph(esg));
+ std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
+ esg.ReachableBlocks().end());
+
+ for (const auto& mid : mid_blocks) {
+ EXPECT_TRUE(contents.find(blks.Get(mid)) != contents.end()) << mid;
+ }
+ // + 2 for entry and exit nodes.
+ ASSERT_EQ(contents.size(), ExecutionSubgraph::kMaxFilterableSuccessors + 2);
+}
+
+// Test with max number of successors and some removals.
+TEST_F(ExecutionSubgraphTest, BigNodesMissing) {
+ std::vector<std::string> mid_blocks;
+ for (auto i : Range(ExecutionSubgraph::kMaxFilterableSuccessors)) {
+ std::ostringstream oss;
+ oss << "blk" << i;
+ mid_blocks.push_back(oss.str());
+ }
+ std::vector<AdjacencyListGraph::Edge> edges;
+ for (const auto& mid : mid_blocks) {
+ edges.emplace_back("entry", mid);
+ edges.emplace_back(mid, "exit");
+ }
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry", "exit", edges));
+ ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
+ ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
+ esg.RemoveBlock(blks.Get("blk2"));
+ esg.RemoveBlock(blks.Get("blk4"));
+ esg.Finalize();
+ ASSERT_TRUE(esg.IsValid());
+ ASSERT_TRUE(IsValidSubgraph(esg));
+ std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
+ esg.ReachableBlocks().end());
+
+ ASSERT_EQ(contents.size(), ExecutionSubgraph::kMaxFilterableSuccessors + 2 - 2);
+
+ // Not present, no path through.
+ ASSERT_TRUE(contents.find(blks.Get("blk2")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("blk4")) == contents.end());
+}
+
+// Test with max number of successors and all successors removed.
+TEST_F(ExecutionSubgraphTest, BigNodesNoPath) {
+ std::vector<std::string> mid_blocks;
+ for (auto i : Range(ExecutionSubgraph::kMaxFilterableSuccessors)) {
+ std::ostringstream oss;
+ oss << "blk" << i;
+ mid_blocks.push_back(oss.str());
+ }
+ std::vector<AdjacencyListGraph::Edge> edges;
+ for (const auto& mid : mid_blocks) {
+ edges.emplace_back("entry", mid);
+ edges.emplace_back(mid, "exit");
+ }
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry", "exit", edges));
+ ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
+ ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
+ for (const auto& mid : mid_blocks) {
+ esg.RemoveBlock(blks.Get(mid));
+ }
+ esg.Finalize();
+ ASSERT_FALSE(esg.IsValid());
+ ASSERT_FALSE(IsValidSubgraph(esg));
+}
+
+// Test with max number of successors
+TEST_F(ExecutionSubgraphTest, CanAnalyseBig) {
+ // Make an absurdly huge and well connected graph. This should be pretty worst-case scenario.
+ constexpr size_t kNumBlocks = ExecutionSubgraph::kMaxFilterableSuccessors + 1000;
+ std::vector<std::string> mid_blocks;
+ for (auto i : Range(kNumBlocks)) {
+ std::ostringstream oss;
+ oss << "blk" << i;
+ mid_blocks.push_back(oss.str());
+ }
+ std::vector<AdjacencyListGraph::Edge> edges;
+ for (auto cur : Range(kNumBlocks)) {
+ for (auto nxt :
+ Range(cur + 1,
+ std::min(cur + ExecutionSubgraph::kMaxFilterableSuccessors + 1, kNumBlocks))) {
+ edges.emplace_back(mid_blocks[cur], mid_blocks[nxt]);
+ }
+ }
+ AdjacencyListGraph blks(SetupFromAdjacencyList(mid_blocks.front(), mid_blocks.back(), edges));
+ ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
+
+ ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
+ esg.Finalize();
+ ASSERT_TRUE(esg.IsValid());
+ ASSERT_TRUE(IsValidSubgraph(esg));
+ std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
+ esg.ReachableBlocks().end());
+
+ ASSERT_EQ(contents.size(), kNumBlocks);
+}
+
+// Test with many successors
+TEST_F(ExecutionSubgraphTest, CanAnalyseBig2) {
+ // Make an absurdly huge and well connected graph. This should be pretty worst-case scenario.
+ constexpr size_t kNumBlocks = ExecutionSubgraph::kMaxFilterableSuccessors + 1000;
+ constexpr size_t kTestMaxSuccessors = ExecutionSubgraph::kMaxFilterableSuccessors - 1;
+ std::vector<std::string> mid_blocks;
+ for (auto i : Range(kNumBlocks)) {
+ std::ostringstream oss;
+ oss << "blk" << i;
+ mid_blocks.push_back(oss.str());
+ }
+ std::vector<AdjacencyListGraph::Edge> edges;
+ for (auto cur : Range(kNumBlocks)) {
+ for (auto nxt : Range(cur + 1, std::min(cur + 1 + kTestMaxSuccessors, kNumBlocks))) {
+ edges.emplace_back(mid_blocks[cur], mid_blocks[nxt]);
+ }
+ }
+ edges.emplace_back(mid_blocks.front(), mid_blocks.back());
+ AdjacencyListGraph blks(SetupFromAdjacencyList(mid_blocks.front(), mid_blocks.back(), edges));
+ ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
+ ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
+ constexpr size_t kToRemoveIdx = kNumBlocks / 2;
+ HBasicBlock* remove_implicit = blks.Get(mid_blocks[kToRemoveIdx]);
+ for (HBasicBlock* pred : remove_implicit->GetPredecessors()) {
+ esg.RemoveBlock(pred);
+ }
+ esg.Finalize();
+ EXPECT_TRUE(esg.IsValid());
+ EXPECT_TRUE(IsValidSubgraph(esg));
+ std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
+ esg.ReachableBlocks().end());
+
+ // Only entry and exit. The middle ones should eliminate everything else.
+ EXPECT_EQ(contents.size(), 2u);
+ EXPECT_TRUE(contents.find(remove_implicit) == contents.end());
+ EXPECT_TRUE(contents.find(blks.Get(mid_blocks.front())) != contents.end());
+ EXPECT_TRUE(contents.find(blks.Get(mid_blocks.back())) != contents.end());
+}
+
+// Test with too many successors
+TEST_F(ExecutionSubgraphTest, CanNotAnalyseBig) {
+ std::vector<std::string> mid_blocks;
+ for (auto i : Range(ExecutionSubgraph::kMaxFilterableSuccessors + 4)) {
+ std::ostringstream oss;
+ oss << "blk" << i;
+ mid_blocks.push_back(oss.str());
+ }
+ std::vector<AdjacencyListGraph::Edge> edges;
+ for (const auto& mid : mid_blocks) {
+ edges.emplace_back("entry", mid);
+ edges.emplace_back(mid, "exit");
+ }
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry", "exit", edges));
+ ASSERT_FALSE(ExecutionSubgraph::CanAnalyse(graph_));
+}
+} // namespace art
diff --git a/compiler/optimizing/execution_subgraph_test.h b/compiler/optimizing/execution_subgraph_test.h
new file mode 100644
index 0000000..13cb2bc
--- /dev/null
+++ b/compiler/optimizing/execution_subgraph_test.h
@@ -0,0 +1,38 @@
+/*
+ * 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.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_EXECUTION_SUBGRAPH_TEST_H_
+#define ART_COMPILER_OPTIMIZING_EXECUTION_SUBGRAPH_TEST_H_
+
+#include "android-base/macros.h"
+
+namespace art {
+
+class HGraph;
+class ExecutionSubgraph;
+
+class ExecutionSubgraphTestHelper {
+ public:
+ static bool CalculateValidity(HGraph* graph, const ExecutionSubgraph* subgraph);
+
+ private:
+ ExecutionSubgraphTestHelper() = delete;
+
+ DISALLOW_COPY_AND_ASSIGN(ExecutionSubgraphTestHelper);
+};
+} // namespace art
+
+#endif // ART_COMPILER_OPTIMIZING_EXECUTION_SUBGRAPH_TEST_H_
diff --git a/compiler/optimizing/load_store_analysis.cc b/compiler/optimizing/load_store_analysis.cc
index 7a67fc5..3daa647 100644
--- a/compiler/optimizing/load_store_analysis.cc
+++ b/compiler/optimizing/load_store_analysis.cc
@@ -88,6 +88,94 @@
return CanIntegerRangesOverlap(l1, h1, l2, h2);
}
+// Make sure we mark any writes/potential writes to heap-locations within partially
+// escaped values as escaping.
+void ReferenceInfo::PrunePartialEscapeWrites() {
+ if (!subgraph_.IsValid()) {
+ // All paths escape.
+ return;
+ }
+ HGraph* graph = reference_->GetBlock()->GetGraph();
+ ArenaBitVector additional_exclusions(
+ allocator_, graph->GetBlocks().size(), false, kArenaAllocLSA);
+ for (const HUseListNode<HInstruction*>& use : reference_->GetUses()) {
+ const HInstruction* user = use.GetUser();
+ const bool possible_exclusion =
+ !additional_exclusions.IsBitSet(user->GetBlock()->GetBlockId()) &&
+ subgraph_.ContainsBlock(user->GetBlock());
+ const bool is_written_to =
+ (user->IsUnresolvedInstanceFieldSet() || user->IsUnresolvedStaticFieldSet() ||
+ user->IsInstanceFieldSet() || user->IsStaticFieldSet() || user->IsArraySet()) &&
+ (reference_ == user->InputAt(0));
+ if (possible_exclusion && is_written_to &&
+ std::any_of(subgraph_.UnreachableBlocks().begin(),
+ subgraph_.UnreachableBlocks().end(),
+ [&](const HBasicBlock* excluded) -> bool {
+ return reference_->GetBlock()->GetGraph()->PathBetween(excluded,
+ user->GetBlock());
+ })) {
+ // This object had memory written to it somewhere, if it escaped along
+ // some paths prior to the current block this write also counts as an
+ // escape.
+ additional_exclusions.SetBit(user->GetBlock()->GetBlockId());
+ }
+ }
+ if (UNLIKELY(additional_exclusions.IsAnyBitSet())) {
+ for (uint32_t exc : additional_exclusions.Indexes()) {
+ subgraph_.RemoveBlock(graph->GetBlocks()[exc]);
+ }
+ }
+}
+
+bool HeapLocationCollector::InstructionEligibleForLSERemoval(HInstruction* inst) const {
+ if (inst->IsNewInstance()) {
+ return !inst->AsNewInstance()->NeedsChecks();
+ } else if (inst->IsNewArray()) {
+ HInstruction* array_length = inst->AsNewArray()->GetLength();
+ bool known_array_length =
+ array_length->IsIntConstant() && array_length->AsIntConstant()->GetValue() >= 0;
+ return known_array_length &&
+ std::all_of(inst->GetUses().cbegin(),
+ inst->GetUses().cend(),
+ [&](const HUseListNode<HInstruction*>& user) {
+ if (user.GetUser()->IsArrayGet() || user.GetUser()->IsArraySet()) {
+ return user.GetUser()->InputAt(1)->IsIntConstant();
+ }
+ return true;
+ });
+ } else {
+ return false;
+ }
+}
+
+void HeapLocationCollector::DumpReferenceStats(OptimizingCompilerStats* stats) {
+ if (stats == nullptr) {
+ return;
+ }
+ std::vector<bool> seen_instructions(GetGraph()->GetCurrentInstructionId(), false);
+ for (auto hl : heap_locations_) {
+ auto ri = hl->GetReferenceInfo();
+ if (ri == nullptr || seen_instructions[ri->GetReference()->GetId()]) {
+ continue;
+ }
+ auto instruction = ri->GetReference();
+ seen_instructions[instruction->GetId()] = true;
+ if (ri->IsSingletonAndRemovable()) {
+ if (InstructionEligibleForLSERemoval(instruction)) {
+ MaybeRecordStat(stats, MethodCompilationStat::kFullLSEPossible);
+ }
+ }
+ // TODO This is an estimate of the number of allocations we will be able
+ // to (partially) remove. As additional work is done this can be refined.
+ if (ri->IsPartialSingleton() && instruction->IsNewInstance() &&
+ ri->GetNoEscapeSubgraph()->ContainsBlock(instruction->GetBlock()) &&
+ !ri->GetNoEscapeSubgraph()->GetExcludedCohorts().empty() &&
+ InstructionEligibleForLSERemoval(instruction)) {
+ MaybeRecordStat(stats, MethodCompilationStat::kPartialLSEPossible);
+ }
+ }
+}
+
bool HeapLocationCollector::CanArrayElementsAlias(const HInstruction* idx1,
const size_t vector_length1,
const HInstruction* idx2,
@@ -172,6 +260,7 @@
}
heap_location_collector_.BuildAliasingMatrix();
+ heap_location_collector_.DumpReferenceStats(stats_);
return true;
}
diff --git a/compiler/optimizing/load_store_analysis.h b/compiler/optimizing/load_store_analysis.h
index 882fe28..5d2d841 100644
--- a/compiler/optimizing/load_store_analysis.h
+++ b/compiler/optimizing/load_store_analysis.h
@@ -17,29 +17,61 @@
#ifndef ART_COMPILER_OPTIMIZING_LOAD_STORE_ANALYSIS_H_
#define ART_COMPILER_OPTIMIZING_LOAD_STORE_ANALYSIS_H_
+#include "base/arena_allocator.h"
+#include "base/arena_bit_vector.h"
#include "base/bit_vector-inl.h"
+#include "base/scoped_arena_allocator.h"
#include "base/scoped_arena_containers.h"
+#include "base/stl_util.h"
#include "escape.h"
+#include "execution_subgraph.h"
#include "nodes.h"
-#include "optimization.h"
+#include "optimizing/optimizing_compiler_stats.h"
namespace art {
// A ReferenceInfo contains additional info about a reference such as
// whether it's a singleton, returned, etc.
-class ReferenceInfo : public ArenaObject<kArenaAllocLSA> {
+class ReferenceInfo : public DeletableArenaObject<kArenaAllocLSA> {
public:
- ReferenceInfo(HInstruction* reference, size_t pos)
+ ReferenceInfo(HInstruction* reference,
+ ScopedArenaAllocator* allocator,
+ size_t pos,
+ bool for_partial_elimination)
: reference_(reference),
position_(pos),
is_singleton_(true),
is_singleton_and_not_returned_(true),
- is_singleton_and_not_deopt_visible_(true) {
+ is_singleton_and_not_deopt_visible_(true),
+ allocator_(allocator),
+ subgraph_(reference->GetBlock()->GetGraph(), for_partial_elimination, allocator_) {
+ // TODO We can do this in one pass.
+ // TODO NewArray is possible but will need to get a handle on how to deal with the dynamic loads
+ // for now just ignore it.
+ bool can_be_partial =
+ for_partial_elimination && (/* reference_->IsNewArray() || */ reference_->IsNewInstance());
+ LambdaEscapeVisitor func([&](HInstruction* inst) { return HandleEscape(inst); });
+ if (can_be_partial) {
+ VisitEscapes(reference_, func);
+ }
CalculateEscape(reference_,
nullptr,
&is_singleton_,
&is_singleton_and_not_returned_,
&is_singleton_and_not_deopt_visible_);
+ if (can_be_partial) {
+ // This is to mark writes to partially escaped values as also part of the escaped subset.
+ // TODO We can avoid this if we have a 'ConditionalWrite' instruction. Will require testing
+ // to see if the additional branches are worth it.
+ PrunePartialEscapeWrites();
+ subgraph_.Finalize();
+ } else {
+ subgraph_.Invalidate();
+ }
+ }
+
+ const ExecutionSubgraph* GetNoEscapeSubgraph() const {
+ return &subgraph_;
}
HInstruction* GetReference() const {
@@ -57,6 +89,14 @@
return is_singleton_;
}
+ // This is a singleton and there are paths that don't escape the method
+ bool IsPartialSingleton() const {
+ auto ref = GetReference();
+ // TODO NewArray is possible but will need to get a handle on how to deal with the dynamic loads
+ // for now just ignore it.
+ return (/* ref->IsNewArray() || */ ref->IsNewInstance()) && GetNoEscapeSubgraph()->IsValid();
+ }
+
// Returns true if reference_ is a singleton and not returned to the caller or
// used as an environment local of an HDeoptimize instruction.
// The allocation and stores into reference_ may be eliminated for such cases.
@@ -72,6 +112,15 @@
}
private:
+ bool HandleEscape(HInstruction* escape) {
+ subgraph_.RemoveBlock(escape->GetBlock());
+ return true;
+ }
+
+ // Make sure we mark any writes/potential writes to heap-locations within partially
+ // escaped values as escaping.
+ void PrunePartialEscapeWrites();
+
HInstruction* const reference_;
const size_t position_; // position in HeapLocationCollector's ref_info_array_.
@@ -82,6 +131,10 @@
// Is singleton and not used as an environment local of HDeoptimize.
bool is_singleton_and_not_deopt_visible_;
+ ScopedArenaAllocator* allocator_;
+
+ ExecutionSubgraph subgraph_;
+
DISALLOW_COPY_AND_ASSIGN(ReferenceInfo);
};
@@ -174,23 +227,28 @@
// aliasing matrix of 8 heap locations.
static constexpr uint32_t kInitialAliasingMatrixBitVectorSize = 32;
- explicit HeapLocationCollector(HGraph* graph, ScopedArenaAllocator* allocator)
+ HeapLocationCollector(HGraph* graph,
+ ScopedArenaAllocator* allocator,
+ bool for_partial_elimination)
: HGraphVisitor(graph),
allocator_(allocator),
ref_info_array_(allocator->Adapter(kArenaAllocLSA)),
heap_locations_(allocator->Adapter(kArenaAllocLSA)),
- aliasing_matrix_(allocator,
- kInitialAliasingMatrixBitVectorSize,
- true,
- kArenaAllocLSA),
+ aliasing_matrix_(allocator, kInitialAliasingMatrixBitVectorSize, true, kArenaAllocLSA),
has_heap_stores_(false),
has_volatile_(false),
- has_monitor_operations_(false) {
+ has_monitor_operations_(false),
+ for_partial_elimination_(for_partial_elimination) {
aliasing_matrix_.ClearAllBits();
}
+ ~HeapLocationCollector() {
+ CleanUp();
+ }
+
void CleanUp() {
heap_locations_.clear();
+ STLDeleteContainerPointers(ref_info_array_.begin(), ref_info_array_.end());
ref_info_array_.clear();
}
@@ -303,6 +361,11 @@
return kHeapLocationNotFound;
}
+ bool InstructionEligibleForLSERemoval(HInstruction* inst) const;
+
+ // Get some estimated statistics based on our analysis.
+ void DumpReferenceStats(OptimizingCompilerStats* stats);
+
// Returns true if heap_locations_[index1] and heap_locations_[index2] may alias.
bool MayAlias(size_t index1, size_t index2) const {
if (index1 < index2) {
@@ -417,7 +480,8 @@
ReferenceInfo* ref_info = FindReferenceInfoOf(instruction);
if (ref_info == nullptr) {
size_t pos = ref_info_array_.size();
- ref_info = new (allocator_) ReferenceInfo(instruction, pos);
+ ref_info =
+ new (allocator_) ReferenceInfo(instruction, allocator_, pos, for_partial_elimination_);
ref_info_array_.push_back(ref_info);
}
return ref_info;
@@ -554,15 +618,25 @@
// alias analysis and won't be as effective.
bool has_volatile_; // If there are volatile field accesses.
bool has_monitor_operations_; // If there are monitor operations.
+ bool for_partial_elimination_;
DISALLOW_COPY_AND_ASSIGN(HeapLocationCollector);
};
class LoadStoreAnalysis {
public:
- explicit LoadStoreAnalysis(HGraph* graph, ScopedArenaAllocator* local_allocator)
- : graph_(graph),
- heap_location_collector_(graph, local_allocator) {}
+ // for_elimination controls whether we should keep track of escapes at a per-block level for
+ // partial LSE.
+ explicit LoadStoreAnalysis(HGraph* graph,
+ OptimizingCompilerStats* stats,
+ ScopedArenaAllocator* local_allocator,
+ bool for_elimination = true)
+ : graph_(graph),
+ stats_(stats),
+ heap_location_collector_(
+ graph,
+ local_allocator,
+ /*for_partial_elimination=*/for_elimination && ExecutionSubgraph::CanAnalyse(graph_)) {}
const HeapLocationCollector& GetHeapLocationCollector() const {
return heap_location_collector_;
@@ -572,6 +646,7 @@
private:
HGraph* graph_;
+ OptimizingCompilerStats* stats_;
HeapLocationCollector heap_location_collector_;
DISALLOW_COPY_AND_ASSIGN(LoadStoreAnalysis);
diff --git a/compiler/optimizing/load_store_analysis_test.cc b/compiler/optimizing/load_store_analysis_test.cc
index c518f03..2284811 100644
--- a/compiler/optimizing/load_store_analysis_test.cc
+++ b/compiler/optimizing/load_store_analysis_test.cc
@@ -15,16 +15,49 @@
*/
#include "load_store_analysis.h"
-#include "nodes.h"
-#include "optimizing_unit_test.h"
+#include <array>
+#include <string_view>
+#include <unordered_map>
+#include <unordered_set>
+
+#include "base/scoped_arena_allocator.h"
+#include "class_root.h"
+#include "dex/dex_file_types.h"
+#include "dex/method_reference.h"
+#include "entrypoints/quick/quick_entrypoints_enum.h"
+#include "execution_subgraph.h"
+#include "execution_subgraph_test.h"
#include "gtest/gtest.h"
+#include "handle.h"
+#include "handle_scope.h"
+#include "nodes.h"
+#include "optimizing/data_type.h"
+#include "optimizing_unit_test.h"
+#include "scoped_thread_state_change.h"
namespace art {
class LoadStoreAnalysisTest : public OptimizingUnitTest {
public:
- LoadStoreAnalysisTest() : graph_(CreateGraph()) { }
+ LoadStoreAnalysisTest() : graph_(CreateGraph()) {}
+
+ AdjacencyListGraph SetupFromAdjacencyList(
+ const std::string_view entry_name,
+ const std::string_view exit_name,
+ const std::vector<AdjacencyListGraph::Edge>& adj) {
+ return AdjacencyListGraph(graph_, GetAllocator(), entry_name, exit_name, adj);
+ }
+
+ bool IsValidSubgraph(const ExecutionSubgraph* esg) {
+ return ExecutionSubgraphTestHelper::CalculateValidity(graph_, esg);
+ }
+
+ bool IsValidSubgraph(const ExecutionSubgraph& esg) {
+ return ExecutionSubgraphTestHelper::CalculateValidity(graph_, &esg);
+ }
+ void CheckReachability(const AdjacencyListGraph& adj,
+ const std::vector<AdjacencyListGraph::Edge>& reach);
HGraph* graph_;
};
@@ -67,7 +100,8 @@
// Test HeapLocationCollector initialization.
// Should be no heap locations, no operations on the heap.
ScopedArenaAllocator allocator(graph_->GetArenaStack());
- HeapLocationCollector heap_location_collector(graph_, &allocator);
+ HeapLocationCollector heap_location_collector(
+ graph_, &allocator, /*for_partial_elimination=*/true);
ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 0U);
ASSERT_FALSE(heap_location_collector.HasHeapStores());
@@ -164,7 +198,8 @@
// Test HeapLocationCollector initialization.
// Should be no heap locations, no operations on the heap.
ScopedArenaAllocator allocator(graph_->GetArenaStack());
- HeapLocationCollector heap_location_collector(graph_, &allocator);
+ HeapLocationCollector heap_location_collector(
+ graph_, &allocator, /*for_partial_elimination=*/true);
ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 0U);
ASSERT_FALSE(heap_location_collector.HasHeapStores());
@@ -244,7 +279,7 @@
entry->AddInstruction(arr_set8); // array[i-(-1)] = c0
ScopedArenaAllocator allocator(graph_->GetArenaStack());
- LoadStoreAnalysis lsa(graph_, &allocator);
+ LoadStoreAnalysis lsa(graph_, nullptr, &allocator, /*for_elimination=*/false);
lsa.Run();
const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
@@ -411,7 +446,7 @@
entry->AddInstruction(vstore_i_add6_vlen2);
ScopedArenaAllocator allocator(graph_->GetArenaStack());
- LoadStoreAnalysis lsa(graph_, &allocator);
+ LoadStoreAnalysis lsa(graph_, nullptr, &allocator, /*for_elimination=*/false);
lsa.Run();
const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
@@ -570,7 +605,7 @@
entry->AddInstruction(arr_set_8);
ScopedArenaAllocator allocator(graph_->GetArenaStack());
- LoadStoreAnalysis lsa(graph_, &allocator);
+ LoadStoreAnalysis lsa(graph_, nullptr, &allocator, /*for_elimination=*/false);
lsa.Run();
const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
@@ -660,7 +695,8 @@
entry->AddInstruction(array_get4);
ScopedArenaAllocator allocator(graph_->GetArenaStack());
- HeapLocationCollector heap_location_collector(graph_, &allocator);
+ HeapLocationCollector heap_location_collector(
+ graph_, &allocator, /*for_partial_elimination=*/true);
heap_location_collector.VisitBasicBlock(entry);
// Test that the HeapLocationCollector should be able to tell
@@ -678,4 +714,975 @@
ASSERT_EQ(loc1, loc4);
}
+void LoadStoreAnalysisTest::CheckReachability(const AdjacencyListGraph& adj,
+ const std::vector<AdjacencyListGraph::Edge>& reach) {
+ uint32_t cnt = 0;
+ for (HBasicBlock* blk : graph_->GetBlocks()) {
+ if (adj.HasBlock(blk)) {
+ for (HBasicBlock* other : graph_->GetBlocks()) {
+ if (other == nullptr) {
+ continue;
+ }
+ if (adj.HasBlock(other)) {
+ bool contains_edge =
+ std::find(reach.begin(),
+ reach.end(),
+ AdjacencyListGraph::Edge { adj.GetName(blk), adj.GetName(other) }) !=
+ reach.end();
+ if (graph_->PathBetween(blk, other)) {
+ cnt++;
+ EXPECT_TRUE(contains_edge) << "Unexpected edge found between " << adj.GetName(blk)
+ << " and " << adj.GetName(other);
+ } else {
+ EXPECT_FALSE(contains_edge) << "Expected edge not found between " << adj.GetName(blk)
+ << " and " << adj.GetName(other);
+ }
+ } else if (graph_->PathBetween(blk, other)) {
+ ADD_FAILURE() << "block " << adj.GetName(blk)
+ << " has path to non-adjacency-graph block id: " << other->GetBlockId();
+ }
+ }
+ } else {
+ for (HBasicBlock* other : graph_->GetBlocks()) {
+ if (other == nullptr) {
+ continue;
+ }
+ EXPECT_FALSE(graph_->PathBetween(blk, other))
+ << "Reachable blocks outside of adjacency-list";
+ }
+ }
+ }
+ EXPECT_EQ(cnt, reach.size());
+}
+
+TEST_F(LoadStoreAnalysisTest, ReachabilityTest1) {
+ AdjacencyListGraph blks(SetupFromAdjacencyList(
+ "entry",
+ "exit",
+ { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
+ CheckReachability(blks,
+ {
+ { "entry", "left" },
+ { "entry", "right" },
+ { "entry", "exit" },
+ { "right", "exit" },
+ { "left", "exit" },
+ });
+}
+
+TEST_F(LoadStoreAnalysisTest, ReachabilityTest2) {
+ AdjacencyListGraph blks(SetupFromAdjacencyList(
+ "entry",
+ "exit",
+ { { "entry", "loop-header" }, { "loop-header", "loop" }, { "loop", "loop-header" } }));
+ CheckReachability(blks,
+ {
+ { "entry", "loop-header" },
+ { "entry", "loop" },
+ { "loop-header", "loop-header" },
+ { "loop-header", "loop" },
+ { "loop", "loop-header" },
+ { "loop", "loop" },
+ });
+}
+
+TEST_F(LoadStoreAnalysisTest, ReachabilityTest3) {
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
+ "exit",
+ { { "entry", "loop-header" },
+ { "loop-header", "loop" },
+ { "loop", "loop-header" },
+ { "entry", "right" },
+ { "right", "exit" } }));
+ CheckReachability(blks,
+ {
+ { "entry", "loop-header" },
+ { "entry", "loop" },
+ { "entry", "right" },
+ { "entry", "exit" },
+ { "loop-header", "loop-header" },
+ { "loop-header", "loop" },
+ { "loop", "loop-header" },
+ { "loop", "loop" },
+ { "right", "exit" },
+ });
+}
+
+static bool AreExclusionsIndependent(HGraph* graph, const ExecutionSubgraph* esg) {
+ auto excluded = esg->GetExcludedCohorts();
+ if (excluded.size() < 2) {
+ return true;
+ }
+ for (auto first = excluded.begin(); first != excluded.end(); ++first) {
+ for (auto second = excluded.begin(); second != excluded.end(); ++second) {
+ if (first == second) {
+ continue;
+ }
+ for (const HBasicBlock* entry : first->EntryBlocks()) {
+ for (const HBasicBlock* exit : second->ExitBlocks()) {
+ if (graph->PathBetween(exit, entry)) {
+ return false;
+ }
+ }
+ }
+ }
+ }
+ return true;
+}
+
+// // ENTRY
+// obj = new Obj();
+// if (parameter_value) {
+// // LEFT
+// call_func(obj);
+// } else {
+// // RIGHT
+// obj.field = 1;
+// }
+// // EXIT
+// obj.field;
+TEST_F(LoadStoreAnalysisTest, PartialEscape) {
+ AdjacencyListGraph blks(SetupFromAdjacencyList(
+ "entry",
+ "exit",
+ { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
+ HBasicBlock* entry = blks.Get("entry");
+ HBasicBlock* left = blks.Get("left");
+ HBasicBlock* right = blks.Get("right");
+ HBasicBlock* exit = blks.Get("exit");
+
+ HInstruction* bool_value = new (GetAllocator())
+ HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ ScopedNullHandle<mirror::Class>(),
+ false,
+ 0,
+ false);
+ HInstruction* new_inst =
+ new (GetAllocator()) HNewInstance(cls,
+ 0,
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ false,
+ QuickEntrypointEnum::kQuickAllocObjectInitialized);
+ HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
+ entry->AddInstruction(bool_value);
+ entry->AddInstruction(cls);
+ entry->AddInstruction(new_inst);
+ entry->AddInstruction(if_inst);
+
+ HInstruction* call_left = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 1,
+ DataType::Type::kVoid,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* goto_left = new (GetAllocator()) HGoto();
+ call_left->AsInvoke()->SetRawInputAt(0, new_inst);
+ left->AddInstruction(call_left);
+ left->AddInstruction(goto_left);
+
+ HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c0,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_right = new (GetAllocator()) HGoto();
+ right->AddInstruction(write_right);
+ right->AddInstruction(goto_right);
+
+ HInstruction* read_final = new (GetAllocator()) HInstanceFieldGet(new_inst,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ exit->AddInstruction(read_final);
+
+ ScopedArenaAllocator allocator(graph_->GetArenaStack());
+ LoadStoreAnalysis lsa(graph_, nullptr, &allocator, /*for_elimination=*/true);
+ lsa.Run();
+
+ const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
+ ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
+ const ExecutionSubgraph* esg = info->GetNoEscapeSubgraph();
+
+ ASSERT_TRUE(esg->IsValid());
+ ASSERT_TRUE(IsValidSubgraph(esg));
+ ASSERT_TRUE(AreExclusionsIndependent(graph_, esg));
+ std::unordered_set<const HBasicBlock*> contents(esg->ReachableBlocks().begin(),
+ esg->ReachableBlocks().end());
+
+ ASSERT_EQ(contents.size(), 3u);
+ ASSERT_TRUE(contents.find(blks.Get("left")) == contents.end());
+
+ ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
+}
+
+// // ENTRY
+// obj = new Obj();
+// if (parameter_value) {
+// // LEFT
+// call_func(obj);
+// } else {
+// // RIGHT
+// obj.field = 1;
+// }
+// // EXIT
+// obj.field2;
+TEST_F(LoadStoreAnalysisTest, PartialEscape2) {
+ AdjacencyListGraph blks(SetupFromAdjacencyList(
+ "entry",
+ "exit",
+ { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
+ HBasicBlock* entry = blks.Get("entry");
+ HBasicBlock* left = blks.Get("left");
+ HBasicBlock* right = blks.Get("right");
+ HBasicBlock* exit = blks.Get("exit");
+
+ HInstruction* bool_value = new (GetAllocator())
+ HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ ScopedNullHandle<mirror::Class>(),
+ false,
+ 0,
+ false);
+ HInstruction* new_inst =
+ new (GetAllocator()) HNewInstance(cls,
+ 0,
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ false,
+ QuickEntrypointEnum::kQuickAllocObjectInitialized);
+ HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
+ entry->AddInstruction(bool_value);
+ entry->AddInstruction(cls);
+ entry->AddInstruction(new_inst);
+ entry->AddInstruction(if_inst);
+
+ HInstruction* call_left = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 1,
+ DataType::Type::kVoid,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* goto_left = new (GetAllocator()) HGoto();
+ call_left->AsInvoke()->SetRawInputAt(0, new_inst);
+ left->AddInstruction(call_left);
+ left->AddInstruction(goto_left);
+
+ HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c0,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_right = new (GetAllocator()) HGoto();
+ right->AddInstruction(write_right);
+ right->AddInstruction(goto_right);
+
+ HInstruction* read_final = new (GetAllocator()) HInstanceFieldGet(new_inst,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(16),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ exit->AddInstruction(read_final);
+
+ ScopedArenaAllocator allocator(graph_->GetArenaStack());
+ LoadStoreAnalysis lsa(graph_, nullptr, &allocator, /*for_elimination=*/true);
+ lsa.Run();
+
+ const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
+ ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
+ const ExecutionSubgraph* esg = info->GetNoEscapeSubgraph();
+
+ ASSERT_TRUE(esg->IsValid());
+ ASSERT_TRUE(IsValidSubgraph(esg));
+ ASSERT_TRUE(AreExclusionsIndependent(graph_, esg));
+ std::unordered_set<const HBasicBlock*> contents(esg->ReachableBlocks().begin(),
+ esg->ReachableBlocks().end());
+
+ ASSERT_EQ(contents.size(), 3u);
+ ASSERT_TRUE(contents.find(blks.Get("left")) == contents.end());
+
+ ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
+}
+
+// // ENTRY
+// obj = new Obj();
+// obj.field = 10;
+// if (parameter_value) {
+// // LEFT
+// call_func(obj);
+// } else {
+// // RIGHT
+// obj.field = 20;
+// }
+// // EXIT
+// obj.field;
+TEST_F(LoadStoreAnalysisTest, PartialEscape3) {
+ AdjacencyListGraph blks(SetupFromAdjacencyList(
+ "entry",
+ "exit",
+ { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
+ HBasicBlock* entry = blks.Get("entry");
+ HBasicBlock* left = blks.Get("left");
+ HBasicBlock* right = blks.Get("right");
+ HBasicBlock* exit = blks.Get("exit");
+
+ HInstruction* bool_value = new (GetAllocator())
+ HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
+ HInstruction* c10 = graph_->GetIntConstant(10);
+ HInstruction* c20 = graph_->GetIntConstant(20);
+ HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ ScopedNullHandle<mirror::Class>(),
+ false,
+ 0,
+ false);
+ HInstruction* new_inst =
+ new (GetAllocator()) HNewInstance(cls,
+ 0,
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ false,
+ QuickEntrypointEnum::kQuickAllocObjectInitialized);
+
+ HInstruction* write_entry = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c10,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
+ entry->AddInstruction(bool_value);
+ entry->AddInstruction(cls);
+ entry->AddInstruction(new_inst);
+ entry->AddInstruction(write_entry);
+ entry->AddInstruction(if_inst);
+
+ HInstruction* call_left = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 1,
+ DataType::Type::kVoid,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* goto_left = new (GetAllocator()) HGoto();
+ call_left->AsInvoke()->SetRawInputAt(0, new_inst);
+ left->AddInstruction(call_left);
+ left->AddInstruction(goto_left);
+
+ HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c20,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_right = new (GetAllocator()) HGoto();
+ right->AddInstruction(write_right);
+ right->AddInstruction(goto_right);
+
+ HInstruction* read_final = new (GetAllocator()) HInstanceFieldGet(new_inst,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ exit->AddInstruction(read_final);
+
+ ScopedArenaAllocator allocator(graph_->GetArenaStack());
+ LoadStoreAnalysis lsa(graph_, nullptr, &allocator, /*for_elimination=*/true);
+ lsa.Run();
+
+ const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
+ ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
+ const ExecutionSubgraph* esg = info->GetNoEscapeSubgraph();
+
+ ASSERT_TRUE(esg->IsValid());
+ ASSERT_TRUE(IsValidSubgraph(esg));
+ ASSERT_TRUE(AreExclusionsIndependent(graph_, esg));
+ std::unordered_set<const HBasicBlock*> contents(esg->ReachableBlocks().begin(),
+ esg->ReachableBlocks().end());
+
+ ASSERT_EQ(contents.size(), 3u);
+ ASSERT_TRUE(contents.find(blks.Get("left")) == contents.end());
+
+ ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
+}
+
+// // ENTRY
+// obj = new Obj();
+// if (parameter_value) {
+// // LEFT
+// call_func(obj);
+// } else {
+// // RIGHT
+// obj.f1 = 0;
+// }
+// // EXIT
+// // call_func prevents the elimination of this store.
+// obj.f2 = 0;
+TEST_F(LoadStoreAnalysisTest, TotalEscapeAdjacent) {
+ AdjacencyListGraph blks(SetupFromAdjacencyList(
+ "entry",
+ "exit",
+ { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
+ HBasicBlock* entry = blks.Get("entry");
+ HBasicBlock* left = blks.Get("left");
+ HBasicBlock* right = blks.Get("right");
+ HBasicBlock* exit = blks.Get("exit");
+
+ HInstruction* bool_value = new (GetAllocator())
+ HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ ScopedNullHandle<mirror::Class>(),
+ false,
+ 0,
+ false);
+ HInstruction* new_inst =
+ new (GetAllocator()) HNewInstance(cls,
+ 0,
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ false,
+ QuickEntrypointEnum::kQuickAllocObjectInitialized);
+ HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
+ entry->AddInstruction(bool_value);
+ entry->AddInstruction(cls);
+ entry->AddInstruction(new_inst);
+ entry->AddInstruction(if_inst);
+
+ HInstruction* call_left = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 1,
+ DataType::Type::kVoid,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* goto_left = new (GetAllocator()) HGoto();
+ call_left->AsInvoke()->SetRawInputAt(0, new_inst);
+ left->AddInstruction(call_left);
+ left->AddInstruction(goto_left);
+
+ HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c0,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_right = new (GetAllocator()) HGoto();
+ right->AddInstruction(write_right);
+ right->AddInstruction(goto_right);
+
+ HInstruction* write_final = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c0,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(16),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ exit->AddInstruction(write_final);
+
+ ScopedArenaAllocator allocator(graph_->GetArenaStack());
+ LoadStoreAnalysis lsa(graph_, nullptr, &allocator, /*for_elimination=*/true);
+ lsa.Run();
+
+ const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
+ ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
+ const ExecutionSubgraph* esg = info->GetNoEscapeSubgraph();
+
+ ASSERT_FALSE(esg->IsValid()) << esg->GetExcludedCohorts();
+ ASSERT_FALSE(IsValidSubgraph(esg));
+ std::unordered_set<const HBasicBlock*> contents(esg->ReachableBlocks().begin(),
+ esg->ReachableBlocks().end());
+
+ ASSERT_EQ(contents.size(), 0u);
+ ASSERT_TRUE(contents.find(blks.Get("left")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("right")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("entry")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("exit")) == contents.end());
+}
+
+// // ENTRY
+// obj = new Obj();
+// if (parameter_value) {
+// // LEFT
+// call_func(obj);
+// } else {
+// // RIGHT
+// obj.f0 = 0;
+// call_func2(obj);
+// }
+// // EXIT
+// obj.f0;
+TEST_F(LoadStoreAnalysisTest, TotalEscape) {
+ AdjacencyListGraph blks(SetupFromAdjacencyList(
+ "entry",
+ "exit",
+ { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
+ HBasicBlock* entry = blks.Get("entry");
+ HBasicBlock* left = blks.Get("left");
+ HBasicBlock* right = blks.Get("right");
+ HBasicBlock* exit = blks.Get("exit");
+
+ HInstruction* bool_value = new (GetAllocator())
+ HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ ScopedNullHandle<mirror::Class>(),
+ false,
+ 0,
+ false);
+ HInstruction* new_inst =
+ new (GetAllocator()) HNewInstance(cls,
+ 0,
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ false,
+ QuickEntrypointEnum::kQuickAllocObjectInitialized);
+ HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
+ entry->AddInstruction(bool_value);
+ entry->AddInstruction(cls);
+ entry->AddInstruction(new_inst);
+ entry->AddInstruction(if_inst);
+
+ HInstruction* call_left = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 1,
+ DataType::Type::kVoid,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* goto_left = new (GetAllocator()) HGoto();
+ call_left->AsInvoke()->SetRawInputAt(0, new_inst);
+ left->AddInstruction(call_left);
+ left->AddInstruction(goto_left);
+
+ HInstruction* call_right = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 1,
+ DataType::Type::kVoid,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c0,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_right = new (GetAllocator()) HGoto();
+ call_right->AsInvoke()->SetRawInputAt(0, new_inst);
+ right->AddInstruction(write_right);
+ right->AddInstruction(call_right);
+ right->AddInstruction(goto_right);
+
+ HInstruction* read_final = new (GetAllocator()) HInstanceFieldGet(new_inst,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ exit->AddInstruction(read_final);
+
+ ScopedArenaAllocator allocator(graph_->GetArenaStack());
+ LoadStoreAnalysis lsa(graph_, nullptr, &allocator, /*for_elimination=*/true);
+ lsa.Run();
+
+ const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
+ ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
+ const ExecutionSubgraph* esg = info->GetNoEscapeSubgraph();
+
+ ASSERT_FALSE(esg->IsValid());
+ ASSERT_FALSE(IsValidSubgraph(esg));
+ std::unordered_set<const HBasicBlock*> contents(esg->ReachableBlocks().begin(),
+ esg->ReachableBlocks().end());
+
+ ASSERT_EQ(contents.size(), 0u);
+ ASSERT_TRUE(contents.find(blks.Get("left")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("right")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("entry")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("exit")) == contents.end());
+}
+
+// // ENTRY
+// obj = new Obj();
+// obj.foo = 0;
+// // EXIT
+// return obj;
+TEST_F(LoadStoreAnalysisTest, TotalEscape2) {
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry", "exit", { { "entry", "exit" } }));
+ HBasicBlock* entry = blks.Get("entry");
+ HBasicBlock* exit = blks.Get("exit");
+
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ ScopedNullHandle<mirror::Class>(),
+ false,
+ 0,
+ false);
+ HInstruction* new_inst =
+ new (GetAllocator()) HNewInstance(cls,
+ 0,
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ false,
+ QuickEntrypointEnum::kQuickAllocObjectInitialized);
+
+ HInstruction* write_start = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c0,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_inst = new (GetAllocator()) HGoto();
+ entry->AddInstruction(cls);
+ entry->AddInstruction(new_inst);
+ entry->AddInstruction(write_start);
+ entry->AddInstruction(goto_inst);
+
+ HInstruction* return_final = new (GetAllocator()) HReturn(new_inst);
+ exit->AddInstruction(return_final);
+
+ ScopedArenaAllocator allocator(graph_->GetArenaStack());
+ LoadStoreAnalysis lsa(graph_, nullptr, &allocator, /*for_elimination=*/true);
+ lsa.Run();
+
+ const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
+ ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
+ const ExecutionSubgraph* esg = info->GetNoEscapeSubgraph();
+
+ ASSERT_FALSE(esg->IsValid());
+ ASSERT_FALSE(IsValidSubgraph(esg));
+ std::unordered_set<const HBasicBlock*> contents(esg->ReachableBlocks().begin(),
+ esg->ReachableBlocks().end());
+
+ ASSERT_EQ(contents.size(), 0u);
+ ASSERT_TRUE(contents.find(blks.Get("entry")) == contents.end());
+ ASSERT_TRUE(contents.find(blks.Get("exit")) == contents.end());
+}
+
+// // ENTRY
+// obj = new Obj();
+// if (parameter_value) {
+// // HIGH_LEFT
+// call_func(obj);
+// } else {
+// // HIGH_RIGHT
+// obj.f0 = 1;
+// }
+// // MID
+// obj.f0 *= 2;
+// if (parameter_value2) {
+// // LOW_LEFT
+// call_func(obj);
+// } else {
+// // LOW_RIGHT
+// obj.f0 = 1;
+// }
+// // EXIT
+// obj.f0
+TEST_F(LoadStoreAnalysisTest, DoubleDiamondEscape) {
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
+ "exit",
+ { { "entry", "high_left" },
+ { "entry", "high_right" },
+ { "low_left", "exit" },
+ { "low_right", "exit" },
+ { "high_right", "mid" },
+ { "high_left", "mid" },
+ { "mid", "low_left" },
+ { "mid", "low_right" } }));
+ HBasicBlock* entry = blks.Get("entry");
+ HBasicBlock* high_left = blks.Get("high_left");
+ HBasicBlock* high_right = blks.Get("high_right");
+ HBasicBlock* mid = blks.Get("mid");
+ HBasicBlock* low_left = blks.Get("low_left");
+ HBasicBlock* low_right = blks.Get("low_right");
+ HBasicBlock* exit = blks.Get("exit");
+
+ HInstruction* bool_value1 = new (GetAllocator())
+ HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
+ HInstruction* bool_value2 = new (GetAllocator())
+ HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 2, DataType::Type::kBool);
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* c2 = graph_->GetIntConstant(2);
+ HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ ScopedNullHandle<mirror::Class>(),
+ false,
+ 0,
+ false);
+ HInstruction* new_inst =
+ new (GetAllocator()) HNewInstance(cls,
+ 0,
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ false,
+ QuickEntrypointEnum::kQuickAllocObjectInitialized);
+ HInstruction* if_inst = new (GetAllocator()) HIf(bool_value1);
+ entry->AddInstruction(bool_value1);
+ entry->AddInstruction(bool_value2);
+ entry->AddInstruction(cls);
+ entry->AddInstruction(new_inst);
+ entry->AddInstruction(if_inst);
+
+ HInstruction* call_left = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 1,
+ DataType::Type::kVoid,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* goto_left = new (GetAllocator()) HGoto();
+ call_left->AsInvoke()->SetRawInputAt(0, new_inst);
+ high_left->AddInstruction(call_left);
+ high_left->AddInstruction(goto_left);
+
+ HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c0,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_right = new (GetAllocator()) HGoto();
+ high_right->AddInstruction(write_right);
+ high_right->AddInstruction(goto_right);
+
+ HInstruction* read_mid = new (GetAllocator()) HInstanceFieldGet(new_inst,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* mul_mid = new (GetAllocator()) HMul(DataType::Type::kInt32, read_mid, c2);
+ HInstruction* write_mid = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ mul_mid,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* if_mid = new (GetAllocator()) HIf(bool_value2);
+ mid->AddInstruction(read_mid);
+ mid->AddInstruction(mul_mid);
+ mid->AddInstruction(write_mid);
+ mid->AddInstruction(if_mid);
+
+ HInstruction* call_low_left = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 1,
+ DataType::Type::kVoid,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* goto_low_left = new (GetAllocator()) HGoto();
+ call_low_left->AsInvoke()->SetRawInputAt(0, new_inst);
+ low_left->AddInstruction(call_low_left);
+ low_left->AddInstruction(goto_low_left);
+
+ HInstruction* write_low_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c0,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_low_right = new (GetAllocator()) HGoto();
+ low_right->AddInstruction(write_low_right);
+ low_right->AddInstruction(goto_low_right);
+
+ HInstruction* read_final = new (GetAllocator()) HInstanceFieldGet(new_inst,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ exit->AddInstruction(read_final);
+
+ ScopedArenaAllocator allocator(graph_->GetArenaStack());
+ LoadStoreAnalysis lsa(graph_, nullptr, &allocator, /*for_elimination=*/true);
+ lsa.Run();
+
+ const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
+ ReferenceInfo* info = heap_location_collector.FindReferenceInfoOf(new_inst);
+ const ExecutionSubgraph* esg = info->GetNoEscapeSubgraph();
+
+ ASSERT_FALSE(esg->IsValid());
+ ASSERT_FALSE(IsValidSubgraph(esg));
+ std::unordered_set<const HBasicBlock*> contents(esg->ReachableBlocks().begin(),
+ esg->ReachableBlocks().end());
+
+ ASSERT_EQ(contents.size(), 0u);
+}
+
+// ┌───────┐ ┌────────────┐
+// ┌─ │ right │ ◀── │ entry │
+// │ └───────┘ └────────────┘
+// │ │
+// │ │
+// │ ▼
+// │ ┌────────────┐
+// │ │ esc_top │
+// │ └────────────┘
+// │ │
+// │ │
+// │ ▼
+// │ ┌────────────┐
+// └──────────────▶ │ middle │ ─┐
+// └────────────┘ │
+// │ │
+// │ │
+// ▼ │
+// ┌────────────┐ │
+// │ esc_bottom │ │
+// └────────────┘ │
+// │ │
+// │ │
+// ▼ │
+// ┌────────────┐ │
+// │ exit │ ◀┘
+// └────────────┘
+TEST_F(LoadStoreAnalysisTest, InAndOutEscape) {
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
+ "exit",
+ { { "entry", "esc_top" },
+ { "entry", "right" },
+ { "esc_top", "middle" },
+ { "right", "middle" },
+ { "middle", "exit" },
+ { "middle", "esc_bottom" },
+ { "esc_bottom", "exit" } }));
+
+ ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
+ esg.RemoveBlock(blks.Get("esc_top"));
+ esg.RemoveBlock(blks.Get("esc_bottom"));
+ esg.Finalize();
+
+ std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
+ esg.ReachableBlocks().end());
+ ASSERT_EQ(contents.size(), 0u);
+ ASSERT_FALSE(esg.IsValid());
+ ASSERT_FALSE(IsValidSubgraph(esg));
+
+ ASSERT_EQ(contents.size(), 0u);
+}
+
} // namespace art
diff --git a/compiler/optimizing/load_store_elimination.cc b/compiler/optimizing/load_store_elimination.cc
index 5f15822..dcccc5b 100644
--- a/compiler/optimizing/load_store_elimination.cc
+++ b/compiler/optimizing/load_store_elimination.cc
@@ -16,15 +16,19 @@
#include "load_store_elimination.h"
+#include "base/arena_allocator.h"
#include "base/arena_bit_vector.h"
#include "base/array_ref.h"
#include "base/bit_vector-inl.h"
+#include "base/bit_vector.h"
#include "base/scoped_arena_allocator.h"
#include "base/scoped_arena_containers.h"
#include "escape.h"
#include "load_store_analysis.h"
-#include "optimizing/optimizing_compiler_stats.h"
+#include "nodes.h"
+#include "optimizing_compiler_stats.h"
#include "reference_type_propagation.h"
+#include "side_effects_analysis.h"
/**
* The general algorithm of load-store elimination (LSE).
@@ -258,6 +262,7 @@
enum class Type {
kInvalid,
kUnknown,
+ kMergedUnknown,
kDefault,
kInstruction,
kNeedsNonLoopPhi,
@@ -282,6 +287,13 @@
return value;
}
+ static Value MergedUnknown(const PhiPlaceholder* phi_placeholder) {
+ Value value;
+ value.type_ = Type::kMergedUnknown;
+ value.phi_placeholder_ = phi_placeholder;
+ return value;
+ }
+
// Default heap value after an allocation.
// A heap location can be set to that value right after an allocation.
static Value Default() {
@@ -325,10 +337,18 @@
return type_ == Type::kInvalid;
}
- bool IsUnknown() const {
+ bool IsMergedUnknown() const {
+ return type_ == Type::kMergedUnknown;
+ }
+
+ bool IsPureUnknown() const {
return type_ == Type::kUnknown;
}
+ bool IsUnknown() const {
+ return type_ == Type::kUnknown || type_ == Type::kMergedUnknown;
+ }
+
bool IsDefault() const {
return type_ == Type::kDefault;
}
@@ -355,10 +375,25 @@
}
const PhiPlaceholder* GetPhiPlaceholder() const {
- DCHECK(NeedsPhi());
+ DCHECK(NeedsPhi() || IsMergedUnknown());
return phi_placeholder_;
}
+ uint32_t GetMergeBlockId() const {
+ DCHECK(IsMergedUnknown()) << this;
+ return phi_placeholder_->GetBlockId();
+ }
+
+ HBasicBlock* GetMergeBlock(const HGraph* graph) const {
+ DCHECK(IsMergedUnknown()) << this;
+ return graph->GetBlocks()[GetMergeBlockId()];
+ }
+
+ size_t GetHeapLocation() const {
+ DCHECK(IsMergedUnknown() || NeedsPhi()) << this;
+ return phi_placeholder_->GetHeapLocation();
+ }
+
bool Equals(Value other) const {
// Only valid values can be compared.
DCHECK(IsValid());
@@ -369,9 +404,9 @@
(other.IsDefault() && IsInstruction() && IsZeroBitPattern(GetInstruction()));
} else {
// Note: Two unknown values are considered different.
- return IsDefault() ||
- (IsInstruction() && GetInstruction() == other.GetInstruction()) ||
- (NeedsPhi() && GetPhiPlaceholder() == other.GetPhiPlaceholder());
+ return IsDefault() || (IsInstruction() && GetInstruction() == other.GetInstruction()) ||
+ (NeedsPhi() && GetPhiPlaceholder() == other.GetPhiPlaceholder()) ||
+ (IsMergedUnknown() && GetPhiPlaceholder() == other.GetPhiPlaceholder());
}
}
@@ -379,7 +414,11 @@
return Equals(ForInstruction(instruction));
}
+ std::ostream& Dump(std::ostream& os) const;
+
private:
+ friend std::ostream& operator<<(std::ostream& os, const Value& v);
+
Type type_;
union {
HInstruction* instruction_;
@@ -397,6 +436,20 @@
return PhiPlaceholderIndex(phi_placeholder.GetPhiPlaceholder());
}
+ bool IsPartialNoEscape(HBasicBlock* blk, size_t idx) {
+ auto* ri = heap_location_collector_.GetHeapLocation(idx)->GetReferenceInfo();
+ auto* sg = ri->GetNoEscapeSubgraph();
+ return ri->IsPartialSingleton() &&
+ std::none_of(sg->GetExcludedCohorts().cbegin(),
+ sg->GetExcludedCohorts().cend(),
+ [&](const ExecutionSubgraph::ExcludedCohort& ex) -> bool {
+ // Make sure we haven't yet and never will escape.
+ return ex.PrecedesBlock(blk) ||
+ ex.ContainsBlock(blk) ||
+ ex.SucceedsBlock(blk);
+ });
+ }
+
const PhiPlaceholder* GetPhiPlaceholder(uint32_t block_id, size_t idx) const {
size_t phi_placeholders_begin = phi_placeholders_begin_for_block_[block_id];
const PhiPlaceholder* phi_placeholder = &phi_placeholders_[phi_placeholders_begin + idx];
@@ -545,7 +598,12 @@
// Keep the store referenced by the instruction, or all stores that feed a Phi placeholder.
// This is necessary if the stored heap value can be observed.
void KeepStores(Value value) {
- if (value.IsUnknown()) {
+ if (value.IsPureUnknown()) {
+ return;
+ }
+ if (value.IsMergedUnknown()) {
+ kept_merged_unknowns_.SetBit(PhiPlaceholderIndex(value));
+ phi_placeholders_to_search_for_kept_stores_.SetBit(PhiPlaceholderIndex(value));
return;
}
if (value.NeedsPhi()) {
@@ -568,7 +626,9 @@
// We use this function when reading a location with unknown value and
// therefore we cannot know what exact store wrote that unknown value.
// But we can have a phi placeholder here marking multiple stores to keep.
- DCHECK(!heap_values[i].stored_by.IsInstruction());
+ DCHECK(
+ !heap_values[i].stored_by.IsInstruction() ||
+ heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo()->IsPartialSingleton());
KeepStores(heap_values[i].stored_by);
heap_values[i].stored_by = Value::Unknown();
} else if (heap_location_collector_.MayAlias(i, loc_index)) {
@@ -779,7 +839,8 @@
ScopedArenaVector<ValueRecord>& heap_values = heap_values_for_[block->GetBlockId()];
for (size_t i = 0u, size = heap_values.size(); i != size; ++i) {
ReferenceInfo* ref_info = heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo();
- if (!ref_info->IsSingletonAndRemovable()) {
+ if (!ref_info->IsSingletonAndRemovable() &&
+ !(ref_info->IsPartialSingleton() && IsPartialNoEscape(block, i))) {
KeepStores(heap_values[i].stored_by);
heap_values[i].stored_by = Value::Unknown();
}
@@ -953,11 +1014,44 @@
// The unknown heap value is used to mark Phi placeholders that cannot be replaced.
ScopedArenaVector<Value> phi_placeholder_replacements_;
+ // Merged-unknowns that must have their predecessor values kept to ensure
+ // partially escaped values are written
+ ArenaBitVector kept_merged_unknowns_;
+
ScopedArenaVector<HInstruction*> singleton_new_instances_;
+ friend std::ostream& operator<<(std::ostream& os, const Value& v);
+
DISALLOW_COPY_AND_ASSIGN(LSEVisitor);
};
+std::ostream& LSEVisitor::Value::Dump(std::ostream& os) const {
+ switch (type_) {
+ case Type::kDefault:
+ return os << "Default";
+ case Type::kInstruction:
+ return os << "Instruction[id: " << instruction_->GetId()
+ << ", block: " << instruction_->GetBlock()->GetBlockId() << "]";
+ case Type::kUnknown:
+ return os << "Unknown";
+ case Type::kInvalid:
+ return os << "Invalid";
+ case Type::kMergedUnknown:
+ return os << "MergedUnknown[block: " << phi_placeholder_->GetBlockId()
+ << ", heap_loc: " << phi_placeholder_->GetHeapLocation() << "]";
+ case Type::kNeedsLoopPhi:
+ return os << "NeedsLoopPhi[block: " << phi_placeholder_->GetBlockId()
+ << ", heap_loc: " << phi_placeholder_->GetHeapLocation() << "]";
+ case Type::kNeedsNonLoopPhi:
+ return os << "NeedsNonLoopPhi[block: " << phi_placeholder_->GetBlockId()
+ << ", heap_loc: " << phi_placeholder_->GetHeapLocation() << "]";
+ }
+}
+
+std::ostream& operator<<(std::ostream& os, const LSEVisitor::Value& v) {
+ return v.Dump(os);
+}
+
ScopedArenaVector<LSEVisitor::PhiPlaceholder> LSEVisitor::CreatePhiPlaceholders(
HGraph* graph,
const HeapLocationCollector& heap_location_collector,
@@ -1032,6 +1126,10 @@
phi_placeholder_replacements_(phi_placeholders_.size(),
Value::Invalid(),
allocator_.Adapter(kArenaAllocLSE)),
+ kept_merged_unknowns_(&allocator_,
+ /*start_bits=*/ phi_placeholders_.size(),
+ /*expandable=*/ false,
+ kArenaAllocLSE),
singleton_new_instances_(allocator_.Adapter(kArenaAllocLSE)) {
// Clear bit vectors.
phi_placeholders_to_search_for_kept_stores_.ClearAllBits();
@@ -1049,18 +1147,21 @@
uint32_t pre_header_block_id = loop_info->GetPreHeader()->GetBlockId();
Value pre_header_value = ReplacementOrValue(heap_values_for_[pre_header_block_id][idx].value);
if (pre_header_value.IsUnknown()) {
- return Value::Unknown();
+ return pre_header_value;
}
if (kIsDebugBuild) {
// Check that the reference indeed dominates this loop.
HeapLocation* location = heap_location_collector_.GetHeapLocation(idx);
HInstruction* ref = location->GetReferenceInfo()->GetReference();
- CHECK(ref->GetBlock() != block && ref->GetBlock()->Dominates(block));
+ CHECK(ref->GetBlock() != block && ref->GetBlock()->Dominates(block))
+ << GetGraph()->PrettyMethod();
// Check that the index, if defined inside the loop, tracks a default value
// or a Phi placeholder requiring a loop Phi.
HInstruction* index = location->GetIndex();
if (index != nullptr && loop_info->Contains(*index->GetBlock())) {
- CHECK(pre_header_value.NeedsLoopPhi() || pre_header_value.Equals(Value::Default()));
+ CHECK(pre_header_value.NeedsLoopPhi() || pre_header_value.Equals(Value::Default()))
+ << GetGraph()->PrettyMethod() << " blk: " << block->GetBlockId() << " "
+ << pre_header_value;
}
}
const PhiPlaceholder* phi_placeholder = GetPhiPlaceholder(block->GetBlockId(), idx);
@@ -1115,14 +1216,21 @@
Value merged_value =
ReplacementOrValue(heap_values_for_[predecessors[0]->GetBlockId()][idx].value);
for (size_t i = 1u, size = predecessors.size(); i != size; ++i) {
- if (merged_value.IsUnknown()) {
- break;
- }
Value pred_value =
ReplacementOrValue(heap_values_for_[predecessors[i]->GetBlockId()][idx].value);
- if (pred_value.IsUnknown()) {
- merged_value = Value::Unknown();
- } else if (!pred_value.Equals(merged_value)) {
+ if (pred_value.Equals(merged_value) ||
+ (pred_value.IsPureUnknown() && merged_value.IsPureUnknown())) {
+ // Value is the same. No need to update our merged value.
+ continue;
+ } else if (pred_value.IsUnknown() || merged_value.IsUnknown()) {
+ // If one is unknown and the other is a different type of unknown
+ const PhiPlaceholder* phi_placeholder = GetPhiPlaceholder(block->GetBlockId(), idx);
+ merged_value = Value::MergedUnknown(phi_placeholder);
+ // We know that at least one of the merge points is unknown (and both are
+ // not pure-unknowns since that's captured above). This means that the
+ // overall value needs to be a MergedUnknown. Just return that.
+ break;
+ } else {
// There are conflicting known values. We may still be able to replace loads with a Phi.
const PhiPlaceholder* phi_placeholder = GetPhiPlaceholder(block->GetBlockId(), idx);
// Propagate the need for a new loop Phi from all predecessors.
@@ -1247,7 +1355,8 @@
phi_inputs.clear();
for (HBasicBlock* predecessor : current_block->GetPredecessors()) {
Value pred_value = ReplacementOrValue(heap_values_for_[predecessor->GetBlockId()][idx].value);
- DCHECK(!pred_value.IsUnknown());
+ DCHECK(!pred_value.IsUnknown())
+ << "block " << current_block->GetBlockId() << " pred: " << predecessor->GetBlockId();
if (pred_value.NeedsNonLoopPhi()) {
// We need to process the Phi placeholder first.
work_queue.push_back(pred_value.GetPhiPlaceholder());
@@ -1287,8 +1396,10 @@
} else if (record.value.IsUnknown()) {
// Load isn't eliminated. Put the load as the value into the HeapLocation.
// This acts like GVN but with better aliasing analysis.
+ Value old_value = record.value;
record.value = Value::ForInstruction(instruction);
KeepStoresIfAliasedToLocation(heap_values, idx);
+ KeepStores(old_value);
} else if (record.value.NeedsLoopPhi()) {
// We do not know yet if the value is known for all back edges. Record for future processing.
loads_requiring_loop_phi_.insert(std::make_pair(instruction, record));
@@ -2047,8 +2158,22 @@
work_queue.push_back(index);
}
const ArenaVector<HBasicBlock*>& blocks = GetGraph()->GetBlocks();
+ std::optional<ArenaBitVector> not_kept_stores;
+ if (stats_) {
+ not_kept_stores.emplace(GetGraph()->GetAllocator(),
+ kept_stores_.GetBitSizeOf(),
+ false,
+ ArenaAllocKind::kArenaAllocLSE);
+ }
while (!work_queue.empty()) {
- const PhiPlaceholder* phi_placeholder = &phi_placeholders_[work_queue.back()];
+ uint32_t cur_phi_idx = work_queue.back();
+ const PhiPlaceholder* phi_placeholder = &phi_placeholders_[cur_phi_idx];
+ // Only writes to partial-escapes need to be specifically kept.
+ bool is_partial_kept_merged_unknown =
+ kept_merged_unknowns_.IsBitSet(cur_phi_idx) &&
+ heap_location_collector_.GetHeapLocation(phi_placeholder->GetHeapLocation())
+ ->GetReferenceInfo()
+ ->IsPartialSingleton();
work_queue.pop_back();
size_t idx = phi_placeholder->GetHeapLocation();
HBasicBlock* block = blocks[phi_placeholder->GetBlockId()];
@@ -2091,18 +2216,39 @@
if (!stored_by.IsUnknown() && (i == idx || may_alias(i))) {
if (stored_by.NeedsPhi()) {
size_t phi_placeholder_index = PhiPlaceholderIndex(stored_by);
+ if (is_partial_kept_merged_unknown) {
+ // Propagate merged-unknown keep since otherwise this might look
+ // like a partial escape we can remove.
+ kept_merged_unknowns_.SetBit(phi_placeholder_index);
+ }
if (!phi_placeholders_to_search_for_kept_stores_.IsBitSet(phi_placeholder_index)) {
phi_placeholders_to_search_for_kept_stores_.SetBit(phi_placeholder_index);
work_queue.push_back(phi_placeholder_index);
}
} else {
DCHECK(IsStore(stored_by.GetInstruction()));
- kept_stores_.SetBit(stored_by.GetInstruction()->GetId());
+ ReferenceInfo* ri = heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo();
+ DCHECK(ri != nullptr) << "No heap value for " << stored_by.GetInstruction()->DebugName()
+ << " id: " << stored_by.GetInstruction()->GetId() << " block: "
+ << stored_by.GetInstruction()->GetBlock()->GetBlockId();
+ if (!is_partial_kept_merged_unknown && IsPartialNoEscape(predecessor, idx)) {
+ if (not_kept_stores) {
+ not_kept_stores->SetBit(stored_by.GetInstruction()->GetId());
+ }
+ } else {
+ kept_stores_.SetBit(stored_by.GetInstruction()->GetId());
+ }
}
}
}
}
}
+ if (not_kept_stores) {
+ // a - b := (a & ~b)
+ not_kept_stores->Subtract(&kept_stores_);
+ auto num_removed = not_kept_stores->NumSetBits();
+ MaybeRecordStat(stats_, MethodCompilationStat::kPartialStoreRemoved, num_removed);
+ }
}
void LSEVisitor::UpdateValueRecordForStoreElimination(/*inout*/ValueRecord* value_record) {
@@ -2273,6 +2419,7 @@
if (!new_instance->HasNonEnvironmentUses()) {
new_instance->RemoveEnvironmentUsers();
new_instance->GetBlock()->RemoveInstruction(new_instance);
+ MaybeRecordStat(stats_, MethodCompilationStat::kFullLSEAllocationRemoved);
}
}
}
@@ -2284,8 +2431,14 @@
// Skip this optimization.
return false;
}
+ // We need to be able to determine reachability. Clear it just to be safe but
+ // this should initially be empty.
+ graph_->ClearReachabilityInformation();
+ // This is O(blocks^3) time complexity. It means we can query reachability in
+ // O(1) though.
+ graph_->ComputeReachabilityInformation();
ScopedArenaAllocator allocator(graph_->GetArenaStack());
- LoadStoreAnalysis lsa(graph_, &allocator);
+ LoadStoreAnalysis lsa(graph_, stats_, &allocator, /*for_elimination=*/true);
lsa.Run();
const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
if (heap_location_collector.GetNumberOfHeapLocations() == 0) {
diff --git a/compiler/optimizing/load_store_elimination_test.cc b/compiler/optimizing/load_store_elimination_test.cc
index f71a473..8196a29 100644
--- a/compiler/optimizing/load_store_elimination_test.cc
+++ b/compiler/optimizing/load_store_elimination_test.cc
@@ -27,6 +27,13 @@
class LoadStoreEliminationTest : public OptimizingUnitTest {
public:
+ AdjacencyListGraph SetupFromAdjacencyList(
+ const std::string_view entry_name,
+ const std::string_view exit_name,
+ const std::vector<AdjacencyListGraph::Edge>& adj) {
+ return AdjacencyListGraph(graph_, GetAllocator(), entry_name, exit_name, adj);
+ }
+
void PerformLSE() {
graph_->BuildDominatorTree();
LoadStoreElimination lse(graph_, /*stats=*/ nullptr);
@@ -1442,4 +1449,1182 @@
EXPECT_TRUE(IsRemoved(alloc_w));
}
+// // ENTRY
+// obj = new Obj();
+// if (parameter_value) {
+// // LEFT
+// obj.field = 1;
+// call_func(obj);
+// foo_r = obj.field
+// } else {
+// // TO BE ELIMINATED
+// obj.field = 2;
+// // RIGHT
+// // TO BE ELIMINATED
+// foo_l = obj.field;
+// }
+// EXIT
+// return PHI(foo_l, foo_r)
+TEST_F(LoadStoreEliminationTest, PartialLoadElimination) {
+ InitGraph();
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
+ "exit_REAL",
+ { { "entry", "left" },
+ { "entry", "right" },
+ { "left", "exit" },
+ { "right", "exit" },
+ { "exit", "exit_REAL" } }));
+ HBasicBlock* entry = blks.Get("entry");
+ HBasicBlock* left = blks.Get("left");
+ HBasicBlock* right = blks.Get("right");
+ HBasicBlock* exit = blks.Get("exit");
+ HInstruction* bool_value = new (GetAllocator())
+ HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
+ HInstruction* c1 = graph_->GetIntConstant(1);
+ HInstruction* c2 = graph_->GetIntConstant(2);
+ HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ ScopedNullHandle<mirror::Class>(),
+ false,
+ 0,
+ false);
+ HInstruction* new_inst =
+ new (GetAllocator()) HNewInstance(cls,
+ 0,
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ false,
+ QuickEntrypointEnum::kQuickAllocObjectInitialized);
+ HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
+ entry->AddInstruction(bool_value);
+ entry->AddInstruction(cls);
+ entry->AddInstruction(new_inst);
+ entry->AddInstruction(if_inst);
+ ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
+ ManuallyBuildEnvFor(cls, ¤t_locals);
+ new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* write_left = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c1,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* call_left = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 1,
+ DataType::Type::kVoid,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* read_left = new (GetAllocator()) HInstanceFieldGet(new_inst,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(16),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_left = new (GetAllocator()) HGoto();
+ call_left->AsInvoke()->SetRawInputAt(0, new_inst);
+ left->AddInstruction(write_left);
+ left->AddInstruction(call_left);
+ left->AddInstruction(read_left);
+ left->AddInstruction(goto_left);
+ call_left->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c2,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(16),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* read_right = new (GetAllocator()) HInstanceFieldGet(new_inst,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(16),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_right = new (GetAllocator()) HGoto();
+ right->AddInstruction(write_right);
+ right->AddInstruction(read_right);
+ right->AddInstruction(goto_right);
+
+ HInstruction* phi_final =
+ new (GetAllocator()) HPhi(GetAllocator(), 12, 2, DataType::Type::kInt32);
+ phi_final->SetRawInputAt(0, read_left);
+ phi_final->SetRawInputAt(1, read_right);
+ HInstruction* return_exit = new (GetAllocator()) HReturn(phi_final);
+ exit->AddPhi(phi_final->AsPhi());
+ exit->AddInstruction(return_exit);
+
+ // PerformLSE expects this to be empty.
+ graph_->ClearDominanceInformation();
+ PerformLSE();
+
+ ASSERT_TRUE(IsRemoved(read_right));
+ ASSERT_FALSE(IsRemoved(read_left));
+ ASSERT_FALSE(IsRemoved(phi_final));
+ ASSERT_TRUE(phi_final->GetInputs()[1] == c2);
+ ASSERT_TRUE(phi_final->GetInputs()[0] == read_left);
+ ASSERT_TRUE(IsRemoved(write_right));
+}
+
+// // ENTRY
+// obj = new Obj();
+// if (parameter_value) {
+// // LEFT
+// obj.field = 1;
+// call_func(obj);
+// // We don't know what obj.field is now we aren't able to eliminate the read below!
+// } else {
+// // DO NOT ELIMINATE
+// obj.field = 2;
+// // RIGHT
+// }
+// EXIT
+// return obj.field
+// TODO We eventually want to be able to eliminate the right write along with the final read but
+// will need either new blocks or new instructions.
+TEST_F(LoadStoreEliminationTest, PartialLoadPreserved) {
+ InitGraph();
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
+ "exit_REAL",
+ { { "entry", "left" },
+ { "entry", "right" },
+ { "left", "exit" },
+ { "right", "exit" },
+ { "exit", "exit_REAL" } }));
+ HBasicBlock* entry = blks.Get("entry");
+ HBasicBlock* left = blks.Get("left");
+ HBasicBlock* right = blks.Get("right");
+ HBasicBlock* exit = blks.Get("exit");
+ HInstruction* bool_value = new (GetAllocator())
+ HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
+ HInstruction* c1 = graph_->GetIntConstant(1);
+ HInstruction* c2 = graph_->GetIntConstant(2);
+ HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ ScopedNullHandle<mirror::Class>(),
+ false,
+ 0,
+ false);
+ HInstruction* new_inst =
+ new (GetAllocator()) HNewInstance(cls,
+ 0,
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ false,
+ QuickEntrypointEnum::kQuickAllocObjectInitialized);
+ HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
+ entry->AddInstruction(bool_value);
+ entry->AddInstruction(cls);
+ entry->AddInstruction(new_inst);
+ entry->AddInstruction(if_inst);
+ ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
+ ManuallyBuildEnvFor(cls, ¤t_locals);
+ new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* write_left = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c1,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* call_left = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 1,
+ DataType::Type::kVoid,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* goto_left = new (GetAllocator()) HGoto();
+ call_left->AsInvoke()->SetRawInputAt(0, new_inst);
+ left->AddInstruction(write_left);
+ left->AddInstruction(call_left);
+ left->AddInstruction(goto_left);
+ call_left->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c2,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_right = new (GetAllocator()) HGoto();
+ right->AddInstruction(write_right);
+ right->AddInstruction(goto_right);
+
+ HInstruction* read_bottom = new (GetAllocator()) HInstanceFieldGet(new_inst,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* return_exit = new (GetAllocator()) HReturn(read_bottom);
+ exit->AddInstruction(read_bottom);
+ exit->AddInstruction(return_exit);
+ // PerformLSE expects this to be empty.
+ graph_->ClearDominanceInformation();
+ PerformLSE();
+
+ ASSERT_FALSE(IsRemoved(read_bottom));
+ ASSERT_FALSE(IsRemoved(write_right));
+}
+
+// // ENTRY
+// obj = new Obj();
+// if (parameter_value) {
+// // LEFT
+// obj.field = 1;
+// call_func(obj);
+// // We don't know what obj.field is now we aren't able to eliminate the read below!
+// } else {
+// // DO NOT ELIMINATE
+// if (param2) {
+// obj.field = 2;
+// } else {
+// obj.field = 3;
+// }
+// // RIGHT
+// }
+// EXIT
+// return obj.field
+// TODO We eventually want to be able to eliminate the right write along with the final read but
+// will need either new blocks or new instructions.
+TEST_F(LoadStoreEliminationTest, PartialLoadPreserved2) {
+ InitGraph();
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
+ "exit_REAL",
+ { { "entry", "left" },
+ { "entry", "right_start" },
+ { "left", "exit" },
+ { "right_start", "right_first" },
+ { "right_start", "right_second" },
+ { "right_first", "right_end" },
+ { "right_second", "right_end" },
+ { "right_end", "exit" },
+ { "exit", "exit_REAL" } }));
+ HBasicBlock* entry = blks.Get("entry");
+ HBasicBlock* left = blks.Get("left");
+ HBasicBlock* right_start = blks.Get("right_start");
+ HBasicBlock* right_first = blks.Get("right_first");
+ HBasicBlock* right_second = blks.Get("right_second");
+ HBasicBlock* right_end = blks.Get("right_end");
+ HBasicBlock* exit = blks.Get("exit");
+ HInstruction* bool_value = new (GetAllocator())
+ HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
+ HInstruction* bool_value_2 = new (GetAllocator())
+ HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 2, DataType::Type::kBool);
+ HInstruction* c1 = graph_->GetIntConstant(1);
+ HInstruction* c2 = graph_->GetIntConstant(2);
+ HInstruction* c3 = graph_->GetIntConstant(3);
+ HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ ScopedNullHandle<mirror::Class>(),
+ false,
+ 0,
+ false);
+ HInstruction* new_inst =
+ new (GetAllocator()) HNewInstance(cls,
+ 0,
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ false,
+ QuickEntrypointEnum::kQuickAllocObjectInitialized);
+ HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
+ entry->AddInstruction(bool_value);
+ entry->AddInstruction(bool_value_2);
+ entry->AddInstruction(cls);
+ entry->AddInstruction(new_inst);
+ entry->AddInstruction(if_inst);
+ ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
+ ManuallyBuildEnvFor(cls, ¤t_locals);
+ new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* write_left = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c1,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* call_left = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 1,
+ DataType::Type::kVoid,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* goto_left = new (GetAllocator()) HGoto();
+ call_left->AsInvoke()->SetRawInputAt(0, new_inst);
+ left->AddInstruction(write_left);
+ left->AddInstruction(call_left);
+ left->AddInstruction(goto_left);
+ call_left->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* right_if = new (GetAllocator()) HIf(bool_value_2);
+ right_start->AddInstruction(right_if);
+
+ HInstruction* write_right_first = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c2,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_right_first = new (GetAllocator()) HGoto();
+ right_first->AddInstruction(write_right_first);
+ right_first->AddInstruction(goto_right_first);
+
+ HInstruction* write_right_second = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c3,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_right_second = new (GetAllocator()) HGoto();
+ right_second->AddInstruction(write_right_second);
+ right_second->AddInstruction(goto_right_second);
+
+ HInstruction* goto_right_end = new (GetAllocator()) HGoto();
+ right_end->AddInstruction(goto_right_end);
+
+ HInstruction* read_bottom = new (GetAllocator()) HInstanceFieldGet(new_inst,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* return_exit = new (GetAllocator()) HReturn(read_bottom);
+ exit->AddInstruction(read_bottom);
+ exit->AddInstruction(return_exit);
+ // PerformLSE expects this to be empty.
+ graph_->ClearDominanceInformation();
+ PerformLSE();
+
+ ASSERT_FALSE(IsRemoved(read_bottom));
+ EXPECT_FALSE(IsRemoved(write_right_first));
+ EXPECT_FALSE(IsRemoved(write_right_second));
+}
+
+// // ENTRY
+// obj = new Obj();
+// if (parameter_value) {
+// // LEFT
+// // DO NOT ELIMINATE
+// escape(obj);
+// obj.field = 1;
+// } else {
+// // RIGHT
+// // ELIMINATE
+// obj.field = 2;
+// }
+// EXIT
+// ELIMINATE
+// return obj.field
+TEST_F(LoadStoreEliminationTest, PartialLoadElimination2) {
+ InitGraph();
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
+ "exit",
+ { { "entry", "left" },
+ { "entry", "right" },
+ { "left", "breturn"},
+ { "right", "breturn" },
+ { "breturn", "exit" } }));
+#define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
+ GET_BLOCK(entry);
+ GET_BLOCK(exit);
+ GET_BLOCK(breturn);
+ GET_BLOCK(left);
+ GET_BLOCK(right);
+#undef GET_BLOCK
+ HInstruction* bool_value = new (GetAllocator())
+ HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
+ HInstruction* c1 = graph_->GetIntConstant(1);
+ HInstruction* c2 = graph_->GetIntConstant(2);
+ HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ ScopedNullHandle<mirror::Class>(),
+ false,
+ 0,
+ false);
+ HInstruction* new_inst =
+ new (GetAllocator()) HNewInstance(cls,
+ 0,
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ false,
+ QuickEntrypointEnum::kQuickAllocObjectInitialized);
+ HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
+ entry->AddInstruction(bool_value);
+ entry->AddInstruction(cls);
+ entry->AddInstruction(new_inst);
+ entry->AddInstruction(if_inst);
+ ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
+ ManuallyBuildEnvFor(cls, ¤t_locals);
+ new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* call_left = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 1,
+ DataType::Type::kVoid,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* write_left = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c1,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_left = new (GetAllocator()) HGoto();
+ call_left->AsInvoke()->SetRawInputAt(0, new_inst);
+ left->AddInstruction(call_left);
+ left->AddInstruction(write_left);
+ left->AddInstruction(goto_left);
+ call_left->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c2,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_right = new (GetAllocator()) HGoto();
+ right->AddInstruction(write_right);
+ right->AddInstruction(goto_right);
+
+ HInstruction* read_bottom = new (GetAllocator()) HInstanceFieldGet(new_inst,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* return_exit = new (GetAllocator()) HReturn(read_bottom);
+ breturn->AddInstruction(read_bottom);
+ breturn->AddInstruction(return_exit);
+
+ HInstruction* exit_instruction = new (GetAllocator()) HExit();
+ exit->AddInstruction(exit_instruction);
+ // PerformLSE expects this to be empty.
+ graph_->ClearDominanceInformation();
+ PerformLSE();
+
+ ASSERT_TRUE(IsRemoved(read_bottom));
+ ASSERT_TRUE(IsRemoved(write_right));
+ ASSERT_FALSE(IsRemoved(write_left));
+ ASSERT_FALSE(IsRemoved(call_left));
+}
+
+// // ENTRY
+// obj = new Obj();
+// if (parameter_value) {
+// // LEFT
+// // DO NOT ELIMINATE
+// obj.field = 1;
+// escape(obj);
+// return obj.field;
+// } else {
+// // RIGHT
+// // ELIMINATE
+// obj.field = 2;
+// return obj.field;
+// }
+// EXIT
+TEST_F(LoadStoreEliminationTest, PartialLoadElimination3) {
+ InitGraph();
+ AdjacencyListGraph blks(SetupFromAdjacencyList(
+ "entry",
+ "exit",
+ { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
+#define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
+ GET_BLOCK(entry);
+ GET_BLOCK(exit);
+ GET_BLOCK(left);
+ GET_BLOCK(right);
+#undef GET_BLOCK
+ HInstruction* bool_value = new (GetAllocator())
+ HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
+ HInstruction* c1 = graph_->GetIntConstant(1);
+ HInstruction* c2 = graph_->GetIntConstant(2);
+ HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ ScopedNullHandle<mirror::Class>(),
+ false,
+ 0,
+ false);
+ HInstruction* new_inst =
+ new (GetAllocator()) HNewInstance(cls,
+ 0,
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ false,
+ QuickEntrypointEnum::kQuickAllocObjectInitialized);
+ HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
+ entry->AddInstruction(bool_value);
+ entry->AddInstruction(cls);
+ entry->AddInstruction(new_inst);
+ entry->AddInstruction(if_inst);
+ ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
+ ManuallyBuildEnvFor(cls, ¤t_locals);
+ new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* write_left = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c1,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* call_left = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 1,
+ DataType::Type::kVoid,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* read_left = new (GetAllocator()) HInstanceFieldGet(new_inst,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* return_left = new (GetAllocator()) HReturn(read_left);
+ call_left->AsInvoke()->SetRawInputAt(0, new_inst);
+ left->AddInstruction(write_left);
+ left->AddInstruction(call_left);
+ left->AddInstruction(read_left);
+ left->AddInstruction(return_left);
+ call_left->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c2,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* read_right = new (GetAllocator()) HInstanceFieldGet(new_inst,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* return_right = new (GetAllocator()) HReturn(read_right);
+ right->AddInstruction(write_right);
+ right->AddInstruction(read_right);
+ right->AddInstruction(return_right);
+
+ HInstruction* exit_instruction = new (GetAllocator()) HExit();
+ exit->AddInstruction(exit_instruction);
+ // PerformLSE expects this to be empty.
+ graph_->ClearDominanceInformation();
+ PerformLSE();
+
+ EXPECT_TRUE(IsRemoved(read_right));
+ EXPECT_TRUE(IsRemoved(write_right));
+ EXPECT_FALSE(IsRemoved(write_left));
+ EXPECT_FALSE(IsRemoved(call_left));
+ EXPECT_FALSE(IsRemoved(read_left));
+}
+
+// // ENTRY
+// obj = new Obj();
+// if (parameter_value) {
+// // LEFT
+// // DO NOT ELIMINATE
+// obj.field = 1;
+// while (true) {
+// bool esc = escape(obj);
+// // DO NOT ELIMINATE
+// obj.field = 3;
+// if (esc) break;
+// }
+// // ELIMINATE.
+// return obj.field;
+// } else {
+// // RIGHT
+// // ELIMINATE
+// obj.field = 2;
+// return obj.field;
+// }
+// EXIT
+TEST_F(LoadStoreEliminationTest, PartialLoadElimination4) {
+ InitGraph();
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
+ "exit",
+ { { "entry", "entry_post" },
+ { "entry_post", "right" },
+ { "right", "exit" },
+ { "entry_post", "left_pre" },
+ { "left_pre", "left_loop" },
+ { "left_loop", "left_loop" },
+ { "left_loop", "left_finish" },
+ { "left_finish", "exit" } }));
+#define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
+ GET_BLOCK(entry);
+ GET_BLOCK(entry_post);
+ GET_BLOCK(exit);
+ GET_BLOCK(left_pre);
+ GET_BLOCK(left_loop);
+ GET_BLOCK(left_finish);
+ GET_BLOCK(right);
+#undef GET_BLOCK
+ // Left-loops first successor is the break.
+ if (left_loop->GetSuccessors()[0] != left_finish) {
+ left_loop->SwapSuccessors();
+ }
+ HInstruction* bool_value = new (GetAllocator())
+ HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
+ HInstruction* c1 = graph_->GetIntConstant(1);
+ HInstruction* c2 = graph_->GetIntConstant(2);
+ HInstruction* c3 = graph_->GetIntConstant(3);
+ HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ ScopedNullHandle<mirror::Class>(),
+ false,
+ 0,
+ false);
+ HInstruction* new_inst =
+ new (GetAllocator()) HNewInstance(cls,
+ 0,
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ false,
+ QuickEntrypointEnum::kQuickAllocObjectInitialized);
+ HInstruction* goto_entry = new (GetAllocator()) HGoto();
+ entry->AddInstruction(bool_value);
+ entry->AddInstruction(cls);
+ entry->AddInstruction(new_inst);
+ entry->AddInstruction(goto_entry);
+ ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
+ ManuallyBuildEnvFor(cls, ¤t_locals);
+ new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
+ entry_post->AddInstruction(if_inst);
+
+ HInstruction* write_left_pre = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c1,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_left_pre = new (GetAllocator()) HGoto();
+ left_pre->AddInstruction(write_left_pre);
+ left_pre->AddInstruction(goto_left_pre);
+
+ HInstruction* suspend_left_loop = new (GetAllocator()) HSuspendCheck();
+ HInstruction* call_left_loop = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 1,
+ DataType::Type::kBool,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* write_left_loop = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c3,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* if_left_loop = new (GetAllocator()) HIf(call_left_loop);
+ call_left_loop->AsInvoke()->SetRawInputAt(0, new_inst);
+ left_loop->AddInstruction(suspend_left_loop);
+ left_loop->AddInstruction(call_left_loop);
+ left_loop->AddInstruction(write_left_loop);
+ left_loop->AddInstruction(if_left_loop);
+ suspend_left_loop->CopyEnvironmentFrom(cls->GetEnvironment());
+ call_left_loop->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* read_left_end = new (GetAllocator()) HInstanceFieldGet(new_inst,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* return_left_end = new (GetAllocator()) HReturn(read_left_end);
+ left_finish->AddInstruction(read_left_end);
+ left_finish->AddInstruction(return_left_end);
+
+ HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c2,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* read_right = new (GetAllocator()) HInstanceFieldGet(new_inst,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* return_right = new (GetAllocator()) HReturn(read_right);
+ right->AddInstruction(write_right);
+ right->AddInstruction(read_right);
+ right->AddInstruction(return_right);
+
+ HInstruction* exit_instruction = new (GetAllocator()) HExit();
+ exit->AddInstruction(exit_instruction);
+ // PerformLSE expects this to be empty.
+ graph_->ClearDominanceInformation();
+ PerformLSE();
+
+ EXPECT_FALSE(IsRemoved(write_left_pre));
+ EXPECT_TRUE(IsRemoved(read_right));
+ EXPECT_TRUE(IsRemoved(write_right));
+ EXPECT_FALSE(IsRemoved(write_left_loop));
+ EXPECT_FALSE(IsRemoved(call_left_loop));
+ EXPECT_TRUE(IsRemoved(read_left_end));
+}
+
+// // ENTRY
+// obj = new Obj();
+// if (parameter_value) {
+// // LEFT
+// // DO NOT ELIMINATE
+// obj.field = 1;
+// while (true) {
+// bool esc = escape(obj);
+// if (esc) break;
+// // DO NOT ELIMINATE
+// obj.field = 3;
+// }
+// } else {
+// // RIGHT
+// // DO NOT ELIMINATE
+// obj.field = 2;
+// }
+// // DO NOT ELIMINATE
+// return obj.field;
+// EXIT
+TEST_F(LoadStoreEliminationTest, PartialLoadPreserved3) {
+ InitGraph();
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
+ "exit",
+ { { "entry", "entry_post" },
+ { "entry_post", "right" },
+ { "right", "return_block" },
+ { "entry_post", "left_pre" },
+ { "left_pre", "left_loop" },
+ { "left_loop", "left_loop_post" },
+ { "left_loop_post", "left_loop" },
+ { "left_loop", "return_block" },
+ { "return_block", "exit" } }));
+#define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
+ GET_BLOCK(entry);
+ GET_BLOCK(entry_post);
+ GET_BLOCK(exit);
+ GET_BLOCK(return_block);
+ GET_BLOCK(left_pre);
+ GET_BLOCK(left_loop);
+ GET_BLOCK(left_loop_post);
+ GET_BLOCK(right);
+#undef GET_BLOCK
+ // Left-loops first successor is the break.
+ if (left_loop->GetSuccessors()[0] != return_block) {
+ left_loop->SwapSuccessors();
+ }
+ HInstruction* bool_value = new (GetAllocator())
+ HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
+ HInstruction* c1 = graph_->GetIntConstant(1);
+ HInstruction* c2 = graph_->GetIntConstant(2);
+ HInstruction* c3 = graph_->GetIntConstant(3);
+ HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ ScopedNullHandle<mirror::Class>(),
+ false,
+ 0,
+ false);
+ HInstruction* new_inst =
+ new (GetAllocator()) HNewInstance(cls,
+ 0,
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ false,
+ QuickEntrypointEnum::kQuickAllocObjectInitialized);
+ HInstruction* goto_entry = new (GetAllocator()) HGoto();
+ entry->AddInstruction(bool_value);
+ entry->AddInstruction(cls);
+ entry->AddInstruction(new_inst);
+ entry->AddInstruction(goto_entry);
+ ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
+ ManuallyBuildEnvFor(cls, ¤t_locals);
+ new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
+ entry_post->AddInstruction(if_inst);
+
+ HInstruction* write_left_pre = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c1,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_left_pre = new (GetAllocator()) HGoto();
+ left_pre->AddInstruction(write_left_pre);
+ left_pre->AddInstruction(goto_left_pre);
+
+ HInstruction* suspend_left_loop = new (GetAllocator()) HSuspendCheck();
+ HInstruction* call_left_loop = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 1,
+ DataType::Type::kBool,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* if_left_loop = new (GetAllocator()) HIf(call_left_loop);
+ call_left_loop->AsInvoke()->SetRawInputAt(0, new_inst);
+ left_loop->AddInstruction(suspend_left_loop);
+ left_loop->AddInstruction(call_left_loop);
+ left_loop->AddInstruction(if_left_loop);
+ suspend_left_loop->CopyEnvironmentFrom(cls->GetEnvironment());
+ call_left_loop->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* write_left_loop = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c3,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_left_loop = new (GetAllocator()) HGoto();
+ left_loop_post->AddInstruction(write_left_loop);
+ left_loop_post->AddInstruction(goto_left_loop);
+
+ HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c2,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_right = new (GetAllocator()) HGoto();
+ right->AddInstruction(write_right);
+ right->AddInstruction(goto_right);
+
+ HInstruction* read_return = new (GetAllocator()) HInstanceFieldGet(new_inst,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* return_final = new (GetAllocator()) HReturn(read_return);
+ return_block->AddInstruction(read_return);
+ return_block->AddInstruction(return_final);
+
+ HInstruction* exit_instruction = new (GetAllocator()) HExit();
+ exit->AddInstruction(exit_instruction);
+ // PerformLSE expects this to be empty.
+ graph_->ClearDominanceInformation();
+ PerformLSE();
+
+ EXPECT_FALSE(IsRemoved(write_left_pre));
+ EXPECT_FALSE(IsRemoved(read_return));
+ EXPECT_FALSE(IsRemoved(write_right));
+ EXPECT_FALSE(IsRemoved(write_left_loop));
+ EXPECT_FALSE(IsRemoved(call_left_loop));
+}
+
+// // ENTRY
+// obj = new Obj();
+// if (parameter_value) {
+// // LEFT
+// // ELIMINATE (not visible since always overridden by obj.field = 3)
+// obj.field = 1;
+// while (true) {
+// bool stop = should_stop();
+// // DO NOT ELIMINATE (visible by read at end)
+// obj.field = 3;
+// if (stop) break;
+// }
+// } else {
+// // RIGHT
+// // DO NOT ELIMINATE
+// obj.field = 2;
+// escape(obj);
+// }
+// // DO NOT ELIMINATE
+// return obj.field;
+// EXIT
+TEST_F(LoadStoreEliminationTest, PartialLoadPreserved4) {
+ InitGraph();
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
+ "exit",
+ { { "entry", "entry_post" },
+ { "entry_post", "right" },
+ { "right", "return_block" },
+ { "entry_post", "left_pre" },
+ { "left_pre", "left_loop" },
+ { "left_loop", "left_loop" },
+ { "left_loop", "return_block" },
+ { "return_block", "exit" } }));
+#define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
+ GET_BLOCK(entry);
+ GET_BLOCK(entry_post);
+ GET_BLOCK(exit);
+ GET_BLOCK(return_block);
+ GET_BLOCK(left_pre);
+ GET_BLOCK(left_loop);
+ GET_BLOCK(right);
+#undef GET_BLOCK
+ // Left-loops first successor is the break.
+ if (left_loop->GetSuccessors()[0] != return_block) {
+ left_loop->SwapSuccessors();
+ }
+ HInstruction* bool_value = new (GetAllocator())
+ HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
+ HInstruction* c1 = graph_->GetIntConstant(1);
+ HInstruction* c2 = graph_->GetIntConstant(2);
+ HInstruction* c3 = graph_->GetIntConstant(3);
+ HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ ScopedNullHandle<mirror::Class>(),
+ false,
+ 0,
+ false);
+ HInstruction* new_inst =
+ new (GetAllocator()) HNewInstance(cls,
+ 0,
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ false,
+ QuickEntrypointEnum::kQuickAllocObjectInitialized);
+ HInstruction* goto_entry = new (GetAllocator()) HGoto();
+ entry->AddInstruction(bool_value);
+ entry->AddInstruction(cls);
+ entry->AddInstruction(new_inst);
+ entry->AddInstruction(goto_entry);
+ ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
+ ManuallyBuildEnvFor(cls, ¤t_locals);
+ new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
+ entry_post->AddInstruction(if_inst);
+
+ HInstruction* write_left_pre = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c1,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_left_pre = new (GetAllocator()) HGoto();
+ left_pre->AddInstruction(write_left_pre);
+ left_pre->AddInstruction(goto_left_pre);
+
+ HInstruction* suspend_left_loop = new (GetAllocator()) HSuspendCheck();
+ HInstruction* call_left_loop = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 0,
+ DataType::Type::kBool,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* write_left_loop = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c3,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* if_left_loop = new (GetAllocator()) HIf(call_left_loop);
+ left_loop->AddInstruction(suspend_left_loop);
+ left_loop->AddInstruction(call_left_loop);
+ left_loop->AddInstruction(write_left_loop);
+ left_loop->AddInstruction(if_left_loop);
+ suspend_left_loop->CopyEnvironmentFrom(cls->GetEnvironment());
+ call_left_loop->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c2,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* call_right = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 1,
+ DataType::Type::kBool,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* goto_right = new (GetAllocator()) HGoto();
+ call_right->AsInvoke()->SetRawInputAt(0, new_inst);
+ right->AddInstruction(write_right);
+ right->AddInstruction(call_right);
+ right->AddInstruction(goto_right);
+ call_right->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* read_return = new (GetAllocator()) HInstanceFieldGet(new_inst,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* return_final = new (GetAllocator()) HReturn(read_return);
+ return_block->AddInstruction(read_return);
+ return_block->AddInstruction(return_final);
+
+ HInstruction* exit_instruction = new (GetAllocator()) HExit();
+ exit->AddInstruction(exit_instruction);
+ // PerformLSE expects this to be empty.
+ graph_->ClearDominanceInformation();
+ PerformLSE();
+
+ EXPECT_FALSE(IsRemoved(read_return));
+ EXPECT_FALSE(IsRemoved(write_right));
+ EXPECT_FALSE(IsRemoved(write_left_loop));
+ EXPECT_FALSE(IsRemoved(call_left_loop));
+ EXPECT_TRUE(IsRemoved(write_left_pre));
+ EXPECT_FALSE(IsRemoved(call_right));
+}
} // namespace art
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index e2d164e..1773c07 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -15,12 +15,19 @@
*/
#include "nodes.h"
+#include <algorithm>
#include <cfloat>
#include "art_method-inl.h"
+#include "base/arena_allocator.h"
+#include "base/arena_bit_vector.h"
#include "base/bit_utils.h"
#include "base/bit_vector-inl.h"
+#include "base/bit_vector.h"
+#include "base/iteration_range.h"
#include "base/logging.h"
+#include "base/scoped_arena_allocator.h"
+#include "base/scoped_arena_containers.h"
#include "base/stl_util.h"
#include "class_linker-inl.h"
#include "class_root-inl.h"
@@ -263,6 +270,171 @@
}
}
+// TODO Consider moving this entirely into LoadStoreAnalysis/Elimination.
+bool HGraph::PathBetween(uint32_t source_idx, uint32_t dest_idx) const {
+ DCHECK_LT(source_idx, blocks_.size()) << "source not present in graph!";
+ DCHECK_LT(dest_idx, blocks_.size()) << "dest not present in graph!";
+ DCHECK(blocks_[source_idx] != nullptr);
+ DCHECK(blocks_[dest_idx] != nullptr);
+ return reachability_graph_.IsBitSet(source_idx, dest_idx);
+}
+
+bool HGraph::PathBetween(const HBasicBlock* source, const HBasicBlock* dest) const {
+ if (source == nullptr || dest == nullptr) {
+ return false;
+ }
+ size_t source_idx = source->GetBlockId();
+ size_t dest_idx = dest->GetBlockId();
+ return PathBetween(source_idx, dest_idx);
+}
+
+// This function/struct calculates the reachability of every node from every
+// other node by iteratively using DFS to find reachability of each individual
+// block.
+//
+// This is in practice faster then the simpler Floyd-Warshall since while that
+// is O(N**3) this is O(N*(E + N)) where N is the number of blocks and E is the
+// number of edges. Since in practice each block only has a few outgoing edges
+// we can confidently say that E ~ B*N where B is a small number (~3). We also
+// memoize the results as we go allowing us to (potentially) avoid walking the
+// entire graph for every node. To make best use of this memoization we
+// calculate the reachability of blocks in PostOrder. This means that
+// (generally) blocks that are dominated by many other blocks and dominate few
+// blocks themselves will be examined first. This makes it more likely we can
+// use our memoized results.
+class ReachabilityAnalysisHelper {
+ public:
+ ReachabilityAnalysisHelper(const HGraph* graph,
+ ArenaBitVectorArray* reachability_graph,
+ ArenaStack* arena_stack)
+ : graph_(graph),
+ reachability_graph_(reachability_graph),
+ arena_stack_(arena_stack),
+ temporaries_(arena_stack_),
+ block_size_(RoundUp(graph_->GetBlocks().size(), BitVector::kWordBits)),
+ all_visited_nodes_(
+ &temporaries_, graph_->GetBlocks().size(), false, kArenaAllocReachabilityGraph),
+ not_post_order_visited_(
+ &temporaries_, graph_->GetBlocks().size(), false, kArenaAllocReachabilityGraph) {
+ // We can't adjust the size of reachability graph any more without breaking
+ // our allocator invariants so it had better be large enough.
+ CHECK_GE(reachability_graph_->NumRows(), graph_->GetBlocks().size());
+ CHECK_GE(reachability_graph_->NumColumns(), graph_->GetBlocks().size());
+ not_post_order_visited_.SetInitialBits(graph_->GetBlocks().size());
+ }
+
+ void CalculateReachability() {
+ // Calculate what blocks connect using repeated DFS
+ //
+ // Going in PostOrder should generally give memoization a good shot of
+ // hitting.
+ for (const HBasicBlock* blk : graph_->GetPostOrder()) {
+ if (blk == nullptr) {
+ continue;
+ }
+ not_post_order_visited_.ClearBit(blk->GetBlockId());
+ CalculateConnectednessOn(blk);
+ all_visited_nodes_.SetBit(blk->GetBlockId());
+ }
+ // Get all other bits
+ for (auto idx : not_post_order_visited_.Indexes()) {
+ const HBasicBlock* blk = graph_->GetBlocks()[idx];
+ if (blk == nullptr) {
+ continue;
+ }
+ CalculateConnectednessOn(blk);
+ all_visited_nodes_.SetBit(blk->GetBlockId());
+ }
+ }
+
+ private:
+ void AddEdge(uint32_t source, const HBasicBlock* dest) {
+ reachability_graph_->SetBit(source, dest->GetBlockId());
+ }
+
+ // Union the reachability of 'idx' into 'update_block_idx'. This is done to
+ // implement memoization. In order to improve performance we do this in 4-byte
+ // blocks. Clang should be able to optimize this to larger blocks if possible.
+ void UnionBlock(size_t update_block_idx, size_t idx) {
+ reachability_graph_->UnionRows(update_block_idx, idx);
+ }
+
+ // Single DFS to get connectedness of a single block
+ void CalculateConnectednessOn(const HBasicBlock* const target_block) {
+ const uint32_t target_idx = target_block->GetBlockId();
+ ScopedArenaAllocator connectedness_temps(arena_stack_);
+ // What nodes we have already discovered and either have processed or are
+ // already on the queue.
+ ArenaBitVector discovered(
+ &connectedness_temps, graph_->GetBlocks().size(), false, kArenaAllocReachabilityGraph);
+ // The work stack. What blocks we still need to process.
+ ScopedArenaVector<const HBasicBlock*> work_stack(
+ connectedness_temps.Adapter(kArenaAllocReachabilityGraph));
+ // Known max size since otherwise we'd have blocks multiple times. Avoids
+ // re-allocation
+ work_stack.reserve(graph_->GetBlocks().size());
+ discovered.SetBit(target_idx);
+ work_stack.push_back(target_block);
+ // Main DFS Loop.
+ while (!work_stack.empty()) {
+ const HBasicBlock* cur = work_stack.back();
+ work_stack.pop_back();
+ // Memoization of previous runs.
+ if (all_visited_nodes_.IsBitSet(cur->GetBlockId())) {
+ DCHECK_NE(target_block, cur);
+ // Already explored from here. Just use that data.
+ UnionBlock(target_idx, cur->GetBlockId());
+ continue;
+ }
+ for (const HBasicBlock* succ : cur->GetSuccessors()) {
+ AddEdge(target_idx, succ);
+ if (!discovered.IsBitSet(succ->GetBlockId())) {
+ work_stack.push_back(succ);
+ discovered.SetBit(succ->GetBlockId());
+ }
+ }
+ }
+ }
+
+ const HGraph* graph_;
+ // The graph's reachability_graph_ on the main allocator.
+ ArenaBitVectorArray* reachability_graph_;
+ ArenaStack* arena_stack_;
+ // An allocator for temporary bit-vectors used by this algorithm. The
+ // 'SetBit,ClearBit' on reachability_graph_ prior to the construction of this
+ // object should be the only allocation on the main allocator so it's safe to
+ // make a sub-allocator here.
+ ScopedArenaAllocator temporaries_;
+ // number of columns
+ const size_t block_size_;
+ // Where we've already completely calculated connectedness.
+ ArenaBitVector all_visited_nodes_;
+ // What we never visited and need to do later
+ ArenaBitVector not_post_order_visited_;
+
+ DISALLOW_COPY_AND_ASSIGN(ReachabilityAnalysisHelper);
+};
+
+void HGraph::ComputeReachabilityInformation() {
+ DCHECK_EQ(reachability_graph_.GetRawData().NumSetBits(), 0u);
+ DCHECK(reachability_graph_.IsExpandable());
+ // Reserve all the bits we'll need. This is the only allocation on the
+ // standard allocator we do here, enabling us to create a new ScopedArena for
+ // use with temporaries.
+ //
+ // reachability_graph_ acts as |N| x |N| graph for PathBetween. Array is
+ // padded so each row starts on an BitVector::kWordBits-bit alignment for
+ // simplicity and performance, allowing us to union blocks together without
+ // going bit-by-bit.
+ reachability_graph_.Resize(blocks_.size(), blocks_.size(), /*clear=*/false);
+ ReachabilityAnalysisHelper helper(this, &reachability_graph_, GetArenaStack());
+ helper.CalculateReachability();
+}
+
+void HGraph::ClearReachabilityInformation() {
+ reachability_graph_.Clear();
+}
+
void HGraph::ComputeDominanceInformation() {
DCHECK(reverse_post_order_.empty());
reverse_post_order_.reserve(blocks_.size());
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index ad56d31..9fa21d5 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -21,6 +21,7 @@
#include <array>
#include <type_traits>
+#include "base/arena_allocator.h"
#include "base/arena_bit_vector.h"
#include "base/arena_containers.h"
#include "base/arena_object.h"
@@ -387,6 +388,7 @@
blocks_(allocator->Adapter(kArenaAllocBlockList)),
reverse_post_order_(allocator->Adapter(kArenaAllocReversePostOrder)),
linear_order_(allocator->Adapter(kArenaAllocLinearOrder)),
+ reachability_graph_(allocator, 0, 0, true, kArenaAllocReachabilityGraph),
entry_block_(nullptr),
exit_block_(nullptr),
maximum_number_of_out_vregs_(0),
@@ -442,6 +444,8 @@
void ComputeDominanceInformation();
void ClearDominanceInformation();
+ void ComputeReachabilityInformation();
+ void ClearReachabilityInformation();
void ClearLoopInformation();
void FindBackEdges(ArenaBitVector* visited);
GraphAnalysisResult BuildDominatorTree();
@@ -590,6 +594,10 @@
has_bounds_checks_ = value;
}
+ // Returns true if dest is reachable from source, using either blocks or block-ids.
+ bool PathBetween(const HBasicBlock* source, const HBasicBlock* dest) const;
+ bool PathBetween(uint32_t source_id, uint32_t dest_id) const;
+
// Is the code known to be robust against eliminating dead references
// and the effects of early finalization?
bool IsDeadReferenceSafe() const { return dead_reference_safe_; }
@@ -746,6 +754,10 @@
// post order, this order is not incrementally kept up-to-date.
ArenaVector<HBasicBlock*> linear_order_;
+ // Reachability graph for checking connectedness between nodes. Acts as a partitioned vector where
+ // each RoundUp(blocks_.size(), BitVector::kWordBits) is the reachability of each node.
+ ArenaBitVectorArray reachability_graph_;
+
HBasicBlock* entry_block_;
HBasicBlock* exit_block_;
diff --git a/compiler/optimizing/optimizing_compiler_stats.h b/compiler/optimizing/optimizing_compiler_stats.h
index 475c532..4322eb7 100644
--- a/compiler/optimizing/optimizing_compiler_stats.h
+++ b/compiler/optimizing/optimizing_compiler_stats.h
@@ -108,6 +108,11 @@
kConstructorFenceRemovedCFRE,
kBitstringTypeCheck,
kJitOutOfMemoryForCommit,
+ kFullLSEAllocationRemoved,
+ kFullLSEPossible,
+ kNonPartialLoadRemoved,
+ kPartialLSEPossible,
+ kPartialStoreRemoved,
kLastStat
};
std::ostream& operator<<(std::ostream& os, MethodCompilationStat rhs);
diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h
index 792c9db..71acdac 100644
--- a/compiler/optimizing/optimizing_unit_test.h
+++ b/compiler/optimizing/optimizing_unit_test.h
@@ -317,21 +317,23 @@
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);
}
diff --git a/compiler/optimizing/scheduler.cc b/compiler/optimizing/scheduler.cc
index ea5a13a..c1891de 100644
--- a/compiler/optimizing/scheduler.cc
+++ b/compiler/optimizing/scheduler.cc
@@ -560,7 +560,7 @@
// should run the analysis or not.
const HeapLocationCollector* heap_location_collector = nullptr;
ScopedArenaAllocator allocator(graph->GetArenaStack());
- LoadStoreAnalysis lsa(graph, &allocator);
+ LoadStoreAnalysis lsa(graph, /*stats=*/nullptr, &allocator, /*for_elimination=*/false);
if (!only_optimize_loop_blocks_ || graph->HasLoops()) {
lsa.Run();
heap_location_collector = &lsa.GetHeapLocationCollector();
diff --git a/compiler/optimizing/scheduler_test.cc b/compiler/optimizing/scheduler_test.cc
index 94f1599..c166a46 100644
--- a/compiler/optimizing/scheduler_test.cc
+++ b/compiler/optimizing/scheduler_test.cc
@@ -273,7 +273,8 @@
entry->AddInstruction(instr);
}
- HeapLocationCollector heap_location_collector(graph_, GetScopedAllocator());
+ HeapLocationCollector heap_location_collector(
+ graph_, GetScopedAllocator(), /*for_partial_elimination=*/false);
heap_location_collector.VisitBasicBlock(entry);
heap_location_collector.BuildAliasingMatrix();
TestSchedulingGraph scheduling_graph(GetScopedAllocator(), &heap_location_collector);
diff --git a/libartbase/base/arena_allocator.cc b/libartbase/base/arena_allocator.cc
index 0e7f6cc..3438651 100644
--- a/libartbase/base/arena_allocator.cc
+++ b/libartbase/base/arena_allocator.cc
@@ -44,6 +44,7 @@
"BlockList ",
"RevPostOrder ",
"LinearOrder ",
+ "Reachability ",
"ConstantsMap ",
"Predecessors ",
"Successors ",
diff --git a/libartbase/base/arena_allocator.h b/libartbase/base/arena_allocator.h
index a9ccae1..44c3add 100644
--- a/libartbase/base/arena_allocator.h
+++ b/libartbase/base/arena_allocator.h
@@ -53,6 +53,7 @@
kArenaAllocBlockList,
kArenaAllocReversePostOrder,
kArenaAllocLinearOrder,
+ kArenaAllocReachabilityGraph,
kArenaAllocConstantsMap,
kArenaAllocPredecessors,
kArenaAllocSuccessors,
diff --git a/libartbase/base/arena_bit_vector.h b/libartbase/base/arena_bit_vector.h
index 0fb6bbf..a367da8 100644
--- a/libartbase/base/arena_bit_vector.h
+++ b/libartbase/base/arena_bit_vector.h
@@ -18,6 +18,7 @@
#define ART_LIBARTBASE_BASE_ARENA_BIT_VECTOR_H_
#include "arena_object.h"
+#include "base/arena_allocator.h"
#include "bit_vector.h"
namespace art {
@@ -49,8 +50,58 @@
ArenaAllocKind kind = kArenaAllocGrowableBitMap);
~ArenaBitVector() {}
+ ArenaBitVector(ArenaBitVector&&) = default;
+ ArenaBitVector(const ArenaBitVector&) = delete;
+};
+
+// A BitVectorArray implementation that uses Arena allocation. See
+// BitVectorArray for more information.
+// This is a helper for dealing with 2d bit-vector arrays packed into a single
+// bit-vector
+class ArenaBitVectorArray final : public BaseBitVectorArray,
+ public ArenaObject<kArenaAllocGrowableBitMap> {
+ public:
+ ArenaBitVectorArray(const ArenaBitVectorArray& bv) = delete;
+ ArenaBitVectorArray& operator=(const ArenaBitVectorArray& other) = delete;
+
+ explicit ArenaBitVectorArray(ArenaBitVector&& bv) : BaseBitVectorArray(), data_(std::move(bv)) {}
+ ArenaBitVectorArray(ArenaBitVector&& bv, size_t cols)
+ : BaseBitVectorArray(BaseBitVectorArray::MaxRowsFor(bv, cols), cols), data_(std::move(bv)) {}
+
+ ArenaBitVectorArray(ArenaAllocator* allocator,
+ size_t start_rows,
+ size_t start_cols,
+ bool expandable,
+ ArenaAllocKind kind = kArenaAllocGrowableBitMap)
+ : BaseBitVectorArray(start_rows, start_cols),
+ data_(ArenaBitVector(allocator,
+ BaseBitVectorArray::RequiredBitVectorSize(start_rows, start_cols),
+ expandable,
+ kind)) {}
+
+ ArenaBitVectorArray(ScopedArenaAllocator* allocator,
+ size_t start_rows,
+ size_t start_cols,
+ bool expandable,
+ ArenaAllocKind kind = kArenaAllocGrowableBitMap)
+ : BaseBitVectorArray(start_rows, start_cols),
+ data_(ArenaBitVector(allocator,
+ BaseBitVectorArray::RequiredBitVectorSize(start_rows, start_cols),
+ expandable,
+ kind)) {}
+
+ ~ArenaBitVectorArray() override {}
+
+ const BitVector& GetRawData() const override {
+ return data_;
+ }
+
+ BitVector& GetRawData() override {
+ return data_;
+ }
+
private:
- DISALLOW_COPY_AND_ASSIGN(ArenaBitVector);
+ ArenaBitVector data_;
};
} // namespace art
diff --git a/libartbase/base/array_ref.h b/libartbase/base/array_ref.h
index e8b3bce..064e26b 100644
--- a/libartbase/base/array_ref.h
+++ b/libartbase/base/array_ref.h
@@ -203,6 +203,19 @@
return !(lhs == rhs);
}
+template<typename T>
+std::ostream& operator<<(std::ostream& os, const ArrayRef<T>& ts) {
+ bool first = true;
+ os << "[";
+ for (const T& t : ts) {
+ if (!first) { os << ", "; }
+ first = false;
+ os << t;
+ }
+ os << "]";
+ return os;
+}
+
} // namespace art
diff --git a/libartbase/base/array_slice.h b/libartbase/base/array_slice.h
index 4679146..a58ff44 100644
--- a/libartbase/base/array_slice.h
+++ b/libartbase/base/array_slice.h
@@ -17,6 +17,7 @@
#ifndef ART_LIBARTBASE_BASE_ARRAY_SLICE_H_
#define ART_LIBARTBASE_BASE_ARRAY_SLICE_H_
+#include <ostream>
#include "bit_utils.h"
#include "casts.h"
#include "iteration_range.h"
@@ -63,6 +64,10 @@
lpa != nullptr && lpa->size() != 0 ? &lpa->At(0, element_size, alignment) : nullptr,
lpa != nullptr ? lpa->size() : 0,
element_size) {}
+ ArraySlice(const ArraySlice<T>&) = default;
+ ArraySlice(ArraySlice<T>&&) = default;
+ ArraySlice<T>& operator=(const ArraySlice<T>&) = default;
+ ArraySlice<T>& operator=(ArraySlice<T>&&) = default;
// Iterators.
iterator begin() { return iterator(&AtUnchecked(0), element_size_); }
@@ -166,6 +171,19 @@
size_t element_size_;
};
+template<typename T>
+std::ostream& operator<<(std::ostream& os, const ArraySlice<T>& ts) {
+ bool first = true;
+ os << "[";
+ for (const T& t : ts) {
+ if (!first) { os << ", "; }
+ first = false;
+ os << t;
+ }
+ os << "]";
+ return os;
+}
+
} // namespace art
#endif // ART_LIBARTBASE_BASE_ARRAY_SLICE_H_
diff --git a/libartbase/base/bit_vector.cc b/libartbase/base/bit_vector.cc
index 8e3d4c9..d3cb652 100644
--- a/libartbase/base/bit_vector.cc
+++ b/libartbase/base/bit_vector.cc
@@ -376,4 +376,31 @@
return allocator_;
}
+void BaseBitVectorArray::Resize(size_t rows, size_t cols, bool clear) {
+ DCHECK(IsExpandable());
+ if (clear) {
+ Clear();
+ }
+ cols = RoundUp(cols, BitVector::kWordBits);
+ num_columns_ = cols;
+ num_rows_ = rows;
+ // Ensure size
+ GetRawData().SetBit(num_rows_ * num_columns_ - 1);
+ GetRawData().ClearBit(num_rows_ * num_columns_ - 1);
+}
+
+// In order to improve performance we do this in 4-byte blocks. Clang should be
+// able to optimize this to larger blocks if possible.
+void BaseBitVectorArray::UnionRows(size_t dest_row, size_t other) {
+ DCHECK_LT(dest_row, num_rows_);
+ DCHECK_LT(other, num_rows_);
+ size_t block_words = num_columns_ / BitVector::kWordBits;
+ uint32_t* dest =
+ GetRawData().GetRawStorage() + ((dest_row * num_columns_) / BitVector::kWordBits);
+ uint32_t* source = GetRawData().GetRawStorage() + ((other * num_columns_) / BitVector::kWordBits);
+ for (uint32_t i = 0; i < block_words; ++i, ++dest, ++source) {
+ *dest = (*dest) | (*source);
+ }
+}
+
} // namespace art
diff --git a/libartbase/base/bit_vector.h b/libartbase/base/bit_vector.h
index dc15874..0c735cc 100644
--- a/libartbase/base/bit_vector.h
+++ b/libartbase/base/bit_vector.h
@@ -18,6 +18,7 @@
#define ART_LIBARTBASE_BASE_BIT_VECTOR_H_
#include <stdint.h>
+
#include <iterator>
#include "bit_utils.h"
@@ -26,6 +27,7 @@
namespace art {
class Allocator;
+class ArenaBitVector;
/*
* Expanding bitmap, used for tracking resources. Bits are numbered starting
@@ -33,6 +35,9 @@
*/
class BitVector {
public:
+ static constexpr uint32_t kWordBytes = sizeof(uint32_t);
+ static constexpr uint32_t kWordBits = kWordBytes * 8;
+
class IndexContainer;
/**
@@ -226,11 +231,22 @@
return storage_size_ * kWordBytes;
}
+ size_t GetBitSizeOf() const {
+ return storage_size_ * kWordBits;
+ }
+
/**
* @return the highest bit set, -1 if none are set
*/
int GetHighestBitSet() const;
+ /**
+ * @return true if there are any bits set, false otherwise.
+ */
+ bool IsAnyBitSet() const {
+ return GetHighestBitSet() != -1;
+ }
+
// Minimum number of bits required to store this vector, 0 if none are set.
size_t GetNumberOfBits() const {
return GetHighestBitSet() + 1;
@@ -281,15 +297,148 @@
return 1 << (idx & 0x1f);
}
- static constexpr uint32_t kWordBytes = sizeof(uint32_t);
- static constexpr uint32_t kWordBits = kWordBytes * 8;
-
uint32_t* storage_; // The storage for the bit vector.
uint32_t storage_size_; // Current size, in 32-bit words.
Allocator* const allocator_; // Allocator if expandable.
const bool expandable_; // Should the bitmap expand if too small?
};
+// Helper for dealing with 2d bit-vector arrays packed into a single bit-vec
+class BaseBitVectorArray {
+ public:
+ BaseBitVectorArray(const BaseBitVectorArray& bv) = default;
+ BaseBitVectorArray& operator=(const BaseBitVectorArray& other) = default;
+
+ BaseBitVectorArray() : num_columns_(0), num_rows_(0) {}
+
+ BaseBitVectorArray(size_t num_rows, size_t num_columns)
+ : num_columns_(RoundUp(num_columns, BitVector::kWordBits)), num_rows_(num_rows) {}
+
+ virtual ~BaseBitVectorArray() {}
+
+ bool IsExpandable() const {
+ return GetRawData().IsExpandable();
+ }
+
+ // Let subclasses provide storage for various types.
+ virtual const BitVector& GetRawData() const = 0;
+ virtual BitVector& GetRawData() = 0;
+
+ size_t NumRows() const {
+ return num_rows_;
+ }
+
+ // NB This might be more than the requested size for alignment purposes.
+ size_t NumColumns() const {
+ return num_columns_;
+ }
+
+ void Clear() {
+ GetRawData().ClearAllBits();
+ }
+
+ // Ensure that we can set all bits in the given range. The actual number of
+ // columns might be larger than requested for alignment purposes.
+ void Resize(size_t rows, size_t cols, bool clear = true);
+
+ void SetBit(size_t row, size_t col) {
+ DCHECK_LT(col, num_columns_);
+ DCHECK_LT(row, num_rows_);
+ GetRawData().SetBit(row * num_columns_ + col);
+ }
+
+ void ClearBit(size_t row, size_t col) {
+ DCHECK_LT(col, num_columns_);
+ DCHECK_LT(row, num_rows_);
+ GetRawData().ClearBit(row * num_columns_ + col);
+ }
+
+ bool IsBitSet(size_t row, size_t col) const {
+ DCHECK_LT(col, num_columns_);
+ DCHECK_LT(row, num_rows_);
+ return GetRawData().IsBitSet(row * num_columns_ + col);
+ }
+
+ // Union the vector of 'other' into 'dest_row'.
+ void UnionRows(size_t dest_row, size_t other);
+
+ static size_t RequiredBitVectorSize(size_t rows, size_t cols) {
+ return rows * RoundUp(cols, BitVector::kWordBits);
+ }
+
+ static size_t MaxRowsFor(const BitVector& bv, size_t cols) {
+ return cols != 0 ? bv.GetBitSizeOf() / RoundUp(cols, BitVector::kWordBits) : 0;
+ }
+
+ private:
+ size_t num_columns_;
+ size_t num_rows_;
+};
+
+// A BitVectorArray with a standard owned BitVector providing the backing
+// storage. This should be used when the BitVectorArray is the owner of the
+// whole BitVector and should use standard allocators for cleanup/allocation.
+// Contrast this with ArenaBitVectorArray which uses arena allocators.
+class BitVectorArray final : public BaseBitVectorArray {
+ public:
+ BitVectorArray(const BitVectorArray& bv) = delete;
+ BitVectorArray& operator=(const BitVectorArray& other) = delete;
+
+ explicit BitVectorArray(BitVector&& bv) : BaseBitVectorArray(), data_(std::move(bv)) {}
+ explicit BitVectorArray(BitVector&& bv, size_t cols)
+ : BaseBitVectorArray(BaseBitVectorArray::MaxRowsFor(bv, cols), cols), data_(std::move(bv)) {}
+ explicit BitVectorArray(BitVector&& bv, size_t rows, size_t cols)
+ : BaseBitVectorArray(rows, cols), data_(std::move(bv)) {}
+
+ BitVectorArray(uint32_t start_rows, uint32_t start_cols, bool expandable, Allocator* allocator)
+ : BaseBitVectorArray(start_rows, start_cols),
+ data_(BaseBitVectorArray::RequiredBitVectorSize(start_rows, start_cols),
+ expandable,
+ allocator) {}
+
+ BitVectorArray(const BaseBitVectorArray& src, bool expandable, Allocator* allocator)
+ : BaseBitVectorArray(src.NumRows(), src.NumColumns()),
+ data_(src.GetRawData(), expandable, allocator) {}
+
+ ~BitVectorArray() override {}
+
+ const BitVector& GetRawData() const override {
+ return data_;
+ }
+
+ BitVector& GetRawData() override {
+ return data_;
+ }
+
+ private:
+ BitVector data_;
+};
+
+// A bit vector array that uses an unowned BitVector reference as it's backing
+// data.
+class BitVectorArrayWrapper final : public BaseBitVectorArray {
+ public:
+ BitVectorArrayWrapper& operator=(BitVectorArrayWrapper& other) = default;
+ BitVectorArrayWrapper(BitVectorArrayWrapper&) = default;
+ explicit BitVectorArrayWrapper(BitVector* bv) : BaseBitVectorArray(), data_(bv) {}
+ explicit BitVectorArrayWrapper(BitVector* bv, size_t cols)
+ : BaseBitVectorArray(BaseBitVectorArray::MaxRowsFor(*bv, cols), cols), data_(bv) {}
+ explicit BitVectorArrayWrapper(BitVector* bv, size_t rows, size_t cols)
+ : BaseBitVectorArray(rows, cols), data_(bv) {}
+
+ ~BitVectorArrayWrapper() override {}
+
+ const BitVector& GetRawData() const override {
+ return *data_;
+ }
+
+ BitVector& GetRawData() override {
+ return *data_;
+ }
+
+ private:
+ BitVector* data_;
+};
} // namespace art
diff --git a/libartbase/base/bit_vector_test.cc b/libartbase/base/bit_vector_test.cc
index 2ef81c6..5f1b167 100644
--- a/libartbase/base/bit_vector_test.cc
+++ b/libartbase/base/bit_vector_test.cc
@@ -15,11 +15,13 @@
*/
#include <memory>
+#include <random>
#include "allocator.h"
+#include "base/stl_util.h"
#include "bit_vector-inl.h"
-#include "transform_iterator.h"
#include "gtest/gtest.h"
+#include "transform_iterator.h"
namespace art {
@@ -363,4 +365,58 @@
EXPECT_EQ(alloc.AllocCount(), 1u);
}
+TEST(BitVector, ArrayCol) {
+ {
+ BitVectorArray bva(100, 200, true, Allocator::GetMallocAllocator());
+ for (uint32_t i : Range(bva.NumColumns())) {
+ bva.SetBit(bva.NumRows() / 2, i);
+ }
+ EXPECT_EQ(bva.GetRawData().NumSetBits(), bva.NumColumns());
+ }
+ {
+ BitVectorArray bva(100, 200, true, Allocator::GetMallocAllocator());
+ for (uint32_t i : Range(bva.NumRows())) {
+ bva.SetBit(i, bva.NumColumns() / 2);
+ }
+ EXPECT_EQ(bva.GetRawData().NumSetBits(), bva.NumRows());
+ }
+}
+
+TEST(BitVector, ArrayUnion) {
+ {
+ BitVectorArray bva(100, 200, true, Allocator::GetMallocAllocator());
+ bva.SetBit(4, 12);
+ bva.SetBit(40, 120);
+ bva.SetBit(40, 121);
+ bva.SetBit(40, 122);
+
+ bva.UnionRows(4, 40);
+
+ EXPECT_TRUE(bva.IsBitSet(4, 12));
+ EXPECT_TRUE(bva.IsBitSet(4, 120));
+ EXPECT_TRUE(bva.IsBitSet(4, 121));
+ EXPECT_TRUE(bva.IsBitSet(4, 122));
+ EXPECT_FALSE(bva.IsBitSet(40, 12));
+ EXPECT_TRUE(bva.IsBitSet(40, 120));
+ EXPECT_TRUE(bva.IsBitSet(40, 121));
+ EXPECT_TRUE(bva.IsBitSet(40, 122));
+ EXPECT_EQ(bva.GetRawData().NumSetBits(), 7u);
+ }
+ {
+ BitVectorArray bva(100, 100, true, Allocator::GetMallocAllocator());
+ for (uint32_t i : Range(bva.NumRows())) {
+ bva.SetBit(i, i);
+ }
+ for (uint32_t i : Range(1, bva.NumRows())) {
+ bva.UnionRows(0, i);
+ }
+ for (uint32_t col : Range(bva.NumColumns())) {
+ for (uint32_t row : Range(bva.NumRows())) {
+ // We set every bit where row== column and every bit on row 0 up to number of rows.
+ EXPECT_EQ(bva.IsBitSet(row, col), row == col || (row == 0 && col < bva.NumRows()));
+ }
+ }
+ }
+}
+
} // namespace art
diff --git a/libartbase/base/hash_map.h b/libartbase/base/hash_map.h
index 7d01892..32c232a 100644
--- a/libartbase/base/hash_map.h
+++ b/libartbase/base/hash_map.h
@@ -81,6 +81,13 @@
HashMap() : Base() { }
explicit HashMap(const Alloc& alloc)
: Base(alloc) { }
+
+ // Used to insert a new mapping.
+ typename Base::iterator Overwrite(const Key& k, const Value& v) {
+ auto res = Base::insert({ k, v }).first;
+ *res = { k, v };
+ return res;
+ }
};
} // namespace art
diff --git a/libartbase/base/iteration_range.h b/libartbase/base/iteration_range.h
index eaed8b0..c916250 100644
--- a/libartbase/base/iteration_range.h
+++ b/libartbase/base/iteration_range.h
@@ -18,6 +18,7 @@
#define ART_LIBARTBASE_BASE_ITERATION_RANGE_H_
#include <iterator>
+#include <type_traits>
namespace art {
@@ -49,9 +50,11 @@
return IterationRange<Iter>(begin_it, end_it);
}
-template<typename List>
-inline IterationRange<typename List::iterator> MakeIterationRange(List& list) {
- return IterationRange<typename List::iterator>(list.begin(), list.end());
+template <typename List>
+inline auto MakeIterationRange(List& list) -> IterationRange<decltype(list.begin())> {
+ static_assert(std::is_same_v<decltype(list.begin()), decltype(list.end())>,
+ "Different iterator types");
+ return MakeIterationRange(list.begin(), list.end());
}
template <typename Iter>
diff --git a/libartbase/base/stl_util.h b/libartbase/base/stl_util.h
index cd7b812..503dfee 100644
--- a/libartbase/base/stl_util.h
+++ b/libartbase/base/stl_util.h
@@ -229,6 +229,64 @@
ZipLeftIter(iter_left.end(), iter_right.end()));
}
+static inline IterationRange<CountIter> Range(size_t start, size_t end) {
+ return IterationRange(CountIter(start), CountIter(end));
+}
+
+static inline IterationRange<CountIter> Range(size_t end) {
+ return Range(0, end);
+}
+
+template <typename RealIter, typename Filter>
+struct FilterIterator
+ : public std::iterator<std::forward_iterator_tag, typename RealIter::value_type> {
+ public:
+ FilterIterator(RealIter rl,
+ Filter cond,
+ std::optional<RealIter> end = std::nullopt)
+ : real_iter_(rl), cond_(cond), end_(end) {
+ DCHECK(std::make_optional(rl) == end_ || cond_(*real_iter_));
+ }
+
+ FilterIterator<RealIter, Filter>& operator++() {
+ DCHECK(std::make_optional(real_iter_) != end_);
+ do {
+ if (std::make_optional(++real_iter_) == end_) {
+ break;
+ }
+ } while (!cond_(*real_iter_));
+ return *this;
+ }
+ FilterIterator<RealIter, Filter> operator++(int) {
+ FilterIterator<RealIter, Filter> ret(real_iter_, cond_, end_);
+ ++(*this);
+ return ret;
+ }
+ bool operator==(const FilterIterator<RealIter, Filter>& other) const {
+ return real_iter_ == other.real_iter_;
+ }
+ bool operator!=(const FilterIterator<RealIter, Filter>& other) const {
+ return !(*this == other);
+ }
+ typename RealIter::value_type operator*() const {
+ return *real_iter_;
+ }
+
+ private:
+ RealIter real_iter_;
+ Filter cond_;
+ std::optional<RealIter> end_;
+};
+
+template <typename Iter, typename Filter>
+static inline IterationRange<FilterIterator<Iter, Filter>> Filter(
+ IterationRange<Iter> it, Filter cond) {
+ auto end = it.end();
+ auto start = std::find_if(it.begin(), end, cond);
+ return MakeIterationRange(FilterIterator(start, cond, std::make_optional(end)),
+ FilterIterator(end, cond, std::make_optional(end)));
+}
+
} // namespace art
#endif // ART_LIBARTBASE_BASE_STL_UTIL_H_
diff --git a/test/530-checker-lse/src/Main.java b/test/530-checker-lse/src/Main.java
index b2ae3a1..f250aa5 100644
--- a/test/530-checker-lse/src/Main.java
+++ b/test/530-checker-lse/src/Main.java
@@ -84,6 +84,12 @@
public class Main {
+ static Object ESCAPE = null;
+ static void $noinline$Escape(TestClass o) {
+ ESCAPE = o;
+ o.next.i++;
+ }
+
/// CHECK-START: double Main.calcCircleArea(double) load_store_elimination (before)
/// CHECK: NewInstance
/// CHECK: InstanceFieldSet
@@ -3728,6 +3734,65 @@
return t;
}
+ private static boolean $noinline$getBoolean(boolean val) {
+ return val;
+ }
+
+ /// CHECK-START: int Main.$noinline$testPartialEscape1(TestClass, boolean) load_store_elimination (before)
+ /// CHECK-DAG: ParameterValue
+ /// CHECK-DAG: NewInstance
+ /// CHECK-DAG: InvokeStaticOrDirect
+ /// CHECK-DAG: InstanceFieldSet
+ /// CHECK-DAG: InvokeStaticOrDirect
+ /// CHECK-DAG: InstanceFieldGet
+ /// CHECK-DAG: InstanceFieldGet
+ /// CHECK-DAG: InstanceFieldSet
+ /// CHECK-DAG: InstanceFieldGet
+ /// CHECK-DAG: InstanceFieldGet
+ /// CHECK-DAG: Phi
+ //
+ /// CHECK-NOT: NewInstance
+ /// CHECK-NOT: InvokeStaticOrDirect
+ /// CHECK-NOT: InstanceFieldSet
+ /// CHECK-NOT: InstanceFieldGet
+ //
+ /// CHECK-START: int Main.$noinline$testPartialEscape1(TestClass, boolean) load_store_elimination (after)
+ /// CHECK-DAG: ParameterValue
+ /// CHECK-DAG: NewInstance
+ /// CHECK-DAG: Phi
+ //
+ /// CHECK-START: int Main.$noinline$testPartialEscape1(TestClass, boolean) load_store_elimination (after)
+ /// CHECK: InvokeStaticOrDirect
+ /// CHECK: InvokeStaticOrDirect
+ //
+ /// CHECK-NOT: InvokeStaticOrDirect
+
+ /// CHECK-START: int Main.$noinline$testPartialEscape1(TestClass, boolean) load_store_elimination (after)
+ /// CHECK: InstanceFieldSet
+ //
+ /// CHECK-NOT: InstanceFieldSet
+ //
+ /// CHECK-START: int Main.$noinline$testPartialEscape1(TestClass, boolean) load_store_elimination (after)
+ /// CHECK: InstanceFieldGet
+ /// CHECK: InstanceFieldGet
+ /// CHECK: InstanceFieldGet
+ //
+ /// CHECK-NOT: InstanceFieldGet
+ private static int $noinline$testPartialEscape1(TestClass obj, boolean escape) {
+ TestClass i = new SubTestClass();
+ int res;
+ if ($noinline$getBoolean(escape)) {
+ i.next = obj;
+ $noinline$Escape(i);
+ res = i.next.i;
+ } else {
+ i.next = obj;
+ res = i.next.i;
+ }
+ return res;
+ }
+
+
private static void $noinline$clobberObservables() {}
static void assertLongEquals(long result, long expected) {
@@ -4129,5 +4194,7 @@
assertIntEquals(testNestedLoop8(new TestClass(), 3), 0);
assertLongEquals(testOverlapLoop(10), 34l);
assertLongEquals(testOverlapLoop(50), 7778742049l);
+ assertIntEquals($noinline$testPartialEscape1(new TestClass(), true), 1);
+ assertIntEquals($noinline$testPartialEscape1(new TestClass(), false), 0);
}
}