| /* |
| * Copyright (C) 2007 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package com.android.dx.ssa.back; |
| |
| import com.android.dx.rop.code.RegOps; |
| import com.android.dx.rop.code.RegisterSpec; |
| import com.android.dx.rop.code.PlainInsn; |
| import com.android.dx.rop.code.Rops; |
| import com.android.dx.rop.code.SourcePosition; |
| import com.android.dx.rop.code.RegisterSpecList; |
| import com.android.dx.ssa.NormalSsaInsn; |
| import com.android.dx.ssa.RegisterMapper; |
| import com.android.dx.ssa.SsaInsn; |
| import com.android.dx.ssa.SsaMethod; |
| import com.android.dx.ssa.SsaBasicBlock; |
| import com.android.dx.util.IntSet; |
| import com.android.dx.util.IntIterator; |
| |
| import java.util.BitSet; |
| import java.util.ArrayList; |
| |
| /** |
| * Base class of all register allocators |
| */ |
| public abstract class RegisterAllocator { |
| |
| /** method being processed */ |
| protected final SsaMethod ssaMeth; |
| |
| /** interference graph, indexed by register in both dimensions */ |
| protected final InterferenceGraph interference; |
| |
| /** |
| * Creates an instance. Call <code>allocateRegisters</code> to run. |
| * @param ssaMeth method to process. |
| * @param interference Interference graph, indexed by register in both |
| * dimensions. |
| */ |
| public RegisterAllocator( |
| final SsaMethod ssaMeth, final InterferenceGraph interference) { |
| this.ssaMeth = ssaMeth; |
| this.interference = interference; |
| } |
| |
| /** |
| * Indicates whether the method params were allocated at the bottom |
| * of the namespace, and thus should be moved up to the top of the |
| * namespace after phi removal. |
| * |
| * @return true if params should be moved from low to high. |
| */ |
| public abstract boolean wantsParamsMovedHigh(); |
| |
| /** |
| * Runs the algorithm. |
| * @return a register mapper to apply to the <code>SsaMethod</code> |
| */ |
| public abstract RegisterMapper allocateRegisters(); |
| |
| /** |
| * Returns the category (width) of the definition site of the register. |
| * Returns 1 for undefined registers. |
| * |
| * @param reg register |
| * @return 1 or 2 |
| */ |
| protected int getCategoryForSsaReg(int reg) { |
| SsaInsn definition; |
| definition = ssaMeth.getDefinitionForRegister(reg); |
| |
| if (definition == null) { |
| // an undefined reg |
| return 1; |
| } else { |
| return definition.getResult().getCategory(); |
| } |
| } |
| |
| /** |
| * Returns the RegisterSpec of the definition of the register. |
| * |
| * @param reg >= 0 SSA register |
| * @return definition spec of the register or null if it is never defined |
| * (for the case of "version 0" SSA registers). |
| */ |
| protected RegisterSpec getDefinitionSpecForSsaReg(int reg) { |
| SsaInsn definition; |
| definition = ssaMeth.getDefinitionForRegister(reg); |
| |
| return definition == null ? null : definition.getResult(); |
| } |
| |
| /** |
| * Returns true if the definition site of this register is a |
| * move-param (ie, this is a method parameter) |
| * @param reg register in question |
| * @return true if this is a method parameter |
| */ |
| protected boolean isDefinitionMoveParam(int reg) { |
| SsaInsn defInsn = ssaMeth.getDefinitionForRegister(reg); |
| if (defInsn instanceof NormalSsaInsn) { |
| NormalSsaInsn ndefInsn = (NormalSsaInsn) defInsn; |
| |
| return ndefInsn.getOpcode().getOpcode() == RegOps.MOVE_PARAM; |
| } |
| |
| return false; |
| } |
| |
| /** |
| * Inserts a move instruction for a specified SSA register before a |
| * specified instruction, creating a new SSA register and adjusting the |
| * interference graph in the process. The insn currently must be the |
| * last insn in a block. |
| * |
| * @param insn non-null; insn to insert move before, must be last insn |
| * in block. |
| * @param reg non-null; SSA register to duplicate |
| * @return non-null; spec of new SSA register created by move |
| */ |
| protected final RegisterSpec insertMoveBefore(SsaInsn insn, |
| RegisterSpec reg) { |
| |
| SsaBasicBlock block = insn.getBlock(); |
| ArrayList<SsaInsn> insns = block.getInsns(); |
| int insnIndex = insns.indexOf(insn); |
| |
| if (insnIndex < 0 ) { |
| throw new IllegalArgumentException ( |
| "specified insn is not in this block"); |
| } |
| |
| if (insnIndex != insns.size() - 1) { |
| /* |
| * Presently, the interference updater only works when |
| * adding before the last insn, and the last insn must have no |
| * result |
| */ |
| throw new IllegalArgumentException( |
| "Adding move here not supported:" + insn.toHuman()); |
| } |
| |
| /* |
| * Get new register and make new move instruction |
| */ |
| |
| // new result must not have associated local variable |
| RegisterSpec newRegSpec = RegisterSpec.make(ssaMeth.makeNewSsaReg(), |
| reg.getTypeBearer()); |
| |
| SsaInsn toAdd; |
| |
| toAdd = SsaInsn.makeFromRop( |
| new PlainInsn(Rops.opMove(newRegSpec.getType()), |
| SourcePosition.NO_INFO, newRegSpec, |
| RegisterSpecList.make(reg)), block); |
| |
| insns.add(insnIndex, toAdd); |
| |
| int newReg = newRegSpec.getReg(); |
| |
| /* |
| * Adjust interference graph based on what's live out of the current |
| * block and what's used by the final instruction. |
| */ |
| |
| IntSet liveOut = block.getLiveOutRegs(); |
| |
| RegisterSpec result = insn.getResult(); |
| int resultReg = (result == null) ? -1 : result.getReg(); |
| |
| IntIterator liveOutIter = liveOut.iterator(); |
| |
| while(liveOutIter.hasNext()) { |
| interference.add(newReg, liveOutIter.next()); |
| } |
| |
| // Everything that's a source in the last insn interferes |
| RegisterSpecList sources = insn.getSources(); |
| int szSources = sources.size(); |
| |
| for (int i = 0; i < szSources; i++) { |
| interference.add(newReg, sources.get(i).getReg()); |
| } |
| |
| ssaMeth.onInsnsChanged(); |
| |
| return newRegSpec; |
| } |
| } |