Optimizer.java revision e31ed7e916d212840dd5639afa01938bea58b2b8 
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
17package com.android.dx.ssa;
18
19import com.android.dx.rop.code.RopMethod;
20import com.android.dx.rop.code.TranslationAdvice;
21import com.android.dx.ssa.back.LivenessAnalyzer;
22import com.android.dx.ssa.back.SsaToRop;
23
24import 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 */
30public 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        }
162
163        if (steps.contains(OptionalStep.LITERAL_UPGRADE)) {
164            LiteralOpUpgrader.process(ssaMeth);
165            DeadCodeRemover.process(ssaMeth);
166            needsDeadCodeRemover = false;
167        }
168
169        /*
170         * ESCAPE_ANALYSIS impacts debuggability, so left off by default
171         */
172        steps.remove(OptionalStep.ESCAPE_ANALYSIS);
173        if (steps.contains(OptionalStep.ESCAPE_ANALYSIS)) {
174            EscapeAnalysis.process(ssaMeth);
175            DeadCodeRemover.process(ssaMeth);
176            needsDeadCodeRemover = false;
177        }
178
179        if (steps.contains(OptionalStep.CONST_COLLECTOR)) {
180            ConstCollector.process(ssaMeth);
181            DeadCodeRemover.process(ssaMeth);
182            needsDeadCodeRemover = false;
183        }
184
185        // dead code remover must be run before phi type resolver
186        if (needsDeadCodeRemover) {
187            DeadCodeRemover.process(ssaMeth);
188        }
189
190        PhiTypeResolver.process(ssaMeth);
191    }
192
193    public static SsaMethod debugEdgeSplit(RopMethod rmeth, int paramWidth,
194            boolean isStatic, boolean inPreserveLocals,
195            TranslationAdvice inAdvice) {
196
197        preserveLocals = inPreserveLocals;
198        advice = inAdvice;
199
200        return SsaConverter.testEdgeSplit(rmeth, paramWidth, isStatic);
201    }
202
203    public static SsaMethod debugPhiPlacement(RopMethod rmeth, int paramWidth,
204            boolean isStatic, boolean inPreserveLocals,
205            TranslationAdvice inAdvice) {
206
207        preserveLocals = inPreserveLocals;
208        advice = inAdvice;
209
210        return SsaConverter.testPhiPlacement(rmeth, paramWidth, isStatic);
211    }
212
213    public static SsaMethod debugRenaming(RopMethod rmeth, int paramWidth,
214            boolean isStatic, boolean inPreserveLocals,
215            TranslationAdvice inAdvice) {
216
217        preserveLocals = inPreserveLocals;
218        advice = inAdvice;
219
220        return SsaConverter.convertToSsaMethod(rmeth, paramWidth, isStatic);
221    }
222
223    public static SsaMethod debugDeadCodeRemover(RopMethod rmeth,
224            int paramWidth, boolean isStatic, boolean inPreserveLocals,
225            TranslationAdvice inAdvice) {
226
227        SsaMethod ssaMeth;
228
229        preserveLocals = inPreserveLocals;
230        advice = inAdvice;
231
232        ssaMeth = SsaConverter.convertToSsaMethod(rmeth, paramWidth, isStatic);
233        DeadCodeRemover.process(ssaMeth);
234
235        return ssaMeth;
236    }
237
238    public static SsaMethod debugNoRegisterAllocation(RopMethod rmeth,
239            int paramWidth, boolean isStatic, boolean inPreserveLocals,
240            TranslationAdvice inAdvice, EnumSet<OptionalStep> steps) {
241
242        SsaMethod ssaMeth;
243
244        preserveLocals = inPreserveLocals;
245        advice = inAdvice;
246
247        ssaMeth = SsaConverter.convertToSsaMethod(rmeth, paramWidth, isStatic);
248
249        runSsaFormSteps(ssaMeth, steps);
250
251        LivenessAnalyzer.constructInterferenceGraph(ssaMeth);
252
253        return ssaMeth;
254    }
255}
256