diff options
Diffstat (limited to 'src/compiler/ralloc.cc')
| -rw-r--r-- | src/compiler/ralloc.cc | 531 |
1 files changed, 531 insertions, 0 deletions
diff --git a/src/compiler/ralloc.cc b/src/compiler/ralloc.cc new file mode 100644 index 0000000000..d9c6a5716a --- /dev/null +++ b/src/compiler/ralloc.cc @@ -0,0 +1,531 @@ +/* + * 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 "dalvik.h" +#include "compiler_internals.h" +#include "dataflow.h" +#include "codegen/ralloc.h" + +namespace art { + +bool setFp(CompilationUnit* cUnit, int index, bool isFP) { + bool change = false; + if (isFP && !cUnit->regLocation[index].fp) { + cUnit->regLocation[index].fp = true; + cUnit->regLocation[index].defined = true; + change = true; + } + return change; +} + +bool setCore(CompilationUnit* cUnit, int index, bool isCore) { + bool change = false; + if (isCore && !cUnit->regLocation[index].defined) { + cUnit->regLocation[index].core = true; + cUnit->regLocation[index].defined = true; + change = true; + } + return change; +} + +bool setRef(CompilationUnit* cUnit, int index, bool isRef) { + bool change = false; + if (isRef && !cUnit->regLocation[index].defined) { + cUnit->regLocation[index].ref = true; + cUnit->regLocation[index].defined = true; + change = true; + } + return change; +} + +bool setWide(CompilationUnit* cUnit, int index, bool isWide) { + bool change = false; + if (isWide && !cUnit->regLocation[index].wide) { + cUnit->regLocation[index].wide = true; + change = true; + } + return change; +} + +bool setHigh(CompilationUnit* cUnit, int index, bool isHigh) { + bool change = false; + if (isHigh && !cUnit->regLocation[index].highWord) { + cUnit->regLocation[index].highWord = true; + change = true; + } + return change; +} + +bool remapNames(CompilationUnit* cUnit, BasicBlock* bb) +{ + if (bb->blockType != kDalvikByteCode && bb->blockType != kEntryBlock && + bb->blockType != kExitBlock) + return false; + + for (MIR* mir = bb->firstMIRInsn; mir; mir = mir->next) { + SSARepresentation *ssaRep = mir->ssaRep; + if (ssaRep) { + for (int i = 0; i < ssaRep->numUses; i++) { + ssaRep->uses[i] = cUnit->phiAliasMap[ssaRep->uses[i]]; + } + for (int i = 0; i < ssaRep->numDefs; i++) { + ssaRep->defs[i] = cUnit->phiAliasMap[ssaRep->defs[i]]; + } + } + } + return false; +} + +/* + * 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 inferTypeAndSize(CompilationUnit* cUnit, BasicBlock* bb) +{ + MIR *mir; + bool changed = false; // Did anything change? + + if (bb->dataFlowInfo == NULL) return false; + if (bb->blockType != kDalvikByteCode && bb->blockType != kEntryBlock) + return false; + + for (mir = bb->firstMIRInsn; mir; mir = mir->next) { + SSARepresentation *ssaRep = mir->ssaRep; + if (ssaRep) { + int attrs = oatDataFlowAttributes[mir->dalvikInsn.opcode]; + + // Handle defs + if (attrs & DF_DA) { + if (attrs & DF_CORE_A) { + changed |= setCore(cUnit, ssaRep->defs[0], true); + } + if (attrs & DF_REF_A) { + changed |= setRef(cUnit, ssaRep->defs[0], true); + } + if (attrs & DF_A_WIDE) { + cUnit->regLocation[ssaRep->defs[0]].wide = true; + cUnit->regLocation[ssaRep->defs[1]].wide = true; + cUnit->regLocation[ssaRep->defs[1]].highWord = true; + DCHECK_EQ(SRegToVReg(cUnit, ssaRep->defs[0])+1, + SRegToVReg(cUnit, ssaRep->defs[1])); + } + } + + // Handles uses + int next = 0; + if (attrs & DF_UA) { + if (attrs & DF_CORE_A) { + changed |= setCore(cUnit, ssaRep->uses[next], true); + } + if (attrs & DF_REF_A) { + changed |= setRef(cUnit, ssaRep->uses[next], true); + } + if (attrs & DF_A_WIDE) { + cUnit->regLocation[ssaRep->uses[next]].wide = true; + cUnit->regLocation[ssaRep->uses[next + 1]].wide = true; + cUnit->regLocation[ssaRep->uses[next + 1]].highWord = true; + DCHECK_EQ(SRegToVReg(cUnit, ssaRep->uses[next])+1, + SRegToVReg(cUnit, ssaRep->uses[next + 1])); + next += 2; + } else { + next++; + } + } + if (attrs & DF_UB) { + if (attrs & DF_CORE_B) { + changed |= setCore(cUnit, ssaRep->uses[next], true); + } + if (attrs & DF_REF_B) { + changed |= setRef(cUnit, ssaRep->uses[next], true); + } + if (attrs & DF_B_WIDE) { + cUnit->regLocation[ssaRep->uses[next]].wide = true; + cUnit->regLocation[ssaRep->uses[next + 1]].wide = true; + cUnit->regLocation[ssaRep->uses[next + 1]].highWord = true; + DCHECK_EQ(SRegToVReg(cUnit, ssaRep->uses[next])+1, + SRegToVReg(cUnit, ssaRep->uses[next + 1])); + next += 2; + } else { + next++; + } + } + if (attrs & DF_UC) { + if (attrs & DF_CORE_C) { + changed |= setCore(cUnit, ssaRep->uses[next], true); + } + if (attrs & DF_REF_C) { + changed |= setRef(cUnit, ssaRep->uses[next], true); + } + if (attrs & DF_C_WIDE) { + cUnit->regLocation[ssaRep->uses[next]].wide = true; + cUnit->regLocation[ssaRep->uses[next + 1]].wide = true; + cUnit->regLocation[ssaRep->uses[next + 1]].highWord = true; + DCHECK_EQ(SRegToVReg(cUnit, ssaRep->uses[next])+1, + SRegToVReg(cUnit, ssaRep->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(cUnit->shorty[0]) { + case 'I': + changed |= setCore(cUnit, ssaRep->uses[0], true); + break; + case 'J': + changed |= setCore(cUnit, ssaRep->uses[0], true); + changed |= setCore(cUnit, ssaRep->uses[1], true); + cUnit->regLocation[ssaRep->uses[0]].wide = true; + cUnit->regLocation[ssaRep->uses[1]].wide = true; + cUnit->regLocation[ssaRep->uses[1]].highWord = true; + break; + case 'F': + changed |= setFp(cUnit, ssaRep->uses[0], true); + break; + case 'D': + changed |= setFp(cUnit, ssaRep->uses[0], true); + changed |= setFp(cUnit, ssaRep->uses[1], true); + cUnit->regLocation[ssaRep->uses[0]].wide = true; + cUnit->regLocation[ssaRep->uses[1]].wide = true; + cUnit->regLocation[ssaRep->uses[1]].highWord = true; + break; + case 'L': + changed |= setRef(cUnit, ssaRep->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 = oatGetShortyFromTargetIdx(cUnit, target_idx); + // Handle result type if floating point + if ((shorty[0] == 'F') || (shorty[0] == 'D')) { + MIR* moveResultMIR = oatFindMoveResult(cUnit, bb, mir); + // Result might not be used at all, so no move-result + if (moveResultMIR && (moveResultMIR->dalvikInsn.opcode != + Instruction::MOVE_RESULT_OBJECT)) { + SSARepresentation* tgtRep = moveResultMIR->ssaRep; + DCHECK(tgtRep != NULL); + tgtRep->fpDef[0] = true; + changed |= setFp(cUnit, tgtRep->defs[0], true); + if (shorty[0] == 'D') { + tgtRep->fpDef[1] = true; + changed |= setFp(cUnit, tgtRep->defs[1], true); + } + } + } + int numUses = 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))) { + cUnit->regLocation[ssaRep->uses[next]].defined = true; + cUnit->regLocation[ssaRep->uses[next]].ref = true; + next++; + } + uint32_t cpos = 1; + if (strlen(shorty) > 1) { + for (int i = next; i < numUses;) { + DCHECK_LT(cpos, strlen(shorty)); + switch (shorty[cpos++]) { + case 'D': + ssaRep->fpUse[i] = true; + ssaRep->fpUse[i+1] = true; + cUnit->regLocation[ssaRep->uses[i]].wide = true; + cUnit->regLocation[ssaRep->uses[i+1]].wide = true; + cUnit->regLocation[ssaRep->uses[i+1]].highWord = true; + DCHECK_EQ(SRegToVReg(cUnit, ssaRep->uses[i])+1, + SRegToVReg(cUnit, ssaRep->uses[i+1])); + i++; + break; + case 'J': + cUnit->regLocation[ssaRep->uses[i]].wide = true; + cUnit->regLocation[ssaRep->uses[i+1]].wide = true; + cUnit->regLocation[ssaRep->uses[i+1]].highWord = true; + DCHECK_EQ(SRegToVReg(cUnit, ssaRep->uses[i])+1, + SRegToVReg(cUnit, ssaRep->uses[i+1])); + changed |= setCore(cUnit, ssaRep->uses[i],true); + i++; + break; + case 'F': + ssaRep->fpUse[i] = true; + break; + case 'L': + changed |= setRef(cUnit,ssaRep->uses[i], true); + break; + default: + changed |= setCore(cUnit,ssaRep->uses[i], true); + break; + } + i++; + } + } + } + + for (int i=0; ssaRep->fpUse && i< ssaRep->numUses; i++) { + if (ssaRep->fpUse[i]) + changed |= setFp(cUnit, ssaRep->uses[i], true); + } + for (int i=0; ssaRep->fpDef && i< ssaRep->numDefs; i++) { + if (ssaRep->fpDef[i]) + changed |= setFp(cUnit, ssaRep->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 isPhi = (static_cast<int>(mir->dalvikInsn.opcode) == + kMirOpPhi); + RegLocation rlTemp = cUnit->regLocation[ssaRep->defs[0]]; + bool definedFP = rlTemp.defined && rlTemp.fp; + bool definedCore = rlTemp.defined && rlTemp.core; + bool definedRef = rlTemp.defined && rlTemp.ref; + bool isWide = rlTemp.wide || ((attrs & DF_A_WIDE) != 0); + bool isHigh = isPhi && rlTemp.wide && rlTemp.highWord; + for (int i = 0; i < ssaRep->numUses;i++) { + rlTemp = cUnit->regLocation[ssaRep->uses[i]]; + definedFP |= rlTemp.defined && rlTemp.fp; + definedCore |= rlTemp.defined && rlTemp.core; + definedRef |= rlTemp.defined && rlTemp.ref; + isWide |= rlTemp.wide; + isHigh |= isPhi && rlTemp.wide && rlTemp.highWord; + } + /* + * 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 ((definedFP && (definedCore | definedRef)) && + ((cUnit->disableOpt & (1 << kPromoteRegs)) == 0)) { + LOG(WARNING) << PrettyMethod(cUnit->method_idx, *cUnit->dex_file) + << " op at block " << bb->id + << " has both fp and core/ref uses for same def."; + cUnit->disableOpt |= (1 << kPromoteRegs); + } + changed |= setFp(cUnit, ssaRep->defs[0], definedFP); + changed |= setCore(cUnit, ssaRep->defs[0], definedCore); + changed |= setRef(cUnit, ssaRep->defs[0], definedRef); + changed |= setWide(cUnit, ssaRep->defs[0], isWide); + changed |= setHigh(cUnit, ssaRep->defs[0], isHigh); + if (attrs & DF_A_WIDE) { + changed |= setWide(cUnit, ssaRep->defs[1], true); + changed |= setHigh(cUnit, ssaRep->defs[1], true); + } + for (int i = 0; i < ssaRep->numUses; i++) { + changed |= setFp(cUnit, ssaRep->uses[i], definedFP); + changed |= setCore(cUnit, ssaRep->uses[i], definedCore); + changed |= setRef(cUnit, ssaRep->uses[i], definedRef); + changed |= setWide(cUnit, ssaRep->uses[i], isWide); + changed |= setHigh(cUnit, ssaRep->uses[i], isHigh); + } + if (attrs & DF_A_WIDE) { + DCHECK_EQ(ssaRep->numUses, 2); + changed |= setWide(cUnit, ssaRep->uses[1], true); + changed |= setHigh(cUnit, ssaRep->uses[1], true); + } + } + } + } + return changed; +} + +static const char* storageName[] = {" Frame ", "PhysReg", " Spill "}; + +void oatDumpRegLocTable(RegLocation* table, int count) +{ + for (int i = 0; i < count; i++) { + LOG(INFO) << StringPrintf("Loc[%02d] : %s, %c %c %c %c %c %c%d %c%d S%d", + table[i].origSReg, storageName[table[i].location], + table[i].wide ? 'W' : 'N', table[i].defined ? 'D' : 'U', + table[i].fp ? 'F' : table[i].ref ? 'R' :'C', + table[i].highWord ? 'H' : 'L', table[i].home ? 'h' : 't', + oatIsFpReg(table[i].lowReg) ? 's' : 'r', + table[i].lowReg & oatFpRegMask(), + oatIsFpReg(table[i].highReg) ? 's' : 'r', + table[i].highReg & oatFpRegMask(), table[i].sRegLow); + } +} + +void oatDumpRegLoc(RegLocation loc) { + oatDumpRegLocTable(&loc, 1); +} + +static const RegLocation freshLoc = {kLocDalvikFrame, 0, 0, 0, 0, 0, 0, 0, 0, + INVALID_REG, INVALID_REG, INVALID_SREG, + INVALID_SREG}; + +int oatComputeFrameSize(CompilationUnit* cUnit) { + /* Figure out the frame size */ + static const uint32_t kAlignMask = kStackAlignment - 1; + uint32_t size = (cUnit->numCoreSpills + cUnit->numFPSpills + + 1 /* filler word */ + cUnit->numRegs + cUnit->numOuts + + cUnit->numCompilerTemps + 1 /* curMethod* */) + * 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 oatSimpleRegAlloc(CompilationUnit* cUnit) +{ + int i; + RegLocation* loc; + + /* Allocate the location map */ + loc = (RegLocation*)oatNew(cUnit, cUnit->numSSARegs * sizeof(*loc), true, + kAllocRegAlloc); + for (i=0; i< cUnit->numSSARegs; i++) { + loc[i] = freshLoc; + loc[i].sRegLow = i; + loc[i].isConst = oatIsBitSet(cUnit->isConstantV, i); + } + + /* Patch up the locations for Method* and the compiler temps */ + loc[cUnit->methodSReg].location = kLocCompilerTemp; + loc[cUnit->methodSReg].defined = true; + for (i = 0; i < cUnit->numCompilerTemps; i++) { + CompilerTemp* ct = (CompilerTemp*)cUnit->compilerTemps.elemList[i]; + loc[ct->sReg].location = kLocCompilerTemp; + loc[ct->sReg].defined = true; + } + + cUnit->regLocation = loc; + + /* Allocation the promotion map */ + int numRegs = cUnit->numDalvikRegisters; + cUnit->promotionMap = + (PromotionMap*)oatNew(cUnit, (numRegs + cUnit->numCompilerTemps + 1) * + sizeof(cUnit->promotionMap[0]), true, + kAllocRegAlloc); + + /* Add types of incoming arguments based on signature */ + int numIns = cUnit->numIns; + if (numIns > 0) { + int sReg = numRegs - numIns; + if ((cUnit->access_flags & kAccStatic) == 0) { + // For non-static, skip past "this" + cUnit->regLocation[sReg].defined = true; + cUnit->regLocation[sReg].ref = true; + sReg++; + } + const char* shorty = cUnit->shorty; + int shorty_len = strlen(shorty); + for (int i = 1; i < shorty_len; i++) { + switch (shorty[i]) { + case 'D': + cUnit->regLocation[sReg].wide = true; + cUnit->regLocation[sReg+1].highWord = true; + cUnit->regLocation[sReg+1].fp = true; + DCHECK_EQ(SRegToVReg(cUnit, sReg)+1, SRegToVReg(cUnit, sReg+1)); + cUnit->regLocation[sReg].fp = true; + cUnit->regLocation[sReg].defined = true; + sReg++; + break; + case 'J': + cUnit->regLocation[sReg].wide = true; + cUnit->regLocation[sReg+1].highWord = true; + DCHECK_EQ(SRegToVReg(cUnit, sReg)+1, SRegToVReg(cUnit, sReg+1)); + cUnit->regLocation[sReg].core = true; + cUnit->regLocation[sReg].defined = true; + sReg++; + break; + case 'F': + cUnit->regLocation[sReg].fp = true; + cUnit->regLocation[sReg].defined = true; + break; + case 'L': + cUnit->regLocation[sReg].ref = true; + cUnit->regLocation[sReg].defined = true; + break; + default: + cUnit->regLocation[sReg].core = true; + cUnit->regLocation[sReg].defined = true; + break; + } + sReg++; + } + } + + if (!cUnit->genBitcode) { + /* Remap names */ + oatDataFlowAnalysisDispatcher(cUnit, remapNames, + kPreOrderDFSTraversal, + false /* isIterative */); + } + + /* Do type & size inference pass */ + oatDataFlowAnalysisDispatcher(cUnit, inferTypeAndSize, + kPreOrderDFSTraversal, + true /* isIterative */); + + /* + * Set the sRegLow 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 < cUnit->numSSARegs; i++) { + if (cUnit->regLocation[i].location != kLocCompilerTemp) { + int origSReg = cUnit->regLocation[i].sRegLow; + cUnit->regLocation[i].origSReg = origSReg; + cUnit->regLocation[i].sRegLow = SRegToVReg(cUnit, origSReg); + } + } + + cUnit->coreSpillMask = 0; + cUnit->fpSpillMask = 0; + cUnit->numCoreSpills = 0; + + oatDoPromotion(cUnit); + + /* Get easily-accessable post-promotion copy of RegLocation for Method* */ + cUnit->methodLoc = cUnit->regLocation[cUnit->methodSReg]; + + if (cUnit->printMe && !(cUnit->disableOpt & (1 << kPromoteRegs))) { + LOG(INFO) << "After Promotion"; + oatDumpRegLocTable(cUnit->regLocation, cUnit->numSSARegs); + } + + /* Set the frame size */ + cUnit->frameSize = oatComputeFrameSize(cUnit); +} + +} // namespace art |