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