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

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief    Loop peeling and unrolling
  23  * @author   Christian Helmer
  24  * @version  $Id$
  25  */
  26 #include "config.h"
  27
  28 #include "irnode.h"
  29 #include "debug.h"
  30
  31 #include "ircons.h"
  32 #include "irgopt.h"
  33 #include "irgmod.h"
  34 #include "irgwalk.h"
  35 #include "irouts.h"
  36 #include "iredges.h"
  37 #include "irtools.h"
  38 #include "array_t.h"    /* automatic array */
  39 #include "beutil.h"             /* get_block */
  40 #include "irloop_t.h"   /* set_irn_loop */
  41
  42 // TODO during DBG
  43 //#include "irnode_t.h"
  44 #include "irdump.h"
  45
  46 DEBUG_ONLY(static firm_dbg_module_t *dbg);
  47
  48 /**
  49  * Convenience macro for iterating over every phi node of the given block.
  50  * Requires phi list per block.
  51  */
  52 #define for_each_phi(block, phi) \
  53         for ( (phi) = get_Block_phis( (block) ); (phi) ; (phi) = get_Phi_next( (phi) ) )
  54
  55 /* current loop */
  56 static ir_loop *cur_loop;
  57
  58 /* The loop walker should be possible to abort if nothing can be done anymore */
  59 typedef unsigned irg_walk_func_abortable(ir_node *, void *);
  60
  61 /* condition for breaking a copy_walk */
  62 typedef unsigned walker_condition(ir_node *);
  63
  64 /* stores node and position of a predecessor */
  65 typedef struct out_edges {
  66         ir_node *node;
  67         int pred_irn_n;
  68 } out_edges;
  69
  70 /* access complex values through the nodes links */
  71 typedef struct node_info {
  72         unsigned invariant:1;
  73         ir_node *copy;
  74         ir_node *link;                                  /* temporary links for ssa creation */
  75         ir_node **ins;                                  /* ins for phi nodes, during rewiring of blocks */
  76         struct node_info *freelistnext; /* linked list to free all node_infos */
  77 } node_info;
  78
  79 static node_info *link_node_state_list;         /* head of the linked list to free all node_infos */
  80
  81 static out_edges *cur_loop_outs;                                /* A walker may start visiting the current loop with these nodes. */
  82 static out_edges *cur_head_outs;                                /* A walker may start visiting the cur head with these nodes. */
  83
  84 static ir_node *loop_cf_head = NULL;                            /* Loop head node */
  85 static unsigned loop_cf_head_valid = 1;                         /* A loop may have one head, otherwise we do not touch it. */
  86
  87 /* Inverted head */
  88 static ir_node *loop_inv_head = NULL;
  89 /* Peeled head */
  90 static ir_node *loop_peeled_head = NULL;
  91
  92 /* Loop analysis informations */
  93 typedef struct loop_info_t {
  94         unsigned calls;
  95         unsigned loads;
  96         unsigned invariant_loads;       /* number of load nodes */
  97         unsigned stores;                        /* number of store nodes */
  98         unsigned blocks;                        /* number of blocks in the loop */
  99         unsigned opnodes_n;                     /* nodes that should result in an instruction */
 100         unsigned opnodes_head;
 101 } loop_info_t;
 102
 103 /* Information about the current loop */
 104 static loop_info_t loop_info;
 105
 106 /* A walker may start visiting a condition chain with these nodes. */
 107 static out_edges *cond_chain_entries;
 108
 109 static unsigned head_inversion_node_count;
 110 static unsigned head_inversion_node_limit;
 111 static unsigned head_inversion_block_count;
 112
 113 /**
 114  *
 115  * ============= AUXILIARY FUNCTIONS =====================================
 116  */
 117
 118 /**
 119  * Creates object on the heap, and adds it to a linked list to free it later.
 120  */
 121 static node_info *new_node_info(void) {
 122         node_info *l = XMALLOCZ(node_info);
 123         l->freelistnext = link_node_state_list;
 124         link_node_state_list = l;
 125         l->copy = NULL;
 126         l->invariant = 0;
 127         return l;
 128 }
 129
 130 static node_info *get_node_info(ir_node *n)
 131 {
 132         return ((node_info *)get_irn_link(n));
 133 }
 134
 135 /* Allocates a node_info struct for the given node. For use with a walker. */
 136 static void alloc_node_info(ir_node *node, void *env)
 137 {
 138         node_info *state = new_node_info();
 139         (void) env;
 140         set_irn_link(node, (void *)state);
 141 }
 142
 143 static void free_node_info(void)
 144 {
 145         node_info *next;
 146         next = link_node_state_list;
 147         while(next->freelistnext) {
 148                 node_info *cur = next;
 149                 next = cur->freelistnext;
 150                 xfree( cur );
 151         }
 152 }
 153
 154 /**
 155  * Use the linked list to reset the reused values of all node_infos
 156  * Reset in particular the copy attribute as copy_walk uses it to determine a present copy
 157  */
 158 static void reset_node_infos(void)
 159 {
 160         node_info *next;
 161         next = link_node_state_list;
 162         while(next->freelistnext) {
 163                 node_info *cur = next;
 164                 next = cur->freelistnext;
 165                 cur->copy = NULL;
 166                 cur->ins = NULL;
 167                 cur->link = NULL;
 168         }
 169 }
 170
 171 /* Returns the  */
 172 static ir_node *get_copy(ir_node *n)
 173 {
 174         return ((node_info *)get_irn_link(n))->copy;
 175 }
 176
 177 /* Links the node to its copy */
 178 static void set_copy(ir_node *n, ir_node *copy)
 179 {
 180         ((node_info *)get_irn_link(n) )->copy = copy;
 181 }
 182
 183 /* Returns 0 if the node or block is not in cur_loop */
 184 static unsigned is_in_loop(ir_node *node)
 185 {
 186         return (get_irn_loop(get_block(node)) == cur_loop);
 187 }
 188
 189 /* Returns if the given be is an alien edge. This is the case when the pred is not in the loop. */
 190 static unsigned is_alien_edge(ir_node *n, int i)
 191 {
 192         return(!is_in_loop(get_irn_n(n, i)));
 193 }
 194
 195 /* used for walker */
 196 static void unmark_block(ir_node *node, void * env)
 197 {
 198         (void) env;
 199         DB((dbg, LEVEL_4, "UNMARK ..."));
 200         DB((dbg, LEVEL_4, " UNMARK %ld\n", get_irn_node_nr(node)));
 201         if(is_Block(node))
 202                 set_Block_mark(node, 0);
 203 }
 204
 205 static unsigned is_nodesblock_marked(ir_node* node)
 206 {
 207         return (get_Block_mark(get_block(node)));
 208 }
 209
 210 /* Returns the number of blocks in a loop. */
 211 int get_loop_n_blocks(ir_loop *loop) {
 212         int elements, e;
 213         int blocks = 0;
 214         elements = get_loop_n_elements(loop);
 215
 216         for(e=0; e<elements; e++) {
 217                 loop_element elem = get_loop_element(loop, e);
 218                 if  (is_ir_node(elem.kind) && is_Block(elem.node) )
 219                         ++blocks;
 220         }
 221         return blocks;
 222 }
 223
 224 /**
 225  * Add newpred at position pos to node and also add the corresponding value to the phis.
 226  * Requires block phi list.
 227  */
 228 static void duplicate_preds(ir_node* node, unsigned pos, ir_node* newpred)
 229 {
 230         ir_node** ins;
 231         ir_node *phi;
 232         int block_arity;
 233         int i;
 234
 235         assert(is_Block(node) && "duplicate_preds is only allowed for blocks");
 236
 237         DB((dbg, LEVEL_4, "duplicate_preds(node %ld, pos %d, newpred %ld)\n", get_irn_node_nr(node), pos, get_irn_node_nr(newpred)));
 238
 239         block_arity = get_irn_arity(node);
 240
 241         NEW_ARR_A(ir_node*, ins, block_arity + 1 );
 242         for (i = 0; i < block_arity; ++i)
 243                 ins[i] = get_irn_n(node, i);
 244         ins[block_arity] = newpred;
 245
 246         set_irn_in(node, block_arity + 1, ins);
 247
 248         for_each_phi(node, phi) {
 249                 int phi_arity = get_irn_arity(phi);
 250                 DB((dbg, LEVEL_4, "duplicate_preds: fixing phi %ld\n", get_irn_node_nr(phi)));
 251
 252                 NEW_ARR_A(ir_node *, ins, block_arity + 1);
 253                 for(i=0; i < phi_arity; ++i) {
 254                         DB((dbg, LEVEL_4, "in %ld\n", get_irn_node_nr(get_irn_n(phi, i))));
 255                         ins[i] = get_irn_n(phi, i);
 256                 }
 257                 ins[block_arity] = get_irn_n(phi, pos);
 258                 set_irn_in(phi, block_arity + 1, ins);
 259         }
 260 }
 261
 262 /* Adds all nodes pointing into the loop to loop_entries and also finds the loops head */
 263 static void get_loop_outs_and_info(ir_node *node, void *env)
 264 {
 265         unsigned node_in_loop, pred_in_loop;
 266         int i, arity;
 267         (void) env;
 268
 269         arity = get_irn_arity(node);
 270         for (i = 0; i < arity; i++) {
 271                 ir_node *pred = get_irn_n(node, i);
 272
 273                 pred_in_loop = is_in_loop(pred);
 274                 node_in_loop = is_in_loop(node);
 275
 276                 /* collect some loop information */
 277                 if (node_in_loop) {
 278                         if ( !is_Store(node) )
 279                                 ++loop_info.stores;
 280                         if ( !is_Load(node) )
 281                                 ++loop_info.loads;
 282                         if ( !is_Call(node) )
 283                                 ++loop_info.calls;
 284                         if ( !is_Block(node) && !is_Proj(node) && !is_Phi(node) )
 285                                 ++loop_info.opnodes_n;
 286                 }
 287
 288                 //Find the loops head/the blocks with cfpred outside of the loop
 289                 if (is_Block(node) && node_in_loop && !pred_in_loop && loop_cf_head_valid) {
 290                         ir_node *cfgpred = get_Block_cfgpred(node, i);
 291                         if ( !is_in_loop(cfgpred) ) {
 292                                 //DB((dbg, LEVEL_1, "potential head %+F\n", node));
 293                                 /* another head? We do not touch this. */
 294                                 if (loop_cf_head && loop_cf_head != node) {
 295                                         loop_cf_head_valid = 0;
 296                                 } else {
 297                                         loop_cf_head = node;
 298                                 }
 299                         }
 300                 }
 301
 302                 if ( pred_in_loop && !node_in_loop ) {
 303                         out_edges entry;
 304                         entry.node = node;
 305                         entry.pred_irn_n = i;
 306                         ARR_APP1(out_edges, cur_loop_outs, entry);
 307                 }
 308         }
 309 }
 310
 311 /**
 312  * Finds invariant loads and marks them as invariant.
 313  * (has to be post walk)
 314  */
 315 static unsigned get_invariants(ir_node *node, void *env)
 316 {
 317         unsigned invar = 1;
 318         int arity = get_irn_arity(node);
 319         (void) env;
 320
 321         /* RETURN, no preds to visit */
 322         if (arity == 0) return 0;
 323
 324         if (is_Load(node)) {
 325                 assert(arity>=2 && "expected load node to have in[1] (address)");
 326
 327                 ir_node *pred = get_irn_n(node, 1);
 328                 if ( (get_Load_volatility(node) == volatility_non_volatile) &
 329                                 (!is_in_loop(pred)
 330                                 || is_Const(pred)
 331                                 || is_SymConst(pred)
 332                                 || get_node_info(node)->invariant ) ) {
 333                         get_node_info(node)->invariant = 1;
 334                         ++loop_info.invariant_loads;
 335                 } else
 336                 {
 337                         get_node_info(node)->invariant = 0;
 338                 }
 339         } else {
 340                 int i;
 341                 invar = 1;
 342                 /* find loop variant preds */
 343                 for(i = 0; i < arity; ++i) {
 344                         ir_node *pred = get_irn_n(node, i);
 345
 346                         if ( is_in_loop(pred)                                                   /* outside loop is loop invariant */
 347                                         && !is_Const(pred)                                              /* constants */
 348                                         && !is_SymConst(pred)                                   /* SymConst */
 349                                         && !get_node_info(node)->invariant ) {  /* pred is marked as invariant */
 350                                 invar = 0;
 351                         }
 352                 }
 353
 354                 if (invar) {
 355                         get_node_info(node)->invariant = 1;
 356                 } else {
 357                         get_node_info(node)->invariant = 0;
 358                 }
 359         }
 360         return 0;
 361 }
 362
 363
 364 static ir_node *ssa_second_def;
 365 static ir_node *ssa_second_def_block;
 366
 367 /**
 368  * Walks the graph bottom up, searching for definitions and create phis.
 369  * (Does not handle the special case where the second definition is in the block of the user
 370  * of the original definition because it is not necessary here.)
 371  */
 372 static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode)
 373 {
 374         int i;
 375         int n_cfgpreds;
 376         ir_graph *irg;
 377         ir_node *phi;
 378         ir_node **in;
 379
 380         DB((dbg, LEVEL_4, "ssa sdacp: block %ld\n", get_irn_node_nr(block)));
 381
 382         /* Prevents creation of phi that would be bad anyway.
 383          * Dead and bad blocks. */
 384         if (get_irn_arity(block) < 1 || is_Bad(block))
 385                 return new_Bad();
 386
 387         if (block == ssa_second_def_block) {
 388                 DB((dbg, LEVEL_4, "ssa found second definition: use second def %ld\n", get_irn_node_nr(ssa_second_def)));
 389                 return ssa_second_def;
 390         }
 391
 392         /* already processed this block? */
 393         if (irn_visited(block)) {
 394                 ir_node *value = get_node_info(block)->link;
 395                 DB((dbg, LEVEL_4, "ssa already visited: use linked %ld\n", get_irn_node_nr(value)));
 396                 return value;
 397         }
 398
 399         irg = get_irn_irg(block);
 400         assert(block != get_irg_start_block(irg));
 401
 402         /* a Block with only 1 predecessor needs no Phi */
 403         n_cfgpreds = get_Block_n_cfgpreds(block);
 404         if (n_cfgpreds == 1) {
 405                 ir_node *pred_block = get_Block_cfgpred_block(block, 0);
 406                 ir_node *value;
 407
 408                 DB((dbg, LEVEL_4, "ssa 1 pred: walk pred %ld\n", get_irn_node_nr(pred_block)));
 409
 410                 value = search_def_and_create_phis(pred_block, mode);
 411                 get_node_info(block)->link = value;
 412                 mark_irn_visited(block);
 413
 414                 return value;
 415         }
 416
 417         /* create a new Phi */
 418         NEW_ARR_A(ir_node*, in, n_cfgpreds);
 419         for(i = 0; i < n_cfgpreds; ++i)
 420                 in[i] = new_Unknown(mode);
 421
 422         phi = new_r_Phi(block, n_cfgpreds, in, mode);
 423
 424         /* Important: always keep block phi list up to date. */
 425         add_Block_phi(block, phi);
 426         /* EVERY node is assumed to have a node_info linked. */
 427         alloc_node_info(phi, NULL);
 428
 429         DB((dbg, LEVEL_4, "ssa phi creation: link new phi %ld to block %ld\n", get_irn_node_nr(phi), get_irn_node_nr(block)));
 430
 431         get_node_info(block)->link = phi;
 432         mark_irn_visited(block);
 433
 434         /* set Phi predecessors */
 435         for(i = 0; i < n_cfgpreds; ++i) {
 436                 ir_node *pred_block = get_Block_cfgpred_block(block, i);
 437                 ir_node *pred_val   = search_def_and_create_phis(pred_block, mode);
 438                 DB((dbg, LEVEL_4, "ssa phi pred:phi %ld, pred %ld\n", get_irn_node_nr(phi), get_irn_node_nr(pred_val)));
 439                 set_irn_n(phi, i, pred_val);
 440         }
 441
 442         return phi;
 443 }
 444
 445 /**
 446  * Given a set of values this function constructs SSA-form for the users of the
 447  * first value (the users are determined through the out-edges of the value).
 448  * Uses the irn_visited flags. Works without using the dominance tree.
 449  */
 450 static void construct_ssa(ir_node *orig_block, ir_node *orig_val,
 451                           ir_node *second_block, ir_node *second_val)
 452 {
 453         ir_graph *irg;
 454         ir_mode *mode;
 455         const ir_edge_t *edge;
 456         const ir_edge_t *next;
 457
 458         assert(orig_block && orig_val && second_block && second_val &&
 459                         "no parameter of construct_ssa may be NULL");
 460
 461         /* no need to do anything */
 462         if (orig_val == second_val)
 463                 return;
 464
 465         irg = get_irn_irg(orig_val);
 466
 467         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
 468         inc_irg_visited(irg);
 469
 470         mode = get_irn_mode(orig_val);
 471         get_node_info(orig_block)->link = orig_val;
 472         mark_irn_visited(orig_block);
 473
 474         ssa_second_def_block = second_block;
 475         ssa_second_def       = second_val;
 476
 477         /* Only fix the users of the first, i.e. the original node */
 478         foreach_out_edge_safe(orig_val, edge, next) {
 479                 ir_node *user = get_edge_src_irn(edge);
 480                 int j = get_edge_src_pos(edge);
 481                 ir_node *user_block = get_nodes_block(user);
 482                 ir_node *newval;
 483
 484                 /* ignore keeps */
 485                 if (is_End(user))
 486                         continue;
 487
 488                 DB((dbg, LEVEL_4, "original user %ld\n", get_irn_node_nr(user)));
 489
 490                 if (is_Phi(user)) {
 491                         ir_node *pred_block = get_Block_cfgpred_block(user_block, j);
 492                         newval = search_def_and_create_phis(pred_block, mode);
 493                 } else {
 494                         newval = search_def_and_create_phis(user_block, mode);
 495                 }
 496
 497                 /* If we get a bad node the user keeps the original in. No second definition needed. */
 498                 if (newval != user && !is_Bad(newval))
 499                         set_irn_n(user, j, newval);
 500         }
 501
 502         ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
 503 }
 504
 505 /* get the number of backedges without alien bes */
 506 static int get_backedge_n(ir_node *loophead, unsigned with_alien)
 507 {
 508         int i;
 509         int be_n = 0;
 510         int arity = get_irn_arity(loophead);
 511         for (i = 0; i < arity; ++i) {
 512                 ir_node *pred = get_irn_n(loophead, i);
 513                 if (is_backedge(loophead, i) && ( with_alien || is_in_loop(pred)) )
 514                         ++be_n;
 515         }
 516         return be_n;
 517 }
 518
 519 /**
 520  * Sets the nodes backedges, according to its predecessors link.
 521  */
 522 static void fix_backedge_info(ir_node *node)
 523 {
 524         int i;
 525         for (i = 0; i < get_irn_arity(node); ++i)
 526         {
 527                 ir_node *pred = get_irn_n(node, i);
 528                 if (get_node_info(pred)->link != NULL)
 529                         set_backedge(node, i);
 530                 else
 531                         set_not_backedge(node, i);
 532         }
 533 }
 534
 535 /**
 536  *
 537  * ============= PEELING =====================================
 538  *
 539  */
 540
 541 /**
 542  * Rewires the heads after peeling.
 543  */
 544 static void peel_fix_heads(void)
 545 {
 546         ir_node **loopheadnins, **peelheadnins;
 547         ir_node *loophead = loop_cf_head;
 548         ir_node *peelhead = get_copy(loophead);
 549
 550         int headarity = get_irn_arity(loophead);
 551         ir_node *phi;
 552         int i;
 553
 554         int lheadin_c = 0;
 555         int pheadin_c = 0;
 556
 557         int backedges_n = get_backedge_n(loophead, 0);
 558
 559         int lhead_arity = 2 * backedges_n;
 560         int phead_arity = headarity - backedges_n;
 561
 562         /* new in arrays */
 563         NEW_ARR_A(ir_node *, loopheadnins, lhead_arity );
 564         NEW_ARR_A(ir_node *, peelheadnins, phead_arity );
 565
 566         for_each_phi(loophead, phi) {
 567                 NEW_ARR_A(ir_node *, get_node_info(phi)->ins, lhead_arity);
 568         }
 569         for_each_phi(peelhead, phi) {
 570                 NEW_ARR_A(ir_node *, get_node_info(phi)->ins, phead_arity);
 571         }
 572
 573         for (i = 0; i < headarity; i++)
 574         {
 575                 ir_node *orgjmp = get_irn_n(loophead, i);
 576                 ir_node *copyjmp = get_copy(orgjmp);
 577
 578                 /**
 579                  * Rewire the head blocks ins and their phi ins.
 580                  * Requires phi list per block.
 581                  */
 582                 if (is_backedge(loophead, i) && !is_alien_edge(loophead, i)) {
 583                         loopheadnins[lheadin_c] = orgjmp;
 584                         /* marks out edge as backedge */
 585                         get_node_info(orgjmp)->link = orgjmp;
 586                         for_each_phi(loophead, phi) {
 587                                 get_node_info( phi )->ins[lheadin_c] =  get_irn_n( phi, i) ;
 588                         }
 589                         ++lheadin_c;
 590
 591                         loopheadnins[lheadin_c] = copyjmp;      /* former bes of the peeled code origin now from the loophead */
 592                         /* marks out edge as normal edge */
 593                         get_node_info(copyjmp)->link = NULL;
 594                         /* get_irn_n( get_copy_of(phi), i) <!=> get_copy_of(get_irn_n( phi, i))
 595                          * Order is crucial! Predecessors outside of the loop are non existent.
 596                          * The copy (cloned with its ins!) has pred i,
 597                          * but phis pred i might not have a copy of itself.
 598                          */
 599                         for_each_phi(loophead, phi) {
 600                                 //printf("normalbe phi %ld @ %d -> %ld\n", phi->node_nr, i,  get_irn_n( get_copy_of(phi), i)->node_nr);
 601                                 get_node_info( phi )->ins[lheadin_c] =  get_irn_n( get_copy(phi), i) ;
 602                         }
 603                         ++lheadin_c;
 604                 } else {
 605                         peelheadnins[pheadin_c] = orgjmp;
 606                         /* marks out edge as normal edge */
 607                         get_node_info(orgjmp)->link = NULL;
 608                         for_each_phi(peelhead, phi) {
 609                                 get_node_info( phi )->ins[pheadin_c] = get_irn_n(phi, i);
 610                         }
 611                         ++pheadin_c;
 612                 }
 613         }/* for */
 614
 615         //DBG
 616         assert(pheadin_c == ARR_LEN(peelheadnins) &&
 617                         lheadin_c == ARR_LEN(loopheadnins) &&
 618                         "the constructed head arities do not match the predefined arities");
 619
 620         /**
 621          * assign the ins to the nodes
 622          */
 623         set_irn_in(loophead, ARR_LEN(loopheadnins), loopheadnins);
 624         set_irn_in(peelhead, ARR_LEN(peelheadnins), peelheadnins);
 625
 626         /* Fixes the backedge information according to the link.
 627          * Following loop optimizations might depend on it. */
 628         fix_backedge_info(loophead);
 629         fix_backedge_info(peelhead);
 630
 631         for_each_phi(loophead, phi) {
 632                 ir_node **ins = get_node_info( phi )->ins;
 633                 set_irn_in(phi, lhead_arity, ins);
 634         }
 635
 636         for_each_phi(peelhead, phi) {
 637                 ir_node **ins = get_node_info( phi )->ins;
 638                 set_irn_in(phi, phead_arity, ins);
 639         }
 640 }
 641
 642 /**
 643  * Create a raw copy (ins are still the old ones) of the given node.
 644  */
 645 static ir_node *rawcopy_node(ir_node *node)
 646 {
 647         ir_node *cp;
 648         node_info *cpstate;
 649
 650         cp = exact_copy(node);
 651         set_copy(node, cp);
 652         cpstate = new_node_info();
 653         set_irn_link(cp, cpstate);
 654         mark_irn_visited(cp);
 655         return cp;
 656 }
 657
 658 //int temp = 0;
 659 //
 660 ///* This walker copies all walked nodes. The walk_condition determines the nodes to walk. */
 661 //static void keepalives_walk(ir_node *node, walker_condition *walk_condition)
 662 //{
 663 //      int i;
 664 //      int arity;
 665 //      ir_graph *irg = current_ir_graph;
 666 //
 667 //      /**
 668 //       * break condition and cycle resolver, creating temporary node copies
 669 //       */
 670 //      if (get_irn_visited(node) >= get_irg_visited(irg)) {
 671 //              return;
 672 //      }
 673 //
 674 //      /* Walk */
 675 //      mark_irn_visited(node);
 676 //
 677 //      if (!is_Block(node)) {
 678 //              ir_node *pred = get_nodes_block(node);
 679 //              if (walk_condition(pred))
 680 //                      keepalives_walk( pred, walk_condition );
 681 //      }
 682 //
 683 //      arity = get_irn_arity(node);
 684 //
 685 //      for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 686 //              ir_node *pred = get_irn_n(node, i);
 687 //
 688 //              if (walk_condition(pred))
 689 //                      keepalives_walk( pred, walk_condition );
 690 //      }
 691 //
 692 //      add_End_keepalive(get_irg_end(current_ir_graph), node);
 693 //}
 694
 695
 696 /**
 697  * This walker copies all walked nodes.
 698  * If the walk_condition is true for a node, it is walked.
 699  * All nodes node_info->copy attributes has to be NULL prior to every to every walk.
 700  */
 701 static void copy_walk(ir_node *node, walker_condition *walk_condition)
 702 {
 703         int i;
 704         int arity;
 705         ir_node *cp;
 706         ir_node **cpin;
 707         ir_graph *irg = current_ir_graph;
 708         node_info *node_info = get_node_info(node);
 709
 710         /**
 711          * break condition and cycle resolver, creating temporary node copies
 712          */
 713         if (get_irn_visited(node) >= get_irg_visited(irg)) {
 714                 /* Here we rely on nodestate's copy being initialized with NULL */
 715                 DB((dbg, LEVEL_4, "copy_walk: We have already visited %ld\n", get_irn_node_nr(node)));
 716                 if (node_info->copy == NULL) {
 717 //                      if (!is_Const(node) && !is_SymConst(node)) {
 718                                 cp = rawcopy_node(node);
 719 //                      } else {
 720 //                              cp = node;
 721 //                              node_info->copy = cp;
 722 //                      }
 723                         DB((dbg, LEVEL_4, "The TEMP copy of %ld is created %ld\n", get_irn_node_nr(node), get_irn_node_nr(cp)));
 724                 }
 725                 return;
 726         }
 727
 728 //      add_End_keepalive(get_irg_end(current_ir_graph), node);
 729
 730         /* Walk */
 731         mark_irn_visited(node);
 732
 733         if (!is_Block(node)) {
 734                 ir_node *pred = get_nodes_block(node);
 735                 if (walk_condition(pred))
 736                         DB((dbg, LEVEL_4, "walk block %ld\n", get_irn_node_nr(pred)));
 737                         copy_walk( pred, walk_condition );
 738         }
 739
 740         arity = get_irn_arity(node);
 741
 742         NEW_ARR_A(ir_node *, cpin, arity);
 743
 744         for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 745                 ir_node *pred = get_irn_n(node, i);
 746
 747                 if (walk_condition(pred)) {
 748                         DB((dbg, LEVEL_4, "walk node %ld\n", get_irn_node_nr(pred)));
 749                         copy_walk( pred, walk_condition );
 750                         cpin[i] = get_copy(pred);
 751                         DB((dbg, LEVEL_4, "copy of %ld gets new in %ld which is copy of %ld\n",
 752                                         get_irn_node_nr(node), get_irn_node_nr(get_copy(pred)), get_irn_node_nr(pred)));
 753                 } else {
 754                         cpin[i] = pred;
 755                 }
 756         }
 757
 758         /* copy node / finalize temp node */
 759         if (node_info->copy == NULL) {
 760                 /* No temporary copy existent */
 761
 762                 /* Do not copy constants TODO right? */
 763 //              if (!is_Const(node) && !is_SymConst(node)) {
 764                         cp = rawcopy_node(node);
 765 //              } else {
 766 //                      cp = node;
 767 //                      node_info->copy = cp;
 768 //              }
 769                 DB((dbg, LEVEL_4, "The FINAL copy of %ld is CREATED %ld\n", get_irn_node_nr(node), get_irn_node_nr(cp)));
 770         } else {
 771                 /* temporary copy is existent but without correct ins */
 772                 cp = get_copy(node);
 773                 DB((dbg, LEVEL_4, "The FINAL copy of %ld is EXISTENT %ld\n", get_irn_node_nr(node), get_irn_node_nr(cp)));
 774         }
 775
 776         if (!is_Block(node)) {
 777                 ir_node *cpblock = get_copy(get_nodes_block(node));
 778
 779                 set_nodes_block(cp, cpblock );
 780                 /* fix the phi information in attr.phis */
 781                 if( is_Phi(cp) )
 782                         add_Block_phi(cpblock, cp);
 783         } else {
 784                 /* macroblock info has not been copied */
 785                 set_Block_MacroBlock(cp, cp);
 786         }
 787
 788         //TODO do?
 789         //set_irn_loop(cp, cur_loop);
 790         set_irn_in(cp, ARR_LEN(cpin), cpin);
 791 }
 792
 793 /* Loop peeling, and fix the cf for the loop entry nodes, which have now more preds */
 794 static void peel(out_edges *loop_outs)
 795 {
 796         int i;
 797         ir_node **entry_buffer;
 798         int entry_c = 0;
 799
 800         ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
 801
 802         NEW_ARR_A(ir_node *, entry_buffer, ARR_LEN(loop_outs));
 803
 804         /* duplicate loop walk */
 805 //      cur_head = loop_cf_head;
 806         inc_irg_visited(current_ir_graph);
 807
 808         for(i = 0; i < ARR_LEN(loop_outs); i++) {
 809                 out_edges entry = loop_outs[i];
 810                 ir_node *node = entry.node;
 811                 ir_node *pred = get_irn_n(entry.node, entry.pred_irn_n);
 812
 813                 if (is_Block(node)) {
 814                         copy_walk( pred, is_in_loop );
 815                         duplicate_preds(node, entry.pred_irn_n, get_copy(pred) );
 816                 } else {
 817                         copy_walk( pred, is_in_loop );
 818                         if (!is_End(node))              /* leave out keepalives */
 819                                 /* Node is user of a value defined inside the loop.
 820                                  * We'll need a phi since we duplicated the loop. */
 821                                 /* cannot construct_ssa here, because it needs another walker */
 822                                 entry_buffer[entry_c++] = pred;
 823                 }
 824         }
 825
 826         ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
 827
 828         /* Rewires the 2 heads */
 829         peel_fix_heads();
 830
 831         /* Generate phis for values from peeled code and original loop */
 832         for(i = 0; i < entry_c; i++)
 833         {
 834                 ir_node *cppred, *block, *cpblock, *pred;
 835
 836                 /* It is not possible to use
 837                  * pred = get_irn_n(entry.node, entry.pred_irn_n);
 838                  * because we might have changed the nodes predecessors in construct_ssa
 839                  */
 840                 pred = entry_buffer[i];
 841                 cppred = get_copy(pred);
 842                 block = get_nodes_block(pred);
 843                 cpblock = get_nodes_block(cppred);
 844                 construct_ssa(block, pred, cpblock, cppred);
 845         }
 846 }
 847
 848 /*
 849  * Populates head_entries with (node, pred_pos) tuple
 850  * whereas the node's pred at pred_pos is in the head but not the node itself.
 851  * Head and condition chain blocks must be marked.
 852  */
 853 static void get_head_entries(ir_node *node, void *env)
 854 {
 855         int i;
 856         int arity = get_irn_arity(node);
 857         (void) env;
 858
 859         DB((dbg, LEVEL_5, "get head entries \n"));
 860
 861         for(i = 0; i < arity; ++i) {
 862                 /* node is not in the head, but the predecessor is.
 863                  * (head or loop chain nodes are marked) */
 864                 DB((dbg, LEVEL_5, "... "));
 865                 DB((dbg, LEVEL_5, "node %ld  marked %d (0)  pred %d marked %d (1) \n",
 866                                 node->node_nr, is_nodesblock_marked(node),i, is_nodesblock_marked(get_irn_n(node, i))));
 867                 if (!is_nodesblock_marked(node) && is_nodesblock_marked(get_irn_n(node, i))) {
 868                         out_edges entry;
 869                         entry.node = node;
 870                         entry.pred_irn_n = i;
 871                         DB((dbg, LEVEL_4,
 872                                         "Found head chain entry %ld @%d because !inloop %ld and inloop %ld\n",
 873                                         node->node_nr, i, node->node_nr, get_irn_n(node, i)->node_nr));
 874                         ARR_APP1(out_edges, cur_head_outs, entry);
 875                 }
 876         }
 877 }
 878
 879 /**
 880  * Find condition chains, and add them to be inverted, until the node count exceeds the limit.
 881  * A block belongs to the chain if a condition branches out of the loop.
 882  * Returns if the given block belongs to the condition chain.
 883  * FIXME prevent collecting ALL loop blocks (may happen if all blocks jump out of the loop)
 884  */
 885 static unsigned condition_chains(ir_node *block) {
 886         const ir_edge_t *edge;
 887         unsigned mark = 0;
 888         int nodes_n = 0;
 889
 890         printf("cd %ld\n", block->node_nr);
 891
 892         /* we need all outs, including keeps (TODO firm function for that??) */
 893         foreach_out_edge_kind(block, edge, EDGE_KIND_NORMAL) {
 894                 ++nodes_n;
 895         }
 896
 897         /* We do not want to collect more nodes from condition chains, than the limit allows us to.
 898          * Also, leave at least one block as body. */
 899         if (head_inversion_node_count + nodes_n > head_inversion_node_limit
 900                         || loop_info.blocks == head_inversion_block_count + 1) {
 901                 set_Block_mark(block, 0);
 902                 printf(" %ld over limit\n", block->node_nr);
 903                 return 0;
 904         }
 905
 906         printf("blocks ++ %ld\n", block->node_nr);
 907 //      ++loop_info.blocks;
 908
 909         /* First: check our successors, and add all succs that are outside of the loop to the list */
 910         foreach_block_succ(block, edge) {
 911                 ir_node *src = get_edge_src_irn( edge );
 912                 int pos = get_edge_src_pos( edge );
 913
 914                 printf("check %ld\n", src->node_nr);
 915
 916                 if (src->loop)
 917                         printf(" src %ld in loop %ld  curlooop %ld \n", src->node_nr, src->loop->loop_nr, cur_loop->loop_nr);
 918                 if (!is_in_loop(src)) {
 919                         printf(" src %ld @ %d into block %ld \n", src->node_nr, pos, block->node_nr);
 920
 921                         mark = 1;
 922                         out_edges entry;
 923                         entry.node = src;
 924                         entry.pred_irn_n = pos;
 925                         ARR_APP1(out_edges, cond_chain_entries, entry);
 926                         mark_irn_visited(src);
 927                 }
 928         }
 929
 930         /* this block is not part of the chain,
 931          * because the chain would become too big or we have no succ outside of the loop */
 932         if (mark == 0) {
 933                 printf("mark is 0 %ld\n", block->node_nr);
 934                 set_Block_mark(block, 0);
 935                 return 0;
 936         } else {
 937                 printf("mark is 1 %ld\n", block->node_nr);
 938                 set_Block_mark(block, 1);
 939                 ++head_inversion_block_count;
 940                 DB((dbg, LEVEL_4, "block %ld is part of condition chain\n", get_irn_node_nr(block)));
 941                 head_inversion_node_count += nodes_n;
 942         }
 943
 944         /* Second: walk all successors, and add them to the list if they are not part of the chain */
 945         foreach_block_succ(block, edge) {
 946                 unsigned inchain;
 947                 ir_node *src = get_edge_src_irn( edge );
 948                 int pos = get_edge_src_pos( edge );
 949
 950                 /* already done cases */
 951                 if (!is_in_loop( src ) || (get_irn_visited(src) >= get_irg_visited(current_ir_graph))) {
 952 //                      printf("!inloop || visited %ld\n", block->node_nr);
 953                         continue;
 954                 }
 955
 956                 mark_irn_visited(src);
 957                 DB((dbg, LEVEL_4, "condition chain walk %ld\n", get_irn_node_nr(src)));
 958                 inchain = condition_chains( src );
 959
 960                 /* if successor is not part of chain we need to collect its outs */
 961                 if ( !inchain ) {
 962                         out_edges entry;
 963                         entry.node = src;
 964                         entry.pred_irn_n = pos;
 965                         ARR_APP1(out_edges, cond_chain_entries, entry);
 966                 }
 967         }
 968         return mark;
 969 }
 970
 971 /**
 972  *
 973  */
 974 static void inversion_fix_heads(void)
 975 {
 976         ir_node **loopheadnins, **invheadnins;
 977         ir_node *loophead = loop_cf_head;
 978         ir_node *invhead =      get_copy(loophead);
 979
 980         int headarity =         get_irn_arity(loophead);
 981         ir_node *phi;
 982         int i;
 983
 984         int lheadin_c = 0;
 985         int iheadin_c = 0;
 986
 987         int backedges_n = get_backedge_n(loophead, 0);
 988         int lhead_arity = headarity - backedges_n;
 989         int ihead_arity = backedges_n;
 990
 991         /* new in arrays for all phis in the head blocks */
 992         NEW_ARR_A(ir_node *, loopheadnins, lhead_arity);
 993         NEW_ARR_A(ir_node *, invheadnins, ihead_arity);
 994
 995         for_each_phi(loophead, phi) {
 996                 NEW_ARR_A(ir_node *, get_node_info(phi)->ins, lhead_arity);
 997         }
 998         for_each_phi(invhead, phi) {
 999                 NEW_ARR_A(ir_node *, get_node_info(phi)->ins, ihead_arity);
1000         }
1001
1002         for (i = 0; i < headarity; i++) {
1003                 ir_node *pred = get_irn_n(loophead, i);
1004
1005                 /**
1006                  * Rewire the head blocks ins and their phi ins.
1007                  * Requires phi list per block.
1008                  */
1009                 if ( is_backedge(loophead, i) && !is_alien_edge(loophead, i) ) {
1010                         invheadnins[iheadin_c] = pred;
1011                         for_each_phi(invhead, phi) {
1012                                 get_node_info( phi )->ins[iheadin_c] =  get_irn_n( phi, i) ;
1013                         }
1014                         ++iheadin_c;
1015                 } else {
1016                         /* just copy these edges */
1017                         loopheadnins[lheadin_c] = pred;
1018                         for_each_phi(loophead, phi) {
1019                                 get_node_info( phi )->ins[lheadin_c] = get_irn_n(phi, i);
1020                         }
1021                         ++lheadin_c;
1022                 }
1023         }/* for */
1024
1025         /* assign the ins to the head blocks */
1026         set_irn_in(loophead, ARR_LEN(loopheadnins), loopheadnins);
1027         set_irn_in(invhead, ARR_LEN(invheadnins), invheadnins);
1028
1029         /* assign the ins for the phis */
1030         for_each_phi(loophead, phi) {
1031                 ir_node **ins = get_node_info(phi)->ins;
1032                 set_irn_in(phi, lhead_arity, ins);
1033         }
1034
1035         for_each_phi(invhead, phi) {
1036                 ir_node **ins = get_node_info(phi)->ins;
1037                 set_irn_in(phi, ihead_arity, ins);
1038         }
1039 }
1040
1041
1042 static void loop_inversion_walk(out_edges *head_entries)
1043 {
1044         int i;
1045         ir_node *phi;
1046         int entry_c = 0;
1047         ir_node **entry_buffer;
1048         ir_node **head_phi_assign;
1049
1050         NEW_ARR_A(ir_node *, entry_buffer, ARR_LEN(head_entries));
1051
1052         head_phi_assign = NEW_ARR_F(ir_node *, 0);
1053
1054         /* Find assignments in the condition chain, to construct_ssa for them after the loop inversion. */
1055         for_each_phi( loop_cf_head , phi) {
1056                 for(i=0; i<get_irn_arity(phi); ++i) {
1057                         ir_node *def = get_irn_n(phi, i);
1058                         if ( is_nodesblock_marked(def) ) {
1059                                 ARR_APP1(ir_node *, head_phi_assign, def);
1060                         }
1061                 }
1062         }
1063
1064         ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
1065
1066         /* duplicate condition chain */
1067         inc_irg_visited(current_ir_graph);
1068
1069         for(i = 0; i < ARR_LEN(head_entries); ++i) {
1070                 out_edges entry = head_entries[i];
1071                 ir_node *node = entry.node;
1072                 ir_node *pred = get_irn_n(entry.node, entry.pred_irn_n);
1073
1074 //              add_End_keepalive(get_irg_end(current_ir_graph), pred);
1075
1076                 if (is_Block(node)) {
1077                         DB((dbg, LEVEL_4, "\nINIT walk block %ld\n", get_irn_node_nr(pred)));
1078                         copy_walk(pred, is_nodesblock_marked);
1079                         duplicate_preds(node, entry.pred_irn_n, get_copy(pred) );
1080                 } else {
1081                         DB((dbg, LEVEL_4, "\nInit walk node  %ld\n", get_irn_node_nr(pred)));
1082                         copy_walk( pred, is_nodesblock_marked );
1083
1084                         /* ignore keepalives */
1085                         if (!is_End(node))
1086                                 /* Node is user of a value assigned inside the loop.
1087                                  * We'll need a phi since we duplicated the head. */
1088                                 entry_buffer[entry_c++] = pred;
1089                 }
1090         }
1091
1092         ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
1093
1094         inversion_fix_heads();
1095
1096         /* Generate phis for users of values assigned in the condition chain and read in the loops body */
1097         for(i = 0; i < entry_c; i++) {
1098                 ir_node *cppred, *block, *cpblock, *pred;
1099
1100                 /* It is not possible to use
1101                  * pred = get_irn_n(entry.node, entry.pred_irn_n);
1102                  * because we might have changed the nodes predecessors in construct_ssa
1103                  */
1104                 pred = entry_buffer[i];
1105                 cppred = get_copy(pred);
1106                 block = get_nodes_block(pred);
1107                 cpblock = get_nodes_block(cppred);
1108                 DB((dbg, LEVEL_4,
1109                                 "construct_ssa (loop out value) original %ld and clone %ld\n",
1110                                 get_irn_node_nr(pred), get_irn_node_nr(cppred)));
1111                 construct_ssa(block, pred, cpblock, cppred);
1112
1113
1114 //              char *res;
1115 //              char *s = "-SSA_";
1116 //              char *n = strdup(" ");
1117 //              n[0] = 'a' + (char)i;
1118 //              res = strdup(s);
1119 //              strcat(res, n);
1120 //              dump_ir_block_graph(current_ir_graph, res );
1121         }
1122
1123         /* Generate phis for values that are assigned in the condition chain
1124          * but not read in the loops body.
1125          */
1126         for(i = 0; i < ARR_LEN(head_phi_assign); ++i) {
1127                 ir_node *def_block, *inhead_phi_def, *inv_def_block, *inv_inhead_phi_def;
1128                 /* Note: construct_ssa only fixes the FIRST nodes usage. */
1129                 inhead_phi_def = head_phi_assign[i];
1130                 inv_inhead_phi_def = get_copy(inhead_phi_def);
1131                 def_block = get_nodes_block(inhead_phi_def);
1132                 inv_def_block = get_nodes_block(inv_inhead_phi_def);
1133                 DB((dbg, LEVEL_4,
1134                                 "construct_ssa (condition chain out values) original %ld and clone %ld\n",
1135                                 get_irn_node_nr(inv_inhead_phi_def), get_irn_node_nr(inhead_phi_def)));
1136                 construct_ssa(inv_def_block, inv_inhead_phi_def, def_block, inhead_phi_def);
1137         }
1138         loop_cf_head = get_copy(loop_cf_head);
1139 }
1140
1141 /**
1142  * Decide if loop inversion, peeling or unrolling should be performed.
1143  * Inversion creates abnormal looking loops. Be careful with optimizations after that.
1144  */
1145 static void decision_maker(void)
1146 {
1147         unsigned do_peel = 0;
1148         unsigned do_inversion = 1;
1149
1150         unsigned max_loop_opnodes = 2000000;
1151
1152         head_inversion_node_limit = 99910;
1153
1154         cur_loop_outs = NEW_ARR_F(out_edges, 0);
1155
1156         /* Find loop entries walk, find head */
1157         inc_irg_visited( current_ir_graph );
1158         irg_walk_graph( current_ir_graph, get_loop_outs_and_info, NULL, NULL );
1159
1160         /* RETURN if there is no valid head */
1161         if (!loop_cf_head || !loop_cf_head_valid) {
1162                 DB((dbg, LEVEL_1, "No valid loop head. Nothing done.\n"));
1163                 return;
1164         }
1165 #if 0
1166         /* RETURN if there is a call in the loop */
1167         if (loop_info.calls)
1168                 return;
1169
1170         /* Loop complexity too high */
1171         if (loop_info.opnodes_n > max_loop_opnodes)
1172                 return;
1173
1174 //      foreach_out_edge(loop_cf_head, edge) {
1175 //              ir_node *node = get_edge_src_irn(edge);
1176 //              if ( !is_Block(node) && !is_Proj(node) && !is_Phi(node) )
1177 //                      ++loop_info.opnodes_head;
1178 //      }
1179
1180         inc_irg_visited(current_ir_graph);
1181         loop_walker( loop_outs, NULL, get_invariants, NULL );
1182
1183         /* This could be improved with knowledge about variable range. */
1184         if (loop_info.stores == 0 && loop_info.invariant_loads > 0)
1185                 do_peel = 1;
1186
1187 #endif
1188
1189
1190         do_peel = 1;
1191         do_inversion = 1;
1192
1193         /* Loop peeling */
1194         if (do_peel) {
1195                 peel(cur_loop_outs);
1196                 reset_node_infos();
1197         }
1198
1199         DEBUG_ONLY(dump_ir_block_graph(current_ir_graph, "-peeled1"));
1200
1201         DEL_ARR_F(cur_loop_outs);
1202
1203         /* Loop inversion */
1204         /* Search for condition chains. We may not do this before peeling, as peeling changes things. */
1205         ir_reserve_resources(current_ir_graph, IR_RESOURCE_BLOCK_MARK);
1206         irg_walk_graph(current_ir_graph, unmark_block, NULL, NULL);
1207
1208         loop_info.blocks = get_loop_n_blocks(cur_loop);
1209         cond_chain_entries = NEW_ARR_F(out_edges, 0);
1210         head_inversion_node_count = 0;
1211         head_inversion_block_count = 0;
1212         inc_irg_visited(current_ir_graph);
1213         set_Block_mark(loop_cf_head, 1);
1214         mark_irn_visited(loop_cf_head);
1215         /* find condition chains */
1216         condition_chains(loop_cf_head);
1217
1218         DEBUG_ONLY(dump_ir_block_graph(current_ir_graph, "-pre_inversion"));
1219
1220         // TODO assume number of phis to be created. prevent inversion in case ...
1221
1222         /* Loop inversion */
1223         /* We catch endless loops here too,
1224          * because they do not have a condition chain and a maximum of 1 block. */
1225         if (loop_info.blocks < 2) {
1226                 do_inversion = 0;
1227                 DB((dbg, LEVEL_1, "Loop contains %d (less than 2) blocks => No Inversion done.\n", loop_info.blocks));
1228         }
1229
1230         if (head_inversion_block_count < 1) {
1231                 do_inversion = 0;
1232                 DB((dbg, LEVEL_1, "Loop contains %d (less than 1) invertible blocks => No Inversion done.\n", head_inversion_block_count));
1233         }
1234
1235
1236         if (do_inversion) {
1237                 cur_head_outs = NEW_ARR_F(out_edges, 0);
1238
1239                 /* get all edges pointing into the head or condition chain */
1240                 irg_walk_graph(current_ir_graph, get_head_entries, NULL, NULL);
1241                 loop_inversion_walk(cur_head_outs);
1242
1243                 DEL_ARR_F(cur_head_outs);
1244         }
1245
1246         DEBUG_ONLY(dump_ir_block_graph(current_ir_graph, "-inversed2"));
1247
1248         /* FREE */
1249         DEL_ARR_F(cond_chain_entries);
1250         ir_free_resources(current_ir_graph, IR_RESOURCE_BLOCK_MARK);
1251 }
1252
1253 /*  */
1254 static void analyze_loop(ir_loop *loop)
1255 {
1256         /* Init new for every loop */
1257         cur_loop = loop;
1258
1259         loop_cf_head = NULL;
1260         loop_cf_head_valid = 1;
1261         loop_inv_head = NULL;
1262         loop_peeled_head = NULL;
1263
1264         loop_info.calls = 0;
1265         loop_info.invariant_loads = 0;
1266         loop_info.loads = 0;
1267         loop_info.stores = 0;
1268         loop_info.opnodes_n = 0;
1269         loop_info.blocks = 0;
1270
1271         DB((dbg, LEVEL_1, "  >>>> current loop includes node %ld <<<\n", get_irn_node_nr(get_loop_node(loop, 0))));
1272
1273         decision_maker();
1274
1275         DB((dbg, LEVEL_1, "    <<<< end of loop with node %ld >>>>\n", get_irn_node_nr(get_loop_node(loop, 0))));
1276 }
1277
1278 /* Find most inner loops and send them to analyze_loop */
1279 static void analyze_inner_loop(ir_loop *loop)
1280 {
1281         /* descend into sons */
1282         int sons = get_loop_n_sons(loop);
1283
1284         if (sons==0) {
1285                 analyze_loop(loop);
1286         } else {
1287                 int s;
1288                 for(s=0; s<sons; s++) {
1289                         analyze_inner_loop( get_loop_son(loop, s) );
1290                 }
1291         }
1292 }
1293
1294 /**
1295  *
1296  */
1297 void loop_optimization(ir_graph *irg)
1298 {
1299         ir_loop *loop;
1300         int     sons, nr;
1301
1302         FIRM_DBG_REGISTER(dbg, "firm.opt.loop");
1303         firm_dbg_set_mask(dbg, -1);
1304
1305         DB((dbg, LEVEL_1, " >>> loop optimization (Startnode %ld) <<<\n", get_irn_node_nr(get_irg_start(irg))));
1306
1307         /* Init */
1308         link_node_state_list = NULL;
1309
1310         /* preconditions */
1311         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1312         collect_phiprojs(irg);
1313         ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
1314
1315         set_current_ir_graph(irg);
1316         assure_cf_loop(irg);
1317
1318         /* allocate node_info for additional information on nodes */
1319         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
1320         irg_walk_graph(current_ir_graph, alloc_node_info, NULL, NULL);
1321
1322         loop = get_irg_loop(irg);
1323         sons = get_loop_n_sons(loop);
1324
1325         for (nr=0; nr<sons; nr++) {
1326                 analyze_inner_loop(get_loop_son(loop, nr));
1327         }
1328
1329         /* Free */
1330         free_node_info();
1331         ir_free_resources(irg, IR_RESOURCE_PHI_LIST|IR_RESOURCE_IRN_LINK);
1332
1333         DB((dbg, LEVEL_1, " >>> loop optimization done (Startnode %ld) <<<\n", get_irn_node_nr(get_irg_start(irg))));
1334 }
1335
1336 void firm_init_loop(void) {
1337         FIRM_DBG_REGISTER(dbg, "firm.opt.loop");
1338 }