1 cananian 1.10.2.7 // Place.java, created Mon Jan 31 08:30:07 2000 by cananian
2 cananian 1.10.2.7 // Copyright (C) 2000 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.10 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1 package harpoon.Analysis;
5 cananian 1.1
6 cananian 1.10.2.1 import harpoon.ClassFile.HCodeElement;
7 cananian 1.10.2.7 import harpoon.ClassFile.HCode;
8 cananian 1.10.2.7 import harpoon.IR.Properties.CFGraphable;
9 cananian 1.10.2.13 import harpoon.IR.Properties.UseDefable;
10 cananian 1.1 import harpoon.Temp.Temp;
11 cananian 1.12 import net.cscott.jutil.WorkSet;
12 cananian 1.12 import net.cscott.jutil.BitSetFactory;
13 cananian 1.12 import net.cscott.jutil.GenericMultiMap;
14 cananian 1.12 import net.cscott.jutil.Factories;
15 cananian 1.12 import net.cscott.jutil.MultiMap;
16 cananian 1.10.2.4
17 cananian 1.10.2.7 import java.util.Collection;
18 cananian 1.10.2.4 import java.util.Iterator;
19 cananian 1.10.2.4 import java.util.Set;
20 cananian 1.1 /**
21 cananian 1.10.2.4 * <code>Place</code> determines the proper locations for phi/sigma
22 cananian 1.10.2.7 * functions. This is the placement algorithm detailed in my
23 cananian 1.10.2.7 * thesis.
24 cananian 1.1 *
25 cananian 1.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
26 cananian 1.13 * @version $Id: Place.java,v 1.13 2004/02/08 03:19:12 cananian Exp $
27 cananian 1.1 */
28 cananian 1.10.2.7 public class Place {
29 cananian 1.10.2.7 private final MultiMap phis;
30 cananian 1.10.2.7 private final MultiMap sigmas;
31 cananian 1.10.2.4
32 cananian 1.1 /** Creates a <code>Place</code>. */
33 cananian 1.10.2.7 public Place(HCode hc, Liveness live) {
34 cananian 1.10.2.7 // create SESE
35 cananian 1.10.2.7 SESE sese = new SESE(hc);
36 cananian 1.10.2.7 // collect all vars
37 cananian 1.10.2.7 Set vars = new WorkSet();
38 cananian 1.10.2.7 for (Iterator it=hc.getElementsI(); it.hasNext(); )
39 cananian 1.10.2.13 vars.addAll(((UseDefable)it.next()).defC());
40 cananian 1.10.2.7 // create result multimaps
41 cananian 1.10.2.12 phis = new GenericMultiMap(new BitSetFactory(vars));
42 cananian 1.10.2.12 sigmas = new GenericMultiMap(new BitSetFactory(vars));
43 cananian 1.10.2.7 // for each variable v in G, do:
44 cananian 1.13 for (Object vO : vars) {
45 cananian 1.13 Temp v = (Temp) vO;
46 cananian 1.10.2.10 PlaceOne(sese.topLevel, v, live); // place phis and sigmas
47 cananian 1.1 }
48 cananian 1.4 }
49 cananian 1.10.2.10 private boolean PlaceOne(SESE.Region r, Temp v, Liveness live)
50 cananian 1.10.2.7 {
51 cananian 1.10.2.7 // post-order traversal.
52 cananian 1.10.2.7 boolean flag = false;
53 cananian 1.10.2.7 for (Iterator it=r.children().iterator(); it.hasNext(); )
54 cananian 1.10.2.10 if (PlaceOne((SESE.Region)it.next(), v, live))
55 cananian 1.10.2.7 flag = true;
56 cananian 1.10.2.7 for (Iterator it=r.nodes().iterator(); !flag && it.hasNext(); ) {
57 cananian 1.10.2.13 UseDefable n = (UseDefable) it.next();
58 cananian 1.10.2.9 // we need phis for 'use-only' vars because the sigma is
59 cananian 1.10.2.9 // going to create a definition for them. Likewise we
60 cananian 1.10.2.9 // need sigmas for 'def-only' vars. [CSA]
61 cananian 1.10.2.9 if (n.defC().contains(v) || n.useC().contains(v))
62 cananian 1.10.2.7 flag = true;
63 cananian 1.1 }
64 cananian 1.10.2.4
65 cananian 1.10.2.7 // add phis/sigmas to merges/splits where v may be live
66 cananian 1.10.2.7 if (flag) {
67 cananian 1.13 for (Object nO : r.nodes()) {
68 cananian 1.13 HCodeElement n = (HCodeElement) nO;
69 cananian 1.10.2.10 if (((CFGraphable)n).predC().size() > 1 &&
70 cananian 1.10.2.7 live.getLiveIn(n).contains(v))
71 cananian 1.10.2.7 phis.add(n, v);
72 cananian 1.10.2.10 if (((CFGraphable)n).succC().size() > 1 &&
73 cananian 1.10.2.7 live.getLiveIn(n).contains(v))
74 cananian 1.10.2.7 sigmas.add(n, v);
75 cananian 1.10.2.7 }
76 cananian 1.1 }
77 cananian 1.10.2.7 return flag;
78 cananian 1.1 }
79 cananian 1.1
80 cananian 1.10.2.7 public Temp[] phiNeeded(HCodeElement n) {
81 cananian 1.10.2.7 Collection c = phis.getValues(n);
82 cananian 1.10.2.7 return (Temp[]) c.toArray(new Temp[c.size()]);
83 cananian 1.1 }
84 cananian 1.10.2.7 public Temp[] sigNeeded(HCodeElement n) {
85 cananian 1.10.2.7 Collection c = sigmas.getValues(n);
86 cananian 1.10.2.7 return (Temp[]) c.toArray(new Temp[c.size()]);
87 cananian 1.1 }
88 cananian 1.1 }