Rewrite BitVector index iterator.
The BitVector::Iterator was not iterating over the bits but
rather over indexes of the set bits. Therefore, we rename it
to IndexIterator and provide a BitVector::Indexes() to get
a container-style interface with begin() and end() for range
based for loops.
Also, simplify InsertPhiNodes where the tmp_blocks isn't
needed since the phi_nodes and input_blocks cannot lose any
blocks in subsequent iterations, so we can do the Union()
directly in those bit vectors and we need to repeat the loop
only if we have new input_blocks, rather than on phi_nodes
change. And move the temporary bit vectors to scoped arena.
Change-Id: I6cb87a2f60724eeef67c6aaa34b36ed5acde6d43
diff --git a/compiler/Android.mk b/compiler/Android.mk
index 274678a..021392c 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -61,7 +61,6 @@
dex/mir_optimization.cc \
dex/bb_optimizations.cc \
dex/pass_driver_me.cc \
- dex/bit_vector_block_iterator.cc \
dex/frontend.cc \
dex/mir_graph.cc \
dex/mir_analysis.cc \
diff --git a/compiler/dex/bb_optimizations.cc b/compiler/dex/bb_optimizations.cc
index 1852f80..8b5eba0 100644
--- a/compiler/dex/bb_optimizations.cc
+++ b/compiler/dex/bb_optimizations.cc
@@ -38,6 +38,13 @@
/*
* SSATransformation pass implementation start.
*/
+void SSATransformation::Start(const PassDataHolder* data) const {
+ DCHECK(data != nullptr);
+ CompilationUnit* cUnit = down_cast<const PassMEDataHolder*>(data)->c_unit;
+ DCHECK(cUnit != nullptr);
+ cUnit->mir_graph->SSATransformationStart();
+}
+
bool SSATransformation::Worker(const PassDataHolder* data) const {
DCHECK(data != nullptr);
const PassMEDataHolder* pass_me_data_holder = down_cast<const PassMEDataHolder*>(data);
@@ -54,10 +61,7 @@
DCHECK(data != nullptr);
CompilationUnit* cUnit = down_cast<const PassMEDataHolder*>(data)->c_unit;
DCHECK(cUnit != nullptr);
- // Verify the dataflow information after the pass.
- if (cUnit->enable_debug & (1 << kDebugVerifyDataflow)) {
- cUnit->mir_graph->VerifyDataflow();
- }
+ cUnit->mir_graph->SSATransformationEnd();
}
/*
diff --git a/compiler/dex/bb_optimizations.h b/compiler/dex/bb_optimizations.h
index 43dcdf4..3a529f2 100644
--- a/compiler/dex/bb_optimizations.h
+++ b/compiler/dex/bb_optimizations.h
@@ -143,12 +143,7 @@
bool Worker(const PassDataHolder* data) const;
- void Start(const PassDataHolder* data) const {
- DCHECK(data != nullptr);
- CompilationUnit* cUnit = down_cast<const PassMEDataHolder*>(data)->c_unit;
- DCHECK(cUnit != nullptr);
- cUnit->mir_graph->InitializeSSATransformation();
- }
+ void Start(const PassDataHolder* data) const;
void End(const PassDataHolder* data) const;
};
diff --git a/compiler/dex/bit_vector_block_iterator.cc b/compiler/dex/bit_vector_block_iterator.cc
deleted file mode 100644
index 32d7d71..0000000
--- a/compiler/dex/bit_vector_block_iterator.cc
+++ /dev/null
@@ -1,32 +0,0 @@
-/*
- * Copyright (C) 2014 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 "bit_vector_block_iterator.h"
-#include "mir_graph.h"
-
-namespace art {
-
-BasicBlock* BitVectorBlockIterator::Next() {
- int idx = internal_iterator_.Next();
-
- if (idx == -1) {
- return nullptr;
- }
-
- return mir_graph_->GetBasicBlock(idx);
-}
-
-} // namespace art
diff --git a/compiler/dex/bit_vector_block_iterator.h b/compiler/dex/bit_vector_block_iterator.h
deleted file mode 100644
index 0f1c2b6..0000000
--- a/compiler/dex/bit_vector_block_iterator.h
+++ /dev/null
@@ -1,58 +0,0 @@
-/*
- * Copyright (C) 2013 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_DEX_BIT_VECTOR_BLOCK_ITERATOR_H_
-#define ART_COMPILER_DEX_BIT_VECTOR_BLOCK_ITERATOR_H_
-
-#include "base/bit_vector.h"
-#include "compiler_enums.h"
-#include "utils/arena_bit_vector.h"
-#include "utils/arena_allocator.h"
-#include "compiler_ir.h"
-
-namespace art {
-
-class MIRGraph;
-
-/**
- * @class BasicBlockIterator
- * @brief Helper class to get the BasicBlocks when iterating through the ArenaBitVector.
- */
-class BitVectorBlockIterator {
- public:
- explicit BitVectorBlockIterator(BitVector* bv, MIRGraph* mir_graph)
- : mir_graph_(mir_graph),
- internal_iterator_(bv) {}
-
- explicit BitVectorBlockIterator(BitVector* bv, CompilationUnit* c_unit)
- : mir_graph_(c_unit->mir_graph.get()),
- internal_iterator_(bv) {}
-
- BasicBlock* Next();
-
- void* operator new(size_t size, ArenaAllocator* arena) {
- return arena->Alloc(size, kArenaAllocGrowableArray);
- };
- void operator delete(void* p) {} // Nop.
-
- private:
- MIRGraph* const mir_graph_;
- BitVector::Iterator internal_iterator_;
-};
-
-} // namespace art
-
-#endif // ART_COMPILER_DEX_BIT_VECTOR_BLOCK_ITERATOR_H_
diff --git a/compiler/dex/mir_graph.cc b/compiler/dex/mir_graph.cc
index c34a9f5..0ef66d2 100644
--- a/compiler/dex/mir_graph.cc
+++ b/compiler/dex/mir_graph.cc
@@ -80,7 +80,6 @@
topological_order_(nullptr),
i_dom_list_(NULL),
def_block_matrix_(NULL),
- temp_dalvik_register_v_(NULL),
temp_scoped_alloc_(),
temp_insn_data_(nullptr),
temp_bit_vector_size_(0u),
@@ -1318,7 +1317,13 @@
}
}
-void MIRGraph::InitializeSSATransformation() {
+void MIRGraph::SSATransformationStart() {
+ DCHECK(temp_scoped_alloc_.get() == nullptr);
+ temp_scoped_alloc_.reset(ScopedArenaAllocator::Create(&cu_->arena_stack));
+ temp_bit_vector_size_ = cu_->num_dalvik_registers;
+ temp_bit_vector_ = new (temp_scoped_alloc_.get()) ArenaBitVector(
+ temp_scoped_alloc_.get(), temp_bit_vector_size_, false, kBitMapRegisterV);
+
/* Compute the DFS order */
ComputeDFSOrders();
@@ -1339,6 +1344,18 @@
DoDFSPreOrderSSARename(GetEntryBlock());
}
+void MIRGraph::SSATransformationEnd() {
+ // Verify the dataflow information after the pass.
+ if (cu_->enable_debug & (1 << kDebugVerifyDataflow)) {
+ VerifyDataflow();
+ }
+
+ temp_bit_vector_size_ = 0u;
+ temp_bit_vector_ = nullptr;
+ DCHECK(temp_scoped_alloc_.get() != nullptr);
+ temp_scoped_alloc_.reset();
+}
+
void MIRGraph::ComputeTopologicalSortOrder() {
std::queue<BasicBlock *> q;
std::map<int, int> visited_cnt_values;
diff --git a/compiler/dex/mir_graph.h b/compiler/dex/mir_graph.h
index 3a00a43..c97dcd6 100644
--- a/compiler/dex/mir_graph.h
+++ b/compiler/dex/mir_graph.h
@@ -890,7 +890,7 @@
/**
* @brief Perform the initial preparation for the SSA Transformation.
*/
- void InitializeSSATransformation();
+ void SSATransformationStart();
/**
* @brief Insert a the operands for the Phi nodes.
@@ -900,6 +900,11 @@
bool InsertPhiNodeOperands(BasicBlock* bb);
/**
+ * @brief Perform the cleanup after the SSA Transformation.
+ */
+ void SSATransformationEnd();
+
+ /**
* @brief Perform constant propagation on a BasicBlock.
* @param bb the considered BasicBlock.
*/
@@ -1012,7 +1017,6 @@
GrowableArray<BasicBlockId>* topological_order_;
int* i_dom_list_;
ArenaBitVector** def_block_matrix_; // num_dalvik_register x num_blocks.
- ArenaBitVector* temp_dalvik_register_v_;
std::unique_ptr<ScopedArenaAllocator> temp_scoped_alloc_;
uint16_t* temp_insn_data_;
uint32_t temp_bit_vector_size_;
diff --git a/compiler/dex/ssa_transformation.cc b/compiler/dex/ssa_transformation.cc
index 865311b..6f47b8f 100644
--- a/compiler/dex/ssa_transformation.cc
+++ b/compiler/dex/ssa_transformation.cc
@@ -14,7 +14,6 @@
* limitations under the License.
*/
-#include "bit_vector_block_iterator.h"
#include "compiler_internals.h"
#include "dataflow_iterator-inl.h"
@@ -127,12 +126,7 @@
return false;
}
- ArenaBitVector::Iterator iterator(bb->data_flow_info->def_v);
- while (true) {
- int idx = iterator.Next();
- if (idx == -1) {
- break;
- }
+ for (uint32_t idx : bb->data_flow_info->def_v->Indexes()) {
/* Block bb defines register idx */
def_block_matrix_[idx]->SetBit(bb->id);
}
@@ -182,22 +176,22 @@
dom_post_order_traversal_->Reset();
}
ClearAllVisitedFlags();
- std::vector<std::pair<BasicBlock*, ArenaBitVector::Iterator*>> work_stack;
+ std::vector<std::pair<BasicBlock*, ArenaBitVector::IndexIterator>> work_stack;
bb->visited = true;
- work_stack.push_back(std::make_pair(bb, bb->i_dominated->GetIterator()));
+ work_stack.push_back(std::make_pair(bb, bb->i_dominated->Indexes().begin()));
while (!work_stack.empty()) {
- const std::pair<BasicBlock*, ArenaBitVector::Iterator*>& curr = work_stack.back();
- BasicBlock* curr_bb = curr.first;
- ArenaBitVector::Iterator* curr_idom_iter = curr.second;
- int bb_idx = curr_idom_iter->Next();
- while ((bb_idx != -1) && (NeedsVisit(GetBasicBlock(bb_idx)) == NULL)) {
- bb_idx = curr_idom_iter->Next();
+ std::pair<BasicBlock*, ArenaBitVector::IndexIterator>* curr = &work_stack.back();
+ BasicBlock* curr_bb = curr->first;
+ ArenaBitVector::IndexIterator* curr_idom_iter = &curr->second;
+ while (!curr_idom_iter->Done() && (NeedsVisit(GetBasicBlock(**curr_idom_iter)) == nullptr)) {
+ ++*curr_idom_iter;
}
- if (bb_idx != -1) {
- BasicBlock* new_bb = GetBasicBlock(bb_idx);
+ // NOTE: work_stack.push_back()/pop_back() invalidate curr and curr_idom_iter.
+ if (!curr_idom_iter->Done()) {
+ BasicBlock* new_bb = GetBasicBlock(**curr_idom_iter);
+ ++*curr_idom_iter;
new_bb->visited = true;
- work_stack.push_back(
- std::make_pair(new_bb, new_bb->i_dominated->GetIterator()));
+ work_stack.push_back(std::make_pair(new_bb, new_bb->i_dominated->Indexes().begin()));
} else {
// no successor/next
if (curr_bb->id != NullBasicBlockId) {
@@ -249,11 +243,10 @@
}
/* Calculate DF_up */
- BitVectorBlockIterator it(bb->i_dominated, cu_);
- for (BasicBlock *dominated_bb = it.Next(); dominated_bb != nullptr; dominated_bb = it.Next()) {
- BitVectorBlockIterator inner_it(dominated_bb->dom_frontier, cu_);
- for (BasicBlock *df_up_block = inner_it.Next(); df_up_block != nullptr;
- df_up_block = inner_it.Next()) {
+ for (uint32_t dominated_idx : bb->i_dominated->Indexes()) {
+ BasicBlock *dominated_bb = GetBasicBlock(dominated_idx);
+ for (uint32_t df_up_block_idx : dominated_bb->dom_frontier->Indexes()) {
+ BasicBlock *df_up_block = GetBasicBlock(df_up_block_idx);
CheckForDominanceFrontier(bb, df_up_block);
}
}
@@ -449,7 +442,8 @@
* insert a phi node if the variable is live-in to the block.
*/
bool MIRGraph::ComputeBlockLiveIns(BasicBlock* bb) {
- ArenaBitVector* temp_dalvik_register_v = temp_dalvik_register_v_;
+ DCHECK_EQ(temp_bit_vector_size_, cu_->num_dalvik_registers);
+ ArenaBitVector* temp_dalvik_register_v = temp_bit_vector_;
if (bb->data_flow_info == NULL) {
return false;
@@ -487,15 +481,10 @@
/* Insert phi nodes to for each variable to the dominance frontiers */
void MIRGraph::InsertPhiNodes() {
int dalvik_reg;
- ArenaBitVector* phi_blocks =
- new (arena_) ArenaBitVector(arena_, GetNumBlocks(), false, kBitMapPhi);
- ArenaBitVector* tmp_blocks =
- new (arena_) ArenaBitVector(arena_, GetNumBlocks(), false, kBitMapTmpBlocks);
- ArenaBitVector* input_blocks =
- new (arena_) ArenaBitVector(arena_, GetNumBlocks(), false, kBitMapInputBlocks);
-
- temp_dalvik_register_v_ =
- new (arena_) ArenaBitVector(arena_, cu_->num_dalvik_registers, false, kBitMapRegisterV);
+ ArenaBitVector* phi_blocks = new (temp_scoped_alloc_.get()) ArenaBitVector(
+ temp_scoped_alloc_.get(), GetNumBlocks(), false, kBitMapPhi);
+ ArenaBitVector* input_blocks = new (temp_scoped_alloc_.get()) ArenaBitVector(
+ temp_scoped_alloc_.get(), GetNumBlocks(), false, kBitMapInputBlocks);
RepeatingPostOrderDfsIterator iter(this);
bool change = false;
@@ -505,53 +494,23 @@
/* Iterate through each Dalvik register */
for (dalvik_reg = cu_->num_dalvik_registers - 1; dalvik_reg >= 0; dalvik_reg--) {
- bool change;
-
input_blocks->Copy(def_block_matrix_[dalvik_reg]);
phi_blocks->ClearAllBits();
-
- /* Calculate the phi blocks for each Dalvik register */
do {
- change = false;
- tmp_blocks->ClearAllBits();
- ArenaBitVector::Iterator iterator(input_blocks);
-
- while (true) {
- int idx = iterator.Next();
- if (idx == -1) {
- break;
- }
+ // TUNING: When we repeat this, we could skip indexes from the previous pass.
+ for (uint32_t idx : input_blocks->Indexes()) {
BasicBlock* def_bb = GetBasicBlock(idx);
-
- /* Merge the dominance frontier to tmp_blocks */
- // TUNING: hot call to Union().
- if (def_bb->dom_frontier != NULL) {
- tmp_blocks->Union(def_bb->dom_frontier);
+ if (def_bb->dom_frontier != nullptr) {
+ phi_blocks->Union(def_bb->dom_frontier);
}
}
- if (!phi_blocks->Equal(tmp_blocks)) {
- change = true;
- phi_blocks->Copy(tmp_blocks);
-
- /*
- * Iterate through the original blocks plus the new ones in
- * the dominance frontier.
- */
- input_blocks->Copy(phi_blocks);
- input_blocks->Union(def_block_matrix_[dalvik_reg]);
- }
- } while (change);
+ } while (input_blocks->Union(phi_blocks));
/*
* Insert a phi node for dalvik_reg in the phi_blocks if the Dalvik
* register is in the live-in set.
*/
- ArenaBitVector::Iterator iterator(phi_blocks);
- while (true) {
- int idx = iterator.Next();
- if (idx == -1) {
- break;
- }
+ for (uint32_t idx : phi_blocks->Indexes()) {
BasicBlock* phi_bb = GetBasicBlock(idx);
/* Variable will be clobbered before being used - no need for phi */
if (!phi_bb->data_flow_info->live_in_v->IsBitSet(dalvik_reg)) {
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 0f16ad2..938c5ec 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -174,28 +174,6 @@
ComputeLiveInAndLiveOutSets();
}
-class InstructionBitVectorIterator : public ValueObject {
- public:
- InstructionBitVectorIterator(const BitVector& vector,
- const GrowableArray<HInstruction*>& instructions)
- : instructions_(instructions),
- iterator_(BitVector::Iterator(&vector)),
- current_bit_index_(iterator_.Next()) {}
-
- bool Done() const { return current_bit_index_ == -1; }
- HInstruction* Current() const { return instructions_.Get(current_bit_index_); }
- void Advance() {
- current_bit_index_ = iterator_.Next();
- }
-
- private:
- const GrowableArray<HInstruction*> instructions_;
- BitVector::Iterator iterator_;
- int32_t current_bit_index_;
-
- DISALLOW_COPY_AND_ASSIGN(InstructionBitVectorIterator);
-};
-
void SsaLivenessAnalysis::ComputeLiveRanges() {
// Do a post order visit, adding inputs of instructions live in the block where
// that instruction is defined, and killing instructions that are being visited.
@@ -218,10 +196,9 @@
}
// Add a range that covers this block to all instructions live_in because of successors.
- for (InstructionBitVectorIterator it(*live_in, instructions_from_ssa_index_);
- !it.Done();
- it.Advance()) {
- it.Current()->GetLiveInterval()->AddRange(block->GetLifetimeStart(), block->GetLifetimeEnd());
+ for (uint32_t idx : live_in->Indexes()) {
+ HInstruction* current = instructions_from_ssa_index_.Get(idx);
+ current->GetLiveInterval()->AddRange(block->GetLifetimeStart(), block->GetLifetimeEnd());
}
for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
@@ -268,11 +245,10 @@
HBasicBlock* back_edge = block->GetLoopInformation()->GetBackEdges().Get(0);
// For all live_in instructions at the loop header, we need to create a range
// that covers the full loop.
- for (InstructionBitVectorIterator it(*live_in, instructions_from_ssa_index_);
- !it.Done();
- it.Advance()) {
- it.Current()->GetLiveInterval()->AddLoopRange(block->GetLifetimeStart(),
- back_edge->GetLifetimeEnd());
+ for (uint32_t idx : live_in->Indexes()) {
+ HInstruction* current = instructions_from_ssa_index_.Get(idx);
+ current->GetLiveInterval()->AddLoopRange(block->GetLifetimeStart(),
+ back_edge->GetLifetimeEnd());
}
}
}