Revert^4 "Partial LSE analysis & store removal"
We incorrectly handled merging unknowns in some situations.
Specifically in cases where we are unable to materialize loop-phis we
could end up with PureUnknowns which could end up hiding stores that
need to be kept.
In an unrelated issue we were incorrectly considering some values as
escapes when live at the point of an invoke. Since
SearchPhiPlaceholdersForKeptStores used a more precise notion of
escapes we could end up removing stores without being able to replace
the values.
This reverts commit 2316b3a0779f3721a78681f5c70ed6624ecaebef.
This unreverts commit b6837f0350ff66c13582b0e94178dd5ca283ff0a
This reverts commit fe270426c8a2a69a8f669339e83b86fbf40e25a1.
This unreverts commit bb6cda60e4418c0ab557ea4090e046bed8206763.
Bug: 67037140
Bug: 173120044
Reason for revert: Fixed issue causing incorrect store elimination
Test: ./test.py --host
Test: Boot cuttlefish
atest FrameworksServicesTests:com.android.server.job.BackgroundRestrictionsTest#testPowerWhiteList
Change-Id: I2ebae9ccfaf5169d551c5019b547589d0fce1dc9
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..0110134 100644
--- a/compiler/optimizing/load_store_elimination.cc
+++ b/compiler/optimizing/load_store_elimination.cc
@@ -16,15 +16,20 @@
#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 "execution_subgraph.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 +263,7 @@
enum class Type {
kInvalid,
kUnknown,
+ kMergedUnknown,
kDefault,
kInstruction,
kNeedsNonLoopPhi,
@@ -282,6 +288,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 +338,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 +376,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 +405,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 +415,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 +437,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 +599,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 +627,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 +840,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();
}
@@ -804,7 +866,23 @@
heap_values_for_[instruction->GetBlock()->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->IsSingleton()) {
+ ArrayRef<const ExecutionSubgraph::ExcludedCohort> cohorts =
+ ref_info->GetNoEscapeSubgraph()->GetExcludedCohorts();
+ HBasicBlock* blk = instruction->GetBlock();
+ // We don't need to do anything if the reference has not escaped at this point.
+ // This is true if either we (1) never escape or (2) sometimes escape but
+ // there is no possible execution where we have done so at this time. NB
+ // We count being in the excluded cohort as escaping. Technically, this is
+ // a bit over-conservative (since we can have multiple non-escaping calls
+ // before a single escaping one) but this simplifies everything greatly.
+ if (ref_info->IsSingleton() ||
+ // partial and we aren't currently escaping and we haven't escaped yet.
+ (ref_info->IsPartialSingleton() && ref_info->GetNoEscapeSubgraph()->ContainsBlock(blk) &&
+ std::none_of(cohorts.begin(),
+ cohorts.end(),
+ [&](const ExecutionSubgraph::ExcludedCohort& cohort) {
+ return cohort.PrecedesBlock(blk);
+ }))) {
// Singleton references cannot be seen by the callee.
} else {
if (side_effects.DoesAnyRead() || side_effects.DoesAnyWrite()) {
@@ -953,11 +1031,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 +1143,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 +1164,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 +1233,20 @@
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)) {
+ // 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.
@@ -1130,6 +1254,8 @@
merged_value = ReplacementOrValue(Value::ForPhiPlaceholder(phi_placeholder, needs_loop_phi));
}
}
+ DCHECK(!merged_value.IsPureUnknown() || block->GetPredecessors().size() <= 1)
+ << merged_value << " in " << GetGraph()->PrettyMethod();
return merged_value;
}
@@ -1247,7 +1373,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 +1414,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));
@@ -1864,7 +1993,8 @@
void LSEVisitor::ProcessLoopPhiWithUnknownInput(const PhiPlaceholder* loop_phi_with_unknown_input) {
size_t loop_phi_with_unknown_input_index = PhiPlaceholderIndex(loop_phi_with_unknown_input);
DCHECK(phi_placeholder_replacements_[loop_phi_with_unknown_input_index].IsInvalid());
- phi_placeholder_replacements_[loop_phi_with_unknown_input_index] = Value::Unknown();
+ phi_placeholder_replacements_[loop_phi_with_unknown_input_index] =
+ Value::MergedUnknown(loop_phi_with_unknown_input);
uint32_t block_id = loop_phi_with_unknown_input->GetBlockId();
const ArenaVector<HBasicBlock*> reverse_post_order = GetGraph()->GetReversePostOrder();
@@ -1895,7 +2025,8 @@
Value value;
if (block->IsLoopHeader()) {
if (block->GetLoopInformation()->IsIrreducible()) {
- value = Value::Unknown();
+ const PhiPlaceholder* placeholder = GetPhiPlaceholder(block->GetBlockId(), idx);
+ value = Value::MergedUnknown(placeholder);
} else {
value = PrepareLoopValue(block, idx);
}
@@ -2047,8 +2178,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 +2236,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 +2439,7 @@
if (!new_instance->HasNonEnvironmentUses()) {
new_instance->RemoveEnvironmentUsers();
new_instance->GetBlock()->RemoveInstruction(new_instance);
+ MaybeRecordStat(stats_, MethodCompilationStat::kFullLSEAllocationRemoved);
}
}
}
@@ -2284,8 +2451,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..55620bb 100644
--- a/compiler/optimizing/load_store_elimination_test.cc
+++ b/compiler/optimizing/load_store_elimination_test.cc
@@ -27,11 +27,19 @@
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);
lse.Run();
- EXPECT_TRUE(CheckGraphSkipRefTypeInfoChecks());
+ std::ostringstream oss;
+ EXPECT_TRUE(CheckGraphSkipRefTypeInfoChecks(oss)) << oss.str();
}
// Create instructions shared among tests.
@@ -1442,4 +1450,2061 @@
EXPECT_TRUE(IsRemoved(alloc_w));
}
+// // ENTRY
+// obj = new Obj();
+// // ALL should be kept
+// switch (parameter_value) {
+// case 1:
+// // Case1
+// obj.field = 1;
+// call_func(obj);
+// break;
+// case 2:
+// // Case2
+// obj.field = 2;
+// call_func(obj);
+// // We don't know what obj.field is now we aren't able to eliminate the read below!
+// break;
+// default:
+// // Case3
+// // TODO This only happens because of limitations on our LSE which is unable
+// // to materialize co-dependent loop and non-loop phis.
+// // Ideally we'd want to generate
+// // P1 = PHI[3, loop_val]
+// // while (test()) {
+// // if (test2()) { goto; } else { goto; }
+// // loop_val = [P1, 5]
+// // }
+// // Currently we aren't able to unfortunately.
+// obj.field = 3;
+// while (test()) {
+// if (test2()) { } else { obj.field = 5; }
+// }
+// break;
+// }
+// EXIT
+// return obj.field
+TEST_F(LoadStoreEliminationTest, PartialUnknownMerge) {
+ CreateGraph();
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
+ "exit",
+ { { "entry", "bswitch" },
+ { "bswitch", "case1" },
+ { "bswitch", "case2" },
+ { "bswitch", "case3" },
+ { "case1", "breturn" },
+ { "case2", "breturn" },
+ { "case3", "loop_pre_header" },
+ { "loop_pre_header", "loop_header" },
+ { "loop_header", "loop_body" },
+ { "loop_body", "loop_if_left" },
+ { "loop_body", "loop_if_right" },
+ { "loop_if_left", "loop_end" },
+ { "loop_if_right", "loop_end" },
+ { "loop_end", "loop_header" },
+ { "loop_header", "breturn" },
+ { "breturn", "exit" } }));
+#define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
+ GET_BLOCK(entry);
+ GET_BLOCK(bswitch);
+ GET_BLOCK(exit);
+ GET_BLOCK(breturn);
+ GET_BLOCK(case1);
+ GET_BLOCK(case2);
+ GET_BLOCK(case3);
+
+ GET_BLOCK(loop_pre_header);
+ GET_BLOCK(loop_header);
+ GET_BLOCK(loop_body);
+ GET_BLOCK(loop_if_left);
+ GET_BLOCK(loop_if_right);
+ GET_BLOCK(loop_end);
+#undef GET_BLOCK
+ HInstruction* switch_val = new (GetAllocator())
+ HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32);
+ HInstruction* c1 = graph_->GetIntConstant(1);
+ HInstruction* c2 = graph_->GetIntConstant(2);
+ HInstruction* c3 = graph_->GetIntConstant(3);
+ HInstruction* c5 = graph_->GetIntConstant(5);
+ 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* entry_goto = new (GetAllocator()) HGoto();
+ entry->AddInstruction(switch_val);
+ entry->AddInstruction(cls);
+ entry->AddInstruction(new_inst);
+ entry->AddInstruction(entry_goto);
+ ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
+ ManuallyBuildEnvFor(cls, ¤t_locals);
+ new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* switch_inst = new (GetAllocator()) HPackedSwitch(0, 2, switch_val);
+ bswitch->AddInstruction(switch_inst);
+
+ HInstruction* write_c1 = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c1,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* call_c1 = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 1,
+ DataType::Type::kVoid,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* goto_c1 = new (GetAllocator()) HGoto();
+ call_c1->AsInvoke()->SetRawInputAt(0, new_inst);
+ case1->AddInstruction(write_c1);
+ case1->AddInstruction(call_c1);
+ case1->AddInstruction(goto_c1);
+ call_c1->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* write_c2 = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c2,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* call_c2 = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 1,
+ DataType::Type::kVoid,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* goto_c2 = new (GetAllocator()) HGoto();
+ call_c2->AsInvoke()->SetRawInputAt(0, new_inst);
+ case2->AddInstruction(write_c2);
+ case2->AddInstruction(call_c2);
+ case2->AddInstruction(goto_c2);
+ call_c2->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* write_c3 = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c3,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_c3 = new (GetAllocator()) HGoto();
+ case3->AddInstruction(write_c3);
+ case3->AddInstruction(goto_c3);
+
+ HInstruction* goto_preheader = new (GetAllocator()) HGoto();
+ loop_pre_header->AddInstruction(goto_preheader);
+
+ HInstruction* suspend_check_header = new (GetAllocator()) HSuspendCheck();
+ HInstruction* call_loop_header = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 0,
+ DataType::Type::kBool,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* if_loop_header = new (GetAllocator()) HIf(call_loop_header);
+ loop_header->AddInstruction(suspend_check_header);
+ loop_header->AddInstruction(call_loop_header);
+ loop_header->AddInstruction(if_loop_header);
+ call_loop_header->CopyEnvironmentFrom(cls->GetEnvironment());
+ suspend_check_header->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* call_loop_body = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 0,
+ DataType::Type::kBool,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* if_loop_body = new (GetAllocator()) HIf(call_loop_body);
+ loop_body->AddInstruction(call_loop_body);
+ loop_body->AddInstruction(if_loop_body);
+ call_loop_body->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* goto_loop_left = new (GetAllocator()) HGoto();
+ loop_if_left->AddInstruction(goto_loop_left);
+
+ HInstruction* write_loop_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c5,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* goto_loop_right = new (GetAllocator()) HGoto();
+ loop_if_right->AddInstruction(write_loop_right);
+ loop_if_right->AddInstruction(goto_loop_right);
+
+ HInstruction* goto_loop_end = new (GetAllocator()) HGoto();
+ loop_end->AddInstruction(goto_loop_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);
+ breturn->AddInstruction(read_bottom);
+ breturn->AddInstruction(return_exit);
+
+ HInstruction* exit_ins = new (GetAllocator()) HExit();
+ exit->AddInstruction(exit_ins);
+ // PerformLSE expects this to be empty.
+ graph_->ClearDominanceInformation();
+ PerformLSE();
+
+ EXPECT_FALSE(IsRemoved(read_bottom));
+ EXPECT_FALSE(IsRemoved(write_c1));
+ EXPECT_FALSE(IsRemoved(write_c2));
+ EXPECT_FALSE(IsRemoved(write_c3));
+ // EXPECT_FALSE(IsRemoved(write_loop_left));
+ EXPECT_FALSE(IsRemoved(write_loop_right));
+}
+
+// // 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();
+
+ EXPECT_TRUE(IsRemoved(read_bottom));
+ EXPECT_TRUE(IsRemoved(write_right));
+ EXPECT_FALSE(IsRemoved(write_left));
+ EXPECT_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
+// escape(obj);
+// obj.field = 1;
+// } else {
+// // RIGHT
+// // obj hasn't escaped so it's invisible.
+// // ELIMINATE
+// obj.field = 2;
+// noescape();
+// }
+// EXIT
+// ELIMINATE
+// return obj.field
+TEST_F(LoadStoreEliminationTest, PartialLoadElimination5) {
+ 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* call_right = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 0,
+ DataType::Type::kVoid,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* goto_right = new (GetAllocator()) HGoto();
+ right->AddInstruction(write_right);
+ right->AddInstruction(call_right);
+ right->AddInstruction(goto_right);
+ call_right->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ 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();
+
+ EXPECT_TRUE(IsRemoved(read_bottom));
+ EXPECT_TRUE(IsRemoved(write_right));
+ EXPECT_FALSE(IsRemoved(write_left));
+ EXPECT_FALSE(IsRemoved(call_left));
+ EXPECT_FALSE(IsRemoved(call_right));
+}
+
+// // ENTRY
+// obj = new Obj();
+// // Eliminate this one. Object hasn't escaped yet so it's safe.
+// obj.field = 3;
+// noescape();
+// if (parameter_value) {
+// // LEFT
+// // DO NOT ELIMINATE
+// obj.field = 5;
+// escape(obj);
+// obj.field = 1;
+// } else {
+// // RIGHT
+// // ELIMINATE
+// obj.field = 2;
+// }
+// EXIT
+// ELIMINATE
+// return obj.field
+TEST_F(LoadStoreEliminationTest, PartialLoadElimination6) {
+ 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* c3 = graph_->GetIntConstant(3);
+ HInstruction* c5 = graph_->GetIntConstant(5);
+ 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,
+ c3,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* call_entry = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 0,
+ DataType::Type::kVoid,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ 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(call_entry);
+ entry->AddInstruction(if_inst);
+ ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
+ ManuallyBuildEnvFor(cls, ¤t_locals);
+ new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
+ call_entry->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* write_left_start = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c5,
+ 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* 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(write_left_start);
+ 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();
+
+ EXPECT_TRUE(IsRemoved(read_bottom));
+ EXPECT_TRUE(IsRemoved(write_right));
+ EXPECT_TRUE(IsRemoved(write_entry));
+ EXPECT_FALSE(IsRemoved(write_left_start));
+ EXPECT_FALSE(IsRemoved(write_left));
+ EXPECT_FALSE(IsRemoved(call_left));
+ EXPECT_FALSE(IsRemoved(call_entry));
+}
+
+// // 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));
+}
+
+// // ENTRY
+// obj = new Obj();
+// if (parameter_value) {
+// // LEFT
+// // DO NOT ELIMINATE
+// escape(obj);
+// obj.field = 1;
+// // obj has already escaped so can't use field = 1 for value
+// noescape();
+// } else {
+// // RIGHT
+// // obj is needed for read since we don't know what the left value is
+// // DO NOT ELIMINATE
+// obj.field = 2;
+// noescape();
+// }
+// EXIT
+// ELIMINATE
+// return obj.field
+TEST_F(LoadStoreEliminationTest, PartialLoadPreserved5) {
+ 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* call2_left = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 0,
+ 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(write_left);
+ left->AddInstruction(call2_left);
+ left->AddInstruction(goto_left);
+ call_left->CopyEnvironmentFrom(cls->GetEnvironment());
+ call2_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* call_right = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 0,
+ DataType::Type::kVoid,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ HInstruction* goto_right = new (GetAllocator()) HGoto();
+ right->AddInstruction(write_right);
+ right->AddInstruction(call_right);
+ right->AddInstruction(goto_right);
+ call_right->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ 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();
+
+ EXPECT_FALSE(IsRemoved(read_bottom));
+ EXPECT_FALSE(IsRemoved(write_right));
+ EXPECT_FALSE(IsRemoved(write_left));
+ EXPECT_FALSE(IsRemoved(call_left));
+ EXPECT_FALSE(IsRemoved(call_right));
+}
+
+// // ENTRY
+// obj = new Obj();
+// DO NOT ELIMINATE. Kept by escape.
+// obj.field = 3;
+// noescape();
+// 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, PartialLoadPreserved6) {
+ 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* 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* write_entry = new (GetAllocator()) HInstanceFieldSet(new_inst,
+ c3,
+ nullptr,
+ DataType::Type::kInt32,
+ MemberOffset(10),
+ false,
+ 0,
+ 0,
+ graph_->GetDexFile(),
+ 0);
+ HInstruction* call_entry = new (GetAllocator())
+ HInvokeStaticOrDirect(GetAllocator(),
+ 0,
+ DataType::Type::kVoid,
+ 0,
+ { nullptr, 0 },
+ nullptr,
+ {},
+ InvokeType::kStatic,
+ { nullptr, 0 },
+ HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
+ 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(call_entry);
+ entry->AddInstruction(if_inst);
+ ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
+ ManuallyBuildEnvFor(cls, ¤t_locals);
+ new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
+ call_entry->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();
+
+ EXPECT_TRUE(IsRemoved(read_bottom));
+ EXPECT_TRUE(IsRemoved(write_right));
+ EXPECT_FALSE(IsRemoved(write_entry));
+ EXPECT_FALSE(IsRemoved(write_left));
+ EXPECT_FALSE(IsRemoved(call_left));
+ EXPECT_FALSE(IsRemoved(call_entry));
+}
+
} // 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..89b606d 100644
--- a/compiler/optimizing/optimizing_unit_test.h
+++ b/compiler/optimizing/optimizing_unit_test.h
@@ -213,23 +213,23 @@
// Run GraphChecker with all checks.
//
// Return: the status whether the run is successful.
- bool CheckGraph(HGraph* graph) {
- return CheckGraph(graph, /*check_ref_type_info=*/true);
+ bool CheckGraph(HGraph* graph, std::ostream& oss = std::cerr) {
+ return CheckGraph(graph, /*check_ref_type_info=*/true, oss);
}
- bool CheckGraph() {
- return CheckGraph(graph_);
+ bool CheckGraph(std::ostream& oss = std::cerr) {
+ return CheckGraph(graph_, oss);
}
// Run GraphChecker with all checks except reference type information checks.
//
// Return: the status whether the run is successful.
- bool CheckGraphSkipRefTypeInfoChecks(HGraph* graph) {
- return CheckGraph(graph, /*check_ref_type_info=*/false);
+ bool CheckGraphSkipRefTypeInfoChecks(HGraph* graph, std::ostream& oss = std::cerr) {
+ return CheckGraph(graph, /*check_ref_type_info=*/false, oss);
}
- bool CheckGraphSkipRefTypeInfoChecks() {
- return CheckGraphSkipRefTypeInfoChecks(graph_);
+ bool CheckGraphSkipRefTypeInfoChecks(std::ostream& oss = std::cerr) {
+ return CheckGraphSkipRefTypeInfoChecks(graph_, oss);
}
HEnvironment* ManuallyBuildEnvFor(HInstruction* instruction,
@@ -247,11 +247,11 @@
}
protected:
- bool CheckGraph(HGraph* graph, bool check_ref_type_info) {
+ bool CheckGraph(HGraph* graph, bool check_ref_type_info, std::ostream& oss) {
GraphChecker checker(graph);
checker.SetRefTypeInfoCheckEnabled(check_ref_type_info);
checker.Run();
- checker.Dump(std::cerr);
+ checker.Dump(oss);
return checker.IsValid();
}
@@ -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);