sdcc/src/f8/ralloc2.cc

   1 // Philipp Klaus Krause, philipp@informatik.uni-frankfurt.de, pkk@spth.de, 2010 - 2013
   2 //
   3 // (c) 2010 - 2013 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 // An optimal, polynomial-time register allocator.
  20
  21 // #define DEBUG_RALLOC_DEC // Uncomment to get debug messages while doing register allocation on the tree decomposition.
  22 // #define DEBUG_RALLOC_DEC_ASS // Uncomment to get debug messages about assignments while doing register allocation on the tree decomposition (much more verbose than the one above).
  23
  24 #include "SDCCralloc.hpp"
  25 #include "SDCCsalloc.hpp"
  26
  27 extern "C"
  28 {
  29   #include "ralloc.h"
  30   #include "gen.h"
  31   float dryF8iCode (iCode *ic);
  32   bool f8_assignment_optimal;
  33   long int f8_call_stack_size;
  34   bool f8_extend_stack;
  35 }
  36
  37 #define REG_XL 0
  38 #define REG_XH 1
  39 #define REG_YL 2
  40 #define REG_YH 3
  41 #define REG_ZL 4
  42 #define REG_ZH 5
  43 #define REG_C 5
  44
  45 template <class I_t>
  46 static void add_operand_conflicts_in_node(const cfg_node &n, I_t &I)
  47 {
  48   const iCode *ic = n.ic;
  49
  50   const operand *result = IC_RESULT(ic);
  51   const operand *left = IC_LEFT(ic);
  52   const operand *right = IC_RIGHT(ic);
  53
  54   if(!result || !IS_SYMOP(result))
  55     return;
  56
  57   // Todo: More fine-grained control for these.
  58   if (!(ic->op == '+' || ic->op == '-' || ic->op == UNARYMINUS && !IS_FLOAT (operandType (left)) || ic->op == '~' ||
  59     ic->op == '^' || ic->op == '|' || ic->op == BITWISEAND ||
  60     ic->op == GET_VALUE_AT_ADDRESS))
  61     return;
  62
  63   operand_map_t::const_iterator oir, oir_end, oirs;
  64   boost::tie(oir, oir_end) = n.operands.equal_range(OP_SYMBOL_CONST(result)->key);
  65   if(oir == oir_end)
  66     return;
  67
  68   operand_map_t::const_iterator oio, oio_end;
  69
  70   if(left && IS_SYMOP(left))
  71     for(boost::tie(oio, oio_end) = n.operands.equal_range(OP_SYMBOL_CONST(left)->key); oio != oio_end; ++oio)
  72       for(oirs = oir; oirs != oir_end; ++oirs)
  73         {
  74           var_t rvar = oirs->second;
  75           var_t ovar = oio->second;
  76           if(I[rvar].byte < I[ovar].byte)
  77             boost::add_edge(rvar, ovar, I);
  78         }
  79
  80   if(right && IS_SYMOP(right))
  81     for(boost::tie(oio, oio_end) = n.operands.equal_range(OP_SYMBOL_CONST(right)->key); oio != oio_end; ++oio)
  82       for(oirs = oir; oirs != oir_end; ++oirs)
  83         {
  84           var_t rvar = oirs->second;
  85           var_t ovar = oio->second;
  86           if(I[rvar].byte < I[ovar].byte)
  87             boost::add_edge(rvar, ovar, I);
  88         }
  89 }
  90
  91 // Return true, iff the operand is placed (partially) in r.
  92 template <class G_t>
  93 static bool operand_in_reg(const operand *o, reg_t r, const i_assignment_t &ia, unsigned short int i, const G_t &G)
  94 {
  95   if(!o || !IS_SYMOP(o))
  96     return(false);
  97
  98   if(r >= port->num_regs)
  99     return(false);
 100
 101   operand_map_t::const_iterator oi, oi_end;
 102   for(boost::tie(oi, oi_end) = G[i].operands.equal_range(OP_SYMBOL_CONST(o)->key); oi != oi_end; ++oi)
 103     if(oi->second == ia.registers[r][1] || oi->second == ia.registers[r][0])
 104       return(true);
 105
 106   return(false);
 107 }
 108
 109 template <class G_t, class I_t>
 110 static bool Zinst_ok(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
 111 {
 112   const iCode *ic = G[i].ic;
 113
 114   const i_assignment_t &ia = a.i_assignment;
 115
 116   if(!f8_extend_stack)
 117     return(true);   // Only an extended stack can make Y unavailable.
 118
 119   if(ia.registers[REG_ZL][1] < 0 && ia.registers[REG_ZH][1] < 0)
 120     return(true);   // Register Y not in use.
 121
 122   return(false);
 123 }
 124
 125 template <class G_t, class I_t>
 126 static void set_surviving_regs(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
 127 {
 128   iCode *ic = G[i].ic;
 129
 130   bitVectClear(ic->rMask);
 131   bitVectClear(ic->rSurv);
 132
 133   cfg_alive_t::const_iterator v, v_end;
 134   for (v = G[i].alive.begin(), v_end = G[i].alive.end(); v != v_end; ++v)
 135     {
 136       if(a.global[*v] < 0)
 137         continue;
 138       ic->rMask = bitVectSetBit(ic->rMask, a.global[*v]);
 139
 140       if(!(IC_RESULT(ic) && IS_SYMOP(IC_RESULT(ic)) && OP_SYMBOL_CONST(IC_RESULT(ic))->key == I[*v].v))
 141         if(G[i].dying.find(*v) == G[i].dying.end())
 142           ic->rSurv = bitVectSetBit(ic->rSurv, a.global[*v]);
 143     }
 144 }
 145
 146 template <class G_t, class I_t>
 147 static void assign_operand_for_cost(operand *o, const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
 148 {
 149   if(!o || !IS_SYMOP(o))
 150     return;
 151   symbol *sym = OP_SYMBOL(o);
 152   operand_map_t::const_iterator oi, oi_end;
 153   for(boost::tie(oi, oi_end) = G[i].operands.equal_range(OP_SYMBOL_CONST(o)->key); oi != oi_end; ++oi)
 154     {
 155       var_t v = oi->second;
 156       if(a.global[v] >= 0)
 157         {
 158           sym->regs[I[v].byte] = f8_regs + a.global[v];
 159           sym->nRegs = I[v].size;
 160         }
 161       else
 162         {
 163           sym->regs[I[v].byte] = 0;
 164           sym->nRegs = I[v].size;
 165         }
 166     }
 167 }
 168
 169 template <class G_t, class I_t>
 170 static void assign_operands_for_cost(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
 171 {
 172   const iCode *ic = G[i].ic;
 173
 174   if(ic->op == IFX)
 175     assign_operand_for_cost(IC_COND(ic), a, i, G, I);
 176   else if(ic->op == JUMPTABLE)
 177     assign_operand_for_cost(IC_JTCOND(ic), a, i, G, I);
 178   else
 179     {
 180       assign_operand_for_cost(IC_LEFT(ic), a, i, G, I);
 181       assign_operand_for_cost(IC_RIGHT(ic), a, i, G, I);
 182       assign_operand_for_cost(IC_RESULT(ic), a, i, G, I);
 183     }
 184
 185   if(ic->op == SEND && ic->builtinSEND)
 186     assign_operands_for_cost(a, (unsigned short)*(adjacent_vertices(i, G).first), G, I);
 187 }
 188
 189 template <class G_t, class I_t>
 190 static bool operand_sane(const operand *o, const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
 191 {
 192   // f8 code generation is very flexible, and can handle nearly anything (including variables where some bytes are spilt, while others are not).
 193   // The only thing it can't handle is variables where some bytes are rematerialized, while others are not.
 194   if(!o || !IS_SYMOP(o) || !OP_SYMBOL_CONST(o)->remat)
 195     return(true);
 196
 197   operand_map_t::const_iterator oi, oi_end;
 198   boost::tie(oi, oi_end) = G[i].operands.equal_range(OP_SYMBOL_CONST(o)->key);
 199
 200   if(oi == oi_end)
 201     return(true);
 202
 203   // In registers.
 204   if(std::binary_search(a.local.begin(), a.local.end(), oi->second))
 205     {
 206       while(++oi != oi_end)
 207         if(!std::binary_search(a.local.begin(), a.local.end(), oi->second))
 208           return(false);
 209     }
 210   else
 211     {
 212        while(++oi != oi_end)
 213         if(std::binary_search(a.local.begin(), a.local.end(), oi->second))
 214           return(false);
 215     }
 216
 217   return(true);
 218 }
 219
 220 template <class G_t, class I_t>
 221 static bool inst_sane(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
 222 {
 223   const iCode *ic = G[i].ic;
 224
 225   return(operand_sane(IC_RESULT(ic), a, i, G, I) && operand_sane(IC_LEFT(ic), a, i, G, I) && operand_sane(IC_RIGHT(ic), a, i, G, I));
 226 }
 227
 228 // Cost function.
 229 template <class G_t, class I_t>
 230 static float instruction_cost(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
 231 {
 232   iCode *ic = G[i].ic;
 233   float c;
 234
 235   wassert(TARGET_IS_F8);
 236   wassert(ic);
 237
 238   if(!inst_sane(a, i, G, I))
 239     return(std::numeric_limits<float>::infinity());
 240
 241 #if 0
 242   std::cout << "Calculating at cost at ic " << ic->key << ", op " << ic->op << " for: ";
 243   print_assignment(a);
 244   std::cout << "\n";
 245   std::cout.flush();
 246 #endif
 247
 248   if(ic->generated)
 249     {
 250 #if 0
 251   std::cout << "Skipping, already generated.\n";
 252 #endif
 253       return(0.0f);
 254     }
 255
 256   if(!Zinst_ok(a, i, G, I))
 257     return(std::numeric_limits<float>::infinity());
 258
 259   switch(ic->op)
 260     {
 261     // Register assignment doesn't matter for these:
 262     case FUNCTION:
 263     case ENDFUNCTION:
 264     case LABEL:
 265     case GOTO:
 266     case INLINEASM:
 267 #if 0
 268   std::cout << "Skipping, indepent from assignment.\n";
 269 #endif
 270       return(0.0f);
 271     case '!':
 272     case '~':
 273     case UNARYMINUS:
 274     case '+':
 275     case '-':
 276     case '^':
 277     case '|':
 278     case BITWISEAND:
 279     case IPUSH:
 280     //case IPOP:
 281     case CALL:
 282     case PCALL:
 283     case RETURN:
 284     case '*':
 285     case '/':
 286     case '%':
 287     case '>':
 288     case '<':
 289     case LE_OP:
 290     case GE_OP:
 291     case EQ_OP:
 292     case NE_OP:
 293     case AND_OP:
 294     case OR_OP:
 295     case GETABIT:
 296     case GETBYTE:
 297     case GETWORD:
 298     case ROT:
 299     case LEFT_OP:
 300     case RIGHT_OP:
 301     case GET_VALUE_AT_ADDRESS:
 302     case SET_VALUE_AT_ADDRESS:
 303     case '=':
 304     case IFX:
 305     case ADDRESS_OF:
 306     case JUMPTABLE:
 307     case CAST:
 308     case RECEIVE:
 309     case SEND:
 310     case DUMMY_READ_VOLATILE:
 311     case CRITICAL:
 312     case ENDCRITICAL:
 313       assign_operands_for_cost(a, i, G, I);
 314       set_surviving_regs(a, i, G, I);
 315       c = dryF8iCode(ic);
 316       ic->generated = false;
 317 #if 0
 318       std::cout << "Got cost " << c << "\n";
 319 #endif
 320       return(c);
 321     default:
 322       return(0.0f);
 323     }
 324 }
 325
 326 // For early removal of assignments that cannot be extended to valid assignments. This is just a dummy for now.
 327 template <class G_t, class I_t>
 328 static bool assignment_hopeless(const assignment &a, unsigned short int i, const G_t &G, const I_t &I, const var_t lastvar)
 329 {
 330   return(false);
 331 }
 332
 333 // Increase chance of finding good compatible assignments at join nodes.
 334 template <class T_t>
 335 static void get_best_local_assignment_biased(assignment &a, typename boost::graph_traits<T_t>::vertex_descriptor t, const T_t &T)
 336 {
 337   a = *T[t].assignments.begin();
 338
 339   varset_t newlocal;
 340   std::set_union(T[t].alive.begin(), T[t].alive.end(), a.local.begin(), a.local.end(), std::inserter(newlocal, newlocal.end()));
 341   a.local = newlocal;
 342 }
 343
 344 // Suggest to honor register keyword and to not reverse bytes and prefer use of a. Prefer x over y.
 345 template <class G_t, class I_t>
 346 static float rough_cost_estimate(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
 347 {
 348   const i_assignment_t &ia = a.i_assignment;
 349   float c = 0.0f;
 350
 351   if(ia.registers[REG_XL][1] < 0)
 352     c += 0.05f;
 353
 354   varset_t::const_iterator v, v_end;
 355   for(v = a.local.begin(), v_end = a.local.end(); v != v_end; ++v)
 356     {
 357       const symbol *const sym = (symbol *)(hTabItemWithKey(liveRanges, I[*v].v));
 358       if(a.global[*v] < 0 && !sym->remat) // Try to put non-rematerializeable variables into registers.
 359         c += 0.1f;
 360       if(a.global[*v] < 0 && IS_REGISTER(sym->type)) // Try to honour register keyword.
 361         c += 4.0f;
 362       if((I[*v].byte % 2) ? // Try not to reverse bytes.
 363         (a.global[*v] == REG_YL || a.global[*v] == REG_ZL) :
 364         (a.global[*v] == REG_XH || a.global[*v] == REG_ZH))
 365         c += 0.1f;
 366     }
 367
 368   return(c);
 369 }
 370
 371 // Code for another ic is generated when generating this one. Mark the other as generated.
 372 static void extra_ic_generated(iCode *ic)
 373 {
 374   if(ic->op == '>' || ic->op == '<' || ic->op == LE_OP || ic->op == GE_OP || ic->op == EQ_OP || ic->op == NE_OP ||
 375     ic->op == BITWISEAND && (IS_OP_LITERAL (IC_LEFT (ic)) || IS_OP_LITERAL (IC_RIGHT (ic))) || ic->op == GETABIT || ic->op == GET_VALUE_AT_ADDRESS)
 376     {
 377       iCode *ifx;
 378
 379       // Bitwise and code generation can only do the jump if one operand is a literal with at most one nonzero byte.
 380       if (ic->op == BITWISEAND && getSize(operandType(IC_RESULT(ic))) > 1)
 381         {
 382           int nonzero = 0;
 383           operand *const litop = IS_OP_LITERAL (IC_LEFT (ic)) ? IC_LEFT (ic) : IC_RIGHT (ic);
 384
 385           for(unsigned int i = 0; i < getSize(operandType(IC_LEFT (ic))) && i < getSize(operandType(IC_RIGHT (ic))) && i < getSize(operandType(IC_RESULT(ic))); i++)
 386             if(byteOfVal (OP_VALUE (litop), i))
 387               nonzero++;
 388
 389           if(nonzero > 1)
 390             return;
 391         }
 392       if (ic->op == GET_VALUE_AT_ADDRESS &&
 393         (getSize(operandType(IC_RESULT(ic))) > 2 || IS_BITVAR (getSpec (operandType (IC_RESULT(ic)))) && SPEC_BLEN (getSpec (operandType (IC_RESULT(ic)))) > 8)) // Similar for pointer read
 394         {
 395           return;
 396         }
 397       if (ic->op == GETABIT)
 398         {
 399           unsigned bit = byteOfVal (OP_VALUE (IC_RIGHT (ic)), 0);
 400
 401           if (bit % 8 != 7)
 402             return;
 403         }
 404
 405       if (ifx = ifxForOp (IC_RESULT (ic), ic))
 406         {
 407           OP_SYMBOL (IC_RESULT (ic))->for_newralloc = false;
 408           OP_SYMBOL (IC_RESULT (ic))->regType = REG_CND;
 409           ifx->generated = true;
 410         }
 411     }
 412 }
 413
 414 template <class T_t, class G_t, class I_t, class SI_t>
 415 static bool tree_dec_ralloc(T_t &T, G_t &G, const I_t &I, SI_t &SI)
 416 {
 417   bool assignment_optimal;
 418
 419   con2_t I2(boost::num_vertices(I));
 420   for(unsigned int i = 0; i < boost::num_vertices(I); i++)
 421     {
 422       I2[i].v = I[i].v;
 423       I2[i].byte = I[i].byte;
 424       I2[i].size = I[i].size;
 425       I2[i].name = I[i].name;
 426     }
 427   typename boost::graph_traits<I_t>::edge_iterator e, e_end;
 428   for(boost::tie(e, e_end) = boost::edges(I); e != e_end; ++e)
 429     add_edge(boost::source(*e, I), boost::target(*e, I), I2);
 430
 431   assignment ac;
 432   assignment_optimal = true;
 433   tree_dec_ralloc_nodes(T, find_root(T), G, I2, ac, &assignment_optimal);
 434
 435   const assignment &winner = *(T[find_root(T)].assignments.begin());
 436
 437 #ifdef DEBUG_RALLOC_DEC
 438   std::cout << "Winner: ";
 439   for(unsigned int i = 0; i < boost::num_vertices(I); i++)
 440     {
 441       std::cout << "(" << i << ", " << int(winner.global[i]) << ") ";
 442     }
 443   std::cout << "\n";
 444   std::cout << "Cost: " << winner.s << "\n";
 445   std::cout.flush();
 446 #endif
 447
 448   // Todo: Make this an assertion
 449   if(winner.global.size() != boost::num_vertices(I))
 450     {
 451       std::cerr << "ERROR: No Assignments at root\n";
 452       exit(-1);
 453     }
 454
 455   for(unsigned int v = 0; v < boost::num_vertices(I); v++)
 456     {
 457       symbol *sym = (symbol *)(hTabItemWithKey(liveRanges, I[v].v));
 458       bool spilt = false;
 459
 460       if(winner.global[v] >= 0)
 461         sym->regs[I[v].byte] = f8_regs + winner.global[v];
 462       else
 463         {
 464           sym->regs[I[v].byte] = 0;
 465           spilt = true;
 466         }
 467
 468       if(spilt)
 469         f8SpillThis(sym, false);
 470
 471       sym->nRegs = I[v].size;
 472     }
 473
 474   for(unsigned int i = 0; i < boost::num_vertices(G); i++)
 475     set_surviving_regs(winner, i, G, I);
 476
 477   set_spilt(G, I, SI);
 478
 479   return(!assignment_optimal);
 480 }
 481
 482 iCode *f8_ralloc2_cc(ebbIndex *ebbi)
 483 {
 484   eBBlock **const ebbs = ebbi->bbOrder;
 485   const int count = ebbi->count;
 486
 487 #ifdef DEBUG_RALLOC_DEC
 488   std::cout << "Processing " << currFunc->name << " from " << dstFileName << "\n"; std::cout.flush();
 489 #endif
 490
 491   cfg_t control_flow_graph;
 492
 493   con_t conflict_graph;
 494
 495   iCode *ic = create_cfg(control_flow_graph, conflict_graph, ebbi);
 496
 497   if(optimize.genconstprop)
 498     recomputeValinfos(ic, ebbi, "_2");
 499
 500   guessCounts(ic, ebbi);
 501
 502   if(options.dump_graphs)
 503     dump_cfg(control_flow_graph);
 504
 505   if(options.dump_graphs)
 506     dump_con(conflict_graph);
 507
 508   tree_dec_t tree_decomposition;
 509
 510   get_nice_tree_decomposition(tree_decomposition, control_flow_graph);
 511
 512   alive_tree_dec(tree_decomposition, control_flow_graph);
 513
 514   good_re_root(tree_decomposition);
 515   nicify(tree_decomposition);
 516   alive_tree_dec(tree_decomposition, control_flow_graph);
 517
 518   if(options.dump_graphs)
 519     dump_tree_decomposition(tree_decomposition);
 520
 521   guessCounts (ic, ebbi);
 522
 523   scon_t stack_conflict_graph;
 524
 525   f8_assignment_optimal = !tree_dec_ralloc(tree_decomposition, control_flow_graph, conflict_graph, stack_conflict_graph);
 526
 527   f8RegFix (ebbs, count);
 528
 529   // Try to reuse parameter locations first.
 530   mergeSpiltParms(stack_conflict_graph);
 531
 532   chaitin_salloc(stack_conflict_graph);
 533
 534   if(options.dump_graphs)
 535     dump_scon(stack_conflict_graph);
 536
 537   return(ic);
 538 }
 539