nsz Git - libfirm/blob - ir/ana/height.c

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