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

   1 /**
   2  *
   3  * @file loop_unrolling.c
   4  *
   5  * Project:     libFIRM
   6  * File name:   ir/opt/loop_unrolling.c
   7  * Purpose:     Make loop unrolling.
   8  * Author:      Beyhan Veliev
   9  * Modified by:
  10  * Created:     16.11.2004
  11  * CVS-ID:      $Id$
  12  * Copyright:   (c) 2004 Universität Karlsruhe
  13  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  14  */
  15 #ifdef HAVE_CONFIG_H
  16 #include "config.h"
  17 #endif
  18
  19 #ifdef HAVE_STRING_H
  20 #include <string.h>
  21 #endif
  22 #ifdef HAVE_MALLOC_H
  23 #include <malloc.h>
  24 #endif
  25 #ifdef HAVE_ALLOCA_H
  26 #include <alloca.h>
  27 #endif
  28
  29 #include "loop_unrolling.h"
  30
  31 #include "irnode_t.h"
  32 #include "irgwalk.h"
  33 #include "ircons.h"
  34 #include "irgmod.h"
  35 #include "irloop_t.h"
  36 #include "irgopt_t.h"
  37 #include "irouts.h"
  38 #include "trouts.h"
  39 #include "hashptr.h"
  40 #include "pset.h"
  41 #include "strength_red.h"
  42 #include "compute_loop_info.h"
  43 #include "irdump.h"
  44 #include "irtools.h"
  45
  46 /* We will unroll maximal 4-times.  */
  47 #define MAX_UNROLL 4
  48
  49 /* We will know if the head of the loop to be copy.
  50  * Default "0"  don't copy.*/
  51 static int copy_loop_head;
  52
  53 typedef struct {
  54   ir_node *irn ;                /* Node of the loop to be unrolling*/
  55   ir_node *copy[MAX_UNROLL] ;   /* The copy of the node */
  56 } copies_t;
  57
  58 /**
  59  * Compare two elements of the copies_t set
  60  */
  61 static int set_cmp(const void *elt, const void *key, size_t size)
  62 {
  63   const copies_t *c1 = elt;
  64   const copies_t *c2 = key;
  65
  66   return c1->irn != c2->irn;
  67 }
  68
  69 /**
  70  * Remember the new node in the old node by using a field all nodes have.
  71  */
  72 static INLINE void
  73 set_new_node (ir_node *old, ir_node *new)
  74 {
  75   old->link = new;
  76 }
  77
  78 /*Check if phi in the loop head is.
  79  *
  80  * @param phi               Must be a phi node from the loop.
  81  * @param loop_head         The loop head .
  82  */
  83 static int is_Phi_in_loop_head(ir_node *phi, ir_node *loop_head) {
  84   assert(is_Block(loop_head));
  85   return is_Phi(phi) && (get_nodes_block(phi) == loop_head);
  86 }
  87
  88 /**
  89  * Copies predecessors of node to copies of node.
  90  * If the predecessor is a loop invariant, then the copy get it
  91  * as predecessor, else the copy of the predecessor.
  92  *
  93  * @param l_n                A set, where the node of the loop are saved.
  94  * @param value              A element of the set.
  95  * @param info               Contains information about the induction variable.
  96  * @param unroll_factor      A integer 2 <= unroll_factor <= 4.
  97  * @param env                Free environment pointer.
  98  */
  99 static void
 100 set_preds (set *l_n, copies_t *value, induct_var_info *info, int unroll_factor, void *env)
 101 {
 102   ir_node *loop_head;
 103   int i, p, irn_arity;
 104   copies_t key, *value_pred;
 105   if(value->copy[0] == NULL ||
 106      get_irn_op(value->irn) != get_irn_op(value->copy[0]))
 107     return;
 108
 109   /* The head of the unrolling loop. */
 110   loop_head = get_loop_node(info->l_itervar_phi, 0);
 111   irn_arity = get_irn_arity(value->irn);
 112
 113   for (i = 0; i < irn_arity; i++) {
 114     ir_node *pred = get_irn_n(value->irn, i);
 115
 116     key.irn = pred;
 117     value_pred = set_find(l_n, &key, sizeof(key), HASH_PTR(pred));
 118
 119     if (value->irn != loop_head && !is_Phi_in_loop_head(value->irn, loop_head)) {
 120       if (value_pred == NULL) {
 121               /* Is loop invariant. */
 122               for (p = 0; p < unroll_factor - 1; p++)
 123                 set_irn_n(value->copy[p], i, pred);
 124               /* pred is a loop invariant. The copies of the successors get it as predecessor. */
 125       }
 126       else {
 127               for (p = 0; p < unroll_factor - 1; p++)
 128                 set_irn_n(value->copy[p], i, value_pred->copy[p]);
 129           /* value_pred->irn is a node from the unrolling loop.
 130            * The copies of the successors get the
 131                  * copies of value_pred as predecessor.
 132            */
 133       }
 134     }
 135   }
 136 }
 137
 138 /* Set the backedge of phi in the loop head.The backedge of phis in the loop head
 139  * must now point to the value defined
 140  * in the last copy of the loop body.
 141  *
 142  * @param l_n                A set, where the node of the loop are saved.
 143  * @param value              A phi in the loop head.
 144  * @param info               Contains information about the induction variable.
 145  * @param unroll_factor      A integer 2 <= unroll_factor <= 4.
 146  */
 147 static void
 148 set_phi_backedge(set *l_n, copies_t *value, induct_var_info *info, int unroll_factor)
 149 {
 150   copies_t key, *value_pred;
 151
 152   /* info->op_pred_pos is the backedge position. */
 153   key.irn = get_irn_n(value->irn, info->op_pred_pos);
 154   value_pred = set_find(l_n, &key, sizeof(key), HASH_PTR(key.irn));
 155
 156   /* value->copy[unroll_factor - 2] is the last copy. */
 157   set_Phi_pred(value->irn, info->op_pred_pos, value_pred->copy[unroll_factor - 2]);
 158 }
 159
 160 /**
 161  * Test for a loop head.
 162  *
 163  * Returns true if the node has predecessors in the loop _and_ out of
 164  * the loop.  Then it is a loop head: The loop can be entered through
 165  * this node.
 166  *
 167  * @param n      The node to be tested. Must be a block.
 168  * @param info   Contains the loop information.
 169  */
 170 static int
 171 is_loop_head(ir_node *n, induct_var_info *info)
 172 {
 173   int i, arity;
 174   int some_outof_loop = 0, some_in_loop = 0;
 175
 176   assert(get_irn_op(n) == op_Block);
 177   arity = get_Block_n_cfgpreds(n);
 178
 179   for (i = 0; i < arity; i++) {
 180     ir_node *pred = get_Block_cfgpred(n, i);
 181     assert(pred);
 182     if (is_loop_invariant(pred, get_loop_node(info->l_itervar_phi, 0))) {
 183       some_outof_loop = 1;
 184     } else
 185       some_in_loop = 1;
 186   }
 187
 188   return some_outof_loop && some_in_loop;
 189 }
 190
 191
 192 /**
 193  * Test whether the passed loop is a natural loop.
 194  *
 195  * Returns true if the loop has only one loop header and only a single
 196  * back edge.
 197  *
 198  * @param info  Contains the loop information.
 199  */
 200 static int
 201 is_natural_loop(induct_var_info *info)
 202 {
 203   ir_node *l_node;
 204   int l_n_node = 0, i;
 205
 206   l_n_node = get_loop_n_nodes (info->l_itervar_phi);
 207
 208   for (i = 1; i < (l_n_node); i ++) {
 209     l_node = get_loop_node (info->l_itervar_phi, i);
 210     if (is_loop_head(l_node, info)) return 0;
 211
 212     if (has_backedges(l_node) && i != l_n_node-1) return 0;
 213   }
 214
 215   return 1;
 216 }
 217
 218 /**
 219  * Search for all nodes of a loop.
 220  *
 221  * @param node       The induction variable of the loop.
 222  * @param loop_head  The head of the loop.
 223  * @param l_n        A set, where the node of the loop are saved.
 224  */
 225 static void
 226 find_loop_nodes(ir_node *node, ir_node *loop_head, set *l_n)
 227 {
 228   int i;
 229   copies_t key, *value;
 230
 231   /* Add this node to the list. */
 232   key.irn  = node;
 233
 234   /* Initialize all copies of the added node with NULL.*/
 235   for (i = 0; i < 4; ++i)
 236     key.copy[i] = NULL;
 237   value = set_insert(l_n, &key, sizeof(key), HASH_PTR(key.irn));
 238
 239   /* Add all outs of this node to the list, if they are within the loop. */
 240   for (i = get_irn_n_outs(node) - 1; i >= 0; --i) {
 241     ir_node *pred = get_irn_out(node, i);
 242
 243     key.irn = pred;
 244     if (!is_loop_invariant(pred, loop_head)         &&
 245             set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn)) == NULL ) {
 246       find_loop_nodes(pred, loop_head, l_n);
 247     }
 248   }
 249
 250   /* Add all ins if they are within the loop. */
 251   for (i = get_irn_arity(node) - 1; i >=0; --i) {
 252     ir_node *pred = get_irn_n(node, i);
 253
 254     key.irn = pred;
 255     if (!is_loop_invariant(pred, loop_head)         &&
 256               set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn)) == NULL ) {
 257       find_loop_nodes(pred, loop_head, l_n);
 258     }
 259   }
 260 }
 261
 262 /**
 263  * Make a new loop head if copy_head = 1.
 264  *
 265  * @param l_n              A set, where the node of the loop are saved.
 266  * @param info             Contains the loop information.
 267  * @param value            A element of the set.
 268  * @param unroll_factor    A integer 2 <= unroll_factor <= 4.
 269  * @param copy_head        if non-zero, the loop head will be copied
 270  *
 271  */
 272 static void
 273 new_loop_head(set *l_n, induct_var_info *info, copies_t *value, int unroll_factor, int copy_head)
 274 {
 275   int i;
 276   copies_t block, *value_backedge_jmp, *backedge_jmp_block;
 277   /* The  predecessor of the loop head in the  backedge position */
 278   ir_node *backedge_jmp = get_Block_cfgpred(value->irn, info->op_pred_pos);
 279
 280   block.irn          = backedge_jmp;
 281   value_backedge_jmp = set_find(l_n, &block, sizeof(block), HASH_PTR(block.irn));
 282
 283   if (copy_head) {
 284     /* The first copy of the loop head must point to the loop head.*/
 285     value->copy[0] = new_Block(1, &backedge_jmp);
 286     if(info->l_itervar_phi->flags & do_loop){
 287       value_backedge_jmp->copy[0] = new_r_Jmp(current_ir_graph, value->copy[0]);
 288       for (i = 1; i < unroll_factor - 1; ++i) {
 289       /* all other copies must point to the copy before it in the array. */
 290       value->copy[i] = new_Block(1, &backedge_jmp);
 291       value_backedge_jmp->copy[i] = new_r_Jmp(current_ir_graph, value->copy[i]);
 292       }
 293       for (i = 1; i < unroll_factor - 1; ++i){
 294         set_nodes_block(value_backedge_jmp->copy[i-1], get_nodes_block(backedge_jmp));
 295         set_Block_cfgpred (value->copy[i], 0, value_backedge_jmp->copy[i-1]);
 296       }
 297     }else
 298       for (i = 1; i < unroll_factor - 1; ++i) {
 299         /* all other copies must point to the copy before it in the array. */
 300         set_nodes_block(value_backedge_jmp->copy[i-1], get_nodes_block(backedge_jmp));
 301         value->copy[i] = new_Block(1, &value_backedge_jmp->copy[i-1]);
 302       }
 303   }
 304   else {
 305     /* If the loop head must not be copy. block.irn is the successor of the loop head.*/
 306     block.irn          = get_nodes_block(backedge_jmp);
 307     backedge_jmp_block = set_find(l_n, &block, sizeof(block), HASH_PTR(block.irn));
 308
 309     /* The first copy of block.irn point to it.
 310       The another copies muss point to the copy before it in the array.*/
 311     set_irn_n(backedge_jmp_block->copy[0], 0, value_backedge_jmp->irn) ;
 312
 313     for (i = 1; i < unroll_factor - 1; ++i)
 314       set_irn_n(backedge_jmp_block->copy[i], 0, value_backedge_jmp->copy[i - 1]);
 315   }
 316 }
 317
 318 /* Set all copies of the induction variable.
 319  *
 320  * @param phi             A phi node in the loop head block.
 321  * @param phi_pred        The predecessor of the phi along the backedge.
 322  * @param unroll_factor   A integer 2 <= unroll_factor <= 4.
 323  */
 324 static void
 325 set_Phi_copies(copies_t *phi, copies_t *phi_pred, int unroll_factor)
 326 {
 327   int p;
 328
 329   if(phi_pred != NULL){
 330     /* The first copy of Phi node get the node along the backedge as predecessor. The next copies
 331        the copies of this node.*/
 332     phi->copy[0] = phi_pred->irn;
 333     for (p = 1; p < unroll_factor - 1; ++p) {
 334       /* If two phi nodes are in cycle.  */
 335       if (phi_pred->copy[p - 1] == NULL && get_irn_op(phi_pred->irn) == op_Phi) {
 336         if (p & 1)
 337           phi->copy[p] =  phi->irn;
 338         else
 339           phi->copy[p] =  phi_pred->irn;
 340       } else
 341         phi->copy[p] =  phi_pred->copy[p - 1];
 342     }
 343   }else
 344     /* The predecessors of phi are loop invariant and the copies von phi
 345        must be phi it self.*/
 346     for(p = 0; p < unroll_factor - 1; ++p)
 347       phi->copy[p] = phi->irn;
 348 }
 349
 350 /**
 351  * Decide if the loop head must be copied. A head with important nodes
 352  * must be copied.
 353  *
 354  * @param l_n         A set, where the node of the loop are saved.
 355  * @param info        Contains information about the induction variable.
 356  *
 357  * @return non-zero if the loop head must be copied
 358  */
 359 static int
 360 loop_head_nodes(set *l_n, induct_var_info *info)
 361 {
 362   int must_copy = 0;
 363   copies_t *value;
 364   ir_node *loop_head = get_loop_node(info->l_itervar_phi, 0);
 365
 366   for (value = set_first(l_n); value != NULL; value = set_next(l_n))
 367     if (is_no_Block(value->irn) && get_nodes_block(value->irn) == loop_head)
 368       /* If the loop head contains just this nodes, than must not be copy. */
 369       switch (get_irn_opcode(value->irn)) {
 370       case iro_Cond:
 371               break;
 372       case iro_Phi:
 373               break;
 374       case iro_Proj:
 375               break;
 376       case iro_Const:
 377               break;
 378       case iro_Cmp:
 379               break;
 380       default:
 381               must_copy = 1;
 382       }
 383     return must_copy;
 384 }
 385
 386 /** Copy all loop nodes.
 387  *
 388  * @param l_n             Contains all nodes of the loop.
 389  * @param info            Contains the loop information.
 390  * @param unroll_factor   A integer 2 <= unroll_factor <= 4.
 391  */
 392 static void
 393 copy_loop_body(set *l_n, induct_var_info *info, int unroll_factor)
 394 {
 395   int i, opt;
 396   copies_t *value, *info_op, *phi, *loop_h = NULL, key, *value_block;
 397   ir_node *proj_b, *cond, *proj_1, *proj_0, *loop_head;
 398   proj_b = get_irn_out(info->cmp, 0);
 399   cond   = get_irn_out(proj_b, 0);
 400   proj_0 = get_irn_out(cond, 0);
 401   proj_1 = get_irn_out(cond, 1);
 402
 403   loop_head = get_loop_node(info->l_itervar_phi, 0);
 404   /* I will create some nodes and need the optimization to
 405      be set off.*/
 406   opt = get_optimize();
 407   set_optimize(0);
 408
 409   for (value = set_first(l_n); value != NULL; value = set_next(l_n)) {
 410     if(value->irn == loop_head)
 411       loop_h = value;
 412     else if (is_Phi_in_loop_head(value->irn, loop_head))
 413       phi = value;
 414     else if (copy_loop_head){
 415       if(value->irn == proj_0){
 416         for (i = 0; i < unroll_factor - 1; i++)
 417         /* In the copies of the loop head we replace the cmp branche with a jmp node.
 418         This is just for "for" loops."do" loops are handled in function
 419         new_loop_head().*/
 420         value->copy[i] = new_r_Jmp(current_ir_graph, get_nodes_block(value->irn));
 421       }else if(value->irn != proj_b && value->irn != cond &&
 422         value->irn != proj_1)
 423         /* The loop head must be copied. */
 424         for (i = 0; i < unroll_factor - 1; i++){
 425           copy_irn_to_irg(value->irn, current_ir_graph);
 426           value->copy[i] = get_irn_link(value->irn);
 427         }
 428     } else {
 429       /* The loop head and its nodes must not be copied. */
 430       if((value->irn->op == op_Block             &&
 431         value->irn != loop_head)               ||
 432         (value->irn->op != op_Block             &&
 433         get_nodes_block(value->irn) != loop_head)) {
 434         for (i = 0; i<unroll_factor -1; i++) {
 435           copy_irn_to_irg(value->irn, current_ir_graph);
 436           value->copy[i] = get_irn_link(value->irn);
 437         }
 438       }
 439     }
 440   }
 441
 442   /* Treat the loop head block */
 443   new_loop_head(l_n, info, loop_h, unroll_factor, copy_loop_head);
 444   /* I have created the nodes and I set the optimization
 445      to it old value.*/
 446   set_optimize(opt);
 447
 448   /* Similarly treat the Phis in the loop head block. info->op is the node
 449      along the backedges. */
 450   key.irn = info->op;
 451   info_op = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
 452   assert(info_op->irn == get_Phi_pred(info->itervar_phi, info->op_pred_pos));
 453   for (i = 0; i < get_irn_n_outs(loop_head); ++i) {
 454     ir_node *phi = get_irn_out(loop_head, i);
 455
 456     if (is_Phi(phi)) {
 457       copies_t *phi_pred, *phi_op;
 458
 459       key.irn  = get_Phi_pred(phi, info->op_pred_pos); // info->op;
 460       phi_pred = set_find(l_n, &key, sizeof(key), HASH_PTR(key.irn));
 461       key.irn  = phi;
 462       phi_op   = set_find(l_n, &key, sizeof(key), HASH_PTR(key.irn));
 463       set_Phi_copies(phi_op, phi_pred, unroll_factor);
 464     }
 465   }
 466
 467   for (value = set_first(l_n); value != NULL; value = set_next(l_n)) {
 468
 469     /* Set the predecessors of the copies. */
 470     if (copy_loop_head){
 471       set_preds(l_n, value, info, unroll_factor, NULL);
 472     }else if ((value->irn->op != op_Block) && get_nodes_block(value->irn) != loop_head)
 473       set_preds(l_n, value, info, unroll_factor, NULL);
 474
 475     if (is_Phi_in_loop_head(value->irn, loop_head) &&
 476       has_backedges(value->irn))
 477       /* Set the backedge of phis in the loop head. */
 478       set_phi_backedge(l_n, value, info, unroll_factor);
 479
 480     if ((value->irn->op != op_Block) && !is_Phi_in_loop_head(value->irn, loop_head) &&
 481       value->copy[0] != NULL ) {
 482       ir_node *nodes_block = get_nodes_block(value->irn);
 483
 484       if (!copy_loop_head && nodes_block == loop_head)
 485         continue;
 486
 487       key.irn = nodes_block;
 488       value_block = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
 489       /* Set the copy of the node in the accordant copy of its block. */
 490       for(i = 0; i < unroll_factor - 1; i++){
 491         set_nodes_block(value->copy[i], value_block->copy[i]);
 492       }
 493     }
 494   }
 495   /* I must repair some control flow edges, when the loop head
 496      have been copied.*/
 497   if (copy_loop_head && !(info->l_itervar_phi->flags & do_loop)){
 498     key.irn = proj_0;
 499     value   = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
 500     key.irn = get_irn_out(proj_0, 0);
 501     info_op = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
 502     for (i = 0; i < unroll_factor - 1; i++){
 503       set_Block_cfgpred(info_op->copy[i], 0, value->copy[i]);
 504     }
 505   }
 506 }
 507
 508 /**
 509  * Returns non-zero if a Proj node from the loop has a predecessor that
 510  * can throw an exception.
 511  *
 512  * @param node  A Proj node from the loop.
 513  *
 514  * @return non-zero if the predecessor of the Proj node can throw an exception
 515  */
 516 static int is_exception_possible(ir_node *node)
 517 {
 518   ir_node *pred = get_Proj_pred(node);
 519
 520   /* only fragile ops can throw an exception */
 521   if (! is_fragile_op(pred))
 522     return 0;
 523
 524   /*
 525    * fragile ops that are known NOT to throw
 526    * an exception if their pin_state is op_pin_state_floats
 527    */
 528   return get_irn_pinned(pred) != op_pin_state_floats;
 529 }
 530
 531 /**
 532  * If a node from the loop is predecessor of the end block, then the end block must get all copies
 533  * of this node as predecessors. This is possible with function calls in the unrolling loop.
 534  *
 535  * @param end_block          The end block.
 536  * @param loop_head          The head of the unrolling loop.
 537  * @param l_n                Contains all nodes of the loop.
 538  * @param loop_endblock_outs The set loop_endblock_outs contains all predecessors
 539  *                           of the end block from the unrolling loop.
 540  * @param unroll_factor      A integer 2 <= unroll_factor <= 4.
 541  */
 542 static void
 543 new_end_block(ir_node *end_block, ir_node *loop_head, set *l_n, set *loop_endblock_outs, int unroll_factor)
 544 {
 545   copies_t key, *value;
 546   int set_el, new_preds, all_new_preds, i, q;
 547   int old_preds = get_Block_n_cfgpreds(end_block);   /* All old predecessors of the end block. */
 548   ir_node **all_in;
 549
 550   for (i = 0; i < old_preds; i++) {
 551     ir_node *pred = get_Block_cfgpred(end_block, i);
 552      key.irn = pred;
 553      value = NULL;
 554      value = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
 555
 556      /* If a predecessor of the end block is a Proj from the unrolling loop (for function calls) .*/
 557      if (get_irn_op(pred) == op_Proj && is_exception_possible(pred) && value != NULL &&
 558                !(!copy_loop_head && get_nodes_block(pred) == loop_head))
 559        value =  set_insert(loop_endblock_outs, &key, sizeof(key), HASH_PTR(key.irn));
 560   }
 561
 562   /* The set loop_endblock_outs contains all predecessors of the end block from the unrolling loop,
 563    * set_el the amount of such nodes.
 564    */
 565   set_el = set_count (loop_endblock_outs);
 566
 567   /* If the end block haven't such predecessors, we are finished. */
 568   if (!set_el) return;
 569
 570   new_preds = (unroll_factor - 1) * set_el;          /* All new predecessors of the end block */
 571   all_new_preds = old_preds + new_preds;             /* All predecessors of this block. */
 572   all_in = alloca(sizeof(*all_in) * all_new_preds);  /* A array with size for all predecessors of this block. */
 573
 574   for (i = 0; i < old_preds; i++)
 575     all_in[i] = get_Block_cfgpred(end_block, i);    /* The old predecessors. */
 576
 577   value = set_first(loop_endblock_outs);
 578
 579   for (; value != NULL; value = set_next(loop_endblock_outs)) {
 580     key.irn = value->irn;
 581     value = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
 582     for (q = 0; q < unroll_factor - 1 ; q++) {
 583       all_in[i++] = value->copy[q];                 /* The new predecessors. */
 584     }
 585
 586   }
 587
 588   /* Replace the old predecessors of the end block wit´h the new ones. */
 589   set_irn_in(end_block, all_new_preds, all_in);
 590 }
 591
 592 /** new_after_loop_block
 593  *
 594  * The after loop block must examine the possible exceptions in the loop.
 595  * If a (Proj) node from the loop is predecessor of this block, then the
 596  * after loop block must have as well all copies of this node as predecessors.
 597  *
 598  * @param l_n             Contains all nodes of the loop.
 599  * @param block           A block after the loop.
 600  * @param loop_in         A node from the loop, that is predecessor of the end block.
 601  * @param unroll_factor   An integer 2 <= unroll_factor <= 4.
 602  */
 603 static void
 604 new_after_loop_block (set *l_n, ir_node* block, copies_t *loop_in, int unroll_factor)
 605 {
 606   copies_t key, *value;
 607   int i, p, q, s, old_preds, new_preds, all_new_preds ;
 608   ir_node **all_in;
 609
 610   /* The node from the unrolling loop must be a Proj. */
 611   if (loop_in->irn->op != op_Proj) return;
 612
 613   old_preds = get_Block_n_cfgpreds(block);     /* All old predecessors of this block. */
 614   new_preds = old_preds * (unroll_factor - 1); /* All new predecessors of this block. */
 615   all_new_preds = old_preds + new_preds;       /* All predecessors of this block. */
 616
 617   all_in = alloca(sizeof(*all_in) * all_new_preds); /* An array with size for all predecessors of this block. */
 618
 619   for (i = 0 ; i < old_preds; i++)
 620     all_in[i] = get_Block_cfgpred(block, i);      /* The old predecessors. */
 621
 622   q = old_preds;
 623   for (i = 0; i < old_preds; i++){
 624     key.irn = all_in[i];
 625     value = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
 626     p = 0;
 627     for (s = 0; s < (unroll_factor - 1); s++) {
 628       all_in[q++] = value->copy[p++];          /* The new predecessors. */
 629     }
 630   }
 631   /* Replace the old predecessors of the end block whit the new one. */
 632   set_irn_in(block, all_new_preds, all_in);
 633 }
 634
 635 /** new_after_loop_node
 636  *
 637  * An after loop node (phi or call) must examine the possible exceptions in the loop.
 638  * If a (Proj) node from the loop is predecessor of this node, then the after loop
 639  * node must have as well all copies of this node as predecessors.
 640  *
 641  * @param l_n             Contains all nodes of the loop.
 642  * @param loop_outs       Contains nodes after the loop,that have as predecessor a node from the loop.
 643  * @param node            A node after the loop.
 644  * @param loop_in         A node (Proj) from the loop, that is predecessor of *node.
 645  * @param unroll_factor   An integer 2 <= unroll_factor <= 4.
 646  */
 647 static void
 648 new_after_loop_node(set *l_n, set *loop_outs, ir_node *node, copies_t *loop_in, int unroll_factor)
 649 {
 650   ir_node *pred, *block_pred = NULL, *node_block, *new_phi;
 651   int phi = 0, old_preds, new_preds, all_new_preds, p, q, i, s;
 652   copies_t key, *value = NULL;
 653   ir_node **all_in;
 654
 655   old_preds = get_irn_arity(node);            /* All old predecessors of this node. */
 656   new_preds =old_preds * (unroll_factor - 1); /* All new predecessors of this block. */
 657   all_new_preds = old_preds + new_preds;      /* All predecessors of this block. */
 658
 659   all_in  = alloca(sizeof(*all_in) * all_new_preds); /* An array with size for all predecessors of this block. */
 660
 661   /* Verification Predecessors, successors and operation of node and loop_in.
 662    * loop_in must be a Proj node.
 663    */
 664   if (loop_in->irn->op != op_Proj) return;
 665   /* Node must be operation Phi with mode memory or a Call node. */
 666   if (get_irn_op(node) == op_Phi  &&
 667       get_irn_mode(node) == mode_M){
 668     /* If node is a Phi node,then must have a Call node as successor. */
 669     for (i = 0; i < get_irn_n_outs(node); i++)
 670       if (get_irn_op(get_irn_out(node, i)) == op_Call) {
 671               phi = 1;
 672         break;
 673       }
 674
 675     if (!phi) return;
 676   }
 677
 678   /* The predecessor of loop_in must not be a loop invariant. */
 679   pred = get_Proj_pred(loop_in->irn);
 680   key.irn = pred;
 681   value = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
 682   if (! value) return;
 683
 684   node_block = get_nodes_block(node);
 685
 686   /* The block of node must also have a (Proj) predecessor from the unrolling loop. */
 687   for (i = 0; i < get_Block_n_cfgpreds(node_block); i++) {
 688     block_pred = get_Block_cfgpred(node_block, i);
 689
 690     if (get_irn_op(block_pred) == op_Proj) {
 691       if (get_Proj_pred(block_pred) == pred)
 692         break;
 693     }
 694     else {
 695       block_pred = NULL;
 696     }
 697   }
 698
 699   if (! block_pred) return;
 700
 701   key.irn = block_pred;
 702   value   = set_find(l_n, &key, sizeof(key), HASH_PTR(key.irn));
 703
 704   if (! value)
 705     return;
 706   else
 707     new_after_loop_block(l_n, node_block, value, unroll_factor);
 708
 709   for (i = 0; i < old_preds; ++i)
 710     all_in[i] = get_irn_n(node, i);  /* The old predecessors. */
 711
 712   q = old_preds;
 713   for (i = 0; i < old_preds; ++i) {
 714     key.irn = all_in[i];
 715     value = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
 716     p = 0;
 717     for (s = 0; s < (unroll_factor - 1); ++s) {
 718       all_in[q] = value->copy[p];  /* The new predecessors. */
 719       p++;
 720       q++;
 721     }
 722   }
 723   /* A new phi node with the new predecessors. */
 724   new_phi = new_r_Phi(current_ir_graph, get_nodes_block(node), all_new_preds,all_in,
 725                        get_irn_mode(node));
 726
 727   if (phi)
 728     exchange(node, new_phi);
 729   else{
 730     for (i = 0; i < get_irn_arity(node); ++i)
 731       if (get_irn_n(node, i) == pred)
 732         set_irn_n(node, i, new_phi);
 733   }
 734
 735   /* The set loop_outs contains the visited nodes and their blocks. */
 736   key.irn = node;
 737   value = set_insert(loop_outs, &key, sizeof(key), HASH_PTR(key.irn));
 738   key.irn = get_nodes_block(node);
 739   value = set_insert(loop_outs, &key, sizeof(key), HASH_PTR(key.irn));
 740 }
 741
 742
 743 /* Set the outs of the unrolling loop. All loop outs of a node muss now
 744  * point to the last copy of it. Just phi nodes in the loop head and proj
 745  * nodes save it outs. The all copies of some Projs  have too outs.
 746  *
 747  * @param l_n                Contains all nodes of the loop.
 748  * @param loop_outs          The set contains the visited and changed loop outs.
 749  * @param loop_endblock_outs The set loop_endblock_outs contains all predecessors
 750  *                           of the end block from the unrolling loop.
 751  * @param info               Contains the loop information.
 752  * @param unroll_factor      A integer 2 <= unroll_factor <= 4.
 753  */
 754 static void
 755 set_loop_outs(set *l_n, set *loop_outs, set *loop_endblock_outs, induct_var_info *info, int unroll_factor)
 756 {
 757   copies_t *value, key;
 758   int i, p;
 759   ir_node *loop_head = get_loop_node(info->l_itervar_phi, 0);
 760   ir_node *end_block = get_irg_end_block(current_ir_graph);
 761
 762   for (value = set_first(l_n); value != NULL; value = set_next(l_n)){
 763     if(get_irn_node_nr(value->irn) == 35047)
 764       printf("\nHi\n");
 765     if (! is_Phi_in_loop_head(value->irn, loop_head) &&
 766         (get_irn_opcode(value->irn) == iro_Proj && value->copy[0] != NULL))
 767       for (i = 0; i < get_irn_n_outs(value->irn); ++i) {
 768         key.irn = get_irn_out(value->irn, i);
 769
 770         /* Search for loop outs. */
 771         if (set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn)) == NULL)
 772           if ((key.irn->op == op_Block && get_Block_dom_depth(key.irn)  >
 773                get_Block_dom_depth(loop_head))                          ||
 774               (key.irn->op != op_Block && get_Block_dom_depth(get_nodes_block(key.irn)) >
 775                get_Block_dom_depth(loop_head))) {
 776
 777             for (p = 0; p < get_irn_arity(key.irn); p++)
 778               if (value->irn == get_irn_n(key.irn, p)) {
 779                 if (get_irn_op(value->irn) == op_Proj && is_exception_possible(value->irn)) {
 780                   if (set_find(loop_outs, &key, sizeof(key), HASH_PTR(key.irn)) == NULL) {
 781                     /* If the loop out is for exceptions in the loop. */
 782                     if ((get_irn_op(key.irn) == op_Phi && get_irn_mode(key.irn) == mode_M) ||
 783                         get_irn_op(key.irn) == op_Call)
 784                       new_after_loop_node(l_n,loop_outs, key.irn, value, unroll_factor);
 785                     else
 786                       continue;
 787                   } else
 788                     continue;
 789                 } else
 790                   /* Loop outs in the loop head must be not changed.*/
 791                   if(get_nodes_block(value->irn) != loop_head)
 792                     set_irn_n(key.irn, p, value->copy[unroll_factor-2]);
 793               }
 794           }
 795       }
 796   }
 797   /* This function searches for loop outs associated with function call in the unrolling loop. */
 798   new_end_block (end_block, loop_head, l_n, loop_endblock_outs, unroll_factor);
 799 }
 800
 801 /**
 802  * Unroll the loop body with a factor that must be power of two.
 803  * Called from a post walker.
 804  *
 805  * @param n        An IR node.
 806  * @param env      points to a result
 807  */
 808 static void do_loop_unroll(ir_node *n, void *env)
 809 {
 810   int *unroll_done = env;
 811   induct_var_info info;
 812   copies_t *value;
 813   set *loop_nodes, *loop_outs, *loop_endblock_outs;
 814   ir_node *phi_init, *loop_head;
 815   ir_node *backedge_jmp;
 816   int l_sons = 0, unroll_factor = 0;
 817   tarval *init, *iter_end, *iter_increment,*tarval_null, *tarval_one, *tarval_three, *tarval_two, *diff, *iter_number;
 818   int backedge_pos;
 819
 820   copy_loop_head = 0;
 821   info.itervar_phi = n;
 822
 823   /* The IR node must be a induction variable. */
 824   if (get_irn_op(n) == op_Phi) {
 825     if (is_induction_variable (&info) == NULL)
 826       return;
 827   }
 828   else
 829     return;
 830
 831   /* Brute force limiting of loop body size. */
 832   if (get_loop_n_nodes(info.l_itervar_phi) > 2 ) return;
 833
 834   /* Only unroll loops that compare against a constant for exiting. */
 835   if (info.cmp == NULL) return;
 836
 837   /* We only want to unroll innermost loops. */
 838   l_sons = get_loop_n_sons(info.l_itervar_phi);
 839   if ( l_sons != 0)
 840     return;
 841   /* "do" loops are not implementit gut for this reason
 842       at the time we don't unroll them.*/
 843   if(info.l_itervar_phi->flags & do_loop)
 844     return;
 845
 846   phi_init = get_Phi_pred(info.itervar_phi, info.init_pred_pos);
 847
 848   if ((!(info.l_itervar_phi->flags & loop_is_count_loop))  ||
 849       (info.l_itervar_phi->flags & loop_is_endless)        ||
 850       (info.l_itervar_phi->flags & loop_is_dead)           ||
 851       (info.l_itervar_phi->flags & once))
 852     return;
 853
 854   init           = info.l_itervar_phi->loop_iter_start;
 855   iter_end       = info.l_itervar_phi->loop_iter_end;
 856   iter_increment = info.l_itervar_phi->loop_iter_increment;
 857   tarval_null = get_mode_null(get_tarval_mode(iter_increment));
 858   tarval_one  = get_mode_one(get_tarval_mode(init));
 859
 860   if(tarval_is_double(init) || tarval_is_double(iter_end) || tarval_is_double(iter_increment))
 861     return;
 862
 863   if((tarval_is_negative(init) && tarval_is_negative(iter_end)) ||
 864      (!tarval_is_negative(init) && !tarval_is_negative(iter_end)) ||
 865      (tarval_is_null(init) || tarval_is_null(iter_end)))
 866     diff = tarval_abs(tarval_sub(iter_end, init));
 867   else
 868     diff = tarval_add(tarval_abs(iter_end),tarval_abs(init));
 869
 870   iter_increment = tarval_abs(iter_increment);
 871
 872   if(!(info.l_itervar_phi->flags & do_loop))
 873     diff = tarval_add(diff, tarval_one);
 874   /* Test for the value of unroll factor. */
 875   if (tarval_cmp(tarval_mod(diff,iter_increment), tarval_null) == pn_Cmp_Eq)
 876     iter_number = tarval_div(diff, iter_increment);
 877   else
 878     return;
 879   tarval_two = tarval_add(tarval_one, tarval_one);
 880   tarval_three = tarval_add(tarval_two,tarval_one);
 881
 882   if (tarval_cmp(tarval_mod(iter_number, tarval_three), tarval_null) == pn_Cmp_Eq)
 883     unroll_factor = 3;
 884   else if (tarval_cmp(tarval_mod(iter_number, tarval_two), tarval_null) == pn_Cmp_Eq)
 885     unroll_factor = 2;
 886   else return;
 887
 888   if (get_firm_verbosity())
 889     printf("\nloop unrolling with factor %d \n", unroll_factor);
 890
 891   /* ok, we will do unrolling */
 892   *unroll_done += 1;
 893
 894   /* The unroll factor must be less than 4. */
 895   assert(unroll_factor <= MAX_UNROLL);
 896
 897   loop_head = (is_natural_loop(&info)) ? get_loop_node(info.l_itervar_phi, 0) : NULL;
 898
 899   assert(loop_head != NULL && is_Block(loop_head));
 900
 901   /* We assume, the loop head has exactly one backedge.  The position of
 902      the backedge is in the following variable: */
 903   backedge_pos = (is_backedge(loop_head, 0)) ? 0:1;
 904
 905   /* A set with the nodes to copy. */
 906   loop_nodes = new_set(set_cmp, 8);
 907   /* A set with the loop outs for exceptions. */
 908   loop_outs =  new_set(set_cmp, 8);
 909
 910   /* A set containing all predecessors
 911      of the end block from the unrolling loop. */
 912   loop_endblock_outs = new_set(set_cmp, 8);
 913   /* Find all nodes of the unrolling loop. */
 914   find_loop_nodes(info.itervar_phi, get_loop_node(info.l_itervar_phi, 0), loop_nodes);
 915
 916   /* Decide if the loop head to be copy.*/
 917   copy_loop_head = loop_head_nodes(loop_nodes, &info);
 918
 919   /* Copy all nodes of the unrolling loop, that muss be copy. */
 920   copy_loop_body(loop_nodes, &info, unroll_factor);
 921
 922   backedge_jmp = get_Block_cfgpred(loop_head, backedge_pos);
 923
 924   /* Set the backedge of the loop head. */
 925   for (value = set_first(loop_nodes); value != NULL; value = set_next(loop_nodes)) {
 926     if (value->irn == backedge_jmp)
 927       set_Block_cfgpred(loop_head, backedge_pos, value->copy[unroll_factor-2]);
 928   }
 929   set_loop_outs(loop_nodes, loop_outs, loop_endblock_outs, &info, unroll_factor);
 930 }
 931
 932 /* Performs loop unrolling for the passed graph. */
 933 void optimize_loop_unrolling(ir_graph *irg /* unroll factor, max body size */)
 934 {
 935   ir_graph *rem;
 936   int unroll_done = 0;
 937
 938   if ( !get_opt_loop_unrolling()) return;
 939
 940   rem = current_ir_graph;
 941   current_ir_graph = irg;
 942
 943   /* -- Precompute some information -- */
 944
 945   /* Call algorithm that computes the loop information */
 946   // construct_backedges(irg);
 947   compute_loop_info(irg);
 948   /* Call algorithm that computes the backedges */
 949   // construct_cf_backedges(irg);
 950
 951   /* Call algorithm that computes the dominator trees. */
 952   assure_doms(irg);
 953
 954   /* Call algorithm that computes the out edges */
 955   assure_irg_outs(irg);
 956
 957   collect_phiprojs(irg);
 958
 959   /* -- Search expressions that can be optimized -- */
 960   irg_walk_graph(irg, NULL, do_loop_unroll, &unroll_done);
 961
 962   if (unroll_done) {
 963     /* unrolling was done, all info is invalid */
 964     set_irg_doms_inconsistent(irg);
 965     set_irg_outs_inconsistent(irg);
 966     set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_inconsistent);
 967     set_trouts_inconsistent();
 968     set_irg_callee_info_state(irg, irg_callee_info_inconsistent);
 969   }
 970
 971   current_ir_graph = rem;
 972 }