1 package Analysis.Loops;
3 import java.util.HashMap;
4 import java.util.Hashtable;
5 import java.util.Iterator;
8 import java.util.Vector;
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;
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;
25 private Hashtable<FlatNode, FlatNode> ntoomap;
26 private Hashtable<FlatNode, FlatNode> clonemap;
27 private Hashtable<FlatNode, FlatNode> map;
29 public LoopOptimize(GlobalFieldType gft, TypeUtil typeutil) {
31 this.typeutil = typeutil;
32 fm2loopinv = new HashMap<FlatMethod, LoopInvariant>();
35 public void analyze(FlatMethod fm){
36 loopinv = new LoopInvariant(typeutil, gft);
38 fm2loopinv.put(fm, loopinv);
41 public void optimize(FlatMethod fm) {
42 ntoomap=new Hashtable<FlatNode, FlatNode>();
43 map=new Hashtable<FlatNode, FlatNode>();
44 clonemap=new Hashtable<FlatNode, FlatNode>();
48 private FlatNode ntooremap(FlatNode fn) {
49 while(ntoomap.containsKey(fn)) {
55 private FlatNode otonremap(FlatNode fn) {
56 while(map.containsKey(fn)) {
62 private void dooptimize(FlatMethod fm) {
63 Loops root=loopinv.root;
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);
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)) {
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();
93 if (tohoist.size()==0)
96 for(int i=0; i<tohoist.size(); i++) {
97 FlatNode fn=tohoist.elementAt(i);
98 TempDescriptor[] writes=fn.writesTemps();
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]);
106 entrance=map.get(fn);
110 //build hoisted version
111 FlatNode fnnew=fn.clone(tnone);
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);
123 clonemap.put(fn, fnnew);
125 //add hoisted version to chain
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));
136 ntoomap.put(fon, fn);
140 } else if (writes.length>1) {
144 /* If the chain is empty, we can exit now */
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);
153 for(int i=0; i<prevarray.length; i++) {
154 FlatNode prev=prevarray[i];
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);
164 last.addNext(entrance);
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);
173 Set lelements=l.loopIncElements();
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>();
180 TempMap t=new TempMap();
182 for(Iterator it=lelements.iterator(); it.hasNext(); ) {
183 FlatNode fn=(FlatNode)it.next();
184 FlatNode nfn=otonremap(fn);
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]);
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);
203 copytable.put(nfn, copy);
204 copyendtable.put(nfn, copyend);
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);
212 FlatNode first=copytable.get(entrance);
214 /* Copy the internal edges */
215 for(Iterator it=lelements.iterator(); it.hasNext(); ) {
216 FlatNode fn=(FlatNode)it.next();
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));
229 /* Just goto same place as before */
230 copyend.setNewNext(i,nnext);
235 /* Splice header in using original in set */
236 for(int i=0; i<prevarray.length; i++) {
237 FlatNode prev=prevarray[i];
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);
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));
262 public LoopInvariant getLoopInvariant(FlatMethod fm){
263 return fm2loopinv.get(fm);