1e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao/* 2e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Copyright (C) 2010 The Android Open Source Project 3e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 4e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Licensed under the Apache License, Version 2.0 (the "License"); 5e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * you may not use this file except in compliance with the License. 6e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * You may obtain a copy of the License at 7e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 8e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * http://www.apache.org/licenses/LICENSE-2.0 9e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 10e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Unless required by applicable law or agreed to in writing, software 11e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * distributed under the License is distributed on an "AS IS" BASIS, 12e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * See the License for the specific language governing permissions and 14e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * limitations under the License. 15e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 16e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 17e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaopackage com.android.dx.ssa; 18e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 19e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.code.Exceptions; 20e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.code.FillArrayDataInsn; 21e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.code.Insn; 22e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.code.PlainCstInsn; 23e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.code.PlainInsn; 24e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.code.RegOps; 25e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.code.RegisterSpec; 26e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.code.RegisterSpecList; 27e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.code.Rop; 28e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.code.Rops; 29e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.code.ThrowingCstInsn; 30e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.code.ThrowingInsn; 31e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.cst.Constant; 32e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.cst.CstLiteralBits; 33e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.cst.CstMethodRef; 34e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.cst.CstNat; 35333201833d506a3accdeac6ceb7caba8d4b95797Jesse Wilsonimport com.android.dx.rop.cst.CstString; 36e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.cst.CstType; 37e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.cst.TypedConstant; 38e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.cst.Zeroes; 39e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.type.StdTypeList; 40e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.type.Type; 41e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.type.TypeBearer; 42e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 43e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport java.util.ArrayList; 44e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport java.util.BitSet; 45e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport java.util.HashSet; 46e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport java.util.List; 47e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 48e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao/** 49e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Simple intraprocedural escape analysis. Finds new arrays that don't escape 50e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * the method they are created in and replaces the array values with registers. 51e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 52e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaopublic class EscapeAnalysis { 53e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 54e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Struct used to generate and maintain escape analysis results. 55e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 56e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao static class EscapeSet { 57e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** set containing all registers related to an object */ 58e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao BitSet regSet; 59e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** escape state of the object */ 60e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao EscapeState escape; 61e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** list of objects that are put into this object */ 62e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao ArrayList<EscapeSet> childSets; 63e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** list of objects that this object is put into */ 64e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao ArrayList<EscapeSet> parentSets; 65e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** flag to indicate this object is a scalar replaceable array */ 66e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao boolean replaceableArray; 67e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 68e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 69e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Constructs an instance of an EscapeSet 70e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 71e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param reg the SSA register that defines the object 72e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param size the number of registers in the method 73e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param escState the lattice value to initially set this to 74e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 75e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao EscapeSet(int reg, int size, EscapeState escState) { 76e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao regSet = new BitSet(size); 77e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao regSet.set(reg); 78e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escape = escState; 79e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao childSets = new ArrayList<EscapeSet>(); 80e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao parentSets = new ArrayList<EscapeSet>(); 81e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao replaceableArray = false; 82e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 83e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 84e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 85e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 86e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Lattice values used to indicate escape state for an object. Analysis can 87e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * only raise escape state values, not lower them. 88e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 89e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * TOP - Used for objects that haven't been analyzed yet 90e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * NONE - Object does not escape, and is eligible for scalar replacement. 91e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * METHOD - Object remains local to method, but can't be scalar replaced. 92e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * INTER - Object is passed between methods. (treated as globally escaping 93e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * since this is an intraprocedural analysis) 94e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * GLOBAL - Object escapes globally. 95e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 96e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao public enum EscapeState { 97e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao TOP, NONE, METHOD, INTER, GLOBAL 98e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 99e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 100e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** method we're processing */ 101e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private SsaMethod ssaMeth; 102e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** ssaMeth.getRegCount() */ 103e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private int regCount; 104e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** Lattice values for each object register group */ 105e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private ArrayList<EscapeSet> latticeValues; 106e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 107e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 108e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Constructs an instance. 109e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 110e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param ssaMeth method to process 111e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 112e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private EscapeAnalysis(SsaMethod ssaMeth) { 113e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao this.ssaMeth = ssaMeth; 114e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao this.regCount = ssaMeth.getRegCount(); 115e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao this.latticeValues = new ArrayList<EscapeSet>(); 116e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 117e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 118e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 119e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Finds the index in the lattice for a particular register. 120e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Returns the size of the lattice if the register wasn't found. 121e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 122e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param reg {@code non-null;} register being looked up 123e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @return index of the register or size of the lattice if it wasn't found. 124e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 125e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private int findSetIndex(RegisterSpec reg) { 126e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao int i; 127e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao for (i = 0; i < latticeValues.size(); i++) { 128e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao EscapeSet e = latticeValues.get(i); 129e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (e.regSet.get(reg.getReg())) { 130e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao return i; 131e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 132e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 133e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao return i; 134e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 135e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 136e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 137e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Finds the corresponding instruction for a given move result 138e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 139e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param moveInsn {@code non-null;} a move result instruction 140e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @return {@code non-null;} the instruction that produces the result for 141e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * the move 142e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 143e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private SsaInsn getInsnForMove(SsaInsn moveInsn) { 144e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao int pred = moveInsn.getBlock().getPredecessors().nextSetBit(0); 145e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao ArrayList<SsaInsn> predInsns = ssaMeth.getBlocks().get(pred).getInsns(); 146e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao return predInsns.get(predInsns.size()-1); 147e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 148e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 149e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 150e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Finds the corresponding move result for a given instruction 151e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 152e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param insn {@code non-null;} an instruction that must always be 153e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * followed by a move result 154e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @return {@code non-null;} the move result for the given instruction 155e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 156e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private SsaInsn getMoveForInsn(SsaInsn insn) { 157e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao int succ = insn.getBlock().getSuccessors().nextSetBit(0); 158e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao ArrayList<SsaInsn> succInsns = ssaMeth.getBlocks().get(succ).getInsns(); 159e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao return succInsns.get(0); 160e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 161e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 162e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 163e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Creates a link in the lattice between two EscapeSets due to a put 164e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * instruction. The object being put is the child and the object being put 165e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * into is the parent. A child set must always have an escape state at 166e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * least as high as its parent. 167e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 168e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param parentSet {@code non-null;} the EscapeSet for the object being put 169e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * into 170e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param childSet {@code non-null;} the EscapeSet for the object being put 171e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 172e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private void addEdge(EscapeSet parentSet, EscapeSet childSet) { 173e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (!childSet.parentSets.contains(parentSet)) { 174e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao childSet.parentSets.add(parentSet); 175e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 176e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (!parentSet.childSets.contains(childSet)) { 177e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao parentSet.childSets.add(childSet); 178e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 179e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 180e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 181e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 182e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Merges all links in the lattice among two EscapeSets. On return, the 183e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * newNode will have its old links as well as all links from the oldNode. 184e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * The oldNode has all its links removed. 185e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 186e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param newNode {@code non-null;} the EscapeSet to merge all links into 187e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param oldNode {@code non-null;} the EscapeSet to remove all links from 188e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 189e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private void replaceNode(EscapeSet newNode, EscapeSet oldNode) { 190e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao for (EscapeSet e : oldNode.parentSets) { 191e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao e.childSets.remove(oldNode); 192e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao e.childSets.add(newNode); 193e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao newNode.parentSets.add(e); 194e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 195e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao for (EscapeSet e : oldNode.childSets) { 196e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao e.parentSets.remove(oldNode); 197e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao e.parentSets.add(newNode); 198e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao newNode.childSets.add(e); 199e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 200e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 201e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 202e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 203e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Performs escape analysis on a method. Finds scalar replaceable arrays and 204e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * replaces them with equivalent registers. 205e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 206e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param ssaMethod {@code non-null;} method to process 207e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 208e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao public static void process(SsaMethod ssaMethod) { 209e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao new EscapeAnalysis(ssaMethod).run(); 210e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 211e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 212e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 213e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Process a single instruction, looking for new objects resulting from 214e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * move result or move param. 215e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 216e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param insn {@code non-null;} instruction to process 217e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 218e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private void processInsn(SsaInsn insn) { 219e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao int op = insn.getOpcode().getOpcode(); 220e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegisterSpec result = insn.getResult(); 221e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao EscapeSet escSet; 222e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 223e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Identify new objects 224e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (op == RegOps.MOVE_RESULT_PSEUDO && 225e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao result.getTypeBearer().getBasicType() == Type.BT_OBJECT) { 226e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Handle objects generated through move_result_pseudo 227e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet = processMoveResultPseudoInsn(insn); 228e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao processRegister(result, escSet); 229e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } else if (op == RegOps.MOVE_PARAM && 230e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao result.getTypeBearer().getBasicType() == Type.BT_OBJECT) { 231e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Track method arguments that are objects 232e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet = new EscapeSet(result.getReg(), regCount, EscapeState.NONE); 233e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao latticeValues.add(escSet); 234e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao processRegister(result, escSet); 235e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } else if (op == RegOps.MOVE_RESULT && 236e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao result.getTypeBearer().getBasicType() == Type.BT_OBJECT) { 237e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Track method return values that are objects 238e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet = new EscapeSet(result.getReg(), regCount, EscapeState.NONE); 239e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao latticeValues.add(escSet); 240e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao processRegister(result, escSet); 241e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 242e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 243e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 244e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 245e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Determine the origin of a move result pseudo instruction that generates 246e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * an object. Creates a new EscapeSet for the new object accordingly. 247e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 248e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param insn {@code non-null;} move result pseudo instruction to process 249e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @return {@code non-null;} an EscapeSet for the object referred to by the 250e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * move result pseudo instruction 251e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 252e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private EscapeSet processMoveResultPseudoInsn(SsaInsn insn) { 253e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegisterSpec result = insn.getResult(); 254e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao SsaInsn prevSsaInsn = getInsnForMove(insn); 255e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao int prevOpcode = prevSsaInsn.getOpcode().getOpcode(); 256e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao EscapeSet escSet; 257e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegisterSpec prevSource; 258e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 259e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao switch(prevOpcode) { 260e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // New instance / Constant 261e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.NEW_INSTANCE: 262e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.CONST: 263e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet = new EscapeSet(result.getReg(), regCount, 264e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao EscapeState.NONE); 265e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao break; 266e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // New array 267e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.NEW_ARRAY: 268e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.FILLED_NEW_ARRAY: 269e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao prevSource = prevSsaInsn.getSources().get(0); 270e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (prevSource.getTypeBearer().isConstant()) { 271e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // New fixed array 272e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet = new EscapeSet(result.getReg(), regCount, 273e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao EscapeState.NONE); 274e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet.replaceableArray = true; 275e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } else { 276e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // New variable array 277e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet = new EscapeSet(result.getReg(), regCount, 278e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao EscapeState.GLOBAL); 279e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 280e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao break; 281e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Loading a static object 282e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.GET_STATIC: 283e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet = new EscapeSet(result.getReg(), regCount, 284e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao EscapeState.GLOBAL); 285e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao break; 286e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Type cast / load an object from a field or array 287e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.CHECK_CAST: 288e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.GET_FIELD: 289e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.AGET: 290e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao prevSource = prevSsaInsn.getSources().get(0); 291e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao int setIndex = findSetIndex(prevSource); 292e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 293e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Set should already exist, try to find it 294e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (setIndex != latticeValues.size()) { 295e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet = latticeValues.get(setIndex); 296e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet.regSet.set(result.getReg()); 297e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao return escSet; 298e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 299e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 300e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Set not found, must be either null or unknown 301e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (prevSource.getType() == Type.KNOWN_NULL) { 302e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet = new EscapeSet(result.getReg(), regCount, 303e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao EscapeState.NONE); 304e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } else { 305e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet = new EscapeSet(result.getReg(), regCount, 306e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao EscapeState.GLOBAL); 307e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 308e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao break; 309e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao default: 310e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao return null; 311e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 312e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 313e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Add the newly created escSet to the lattice and return it 314e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao latticeValues.add(escSet); 315e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao return escSet; 316e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 317e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 318e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 319e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Iterate through all the uses of a new object. 320e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 321e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param result {@code non-null;} register where new object is stored 322e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param escSet {@code non-null;} EscapeSet for the new object 323e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 324e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private void processRegister(RegisterSpec result, EscapeSet escSet) { 325e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao ArrayList<RegisterSpec> regWorklist = new ArrayList<RegisterSpec>(); 326e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao regWorklist.add(result); 327e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 328e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Go through the worklist 329e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao while (!regWorklist.isEmpty()) { 330e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao int listSize = regWorklist.size() - 1; 331e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegisterSpec def = regWorklist.remove(listSize); 332e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao List<SsaInsn> useList = ssaMeth.getUseListForRegister(def.getReg()); 333e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 334e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Handle all the uses of this register 335e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao for (SsaInsn use : useList) { 336e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao Rop useOpcode = use.getOpcode(); 337e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 338e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (useOpcode == null) { 339e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Handle phis 340e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao processPhiUse(use, escSet, regWorklist); 341e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } else { 342e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Handle other opcodes 343e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao processUse(def, use, escSet, regWorklist); 344e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 345e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 346e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 347e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 348e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 349e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 350e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Handles phi uses of new objects. Will merge together the sources of a phi 351e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * into a single EscapeSet. Adds the result of the phi to the worklist so 352e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * its uses can be followed. 353e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 354e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param use {@code non-null;} phi use being processed 355e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param escSet {@code non-null;} EscapeSet for the object 356e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param regWorklist {@code non-null;} worklist of instructions left to 357e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * process for this object 358e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 359e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private void processPhiUse(SsaInsn use, EscapeSet escSet, 360e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao ArrayList<RegisterSpec> regWorklist) { 361e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao int setIndex = findSetIndex(use.getResult()); 362e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (setIndex != latticeValues.size()) { 363e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Check if result is in a set already 364e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao EscapeSet mergeSet = latticeValues.get(setIndex); 365e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (mergeSet != escSet) { 366e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // If it is, merge the sets and states, then delete the copy 367e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet.replaceableArray = false; 368e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet.regSet.or(mergeSet.regSet); 369e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (escSet.escape.compareTo(mergeSet.escape) < 0) { 370e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet.escape = mergeSet.escape; 371e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 372e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao replaceNode(escSet, mergeSet); 373e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao latticeValues.remove(setIndex); 374e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 375e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } else { 376e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // If no set is found, add it to this escSet and the worklist 377e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet.regSet.set(use.getResult().getReg()); 378e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao regWorklist.add(use.getResult()); 379e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 380e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 381e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 382e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 383e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Handles non-phi uses of new objects. Checks to see how instruction is 384e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * used and updates the escape state accordingly. 385e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 386e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param def {@code non-null;} register holding definition of new object 387e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param use {@code non-null;} use of object being processed 388e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param escSet {@code non-null;} EscapeSet for the object 389e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param regWorklist {@code non-null;} worklist of instructions left to 390e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * process for this object 391e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 392e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private void processUse(RegisterSpec def, SsaInsn use, EscapeSet escSet, 393e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao ArrayList<RegisterSpec> regWorklist) { 394e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao int useOpcode = use.getOpcode().getOpcode(); 395e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao switch (useOpcode) { 396e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.MOVE: 397e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Follow uses of the move by adding it to the worklist 398e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet.regSet.set(use.getResult().getReg()); 399e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao regWorklist.add(use.getResult()); 400e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao break; 401e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.IF_EQ: 402e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.IF_NE: 403e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.CHECK_CAST: 404e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Compared objects can't be replaced, so promote if necessary 405e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (escSet.escape.compareTo(EscapeState.METHOD) < 0) { 406e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet.escape = EscapeState.METHOD; 407e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 408e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao break; 409e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.APUT: 410e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // For array puts, check for a constant array index 411e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegisterSpec putIndex = use.getSources().get(2); 412e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (!putIndex.getTypeBearer().isConstant()) { 413e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // If not constant, array can't be replaced 414e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet.replaceableArray = false; 415e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 416e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Intentional fallthrough 417e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.PUT_FIELD: 418e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Skip non-object puts 419e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegisterSpec putValue = use.getSources().get(0); 420e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (putValue.getTypeBearer().getBasicType() != Type.BT_OBJECT) { 421e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao break; 422e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 423e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet.replaceableArray = false; 424e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 425e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Raise 1st object's escape state to 2nd if 2nd is higher 426e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegisterSpecList sources = use.getSources(); 427e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (sources.get(0).getReg() == def.getReg()) { 428e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao int setIndex = findSetIndex(sources.get(1)); 429e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (setIndex != latticeValues.size()) { 430e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao EscapeSet parentSet = latticeValues.get(setIndex); 431e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao addEdge(parentSet, escSet); 432e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (escSet.escape.compareTo(parentSet.escape) < 0) { 433e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet.escape = parentSet.escape; 434e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 435e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 436e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } else { 437e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao int setIndex = findSetIndex(sources.get(0)); 438e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (setIndex != latticeValues.size()) { 439e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao EscapeSet childSet = latticeValues.get(setIndex); 440e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao addEdge(escSet, childSet); 441e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (childSet.escape.compareTo(escSet.escape) < 0) { 442e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao childSet.escape = escSet.escape; 443e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 444e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 445e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 446e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao break; 447e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.AGET: 448e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // For array gets, check for a constant array index 449e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegisterSpec getIndex = use.getSources().get(1); 450e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (!getIndex.getTypeBearer().isConstant()) { 451e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // If not constant, array can't be replaced 452e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet.replaceableArray = false; 453e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 454e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao break; 455e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.PUT_STATIC: 456e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Static puts cause an object to escape globally 457e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet.escape = EscapeState.GLOBAL; 458e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao break; 459e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.INVOKE_STATIC: 460e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.INVOKE_VIRTUAL: 461e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.INVOKE_SUPER: 462e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.INVOKE_DIRECT: 463e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.INVOKE_INTERFACE: 464e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.RETURN: 465e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.THROW: 466e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // These operations cause an object to escape interprocedurally 467e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao escSet.escape = EscapeState.INTER; 468e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao break; 469e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao default: 470e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao break; 471e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 472e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 473e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 474e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 475e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Performs scalar replacement on all eligible arrays. 476e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 477e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private void scalarReplacement() { 478e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Iterate through lattice, looking for non-escaping replaceable arrays 479e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao for (EscapeSet escSet : latticeValues) { 480e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (!escSet.replaceableArray || escSet.escape != EscapeState.NONE) { 481e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao continue; 482e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 483e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 484e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Get the instructions for the definition and move of the array 485e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao int e = escSet.regSet.nextSetBit(0); 486e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao SsaInsn def = ssaMeth.getDefinitionForRegister(e); 487e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao SsaInsn prev = getInsnForMove(def); 488e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 489e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Create a map for the new registers that will be created 490e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao TypeBearer lengthReg = prev.getSources().get(0).getTypeBearer(); 491e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao int length = ((CstLiteralBits) lengthReg).getIntBits(); 492e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao ArrayList<RegisterSpec> newRegs = 493e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao new ArrayList<RegisterSpec>(length); 494e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao HashSet<SsaInsn> deletedInsns = new HashSet<SsaInsn>(); 495e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 496e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Replace the definition of the array with registers 497e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao replaceDef(def, prev, length, newRegs); 498e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 499e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Mark definition instructions for deletion 500e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao deletedInsns.add(prev); 501e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao deletedInsns.add(def); 502e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 503e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Go through all uses of the array 504e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao List<SsaInsn> useList = ssaMeth.getUseListForRegister(e); 505e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao for (SsaInsn use : useList) { 506e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Replace the use with scalars and then mark it for deletion 507e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao replaceUse(use, prev, newRegs, deletedInsns); 508e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao deletedInsns.add(use); 509e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 510e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 511e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Delete all marked instructions 512e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao ssaMeth.deleteInsns(deletedInsns); 513e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao ssaMeth.onInsnsChanged(); 514e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 515e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Convert the method back to SSA form 516e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao SsaConverter.updateSsaMethod(ssaMeth, regCount); 517e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 518e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Propagate and remove extra moves added by scalar replacement 519e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao movePropagate(); 520e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 521e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 522e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 523e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 524e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Replaces the instructions that define an array with equivalent registers. 525e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * For each entry in the array, a register is created, initialized to zero. 526e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * A mapping between this register and the corresponding array index is 527e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * added. 528e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 529e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param def {@code non-null;} move result instruction for array 530e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param prev {@code non-null;} instruction for instantiating new array 531e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param length size of the new array 532e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param newRegs {@code non-null;} mapping of array indices to new 533e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * registers to be populated 534e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 535e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private void replaceDef(SsaInsn def, SsaInsn prev, int length, 536e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao ArrayList<RegisterSpec> newRegs) { 537e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao Type resultType = def.getResult().getType(); 538e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 539e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Create new zeroed out registers for each element in the array 540e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao for (int i = 0; i < length; i++) { 541e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao Constant newZero = Zeroes.zeroFor(resultType.getComponentType()); 542e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao TypedConstant typedZero = (TypedConstant) newZero; 543e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegisterSpec newReg = 544e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegisterSpec.make(ssaMeth.makeNewSsaReg(), typedZero); 545e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao newRegs.add(newReg); 546e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao insertPlainInsnBefore(def, RegisterSpecList.EMPTY, newReg, 547e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegOps.CONST, newZero); 548e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 549e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 550e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 551e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 552e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Replaces the use for a scalar replaceable array. Gets and puts become 553e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * move instructions, and array lengths and fills are handled. Can also 554e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * identify ArrayIndexOutOfBounds exceptions and throw them if detected. 555e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 556e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param use {@code non-null;} move result instruction for array 557e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param prev {@code non-null;} instruction for instantiating new array 558e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param newRegs {@code non-null;} mapping of array indices to new 559e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * registers 560e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param deletedInsns {@code non-null;} set of instructions marked for 561e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * deletion 562e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 563e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private void replaceUse(SsaInsn use, SsaInsn prev, 564e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao ArrayList<RegisterSpec> newRegs, 565e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao HashSet<SsaInsn> deletedInsns) { 566e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao int index; 567e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao int length = newRegs.size(); 568e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao SsaInsn next; 569e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegisterSpecList sources; 570e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegisterSpec source, result; 571e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao CstLiteralBits indexReg; 572e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 573e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao switch (use.getOpcode().getOpcode()) { 574e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.AGET: 575e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Replace array gets with moves 576e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao next = getMoveForInsn(use); 577e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao sources = use.getSources(); 578e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao indexReg = ((CstLiteralBits) sources.get(1).getTypeBearer()); 579e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao index = indexReg.getIntBits(); 580e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (index < length) { 581e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao source = newRegs.get(index); 582e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao result = source.withReg(next.getResult().getReg()); 583e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao insertPlainInsnBefore(next, RegisterSpecList.make(source), 584e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao result, RegOps.MOVE, null); 585e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } else { 586e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Throw an exception if the index is out of bounds 587e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao insertExceptionThrow(next, sources.get(1), deletedInsns); 588e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao deletedInsns.add(next.getBlock().getInsns().get(2)); 589e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 590e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao deletedInsns.add(next); 591e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao break; 592e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.APUT: 593e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Replace array puts with moves 594e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao sources = use.getSources(); 595e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao indexReg = ((CstLiteralBits) sources.get(2).getTypeBearer()); 596e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao index = indexReg.getIntBits(); 597e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (index < length) { 598e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao source = sources.get(0); 599e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao result = source.withReg(newRegs.get(index).getReg()); 600e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao insertPlainInsnBefore(use, RegisterSpecList.make(source), 601e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao result, RegOps.MOVE, null); 602e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Update the newReg entry to mark value as unknown now 603e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao newRegs.set(index, result.withSimpleType()); 604e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } else { 605e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Throw an exception if the index is out of bounds 606e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao insertExceptionThrow(use, sources.get(2), deletedInsns); 607e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 608e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao break; 609e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.ARRAY_LENGTH: 610e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Replace array lengths with const instructions 611e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao TypeBearer lengthReg = prev.getSources().get(0).getTypeBearer(); 612e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao //CstInteger lengthReg = CstInteger.make(length); 613e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao next = getMoveForInsn(use); 614e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao insertPlainInsnBefore(next, RegisterSpecList.EMPTY, 615e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao next.getResult(), RegOps.CONST, 616e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao (Constant) lengthReg); 617e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao deletedInsns.add(next); 618e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao break; 619e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.MARK_LOCAL: 620e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Remove mark local instructions 621e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao break; 622e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao case RegOps.FILL_ARRAY_DATA: 623e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Create const instructions for each fill value 624e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao Insn ropUse = use.getOriginalRopInsn(); 625e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao FillArrayDataInsn fill = (FillArrayDataInsn) ropUse; 626e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao ArrayList<Constant> constList = fill.getInitValues(); 627e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao for (int i = 0; i < length; i++) { 628e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegisterSpec newFill = 629e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegisterSpec.make(newRegs.get(i).getReg(), 630e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao (TypeBearer) constList.get(i)); 631e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao insertPlainInsnBefore(use, RegisterSpecList.EMPTY, newFill, 632e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegOps.CONST, constList.get(i)); 633e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Update the newRegs to hold the new const value 634e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao newRegs.set(i, newFill); 635e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 636e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao break; 637e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao default: 638e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 639e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 640e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 641e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 642e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Identifies extra moves added by scalar replacement and propagates the 643e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * source of the move to any users of the result. 644e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 645e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private void movePropagate() { 646e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao for (int i = 0; i < ssaMeth.getRegCount(); i++) { 647e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao SsaInsn insn = ssaMeth.getDefinitionForRegister(i); 648e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 649e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Look for move instructions only 650e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (insn == null || insn.getOpcode() == null || 651e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao insn.getOpcode().getOpcode() != RegOps.MOVE) { 652e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao continue; 653e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 654e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 655e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao final ArrayList<SsaInsn>[] useList = ssaMeth.getUseListCopy(); 656e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao final RegisterSpec source = insn.getSources().get(0); 657e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao final RegisterSpec result = insn.getResult(); 658e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 659e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Ignore moves that weren't added due to scalar replacement 660e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (source.getReg() < regCount && result.getReg() < regCount) { 661e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao continue; 662e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 663e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 664e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Create a mapping from source to result 665e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegisterMapper mapper = new RegisterMapper() { 666e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao @Override 667e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao public int getNewRegisterCount() { 668e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao return ssaMeth.getRegCount(); 669e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 670e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 671e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao @Override 672e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao public RegisterSpec map(RegisterSpec registerSpec) { 673e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (registerSpec.getReg() == result.getReg()) { 674e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao return source; 675e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 676e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 677e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao return registerSpec; 678e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 679e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao }; 680e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 681e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Modify all uses of the move to use the source of the move instead 682e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao for (SsaInsn use : useList[result.getReg()]) { 683e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao use.mapSourceRegisters(mapper); 684e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 685e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 686e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 687e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 688e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 689e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Runs escape analysis and scalar replacement of arrays. 690e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 691e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private void run() { 692e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao ssaMeth.forEachBlockDepthFirstDom(new SsaBasicBlock.Visitor() { 693e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao public void visitBlock (SsaBasicBlock block, 694e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao SsaBasicBlock unused) { 695e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao block.forEachInsn(new SsaInsn.Visitor() { 696e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao public void visitMoveInsn(NormalSsaInsn insn) { 697e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // do nothing 698e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 699e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 700e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao public void visitPhiInsn(PhiInsn insn) { 701e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // do nothing 702e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 703e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 704e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao public void visitNonMoveInsn(NormalSsaInsn insn) { 705e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao processInsn(insn); 706e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 707e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao }); 708e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 709e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao }); 710e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 711e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Go through lattice and promote fieldSets as necessary 712e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao for (EscapeSet e : latticeValues) { 713e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (e.escape != EscapeState.NONE) { 714e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao for (EscapeSet field : e.childSets) { 715e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (e.escape.compareTo(field.escape) > 0) { 716e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao field.escape = e.escape; 717e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 718e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 719e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 720e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 721e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 722e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Perform scalar replacement for arrays 723e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao scalarReplacement(); 724e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 725e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 726e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 727e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Replaces instructions that trigger an ArrayIndexOutofBounds exception 728e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * with an actual throw of the exception. 729e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 730e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param insn {@code non-null;} instruction causing the exception 731e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param index {@code non-null;} index value that is out of bounds 732e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param deletedInsns {@code non-null;} set of instructions marked for 733e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * deletion 734e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 735e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private void insertExceptionThrow(SsaInsn insn, RegisterSpec index, 736e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao HashSet<SsaInsn> deletedInsns) { 737e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Create a new ArrayIndexOutOfBoundsException 738e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao CstType exception = 739e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao new CstType(Exceptions.TYPE_ArrayIndexOutOfBoundsException); 740e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao insertThrowingInsnBefore(insn, RegisterSpecList.EMPTY, null, 741e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegOps.NEW_INSTANCE, exception); 742e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 743e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Add a successor block with a move result pseudo for the exception 744e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao SsaBasicBlock currBlock = insn.getBlock(); 745e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao SsaBasicBlock newBlock = 746e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao currBlock.insertNewSuccessor(currBlock.getPrimarySuccessor()); 747e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao SsaInsn newInsn = newBlock.getInsns().get(0); 748e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegisterSpec newReg = 749e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegisterSpec.make(ssaMeth.makeNewSsaReg(), exception); 750e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao insertPlainInsnBefore(newInsn, RegisterSpecList.EMPTY, newReg, 751e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegOps.MOVE_RESULT_PSEUDO, null); 752e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 753e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Add another successor block to initialize the exception 754e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao SsaBasicBlock newBlock2 = 755e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao newBlock.insertNewSuccessor(newBlock.getPrimarySuccessor()); 756e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao SsaInsn newInsn2 = newBlock2.getInsns().get(0); 757333201833d506a3accdeac6ceb7caba8d4b95797Jesse Wilson CstNat newNat = new CstNat(new CstString("<init>"), new CstString("(I)V")); 758e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao CstMethodRef newRef = new CstMethodRef(exception, newNat); 759e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao insertThrowingInsnBefore(newInsn2, RegisterSpecList.make(newReg, index), 760e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao null, RegOps.INVOKE_DIRECT, newRef); 761e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao deletedInsns.add(newInsn2); 762e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 763e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Add another successor block to throw the new exception 764e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao SsaBasicBlock newBlock3 = 765e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao newBlock2.insertNewSuccessor(newBlock2.getPrimarySuccessor()); 766e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao SsaInsn newInsn3 = newBlock3.getInsns().get(0); 767e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao insertThrowingInsnBefore(newInsn3, RegisterSpecList.make(newReg), null, 768e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegOps.THROW, null); 769e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao newBlock3.replaceSuccessor(newBlock3.getPrimarySuccessorIndex(), 770e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao ssaMeth.getExitBlock().getIndex()); 771e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao deletedInsns.add(newInsn3); 772e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 773e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 774e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 775e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Inserts a new PlainInsn before the given instruction. 776e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * TODO: move this somewhere more appropriate 777e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 778e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param insn {@code non-null;} instruction to insert before 779e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param newSources {@code non-null;} sources of new instruction 780e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param newResult {@code non-null;} result of new instruction 781e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param newOpcode opcode of new instruction 782e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param cst {@code null-ok;} constant for new instruction, if any 783e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 784e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private void insertPlainInsnBefore(SsaInsn insn, 785e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegisterSpecList newSources, RegisterSpec newResult, int newOpcode, 786e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao Constant cst) { 787e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 788e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao Insn originalRopInsn = insn.getOriginalRopInsn(); 789e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao Rop newRop; 790e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (newOpcode == RegOps.MOVE_RESULT_PSEUDO) { 791e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao newRop = Rops.opMoveResultPseudo(newResult.getType()); 792e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } else { 793e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao newRop = Rops.ropFor(newOpcode, newResult, newSources, cst); 794e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 795e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 796e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao Insn newRopInsn; 797e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (cst == null) { 798e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao newRopInsn = new PlainInsn(newRop, 799e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao originalRopInsn.getPosition(), newResult, newSources); 800e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } else { 801e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao newRopInsn = new PlainCstInsn(newRop, 802e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao originalRopInsn.getPosition(), newResult, newSources, cst); 803e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 804e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 805e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao NormalSsaInsn newInsn = new NormalSsaInsn(newRopInsn, insn.getBlock()); 806e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao List<SsaInsn> insns = insn.getBlock().getInsns(); 807e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 808e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao insns.add(insns.lastIndexOf(insn), newInsn); 809e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao ssaMeth.onInsnAdded(newInsn); 810e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 811e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 812e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 813e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Inserts a new ThrowingInsn before the given instruction. 814e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * TODO: move this somewhere more appropriate 815e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 816e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param insn {@code non-null;} instruction to insert before 817e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param newSources {@code non-null;} sources of new instruction 818e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param newResult {@code non-null;} result of new instruction 819e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param newOpcode opcode of new instruction 820e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param cst {@code null-ok;} constant for new instruction, if any 821e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 822e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private void insertThrowingInsnBefore(SsaInsn insn, 823e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao RegisterSpecList newSources, RegisterSpec newResult, int newOpcode, 824e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao Constant cst) { 825e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 826e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao Insn origRopInsn = insn.getOriginalRopInsn(); 827e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao Rop newRop = Rops.ropFor(newOpcode, newResult, newSources, cst); 828e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao Insn newRopInsn; 829e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (cst == null) { 830e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao newRopInsn = new ThrowingInsn(newRop, 831e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao origRopInsn.getPosition(), newSources, StdTypeList.EMPTY); 832e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } else { 833e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao newRopInsn = new ThrowingCstInsn(newRop, 834e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao origRopInsn.getPosition(), newSources, StdTypeList.EMPTY, cst); 835e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 836e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 837e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao NormalSsaInsn newInsn = new NormalSsaInsn(newRopInsn, insn.getBlock()); 838e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao List<SsaInsn> insns = insn.getBlock().getInsns(); 839e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 840e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao insns.add(insns.lastIndexOf(insn), newInsn); 841e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao ssaMeth.onInsnAdded(newInsn); 842e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 843e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao} 844