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