Home | History | Annotate | Download | only in compiler 
      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 
     21 typedef struct LiveRange {
     22     int ssaName;
     23     bool active;
     24     int first;
     25     int last;
     26 } LiveRange;
     27 
     28 int computeLiveRange(LiveRange *list, BasicBlock *bb, int seqNum)
     29 {
     30     MIR *mir;
     31     int i;
     32 
     33     if (bb->blockType != kDalvikByteCode &&
     34         bb->blockType != kTraceEntryBlock)
     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  */
     63 static void inferTypes(CompilationUnit *cUnit, BasicBlock *bb)
     64 {
     65     MIR *mir;
     66     if (bb->blockType != kDalvikByteCode &&
     67         bb->blockType != kTraceEntryBlock)
     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  */
     90 static 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  */
    119 static const RegLocation freshLoc = {kLocDalvikFrame, 0, 0, INVALID_REG,
    120                                      INVALID_REG, INVALID_SREG};
    121 void dvmCompilerRegAlloc(CompilationUnit *cUnit)
    122 {
    123     int i;
    124     int seqNum = 0;
    125     LiveRange *ranges;
    126     RegLocation *loc;
    127 
    128     /* Allocate the location map */
    129     loc = (RegLocation*)dvmCompilerNew(cUnit->numSSARegs * sizeof(*loc), true);
    130     for (i=0; i< cUnit->numSSARegs; i++) {
    131         loc[i] = freshLoc;
    132         loc[i].sRegLow = i;
    133     }
    134     cUnit->regLocation = loc;
    135 
    136     /* Do type inference pass */
    137     for (i=0; i < cUnit->numBlocks; i++) {
    138         inferTypes(cUnit, cUnit->blockList[i]);
    139     }
    140 
    141     if (simpleTrace(cUnit)) {
    142         /*
    143          * Just rename everything back to subscript 0 names and don't do
    144          * any explicit promotion.  Local allocator will opportunistically
    145          * promote on the fly.
    146          */
    147         for (i=0; i < cUnit->numSSARegs; i++) {
    148             cUnit->regLocation[i].sRegLow =
    149                 DECODE_REG(dvmConvertSSARegToDalvik(cUnit, loc[i].sRegLow));
    150         }
    151     } else {
    152         // Compute live ranges
    153         ranges = dvmCompilerNew(cUnit->numSSARegs * sizeof(*ranges), true);
    154         for (i=0; i < cUnit->numSSARegs; i++)
    155             ranges[i].active = false;
    156         seqNum = computeLiveRange(ranges, cUnit->blockList[i], seqNum);
    157         //TODO: phi squash & linear scan promotion
    158     }
    159 }
    160