1579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/* 2579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Copyright (C) 2010 The Android Open Source Project 3579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 4579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * you may not use this file except in compliance with the License. 6579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * You may obtain a copy of the License at 7579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 8579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 10579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * See the License for the specific language governing permissions and 14579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * limitations under the License. 15579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 16579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 17579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpackage com.android.dx.ssa; 18579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 19579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.Exceptions; 20579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.FillArrayDataInsn; 21579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.Insn; 22579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.PlainCstInsn; 23579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.PlainInsn; 24579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RegOps; 25579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RegisterSpec; 26579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RegisterSpecList; 27579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.Rop; 28579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.Rops; 29579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.ThrowingCstInsn; 30579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.ThrowingInsn; 31579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.cst.Constant; 32579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.cst.CstLiteralBits; 33579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.cst.CstMethodRef; 34579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.cst.CstNat; 35579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.cst.CstString; 36579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.cst.CstType; 37579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.cst.TypedConstant; 38579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.cst.Zeroes; 39579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.type.StdTypeList; 40579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.type.Type; 41579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.type.TypeBearer; 42579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 43579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.ArrayList; 44579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.BitSet; 45579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.HashSet; 46579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.List; 47579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 48579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/** 49579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Simple intraprocedural escape analysis. Finds new arrays that don't escape 50579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * the method they are created in and replaces the array values with registers. 51579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 52579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic class EscapeAnalysis { 53579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 54579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Struct used to generate and maintain escape analysis results. 55579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 56579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson static class EscapeSet { 57579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** set containing all registers related to an object */ 58579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BitSet regSet; 59579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** escape state of the object */ 60579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson EscapeState escape; 61579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** list of objects that are put into this object */ 62579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<EscapeSet> childSets; 63579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** list of objects that this object is put into */ 64579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<EscapeSet> parentSets; 65579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** flag to indicate this object is a scalar replaceable array */ 66579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson boolean replaceableArray; 67579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 68579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 69579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Constructs an instance of an EscapeSet 70579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 71579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param reg the SSA register that defines the object 72579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param size the number of registers in the method 73579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param escState the lattice value to initially set this to 74579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 75579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson EscapeSet(int reg, int size, EscapeState escState) { 76579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson regSet = new BitSet(size); 77579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson regSet.set(reg); 78579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escape = escState; 79579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson childSets = new ArrayList<EscapeSet>(); 80579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson parentSets = new ArrayList<EscapeSet>(); 81579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson replaceableArray = false; 82579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 83579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 84579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 85579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 86579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Lattice values used to indicate escape state for an object. Analysis can 87579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * only raise escape state values, not lower them. 88579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 89579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * TOP - Used for objects that haven't been analyzed yet 90579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * NONE - Object does not escape, and is eligible for scalar replacement. 91579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * METHOD - Object remains local to method, but can't be scalar replaced. 92579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * INTER - Object is passed between methods. (treated as globally escaping 93579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * since this is an intraprocedural analysis) 94579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * GLOBAL - Object escapes globally. 95579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 96579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public enum EscapeState { 97579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson TOP, NONE, METHOD, INTER, GLOBAL 98579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 99579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 100579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** method we're processing */ 101579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private SsaMethod ssaMeth; 102579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** ssaMeth.getRegCount() */ 103579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private int regCount; 104579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** Lattice values for each object register group */ 105579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private ArrayList<EscapeSet> latticeValues; 106579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 107579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 108579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Constructs an instance. 109579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 110579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param ssaMeth method to process 111579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 112579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private EscapeAnalysis(SsaMethod ssaMeth) { 113579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.ssaMeth = ssaMeth; 114579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.regCount = ssaMeth.getRegCount(); 115579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.latticeValues = new ArrayList<EscapeSet>(); 116579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 117579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 118579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 119579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Finds the index in the lattice for a particular register. 120579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Returns the size of the lattice if the register wasn't found. 121579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 122579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param reg {@code non-null;} register being looked up 123579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return index of the register or size of the lattice if it wasn't found. 124579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 125579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private int findSetIndex(RegisterSpec reg) { 126579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int i; 127579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (i = 0; i < latticeValues.size(); i++) { 128579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson EscapeSet e = latticeValues.get(i); 129579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (e.regSet.get(reg.getReg())) { 130579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return i; 131579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 132579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 133579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return i; 134579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 135579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 136579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 137579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Finds the corresponding instruction for a given move result 138579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 139579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param moveInsn {@code non-null;} a move result instruction 140579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} the instruction that produces the result for 141579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * the move 142579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 143579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private SsaInsn getInsnForMove(SsaInsn moveInsn) { 144579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int pred = moveInsn.getBlock().getPredecessors().nextSetBit(0); 145579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<SsaInsn> predInsns = ssaMeth.getBlocks().get(pred).getInsns(); 146579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return predInsns.get(predInsns.size()-1); 147579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 148579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 149579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 150579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Finds the corresponding move result for a given instruction 151579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 152579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param insn {@code non-null;} an instruction that must always be 153579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * followed by a move result 154579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} the move result for the given instruction 155579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 156579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private SsaInsn getMoveForInsn(SsaInsn insn) { 157579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int succ = insn.getBlock().getSuccessors().nextSetBit(0); 158579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<SsaInsn> succInsns = ssaMeth.getBlocks().get(succ).getInsns(); 159579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return succInsns.get(0); 160579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 161579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 162579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 163579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Creates a link in the lattice between two EscapeSets due to a put 164579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * instruction. The object being put is the child and the object being put 165579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * into is the parent. A child set must always have an escape state at 166579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * least as high as its parent. 167579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 168579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param parentSet {@code non-null;} the EscapeSet for the object being put 169579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * into 170579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param childSet {@code non-null;} the EscapeSet for the object being put 171579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 172579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void addEdge(EscapeSet parentSet, EscapeSet childSet) { 173579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!childSet.parentSets.contains(parentSet)) { 174579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson childSet.parentSets.add(parentSet); 175579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 176579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!parentSet.childSets.contains(childSet)) { 177579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson parentSet.childSets.add(childSet); 178579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 179579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 180579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 181579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 182579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Merges all links in the lattice among two EscapeSets. On return, the 183579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * newNode will have its old links as well as all links from the oldNode. 184579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * The oldNode has all its links removed. 185579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 186579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param newNode {@code non-null;} the EscapeSet to merge all links into 187579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param oldNode {@code non-null;} the EscapeSet to remove all links from 188579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 189579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void replaceNode(EscapeSet newNode, EscapeSet oldNode) { 190579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (EscapeSet e : oldNode.parentSets) { 191579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson e.childSets.remove(oldNode); 192579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson e.childSets.add(newNode); 193579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newNode.parentSets.add(e); 194579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 195579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (EscapeSet e : oldNode.childSets) { 196579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson e.parentSets.remove(oldNode); 197579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson e.parentSets.add(newNode); 198579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newNode.childSets.add(e); 199579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 200579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 201579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 202579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 203579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Performs escape analysis on a method. Finds scalar replaceable arrays and 204579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * replaces them with equivalent registers. 205579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 206579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param ssaMethod {@code non-null;} method to process 207579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 208579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static void process(SsaMethod ssaMethod) { 209579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson new EscapeAnalysis(ssaMethod).run(); 210579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 211579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 212579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 213579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Process a single instruction, looking for new objects resulting from 214579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * move result or move param. 215579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 216579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param insn {@code non-null;} instruction to process 217579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 218579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void processInsn(SsaInsn insn) { 219579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int op = insn.getOpcode().getOpcode(); 220579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec result = insn.getResult(); 221579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson EscapeSet escSet; 222579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 223579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Identify new objects 224579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (op == RegOps.MOVE_RESULT_PSEUDO && 225579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.getTypeBearer().getBasicType() == Type.BT_OBJECT) { 226579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Handle objects generated through move_result_pseudo 227579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet = processMoveResultPseudoInsn(insn); 228579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson processRegister(result, escSet); 229579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else if (op == RegOps.MOVE_PARAM && 230579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.getTypeBearer().getBasicType() == Type.BT_OBJECT) { 231579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Track method arguments that are objects 232579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet = new EscapeSet(result.getReg(), regCount, EscapeState.NONE); 233579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson latticeValues.add(escSet); 234579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson processRegister(result, escSet); 235579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else if (op == RegOps.MOVE_RESULT && 236579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.getTypeBearer().getBasicType() == Type.BT_OBJECT) { 237579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Track method return values that are objects 238579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet = new EscapeSet(result.getReg(), regCount, EscapeState.NONE); 239579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson latticeValues.add(escSet); 240579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson processRegister(result, escSet); 241579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 242579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 243579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 244579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 245579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Determine the origin of a move result pseudo instruction that generates 246579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * an object. Creates a new EscapeSet for the new object accordingly. 247579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 248579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param insn {@code non-null;} move result pseudo instruction to process 249579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} an EscapeSet for the object referred to by the 250579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * move result pseudo instruction 251579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 252579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private EscapeSet processMoveResultPseudoInsn(SsaInsn insn) { 253579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec result = insn.getResult(); 254579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn prevSsaInsn = getInsnForMove(insn); 255579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int prevOpcode = prevSsaInsn.getOpcode().getOpcode(); 256579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson EscapeSet escSet; 257579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec prevSource; 258579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 259579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson switch(prevOpcode) { 260579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // New instance / Constant 261579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.NEW_INSTANCE: 262579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.CONST: 263579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet = new EscapeSet(result.getReg(), regCount, 264579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson EscapeState.NONE); 265579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 266579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // New array 267579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.NEW_ARRAY: 268579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.FILLED_NEW_ARRAY: 269579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson prevSource = prevSsaInsn.getSources().get(0); 270579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (prevSource.getTypeBearer().isConstant()) { 271579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // New fixed array 272579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet = new EscapeSet(result.getReg(), regCount, 273579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson EscapeState.NONE); 274579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet.replaceableArray = true; 275579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 276579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // New variable array 277579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet = new EscapeSet(result.getReg(), regCount, 278579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson EscapeState.GLOBAL); 279579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 280579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 281579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Loading a static object 282579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.GET_STATIC: 283579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet = new EscapeSet(result.getReg(), regCount, 284579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson EscapeState.GLOBAL); 285579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 286579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Type cast / load an object from a field or array 287579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.CHECK_CAST: 288579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.GET_FIELD: 289579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.AGET: 290579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson prevSource = prevSsaInsn.getSources().get(0); 291579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int setIndex = findSetIndex(prevSource); 292579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 293579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Set should already exist, try to find it 294579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (setIndex != latticeValues.size()) { 295579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet = latticeValues.get(setIndex); 296579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet.regSet.set(result.getReg()); 297579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return escSet; 298579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 299579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 300579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Set not found, must be either null or unknown 301579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (prevSource.getType() == Type.KNOWN_NULL) { 302579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet = new EscapeSet(result.getReg(), regCount, 303579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson EscapeState.NONE); 304579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 305579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet = new EscapeSet(result.getReg(), regCount, 306579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson EscapeState.GLOBAL); 307579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 308579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 309579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson default: 310579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return null; 311579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 312579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 313579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Add the newly created escSet to the lattice and return it 314579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson latticeValues.add(escSet); 315579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return escSet; 316579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 317579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 318579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 319579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Iterate through all the uses of a new object. 320579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 321579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param result {@code non-null;} register where new object is stored 322579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param escSet {@code non-null;} EscapeSet for the new object 323579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 324579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void processRegister(RegisterSpec result, EscapeSet escSet) { 325579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<RegisterSpec> regWorklist = new ArrayList<RegisterSpec>(); 326579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson regWorklist.add(result); 327579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 328579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Go through the worklist 329579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson while (!regWorklist.isEmpty()) { 330579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int listSize = regWorklist.size() - 1; 331579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec def = regWorklist.remove(listSize); 332579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson List<SsaInsn> useList = ssaMeth.getUseListForRegister(def.getReg()); 333579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 334579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Handle all the uses of this register 335579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (SsaInsn use : useList) { 336579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Rop useOpcode = use.getOpcode(); 337579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 338579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (useOpcode == null) { 339579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Handle phis 340579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson processPhiUse(use, escSet, regWorklist); 341579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 342579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Handle other opcodes 343579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson processUse(def, use, escSet, regWorklist); 344579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 345579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 346579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 347579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 348579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 349579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 350579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Handles phi uses of new objects. Will merge together the sources of a phi 351579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * into a single EscapeSet. Adds the result of the phi to the worklist so 352579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * its uses can be followed. 353579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 354579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param use {@code non-null;} phi use being processed 355579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param escSet {@code non-null;} EscapeSet for the object 356579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param regWorklist {@code non-null;} worklist of instructions left to 357579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * process for this object 358579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 359579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void processPhiUse(SsaInsn use, EscapeSet escSet, 360579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<RegisterSpec> regWorklist) { 361579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int setIndex = findSetIndex(use.getResult()); 362579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (setIndex != latticeValues.size()) { 363579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Check if result is in a set already 364579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson EscapeSet mergeSet = latticeValues.get(setIndex); 365579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (mergeSet != escSet) { 366579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // If it is, merge the sets and states, then delete the copy 367579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet.replaceableArray = false; 368579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet.regSet.or(mergeSet.regSet); 369579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (escSet.escape.compareTo(mergeSet.escape) < 0) { 370579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet.escape = mergeSet.escape; 371579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 372579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson replaceNode(escSet, mergeSet); 373579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson latticeValues.remove(setIndex); 374579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 375579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 376579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // If no set is found, add it to this escSet and the worklist 377579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet.regSet.set(use.getResult().getReg()); 378579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson regWorklist.add(use.getResult()); 379579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 380579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 381579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 382579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 383579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Handles non-phi uses of new objects. Checks to see how instruction is 384579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * used and updates the escape state accordingly. 385579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 386579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param def {@code non-null;} register holding definition of new object 387579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param use {@code non-null;} use of object being processed 388579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param escSet {@code non-null;} EscapeSet for the object 389579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param regWorklist {@code non-null;} worklist of instructions left to 390579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * process for this object 391579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 392579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void processUse(RegisterSpec def, SsaInsn use, EscapeSet escSet, 393579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<RegisterSpec> regWorklist) { 394579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int useOpcode = use.getOpcode().getOpcode(); 395579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson switch (useOpcode) { 396579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.MOVE: 397579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Follow uses of the move by adding it to the worklist 398579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet.regSet.set(use.getResult().getReg()); 399579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson regWorklist.add(use.getResult()); 400579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 401579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.IF_EQ: 402579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.IF_NE: 403579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.CHECK_CAST: 404579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Compared objects can't be replaced, so promote if necessary 405579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (escSet.escape.compareTo(EscapeState.METHOD) < 0) { 406579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet.escape = EscapeState.METHOD; 407579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 408579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 409579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.APUT: 410579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // For array puts, check for a constant array index 411579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec putIndex = use.getSources().get(2); 412579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!putIndex.getTypeBearer().isConstant()) { 413579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // If not constant, array can't be replaced 414579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet.replaceableArray = false; 415579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 416579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Intentional fallthrough 417579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.PUT_FIELD: 418579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Skip non-object puts 419579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec putValue = use.getSources().get(0); 420579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (putValue.getTypeBearer().getBasicType() != Type.BT_OBJECT) { 421579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 422579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 423579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet.replaceableArray = false; 424579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 425579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Raise 1st object's escape state to 2nd if 2nd is higher 426579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpecList sources = use.getSources(); 427579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (sources.get(0).getReg() == def.getReg()) { 428579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int setIndex = findSetIndex(sources.get(1)); 429579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (setIndex != latticeValues.size()) { 430579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson EscapeSet parentSet = latticeValues.get(setIndex); 431579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson addEdge(parentSet, escSet); 432579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (escSet.escape.compareTo(parentSet.escape) < 0) { 433579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet.escape = parentSet.escape; 434579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 435579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 436579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 437579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int setIndex = findSetIndex(sources.get(0)); 438579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (setIndex != latticeValues.size()) { 439579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson EscapeSet childSet = latticeValues.get(setIndex); 440579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson addEdge(escSet, childSet); 441579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (childSet.escape.compareTo(escSet.escape) < 0) { 442579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson childSet.escape = escSet.escape; 443579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 444579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 445579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 446579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 447579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.AGET: 448579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // For array gets, check for a constant array index 449579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec getIndex = use.getSources().get(1); 450579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!getIndex.getTypeBearer().isConstant()) { 451579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // If not constant, array can't be replaced 452579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet.replaceableArray = false; 453579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 454579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 455579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.PUT_STATIC: 456579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Static puts cause an object to escape globally 457579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet.escape = EscapeState.GLOBAL; 458579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 459579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.INVOKE_STATIC: 460579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.INVOKE_VIRTUAL: 461579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.INVOKE_SUPER: 462579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.INVOKE_DIRECT: 463579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.INVOKE_INTERFACE: 464579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.RETURN: 465579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.THROW: 466579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // These operations cause an object to escape interprocedurally 467579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson escSet.escape = EscapeState.INTER; 468579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 469579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson default: 470579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 471579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 472579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 473579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 474579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 475579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Performs scalar replacement on all eligible arrays. 476579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 477579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void scalarReplacement() { 478579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Iterate through lattice, looking for non-escaping replaceable arrays 479579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (EscapeSet escSet : latticeValues) { 480579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!escSet.replaceableArray || escSet.escape != EscapeState.NONE) { 481579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson continue; 482579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 483579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 484579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Get the instructions for the definition and move of the array 485579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int e = escSet.regSet.nextSetBit(0); 486579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn def = ssaMeth.getDefinitionForRegister(e); 487579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn prev = getInsnForMove(def); 488579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 489579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Create a map for the new registers that will be created 490579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson TypeBearer lengthReg = prev.getSources().get(0).getTypeBearer(); 491579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int length = ((CstLiteralBits) lengthReg).getIntBits(); 492579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<RegisterSpec> newRegs = 493579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson new ArrayList<RegisterSpec>(length); 494579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson HashSet<SsaInsn> deletedInsns = new HashSet<SsaInsn>(); 495579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 496579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Replace the definition of the array with registers 497579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson replaceDef(def, prev, length, newRegs); 498579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 499579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Mark definition instructions for deletion 500579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson deletedInsns.add(prev); 501579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson deletedInsns.add(def); 502579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 503579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Go through all uses of the array 504579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson List<SsaInsn> useList = ssaMeth.getUseListForRegister(e); 505579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (SsaInsn use : useList) { 506579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Replace the use with scalars and then mark it for deletion 507579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson replaceUse(use, prev, newRegs, deletedInsns); 508579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson deletedInsns.add(use); 509579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 510579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 511579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Delete all marked instructions 512579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaMeth.deleteInsns(deletedInsns); 513579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaMeth.onInsnsChanged(); 514579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 515579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Convert the method back to SSA form 516579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaConverter.updateSsaMethod(ssaMeth, regCount); 517579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 518579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Propagate and remove extra moves added by scalar replacement 519579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson movePropagate(); 520579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 521579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 522579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 523579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 524579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Replaces the instructions that define an array with equivalent registers. 525579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * For each entry in the array, a register is created, initialized to zero. 526579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * A mapping between this register and the corresponding array index is 527579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * added. 528579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 529579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param def {@code non-null;} move result instruction for array 530579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param prev {@code non-null;} instruction for instantiating new array 531579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param length size of the new array 532579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param newRegs {@code non-null;} mapping of array indices to new 533579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * registers to be populated 534579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 535579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void replaceDef(SsaInsn def, SsaInsn prev, int length, 536579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<RegisterSpec> newRegs) { 537579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Type resultType = def.getResult().getType(); 538579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 539579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Create new zeroed out registers for each element in the array 540579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < length; i++) { 541579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Constant newZero = Zeroes.zeroFor(resultType.getComponentType()); 542579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson TypedConstant typedZero = (TypedConstant) newZero; 543579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec newReg = 544579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec.make(ssaMeth.makeNewSsaReg(), typedZero); 545579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newRegs.add(newReg); 546579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insertPlainInsnBefore(def, RegisterSpecList.EMPTY, newReg, 547579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegOps.CONST, newZero); 548579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 549579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 550579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 551579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 552579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Replaces the use for a scalar replaceable array. Gets and puts become 553579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * move instructions, and array lengths and fills are handled. Can also 554579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * identify ArrayIndexOutOfBounds exceptions and throw them if detected. 555579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 556579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param use {@code non-null;} move result instruction for array 557579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param prev {@code non-null;} instruction for instantiating new array 558579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param newRegs {@code non-null;} mapping of array indices to new 559579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * registers 560579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param deletedInsns {@code non-null;} set of instructions marked for 561579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * deletion 562579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 563579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void replaceUse(SsaInsn use, SsaInsn prev, 564579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<RegisterSpec> newRegs, 565579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson HashSet<SsaInsn> deletedInsns) { 566579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int index; 567579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int length = newRegs.size(); 568579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn next; 569579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpecList sources; 570579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec source, result; 571579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson CstLiteralBits indexReg; 572579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 573579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson switch (use.getOpcode().getOpcode()) { 574579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.AGET: 575579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Replace array gets with moves 576579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson next = getMoveForInsn(use); 577579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sources = use.getSources(); 578579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson indexReg = ((CstLiteralBits) sources.get(1).getTypeBearer()); 579579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson index = indexReg.getIntBits(); 580579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (index < length) { 581579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson source = newRegs.get(index); 582579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result = source.withReg(next.getResult().getReg()); 583579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insertPlainInsnBefore(next, RegisterSpecList.make(source), 584579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result, RegOps.MOVE, null); 585579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 586579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Throw an exception if the index is out of bounds 587579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insertExceptionThrow(next, sources.get(1), deletedInsns); 588579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson deletedInsns.add(next.getBlock().getInsns().get(2)); 589579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 590579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson deletedInsns.add(next); 591579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 592579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.APUT: 593579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Replace array puts with moves 594579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sources = use.getSources(); 595579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson indexReg = ((CstLiteralBits) sources.get(2).getTypeBearer()); 596579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson index = indexReg.getIntBits(); 597579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (index < length) { 598579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson source = sources.get(0); 599579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result = source.withReg(newRegs.get(index).getReg()); 600579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insertPlainInsnBefore(use, RegisterSpecList.make(source), 601579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result, RegOps.MOVE, null); 602579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Update the newReg entry to mark value as unknown now 603579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newRegs.set(index, result.withSimpleType()); 604579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 605579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Throw an exception if the index is out of bounds 606579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insertExceptionThrow(use, sources.get(2), deletedInsns); 607579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 608579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 609579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.ARRAY_LENGTH: 610579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Replace array lengths with const instructions 611579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson TypeBearer lengthReg = prev.getSources().get(0).getTypeBearer(); 612579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson //CstInteger lengthReg = CstInteger.make(length); 613579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson next = getMoveForInsn(use); 614579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insertPlainInsnBefore(next, RegisterSpecList.EMPTY, 615579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson next.getResult(), RegOps.CONST, 616579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson (Constant) lengthReg); 617579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson deletedInsns.add(next); 618579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 619579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.MARK_LOCAL: 620579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Remove mark local instructions 621579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 622579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson case RegOps.FILL_ARRAY_DATA: 623579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Create const instructions for each fill value 624579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Insn ropUse = use.getOriginalRopInsn(); 625579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson FillArrayDataInsn fill = (FillArrayDataInsn) ropUse; 626579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<Constant> constList = fill.getInitValues(); 627579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < length; i++) { 628579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec newFill = 629579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec.make(newRegs.get(i).getReg(), 630579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson (TypeBearer) constList.get(i)); 631579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insertPlainInsnBefore(use, RegisterSpecList.EMPTY, newFill, 632579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegOps.CONST, constList.get(i)); 633579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Update the newRegs to hold the new const value 634579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newRegs.set(i, newFill); 635579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 636579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 637579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson default: 638579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 639579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 640579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 641579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 642579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Identifies extra moves added by scalar replacement and propagates the 643579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * source of the move to any users of the result. 644579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 645579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void movePropagate() { 646579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < ssaMeth.getRegCount(); i++) { 647579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn insn = ssaMeth.getDefinitionForRegister(i); 648579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 649579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Look for move instructions only 650579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (insn == null || insn.getOpcode() == null || 651579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insn.getOpcode().getOpcode() != RegOps.MOVE) { 652579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson continue; 653579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 654579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 655579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson final ArrayList<SsaInsn>[] useList = ssaMeth.getUseListCopy(); 656579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson final RegisterSpec source = insn.getSources().get(0); 657579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson final RegisterSpec result = insn.getResult(); 658579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 659579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Ignore moves that weren't added due to scalar replacement 660579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (source.getReg() < regCount && result.getReg() < regCount) { 661579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson continue; 662579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 663579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 664579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Create a mapping from source to result 665579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterMapper mapper = new RegisterMapper() { 666579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson @Override 667579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int getNewRegisterCount() { 668579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return ssaMeth.getRegCount(); 669579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 670579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 671579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson @Override 672579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public RegisterSpec map(RegisterSpec registerSpec) { 673579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (registerSpec.getReg() == result.getReg()) { 674579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return source; 675579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 676579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 677579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return registerSpec; 678579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 679579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson }; 680579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 681579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Modify all uses of the move to use the source of the move instead 682579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (SsaInsn use : useList[result.getReg()]) { 683579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson use.mapSourceRegisters(mapper); 684579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 685579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 686579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 687579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 688579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 689579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Runs escape analysis and scalar replacement of arrays. 690579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 691579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void run() { 692579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaMeth.forEachBlockDepthFirstDom(new SsaBasicBlock.Visitor() { 693579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void visitBlock (SsaBasicBlock block, 694579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock unused) { 695579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson block.forEachInsn(new SsaInsn.Visitor() { 696579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void visitMoveInsn(NormalSsaInsn insn) { 697579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // do nothing 698579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 699579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 700579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void visitPhiInsn(PhiInsn insn) { 701579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // do nothing 702579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 703579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 704579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void visitNonMoveInsn(NormalSsaInsn insn) { 705579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson processInsn(insn); 706579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 707579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson }); 708579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 709579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson }); 710579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 711579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Go through lattice and promote fieldSets as necessary 712579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (EscapeSet e : latticeValues) { 713579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (e.escape != EscapeState.NONE) { 714579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (EscapeSet field : e.childSets) { 715579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (e.escape.compareTo(field.escape) > 0) { 716579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson field.escape = e.escape; 717579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 718579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 719579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 720579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 721579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 722579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Perform scalar replacement for arrays 723579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson scalarReplacement(); 724579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 725579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 726579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 727579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Replaces instructions that trigger an ArrayIndexOutofBounds exception 728579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * with an actual throw of the exception. 729579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 730579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param insn {@code non-null;} instruction causing the exception 731579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param index {@code non-null;} index value that is out of bounds 732579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param deletedInsns {@code non-null;} set of instructions marked for 733579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * deletion 734579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 735579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void insertExceptionThrow(SsaInsn insn, RegisterSpec index, 736579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson HashSet<SsaInsn> deletedInsns) { 737579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Create a new ArrayIndexOutOfBoundsException 738579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson CstType exception = 739579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson new CstType(Exceptions.TYPE_ArrayIndexOutOfBoundsException); 740579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insertThrowingInsnBefore(insn, RegisterSpecList.EMPTY, null, 741579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegOps.NEW_INSTANCE, exception); 742579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 743579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Add a successor block with a move result pseudo for the exception 744579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock currBlock = insn.getBlock(); 745579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock newBlock = 746579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson currBlock.insertNewSuccessor(currBlock.getPrimarySuccessor()); 747579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn newInsn = newBlock.getInsns().get(0); 748579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec newReg = 749579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec.make(ssaMeth.makeNewSsaReg(), exception); 750579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insertPlainInsnBefore(newInsn, RegisterSpecList.EMPTY, newReg, 751579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegOps.MOVE_RESULT_PSEUDO, null); 752579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 753579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Add another successor block to initialize the exception 754579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock newBlock2 = 755579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newBlock.insertNewSuccessor(newBlock.getPrimarySuccessor()); 756579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn newInsn2 = newBlock2.getInsns().get(0); 757579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson CstNat newNat = new CstNat(new CstString("<init>"), new CstString("(I)V")); 758579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson CstMethodRef newRef = new CstMethodRef(exception, newNat); 759579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insertThrowingInsnBefore(newInsn2, RegisterSpecList.make(newReg, index), 760579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson null, RegOps.INVOKE_DIRECT, newRef); 761579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson deletedInsns.add(newInsn2); 762579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 763579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Add another successor block to throw the new exception 764579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock newBlock3 = 765579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newBlock2.insertNewSuccessor(newBlock2.getPrimarySuccessor()); 766579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn newInsn3 = newBlock3.getInsns().get(0); 767579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insertThrowingInsnBefore(newInsn3, RegisterSpecList.make(newReg), null, 768579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegOps.THROW, null); 769579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newBlock3.replaceSuccessor(newBlock3.getPrimarySuccessorIndex(), 770579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaMeth.getExitBlock().getIndex()); 771579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson deletedInsns.add(newInsn3); 772579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 773579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 774579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 775579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Inserts a new PlainInsn before the given instruction. 776579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * TODO: move this somewhere more appropriate 777579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 778579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param insn {@code non-null;} instruction to insert before 779579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param newSources {@code non-null;} sources of new instruction 780579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param newResult {@code non-null;} result of new instruction 781579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param newOpcode opcode of new instruction 782579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param cst {@code null-ok;} constant for new instruction, if any 783579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 784579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void insertPlainInsnBefore(SsaInsn insn, 785579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpecList newSources, RegisterSpec newResult, int newOpcode, 786579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Constant cst) { 787579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 788579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Insn originalRopInsn = insn.getOriginalRopInsn(); 789579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Rop newRop; 790579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (newOpcode == RegOps.MOVE_RESULT_PSEUDO) { 791579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newRop = Rops.opMoveResultPseudo(newResult.getType()); 792579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 793579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newRop = Rops.ropFor(newOpcode, newResult, newSources, cst); 794579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 795579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 796579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Insn newRopInsn; 797579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (cst == null) { 798579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newRopInsn = new PlainInsn(newRop, 799579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson originalRopInsn.getPosition(), newResult, newSources); 800579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 801579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newRopInsn = new PlainCstInsn(newRop, 802579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson originalRopInsn.getPosition(), newResult, newSources, cst); 803579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 804579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 805579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson NormalSsaInsn newInsn = new NormalSsaInsn(newRopInsn, insn.getBlock()); 806579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson List<SsaInsn> insns = insn.getBlock().getInsns(); 807579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 808579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insns.add(insns.lastIndexOf(insn), newInsn); 809579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaMeth.onInsnAdded(newInsn); 810579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 811579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 812579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 813579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Inserts a new ThrowingInsn before the given instruction. 814579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * TODO: move this somewhere more appropriate 815579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 816579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param insn {@code non-null;} instruction to insert before 817579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param newSources {@code non-null;} sources of new instruction 818579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param newResult {@code non-null;} result of new instruction 819579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param newOpcode opcode of new instruction 820579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param cst {@code null-ok;} constant for new instruction, if any 821579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 822579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void insertThrowingInsnBefore(SsaInsn insn, 823579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpecList newSources, RegisterSpec newResult, int newOpcode, 824579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Constant cst) { 825579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 826579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Insn origRopInsn = insn.getOriginalRopInsn(); 827579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Rop newRop = Rops.ropFor(newOpcode, newResult, newSources, cst); 828579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Insn newRopInsn; 829579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (cst == null) { 830579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newRopInsn = new ThrowingInsn(newRop, 831579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson origRopInsn.getPosition(), newSources, StdTypeList.EMPTY); 832579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 833579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newRopInsn = new ThrowingCstInsn(newRop, 834579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson origRopInsn.getPosition(), newSources, StdTypeList.EMPTY, cst); 835579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 836579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 837579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson NormalSsaInsn newInsn = new NormalSsaInsn(newRopInsn, insn.getBlock()); 838579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson List<SsaInsn> insns = insn.getBlock().getInsns(); 839579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 840579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insns.add(insns.lastIndexOf(insn), newInsn); 841579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaMeth.onInsnAdded(newInsn); 842579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 843579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson} 844