1 cananian 1.1.2.1 // QuadInterferenceGraph.java, created Thu Nov 23 13:14:33 2000 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.Quads;
5 cananian 1.1.2.1
6 cananian 1.1.2.2 import harpoon.Analysis.InterferenceGraph;
7 cananian 1.1.2.1 import harpoon.Analysis.Liveness;
8 cananian 1.2.2.1 import harpoon.ClassFile.HCodeElement;
9 cananian 1.1.2.1 import harpoon.IR.Quads.Code;
10 cananian 1.1.2.1 import harpoon.IR.Quads.Quad;
11 cananian 1.1.2.1 import harpoon.Temp.Temp;
12 cananian 1.4 import net.cscott.jutil.AggregateSetFactory;
13 cananian 1.4 import net.cscott.jutil.GenericMultiMap;
14 cananian 1.4 import net.cscott.jutil.MultiMap;
15 cananian 1.1.2.1 import harpoon.Util.Grapher;
16 cananian 1.1.2.1
17 cananian 1.1.2.1 import java.util.Collection;
18 cananian 1.1.2.2 import java.util.Collections;
19 cananian 1.1.2.1 import java.util.Iterator;
20 cananian 1.1.2.2 import java.util.List;
21 cananian 1.1.2.1 import java.util.Set;
22 cananian 1.1.2.1 /**
23 cananian 1.1.2.1 * <code>QuadInterferenceGraph</code> constructs a variable-liveness
24 cananian 1.1.2.1 * interference graph from a <code>Quad.Code</code>. There is an
25 cananian 1.1.2.1 * edge between <code>Temp</code> <code>t1</code> and
26 cananian 1.1.2.1 * <code>Temp</code> <code>t2</code> if <code>t1</code> and
27 cananian 1.1.2.1 * <code>t2</code> are ever live at the same point.
28 cananian 1.1.2.1 * <p>
29 cananian 1.1.2.1 * <code>QuadInterferenceGraph</code> is a <code>Grapher</code>
30 cananian 1.1.2.1 * for <code>Temp</code>s.
31 cananian 1.1.2.1 *
32 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
33 cananian 1.5 * @version $Id: QuadInterferenceGraph.java,v 1.5 2004/02/08 03:20:10 cananian Exp $
34 cananian 1.1.2.1 */
35 cananian 1.1.2.2 public class QuadInterferenceGraph implements InterferenceGraph {
36 cananian 1.2.2.1 private final MultiMap<Temp,Temp> mm;
37 cananian 1.1.2.1
38 cananian 1.1.2.1 /** Creates a <code>QuadInterferenceGraph</code>. */
39 cananian 1.1.2.1 public QuadInterferenceGraph(Code code) {
40 cananian 1.1.2.1 this(code, new QuadLiveness(code));
41 cananian 1.1.2.1 }
42 cananian 1.2.2.1 public QuadInterferenceGraph(Code code, Liveness<Quad> live) {
43 cananian 1.2.2.1 this.mm=new GenericMultiMap<Temp,Temp>(new AggregateSetFactory<Temp>());
44 cananian 1.2.2.1 for (Iterator<Quad> it=code.getElementsI(); it.hasNext(); ) {
45 cananian 1.2.2.1 Quad q = it.next();
46 cananian 1.5 for (Temp t : live.getLiveOut(q)) {
47 cananian 1.5 for (Temp d : q.defC()) {
48 cananian 1.1.2.1 if (!t.equals(d)) {
49 cananian 1.1.2.1 mm.add(t, d);
50 cananian 1.1.2.1 mm.add(d, t);
51 cananian 1.1.2.1 }
52 cananian 1.1.2.1 }
53 cananian 1.1.2.1 }
54 cananian 1.1.2.1 }
55 cananian 1.1.2.1 }
56 cananian 1.1.2.2 /** unimplemented. always returns 1. */
57 cananian 1.1.2.2 public int spillCost(Temp t) { return 1; }
58 cananian 1.1.2.2 /** unimplemented. always returns 0-element list. */
59 cananian 1.2.2.1 public List<HCodeElement> moves() { return Collections.EMPTY_LIST; }
60 cananian 1.1.2.2
61 cananian 1.2.2.1 public boolean isEdge(Temp from, Temp to) {
62 cananian 1.1.2.1 return mm.contains(from, to);
63 cananian 1.1.2.1 }
64 cananian 1.2.2.1 public Set<Temp> succSet(Temp node) {
65 cananian 1.2.2.1 return (Set<Temp>) mm.getValues(node);
66 cananian 1.2.2.1 }
67 cananian 1.2.2.1 public Set<Temp> predSet(Temp node) {
68 cananian 1.2.2.1 return (Set<Temp>) mm.getValues(node);
69 cananian 1.2.2.1 }
70 cananian 1.2 }