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