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; 18f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 19f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.RegisterSpecList; 20f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.RegisterSpec; 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.back.InterferenceGraph; 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.IntSet; 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.BitIntSet; 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.ArrayList; 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.BitSet; 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * A register mapper that keeps track of the accumulated interference 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * information for the registers in the new namespace. 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Please note that this mapper requires that the old namespace does not 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * have variable register widths/categories, and the new namespace does. 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic class InterferenceRegisterMapper extends BasicRegisterMapper { 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Array of interference sets. ArrayList is indexed by new namespace 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and BitIntSet's are indexed by old namespace. The list expands 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * as needed and missing items are assumed to interfere with nothing. 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Bit sets are always used here, unlike elsewhere, because the max 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * size of this matrix will be (countSsaRegs * countRopRegs), which may 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * grow to hundreds of K but not megabytes. 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final ArrayList<BitIntSet> newRegInterference; 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 4799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** the interference graph for the old namespace */ 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final InterferenceGraph oldRegInterference; 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 5199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Constructs an instance 52de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 5399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param countOldRegisters number of registers in old namespace 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 5599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project public InterferenceRegisterMapper(InterferenceGraph oldRegInterference, 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int countOldRegisters) { 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project super(countOldRegisters); 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newRegInterference = new ArrayList<BitIntSet>(); 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.oldRegInterference = oldRegInterference; 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project @Override 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void addMapping(int oldReg, int newReg, int category) { 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project super.addMapping(oldReg, newReg, category); 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addInterfence(newReg, oldReg); 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (category == 2) { 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addInterfence(newReg + 1, oldReg); 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 7699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Checks to see if old namespace reg {@code oldReg} interferes 7799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * with what currently maps to {@code newReg}. 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param oldReg old namespace register 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param newReg new namespace register 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param category category of old namespace register 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if oldReg will interfere with newReg 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public boolean interferes(int oldReg, int newReg, int category) { 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (newReg >= newRegInterference.size()) { 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntSet existing = newRegInterference.get(newReg); 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (existing == null) { 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (category == 1) { 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return existing.has(oldReg); 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return existing.has(oldReg) 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project || (interferes(oldReg, newReg+1, category-1)); 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 10299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Checks to see if old namespace reg {@code oldReg} interferes 10399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * with what currently maps to {@code newReg}. 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 10599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param oldSpec {@code non-null;} old namespace register 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param newReg new namespace register 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if oldReg will interfere with newReg 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public boolean interferes(RegisterSpec oldSpec, int newReg) { 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return interferes(oldSpec.getReg(), newReg, oldSpec.getCategory()); 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds a register's interference set to the interference list, 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * growing it if necessary. 116de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param newReg register in new namespace 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param oldReg register in old namespace 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void addInterfence(int newReg, int oldReg) { 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newRegInterference.ensureCapacity(newReg + 1); 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (newReg >= newRegInterference.size()) { 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newRegInterference.add(new BitIntSet(newReg +1)); 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project oldRegInterference.mergeInterferenceSet( 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project oldReg, newRegInterference.get(newReg)); 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Checks to see if any of a set of old-namespace registers are 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * pinned to the specified new-namespace reg + category. Takes into 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * account the category of the old-namespace registers. 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 13699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param oldSpecs {@code non-null;} set of old-namespace regs 13799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param newReg {@code >= 0;} new-namespace register 13899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param targetCategory {@code 1..2;} the number of adjacent new-namespace 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers (starting at ropReg) to consider 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if any of the old-namespace register have been mapped 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to the new-namespace register + category 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public boolean areAnyPinned(RegisterSpecList oldSpecs, 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int newReg, int targetCategory) { 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = oldSpecs.size(); 14699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec oldSpec = oldSpecs.get(i); 149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int r = oldToNew(oldSpec.getReg()); 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If oldSpec is a category-2 register, then check both newReg 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and newReg - 1. 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (r == newReg 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project || (oldSpec.getCategory() == 2 && (r + 1) == newReg) 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project || (targetCategory == 2 && (r == newReg + 1))) { 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 161de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 165