FileDocCategorySizeDatePackage
EscapeAnalysis.javaAPI DocAndroid 5.1 API34905Thu Mar 12 22:18:30 GMT 2015com.android.dx.ssa

EscapeAnalysis

public class EscapeAnalysis extends Object
Simple intraprocedural escape analysis. Finds new arrays that don't escape the method they are created in and replaces the array values with registers.

Fields Summary
private SsaMethod
ssaMeth
method we're processing
private int
regCount
ssaMeth.getRegCount()
private ArrayList
latticeValues
Lattice values for each object register group
Constructors Summary
private EscapeAnalysis(SsaMethod ssaMeth)
Constructs an instance.

param
ssaMeth method to process

        this.ssaMeth = ssaMeth;
        this.regCount = ssaMeth.getRegCount();
        this.latticeValues = new ArrayList<EscapeSet>();
Methods Summary
private voidaddEdge(com.android.dx.ssa.EscapeAnalysis$EscapeSet parentSet, com.android.dx.ssa.EscapeAnalysis$EscapeSet childSet)
Creates a link in the lattice between two EscapeSets due to a put instruction. The object being put is the child and the object being put into is the parent. A child set must always have an escape state at least as high as its parent.

param
parentSet {@code non-null;} the EscapeSet for the object being put into
param
childSet {@code non-null;} the EscapeSet for the object being put

        if (!childSet.parentSets.contains(parentSet)) {
            childSet.parentSets.add(parentSet);
        }
        if (!parentSet.childSets.contains(childSet)) {
            parentSet.childSets.add(childSet);
        }
private intfindSetIndex(com.android.dx.rop.code.RegisterSpec reg)
Finds the index in the lattice for a particular register. Returns the size of the lattice if the register wasn't found.

param
reg {@code non-null;} register being looked up
return
index of the register or size of the lattice if it wasn't found.

        int i;
        for (i = 0; i < latticeValues.size(); i++) {
            EscapeSet e = latticeValues.get(i);
            if (e.regSet.get(reg.getReg())) {
                return i;
            }
        }
        return i;
private SsaInsngetInsnForMove(SsaInsn moveInsn)
Finds the corresponding instruction for a given move result

param
moveInsn {@code non-null;} a move result instruction
return
{@code non-null;} the instruction that produces the result for the move

        int pred = moveInsn.getBlock().getPredecessors().nextSetBit(0);
        ArrayList<SsaInsn> predInsns = ssaMeth.getBlocks().get(pred).getInsns();
        return predInsns.get(predInsns.size()-1);
private SsaInsngetMoveForInsn(SsaInsn insn)
Finds the corresponding move result for a given instruction

param
insn {@code non-null;} an instruction that must always be followed by a move result
return
{@code non-null;} the move result for the given instruction

        int succ = insn.getBlock().getSuccessors().nextSetBit(0);
        ArrayList<SsaInsn> succInsns = ssaMeth.getBlocks().get(succ).getInsns();
        return succInsns.get(0);
private voidinsertExceptionThrow(SsaInsn insn, com.android.dx.rop.code.RegisterSpec index, java.util.HashSet deletedInsns)
Replaces instructions that trigger an ArrayIndexOutofBounds exception with an actual throw of the exception.

