Compiler: Spring cleaning
Significant restructuring of the Quick compiler to break out the
common frontend more cleanly. Additional C++'ification.
The goal is to move from the monolithic structure of the old
JIT towards a more modular model in which components - in
particular the compiler backend - can be replaced. This CL
focuses on moving MIR-related data from the CompilationUnit
struct into a new MIRGraph class. The next CL will isolate all
LIR-related data and code down into the Quick backend.
This change will happen in multiple steps, and may look uglier
before it starts looking better.
Among the changes:
o Moved all mir-related fields from CompilationUnit to new
MirGraph class.
o Moved the register promotion stuff into the Quick backend.
o Deleted the GBC to LIR conversion code.
o Replaced with old C-style function pointer dataflow analysis
dispatcher with a basic block iterator class.
o Renamed some files to make the name more consistent with what
the code actually does.
o Added the foundation for future inlining support.
o Stripped out the remains of the old fingerprinting mechanism.
Change-Id: I6c30facc642f8084b1c7b2075cf7014de387aa56
diff --git a/src/compiler/dex/vreg_analysis.cc b/src/compiler/dex/vreg_analysis.cc
new file mode 100644
index 0000000..4f516fe
--- /dev/null
+++ b/src/compiler/dex/vreg_analysis.cc
@@ -0,0 +1,496 @@
+/*
+ * Copyright (C) 2011 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 "compiler_internals.h"
+#include "dataflow_iterator.h"
+#include "quick/ralloc_util.h"
+
+namespace art {
+
+static bool SetFp(CompilationUnit* cu, int index, bool is_fp) {
+ bool change = false;
+ if (is_fp && !cu->reg_location[index].fp) {
+ cu->reg_location[index].fp = true;
+ cu->reg_location[index].defined = true;
+ change = true;
+ }
+ return change;
+}
+
+static bool SetCore(CompilationUnit* cu, int index, bool is_core) {
+ bool change = false;
+ if (is_core && !cu->reg_location[index].defined) {
+ cu->reg_location[index].core = true;
+ cu->reg_location[index].defined = true;
+ change = true;
+ }
+ return change;
+}
+
+static bool SetRef(CompilationUnit* cu, int index, bool is_ref) {
+ bool change = false;
+ if (is_ref && !cu->reg_location[index].defined) {
+ cu->reg_location[index].ref = true;
+ cu->reg_location[index].defined = true;
+ change = true;
+ }
+ return change;
+}
+
+static bool SetWide(CompilationUnit* cu, int index, bool is_wide) {
+ bool change = false;
+ if (is_wide && !cu->reg_location[index].wide) {
+ cu->reg_location[index].wide = true;
+ change = true;
+ }
+ return change;
+}
+
+static bool SetHigh(CompilationUnit* cu, int index, bool is_high) {
+ bool change = false;
+ if (is_high && !cu->reg_location[index].high_word) {
+ cu->reg_location[index].high_word = true;
+ change = true;
+ }
+ return change;
+}
+
+/*
+ * Infer types and sizes. We don't need to track change on sizes,
+ * as it doesn't propagate. We're guaranteed at least one pass through
+ * the cfg.
+ */
+bool MIRGraph::InferTypeAndSize(BasicBlock* bb)
+{
+ MIR *mir;
+ bool changed = false; // Did anything change?
+
+ if (bb->data_flow_info == NULL) return false;
+ if (bb->block_type != kDalvikByteCode && bb->block_type != kEntryBlock)
+ return false;
+
+ for (mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
+ SSARepresentation *ssa_rep = mir->ssa_rep;
+ if (ssa_rep) {
+ int attrs = oat_data_flow_attributes[mir->dalvikInsn.opcode];
+
+ // Handle defs
+ if (attrs & DF_DA) {
+ if (attrs & DF_CORE_A) {
+ changed |= SetCore(cu_, ssa_rep->defs[0], true);
+ }
+ if (attrs & DF_REF_A) {
+ changed |= SetRef(cu_, ssa_rep->defs[0], true);
+ }
+ if (attrs & DF_A_WIDE) {
+ cu_->reg_location[ssa_rep->defs[0]].wide = true;
+ cu_->reg_location[ssa_rep->defs[1]].wide = true;
+ cu_->reg_location[ssa_rep->defs[1]].high_word = true;
+ DCHECK_EQ(SRegToVReg(ssa_rep->defs[0])+1,
+ SRegToVReg(ssa_rep->defs[1]));
+ }
+ }
+
+ // Handles uses
+ int next = 0;
+ if (attrs & DF_UA) {
+ if (attrs & DF_CORE_A) {
+ changed |= SetCore(cu_, ssa_rep->uses[next], true);
+ }
+ if (attrs & DF_REF_A) {
+ changed |= SetRef(cu_, ssa_rep->uses[next], true);
+ }
+ if (attrs & DF_A_WIDE) {
+ cu_->reg_location[ssa_rep->uses[next]].wide = true;
+ cu_->reg_location[ssa_rep->uses[next + 1]].wide = true;
+ cu_->reg_location[ssa_rep->uses[next + 1]].high_word = true;
+ DCHECK_EQ(SRegToVReg(ssa_rep->uses[next])+1,
+ SRegToVReg(ssa_rep->uses[next + 1]));
+ next += 2;
+ } else {
+ next++;
+ }
+ }
+ if (attrs & DF_UB) {
+ if (attrs & DF_CORE_B) {
+ changed |= SetCore(cu_, ssa_rep->uses[next], true);
+ }
+ if (attrs & DF_REF_B) {
+ changed |= SetRef(cu_, ssa_rep->uses[next], true);
+ }
+ if (attrs & DF_B_WIDE) {
+ cu_->reg_location[ssa_rep->uses[next]].wide = true;
+ cu_->reg_location[ssa_rep->uses[next + 1]].wide = true;
+ cu_->reg_location[ssa_rep->uses[next + 1]].high_word = true;
+ DCHECK_EQ(SRegToVReg(ssa_rep->uses[next])+1,
+ SRegToVReg(ssa_rep->uses[next + 1]));
+ next += 2;
+ } else {
+ next++;
+ }
+ }
+ if (attrs & DF_UC) {
+ if (attrs & DF_CORE_C) {
+ changed |= SetCore(cu_, ssa_rep->uses[next], true);
+ }
+ if (attrs & DF_REF_C) {
+ changed |= SetRef(cu_, ssa_rep->uses[next], true);
+ }
+ if (attrs & DF_C_WIDE) {
+ cu_->reg_location[ssa_rep->uses[next]].wide = true;
+ cu_->reg_location[ssa_rep->uses[next + 1]].wide = true;
+ cu_->reg_location[ssa_rep->uses[next + 1]].high_word = true;
+ DCHECK_EQ(SRegToVReg(ssa_rep->uses[next])+1,
+ SRegToVReg(ssa_rep->uses[next + 1]));
+ }
+ }
+
+ // Special-case return handling
+ if ((mir->dalvikInsn.opcode == Instruction::RETURN) ||
+ (mir->dalvikInsn.opcode == Instruction::RETURN_WIDE) ||
+ (mir->dalvikInsn.opcode == Instruction::RETURN_OBJECT)) {
+ switch(cu_->shorty[0]) {
+ case 'I':
+ changed |= SetCore(cu_, ssa_rep->uses[0], true);
+ break;
+ case 'J':
+ changed |= SetCore(cu_, ssa_rep->uses[0], true);
+ changed |= SetCore(cu_, ssa_rep->uses[1], true);
+ cu_->reg_location[ssa_rep->uses[0]].wide = true;
+ cu_->reg_location[ssa_rep->uses[1]].wide = true;
+ cu_->reg_location[ssa_rep->uses[1]].high_word = true;
+ break;
+ case 'F':
+ changed |= SetFp(cu_, ssa_rep->uses[0], true);
+ break;
+ case 'D':
+ changed |= SetFp(cu_, ssa_rep->uses[0], true);
+ changed |= SetFp(cu_, ssa_rep->uses[1], true);
+ cu_->reg_location[ssa_rep->uses[0]].wide = true;
+ cu_->reg_location[ssa_rep->uses[1]].wide = true;
+ cu_->reg_location[ssa_rep->uses[1]].high_word = true;
+ break;
+ case 'L':
+ changed |= SetRef(cu_, ssa_rep->uses[0], true);
+ break;
+ default: break;
+ }
+ }
+
+ // Special-case handling for format 35c/3rc invokes
+ Instruction::Code opcode = mir->dalvikInsn.opcode;
+ int flags = (static_cast<int>(opcode) >= kNumPackedOpcodes)
+ ? 0 : Instruction::FlagsOf(mir->dalvikInsn.opcode);
+ if ((flags & Instruction::kInvoke) &&
+ (attrs & (DF_FORMAT_35C | DF_FORMAT_3RC))) {
+ DCHECK_EQ(next, 0);
+ int target_idx = mir->dalvikInsn.vB;
+ const char* shorty = GetShortyFromTargetIdx(cu_, target_idx);
+ // Handle result type if floating point
+ if ((shorty[0] == 'F') || (shorty[0] == 'D')) {
+ MIR* move_result_mir = FindMoveResult(bb, mir);
+ // Result might not be used at all, so no move-result
+ if (move_result_mir && (move_result_mir->dalvikInsn.opcode !=
+ Instruction::MOVE_RESULT_OBJECT)) {
+ SSARepresentation* tgt_rep = move_result_mir->ssa_rep;
+ DCHECK(tgt_rep != NULL);
+ tgt_rep->fp_def[0] = true;
+ changed |= SetFp(cu_, tgt_rep->defs[0], true);
+ if (shorty[0] == 'D') {
+ tgt_rep->fp_def[1] = true;
+ changed |= SetFp(cu_, tgt_rep->defs[1], true);
+ }
+ }
+ }
+ int num_uses = mir->dalvikInsn.vA;
+ // If this is a non-static invoke, mark implicit "this"
+ if (((mir->dalvikInsn.opcode != Instruction::INVOKE_STATIC) &&
+ (mir->dalvikInsn.opcode != Instruction::INVOKE_STATIC_RANGE))) {
+ cu_->reg_location[ssa_rep->uses[next]].defined = true;
+ cu_->reg_location[ssa_rep->uses[next]].ref = true;
+ next++;
+ }
+ uint32_t cpos = 1;
+ if (strlen(shorty) > 1) {
+ for (int i = next; i < num_uses;) {
+ DCHECK_LT(cpos, strlen(shorty));
+ switch (shorty[cpos++]) {
+ case 'D':
+ ssa_rep->fp_use[i] = true;
+ ssa_rep->fp_use[i+1] = true;
+ cu_->reg_location[ssa_rep->uses[i]].wide = true;
+ cu_->reg_location[ssa_rep->uses[i+1]].wide = true;
+ cu_->reg_location[ssa_rep->uses[i+1]].high_word = true;
+ DCHECK_EQ(SRegToVReg(ssa_rep->uses[i])+1, SRegToVReg(ssa_rep->uses[i+1]));
+ i++;
+ break;
+ case 'J':
+ cu_->reg_location[ssa_rep->uses[i]].wide = true;
+ cu_->reg_location[ssa_rep->uses[i+1]].wide = true;
+ cu_->reg_location[ssa_rep->uses[i+1]].high_word = true;
+ DCHECK_EQ(SRegToVReg(ssa_rep->uses[i])+1, SRegToVReg(ssa_rep->uses[i+1]));
+ changed |= SetCore(cu_, ssa_rep->uses[i],true);
+ i++;
+ break;
+ case 'F':
+ ssa_rep->fp_use[i] = true;
+ break;
+ case 'L':
+ changed |= SetRef(cu_,ssa_rep->uses[i], true);
+ break;
+ default:
+ changed |= SetCore(cu_,ssa_rep->uses[i], true);
+ break;
+ }
+ i++;
+ }
+ }
+ }
+
+ for (int i=0; ssa_rep->fp_use && i< ssa_rep->num_uses; i++) {
+ if (ssa_rep->fp_use[i])
+ changed |= SetFp(cu_, ssa_rep->uses[i], true);
+ }
+ for (int i=0; ssa_rep->fp_def && i< ssa_rep->num_defs; i++) {
+ if (ssa_rep->fp_def[i])
+ changed |= SetFp(cu_, ssa_rep->defs[i], true);
+ }
+ // Special-case handling for moves & Phi
+ if (attrs & (DF_IS_MOVE | DF_NULL_TRANSFER_N)) {
+ /*
+ * If any of our inputs or outputs is defined, set all.
+ * Some ugliness related to Phi nodes and wide values.
+ * The Phi set will include all low words or all high
+ * words, so we have to treat them specially.
+ */
+ bool is_phi = (static_cast<int>(mir->dalvikInsn.opcode) ==
+ kMirOpPhi);
+ RegLocation rl_temp = cu_->reg_location[ssa_rep->defs[0]];
+ bool defined_fp = rl_temp.defined && rl_temp.fp;
+ bool defined_core = rl_temp.defined && rl_temp.core;
+ bool defined_ref = rl_temp.defined && rl_temp.ref;
+ bool is_wide = rl_temp.wide || ((attrs & DF_A_WIDE) != 0);
+ bool is_high = is_phi && rl_temp.wide && rl_temp.high_word;
+ for (int i = 0; i < ssa_rep->num_uses;i++) {
+ rl_temp = cu_->reg_location[ssa_rep->uses[i]];
+ defined_fp |= rl_temp.defined && rl_temp.fp;
+ defined_core |= rl_temp.defined && rl_temp.core;
+ defined_ref |= rl_temp.defined && rl_temp.ref;
+ is_wide |= rl_temp.wide;
+ is_high |= is_phi && rl_temp.wide && rl_temp.high_word;
+ }
+ /*
+ * TODO: cleaner fix
+ * We don't normally expect to see a Dalvik register
+ * definition used both as a floating point and core
+ * value. However, the instruction rewriting that occurs
+ * during verification can eliminate some type information,
+ * leaving us confused. The real fix here is either to
+ * add explicit type information to Dalvik byte codes,
+ * or to recognize THROW_VERIFICATION_ERROR as
+ * an unconditional branch and support dead code elimination.
+ * As a workaround we can detect this situation and
+ * disable register promotion (which is the only thing that
+ * relies on distinctions between core and fp usages.
+ */
+ if ((defined_fp && (defined_core | defined_ref)) &&
+ ((cu_->disable_opt & (1 << kPromoteRegs)) == 0)) {
+ LOG(WARNING) << PrettyMethod(cu_->method_idx, *cu_->dex_file)
+ << " op at block " << bb->id
+ << " has both fp and core/ref uses for same def.";
+ cu_->disable_opt |= (1 << kPromoteRegs);
+ }
+ changed |= SetFp(cu_, ssa_rep->defs[0], defined_fp);
+ changed |= SetCore(cu_, ssa_rep->defs[0], defined_core);
+ changed |= SetRef(cu_, ssa_rep->defs[0], defined_ref);
+ changed |= SetWide(cu_, ssa_rep->defs[0], is_wide);
+ changed |= SetHigh(cu_, ssa_rep->defs[0], is_high);
+ if (attrs & DF_A_WIDE) {
+ changed |= SetWide(cu_, ssa_rep->defs[1], true);
+ changed |= SetHigh(cu_, ssa_rep->defs[1], true);
+ }
+ for (int i = 0; i < ssa_rep->num_uses; i++) {
+ changed |= SetFp(cu_, ssa_rep->uses[i], defined_fp);
+ changed |= SetCore(cu_, ssa_rep->uses[i], defined_core);
+ changed |= SetRef(cu_, ssa_rep->uses[i], defined_ref);
+ changed |= SetWide(cu_, ssa_rep->uses[i], is_wide);
+ changed |= SetHigh(cu_, ssa_rep->uses[i], is_high);
+ }
+ if (attrs & DF_A_WIDE) {
+ DCHECK_EQ(ssa_rep->num_uses, 2);
+ changed |= SetWide(cu_, ssa_rep->uses[1], true);
+ changed |= SetHigh(cu_, ssa_rep->uses[1], true);
+ }
+ }
+ }
+ }
+ return changed;
+}
+
+static const char* storage_name[] = {" Frame ", "PhysReg", " Spill "};
+
+void MIRGraph::DumpRegLocTable(RegLocation* table, int count)
+{
+ Codegen* cg = cu_->cg.get();
+ if (cg != NULL) {
+ for (int i = 0; i < count; i++) {
+ LOG(INFO) << StringPrintf("Loc[%02d] : %s, %c %c %c %c %c %c %c%d %c%d S%d",
+ table[i].orig_sreg, storage_name[table[i].location],
+ table[i].wide ? 'W' : 'N', table[i].defined ? 'D' : 'U',
+ table[i].fp ? 'F' : table[i].ref ? 'R' :'C',
+ table[i].is_const ? 'c' : 'n',
+ table[i].high_word ? 'H' : 'L', table[i].home ? 'h' : 't',
+ cg->IsFpReg(table[i].low_reg) ? 's' : 'r',
+ table[i].low_reg & cg->FpRegMask(),
+ cg->IsFpReg(table[i].high_reg) ? 's' : 'r',
+ table[i].high_reg & cg->FpRegMask(), table[i].s_reg_low);
+ }
+ } else {
+ // Either pre-regalloc or Portable.
+ for (int i = 0; i < count; i++) {
+ LOG(INFO) << StringPrintf("Loc[%02d] : %s, %c %c %c %c %c %c S%d",
+ table[i].orig_sreg, storage_name[table[i].location],
+ table[i].wide ? 'W' : 'N', table[i].defined ? 'D' : 'U',
+ table[i].fp ? 'F' : table[i].ref ? 'R' :'C',
+ table[i].is_const ? 'c' : 'n',
+ table[i].high_word ? 'H' : 'L', table[i].home ? 'h' : 't',
+ table[i].s_reg_low);
+ }
+ }
+}
+
+static const RegLocation fresh_loc = {kLocDalvikFrame, 0, 0, 0, 0, 0, 0, 0, 0,
+ INVALID_REG, INVALID_REG, INVALID_SREG,
+ INVALID_SREG};
+
+int MIRGraph::ComputeFrameSize() {
+ /* Figure out the frame size */
+ static const uint32_t kAlignMask = kStackAlignment - 1;
+ uint32_t size = (cu_->num_core_spills + cu_->num_fp_spills +
+ 1 /* filler word */ + cu_->num_regs + cu_->num_outs +
+ cu_->num_compiler_temps + 1 /* cur_method* */)
+ * sizeof(uint32_t);
+ /* Align and set */
+ return (size + kAlignMask) & ~(kAlignMask);
+}
+
+/*
+ * Simple register allocation. Some Dalvik virtual registers may
+ * be promoted to physical registers. Most of the work for temp
+ * allocation is done on the fly. We also do some initialization and
+ * type inference here.
+ */
+void MIRGraph::BuildRegLocations()
+{
+ int i;
+ RegLocation* loc;
+
+ /* Allocate the location map */
+ loc = static_cast<RegLocation*>(NewMem(cu_, GetNumSSARegs() * sizeof(*loc),
+ true, kAllocRegAlloc));
+ for (i=0; i < GetNumSSARegs(); i++) {
+ loc[i] = fresh_loc;
+ loc[i].s_reg_low = i;
+ loc[i].is_const = IsBitSet(is_constant_v_, i);
+ }
+
+ /* Patch up the locations for Method* and the compiler temps */
+ loc[cu_->method_sreg].location = kLocCompilerTemp;
+ loc[cu_->method_sreg].defined = true;
+ for (i = 0; i < cu_->num_compiler_temps; i++) {
+ CompilerTemp* ct = reinterpret_cast<CompilerTemp*>(cu_->compiler_temps.elem_list[i]);
+ loc[ct->s_reg].location = kLocCompilerTemp;
+ loc[ct->s_reg].defined = true;
+ }
+
+ cu_->reg_location = loc;
+
+ /* Allocation the promotion map */
+ int num_regs = cu_->num_dalvik_registers;
+ cu_->promotion_map = static_cast<PromotionMap*>
+ (NewMem(cu_, (num_regs + cu_->num_compiler_temps + 1) * sizeof(cu_->promotion_map[0]),
+ true, kAllocRegAlloc));
+
+ /* Add types of incoming arguments based on signature */
+ int num_ins = cu_->num_ins;
+ if (num_ins > 0) {
+ int s_reg = num_regs - num_ins;
+ if ((cu_->access_flags & kAccStatic) == 0) {
+ // For non-static, skip past "this"
+ cu_->reg_location[s_reg].defined = true;
+ cu_->reg_location[s_reg].ref = true;
+ s_reg++;
+ }
+ const char* shorty = cu_->shorty;
+ int shorty_len = strlen(shorty);
+ for (int i = 1; i < shorty_len; i++) {
+ switch (shorty[i]) {
+ case 'D':
+ cu_->reg_location[s_reg].wide = true;
+ cu_->reg_location[s_reg+1].high_word = true;
+ cu_->reg_location[s_reg+1].fp = true;
+ DCHECK_EQ(SRegToVReg(s_reg)+1, SRegToVReg(s_reg+1));
+ cu_->reg_location[s_reg].fp = true;
+ cu_->reg_location[s_reg].defined = true;
+ s_reg++;
+ break;
+ case 'J':
+ cu_->reg_location[s_reg].wide = true;
+ cu_->reg_location[s_reg+1].high_word = true;
+ DCHECK_EQ(SRegToVReg(s_reg)+1, SRegToVReg(s_reg+1));
+ cu_->reg_location[s_reg].core = true;
+ cu_->reg_location[s_reg].defined = true;
+ s_reg++;
+ break;
+ case 'F':
+ cu_->reg_location[s_reg].fp = true;
+ cu_->reg_location[s_reg].defined = true;
+ break;
+ case 'L':
+ cu_->reg_location[s_reg].ref = true;
+ cu_->reg_location[s_reg].defined = true;
+ break;
+ default:
+ cu_->reg_location[s_reg].core = true;
+ cu_->reg_location[s_reg].defined = true;
+ break;
+ }
+ s_reg++;
+ }
+ }
+
+ /* Do type & size inference pass */
+ DataflowIterator iter(this, kPreOrderDFSTraversal, true /* iterative */);
+ bool change = false;
+ for (BasicBlock* bb = iter.Next(false); bb != NULL; bb = iter.Next(change)) {
+ change = InferTypeAndSize(bb);
+ }
+
+ /*
+ * Set the s_reg_low field to refer to the pre-SSA name of the
+ * base Dalvik virtual register. Once we add a better register
+ * allocator, remove this remapping.
+ */
+ for (i=0; i < GetNumSSARegs(); i++) {
+ if (cu_->reg_location[i].location != kLocCompilerTemp) {
+ int orig_sreg = cu_->reg_location[i].s_reg_low;
+ cu_->reg_location[i].orig_sreg = orig_sreg;
+ cu_->reg_location[i].s_reg_low = SRegToVReg(orig_sreg);
+ }
+ }
+}
+
+} // namespace art