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