1 pnkfelix 1.1.2.1 // CachingLiveTemps.java, created Sat Jul 29 15:22:48 2000 by pnkfelix
2 cananian 1.1.2.4 // Copyright (C) 2000 Felix S. Klock II <pnkfelix@mit.edu>
3 pnkfelix 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 pnkfelix 1.1.2.1 package harpoon.Analysis.DataFlow;
5 pnkfelix 1.1.2.1
6 pnkfelix 1.1.2.1 import harpoon.Analysis.BasicBlock;
7 pnkfelix 1.1.2.1 import harpoon.IR.Properties.UseDefer;
8 pnkfelix 1.1.2.1 import harpoon.ClassFile.HCode;
9 pnkfelix 1.1.2.1 import harpoon.ClassFile.HCodeElement;
10 pnkfelix 1.1.2.1 import harpoon.Temp.Temp;
11 pnkfelix 1.1.2.1 import harpoon.Util.CloneableIterator;
12 pnkfelix 1.1.2.1 import harpoon.Util.Util;
13 cananian 1.4 import net.cscott.jutil.BitSetFactory;
14 cananian 1.4 import net.cscott.jutil.ReverseIterator;
15 cananian 1.4 import net.cscott.jutil.SetFactory;
16 pnkfelix 1.1.2.1
17 pnkfelix 1.1.2.1 import java.util.Set;
18 pnkfelix 1.1.2.1 import java.util.Map;
19 pnkfelix 1.1.2.1 import java.util.HashSet;
20 pnkfelix 1.1.2.1 import java.util.HashMap;
21 pnkfelix 1.1.2.1 import java.util.Iterator;
22 pnkfelix 1.1.2.1
23 pnkfelix 1.1.2.1 /**
24 pnkfelix 1.1.2.1 * <code>CachingLiveTemps</code> is an extension of
25 pnkfelix 1.1.2.1 * <code>LiveTemps</code> that keeps a cache of the recent results
26 pnkfelix 1.1.2.1 * that it calculated. The cache keeps the last few basic blocks
27 pnkfelix 1.1.2.1 * accessed, along with the results of liveness analysis on all of the
28 pnkfelix 1.1.2.1 * statements in the basic blocks.
29 pnkfelix 1.1.2.1 *
30 cananian 1.1.2.4 * @author Felix S. Klock II <pnkfelix@mit.edu>
31 cananian 1.4 * @version $Id: CachingLiveTemps.java,v 1.4 2004/02/08 01:51:05 cananian Exp $
32 pnkfelix 1.1.2.1 */
33 pnkfelix 1.1.2.1 public class CachingLiveTemps extends LiveTemps {
34 pnkfelix 1.1.2.3
35 pnkfelix 1.1.2.3 public static LiveTemps make(HCode code, Set liveOnExit) {
36 pnkfelix 1.1.2.3 BasicBlock.Factory bbf = new BasicBlock.Factory(code);
37 pnkfelix 1.1.2.3 LiveTemps lt = new CachingLiveTemps(bbf, liveOnExit);
38 pnkfelix 1.1.2.3 Solver.worklistSolve
39 pnkfelix 1.1.2.3 // (bbFact.preorderBlocksIter(),
40 cananian 1.3 (new ReverseIterator(bbf.postorderBlocksIter()),
41 pnkfelix 1.1.2.3 lt);
42 pnkfelix 1.1.2.3 return lt;
43 pnkfelix 1.1.2.3 }
44 pnkfelix 1.1.2.1
45 pnkfelix 1.1.2.1 /** Creates a <code>CachingLiveTemps</code>. */
46 pnkfelix 1.1.2.1 public CachingLiveTemps(BasicBlock.Factory bbf, Set liveOnExit) {
47 pnkfelix 1.1.2.1 super(bbf, liveOnExit);
48 pnkfelix 1.1.2.1 }
49 pnkfelix 1.1.2.1
50 pnkfelix 1.1.2.1 public CachingLiveTemps(BasicBlock.Factory bbf, Set liveOnExit,
51 pnkfelix 1.1.2.1 UseDefer ud) {
52 pnkfelix 1.1.2.1 super(bbf, liveOnExit, ud);
53 pnkfelix 1.1.2.1 }
54 pnkfelix 1.1.2.1
55 pnkfelix 1.1.2.1 public CachingLiveTemps(BasicBlock.Factory bbf, Set liveOnExit,
56 pnkfelix 1.1.2.1 SetFactory tempSetFact, UseDefer ud) {
57 pnkfelix 1.1.2.1 super(bbf, liveOnExit, tempSetFact, ud);
58 pnkfelix 1.1.2.1 }
59 pnkfelix 1.1.2.1
60 pnkfelix 1.1.2.1 public String cachePerformance() {
61 pnkfelix 1.1.2.1 return "HITS: "+hits+" MISSES: "+misses+" SETUP: "+setup;
62 pnkfelix 1.1.2.1 }
63 pnkfelix 1.1.2.1
64 pnkfelix 1.1.2.1 private int hits = 0, misses = 0, setup = 0;
65 pnkfelix 1.1.2.1
66 pnkfelix 1.1.2.1
67 pnkfelix 1.1.2.3 private static final int CACHE_SIZE = 20;
68 pnkfelix 1.1.2.1 private int nextPt = 0;
69 pnkfelix 1.1.2.1 private BasicBlock[] lastBBs = new BasicBlock[CACHE_SIZE];
70 pnkfelix 1.1.2.1 // a cache of results for the getLiveAfter(HCodeElement) method
71 pnkfelix 1.1.2.1 // each index corresponds to the basic block in lastBBs
72 pnkfelix 1.1.2.1 private HashMap hce2liveAfters[] = new HashMap[CACHE_SIZE];
73 pnkfelix 1.1.2.1
74 pnkfelix 1.1.2.1 private HashSet blocksSeenBefore = new HashSet();
75 pnkfelix 1.1.2.1
76 pnkfelix 1.1.2.1 private HashMap addToCache(BasicBlock bb) {
77 pnkfelix 1.1.2.1 if (blocksSeenBefore.contains(bb)) {
78 pnkfelix 1.1.2.1 misses++;
79 pnkfelix 1.1.2.1 } else {
80 pnkfelix 1.1.2.1 setup++;
81 pnkfelix 1.1.2.1 blocksSeenBefore.add(bb);
82 pnkfelix 1.1.2.1 }
83 pnkfelix 1.1.2.1
84 pnkfelix 1.1.2.1 if (lastBBs[ nextPt ] != null) {
85 pnkfelix 1.1.2.1 hce2liveAfters[ nextPt ].clear();
86 pnkfelix 1.1.2.1 } else {
87 pnkfelix 1.1.2.1 hce2liveAfters[ nextPt ] = new HashMap(bb.statements().size());
88 pnkfelix 1.1.2.1 }
89 pnkfelix 1.1.2.1 lastBBs[ nextPt ] = bb;
90 pnkfelix 1.1.2.1 final HashMap hce2liveAfter = hce2liveAfters[ nextPt ];
91 pnkfelix 1.1.2.1 nextPt = (nextPt == lastBBs.length-1)?0:nextPt+1;
92 pnkfelix 1.1.2.1
93 pnkfelix 1.1.2.1
94 pnkfelix 1.1.2.1 Set liveAfter =
95 pnkfelix 1.1.2.1 mySetFactory.makeSet(this.getLiveOnExit(bb));
96 pnkfelix 1.1.2.1
97 pnkfelix 1.1.2.1 // Starting from the last element in hce's basic block,
98 pnkfelix 1.1.2.1 // traverse the block in reverse order, until hce is
99 pnkfelix 1.1.2.1 // reached. Each step updates the liveness information.
100 pnkfelix 1.1.2.1
101 pnkfelix 1.1.2.1 java.util.List stms = bb.statements();
102 pnkfelix 1.1.2.1 // System.out.print(" M"+stms.size());
103 pnkfelix 1.1.2.1 java.util.ListIterator iter = stms.listIterator(stms.size());
104 pnkfelix 1.1.2.1
105 pnkfelix 1.1.2.1 while(iter.hasPrevious()) {
106 pnkfelix 1.1.2.1 HCodeElement current = (HCodeElement) iter.previous();
107 pnkfelix 1.1.2.1
108 pnkfelix 1.1.2.1 // System.out.println("doing live after for "+current);
109 pnkfelix 1.1.2.1
110 pnkfelix 1.1.2.1 hce2liveAfter.put(current, mySetFactory.makeSet(liveAfter));
111 pnkfelix 1.1.2.1
112 pnkfelix 1.1.2.1 // update set for before 'current'
113 pnkfelix 1.1.2.1 liveAfter.removeAll(ud.defC(current));
114 pnkfelix 1.1.2.1 liveAfter.addAll(ud.useC(current));
115 pnkfelix 1.1.2.1 }
116 pnkfelix 1.1.2.1
117 pnkfelix 1.1.2.1 return hce2liveAfter;
118 pnkfelix 1.1.2.1 }
119 pnkfelix 1.1.2.1
120 pnkfelix 1.1.2.1 public Set getLiveAfter(HCodeElement hce) {
121 pnkfelix 1.1.2.1 BasicBlock bb = bbFact.getBlock(hce);
122 pnkfelix 1.1.2.1
123 pnkfelix 1.1.2.1 for(int i=0; i < lastBBs.length; i++) {
124 pnkfelix 1.1.2.1 if (lastBBs[i] == bb) {
125 pnkfelix 1.1.2.1 hits++;
126 pnkfelix 1.1.2.1 return (Set) hce2liveAfters[i].get(hce);
127 pnkfelix 1.1.2.1 }
128 pnkfelix 1.1.2.1 }
129 pnkfelix 1.1.2.1
130 pnkfelix 1.1.2.1 return (Set) addToCache( bb ).get(hce);
131 pnkfelix 1.1.2.1 }
132 cananian 1.2 }