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