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

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