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;
24 public DCWrapper(LocalityAnalysis locality, State state, TypeAnalysis typeanalysis, GlobalFieldType gft) {
25 delaycomp=new DelayComputation(locality, state, typeanalysis, gft);
26 delaycomp.doAnalysis();
28 this.locality=locality;
29 Set<LocalityBinding> localityset=locality.getLocalityBindings();
30 for(Iterator<LocalityBinding> lbit=localityset.iterator();lbit.hasNext();) {
31 processlb(lbit.next());
35 Hashtable<LocalityBinding, Set<FlatNode>> transmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
36 Hashtable<LocalityBinding, Set<FlatNode>> recordmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
37 Hashtable<LocalityBinding, Set<FlatNode>> othermap=new Hashtable<LocalityBinding, Set<FlatNode>>();
38 Hashtable<LocalityBinding, Set<FlatNode>> notreadymap=new Hashtable<LocalityBinding, Set<FlatNode>>();
39 Hashtable<LocalityBinding, HashSet<FlatNode>> cannotdelaymap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
40 Hashtable<LocalityBinding, Set<FlatNode>> derefmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
42 public DiscoverConflicts getConflicts() {
43 return delaycomp.getConflicts();
46 public Hashtable<LocalityBinding, HashSet<FlatNode>> getCannotDelayMap() {
47 return cannotdelaymap;
50 public boolean needsFission(LocalityBinding lb, FlatAtomicEnterNode faen) {
51 return transmap.get(lb).contains(faen);
54 public Set<TempDescriptor> liveinto(LocalityBinding lb, FlatAtomicEnterNode faen, Set<FlatNode> recordset) {
55 return delaycomp.liveinto(lb, faen, recordset);
58 public Set<TempDescriptor> alltemps(LocalityBinding lb, FlatAtomicEnterNode faen, Set<FlatNode> recordset) {
59 return delaycomp.alltemps(lb, faen, recordset);
62 public Set<TempDescriptor> liveout(LocalityBinding lb, FlatAtomicEnterNode faen) {
63 return delaycomp.liveout(lb, faen);
66 public Set<TempDescriptor> liveoutvirtualread(LocalityBinding lb, FlatAtomicEnterNode faen) {
67 return delaycomp.liveoutvirtualread(lb, faen);
70 private static HashSet<FlatNode> intersect(Set<FlatNode> a, Set<FlatNode> b) {
71 HashSet<FlatNode> intersect=new HashSet(b);
72 intersect.retainAll(a);
76 public Set<FlatNode> getDeref(LocalityBinding lb) {
77 return derefmap.get(lb);
80 public Set<FlatNode> getNotReady(LocalityBinding lb) {
81 return notreadymap.get(lb);
84 public Set<FlatNode> getCannotDelay(LocalityBinding lb) {
85 return cannotdelaymap.get(lb);
88 public Set<FlatNode> getOther(LocalityBinding lb) {
89 return othermap.get(lb);
92 public Set<FlatNode> livecode(LocalityBinding lb) {
93 return recordmap.get(lb);
96 private void processlb(LocalityBinding lb) {
97 transmap.put(lb, new HashSet<FlatNode>());
98 if (lb.isAtomic()||!lb.getHasAtomic())
101 Set<FlatNode> recordset=delaycomp.livecode(lb);
102 Set<FlatNode> cannotdelay=delaycomp.getCannotDelay(lb);
103 Set<FlatNode> otherset=delaycomp.getOther(lb);
104 Set<FlatNode> notreadyset=delaycomp.getNotReady(lb);
105 Set<FlatNode> derefset=(state.STMARRAY&&!state.DUALVIEW)?delaycomp.getDeref(lb):null;
106 Set<FlatNode> checkset=new HashSet<FlatNode>();
107 checkset.addAll(cannotdelay);
108 checkset.addAll(otherset);
110 Set<FlatNode> nrecordset=new HashSet<FlatNode>();
111 HashSet<FlatNode> ncannotdelay=new HashSet<FlatNode>();
112 Set<FlatNode> notherset=new HashSet<FlatNode>();
113 Set<FlatNode> nnotready=new HashSet<FlatNode>();
114 Set<FlatNode> nderef=new HashSet<FlatNode>();
116 recordmap.put(lb, nrecordset);
117 cannotdelaymap.put(lb, ncannotdelay);
118 notreadymap.put(lb, nnotready);
119 othermap.put(lb, notherset);
120 derefmap.put(lb, nderef);
122 FlatMethod fm=state.getMethodFlat(lb.getMethod());
123 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
124 FlatNode fn=fnit.next();
125 if (fn.kind()==FKind.FlatAtomicEnterNode&&
126 locality.getAtomic(lb).get(fn.getPrev(0)).intValue()==0) {
127 Set<FlatNode> transSet=computeTrans(lb, fn);
128 Set<FlatNode> tCheckSet=intersect(checkset, transSet);
129 Set<FlatNode> tRecordSet=intersect(recordset, transSet);
130 Set<FlatNode> tOtherSet=intersect(otherset, transSet);
131 Set<FlatNode> tNotReadySet=intersect(notreadyset, transSet);
132 HashSet<FlatNode> tCannotDelay=intersect(cannotdelay, transSet);
133 Set<FlatNode> tderef=(state.STMARRAY&&!state.DUALVIEW)?intersect(derefset, transSet):null;
135 if (checkSet(fn, tCheckSet, tRecordSet, lb)) {
136 //We will convert this one
137 nrecordset.addAll(tRecordSet);
138 notherset.addAll(tOtherSet);
139 nnotready.addAll(tNotReadySet);
140 ncannotdelay.addAll(tCannotDelay);
141 if (state.STMARRAY&&!state.DUALVIEW)
142 nderef.addAll(tderef);
143 transmap.get(lb).add(fn);
145 ncannotdelay.addAll(transSet);
147 if (!lwmap.containsKey(lb))
148 lwmap.put(lb, new HashSet<FlatNode>());
149 lwmap.get(lb).add(fn);
151 if (locality.getAtomic(lb).get(fn).intValue()==0)
152 ncannotdelay.add(fn);
157 Hashtable<LocalityBinding, Set<FlatNode>> lwmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
158 Hashtable<LocalityBinding, Set<FlatNode>> optmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
160 public boolean lightweightTrans(LocalityBinding lb, FlatNode fn) {
161 return lwmap.get(lb).contains(fn);
164 public boolean optimizeTrans(LocalityBinding lb, FlatNode fn) {
165 return optmap.get(lb).contains(fn);
168 private boolean checkSet(FlatNode faen, Set<FlatNode> checkset, Set<FlatNode> recordset, LocalityBinding lb) {
169 if (!optmap.containsKey(lb)) {
170 optmap.put(lb, new HashSet<FlatNode>());
172 DiscoverConflicts dc=delaycomp.getConflicts();
173 for(Iterator<FlatNode> fnit=checkset.iterator();fnit.hasNext();) {
174 FlatNode fn=fnit.next();
176 if (!state.READSET&&dc.getNeedTrans(lb, fn)||state.READSET&&dc.getNeedWriteTrans(lb, fn)) {
177 System.out.println("False because"+fn);
183 optmap.get(lb).add(faen);
187 private Set<FlatNode> computeTrans(LocalityBinding lb, FlatNode faen) {
188 HashSet<FlatNode> transSet=new HashSet<FlatNode>();
189 HashSet<FlatNode> toProcess=new HashSet<FlatNode>();
191 while(!toProcess.isEmpty()) {
192 FlatNode fn=toProcess.iterator().next();
193 toProcess.remove(fn);
195 if (locality.getAtomic(lb).get(fn).intValue()==0)
197 for(int i=0;i<fn.numNext();i++) {
198 if (!transSet.contains(fn.getNext(i)))
199 toProcess.add(fn.getNext(i));