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