11465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee/* 21465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * Copyright (C) 2009 The Android Open Source Project 31465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * 41465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * Licensed under the Apache License, Version 2.0 (the "License"); 51465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * you may not use this file except in compliance with the License. 61465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * You may obtain a copy of the License at 71465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * 81465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * http://www.apache.org/licenses/LICENSE-2.0 91465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * 101465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * Unless required by applicable law or agreed to in writing, software 111465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * distributed under the License is distributed on an "AS IS" BASIS, 121465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 131465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * See the License for the specific language governing permissions and 141465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * limitations under the License. 151465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee */ 161465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee 171465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee#include "Dalvik.h" 181465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee#include "CompilerInternals.h" 191465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee#include "Dataflow.h" 201465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee 211465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbeetypedef struct LiveRange { 221465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee int ssaName; 231465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee bool active; 241465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee int first; 251465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee int last; 261465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee} LiveRange; 271465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee 281465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbeeint computeLiveRange(LiveRange *list, BasicBlock *bb, int seqNum) 291465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee{ 301465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee MIR *mir; 311465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee int i; 321465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee 331465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee if (bb->blockType != kDalvikByteCode && 341465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee bb->blockType != kEntryBlock) 351465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee return seqNum; 361465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee 371465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee for (mir = bb->firstMIRInsn; mir; mir = mir->next) { 381465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee SSARepresentation *ssaRep = mir->ssaRep; 391465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee mir->seqNum = seqNum; 401465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee if (ssaRep) { 411465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee for (i=0; i< ssaRep->numUses; i++) { 421465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee int reg = ssaRep->uses[i]; 431465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee list[reg].first = MIN(list[reg].first, seqNum); 441465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee list[reg].active = true; 451465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee } 461465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee for (i=0; i< ssaRep->numDefs; i++) { 471465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee int reg = ssaRep->defs[i]; 481465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee list[reg].last = MAX(list[reg].last, seqNum + 1); 491465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee list[reg].active = true; 501465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee } 511465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee seqNum += 2; 521465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee } 531465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee } 541465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee return seqNum; 551465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee} 561465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee 571465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee/* 581465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * Quick & dirty - make FP usage sticky. This is strictly a hint - local 591465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * code generation will handle misses. It might be worthwhile to collaborate 601465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * with dx/dexopt to avoid reusing the same Dalvik temp for values of 611465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * different types. 621465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee */ 631465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbeestatic void inferTypes(CompilationUnit *cUnit, BasicBlock *bb) 641465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee{ 651465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee MIR *mir; 661465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee if (bb->blockType != kDalvikByteCode && 671465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee bb->blockType != kEntryBlock) 681465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee return; 691465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee 701465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee for (mir = bb->firstMIRInsn; mir; mir = mir->next) { 711465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee SSARepresentation *ssaRep = mir->ssaRep; 721465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee if (ssaRep) { 731465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee int i; 741465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee for (i=0; ssaRep->fpUse && i< ssaRep->numUses; i++) { 751465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee if (ssaRep->fpUse[i]) 761465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee cUnit->regLocation[ssaRep->uses[i]].fp = true; 771465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee } 781465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee for (i=0; ssaRep->fpDef && i< ssaRep->numDefs; i++) { 791465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee if (ssaRep->fpDef[i]) 801465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee cUnit->regLocation[ssaRep->defs[i]].fp = true; 811465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee } 821465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee } 831465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee } 841465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee} 851465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee 861465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee/* 871465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * Determine whether to use simple or aggressive register allocation. In 881465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * general, loops and full methods will get aggressive. 891465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee */ 901465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbeestatic bool simpleTrace(CompilationUnit *cUnit) 911465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee{ 921465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee //TODO: flesh out 931465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee return true; 941465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee} 951465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee 961465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee/* 971465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * Target-independent register allocation. Requires target-dependent 981465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * helper functions and assumes free list, temp list and spill region. 991465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * Uses a variant of linear scan and produces a mapping between SSA names 1001465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * and location. Location may be original Dalvik register, hardware 1011465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * register or spill location. 1021465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * 1031465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * Method: 1041465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * 0. Allocate the structure to hold the SSA name life ranges 1051465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * 1. Number each MIR instruction, counting by 2. 1061465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * +0 -> The "read" of the operands 1071465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * +1 -> The definition of the target resource 1081465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * 2. Compute live ranges for all SSA names *not* including the 1091465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * subscript 0 original Dalvik names. Phi functions ignored 1101465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * at this point. 1111465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * 3. Sort the live range list by lowest range start. 1121465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * 4. Process and remove all Phi functions. 1131465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * o If there is no live range collisions among all operands and 1141465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * the target of a Phi function, collapse operands and target 1151465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * and rewrite using target SSA name. 1161465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * o If there is a collision, introduce copies. 1171465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * 5. Allocate in order of increasing live range start. 1181465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee */ 1191465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbeestatic const RegLocation freshLoc = {kLocDalvikFrame, 0, 0, INVALID_REG, 1201465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee INVALID_REG, INVALID_SREG}; 1211465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbeevoid dvmCompilerRegAlloc(CompilationUnit *cUnit) 1221465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee{ 1231465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee int i; 1241465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee int seqNum = 0; 1251465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee LiveRange *ranges; 1261465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee RegLocation *loc; 1271465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee int *ssaToDalvikMap = (int *) cUnit->ssaToDalvikMap->elemList; 1281465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee 1291465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee /* Allocate the location map */ 1301465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee loc = (RegLocation*)dvmCompilerNew(cUnit->numSSARegs * sizeof(*loc), true); 1311465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee for (i=0; i< cUnit->numSSARegs; i++) { 1321465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee loc[i] = freshLoc; 1331465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee loc[i].sRegLow = i; 1341465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee } 1351465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee cUnit->regLocation = loc; 1361465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee 1371465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee /* Do type inference pass */ 1381465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee for (i=0; i < cUnit->numBlocks; i++) { 1391465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee inferTypes(cUnit, cUnit->blockList[i]); 1401465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee } 1411465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee 1421465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee if (simpleTrace(cUnit)) { 1431465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee /* 1441465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * Just rename everything back to subscript 0 names and don't do 1451465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * any explicit promotion. Local allocator will opportunistically 1461465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee * promote on the fly. 1471465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee */ 1481465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee for (i=0; i < cUnit->numSSARegs; i++) { 1491465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee cUnit->regLocation[i].sRegLow = 1501465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee DECODE_REG(dvmConvertSSARegToDalvik(cUnit, loc[i].sRegLow)); 1511465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee } 1521465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee } else { 1531465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee // Compute live ranges 1541465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee ranges = dvmCompilerNew(cUnit->numSSARegs * sizeof(*ranges), true); 1551465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee for (i=0; i < cUnit->numSSARegs; i++) 1561465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee ranges[i].active = false; 1571465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee seqNum = computeLiveRange(ranges, cUnit->blockList[i], seqNum); 1581465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee //TODO: phi squash & linear scan promotion 1591465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee } 1601465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee} 161