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;
 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(int p = 0; p < unroll_factor -1; p++)
 179           set_irn_n (value->copy[p], i, pred);
 180
 181       } else
 182         for(int 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 l_n_node = 0;
 250   l_n_node = get_loop_n_nodes (info->l_itervar_phi);
 251
 252   for (int 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   copies_t key, *value;
 272
 273   /* Add this node to the list. */
 274   key.irn  = node;
 275   for(int i = 0; i < 4 ;i++)
 276     key.copy[i] = NULL;
 277   value = set_insert(l_n, &key, sizeof(key), HASH_PTR(key.irn));
 278
 279   /* Add all outs of this node to the list, if they are within the loop. */
 280   for (int i = get_irn_n_outs(node) - 1; i >= 0; i--) {
 281     ir_node *pred = get_irn_out(node, i);
 282     key.irn = pred;
 283     if (!is_loop_invariant(pred, loop_head)         &&
 284         set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn)) == NULL ) {
 285       find_loop_nodes(pred, loop_head, l_n);
 286     }
 287   }
 288
 289   /* Add all ins if they are within the loop. */
 290   for(int i = get_irn_arity(node) -1; i >=0; i--) {
 291     ir_node *pred = get_irn_n(node, i);
 292     key.irn = pred;
 293     if (!is_loop_invariant(pred, loop_head)         &&
 294         set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn)) == NULL ){
 295       find_loop_nodes(pred, loop_head, l_n);
 296     }
 297   }
 298 }
 299
 300 /* Make a new loop head if copy_loop_head = 1.
 301  *
 302  * @param *l_n              A set, where the node of the loop are saved.
 303  * @param *info             Contains the loop information.
 304  * @param *value            A element of the set.
 305  * @param *unroll_factor    A integer power of 2.
 306  *
 307  */
 308 static void
 309 new_loop_head (set *l_n, induct_var_info *info, copies_t *value, int unroll_factor)
 310 {
 311   copies_t block, *value_backedge_jmp, *backedge_jmp_block;
 312
 313   ir_node *backedge_jmp = get_Block_cfgpred(value->irn, info->op_pred_pos);
 314   block.irn = backedge_jmp;
 315
 316   value_backedge_jmp = set_find( l_n, &block, sizeof(block), HASH_PTR(block.irn));
 317   if(copy_loop_head){
 318     ir_node *new_loop_head = new_Block(1, &backedge_jmp);
 319     value->copy[0] = new_loop_head;
 320
 321     for(int i = 1; i<unroll_factor - 1; i++){
 322       ir_node *new_loop_head1 = new_Block(1, &value_backedge_jmp->copy[i-1]);
 323       value->copy[i] = new_loop_head1;
 324     }
 325   }else{
 326
 327     block.irn = get_nodes_block(backedge_jmp);
 328     backedge_jmp_block =  set_find( l_n, &block, sizeof(block), HASH_PTR(block.irn));
 329
 330     set_irn_n(backedge_jmp_block->copy[0], 0, value_backedge_jmp->irn) ;
 331
 332     for(int i = 1; i<unroll_factor - 1; i++)
 333       set_irn_n(backedge_jmp_block->copy[i], 0, value_backedge_jmp->copy[i - 1]);
 334   }
 335
 336 }
 337
 338 /* Set all copies of the induction variable.
 339  *
 340  * @param *phi             A phi node in the loop head block.
 341  * @param *phi_pred        The predecessor of the phi along the backedge.
 342  * @param *unroll_factor   A integer power of 2.
 343  *
 344  */
 345 static void
 346 set_Phi_copies(copies_t *phi, copies_t *phi_pred, int unroll_factor)
 347 {
 348   phi->copy[0] = phi_pred->irn;
 349   for(int p = 1; p < unroll_factor -1; p++)
 350     phi->copy[p] =  phi_pred->copy[p -1];
 351 }
 352
 353 /* Decide if the loop head to be copy. A head with important nodes
 354  * mus be copy.
 355  *
 356  * @param *l_n                A set, where the node of the loop are saved.
 357  * @param *info               Contains information about the induction variable.
 358  */
 359 static void
 360 loop_head_nodes(set *l_n, induct_var_info *info)
 361 {
 362   copies_t *value;
 363   ir_node *loop_head = get_loop_node(info->l_itervar_phi, 0);
 364
 365   for (value = set_first(l_n); value != NULL; value = set_next(l_n))
 366     if(value->irn->op != op_Block &&
 367        get_nodes_block(value->irn) == loop_head)
 368       switch(get_irn_opcode(value->irn)) {
 369       case iro_Cond:
 370         break;
 371       case iro_Phi:
 372         break;
 373       case iro_Proj:
 374         break;
 375       case iro_Const:
 376         break;
 377       case iro_Cmp:
 378         break;
 379       default:
 380         copy_loop_head = 1;
 381       }
 382 }
 383
 384 /** Copy all loop nodes.
 385  *
 386  * @param *l_n    Contains all nodes of the loop.
 387  * @param *info   Contains the loop information.
 388  * @param *unroll_factor   A integer power of 2.
 389  */
 390 static void
 391 copy_loop_body(set *l_n, induct_var_info *info, int unroll_factor)
 392 {
 393   copies_t *value, *info_op, *phi, *loop_h, key, *value1;
 394
 395   ir_node *loop_head = get_loop_node(info->l_itervar_phi, 0);
 396
 397
 398   for (value = set_first(l_n); value != NULL; value = set_next(l_n)) {
 399     if(value->irn == loop_head)
 400       loop_h = value;
 401     else if (is_Phi_in_loop_head(value->irn, loop_head))
 402       phi = value;
 403     else if(copy_loop_head){
 404       for (int i = 0; i<unroll_factor -1; i++){
 405         copy_node(value->irn, NULL);
 406         value->copy[i] = get_irn_link(value->irn);
 407       }
 408     } else {
 409       if((value->irn->op == op_Block            &&
 410           value->irn != loop_head)              ||
 411          (value->irn->op != op_Block             &&
 412           get_nodes_block(value->irn) != loop_head))
 413         for (int i = 0; i<unroll_factor -1; i++){
 414           copy_node(value->irn, NULL);
 415           value->copy[i] = get_irn_link(value->irn);
 416         }
 417     }
 418   }
 419   /* Treat the loop head block */
 420   new_loop_head (l_n, info, loop_h, unroll_factor);
 421
 422   /* Similarily treat the Phis in the loop head block. */
 423   key.irn = info->op;
 424   info_op = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
 425   assert(info_op->irn == get_Phi_pred(info->itervar_phi, info->op_pred_pos));
 426   for (int i = 0; i < get_irn_n_outs(loop_head); ++i) {
 427     ir_node *phi = get_irn_out(loop_head, i);
 428
 429     if (is_Phi(phi)) {
 430       key.irn = get_Phi_pred(phi, info->op_pred_pos); // info->op;
 431       copies_t *phi_pred = set_find(l_n, &key, sizeof(key), HASH_PTR(key.irn));
 432       key.irn = phi;
 433       copies_t *phi_op = set_find(l_n, &key, sizeof(key), HASH_PTR(key.irn));
 434       set_Phi_copies(phi_op, phi_pred, unroll_factor);
 435     }
 436   }
 437
 438
 439   for (value = set_first(l_n); value != NULL; value = set_next(l_n)) {
 440
 441     if(copy_loop_head)
 442       set_preds(l_n, value, info, unroll_factor, NULL);
 443     else if((value->irn->op != op_Block) && get_nodes_block(value->irn) != loop_head)
 444       set_preds(l_n, value, info, unroll_factor, NULL);
 445
 446     if (is_Phi_in_loop_head(value->irn, loop_head))
 447       set_phi_backedge(l_n, value, info, unroll_factor);
 448
 449     if ((value->irn->op != op_Block) && !is_Phi_in_loop_head(value->irn, loop_head)) {
 450       ir_node *nodes_block = get_nodes_block(value->irn);
 451
 452       if(!copy_loop_head && nodes_block == loop_head)
 453         continue;
 454
 455       key.irn = nodes_block;
 456       value1 = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
 457
 458       for(int p = 0; p < unroll_factor - 1; p++){
 459         set_nodes_block(value->copy[p], value1->copy[p]);
 460         //add_End_keepalive(get_irg_end(current_ir_graph), value->copy[p]);
 461       }
 462     }
 463   }
 464 }
 465
 466 static void
 467 set_loop_outs(set *l_n, induct_var_info *info, int unroll_factor)
 468 {
 469   copies_t *value, key;
 470   ir_node *loop_head = get_loop_node(info->l_itervar_phi, 0);
 471
 472   value = set_first(l_n);
 473   for( ; value != NULL; value = set_next(l_n))
 474     if(value->irn != info->op && !is_Phi_in_loop_head(value->irn, loop_head) &&
 475        get_irn_opcode(value->irn) != iro_Proj)
 476     for(int i = 0; i < get_irn_n_outs(value->irn); i++){
 477       key.irn = get_irn_out(value->irn, i);
 478         if(set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn)) == NULL)
 479           for(int p = 0; p < get_irn_arity(key.irn); p++)
 480             if(value->irn == get_irn_n(key.irn, p))
 481               set_irn_n (key.irn, p, value->copy[unroll_factor-2]);
 482     }
 483 }
 484
 485
 486 /** Unroll the loop boby with a factor that must be power of two.
 487  *
 488  *  @param *n        A ir node.
 489  *  @param *env      Free environment pointer.
 490  */
 491 static void do_loop_unroll(ir_node *n, void *env){
 492
 493   induct_var_info info;
 494   info.itervar_phi = n;
 495   int l_sons = 0, unroll_factor = 0;
 496
 497   /* The ir node must be a induction varible. */
 498
 499   if (get_irn_op (n) == op_Phi) {
 500     if (is_induction_variable (&info) == NULL) return;
 501   } else return;
 502
 503   /* Brute force limiting of loop body size. */
 504   if (get_loop_n_nodes(info.l_itervar_phi) > 2 ) return;
 505
 506   /* Only unroll loops that compare against a constant for exiting. */
 507   if (info.cmp == NULL) return;
 508
 509   /* We only want to unroll innermost loops. */
 510   l_sons = get_loop_n_sons (info.l_itervar_phi);
 511   if ( l_sons != 0)
 512     return;
 513
 514   ir_node* cmp_out = get_irn_out(info.cmp, 0);
 515
 516   if(!is_Proj(cmp_out)) return;
 517   if(get_irn_op(info.increment) != op_Const) return;
 518
 519   int cmp_typ =  get_Proj_proj(cmp_out);
 520   int init = get_tarval_long(get_Const_tarval
 521                               (get_Phi_pred(info.itervar_phi, info.init_pred_pos)));
 522   int iter_end = get_tarval_long(get_Const_tarval(info.cmp_const));
 523   int iter_increment = get_tarval_long(get_Const_tarval(info.increment));
 524   int diff, iter_number;
 525
 526   if(iter_end < init){
 527     int p = iter_end;
 528     iter_end = init;
 529     init = p;
 530   }
 531
 532   iter_increment = iter_increment < 0 ? -iter_increment : iter_increment;
 533   diff = iter_end - init;
 534
 535   if (diff == 0 || iter_increment == 0) return;
 536
 537   iter_number = diff/iter_increment;
 538   if((cmp_typ == 3 || cmp_typ == 5) && (iter_end % iter_increment == 0))
 539     iter_number ++;
 540
 541   if(iter_number % 4 == 0)
 542     unroll_factor = 4;
 543   else if(iter_number % 3 == 0)
 544     unroll_factor = 3;
 545   else if(iter_number % 2 == 0)
 546     unroll_factor = 2;
 547   else return;
 548
 549
 550   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);
 551
 552   // int unroll_factor = 4;  /* Must be power of 2. */
 553   assert(unroll_factor <= MAX_UNROLL);
 554
 555   ir_node *loop_head;
 556
 557   loop_head = (is_natural_loop(&info)) ? get_loop_node(info.l_itervar_phi, 0) : NULL;
 558
 559   assert(loop_head != NULL && is_Block(loop_head));
 560
 561  /* We assume, the loop head has exactly one backedge.  The position of
 562     the backedge is in the following variable: */
 563   int backedge_pos ;
 564   backedge_pos = (is_backedge(loop_head, 0)) ? 0:1;
 565
 566   /* A set with the nodes to copy. */
 567   set *loop_nodes;
 568   loop_nodes = new_set(set_cmp, 8);
 569
 570   ir_node *backedge_jmp = get_Block_cfgpred(loop_head, backedge_pos);
 571
 572   find_loop_nodes(info.itervar_phi, get_loop_node(info.l_itervar_phi, 0), loop_nodes);
 573   loop_head_nodes(loop_nodes, &info);
 574   copy_loop_body(loop_nodes, &info, unroll_factor);
 575
 576   copies_t *value;
 577   for (value = set_first(loop_nodes); value != NULL; value = set_next(loop_nodes)) {
 578     if(value->irn == backedge_jmp)
 579       set_Block_cfgpred(loop_head, backedge_pos, value->copy[unroll_factor-2]);
 580   }
 581
 582   set_loop_outs(loop_nodes, &info, unroll_factor);
 583
 584   /*
 585   if (needs_preloop(unroll_factor)) {
 586     return;    for now ...
 587     make_preloop(unroll_factor);
 588   }
 589 */
 590
 591
 592   // adapt_result_usage();
 593
 594 }
 595
 596 /* Performs loop unrolling for the passed graph. */
 597 void optimize_loop_unrolling(ir_graph *irg /* unroll factor, max body size */) {
 598   ir_graph *rem = current_ir_graph;
 599   current_ir_graph = irg;
 600
 601   if ( !get_opt_loop_unrolling()) return;
 602
 603   /* -- Precompute some information -- */
 604   /* Call algorithm that computes the backedges */
 605   construct_cf_backedges(irg);
 606  /* Call algorithm that computes the dominator trees. */
 607   compute_doms(irg);
 608   /* Call algorithm that computes the out edges */
 609   compute_outs(irg);
 610   collect_phiprojs(irg);
 611
 612   /* -- Search expressions that can be optimized -- */
 613   irg_walk_graph(irg, NULL, do_loop_unroll, NULL);
 614
 615   current_ir_graph = rem;
 616 }