1 // Philipp Klaus Krause, philipp@informatik.uni-frankfurt.de, pkk@spth.de, 2011
2 //
3 // (c) 2011 Goethe-Universität Frankfurt
4 //
5 // This program is free software; you can redistribute it and/or modify it
6 // under the terms of the GNU General Public License as published by the
7 // Free Software Foundation; either version 2, or (at your option) any
8 // later version.
9 //
10 // This program is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU General Public License for more details.
14 //
15 // You should have received a copy of the GNU General Public License
16 // along with this program; if not, write to the Free Software
17 // Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
18 //
19 //
20 // Optimal placement of bank switching instructions for named address spaces.
21 //
22 // For details, see:
23 //
24 // Philipp Klaus Krause,
25 // "Optimal Placement of Bank Selection Instructions in Polynomial Time",
26 // Proceedings of the 16th International Workshop on Software and Compilers for Embedded Systems,
27 // M-SCOPES '13, pp. 23-30.
28 // Association for Computing Machinery,
29 // 2013.
30
31 #ifndef SDCCNADDR_HH
32 #define SDCCNADDR_HH 1
33
34
35 #include <map>
36 #include <vector>
37 #include <sstream>
38 #include <fstream>
39
40 // Workaround for boost bug #11880
41 #include <boost/version.hpp>
42 #if BOOST_VERSION == 106000
43 #include <boost/type_traits/ice.hpp>
44 #endif
45
46 #include <boost/graph/graphviz.hpp>
47
48 extern "C"
49 {
50 #include "SDCCsymt.h"
51 #include "SDCCicode.h"
52 #include "SDCCBBlock.h"
53 #include "SDCCopt.h"
54 #include "SDCCy.h"
55 }
56
57 typedef short int naddrspace_t; // Named address spaces. -1: Undefined, Others: see map.
58
59 typedef std::set<unsigned short int> naddrspaceset_t;
60
61 struct assignment_naddr
62 {
63 float s;
64 naddrspaceset_t local;
65 std::vector<naddrspace_t> global;
66
operator <assignment_naddr67 bool operator<(const assignment_naddr& a) const
68 {
69 naddrspaceset_t::const_iterator i, ai, i_end, ai_end;
70
71 i_end = local.end();
72 ai_end = a.local.end();
73
74 for (i = local.begin(), ai = a.local.begin();; ++i, ++ai)
75 {
76 if (i == i_end)
77 return(true);
78 if (ai == ai_end)
79 return(false);
80
81 if (*i < *ai)
82 return(true);
83 if (*i > *ai)
84 return(false);
85
86 if (global[*i] < a.global[*ai])
87 return(true);
88 if (global[*i] > a.global[*ai])
89 return(false);
90 }
91 }
92 };
93
assignments_naddr_locally_same(const assignment_naddr & a1,const assignment_naddr & a2)94 bool assignments_naddr_locally_same(const assignment_naddr &a1, const assignment_naddr &a2)
95 {
96 if (a1.local != a2.local)
97 return(false);
98
99 naddrspaceset_t::const_iterator i, i_end;
100 for (i = a1.local.begin(), i_end = a1.local.end(); i != i_end; ++i)
101 if (a1.global[*i] != a2.global[*i])
102 return(false);
103
104 return(true);
105 }
106
107 struct cfg_naddr_node
108 {
109 iCode *ic;
110 naddrspaceset_t possible_naddrspaces;
111 };
112
113 typedef std::list<assignment_naddr> assignment_list_naddr_t;
114
115 struct tree_dec_naddr_node
116 {
117 std::set<unsigned int> bag;
118 assignment_list_naddr_t assignments;
119 unsigned weight; // The weight is the number of nodes at which intermediate results need to be remembered. In general, to minimize memory consumption, at join nodes the child with maximum weight should be processed first.
120 };
121
122 typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, cfg_naddr_node, float> cfg_t; // The edge property is the cost of subdividing the edge and inserting a bank switching instruction.
123 typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, tree_dec_naddr_node> tree_dec_t;
124
125 #ifdef HAVE_TREEDEC_COMBINATIONS_HPP
126 #include <treedec/treedec_traits.hpp>
127 TREEDEC_TREEDEC_BAG_TRAITS(tree_dec_t, bag);
128 #endif
129
130 #include "SDCCtree_dec.hpp"
131
132 // Annotate nodes of the control flow graph with the set of possible named address spaces active there.
annotate_cfg_naddr(cfg_t & cfg,std::map<naddrspace_t,const symbol * > & addrspaces)133 void annotate_cfg_naddr(cfg_t &cfg, std::map<naddrspace_t, const symbol *> &addrspaces)
134 {
135 /* MSVC 2010 doesn't like the typename here, though it accepts it elsewhere */
136 typedef /*typename*/ boost::graph_traits<cfg_t>::vertex_descriptor vertex_t;
137
138 std::map<const symbol *, naddrspace_t> sym_to_index;
139 naddrspace_t na_max = -1;
140
141 std::vector<bool> predetermined(boost::num_vertices (cfg), false);
142
143 // Initialize the cfg vertices where there is information on the desired named address space.
144 for (vertex_t i = 0; i < boost::num_vertices (cfg); i++)
145 {
146 const iCode *ic = cfg[i].ic;
147 const symbol *addrspace;
148
149 // We do not know the current named address space when entering a function or after calling one.
150 if (ic->op == CALL || ic->op == PCALL || ic->op == FUNCTION)
151 predetermined[i] = true;
152
153 // Set the required named address spaces
154 if (addrspace = getAddrspaceiCode (ic))
155 {
156 naddrspace_t na;
157
158 if (sym_to_index.find (addrspace) == sym_to_index.end ())
159 sym_to_index[addrspace] = ++na_max;
160 na = sym_to_index[addrspace];
161 addrspaces[na] = addrspace;
162
163 cfg[i].possible_naddrspaces.insert (na);
164 predetermined[i] = true;
165 }
166 else
167 cfg[i].possible_naddrspaces.insert(-1);
168 }
169
170 // Extend.
171 bool change;
172 do
173 {
174 change = false;
175 for (vertex_t i = 0; i < boost::num_vertices (cfg); i++)
176 {
177 if (predetermined[i])
178 continue;
179
180 size_t oldsize = cfg[i].possible_naddrspaces.size();
181 {
182 /* MSVC 2010 doesn't like the typename here, though it accepts it elsewhere */
183 typedef /*typename*/ boost::graph_traits<cfg_t>::out_edge_iterator n_iter_t;
184 n_iter_t n, n_end;
185 for (boost::tie(n, n_end) = boost::out_edges(i, cfg); n != n_end; ++n)
186 {
187 vertex_t v = boost::target(*n, cfg);
188 cfg[i].possible_naddrspaces.insert(cfg[v].possible_naddrspaces.begin(), cfg[v].possible_naddrspaces.end());
189 }
190 }
191 {
192 /* MSVC 2010 doesn't like the typename here, though it accepts it elsewhere */
193 typedef /*typename*/ boost::graph_traits<cfg_t>::in_edge_iterator n_iter_t;
194 n_iter_t n, n_end;
195 for (boost::tie(n, n_end) = boost::in_edges(i, cfg); n != n_end; ++n)
196 {
197 vertex_t v = boost::source(*n, cfg);
198 cfg[i].possible_naddrspaces.insert(cfg[v].possible_naddrspaces.begin(), cfg[v].possible_naddrspaces.end());
199 }
200 }
201
202 if (oldsize != cfg[i].possible_naddrspaces.size())
203 change = true;
204 }
205 }
206 while(change);
207 }
208
209 // Handle Leaf nodes in the nice tree decomposition
210 template <class T_t, class G_t>
tree_dec_naddrswitch_leaf(T_t & T,typename boost::graph_traits<T_t>::vertex_descriptor t,const G_t & G)211 void tree_dec_naddrswitch_leaf(T_t &T, typename boost::graph_traits<T_t>::vertex_descriptor t, const G_t &G)
212 {
213 assignment_naddr a;
214 assignment_list_naddr_t &alist = T[t].assignments;
215
216 a.s = 0;
217 a.global.resize(boost::num_vertices(G), -2);
218 alist.push_back(a);
219 }
220
221 // Handle introduce nodes in the nice tree decomposition
222 template <class T_t, class G_t>
tree_dec_naddrswitch_introduce(T_t & T,typename boost::graph_traits<T_t>::vertex_descriptor t,const G_t & G)223 int tree_dec_naddrswitch_introduce(T_t &T, typename boost::graph_traits<T_t>::vertex_descriptor t, const G_t &G)
224 {
225 typedef typename boost::graph_traits<T_t>::adjacency_iterator adjacency_iter_t;
226 adjacency_iter_t c, c_end;
227 assignment_list_naddr_t::iterator ai;
228 boost::tie(c, c_end) = adjacent_vertices(t, T);
229
230 assignment_list_naddr_t &alist2 = T[t].assignments;
231 assignment_list_naddr_t &alist = T[*c].assignments;
232
233 std::set<unsigned short> new_inst;
234 std::set_difference(T[t].bag.begin(), T[t].bag.end(), T[*c].bag.begin(), T[*c].bag.end(), std::inserter(new_inst, new_inst.end()));
235 unsigned short int i = *(new_inst.begin());
236
237 for(ai = alist.begin(); ai != alist.end(); ++ai)
238 {
239 ai->local.insert(i);
240
241 naddrspaceset_t::const_iterator ni, ni_end;
242 for(ni = G[i].possible_naddrspaces.begin(), ni_end = G[i].possible_naddrspaces.end(); ni != ni_end; ++ni)
243 {
244 ai->global[i] = *ni;
245 alist2.push_back(*ai);
246 }
247 }
248
249 alist.clear();
250
251 return((int)alist2.size() <= options.max_allocs_per_node ? 0 : -1);
252 }
253
254 // Handle forget nodes in the nice tree decomposition
255 template <class T_t, class G_t>
tree_dec_naddrswitch_forget(T_t & T,typename boost::graph_traits<T_t>::vertex_descriptor t,const G_t & G)256 void tree_dec_naddrswitch_forget(T_t &T, typename boost::graph_traits<T_t>::vertex_descriptor t, const G_t &G)
257 {
258 typedef typename boost::graph_traits<T_t>::adjacency_iterator adjacency_iter_t;
259 adjacency_iter_t c, c_end;
260 boost::tie(c, c_end) = adjacent_vertices(t, T);
261
262 assignment_list_naddr_t &alist = T[t].assignments;
263
264 std::swap(alist, T[*c].assignments);
265
266 std::set<unsigned short int> old_inst;
267 std::set_difference(T[*c].bag.begin(), T[*c].bag.end(), T[t].bag.begin(), T[t].bag.end(), std::inserter(old_inst, old_inst.end()));
268 unsigned short int i = *(old_inst.begin());
269
270 assignment_list_naddr_t::iterator ai, aif;
271
272 // Restrict assignments (locally) to current variables.
273 for (ai = alist.begin(); ai != alist.end(); ++ai)
274 {
275 ai->local.erase(i);
276 {
277 typedef typename boost::graph_traits<cfg_t>::out_edge_iterator n_iter_t;
278 n_iter_t n, n_end;
279 for (boost::tie(n, n_end) = boost::out_edges(i, G); n != n_end; ++n)
280 {
281 if (ai->local.find(boost::target(*n, G)) == ai->local.end() || ai->global[boost::target(*n, G)] == -1)
282 continue;
283 if (ai->global[boost::source(*n, G)] == ai->global[boost::target(*n, G)])
284 continue;
285 ai->s += G[*n];
286 }
287 }
288 {
289 typedef typename boost::graph_traits<cfg_t>::in_edge_iterator n_iter_t;
290 n_iter_t n, n_end;
291 for (boost::tie(n, n_end) = boost::in_edges(i, G); n != n_end; ++n)
292 {
293 if (ai->local.find(boost::source(*n, G)) == ai->local.end() || ai->global[boost::target(*n, G)] == -1)
294 continue;
295 if (ai->global[boost::source(*n, G)] == ai->global[boost::target(*n, G)])
296 continue;
297 ai->s += G[*n];
298 }
299 }
300 }
301
302 alist.sort();
303
304 // Collapse (locally) identical assignments.
305 for (ai = alist.begin(); ai != alist.end();)
306 {
307 aif = ai;
308
309 for (++ai; ai != alist.end() && assignments_naddr_locally_same(*aif, *ai);)
310 {
311 if (aif->s > ai->s)
312 {
313 alist.erase(aif);
314 aif = ai;
315 ++ai;
316 }
317 else
318 {
319 alist.erase(ai);
320 ai = aif;
321 ++ai;
322 }
323 }
324 }
325 }
326
327 // Handle join nodes in the nice tree decomposition
328 template <class T_t, class G_t>
tree_dec_naddrswitch_join(T_t & T,typename boost::graph_traits<T_t>::vertex_descriptor t,const G_t & G)329 void tree_dec_naddrswitch_join(T_t &T, typename boost::graph_traits<T_t>::vertex_descriptor t, const G_t &G)
330 {
331 typedef typename boost::graph_traits<T_t>::adjacency_iterator adjacency_iter_t;
332 adjacency_iter_t c, c_end, c2, c3;
333 boost::tie(c, c_end) = adjacent_vertices(t, T);
334
335 c2 = c;
336 ++c;
337 c3 = c;
338
339 assignment_list_naddr_t &alist1 = T[t].assignments;
340 assignment_list_naddr_t &alist2 = T[*c2].assignments;
341 assignment_list_naddr_t &alist3 = T[*c3].assignments;
342
343 alist2.sort();
344 alist3.sort();
345
346 assignment_list_naddr_t::iterator ai2, ai3;
347 for (ai2 = alist2.begin(), ai3 = alist3.begin(); ai2 != alist2.end() && ai3 != alist3.end();)
348 {
349 if (assignments_naddr_locally_same(*ai2, *ai3))
350 {
351 ai2->s += ai3->s;
352 for (size_t i = 0; i < ai2->global.size(); i++)
353 ai2->global[i] = ((ai2->global[i] != -2) ? ai2->global[i] : ai3->global[i]);
354 alist1.push_back(*ai2);
355 ++ai2;
356 ++ai3;
357 }
358 else if (*ai2 < *ai3)
359 {
360 ++ai2;
361 continue;
362 }
363 else if (*ai3 < *ai2)
364 {
365 ++ai3;
366 continue;
367 }
368 }
369
370 alist2.clear();
371 alist3.clear();
372 }
373
374 template <class T_t, class G_t>
tree_dec_naddrswitch_nodes(T_t & T,typename boost::graph_traits<T_t>::vertex_descriptor t,const G_t & G)375 int tree_dec_naddrswitch_nodes(T_t &T, typename boost::graph_traits<T_t>::vertex_descriptor t, const G_t &G)
376 {
377 typedef typename boost::graph_traits<T_t>::adjacency_iterator adjacency_iter_t;
378
379 adjacency_iter_t c, c_end;
380 typename boost::graph_traits<T_t>::vertex_descriptor c0, c1;
381
382 boost::tie(c, c_end) = adjacent_vertices(t, T);
383
384 switch (out_degree(t, T))
385 {
386 case 0:
387 tree_dec_naddrswitch_leaf(T, t, G);
388 break;
389 case 1:
390 c0 = *c;
391 tree_dec_naddrswitch_nodes(T, c0, G);
392 if (T[c0].bag.size() < T[t].bag.size())
393 {
394 if (tree_dec_naddrswitch_introduce(T, t, G))
395 return(-1);
396 }
397 else
398 tree_dec_naddrswitch_forget(T, t, G);
399 break;
400 case 2:
401 c0 = *c++;
402 c1 = *c;
403
404 if (T[c0].weight < T[c1].weight) // Minimize memory consumption.
405 std::swap (c0, c1);
406
407 tree_dec_naddrswitch_nodes(T, c0, G);
408 tree_dec_naddrswitch_nodes(T, c1, G);
409 tree_dec_naddrswitch_join(T, t, G);
410 break;
411 default:
412 std::cerr << "Not nice.\n";
413 break;
414 }
415 return(0);
416 }
417
418 template <class G_t>
implement_naddr_assignment(const assignment_naddr & a,const G_t & G,const std::map<naddrspace_t,const symbol * > addrspaces)419 static void implement_naddr_assignment(const assignment_naddr &a, const G_t &G, const std::map<naddrspace_t, const symbol *> addrspaces)
420 {
421 typedef typename boost::graph_traits<G_t>::vertex_descriptor vertex_t;
422 typedef typename boost::graph_traits<G_t>::edge_iterator ei_t;
423 ei_t e, e_end;
424
425 for(boost::tie(e, e_end) = boost::edges(G); e != e_end; ++e)
426 {
427 const vertex_t source = boost::source(*e, G);
428 const vertex_t target = boost::target(*e, G);
429 const naddrspace_t sourcespace = a.global[source];
430 const naddrspace_t targetspace = a.global[target];
431
432 // Nothing to do if the space doesn't change, or we just forget it.
433 if(targetspace == -1 || sourcespace == targetspace)
434 continue;
435
436 // This shouldn't happen with the CFGs sdcc generates and a cost function based on code size.
437 if(G[source].ic->next != G[target].ic)
438 std::cerr << "Trying to switch address space at weird edge in CFG.";
439
440 switchAddressSpaceAt(G[target].ic, addrspaces.find(targetspace)->second);
441 }
442 }
443
444 template <class T_t, class G_t>
tree_dec_address_switch(T_t & T,const G_t & G,const std::map<naddrspace_t,const symbol * > addrspaces)445 int tree_dec_address_switch(T_t &T, const G_t &G, const std::map<naddrspace_t, const symbol *> addrspaces)
446 {
447 if(tree_dec_naddrswitch_nodes(T, find_root(T), G))
448 return(-1);
449
450 const assignment_naddr &winner = *(T[find_root(T)].assignments.begin());
451
452 #if 0
453 std::cout << "Winner: ";
454 for(unsigned int i = 0; i < boost::num_vertices(G); i++)
455 {
456 std::cout << "(" << i << ", " << int(winner.global[i]) << ") ";
457 }
458 std::cout << "\n";
459 std::cout << "Cost: " << winner.s << "\n";
460 std::cout.flush();
461 #endif
462
463 implement_naddr_assignment(winner, G, addrspaces);
464
465 return(0);
466 }
467
468 // Dump cfg, with numbered nodes, show possible address spaces at each node.
dump_cfg_naddr(const cfg_t & cfg)469 void dump_cfg_naddr(const cfg_t &cfg)
470 {
471 std::ofstream dump_file((std::string(dstFileName) + ".dumpnaddrcfg" + (currFunc ? currFunc->rname : "__global") + ".dot").c_str());
472
473 std::string *name = new std::string[num_vertices(cfg)];
474 for (unsigned int i = 0; i < boost::num_vertices(cfg); i++)
475 {
476 std::ostringstream os;
477 os << i << ", " << cfg[i].ic->key << ": ";
478 naddrspaceset_t::const_iterator n;
479 for (n = cfg[i].possible_naddrspaces.begin(); n != cfg[i].possible_naddrspaces.end(); ++n)
480 os << *n << " ";
481 name[i] = os.str();
482 }
483 boost::write_graphviz(dump_file, cfg, boost::make_label_writer(name), boost::default_writer(), cfg_titlewriter(currFunc->rname, " bank selection instr. placement"));
484 delete[] name;
485 }
486
487 // Dump tree decomposition, show bag and live variables at each node.
dump_tree_decomposition_naddr(const tree_dec_t & tree_dec)488 static void dump_tree_decomposition_naddr(const tree_dec_t &tree_dec)
489 {
490 std::ofstream dump_file((std::string(dstFileName) + ".dumpnaddrdec" + currFunc->rname + ".dot").c_str());
491
492 unsigned int w = 0;
493
494 std::string *name = new std::string[num_vertices(tree_dec)];
495 for (unsigned int i = 0; i < boost::num_vertices(tree_dec); i++)
496 {
497 if (tree_dec[i].bag.size() > w)
498 w = tree_dec[i].bag.size();
499 std::ostringstream os;
500 std::set<unsigned int>::const_iterator v1;
501 os << i << " | ";
502 for (v1 = tree_dec[i].bag.begin(); v1 != tree_dec[i].bag.end(); ++v1)
503 os << *v1 << " ";
504 name[i] = os.str();
505 }
506 boost::write_graphviz(dump_file, tree_dec, boost::make_label_writer(name), boost::default_writer(), dec_titlewriter((w - 1), currFunc->rname, " bank selection instr. placement"));
507 delete[] name;
508 }
509
510 #endif
511
512