RegisterAllocator.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.RegOps;
20import com.android.dx.rop.code.RegisterSpec;
21import com.android.dx.rop.code.PlainInsn;
22import com.android.dx.rop.code.Rops;
23import com.android.dx.rop.code.SourcePosition;
24import com.android.dx.rop.code.RegisterSpecList;
25import com.android.dx.ssa.NormalSsaInsn;
26import com.android.dx.ssa.RegisterMapper;
27import com.android.dx.ssa.SsaInsn;
28import com.android.dx.ssa.SsaMethod;
29import com.android.dx.ssa.SsaBasicBlock;
30import com.android.dx.util.IntSet;
31import com.android.dx.util.IntIterator;
32
33import java.util.BitSet;
34import java.util.ArrayList;
35
36/**
37 * Base class of all register allocators.
38 */
39public abstract class RegisterAllocator {
40    /** method being processed */
41    protected final SsaMethod ssaMeth;
42
43    /** interference graph, indexed by register in both dimensions */
44    protected final InterferenceGraph interference;
45
46    /**
47     * Creates an instance. Call {@code allocateRegisters} to run.
48     * @param ssaMeth method to process.
49     * @param interference Interference graph, indexed by register in both
50     * dimensions.
51     */
52    public RegisterAllocator(SsaMethod ssaMeth,
53            InterferenceGraph interference) {
54        this.ssaMeth = ssaMeth;
55        this.interference = interference;
56    }
57
58    /**
59     * Indicates whether the method params were allocated at the bottom
60     * of the namespace, and thus should be moved up to the top of the
61     * namespace after phi removal.
62     *
63     * @return {@code true} if params should be moved from low to high
64     */
65    public abstract boolean wantsParamsMovedHigh();
66
67    /**
68     * Runs the algorithm.
69     *
70     * @return a register mapper to apply to the {@code SsaMethod}
71     */
72    public abstract RegisterMapper allocateRegisters();
73
74    /**
75     * Returns the category (width) of the definition site of the register.
76     * Returns {@code 1} for undefined registers.
77     *
78     * @param reg register
79     * @return {@code 1..2}
80     */
81    protected final int getCategoryForSsaReg(int reg) {
82        SsaInsn definition = ssaMeth.getDefinitionForRegister(reg);
83
84        if (definition == null) {
85            // an undefined reg
86            return 1;
87        } else {
88            return definition.getResult().getCategory();
89        }
90    }
91
92    /**
93     * Returns the RegisterSpec of the definition of the register.
94     *
95     * @param reg {@code >= 0;} SSA register
96     * @return definition spec of the register or null if it is never defined
97     * (for the case of "version 0" SSA registers)
98     */
99    protected final RegisterSpec getDefinitionSpecForSsaReg(int reg) {
100        SsaInsn definition = ssaMeth.getDefinitionForRegister(reg);
101
102        return definition == null ? null : definition.getResult();
103    }
104
105    /**
106     * Returns true if the definition site of this register is a
107     * move-param (ie, this is a method parameter).
108     *
109     * @param reg register in question
110     * @return {@code true} if this is a method parameter
111     */
112    protected boolean isDefinitionMoveParam(int reg) {
113        SsaInsn defInsn = ssaMeth.getDefinitionForRegister(reg);
114
115        if (defInsn instanceof NormalSsaInsn) {
116            NormalSsaInsn ndefInsn = (NormalSsaInsn) defInsn;
117
118            return ndefInsn.getOpcode().getOpcode() == RegOps.MOVE_PARAM;
119        }
120
121        return false;
122    }
123
124    /**
125     * Inserts a move instruction for a specified SSA register before a
126     * specified instruction, creating a new SSA register and adjusting the
127     * interference graph in the process. The insn currently must be the
128     * last insn in a block.
129     *
130     * @param insn {@code non-null;} insn to insert move before, must
131     * be last insn in block
132     * @param reg {@code non-null;} SSA register to duplicate
133     * @return {@code non-null;} spec of new SSA register created by move
134     */
135    protected final RegisterSpec insertMoveBefore(SsaInsn insn,
136            RegisterSpec reg) {
137        SsaBasicBlock block = insn.getBlock();
138        ArrayList<SsaInsn> insns = block.getInsns();
139        int insnIndex = insns.indexOf(insn);
140
141        if (insnIndex < 0) {
142            throw new IllegalArgumentException (
143                    "specified insn is not in this block");
144        }
145
146        if (insnIndex != insns.size() - 1) {
147            /*
148             * Presently, the interference updater only works when
149             * adding before the last insn, and the last insn must have no
150             * result
151             */
152            throw new IllegalArgumentException(
153                    "Adding move here not supported:" + insn.toHuman());
154        }
155
156        /*
157         * Get new register and make new move instruction.
158         */
159
160        // The new result must not have an associated local variable.
161        RegisterSpec newRegSpec = RegisterSpec.make(ssaMeth.makeNewSsaReg(),
162                reg.getTypeBearer());
163
164        SsaInsn toAdd = SsaInsn.makeFromRop(
165                new PlainInsn(Rops.opMove(newRegSpec.getType()),
166                        SourcePosition.NO_INFO, newRegSpec,
167                        RegisterSpecList.make(reg)), block);
168
169        insns.add(insnIndex, toAdd);
170
171        int newReg = newRegSpec.getReg();
172
173        /*
174         * Adjust interference graph based on what's live out of the current
175         * block and what's used by the final instruction.
176         */
177
178        IntSet liveOut = block.getLiveOutRegs();
179        IntIterator liveOutIter = liveOut.iterator();
180
181        while (liveOutIter.hasNext()) {
182            interference.add(newReg, liveOutIter.next());
183        }
184
185        // Everything that's a source in the last insn interferes.
186        RegisterSpecList sources = insn.getSources();
187        int szSources = sources.size();
188
189        for (int i = 0; i < szSources; i++) {
190            interference.add(newReg, sources.get(i).getReg());
191        }
192
193        ssaMeth.onInsnsChanged();
194
195        return newRegSpec;
196    }
197}
198