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 17 package com.android.dx.ssa; 18 19 import com.android.dx.rop.code.RopMethod; 20 import com.android.dx.rop.code.TranslationAdvice; 21 import com.android.dx.ssa.back.LivenessAnalyzer; 22 import com.android.dx.ssa.back.SsaToRop; 23 24 import java.util.EnumSet; 25 26 /** 27 * Runs a method through the SSA form conversion, any optimization algorithms, 28 * and returns it to rop form. 29 */ 30 public class Optimizer { 31 private static boolean preserveLocals = true; 32 33 private static TranslationAdvice advice; 34 35 /** optional optimizer steps */ 36 public enum OptionalStep { 37 MOVE_PARAM_COMBINER, SCCP, LITERAL_UPGRADE, CONST_COLLECTOR, 38 ESCAPE_ANALYSIS 39 } 40 41 /** 42 * @return true if local variable information should be preserved, even 43 * at code size/register size cost 44 */ 45 public static boolean getPreserveLocals() { 46 return preserveLocals; 47 } 48 49 /** 50 * @return {@code non-null;} translation advice 51 */ 52 public static TranslationAdvice getAdvice() { 53 return advice; 54 } 55 56 /** 57 * Runs optimization algorthims over this method, and returns a new 58 * instance of RopMethod with the changes. 59 * 60 * @param rmeth method to process 61 * @param paramWidth the total width, in register-units, of this method's 62 * parameters 63 * @param isStatic true if this method has no 'this' pointer argument. 64 * @param inPreserveLocals true if local variable info should be preserved, 65 * at the cost of some registers and insns 66 * @param inAdvice {@code non-null;} translation advice 67 * @return optimized method 68 */ 69 public static RopMethod optimize(RopMethod rmeth, int paramWidth, 70 boolean isStatic, boolean inPreserveLocals, 71 TranslationAdvice inAdvice) { 72 73 return optimize(rmeth, paramWidth, isStatic, inPreserveLocals, inAdvice, 74 EnumSet.allOf(OptionalStep.class)); 75 } 76 77 /** 78 * Runs optimization algorthims over this method, and returns a new 79 * instance of RopMethod with the changes. 80 * 81 * @param rmeth method to process 82 * @param paramWidth the total width, in register-units, of this method's 83 * parameters 84 * @param isStatic true if this method has no 'this' pointer argument. 85 * @param inPreserveLocals true if local variable info should be preserved, 86 * at the cost of some registers and insns 87 * @param inAdvice {@code non-null;} translation advice 88 * @param steps set of optional optimization steps to run 89 * @return optimized method 90 */ 91 public static RopMethod optimize(RopMethod rmeth, int paramWidth, 92 boolean isStatic, boolean inPreserveLocals, 93 TranslationAdvice inAdvice, EnumSet<OptionalStep> steps) { 94 SsaMethod ssaMeth = null; 95 96 preserveLocals = inPreserveLocals; 97 advice = inAdvice; 98 99 ssaMeth = SsaConverter.convertToSsaMethod(rmeth, paramWidth, isStatic); 100 runSsaFormSteps(ssaMeth, steps); 101 102 RopMethod resultMeth = SsaToRop.convertToRopMethod(ssaMeth, false); 103 104 if (resultMeth.getBlocks().getRegCount() 105 > advice.getMaxOptimalRegisterCount()) { 106 // Try to see if we can squeeze it under the register count bar 107 resultMeth = optimizeMinimizeRegisters(rmeth, paramWidth, isStatic, 108 steps); 109 } 110 return resultMeth; 111 } 112 113 /** 114 * Runs the optimizer with a strategy to minimize the number of rop-form 115 * registers used by the end result. Dex bytecode does not have instruction 116 * forms that take register numbers larger than 15 for all instructions. 117 * If we've produced a method that uses more than 16 registers, try again 118 * with a different strategy to see if we can get under the bar. The end 119 * result will be much more efficient. 120 * 121 * @param rmeth method to process 122 * @param paramWidth the total width, in register-units, of this method's 123 * parameters 124 * @param isStatic true if this method has no 'this' pointer argument. 125 * @param steps set of optional optimization steps to run 126 * @return optimized method 127 */ 128 private static RopMethod optimizeMinimizeRegisters(RopMethod rmeth, 129 int paramWidth, boolean isStatic, 130 EnumSet<OptionalStep> steps) { 131 SsaMethod ssaMeth; 132 RopMethod resultMeth; 133 134 ssaMeth = SsaConverter.convertToSsaMethod( 135 rmeth, paramWidth, isStatic); 136 137 EnumSet<OptionalStep> newSteps = steps.clone(); 138 139 /* 140 * CONST_COLLECTOR trades insns for registers, which is not an 141 * appropriate strategy here. 142 */ 143 newSteps.remove(OptionalStep.CONST_COLLECTOR); 144 145 runSsaFormSteps(ssaMeth, newSteps); 146 147 resultMeth = SsaToRop.convertToRopMethod(ssaMeth, true); 148 return resultMeth; 149 } 150 151 private static void runSsaFormSteps(SsaMethod ssaMeth, 152 EnumSet<OptionalStep> steps) { 153 boolean needsDeadCodeRemover = true; 154 155 if (steps.contains(OptionalStep.MOVE_PARAM_COMBINER)) { 156 MoveParamCombiner.process(ssaMeth); 157 } 158 159 if (steps.contains(OptionalStep.SCCP)) { 160 SCCP.process(ssaMeth); 161 DeadCodeRemover.process(ssaMeth); 162 needsDeadCodeRemover = false; 163 } 164 165 if (steps.contains(OptionalStep.LITERAL_UPGRADE)) { 166 LiteralOpUpgrader.process(ssaMeth); 167 DeadCodeRemover.process(ssaMeth); 168 needsDeadCodeRemover = false; 169 } 170 171 /* 172 * ESCAPE_ANALYSIS impacts debuggability, so left off by default 173 */ 174 steps.remove(OptionalStep.ESCAPE_ANALYSIS); 175 if (steps.contains(OptionalStep.ESCAPE_ANALYSIS)) { 176 EscapeAnalysis.process(ssaMeth); 177 DeadCodeRemover.process(ssaMeth); 178 needsDeadCodeRemover = false; 179 } 180 181 if (steps.contains(OptionalStep.CONST_COLLECTOR)) { 182 ConstCollector.process(ssaMeth); 183 DeadCodeRemover.process(ssaMeth); 184 needsDeadCodeRemover = false; 185 } 186 187 // dead code remover must be run before phi type resolver 188 if (needsDeadCodeRemover) { 189 DeadCodeRemover.process(ssaMeth); 190 } 191 192 PhiTypeResolver.process(ssaMeth); 193 } 194 195 public static SsaMethod debugEdgeSplit(RopMethod rmeth, int paramWidth, 196 boolean isStatic, boolean inPreserveLocals, 197 TranslationAdvice inAdvice) { 198 199 preserveLocals = inPreserveLocals; 200 advice = inAdvice; 201 202 return SsaConverter.testEdgeSplit(rmeth, paramWidth, isStatic); 203 } 204 205 public static SsaMethod debugPhiPlacement(RopMethod rmeth, int paramWidth, 206 boolean isStatic, boolean inPreserveLocals, 207 TranslationAdvice inAdvice) { 208 209 preserveLocals = inPreserveLocals; 210 advice = inAdvice; 211 212 return SsaConverter.testPhiPlacement(rmeth, paramWidth, isStatic); 213 } 214 215 public static SsaMethod debugRenaming(RopMethod rmeth, int paramWidth, 216 boolean isStatic, boolean inPreserveLocals, 217 TranslationAdvice inAdvice) { 218 219 preserveLocals = inPreserveLocals; 220 advice = inAdvice; 221 222 return SsaConverter.convertToSsaMethod(rmeth, paramWidth, isStatic); 223 } 224 225 public static SsaMethod debugDeadCodeRemover(RopMethod rmeth, 226 int paramWidth, boolean isStatic, boolean inPreserveLocals, 227 TranslationAdvice inAdvice) { 228 229 SsaMethod ssaMeth; 230 231 preserveLocals = inPreserveLocals; 232 advice = inAdvice; 233 234 ssaMeth = SsaConverter.convertToSsaMethod(rmeth, paramWidth, isStatic); 235 DeadCodeRemover.process(ssaMeth); 236 237 return ssaMeth; 238 } 239 240 public static SsaMethod debugNoRegisterAllocation(RopMethod rmeth, 241 int paramWidth, boolean isStatic, boolean inPreserveLocals, 242 TranslationAdvice inAdvice, EnumSet<OptionalStep> steps) { 243 244 SsaMethod ssaMeth; 245 246 preserveLocals = inPreserveLocals; 247 advice = inAdvice; 248 249 ssaMeth = SsaConverter.convertToSsaMethod(rmeth, paramWidth, isStatic); 250 251 runSsaFormSteps(ssaMeth, steps); 252 253 LivenessAnalyzer.constructInterferenceGraph(ssaMeth); 254 255 return ssaMeth; 256 } 257 } 258
