1579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/* 2579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Copyright (C) 2007 The Android Open Source Project 3579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 4579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * you may not use this file except in compliance with the License. 6579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * You may obtain a copy of the License at 7579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 8579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 10579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * See the License for the specific language governing permissions and 14579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * limitations under the License. 15579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 16579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 17579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpackage com.android.dx.ssa.back; 18579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 19579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RegOps; 20579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RegisterSpec; 21579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.PlainInsn; 22579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.Rops; 23579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.SourcePosition; 24579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RegisterSpecList; 25579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.ssa.NormalSsaInsn; 26579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.ssa.RegisterMapper; 27579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.ssa.SsaInsn; 28579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.ssa.SsaMethod; 29579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.ssa.SsaBasicBlock; 30579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.IntSet; 31579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.IntIterator; 32579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 33579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.BitSet; 34579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.ArrayList; 35579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 36579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/** 37579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Base class of all register allocators. 38579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 39579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic abstract class RegisterAllocator { 40579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** method being processed */ 41579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson protected final SsaMethod ssaMeth; 42579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 43579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** interference graph, indexed by register in both dimensions */ 44579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson protected final InterferenceGraph interference; 45579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 46579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 47579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Creates an instance. Call {@code allocateRegisters} to run. 48579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param ssaMeth method to process. 49579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param interference Interference graph, indexed by register in both 50579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * dimensions. 51579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 52579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public RegisterAllocator(SsaMethod ssaMeth, 53579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson InterferenceGraph interference) { 54579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.ssaMeth = ssaMeth; 55579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.interference = interference; 56579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 57579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 58579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 59579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Indicates whether the method params were allocated at the bottom 60579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * of the namespace, and thus should be moved up to the top of the 61579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * namespace after phi removal. 62579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 63579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code true} if params should be moved from low to high 64579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 65579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public abstract boolean wantsParamsMovedHigh(); 66579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 67579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 68579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Runs the algorithm. 69579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 70579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return a register mapper to apply to the {@code SsaMethod} 71579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 72579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public abstract RegisterMapper allocateRegisters(); 73579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 74579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 75579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Returns the category (width) of the definition site of the register. 76579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Returns {@code 1} for undefined registers. 77579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 78579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param reg register 79579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code 1..2} 80579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 81579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson protected final int getCategoryForSsaReg(int reg) { 82579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn definition = ssaMeth.getDefinitionForRegister(reg); 83579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 84579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (definition == null) { 85579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // an undefined reg 86579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return 1; 87579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 88579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return definition.getResult().getCategory(); 89579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 90579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 91579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 92579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 93579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Returns the RegisterSpec of the definition of the register. 94579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 95579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param reg {@code >= 0;} SSA register 96579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return definition spec of the register or null if it is never defined 97579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * (for the case of "version 0" SSA registers) 98579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 99579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson protected final RegisterSpec getDefinitionSpecForSsaReg(int reg) { 100579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn definition = ssaMeth.getDefinitionForRegister(reg); 101579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 102579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return definition == null ? null : definition.getResult(); 103579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 104579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 105579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 106579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Returns true if the definition site of this register is a 107579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * move-param (ie, this is a method parameter). 108579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 109579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param reg register in question 110579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code true} if this is a method parameter 111579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 112579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson protected boolean isDefinitionMoveParam(int reg) { 113579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn defInsn = ssaMeth.getDefinitionForRegister(reg); 114579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 115579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (defInsn instanceof NormalSsaInsn) { 116579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson NormalSsaInsn ndefInsn = (NormalSsaInsn) defInsn; 117579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 118579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return ndefInsn.getOpcode().getOpcode() == RegOps.MOVE_PARAM; 119579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 120579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 121579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return false; 122579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 123579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 124579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 125579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Inserts a move instruction for a specified SSA register before a 126579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * specified instruction, creating a new SSA register and adjusting the 127579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * interference graph in the process. The insn currently must be the 128579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * last insn in a block. 129579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 130579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param insn {@code non-null;} insn to insert move before, must 131579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * be last insn in block 132579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param reg {@code non-null;} SSA register to duplicate 133579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} spec of new SSA register created by move 134579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 135579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson protected final RegisterSpec insertMoveBefore(SsaInsn insn, 136579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec reg) { 137579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock block = insn.getBlock(); 138579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<SsaInsn> insns = block.getInsns(); 139579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int insnIndex = insns.indexOf(insn); 140579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 141579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (insnIndex < 0) { 142579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new IllegalArgumentException ( 143579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson "specified insn is not in this block"); 144579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 145579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 146579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (insnIndex != insns.size() - 1) { 147579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 148579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Presently, the interference updater only works when 149579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * adding before the last insn, and the last insn must have no 150579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * result 151579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 152579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new IllegalArgumentException( 153579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson "Adding move here not supported:" + insn.toHuman()); 154579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 155579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 156579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 157579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Get new register and make new move instruction. 158579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 159579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 160579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // The new result must not have an associated local variable. 161579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec newRegSpec = RegisterSpec.make(ssaMeth.makeNewSsaReg(), 162579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson reg.getTypeBearer()); 163579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 164579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn toAdd = SsaInsn.makeFromRop( 165579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson new PlainInsn(Rops.opMove(newRegSpec.getType()), 166579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SourcePosition.NO_INFO, newRegSpec, 167579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpecList.make(reg)), block); 168579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 169579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insns.add(insnIndex, toAdd); 170579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 171579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int newReg = newRegSpec.getReg(); 172579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 173579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 174579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Adjust interference graph based on what's live out of the current 175579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * block and what's used by the final instruction. 176579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 177579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 178579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntSet liveOut = block.getLiveOutRegs(); 179579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntIterator liveOutIter = liveOut.iterator(); 180579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 181579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson while (liveOutIter.hasNext()) { 182579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson interference.add(newReg, liveOutIter.next()); 183579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 184579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 185579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Everything that's a source in the last insn interferes. 186579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpecList sources = insn.getSources(); 187579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int szSources = sources.size(); 188579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 189579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < szSources; i++) { 190579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson interference.add(newReg, sources.get(i).getReg()); 191579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 192579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 193579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaMeth.onInsnsChanged(); 194579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 195579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return newRegSpec; 196579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 197579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson} 198