4 import java.util.Arrays;
5 import java.util.HashSet;
7 import java.util.Iterator;
9 import java.util.Hashtable;
11 public class Liveness {
12 /* This methods takes in a FlatMethod and returns a map from a
13 * FlatNode to the set of temps that are live into the FlatNode.*/
15 public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveTemps(FlatMethod fm) {
16 Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=new Hashtable<FlatNode, Set<TempDescriptor>>();
18 Set<FlatNode> toprocess=fm.getNodeSet();
20 while(!toprocess.isEmpty()) {
21 FlatNode fn=toprocess.iterator().next();
24 List<TempDescriptor> reads=Arrays.asList(fn.readsTemps());
25 List<TempDescriptor> writes=Arrays.asList(fn.writesTemps());
27 HashSet<TempDescriptor> tempset=new HashSet<TempDescriptor>();
28 for(int i=0; i<fn.numNext(); i++) {
29 FlatNode fnnext=fn.getNext(i);
30 if (nodetotemps.containsKey(fnnext))
31 tempset.addAll(nodetotemps.get(fnnext));
33 tempset.removeAll(writes);
34 tempset.addAll(reads);
35 if (!nodetotemps.containsKey(fn)||
36 !nodetotemps.get(fn).equals(tempset)) {
37 nodetotemps.put(fn, tempset);
38 for(int i=0; i<fn.numPrev(); i++)
39 toprocess.add(fn.getPrev(i));
45 public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveOut(FlatMethod fm) {
46 Hashtable<FlatNode, Set<TempDescriptor>> liveinmap=computeLiveTemps(fm);
47 Hashtable<FlatNode, Set<TempDescriptor>> liveoutmap=new Hashtable<FlatNode, Set<TempDescriptor>>();
49 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator(); fnit.hasNext();) {
50 FlatNode fn=fnit.next();
51 liveoutmap.put(fn, new HashSet<TempDescriptor>());
52 for(int i=0;i<fn.numNext();i++) {
53 FlatNode fn2=fn.getNext(i);
54 liveoutmap.get(fn).addAll(liveinmap.get(fn2));