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);
56 FlatCall fc=(FlatCall) fn;
57 MethodDescriptor md=fc.getMethod();
58 Set<FieldDescriptor> fields=gft.getFields(md);
59 Set<TypeDescriptor> arrays=gft.getArrays(md);
60 killexpressions(tab, fields, arrays, gft.containsAtomic(md));
63 case FKind.FlatOpNode:
65 FlatOpNode fon=(FlatOpNode) fn;
66 Expression e=new Expression(fon.getLeft(), fon.getRight(), fon.getOp());
67 tab.put(e, fon.getDest());
70 case FKind.FlatSetFieldNode:
72 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
73 Set<FieldDescriptor> fields=new HashSet<FieldDescriptor>();
74 fields.add(fsfn.getField());
75 killexpressions(tab, fields, null, false);
76 Expression e=new Expression(fsfn.getDst(), fsfn.getField());
77 tab.put(e, fsfn.getSrc());
80 case FKind.FlatFieldNode:
82 FlatFieldNode ffn=(FlatFieldNode)fn;
83 Expression e=new Expression(ffn.getSrc(), ffn.getField());
84 tab.put(e, ffn.getDst());
87 case FKind.FlatSetElementNode:
89 FlatSetElementNode fsen=(FlatSetElementNode)fn;
90 Expression e=new Expression(fsen.getDst(),fsen.getIndex());
91 tab.put(e, fsen.getSrc());
94 case FKind.FlatElementNode:
96 FlatElementNode fen=(FlatElementNode)fn;
97 Expression e=new Expression(fen.getSrc(),fen.getIndex());
98 tab.put(e, fen.getDst());
104 if (write.length==1) {
105 TempDescriptor w=write[0];
106 for(Iterator it=tab.entrySet().iterator();it.hasNext();) {
107 Map.Entry m=(Map.Entry)it.next();
108 Expression e=(Expression)m.getKey();
113 if (!availexpr.containsKey(fn)||!availexpr.get(fn).equals(tab)) {
114 availexpr.put(fn, tab);
115 for(int i=0;i<fn.numNext();i++) {
116 FlatNode nnext=fn.getNext(i);
117 toprocess.add(nnext);
122 doOptimize(fm, availexpr);
125 public void doOptimize(FlatMethod fm, Hashtable<FlatNode,Hashtable<Expression, TempDescriptor>> availexpr) {
126 Hashtable<FlatNode, FlatNode> replacetable=new Hashtable<FlatNode, FlatNode>();
127 for(Iterator<FlatNode> it=fm.getNodeSet().iterator();it.hasNext();) {
128 FlatNode fn=it.next();
129 Hashtable<Expression, TempDescriptor> tab=computeIntersection(fn, availexpr);
131 case FKind.FlatOpNode:
133 FlatOpNode fon=(FlatOpNode) fn;
134 Expression e=new Expression(fon.getLeft(), fon.getRight(),fon.getOp());
135 if (tab.containsKey(e)) {
136 TempDescriptor t=tab.get(e);
137 FlatNode newfon=new FlatOpNode(fon.getDest(),t,null,new Operation(Operation.ASSIGN));
138 replacetable.put(fon,newfon);
142 case FKind.FlatFieldNode:
144 FlatFieldNode ffn=(FlatFieldNode)fn;
145 Expression e=new Expression(ffn.getSrc(), ffn.getField());
146 if (tab.containsKey(e)) {
147 TempDescriptor t=tab.get(e);
148 FlatNode newfon=new FlatOpNode(ffn.getDst(),t,null,new Operation(Operation.ASSIGN));
149 replacetable.put(ffn,newfon);
153 case FKind.FlatElementNode:
155 FlatElementNode fen=(FlatElementNode)fn;
156 Expression e=new Expression(fen.getSrc(),fen.getIndex());
157 if (tab.containsKey(e)) {
158 TempDescriptor t=tab.get(e);
159 FlatNode newfon=new FlatOpNode(fen.getDst(),t,null,new Operation(Operation.ASSIGN));
160 replacetable.put(fen,newfon);
167 for(Iterator<FlatNode> it=replacetable.keySet().iterator();it.hasNext();) {
168 FlatNode fn=it.next();
169 FlatNode newfn=replacetable.get(fn);
174 public Hashtable<Expression, TempDescriptor> computeIntersection(FlatNode fn, Hashtable<FlatNode,Hashtable<Expression, TempDescriptor>> availexpr) {
175 Hashtable<Expression, TempDescriptor> tab=new Hashtable<Expression, TempDescriptor>();
178 //compute intersection
179 for(int i=0;i<fn.numPrev();i++) {
180 FlatNode prev=fn.getPrev(i);
182 if (availexpr.containsKey(prev)) {
183 tab.putAll(availexpr.get(prev));
187 if (availexpr.containsKey(prev)) {
188 Hashtable<Expression, TempDescriptor> table=availexpr.get(prev);
189 for(Iterator mapit=tab.entrySet().iterator();mapit.hasNext();) {
190 Object entry=mapit.next();
191 if (!table.contains(entry))
200 public void killexpressions(Hashtable<Expression, TempDescriptor> tab, Set<FieldDescriptor> fields, Set<TypeDescriptor> arrays, boolean killall) {
201 for(Iterator it=tab.entrySet().iterator();it.hasNext();) {
202 Map.Entry m=(Map.Entry)it.next();
203 Expression e=(Expression)m.getKey();
204 if (killall&&(e.f!=null||e.a!=null))
206 else if (e.f!=null&&fields!=null&&fields.contains(e.f))
208 else if ((e.a!=null)&&(arrays!=null)) {
209 for(Iterator<TypeDescriptor> arit=arrays.iterator();arit.hasNext();) {
210 TypeDescriptor artd=arit.next();
211 if (typeutil.isSuperorType(artd,e.a.getType())||
212 typeutil.isSuperorType(e.a.getType(),artd)) {
227 Expression(TempDescriptor a, TempDescriptor b, Operation op) {
232 Expression(TempDescriptor a, FieldDescriptor f) {
236 Expression(TempDescriptor a, TempDescriptor index) {
240 public int hashCode() {
251 public boolean equals(Object o) {
252 Expression e=(Expression)o;
253 if (a!=e.a||f!=e.f||b!=e.b)
256 return op.getOp()==e.op.getOp();