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=new Hashtable<Expression, TempDescriptor>();
43 //compute intersection
44 for(int i=0;i<fn.numPrev();i++) {
45 FlatNode prev=fn.getPrev(i);
47 if (availexpr.containsKey(prev))
48 tab.putAll(availexpr.get(prev));
51 if (availexpr.containsKey(prev)) {
52 Hashtable<Expression, TempDescriptor> table=availexpr.get(prev);
53 for(Iterator mapit=tab.entrySet().iterator();mapit.hasNext();) {
54 Object entry=mapit.next();
55 if (!table.contains(entry))
61 //Do kills of expression/variable mappings
62 TempDescriptor[] write=fn.writesTemps();
63 for(int i=0;i<write.length;i++) {
64 if (tab.containsKey(write[i]))
71 FlatCall fc=(FlatCall) fn;
72 MethodDescriptor md=fc.getMethod();
73 Set<FieldDescriptor> fields=gft.getFields(md);
74 Set<TypeDescriptor> arrays=gft.getArrays(md);
75 killexpressions(tab, fields, arrays);
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());
85 case FKind.FlatSetFieldNode:
87 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
88 Set<FieldDescriptor> fields=new HashSet<FieldDescriptor>();
89 fields.add(fsfn.getField());
90 killexpressions(tab, fields, null);
91 Expression e=new Expression(fsfn.getDst(), fsfn.getField());
92 tab.put(e, fsfn.getSrc());
95 case FKind.FlatFieldNode:
97 FlatFieldNode ffn=(FlatFieldNode)fn;
98 Expression e=new Expression(ffn.getSrc(), ffn.getField());
99 tab.put(e, ffn.getDst());
102 case FKind.FlatSetElementNode:
104 FlatSetElementNode fsen=(FlatSetElementNode)fn;
105 Expression e=new Expression(fsen.getDst(),fsen.getIndex());
106 tab.put(e, fsen.getSrc());
109 case FKind.FlatElementNode:
111 FlatElementNode fen=(FlatElementNode)fn;
112 Expression e=new Expression(fen.getSrc(),fen.getIndex());
113 tab.put(e, fen.getDst());
119 if (write.length==1) {
120 TempDescriptor w=write[0];
121 for(Iterator it=tab.entrySet().iterator();it.hasNext();) {
122 Map.Entry m=(Map.Entry)it.next();
123 Expression e=(Expression)m.getKey();
128 if (!availexpr.containsKey(fn)||!availexpr.get(fn).equals(tab)) {
129 availexpr.put(fn, tab);
130 for(int i=0;i<fn.numNext();i++) {
131 FlatNode nnext=fn.getNext(i);
132 toprocess.add(nnext);
138 public void killexpressions(Hashtable<Expression, TempDescriptor> tab, Set<FieldDescriptor> fields, Set<TypeDescriptor> arrays) {
139 for(Iterator it=tab.entrySet().iterator();it.hasNext();) {
140 Map.Entry m=(Map.Entry)it.next();
141 Expression e=(Expression)m.getKey();
142 if (e.f!=null&&fields!=null&&fields.contains(e.f))
144 else if ((e.a!=null)&&(arrays!=null)) {
145 for(Iterator<TypeDescriptor> arit=arrays.iterator();arit.hasNext();) {
146 TypeDescriptor artd=arit.next();
147 if (typeutil.isSuperorType(artd,e.a.getType())||
148 typeutil.isSuperorType(e.a.getType(),artd)) {
163 Expression(TempDescriptor a, TempDescriptor b, Operation op) {
168 Expression(TempDescriptor a, FieldDescriptor f) {
172 Expression(TempDescriptor a, TempDescriptor index) {
176 public int hashCode() {
187 public boolean equals(Object o) {
188 Expression e=(Expression)o;
189 if (a!=e.a||f!=e.f||b!=e.b)
192 return op.getOp()==e.op.getOp();