FileDocCategorySizeDatePackage
SsaMethod.javaAPI DocAndroid 1.5 API25056Wed May 06 22:41:02 BST 2009com.android.dx.ssa

SsaMethod

public final class SsaMethod extends Object
A method in SSA form

Fields Summary
private ArrayList
blocks
basic blocks, indexed by block index
private int
entryBlockIndex
Index of first executed block in method
private int
exitBlockIndex
Index of exit block, which exists only in SSA form, or or -1 if there is none
private int
registerCount
private int
spareRegisterBase
private int
borrowedSpareRegisters
private int
maxLabel
really one greater than the max label
private final int
paramWidth
the total width, in register-units, of the method's parameters
private final boolean
isStatic
true if this method has no 'this' pointer argument
private SsaInsn[]
definitionList
indexed by register: the insn where said register is defined or null if undefined. null until (lazily) created.
private ArrayList[]
useList
indexed by register: the list of all insns that use a register
private List[]
unmodifiableUseList
A version of useList with each List unmodifiable
private boolean
backMode
"back-convert mode". Set during back-conversion when registers are about to be mapped into a non-SSA namespace. When true, use and def lists are unavailable. TODO remove this mode, plase the functionality elsewhere
Constructors Summary
private SsaMethod(int paramWidth, boolean isStatic)
Constructor

param
paramWidth the total width, in register-units, of the method's parameters
param
isStatic true if this method has no 'this' pointer argument

        this.paramWidth = paramWidth;
        this.isStatic = isStatic;
Methods Summary
static java.util.BitSetbitSetFromLabelList(com.android.dx.rop.code.BasicBlockList blocks, com.android.dx.util.IntList labelList)
Builds a BitSet of block indices from a basic block list and a list of labels taken from Rop form

param
blocks Rop blocks
param
labelList list of rop block labels
return
BitSet of block indices


        BitSet result;

        result = new BitSet(blocks.size());

        for (int i = 0, sz = labelList.size() ; i < sz ; i++) {
            result.set(blocks.indexOfLabel(labelList.get(i)));
        }

        return result;
public intblockIndexToRopLabel(int bi)

param
bi block index or -1 for none
return
rop label or -1 if bi was -1

        if (bi < 0) {
            return -1;
        }
        return blocks.get(bi).getRopLabel();
public intborrowSpareRegister(int category)
Borrow a register to use as a temp. Used in the phi removal process. Call returnSpareRegisters() when done.

param
category width (1 or 2) of the register
return
register number to use

        int result;

        result = spareRegisterBase + borrowedSpareRegisters;

        borrowedSpareRegisters += category;

        registerCount = Math.max(registerCount, result + category);

        return result;
private voidbuildUseList()
Builds useList and unmodifiableUseList.

        if (backMode) {
            throw new RuntimeException("No use list in back mode");
        }

        useList = new ArrayList[registerCount];

        for (int i = 0 ; i < registerCount; i++) {
            useList[i] = new ArrayList();
        }

        forEachInsn(new SsaInsn.Visitor() {
            /** {@inheritDoc} */
            public void visitMoveInsn (NormalSsaInsn insn) {
                addToUses(insn);
            }
            /** {@inheritDoc} */
            public void visitPhiInsn (PhiInsn phi) {
                addToUses(phi);
            }
            /** {@inheritDoc} */
            public void visitNonMoveInsn (NormalSsaInsn insn) {
                addToUses(insn);
            }
            /**
             * Adds specified insn to the uses list for all of its sources.
             * @param insn non-null; insn to process
             */
            private void addToUses(SsaInsn insn) {
                RegisterSpecList rl = insn.getSources();
                int sz = rl.size();

                for (int i = 0; i < sz; i++) {
                    useList[rl.get(i).getReg()].add(insn);
                }
            }
        });

        unmodifiableUseList = new List[registerCount];

        for (int i = 0 ; i < registerCount; i++) {
            unmodifiableUseList[i] = Collections.unmodifiableList(useList[i]);
        }
