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(fnnext))
  67       table.put(fnnext, new HashSet<FlatCondBranch>());
  68
  69     if (table.containsKey(fn)) {
  70       HashSet<FlatCondBranch> toadd=new HashSet<FlatCondBranch>();
  71       toadd.addAll(table.get(fn));
  72       if (toadd.contains(fnnext))       //can't propagate back to node
  73         toadd.remove(fnnext);
  74       if(!table.get(fnnext).containsAll(toadd)) {
  75         table.get(fnnext).addAll(toadd);
  76         enqueuechange=true;
  77       }
  78     }
  79     if (fcb!=null&&!table.get(fnnext).contains(fcb)) {
  80       table.get(fnnext).add(fcb);
  81       enqueuechange=true;
  82     }
  83     if (enqueuechange)
  84       tovisit.add(fnnext);
  85   }
  86 }