KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > proguard > optimize > evaluation > LivenessAnalyzer


1 /*
2  * ProGuard -- shrinking, optimization, obfuscation, and preverification
3  * of Java bytecode.
4  *
5  * Copyright (c) 2002-2007 Eric Lafortune (eric@graphics.cornell.edu)
6  *
7  * This library 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 library 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 Lesser General Public License
15  * for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public License
18  * along with this library; if not, write to the Free Software Foundation,
19  * Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20  */
21 package proguard.optimize.evaluation;
22
23 import proguard.classfile.*;
24 import proguard.classfile.attribute.*;
25 import proguard.classfile.attribute.visitor.*;
26 import proguard.classfile.instruction.*;
27 import proguard.classfile.instruction.visitor.InstructionVisitor;
28 import proguard.classfile.util.*;
29 import proguard.evaluation.value.*;
30
31 /**
32  * This AttributeVisitor analyzes the liveness of the variables in the code
33  * attributes that it visits, based on partial evaluation.
34  *
35  * @author Eric Lafortune
36  */
37 public class LivenessAnalyzer
38 extends SimplifiedVisitor
39 implements AttributeVisitor,
40              InstructionVisitor,
41              ExceptionInfoVisitor
42 {
43     //*
44 private static final boolean DEBUG = false;
45     /*/
46     private static boolean DEBUG = true;
47     //*/
48
49     private static final int MAX_VARIABLES_SIZE = 64;
50
51     private PartialEvaluator partialEvaluator;
52
53     private long[] isAliveBefore = new long[ClassConstants.TYPICAL_CODE_LENGTH];
54     private long[] isAliveAfter = new long[ClassConstants.TYPICAL_CODE_LENGTH];
55     private long[] isCategory2 = new long[ClassConstants.TYPICAL_CODE_LENGTH];
56
57     // Fields acting as global temporary variables.
58 private boolean checkAgain;
59     private long alive;
60
61
62     /**
63      * Creates a new LivenessAnalyzer.
64      */
65     public LivenessAnalyzer()
66     {
67         this(new PartialEvaluator());
68     }
69
70
71     /**
72      * Creates a new LivenessAnalyzer that will use the given partial evaluator.
73      * It will run this evaluator on every code attribute that it visits.
74      */
75     public LivenessAnalyzer(PartialEvaluator partialEvaluator)
76     {
77         this.partialEvaluator = partialEvaluator;
78     }
79
80
81     /**
82      * Returns whether the specified variable is alive before the instruction
83      * at the given offset.
84      */
85     public boolean isAliveBefore(int instructionOffset, int variableIndex)
86     {
87         return variableIndex >= MAX_VARIABLES_SIZE ||
88                (isAliveBefore[instructionOffset] & (1L << variableIndex)) != 0;
89     }
90
91
92     /**
93      * Sets whether the specified variable is alive before the instruction
94      * at the given offset.
95      */
96     public void setAliveBefore(int instructionOffset, int variableIndex, boolean alive)
97     {
98         if (variableIndex < MAX_VARIABLES_SIZE)
99         {
100             if (alive)
101             {
102                 isAliveBefore[instructionOffset] |= 1L << variableIndex;
103             }
104             else
105             {
106                 isAliveBefore[instructionOffset] &= ~(1L << variableIndex);
107             }
108         }
109     }
110
111
112     /**
113      * Returns whether the specified variable is alive after the instruction
114      * at the given offset.
115      */
116     public boolean isAliveAfter(int instructionOffset, int variableIndex)
117     {
118         return variableIndex >= MAX_VARIABLES_SIZE ||
119                (isAliveAfter[instructionOffset] & (1L << variableIndex)) != 0;
120     }
121
122
123     /**
124      * Sets whether the specified variable is alive after the instruction
125      * at the given offset.
126      */
127     public void setAliveAfter(int instructionOffset, int variableIndex, boolean alive)
128     {
129         if (variableIndex < MAX_VARIABLES_SIZE)
130         {
131             if (alive)
132             {
133                 isAliveAfter[instructionOffset] |= 1L << variableIndex;
134             }
135             else
136             {
137                 isAliveAfter[instructionOffset] &= ~(1L << variableIndex);
138             }
139         }
140     }
141
142
143     /**
144      * Returns whether the specified variable takes up two entries after the
145      * instruction at the given offset.
146      */
147     public boolean isCategory2(int instructionOffset, int variableIndex)
148     {
149         return variableIndex < MAX_VARIABLES_SIZE &&
150                (isCategory2[instructionOffset] & (1L << variableIndex)) != 0;
151     }
152
153
154     /**
155      * Sets whether the specified variable takes up two entries after the
156      * instruction at the given offset.
157      */
158     public void setCategory2(int instructionOffset, int variableIndex, boolean category2)
159     {
160         if (variableIndex < MAX_VARIABLES_SIZE)
161         {
162             if (category2)
163             {
164                 isCategory2[instructionOffset] |= 1L << variableIndex;
165             }
166             else
167             {
168                 isCategory2[instructionOffset] &= ~(1L << variableIndex);
169             }
170         }
171     }
172
173
174     // Implementations for AttributeVisitor.
175
176     public void visitAnyAttribute(Clazz clazz, Attribute attribute) {}
177
178
179     public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute)
180     {
181 // DEBUG =
182 // clazz.getName().equals("abc/Def") &&
183 // method.getName(clazz).equals("abc");
184
185         if (DEBUG)
186         {
187             System.out.println();
188             System.out.println("Liveness analysis: "+clazz.getName()+"."+method.getName(clazz)+method.getDescriptor(clazz));
189         }
190
191         // Initialize the global arrays.
192 initializeArrays(codeAttribute);
193
194         // Evaluate the method.
195 partialEvaluator.visitCodeAttribute(clazz, method, codeAttribute);
196
197         int codeLength = codeAttribute.u4codeLength;
198         int variablesSize = codeAttribute.u2maxLocals;
199
200         // We'll only really analyze the first 64 variables.
201 if (variablesSize > MAX_VARIABLES_SIZE)
202         {
203             variablesSize = MAX_VARIABLES_SIZE;
204         }
205
206         // Mark liveness blocks, as many times as necessary.
207 do
208         {
209             checkAgain = false;
210             alive = 0L;
211
212             // Loop over all traced instructions, backward.
213 for (int offset = codeLength - 1; offset >= 0; offset--)
214             {
215                 if (partialEvaluator.isTraced(offset))
216                 {
217                     // Update the liveness based on the branch targets.
218 InstructionOffsetValue branchTargets = partialEvaluator.branchTargets(offset);
219                     if (branchTargets != null)
220                     {
221                         // Update the liveness right after the branch instruction.
222 alive = combinedLiveness(branchTargets);
223                     }
224
225                     // Merge the current liveness.
226 alive |= isAliveAfter[offset];
227
228                     // Update the liveness after the instruction.
229 isAliveAfter[offset] = alive;
230
231                     // Update the current liveness based on the instruction.
232 codeAttribute.instructionAccept(clazz, method, offset, this);
233
234                     // Merge the current liveness.
235 alive |= isAliveBefore[offset];
236
237                     // Update the liveness before the instruction.
238 if ((~isAliveBefore[offset] & alive) != 0L)
239                     {
240                         isAliveBefore[offset] = alive;
241
242                         // Do we have to check again after this loop?
243 checkAgain |= offset < maxOffset(partialEvaluator.branchOrigins(offset));
244                     }
245                 }
246             }
247
248             // Account for the liveness at the start of the exception handlers.
249 codeAttribute.exceptionsAccept(clazz, method, this);
250         }
251         while (checkAgain);
252
253         // Loop over all instructions, to mark variables that take up two entries.
254 for (int offset = 0; offset < codeLength; offset++)
255         {
256             if (partialEvaluator.isTraced(offset))
257             {
258                 // Loop over all variables.
259 for (int variableIndex = 0; variableIndex < variablesSize; variableIndex++)
260                 {
261                     // Is the variable alive and a category 2 type?
262 if (isAliveBefore(offset, variableIndex))
263                     {
264                         Value value = partialEvaluator.getVariablesBefore(offset).getValue(variableIndex);
265                         if (value != null && value.isCategory2())
266                         {
267                             // Mark it as such.
268 setCategory2(offset, variableIndex, true);
269
270                             // Mark the next variable as well.
271 setAliveBefore(offset, variableIndex + 1, true);
272                             setCategory2( offset, variableIndex + 1, true);
273                         }
274                     }
275
276                     // Is the variable alive and a category 2 type?
277 if (isAliveAfter(offset, variableIndex))
278                     {
279                         Value value = partialEvaluator.getVariablesAfter(offset).getValue(variableIndex);
280                         if (value != null && value.isCategory2())
281                         {
282                             // Mark it as such.
283 setCategory2(offset, variableIndex, true);
284
285                             // Mark the next variable as well.
286 setAliveAfter(offset, variableIndex + 1, true);
287                             setCategory2( offset, variableIndex + 1, true);
288                         }
289                     }
290                 }
291             }
292         }
293
294         if (DEBUG)
295         {
296             // Loop over all instructions.
297 for (int offset = 0; offset < codeLength; offset++)
298             {
299                 if (partialEvaluator.isTraced(offset))
300                 {
301                     long aliveBefore = isAliveBefore[offset];
302                     long aliveAfter = isAliveAfter[offset];
303                     long category2 = isCategory2[offset];
304
305                     // Print out the liveness of all variables before the instruction.
306 for (int variableIndex = 0; variableIndex < variablesSize; variableIndex++)
307                     {
308                         long variableMask = (1L << variableIndex);
309                         System.out.print((aliveBefore & variableMask) == 0L ? '.' :
310                                          (category2 & variableMask) == 0L ? 'x' :
311                                                                               '*');
312                     }
313
314                     // Print out the instruction itself.
315 System.out.println(" "+ InstructionFactory.create(codeAttribute.code, offset).toString(offset));
316
317                     // Print out the liveness of all variables after the instruction.
318 for (int variableIndex = 0; variableIndex < variablesSize; variableIndex++)
319                     {
320                         long variableMask = (1L << variableIndex);
321                         System.out.print((aliveAfter & variableMask) == 0L ? '.' :
322                                          (category2 & variableMask) == 0L ? 'x' :
323                                                                              '=');
324                     }
325
326                     System.out.println();
327                 }
328             }
329         }
330     }
331
332
333     // Implementations for InstructionVisitor.
334
335     public void visitAnyInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, Instruction instruction) {}
336
337
338     public void visitVariableInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, VariableInstruction variableInstruction)
339     {
340         int variableIndex = variableInstruction.variableIndex;
341         if (variableIndex < MAX_VARIABLES_SIZE)
342         {
343             long livenessMask = 1L << variableIndex;
344
345             // Is it a load instruction or a store instruction?
346 if (variableInstruction.isLoad())
347             {
348                 // Start marking the variable before the load instruction.
349 alive |= livenessMask;
350             }
351             else if (variableInstruction.opcode != InstructionConstants.OP_IINC)
352             {
353                 // Stop marking the variable before the store instruction.
354 alive &= ~livenessMask;
355
356                 // But do mark the variable right after the store instruction.
357 isAliveAfter[offset] |= livenessMask;
358             }
359         }
360     }
361
362
363     public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction)
364     {
365         // Special case: variable 0 ('this') in an initializer has to be alive
366 // as long as it hasn't been initialized.
367 if (offset == partialEvaluator.superInitializationOffset())
368         {
369             alive |= 1L;
370         }
371     }
372
373
374     // Implementations for ExceptionInfoVisitor.
375
376     public void visitExceptionInfo(Clazz clazz, Method method, CodeAttribute codeAttribute, ExceptionInfo exceptionInfo)
377     {
378         // Are any variables alive at the start of the handler?
379 long alive = isAliveBefore[exceptionInfo.u2handlerPC];
380         if (alive != 0L)
381         {
382             // Set the same liveness flags for the entire try block.
383 int startOffset = exceptionInfo.u2startPC;
384             int endOffset = exceptionInfo.u2endPC;
385
386             for (int offset = startOffset; offset < endOffset; offset++)
387             {
388                 if (partialEvaluator.isTraced(offset))
389                 {
390                     if ((~(isAliveBefore[offset] & isAliveAfter[offset]) & alive) != 0L)
391                     {
392                         isAliveBefore[offset] |= alive;
393                         isAliveAfter[offset] |= alive;
394
395                         // Check again after having marked this try block.
396 checkAgain = true;
397                     }
398                 }
399             }
400         }
401     }
402
403
404     // Small utility methods.
405
406     /**
407      * Initializes the global arrays.
408      */
409     private void initializeArrays(CodeAttribute codeAttribute)
410     {
411         int codeLength = codeAttribute.u4codeLength;
412
413         // Create new arrays for storing information at each instruction offset.
414 if (isAliveBefore.length < codeLength)
415         {
416             isAliveBefore = new long[codeLength];
417             isAliveAfter = new long[codeLength];
418             isCategory2 = new long[codeLength];
419         }
420         else
421         {
422             for (int index = 0; index < codeLength; index++)
423             {
424                 isAliveBefore[index] = 0L;
425                 isAliveAfter[index] = 0L;
426                 isCategory2[index] = 0L;
427             }
428         }
429     }
430
431
432     private long combinedLiveness(InstructionOffsetValue instructionOffsetValue)
433     {
434         long alive = 0L;
435
436         int count = instructionOffsetValue.instructionOffsetCount();
437         for (int index = 0; index < count; index++)
438         {
439             alive |= isAliveBefore[instructionOffsetValue.instructionOffset(index)];
440         }
441
442         return alive;
443     }
444
445
446     /**
447      * Returns the minimum offset from the given instruction offsets.
448      */
449     private int minOffset(Value instructionOffsets)
450     {
451         return minOffset(instructionOffsets, Integer.MAX_VALUE);
452     }
453
454
455     /**
456      * Returns the minimum offset from the given instruction offsets.
457      */
458     private int minOffset(Value instructionOffsets, int minOffset)
459     {
460         if (instructionOffsets != null)
461         {
462             InstructionOffsetValue instructionOffsetValue =
463                 instructionOffsets.instructionOffsetValue();
464
465             int count = instructionOffsetValue.instructionOffsetCount();
466             for (int index = 0; index < count; index++)
467             {
468                 int offset = instructionOffsetValue.instructionOffset(index);
469                 if (minOffset > offset)
470                 {
471                     minOffset = offset;
472                 }
473             }
474         }
475
476         return minOffset;
477     }
478
479
480     /**
481      * Returns the maximum offset from the given instruction offsets.
482      */
483     private int maxOffset(Value instructionOffsets)
484     {
485         return maxOffset(instructionOffsets, Integer.MIN_VALUE);
486     }
487
488
489     /**
490      * Returns the maximum offset from the given instruction offsets.
491      */
492     private int maxOffset(Value instructionOffsets, int maxOffset)
493     {
494         if (instructionOffsets != null)
495         {
496             InstructionOffsetValue instructionOffsetValue =
497                 instructionOffsets.instructionOffsetValue();
498
499             int count = instructionOffsetValue.instructionOffsetCount();
500             for (int index = 0; index < count; index++)
501             {
502                 int offset = instructionOffsetValue.instructionOffset(index);
503                 if (maxOffset < offset)
504                 {
505                     maxOffset = offset;
506                 }
507             }
508         }
509
510         return maxOffset;
511     }
512 }
513
Popular Tags