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
  29 /* */
  30 typedef struct block_info {
  31   pset *nodes;        /**< the set of nodes per block */
  32   pset *avail_out;    /**< the Avail_out set for a block */
  33   pset *antic_in;     /**< the Antic_in set for a block */
  34   struct block_info *next;
  35 } block_info;
  36
  37 typedef struct avail_env {
  38   struct obstack *obst;   /**< the obstack to allocate on */
  39   ir_node *start_block;
  40   ir_node *end_block;
  41   block_info *list;       /**< links all block info entires for easier recovery */
  42   int changes;            /**< non-zero, if calculation of Antic_in has changed */
  43 } avail_env;
  44
  45 /**
  46  * returns non-zero if a node is movable.
  47  */
  48 static int is_nice_value(ir_node *n) {
  49   ir_mode *mode = get_irn_mode(n);
  50
  51   if (mode == mode_M || mode == mode_X)
  52     return 0;
  53   return (get_irn_pinned(n) != op_pin_state_pinned);
  54 }
  55
  56 /** computes dst = dst \/ src */
  57 static void pset_union(pset *dst, pset *src, unsigned (*hash)(void *))
  58 {
  59   void *entry;
  60
  61   for (entry = pset_first(src); entry; entry = pset_next(src)) {
  62     pset_insert(dst, entry, ir_node_hash(entry));
  63   }
  64 }
  65
  66 /**
  67  * computes Avail_out(block):
  68  *
  69  * Avail_in(block)  = Avail_out(dom(block))
  70  * Avail_out(block) = Avail_in(block) \/ Nodes(block)
  71  *
  72  * Precondition:
  73  *  This function must be called in the top-down dominance order:
  74  *  Then, it computes Leader(Nodes(block)) instead of Nodes(block) !
  75  */
  76 static void compute_avail_top_down(ir_node *block, void *ctx)
  77 {
  78   avail_env *env = ctx;
  79   block_info *dom_info;
  80   block_info *info = get_irn_link(block);
  81   ir_node *dom_blk;
  82   int i;
  83
  84   /* the root has no dominator */
  85   if (block != env->start_block) {
  86     dom_blk = get_Block_idom(block);
  87     assert(is_Block(dom_blk));
  88
  89     dom_info = get_irn_link(dom_blk);
  90     assert(dom_info);
  91
  92     pset_union(info->avail_out, dom_info->avail_out, ir_node_hash);
  93     pset_union(info->avail_out, info->nodes, ir_node_hash);
  94   }
  95 #ifdef _DEBUG
  96   {
  97     ir_node *n;
  98
  99     ir_printf("Avail_out(%+F) = {\n", block);
 100     for (i = 0, n = pset_first(info->avail_out); n; ++i, n = pset_next(info->avail_out)) {
 101       if ((i & 3) == 3)
 102         printf("\n");
 103       ir_printf(" %+F,", n);
 104     }
 105     printf("\n}\n");
 106   }
 107 #endif
 108 }
 109
 110 /*
 111  * Implement phi_translate
 112  */
 113 static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, avail_env *env)
 114 {
 115   ir_node *pred_block;
 116   ir_node *res;
 117   int i, arity = get_irn_intra_arity(node);
 118   struct obstack *old;
 119
 120   if (is_Phi(node)) {
 121     if (get_nodes_block(node) == block)
 122       return get_Phi_pred(node, pos);
 123     return node;
 124   }
 125
 126   /* check if the node has at least one Phi predecessor */
 127   for (i = 0; i < arity; ++i) {
 128     ir_node *phi = get_irn_intra_n(node, i);
 129     if (is_Phi(phi) && get_nodes_block(phi) == block)
 130       break;
 131   }
 132   if (i >= arity) {
 133     /* no Phi in the predecessors */
 134     return node;
 135   }
 136
 137   pred_block = get_Block_cfgpred_block(block, pos);
 138
 139   /* Create a copy of the node in the pos'th predecessor block.
 140      Use our environmental obstack, as these nodes are always
 141      temporary. */
 142   old = current_ir_graph->obst;
 143   current_ir_graph->obst = env->obst;
 144   res   = new_ir_node(
 145             get_irn_dbg_info(node),
 146             current_ir_graph,
 147             pred_block,
 148             get_irn_op(node),
 149             get_irn_mode(node),
 150             arity,
 151             get_irn_in(node));
 152   /* We need the attribute copy here, because the Hash value of a
 153      node might depend on that. */
 154   copy_node_attr(node, res);
 155   current_ir_graph->obst = old;
 156
 157   for (i = -1; i < arity; ++i) {
 158     ir_node *pred = get_irn_intra_n(node, i);
 159
 160     if (! is_Phi(pred))
 161       set_irn_n(res, i, pred);
 162     else
 163       set_irn_n(res, i, get_Phi_pred(pred, pos));
 164   }
 165   set_irn_link(res, node);
 166   return res;
 167 }
 168
 169 /**
 170  * Retranslate a Phi-translated node back
 171  */
 172 static ir_node *phi_retrans(ir_node *n, avail_env *env)
 173 {
 174   if (node_is_in_irgs_storage(current_ir_graph, n))
 175     return n;
 176   return get_irn_link(n);
 177 }
 178
 179 /**
 180  * computes Antic_in(block):
 181  *
 182  */
 183 static void compute_antic(ir_node *block, void *ctx)
 184 {
 185   avail_env *env = ctx;
 186   block_info *succ_info;
 187   block_info *info = get_irn_link(block);
 188   ir_node *succ;
 189   int i, size;
 190
 191   size = pset_count(info->antic_in);
 192
 193   /* the root has no dominator */
 194   if (block != env->end_block) {
 195     int n_succ = get_Block_n_cfg_outs(block);
 196
 197     if (n_succ == 1) {
 198       ir_node *node;
 199       int i, pos = -1;
 200       pset *nodes = new_pset(identities_cmp, 8);
 201
 202       pset_union(nodes, info->nodes, ir_node_hash);
 203
 204       /* find blocks position in succ's block predecessors */
 205       succ = get_Block_cfg_out(block, 0);
 206       for (i = get_Block_n_cfgpreds(succ) - 1; i >= 0; --i) {
 207         if (get_Block_cfgpred_block(succ, i) == block) {
 208           pos = i;
 209           break;
 210         }
 211       }
 212       assert(pos >= 0);
 213
 214       succ_info = get_irn_link(succ);
 215       for (node = pset_first(succ_info->antic_in);
 216            node;
 217            node = pset_next(succ_info->antic_in)) {
 218         ir_node *trans = phi_translate(node, succ, pos, env);
 219
 220         identify_remember(nodes, trans);
 221
 222         /* add all predecessors of node */
 223         for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 224           ir_node *pred = get_irn_n(node, i);
 225           ir_node *trans = phi_translate(pred, succ, pos, env);
 226
 227           if (is_nice_value(trans))
 228             identify_remember(nodes, trans);
 229         }
 230       }
 231      /* this step calculates Antic_in(b) = Antic_out(b) \/ Nodes(b) */
 232      pset_union(info->antic_in, nodes, ir_node_hash);
 233      del_pset(nodes);
 234    }
 235     else {
 236       ir_node *n, *succ0;
 237       block_info *succ0_info;
 238       int i;
 239
 240       assert(n_succ > 1);
 241
 242       /* Select a successor to compute the disjoint of all Nodes
 243          sets, it might be useful to select the block with the
 244          smallest number of nodes.  For simplicity we choose the
 245          first one. */
 246       succ0 = get_Block_cfg_out(block, 0);
 247       succ0_info = get_irn_link(succ0);
 248       for (n = pset_first(succ0_info->antic_in);
 249            n;
 250            n = pset_next(succ0_info->antic_in)) {
 251         /* we need the disjoint */
 252         for (i = 1; i < n_succ; ++i) {
 253           ir_node *succ = get_Block_cfg_out(block, i);
 254           block_info *succ_info = get_irn_link(succ);
 255           if (pset_find(succ_info->antic_in, n, ir_node_hash(n)) == NULL)
 256             break;
 257         }
 258         if (i >= n_succ) {
 259           /* we found a node that is common in all Antic_in(succ(b)),
 260              put it in Antic_in(b) */
 261           identify_remember(info->antic_in, n);
 262         }
 263       }
 264       /* this step calculates Antic_in(b) = Antic_out(b) \/ Nodes(b) */
 265       pset_union(info->antic_in, info->nodes, ir_node_hash);
 266     }
 267   }
 268
 269   if (size != pset_count(info->antic_in))
 270     /* the Antic_in set has changed */
 271     env->changes |= 1;
 272
 273 #ifdef _DEBUG
 274   {
 275     ir_node *n;
 276
 277     ir_printf("Antic_in(%+F) = {\n", block);
 278     for (i = 0, n = pset_first(info->antic_in); n; ++i, n = pset_next(info->antic_in)) {
 279       ir_node *orig = phi_retrans(n, env);
 280       if ((i & 3) == 3)
 281         printf("\n");
 282       ir_printf(" %+F%", n);
 283       if (orig != n)
 284         ir_printf("{%+F}", orig);
 285       printf(", ");
 286     }
 287     printf("\n}\n");
 288   }
 289 #endif
 290 }
 291
 292 /**
 293  * allocate a block info
 294  */
 295 static void alloc_blk_info(ir_node *block, void *ctx)
 296 {
 297   int i;
 298   avail_env *env = ctx;
 299   block_info *info = obstack_alloc(env->obst, sizeof(block_info));
 300
 301   set_irn_link(block, info);
 302   info->nodes     = new_pset(identities_cmp, 8);
 303   info->antic_in  = new_pset(identities_cmp, 8);
 304   info->avail_out = new_pset(identities_cmp, 8);
 305   info->next      = env->list;
 306   env->list       = info->next;
 307
 308   /* fill the nodes set, we will need it later */
 309   for (i = get_irn_n_outs(block) - 1; i >= 0; --i) {
 310     ir_node *n = get_irn_out(block, i);
 311
 312     /* we cannot optimize pinned nodes, so do not remember them */
 313     if (is_nice_value(n))
 314       identify_remember(info->nodes, n);
 315     else if (is_Phi(n) && get_irn_mode(n) != mode_M) {
 316       /*
 317        * Phis are "temporaries" and must be handled special:
 318        * They are avail, but are not in Antic_in
 319        */
 320       identify_remember(info->avail_out, n);
 321     }
 322   }
 323 }
 324
 325 /**
 326  * Insert the nodes.
 327  */
 328 static void insert_nodes(ir_node *block, void *ctx)
 329 {
 330   avail_env *env = ctx;
 331   ir_node *v, *idom, *first_s;
 332   block_info *info, *idom_info;
 333   int pos, arity = get_irn_intra_arity(block);
 334   int all_same, by_some;
 335
 336   if (arity <= 1)
 337     return;
 338
 339   info = get_irn_link(block);
 340
 341   idom = get_Block_idom(block);
 342   idom_info = get_irn_link(idom);
 343   for (v = pset_first(info->antic_in);
 344        v;
 345        v = pset_next(info->antic_in)) {
 346     /* If the value was already computed in the dominator, then
 347        it is totally redundant.  Hence we have nothing to insert. */
 348     if (pset_find(idom_info->avail_out, v, ir_node_hash(v))) {
 349 //      ir_printf("Found %+F from block %+F avail in dom %+F\n", v, block, idom);
 350       continue;
 351     }
 352
 353     all_same = 1;
 354     by_some  = 0;
 355     first_s  = NULL;
 356
 357     for (pos = 0; pos < arity; ++pos) {
 358       block_info *pred_info;
 359       ir_node *pred = get_Block_cfgpred_block(block, pos);
 360       ir_node *trans, *found;
 361
 362       if (is_Bad(pred))
 363         continue;
 364
 365       trans = phi_translate(v, block, pos, env);
 366
 367       pred_info = get_irn_link(pred);
 368       found = pset_find(pred_info->avail_out, trans, ir_node_hash(trans));
 369
 370       if (found == NULL) {
 371         all_same = 0;
 372       }
 373       else {
 374         by_some = 1;
 375         if (first_s == NULL)
 376           first_s = found;
 377         else if (first_s != found)
 378           all_same = 0;
 379
 380         ir_printf("Found %+F from block %+F as %+F in pred %+F\n", v, block, found, pred);
 381       }
 382     }
 383
 384     if (! all_same && by_some) {
 385       ir_printf("Partial redundant %+F from block %+F found\n", v, block);
 386     }
 387   }
 388 }
 389
 390 void do_gvn_pre(ir_graph *irg)
 391 {
 392   struct obstack obst;
 393   avail_env a_env;
 394   optimization_state_t state;
 395   block_info *p;
 396   int iter = 0;
 397
 398   obstack_init(&obst);
 399   a_env.obst        = &obst;
 400   a_env.list        = NULL;
 401   a_env.start_block = get_irg_start_block(irg);
 402   a_env.end_block   = get_irg_end_block(irg);
 403
 404   remove_critical_cf_edges(irg);
 405
 406   /* we need dominator AND post dominator information */
 407   if (get_irg_dom_state(irg) != dom_consistent)
 408     compute_doms(irg);
 409   if (get_irg_postdom_state(irg) != dom_consistent)
 410     compute_postdoms(irg);
 411   if (get_irg_outs_state(irg) != outs_consistent)
 412     compute_irg_outs(irg);
 413
 414   save_optimization_state(&state);
 415   set_opt_global_cse(1);
 416
 417   /* allocate block info for all blocks */
 418   irg_block_walk_graph(irg, NULL, alloc_blk_info, &a_env);
 419
 420   /* compute the available value sets for all blocks */
 421   dom_tree_walk_irg(irg, compute_avail_top_down, NULL, &a_env);
 422
 423   /* compute the anticipated value sets for all blocks */
 424   do {
 425 #ifdef _DEBUG
 426     printf("Antic_in Iteration %d starts ...\n", ++iter);
 427 #endif /* _DEBUG */
 428     a_env.changes = 0;
 429     irg_block_walk_graph(irg, compute_antic, NULL, &a_env);
 430 //    postdom_tree_walk_irg(irg, compute_antic, NULL, &a_env);
 431 #ifdef _DEBUG
 432     printf("------------------------\n");
 433 #endif /* _DEBUG */
 434   } while (a_env.changes != 0);
 435
 436   iter = 0;
 437   do {
 438 #ifdef _DEBUG
 439     printf("Insert Iteration %d starts ...\n", ++iter);
 440 #endif /* _DEBUG */
 441     a_env.changes = 0;
 442     irg_block_walk_graph(irg, insert_nodes, NULL, &a_env);
 443 //    dom_tree_walk_irg(irg, insert_nodes, NULL, &a_env);
 444 #ifdef _DEBUG
 445     printf("------------------------\n");
 446 #endif /* _DEBUG */
 447   } while (a_env.changes != 0);
 448
 449   restore_optimization_state(&state);
 450
 451   for (p = a_env.list; p != NULL; p = p->next) {
 452     if (p->antic_in)
 453       del_pset(p->antic_in);
 454     if (p->avail_out)
 455       del_pset(p->avail_out);
 456   }
 457   obstack_free(&obst, NULL);
 458 }