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 /**
 125  * Check, if one node can be reached from another one, according to data
 126  * dependence.
 127  */
 128 int heights_reachable_in_block(ir_heights_t *h, const ir_node *n,
 129                                const ir_node *m)
 130 {
 131         int res          = 0;
 132         irn_height_t *hn = maybe_get_height_data(h, n);
 133         irn_height_t *hm = maybe_get_height_data(h, m);
 134
 135         assert(get_nodes_block(n) == get_nodes_block(m));
 136         assert(hn != NULL && hm != NULL);
 137
 138         if (hn->height <= hm->height) {
 139                 h->visited++;
 140                 res = search(h, n, m);
 141         }
 142
 143         return res;
 144 }
 145
 146 /**
 147  * Compute the height of a node in a block.
 148  * @param h   The heights object.
 149  * @param irn The node.
 150  * @param bl  The block.
 151  */
 152 static unsigned compute_height(ir_heights_t *h, ir_node *irn, const ir_node *bl)
 153 {
 154         irn_height_t *ih = get_height_data(h, irn);
 155
 156         const ir_edge_t *edge;
 157
 158         /* bail out if we already visited that node. */
 159         if (ih->visited >= h->visited)
 160                 return ih->height;
 161
 162         ih->visited = h->visited;
 163         ih->height  = 0;
 164
 165         foreach_out_edge(irn, edge) {
 166                 ir_node *dep = get_edge_src_irn(edge);
 167
 168                 if (!is_Block(dep) && !is_Phi(dep) && get_nodes_block(dep) == bl) {
 169                         unsigned dep_height = compute_height(h, dep, bl);
 170                         ih->height          = MAX(ih->height, dep_height);
 171                 }
 172
 173                 ih->height++;
 174         }
 175
 176         foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
 177                 ir_node *dep = get_edge_src_irn(edge);
 178
 179                 assert(!is_Phi(dep));
 180                 if (!is_Block(dep) && get_nodes_block(dep) == bl) {
 181                         unsigned dep_height = compute_height(h, dep, bl);
 182                         ih->height          = MAX(ih->height, dep_height);
 183                 }
 184
 185                 ih->height++;
 186         }
 187
 188         return ih->height;
 189 }
 190
 191 static unsigned compute_heights_in_block(ir_node *bl, ir_heights_t *h)
 192 {
 193         int             max_height = -1;
 194         const ir_edge_t *edge;
 195
 196         h->visited++;
 197
 198         foreach_out_edge(bl, edge) {
 199                 ir_node *dep = get_edge_src_irn(edge);
 200                 int     curh = compute_height(h, dep, bl);
 201
 202                 max_height = MAX(curh, max_height);
 203         }
 204
 205         foreach_out_edge_kind(bl, edge, EDGE_KIND_DEP) {
 206                 ir_node *dep = get_edge_src_irn(edge);
 207                 int     curh = compute_height(h, dep, bl);
 208
 209                 max_height = MAX(curh, max_height);
 210         }
 211
 212         return max_height;
 213 }
 214
 215 static void compute_heights_in_block_walker(ir_node *block, void *data)
 216 {
 217         ir_heights_t *h = (ir_heights_t*) data;
 218         compute_heights_in_block(block, h);
 219 }
 220
 221 unsigned get_irn_height(const ir_heights_t *heights, const ir_node *irn)
 222 {
 223         const irn_height_t *height = maybe_get_height_data(heights, irn);
 224         assert(height != NULL && "No height information for node");
 225         return height->height;
 226 }
 227
 228 unsigned heights_recompute_block(ir_heights_t *h, ir_node *block)
 229 {
 230         ir_graph *irg = get_irn_irg(block);
 231         const ir_edge_t *edge;
 232
 233         edges_assure(irg);
 234
 235         /* reset phase data for all nodes in the block */
 236         foreach_out_edge(block, edge) {
 237                 ir_node      *irn = get_edge_src_irn(edge);
 238                 irn_height_t *ih  = get_height_data(h, irn);
 239                 memset(ih, 0, sizeof(*ih));
 240         }
 241
 242         h->visited = 0;
 243         return compute_heights_in_block(block, h);
 244 }
 245
 246 ir_heights_t *heights_new(ir_graph *irg)
 247 {
 248         ir_heights_t *res = XMALLOCZ(ir_heights_t);
 249         ir_nodemap_init(&res->data, irg);
 250         obstack_init(&res->obst);
 251         res->dump_handle = dump_add_node_info_callback(height_dump_cb, res);
 252
 253         edges_assure(irg);
 254         irg_block_walk_graph(irg, compute_heights_in_block_walker, NULL, res);
 255
 256         return res;
 257 }
 258
 259 void heights_free(ir_heights_t *h)
 260 {
 261         dump_remove_node_info_callback(h->dump_handle);
 262         obstack_free(&h->obst, NULL);
 263         ir_nodemap_destroy(&h->data);
 264         xfree(h);
 265 }