dx/src/com/android/dx/ssa/SsaBasicBlock.java

/*
 * 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.Insn;
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.Rop;
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.util.Hex;
import com.android.dx.util.IntList;
import com.android.dx.util.IntSet;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * An SSA representation of a basic block.
 */
public final class SsaBasicBlock {
    /**
     * {@code non-null;} comparator for instances of this class that
     * just compares block labels
     */
    public static final Comparator<SsaBasicBlock> LABEL_COMPARATOR =
        new LabelComparator();

    /** {@code non-null;} insn list associated with this instance */
    private ArrayList<SsaInsn> insns;

    /** {@code non-null;} predecessor set (by block list index) */
    private BitSet predecessors;

    /** {@code non-null;} successor set (by block list index) */
    private BitSet successors;

    /**
     * {@code non-null;} ordered successor list
     * (same block may be listed more than once)
     */
    private IntList successorList;

    /**
     * block list index of primary successor, or {@code -1} for no primary
     * successor
     */
    private int primarySuccessor = -1;

    /** label of block in rop form */
    private int ropLabel;

    /** {@code 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;

    /**
     * contains last computed value of reachability of this block, or -1
     * if reachability hasn't been calculated yet
     */
    private int reachable = -1;

    /**
     * {@code null-ok;} indexed by reg: the regs that are live-in at
     * this block
     */
    private IntSet liveIn;

    /**
     * {@code null-ok;} indexed by reg: the regs that are live-out at
     * this block
     */
    private IntSet liveOut;

    /**
     * Creates 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 = rmeth.getBlocks();
        BasicBlock bb = ropBlocks.get(basicBlockIndex);
        SsaBasicBlock result =
            new SsaBasicBlock(basicBlockIndex, bb.getLabel(), parent);
        InsnList 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 {@code non-null;} new dom child
     */
    public void addDomChild(SsaBasicBlock child) {
        domChildren.add(child);
    }

    /**
     * Gets the dom children for this node. Don't modify this list.
     *
     * @return {@code non-null;} list of dom children
     */
    public 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 {@code >=0;} result reg
     */
    public 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 {@code non-null;} reg
     */
    public 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 {@code non-null;} rop-form insn to add
     */
    public 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 {@code non-null;} rop-form insn to add, which must branch.
     */
    public 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 {@code non-null;} the 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 {@code non-null;} the (mutable) instruction list for this block,
     * with phi insns at the beginning
     */
    public ArrayList<SsaInsn> getInsns() {
        return insns;
    }

    /**
     * @return {@code 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 {@code non-null;} predecessors set, indexed by block index
     */
    public BitSet getPredecessors() {
        return predecessors;
    }

    /**
     * @return {@code non-null;} successors set, indexed by block index
     */
    public BitSet getSuccessors() {
        return successors;
    }

    /**
     * @return {@code non-null;} ordered successor list, containing block
     * indicies
     */
    public IntList getSuccessorList() {
        return successorList;
    }

    /**
     * @return {@code >= -1;} block index of primary successor or
     * {@code -1} if no primary successor
     */
    public int getPrimarySuccessorIndex() {
        return primarySuccessor;
    }

    /**
     * @return rop label of primary successor
     */
    public int getPrimarySuccessorRopLabel() {
        return parent.blockIndexToRopLabel(primarySuccessor);
    }

    /**
     * @return {@code null-ok;} the primary successor block or {@code 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 {@code 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 {@code 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} between
     * this block ({@code A}) and a current successor block
     * ({@code B}). 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 {@code 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;
    }

    /**
     * Replaces an old successor with a new successor. This will throw
     * RuntimeException if {@code 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);
    }

    /**
     * Removes a successor from this block's successor list.
     *
     * @param oldIndex index of successor block to remove
     */
    public void removeSuccessor(int oldIndex) {
        int removeIndex = 0;

        for (int i = successorList.size() - 1; i >= 0; i--) {
            if (successorList.get(i) == oldIndex) {
                removeIndex = i;
            } else {
                primarySuccessor = successorList.get(i);
            }
        }

        successorList.removeIndex(removeIndex);
        successors.clear(oldIndex);
        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 {@code 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 = RegisterSpecList.make(source);
            NormalSsaInsn toAdd = new NormalSsaInsn(
                    new PlainInsn(Rops.opMove(result.getType()),
                            SourcePosition.NO_INFO, result, sources), this);

            insns.add(insns.size() - 1, toAdd);

            movesFromPhisAtEnd++;
        }
    }

    /**
     * Adds 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 = RegisterSpecList.make(source);
        NormalSsaInsn 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 = new NormalSsaInsn(
                        new PlainInsn(Rops.opMove(result.getType()),
                                SourcePosition.NO_INFO,
                                tempSpec,
                                insnToSplit.getSources()), this);

                toSchedule.add(insertPlace++, toAdd);

                RegisterSpecList newSources = RegisterSpecList.make(tempSpec);

                NormalSsaInsn toReplace = new NormalSsaInsn(
                        new PlainInsn(Rops.opMove(result.getType()),
                                SourcePosition.NO_INFO,
                                result,
                                newSources), this);

                toSchedule.set(insertPlace, toReplace);

                // The size changed.
                sz = toSchedule.size();
            }

            regsUsedAsSources.clear();
            regsUsedAsResults.clear();
        }
    }

    /**
     * Adds {@code regV} to the live-out list for this block. This is 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 {@code regV} to the live-in list for this block. This is
     * 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 {@code 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 {@code 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 was last calculated to be reachable.
     * Recalculates reachability if value has never been computed.
     *
     * @return {@code true} if reachable
     */
    public boolean isReachable() {
        if (reachable == -1) {
            parent.computeReachability();
        }
        return (reachable == 1);
    }

    /**
     * Sets reachability of block to specified value
     *
     * @param reach new value of reachability for block
     */
    public void setReachable(int reach) {
        reachable = reach;
    }

    /**
     * Sorts move instructions added via {@code addMoveToEnd} 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) {
                        // This is 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.
                         */
                        RegisterSpec originalResultSpec
                            = firstNonPhiMoveInsn.getResult();
                        int 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 = 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();

    }

    /**
     * Visits all insns in this block.
     *
     * @param visitor {@code non-null;} callback interface
     */
    public void forEachInsn(SsaInsn.Visitor visitor) {
        // This gets called a LOT, and not using an iterator
        // saves a lot of allocations and reduces memory usage
        int len = insns.size();
        for (int i = 0; i < len; i++) {
            insns.get(i).accept(visitor);
        }
    }

    /** {@inheritDoc} */
    @Override
    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 {@code non-null;} block visited
         * @param parent {@code null-ok;} parent node if applicable
         */
        void visitBlock (SsaBasicBlock v, SsaBasicBlock parent);
    }

    /**
     * Label comparator.
     */
    public static final class LabelComparator
            implements Comparator<SsaBasicBlock> {
        /** {@inheritDoc} */
        public int compare(SsaBasicBlock b1, SsaBasicBlock b2) {
            int label1 = b1.ropLabel;
            int label2 = b2.ropLabel;

            if (label1 < label2) {
                return -1;
            } else if (label1 > label2) {
                return 1;
            } else {
                return 0;
            }
        }
    }
}