private voidconvertRopToSsaBlocks(com.android.dx.rop.code.RopMethod rmeth)


        BasicBlockList ropBlocks;

        ropBlocks = rmeth.getBlocks();

        blocks = new ArrayList<SsaBasicBlock>(ropBlocks.size() + 2);

        for (int i = 0, sz = ropBlocks.size() ; i < sz ; i++) {
            SsaBasicBlock sbb;

            sbb = SsaBasicBlock.newFromRop(rmeth, i, this);

            blocks.add(sbb);
        }

        // Add an no-op entry block
        int origEntryBlockIndex = rmeth.getBlocks()
                .indexOfLabel(rmeth.getFirstLabel());

        SsaBasicBlock entryBlock
                = blocks.get(origEntryBlockIndex).insertNewPredecessor();

        entryBlockIndex = entryBlock.getIndex();
        exitBlockIndex = -1; // this gets made later
public voiddeleteInsns(java.util.Set deletedInsns)
Deletes all insns in the set from this method

param
deletedInsns non-null; insns to delete

        for (SsaBasicBlock block: getBlocks()) {
            ArrayList<SsaInsn> insns = block.getInsns();

            for (int i = insns.size() - 1; i >= 0; i--) {
                SsaInsn insn = insns.get(i);

                if (deletedInsns.contains(insn)) {
                    onInsnRemoved(insn);
                    insns.remove(i);
                }
            }

            // Check to see if we need to add a GOTO

            int insnsSz = insns.size();
            SsaInsn lastInsn = (insnsSz == 0) ? null : insns.get(insnsSz - 1);

            if (block != getExitBlock() && (insnsSz == 0
                    || lastInsn.getOriginalRopInsn() == null
                    || lastInsn.getOriginalRopInsn().getOpcode()
                        .getBranchingness() == Rop.BRANCH_NONE)) {
                // We managed to eat a throwable insn

                Insn gotoInsn = new PlainInsn(Rops.GOTO,
                        SourcePosition.NO_INFO, null, RegisterSpecList.EMPTY);
                insns.add(SsaInsn.makeFromRop(gotoInsn, block));
            }
        }
public voidforEachBlockDepthFirst(boolean reverse, SsaBasicBlock.Visitor v)
Walk the basic block tree in depth-first order, calling the visitor method once for every block. This depth-first walk may be run forward from the method entry point or backwards from the method exit points.

param
reverse true if this should walk backwards from the exit points
param
v non-null; callback interface. parentis set unless this is the root node

        BitSet visited = new BitSet(blocks.size());
        // We push the parent first, then the child on the stack
        Stack<SsaBasicBlock> stack = new Stack<SsaBasicBlock>();

        SsaBasicBlock rootBlock = reverse ? getExitBlock() : getEntryBlock();

        if (rootBlock == null) {
            // in the case there's no exit block
            return;
        }

        stack.add(null);    // start with null parent
        stack.add(rootBlock);

        while (stack.size() > 0) {
            SsaBasicBlock cur = stack.pop();
            SsaBasicBlock parent = stack.pop();

            if (!visited.get(cur.getIndex())) {
                BitSet children
                        = reverse ? cur.getPredecessors() : cur.getSuccessors();
                for (int i = children.nextSetBit(0); i >= 0
                        ; i = children.nextSetBit(i + 1)) {
                    stack.add(cur);
                    stack.add(blocks.get(i));
                }
                visited.set(cur.getIndex());
                v.visitBlock(cur, parent);
            }
        }
public voidforEachBlockDepthFirstDom(SsaBasicBlock.Visitor v)
Visits blocks in dom-tree order, starting at the current node. The parent parameter of the Visitor.visitBlock callback is currently always set to null.

param
v non-null; callback interface

        BitSet visited = new BitSet(getBlocks().size());
        Stack<SsaBasicBlock> stack = new Stack<SsaBasicBlock>();

        stack.add(getEntryBlock());

        while (stack.size() > 0) {
            SsaBasicBlock cur = stack.pop();
            ArrayList<SsaBasicBlock> curDomChildren = cur.getDomChildren();

            if (!visited.get(cur.getIndex())) {
                // We walk the tree this way for historical reasons...
                for (int i = curDomChildren.size() - 1; i >= 0; i--) {
                    SsaBasicBlock child = curDomChildren.get(i);
                    stack.add(child);
                }
                visited.set(cur.getIndex());
                v.visitBlock(cur, null);
            }
        }
