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.SsaMethod; 20 import com.android.dx.ssa.SsaBasicBlock; 21 import com.android.dx.ssa.SsaInsn; 22 import com.android.dx.ssa.PhiInsn; 23 import com.android.dx.ssa.SetFactory; 24 import com.android.dx.rop.code.RegisterSpec; 25 import com.android.dx.util.IntSet; 26 import com.android.dx.util.BitIntSet; 27 import com.android.dx.util.ListIntSet; 28 29 import java.util.BitSet; 30 import java.util.List; 31 import java.util.ArrayList; 32 33 /** 34 * A register interference graph 35 */ 36 public 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 */ InterferenceGraph(int countRegs)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 */ add(int regV, int regW)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 */ dumpToStdout()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 */ mergeInterferenceSet(int reg, IntSet set)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 */ ensureCapacity(int size)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