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
  17 # include "loop_unrolling.h"
  18
  19 # include "irgwalk.h"
  20 # include "ircons.h"
  21 # include "irgmod.h"
  22 # include "irloop_t.h"
  23 # include "irgopt_t.h"
  24 # include "irnode_t.h"
  25 # include "irouts.h"
  26 # include "hashptr.h"
  27 # include "pset.h"
  28 # include "strength_red.h"
  29
  30 #define MAX_UNROLL 4
  31
  32 /*We will know if the head of the loop to be copy.
  33  * Default don't copy.*/
  34 static int copy_loop_head = 0;
  35
  36 typedef struct {
  37   ir_node *irn ;                /* Node of the loop to be unrolling*/
  38   ir_node *copy[MAX_UNROLL] ;   /* The copy of the node */
  39 } copies_t;
  40
  41 /**
  42  * compare two elements of the copies_t set
  43  */
  44 static int set_cmp(const void *elt, const void *key, size_t size)
  45 {
  46   const copies_t *c1 = elt;
  47   const copies_t *c2 = key;
  48
  49   return c1->irn != c2->irn;
  50 }
  51
  52 static INLINE int * new_backedge_arr(struct obstack *obst, int size)
  53 {
  54   int *res = NEW_ARR_D (int, obst, size);
  55   memset(res, 0, sizeof(int) * size);
  56   return res;
  57 }
  58
  59 static INLINE void new_backedge_info(ir_node *n) {
  60   switch(get_irn_opcode(n)) {
  61   case iro_Block:
  62     n->attr.block.cg_backedge = NULL;
  63     n->attr.block.backedge = new_backedge_arr(current_ir_graph->obst, get_irn_arity(n));
  64     break;
  65   case iro_Phi:
  66     n->attr.phi_backedge = new_backedge_arr(current_ir_graph->obst, get_irn_arity(n));
  67     break;
  68   case iro_Filter:
  69     n->attr.filter.backedge = new_backedge_arr(current_ir_graph->obst, get_irn_arity(n));
  70     break;
  71   default: ;
  72   }
  73 }
  74
  75 /**
  76  * Remember the new node in the old node by using a field all nodes have.
  77  */
  78
  79 static INLINE void
  80 set_new_node (ir_node *old, ir_node *new)
  81 {
  82   old->link = new;
  83 }
  84
  85 /**
  86  * Copies the node to the new obstack. The Ins of the new node point to
  87  * the predecessors on the old obstack.  For block/phi nodes not all
  88  * predecessors might be copied.  n->link points to the new node.
  89  * For Phi and Block nodes the function allocates in-arrays with an arity
  90  * only for useful predecessors.  The arity is determined by counting
  91  * the non-bad predecessors of the block.
  92  *
  93  * @param n    The node to be copied
  94  * @param env  if non-NULL, the node number attribute will be copied to the new node
  95  */
  96
  97 static void
  98 copy_node (ir_node *n, void *env)
  99 {
 100   ir_node *nn, *block;
 101   int new_arity;
 102   opcode op = get_irn_opcode(n);
 103   int copy_node_nr = env != NULL;
 104
 105   /* The end node looses it's flexible in array.  This doesn't matter,
 106      as dead node elimination builds End by hand, inlineing doesn't use
 107      the End node. */
 108   /* assert(n->op == op_End ||  ((_ARR_DESCR(n->in))->cookie != ARR_F_MAGIC)); */
 109
 110   if (op == iro_Bad)
 111     /* node copied already */
 112     return;
 113
 114   new_arity = get_irn_arity(n);
 115
 116   nn = new_ir_node(get_irn_dbg_info(n),
 117            current_ir_graph,
 118            block,
 119            get_irn_op(n),
 120            get_irn_mode(n),
 121            new_arity,
 122            get_irn_in(n));
 123
 124
 125   /* Copy the attributes.  These might point to additional data.  If this
 126      was allocated on the old obstack the pointers now are dangling.  This
 127      frees e.g. the memory of the graph_arr allocated in new_immBlock. */
 128   copy_node_attr(n, nn);
 129   new_backedge_info(nn);
 130   set_new_node(n, nn);
 131
 132 #if DEBUG_libfirm
 133   if (copy_node_nr) {
 134     /* for easier debugging, we want to copy the node numbers too */
 135     nn->node_nr = n->node_nr;
 136   }
 137 #endif
 138
 139 }
 140
 141 static int is_Phi_in_loop_head(ir_node *phi, ir_node *loop_head) {
 142   assert(is_Block(loop_head));
 143   return is_Phi(phi) && (get_nodes_block(phi) == loop_head);
 144 }
 145
 146 /**
 147  * Copies predecessors of node to copies of node.
 148  * If the predecessor is a loop invariant, then the copy get it
 149  * as predecessor, else the copy of the predecessor.
 150  *
 151  * @param *l_n                A set, where the node of the loop are saved.
 152  * @param *value              A element of the set.
 153  * @param *info               Contains information about the induction variable.
 154  * @param *unroll_factor      A integer power of 2.
 155  * @param *env                Free environment pointer.
 156  */
 157 static void
 158 set_preds (set *l_n, copies_t *value, induct_var_info *info, int unroll_factor, void *env)
 159 {
 160   int i, irn_arity, p;
 161   copies_t *value_pred;
 162
 163   ir_node *loop_head = get_loop_node(info->l_itervar_phi, 0);
 164
 165   irn_arity = get_irn_arity(value->irn);
 166
 167   for (i = 0; i < irn_arity; i++) {
 168     ir_node *pred = get_irn_n(value->irn, i);
 169
 170     copies_t key;
 171
 172     key.irn = pred;
 173     value_pred = set_find(l_n, &key, sizeof(key), HASH_PTR(pred));
 174
 175     if (value->irn != loop_head && !is_Phi_in_loop_head(value->irn, loop_head)) {
 176       if (value_pred == NULL) {
 177       /* Is loop invariant. */
 178     for(p = 0; p < unroll_factor -1; p++)
 179       set_irn_n (value->copy[p], i, pred);
 180
 181       } else
 182     for(p = 0; p < unroll_factor -1; p++)
 183       set_irn_n (value->copy[p], i, value_pred->copy[p]);
 184     }
 185   }
 186 }
 187
 188 /* Set the backedge of phi in the loop head.The backedge of phis in the loop head
 189  * must now point to the value defined
 190  * in the last copie of the loop body.
 191  *
 192  * @param *l_n                A set, where the node of the loop are saved.
 193  * @param *value              A phi in the loop head.
 194  * @param *info               Contains information about the induction variable.
 195  * @param *unroll_factor      A integer power of 2.
 196  */
 197 static void
 198 set_phi_backedge(set *l_n, copies_t *value, induct_var_info *info, int unroll_factor)
 199 {
 200   copies_t key, *value_pred;
 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   set_Phi_pred(value->irn, info->op_pred_pos, value_pred->copy[unroll_factor - 2]);
 205 }
 206
 207 /** Test for a loop head.
 208  *
 209  *  Returns true if the node has predecessors in the loop _and_ out of
 210  *  the loop.  Then it is a loop head: The loop can be entered through
 211  *  this node.
 212  *
 213  *  @param *n      The node to be tested.
 214  *  @param *info   Contains the loop information.
 215  */
 216 static int
 217 is_loop_head(ir_node *n, induct_var_info *info)
 218 {
 219   int i, arity;
 220   int some_outof_loop = 0, some_in_loop = 0;
 221
 222   assert(get_irn_op(n) == op_Block);
 223   arity = get_Block_n_cfgpreds(n);
 224
 225   for (i = 0; i < arity; i++) {
 226     ir_node *pred = get_Block_cfgpred(n, i);
 227     assert(pred);
 228     if (is_loop_invariant(pred, get_loop_node(info->l_itervar_phi, 0))) {
 229       some_outof_loop = 1;
 230     } else
 231       some_in_loop = 1;
 232   }
 233
 234   return some_outof_loop && some_in_loop;
 235 }
 236
 237
 238 /** Test wether the passed loop is a natural loop.
 239  *
 240  * Returns true if the loop has only one loop header and only a single
 241  * back edge.
 242  *
 243  * @param *info  Contains the loop information.
 244  */
 245 static int
 246 is_natural_loop ( induct_var_info *info)
 247 {
 248   ir_node *l_node;
 249   int i, l_n_node = 0;
 250   l_n_node = get_loop_n_nodes (info->l_itervar_phi);
 251
 252   for (i = 1; i < (l_n_node); i ++) {
 253     l_node = get_loop_node (info->l_itervar_phi, i);
 254     if (is_loop_head(l_node, info)) return 0;
 255
 256     if (has_backedges(l_node) && i != l_n_node-1) return 0;
 257   }
 258
 259   return 1;
 260 }
 261
 262 /** Serch for all nodes of a loop.
 263  *
 264  * @param  *node       The induction variable of the loop.
 265  * @param  *loop_head  The head of the loop.
 266  * @param  *l_n        A set, where the node of the loop are saved.
 267  */
 268 static void
 269 find_loop_nodes(ir_node *node, ir_node *loop_head, set *l_n)
 270 {
 271   int i;
 272   copies_t key, *value;
 273
 274   /* Add this node to the list. */
 275   key.irn  = node;
 276   for(i = 0; i < 4 ;i++)
 277     key.copy[i] = NULL;
 278   value = set_insert(l_n, &key, sizeof(key), HASH_PTR(key.irn));
 279
 280   /* Add all outs of this node to the list, if they are within the loop. */
 281   for (i = get_irn_n_outs(node) - 1; i >= 0; i--) {
 282     ir_node *pred = get_irn_out(node, i);
 283     key.irn = pred;
 284     if (!is_loop_invariant(pred, loop_head)         &&
 285     set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn)) == NULL ) {
 286       find_loop_nodes(pred, loop_head, l_n);
 287     }
 288   }
 289
 290   /* Add all ins if they are within the loop. */
 291   for(i = get_irn_arity(node) -1; i >=0; i--) {
 292     ir_node *pred = get_irn_n(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
 301 /* Make a new loop head if copy_loop_head = 1.
 302  *
 303  * @param *l_n              A set, where the node of the loop are saved.
 304  * @param *info             Contains the loop information.
 305  * @param *value            A element of the set.
 306  * @param *unroll_factor    A integer power of 2.
 307  *
 308  */
 309 static void
 310 new_loop_head (set *l_n, induct_var_info *info, copies_t *value, int unroll_factor)
 311 {
 312   copies_t block, *value_backedge_jmp, *backedge_jmp_block;
 313   int i;
 314
 315   ir_node *backedge_jmp = get_Block_cfgpred(value->irn, info->op_pred_pos);
 316   block.irn = backedge_jmp;
 317
 318   value_backedge_jmp = set_find( l_n, &block, sizeof(block), HASH_PTR(block.irn));
 319   if(copy_loop_head){
 320     ir_node *new_loop_head = new_Block(1, &backedge_jmp);
 321     value->copy[0] = new_loop_head;
 322
 323     for(i = 1; i<unroll_factor - 1; i++){
 324       ir_node *new_loop_head1 = new_Block(1, &value_backedge_jmp->copy[i-1]);
 325       value->copy[i] = new_loop_head1;
 326     }
 327   }else{
 328
 329     block.irn = get_nodes_block(backedge_jmp);
 330     backedge_jmp_block =  set_find( l_n, &block, sizeof(block), HASH_PTR(block.irn));
 331
 332     set_irn_n(backedge_jmp_block->copy[0], 0, value_backedge_jmp->irn) ;
 333
 334     for(i = 1; i<unroll_factor - 1; i++)
 335       set_irn_n(backedge_jmp_block->copy[i], 0, value_backedge_jmp->copy[i - 1]);
 336   }
 337
 338 }
 339
 340 /* Set all copies of the induction variable.
 341  *
 342  * @param *phi             A phi node in the loop head block.
 343  * @param *phi_pred        The predecessor of the phi along the backedge.
 344  * @param *unroll_factor   A integer power of 2.
 345  *
 346  */
 347 static void
 348 set_Phi_copies(copies_t *phi, copies_t *phi_pred, int unroll_factor)
 349 {
 350   int p;
 351   phi->copy[0] = phi_pred->irn;
 352   for(p = 1; p < unroll_factor -1; p++)
 353     phi->copy[p] =  phi_pred->copy[p -1];
 354 }
 355
 356 /* Decide if the loop head to be copy. A head with important nodes
 357  * mus be copy.
 358  *
 359  * @param *l_n                A set, where the node of the loop are saved.
 360  * @param *info               Contains information about the induction variable.
 361  */
 362 static void
 363 loop_head_nodes(set *l_n, induct_var_info *info)
 364 {
 365   copies_t *value;
 366   ir_node *loop_head = get_loop_node(info->l_itervar_phi, 0);
 367
 368   for (value = set_first(l_n); value != NULL; value = set_next(l_n))
 369     if(value->irn->op != op_Block &&
 370        get_nodes_block(value->irn) == loop_head)
 371       switch(get_irn_opcode(value->irn)) {
 372       case iro_Cond:
 373     break;
 374       case iro_Phi:
 375     break;
 376       case iro_Proj:
 377     break;
 378       case iro_Const:
 379     break;
 380       case iro_Cmp:
 381     break;
 382       default:
 383     copy_loop_head = 1;
 384       }
 385 }
 386
 387 /** Copy all loop nodes.
 388  *
 389  * @param *l_n    Contains all nodes of the loop.
 390  * @param *info   Contains the loop information.
 391  * @param *unroll_factor   A integer power of 2.
 392  */
 393 static void
 394 copy_loop_body(set *l_n, induct_var_info *info, int unroll_factor)
 395 {
 396   copies_t *value, *info_op, *phi, *loop_h, key, *value1;
 397   int i;
 398   ir_node *loop_head = get_loop_node(info->l_itervar_phi, 0);
 399
 400
 401   for (value = set_first(l_n); value != NULL; value = set_next(l_n)) {
 402     if(value->irn == loop_head)
 403       loop_h = value;
 404     else if (is_Phi_in_loop_head(value->irn, loop_head))
 405       phi = value;
 406     else if(copy_loop_head){
 407       for (i = 0; i<unroll_factor -1; i++){
 408     copy_node(value->irn, NULL);
 409     value->copy[i] = get_irn_link(value->irn);
 410       }
 411     } else {
 412       if((value->irn->op == op_Block            &&
 413       value->irn != loop_head)              ||
 414      (value->irn->op != op_Block             &&
 415       get_nodes_block(value->irn) != loop_head))
 416     for (i = 0; i<unroll_factor -1; i++){
 417       copy_node(value->irn, NULL);
 418       value->copy[i] = get_irn_link(value->irn);
 419     }
 420     }
 421   }
 422   /* Treat the loop head block */
 423   new_loop_head (l_n, info, loop_h, unroll_factor);
 424
 425   /* Similarily treat the Phis in the loop head block. */
 426   key.irn = info->op;
 427   info_op = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
 428   assert(info_op->irn == get_Phi_pred(info->itervar_phi, info->op_pred_pos));
 429   for (i = 0; i < get_irn_n_outs(loop_head); ++i) {
 430     ir_node *phi = get_irn_out(loop_head, i);
 431
 432     if (is_Phi(phi)) {
 433       key.irn = get_Phi_pred(phi, info->op_pred_pos); // info->op;
 434       copies_t *phi_pred = set_find(l_n, &key, sizeof(key), HASH_PTR(key.irn));
 435       key.irn = phi;
 436       copies_t *phi_op = set_find(l_n, &key, sizeof(key), HASH_PTR(key.irn));
 437       set_Phi_copies(phi_op, phi_pred, unroll_factor);
 438     }
 439   }
 440
 441
 442   for (value = set_first(l_n); value != NULL; value = set_next(l_n)) {
 443     int p;
 444
 445     if(copy_loop_head)
 446       set_preds(l_n, value, info, unroll_factor, NULL);
 447     else if((value->irn->op != op_Block) && get_nodes_block(value->irn) != loop_head)
 448       set_preds(l_n, value, info, unroll_factor, NULL);
 449
 450     if (is_Phi_in_loop_head(value->irn, loop_head))
 451       set_phi_backedge(l_n, value, info, unroll_factor);
 452
 453     if ((value->irn->op != op_Block) && !is_Phi_in_loop_head(value->irn, loop_head)) {
 454       ir_node *nodes_block = get_nodes_block(value->irn);
 455
 456       if(!copy_loop_head && nodes_block == loop_head)
 457     continue;
 458
 459       key.irn = nodes_block;
 460       value1 = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
 461
 462       for(p = 0; p < unroll_factor - 1; p++){
 463     set_nodes_block(value->copy[p], value1->copy[p]);
 464     //add_End_keepalive(get_irg_end(current_ir_graph), value->copy[p]);
 465       }
 466     }
 467   }
 468 }
 469
 470 static void
 471 set_loop_outs(set *l_n, induct_var_info *info, int unroll_factor)
 472 {
 473   copies_t *value, key;
 474   int p, i;
 475   ir_node *loop_head = get_loop_node(info->l_itervar_phi, 0);
 476
 477   value = set_first(l_n);
 478   for( ; value != NULL; value = set_next(l_n))
 479     if(value->irn != info->op && !is_Phi_in_loop_head(value->irn, loop_head) &&
 480        get_irn_opcode(value->irn) != iro_Proj)
 481     for(i = 0; i < get_irn_n_outs(value->irn); i++){
 482       key.irn = get_irn_out(value->irn, i);
 483     if(set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn)) == NULL)
 484       for(p = 0; p < get_irn_arity(key.irn); p++)
 485         if(value->irn == get_irn_n(key.irn, p))
 486           set_irn_n (key.irn, p, value->copy[unroll_factor-2]);
 487     }
 488 }
 489
 490
 491 /** Unroll the loop boby with a factor that must be power of two.
 492  *
 493  *  @param *n        A ir node.
 494  *  @param *env      Free environment pointer.
 495  */
 496 static void do_loop_unroll(ir_node *n, void *env){
 497
 498   induct_var_info info;
 499   info.itervar_phi = n;
 500   int l_sons = 0, unroll_factor = 0;
 501
 502   /* The ir node must be a induction varible. */
 503
 504   if (get_irn_op (n) == op_Phi) {
 505     if (is_induction_variable (&info) == NULL) return;
 506   } else return;
 507
 508   /* Brute force limiting of loop body size. */
 509   if (get_loop_n_nodes(info.l_itervar_phi) > 2 ) return;
 510
 511   /* Only unroll loops that compare against a constant for exiting. */
 512   if (info.cmp == NULL) return;
 513
 514   /* We only want to unroll innermost loops. */
 515   l_sons = get_loop_n_sons (info.l_itervar_phi);
 516   if ( l_sons != 0)
 517     return;
 518
 519   ir_node* cmp_out = get_irn_out(info.cmp, 0);
 520
 521   if(!is_Proj(cmp_out)) return;
 522   if(get_irn_op(info.increment) != op_Const) return;
 523
 524   int cmp_typ =  get_Proj_proj(cmp_out);
 525   int init = get_tarval_long(get_Const_tarval
 526                   (get_Phi_pred(info.itervar_phi, info.init_pred_pos)));
 527   int iter_end = get_tarval_long(get_Const_tarval(info.cmp_const));
 528   int iter_increment = get_tarval_long(get_Const_tarval(info.increment));
 529   int diff, iter_number;
 530
 531   if(iter_end < init){
 532     int p = iter_end;
 533     iter_end = init;
 534     init = p;
 535   }
 536
 537   iter_increment = iter_increment < 0 ? -iter_increment : iter_increment;
 538   diff = iter_end - init;
 539
 540   if (diff == 0 || iter_increment == 0) return;
 541
 542   iter_number = diff/iter_increment;
 543   if((cmp_typ == 3 || cmp_typ == 5) && (iter_end % iter_increment == 0))
 544     iter_number ++;
 545
 546   if(iter_number % 4 == 0)
 547     unroll_factor = 4;
 548   else if(iter_number % 3 == 0)
 549     unroll_factor = 3;
 550   else if(iter_number % 2 == 0)
 551     unroll_factor = 2;
 552   else return;
 553
 554
 555   printf("\ninit %d,\n iter_end %d, \n diff %d, cmp_typ\n %d, \n unroll_factor %d", init, iter_end, diff, cmp_typ, unroll_factor);
 556
 557   // int unroll_factor = 4;  /* Must be power of 2. */
 558   assert(unroll_factor <= MAX_UNROLL);
 559
 560   ir_node *loop_head;
 561
 562   loop_head = (is_natural_loop(&info)) ? get_loop_node(info.l_itervar_phi, 0) : NULL;
 563
 564   assert(loop_head != NULL && is_Block(loop_head));
 565
 566  /* We assume, the loop head has exactly one backedge.  The position of
 567     the backedge is in the following variable: */
 568   int backedge_pos ;
 569   backedge_pos = (is_backedge(loop_head, 0)) ? 0:1;
 570
 571   /* A set with the nodes to copy. */
 572   set *loop_nodes;
 573   loop_nodes = new_set(set_cmp, 8);
 574
 575   ir_node *backedge_jmp = get_Block_cfgpred(loop_head, backedge_pos);
 576
 577   find_loop_nodes(info.itervar_phi, get_loop_node(info.l_itervar_phi, 0), loop_nodes);
 578   loop_head_nodes(loop_nodes, &info);
 579   copy_loop_body(loop_nodes, &info, unroll_factor);
 580
 581   copies_t *value;
 582   for (value = set_first(loop_nodes); value != NULL; value = set_next(loop_nodes)) {
 583     if(value->irn == backedge_jmp)
 584       set_Block_cfgpred(loop_head, backedge_pos, value->copy[unroll_factor-2]);
 585   }
 586
 587   set_loop_outs(loop_nodes, &info, unroll_factor);
 588
 589   /*
 590   if (needs_preloop(unroll_factor)) {
 591     return;    for now ...
 592     make_preloop(unroll_factor);
 593   }
 594 */
 595
 596
 597   // adapt_result_usage();
 598
 599 }
 600
 601 /* Performs loop unrolling for the passed graph. */
 602 void optimize_loop_unrolling(ir_graph *irg /* unroll factor, max body size */) {
 603   ir_graph *rem = current_ir_graph;
 604   current_ir_graph = irg;
 605
 606   if ( !get_opt_loop_unrolling()) return;
 607
 608   /* -- Precompute some information -- */
 609   /* Call algorithm that computes the backedges */
 610   construct_cf_backedges(irg);
 611  /* Call algorithm that computes the dominator trees. */
 612   compute_doms(irg);
 613   /* Call algorithm that computes the out edges */
 614   compute_outs(irg);
 615   collect_phiprojs(irg);
 616
 617   /* -- Search expressions that can be optimized -- */
 618   irg_walk_graph(irg, NULL, do_loop_unroll, NULL);
 619
 620   current_ir_graph = rem;
 621 }