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)) {
112 case FKind.FlatInstanceOfNode:
113 if (checkNode(fn,elements)) {
118 case FKind.FlatElementNode:
119 if (unsafe||dominatorset==null||
120 !dominatorset.contains(fn)||
121 checkNode(fn,elements))
123 TypeDescriptor td=((FlatElementNode)fn).getSrc().getType();
124 for(Iterator<TypeDescriptor> tdit=types.iterator();tdit.hasNext();) {
125 TypeDescriptor td2=tdit.next();
126 if (typeutil.isSuperorType(td,td2)||
127 typeutil.isSuperorType(td2,td)) {
132 tounroll.add(entrance);
135 case FKind.FlatFieldNode:
136 if (unsafe||dominatorset==null||
137 !dominatorset.contains(fn)||
138 fields.contains(((FlatFieldNode)fn).getField())||
139 checkNode(fn,elements)) {
143 tounroll.add(entrance);
152 table.get(entrance).add(fn);
157 public HashSet computeAlways(Loops l) {
158 /* Compute nodes that are always executed in loop */
159 HashSet dominatorset=null;
160 /* Compute nodes that definitely get executed in a loop */
161 Set elements=l.loopIncElements();
162 Set entrances=l.loopEntrances();
163 assert entrances.size()==1;
164 FlatNode entrance=(FlatNode)entrances.iterator().next();
166 for (int i=0;i<entrance.numPrev();i++) {
167 FlatNode incoming=entrance.getPrev(i);
168 if (elements.contains(incoming)) {
169 HashSet domset=new HashSet();
170 domset.add(incoming);
171 FlatNode tmp=incoming;
172 while(tmp!=entrance) {
173 tmp=domtree.idom(tmp);
180 for(Iterator it=dominatorset.iterator();it.hasNext();) {
181 FlatNode fn=(FlatNode)it.next();
182 if (!domset.contains(fn))
191 public boolean checkNode(FlatNode fn, Set elements) {
192 //Can hoist if all variables are loop invariant
193 TempDescriptor[]uses=fn.readsTemps();
194 for(int i=0;i<uses.length;i++) {
195 TempDescriptor t=uses[i];
196 Set<FlatNode> defset=usedef.defMap(fn, t);
197 for(Iterator<FlatNode> defit=defset.iterator();defit.hasNext();) {
198 FlatNode def=defit.next();
199 if (elements.contains(def)&&defset.size()>1)
201 if (elements.contains(def)&&!hoisted.contains(def))