public voidforEachInsn(SsaInsn.Visitor visitor)
Visit all insns in this method

param
visitor non-null; callback interface

        for (SsaBasicBlock block: blocks) {
            block.forEachInsn(visitor);
        }
public voidforEachPhiInsn(PhiInsn.Visitor v)
Visits each phi insn in this method

param
v non-null; callback

        for (SsaBasicBlock block: blocks) {
            block.forEachPhiInsn(v);
        }
public java.util.ArrayListgetBlocks()

return
non-null; basic block list, do not modify.

        return blocks;
public intgetCountReachableBlocks()
Returns the count of reachable blocks in this method: blocks that have predecessors (or are the start block)

return
>= 0; number of reachable basic blocks

        int ret = 0;

        for (SsaBasicBlock b: blocks) {
            // Blocks that have been disconnected don't count.
            if (b.isReachable()) {
                ret++;
            }
        }

        return ret;
public SsaInsngetDefinitionForRegister(int reg)
Returns the insn that defines the given register

param
reg register in question
return
insn (actual instance from code) that defined this reg or null if reg is not defined.

        if (backMode) {
            throw new RuntimeException("No def list in back mode");
        }

        if (definitionList != null) {
            return definitionList[reg];
        }

        definitionList = new SsaInsn[getRegCount()];

        forEachInsn(new SsaInsn.Visitor() {
            public void visitMoveInsn (NormalSsaInsn insn) {
                definitionList[insn.getResult().getReg()] = insn;
            }
            public void visitPhiInsn (PhiInsn phi) {
                definitionList[phi.getResult().getReg()] = phi;
            }
            public void visitNonMoveInsn (NormalSsaInsn insn) {
                RegisterSpec result = insn.getResult();
                if (result != null) {
                    definitionList[insn.getResult().getReg()] = insn;
                }
            }
        });

        return definitionList[reg];
public SsaBasicBlockgetEntryBlock()

return
first execution block

        return blocks.get(entryBlockIndex);
public intgetEntryBlockIndex()

return
block index of first execution block

        return entryBlockIndex;
public SsaBasicBlockgetExitBlock()

return
null-ok; block of exit block or null if there is none

        return exitBlockIndex < 0 ? null : blocks.get(exitBlockIndex);
public intgetExitBlockIndex()

return
block index of exit block or -1 if there is none

        return exitBlockIndex;
private static SsaInsngetGoto(SsaBasicBlock block)
Gets a new GOTO insn.

