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 "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 ir_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 = (irn_height_t*) 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         ir_heights_t *heights = (ir_heights_t*) data;
  74         irn_height_t *h       = (irn_height_t*) 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 ir_heights_t *h, const ir_node *curr,
  88                    const ir_node *tgt)
  89 {
  90         irn_height_t *h_curr;
  91         irn_height_t *h_tgt;
  92         int i, n;
  93
  94         /* if the current node is the one we were looking for, we're done. */
  95         if (curr == tgt)
  96                 return true;
  97
  98         /* If we are in another block or at a phi we won't find our target. */
  99         if (get_nodes_block(curr) != get_nodes_block(tgt))
 100                 return false;
 101         if (is_Phi(curr))
 102                 return false;
 103
 104         /* Check, if we have already been here. Coming more often won't help :-) */
 105         h_curr = (irn_height_t*) phase_get_irn_data(&h->phase, curr);
 106         if (h_curr->visited >= h->visited)
 107                 return false;
 108
 109         /* If we are too deep into the DAG we won't find the target either. */
 110         h_tgt = (irn_height_t*) phase_get_irn_data(&h->phase, tgt);
 111         if (h_curr->height > h_tgt->height)
 112                 return false;
 113
 114         /* Mark this place as visited. */
 115         h_curr->visited = h->visited;
 116
 117         /* Start a search from this node. */
 118         for (i = 0, n = get_irn_ins_or_deps(curr); i < n; ++i) {
 119                 ir_node *op = get_irn_in_or_dep(curr, i);
 120                 if (search(h, op, tgt))
 121                         return true;
 122         }
 123
 124         return false;
 125 }
 126
 127 /**
 128  * Check, if one node can be reached from another one, according to data
 129  * dependence.
 130  */
 131 int heights_reachable_in_block(ir_heights_t *h, const ir_node *n,
 132                                const ir_node *m)
 133 {
 134         int res          = 0;
 135         irn_height_t *hn = (irn_height_t*) phase_get_irn_data(&h->phase, n);
 136         irn_height_t *hm = (irn_height_t*) phase_get_irn_data(&h->phase, m);
 137
 138         assert(get_nodes_block(n) == get_nodes_block(m));
 139         assert(hn != NULL && hm != NULL);
 140
 141         if (hn->height <= hm->height) {
 142                 h->visited++;
 143                 res = search(h, n, m);
 144         }
 145
 146         return res;
 147 }
 148
 149 /**
 150  * Compute the height of a node in a block.
 151  * @param h   The heights object.
 152  * @param irn The node.
 153  * @param bl  The block.
 154  */
 155 static unsigned compute_height(ir_heights_t *h, ir_node *irn, const ir_node *bl)
 156 {
 157         irn_height_t *ih = (irn_height_t*) phase_get_or_set_irn_data(&h->phase, irn);
 158
 159         const ir_edge_t *edge;
 160
 161         /* bail out if we already visited that node. */
 162         if (ih->visited >= h->visited)
 163                 return ih->height;
 164
 165         ih->visited = h->visited;
 166         ih->height  = 0;
 167
 168         foreach_out_edge(irn, edge) {
 169                 ir_node *dep = get_edge_src_irn(edge);
 170
 171                 if (!is_Block(dep) && !is_Phi(dep) && get_nodes_block(dep) == bl) {
 172                         unsigned dep_height = compute_height(h, dep, bl);
 173                         ih->height          = MAX(ih->height, dep_height);
 174                 }
 175
 176                 ih->height++;
 177         }
 178
 179         foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
 180                 ir_node *dep = get_edge_src_irn(edge);
 181
 182                 assert(!is_Phi(dep));
 183                 if (!is_Block(dep) && get_nodes_block(dep) == bl) {
 184                         unsigned dep_height = compute_height(h, dep, bl);
 185                         ih->height          = MAX(ih->height, dep_height);
 186                 }
 187
 188                 ih->height++;
 189         }
 190
 191         return ih->height;
 192 }
 193
 194 static unsigned compute_heights_in_block(ir_node *bl, ir_heights_t *h)
 195 {
 196         int             max_height = -1;
 197         const ir_edge_t *edge;
 198
 199         h->visited++;
 200
 201         foreach_out_edge(bl, edge) {
 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         foreach_out_edge_kind(bl, edge, EDGE_KIND_DEP) {
 209                 ir_node *dep = get_edge_src_irn(edge);
 210                 int     curh = compute_height(h, dep, bl);
 211
 212                 max_height = MAX(curh, max_height);
 213         }
 214
 215         return max_height;
 216 }
 217
 218 static void compute_heights_in_block_walker(ir_node *block, void *data)
 219 {
 220         ir_heights_t *h = (ir_heights_t*) data;
 221         compute_heights_in_block(block, h);
 222 }
 223
 224 unsigned get_irn_height(const ir_heights_t *heights, const ir_node *irn)
 225 {
 226         const irn_height_t *h = (irn_height_t*) phase_get_irn_data(&heights->phase, irn);
 227         assert(h && "No height information for node");
 228         return h->height;
 229 }
 230
 231 unsigned heights_recompute_block(ir_heights_t *h, ir_node *block)
 232 {
 233         const ir_edge_t *edge;
 234
 235         edges_assure(phase_get_irg(&h->phase));
 236
 237         /* reset phase data for all nodes in the block */
 238         foreach_out_edge(block, edge) {
 239                 ir_node      *irn = get_edge_src_irn(edge);
 240                 irn_height_t *ih  = (irn_height_t*) phase_get_irn_data(&h->phase, irn);
 241                 memset(ih, 0, sizeof(*ih));
 242         }
 243
 244         h->visited = 0;
 245         return compute_heights_in_block(block, h);
 246 }
 247
 248 void heights_recompute(ir_heights_t *h)
 249 {
 250         ir_graph *irg = phase_get_irg(&h->phase);
 251
 252         edges_assure(irg);
 253         phase_reinit_irn_data(&h->phase, irn_height_reinit);
 254         h->visited = 0;
 255         irg_block_walk_graph(irg, compute_heights_in_block_walker, NULL, h);
 256 }
 257
 258 ir_heights_t *heights_new(ir_graph *irg)
 259 {
 260         ir_heights_t *res = XMALLOC(ir_heights_t);
 261         phase_init(&res->phase, irg, irn_height_init);
 262         res->dump_handle = dump_add_node_info_callback(height_dump_cb, res);
 263         heights_recompute(res);
 264
 265         return res;
 266 }
 267
 268 void heights_free(ir_heights_t *h)
 269 {
 270         phase_deinit(&h->phase);
 271         dump_remove_node_info_callback(h->dump_handle);
 272         xfree(h);
 273 }