64-bit prep
Preparation for 64-bit roll.
o Eliminated storing pointers in 32-bit int slots in LIR.
o General size reductions of common structures to reduce impact
of doubled pointer sizes:
- BasicBlock struct was 72 bytes, now is 48.
- MIR struct was 72 bytes, now is 64.
- RegLocation was 12 bytes, now is 8.
o Generally replaced uses of BasicBlock* pointers with 16-bit Ids.
o Replaced several doubly-linked lists with singly-linked to save
one stored pointer per node.
o We had quite a few uses of uintptr_t's that were a holdover from
the JIT (which used pointers to mapped dex & actual code cache
addresses rather than trace-relative offsets). Replaced those with
uint32_t's.
o Clean up handling of embedded data for switch tables and array data.
o Miscellaneous cleanup.
I anticipate one or two additional CLs to reduce the size of MIR and LIR
structs.
Change-Id: I58e426d3f8e5efe64c1146b2823453da99451230
diff --git a/compiler/dex/ssa_transformation.cc b/compiler/dex/ssa_transformation.cc
index 0ca5fd4..eb0d412 100644
--- a/compiler/dex/ssa_transformation.cc
+++ b/compiler/dex/ssa_transformation.cc
@@ -38,18 +38,18 @@
}
BasicBlock* MIRGraph::NextUnvisitedSuccessor(BasicBlock* bb) {
- BasicBlock* res = NeedsVisit(bb->fall_through);
+ BasicBlock* res = NeedsVisit(GetBasicBlock(bb->fall_through));
if (res == NULL) {
- res = NeedsVisit(bb->taken);
+ res = NeedsVisit(GetBasicBlock(bb->taken));
if (res == NULL) {
- if (bb->successor_block_list.block_list_type != kNotUsed) {
- GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_block_list.blocks);
+ if (bb->successor_block_list_type != kNotUsed) {
+ GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_blocks);
while (true) {
SuccessorBlockInfo *sbi = iterator.Next();
if (sbi == NULL) {
break;
}
- res = NeedsVisit(sbi->block);
+ res = NeedsVisit(GetBasicBlock(sbi->block));
if (res != NULL) {
break;
}
@@ -63,7 +63,9 @@
void MIRGraph::MarkPreOrder(BasicBlock* block) {
block->visited = true;
/* Enqueue the pre_order block id */
- dfs_order_->Insert(block->id);
+ if (block->id != NullBasicBlockId) {
+ dfs_order_->Insert(block->id);
+ }
}
void MIRGraph::RecordDFSOrders(BasicBlock* block) {
@@ -79,7 +81,9 @@
continue;
}
curr->dfs_id = dfs_post_order_->Size();
- dfs_post_order_->Insert(curr->id);
+ if (curr->id != NullBasicBlockId) {
+ dfs_post_order_->Insert(curr->id);
+ }
succ.pop_back();
}
}
@@ -88,7 +92,8 @@
void MIRGraph::ComputeDFSOrders() {
/* Initialize or reset the DFS pre_order list */
if (dfs_order_ == NULL) {
- dfs_order_ = new (arena_) GrowableArray<int>(arena_, GetNumBlocks(), kGrowableArrayDfsOrder);
+ dfs_order_ = new (arena_) GrowableArray<BasicBlockId>(arena_, GetNumBlocks(),
+ kGrowableArrayDfsOrder);
} else {
/* Just reset the used length on the counter */
dfs_order_->Reset();
@@ -96,7 +101,8 @@
/* Initialize or reset the DFS post_order list */
if (dfs_post_order_ == NULL) {
- dfs_post_order_ = new (arena_) GrowableArray<int>(arena_, GetNumBlocks(), kGrowableArrayDfsPostOrder);
+ dfs_post_order_ = new (arena_) GrowableArray<BasicBlockId>(arena_, GetNumBlocks(),
+ kGrowableArrayDfsPostOrder);
} else {
/* Just reset the used length on the counter */
dfs_post_order_->Reset();
@@ -169,7 +175,7 @@
if (dom_post_order_traversal_ == NULL) {
// First time - create the array.
dom_post_order_traversal_ =
- new (arena_) GrowableArray<int>(arena_, num_reachable_blocks_,
+ new (arena_) GrowableArray<BasicBlockId>(arena_, num_reachable_blocks_,
kGrowableArrayDomPostOrderTraversal);
} else {
dom_post_order_traversal_->Reset();
@@ -193,11 +199,13 @@
std::make_pair(new_bb, new (arena_) ArenaBitVector::Iterator(new_bb->i_dominated)));
} else {
// no successor/next
- dom_post_order_traversal_->Insert(curr_bb->id);
+ if (curr_bb->id != NullBasicBlockId) {
+ dom_post_order_traversal_->Insert(curr_bb->id);
+ }
work_stack.pop_back();
/* hacky loop detection */
- if (curr_bb->taken && curr_bb->dominators->IsBitSet(curr_bb->taken->id)) {
+ if ((curr_bb->taken != NullBasicBlockId) && curr_bb->dominators->IsBitSet(curr_bb->taken)) {
attributes_ |= METHOD_HAS_LOOP;
}
}
@@ -210,7 +218,7 @@
* TODO - evaluate whether phi will ever need to be inserted into exit
* blocks.
*/
- if (succ_bb->i_dom != dom_bb &&
+ if (succ_bb->i_dom != dom_bb->id &&
succ_bb->block_type == kDalvikByteCode &&
succ_bb->hidden == false) {
dom_bb->dom_frontier->SetBit(succ_bb->id);
@@ -220,20 +228,20 @@
/* Worker function to compute the dominance frontier */
bool MIRGraph::ComputeDominanceFrontier(BasicBlock* bb) {
/* Calculate DF_local */
- if (bb->taken) {
- CheckForDominanceFrontier(bb, bb->taken);
+ if (bb->taken != NullBasicBlockId) {
+ CheckForDominanceFrontier(bb, GetBasicBlock(bb->taken));
}
- if (bb->fall_through) {
- CheckForDominanceFrontier(bb, bb->fall_through);
+ if (bb->fall_through != NullBasicBlockId) {
+ CheckForDominanceFrontier(bb, GetBasicBlock(bb->fall_through));
}
- if (bb->successor_block_list.block_list_type != kNotUsed) {
- GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_block_list.blocks);
+ if (bb->successor_block_list_type != kNotUsed) {
+ GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_blocks);
while (true) {
SuccessorBlockInfo *successor_block_info = iterator.Next();
if (successor_block_info == NULL) {
break;
}
- BasicBlock* succ_bb = successor_block_info->block;
+ BasicBlock* succ_bb = GetBasicBlock(successor_block_info->block);
CheckForDominanceFrontier(bb, succ_bb);
}
}
@@ -306,17 +314,17 @@
/* Worker function to compute each block's immediate dominator */
bool MIRGraph::ComputeblockIDom(BasicBlock* bb) {
/* Special-case entry block */
- if (bb == GetEntryBlock()) {
+ if ((bb->id == NullBasicBlockId) || (bb == GetEntryBlock())) {
return false;
}
/* Iterate through the predecessors */
- GrowableArray<BasicBlock*>::Iterator iter(bb->predecessors);
+ GrowableArray<BasicBlockId>::Iterator iter(bb->predecessors);
/* Find the first processed predecessor */
int idom = -1;
while (true) {
- BasicBlock* pred_bb = iter.Next();
+ BasicBlock* pred_bb = GetBasicBlock(iter.Next());
CHECK(pred_bb != NULL);
if (i_dom_list_[pred_bb->dfs_id] != NOTVISITED) {
idom = pred_bb->dfs_id;
@@ -326,7 +334,7 @@
/* Scan the rest of the predecessors */
while (true) {
- BasicBlock* pred_bb = iter.Next();
+ BasicBlock* pred_bb = GetBasicBlock(iter.Next());
if (!pred_bb) {
break;
}
@@ -352,7 +360,7 @@
if (bb == GetEntryBlock()) {
bb->dominators->ClearAllBits();
} else {
- bb->dominators->Copy(bb->i_dom->dominators);
+ bb->dominators->Copy(GetBasicBlock(bb->i_dom)->dominators);
}
bb->dominators->SetBit(bb->id);
return false;
@@ -364,7 +372,7 @@
DCHECK_NE(idom_dfs_idx, NOTVISITED);
int i_dom_idx = dfs_post_order_->Get(idom_dfs_idx);
BasicBlock* i_dom = GetBasicBlock(i_dom_idx);
- bb->i_dom = i_dom;
+ bb->i_dom = i_dom->id;
/* Add bb to the i_dominated set of the immediate dominator block */
i_dom->i_dominated->SetBit(bb->id);
}
@@ -412,7 +420,7 @@
} else {
temp_block_v_->ClearAllBits();
}
- GetEntryBlock()->i_dom = NULL;
+ GetEntryBlock()->i_dom = 0;
PreOrderDfsIterator iter3(this);
for (BasicBlock* bb = iter3.Next(); bb != NULL; bb = iter3.Next()) {
@@ -463,20 +471,22 @@
return false;
}
temp_dalvik_register_v->Copy(bb->data_flow_info->live_in_v);
- if (bb->taken && bb->taken->data_flow_info)
- ComputeSuccLineIn(temp_dalvik_register_v, bb->taken->data_flow_info->live_in_v,
+ BasicBlock* bb_taken = GetBasicBlock(bb->taken);
+ BasicBlock* bb_fall_through = GetBasicBlock(bb->fall_through);
+ if (bb_taken && bb_taken->data_flow_info)
+ ComputeSuccLineIn(temp_dalvik_register_v, bb_taken->data_flow_info->live_in_v,
bb->data_flow_info->def_v);
- if (bb->fall_through && bb->fall_through->data_flow_info)
- ComputeSuccLineIn(temp_dalvik_register_v, bb->fall_through->data_flow_info->live_in_v,
+ if (bb_fall_through && bb_fall_through->data_flow_info)
+ ComputeSuccLineIn(temp_dalvik_register_v, bb_fall_through->data_flow_info->live_in_v,
bb->data_flow_info->def_v);
- if (bb->successor_block_list.block_list_type != kNotUsed) {
- GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_block_list.blocks);
+ if (bb->successor_block_list_type != kNotUsed) {
+ GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_blocks);
while (true) {
SuccessorBlockInfo *successor_block_info = iterator.Next();
if (successor_block_info == NULL) {
break;
}
- BasicBlock* succ_bb = successor_block_info->block;
+ BasicBlock* succ_bb = GetBasicBlock(successor_block_info->block);
if (succ_bb->data_flow_info) {
ComputeSuccLineIn(temp_dalvik_register_v, succ_bb->data_flow_info->live_in_v,
bb->data_flow_info->def_v);
@@ -579,50 +589,37 @@
* predecessor blocks
*/
bool MIRGraph::InsertPhiNodeOperands(BasicBlock* bb) {
- MIR *mir;
- std::vector<int> uses;
- std::vector<int> incoming_arc;
-
/* Phi nodes are at the beginning of each block */
- for (mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
+ for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
if (mir->dalvikInsn.opcode != static_cast<Instruction::Code>(kMirOpPhi))
return true;
int ssa_reg = mir->ssa_rep->defs[0];
DCHECK_GE(ssa_reg, 0); // Shouldn't see compiler temps here
int v_reg = SRegToVReg(ssa_reg);
- uses.clear();
- incoming_arc.clear();
-
/* Iterate through the predecessors */
- GrowableArray<BasicBlock*>::Iterator iter(bb->predecessors);
+ GrowableArray<BasicBlockId>::Iterator iter(bb->predecessors);
+ size_t num_uses = bb->predecessors->Size();
+ mir->ssa_rep->num_uses = num_uses;
+ int* uses = static_cast<int*>(arena_->Alloc(sizeof(int) * num_uses,
+ ArenaAllocator::kAllocDFInfo));
+ mir->ssa_rep->uses = uses;
+ mir->ssa_rep->fp_use =
+ static_cast<bool*>(arena_->Alloc(sizeof(bool) * num_uses, ArenaAllocator::kAllocDFInfo));
+ BasicBlockId* incoming =
+ static_cast<BasicBlockId*>(arena_->Alloc(sizeof(BasicBlockId) * num_uses,
+ ArenaAllocator::kAllocDFInfo));
+ mir->meta.phi_incoming = incoming;
+ int idx = 0;
while (true) {
- BasicBlock* pred_bb = iter.Next();
+ BasicBlock* pred_bb = GetBasicBlock(iter.Next());
if (!pred_bb) {
break;
}
int ssa_reg = pred_bb->data_flow_info->vreg_to_ssa_map[v_reg];
- uses.push_back(ssa_reg);
- incoming_arc.push_back(pred_bb->id);
- }
-
- /* Count the number of SSA registers for a Dalvik register */
- int num_uses = uses.size();
- mir->ssa_rep->num_uses = num_uses;
- mir->ssa_rep->uses =
- static_cast<int*>(arena_->Alloc(sizeof(int) * num_uses, ArenaAllocator::kAllocDFInfo));
- mir->ssa_rep->fp_use =
- static_cast<bool*>(arena_->Alloc(sizeof(bool) * num_uses, ArenaAllocator::kAllocDFInfo));
- int* incoming =
- static_cast<int*>(arena_->Alloc(sizeof(int) * num_uses, ArenaAllocator::kAllocDFInfo));
- // TODO: Ugly, rework (but don't burden each MIR/LIR for Phi-only needs)
- mir->dalvikInsn.vB = reinterpret_cast<uintptr_t>(incoming);
-
- /* Set the uses array for the phi node */
- int *use_ptr = mir->ssa_rep->uses;
- for (int i = 0; i < num_uses; i++) {
- *use_ptr++ = uses[i];
- *incoming++ = incoming_arc[i];
+ uses[idx] = ssa_reg;
+ incoming[idx] = pred_bb->id;
+ idx++;
}
}
@@ -644,24 +641,24 @@
static_cast<int*>(arena_->Alloc(map_size, ArenaAllocator::kAllocDalvikToSSAMap));
memcpy(saved_ssa_map, vreg_to_ssa_map_, map_size);
- if (block->fall_through) {
- DoDFSPreOrderSSARename(block->fall_through);
+ if (block->fall_through != NullBasicBlockId) {
+ DoDFSPreOrderSSARename(GetBasicBlock(block->fall_through));
/* Restore SSA map snapshot */
memcpy(vreg_to_ssa_map_, saved_ssa_map, map_size);
}
- if (block->taken) {
- DoDFSPreOrderSSARename(block->taken);
+ if (block->taken != NullBasicBlockId) {
+ DoDFSPreOrderSSARename(GetBasicBlock(block->taken));
/* Restore SSA map snapshot */
memcpy(vreg_to_ssa_map_, saved_ssa_map, map_size);
}
- if (block->successor_block_list.block_list_type != kNotUsed) {
- GrowableArray<SuccessorBlockInfo*>::Iterator iterator(block->successor_block_list.blocks);
+ if (block->successor_block_list_type != kNotUsed) {
+ GrowableArray<SuccessorBlockInfo*>::Iterator iterator(block->successor_blocks);
while (true) {
SuccessorBlockInfo *successor_block_info = iterator.Next();
if (successor_block_info == NULL) {
break;
}
- BasicBlock* succ_bb = successor_block_info->block;
+ BasicBlock* succ_bb = GetBasicBlock(successor_block_info->block);
DoDFSPreOrderSSARename(succ_bb);
/* Restore SSA map snapshot */
memcpy(vreg_to_ssa_map_, saved_ssa_map, map_size);