Robust/src/Analysis/Loops/LoopInvariant.java

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