FirstFitLocalCombiningAllocator.java revision 99409883d9c4c0ffb49b070ce307bb33a9dfe9f1
1f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/*
2f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Copyright (C) 2007 The Android Open Source Project
3f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project *
4f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License");
5f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * you may not use this file except in compliance with the License.
6f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * You may obtain a copy of the License at
7f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project *
8f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project *      http://www.apache.org/licenses/LICENSE-2.0
9f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project *
10f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Unless required by applicable law or agreed to in writing, software
11f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS,
12f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * See the License for the specific language governing permissions and
14f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * limitations under the License.
15f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */
16f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
17f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpackage com.android.dx.ssa.back;
18f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
19f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.*;
20f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.cst.CstInteger;
21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.InterferenceRegisterMapper;
22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.RegisterMapper;
23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.SsaInsn;
24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.SsaMethod;
25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.NormalSsaInsn;
26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.PhiInsn;
27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.Optimizer;
28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.SsaBasicBlock;
29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.IntSet;
30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.IntIterator;
31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.ArrayList;
33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.BitSet;
34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.Map;
35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.TreeMap;
36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/**
38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Allocates registers in a first-fit fashion, with the bottom reserved for
39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * method parameters and all SSAregisters representing the same local variable
40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * kept together if possible.
41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */
42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic class FirstFitLocalCombiningAllocator extends RegisterAllocator {
4399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project    /** local debug flag */
44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private static final boolean DEBUG = false;
45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
4699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project    /** maps local variable to a list of associated SSA registers */
47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private final Map<LocalItem, ArrayList<RegisterSpec>> localVariables;
48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /** list of move-result-pesudo instructions seen in this method */
50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private final ArrayList<NormalSsaInsn> moveResultPseudoInsns;
51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /** list of invoke-range instructions seen in this method */
53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private final ArrayList<NormalSsaInsn> invokeRangeInsns;
54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /** indexed by SSA reg; the set of SSA regs we've mapped */
56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private final BitSet ssaRegsMapped;
57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /** Register mapper which will be our result */
59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private final InterferenceRegisterMapper mapper;
60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /** end of rop registers range (starting at 0) reserved for parameters. */
62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private final int paramRangeEnd;
63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /** set of Rop registers reserved for parameters or local variables. */
65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private final BitSet reservedRopRegs;
66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /** set of Rop registers that have been used by anything.*/
68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private final BitSet usedRopRegs;
69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /** true if converter should take steps to minimize rop-form registers*/
71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private final boolean minimizeRegisters;
72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Constructs instance.
75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     *
7699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param ssaMeth {@code non-null;} method to process
77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * @param interference non-null interference graph for SSA registers
78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * @param minimizeRegisters true if converter should take steps to
79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * minimize rop-form registers
80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    public FirstFitLocalCombiningAllocator(
8299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project            SsaMethod ssaMeth, InterferenceGraph interference,
83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            boolean minimizeRegisters) {
84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        super(ssaMeth, interference);
85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        ssaRegsMapped = new BitSet(ssaMeth.getRegCount());
87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        mapper = new InterferenceRegisterMapper(
89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                interference, ssaMeth.getRegCount());
90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        this.minimizeRegisters = minimizeRegisters;
92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        /*
94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project         * Reserve space for the params at the bottom of the register
95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project         * space. Later, we'll flip the params to the end of the register
96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project         * space.
97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project         */
98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        paramRangeEnd = ssaMeth.getParamWidth();
100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        reservedRopRegs = new BitSet(paramRangeEnd * 2);
102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        reservedRopRegs.set(0, paramRangeEnd);
103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        usedRopRegs = new BitSet(paramRangeEnd * 2);
104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        localVariables = new TreeMap<LocalItem, ArrayList<RegisterSpec>>();
105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        moveResultPseudoInsns = new ArrayList<NormalSsaInsn>();
106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        invokeRangeInsns = new ArrayList<NormalSsaInsn>();
107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /** {@inheritDoc} */
110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    @Override
111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    public boolean wantsParamsMovedHigh() {
112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        return true;
113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /** {@inheritDoc} */
116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    @Override
117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    public RegisterMapper allocateRegisters() {
118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        analyzeInstructions();
120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        if (DEBUG) {
122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            printLocalVars();
123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
12599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project        if (DEBUG) System.out.println("--->Mapping local-associated params");
126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        handleLocalAssociatedParams();
127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
12899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project        if (DEBUG) System.out.println("--->Mapping other params");
129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        handleUnassociatedParameters();
130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
13199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project        if (DEBUG) System.out.println("--->Mapping invoke-range");
132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        handleInvokeRangeInsns();
133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
13499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project        if (DEBUG) {
13599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project            System.out.println("--->Mapping local-associated non-params");
13699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project        }
137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        handleLocalAssociatedOther();
138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
13999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project        if (DEBUG) System.out.println("--->Mapping check-cast results");
140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        handleCheckCastResults();
141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
14299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project        if (DEBUG) System.out.println("--->Mapping others");
143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        handleNormalUnassociated();
144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        return mapper;
146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Dumps local variable table to stdout for debugging.
150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private void printLocalVars() {
152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        System.out.println("Printing local vars");
153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        for (Map.Entry<LocalItem, ArrayList<RegisterSpec>> e:
154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                localVariables.entrySet()) {
155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            StringBuilder regs = new StringBuilder();
156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            regs.append('{');
158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            regs.append(' ');
159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            for(RegisterSpec reg: e.getValue()) {
160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                regs.append('v');
161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                regs.append(reg.getReg());
162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                regs.append(' ');
163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            regs.append('}');
165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            System.out.printf("Local: %s Registers: %s\n", e.getKey(), regs);
166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Maps all local-associated parameters to Rop registers.
171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private void handleLocalAssociatedParams() {
17399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project        for (ArrayList<RegisterSpec> ssaRegs : localVariables.values()) {
174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int sz = ssaRegs.size();
175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int paramIndex = -1;
176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int paramCategory = 0;
177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            // First, find out if this local variable is a parameter
17999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project            for (int i = 0; i < sz; i++) {
180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                RegisterSpec ssaSpec = ssaRegs.get(i);
181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                int ssaReg = ssaSpec.getReg();
182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                paramIndex = getParameterIndexForReg(ssaReg);
184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                if (paramIndex >= 0) {
186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    paramCategory = ssaSpec.getCategory();
187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    addMapping(ssaSpec, paramIndex);
188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    break;
189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                }
190f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (paramIndex < 0) {
193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                // this local wasn't a parameter
194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                continue;
195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            // Any remaining local-associated registers will be mapped later
198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            tryMapRegs(ssaRegs, paramIndex, paramCategory, true);
199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
200f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
201f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Gets the parameter index for SSA registers that are method parameters.
204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * -1 is returned for non-parameter registers.
205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     *
20699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param ssaReg {@code >=0;} SSA register to look up
207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * @return parameter index or -1 if not a parameter
208f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private int getParameterIndexForReg(int ssaReg) {
210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        SsaInsn defInsn = ssaMeth.getDefinitionForRegister(ssaReg);
211f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        if (defInsn == null) {
212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            return -1;
213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        Rop opcode = defInsn.getOpcode();
216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
217f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        // opcode == null for phi insns
218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        if (opcode != null && opcode.getOpcode() == RegOps.MOVE_PARAM) {
219f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            CstInsn origInsn = (CstInsn) defInsn.getOriginalRopInsn();
220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            return  ((CstInteger) origInsn.getConstant()).getValue();
221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
222f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        return -1;
224f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
225f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
22799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * Maps all local-associated registers that are not parameters.
22899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * Tries to find an unreserved range that's wide enough for all of
22999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * the SSA registers, and then tries to map them all to that
23099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * range. If not all fit, a new range is tried until all registers
23199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * have been fit.
232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private void handleLocalAssociatedOther() {
23499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project        for (ArrayList<RegisterSpec> specs : localVariables.values()) {
235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int ropReg = 0;
236f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            boolean done;
238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            do {
239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                int maxCategory = 1;
240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
241f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                // compute max category for remaining unmapped registers
242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                int sz = specs.size();
243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                for (int i = 0; i < sz; i++) {
244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    RegisterSpec ssaSpec = specs.get(i);
245f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    int category = ssaSpec.getCategory();
246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    if (!ssaRegsMapped.get(ssaSpec.getReg())
247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                            && category > maxCategory) {
248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                        maxCategory = category;
249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    }
250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                }
251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                ropReg = findRopRegForLocal(ropReg, maxCategory);
253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                done = tryMapRegs(specs, ropReg, maxCategory, true);
255f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                // Increment for next call to findNext
257f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                ropReg++;
258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            } while (!done);
259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
262f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
263f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Tries to map a list of SSA registers into the a rop reg, marking
264f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * used rop space as reserved. SSA registers that don't fit are left
265f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * unmapped.
266f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     *
26799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param specs {@code non-null;} SSA registers to attempt to map
26899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param ropReg {@code >=0;} rop register to map to
269f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * @param maxAllowedCategory 1 or 2, maximum category allowed in mapping.
270f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * @param markReserved do so if true
271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * @return true if all registers wew mapped, false if some remain unmapped.
272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private boolean tryMapRegs(
274f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            ArrayList<RegisterSpec> specs, int ropReg,
275f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int maxAllowedCategory, boolean markReserved) {
276f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        boolean remaining = false;
27799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project        for (RegisterSpec spec : specs) {
278f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (ssaRegsMapped.get(spec.getReg())) {
279f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                continue;
280f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
281f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            boolean succeeded;
283f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            succeeded = tryMapReg(spec, ropReg, maxAllowedCategory);
284f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            remaining = !succeeded || remaining;
285f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (succeeded && markReserved) {
286f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                // This only needs to be called once really with
287f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                // the widest category used, but <shrug>
288f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                markReserved(ropReg, spec.getCategory());
289f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
290f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
291f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        return !remaining;
292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
293f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
294f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
295f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Tries to map an SSA register to a rop register.
296f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     *
29799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param ssaSpec {@code non-null;} SSA register
29899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param ropReg {@code >=0;} rop register
299f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * @param maxAllowedCategory 1 or 2, the maximum category that the SSA
300f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * register is allowed to be.
301f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * @return true if map succeeded, false if not.
302f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
303f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private boolean tryMapReg(RegisterSpec ssaSpec, int ropReg,
304f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int maxAllowedCategory) {
305f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        if (ssaSpec.getCategory() <= maxAllowedCategory
306f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                && !ssaRegsMapped.get(ssaSpec.getReg())
307f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                && canMapReg(ssaSpec, ropReg)) {
308f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            addMapping(ssaSpec, ropReg);
309f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            return true;
310f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
311f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
312f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        return false;
313f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
314f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
315f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
316f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Marks a range of Rop registers as "reserved for a local variable"
317f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     *
31899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param ropReg {@code >= 0;} rop register to reserve
31999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param category {@code > 0;} width to reserve
320f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
321f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private void markReserved(int ropReg, int category) {
322f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        reservedRopRegs.set(ropReg, ropReg + category, true);
323f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
326f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Checks to see if any Rop registers in the specified range are reserved
327f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * for local variables or parameters
328f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     *
32999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param ropRangeStart {@code >= 0;} lowest Rop register
33099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param width {@code > 0;} number of Rop registers in range.
331f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * @return true if any register in range is marked reserved
332f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
333f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private boolean rangeContainsReserved(int ropRangeStart, int width) {
334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        for (int i = ropRangeStart; i < (ropRangeStart + width); i++) {
335f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (reservedRopRegs.get(i)) {
336f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                return true;
337f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
338f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
339f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        return false;
340f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
341f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
342f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
343f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Returns true if given rop register represents the "this" pointer
344f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * for a non-static method
345f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     *
346f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * @param startReg rop register
347f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * @return true if the "this" pointer is located here.
348f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
349f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private boolean isThisPointerReg(int startReg) {
350f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        // "this" is always the first parameter
351f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        return startReg == 0 && !ssaMeth.isStatic();
352f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
353f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
354f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
355f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Finds a range of unreserved Rop registers.
356f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     *
35799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param startReg {@code >= 0;} a Rop register to start the search at
35899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param width {@code > 0;} the width, in registers, required.
35999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @return {@code >= 0;} start of available register range.
360f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
361f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private int findNextUnreservedRopReg(int startReg, int width) {
362f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        if (minimizeRegisters && !isThisPointerReg(startReg)) {
363f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            return startReg;
364f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
365f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
366f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        int reg;
367f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
368f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        reg = reservedRopRegs.nextClearBit(startReg);
369f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
370f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        while (true) {
371f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int i = 1;
372f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
373f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            while (i < width && !reservedRopRegs.get(reg + i)) {
374f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                i++;
375f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
376f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
377f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (i == width) {
378f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                return reg;
379f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
380f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
381f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            reg = reservedRopRegs.nextClearBit(reg + i);
382f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
383f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
384f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
385f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
386f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Finds a range of rop regs that can be used for local variables.
38799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * If {@code MIX_LOCALS_AND_OTHER} is false, this means any
388f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * rop register that has not yet been used.
389f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     *
39099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param startReg {@code >= 0;} a Rop register to start the search at
39199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param width {@code > 0;} the width, in registers, required.
39299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @return {@code >= 0;} start of available register range.
393f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
394f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private int findRopRegForLocal(int startReg, int width) {
395f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        if (minimizeRegisters && !isThisPointerReg(startReg)) {
396f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            return startReg;
397f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
398f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
399f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        int reg;
400f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
401f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        reg = usedRopRegs.nextClearBit(startReg);
402f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
403f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        while (true) {
404f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int i = 1;
405f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
406f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            while (i < width && !usedRopRegs.get(reg + i)) {
407f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                i++;
408f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
409f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
410f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (i == width) {
411f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                return reg;
412f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
413f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
414f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            reg = usedRopRegs.nextClearBit(reg + i);
415f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
416f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
417f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
418f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
419f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Maps any parameter that isn't local-associated, which can happen
420f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * in the case where there is no java debug info.
421f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
422f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private void handleUnassociatedParameters() {
423f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        int szSsaRegs = ssaMeth.getRegCount();
42499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project
425f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        for (int ssaReg = 0; ssaReg < szSsaRegs; ssaReg++) {
426f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (ssaRegsMapped.get(ssaReg)) {
427f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                // We already did this one above
428f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                continue;
429f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
430f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
431f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int paramIndex = getParameterIndexForReg(ssaReg);
432f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
433f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            RegisterSpec ssaSpec = getDefinitionSpecForSsaReg(ssaReg);
434f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (paramIndex >= 0) {
435f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                addMapping(ssaSpec, paramIndex);
436f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
437f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
438f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
439f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
440f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
441f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Handles all insns that want a register range for their sources.
442f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
443f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private void handleInvokeRangeInsns() {
44499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project        for(NormalSsaInsn insn : invokeRangeInsns) {
445f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            adjustAndMapSourceRangeRange(insn);
446f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
447f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
448f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
449f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
450f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Handles check cast results to reuse the same source register if possible
451f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
452f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private void handleCheckCastResults() {
453f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        for (NormalSsaInsn insn : moveResultPseudoInsns) {
454f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            RegisterSpec moveRegSpec = insn.getResult();
455f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int moveReg = moveRegSpec.getReg();
456f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            BitSet predBlocks = insn.getBlock().getPredecessors();
457f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
458f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            // Expect one predecessor block only
459f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (predBlocks.cardinality() != 1) {
460f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                continue;
461f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
462f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
463f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            SsaBasicBlock predBlock =
464f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    ssaMeth.getBlocks().get(predBlocks.nextSetBit(0));
465f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            ArrayList<SsaInsn> insnList = predBlock.getInsns();
466f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
467f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            /**
468f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project             * If the predecessor block has a check-cast, it will be the last
469f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project             * instruction
470f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project             */
471f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            SsaInsn checkCastInsn = insnList.get(insnList.size() - 1);
472f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (checkCastInsn.getOpcode().getOpcode() != RegOps.CHECK_CAST) {
473f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                continue;
474f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
475f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
476f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            RegisterSpec checkRegSpec = checkCastInsn.getSources().get(0);
477f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int checkReg = checkRegSpec.getReg();
478f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
479f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            // Assume none of the register is mapped yet
480f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int ropReg = 0;
481f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
482f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            /**
483f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project             * See if either register is already mapped. Most likely the move
484f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project             * result will be mapped already since the cast result is stored
485f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project             * in a local variable.
486f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project             */
487f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (ssaRegsMapped.get(moveReg)) {
488f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                ropReg = mapper.oldToNew(moveReg);
489f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            } else if (ssaRegsMapped.get(checkReg)) {
490f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                ropReg = mapper.oldToNew(checkReg);
491f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
492f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
493f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            ArrayList<RegisterSpec> ssaRegs = new ArrayList<RegisterSpec>(2);
494f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            ssaRegs.add(moveRegSpec);
495f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            ssaRegs.add(checkRegSpec);
496f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int category = checkRegSpec.getCategory();
497f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
498f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            while (!tryMapRegs(ssaRegs, ropReg, category, false)) {
499f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                ropReg = findNextUnreservedRopReg(ropReg + 1, category);
500f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
501f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
502f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
503f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
504f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
505f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Maps all non-parameter, non-local variable
506f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * registers.
507f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
508f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private void handleNormalUnassociated() {
509f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        int szSsaRegs = ssaMeth.getRegCount();
51099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project
511f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        for (int ssaReg = 0; ssaReg < szSsaRegs; ssaReg++) {
512f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (ssaRegsMapped.get(ssaReg)) {
513f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                // We already did this one
514f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                continue;
515f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
516f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
517f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            RegisterSpec ssaSpec = getDefinitionSpecForSsaReg(ssaReg);
518f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
519f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (ssaSpec == null) continue;
520f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
521f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int category = ssaSpec.getCategory();
522f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            // Find a rop reg that does not interfere
523f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int ropReg = findNextUnreservedRopReg(0, category);
524f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            while (!canMapReg(ssaSpec, ropReg)) {
525f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                ropReg = findNextUnreservedRopReg(ropReg + 1, category);
526f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
527f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
528f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            addMapping(ssaSpec, ropReg);
529f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
530f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
531f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
532f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
53399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * Checks to see if {@code ssaSpec} can be mapped to
53499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * {@code ropReg}. Checks interference graph and ensures
535f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * the range does not cross the parameter range.
536f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     *
53799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param ssaSpec {@code non-null;} SSA spec
538f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * @param ropReg prosepctive new-namespace reg
539f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * @return true if mapping is possible
540f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
541f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private boolean canMapReg(RegisterSpec ssaSpec, int ropReg) {
542f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        int category = ssaSpec.getCategory();
543f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        return !(spansParamRange(ropReg, category)
544f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                || mapper.interferes(ssaSpec, ropReg));
545f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
546f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
547f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
548f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Returns true if the specified Rop register + category
54999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * will cross the boundry between the lower {@code paramWidth}
550f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * registers reserved for method params and the upper registers. We cannot
551f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * allocate a register that spans the param block and the normal block,
552f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * because we will be moving the param block to high registers later.
553f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     *
554f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * @param ssaReg register in new namespace
555f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * @param category width that the register will have
556f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * @return true in the case noted above.
557f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
558f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private boolean spansParamRange(int ssaReg, int category) {
559f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        return ((ssaReg < paramRangeEnd)
560f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                && ((ssaReg + category) > paramRangeEnd));
561f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
562f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
563f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
564f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Analyze each instruction and find out all the local variable assignments
565f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * and move-result-pseudo/invoke-range instrucitons.
566f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
567f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private void analyzeInstructions() {
568f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        ssaMeth.forEachInsn(new SsaInsn.Visitor() {
569f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            /** {@inheritDoc} */
570f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            public void visitMoveInsn(NormalSsaInsn insn) {
571f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                processInsn(insn);
572f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
573f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
574f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            /** {@inheritDoc} */
575f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            public void visitPhiInsn(PhiInsn insn) {
576f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                processInsn(insn);
577f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
578f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
579f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            /** {@inheritDoc} */
580f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            public void visitNonMoveInsn(NormalSsaInsn insn) {
581f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                processInsn(insn);
582f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
583f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
584f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            /**
585f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project             * This method collects three types of instructions:
586f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project             * 1) Adds a local variable assignment to the
58799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project             *    {@code localVariables} map.
588f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project             * 2) Add move-result-pseudo to the
58999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project             *    {@code moveResultPseudoInsns} list.
590f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project             * 3) Add invoke-range to the
59199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project             *    {@code invokeRangeInsns} list.
592f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project             *
59399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project             * @param insn {@code non-null;} insn that may represent a
59499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project             * local variable assignment
595f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project             */
596f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            private void processInsn(SsaInsn insn) {
597f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                RegisterSpec assignment;
598f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                assignment = insn.getLocalAssignment();
599f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
600f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                if (assignment != null) {
601f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    LocalItem local = assignment.getLocalItem();
602f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
60399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project                    ArrayList<RegisterSpec> regList
60499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project                        = localVariables.get(local);
605f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
606f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    if (regList == null) {
607f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                        regList = new ArrayList<RegisterSpec>();
608f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                        localVariables.put(local, regList);
609f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    }
610f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
611f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    regList.add(assignment);
612f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                }
613f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
614f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                if (insn instanceof NormalSsaInsn) {
615f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    if (insn.getOpcode().getOpcode() ==
616f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                            RegOps.MOVE_RESULT_PSEUDO) {
617f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                        moveResultPseudoInsns.add((NormalSsaInsn) insn);
618f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    } else if (Optimizer.getAdvice().requiresSourcesInOrder(
619f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                            insn.getOriginalRopInsn().getOpcode(),
620f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                            insn.getSources())) {
621f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                        invokeRangeInsns.add((NormalSsaInsn) insn);
622f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    }
623f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                }
624f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
625f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
626f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        });
627f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
628f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
629f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
63099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * Adds a mapping from an SSA register to a Rop register.
63199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * {@link #canMapReg} should have already been called.
632f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     *
63399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param ssaSpec {@code non-null;} SSA register to map from
63499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param ropReg {@code >=0;} Rop register to map to
635f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
636f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private void addMapping(RegisterSpec ssaSpec, int ropReg) {
637f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        int ssaReg = ssaSpec.getReg();
638f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
639f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        // An assertion
640f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        if (ssaRegsMapped.get(ssaReg) || !canMapReg(ssaSpec, ropReg)) {
641f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            throw new RuntimeException(
642f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    "attempt to add invalid register mapping");
643f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
644f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
645f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        if (DEBUG) {
646f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            System.out.printf("Add mapping s%d -> v%d c:%d\n",
64799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project                    ssaSpec.getReg(), ropReg, ssaSpec.getCategory());
648f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
649f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
650f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        int category = ssaSpec.getCategory();
651f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        mapper.addMapping(ssaSpec.getReg(), ropReg, category);
652f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        ssaRegsMapped.set(ssaReg);
653f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        usedRopRegs.set(ropReg, ropReg + category);
654f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
655f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
656f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
657f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
658f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Maps the source registers of the specified instruction such that they
659f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * will fall in a contiguous range in Rop form. Moves are inserted as
660f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * necessary to allow the range to be allocated.
661f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     *
66299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param insn {@code non-null;} insn whos sources to process
663f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
664f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private void adjustAndMapSourceRangeRange(NormalSsaInsn insn) {
66599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project        int newRegStart = findRangeAndAdjust(insn);
666f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
667f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        RegisterSpecList sources = insn.getSources();
668f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        int szSources = sources.size();
669f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        int nextRopReg = newRegStart;
67099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project
671f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        for (int i = 0; i < szSources; i++) {
672f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            RegisterSpec source = sources.get(i);
673f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int sourceReg = source.getReg();
674f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int category = source.getCategory();
675f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int curRopReg = nextRopReg;
676f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            nextRopReg += category;
677f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
678f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (ssaRegsMapped.get(sourceReg)) {
679f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                continue;
680f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
681f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
682f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            LocalItem localItem = getLocalItemForReg(sourceReg);
683f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            addMapping(source, curRopReg);
684f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
685f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (localItem != null) {
686f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                markReserved(curRopReg, category);
687f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                ArrayList<RegisterSpec> similarRegisters
688f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                        = localVariables.get(localItem);
689f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
690f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                int szSimilar = similarRegisters.size();
691f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
692f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                // Try to map all SSA registers also associated with this local
693f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                for (int j = 0; j < szSimilar; j++) {
694f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    RegisterSpec similarSpec = similarRegisters.get(j);
695f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    int similarReg = similarSpec.getReg();
696f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
697f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    // ...and don't map anything that's also a source...
698f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    if (-1 != sources.indexOfRegister(similarReg)) {
699f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                        continue;
700f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    }
701f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
702f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    // Registers left unmapped will get handled later
703f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    tryMapReg(similarSpec, curRopReg, category);
704f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                }
705f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
706f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
707f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
708f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
709f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
710f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Find a contiguous rop register range that fits the specified
711f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * instruction's sources. First, try to center the range around
712f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * sources that have already been mapped to Rop registers. If that fails,
713f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * just find a new contiguous range that doesn't interfere.
71499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     *
71599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param insn {@code non-null;} the insn whose sources need to
71699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * fit. Must be last insn in basic block.
71799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @return {@code >= 0;} rop register of start of range
718f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
719f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private int findRangeAndAdjust(NormalSsaInsn insn) {
720f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        RegisterSpecList sources = insn.getSources();
721f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        int szSources = sources.size();
722f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        // the category for each source index
723f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        int categoriesForIndex[] = new int[szSources];
724f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        int rangeLength = 0;
725f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
726f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        // Compute rangeLength and categoriesForIndex
727f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        for (int i = 0; i < szSources; i++) {
728f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int category = sources.get(i).getCategory();
729f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            categoriesForIndex[i] = category;
730f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            rangeLength += categoriesForIndex[i];
731f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
732f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
733f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        // The highest score of fits tried so far
734f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        int maxScore = Integer.MIN_VALUE;
735f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        // the high scoring range's start
736f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        int resultRangeStart = -1;
737f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        // by source index: set of sources needing moves in high scoring plan
738f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        BitSet resultMovesRequired = null;
739f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
740f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        /*
741f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project         * First, go through each source that's already been mapped. Try
742f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project         * to center the range around the Rop register this source is mapped
743f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project         * to.
744f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project         */
745f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        int rangeStartOffset = 0;
746f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        for (int i = 0; i < szSources; i++) {
747f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int ssaCenterReg = sources.get(i).getReg();
748f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
749f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (i != 0) {
750f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                rangeStartOffset -= categoriesForIndex[i - 1];
751f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
752f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (!ssaRegsMapped.get(ssaCenterReg)) {
753f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                continue;
754f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
755f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
756f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int rangeStart = mapper.oldToNew(ssaCenterReg) + rangeStartOffset;
757f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
758f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (rangeStart < 0 || spansParamRange(rangeStart, rangeLength)) {
759f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                continue;
760f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
761f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
762f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            BitSet curMovesRequired = new BitSet(szSources);
763f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
764f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int fitWidth
765f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    = fitPlanForRange(rangeStart, insn, categoriesForIndex,
766f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    curMovesRequired);
767f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
768f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (fitWidth < 0) {
769f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                continue;
770f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
771f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
772f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int score = fitWidth - curMovesRequired.cardinality();
773f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
774f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (score > maxScore) {
775f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                maxScore = score;
776f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                resultRangeStart = rangeStart;
777f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                resultMovesRequired = curMovesRequired;
778f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
779f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
780f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (fitWidth == rangeLength) {
781f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                // We can't do any better than this, so stop here
782f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                break;
783f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
784f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
785f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
786f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        /*
787f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project         * If we were unable to find a plan for a fit centered around
788f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project         * an already-mapped source, just try to find a range of
789f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project         * registers we can move the range into.
790f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project         */
791f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
792f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        if (resultRangeStart == -1) {
793f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            resultMovesRequired = new BitSet(szSources);
794f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
795f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            resultRangeStart = findAnyFittingRange(insn, rangeLength,
796f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    categoriesForIndex, resultMovesRequired);
797f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
798f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
799f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        /*
800f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project         * Now, insert any moves required
801f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project         */
802f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
803f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        for (int i = resultMovesRequired.nextSetBit(0); i >= 0
804f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                ; i = resultMovesRequired.nextSetBit(i+1)) {
805f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            insn.changeOneSource(i,
806f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    insertMoveBefore(insn, sources.get(i)));
807f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
808f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
809f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        return resultRangeStart;
810f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
811f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
812f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
813f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Finds an unreserved range that will fit the sources of the
814f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * specified instruction. Does not bother trying to center the range
815f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * around an already-mapped source register;
816f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     *
81799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param insn {@code non-null;} insn to build range for
81899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param rangeLength {@code >=0;} length required in register units.
81999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param categoriesForIndex {@code non-null;} indexed by source index;
820f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * the category for each source.
82199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param outMovesRequired {@code non-null;} an output parameter indexed by
822f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * source index that will contain the set of sources which need
823f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * moves inserted.
824f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * @return the rop register that starts the fitting range.
825f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
826f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private int findAnyFittingRange(NormalSsaInsn insn, int rangeLength,
827f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int[] categoriesForIndex, BitSet outMovesRequired) {
828f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        int rangeStart = 0;
829f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        while (true) {
830f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            rangeStart = findNextUnreservedRopReg(rangeStart, rangeLength);
831f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int fitWidth
832f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    = fitPlanForRange(rangeStart, insn,
833f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    categoriesForIndex, outMovesRequired);
834f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
835f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (fitWidth >= 0) {
836f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                break;
837f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
838f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            rangeStart++;
839f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            outMovesRequired.clear();
840f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
841f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        return rangeStart;
842f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
843f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
844f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
845f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Attempts to build a plan for fitting a range of sources into rop
846f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * registers.
847f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     *
84899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param ropReg {@code >= 0;} rop reg that begins range
84999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param insn {@code non-null;} insn to plan range for
85099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param categoriesForIndex {@code non-null;} indexed by source index;
851f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * the category for each source.
85299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param outMovesRequired {@code non-null;} an output parameter indexed by
853f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * source index that will contain the set of sources which need
854f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * moves inserted.
855f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * @return the width of the fit that that does not involve added moves or
856f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * -1 if "no fit possible"
857f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
858f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private int fitPlanForRange(int ropReg, NormalSsaInsn insn,
859f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int[] categoriesForIndex, BitSet outMovesRequired) {
860f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        RegisterSpecList sources = insn.getSources();
861f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        int szSources = sources.size();
862f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        int fitWidth = 0;
863f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        IntSet liveOut = insn.getBlock().getLiveOutRegs();
864f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        RegisterSpecList liveOutSpecs = ssaSetToSpecs(liveOut);
865f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
866f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        // An SSA reg may only be mapped into a range once
867f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        BitSet seen = new BitSet(ssaMeth.getRegCount());
868f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
869f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        for (int i = 0; i < szSources ; i++) {
870f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            RegisterSpec ssaSpec = sources.get(i);
871f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int ssaReg = ssaSpec.getReg();
872f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            int category = categoriesForIndex[i];
873f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
874f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (i != 0) {
875f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                ropReg += categoriesForIndex[i-1];
876f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
877f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
878f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            if (ssaRegsMapped.get(ssaReg)
879f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    && mapper.oldToNew(ssaReg) == ropReg) {
880f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                // A register already mapped appropriately
881f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                fitWidth += category;
882f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            } else if (rangeContainsReserved(ropReg, category)) {
883f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                fitWidth = -1;
884f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                break;
885f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            } else if (!ssaRegsMapped.get(ssaReg)
886f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    && canMapReg(ssaSpec, ropReg)
887f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    && !seen.get(ssaReg)) {
888f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                // A register that can be mapped appropriately
889f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                fitWidth += category;
890f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            } else if (!mapper.areAnyPinned(liveOutSpecs, ropReg, category)
891f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    && !mapper.areAnyPinned(sources, ropReg, category)) {
892f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                /*
893f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                 * A source that can be moved
894f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                 * We can insert a move as long as:
895f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                 *
896f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                 *  - no SSA register pinned to the desired rop reg
897f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                 * is live out on the block
898f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                 *  - no SSA register pinned to desired rop reg is
899f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                 *  a source of this insn (since this may require
900f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                 * overlapping moves, which we can't presently handle)
901f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                 */
902f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
903f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                outMovesRequired.set(i);
904f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            } else {
905f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                fitWidth = -1;
906f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                break;
907f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
908f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
909f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            seen.set(ssaReg);
910f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
911f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        return fitWidth;
912f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
913f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
914f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
915f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Converts a bit set of SSA registers into a RegisterSpecList containing
916f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * the definition specs of all the registers.
917f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     *
91899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param ssaSet {@code non-null;} set of SSA registers
919f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * @return list of RegisterSpecs as noted above
920f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
921f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    RegisterSpecList ssaSetToSpecs(IntSet ssaSet) {
922f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        RegisterSpecList result = new RegisterSpecList(ssaSet.elements());
923f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
924f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        IntIterator iter = ssaSet.iterator();
925f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
926f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        int i = 0;
927f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        while (iter.hasNext()) {
928f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            result.set(i++, getDefinitionSpecForSsaReg(iter.next()));
929f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
930f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
931f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        return result;
932f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
933f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
934f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    /**
935f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     * Gets a local item associated with an ssa register, if one exists
936f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     *
93799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @param ssaReg {@code >= 0;} SSA register
93899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project     * @return {@code null-ok;} associated local item or null
939f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project     */
940f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    private LocalItem getLocalItemForReg(int ssaReg) {
941f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        for(Map.Entry<LocalItem, ArrayList<RegisterSpec>> entry:
942f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                localVariables.entrySet()) {
943f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
94499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project            for (RegisterSpec spec : entry.getValue()) {
945f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                if (spec.getReg() == ssaReg) {
946f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                    return entry.getKey();
947f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project                }
948f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project            }
949f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        }
950f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project
951f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project        return null;
952f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project    }
953f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project}
954