param
insn {@code non-null;} instruction causing the exception
param
index {@code non-null;} index value that is out of bounds
param
deletedInsns {@code non-null;} set of instructions marked for deletion

        // Create a new ArrayIndexOutOfBoundsException
        CstType exception =
            new CstType(Exceptions.TYPE_ArrayIndexOutOfBoundsException);
        insertThrowingInsnBefore(insn, RegisterSpecList.EMPTY, null,
                                     RegOps.NEW_INSTANCE, exception);

        // Add a successor block with a move result pseudo for the exception
        SsaBasicBlock currBlock = insn.getBlock();
        SsaBasicBlock newBlock =
            currBlock.insertNewSuccessor(currBlock.getPrimarySuccessor());
        SsaInsn newInsn = newBlock.getInsns().get(0);
        RegisterSpec newReg =
            RegisterSpec.make(ssaMeth.makeNewSsaReg(), exception);
        insertPlainInsnBefore(newInsn, RegisterSpecList.EMPTY, newReg,
                                  RegOps.MOVE_RESULT_PSEUDO, null);

        // Add another successor block to initialize the exception
        SsaBasicBlock newBlock2 =
            newBlock.insertNewSuccessor(newBlock.getPrimarySuccessor());
        SsaInsn newInsn2 = newBlock2.getInsns().get(0);
        CstNat newNat = new CstNat(new CstString("<init>"), new CstString("(I)V"));
        CstMethodRef newRef = new CstMethodRef(exception, newNat);
        insertThrowingInsnBefore(newInsn2, RegisterSpecList.make(newReg, index),
                                     null, RegOps.INVOKE_DIRECT, newRef);
        deletedInsns.add(newInsn2);

        // Add another successor block to throw the new exception
        SsaBasicBlock newBlock3 =
            newBlock2.insertNewSuccessor(newBlock2.getPrimarySuccessor());
        SsaInsn newInsn3 = newBlock3.getInsns().get(0);
        insertThrowingInsnBefore(newInsn3, RegisterSpecList.make(newReg), null,
                                     RegOps.THROW, null);
        newBlock3.replaceSuccessor(newBlock3.getPrimarySuccessorIndex(),
                                       ssaMeth.getExitBlock().getIndex());
        deletedInsns.add(newInsn3);
private voidinsertPlainInsnBefore(SsaInsn insn, com.android.dx.rop.code.RegisterSpecList newSources, com.android.dx.rop.code.RegisterSpec newResult, int newOpcode, com.android.dx.rop.cst.Constant cst)
Inserts a new PlainInsn before the given instruction. TODO: move this somewhere more appropriate

param
insn {@code non-null;} instruction to insert before
param
newSources {@code non-null;} sources of new instruction
param
newResult {@code non-null;} result of new instruction
param
newOpcode opcode of new instruction
param
cst {@code null-ok;} constant for new instruction, if any


        Insn originalRopInsn = insn.getOriginalRopInsn();
        Rop newRop;
        if (newOpcode == RegOps.MOVE_RESULT_PSEUDO) {
            newRop = Rops.opMoveResultPseudo(newResult.getType());
        } else {
            newRop = Rops.ropFor(newOpcode, newResult, newSources, cst);
        }

        Insn newRopInsn;
        if (cst == null) {
            newRopInsn = new PlainInsn(newRop,
                    originalRopInsn.getPosition(), newResult, newSources);
        } else {
            newRopInsn = new PlainCstInsn(newRop,
                originalRopInsn.getPosition(), newResult, newSources, cst);
        }

        NormalSsaInsn newInsn = new NormalSsaInsn(newRopInsn, insn.getBlock());
        List<SsaInsn> insns = insn.getBlock().getInsns();

        insns.add(insns.lastIndexOf(insn), newInsn);
        ssaMeth.onInsnAdded(newInsn);
private voidinsertThrowingInsnBefore(SsaInsn insn, com.android.dx.rop.code.RegisterSpecList newSources, com.android.dx.rop.code.RegisterSpec newResult, int newOpcode, com.android.dx.rop.cst.Constant cst)
Inserts a new ThrowingInsn before the given instruction. TODO: move this somewhere more appropriate

param
insn {@code non-null;} instruction to insert before
param
newSources {@code non-null;} sources of new instruction
param
newResult {@code non-null;} result of new instruction
param
newOpcode opcode of new instruction
param
cst {@code null-ok;} constant for new instruction, if any


        Insn origRopInsn = insn.getOriginalRopInsn();
        Rop newRop = Rops.ropFor(newOpcode, newResult, newSources, cst);
        Insn newRopInsn;
        if (cst == null) {
            newRopInsn = new ThrowingInsn(newRop,
                origRopInsn.getPosition(), newSources, StdTypeList.EMPTY);
        } else {
            newRopInsn = new ThrowingCstInsn(newRop,
                origRopInsn.getPosition(), newSources, StdTypeList.EMPTY, cst);
        }

        NormalSsaInsn newInsn = new NormalSsaInsn(newRopInsn, insn.getBlock());
        List<SsaInsn> insns = insn.getBlock().getInsns();

        insns.add(insns.lastIndexOf(insn), newInsn);
        ssaMeth.onInsnAdded(newInsn);
