3 * File name: ir/ana/height.c
4 * Purpose: Compute heights of nodes inside basic blocks
5 * Author: Sebastian Hack
9 * Copyright: (c) 2006 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
21 #include "irphase_t.h"
22 #include "iredges_t.h"
24 typedef struct _heights_t heights_t;
37 static void *irn_height_init(phase_t *ph, ir_node *irn, void *data)
39 irn_height_t *h = data ? data : phase_alloc(ph, sizeof(h[0]));
40 memset(h, 0, sizeof(h[0]));
44 static void height_dump_cb(void *data, FILE *f, const ir_node *irn)
46 heights_t *heights = data;
47 irn_height_t *h = phase_get_irn_data(&heights->ph, irn);
50 fprintf(f, "height: %u\n", h->height);
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.
60 static int search(heights_t *h, const ir_node *curr, const ir_node *tgt)
66 /* if the current node is the one we were looking for, we're done. */
70 /* If we are in another block we won't find our target. */
71 if(get_nodes_block(curr) != get_nodes_block(tgt))
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)
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)
84 /* Mark this place as visited. */
85 h_curr->visited = h->visited;
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))
98 * Check, if one node can be reached from another one, according to data dependence.
100 int heights_reachable_in_block(heights_t *h, const ir_node *n, const ir_node *m)
103 irn_height_t *hn = phase_get_irn_data(&h->ph, n);
104 irn_height_t *hm = phase_get_irn_data(&h->ph, m);
106 assert(get_nodes_block(n) == get_nodes_block(m));
107 assert(hn != NULL && hm != NULL);
109 if(hn->height <= hm->height) {
111 res = search(h, n, m);
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.
123 static unsigned compute_height(heights_t *h, ir_node *irn, const ir_node *bl)
125 irn_height_t *ih = phase_get_or_set_irn_data(&h->ph, irn);
127 const ir_edge_t *edge;
129 /* bail out if we already visited that node. */
130 if(ih->visited >= h->visited)
133 ih->visited = h->visited;
136 foreach_out_edge(irn, edge) {
137 ir_node *dep = get_edge_src_irn(edge);
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);
147 foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
148 ir_node *dep = get_edge_src_irn(edge);
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);
161 static unsigned compute_heights_in_block(ir_node *bl, heights_t *h)
164 const ir_edge_t *edge;
168 foreach_out_edge(bl, edge) {
169 ir_node *dep = get_edge_src_irn(edge);
170 int curh = compute_height(h, dep, bl);
172 max_height = MAX(curh, max_height);
175 foreach_out_edge_kind(bl, edge, EDGE_KIND_DEP) {
176 ir_node *dep = get_edge_src_irn(edge);
177 int curh = compute_height(h, dep, bl);
179 max_height = MAX(curh, max_height);
185 static void compute_heights_in_block_walker(ir_node *block, void *data)
188 compute_heights_in_block(block, h);
191 unsigned get_irn_height(heights_t *heights, const ir_node *irn)
193 irn_height_t *h = phase_get_irn_data(&heights->ph, irn);
194 assert(h && "No height information for node");
198 unsigned heights_recompute_block(heights_t *h, ir_node *block)
200 const ir_edge_t *edge;
202 edges_assure(phase_get_irg(&h->ph));
204 /* reset phase data for all nodes in the block */
205 foreach_out_edge(block, edge) {
206 ir_node *irn = get_edge_src_irn(edge);
207 irn_height_t *ih = phase_get_irn_data(&h->ph, irn);
209 irn_height_init(&h->ph, irn, ih);
213 return compute_heights_in_block(block, h);
216 void heights_recompute(heights_t *h)
218 edges_assure(phase_get_irg(&h->ph));
219 phase_reinit_irn_data(&h->ph);
221 irg_block_walk_graph(phase_get_irg(&h->ph), compute_heights_in_block_walker, NULL, h);
224 heights_t *heights_new(ir_graph *irg)
226 heights_t *res = xmalloc(sizeof(res[0]));
227 phase_init(&res->ph, "heights", irg, PHASE_DEFAULT_GROWTH, irn_height_init);
228 res->dump_handle = dump_add_node_info_callback(height_dump_cb, res);
229 heights_recompute(res);
234 void heights_free(heights_t *h)
237 dump_remv_node_info_callback(h->dump_handle);