• Home
  • History
  • Annotate
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
17 package com.android.dx.ssa;
18 
19 import com.android.dx.rop.code.LocalItem;
20 import com.android.dx.rop.code.PlainCstInsn;
21 import com.android.dx.rop.code.PlainInsn;
22 import com.android.dx.rop.code.RegOps;
23 import com.android.dx.rop.code.RegisterSpec;
24 import com.android.dx.rop.code.RegisterSpecList;
25 import com.android.dx.rop.code.Rop;
26 import com.android.dx.rop.code.Rops;
27 import com.android.dx.rop.code.SourcePosition;
28 import com.android.dx.rop.code.ThrowingCstInsn;
29 import com.android.dx.rop.cst.Constant;
30 import com.android.dx.rop.cst.CstString;
31 import com.android.dx.rop.cst.TypedConstant;
32 import com.android.dx.rop.type.StdTypeList;
33 import com.android.dx.rop.type.TypeBearer;
34 import java.util.ArrayList;
35 import java.util.Collections;
36 import java.util.Comparator;
37 import java.util.HashMap;
38 import java.util.HashSet;
39 import 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  */
46 public 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 final 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 final 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      */
process(SsaMethod ssaMethod)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      */
ConstCollector(SsaMethod ssaMethod)83     private ConstCollector(SsaMethod ssaMethod) {
84         this.ssaMeth = ssaMethod;
85     }
86 
87     /**
88      * Applies the optimization.
89      */
run()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      */
getConstsSortedByCountUse()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             @Override
244             public int compare(Constant a, Constant b) {
245                 int ret;
246                 ret = countUses.get(b) - countUses.get(a);
247 
248                 if (ret == 0) {
249                     /*
250                      * Provide sorting determinisim for constants with same
251                      * usage count.
252                      */
253                     ret = a.compareTo(b);
254                 }
255 
256                 return ret;
257             }
258 
259             @Override
260             public boolean equals (Object obj) {
261                 return obj == this;
262             }
263         });
264 
265         return constantList;
266     }
267 
268     /**
269      * Inserts mark-locals if necessary when changing a register. If
270      * the definition of {@code origReg} is associated with a local
271      * variable, then insert a mark-local for {@code newReg} just below
272      * it. We expect the definition of  {@code origReg} to ultimately
273      * be removed by the dead code eliminator
274      *
275      * @param origReg {@code non-null;} original register
276      * @param newReg {@code non-null;} new register that will replace
277      * {@code origReg}
278      */
fixLocalAssignment(RegisterSpec origReg, RegisterSpec newReg)279     private void fixLocalAssignment(RegisterSpec origReg,
280             RegisterSpec newReg) {
281         for (SsaInsn use : ssaMeth.getUseListForRegister(origReg.getReg())) {
282             RegisterSpec localAssignment = use.getLocalAssignment();
283             if (localAssignment == null) {
284                 continue;
285             }
286 
287             if (use.getResult() == null) {
288                 /*
289                  * This is a mark-local. it will be updated when all uses
290                  * are updated.
291                  */
292                 continue;
293             }
294 
295             LocalItem local = localAssignment.getLocalItem();
296 
297             // Un-associate original use.
298             use.setResultLocal(null);
299 
300             // Now add a mark-local to the new reg immediately after.
301             newReg = newReg.withLocalItem(local);
302 
303             SsaInsn newInsn
304                     = SsaInsn.makeFromRop(
305                         new PlainInsn(Rops.opMarkLocal(newReg),
306                         SourcePosition.NO_INFO, null,
307                                 RegisterSpecList.make(newReg)),
308                     use.getBlock());
309 
310             ArrayList<SsaInsn> insns = use.getBlock().getInsns();
311 
312             insns.add(insns.indexOf(use) + 1, newInsn);
313         }
314     }
315 
316     /**
317      * Updates all uses of various consts to use the values in the newly
318      * assigned registers.
319      *
320      * @param newRegs {@code non-null;} mapping between constant and new reg
321      * @param origRegCount {@code >=0;} original SSA reg count, not including
322      * newly added constant regs
323      */
updateConstUses(HashMap<TypedConstant, RegisterSpec> newRegs, int origRegCount)324     private void updateConstUses(HashMap<TypedConstant, RegisterSpec> newRegs,
325             int origRegCount) {
326 
327         /*
328          * set of constants associated with a local variable; used
329          * only if COLLECT_ONE_LOCAL is true.
330          */
331         final HashSet<TypedConstant> usedByLocal
332                 = new HashSet<TypedConstant>();
333 
334         final ArrayList<SsaInsn>[] useList = ssaMeth.getUseListCopy();
335 
336         for (int i = 0; i < origRegCount; i++) {
337             SsaInsn insn = ssaMeth.getDefinitionForRegister(i);
338 
339             if (insn == null) {
340                 continue;
341             }
342 
343             final RegisterSpec origReg = insn.getResult();
344             TypeBearer typeBearer = insn.getResult().getTypeBearer();
345 
346             if (!typeBearer.isConstant()) continue;
347 
348             TypedConstant cst = (TypedConstant) typeBearer;
349             final RegisterSpec newReg = newRegs.get(cst);
350 
351             if (newReg == null) {
352                 continue;
353             }
354 
355             if (ssaMeth.isRegALocal(origReg)) {
356                 if (!COLLECT_ONE_LOCAL) {
357                     continue;
358                 } else {
359                     /*
360                      * TODO: If the same local gets the same cst
361                      * multiple times, it would be nice to reuse the
362                      * register.
363                      */
364                     if (usedByLocal.contains(cst)) {
365                         continue;
366                     } else {
367                         usedByLocal.add(cst);
368                         fixLocalAssignment(origReg, newRegs.get(cst));
369                     }
370                 }
371             }
372 
373             // maps an original const register to the new collected register
374             RegisterMapper mapper = new RegisterMapper() {
375                 @Override
376                 public int getNewRegisterCount() {
377                     return ssaMeth.getRegCount();
378                 }
379 
380                 @Override
381                 public RegisterSpec map(RegisterSpec registerSpec) {
382                     if (registerSpec.getReg() == origReg.getReg()) {
383                         return newReg.withLocalItem(
384                                 registerSpec.getLocalItem());
385                     }
386 
387                     return registerSpec;
388                 }
389             };
390 
391             for (SsaInsn use : useList[origReg.getReg()]) {
392                 if (use.canThrow()
393                         && use.getBlock().getSuccessors().cardinality() > 1) {
394                     continue;
395                 }
396                 use.mapSourceRegisters(mapper);
397             }
398         }
399     }
400 }
401