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.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           }
  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             continue nextfn;
 109           }
 110           break;
 111
 112         case FKind.FlatInstanceOfNode:
 113           if (checkNode(fn,elements)) {
 114             continue nextfn;
 115           }
 116           break;
 117
 118         case FKind.FlatElementNode:
 119           if (unsafe||dominatorset==null||
 120               !dominatorset.contains(fn)||
 121               checkNode(fn,elements))
 122             continue nextfn;
 123           TypeDescriptor td=((FlatElementNode)fn).getSrc().getType();
 124           for(Iterator<TypeDescriptor> tdit=types.iterator();tdit.hasNext();) {
 125             TypeDescriptor td2=tdit.next();
 126             if (typeutil.isSuperorType(td,td2)||
 127                 typeutil.isSuperorType(td2,td)) {
 128               continue nextfn;
 129             }
 130           }
 131           if (isLeaf)
 132             tounroll.add(entrance);
 133           break;
 134
 135         case FKind.FlatFieldNode:
 136           if (unsafe||dominatorset==null||
 137               !dominatorset.contains(fn)||
 138               fields.contains(((FlatFieldNode)fn).getField())||
 139               checkNode(fn,elements)) {
 140             continue nextfn;
 141           }
 142           if (isLeaf)
 143             tounroll.add(entrance);
 144           break;
 145
 146         default:
 147           continue nextfn;
 148         }
 149         //mark to hoist
 150         hoisted.add(fn);
 151         table.get(entrance).add(fn);
 152       }
 153     }
 154   }
 155
 156   public HashSet computeAlways(Loops l) {
 157     /* Compute nodes that are always executed in loop */
 158     HashSet dominatorset=null;
 159     /* Compute nodes that definitely get executed in a loop */
 160     Set elements=l.loopIncElements();
 161     Set entrances=l.loopEntrances();
 162     assert entrances.size()==1;
 163     FlatNode entrance=(FlatNode)entrances.iterator().next();
 164     boolean first=true;
 165     for (int i=0;i<entrance.numPrev();i++) {
 166       FlatNode incoming=entrance.getPrev(i);
 167       if (elements.contains(incoming)) {
 168         HashSet domset=new HashSet();
 169         domset.add(incoming);
 170         FlatNode tmp=incoming;
 171         while(tmp!=entrance) {
 172           tmp=domtree.idom(tmp);
 173           domset.add(tmp);
 174         }
 175         if (first) {
 176           dominatorset=domset;
 177           first=false;
 178         } else {
 179           for(Iterator it=dominatorset.iterator();it.hasNext();) {
 180             FlatNode fn=(FlatNode)it.next();
 181             if (!domset.contains(fn))
 182               it.remove();
 183           }
 184         }
 185       }
 186     }
 187     return dominatorset;
 188   }
 189
 190   public boolean checkNode(FlatNode fn, Set elements) {
 191     //Can hoist if all variables are loop invariant
 192     TempDescriptor[]uses=fn.readsTemps();
 193     for(int i=0;i<uses.length;i++) {
 194       TempDescriptor t=uses[i];
 195       Set<FlatNode> defset=usedef.defMap(fn, t);
 196       for(Iterator<FlatNode> defit=defset.iterator();defit.hasNext();) {
 197         FlatNode def=defit.next();
 198         if (elements.contains(def)&&defset.size()>1)
 199           return true;
 200         if (elements.contains(def)&&!hoisted.contains(def))
 201           return true;
 202       }
 203     }
 204     return false;
 205   }
 206 }