| /* |
| * 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; |
| |
| import com.android.dx.rop.code.BasicBlock; |
| import com.android.dx.rop.code.BasicBlockList; |
| import com.android.dx.rop.code.InsnList; |
| import com.android.dx.rop.code.PlainInsn; |
| import com.android.dx.rop.code.RegisterSpec; |
| import com.android.dx.rop.code.RegisterSpecList; |
| import com.android.dx.rop.code.RopMethod; |
| import com.android.dx.rop.code.Rops; |
| import com.android.dx.rop.code.SourcePosition; |
| import com.android.dx.rop.code.Insn; |
| import com.android.dx.rop.code.Rop; |
| import com.android.dx.util.IntList; |
| import com.android.dx.util.Hex; |
| import com.android.dx.util.IntSet; |
| import com.android.dx.util.BitIntSet; |
| import com.android.dx.util.ListIntSet; |
| |
| import java.util.ArrayList; |
| import java.util.BitSet; |
| import java.util.Collections; |
| import java.util.List; |
| |
| /** |
| * An SSA representation of a basic block. |
| */ |
| public final class SsaBasicBlock { |
| |
| /** non-null; insn list associated with this instance */ |
| private ArrayList<SsaInsn> insns; |
| /** non-null; predecessor set (by block list index) */ |
| private BitSet predecessors; |
| /** non-null; successor set (by block list index) */ |
| private BitSet successors; |
| /** |
| * non-null; ordered successor list |
| * (same block may be listed more than once) |
| */ |
| private IntList successorList; |
| /** block list index of primary successor, or -1 for no primary successor */ |
| private int primarySuccessor = -1; |
| /** label of block in rop form */ |
| private int ropLabel; |
| /** non-null; method we belong to */ |
| private SsaMethod parent; |
| /** our index into parent.getBlock() */ |
| private int index; |
| /** list of dom children */ |
| private final ArrayList<SsaBasicBlock> domChildren; |
| |
| /** |
| * The number of moves added to the end of the block during the |
| * phi-removal process. Retained for subsequent move scheduling. |
| */ |
| private int movesFromPhisAtEnd = 0; |
| /** |
| * The number of moves added to the beginning of the block during the |
| * phi-removal process. Retained for subsequent move scheduling. |
| */ |
| private int movesFromPhisAtBeginning = 0; |
| |
| /** null-ok; indexed by reg: the regs that are live-in at this block */ |
| private IntSet liveIn; |
| /** null-ok; indexed by reg: the regs that are live-out at this block */ |
| private IntSet liveOut; |
| |
| /** |
| * Create a new empty basic block |
| * @param basicBlockIndex index this block will have |
| * @param ropLabel original rop-form label |
| * @param parent method of this block |
| */ |
| public SsaBasicBlock(final int basicBlockIndex, final int ropLabel, |
| final SsaMethod parent) { |
| this.parent = parent; |
| this.index = basicBlockIndex; |
| this.insns = new ArrayList<SsaInsn>(); |
| this.ropLabel = ropLabel; |
| |
| this.predecessors = new BitSet(parent.getBlocks().size()); |
| this.successors = new BitSet(parent.getBlocks().size()); |
| this.successorList = new IntList(); |
| |
| domChildren = new ArrayList<SsaBasicBlock>(); |
| } |
| |
| /** |
| * Creates a new SSA basic block from a ROP form basic block. |
| * |
| * @param rmeth original method |
| * @param basicBlockIndex index this block will have |
| * @param parent method of this block |
| * predecessor set will be updated. |
| * @return new instance |
| */ |
| public static SsaBasicBlock newFromRop(RopMethod rmeth, |
| int basicBlockIndex, final SsaMethod parent) { |
| |
| BasicBlockList ropBlocks; |
| SsaBasicBlock result; |
| InsnList ropInsns; |
| BasicBlock bb; |
| |
| ropBlocks = rmeth.getBlocks(); |
| bb = ropBlocks.get(basicBlockIndex); |
| |
| result = new SsaBasicBlock(basicBlockIndex, bb.getLabel(), parent); |
| |
| ropInsns = bb.getInsns(); |
| |
| result.insns.ensureCapacity(ropInsns.size()); |
| for (int i = 0, sz = ropInsns.size() ; i < sz ; i++) { |
| result.insns.add(new NormalSsaInsn (ropInsns.get(i), result)); |
| } |
| |
| result.predecessors = SsaMethod.bitSetFromLabelList( |
| ropBlocks, |
| rmeth.labelToPredecessors(bb.getLabel())); |
| |
| result.successors |
| = SsaMethod.bitSetFromLabelList(ropBlocks, bb.getSuccessors()); |
| |
| result.successorList |
| = SsaMethod.indexListFromLabelList(ropBlocks, |
| bb.getSuccessors()); |
| |
| |
| if (result.successorList.size() != 0) { |
| int primarySuccessor = bb.getPrimarySuccessor(); |
| |
| result.primarySuccessor = (primarySuccessor < 0) |
| ? -1 : ropBlocks.indexOfLabel(primarySuccessor); |
| } |
| |
| return result; |
| } |
| |
| /** |
| * Adds a basic block as a dom child for this block. Used when constructing |
| * the dom tree. |
| * |
| * @param child non-null; new dom child |
| */ |
| void addDomChild(SsaBasicBlock child) { |
| domChildren.add(child); |
| } |
| |
| /** |
| * Gets the dom children for this node. Don't modify this list. |
| * |
| * @return non-null; list of dom children |
| */ |
| ArrayList<SsaBasicBlock> getDomChildren() { |
| return domChildren; |
| } |
| |
| /** |
| * Adds a phi insn to the beginning of this block. The result type of |
| * the phi will be set to void, to indicate that it's currently unknown. |
| * |
| * @param reg >=0 result reg |
| */ |
| void addPhiInsnForReg(int reg) { |
| insns.add(0, new PhiInsn(reg, this)); |
| } |
| |
| /** |
| * Adds a phi insn to the beginning of this block. This is to be used |
| * when the result type or local-association can be determined at phi |
| * insert time. |
| * |
| * @param resultSpec non-null; reg |
| */ |
| void addPhiInsnForReg(RegisterSpec resultSpec) { |
| insns.add(0, new PhiInsn(resultSpec, this)); |
| } |
| |
| /** |
| * Adds an insn to the head of this basic block, just after any phi |
| * insns. |
| * |
| * @param insn non-null; rop-form insn to add |
| */ |
| void addInsnToHead(Insn insn) { |
| SsaInsn newInsn = SsaInsn.makeFromRop(insn, this); |
| insns.add(getCountPhiInsns(), newInsn); |
| parent.onInsnAdded(newInsn); |
| } |
| |
| /** |
| * Replaces the last insn in this block. The provided insn must have |
| * some branchingness. |
| * |
| * @param insn non-null; rop-form insn to add, which must branch. |
| */ |
| void replaceLastInsn(Insn insn) { |
| if (insn.getOpcode().getBranchingness() == Rop.BRANCH_NONE) { |
| throw new IllegalArgumentException("last insn must branch"); |
| } |
| |
| SsaInsn oldInsn = insns.get(insns.size() - 1); |
| SsaInsn newInsn = SsaInsn.makeFromRop(insn, this); |
| |
| insns.set(insns.size() - 1, newInsn); |
| |
| parent.onInsnRemoved(oldInsn); |
| parent.onInsnAdded(newInsn); |
| } |
| |
| /** |
| * Visits each phi insn |
| * @param v callback |
| */ |
| public void forEachPhiInsn(PhiInsn.Visitor v) { |
| |
| int sz = insns.size(); |
| for (int i = 0; i < sz; i++) { |
| SsaInsn insn = insns.get(i); |
| if (insn instanceof PhiInsn) { |
| v.visitPhiInsn((PhiInsn) insn); |
| } else { |
| /* |
| * Presently we assume PhiInsn's are in a continuous |
| * block at the top of the list |
| */ |
| break; |
| } |
| } |
| } |
| |
| /** |
| * Deletes all phi insns. Do this after adding appropriate move insns. |
| */ |
| public void removeAllPhiInsns() { |
| /* |
| * Presently we assume PhiInsn's are in a continuous |
| * block at the top of the list |
| */ |
| |
| insns.subList(0, getCountPhiInsns()).clear(); |
| } |
| |
| /** |
| * Gets the number of phi insns at the top of this basic block. |
| * @return count of phi insns |
| */ |
| private int getCountPhiInsns() { |
| int countPhiInsns; |
| |
| int sz = insns.size(); |
| for (countPhiInsns = 0; countPhiInsns < sz; countPhiInsns++) { |
| SsaInsn insn = insns.get(countPhiInsns); |
| if (!(insn instanceof PhiInsn)) { |
| break; |
| } |
| } |
| |
| return countPhiInsns; |
| } |
| |
| /** |
| * @return non-null;the (mutable) instruction list for this block, |
| * with phi insns at the beginning. |
| */ |
| public ArrayList<SsaInsn> getInsns() { |
| return insns; |
| } |
| |
| /** |
| * @return non-null; the (mutable) list of phi insns for this block |
| */ |
| public List<SsaInsn> getPhiInsns() { |
| return insns.subList(0, getCountPhiInsns()); |
| } |
| |
| /** |
| * @return the block index of this block |
| */ |
| public int getIndex() { |
| return index; |
| } |
| |
| /** |
| * @return the label of this block in rop form |
| */ |
| public int getRopLabel() { |
| return ropLabel; |
| } |
| |
| /** |
| * @return the label of this block in rop form as a hex string |
| */ |
| public String getRopLabelString() { |
| return Hex.u2(ropLabel); |
| } |
| |
| /** |
| * @return non-null;predecessors set, indexed by block index |
| */ |
| public BitSet getPredecessors() { |
| return predecessors; |
| } |
| |
| /** |
| * @return non-null;successors set, indexed by block index |
| */ |
| public BitSet getSuccessors() { |
| return successors; |
| } |
| |
| /** |
| * @return non-null;ordered successor list, containing block indicies |
| */ |
| public IntList getSuccessorList() { |
| return successorList; |
| } |
| |
| /** |
| * @return >= -1; block index of primary successor or -1 if no |
| * primary successor. |
| */ |
| public int getPrimarySuccessorIndex() { |
| return primarySuccessor; |
| } |
| |
| /** |
| * @return rop label of primary successor |
| */ |
| public int getPrimarySuccessorRopLabel() { |
| return parent.blockIndexToRopLabel(primarySuccessor); |
| } |
| |
| /** |
| * @return null-ok; the primary successor block or null if there is none. |
| */ |
| public SsaBasicBlock getPrimarySuccessor() { |
| if (primarySuccessor < 0) { |
| return null; |
| } else { |
| return parent.getBlocks().get(primarySuccessor); |
| } |
| } |
| |
| /** |
| * @return successor list of rop labels |
| */ |
| public IntList getRopLabelSuccessorList() { |
| IntList result = new IntList(successorList.size()); |
| |
| int sz = successorList.size(); |
| |
| for (int i = 0; i < sz; i++) { |
| result.add(parent.blockIndexToRopLabel(successorList.get(i))); |
| } |
| return result; |
| } |
| |
| /** |
| * @return non-null; method that contains this block |
| */ |
| public SsaMethod getParent() { |
| return parent; |
| } |
| |
| /** |
| * Inserts a new empty GOTO block as a predecessor to this block. |
| * All previous predecessors will be predecessors to the new block. |
| * |
| * @return non-null; an appropriately-constructed instance |
| */ |
| public SsaBasicBlock insertNewPredecessor() { |
| SsaBasicBlock newPred = parent.makeNewGotoBlock(); |
| |
| // Update the new block |
| newPred.predecessors = predecessors; |
| newPred.successors.set(index) ; |
| newPred.successorList.add(index); |
| newPred.primarySuccessor = index; |
| |
| |
| // Update us |
| predecessors = new BitSet(parent.getBlocks().size()); |
| predecessors.set(newPred.index); |
| |
| // Update our (soon-to-be) old predecessors |
| for (int i = newPred.predecessors.nextSetBit(0); i >= 0; |
| i = newPred.predecessors.nextSetBit(i + 1)) { |
| |
| SsaBasicBlock predBlock = parent.getBlocks().get(i); |
| |
| predBlock.replaceSuccessor(index, newPred.index); |
| } |
| |
| return newPred; |
| } |
| |
| /** |
| * Constructs and inserts a new empty GOTO block <code>Z</code> between |
| * this block (<code>A</code>) and a current successor block |
| * (<code>B</code>). The new block will replace B as A's successor and |
| * A as B's predecessor. A and B will no longer be directly connected. |
| * If B is listed as a successor multiple times, all references |
| * are replaced. |
| * |
| * @param other current successor (B) |
| * @return non-null; an appropriately-constructed instance |
| */ |
| public SsaBasicBlock insertNewSuccessor(SsaBasicBlock other) { |
| SsaBasicBlock newSucc = parent.makeNewGotoBlock(); |
| |
| if (!successors.get(other.index)) { |
| throw new RuntimeException("Block " + other.getRopLabelString() |
| + " not successor of " + getRopLabelString()); |
| } |
| |
| // Update the new block |
| newSucc.predecessors.set(this.index); |
| newSucc.successors.set(other.index) ; |
| newSucc.successorList.add(other.index); |
| newSucc.primarySuccessor = other.index; |
| |
| // Update us |
| for (int i = successorList.size() - 1 ; i >= 0; i--) { |
| if(successorList.get(i) == other.index) { |
| successorList.set(i, newSucc.index); |
| } |
| } |
| |
| if (primarySuccessor == other.index) { |
| primarySuccessor = newSucc.index; |
| } |
| successors.clear(other.index); |
| successors.set(newSucc.index); |
| |
| // Update "other" |
| other.predecessors.set(newSucc.index); |
| other.predecessors.set(index, successors.get(other.index)); |
| |
| return newSucc; |
| } |
| |
| /** |
| * Replace an old successor with a new successor. |
| * Throws RuntimeException if oldIndex was not a successor. |
| * @param oldIndex index of old successor block |
| * @param newIndex index of new successor block. |
| */ |
| public void replaceSuccessor(int oldIndex, int newIndex) { |
| if (oldIndex == newIndex) { |
| return; |
| } |
| |
| // Update us |
| successors.set(newIndex); |
| |
| if (primarySuccessor == oldIndex) { |
| primarySuccessor = newIndex; |
| } |
| |
| for (int i = successorList.size() - 1 ; i >= 0; i--) { |
| if(successorList.get(i) == oldIndex) { |
| successorList.set(i, newIndex); |
| } |
| } |
| |
| successors.clear(oldIndex); |
| |
| // Update new successor |
| parent.getBlocks().get(newIndex).predecessors.set(index); |
| |
| // Update old successor |
| parent.getBlocks().get(oldIndex).predecessors.clear(index); |
| } |
| |
| |
| /** |
| * Attaches block to an exit block if necessary. If this block |
| * is not an exit predecessor or is the exit block, this block does |
| * nothing. For use by {@link com.android.dx.ssa.SsaMethod#makeExitBlock} |
| * |
| * @param exitBlock non-null; exit block |
| */ |
| public void exitBlockFixup(SsaBasicBlock exitBlock) { |
| if (this == exitBlock) { |
| return; |
| } |
| |
| if (successorList.size() == 0) { |
| /* |
| * This is an exit predecessor. |
| * Set the successor to the exit block |
| */ |
| successors.set(exitBlock.index); |
| successorList.add(exitBlock.index); |
| primarySuccessor = exitBlock.index; |
| exitBlock.predecessors.set(this.index); |
| } |
| } |
| |
| /** |
| * Adds a move instruction to the end of this basic block, just |
| * before the last instruction. If the result of the final instruction |
| * is the source in question, then the move is placed at the beginning of |
| * the primary successor block. This is for unversioned registers. |
| * @param result move destination |
| * @param source move source |
| */ |
| public void addMoveToEnd(RegisterSpec result, RegisterSpec source) { |
| |
| if (result.getReg() == source.getReg()) { |
| // Sometimes we end up with no-op moves. Ignore them here. |
| return; |
| } |
| |
| /* |
| * The last Insn has to be a normal SSA insn: a phi can't branch |
| * or return or cause an exception, etc. |
| */ |
| NormalSsaInsn lastInsn; |
| lastInsn = (NormalSsaInsn)insns.get(insns.size()-1); |
| |
| if (lastInsn.getResult() != null || lastInsn.getSources().size() > 0) { |
| /* |
| * The final insn in this block has a source or result register, |
| * and the moves we may need to place and schedule may interfere. |
| * We need to insert this instruction at the |
| * beginning of the primary successor block instead. We know |
| * this is safe, because when we edge-split earlier, we ensured |
| * that each successor has only us as a predecessor. |
| */ |
| |
| for (int i = successors.nextSetBit(0) |
| ; i >= 0 |
| ; i = successors.nextSetBit(i + 1)) { |
| |
| SsaBasicBlock succ; |
| |
| succ = parent.getBlocks().get(i); |
| succ.addMoveToBeginning(result, source); |
| } |
| } else { |
| /* |
| * We can safely add a move to the end of the block |
| * just before the last instruction because |
| * the final insn does not assign to anything. |
| */ |
| |
| RegisterSpecList sources; |
| sources = RegisterSpecList.make(source); |
| |
| NormalSsaInsn toAdd; |
| |
| toAdd = new NormalSsaInsn( |
| new PlainInsn(Rops.opMove(result.getType()), |
| SourcePosition.NO_INFO, result, sources), this); |
| |
| insns.add(insns.size() - 1, toAdd); |
| |
| movesFromPhisAtEnd++; |
| } |
| } |
| |
| /** |
| * Add a move instruction after the phi insn block. |
| * @param result move destination |
| * @param source move source |
| */ |
| public void addMoveToBeginning (RegisterSpec result, RegisterSpec source) { |
| |
| if (result.getReg() == source.getReg()) { |
| // Sometimes we end up with no-op moves. Ignore them here. |
| return; |
| } |
| |
| RegisterSpecList sources; |
| sources = RegisterSpecList.make(source); |
| |
| NormalSsaInsn toAdd; |
| |
| toAdd = new NormalSsaInsn( |
| new PlainInsn(Rops.opMove(result.getType()), |
| SourcePosition.NO_INFO, result, sources), this); |
| |
| insns.add(getCountPhiInsns(), toAdd); |
| movesFromPhisAtBeginning++; |
| } |
| |
| /** |
| * Sets the register as used in a bitset, taking into account its |
| * category/width. |
| * |
| * @param regsUsed set, indexed by register number |
| * @param rs register to mark as used |
| */ |
| private static void setRegsUsed (BitSet regsUsed, RegisterSpec rs) { |
| regsUsed.set(rs.getReg()); |
| if (rs.getCategory() > 1) { |
| regsUsed.set(rs.getReg() + 1); |
| } |
| } |
| |
| /** |
| * Checks to see if the register is used in a bitset, taking |
| * into account its category/width. |
| * |
| * @param regsUsed set, indexed by register number |
| * @param rs register to mark as used |
| * @return true if register is fully or partially (for the case of wide |
| * registers) used. |
| */ |
| private static boolean checkRegUsed (BitSet regsUsed, RegisterSpec rs) { |
| int reg = rs.getReg(); |
| int category = rs.getCategory(); |
| |
| return regsUsed.get(reg) |
| || (category == 2 ? regsUsed.get(reg + 1) : false); |
| } |
| |
| /** |
| * Ensures that all move operations in this block occur such that |
| * reads of any register happen before writes to that register. |
| * NOTE: caller is expected to returnSpareRegisters()! |
| * |
| * TODO See Briggs, et al "Practical Improvements to the Construction and |
| * Destruction of Static Single Assignment Form" section 5. a) This can |
| * be done in three passes. |
| * @param toSchedule List of instructions. Must consist only of moves. |
| */ |
| private void scheduleUseBeforeAssigned(List<SsaInsn> toSchedule) { |
| BitSet regsUsedAsSources = new BitSet(parent.getRegCount()); |
| // TODO get rid of this |
| BitSet regsUsedAsResults = new BitSet(parent.getRegCount()); |
| |
| int sz = toSchedule.size(); |
| |
| int insertPlace = 0; |
| |
| while (insertPlace < sz) { |
| int oldInsertPlace = insertPlace; |
| |
| // Record all registers used as sources in this block. |
| for (int i = insertPlace; i < sz; i++) { |
| setRegsUsed(regsUsedAsSources, |
| toSchedule.get(i).getSources().get(0)); |
| |
| setRegsUsed(regsUsedAsResults, |
| toSchedule.get(i).getResult()); |
| } |
| |
| /* |
| * If there are no circular dependencies, then there exists |
| * n instructions where n > 1 whose result is not used as a source. |
| */ |
| for (int i = insertPlace; i <sz; i++) { |
| SsaInsn insn = toSchedule.get(i); |
| |
| /* |
| * Move these n registers to the front, since they overwrite |
| * nothing. |
| */ |
| if (!checkRegUsed(regsUsedAsSources, insn.getResult())) { |
| Collections.swap(toSchedule, i, insertPlace++); |
| } |
| } |
| |
| // If we've made no progress in this iteration, there's a |
| // circular dependency. Split it using the temp reg. |
| if (oldInsertPlace == insertPlace) { |
| |
| SsaInsn insnToSplit = null; |
| |
| // Find an insn whose result is used as a source. |
| for (int i = insertPlace; i < sz; i++) { |
| SsaInsn insn = toSchedule.get(i); |
| if (checkRegUsed(regsUsedAsSources, insn.getResult()) |
| && checkRegUsed(regsUsedAsResults, |
| insn.getSources().get(0))) { |
| |
| insnToSplit = insn; |
| // We're going to split this insn--move it to the |
| // front |
| Collections.swap(toSchedule, insertPlace, i); |
| break; |
| } |
| } |
| |
| // At least one insn will be set above |
| |
| RegisterSpec result = insnToSplit.getResult(); |
| RegisterSpec tempSpec = result.withReg( |
| parent.borrowSpareRegister(result.getCategory())); |
| |
| NormalSsaInsn toAdd; |
| |
| toAdd = new NormalSsaInsn( |
| new PlainInsn(Rops.opMove(result.getType()), |
| SourcePosition.NO_INFO, |
| tempSpec, |
| insnToSplit.getSources()), this); |
| |
| toSchedule.add(insertPlace++, toAdd); |
| |
| NormalSsaInsn toReplace; |
| RegisterSpecList newSources; |
| |
| newSources = RegisterSpecList.make(tempSpec); |
| |
| toReplace = new NormalSsaInsn( |
| new PlainInsn(Rops.opMove(result.getType()), |
| SourcePosition.NO_INFO, |
| result, |
| newSources), this); |
| |
| toSchedule.set(insertPlace, toReplace); |
| |
| // size has changed |
| sz = toSchedule.size(); |
| } |
| |
| regsUsedAsSources.clear(); |
| regsUsedAsResults.clear(); |
| } |
| } |
| |
| /** |
| * Adds regV to the live-out list for this block. |
| * Called by the liveness analyzer. |
| * @param regV register that is live-out for this block. |
| */ |
| public void |
| addLiveOut (int regV) { |
| if (liveOut == null) { |
| liveOut = SetFactory.makeLivenessSet(parent.getRegCount()); |
| } |
| |
| liveOut.add(regV); |
| } |
| |
| /** |
| * Adds regV to the live-in list for this block. |
| * Called by the liveness analyzer. |
| * @param regV register that is live-in for this block. |
| */ |
| public void |
| addLiveIn (int regV) { |
| if (liveIn == null) { |
| liveIn = SetFactory.makeLivenessSet(parent.getRegCount()); |
| } |
| |
| liveIn.add(regV); |
| } |
| |
| /** |
| * Returns the set of live-in registers. Valid after register |
| * interference graph has been generated, otherwise empty. |
| * |
| * @return non-null; live-in register set. |
| */ |
| public IntSet getLiveInRegs() { |
| if (liveIn == null) { |
| liveIn = SetFactory.makeLivenessSet(parent.getRegCount()); |
| } |
| return liveIn; |
| } |
| |
| /** |
| * Returns the set of live-out registers. Valid after register |
| * interference graph has been generated, otherwise empty. |
| * |
| * @return non-null; live-out register set. |
| */ |
| public IntSet getLiveOutRegs() { |
| if (liveOut == null) { |
| liveOut = SetFactory.makeLivenessSet(parent.getRegCount()); |
| } |
| return liveOut; |
| } |
| |
| /** |
| * @return true if this is the one-and-only exit block for this method |
| */ |
| public boolean isExitBlock() { |
| return index == parent.getExitBlockIndex(); |
| } |
| |
| /** |
| * Returns true if this block is reachable (that is, it hasn't been |
| * unlinked from the control flow of this method). This currently tests |
| * that it's either the start block or it has predecessors, which suffices |
| * for all current control flow transformations. |
| * |
| * @return true if reachable |
| */ |
| public boolean isReachable() { |
| return index == parent.getEntryBlockIndex() |
| || predecessors.cardinality() > 0; |
| } |
| |
| /** |
| * Sorts move instructions added via <code>addMoveToEnd</code> during |
| * phi removal so that results don't overwrite sources that are used. |
| * For use after all phis have been removed and all calls to |
| * addMoveToEnd() have been made.<p> |
| * |
| * This is necessary because copy-propogation may have left us in a state |
| * where the same basic block has the same register as a phi operand |
| * and a result. In this case, the register in the phi operand always |
| * refers value before any other phis have executed. |
| */ |
| public void scheduleMovesFromPhis() { |
| |
| if (movesFromPhisAtBeginning > 1) { |
| List<SsaInsn> toSchedule; |
| |
| toSchedule = insns.subList(0, movesFromPhisAtBeginning); |
| |
| scheduleUseBeforeAssigned(toSchedule); |
| |
| SsaInsn firstNonPhiMoveInsn = insns.get(movesFromPhisAtBeginning); |
| |
| //TODO it's actually possible that this case never happens, |
| //because a move-exception block, having only one predecessor |
| //in SSA form, perhaps is never on a dominance frontier. |
| if (firstNonPhiMoveInsn.isMoveException()) { |
| if (true) { |
| /* |
| * We've yet to observe this case, and if it can |
| * occur the code written to handle it probably |
| * does not work. |
| */ |
| throw new RuntimeException( |
| "Unexpected: moves from " |
| +"phis before move-exception"); |
| } else { |
| |
| // A move-exception insn must be placed first in this block |
| // We need to move it there, and deal with possible |
| // interference. |
| boolean moveExceptionInterferes = false; |
| |
| int moveExceptionResult |
| = firstNonPhiMoveInsn.getResult().getReg(); |
| |
| // Does the move-exception result reg interfere with the |
| // phi moves? |
| for(SsaInsn insn: toSchedule) { |
| if (insn.isResultReg(moveExceptionResult) |
| || insn.isRegASource(moveExceptionResult)) { |
| moveExceptionInterferes = true; |
| break; |
| } |
| } |
| |
| if (!moveExceptionInterferes) { |
| // The easy case |
| insns.remove(movesFromPhisAtBeginning); |
| insns.add(0, firstNonPhiMoveInsn); |
| } else { |
| // We need to move the result to a spare reg and move it |
| // back. |
| |
| int spareRegister; |
| RegisterSpec originalResultSpec; |
| |
| originalResultSpec = firstNonPhiMoveInsn.getResult(); |
| spareRegister = parent.borrowSpareRegister( |
| originalResultSpec.getCategory()); |
| |
| // We now move it to a spare register |
| firstNonPhiMoveInsn.changeResultReg(spareRegister); |
| RegisterSpec tempSpec = firstNonPhiMoveInsn.getResult(); |
| |
| insns.add(0, firstNonPhiMoveInsn); |
| |
| // And here we move it back |
| |
| NormalSsaInsn toAdd; |
| |
| toAdd = new NormalSsaInsn( |
| new PlainInsn(Rops.opMove( |
| tempSpec.getType()), |
| SourcePosition.NO_INFO, |
| originalResultSpec, |
| RegisterSpecList.make(tempSpec)), |
| this); |
| |
| |
| // Place it immediately after the phi-moves, |
| // overwriting the move-exception that was there. |
| insns.set(movesFromPhisAtBeginning + 1, toAdd); |
| } |
| } |
| } |
| } |
| if (movesFromPhisAtEnd > 1) { |
| scheduleUseBeforeAssigned( |
| insns.subList(insns.size() - movesFromPhisAtEnd - 1, |
| insns.size() - 1)); |
| } |
| |
| // Return registers borrowed here and in scheduleUseBeforeAssigned() |
| parent.returnSpareRegisters(); |
| |
| } |
| |
| /** |
| * Visit all insns in this block |
| * @param visitor callback interface |
| */ |
| public void forEachInsn(SsaInsn.Visitor visitor) { |
| for (SsaInsn insn: insns) { |
| insn.accept(visitor); |
| } |
| } |
| |
| public String toString() { |
| return "{" + index + ":" + Hex.u2(ropLabel) + '}'; |
| } |
| |
| /** |
| * Visitor interface for basic blocks |
| */ |
| public interface Visitor { |
| |
| /** |
| * Indicates a block has been visited by an iterator method. |
| * @param v non-null; block visited |
| * @param parent null-ok; parent node if applicable. |
| */ |
| void visitBlock (SsaBasicBlock v, SsaBasicBlock parent); |
| } |
| } |
