1/*
2 * Copyright (C) 2008 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.LocalItem;
20import com.android.dx.rop.code.PlainCstInsn;
21import com.android.dx.rop.code.PlainInsn;
22import com.android.dx.rop.code.RegOps;
23import com.android.dx.rop.code.RegisterSpec;
24import com.android.dx.rop.code.RegisterSpecList;
25import com.android.dx.rop.code.Rop;
26import com.android.dx.rop.code.Rops;
27import com.android.dx.rop.code.SourcePosition;
28import com.android.dx.rop.code.ThrowingCstInsn;
29import com.android.dx.rop.cst.Constant;
30import com.android.dx.rop.cst.CstString;
31import com.android.dx.rop.cst.TypedConstant;
32import com.android.dx.rop.type.StdTypeList;
33import com.android.dx.rop.type.TypeBearer;
34import java.util.ArrayList;
35import java.util.Collections;
36import java.util.Comparator;
37import java.util.HashMap;
38import java.util.HashSet;
39import java.util.Map;
40
41/**
42 * Collects constants that are used more than once at the top of the
43 * method block. This increases register usage by about 5% but decreases
44 * insn size by about 3%.
45 */
46public class ConstCollector {
47    /** Maximum constants to collect per method. Puts cap on reg use */
48    private static final int MAX_COLLECTED_CONSTANTS = 5;
49
50    /**
51     * Also collect string consts, although they can throw exceptions.
52     * This is off now because it just doesn't seem to gain a whole lot.
53     * TODO if you turn this on, you must change SsaInsn.hasSideEffect()
54     * to return false for const-string insns whose exceptions are not
55     * caught in the current method.
56     */
57    private static boolean COLLECT_STRINGS = false;
58
59    /**
60     * If true, allow one local var to be involved with a collected const.
61     * Turned off because it mostly just inserts more moves.
62     */
63    private static boolean COLLECT_ONE_LOCAL = false;
64
65    /** method we're processing */
66    private final SsaMethod ssaMeth;
67
68    /**
69     * Processes a method.
70     *
71     * @param ssaMethod {@code non-null;} method to process
72     */
73    public static void process(SsaMethod ssaMethod) {
74        ConstCollector cc = new ConstCollector(ssaMethod);
75        cc.run();
76    }
77
78    /**
79     * Constructs an instance.
80     *
81     * @param ssaMethod {@code non-null;} method to process
82     */
83    private ConstCollector(SsaMethod ssaMethod) {
84        this.ssaMeth = ssaMethod;
85    }
86
87    /**
88     * Applies the optimization.
89     */
90    private void run() {
91        int regSz = ssaMeth.getRegCount();
92
93        ArrayList<TypedConstant> constantList
94                = getConstsSortedByCountUse();
95
96        int toCollect = Math.min(constantList.size(), MAX_COLLECTED_CONSTANTS);
97
98        SsaBasicBlock start = ssaMeth.getEntryBlock();
99
100        // Constant to new register containing the constant
101        HashMap<TypedConstant, RegisterSpec> newRegs
102                = new HashMap<TypedConstant, RegisterSpec> (toCollect);
103
104        for (int i = 0; i < toCollect; i++) {
105            TypedConstant cst = constantList.get(i);
106            RegisterSpec result
107                    = RegisterSpec.make(ssaMeth.makeNewSsaReg(), cst);
108
109            Rop constRop = Rops.opConst(cst);
110
111            if (constRop.getBranchingness() == Rop.BRANCH_NONE) {
112                start.addInsnToHead(
113                        new PlainCstInsn(Rops.opConst(cst),
114                                SourcePosition.NO_INFO, result,
115                                RegisterSpecList.EMPTY, cst));
116            } else {
117                // We need two new basic blocks along with the new insn
118                SsaBasicBlock entryBlock = ssaMeth.getEntryBlock();
119                SsaBasicBlock successorBlock
120                        = entryBlock.getPrimarySuccessor();
121
122                // Insert a block containing the const insn.
123                SsaBasicBlock constBlock
124                        = entryBlock.insertNewSuccessor(successorBlock);
125
126                constBlock.replaceLastInsn(
127                        new ThrowingCstInsn(constRop, SourcePosition.NO_INFO,
128                                RegisterSpecList.EMPTY,
129                                StdTypeList.EMPTY, cst));
130
131                // Insert a block containing the move-result-pseudo insn.
132
133                SsaBasicBlock resultBlock
134                        = constBlock.insertNewSuccessor(successorBlock);
135                PlainInsn insn
136                    = new PlainInsn(
137                            Rops.opMoveResultPseudo(result.getTypeBearer()),
138                            SourcePosition.NO_INFO,
139                            result, RegisterSpecList.EMPTY);
140
141                resultBlock.addInsnToHead(insn);
142            }
143
144            newRegs.put(cst, result);
145        }
146
147        updateConstUses(newRegs, regSz);
148    }
149
150    /**
151     * Gets all of the collectable constant values used in this method,
152     * sorted by most used first. Skips non-collectable consts, such as
153     * non-string object constants
154     *
155     * @return {@code non-null;} list of constants in most-to-least used order
156     */
157    private ArrayList<TypedConstant> getConstsSortedByCountUse() {
158        int regSz = ssaMeth.getRegCount();
159
160        final HashMap<TypedConstant, Integer> countUses
161                = new HashMap<TypedConstant, Integer>();
162
163        /*
164         * Each collected constant can be used by just one local
165         * (used only if COLLECT_ONE_LOCAL is true).
166         */
167        final HashSet<TypedConstant> usedByLocal
168                = new HashSet<TypedConstant>();
169
170        // Count how many times each const value is used.
171        for (int i = 0; i < regSz; i++) {
172            SsaInsn insn = ssaMeth.getDefinitionForRegister(i);
173
174            if (insn == null || insn.getOpcode() == null) continue;
175
176            RegisterSpec result = insn.getResult();
177            TypeBearer typeBearer = result.getTypeBearer();
178
179            if (!typeBearer.isConstant()) continue;
180
181            TypedConstant cst = (TypedConstant) typeBearer;
182
183            // Find defining instruction for move-result-pseudo instructions
184            if (insn.getOpcode().getOpcode() == RegOps.MOVE_RESULT_PSEUDO) {
185                int pred = insn.getBlock().getPredecessors().nextSetBit(0);
186                ArrayList<SsaInsn> predInsns;
187                predInsns = ssaMeth.getBlocks().get(pred).getInsns();
188                insn = predInsns.get(predInsns.size()-1);
189            }
190
191            if (insn.canThrow()) {
192                /*
193                 * Don't move anything other than strings -- the risk
194                 * of changing where an exception is thrown is too high.
195                 */
196                if (!(cst instanceof CstString) || !COLLECT_STRINGS) {
197                    continue;
198                }
199                /*
200                 * We can't move any throwable const whose throw will be
201                 * caught, so don't count them.
202                 */
203                if (insn.getBlock().getSuccessors().cardinality() > 1) {
204                    continue;
205                }
206            }
207
208            /*
209             * TODO: Might be nice to try and figure out which local
210             * wins most when collected.
211             */
212            if (ssaMeth.isRegALocal(result)) {
213                if (!COLLECT_ONE_LOCAL) {
214                    continue;
215                } else {
216                    if (usedByLocal.contains(cst)) {
217                        // Count one local usage only.
218                        continue;
219                    } else {
220                        usedByLocal.add(cst);
221                    }
222                }
223            }
224
225            Integer has = countUses.get(cst);
226            if (has == null) {
227                countUses.put(cst, 1);
228            } else {
229                countUses.put(cst, has + 1);
230            }
231        }
232
233        // Collect constants that have been reused.
234        ArrayList<TypedConstant> constantList = new ArrayList<TypedConstant>();
235        for (Map.Entry<TypedConstant, Integer> entry : countUses.entrySet()) {
236            if (entry.getValue() > 1) {
237                constantList.add(entry.getKey());
238            }
239        }
240
241        // Sort by use, with most used at the beginning of the list.
242        Collections.sort(constantList, new Comparator<Constant>() {
243            public int compare(Constant a, Constant b) {
244                int ret;
245                ret = countUses.get(b) - countUses.get(a);
246
247                if (ret == 0) {
248                    /*
249                     * Provide sorting determinisim for constants with same
250                     * usage count.
251                     */
252                    ret = a.compareTo(b);
253                }
254
255                return ret;
256            }
257
258            @Override
259            public boolean equals (Object obj) {
260                return obj == this;
261            }
262        });
263
264        return constantList;
265    }
266
267    /**
268     * Inserts mark-locals if necessary when changing a register. If
269     * the definition of {@code origReg} is associated with a local
270     * variable, then insert a mark-local for {@code newReg} just below
271     * it. We expect the definition of  {@code origReg} to ultimately
272     * be removed by the dead code eliminator
273     *
274     * @param origReg {@code non-null;} original register
275     * @param newReg {@code non-null;} new register that will replace
276     * {@code origReg}
277     */
278    private void fixLocalAssignment(RegisterSpec origReg,
279            RegisterSpec newReg) {
280        for (SsaInsn use : ssaMeth.getUseListForRegister(origReg.getReg())) {
281            RegisterSpec localAssignment = use.getLocalAssignment();
282            if (localAssignment == null) {
283                continue;
284            }
285
286            if (use.getResult() == null) {
287                /*
288                 * This is a mark-local. it will be updated when all uses
289                 * are updated.
290                 */
291                continue;
292            }
293
294            LocalItem local = localAssignment.getLocalItem();
295
296            // Un-associate original use.
297            use.setResultLocal(null);
298
299            // Now add a mark-local to the new reg immediately after.
300            newReg = newReg.withLocalItem(local);
301
302            SsaInsn newInsn
303                    = SsaInsn.makeFromRop(
304                        new PlainInsn(Rops.opMarkLocal(newReg),
305                        SourcePosition.NO_INFO, null,
306                                RegisterSpecList.make(newReg)),
307                    use.getBlock());
308
309            ArrayList<SsaInsn> insns = use.getBlock().getInsns();
310
311            insns.add(insns.indexOf(use) + 1, newInsn);
312        }
313    }
314
315    /**
316     * Updates all uses of various consts to use the values in the newly
317     * assigned registers.
318     *
319     * @param newRegs {@code non-null;} mapping between constant and new reg
320     * @param origRegCount {@code >=0;} original SSA reg count, not including
321     * newly added constant regs
322     */
323    private void updateConstUses(HashMap<TypedConstant, RegisterSpec> newRegs,
324            int origRegCount) {
325
326        /*
327         * set of constants associated with a local variable; used
328         * only if COLLECT_ONE_LOCAL is true.
329         */
330        final HashSet<TypedConstant> usedByLocal
331                = new HashSet<TypedConstant>();
332
333        final ArrayList<SsaInsn>[] useList = ssaMeth.getUseListCopy();
334
335        for (int i = 0; i < origRegCount; i++) {
336            SsaInsn insn = ssaMeth.getDefinitionForRegister(i);
337
338            if (insn == null) {
339                continue;
340            }
341
342            final RegisterSpec origReg = insn.getResult();
343            TypeBearer typeBearer = insn.getResult().getTypeBearer();
344
345            if (!typeBearer.isConstant()) continue;
346
347            TypedConstant cst = (TypedConstant) typeBearer;
348            final RegisterSpec newReg = newRegs.get(cst);
349
350            if (newReg == null) {
351                continue;
352            }
353
354            if (ssaMeth.isRegALocal(origReg)) {
355                if (!COLLECT_ONE_LOCAL) {
356                    continue;
357                } else {
358                    /*
359                     * TODO: If the same local gets the same cst
360                     * multiple times, it would be nice to reuse the
361                     * register.
362                     */
363                    if (usedByLocal.contains(cst)) {
364                        continue;
365                    } else {
366                        usedByLocal.add(cst);
367                        fixLocalAssignment(origReg, newRegs.get(cst));
368                    }
369                }
370            }
371
372            // maps an original const register to the new collected register
373            RegisterMapper mapper = new RegisterMapper() {
374                @Override
375                public int getNewRegisterCount() {
376                    return ssaMeth.getRegCount();
377                }
378
379                @Override
380                public RegisterSpec map(RegisterSpec registerSpec) {
381                    if (registerSpec.getReg() == origReg.getReg()) {
382                        return newReg.withLocalItem(
383                                registerSpec.getLocalItem());
384                    }
385
386                    return registerSpec;
387                }
388            };
389
390            for (SsaInsn use : useList[origReg.getReg()]) {
391                if (use.canThrow()
392                        && use.getBlock().getSuccessors().cardinality() > 1) {
393                    continue;
394                }
395                use.mapSourceRegisters(mapper);
396            }
397        }
398    }
399}
400