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