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