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

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