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) {
17 return computeLiveTemps(fm, null);
19 public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveTemps(FlatMethod fm, LocalityBinding lb) {
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 for(int i=0; i<fn.numPrev(); i++)
46 toprocess.add(fn.getPrev(i));
52 public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveOut(FlatMethod fm) {
53 return computeLiveOut(fm, null);
56 public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveOut(FlatMethod fm, LocalityBinding lb) {
57 Hashtable<FlatNode, Set<TempDescriptor>> liveinmap=computeLiveTemps(fm, lb);
58 Hashtable<FlatNode, Set<TempDescriptor>> liveoutmap=new Hashtable<FlatNode, Set<TempDescriptor>>();
60 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator(); fnit.hasNext();) {
61 FlatNode fn=fnit.next();
62 liveoutmap.put(fn, new HashSet<TempDescriptor>());
63 for(int i=0;i<fn.numNext();i++) {
64 FlatNode fn2=fn.getNext(i);
65 liveoutmap.get(fn).addAll(liveinmap.get(fn2));
72 // Also allow an instantiation of this object that memoizes results
73 protected Hashtable< FlatMethod, Hashtable< FlatNode, Set<TempDescriptor> > > fm2liveMap;
76 fm2liveMap = new Hashtable< FlatMethod, Hashtable< FlatNode, Set<TempDescriptor> > >();
79 public Set<TempDescriptor> getLiveInTemps( FlatMethod fm, FlatNode fn ) {
80 if( !fm2liveMap.containsKey( fm ) ) {
81 fm2liveMap.put( fm, Liveness.computeLiveTemps( fm ) );
83 return fm2liveMap.get( fm ).get( fn );