sdcc/src/mos6502/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 drym6502iCode (iCode *ic);
  32   bool m6502_assignment_optimal;
  33 }
  34
  35 #define REG_A 0
  36 #define REG_X 1
  37 #define REG_Y 2
  38
  39 template <class I_t>
  40 static void add_operand_conflicts_in_node(const cfg_node &n, I_t &I)
  41 {
  42   const iCode *ic = n.ic;
  43
  44   const operand *result = IC_RESULT(ic);
  45   const operand *left = IC_LEFT(ic);
  46   const operand *right = IC_RIGHT(ic);
  47
  48   if(!result || !IS_SYMOP(result))
  49     return;
  50
  51   // Todo: Identify more operations that code generation can always handle and exclude them (as done for the z80-like ports).
  52   if (ic->op == '=')
  53     return;
  54
  55   operand_map_t::const_iterator oir, oir_end, oirs;
  56   boost::tie(oir, oir_end) = n.operands.equal_range(OP_SYMBOL_CONST(result)->key);
  57   if(oir == oir_end)
  58     return;
  59
  60   operand_map_t::const_iterator oio, oio_end;
  61
  62   if(left && IS_SYMOP(left))
  63     for(boost::tie(oio, oio_end) = n.operands.equal_range(OP_SYMBOL_CONST(left)->key); oio != oio_end; ++oio)
  64       for(oirs = oir; oirs != oir_end; ++oirs)
  65         {
  66           var_t rvar = oirs->second;
  67           var_t ovar = oio->second;
  68           if(I[rvar].byte < I[ovar].byte)
  69             boost::add_edge(rvar, ovar, I);
  70         }
  71
  72   if(right && IS_SYMOP(right))
  73     for(boost::tie(oio, oio_end) = n.operands.equal_range(OP_SYMBOL_CONST(right)->key); oio != oio_end; ++oio)
  74       for(oirs = oir; oirs != oir_end; ++oirs)
  75         {
  76           var_t rvar = oirs->second;
  77           var_t ovar = oio->second;
  78           if(I[rvar].byte < I[ovar].byte)
  79             boost::add_edge(rvar, ovar, I);
  80         }
  81 }
  82
  83 // Return true, iff the operand is placed (partially) in r.
  84 template <class G_t>
  85 static bool operand_in_reg(const operand *o, reg_t r, const i_assignment_t &ia, unsigned short int i, const G_t &G)
  86 {
  87   if(!o || !IS_SYMOP(o))
  88     return(false);
  89
  90   if(r >= port->num_regs)
  91     return(false);
  92
  93   operand_map_t::const_iterator oi, oi_end;
  94   for(boost::tie(oi, oi_end) = G[i].operands.equal_range(OP_SYMBOL_CONST(o)->key); oi != oi_end; ++oi)
  95     if(oi->second == ia.registers[r][1] || oi->second == ia.registers[r][0])
  96       return(true);
  97
  98   return(false);
  99 }
 100
 101 // Return true, iff the operand is placed in a reg.
 102 template <class G_t, class I_t>
 103 static bool operand_is_ax(const operand *o, const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
 104 {
 105   if(!o || !IS_SYMOP(o))
 106     return(false);
 107
 108   operand_map_t::const_iterator oi, oi2, oi_end;
 109   boost::tie(oi, oi_end) = G[i].operands.equal_range(OP_SYMBOL_CONST(o)->key);
 110
 111   if(oi == oi_end)
 112     return(false);
 113
 114   oi2 = oi;
 115   oi2++;
 116   if (oi2 == oi_end)
 117     return(false);
 118
 119   // Register combinations code generation cannot handle yet (AX, AY, XY, YA).
 120   if(std::binary_search(a.local.begin(), a.local.end(), oi->second) && std::binary_search(a.local.begin(), a.local.end(), oi2->second))
 121     {
 122       const reg_t l = a.global[oi->second];
 123       const reg_t h = a.global[oi2->second];
 124       if(l == REG_X && h == REG_A)
 125         return(true);
 126     }
 127
 128   return(false);
 129 }
 130
 131 // Return true, iff the operand is placed in xa
 132 template <class G_t, class I_t>
 133 static bool XAinst_ok(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
 134 {
 135   const iCode *ic = G[i].ic;
 136
 137   // Instructions that can handle anything.
 138   if(ic->op == '!' ||
 139     ic->op == '~' ||
 140     ic->op == UNARYMINUS ||
 141     ic->op == CALL ||
 142     ic->op == PCALL ||
 143     ic->op == FUNCTION ||
 144     ic->op == ENDFUNCTION ||
 145     ic->op == RETURN ||
 146     ic->op == LABEL ||
 147     ic->op == GOTO ||
 148     ic->op == IFX ||
 149     ic->op == '+' ||
 150     ic->op == '-' ||
 151     ic->op == '*' ||
 152     ic->op == '/' ||
 153     ic->op == '%' ||
 154     ic->op == '<' || ic->op == '>' || ic->op == LE_OP || ic->op == GE_OP ||
 155     ic->op == NE_OP || ic->op == EQ_OP ||
 156     ic->op == AND_OP ||
 157     ic->op == OR_OP ||
 158     ic->op == '^' ||
 159     ic->op == '|' ||
 160     ic->op == BITWISEAND ||
 161     ic->op == GETABIT ||
 162     ic->op == GETBYTE ||
 163     ic->op == GETWORD ||
 164     ic-> op == ROT ||
 165     ic->op == LEFT_OP ||
 166     ic->op == RIGHT_OP ||
 167     //ic->op == '=' ||  /* both regular assignment and POINTER_SET safe */
 168     //ic->op == GET_VALUE_AT_ADDRESS ||
 169     ic->op == ADDRESS_OF ||
 170     ic->op == CAST ||
 171     ic->op == DUMMY_READ_VOLATILE)
 172     return(true);
 173
 174   if(ic->op == IFX && ic->generated)
 175     return(true);
 176
 177   const i_assignment_t &ia = a.i_assignment;
 178
 179   bool unused_A = (ia.registers[REG_A][1] < 0);
 180   bool unused_Y = (ia.registers[REG_Y][1] < 0);
 181   bool unused_X = (ia.registers[REG_X][1] < 0);
 182
 183   if(unused_X && unused_A && unused_Y)
 184     return(true);
 185
 186 #if 0
 187   std::cout << "XAinst_ok: at (" << i << ", " << ic->key << ")\nX = (" << ia.registers[REG_X][0] << ", " << ia.registers[REG_X][1] << "), A = (" << ia.registers[REG_A][0] << ", " << ia.registers[REG_A][1] << ")inst " << i << ", " << ic->key << "\n";
 188 #endif
 189
 190   const operand *left = IC_LEFT(ic);
 191   const operand *right = IC_RIGHT(ic);
 192   const operand *result = IC_RESULT(ic);
 193
 194   bool result_in_A = operand_in_reg(result, REG_A, ia, i, G) && !(ic->op == '=' && POINTER_SET(ic));
 195   bool result_in_Y = operand_in_reg(result, REG_Y, ia, i, G) && !(ic->op == '=' && POINTER_SET(ic));
 196   bool result_in_X = operand_in_reg(result, REG_X, ia, i, G) && !(ic->op == '=' && POINTER_SET(ic));
 197   bool left_in_A = operand_in_reg(result, REG_A, ia, i, G);
 198   bool left_in_X = operand_in_reg(result, REG_X, ia, i, G);
 199
 200   const cfg_dying_t &dying = G[i].dying;
 201
 202   bool dying_A = result_in_A || dying.find(ia.registers[REG_A][1]) != dying.end() || dying.find(ia.registers[REG_A][0]) != dying.end();
 203   bool dying_Y = result_in_Y || dying.find(ia.registers[REG_Y][1]) != dying.end() || dying.find(ia.registers[REG_Y][0]) != dying.end();
 204   bool dying_X = result_in_X || dying.find(ia.registers[REG_X][1]) != dying.end() || dying.find(ia.registers[REG_X][0]) != dying.end();
 205
 206   bool result_only_XA = (result_in_X || unused_X || dying_X) && (result_in_A || unused_A || dying_A);
 207
 208   if(ic->op == JUMPTABLE && (unused_A || dying_A))
 209     return(true);
 210
 211   if(ic->op == IPUSH && (unused_A || dying_A || left_in_A || operand_in_reg(left, REG_Y, ia, i, G) || left_in_X))
 212     return(true);
 213
 214   if(ic->op == RECEIVE && (!ic->next || !(ic->next->op == RECEIVE) || !result_in_X || getSize(operandType(result)) >= 2))
 215     return(true);
 216
 217   if(ic->op == SEND && ic->next && ic->next->op == SEND && ic->next->next && ic->next->next->op == SEND)
 218     return(true);
 219
 220   if(ic->op == SEND && ic->next && ic->next->op == SEND && (unused_X || dying_X))
 221     return(true);
 222
 223   if(ic->op == SEND && (unused_X || dying_X) && (unused_A || dying_A))
 224     return(true);
 225
 226   if(ic->op == SEND && ic->next && (ic->next->op == CALL || ic->next->op == PCALL)) // Might mess up A and X, but these would have been saved before if surviving, and will not be needed again before the call.
 227     return(true);
 228
 229   if((ic->op == CRITICAL || ic->op == ENDCRITICAL) && (unused_A || dying_A))
 230     return(true);
 231
 232   // Y must be free
 233   if ((ic->op == GET_VALUE_AT_ADDRESS) && (unused_Y || dying_Y))
 234     return true;
 235   if (POINTER_SET(ic) && (unused_Y || dying_Y))
 236     return true;
 237   if (ic->op == '=')
 238     return true;
 239
 240   return(false);
 241 }
 242
 243 template <class G_t, class I_t>
 244 static bool AXinst_ok(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
 245 {
 246   const iCode *ic = G[i].ic;
 247
 248   const i_assignment_t &ia = a.i_assignment;
 249
 250   if(ic->op == '!' ||
 251     ic->op == '~' ||
 252     ic->op == IPUSH ||
 253     ic->op == CALL ||
 254     ic->op == FUNCTION ||
 255     ic->op == ENDFUNCTION ||
 256     ic->op == RETURN ||
 257     ic->op == LABEL ||
 258     ic->op == GOTO ||
 259     ic->op == '+' ||
 260     ic->op == '-' ||
 261     ic->op == NE_OP || ic->op == EQ_OP ||
 262     ic->op == '^' ||
 263     ic->op == '|' ||
 264     ic->op == BITWISEAND ||
 265     ic->op == GETABIT ||
 266     ic->op == GETBYTE ||
 267     ic->op == GETWORD ||
 268     /*ic->op == LEFT_OP ||
 269     ic->op == RIGHT_OP ||*/
 270     ic->op == GET_VALUE_AT_ADDRESS ||
 271     ic->op == '=' ||
 272     ic->op == ADDRESS_OF ||
 273     ic->op == RECEIVE ||
 274     ic->op == SEND ||
 275     ic->op == DUMMY_READ_VOLATILE ||
 276     ic->op == CRITICAL ||
 277     ic->op == ENDCRITICAL ||
 278     ic->op == ROT && IS_OP_LITERAL (IC_RIGHT (ic)) && operandLitValueUll (IC_RIGHT (ic)) * 2 == bitsForType (operandType (IC_LEFT (ic))))
 279     return(true);
 280
 281   bool unused_A = (ia.registers[REG_A][1] < 0);
 282   bool unused_X = (ia.registers[REG_X][1] < 0);
 283
 284   if (unused_A || unused_X)
 285     return(true);
 286
 287   const operand *left = IC_LEFT(ic);
 288   const operand *right = IC_RIGHT(ic);
 289   const operand *result = IC_RESULT(ic);
 290
 291   bool result_in_A = operand_in_reg(result, REG_A, ia, i, G) && !(ic->op == '=' && POINTER_SET(ic));
 292   bool result_in_X = operand_in_reg(result, REG_X, ia, i, G) && !(ic->op == '=' && POINTER_SET(ic));
 293   bool left_in_A = operand_in_reg(result, REG_A, ia, i, G);
 294   bool left_in_X = operand_in_reg(result, REG_X, ia, i, G);
 295   bool right_in_A = operand_in_reg(result, REG_A, ia, i, G);
 296   bool right_in_X = operand_in_reg(result, REG_X, ia, i, G);
 297
 298   bool result_is_ax = operand_is_ax (result, a, i, G, I);
 299   bool left_is_ax = operand_is_ax (left, a, i, G, I);
 300   bool right_is_ax = operand_is_ax (right, a, i, G, I);
 301
 302   if (!result_is_ax && !left_is_ax && !right_is_ax)
 303     return(true);
 304
 305   return(false);
 306 }
 307
 308 template <class G_t, class I_t>
 309 static void set_surviving_regs(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
 310 {
 311   iCode *ic = G[i].ic;
 312
 313   bitVectClear(ic->rMask);
 314   bitVectClear(ic->rSurv);
 315
 316   cfg_alive_t::const_iterator v, v_end;
 317   for (v = G[i].alive.begin(), v_end = G[i].alive.end(); v != v_end; ++v)
 318     {
 319       if(a.global[*v] < 0)
 320         continue;
 321       ic->rMask = bitVectSetBit(ic->rMask, a.global[*v]);
 322
 323       if(G[i].dying.find(*v) == G[i].dying.end())
 324         if(!((IC_RESULT(ic) && !POINTER_SET(ic)) && IS_SYMOP(IC_RESULT(ic)) && OP_SYMBOL_CONST(IC_RESULT(ic))->key == I[*v].v))
 325           ic->rSurv = bitVectSetBit(ic->rSurv, a.global[*v]);
 326     }
 327 }
 328
 329 template <class G_t, class I_t>
 330 static void assign_operand_for_cost(operand *o, const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
 331 {
 332   if(!o || !IS_SYMOP(o))
 333     return;
 334   symbol *sym = OP_SYMBOL(o);
 335   operand_map_t::const_iterator oi, oi_end;
 336   for(boost::tie(oi, oi_end) = G[i].operands.equal_range(OP_SYMBOL_CONST(o)->key); oi != oi_end; ++oi)
 337     {
 338       var_t v = oi->second;
 339       if(a.global[v] >= 0)
 340         {
 341           sym->regs[I[v].byte] = regsm6502 + a.global[v];
 342           sym->accuse = 0;
 343           sym->isspilt = false;
 344           sym->nRegs = I[v].size;
 345         }
 346       else
 347         {
 348           sym->isspilt = true;
 349           sym->accuse = 0;
 350           sym->nRegs = I[v].size;
 351           for(int i = 0; i < I[v].size; i++)
 352             sym->regs[i] = 0;
 353         }
 354     }
 355 }
 356
 357 template <class G_t, class I_t>
 358 static void assign_operands_for_cost(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
 359 {
 360   const iCode *ic = G[i].ic;
 361
 362   assign_operand_for_cost(IC_LEFT(ic), a, i, G, I);
 363   assign_operand_for_cost(IC_RIGHT(ic), a, i, G, I);
 364   assign_operand_for_cost(IC_RESULT(ic), a, i, G, I);
 365
 366   if(ic->op == SEND && ic->builtinSEND)
 367     assign_operands_for_cost(a, (unsigned short)*(adjacent_vertices(i, G).first), G, I);
 368 }
 369
 370 // Check that the operand is either fully in registers or fully in memory.
 371 template <class G_t, class I_t>
 372 static bool operand_sane(const operand *o, const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
 373 {
 374   if(!o || !IS_SYMOP(o))
 375     return(true);
 376
 377   operand_map_t::const_iterator oi, oi2, oi_end;
 378   boost::tie(oi, oi_end) = G[i].operands.equal_range(OP_SYMBOL_CONST(o)->key);
 379
 380   if(oi == oi_end)
 381     return(true);
 382
 383   // Go to the second byte. If the operand is only a single byte, it cannot be
 384   // an unsupported register combination or split between register and memory.
 385   oi2 = oi;
 386   oi2++;
 387   if (oi2 == oi_end)
 388     return(true);
 389
 390   // Register combinations code generation cannot handle yet (AY, XY, YA).
 391   if(std::binary_search(a.local.begin(), a.local.end(), oi->second) && std::binary_search(a.local.begin(), a.local.end(), oi2->second))
 392     {
 393       const reg_t l = a.global[oi->second];
 394       const reg_t h = a.global[oi2->second];
 395 //      if(l == REG_A && h == REG_Y || l == REG_Y)
 396       if(l != REG_A || h != REG_X)
 397         return(false);
 398     }
 399
 400   // In registers.
 401   if(std::binary_search(a.local.begin(), a.local.end(), oi->second))
 402     {
 403       while(++oi != oi_end)
 404         if(!std::binary_search(a.local.begin(), a.local.end(), oi->second))
 405           return(false);
 406       if (OP_SYMBOL_CONST (o)->nRegs > 2) // cannot handle register operand wider than 2 B yet.
 407         return (false);
 408     }
 409   else
 410     {
 411        while(++oi != oi_end)
 412         if(std::binary_search(a.local.begin(), a.local.end(), oi->second))
 413           return(false);
 414     }
 415
 416   return(true);
 417 }
 418
 419 template <class G_t, class I_t>
 420 static bool inst_sane(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
 421 {
 422   const iCode *ic = G[i].ic;
 423
 424   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));
 425 }
 426
 427 // Cost function.
 428 template <class G_t, class I_t>
 429 static float instruction_cost(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
 430 {
 431   iCode *ic = G[i].ic;
 432   float c;
 433
 434   wassert (TARGET_IS_MOS6502 || TARGET_IS_MOS65C02);
 435   wassert(ic);
 436
 437   if(!inst_sane(a, i, G, I))
 438     return(std::numeric_limits<float>::infinity());
 439
 440 #if 0
 441   std::cout << "Calculating at cost at ic " << ic->key << ", op " << ic->op << " for: ";
 442   print_assignment(a);
 443   std::cout << "\n";
 444   std::cout.flush();
 445 #endif
 446
 447   if(ic->generated)
 448     {
 449 #if 0
 450   std::cout << "Skipping, already generated.\n";
 451 #endif
 452     return(0.0f);
 453     }
 454
 455   if(!XAinst_ok(a, i, G, I))
 456     return(std::numeric_limits<float>::infinity());
 457
 458   if(!AXinst_ok(a, i, G, I))
 459     return(std::numeric_limits<float>::infinity());
 460
 461   switch(ic->op)
 462     {
 463     // Register assignment doesn't matter for these:
 464     case FUNCTION:
 465     case ENDFUNCTION:
 466     case LABEL:
 467     case GOTO:
 468     case INLINEASM:
 469 #if 0
 470   std::cout << "Skipping, indepent from assignment.\n";
 471 #endif
 472       return(0.0f);
 473     case '!':
 474     case '~':
 475     case UNARYMINUS:
 476     case '+':
 477     case '-':
 478     case '^':
 479     case '|':
 480     case BITWISEAND:
 481     case IPUSH:
 482     case IPUSH_VALUE_AT_ADDRESS:
 483     //case IPOP:
 484     case CALL:
 485     case PCALL:
 486     case RETURN:
 487     case '*':
 488     case '/':
 489     case '%':
 490     case '>':
 491     case '<':
 492     case LE_OP:
 493     case GE_OP:
 494     case EQ_OP:
 495     case NE_OP:
 496     case AND_OP:
 497     case OR_OP:
 498     case GETABIT:
 499     case GETBYTE:
 500     case GETWORD:
 501     case ROT:
 502     case LEFT_OP:
 503     case RIGHT_OP:
 504     case GET_VALUE_AT_ADDRESS:
 505 //    case SET_VALUE_AT_ADDRESS:
 506     case '=':
 507     case IFX:
 508     case ADDRESS_OF:
 509     case JUMPTABLE:
 510     case CAST:
 511     case RECEIVE:
 512     case SEND:
 513     case DUMMY_READ_VOLATILE:
 514     case CRITICAL:
 515     case ENDCRITICAL:
 516       assign_operands_for_cost(a, i, G, I);
 517       set_surviving_regs(a, i, G, I);
 518       c = drym6502iCode(ic);
 519       ic->generated = false;
 520 #if 0
 521       std::cout << "Got cost " << c << "\n";
 522 #endif
 523       return(c);
 524     default:
 525       std::cout << "no cost for op " << ic->op << "\n";
 526       return(0.0f);
 527     }
 528 }
 529
 530 // For early removal of assignments that cannot be extended to valid assignments. This is just a dummy for now.
 531 template <class G_t, class I_t>
 532 static bool assignment_hopeless(const assignment &a, unsigned short int i, const G_t &G, const I_t &I, const var_t lastvar)
 533 {
 534   return(false);
 535 }
 536
 537 // Increase chance of finding good compatible assignments at join nodes.
 538 template <class T_t>
 539 static void get_best_local_assignment_biased(assignment &a, typename boost::graph_traits<T_t>::vertex_descriptor t, const T_t &T)
 540 {
 541   a = *T[t].assignments.begin();
 542
 543   varset_t newlocal;
 544   std::set_union(T[t].alive.begin(), T[t].alive.end(), a.local.begin(), a.local.end(), std::inserter(newlocal, newlocal.end()));
 545   a.local = newlocal;
 546 }
 547
 548 // This is just a dummy for now, it probably isn't really needed for m6502 due to the low number of registers.
 549 template <class G_t, class I_t>
 550 static float rough_cost_estimate(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
 551 {
 552   return(0.0f);
 553 }
 554
 555 // Code for another ic is generated when generating this one. Mark the other as generated.
 556 static void extra_ic_generated(iCode *ic)
 557 {
 558   if(ic->op == '>' || ic->op == '<' || ic->op == LE_OP || ic->op == GE_OP || ic->op == EQ_OP || ic->op == NE_OP || ic->op == '^' || ic->op == '|' || ic->op == BITWISEAND)
 559     {
 560       iCode *ifx;
 561       if (ifx = ifxForOp (IC_RESULT (ic), ic))
 562         {
 563           OP_SYMBOL (IC_RESULT (ic))->for_newralloc = false;
 564           OP_SYMBOL (IC_RESULT (ic))->regType = REG_CND;
 565           ifx->generated = true;
 566         }
 567     }
 568   if(ic->op == '-' && IS_VALOP (IC_RIGHT (ic)) && operandLitValue (IC_RIGHT (ic)) == 1 && getSize(operandType(IC_RESULT (ic))) == 1 && !isOperandInFarSpace (IC_RESULT (ic)) && isOperandEqual (IC_RESULT (ic), IC_LEFT (ic)))
 569     {
 570       iCode *ifx;
 571       if (ifx = ifxForOp (IC_RESULT (ic), ic))
 572         {
 573           OP_SYMBOL (IC_RESULT (ic))->for_newralloc = false;
 574           OP_SYMBOL (IC_RESULT (ic))->regType = REG_CND;
 575           ifx->generated = true;
 576         }
 577     }
 578 }
 579
 580 template <class T_t, class G_t, class I_t>
 581 static bool tree_dec_ralloc(T_t &T, G_t &G, const I_t &I)
 582 {
 583   bool assignment_optimal;
 584
 585   con2_t I2(boost::num_vertices(I));
 586   for(unsigned int i = 0; i < boost::num_vertices(I); i++)
 587     {
 588       I2[i].v = I[i].v;
 589       I2[i].byte = I[i].byte;
 590       I2[i].size = I[i].size;
 591       I2[i].name = I[i].name;
 592     }
 593   typename boost::graph_traits<I_t>::edge_iterator e, e_end;
 594   for(boost::tie(e, e_end) = boost::edges(I); e != e_end; ++e)
 595     add_edge(boost::source(*e, I), boost::target(*e, I), I2);
 596
 597   assignment ac;
 598   assignment_optimal = true;
 599   tree_dec_ralloc_nodes(T, find_root(T), G, I2, ac, &assignment_optimal);
 600
 601   const assignment &winner = *(T[find_root(T)].assignments.begin());
 602
 603 #ifdef DEBUG_RALLOC_DEC
 604   std::cout << "Winner: ";
 605   for(unsigned int i = 0; i < boost::num_vertices(I); i++)
 606   {
 607         std::cout << "(" << i << ", " << int(winner.global[i]) << ") ";
 608   }
 609   std::cout << "\n";
 610   std::cout << "Cost: " << winner.s << "\n";
 611   std::cout.flush();
 612 #endif
 613
 614   // Todo: Make this an assertion
 615   if(winner.global.size() != boost::num_vertices(I))
 616     {
 617       std::cerr << "ERROR: No Assignments at root\n";
 618       exit(-1);
 619     }
 620
 621   for(unsigned int v = 0; v < boost::num_vertices(I); v++)
 622     {
 623       symbol *sym = (symbol *)(hTabItemWithKey(liveRanges, I[v].v));
 624       if(winner.global[v] >= 0)
 625         {
 626           sym->regs[I[v].byte] = regsm6502 + winner.global[v];
 627           sym->accuse = 0;
 628           sym->isspilt = false;
 629           sym->nRegs = I[v].size;
 630         }
 631       else
 632         {
 633           for(int i = 0; i < I[v].size; i++)
 634             sym->regs[i] = 0;
 635           sym->accuse = 0;
 636           sym->nRegs = I[v].size;
 637           wassert (sym->nRegs);
 638           //m6502SpillThis(sym); Leave it to regFix, which can do some spillocation compaction. Todo: Use Thorup instead.
 639           sym->isspilt = false;
 640         }
 641     }
 642
 643   for(unsigned int i = 0; i < boost::num_vertices(G); i++)
 644     set_surviving_regs(winner, i, G, I);
 645
 646   return(!assignment_optimal);
 647 }
 648
 649 iCode *m6502_ralloc2_cc(ebbIndex *ebbi)
 650 {
 651   eBBlock **const ebbs = ebbi->bbOrder;
 652   const int count = ebbi->count;
 653
 654 #ifdef DEBUG_RALLOC_DEC
 655   std::cout << "Processing " << currFunc->name << " from " << dstFileName << "\n"; std::cout.flush();
 656 #endif
 657
 658   cfg_t control_flow_graph;
 659
 660   con_t conflict_graph;
 661
 662   iCode *ic = create_cfg(control_flow_graph, conflict_graph, ebbi);
 663
 664   if(optimize.genconstprop)
 665     recomputeValinfos(ic, ebbi, "_2");
 666
 667   guessCounts(ic, ebbi);
 668
 669   if(options.dump_graphs)
 670     dump_cfg(control_flow_graph);
 671
 672   if(options.dump_graphs)
 673     dump_con(conflict_graph);
 674
 675   tree_dec_t tree_decomposition;
 676
 677   get_nice_tree_decomposition(tree_decomposition, control_flow_graph);
 678
 679   alive_tree_dec(tree_decomposition, control_flow_graph);
 680
 681   good_re_root(tree_decomposition);
 682   nicify(tree_decomposition);
 683   alive_tree_dec(tree_decomposition, control_flow_graph);
 684
 685   if(options.dump_graphs)
 686     dump_tree_decomposition(tree_decomposition);
 687
 688   guessCounts (ic, ebbi);
 689
 690   m6502_assignment_optimal = !tree_dec_ralloc(tree_decomposition, control_flow_graph, conflict_graph);
 691
 692   m6502RegFix (ebbs, count);
 693
 694   /* do the overlaysegment stuff SDCCmem.c */
 695   doOverlays (ebbs, count);
 696
 697   return(ic);
 698 }
 699