sdcc/src/SDCCnaddr.hpp

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