FileDocCategorySizeDatePackage
SsaMethod.javaAPI DocAndroid 5.1 API26950Thu Mar 12 22:18:30 GMT 2015com.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 {@code -1} if there is none
private int
registerCount
total number of registers required
private int
spareRegisterBase
first register number to use for any temporary "spares"
private int
borrowedSpareRegisters
current count of spare registers used
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 {@code 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, and place the functionality elsewhere
Constructors Summary
private SsaMethod(com.android.dx.rop.code.RopMethod ropMethod, int paramWidth, boolean isStatic)
Constructs an instance.

param
ropMethod {@code non-null;} the original rop-form method that this instance is based on
param
paramWidth the total width, in register-units, of the method's parameters
param
isStatic {@code true} if this method has no {@code this} pointer argument

        this.paramWidth = paramWidth;
        this.isStatic = isStatic;
        this.backMode = false;
        this.maxLabel = ropMethod.getBlocks().getMaxLabel();
        this.registerCount = ropMethod.getBlocks().getRegCount();
        this.spareRegisterBase = registerCount;
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 = 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 {@code -1} for none
return
rop label or {code -1} if {@code bi} was {@code -1}

        if (bi < 0) {
            return -1;
        }
        return blocks.get(bi).getRopLabel();
public intborrowSpareRegister(int category)
Borrows 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 = 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 {@code 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]);
        }
public voidcomputeReachability()
Computes reachability for all blocks in the method. First clears old values from all blocks, then starts with the entry block and walks down the control flow graph, marking all blocks it finds as reachable.

        for (SsaBasicBlock block : blocks) {
            block.setReachable(0);
        }

        ArrayList<SsaBasicBlock> blockList = new ArrayList<SsaBasicBlock>();
        blockList.add(this.getEntryBlock());

        while (!blockList.isEmpty()) {
            SsaBasicBlock block = blockList.remove(0);
            if (block.isReachable()) continue;

            block.setReachable(1);
            BitSet succs = block.getSuccessors();
            for (int i = succs.nextSetBit(0); i >= 0;
                     i = succs.nextSetBit(i + 1)) {
                blockList.add(blocks.get(i));
            }
        }
private voidconvertRopToSsaBlocks(com.android.dx.rop.code.RopMethod rmeth)

        BasicBlockList ropBlocks = rmeth.getBlocks();
        int sz = ropBlocks.size();

        blocks = new ArrayList<SsaBasicBlock>(sz + 2);

        for (int i = 0; i < sz; i++) {
            SsaBasicBlock 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 {@code 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));

                // Remove secondary successors from this block
                BitSet succs = block.getSuccessors();
                for (int i = succs.nextSetBit(0); i >= 0;
                         i = succs.nextSetBit(i + 1)) {
                    if (i != block.getPrimarySuccessorIndex()) {
                        block.removeSuccessor(i);
                    }
                }
            }
        }
public voidforEachBlockDepthFirst(boolean reverse, SsaBasicBlock.Visitor v)
Walks 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 {@code non-null;} callback interface. {@code parent} is 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 {@code parent} parameter of the Visitor.visitBlock callback is currently always set to null.

param
v {@code 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)
Visits all insns in this method.

param
visitor {@code 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 {@code non-null;} callback.

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

return
{@code 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
{@code >= 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
{@code null-ok;} block of exit block or {@code null} if there is none

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

return
block index of exit block or {@code -1} if there is none

        return exitBlockIndex;
private static SsaInsngetGoto(SsaBasicBlock block)
Gets a new {@code 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 = 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 {@code 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 {@code true} if this is a static method.

return
{@code 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 {@code 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
{@code >=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;
public static com.android.dx.ssa.SsaMethodnewFromRopMethod(com.android.dx.rop.code.RopMethod ropMethod, int paramWidth, boolean isStatic)

param
ropMethod rop-form method to convert from
param
paramWidth the total width, in register-units, of the method's parameters
param
isStatic {@code true} if this method has no {@code this} pointer argument

        SsaMethod result = new SsaMethod(ropMethod, paramWidth, isStatic);

        result.convertRopToSsaBlocks(ropMethod);

        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 {@code 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 {@code 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 {@code non-null;} insn being changed
param
oldSource {@code null-ok;} The source that was used, if applicable
param
newSource {@code 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 {@code insn non-null;} insn being changed. {@code insn.getSources()} must return the new source list.
param
oldSources {@code 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 {@code insn} from the use lists for the given {@code oldSources} (rather than the sources currently returned by insn.getSources()).

param
insn {@code non-null;} insn in question
param
oldSources {@code null-ok;} registers whose use lists {@code 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()
Sets "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 {@code non-null;} insn who's result should be recorded as a definition
param
oldResult {@code 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;
            }
        }