nsz Git - libfirm/blob - ir/be/bedomfront.c

   1 /**
   2  * @file
   3  * @author      Sebastian Hack, Daniel Grund
   4  * @date:       04.05.2005
   5  * @version     $Id$
   6  * Copyright:   (c) Universitaet Karlsruhe
   7  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
   8  */
   9 #ifdef HAVE_CONFIG_H
  10 #include <config.h>
  11 #endif
  12
  13 #include "bedomfront.h"
  14
  15 #include "obst.h"
  16 #include "pmap.h"
  17 #include "pdeq.h"
  18 #include "irdom.h"
  19 #include "array.h"
  20 #include "irgraph.h"
  21 #include "iredges_t.h"
  22
  23 /**
  24  * The dominance frontier for a graph.
  25  */
  26 struct _be_dom_front_info_t {
  27         pmap *df_map;         /**< A map, mapping every block to a list of its dominance frontier blocks. */
  28         struct obstack obst;  /**< An obstack holding all the frontier data. */
  29 };
  30
  31 /**
  32  * A wrapper for get_Block_idom.
  33  * This function returns the block itself, if the block is the start
  34  * block. Returning NULL would make any != comparison true which
  35  * suggests, that the start block is dominated by some other node.
  36  * @param bl The block.
  37  * @return The immediate dominator of the block.
  38  */
  39 static INLINE
  40 ir_node *get_idom(ir_node *bl)
  41 {
  42         ir_node *idom = get_Block_idom(bl);
  43         return idom == NULL ? bl : idom;
  44 }
  45
  46 /**
  47  * Compute the dominance frontier for a given block.
  48  *
  49  * @param blk   the block where the calculation starts
  50  *
  51  * @return the list of all blocks in the dominance frontier of blk
  52  */
  53 static
  54 ir_node **compute_df(ir_node *blk, be_dom_front_info_t *info)
  55 {
  56         ir_node *c;
  57         const ir_edge_t *edge;
  58         ir_node **df_list = NEW_ARR_F(ir_node *, 0);
  59         ir_node **df;
  60         int len;
  61
  62         /* Add local dominance frontiers */
  63         foreach_block_succ(blk, edge) {
  64                 ir_node *y = get_edge_src_irn(edge);
  65
  66                 if (get_idom(y) != blk) {
  67                         ARR_APP1(ir_node *, df_list, y);
  68                 }
  69         }
  70
  71         /*
  72          * Go recursively down the dominance tree and add all blocks
  73          * into the dominance frontiers of the children, which are not
  74          * dominated by the given block.
  75          */
  76         for (c = get_Block_dominated_first(blk); c; c = get_Block_dominated_next(c)) {
  77                 int i;
  78                 ir_node **df_c_list = compute_df(c, info);
  79
  80                 for (i = ARR_LEN(df_c_list) - 1; i >= 0; --i) {
  81                         ir_node *w = df_c_list[i];
  82                         if (get_idom(w) != blk)
  83                                 ARR_APP1(ir_node *, df_list, w);
  84                 }
  85         }
  86
  87         /* now copy the flexible array to the obstack */
  88         len = ARR_LEN(df_list);
  89         df = NEW_ARR_D(ir_node *, &info->obst, len);
  90         memcpy(df, df_list, len * sizeof(df[0]));
  91         DEL_ARR_F(df_list);
  92
  93         pmap_insert(info->df_map, blk, df);
  94         return df;
  95 }
  96
  97 be_dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg)
  98 {
  99         be_dom_front_info_t *info = xmalloc(sizeof(*info));
 100
 101         edges_assure(irg);
 102         obstack_init(&info->obst);
 103         info->df_map = pmap_create();
 104         assure_doms(irg);
 105         (void)compute_df(get_irg_start_block(irg), info);
 106
 107         return info;
 108 }
 109
 110 void be_free_dominance_frontiers(be_dom_front_info_t *info)
 111 {
 112         obstack_free(&info->obst, NULL);
 113         pmap_destroy(info->df_map);
 114         free(info);
 115 }
 116
 117 /* Get the dominance frontier of a block. */
 118 ir_node **be_get_dominance_frontier(const be_dom_front_info_t *info,
 119                                     ir_node *block)
 120 {
 121         return pmap_get(info->df_map, block);
 122 }
 123
 124 /**
 125  * Calculates the iterated dominance frontier of a set of blocks.
 126  * Also clears the link field of the returned blocks as a side effect
 127  */
 128 void be_get_iterated_dominance_frontiers(const be_dom_front_info_t *domfronts,
 129                                          ir_nodeset_t *blocks)
 130 {
 131         ir_node *block;
 132         ir_nodeset_iterator_t iter;
 133         waitq *worklist = new_waitq();
 134
 135         foreach_ir_nodeset(blocks, block, iter) {
 136                 waitq_put(worklist, block);
 137         }
 138
 139         while(!pdeq_empty(worklist)) {
 140                 int i;
 141                 ir_node *block = waitq_get(worklist);
 142                 ir_node **domfront = be_get_dominance_frontier(domfronts, block);
 143                 int domfront_len = ARR_LEN(domfront);
 144
 145                 for (i = 0; i < domfront_len; ++i) {
 146                         ir_node *y = domfront[i];
 147                         if(!ir_nodeset_insert(blocks, y))
 148                                 continue;
 149
 150                         waitq_put(worklist, y);
 151                 }
 152         }
 153
 154         del_waitq(worklist);
 155 }