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