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