1 package Analysis.Loops;
5 import IR.MethodDescriptor;
7 import java.util.HashSet;
9 import java.util.Vector;
10 import java.util.Iterator;
11 import java.util.Hashtable;
13 public class LoopOptimize {
14 LoopInvariant loopinv;
15 public LoopOptimize(GlobalFieldType gft, TypeUtil typeutil) {
16 loopinv=new LoopInvariant(typeutil,gft);
18 Hashtable<FlatNode, FlatNode> ntoomap;
19 Hashtable<FlatNode, FlatNode> clonemap;
20 Hashtable<FlatNode, FlatNode> map;
22 public void optimize(FlatMethod fm) {
24 ntoomap=new Hashtable<FlatNode, FlatNode>();
25 map=new Hashtable<FlatNode, FlatNode>();
26 clonemap=new Hashtable<FlatNode, FlatNode>();
30 private FlatNode ntooremap(FlatNode fn) {
31 while(ntoomap.containsKey(fn)) {
37 private FlatNode otonremap(FlatNode fn) {
38 while(map.containsKey(fn)) {
44 private void dooptimize(FlatMethod fm) {
45 Loops root=loopinv.root;
48 private void recurse(FlatMethod fm, Loops parent) {
49 for(Iterator lpit=parent.nestedLoops().iterator();lpit.hasNext();) {
50 Loops child=(Loops)lpit.next();
51 processLoop(fm, child);
55 public void processLoop(FlatMethod fm, Loops l) {
56 Set entrances=l.loopEntrances();
57 assert entrances.size()==1;
58 FlatNode entrance=(FlatNode)entrances.iterator().next();
59 if (loopinv.tounroll.contains(entrance)) {
65 public void hoistOps(Loops l) {
66 Set entrances=l.loopEntrances();
67 assert entrances.size()==1;
68 FlatNode entrance=(FlatNode)entrances.iterator().next();
69 Vector<FlatNode> tohoist=loopinv.table.get(entrance);
70 Set lelements=l.loopIncElements();
71 TempMap t=new TempMap();
72 TempMap tnone=new TempMap();
75 if (tohoist.size()==0)
78 for(int i=0;i<tohoist.size();i++) {
79 FlatNode fn=tohoist.elementAt(i);
80 TempDescriptor[] writes=fn.writesTemps();
82 //deal with the possiblity we already hoisted this node
83 if (clonemap.containsKey(fn)) {
84 FlatNode fnnew=clonemap.get(fn);
85 TempDescriptor writenew[]=fnnew.writesTemps();
86 t.addPair(writes[0],writenew[0]);
92 //build hoisted version
93 FlatNode fnnew=fn.clone(tnone);
96 for(int j=0;j<writes.length;j++) {
97 if (writes[j]!=null) {
98 TempDescriptor cp=writes[j].createNew();
99 t.addPair(writes[j],cp);
105 clonemap.put(fn, fnnew);
107 //add hoisted version to chain
114 /* Splice out old node */
115 if (writes.length==1) {
116 FlatOpNode fon=new FlatOpNode(writes[0], t.tempMap(writes[0]), null, new Operation(Operation.ASSIGN));
118 ntoomap.put(fon, fn);
122 } else if (writes.length>1) {
126 /* If the chain is empty, we can exit now */
130 /* The chain is built at this point. */
131 FlatNode[] prevarray=new FlatNode[entrance.numPrev()];
132 for(int i=0;i<entrance.numPrev();i++) {
133 prevarray[i]=entrance.getPrev(i);
135 for(int i=0;i<prevarray.length;i++) {
136 FlatNode prev=prevarray[i];
138 if (!lelements.contains(ntooremap(prev))) {
139 //need to fix this edge
140 for(int j=0;j<prev.numNext();j++) {
141 if (prev.getNext(j)==entrance)
142 prev.setNext(j, first);
146 last.addNext(entrance);
149 public void unrollLoop(Loops l, FlatMethod fm) {
150 assert l.loopEntrances().size()==1;
151 //deal with possibility that entrance has been hoisted
152 FlatNode entrance=(FlatNode)l.loopEntrances().iterator().next();
153 entrance=otonremap(entrance);
155 Set lelements=l.loopIncElements();
157 Set<FlatNode> tohoist=loopinv.hoisted;
158 Hashtable<FlatNode, TempDescriptor> temptable=new Hashtable<FlatNode, TempDescriptor>();
159 Hashtable<FlatNode, FlatNode> copytable=new Hashtable<FlatNode, FlatNode>();
160 Hashtable<FlatNode, FlatNode> copyendtable=new Hashtable<FlatNode, FlatNode>();
162 TempMap t=new TempMap();
164 for(Iterator it=lelements.iterator();it.hasNext();) {
165 FlatNode fn=(FlatNode)it.next();
166 FlatNode nfn=otonremap(fn);
168 FlatNode copy=nfn.clone(t);
169 FlatNode copyend=copy;
170 if (tohoist.contains(fn)) {
171 //deal with the possiblity we already hoisted this node
172 if (clonemap.containsKey(fn)) {
173 FlatNode fnnew=clonemap.get(fn);
174 TempDescriptor writenew[]=fnnew.writesTemps();
175 temptable.put(nfn, writenew[0]);
177 TempDescriptor[] writes=nfn.writesTemps();
178 TempDescriptor tmp=writes[0];
179 TempDescriptor ntmp=tmp.createNew();
180 temptable.put(nfn, ntmp);
181 copyend=new FlatOpNode(ntmp, tmp, null, new Operation(Operation.ASSIGN));
182 copy.addNext(copyend);
185 copytable.put(nfn, copy);
186 copyendtable.put(nfn, copyend);
189 /* Store initial in set for loop header */
190 FlatNode[] prevarray=new FlatNode[entrance.numPrev()];
191 for(int i=0;i<entrance.numPrev();i++) {
192 prevarray[i]=entrance.getPrev(i);
194 FlatNode first=copytable.get(entrance);
196 /* Copy the internal edges */
197 for(Iterator it=lelements.iterator();it.hasNext();) {
198 FlatNode fn=(FlatNode)it.next();
200 FlatNode copyend=copyendtable.get(fn);
201 for(int i=0;i<fn.numNext();i++) {
202 FlatNode nnext=fn.getNext(i);
203 if (nnext==entrance) {
204 /* Back to loop header...point to old graph */
205 copyend.setNewNext(i,nnext);
206 } else if (lelements.contains(ntooremap(nnext))) {
207 /* In graph...point to first graph */
208 copyend.setNewNext(i,copytable.get(nnext));
211 /* Just goto same place as before */
212 copyend.setNewNext(i,nnext);
217 /* Splice header in using original in set */
218 for(int i=0;i<prevarray.length;i++) {
219 FlatNode prev=prevarray[i];
221 if (!lelements.contains(ntooremap(prev))) {
222 //need to fix this edge
223 for(int j=0;j<prev.numNext();j++) {
224 if (prev.getNext(j)==entrance) {
225 prev.setNext(j, first);
231 /* Splice out loop invariant stuff */
232 for(Iterator it=lelements.iterator();it.hasNext();) {
233 FlatNode fn=(FlatNode)it.next();
234 FlatNode nfn=otonremap(fn);
235 if (tohoist.contains(fn)) {
236 TempDescriptor[] writes=nfn.writesTemps();
237 TempDescriptor tmp=writes[0];
238 FlatOpNode fon=new FlatOpNode(tmp, temptable.get(nfn), null, new Operation(Operation.ASSIGN));