1 cananian 1.1.2.1 /*
2 cananian 1.1.2.1 * FlowGraph/AssemFlowGraph.java
3 cananian 1.1.2.1 * construct a flow-graph from a list of instructions.
4 cananian 1.1.2.1 *
5 cananian 1.1.2.1 * C. Scott Ananian, cananian@princeton.edu, COS320
6 cananian 1.1.2.1 */
7 cananian 1.1.2.2 package harpoon.Backend.CSAHack.FlowGraph;
8 cananian 1.1.2.1
9 cananian 1.1.2.2 import harpoon.Backend.StrongARM.TwoWordTemp;
10 cananian 1.1.2.2
11 cananian 1.1.2.2 import harpoon.IR.Assem.Instr;
12 cananian 1.1.2.2 import harpoon.IR.Assem.InstrLABEL;
13 cananian 1.1.2.2 import harpoon.IR.Assem.InstrMOVE;
14 cananian 1.1.2.5 import harpoon.IR.Properties.UseDefer;
15 cananian 1.1.2.2 import harpoon.Backend.CSAHack.Graph.Node;
16 cananian 1.1.2.2 import harpoon.Backend.CSAHack.Graph.NodeList;
17 cananian 1.1.2.2 import harpoon.Temp.Label;
18 cananian 1.1.2.2 import harpoon.Temp.Temp;
19 cananian 1.1.2.2 import harpoon.Temp.TempList;
20 cananian 1.1.2.2 import harpoon.Util.Util;
21 cananian 1.1.2.1
22 cananian 1.1.2.1 import java.util.Hashtable;
23 cananian 1.1.2.2 import java.util.Iterator;
24 cananian 1.1.2.1
25 cananian 1.1.2.1 /**
26 cananian 1.1.2.1 * A flow graph whose nodes correspond to machine instructions.
27 cananian 1.1.2.1 * @version 1.00, 25 Nov 1996
28 cananian 1.1.2.1 * @author C. Scott Ananian
29 cananian 1.4 * @see harpoon.IR.Assem.Instr
30 cananian 1.1.2.1 */
31 cananian 1.1.2.1 public class AssemFlowGraph extends FlowGraph {
32 cananian 1.1.2.5 UseDefer ud;
33 cananian 1.1.2.2 boolean twoWord;
34 cananian 1.1.2.1 /**
35 cananian 1.1.2.1 * Construct an AssemFlowGraph from a list of instructions.
36 cananian 1.1.2.1 */
37 cananian 1.1.2.5 public AssemFlowGraph(Instr root, UseDefer ud, boolean twoWord) {
38 cananian 1.1.2.5 this.ud = ud;
39 cananian 1.1.2.2 this.twoWord = twoWord;
40 cananian 1.3.2.1 assert root.getPrev()==null;
41 cananian 1.1.2.1 Hashtable instr2node;
42 cananian 1.1.2.1 Hashtable label2node;
43 cananian 1.1.2.1
44 cananian 1.1.2.1 instr2node = new Hashtable();
45 cananian 1.1.2.1 label2node = new Hashtable();
46 cananian 1.1.2.1
47 cananian 1.1.2.1 // Make a node for each instruction.
48 cananian 1.1.2.1 // add these nodes to various lookup tables.
49 cananian 1.1.2.2 for (Instr il = root; il!=null; il=il.getNext()) {
50 cananian 1.1.2.2 Node n = newNode(il);
51 cananian 1.1.2.2 instr2node.put(il, n);
52 cananian 1.1.2.2 if (il instanceof InstrLABEL) {
53 cananian 1.1.2.2 Object prev = label2node.put(((InstrLABEL)il).getLabel(), n);
54 cananian 1.1.2.1 if (prev!=null)
55 cananian 1.1.2.1 throw new Error("InstrList error: multiple definitions of label "+
56 cananian 1.1.2.2 ((InstrLABEL)il).getLabel());
57 cananian 1.1.2.1 }
58 cananian 1.1.2.1 }
59 cananian 1.1.2.1
60 cananian 1.1.2.1 // Add edges for each node.
61 cananian 1.1.2.2 for (Instr il = root; il!=null; il=il.getNext()) {
62 cananian 1.1.2.2 // handle fall through.
63 cananian 1.1.2.2 if (il.canFallThrough) {
64 cananian 1.1.2.2 if (il.getNext() != null)
65 cananian 1.1.2.2 addEdge((Node)instr2node.get(il),
66 cananian 1.1.2.2 (Node)instr2node.get(il.getNext()));
67 cananian 1.1.2.2 }
68 cananian 1.1.2.2 // handle jumps.
69 cananian 1.6 for (Object llO : il.getTargets()) {
70 cananian 1.6 Label ll = (Label) llO;
71 cananian 1.1.2.2 if (label2node.get(ll)==null)
72 cananian 1.1.2.1 throw new Error("Non-existent label used in instruction list: "+
73 cananian 1.1.2.2 ll.toString()+" used in "+il.toString());
74 cananian 1.1.2.2 addEdge((Node)instr2node.get(il),
75 cananian 1.1.2.2 (Node)label2node.get(ll));
76 cananian 1.1.2.1 }
77 cananian 1.1.2.1 }
78 cananian 1.1.2.1 // all done.
79 cananian 1.1.2.1 }
80 cananian 1.1.2.1 /**
81 cananian 1.1.2.1 * @param n a node in the flow graph.
82 cananian 1.1.2.1 * @return the instruction corresponding to node 'n'
83 cananian 1.1.2.1 */
84 cananian 1.1.2.1 public Instr instr(Node n) {
85 cananian 1.1.2.1 if (!(n instanceof AssemNode))
86 cananian 1.1.2.1 throw new Error("not a AssemFlowGraph node");
87 cananian 1.1.2.1 else return ((AssemNode)n).instr;
88 cananian 1.1.2.1 }
89 cananian 1.1.2.1 /**
90 cananian 1.1.2.1 * @param n a node in the flow graph.
91 cananian 1.1.2.1 * @return a list of temps defined by the instruction at node 'n'
92 cananian 1.4 * @see harpoon.Temp.Temp
93 cananian 1.1.2.1 */
94 cananian 1.1.2.1 public TempList def(Node n) {
95 cananian 1.1.2.2 // CSA'99: clunk. def() returns an array in FLEX. Thunk it to a TempList.
96 cananian 1.1.2.5 Temp[] d = ud.def(instr(n));
97 cananian 1.1.2.2 TempList tl = null;
98 cananian 1.1.2.2 for (int i=d.length-1; i>=0; i--)
99 cananian 1.1.2.2 if (twoWord && d[i] instanceof TwoWordTemp) {
100 cananian 1.3.2.1 assert instr(n).getAssem().indexOf("`d"+i)!=-1;
101 cananian 1.1.2.4 if (instr(n).getAssem().indexOf("`d"+i+"l")!=-1)
102 cananian 1.1.2.4 tl = new TempList(((TwoWordTemp)d[i]).getLow(), tl);
103 cananian 1.1.2.4 if (instr(n).getAssem().indexOf("`d"+i+"h")!=-1)
104 cananian 1.1.2.4 tl = new TempList(((TwoWordTemp)d[i]).getHigh(), tl);
105 cananian 1.1.2.2 } else tl = new TempList(d[i], tl);
106 cananian 1.1.2.2 return tl;
107 cananian 1.1.2.1 }
108 cananian 1.1.2.1 /**
109 cananian 1.1.2.1 * @param n a node in the flow graph.
110 cananian 1.1.2.1 * @return a list of temps used by the instruction at node 'n'
111 cananian 1.4 * @see harpoon.Temp.Temp
112 cananian 1.1.2.1 */
113 cananian 1.1.2.1 public TempList use(Node n) {
114 cananian 1.1.2.2 // CSA'99: clunk. use() returns an array in FLEX. Thunk it to a TempList.
115 cananian 1.1.2.5 Temp[] u = ud.use(instr(n));
116 cananian 1.1.2.2 TempList tl = null;
117 cananian 1.1.2.2 for (int i=u.length-1; i>=0; i--)
118 cananian 1.1.2.2 if (twoWord && u[i] instanceof TwoWordTemp) {
119 cananian 1.3.2.1 assert instr(n).getAssem().indexOf("`s"+i)!=-1;
120 cananian 1.1.2.4 if (instr(n).getAssem().indexOf("`s"+i+"l")!=-1)
121 cananian 1.1.2.4 tl = new TempList(((TwoWordTemp)u[i]).getLow(), tl);
122 cananian 1.1.2.4 if (instr(n).getAssem().indexOf("`s"+i+"h")!=-1)
123 cananian 1.1.2.4 tl = new TempList(((TwoWordTemp)u[i]).getHigh(), tl);
124 cananian 1.1.2.2 } else tl = new TempList(u[i], tl);
125 cananian 1.1.2.2 return tl;
126 cananian 1.1.2.1 }
127 cananian 1.1.2.1 /**
128 cananian 1.1.2.1 * @param n a node in the flow graph.
129 cananian 1.1.2.1 * @return true if node n can be eliminated if use() == def(), false otherwise.
130 cananian 1.1.2.1 */
131 cananian 1.1.2.1 public boolean isMove(Node n) {
132 cananian 1.1.2.2 return instr(n) instanceof InstrMOVE;
133 cananian 1.1.2.1 }
134 cananian 1.1.2.1 /**
135 cananian 1.1.2.1 * Create a new node in the flow graph that does not correspond to
136 cananian 1.1.2.1 * an instruction. <BR>
137 cananian 1.1.2.1 * <STRONG>NOT RECOMMENDED.</STRONG> Use <TT>newNode(Instr i)</TT> instead.
138 cananian 1.1.2.1 */
139 cananian 1.1.2.1 public Node newNode() {
140 cananian 1.1.2.1 return new AssemNode(this, null);
141 cananian 1.1.2.1 }
142 cananian 1.1.2.1 /** Create a new node in the flow graph corresponding to the instruction
143 cananian 1.1.2.1 * passed as parameter.
144 cananian 1.1.2.1 */
145 cananian 1.1.2.1 public Node newNode(Instr i) {
146 cananian 1.1.2.1 return new AssemNode(this, i);
147 cananian 1.1.2.1 }
148 cananian 1.1.2.1 }
149 cananian 1.1.2.1
150 cananian 1.1.2.1 /**
151 cananian 1.1.2.1 * Extension to Graph.Node to represent nodes
152 cananian 1.1.2.1 * corresponding to Assem.Instr's.
153 cananian 1.1.2.1 */
154 cananian 1.1.2.2 class AssemNode extends harpoon.Backend.CSAHack.Graph.Node
155 cananian 1.1.2.2 // implements harpoon.Temp.TempMap
156 cananian 1.1.2.2 {
157 cananian 1.1.2.1 Instr instr;
158 cananian 1.1.2.2 AssemNode(harpoon.Backend.CSAHack.Graph.Graph g, Instr i) {
159 cananian 1.1.2.1 super(g);
160 cananian 1.1.2.1 instr = i;
161 cananian 1.1.2.1 }
162 cananian 1.1.2.1 public String toString() {
163 cananian 1.1.2.1 if (instr!=null) {
164 cananian 1.1.2.2 String r = "Instr["+super.toString()+"]";
165 cananian 1.1.2.2 //r+="("+instr.format(this).trim()+") ";
166 cananian 1.1.2.2 r+="("+instr.toString().trim()+") ";
167 cananian 1.1.2.2 /*
168 cananian 1.1.2.2 r+="- use: ";
169 cananian 1.1.2.2 Temp[] u = instr.use();
170 cananian 1.1.2.2 for (int i=0; i<u.length; i++)
171 cananian 1.1.2.2 r+=u[i].toString()+" ";
172 cananian 1.1.2.2 r+=", def: ";
173 cananian 1.1.2.2 Temp[] d = instr.def();
174 cananian 1.1.2.2 for (int i=0; i<d.length; i++)
175 cananian 1.1.2.2 r+=d[i].toString()+" ";
176 cananian 1.1.2.2 */
177 cananian 1.1.2.1 return r;
178 cananian 1.1.2.1 } else return super.toString();
179 cananian 1.1.2.1 }
180 cananian 1.1.2.2 public String tempMap(harpoon.Temp.Temp t) {
181 cananian 1.1.2.1 return t.toString();
182 cananian 1.1.2.1 }
183 cananian 1.1.2.3 public int hashCode() { return instr.hashCode(); }
184 cananian 1.1.2.1 }
185 cananian 1.2