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>>();
26 HashSet toprocess=new HashSet();
27 HashSet discovered=new HashSet();
30 while(!toprocess.isEmpty()) {
31 FlatNode fn=(FlatNode)toprocess.iterator().next();
33 for(int i=0;i<fn.numNext();i++) {
34 FlatNode nnext=fn.getNext(i);
35 if (!discovered.contains(nnext)) {
37 discovered.add(nnext);
40 Hashtable<Expression, TempDescriptor> tab=computeIntersection(fn, availexpr);
42 //Do kills of expression/variable mappings
43 TempDescriptor[] write=fn.writesTemps();
44 for(int i=0;i<write.length;i++) {
45 if (tab.containsKey(write[i]))
52 FlatCall fc=(FlatCall) fn;
53 MethodDescriptor md=fc.getMethod();
54 Set<FieldDescriptor> fields=gft.getFields(md);
55 Set<TypeDescriptor> arrays=gft.getArrays(md);
56 killexpressions(tab, fields, arrays);
59 case FKind.FlatOpNode:
61 FlatOpNode fon=(FlatOpNode) fn;
62 Expression e=new Expression(fon.getLeft(), fon.getRight(),fon.getOp());
63 tab.put(e, fon.getDest());
66 case FKind.FlatSetFieldNode:
68 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
69 Set<FieldDescriptor> fields=new HashSet<FieldDescriptor>();
70 fields.add(fsfn.getField());
71 killexpressions(tab, fields, null);
72 Expression e=new Expression(fsfn.getDst(), fsfn.getField());
73 tab.put(e, fsfn.getSrc());
76 case FKind.FlatFieldNode:
78 FlatFieldNode ffn=(FlatFieldNode)fn;
79 Expression e=new Expression(ffn.getSrc(), ffn.getField());
80 tab.put(e, ffn.getDst());
83 case FKind.FlatSetElementNode:
85 FlatSetElementNode fsen=(FlatSetElementNode)fn;
86 Expression e=new Expression(fsen.getDst(),fsen.getIndex());
87 tab.put(e, fsen.getSrc());
90 case FKind.FlatElementNode:
92 FlatElementNode fen=(FlatElementNode)fn;
93 Expression e=new Expression(fen.getSrc(),fen.getIndex());
94 tab.put(e, fen.getDst());
100 if (write.length==1) {
101 TempDescriptor w=write[0];
102 for(Iterator it=tab.entrySet().iterator();it.hasNext();) {
103 Map.Entry m=(Map.Entry)it.next();
104 Expression e=(Expression)m.getKey();
109 if (!availexpr.containsKey(fn)||!availexpr.get(fn).equals(tab)) {
110 availexpr.put(fn, tab);
111 for(int i=0;i<fn.numNext();i++) {
112 FlatNode nnext=fn.getNext(i);
113 toprocess.add(nnext);
117 doOptimize(fm, availexpr);
120 public void doOptimize(FlatMethod fm, Hashtable<FlatNode,Hashtable<Expression, TempDescriptor>> availexpr) {
121 for(Iterator<FlatNode> it=fm.getNodeSet().iterator();it.hasNext();) {
122 FlatNode fn=it.next();
123 Hashtable<Expression, TempDescriptor> tab=computeIntersection(fn, availexpr);
125 case FKind.FlatOpNode:
127 FlatOpNode fon=(FlatOpNode) fn;
128 Expression e=new Expression(fon.getLeft(), fon.getRight(),fon.getOp());
129 if (tab.containsKey(e)) {
130 TempDescriptor t=tab.get(e);
131 FlatOpNode newfon=new FlatOpNode(fon.getDest(),t,null,new Operation(Operation.ASSIGN));
136 case FKind.FlatFieldNode:
138 FlatFieldNode ffn=(FlatFieldNode)fn;
139 Expression e=new Expression(ffn.getSrc(), ffn.getField());
140 if (tab.containsKey(e)) {
141 TempDescriptor t=tab.get(e);
142 FlatOpNode newfon=new FlatOpNode(ffn.getDst(),t,null,new Operation(Operation.ASSIGN));
147 case FKind.FlatElementNode:
149 FlatElementNode fen=(FlatElementNode)fn;
150 Expression e=new Expression(fen.getSrc(),fen.getIndex());
151 if (tab.containsKey(e)) {
152 TempDescriptor t=tab.get(e);
153 FlatOpNode newfon=new FlatOpNode(fen.getDst(),t,null,new Operation(Operation.ASSIGN));
163 public Hashtable<Expression, TempDescriptor> computeIntersection(FlatNode fn, Hashtable<FlatNode,Hashtable<Expression, TempDescriptor>> availexpr) {
164 Hashtable<Expression, TempDescriptor> tab=new Hashtable<Expression, TempDescriptor>();
167 //compute intersection
168 for(int i=0;i<fn.numPrev();i++) {
169 FlatNode prev=fn.getPrev(i);
171 if (availexpr.containsKey(prev))
172 tab.putAll(availexpr.get(prev));
175 if (availexpr.containsKey(prev)) {
176 Hashtable<Expression, TempDescriptor> table=availexpr.get(prev);
177 for(Iterator mapit=tab.entrySet().iterator();mapit.hasNext();) {
178 Object entry=mapit.next();
179 if (!table.contains(entry))
188 public void killexpressions(Hashtable<Expression, TempDescriptor> tab, Set<FieldDescriptor> fields, Set<TypeDescriptor> arrays) {
189 for(Iterator it=tab.entrySet().iterator();it.hasNext();) {
190 Map.Entry m=(Map.Entry)it.next();
191 Expression e=(Expression)m.getKey();
192 if (e.f!=null&&fields!=null&&fields.contains(e.f))
194 else if ((e.a!=null)&&(arrays!=null)) {
195 for(Iterator<TypeDescriptor> arit=arrays.iterator();arit.hasNext();) {
196 TypeDescriptor artd=arit.next();
197 if (typeutil.isSuperorType(artd,e.a.getType())||
198 typeutil.isSuperorType(e.a.getType(),artd)) {
213 Expression(TempDescriptor a, TempDescriptor b, Operation op) {
218 Expression(TempDescriptor a, FieldDescriptor f) {
222 Expression(TempDescriptor a, TempDescriptor index) {
226 public int hashCode() {
237 public boolean equals(Object o) {
238 Expression e=(Expression)o;
239 if (a!=e.a||f!=e.f||b!=e.b)
242 return op.getOp()==e.op.getOp();