private voidmovePropagate()
Identifies extra moves added by scalar replacement and propagates the source of the move to any users of the result.

        for (int i = 0; i < ssaMeth.getRegCount(); i++) {
            SsaInsn insn = ssaMeth.getDefinitionForRegister(i);

            // Look for move instructions only
            if (insn == null || insn.getOpcode() == null ||
                insn.getOpcode().getOpcode() != RegOps.MOVE) {
                continue;
            }

            final ArrayList<SsaInsn>[] useList = ssaMeth.getUseListCopy();
            final RegisterSpec source = insn.getSources().get(0);
            final RegisterSpec result = insn.getResult();

            // Ignore moves that weren't added due to scalar replacement
            if (source.getReg() < regCount && result.getReg() < regCount) {
                continue;
            }

            // Create a mapping from source to result
            RegisterMapper mapper = new RegisterMapper() {
                @Override
                public int getNewRegisterCount() {
                    return ssaMeth.getRegCount();
                }

                @Override
                public RegisterSpec map(RegisterSpec registerSpec) {
                    if (registerSpec.getReg() == result.getReg()) {
                        return source;
                    }

                    return registerSpec;
                }
            };

            // Modify all uses of the move to use the source of the move instead
            for (SsaInsn use : useList[result.getReg()]) {
                use.mapSourceRegisters(mapper);
            }
        }
public static voidprocess(SsaMethod ssaMethod)
Performs escape analysis on a method. Finds scalar replaceable arrays and replaces them with equivalent registers.

param
ssaMethod {@code non-null;} method to process

        new EscapeAnalysis(ssaMethod).run();
private voidprocessInsn(SsaInsn insn)
Process a single instruction, looking for new objects resulting from move result or move param.

param
insn {@code non-null;} instruction to process

        int op = insn.getOpcode().getOpcode();
        RegisterSpec result = insn.getResult();
        EscapeSet escSet;

        // Identify new objects
        if (op == RegOps.MOVE_RESULT_PSEUDO &&
                result.getTypeBearer().getBasicType() == Type.BT_OBJECT) {
            // Handle objects generated through move_result_pseudo
            escSet = processMoveResultPseudoInsn(insn);
            processRegister(result, escSet);
        } else if (op == RegOps.MOVE_PARAM &&
                      result.getTypeBearer().getBasicType() == Type.BT_OBJECT) {
            // Track method arguments that are objects
            escSet = new EscapeSet(result.getReg(), regCount, EscapeState.NONE);
            latticeValues.add(escSet);
            processRegister(result, escSet);
        } else if (op == RegOps.MOVE_RESULT &&
                result.getTypeBearer().getBasicType() == Type.BT_OBJECT) {
            // Track method return values that are objects
            escSet = new EscapeSet(result.getReg(), regCount, EscapeState.NONE);
            latticeValues.add(escSet);
            processRegister(result, escSet);
        }
private com.android.dx.ssa.EscapeAnalysis$EscapeSetprocessMoveResultPseudoInsn(SsaInsn insn)
Determine the origin of a move result pseudo instruction that generates an object. Creates a new EscapeSet for the new object accordingly.

