1 package Analysis.Loops;
4 import IR.MethodDescriptor;
5 import IR.FieldDescriptor;
6 import IR.TypeDescriptor;
9 import java.util.Iterator;
10 import java.util.HashSet;
12 import java.util.Vector;
13 import java.util.Hashtable;
15 public class LoopInvariant {
16 public LoopInvariant(TypeUtil typeutil, GlobalFieldType gft) {
17 this.typeutil=typeutil;
23 Hashtable<FlatNode, Vector<FlatNode>> table;
24 Set<FlatNode> hoisted;
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();
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);
49 public void processLoop(Loops l, boolean isLeaf) {
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();
59 HashSet<FieldDescriptor> fields=new HashSet<FieldDescriptor>();
60 HashSet<TypeDescriptor> types=new HashSet<TypeDescriptor>();
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) {
72 } else if (fn.kind()==FKind.FlatCall) {
73 FlatCall fcall=(FlatCall)fn;
74 MethodDescriptor md=fcall.getMethod();
75 Set<FieldDescriptor> f=gft.getFieldsAll(md);
76 Set<TypeDescriptor> t=gft.getArraysAll(md);
81 if (gft.containsAtomicAll(md)||gft.containsBarrierAll(md)) {
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());
94 HashSet dominatorset=unsafe?null:computeAlways(l);
96 /* Compute loop invariants */
97 table.put(entrance, new Vector<FlatNode>());
101 for(Iterator tpit=toprocess.iterator(); tpit.hasNext(); ) {
102 FlatNode fn=(FlatNode)tpit.next();
104 case FKind.FlatOpNode:
105 int op=((FlatOpNode)fn).getOp().getOp();
106 if (op==Operation.DIV||op==Operation.MOD||
107 checkNode(fn,elements)||
108 !unsafe&&!dominatorset.contains(fn)) {
113 case FKind.FlatInstanceOfNode:
114 if (checkNode(fn,elements)||
115 !unsafe&&!dominatorset.contains(fn)) {
120 case FKind.FlatElementNode:
121 if (unsafe||dominatorset==null||
122 !dominatorset.contains(fn)||
123 checkNode(fn,elements))
125 TypeDescriptor td=((FlatElementNode)fn).getSrc().getType();
126 for(Iterator<TypeDescriptor> tdit=types.iterator(); tdit.hasNext(); ) {
127 TypeDescriptor td2=tdit.next();
128 if (typeutil.isSuperorType(td,td2)||
129 typeutil.isSuperorType(td2,td)) {
134 tounroll.add(entrance);
137 case FKind.FlatFieldNode:
138 if (unsafe||dominatorset==null||
139 !dominatorset.contains(fn)||
140 fields.contains(((FlatFieldNode)fn).getField())||
141 checkNode(fn,elements)) {
145 tounroll.add(entrance);
154 table.get(entrance).add(fn);
159 public HashSet computeAlways(Loops l) {
160 /* Compute nodes that are always executed in loop */
161 HashSet dominatorset=null;
162 /* Compute nodes that definitely get executed in a loop */
163 Set elements=l.loopIncElements();
164 Set entrances=l.loopEntrances();
165 assert entrances.size()==1;
166 FlatNode entrance=(FlatNode)entrances.iterator().next();
168 for (int i=0; i<entrance.numPrev(); i++) {
169 FlatNode incoming=entrance.getPrev(i);
170 if (elements.contains(incoming)) {
171 HashSet domset=new HashSet();
172 domset.add(incoming);
173 FlatNode tmp=incoming;
174 while(tmp!=entrance) {
175 tmp=domtree.idom(tmp);
182 for(Iterator it=dominatorset.iterator(); it.hasNext(); ) {
183 FlatNode fn=(FlatNode)it.next();
184 if (!domset.contains(fn))
193 public boolean checkNode(FlatNode fn, Set elements) {
194 //Can hoist if all variables are loop invariant
195 TempDescriptor[] uses=fn.readsTemps();
196 for(int i=0; i<uses.length; i++) {
197 TempDescriptor t=uses[i];
198 Set<FlatNode> defset=usedef.defMap(fn, t);
199 for(Iterator<FlatNode> defit=defset.iterator(); defit.hasNext(); ) {
200 FlatNode def=defit.next();
201 if (elements.contains(def)&&defset.size()>1)
203 if (elements.contains(def)&&!hoisted.contains(def))