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