1 cananian 1.1.2.1 // DominatingCheckOracle.java, created Tue Jan 16 12:05:26 2001 by cananian
 2 cananian 1.1.2.1 // Copyright (C) 2000 C. Scott Ananian <cananian@alumni.princeton.edu>
 3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
 4 cananian 1.1.2.1 package harpoon.Analysis.Transactions;
 5 cananian 1.1.2.1 
 6 cananian 1.1.2.1 import harpoon.Analysis.DomTree;
 7 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
 8 cananian 1.1.2.1 import harpoon.ClassFile.HCodeElement;
 9 cananian 1.1.2.1 import harpoon.IR.Quads.MONITORENTER;
10 cananian 1.1.2.1 import harpoon.IR.Quads.MONITOREXIT;
11 cananian 1.1.2.1 import harpoon.Util.ArrayIterator;
12 cananian 1.4     import net.cscott.jutil.MultiMap;
13 cananian 1.1.2.1 
14 cananian 1.1.2.1 import java.util.Iterator;
15 cananian 1.1.2.1 import java.util.Set;
16 cananian 1.1.2.1 /**
17 cananian 1.1.2.1  * A <code>DominatingCheckOracle</code> removes checks which
18 cananian 1.1.2.1  * have already been done at a dominating node.  It improves
19 cananian 1.1.2.1  * on the results of a client <code>CheckOracle</code>.
20 cananian 1.1.2.1  * 
21 cananian 1.1.2.1  * @author  C. Scott Ananian <cananian@alumni.princeton.edu>
22 cananian 1.4      * @version $Id: DominatingCheckOracle.java,v 1.4 2004/02/08 01:54:21 cananian Exp $
23 cananian 1.1.2.1  */
24 cananian 1.1.2.1 class DominatingCheckOracle extends AnalysisCheckOracle {
25 cananian 1.1.2.1     /** Creates a <code>DominatingCheckOracle</code>. */
26 cananian 1.1.2.1     public DominatingCheckOracle(HCode hc, CheckOracle co) {
27 cananian 1.1.2.1         this(new DomTree(hc, false), co);
28 cananian 1.1.2.1     }
29 cananian 1.1.2.1     DominatingCheckOracle(DomTree dt, CheckOracle co) {
30 cananian 1.1.2.1         /* okay, compute the proper check locations by propagating down
31 cananian 1.1.2.1          * domtree */
32 cananian 1.2.2.1         for (Iterator<HCodeElement> it = new ArrayIterator<HCodeElement>
33 cananian 1.2.2.1                  (dt.roots()); it.hasNext(); )
34 cananian 1.2.2.1             propagate(it.next(), dt, co, new CheckSet());
35 cananian 1.1.2.1     }
36 cananian 1.1.2.1     void propagate(HCodeElement hce, DomTree dt, CheckOracle co, CheckSet cs){
37 cananian 1.1.2.1         /* collect checks from client CheckOracle */
38 cananian 1.1.2.1         CheckSet checks = new CheckSet(co, hce);
39 cananian 1.1.2.1         /* remove the dominated ones */
40 cananian 1.1.2.1         checks.removeAll(cs);
41 cananian 1.1.2.1         checks.readVersions.removeAll(cs.writeVersions);
42 cananian 1.1.2.1         /* update our data struct with those left */
43 cananian 1.1.2.2         results.put(hce, checks.clone());
44 cananian 1.1.2.1         /* create new 'dominated checks' set */
45 cananian 1.1.2.1         checks.addAll(cs);
46 cananian 1.1.2.1         /* nothing passes MONITORENTER or MONITOREXIT */
47 cananian 1.1.2.1         if (hce instanceof MONITORENTER || hce instanceof MONITOREXIT)
48 cananian 1.1.2.1             checks.clear();
49 cananian 1.1.2.3         // XXX: nothing should pass Object.wait() either.
50 cananian 1.1.2.1         /* recurse down dom tree */
51 cananian 1.2.2.1         for (Iterator<HCodeElement> it = new ArrayIterator<HCodeElement>
52 cananian 1.2.2.1                  (dt.children(hce)); it.hasNext(); )
53 cananian 1.2.2.1             propagate(it.next(), dt, co, checks);
54 cananian 1.1.2.1         /* done! */
55 cananian 1.1.2.1     }
56 cananian 1.2     }