1 package Analysis.Locality;
2 import Analysis.Liveness;
3 import Analysis.ReachingDefs;
4 import Analysis.Loops.DomTree;
6 import IR.MethodDescriptor;
7 import IR.TypeDescriptor;
8 import IR.FieldDescriptor;
10 import Analysis.Loops.GlobalFieldType;
11 import java.util.HashSet;
12 import java.util.Hashtable;
14 import java.util.List;
15 import java.util.Arrays;
16 import java.util.Stack;
17 import java.util.Iterator;
19 public class DCWrapper {
20 DelayComputation delaycomp;
22 LocalityAnalysis locality;
23 TypeAnalysis typeanalysis;
26 public DCWrapper(LocalityAnalysis locality, State state, TypeAnalysis typeanalysis, GlobalFieldType gft) {
27 delaycomp=new DelayComputation(locality, state, typeanalysis, gft);
28 delaycomp.doAnalysis();
30 this.locality=locality;
31 this.typeanalysis=typeanalysis;
33 Set<LocalityBinding> localityset=locality.getLocalityBindings();
34 for(Iterator<LocalityBinding> lbit=localityset.iterator();lbit.hasNext();) {
35 processlb(lbit.next());
39 Hashtable<LocalityBinding, Set<FlatNode>> transmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
40 Hashtable<LocalityBinding, Set<FlatNode>> recordmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
41 Hashtable<LocalityBinding, Set<FlatNode>> othermap=new Hashtable<LocalityBinding, Set<FlatNode>>();
42 Hashtable<LocalityBinding, Set<FlatNode>> notreadymap=new Hashtable<LocalityBinding, Set<FlatNode>>();
43 Hashtable<LocalityBinding, HashSet<FlatNode>> cannotdelaymap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
44 Hashtable<LocalityBinding, Set<FlatNode>> derefmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
45 Hashtable<LocalityBinding, Set<FlatNode>> convmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
47 public DiscoverConflicts getConflicts() {
48 DiscoverConflicts dc=new DiscoverConflicts(locality, state, typeanalysis, cannotdelaymap, false, false, state.READSET?gft:null);
53 public Hashtable<LocalityBinding, HashSet<FlatNode>> getCannotDelayMap() {
54 return cannotdelaymap;
57 public boolean needsFission(LocalityBinding lb, FlatAtomicEnterNode faen) {
58 return transmap.get(lb).contains(faen);
61 public Set<TempDescriptor> liveinto(LocalityBinding lb, FlatAtomicEnterNode faen, Set<FlatNode> recordset) {
62 return delaycomp.liveinto(lb, faen, recordset);
65 public Set<TempDescriptor> alltemps(LocalityBinding lb, FlatAtomicEnterNode faen, Set<FlatNode> recordset) {
66 return delaycomp.alltemps(lb, faen, recordset);
69 public Set<TempDescriptor> liveout(LocalityBinding lb, FlatAtomicEnterNode faen) {
70 return delaycomp.liveout(lb, faen);
73 public Set<TempDescriptor> liveoutvirtualread(LocalityBinding lb, FlatAtomicEnterNode faen) {
74 return delaycomp.liveoutvirtualread(lb, faen);
77 private static HashSet<FlatNode> intersect(Set<FlatNode> a, Set<FlatNode> b) {
78 HashSet<FlatNode> intersect=new HashSet(b);
79 intersect.retainAll(a);
83 public Set<FlatNode> getDeref(LocalityBinding lb) {
84 return derefmap.get(lb);
87 public Set<FlatNode> getNotReady(LocalityBinding lb) {
88 return notreadymap.get(lb);
91 public Set<FlatNode> getCannotDelay(LocalityBinding lb) {
92 return cannotdelaymap.get(lb);
95 public Set<FlatNode> getOther(LocalityBinding lb) {
96 return othermap.get(lb);
99 public Set<FlatNode> getConv(LocalityBinding lb) {
100 return convmap.get(lb);
103 public Set<FlatNode> livecode(LocalityBinding lb) {
104 return recordmap.get(lb);
107 private void processlb(LocalityBinding lb) {
108 transmap.put(lb, new HashSet<FlatNode>());
109 Set<FlatNode> convset=new HashSet<FlatNode>();
110 convmap.put(lb, convset);
111 if (lb.isAtomic()||!lb.getHasAtomic())
114 Set<FlatNode> recordset=delaycomp.livecode(lb);
115 Set<FlatNode> cannotdelay=delaycomp.getCannotDelay(lb);
116 Set<FlatNode> otherset=delaycomp.getOther(lb);
117 Set<FlatNode> notreadyset=delaycomp.getNotReady(lb);
118 Set<FlatNode> derefset=(state.STMARRAY&&!state.DUALVIEW)?delaycomp.getDeref(lb):null;
119 Set<FlatNode> checkset=new HashSet<FlatNode>();
120 checkset.addAll(cannotdelay);
121 checkset.addAll(otherset);
123 Set<FlatNode> nrecordset=new HashSet<FlatNode>();
124 HashSet<FlatNode> ncannotdelay=new HashSet<FlatNode>();
125 Set<FlatNode> notherset=new HashSet<FlatNode>();
126 Set<FlatNode> nnotready=new HashSet<FlatNode>();
127 Set<FlatNode> nderef=new HashSet<FlatNode>();
130 recordmap.put(lb, nrecordset);
131 cannotdelaymap.put(lb, ncannotdelay);
132 notreadymap.put(lb, nnotready);
133 othermap.put(lb, notherset);
134 derefmap.put(lb, nderef);
137 FlatMethod fm=state.getMethodFlat(lb.getMethod());
138 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
139 FlatNode fn=fnit.next();
140 if (fn.kind()==FKind.FlatAtomicEnterNode&&
141 locality.getAtomic(lb).get(fn.getPrev(0)).intValue()==0) {
142 Set<FlatNode> transSet=computeTrans(lb, fn);
143 Set<FlatNode> tCheckSet=intersect(checkset, transSet);
144 Set<FlatNode> tRecordSet=intersect(recordset, transSet);
145 Set<FlatNode> tOtherSet=intersect(otherset, transSet);
146 Set<FlatNode> tNotReadySet=intersect(notreadyset, transSet);
147 HashSet<FlatNode> tCannotDelay=intersect(cannotdelay, transSet);
148 Set<FlatNode> tderef=(state.STMARRAY&&!state.DUALVIEW)?intersect(derefset, transSet):null;
150 if (checkSet(fn, tCheckSet, tRecordSet, lb)) {
151 //We will convert this one
152 nrecordset.addAll(tRecordSet);
153 notherset.addAll(tOtherSet);
154 nnotready.addAll(tNotReadySet);
155 ncannotdelay.addAll(tCannotDelay);
156 if (state.STMARRAY&&!state.DUALVIEW)
157 nderef.addAll(tderef);
158 transmap.get(lb).add(fn);
159 convset.addAll(transSet);
161 ncannotdelay.addAll(transSet);
163 if (!lwmap.containsKey(lb))
164 lwmap.put(lb, new HashSet<FlatNode>());
165 lwmap.get(lb).add(fn);
167 if (locality.getAtomic(lb).get(fn).intValue()==0)
168 ncannotdelay.add(fn);
173 Hashtable<LocalityBinding, Set<FlatNode>> lwmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
174 Hashtable<LocalityBinding, Set<FlatNode>> optmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
176 public boolean lightweightTrans(LocalityBinding lb, FlatNode fn) {
177 return lwmap.get(lb).contains(fn);
180 public boolean optimizeTrans(LocalityBinding lb, FlatNode fn) {
181 return optmap.get(lb).contains(fn);
184 private boolean checkSet(FlatNode faen, Set<FlatNode> checkset, Set<FlatNode> recordset, LocalityBinding lb) {
185 if (!optmap.containsKey(lb)) {
186 optmap.put(lb, new HashSet<FlatNode>());
189 if (state.HYBRID&&recordset.size()>6)
192 DiscoverConflicts dc=delaycomp.getConflicts();
193 for(Iterator<FlatNode> fnit=checkset.iterator();fnit.hasNext();) {
194 FlatNode fn=fnit.next();
196 if (!state.READSET&&dc.getNeedTrans(lb, fn)||state.READSET&&dc.getNeedWriteTrans(lb, fn)||fn.kind()==FKind.FlatCall) {
197 System.out.println("False because"+fn);
203 optmap.get(lb).add(faen);
207 private Set<FlatNode> computeTrans(LocalityBinding lb, FlatNode faen) {
208 HashSet<FlatNode> transSet=new HashSet<FlatNode>();
209 HashSet<FlatNode> toProcess=new HashSet<FlatNode>();
211 while(!toProcess.isEmpty()) {
212 FlatNode fn=toProcess.iterator().next();
213 toProcess.remove(fn);
215 if (locality.getAtomic(lb).get(fn).intValue()==0)
217 for(int i=0;i<fn.numNext();i++) {
218 if (!transSet.contains(fn.getNext(i)))
219 toProcess.add(fn.getNext(i));