BasicBlock


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" as part of the
7    * DARPA OASIS research program.
8    *
9    * Redistribution and use in source and binary forms, with or without
10   * modification, are permitted provided that the following conditions
11   * are met:
12   * 1. Redistributions of source code must retain the above copyright
13   *    notice, this list of conditions and the following disclaimer.
14   * 2. Redistributions in binary form must reproduce the above copyright
15   *    notice, this list of conditions and the following disclaimer in the
16   *    documentation and/or other materials provided with the distribution.
17   *
18   * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19   * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21   * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
22   * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23   * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24   * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25   * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26   * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27   * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28   * SUCH DAMAGE.
29   */
30  
31  /** Representation of a basic block stored as a value dag.
32     Includes conversion from JVM basic blocks to value dags, and 
33     support for linking inputs of predecessors to outputs.
34  
35     The user interface for this class is graphify, which creates a 
36     DagRep for a method specified by its basic blocks.
37  
38     Control flow is initially maintained as exit records (defined in Block)
39  
40     @author Andrew Reisse
41     @author Larry D'Anna
42  */
43  
44  package jbet;
45  import java.util.*;
46  
47  public class BasicBlock extends Block
48  {
49      public Node.var[] inputs;     // inputs (either method arguments or outputs of other blocks)
50      public Node []    outputs;    // values produced (stored or left on stack) by this block.
51      public InternSet  senodes;    // all nodes with side effects.
52      public String       handler;    // if not null, type for which this block begins an exception handler
53      public AliasDB    db;
54      public Node[]     esnodes;    // nodes needed by exit record.
55      
56      public String       bname;      // comment displayed by printinfo
57      public Vector     alternates; // other versions of this block
58      public Node.cint  swvaln;
59  
60      public static String   JbetLogFacility = "dags";
61  
62      public BasicBlock splitInHalf() { 
63      final
64      Util.int_ptr evil = new Util.int_ptr(-10);
65      final Node[] nodes = order();
66      final int    mid = nodes.length/2; 
67      Vector       oldins = new Vector();
68      final Vector newins = new Vector();
69      Vector       oldouts = new Vector();
70      Vector       newouts = new Vector();
71      InternSet    newsenodes = new InternSet();
72      InternSet    oldsenodes = new InternSet();
73  
74      final BasicBlock ret = new BasicBlock();
75      final InternSet  consts = new InternSet();
76      final Node[]     crossovers = new Node [ nodes.length ];
77  
78      if (bname == null)
79          bname = "#B" + String.valueOf (swval);
80  
81      // set evil
82  
83      for (Iterator i = findnodes().iterator(); i.hasNext(); ) {
84          Object   io = i.next();
85          if (io instanceof Node.var) {
86          Node.var var = (Node.var)io;
87          if (var.v < evil.i)
88              evil.i = var.v - 10;
89          }
90      }
91      evil.i = -666;
92  
93  
94      // the exception handler input has to be listed even if not used.
95      // it also must be in the first half
96      Node.var _exinput = null;
97      for (int i = 0; i < inputs.length; i++)
98          if (inputs[i].exobject) {
99          oldins.add(inputs[i]);
100         _exinput = inputs[i];
101         }
102     final Node.var exinput = _exinput;
103 
104     class _util { 
105         Node check_param(Node p) { 
106         if (p instanceof Node.var && p != exinput) { 
107             Node.var pv = (Node.var) p;
108             for (int i = 0; i < newins.size(); i++) {
109             Node.var v = (Node.var) newins.elementAt(i);
110             if (v.v == pv.v) return v;
111             }
112             Node newvar = ((Node.var)p).split(ret);
113             newins.add(newvar);
114             return newvar;
115         } else if (p.number < mid || p == exinput) {
116             if (p instanceof Node.constant) { 
117             Node newconst = p.safeclone();
118             newconst.sb = ret;
119             newconst = (Node) consts.add2(newconst);
120             return newconst;
121             } else { 
122             if (crossovers[p.number] == null) {
123                 Node.var var = 
124                 new Node.var(evil.i--, p.type());
125                 var.sb = ret;
126                 p.addDestination2(var);
127                 newins.add(var);
128 
129                 crossovers[p.number] = var;
130             }
131             return crossovers[p.number];
132             }
133         }
134         return p;
135         }
136         boolean forreal(Node n) {  // check to see if a node is extranious
137         return n.number >= 0 && n.number < nodes.length &&
138             n == nodes[n.number];
139         }
140     };
141     _util util = new _util();
142 
143     //loop over 2nd half 
144     for (int i = mid; i < nodes.length; i++) { 
145         Node n = nodes[i];
146         if (n == exinput) continue;
147         n.sb = ret;
148         if (n.destinations != null) newouts.add(n);
149         if (n instanceof Node.var) continue;
150         if (senodes.contains(n))
151         newsenodes.add(n);
152 
153         for (int j=0; j < n.numParams(); j++)
154         n.requires.setElementAt(util.check_param(n.usesAt(j)),j);
155 
156         //if n requires any nodes in the first half then we don't
157         //need that edge anymore.  We also traverse through
158         //extranious nodes.  The purpose of this is to make sure
159         //order doesn't wind up includeing nodes from the first half
160         for (int j = n.numParams(); j < n.requires.size();) 
161         if (util.forreal(n.usesAt(j)))
162             if (n.usesAt(j).number < mid) {
163             n.requires.removeElementAt(j);
164             } else
165             j++;
166         else { 
167             Node fake = n.usesAt(j);
168             n.requires.removeElementAt(j);
169             for (int k = fake.numParams(); k < fake.requires.size(); k++) {
170             n.requires.add( fake.usesAt(k) );
171             }
172         }
173     }
174 
175     // do esnodes
176     for (int i = 0; i < esnodes.length; i++) 
177         esnodes[i] = util.check_param(esnodes[i]);
178 
179     //loop over first half
180     for (int i = 0; i < mid; i++) { 
181         Node n = nodes[i];
182         if (n.destinations != null) oldouts.add(n);
183         if (n instanceof Node.var) continue;
184         if (senodes.contains(n))
185         oldsenodes.add(n);
186         for (int j = 0 ; j < n.numParams(); j++) 
187         if (n.usesAt(j) instanceof Node.var) {
188             Node.var old = (Node.var) n.usesAt (j);
189 
190             boolean found = false;
191             for (Iterator ita = oldins.iterator(); ita.hasNext(); )
192             if (((Node.var)ita.next()).v == old.v) {
193                 found = true;
194                 break;
195             }
196 
197             if (!found)
198             oldins.add (old);
199         }
200     }
201     if (exinput != null && exinput.number >= mid && exinput.destinations!=null)
202         oldouts.add(exinput);
203 
204     ret.inputs  = (Node.var[]) newins.toArray(new Node.var[0]);
205     ret.outputs = (Node[])     newouts.toArray(new Node[0]);
206     ret.senodes = newsenodes;
207     ret.bname = "" + bname + ".B";
208     ret.esnodes = esnodes;
209     ret.es = es;
210 
211 
212     //if any inputs are deleted, remove them from their producers
213     OUTER: 
214     for (int i = 0; i < inputs.length; i++) { 
215         for (int j = 0; j < oldins.size(); j++) 
216         if (inputs[i] == oldins.elementAt(j))
217             continue OUTER;
218         for (Iterator j = inputs[i].producers.iterator(); j.hasNext();) 
219         ((Node)j.next()).destinations.remove(inputs[i]);
220     }
221 
222     inputs  = (Node.var[]) oldins.toArray(new Node.var[0]);
223     outputs = (Node [])    oldouts.toArray(new Node[0]);
224     senodes = oldsenodes;
225 
226 
227     bname   = "" + bname + ".A";
228     esnodes = new Node[0];
229     es = new ExitRec(0, null, ret);
230 
231     //copy exception handlers if there are any
232     if (ret.es.exceptions != null) { 
233         es.exceptions = new Vector (ret.es.exceptions.size());
234         for (int i = 0; i < ret.es.exceptions.size(); i++)
235         es.exceptions.add
236             (new ExcInfo((ExcInfo) ret.es.exceptions.elementAt(i)));
237     }
238 
239     class _util2 {
240         String   bname (BasicBlock sb) {
241         if (sb == ret)
242             return "new second half of " + swval;
243         else
244             return Integer.toString (sb.swval);
245         }
246         void check (BasicBlock sb) {
247         for (Iterator i = sb.findnodes().iterator(); i.hasNext(); ) {
248             Object   io = i.next();
249             if (io instanceof Node.var) {
250             Node.var iv = (Node.var)io;
251             if (iv.sb != sb) throw new IllegalStateException   
252                 ("block " + bname(sb) + " has var from " + iv.sb.swval);
253 
254             for (Iterator ij = iv.producers.iterator(); ij.hasNext(); ) {
255                 Node no = (Node) ij.next();
256 
257                 if (!no.destinations.contains (iv)) throw new 
258                 IllegalStateException   ("var " + iv + 
259                                " has no valid producer");
260 
261                 if (no.sb == null)
262                 if (no instanceof Node.param)
263                     continue;
264                 else throw new IllegalStateException   
265                     ("node " + no + " has no block");
266 
267                 if (no.sb.outputs == null) throw new 
268                 IllegalStateException   ("block " + bname(no.sb) + 
269                                " has no outputs");
270 
271                 int j;
272                 for (j = 0; j < no.sb.outputs.length; j++)
273                 if (no.sb.outputs[j] == no)
274                     break;
275                 if (j == no.sb.outputs.length) throw new 
276                 IllegalStateException   
277                 ("output " + no + " is not in outputs of " + 
278                  bname(no.sb) + "  -- produces " + iv);
279             }
280             }
281         }
282         }
283     } _util2 util2 = new _util2();
284     
285     util2.check(this);
286     util2.check(ret);
287 
288     return ret;
289     }
290 
291     public BasicBlock () { senodes = new InternSet(); }
292 
293     public BasicBlock (int numin, int numou, int numes)
294     {
295     inputs = new Node.var[numin];
296     if (numou > 0 || numin > 0)
297         outputs = new Node [numou];
298     else
299         outputs = inputs;
300     if (numes > 0 || numin > 0)
301         esnodes = new Node [numes];
302     else
303         esnodes = inputs;
304     senodes = new InternSet ();
305     }
306 
307     /**
308      * Constructs a BasicBlock from an InstrBlock.  
309      *
310      * @param in       input InstrBlock
311      */
312 
313     public BasicBlock (InstrBlock in)
314     {
315     this (in, ClassFilter.ALL);
316     }
317 
318     /**
319      * Constructs a BasicBlock from in.  
320      *
321      * @param in       input
322      * @param stacknum just an integer that is used to keep the var.v fields
323      *                   for stack-input nodes unique
324      * @param fixcons  Classes for which invokeinits should replace news
325      */
326     public BasicBlock (InstrBlock in, ClassFilter fixcons) {
327     model (in, fixcons, null, null);
328     }
329 
330 
331     void model(InstrBlock in, ClassFilter fixcons, final IntFunction inserials, AliasDB indb) {
332     senodes = new InternSet();
333     swval = in.swval;
334     handler = in.handler;
335     enflags = in.enflags;
336 
337     final Hashtable nodes;
338     // final boolean lonever[] = new boolean [in.psx.locals.length];
339     // lonever is true if we have touched this local
340     final Node    lonodes[] = new Node [in.psx.locals.length]; 
341     // lonodes are the locals 
342     final Node    stnodes[] = new Node [in.from.maxStack+1];
343     // stnodes is the stack
344     int           stacklen = 0;
345 
346     db = (indb == null) ? new AliasDB() : indb;
347 
348     nodes = new Hashtable();
349     es = new Block.ExitRec();
350 
351     /* Field version tracking. 
352        This is only used for debugging now, but it could help optimization
353        later. */
354     final Hashtable    fieldversions = new Hashtable();
355     final Util.int_ptr fieldmin = new Util.int_ptr (0);
356 
357     final Vector innodes = new Vector();
358     final Vector outnodes = new Vector();
359 
360     class _util {
361         /* return an input node for LVT, allocating a new graph node 
362            if necessary */
363 
364         Node lastorderd = null;
365 
366         Node addOrdered(Node n) { 
367         if (lastorderd  != null)
368             n.requires.addElement(lastorderd);
369         lastorderd = n;
370         return n;
371         }                     
372 
373         Node.var node (int lvt, Type t) {
374         Node.var n = new Node.var (lvt, t);
375         int f;
376         if (inserials != null && (f = inserials.f(lvt)) > 0)
377             db.setNode(n, f);
378         else
379             db.setNode(n);
380         n.count = 1;
381         n.sb = BasicBlock.this;
382         Object   o = nodes.get (n);
383         if (o != null) {
384             ((Node.var) o).count++;
385             return (Node.var) o;
386         }
387         nodes.put (n, n);
388         return n;
389         }
390 
391         /* return a node for the expression (a OP b), allocating a new 
392            graph node if necessary. */
393 
394         Node node (int op, Node a, Node b) {
395         Node n = new Node.N2 (op, a, b);
396         db.setNode(n);
397         n.sb = BasicBlock.this;
398         n.count = 1;
399         Object   o = nodes.get (n);
400         if (o != null) {
401             ((Node) o).count++;
402             return (Node) o;
403         }
404         nodes.put(n, n);
405         return n;
406         }
407 
408         /* return a node for the expression (OP a), allocating a new graph node if
409            necessary. */
410 
411         Node node (int op, Node a) {
412         Node n = new Node.N1 (op, a);
413         db.setNode(n);
414         n.sb  = BasicBlock.this;
415         n.count = 1;
416         Object   o = nodes.get (n);
417         if (o != null) {
418             ((Node) o).count++;
419             return (Node) o;
420         }
421         else {
422             n = new Node.N1 (op, a);
423             n.count = 1;
424             n.sb = BasicBlock.this;
425             nodes.put (n, n);
426             return n;
427         }
428         }
429 
430         /* return this node or one equal() to it and allready in the graph */ 
431         Node node (Node n) {
432         n.sb = BasicBlock.this; 
433         Object   o = nodes.get(n);
434         if (o == null) { 
435             nodes.put(n,n);
436             return n;
437         } else 
438             return (Node) o;
439         }
440 
441         /* return a node for checkcast or instanceof, allocating a new node if
442            necessary.
443            @param cname     class name for checkcast/instanceof
444            @param a         input object
445            @param checkcast true for checkcast, false for instanceof
446         */
447         Node.Cast Cast (String   cname, Node a, boolean checkcast) {
448         Node.Cast n = new Node.Cast (cname, a, checkcast);
449         if (checkcast) 
450             db.setNode(n, a.serial);
451         else 
452             db.setNode(n);
453         n.sb = BasicBlock.this;
454         Object   o = nodes.get (n);
455         if (o != null) {
456             ((Node) o).count++;
457             return (Node.Cast) o;
458         }
459         n.count = 1;
460         nodes.put(n, n);
461         return n;
462         }
463 
464         /* Local Check */ 
465         void lc(int i) { 
466         if (false) return; 
467         Node node = lonodes[i];
468         if (node instanceof Node.var) {
469             Node.var var = (Node.var) node;
470             if (var.leftover) { 
471             innodes.addElement(node);
472             var.leftover = false;
473             }
474         }
475         }
476 
477         /* Stack Check */ 
478         void sc(int i) { 
479         if (true) return; 
480         Node node = stnodes[i];
481         if (node instanceof Node.var) {
482             Node.var var = (Node.var) node;
483             if (var.leftover) { 
484             innodes.addElement(node);
485             var.leftover = false;
486             }
487         }
488         }
489 
490         // util.raiseall
491         void raiseall () {
492           for (Iterator e = fieldversions.values().iterator(); e.hasNext(); ) {
493         Util.int_ptr o = (Util.int_ptr) e.next();
494 
495         o.i++;
496           }
497           fieldmin.i++;
498         }
499 
500         // util.getfield
501         Node.getfield getfield (String   cname, String   field, Type t, Node obj){
502           Node.getfield n = new Node.getfield (cname, field, t, obj);
503           n.sb = BasicBlock.this;
504           
505           if (obj==null)
506           db.setNode(n, db.getSField(cname, field));
507           else 
508           db.setNode(n, db.getField(obj.serial, field));
509 
510           String   fname = cname + "." + field + (obj != null);
511           Object   o = fieldversions.get (fname);
512           if (o == null) {
513         Util.int_ptr ver = new Util.int_ptr (fieldmin.i);
514         fieldversions.put (fname, ver);
515         n.ver = ver.i;
516         nodes.put(n, n);
517         addOrdered(n);
518         return n;
519           } else {
520         n.ver = ((Util.int_ptr) o).i;
521         Node.getfield nn = (Node.getfield) nodes.get(n);
522         if (nn != null)
523             return nn;
524         nodes.put(n, n);
525         addOrdered(n);
526         return n;
527           }
528         }
529 
530         // util.setfield
531         Node.setfield setfield (String   cname, String   field, Type t, Node obj, Node val) {
532           Node.setfield n = new Node.setfield (cname, field, t, obj, val);
533           n.sb = BasicBlock.this;
534 
535           if (obj == null)
536           db.setSField(cname, field, val.serial);
537           else
538           db.setField(obj.serial, field, val.serial);
539 
540           String   fname = cname + "." + field + (obj != null);
541 
542           Object   o = fieldversions.get (fname);
543           if (o == null) {
544         Util.int_ptr ver = new Util.int_ptr (fieldmin.i+1);
545         fieldversions.put (fname, ver);
546         n.ver = ver.i;
547           } else {
548         n.ver = ++((Util.int_ptr) o).i;
549           }
550 
551           return n;
552 
553         }
554 
555     }
556     _util util = new _util();
557 
558     /* Register the locals left by the predecessor as inputs. They are not
559        stored as inputs unless used. */
560 
561     for (int i = 0; i < in.pse.locals.length; i++)
562         if (in.pse.locals[i] != null && in.pse.locals[i].base != '-') {
563         lonodes[i] = util.node (i, in.pse.locals[i]);
564         ((Node.var)lonodes[i]).leftover = true;
565         }
566 
567     /* Add records for anything left on the stack from other blocks */ 
568     for (int i = 0; i < in.pse.stacklen; i++) 
569         if (in.pse.stack[i] != null && in.pse.stack[i].base != '-') {
570         stnodes[stacklen] = util.node(- stacklen - 1, in.pse.stack[i]);
571         ((Node.var)stnodes[stacklen]).leftover = true;
572         //innodes.addElement (stnodes[stacklen]);
573         stacklen++;
574         }
575 
576 
577     /* Model the instructions in the block to construct the dag. */
578 
579     for (Instruction instr = in.code.head; instr != null; instr = instr.next){
580 
581         int lvt = instr.lvtIndex();
582         int op  = instr.opCode();
583         Node n;  // just a place to put new nodes
584 
585         switch (op) {
586         case Instruction.OP_NOP:
587         break;
588 
589         case Instruction.OP_IINC:
590         util.lc(lvt);
591 
592         lonodes[lvt] = util.node
593             (Node.OP_IADD, lonodes[lvt], 
594              util.node(new Node.cint (instr.immediate())));
595 
596         break;
597 
598         case Instruction.OP_ILOAD:
599         case Instruction.OP_FLOAD:
600         case Instruction.OP_ALOAD:
601         case Instruction.OP_LLOAD:
602         case Instruction.OP_DLOAD: {
603         Node local = lonodes[lvt];
604         stnodes[stacklen++] = local;
605         if (instr.lvname() != null && 
606             lonodes[lvt] instanceof Node.var && 
607             ((Node.var)lonodes[lvt]).v == lvt) { 
608             ((Node.var)lonodes[lvt]).addname( instr.lvname() );
609         }
610         break;
611         }
612 
613         case Instruction.OP_ISTORE:
614         case Instruction.OP_FSTORE:
615         case Instruction.OP_ASTORE:
616         case Instruction.OP_LSTORE:
617         case Instruction.OP_DSTORE:
618         lonodes[lvt] = stnodes[--stacklen];
619         break;
620 
621         case Instruction.OP_IUSHR:
622         case Instruction.OP_LUSHR:
623         case Instruction.OP_ISHR:
624         case Instruction.OP_ISHL:
625         case Instruction.OP_LSHR:
626         case Instruction.OP_LSHL:
627         case Instruction.OP_IADD:
628         case Instruction.OP_ISUB:
629         case Instruction.OP_IMUL:
630         case Instruction.OP_IDIV:
631             case Instruction.OP_IREM:
632             case Instruction.OP_LREM:
633         case Instruction.OP_IAND:
634         case Instruction.OP_IOR:
635         case Instruction.OP_IXOR:
636             case Instruction.OP_LADD:
637             case Instruction.OP_LSUB:
638             case Instruction.OP_LMUL:
639             case Instruction.OP_LDIV:
640             case Instruction.OP_LAND:
641             case Instruction.OP_LOR:
642             case Instruction.OP_LXOR:
643             case Instruction.OP_LCMP:
644         case Instruction.OP_FADD:   
645         case Instruction.OP_FSUB:
646         case Instruction.OP_FMUL:
647         case Instruction.OP_FDIV:
648             case Instruction.OP_FCMPL:
649             case Instruction.OP_FCMPG:
650         case Instruction.OP_DADD:   
651         case Instruction.OP_DSUB:
652         case Instruction.OP_DMUL:
653         case Instruction.OP_DDIV:
654             case Instruction.OP_DCMPL:
655             case Instruction.OP_DCMPG:
656         util.sc(stacklen-1); util.sc(stacklen-2);
657         stacklen--;
658         stnodes[stacklen-1] = util.node (Node.jvm2node [op], stnodes[stacklen-1], stnodes[stacklen]);
659         break;
660 
661         case Instruction.OP_ARRAYLENGTH:
662         case Instruction.OP_INEG:
663         case Instruction.OP_I2L:
664         case Instruction.OP_L2I:
665         case Instruction.OP_F2L:   // BJM
666         case Instruction.OP_F2I:
667         case Instruction.OP_I2F:
668         case Instruction.OP_L2F:
669         case Instruction.OP_D2L:   // BJM
670         case Instruction.OP_D2I:
671         case Instruction.OP_D2F:
672         case Instruction.OP_I2D:
673         case Instruction.OP_L2D:
674         case Instruction.OP_F2D:
675             case Instruction.OP_I2S:
676             case Instruction.OP_I2B:
677             case Instruction.OP_I2C:
678             case Instruction.OP_DNEG:
679             case Instruction.OP_FNEG:
680             case Instruction.OP_LNEG:
681         util.sc (stacklen-1);
682         stnodes[stacklen-1] = util.node (Node.jvm2node [op], stnodes[stacklen-1]);
683         break;
684 
685         case Instruction.OP_IALOAD:
686         case Instruction.OP_FALOAD:
687         case Instruction.OP_AALOAD:
688         case Instruction.OP_LALOAD:
689         case Instruction.OP_DALOAD:
690         case Instruction.OP_CALOAD:
691         case Instruction.OP_BALOAD:
692         case Instruction.OP_SALOAD: {
693         util.sc(stacklen-1); util.sc(stacklen-2);
694         stacklen--;
695         Node a = stnodes[stacklen-1];
696         Node i = stnodes[stacklen];
697         stnodes[stacklen-1] = util.node( new Node.aload(a,i) );
698                 
699         if (i  instanceof Node.cint) { 
700             if (db.isBad(a.serial))
701             db.setNode(stnodes[stacklen-1]);
702             else
703             db.setNode(stnodes[stacklen-1], db.getArrayElt(a.serial, ((Node.cint)i).i));
704         } else { 
705             db.setNode(stnodes[stacklen-1]);
706         }
707 
708         stnodes[stacklen-1].sb = this;
709         util.addOrdered( stnodes[stacklen-1] );
710         break;
711         }
712 
713         case Instruction.OP_IASTORE:
714         case Instruction.OP_FASTORE:
715         case Instruction.OP_AASTORE:
716         case Instruction.OP_LASTORE:
717         case Instruction.OP_DASTORE: 
718             case Instruction.OP_CASTORE:
719             case Instruction.OP_BASTORE:
720             case Instruction.OP_SASTORE: {
721         util.sc(stacklen-1); util.sc(stacklen-2); util.sc(stacklen-3); 
722 
723         Node a = stnodes[stacklen-3];
724         Node i = stnodes[stacklen-2];
725         Node v = stnodes[stacklen-1];
726 
727         n = util.node ( new Node.astore (a,i,v) );
728 
729         if (! db.isBad(a.serial)) {
730             if (i instanceof Node.cint)
731             db.setArrayElt(a.serial, ((Node.cint)i).i, v.serial);
732             else
733             db.setBad(a.serial);
734         }
735         
736         n.sb = this;
737         senodes.add (n);
738         util.addOrdered(n);
739         stacklen-=3;
740         break;
741         }
742 
743         case Instruction.OP_NEWARRAY:
744         stnodes[stacklen-1] = util.node ( new Node.NewArray 
745             (stnodes[stacklen-1], instr.immediate()) );
746         stnodes[stacklen-1].sb = this;
747         break;
748 
749         case Instruction.OP_ANEWARRAY:
750         stnodes[stacklen-1] = util.node ( new Node.NewArray 
751             (stnodes[stacklen-1], instr.classRef()) );
752         stnodes[stacklen-1].sb = this;
753         break;
754 
755         case Instruction.OP_MULTIANEWARRAY: {
756         int ns = instr.immediate ();
757         Node[] sizes = new Node[ns];
758 
759         for (int i = 0; i < ns; i++) {
760             sizes[i] = stnodes [stacklen - (ns-i)];
761             util.sc (stacklen - (ns-i));
762         }
763 
764         stacklen -= ns - 1;
765         stnodes[stacklen-1] = util.node (new Node.MultiNewArray (sizes, instr.classRef()));
766         }
767         break;
768 
769         case Instruction.AOP_IPUSH:
770         stnodes[stacklen] = util.node (new Node.cint (instr.immediate()));
771         db.setNode(stnodes[stacklen]);
772         stacklen++;
773         break;
774 
775         case Instruction.AOP_SPUSH:
776         stnodes[stacklen] = util.node 
777             (new Node.cString (instr.immediate_s()));
778         stacklen++;
779         break;
780 
781             case Instruction.AOP_LPUSH:
782                 stnodes[stacklen] = util.node
783             (new Node.clong( instr.immediate_l()));
784         db.setNode(stnodes[stacklen]);
785         stacklen++;
786                 break;
787 
788             case Instruction.AOP_FPUSH:  
789                 stnodes[stacklen++] = util.node
790             (new Node.cfloat( instr.immediate_f() ));
791                 break;
792             case Instruction.AOP_DPUSH:  
793                 stnodes[stacklen++] = util.node
794             (new Node.cdouble( instr.immediate_f() ));
795                 break;
796 
797             case Instruction.OP_ACONST_NULL:
798                 stnodes[stacklen++] = util.node(new Node.cnull ());
799                 break;
800 
801             case Instruction.OP_MONITORENTER:
802             case Instruction.OP_MONITOREXIT: 
803         util.sc(stacklen-1);
804         n = util.addOrdered ( util.node ( new Node.monitorop
805                           (op, stnodes[stacklen-1])/*.require()*/ ));
806         senodes.add(n);
807         --stacklen;
808                 break;
809 
810         case Instruction.OP_INVOKEVIRTUAL: 
811         case Instruction.OP_INVOKEINTERFACE: 
812         case Instruction.OP_INVOKESPECIAL: {
813         Node.invokev node = null;
814         Vector     args = new Vector();
815         Descriptor desc = instr.descriptor();
816         MethodSignature mi = new MethodSignature (instr.classRef(), instr.elemName(), desc);
817 
818         for (int i = 0; i < desc.args.length; i++) {
819             args.addElement (stnodes [stacklen - desc.args.length +i]);
820             util.sc(stacklen - desc.args.length + i);
821         }
822         util.sc(stacklen - desc.args.length -1);
823         stacklen -= desc.args.length;
824         
825         if (op == Instruction.OP_INVOKESPECIAL) {
826             node = (Node.invokev) util.node( new Node.invokev
827             (mi, stnodes[stacklen-1], args, op) );
828             node.sb = this;
829             util.addOrdered(node);
830             senodes.add(node);
831 
832             try {
833             if (node.method.name.equals ("<init>") && fixcons.check (node.method.classrep().toString()))
834                 node.op = Instruction.AOP_INVOKEINIT;
835             } catch (ClassFileException e) {
836             throw new RuntimeException   ("ClassFilter threw an exception", e);
837             }
838 
839             if (node.type().base == 'V') 
840             stacklen--;
841             else
842             stnodes[stacklen-1] = node;
843 
844             if (node.isinit()) {
845             stacklen--;
846             for (int i = 0; i < stacklen; i++)
847                 if (stnodes[i] == node.This)
848                 stnodes[i] = node;
849             for (int i = 0; i < lonodes.length; i++)
850                 if (lonodes[i] == node.This)
851                 lonodes[i] = node;
852             }
853         }
854         else {
855             if (desc.ret.base == 'V') {
856             node = (Node.invokev) util.node( new Node.invokev
857                        (mi, stnodes[--stacklen], args, op)/*.require()*/ );
858             node.sb = this;
859             util.addOrdered(node);
860             senodes.add(node);
861             } else {
862             stnodes[stacklen-1] = util.node (new Node.invokev 
863                 (mi, stnodes[stacklen-1], args, op) );
864             node = (Node.invokev) stnodes[stacklen-1];
865             stnodes[stacklen-1].sb = this;
866             util.addOrdered (stnodes[stacklen-1]);
867             senodes.add (stnodes[stacklen-1]);
868             }
869         }
870         db.setNode(node);
871         util.raiseall();
872         } // invokespecial
873         break;
874 
875         case Instruction.OP_INVOKESTATIC: {
876         Vector          args = new Vector();
877         Descriptor      desc = instr.descriptor();
878         MethodSignature mi = new MethodSignature (instr.classRef(), instr.elemName(), desc);
879 
880         for (int i = 0; i < desc.args.length; i++) {
881             args.addElement (stnodes [stacklen - (desc.args.length-i)]);
882             util.sc(stacklen - (desc.args.length-i));
883         }
884         stacklen -= desc.args.length - 1;
885         if (desc.ret.base == 'V') {
886             --stacklen;
887             n = util.node ( new Node.invokes (mi, args)/*.require()*/ );
888             db.setNode(n);
889             //n.sb = this;
890             senodes.add(n);
891             util.addOrdered (n);
892         } else {
893             stnodes[stacklen-1] = util.node (new Node.invokes (mi, args));
894             db.setNode(stnodes[stacklen-1]);
895             //stnodes[stacklen-1].sb = this;
896             senodes.add (stnodes[stacklen-1]);
897             util.addOrdered(stnodes[stacklen-1]);
898         }
899         util.raiseall();
900         } // invokestatic
901         break;
902 
903         case Instruction.OP_POP:
904         stacklen -= 1;
905         break;
906 
907             case Instruction.OP_POP2:
908                 if (stnodes[stacklen-1].type().category() == 2) {
909                     --stacklen;
910                 } else {
911                     stacklen -= 2;
912                 }
913                 break;
914 
915             case Instruction.OP_SWAP: {
916         Node t = stnodes[stacklen-1];
917         stnodes[stacklen-1] = stnodes[stacklen-2];
918         stnodes[stacklen-2] = t;
919         break;
920         }
921 
922         case Instruction.OP_DUP:
923         stnodes[stacklen] = stnodes[stacklen-1];
924         stnodes[stacklen].count++;
925         stacklen++;
926         break;
927 
928             /*
929              * Dup2:  Designed for duplicating longs/doubles, it duplicates
930              * the top two elements on the stack
931              * (foo, bar) => (foo, bar, foo, bar)
932              */
933             case Instruction.OP_DUP2:
934                 // Problem: in this file "longs" take a single stack
935                 // element.  So:
936                 // If type1 (word), dup 2.  else, dup
937                 if (stnodes[stacklen-1].type().category() == 2) {
938                     ++stacklen;
939                     stnodes[stacklen-1] = stnodes[stacklen-2];
940                 } else {
941                     stacklen += 2;
942                     stnodes[stacklen-1] = stnodes[stacklen-3];
943                     stnodes[stacklen-2] = stnodes[stacklen-4];
944                 }
945                 break;
946             /*
947              * Dup_x1: Duplicate, and insert two values down.
948              * IE: Copy to t, rot, push from t.
949              * (foo, bar) => (bar, foo, bar)
950              */
951             case Instruction.OP_DUP_X1:
952         //util.sc(stacklen-1); util.sc(stacklen-2); 
953                 ++stacklen;
954                 stnodes[stacklen-1] = stnodes[stacklen-2];
955                 stnodes[stacklen-2] = stnodes[stacklen-3];
956                 stnodes[stacklen-3] = stnodes[stacklen-1];
957                 break;
958             /*
959              * dup_x1: Duplicate the top element, and insert
960              * down past the long/double.
961              */
962             case Instruction.OP_DUP_X2:
963                 if (stnodes[stacklen-2].type().category() == 2) {
964             //util.sc(stacklen-1); util.sc(stacklen-2); 
965                     ++stacklen;
966                     stnodes[stacklen-1] = stnodes[stacklen-2];
967                     stnodes[stacklen-2] = stnodes[stacklen-3];
968                     stnodes[stacklen-3] = stnodes[stacklen-1];
969                 } else {
970             //util.sc(stacklen-1); util.sc(stacklen-2); util.sc(stacklen-3);
971                     ++stacklen;
972                     stnodes[stacklen-1] = stnodes[stacklen-2];
973                     stnodes[stacklen-2] = stnodes[stacklen-3];
974                     stnodes[stacklen-3] = stnodes[stacklen-4];
975                     stnodes[stacklen-4] = stnodes[stacklen-1];
976                 }
977                 break;
978             /*
979              * dup2_x1: Duplicate the top long/double,
980              * and insert it down one in the stack.
981              */
982             case Instruction.OP_DUP2_X1:
983                 // If the top is a long/double, dup_x1, else, dup2_x1
984                 if (stnodes[stacklen-1].type().category() == 2) {
985             //util.sc(stacklen-1); util.sc(stacklen-2); 
986                     ++stacklen;
987                     stnodes[stacklen-1] = stnodes[stacklen-2];
988                     stnodes[stacklen-2] = stnodes[stacklen-3];
989                     // and now duplicate the top entry.
990                     stnodes[stacklen-3] = stnodes[stacklen-1];
991                 } else {
992             //util.sc(stacklen-1); util.sc(stacklen-2); util.sc(stacklen-3); 
993                     stacklen +=2;
994                     stnodes[stacklen-1] = stnodes[stacklen-3];
995                     stnodes[stacklen-2] = stnodes[stacklen-4];
996                     stnodes[stacklen-3] = stnodes[stacklen-5];
997                     // and now duplicate the top entries.
998                     stnodes[stacklen-4] = stnodes[stacklen-1];
999                     stnodes[stacklen-5] = stnodes[stacklen-2];
1000                }
1001
1002                break;
1003            /*
1004             * dup2_x2: Duplicate the top long/double, and
1005             * insert it past the long/double.
1006             */
1007            case Instruction.OP_DUP2_X2:
1008                // Ok, four cases:  Either Top (-1) is a long, or not.
1009                // and the thing(s) being skipped are either long or not.
1010                // Top being long affects the position of next-to-top
1011                if (stnodes[stacklen-1].type().category() == 2) {
1012                    // dup_x2
1013                    if (stnodes[stacklen-2].type().category() == 2) {
1014            //util.sc(stacklen-1); util.sc(stacklen-2); 
1015                        // Life is good.  Dup_x1;
1016                        ++stacklen;
1017                        stnodes[stacklen-1] = stnodes[stacklen-2];
1018                        stnodes[stacklen-2] = stnodes[stacklen-3];
1019                        stnodes[stacklen-3] = stnodes[stacklen-1];
1020                    } else  {
1021            //util.sc(stacklen-1); util.sc(stacklen-2); util.sc(stacklen-3); 
1022                        // dup_x2;
1023                        ++stacklen;
1024                        stnodes[stacklen-1] = stnodes[stacklen-2];
1025                        stnodes[stacklen-2] = stnodes[stacklen-3];
1026                        stnodes[stacklen-3] = stnodes[stacklen-4];
1027                        stnodes[stacklen-4] = stnodes[stacklen-1];
1028                    }
1029                } else {
1030                    if (stnodes[stacklen-3].type().category() == 2) {
1031            //util.sc(stacklen-1); util.sc(stacklen-2); util.sc(stacklen-3); 
1032                        // Dup the top two elements past the long/double
1033                        stacklen += 2;
1034                        // Move everything up
1035                        stnodes[stacklen-1] = stnodes[stacklen-3];
1036                        stnodes[stacklen-2] = stnodes[stacklen-4];
1037                        stnodes[stacklen-3] = stnodes[stacklen-5];
1038                        // And now copy in the top;
1039                        stnodes[stacklen-4] = stnodes[stacklen-1];
1040                        stnodes[stacklen-5] = stnodes[stacklen-2];
1041                    } else {
1042            //util.sc(stacklen-1); util.sc(stacklen-2); 
1043            //util.sc(stacklen-3); util.sc(stacklen-4); 
1044                        // Nothing's a double.
1045                        stacklen += 2;
1046                        // Move everything up
1047                        stnodes[stacklen-1] = stnodes[stacklen-3];
1048                        stnodes[stacklen-2] = stnodes[stacklen-4];
1049                        stnodes[stacklen-3] = stnodes[stacklen-5];
1050                        stnodes[stacklen-4] = stnodes[stacklen-6];
1051                        // And now copy in the top;
1052                        stnodes[stacklen-5] = stnodes[stacklen-1];
1053                        stnodes[stacklen-6] = stnodes[stacklen-2];
1054                    }
1055                }
1056                break;
1057
1058        case Instruction.OP_GETSTATIC:
1059        stnodes[stacklen++] = util.getfield
1060            (instr.classRef(), instr.elemName(), instr.type(), null);
1061        //util.addOrdered ( stnodes[stacklen++] );
1062        break;
1063
1064        case Instruction.OP_PUTSTATIC:
1065        n = util.addOrdered(util.setfield 
1066            (instr.classRef(), instr.elemName(), instr.type(), null, 
1067             stnodes[--stacklen])/*.require()*/);
1068        senodes.add (n);
1069        break;
1070
1071        case Instruction.OP_GETFIELD:
1072        util.sc(stacklen-1);
1073        stnodes[stacklen-1] = util.getfield 
1074            (instr.classRef(), instr.elemName(), instr.type(), 
1075             stnodes[stacklen-1]);
1076        //util.addOrdered(stnodes[stacklen-1]);     
1077        break;
1078
1079        case Instruction.OP_PUTFIELD:
1080        util.sc(stacklen-1); util.sc(stacklen-2);
1081        stacklen-=2;
1082        n = util.addOrdered(util.setfield 
1083            (instr.classRef(), instr.elemName(), instr.type(),
1084             stnodes[stacklen], stnodes[stacklen+1])/*.require()*/);
1085        senodes.add (n);
1086        break;
1087
1088        case Instruction.OP_NEW:
1089        stnodes[stacklen] = util.node( new Node.New (instr.classRef()) );
1090        stnodes[stacklen++].sb = this;
1091        break;
1092
1093        case Instruction.OP_CHECKCAST:
1094        case Instruction.OP_INSTANCEOF:
1095        util.sc(stacklen-1);
1096        stnodes[stacklen-1] = util.Cast
1097            (instr.classRef(), stnodes[stacklen-1], op == Instruction.OP_CHECKCAST);
1098        break;
1099
1100        default:
1101        throw new IllegalStateException   ("unsupported opcode " +
1102                                                instr.recString(false));
1103        } // switch(op)
1104
1105        if (stacklen>0 && stnodes[stacklen-1].serial == 0)
1106        db.setNode(stnodes[stacklen-1]);
1107
1108    } // for instr
1109
1110    if (in.es.op == Instruction.OP_JSR) {
1111        Node.ret ret = new Node.ret(null);
1112        ret.sb = this;
1113        stnodes[stacklen++] = ret;
1114    }
1115
1116    if (in.es.op == Instruction.OP_RET) { 
1117        esnodes = new Node[1];
1118        esnodes[0] = lonodes[in.es.retlvt];
1119    } else if (in.es.stackuse < 0) {
1120        esnodes = new Node[0];
1121    } else { 
1122        esnodes = new Node [ in.es.stackuse ];
1123        for (int i = 0; i < in.es.stackuse; i++)
1124        esnodes[i] = stnodes[stacklen-in.es.stackuse + i];
1125        stacklen -= in.es.stackuse;
1126    }
1127
1128    for (int i = 0; i < lonodes.length; i++) { 
1129        Node n = lonodes[i];
1130        if (n==null) continue;
1131        if (n instanceof Node.var && ((Node.var)n).v==i) continue;
1132        outnodes.addElement(new Node.assign (i, n, this));
1133    }
1134
1135    for (int i = 0; i < /*stnodes.length*/ stacklen; i++) { 
1136        Node n = stnodes[i];
1137        if (n==null) continue;
1138        if (n instanceof Node.var && ((Node.var)n).v==(-i-1)) continue;
1139        outnodes.addElement(new Node.assign (-i-1, n, this));
1140    }
1141
1142    outputs = (Node[]) outnodes.toArray (new Node[0]);
1143
1144    Collection h = findnodes();
1145
1146    for (Iterator i = h.iterator(); i.hasNext();) { 
1147        Object   o = i.next();
1148        if (o instanceof Node.var)
1149        innodes.addElement(o);
1150    }   
1151
1152    inputs = (Node.var[]) innodes.toArray (new Node.var[0]);
1153    }
1154
1155    /** Construct a placeholder for a label. 
1156     * @param n a label node
1157     */
1158    BasicBlock (Node.Label n) {
1159    esnodes = new Node[1];
1160    esnodes[0] = n;
1161    outputs = inputs = new Node.var[0];
1162    es = new ExitRec();
1163    es.op = Instruction.AOP_LABEL;
1164    senodes = InternSet.EMPTY;
1165
1166    n.swvalb = this;
1167    }
1168
1169    /** Partial copy "constructor"
1170     * Called by DagRep.obfuscate on each BasicBlock of a method.
1171     * @param bb an input BasicBlock
1172     * @return a copy of the input, with no Nodes
1173     */
1174    public static BasicBlock partialCopy(BasicBlock bb) {
1175    BasicBlock copy = new BasicBlock();
1176
1177    copy.handler = bb.handler;
1178    copy.bname = bb.bname;
1179    copy.swvaln = bb.swvaln;
1180    copy.es = new Block.ExitRec();
1181    return copy;
1182    }
1183
1184    // Follow the "requires" chain for a Node.
1185    static void findnodes (Vector visited, Node n) {
1186    for (int i = 0; i < visited.size(); i++) // this is because of duplicate elimination
1187        if (visited.elementAt (i) == n)
1188        return;
1189
1190    visited.addElement (n);
1191
1192    for (int i = 0; i < n.numParams(); i++) try {
1193        findnodes (visited, (Node) n.requires.elementAt(i));
1194    } catch (RuntimeException   e) {
1195        /*
1196        Jbet.error.println ("findnodes failed for " + n);
1197        for (int j = 0; j < n.numParams(); j++)
1198        Jbet.error.println ("  " + n.requires.elementAt (j)); 
1199        */
1200        throw e;
1201    }
1202    }
1203
1204    // Search senodes, outputs, and esnodes.
1205    void findnodes (Vector visited) { 
1206    for (Iterator i = senodes.iterator(); i.hasNext();)
1207        findnodes(visited, (Node) i.next());
1208
1209    for (int i = 0; i < outputs.length; i++)
1210        findnodes(visited, outputs[i]);
1211
1212    for (int i = 0; i < esnodes.length; i++)
1213        findnodes(visited, esnodes[i]);
1214    }
1215
1216    /** Find all used nodes.
1217     * visit all nodes 
1218     * in the block whose value is used.
1219     * @return a Collection of Nodes, 
1220     *         that one can access by making an iterator over.
1221     */
1222    public Collection findnodes() { 
1223    Vector allnodes = new Vector();
1224    findnodes(allnodes);
1225    return allnodes;
1226    }
1227
1228    public BasicBlock any (Random values) {
1229    if (alternates == null)
1230        return this;
1231
1232    int a = values.nextInt (alternates.size() + 1);
1233
1234    if (a == alternates.size())
1235        return this;
1236    else
1237        return (BasicBlock)alternates.elementAt (a);
1238    }
1239
1240    public void addAlternate (BasicBlock other) {
1241    if (alternates == null)
1242        alternates = new Vector();
1243    alternates.addElement (other);
1244    }
1245
1246    /* Make a new basic block containing only the exit instructions for this block.
1247       Any values needed by the exit instructions become outputs in the original block, if they
1248       were not already. The original block retains all the computations. */
1249    public BasicBlock split ()
1250    {
1251    boolean[] esout = new boolean [esnodes.length];
1252    int no = 0;
1253    Node.var[] newins = new Node.var[esnodes.length];
1254
1255    // allocate var nodes for new block
1256    // put esnodes into outputs if not already there
1257    for (int i = 0; i < esnodes.length; i++) {
1258        newins[i] = new Node.var (1000 + i, esnodes[i].type());
1259
1260        for (int j = 0; j < outputs.length; j++)
1261        if (esnodes[i].equals (outputs[j])) {
1262            esout[i] = true;
1263        }
1264
1265        if (!esout[i])
1266        no++;
1267
1268        esnodes[i].addDestination (newins[i]);
1269        newins[i].producers.add (esnodes[i]);
1270    }
1271
1272    // make new output array if necessary
1273    if (no > 0) {
1274        Node[] newout = new Node[outputs.length + no];
1275
1276        for (int i = 0; i < outputs.length; i++)
1277        newout[i] = outputs[i];
1278        for (int i = 0; i < esout.length; i++)
1279        if (!esout[i])
1280            newout[outputs.length+--no] = esnodes[i];
1281
1282        outputs = newout;
1283    }
1284
1285    BasicBlock b = new BasicBlock (0, 0, esnodes.length);
1286    b.inputs = newins;
1287    for (int i = 0; i < newins.length; i++) {
1288        b.esnodes[i] = newins[i];
1289        b.esnodes[i].sb = b;
1290    }
1291
1292    b.es = es;
1293    es = new ExitRec();
1294    es.op = 0;
1295    es.primary = b;
1296    return b;
1297    }
1298
1299    /** Display a block on the output stream.
1300     * @param out stream to write
1301     * @param printcode true to print the code
1302     */
1303    public void printinfo (LineWriter out, boolean printcode) {
1304    if (es.op == Instruction.AOP_LABEL)
1305        return;
1306
1307    out.println ("block " + swval + (bname != null ? ' ' + bname + ' ': "") + 
1308             ' ' + Util.flags2str (blflags, Block.Blc_flags));
1309
1310    if (pred != null) {
1311        StringBuffer   ps = new StringBuffer   ("  predecessors:");
1312        for (int i = 0; i < pred.size(); i++) {
1313        ps.append (" #B");
1314        ps.append (((Block) pred.elementAt (i)).swval);
1315        }
1316        out.println (ps);
1317    }
1318
1319    if (handler != null) 
1320        out.println("  handles: " + handler);
1321
1322    if ((enflags & Block.En_jsr) != 0)
1323        out.println("  jsr target");
1324
1325    
1326    out.print("  inputs: ");
1327    for (int i = 0; i < inputs.length; i++) {
1328        out.print (inputs[i]);
1329        if (i+1 < inputs.length) out.print(", ");
1330    }
1331    out.println();
1332
1333    Node []arr = order();
1334    
1335    for (int i = 0; i < arr.length; i++) {
1336
1337        if (arr[i] instanceof Node.Label) {
1338        out.println (" " + arr[i]);
1339        continue;
1340        }
1341
1342        boolean isoutput = false;
1343        for (int j = 0; j < outputs.length; j++)
1344        if (outputs[j] == arr[i]) { 
1345            isoutput = true; 
1346            break;
1347        }
1348        
1349        if (isoutput && senodes.contains(arr[i]))
1350        out.println ("  se,output: " + arr[i].destinationString() + " = " 
1351                 + arr[i]);
1352        else if (isoutput)
1353        out.println ("  output:    " + arr[i].destinationString() + " = " 
1354                 + arr[i]);
1355
1356        else if (senodes.contains(arr[i]))
1357        out.println ("  se:        " + arr[i]);
1358    }
1359
1360
1361    int n = es.stackuse;
1362
1363    if (es.role != 0)
1364        out.println ("  role: " + Block.Erol_names [es.role]);
1365
1366    if (es.op == Instruction.AOP_NONE) {
1367        ;
1368    } else if  (es.op == 0 && es.primary != null) {
1369        out.println ("  exit: goto #B" + es.primary.swval);
1370    } else if (es.op == Instruction.OP_TABLESWITCH) {
1371        out.println ("  exit: tableswitch  " + esnodes[0]);
1372        if (es.primary != null) 
1373        out.println ("    default: #B" + es.primary.swval);
1374        for (int i = 0; i < es.switches.length; i++) 
1375        out.println ("     " + (i+es.swofs) + " -> #B" + 
1376                 es.switches[i].block.swval);
1377
1378    } else if (es.op == Instruction.OP_LOOKUPSWITCH) {
1379        out.println ("  exit: lookupswitch  " + esnodes[0]);
1380        if (es.primary != null) 
1381        out.println ("    default: #B" + es.primary.swval);
1382        for (int i = 0; i < es.switches.length; i++) 
1383        out.println ("     " + es.switches[i].key + " -> #B" + 
1384                 es.switches[i].block.swval);
1385
1386    } else if (es.op == Instruction.OP_RET) {
1387        out.println ("  exit: " + es.exflags2str(es.exflags) + " ret " + 
1388               esnodes[0]);
1389    } else if (es.op == Instruction.OP_JSR) {
1390        out.println ("  exit: " + es.exflags2str(es.exflags) + " jsr #B" + 
1391               es.primary.swval + " then #B" + es.ret.swval);
1392    } else if (es.op == Instruction.AOP_GOTOBLK) {
1393        out.print ("  exit: " + es.exflags2str(es.exflags) + "gotoblock");
1394        for (int i = 0; i < esnodes.length; i++)
1395        out.print (" " + esnodes[i]);
1396        out.println();
1397    } else if (es.op == Instruction.AOP_LABEL) {
1398        out.println ("  (label placeholder)");
1399    } else if (es.op != 0) {
1400        out.print ("  exit: " + es.exflags2str(es.exflags) + 
1401               Instruction.mnemonics[es.op]);
1402        if (es.jump != null) 
1403        out.print (" #B" + es.jump.swval);
1404        if (es.primary != null) 
1405        out.print (" else #B" + es.primary.swval);
1406
1407        for (int i = 0; i < esnodes.length; i++)
1408        out.print (" " + esnodes[i]);
1409        out.println();
1410    }
1411
1412    if (es.exceptions != null) {
1413        out.println ("  Exceptions:");
1414        for (int i = 0; i < es.exceptions.size(); i++) {
1415        ExcInfo er = es.exAt (i);
1416
1417        out.println ("   " + er.type + " -> #B" + er.handler.swval);
1418        }
1419    }
1420
1421    //if (db != null) db.print(out);
1422    }
1423    
1424    public void replacees (Vector newes) { 
1425    esnodes = (Node[]) newes.toArray(new Node[newes.size()]);
1426    }
1427
1428    public void setGotoBlk (Node n) {
1429    esnodes = new Node[1];
1430    esnodes[0] = n;
1431    es.op = Instruction.AOP_GOTOBLK;
1432    es.jump = es.primary = null;
1433    es.switches = null;
1434    }
1435
1436    public void replace (Hashtable subs, Node.SubMethod sm) throws Throwable   {
1437    boolean change = true;
1438    while (change) {
1439        change = false;
1440    final Collection cin = findnodes ();
1441    final Hashtable  map = new Hashtable();
1442    InternSet oldse = new InternSet (senodes);
1443    senodes = new InternSet ();
1444
1445    class _util {
1446        Node sub (Node in) {
1447        Object   o = map.get (in);
1448        if (o != null)
1449            return (Node) o;
1450        return in;
1451        }
1452    } _util util = new _util();
1453
1454    // do replacement on individual nodes
1455    for (Iterator i = cin.iterator(); i.hasNext(); ) {
1456        Node in = (Node) i.next();
1457        Node out = in.replace (subs, sm, false);
1458
1459        if (out == null)
1460        throw new IllegalStateException   ("replace on " + in + " failed");
1461
1462        if (in != out)
1463        change = true;
1464
1465        map.put (in, out);
1466    }
1467
1468    // fix links in new nodes
1469    for (Iterator i = cin.iterator(); i.hasNext(); ) {
1470        Node old = (Node) i.next();
1471        Node n = (Node) map.get (old);
1472
1473        if (n == null) {
1474        Jbet.output.println ("allnodes:");
1475        for (Iterator i2 = cin.iterator(); i2.hasNext(); )
1476            Jbet.output.println ("    " + i2.next());
1477
1478        Jbet.output.println ("WARNING: node " + old + " not in original list");
1479        n = old;
1480        }
1481
1482        if (n != old) {
1483        // fix param links
1484        for (int j = n.numParams(); j < /*n.numParams()*/n.requires.size(); j++) {
1485            Node old2 = n.usesAt(j);
1486            n.requires.setElementAt (util.sub (n.usesAt (j)), j);
1487        }
1488
1489        // require old things too
1490        for (int j = old.numParams(); j < old.requires.size(); j++) {
1491            Node req = util.sub (old.usesAt (j));
1492            n.require (req);
1493        }
1494        }
1495        else
1496        for (int j = 0/*old.numParams()*/; j < old.requires.size(); j++) {
1497            n.requires.setElementAt (util.sub (old.usesAt (j)), j);
1498        }
1499    }
1500
1501    // fix requirements in all new nodes
1502    Collection cin2 = findnodes();
1503
1504    for (Iterator i = cin2.iterator(); i.hasNext(); ) {
1505        Node n = (Node) i.next();
1506
1507        for (int j = n.numParams(); j < /*n.numParams()*/n.requires.size(); j++) {
1508        Node old2 = n.usesAt(j);
1509        n.requires.setElementAt (util.sub (n.usesAt (j)), j);
1510        }
1511    }
1512
1513    for (int i = 0; i < outputs.length; i++) {
1514        Node orig = outputs[i];
1515        outputs[i] = util.sub (outputs[i]);
1516        if (outputs[i] == null)
1517        throw new IllegalStateException   ("replace returned null for " + orig);
1518    }
1519
1520    for (Iterator i = oldse.iterator(); i.hasNext(); ) {
1521        Node se = util.sub ((Node) i.next());
1522        senodes.add (se);
1523    }
1524
1525    for (int i = 0; i < esnodes.length; i++)
1526        esnodes[i] = util.sub (esnodes[i]);
1527    }
1528    }
1529
1530    /* Replace with different exception specifications */
1531
1532    public void replace_cfe (Hashtable subs, Node.SubMethod sm) throws ClassFileException
1533    {
1534    try {
1535        replace (subs, sm);
1536    }
1537    catch (ClassFileException e) { throw e; }
1538    catch (Throwable   e) { throw new IllegalStateException   (e.getMessage ()); }
1539    }
1540
1541    /* If nonnull, add a node to the end of exorder. */
1542
1543    public void addExnode (Node ex)
1544    {
1545    if (ex != null) {
1546        ex.require (new HashSet (senodes));
1547        senodes.add (ex);
1548
1549        if (ex.esneed) {
1550        Node[] newex = new Node[1+esnodes.length];
1551
1552        for (int i = 0; i < esnodes.length; i++)
1553            newex[i] = esnodes[i];
1554        newex[esnodes.length] = ex;
1555        esnodes = newex;
1556        }
1557    }
1558    }
1559
1560    /* add a node to outputs, unless it has no destinations or is already in outputs. */
1561
1562    public void addOutput (Node ex)
1563    {
1564    if (ex.destinations != null) {
1565        for (int i = 0; i < outputs.length; i++)
1566        if (ex.equals (outputs[i]))
1567            return;
1568        
1569        Node[] newex = new Node[1+outputs.length];
1570
1571        for (int i = 0; i < outputs.length; i++)
1572            newex[i] = outputs[i];
1573        newex[outputs.length] = ex;
1574        outputs = newex;
1575    }
1576    }
1577    
1578    /* assumes that there are no duplicates */
1579    boolean doesPathExist(final Node start, final Set end) { 
1580    if (start == Node.EXIT) return true;
1581
1582    final HashSet visited = new HashSet();
1583    
1584    class _util { 
1585        boolean dpe (Node n) { 
1586        if (end.contains(n))  
1587            return true;
1588        if ( visited.contains(n) )
1589            return false;
1590        visited.add(n);
1591        for (int i = 0; i < n.requires.size(); i++) 
1592            if (dpe(n.usesAt(i)))
1593            return true;
1594        return false;
1595        }
1596    }
1597    _util util = new _util();
1598    return util.dpe(start);
1599    }
1600
1601    void doRefCount() { 
1602    Collection allnodes = findnodes();
1603    for (Iterator i = allnodes.iterator(); i.hasNext(); ) { 
1604        Node n = (Node) i.next();
1605        n.count = 0;
1606    }
1607    for (Iterator i = allnodes.iterator(); i.hasNext(); ) { 
1608        Node n = (Node) i.next();
1609        for (int j = 0; j < n.numParams(); j++)
1610        n.usesAt(j).count++;
1611    }
1612    for (int i = 0; i < esnodes.length; i++)
1613        esnodes[i].count++;
1614    }
1615
1616    
1617    /* put all the nodes in this basic block in order for code generation */
1618    Node [] order() { 
1619    //Jbet.output.println (" ====================== O R D E R ================= " + swval);
1620    //printinfo(Jbet.output, true);
1621    //Jbet.output.println ("======================");
1622    
1623    /* Remove duplicates */
1624    final Hashtable subs = new Hashtable();
1625    try {
1626        replace (subs, new Node.SubMethod() {
1627            public Node f (Node in) {
1628            Object   o = subs.get (in);
1629            if (o != null) {
1630                return (Node) o;
1631            }
1632
1633            subs.put (in, in);
1634            return in;
1635            }
1636        });
1637    } catch (Throwable   e) { throw new IllegalStateException   (e.toString ()); }
1638
1639    final Collection allnodes = findnodes();
1640
1641    HashSet all2 = new HashSet ();
1642    all2.addAll (allnodes);
1643
1644    if (all2.size() != allnodes.size()) {  
1645        /* this code should never be reached.  It's a check that
1646               equals() and hashcode() are properly implemented */
1647        for (Iterator i = all2.iterator(); i.hasNext(); ) {
1648        int n = 0;
1649        Object   io = i.next();
1650        Vector v = new Vector();
1651        for (int j = 0; j < allnodes.size(); j++)
1652            if (((Vector)allnodes).elementAt (j).equals (io)) {
1653            v.addElement (((Vector)allnodes).elementAt (j));
1654            n++;
1655            }
1656
1657        if (n != 1) {
1658            Jbet.output.println ("** " + io + " : " + n);
1659            for (int k = 0; k < v.size(); k++)
1660            Jbet.output.println (" + " + v.elementAt(k) + "   " + ((Node)v.elementAt(k)).objectHashCode());
1661        }
1662        }
1663
1664        throw new IllegalStateException   ("sizes are different! " + (allnodes.size()-all2.size()));
1665    }
1666
1667    /* initialize direct_user and users elements of Node */ 
1668    for (Iterator i = allnodes.iterator(); i.hasNext();)
1669        ((Node)i.next()).users = new HashSet();
1670
1671    for (Iterator i = allnodes.iterator(); i.hasNext();) { 
1672        Node n = (Node) i.next();
1673        for (int j = 0; j < n.numParams(); j++)
1674        n.usesAt(j).users.add(n);
1675        //n.direct_user = null;
1676        n.hasDirectUsers = false;
1677        n.hasIndirectUsers = false;
1678    }
1679    for (int i = 0; i < esnodes.length; i++)
1680        esnodes[i].users.add(Node.EXIT);
1681
1682    final Vector ret = new Vector();
1683    final HashSet notvisited = new HashSet ();
1684    final HashSet currentnodes = new HashSet();
1685
1686    class _util { 
1687        int j = 0; 
1688        int depth = 0;
1689
1690        /* only used for debugging order */
1691        void println(String   s) { 
1692        if (false) {
1693            Jbet.output.print("__");
1694            for (int i = 0; i < depth; i += 2) Jbet.output.print(". ");
1695            Jbet.output.println(s);
1696        }
1697
1698        }
1699        void in() { depth += 2; }
1700        void out() {depth -= 2; }
1701        
1702        /* this is a depth first search of the dag.  each time it traverses a node 
1703         * for the first time emits it.  It returns true iff n is emited.  */
1704        boolean traverse (Node n) {  
1705        if (currentnodes.contains(n)) throw new IllegalStateException  
1706            ("CYCLE!!!!");
1707        currentnodes.add(n);
1708        try {
1709            
1710            if (! allnodes.contains(n)) { 
1711            /* if we have 3 nodes a, b, c with c depends on b and b depends on a
1712             * and b is removed as a duplicate node, we still need to traverse
1713             * b so that we still know that c depends on a */
1714            println("Tr: " + n + ", EXTRANIOUS"); 
1715            for (int k = n.numParams(); k < n.requires.size(); k++) 
1716                traverse((Node) n.requires.elementAt(k));
1717            return false; 
1718            }
1719            if (!notvisited.contains(n) && !(n instanceof Node.constant)) { 
1720            println("Tr: " + n + ", BEENHERE"); 
1721            return false; 
1722            }
1723            println("Tr: " + n);
1724            in();
1725            try { 
1726            int sz = notvisited.size();
1727            notvisited.remove(n);
1728            if (!(n instanceof Node.constant) && sz==notvisited.size())
1729                throw new IllegalStateException   
1730                (n.getClass().getName() + 
1731                 " does not implement hashcode correctly");
1732            MYLOOP:
1733            for (int k = n.numParams();;) {
1734                if (k == n.requires.size()) 
1735                if (n.numParams() == 0) break;
1736                else {
1737                    println("-----");
1738                    k=0;
1739                }
1740                
1741                Node r = n.usesAt(k);
1742
1743                if (k >= n.numParams() && r != null && r.users != null)
1744                for (Iterator l = r.users.iterator(); 
1745                     l.hasNext();) { 
1746                    Node u = (Node) l.next();
1747                    if (notvisited.contains(u) && !doesPathExist
1748                    (u, currentnodes)) {
1749                    println ("BACK " + r + " ----- " + u);
1750                    traverse(u);
1751                    continue MYLOOP;
1752                    }
1753                }
1754                boolean emmited = traverse(r);
1755                if (k < n.numParams())
1756                if (emmited) {
1757                    r.hasDirectUsers = true;
1758                    println ("DIRECT");
1759                } else {
1760                    /* we don't caclulate any node twice, so if it needs to be used twice codegen
1761                     * will save it to a register.  This marker tells codegen when to load that register
1762                     */
1763                    emit( new Node.LoadMarker(r) );
1764                    r.hasIndirectUsers = true;
1765                    println ("LOAD");
1766                }
1767
1768                if (k==0 && n.isinit())
1769                emit( new Node.DupMarker() );
1770
1771                k++;
1772                if (k == n.numParams()) break;
1773            }
1774            println("write " + j + " " + n);
1775            emit(n);
1776            return true;
1777            } finally { out(); }
1778        
1779        } finally { currentnodes.remove(n); }
1780        }
1781        void emit(Node n) { 
1782        n.number = j;
1783        j++;
1784        ret.addElement(n);
1785        }       
1786    }
1787    _util util = new _util();
1788
1789    for (Iterator i = allnodes.iterator(); i.hasNext();) { 
1790        Object   o = i.next();
1791        util.println("AN " + o);
1792        notvisited.add(o);
1793    }
1794
1795    if (es.op != Instruction.OP_RET)
1796        for (int i = 0; i < esnodes.length; i++) {
1797        boolean emmited = util.traverse( esnodes[i] );
1798        if (emmited)
1799            esnodes[i].hasDirectUsers = true;
1800        else {
1801            util.emit( new Node.LoadMarker(esnodes[i]) );
1802            esnodes[i].hasIndirectUsers = true;
1803        }
1804        }
1805
1806    while (! notvisited.isEmpty()) { 
1807        if (! notvisited.contains(notvisited.iterator().next())) {
1808        throw new IllegalStateException  ("implement hashcode correctly! " + swval);
1809        }
1810        util.println("ORDERLOOP "  + notvisited.size());
1811        util.in();
1812        for (Iterator i = notvisited.iterator(); i.hasNext();)
1813        util.println("NV " + ((Node)i.next()).users);
1814
1815        Node next;
1816        for (next = (Node) notvisited.iterator().next(); 
1817         next.users.size() != 0 && next.users.iterator().next() != Node.EXIT;
1818         next = (Node) next.users.iterator().next())
1819        ;
1820
1821        util.traverse(next);
1822        util.out();
1823    }
1824
1825    Node[] reta = (Node[]) ret.toArray( new Node [0] );
1826
1827    /* Move nodes inserted between a goto and label to after the label */
1828    boolean change = true;
1829    while (change) {
1830        change = false;
1831        for (int i = 0; i < reta.length-1; i++)
1832        if (reta[i] instanceof Node.Goto &&
1833            !(reta[i+1] instanceof Node.Label)) {
1834            int j;
1835            for (j = i+2; i < reta.length; j++)
1836            if (reta[j] instanceof Node.Label)
1837                break;
1838            if (j == reta.length)
1839            throw new IllegalStateException   ("no label for a goto");
1840
1841            Node label = reta[j];
1842
1843            for (int k = j-1; k > i; k--)
1844            reta[k+1] = reta[k];
1845            reta[i+1] = label;
1846            change = true;
1847            break;
1848        }
1849    }
1850    return reta;
1851    } // order
1852
1853    /* renumber a vector of blocks */
1854
1855    static void renumber (Vector bbs)
1856    {
1857    for (int i = 0; i < bbs.size(); i++) {
1858        BasicBlock sb = (BasicBlock)(bbs.elementAt (i));
1859        sb.swval = i+1;
1860        if (sb.es.op == Instruction.AOP_LABEL) {
1861        Node.Label la = (Node.Label)(sb.esnodes[0]);
1862        la.swvaln.i = i+1;
1863        }
1864        if (sb.swvaln != null)
1865        sb.swvaln.i = sb.swval;
1866    }
1867    }
1868} 
1869
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags