From 715c956ff0b7ce56bfb85ebc113f2ad8abc6a3aa Mon Sep 17 00:00:00 2001 From: Sebastian Hack Date: Wed, 19 Apr 2006 15:44:51 +0000 Subject: [PATCH] Added height computation [r7644] --- ir/ana/Makefile.in | 4 +- ir/ana/height.c | 194 +++++++++++++++++++++++++++++++++++++++++++++ ir/ana/height.h | 57 +++++++++++++ 3 files changed, 253 insertions(+), 2 deletions(-) create mode 100644 ir/ana/height.c create mode 100644 ir/ana/height.h diff --git a/ir/ana/Makefile.in b/ir/ana/Makefile.in index ff52154e9..7ee19c8c2 100644 --- a/ir/ana/Makefile.in +++ b/ir/ana/Makefile.in @@ -18,7 +18,7 @@ subdir := ir/ana INSTALL_HEADERS = irouts.h trouts.h irdom.h cgana.h irloop.h irtypeinfo.h irsimpletype.h \ callgraph.h rta.h interval_analysis.h \ field_temperature.h execution_frequency.h irextbb.h irconsconfirm.h \ - analyze_irg_args.h + analyze_irg_args.h height.h SOURCES = $(INSTALL_HEADERS) @@ -28,7 +28,7 @@ SOURCES += Makefile.in \ irtypeinfo.c irsimpletype.c interval_analysis.c \ callgraph.c field_temperature.c execution_frequency.c phiclass.c \ irextbb.c irextbb_t.h irconsconfirm.c analyze_irg_args.c \ - compute_loop_info.c compute_loop_info.h + compute_loop_info.c compute_loop_info.h height.c include $(topdir)/MakeRules diff --git a/ir/ana/height.c b/ir/ana/height.c new file mode 100644 index 000000000..8a060efe4 --- /dev/null +++ b/ir/ana/height.c @@ -0,0 +1,194 @@ + +#include +#include + +#include "list.h" + +#include "irdump.h" +#include "irgwalk.h" +#include "irtools.h" +#include "irphase_t.h" +#include "iredges_t.h" + +typedef struct _heights_t heights_t; + +struct _heights_t { + phase_t 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) +{ + irn_height_t *h = data; + memset(h, 0, sizeof(h[0])); + INIT_LIST_HEAD(&h->sink_list); +} + +static void height_dump_cb(void *data, FILE *f, const ir_node *irn) +{ + heights_t *heights = data; + irn_height_t *h = phase_get_irn_data(&heights->ph, irn); + + if(h) + fprintf(f, "height: %u\n", h->height); +} + +/** + * Check, if we can reach a target node from a given node inside one basic block. + * @param h The heights object. + * @param curr The current node from which we tried to reach the other one. + * @param tgt The node we try to reach. + * @return 1, one of tgt can be reached from curr, 0 else. + */ +static int search(heights_t *h, const ir_node *curr, const ir_node *tgt) +{ + irn_height_t *h_curr; + irn_height_t *h_tgt; + int i, n; + + /* if the current node is the one we were looking for, we're done. */ + if(curr == tgt) + return 1; + + /* If we are in another block we won't find our target. */ + if(get_nodes_block(curr) != get_nodes_block(tgt)) + return 0; + + /* Check, if we have already been here. Coming more often won't help :-) */ + h_curr = phase_get_irn_data(&h->ph, curr); + if(h_curr->visited >= h->visited) + return 0; + + /* If we are too deep into the DAG we won't find the target either. */ + h_tgt = phase_get_irn_data(&h->ph, tgt); + if(h_curr->height > h_tgt->height) + return 0; + + /* Mark this place as visited. */ + 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); + if(search(h, op, tgt)) + return 1; + } + + return 0; +} + +/** + * Check, if one node can be reached from another one, according to data dependence. + */ +int heights_reachable_in_block(heights_t *h, const ir_node *n, const ir_node *m) +{ + int res = 0; + irn_height_t *hn = phase_get_irn_data(&h->ph, n); + irn_height_t *hm = phase_get_irn_data(&h->ph, m); + + assert(get_nodes_block(n) == get_nodes_block(m)); + assert(hn != NULL && hm != NULL); + + if(hn->height <= hm->height) { + h->visited++; + res = search(h, n, m); + } + + return res; +} + +/** + * Compute the height of a node in a block. + * @param h The heights object. + * @param irn The node. + * @param bl The block. + */ +static unsigned compute_height(heights_t *h, const 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; + + /* bail out if we already visited that node. */ + if(ih->visited >= h->visited) + return ih->height; + + 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) { + 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); + + return ih->height; +} + +static void compute_heights_in_block(ir_node *bl, void *data) +{ + heights_t *h = data; + 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); + } +} + +unsigned get_irn_height(heights_t *heights, const ir_node *irn) +{ + irn_height_t *h = phase_get_irn_data(&heights->ph, irn); + assert(h && "No height information for node"); + return h->height; +} + +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); +} + +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); + res->dump_handle = dump_add_node_info_callback(height_dump_cb, res); + heights_recompute(res); + + return res; +} + +void heights_free(heights_t *h) +{ + phase_free(&h->ph); + dump_remv_node_info_callback(h->dump_handle); + xfree(h); +} diff --git a/ir/ana/height.h b/ir/ana/height.h new file mode 100644 index 000000000..c85b81917 --- /dev/null +++ b/ir/ana/height.h @@ -0,0 +1,57 @@ +/* + * Project: libFIRM + * File name: ir/ana/height.h + * 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. + */ + +#ifndef _FIRM_HEIGHTS_H +#define _FIRM_HEIGHTS_H + +typedef struct _heights_t heights_t; + +/** + * Get the height of a node inside a basic block. + * The height of the node is the maximal number of edges between a sink node in that block and the node itself (plus 1). + * @param h The heights object. + * @param irn The node. + * @return The height of the node. + */ +unsigned get_irn_height(heights_t *h, const ir_node *irn); + +/** + * Check, if a certain node is reachable according to data dependence edges from another node. + * @param h The heights object. + * @param n The first node. + * @param m The other node. + * @return 1, if n is data dependent on m, 0 if not. + */ +int heights_reachable_in_block(heights_t *h, const ir_node *n, const ir_node *m); + +/** + * Recompute the height information. + * This can be used to recompute the height information if the graph has changed since the last computation. + * @param h The heights object. + */ +void heights_recompute(heights_t *h); + +/** + * Make a new heights object. + * This also computes the heights for each block in the graph. + * @param irg The graph. + */ +heights_t *heights_new(ir_graph *irg); + +/** + * Free a heights object. + * @param h The heights object. + */ +void heights_free(heights_t *h); + + +#endif /* _FIRM_HEIGHTS_H */ -- 2.20.1