Robust/src/Analysis/Loops/LoopInvariant.java

   1 package Analysis.Loops;
   2
   3 import IR.Flat.*;
   4 import IR.FieldDescriptor;
   5 import IR.TypeDescriptor;
   6 import IR.TypeUtil;
   7 import IR.Operation;
   8 import java.util.Iterator;
   9 import java.util.HashSet;
  10 import java.util.Set;
  11 import java.util.Vector;
  12 import java.util.Hashtable;
  13
  14 public class LoopInvariant {
  15   public LoopInvariant(TypeUtil typeutil) {
  16     this.typeutil=typeutil;
  17   }
  18   LoopFinder loops;
  19   DomTree posttree;
  20   Hashtable<Loops, Vector<FlatNode>> table;
  21   Set<FlatNode> hoisted;
  22   UseDef usedef;
  23   TypeUtil typeutil;
  24   Set tounroll;
  25
  26   public void analyze(FlatMethod fm) {
  27     loops=new LoopFinder(fm);
  28     Loops root=loops.getRootloop(fm);
  29     table=new Hashtable<Loops, Vector<FlatNode>>();
  30     hoisted=new HashSet<FlatNode>();
  31     usedef=new UseDef(fm);
  32     posttree=new DomTree(fm,true);
  33     tounroll=new HashSet();
  34     recurse(root);
  35   }
  36
  37   public void recurse(Loops parent) {
  38     processLoop(parent, parent.nestedLoops().size()==0);
  39     for(Iterator lpit=parent.nestedLoops().iterator();lpit.hasNext();) {
  40       Loops child=(Loops)lpit.next();
  41       recurse(child);
  42     }
  43   }
  44
  45   public void processLoop(Loops l, boolean isLeaf) {
  46     boolean changed=true;
  47     boolean unsafe=false;
  48     Set elements=l.loopIncElements();
  49     Set toprocess=l.loopIncElements();
  50     toprocess.removeAll(hoisted);
  51
  52     HashSet<FieldDescriptor> fields=new HashSet<FieldDescriptor>();
  53     HashSet<TypeDescriptor> types=new HashSet<TypeDescriptor>();
  54
  55     if (!isLeaf) {
  56       unsafe=true;
  57     } else {
  58       /* Check whether it is safe to reuse values. */
  59       for(Iterator elit=elements.iterator();elit.hasNext();) {
  60         FlatNode fn=(FlatNode)elit.next();
  61         if (fn.kind()==FKind.FlatAtomicEnterNode||
  62             fn.kind()==FKind.FlatAtomicExitNode||
  63             fn.kind()==FKind.FlatCall) {
  64           unsafe=true;
  65           break;
  66         } else if (fn.kind()==FKind.FlatSetFieldNode) {
  67           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
  68           fields.add(fsfn.getField());
  69         } else if (fn.kind()==FKind.FlatSetElementNode) {
  70           FlatSetElementNode fsen=(FlatSetElementNode)fn;
  71           types.add(fsen.getDst().getType());
  72         }
  73       }
  74     }
  75
  76     HashSet dominatorset=unsafe?null:computeAlways(l);
  77
  78     /* Compute loop invariants */
  79     table.put(l, new Vector<FlatNode>());
  80     while(changed) {
  81       changed=false;
  82       nextfn:
  83       for(Iterator tpit=toprocess.iterator();tpit.hasNext();) {
  84         FlatNode fn=(FlatNode)tpit.next();
  85         switch(fn.kind()) {
  86         case FKind.FlatOpNode:
  87           int op=((FlatOpNode)fn).getOp().getOp();
  88           if (op==Operation.DIV||op==Operation.MOD||
  89               checkNode(fn,elements)) {
  90             continue nextfn;
  91           }
  92           break;
  93
  94         case FKind.FlatInstanceOfNode:
  95           if (checkNode(fn,elements)) {
  96             continue nextfn;
  97           }
  98           break;
  99
 100         case FKind.FlatElementNode:
 101           if (unsafe||!dominatorset.contains(fn)||
 102               checkNode(fn,elements))
 103             continue nextfn;
 104           TypeDescriptor td=((FlatElementNode)fn).getSrc().getType();
 105           for(Iterator<TypeDescriptor> tdit=types.iterator();tdit.hasNext();) {
 106             TypeDescriptor td2=tdit.next();
 107             if (typeutil.isSuperorType(td,td2)||
 108                 typeutil.isSuperorType(td2,td)) {
 109               continue nextfn;
 110             }
 111           }
 112           if (isLeaf)
 113             tounroll.add(l);
 114           break;
 115
 116         case FKind.FlatFieldNode:
 117           if (unsafe||!dominatorset.contains(fn)||
 118               fields.contains(((FlatFieldNode)fn).getField())||
 119               checkNode(fn,elements)) {
 120             continue nextfn;
 121           }
 122           if (isLeaf)
 123             tounroll.add(l);
 124           break;
 125
 126         default:
 127           continue nextfn;
 128         }
 129         //mark to hoist
 130         hoisted.add(fn);
 131         table.get(l).add(fn);
 132       }
 133     }
 134   }
 135
 136   public HashSet computeAlways(Loops l) {
 137     /* Compute nodes that are always executed in loop */
 138     HashSet dominatorset=null;
 139     /* Compute nodes that definitely get executed in a loop */
 140     Set elements=l.loopIncElements();
 141     Set entrances=l.loopEntrances();
 142     assert entrances.size()==1;
 143     FlatNode entrance=(FlatNode)entrances.iterator().next();
 144     boolean first=true;
 145     for (int i=0;i<entrance.numPrev();i++) {
 146       FlatNode incoming=entrance.getPrev(i);
 147       if (elements.contains(incoming)) {
 148         HashSet domset=new HashSet();
 149         domset.add(incoming);
 150         FlatNode tmp=incoming;
 151         while(tmp!=entrance) {
 152           tmp=posttree.idom(tmp);
 153           domset.add(tmp);
 154         }
 155         if (first) {
 156           dominatorset=domset;
 157           first=false;
 158         } else {
 159           for(Iterator it=dominatorset.iterator();it.hasNext();) {
 160             FlatNode fn=(FlatNode)it.next();
 161             if (!domset.contains(fn))
 162               it.remove();
 163           }
 164         }
 165       }
 166     }
 167     return dominatorset;
 168   }
 169
 170   public boolean checkNode(FlatNode fn, Set elements) {
 171     //Can hoist if all variables are loop invariant
 172     TempDescriptor[]uses=fn.readsTemps();
 173     for(int i=0;i<uses.length;i++) {
 174       TempDescriptor t=uses[i];
 175       Set<FlatNode> defset=usedef.defMap(fn, t);
 176       for(Iterator<FlatNode> defit=defset.iterator();defit.hasNext();) {
 177         FlatNode def=defit.next();
 178         if (elements.contains(def)&&defset.size()>1)
 179           return true;
 180         if (elements.contains(def)&&!hoisted.contains(def))
 181           return true;
 182       }
 183     }
 184     return false;
 185   }
 186 }