2 * Copyright (C) 2009 The Android Open Source Project
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
18 #include "CompilerInternals.h"
21 typedef struct LiveRange {
28 static int computeLiveRange(LiveRange *list, BasicBlock *bb, int seqNum)
33 if (bb->blockType != kDalvikByteCode &&
34 bb->blockType != kTraceEntryBlock)
37 for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
38 SSARepresentation *ssaRep = mir->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;
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;
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
63 static void inferTypes(CompilationUnit *cUnit, BasicBlock *bb)
66 if (bb->blockType != kDalvikByteCode &&
67 bb->blockType != kTraceEntryBlock)
70 for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
71 SSARepresentation *ssaRep = mir->ssaRep;
74 for (i=0; ssaRep->fpUse && i< ssaRep->numUses; i++) {
76 cUnit->regLocation[ssaRep->uses[i]].fp = true;
78 for (i=0; ssaRep->fpDef && i< ssaRep->numDefs; i++) {
80 cUnit->regLocation[ssaRep->defs[i]].fp = true;
87 * Determine whether to use simple or aggressive register allocation. In
88 * general, loops and full methods will get aggressive.
90 static bool simpleTrace(CompilationUnit *cUnit)
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.
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
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.
119 static const RegLocation freshLoc = {kLocDalvikFrame, 0, 0, INVALID_REG,
120 INVALID_REG, INVALID_SREG};
121 void dvmCompilerRegAlloc(CompilationUnit *cUnit)
128 /* Allocate the location map */
129 loc = (RegLocation*)dvmCompilerNew(cUnit->numSSARegs * sizeof(*loc), true);
130 for (i=0; i< cUnit->numSSARegs; i++) {
134 cUnit->regLocation = loc;
136 /* Do type inference pass */
137 for (i=0; i < cUnit->numBlocks; i++) {
138 inferTypes(cUnit, cUnit->blockList[i]);
141 if (simpleTrace(cUnit)) {
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.
147 for (i=0; i < cUnit->numSSARegs; i++) {
148 cUnit->regLocation[i].sRegLow =
149 DECODE_REG(dvmConvertSSARegToDalvik(cUnit, loc[i].sRegLow));
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