param
insn {@code non-null;} move result pseudo instruction to process
return
{@code non-null;} an EscapeSet for the object referred to by the move result pseudo instruction

        RegisterSpec result = insn.getResult();
        SsaInsn prevSsaInsn = getInsnForMove(insn);
        int prevOpcode = prevSsaInsn.getOpcode().getOpcode();
        EscapeSet escSet;
        RegisterSpec prevSource;

        switch(prevOpcode) {
           // New instance / Constant
            case RegOps.NEW_INSTANCE:
            case RegOps.CONST:
                escSet = new EscapeSet(result.getReg(), regCount,
                                           EscapeState.NONE);
                break;
            // New array
            case RegOps.NEW_ARRAY:
            case RegOps.FILLED_NEW_ARRAY:
                prevSource = prevSsaInsn.getSources().get(0);
                if (prevSource.getTypeBearer().isConstant()) {
                    // New fixed array
                    escSet = new EscapeSet(result.getReg(), regCount,
                                               EscapeState.NONE);
                    escSet.replaceableArray = true;
                } else {
                    // New variable array
                    escSet = new EscapeSet(result.getReg(), regCount,
                                               EscapeState.GLOBAL);
                }
                break;
            // Loading a static object
            case RegOps.GET_STATIC:
                escSet = new EscapeSet(result.getReg(), regCount,
                                           EscapeState.GLOBAL);
                break;
            // Type cast / load an object from a field or array
            case RegOps.CHECK_CAST:
            case RegOps.GET_FIELD:
            case RegOps.AGET:
                prevSource = prevSsaInsn.getSources().get(0);
                int setIndex = findSetIndex(prevSource);

                // Set should already exist, try to find it
                if (setIndex != latticeValues.size()) {
                    escSet = latticeValues.get(setIndex);
                    escSet.regSet.set(result.getReg());
                    return escSet;
                }

                // Set not found, must be either null or unknown
                if (prevSource.getType() == Type.KNOWN_NULL) {
                    escSet = new EscapeSet(result.getReg(), regCount,
                                               EscapeState.NONE);
               } else {
                    escSet = new EscapeSet(result.getReg(), regCount,
                                               EscapeState.GLOBAL);
                }
                break;
            default:
                return null;
        }

        // Add the newly created escSet to the lattice and return it
        latticeValues.add(escSet);
        return escSet;
private voidprocessPhiUse(SsaInsn use, com.android.dx.ssa.EscapeAnalysis$EscapeSet escSet, java.util.ArrayList regWorklist)
Handles phi uses of new objects. Will merge together the sources of a phi into a single EscapeSet. Adds the result of the phi to the worklist so its uses can be followed.

param
use {@code non-null;} phi use being processed
param
escSet {@code non-null;} EscapeSet for the object
param
regWorklist {@code non-null;} worklist of instructions left to process for this object

        int setIndex = findSetIndex(use.getResult());
        if (setIndex != latticeValues.size()) {
            // Check if result is in a set already
            EscapeSet mergeSet = latticeValues.get(setIndex);
            if (mergeSet != escSet) {
                // If it is, merge the sets and states, then delete the copy
                escSet.replaceableArray = false;
                escSet.regSet.or(mergeSet.regSet);
                if (escSet.escape.compareTo(mergeSet.escape) < 0) {
                    escSet.escape = mergeSet.escape;
                }
                replaceNode(escSet, mergeSet);
                latticeValues.remove(setIndex);
            }
        } else {
            // If no set is found, add it to this escSet and the worklist
            escSet.regSet.set(use.getResult().getReg());
            regWorklist.add(use.getResult());
        }
private voidprocessRegister(com.android.dx.rop.code.RegisterSpec result, com.android.dx.ssa.EscapeAnalysis$EscapeSet escSet)
Iterate through all the uses of a new object.

param
result {@code non-null;} register where new object is stored
param
escSet {@code non-null;} EscapeSet for the new object

        ArrayList<RegisterSpec> regWorklist = new ArrayList<RegisterSpec>();
        regWorklist.add(result);

        // Go through the worklist
        while (!regWorklist.isEmpty()) {
            int listSize = regWorklist.size() - 1;
            RegisterSpec def = regWorklist.remove(listSize);
            List<SsaInsn> useList = ssaMeth.getUseListForRegister(def.getReg());

            // Handle all the uses of this register
            for (SsaInsn use : useList) {
                Rop useOpcode = use.getOpcode();

                if (useOpcode == null) {
                    // Handle phis
                    processPhiUse(use, escSet, regWorklist);
                } else {
                    // Handle other opcodes
                    processUse(def, use, escSet, regWorklist);
                }
            }
        }
