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 17 package com.android.dx.ssa.back; 18 19 import com.android.dx.rop.code.PlainInsn; 20 import com.android.dx.rop.code.RegOps; 21 import com.android.dx.rop.code.RegisterSpec; 22 import com.android.dx.rop.code.RegisterSpecList; 23 import com.android.dx.rop.code.Rops; 24 import com.android.dx.rop.code.SourcePosition; 25 import com.android.dx.ssa.NormalSsaInsn; 26 import com.android.dx.ssa.RegisterMapper; 27 import com.android.dx.ssa.SsaBasicBlock; 28 import com.android.dx.ssa.SsaInsn; 29 import com.android.dx.ssa.SsaMethod; 30 import com.android.dx.util.IntIterator; 31 import com.android.dx.util.IntSet; 32 import java.util.ArrayList; 33 34 /** 35 * Base class of all register allocators. 36 */ 37 public abstract class RegisterAllocator { 38 /** method being processed */ 39 protected final SsaMethod ssaMeth; 40 41 /** interference graph, indexed by register in both dimensions */ 42 protected final InterferenceGraph interference; 43 44 /** 45 * Creates an instance. Call {@code allocateRegisters} to run. 46 * @param ssaMeth method to process. 47 * @param interference Interference graph, indexed by register in both 48 * dimensions. 49 */ RegisterAllocator(SsaMethod ssaMeth, InterferenceGraph interference)50 public RegisterAllocator(SsaMethod ssaMeth, 51 InterferenceGraph interference) { 52 this.ssaMeth = ssaMeth; 53 this.interference = interference; 54 } 55 56 /** 57 * Indicates whether the method params were allocated at the bottom 58 * of the namespace, and thus should be moved up to the top of the 59 * namespace after phi removal. 60 * 61 * @return {@code true} if params should be moved from low to high 62 */ wantsParamsMovedHigh()63 public abstract boolean wantsParamsMovedHigh(); 64 65 /** 66 * Runs the algorithm. 67 * 68 * @return a register mapper to apply to the {@code SsaMethod} 69 */ allocateRegisters()70 public abstract RegisterMapper allocateRegisters(); 71 72 /** 73 * Returns the category (width) of the definition site of the register. 74 * Returns {@code 1} for undefined registers. 75 * 76 * @param reg register 77 * @return {@code 1..2} 78 */ getCategoryForSsaReg(int reg)79 protected final int getCategoryForSsaReg(int reg) { 80 SsaInsn definition = ssaMeth.getDefinitionForRegister(reg); 81 82 if (definition == null) { 83 // an undefined reg 84 return 1; 85 } else { 86 return definition.getResult().getCategory(); 87 } 88 } 89 90 /** 91 * Returns the RegisterSpec of the definition of the register. 92 * 93 * @param reg {@code >= 0;} SSA register 94 * @return definition spec of the register or null if it is never defined 95 * (for the case of "version 0" SSA registers) 96 */ getDefinitionSpecForSsaReg(int reg)97 protected final RegisterSpec getDefinitionSpecForSsaReg(int reg) { 98 SsaInsn definition = ssaMeth.getDefinitionForRegister(reg); 99 100 return definition == null ? null : definition.getResult(); 101 } 102 103 /** 104 * Returns true if the definition site of this register is a 105 * move-param (ie, this is a method parameter). 106 * 107 * @param reg register in question 108 * @return {@code true} if this is a method parameter 109 */ isDefinitionMoveParam(int reg)110 protected boolean isDefinitionMoveParam(int reg) { 111 SsaInsn defInsn = ssaMeth.getDefinitionForRegister(reg); 112 113 if (defInsn instanceof NormalSsaInsn) { 114 NormalSsaInsn ndefInsn = (NormalSsaInsn) defInsn; 115 116 return ndefInsn.getOpcode().getOpcode() == RegOps.MOVE_PARAM; 117 } 118 119 return false; 120 } 121 122 /** 123 * Inserts a move instruction for a specified SSA register before a 124 * specified instruction, creating a new SSA register and adjusting the 125 * interference graph in the process. The insn currently must be the 126 * last insn in a block. 127 * 128 * @param insn {@code non-null;} insn to insert move before, must 129 * be last insn in block 130 * @param reg {@code non-null;} SSA register to duplicate 131 * @return {@code non-null;} spec of new SSA register created by move 132 */ insertMoveBefore(SsaInsn insn, RegisterSpec reg)133 protected final RegisterSpec insertMoveBefore(SsaInsn insn, 134 RegisterSpec reg) { 135 SsaBasicBlock block = insn.getBlock(); 136 ArrayList<SsaInsn> insns = block.getInsns(); 137 int insnIndex = insns.indexOf(insn); 138 139 if (insnIndex < 0) { 140 throw new IllegalArgumentException ( 141 "specified insn is not in this block"); 142 } 143 144 if (insnIndex != insns.size() - 1) { 145 /* 146 * Presently, the interference updater only works when 147 * adding before the last insn, and the last insn must have no 148 * result 149 */ 150 throw new IllegalArgumentException( 151 "Adding move here not supported:" + insn.toHuman()); 152 } 153 154 /* 155 * Get new register and make new move instruction. 156 */ 157 158 // The new result must not have an associated local variable. 159 RegisterSpec newRegSpec = RegisterSpec.make(ssaMeth.makeNewSsaReg(), 160 reg.getTypeBearer()); 161 162 SsaInsn toAdd = SsaInsn.makeFromRop( 163 new PlainInsn(Rops.opMove(newRegSpec.getType()), 164 SourcePosition.NO_INFO, newRegSpec, 165 RegisterSpecList.make(reg)), block); 166 167 insns.add(insnIndex, toAdd); 168 169 int newReg = newRegSpec.getReg(); 170 171 /* 172 * Adjust interference graph based on what's live out of the current 173 * block and what's used by the final instruction. 174 */ 175 176 IntSet liveOut = block.getLiveOutRegs(); 177 IntIterator liveOutIter = liveOut.iterator(); 178 179 while (liveOutIter.hasNext()) { 180 interference.add(newReg, liveOutIter.next()); 181 } 182 183 // Everything that's a source in the last insn interferes. 184 RegisterSpecList sources = insn.getSources(); 185 int szSources = sources.size(); 186 187 for (int i = 0; i < szSources; i++) { 188 interference.add(newReg, sources.get(i).getReg()); 189 } 190 191 ssaMeth.onInsnsChanged(); 192 193 return newRegSpec; 194 } 195 } 196