Robust/src/Analysis/Loops/LoopInvariant.java

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