FirstFitLocalCombiningAllocator.java revision 64986d4f1b50a5f3a12e05eb179ae9ad555814e7
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 6164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /** 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 6464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /** set of rop registers reserved for parameters or local variables */ 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final BitSet reservedRopRegs; 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 6764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /** set of rop registers that have been used by anything */ 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final BitSet usedRopRegs; 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 7064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /** 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(); 13364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein 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"); 15341aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein 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(' '); 15941aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein 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 /** 17064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 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 17864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // 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) { 19364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // This local wasn't a parameter. 194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 19764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // 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. 20464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * {@code -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 20764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return parameter index or {@code -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 } 21464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein 215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Rop opcode = defInsn.getOpcode(); 216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 21764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // 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 /** 22764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 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 24164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // 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 25664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // 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 26964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param maxAllowedCategory {@code 1..2;} maximum category 27064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * allowed in mapping. 27164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param markReserved do so if {@code true} 27264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return {@code true} if all registers were mapped, {@code false} 27364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * if some remain unmapped 274f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 275f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean tryMapRegs( 276f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<RegisterSpec> specs, int ropReg, 277f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int maxAllowedCategory, boolean markReserved) { 278f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean remaining = false; 27999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (RegisterSpec spec : specs) { 280f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(spec.getReg())) { 281f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 283f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 284f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean succeeded; 285f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project succeeded = tryMapReg(spec, ropReg, maxAllowedCategory); 286f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project remaining = !succeeded || remaining; 287f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (succeeded && markReserved) { 288f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // This only needs to be called once really with 289f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // the widest category used, but <shrug> 290f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project markReserved(ropReg, spec.getCategory()); 291f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 293f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return !remaining; 294f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 295f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 296f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 297f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Tries to map an SSA register to a rop register. 298f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 29999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaSpec {@code non-null;} SSA register 30099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ropReg {@code >=0;} rop register 30164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param maxAllowedCategory {@code 1..2;} the maximum category 30264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * that the SSA register is allowed to be 30364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return {@code true} if map succeeded, {@code false} if not 304f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 305f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean tryMapReg(RegisterSpec ssaSpec, int ropReg, 306f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int maxAllowedCategory) { 307f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaSpec.getCategory() <= maxAllowedCategory 308f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && !ssaRegsMapped.get(ssaSpec.getReg()) 309f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && canMapReg(ssaSpec, ropReg)) { 310f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addMapping(ssaSpec, ropReg); 311f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 312f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 313f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 314f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 315f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 316f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 317f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 31864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Marks a range of rop registers as "reserved for a local variable." 319f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 32099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ropReg {@code >= 0;} rop register to reserve 32199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param category {@code > 0;} width to reserve 322f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 323f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void markReserved(int ropReg, int category) { 324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reservedRopRegs.set(ropReg, ropReg + category, true); 325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 326f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 327f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 32864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Checks to see if any rop registers in the specified range are reserved 32964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * for local variables or parameters. 330f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 33164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param ropRangeStart {@code >= 0;} lowest rop register 33264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param width {@code > 0;} number of rop registers in range. 33364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return {@code true} if any register in range is marked reserved 334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 335f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean rangeContainsReserved(int ropRangeStart, int width) { 336f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = ropRangeStart; i < (ropRangeStart + width); i++) { 337f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (reservedRopRegs.get(i)) { 338f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 339f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 340f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 341f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 342f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 343f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 344f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 34564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Returns true if given rop register represents the {@code this} pointer 34664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * for a non-static method. 347f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 348f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param startReg rop register 349f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if the "this" pointer is located here. 350f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 351f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean isThisPointerReg(int startReg) { 35264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // "this" is always the first parameter. 353f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return startReg == 0 && !ssaMeth.isStatic(); 354f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 355f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 356f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 35764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Finds a range of unreserved rop registers. 358f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 35964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param startReg {@code >= 0;} a rop register to start the search at 36099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param width {@code > 0;} the width, in registers, required. 36199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} start of available register range. 362f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 363f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int findNextUnreservedRopReg(int startReg, int width) { 364f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (minimizeRegisters && !isThisPointerReg(startReg)) { 365f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return startReg; 366f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 367f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 368f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int reg; 369f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 370f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reg = reservedRopRegs.nextClearBit(startReg); 371f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 372f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (true) { 373f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i = 1; 374f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 375f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (i < width && !reservedRopRegs.get(reg + i)) { 376f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project i++; 377f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 378f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 379f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (i == width) { 380f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return reg; 381f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 382f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 383f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reg = reservedRopRegs.nextClearBit(reg + i); 384f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 385f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 386f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 387f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 388f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Finds a range of rop regs that can be used for local variables. 38964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * If {@code MIX_LOCALS_AND_OTHER} is {@code false}, this means any 390f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * rop register that has not yet been used. 391f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 39264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param startReg {@code >= 0;} a rop register to start the search at 39399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param width {@code > 0;} the width, in registers, required. 39499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} start of available register range. 395f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 396f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int findRopRegForLocal(int startReg, int width) { 397f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (minimizeRegisters && !isThisPointerReg(startReg)) { 398f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return startReg; 399f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 400f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 401f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int reg; 402f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 403f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reg = usedRopRegs.nextClearBit(startReg); 404f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 405f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (true) { 406f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i = 1; 407f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 408f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (i < width && !usedRopRegs.get(reg + i)) { 409f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project i++; 410f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 411f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 412f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (i == width) { 413f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return reg; 414f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 415f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 416f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reg = usedRopRegs.nextClearBit(reg + i); 417f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 418f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 419f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 420f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 421f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Maps any parameter that isn't local-associated, which can happen 422f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * in the case where there is no java debug info. 423f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 424f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleUnassociatedParameters() { 425f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSsaRegs = ssaMeth.getRegCount(); 42699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 427f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int ssaReg = 0; ssaReg < szSsaRegs; ssaReg++) { 428f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(ssaReg)) { 429f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // We already did this one above 430f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 431f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 432f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 433f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int paramIndex = getParameterIndexForReg(ssaReg); 434f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 435f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec ssaSpec = getDefinitionSpecForSsaReg(ssaReg); 436f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (paramIndex >= 0) { 437f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addMapping(ssaSpec, paramIndex); 43864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein } 439f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 440f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 441f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 442f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 443f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Handles all insns that want a register range for their sources. 444f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 445f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleInvokeRangeInsns() { 44641aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (NormalSsaInsn insn : invokeRangeInsns) { 447f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project adjustAndMapSourceRangeRange(insn); 448f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 449f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 450f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 451f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 45264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Handles check cast results to reuse the same source register if 45364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * possible. 454f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 455f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleCheckCastResults() { 456f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (NormalSsaInsn insn : moveResultPseudoInsns) { 457f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec moveRegSpec = insn.getResult(); 458f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int moveReg = moveRegSpec.getReg(); 459f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet predBlocks = insn.getBlock().getPredecessors(); 460f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 461f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Expect one predecessor block only 462f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (predBlocks.cardinality() != 1) { 463f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 464f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 465f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 466f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock predBlock = 467f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaMeth.getBlocks().get(predBlocks.nextSetBit(0)); 468f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<SsaInsn> insnList = predBlock.getInsns(); 469f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 470f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 471f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If the predecessor block has a check-cast, it will be the last 472f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction 473f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 474f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn checkCastInsn = insnList.get(insnList.size() - 1); 475f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (checkCastInsn.getOpcode().getOpcode() != RegOps.CHECK_CAST) { 476f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 477f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 478f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 479f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec checkRegSpec = checkCastInsn.getSources().get(0); 480f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int checkReg = checkRegSpec.getReg(); 481f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 482f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Assume none of the register is mapped yet 483f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ropReg = 0; 484f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 485f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 486f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * See if either register is already mapped. Most likely the move 487f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * result will be mapped already since the cast result is stored 488f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * in a local variable. 489f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 490f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(moveReg)) { 491f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropReg = mapper.oldToNew(moveReg); 492f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (ssaRegsMapped.get(checkReg)) { 493f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropReg = mapper.oldToNew(checkReg); 494f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 495f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 496f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<RegisterSpec> ssaRegs = new ArrayList<RegisterSpec>(2); 497f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaRegs.add(moveRegSpec); 498f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaRegs.add(checkRegSpec); 499f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = checkRegSpec.getCategory(); 500f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 501f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (!tryMapRegs(ssaRegs, ropReg, category, false)) { 502f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropReg = findNextUnreservedRopReg(ropReg + 1, category); 503f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 504f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 505f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 506f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 507f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 50864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Maps all non-parameter, non-local variable registers. 509f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 510f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void handleNormalUnassociated() { 511f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSsaRegs = ssaMeth.getRegCount(); 51299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 513f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int ssaReg = 0; ssaReg < szSsaRegs; ssaReg++) { 514f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(ssaReg)) { 515f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // We already did this one 516f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 517f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 518f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 519f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec ssaSpec = getDefinitionSpecForSsaReg(ssaReg); 520f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 521f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaSpec == null) continue; 522f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 523f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = ssaSpec.getCategory(); 524f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Find a rop reg that does not interfere 525f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ropReg = findNextUnreservedRopReg(0, category); 526f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (!canMapReg(ssaSpec, ropReg)) { 527f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropReg = findNextUnreservedRopReg(ropReg + 1, category); 528f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 529f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 530f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addMapping(ssaSpec, ropReg); 531f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 532f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 533f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 534f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 53599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Checks to see if {@code ssaSpec} can be mapped to 53699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code ropReg}. Checks interference graph and ensures 537f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the range does not cross the parameter range. 538f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 53999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaSpec {@code non-null;} SSA spec 540f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param ropReg prosepctive new-namespace reg 54164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return {@code true} if mapping is possible 542f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 543f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean canMapReg(RegisterSpec ssaSpec, int ropReg) { 544f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = ssaSpec.getCategory(); 545f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return !(spansParamRange(ropReg, category) 546f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project || mapper.interferes(ssaSpec, ropReg)); 547f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 54864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein 549f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 55064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Returns true if the specified rop register + category 55199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * will cross the boundry between the lower {@code paramWidth} 552f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers reserved for method params and the upper registers. We cannot 553f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * allocate a register that spans the param block and the normal block, 554f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * because we will be moving the param block to high registers later. 55564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 556f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param ssaReg register in new namespace 557f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param category width that the register will have 55864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return {@code true} in the case noted above 559f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 560f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean spansParamRange(int ssaReg, int category) { 561f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return ((ssaReg < paramRangeEnd) 562f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && ((ssaReg + category) > paramRangeEnd)); 563f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 564f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 565f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 566f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Analyze each instruction and find out all the local variable assignments 567f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and move-result-pseudo/invoke-range instrucitons. 568f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 569f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void analyzeInstructions() { 570f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaMeth.forEachInsn(new SsaInsn.Visitor() { 571f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 572f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitMoveInsn(NormalSsaInsn insn) { 573f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project processInsn(insn); 574f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 575f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 576f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 577f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitPhiInsn(PhiInsn insn) { 578f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project processInsn(insn); 579f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 580f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 581f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 582f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitNonMoveInsn(NormalSsaInsn insn) { 583f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project processInsn(insn); 584f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 585f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 586f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 587f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This method collects three types of instructions: 58864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 589f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1) Adds a local variable assignment to the 59099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code localVariables} map. 591f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 2) Add move-result-pseudo to the 59299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code moveResultPseudoInsns} list. 593f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 3) Add invoke-range to the 59499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code invokeRangeInsns} list. 595f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 59699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn that may represent a 59799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * local variable assignment 598f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 599f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void processInsn(SsaInsn insn) { 600f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec assignment; 601f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assignment = insn.getLocalAssignment(); 602f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 603f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (assignment != null) { 604f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LocalItem local = assignment.getLocalItem(); 605f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 60699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project ArrayList<RegisterSpec> regList 60799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project = localVariables.get(local); 608f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 609f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (regList == null) { 610f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regList = new ArrayList<RegisterSpec>(); 611f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project localVariables.put(local, regList); 612f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 613f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 614f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regList.add(assignment); 615f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 616f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 617f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn instanceof NormalSsaInsn) { 618f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn.getOpcode().getOpcode() == 619f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegOps.MOVE_RESULT_PSEUDO) { 620f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project moveResultPseudoInsns.add((NormalSsaInsn) insn); 621f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (Optimizer.getAdvice().requiresSourcesInOrder( 622f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn.getOriginalRopInsn().getOpcode(), 623f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn.getSources())) { 624f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project invokeRangeInsns.add((NormalSsaInsn) insn); 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 }); 630f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 631f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 632f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 63364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Adds a mapping from an SSA register to a rop register. 63499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@link #canMapReg} should have already been called. 635f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 63699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaSpec {@code non-null;} SSA register to map from 63764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param ropReg {@code >=0;} rop register to map to 638f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 639f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void addMapping(RegisterSpec ssaSpec, int ropReg) { 640f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ssaReg = ssaSpec.getReg(); 641f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 64264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // An assertion. 643f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(ssaReg) || !canMapReg(ssaSpec, ropReg)) { 644f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new RuntimeException( 645f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project "attempt to add invalid register mapping"); 646f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 647f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 648f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (DEBUG) { 649f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project System.out.printf("Add mapping s%d -> v%d c:%d\n", 65099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project ssaSpec.getReg(), ropReg, ssaSpec.getCategory()); 651f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 652f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 653f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = ssaSpec.getCategory(); 654f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project mapper.addMapping(ssaSpec.getReg(), ropReg, category); 655f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaRegsMapped.set(ssaReg); 656f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project usedRopRegs.set(ropReg, ropReg + category); 657f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 658f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 659f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 660f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 661f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Maps the source registers of the specified instruction such that they 66264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * will fall in a contiguous range in rop form. Moves are inserted as 663f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * necessary to allow the range to be allocated. 664f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 66599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn whos sources to process 666f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 667f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void adjustAndMapSourceRangeRange(NormalSsaInsn insn) { 66899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project int newRegStart = findRangeAndAdjust(insn); 669f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 670f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList sources = insn.getSources(); 671f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSources = sources.size(); 672f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int nextRopReg = newRegStart; 67399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 674f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szSources; i++) { 675f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec source = sources.get(i); 676f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sourceReg = source.getReg(); 677f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = source.getCategory(); 678f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int curRopReg = nextRopReg; 679f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project nextRopReg += category; 680f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 681f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(sourceReg)) { 682f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 683f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 684f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 685f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LocalItem localItem = getLocalItemForReg(sourceReg); 686f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addMapping(source, curRopReg); 687f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 688f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (localItem != null) { 689f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project markReserved(curRopReg, category); 690f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<RegisterSpec> similarRegisters 691f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = localVariables.get(localItem); 692f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 693f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSimilar = similarRegisters.size(); 694f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 69564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /* 69664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Try to map all SSA registers also associated with 69764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * this local. 69864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein */ 699f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int j = 0; j < szSimilar; j++) { 700f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec similarSpec = similarRegisters.get(j); 701f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int similarReg = similarSpec.getReg(); 702f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 70364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // Don't map anything that's also a source. 704f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (-1 != sources.indexOfRegister(similarReg)) { 705f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 706f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 707f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 70864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // Registers left unmapped will get handled later. 709f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project tryMapReg(similarSpec, curRopReg, category); 710f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 711f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 712f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 713f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 714f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 715f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 716f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Find a contiguous rop register range that fits the specified 717f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction's sources. First, try to center the range around 71864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * sources that have already been mapped to rop registers. If that fails, 719f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * just find a new contiguous range that doesn't interfere. 72064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 72199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} the insn whose sources need to 72299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * fit. Must be last insn in basic block. 72399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} rop register of start of range 724f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 725f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int findRangeAndAdjust(NormalSsaInsn insn) { 726f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList sources = insn.getSources(); 727f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSources = sources.size(); 728f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // the category for each source index 729f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int categoriesForIndex[] = new int[szSources]; 730f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int rangeLength = 0; 731f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 732f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Compute rangeLength and categoriesForIndex 733f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szSources; i++) { 734f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = sources.get(i).getCategory(); 735f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project categoriesForIndex[i] = category; 736f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project rangeLength += categoriesForIndex[i]; 737f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 738f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 73964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // the highest score of fits tried so far 740f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int maxScore = Integer.MIN_VALUE; 741f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // the high scoring range's start 742f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int resultRangeStart = -1; 743f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // by source index: set of sources needing moves in high scoring plan 744f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet resultMovesRequired = null; 745f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 746f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 747f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * First, go through each source that's already been mapped. Try 74864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * to center the range around the rop register this source is mapped 749f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to. 750f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 751f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int rangeStartOffset = 0; 752f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szSources; i++) { 753f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ssaCenterReg = sources.get(i).getReg(); 754f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 755f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (i != 0) { 756f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project rangeStartOffset -= categoriesForIndex[i - 1]; 757f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 758f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!ssaRegsMapped.get(ssaCenterReg)) { 759f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 760f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 761f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 762f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int rangeStart = mapper.oldToNew(ssaCenterReg) + rangeStartOffset; 763f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 764f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (rangeStart < 0 || spansParamRange(rangeStart, rangeLength)) { 765f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 766f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 767f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 768f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet curMovesRequired = new BitSet(szSources); 769f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 770f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int fitWidth 771f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = fitPlanForRange(rangeStart, insn, categoriesForIndex, 772f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project curMovesRequired); 773f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 774f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (fitWidth < 0) { 775f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 776f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 777f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 778f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int score = fitWidth - curMovesRequired.cardinality(); 779f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 780f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (score > maxScore) { 781f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project maxScore = score; 782f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultRangeStart = rangeStart; 783f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultMovesRequired = curMovesRequired; 784f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 785f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 786f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (fitWidth == rangeLength) { 787f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // We can't do any better than this, so stop here 788f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 789f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 790f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 791f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 792f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 793f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If we were unable to find a plan for a fit centered around 794f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * an already-mapped source, just try to find a range of 795f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers we can move the range into. 796f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 797f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 798f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (resultRangeStart == -1) { 799f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultMovesRequired = new BitSet(szSources); 800f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 801f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultRangeStart = findAnyFittingRange(insn, rangeLength, 802f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project categoriesForIndex, resultMovesRequired); 803f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 804f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 805f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 80664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Now, insert any moves required. 807f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 808f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 80941aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (int i = resultMovesRequired.nextSetBit(0); i >= 0; 81041aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein i = resultMovesRequired.nextSetBit(i+1)) { 81141aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein insn.changeOneSource(i, insertMoveBefore(insn, sources.get(i))); 812f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 813f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 814f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return resultRangeStart; 815f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 816f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 817f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 818f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Finds an unreserved range that will fit the sources of the 819f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * specified instruction. Does not bother trying to center the range 820f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * around an already-mapped source register; 821f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 82299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn to build range for 82364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param rangeLength {@code >=0;} length required in register units 82499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param categoriesForIndex {@code non-null;} indexed by source index; 82564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * the category for each source 82699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param outMovesRequired {@code non-null;} an output parameter indexed by 827f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * source index that will contain the set of sources which need 82864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * moves inserted 82964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return the rop register that starts the fitting range 830f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 831f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int findAnyFittingRange(NormalSsaInsn insn, int rangeLength, 832f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int[] categoriesForIndex, BitSet outMovesRequired) { 833f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int rangeStart = 0; 834f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (true) { 835f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project rangeStart = findNextUnreservedRopReg(rangeStart, rangeLength); 836f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int fitWidth 837f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = fitPlanForRange(rangeStart, insn, 838f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project categoriesForIndex, outMovesRequired); 839f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 840f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (fitWidth >= 0) { 841f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 842f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 843f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project rangeStart++; 844f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project outMovesRequired.clear(); 845f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 846f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return rangeStart; 847f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 848f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 849f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 850f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Attempts to build a plan for fitting a range of sources into rop 851f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers. 852f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 85399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ropReg {@code >= 0;} rop reg that begins range 85499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn to plan range for 85599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param categoriesForIndex {@code non-null;} indexed by source index; 85664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * the category for each source 85799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param outMovesRequired {@code non-null;} an output parameter indexed by 858f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * source index that will contain the set of sources which need 85964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * moves inserted 860f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return the width of the fit that that does not involve added moves or 86164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * {@code -1} if "no fit possible" 862f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 863f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int fitPlanForRange(int ropReg, NormalSsaInsn insn, 864f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int[] categoriesForIndex, BitSet outMovesRequired) { 865f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList sources = insn.getSources(); 866f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szSources = sources.size(); 867f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int fitWidth = 0; 868f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntSet liveOut = insn.getBlock().getLiveOutRegs(); 869f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList liveOutSpecs = ssaSetToSpecs(liveOut); 870f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 87164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // An SSA reg may only be mapped into a range once. 872f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet seen = new BitSet(ssaMeth.getRegCount()); 873f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 874f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szSources ; i++) { 875f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec ssaSpec = sources.get(i); 876f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ssaReg = ssaSpec.getReg(); 877f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = categoriesForIndex[i]; 878f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 879f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (i != 0) { 880f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropReg += categoriesForIndex[i-1]; 881f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 882f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 883f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaRegsMapped.get(ssaReg) 884f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && mapper.oldToNew(ssaReg) == ropReg) { 88564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // This is a register that is already mapped appropriately. 886f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project fitWidth += category; 887f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (rangeContainsReserved(ropReg, category)) { 888f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project fitWidth = -1; 889f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 890f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (!ssaRegsMapped.get(ssaReg) 891f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && canMapReg(ssaSpec, ropReg) 892f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && !seen.get(ssaReg)) { 89364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // This is a register that can be mapped appropriately. 894f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project fitWidth += category; 895f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (!mapper.areAnyPinned(liveOutSpecs, ropReg, category) 896f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && !mapper.areAnyPinned(sources, ropReg, category)) { 897f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 89864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * This is a source that can be moved. We can insert a 89964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * move as long as: 90064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 90164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * * no SSA register pinned to the desired rop reg 90264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * is live out on the block 903f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 90464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * * no SSA register pinned to desired rop reg is 90564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * a source of this insn (since this may require 90664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * overlapping moves, which we can't presently handle) 907f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 908f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 909f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project outMovesRequired.set(i); 910f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 911f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project fitWidth = -1; 912f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 913f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 914f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 915f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project seen.set(ssaReg); 916f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 917f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return fitWidth; 918f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 919f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 920f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 921f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Converts a bit set of SSA registers into a RegisterSpecList containing 922f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the definition specs of all the registers. 923f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 92499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaSet {@code non-null;} set of SSA registers 925f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return list of RegisterSpecs as noted above 926f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 927f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList ssaSetToSpecs(IntSet ssaSet) { 928f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList result = new RegisterSpecList(ssaSet.elements()); 929f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 930f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntIterator iter = ssaSet.iterator(); 931f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 932f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i = 0; 933f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (iter.hasNext()) { 934f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.set(i++, getDefinitionSpecForSsaReg(iter.next())); 935f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 93664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein 937f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 938f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 939f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 940f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 94164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Gets a local item associated with an ssa register, if one exists. 942f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 94399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaReg {@code >= 0;} SSA register 94499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code null-ok;} associated local item or null 945f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 946f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private LocalItem getLocalItemForReg(int ssaReg) { 94741aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (Map.Entry<LocalItem, ArrayList<RegisterSpec>> entry : 94841aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein localVariables.entrySet()) { 94999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (RegisterSpec spec : entry.getValue()) { 950f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (spec.getReg() == ssaReg) { 951f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return entry.getKey(); 952f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 953f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 954f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 955f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 956f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return null; 957f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 958f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 959