private voidprocessUse(com.android.dx.rop.code.RegisterSpec def, SsaInsn use, com.android.dx.ssa.EscapeAnalysis$EscapeSet escSet, java.util.ArrayList regWorklist)
Handles non-phi uses of new objects. Checks to see how instruction is used and updates the escape state accordingly.

param
def {@code non-null;} register holding definition of new object
param
use {@code non-null;} use of object being processed
param
escSet {@code non-null;} EscapeSet for the object
param
regWorklist {@code non-null;} worklist of instructions left to process for this object

        int useOpcode = use.getOpcode().getOpcode();
        switch (useOpcode) {
            case RegOps.MOVE:
                // Follow uses of the move by adding it to the worklist
                escSet.regSet.set(use.getResult().getReg());
                regWorklist.add(use.getResult());
                break;
            case RegOps.IF_EQ:
            case RegOps.IF_NE:
            case RegOps.CHECK_CAST:
                // Compared objects can't be replaced, so promote if necessary
                if (escSet.escape.compareTo(EscapeState.METHOD) < 0) {
                    escSet.escape = EscapeState.METHOD;
                }
                break;
            case RegOps.APUT:
                // For array puts, check for a constant array index
                RegisterSpec putIndex = use.getSources().get(2);
                if (!putIndex.getTypeBearer().isConstant()) {
                    // If not constant, array can't be replaced
                    escSet.replaceableArray = false;
                }
                // Intentional fallthrough
            case RegOps.PUT_FIELD:
                // Skip non-object puts
                RegisterSpec putValue = use.getSources().get(0);
                if (putValue.getTypeBearer().getBasicType() != Type.BT_OBJECT) {
                    break;
                }
                escSet.replaceableArray = false;

                // Raise 1st object's escape state to 2nd if 2nd is higher
                RegisterSpecList sources = use.getSources();
                if (sources.get(0).getReg() == def.getReg()) {
                    int setIndex = findSetIndex(sources.get(1));
                    if (setIndex != latticeValues.size()) {
                        EscapeSet parentSet = latticeValues.get(setIndex);
                        addEdge(parentSet, escSet);
                        if (escSet.escape.compareTo(parentSet.escape) < 0) {
                            escSet.escape = parentSet.escape;
                        }
                    }
                } else {
                    int setIndex = findSetIndex(sources.get(0));
                    if (setIndex != latticeValues.size()) {
                        EscapeSet childSet = latticeValues.get(setIndex);
                        addEdge(escSet, childSet);
                        if (childSet.escape.compareTo(escSet.escape) < 0) {
                            childSet.escape = escSet.escape;
                        }
                    }
                }
                break;
            case RegOps.AGET:
                // For array gets, check for a constant array index
                RegisterSpec getIndex = use.getSources().get(1);
                if (!getIndex.getTypeBearer().isConstant()) {
                    // If not constant, array can't be replaced
                    escSet.replaceableArray = false;
                }
                break;
            case RegOps.PUT_STATIC:
                // Static puts cause an object to escape globally
                escSet.escape = EscapeState.GLOBAL;
                break;
            case RegOps.INVOKE_STATIC:
            case RegOps.INVOKE_VIRTUAL:
            case RegOps.INVOKE_SUPER:
            case RegOps.INVOKE_DIRECT:
            case RegOps.INVOKE_INTERFACE:
            case RegOps.RETURN:
            case RegOps.THROW:
                // These operations cause an object to escape interprocedurally
                escSet.escape = EscapeState.INTER;
                break;
            default:
                break;
        }
private voidreplaceDef(SsaInsn def, SsaInsn prev, int length, java.util.ArrayList newRegs)
Replaces the instructions that define an array with equivalent registers. For each entry in the array, a register is created, initialized to zero. A mapping between this register and the corresponding array index is added.

