From 7b8d08a1abb6b63a21502857206fb1ab32eebd26 Mon Sep 17 00:00:00 2001 From: Christoph Mallon Date: Wed, 3 May 2006 08:27:11 +0000 Subject: [PATCH] Add control dependency analysis [r7684] --- ir/ana/Makefile.in | 6 +- ir/ana/cdep.c | 163 +++++++++++++++++++++++++++++++++++++++++++++ ir/ana/cdep.h | 22 ++++++ 3 files changed, 189 insertions(+), 2 deletions(-) create mode 100644 ir/ana/cdep.c create mode 100644 ir/ana/cdep.h diff --git a/ir/ana/Makefile.in b/ir/ana/Makefile.in index 7ee19c8c2..e154d2d3d 100644 --- a/ir/ana/Makefile.in +++ b/ir/ana/Makefile.in @@ -18,7 +18,8 @@ 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 height.h + analyze_irg_args.h height.h \ + cdep.h SOURCES = $(INSTALL_HEADERS) @@ -28,7 +29,8 @@ 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 height.c + compute_loop_info.c compute_loop_info.h height.c \ + cdep.c include $(topdir)/MakeRules diff --git a/ir/ana/cdep.c b/ir/ana/cdep.c new file mode 100644 index 000000000..10ecbf4a1 --- /dev/null +++ b/ir/ana/cdep.c @@ -0,0 +1,163 @@ +#include +#include +#include "irdom.h" +#include "irgraph.h" +#include "irgwalk.h" +#include "irnode.h" +#include "pmap.h" +#include "cdep.h" +#include "irprintf.h" + +typedef unsigned int uint; + +static pmap* cdep_map; + +cdep* find_cdep(const ir_node* block) +{ + return pmap_get(cdep_map, (void*)block); +} + + +static void add_cdep(ir_node* node, ir_node* dep_on) +{ + cdep* dep = find_cdep(node); +#if 0 + ir_fprintf(stderr, "Adding cdep of %+F on %+F\n", node, dep_on); +#endif + + if (dep == NULL) { + cdep* newdep = malloc(sizeof(*newdep)); + + newdep->node = dep_on; + newdep->next = NULL; + pmap_insert(cdep_map, node, newdep); + } else { + cdep* newdep; + + for (;;) { + if (dep->node == dep_on) return; + if (dep->next == NULL) break; + dep = dep->next; + } + newdep = malloc(sizeof(*newdep)); + newdep->node = dep_on; + newdep->next = NULL; + dep->next = newdep; + } +} + + +static void cdep_pre(ir_node* node, void* env) +{ + uint n; + uint i; + + /* special case: + * start and end block have no control depency + */ + if (node == get_irg_start_block(get_irn_irg(node))) return; + if (node == get_irg_end_block(get_irn_irg(node))) return; + + n = get_Block_n_cfgpreds(node); + for (i = 0; i < n; i++) { + ir_node* pred = get_Block_cfgpred_block(node, i); + ir_node* pdom; + ir_node* dependee; + + if (is_Bad(pred)) continue; + + pdom = get_Block_ipostdom(pred); + for (dependee = node; dependee != pdom; dependee = get_Block_ipostdom(dependee)) { + assert(!is_Bad(pdom)); + add_cdep(dependee, pred); + } + } +} + + +#include "irdump.h" + + +static int cdep_edge_hook(FILE* F, ir_node* block) +{ +#if 0 + ir_node* pdom; +#endif + cdep* cd; + +#if 0 + pdom = get_Block_ipostdom(block); + if (pdom != NULL) { + fprintf( + F, + "edge:{sourcename:\"n%ld\" targetname:\"n%ld\" color:gold}\n", + get_irn_node_nr(pdom), get_irn_node_nr(block) + ); + } +#endif + + for (cd = find_cdep(block); cd != NULL; cd = cd->next) { + fprintf( + F, + "edge:{sourcename:\"n%ld\" targetname:\"n%ld\" " + "linestyle:dashed color:gold}\n", + get_irn_node_nr(block), get_irn_node_nr(cd->node) + ); + } + + return 0; +} + + +void compute_cdep(ir_graph* irg) +{ + cdep_map = pmap_create(); + + compute_postdoms(irg); + set_Block_ipostdom(get_irg_start_block(irg), get_irg_end_block(irg)); + + irg_block_walk_graph(irg, cdep_pre, NULL, NULL); + +#if 1 + set_dump_block_edge_hook(cdep_edge_hook); + dump_ir_block_graph(irg, "_cdep"); + set_dump_block_edge_hook(NULL); +#endif + + free_postdom(irg); +} + + +void free_cdep(ir_graph* irg) +{ + // TODO atm leaking more memory than a small memory leaking animal +} + + +int is_iterated_cdep_on(ir_node* dependee, ir_node* candidate) +{ + const cdep* dep; + + while ((dep = find_cdep(dependee)) != NULL) { + if (dep->next != NULL) return 0; + if (dep->node == candidate) return 1; + dependee = dep->node; + } + return 0; +} + + +ir_node* get_unique_cdep(const ir_node* block) +{ + cdep* cdep = find_cdep(block); + + return cdep != NULL && cdep->next == NULL ? cdep->node : NULL; +} + + +int has_multiple_cdep(const ir_node* block) +{ + cdep* cdep = find_cdep(block); + + return cdep != NULL && cdep->next != NULL; +} diff --git a/ir/ana/cdep.h b/ir/ana/cdep.h new file mode 100644 index 000000000..7c8f16164 --- /dev/null +++ b/ir/ana/cdep.h @@ -0,0 +1,22 @@ +#ifndef CDEP_H +#define CDEP_H + +#include "irnode.h" + +typedef struct cdep cdep; +struct cdep { + ir_node* node; + cdep* next; +}; + +void compute_cdep(ir_graph*); +void free_cdep(ir_graph*); + +cdep* find_cdep(const ir_node* block); + +int is_iterated_cdep_on(ir_node* dependee, ir_node* candidate); + +ir_node* get_unique_cdep(const ir_node* block); +int has_multiple_cdep(const ir_node* block); + +#endif -- 2.20.1