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