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

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