1 package Analysis.Loops;
6 import IR.FieldDescriptor;
7 import IR.MethodDescriptor;
8 import IR.TypeDescriptor;
10 import java.util.Iterator;
11 import java.util.Hashtable;
12 import java.util.HashSet;
18 public CSE(GlobalFieldType gft, TypeUtil typeutil) {
20 this.typeutil=typeutil;
23 public void doAnalysis(FlatMethod fm) {
24 Hashtable<FlatNode,Hashtable<Expression, TempDescriptor>> availexpr=new Hashtable<FlatNode,Hashtable<Expression, TempDescriptor>>();
25 HashSet toprocess=new HashSet();
26 HashSet discovered=new HashSet();
29 while(!toprocess.isEmpty()) {
30 FlatNode fn=(FlatNode)toprocess.iterator().next();
32 for(int i=0; i<fn.numNext(); i++) {
33 FlatNode nnext=fn.getNext(i);
34 if (!discovered.contains(nnext)) {
36 discovered.add(nnext);
39 Hashtable<Expression, TempDescriptor> tab=computeIntersection(fn, availexpr);
41 //Do kills of expression/variable mappings
42 TempDescriptor[] write=fn.writesTemps();
43 for(int i=0; i<write.length; i++) {
44 if (tab.containsKey(write[i]))
49 case FKind.FlatAtomicEnterNode:
51 killexpressions(tab, null, null, true);
57 FlatCall fc=(FlatCall) fn;
58 MethodDescriptor md=fc.getMethod();
59 Set<FieldDescriptor> fields=gft.getFieldsAll(md);
60 Set<TypeDescriptor> arrays=gft.getArraysAll(md);
61 killexpressions(tab, fields, arrays, gft.containsAtomicAll(md)||gft.containsBarrierAll(md));
65 case FKind.FlatOpNode:
67 FlatOpNode fon=(FlatOpNode) fn;
68 Expression e=new Expression(fon.getLeft(), fon.getRight(), fon.getOp());
69 tab.put(e, fon.getDest());
73 case FKind.FlatSetFieldNode:
75 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
76 Set<FieldDescriptor> fields=new HashSet<FieldDescriptor>();
77 fields.add(fsfn.getField());
78 killexpressions(tab, fields, null, false);
79 Expression e=new Expression(fsfn.getDst(), fsfn.getField());
80 tab.put(e, fsfn.getSrc());
84 case FKind.FlatFieldNode:
86 FlatFieldNode ffn=(FlatFieldNode)fn;
87 Expression e=new Expression(ffn.getSrc(), ffn.getField());
88 tab.put(e, ffn.getDst());
92 case FKind.FlatSetElementNode:
94 FlatSetElementNode fsen=(FlatSetElementNode)fn;
95 Expression e=new Expression(fsen.getDst(),fsen.getIndex());
96 tab.put(e, fsen.getSrc());
100 case FKind.FlatElementNode:
102 FlatElementNode fen=(FlatElementNode)fn;
103 Expression e=new Expression(fen.getSrc(),fen.getIndex());
104 tab.put(e, fen.getDst());
111 if (write.length==1) {
112 TempDescriptor w=write[0];
113 for(Iterator it=tab.entrySet().iterator(); it.hasNext(); ) {
114 Map.Entry m=(Map.Entry)it.next();
115 Expression e=(Expression)m.getKey();
120 if (!availexpr.containsKey(fn)||!availexpr.get(fn).equals(tab)) {
121 availexpr.put(fn, tab);
122 for(int i=0; i<fn.numNext(); i++) {
123 FlatNode nnext=fn.getNext(i);
124 toprocess.add(nnext);
129 doOptimize(fm, availexpr);
132 public void doOptimize(FlatMethod fm, Hashtable<FlatNode,Hashtable<Expression, TempDescriptor>> availexpr) {
133 Hashtable<FlatNode, FlatNode> replacetable=new Hashtable<FlatNode, FlatNode>();
134 for(Iterator<FlatNode> it=fm.getNodeSet().iterator(); it.hasNext(); ) {
135 FlatNode fn=it.next();
136 Hashtable<Expression, TempDescriptor> tab=computeIntersection(fn, availexpr);
138 case FKind.FlatOpNode:
140 FlatOpNode fon=(FlatOpNode) fn;
141 Expression e=new Expression(fon.getLeft(), fon.getRight(),fon.getOp());
142 if (tab.containsKey(e)) {
143 TempDescriptor t=tab.get(e);
144 FlatNode newfon=new FlatOpNode(fon.getDest(),t,null,new Operation(Operation.ASSIGN));
145 replacetable.put(fon,newfon);
150 case FKind.FlatFieldNode:
152 FlatFieldNode ffn=(FlatFieldNode)fn;
153 Expression e=new Expression(ffn.getSrc(), ffn.getField());
154 if (tab.containsKey(e)) {
155 TempDescriptor t=tab.get(e);
156 FlatNode newfon=new FlatOpNode(ffn.getDst(),t,null,new Operation(Operation.ASSIGN));
157 replacetable.put(ffn,newfon);
162 case FKind.FlatElementNode:
164 FlatElementNode fen=(FlatElementNode)fn;
165 Expression e=new Expression(fen.getSrc(),fen.getIndex());
166 if (tab.containsKey(e)) {
167 TempDescriptor t=tab.get(e);
168 FlatNode newfon=new FlatOpNode(fen.getDst(),t,null,new Operation(Operation.ASSIGN));
169 replacetable.put(fen,newfon);
177 for(Iterator<FlatNode> it=replacetable.keySet().iterator(); it.hasNext(); ) {
178 FlatNode fn=it.next();
179 FlatNode newfn=replacetable.get(fn);
184 public Hashtable<Expression, TempDescriptor> computeIntersection(FlatNode fn, Hashtable<FlatNode,Hashtable<Expression, TempDescriptor>> availexpr) {
185 Hashtable<Expression, TempDescriptor> tab=new Hashtable<Expression, TempDescriptor>();
188 //compute intersection
189 for(int i=0; i<fn.numPrev(); i++) {
190 FlatNode prev=fn.getPrev(i);
192 if (availexpr.containsKey(prev)) {
193 tab.putAll(availexpr.get(prev));
197 if (availexpr.containsKey(prev)) {
198 Hashtable<Expression, TempDescriptor> table=availexpr.get(prev);
199 for(Iterator mapit=tab.entrySet().iterator(); mapit.hasNext(); ) {
200 Object entry=mapit.next();
201 if (!table.contains(entry))
210 public void killexpressions(Hashtable<Expression, TempDescriptor> tab, Set<FieldDescriptor> fields, Set<TypeDescriptor> arrays, boolean killall) {
211 for(Iterator it=tab.entrySet().iterator(); it.hasNext(); ) {
212 Map.Entry m=(Map.Entry)it.next();
213 Expression e=(Expression)m.getKey();
214 if (killall&&(e.f!=null||e.a!=null))
216 else if (e.f!=null&&fields!=null&&fields.contains(e.f))
218 else if ((e.a!=null)&&(arrays!=null)) {
219 for(Iterator<TypeDescriptor> arit=arrays.iterator(); arit.hasNext(); ) {
220 TypeDescriptor artd=arit.next();
221 if (typeutil.isSuperorType(artd,e.a.getType())||
222 typeutil.isSuperorType(e.a.getType(),artd)) {
237 Expression(TempDescriptor a, TempDescriptor b, Operation op) {
242 Expression(TempDescriptor a, FieldDescriptor f) {
246 Expression(TempDescriptor a, TempDescriptor index) {
250 public int hashCode() {
261 public boolean equals(Object o) {
262 Expression e=(Expression)o;
263 if (a!=e.a||f!=e.f||b!=e.b)
266 return op.getOp()==e.op.getOp();