vm/compiler/Ralloc.c

   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 static 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 }