param
def {@code non-null;} move result instruction for array
param
prev {@code non-null;} instruction for instantiating new array
param
length size of the new array
param
newRegs {@code non-null;} mapping of array indices to new registers to be populated

        Type resultType = def.getResult().getType();

        // Create new zeroed out registers for each element in the array
        for (int i = 0; i < length; i++) {
            Constant newZero = Zeroes.zeroFor(resultType.getComponentType());
            TypedConstant typedZero = (TypedConstant) newZero;
            RegisterSpec newReg =
                RegisterSpec.make(ssaMeth.makeNewSsaReg(), typedZero);
            newRegs.add(newReg);
            insertPlainInsnBefore(def, RegisterSpecList.EMPTY, newReg,
                                      RegOps.CONST, newZero);
        }
private voidreplaceNode(com.android.dx.ssa.EscapeAnalysis$EscapeSet newNode, com.android.dx.ssa.EscapeAnalysis$EscapeSet oldNode)
Merges all links in the lattice among two EscapeSets. On return, the newNode will have its old links as well as all links from the oldNode. The oldNode has all its links removed.

param
newNode {@code non-null;} the EscapeSet to merge all links into
param
oldNode {@code non-null;} the EscapeSet to remove all links from

        for (EscapeSet e : oldNode.parentSets) {
            e.childSets.remove(oldNode);
            e.childSets.add(newNode);
            newNode.parentSets.add(e);
        }
        for (EscapeSet e : oldNode.childSets) {
            e.parentSets.remove(oldNode);
            e.parentSets.add(newNode);
            newNode.childSets.add(e);
        }
private voidreplaceUse(SsaInsn use, SsaInsn prev, java.util.ArrayList newRegs, java.util.HashSet deletedInsns)
Replaces the use for a scalar replaceable array. Gets and puts become move instructions, and array lengths and fills are handled. Can also identify ArrayIndexOutOfBounds exceptions and throw them if detected.

param
use {@code non-null;} move result instruction for array
param
prev {@code non-null;} instruction for instantiating new array
param
newRegs {@code non-null;} mapping of array indices to new registers
param
deletedInsns {@code non-null;} set of instructions marked for deletion

        int index;
        int length = newRegs.size();
        SsaInsn next;
        RegisterSpecList sources;
        RegisterSpec source, result;
        CstLiteralBits indexReg;

        switch (use.getOpcode().getOpcode()) {
            case RegOps.AGET:
                // Replace array gets with moves
                next = getMoveForInsn(use);
                sources = use.getSources();
                indexReg = ((CstLiteralBits) sources.get(1).getTypeBearer());
                index = indexReg.getIntBits();
                if (index < length) {
                    source = newRegs.get(index);
                    result = source.withReg(next.getResult().getReg());
                    insertPlainInsnBefore(next, RegisterSpecList.make(source),
                                              result, RegOps.MOVE, null);
                } else {
                    // Throw an exception if the index is out of bounds
                    insertExceptionThrow(next, sources.get(1), deletedInsns);
                    deletedInsns.add(next.getBlock().getInsns().get(2));
                }
                deletedInsns.add(next);
                break;
            case RegOps.APUT:
                // Replace array puts with moves
                sources = use.getSources();
                indexReg = ((CstLiteralBits) sources.get(2).getTypeBearer());
                index = indexReg.getIntBits();
                if (index < length) {
                    source = sources.get(0);
                    result = source.withReg(newRegs.get(index).getReg());
                    insertPlainInsnBefore(use, RegisterSpecList.make(source),
                                              result, RegOps.MOVE, null);
                    // Update the newReg entry to mark value as unknown now
                    newRegs.set(index, result.withSimpleType());
                } else {
                    // Throw an exception if the index is out of bounds
                    insertExceptionThrow(use, sources.get(2), deletedInsns);
                }
                break;
            case RegOps.ARRAY_LENGTH:
                // Replace array lengths with const instructions
                TypeBearer lengthReg = prev.getSources().get(0).getTypeBearer();
                //CstInteger lengthReg = CstInteger.make(length);
                next = getMoveForInsn(use);
                insertPlainInsnBefore(next, RegisterSpecList.EMPTY,
                                          next.getResult(), RegOps.CONST,
                                          (Constant) lengthReg);
                deletedInsns.add(next);
                break;
            case RegOps.MARK_LOCAL:
                // Remove mark local instructions
                break;
            case RegOps.FILL_ARRAY_DATA:
                // Create const instructions for each fill value
                Insn ropUse = use.getOriginalRopInsn();
                FillArrayDataInsn fill = (FillArrayDataInsn) ropUse;
                ArrayList<Constant> constList = fill.getInitValues();
                for (int i = 0; i < length; i++) {
                    RegisterSpec newFill =
                        RegisterSpec.make(newRegs.get(i).getReg(),
                                              (TypeBearer) constList.get(i));
                    insertPlainInsnBefore(use, RegisterSpecList.EMPTY, newFill,
                                              RegOps.CONST, constList.get(i));
                    // Update the newRegs to hold the new const value
                    newRegs.set(i, newFill);
                }
                break;
            default:
        }
