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

   1 /*
   2  * Copyright (C) 1995-2011 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  */
  26 #include "config.h"
  27
  28 #include <stdbool.h>
  29
  30 #include "iroptimize.h"
  31 #include "opt_init.h"
  32 #include "irnode.h"
  33 #include "debug.h"
  34 #include "error.h"
  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 <math.h>
  49 #include "irbackedge_t.h"
  50 #include "irnodemap.h"
  51 #include "irloop_t.h"
  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 /* Flag for kind of unrolling. */
  70 typedef enum {
  71         constant,
  72         invariant
  73 } unrolling_kind_flag;
  74
  75 /* Condition for performing visiting a node during copy_walk. */
  76 typedef bool walker_condition(const ir_node *);
  77
  78 /* Node and position of a predecessor. */
  79 typedef struct entry_edge {
  80         ir_node *node;
  81         int pos;
  82         ir_node *pred;
  83 } entry_edge;
  84
  85 /* Node info for unrolling. */
  86 typedef struct unrolling_node_info {
  87         ir_node **copies;
  88 } unrolling_node_info;
  89
  90 /* Outs of the nodes head. */
  91 static entry_edge *cur_head_outs;
  92
  93 /* Information about the loop head */
  94 static ir_node *loop_head       = NULL;
  95 static bool     loop_head_valid = true;
  96
  97 /* List of all inner loops, that are processed. */
  98 static ir_loop **loops;
  99
 100 /* Stats */
 101 typedef struct loop_stats_t {
 102         unsigned loops;
 103         unsigned inverted;
 104         unsigned too_large;
 105         unsigned too_large_adapted;
 106         unsigned cc_limit_reached;
 107         unsigned calls_limit;
 108
 109         unsigned u_simple_counting_loop;
 110         unsigned constant_unroll;
 111         unsigned invariant_unroll;
 112
 113         unsigned unhandled;
 114 } loop_stats_t;
 115
 116 static loop_stats_t stats;
 117
 118 /* Set stats to sero */
 119 static void reset_stats(void)
 120 {
 121         memset(&stats, 0, sizeof(loop_stats_t));
 122 }
 123
 124 /* Print stats */
 125 static void print_stats(void)
 126 {
 127         DB((dbg, LEVEL_2, "---------------------------------------\n"));
 128         DB((dbg, LEVEL_2, "loops             :   %d\n",stats.loops));
 129         DB((dbg, LEVEL_2, "inverted          :   %d\n",stats.inverted));
 130         DB((dbg, LEVEL_2, "too_large         :   %d\n",stats.too_large));
 131         DB((dbg, LEVEL_2, "too_large_adapted :   %d\n",stats.too_large_adapted));
 132         DB((dbg, LEVEL_2, "cc_limit_reached  :   %d\n",stats.cc_limit_reached));
 133         DB((dbg, LEVEL_2, "calls_limit       :   %d\n",stats.calls_limit));
 134         DB((dbg, LEVEL_2, "u_simple_counting :   %d\n",stats.u_simple_counting_loop));
 135         DB((dbg, LEVEL_2, "constant_unroll   :   %d\n",stats.constant_unroll));
 136         DB((dbg, LEVEL_2, "invariant_unroll  :   %d\n",stats.invariant_unroll));
 137         DB((dbg, LEVEL_2, "=======================================\n"));
 138 }
 139
 140 /* Commandline parameters */
 141 typedef struct loop_opt_params_t {
 142 unsigned max_loop_size;     /* Maximum number of nodes  [nodes]*/
 143 int      depth_adaption;    /* Loop nest depth adaption [percent] */
 144 unsigned allowed_calls;     /* Number of calls allowed [number] */
 145 bool     count_phi;         /* Count phi nodes */
 146 bool     count_proj;        /* Count projections */
 147
 148 unsigned max_cc_size;       /* Maximum condition chain size [nodes] */
 149 unsigned max_branches;
 150
 151 unsigned max_unrolled_loop_size;    /* [nodes] */
 152 bool     allow_const_unrolling;
 153 bool     allow_invar_unrolling;
 154 unsigned invar_unrolling_min_size;  /* [nodes] */
 155
 156 } loop_opt_params_t;
 157
 158 static loop_opt_params_t opt_params;
 159
 160 /* Loop analysis informations */
 161 typedef struct loop_info_t {
 162         unsigned nodes;        /* node count */
 163         unsigned ld_st;        /* load and store nodes */
 164         unsigned branches;     /* number of conditions */
 165         unsigned calls;        /* number of calls */
 166         unsigned cf_outs;      /* number of cf edges which leave the loop */
 167         entry_edge cf_out;     /* single loop leaving cf edge */
 168         int be_src_pos;        /* position of the single own backedge in the head */
 169
 170         /* for inversion */
 171         unsigned cc_size;      /* nodes in the condition chain */
 172
 173         /* for unrolling */
 174         unsigned max_unroll;   /* Number of unrolls satisfying max_loop_size */
 175         unsigned exit_cond;    /* 1 if condition==true exits the loop.  */
 176         unsigned latest_value:1;    /* 1 if condition is checked against latest counter value */
 177         unsigned needs_backedge:1;  /* 0 if loop is completely unrolled */
 178         unsigned decreasing:1;      /* Step operation is_Sub, or step is<0 */
 179
 180         /* IV informations of a simple loop */
 181         ir_node *start_val;
 182         ir_node *step;
 183         ir_node *end_val;
 184         ir_node *iteration_phi;
 185         ir_node *add;
 186
 187         ir_tarval *count_tar;               /* Number of loop iterations */
 188
 189         ir_node *duff_cond;                 /* Duff mod */
 190         unrolling_kind_flag unroll_kind;    /* constant or invariant unrolling */
 191 } loop_info_t;
 192
 193 /* Information about the current loop */
 194 static loop_info_t loop_info;
 195
 196 /* Outs of the condition chain (loop inversion). */
 197 static ir_node **cc_blocks;
 198 /* df/cf edges with def in the condition chain */
 199 static entry_edge *cond_chain_entries;
 200 /* Array of df loops found in the condition chain. */
 201 static entry_edge *head_df_loop;
 202 /* Number of blocks in cc */
 203 static unsigned inversion_blocks_in_cc;
 204
 205
 206 /* Cf/df edges leaving the loop.
 207  * Called entries here, as they are used to enter the loop with walkers. */
 208 static entry_edge *loop_entries;
 209 /* Number of unrolls to perform */
 210 static int unroll_nr;
 211 /* Phase is used to keep copies of nodes. */
 212 static ir_nodemap     map;
 213 static struct obstack obst;
 214
 215 /* Loop operations.  */
 216 typedef enum loop_op_t {
 217         loop_op_inversion,
 218         loop_op_unrolling,
 219         loop_op_peeling
 220 } loop_op_t;
 221
 222 /* Saves which loop operation to do until after basic tests. */
 223 static loop_op_t loop_op;
 224
 225 /* Returns the maximum nodes for the given nest depth */
 226 static unsigned get_max_nodes_adapted(unsigned depth)
 227 {
 228         double perc = 100.0 + (double)opt_params.depth_adaption;
 229         double factor = pow(perc / 100.0, depth);
 230
 231         return (int)((double)opt_params.max_loop_size * factor);
 232 }
 233
 234 /* Reset nodes link. For use with a walker. */
 235 static void reset_link(ir_node *node, void *env)
 236 {
 237         (void)env;
 238         set_irn_link(node, NULL);
 239 }
 240
 241 /* Returns 0 if the node or block is not in cur_loop. */
 242 static bool is_in_loop(const ir_node *node)
 243 {
 244         return get_irn_loop(get_block_const(node)) == cur_loop;
 245 }
 246
 247 /* Returns 0 if the given edge is not a backedge
 248  * with its pred in the cur_loop. */
 249 static bool is_own_backedge(const ir_node *n, int pos)
 250 {
 251         return is_backedge(n, pos) && is_in_loop(get_irn_n(n, pos));
 252 }
 253
 254 /* Finds loop head and some loop_info as calls or else if necessary. */
 255 static void get_loop_info(ir_node *node, void *env)
 256 {
 257         bool node_in_loop = is_in_loop(node);
 258         int i, arity;
 259         (void)env;
 260
 261         /* collect some loop information */
 262         if (node_in_loop) {
 263                 if (is_Phi(node) && opt_params.count_phi)
 264                         ++loop_info.nodes;
 265                 else if (is_Proj(node) && opt_params.count_proj)
 266                         ++loop_info.nodes;
 267                 else if (!is_Confirm(node) && !is_Const(node) && !is_SymConst(node))
 268                         ++loop_info.nodes;
 269
 270                 if (is_Load(node) || is_Store(node))
 271                         ++loop_info.ld_st;
 272
 273                 if (is_Call(node))
 274                         ++loop_info.calls;
 275         }
 276
 277         arity = get_irn_arity(node);
 278         for (i = 0; i < arity; i++) {
 279                 ir_node *pred         = get_irn_n(node, i);
 280                 bool     pred_in_loop = is_in_loop(pred);
 281
 282                 if (is_Block(node) && !node_in_loop && pred_in_loop) {
 283                         entry_edge entry;
 284                         entry.node = node;
 285                         entry.pos = i;
 286                         entry.pred = pred;
 287                         /* Count cf outs */
 288                         ++loop_info.cf_outs;
 289                         loop_info.cf_out = entry;
 290                 }
 291
 292                 /* Find the loops head/the blocks with cfpred outside of the loop */
 293                 if (is_Block(node)) {
 294                         unsigned outs_n = 0;
 295
 296                         /* Count innerloop branches */
 297                         foreach_out_edge_kind(node, edge, EDGE_KIND_BLOCK) {
 298                                 ir_node *succ = get_edge_src_irn(edge);
 299                                 if (is_Block(succ) && is_in_loop(succ))
 300                                         ++outs_n;
 301                         }
 302                         if (outs_n > 1)
 303                                 ++loop_info.branches;
 304
 305                         if (node_in_loop && !pred_in_loop && loop_head_valid) {
 306                                 ir_node *cfgpred = get_Block_cfgpred(node, i);
 307
 308                                 if (!is_in_loop(cfgpred)) {
 309                                         DB((dbg, LEVEL_5, "potential head %+F because inloop and pred %+F not inloop\n",
 310                                                                 node, pred));
 311                                         /* another head? We do not touch this. */
 312                                         if (loop_head && loop_head != node) {
 313                                                 loop_head_valid = false;
 314                                         } else {
 315                                                 loop_head = node;
 316                                         }
 317                                 }
 318                         }
 319                 }
 320         }
 321 }
 322
 323 /* Finds all edges with users outside of the loop
 324  * and definition inside the loop. */
 325 static void get_loop_entries(ir_node *node, void *env)
 326 {
 327         unsigned node_in_loop, pred_in_loop;
 328         int i, arity;
 329         (void) env;
 330
 331         arity = get_irn_arity(node);
 332         for (i = 0; i < arity; ++i) {
 333                 ir_node *pred = get_irn_n(node, i);
 334
 335                 pred_in_loop = is_in_loop(pred);
 336                 node_in_loop = is_in_loop(node);
 337
 338                 if (pred_in_loop && !node_in_loop) {
 339                         entry_edge entry;
 340                         entry.node = node;
 341                         entry.pos = i;
 342                         entry.pred = pred;
 343                         ARR_APP1(entry_edge, loop_entries, entry);
 344                 }
 345         }
 346 }
 347
 348 /* ssa */
 349 static ir_node *ssa_second_def;
 350 static ir_node *ssa_second_def_block;
 351
 352 /**
 353  * Walks the graph bottom up, searching for definitions and creates phis.
 354  */
 355 static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode, int first)
 356 {
 357         int i;
 358         int n_cfgpreds;
 359         ir_graph *irg = get_irn_irg(block);
 360         ir_node *phi;
 361         ir_node **in;
 362
 363         DB((dbg, LEVEL_5, "ssa search_def_and_create_phis: block %N\n", block));
 364
 365         /* Prevents creation of phi that would be bad anyway.
 366          * Dead and bad blocks. */
 367         if (get_irn_arity(block) < 1 || is_Bad(block)) {
 368                 DB((dbg, LEVEL_5, "ssa bad %N\n", block));
 369                 return new_r_Bad(irg, mode);
 370         }
 371
 372         if (block == ssa_second_def_block && !first) {
 373                 DB((dbg, LEVEL_5, "ssa found second definition: use second def %N\n", ssa_second_def));
 374                 return ssa_second_def;
 375         }
 376
 377         /* already processed this block? */
 378         if (irn_visited(block)) {
 379                 ir_node *value = (ir_node *) get_irn_link(block);
 380                 DB((dbg, LEVEL_5, "ssa already visited: use linked %N\n", value));
 381                 return value;
 382         }
 383
 384         assert(block != get_irg_start_block(irg));
 385
 386         /* a Block with only 1 predecessor needs no Phi */
 387         n_cfgpreds = get_Block_n_cfgpreds(block);
 388         if (n_cfgpreds == 1) {
 389                 ir_node *pred_block = get_Block_cfgpred_block(block, 0);
 390                 ir_node *value;
 391
 392                 DB((dbg, LEVEL_5, "ssa 1 pred: walk pred %N\n", pred_block));
 393
 394                 value = search_def_and_create_phis(pred_block, mode, 0);
 395                 set_irn_link(block, value);
 396                 mark_irn_visited(block);
 397
 398                 return value;
 399         }
 400
 401         /* create a new Phi */
 402         NEW_ARR_A(ir_node*, in, n_cfgpreds);
 403         for (i = 0; i < n_cfgpreds; ++i)
 404                 in[i] = new_r_Dummy(irg, mode);
 405
 406         phi = new_r_Phi(block, n_cfgpreds, in, mode);
 407         /* Important: always keep block phi list up to date. */
 408         add_Block_phi(block, phi);
 409         DB((dbg, LEVEL_5, "ssa phi creation: link new phi %N to block %N\n", phi, block));
 410         set_irn_link(block, phi);
 411         mark_irn_visited(block);
 412
 413         /* set Phi predecessors */
 414         for (i = 0; i < n_cfgpreds; ++i) {
 415                 ir_node *pred_val;
 416                 ir_node *pred_block = get_Block_cfgpred_block(block, i);
 417                 assert(pred_block != NULL);
 418                 pred_val = search_def_and_create_phis(pred_block, mode, 0);
 419
 420                 assert(pred_val != NULL);
 421
 422                 DB((dbg, LEVEL_5, "ssa phi pred:phi %N, pred %N\n", phi, pred_val));
 423                 set_irn_n(phi, i, pred_val);
 424         }
 425
 426         return phi;
 427 }
 428
 429
 430 /**
 431  * Given a set of values this function constructs SSA-form for the users of the
 432  * first value (the users are determined through the out-edges of the value).
 433  * Works without using the dominance tree.
 434  */
 435 static void construct_ssa(ir_node *orig_block, ir_node *orig_val,
 436                 ir_node *second_block, ir_node *second_val)
 437 {
 438         ir_graph *irg;
 439         ir_mode *mode;
 440
 441         assert(orig_block && orig_val && second_block && second_val &&
 442                         "no parameter of construct_ssa may be NULL");
 443
 444         if (orig_val == second_val)
 445                 return;
 446
 447         irg = get_irn_irg(orig_val);
 448
 449         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
 450         inc_irg_visited(irg);
 451
 452         mode = get_irn_mode(orig_val);
 453         set_irn_link(orig_block, orig_val);
 454         mark_irn_visited(orig_block);
 455
 456         ssa_second_def_block = second_block;
 457         ssa_second_def       = second_val;
 458
 459         /* Only fix the users of the first, i.e. the original node */
 460         foreach_out_edge_safe(orig_val, edge) {
 461                 ir_node *user = get_edge_src_irn(edge);
 462                 int j = get_edge_src_pos(edge);
 463                 ir_node *user_block = get_nodes_block(user);
 464                 ir_node *newval;
 465
 466                 /* ignore keeps */
 467                 if (is_End(user))
 468                         continue;
 469
 470                 DB((dbg, LEVEL_5, "original user %N\n", user));
 471
 472                 if (is_Phi(user)) {
 473                         ir_node *pred_block = get_Block_cfgpred_block(user_block, j);
 474                         newval = search_def_and_create_phis(pred_block, mode, 1);
 475                 } else {
 476                         newval = search_def_and_create_phis(user_block, mode, 1);
 477                 }
 478                 if (newval != user && !is_Bad(newval))
 479                         set_irn_n(user, j, newval);
 480         }
 481
 482         ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
 483 }
 484
 485
 486 /***** Unrolling Helper Functions *****/
 487
 488 /* Assign the copy with index nr to node n */
 489 static void set_unroll_copy(ir_node *n, int nr, ir_node *cp)
 490 {
 491         unrolling_node_info *info;
 492         assert(nr != 0 && "0 reserved");
 493
 494         info = ir_nodemap_get(unrolling_node_info, &map, n);
 495         if (! info) {
 496                 ir_node **const arr = NEW_ARR_DZ(ir_node*, &obst, unroll_nr);
 497
 498                 info = OALLOCZ(&obst, unrolling_node_info);
 499                 info->copies = arr;
 500                 ir_nodemap_insert(&map, n, info);
 501         }
 502         /* Original node */
 503         info->copies[0] = n;
 504
 505         info->copies[nr] = cp;
 506 }
 507
 508 /* Returns a nodes copy if it exists, else NULL. */
 509 static ir_node *get_unroll_copy(ir_node *n, int nr)
 510 {
 511         ir_node             *cp;
 512         unrolling_node_info *info = ir_nodemap_get(unrolling_node_info, &map, n);
 513         if (! info)
 514                 return NULL;
 515
 516         cp = info->copies[nr];
 517         return cp;
 518 }
 519
 520
 521 /***** Inversion Helper Functions *****/
 522
 523 /* Sets copy cp of node n. */
 524 static void set_inversion_copy(ir_node *n, ir_node *cp)
 525 {
 526         ir_nodemap_insert(&map, n, cp);
 527 }
 528
 529 /* Getter of copy of n for inversion */
 530 static ir_node *get_inversion_copy(ir_node *n)
 531 {
 532         ir_node *cp = ir_nodemap_get(ir_node, &map, n);
 533         return cp;
 534 }
 535
 536 /* Resets block mark for given node. For use with walker */
 537 static void reset_block_mark(ir_node *node, void * env)
 538 {
 539         (void) env;
 540
 541         if (is_Block(node))
 542                 set_Block_mark(node, 0);
 543 }
 544
 545 /* Returns mark of node, or its block if node is not a block.
 546  * Used in this context to determine if node is in the condition chain. */
 547 static bool is_nodes_block_marked(const ir_node* node)
 548 {
 549         return get_Block_mark(get_block_const(node));
 550 }
 551
 552 /* Extends a nodes ins by node new.
 553  * NOTE: This is slow if a node n needs to be extended more than once. */
 554 static void extend_irn(ir_node *n, ir_node *newnode, bool new_is_backedge)
 555 {
 556         int i;
 557         int arity = get_irn_arity(n);
 558         int new_arity = arity + 1;
 559         ir_node **ins = XMALLOCN(ir_node*, new_arity);
 560         bool     *bes = XMALLOCN(bool, new_arity);
 561
 562         /* save bes */
 563         /* Bes are important!
 564          * Another way would be recreating the looptree,
 565          * but after that we cannot distinguish already processed loops
 566          * from not yet processed ones. */
 567         if (is_Block(n)) {
 568                 for(i = 0; i < arity; ++i) {
 569                         bes[i] = is_backedge(n, i);
 570                 }
 571                 bes[i] = new_is_backedge;
 572         }
 573
 574         for(i = 0; i < arity; ++i) {
 575                 ins[i] = get_irn_n(n, i);
 576         }
 577         ins[i] = newnode;
 578
 579         set_irn_in(n, new_arity, ins);
 580
 581         /* restore bes  */
 582         if (is_Block(n)) {
 583                 for(i = 0; i < new_arity; ++i) {
 584                         if (bes[i])
 585                                 set_backedge(n, i);
 586                 }
 587         }
 588         free(ins);
 589         free(bes);
 590 }
 591
 592 /* Extends a block by a copy of its pred at pos,
 593  * fixing also the phis in the same way. */
 594 static void extend_ins_by_copy(ir_node *block, int pos)
 595 {
 596         ir_node *new_in;
 597         ir_node *phi;
 598
 599         /* Extend block by copy of definition at pos */
 600         ir_node *const pred = get_Block_cfgpred(block, pos);
 601         new_in = get_inversion_copy(pred);
 602         DB((dbg, LEVEL_5, "Extend block %N by %N cp of %N\n", block, new_in, pred));
 603         extend_irn(block, new_in, false);
 604
 605         /* Extend block phis by copy of definition at pos */
 606         for_each_phi(block, phi) {
 607                 ir_node *pred, *cp;
 608
 609                 pred = get_irn_n(phi, pos);
 610                 cp = get_inversion_copy(pred);
 611                 /* If the phis in is not in the condition chain (eg. a constant),
 612                  * there is no copy. */
 613                 if (cp == NULL)
 614                         new_in = pred;
 615                 else
 616                         new_in = cp;
 617
 618                 DB((dbg, LEVEL_5, "Extend phi %N by %N cp of %N\n", phi, new_in, pred));
 619                 extend_irn(phi, new_in, false);
 620         }
 621 }
 622
 623 /* Returns the number of blocks backedges. With or without alien bes. */
 624 static int get_backedge_n(ir_node *block, bool with_alien)
 625 {
 626         int       be_n  = 0;
 627         int const arity = get_Block_n_cfgpreds(block);
 628         for (int i = 0; i < arity; ++i) {
 629                 ir_node *const pred = get_Block_cfgpred(block, i);
 630                 if (is_backedge(block, i) && (with_alien || is_in_loop(pred)))
 631                         ++be_n;
 632         }
 633         return be_n;
 634 }
 635
 636 /* Returns a raw copy of the given node.
 637  * Attributes are kept/set according to the needs of loop inversion. */
 638 static ir_node *copy_node(ir_node *node)
 639 {
 640         int i, arity;
 641         ir_node *cp;
 642
 643         cp = exact_copy(node);
 644         arity = get_irn_arity(node);
 645
 646         /* Keep backedge info */
 647         for (i = 0; i < arity; ++i) {
 648                 if (is_backedge(node, i))
 649                         set_backedge(cp, i);
 650         }
 651
 652         if (is_Block(cp)) {
 653                 set_Block_mark(cp, 0);
 654         }
 655
 656         return cp;
 657 }
 658
 659
 660 /**
 661  * This walker copies all walked nodes.
 662  * If the walk_condition is true for a node, it is copied.
 663  * All nodes node_info->copy have to be NULL prior to every walk.
 664  * Order of ins is important for later usage.
 665  */
 666 static void copy_walk(ir_node *node, walker_condition *walk_condition,
 667                       ir_loop *set_loop)
 668 {
 669         int i;
 670         int arity;
 671         ir_node *cp;
 672         ir_node **cpin;
 673
 674         /**
 675          * break condition and cycle resolver, creating temporary node copies
 676          */
 677         if (irn_visited(node)) {
 678                 /* Here we rely on nodestate's copy being initialized with NULL */
 679                 DB((dbg, LEVEL_5, "copy_walk: We have already visited %N\n", node));
 680                 if (get_inversion_copy(node) == NULL) {
 681                         cp = copy_node(node);
 682                         set_inversion_copy(node, cp);
 683
 684                         DB((dbg, LEVEL_5, "The TEMP copy of %N is created %N\n", node, cp));
 685                 }
 686                 return;
 687         }
 688
 689         /* Walk */
 690         mark_irn_visited(node);
 691
 692         if (!is_Block(node)) {
 693                 ir_node *pred = get_nodes_block(node);
 694                 if (walk_condition(pred))
 695                         DB((dbg, LEVEL_5, "walk block %N\n", pred));
 696                 copy_walk(pred, walk_condition, set_loop);
 697         }
 698
 699         arity = get_irn_arity(node);
 700
 701         NEW_ARR_A(ir_node *, cpin, arity);
 702
 703         for (i = 0; i < arity; ++i) {
 704                 ir_node *pred = get_irn_n(node, i);
 705
 706                 if (walk_condition(pred)) {
 707                         DB((dbg, LEVEL_5, "walk node %N\n", pred));
 708                         copy_walk(pred, walk_condition, set_loop);
 709                         cpin[i] = get_inversion_copy(pred);
 710                         DB((dbg, LEVEL_5, "copy of %N gets new in %N which is copy of %N\n",
 711                                                 node, get_inversion_copy(pred), pred));
 712                 } else {
 713                         cpin[i] = pred;
 714                 }
 715         }
 716
 717         /* copy node / finalize temp node */
 718         if (get_inversion_copy(node) == NULL) {
 719                 /* No temporary copy existent */
 720                 cp = copy_node(node);
 721                 set_inversion_copy(node, cp);
 722                 DB((dbg, LEVEL_5, "The FINAL copy of %N is CREATED %N\n", node, cp));
 723         } else {
 724                 /* temporary copy is existent but without correct ins */
 725                 cp = get_inversion_copy(node);
 726                 DB((dbg, LEVEL_5, "The FINAL copy of %N is EXISTENT %N\n", node, cp));
 727         }
 728
 729         if (!is_Block(node)) {
 730                 ir_node *cpblock = get_inversion_copy(get_nodes_block(node));
 731
 732                 set_nodes_block(cp, cpblock );
 733                 if (is_Phi(cp))
 734                         add_Block_phi(cpblock, cp);
 735         }
 736
 737         /* Keeps phi list of temporary node. */
 738         set_irn_in(cp, ARR_LEN(cpin), cpin);
 739 }
 740
 741 /**
 742  * This walker copies all walked nodes.
 743  * If the walk_condition is true for a node, it is copied.
 744  * All nodes node_info->copy have to be NULL prior to every walk.
 745  * Order of ins is important for later usage.
 746  * Takes copy_index, to phase-link copy at specific index.
 747  */
 748 static void copy_walk_n(ir_node *node, walker_condition *walk_condition,
 749                         int copy_index)
 750 {
 751         int i;
 752         int arity;
 753         ir_node *cp;
 754         ir_node **cpin;
 755
 756         /**
 757          * break condition and cycle resolver, creating temporary node copies
 758          */
 759         if (irn_visited(node)) {
 760                 /* Here we rely on nodestate's copy being initialized with NULL */
 761                 DB((dbg, LEVEL_5, "copy_walk: We have already visited %N\n", node));
 762                 if (get_unroll_copy(node, copy_index) == NULL) {
 763                         ir_node *u;
 764                         u = copy_node(node);
 765                         set_unroll_copy(node, copy_index, u);
 766                         DB((dbg, LEVEL_5, "The TEMP unknown of %N is created %N\n", node, u));
 767                 }
 768                 return;
 769         }
 770
 771         /* Walk */
 772         mark_irn_visited(node);
 773
 774         if (!is_Block(node)) {
 775                 ir_node *block = get_nodes_block(node);
 776                 if (walk_condition(block))
 777                         DB((dbg, LEVEL_5, "walk block %N\n", block));
 778                 copy_walk_n(block, walk_condition, copy_index);
 779         }
 780
 781         arity = get_irn_arity(node);
 782         NEW_ARR_A(ir_node *, cpin, arity);
 783
 784         for (i = 0; i < arity; ++i) {
 785                 ir_node *pred = get_irn_n(node, i);
 786
 787                 if (walk_condition(pred)) {
 788                         DB((dbg, LEVEL_5, "walk node %N\n", pred));
 789                         copy_walk_n(pred, walk_condition, copy_index);
 790                         cpin[i] = get_unroll_copy(pred, copy_index);
 791                 } else {
 792                         cpin[i] = pred;
 793                 }
 794         }
 795
 796         /* copy node / finalize temp node */
 797         cp = get_unroll_copy(node, copy_index);
 798         if (cp == NULL || is_Unknown(cp)) {
 799                 cp = copy_node(node);
 800                 set_unroll_copy(node, copy_index, cp);
 801                 DB((dbg, LEVEL_5, "The FINAL copy of %N is CREATED %N\n", node, cp));
 802         } else {
 803                 /* temporary copy is existent but without correct ins */
 804                 cp = get_unroll_copy(node, copy_index);
 805                 DB((dbg, LEVEL_5, "The FINAL copy of %N is EXISTENT %N\n", node, cp));
 806         }
 807
 808         if (!is_Block(node)) {
 809                 ir_node *cpblock = get_unroll_copy(get_nodes_block(node), copy_index);
 810
 811                 set_nodes_block(cp, cpblock );
 812                 if (is_Phi(cp))
 813                         add_Block_phi(cpblock, cp);
 814         }
 815
 816         /* Keeps phi list of temporary node. */
 817         set_irn_in(cp, ARR_LEN(cpin), cpin);
 818 }
 819
 820 /* Removes alle Blocks with non marked predecessors from the condition chain. */
 821 static void unmark_not_allowed_cc_blocks(void)
 822 {
 823         size_t blocks = ARR_LEN(cc_blocks);
 824         size_t i;
 825
 826         for(i = 0; i < blocks; ++i) {
 827                 ir_node *block = cc_blocks[i];
 828
 829                 /* Head is an exception. */
 830                 if (block == loop_head)
 831                         continue;
 832
 833                 int const arity = get_Block_n_cfgpreds(block);
 834                 for (int a = 0; a < arity; ++a) {
 835                         if (!is_nodes_block_marked(get_Block_cfgpred(block, a))) {
 836                                 set_Block_mark(block, 0);
 837                                 --inversion_blocks_in_cc;
 838                                 DB((dbg, LEVEL_5, "Removed %N from cc (blocks in cc %d)\n",
 839                                                 block, inversion_blocks_in_cc));
 840
 841                                 break;
 842                         }
 843                 }
 844         }
 845 }
 846
 847 /* Unmarks all cc blocks using cc_blocks except head.
 848  * TODO: invert head for unrolling? */
 849 static void unmark_cc_blocks(void)
 850 {
 851         size_t blocks = ARR_LEN(cc_blocks);
 852         size_t i;
 853
 854         for(i = 0; i < blocks; ++i) {
 855                 ir_node *block = cc_blocks[i];
 856
 857                 /* TODO Head is an exception. */
 858                 /*if (block != loop_head)*/
 859                 set_Block_mark(block, 0);
 860         }
 861         /*inversion_blocks_in_cc = 1;*/
 862         inversion_blocks_in_cc = 0;
 863
 864         /* invalidate */
 865         loop_info.cc_size = 0;
 866 }
 867
 868 /**
 869  * Populates head_entries with (node, pred_pos) tuple
 870  * whereas the node's pred at pred_pos is in the cc but not the node itself.
 871  * Also finds df loops inside the cc.
 872  * Head and condition chain blocks have been marked previously.
 873  */
 874 static void get_head_outs(ir_node *node, void *env)
 875 {
 876         int i;
 877         int arity = get_irn_arity(node);
 878         (void) env;
 879
 880         for (i = 0; i < arity; ++i) {
 881                 if (!is_nodes_block_marked(node) && is_nodes_block_marked(get_irn_n(node, i))) {
 882                         entry_edge entry;
 883                         entry.node = node;
 884                         entry.pos = i;
 885                         /* Saving also predecessor seems redundant, but becomes
 886                          * necessary when changing position of it, before
 887                          * dereferencing it.*/
 888                         entry.pred = get_irn_n(node, i);
 889                         ARR_APP1(entry_edge, cur_head_outs, entry);
 890                 }
 891         }
 892
 893         arity = get_irn_arity(loop_head);
 894
 895         /* Find df loops inside the cc */
 896         if (is_Phi(node) && get_nodes_block(node) == loop_head) {
 897                 for (i = 0; i < arity; ++i) {
 898                         if (is_own_backedge(loop_head, i)) {
 899                                 if (is_nodes_block_marked(get_irn_n(node, i))) {
 900                                         entry_edge entry;
 901                                         entry.node = node;
 902                                         entry.pos = i;
 903                                         entry.pred = get_irn_n(node, i);
 904                                         ARR_APP1(entry_edge, head_df_loop, entry);
 905                                         DB((dbg, LEVEL_5, "Found incc assignment node %N @%d is pred %N, graph %N %N\n",
 906                                                         node, i, entry.pred, current_ir_graph, get_irg_start_block(current_ir_graph)));
 907                                 }
 908                         }
 909                 }
 910         }
 911 }
 912
 913 /**
 914  * Find condition chains, and add them to be inverted.
 915  * A block belongs to the chain if a condition branches out of the loop.
 916  * (Some blocks need to be removed once again.)
 917  * Returns 1 if the given block belongs to the condition chain.
 918  */
 919 static void find_condition_chain(ir_node *block)
 920 {
 921         bool     mark     = false;
 922         bool     has_be   = false;
 923         bool     jmp_only = true;
 924         unsigned nodes_n  = 0;
 925
 926         mark_irn_visited(block);
 927
 928         DB((dbg, LEVEL_5, "condition_chains for block %N\n", block));
 929
 930         /* Get node count */
 931         foreach_out_edge_kind(block, edge, EDGE_KIND_NORMAL) {
 932                 ++nodes_n;
 933         }
 934
 935         /* Check if node count would exceed maximum cc size.
 936          * TODO
 937          * This is not optimal, as we search depth-first and break here,
 938          * continuing with another subtree. */
 939         if (loop_info.cc_size + nodes_n > opt_params.max_cc_size) {
 940                 set_Block_mark(block, 0);
 941                 return;
 942         }
 943
 944         /* Check if block only has a jmp instruction. */
 945         foreach_out_edge(block, edge) {
 946                 ir_node *src = get_edge_src_irn(edge);
 947
 948                 if (!is_Block(src) && !is_Jmp(src)) {
 949                         jmp_only = false;
 950                 }
 951         }
 952
 953         /* Check cf outs if one is leaving the loop,
 954          * or if this node has a backedge. */
 955         foreach_block_succ(block, edge) {
 956                 ir_node *src = get_edge_src_irn(edge);
 957                 int pos = get_edge_src_pos(edge);
 958
 959                 if (!is_in_loop(src))
 960                         mark = true;
 961
 962                 /* Inverting blocks with backedge outs leads to a cf edge
 963                  * from the inverted head, into the inverted head (skipping the body).
 964                  * As the body becomes the new loop head,
 965                  * this would introduce another loop in the existing loop.
 966                  * This loop inversion cannot cope with this case. */
 967                 if (is_backedge(src, pos)) {
 968                         has_be = true;
 969                         break;
 970                 }
 971         }
 972
 973         /* We need all predecessors to already belong to the condition chain.
 974          * Example of wrong case:  * == in cc
 975          *
 976          *     Head*             ,--.
 977          *    /|   \            B   |
 978          *   / A*  B           /    |
 979          *  / /\   /          ?     |
 980          *   /   C*      =>      D  |
 981          *      /  D           Head |
 982          *     /               A  \_|
 983          *                      C
 984          */
 985         /* Collect blocks containing only a Jmp.
 986          * Do not collect blocks with backedge outs. */
 987         if ((jmp_only || mark) && !has_be) {
 988                 set_Block_mark(block, 1);
 989                 ++inversion_blocks_in_cc;
 990                 loop_info.cc_size += nodes_n;
 991                 DB((dbg, LEVEL_5, "block %N is part of condition chain\n", block));
 992                 ARR_APP1(ir_node *, cc_blocks, block);
 993         } else {
 994                 set_Block_mark(block, 0);
 995         }
 996
 997         foreach_block_succ(block, edge) {
 998                 ir_node *src = get_edge_src_irn( edge );
 999
1000                 if (is_in_loop(src) && ! irn_visited(src))
1001                         find_condition_chain(src);
1002         }
1003 }
1004
1005 /**
1006  * Rewires the copied condition chain. Removes backedges
1007  * as this condition chain is prior to the loop.
1008  * Copy of loop_head must have phi list and old (unfixed) backedge info of the loop head.
1009  * (loop_head is already fixed, we cannot rely on it.)
1010  */
1011 static void fix_copy_inversion(void)
1012 {
1013         ir_node *new_head;
1014         ir_node **ins;
1015         ir_node **phis;
1016         ir_node *phi, *next;
1017         ir_node *head_cp = get_inversion_copy(loop_head);
1018         ir_graph *irg    = get_irn_irg(head_cp);
1019         int arity        = get_irn_arity(head_cp);
1020         int backedges    = get_backedge_n(head_cp, false);
1021         int new_arity    = arity - backedges;
1022         int pos;
1023         int i;
1024
1025         NEW_ARR_A(ir_node *, ins, new_arity);
1026
1027         pos = 0;
1028         /* Remove block backedges */
1029         for(i = 0; i < arity; ++i) {
1030                 if (!is_backedge(head_cp, i))
1031                         ins[pos++] = get_irn_n(head_cp, i);
1032         }
1033
1034         new_head = new_r_Block(irg, new_arity, ins);
1035
1036         phis = NEW_ARR_F(ir_node *, 0);
1037
1038         for_each_phi_safe(get_Block_phis(head_cp), phi, next) {
1039                 ir_node *new_phi;
1040                 NEW_ARR_A(ir_node *, ins, new_arity);
1041                 pos = 0;
1042                 for(i = 0; i < arity; ++i) {
1043                         if (!is_backedge(head_cp, i))
1044                                 ins[pos++] = get_irn_n(phi, i);
1045                 }
1046                 new_phi = new_rd_Phi(get_irn_dbg_info(phi),
1047                                 new_head, new_arity, ins,
1048                                 get_irn_mode(phi));
1049                 ARR_APP1(ir_node *, phis, new_phi);
1050         }
1051
1052         pos = 0;
1053         for_each_phi_safe(get_Block_phis(head_cp), phi, next) {
1054                 exchange(phi, phis[pos++]);
1055         }
1056
1057         exchange(head_cp, new_head);
1058
1059         DEL_ARR_F(phis);
1060 }
1061
1062
1063 /* Puts the original condition chain at the end of the loop,
1064  * subsequently to the body.
1065  * Relies on block phi list and correct backedges.
1066  */
1067 static void fix_head_inversion(void)
1068 {
1069         ir_node *new_head;
1070         ir_node **ins;
1071         ir_node *phi, *next;
1072         ir_node **phis;
1073         ir_graph *irg = get_irn_irg(loop_head);
1074         int arity     = get_irn_arity(loop_head);
1075         int backedges = get_backedge_n(loop_head, false);
1076         int new_arity = backedges;
1077         int pos;
1078         int i;
1079
1080         NEW_ARR_A(ir_node *, ins, new_arity);
1081
1082         pos = 0;
1083         /* Keep only backedges */
1084         for(i = 0; i < arity; ++i) {
1085                 if (is_own_backedge(loop_head, i))
1086                         ins[pos++] = get_irn_n(loop_head, i);
1087         }
1088
1089         new_head = new_r_Block(irg, new_arity, ins);
1090
1091         phis = NEW_ARR_F(ir_node *, 0);
1092
1093         for_each_phi(loop_head, phi) {
1094                 ir_node *new_phi;
1095                 DB((dbg, LEVEL_5, "Fixing phi %N of loop head\n", phi));
1096
1097                 NEW_ARR_A(ir_node *, ins, new_arity);
1098
1099                 pos = 0;
1100                 for (i = 0; i < arity; ++i) {
1101                         ir_node *pred = get_irn_n(phi, i);
1102
1103                         if (is_own_backedge(loop_head, i)) {
1104                                 /* If assignment is in the condition chain,
1105                                  * we need to create a phi in the new loop head.
1106                                  * This can only happen for df, not cf. See find_condition_chains. */
1107                                 /*if (is_nodes_block_marked(pred)) {
1108                                         ins[pos++] = pred;
1109                                 } else {*/
1110                                 ins[pos++] = pred;
1111
1112                         }
1113                 }
1114
1115                 new_phi = new_rd_Phi(get_irn_dbg_info(phi),
1116                         new_head, new_arity, ins,
1117                         get_irn_mode(phi));
1118
1119                 ARR_APP1(ir_node *, phis, new_phi);
1120
1121                 DB((dbg, LEVEL_5, "fix inverted head should exch %N by %N (pos %d)\n", phi, new_phi, pos ));
1122         }
1123
1124         pos = 0;
1125         for_each_phi_safe(get_Block_phis(loop_head), phi, next) {
1126                 DB((dbg, LEVEL_5, "fix inverted exch phi %N by %N\n", phi, phis[pos]));
1127                 if (phis[pos] != phi)
1128                         exchange(phi, phis[pos++]);
1129         }
1130
1131         DEL_ARR_F(phis);
1132
1133         DB((dbg, LEVEL_5, "fix inverted head exch head block %N by %N\n", loop_head, new_head));
1134         exchange(loop_head, new_head);
1135 }
1136
1137 /* Does the loop inversion.  */
1138 static void inversion_walk(ir_graph *irg, entry_edge *head_entries)
1139 {
1140         size_t i;
1141
1142         /*
1143          * The order of rewiring bottom-up is crucial.
1144          * Any change of the order leads to lost information that would be needed later.
1145          */
1146
1147         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
1148
1149         /* 1. clone condition chain */
1150         inc_irg_visited(irg);
1151
1152         for (i = 0; i < ARR_LEN(head_entries); ++i) {
1153                 entry_edge entry = head_entries[i];
1154                 ir_node *pred = get_irn_n(entry.node, entry.pos);
1155
1156                 DB((dbg, LEVEL_5, "\nInit walk block %N\n", pred));
1157
1158                 copy_walk(pred, is_nodes_block_marked, cur_loop);
1159         }
1160
1161         ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
1162
1163         /* 2. Extends the head control flow successors ins
1164          *    with the definitions of the copied head node. */
1165         for (i = 0; i < ARR_LEN(head_entries); ++i) {
1166                 entry_edge head_out = head_entries[i];
1167
1168                 if (is_Block(head_out.node))
1169                         extend_ins_by_copy(head_out.node, head_out.pos);
1170         }
1171
1172         /* 3. construct_ssa for users of definitions in the condition chain,
1173          *    as there is now a second definition. */
1174         for (i = 0; i < ARR_LEN(head_entries); ++i) {
1175                 entry_edge head_out = head_entries[i];
1176
1177                 /* Ignore keepalives */
1178                 if (is_End(head_out.node))
1179                         continue;
1180
1181                 /* Construct ssa for assignments in the condition chain. */
1182                 if (!is_Block(head_out.node)) {
1183                         ir_node *pred, *cppred, *block, *cpblock;
1184
1185                         pred = head_out.pred;
1186                         cppred = get_inversion_copy(pred);
1187                         block = get_nodes_block(pred);
1188                         cpblock = get_nodes_block(cppred);
1189                         construct_ssa(block, pred, cpblock, cppred);
1190                 }
1191         }
1192
1193         /*
1194          * If there is an assignment in the condition chain
1195          * with a user also in the condition chain,
1196          * the dominance frontier is in the new loop head.
1197          * The dataflow loop is completely in the condition chain.
1198          * Goal:
1199          *  To be wired: >|
1200          *
1201          *  | ,--.   |
1202          * Phi_cp |  | copied condition chain
1203          * >| |   |  |
1204          * >| ?__/   |
1205          * >| ,-.
1206          *  Phi* |   | new loop head with newly created phi.
1207          *   |   |
1208          *  Phi  |   | original, inverted condition chain
1209          *   |   |   |
1210          *   ?__/    |
1211          *
1212          */
1213         for (i = 0; i < ARR_LEN(head_df_loop); ++i) {
1214                 entry_edge head_out = head_df_loop[i];
1215
1216                 /* Construct ssa for assignments in the condition chain. */
1217                 ir_node *pred, *cppred, *block, *cpblock;
1218
1219                 pred = head_out.pred;
1220                 cppred = get_inversion_copy(pred);
1221                 assert(cppred && pred);
1222                 block = get_nodes_block(pred);
1223                 cpblock = get_nodes_block(cppred);
1224                 construct_ssa(block, pred, cpblock, cppred);
1225         }
1226
1227         /* 4. Remove the ins which are no backedges from the original condition chain
1228          *    as the cc is now subsequent to the body. */
1229         fix_head_inversion();
1230
1231         /* 5. Remove the backedges of the copied condition chain,
1232          *    because it is going to be the new 'head' in advance to the loop. */
1233         fix_copy_inversion();
1234
1235 }
1236
1237 /* Performs loop inversion of cur_loop if possible and reasonable. */
1238 static void loop_inversion(ir_graph *irg)
1239 {
1240         int      loop_depth;
1241         unsigned max_loop_nodes = opt_params.max_loop_size;
1242         unsigned max_loop_nodes_adapted;
1243         int      depth_adaption = opt_params.depth_adaption;
1244
1245         bool do_inversion = true;
1246
1247         /* Depth of 0 is the procedure and 1 a topmost loop. */
1248         loop_depth = get_loop_depth(cur_loop) - 1;
1249
1250         /* Calculating in per mil. */
1251         max_loop_nodes_adapted = get_max_nodes_adapted(loop_depth);
1252
1253         DB((dbg, LEVEL_1, "max_nodes: %d\nmax_nodes_adapted %d at depth of %d (adaption %d)\n",
1254                         max_loop_nodes, max_loop_nodes_adapted, loop_depth, depth_adaption));
1255
1256         if (loop_info.nodes == 0)
1257                 return;
1258
1259         if (loop_info.nodes > max_loop_nodes) {
1260                 /* Only for stats */
1261                 DB((dbg, LEVEL_1, "Nodes %d > allowed nodes %d\n",
1262                         loop_info.nodes, loop_depth, max_loop_nodes));
1263                 ++stats.too_large;
1264                 /* no RETURN */
1265                 /* Adaption might change it */
1266         }
1267
1268         /* Limit processing to loops smaller than given parameter. */
1269         if (loop_info.nodes > max_loop_nodes_adapted) {
1270                 DB((dbg, LEVEL_1, "Nodes %d > allowed nodes (depth %d adapted) %d\n",
1271                         loop_info.nodes, loop_depth, max_loop_nodes_adapted));
1272                 ++stats.too_large_adapted;
1273                 return;
1274         }
1275
1276         if (loop_info.calls > opt_params.allowed_calls) {
1277                 DB((dbg, LEVEL_1, "Calls %d > allowed calls %d\n",
1278                         loop_info.calls, opt_params.allowed_calls));
1279                 ++stats.calls_limit;
1280                 return;
1281         }
1282
1283         /*inversion_head_node_limit = INT_MAX;*/
1284         ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK);
1285
1286         /* Reset block marks.
1287          * We use block marks to flag blocks of the original condition chain. */
1288         irg_walk_graph(irg, reset_block_mark, NULL, NULL);
1289
1290         /*loop_info.blocks = get_loop_n_blocks(cur_loop);*/
1291         cond_chain_entries = NEW_ARR_F(entry_edge, 0);
1292         head_df_loop = NEW_ARR_F(entry_edge, 0);
1293
1294         /*head_inversion_node_count = 0;*/
1295         inversion_blocks_in_cc = 0;
1296
1297         /* Use phase to keep copy of nodes from the condition chain. */
1298         ir_nodemap_init(&map, irg);
1299         obstack_init(&obst);
1300
1301         /* Search for condition chains and temporarily save the blocks in an array. */
1302         cc_blocks = NEW_ARR_F(ir_node *, 0);
1303         inc_irg_visited(irg);
1304         find_condition_chain(loop_head);
1305
1306         unmark_not_allowed_cc_blocks();
1307         DEL_ARR_F(cc_blocks);
1308
1309         /* Condition chain too large.
1310          * Loop should better be small enough to fit into the cache. */
1311         /* TODO Of course, we should take a small enough cc in the first place,
1312          * which is not that simple. (bin packing)  */
1313         if (loop_info.cc_size > opt_params.max_cc_size) {
1314                 ++stats.cc_limit_reached;
1315
1316                 do_inversion = false;
1317
1318                 /* Unmark cc blocks except the head.
1319                  * Invert head only for possible unrolling. */
1320                 unmark_cc_blocks();
1321         }
1322
1323         /* We also catch endless loops here,
1324          * because they do not have a condition chain. */
1325         if (inversion_blocks_in_cc < 1) {
1326                 do_inversion = false;
1327                 DB((dbg, LEVEL_3,
1328                         "Loop contains %d (less than 1) invertible blocks => No Inversion done.\n",
1329                         inversion_blocks_in_cc));
1330         }
1331
1332         if (do_inversion) {
1333                 cur_head_outs = NEW_ARR_F(entry_edge, 0);
1334
1335                 /* Get all edges pointing into the condition chain. */
1336                 irg_walk_graph(irg, get_head_outs, NULL, NULL);
1337
1338                 /* Do the inversion */
1339                 inversion_walk(irg, cur_head_outs);
1340
1341                 DEL_ARR_F(cur_head_outs);
1342
1343                 /* Duplicated blocks changed doms */
1344                 clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE
1345                                    | IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO);
1346
1347                 ++stats.inverted;
1348         }
1349
1350         /* free */
1351         obstack_free(&obst, NULL);
1352         ir_nodemap_destroy(&map);
1353         DEL_ARR_F(cond_chain_entries);
1354         DEL_ARR_F(head_df_loop);
1355
1356         ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK);
1357 }
1358
1359 /* Fix the original loop_heads ins for invariant unrolling case. */
1360 static void unrolling_fix_loop_head_inv(void)
1361 {
1362         ir_node *ins[2];
1363         ir_node *phi;
1364         ir_node *proj = new_Proj(loop_info.duff_cond, mode_X, 0);
1365         ir_node *head_pred = get_irn_n(loop_head, loop_info.be_src_pos);
1366         ir_node *loop_condition = get_unroll_copy(head_pred, unroll_nr - 1);
1367
1368         /* Original loop_heads ins are:
1369          * duff block and the own backedge */
1370
1371         ins[0] = loop_condition;
1372         ins[1] = proj;
1373         set_irn_in(loop_head, 2, ins);
1374         DB((dbg, LEVEL_4, "Rewire ins of block loophead %N to pred %N and duffs entry %N \n" , loop_head, ins[0], ins[1]));
1375
1376         for_each_phi(loop_head, phi) {
1377                 ir_node *pred = get_irn_n(phi, loop_info.be_src_pos);
1378                 /* TODO we think it is a phi, but for Mergesort it is not the case.*/
1379
1380                 ir_node *last_pred = get_unroll_copy(pred, unroll_nr - 1);
1381
1382                 ins[0] = last_pred;
1383                 ins[1] = (ir_node*)get_irn_link(phi);
1384                 set_irn_in(phi, 2, ins);
1385                 DB((dbg, LEVEL_4, "Rewire ins of loophead phi %N to pred %N and duffs entry %N \n" , phi, ins[0], ins[1]));
1386         }
1387 }
1388
1389 /* Removes previously created phis with only 1 in. */
1390 static void correct_phis(ir_node *node, void *env)
1391 {
1392         (void)env;
1393
1394         if (is_Phi(node) && get_irn_arity(node) == 1) {
1395                 ir_node *exch;
1396                 ir_node *in[1];
1397
1398                 in[0] = get_irn_n(node, 0);
1399
1400                 exch = new_rd_Phi(get_irn_dbg_info(node),
1401                     get_nodes_block(node), 1, in,
1402                         get_irn_mode(node));
1403
1404                 exchange(node, exch);
1405         }
1406 }
1407
1408 /* Unrolling: Rewire floating copies. */
1409 static void place_copies(int copies)
1410 {
1411         ir_node *loophead = loop_head;
1412         size_t i;
1413         int c;
1414         int be_src_pos = loop_info.be_src_pos;
1415
1416         /* Serialize loops by fixing their head ins.
1417          * Processed are the copies.
1418          * The original loop is done after that, to keep backedge infos. */
1419         for (c = 0; c < copies; ++c) {
1420                 ir_node *upper = get_unroll_copy(loophead, c);
1421                 ir_node *lower = get_unroll_copy(loophead, c + 1);
1422                 ir_node *phi;
1423                 ir_node *topmost_be_block = get_nodes_block(get_irn_n(loophead, be_src_pos));
1424
1425                 /* Important: get the preds first and then their copy. */
1426                 ir_node *upper_be_block = get_unroll_copy(topmost_be_block, c);
1427                 ir_node *new_jmp = new_r_Jmp(upper_be_block);
1428                 DB((dbg, LEVEL_5, " place_copies upper %N lower %N\n", upper, lower));
1429
1430                 DB((dbg, LEVEL_5, "topmost be block %N \n", topmost_be_block));
1431
1432                 if (loop_info.unroll_kind == constant) {
1433                         ir_node *ins[1];
1434                         ins[0] = new_jmp;
1435                         set_irn_in(lower, 1, ins);
1436
1437                         for_each_phi(loophead, phi) {
1438                                 ir_node *topmost_def = get_irn_n(phi, be_src_pos);
1439                                 ir_node *upper_def = get_unroll_copy(topmost_def, c);
1440                                 ir_node *lower_phi = get_unroll_copy(phi, c + 1);
1441
1442                                 /* It is possible, that the value used
1443                                  * in the OWN backedge path is NOT defined in this loop. */
1444                                 if (is_in_loop(topmost_def))
1445                                         ins[0] = upper_def;
1446                                 else
1447                                         ins[0] = topmost_def;
1448
1449                                 set_irn_in(lower_phi, 1, ins);
1450                                 /* Need to replace phis with 1 in later. */
1451                         }
1452                 } else {
1453                         /* Invariant case */
1454                         /* Every node has 2 ins. One from the duff blocks
1455                          * and one from the previously unrolled loop. */
1456                         ir_node *ins[2];
1457                         /* Calculate corresponding projection of mod result for this copy c */
1458                         ir_node *proj = new_Proj(loop_info.duff_cond, mode_X, unroll_nr - c - 1);
1459                         DB((dbg, LEVEL_4, "New duff proj %N\n" , proj));
1460
1461                         ins[0] = new_jmp;
1462                         ins[1] = proj;
1463                         set_irn_in(lower, 2, ins);
1464                         DB((dbg, LEVEL_4, "Rewire ins of Block %N to pred %N and duffs entry %N \n" , lower, ins[0], ins[1]));
1465
1466                         for_each_phi(loophead, phi) {
1467                                 ir_node *topmost_phi_pred = get_irn_n(phi, be_src_pos);
1468                                 ir_node *upper_phi_pred;
1469                                 ir_node *lower_phi;
1470                                 ir_node *duff_phi;
1471
1472                                 lower_phi = get_unroll_copy(phi, c + 1);
1473                                 duff_phi = (ir_node*)get_irn_link(phi);
1474                                 DB((dbg, LEVEL_4, "DD Link of %N is %N\n" , phi, duff_phi));
1475
1476                                 /*  */
1477                                 if (is_in_loop(topmost_phi_pred)) {
1478                                         upper_phi_pred = get_unroll_copy(topmost_phi_pred, c);
1479                                 } else {
1480                                         upper_phi_pred = topmost_phi_pred;
1481                                 }
1482
1483                                 ins[0] = upper_phi_pred;
1484                                 ins[1] = duff_phi;
1485                                 set_irn_in(lower_phi, 2, ins);
1486                                 DB((dbg, LEVEL_4, "Rewire ins of %N to pred %N and duffs entry %N \n" , lower_phi, ins[0], ins[1]));
1487                         }
1488                 }
1489         }
1490
1491         /* Reconnect last copy. */
1492         for (i = 0; i < ARR_LEN(loop_entries); ++i) {
1493                 entry_edge edge = loop_entries[i];
1494                 /* Last copy is at the bottom */
1495                 ir_node *new_pred = get_unroll_copy(edge.pred, copies);
1496                 set_irn_n(edge.node, edge.pos, new_pred);
1497         }
1498
1499         /* Fix original loops head.
1500          * Done in the end, as ins and be info were needed before. */
1501         if (loop_info.unroll_kind == constant) {
1502                 ir_node *phi;
1503                 ir_node *head_pred = get_irn_n(loop_head, be_src_pos);
1504                 ir_node *loop_condition = get_unroll_copy(head_pred, unroll_nr - 1);
1505
1506                 set_irn_n(loop_head, loop_info.be_src_pos, loop_condition);
1507
1508                 for_each_phi(loop_head, phi) {
1509                         ir_node *pred = get_irn_n(phi, be_src_pos);
1510                         ir_node *last_pred;
1511
1512                         /* It is possible, that the value used
1513                          * in the OWN backedge path is NOT assigned in this loop. */
1514                         if (is_in_loop(pred))
1515                                 last_pred = get_unroll_copy(pred, copies);
1516                         else
1517                                 last_pred = pred;
1518                         set_irn_n(phi, be_src_pos, last_pred);
1519                 }
1520
1521         } else {
1522                 unrolling_fix_loop_head_inv();
1523         }
1524 }
1525
1526 /* Copies the cur_loop several times. */
1527 static void copy_loop(entry_edge *cur_loop_outs, int copies)
1528 {
1529         int c;
1530
1531         ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
1532
1533         for (c = 0; c < copies; ++c) {
1534                 size_t i;
1535
1536                 inc_irg_visited(current_ir_graph);
1537
1538                 DB((dbg, LEVEL_5, "         ### Copy_loop  copy nr: %d ###\n", c));
1539                 for (i = 0; i < ARR_LEN(cur_loop_outs); ++i) {
1540                         entry_edge entry = cur_loop_outs[i];
1541                         ir_node *pred = get_irn_n(entry.node, entry.pos);
1542
1543                         copy_walk_n(pred, is_in_loop, c + 1);
1544                 }
1545         }
1546
1547         ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
1548 }
1549
1550
1551 /* Creates a new phi from the given phi node omitting own bes,
1552  * using be_block as supplier of backedge informations. */
1553 static ir_node *clone_phis_sans_bes(ir_node *phi, ir_node *be_block, ir_node *dest_block)
1554 {
1555         ir_node **ins;
1556         int i, c = 0;
1557         ir_node *newphi;
1558
1559         int const arity = get_Phi_n_preds(phi);
1560         assert(arity == get_Block_n_cfgpreds(be_block));
1561
1562         ins = NEW_ARR_F(ir_node *, arity);
1563         for (i = 0; i < arity; ++i) {
1564                 if (! is_own_backedge(be_block, i)) {
1565                         ins[c] = get_irn_n(phi, i);
1566                         ++c;
1567                 }
1568         }
1569
1570         newphi = new_r_Phi(dest_block, c, ins, get_irn_mode(phi));
1571
1572         set_irn_link(phi, newphi);
1573         DB((dbg, LEVEL_4, "Linking for duffs device %N to %N\n", phi, newphi));
1574
1575         return newphi;
1576 }
1577
1578 /* Creates a new block from the given block node omitting own bes,
1579  * using be_block as supplier of backedge informations. */
1580 static ir_node *clone_block_sans_bes(ir_node *node, ir_node *be_block)
1581 {
1582         int i, c = 0;
1583         ir_node **ins;
1584
1585         int const arity = get_Block_n_cfgpreds(node);
1586         assert(arity == get_irn_arity(be_block));
1587
1588         NEW_ARR_A(ir_node *, ins, arity);
1589         for (i = 0; i < arity; ++i) {
1590                 if (! is_own_backedge(be_block, i)) {
1591                         ins[c] = get_irn_n(node, i);
1592                         ++c;
1593                 }
1594         }
1595
1596         return new_Block(c, ins);
1597 }
1598
1599 /* Creates a structure to calculate absolute value of node op.
1600  * Returns mux node with absolute value. */
1601 static ir_node *new_Abs(ir_node *op, ir_mode *mode)
1602 {
1603   ir_graph *irg      = get_irn_irg(op);
1604   ir_node  *block    = get_nodes_block(op);
1605   ir_node  *zero     = new_r_Const(irg, get_mode_null(mode));
1606   ir_node  *cmp      = new_r_Cmp(block, op, zero, ir_relation_less);
1607   ir_node  *minus_op = new_r_Minus(block, op, mode);
1608   ir_node  *mux      = new_r_Mux(block, cmp, op, minus_op, mode);
1609
1610   return mux;
1611 }
1612
1613
1614 /* Creates blocks for duffs device, using previously obtained
1615  * informations about the iv.
1616  * TODO split */
1617 static void create_duffs_block(void)
1618 {
1619         ir_mode *mode;
1620
1621         ir_node *block1, *count_block, *duff_block;
1622         ir_node *ems, *ems_mod, *ems_div, *ems_mod_proj, *cmp_null,
1623                 *ems_mode_cond, *x_true, *x_false, *const_null;
1624         ir_node *true_val, *false_val;
1625         ir_node *ins[2];
1626
1627         ir_node *duff_mod, *proj, *cond;
1628
1629         ir_node *count, *correction, *unroll_c;
1630         ir_node *cmp_bad_count, *good_count, *bad_count, *count_phi, *bad_count_neg;
1631         ir_node *phi;
1632
1633         mode = get_irn_mode(loop_info.end_val);
1634         const_null = new_Const(get_mode_null(mode));
1635
1636         /* TODO naming
1637          * 1. Calculate first approach to count.
1638          *    Condition: (end - start) % step == 0 */
1639         block1 = clone_block_sans_bes(loop_head, loop_head);
1640         DB((dbg, LEVEL_4, "Duff block 1 %N\n", block1));
1641
1642         /* Create loop entry phis in first duff block
1643          * as it becomes the loops preheader */
1644         for_each_phi(loop_head, phi) {
1645                 /* Returns phis pred if phi would have arity 1*/
1646                 ir_node *new_phi = clone_phis_sans_bes(phi, loop_head, block1);
1647
1648                 DB((dbg, LEVEL_4, "HEAD %N phi %N\n", loop_head, phi));
1649                 DB((dbg, LEVEL_4, "BLOCK1 %N phi %N\n", block1, new_phi));
1650         }
1651
1652         ems = new_r_Sub(block1, loop_info.end_val, loop_info.start_val,
1653                 get_irn_mode(loop_info.end_val));
1654                 DB((dbg, LEVEL_4, "BLOCK1 sub %N\n", ems));
1655
1656
1657         ems = new_Sub(loop_info.end_val, loop_info.start_val,
1658                 get_irn_mode(loop_info.end_val));
1659
1660         DB((dbg, LEVEL_4, "mod ins %N %N\n", ems, loop_info.step));
1661         ems_mod = new_r_Mod(block1,
1662                 new_NoMem(),
1663                 ems,
1664                 loop_info.step,
1665                 mode,
1666                 op_pin_state_pinned);
1667         ems_div = new_r_Div(block1,
1668                 new_NoMem(),
1669                 ems,
1670                 loop_info.step,
1671                 mode,
1672                 op_pin_state_pinned);
1673
1674         DB((dbg, LEVEL_4, "New module node %N\n", ems_mod));
1675
1676         ems_mod_proj = new_r_Proj(ems_mod, mode_Iu, pn_Mod_res);
1677         cmp_null = new_r_Cmp(block1, ems_mod_proj, const_null, ir_relation_less);
1678         ems_mode_cond = new_r_Cond(block1, cmp_null);
1679
1680         /* ems % step == 0 */
1681         x_true = new_r_Proj(ems_mode_cond, mode_X, pn_Cond_true);
1682         /* ems % step != 0 */
1683         x_false = new_r_Proj(ems_mode_cond, mode_X, pn_Cond_false);
1684
1685         /* 2. Second block.
1686          * Assures, duffs device receives a valid count.
1687          * Condition:
1688          *     decreasing: count < 0
1689          *     increasing: count > 0
1690          */
1691         ins[0] = x_true;
1692         ins[1] = x_false;
1693
1694         count_block = new_Block(2, ins);
1695         DB((dbg, LEVEL_4, "Duff block 2 %N\n", count_block));
1696
1697
1698         /* Increase loop-taken-count depending on the loop condition
1699          * uses the latest iv to compare to. */
1700         if (loop_info.latest_value == 1) {
1701                 /* ems % step == 0 :  +0 */
1702                 true_val = new_Const(get_mode_null(mode));
1703                 /* ems % step != 0 :  +1 */
1704                 false_val = new_Const(get_mode_one(mode));
1705         } else {
1706                 ir_tarval *tv_two = new_tarval_from_long(2, mode);
1707                 /* ems % step == 0 :  +1 */
1708                 true_val = new_Const(get_mode_one(mode));
1709                 /* ems % step != 0 :  +2 */
1710                 false_val = new_Const(tv_two);
1711         }
1712
1713         ins[0] = true_val;
1714         ins[1] = false_val;
1715
1716         correction = new_r_Phi(count_block, 2, ins, mode);
1717
1718         count = new_r_Proj(ems_div, mode, pn_Div_res);
1719
1720         /* (end - start) / step  +  correction */
1721         count = new_Add(count, correction, mode);
1722
1723         /* We preconditioned the loop to be tail-controlled.
1724          * So, if count is something 'wrong' like 0,
1725          * negative/positive (depending on step direction),
1726          * we may take the loop once (tail-contr.) and leave it
1727          * to the existing condition, to break; */
1728
1729         /* Depending on step direction, we have to check for > or < 0 */
1730         if (loop_info.decreasing == 1) {
1731                 cmp_bad_count = new_r_Cmp(count_block, count, const_null,
1732                                           ir_relation_less);
1733         } else {
1734                 cmp_bad_count = new_r_Cmp(count_block, count, const_null,
1735                                           ir_relation_greater);
1736         }
1737
1738         bad_count_neg = new_r_Cond(count_block, cmp_bad_count);
1739         good_count = new_Proj(bad_count_neg, mode_X, pn_Cond_true);
1740         bad_count = new_Proj(ems_mode_cond, mode_X, pn_Cond_false);
1741
1742         /* 3. Duff Block
1743          *    Contains module to decide which loop to start from. */
1744
1745         ins[0] = good_count;
1746         ins[1] = bad_count;
1747         duff_block = new_Block(2, ins);
1748         DB((dbg, LEVEL_4, "Duff block 3 %N\n", duff_block));
1749
1750         /* Get absolute value */
1751         ins[0] = new_Abs(count, mode);
1752         /* Manually feed the aforementioned count = 1 (bad case)*/
1753         ins[1] = new_Const(get_mode_one(mode));
1754         count_phi = new_r_Phi(duff_block, 2, ins, mode);
1755
1756         unroll_c = new_Const(new_tarval_from_long((long)unroll_nr, mode));
1757
1758         /* count % unroll_nr */
1759         duff_mod = new_r_Mod(duff_block,
1760                 new_NoMem(),
1761                 count_phi,
1762                 unroll_c,
1763                 mode,
1764                 op_pin_state_pinned);
1765
1766
1767         proj = new_Proj(duff_mod, mode, pn_Mod_res);
1768         /* condition does NOT create itself in the block of the proj! */
1769         cond = new_r_Cond(duff_block, proj);
1770
1771         loop_info.duff_cond = cond;
1772 }
1773
1774 /* Returns 1 if given node is not in loop,
1775  * or if it is a phi of the loop head with only loop invariant defs.
1776  */
1777 static unsigned is_loop_invariant_def(ir_node *node)
1778 {
1779         int i;
1780
1781         if (! is_in_loop(node)) {
1782                 DB((dbg, LEVEL_4, "Not in loop %N\n", node));
1783                 /* || is_Const(node) || is_SymConst(node)) {*/
1784                 return 1;
1785         }
1786
1787         /* If this is a phi of the loophead shared by more than 1 loop,
1788          * we need to check if all defs are not in the loop.  */
1789         if (is_Phi(node)) {
1790                 ir_node *block;
1791                 block = get_nodes_block(node);
1792
1793                 /* To prevent unexpected situations. */
1794                 if (block != loop_head) {
1795                         return 0;
1796                 }
1797
1798                 for (i = 0; i < get_irn_arity(node); ++i) {
1799                         /* Check if all bes are just loopbacks. */
1800                         if (is_own_backedge(block, i) && get_irn_n(node, i) != node)
1801                                 return 0;
1802                 }
1803                 DB((dbg, LEVEL_4, "invar %N\n", node));
1804                 return 1;
1805         }
1806         DB((dbg, LEVEL_4, "Not invar %N\n", node));
1807
1808         return 0;
1809 }
1810
1811 /* Returns 1 if one pred of node is invariant and the other is not.
1812  * invar_pred and other are set analogously. */
1813 static unsigned get_invariant_pred(ir_node *node, ir_node **invar_pred, ir_node **other)
1814 {
1815         ir_node *pred0 = get_irn_n(node, 0);
1816         ir_node *pred1 = get_irn_n(node, 1);
1817
1818         *invar_pred = NULL;
1819         *other = NULL;
1820
1821         if (is_loop_invariant_def(pred0)) {
1822                 DB((dbg, LEVEL_4, "pred0 invar %N\n", pred0));
1823                 *invar_pred = pred0;
1824                 *other = pred1;
1825         }
1826
1827         if (is_loop_invariant_def(pred1)) {
1828                 DB((dbg, LEVEL_4, "pred1 invar %N\n", pred1));
1829
1830                 if (*invar_pred != NULL) {
1831                         /* RETURN. We do not want both preds to be invariant. */
1832                         return 0;
1833                 }
1834
1835                 *other = pred0;
1836                 *invar_pred = pred1;
1837                 return 1;
1838         } else {
1839                 DB((dbg, LEVEL_4, "pred1 not invar %N\n", pred1));
1840
1841                 if (*invar_pred != NULL)
1842                         return 1;
1843                 else
1844                         return 0;
1845         }
1846 }
1847
1848 /* Starts from a phi that may belong to an iv.
1849  * If an add forms a loop with iteration_phi,
1850  * and add uses a constant, 1 is returned
1851  * and 'start' as well as 'add' are sane. */
1852 static unsigned get_start_and_add(ir_node *iteration_phi, unrolling_kind_flag role)
1853 {
1854         int i;
1855         ir_node *found_add = loop_info.add;
1856         int arity = get_irn_arity(iteration_phi);
1857
1858         DB((dbg, LEVEL_4, "Find start and add from %N\n", iteration_phi));
1859
1860         for (i = 0; i < arity; ++i) {
1861
1862                 /* Find start_val which needs to be pred of the iteration_phi.
1863                  * If start_val already known, sanity check. */
1864                 if (!is_backedge(get_nodes_block(loop_info.iteration_phi), i)) {
1865                         ir_node *found_start_val = get_irn_n(loop_info.iteration_phi, i);
1866
1867                         DB((dbg, LEVEL_4, "found_start_val %N\n", found_start_val));
1868
1869                         /* We already found a start_val it has to be always the same. */
1870                         if (loop_info.start_val && found_start_val != loop_info.start_val)
1871                                 return 0;
1872
1873                         if ((role == constant) && !(is_SymConst(found_start_val) || is_Const(found_start_val)))
1874                                         return 0;
1875                         else if((role == constant) && !(is_loop_invariant_def(found_start_val)))
1876                                         return 0;
1877
1878                         loop_info.start_val = found_start_val;
1879                 }
1880
1881                 /* The phi has to be in the loop head.
1882                  * Follow all own backedges. Every value supplied from these preds of the phi
1883                  * needs to origin from the same add. */
1884                 if (is_own_backedge(get_nodes_block(loop_info.iteration_phi), i)) {
1885                         ir_node *new_found = get_irn_n(loop_info.iteration_phi,i);
1886
1887                         DB((dbg, LEVEL_4, "is add? %N\n", new_found));
1888
1889                         if (! (is_Add(new_found) || is_Sub(new_found)) || (found_add && found_add != new_found))
1890                                 return 0;
1891                         else
1892                                 found_add = new_found;
1893                 }
1894         }
1895
1896         loop_info.add = found_add;
1897
1898         return 1;
1899 }
1900
1901
1902 /* Returns 1 if one pred of node is a const value and the other is not.
1903  * const_pred and other are set analogously. */
1904 static unsigned get_const_pred(ir_node *node, ir_node **const_pred, ir_node **other)
1905 {
1906         ir_node *pred0 = get_irn_n(node, 0);
1907         ir_node *pred1 = get_irn_n(node, 1);
1908
1909         DB((dbg, LEVEL_4, "Checking for constant pred of %N\n", node));
1910
1911         *const_pred = NULL;
1912         *other = NULL;
1913
1914         /*DB((dbg, LEVEL_4, "is %N const\n", pred0));*/
1915         if (is_Const(pred0) || is_SymConst(pred0)) {
1916                 *const_pred = pred0;
1917                 *other = pred1;
1918         }
1919
1920         /*DB((dbg, LEVEL_4, "is %N const\n", pred1));*/
1921         if (is_Const(pred1) || is_SymConst(pred1)) {
1922                 if (*const_pred != NULL) {
1923                         /* RETURN. We do not want both preds to be constant. */
1924                         return 0;
1925                 }
1926
1927                 *other = pred0;
1928                 *const_pred = pred1;
1929         }
1930
1931         if (*const_pred == NULL)
1932                 return 0;
1933         else
1934                 return 1;
1935 }
1936
1937 /* Returns 1 if loop exits within 2 steps of the iv.
1938  * Norm_proj means we do not exit the loop.*/
1939 static unsigned simulate_next(ir_tarval **count_tar,
1940                 ir_tarval *stepped, ir_tarval *step_tar, ir_tarval *end_tar,
1941                 ir_relation norm_proj)
1942 {
1943         ir_tarval *next;
1944
1945         DB((dbg, LEVEL_4, "Loop taken if (stepped)%ld %s (end)%ld ",
1946                                 get_tarval_long(stepped),
1947                                 get_relation_string((norm_proj)),
1948                                 get_tarval_long(end_tar)));
1949         DB((dbg, LEVEL_4, "comparing latest value %d\n", loop_info.latest_value));
1950
1951         /* If current iv does not stay in the loop,
1952          * this run satisfied the exit condition. */
1953         if (! (tarval_cmp(stepped, end_tar) & norm_proj))
1954                 return 1;
1955
1956         DB((dbg, LEVEL_4, "Result: (stepped)%ld IS %s (end)%ld\n",
1957                                 get_tarval_long(stepped),
1958                                 get_relation_string(tarval_cmp(stepped, end_tar)),
1959                                 get_tarval_long(end_tar)));
1960
1961         /* next step */
1962         if (is_Add(loop_info.add))
1963                 next = tarval_add(stepped, step_tar);
1964         else
1965                 /* sub */
1966                 next = tarval_sub(stepped, step_tar, get_irn_mode(loop_info.end_val));
1967
1968         DB((dbg, LEVEL_4, "Loop taken if %ld %s %ld ",
1969                                 get_tarval_long(next),
1970                                 get_relation_string(norm_proj),
1971                                 get_tarval_long(end_tar)));
1972         DB((dbg, LEVEL_4, "comparing latest value %d\n", loop_info.latest_value));
1973
1974         /* Increase steps. */
1975         *count_tar = tarval_add(*count_tar, get_tarval_one(get_tarval_mode(*count_tar)));
1976
1977         /* Next has to fail the loop condition, or we will never exit. */
1978         if (! (tarval_cmp(next, end_tar) & norm_proj))
1979                 return 1;
1980         else
1981                 return 0;
1982 }
1983
1984 /* Check if loop meets requirements for a 'simple loop':
1985  * - Exactly one cf out
1986  * - Allowed calls
1987  * - Max nodes after unrolling
1988  * - tail-controlled
1989  * - exactly one be
1990  * - cmp
1991  * Returns Projection of cmp node or NULL; */
1992 static ir_node *is_simple_loop(void)
1993 {
1994         int arity, i;
1995         ir_node *loop_block, *exit_block, *projx, *cond, *cmp;
1996
1997         /* Maximum of one condition, and no endless loops. */
1998         if (loop_info.cf_outs != 1)
1999                 return NULL;
2000
2001         DB((dbg, LEVEL_4, "1 loop exit\n"));
2002
2003         /* Calculate maximum unroll_nr keeping node count below limit. */
2004         loop_info.max_unroll = (int)((double)opt_params.max_unrolled_loop_size / (double)loop_info.nodes);
2005         if (loop_info.max_unroll < 2) {
2006                 ++stats.too_large;
2007                 return NULL;
2008         }
2009
2010         DB((dbg, LEVEL_4, "maximum unroll factor %u, to not exceed node limit \n",
2011                 opt_params.max_unrolled_loop_size));
2012
2013         arity = get_irn_arity(loop_head);
2014         /* RETURN if we have more than 1 be. */
2015         /* Get my backedges without alien bes. */
2016         loop_block = NULL;
2017         for (i = 0; i < arity; ++i) {
2018                 ir_node *pred = get_irn_n(loop_head, i);
2019                 if (is_own_backedge(loop_head, i)) {
2020                         if (loop_block)
2021                                 /* Our simple loops may have only one backedge. */
2022                                 return NULL;
2023                         else {
2024                                 loop_block = get_nodes_block(pred);
2025                                 loop_info.be_src_pos = i;
2026                         }
2027                 }
2028         }
2029
2030         DB((dbg, LEVEL_4, "loop has 1 own backedge.\n"));
2031
2032         exit_block = get_nodes_block(loop_info.cf_out.pred);
2033         /* The loop has to be tail-controlled.
2034          * This can be changed/improved,
2035          * but we would need a duff iv. */
2036         if (exit_block != loop_block)
2037                 return NULL;
2038
2039         DB((dbg, LEVEL_4, "tail-controlled loop.\n"));
2040
2041         /* find value on which loop exit depends */
2042         projx = loop_info.cf_out.pred;
2043         cond = get_irn_n(projx, 0);
2044         cmp = get_irn_n(cond, 0);
2045
2046         if (!is_Cmp(cmp))
2047                 return NULL;
2048
2049         DB((dbg, LEVEL_5, "projection is %s\n", get_relation_string(get_Cmp_relation(cmp))));
2050
2051         switch(get_Proj_proj(projx)) {
2052                 case pn_Cond_false:
2053                         loop_info.exit_cond = 0;
2054                         break;
2055                 case pn_Cond_true:
2056                         loop_info.exit_cond = 1;
2057                         break;
2058                 default:
2059                         panic("Cond Proj_proj other than true/false");
2060         }
2061
2062         DB((dbg, LEVEL_4, "Valid Cmp.\n"));
2063         return cmp;
2064 }
2065
2066 /* Returns 1 if all nodes are mode_Iu or mode_Is. */
2067 static unsigned are_mode_I(ir_node *n1, ir_node* n2, ir_node *n3)
2068 {
2069         ir_mode *m1 = get_irn_mode(n1);
2070         ir_mode *m2 = get_irn_mode(n2);
2071         ir_mode *m3 = get_irn_mode(n3);
2072
2073         if ((m1 == mode_Iu && m2 == mode_Iu && m3 == mode_Iu) ||
2074             (m1 == mode_Is && m2 == mode_Is && m3 == mode_Is))
2075                 return 1;
2076         else
2077                 return 0;
2078 }
2079
2080 /* Checks if cur_loop is a simple tail-controlled counting loop
2081  * with start and end value loop invariant, step constant. */
2082 static unsigned get_unroll_decision_invariant(void)
2083 {
2084
2085         ir_node   *projres, *loop_condition, *iteration_path;
2086         unsigned   success;
2087         ir_tarval *step_tar;
2088         ir_mode   *mode;
2089
2090
2091         /* RETURN if loop is not 'simple' */
2092         projres = is_simple_loop();
2093         if (projres == NULL)
2094                 return 0;
2095
2096         /* Use a minimal size for the invariant unrolled loop,
2097      * as duffs device produces overhead */
2098         if (loop_info.nodes < opt_params.invar_unrolling_min_size)
2099                 return 0;
2100
2101         loop_condition = get_irn_n(projres, 0);
2102
2103         success = get_invariant_pred(loop_condition, &loop_info.end_val, &iteration_path);
2104         DB((dbg, LEVEL_4, "pred invar %d\n", success));
2105
2106         if (! success)
2107                 return 0;
2108
2109         DB((dbg, LEVEL_4, "Invariant End_val %N, other %N\n", loop_info.end_val, iteration_path));
2110
2111         /* We may find the add or the phi first.
2112          * Until now we only have end_val. */
2113         if (is_Add(iteration_path) || is_Sub(iteration_path)) {
2114
2115                 loop_info.add = iteration_path;
2116                 DB((dbg, LEVEL_4, "Case 1: Got add %N (maybe not sane)\n", loop_info.add));
2117
2118                 /* Preds of the add should be step and the iteration_phi */
2119                 success = get_const_pred(loop_info.add, &loop_info.step, &loop_info.iteration_phi);
2120                 if (! success)
2121                         return 0;
2122
2123                 DB((dbg, LEVEL_4, "Got step %N\n", loop_info.step));
2124
2125                 if (! is_Phi(loop_info.iteration_phi))
2126                         return 0;
2127
2128                 DB((dbg, LEVEL_4, "Got phi %N\n", loop_info.iteration_phi));
2129
2130                 /* Find start_val.
2131                  * Does necessary sanity check of add, if it is already set.  */
2132                 success = get_start_and_add(loop_info.iteration_phi, invariant);
2133                 if (! success)
2134                         return 0;
2135
2136                 DB((dbg, LEVEL_4, "Got start A  %N\n", loop_info.start_val));
2137
2138         } else if (is_Phi(iteration_path)) {
2139                 ir_node *new_iteration_phi;
2140
2141                 loop_info.iteration_phi = iteration_path;
2142                 DB((dbg, LEVEL_4, "Case 2: Got phi %N\n", loop_info.iteration_phi));
2143
2144                 /* Find start_val and add-node.
2145                  * Does necessary sanity check of add, if it is already set.  */
2146                 success = get_start_and_add(loop_info.iteration_phi, invariant);
2147                 if (! success)
2148                         return 0;
2149
2150                 DB((dbg, LEVEL_4, "Got start B %N\n", loop_info.start_val));
2151                 DB((dbg, LEVEL_4, "Got add or sub %N\n", loop_info.add));
2152
2153                 success = get_const_pred(loop_info.add, &loop_info.step, &new_iteration_phi);
2154                 if (! success)
2155                         return 0;
2156
2157                 DB((dbg, LEVEL_4, "Got step (B) %N\n", loop_info.step));
2158
2159                 if (loop_info.iteration_phi != new_iteration_phi)
2160                         return 0;
2161
2162         } else {
2163                 return 0;
2164         }
2165
2166         mode = get_irn_mode(loop_info.end_val);
2167
2168         DB((dbg, LEVEL_4, "start %N, end %N, step %N\n",
2169                                 loop_info.start_val, loop_info.end_val, loop_info.step));
2170
2171         if (mode != mode_Is && mode != mode_Iu)
2172                 return 0;
2173
2174         /* TODO necessary? */
2175         if (!are_mode_I(loop_info.start_val, loop_info.step, loop_info.end_val))
2176                 return 0;
2177
2178         DB((dbg, LEVEL_4, "mode integer\n"));
2179
2180         step_tar = get_Const_tarval(loop_info.step);
2181
2182         if (tarval_is_null(step_tar)) {
2183                 /* TODO Might be worth a warning. */
2184                 return 0;
2185         }
2186
2187         DB((dbg, LEVEL_4, "step is not 0\n"));
2188
2189         create_duffs_block();
2190
2191         return loop_info.max_unroll;
2192 }
2193
2194 /* Returns unroll factor,
2195  * given maximum unroll factor and number of loop passes. */
2196 static unsigned get_preferred_factor_constant(ir_tarval *count_tar)
2197 {
2198         ir_tarval *tar_6, *tar_5, *tar_4, *tar_3, *tar_2;
2199         unsigned prefer;
2200         ir_mode *mode = get_irn_mode(loop_info.end_val);
2201
2202         tar_6 = new_tarval_from_long(6, mode);
2203         tar_5 = new_tarval_from_long(5, mode);
2204         tar_4 = new_tarval_from_long(4, mode);
2205         tar_3 = new_tarval_from_long(3, mode);
2206         tar_2 = new_tarval_from_long(2, mode);
2207
2208         /* loop passes % {6, 5, 4, 3, 2} == 0  */
2209         if (tarval_is_null(tarval_mod(count_tar, tar_6)))
2210                 prefer = 6;
2211         else if (tarval_is_null(tarval_mod(count_tar, tar_5)))
2212                 prefer = 5;
2213         else if (tarval_is_null(tarval_mod(count_tar, tar_4)))
2214                 prefer = 4;
2215         else if (tarval_is_null(tarval_mod(count_tar, tar_3)))
2216                 prefer = 3;
2217         else if (tarval_is_null(tarval_mod(count_tar, tar_2)))
2218                 prefer = 2;
2219         else {
2220                 /* gcd(max_unroll, count_tar) */
2221                 int a = loop_info.max_unroll;
2222                 int b = (int)get_tarval_long(count_tar);
2223                 int c;
2224
2225                 DB((dbg, LEVEL_4, "gcd of max_unroll %d and count_tar %d: ", a, b));
2226
2227                 do {
2228                 c = a % b;
2229                 a = b; b = c;
2230                 } while( c != 0);
2231
2232                 DB((dbg, LEVEL_4, "%d\n", a));
2233                 return a;
2234         }
2235
2236         DB((dbg, LEVEL_4, "preferred unroll factor %d\n", prefer));
2237
2238         /*
2239          * If our preference is greater than the allowed unroll factor
2240          * we either might reduce the preferred factor and prevent a duffs device block,
2241          * or create a duffs device block, from which in this case (constants only)
2242          * we know the startloop at compiletime.
2243          * The latter yields the following graphs.
2244          * but for code generation we would want to use graph A.
2245          * The graphs are equivalent. So, we can only reduce the preferred factor.
2246          * A)                   B)
2247          *     PreHead             PreHead
2248          *        |      ,--.         |   ,--.
2249          *         \ Loop1   \        Loop2   \
2250          *          \  |     |       /  |     |
2251          *           Loop2   /      / Loop1   /
2252          *           |   `--'      |      `--'
2253          */
2254
2255         if (prefer <= loop_info.max_unroll)
2256                 return prefer;
2257         else {
2258                 switch(prefer) {
2259                         case 6:
2260                                 if (loop_info.max_unroll >= 3)
2261                                         return 3;
2262                                 else if (loop_info.max_unroll >= 2)
2263                                         return 2;
2264                                 else
2265                                         return 0;
2266
2267                         case 4:
2268                                 if (loop_info.max_unroll >= 2)
2269                                         return 2;
2270                                 else
2271                                         return 0;
2272
2273                         default:
2274                                 return 0;
2275                 }
2276         }
2277 }
2278
2279 /* Check if cur_loop is a simple counting loop.
2280  * Start, step and end are constants.
2281  * TODO The whole constant case should use procedures similar to
2282  * the invariant case, as they are more versatile. */
2283 /* TODO split. */
2284 static unsigned get_unroll_decision_constant(void)
2285 {
2286         ir_node     *cmp, *iteration_path;
2287         unsigned     success, is_latest_val;
2288         ir_tarval   *start_tar, *end_tar, *step_tar, *diff_tar, *count_tar;
2289         ir_tarval   *stepped;
2290         ir_relation  proj_proj, norm_proj;
2291         ir_mode     *mode;
2292
2293         /* RETURN if loop is not 'simple' */
2294         cmp = is_simple_loop();
2295         if (cmp == NULL)
2296                 return 0;
2297
2298         /* One in of the loop condition needs to be loop invariant. => end_val
2299          * The other in is assigned by an add. => add
2300          * The add uses a loop invariant value => step
2301          * and a phi with a loop invariant start_val and the add node as ins.
2302
2303            ^   ^
2304            |   | .-,
2305            |   Phi |
2306                 \  |   |
2307           ^  Add   |
2308            \  | \__|
2309             cond
2310              /\
2311         */
2312
2313         success = get_const_pred(cmp, &loop_info.end_val, &iteration_path);
2314         if (! success)
2315                 return 0;
2316
2317         DB((dbg, LEVEL_4, "End_val %N, other %N\n", loop_info.end_val, iteration_path));
2318
2319         /* We may find the add or the phi first.
2320          * Until now we only have end_val. */
2321         if (is_Add(iteration_path) || is_Sub(iteration_path)) {
2322
2323                 /* We test against the latest value of the iv. */
2324                 is_latest_val = 1;
2325
2326                 loop_info.add = iteration_path;
2327                 DB((dbg, LEVEL_4, "Case 2: Got add %N (maybe not sane)\n", loop_info.add));
2328
2329                 /* Preds of the add should be step and the iteration_phi */
2330                 success = get_const_pred(loop_info.add, &loop_info.step, &loop_info.iteration_phi);
2331                 if (! success)
2332                         return 0;
2333
2334                 DB((dbg, LEVEL_4, "Got step %N\n", loop_info.step));
2335
2336                 if (! is_Phi(loop_info.iteration_phi))
2337                         return 0;
2338
2339                 DB((dbg, LEVEL_4, "Got phi %N\n", loop_info.iteration_phi));
2340
2341                 /* Find start_val.
2342                  * Does necessary sanity check of add, if it is already set.  */
2343                 success = get_start_and_add(loop_info.iteration_phi, constant);
2344                 if (! success)
2345                         return 0;
2346
2347                 DB((dbg, LEVEL_4, "Got start %N\n", loop_info.start_val));
2348
2349         } else if (is_Phi(iteration_path)) {
2350                 ir_node *new_iteration_phi;
2351
2352                 /* We compare with the value the iv had entering this run. */
2353                 is_latest_val = 0;
2354
2355                 loop_info.iteration_phi = iteration_path;
2356                 DB((dbg, LEVEL_4, "Case 1: Got phi %N \n", loop_info.iteration_phi));
2357
2358                 /* Find start_val and add-node.
2359                  * Does necessary sanity check of add, if it is already set.  */
2360                 success = get_start_and_add(loop_info.iteration_phi, constant);
2361                 if (! success)
2362                         return 0;
2363
2364                 DB((dbg, LEVEL_4, "Got start %N\n", loop_info.start_val));
2365                 DB((dbg, LEVEL_4, "Got add or sub %N\n", loop_info.add));
2366
2367                 success = get_const_pred(loop_info.add, &loop_info.step, &new_iteration_phi);
2368                 if (! success)
2369                         return 0;
2370
2371                 DB((dbg, LEVEL_4, "Got step %N\n", loop_info.step));
2372
2373                 if (loop_info.iteration_phi != new_iteration_phi)
2374                         return 0;
2375
2376         } else {
2377                 /* RETURN */
2378                 return 0;
2379         }
2380
2381         mode = get_irn_mode(loop_info.end_val);
2382
2383         DB((dbg, LEVEL_4, "start %N, end %N, step %N\n",
2384                                 loop_info.start_val, loop_info.end_val, loop_info.step));
2385
2386         if (mode != mode_Is && mode != mode_Iu)
2387                 return 0;
2388
2389         /* TODO necessary? */
2390         if (!are_mode_I(loop_info.start_val, loop_info.step, loop_info.end_val))
2391                 return 0;
2392
2393         DB((dbg, LEVEL_4, "mode integer\n"));
2394
2395         end_tar = get_Const_tarval(loop_info.end_val);
2396         start_tar = get_Const_tarval(loop_info.start_val);
2397         step_tar = get_Const_tarval(loop_info.step);
2398
2399         if (tarval_is_null(step_tar))
2400                 /* TODO Might be worth a warning. */
2401                 return 0;
2402
2403         DB((dbg, LEVEL_4, "step is not 0\n"));
2404
2405         if ((!tarval_is_negative(step_tar)) ^ (!is_Sub(loop_info.add)))
2406                 loop_info.decreasing = 1;
2407
2408         diff_tar = tarval_sub(end_tar, start_tar, mode);
2409
2410         /* We need at least count_tar steps to be close to end_val, maybe more.
2411          * No way, that we have gone too many steps.
2412          * This represents the 'latest value'.
2413          * (If condition checks against latest value, is checked later) */
2414         count_tar = tarval_div(diff_tar, step_tar);
2415
2416         /* Iv will not pass end_val (except overflows).
2417          * Nothing done, as it would yield to no advantage. */
2418         if (tarval_is_negative(count_tar)) {
2419                 DB((dbg, LEVEL_4, "Loop is endless or never taken."));
2420                 /* TODO Might be worth a warning. */
2421                 return 0;
2422         }
2423
2424         ++stats.u_simple_counting_loop;
2425
2426         loop_info.latest_value = is_latest_val;
2427
2428         /* TODO split here
2429         if (! is_simple_counting_loop(&count_tar))
2430                 return 0;
2431         */
2432
2433         /* stepped can be negative, if step < 0 */
2434         stepped = tarval_mul(count_tar, step_tar);
2435
2436         /* step as close to end_val as possible, */
2437         /* |stepped| <= |end_tar|, and dist(stepped, end_tar) is smaller than a step. */
2438         if (is_Sub(loop_info.add))
2439                 stepped = tarval_sub(start_tar, stepped, mode_Is);
2440         else
2441                 stepped = tarval_add(start_tar, stepped);
2442
2443         DB((dbg, LEVEL_4, "stepped to %ld\n", get_tarval_long(stepped)));
2444
2445         proj_proj = get_Cmp_relation(cmp);
2446         /* Assure that norm_proj is the stay-in-loop case. */
2447         if (loop_info.exit_cond == 1)
2448                 norm_proj = get_negated_relation(proj_proj);
2449         else
2450                 norm_proj = proj_proj;
2451
2452         DB((dbg, LEVEL_4, "normalized projection %s\n", get_relation_string(norm_proj)));
2453         /* Executed at most once (stay in counting loop if a Eq b) */
2454         if (norm_proj == ir_relation_equal)
2455                 /* TODO Might be worth a warning. */
2456                 return 0;
2457
2458         /* calculates next values and increases count_tar according to it */
2459         success = simulate_next(&count_tar, stepped, step_tar, end_tar, norm_proj);
2460         if (! success)
2461                 return 0;
2462
2463         /* We run loop once more, if we compare to the
2464          * not yet in-/decreased iv. */
2465         if (is_latest_val == 0) {
2466                 DB((dbg, LEVEL_4, "condition uses not latest iv value\n"));
2467                 count_tar = tarval_add(count_tar, get_tarval_one(mode));
2468         }
2469
2470         DB((dbg, LEVEL_4, "loop taken %ld times\n", get_tarval_long(count_tar)));
2471
2472         /* Assure the loop is taken at least 1 time. */
2473         if (tarval_is_null(count_tar)) {
2474                 /* TODO Might be worth a warning. */
2475                 return 0;
2476         }
2477
2478         loop_info.count_tar = count_tar;
2479         return get_preferred_factor_constant(count_tar);
2480 }
2481
2482 /**
2483  * Loop unrolling
2484  */
2485 static void unroll_loop(void)
2486 {
2487
2488         if (! (loop_info.nodes > 0))
2489                 return;
2490
2491         if (loop_info.nodes > opt_params.max_unrolled_loop_size) {
2492                 DB((dbg, LEVEL_2, "Nodes %d > allowed nodes %d\n",
2493                         loop_info.nodes, opt_params.max_unrolled_loop_size));
2494                 ++stats.too_large;
2495                 return;
2496         }
2497
2498         if (loop_info.calls > 0) {
2499                 DB((dbg, LEVEL_2, "Calls %d > allowed calls 0\n",
2500                         loop_info.calls));
2501                 ++stats.calls_limit;
2502                 return;
2503         }
2504
2505         unroll_nr = 0;
2506
2507         /* get_unroll_decision_constant and invariant are completely
2508          * independent for flexibility.
2509          * Some checks may be performed twice. */
2510
2511         /* constant case? */
2512         if (opt_params.allow_const_unrolling)
2513                 unroll_nr = get_unroll_decision_constant();
2514         if (unroll_nr > 1) {
2515                 loop_info.unroll_kind = constant;
2516
2517         } else {
2518                 /* invariant case? */
2519                 if (opt_params.allow_invar_unrolling)
2520                         unroll_nr = get_unroll_decision_invariant();
2521                 if (unroll_nr > 1)
2522                         loop_info.unroll_kind = invariant;
2523         }
2524
2525         DB((dbg, LEVEL_2, " *** Unrolling %d times ***\n", unroll_nr));
2526
2527         if (unroll_nr > 1) {
2528                 loop_entries = NEW_ARR_F(entry_edge, 0);
2529
2530                 /* Get loop outs */
2531                 irg_walk_graph(current_ir_graph, get_loop_entries, NULL, NULL);
2532
2533                 if (loop_info.unroll_kind == constant) {
2534                         if ((int)get_tarval_long(loop_info.count_tar) == unroll_nr)
2535                                 loop_info.needs_backedge = 0;
2536                         else
2537                                 loop_info.needs_backedge = 1;
2538                 } else {
2539                         loop_info.needs_backedge = 1;
2540                 }
2541
2542                 /* Use phase to keep copy of nodes from the condition chain. */
2543                 ir_nodemap_init(&map, current_ir_graph);
2544                 obstack_init(&obst);
2545
2546                 /* Copies the loop */
2547                 copy_loop(loop_entries, unroll_nr - 1);
2548
2549                 /* Line up the floating copies. */
2550                 place_copies(unroll_nr - 1);
2551
2552                 /* Remove phis with 1 in
2553                  * If there were no nested phis, this would not be necessary.
2554                  * Avoiding the creation in the first place
2555                  * leads to complex special cases. */
2556                 irg_walk_graph(current_ir_graph, correct_phis, NULL, NULL);
2557
2558                 if (loop_info.unroll_kind == constant)
2559                         ++stats.constant_unroll;
2560                 else
2561                         ++stats.invariant_unroll;
2562
2563                 clear_irg_properties(current_ir_graph, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
2564
2565                 DEL_ARR_F(loop_entries);
2566                 obstack_free(&obst, NULL);
2567                 ir_nodemap_destroy(&map);
2568         }
2569
2570 }
2571
2572 /* Analyzes the loop, and checks if size is within allowed range.
2573  * Decides if loop will be processed. */
2574 static void init_analyze(ir_graph *irg, ir_loop *loop)
2575 {
2576         cur_loop = loop;
2577
2578         loop_head       = NULL;
2579         loop_head_valid = true;
2580
2581         /* Reset loop info */
2582         memset(&loop_info, 0, sizeof(loop_info_t));
2583
2584         DB((dbg, LEVEL_1, "    >>>> current loop %ld <<<\n",
2585             get_loop_loop_nr(loop)));
2586
2587         /* Collect loop informations: head, node counts. */
2588         irg_walk_graph(irg, get_loop_info, NULL, NULL);
2589
2590         /* RETURN if there is no valid head */
2591         if (!loop_head || !loop_head_valid) {
2592                 DB((dbg, LEVEL_1,   "No valid loop head. Nothing done.\n"));
2593                 return;
2594         } else {
2595                 DB((dbg, LEVEL_1,   "Loophead: %N\n", loop_head));
2596         }
2597
2598         if (loop_info.branches > opt_params.max_branches) {
2599                 DB((dbg, LEVEL_1, "Branches %d > allowed branches %d\n",
2600                         loop_info.branches, opt_params.max_branches));
2601                 ++stats.calls_limit;
2602                 return;
2603         }
2604
2605         switch (loop_op) {
2606                 case loop_op_inversion:
2607                         loop_inversion(irg);
2608                         break;
2609
2610                 case loop_op_unrolling:
2611                         unroll_loop();
2612                         break;
2613
2614                 default:
2615                         panic("Loop optimization not implemented.");
2616         }
2617         DB((dbg, LEVEL_1, "       <<<< end of loop with node %ld >>>>\n",
2618             get_loop_loop_nr(loop)));
2619 }
2620
2621 /* Find innermost loops and add them to loops. */
2622 static void find_innermost_loop(ir_loop *loop)
2623 {
2624         bool   had_sons   = false;
2625         size_t n_elements = get_loop_n_elements(loop);
2626         size_t e;
2627
2628         for (e = 0; e < n_elements; ++e) {
2629                 loop_element element = get_loop_element(loop, e);
2630                 if (*element.kind == k_ir_loop) {
2631                         find_innermost_loop(element.son);
2632                         had_sons = true;
2633                 }
2634         }
2635
2636         if (!had_sons) {
2637                 ARR_APP1(ir_loop*, loops, loop);
2638         }
2639 }
2640
2641 static void set_loop_params(void)
2642 {
2643     opt_params.max_loop_size = 100;
2644     opt_params.depth_adaption = -50;
2645     opt_params.count_phi = true;
2646     opt_params.count_proj = false;
2647     opt_params.allowed_calls = 0;
2648
2649     opt_params.max_cc_size = 5;
2650
2651
2652     opt_params.allow_const_unrolling = true;
2653     opt_params.allow_invar_unrolling = false;
2654
2655     opt_params.invar_unrolling_min_size = 20;
2656     opt_params.max_unrolled_loop_size = 400;
2657     opt_params.max_branches = 9999;
2658 }
2659
2660 /* Assure preconditions are met and go through all loops. */
2661 void loop_optimization(ir_graph *irg)
2662 {
2663         ir_loop *loop;
2664         size_t   i;
2665         size_t   n_elements;
2666
2667         assure_irg_properties(irg,
2668                 IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES
2669                 | IR_GRAPH_PROPERTY_CONSISTENT_OUTS
2670                 | IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO);
2671
2672         set_loop_params();
2673
2674         /* Reset stats for this procedure */
2675         reset_stats();
2676
2677         /* Preconditions */
2678         set_current_ir_graph(irg);
2679
2680         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
2681         collect_phiprojs(irg);
2682
2683         loop = get_irg_loop(irg);
2684
2685         loops = NEW_ARR_F(ir_loop *, 0);
2686         /* List all inner loops */
2687         n_elements = get_loop_n_elements(loop);
2688         for (i = 0; i < n_elements; ++i) {
2689                 loop_element element = get_loop_element(loop, i);
2690                 if (*element.kind != k_ir_loop)
2691                         continue;
2692                 find_innermost_loop(element.son);
2693         }
2694
2695         /* Set all links to NULL */
2696         irg_walk_graph(irg, reset_link, NULL, NULL);
2697
2698         for (i = 0; i < ARR_LEN(loops); ++i) {
2699                 ir_loop *loop = loops[i];
2700
2701                 ++stats.loops;
2702
2703                 /* Analyze and handle loop */
2704                 init_analyze(irg, loop);
2705
2706                 /* Copied blocks do not have their phi list yet */
2707                 collect_phiprojs(irg);
2708
2709                 /* Set links to NULL
2710                  * TODO Still necessary? */
2711                 irg_walk_graph(irg, reset_link, NULL, NULL);
2712         }
2713
2714         print_stats();
2715
2716         DEL_ARR_F(loops);
2717         ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
2718
2719         confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE);
2720 }
2721
2722 void do_loop_unrolling(ir_graph *irg)
2723 {
2724         loop_op = loop_op_unrolling;
2725         loop_optimization(irg);
2726 }
2727
2728 void do_loop_inversion(ir_graph *irg)
2729 {
2730         loop_op = loop_op_inversion;
2731         loop_optimization(irg);
2732 }
2733
2734 void do_loop_peeling(ir_graph *irg)
2735 {
2736         loop_op = loop_op_peeling;
2737         loop_optimization(irg);
2738 }
2739
2740 ir_graph_pass_t *loop_inversion_pass(const char *name)
2741 {
2742         return def_graph_pass(name ? name : "loop_inversion", do_loop_inversion);
2743 }
2744
2745 ir_graph_pass_t *loop_unroll_pass(const char *name)
2746 {
2747         return def_graph_pass(name ? name : "loop_unroll", do_loop_unrolling);
2748 }
2749
2750 ir_graph_pass_t *loop_peeling_pass(const char *name)
2751 {
2752         return def_graph_pass(name ? name : "loop_peeling", do_loop_peeling);
2753 }
2754
2755 void firm_init_loop_opt(void)
2756 {
2757         FIRM_DBG_REGISTER(dbg, "firm.opt.loop");
2758 }