1/* 2 * Copyright (C) 2007 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package com.android.dx.ssa.back; 18 19import com.android.dx.rop.code.CstInsn; 20import com.android.dx.rop.cst.CstInteger; 21import com.android.dx.ssa.BasicRegisterMapper; 22import com.android.dx.ssa.NormalSsaInsn; 23import com.android.dx.ssa.RegisterMapper; 24import com.android.dx.ssa.SsaMethod; 25import com.android.dx.util.BitIntSet; 26import com.android.dx.util.IntSet; 27import java.util.BitSet; 28 29/** 30 * Allocates registers via a naive n^2 register allocator. 31 * This allocator does not try to co-locate local variables or deal 32 * intelligently with different size register uses. 33 */ 34public class FirstFitAllocator extends RegisterAllocator { 35 /** 36 * If true, allocator places parameters at the top of the frame 37 * in calling-convention order. 38 */ 39 private static final boolean PRESLOT_PARAMS = true; 40 41 /** indexed by old reg; the set of old regs we've mapped */ 42 private final BitSet mapped; 43 44 /** {@inheritDoc} */ 45 public FirstFitAllocator( 46 final SsaMethod ssaMeth, final InterferenceGraph interference) { 47 super(ssaMeth, interference); 48 49 mapped = new BitSet(ssaMeth.getRegCount()); 50 } 51 52 /** {@inheritDoc} */ 53 @Override 54 public boolean wantsParamsMovedHigh() { 55 return PRESLOT_PARAMS; 56 } 57 58 /** {@inheritDoc} */ 59 @Override 60 public RegisterMapper allocateRegisters() { 61 int oldRegCount = ssaMeth.getRegCount(); 62 63 BasicRegisterMapper mapper 64 = new BasicRegisterMapper(oldRegCount); 65 66 int nextNewRegister = 0; 67 68 if (PRESLOT_PARAMS) { 69 /* 70 * Reserve space for the params at the bottom of the register 71 * space. Later, we'll flip the params to the end of the register 72 * space. 73 */ 74 75 nextNewRegister = ssaMeth.getParamWidth(); 76 } 77 78 for (int i = 0; i < oldRegCount; i++) { 79 if (mapped.get(i)) { 80 // we already got this one 81 continue; 82 } 83 84 int maxCategory = getCategoryForSsaReg(i); 85 IntSet current = new BitIntSet(oldRegCount); 86 87 interference.mergeInterferenceSet(i, current); 88 89 boolean isPreslotted = false; 90 int newReg = 0; 91 92 if (PRESLOT_PARAMS && isDefinitionMoveParam(i)) { 93 // Any move-param definition must be a NormalSsaInsn 94 NormalSsaInsn defInsn = (NormalSsaInsn) 95 ssaMeth.getDefinitionForRegister(i); 96 97 newReg = paramNumberFromMoveParam(defInsn); 98 99 mapper.addMapping(i, newReg, maxCategory); 100 isPreslotted = true; 101 } else { 102 mapper.addMapping(i, nextNewRegister, maxCategory); 103 newReg = nextNewRegister; 104 } 105 106 for (int j = i + 1; j < oldRegCount; j++) { 107 if (mapped.get(j) || isDefinitionMoveParam(j)) { 108 continue; 109 } 110 111 /* 112 * If reg j doesn't interfere with the current mapping. 113 * Also, if this is a pre-slotted method parameter, we 114 * can't use more than the original param width. 115 */ 116 if (!current.has(j) 117 && !(isPreslotted 118 && (maxCategory < getCategoryForSsaReg(j)))) { 119 120 interference.mergeInterferenceSet(j, current); 121 122 maxCategory = Math.max(maxCategory, 123 getCategoryForSsaReg(j)); 124 125 mapper.addMapping(j, newReg, maxCategory); 126 mapped.set(j); 127 } 128 } 129 130 mapped.set(i); 131 if (!isPreslotted) { 132 nextNewRegister += maxCategory; 133 } 134 } 135 136 return mapper; 137 } 138 139 /** 140 * Returns the parameter number that this move-param insn refers to 141 * @param ndefInsn a move-param insn (otherwise, exceptions will be thrown) 142 * @return parameter number (offset in the total parameter width) 143 */ 144 private int paramNumberFromMoveParam(NormalSsaInsn ndefInsn) { 145 CstInsn origInsn = (CstInsn) ndefInsn.getOriginalRopInsn(); 146 147 return ((CstInteger) origInsn.getConstant()).getValue(); 148 } 149} 150