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 19fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.CstInsn; 20fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.LocalItem; 21fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.RegOps; 22fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.RegisterSpec; 23fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.RegisterSpecList; 24fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.Rop; 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.cst.CstInteger; 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.InterferenceRegisterMapper; 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.NormalSsaInsn; 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.Optimizer; 29fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.ssa.PhiInsn; 30fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.ssa.RegisterMapper; 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.SsaBasicBlock; 32fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.ssa.SsaInsn; 33fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.ssa.SsaMethod; 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.IntIterator; 35fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.util.IntSet; 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.ArrayList; 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.BitSet; 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.Map; 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.TreeMap; 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Allocates registers in a first-fit fashion, with the bottom reserved for 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * method parameters and all SSAregisters representing the same local variable 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * kept together if possible. 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic class FirstFitLocalCombiningAllocator extends RegisterAllocator { 4799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** local debug flag */ 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final boolean DEBUG = false; 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 5099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** maps local variable to a list of associated SSA registers */ 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final Map<LocalItem, ArrayList<RegisterSpec>> localVariables; 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** list of move-result-pesudo instructions seen in this method */ 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final ArrayList<NormalSsaInsn> moveResultPseudoInsns; 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** list of invoke-range instructions seen in this method */ 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final ArrayList<NormalSsaInsn> invokeRangeInsns; 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 596ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao /** list of phi instructions seen in this method */ 606ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao private final ArrayList<PhiInsn> phiInsns; 616ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** indexed by SSA reg; the set of SSA regs we've mapped */ 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final BitSet ssaRegsMapped; 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** Register mapper which will be our result */ 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final InterferenceRegisterMapper mapper; 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 6864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /** end of rop registers range (starting at 0) reserved for parameters */ 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final int paramRangeEnd; 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 7164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /** set of rop registers reserved for parameters or local variables */ 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final BitSet reservedRopRegs; 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 7464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /** set of rop registers that have been used by anything */ 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final BitSet usedRopRegs; 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 7764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /** true if converter should take steps to minimize rop-form registers */ 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final boolean minimizeRegisters; 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs instance. 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 8399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaMeth {@code non-null;} method to process 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param interference non-null interference graph for SSA registers 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param minimizeRegisters true if converter should take steps to 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * minimize rop-form registers 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public FirstFitLocalCombiningAllocator( 8999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project SsaMethod ssaMeth, InterferenceGraph interference, 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean minimizeRegisters) { 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project super(ssaMeth, interference); 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaRegsMapped = new BitSet(ssaMeth.getRegCount()); 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project mapper = new InterferenceRegisterMapper( 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project interference, ssaMeth.getRegCount()); 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.minimizeRegisters = minimizeRegisters; 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Reserve space for the params at the bottom of the register 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * space. Later, we'll flip the params to the end of the register 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * space. 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project paramRangeEnd = ssaMeth.getParamWidth(); 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reservedRopRegs = new BitSet(paramRangeEnd * 2); 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reservedRopRegs.set(0, paramRangeEnd); 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project usedRopRegs = new BitSet(paramRangeEnd * 2); 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project localVariables = new TreeMap<LocalItem, ArrayList<RegisterSpec>>(); 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project moveResultPseudoInsns = new ArrayList<NormalSsaInsn>(); 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project invokeRangeInsns = new ArrayList<NormalSsaInsn>(); 1146ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao phiInsns = new ArrayList<PhiInsn>(); 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project @Override 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public boolean wantsParamsMovedHigh() { 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project @Override 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public RegisterMapper allocateRegisters() { 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project analyzeInstructions(); 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (DEBUG) { 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project printLocalVars(); 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 13399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (DEBUG) System.out.println("--->Mapping local-associated params"); 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project handleLocalAssociatedParams(); 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 13699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (DEBUG) System.out.println("--->Mapping other params"); 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project handleUnassociatedParameters(); 138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 13999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (DEBUG) System.out.println("--->Mapping invoke-range"); 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project handleInvokeRangeInsns(); 14164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein 14299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (DEBUG) { 14399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project System.out.println("--->Mapping local-associated non-params"); 14499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project } 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project handleLocalAssociatedOther(); 146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 14799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (DEBUG) System.out.println("--->Mapping check-cast results"); 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project handleCheckCastResults(); 149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1506ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao if (DEBUG) System.out.println("--->Mapping phis"); 1516ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao handlePhiInsns(); 1526ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao 15399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (DEBUG) System.out.println("--->Mapping others"); 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project handleNormalUnassociated(); 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return mapper; 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Dumps local variable table to stdout for debugging. 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void printLocalVars() { 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project System.out.println("Printing local vars"); 16441aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (Map.Entry<LocalItem, ArrayList<RegisterSpec>> e : 165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project localVariables.entrySet()) { 166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project StringBuilder regs = new StringBuilder(); 167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regs.append('{'); 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regs.append(' '); 17041aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (RegisterSpec reg : e.getValue()) { 171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regs.append('v'); 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regs.append(reg.getReg()); 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regs.append(' '); 174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regs.append('}'); 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project System.out.printf("Local: %s Registers: %s\n", e.getKey(), regs); 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 18164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Maps all local-associated parameters to rop registers. 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleLocalAssociatedParams() { 18499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (ArrayList<RegisterSpec> ssaRegs : localVariables.values()) { 185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = ssaRegs.size(); 186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int paramIndex = -1; 187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int paramCategory = 0; 188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 18964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // First, find out if this local variable is a parameter. 19099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (int i = 0; i < sz; i++) { 191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec ssaSpec = ssaRegs.get(i); 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ssaReg = ssaSpec.getReg(); 193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project paramIndex = getParameterIndexForReg(ssaReg); 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (paramIndex >= 0) { 197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project paramCategory = ssaSpec.getCategory(); 198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addMapping(ssaSpec, paramIndex); 199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 200f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 201f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (paramIndex < 0) { 20464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // This local wasn't a parameter. 205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 20864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // Any remaining local-associated registers will be mapped later. 209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project tryMapRegs(ssaRegs, paramIndex, paramCategory, true); 210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 211f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the parameter index for SSA registers that are method parameters. 21564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * {@code -1} is returned for non-parameter registers. 216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 21799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaReg {@code >=0;} SSA register to look up 21864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return parameter index or {@code -1} if not a parameter 219f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int getParameterIndexForReg(int ssaReg) { 221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn defInsn = ssaMeth.getDefinitionForRegister(ssaReg); 222f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (defInsn == null) { 223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return -1; 224f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 22564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein 226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Rop opcode = defInsn.getOpcode(); 227f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 22864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // opcode == null for phi insns. 229f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (opcode != null && opcode.getOpcode() == RegOps.MOVE_PARAM) { 230f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project CstInsn origInsn = (CstInsn) defInsn.getOriginalRopInsn(); 231f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return ((CstInteger) origInsn.getConstant()).getValue(); 232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 234f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return -1; 235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 236f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 23864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Maps all local-associated registers that are not parameters. 23999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Tries to find an unreserved range that's wide enough for all of 24099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * the SSA registers, and then tries to map them all to that 24199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * range. If not all fit, a new range is tried until all registers 24299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * have been fit. 243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleLocalAssociatedOther() { 24599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (ArrayList<RegisterSpec> specs : localVariables.values()) { 2462e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao int ropReg = paramRangeEnd; 247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 2482e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao boolean done = false; 249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project do { 250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int maxCategory = 1; 251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 25264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // Compute max category for remaining unmapped registers. 253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = specs.size(); 254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 255f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec ssaSpec = specs.get(i); 256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = ssaSpec.getCategory(); 257f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!ssaRegsMapped.get(ssaSpec.getReg()) 258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && category > maxCategory) { 259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project maxCategory = category; 260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 262f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 263f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropReg = findRopRegForLocal(ropReg, maxCategory); 2642e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao if (canMapRegs(specs, ropReg)) { 2652e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao done = tryMapRegs(specs, ropReg, maxCategory, true); 2662e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao } 267f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 2682e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao // Increment for next call to findRopRegForLocal. 269f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropReg++; 270f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } while (!done); 271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 274f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 275f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Tries to map a list of SSA registers into the a rop reg, marking 276f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * used rop space as reserved. SSA registers that don't fit are left 277f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * unmapped. 278f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 27999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param specs {@code non-null;} SSA registers to attempt to map 28099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ropReg {@code >=0;} rop register to map to 28164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param maxAllowedCategory {@code 1..2;} maximum category 28264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * allowed in mapping. 28364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param markReserved do so if {@code true} 28464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return {@code true} if all registers were mapped, {@code false} 28564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * if some remain unmapped 286f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 287f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean tryMapRegs( 288f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<RegisterSpec> specs, int ropReg, 289f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int maxAllowedCategory, boolean markReserved) { 290f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean remaining = false; 29199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (RegisterSpec spec : specs) { 292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(spec.getReg())) { 293f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 294f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 295f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 296f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean succeeded; 297f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project succeeded = tryMapReg(spec, ropReg, maxAllowedCategory); 298f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project remaining = !succeeded || remaining; 299f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (succeeded && markReserved) { 300f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // This only needs to be called once really with 301f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // the widest category used, but <shrug> 302f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project markReserved(ropReg, spec.getCategory()); 303f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 304f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 305f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return !remaining; 306f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 307f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 308f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 309f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Tries to map an SSA register to a rop register. 310f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 31199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaSpec {@code non-null;} SSA register 31299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ropReg {@code >=0;} rop register 31364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param maxAllowedCategory {@code 1..2;} the maximum category 31464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * that the SSA register is allowed to be 31564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return {@code true} if map succeeded, {@code false} if not 316f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 317f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean tryMapReg(RegisterSpec ssaSpec, int ropReg, 318f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int maxAllowedCategory) { 319f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaSpec.getCategory() <= maxAllowedCategory 320f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && !ssaRegsMapped.get(ssaSpec.getReg()) 321f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && canMapReg(ssaSpec, ropReg)) { 322f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addMapping(ssaSpec, ropReg); 323f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 326f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 327f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 328f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 329f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 33064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Marks a range of rop registers as "reserved for a local variable." 331f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 33299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ropReg {@code >= 0;} rop register to reserve 33399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param category {@code > 0;} width to reserve 334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 335f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void markReserved(int ropReg, int category) { 336f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reservedRopRegs.set(ropReg, ropReg + category, true); 337f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 338f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 339f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 34064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Checks to see if any rop registers in the specified range are reserved 34164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * for local variables or parameters. 342f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 34364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param ropRangeStart {@code >= 0;} lowest rop register 34464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param width {@code > 0;} number of rop registers in range. 34564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return {@code true} if any register in range is marked reserved 346f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 347f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean rangeContainsReserved(int ropRangeStart, int width) { 348f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = ropRangeStart; i < (ropRangeStart + width); i++) { 349f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (reservedRopRegs.get(i)) { 350f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 351f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 352f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 353f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 354f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 355f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 356f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 35764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Returns true if given rop register represents the {@code this} pointer 35864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * for a non-static method. 359f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 360f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param startReg rop register 361f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if the "this" pointer is located here. 362f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 363f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean isThisPointerReg(int startReg) { 36464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // "this" is always the first parameter. 365f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return startReg == 0 && !ssaMeth.isStatic(); 366f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 367f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 368f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 36964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Finds a range of unreserved rop registers. 370f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 37164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param startReg {@code >= 0;} a rop register to start the search at 37299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param width {@code > 0;} the width, in registers, required. 37399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} start of available register range. 374f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 375f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int findNextUnreservedRopReg(int startReg, int width) { 376f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int reg; 377f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 378f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reg = reservedRopRegs.nextClearBit(startReg); 379f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 380f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (true) { 381f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i = 1; 382f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 383f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (i < width && !reservedRopRegs.get(reg + i)) { 384f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project i++; 385f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 386f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 387f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (i == width) { 388f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return reg; 389f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 390f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 391f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reg = reservedRopRegs.nextClearBit(reg + i); 392f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 393f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 394f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 395f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 396f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Finds a range of rop regs that can be used for local variables. 39764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * If {@code MIX_LOCALS_AND_OTHER} is {@code false}, this means any 398f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * rop register that has not yet been used. 399f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 40064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param startReg {@code >= 0;} a rop register to start the search at 40199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param width {@code > 0;} the width, in registers, required. 40299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} start of available register range. 403f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 404f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int findRopRegForLocal(int startReg, int width) { 405f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int reg; 406f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 407f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reg = usedRopRegs.nextClearBit(startReg); 408f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 409f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (true) { 410f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i = 1; 411f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 412f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (i < width && !usedRopRegs.get(reg + i)) { 413f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project i++; 414f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 415f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 416f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (i == width) { 417f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return reg; 418f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 419f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 420f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reg = usedRopRegs.nextClearBit(reg + i); 421f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 422f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 423f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 424f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 425f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Maps any parameter that isn't local-associated, which can happen 426f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * in the case where there is no java debug info. 427f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 428f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleUnassociatedParameters() { 429f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSsaRegs = ssaMeth.getRegCount(); 43099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 431f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int ssaReg = 0; ssaReg < szSsaRegs; ssaReg++) { 432f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(ssaReg)) { 433f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // We already did this one above 434f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 435f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 436f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 437f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int paramIndex = getParameterIndexForReg(ssaReg); 438f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 439f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec ssaSpec = getDefinitionSpecForSsaReg(ssaReg); 440f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (paramIndex >= 0) { 441f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addMapping(ssaSpec, paramIndex); 44264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein } 443f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 444f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 445f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 446f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 447f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Handles all insns that want a register range for their sources. 448f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 449f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleInvokeRangeInsns() { 45041aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (NormalSsaInsn insn : invokeRangeInsns) { 451f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project adjustAndMapSourceRangeRange(insn); 452f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 453f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 454f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 455f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 456b6f966024be7d6dd260735c9e541e23572f26f37jeffhao * Handles check cast results to reuse the same source register. 457b6f966024be7d6dd260735c9e541e23572f26f37jeffhao * Inserts a move if it can't map the same register to both and the 458b6f966024be7d6dd260735c9e541e23572f26f37jeffhao * check cast is not caught. 459f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 460f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleCheckCastResults() { 461f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (NormalSsaInsn insn : moveResultPseudoInsns) { 462f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec moveRegSpec = insn.getResult(); 463f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int moveReg = moveRegSpec.getReg(); 464f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet predBlocks = insn.getBlock().getPredecessors(); 465f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 466f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Expect one predecessor block only 467f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (predBlocks.cardinality() != 1) { 468f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 469f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 470f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 471f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock predBlock = 472f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaMeth.getBlocks().get(predBlocks.nextSetBit(0)); 473f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<SsaInsn> insnList = predBlock.getInsns(); 474f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 475f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 476f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If the predecessor block has a check-cast, it will be the last 477f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction 478f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 479f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn checkCastInsn = insnList.get(insnList.size() - 1); 480f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (checkCastInsn.getOpcode().getOpcode() != RegOps.CHECK_CAST) { 481f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 482f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 483f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 484f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec checkRegSpec = checkCastInsn.getSources().get(0); 485f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int checkReg = checkRegSpec.getReg(); 486f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 487f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 488f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * See if either register is already mapped. Most likely the move 489f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * result will be mapped already since the cast result is stored 490f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * in a local variable. 491f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 492b6f966024be7d6dd260735c9e541e23572f26f37jeffhao int category = checkRegSpec.getCategory(); 493b6f966024be7d6dd260735c9e541e23572f26f37jeffhao boolean moveMapped = ssaRegsMapped.get(moveReg); 494b6f966024be7d6dd260735c9e541e23572f26f37jeffhao boolean checkMapped = ssaRegsMapped.get(checkReg); 495b6f966024be7d6dd260735c9e541e23572f26f37jeffhao if (moveMapped & !checkMapped) { 496b6f966024be7d6dd260735c9e541e23572f26f37jeffhao int moveRopReg = mapper.oldToNew(moveReg); 497b6f966024be7d6dd260735c9e541e23572f26f37jeffhao checkMapped = tryMapReg(checkRegSpec, moveRopReg, category); 498b6f966024be7d6dd260735c9e541e23572f26f37jeffhao } 499b6f966024be7d6dd260735c9e541e23572f26f37jeffhao if (checkMapped & !moveMapped) { 500b6f966024be7d6dd260735c9e541e23572f26f37jeffhao int checkRopReg = mapper.oldToNew(checkReg); 501b6f966024be7d6dd260735c9e541e23572f26f37jeffhao moveMapped = tryMapReg(moveRegSpec, checkRopReg, category); 502f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 503f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 504b6f966024be7d6dd260735c9e541e23572f26f37jeffhao // Map any unmapped registers to anything available 505b6f966024be7d6dd260735c9e541e23572f26f37jeffhao if (!moveMapped || !checkMapped) { 50638b61748553bd387bc36b6bd82a8667b6c5f5934jeffhao int ropReg = findNextUnreservedRopReg(paramRangeEnd, category); 507b6f966024be7d6dd260735c9e541e23572f26f37jeffhao ArrayList<RegisterSpec> ssaRegs = 508b6f966024be7d6dd260735c9e541e23572f26f37jeffhao new ArrayList<RegisterSpec>(2); 509b6f966024be7d6dd260735c9e541e23572f26f37jeffhao ssaRegs.add(moveRegSpec); 510b6f966024be7d6dd260735c9e541e23572f26f37jeffhao ssaRegs.add(checkRegSpec); 511f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 512b6f966024be7d6dd260735c9e541e23572f26f37jeffhao while (!tryMapRegs(ssaRegs, ropReg, category, false)) { 513b6f966024be7d6dd260735c9e541e23572f26f37jeffhao ropReg = findNextUnreservedRopReg(ropReg + 1, category); 514b6f966024be7d6dd260735c9e541e23572f26f37jeffhao } 515b6f966024be7d6dd260735c9e541e23572f26f37jeffhao } 516b6f966024be7d6dd260735c9e541e23572f26f37jeffhao 517b6f966024be7d6dd260735c9e541e23572f26f37jeffhao /* 518b6f966024be7d6dd260735c9e541e23572f26f37jeffhao * If source and result have a different mapping, insert a move so 519b6f966024be7d6dd260735c9e541e23572f26f37jeffhao * they can have the same mapping. Don't do this if the check cast 520b6f966024be7d6dd260735c9e541e23572f26f37jeffhao * is caught, since it will overwrite a potentially live value. 521b6f966024be7d6dd260735c9e541e23572f26f37jeffhao */ 522b6f966024be7d6dd260735c9e541e23572f26f37jeffhao boolean hasExceptionHandlers = 523b6f966024be7d6dd260735c9e541e23572f26f37jeffhao checkCastInsn.getOriginalRopInsn().getCatches().size() != 0; 524b6f966024be7d6dd260735c9e541e23572f26f37jeffhao int moveRopReg = mapper.oldToNew(moveReg); 525b6f966024be7d6dd260735c9e541e23572f26f37jeffhao int checkRopReg = mapper.oldToNew(checkReg); 526b6f966024be7d6dd260735c9e541e23572f26f37jeffhao if (moveRopReg != checkRopReg && !hasExceptionHandlers) { 527b6f966024be7d6dd260735c9e541e23572f26f37jeffhao ((NormalSsaInsn) checkCastInsn).changeOneSource(0, 528b6f966024be7d6dd260735c9e541e23572f26f37jeffhao insertMoveBefore(checkCastInsn, checkRegSpec)); 529b6f966024be7d6dd260735c9e541e23572f26f37jeffhao addMapping(checkCastInsn.getSources().get(0), moveRopReg); 530f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 531f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 532f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 533f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 534f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 5356ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao * Handles all phi instructions, trying to map them to a common register. 5366ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao */ 5376ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao private void handlePhiInsns() { 5386ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao for (PhiInsn insn : phiInsns) { 5396ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao processPhiInsn(insn); 5406ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao } 5416ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao } 5426ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao 5436ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao /** 54464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Maps all non-parameter, non-local variable registers. 545f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 546f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleNormalUnassociated() { 547f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSsaRegs = ssaMeth.getRegCount(); 54899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 549f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int ssaReg = 0; ssaReg < szSsaRegs; ssaReg++) { 550f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(ssaReg)) { 551f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // We already did this one 552f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 553f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 554f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 555f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec ssaSpec = getDefinitionSpecForSsaReg(ssaReg); 556f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 557f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaSpec == null) continue; 558f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 559f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = ssaSpec.getCategory(); 560f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Find a rop reg that does not interfere 56138b61748553bd387bc36b6bd82a8667b6c5f5934jeffhao int ropReg = findNextUnreservedRopReg(paramRangeEnd, category); 562f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (!canMapReg(ssaSpec, ropReg)) { 563f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropReg = findNextUnreservedRopReg(ropReg + 1, category); 564f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 565f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 566f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addMapping(ssaSpec, ropReg); 567f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 568f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 569f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 570f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 5712e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao * Checks to see if a list of SSA registers can all be mapped into 5722e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao * the same rop reg. Ignores registers that have already been mapped, 5732e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao * and checks the interference graph and ensures the range does not 5742e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao * cross the parameter range. 5752e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao * 5762e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao * @param specs {@code non-null;} SSA registers to check 5772e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao * @param ropReg {@code >=0;} rop register to check mapping to 5782e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao * @return {@code true} if all unmapped registers can be mapped 5792e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao */ 5802e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao private boolean canMapRegs(ArrayList<RegisterSpec> specs, int ropReg) { 5812e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao for (RegisterSpec spec : specs) { 5822e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao if (ssaRegsMapped.get(spec.getReg())) continue; 5832e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao if (!canMapReg(spec, ropReg)) return false; 5842e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao } 5852e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao return true; 5862e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao } 5872e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao 5882e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao /** 58999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Checks to see if {@code ssaSpec} can be mapped to 59099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code ropReg}. Checks interference graph and ensures 591f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the range does not cross the parameter range. 592f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 59399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaSpec {@code non-null;} SSA spec 594f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param ropReg prosepctive new-namespace reg 59564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return {@code true} if mapping is possible 596f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 597f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean canMapReg(RegisterSpec ssaSpec, int ropReg) { 598f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = ssaSpec.getCategory(); 599f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return !(spansParamRange(ropReg, category) 600f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project || mapper.interferes(ssaSpec, ropReg)); 601f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 60264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein 603f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 60464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Returns true if the specified rop register + category 60599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * will cross the boundry between the lower {@code paramWidth} 606f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers reserved for method params and the upper registers. We cannot 607f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * allocate a register that spans the param block and the normal block, 608f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * because we will be moving the param block to high registers later. 60964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 610f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param ssaReg register in new namespace 611f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param category width that the register will have 61264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return {@code true} in the case noted above 613f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 614f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean spansParamRange(int ssaReg, int category) { 615f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return ((ssaReg < paramRangeEnd) 616f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && ((ssaReg + category) > paramRangeEnd)); 617f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 618f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 619f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 620f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Analyze each instruction and find out all the local variable assignments 621f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and move-result-pseudo/invoke-range instrucitons. 622f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 623f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void analyzeInstructions() { 624f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaMeth.forEachInsn(new SsaInsn.Visitor() { 625f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 626f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitMoveInsn(NormalSsaInsn insn) { 627f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project processInsn(insn); 628f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 629f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 630f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 631f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitPhiInsn(PhiInsn insn) { 632f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project processInsn(insn); 633f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 634f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 635f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 636f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitNonMoveInsn(NormalSsaInsn insn) { 637f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project processInsn(insn); 638f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 639f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 640f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 641f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This method collects three types of instructions: 64264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 643f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1) Adds a local variable assignment to the 64499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code localVariables} map. 645f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 2) Add move-result-pseudo to the 64699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code moveResultPseudoInsns} list. 647f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 3) Add invoke-range to the 64899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code invokeRangeInsns} list. 649f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 65099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn that may represent a 65199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * local variable assignment 652f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 653f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void processInsn(SsaInsn insn) { 654f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec assignment; 655f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assignment = insn.getLocalAssignment(); 656f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 657f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (assignment != null) { 658f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LocalItem local = assignment.getLocalItem(); 659f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 66099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project ArrayList<RegisterSpec> regList 66199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project = localVariables.get(local); 662f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 663f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (regList == null) { 664f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regList = new ArrayList<RegisterSpec>(); 665f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project localVariables.put(local, regList); 666f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 667f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 668f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regList.add(assignment); 669f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 670f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 671f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn instanceof NormalSsaInsn) { 672f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn.getOpcode().getOpcode() == 673f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegOps.MOVE_RESULT_PSEUDO) { 674f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project moveResultPseudoInsns.add((NormalSsaInsn) insn); 675f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (Optimizer.getAdvice().requiresSourcesInOrder( 676f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn.getOriginalRopInsn().getOpcode(), 677f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn.getSources())) { 678f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project invokeRangeInsns.add((NormalSsaInsn) insn); 679f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 6806ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao } else if (insn instanceof PhiInsn) { 6816ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao phiInsns.add((PhiInsn) insn); 682f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 683f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 684f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 685f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project }); 686f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 687f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 688f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 68964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Adds a mapping from an SSA register to a rop register. 69099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@link #canMapReg} should have already been called. 691f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 69299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaSpec {@code non-null;} SSA register to map from 69364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param ropReg {@code >=0;} rop register to map to 694f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 695f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void addMapping(RegisterSpec ssaSpec, int ropReg) { 696f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ssaReg = ssaSpec.getReg(); 697f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 69864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // An assertion. 699f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(ssaReg) || !canMapReg(ssaSpec, ropReg)) { 700f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new RuntimeException( 701f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project "attempt to add invalid register mapping"); 702f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 703f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 704f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (DEBUG) { 705f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project System.out.printf("Add mapping s%d -> v%d c:%d\n", 70699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project ssaSpec.getReg(), ropReg, ssaSpec.getCategory()); 707f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 708f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 709f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = ssaSpec.getCategory(); 710f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project mapper.addMapping(ssaSpec.getReg(), ropReg, category); 711f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaRegsMapped.set(ssaReg); 712f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project usedRopRegs.set(ropReg, ropReg + category); 713f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 714f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 715f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 716f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 717f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Maps the source registers of the specified instruction such that they 71864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * will fall in a contiguous range in rop form. Moves are inserted as 719f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * necessary to allow the range to be allocated. 720f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 72199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn whos sources to process 722f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 723f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void adjustAndMapSourceRangeRange(NormalSsaInsn insn) { 72499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project int newRegStart = findRangeAndAdjust(insn); 725f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 726f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList sources = insn.getSources(); 727f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSources = sources.size(); 728f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int nextRopReg = newRegStart; 72999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 730f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szSources; i++) { 731f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec source = sources.get(i); 732f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sourceReg = source.getReg(); 733f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = source.getCategory(); 734f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int curRopReg = nextRopReg; 735f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project nextRopReg += category; 736f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 737f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(sourceReg)) { 738f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 739f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 740f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 741f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LocalItem localItem = getLocalItemForReg(sourceReg); 742f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addMapping(source, curRopReg); 743f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 744f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (localItem != null) { 745f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project markReserved(curRopReg, category); 746f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<RegisterSpec> similarRegisters 747f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = localVariables.get(localItem); 748f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 749f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSimilar = similarRegisters.size(); 750f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 75164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /* 75264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Try to map all SSA registers also associated with 75364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * this local. 75464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein */ 755f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int j = 0; j < szSimilar; j++) { 756f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec similarSpec = similarRegisters.get(j); 757f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int similarReg = similarSpec.getReg(); 758f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 75964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // Don't map anything that's also a source. 760f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (-1 != sources.indexOfRegister(similarReg)) { 761f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 762f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 763f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 76464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // Registers left unmapped will get handled later. 765f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project tryMapReg(similarSpec, curRopReg, category); 766f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 767f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 768f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 769f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 770f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 771f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 772f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Find a contiguous rop register range that fits the specified 773f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction's sources. First, try to center the range around 77464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * sources that have already been mapped to rop registers. If that fails, 775f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * just find a new contiguous range that doesn't interfere. 77664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 77799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} the insn whose sources need to 77899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * fit. Must be last insn in basic block. 77999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} rop register of start of range 780f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 781f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int findRangeAndAdjust(NormalSsaInsn insn) { 782f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList sources = insn.getSources(); 783f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSources = sources.size(); 784f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // the category for each source index 785f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int categoriesForIndex[] = new int[szSources]; 786f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int rangeLength = 0; 787f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 788f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Compute rangeLength and categoriesForIndex 789f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szSources; i++) { 790f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = sources.get(i).getCategory(); 791f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project categoriesForIndex[i] = category; 792f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project rangeLength += categoriesForIndex[i]; 793f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 794f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 79564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // the highest score of fits tried so far 796f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int maxScore = Integer.MIN_VALUE; 797f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // the high scoring range's start 798f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int resultRangeStart = -1; 799f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // by source index: set of sources needing moves in high scoring plan 800f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet resultMovesRequired = null; 801f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 802f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 803f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * First, go through each source that's already been mapped. Try 80464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * to center the range around the rop register this source is mapped 805f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to. 806f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 807f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int rangeStartOffset = 0; 808f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szSources; i++) { 809f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ssaCenterReg = sources.get(i).getReg(); 810f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 811f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (i != 0) { 812f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project rangeStartOffset -= categoriesForIndex[i - 1]; 813f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 814f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!ssaRegsMapped.get(ssaCenterReg)) { 815f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 816f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 817f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 818f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int rangeStart = mapper.oldToNew(ssaCenterReg) + rangeStartOffset; 819f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 820f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (rangeStart < 0 || spansParamRange(rangeStart, rangeLength)) { 821f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 822f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 823f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 824f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet curMovesRequired = new BitSet(szSources); 825f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 826f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int fitWidth 827f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = fitPlanForRange(rangeStart, insn, categoriesForIndex, 828f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project curMovesRequired); 829f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 830f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (fitWidth < 0) { 831f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 832f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 833f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 834f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int score = fitWidth - curMovesRequired.cardinality(); 835f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 836f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (score > maxScore) { 837f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project maxScore = score; 838f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultRangeStart = rangeStart; 839f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultMovesRequired = curMovesRequired; 840f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 841f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 842f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (fitWidth == rangeLength) { 843f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // We can't do any better than this, so stop here 844f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 845f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 846f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 847f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 848f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 849f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If we were unable to find a plan for a fit centered around 850f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * an already-mapped source, just try to find a range of 851f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers we can move the range into. 852f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 853f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 854f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (resultRangeStart == -1) { 855f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultMovesRequired = new BitSet(szSources); 856f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 857f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultRangeStart = findAnyFittingRange(insn, rangeLength, 858f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project categoriesForIndex, resultMovesRequired); 859f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 860f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 861f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 86264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Now, insert any moves required. 863f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 864f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 86541aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (int i = resultMovesRequired.nextSetBit(0); i >= 0; 86641aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein i = resultMovesRequired.nextSetBit(i+1)) { 86741aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein insn.changeOneSource(i, insertMoveBefore(insn, sources.get(i))); 868f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 869f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 870f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return resultRangeStart; 871f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 872f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 873f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 874f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Finds an unreserved range that will fit the sources of the 875f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * specified instruction. Does not bother trying to center the range 876f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * around an already-mapped source register; 877f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 87899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn to build range for 87964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param rangeLength {@code >=0;} length required in register units 88099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param categoriesForIndex {@code non-null;} indexed by source index; 88164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * the category for each source 88299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param outMovesRequired {@code non-null;} an output parameter indexed by 883f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * source index that will contain the set of sources which need 88464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * moves inserted 88564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return the rop register that starts the fitting range 886f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 887f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int findAnyFittingRange(NormalSsaInsn insn, int rangeLength, 888f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int[] categoriesForIndex, BitSet outMovesRequired) { 88938b61748553bd387bc36b6bd82a8667b6c5f5934jeffhao int rangeStart = paramRangeEnd; 890f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (true) { 891f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project rangeStart = findNextUnreservedRopReg(rangeStart, rangeLength); 892f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int fitWidth 893f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = fitPlanForRange(rangeStart, insn, 894f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project categoriesForIndex, outMovesRequired); 895f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 896f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (fitWidth >= 0) { 897f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 898f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 899f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project rangeStart++; 900f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project outMovesRequired.clear(); 901f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 902f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return rangeStart; 903f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 904f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 905f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 906f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Attempts to build a plan for fitting a range of sources into rop 907f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers. 908f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 90999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ropReg {@code >= 0;} rop reg that begins range 91099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn to plan range for 91199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param categoriesForIndex {@code non-null;} indexed by source index; 91264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * the category for each source 91399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param outMovesRequired {@code non-null;} an output parameter indexed by 914f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * source index that will contain the set of sources which need 91564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * moves inserted 916f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return the width of the fit that that does not involve added moves or 91764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * {@code -1} if "no fit possible" 918f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 919f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int fitPlanForRange(int ropReg, NormalSsaInsn insn, 920f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int[] categoriesForIndex, BitSet outMovesRequired) { 921f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList sources = insn.getSources(); 922f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSources = sources.size(); 923f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int fitWidth = 0; 924f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntSet liveOut = insn.getBlock().getLiveOutRegs(); 925f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList liveOutSpecs = ssaSetToSpecs(liveOut); 926f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 92764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // An SSA reg may only be mapped into a range once. 928f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet seen = new BitSet(ssaMeth.getRegCount()); 929f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 930f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szSources ; i++) { 931f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec ssaSpec = sources.get(i); 932f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ssaReg = ssaSpec.getReg(); 933f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = categoriesForIndex[i]; 934f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 935f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (i != 0) { 936f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropReg += categoriesForIndex[i-1]; 937f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 938f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 939f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(ssaReg) 940f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && mapper.oldToNew(ssaReg) == ropReg) { 94164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // This is a register that is already mapped appropriately. 942f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project fitWidth += category; 943f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (rangeContainsReserved(ropReg, category)) { 944f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project fitWidth = -1; 945f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 946f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (!ssaRegsMapped.get(ssaReg) 947f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && canMapReg(ssaSpec, ropReg) 948f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && !seen.get(ssaReg)) { 94964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // This is a register that can be mapped appropriately. 950f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project fitWidth += category; 951f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (!mapper.areAnyPinned(liveOutSpecs, ropReg, category) 952f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && !mapper.areAnyPinned(sources, ropReg, category)) { 953f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 95464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * This is a source that can be moved. We can insert a 95564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * move as long as: 95664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 95764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * * no SSA register pinned to the desired rop reg 95864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * is live out on the block 959f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 96064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * * no SSA register pinned to desired rop reg is 96164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * a source of this insn (since this may require 96264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * overlapping moves, which we can't presently handle) 963f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 964f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 965f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project outMovesRequired.set(i); 966f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 967f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project fitWidth = -1; 968f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 969f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 970f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 971f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project seen.set(ssaReg); 972f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 973f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return fitWidth; 974f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 975f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 976f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 977f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Converts a bit set of SSA registers into a RegisterSpecList containing 978f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the definition specs of all the registers. 979f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 98099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaSet {@code non-null;} set of SSA registers 981f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return list of RegisterSpecs as noted above 982f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 983f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList ssaSetToSpecs(IntSet ssaSet) { 984f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList result = new RegisterSpecList(ssaSet.elements()); 985f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 986f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntIterator iter = ssaSet.iterator(); 987f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 988f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i = 0; 989f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (iter.hasNext()) { 990f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.set(i++, getDefinitionSpecForSsaReg(iter.next())); 991f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 99264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein 993f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 994f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 995f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 996f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 99764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Gets a local item associated with an ssa register, if one exists. 998f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 99999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaReg {@code >= 0;} SSA register 100099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code null-ok;} associated local item or null 1001f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1002f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private LocalItem getLocalItemForReg(int ssaReg) { 100341aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (Map.Entry<LocalItem, ArrayList<RegisterSpec>> entry : 100441aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein localVariables.entrySet()) { 100599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (RegisterSpec spec : entry.getValue()) { 1006f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (spec.getReg() == ssaReg) { 1007f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return entry.getKey(); 1008f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1009f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1010f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1011f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1012f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return null; 1013f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 10146ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao 10156ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao /** 10166ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao * Attempts to map the sources and result of a phi to a common register. 10171acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * Will try existing mappings first, from most to least common. If none 10181acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * of the registers have mappings yet, a new mapping is created. 10196ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao */ 10206ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao private void processPhiInsn(PhiInsn insn) { 10216ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao RegisterSpec result = insn.getResult(); 10226ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao int resultReg = result.getReg(); 10236ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao int category = result.getCategory(); 10241acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao 10251acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao RegisterSpecList sources = insn.getSources(); 10261acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao int sourcesSize = sources.size(); 10271acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao 10281acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao // List of phi sources / result that need mapping 10296ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao ArrayList<RegisterSpec> ssaRegs = new ArrayList<RegisterSpec>(); 10306ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao 10311acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao // Track how many times a particular mapping is found 10321acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao Multiset mapSet = new Multiset(sourcesSize + 1); 10331acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao 10341acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao /* 10351acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * If the result of the phi has an existing mapping, get it. 10361acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * Otherwise, add it to the list of regs that need mapping. 10371acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao */ 10386ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao if (ssaRegsMapped.get(resultReg)) { 10391acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao mapSet.add(mapper.oldToNew(resultReg)); 10401acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } else { 10411acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao ssaRegs.add(result); 10426ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao } 10436ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao 10441acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao for (int i = 0; i < sourcesSize; i++) { 10456ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao RegisterSpec source = sources.get(i); 10467debb9113af41a38a6f5ecbda1a2c28c5e5a17afjeffhao SsaInsn def = ssaMeth.getDefinitionForRegister(source.getReg()); 10477debb9113af41a38a6f5ecbda1a2c28c5e5a17afjeffhao RegisterSpec sourceDef = def.getResult(); 10487debb9113af41a38a6f5ecbda1a2c28c5e5a17afjeffhao int sourceReg = sourceDef.getReg(); 10496ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao 10501acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao /* 10511acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * If a source of the phi has an existing mapping, get it. 10521acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * Otherwise, add it to the list of regs that need mapping. 10531acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao */ 10546ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao if (ssaRegsMapped.get(sourceReg)) { 10551acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao mapSet.add(mapper.oldToNew(sourceReg)); 10561acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } else { 10577debb9113af41a38a6f5ecbda1a2c28c5e5a17afjeffhao ssaRegs.add(sourceDef); 10581acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } 10591acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } 10601acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao 10611acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao // Try all existing mappings, with the most common ones first 10621acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao for (int i = 0; i < mapSet.getSize(); i++) { 10631acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao int maxReg = mapSet.getAndRemoveHighestCount(); 10641acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao tryMapRegs(ssaRegs, maxReg, category, false); 10651acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } 10661acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao 10671acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao // Map any remaining unmapped regs with whatever fits 106838b61748553bd387bc36b6bd82a8667b6c5f5934jeffhao int mapReg = findNextUnreservedRopReg(paramRangeEnd, category); 10691acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao while (!tryMapRegs(ssaRegs, mapReg, category, false)) { 10701acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao mapReg = findNextUnreservedRopReg(mapReg + 1, category); 10711acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } 10721acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } 10736ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao 10741acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao // A set that tracks how often elements are added to it. 10751acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao private static class Multiset { 10761acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao private final int[] reg; 10771acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao private final int[] count; 10781acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao private int size; 10791acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao 10801acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao /** 10811acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * Constructs an instance. 10821acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * 10831acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * @param maxSize the maximum distinct elements the set may have 10841acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao */ 10851acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao public Multiset(int maxSize) { 10861acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao reg = new int[maxSize]; 10871acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao count = new int[maxSize]; 10881acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao size = 0; 10891acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } 10901acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao 10911acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao /** 10921acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * Adds an element to the set. 10931acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * 10941acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * @param element element to add 10951acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao */ 10961acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao public void add(int element) { 10971acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao for (int i = 0; i < size; i++) { 10981acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao if (reg[i] == element) { 10991acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao count[i]++; 11006ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao return; 11016ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao } 11021acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } 11031acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao 11041acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao reg[size] = element; 11051acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao count[size] = 1; 11061acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao size++; 11071acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } 11086ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao 11091acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao /** 11101acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * Searches the set for the element that has been added the most. 11111acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * In the case of a tie, the element that was added first is returned. 11121acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * Then, it clears the count on that element. The size of the set 11131acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * remains unchanged. 11141acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * 11151acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * @return element with the highest count 11161acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao */ 11171acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao public int getAndRemoveHighestCount() { 11181acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao int maxIndex = -1; 11191acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao int maxReg = -1; 11201acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao int maxCount = 0; 11211acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao 11221acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao for (int i = 0; i < size; i++) { 11231acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao if (maxCount < count[i]) { 11241acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao maxIndex = i; 11251acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao maxReg = reg[i]; 11261acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao maxCount = count[i]; 11271acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } 11286ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao } 11291acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao 11301acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao count[maxIndex] = 0; 11311acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao return maxReg; 11326ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao } 11336ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao 11341acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao /** 11351acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * Gets the number of distinct elements in the set. 11361acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * 11371acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * @return size of the set 11381acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao */ 11391acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao public int getSize() { 11401acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao return size; 11416ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao } 11426ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao } 1143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 1144