nsz Git - libfirm/blob - ir/opt/loop.c

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @author   Christian Helmer
  23  * @brief    loop inversion and loop unrolling
  24  *
  25  * @version  $Id$
  26  */
  27
  28 #include "config.h"
  29
  30 #include "iroptimize.h"
  31 #include "opt_init.h"
  32 #include "irnode.h"
  33 #include "debug.h"
  34
  35
  36 #include "ircons.h"
  37 #include "irgopt.h"
  38 #include "irgmod.h"
  39 #include "irgwalk.h"
  40 #include "irouts.h"
  41 #include "iredges.h"
  42 #include "irtools.h"
  43 #include "array_t.h"
  44 #include "beutil.h"
  45 #include "irpass.h"
  46 #include "irdom.h"
  47
  48 #include "irbackedge_t.h"
  49 #include "irphase_t.h"
  50 #include "irloop_t.h"
  51
  52
  53 DEBUG_ONLY(static firm_dbg_module_t *dbg);
  54
  55 /**
  56  * Convenience macro for iterating over every phi node of the given block.
  57  * Requires phi list per block.
  58  */
  59 #define for_each_phi(block, phi) \
  60         for ((phi) = get_Block_phis( (block) ); (phi) ; (phi) = get_Phi_next((phi)))
  61
  62 #define for_each_phi_safe(head, phi, next) \
  63         for ((phi) = (head), (next) = (head) ? get_Phi_next((head)) : NULL; \
  64                         (phi) ; (phi) = (next), (next) = (next) ? get_Phi_next((next)) : NULL)
  65
  66 /* currently processed loop */
  67 static ir_loop *cur_loop;
  68
  69 /* Condition for performing copy_walk. */
  70 typedef unsigned walker_condition(ir_node *);
  71
  72 /* Node and position of a predecessor */
  73 typedef struct out_edge {
  74         ir_node *node;
  75         int pos;
  76         ir_node *pred;
  77 } out_edge;
  78
  79 /**/
  80 typedef struct inversion_node_info {
  81         ir_node *copy;
  82         ir_node **ins;
  83         struct inversion_node_info *free_list_next;     /* linked list to free all node_infos */
  84 } inversion_node_info;
  85
  86 /*   */
  87 typedef struct node_info {
  88         ir_node **copy;
  89         ir_node **ins;
  90         struct ir_node *free_list_next;         /* linked list to free all node_infos */
  91 } node_info;
  92
  93 /* Head of the list for freeing node_infos */
  94 static ir_node *free_list;
  95
  96 /* A walker may start visiting the current loop with these nodes. */
  97 static out_edge *cur_loop_outs;
  98
  99 /* Outs of the nodes head. */
 100 static out_edge *cur_head_outs;
 101
 102 /* Information about the loop head */
 103 static ir_node *loop_head = NULL;
 104 static unsigned loop_head_valid = 1;
 105
 106 /* List of all inner loops, that are processed. */
 107 static ir_loop **loops;
 108
 109 /* Inverted head */
 110 static ir_node *loop_inv_head = NULL;
 111 /* Peeled head */
 112 static ir_node *loop_peeled_head = NULL;
 113
 114 /* Loop analysis informations */
 115 typedef struct loop_info_t {
 116         unsigned blocks;                        /* number of blocks in the loop */
 117         unsigned calls;                         /* number of calls */
 118         unsigned cf_outs;
 119         out_edge cf_out;
 120         ir_node *new_loop_head;
 121 } loop_info_t;
 122
 123 /* Information about the current loop */
 124 static loop_info_t loop_info;
 125
 126 /* Outs of the condition chain (loop inversion). */
 127 static out_edge *cond_chain_entries;
 128
 129 /* Arity of the unrolled loop heads. */
 130 static int unroll_arity;
 131
 132 static ir_phase *phase;
 133
 134
 135
 136 /*  */
 137 static unsigned head_inversion_node_count;
 138 static unsigned inversion_head_node_limit;
 139 static unsigned head_inversion_block_count;
 140
 141 /* As the preconditions are the same, these flags,
 142  * set depending on which function called, are used to determine what to do. */
 143 static unsigned enable_peeling;
 144 static unsigned enable_inversion;
 145 static unsigned enable_unrolling;
 146
 147
 148 /* Creates node_info. A linked list keeps all node_infos to free them again. */
 149 static node_info *new_node_info(ir_node *node)
 150 {
 151         node_info *l = XMALLOCZ(node_info);
 152         l->free_list_next = free_list;
 153         free_list = node;
 154         l->copy = NULL;
 155         return l;
 156 }
 157
 158 /* Returns linked node_info for given node. */
 159 static node_info *get_node_info(ir_node *n)
 160 {
 161         return ((node_info *)get_irn_link(n));
 162 }
 163
 164 /* Allocates a node_info struct for the given node */
 165 static void alloc_node_info(ir_node *node)
 166 {
 167         node_info *state;
 168         state = new_node_info(node);
 169         set_irn_link(node, (void *)state);
 170 }
 171
 172 /* Frees node info and copy array for given node. Returns next node of free_list. */
 173 static ir_node *free_info(ir_node *node)
 174 {
 175         node_info *info = get_node_info(node);
 176         ir_node *next = info->free_list_next;
 177         /*DB((dbg, LEVEL_1, "FREE %N\n", node));*/
 178         DEL_ARR_F(info->copy);
 179         xfree(info);
 180         set_irn_link(node, NULL);
 181         return next;
 182 }
 183
 184 /* Free all created node_infos, including the copy arrays. */
 185 static void free_node_info(void)
 186 {
 187         ir_node *node = free_list;
 188         while (node) {
 189                 node = free_info(node);
 190         }
 191         free_list = NULL;
 192 }
 193
 194 /* Free node_infos of blocks only, including the copy arrays. */
 195 static void free_node_info_blocks(void)
 196 {
 197         ir_node *node = free_list;
 198         ir_node *new_freelist = NULL;
 199         while (node) {
 200                 ir_node *next;
 201                 if (is_Block(node)) {
 202                         next = free_info(node);
 203                 } else {
 204                         next = get_node_info(node)->free_list_next;
 205                         get_node_info(node)->free_list_next = new_freelist;
 206                         new_freelist = node;
 207                 }
 208                 node = next;
 209         }
 210         free_list = new_freelist;
 211 }
 212
 213 /* Reset nodes link. For use with a walker. */
 214 static void reset_link(ir_node *node, void *env)
 215 {
 216         (void)env;
 217         set_irn_link(node, NULL);
 218 }
 219
 220 static void set_inversion_copy(ir_node *n, ir_node *cp)
 221 {
 222         phase_set_irn_data(phase, n, cp);
 223 }
 224
 225 /* Returns a nodes copy. */
 226 static ir_node *get_copy(ir_node *n, int index)
 227 {
 228         ir_node *cp = ((node_info *)get_irn_link(n))->copy[index];
 229         return cp;
 230 }
 231
 232 /* Returns a nodes copy if it exists, or else the node. */
 233 static ir_node *get_inversion_copy(ir_node *n)
 234 {
 235         ir_node *cp = (ir_node *)phase_get_irn_data(phase, n);
 236         return cp;
 237 }
 238
 239 /* Returns a nodes copy, or node if there is no node info linked. */
 240 static ir_node *get_copy_safe(ir_node *node, int index)
 241 {
 242         node_info *info = (node_info *)get_irn_link(node);
 243         if (info != NULL)
 244                 return get_copy(node, index);
 245         else
 246                 return node;
 247 }
 248
 249 /* Assigns the given array to a nodes node_info */
 250 static void set_copy_arr(ir_node *n, ir_node **arr)
 251 {
 252         ((node_info *)get_irn_link(n))->copy = arr;
 253 }
 254
 255 /* Assigns a copy with given index to a node.
 256  * Prerequirements are existing node_info and copy array. */
 257 static void set_copy(ir_node *n, int index, ir_node *copy)
 258 {
 259         ((node_info *)get_irn_link(n))->copy[index] = copy;
 260 }
 261
 262 /* Returns 0 if the node or block is not in cur_loop. */
 263 static unsigned is_in_loop(ir_node *node)
 264 {
 265         return (get_irn_loop(get_block(node)) == cur_loop);
 266 }
 267
 268 /* Returns if the given be is an alien edge.
 269  * This is the case when the pred is not in the loop. */
 270 static unsigned is_alien_edge(ir_node *n, int i)
 271 {
 272         return(!is_in_loop(get_irn_n(n, i)));
 273 }
 274
 275 static unsigned is_own_backedge(ir_node *n, int pos)
 276 {
 277         return (is_backedge(n, pos) && is_in_loop(get_irn_n(n, pos)));
 278 }
 279
 280 /* Resets block mark for given node. For use with walker */
 281 static void reset_block_mark(ir_node *node, void * env)
 282 {
 283         (void) env;
 284
 285         if (is_Block(node))
 286                 set_Block_mark(node, 0);
 287 }
 288
 289 static unsigned is_nodes_block_marked(ir_node* node)
 290 {
 291         if (is_Block(node))
 292                 return get_Block_mark(node);
 293         else
 294                 return get_Block_mark(get_block(node));
 295 }
 296
 297 /* Returns the number of blocks in a loop. */
 298 static int get_loop_n_blocks(ir_loop *loop)
 299 {
 300         int elements, e;
 301         int blocks = 0;
 302         elements = get_loop_n_elements(loop);
 303
 304         for (e=0; e<elements; e++) {
 305                 loop_element elem = get_loop_element(loop, e);
 306                 if (is_ir_node(elem.kind) && is_Block(elem.node))
 307                         ++blocks;
 308         }
 309         return blocks;
 310 }
 311
 312 /**/
 313 static int extend_irn(ir_node *n, ir_node *new)
 314 {
 315         ir_node **ins;
 316         int i;
 317         int arity = get_irn_arity(n);
 318         int new_arity = arity + 1;
 319
 320         NEW_ARR_A(ir_node *, ins, new_arity);
 321
 322         for(i = 0; i < arity; ++i) {
 323                 ins[i] = get_irn_n(n, i);
 324         }
 325         ins[i] = new;
 326
 327         set_irn_in(n, new_arity, ins);
 328         /* arity equals the position of the new node */
 329         return arity;
 330 }
 331
 332 /* */
 333 static void extend_ins_by_copy(ir_node *block, int pos)
 334 {
 335         ir_node *new_in;
 336         ir_node *phi;
 337         assert(is_Block(block));
 338
 339         /* Extend block by copy of definition at pos */
 340         new_in = get_inversion_copy(get_irn_n(block, pos));
 341         extend_irn(block, new_in);
 342
 343         /* Extend block phis by copy of definition at pos */
 344         for_each_phi(block, phi) {
 345                 ir_node *pred, *cp;
 346
 347                 pred = get_irn_n(phi, pos);
 348                 cp = get_inversion_copy(pred);
 349                 /* If the phis in is not in the condition chain (eg. a constant),
 350                  * there is no copy. */
 351                 if (cp == NULL)
 352                         new_in = pred;
 353                 else
 354                         new_in = cp;
 355
 356                 DB((dbg, LEVEL_5, "Extend phi %N by %N\n", phi, new_in));
 357                 extend_irn(phi, new_in);
 358         }
 359 }
 360
 361 /*
 362  * Extends all blocks which succeed the loop with the copied loops outs.
 363  * Also extends the blocks phis. Requires block phi list.
 364  * Returns an updated list of loop outs of the original loop outs.
 365  */
 366 static out_edge *extend_ins(out_edge *outs, int copies)
 367 {
 368         ir_node **ins;
 369         ir_node **phi_ins;
 370         int *bes, *phi_bes;
 371         ir_node *phi, *next_phi, *new_phi, *head, *new_block;
 372         int old_arity, new_arity;
 373         int i, c, p;
 374         out_edge *new_outs;
 375
 376         inc_irg_visited(current_ir_graph);
 377
 378         new_outs = NEW_ARR_F(out_edge, 0);
 379
 380 #if 0
 381         for (i = 0; i < ARR_LEN(outs); ++i) {
 382                 out_edge edge = outs[i];
 383                 ir_node *node = edge.node;
 384                 DB((dbg, LEVEL_5, "outs %N %d\n", node, edge.pos));
 385         }
 386 #endif
 387
 388         for (i = 0; i < ARR_LEN(outs); ++i) {
 389                 out_edge edge = outs[i];
 390                 ir_node *node = edge.node;
 391                 int in_c, positions_n;
 392                 int *positions;
 393
 394                 if (!is_Block(node) && !is_Bad(node)) {
 395 #if 0
 396                         if (is_Phi(node)) {
 397                                 int c;
 398                                 unsigned b = 0;
 399                                 ir_node *p = get_nodes_block(node);
 400                                 for(c = 0; c < get_irn_arity(p); ++c) {
 401                                         if (is_in_loop(get_irn_n(p, c))) {
 402                                                 b=1;
 403                                                 break;
 404                                         }
 405                                 }
 406                                 if (!b) {
 407                                         ARR_APP1(out_edge, new_outs, edge);
 408                                         DB((dbg, LEVEL_5, "new out %N\n", node));
 409                                 }
 410
 411                         } else {
 412 #endif
 413                         ARR_APP1(out_edge, new_outs, edge);
 414                         DB((dbg, LEVEL_5, "new out %N\n", node));
 415
 416                 }
 417
 418                 /* CONTINUE if node already processed. */
 419                 if (irn_visited(node))
 420                         continue;
 421
 422                 if (!is_Block(node))
 423                         continue;
 424
 425                 positions = NEW_ARR_F(int, 0);
 426                 positions_n = 0;
 427
 428                 /* Search for all occurences of the current node, and save the in positions. */
 429                 for (p = 0; p < ARR_LEN(outs); ++p) {
 430                         ir_node *cur = outs[p].node;
 431                         int d_pos = outs[p].pos;
 432
 433                         if (node==cur) {
 434                                 DB((dbg, LEVEL_5, "Loop successor %N with pred @%d in loop\n",
 435                                                         node, d_pos));
 436                                 ARR_APP1(int, positions, d_pos);
 437                                 mark_irn_visited(cur);
 438                                 ++positions_n;
 439                         }
 440                 }
 441
 442                 old_arity = get_irn_arity(node);
 443                 new_arity = old_arity + (positions_n * copies);
 444
 445                 ins = NEW_ARR_F(ir_node*, new_arity);
 446                 bes = NEW_ARR_F(int, new_arity);
 447
 448                 /* extend block ins */
 449                 for (in_c = 0; in_c < old_arity; ++in_c) {
 450                         ins[in_c] = get_irn_n(node, in_c);
 451                         bes[in_c] = is_backedge(node, in_c);
 452                 }
 453                 for (p = 0; p < positions_n; ++p) {
 454                         for (c = 0; c < copies; ++c) {
 455                                 ir_node *cp = get_copy_safe(get_irn_n(node, positions[p]), c);
 456                                 DB((dbg, LEVEL_5, "%N (new_arity %d) @%d = %N\n",
 457                                                         node, new_arity, in_c, cp));
 458                                 ins[in_c] = cp;
 459                                 bes[in_c] = is_backedge(node, positions[p]);
 460                                 ++in_c;
 461                         }
 462                 }
 463
 464                 assert(new_arity == in_c);
 465
 466                 head = get_Block_phis(node);
 467                 new_block = new_r_Block(get_irn_irg(node), new_arity, ins);
 468                 set_irn_loop(new_block, get_irn_loop(node));
 469
 470                 for (in_c = 0; in_c < new_arity; ++in_c) {
 471                         if (bes[in_c])
 472                                 set_backedge(new_block, in_c);
 473                 }
 474                 DEL_ARR_F(ins);
 475                 DEL_ARR_F(bes);
 476
 477 #if 1
 478                 set_Block_phis(node, NULL);
 479
 480                 phi_ins = NEW_ARR_F(ir_node *, new_arity);
 481                 phi_bes = NEW_ARR_F(int, new_arity);
 482
 483                 for_each_phi_safe(head, phi, next_phi) {
 484                         for (in_c = 0; in_c < old_arity; ++in_c) {
 485                                 phi_ins[in_c] = get_irn_n(phi, in_c);
 486                                 phi_bes[in_c] = is_backedge(phi, in_c);
 487                         }
 488
 489                         for (p = 0; p < positions_n; ++p) {
 490                                 for(c = 0; c < copies; ++c) {
 491                                         ir_node *cp, *pred;
 492                                         pred = get_irn_n(phi, positions[p]);
 493                                         DB((dbg, LEVEL_5, "Phi %N pred @%d is %N\n",
 494                                                                 phi, positions[p], pred));
 495                                         cp = get_copy_safe(pred, c);
 496                                         phi_ins[in_c] = cp;
 497                                         DB((dbg, LEVEL_5, "Phi %N in %d is %N\n",
 498                                                                 phi, in_c, cp));
 499                                         phi_bes[in_c] = is_backedge(phi, positions[p]);
 500                                         ++in_c;
 501                                 }
 502                         }
 503
 504                         new_phi = new_r_Phi(new_block, new_arity, phi_ins, get_irn_mode(phi));
 505
 506                         for (in_c = 0; in_c < new_arity; ++in_c) {
 507                                 if (phi_bes[in_c])
 508                                         set_backedge(new_phi, in_c);
 509                         }
 510                         exchange(phi, new_phi);
 511                         DB((dbg, LEVEL_5, "exch Phi %N  %N\n",phi, new_phi));
 512
 513                         add_Block_phi(new_block, new_phi);
 514                 }
 515
 516                 DEL_ARR_F(phi_ins);
 517                 DEL_ARR_F(phi_bes);
 518 #endif
 519                 exchange(node, new_block);
 520                 set_Block_MacroBlock(new_block, new_block);
 521                 DB((dbg, LEVEL_5, "exch block %N  %N\n", node, new_block));
 522
 523                 DEL_ARR_F(positions);
 524         }
 525         return new_outs;
 526 }
 527
 528 /**
 529  * Finds loop head and loop_info.
 530  */
 531 static void get_loop_info(ir_node *node, void *env)
 532 {
 533         unsigned node_in_loop, pred_in_loop;
 534         int i, arity;
 535         (void)env;
 536
 537         arity = get_irn_arity(node);
 538         for (i = 0; i < arity; i++) {
 539                 ir_node *pred = get_irn_n(node, i);
 540
 541                 pred_in_loop = is_in_loop(pred);
 542                 node_in_loop = is_in_loop(node);
 543
 544                 /* collect some loop information */
 545                 if (node_in_loop) {
 546                         if (is_Call(node))
 547                                 ++loop_info.calls;
 548                 }
 549
 550                 /* Find the loops head/the blocks with cfpred outside of the loop */
 551                 if (is_Block(node) && node_in_loop && !pred_in_loop && loop_head_valid) {
 552                         ir_node *cfgpred = get_Block_cfgpred(node, i);
 553
 554                         if (!is_in_loop(cfgpred)) {
 555                                 DB((dbg, LEVEL_5, "potential head %+F because inloop and pred %+F not inloop\n",
 556                                                         node, pred));
 557                                 /* another head? We do not touch this. */
 558                                 if (loop_head && loop_head != node) {
 559                                         loop_head_valid = 0;
 560                                 } else {
 561                                         loop_head = node;
 562                                 }
 563                         }
 564                 }
 565         }
 566 }
 567
 568 #if 0
 569 /*  */
 570 static void correct_phis(ir_node *node, void *env)
 571 {
 572         (void)env;
 573
 574         if (is_Phi(node) && get_irn_arity(node) == 1) {
 575                 ir_node *exch;
 576                 ir_node *in[1];
 577                 in[0] = get_irn_n(node, 0);
 578
 579                 exch = new_rd_Phi(get_irn_dbg_info(node),
 580                         get_nodes_block(node), 1, in,
 581                         get_irn_mode(node));
 582
 583                 exchange(node, exch);
 584                 /* TODO make sure visited is copied */
 585         }
 586
 587
 588 }
 589 #endif
 590
 591 /* Adds all nodes pointing into the loop to loop_entries and also finds the loops head */
 592 static void get_loop_outs(ir_node *node, void *env)
 593 {
 594         unsigned node_in_loop, pred_in_loop;
 595         int i, arity;
 596         (void) env;
 597
 598         arity = get_irn_arity(node);
 599         for (i = 0; i < arity; ++i) {
 600                 ir_node *pred = get_irn_n(node, i);
 601
 602                 pred_in_loop = is_in_loop(pred);
 603                 node_in_loop = is_in_loop(node);
 604
 605                 if (pred_in_loop && !node_in_loop) {
 606                         out_edge entry;
 607                         entry.node = node;
 608                         entry.pos = i;
 609                         ARR_APP1(out_edge, cur_loop_outs, entry);
 610                         if (is_Block(node)) {
 611                                 ++loop_info.cf_outs;
 612                                 loop_info.cf_out = entry;
 613                         }
 614                         DB((dbg, LEVEL_5, "loop outs %N\n", node));
 615                 }
 616         }
 617 }
 618
 619 static ir_node *ssa_second_def;
 620 static ir_node *ssa_second_def_block;
 621
 622 /**
 623  * Walks the graph bottom up, searching for definitions and creates phis.
 624  */
 625 static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode)
 626 {
 627         int i;
 628         int n_cfgpreds;
 629         ir_graph *irg;
 630         ir_node *phi;
 631         ir_node **in;
 632
 633         DB((dbg, LEVEL_5, "ssa search_def_and_create_phis: block %N\n", block));
 634
 635         /* Prevents creation of phi that would be bad anyway.
 636          * Dead and bad blocks. */
 637         if (get_irn_arity(block) < 1 || is_Bad(block)) {
 638                 DB((dbg, LEVEL_5, "ssa bad %N\n", block));
 639                 return new_Bad();
 640         }
 641
 642         if (block == ssa_second_def_block) {
 643                 DB((dbg, LEVEL_5, "ssa found second definition: use second def %N\n", ssa_second_def));
 644                 return ssa_second_def;
 645         }
 646
 647         /* already processed this block? */
 648         if (irn_visited(block)) {
 649                 ir_node *value = get_irn_link(block);
 650                 DB((dbg, LEVEL_5, "ssa already visited: use linked %N\n", value));
 651                 return value;
 652         }
 653
 654         irg = get_irn_irg(block);
 655         assert(block != get_irg_start_block(irg));
 656
 657         /* a Block with only 1 predecessor needs no Phi */
 658         n_cfgpreds = get_Block_n_cfgpreds(block);
 659         if (n_cfgpreds == 1) {
 660                 ir_node *pred_block = get_Block_cfgpred_block(block, 0);
 661                 ir_node *value;
 662
 663                 DB((dbg, LEVEL_5, "ssa 1 pred: walk pred %N\n", pred_block));
 664
 665                 value = search_def_and_create_phis(pred_block, mode);
 666                 set_irn_link(block, value);
 667                 mark_irn_visited(block);
 668
 669                 return value;
 670         }
 671
 672         /* create a new Phi */
 673         NEW_ARR_A(ir_node*, in, n_cfgpreds);
 674         for (i = 0; i < n_cfgpreds; ++i)
 675                 in[i] = new_Unknown(mode);
 676
 677         phi = new_r_Phi(block, n_cfgpreds, in, mode);
 678
 679         /* Important: always keep block phi list up to date. */
 680         add_Block_phi(block, phi);
 681
 682         DB((dbg, LEVEL_5, "ssa phi creation: link new phi %N to block %N\n", phi, block));
 683
 684         set_irn_link(block, phi);
 685         mark_irn_visited(block);
 686
 687         /* set Phi predecessors */
 688         for (i = 0; i < n_cfgpreds; ++i) {
 689                 ir_node *pred_val;
 690                 ir_node *pred_block = get_Block_cfgpred_block(block, i);
 691                 assert(pred_block != NULL);
 692                 pred_val = search_def_and_create_phis(pred_block, mode);
 693                 assert(pred_val != NULL);
 694
 695                 DB((dbg, LEVEL_5, "ssa phi pred:phi %N, pred %N\n", phi, pred_val));
 696                 set_irn_n(phi, i, pred_val);
 697         }
 698
 699         return phi;
 700 }
 701
 702 /**
 703  * Given a set of values this function constructs SSA-form for the users of the
 704  * first value (the users are determined through the out-edges of the value).
 705  * Works without using the dominance tree.
 706  */
 707 static void construct_ssa(ir_node *orig_block, ir_node *orig_val,
 708                 ir_node *second_block, ir_node *second_val)
 709 {
 710         ir_graph *irg;
 711         ir_mode *mode;
 712         const ir_edge_t *edge;
 713         const ir_edge_t *next;
 714
 715         assert(orig_block && orig_val && second_block && second_val &&
 716                         "no parameter of construct_ssa may be NULL");
 717
 718         /* no need to do anything */
 719         if (orig_val == second_val)
 720                 return;
 721
 722         irg = get_irn_irg(orig_val);
 723
 724         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
 725         inc_irg_visited(irg);
 726
 727         mode = get_irn_mode(orig_val);
 728         set_irn_link(orig_block, orig_val);
 729         mark_irn_visited(orig_block);
 730
 731         ssa_second_def_block = second_block;
 732         ssa_second_def       = second_val;
 733
 734         /* Only fix the users of the first, i.e. the original node */
 735         foreach_out_edge_safe(orig_val, edge, next) {
 736                 ir_node *user = get_edge_src_irn(edge);
 737                 int j = get_edge_src_pos(edge);
 738                 ir_node *user_block = get_nodes_block(user);
 739                 ir_node *newval;
 740
 741                 /* ignore keeps */
 742                 if (is_End(user))
 743                         continue;
 744
 745                 DB((dbg, LEVEL_5, "original user %N\n", user));
 746
 747                 if (is_Phi(user)) {
 748                         ir_node *pred_block = get_Block_cfgpred_block(user_block, j);
 749                         newval = search_def_and_create_phis(pred_block, mode);
 750                 } else {
 751                         newval = search_def_and_create_phis(user_block, mode);
 752                 }
 753
 754                 assert(!is_Bad(newval));
 755
 756                 /* If we get a bad node the user keeps the original in.
 757                  * No second definition needed. */
 758                 if (newval != user && !is_Bad(newval))
 759                         set_irn_n(user, j, newval);
 760         }
 761
 762         ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
 763 }
 764
 765
 766 /* Construct ssa for def and all of its copies.
 767  * NOTE: Overwrites links of blocks.
 768 */
 769 static ir_node *construct_ssa_n(ir_node *def, ir_node *user, int copies)
 770 {
 771         ir_graph *irg;
 772         ir_mode *mode;
 773         irg = get_irn_irg(def);
 774         int i, user_arity;
 775         ir_node *newval;
 776
 777         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
 778         inc_irg_visited(current_ir_graph);
 779         mode = get_irn_mode(def);
 780
 781         set_irn_link(get_nodes_block(def), def);
 782         mark_irn_visited(get_nodes_block(def));
 783
 784         for (i = 0; i < copies; ++i) {
 785                 ir_node *cp = get_copy(def, i);
 786                 ir_node *block = get_nodes_block(cp);
 787                 set_irn_link(block, cp);
 788                 mark_irn_visited(block);
 789
 790                 DB((dbg, LEVEL_5, "ssa mark cp %N of def %N  usr %N\n", cp, def, user));
 791         }
 792
 793         newval = user;
 794         user_arity = get_irn_arity(user);
 795         for (i = 0; i < user_arity; ++i) {
 796                 ir_node *user_block = get_nodes_block(user);
 797                 if (get_irn_n(user, i) != def)
 798                         continue;
 799
 800                 DB((dbg, LEVEL_5, "ssa_n found edge of user %N\n", user));
 801
 802                 if (is_Phi(user)) {
 803                         ir_node *pred_block = get_Block_cfgpred_block(user_block, i);
 804                         newval = search_def_and_create_phis(pred_block, mode);
 805                 } else {
 806                         newval = search_def_and_create_phis(user_block, mode);
 807                 }
 808                 /*TODO bads should not happen! */
 809                 if (newval != user) {
 810                         DB((dbg, LEVEL_5, "=> ssa_n new in is %N\n", newval));
 811                         set_irn_n(user, i, newval);
 812                         /*if (is_Phi(newval) && get_nodes_block(newval)== user_block) {
 813                         ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
 814                                 return newval;
 815                         }*/
 816                 }
 817
 818                 /* BREAK, as we found and handled the definition */
 819                 break;
 820
 821 #if 0
 822                 if (is_Bad(newval)) {
 823                         DB((dbg, LEVEL_5, "=> ssa_n new in is BAD %N in graph %N\n", newval, current_ir_graph));
 824                         add_End_keepalive(get_irg_end(current_ir_graph), newval);
 825                         dump_ir_block_graph(current_ir_graph, "-bad");
 826                         assert(0);
 827
 828                 }
 829 #endif
 830         }
 831
 832         ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
 833         return NULL;
 834 }
 835
 836 /* Returns the number of backedges with or without alien bes. */
 837 static int get_backedge_n(ir_node *loophead, unsigned with_alien)
 838 {
 839         int i;
 840         int be_n = 0;
 841         int arity = get_irn_arity(loophead);
 842         for (i = 0; i < arity; ++i) {
 843                 ir_node *pred = get_irn_n(loophead, i);
 844                 if (is_backedge(loophead, i) && (with_alien || is_in_loop(pred)))
 845                         ++be_n;
 846         }
 847         return be_n;
 848 }
 849
 850 /**
 851  * Returns a raw copy of the given node.
 852  * Attributes are kept/set according to the needs of loop inversion.
 853  */
 854 static ir_node *copy_node_inversion(ir_node *node)
 855 {
 856         int i, arity;
 857         ir_node *cp;
 858
 859         cp = exact_copy(node);
 860         arity = get_irn_arity(node);
 861
 862         for (i = 0; i < arity; ++i) {
 863                 if (is_backedge(node, i))
 864                         set_backedge(cp, i);
 865         }
 866
 867         set_inversion_copy(node, cp);
 868         DB((dbg, LEVEL_5, "set copy of %N to cp %N \n", node, cp));
 869
 870         if (is_Block(cp)) {
 871                 /* We may not keep the old macroblock. */
 872                 set_Block_MacroBlock(cp, cp);
 873                 set_Block_mark(cp, 0);
 874         }
 875         return cp;
 876 }
 877
 878
 879 /**
 880  * This walker copies all walked nodes.
 881  * If the walk_condition is true for a node, it is copied.
 882  * All nodes node_info copy attributes have to be NULL prior to every walk.
 883  * TODO temporary nodes not necessary anymore.
 884  */
 885 static void copy_walk(ir_node *node, walker_condition *walk_condition,
 886                 ir_loop *set_loop)
 887 {
 888         int i;
 889         int arity;
 890         ir_node *cp;
 891         ir_node **cpin;
 892         ir_graph *irg = current_ir_graph;
 893
 894         /**
 895          * break condition and cycle resolver, creating temporary node copies
 896          */
 897         if (get_irn_visited(node) >= get_irg_visited(irg)) {
 898                 /* Here we rely on nodestate's copy being initialized with NULL */
 899                 DB((dbg, LEVEL_5, "copy_walk: We have already visited %N\n", node));
 900                 if (get_inversion_copy(node) == NULL) {
 901                         cp = copy_node_inversion(node);
 902                         DB((dbg, LEVEL_5, "The TEMP copy of %N is created %N\n", node, cp));
 903                 }
 904                 return;
 905         }
 906
 907         /* Walk */
 908         mark_irn_visited(node);
 909
 910         if (!is_Block(node)) {
 911                 ir_node *pred = get_nodes_block(node);
 912                 if (walk_condition(pred))
 913                         DB((dbg, LEVEL_5, "walk block %N\n", pred));
 914                 copy_walk(pred, walk_condition, set_loop);
 915         }
 916
 917         arity = get_irn_arity(node);
 918
 919         NEW_ARR_A(ir_node *, cpin, arity);
 920
 921         for (i = 0; i < arity; ++i) {
 922                 ir_node *pred = get_irn_n(node, i);
 923
 924                 if (walk_condition(pred)) {
 925                         DB((dbg, LEVEL_5, "walk node %N\n", pred));
 926                         copy_walk(pred, walk_condition, set_loop);
 927                         cpin[i] = get_inversion_copy(pred);
 928                         DB((dbg, LEVEL_5, "copy of %N gets new in %N which is copy of %N\n",
 929                                                 node, get_inversion_copy(pred), pred));
 930                 } else {
 931                         cpin[i] = pred;
 932                 }
 933         }
 934
 935         /* copy node / finalize temp node */
 936         if (get_inversion_copy(node) == NULL) {
 937                 /* No temporary copy existent */
 938                 cp = copy_node_inversion(node);
 939                 DB((dbg, LEVEL_5, "The FINAL copy of %N is CREATED %N\n", node, cp));
 940         } else {
 941                 /* temporary copy is existent but without correct ins */
 942                 cp = get_inversion_copy(node);
 943                 DB((dbg, LEVEL_5, "The FINAL copy of %N is EXISTENT %N\n", node, cp));
 944         }
 945
 946         if (!is_Block(node)) {
 947                 ir_node *cpblock = get_inversion_copy(get_nodes_block(node));
 948
 949                 set_nodes_block(cp, cpblock );
 950                 if (is_Phi(cp))
 951                         add_Block_phi(cpblock, cp);
 952         }
 953
 954         set_irn_loop(cp, set_loop);
 955
 956         /* Keeps phi list of temporary node. */
 957         set_irn_in(cp, ARR_LEN(cpin), cpin);
 958 }
 959
 960 /* Creates a new node from a given one, but with custom ins. */
 961 static ir_node *copy_node_changed(
 962                 ir_node *node, ir_node *block, int arity, ir_node **ins, ir_loop *loop)
 963 {
 964         ir_node *cp;
 965         DB((dbg, LEVEL_5, "New node from %N in %N block %N arity %d\n",
 966                                 node, get_irn_irg(node), block, arity));
 967 #if 0
 968         if (is_Phi(node)) {
 969                 cp = new_rd_Phi(get_irn_dbg_info(node),
 970                                 block,
 971                                 arity,
 972                                 ins,
 973                                 get_irn_mode(node));
 974
 975         } else {
 976 #endif
 977         /* We want to keep phi nodes with arity 1, as it makes rewiring a lot easier. */
 978         cp = new_ir_node(get_irn_dbg_info(node),
 979                         get_irn_irg(node),
 980                         block,
 981                         get_irn_op(node),
 982                         get_irn_mode(node),
 983                         arity,
 984                         ins);
 985
 986         if (is_Phi(cp))
 987                 add_Block_phi(block, cp);
 988         /* TODO */
 989         if (get_irn_op(node) == get_irn_op(cp))
 990                 copy_node_attr(get_irn_irg(node), node, cp);
 991
 992         /*new_backedge_info(cp); function removed */
 993         if (is_Block(cp))
 994                 set_Block_MacroBlock(cp, cp);
 995
 996         set_irn_loop(cp, loop);
 997
 998         /* Blocks are copied first, so that future phi nodes populate the phi list. */
 999         if (is_Block(cp))
1000                 set_Block_phis(cp, NULL);
1001
1002         DB((dbg, LEVEL_5, "New node %N in %N block %N arity %d\n",
1003                                 cp, get_irn_irg(cp), block, arity));
1004         return cp;
1005 }
1006
1007 /* To be exchangeable, the unknown needs to have proper graph set. */
1008 static ir_node *new_node_unknown(ir_node *block, ir_mode *mode)
1009 {
1010         ir_node *new = new_ir_node(NULL, get_irn_irg(block), block, op_Unknown, mode, 0, NULL);
1011         return new;
1012 }
1013
1014 /**
1015  * Walker, to copy alle nodes that meet the walk_condition.
1016  * Blocks are copied first, which is important for the creation of the phi lists.
1017  *
1018  */
1019 static ir_node *copy_walk_n(ir_node *node, walker_condition *walk_condition, int copy_index, int alloc_cp_arr)
1020 {
1021         int             i;
1022         int             arity;
1023         unsigned        headblock = 0;
1024         ir_node         *block, *cp, *new_cp;
1025         ir_node         **ins = NULL;
1026
1027         if (irn_visited(node)) {
1028                 cp = get_copy(node, copy_index);
1029
1030                 DB((dbg, LEVEL_5, "Visited %N\n", node));
1031
1032                 if (cp != NULL) {
1033                         DB((dbg, LEVEL_5, "Visited. Return copy %N\n", cp));
1034                         return cp;
1035                 }
1036
1037                 if (!is_Block(node)) {
1038                         ir_node *unknown = new_node_unknown(
1039                                         get_nodes_block(node),
1040                                         get_irn_mode(node));
1041                         DB((dbg, LEVEL_5, " #### Create Unknown %N for %N\n", unknown, node));
1042                         set_copy(node, copy_index, unknown);
1043                         return unknown;
1044                 }
1045         } else {
1046                 DB((dbg, LEVEL_5, "Walk %N\n", node));
1047                 mark_irn_visited(node);
1048
1049                 /* Allocate array of copies */
1050                 if (alloc_cp_arr > 0) {
1051                         ir_node **arr = NEW_ARR_F(ir_node *, alloc_cp_arr);
1052                         alloc_node_info(node);
1053                         for (i = 0; i < alloc_cp_arr; ++i)
1054                                 arr[i] = NULL;
1055                         set_copy_arr(node, arr);
1056                 }
1057         }
1058
1059         block = NULL;
1060         if (!is_Block(node)) {
1061                 ir_node *orig_block = get_nodes_block(node);
1062                 DB((dbg, LEVEL_5, "current node: %N about to walk block %N\n", node, orig_block));
1063                 /* Check walk_condition for blocks not necessary */
1064
1065                 if (orig_block == loop_head && is_Phi(node))
1066                         headblock = 1;
1067
1068                 block = copy_walk_n(orig_block, walk_condition, copy_index, alloc_cp_arr);
1069                 DB((dbg, LEVEL_5, "current node: %N block %N blocks copy %N\n",
1070                                         node, orig_block, block));
1071         } else {
1072                 if (node == loop_head)
1073                         headblock = 1;
1074         }
1075
1076
1077         arity = get_irn_arity(node);
1078
1079         if (headblock) {
1080                 /* Headblock and headblock-phi case */
1081                 int in_c = 0;
1082                 DB((dbg, LEVEL_5, "Headblock/Phi from headblock\n"));
1083                 NEW_ARR_A(ir_node *, ins, unroll_arity);
1084
1085                 for (i = 0; i < arity; ++i) {
1086                         ir_node *ret;
1087                         ir_node *pred = get_irn_n(node, i);
1088                         if (is_backedge(loop_head, i)) {
1089                                 if (walk_condition(pred)) {
1090                                         ret = copy_walk_n(pred, walk_condition, copy_index, alloc_cp_arr);
1091                                         DB((dbg, LEVEL_5, "in %d = %N walked\n", i, ret));
1092                                 } else {
1093                                         ret = pred;
1094                                         DB((dbg, LEVEL_5, "in %d = %N not walked\n", i, ret));
1095                                 }
1096                                 ins[in_c++] = ret;
1097                         }
1098                 }
1099                 arity = unroll_arity;
1100         } else {
1101                 /* Normal case */
1102                 NEW_ARR_A(ir_node *, ins, arity);
1103
1104                 for (i = 0; i < arity; ++i) {
1105                         ir_node *ret;
1106                         ir_node *pred = get_irn_n(node, i);
1107                         if (walk_condition(pred)) {
1108                                 ret = copy_walk_n(pred, walk_condition, copy_index, alloc_cp_arr);
1109                                 DB((dbg, LEVEL_5, "in %d = %N walked\n", i, ret));
1110                         } else {
1111                                 ret = pred;
1112                                 DB((dbg, LEVEL_5, "in %d = %N not walked\n", i, ret));
1113                         }
1114                         ins[i] = ret;
1115                 }
1116         }
1117
1118         /* NOW, after the walk, we may check if the blocks copy is already present. */
1119         cp = get_copy(node, copy_index);
1120         if (cp != NULL && !is_Unknown(cp)) {
1121                 DB((dbg, LEVEL_5, "Must be Block %N copy is already present\n", node, cp));
1122                 assert(is_Block(cp) &&
1123                                 "sanity: The copy should have been a block.");
1124                 return cp;
1125         }
1126
1127         new_cp = copy_node_changed(node, block, arity, ins, cur_loop);
1128         set_copy(node, copy_index, new_cp);
1129
1130         if (cp != NULL && is_Unknown(cp)) {
1131                 DB((dbg, LEVEL_5, "Found unknown %N in %N now exchanged by %N in %N\n",
1132                                         cp, get_irn_irg(cp), new_cp, get_irn_irg(new_cp)));
1133                 exchange(cp, new_cp);
1134         }
1135         return new_cp;
1136 }
1137
1138 /**
1139  * Populates head_entries with (node, pred_pos) tuple
1140  * whereas the node's pred at pred_pos is in the head but not the node itself.
1141  * Head and condition chain blocks must be marked.
1142  */
1143 static void get_head_outs(ir_node *node, void *env)
1144 {
1145         int i;
1146         int arity = get_irn_arity(node);
1147         (void) env;
1148
1149         DB((dbg, LEVEL_5, "get head entries %N \n", node));
1150
1151         for (i = 0; i < arity; ++i) {
1152                 /* node is not in the head, but the predecessor is.
1153                  * (head or loop chain nodes are marked) */
1154
1155                 DB((dbg, LEVEL_5, "node %N  marked %d (0)  pred %d marked %d (1) \n",
1156                                         node, is_nodes_block_marked(node), i,
1157                                         is_nodes_block_marked(get_irn_n(node, i))));
1158
1159                 if (!is_nodes_block_marked(node) && is_nodes_block_marked(get_irn_n(node, i))) {
1160                         out_edge entry;
1161                         entry.node = node;
1162                         entry.pos = i;
1163                         entry.pred = get_irn_n(node, i);
1164                         ARR_APP1(out_edge, cur_head_outs, entry);
1165
1166                         if (is_in_loop(node) && is_Block(node)) {
1167                                 loop_info.new_loop_head = node;
1168                                 DB((dbg, LEVEL_5, " SET NEW LOOPHEAD to %N\n", node));
1169                         }
1170                 }
1171         }
1172 #if 0
1173         if (is_Phi(node) && get_nodes_block(node) == loop_head)
1174         {
1175                 unsigned needs_ssa = 1;
1176                 unsigned loop_invar = 1;
1177                 for (i = 0; i < arity; ++i) {
1178                         if (is_own_backedge(node, i)) {
1179                                 if (get_irn_n(node, i) != node)
1180                                         loop_invar = 0;
1181
1182                                 if (is_nodes_block_marked(get_irn_n(node, i)))
1183                                         needs_ssa = 0;
1184                         }
1185                 }
1186                 /* Construct ssa for all uses of this phi, as there will be a copy of it. */
1187                 if(needs_ssa && !loop_invar) {
1188                         const ir_edge_t *edge;
1189                         DB((dbg, LEVEL_5, "NEEDS SSA users of phi %N\n", node));
1190                         foreach_out_edge(node, edge) {
1191                                 out_edge entry;
1192                                 entry.node = get_edge_src_irn(edge);
1193                                 DB((dbg, LEVEL_5, "NEEDS SSA user %N\n", entry.node));
1194                                 entry.pos = get_edge_src_pos(edge);
1195                                 ARR_APP1(out_edge, cur_head_outs, entry);
1196                         }
1197                 }
1198         }
1199 #endif
1200 }
1201
1202 /**
1203  * Find condition chains, and add them to be inverted
1204  * A block belongs to the chain if a condition branches out of the loop.
1205  * Returns 1 if the given block belongs to the condition chain.
1206  */
1207 static unsigned find_condition_chains(ir_node *block)
1208 {
1209         const ir_edge_t *edge;
1210         unsigned mark = 0;
1211         unsigned has_backedge = 0;
1212         int nodes_n = 0;
1213
1214         DB((dbg, LEVEL_5, "condition_chains for block %N\n", block));
1215
1216         /* Collect all outs, including keeps. */
1217         foreach_out_edge_kind(block, edge, EDGE_KIND_NORMAL) {
1218                 ++nodes_n;
1219         }
1220
1221         /* Leave at least one block as body. */
1222         if (head_inversion_node_count + nodes_n > inversion_head_node_limit
1223                         || head_inversion_block_count + 1 == loop_info.blocks) {
1224                 set_Block_mark(block, 0);
1225
1226                 return 0;
1227         }
1228
1229         /* First: check our successors,
1230          * and add all of them, which are outside of the loop, to the list */
1231         foreach_block_succ(block, edge) {
1232                 ir_node *src = get_edge_src_irn( edge );
1233                 int pos = get_edge_src_pos( edge );
1234
1235                 if (!is_in_loop(src)) {
1236                         out_edge entry;
1237
1238                         mark = 1;
1239                         entry.node = src;
1240                         entry.pos = pos;
1241                         ARR_APP1(out_edge, cond_chain_entries, entry);
1242                         mark_irn_visited(src);
1243                 } else if (is_backedge(src, pos)) {
1244                         /* Inverting blocks with backedge outs leads to a cf edge
1245                          * from the inverted head, into the inverted head (skipping the body).
1246                          * As the body becomes the new loop head,
1247                          * this would introduce another loop in the existing loop.
1248                          * This loop inversion cannot cope with this complex case. */
1249                         out_edge entry;
1250
1251                         has_backedge = 1;
1252                         entry.node = src;
1253                         entry.pos = pos;
1254                         ARR_APP1(out_edge, cond_chain_entries, entry);
1255                         mark_irn_visited(src);
1256                 }
1257         }
1258
1259         if (mark == 0 || has_backedge) {
1260                 set_Block_mark(block, 0);
1261                 return 0;
1262         } else {
1263                 set_Block_mark(block, 1);
1264                 ++head_inversion_block_count;
1265                 DB((dbg, LEVEL_5, "block %N is part of condition chain\n", block));
1266                 head_inversion_node_count += nodes_n;
1267         }
1268
1269         /* Second: walk all successors,
1270          * and add them to the list if they are not part of the chain */
1271         foreach_block_succ(block, edge) {
1272                 unsigned inchain;
1273                 ir_node *src = get_edge_src_irn( edge );
1274                 int pos = get_edge_src_pos( edge );
1275
1276                 /* already done */
1277                 if (!is_in_loop( src ) || irn_visited(src)) {
1278                         continue;
1279                 }
1280
1281                 mark_irn_visited(src);
1282                 DB((dbg, LEVEL_5, "condition chain walk %N\n", src));
1283                 inchain = find_condition_chains(src);
1284
1285                 /* if successor is not part of chain we need to collect its outs */
1286                 if (!inchain) {
1287                         out_edge entry;
1288                         entry.node = src;
1289                         entry.pos = pos;
1290                         ARR_APP1(out_edge, cond_chain_entries, entry);
1291                 }
1292         }
1293         return mark;
1294 }
1295
1296 /**
1297  * Rewires the copied condition chain. Removes backedges.
1298  * as this condition chain is prior to the loop.
1299  * Copy of loop_head must have phi list and old (unfixed) backedge info of the loop head.
1300  * (loop_head is already fixed, we cannot rely on it.)
1301  */
1302 static void fix_copy_inversion(void)
1303 {
1304         ir_node *new_head;
1305         ir_node **ins;
1306         ir_node **phis;
1307         ir_node *phi, *next;
1308         ir_node *head_cp        = get_inversion_copy(loop_head);
1309         int arity                       = get_irn_arity(head_cp);
1310         int backedges           = get_backedge_n(head_cp, 0);
1311         int new_arity           = arity - backedges;
1312         int pos;
1313         int i;
1314
1315         NEW_ARR_A(ir_node *, ins, new_arity);
1316
1317         pos = 0;
1318         /* Remove block backedges */
1319         for(i = 0; i < arity; ++i) {
1320                 if (!is_backedge(head_cp, i))
1321                         ins[pos++] = get_irn_n(head_cp, i);
1322         }
1323
1324         new_head = new_Block(new_arity, ins);
1325
1326         phis = NEW_ARR_F(ir_node *, 0);
1327
1328         for_each_phi_safe(get_Block_phis(head_cp), phi, next) {
1329                 ir_node *new_phi;
1330                 NEW_ARR_A(ir_node *, ins, new_arity);
1331                 pos = 0;
1332                 for(i = 0; i < arity; ++i) {
1333                         if (!is_backedge(head_cp, i))
1334                                 ins[pos++] = get_irn_n(phi, i);
1335                 }
1336                 new_phi = new_rd_Phi(get_irn_dbg_info(phi),
1337                                 new_head, new_arity, ins,
1338                                 get_irn_mode(phi));
1339                 ARR_APP1(ir_node *, phis, new_phi);
1340         }
1341
1342         pos = 0;
1343         for_each_phi_safe(get_Block_phis(head_cp), phi, next) {
1344                 exchange(phi, phis[pos++]);
1345         }
1346
1347         exchange(head_cp, new_head);
1348
1349         DEL_ARR_F(phis);
1350 }
1351
1352 /* Takes a phi from the inverted loop head and its pred
1353  * which is assigned in the condition chain.
1354  *
1355  * Returns new phi, created in the new loop head.
1356  * If there is an assignment in the condition chain
1357  * with a user also in the condition chain,
1358  * the dominance frontier is in the new loop head.
1359  * The dataflow loop is completely in the condition chain.
1360  * Goal:
1361  *
1362  *  | ,--.   |
1363  * Phi_cp |  | copied condition chain
1364  *  | |   |  |
1365  *  | ?__/   |
1366  *  | ,-.
1367  *  Phi* |   | new loop head
1368  *   |   |
1369  *  Phi  |   | original, inverted condition chain
1370  *   |   |   |
1371  *   ?__/    |
1372  *
1373  */
1374 static ir_node *fix_inner_cc_definitions(ir_node *phi, ir_node *pred)
1375 {
1376         int i;
1377         ir_node *head_phi;
1378         ir_node **head_phi_ins;
1379         ir_node *new_loop_head = loop_info.new_loop_head;
1380         int new_loop_head_arity = get_irn_arity(new_loop_head);
1381         DB((dbg, LEVEL_5, "NEW HEAD %N arity %d\n", new_loop_head, new_loop_head_arity));
1382
1383         NEW_ARR_A(ir_node *, head_phi_ins, new_loop_head_arity);
1384
1385         for(i = 0; i < new_loop_head_arity; ++i) {
1386                 /* Rely on correct backedge info for the new loop head
1387                  * is set by extend_ins_by_copy. */
1388
1389                 DB((dbg, LEVEL_5, "CHECK mark of pred of %N @%d  %N\n",
1390                                         new_loop_head, i, get_irn_n(new_loop_head, i)));
1391
1392                 if(is_nodes_block_marked(get_irn_n(new_loop_head, i))) {
1393                         head_phi_ins[i] = pred;
1394                         DB((dbg, LEVEL_5, "NEW HEAD %N pred %d %N is in cc\n", new_loop_head, i, pred));
1395                 } else {
1396                         ir_node *cp = get_inversion_copy(pred);
1397                         /* As pred is in the condition chain there has to be a copy. */
1398                         assert(cp);
1399                         head_phi_ins[i] = cp;
1400
1401                         DB((dbg, LEVEL_5, "NEW HEAD %N pred %d %N is in not in cc so get copy %N\n",
1402                                                 new_loop_head, i, pred, head_phi_ins[i] ));
1403                 }
1404                 DB((dbg, LEVEL_5, "NEW HEAD %N in %N %N\n",
1405                                         new_loop_head, head_phi_ins[i], current_ir_graph));
1406         }
1407
1408         head_phi= new_r_Phi(new_loop_head,
1409                         new_loop_head_arity,
1410                         head_phi_ins,
1411                         get_irn_mode(phi));
1412
1413         add_Block_phi(new_loop_head, head_phi);
1414
1415         DB((dbg, LEVEL_5, "fix inner cc definitions: new head %N has new phi %N from cc phi %N @%N\n",
1416                                 new_loop_head, head_phi, phi, pred));
1417
1418         return head_phi;
1419 }
1420
1421
1422 /* Puts the original condition chain at the end of the loop,
1423  * subsequently to the body.
1424  * Relies on block phi list and correct backedges.
1425  */
1426 static void fix_head_inversion(void)
1427 {
1428         ir_node *new_head;
1429         ir_node **ins;
1430         ir_node *phi, *next;
1431         ir_node **phis;
1432         int arity                       = get_irn_arity(loop_head);
1433         int backedges           = get_backedge_n(loop_head, 0);
1434         int new_arity           = backedges;
1435         int pos;
1436         int i;
1437
1438         NEW_ARR_A(ir_node *, ins, new_arity);
1439
1440         pos = 0;
1441         /* Keep only backedges */
1442         for(i = 0; i < arity; ++i) {
1443                 if (is_own_backedge(loop_head, i))
1444                         ins[pos++] = get_irn_n(loop_head, i);
1445         }
1446
1447         new_head = new_Block(new_arity, ins);
1448
1449         phis = NEW_ARR_F(ir_node *, 0);
1450
1451         for_each_phi(loop_head, phi) {
1452                 ir_node *new_phi;
1453
1454                 NEW_ARR_A(ir_node *, ins, new_arity);
1455
1456                 pos = 0;
1457                 for (i = 0; i < arity; ++i) {
1458                         ir_node *pred = get_irn_n(phi, i);
1459
1460                         if (is_own_backedge(loop_head, i)) {
1461                                 /* If assignment is in the condition chain,
1462                                  * we need to create a phi in the new loop head.
1463                                  * This can only happen for df, not cf. See find_condition_chains. */
1464                                 if (is_nodes_block_marked(pred)) {
1465                                         ins[pos++] = fix_inner_cc_definitions(phi, pred);
1466                                 } else {
1467                                         ins[pos++] = pred;
1468                                 }
1469                         }
1470                 }
1471
1472                 /**/
1473                 new_phi = new_rd_Phi(get_irn_dbg_info(phi),
1474                         new_head, new_arity, ins,
1475                         get_irn_mode(phi));
1476
1477                 ARR_APP1(ir_node *, phis, new_phi);
1478
1479                 DB((dbg, LEVEL_5, "fix inverted head should exch %N by %N\n", phi, new_phi));
1480         }
1481
1482         pos = 0;
1483         for_each_phi_safe(get_Block_phis(loop_head), phi, next) {
1484                 DB((dbg, LEVEL_5, "fix inverted exch phi %N by %N\n", phi, phis[pos]));
1485                 if (phis[pos] != phi)
1486                         exchange(phi, phis[pos++]);
1487         }
1488
1489         DEL_ARR_F(phis);
1490
1491         DB((dbg, LEVEL_5, "fix inverted head exch head block %N by %N\n", loop_head, new_head));
1492         exchange(loop_head, new_head);
1493 }
1494
1495 /* Does the loop inversion.  */
1496 static void inversion_walk(out_edge *head_entries)
1497 {
1498         int i;
1499
1500         /*
1501          * The order of rewiring bottom-up is crucial.
1502          * Any change of the order leads to lost information that would be needed later.
1503          */
1504
1505         ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
1506
1507         /* 1. clone condition chain */
1508         inc_irg_visited(current_ir_graph);
1509
1510         for (i = 0; i < ARR_LEN(head_entries); ++i) {
1511                 out_edge entry = head_entries[i];
1512                 ir_node *pred = get_irn_n(entry.node, entry.pos);
1513
1514                 DB((dbg, LEVEL_5, "\nInit walk block %N\n", pred));
1515
1516                 copy_walk(pred, is_nodes_block_marked, cur_loop);
1517         }
1518
1519         ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
1520
1521         /* 2. Extends the head control flow successors ins
1522          *    with the definitions of the copied head node. */
1523         for (i = 0; i < ARR_LEN(head_entries); ++i) {
1524                 out_edge head_out = head_entries[i];
1525
1526                 if (is_Block(head_out.node))
1527                         extend_ins_by_copy(head_out.node, head_out.pos);
1528         }
1529
1530         /* 3. construct_ssa for users of definitions in the condition chain,
1531          *    as there is now a second definition. */
1532         for (i = 0; i < ARR_LEN(head_entries); ++i) {
1533                 out_edge head_out = head_entries[i];
1534
1535                 /* Ignore keepalives */
1536                 if (is_End(head_out.node))
1537                         continue;
1538
1539                 /*if (!is_Block(head_out.node))
1540                         assert(is_nodes_block_marked(head_out.pred) && "damn");*/
1541
1542                 /* Construct ssa for definitions in the condition chain. */
1543                 if (!is_Block(head_out.node)) {
1544                         ir_node *pred, *cppred, *block, *cpblock;
1545
1546                         /* May not use get_irn_n(head_out.node, head_out.pos)
1547                          * as it can be changed by construct_ssa. */
1548                         pred = head_out.pred;
1549                         cppred = get_inversion_copy(pred);
1550                         block = get_nodes_block(pred);
1551                         cpblock = get_nodes_block(cppred);
1552                         construct_ssa(block, pred, cpblock, cppred);
1553                 }
1554         }
1555
1556         /* 4. Remove the ins which are no backedges from the original condition chain
1557          *    as the cc is now subsequently to the body. */
1558         fix_head_inversion();
1559
1560         /* 5. Remove the backedges of the copied condition chain,
1561          *    because it is going to be the new 'head' in advance to the loop */
1562         fix_copy_inversion();
1563 }
1564
1565 /* Analyse loop, if inversion is possible or reasonable. Then do the inversion. */
1566 static void loop_inversion(void)
1567 {
1568         unsigned do_inversion = 1;
1569
1570         inversion_head_node_limit = INT_MAX;
1571         ir_reserve_resources(current_ir_graph, IR_RESOURCE_BLOCK_MARK);
1572
1573         /* Reset block marks.
1574          * We use block marks to flag blocks of the original condition chain. */
1575         irg_walk_graph(current_ir_graph, reset_block_mark, NULL, NULL);
1576
1577         loop_info.blocks = get_loop_n_blocks(cur_loop);
1578         cond_chain_entries = NEW_ARR_F(out_edge, 0);
1579
1580         head_inversion_node_count = 0;
1581         head_inversion_block_count = 0;
1582
1583         set_Block_mark(loop_head, 1);
1584         mark_irn_visited(loop_head);
1585
1586         /* Use phase to keep copy of nodes from the condition chain. */
1587         phase = new_phase(current_ir_graph, phase_irn_init_default);
1588
1589         inc_irg_visited(current_ir_graph);
1590
1591         /* Search for condition chains. */
1592         find_condition_chains(loop_head);
1593
1594         DB((dbg, LEVEL_3, "Loop contains %d blocks.\n", loop_info.blocks));
1595
1596         if (loop_info.blocks < 2) {
1597                 do_inversion = 0;
1598                 DB((dbg, LEVEL_3,
1599                         "Loop contains %d (less than 2) blocks => No Inversion done.\n",
1600                         loop_info.blocks));
1601         }
1602
1603         /* We also catch endless loops here,
1604          * because they do not have a condition chain. */
1605         if (head_inversion_block_count < 1) {
1606                 do_inversion = 0;
1607                 DB((dbg, LEVEL_3,
1608                         "Loop contains %d (less than 1) invertible blocks => No Inversion done.\n",
1609                         head_inversion_block_count));
1610         }
1611
1612         if (do_inversion) {
1613                 cur_head_outs = NEW_ARR_F(out_edge, 0);
1614
1615                 /* Get all edges pointing into the condition chain. */
1616                 irg_walk_graph(current_ir_graph, get_head_outs, NULL, NULL);
1617
1618                 /* Do the inversion */
1619                 inversion_walk(cur_head_outs);
1620
1621                 DEL_ARR_F(cur_head_outs);
1622                 /* Duplicated blocks changed doms */
1623                 set_irg_doms_inconsistent(current_ir_graph);
1624                 /* Loop content changed */
1625                 set_irg_loopinfo_inconsistent(current_ir_graph);
1626                 /* TODO are they? Depends on set_irn_in and set_irn_n exchange and new_node. */
1627                 set_irg_outs_inconsistent(current_ir_graph);
1628         }
1629
1630         /* free */
1631         phase_free(phase);
1632         DEL_ARR_F(cond_chain_entries);
1633         ir_free_resources(current_ir_graph, IR_RESOURCE_BLOCK_MARK);
1634 }
1635
1636 /**
1637  * Rewire floating copies of the current loop.
1638  */
1639 static void place_copies(int copies)
1640 {
1641         ir_node *loophead = loop_head;
1642         int headarity =         get_irn_arity(loophead);
1643         ir_node *phi;
1644         int i, pos, c;
1645
1646         pos = 0;
1647         /* Append the copies to the existing loop. */
1648         for (i = 0; i < headarity; ++i) {
1649                 /* Build unrolled loop top down */
1650                 if (is_backedge(loophead, i) && !is_alien_edge(loophead, i)) {
1651                         for (c = 0; c < copies; ++c) {
1652                                 ir_node *upper_head;
1653                                 ir_node *lower_head = get_copy(loophead, c);
1654                                 ir_node *upper_pred;
1655
1656                                 if (c == 0) {
1657                                         upper_head = loophead;
1658                                         upper_pred = get_irn_n(loophead, i);
1659                                 } else {
1660                                         upper_head = get_copy(loophead, c - 1);
1661                                         upper_pred = get_copy_safe(get_irn_n(loophead, i), c - 1);
1662                                 }
1663                                 set_irn_n(lower_head, pos, upper_pred);
1664                                 for_each_phi(loophead, phi) {
1665                                         ir_node *lower_phi, *upper_phi, *upper_pred_phi;
1666                                         lower_phi = get_copy(phi, c);
1667                                         if (c == 0) {
1668                                                 upper_phi = phi;
1669                                                 upper_pred_phi = get_irn_n(phi, i);
1670                                         } else {
1671                                                 upper_phi = get_copy(phi, c - 1);
1672                                                 upper_pred_phi = get_copy_safe(get_irn_n(phi, i), c - 1);
1673                                         }
1674
1675                                         DB((dbg, LEVEL_5, "Rewire %N @%d to %N\n",
1676                                                                 lower_phi, pos, upper_pred_phi));
1677
1678                                         /* Relying on phi nodes with 1 in to be present. */
1679                                         assert(is_Phi(lower_phi));
1680
1681 /* Do not fix phis here. Chained phis will cause a defective copy array. */
1682 #if 0
1683                                         if (get_irn_arity(lower_phi) == 1) {
1684                                                 ir_node *single_in[1];
1685                                                 ir_node *cp;
1686                                                 single_in[0] = upper_pred_phi;
1687
1688                                                 cp = new_rd_Phi(get_irn_dbg_info(lower_phi),
1689                                                                 get_nodes_block(lower_phi), 1, single_in,
1690                                                                 get_irn_mode(lower_phi));
1691
1692                                                 set_copy(phi, c, cp);
1693                                                 exchange(lower_phi, cp);
1694                                         } else
1695 #endif
1696                                                 set_irn_n(lower_phi, pos, upper_pred_phi);
1697
1698                                 }
1699                         }
1700                         ++pos;
1701                         /* Fix the topmost loop heads backedges. */
1702                         set_irn_n(loophead, i, get_copy(get_irn_n(loophead, i), copies - 1));
1703                         for_each_phi(loophead, phi) {
1704                                 ir_node *last_cp = get_copy_safe(get_irn_n(phi, i), copies - 1);
1705                                 set_irn_n(phi, i, last_cp);
1706                         }
1707                 }
1708         }
1709 }
1710
1711 /* Copies the cur_loop */
1712 static void copy_loop(out_edge *cur_loop_outs, int copies)
1713 {
1714         int i, c;
1715         unroll_arity = get_backedge_n(loop_head, 0);
1716
1717         ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
1718
1719         /* copy loop */
1720         for (c = 0; c < copies; ++c) {
1721
1722                 inc_irg_visited(current_ir_graph);
1723
1724                 DB((dbg, LEVEL_5, "          ### Copy_loop  copy n: %d ###\n", c));
1725                 for (i = 0; i < ARR_LEN(cur_loop_outs); ++i) {
1726                         out_edge entry = cur_loop_outs[i];
1727                         ir_node *pred = get_irn_n(entry.node, entry.pos);
1728
1729                         copy_walk_n(pred, is_in_loop, c, c ? 0 : copies);
1730                 }
1731         }
1732
1733         ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
1734 }
1735
1736 /**/
1737 static void create_duffs_device(int unroll_number)
1738 {
1739         (void)unroll_number;
1740 }
1741
1742 #if 0
1743
1744 static unsigned is_loop_invariant_val(ir_node *node)
1745 {
1746         int i;
1747
1748         if (! is_in_loop(node))
1749                 return 1;
1750
1751         /* TODO all cases? and how to use the dom tree for that. */
1752
1753         if (is_Phi(node)) {
1754                 for (i = 0; i < get_irn_arity(node); ++i) {
1755                         if (is_own_backedge(get_nodes_block(node), i) && get_irn_n(node, i) != node)
1756                                 return 0;
1757                 }
1758         }
1759         return 1;
1760 }
1761
1762 /* TODO name */
1763 static ir_node *is_loop_iteration(ir_node *node)
1764 {
1765         int i;
1766         ir_node *found_add = NULL;
1767
1768         if (!is_in_loop(node))
1769                 return NULL;
1770
1771         if (is_Add(node))
1772                 return node;
1773
1774         /*TODO all cases? and how do i use the dom tree for that.*/
1775
1776         if (is_Phi(node)) {
1777                 for (i = 0; i < get_irn_arity(node); ++i) {
1778                         ir_node *new_found;
1779                         if (! is_own_backedge(get_nodes_block(node), i))
1780                                 continue;
1781                         new_found = get_irn_n(node,i);
1782
1783                         if (found_add && found_add != new_found)
1784                                 return NULL;
1785
1786                         found_add = new_found;
1787                 }
1788         }
1789         return found_add;
1790 }
1791
1792 /* counting loop */
1793 static unsigned get_unroll_decision(out_edge *cur_loop_outs)
1794 {
1795         int i;
1796         ir_node *pred0, *pred1, *projx, *cond, *projres, *loop_condition;
1797         ir_node *iteration, *add, *iteration_phi, *end_val, *step, *add_in0, *add_in1;
1798
1799         (void) cur_loop_outs;
1800         (void) i;
1801
1802
1803         /* There is more than 1 condition for the loop exit. We cannot cope this with duffs device. */
1804         if (loop_info.cf_outs != 1)
1805                 return 0;
1806
1807         /*TODO test for impact on performance */
1808         if (loop_info.calls > 0)
1809                 return 0;
1810
1811
1812         projx = get_irn_n(loop_info.cf_out.node, loop_info.cf_out.pos);
1813         cond = get_irn_n(projx, 0);
1814         projres = get_irn_n(cond, 0);
1815         loop_condition = get_irn_n(projres, 0);
1816
1817         DB((dbg, LEVEL_2, " loop condition %N in graph %N\n", loop_condition, current_ir_graph));
1818
1819         /* One in of the loop condition needs to be loop invariant.
1820          * The other in is assigned by an add.
1821          * The add uses a loop invariant value
1822          * and another value that depends on a loop invariant start value and the add itself.
1823
1824            ^   ^
1825            |   | .-,
1826            |   Phi |
1827                 \  |   |
1828                  Add  /
1829               |__/
1830         */
1831
1832         end_val = NULL;
1833         iteration = NULL;
1834
1835         /* Find the loop invariant in */
1836         /* Assumption that condition is cmp or mod.
1837            TODO other? */
1838         pred0 = get_irn_n(loop_condition, 0);
1839         pred1 = get_irn_n(loop_condition, 1);
1840
1841         if (is_loop_invariant_val(pred0)) {
1842                 end_val = pred0;
1843                 iteration = pred1;
1844         }
1845
1846
1847         if (is_loop_invariant_val(pred1)) {
1848                 if (end_val != NULL)
1849                         /* RETURN. loop condition does not change during the loop. */
1850                         return 0;
1851
1852                 end_val = pred1;
1853                 iteration = pred0;
1854         }
1855
1856         DB((dbg, LEVEL_2, " end_val %N\n", end_val));
1857
1858         add = NULL;
1859         /* Check for constraint of remaining in. */
1860         add = is_loop_iteration(iteration);
1861         if (! add)
1862                 return 0;
1863
1864         DB((dbg, LEVEL_2, " add %N\n", add));
1865
1866         add_in0 = get_irn_n(add, 0);
1867         add_in1 = get_irn_n(add, 1);
1868
1869         step = NULL;
1870         iteration_phi = NULL;
1871
1872         if (is_loop_invariant_val(add_in0)) {
1873                 step = add_in0;
1874                 iteration_phi = add_in1;
1875         }
1876
1877         DB((dbg, LEVEL_2, "seems step %N iter_phi %N\n", step, iteration_phi));
1878
1879         if (is_loop_invariant_val(add_in1)) {
1880                 if (step != NULL)
1881                         return 0;
1882                 step = add_in1;
1883                 iteration_phi = add_in0;
1884         }
1885
1886         DB((dbg, LEVEL_2, " step %N\n", step));
1887
1888         if (! is_Phi(iteration_phi)) {
1889                 if (is_Phi(iteration))
1890                         iteration_phi = iteration;
1891                 else
1892                         return 0;
1893         }
1894
1895         DB((dbg, LEVEL_2, " #### COUNTING LOOP in graph %N step %N end %N phi %N\n",
1896                                 current_ir_graph, step, end_val, iteration_phi));
1897
1898 #if 0
1899         phi for startval
1900
1901         mode = get_irn_mode(add);
1902
1903         block = new_Block(0, NULL);
1904         /*set_irg_current_Block(current_ir_graph, block);*/
1905
1906         /*TODO*/
1907         unroll_mod_const = new_Const(unroll_number);
1908         module = new_d_Mod(block, new_NoMem(), end_val, step, mode, op_pin_state_pinned);
1909         /*new_Proj();*/
1910
1911
1912 #endif
1913         return 0;
1914 }
1915 #endif
1916
1917 /**
1918  * Loop unrolling
1919  */
1920 static void unroll_loop(void)
1921 {
1922         int i;
1923         unsigned unroll_number;
1924         out_edge *ssa_outs;
1925         cur_loop_outs = NEW_ARR_F(out_edge, 0);
1926
1927         /* Get loop outs */
1928         irg_walk_graph(current_ir_graph, get_loop_outs, NULL, NULL);
1929
1930         /*unroll_number = get_unroll_decision(cur_loop_outs);*/
1931         unroll_number = 2;
1932
1933         /*dump_ir_block_graph(current_ir_graph, "-pre");*/
1934
1935         if (unroll_number) {
1936                 create_duffs_device(unroll_number);
1937
1938                 /* Copies the loop and allocs node_info */
1939                 copy_loop(cur_loop_outs, unroll_number - 1);
1940                 /*dump_ir_block_graph(current_ir_graph, "-cp");*/
1941
1942                 /* Line up the floating copies. */
1943                 place_copies(unroll_number - 1);
1944                 /*dump_ir_block_graph(current_ir_graph, "-ord");*/
1945
1946                 /* Extend loop successors */
1947                 ssa_outs = extend_ins(cur_loop_outs, unroll_number - 1);
1948                 /*dump_ir_block_graph(current_ir_graph, "-fixed")*/ ;
1949
1950                 /* Links are going to be overwritten */
1951                 free_node_info_blocks();
1952
1953                 /* Generate phis for all loop outs */
1954                 for (i = 0; i < ARR_LEN(ssa_outs); ++i) {
1955                         out_edge entry = ssa_outs[i];
1956                         ir_node *node = entry.node;
1957                         ir_node *pred = get_irn_n(entry.node, entry.pos);
1958
1959                         DB((dbg, LEVEL_5, "Do? construct_ssa_n def %N  node %N  pos %d\n",
1960                                         pred, node, entry.pos));
1961
1962                         if (!is_End(node)) {
1963                                 DB((dbg, LEVEL_5, "construct_ssa_n def %N  node %N  pos %d\n",
1964                                                         pred, node, entry.pos));
1965
1966                                 construct_ssa_n(pred, node, unroll_number - 1);
1967                                 /*if (new_phi)
1968                                         construct_ssa_n(pred, new_phi, unroll_number - 1);*/
1969                         }
1970                 }
1971                 /*dump_ir_block_graph(current_ir_graph, "-ssa-done");*/
1972
1973                 /* FREE */
1974                 free_node_info();
1975
1976                 /*irg_walk_graph(current_ir_graph, correct_phis, NULL, NULL);*/
1977
1978                 DEL_ARR_F(ssa_outs);
1979
1980                 set_irg_doms_inconsistent(current_ir_graph);
1981                 set_irg_loopinfo_inconsistent(current_ir_graph);
1982                 set_irg_outs_inconsistent(current_ir_graph);
1983         }
1984         DEL_ARR_F(cur_loop_outs);
1985 }
1986
1987 /* Initialization and */
1988 static void init_analyze(ir_loop *loop)
1989 {
1990         /* Init new for every loop */
1991         cur_loop = loop;
1992
1993         loop_head = NULL;
1994         loop_head_valid = 1;
1995         loop_inv_head = NULL;
1996         loop_peeled_head = NULL;
1997
1998         loop_info.calls = 0;
1999         loop_info.blocks = 0;
2000         loop_info.cf_outs = 0;
2001
2002         DB((dbg, LEVEL_2, "          >>>> current loop includes node %N <<<\n",
2003                 get_loop_node(loop, 0)));
2004
2005         irg_walk_graph(current_ir_graph, get_loop_info, NULL, NULL);
2006
2007         /* RETURN if there is no valid head */
2008         if (!loop_head || !loop_head_valid) {
2009                 DB((dbg, LEVEL_2,   "No valid loop head. Nothing done.\n"));
2010                 return;
2011         }
2012
2013         DB((dbg, LEVEL_2,   "Loophead: %N\n", loop_head));
2014
2015         if (enable_inversion)
2016                 loop_inversion();
2017
2018         if (enable_unrolling)
2019                 unroll_loop();
2020
2021         DB((dbg, LEVEL_2, "             <<<< end of loop with node %N >>>>\n",
2022                 get_loop_node(loop, 0)));
2023 }
2024
2025 /* Find most inner loops and send them to analyze_loop */
2026 static void find_most_inner_loop(ir_loop *loop)
2027 {
2028         /* descend into sons */
2029         int sons = get_loop_n_sons(loop);
2030
2031         if (sons == 0) {
2032                 ARR_APP1(ir_loop *, loops, loop);
2033         } else {
2034                 int s;
2035                 for (s=0; s<sons; s++) {
2036                         find_most_inner_loop(get_loop_son(loop, s));
2037                 }
2038         }
2039 }
2040
2041 /**
2042  * Assure preconditions are met and go through all loops.
2043  */
2044 void loop_optimization(ir_graph *irg)
2045 {
2046         ir_loop *loop;
2047         int     i, sons, nr;
2048
2049         /* Init */
2050         free_list = NULL;
2051         set_current_ir_graph(irg);
2052
2053         edges_assure(irg);
2054         assure_irg_outs(irg);
2055
2056         /* NOTE: sets only the loop attribute of blocks, not nodes */
2057         /* NOTE: Kills links */
2058         assure_cf_loop(irg);
2059
2060         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
2061         collect_phiprojs(irg);
2062         ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
2063
2064         loop = get_irg_loop(irg);
2065         sons = get_loop_n_sons(loop);
2066
2067         loops = NEW_ARR_F(ir_loop *, 0);
2068         /* List all inner loops */
2069         for (nr = 0; nr < sons; ++nr) {
2070                 find_most_inner_loop(get_loop_son(loop, nr));
2071         }
2072
2073         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
2074         /* Set all links NULL */
2075         irg_walk_graph(current_ir_graph, reset_link, NULL, NULL);
2076
2077         for (i = 0; i < ARR_LEN(loops); ++i) {
2078                 ir_loop *loop = loops[i];
2079                 init_analyze(loop);
2080
2081                 /*dump_ir_block_graph(current_ir_graph, "-part");*/
2082                 collect_phiprojs(irg);
2083                 irg_walk_graph(current_ir_graph, reset_link, NULL, NULL);
2084         }
2085
2086         /*dump_ir_block_graph(current_ir_graph, "-full");*/
2087
2088         DEL_ARR_F(loops);
2089         ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
2090         ir_free_resources(irg, IR_RESOURCE_PHI_LIST);
2091 }
2092
2093 void do_loop_unrolling(ir_graph *irg)
2094 {
2095         enable_unrolling = 1;
2096         enable_peeling = 0;
2097         enable_inversion = 0;
2098
2099         DB((dbg, LEVEL_2, " >>> unrolling (Startnode %N) <<<\n",
2100                                 get_irg_start(irg)));
2101
2102         loop_optimization(irg);
2103
2104         DB((dbg, LEVEL_2, " >>> unrolling done (Startnode %N) <<<\n",
2105                                 get_irg_start(irg)));
2106 }
2107
2108 void do_loop_inversion(ir_graph *irg)
2109 {
2110         enable_unrolling = 0;
2111         enable_peeling = 0;
2112         enable_inversion = 1;
2113
2114         DB((dbg, LEVEL_2, " >>> inversion (Startnode %N) <<<\n",
2115                                 get_irg_start(irg)));
2116
2117         loop_optimization(irg);
2118
2119         DB((dbg, LEVEL_2, " >>> inversion done (Startnode %N) <<<\n",
2120                                 get_irg_start(irg)));
2121 }
2122
2123 void do_loop_peeling(ir_graph *irg)
2124 {
2125         enable_unrolling = 0;
2126         enable_peeling = 1;
2127         enable_inversion = 0;
2128
2129         DB((dbg, LEVEL_2, " >>> peeling (Startnode %N) <<<\n",
2130                                 get_irg_start(irg)));
2131
2132         loop_optimization(irg);
2133
2134         DB((dbg, LEVEL_2, " >>> peeling done (Startnode %N) <<<\n",
2135                                 get_irg_start(irg)));
2136
2137 }
2138
2139 ir_graph_pass_t *loop_inversion_pass(const char *name)
2140 {
2141         return def_graph_pass(name ? name : "loop_inversion", do_loop_inversion);
2142 }
2143
2144 ir_graph_pass_t *loop_unroll_pass(const char *name)
2145 {
2146         return def_graph_pass(name ? name : "loop_unroll", do_loop_unrolling);
2147 }
2148
2149 ir_graph_pass_t *loop_peeling_pass(const char *name)
2150 {
2151         return def_graph_pass(name ? name : "loop_peeling", do_loop_peeling);
2152 }
2153
2154 void firm_init_loop_opt(void)
2155 {
2156         FIRM_DBG_REGISTER(dbg, "firm.opt.loop");
2157 }