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