VariableOptimizer.java revision db267bc191f906f55eaef21a27110cce2ec57fdf 
1/*
2 * ProGuard -- shrinking, optimization, obfuscation, and preverification
3 *             of Java bytecode.
4 *
5 * Copyright (c) 2002-2009 Eric Lafortune (eric@graphics.cornell.edu)
6 *
7 * This program is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU General Public License as published by the Free
9 * Software Foundation; either version 2 of the License, or (at your option)
10 * any later version.
11 *
12 * This program is distributed in the hope that it will be useful, but WITHOUT
13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
15 * more details.
16 *
17 * You should have received a copy of the GNU General Public License along
18 * with this program; if not, write to the Free Software Foundation, Inc.,
19 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 */
21package proguard.optimize.evaluation;
22
23import proguard.classfile.*;
24import proguard.classfile.visitor.MemberVisitor;
25import proguard.classfile.attribute.*;
26import proguard.classfile.attribute.visitor.AttributeVisitor;
27import proguard.classfile.editor.VariableRemapper;
28import proguard.classfile.util.*;
29
30/**
31 * This AttributeVisitor optimizes variable allocation based on their the liveness,
32 * in the code attributes that it visits.
33 *
34 * @author Eric Lafortune
35 */
36public class VariableOptimizer
37extends      SimplifiedVisitor
38implements   AttributeVisitor
39{
40    //*
41    private static final boolean DEBUG = false;
42    /*/
43    private static       boolean DEBUG = true;
44    //*/
45
46    private static final int MAX_VARIABLES_SIZE = 64;
47
48
49    private final boolean       reuseThis;
50    private final MemberVisitor extraVariableMemberVisitor;
51
52    private final LivenessAnalyzer livenessAnalyzer = new LivenessAnalyzer();
53    private final VariableRemapper variableRemapper = new VariableRemapper();
54
55    private int[] variableMap = new int[ClassConstants.TYPICAL_VARIABLES_SIZE];
56
57
58    /**
59     * Creates a new VariableOptimizer.
60     * @param reuseThis specifies whether the 'this' variable can be reused.
61     *                  Many JVMs for JME and IBM's JVMs for JSE can't handle
62     *                  such reuse.
63     */
64    public VariableOptimizer(boolean reuseThis)
65    {
66        this(reuseThis, null);
67    }
68
69
70    /**
71     * Creates a new VariableOptimizer with an extra visitor.
72     * @param reuseThis                  specifies whether the 'this' variable
73     *                                   can be reused. Many JVMs for JME and
74     *                                   IBM's JVMs for JSE can't handle such
75     *                                   reuse.
76     * @param extraVariableMemberVisitor an optional extra visitor for all
77     *                                   removed variables.
78     */
79    public VariableOptimizer(boolean       reuseThis,
80                             MemberVisitor extraVariableMemberVisitor)
81    {
82        this.reuseThis                  = reuseThis;
83        this.extraVariableMemberVisitor = extraVariableMemberVisitor;
84    }
85
86
87    // Implementations for AttributeVisitor.
88
89    public void visitAnyAttribute(Clazz clazz, Attribute attribute) {}
90
91
92    public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute)
93    {
94//        DEBUG =
95//            clazz.getName().equals("abc/Def") &&
96//            method.getName(clazz).equals("abc");
97
98        // Initialize the global arrays.
99        initializeArrays(codeAttribute);
100
101        // Analyze the liveness of the variables in the code.
102        livenessAnalyzer.visitCodeAttribute(clazz, method, codeAttribute);
103
104        int startIndex =
105            (method.getAccessFlags() & ClassConstants.INTERNAL_ACC_STATIC) != 0 ||
106            reuseThis ? 0 : 1;
107
108        int parameterSize =
109            ClassUtil.internalMethodParameterSize(method.getDescriptor(clazz),
110                                                  method.getAccessFlags());
111
112        int variableSize = codeAttribute.u2maxLocals;
113        int codeLength   = codeAttribute.u4codeLength;
114
115        boolean remapping = false;
116
117        // Loop over all variables.
118        for (int oldIndex = 0; oldIndex < variableSize; oldIndex++)
119        {
120            // By default, the variable will be mapped onto itself.
121            variableMap[oldIndex] = oldIndex;
122
123            // Only try remapping the variable if it's not a parameter.
124            if (oldIndex >= parameterSize &&
125                oldIndex < MAX_VARIABLES_SIZE)
126            {
127                // Try to remap the variable to a variable with a smaller index.
128                for (int newIndex = startIndex; newIndex < oldIndex; newIndex++)
129                {
130                    if (areNonOverlapping(oldIndex, newIndex, codeLength))
131                    {
132                        variableMap[oldIndex] = newIndex;
133
134                        updateLiveness(oldIndex, newIndex, codeLength);
135
136                        remapping = true;
137
138                        // This variable has been remapped. Go to the next one.
139                        break;
140                    }
141                }
142            }
143        }
144
145        // Remap the variables.
146        if (remapping)
147        {
148            if (DEBUG)
149            {
150                System.out.println("Remapping variables:");
151                System.out.println("  Class "+ ClassUtil.externalClassName(clazz.getName()));
152                System.out.println("  Method "+ClassUtil.externalFullMethodDescription(clazz.getName(),
153                                                                                       0,
154                                                                                       method.getName(clazz),
155                                                                                       method.getDescriptor(clazz)));
156                for (int index = 0; index < variableSize; index++)
157                {
158                    System.out.println("  ["+index+"] -> ["+variableMap[index]+"]");
159                }
160            }
161
162            variableRemapper.setVariableMap(variableMap);
163            variableRemapper.visitCodeAttribute(clazz, method, codeAttribute);
164
165            // Visit the method, if required.
166            if (extraVariableMemberVisitor != null)
167            {
168                method.accept(clazz, extraVariableMemberVisitor);
169            }
170        }
171    }
172
173
174    // Small utility methods.
175
176    /**
177     * Initializes the global arrays.
178     */
179    private void initializeArrays(CodeAttribute codeAttribute)
180    {
181        int codeLength = codeAttribute.u4codeLength;
182
183        // Create new arrays for storing information at each instruction offset.
184        if (variableMap.length < codeLength)
185        {
186            variableMap = new int[codeLength];
187        }
188    }
189
190
191    /**
192     * Returns whether the given variables are never alive at the same time.
193     */
194    private boolean areNonOverlapping(int variableIndex1,
195                                      int variableIndex2,
196                                      int codeLength)
197    {
198        // Loop over all instructions.
199        for (int offset = 0; offset < codeLength; offset++)
200        {
201            if ((livenessAnalyzer.isAliveBefore(offset, variableIndex1) &&
202                 livenessAnalyzer.isAliveBefore(offset, variableIndex2)) ||
203
204                (livenessAnalyzer.isAliveAfter(offset, variableIndex1) &&
205                 livenessAnalyzer.isAliveAfter(offset, variableIndex2)) ||
206
207                // For now, exclude Category 2 variables.
208                livenessAnalyzer.isCategory2(offset, variableIndex1))
209            {
210                return false;
211            }
212        }
213
214        return true;
215    }
216
217
218    /**
219     * Updates the liveness resulting from mapping the given old variable on
220     * the given new variable.
221     */
222    private void updateLiveness(int oldVariableIndex,
223                                int newVariableIndex,
224                                int codeLength)
225    {
226        // Loop over all instructions.
227        for (int offset = 0; offset < codeLength; offset++)
228        {
229            // Update the liveness before the instruction.
230            if (livenessAnalyzer.isAliveBefore(offset, oldVariableIndex))
231            {
232                livenessAnalyzer.setAliveBefore(offset, oldVariableIndex, false);
233                livenessAnalyzer.setAliveBefore(offset, newVariableIndex, true);
234            }
235
236            // Update the liveness after the instruction.
237            if (livenessAnalyzer.isAliveAfter(offset, oldVariableIndex))
238            {
239                livenessAnalyzer.setAliveAfter(offset, oldVariableIndex, false);
240                livenessAnalyzer.setAliveAfter(offset, newVariableIndex, true);
241            }
242        }
243    }
244}
245