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());
84 case FKind.FlatLiteralNode: {
85 FlatLiteralNode fln=(FlatLiteralNode)fn;
86 LocalExpression e=new LocalExpression(fln.getValue());
87 Group src=getGroup(table, e);
88 LocalExpression dst=new LocalExpression(fln.getDst());
90 kill(table, fln.getDst());
95 case FKind.FlatFieldNode: {
96 FlatFieldNode ffn=(FlatFieldNode) fn;
97 Group src=getGroup(table, ffn.getSrc());
98 LocalExpression e=new LocalExpression(src, ffn.getField());
99 Group srcf=getGroup(table, e);
100 LocalExpression dst=new LocalExpression(ffn.getDst());
101 TempDescriptor td=getTemp(srcf);
103 FlatOpNode fon=new FlatOpNode(ffn.getDst(),td,null,new Operation(Operation.ASSIGN));
107 kill(table, ffn.getDst());
108 table.put(dst, srcf);
112 case FKind.FlatElementNode: {
113 FlatElementNode fen=(FlatElementNode) fn;
114 Group src=getGroup(table, fen.getSrc());
115 Group index=getGroup(table, fen.getIndex());
116 LocalExpression e=new LocalExpression(src, fen.getSrc().getType(), index);
117 Group srcf=getGroup(table, e);
118 LocalExpression dst=new LocalExpression(fen.getDst());
119 TempDescriptor td=getTemp(srcf);
121 FlatOpNode fon=new FlatOpNode(fen.getDst(),td,null,new Operation(Operation.ASSIGN));
125 kill(table, fen.getDst());
126 table.put(dst, srcf);
130 case FKind.FlatSetFieldNode: {
131 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
132 Group dst=getGroup(table, fsfn.getDst());
133 LocalExpression e=new LocalExpression(dst, fsfn.getField());
134 Group dstf=getGroup(table, e);
135 LocalExpression src=new LocalExpression(fsfn.getSrc());
137 HashSet<FieldDescriptor> fields=new HashSet<FieldDescriptor>();
138 fields.add(fsfn.getField());
139 kill(table, fields, null, false, false);
140 table.put(src, dstf);
144 case FKind.FlatSetElementNode: {
145 FlatSetElementNode fsen=(FlatSetElementNode)fn;
146 Group dst=getGroup(table, fsen.getDst());
147 Group index=getGroup(table, fsen.getIndex());
148 LocalExpression e=new LocalExpression(dst, fsen.getDst().getType(), index);
149 Group dstf=getGroup(table, e);
150 LocalExpression src=new LocalExpression(fsen.getSrc());
152 HashSet<TypeDescriptor> arrays=new HashSet<TypeDescriptor>();
153 arrays.add(fsen.getDst().getType());
154 kill(table, null, arrays, false, false);
155 table.put(src, dstf);
159 case FKind.FlatCall: {
161 FlatCall fc=(FlatCall)fn;
162 MethodDescriptor md=fc.getMethod();
163 Set<FieldDescriptor> fields=gft.getFieldsAll(md);
164 Set<TypeDescriptor> arrays=gft.getArraysAll(md);
165 kill(table, fields, arrays, gft.containsAtomicAll(md), gft.containsBarrierAll(md));
169 TempDescriptor[] writes=fn.writesTemps();
170 for(int i=0; i<writes.length; i++) {
171 kill(table,writes[i]);
175 } while(fn.numPrev()==1);
178 public void kill(Hashtable<LocalExpression, Group> tab, Set<FieldDescriptor> fields, Set<TypeDescriptor> arrays, boolean isAtomic, boolean isBarrier) {
179 Set<LocalExpression> eset=tab.keySet();
180 for(Iterator<LocalExpression> it=eset.iterator(); it.hasNext(); ) {
181 LocalExpression e=it.next();
183 //make Barriers kill everything
185 } else if (isAtomic&&(e.td!=null||e.f!=null)) {
189 } else if (e.td!=null) {
191 TypeDescriptor artd=e.td;
192 for(Iterator<TypeDescriptor> arit=arrays.iterator(); arit.hasNext(); ) {
193 TypeDescriptor td=arit.next();
194 if (typeutil.isSuperorType(artd,td)||
195 typeutil.isSuperorType(td,artd)) {
202 } else if (e.f!=null) {
203 if (fields.contains(e.f)) {
211 public void kill(Hashtable<LocalExpression, Group> tab, TempDescriptor t) {
212 LocalExpression e=new LocalExpression(t);
228 public int hashCode() {
231 public boolean equals(Object o) {
237 class LocalExpression {
245 LocalExpression(TempDescriptor t) {
248 LocalExpression(Object o) {
251 LocalExpression(Group a, Group b, Operation op) {
256 LocalExpression(Group a, FieldDescriptor f) {
260 LocalExpression(Group a, TypeDescriptor td, Group index) {
265 public int hashCode() {
283 public static boolean equiv(Object a, Object b) {
290 public boolean equals(Object o) {
291 LocalExpression e=(LocalExpression)o;
292 if (!(equiv(a,e.a)&&equiv(f,e.f)&&equiv(b,e.b)&&
293 equiv(td,e.td)&&equiv(this.obj,e.obj)))
296 return op.getOp()==e.op.getOp();