InterferenceGraph.java revision 579d7739c53a2707ad711a2d2cae46d7d782f061 
1/*
2 * Copyright (C) 2007 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.android.dx.ssa.back;
18
19import com.android.dx.ssa.SsaMethod;
20import com.android.dx.ssa.SsaBasicBlock;
21import com.android.dx.ssa.SsaInsn;
22import com.android.dx.ssa.PhiInsn;
23import com.android.dx.ssa.SetFactory;
24import com.android.dx.rop.code.RegisterSpec;
25import com.android.dx.util.IntSet;
26import com.android.dx.util.BitIntSet;
27import com.android.dx.util.ListIntSet;
28
29import java.util.BitSet;
30import java.util.List;
31import java.util.ArrayList;
32
33/**
34 * A register interference graph
35 */
36public class InterferenceGraph {
37    /**
38     * {@code non-null;} interference graph, indexed by register in
39     * both dimensions
40     */
41    private final ArrayList<IntSet> interference;
42
43    /**
44     * Creates a new graph.
45     *
46     * @param countRegs {@code >= 0;} the start count of registers in
47     * the namespace. New registers can be added subsequently.
48     */
49    public InterferenceGraph(int countRegs) {
50        interference = new ArrayList<IntSet>(countRegs);
51
52        for (int i = 0; i < countRegs; i++) {
53            interference.add(SetFactory.makeInterferenceSet(countRegs));
54        }
55    }
56
57    /**
58     * Adds a register pair to the interference/liveness graph. Parameter
59     * order is insignificant.
60     *
61     * @param regV one register index
62     * @param regW another register index
63     */
64    public void add(int regV, int regW) {
65        ensureCapacity(Math.max(regV, regW) + 1);
66
67        interference.get(regV).add(regW);
68        interference.get(regW).add(regV);
69    }
70
71    /**
72     * Dumps interference graph to stdout for debugging.
73     */
74    public void dumpToStdout() {
75        int oldRegCount = interference.size();
76
77        for (int i = 0; i < oldRegCount; i++) {
78            StringBuilder sb = new StringBuilder();
79
80            sb.append("Reg " + i + ":" + interference.get(i).toString());
81
82            System.out.println(sb.toString());
83        }
84    }
85
86    /**
87     * Merges the interference set for a register into a given bit set
88     *
89     * @param reg {@code >= 0;} register
90     * @param set {@code non-null;} interference set; will be merged
91     * with set for given register
92     */
93    public void mergeInterferenceSet(int reg, IntSet set) {
94        if (reg < interference.size()) {
95            set.merge(interference.get(reg));
96        }
97    }
98
99    /**
100     * Ensures that the interference graph is appropriately sized.
101     *
102     * @param size requested minumum size
103     */
104    private void ensureCapacity(int size) {
105        int countRegs = interference.size();
106
107        interference.ensureCapacity(size);
108
109        for (int i = countRegs; i < size; i++) {
110            interference.add(SetFactory.makeInterferenceSet(size));
111        }
112    }
113}
114