KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > jbet > Block


1 /*
2  * JBET - Java Binary Enhancement Tool
3  * Copyright (c) 2003 Networks Associates Technology, Inc.
4  *
5  * This software was developed under DARPA/SPAWAR contract
6  * N66001-00-C-8602 "SPMA" and DARPA/AFRL contract
7  * F30602-00-C-0183 "Survivable Server" as part of the
8  * DARPA OASIS research program.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions
12  * are met:
13  * 1. Redistributions of source code must retain the above copyright
14  * notice, this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in the
17  * documentation and/or other materials provided with the distribution.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
23  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29  * SUCH DAMAGE.
30  */
31
32 /* Abstract interface for a (possibly basic) block. Contains a block number and an exit record,
33    which replaces control-flow instructions.
34
35    See derived classes:
36
37    InstrBlock - block of original JVM instructions
38    BasicBlock - represents a basic block as a value DAG
39
40    @author Andrew Reisse
41 */
42
43 package jbet;
44 import java.util.*;
45
46
47 public class Block
48 {
49     public ExitRec es; // exit behavior
50 public int swval; // block number
51 public int enflags; // the En flags
52 public int blflags; // the Blc flags
53 Vector pred; // predecessors (now only for basicBlocks)
54 Object JavaDoc data;
55
56     public static class ExcInfo
57     {
58     public String JavaDoc type; // handle type
59 public ExceptionRec info; // from original ClassRep
60 public Block handler;
61
62         public ExcInfo () { }
63     public ExcInfo (ExcInfo ei) {
64         type = ei.type; info = ei.info; handler = ei.handler;
65     }
66     public ExcInfo (String JavaDoc t, ExceptionRec i) { type = t; info = i; }
67     }
68
69     // flags for exit behavior
70 public static final int Exit_DoubleCons = 1;
71     public static final int Exit_NewFrame = 2; /* We have locals that cannot be saved, so a method call will
72                             need to make a new Java stack frame */
73     public static final int Exit_swap = 4;
74
75     public static final String JavaDoc[] Exit_flags = {"Double cons", "New frame", "Swap"};
76
77     // exit roles
78 public static final int Erol_Unknown = 0;
79     public static final int Erol_Single = 1;
80     public static final int Erol_Cond = 2;
81     public static final int Erol_LoopCond = 3;
82     public static final int Erol_Switch = 4;
83     public static final int Erol_Special = 5;
84
85     public static final String JavaDoc[] Erol_names = {"unknown", "single", "conditional", "loop condition", "switch", "special"};
86
87     // flags for entry behaviour
88 public static final int En_jsr = 1; // this block is the target of a jsr
89
90     public static final String JavaDoc[] En_flags = {"jsr"};
91
92     // flags for block contents
93 public static final int Blc_const = 1; // no changes outside its outputs
94 public static final int Blc_idempotent = 2; // can be executed any number of times same as one
95 public static final int Blc_indet = 4; // effects are completely determined by inputs
96 public static final int Blc_NoAlias = 8; // no aliases in block
97 public static final int Blc_disabled = 16;
98
99     public static final String JavaDoc[] Blc_flags = {"const", "idempotent", "indet", "noalias", "disabled"};
100
101     /* exit behavior of a block (InstrBlock or BasicBlock) */
102
103     public static class ExitRec
104     {
105     public Block primary; // default next block
106 public int op; // last instruction of block if jump
107 public int stackuse; // how many stack elements are needed by op
108 public Block jump; // target if conditional jump taken
109 public int swofs; // TABLESWITCH offset
110 public int retlvt; // local variable for ret
111 public Object JavaDoc retnode; // node for ret
112 public BranchTarget[] switches; // user's switch array, or ret possibilities
113 public int swanum; // switch translation array (tmp)
114 public Block ret; // where ret goes after jsr (this block ends in a jsr)
115 public boolean savestack; // whether to save the stack before implementing exit behavior
116 public MethodInfo method; // method and class if op is an invoke
117 public ClassInfo mclass;
118     public Vector exceptions; // possible exceptions for method call or throw in this block
119 public int superinit; // whether this call to <init> is a superclass initializer
120 public int exflags; // the Exit flags
121 public Hashtable localcopies;// ignore - to be removed soon
122 public int role;
123
124     public ExitRec ()
125     {
126         primary = jump = null;
127         switches = null;
128         op = 0;
129         swofs = 0;
130         savestack = true;
131         method = null;
132         mclass = null;
133         superinit = 0;
134         exflags = 0;
135         localcopies = new Hashtable();
136     }
137
138     public ExitRec (int _op, Block j, Block p)
139     {
140         super ();
141         op = _op;
142         primary = p;
143         jump = j;
144     }
145
146     public ExcInfo exAt (int i)
147     {
148         return (ExcInfo) exceptions.elementAt (i);
149     }
150
151     public static String JavaDoc exflags2str (int exflags)
152     {
153         return Util.flags2str (exflags, Exit_flags);
154     }
155
156     public void print (LineWriter out) {
157         if (exflags != 0)
158         out.println ("\tE\t\t" + exflags2str (exflags) + ' ' + Erol_names[role]);
159
160         switch( op ) {
161         case Instruction.OP_IFEQ:
162         case Instruction.OP_IFNE:
163         case Instruction.OP_IFLT:
164         case Instruction.OP_IFGE:
165         case Instruction.OP_IFGT:
166         case Instruction.OP_IFLE:
167         case Instruction.OP_IF_ICMPEQ:
168         case Instruction.OP_IF_ICMPNE:
169         case Instruction.OP_IF_ICMPLT:
170         case Instruction.OP_IF_ICMPGE:
171         case Instruction.OP_IF_ICMPGT:
172         case Instruction.OP_IF_ICMPLE:
173         case Instruction.OP_IF_ACMPEQ:
174         case Instruction.OP_IF_ACMPNE:
175         case Instruction.OP_IFNULL:
176         case Instruction.OP_IFNONNULL:
177         out.println ("\tE\t\t" + Instruction.mnemonics[op] + " #B" +
178                  jump.swval + " else #B" + primary.swval);
179         break;
180         case Instruction.OP_TABLESWITCH:
181         out.print ("\tE\t\t" + Instruction.mnemonics[op] + " #B" +
182                primary.swval);
183         for (int i = 0; i < switches.length; i++)
184             out.print (" " + (i+swofs) + ":#B" + switches[i].block.swval);
185         out.println ();
186         break;
187         case Instruction.OP_LOOKUPSWITCH:
188         out.print ("\tE\t\t" + Instruction.mnemonics[op] + " #B" + primary.swval);
189         for (int i = 0; i < switches.length; i++)
190             out.print (" " + switches[i].key + ":#B" + switches[i].block.swval);
191         out.println ();
192         break;
193         case Instruction.OP_JSR:
194         out.println ("\tE\t\tjsr #B" + primary.swval + " then #B" +
195                  ret.swval);
196         break;
197         case Instruction.OP_RET:
198         out.print ("\tE\t\tret " + retlvt);
199         if (switches == null) { out.println(); break; }
200         for (int i = 0; i < switches.length; i++)
201             out.print (" #B" + switches[i].block.swval);
202         out.println();
203         break;
204         case Instruction.OP_INVOKEVIRTUAL:
205         if (primary != null)
206             out.println ("\tE\t\tinvokevirtual #B" + primary.swval +
207                  " then #B" + ret.swval + " " + mclass.name() + "." + method.name + ": " +
208                  method.descriptor.toString ());
209         else
210             out.println ("\tE\t\tinvokevirtual " + mclass.name() + "." + method.name + method.descriptor +
211                  " then #B" + ret.swval);
212         break;
213         case Instruction.OP_INVOKESPECIAL:
214         if (superinit > 0)
215             out.println ("\tE\t\tinvokespecial (super init) #B" + primary.swval +
216                  " then #B" + ret.swval + " " + mclass.name() + "." + method.name + ": " +
217                  method.descriptor.toString ());
218         else
219             out.println ("\tE\t\tinvokespecial #B" + primary.swval +
220                  " then #B" + ret.swval + " " + mclass.name() + "." + method.name + ": " +
221                  method.descriptor.toString ());
222         break;
223         case Instruction.OP_INVOKESTATIC:
224         out.println ("\tE\t\tinvokestatic #B" + primary.swval +
225                  " then #B" + ret.swval + " " + mclass.name() + "." + method.name + ": " +
226                  method.descriptor.toString ());
227         break;
228         default:
229         out.println ("\tE\t\t" + Instruction.mnemonics[op]);
230         break;
231
232         case 0:
233           if (primary != null) {
234         out.println ("\tE\t\tgoto #B" + primary.swval);
235           } else {
236         out.println ("\tE\t\tBUG!");
237           }
238           break;
239         }
240
241         if (exceptions != null)
242         for (int i = 0; i < exceptions.size(); i++) {
243             ExcInfo ex = exAt (i);
244             out.println ("\tE\t\t" + ex.type + " -> #B" + ex.handler.swval);
245         }
246     }
247     }
248
249     /* This isn't successors in the usual sense, only blocks that follow and share data (so the first block of a
250        called method is not a successor, but the block after returning is)
251
252        @return list of successors
253     */
254
255     public Vector getSuccessors()
256     {
257       return getSuccessors (true);
258     }
259
260     public Vector getSuccessors (boolean doExceptions)
261     {
262     Vector succ = new Vector();
263
264     if (doExceptions && es.exceptions != null) {
265       for (int i = 0; i < es.exceptions.size(); i++) {
266         ExcInfo er = (ExcInfo) es.exceptions.elementAt (i);
267         succ.addElement (er.handler);
268       }
269     }
270
271     switch (es.op) {
272     case Instruction.OP_INVOKESTATIC:
273     case Instruction.OP_INVOKESPECIAL:
274     case Instruction.OP_INVOKEVIRTUAL:
275         succ.addElement (es.ret);
276         break;
277
278     case Instruction.OP_TABLESWITCH:
279     case Instruction.OP_LOOKUPSWITCH:
280         if (es.primary != null)
281         succ.addElement (es.primary);
282
283         for (int i = 0; i < es.switches.length; i++) {
284         succ.addElement (es.switches[i].block);
285         }
286         break;
287
288     case Instruction.OP_JSR:
289         if (es.primary != null)
290         succ.addElement (es.primary);
291         break;
292
293     case Instruction.OP_RET:
294         for (int i = 0; i < es.switches.length; i++)
295         succ.addElement( es.switches[i].block );
296         break;
297         
298     default:
299         if (es.primary != null)
300         succ.addElement (es.primary);
301         if (es.jump != null)
302         succ.addElement (es.jump);
303         if (es.ret != null)
304         succ.addElement (es.ret);
305         break;
306     }
307
308     return succ;
309     }
310     
311     /* get all successors of all blocks specified
312      
313     @param bbs List of blocks to get successors of
314     @param bused List of blocks to skip (this is modified to inlude all input blocks)
315
316     @return list of successors
317     */
318
319     public static Vector getSuccessors (Vector bbs, boolean[] bused)
320     {
321     Vector out = new Vector();
322     for (int i = 0; i < bbs.size(); i++) {
323         Block sb = (Block) (bbs.elementAt (i));
324
325         if (!bused[sb.swval-1]) {
326         bused[sb.swval-1] = true;
327         Vector newsuccs = sb.getSuccessors();
328         out.addAll (newsuccs);
329         }
330     }
331
332     return out;
333     }
334
335     /* Should be overriden by subclasses */
336     public void printinfo (LineWriter out, boolean printcode)
337     {
338     out.println ("invalid block type");
339     }
340
341     /*** EXPERIMENTAL - higher level behavior of basic blocks (to assist decompilers) */
342
343     static class IndetFlowException extends Exception JavaDoc
344     {
345     IndetFlowException () { super ("indeterminate control flow"); }
346     }
347
348     // return true if all normal control flow paths from this block eventually lead to other
349 boolean alwaysLeadsTo (Block other)
350     {
351     Hashtable h = new Hashtable();
352     return alwaysLeadsTo (other, h);
353     }
354
355     boolean alwaysLeadsTo (Block other, Hashtable skip)
356     {
357     Vector sbs = getSuccessors();
358     int n = 0;
359     Util.int_ptr result = new Util.int_ptr(-swval);
360     Vector checkLater = new Vector();
361
362     skip.put (this, result);
363
364     for (int i = 0; i < sbs.size(); i++)
365         if (sbs.elementAt (i) == other)
366         n++;
367
368     if (n == sbs.size() && sbs.size() != 0) {
369         result.i = 1;
370         return true;
371     }
372
373     for (int i = 0; i < sbs.size(); i++)
374         if (null == skip.get (sbs.elementAt (i))) {
375         if (((Block)sbs.elementAt (i)).alwaysLeadsTo (other, skip))
376             n++;
377         } else {
378         Util.int_ptr subresult = (Util.int_ptr)skip.get (sbs.elementAt (i));
379
380         if (subresult.i < 0)
381             checkLater.addElement (subresult);
382         else if (subresult.i == 1)
383             n++;
384         }
385
386     for (int i = 0; i < checkLater.size(); i++) {
387         Util.int_ptr iv = (Util.int_ptr)checkLater.elementAt (i);
388         if (iv.i == 1)
389         n++;
390         else if (iv.i < 0) {
391         
392         //if (iv != result)
393 //throw new IllegalStateException ("skipped block never finished: #B" + -iv.i);
394 }
395     }
396
397     if (n == sbs.size() && sbs.size() != 0) {
398         result.i = 1;
399         return true;
400     }
401
402     result.i = 0;
403
404     return false;
405     }
406
407     // return true if all normal control flow paths from this block eventually lead to other, or
408 // there is a closed loop inside
409 boolean alwaysIfLeadsTo (Block other)
410     {
411     if (other == this)
412         return true;
413
414     Hashtable h = new Hashtable();
415     return alwaysIfLeadsTo (other, h);
416     }
417
418     boolean alwaysIfLeadsTo (Block other, Hashtable skip)
419     {
420     class BCResult extends Util.int_ptr
421     {
422         Block block() { return Block.this; }
423         BCResult () { super (-1); }
424     }
425
426     Vector sbs = getSuccessors();
427     int n = 0;
428     BCResult result = new BCResult ();
429     Vector checkLater = new Vector();
430
431     skip.put (this, result);
432
433     for (int i = 0; i < sbs.size(); i++)
434         if (sbs.elementAt (i) == other)
435         n++;
436
437     if (n == sbs.size() && sbs.size() != 0) {
438         result.i = 1;
439         return true;
440     }
441
442     for (int i = 0; i < sbs.size(); i++)
443         if (null == skip.get (sbs.elementAt (i))) {
444         if (((Block)sbs.elementAt (i)).alwaysIfLeadsTo (other, skip))
445             n++;
446         } else {
447         BCResult subresult = (BCResult)skip.get (sbs.elementAt (i));
448
449         if (subresult.i < 0)
450             checkLater.addElement (subresult);
451         else if (subresult.i == 1)
452             n++;
453         }
454
455     for (int i = 0; i < checkLater.size(); i++) {
456         BCResult iv = (BCResult)checkLater.elementAt (i);
457         if (iv.i == 1)
458         n++;
459         else if (iv.i < 0) {
460         Block sb = iv.block();
461
462         if (sb.es.primary != null && sb.es.jump != null) {
463             if (sb.es.primary.alwaysIfLeadsTo (sb) ||
464             sb.es.jump.alwaysIfLeadsTo (sb))
465             n++;
466         }
467         }
468     }
469
470     if (n == sbs.size() && sbs.size() != 0) {
471         result.i = 1;
472         return true;
473     }
474
475     result.i = 0;
476
477     return false;
478     }
479
480     // return true if all normal control flow paths from this block eventually lead to any block in others, or
481 // there is a closed loop inside
482 boolean alwaysIfLeadsTo (Vector others)
483     {
484     Hashtable h = new Hashtable();
485     return alwaysIfLeadsTo (others, h);
486     }
487
488     boolean alwaysIfLeadsTo (Vector others, Hashtable skip)
489     {
490     class BCResult extends Util.int_ptr
491     {
492         Block block() { return Block.this; }
493         BCResult () { super (-1); }
494     }
495
496     Vector sbs = getSuccessors();
497     int n = 0;
498     BCResult result = new BCResult ();
499     Vector checkLater = new Vector();
500
501     skip.put (this, result);
502
503     for (int i = 0; i < sbs.size(); i++)
504         for (int j = 0; j < others.size(); j++)
505         if (sbs.elementAt (i) == others.elementAt (j))
506             n++;
507
508     if (n == sbs.size() && sbs.size() != 0) {
509         result.i = 1;
510         return true;
511     }
512
513     for (int i = 0; i < sbs.size(); i++)
514         if (null == skip.get (sbs.elementAt (i))) {
515         if (((Block)sbs.elementAt (i)).alwaysIfLeadsTo (others, skip))
516             n++;
517         } else {
518         BCResult subresult = (BCResult)skip.get (sbs.elementAt (i));
519
520         if (subresult.i < 0)
521             checkLater.addElement (subresult);
522         else if (subresult.i == 1)
523             n++;
524         }
525
526     for (int i = 0; i < checkLater.size(); i++) {
527         BCResult iv = (BCResult)checkLater.elementAt (i);
528         if (iv.i == 1)
529         n++;
530         else if (iv.i < 0) {
531         Block sb = iv.block();
532
533         if (sb.es.primary != null && sb.es.jump != null) {
534             if (sb.es.primary.alwaysIfLeadsTo (sb) ||
535             sb.es.jump.alwaysIfLeadsTo (sb))
536             n++;
537         }
538         }
539     }
540
541     if (n == sbs.size() && sbs.size() != 0) {
542         result.i = 1;
543         return true;
544     }
545
546     result.i = 0;
547
548     return false;
549     }
550
551     // returns the first block that always follows a and b, or null if none
552 static Block firstCommonSuccessor (Vector bbs, Block a, Block b)
553     {
554     HashSet aas = new HashSet();
555     HashSet abs = new HashSet();
556     Vector as = new Vector();
557     Vector bs = new Vector();
558     boolean[] aused = new boolean [bbs.size()];
559     boolean[] bused = new boolean [bbs.size()];
560
561     as.addElement (a);
562     aas.add (a);
563     bs.addElement (b);
564     abs.add (b);
565
566     while (as.size() + bs.size() > 0) {
567         as = getSuccessors (as, aused);
568         aas.addAll (as);
569         bs = getSuccessors (bs, bused);
570         abs.addAll (bs);
571
572         for (Iterator i = aas.iterator(); i.hasNext(); ) {
573         Object JavaDoc o = i.next();
574         if (abs.contains (o))
575             return (Block)o;
576         }
577     }
578
579     return null;
580     }
581
582     // returns the first block that always follows all blocks in bbs, or null if none
583 static Block firstCommonSuccessor (final Vector allBlocks, final Vector bbs)
584     {
585     class BInfo {
586         Block b;
587         HashSet as = new HashSet();
588         Vector s = new Vector();
589         boolean[] bused = new boolean [allBlocks.size()];
590
591         BInfo (Block bin) { b = bin; as.add (b); s.add (b); }
592
593         int sum (BInfo[] bis) {
594         int n = 0;
595         for (int i = 0; i < bis.length; i++)
596             n += bis[i].s.size();
597         return n;
598         }
599     };
600
601     BInfo[] bis = new BInfo [bbs.size()];
602
603     for (int i = 0; i < bis.length; i++)
604         bis[i] = new BInfo ((Block)bbs.elementAt (i));
605
606     while (bis[0].sum (bis) > 0) {
607         for (int i = 0; i < bis.length; i++) {
608         BInfo bi = bis[i];
609
610         bi.s = getSuccessors (bi.s, bi.bused);
611         bi.as.addAll (bi.s);
612         }
613
614         for (Iterator i = bis[0].as.iterator(); i.hasNext(); ) {
615         Object JavaDoc o = i.next();
616         int n = 1;
617
618         for (int j = 1; j < bis.length; j++)
619             if (bis[j].as.contains (o))
620             n++;
621
622         if (n == bis.length)
623             return (Block) o;
624         }
625     }
626
627     return null;
628     }
629
630     /* renumber a vector of blocks */
631
632     static void renumber (Vector bbs)
633     {
634     for (int i = 0; i < bbs.size(); i++) {
635         Block sb = (Block)(bbs.elementAt (i));
636         sb.swval = i+1;
637     }
638     }
639
640 }
641
Popular Tags