param
block block to which this GOTO will be added (not it's destination!)
return
an appropriately-constructed instance.

        return new NormalSsaInsn (
                new PlainInsn(Rops.GOTO, SourcePosition.NO_INFO,
                    null, RegisterSpecList.EMPTY), block);
public intgetParamWidth()

return
the total width, in register units, of the method's parameters

        return paramWidth;
public intgetRegCount()

return
count of registers used in this method

        return registerCount;
public java.util.ArrayList[]getUseListCopy()
Returns a modifiable copy of the register use list.

return
modifiable copy of the use-list, indexed by register

        if (useList == null) {
            buildUseList();
        }

        ArrayList<SsaInsn>[] useListCopy
                = (ArrayList<SsaInsn>[])(new ArrayList[registerCount]);

        for (int i = 0; i < registerCount; i++) {
            useListCopy[i] = (ArrayList<SsaInsn>)(new ArrayList(useList[i]));
        }

        return useListCopy;
public java.util.ListgetUseListForRegister(int reg)
Returns the list of all source uses (not results) for a register

param
reg register in question
return
unmodifiable instruction list


        if (unmodifiableUseList == null) {
            buildUseList();
        }

        return unmodifiableUseList[reg];
public static com.android.dx.util.IntListindexListFromLabelList(com.android.dx.rop.code.BasicBlockList ropBlocks, com.android.dx.util.IntList labelList)
Builds an IntList of block indices from a basic block list and a list of labels taken from Rop form

param
ropBlocks Rop blocks
param
labelList list of rop block labels
return
IntList of block indices


        IntList result;

        result = new IntList(labelList.size());

        for (int i = 0, sz = labelList.size() ; i < sz ; i++) {
            result.add(ropBlocks.indexOfLabel(labelList.get(i)));
        }

        return result;
public booleanisRegALocal(com.android.dx.rop.code.RegisterSpec spec)
Checks to see if the given SSA reg is ever associated with a local local variable. Each SSA reg may be associated with at most one local var.

param
spec non-null; ssa reg
return
true if reg is ever associated with a local

        SsaInsn defn = getDefinitionForRegister(spec.getReg());

        if (defn == null) {
            // version 0 registers are never used as locals
            return false;
        }

        // Does the definition have a local associated with it?
        if (defn.getLocalAssignment() != null) return true;

        // If not, is there a mark-local insn?
        for (SsaInsn use: getUseListForRegister(spec.getReg())) {
            Insn insn = use.getOriginalRopInsn();

            if (insn != null
                    && insn.getOpcode().getOpcode() == RegOps.MARK_LOCAL) {
                return true;
            }
        }
        
        return false;
public booleanisStatic()
Returns true if this is a static method.

return
true if this is a static method

        return isStatic;
voidmakeExitBlock()
Creates an exit block and attaches it to the CFG if this method exits. Methods that never exit will not have an exit block. This is called after edge-splitting and phi insertion, since the edges going into the exit block should not be considered in those steps.

        if (exitBlockIndex >= 0) {
            throw new RuntimeException("must be called at most once");
        }

        exitBlockIndex = blocks.size();
        SsaBasicBlock exitBlock
                = new SsaBasicBlock(exitBlockIndex, maxLabel++, this);

        blocks.add(exitBlock);

        for (SsaBasicBlock block: blocks) {
            block.exitBlockFixup(exitBlock);
        }

        if (exitBlock.getPredecessors().cardinality() == 0) {
            // In cases where there is no exit...
            blocks.remove(exitBlockIndex);
            exitBlockIndex = -1;
            maxLabel--;
        }
public SsaBasicBlockmakeNewGotoBlock()
Makes a new basic block for this method, which is empty besides a single GOTO. Successors and predecessors are not yet set.

return
new block

        int newIndex = blocks.size();
        SsaBasicBlock newBlock = new SsaBasicBlock(newIndex, maxLabel++, this);

        newBlock.getInsns().add(getGoto(newBlock));
        blocks.add(newBlock);

        return newBlock;
public intmakeNewSsaReg()
Makes a new SSA register. For use after renaming has completed.

return
>=0 new SSA register.

        int reg = registerCount++;
        spareRegisterBase = registerCount;
        onInsnsChanged();
        return reg;
public voidmapRegisters(RegisterMapper mapper)
Remaps unversioned registers.

param
mapper maps old registers to new.


        for (SsaBasicBlock block: getBlocks()) {
            for (SsaInsn insn: block.getInsns()) {
                insn.mapRegisters(mapper);
            }
        }        
        
        registerCount = mapper.getNewRegisterCount();
        spareRegisterBase = registerCount;
static com.android.dx.ssa.SsaMethodnewFromRopMethod(com.android.dx.rop.code.RopMethod rmeth, int paramWidth, boolean isStatic)

param
rmeth RopMethod to convert from
param
paramWidth the total width, in register-units, of the method's parameters
param
isStatic true if this method has no 'this' pointer argument
return
SsaMethod representation


                                        
         
              
        SsaMethod result;

        result = new SsaMethod(paramWidth, isStatic);

        result.maxLabel = rmeth.getBlocks().getMaxLabel();
        result.registerCount = rmeth.getBlocks().getRegCount();
        result.spareRegisterBase = result.registerCount;

        result.convertRopToSsaBlocks(rmeth);

        return result;
voidonInsnAdded(SsaInsn insn)
Adds an insn to both the use and def lists. For use when adding a new insn to the method.

param
insn non-null; insn to add

        onSourcesChanged(insn, null);
        updateOneDefinition(insn, null);
voidonInsnRemoved(SsaInsn insn)
Removes an instruction from use and def lists. For use during instruction removal.

param
insn non-null; insn to remove.

         if (useList != null) {
             removeFromUseList(insn, insn.getSources());
         }

         RegisterSpec resultReg = insn.getResult();
         if (definitionList != null && resultReg != null) {
             definitionList[resultReg.getReg()] = null;
         }
public voidonInsnsChanged()
Indicates that the instruction list has changed or the SSA register count has increased, so that internal datastructures that rely on it should be rebuild. In general, the various other on* methods should be called in preference when changes occur if they are applicable.

        // Definition list will need to be recomputed
        definitionList = null;

        // Use list will need to be recomputed
        useList = null;
        unmodifiableUseList = null;
voidonSourceChanged(SsaInsn insn, com.android.dx.rop.code.RegisterSpec oldSource, com.android.dx.rop.code.RegisterSpec newSource)
Updates the use list for a single change in source register.

param
insn non-null; insn being changed
param
oldSource null-ok; The source that was used, if applicable
param
newSource non-null; the new source being used


        if (useList == null) return;
        
        if (oldSource != null) {
            int reg = oldSource.getReg();
            useList[reg].remove(insn);
        }

        int reg = newSource.getReg();
        if (useList.length <= reg) {
            useList = null;
            return;
        }
        useList[reg].add(insn);
voidonSourcesChanged(SsaInsn insn, com.android.dx.rop.code.RegisterSpecList oldSources)
Updates the use list for a source list change.

param
insn insn non-null; insn being changed. insn.getSources() must return the new source list.
param
oldSources null-ok; list of sources that were previously used.

        if (useList == null) return;

        if (oldSources != null) {
            removeFromUseList(insn, oldSources);
        }

        RegisterSpecList sources = insn.getSources();
        int szNew = sources.size();

        for(int i = 0; i < szNew; i++) {
            int reg = sources.get(i).getReg();
            useList[reg].add(insn);
        }
private voidremoveFromUseList(SsaInsn insn, com.android.dx.rop.code.RegisterSpecList oldSources)
Removes a given insn from the use lists for the given oldSources (rather than the sources currently returned by insn.getSources()).

param
insn non-null; insn in question
param
oldSources null-ok; registers whose use lists insn should be removed form.

        if (oldSources == null) {
            return;
        }
        int szNew = oldSources.size();
        for(int i = 0; i < szNew; i++) {
            if (!useList[oldSources.get(i).getReg()].remove(insn)) {
                throw new RuntimeException("use not found");
            }
        }
public voidreturnSpareRegisters()
Returns all borrowed registers.

        borrowedSpareRegisters = 0;
public voidsetBackMode()
Set "back-convert mode". Set during back-conversion when registers are about to be mapped into a non-SSA namespace. When true, use and def lists are unavailable.

        backMode = true;
        useList = null;
        definitionList = null;
voidsetNewRegCount(int newRegCount)
Sets the new register count after renaming.

param
newRegCount new register count

        registerCount = newRegCount;
        spareRegisterBase = registerCount;
        onInsnsChanged();
voidupdateOneDefinition(SsaInsn insn, com.android.dx.rop.code.RegisterSpec oldResult)
Updates a single definition.

param
insn non-null; insn who's result should be recorded as a definition
param
oldResult null-ok; a previous result that should be no longer considered a definition by this insn

        if (definitionList == null) return;
        if (oldResult != null) {
            int reg = oldResult.getReg();
            definitionList[reg] = null;
        }

        RegisterSpec resultReg = insn.getResult();
        if (resultReg != null) {
            int reg = resultReg.getReg();

            if (definitionList[reg] != null) {
                throw new RuntimeException("Duplicate add of insn");
            } else {
                definitionList[resultReg.getReg()] = insn;
            }
        }