FirstFitAllocator.java revision 579d7739c53a2707ad711a2d2cae46d7d782f061 
1/*
2 * Copyright (C) 2007 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
17package com.android.dx.ssa.back;
18
19import com.android.dx.rop.code.CstInsn;
20import com.android.dx.rop.cst.CstInteger;
21import com.android.dx.ssa.NormalSsaInsn;
22import com.android.dx.ssa.BasicRegisterMapper;
23import com.android.dx.ssa.RegisterMapper;
24import com.android.dx.ssa.SsaMethod;
25import com.android.dx.util.IntSet;
26import com.android.dx.util.BitIntSet;
27
28import java.util.BitSet;
29import java.util.ArrayList;
30
31/**
32 * Allocates registers via a naive n^2 register allocator.
33 * This allocator does not try to co-locate local variables or deal
34 * intelligently with different size register uses.
35 */
36public class FirstFitAllocator extends RegisterAllocator {
37    /**
38     * If true, allocator places parameters at the top of the frame
39     * in calling-convention order.
40     */
41    private static final boolean PRESLOT_PARAMS = true;
42
43    /** indexed by old reg; the set of old regs we've mapped */
44    private final BitSet mapped;
45
46    /** {@inheritDoc} */
47    public FirstFitAllocator(
48            final SsaMethod ssaMeth, final InterferenceGraph interference) {
49        super(ssaMeth, interference);
50
51        mapped = new BitSet(ssaMeth.getRegCount());
52    }
53
54    /** {@inheritDoc} */
55    @Override
56    public boolean wantsParamsMovedHigh() {
57        return PRESLOT_PARAMS;
58    }
59
60    /** {@inheritDoc} */
61    @Override
62    public RegisterMapper allocateRegisters() {
63        int oldRegCount = ssaMeth.getRegCount();
64
65        BasicRegisterMapper mapper
66                = new BasicRegisterMapper(oldRegCount);
67
68        int nextNewRegister = 0;
69
70        if (PRESLOT_PARAMS) {
71            /*
72             * Reserve space for the params at the bottom of the register
73             * space. Later, we'll flip the params to the end of the register
74             * space.
75             */
76
77            nextNewRegister = ssaMeth.getParamWidth();
78        }
79
80        for (int i = 0; i < oldRegCount; i++) {
81            if (mapped.get(i)) {
82                // we already got this one
83                continue;
84            }
85
86            int maxCategory = getCategoryForSsaReg(i);
87            IntSet current = new BitIntSet(oldRegCount);
88
89            interference.mergeInterferenceSet(i, current);
90
91            boolean isPreslotted = false;
92            int newReg = 0;
93
94            if (PRESLOT_PARAMS && isDefinitionMoveParam(i)) {
95                // Any move-param definition must be a NormalSsaInsn
96                NormalSsaInsn defInsn = (NormalSsaInsn)
97                       ssaMeth.getDefinitionForRegister(i);
98
99                newReg = paramNumberFromMoveParam(defInsn);
100
101                mapper.addMapping(i, newReg, maxCategory);
102                isPreslotted = true;
103            } else {
104                mapper.addMapping(i, nextNewRegister, maxCategory);
105                newReg = nextNewRegister;
106            }
107
108            for (int j = i + 1; j < oldRegCount; j++) {
109                if (mapped.get(j) || isDefinitionMoveParam(j)) {
110                    continue;
111                }
112
113                /*
114                 * If reg j doesn't interfere with the current mapping.
115                 * Also, if this is a pre-slotted method parameter, we
116                 * can't use more than the original param width.
117                 */
118                if (!current.has(j)
119                        && !(isPreslotted
120                            && (maxCategory < getCategoryForSsaReg(j)))) {
121
122                    interference.mergeInterferenceSet(j, current);
123
124                    maxCategory = Math.max(maxCategory,
125                            getCategoryForSsaReg(j));
126
127                    mapper.addMapping(j, newReg, maxCategory);
128                    mapped.set(j);
129                }
130            }
131
132            mapped.set(i);
133            if (!isPreslotted) {
134                nextNewRegister += maxCategory;
135            }
136        }
137
138        return mapper;
139    }
140
141    /**
142     * Returns the parameter number that this move-param insn refers to
143     * @param ndefInsn a move-param insn (otherwise, exceptions will be thrown)
144     * @return parameter number (offset in the total parameter width)
145     */
146    private int paramNumberFromMoveParam(NormalSsaInsn ndefInsn) {
147        CstInsn origInsn = (CstInsn) ndefInsn.getOriginalRopInsn();
148
149        return ((CstInteger) origInsn.getConstant()).getValue();
150    }
151}
152