From 24bf6578cdc8b73011242a9371e369dee6e15049 Mon Sep 17 00:00:00 2001
From: bdemsky <bdemsky>
Date: Mon, 30 Mar 2009 18:52:17 +0000
Subject: [PATCH] changes

---
 Robust/src/Analysis/Loops/LoopInvariant.java | 172 +++++++++++++++++++
 Robust/src/Analysis/Loops/LoopOptimize.java  |  18 ++
 2 files changed, 190 insertions(+)
 create mode 100644 Robust/src/Analysis/Loops/LoopInvariant.java
 create mode 100644 Robust/src/Analysis/Loops/LoopOptimize.java

diff --git a/Robust/src/Analysis/Loops/LoopInvariant.java b/Robust/src/Analysis/Loops/LoopInvariant.java
new file mode 100644
index 00000000..db2e2d93
--- /dev/null
+++ b/Robust/src/Analysis/Loops/LoopInvariant.java
@@ -0,0 +1,172 @@
+package Analysis.Loops;
+
+import IR.Flat.*;
+
+public class LoopInvariant {
+  public LoopInvariant(TypeUtil typeutil) {
+    this.typeutil=typeutil;
+  }
+  LoopFinder loops;
+  DomTree posttree;
+  Hashtable<Loops, Set<FlatNode>> table;
+  Set<FlatNode> hoisted;
+  UseDef usedef;
+  TypeUtil typeutil;
+
+  public void analyze(FlatMethod fm) {
+    loops=new LoopFinder(fm);
+    Loops root=loops.getRootLoop(fm);
+    table=new Hashtable<Loops, Set<FlatNode>>();
+    hoisted=new HashSet<FlatNode>();
+    usedef=new UseDef(fm);
+    posttree=new DomTree(fm,true);
+    recurse(root);
+  }
+
+  public void recurse(Loops parent) {
+    processLoop(parent, parent.nestedLoops().size()==0);
+    for(Iterator lpit=parent.nestedLoops().iterator();lpit.hasNext();) {
+      Loops child=(Loops)lpit.next();
+      recurse(child);
+    }
+  }
+
+  public void processLoop(Loops l, boolean isLeaf) {
+    boolean changed=true;
+    boolean unsafe=false;
+    Set elements=l.loopIncElements();
+    Set toprocess=l.loopIncElements();
+    toprocess.removeAll(hoisted);
+
+    HashSet<FieldDescriptor> fields=new HashSet<FieldDescriptor>();
+    HashSet<TypeDescriptor> types=new HashSet<TypeDescriptor>();
+
+    if (!isLeaf) {
+      unsafe=true; 
+    } else {
+      /* Check whether it is safe to reuse values. */
+      for(Iterator elit=elements.iterator();elit.hasNext();) {
+	FlatNode fn=elit.next();
+	if (fn.kind()==FKind.FlatAtomicEnterNode||
+	    fn.kind()==FKind.FlatAtomicExitNode||
+	    fn.kind()==FKind.Call) {
+	  unsafe=true;
+qq	  break;
+	} else if (fn.kind()==FKind.FlatSetFieldNode) {
+	  FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
+	  fields.add(fsfn.getField());
+	} else if (fn.kind()==FKind.FlatSetElementNode) {
+	  FlatSetElementNode fsen=(FlatSetElementNode)fn;
+	  types.add(fsen.getDst().getType());
+	}
+      }   
+    }
+    
+    HashSet dominatorset=computeAlways(l);
+
+    /* Compute loop invariants */
+    table.put(l, new HashSet<FlatNode>());
+    while(changed) {
+      changed=false;
+      nextfn:
+      for(Iterator tpit=toprocess.iterator();tpit.hasNext();) {
+	FlatNode fn=(FlatNode)tpit.next();
+	switch(fn.kind()) {
+	case FKind.FlatOpNode:
+	  int op=((FlatOpNode)fn).getOperation();
+	  if (op==Operation.DIV||op==Operation.MID||
+	      checkNode(fn,elements)) {
+	    continue nextfn;
+	  }
+	  break;
+
+	case FKind.FlatInstanceOfNode:
+	  if (checkNode(fn,elements)) {
+	    continue nextfn;
+	  }
+	  break;
+
+	case FKind.FlatElementNode:
+	  if (unsafe||!dominatorset.contains(fn)||
+	      checkNode(fn,elements))
+	    continue nextfn;
+	  TypeDescriptor td=((FlatElementNode)fn).getSrc().getType();
+	  for(Iterator<TypeDescriptor> tpit=types.iterator();tpit.hasNext();) {
+	    TypeDescriptor td2=tpit.next();
+	    if (typeutil.isSuperorType(td,td2)||
+		typeutil.isSuperorType(td2,td)) {
+	      continue nextfn;
+	    }
+	  }
+	  break;
+
+	case FKind.FlatFieldNode:
+	  if (unsafe||!dominatorset.contains(fn)||
+	      fields.contains(((FlatFieldNode)fn).getField())||
+	      checkNode(fn,elements)) {
+	    continue nextfn;
+	  }
+	  break;
+
+	default:
+	  continue nextfn;
+	}
+	//mark to hoist
+	hoisted.add(fn);
+	table.get(l).add(fn);
+      }
+    }
+  }
+
+  public HashSet computeAlways(Loops l) {
+    /* Compute nodes that are always executed in loop */
+    HashSet dominatorset=null;
+    if (!unsafe) {
+      /* Compute nodes that definitely get executed in a loop */
+      Set entrances=l.loopEntraces();
+      assert entrances.size()==1;
+      FlatNode entrance=(FlatNode)entrances.iterator().next();
+      boolean first=true;
+      for (int i=0;i<entrances.numPrev();i++) {
+	FlatNode incoming=entrence.getPrev(i);
+	if (elements.contains(incoming)) {
+	  HashSet domset=new HashSet();
+	  domset.add(incoming);
+	  FlatNode tmp=incoming;
+	  while(tmp!=entrance) {
+	    tmp=domtree.idom(tmp);
+	    domset.add(tmp);
+	  }
+	}
+	if (first) {
+	  dominatorset=domset;
+	  first=false;
+	} else {
+	  for(Iterator it=dominatorset.iterator();it.hasNext();) {
+	    FlatNode fn=(FlatNode)it.next();
+	    if (!domset.containsKey(fn))
+	      it.remove();
+	  }
+	}
+      }
+    }
+    return dominatorset;
+  }
+
+  public boolean checkNode(FlatNode fn, Set elements) {
+    //Can hoist if all variables are loop invariant
+    TempDescriptor[]uses=fn.readsTemps();
+    for(int i=0;i<uses.length;i++) {
+      TempDescriptor t=uses[i];
+      Set<FlatNode> defset=usedef.defMap(fn, t);
+      for(Iterator<FlatNode> defit=defset.iterator();defit.hasNext();) {
+	FlatNode def=defit.next();
+	if (elements.contains(def)&&defset.size()>1)
+	  return true;
+	if (elements.contains(def)&&!hoisted.contains(def))
+	  return true;
+      }
+    }
+    return false;
+  }
+}
\ No newline at end of file
diff --git a/Robust/src/Analysis/Loops/LoopOptimize.java b/Robust/src/Analysis/Loops/LoopOptimize.java
new file mode 100644
index 00000000..9456ea1e
--- /dev/null
+++ b/Robust/src/Analysis/Loops/LoopOptimize.java
@@ -0,0 +1,18 @@
+package Analysis.Loops;
+
+import IR.Flat.*;
+
+public class LoopOptimize {
+  LoopInvariant loopinv;
+  public LoopOptimize(TypeUtil typeutil) {
+    loopinv=new LoopInvariant(typeutil);
+  }
+  public void optimize(FlatMethod fm) {
+    loopinv.analyze(fm);
+    dooptimize(fm);
+  } 
+  private void dooptimize(FlatMethod fm) {
+  }
+  
+
+}
-- 
2.34.1