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

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/opt/gvn_pre.c
   4  * Purpose:     Global Value Numbering Partial Redundancy Elimination
   5  *              (VanDrunen Hosking 2004)
   6  * Author:      Michael Beck, Rubino Geiss
   7  * Created:
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 1998-2006 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 #ifdef HAVE_CONFIG_H
  14 # include "config.h"
  15 #endif
  16
  17 #include <assert.h>
  18
  19 #include "irgraph_t.h"
  20 #include "irgwalk.h"
  21 #include "irdom.h"
  22 #include "irouts.h"
  23 #include "pset.h"
  24 #include "irgopt.h"
  25 #include "iropt_t.h"
  26 #include "irprintf.h"
  27 #include "irnode_t.h"
  28 #include "ircons.h"
  29 #include "irgmod.h"
  30 #include "debug.h"
  31 #include "gvn_pre.h"
  32
  33 /* */
  34 typedef struct block_info {
  35   pset *nodes;        /**< the set of nodes per block */
  36   pset *avail_out;    /**< the Avail_out set for a block */
  37   pset *antic_in;     /**< the Antic_in set for a block */
  38   pset *new_set;      /**< the set of all new values for a block */
  39   ir_node *avail;     /**< the get_map(avail, block) result */
  40   int not_found;      /**< non-zero, if avail was not found in this block */
  41   struct block_info *next;
  42 } block_info;
  43
  44 typedef struct avail_env {
  45   struct obstack *obst;   /**< the obstack to allocate on */
  46   ir_node *start_block;   /**< the start block of the current graph */
  47   ir_node *end_block;     /**< the end block of the current graph */
  48   block_info *list;       /**< links all block info entires for easier recovery */
  49   int changes;            /**< non-zero, if calculation of Antic_in has changed */
  50 } avail_env;
  51
  52 /** The debug module handle. */
  53 static firm_dbg_module_t *dbg;
  54
  55 /**
  56  * returns non-zero if a node is movable.
  57  */
  58 static int is_nice_value(ir_node *n) {
  59   ir_mode *mode = get_irn_mode(n);
  60
  61   if (!mode_is_data(mode))
  62     return 0;
  63   if (is_irn_constlike(n))
  64     return 0;
  65   return (get_irn_pinned(n) != op_pin_state_pinned);
  66 }
  67
  68 #define pset_foreach(v, s)  for ((v) = pset_first(s); (v); (v) = pset_next(s))
  69
  70 /** computes dst = dst \/ src */
  71 static void pset_union(pset *dst, pset *src, unsigned (*hash)(void *))
  72 {
  73   void *entry;
  74
  75   pset_foreach(entry, src) {
  76     pset_insert(dst, entry, ir_node_hash(entry));
  77   }
  78 }
  79
  80 #ifdef DEBUG_libfirm
  81 /**
  82  * Dump the Avail or Antic sets
  83  */
  84 static void dump_set(pset *set, char *txt, ir_node *block)
  85 {
  86   ir_node *n;
  87   int i;
  88
  89   DBG((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
  90   i = 0;
  91   pset_foreach(n, set) {
  92     if ((i & 3) == 3)
  93       DBG((dbg, LEVEL_2, "\n"));
  94     DBG((dbg, LEVEL_2, " %+F,", n));
  95     ++i;
  96   }
  97   DBG((dbg, LEVEL_2, "\n}\n"));
  98 }  /* dump_set */
  99
 100 #else
 101 #define dump_set(set, txt, block)
 102 #endif /* DEBUG_libfirm */
 103
 104
 105 /**
 106  * Return the block info of a block
 107  */
 108 static block_info *get_block_info(ir_node *block) {
 109   return get_irn_link(block);
 110 }
 111
 112 /**
 113  * computes Avail_out(block):
 114  *
 115  * Avail_in(block)  = Avail_out(dom(block))
 116  * Avail_out(block) = Avail_in(block) \/ Nodes(block)
 117  *
 118  * Precondition:
 119  *  This function must be called in the top-down dominance order:
 120  *  Then, it computes Leader(Nodes(block)) instead of Nodes(block) !
 121  */
 122 static void compute_avail_top_down(ir_node *block, void *ctx)
 123 {
 124   avail_env *env = ctx;
 125   block_info *dom_info;
 126   block_info *info = get_block_info(block);
 127   ir_node *dom_blk;
 128
 129   /* we don't need the end block Avail */
 130   if (block == env->end_block)
 131     return;
 132
 133   pset_union(info->avail_out, info->nodes, ir_node_hash);
 134
 135   /* the root has no dominator */
 136   if (block != env->start_block) {
 137     dom_blk = get_Block_idom(block);
 138     assert(is_Block(dom_blk));
 139
 140     dom_info = get_block_info(dom_blk);
 141     assert(dom_info);
 142
 143     pset_union(info->avail_out, dom_info->avail_out, ir_node_hash);
 144   }
 145   dump_set(info->avail_out, "Avail_out", block);
 146 }
 147
 148 /*
 149  * Implement phi_translate
 150  */
 151 static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, avail_env *env)
 152 {
 153   ir_node *pred_block;
 154   ir_node *res;
 155   int i, arity = get_irn_intra_arity(node);
 156   struct obstack *old;
 157
 158   if (is_Phi(node)) {
 159     if (get_nodes_block(node) == block)
 160       return get_Phi_pred(node, pos);
 161     return node;
 162   }
 163
 164   /* check if the node has at least one Phi predecessor */
 165   for (i = 0; i < arity; ++i) {
 166     ir_node *phi = get_irn_intra_n(node, i);
 167     if (is_Phi(phi) && get_nodes_block(phi) == block)
 168       break;
 169   }
 170   if (i >= arity) {
 171     /* no Phi in the predecessors */
 172     return node;
 173   }
 174
 175   pred_block = get_Block_cfgpred_block(block, pos);
 176
 177   /* Create a copy of the node in the pos'th predecessor block.
 178      Use our environmental obstack, as these nodes are always
 179      temporary. */
 180   old = current_ir_graph->obst;
 181   current_ir_graph->obst = env->obst;
 182   res   = new_ir_node(
 183             get_irn_dbg_info(node),
 184             current_ir_graph,
 185             pred_block,
 186             get_irn_op(node),
 187             get_irn_mode(node),
 188             arity,
 189             get_irn_in(node));
 190   /* We need the attribute copy here, because the Hash value of a
 191      node might depend on that. */
 192   copy_node_attr(node, res);
 193   current_ir_graph->obst = old;
 194
 195   for (i = -1; i < arity; ++i) {
 196     ir_node *pred = get_irn_intra_n(node, i);
 197
 198     if (! is_Phi(pred))
 199       set_irn_n(res, i, pred);
 200     else
 201       set_irn_n(res, i, get_Phi_pred(pred, pos));
 202   }
 203   set_irn_link(res, NULL);
 204   return res;
 205 }
 206
 207 /**
 208  * computes Antic_in(block):
 209  *
 210  */
 211 static void compute_antic(ir_node *block, void *ctx)
 212 {
 213   avail_env *env = ctx;
 214   block_info *succ_info;
 215   block_info *info = get_block_info(block);
 216   ir_node *succ;
 217   int size;
 218
 219   /* no need for computations in start block */
 220   if (block == env->start_block)
 221     return;
 222
 223   size = pset_count(info->antic_in);
 224
 225   /* the root has no dominator */
 226   if (block != env->end_block) {
 227     int n_succ = get_Block_n_cfg_outs(block);
 228
 229     if (n_succ == 1) {
 230       ir_node *node;
 231       int i, pos = -1;
 232       pset *nodes = new_pset(identities_cmp, 8);
 233
 234       pset_union(nodes, info->nodes, ir_node_hash);
 235
 236       /* find blocks position in succ's block predecessors */
 237       succ = get_Block_cfg_out(block, 0);
 238       for (i = get_Block_n_cfgpreds(succ) - 1; i >= 0; --i) {
 239         if (get_Block_cfgpred_block(succ, i) == block) {
 240           pos = i;
 241           break;
 242         }
 243       }
 244       assert(pos >= 0);
 245
 246       succ_info = get_block_info(succ);
 247       for (node = pset_first(succ_info->antic_in);
 248            node;
 249            node = pset_next(succ_info->antic_in)) {
 250         ir_node *trans = phi_translate(node, succ, pos, env);
 251
 252         identify_remember(nodes, trans);
 253
 254         /* add all predecessors of node */
 255         for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 256           ir_node *pred = get_irn_n(node, i);
 257           ir_node *trans = phi_translate(pred, succ, pos, env);
 258
 259           if (is_nice_value(trans))
 260             identify_remember(nodes, trans);
 261         }
 262       }
 263      /* this step calculates Antic_in(b) = Antic_out(b) \/ Nodes(b) */
 264      pset_union(info->antic_in, nodes, ir_node_hash);
 265      del_pset(nodes);
 266    }
 267     else {
 268       ir_node *n, *succ0;
 269       block_info *succ0_info;
 270       int i;
 271
 272       assert(n_succ > 1);
 273
 274       /* Select a successor to compute the disjoint of all Nodes
 275          sets, it might be useful to select the block with the
 276          smallest number of nodes.  For simplicity we choose the
 277          first one. */
 278       succ0 = get_Block_cfg_out(block, 0);
 279       succ0_info = get_block_info(succ0);
 280       for (n = pset_first(succ0_info->antic_in);
 281            n;
 282            n = pset_next(succ0_info->antic_in)) {
 283         /* we need the disjoint */
 284         for (i = 1; i < n_succ; ++i) {
 285           ir_node *succ = get_Block_cfg_out(block, i);
 286           block_info *succ_info = get_block_info(succ);
 287           if (pset_find(succ_info->antic_in, n, ir_node_hash(n)) == NULL)
 288             break;
 289         }
 290         if (i >= n_succ) {
 291           /* we found a node that is common in all Antic_in(succ(b)),
 292              put it in Antic_in(b) */
 293           identify_remember(info->antic_in, n);
 294         }
 295       }
 296       /* this step calculates Antic_in(b) = Antic_out(b) \/ Nodes(b) */
 297       pset_union(info->antic_in, info->nodes, ir_node_hash);
 298     }
 299   }
 300
 301   if (size != pset_count(info->antic_in))
 302     /* the Antic_in set has changed */
 303     env->changes |= 1;
 304
 305   dump_set(info->antic_in, "Antic_in", block);
 306 }  /* compute_antic */
 307
 308 /**
 309  * allocate a block info
 310  */
 311 static void alloc_blk_info(ir_node *block, void *ctx)
 312 {
 313   int i;
 314   avail_env *env = ctx;
 315   block_info *info = obstack_alloc(env->obst, sizeof(block_info));
 316
 317   set_irn_link(block, info);
 318   info->nodes     = new_pset(identities_cmp, 8);
 319   info->antic_in  = new_pset(identities_cmp, 8);
 320   info->avail_out = new_pset(identities_cmp, 8);
 321   info->avail     = NULL;
 322   info->not_found = 0;
 323   info->new_set   = NULL;
 324   info->next      = env->list;
 325   env->list       = info->next;
 326
 327   /* fill the nodes set, we will need it later */
 328   for (i = get_irn_n_outs(block) - 1; i >= 0; --i) {
 329     ir_node *n = get_irn_out(block, i);
 330
 331     /* clear the link field here, we need it later */
 332     set_irn_link(n, NULL);
 333
 334     /* we cannot optimize pinned nodes, so do not remember them */
 335     if (is_nice_value(n))
 336       identify_remember(info->nodes, n);
 337     else if (is_Phi(n) && get_irn_mode(n) != mode_M) {
 338       /*
 339        * Phis are "temporaries" and must be handled special:
 340        * They are avail, but are not in Antic_in
 341        */
 342       identify_remember(info->avail_out, n);
 343     }
 344   }
 345 }
 346
 347 /**
 348  * Compare two nodes for equal operands.
 349  */
 350 static int operands_equal(ir_node *n1, ir_node *n2)
 351 {
 352   int i, arity = get_irn_arity(n1);
 353   assert(n1->op == n2->op && arity == get_irn_arity(n2));
 354   for (i = 0; i < arity; ++i)
 355     if (get_irn_n(n1, i) != get_irn_n(n2, i))
 356       return 0;
 357   return 1;
 358 }
 359
 360 /**
 361  * Get the leader of an expression. In Firm, only
 362  * Phi nodes can be leaders, all other 'leader' are
 363  * handled by the identify_remember mechanism right.
 364  */
 365 static ir_node *get_leader(ir_node *n)
 366 {
 367   ir_node *l = get_irn_link(n);
 368
 369   if (l) {
 370     assert(is_Phi(l));
 371     return l;
 372   }
 373   return n;
 374 }
 375
 376 static ir_node *has_leader(ir_node *n)
 377 {
 378   ir_node *l = get_irn_link(n);
 379
 380   if (l) {
 381     assert(is_Phi(l));
 382     return l;
 383   }
 384   return NULL;
 385 }
 386
 387 /**
 388  * Perform insertion of partially redundant values.
 389  * For every Block node, do the following:
 390  * 1.  Propagate the NEW_SETS of the dominator into the current block.
 391  * If the block has multiple predecessors,
 392  *     2a. Iterate over the ANTIC expressions for the block to see if
 393  *         any of them are partially redundant.
 394  *     2b. If so, insert them into the necessary predecessors to make
 395  *         the expression fully redundant.
 396  *     2c. Insert a new Phi merging the values of the predecessors.
 397  *     2d. Insert the new Phi, and the new expressions, into the
 398  *         NEW_SETS set.
 399  */
 400 static void insert_nodes(ir_node *block, void *ctx)
 401 {
 402   avail_env *env = ctx;
 403   ir_node *v, *idom, *first_s;
 404   block_info *curr_info, *idom_info;
 405   int pos, arity = get_irn_intra_arity(block);
 406   int all_same, by_some;
 407
 408   curr_info = get_block_info(block);
 409   curr_info->new_set = new_pset(identities_cmp, 8);
 410
 411   if (block == env->start_block)
 412     return;
 413
 414   idom = get_Block_idom(block);
 415   idom_info = get_block_info(idom);
 416
 417   /* update the new_sets */
 418   pset_union(curr_info->new_set, idom_info->new_set, ir_node_hash);
 419   pset_foreach(v, idom_info->new_set) {
 420     ir_node *old = identify_remember(idom_info->new_set, v);
 421
 422     if (old != v) {
 423       /* v must dominate old here */
 424       assert(block_dominates(get_nodes_block(v), get_nodes_block(old)));
 425
 426       pset_remove(curr_info->avail_out, old, ir_node_hash(old));
 427       identify_remember(curr_info->avail_out, v);
 428     }
 429   }
 430   dump_set(curr_info->avail_out, "[Avail_out]", block);
 431
 432   if (arity <= 1)
 433     return;
 434
 435   pset_foreach(v, curr_info->antic_in) {
 436     /*
 437      * If we already have a leader for this node,
 438      * it is totally redundant.
 439      */
 440     if (has_leader(v))
 441       continue;
 442
 443     /* If the value was already computed in the dominator, then
 444        it is totally redundant.  Hence we have nothing to insert. */
 445     if (pset_find(idom_info->avail_out, v, ir_node_hash(v))) {
 446 //      DBG((dbg, LEVEL_2, "Found %+F from block %+F avail in dom %+F\n", v, block, idom));
 447       continue;
 448     }
 449
 450     all_same = 1;
 451     by_some  = 0;
 452     first_s  = NULL;
 453
 454     /* for all predecessor blocks */
 455     for (pos = 0; pos < arity; ++pos) {
 456       block_info *pred_info;
 457       ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
 458       ir_node *trans, *found;
 459
 460       /* ignore bad blocks. */
 461       if (is_Bad(pred_blk))
 462         continue;
 463
 464       trans = phi_translate(v, block, pos, env);
 465
 466       pred_info = get_block_info(pred_blk);
 467       found = pset_find(pred_info->avail_out, trans, ir_node_hash(trans));
 468
 469       if (found == NULL) {
 470         all_same = 0;
 471         pred_info->avail = trans;
 472         pred_info->not_found = 1;
 473       }
 474       else {
 475         found = get_leader(found);
 476         pred_info->avail = found;
 477         pred_info->not_found = 0;
 478         by_some = 1;
 479         if (first_s == NULL)
 480           first_s = found;
 481         else if (first_s != found)
 482           all_same = 0;
 483
 484         DBG((dbg, LEVEL_2, "Found %+F from block %+F as %+F in pred %+F\n", v, block, found, pred_blk));
 485       }  /* if */
 486     }  /* for */
 487
 488     /* If it's not the same value already existing along every predecessor, and
 489        it's defined by some predecessor, it is partially redundant. */
 490     if (! all_same && by_some) {
 491       ir_node *phi, **in;
 492       ir_mode *mode = NULL;
 493       DBG((dbg, LEVEL_1, "Partial redundant %+F from block %+F found\n", v, block));
 494
 495       in = xmalloc(arity * sizeof(*in));
 496       /* for all predecessor blocks */
 497       for (pos = 0; pos < arity; ++pos) {
 498         ir_node *pred_blk = get_Block_cfgpred_block(block, pos);
 499         block_info *pred_info = get_block_info(pred_blk);
 500
 501         /* ignore bad blocks. */
 502         if (is_Bad(pred_blk)) {
 503           in[pos] = new_Bad();
 504           continue;
 505         }
 506
 507         /* ignore blocks that already have the expression */
 508         if (pred_info->not_found) {
 509           ir_node *avail = pred_info->avail;
 510           ir_node *nn;
 511           assert(! is_Phi(avail));
 512
 513           mode = get_irn_mode(avail);
 514           nn = new_ir_node(
 515             get_irn_dbg_info(avail),
 516             current_ir_graph, pred_blk,
 517             get_irn_op(avail),
 518             mode,
 519             get_irn_arity(avail),
 520             get_irn_in(avail) + 1);
 521
 522           pred_info->avail = identify_remember(pred_info->avail_out, nn);
 523         }
 524         in[pos] = pred_info->avail;
 525       }  /* for */
 526       phi = new_r_Phi(current_ir_graph, block, arity, in, mode);
 527       free(in);
 528       identify_remember(curr_info->avail_out, phi);
 529       identify_remember(curr_info->new_set, phi);
 530       /* v might be translated, so add it here */
 531       identify_remember(curr_info->avail_out, v);
 532       identify_remember(curr_info->new_set, v);
 533       set_irn_link(v, phi);
 534       DBG((dbg, LEVEL_2, "New %+F for redundant %+F created\n", phi, v));
 535       env->changes |= 1;
 536     }  /* if */
 537   }  /* pset_foreach */
 538 }  /* insert_nodes */
 539
 540 /**
 541  * Do the elimination step
 542  */
 543 static void eliminate_nodes(ir_node *block, void *ctx)
 544 {
 545   avail_env *env = ctx;
 546   block_info *curr_info = get_block_info(block);
 547   ir_node *v;
 548
 549   pset_foreach(v, curr_info->nodes) {
 550     ir_node *l = identify_remember(curr_info->avail_out, v);
 551
 552     l = get_leader(l);
 553     if (l != v) {
 554       DBG((dbg, LEVEL_2, "Replacing %+F by %+F\n", v, l));
 555       exchange(v, l);
 556     }
 557   }
 558 }
 559
 560 void do_gvn_pre(ir_graph *irg)
 561 {
 562   struct obstack obst;
 563   avail_env a_env;
 564   optimization_state_t state;
 565   block_info *p;
 566   int iter = 0;
 567
 568   /* register a debug mask */
 569   dbg = firm_dbg_register("firm.opt.gvn_pre");
 570
 571   obstack_init(&obst);
 572   a_env.obst        = &obst;
 573   a_env.list        = NULL;
 574   a_env.start_block = get_irg_start_block(irg);
 575   a_env.end_block   = get_irg_end_block(irg);
 576
 577   /* Move Proj's into the same block as their args,
 578      else we would assign the result to wrong blocks */
 579   normalize_proj_nodes(irg);
 580
 581   /* critical edges MUST be removed */
 582   remove_critical_cf_edges(irg);
 583
 584   /* we need dominator AND post dominator information */
 585   if (get_irg_dom_state(irg) != dom_consistent)
 586     compute_doms(irg);
 587   if (get_irg_postdom_state(irg) != dom_consistent)
 588     compute_postdoms(irg);
 589   if (get_irg_outs_state(irg) != outs_consistent)
 590     compute_irg_outs(irg);
 591
 592   /*
 593    * Switch on GCSE. We need it to correctly compute
 594    * the leader of a node by hashing.
 595    */
 596   save_optimization_state(&state);
 597   set_opt_global_cse(1);
 598
 599   /* allocate block info for all blocks */
 600   irg_block_walk_graph(irg, NULL, alloc_blk_info, &a_env);
 601
 602   /* compute the available value sets for all blocks */
 603   dom_tree_walk_irg(irg, compute_avail_top_down, NULL, &a_env);
 604
 605   /* compute the anticipated value sets for all blocks */
 606   do {
 607     DBG((dbg, LEVEL_1, "Antic_in Iteration %d starts ...\n", ++iter));
 608     a_env.changes = 0;
 609     irg_block_walk_graph(irg, compute_antic, NULL, &a_env);
 610 //    postdom_tree_walk_irg(irg, compute_antic, NULL, &a_env);
 611     DBG((dbg, LEVEL_1, "------------------------\n"));
 612   } while (a_env.changes != 0);
 613
 614   /* compute redundant expressions */
 615   iter = 0;
 616   do {
 617     DBG((dbg, LEVEL_1, "Insert Iteration %d starts ...\n", ++iter));
 618     a_env.changes = 0;
 619     dom_tree_walk_irg(irg, insert_nodes, NULL, &a_env);
 620     DBG((dbg, LEVEL_1, "------------------------\n"));
 621   } while (a_env.changes != 0);
 622
 623   /* last step: eliminate nodes */
 624   dom_tree_walk_irg(irg, eliminate_nodes, NULL, &a_env);
 625
 626   restore_optimization_state(&state);
 627
 628   /* clean up: delete all sets */
 629   for (p = a_env.list; p != NULL; p = p->next) {
 630     if (p->antic_in)
 631       del_pset(p->antic_in);
 632     if (p->avail_out)
 633       del_pset(p->avail_out);
 634     if (p->nodes)
 635       del_pset(p->nodes);
 636   }
 637   obstack_free(&obst, NULL);
 638 }  /* do_gvn_pre */