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