| /* |
| * 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 "CompilerInternals.h" |
| #include "Dataflow.h" |
| #include "codegen/Ralloc.h" |
| |
| STATIC bool setFp(CompilationUnit* cUnit, int index, bool isFP) { |
| bool change = false; |
| if (cUnit->regLocation[index].highWord) { |
| return change; |
| } |
| if (isFP && !cUnit->regLocation[index].fp) { |
| cUnit->regLocation[index].fp = true; |
| cUnit->regLocation[index].defined = true; |
| change = true; |
| } |
| return change; |
| } |
| |
| STATIC bool setCore(CompilationUnit* cUnit, int index, bool isCore) { |
| bool change = false; |
| if (cUnit->regLocation[index].highWord) { |
| return change; |
| } |
| if (isCore && !cUnit->regLocation[index].defined) { |
| cUnit->regLocation[index].core = true; |
| cUnit->regLocation[index].defined = true; |
| change = true; |
| } |
| return change; |
| } |
| |
| STATIC 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; |
| } |
| |
| // Try to find the next move result which might have an FP target |
| STATIC SSARepresentation* findMoveResult(MIR* mir) |
| { |
| SSARepresentation* res = NULL; |
| for (; mir; mir = mir->next) { |
| if ((mir->dalvikInsn.opcode == OP_MOVE_RESULT) || |
| (mir->dalvikInsn.opcode == OP_MOVE_RESULT_WIDE)) { |
| res = mir->ssaRep; |
| break; |
| } |
| } |
| return res; |
| } |
| |
| /* |
| * 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. |
| */ |
| STATIC 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 | DF_DA_WIDE)) { |
| if (attrs & DF_CORE_A) { |
| changed |= setCore(cUnit, ssaRep->defs[0], true); |
| } |
| if (attrs & DF_DA_WIDE) { |
| cUnit->regLocation[ssaRep->defs[0]].wide = true; |
| cUnit->regLocation[ssaRep->defs[1]].highWord = true; |
| DCHECK_EQ(oatS2VReg(cUnit, ssaRep->defs[0])+1, |
| oatS2VReg(cUnit, ssaRep->defs[1])); |
| } |
| } |
| |
| // Handles uses |
| int next = 0; |
| if (attrs & (DF_UA | DF_UA_WIDE)) { |
| if (attrs & DF_CORE_A) { |
| changed |= setCore(cUnit, ssaRep->uses[next], true); |
| } |
| if (attrs & DF_UA_WIDE) { |
| cUnit->regLocation[ssaRep->uses[next]].wide = true; |
| cUnit->regLocation[ssaRep->uses[next + 1]].highWord = true; |
| DCHECK_EQ(oatS2VReg(cUnit, ssaRep->uses[next])+1, |
| oatS2VReg(cUnit, ssaRep->uses[next + 1])); |
| next += 2; |
| } else { |
| next++; |
| } |
| } |
| if (attrs & (DF_UB | DF_UB_WIDE)) { |
| if (attrs & DF_CORE_B) { |
| changed |= setCore(cUnit, ssaRep->uses[next], true); |
| } |
| if (attrs & DF_UB_WIDE) { |
| cUnit->regLocation[ssaRep->uses[next]].wide = true; |
| cUnit->regLocation[ssaRep->uses[next + 1]].highWord = true; |
| DCHECK_EQ(oatS2VReg(cUnit, ssaRep->uses[next])+1, |
| oatS2VReg(cUnit, ssaRep->uses[next + 1])); |
| next += 2; |
| } else { |
| next++; |
| } |
| } |
| if (attrs & (DF_UC | DF_UC_WIDE)) { |
| if (attrs & DF_CORE_C) { |
| changed |= setCore(cUnit, ssaRep->uses[next], true); |
| } |
| if (attrs & DF_UC_WIDE) { |
| cUnit->regLocation[ssaRep->uses[next]].wide = true; |
| cUnit->regLocation[ssaRep->uses[next + 1]].highWord = true; |
| DCHECK_EQ(oatS2VReg(cUnit, ssaRep->uses[next])+1, |
| oatS2VReg(cUnit, ssaRep->uses[next + 1])); |
| } |
| } |
| |
| // Special-case handling for format 35c/3rc invokes |
| Opcode opcode = mir->dalvikInsn.opcode; |
| int flags = (opcode >= kNumPackedOpcodes) ? 0 : |
| dexGetFlagsFromOpcode(opcode); |
| if ((flags & kInstrInvoke) && |
| (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')) { |
| // Find move-result that consumes this result |
| SSARepresentation* tgtRep = findMoveResult(mir->next); |
| // Might be in next basic block |
| if (!tgtRep) { |
| tgtRep = findMoveResult(bb->fallThrough->firstMIRInsn); |
| } |
| // Result might not be used at all, so no move-result |
| if (tgtRep) { |
| 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, skip implicit "this" |
| if (((mir->dalvikInsn.opcode != OP_INVOKE_STATIC) && |
| (mir->dalvikInsn.opcode != OP_INVOKE_STATIC_RANGE))) { |
| cUnit->regLocation[ssaRep->uses[next]].defined = true; |
| cUnit->regLocation[ssaRep->uses[next]].core = 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]].highWord |
| = true; |
| DCHECK_EQ(oatS2VReg(cUnit, ssaRep->uses[i])+1, |
| oatS2VReg(cUnit, ssaRep->uses[i+1])); |
| i++; |
| break; |
| case 'J': |
| cUnit->regLocation[ssaRep->uses[i]].wide = true; |
| cUnit->regLocation[ssaRep->uses[i+1]].highWord |
| = true; |
| DCHECK_EQ(oatS2VReg(cUnit, ssaRep->uses[i])+1, |
| oatS2VReg(cUnit, ssaRep->uses[i+1])); |
| changed |= setCore(cUnit, ssaRep->uses[i],true); |
| i++; |
| break; |
| case 'F': |
| ssaRep->fpUse[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 |
| bool definedFP = false; |
| bool definedCore = false; |
| definedFP |= (cUnit->regLocation[ssaRep->defs[0]].defined && |
| cUnit->regLocation[ssaRep->defs[0]].fp); |
| definedCore |= (cUnit->regLocation[ssaRep->defs[0]].defined && |
| cUnit->regLocation[ssaRep->defs[0]].core); |
| for (int i = 0; i < ssaRep->numUses; i++) { |
| definedFP |= (cUnit->regLocation[ssaRep->uses[i]].defined && |
| cUnit->regLocation[ssaRep->uses[i]].fp); |
| definedCore |= (cUnit->regLocation[ssaRep->uses[i]].defined |
| && cUnit->regLocation[ssaRep->uses[i]].core); |
| } |
| /* |
| * 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 OP_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) && |
| ((cUnit->disableOpt & (1 << kPromoteRegs)) == 0)) { |
| LOG(WARNING) << art::PrettyMethod(cUnit->method_idx, *cUnit->dex_file) |
| << " op at block " << bb->id |
| << " has both fp and core uses for same def."; |
| cUnit->disableOpt |= (1 << kPromoteRegs); |
| } |
| changed |= setFp(cUnit, ssaRep->defs[0], definedFP); |
| changed |= setCore(cUnit, ssaRep->defs[0], definedCore); |
| for (int i = 0; i < ssaRep->numUses; i++) { |
| changed |= setFp(cUnit, ssaRep->uses[i], definedFP); |
| changed |= setCore(cUnit, ssaRep->uses[i], definedCore); |
| } |
| } |
| } |
| } |
| return changed; |
| } |
| |
| static const char* storageName[] = {" Frame ", "PhysReg", " Spill "}; |
| |
| void oatDumpRegLocTable(RegLocation* table, int count) |
| { |
| for (int i = 0; i < count; i++) { |
| char buf[100]; |
| snprintf(buf, 100, "Loc[%02d] : %s, %c %c %c %c %c %c%d %c%d S%d", |
| i, storageName[table[i].location], table[i].wide ? 'W' : 'N', |
| table[i].defined ? 'D' : 'U', table[i].fp ? 'F' : 'C', |
| table[i].highWord ? 'H' : 'L', table[i].home ? 'h' : 't', |
| FPREG(table[i].lowReg) ? 's' : 'r', table[i].lowReg & FP_REG_MASK, |
| FPREG(table[i].highReg) ? 's' : 'r', table[i].highReg & FP_REG_MASK, |
| table[i].sRegLow); |
| LOG(INFO) << buf; |
| } |
| } |
| |
| static const RegLocation freshLoc = {kLocDalvikFrame, 0, 0, 0, 0, 0, 0, |
| INVALID_REG, INVALID_REG, INVALID_SREG}; |
| |
| /* |
| * 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 initilization and |
| * type inference here. |
| */ |
| void oatSimpleRegAlloc(CompilationUnit* cUnit) |
| { |
| int i; |
| RegLocation* loc; |
| |
| /* Allocate the location map */ |
| loc = (RegLocation*)oatNew(cUnit->numSSARegs * sizeof(*loc), true); |
| for (i=0; i< cUnit->numSSARegs; i++) { |
| loc[i] = freshLoc; |
| loc[i].sRegLow = i; |
| } |
| cUnit->regLocation = loc; |
| |
| /* Allocation the promotion map */ |
| int numRegs = cUnit->numDalvikRegisters; |
| cUnit->promotionMap = |
| (PromotionMap*)oatNew(numRegs * sizeof(cUnit->promotionMap[0]), true); |
| |
| /* Add types of incoming arguments based on signature */ |
| int numIns = cUnit->numIns; |
| if (numIns > 0) { |
| int sReg = numRegs - numIns; |
| if ((cUnit->access_flags & art::kAccStatic) == 0) { |
| // For non-static, skip past "this" |
| cUnit->regLocation[sReg].defined = true; |
| cUnit->regLocation[sReg].core = 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; |
| DCHECK_EQ(oatS2VReg(cUnit, sReg)+1, |
| oatS2VReg(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(oatS2VReg(cUnit, sReg)+1, |
| oatS2VReg(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; |
| default: |
| cUnit->regLocation[sReg].core = true; |
| cUnit->regLocation[sReg].defined = true; |
| break; |
| } |
| sReg++; |
| } |
| } |
| |
| /* 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++) { |
| cUnit->regLocation[i].sRegLow = |
| DECODE_REG(oatConvertSSARegToDalvik(cUnit, loc[i].sRegLow)); |
| } |
| |
| cUnit->coreSpillMask = 0; |
| cUnit->fpSpillMask = 0; |
| cUnit->numCoreSpills = 0; |
| |
| oatDoPromotion(cUnit); |
| |
| if (cUnit->printMe && !(cUnit->disableOpt & (1 << kPromoteRegs))) { |
| LOG(INFO) << "After Promotion"; |
| oatDumpRegLocTable(cUnit->regLocation, cUnit->numSSARegs); |
| } |
| |
| /* Figure out the frame size */ |
| cUnit->numPadding = (STACK_ALIGN_WORDS - |
| (cUnit->numCoreSpills + cUnit->numFPSpills + cUnit->numRegs + |
| cUnit->numOuts + 2)) & (STACK_ALIGN_WORDS-1); |
| cUnit->frameSize = (cUnit->numCoreSpills + cUnit->numFPSpills + |
| cUnit->numRegs + cUnit->numOuts + |
| cUnit->numPadding + 2) * 4; |
| cUnit->insOffset = cUnit->frameSize + 4; |
| cUnit->regsOffset = (cUnit->numOuts + cUnit->numPadding + 1) * 4; |
| } |
