4 import java.util.HashSet;
6 import java.util.Iterator;
7 import java.util.Hashtable;
8 import Analysis.Locality.*;
10 public class ReachingDefs {
11 /* This methods takes in a FlatMethod and returns a map from a
12 * FlatNode to the set of live temps for that FlatNode.*/
14 /* liveintoset if true computes the reaching defs into the node and if false computes the reaching defs out of the node. */
16 public static Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> computeReachingDefs(FlatMethod fm, Hashtable<FlatNode, Set<TempDescriptor>> livemap, boolean liveintoset) {
17 return computeReachingDefs(fm, livemap, liveintoset, null);
20 public static Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> computeReachingDefs(FlatMethod fm, Hashtable<FlatNode, Set<TempDescriptor>> livemap, boolean liveintoset, LocalityBinding lb) {
21 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> nodetotemps=new Hashtable<FlatNode, Hashtable<TempDescriptor,Set<FlatNode>>>();
23 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> liveinto=liveintoset?new Hashtable<FlatNode, Hashtable<TempDescriptor,Set<FlatNode>>>():null;
26 Set<FlatNode> toprocess=fm.getNodeSet();
28 while(!toprocess.isEmpty()) {
29 FlatNode fn=toprocess.iterator().next();
32 Hashtable<TempDescriptor, Set<FlatNode>> tempset=new Hashtable<TempDescriptor, Set<FlatNode>>();
34 Set<TempDescriptor> livetempset=livemap.get(fn);
36 for(int i=0; i<fn.numPrev(); i++) {
37 FlatNode fnprev=fn.getPrev(i);
38 if (nodetotemps.containsKey(fnprev)) {
39 Hashtable<TempDescriptor,Set<FlatNode>> prevtable=nodetotemps.get(fnprev);
40 for(Iterator<TempDescriptor> tmpit=prevtable.keySet().iterator();tmpit.hasNext();) {
41 TempDescriptor tmp=tmpit.next();
42 if (!livetempset.contains(tmp))
44 if (!tempset.containsKey(tmp))
45 tempset.put(tmp, new HashSet<FlatNode>());
46 tempset.get(tmp).addAll(prevtable.get(tmp));
52 liveinto.put(fn, new Hashtable<TempDescriptor, Set<FlatNode>>(tempset));
55 if (lb==null||(!(fn instanceof FlatGlobalConvNode))||
56 ((FlatGlobalConvNode) fn).getLocality()==lb) {
57 TempDescriptor writes[]=fn.writesTemps();
58 for(int i=0;i<writes.length;i++) {
59 HashSet<FlatNode> s=new HashSet<FlatNode>();
61 tempset.put(writes[i],s);
64 if (!nodetotemps.containsKey(fn)||
65 !nodetotemps.get(fn).equals(tempset)) {
66 nodetotemps.put(fn, tempset);
67 for(int i=0; i<fn.numNext(); i++)
68 toprocess.add(fn.getNext(i));
71 return liveintoset?liveinto:nodetotemps;