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             if (fn.kind()==FKind.FlatCondBranch&&((FlatCondBranch)fn).isLoopBranch()) {
  44                 FlatCondBranch fcb=(FlatCondBranch)fn;
  45                 loopbranchset.add(fcb);
  46                 //True edge
  47                 propagateset(nodeset, table, fcb, fcb.getNext(0), fcb);
  48                 //False edge
  49                 propagateset(nodeset, table, fcb, fcb.getNext(1), null);
  50                 loopbranchset.add(fcb);
  51             } else if (fn.kind()==FKind.FlatReturnNode) {
  52                 exitset.addAll(table.get(fn));
  53             } else {
  54                 for(int i=0;i<fn.numNext();i++)
  55                     propagateset(nodeset, table, fn, fn.getNext(i), null);
  56             }
  57         }
  58         loopbranchset.removeAll(exitset);
  59         results.put(md, loopbranchset);
  60     }
  61
  62     void propagateset(Set<FlatNode> tovisit, Hashtable<FlatNode, Set<FlatCondBranch>> table, FlatNode fn, FlatNode fnnext, FlatCondBranch fcb) {
  63         boolean enqueuechange=false;
  64         if (table.containsKey(fn)) {
  65             if (!table.containsKey(fnnext))
  66                 table.put(fnnext, new HashSet<FlatCondBranch>());
  67             if(!table.get(fnnext).containsAll(table.get(fn))) {
  68                 table.get(fnnext).addAll(table.get(fn));
  69                 enqueuechange=true;
  70             }
  71         }
  72         if (fcb!=null) {
  73             if (!table.containsKey(fnnext))
  74                 table.put(fnnext, new HashSet<FlatCondBranch>());
  75             if (!table.get(fnnext).contains(fcb)) {
  76                 table.get(fnnext).add(fcb);
  77                 enqueuechange=true;
  78             }
  79         }
  80         if (enqueuechange)
  81             tovisit.add(fnnext);
  82     }
  83
  84 }