cfda18683ff2451bd25f8dff21093c139e316c6e
[libfirm] / ir / ana / height.c
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  * @version  $Id$
26  */
27 #include "config.h"
28
29 #include "height.h"
30
31 #include <stdlib.h>
32 #include <stdio.h>
33 #include <stdbool.h>
34
35 #include "list.h"
36 #include "irdump.h"
37 #include "irgwalk.h"
38 #include "irtools.h"
39 #include "irphase_t.h"
40 #include "iredges_t.h"
41
42 struct _heights_t {
43         ir_phase  phase;
44         unsigned  visited;
45         void     *dump_handle;
46 };
47
48 typedef struct {
49         unsigned height;
50         unsigned visited;
51 } irn_height_t;
52
53 static void *irn_height_init(ir_phase *phase, const ir_node *node)
54 {
55         irn_height_t *h = phase_alloc(phase, sizeof(*h));
56         (void) node;
57         memset(h, 0, sizeof(*h));
58         return h;
59 }
60
61 static void *irn_height_reinit(ir_phase *phase, const ir_node *node,
62                                void *old_data)
63 {
64         irn_height_t *h = (irn_height_t*) old_data;
65         (void) node;
66         (void) phase;
67         memset(h, 0, sizeof(*h));
68         return h;
69 }
70
71 static void height_dump_cb(void *data, FILE *f, const ir_node *irn)
72 {
73         heights_t *heights = data;
74         irn_height_t *h    = phase_get_irn_data(&heights->phase, irn);
75
76         if (h)
77                 fprintf(f, "height: %u\n", h->height);
78 }
79
80 /**
81  * Check, if we can reach a target node from a given node inside one basic block.
82  * @param h    The heights object.
83  * @param curr The current node from which we tried to reach the other one.
84  * @param tgt  The node we try to reach.
85  * @return     1, one of tgt can be reached from curr, 0 else.
86  */
87 static bool search(heights_t *h, const ir_node *curr, const ir_node *tgt)
88 {
89         irn_height_t *h_curr;
90         irn_height_t *h_tgt;
91         int i, n;
92
93         /* if the current node is the one we were looking for, we're done. */
94         if (curr == tgt)
95                 return true;
96
97         /* If we are in another block or at a phi we won't find our target. */
98         if (get_nodes_block(curr) != get_nodes_block(tgt))
99                 return false;
100         if (is_Phi(curr))
101                 return false;
102
103         /* Check, if we have already been here. Coming more often won't help :-) */
104         h_curr = phase_get_irn_data(&h->phase, curr);
105         if (h_curr->visited >= h->visited)
106                 return false;
107
108         /* If we are too deep into the DAG we won't find the target either. */
109         h_tgt = phase_get_irn_data(&h->phase, tgt);
110         if (h_curr->height > h_tgt->height)
111                 return false;
112
113         /* Mark this place as visited. */
114         h_curr->visited = h->visited;
115
116         /* Start a search from this node. */
117         for (i = 0, n = get_irn_ins_or_deps(curr); i < n; ++i) {
118                 ir_node *op = get_irn_in_or_dep(curr, i);
119                 if (search(h, op, tgt))
120                         return true;
121         }
122
123         return false;
124 }
125
126 /**
127  * Check, if one node can be reached from another one, according to data dependence.
128  */
129 int heights_reachable_in_block(heights_t *h, const ir_node *n, const ir_node *m)
130 {
131         int res          = 0;
132         irn_height_t *hn = phase_get_irn_data(&h->phase, n);
133         irn_height_t *hm = phase_get_irn_data(&h->phase, m);
134
135         assert(get_nodes_block(n) == get_nodes_block(m));
136         assert(hn != NULL && hm != NULL);
137
138         if (hn->height <= hm->height) {
139                 h->visited++;
140                 res = search(h, n, m);
141         }
142
143         return res;
144 }
145
146 /**
147  * Compute the height of a node in a block.
148  * @param h   The heights object.
149  * @param irn The node.
150  * @param bl  The block.
151  */
152 static unsigned compute_height(heights_t *h, ir_node *irn, const ir_node *bl)
153 {
154         irn_height_t *ih = phase_get_or_set_irn_data(&h->phase, irn);
155
156         const ir_edge_t *edge;
157
158         /* bail out if we already visited that node. */
159         if (ih->visited >= h->visited)
160                 return ih->height;
161
162         ih->visited = h->visited;
163         ih->height  = 0;
164
165         foreach_out_edge(irn, edge) {
166                 ir_node *dep = get_edge_src_irn(edge);
167
168                 if (!is_Block(dep) && !is_Phi(dep) && get_nodes_block(dep) == bl) {
169                         unsigned dep_height = compute_height(h, dep, bl);
170                         ih->height          = MAX(ih->height, dep_height);
171                 }
172
173                 ih->height++;
174         }
175
176         foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
177                 ir_node *dep = get_edge_src_irn(edge);
178
179                 assert(!is_Phi(dep));
180                 if (!is_Block(dep) && get_nodes_block(dep) == bl) {
181                         unsigned dep_height = compute_height(h, dep, bl);
182                         ih->height          = MAX(ih->height, dep_height);
183                 }
184
185                 ih->height++;
186         }
187
188         return ih->height;
189 }
190
191 static unsigned compute_heights_in_block(ir_node *bl, heights_t *h)
192 {
193         int             max_height = -1;
194         const ir_edge_t *edge;
195
196         h->visited++;
197
198         foreach_out_edge(bl, edge) {
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         foreach_out_edge_kind(bl, edge, EDGE_KIND_DEP) {
206                 ir_node *dep = get_edge_src_irn(edge);
207                 int     curh = compute_height(h, dep, bl);
208
209                 max_height = MAX(curh, max_height);
210         }
211
212         return max_height;
213 }
214
215 static void compute_heights_in_block_walker(ir_node *block, void *data)
216 {
217         heights_t *h = data;
218         compute_heights_in_block(block, h);
219 }
220
221 unsigned get_irn_height(heights_t *heights, const ir_node *irn)
222 {
223         irn_height_t *h = phase_get_irn_data(&heights->phase, irn);
224         assert(h && "No height information for node");
225         return h->height;
226 }
227
228 unsigned heights_recompute_block(heights_t *h, ir_node *block)
229 {
230         const ir_edge_t *edge;
231
232         edges_assure(phase_get_irg(&h->phase));
233
234         /* reset phase data for all nodes in the block */
235         foreach_out_edge(block, edge) {
236                 ir_node      *irn = get_edge_src_irn(edge);
237                 irn_height_t *ih  = phase_get_irn_data(&h->phase, irn);
238                 memset(ih, 0, sizeof(*ih));
239         }
240
241         h->visited = 0;
242         return compute_heights_in_block(block, h);
243 }
244
245 void heights_recompute(heights_t *h)
246 {
247         ir_graph *irg = phase_get_irg(&h->phase);
248
249         edges_assure(irg);
250         phase_reinit_irn_data(&h->phase, irn_height_reinit);
251         h->visited = 0;
252         irg_block_walk_graph(irg, compute_heights_in_block_walker, NULL, h);
253 }
254
255 heights_t *heights_new(ir_graph *irg)
256 {
257         heights_t *res = XMALLOC(heights_t);
258         phase_init(&res->phase, irg, irn_height_init);
259         res->dump_handle = dump_add_node_info_callback(height_dump_cb, res);
260         heights_recompute(res);
261
262         return res;
263 }
264
265 void heights_free(heights_t *h)
266 {
267         phase_deinit(&h->phase);
268         dump_remove_node_info_callback(h->dump_handle);
269         xfree(h);
270 }