1 package Analysis.Loops;
3 import IR.MethodDescriptor;
4 import IR.TypeDescriptor;
8 import IR.FieldDescriptor;
10 import java.util.HashSet;
11 import java.util.Hashtable;
12 import java.util.Iterator;
14 public class localCSE {
17 public localCSE(GlobalFieldType gft, TypeUtil typeutil) {
19 this.typeutil=typeutil;
23 public Group getGroup(Hashtable<LocalExpression, Group> tab, TempDescriptor t) {
24 LocalExpression e=new LocalExpression(t);
25 return getGroup(tab, e);
27 public Group getGroup(Hashtable<LocalExpression, Group> tab, LocalExpression e) {
28 if (tab.containsKey(e))
31 Group g=new Group(index++);
37 public TempDescriptor getTemp(Group g) {
38 for(Iterator it=g.set.iterator();it.hasNext();) {
39 LocalExpression e=(LocalExpression)it.next();
46 public void doAnalysis(FlatMethod fm) {
47 Set nodes=fm.getNodeSet();
48 HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
49 for(Iterator it=nodes.iterator();it.hasNext();) {
50 FlatNode fn=(FlatNode)it.next();
54 for(Iterator<FlatNode> it=toanalyze.iterator();it.hasNext();) {
55 FlatNode fn=it.next();
56 Hashtable<LocalExpression, Group> table=new Hashtable<LocalExpression,Group>();
60 case FKind.FlatOpNode: {
61 FlatOpNode fon=(FlatOpNode)fn;
62 Group left=getGroup(table, fon.getLeft());
63 Group right=getGroup(table, fon.getRight());
64 LocalExpression dst=new LocalExpression(fon.getDest());
65 if (fon.getOp().getOp()==Operation.ASSIGN) {
67 kill(table, fon.getDest());
70 LocalExpression e=new LocalExpression(left, right, fon.getOp());
71 Group g=getGroup(table,e);
72 TempDescriptor td=getTemp(g);
74 FlatNode nfon=new FlatOpNode(fon.getDest(),td,null,new Operation(Operation.ASSIGN));
78 kill(table, fon.getDest());
83 case FKind.FlatLiteralNode: {
84 FlatLiteralNode fln=(FlatLiteralNode)fn;
85 LocalExpression e=new LocalExpression(fln.getValue());
86 Group src=getGroup(table, e);
87 LocalExpression dst=new LocalExpression(fln.getDst());
89 kill(table, fln.getDst());
93 case FKind.FlatFieldNode: {
94 FlatFieldNode ffn=(FlatFieldNode) fn;
95 Group src=getGroup(table, ffn.getSrc());
96 LocalExpression e=new LocalExpression(src, ffn.getField());
97 Group srcf=getGroup(table, e);
98 LocalExpression dst=new LocalExpression(ffn.getDst());
99 TempDescriptor td=getTemp(srcf);
101 FlatOpNode fon=new FlatOpNode(ffn.getDst(),td,null,new Operation(Operation.ASSIGN));
105 kill(table, ffn.getDst());
106 table.put(dst, srcf);
109 case FKind.FlatElementNode: {
110 FlatElementNode fen=(FlatElementNode) fn;
111 Group src=getGroup(table, fen.getSrc());
112 Group index=getGroup(table, fen.getIndex());
113 LocalExpression e=new LocalExpression(src, fen.getSrc().getType(), index);
114 Group srcf=getGroup(table, e);
115 LocalExpression dst=new LocalExpression(fen.getDst());
116 TempDescriptor td=getTemp(srcf);
118 FlatOpNode fon=new FlatOpNode(fen.getDst(),td,null,new Operation(Operation.ASSIGN));
122 kill(table, fen.getDst());
123 table.put(dst, srcf);
126 case FKind.FlatSetFieldNode: {
127 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
128 Group dst=getGroup(table, fsfn.getDst());
129 LocalExpression e=new LocalExpression(dst, fsfn.getField());
130 Group dstf=getGroup(table, e);
131 LocalExpression src=new LocalExpression(fsfn.getSrc());
133 HashSet<FieldDescriptor> fields=new HashSet<FieldDescriptor>();
134 fields.add(fsfn.getField());
135 kill(table, fields, null, false, false);
136 table.put(src, dstf);
139 case FKind.FlatSetElementNode: {
140 FlatSetElementNode fsen=(FlatSetElementNode)fn;
141 Group dst=getGroup(table, fsen.getDst());
142 Group index=getGroup(table, fsen.getIndex());
143 LocalExpression e=new LocalExpression(dst, fsen.getDst().getType(), index);
144 Group dstf=getGroup(table, e);
145 LocalExpression src=new LocalExpression(fsen.getSrc());
147 HashSet<TypeDescriptor> arrays=new HashSet<TypeDescriptor>();
148 arrays.add(fsen.getDst().getType());
149 kill(table, null, arrays, false, false);
150 table.put(src, dstf);
153 case FKind.FlatCall:{
155 FlatCall fc=(FlatCall)fn;
156 MethodDescriptor md=fc.getMethod();
157 Set<FieldDescriptor> fields=gft.getFieldsAll(md);
158 Set<TypeDescriptor> arrays=gft.getArraysAll(md);
159 kill(table, fields, arrays, gft.containsAtomicAll(md), gft.containsBarrierAll(md));
162 TempDescriptor[] writes=fn.writesTemps();
163 for(int i=0;i<writes.length;i++) {
164 kill(table,writes[i]);
168 } while(fn.numPrev()==1);
171 public void kill(Hashtable<LocalExpression, Group> tab, Set<FieldDescriptor> fields, Set<TypeDescriptor> arrays, boolean isAtomic, boolean isBarrier) {
172 Set<LocalExpression> eset=tab.keySet();
173 for(Iterator<LocalExpression> it=eset.iterator();it.hasNext();) {
174 LocalExpression e=it.next();
176 //make Barriers kill everything
178 } else if (isAtomic&&(e.td!=null||e.f!=null)) {
182 } else if (e.td!=null) {
184 TypeDescriptor artd=e.td;
185 for(Iterator<TypeDescriptor> arit=arrays.iterator();arit.hasNext();) {
186 TypeDescriptor td=arit.next();
187 if (typeutil.isSuperorType(artd,td)||
188 typeutil.isSuperorType(td,artd)) {
195 } else if (e.f!=null) {
196 if (fields.contains(e.f)) {
204 public void kill(Hashtable<LocalExpression, Group> tab, TempDescriptor t) {
205 LocalExpression e=new LocalExpression(t);
221 public int hashCode() {
224 public boolean equals(Object o) {
230 class LocalExpression {
238 LocalExpression(TempDescriptor t) {
241 LocalExpression(Object o) {
244 LocalExpression(Group a, Group b, Operation op) {
249 LocalExpression(Group a, FieldDescriptor f) {
253 LocalExpression(Group a, TypeDescriptor td, Group index) {
258 public int hashCode() {
276 public static boolean equiv(Object a, Object b) {
283 public boolean equals(Object o) {
284 LocalExpression e=(LocalExpression)o;
285 if (!(equiv(a,e.a)&&equiv(f,e.f)&&equiv(b,e.b)&&
286 equiv(td,e.td)&&equiv(this.obj,e.obj)))
289 return op.getOp()==e.op.getOp();