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