2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Compute heights of nodes inside basic blocks
23 * @author Sebastian Hack
38 #include "irphase_t.h"
39 #include "iredges_t.h"
52 static void *irn_height_init(ir_phase *ph, const ir_node *irn, void *data)
54 irn_height_t *h = data ? data : phase_alloc(ph, sizeof(h[0]));
56 memset(h, 0, sizeof(h[0]));
60 static void height_dump_cb(void *data, FILE *f, const ir_node *irn)
62 heights_t *heights = data;
63 irn_height_t *h = phase_get_irn_data(&heights->ph, irn);
66 fprintf(f, "height: %u\n", h->height);
70 * Check, if we can reach a target node from a given node inside one basic block.
71 * @param h The heights object.
72 * @param curr The current node from which we tried to reach the other one.
73 * @param tgt The node we try to reach.
74 * @return 1, one of tgt can be reached from curr, 0 else.
76 static int search(heights_t *h, const ir_node *curr, const ir_node *tgt)
82 /* if the current node is the one we were looking for, we're done. */
86 /* If we are in another block or at a phi we won't find our target. */
87 if (get_nodes_block(curr) != get_nodes_block(tgt))
92 /* Check, if we have already been here. Coming more often won't help :-) */
93 h_curr = phase_get_irn_data(&h->ph, curr);
94 if (h_curr->visited >= h->visited)
97 /* If we are too deep into the DAG we won't find the target either. */
98 h_tgt = phase_get_irn_data(&h->ph, tgt);
99 if (h_curr->height > h_tgt->height)
102 /* Mark this place as visited. */
103 h_curr->visited = h->visited;
105 /* Start a search from this node. */
106 for (i = 0, n = get_irn_ins_or_deps(curr); i < n; ++i) {
107 ir_node *op = get_irn_in_or_dep(curr, i);
108 if (search(h, op, tgt))
116 * Check, if one node can be reached from another one, according to data dependence.
118 int heights_reachable_in_block(heights_t *h, const ir_node *n, const ir_node *m)
121 irn_height_t *hn = phase_get_irn_data(&h->ph, n);
122 irn_height_t *hm = phase_get_irn_data(&h->ph, m);
124 assert(get_nodes_block(n) == get_nodes_block(m));
125 assert(hn != NULL && hm != NULL);
127 if (hn->height <= hm->height) {
129 res = search(h, n, m);
136 * Compute the height of a node in a block.
137 * @param h The heights object.
138 * @param irn The node.
139 * @param bl The block.
141 static unsigned compute_height(heights_t *h, ir_node *irn, const ir_node *bl)
143 irn_height_t *ih = phase_get_or_set_irn_data(&h->ph, irn);
145 const ir_edge_t *edge;
147 /* bail out if we already visited that node. */
148 if (ih->visited >= h->visited)
151 ih->visited = h->visited;
154 foreach_out_edge(irn, edge) {
155 ir_node *dep = get_edge_src_irn(edge);
157 if (!is_Block(dep) && !is_Phi(dep) && get_nodes_block(dep) == bl) {
158 unsigned dep_height = compute_height(h, dep, bl);
159 ih->height = MAX(ih->height, dep_height);
165 foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
166 ir_node *dep = get_edge_src_irn(edge);
168 assert(!is_Phi(dep));
169 if (!is_Block(dep) && get_nodes_block(dep) == bl) {
170 unsigned dep_height = compute_height(h, dep, bl);
171 ih->height = MAX(ih->height, dep_height);
180 static unsigned compute_heights_in_block(ir_node *bl, heights_t *h)
183 const ir_edge_t *edge;
187 foreach_out_edge(bl, edge) {
188 ir_node *dep = get_edge_src_irn(edge);
189 int curh = compute_height(h, dep, bl);
191 max_height = MAX(curh, max_height);
194 foreach_out_edge_kind(bl, edge, EDGE_KIND_DEP) {
195 ir_node *dep = get_edge_src_irn(edge);
196 int curh = compute_height(h, dep, bl);
198 max_height = MAX(curh, max_height);
204 static void compute_heights_in_block_walker(ir_node *block, void *data)
207 compute_heights_in_block(block, h);
210 unsigned get_irn_height(heights_t *heights, const ir_node *irn)
212 irn_height_t *h = phase_get_irn_data(&heights->ph, irn);
213 assert(h && "No height information for node");
217 unsigned heights_recompute_block(heights_t *h, ir_node *block)
219 const ir_edge_t *edge;
221 edges_assure(phase_get_irg(&h->ph));
223 /* reset phase data for all nodes in the block */
224 foreach_out_edge(block, edge) {
225 ir_node *irn = get_edge_src_irn(edge);
226 irn_height_t *ih = phase_get_irn_data(&h->ph, irn);
228 irn_height_init(&h->ph, irn, ih);
232 return compute_heights_in_block(block, h);
235 void heights_recompute(heights_t *h)
237 edges_assure(phase_get_irg(&h->ph));
238 phase_reinit_irn_data(&h->ph);
240 irg_block_walk_graph(phase_get_irg(&h->ph), compute_heights_in_block_walker, NULL, h);
243 heights_t *heights_new(ir_graph *irg)
245 heights_t *res = XMALLOC(heights_t);
246 phase_init(&res->ph, irg, irn_height_init);
247 res->dump_handle = dump_add_node_info_callback(height_dump_cb, res);
248 heights_recompute(res);
253 void heights_free(heights_t *h)
255 phase_deinit(&h->ph);
256 dump_remv_node_info_callback(h->dump_handle);