Robust/src/Analysis/Loops/LoopOptimize.java

   1 package Analysis.Loops;
   2
   3 import java.util.HashMap;
   4 import java.util.Hashtable;
   5 import java.util.Iterator;
   6 import java.util.Map;
   7 import java.util.Set;
   8 import java.util.Vector;
   9
  10 import IR.Operation;
  11 import IR.TypeUtil;
  12 import IR.Flat.FlatMethod;
  13 import IR.Flat.FlatNode;
  14 import IR.Flat.FlatOpNode;
  15 import IR.Flat.TempDescriptor;
  16 import IR.Flat.TempMap;
  17
  18 public class LoopOptimize {
  19   private LoopInvariant loopinv;
  20   private GlobalFieldType gft;
  21   private TypeUtil typeutil;
  22   private Map<FlatMethod, LoopInvariant> fm2loopinv;
  23   private LoopTerminate lt;
  24
  25   private Hashtable<FlatNode, FlatNode> ntoomap;
  26   private Hashtable<FlatNode, FlatNode> clonemap;
  27   private Hashtable<FlatNode, FlatNode> map;
  28
  29   public LoopOptimize(GlobalFieldType gft, TypeUtil typeutil) {
  30     this.gft = gft;
  31     this.typeutil = typeutil;
  32     fm2loopinv = new HashMap<FlatMethod, LoopInvariant>();
  33   }
  34
  35   public void analyze(FlatMethod fm){
  36     loopinv = new LoopInvariant(typeutil, gft);
  37     loopinv.analyze(fm);
  38     fm2loopinv.put(fm, loopinv);
  39   }
  40
  41   public void optimize(FlatMethod fm) {
  42     ntoomap=new Hashtable<FlatNode, FlatNode>();
  43     map=new Hashtable<FlatNode, FlatNode>();
  44     clonemap=new Hashtable<FlatNode, FlatNode>();
  45     dooptimize(fm);
  46   }
  47
  48   private FlatNode ntooremap(FlatNode fn) {
  49     while(ntoomap.containsKey(fn)) {
  50       fn=ntoomap.get(fn);
  51     }
  52     return fn;
  53   }
  54
  55   private FlatNode otonremap(FlatNode fn) {
  56     while(map.containsKey(fn)) {
  57       fn=map.get(fn);
  58     }
  59     return fn;
  60   }
  61
  62   private void dooptimize(FlatMethod fm) {
  63     Loops root=loopinv.root;
  64     recurse(fm, root);
  65   }
  66   private void recurse(FlatMethod fm, Loops parent) {
  67     for(Iterator lpit=parent.nestedLoops().iterator(); lpit.hasNext(); ) {
  68       Loops child=(Loops)lpit.next();
  69       processLoop(fm, child);
  70       recurse(fm, child);
  71     }
  72   }
  73   public void processLoop(FlatMethod fm, Loops l) {
  74     Set entrances=l.loopEntrances();
  75     assert entrances.size()==1;
  76     FlatNode entrance=(FlatNode)entrances.iterator().next();
  77     if (loopinv.tounroll.contains(entrance)) {
  78       unrollLoop(l, fm);
  79     } else {
  80       hoistOps(l);
  81     }
  82   }
  83   public void hoistOps(Loops l) {
  84     Set entrances=l.loopEntrances();
  85     assert entrances.size()==1;
  86     FlatNode entrance=(FlatNode)entrances.iterator().next();
  87     Vector<FlatNode> tohoist=loopinv.table.get(entrance);
  88     Set lelements=l.loopIncElements();
  89     TempMap t=new TempMap();
  90     TempMap tnone=new TempMap();
  91     FlatNode first=null;
  92     FlatNode last=null;
  93     if (tohoist.size()==0)
  94       return;
  95
  96     for(int i=0; i<tohoist.size(); i++) {
  97       FlatNode fn=tohoist.elementAt(i);
  98       TempDescriptor[] writes=fn.writesTemps();
  99
 100       //deal with the possiblity we already hoisted this node
 101       if (clonemap.containsKey(fn)) {
 102         FlatNode fnnew=clonemap.get(fn);
 103         TempDescriptor writenew[]=fnnew.writesTemps();
 104         t.addPair(writes[0],writenew[0]);
 105         if (fn==entrance)
 106           entrance=map.get(fn);
 107         continue;
 108       }
 109
 110       //build hoisted version
 111       FlatNode fnnew=fn.clone(tnone);
 112       fnnew.rewriteUse(t);
 113
 114       for(int j=0; j<writes.length; j++) {
 115         if (writes[j]!=null) {
 116           TempDescriptor cp=writes[j].createNew();
 117           t.addPair(writes[j],cp);
 118         }
 119       }
 120       fnnew.rewriteDef(t);
 121
 122       //store mapping
 123       clonemap.put(fn, fnnew);
 124
 125       //add hoisted version to chain
 126       if (first==null)
 127         first=fnnew;
 128       else
 129         last.addNext(fnnew);
 130       last=fnnew;
 131
 132       /* Splice out old node */
 133       if (writes.length==1) {
 134         FlatOpNode fon=new FlatOpNode(writes[0], t.tempMap(writes[0]), null, new Operation(Operation.ASSIGN));
 135         fn.replace(fon);
 136         ntoomap.put(fon, fn);
 137         map.put(fn, fon);
 138         if (fn==entrance)
 139           entrance=fon;
 140       } else if (writes.length>1) {
 141         throw new Error();
 142       }
 143     }
 144     /* If the chain is empty, we can exit now */
 145     if (first==null)
 146       return;
 147
 148     /* The chain is built at this point. */
 149     FlatNode[] prevarray=new FlatNode[entrance.numPrev()];
 150     for(int i=0; i<entrance.numPrev(); i++) {
 151       prevarray[i]=entrance.getPrev(i);
 152     }
 153     for(int i=0; i<prevarray.length; i++) {
 154       FlatNode prev=prevarray[i];
 155
 156       if (!lelements.contains(ntooremap(prev))) {
 157         //need to fix this edge
 158         for(int j=0; j<prev.numNext(); j++) {
 159           if (prev.getNext(j)==entrance)
 160             prev.setNext(j, first);
 161         }
 162       }
 163     }
 164     last.addNext(entrance);
 165   }
 166
 167   public void unrollLoop(Loops l, FlatMethod fm) {
 168     assert l.loopEntrances().size()==1;
 169     //deal with possibility that entrance has been hoisted
 170     FlatNode entrance=(FlatNode)l.loopEntrances().iterator().next();
 171     entrance=otonremap(entrance);
 172
 173     Set lelements=l.loopIncElements();
 174
 175     Set<FlatNode> tohoist=loopinv.hoisted;
 176     Hashtable<FlatNode, TempDescriptor> temptable=new Hashtable<FlatNode, TempDescriptor>();
 177     Hashtable<FlatNode, FlatNode> copytable=new Hashtable<FlatNode, FlatNode>();
 178     Hashtable<FlatNode, FlatNode> copyendtable=new Hashtable<FlatNode, FlatNode>();
 179
 180     TempMap t=new TempMap();
 181     /* Copy the nodes */
 182     for(Iterator it=lelements.iterator(); it.hasNext(); ) {
 183       FlatNode fn=(FlatNode)it.next();
 184       FlatNode nfn=otonremap(fn);
 185
 186       FlatNode copy=nfn.clone(t);
 187       FlatNode copyend=copy;
 188       if (tohoist.contains(fn)) {
 189         //deal with the possiblity we already hoisted this node
 190         if (clonemap.containsKey(fn)) {
 191           FlatNode fnnew=clonemap.get(fn);
 192           TempDescriptor writenew[]=fnnew.writesTemps();
 193           temptable.put(nfn, writenew[0]);
 194         } else {
 195           TempDescriptor[] writes=nfn.writesTemps();
 196           TempDescriptor tmp=writes[0];
 197           TempDescriptor ntmp=tmp.createNew();
 198           temptable.put(nfn, ntmp);
 199           copyend=new FlatOpNode(ntmp, tmp, null, new Operation(Operation.ASSIGN));
 200           copy.addNext(copyend);
 201         }
 202       }
 203       copytable.put(nfn, copy);
 204       copyendtable.put(nfn, copyend);
 205     }
 206
 207     /* Store initial in set for loop header */
 208     FlatNode[] prevarray=new FlatNode[entrance.numPrev()];
 209     for(int i=0; i<entrance.numPrev(); i++) {
 210       prevarray[i]=entrance.getPrev(i);
 211     }
 212     FlatNode first=copytable.get(entrance);
 213
 214     /* Copy the internal edges */
 215     for(Iterator it=lelements.iterator(); it.hasNext(); ) {
 216       FlatNode fn=(FlatNode)it.next();
 217       fn=otonremap(fn);
 218       FlatNode copyend=copyendtable.get(fn);
 219       for(int i=0; i<fn.numNext(); i++) {
 220         FlatNode nnext=fn.getNext(i);
 221         if (nnext==entrance) {
 222           /* Back to loop header...point to old graph */
 223           copyend.setNewNext(i,nnext);
 224         } else if (lelements.contains(ntooremap(nnext))) {
 225           /* In graph...point to first graph */
 226           copyend.setNewNext(i,copytable.get(nnext));
 227         } else {
 228           /* Outside loop */
 229           /* Just goto same place as before */
 230           copyend.setNewNext(i,nnext);
 231         }
 232       }
 233     }
 234
 235     /* Splice header in using original in set */
 236     for(int i=0; i<prevarray.length; i++) {
 237       FlatNode prev=prevarray[i];
 238
 239       if (!lelements.contains(ntooremap(prev))) {
 240         //need to fix this edge
 241         for(int j=0; j<prev.numNext(); j++) {
 242           if (prev.getNext(j)==entrance) {
 243             prev.setNext(j, first);
 244           }
 245         }
 246       }
 247     }
 248
 249     /* Splice out loop invariant stuff */
 250     for(Iterator it=lelements.iterator(); it.hasNext(); ) {
 251       FlatNode fn=(FlatNode)it.next();
 252       FlatNode nfn=otonremap(fn);
 253       if (tohoist.contains(fn)) {
 254         TempDescriptor[] writes=nfn.writesTemps();
 255         TempDescriptor tmp=writes[0];
 256         FlatOpNode fon=new FlatOpNode(tmp, temptable.get(nfn), null, new Operation(Operation.ASSIGN));
 257         nfn.replace(fon);
 258       }
 259     }
 260   }
 261
 262   public LoopInvariant getLoopInvariant(FlatMethod fm){
 263     return fm2loopinv.get(fm);
 264   }
 265 }