nsz Git - libfirm/blob - ir/ana/heights.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    Compute heights of nodes inside basic blocks
  23  * @author   Sebastian Hack
  24  * @date     19.04.2006
  25  */
  26 #include "config.h"
  27
  28 #include "heights.h"
  29
  30 #include <stdlib.h>
  31 #include <stdio.h>
  32 #include <stdbool.h>
  33
  34 #include "irdump.h"
  35 #include "irgwalk.h"
  36 #include "irnodemap.h"
  37 #include "iredges_t.h"
  38 #include "list.h"
  39 #include "util.h"
  40
  41 struct ir_heights_t {
  42         ir_nodemap      data;
  43         unsigned        visited;
  44         void           *dump_handle;
  45         struct obstack  obst;
  46 };
  47
  48 typedef struct {
  49         unsigned height;
  50         unsigned visited;
  51 } irn_height_t;
  52
  53 static irn_height_t *maybe_get_height_data(const ir_heights_t *heights,
  54                                            const ir_node *node)
  55 {
  56         irn_height_t *height = (irn_height_t*)ir_nodemap_get(&heights->data, node);
  57         return height;
  58 }
  59
  60 static irn_height_t *get_height_data(ir_heights_t *heights, const ir_node *node)
  61 {
  62         irn_height_t *height = (irn_height_t*)ir_nodemap_get(&heights->data, node);
  63         if (height == NULL) {
  64                 height = OALLOCZ(&heights->obst, irn_height_t);
  65                 ir_nodemap_insert(&heights->data, node, height);
  66         }
  67         return height;
  68 }
  69
  70 static void height_dump_cb(void *data, FILE *f, const ir_node *irn)
  71 {
  72         const ir_heights_t *heights = (const ir_heights_t*) data;
  73         const irn_height_t *h       = maybe_get_height_data(heights, irn);
  74         if (h != NULL)
  75                 fprintf(f, "height: %u\n", h->height);
  76 }
  77
  78 /**
  79  * Check, if we can reach a target node from a given node inside one basic block.
  80  * @param h    The heights object.
  81  * @param curr The current node from which we tried to reach the other one.
  82  * @param tgt  The node we try to reach.
  83  * @return     1, one of tgt can be reached from curr, 0 else.
  84  */
  85 static bool search(ir_heights_t *h, const ir_node *curr, const ir_node *tgt)
  86 {
  87         irn_height_t *h_curr;
  88         irn_height_t *h_tgt;
  89         int i, n;
  90
  91         /* if the current node is the one we were looking for, we're done. */
  92         if (curr == tgt)
  93                 return true;
  94
  95         /* If we are in another block or at a phi we won't find our target. */
  96         if (get_nodes_block(curr) != get_nodes_block(tgt))
  97                 return false;
  98         if (is_Phi(curr))
  99                 return false;
 100
 101         /* Check, if we have already been here. Coming more often won't help :-) */
 102         h_curr = maybe_get_height_data(h, curr);
 103         if (h_curr->visited >= h->visited)
 104                 return false;
 105
 106         /* If we are too deep into the DAG we won't find the target either. */
 107         h_tgt = maybe_get_height_data(h, tgt);
 108         if (h_curr->height > h_tgt->height)
 109                 return false;
 110
 111         /* Mark this place as visited. */
 112         h_curr->visited = h->visited;
 113
 114         /* Start a search from this node. */
 115         for (i = 0, n = get_irn_ins_or_deps(curr); i < n; ++i) {
 116                 ir_node *op = get_irn_in_or_dep(curr, i);
 117                 if (search(h, op, tgt))
 118                         return true;
 119         }
 120
 121         return false;
 122 }
 123
 124 int heights_reachable_in_block(ir_heights_t *h, const ir_node *n,
 125                                const ir_node *m)
 126 {
 127         int res          = 0;
 128         irn_height_t *hn = maybe_get_height_data(h, n);
 129         irn_height_t *hm = maybe_get_height_data(h, m);
 130
 131         assert(get_nodes_block(n) == get_nodes_block(m));
 132         assert(hn != NULL && hm != NULL);
 133
 134         if (hn->height <= hm->height) {
 135                 h->visited++;
 136                 res = search(h, n, m);
 137         }
 138
 139         return res;
 140 }
 141
 142 /**
 143  * Compute the height of a node in a block.
 144  * @param h   The heights object.
 145  * @param irn The node.
 146  * @param bl  The block.
 147  */
 148 static unsigned compute_height(ir_heights_t *h, ir_node *irn, const ir_node *bl)
 149 {
 150         irn_height_t *ih = get_height_data(h, irn);
 151
 152         const ir_edge_t *edge;
 153
 154         /* bail out if we already visited that node. */
 155         if (ih->visited >= h->visited)
 156                 return ih->height;
 157
 158         ih->visited = h->visited;
 159         ih->height  = 0;
 160
 161         foreach_out_edge(irn, edge) {
 162                 ir_node *dep = get_edge_src_irn(edge);
 163
 164                 if (!is_Block(dep) && !is_Phi(dep) && get_nodes_block(dep) == bl) {
 165                         unsigned dep_height = compute_height(h, dep, bl);
 166                         ih->height          = MAX(ih->height, dep_height);
 167                 }
 168
 169                 ih->height++;
 170         }
 171
 172         foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
 173                 ir_node *dep = get_edge_src_irn(edge);
 174
 175                 assert(!is_Phi(dep));
 176                 if (!is_Block(dep) && get_nodes_block(dep) == bl) {
 177                         unsigned dep_height = compute_height(h, dep, bl);
 178                         ih->height          = MAX(ih->height, dep_height);
 179                 }
 180
 181                 ih->height++;
 182         }
 183
 184         return ih->height;
 185 }
 186
 187 static unsigned compute_heights_in_block(ir_node *bl, ir_heights_t *h)
 188 {
 189         int             max_height = -1;
 190         const ir_edge_t *edge;
 191
 192         h->visited++;
 193
 194         foreach_out_edge(bl, edge) {
 195                 ir_node *dep = get_edge_src_irn(edge);
 196                 int     curh = compute_height(h, dep, bl);
 197
 198                 max_height = MAX(curh, max_height);
 199         }
 200
 201         foreach_out_edge_kind(bl, edge, EDGE_KIND_DEP) {
 202                 ir_node *dep = get_edge_src_irn(edge);
 203                 int     curh = compute_height(h, dep, bl);
 204
 205                 max_height = MAX(curh, max_height);
 206         }
 207
 208         return max_height;
 209 }
 210
 211 static void compute_heights_in_block_walker(ir_node *block, void *data)
 212 {
 213         ir_heights_t *h = (ir_heights_t*) data;
 214         compute_heights_in_block(block, h);
 215 }
 216
 217 unsigned get_irn_height(const ir_heights_t *heights, const ir_node *irn)
 218 {
 219         const irn_height_t *height = maybe_get_height_data(heights, irn);
 220         assert(height != NULL && "No height information for node");
 221         return height->height;
 222 }
 223
 224 unsigned heights_recompute_block(ir_heights_t *h, ir_node *block)
 225 {
 226         ir_graph *irg = get_irn_irg(block);
 227         const ir_edge_t *edge;
 228
 229         edges_assure(irg);
 230
 231         /* reset phase data for all nodes in the block */
 232         foreach_out_edge(block, edge) {
 233                 ir_node      *irn = get_edge_src_irn(edge);
 234                 irn_height_t *ih  = get_height_data(h, irn);
 235                 memset(ih, 0, sizeof(*ih));
 236         }
 237
 238         h->visited = 0;
 239         return compute_heights_in_block(block, h);
 240 }
 241
 242 ir_heights_t *heights_new(ir_graph *irg)
 243 {
 244         ir_heights_t *res = XMALLOCZ(ir_heights_t);
 245         ir_nodemap_init(&res->data, irg);
 246         obstack_init(&res->obst);
 247         res->dump_handle = dump_add_node_info_callback(height_dump_cb, res);
 248
 249         edges_assure(irg);
 250         irg_block_walk_graph(irg, compute_heights_in_block_walker, NULL, res);
 251
 252         return res;
 253 }
 254
 255 void heights_free(ir_heights_t *h)
 256 {
 257         dump_remove_node_info_callback(h->dump_handle);
 258         obstack_free(&h->obst, NULL);
 259         ir_nodemap_destroy(&h->data);
 260         xfree(h);
 261 }