1f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 2f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Copyright (C) 2007 The Android Open Source Project 3f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 4f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 5f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * you may not use this file except in compliance with the License. 6f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * You may obtain a copy of the License at 7f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 8f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 9f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 10f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 11f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 12f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * See the License for the specific language governing permissions and 14f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * limitations under the License. 15f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 16f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 17f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpackage com.android.dx.ssa.back; 18f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 19f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.*; 20f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.cst.CstInteger; 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.InterferenceRegisterMapper; 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.RegisterMapper; 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.SsaInsn; 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.SsaMethod; 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.NormalSsaInsn; 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.PhiInsn; 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.Optimizer; 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.ssa.SsaBasicBlock; 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.IntSet; 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.IntIterator; 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.ArrayList; 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.BitSet; 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.Map; 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.TreeMap; 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Allocates registers in a first-fit fashion, with the bottom reserved for 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * method parameters and all SSAregisters representing the same local variable 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * kept together if possible. 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic class FirstFitLocalCombiningAllocator extends RegisterAllocator { 4399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** local debug flag */ 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final boolean DEBUG = false; 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 4699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** maps local variable to a list of associated SSA registers */ 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final Map<LocalItem, ArrayList<RegisterSpec>> localVariables; 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** list of move-result-pesudo instructions seen in this method */ 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final ArrayList<NormalSsaInsn> moveResultPseudoInsns; 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** list of invoke-range instructions seen in this method */ 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final ArrayList<NormalSsaInsn> invokeRangeInsns; 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 556ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao /** list of phi instructions seen in this method */ 566ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao private final ArrayList<PhiInsn> phiInsns; 576ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** indexed by SSA reg; the set of SSA regs we've mapped */ 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final BitSet ssaRegsMapped; 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** Register mapper which will be our result */ 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final InterferenceRegisterMapper mapper; 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 6464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /** end of rop registers range (starting at 0) reserved for parameters */ 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final int paramRangeEnd; 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 6764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /** set of rop registers reserved for parameters or local variables */ 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final BitSet reservedRopRegs; 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 7064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /** set of rop registers that have been used by anything */ 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final BitSet usedRopRegs; 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 7364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /** true if converter should take steps to minimize rop-form registers */ 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final boolean minimizeRegisters; 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs instance. 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 7999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaMeth {@code non-null;} method to process 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param interference non-null interference graph for SSA registers 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param minimizeRegisters true if converter should take steps to 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * minimize rop-form registers 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public FirstFitLocalCombiningAllocator( 8599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project SsaMethod ssaMeth, InterferenceGraph interference, 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean minimizeRegisters) { 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project super(ssaMeth, interference); 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaRegsMapped = new BitSet(ssaMeth.getRegCount()); 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project mapper = new InterferenceRegisterMapper( 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project interference, ssaMeth.getRegCount()); 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.minimizeRegisters = minimizeRegisters; 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Reserve space for the params at the bottom of the register 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * space. Later, we'll flip the params to the end of the register 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * space. 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project paramRangeEnd = ssaMeth.getParamWidth(); 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reservedRopRegs = new BitSet(paramRangeEnd * 2); 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reservedRopRegs.set(0, paramRangeEnd); 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project usedRopRegs = new BitSet(paramRangeEnd * 2); 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project localVariables = new TreeMap<LocalItem, ArrayList<RegisterSpec>>(); 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project moveResultPseudoInsns = new ArrayList<NormalSsaInsn>(); 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project invokeRangeInsns = new ArrayList<NormalSsaInsn>(); 1106ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao phiInsns = new ArrayList<PhiInsn>(); 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project @Override 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public boolean wantsParamsMovedHigh() { 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project @Override 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public RegisterMapper allocateRegisters() { 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project analyzeInstructions(); 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (DEBUG) { 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project printLocalVars(); 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 12999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (DEBUG) System.out.println("--->Mapping local-associated params"); 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project handleLocalAssociatedParams(); 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 13299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (DEBUG) System.out.println("--->Mapping other params"); 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project handleUnassociatedParameters(); 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 13599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (DEBUG) System.out.println("--->Mapping invoke-range"); 136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project handleInvokeRangeInsns(); 13764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein 13899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (DEBUG) { 13999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project System.out.println("--->Mapping local-associated non-params"); 14099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project } 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project handleLocalAssociatedOther(); 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 14399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (DEBUG) System.out.println("--->Mapping check-cast results"); 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project handleCheckCastResults(); 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1466ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao if (DEBUG) System.out.println("--->Mapping phis"); 1476ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao handlePhiInsns(); 1486ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao 14999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (DEBUG) System.out.println("--->Mapping others"); 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project handleNormalUnassociated(); 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return mapper; 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Dumps local variable table to stdout for debugging. 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void printLocalVars() { 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project System.out.println("Printing local vars"); 16041aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (Map.Entry<LocalItem, ArrayList<RegisterSpec>> e : 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project localVariables.entrySet()) { 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project StringBuilder regs = new StringBuilder(); 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regs.append('{'); 165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regs.append(' '); 16641aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (RegisterSpec reg : e.getValue()) { 167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regs.append('v'); 168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regs.append(reg.getReg()); 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regs.append(' '); 170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regs.append('}'); 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project System.out.printf("Local: %s Registers: %s\n", e.getKey(), regs); 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 17764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Maps all local-associated parameters to rop registers. 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleLocalAssociatedParams() { 18099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (ArrayList<RegisterSpec> ssaRegs : localVariables.values()) { 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = ssaRegs.size(); 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int paramIndex = -1; 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int paramCategory = 0; 184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 18564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // First, find out if this local variable is a parameter. 18699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (int i = 0; i < sz; i++) { 187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec ssaSpec = ssaRegs.get(i); 188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ssaReg = ssaSpec.getReg(); 189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 190f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project paramIndex = getParameterIndexForReg(ssaReg); 191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (paramIndex >= 0) { 193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project paramCategory = ssaSpec.getCategory(); 194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addMapping(ssaSpec, paramIndex); 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (paramIndex < 0) { 20064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // This local wasn't a parameter. 201f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 20464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // Any remaining local-associated registers will be mapped later. 205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project tryMapRegs(ssaRegs, paramIndex, paramCategory, true); 206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 208f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the parameter index for SSA registers that are method parameters. 21164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * {@code -1} is returned for non-parameter registers. 212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 21399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaReg {@code >=0;} SSA register to look up 21464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return parameter index or {@code -1} if not a parameter 215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int getParameterIndexForReg(int ssaReg) { 217f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn defInsn = ssaMeth.getDefinitionForRegister(ssaReg); 218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (defInsn == null) { 219f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return -1; 220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 22164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein 222f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Rop opcode = defInsn.getOpcode(); 223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 22464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // opcode == null for phi insns. 225f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (opcode != null && opcode.getOpcode() == RegOps.MOVE_PARAM) { 226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project CstInsn origInsn = (CstInsn) defInsn.getOriginalRopInsn(); 227f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return ((CstInteger) origInsn.getConstant()).getValue(); 228f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 229f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 230f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return -1; 231f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 23464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Maps all local-associated registers that are not parameters. 23599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Tries to find an unreserved range that's wide enough for all of 23699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * the SSA registers, and then tries to map them all to that 23799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * range. If not all fit, a new range is tried until all registers 23899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * have been fit. 239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleLocalAssociatedOther() { 24199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (ArrayList<RegisterSpec> specs : localVariables.values()) { 2422e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao int ropReg = paramRangeEnd; 243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 2442e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao boolean done = false; 245f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project do { 246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int maxCategory = 1; 247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 24864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // Compute max category for remaining unmapped registers. 249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = specs.size(); 250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec ssaSpec = specs.get(i); 252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = ssaSpec.getCategory(); 253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!ssaRegsMapped.get(ssaSpec.getReg()) 254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && category > maxCategory) { 255f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project maxCategory = category; 256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 257f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropReg = findRopRegForLocal(ropReg, maxCategory); 2602e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao if (canMapRegs(specs, ropReg)) { 2612e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao done = tryMapRegs(specs, ropReg, maxCategory, true); 2622e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao } 263f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 2642e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao // Increment for next call to findRopRegForLocal. 265f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropReg++; 266f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } while (!done); 267f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 268f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 269f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 270f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Tries to map a list of SSA registers into the a rop reg, marking 272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * used rop space as reserved. SSA registers that don't fit are left 273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * unmapped. 274f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 27599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param specs {@code non-null;} SSA registers to attempt to map 27699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ropReg {@code >=0;} rop register to map to 27764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param maxAllowedCategory {@code 1..2;} maximum category 27864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * allowed in mapping. 27964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param markReserved do so if {@code true} 28064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return {@code true} if all registers were mapped, {@code false} 28164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * if some remain unmapped 282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 283f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean tryMapRegs( 284f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<RegisterSpec> specs, int ropReg, 285f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int maxAllowedCategory, boolean markReserved) { 286f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean remaining = false; 28799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (RegisterSpec spec : specs) { 288f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(spec.getReg())) { 289f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 290f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 291f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean succeeded; 293f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project succeeded = tryMapReg(spec, ropReg, maxAllowedCategory); 294f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project remaining = !succeeded || remaining; 295f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (succeeded && markReserved) { 296f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // This only needs to be called once really with 297f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // the widest category used, but <shrug> 298f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project markReserved(ropReg, spec.getCategory()); 299f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 300f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 301f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return !remaining; 302f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 303f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 304f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 305f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Tries to map an SSA register to a rop register. 306f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 30799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaSpec {@code non-null;} SSA register 30899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ropReg {@code >=0;} rop register 30964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param maxAllowedCategory {@code 1..2;} the maximum category 31064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * that the SSA register is allowed to be 31164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return {@code true} if map succeeded, {@code false} if not 312f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 313f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean tryMapReg(RegisterSpec ssaSpec, int ropReg, 314f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int maxAllowedCategory) { 315f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaSpec.getCategory() <= maxAllowedCategory 316f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && !ssaRegsMapped.get(ssaSpec.getReg()) 317f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && canMapReg(ssaSpec, ropReg)) { 318f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addMapping(ssaSpec, ropReg); 319f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 320f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 321f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 322f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 323f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 32664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Marks a range of rop registers as "reserved for a local variable." 327f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 32899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ropReg {@code >= 0;} rop register to reserve 32999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param category {@code > 0;} width to reserve 330f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 331f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void markReserved(int ropReg, int category) { 332f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reservedRopRegs.set(ropReg, ropReg + category, true); 333f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 335f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 33664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Checks to see if any rop registers in the specified range are reserved 33764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * for local variables or parameters. 338f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 33964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param ropRangeStart {@code >= 0;} lowest rop register 34064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param width {@code > 0;} number of rop registers in range. 34164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return {@code true} if any register in range is marked reserved 342f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 343f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean rangeContainsReserved(int ropRangeStart, int width) { 344f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = ropRangeStart; i < (ropRangeStart + width); i++) { 345f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (reservedRopRegs.get(i)) { 346f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 347f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 348f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 349f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 350f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 351f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 352f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 35364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Returns true if given rop register represents the {@code this} pointer 35464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * for a non-static method. 355f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 356f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param startReg rop register 357f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if the "this" pointer is located here. 358f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 359f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean isThisPointerReg(int startReg) { 36064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // "this" is always the first parameter. 361f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return startReg == 0 && !ssaMeth.isStatic(); 362f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 363f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 364f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 36564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Finds a range of unreserved rop registers. 366f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 36764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param startReg {@code >= 0;} a rop register to start the search at 36899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param width {@code > 0;} the width, in registers, required. 36999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} start of available register range. 370f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 371f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int findNextUnreservedRopReg(int startReg, int width) { 372f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int reg; 373f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 374f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reg = reservedRopRegs.nextClearBit(startReg); 375f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 376f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (true) { 377f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i = 1; 378f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 379f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (i < width && !reservedRopRegs.get(reg + i)) { 380f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project i++; 381f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 382f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 383f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (i == width) { 384f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return reg; 385f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 386f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 387f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reg = reservedRopRegs.nextClearBit(reg + i); 388f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 389f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 390f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 391f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 392f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Finds a range of rop regs that can be used for local variables. 39364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * If {@code MIX_LOCALS_AND_OTHER} is {@code false}, this means any 394f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * rop register that has not yet been used. 395f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 39664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param startReg {@code >= 0;} a rop register to start the search at 39799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param width {@code > 0;} the width, in registers, required. 39899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} start of available register range. 399f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 400f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int findRopRegForLocal(int startReg, int width) { 401f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int reg; 402f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 403f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reg = usedRopRegs.nextClearBit(startReg); 404f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 405f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (true) { 406f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i = 1; 407f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 408f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (i < width && !usedRopRegs.get(reg + i)) { 409f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project i++; 410f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 411f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 412f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (i == width) { 413f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return reg; 414f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 415f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 416f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reg = usedRopRegs.nextClearBit(reg + i); 417f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 418f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 419f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 420f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 421f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Maps any parameter that isn't local-associated, which can happen 422f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * in the case where there is no java debug info. 423f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 424f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleUnassociatedParameters() { 425f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSsaRegs = ssaMeth.getRegCount(); 42699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 427f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int ssaReg = 0; ssaReg < szSsaRegs; ssaReg++) { 428f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(ssaReg)) { 429f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // We already did this one above 430f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 431f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 432f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 433f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int paramIndex = getParameterIndexForReg(ssaReg); 434f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 435f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec ssaSpec = getDefinitionSpecForSsaReg(ssaReg); 436f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (paramIndex >= 0) { 437f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addMapping(ssaSpec, paramIndex); 43864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein } 439f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 440f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 441f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 442f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 443f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Handles all insns that want a register range for their sources. 444f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 445f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleInvokeRangeInsns() { 44641aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (NormalSsaInsn insn : invokeRangeInsns) { 447f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project adjustAndMapSourceRangeRange(insn); 448f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 449f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 450f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 451f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 452b6f966024be7d6dd260735c9e541e23572f26f37jeffhao * Handles check cast results to reuse the same source register. 453b6f966024be7d6dd260735c9e541e23572f26f37jeffhao * Inserts a move if it can't map the same register to both and the 454b6f966024be7d6dd260735c9e541e23572f26f37jeffhao * check cast is not caught. 455f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 456f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleCheckCastResults() { 457f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (NormalSsaInsn insn : moveResultPseudoInsns) { 458f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec moveRegSpec = insn.getResult(); 459f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int moveReg = moveRegSpec.getReg(); 460f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet predBlocks = insn.getBlock().getPredecessors(); 461f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 462f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Expect one predecessor block only 463f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (predBlocks.cardinality() != 1) { 464f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 465f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 466f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 467f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock predBlock = 468f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaMeth.getBlocks().get(predBlocks.nextSetBit(0)); 469f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<SsaInsn> insnList = predBlock.getInsns(); 470f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 471f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 472f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If the predecessor block has a check-cast, it will be the last 473f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction 474f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 475f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn checkCastInsn = insnList.get(insnList.size() - 1); 476f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (checkCastInsn.getOpcode().getOpcode() != RegOps.CHECK_CAST) { 477f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 478f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 479f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 480f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec checkRegSpec = checkCastInsn.getSources().get(0); 481f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int checkReg = checkRegSpec.getReg(); 482f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 483f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 484f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * See if either register is already mapped. Most likely the move 485f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * result will be mapped already since the cast result is stored 486f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * in a local variable. 487f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 488b6f966024be7d6dd260735c9e541e23572f26f37jeffhao int category = checkRegSpec.getCategory(); 489b6f966024be7d6dd260735c9e541e23572f26f37jeffhao boolean moveMapped = ssaRegsMapped.get(moveReg); 490b6f966024be7d6dd260735c9e541e23572f26f37jeffhao boolean checkMapped = ssaRegsMapped.get(checkReg); 491b6f966024be7d6dd260735c9e541e23572f26f37jeffhao if (moveMapped & !checkMapped) { 492b6f966024be7d6dd260735c9e541e23572f26f37jeffhao int moveRopReg = mapper.oldToNew(moveReg); 493b6f966024be7d6dd260735c9e541e23572f26f37jeffhao checkMapped = tryMapReg(checkRegSpec, moveRopReg, category); 494b6f966024be7d6dd260735c9e541e23572f26f37jeffhao } 495b6f966024be7d6dd260735c9e541e23572f26f37jeffhao if (checkMapped & !moveMapped) { 496b6f966024be7d6dd260735c9e541e23572f26f37jeffhao int checkRopReg = mapper.oldToNew(checkReg); 497b6f966024be7d6dd260735c9e541e23572f26f37jeffhao moveMapped = tryMapReg(moveRegSpec, checkRopReg, category); 498f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 499f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 500b6f966024be7d6dd260735c9e541e23572f26f37jeffhao // Map any unmapped registers to anything available 501b6f966024be7d6dd260735c9e541e23572f26f37jeffhao if (!moveMapped || !checkMapped) { 50238b61748553bd387bc36b6bd82a8667b6c5f5934jeffhao int ropReg = findNextUnreservedRopReg(paramRangeEnd, category); 503b6f966024be7d6dd260735c9e541e23572f26f37jeffhao ArrayList<RegisterSpec> ssaRegs = 504b6f966024be7d6dd260735c9e541e23572f26f37jeffhao new ArrayList<RegisterSpec>(2); 505b6f966024be7d6dd260735c9e541e23572f26f37jeffhao ssaRegs.add(moveRegSpec); 506b6f966024be7d6dd260735c9e541e23572f26f37jeffhao ssaRegs.add(checkRegSpec); 507f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 508b6f966024be7d6dd260735c9e541e23572f26f37jeffhao while (!tryMapRegs(ssaRegs, ropReg, category, false)) { 509b6f966024be7d6dd260735c9e541e23572f26f37jeffhao ropReg = findNextUnreservedRopReg(ropReg + 1, category); 510b6f966024be7d6dd260735c9e541e23572f26f37jeffhao } 511b6f966024be7d6dd260735c9e541e23572f26f37jeffhao } 512b6f966024be7d6dd260735c9e541e23572f26f37jeffhao 513b6f966024be7d6dd260735c9e541e23572f26f37jeffhao /* 514b6f966024be7d6dd260735c9e541e23572f26f37jeffhao * If source and result have a different mapping, insert a move so 515b6f966024be7d6dd260735c9e541e23572f26f37jeffhao * they can have the same mapping. Don't do this if the check cast 516b6f966024be7d6dd260735c9e541e23572f26f37jeffhao * is caught, since it will overwrite a potentially live value. 517b6f966024be7d6dd260735c9e541e23572f26f37jeffhao */ 518b6f966024be7d6dd260735c9e541e23572f26f37jeffhao boolean hasExceptionHandlers = 519b6f966024be7d6dd260735c9e541e23572f26f37jeffhao checkCastInsn.getOriginalRopInsn().getCatches().size() != 0; 520b6f966024be7d6dd260735c9e541e23572f26f37jeffhao int moveRopReg = mapper.oldToNew(moveReg); 521b6f966024be7d6dd260735c9e541e23572f26f37jeffhao int checkRopReg = mapper.oldToNew(checkReg); 522b6f966024be7d6dd260735c9e541e23572f26f37jeffhao if (moveRopReg != checkRopReg && !hasExceptionHandlers) { 523b6f966024be7d6dd260735c9e541e23572f26f37jeffhao ((NormalSsaInsn) checkCastInsn).changeOneSource(0, 524b6f966024be7d6dd260735c9e541e23572f26f37jeffhao insertMoveBefore(checkCastInsn, checkRegSpec)); 525b6f966024be7d6dd260735c9e541e23572f26f37jeffhao addMapping(checkCastInsn.getSources().get(0), moveRopReg); 526f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 527f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 528f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 529f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 530f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 5316ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao * Handles all phi instructions, trying to map them to a common register. 5326ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao */ 5336ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao private void handlePhiInsns() { 5346ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao for (PhiInsn insn : phiInsns) { 5356ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao processPhiInsn(insn); 5366ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao } 5376ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao } 5386ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao 5396ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao /** 54064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Maps all non-parameter, non-local variable registers. 541f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 542f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleNormalUnassociated() { 543f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSsaRegs = ssaMeth.getRegCount(); 54499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 545f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int ssaReg = 0; ssaReg < szSsaRegs; ssaReg++) { 546f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(ssaReg)) { 547f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // We already did this one 548f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 549f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 550f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 551f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec ssaSpec = getDefinitionSpecForSsaReg(ssaReg); 552f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 553f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaSpec == null) continue; 554f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 555f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = ssaSpec.getCategory(); 556f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Find a rop reg that does not interfere 55738b61748553bd387bc36b6bd82a8667b6c5f5934jeffhao int ropReg = findNextUnreservedRopReg(paramRangeEnd, category); 558f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (!canMapReg(ssaSpec, ropReg)) { 559f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropReg = findNextUnreservedRopReg(ropReg + 1, category); 560f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 561f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 562f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addMapping(ssaSpec, ropReg); 563f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 564f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 565f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 566f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 5672e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao * Checks to see if a list of SSA registers can all be mapped into 5682e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao * the same rop reg. Ignores registers that have already been mapped, 5692e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao * and checks the interference graph and ensures the range does not 5702e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao * cross the parameter range. 5712e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao * 5722e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao * @param specs {@code non-null;} SSA registers to check 5732e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao * @param ropReg {@code >=0;} rop register to check mapping to 5742e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao * @return {@code true} if all unmapped registers can be mapped 5752e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao */ 5762e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao private boolean canMapRegs(ArrayList<RegisterSpec> specs, int ropReg) { 5772e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao for (RegisterSpec spec : specs) { 5782e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao if (ssaRegsMapped.get(spec.getReg())) continue; 5792e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao if (!canMapReg(spec, ropReg)) return false; 5802e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao } 5812e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao return true; 5822e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao } 5832e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao 5842e31a719118f7b6c8d6c987d27532c29530cc9c8jeffhao /** 58599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Checks to see if {@code ssaSpec} can be mapped to 58699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code ropReg}. Checks interference graph and ensures 587f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the range does not cross the parameter range. 588f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 58999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaSpec {@code non-null;} SSA spec 590f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param ropReg prosepctive new-namespace reg 59164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return {@code true} if mapping is possible 592f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 593f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean canMapReg(RegisterSpec ssaSpec, int ropReg) { 594f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = ssaSpec.getCategory(); 595f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return !(spansParamRange(ropReg, category) 596f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project || mapper.interferes(ssaSpec, ropReg)); 597f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 59864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein 599f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 60064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Returns true if the specified rop register + category 60199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * will cross the boundry between the lower {@code paramWidth} 602f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers reserved for method params and the upper registers. We cannot 603f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * allocate a register that spans the param block and the normal block, 604f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * because we will be moving the param block to high registers later. 60564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 606f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param ssaReg register in new namespace 607f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param category width that the register will have 60864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return {@code true} in the case noted above 609f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 610f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean spansParamRange(int ssaReg, int category) { 611f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return ((ssaReg < paramRangeEnd) 612f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && ((ssaReg + category) > paramRangeEnd)); 613f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 614f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 615f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 616f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Analyze each instruction and find out all the local variable assignments 617f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and move-result-pseudo/invoke-range instrucitons. 618f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 619f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void analyzeInstructions() { 620f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaMeth.forEachInsn(new SsaInsn.Visitor() { 621f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 622f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitMoveInsn(NormalSsaInsn insn) { 623f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project processInsn(insn); 624f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 625f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 626f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 627f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitPhiInsn(PhiInsn insn) { 628f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project processInsn(insn); 629f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 630f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 631f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 632f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitNonMoveInsn(NormalSsaInsn insn) { 633f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project processInsn(insn); 634f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 635f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 636f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 637f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This method collects three types of instructions: 63864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 639f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1) Adds a local variable assignment to the 64099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code localVariables} map. 641f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 2) Add move-result-pseudo to the 64299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code moveResultPseudoInsns} list. 643f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 3) Add invoke-range to the 64499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code invokeRangeInsns} list. 645f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 64699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn that may represent a 64799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * local variable assignment 648f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 649f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void processInsn(SsaInsn insn) { 650f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec assignment; 651f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assignment = insn.getLocalAssignment(); 652f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 653f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (assignment != null) { 654f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LocalItem local = assignment.getLocalItem(); 655f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 65699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project ArrayList<RegisterSpec> regList 65799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project = localVariables.get(local); 658f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 659f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (regList == null) { 660f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regList = new ArrayList<RegisterSpec>(); 661f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project localVariables.put(local, regList); 662f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 663f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 664f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regList.add(assignment); 665f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 666f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 667f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn instanceof NormalSsaInsn) { 668f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn.getOpcode().getOpcode() == 669f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegOps.MOVE_RESULT_PSEUDO) { 670f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project moveResultPseudoInsns.add((NormalSsaInsn) insn); 671f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (Optimizer.getAdvice().requiresSourcesInOrder( 672f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn.getOriginalRopInsn().getOpcode(), 673f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn.getSources())) { 674f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project invokeRangeInsns.add((NormalSsaInsn) insn); 675f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 6766ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao } else if (insn instanceof PhiInsn) { 6776ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao phiInsns.add((PhiInsn) insn); 678f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 679f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 680f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 681f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project }); 682f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 683f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 684f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 68564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Adds a mapping from an SSA register to a rop register. 68699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@link #canMapReg} should have already been called. 687f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 68899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaSpec {@code non-null;} SSA register to map from 68964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param ropReg {@code >=0;} rop register to map to 690f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 691f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void addMapping(RegisterSpec ssaSpec, int ropReg) { 692f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ssaReg = ssaSpec.getReg(); 693f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 69464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // An assertion. 695f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(ssaReg) || !canMapReg(ssaSpec, ropReg)) { 696f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new RuntimeException( 697f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project "attempt to add invalid register mapping"); 698f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 699f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 700f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (DEBUG) { 701f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project System.out.printf("Add mapping s%d -> v%d c:%d\n", 70299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project ssaSpec.getReg(), ropReg, ssaSpec.getCategory()); 703f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 704f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 705f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = ssaSpec.getCategory(); 706f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project mapper.addMapping(ssaSpec.getReg(), ropReg, category); 707f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaRegsMapped.set(ssaReg); 708f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project usedRopRegs.set(ropReg, ropReg + category); 709f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 710f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 711f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 712f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 713f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Maps the source registers of the specified instruction such that they 71464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * will fall in a contiguous range in rop form. Moves are inserted as 715f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * necessary to allow the range to be allocated. 716f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 71799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn whos sources to process 718f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 719f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void adjustAndMapSourceRangeRange(NormalSsaInsn insn) { 72099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project int newRegStart = findRangeAndAdjust(insn); 721f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 722f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList sources = insn.getSources(); 723f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSources = sources.size(); 724f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int nextRopReg = newRegStart; 72599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 726f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szSources; i++) { 727f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec source = sources.get(i); 728f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sourceReg = source.getReg(); 729f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = source.getCategory(); 730f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int curRopReg = nextRopReg; 731f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project nextRopReg += category; 732f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 733f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(sourceReg)) { 734f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 735f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 736f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 737f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LocalItem localItem = getLocalItemForReg(sourceReg); 738f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addMapping(source, curRopReg); 739f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 740f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (localItem != null) { 741f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project markReserved(curRopReg, category); 742f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<RegisterSpec> similarRegisters 743f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = localVariables.get(localItem); 744f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 745f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSimilar = similarRegisters.size(); 746f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 74764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /* 74864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Try to map all SSA registers also associated with 74964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * this local. 75064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein */ 751f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int j = 0; j < szSimilar; j++) { 752f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec similarSpec = similarRegisters.get(j); 753f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int similarReg = similarSpec.getReg(); 754f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 75564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // Don't map anything that's also a source. 756f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (-1 != sources.indexOfRegister(similarReg)) { 757f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 758f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 759f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 76064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // Registers left unmapped will get handled later. 761f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project tryMapReg(similarSpec, curRopReg, category); 762f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 763f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 764f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 765f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 766f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 767f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 768f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Find a contiguous rop register range that fits the specified 769f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction's sources. First, try to center the range around 77064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * sources that have already been mapped to rop registers. If that fails, 771f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * just find a new contiguous range that doesn't interfere. 77264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 77399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} the insn whose sources need to 77499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * fit. Must be last insn in basic block. 77599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} rop register of start of range 776f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 777f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int findRangeAndAdjust(NormalSsaInsn insn) { 778f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList sources = insn.getSources(); 779f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSources = sources.size(); 780f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // the category for each source index 781f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int categoriesForIndex[] = new int[szSources]; 782f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int rangeLength = 0; 783f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 784f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Compute rangeLength and categoriesForIndex 785f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szSources; i++) { 786f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = sources.get(i).getCategory(); 787f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project categoriesForIndex[i] = category; 788f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project rangeLength += categoriesForIndex[i]; 789f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 790f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 79164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // the highest score of fits tried so far 792f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int maxScore = Integer.MIN_VALUE; 793f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // the high scoring range's start 794f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int resultRangeStart = -1; 795f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // by source index: set of sources needing moves in high scoring plan 796f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet resultMovesRequired = null; 797f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 798f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 799f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * First, go through each source that's already been mapped. Try 80064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * to center the range around the rop register this source is mapped 801f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to. 802f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 803f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int rangeStartOffset = 0; 804f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szSources; i++) { 805f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ssaCenterReg = sources.get(i).getReg(); 806f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 807f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (i != 0) { 808f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project rangeStartOffset -= categoriesForIndex[i - 1]; 809f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 810f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!ssaRegsMapped.get(ssaCenterReg)) { 811f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 812f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 813f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 814f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int rangeStart = mapper.oldToNew(ssaCenterReg) + rangeStartOffset; 815f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 816f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (rangeStart < 0 || spansParamRange(rangeStart, rangeLength)) { 817f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 818f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 819f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 820f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet curMovesRequired = new BitSet(szSources); 821f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 822f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int fitWidth 823f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = fitPlanForRange(rangeStart, insn, categoriesForIndex, 824f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project curMovesRequired); 825f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 826f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (fitWidth < 0) { 827f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 828f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 829f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 830f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int score = fitWidth - curMovesRequired.cardinality(); 831f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 832f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (score > maxScore) { 833f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project maxScore = score; 834f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultRangeStart = rangeStart; 835f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultMovesRequired = curMovesRequired; 836f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 837f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 838f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (fitWidth == rangeLength) { 839f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // We can't do any better than this, so stop here 840f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 841f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 842f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 843f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 844f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 845f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If we were unable to find a plan for a fit centered around 846f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * an already-mapped source, just try to find a range of 847f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers we can move the range into. 848f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 849f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 850f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (resultRangeStart == -1) { 851f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultMovesRequired = new BitSet(szSources); 852f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 853f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultRangeStart = findAnyFittingRange(insn, rangeLength, 854f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project categoriesForIndex, resultMovesRequired); 855f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 856f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 857f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 85864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Now, insert any moves required. 859f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 860f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 86141aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (int i = resultMovesRequired.nextSetBit(0); i >= 0; 86241aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein i = resultMovesRequired.nextSetBit(i+1)) { 86341aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein insn.changeOneSource(i, insertMoveBefore(insn, sources.get(i))); 864f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 865f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 866f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return resultRangeStart; 867f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 868f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 869f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 870f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Finds an unreserved range that will fit the sources of the 871f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * specified instruction. Does not bother trying to center the range 872f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * around an already-mapped source register; 873f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 87499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn to build range for 87564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param rangeLength {@code >=0;} length required in register units 87699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param categoriesForIndex {@code non-null;} indexed by source index; 87764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * the category for each source 87899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param outMovesRequired {@code non-null;} an output parameter indexed by 879f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * source index that will contain the set of sources which need 88064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * moves inserted 88164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return the rop register that starts the fitting range 882f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 883f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int findAnyFittingRange(NormalSsaInsn insn, int rangeLength, 884f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int[] categoriesForIndex, BitSet outMovesRequired) { 88538b61748553bd387bc36b6bd82a8667b6c5f5934jeffhao int rangeStart = paramRangeEnd; 886f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (true) { 887f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project rangeStart = findNextUnreservedRopReg(rangeStart, rangeLength); 888f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int fitWidth 889f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = fitPlanForRange(rangeStart, insn, 890f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project categoriesForIndex, outMovesRequired); 891f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 892f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (fitWidth >= 0) { 893f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 894f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 895f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project rangeStart++; 896f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project outMovesRequired.clear(); 897f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 898f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return rangeStart; 899f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 900f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 901f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 902f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Attempts to build a plan for fitting a range of sources into rop 903f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers. 904f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 90599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ropReg {@code >= 0;} rop reg that begins range 90699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn to plan range for 90799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param categoriesForIndex {@code non-null;} indexed by source index; 90864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * the category for each source 90999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param outMovesRequired {@code non-null;} an output parameter indexed by 910f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * source index that will contain the set of sources which need 91164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * moves inserted 912f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return the width of the fit that that does not involve added moves or 91364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * {@code -1} if "no fit possible" 914f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 915f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int fitPlanForRange(int ropReg, NormalSsaInsn insn, 916f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int[] categoriesForIndex, BitSet outMovesRequired) { 917f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList sources = insn.getSources(); 918f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSources = sources.size(); 919f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int fitWidth = 0; 920f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntSet liveOut = insn.getBlock().getLiveOutRegs(); 921f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList liveOutSpecs = ssaSetToSpecs(liveOut); 922f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 92364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // An SSA reg may only be mapped into a range once. 924f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet seen = new BitSet(ssaMeth.getRegCount()); 925f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 926f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szSources ; i++) { 927f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec ssaSpec = sources.get(i); 928f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ssaReg = ssaSpec.getReg(); 929f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = categoriesForIndex[i]; 930f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 931f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (i != 0) { 932f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropReg += categoriesForIndex[i-1]; 933f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 934f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 935f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(ssaReg) 936f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && mapper.oldToNew(ssaReg) == ropReg) { 93764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // This is a register that is already mapped appropriately. 938f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project fitWidth += category; 939f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (rangeContainsReserved(ropReg, category)) { 940f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project fitWidth = -1; 941f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 942f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (!ssaRegsMapped.get(ssaReg) 943f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && canMapReg(ssaSpec, ropReg) 944f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && !seen.get(ssaReg)) { 94564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // This is a register that can be mapped appropriately. 946f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project fitWidth += category; 947f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (!mapper.areAnyPinned(liveOutSpecs, ropReg, category) 948f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && !mapper.areAnyPinned(sources, ropReg, category)) { 949f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 95064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * This is a source that can be moved. We can insert a 95164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * move as long as: 95264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 95364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * * no SSA register pinned to the desired rop reg 95464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * is live out on the block 955f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 95664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * * no SSA register pinned to desired rop reg is 95764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * a source of this insn (since this may require 95864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * overlapping moves, which we can't presently handle) 959f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 960f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 961f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project outMovesRequired.set(i); 962f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 963f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project fitWidth = -1; 964f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 965f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 966f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 967f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project seen.set(ssaReg); 968f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 969f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return fitWidth; 970f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 971f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 972f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 973f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Converts a bit set of SSA registers into a RegisterSpecList containing 974f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the definition specs of all the registers. 975f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 97699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaSet {@code non-null;} set of SSA registers 977f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return list of RegisterSpecs as noted above 978f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 979f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList ssaSetToSpecs(IntSet ssaSet) { 980f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList result = new RegisterSpecList(ssaSet.elements()); 981f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 982f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntIterator iter = ssaSet.iterator(); 983f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 984f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i = 0; 985f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (iter.hasNext()) { 986f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.set(i++, getDefinitionSpecForSsaReg(iter.next())); 987f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 98864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein 989f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 990f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 991f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 992f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 99364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Gets a local item associated with an ssa register, if one exists. 994f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 99599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaReg {@code >= 0;} SSA register 99699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code null-ok;} associated local item or null 997f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 998f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private LocalItem getLocalItemForReg(int ssaReg) { 99941aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (Map.Entry<LocalItem, ArrayList<RegisterSpec>> entry : 100041aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein localVariables.entrySet()) { 100199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (RegisterSpec spec : entry.getValue()) { 1002f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (spec.getReg() == ssaReg) { 1003f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return entry.getKey(); 1004f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1005f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1006f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1007f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1008f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return null; 1009f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 10106ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao 10116ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao /** 10126ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao * Attempts to map the sources and result of a phi to a common register. 10131acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * Will try existing mappings first, from most to least common. If none 10141acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * of the registers have mappings yet, a new mapping is created. 10156ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao */ 10166ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao private void processPhiInsn(PhiInsn insn) { 10176ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao RegisterSpec result = insn.getResult(); 10186ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao int resultReg = result.getReg(); 10196ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao int category = result.getCategory(); 10201acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao 10211acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao RegisterSpecList sources = insn.getSources(); 10221acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao int sourcesSize = sources.size(); 10231acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao 10241acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao // List of phi sources / result that need mapping 10256ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao ArrayList<RegisterSpec> ssaRegs = new ArrayList<RegisterSpec>(); 10266ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao 10271acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao // Track how many times a particular mapping is found 10281acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao Multiset mapSet = new Multiset(sourcesSize + 1); 10291acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao 10301acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao /* 10311acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * If the result of the phi has an existing mapping, get it. 10321acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * Otherwise, add it to the list of regs that need mapping. 10331acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao */ 10346ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao if (ssaRegsMapped.get(resultReg)) { 10351acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao mapSet.add(mapper.oldToNew(resultReg)); 10361acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } else { 10371acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao ssaRegs.add(result); 10386ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao } 10396ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao 10401acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao for (int i = 0; i < sourcesSize; i++) { 10416ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao RegisterSpec source = sources.get(i); 10427debb9113af41a38a6f5ecbda1a2c28c5e5a17afjeffhao SsaInsn def = ssaMeth.getDefinitionForRegister(source.getReg()); 10437debb9113af41a38a6f5ecbda1a2c28c5e5a17afjeffhao RegisterSpec sourceDef = def.getResult(); 10447debb9113af41a38a6f5ecbda1a2c28c5e5a17afjeffhao int sourceReg = sourceDef.getReg(); 10456ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao 10461acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao /* 10471acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * If a source of the phi has an existing mapping, get it. 10481acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * Otherwise, add it to the list of regs that need mapping. 10491acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao */ 10506ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao if (ssaRegsMapped.get(sourceReg)) { 10511acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao mapSet.add(mapper.oldToNew(sourceReg)); 10521acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } else { 10537debb9113af41a38a6f5ecbda1a2c28c5e5a17afjeffhao ssaRegs.add(sourceDef); 10541acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } 10551acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } 10561acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao 10571acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao // Try all existing mappings, with the most common ones first 10581acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao for (int i = 0; i < mapSet.getSize(); i++) { 10591acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao int maxReg = mapSet.getAndRemoveHighestCount(); 10601acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao tryMapRegs(ssaRegs, maxReg, category, false); 10611acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } 10621acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao 10631acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao // Map any remaining unmapped regs with whatever fits 106438b61748553bd387bc36b6bd82a8667b6c5f5934jeffhao int mapReg = findNextUnreservedRopReg(paramRangeEnd, category); 10651acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao while (!tryMapRegs(ssaRegs, mapReg, category, false)) { 10661acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao mapReg = findNextUnreservedRopReg(mapReg + 1, category); 10671acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } 10681acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } 10696ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao 10701acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao // A set that tracks how often elements are added to it. 10711acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao private static class Multiset { 10721acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao private final int[] reg; 10731acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao private final int[] count; 10741acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao private int size; 10751acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao 10761acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao /** 10771acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * Constructs an instance. 10781acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * 10791acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * @param maxSize the maximum distinct elements the set may have 10801acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao */ 10811acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao public Multiset(int maxSize) { 10821acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao reg = new int[maxSize]; 10831acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao count = new int[maxSize]; 10841acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao size = 0; 10851acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } 10861acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao 10871acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao /** 10881acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * Adds an element to the set. 10891acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * 10901acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * @param element element to add 10911acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao */ 10921acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao public void add(int element) { 10931acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao for (int i = 0; i < size; i++) { 10941acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao if (reg[i] == element) { 10951acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao count[i]++; 10966ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao return; 10976ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao } 10981acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } 10991acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao 11001acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao reg[size] = element; 11011acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao count[size] = 1; 11021acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao size++; 11031acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } 11046ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao 11051acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao /** 11061acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * Searches the set for the element that has been added the most. 11071acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * In the case of a tie, the element that was added first is returned. 11081acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * Then, it clears the count on that element. The size of the set 11091acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * remains unchanged. 11101acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * 11111acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * @return element with the highest count 11121acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao */ 11131acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao public int getAndRemoveHighestCount() { 11141acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao int maxIndex = -1; 11151acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao int maxReg = -1; 11161acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao int maxCount = 0; 11171acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao 11181acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao for (int i = 0; i < size; i++) { 11191acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao if (maxCount < count[i]) { 11201acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao maxIndex = i; 11211acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao maxReg = reg[i]; 11221acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao maxCount = count[i]; 11231acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao } 11246ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao } 11251acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao 11261acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao count[maxIndex] = 0; 11271acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao return maxReg; 11286ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao } 11296ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao 11301acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao /** 11311acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * Gets the number of distinct elements in the set. 11321acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * 11331acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao * @return size of the set 11341acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao */ 11351acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao public int getSize() { 11361acb3f560b45df68d5acdcb2759de1f78ef5da7cjeffhao return size; 11376ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao } 11386ca2505711b24a91385c6bf46dbef5c404dcf65fjeffhao } 1139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 1140