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