1/*
2 * Copyright (C) 2007 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.android.dx.ssa;
18
19import com.android.dx.rop.code.RegisterSpec;
20import com.android.dx.rop.code.RegisterSpecList;
21import com.android.dx.ssa.back.InterferenceGraph;
22import com.android.dx.util.BitIntSet;
23import com.android.dx.util.IntSet;
24import java.util.ArrayList;
25
26/**
27 * A register mapper that keeps track of the accumulated interference
28 * information for the registers in the new namespace.
29 *
30 * Please note that this mapper requires that the old namespace does not
31 * have variable register widths/categories, and the new namespace does.
32 */
33public class InterferenceRegisterMapper extends BasicRegisterMapper {
34    /**
35     * Array of interference sets. ArrayList is indexed by new namespace
36     * and BitIntSet's are indexed by old namespace.  The list expands
37     * as needed and missing items are assumed to interfere with nothing.
38     *
39     * Bit sets are always used here, unlike elsewhere, because the max
40     * size of this matrix will be (countSsaRegs * countRopRegs), which may
41     * grow to hundreds of K but not megabytes.
42     */
43    private final ArrayList<BitIntSet> newRegInterference;
44
45    /** the interference graph for the old namespace */
46    private final InterferenceGraph oldRegInterference;
47
48    /**
49     * Constructs an instance
50     *
51     * @param countOldRegisters number of registers in old namespace
52     */
53    public InterferenceRegisterMapper(InterferenceGraph oldRegInterference,
54            int countOldRegisters) {
55        super(countOldRegisters);
56
57        newRegInterference = new ArrayList<BitIntSet>();
58        this.oldRegInterference = oldRegInterference;
59    }
60
61    /** {@inheritDoc} */
62    @Override
63    public void addMapping(int oldReg, int newReg, int category) {
64        super.addMapping(oldReg, newReg, category);
65
66        addInterfence(newReg, oldReg);
67
68        if (category == 2) {
69            addInterfence(newReg + 1, oldReg);
70        }
71    }
72
73    /**
74     * Checks to see if old namespace reg {@code oldReg} interferes
75     * with what currently maps to {@code newReg}.
76     *
77     * @param oldReg old namespace register
78     * @param newReg new namespace register
79     * @param category category of old namespace register
80     * @return true if oldReg will interfere with newReg
81     */
82    public boolean interferes(int oldReg, int newReg, int category) {
83        if (newReg >= newRegInterference.size()) {
84            return false;
85        } else {
86            IntSet existing = newRegInterference.get(newReg);
87
88            if (existing == null) {
89                return false;
90            } else if (category == 1) {
91                return existing.has(oldReg);
92            } else {
93                return existing.has(oldReg)
94                        || (interferes(oldReg, newReg+1, category-1));
95            }
96        }
97    }
98
99    /**
100     * Checks to see if old namespace reg {@code oldReg} interferes
101     * with what currently maps to {@code newReg}.
102     *
103     * @param oldSpec {@code non-null;} old namespace register
104     * @param newReg new namespace register
105     * @return true if oldReg will interfere with newReg
106     */
107    public boolean interferes(RegisterSpec oldSpec, int newReg) {
108        return interferes(oldSpec.getReg(), newReg, oldSpec.getCategory());
109    }
110
111    /**
112     * Adds a register's interference set to the interference list,
113     * growing it if necessary.
114     *
115     * @param newReg register in new namespace
116     * @param oldReg register in old namespace
117     */
118    private void addInterfence(int newReg, int oldReg) {
119        newRegInterference.ensureCapacity(newReg + 1);
120
121        while (newReg >= newRegInterference.size()) {
122            newRegInterference.add(new BitIntSet(newReg +1));
123        }
124
125        oldRegInterference.mergeInterferenceSet(
126                oldReg, newRegInterference.get(newReg));
127    }
128
129    /**
130     * Checks to see if any of a set of old-namespace registers are
131     * pinned to the specified new-namespace reg + category. Takes into
132     * account the category of the old-namespace registers.
133     *
134     * @param oldSpecs {@code non-null;} set of old-namespace regs
135     * @param newReg {@code >= 0;} new-namespace register
136     * @param targetCategory {@code 1..2;} the number of adjacent new-namespace
137     * registers (starting at ropReg) to consider
138     * @return true if any of the old-namespace register have been mapped
139     * to the new-namespace register + category
140     */
141    public boolean areAnyPinned(RegisterSpecList oldSpecs,
142            int newReg, int targetCategory) {
143        int sz = oldSpecs.size();
144
145        for (int i = 0; i < sz; i++) {
146            RegisterSpec oldSpec = oldSpecs.get(i);
147            int r = oldToNew(oldSpec.getReg());
148
149            /*
150             * If oldSpec is a category-2 register, then check both newReg
151             * and newReg - 1.
152             */
153            if (r == newReg
154                || (oldSpec.getCategory() == 2 && (r + 1) == newReg)
155                || (targetCategory == 2 && (r == newReg + 1))) {
156                return true;
157            }
158        }
159
160        return false;
161    }
162}
163