Robust/src/Analysis/Prefetch/LoopExit.java

   1 package Analysis.Prefetch;
   2
   3 import java.util.*;
   4 import IR.SymbolTable;
   5 import IR.State;
   6 import IR.TypeUtil;
   7 import IR.MethodDescriptor;
   8 import IR.Flat.*;
   9 import IR.*;
  10 import IR.ClassDescriptor;
  11
  12
  13 public class LoopExit {
  14     State state;
  15     Hashtable<MethodDescriptor, Set<FlatCondBranch>> results;
  16
  17     public LoopExit(State state) {
  18         this.state=state;
  19         this.results=new Hashtable<MethodDescriptor, Set<FlatCondBranch>>();
  20     }
  21
  22     public Set<FlatCondBranch> getLoopBranches(MethodDescriptor md) {
  23         if (!results.containsKey(md))
  24             doAnalysis(md);
  25         return results.get(md);
  26     }
  27
  28     public boolean isLoopingBranch(MethodDescriptor md, FlatCondBranch fcb) {
  29         return getLoopBranches(md).contains(fcb);
  30     }
  31
  32     private void doAnalysis(MethodDescriptor md) {
  33         FlatMethod fm=state.getMethodFlat(md);
  34         HashSet<FlatNode> nodeset=new HashSet<FlatNode>();
  35         nodeset.addAll(fm.getNodeSet());
  36         Hashtable<FlatNode, Set<FlatCondBranch>> table=new Hashtable<FlatNode, Set<FlatCondBranch>>();
  37
  38         HashSet<FlatCondBranch> loopbranchset=new HashSet<FlatCondBranch>();
  39         HashSet<FlatCondBranch> exitset=new HashSet<FlatCondBranch>();
  40
  41         while(!nodeset.isEmpty()) {
  42             FlatNode fn=nodeset.iterator().next();
  43             nodeset.remove(fn);
  44             if (fn.kind()==FKind.FlatCondBranch&&((FlatCondBranch)fn).isLoopBranch()) {
  45                 FlatCondBranch fcb=(FlatCondBranch)fn;
  46                 loopbranchset.add(fcb);
  47                 //True edge
  48                 propagateset(nodeset, table, fcb, fcb.getNext(0), fcb);
  49                 //False edge
  50                 propagateset(nodeset, table, fcb, fcb.getNext(1), null);
  51                 loopbranchset.add(fcb);
  52             } else if (fn.kind()==FKind.FlatReturnNode) {
  53                 if (table.containsKey(fn))
  54                     exitset.addAll(table.get(fn));
  55             } else {
  56                 for(int i=0;i<fn.numNext();i++)
  57                     propagateset(nodeset, table, fn, fn.getNext(i), null);
  58             }
  59         }
  60         loopbranchset.removeAll(exitset);
  61         results.put(md, loopbranchset);
  62     }
  63
  64     void propagateset(Set<FlatNode> tovisit, Hashtable<FlatNode, Set<FlatCondBranch>> table, FlatNode fn, FlatNode fnnext, FlatCondBranch fcb) {
  65         boolean enqueuechange=false;
  66         if (table.containsKey(fn)) {
  67             if (!table.containsKey(fnnext))
  68                 table.put(fnnext, new HashSet<FlatCondBranch>());
  69             HashSet<FlatCondBranch> toadd=new HashSet<FlatCondBranch>();
  70             toadd.addAll(table.get(fn));
  71             if (toadd.contains(fnnext)) //can't propagate back to node
  72                 toadd.remove(fnnext);
  73             if(!table.get(fnnext).containsAll(toadd)) {
  74                 table.get(fnnext).addAll(toadd);
  75                 enqueuechange=true;
  76             }
  77         }
  78         if (fcb!=null) {
  79             if (!table.containsKey(fnnext))
  80                 table.put(fnnext, new HashSet<FlatCondBranch>());
  81             if (!table.get(fnnext).contains(fcb)) {
  82                 table.get(fnnext).add(fcb);
  83                 enqueuechange=true;
  84             }
  85         }
  86         if (enqueuechange)
  87             tovisit.add(fnnext);
  88     }
  89
  90 }