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.NormalSsaInsn; 22import com.android.dx.ssa.BasicRegisterMapper; 23import com.android.dx.ssa.RegisterMapper; 24import com.android.dx.ssa.SsaMethod; 25import com.android.dx.util.IntSet; 26import com.android.dx.util.BitIntSet; 27 28import java.util.BitSet; 29import java.util.ArrayList; 30 31/** 32 * Allocates registers via a naive n^2 register allocator. 33 * This allocator does not try to co-locate local variables or deal 34 * intelligently with different size register uses. 35 */ 36public class FirstFitAllocator extends RegisterAllocator { 37 /** 38 * If true, allocator places parameters at the top of the frame 39 * in calling-convention order. 40 */ 41 private static final boolean PRESLOT_PARAMS = true; 42 43 /** indexed by old reg; the set of old regs we've mapped */ 44 private final BitSet mapped; 45 46 /** {@inheritDoc} */ 47 public FirstFitAllocator( 48 final SsaMethod ssaMeth, final InterferenceGraph interference) { 49 super(ssaMeth, interference); 50 51 mapped = new BitSet(ssaMeth.getRegCount()); 52 } 53 54 /** {@inheritDoc} */ 55 @Override 56 public boolean wantsParamsMovedHigh() { 57 return PRESLOT_PARAMS; 58 } 59 60 /** {@inheritDoc} */ 61 @Override 62 public RegisterMapper allocateRegisters() { 63 int oldRegCount = ssaMeth.getRegCount(); 64 65 BasicRegisterMapper mapper 66 = new BasicRegisterMapper(oldRegCount); 67 68 int nextNewRegister = 0; 69 70 if (PRESLOT_PARAMS) { 71 /* 72 * Reserve space for the params at the bottom of the register 73 * space. Later, we'll flip the params to the end of the register 74 * space. 75 */ 76 77 nextNewRegister = ssaMeth.getParamWidth(); 78 } 79 80 for (int i = 0; i < oldRegCount; i++) { 81 if (mapped.get(i)) { 82 // we already got this one 83 continue; 84 } 85 86 int maxCategory = getCategoryForSsaReg(i); 87 IntSet current = new BitIntSet(oldRegCount); 88 89 interference.mergeInterferenceSet(i, current); 90 91 boolean isPreslotted = false; 92 int newReg = 0; 93 94 if (PRESLOT_PARAMS && isDefinitionMoveParam(i)) { 95 // Any move-param definition must be a NormalSsaInsn 96 NormalSsaInsn defInsn = (NormalSsaInsn) 97 ssaMeth.getDefinitionForRegister(i); 98 99 newReg = paramNumberFromMoveParam(defInsn); 100 101 mapper.addMapping(i, newReg, maxCategory); 102 isPreslotted = true; 103 } else { 104 mapper.addMapping(i, nextNewRegister, maxCategory); 105 newReg = nextNewRegister; 106 } 107 108 for (int j = i + 1; j < oldRegCount; j++) { 109 if (mapped.get(j) || isDefinitionMoveParam(j)) { 110 continue; 111 } 112 113 /* 114 * If reg j doesn't interfere with the current mapping. 115 * Also, if this is a pre-slotted method parameter, we 116 * can't use more than the original param width. 117 */ 118 if (!current.has(j) 119 && !(isPreslotted 120 && (maxCategory < getCategoryForSsaReg(j)))) { 121 122 interference.mergeInterferenceSet(j, current); 123 124 maxCategory = Math.max(maxCategory, 125 getCategoryForSsaReg(j)); 126 127 mapper.addMapping(j, newReg, maxCategory); 128 mapped.set(j); 129 } 130 } 131 132 mapped.set(i); 133 if (!isPreslotted) { 134 nextNewRegister += maxCategory; 135 } 136 } 137 138 return mapper; 139 } 140 141 /** 142 * Returns the parameter number that this move-param insn refers to 143 * @param ndefInsn a move-param insn (otherwise, exceptions will be thrown) 144 * @return parameter number (offset in the total parameter width) 145 */ 146 private int paramNumberFromMoveParam(NormalSsaInsn ndefInsn) { 147 CstInsn origInsn = (CstInsn) ndefInsn.getOriginalRopInsn(); 148 149 return ((CstInteger) origInsn.getConstant()).getValue(); 150 } 151} 152