private voidrun()
Runs escape analysis and scalar replacement of arrays.

        ssaMeth.forEachBlockDepthFirstDom(new SsaBasicBlock.Visitor() {
            public void visitBlock (SsaBasicBlock block,
                    SsaBasicBlock unused) {
                block.forEachInsn(new SsaInsn.Visitor() {
                    public void visitMoveInsn(NormalSsaInsn insn) {
                        // do nothing
                    }

                    public void visitPhiInsn(PhiInsn insn) {
                        // do nothing
                    }

                    public void visitNonMoveInsn(NormalSsaInsn insn) {
                        processInsn(insn);
                    }
                });
            }
        });

        // Go through lattice and promote fieldSets as necessary
        for (EscapeSet e : latticeValues) {
            if (e.escape != EscapeState.NONE) {
                for (EscapeSet field : e.childSets) {
                    if (e.escape.compareTo(field.escape) > 0) {
                        field.escape = e.escape;
                    }
                }
            }
        }

        // Perform scalar replacement for arrays
        scalarReplacement();
private voidscalarReplacement()
Performs scalar replacement on all eligible arrays.

        // Iterate through lattice, looking for non-escaping replaceable arrays
        for (EscapeSet escSet : latticeValues) {
            if (!escSet.replaceableArray || escSet.escape != EscapeState.NONE) {
                continue;
            }

            // Get the instructions for the definition and move of the array
            int e = escSet.regSet.nextSetBit(0);
            SsaInsn def = ssaMeth.getDefinitionForRegister(e);
            SsaInsn prev = getInsnForMove(def);

            // Create a map for the new registers that will be created
            TypeBearer lengthReg = prev.getSources().get(0).getTypeBearer();
            int length = ((CstLiteralBits) lengthReg).getIntBits();
            ArrayList<RegisterSpec> newRegs =
                new ArrayList<RegisterSpec>(length);
            HashSet<SsaInsn> deletedInsns = new HashSet<SsaInsn>();

            // Replace the definition of the array with registers
            replaceDef(def, prev, length, newRegs);

            // Mark definition instructions for deletion
            deletedInsns.add(prev);
            deletedInsns.add(def);

            // Go through all uses of the array
            List<SsaInsn> useList = ssaMeth.getUseListForRegister(e);
            for (SsaInsn use : useList) {
                // Replace the use with scalars and then mark it for deletion
                replaceUse(use, prev, newRegs, deletedInsns);
                deletedInsns.add(use);
            }

            // Delete all marked instructions
            ssaMeth.deleteInsns(deletedInsns);
            ssaMeth.onInsnsChanged();

            // Convert the method back to SSA form
            SsaConverter.updateSsaMethod(ssaMeth, regCount);

            // Propagate and remove extra moves added by scalar replacement
            movePropagate();
        }