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 
17 package com.android.dx.ssa.back;
18 
19 import com.android.dx.ssa.SetFactory;
20 import com.android.dx.util.IntSet;
21 import java.util.ArrayList;
22 
23 /**
24  * A register interference graph
25  */
26 public 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      */
InterferenceGraph(int countRegs)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      */
add(int regV, int regW)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      */
dumpToStdout()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      */
mergeInterferenceSet(int reg, IntSet set)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      */
ensureCapacity(int size)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