1/* 2 * Copyright (C) 2009 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17#include "Dalvik.h" 18#include "CompilerInternals.h" 19#include "Dataflow.h" 20 21typedef struct LiveRange { 22 int ssaName; 23 bool active; 24 int first; 25 int last; 26} LiveRange; 27 28int computeLiveRange(LiveRange *list, BasicBlock *bb, int seqNum) 29{ 30 MIR *mir; 31 int i; 32 33 if (bb->blockType != kDalvikByteCode && 34 bb->blockType != kEntryBlock) 35 return seqNum; 36 37 for (mir = bb->firstMIRInsn; mir; mir = mir->next) { 38 SSARepresentation *ssaRep = mir->ssaRep; 39 mir->seqNum = seqNum; 40 if (ssaRep) { 41 for (i=0; i< ssaRep->numUses; i++) { 42 int reg = ssaRep->uses[i]; 43 list[reg].first = MIN(list[reg].first, seqNum); 44 list[reg].active = true; 45 } 46 for (i=0; i< ssaRep->numDefs; i++) { 47 int reg = ssaRep->defs[i]; 48 list[reg].last = MAX(list[reg].last, seqNum + 1); 49 list[reg].active = true; 50 } 51 seqNum += 2; 52 } 53 } 54 return seqNum; 55} 56 57/* 58 * Quick & dirty - make FP usage sticky. This is strictly a hint - local 59 * code generation will handle misses. It might be worthwhile to collaborate 60 * with dx/dexopt to avoid reusing the same Dalvik temp for values of 61 * different types. 62 */ 63static void inferTypes(CompilationUnit *cUnit, BasicBlock *bb) 64{ 65 MIR *mir; 66 if (bb->blockType != kDalvikByteCode && 67 bb->blockType != kEntryBlock) 68 return; 69 70 for (mir = bb->firstMIRInsn; mir; mir = mir->next) { 71 SSARepresentation *ssaRep = mir->ssaRep; 72 if (ssaRep) { 73 int i; 74 for (i=0; ssaRep->fpUse && i< ssaRep->numUses; i++) { 75 if (ssaRep->fpUse[i]) 76 cUnit->regLocation[ssaRep->uses[i]].fp = true; 77 } 78 for (i=0; ssaRep->fpDef && i< ssaRep->numDefs; i++) { 79 if (ssaRep->fpDef[i]) 80 cUnit->regLocation[ssaRep->defs[i]].fp = true; 81 } 82 } 83 } 84} 85 86/* 87 * Determine whether to use simple or aggressive register allocation. In 88 * general, loops and full methods will get aggressive. 89 */ 90static bool simpleTrace(CompilationUnit *cUnit) 91{ 92 //TODO: flesh out 93 return true; 94} 95 96/* 97 * Target-independent register allocation. Requires target-dependent 98 * helper functions and assumes free list, temp list and spill region. 99 * Uses a variant of linear scan and produces a mapping between SSA names 100 * and location. Location may be original Dalvik register, hardware 101 * register or spill location. 102 * 103 * Method: 104 * 0. Allocate the structure to hold the SSA name life ranges 105 * 1. Number each MIR instruction, counting by 2. 106 * +0 -> The "read" of the operands 107 * +1 -> The definition of the target resource 108 * 2. Compute live ranges for all SSA names *not* including the 109 * subscript 0 original Dalvik names. Phi functions ignored 110 * at this point. 111 * 3. Sort the live range list by lowest range start. 112 * 4. Process and remove all Phi functions. 113 * o If there is no live range collisions among all operands and 114 * the target of a Phi function, collapse operands and target 115 * and rewrite using target SSA name. 116 * o If there is a collision, introduce copies. 117 * 5. Allocate in order of increasing live range start. 118 */ 119static const RegLocation freshLoc = {kLocDalvikFrame, 0, 0, INVALID_REG, 120 INVALID_REG, INVALID_SREG}; 121void dvmCompilerRegAlloc(CompilationUnit *cUnit) 122{ 123 int i; 124 int seqNum = 0; 125 LiveRange *ranges; 126 RegLocation *loc; 127 int *ssaToDalvikMap = (int *) cUnit->ssaToDalvikMap->elemList; 128 129 /* Allocate the location map */ 130 loc = (RegLocation*)dvmCompilerNew(cUnit->numSSARegs * sizeof(*loc), true); 131 for (i=0; i< cUnit->numSSARegs; i++) { 132 loc[i] = freshLoc; 133 loc[i].sRegLow = i; 134 } 135 cUnit->regLocation = loc; 136 137 /* Do type inference pass */ 138 for (i=0; i < cUnit->numBlocks; i++) { 139 inferTypes(cUnit, cUnit->blockList[i]); 140 } 141 142 if (simpleTrace(cUnit)) { 143 /* 144 * Just rename everything back to subscript 0 names and don't do 145 * any explicit promotion. Local allocator will opportunistically 146 * promote on the fly. 147 */ 148 for (i=0; i < cUnit->numSSARegs; i++) { 149 cUnit->regLocation[i].sRegLow = 150 DECODE_REG(dvmConvertSSARegToDalvik(cUnit, loc[i].sRegLow)); 151 } 152 } else { 153 // Compute live ranges 154 ranges = dvmCompilerNew(cUnit->numSSARegs * sizeof(*ranges), true); 155 for (i=0; i < cUnit->numSSARegs; i++) 156 ranges[i].active = false; 157 seqNum = computeLiveRange(ranges, cUnit->blockList[i], seqNum); 158 //TODO: phi squash & linear scan promotion 159 } 160} 161