2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Compute heights of nodes inside basic blocks
9 * @author Sebastian Hack
22 #include "irnodemap.h"
23 #include "iredges_t.h"
39 static irn_height_t *maybe_get_height_data(const ir_heights_t *heights,
42 irn_height_t *height = ir_nodemap_get(irn_height_t, &heights->data, node);
46 static irn_height_t *get_height_data(ir_heights_t *heights, const ir_node *node)
48 irn_height_t *height = ir_nodemap_get(irn_height_t, &heights->data, node);
50 height = OALLOCZ(&heights->obst, irn_height_t);
51 ir_nodemap_insert(&heights->data, node, height);
56 static void height_dump_cb(void *data, FILE *f, const ir_node *irn)
58 const ir_heights_t *heights = (const ir_heights_t*) data;
59 const irn_height_t *h = maybe_get_height_data(heights, irn);
61 fprintf(f, "height: %u\n", h->height);
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.
71 static bool search(ir_heights_t *h, const ir_node *curr, const ir_node *tgt)
77 /* if the current node is the one we were looking for, we're done. */
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))
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)
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)
97 /* Mark this place as visited. */
98 h_curr->visited = h->visited;
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))
110 int heights_reachable_in_block(ir_heights_t *h, const ir_node *n,
114 irn_height_t *hn = maybe_get_height_data(h, n);
115 irn_height_t *hm = maybe_get_height_data(h, m);
117 assert(get_nodes_block(n) == get_nodes_block(m));
118 assert(hn != NULL && hm != NULL);
120 if (hn->height <= hm->height) {
122 res = search(h, n, m);
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.
134 static unsigned compute_height(ir_heights_t *h, ir_node *irn, const ir_node *bl)
136 irn_height_t *ih = get_height_data(h, irn);
138 /* bail out if we already visited that node. */
139 if (ih->visited >= h->visited)
142 ih->visited = h->visited;
145 foreach_out_edge(irn, edge) {
146 ir_node *dep = get_edge_src_irn(edge);
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);
156 foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
157 ir_node *dep = get_edge_src_irn(edge);
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);
171 static unsigned compute_heights_in_block(ir_node *bl, ir_heights_t *h)
177 foreach_out_edge(bl, edge) {
178 ir_node *dep = get_edge_src_irn(edge);
179 int curh = compute_height(h, dep, bl);
181 max_height = MAX(curh, max_height);
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);
188 max_height = MAX(curh, max_height);
194 static void compute_heights_in_block_walker(ir_node *block, void *data)
196 ir_heights_t *h = (ir_heights_t*) data;
197 compute_heights_in_block(block, h);
200 unsigned get_irn_height(const ir_heights_t *heights, const ir_node *irn)
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;
207 unsigned heights_recompute_block(ir_heights_t *h, ir_node *block)
209 ir_graph *irg = get_irn_irg(block);
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));
221 return compute_heights_in_block(block, h);
224 ir_heights_t *heights_new(ir_graph *irg)
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);
232 irg_block_walk_graph(irg, compute_heights_in_block_walker, NULL, res);
237 void heights_free(ir_heights_t *h)
239 dump_remove_node_info_callback(h->dump_handle);
240 obstack_free(&h->obst, NULL);
241 ir_nodemap_destroy(&h->data);