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