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 posttree;
  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     posttree=new DomTree(fm,true);
  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.getFields(md);
  76           Set<TypeDescriptor> t=gft.getArrays(md);
  77           if (f!=null)
  78             fields.addAll(f);
  79           if (t!=null)
  80             types.addAll(t);
  81           if (gft.containsAtomic(md))
  82             unsafe=true;
  83         } else if (fn.kind()==FKind.FlatSetFieldNode) {
  84           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
  85           fields.add(fsfn.getField());
  86         } else if (fn.kind()==FKind.FlatSetElementNode) {
  87           FlatSetElementNode fsen=(FlatSetElementNode)fn;
  88           types.add(fsen.getDst().getType());
  89         }
  90       }
  91     }
  92
  93     HashSet dominatorset=unsafe?null:computeAlways(l);
  94
  95     /* Compute loop invariants */
  96     table.put(entrance, new Vector<FlatNode>());
  97     while(changed) {
  98       changed=false;
  99       nextfn:
 100       for(Iterator tpit=toprocess.iterator();tpit.hasNext();) {
 101         FlatNode fn=(FlatNode)tpit.next();
 102         switch(fn.kind()) {
 103         case FKind.FlatOpNode:
 104           int op=((FlatOpNode)fn).getOp().getOp();
 105           if (op==Operation.DIV||op==Operation.MOD||
 106               checkNode(fn,elements)) {
 107             continue nextfn;
 108           }
 109           break;
 110
 111         case FKind.FlatInstanceOfNode:
 112           if (checkNode(fn,elements)) {
 113             continue nextfn;
 114           }
 115           break;
 116
 117         case FKind.FlatElementNode:
 118           if (unsafe||dominatorset==null||
 119               !dominatorset.contains(fn)||
 120               checkNode(fn,elements))
 121             continue nextfn;
 122           TypeDescriptor td=((FlatElementNode)fn).getSrc().getType();
 123           for(Iterator<TypeDescriptor> tdit=types.iterator();tdit.hasNext();) {
 124             TypeDescriptor td2=tdit.next();
 125             if (typeutil.isSuperorType(td,td2)||
 126                 typeutil.isSuperorType(td2,td)) {
 127               continue nextfn;
 128             }
 129           }
 130           if (isLeaf)
 131             tounroll.add(l);
 132           break;
 133
 134         case FKind.FlatFieldNode:
 135           if (unsafe||dominatorset==null||
 136               !dominatorset.contains(fn)||
 137               fields.contains(((FlatFieldNode)fn).getField())||
 138               checkNode(fn,elements)) {
 139             continue nextfn;
 140           }
 141           if (isLeaf)
 142             tounroll.add(l);
 143           break;
 144
 145         default:
 146           continue nextfn;
 147         }
 148         //mark to hoist
 149         hoisted.add(fn);
 150         table.get(entrance).add(fn);
 151       }
 152     }
 153   }
 154
 155   public HashSet computeAlways(Loops l) {
 156     /* Compute nodes that are always executed in loop */
 157     HashSet dominatorset=null;
 158     /* Compute nodes that definitely get executed in a loop */
 159     Set elements=l.loopIncElements();
 160     Set entrances=l.loopEntrances();
 161     assert entrances.size()==1;
 162     FlatNode entrance=(FlatNode)entrances.iterator().next();
 163     boolean first=true;
 164     for (int i=0;i<entrance.numPrev();i++) {
 165       FlatNode incoming=entrance.getPrev(i);
 166       if (elements.contains(incoming)) {
 167         HashSet domset=new HashSet();
 168         domset.add(incoming);
 169         FlatNode tmp=incoming;
 170         while(tmp!=entrance) {
 171           tmp=posttree.idom(tmp);
 172           domset.add(tmp);
 173         }
 174         if (first) {
 175           dominatorset=domset;
 176           first=false;
 177         } else {
 178           for(Iterator it=dominatorset.iterator();it.hasNext();) {
 179             FlatNode fn=(FlatNode)it.next();
 180             if (!domset.contains(fn))
 181               it.remove();
 182           }
 183         }
 184       }
 185     }
 186     return dominatorset;
 187   }
 188
 189   public boolean checkNode(FlatNode fn, Set elements) {
 190     //Can hoist if all variables are loop invariant
 191     TempDescriptor[]uses=fn.readsTemps();
 192     for(int i=0;i<uses.length;i++) {
 193       TempDescriptor t=uses[i];
 194       Set<FlatNode> defset=usedef.defMap(fn, t);
 195       for(Iterator<FlatNode> defit=defset.iterator();defit.hasNext();) {
 196         FlatNode def=defit.next();
 197         if (elements.contains(def)&&defset.size()>1)
 198           return true;
 199         if (elements.contains(def)&&!hoisted.contains(def))
 200           return true;
 201       }
 202     }
 203     return false;
 204   }
 205 }