1579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/* 2579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Copyright (C) 2007 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.RegOps; 20579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RegisterSpec; 21579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RegisterSpecList; 22579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.Rop; 23579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.PlainInsn; 24579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.Rops; 25579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.SourcePosition; 26579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.Insn; 27579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 28579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.ArrayList; 29579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.BitSet; 30579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.HashSet; 31579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 32579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/** 33579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * A variation on Appel Algorithm 19.12 "Dead code elimination in SSA form". 34579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 35579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * TODO this algorithm is more efficient if run in reverse from exit 36579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * block to entry block. 37579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 38579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic class DeadCodeRemover { 39579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** method we're processing */ 40579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final SsaMethod ssaMeth; 41579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 42579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** ssaMeth.getRegCount() */ 43579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final int regCount; 44579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 45579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 46579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * indexed by register: whether reg should be examined 47579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * (does it correspond to a no-side-effect insn?) 48579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 49579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final BitSet worklist; 50579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 51579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** use list indexed by register; modified during operation */ 52579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final ArrayList<SsaInsn>[] useList; 53579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 54579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 55579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Process a method with the dead-code remver 56579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 57579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param ssaMethod method to process 58579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 59579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static void process(SsaMethod ssaMethod) { 60579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson DeadCodeRemover dc = new DeadCodeRemover(ssaMethod); 61579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson dc.run(); 62579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 63579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 64579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 65579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Constructs an instance. 66579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 67579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param ssaMethod method to process 68579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 69579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private DeadCodeRemover(SsaMethod ssaMethod) { 70579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.ssaMeth = ssaMethod; 71579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 72579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson regCount = ssaMethod.getRegCount(); 73579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson worklist = new BitSet(regCount); 74579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson useList = ssaMeth.getUseListCopy(); 75579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 76579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 77579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 78579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Runs the dead code remover. 79579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 80579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void run() { 81579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson pruneDeadInstructions(); 82579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 83579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson HashSet<SsaInsn> deletedInsns = new HashSet<SsaInsn>(); 84579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 85579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaMeth.forEachInsn(new NoSideEffectVisitor(worklist)); 86579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 87579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int regV; 88579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 89579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson while ( 0 <= (regV = worklist.nextSetBit(0)) ) { 90579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson worklist.clear(regV); 91579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 92579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (useList[regV].size() == 0 93579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson || isCircularNoSideEffect(regV, null)) { 94579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 95579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn insnS = ssaMeth.getDefinitionForRegister(regV); 96579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 97579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // This insn has already been deleted. 98579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (deletedInsns.contains(insnS)) { 99579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson continue; 100579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 101579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 102579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpecList sources = insnS.getSources(); 103579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 104579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int sz = sources.size(); 105579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < sz; i++) { 106579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Delete this insn from all usage lists. 107579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec source = sources.get(i); 108579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson useList[source.getReg()].remove(insnS); 109579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 110579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!hasSideEffect( 111579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaMeth.getDefinitionForRegister( 112579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson source.getReg()))) { 113579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 114579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Only registers whose definition has no side effect 115579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * should be added back to the worklist. 116579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 117579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson worklist.set(source.getReg()); 118579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 119579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 120579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 121579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Schedule this insn for later deletion. 122579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson deletedInsns.add(insnS); 123579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 124579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 125579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 126579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaMeth.deleteInsns(deletedInsns); 127579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 128579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 129579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 130579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Removes all instructions from every unreachable block. 131579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 132579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void pruneDeadInstructions() { 133579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson HashSet<SsaInsn> deletedInsns = new HashSet<SsaInsn>(); 134579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 135579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaMeth.computeReachability(); 136579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 137579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (SsaBasicBlock block : ssaMeth.getBlocks()) { 138579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (block.isReachable()) continue; 139579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 140579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Prune instructions from unreachable blocks 141579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < block.getInsns().size(); i++) { 142579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn insn = block.getInsns().get(i); 143579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpecList sources = insn.getSources(); 144579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int sourcesSize = sources.size(); 145579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 146579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Delete this instruction completely if it has sources 147579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (sourcesSize != 0) { 148579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson deletedInsns.add(insn); 149579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 150579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 151579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Delete this instruction from all usage lists. 152579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int j = 0; j < sourcesSize; j++) { 153579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec source = sources.get(j); 154579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson useList[source.getReg()].remove(insn); 155579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 156579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 157579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Remove this instruction result from the sources of any phis 158579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec result = insn.getResult(); 159579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (result == null) continue; 160579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (SsaInsn use : useList[result.getReg()]) { 161579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (use instanceof PhiInsn) { 162579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson PhiInsn phiUse = (PhiInsn) use; 163579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson phiUse.removePhiRegister(result); 164579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 165579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 166579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 167579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 168579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 169579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaMeth.deleteInsns(deletedInsns); 170579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 171579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 172579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 173579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Returns true if the only uses of this register form a circle of 174579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * operations with no side effects. 175579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 176579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param regV register to examine 177579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param set a set of registers that we've already determined 178579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * are only used as sources in operations with no side effect or null 179579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * if this is the first recursion 180579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return true if usage is circular without side effect 181579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 182579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private boolean isCircularNoSideEffect(int regV, BitSet set) { 183579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if ((set != null) && set.get(regV)) { 184579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return true; 185579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 186579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 187579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (SsaInsn use : useList[regV]) { 188579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (hasSideEffect(use)) { 189579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return false; 190579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 191579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 192579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 193579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (set == null) { 194579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson set = new BitSet(regCount); 195579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 196579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 197579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // This register is only used in operations that have no side effect. 198579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson set.set(regV); 199579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 200579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (SsaInsn use : useList[regV]) { 201579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec result = use.getResult(); 202579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 203579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (result == null 204579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson || !isCircularNoSideEffect(result.getReg(), set)) { 205579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return false; 206579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 207579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 208579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 209579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return true; 210579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 211579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 212579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 213579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Returns true if this insn has a side-effect. Returns true 214579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * if the insn is null for reasons stated in the code block. 215579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 216579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param insn {@code null-ok;} instruction in question 217579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return true if it has a side-effect 218579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 219579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static boolean hasSideEffect(SsaInsn insn) { 220579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (insn == null) { 221579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* While false would seem to make more sense here, true 222579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * prevents us from adding this back to a worklist unnecessarally. 223579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 224579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return true; 225579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 226579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 227579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return insn.hasSideEffect(); 228579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 229579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 230579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 231579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * A callback class used to build up the initial worklist of 232579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * registers defined by an instruction with no side effect. 233579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 234579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson static private class NoSideEffectVisitor implements SsaInsn.Visitor { 235579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BitSet noSideEffectRegs; 236579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 237579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 238579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Passes in data structures that will be filled out after 239579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * ssaMeth.forEachInsn() is called with this instance. 240579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 241579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param noSideEffectRegs to-build bitset of regs that are 242579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * results of regs with no side effects 243579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 244579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public NoSideEffectVisitor(BitSet noSideEffectRegs) { 245579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.noSideEffectRegs = noSideEffectRegs; 246579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 247579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 248579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@inheritDoc} */ 249579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void visitMoveInsn (NormalSsaInsn insn) { 250579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // If we're tracking local vars, some moves have side effects. 251579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!hasSideEffect(insn)) { 252579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson noSideEffectRegs.set(insn.getResult().getReg()); 253579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 254579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 255579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 256579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@inheritDoc} */ 257579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void visitPhiInsn (PhiInsn phi) { 258579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // If we're tracking local vars, then some phis have side effects. 259579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!hasSideEffect(phi)) { 260579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson noSideEffectRegs.set(phi.getResult().getReg()); 261579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 262579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 263579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 264579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@inheritDoc} */ 265579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void visitNonMoveInsn (NormalSsaInsn insn) { 266579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec result = insn.getResult(); 267579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!hasSideEffect(insn) && result != null) { 268579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson noSideEffectRegs.set(result.getReg()); 269579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 270579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 271579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 272579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson} 273