nsz Git - libfirm/blob - ir/ana/domfront.c

   1 /*
   2  * Copyright (C) 1995-2011 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 dominance frontiers.
  23  * @author      Sebastian Hack, Daniel Grund
  24  * @date        04.05.2005
  25  */
  26 #include "config.h"
  27
  28 #include "obst.h"
  29 #include "pmap.h"
  30 #include "pdeq.h"
  31 #include "irdom.h"
  32 #include "array.h"
  33 #include "irgraph.h"
  34 #include "iredges_t.h"
  35 #include "irnodeset.h"
  36
  37 /**
  38  * A wrapper for get_Block_idom.
  39  * This function returns the block itself, if the block is the start
  40  * block. Returning NULL would make any != comparison true which
  41  * suggests, that the start block is dominated by some other node.
  42  * @param bl The block.
  43  * @return The immediate dominator of the block.
  44  */
  45 static inline ir_node *get_idom(ir_node *bl)
  46 {
  47         ir_node *idom = get_Block_idom(bl);
  48         return idom == NULL ? bl : idom;
  49 }
  50
  51 /**
  52  * Compute the dominance frontier for a given block.
  53  *
  54  * @param blk   the block where the calculation starts
  55  *
  56  * @return the list of all blocks in the dominance frontier of blk
  57  */
  58 static ir_node **compute_df(ir_node *blk, ir_dom_front_info_t *info)
  59 {
  60         ir_node *c;
  61         ir_node **df_list = NEW_ARR_F(ir_node *, 0);
  62
  63         /* Add local dominance frontiers */
  64         foreach_block_succ(blk, edge) {
  65                 ir_node *y = get_edge_src_irn(edge);
  66
  67                 if (get_idom(y) != blk) {
  68                         ARR_APP1(ir_node *, df_list, y);
  69                 }
  70         }
  71
  72         /*
  73          * Go recursively down the dominance tree and add all blocks
  74          * into the dominance frontiers of the children, which are not
  75          * dominated by the given block.
  76          */
  77         for (c = get_Block_dominated_first(blk); c; c = get_Block_dominated_next(c)) {
  78                 size_t i;
  79                 ir_node **df_c_list = compute_df(c, info);
  80
  81                 for (i = ARR_LEN(df_c_list); i > 0;) {
  82                         ir_node *w = df_c_list[--i];
  83                         if (get_idom(w) != blk)
  84                                 ARR_APP1(ir_node *, df_list, w);
  85                 }
  86         }
  87
  88         /* now copy the flexible array to the obstack */
  89         ir_node **const df = DUP_ARR_D(ir_node*, &info->obst, df_list);
  90         DEL_ARR_F(df_list);
  91
  92         pmap_insert(info->df_map, blk, df);
  93         return df;
  94 }
  95
  96 void ir_compute_dominance_frontiers(ir_graph *irg)
  97 {
  98         ir_dom_front_info_t *info = &irg->domfront;
  99
 100         assure_edges(irg);
 101         obstack_init(&info->obst);
 102         info->df_map = pmap_create();
 103         assure_doms(irg);
 104         compute_df(get_irg_start_block(irg), info);
 105
 106         add_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS);
 107 }
 108
 109 void ir_free_dominance_frontiers(ir_graph *irg)
 110 {
 111         clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS);
 112
 113         ir_dom_front_info_t *info = &irg->domfront;
 114         if (info->df_map == NULL)
 115                 return;
 116
 117         obstack_free(&info->obst, NULL);
 118         pmap_destroy(info->df_map);
 119         info->df_map = NULL;
 120 }
 121
 122 /* Get the dominance frontier of a block. */
 123 ir_node **ir_get_dominance_frontier(const ir_node *block)
 124 {
 125         ir_graph            *irg  = get_irn_irg(block);
 126         ir_dom_front_info_t *info = &irg->domfront;
 127         return pmap_get(ir_node*, info->df_map, block);
 128 }