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.SetFactory;
20import com.android.dx.util.IntSet;
21import java.util.ArrayList;
22
23/**
24 * A register interference graph
25 */
26public class InterferenceGraph {
27    /**
28     * {@code non-null;} interference graph, indexed by register in
29     * both dimensions
30     */
31    private final ArrayList<IntSet> interference;
32
33    /**
34     * Creates a new graph.
35     *
36     * @param countRegs {@code >= 0;} the start count of registers in
37     * the namespace. New registers can be added subsequently.
38     */
39    public InterferenceGraph(int countRegs) {
40        interference = new ArrayList<IntSet>(countRegs);
41
42        for (int i = 0; i < countRegs; i++) {
43            interference.add(SetFactory.makeInterferenceSet(countRegs));
44        }
45    }
46
47    /**
48     * Adds a register pair to the interference/liveness graph. Parameter
49     * order is insignificant.
50     *
51     * @param regV one register index
52     * @param regW another register index
53     */
54    public void add(int regV, int regW) {
55        ensureCapacity(Math.max(regV, regW) + 1);
56
57        interference.get(regV).add(regW);
58        interference.get(regW).add(regV);
59    }
60
61    /**
62     * Dumps interference graph to stdout for debugging.
63     */
64    public void dumpToStdout() {
65        int oldRegCount = interference.size();
66
67        for (int i = 0; i < oldRegCount; i++) {
68            StringBuilder sb = new StringBuilder();
69
70            sb.append("Reg " + i + ":" + interference.get(i).toString());
71
72            System.out.println(sb.toString());
73        }
74    }
75
76    /**
77     * Merges the interference set for a register into a given bit set
78     *
79     * @param reg {@code >= 0;} register
80     * @param set {@code non-null;} interference set; will be merged
81     * with set for given register
82     */
83    public void mergeInterferenceSet(int reg, IntSet set) {
84        if (reg < interference.size()) {
85            set.merge(interference.get(reg));
86        }
87    }
88
89    /**
90     * Ensures that the interference graph is appropriately sized.
91     *
92     * @param size requested minumum size
93     */
94    private void ensureCapacity(int size) {
95        int countRegs = interference.size();
96
97        interference.ensureCapacity(size);
98
99        for (int i = countRegs; i < size; i++) {
100            interference.add(SetFactory.makeInterferenceSet(size));
101        }
102    }
103}
104