X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fheight.c;h=482268f28a93fb1a5df278917769f789d2ebe531;hb=c6e8578501b64a525e98b222894918e7a4512708;hp=c256b2501eeb9f70f2d684c53f60e7df5798d017;hpb=b7cac41a298d4a4f051440d15d7397a25275e3ce;p=libfirm diff --git a/ir/ana/height.c b/ir/ana/height.c index c256b2501..482268f28 100644 --- a/ir/ana/height.c +++ b/ir/ana/height.c @@ -1,15 +1,33 @@ /* - * Project: libFIRM - * File name: ir/ana/height.c - * Purpose: Compute heights of nodes inside basic blocks - * Author: Sebastian Hack - * Modified by: - * Created: 19.04.2006 - * CVS-ID: $Id$ - * Copyright: (c) 2006 Universität Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. */ +/** + * @file + * @brief Compute heights of nodes inside basic blocks + * @author Sebastian Hack + * @date 19.04.2006 + * @version $Id$ + */ +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif + #include #include @@ -24,24 +42,22 @@ typedef struct _heights_t heights_t; struct _heights_t { - phase_t ph; + ir_phase ph; unsigned visited; void *dump_handle; - struct list_head sink_head; }; typedef struct { unsigned height; unsigned visited; - unsigned is_sink : 1; - struct list_head sink_list; } irn_height_t; -static void irn_height_init(const phase_t *ph, const ir_node *irn, void *data) +static void *irn_height_init(ir_phase *ph, const ir_node *irn, void *data) { - irn_height_t *h = data; + irn_height_t *h = data ? data : phase_alloc(ph, sizeof(h[0])); + (void)irn; memset(h, 0, sizeof(h[0])); - INIT_LIST_HEAD(&h->sink_list); + return h; } static void height_dump_cb(void *data, FILE *f, const ir_node *irn) @@ -70,9 +86,11 @@ static int search(heights_t *h, const ir_node *curr, const ir_node *tgt) if(curr == tgt) return 1; - /* If we are in another block we won't find our target. */ + /* If we are in another block or at a phi we won't find our target. */ if(get_nodes_block(curr) != get_nodes_block(tgt)) return 0; + if(is_Phi(curr)) + return 0; /* Check, if we have already been here. Coming more often won't help :-) */ h_curr = phase_get_irn_data(&h->ph, curr); @@ -88,8 +106,8 @@ static int search(heights_t *h, const ir_node *curr, const ir_node *tgt) h_curr->visited = h->visited; /* Start a search from this node. */ - for(i = 0, n = get_irn_arity(curr); i < n; ++i) { - ir_node *op = get_irn_n(curr, i); + for(i = 0, n = get_irn_ins_or_deps(curr); i < n; ++i) { + ir_node *op = get_irn_in_or_dep(curr, i); if(search(h, op, tgt)) return 1; } @@ -123,10 +141,9 @@ int heights_reachable_in_block(heights_t *h, const ir_node *n, const ir_node *m) * @param irn The node. * @param bl The block. */ -static unsigned compute_height(heights_t *h, const ir_node *irn, const ir_node *bl) +static unsigned compute_height(heights_t *h, ir_node *irn, const ir_node *bl) { irn_height_t *ih = phase_get_or_set_irn_data(&h->ph, irn); - int is_sink; const ir_edge_t *edge; @@ -137,38 +154,60 @@ static unsigned compute_height(heights_t *h, const ir_node *irn, const ir_node * ih->visited = h->visited; ih->height = 0; - is_sink = 1; - foreach_out_edge(irn, edge) { ir_node *dep = get_edge_src_irn(edge); - if(!is_Block(dep) && get_nodes_block(dep) == bl) { + if(!is_Block(dep) && !is_Phi(dep) && get_nodes_block(dep) == bl) { unsigned dep_height = compute_height(h, dep, bl); ih->height = MAX(ih->height, dep_height); - is_sink = 0; } ih->height++; } - ih->is_sink = is_sink; - if(is_sink) - list_add(&ih->sink_list, &h->sink_head); + foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) { + ir_node *dep = get_edge_src_irn(edge); + + assert(!is_Phi(dep)); + if(!is_Block(dep) && get_nodes_block(dep) == bl) { + unsigned dep_height = compute_height(h, dep, bl); + ih->height = MAX(ih->height, dep_height); + } + + ih->height++; + } return ih->height; } -static void compute_heights_in_block(ir_node *bl, void *data) +static unsigned compute_heights_in_block(ir_node *bl, heights_t *h) { - heights_t *h = data; + int max_height = -1; const ir_edge_t *edge; h->visited++; foreach_out_edge(bl, edge) { ir_node *dep = get_edge_src_irn(edge); - compute_height(h, dep, bl); + int curh = compute_height(h, dep, bl); + + max_height = MAX(curh, max_height); } + + foreach_out_edge_kind(bl, edge, EDGE_KIND_DEP) { + ir_node *dep = get_edge_src_irn(edge); + int curh = compute_height(h, dep, bl); + + max_height = MAX(curh, max_height); + } + + return max_height; +} + +static void compute_heights_in_block_walker(ir_node *block, void *data) +{ + heights_t *h = data; + compute_heights_in_block(block, h); } unsigned get_irn_height(heights_t *heights, const ir_node *irn) @@ -178,19 +217,36 @@ unsigned get_irn_height(heights_t *heights, const ir_node *irn) return h->height; } +unsigned heights_recompute_block(heights_t *h, ir_node *block) +{ + const ir_edge_t *edge; + + edges_assure(phase_get_irg(&h->ph)); + + /* reset phase data for all nodes in the block */ + foreach_out_edge(block, edge) { + ir_node *irn = get_edge_src_irn(edge); + irn_height_t *ih = phase_get_irn_data(&h->ph, irn); + + irn_height_init(&h->ph, irn, ih); + } + + h->visited = 0; + return compute_heights_in_block(block, h); +} + void heights_recompute(heights_t *h) { edges_assure(phase_get_irg(&h->ph)); phase_reinit_irn_data(&h->ph); h->visited = 0; - INIT_LIST_HEAD(&h->sink_head); - irg_block_walk_graph(phase_get_irg(&h->ph), compute_heights_in_block, NULL, h); + irg_block_walk_graph(phase_get_irg(&h->ph), compute_heights_in_block_walker, NULL, h); } heights_t *heights_new(ir_graph *irg) { - heights_t *res = xmalloc(sizeof(res[0])); - phase_init(&res->ph, "heights", irg, sizeof(irn_height_t), PHASE_DEFAULT_GROWTH, irn_height_init); + heights_t *res = XMALLOC(heights_t); + phase_init(&res->ph, "heights", irg, PHASE_DEFAULT_GROWTH, irn_height_init, NULL); res->dump_handle = dump_add_node_info_callback(height_dump_cb, res); heights_recompute(res);