FirstFitLocalCombiningAllocator.java revision 99409883d9c4c0ffb49b070ce307bb33a9dfe9f1
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 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** indexed by SSA reg; the set of SSA regs we've mapped */ 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final BitSet ssaRegsMapped; 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** Register mapper which will be our result */ 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final InterferenceRegisterMapper mapper; 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** end of rop registers range (starting at 0) reserved for parameters. */ 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final int paramRangeEnd; 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** set of Rop registers reserved for parameters or local variables. */ 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final BitSet reservedRopRegs; 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** set of Rop registers that have been used by anything.*/ 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final BitSet usedRopRegs; 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** true if converter should take steps to minimize rop-form registers*/ 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final boolean minimizeRegisters; 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs instance. 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 7699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaMeth {@code non-null;} method to process 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param interference non-null interference graph for SSA registers 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param minimizeRegisters true if converter should take steps to 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * minimize rop-form registers 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public FirstFitLocalCombiningAllocator( 8299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project SsaMethod ssaMeth, InterferenceGraph interference, 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean minimizeRegisters) { 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project super(ssaMeth, interference); 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaRegsMapped = new BitSet(ssaMeth.getRegCount()); 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project mapper = new InterferenceRegisterMapper( 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project interference, ssaMeth.getRegCount()); 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.minimizeRegisters = minimizeRegisters; 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Reserve space for the params at the bottom of the register 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * space. Later, we'll flip the params to the end of the register 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * space. 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project paramRangeEnd = ssaMeth.getParamWidth(); 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reservedRopRegs = new BitSet(paramRangeEnd * 2); 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reservedRopRegs.set(0, paramRangeEnd); 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project usedRopRegs = new BitSet(paramRangeEnd * 2); 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project localVariables = new TreeMap<LocalItem, ArrayList<RegisterSpec>>(); 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project moveResultPseudoInsns = new ArrayList<NormalSsaInsn>(); 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project invokeRangeInsns = new ArrayList<NormalSsaInsn>(); 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project @Override 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public boolean wantsParamsMovedHigh() { 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project @Override 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public RegisterMapper allocateRegisters() { 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project analyzeInstructions(); 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (DEBUG) { 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project printLocalVars(); 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 12599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (DEBUG) System.out.println("--->Mapping local-associated params"); 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project handleLocalAssociatedParams(); 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 12899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (DEBUG) System.out.println("--->Mapping other params"); 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project handleUnassociatedParameters(); 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 13199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (DEBUG) System.out.println("--->Mapping invoke-range"); 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project handleInvokeRangeInsns(); 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 13499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (DEBUG) { 13599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project System.out.println("--->Mapping local-associated non-params"); 13699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project } 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project handleLocalAssociatedOther(); 138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 13999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (DEBUG) System.out.println("--->Mapping check-cast results"); 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project handleCheckCastResults(); 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 14299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (DEBUG) System.out.println("--->Mapping others"); 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project handleNormalUnassociated(); 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return mapper; 146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Dumps local variable table to stdout for debugging. 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void printLocalVars() { 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project System.out.println("Printing local vars"); 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (Map.Entry<LocalItem, ArrayList<RegisterSpec>> e: 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project localVariables.entrySet()) { 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project StringBuilder regs = new StringBuilder(); 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regs.append('{'); 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regs.append(' '); 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for(RegisterSpec reg: e.getValue()) { 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regs.append('v'); 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regs.append(reg.getReg()); 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regs.append(' '); 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regs.append('}'); 165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project System.out.printf("Local: %s Registers: %s\n", e.getKey(), regs); 166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Maps all local-associated parameters to Rop registers. 171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleLocalAssociatedParams() { 17399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (ArrayList<RegisterSpec> ssaRegs : localVariables.values()) { 174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = ssaRegs.size(); 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int paramIndex = -1; 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int paramCategory = 0; 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // First, find out if this local variable is a parameter 17999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (int i = 0; i < sz; i++) { 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec ssaSpec = ssaRegs.get(i); 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ssaReg = ssaSpec.getReg(); 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project paramIndex = getParameterIndexForReg(ssaReg); 184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (paramIndex >= 0) { 186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project paramCategory = ssaSpec.getCategory(); 187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addMapping(ssaSpec, paramIndex); 188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 190f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (paramIndex < 0) { 193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // this local wasn't a parameter 194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Any remaining local-associated registers will be mapped later 198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project tryMapRegs(ssaRegs, paramIndex, paramCategory, true); 199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 200f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 201f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the parameter index for SSA registers that are method parameters. 204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * -1 is returned for non-parameter registers. 205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 20699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaReg {@code >=0;} SSA register to look up 207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return parameter index or -1 if not a parameter 208f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int getParameterIndexForReg(int ssaReg) { 210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn defInsn = ssaMeth.getDefinitionForRegister(ssaReg); 211f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (defInsn == null) { 212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return -1; 213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Rop opcode = defInsn.getOpcode(); 216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 217f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // opcode == null for phi insns 218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (opcode != null && opcode.getOpcode() == RegOps.MOVE_PARAM) { 219f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project CstInsn origInsn = (CstInsn) defInsn.getOriginalRopInsn(); 220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return ((CstInteger) origInsn.getConstant()).getValue(); 221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 222f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return -1; 224f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 225f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 22799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Maps all local-associated registers that are not parameters. 22899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Tries to find an unreserved range that's wide enough for all of 22999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * the SSA registers, and then tries to map them all to that 23099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * range. If not all fit, a new range is tried until all registers 23199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * have been fit. 232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleLocalAssociatedOther() { 23499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (ArrayList<RegisterSpec> specs : localVariables.values()) { 235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ropReg = 0; 236f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean done; 238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project do { 239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int maxCategory = 1; 240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 241f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // compute max category for remaining unmapped registers 242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = specs.size(); 243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec ssaSpec = specs.get(i); 245f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = ssaSpec.getCategory(); 246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!ssaRegsMapped.get(ssaSpec.getReg()) 247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && category > maxCategory) { 248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project maxCategory = category; 249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropReg = findRopRegForLocal(ropReg, maxCategory); 253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project done = tryMapRegs(specs, ropReg, maxCategory, true); 255f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Increment for next call to findNext 257f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropReg++; 258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } while (!done); 259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 262f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 263f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Tries to map a list of SSA registers into the a rop reg, marking 264f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * used rop space as reserved. SSA registers that don't fit are left 265f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * unmapped. 266f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 26799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param specs {@code non-null;} SSA registers to attempt to map 26899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ropReg {@code >=0;} rop register to map to 269f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param maxAllowedCategory 1 or 2, maximum category allowed in mapping. 270f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param markReserved do so if true 271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if all registers wew mapped, false if some remain unmapped. 272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean tryMapRegs( 274f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<RegisterSpec> specs, int ropReg, 275f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int maxAllowedCategory, boolean markReserved) { 276f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean remaining = false; 27799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (RegisterSpec spec : specs) { 278f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(spec.getReg())) { 279f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 280f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 281f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean succeeded; 283f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project succeeded = tryMapReg(spec, ropReg, maxAllowedCategory); 284f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project remaining = !succeeded || remaining; 285f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (succeeded && markReserved) { 286f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // This only needs to be called once really with 287f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // the widest category used, but <shrug> 288f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project markReserved(ropReg, spec.getCategory()); 289f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 290f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 291f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return !remaining; 292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 293f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 294f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 295f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Tries to map an SSA register to a rop register. 296f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 29799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaSpec {@code non-null;} SSA register 29899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ropReg {@code >=0;} rop register 299f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param maxAllowedCategory 1 or 2, the maximum category that the SSA 300f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * register is allowed to be. 301f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if map succeeded, false if not. 302f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 303f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean tryMapReg(RegisterSpec ssaSpec, int ropReg, 304f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int maxAllowedCategory) { 305f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaSpec.getCategory() <= maxAllowedCategory 306f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && !ssaRegsMapped.get(ssaSpec.getReg()) 307f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && canMapReg(ssaSpec, ropReg)) { 308f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addMapping(ssaSpec, ropReg); 309f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 310f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 311f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 312f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 313f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 314f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 315f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 316f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Marks a range of Rop registers as "reserved for a local variable" 317f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 31899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ropReg {@code >= 0;} rop register to reserve 31999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param category {@code > 0;} width to reserve 320f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 321f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void markReserved(int ropReg, int category) { 322f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reservedRopRegs.set(ropReg, ropReg + category, true); 323f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 326f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Checks to see if any Rop registers in the specified range are reserved 327f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * for local variables or parameters 328f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 32999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ropRangeStart {@code >= 0;} lowest Rop register 33099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param width {@code > 0;} number of Rop registers in range. 331f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if any register in range is marked reserved 332f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 333f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean rangeContainsReserved(int ropRangeStart, int width) { 334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = ropRangeStart; i < (ropRangeStart + width); i++) { 335f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (reservedRopRegs.get(i)) { 336f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 337f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 338f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 339f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 340f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 341f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 342f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 343f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns true if given rop register represents the "this" pointer 344f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * for a non-static method 345f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 346f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param startReg rop register 347f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if the "this" pointer is located here. 348f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 349f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean isThisPointerReg(int startReg) { 350f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // "this" is always the first parameter 351f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return startReg == 0 && !ssaMeth.isStatic(); 352f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 353f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 354f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 355f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Finds a range of unreserved Rop registers. 356f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 35799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param startReg {@code >= 0;} a Rop register to start the search at 35899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param width {@code > 0;} the width, in registers, required. 35999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} start of available register range. 360f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 361f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int findNextUnreservedRopReg(int startReg, int width) { 362f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (minimizeRegisters && !isThisPointerReg(startReg)) { 363f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return startReg; 364f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 365f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 366f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int reg; 367f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 368f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reg = reservedRopRegs.nextClearBit(startReg); 369f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 370f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (true) { 371f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i = 1; 372f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 373f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (i < width && !reservedRopRegs.get(reg + i)) { 374f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project i++; 375f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 376f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 377f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (i == width) { 378f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return reg; 379f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 380f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 381f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reg = reservedRopRegs.nextClearBit(reg + i); 382f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 383f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 384f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 385f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 386f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Finds a range of rop regs that can be used for local variables. 38799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * If {@code MIX_LOCALS_AND_OTHER} is false, this means any 388f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * rop register that has not yet been used. 389f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 39099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param startReg {@code >= 0;} a Rop register to start the search at 39199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param width {@code > 0;} the width, in registers, required. 39299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} start of available register range. 393f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 394f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int findRopRegForLocal(int startReg, int width) { 395f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (minimizeRegisters && !isThisPointerReg(startReg)) { 396f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return startReg; 397f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 398f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 399f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int reg; 400f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 401f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reg = usedRopRegs.nextClearBit(startReg); 402f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 403f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (true) { 404f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i = 1; 405f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 406f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (i < width && !usedRopRegs.get(reg + i)) { 407f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project i++; 408f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 409f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 410f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (i == width) { 411f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return reg; 412f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 413f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 414f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reg = usedRopRegs.nextClearBit(reg + i); 415f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 416f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 417f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 418f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 419f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Maps any parameter that isn't local-associated, which can happen 420f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * in the case where there is no java debug info. 421f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 422f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleUnassociatedParameters() { 423f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSsaRegs = ssaMeth.getRegCount(); 42499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 425f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int ssaReg = 0; ssaReg < szSsaRegs; ssaReg++) { 426f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(ssaReg)) { 427f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // We already did this one above 428f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 429f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 430f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 431f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int paramIndex = getParameterIndexForReg(ssaReg); 432f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 433f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec ssaSpec = getDefinitionSpecForSsaReg(ssaReg); 434f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (paramIndex >= 0) { 435f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addMapping(ssaSpec, paramIndex); 436f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 437f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 438f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 439f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 440f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 441f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Handles all insns that want a register range for their sources. 442f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 443f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleInvokeRangeInsns() { 44499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for(NormalSsaInsn insn : invokeRangeInsns) { 445f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project adjustAndMapSourceRangeRange(insn); 446f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 447f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 448f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 449f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 450f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Handles check cast results to reuse the same source register if possible 451f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 452f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleCheckCastResults() { 453f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (NormalSsaInsn insn : moveResultPseudoInsns) { 454f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec moveRegSpec = insn.getResult(); 455f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int moveReg = moveRegSpec.getReg(); 456f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet predBlocks = insn.getBlock().getPredecessors(); 457f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 458f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Expect one predecessor block only 459f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (predBlocks.cardinality() != 1) { 460f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 461f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 462f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 463f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock predBlock = 464f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaMeth.getBlocks().get(predBlocks.nextSetBit(0)); 465f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<SsaInsn> insnList = predBlock.getInsns(); 466f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 467f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 468f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If the predecessor block has a check-cast, it will be the last 469f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction 470f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 471f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn checkCastInsn = insnList.get(insnList.size() - 1); 472f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (checkCastInsn.getOpcode().getOpcode() != RegOps.CHECK_CAST) { 473f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 474f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 475f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 476f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec checkRegSpec = checkCastInsn.getSources().get(0); 477f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int checkReg = checkRegSpec.getReg(); 478f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 479f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Assume none of the register is mapped yet 480f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ropReg = 0; 481f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 482f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 483f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * See if either register is already mapped. Most likely the move 484f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * result will be mapped already since the cast result is stored 485f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * in a local variable. 486f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 487f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(moveReg)) { 488f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropReg = mapper.oldToNew(moveReg); 489f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (ssaRegsMapped.get(checkReg)) { 490f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropReg = mapper.oldToNew(checkReg); 491f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 492f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 493f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<RegisterSpec> ssaRegs = new ArrayList<RegisterSpec>(2); 494f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaRegs.add(moveRegSpec); 495f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaRegs.add(checkRegSpec); 496f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = checkRegSpec.getCategory(); 497f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 498f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (!tryMapRegs(ssaRegs, ropReg, category, false)) { 499f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropReg = findNextUnreservedRopReg(ropReg + 1, category); 500f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 501f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 502f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 503f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 504f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 505f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Maps all non-parameter, non-local variable 506f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers. 507f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 508f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleNormalUnassociated() { 509f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSsaRegs = ssaMeth.getRegCount(); 51099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 511f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int ssaReg = 0; ssaReg < szSsaRegs; ssaReg++) { 512f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(ssaReg)) { 513f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // We already did this one 514f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 515f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 516f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 517f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec ssaSpec = getDefinitionSpecForSsaReg(ssaReg); 518f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 519f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaSpec == null) continue; 520f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 521f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = ssaSpec.getCategory(); 522f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Find a rop reg that does not interfere 523f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ropReg = findNextUnreservedRopReg(0, category); 524f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (!canMapReg(ssaSpec, ropReg)) { 525f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropReg = findNextUnreservedRopReg(ropReg + 1, category); 526f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 527f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 528f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addMapping(ssaSpec, ropReg); 529f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 530f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 531f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 532f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 53399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Checks to see if {@code ssaSpec} can be mapped to 53499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code ropReg}. Checks interference graph and ensures 535f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the range does not cross the parameter range. 536f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 53799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaSpec {@code non-null;} SSA spec 538f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param ropReg prosepctive new-namespace reg 539f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if mapping is possible 540f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 541f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean canMapReg(RegisterSpec ssaSpec, int ropReg) { 542f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = ssaSpec.getCategory(); 543f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return !(spansParamRange(ropReg, category) 544f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project || mapper.interferes(ssaSpec, ropReg)); 545f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 546f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 547f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 548f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns true if the specified Rop register + category 54999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * will cross the boundry between the lower {@code paramWidth} 550f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers reserved for method params and the upper registers. We cannot 551f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * allocate a register that spans the param block and the normal block, 552f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * because we will be moving the param block to high registers later. 553f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 554f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param ssaReg register in new namespace 555f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param category width that the register will have 556f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true in the case noted above. 557f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 558f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean spansParamRange(int ssaReg, int category) { 559f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return ((ssaReg < paramRangeEnd) 560f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && ((ssaReg + category) > paramRangeEnd)); 561f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 562f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 563f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 564f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Analyze each instruction and find out all the local variable assignments 565f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and move-result-pseudo/invoke-range instrucitons. 566f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 567f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void analyzeInstructions() { 568f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaMeth.forEachInsn(new SsaInsn.Visitor() { 569f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 570f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitMoveInsn(NormalSsaInsn insn) { 571f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project processInsn(insn); 572f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 573f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 574f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 575f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitPhiInsn(PhiInsn insn) { 576f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project processInsn(insn); 577f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 578f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 579f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 580f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitNonMoveInsn(NormalSsaInsn insn) { 581f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project processInsn(insn); 582f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 583f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 584f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 585f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This method collects three types of instructions: 586f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1) Adds a local variable assignment to the 58799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code localVariables} map. 588f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 2) Add move-result-pseudo to the 58999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code moveResultPseudoInsns} list. 590f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 3) Add invoke-range to the 59199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code invokeRangeInsns} list. 592f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 59399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn that may represent a 59499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * local variable assignment 595f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 596f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void processInsn(SsaInsn insn) { 597f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec assignment; 598f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assignment = insn.getLocalAssignment(); 599f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 600f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (assignment != null) { 601f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LocalItem local = assignment.getLocalItem(); 602f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 60399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project ArrayList<RegisterSpec> regList 60499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project = localVariables.get(local); 605f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 606f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (regList == null) { 607f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regList = new ArrayList<RegisterSpec>(); 608f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project localVariables.put(local, regList); 609f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 610f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 611f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regList.add(assignment); 612f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 613f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 614f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn instanceof NormalSsaInsn) { 615f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn.getOpcode().getOpcode() == 616f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegOps.MOVE_RESULT_PSEUDO) { 617f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project moveResultPseudoInsns.add((NormalSsaInsn) insn); 618f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (Optimizer.getAdvice().requiresSourcesInOrder( 619f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn.getOriginalRopInsn().getOpcode(), 620f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn.getSources())) { 621f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project invokeRangeInsns.add((NormalSsaInsn) insn); 622f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 623f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 624f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 625f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 626f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project }); 627f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 628f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 629f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 63099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Adds a mapping from an SSA register to a Rop register. 63199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@link #canMapReg} should have already been called. 632f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 63399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaSpec {@code non-null;} SSA register to map from 63499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ropReg {@code >=0;} Rop register to map to 635f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 636f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void addMapping(RegisterSpec ssaSpec, int ropReg) { 637f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ssaReg = ssaSpec.getReg(); 638f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 639f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // An assertion 640f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(ssaReg) || !canMapReg(ssaSpec, ropReg)) { 641f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new RuntimeException( 642f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project "attempt to add invalid register mapping"); 643f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 644f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 645f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (DEBUG) { 646f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project System.out.printf("Add mapping s%d -> v%d c:%d\n", 64799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project ssaSpec.getReg(), ropReg, ssaSpec.getCategory()); 648f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 649f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 650f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = ssaSpec.getCategory(); 651f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project mapper.addMapping(ssaSpec.getReg(), ropReg, category); 652f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaRegsMapped.set(ssaReg); 653f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project usedRopRegs.set(ropReg, ropReg + category); 654f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 655f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 656f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 657f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 658f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Maps the source registers of the specified instruction such that they 659f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * will fall in a contiguous range in Rop form. Moves are inserted as 660f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * necessary to allow the range to be allocated. 661f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 66299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn whos sources to process 663f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 664f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void adjustAndMapSourceRangeRange(NormalSsaInsn insn) { 66599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project int newRegStart = findRangeAndAdjust(insn); 666f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 667f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList sources = insn.getSources(); 668f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSources = sources.size(); 669f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int nextRopReg = newRegStart; 67099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 671f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szSources; i++) { 672f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec source = sources.get(i); 673f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sourceReg = source.getReg(); 674f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = source.getCategory(); 675f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int curRopReg = nextRopReg; 676f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project nextRopReg += category; 677f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 678f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(sourceReg)) { 679f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 680f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 681f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 682f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LocalItem localItem = getLocalItemForReg(sourceReg); 683f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addMapping(source, curRopReg); 684f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 685f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (localItem != null) { 686f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project markReserved(curRopReg, category); 687f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<RegisterSpec> similarRegisters 688f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = localVariables.get(localItem); 689f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 690f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSimilar = similarRegisters.size(); 691f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 692f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Try to map all SSA registers also associated with this local 693f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int j = 0; j < szSimilar; j++) { 694f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec similarSpec = similarRegisters.get(j); 695f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int similarReg = similarSpec.getReg(); 696f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 697f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // ...and don't map anything that's also a source... 698f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (-1 != sources.indexOfRegister(similarReg)) { 699f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 700f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 701f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 702f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Registers left unmapped will get handled later 703f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project tryMapReg(similarSpec, curRopReg, category); 704f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 705f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 706f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 707f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 708f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 709f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 710f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Find a contiguous rop register range that fits the specified 711f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction's sources. First, try to center the range around 712f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * sources that have already been mapped to Rop registers. If that fails, 713f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * just find a new contiguous range that doesn't interfere. 71499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * 71599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} the insn whose sources need to 71699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * fit. Must be last insn in basic block. 71799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} rop register of start of range 718f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 719f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int findRangeAndAdjust(NormalSsaInsn insn) { 720f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList sources = insn.getSources(); 721f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSources = sources.size(); 722f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // the category for each source index 723f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int categoriesForIndex[] = new int[szSources]; 724f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int rangeLength = 0; 725f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 726f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Compute rangeLength and categoriesForIndex 727f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szSources; i++) { 728f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = sources.get(i).getCategory(); 729f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project categoriesForIndex[i] = category; 730f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project rangeLength += categoriesForIndex[i]; 731f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 732f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 733f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // The highest score of fits tried so far 734f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int maxScore = Integer.MIN_VALUE; 735f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // the high scoring range's start 736f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int resultRangeStart = -1; 737f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // by source index: set of sources needing moves in high scoring plan 738f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet resultMovesRequired = null; 739f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 740f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 741f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * First, go through each source that's already been mapped. Try 742f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to center the range around the Rop register this source is mapped 743f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to. 744f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 745f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int rangeStartOffset = 0; 746f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szSources; i++) { 747f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ssaCenterReg = sources.get(i).getReg(); 748f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 749f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (i != 0) { 750f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project rangeStartOffset -= categoriesForIndex[i - 1]; 751f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 752f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!ssaRegsMapped.get(ssaCenterReg)) { 753f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 754f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 755f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 756f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int rangeStart = mapper.oldToNew(ssaCenterReg) + rangeStartOffset; 757f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 758f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (rangeStart < 0 || spansParamRange(rangeStart, rangeLength)) { 759f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 760f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 761f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 762f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet curMovesRequired = new BitSet(szSources); 763f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 764f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int fitWidth 765f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = fitPlanForRange(rangeStart, insn, categoriesForIndex, 766f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project curMovesRequired); 767f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 768f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (fitWidth < 0) { 769f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 770f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 771f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 772f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int score = fitWidth - curMovesRequired.cardinality(); 773f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 774f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (score > maxScore) { 775f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project maxScore = score; 776f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultRangeStart = rangeStart; 777f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultMovesRequired = curMovesRequired; 778f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 779f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 780f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (fitWidth == rangeLength) { 781f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // We can't do any better than this, so stop here 782f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 783f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 784f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 785f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 786f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 787f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If we were unable to find a plan for a fit centered around 788f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * an already-mapped source, just try to find a range of 789f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers we can move the range into. 790f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 791f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 792f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (resultRangeStart == -1) { 793f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultMovesRequired = new BitSet(szSources); 794f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 795f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultRangeStart = findAnyFittingRange(insn, rangeLength, 796f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project categoriesForIndex, resultMovesRequired); 797f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 798f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 799f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 800f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Now, insert any moves required 801f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 802f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 803f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = resultMovesRequired.nextSetBit(0); i >= 0 804f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ; i = resultMovesRequired.nextSetBit(i+1)) { 805f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn.changeOneSource(i, 806f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insertMoveBefore(insn, sources.get(i))); 807f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 808f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 809f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return resultRangeStart; 810f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 811f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 812f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 813f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Finds an unreserved range that will fit the sources of the 814f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * specified instruction. Does not bother trying to center the range 815f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * around an already-mapped source register; 816f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 81799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn to build range for 81899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param rangeLength {@code >=0;} length required in register units. 81999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param categoriesForIndex {@code non-null;} indexed by source index; 820f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the category for each source. 82199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param outMovesRequired {@code non-null;} an output parameter indexed by 822f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * source index that will contain the set of sources which need 823f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * moves inserted. 824f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return the rop register that starts the fitting range. 825f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 826f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int findAnyFittingRange(NormalSsaInsn insn, int rangeLength, 827f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int[] categoriesForIndex, BitSet outMovesRequired) { 828f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int rangeStart = 0; 829f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (true) { 830f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project rangeStart = findNextUnreservedRopReg(rangeStart, rangeLength); 831f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int fitWidth 832f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = fitPlanForRange(rangeStart, insn, 833f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project categoriesForIndex, outMovesRequired); 834f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 835f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (fitWidth >= 0) { 836f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 837f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 838f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project rangeStart++; 839f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project outMovesRequired.clear(); 840f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 841f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return rangeStart; 842f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 843f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 844f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 845f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Attempts to build a plan for fitting a range of sources into rop 846f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers. 847f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 84899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ropReg {@code >= 0;} rop reg that begins range 84999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn to plan range for 85099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param categoriesForIndex {@code non-null;} indexed by source index; 851f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the category for each source. 85299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param outMovesRequired {@code non-null;} an output parameter indexed by 853f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * source index that will contain the set of sources which need 854f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * moves inserted. 855f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return the width of the fit that that does not involve added moves or 856f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * -1 if "no fit possible" 857f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 858f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int fitPlanForRange(int ropReg, NormalSsaInsn insn, 859f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int[] categoriesForIndex, BitSet outMovesRequired) { 860f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList sources = insn.getSources(); 861f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSources = sources.size(); 862f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int fitWidth = 0; 863f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntSet liveOut = insn.getBlock().getLiveOutRegs(); 864f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList liveOutSpecs = ssaSetToSpecs(liveOut); 865f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 866f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // An SSA reg may only be mapped into a range once 867f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet seen = new BitSet(ssaMeth.getRegCount()); 868f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 869f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szSources ; i++) { 870f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec ssaSpec = sources.get(i); 871f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ssaReg = ssaSpec.getReg(); 872f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = categoriesForIndex[i]; 873f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 874f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (i != 0) { 875f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropReg += categoriesForIndex[i-1]; 876f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 877f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 878f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(ssaReg) 879f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && mapper.oldToNew(ssaReg) == ropReg) { 880f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // A register already mapped appropriately 881f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project fitWidth += category; 882f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (rangeContainsReserved(ropReg, category)) { 883f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project fitWidth = -1; 884f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 885f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (!ssaRegsMapped.get(ssaReg) 886f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && canMapReg(ssaSpec, ropReg) 887f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && !seen.get(ssaReg)) { 888f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // A register that can be mapped appropriately 889f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project fitWidth += category; 890f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (!mapper.areAnyPinned(liveOutSpecs, ropReg, category) 891f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && !mapper.areAnyPinned(sources, ropReg, category)) { 892f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 893f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * A source that can be moved 894f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * We can insert a move as long as: 895f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 896f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * - no SSA register pinned to the desired rop reg 897f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * is live out on the block 898f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * - no SSA register pinned to desired rop reg is 899f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * a source of this insn (since this may require 900f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * overlapping moves, which we can't presently handle) 901f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 902f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 903f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project outMovesRequired.set(i); 904f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 905f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project fitWidth = -1; 906f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 907f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 908f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 909f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project seen.set(ssaReg); 910f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 911f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return fitWidth; 912f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 913f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 914f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 915f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Converts a bit set of SSA registers into a RegisterSpecList containing 916f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the definition specs of all the registers. 917f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 91899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaSet {@code non-null;} set of SSA registers 919f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return list of RegisterSpecs as noted above 920f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 921f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList ssaSetToSpecs(IntSet ssaSet) { 922f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList result = new RegisterSpecList(ssaSet.elements()); 923f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 924f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntIterator iter = ssaSet.iterator(); 925f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 926f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i = 0; 927f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (iter.hasNext()) { 928f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.set(i++, getDefinitionSpecForSsaReg(iter.next())); 929f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 930f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 931f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 932f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 933f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 934f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 935f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets a local item associated with an ssa register, if one exists 936f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 93799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaReg {@code >= 0;} SSA register 93899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code null-ok;} associated local item or null 939f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 940f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private LocalItem getLocalItemForReg(int ssaReg) { 941f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for(Map.Entry<LocalItem, ArrayList<RegisterSpec>> entry: 942f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project localVariables.entrySet()) { 943f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 94499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (RegisterSpec spec : entry.getValue()) { 945f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (spec.getReg() == ssaReg) { 946f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return entry.getKey(); 947f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 948f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 949f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 950f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 951f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return null; 952f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 953f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 954