4 import java.util.Arrays;
5 import java.util.HashSet;
7 import java.util.Iterator;
9 import java.util.Hashtable;
10 import Analysis.Locality.*;
12 public class Liveness {
13 /* This methods takes in a FlatMethod and returns a map from a
14 * FlatNode to the set of temps that are live into the FlatNode.*/
16 public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveTemps(FlatMethod fm, int threshold) {
17 return computeLiveTemps(fm, null, threshold);
19 public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveTemps(FlatMethod fm, LocalityBinding lb, int threshold) {
20 Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=new Hashtable<FlatNode, Set<TempDescriptor>>();
22 Set<FlatNode> toprocess=fm.getNodeSet();
24 while(!toprocess.isEmpty()) {
25 FlatNode fn=toprocess.iterator().next();
28 List<TempDescriptor> reads=Arrays.asList(fn.readsTemps());
29 List<TempDescriptor> writes=Arrays.asList(fn.writesTemps());
31 HashSet<TempDescriptor> tempset=new HashSet<TempDescriptor>();
32 for(int i=0; i<fn.numNext(); i++) {
33 FlatNode fnnext=fn.getNext(i);
34 if (nodetotemps.containsKey(fnnext))
35 tempset.addAll(nodetotemps.get(fnnext));
37 if ((lb==null)||(!(fn instanceof FlatGlobalConvNode))||
38 ((FlatGlobalConvNode)fn).getLocality()==lb) {
39 tempset.removeAll(writes);
40 tempset.addAll(reads);
42 if (!nodetotemps.containsKey(fn)||
43 !nodetotemps.get(fn).equals(tempset)) {
44 nodetotemps.put(fn, tempset);
45 if(threshold!=-1 && nodetotemps.size()>threshold){
48 for(int i=0; i<fn.numPrev(); i++)
49 toprocess.add(fn.getPrev(i));
55 public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveOut(FlatMethod fm) {
56 return computeLiveOut(fm, null);
59 public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveOut(FlatMethod fm, LocalityBinding lb) {
60 Hashtable<FlatNode, Set<TempDescriptor>> liveinmap=computeLiveTemps(fm, lb,-1);
61 Hashtable<FlatNode, Set<TempDescriptor>> liveoutmap=new Hashtable<FlatNode, Set<TempDescriptor>>();
63 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator(); fnit.hasNext();) {
64 FlatNode fn=fnit.next();
65 liveoutmap.put(fn, new HashSet<TempDescriptor>());
66 for(int i=0;i<fn.numNext();i++) {
67 FlatNode fn2=fn.getNext(i);
68 liveoutmap.get(fn).addAll(liveinmap.get(fn2));
75 // Also allow an instantiation of this object that memoizes results
76 protected Hashtable< FlatMethod, Hashtable< FlatNode, Set<TempDescriptor> > > fm2liveMap;
78 protected Hashtable< FlatMethod, Hashtable< FlatNode, Set<TempDescriptor> > > fm2liveOutMap;
81 fm2liveMap = new Hashtable< FlatMethod, Hashtable< FlatNode, Set<TempDescriptor> > >();
82 fm2liveOutMap = new Hashtable< FlatMethod, Hashtable< FlatNode, Set<TempDescriptor> > >();
85 public Set<TempDescriptor> getLiveOutTemps( FlatMethod fm, FlatNode fn ) {
86 if( !fm2liveOutMap.containsKey( fm ) ) {
87 fm2liveOutMap.put( fm, Liveness.computeLiveOut( fm ) );
89 return fm2liveOutMap.get( fm ).get( fn );
92 public Set<TempDescriptor> getLiveInTemps( FlatMethod fm, FlatNode fn ) {
93 if( !fm2liveMap.containsKey( fm ) ) {
94 fm2liveMap.put( fm, Liveness.computeLiveTemps( fm,-1 ) );
96 return fm2liveMap.get( fm ).get( fn );