compilers/imcc/cfg.c

   1 /*
   2  * Copyright (C) 2002-2009, Parrot Foundation.
   3  * $Id$
   4  */
   5
   6 /*
   7
   8 =head1 NAME
   9
  10 compilers/imcc/cfg.c
  11
  12 =head1 DESCRIPTION
  13
  14 A basic block is the longest sequence of instructions that we are sure will be
  15 executed sequentially: no branches, no labels.
  16
  17 The control-flow graph is a directed graph that reflects the flow of execution
  18 between blocks.
  19
  20 =head2 Functions
  21
  22 =over 4
  23
  24 =cut
  25
  26 */
  27
  28 #include <stdlib.h>
  29 #include <string.h>
  30 #include "imc.h"
  31 #include "optimizer.h"
  32
  33 /* HEADERIZER HFILE: compilers/imcc/cfg.h */
  34
  35 /* HEADERIZER BEGIN: static */
  36 /* Don't modify between HEADERIZER BEGIN / HEADERIZER END.  Your changes will be lost. */
  37
  38 static void analyse_life_block(PARROT_INTERP,
  39     ARGIN(const Basic_block* bb),
  40     ARGMOD(SymReg *r))
  41         __attribute__nonnull__(1)
  42         __attribute__nonnull__(2)
  43         __attribute__nonnull__(3)
  44         FUNC_MODIFIES(*r);
  45
  46 static void analyse_life_symbol(PARROT_INTERP,
  47     ARGIN(const IMC_Unit *unit),
  48     ARGMOD(SymReg* r))
  49         __attribute__nonnull__(1)
  50         __attribute__nonnull__(2)
  51         __attribute__nonnull__(3)
  52         FUNC_MODIFIES(* r);
  53
  54 static void bb_add_edge(PARROT_INTERP,
  55     ARGMOD(IMC_Unit *unit),
  56     ARGIN(Basic_block *from),
  57     ARGMOD(Basic_block *to))
  58         __attribute__nonnull__(1)
  59         __attribute__nonnull__(2)
  60         __attribute__nonnull__(3)
  61         __attribute__nonnull__(4)
  62         FUNC_MODIFIES(*unit)
  63         FUNC_MODIFIES(*to);
  64
  65 static void bb_check_set_addr(PARROT_INTERP,
  66     ARGMOD(IMC_Unit *unit),
  67     ARGMOD(Basic_block *bb),
  68     ARGIN(const SymReg *label))
  69         __attribute__nonnull__(1)
  70         __attribute__nonnull__(2)
  71         __attribute__nonnull__(3)
  72         __attribute__nonnull__(4)
  73         FUNC_MODIFIES(*unit)
  74         FUNC_MODIFIES(*bb);
  75
  76 static void bb_findadd_edge(PARROT_INTERP,
  77     ARGMOD(IMC_Unit *unit),
  78     ARGIN(Basic_block *from),
  79     ARGIN(const SymReg *label))
  80         __attribute__nonnull__(1)
  81         __attribute__nonnull__(2)
  82         __attribute__nonnull__(3)
  83         __attribute__nonnull__(4)
  84         FUNC_MODIFIES(*unit);
  85
  86 static void bb_remove_edge(ARGMOD(IMC_Unit *unit), ARGMOD(Edge *edge))
  87         __attribute__nonnull__(1)
  88         __attribute__nonnull__(2)
  89         FUNC_MODIFIES(*unit)
  90         FUNC_MODIFIES(*edge);
  91
  92 PARROT_WARN_UNUSED_RESULT
  93 static int check_invoke_type(PARROT_INTERP,
  94     ARGIN(const IMC_Unit *unit),
  95     ARGIN(const Instruction *ins))
  96         __attribute__nonnull__(1)
  97         __attribute__nonnull__(2)
  98         __attribute__nonnull__(3);
  99
 100 static void free_dominance_frontiers(ARGMOD(IMC_Unit *unit))
 101         __attribute__nonnull__(1)
 102         FUNC_MODIFIES(*unit);
 103
 104 static void free_dominators(ARGMOD(IMC_Unit *unit))
 105         __attribute__nonnull__(1)
 106         FUNC_MODIFIES(*unit);
 107
 108 static void free_edge(ARGMOD(IMC_Unit *unit))
 109         __attribute__nonnull__(1)
 110         FUNC_MODIFIES(*unit);
 111
 112 static void free_loops(ARGMOD(IMC_Unit *unit))
 113         __attribute__nonnull__(1)
 114         FUNC_MODIFIES(*unit);
 115
 116 static void init_basic_blocks(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
 117         __attribute__nonnull__(1)
 118         __attribute__nonnull__(2)
 119         FUNC_MODIFIES(*unit);
 120
 121 PARROT_CANNOT_RETURN_NULL
 122 PARROT_WARN_UNUSED_RESULT
 123 static Basic_block* make_basic_block(PARROT_INTERP,
 124     ARGMOD(IMC_Unit *unit),
 125     ARGMOD(Instruction *ins))
 126         __attribute__nonnull__(1)
 127         __attribute__nonnull__(2)
 128         __attribute__nonnull__(3)
 129         FUNC_MODIFIES(*unit)
 130         FUNC_MODIFIES(*ins);
 131
 132 static void mark_loop(PARROT_INTERP,
 133     ARGMOD(IMC_Unit *unit),
 134     ARGIN(const Edge *e))
 135         __attribute__nonnull__(1)
 136         __attribute__nonnull__(2)
 137         __attribute__nonnull__(3)
 138         FUNC_MODIFIES(*unit);
 139
 140 static void propagate_need(
 141     ARGMOD(Basic_block *bb),
 142     ARGIN(const SymReg *r),
 143     int i)
 144         __attribute__nonnull__(1)
 145         __attribute__nonnull__(2)
 146         FUNC_MODIFIES(*bb);
 147
 148 static void sort_loops(PARROT_INTERP, ARGIN(IMC_Unit *unit))
 149         __attribute__nonnull__(1)
 150         __attribute__nonnull__(2);
 151
 152 #define ASSERT_ARGS_analyse_life_block __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 153        PARROT_ASSERT_ARG(interp) \
 154     , PARROT_ASSERT_ARG(bb) \
 155     , PARROT_ASSERT_ARG(r))
 156 #define ASSERT_ARGS_analyse_life_symbol __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 157        PARROT_ASSERT_ARG(interp) \
 158     , PARROT_ASSERT_ARG(unit) \
 159     , PARROT_ASSERT_ARG(r))
 160 #define ASSERT_ARGS_bb_add_edge __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 161        PARROT_ASSERT_ARG(interp) \
 162     , PARROT_ASSERT_ARG(unit) \
 163     , PARROT_ASSERT_ARG(from) \
 164     , PARROT_ASSERT_ARG(to))
 165 #define ASSERT_ARGS_bb_check_set_addr __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 166        PARROT_ASSERT_ARG(interp) \
 167     , PARROT_ASSERT_ARG(unit) \
 168     , PARROT_ASSERT_ARG(bb) \
 169     , PARROT_ASSERT_ARG(label))
 170 #define ASSERT_ARGS_bb_findadd_edge __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 171        PARROT_ASSERT_ARG(interp) \
 172     , PARROT_ASSERT_ARG(unit) \
 173     , PARROT_ASSERT_ARG(from) \
 174     , PARROT_ASSERT_ARG(label))
 175 #define ASSERT_ARGS_bb_remove_edge __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 176        PARROT_ASSERT_ARG(unit) \
 177     , PARROT_ASSERT_ARG(edge))
 178 #define ASSERT_ARGS_check_invoke_type __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 179        PARROT_ASSERT_ARG(interp) \
 180     , PARROT_ASSERT_ARG(unit) \
 181     , PARROT_ASSERT_ARG(ins))
 182 #define ASSERT_ARGS_free_dominance_frontiers __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 183        PARROT_ASSERT_ARG(unit))
 184 #define ASSERT_ARGS_free_dominators __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 185        PARROT_ASSERT_ARG(unit))
 186 #define ASSERT_ARGS_free_edge __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 187        PARROT_ASSERT_ARG(unit))
 188 #define ASSERT_ARGS_free_loops __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 189        PARROT_ASSERT_ARG(unit))
 190 #define ASSERT_ARGS_init_basic_blocks __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 191        PARROT_ASSERT_ARG(interp) \
 192     , PARROT_ASSERT_ARG(unit))
 193 #define ASSERT_ARGS_make_basic_block __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 194        PARROT_ASSERT_ARG(interp) \
 195     , PARROT_ASSERT_ARG(unit) \
 196     , PARROT_ASSERT_ARG(ins))
 197 #define ASSERT_ARGS_mark_loop __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 198        PARROT_ASSERT_ARG(interp) \
 199     , PARROT_ASSERT_ARG(unit) \
 200     , PARROT_ASSERT_ARG(e))
 201 #define ASSERT_ARGS_propagate_need __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 202        PARROT_ASSERT_ARG(bb) \
 203     , PARROT_ASSERT_ARG(r))
 204 #define ASSERT_ARGS_sort_loops __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 205        PARROT_ASSERT_ARG(interp) \
 206     , PARROT_ASSERT_ARG(unit))
 207 /* Don't modify between HEADERIZER BEGIN / HEADERIZER END.  Your changes will be lost. */
 208 /* HEADERIZER END: static */
 209
 210 /* Code: */
 211
 212 #define INVOKE_SUB_CALL 1
 213 #define INVOKE_SUB_RET  2
 214 #define INVOKE_SUB_LOOP 3
 215 #define INVOKE_SUB_OTHER 4
 216
 217 /*
 218
 219 =item C<static int check_invoke_type(PARROT_INTERP, const IMC_Unit *unit, const
 220 Instruction *ins)>
 221
 222 Given an invoke-type instruction, returns the type of the invocation.
 223
 224 =cut
 225
 226 */
 227
 228 PARROT_WARN_UNUSED_RESULT
 229 static int
 230 check_invoke_type(PARROT_INTERP, ARGIN(const IMC_Unit    *unit),
 231                                  ARGIN(const Instruction *ins))
 232 {
 233     ASSERT_ARGS(check_invoke_type)
 234     /* 1) pcc sub call or yield */
 235     if (ins->type & (ITPCCSUB | ITPCCYIELD))
 236         return INVOKE_SUB_CALL;
 237
 238     /*
 239      * inside another pcc_sub
 240      * 2) invoke = loop to begin
 241      */
 242     if (unit->instructions->symregs[0]
 243     &&  unit->instructions->symregs[0]->pcc_sub)
 244         return INVOKE_SUB_LOOP;
 245
 246     /* 3) invoke P1 returns */
 247     if (ins->opsize == 2)
 248         return INVOKE_SUB_RET;
 249
 250     /* 4) other usage, too complex to follow */
 251     IMCC_INFO(interp)->dont_optimize    = 1;
 252     IMCC_INFO(interp)->optimizer_level &= ~OPT_PASM;
 253
 254     return INVOKE_SUB_OTHER;
 255 }
 256
 257
 258 /*
 259
 260 =item C<void find_basic_blocks(PARROT_INTERP, IMC_Unit *unit, int first)>
 261
 262 Finds all basic blocks in the given IMC_Unit, expanding PCC calls if first is
 263 true.
 264
 265 =cut
 266
 267 */
 268
 269 void
 270 find_basic_blocks(PARROT_INTERP, ARGMOD(IMC_Unit *unit), int first)
 271 {
 272     ASSERT_ARGS(find_basic_blocks)
 273     Basic_block          *bb;
 274     Instruction          *ins;
 275     const SymHash * const hsh = &unit->hash;
 276     int                   nu  = 0;
 277     unsigned int          i;
 278
 279     IMCC_info(interp, 2, "find_basic_blocks\n");
 280     init_basic_blocks(interp, unit);
 281
 282     for (i = 0; i < hsh->size; i++) {
 283         SymReg *r;
 284
 285         for (r = hsh->data[i]; r; r = r->next) {
 286             if (r->type & VTADDRESS)
 287                 r->last_ins = NULL;
 288         }
 289     }
 290
 291     ins = unit->instructions;
 292
 293     if (unit->type & IMC_PCCSUB) {
 294         IMCC_debug(interp, DEBUG_CFG, "pcc_sub %s nparams %d\n",
 295                 ins->symregs[0]->name, ins->symregs[0]->pcc_sub->nargs);
 296         expand_pcc_sub(interp, unit, ins);
 297     }
 298
 299     ins->index = i = 0;
 300
 301     bb         = make_basic_block(interp, unit, ins);
 302
 303     if (ins->type & ITBRANCH) {
 304         SymReg * const addr = get_branch_reg(bb->end);
 305         if (addr)
 306             addr->last_ins = ins;
 307     }
 308
 309     for (ins = ins->next; ins; ins = ins->next) {
 310         bb->end      = ins;
 311         ins->index   = ++i;
 312         ins->bbindex = unit->n_basic_blocks - 1;
 313
 314         if (ins->opnum == -1 && (ins->type & ITPCCSUB)) {
 315             if (first) {
 316                 if (ins->type & ITLABEL) {
 317                     expand_pcc_sub_ret(interp, unit, ins);
 318                     ins->type &= ~ITLABEL;
 319                 }
 320                 else {
 321                     /* if this is a sub call expand it */
 322                     expand_pcc_sub_call(interp, unit, ins);
 323                 }
 324
 325                 ins->type &= ~ITPCCSUB;
 326             }
 327         }
 328         else if (ins->type & ITLABEL) {
 329             /* set the labels address (ins) */
 330             ins->symregs[0]->first_ins = ins;
 331         }
 332
 333         /* a LABEL starts a new basic block, but not, if we already have
 334          * a new one (last was a branch) */
 335         if (nu)
 336             nu = 0;
 337         else if (ins->type & ITLABEL) {
 338             bb->end = ins->prev;
 339             bb      = make_basic_block(interp, unit, ins);
 340         }
 341
 342         /* a branch is the end of a basic block
 343          * so start a new one with the next instruction */
 344         if (ins->type & ITBRANCH) {
 345             SymReg * const addr = get_branch_reg(bb->end);
 346
 347             if (addr)
 348                 addr->last_ins = ins;
 349
 350             /* ignore set_addr - no new basic block */
 351             if (STREQ(ins->opname, "set_addr"))
 352                 continue;
 353
 354             if (ins->next)
 355                 bb = make_basic_block(interp, unit, ins->next);
 356
 357             nu = 1;
 358         }
 359     }
 360
 361     if (IMCC_INFO(interp)->debug & DEBUG_CFG) {
 362         dump_instructions(interp, unit);
 363         dump_labels(unit);
 364     }
 365 }
 366
 367
 368 /*
 369
 370 =item C<static void bb_check_set_addr(PARROT_INTERP, IMC_Unit *unit, Basic_block
 371 *bb, const SymReg *label)>
 372
 373 Looks for a C<set_addr> op in the current unit referring to the given label.
 374
 375 =cut
 376
 377 */
 378
 379 static void
 380 bb_check_set_addr(PARROT_INTERP, ARGMOD(IMC_Unit *unit),
 381         ARGMOD(Basic_block *bb), ARGIN(const SymReg *label))
 382 {
 383     ASSERT_ARGS(bb_check_set_addr)
 384     const Instruction *ins;
 385
 386     for (ins = unit->instructions; ins; ins = ins->next) {
 387         if ((ins->opnum == PARROT_OP_set_addr_p_ic)
 388         &&   STREQ(label->name, ins->symregs[1]->name)) {
 389             IMCC_debug(interp, DEBUG_CFG, "set_addr %s\n",
 390                     ins->symregs[1]->name);
 391
 392             /* connect this block with first and last block */
 393             bb_add_edge(interp, unit, unit->bb_list[0], bb);
 394             bb_add_edge(interp, unit, unit->bb_list[unit->n_basic_blocks - 1], bb);
 395
 396             /* and mark the instruction as being kind of a branch */
 397             bb->start->type |= ITADDR;
 398
 399             break;
 400         }
 401     }
 402 }
 403
 404
 405 /*
 406
 407 =item C<void build_cfg(PARROT_INTERP, IMC_Unit *unit)>
 408
 409 Once the basic blocks have been computed, build_cfg computes the dependencies
 410 between them.
 411
 412 =cut
 413
 414 */
 415
 416 void
 417 build_cfg(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
 418 {
 419     ASSERT_ARGS(build_cfg)
 420     Basic_block *last = NULL;
 421     unsigned int i;
 422     int changes;
 423
 424     IMCC_info(interp, 2, "build_cfg\n");
 425
 426     for (i = 0; i < unit->n_basic_blocks; i++) {
 427         Basic_block * const bb = unit->bb_list[i];
 428         SymReg             *addr;
 429
 430         /* if the block can fall-through */
 431         if (i > 0 && ! (last->end->type & IF_goto))
 432             bb_add_edge(interp, unit, last, bb);
 433
 434         /* check first ins, if label try to find a set_addr op */
 435         if (bb->start->type & ITLABEL)
 436             bb_check_set_addr(interp, unit, bb, bb->start->symregs[0]);
 437
 438         /* look if last instruction is a branch */
 439         addr = get_branch_reg(bb->end);
 440
 441         if (addr)
 442             bb_findadd_edge(interp, unit, bb, addr);
 443         else if (STREQ(bb->start->opname, "invoke")
 444              ||  STREQ(bb->start->opname, "invokecc")) {
 445             if (check_invoke_type(interp, unit, bb->start) == INVOKE_SUB_LOOP)
 446                 bb_add_edge(interp, unit, bb, unit->bb_list[0]);
 447         }
 448
 449         last = bb;
 450     }
 451
 452     /* Decouple unreachable blocks (not the first block, with no predecessors)
 453      * from the CFG */
 454     do {
 455         unsigned int i;
 456         changes = 0;
 457
 458         for (i = 1; i < unit->n_basic_blocks; i++) {
 459             Basic_block * const bb = unit->bb_list[i];
 460
 461             if (!bb->pred_list) {
 462                 /* Remove all successor edges of block bb */
 463                 while (bb->succ_list) {
 464                     bb_remove_edge(unit, bb->succ_list);
 465                     IMCC_debug(interp, DEBUG_CFG,
 466                             "remove edge from bb: %d\n", bb->index);
 467                     changes = 1;
 468                 }
 469             }
 470         }
 471     } while (changes);
 472
 473     if (IMCC_INFO(interp)->debug & DEBUG_CFG)
 474         dump_cfg(unit);
 475 }
 476
 477
 478 /*
 479
 480 =item C<static void bb_findadd_edge(PARROT_INTERP, IMC_Unit *unit, Basic_block
 481 *from, const SymReg *label)>
 482
 483 Finds the placement of the given label and links its containing block to the
 484 given basic block.
 485
 486 =cut
 487
 488 */
 489
 490 static void
 491 bb_findadd_edge(PARROT_INTERP, ARGMOD(IMC_Unit *unit), ARGIN(Basic_block *from),
 492         ARGIN(const SymReg *label))
 493 {
 494     ASSERT_ARGS(bb_findadd_edge)
 495     Instruction         *ins;
 496     const SymReg * const r = find_sym(interp, label->name);
 497
 498     if (r && (r->type & VTADDRESS) && r->first_ins)
 499         bb_add_edge(interp, unit, from, unit->bb_list[r->first_ins->bbindex]);
 500     else {
 501         IMCC_debug(interp, DEBUG_CFG, "register branch %I ", from->end);
 502         for (ins = from->end; ins; ins = ins->prev) {
 503             if ((ins->type & ITBRANCH)
 504             &&   STREQ(ins->opname, "set_addr")
 505             &&   ins->symregs[1]->first_ins) {
 506                 bb_add_edge(interp, unit, from,
 507                     unit-> bb_list[ins->symregs[1]->first_ins->bbindex]);
 508                 IMCC_debug(interp, DEBUG_CFG, "(%s) ", ins->symregs[1]->name);
 509                 break;
 510             }
 511         }
 512
 513         IMCC_debug(interp, DEBUG_CFG, "\n");
 514     }
 515 }
 516
 517
 518 /*
 519
 520 =item C<int blocks_are_connected(const Basic_block *from, const Basic_block
 521 *to)>
 522
 523 Returns true or false whether the given blocks are linked.
 524
 525 =cut
 526
 527 */
 528
 529 PARROT_WARN_UNUSED_RESULT
 530 int
 531 blocks_are_connected(ARGIN(const Basic_block *from),
 532                      ARGIN(const Basic_block *to))
 533 {
 534     ASSERT_ARGS(blocks_are_connected)
 535     const Edge *pred = to->pred_list;
 536
 537     while (pred) {
 538         /*already linked*/
 539         if (pred->from == from)
 540             return 1;
 541
 542         pred = pred->pred_next;
 543     }
 544
 545     return 0;
 546 }
 547
 548
 549 /*
 550
 551 =item C<static void bb_add_edge(PARROT_INTERP, IMC_Unit *unit, Basic_block
 552 *from, Basic_block *to)>
 553
 554 Adds an edge between the two given blocks.
 555
 556 =cut
 557
 558 */
 559
 560 static void
 561 bb_add_edge(PARROT_INTERP,
 562         ARGMOD(IMC_Unit *unit),
 563         ARGIN(Basic_block  *from),
 564         ARGMOD(Basic_block *to))
 565 {
 566     ASSERT_ARGS(bb_add_edge)
 567     Edge *e;
 568     if (blocks_are_connected(from, to))
 569         return;
 570
 571     /* we assume that the data is correct, and thus if the edge is not
 572      * on the predecessors of 'from', it won't be on the successors of 'to' */
 573     e             = mem_gc_allocate_typed(interp, Edge);
 574
 575     e->succ_next  = from->succ_list;
 576     e->from       = from;
 577
 578     e->pred_next  = to->pred_list;
 579     e->to         = to;
 580
 581     to->pred_list = from->succ_list = e;
 582
 583     /* memory housekeeping */
 584     e->next = NULL;
 585
 586     if (unit->edge_list == NULL)
 587         unit->edge_list = e;
 588     else {
 589         e->next         = unit->edge_list;
 590         unit->edge_list = e;
 591     }
 592 }
 593
 594
 595 /*
 596
 597 =item C<static void bb_remove_edge(IMC_Unit *unit, Edge *edge)>
 598
 599 Removes the given edge from the graph.
 600
 601 =cut
 602
 603 */
 604
 605 static void
 606 bb_remove_edge(ARGMOD(IMC_Unit *unit), ARGMOD(Edge *edge))
 607 {
 608     ASSERT_ARGS(bb_remove_edge)
 609     if (edge->from->succ_list == edge) {
 610         edge->from->succ_list = edge->succ_next;
 611     }
 612     else {
 613         Edge *prev;
 614
 615         for (prev = edge->from->succ_list; prev; prev = prev->succ_next) {
 616             if (prev->succ_next == edge)
 617                 prev->succ_next = edge->succ_next;
 618         }
 619     }
 620
 621     if (edge->to->pred_list == edge) {
 622         edge->to->pred_list = edge->pred_next;
 623     }
 624     else {
 625         Edge *prev;
 626
 627         for (prev = edge->to->pred_list; prev; prev = prev->pred_next) {
 628             if (prev->pred_next == edge)
 629                 prev->pred_next = edge->pred_next;
 630         }
 631     }
 632
 633     if (unit->edge_list == edge) {
 634         unit->edge_list = edge->next;
 635         mem_sys_free(edge);
 636     }
 637     else {
 638         Edge *prev;
 639         for (prev = unit->edge_list; prev; prev = prev->next) {
 640             if (prev->next == edge) {
 641                 prev->next = edge->next;
 642                 mem_sys_free(edge);
 643                 break;
 644             }
 645         }
 646     }
 647 }
 648
 649
 650 /*
 651
 652 =item C<static void free_edge(IMC_Unit *unit)>
 653
 654 Frees the memory of an IMC_Unit's edge list.
 655
 656 =cut
 657
 658 */
 659
 660 static void
 661 free_edge(ARGMOD(IMC_Unit *unit))
 662 {
 663     ASSERT_ARGS(free_edge)
 664     Edge *e;
 665
 666     for (e = unit->edge_list; e;) {
 667         Edge * const next = e->next;
 668         mem_sys_free(e);
 669         e = next;
 670     }
 671
 672     unit->edge_list = NULL;
 673 }
 674
 675
 676 /*
 677
 678 =item C<int edge_count(const IMC_Unit *unit)>
 679
 680 Counts and returns the number of edges in the specified IMC_Unit.
 681
 682 =cut
 683
 684 */
 685
 686 PARROT_WARN_UNUSED_RESULT
 687 int
 688 edge_count(ARGIN(const IMC_Unit *unit))
 689 {
 690     ASSERT_ARGS(edge_count)
 691     Edge *e = unit->edge_list;
 692     int   i = 0;
 693     while (e) {
 694         i++;
 695         e = e->next;
 696     }
 697
 698     return i;
 699 }
 700
 701
 702 /*
 703
 704 =item C<void life_analysis(PARROT_INTERP, const IMC_Unit *unit)>
 705
 706 This driver routine calls analyse_life_symbol for each reglist in the specified
 707 IMC_Unit.
 708
 709 =cut
 710
 711 */
 712
 713 void
 714 life_analysis(PARROT_INTERP, ARGIN(const IMC_Unit *unit))
 715 {
 716     ASSERT_ARGS(life_analysis)
 717     SymReg  ** const reglist = unit->reglist;
 718     unsigned int     i;
 719
 720     IMCC_info(interp, 2, "life_analysis\n");
 721
 722     for (i = 0; i < unit->n_symbols; i++)
 723         analyse_life_symbol(interp, unit, reglist[i]);
 724 }
 725
 726
 727 /*
 728
 729 =item C<static void analyse_life_symbol(PARROT_INTERP, const IMC_Unit *unit,
 730 SymReg* r)>
 731
 732 Analyzes the lifetime for a given symbol.
 733
 734 =cut
 735
 736 */
 737
 738 static void
 739 analyse_life_symbol(PARROT_INTERP,
 740         ARGIN(const IMC_Unit *unit), ARGMOD(SymReg* r))
 741 {
 742     ASSERT_ARGS(analyse_life_symbol)
 743     unsigned int i;
 744
 745 #if IMC_TRACE_HIGH
 746     fprintf(stderr, "cfg.c: analyse_life_symbol(%s)\n", r->name);
 747 #endif
 748
 749     if (r->life_info)
 750         free_life_info(unit, r);
 751
 752     r->life_info = mem_gc_allocate_n_zeroed_typed(interp, unit->n_basic_blocks,
 753                                                Life_range *);
 754
 755     /* First we make a pass to each block to gather the information
 756      * that can be obtained locally */
 757     for (i = 0; i < unit->n_basic_blocks; i++) {
 758         analyse_life_block(interp, unit->bb_list[i], r);
 759     }
 760
 761     /* Now we need to consider the relations between blocks */
 762     for (i = 0; i < unit->n_basic_blocks; i++) {
 763         if (r->life_info[i]->flags & LF_use) {
 764             const Instruction * const ins = unit->bb_list[i]->start;
 765
 766             /* if the previous instruction (the last of the previous block) was
 767              * a sub call, and the symbol is live/use here, it needs allocation
 768              * in the non-volatile register range */
 769             if (ins->prev) {
 770                 const Instruction * const prev = ins->prev;
 771
 772                 if ((prev->type  & (ITPCCSUB|ITPCCYIELD))
 773                 &&   prev->opnum != PARROT_OP_tailcall_p)
 774                     r->usage |= U_NON_VOLATILE;
 775                 else if (prev->opnum == PARROT_OP_invoke_p_p
 776                      ||  prev->opnum == PARROT_OP_invokecc_p)
 777                     r->usage |= U_NON_VOLATILE;
 778                 else if (ins->type & ITADDR)
 779                     r->usage |= U_NON_VOLATILE;
 780             }
 781
 782             /* This block uses r, so it must be live at the beginning */
 783             r->life_info[i]->flags |= LF_lv_in;
 784
 785             /* propagate this info to every predecessor */
 786             propagate_need(unit->bb_list[i], r, i);
 787         }
 788     }
 789 }
 790
 791
 792 /*
 793
 794 =item C<void free_life_info(const IMC_Unit *unit, SymReg *r)>
 795
 796 Frees memory of the life analysis info structures.
 797
 798 =cut
 799
 800 */
 801
 802 void
 803 free_life_info(ARGIN(const IMC_Unit *unit), ARGMOD(SymReg *r))
 804 {
 805     ASSERT_ARGS(free_life_info)
 806 #if IMC_TRACE_HIGH
 807     fprintf(stderr, "free_life_into(%s)\n", r->name);
 808 #endif
 809     if (r->life_info) {
 810         unsigned int i;
 811
 812         for (i = 0; i < unit->n_basic_blocks; i++) {
 813             mem_sys_free(r->life_info[i]);
 814         }
 815
 816         mem_sys_free(r->life_info);
 817         r->life_info = NULL;
 818     }
 819 }
 820
 821
 822 /*
 823
 824 =item C<static void analyse_life_block(PARROT_INTERP, const Basic_block* bb,
 825 SymReg *r)>
 826
 827 Studies the state of the var r in the block bb.
 828
 829 Its job is to set the flags LF_use, or LF_read, and record the intervals inside
 830 the block where the var is alive.
 831
 832 =cut
 833
 834 */
 835
 836 static void
 837 analyse_life_block(PARROT_INTERP, ARGIN(const Basic_block* bb), ARGMOD(SymReg *r))
 838 {
 839     ASSERT_ARGS(analyse_life_block)
 840     Life_range  * const l        = make_life_range(interp, r, bb->index);
 841     Instruction         *special = NULL;
 842     Instruction         *ins;
 843
 844     for (ins = bb->start; ins; ins = ins->next) {
 845         int is_alias;
 846
 847         /* if we have a setp_ind opcode, it may write all PMC registers */
 848         if (ins->opnum == PARROT_OP_setp_ind_i_p && r->set == 'P')
 849             r->usage |= U_NON_VOLATILE;
 850
 851         /* restoreall and such */
 852         if (ins_writes2(ins, r->set))
 853             special = ins;
 854
 855         /*
 856          * set p, p is basically a read - both are LF_use
 857          *
 858          * TODO live range coalescing
 859          */
 860         is_alias = (ins->type & ITALIAS) && ins->symregs[0] == r;
 861
 862         if (instruction_reads(ins, r) || is_alias) {
 863             /* if instruction gets read after a special, consider the first
 864              * read of this instruction, like if a write had happened at
 865              * special, so that the reg doesn't pop into life */
 866             if (! (l->flags & LF_def)) {
 867                 if (special) {
 868                     l->first_ins = special;
 869                     l->flags    |= LF_def;
 870                     special      = NULL;
 871                 }
 872                 else {
 873                     /* we read before having written before, so the var was
 874                      * live at the beginning of the block */
 875                     l->first_ins = bb->start;
 876                     l->flags    |= LF_use;
 877                 }
 878             }
 879
 880             l->last_ins = ins;
 881         }
 882
 883         if (!is_alias && instruction_writes(ins, r)) {
 884             l->flags |= LF_def;
 885
 886             if (!l->first_ins)
 887                 l->first_ins = ins;
 888
 889             l->last_ins = ins;
 890         }
 891
 892         if (ins == bb->end)
 893             break;
 894     }
 895
 896     if (!l->last_ins)
 897         l->last_ins = l->first_ins;
 898
 899     /* l->last can later be extended if it turns out that another block needs
 900      * the value resulting from this computation */
 901 }
 902
 903
 904 /*
 905
 906 =item C<static void propagate_need(Basic_block *bb, const SymReg *r, int i)>
 907
 908 Follows the uses of the given symbol through all of the basic blocks of the
 909 unit.
 910
 911 =cut
 912
 913 */
 914
 915 static void
 916 propagate_need(ARGMOD(Basic_block *bb), ARGIN(const SymReg *r), int i)
 917 {
 918     ASSERT_ARGS(propagate_need)
 919     Edge        *edge;
 920     Life_range  *l;
 921     Basic_block *pred;
 922
 923     /* every predecessor of a LF_lv_in block must be in LF_lv_out
 924      * and, unless itself is LV_def, this should be propagated to its
 925      * predecessors themselves */
 926
 927     for (edge = bb->pred_list; edge; edge = edge->pred_next) {
 928         pred = edge->from;
 929         l    = r->life_info[pred->index];
 930
 931         if (l->flags & LF_lv_out) {
 932             /* this node has already been visited. Ignore it */
 933         }
 934         else {
 935             l->flags   |= LF_lv_out;
 936             l->last_ins = pred->end;
 937
 938             if (! (l->flags & LF_def)) {
 939                 l->flags    |= LF_lv_in;
 940                 l->first_ins = pred->start;
 941                 l->last_ins  = pred->end;
 942
 943                 /* we arrived at block 0
 944                  *
 945                  * emit a warning if -w looking at some Perl 6 examples where
 946                  * this warning is emitted, there seems always to be a code
 947                  * path where the var is not initialized, so this might even be
 948                  * correct :)
 949                  *
 950                  * TT #1244: emit warning in propagate_need()
 951                  */
 952                 propagate_need(pred, r, i);
 953             }
 954         }
 955     }
 956 }
 957
 958
 959 /*
 960
 961 =item C<void compute_dominators(PARROT_INTERP, IMC_Unit *unit)>
 962
 963 Computes the dominators tree of the CFG.  Basic block A dominates B if each
 964 path to B passes through A
 965
 966 See gcc:flow.c compute_dominators
 967
 968 =cut
 969
 970 */
 971
 972 void
 973 compute_dominators(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
 974 {
 975     ASSERT_ARGS(compute_dominators)
 976 #define USE_BFS 0
 977
 978 #if !USE_BFS
 979     int i, change, pred_index;
 980 #else
 981     int i, cur, len, succ_index;
 982     int *q;
 983     Set *visited;
 984 #endif
 985     int b, runner, wrong;
 986     Set **dominators;
 987
 988     const unsigned int n = unit->n_basic_blocks;
 989     IMCC_info(interp, 2, "compute_dominators\n");
 990
 991     unit->idoms          = mem_gc_allocate_n_zeroed_typed(interp, n, int);
 992     dominators           = mem_gc_allocate_n_zeroed_typed(interp, n, Set *);
 993     unit->dominators     = dominators;
 994
 995     dominators[0]        = set_make(interp, n);
 996     set_add(dominators[0], 0);
 997
 998     for (i = n - 1; i; --i) {
 999         if (unit->bb_list[i]->pred_list) {
1000             dominators[i] = set_make_full(interp, n);
1001         }
1002         else {
1003             dominators[i] = set_make(interp, n);
1004             set_add(dominators[i], i);
1005         }
1006     }
1007
1008 #if USE_BFS
1009     q       = calloc(n, sizeof (int));
1010     visited = set_make(n);
1011     set_add(visited, 0);
1012     len     = 1;
1013     cur     = 0;
1014
1015     while (cur < len) {
1016         Edge *edge;
1017         for (edge = unit->bb_list[q[cur]]->succ_list;
1018                 edge; edge = edge->succ_next) {
1019
1020             succ_index = edge->to->index;
1021             set_intersec_inplace(dominators[succ_index], dominators[q[cur]]);
1022             set_add(dominators[succ_index], succ_index);
1023
1024             if (!set_contains(visited, succ_index)) {
1025                 set_add(visited, succ_index);
1026                 q[len++] = succ_index;
1027             }
1028         }
1029         cur++;
1030     }
1031 #else
1032     change = 1;
1033
1034     while (change) {
1035         unsigned int i;
1036         change = 0;
1037
1038         /* TODO: This 'for' should be a breadth-first search for speed */
1039         for (i = 1; i < n; i++) {
1040             Set  * const s = set_copy(interp, dominators[i]);
1041             Edge *edge;
1042
1043             for (edge = unit->bb_list[i]->pred_list;
1044                 edge;
1045                 edge = edge->pred_next) {
1046                 pred_index = edge->from->index;
1047                 set_intersec_inplace(s, dominators[pred_index]);
1048             }
1049
1050             set_add(s, i);
1051
1052             if (! set_equal(dominators[i], s)) {
1053                 change = 1;
1054                 set_free(dominators[i]);
1055                 dominators[i] = s;
1056             }
1057             else
1058                 set_free(s);
1059         }
1060     }
1061 #endif
1062
1063     /* calc idoms */
1064     unit->idoms[0] = unit->bb_list[0]->index;
1065
1066     for (b = n - 1; b; --b) {
1067         unit->idoms[b] = 0;
1068         for (i = n - 1; i > 0; i--) {
1069             if (i != b && set_contains(dominators[b], i)) {
1070                 wrong = 0;
1071                 for (runner = n - 1; runner >= 0; --runner) {
1072                     if (runner != b && runner != i
1073                     &&  set_contains(dominators[b], runner))
1074                     {
1075                         if (set_contains(dominators[runner], i)) {
1076                             wrong = 1;
1077                             break;
1078                         }
1079                     }
1080                 }
1081
1082                 if (!wrong) {
1083                     unit->idoms[b] = unit->bb_list[i]->index;
1084                     break;
1085                 }
1086
1087             }
1088        }
1089    }
1090
1091     if (IMCC_INFO(interp)->debug & DEBUG_CFG)
1092         dump_dominators(unit);
1093 #if USE_BFS
1094     mem_sys_free(q);
1095     set_free(visited);
1096 #endif
1097 }
1098
1099
1100 /*
1101
1102 =item C<void compute_dominance_frontiers(PARROT_INTERP, IMC_Unit *unit)>
1103
1104 Algorithm to find dominance frontiers described in paper "A Simple, Fast
1105 Dominance Algorithm", Cooper et al. (2001)
1106
1107 =cut
1108
1109 */
1110
1111 void
1112 compute_dominance_frontiers(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
1113 {
1114     ASSERT_ARGS(compute_dominance_frontiers)
1115     int i, b;
1116
1117     const int    n                   = unit->n_basic_blocks;
1118     Set ** const dominance_frontiers = unit->dominance_frontiers =
1119             mem_gc_allocate_n_typed(interp, n, Set *);
1120
1121     IMCC_info(interp, 2, "compute_dominance_frontiers\n");
1122
1123     for (i = 0; i < n; i++) {
1124         dominance_frontiers[i] = set_make(interp, n);
1125     }
1126
1127     /* for all nodes, b */
1128     for (b = 1; b < n; b++) {
1129         const Edge *edge = unit->bb_list[b]->pred_list;
1130
1131         /* if the number of predecessors of b >= 2 */
1132         if (edge && edge->pred_next) {
1133
1134             /* for all predecessors, p, of b */
1135             for (; edge; edge = edge->pred_next) {
1136                 /* runner = p */
1137                 int runner = edge->from->index;
1138
1139                 /* while runner != idoms[b] */
1140                 while (runner >= 0 && runner != unit->idoms[b]) {
1141                     if (set_contains(unit->dominance_frontiers[runner], b))
1142                         /* we've already gone down this path once before */
1143                         runner = 0;
1144                     else
1145                         /* add b to runner's dominance frontier set */
1146                         set_add(unit->dominance_frontiers[runner], b);
1147
1148                     /* runner = idoms[runner] */
1149                     if (runner == 0)
1150                         runner = -1;
1151                     else
1152                         runner = unit->idoms[runner];
1153                 }
1154             }
1155         }
1156     }
1157
1158     if (IMCC_INFO(interp)->debug & DEBUG_CFG)
1159         dump_dominance_frontiers(unit);
1160 }
1161
1162
1163 /*
1164
1165 =item C<static void free_dominators(IMC_Unit *unit)>
1166
1167 Frees the memory in the given unit related to all dominators.
1168
1169 =cut
1170
1171 */
1172
1173 static void
1174 free_dominators(ARGMOD(IMC_Unit *unit))
1175 {
1176     ASSERT_ARGS(free_dominators)
1177     if (unit->dominators) {
1178         unsigned int i;
1179
1180         for (i = 0; i < unit->n_basic_blocks; i++) {
1181             set_free(unit->dominators[i]);
1182         }
1183
1184         mem_sys_free(unit->dominators);
1185         unit->dominators = NULL;
1186         mem_sys_free(unit->idoms);
1187     }
1188 }
1189
1190
1191 /*
1192
1193 =item C<static void free_dominance_frontiers(IMC_Unit *unit)>
1194
1195 Frees the memory in the given unit related to all dominance frontiers.
1196
1197 =cut
1198
1199 */
1200
1201 static void
1202 free_dominance_frontiers(ARGMOD(IMC_Unit *unit))
1203 {
1204     ASSERT_ARGS(free_dominance_frontiers)
1205     if (unit->dominance_frontiers) {
1206         unsigned int i;
1207
1208         for (i = 0; i < unit->n_basic_blocks; i++) {
1209             set_free(unit->dominance_frontiers[i]);
1210         }
1211
1212         mem_sys_free(unit->dominance_frontiers);
1213         unit->dominance_frontiers = NULL;
1214     }
1215 }
1216
1217
1218 /*
1219
1220 =item C<static void sort_loops(PARROT_INTERP, IMC_Unit *unit)>
1221
1222 Sorts the loops found in the CFG of the current unit.
1223
1224 =cut
1225
1226 */
1227
1228 static void
1229 sort_loops(PARROT_INTERP, ARGIN(IMC_Unit *unit))
1230 {
1231     ASSERT_ARGS(sort_loops)
1232
1233     Loop_info   *li;
1234     Loop_info  **loop_info = unit->loop_info;
1235     int          n_loops   = (int)unit->n_loops;
1236     int          i, k, changed;
1237     unsigned int j;
1238
1239     for (i = 0; i < n_loops; i++) {
1240         loop_info[i]->size = 0;
1241
1242         for (j = 0; j < unit->n_basic_blocks; j++)
1243             if (set_contains(loop_info[i]->loop, j))
1244                 loop_info[i]->size++;
1245     }
1246
1247     changed = 1;
1248
1249     while (changed) {
1250         changed = 0;
1251
1252         for (i = 0; n_loops && i < n_loops - 1; i++)
1253             if (loop_info[i]->size < loop_info[i + 1]->size) {
1254                 li             = loop_info[i];
1255                 loop_info[i]   = loop_info[i + 1];
1256                 loop_info[i+1] = li;
1257                 changed        = 1;
1258             }
1259     }
1260
1261     /* set depth was incorrect until now, as it depended on the order of
1262      * finding loops */
1263     for (i = 0; n_loops && i < n_loops - 1; i++) {
1264         int first           = -1;
1265         int last            = 0;
1266         loop_info[i]->depth = 1;
1267
1268         /* we could also take the depth of the first contained block, but below
1269          * is a check, that a inner loop is fully contained in a outer loop */
1270         for (j = 0; j < unit->n_basic_blocks; j++)
1271             if (set_contains(loop_info[i+1]->loop, j)) {
1272                 if (first < 0)
1273                     first = j;
1274                 last = j;
1275             }
1276
1277         for (k = i + 1; k < n_loops; k++) {
1278             if (set_contains(loop_info[i]->loop, first)
1279             && !set_contains(loop_info[i]->loop, last)) {
1280                 IMCC_debug(interp, DEBUG_CFG, "sort_loops",
1281                         "loop %d contains first but not"
1282                         "last of outer loop %d\n", k, i);
1283             }
1284
1285             if (set_contains(loop_info[i]->loop, last)
1286             && !set_contains(loop_info[i]->loop, first)) {
1287                 IMCC_debug(interp, DEBUG_CFG, "sort_loops",
1288                         "loop %d contains last but not"
1289                         "first of outer loop %d\n", k, i);
1290             }
1291
1292             loop_info[k]->depth = loop_info[i]->depth + 1;
1293         }
1294     }
1295 }
1296
1297
1298 /*
1299
1300 =item C<void find_loops(PARROT_INTERP, IMC_Unit *unit)>
1301
1302 Searches for loops in the CFG. We search for edges that go from a node to one
1303 of its dominators.
1304
1305 =cut
1306
1307 */
1308
1309 void
1310 find_loops(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
1311 {
1312     ASSERT_ARGS(find_loops)
1313     unsigned int i;
1314
1315     IMCC_info(interp, 2, "find_loops\n");
1316
1317     for (i = 0; i < unit->n_basic_blocks; i++) {
1318         const Set * const dom = unit->dominators[i];
1319         const Edge       *edge;
1320
1321         for (edge = unit->bb_list[i]->succ_list; edge; edge = edge->succ_next) {
1322             if (set_contains(dom, edge->to->index))
1323                 mark_loop(interp, unit, edge);
1324         }
1325     }
1326
1327     sort_loops(interp, unit);
1328     if (IMCC_INFO(interp)->debug & DEBUG_CFG)
1329         dump_loops(unit);
1330 }
1331
1332
1333 /*
1334
1335 =item C<int natural_preheader(const IMC_Unit *unit, const Loop_info *loop_info)>
1336
1337 For loop_info, finds the natural preheader of the loop, if any, and returns its
1338 index, otherwise returns -1.  A natural preheader exists if there is only one
1339 predecessor to the loop header outside of the loop body, and if it always
1340 transfers control directly to the header.
1341
1342 =cut
1343
1344 */
1345
1346 PARROT_WARN_UNUSED_RESULT
1347 int
1348 natural_preheader(ARGIN(const IMC_Unit *unit), ARGIN(const Loop_info *loop_info))
1349 {
1350     ASSERT_ARGS(natural_preheader)
1351     Edge *edge;
1352     int   preheader = -1;
1353
1354     for (edge = unit->bb_list[loop_info->header]->pred_list;
1355          edge;
1356          edge = edge->pred_next) {
1357         if (!set_contains(loop_info->loop, edge->from->index)) {
1358             if (preheader == -1
1359             &&  unit->bb_list[edge->from->index]->succ_list->to->index
1360                 == loop_info->header
1361             && !unit->bb_list[edge->from->index]->succ_list->succ_next)
1362             {
1363                 preheader = unit->bb_list[edge->from->index]->index;
1364                 continue;
1365             }
1366             else {
1367                 return -1;
1368             }
1369         }
1370     }
1371
1372     return preheader;
1373 }
1374
1375
1376 /*
1377
1378 =item C<static void mark_loop(PARROT_INTERP, IMC_Unit *unit, const Edge *e)>
1379
1380 Increases the loop_depth of all the nodes in a loop.
1381
1382 =cut
1383
1384 */
1385
1386 static void
1387 mark_loop(PARROT_INTERP, ARGMOD(IMC_Unit *unit), ARGIN(const Edge *e))
1388 {
1389     ASSERT_ARGS(mark_loop)
1390     Set         *loop;
1391     Set         *exits;
1392     Edge        *edge;
1393     Loop_info  **loop_info;
1394     Basic_block *header = e->to;
1395     Basic_block *footer = e->from;
1396     Basic_block *enter  = 0;
1397
1398     unsigned int i;
1399     int n_loops;
1400
1401     /* look from where loop was entered */
1402     for (i = 0, edge=header->pred_list; edge; edge=edge->pred_next)
1403         if (footer != edge->from) {
1404             enter = edge->from;
1405             i++;
1406         }
1407
1408     IMCC_debug(interp, DEBUG_CFG, "loop from %d to %d, entered from %d\n",
1409             footer->index, header->index, enter ? (int)enter->index : -1);
1410
1411     if (i == 0) {
1412         if (header->index)
1413             IMCC_debug(interp, DEBUG_CFG, "\tdead code\n");
1414         else
1415             IMCC_debug(interp, DEBUG_CFG, "\tsub start\n");
1416     }
1417     else if (i != 1) {
1418         IMCC_debug(interp, DEBUG_CFG,
1419                 "\tcan't determine loop entry block (%d found)\n" , i);
1420     }
1421
1422     loop = set_make(interp, unit->n_basic_blocks);
1423     set_add(loop, footer->index);
1424     set_add(loop, header->index);
1425
1426     footer->loop_depth++;
1427
1428     if (header != footer) {
1429         header->loop_depth++;
1430         search_predecessors_not_in(footer, loop);
1431     }
1432
1433     exits = set_make(interp, unit->n_basic_blocks);
1434
1435     for (i = 1; i < unit->n_basic_blocks; i++) {
1436         if (set_contains(loop, i)) {
1437             for (edge = unit->bb_list[i]->succ_list;
1438                  edge;
1439                  edge = edge->succ_next)
1440             {
1441                 if (!set_contains(loop, edge->to->index))
1442                     set_add(exits, i);
1443             }
1444         }
1445     }
1446
1447     /* now 'loop' contains the set of nodes inside the loop.  */
1448     n_loops                       = unit->n_loops;
1449     loop_info                     = mem_gc_realloc_n_typed(interp,
1450                                             unit->loop_info,
1451                                             n_loops + 1, Loop_info *);
1452     loop_info[n_loops]            = mem_gc_allocate_typed(interp, Loop_info);
1453     loop_info[n_loops]->loop      = loop;
1454     loop_info[n_loops]->exits     = exits;
1455     loop_info[n_loops]->depth     = footer->loop_depth;
1456     loop_info[n_loops]->n_entries = i;
1457     loop_info[n_loops]->header    = header->index;
1458     loop_info[n_loops]->preheader = natural_preheader(unit, loop_info[n_loops]);
1459
1460     unit->loop_info = loop_info;
1461
1462     unit->n_loops++;
1463 }
1464
1465
1466 /*
1467
1468 =item C<static void free_loops(IMC_Unit *unit)>
1469
1470 Frees the memory associated with the loops in this unit.
1471
1472 =cut
1473
1474 */
1475
1476 static void
1477 free_loops(ARGMOD(IMC_Unit *unit))
1478 {
1479     ASSERT_ARGS(free_loops)
1480     int i;
1481
1482     for (i = 0; i < unit->n_loops; i++) {
1483         set_free(unit->loop_info[i]->loop);
1484         set_free(unit->loop_info[i]->exits);
1485         mem_sys_free(unit->loop_info[i]);
1486     }
1487
1488     mem_sys_free(unit->loop_info);
1489
1490     unit->n_loops   = 0;
1491     unit->loop_info = NULL;
1492 }
1493
1494
1495 /*
1496
1497 =item C<void search_predecessors_not_in(const Basic_block *node, Set *s)>
1498
1499 Searches for predecessor edges for this node not in the given set (and adds
1500 them).
1501
1502 =cut
1503
1504 */
1505
1506 void
1507 search_predecessors_not_in(ARGIN(const Basic_block *node), ARGMOD(Set *s))
1508 {
1509     ASSERT_ARGS(search_predecessors_not_in)
1510     Edge *edge;
1511
1512     for (edge = node->pred_list; edge; edge = edge->pred_next) {
1513         Basic_block * const pred = edge->from;
1514
1515         if (!set_contains(s, pred->index)) {
1516            set_add(s, pred->index);
1517            pred->loop_depth++;
1518            search_predecessors_not_in(pred, s);
1519         }
1520     }
1521 }
1522
1523 /*** Utility functions ***/
1524
1525 /*
1526
1527 =item C<static void init_basic_blocks(PARROT_INTERP, IMC_Unit *unit)>
1528
1529 Initializes the basic blocks memory for this unit.
1530
1531 =cut
1532
1533 */
1534
1535 static void
1536 init_basic_blocks(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
1537 {
1538     ASSERT_ARGS(init_basic_blocks)
1539
1540     if (!unit->bb_list)
1541         clear_basic_blocks(unit);
1542
1543     unit->n_basic_blocks = 0;
1544     unit->edge_list      = NULL;
1545     unit->bb_list_size   = 256;
1546     unit->bb_list        = mem_gc_allocate_n_zeroed_typed(interp,
1547                                     unit->bb_list_size, Basic_block *);
1548 }
1549
1550
1551 /*
1552
1553 =item C<void clear_basic_blocks(IMC_Unit *unit)>
1554
1555 Frees all of the blocks and CFG memory allocated for this unit.
1556
1557 =cut
1558
1559 */
1560
1561 void
1562 clear_basic_blocks(ARGMOD(IMC_Unit *unit))
1563 {
1564     ASSERT_ARGS(clear_basic_blocks)
1565
1566     if (unit->bb_list) {
1567         unsigned int i;
1568
1569         for (i = 0; i < unit->n_basic_blocks; i++)
1570             mem_sys_free(unit->bb_list[i]);
1571
1572         mem_sys_free(unit->bb_list);
1573         unit->bb_list = NULL;
1574     }
1575
1576     free_edge(unit);
1577     free_dominators(unit);
1578     free_dominance_frontiers(unit);
1579     free_loops(unit);
1580 }
1581
1582
1583 /*
1584
1585 =item C<static Basic_block* make_basic_block(PARROT_INTERP, IMC_Unit *unit,
1586 Instruction *ins)>
1587
1588 Creates, initializes, and returns a new Basic_block.
1589
1590 =cut
1591
1592 */
1593
1594 PARROT_CANNOT_RETURN_NULL
1595 PARROT_WARN_UNUSED_RESULT
1596 static Basic_block*
1597 make_basic_block(PARROT_INTERP, ARGMOD(IMC_Unit *unit), ARGMOD(Instruction *ins))
1598 {
1599     ASSERT_ARGS(make_basic_block)
1600     Basic_block * const bb = mem_gc_allocate_typed(interp, Basic_block);
1601     int                 n  = unit->n_basic_blocks;
1602
1603     bb->start      = ins;
1604     bb->end        = ins;
1605
1606     bb->pred_list  = NULL;
1607     bb->succ_list  = NULL;
1608
1609     ins->bbindex   = n;
1610     bb->index      = n;
1611     bb->loop_depth = 0;
1612
1613     if (n == unit->bb_list_size) {
1614         unit->bb_list_size *= 2;
1615         unit->bb_list = mem_gc_realloc_n_typed(interp, unit->bb_list,
1616                     unit->bb_list_size, Basic_block *);
1617     }
1618
1619     unit->bb_list[n] = bb;
1620     unit->n_basic_blocks++;
1621
1622     return bb;
1623 }
1624
1625
1626 /*
1627
1628 =item C<Life_range * make_life_range(PARROT_INTERP, SymReg *r, int idx)>
1629
1630 Creates and returns a Life_range for the given register at the specified index.
1631
1632 =cut
1633
1634 */
1635
1636 PARROT_MALLOC
1637 PARROT_CANNOT_RETURN_NULL
1638 Life_range *
1639 make_life_range(PARROT_INTERP, ARGMOD(SymReg *r), int idx)
1640 {
1641     ASSERT_ARGS(make_life_range)
1642     Life_range * const l = mem_gc_allocate_zeroed_typed(interp, Life_range);
1643     r->life_info[idx]    = l;
1644
1645     return l;
1646 }
1647
1648 /*
1649
1650 =back
1651
1652 =cut
1653
1654 */
1655
1656 /*
1657  * Local variables:
1658  *   c-file-style: "parrot"
1659  * End:
1660  * vim: expandtab shiftwidth=4:
1661  */