Optimizer.java revision 579d7739c53a2707ad711a2d2cae46d7d782f061 
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            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