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