1f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 2f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Copyright (C) 2007 The Android Open Source Project 3f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 4f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 5f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * you may not use this file except in compliance with the License. 6f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * You may obtain a copy of the License at 7f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 8f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 9f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 10f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 11f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 12f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * See the License for the specific language governing permissions and 14f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * limitations under the License. 15f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 16f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 17f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpackage com.android.dx.ssa; 18f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 19f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.RegOps; 20f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.RegisterSpec; 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.RegisterSpecList; 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.Rop; 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.PlainInsn; 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.Rops; 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.SourcePosition; 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.Insn; 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.ArrayList; 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.BitSet; 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.HashSet; 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * A variation on Appel Algorithm 19.12 "Dead code elimination in SSA form". 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * TODO this algorithm is more efficient if run in reverse from exit 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * block to entry block. 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic class DeadCodeRemover { 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** method we're processing */ 4099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private final SsaMethod ssaMeth; 4199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** ssaMeth.getRegCount() */ 4399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private final int regCount; 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * indexed by register: whether reg should be examined 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * (does it correspond to a no-side-effect insn?) 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 4999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private final BitSet worklist; 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** use list indexed by register; modified during operation */ 5299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private final ArrayList<SsaInsn>[] useList; 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Process a method with the dead-code remver 56de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param ssaMethod method to process 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public static void process(SsaMethod ssaMethod) { 6099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project DeadCodeRemover dc = new DeadCodeRemover(ssaMethod); 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project dc.run(); 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 6499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** 6599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Constructs an instance. 66de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 6799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaMethod method to process 6899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project */ 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private DeadCodeRemover(SsaMethod ssaMethod) { 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.ssaMeth = ssaMethod; 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regCount = ssaMethod.getRegCount(); 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project worklist = new BitSet(regCount); 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project useList = ssaMeth.getUseListCopy(); 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 7899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Runs the dead code remover. 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void run() { 81b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao pruneDeadInstructions(); 82b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao 83b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao HashSet<SsaInsn> deletedInsns = new HashSet<SsaInsn>(); 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaMeth.forEachInsn(new NoSideEffectVisitor(worklist)); 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int regV; 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 8999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project while ( 0 <= (regV = worklist.nextSetBit(0)) ) { 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project worklist.clear(regV); 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (useList[regV].size() == 0 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project || isCircularNoSideEffect(regV, null)) { 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn insnS = ssaMeth.getDefinitionForRegister(regV); 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 9799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // This insn has already been deleted. 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (deletedInsns.contains(insnS)) { 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList sources = insnS.getSources(); 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = sources.size(); 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 10699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // Delete this insn from all usage lists. 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec source = sources.get(i); 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project useList[source.getReg()].remove(insnS); 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!hasSideEffect( 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaMeth.getDefinitionForRegister( 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project source.getReg()))) { 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 11499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Only registers whose definition has no side effect 11599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * should be added back to the worklist. 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project worklist.set(source.getReg()); 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 12199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // Schedule this insn for later deletion. 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project deletedInsns.add(insnS); 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaMeth.deleteInsns(deletedInsns); 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 130b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao * Removes all instructions from every unreachable block. 131b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao */ 132b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao private void pruneDeadInstructions() { 133b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao HashSet<SsaInsn> deletedInsns = new HashSet<SsaInsn>(); 134b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao 135b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao ssaMeth.computeReachability(); 136b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao 137b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao for (SsaBasicBlock block : ssaMeth.getBlocks()) { 138b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao if (block.isReachable()) continue; 139b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao 140b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao // Prune instructions from unreachable blocks 141b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao for (int i = 0; i < block.getInsns().size(); i++) { 142b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao SsaInsn insn = block.getInsns().get(i); 143b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao RegisterSpecList sources = insn.getSources(); 144b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao int sourcesSize = sources.size(); 145b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao 146b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao // Delete this instruction completely if it has sources 147b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao if (sourcesSize != 0) { 148b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao deletedInsns.add(insn); 149b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao } 150b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao 151b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao // Delete this instruction from all usage lists. 152b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao for (int j = 0; j < sourcesSize; j++) { 153b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao RegisterSpec source = sources.get(j); 154b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao useList[source.getReg()].remove(insn); 155b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao } 156b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao 157b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao // Remove this instruction result from the sources of any phis 158b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao RegisterSpec result = insn.getResult(); 159b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao if (result == null) continue; 160b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao for (SsaInsn use : useList[result.getReg()]) { 161b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao if (use instanceof PhiInsn) { 162b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao PhiInsn phiUse = (PhiInsn) use; 163b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao phiUse.removePhiRegister(result); 164b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao } 165b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao } 166b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao } 167b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao } 168b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao 169b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao ssaMeth.deleteInsns(deletedInsns); 170b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao } 171b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao 172b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao /** 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns true if the only uses of this register form a circle of 17499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * operations with no side effects. 175de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param regV register to examine 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param set a set of registers that we've already determined 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * are only used as sources in operations with no side effect or null 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * if this is the first recursion 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if usage is circular without side effect 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean isCircularNoSideEffect(int regV, BitSet set) { 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if ((set != null) && set.get(regV)) { 184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 18799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (SsaInsn use : useList[regV]) { 188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (hasSideEffect(use)) { 189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 190f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (set == null) { 194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project set = new BitSet(regCount); 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // This register is only used in operations that have no side effect. 198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project set.set(regV); 199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 20041aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (SsaInsn use : useList[regV]) { 201f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec result = use.getResult(); 202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (result == null 204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project || !isCircularNoSideEffect(result.getReg(), set)) { 205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 208f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 211f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns true if this insn has a side-effect. Returns true 214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * if the insn is null for reasons stated in the code block. 21599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * 21699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code null-ok;} instruction in question 217f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if it has a side-effect 218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 219f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static boolean hasSideEffect(SsaInsn insn) { 220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn == null) { 22199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /* While false would seem to make more sense here, true 22299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * prevents us from adding this back to a worklist unnecessarally. 223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 224f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 225f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 227de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro return insn.hasSideEffect(); 228f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 229f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 230f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 231f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * A callback class used to build up the initial worklist of 232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers defined by an instruction with no side effect. 233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 23499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project static private class NoSideEffectVisitor implements SsaInsn.Visitor { 235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet noSideEffectRegs; 236f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Passes in data structures that will be filled out after 239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * ssaMeth.forEachInsn() is called with this instance. 240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 241f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param noSideEffectRegs to-build bitset of regs that are 242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * results of regs with no side effects 243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 24499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project public NoSideEffectVisitor(BitSet noSideEffectRegs) { 245f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.noSideEffectRegs = noSideEffectRegs; 246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitMoveInsn (NormalSsaInsn insn) { 25099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // If we're tracking local vars, some moves have side effects. 251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!hasSideEffect(insn)) { 252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project noSideEffectRegs.set(insn.getResult().getReg()); 253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 255f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 257f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitPhiInsn (PhiInsn phi) { 25899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // If we're tracking local vars, then some phis have side effects. 259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!hasSideEffect(phi)) { 260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project noSideEffectRegs.set(phi.getResult().getReg()); 261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 262f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 263f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 264f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 265f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitNonMoveInsn (NormalSsaInsn insn) { 266f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec result = insn.getResult(); 267f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!hasSideEffect(insn) && result != null) { 268f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project noSideEffectRegs.set(result.getReg()); 269f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 270f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 273