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 // if(tab.size()>1000){
42 // System.out.println("Skipping CSE of "+fm.getMethod()+" due to size.");
46 //Do kills of expression/variable mappings
47 TempDescriptor[] write=fn.writesTemps();
48 for(int i=0; i<write.length; i++) {
49 for(Iterator it=tab.entrySet().iterator(); it.hasNext(); ) {
50 Map.Entry m=(Map.Entry)it.next();
51 TempDescriptor td=(TempDescriptor)m.getValue();
52 if(td.equals(write[i])){
62 case FKind.FlatAtomicEnterNode:
64 killexpressions(tab, null, null, true);
70 FlatCall fc=(FlatCall) fn;
71 MethodDescriptor md=fc.getMethod();
72 Set<FieldDescriptor> fields=gft.getFieldsAll(md);
73 Set<TypeDescriptor> arrays=gft.getArraysAll(md);
74 killexpressions(tab, fields, arrays, gft.containsAtomicAll(md)||gft.containsBarrierAll(md));
78 case FKind.FlatOpNode:
80 FlatOpNode fon=(FlatOpNode) fn;
81 Expression e=new Expression(fon.getLeft(), fon.getRight(), fon.getOp());
82 tab.put(e, fon.getDest());
86 case FKind.FlatSetFieldNode:
88 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
89 Set<FieldDescriptor> fields=new HashSet<FieldDescriptor>();
90 fields.add(fsfn.getField());
91 killexpressions(tab, fields, null, false);
92 Expression e=new Expression(fsfn.getDst(), fsfn.getField());
93 tab.put(e, fsfn.getSrc());
97 case FKind.FlatFieldNode:
99 FlatFieldNode ffn=(FlatFieldNode)fn;
100 Expression e=new Expression(ffn.getSrc(), ffn.getField());
101 tab.put(e, ffn.getDst());
105 case FKind.FlatSetElementNode:
107 FlatSetElementNode fsen=(FlatSetElementNode)fn;
108 Expression e=new Expression(fsen.getDst(),fsen.getIndex());
109 tab.put(e, fsen.getSrc());
113 case FKind.FlatElementNode:
115 FlatElementNode fen=(FlatElementNode)fn;
116 Expression e=new Expression(fen.getSrc(),fen.getIndex());
117 tab.put(e, fen.getDst());
124 if (write.length==1) {
125 TempDescriptor w=write[0];
126 for(Iterator it=tab.entrySet().iterator(); it.hasNext(); ) {
127 Map.Entry m=(Map.Entry)it.next();
128 Expression e=(Expression)m.getKey();
133 if (!availexpr.containsKey(fn)||!availexpr.get(fn).equals(tab)) {
134 availexpr.put(fn, tab);
135 for(int i=0; i<fn.numNext(); i++) {
136 FlatNode nnext=fn.getNext(i);
137 toprocess.add(nnext);
142 doOptimize(fm, availexpr);
145 public void doOptimize(FlatMethod fm, Hashtable<FlatNode,Hashtable<Expression, TempDescriptor>> availexpr) {
146 Hashtable<FlatNode, FlatNode> replacetable=new Hashtable<FlatNode, FlatNode>();
147 for(Iterator<FlatNode> it=fm.getNodeSet().iterator(); it.hasNext(); ) {
148 FlatNode fn=it.next();
149 Hashtable<Expression, TempDescriptor> tab=computeIntersection(fn, availexpr);
151 case FKind.FlatOpNode:
153 FlatOpNode fon=(FlatOpNode) fn;
154 Expression e=new Expression(fon.getLeft(), fon.getRight(),fon.getOp());
155 if (tab.containsKey(e)) {
156 TempDescriptor t=tab.get(e);
157 FlatNode newfon=new FlatOpNode(fon.getDest(),t,null,new Operation(Operation.ASSIGN));
158 replacetable.put(fon,newfon);
163 case FKind.FlatFieldNode:
165 FlatFieldNode ffn=(FlatFieldNode)fn;
166 Expression e=new Expression(ffn.getSrc(), ffn.getField());
167 if (tab.containsKey(e)) {
168 TempDescriptor t=tab.get(e);
169 FlatNode newfon=new FlatOpNode(ffn.getDst(),t,null,new Operation(Operation.ASSIGN));
170 replacetable.put(ffn,newfon);
175 case FKind.FlatElementNode:
177 FlatElementNode fen=(FlatElementNode)fn;
178 Expression e=new Expression(fen.getSrc(),fen.getIndex());
179 if (tab.containsKey(e)) {
180 TempDescriptor t=tab.get(e);
181 FlatNode newfon=new FlatOpNode(fen.getDst(),t,null,new Operation(Operation.ASSIGN));
182 replacetable.put(fen,newfon);
190 for(Iterator<FlatNode> it=replacetable.keySet().iterator(); it.hasNext(); ) {
191 FlatNode fn=it.next();
192 FlatNode newfn=replacetable.get(fn);
197 public Hashtable<Expression, TempDescriptor> computeIntersection(FlatNode fn, Hashtable<FlatNode,Hashtable<Expression, TempDescriptor>> availexpr) {
198 Hashtable<Expression, TempDescriptor> tab=new Hashtable<Expression, TempDescriptor>();
201 //compute intersection
202 for(int i=0; i<fn.numPrev(); i++) {
203 FlatNode prev=fn.getPrev(i);
205 if (availexpr.containsKey(prev)) {
206 tab.putAll(availexpr.get(prev));
210 if (availexpr.containsKey(prev)) {
211 Hashtable<Expression, TempDescriptor> table=availexpr.get(prev);
212 for(Iterator mapit=tab.entrySet().iterator(); mapit.hasNext(); ) {
213 Object entry=mapit.next();
214 if (!table.contains(entry))
223 public void killexpressions(Hashtable<Expression, TempDescriptor> tab, Set<FieldDescriptor> fields, Set<TypeDescriptor> arrays, boolean killall) {
224 for(Iterator it=tab.entrySet().iterator(); it.hasNext(); ) {
225 Map.Entry m=(Map.Entry)it.next();
226 Expression e=(Expression)m.getKey();
227 if (killall&&(e.f!=null||e.a!=null))
229 else if (e.f!=null&&fields!=null&&fields.contains(e.f))
231 else if ((e.a!=null)&&(arrays!=null)) {
232 for(Iterator<TypeDescriptor> arit=arrays.iterator(); arit.hasNext(); ) {
233 TypeDescriptor artd=arit.next();
234 if (typeutil.isSuperorType(artd,e.a.getType())||
235 typeutil.isSuperorType(e.a.getType(),artd)) {
250 Expression(TempDescriptor a, TempDescriptor b, Operation op) {
255 Expression(TempDescriptor a, FieldDescriptor f) {
259 Expression(TempDescriptor a, TempDescriptor index) {
263 public int hashCode() {
274 public boolean equals(Object o) {
275 Expression e=(Expression)o;
276 if (a!=e.a||f!=e.f||b!=e.b)
279 return op.getOp()==e.op.getOp();