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 */ 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
