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/mir_graph.h b/compiler/dex/mir_graph.h
index 5d01489..8dda7c4 100644
--- a/compiler/dex/mir_graph.h
+++ b/compiler/dex/mir_graph.h
@@ -183,6 +183,9 @@
#define BLOCK_NAME_LEN 80
+typedef uint16_t BasicBlockId;
+static const BasicBlockId NullBasicBlockId = 0;
+
/*
* In general, vreg/sreg describe Dalvik registers that originated with dx. However,
* it is useful to have compiler-generated temporary registers and have them treated
@@ -190,15 +193,15 @@
* name of compiler-introduced temporaries.
*/
struct CompilerTemp {
- int s_reg;
+ int32_t s_reg;
};
// When debug option enabled, records effectiveness of null and range check elimination.
struct Checkstats {
- int null_checks;
- int null_checks_eliminated;
- int range_checks;
- int range_checks_eliminated;
+ int32_t null_checks;
+ int32_t null_checks_eliminated;
+ int32_t range_checks;
+ int32_t range_checks_eliminated;
};
// Dataflow attributes of a basic block.
@@ -207,7 +210,7 @@
ArenaBitVector* def_v;
ArenaBitVector* live_in_v;
ArenaBitVector* phi_v;
- int* vreg_to_ssa_map;
+ int32_t* vreg_to_ssa_map;
ArenaBitVector* ending_null_check_v;
};
@@ -220,11 +223,11 @@
* we may want to revisit in the future.
*/
struct SSARepresentation {
- int num_uses;
- int* uses;
+ int16_t num_uses;
+ int16_t num_defs;
+ int32_t* uses;
bool* fp_use;
- int num_defs;
- int* defs;
+ int32_t* defs;
bool* fp_def;
};
@@ -233,51 +236,53 @@
* wrapper around a Dalvik byte code.
*/
struct MIR {
+ /*
+ * TODO: remove embedded DecodedInstruction to save space, keeping only opcode. Recover
+ * additional fields on as-needed basis. Question: how to support MIR Pseudo-ops; probably
+ * need to carry aux data pointer.
+ */
DecodedInstruction dalvikInsn;
- uint32_t width; // NOTE: only need 16 bits for width.
- unsigned int offset;
- int m_unit_index; // From which method was this MIR included
- MIR* prev;
+ uint16_t width; // Note: width can include switch table or fill array data.
+ NarrowDexOffset offset; // Offset of the instruction in code units.
+ uint16_t optimization_flags;
+ int16_t m_unit_index; // From which method was this MIR included
MIR* next;
SSARepresentation* ssa_rep;
- int optimization_flags;
union {
+ // Incoming edges for phi node.
+ BasicBlockId* phi_incoming;
// Establish link between two halves of throwing instructions.
MIR* throw_insn;
- // Saved opcode for NOP'd MIRs
- Instruction::Code original_opcode;
} meta;
};
struct SuccessorBlockInfo;
struct BasicBlock {
- int id;
- int dfs_id;
- bool visited;
- bool hidden;
- bool catch_entry;
- bool explicit_throw;
- bool conditional_branch;
- bool terminated_by_return; // Block ends with a Dalvik return opcode.
- bool dominates_return; // Is a member of return extended basic block.
- uint16_t start_offset;
+ BasicBlockId id;
+ BasicBlockId dfs_id;
+ NarrowDexOffset start_offset; // Offset in code units.
+ BasicBlockId fall_through;
+ BasicBlockId taken;
+ BasicBlockId i_dom; // Immediate dominator.
uint16_t nesting_depth;
- BBType block_type;
+ BBType block_type:4;
+ BlockListType successor_block_list_type:4;
+ bool visited:1;
+ bool hidden:1;
+ bool catch_entry:1;
+ bool explicit_throw:1;
+ bool conditional_branch:1;
+ bool terminated_by_return:1; // Block ends with a Dalvik return opcode.
+ bool dominates_return:1; // Is a member of return extended basic block.
MIR* first_mir_insn;
MIR* last_mir_insn;
- BasicBlock* fall_through;
- BasicBlock* taken;
- BasicBlock* i_dom; // Immediate dominator.
BasicBlockDataFlow* data_flow_info;
- GrowableArray<BasicBlock*>* predecessors;
ArenaBitVector* dominators;
ArenaBitVector* i_dominated; // Set nodes being immediately dominated.
ArenaBitVector* dom_frontier; // Dominance frontier.
- struct { // For one-to-many successors like.
- BlockListType block_list_type; // switch and exception handling.
- GrowableArray<SuccessorBlockInfo*>* blocks;
- } successor_block_list;
+ GrowableArray<BasicBlockId>* predecessors;
+ GrowableArray<SuccessorBlockInfo*>* successor_blocks;
};
/*
@@ -285,9 +290,8 @@
* "SuccessorBlockInfo". For catch blocks, key is type index for the exception. For swtich
* blocks, key is the case value.
*/
-// TODO: make class with placement new.
struct SuccessorBlockInfo {
- BasicBlock* block;
+ BasicBlockId block;
int key;
};
@@ -296,6 +300,15 @@
* the type of an SSA name (and, can also be used by code generators to record where the
* value is located (i.e. - physical register, frame, spill, etc.). For each SSA name (SReg)
* there is a RegLocation.
+ * A note on SSA names:
+ * o SSA names for Dalvik vRegs v0..vN will be assigned 0..N. These represent the "vN_0"
+ * names. Negative SSA names represent special values not present in the Dalvik byte code.
+ * For example, SSA name -1 represents an invalid SSA name, and SSA name -2 represents the
+ * the Method pointer. SSA names < -2 are reserved for future use.
+ * o The vN_0 names for non-argument Dalvik should in practice never be used (as they would
+ * represent the read of an undefined local variable). The first definition of the
+ * underlying Dalvik vReg will result in a vN_1 name.
+ *
* FIXME: The orig_sreg field was added as a workaround for llvm bitcode generation. With
* the latest restructuring, we should be able to remove it and rely on s_reg_low throughout.
*/
@@ -311,9 +324,9 @@
unsigned home:1; // Does this represent the home location?
uint8_t low_reg; // First physical register.
uint8_t high_reg; // 2nd physical register (if wide).
- int32_t s_reg_low; // SSA name for low Dalvik word.
- int32_t orig_sreg; // TODO: remove after Bitcode gen complete
- // and consolodate usage w/ s_reg_low.
+ int16_t s_reg_low; // SSA name for low Dalvik word.
+ int16_t orig_sreg; // TODO: remove after Bitcode gen complete
+ // and consolidate usage w/ s_reg_low.
};
/*
@@ -334,7 +347,7 @@
RegLocation target; // Target of following move_result.
bool skip_this;
bool is_range;
- int offset; // Dalvik offset.
+ DexOffset offset; // Offset in code units.
};
@@ -361,7 +374,7 @@
uint32_t method_idx, jobject class_loader, const DexFile& dex_file);
/* Find existing block */
- BasicBlock* FindBlock(unsigned int code_offset) {
+ BasicBlock* FindBlock(DexOffset code_offset) {
return FindBlock(code_offset, false, false, NULL);
}
@@ -394,7 +407,7 @@
}
BasicBlock* GetBasicBlock(int block_id) const {
- return block_list_.Get(block_id);
+ return (block_id == NullBasicBlockId) ? NULL : block_list_.Get(block_id);
}
size_t GetBasicBlockListCount() const {
@@ -405,15 +418,15 @@
return &block_list_;
}
- GrowableArray<int>* GetDfsOrder() {
+ GrowableArray<BasicBlockId>* GetDfsOrder() {
return dfs_order_;
}
- GrowableArray<int>* GetDfsPostOrder() {
+ GrowableArray<BasicBlockId>* GetDfsPostOrder() {
return dfs_post_order_;
}
- GrowableArray<int>* GetDomPostOrder() {
+ GrowableArray<BasicBlockId>* GetDomPostOrder() {
return dom_post_order_traversal_;
}
@@ -477,6 +490,12 @@
}
void SetNumSSARegs(int new_num) {
+ /*
+ * TODO: It's theoretically possible to exceed 32767, though any cases which did
+ * would be filtered out with current settings. When orig_sreg field is removed
+ * from RegLocation, expand s_reg_low to handle all possible cases and remove DCHECK().
+ */
+ DCHECK_EQ(new_num, static_cast<int16_t>(new_num));
num_ssa_regs_ = new_num;
}
@@ -561,15 +580,16 @@
return special_case_;
}
- bool IsBackedge(BasicBlock* branch_bb, BasicBlock* target_bb) {
- return ((target_bb != NULL) && (target_bb->start_offset <= branch_bb->start_offset));
+ bool IsBackedge(BasicBlock* branch_bb, BasicBlockId target_bb_id) {
+ return ((target_bb_id != NullBasicBlockId) &&
+ (GetBasicBlock(target_bb_id)->start_offset <= branch_bb->start_offset));
}
bool IsBackwardsBranch(BasicBlock* branch_bb) {
return IsBackedge(branch_bb, branch_bb->taken) || IsBackedge(branch_bb, branch_bb->fall_through);
}
- void CountBranch(int target_offset) {
+ void CountBranch(DexOffset target_offset) {
if (target_offset <= current_offset_) {
backward_branches_++;
} else {
@@ -640,6 +660,9 @@
void DumpMIRGraph();
CallInfo* NewMemCallInfo(BasicBlock* bb, MIR* mir, InvokeType type, bool is_range);
BasicBlock* NewMemBB(BBType block_type, int block_id);
+ MIR* AdvanceMIR(BasicBlock** p_bb, MIR* mir);
+ BasicBlock* NextDominatedBlock(BasicBlock* bb);
+ bool LayoutBlocks(BasicBlock* bb);
/*
* IsDebugBuild sanity check: keep track of the Dex PCs for catch entries so that later on
@@ -668,15 +691,16 @@
bool InvokeUsesMethodStar(MIR* mir);
int ParseInsn(const uint16_t* code_ptr, DecodedInstruction* decoded_instruction);
bool ContentIsInsn(const uint16_t* code_ptr);
- BasicBlock* SplitBlock(unsigned int code_offset, BasicBlock* orig_block,
+ BasicBlock* SplitBlock(DexOffset code_offset, BasicBlock* orig_block,
BasicBlock** immed_pred_block_p);
- BasicBlock* FindBlock(unsigned int code_offset, bool split, bool create,
+ BasicBlock* FindBlock(DexOffset code_offset, bool split, bool create,
BasicBlock** immed_pred_block_p);
void ProcessTryCatchBlocks();
- BasicBlock* ProcessCanBranch(BasicBlock* cur_block, MIR* insn, int cur_offset, int width,
+ BasicBlock* ProcessCanBranch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, int width,
int flags, const uint16_t* code_ptr, const uint16_t* code_end);
- void ProcessCanSwitch(BasicBlock* cur_block, MIR* insn, int cur_offset, int width, int flags);
- BasicBlock* ProcessCanThrow(BasicBlock* cur_block, MIR* insn, int cur_offset, int width,
+ void ProcessCanSwitch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, int width,
+ int flags);
+ BasicBlock* ProcessCanThrow(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, int width,
int flags, ArenaBitVector* try_block_addr, const uint16_t* code_ptr,
const uint16_t* code_end);
int AddNewSReg(int v_reg);
@@ -732,9 +756,9 @@
GrowableArray<uint32_t> use_counts_; // Weighted by nesting depth
GrowableArray<uint32_t> raw_use_counts_; // Not weighted
unsigned int num_reachable_blocks_;
- GrowableArray<int>* dfs_order_;
- GrowableArray<int>* dfs_post_order_;
- GrowableArray<int>* dom_post_order_traversal_;
+ GrowableArray<BasicBlockId>* dfs_order_;
+ GrowableArray<BasicBlockId>* dfs_post_order_;
+ GrowableArray<BasicBlockId>* dom_post_order_traversal_;
int* i_dom_list_;
ArenaBitVector** def_block_matrix_; // num_dalvik_register x num_blocks.
ArenaBitVector* temp_block_v_;
@@ -752,11 +776,11 @@
typedef std::pair<int, int> MIRLocation; // Insert point, (m_unit_ index, offset)
std::vector<MIRLocation> method_stack_; // Include stack
int current_method_;
- int current_offset_; // Dex offset in code units
+ DexOffset current_offset_; // Offset in code units
int def_count_; // Used to estimate size of ssa name storage.
int* opcode_count_; // Dex opcode coverage stats.
int num_ssa_regs_; // Number of names following SSA transformation.
- std::vector<BasicBlock*> extended_basic_blocks_; // Heads of block "traces".
+ std::vector<BasicBlockId> extended_basic_blocks_; // Heads of block "traces".
int method_sreg_;
unsigned int attributes_;
Checkstats* checkstats_;