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