loop exit detection

[IRC.git] / Robust / src / Analysis / Prefetch / LoopExit.java

diff --git a/Robust/src/Analysis/Prefetch/LoopExit.java b/Robust/src/Analysis/Prefetch/LoopExit.java
new file mode 100644 (file)
index 0000000..d116741
--- /dev/null
+++ b/Robust/src/Analysis/Prefetch/LoopExit.java
@@ -0,0 +1,84 @@
+package Analysis.Prefetch;
+
+import java.util.*;
+import IR.SymbolTable;
+import IR.State;
+import IR.TypeUtil;
+import IR.MethodDescriptor;
+import IR.Flat.*;
+import IR.*;
+import IR.ClassDescriptor;
+
+
+public class LoopExit {
+    State state;
+    Hashtable<MethodDescriptor, Set<FlatCondBranch>> results;
+
+    public LoopExit(State state) {
+       this.state=state;
+       this.results=new Hashtable<MethodDescriptor, Set<FlatCondBranch>>();
+    }
+
+    public Set<FlatCondBranch> getLoopBranches(MethodDescriptor md) {
+       if (!results.containsKey(md))
+           doAnalysis(md);
+       return results.get(md);
+    }
+
+    public boolean isLoopingBranch(MethodDescriptor md, FlatCondBranch fcb) {
+       return getLoopBranches(md).contains(fcb);
+    }
+
+    private void doAnalysis(MethodDescriptor md) {
+       FlatMethod fm=state.getMethodFlat(md);
+       HashSet<FlatNode> nodeset=new HashSet<FlatNode>();
+       nodeset.addAll(fm.getNodeSet());
+       Hashtable<FlatNode, Set<FlatCondBranch>> table=new Hashtable<FlatNode, Set<FlatCondBranch>>();
+
+       HashSet<FlatCondBranch> loopbranchset=new HashSet<FlatCondBranch>();
+       HashSet<FlatCondBranch> exitset=new HashSet<FlatCondBranch>();
+       
+       while(!nodeset.isEmpty()) {
+           FlatNode fn=nodeset.iterator().next();
+           if (fn.kind()==FKind.FlatCondBranch&&((FlatCondBranch)fn).isLoopBranch()) {
+               FlatCondBranch fcb=(FlatCondBranch)fn;
+               loopbranchset.add(fcb);
+               //True edge
+               propagateset(nodeset, table, fcb, fcb.getNext(0), fcb); 
+               //False edge
+               propagateset(nodeset, table, fcb, fcb.getNext(1), null); 
+               loopbranchset.add(fcb);
+           } else if (fn.kind()==FKind.FlatReturnNode) {
+               exitset.addAll(table.get(fn));
+           } else {
+               for(int i=0;i<fn.numNext();i++)
+                   propagateset(nodeset, table, fn, fn.getNext(i), null); 
+           }
+       }
+       loopbranchset.removeAll(exitset);
+       results.put(md, loopbranchset);
+    }
+
+    void propagateset(Set<FlatNode> tovisit, Hashtable<FlatNode, Set<FlatCondBranch>> table, FlatNode fn, FlatNode fnnext, FlatCondBranch fcb) {
+       boolean enqueuechange=false;
+       if (table.containsKey(fn)) {
+           if (!table.containsKey(fnnext))
+               table.put(fnnext, new HashSet<FlatCondBranch>());
+           if(!table.get(fnnext).containsAll(table.get(fn))) {
+               table.get(fnnext).addAll(table.get(fn));
+               enqueuechange=true;
+           }
+       }
+       if (fcb!=null) {
+           if (!table.containsKey(fnnext))
+               table.put(fnnext, new HashSet<FlatCondBranch>());
+           if (!table.get(fnnext).contains(fcb)) {
+               table.get(fnnext).add(fcb);
+               enqueuechange=true;
+           }
+       }
+       if (enqueuechange)
+           tovisit.add(fnnext);
+    }
+
+}