Deprecate GrowableArray, use ArenaVector instead.
Purge GrowableArray from Quick and Portable.
Remove GrowableArray<T>::Iterator.
Change-Id: I92157d3a6ea5975f295662809585b2dc15caa1c6
diff --git a/compiler/dex/mir_graph.cc b/compiler/dex/mir_graph.cc
index ce56255..7c0a996 100644
--- a/compiler/dex/mir_graph.cc
+++ b/compiler/dex/mir_graph.cc
@@ -76,23 +76,23 @@
: reg_location_(NULL),
block_id_map_(std::less<unsigned int>(), arena->Adapter()),
cu_(cu),
- ssa_base_vregs_(NULL),
- ssa_subscripts_(NULL),
+ ssa_base_vregs_(arena->Adapter(kArenaAllocSSAToDalvikMap)),
+ ssa_subscripts_(arena->Adapter(kArenaAllocSSAToDalvikMap)),
vreg_to_ssa_map_(NULL),
ssa_last_defs_(NULL),
is_constant_v_(NULL),
constant_values_(NULL),
- use_counts_(arena, 256, kGrowableArrayMisc),
- raw_use_counts_(arena, 256, kGrowableArrayMisc),
+ use_counts_(arena->Adapter()),
+ raw_use_counts_(arena->Adapter()),
num_reachable_blocks_(0),
max_num_reachable_blocks_(0),
- dfs_order_(NULL),
- dfs_post_order_(NULL),
- dom_post_order_traversal_(NULL),
- topological_order_(nullptr),
- topological_order_loop_ends_(nullptr),
- topological_order_indexes_(nullptr),
- topological_order_loop_head_stack_(nullptr),
+ dfs_order_(arena->Adapter(kArenaAllocDfsPreOrder)),
+ dfs_post_order_(arena->Adapter(kArenaAllocDfsPostOrder)),
+ dom_post_order_traversal_(arena->Adapter(kArenaAllocDomPostOrder)),
+ topological_order_(arena->Adapter(kArenaAllocTopologicalSortOrder)),
+ topological_order_loop_ends_(arena->Adapter(kArenaAllocTopologicalSortOrder)),
+ topological_order_indexes_(arena->Adapter(kArenaAllocTopologicalSortOrder)),
+ topological_order_loop_head_stack_(arena->Adapter(kArenaAllocTopologicalSortOrder)),
i_dom_list_(NULL),
def_block_matrix_(NULL),
temp_scoped_alloc_(),
@@ -100,13 +100,13 @@
temp_bit_vector_size_(0u),
temp_bit_vector_(nullptr),
temp_gvn_(),
- block_list_(arena, 100, kGrowableArrayBlockList),
+ block_list_(arena->Adapter(kArenaAllocBBList)),
try_block_addr_(NULL),
entry_block_(NULL),
exit_block_(NULL),
num_blocks_(0),
current_code_item_(NULL),
- dex_pc_to_block_map_(arena, 0, kGrowableArrayMisc),
+ dex_pc_to_block_map_(arena->Adapter()),
m_units_(arena->Adapter()),
method_stack_(arena->Adapter()),
current_method_(kInvalidEntry),
@@ -127,10 +127,13 @@
compiler_temps_committed_(false),
punt_to_interpreter_(false),
merged_df_flags_(0u),
- ifield_lowering_infos_(arena, 0u),
- sfield_lowering_infos_(arena, 0u),
- method_lowering_infos_(arena, 0u),
- gen_suspend_test_list_(arena, 0u) {
+ ifield_lowering_infos_(arena->Adapter(kArenaAllocLoweringInfo)),
+ sfield_lowering_infos_(arena->Adapter(kArenaAllocLoweringInfo)),
+ method_lowering_infos_(arena->Adapter(kArenaAllocLoweringInfo)),
+ gen_suspend_test_list_(arena->Adapter()) {
+ use_counts_.reserve(256);
+ raw_use_counts_.reserve(256);
+ block_list_.reserve(100);
try_block_addr_ = new (arena_) ArenaBitVector(arena_, 0, true /* expandable */);
@@ -149,6 +152,7 @@
}
MIRGraph::~MIRGraph() {
+ STLDeleteElements(&block_list_);
STLDeleteElements(&m_units_);
}
@@ -183,8 +187,7 @@
if (insn == NULL) {
LOG(FATAL) << "Break split failed";
}
- BasicBlock* bottom_block = NewMemBB(kDalvikByteCode, num_blocks_++);
- block_list_.Insert(bottom_block);
+ BasicBlock* bottom_block = CreateNewBB(kDalvikByteCode);
bottom_block->start_offset = code_offset;
bottom_block->first_mir_insn = insn;
@@ -207,34 +210,31 @@
if (bottom_block->taken != NullBasicBlockId) {
orig_block->taken = NullBasicBlockId;
BasicBlock* bb_taken = GetBasicBlock(bottom_block->taken);
- bb_taken->predecessors->Delete(orig_block->id);
- bb_taken->predecessors->Insert(bottom_block->id);
+ bb_taken->ErasePredecessor(orig_block->id);
+ bb_taken->predecessors.push_back(bottom_block->id);
}
/* Handle the fallthrough path */
bottom_block->fall_through = orig_block->fall_through;
orig_block->fall_through = bottom_block->id;
- bottom_block->predecessors->Insert(orig_block->id);
+ bottom_block->predecessors.push_back(orig_block->id);
if (bottom_block->fall_through != NullBasicBlockId) {
BasicBlock* bb_fall_through = GetBasicBlock(bottom_block->fall_through);
- bb_fall_through->predecessors->Delete(orig_block->id);
- bb_fall_through->predecessors->Insert(bottom_block->id);
+ bb_fall_through->ErasePredecessor(orig_block->id);
+ bb_fall_through->predecessors.push_back(bottom_block->id);
}
/* Handle the successor list */
if (orig_block->successor_block_list_type != kNotUsed) {
bottom_block->successor_block_list_type = orig_block->successor_block_list_type;
- bottom_block->successor_blocks = orig_block->successor_blocks;
+ bottom_block->successor_blocks.swap(orig_block->successor_blocks);
orig_block->successor_block_list_type = kNotUsed;
- orig_block->successor_blocks = nullptr;
- GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bottom_block->successor_blocks);
- while (true) {
- SuccessorBlockInfo* successor_block_info = iterator.Next();
- if (successor_block_info == nullptr) break;
+ DCHECK(orig_block->successor_blocks.empty()); // Empty after the swap() above.
+ for (SuccessorBlockInfo* successor_block_info : bottom_block->successor_blocks) {
BasicBlock* bb = GetBasicBlock(successor_block_info->block);
if (bb != nullptr) {
- bb->predecessors->Delete(orig_block->id);
- bb->predecessors->Insert(bottom_block->id);
+ bb->ErasePredecessor(orig_block->id);
+ bb->predecessors.push_back(bottom_block->id);
}
}
}
@@ -258,9 +258,9 @@
DCHECK_EQ(insn->offset, bottom_block->start_offset);
DCHECK(static_cast<int>(insn->dalvikInsn.opcode) == kMirOpCheck ||
!MIR::DecodedInstruction::IsPseudoMirOp(insn->dalvikInsn.opcode));
- DCHECK_EQ(dex_pc_to_block_map_.Get(insn->offset), orig_block->id);
+ DCHECK_EQ(dex_pc_to_block_map_[insn->offset], orig_block->id);
MIR* p = insn;
- dex_pc_to_block_map_.Put(p->offset, bottom_block->id);
+ dex_pc_to_block_map_[p->offset] = bottom_block->id;
while (p != bottom_block->last_mir_insn) {
p = p->next;
DCHECK(p != nullptr);
@@ -273,8 +273,8 @@
* the first in a BasicBlock, we can't hit it here.
*/
if ((opcode == kMirOpCheck) || !MIR::DecodedInstruction::IsPseudoMirOp(opcode)) {
- DCHECK_EQ(dex_pc_to_block_map_.Get(p->offset), orig_block->id);
- dex_pc_to_block_map_.Put(p->offset, bottom_block->id);
+ DCHECK_EQ(dex_pc_to_block_map_[p->offset], orig_block->id);
+ dex_pc_to_block_map_[p->offset] = bottom_block->id;
}
}
@@ -295,8 +295,8 @@
return NULL;
}
- int block_id = dex_pc_to_block_map_.Get(code_offset);
- BasicBlock* bb = (block_id == 0) ? NULL : block_list_.Get(block_id);
+ int block_id = dex_pc_to_block_map_[code_offset];
+ BasicBlock* bb = GetBasicBlock(block_id);
if ((bb != NULL) && (bb->start_offset == code_offset)) {
// Does this containing block start with the desired instruction?
@@ -314,10 +314,9 @@
}
// Create a new block.
- bb = NewMemBB(kDalvikByteCode, num_blocks_++);
- block_list_.Insert(bb);
+ bb = CreateNewBB(kDalvikByteCode);
bb->start_offset = code_offset;
- dex_pc_to_block_map_.Put(bb->start_offset, bb->id);
+ dex_pc_to_block_map_[bb->start_offset] = bb->id;
return bb;
}
@@ -457,7 +456,7 @@
BasicBlock* taken_block = FindBlock(target, /* split */ true, /* create */ true,
/* immed_pred_block_p */ &cur_block);
cur_block->taken = taken_block->id;
- taken_block->predecessors->Insert(cur_block->id);
+ taken_block->predecessors.push_back(cur_block->id);
/* Always terminate the current block for conditional branches */
if (flags & Instruction::kContinue) {
@@ -480,7 +479,7 @@
/* immed_pred_block_p */
&cur_block);
cur_block->fall_through = fallthrough_block->id;
- fallthrough_block->predecessors->Insert(cur_block->id);
+ fallthrough_block->predecessors.push_back(cur_block->id);
} else if (code_ptr < code_end) {
FindBlock(cur_offset + width, /* split */ false, /* create */ true,
/* immed_pred_block_p */ NULL);
@@ -539,8 +538,7 @@
}
cur_block->successor_block_list_type =
(insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? kPackedSwitch : kSparseSwitch;
- cur_block->successor_blocks =
- new (arena_) GrowableArray<SuccessorBlockInfo*>(arena_, size, kGrowableArraySuccessorBlocks);
+ cur_block->successor_blocks.reserve(size);
for (i = 0; i < size; i++) {
BasicBlock* case_block = FindBlock(cur_offset + target_table[i], /* split */ true,
@@ -552,15 +550,15 @@
successor_block_info->key =
(insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ?
first_key + i : keyTable[i];
- cur_block->successor_blocks->Insert(successor_block_info);
- case_block->predecessors->Insert(cur_block->id);
+ cur_block->successor_blocks.push_back(successor_block_info);
+ case_block->predecessors.push_back(cur_block->id);
}
/* Fall-through case */
BasicBlock* fallthrough_block = FindBlock(cur_offset + width, /* split */ false,
/* create */ true, /* immed_pred_block_p */ NULL);
cur_block->fall_through = fallthrough_block->id;
- fallthrough_block->predecessors->Insert(cur_block->id);
+ fallthrough_block->predecessors.push_back(cur_block->id);
return cur_block;
}
@@ -593,8 +591,6 @@
}
if (cur_block->successor_block_list_type == kNotUsed) {
cur_block->successor_block_list_type = kCatch;
- cur_block->successor_blocks = new (arena_) GrowableArray<SuccessorBlockInfo*>(
- arena_, 2, kGrowableArraySuccessorBlocks);
}
catch_block->catch_entry = true;
if (kIsDebugBuild) {
@@ -604,17 +600,16 @@
(arena_->Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor));
successor_block_info->block = catch_block->id;
successor_block_info->key = iterator.GetHandlerTypeIndex();
- cur_block->successor_blocks->Insert(successor_block_info);
- catch_block->predecessors->Insert(cur_block->id);
+ cur_block->successor_blocks.push_back(successor_block_info);
+ catch_block->predecessors.push_back(cur_block->id);
}
in_try_block = (cur_block->successor_block_list_type != kNotUsed);
}
if (!in_try_block && build_all_edges) {
- BasicBlock* eh_block = NewMemBB(kExceptionHandling, num_blocks_++);
+ BasicBlock* eh_block = CreateNewBB(kExceptionHandling);
cur_block->taken = eh_block->id;
- block_list_.Insert(eh_block);
eh_block->start_offset = cur_offset;
- eh_block->predecessors->Insert(cur_block->id);
+ eh_block->predecessors.push_back(cur_block->id);
}
if (is_throw) {
@@ -657,11 +652,10 @@
* Note also that the dex_pc_to_block_map_ entry for the potentially
* throwing instruction will refer to the original basic block.
*/
- BasicBlock* new_block = NewMemBB(kDalvikByteCode, num_blocks_++);
- block_list_.Insert(new_block);
+ BasicBlock* new_block = CreateNewBB(kDalvikByteCode);
new_block->start_offset = insn->offset;
cur_block->fall_through = new_block->id;
- new_block->predecessors->Insert(cur_block->id);
+ new_block->predecessors.push_back(cur_block->id);
MIR* new_insn = NewMIR();
*new_insn = *insn;
insn->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpCheck);
@@ -689,8 +683,8 @@
// TODO: need to rework expansion of block list & try_block_addr when inlining activated.
// TUNING: use better estimate of basic blocks for following resize.
- block_list_.Resize(block_list_.Size() + current_code_item_->insns_size_in_code_units_);
- dex_pc_to_block_map_.SetSize(dex_pc_to_block_map_.Size() + current_code_item_->insns_size_in_code_units_);
+ block_list_.reserve(block_list_.size() + current_code_item_->insns_size_in_code_units_);
+ dex_pc_to_block_map_.resize(dex_pc_to_block_map_.size() + current_code_item_->insns_size_in_code_units_);
// TODO: replace with explicit resize routine. Using automatic extension side effect for now.
try_block_addr_->SetBit(current_code_item_->insns_size_in_code_units_);
@@ -702,14 +696,11 @@
DCHECK(exit_block_ == NULL);
DCHECK_EQ(num_blocks_, 0U);
// Use id 0 to represent a null block.
- BasicBlock* null_block = NewMemBB(kNullBlock, num_blocks_++);
+ BasicBlock* null_block = CreateNewBB(kNullBlock);
DCHECK_EQ(null_block->id, NullBasicBlockId);
null_block->hidden = true;
- block_list_.Insert(null_block);
- entry_block_ = NewMemBB(kEntryBlock, num_blocks_++);
- block_list_.Insert(entry_block_);
- exit_block_ = NewMemBB(kExitBlock, num_blocks_++);
- block_list_.Insert(exit_block_);
+ entry_block_ = CreateNewBB(kEntryBlock);
+ exit_block_ = CreateNewBB(kExitBlock);
// TODO: deprecate all "cu->" fields; move what's left to wherever CompilationUnit is allocated.
cu_->dex_file = &dex_file;
cu_->class_def_idx = class_def_idx;
@@ -727,13 +718,12 @@
}
/* Current block to record parsed instructions */
- BasicBlock* cur_block = NewMemBB(kDalvikByteCode, num_blocks_++);
+ BasicBlock* cur_block = CreateNewBB(kDalvikByteCode);
DCHECK_EQ(current_offset_, 0U);
cur_block->start_offset = current_offset_;
- block_list_.Insert(cur_block);
// TODO: for inlining support, insert at the insert point rather than entry block.
entry_block_->fall_through = cur_block->id;
- cur_block->predecessors->Insert(entry_block_->id);
+ cur_block->predecessors.push_back(entry_block_->id);
/* Identify code range in try blocks and set up the empty catch blocks */
ProcessTryCatchBlocks();
@@ -791,7 +781,7 @@
}
// Associate the starting dex_pc for this opcode with its containing basic block.
- dex_pc_to_block_map_.Put(insn->offset, cur_block->id);
+ dex_pc_to_block_map_[insn->offset] = cur_block->id;
code_ptr += width;
@@ -801,7 +791,7 @@
} else if (flags & Instruction::kReturn) {
cur_block->terminated_by_return = true;
cur_block->fall_through = exit_block_->id;
- exit_block_->predecessors->Insert(cur_block->id);
+ exit_block_->predecessors.push_back(cur_block->id);
/*
* Terminate the current block if there are instructions
* afterwards.
@@ -850,7 +840,7 @@
if ((cur_block->fall_through == NullBasicBlockId) && (flags & Instruction::kContinue)) {
cur_block->fall_through = next_block->id;
- next_block->predecessors->Insert(cur_block->id);
+ next_block->predecessors.push_back(cur_block->id);
}
cur_block = next_block;
}
@@ -915,7 +905,7 @@
int idx;
for (idx = 0; idx < num_blocks; idx++) {
- int block_idx = all_blocks ? idx : dfs_order_->Get(idx);
+ int block_idx = all_blocks ? idx : dfs_order_[idx];
BasicBlock* bb = GetBasicBlock(block_idx);
if (bb == NULL) continue;
if (bb->block_type == kDead) continue;
@@ -971,23 +961,17 @@
fprintf(file, " succ%04x_%d [shape=%s,label = \"{ \\\n",
bb->start_offset, bb->id,
(bb->successor_block_list_type == kCatch) ? "Mrecord" : "record");
- GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_blocks);
- SuccessorBlockInfo* successor_block_info = iterator.Next();
+ int last_succ_id = static_cast<int>(bb->successor_blocks.size() - 1u);
int succ_id = 0;
- while (true) {
- if (successor_block_info == NULL) break;
-
+ for (SuccessorBlockInfo* successor_block_info : bb->successor_blocks) {
BasicBlock* dest_block = GetBasicBlock(successor_block_info->block);
- SuccessorBlockInfo *next_successor_block_info = iterator.Next();
-
fprintf(file, " {<f%d> %04x: %04x\\l}%s\\\n",
- succ_id++,
+ succ_id,
successor_block_info->key,
dest_block->start_offset,
- (next_successor_block_info != NULL) ? " | " : " ");
-
- successor_block_info = next_successor_block_info;
+ (succ_id != last_succ_id) ? " | " : " ");
+ ++succ_id;
}
fprintf(file, " }\"];\n\n");
@@ -996,13 +980,8 @@
block_name1, bb->start_offset, bb->id);
// Link the successor pseudo-block with all of its potential targets.
- GrowableArray<SuccessorBlockInfo*>::Iterator iter(bb->successor_blocks);
-
succ_id = 0;
- while (true) {
- SuccessorBlockInfo* successor_block_info = iter.Next();
- if (successor_block_info == NULL) break;
-
+ for (SuccessorBlockInfo* successor_block_info : bb->successor_blocks) {
BasicBlock* dest_block = GetBasicBlock(successor_block_info->block);
GetBlockName(dest_block, block_name2);
@@ -1603,7 +1582,6 @@
/* Debug Utility - dump a compilation unit */
void MIRGraph::DumpMIRGraph() {
- BasicBlock* bb;
const char* block_type_names[] = {
"Null Block",
"Entry Block",
@@ -1616,11 +1594,8 @@
LOG(INFO) << "Compiling " << PrettyMethod(cu_->method_idx, *cu_->dex_file);
LOG(INFO) << GetInsns(0) << " insns";
LOG(INFO) << GetNumBlocks() << " blocks in total";
- GrowableArray<BasicBlock*>::Iterator iterator(&block_list_);
- while (true) {
- bb = iterator.Next();
- if (bb == NULL) break;
+ for (BasicBlock* bb : block_list_) {
LOG(INFO) << StringPrintf("Block %d (%s) (insn %04x - %04x%s)",
bb->id,
block_type_names[bb->block_type],
@@ -1678,15 +1653,10 @@
// Allocate a new basic block.
BasicBlock* MIRGraph::NewMemBB(BBType block_type, int block_id) {
- BasicBlock* bb = new (arena_) BasicBlock();
+ BasicBlock* bb = new (arena_) BasicBlock(block_id, block_type, arena_);
- bb->block_type = block_type;
- bb->id = block_id;
// TUNING: better estimate of the exit block predecessors?
- bb->predecessors = new (arena_) GrowableArray<BasicBlockId>(arena_,
- (block_type == kExitBlock) ? 2048 : 2,
- kGrowableArrayPredecessors);
- bb->successor_block_list_type = kNotUsed;
+ bb->predecessors.reserve((block_type == kExitBlock) ? 2048 : 2);
block_id_map_.Put(block_id, block_id);
return bb;
}
@@ -1699,16 +1669,12 @@
void MIRGraph::InitializeMethodUses() {
// The gate starts by initializing the use counts.
int num_ssa_regs = GetNumSSARegs();
- use_counts_.Resize(num_ssa_regs + 32);
- raw_use_counts_.Resize(num_ssa_regs + 32);
- // Resize does not actually reset the number of used, so reset before initialization.
- use_counts_.Reset();
- raw_use_counts_.Reset();
- // Initialize list.
- for (int i = 0; i < num_ssa_regs; i++) {
- use_counts_.Insert(0);
- raw_use_counts_.Insert(0);
- }
+ use_counts_.clear();
+ use_counts_.reserve(num_ssa_regs + 32);
+ use_counts_.resize(num_ssa_regs, 0u);
+ raw_use_counts_.clear();
+ raw_use_counts_.reserve(num_ssa_regs + 32);
+ raw_use_counts_.resize(num_ssa_regs, 0u);
}
void MIRGraph::SSATransformationStart() {
@@ -1800,9 +1766,9 @@
tmp_stack->pop_back();
BasicBlock* current_bb = mir_graph->GetBasicBlock(current_id);
DCHECK(current_bb != nullptr);
- GrowableArray<BasicBlockId>::Iterator iter(current_bb->predecessors);
- BasicBlock* pred_bb = mir_graph->GetBasicBlock(iter.Next());
- for ( ; pred_bb != nullptr; pred_bb = mir_graph->GetBasicBlock(iter.Next())) {
+ for (BasicBlockId pred_id : current_bb->predecessors) {
+ BasicBlock* pred_bb = mir_graph->GetBasicBlock(pred_id);
+ DCHECK(pred_bb != nullptr);
if (!pred_bb->visited && !reachable->IsBitSet(pred_bb->id)) {
reachable->SetBit(pred_bb->id);
tmp_stack->push_back(pred_bb->id);
@@ -1823,36 +1789,27 @@
loop_exit_blocks.ClearAllBits();
// Count the number of blocks to process and add the entry block(s).
- GrowableArray<BasicBlock*>::Iterator iterator(&block_list_);
unsigned int num_blocks_to_process = 0u;
- for (BasicBlock* bb = iterator.Next(); bb != nullptr; bb = iterator.Next()) {
+ for (BasicBlock* bb : block_list_) {
if (bb->hidden == true) {
continue;
}
num_blocks_to_process += 1u;
- if (bb->predecessors->Size() == 0u) {
+ if (bb->predecessors.size() == 0u) {
// Add entry block to the queue.
q.push(bb);
}
}
- // Create the topological order if need be.
- if (topological_order_ == nullptr) {
- topological_order_ = new (arena_) GrowableArray<BasicBlockId>(arena_, num_blocks);
- topological_order_loop_ends_ = new (arena_) GrowableArray<uint16_t>(arena_, num_blocks);
- topological_order_indexes_ = new (arena_) GrowableArray<uint16_t>(arena_, num_blocks);
- }
- topological_order_->Reset();
- topological_order_loop_ends_->Reset();
- topological_order_indexes_->Reset();
- topological_order_loop_ends_->Resize(num_blocks);
- topological_order_indexes_->Resize(num_blocks);
- for (BasicBlockId i = 0; i != num_blocks; ++i) {
- topological_order_loop_ends_->Insert(0u);
- topological_order_indexes_->Insert(static_cast<uint16_t>(-1));
- }
+ // Clear the topological order arrays.
+ topological_order_.clear();
+ topological_order_.reserve(num_blocks);
+ topological_order_loop_ends_.clear();
+ topological_order_loop_ends_.resize(num_blocks, 0u);
+ topological_order_indexes_.clear();
+ topological_order_indexes_.resize(num_blocks, static_cast<uint16_t>(-1));
// Mark all blocks as unvisited.
ClearAllVisitedFlags();
@@ -1875,8 +1832,8 @@
if (bb->visited) {
// Loop head: it was already processed, mark end and copy exit blocks to the queue.
DCHECK(q.empty()) << PrettyMethod(cu_->method_idx, *cu_->dex_file);
- uint16_t idx = static_cast<uint16_t>(topological_order_->Size());
- topological_order_loop_ends_->Put(topological_order_indexes_->Get(bb->id), idx);
+ uint16_t idx = static_cast<uint16_t>(topological_order_.size());
+ topological_order_loop_ends_[topological_order_indexes_[bb->id]] = idx;
DCHECK_EQ(loop_head_stack.back(), bb->id);
loop_head_stack.pop_back();
ArenaBitVector* reachable =
@@ -1919,15 +1876,16 @@
continue;
}
- GrowableArray<BasicBlockId>::Iterator pred_iter(candidate->predecessors);
- BasicBlock* pred_bb = GetBasicBlock(pred_iter.Next());
- for ( ; pred_bb != nullptr; pred_bb = GetBasicBlock(pred_iter.Next())) {
+ for (BasicBlockId pred_id : candidate->predecessors) {
+ BasicBlock* pred_bb = GetBasicBlock(pred_id);
+ DCHECK(pred_bb != nullptr);
if (pred_bb != candidate && !pred_bb->visited &&
!pred_bb->dominators->IsBitSet(candidate->id)) {
- break; // Keep non-null pred_bb to indicate failure.
+ candidate = nullptr; // Set candidate to null to indicate failure.
+ break;
}
}
- if (pred_bb == nullptr) {
+ if (candidate != nullptr) {
bb = candidate;
break;
}
@@ -1947,9 +1905,9 @@
bb->visited = true;
// Now add the basic block.
- uint16_t idx = static_cast<uint16_t>(topological_order_->Size());
- topological_order_indexes_->Put(bb->id, idx);
- topological_order_->Insert(bb->id);
+ uint16_t idx = static_cast<uint16_t>(topological_order_.size());
+ topological_order_indexes_[bb->id] = idx;
+ topological_order_.push_back(bb->id);
// Update visited_cnt_values for children.
ChildBlockIterator succIter(bb, this);
@@ -1961,7 +1919,7 @@
// One more predecessor was visited.
visited_cnt_values[successor->id] += 1u;
- if (visited_cnt_values[successor->id] == successor->predecessors->Size()) {
+ if (visited_cnt_values[successor->id] == successor->predecessors.size()) {
if (loop_head_stack.empty() ||
loop_head_reachable_from[loop_head_stack.back()]->IsBitSet(successor->id)) {
q.push(successor);
@@ -1974,8 +1932,8 @@
}
// Prepare the loop head stack for iteration.
- topological_order_loop_head_stack_ =
- new (arena_) GrowableArray<std::pair<uint16_t, bool>>(arena_, max_nested_loops);
+ topological_order_loop_head_stack_.clear();
+ topological_order_loop_head_stack_.reserve(max_nested_loops);
}
bool BasicBlock::IsExceptionBlock() const {
@@ -1992,8 +1950,8 @@
return false;
int idx;
- for (idx = gen_suspend_test_list_.Size() - 1; idx >= 0; idx--) {
- BasicBlock* bb = gen_suspend_test_list_.Get(idx);
+ for (idx = gen_suspend_test_list_.size() - 1; idx >= 0; idx--) {
+ BasicBlock* bb = gen_suspend_test_list_[idx];
if (bb == source)
return true; // The block has been inserted by a suspend check before.
if (source->dominators->IsBitSet(bb->id) && bb->dominators->IsBitSet(target_id))
@@ -2009,7 +1967,7 @@
// Check if we actually do have successors.
if (basic_block_ != 0 && basic_block_->successor_block_list_type != kNotUsed) {
have_successors_ = true;
- successor_iter_.Reset(basic_block_->successor_blocks);
+ successor_iter_ = basic_block_->successor_blocks.cbegin();
}
}
@@ -2042,9 +2000,10 @@
// We visited both taken and fallthrough. Now check if we have successors we need to visit.
if (have_successors_ == true) {
// Get information about next successor block.
- for (SuccessorBlockInfo* successor_block_info = successor_iter_.Next();
- successor_block_info != nullptr;
- successor_block_info = successor_iter_.Next()) {
+ auto end = basic_block_->successor_blocks.cend();
+ while (successor_iter_ != end) {
+ SuccessorBlockInfo* successor_block_info = *successor_iter_;
+ ++successor_iter_;
// If block was replaced by zero block, take next one.
if (successor_block_info->block != NullBasicBlockId) {
return mir_graph_->GetBasicBlock(successor_block_info->block);
@@ -2075,17 +2034,12 @@
result_bb->successor_block_list_type = successor_block_list_type;
if (result_bb->successor_block_list_type != kNotUsed) {
- size_t size = successor_blocks->Size();
- result_bb->successor_blocks = new (arena) GrowableArray<SuccessorBlockInfo*>(arena, size, kGrowableArraySuccessorBlocks);
- GrowableArray<SuccessorBlockInfo*>::Iterator iterator(successor_blocks);
- while (true) {
- SuccessorBlockInfo* sbi_old = iterator.Next();
- if (sbi_old == nullptr) {
- break;
- }
- SuccessorBlockInfo* sbi_new = static_cast<SuccessorBlockInfo*>(arena->Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor));
+ result_bb->successor_blocks.reserve(successor_blocks.size());
+ for (SuccessorBlockInfo* sbi_old : successor_blocks) {
+ SuccessorBlockInfo* sbi_new = static_cast<SuccessorBlockInfo*>(
+ arena->Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor));
memcpy(sbi_new, sbi_old, sizeof(SuccessorBlockInfo));
- result_bb->successor_blocks->Insert(sbi_new);
+ result_bb->successor_blocks.push_back(sbi_new);
}
}
@@ -2244,14 +2198,10 @@
first_mir_insn = nullptr;
last_mir_insn = nullptr;
- GrowableArray<BasicBlockId>::Iterator iterator(predecessors);
-
MIRGraph* mir_graph = c_unit->mir_graph.get();
- while (true) {
- BasicBlock* pred_bb = mir_graph->GetBasicBlock(iterator.Next());
- if (pred_bb == nullptr) {
- break;
- }
+ for (BasicBlockId pred_id : predecessors) {
+ BasicBlock* pred_bb = mir_graph->GetBasicBlock(pred_id);
+ DCHECK(pred_bb != nullptr);
// Sadly we have to go through the children by hand here.
pred_bb->ReplaceChild(id, NullBasicBlockId);
@@ -2261,8 +2211,8 @@
ChildBlockIterator successorChildIter(this, mir_graph);
for (BasicBlock* childPtr = successorChildIter.Next(); childPtr != 0; childPtr = successorChildIter.Next()) {
- // Replace child with null child.
- childPtr->predecessors->Delete(id);
+ // Erase this predecessor from child.
+ childPtr->ErasePredecessor(id);
}
// Remove link to children.
@@ -2328,12 +2278,7 @@
}
if (successor_block_list_type != kNotUsed) {
- GrowableArray<SuccessorBlockInfo*>::Iterator iterator(successor_blocks);
- while (true) {
- SuccessorBlockInfo* successor_block_info = iterator.Next();
- if (successor_block_info == nullptr) {
- break;
- }
+ for (SuccessorBlockInfo* successor_block_info : successor_blocks) {
if (successor_block_info->block == old_bb) {
successor_block_info->block = new_bb;
found = true;
@@ -2344,28 +2289,20 @@
return found;
}
-void BasicBlock::UpdatePredecessor(BasicBlockId old_parent, BasicBlockId new_parent) {
- GrowableArray<BasicBlockId>::Iterator iterator(predecessors);
- bool found = false;
+void BasicBlock::ErasePredecessor(BasicBlockId old_pred) {
+ auto pos = std::find(predecessors.begin(), predecessors.end(), old_pred);
+ DCHECK(pos != predecessors.end());
+ predecessors.erase(pos);
+}
- while (true) {
- BasicBlockId pred_bb_id = iterator.Next();
-
- if (pred_bb_id == NullBasicBlockId) {
- break;
- }
-
- if (pred_bb_id == old_parent) {
- size_t idx = iterator.GetIndex() - 1;
- predecessors->Put(idx, new_parent);
- found = true;
- break;
- }
- }
-
- // If not found, add it.
- if (found == false) {
- predecessors->Insert(new_parent);
+void BasicBlock::UpdatePredecessor(BasicBlockId old_pred, BasicBlockId new_pred) {
+ DCHECK_NE(new_pred, NullBasicBlockId);
+ auto pos = std::find(predecessors.begin(), predecessors.end(), old_pred);
+ if (pos != predecessors.end()) {
+ *pos = new_pred;
+ } else {
+ // If not found, add it.
+ predecessors.push_back(new_pred);
}
}
@@ -2373,7 +2310,7 @@
// post-incremented.
BasicBlock* MIRGraph::CreateNewBB(BBType block_type) {
BasicBlock* res = NewMemBB(block_type, num_blocks_++);
- block_list_.Insert(res);
+ block_list_.push_back(res);
return res;
}
@@ -2383,7 +2320,7 @@
}
void MIRGraph::InitializeBasicBlockData() {
- num_blocks_ = block_list_.Size();
+ num_blocks_ = block_list_.size();
}
int MIR::DecodedInstruction::FlagsOf() const {