From 5ff40d04f7617b3ea10b11ef9b46dbdb7d02249c Mon Sep 17 00:00:00 2001 From: Florian Liekweg Date: Tue, 16 Apr 2002 14:03:22 +0000 Subject: [PATCH] Added Exception marking support --flo [r352] --- Makefile.in | 2 +- configure.in | 2 +- ir/ana/Makefile.in | 2 +- ir/ana/irdom.c | 2 +- ir/common/Makefile.in | 2 +- ir/common/bool.h | 5 + ir/ir/Makefile.in | 2 +- ir/ir/ircons.c | 4 +- ir/ir/irgwalk.c | 14 +- ir/st/Makefile.in | 30 +++ ir/st/bs.h | 30 +++ ir/st/exc.c | 230 ++++++++++++++++++ ir/st/exc.h | 38 +++ ir/st/st.c | 528 ++++++++++++++++++++++++++++++++++++++++++ ir/st/st.h | 73 ++++++ 15 files changed, 950 insertions(+), 14 deletions(-) create mode 100644 ir/st/Makefile.in create mode 100644 ir/st/bs.h create mode 100644 ir/st/exc.c create mode 100644 ir/st/exc.h create mode 100644 ir/st/st.c create mode 100644 ir/st/st.h diff --git a/Makefile.in b/Makefile.in index 5d4927201..7efdfbc12 100644 --- a/Makefile.in +++ b/Makefile.in @@ -21,7 +21,7 @@ exec_prefix := @exec_prefix@ bindir = $(exec_prefix)/bin datadir = $(prefix)/lib -subdirs := ir ir/adt ir/debug ir/tv ir/common ir/ident ir/ir ir/tr ir/ana +subdirs := ir ir/adt ir/debug ir/tv ir/common ir/ident ir/ir ir/tr ir/ana ir/st SOURCES := Makefile.in MakeRules.in MakeTargets\ aclocal.m4 config.h.in\ diff --git a/configure.in b/configure.in index fb153e818..0ed63b23d 100644 --- a/configure.in +++ b/configure.in @@ -12,7 +12,7 @@ AC_INIT(ir/ir/ircons.c) dnl if other files should be generated just add them to ac_output_files ac_output_file="Makefile MakeRules ir/Makefile ir/adt/Makefile ir/debug/Makefile \ ir/tv/Makefile ir/common/Makefile ir/ident/Makefile ir/ir/Makefile \ - ir/ana/Makefile ir/tr/Makefile testprograms/Makefile" + ir/ana/Makefile ir/tr/Makefile ir/st/Makefile testprograms/Makefile" dnl generate the config header file AC_CONFIG_HEADER(config.h) diff --git a/ir/ana/Makefile.in b/ir/ana/Makefile.in index 89800f918..6a8f0afc4 100644 --- a/ir/ana/Makefile.in +++ b/ir/ana/Makefile.in @@ -22,7 +22,7 @@ include $(topdir)/MakeRules CPPFLAGS += -I$(top_srcdir)/ir/adt -I$(top_srcdir)/ir/ir -I$(top_srcdir)/ir/common \ -I$(top_srcdir)/ir/ident -I$(top_srcdir)/ir/tr -I$(top_srcdir)/ir/tv \ - -I$(top_srcdir)/ir/debug -I$(top_srcdir)/ir/ana + -I$(top_srcdir)/ir/debug -I$(top_srcdir)/ir/ana -I$(top_srcdir)/ir/st include $(top_srcdir)/MakeTargets diff --git a/ir/ana/irdom.c b/ir/ana/irdom.c index 46dd54721..6a7b94fa8 100644 --- a/ir/ana/irdom.c +++ b/ir/ana/irdom.c @@ -262,7 +262,7 @@ void compute_doms(ir_graph *irg) { } /* clean up */ - free(tdi_list); + // free(tdi_list); current_ir_graph = rem; } diff --git a/ir/common/Makefile.in b/ir/common/Makefile.in index 687e54657..4a194accc 100644 --- a/ir/common/Makefile.in +++ b/ir/common/Makefile.in @@ -21,7 +21,7 @@ include $(topdir)/MakeRules CPPFLAGS += -I$(top_srcdir)/ir/common -I$(top_srcdir)/ir/ident -I$(top_srcdir)/ir/tr \ -I$(top_srcdir)/ir/adt -I$(top_srcdir)/ir/tv -I$(top_srcdir)/ir/ir \ - -I$(top_srcdir)/ir/ana + -I$(top_srcdir)/ir/ana -I$(top_srcdir)/ir/st include $(top_srcdir)/MakeTargets diff --git a/ir/common/bool.h b/ir/common/bool.h index b18a5913b..6939b66b8 100644 --- a/ir/common/bool.h +++ b/ir/common/bool.h @@ -18,4 +18,9 @@ typedef unsigned char bool; # endif /* __cplusplus */ +# ifndef TRUE +# define TRUE 1 +# define FALSE 0 +# endif /* ndef TRUE */ + # endif /* _BOOL_H_ */ diff --git a/ir/ir/Makefile.in b/ir/ir/Makefile.in index 29c035323..d629f7e2e 100644 --- a/ir/ir/Makefile.in +++ b/ir/ir/Makefile.in @@ -27,7 +27,7 @@ include $(topdir)/MakeRules CPPFLAGS += -I$(top_srcdir)/ir/adt -I$(top_srcdir)/ir/ir -I$(top_srcdir)/ir/common \ -I$(top_srcdir)/ir/ident -I$(top_srcdir)/ir/tr -I$(top_srcdir)/ir/tv \ - -I$(top_srcdir)/ir/debug -I$(top_srcdir)/ir/ana + -I$(top_srcdir)/ir/debug -I$(top_srcdir)/ir/ana -I$(top_srcdir)/ir/st include $(top_srcdir)/MakeTargets diff --git a/ir/ir/ircons.c b/ir/ir/ircons.c index 014d8b0de..b22b5ffe7 100644 --- a/ir/ir/ircons.c +++ b/ir/ir/ircons.c @@ -55,7 +55,7 @@ new_r_Block (ir_graph *irg, int arity, ir_node **in) set_Block_matured(res, 1); set_Block_block_visited(res, 0); - // res->attr.block.exc = exc_invalid; + res->attr.block.exc = exc_invalid; irn_vrfy (res); return res; @@ -1756,7 +1756,7 @@ ir_node *new_immBlock (void) { res = new_ir_node (current_ir_graph, NULL, op_Block, mode_R, -1, NULL); current_ir_graph->current_block = res; res->attr.block.matured = 0; - // res->attr.block.exc = exc_invalid; + res->attr.block.exc = exc_invalid; set_Block_block_visited(res, 0); /* Create and initialize array for Phi-node construction. */ diff --git a/ir/ir/irgwalk.c b/ir/ir/irgwalk.c index 1c5c60bf1..364e6e63c 100644 --- a/ir/ir/irgwalk.c +++ b/ir/ir/irgwalk.c @@ -102,7 +102,7 @@ ir_node *get_cf_op(ir_node *n) { } void irg_block_walk_2(ir_node *node, void (pre)(ir_node*, void*), - void (post)(ir_node*, void*), void *env) + void (post)(ir_node*, void*), void *env) { int i; @@ -121,15 +121,17 @@ void irg_block_walk_2(ir_node *node, void (pre)(ir_node*, void*), /* GL: I'm not sure whether this assert must go through. There could be Id chains?? Tuple/Proj .... */ - assert(is_cfop(pred) || is_fragile_op(pred) || - (get_irn_op(pred) == op_Bad)); + assert(is_cfop(pred) + || is_fragile_op(pred) + || (get_irn_op(pred) == op_Bad)); + pred = get_nodes_Block(pred); if(get_irn_opcode(pred) == iro_Block) { - /* recursion */ - irg_block_walk_2(pred, pre, post, env); + /* recursion */ + irg_block_walk_2(pred, pre, post, env); } else { - assert(get_irn_opcode(pred) == iro_Bad); + assert(get_irn_opcode(pred) == iro_Bad); } } diff --git a/ir/st/Makefile.in b/ir/st/Makefile.in new file mode 100644 index 000000000..e4fe0ea49 --- /dev/null +++ b/ir/st/Makefile.in @@ -0,0 +1,30 @@ +# Hey Emacs, this is a -*- makefile -*- +# +# libFIRM Project +# +# $Id$ +# + +top_srcdir := @top_srcdir@ +srcdir = @srcdir@ +topdir = ../.. +subdir := ir/tr + +INSTALL_HEADERS = st.h + +SOURCES = $(INSTALL_HEADERS) + +SOURCES += Makefile.in \ + st.c \ + st.h + + +include $(topdir)/MakeRules + +CPPFLAGS += -I$(top_srcdir)/ir/common -I$(top_srcdir)/ir/tr \ + -I$(top_srcdir)/ir/ident -I$(top_srcdir)/ir/adt \ + -I$(top_srcdir)/ir/ir -I$(top_srcdir)/ir/tv + +include $(top_srcdir)/MakeTargets + +all: subdir.o diff --git a/ir/st/bs.h b/ir/st/bs.h new file mode 100644 index 000000000..12ff85db7 --- /dev/null +++ b/ir/st/bs.h @@ -0,0 +1,30 @@ +/* Copyright (c) 2002 by Universität Karlsruhe (TH). All Rights Reserved */ + +/*** + NAME + bs + PURPOSE + provide bs_t + NOTES + not quite complete + HISTORY + liekweg - Feb 27, 2002: Created. + CVS: + $Id$ +***/ + +# ifndef _BS_H_ +# define _BS_H_ + +typedef long int bs_t; + +# define bs_set(bs, i) (bs) |= (0x00000001 << i) +# define bs_get(bs, i) (bs) & (0x00000001 << i) + +# define bs_and(bsa, bsb) (bsa) &= (bsb) +# define bs_or(bsa, bsb) (bsa) |= (bsb) +# define bs_xor(bsa, bsb) (bsa) ^= (bsb) + +# define bs_zro(bs) (0x00000000 != bs) + +# endif /* ndef _BS_H_ */ diff --git a/ir/st/exc.c b/ir/st/exc.c new file mode 100644 index 000000000..4dc924b1f --- /dev/null +++ b/ir/st/exc.c @@ -0,0 +1,230 @@ +/* Copyright (c) 2002 by Universität Karlsruhe (TH). All Rights Reserved */ +// +// Time-stamp: <02/03/04 17:24:07 liekweg> +// + +/*** + NAME + exc + PURPOSE + Helper functions for exceptions + NOTES + not quite complete + HISTORY + liekweg - Mar 4, 2002: Created. + CVS: + $Id$ +***/ + +# include "exc.h" +# include "st.h" +# include "irop.h" +# include "irouts.h" + +# include + +/* + Return true iff (block b is a handler entry AND a dominates b) OR + (b has a CFG successor that is both a handler entry AND is dominated + by a) +*/ +static bool has_handler (ir_graph *graph, ir_node *b, ir_node *a) +{ + int i = 0; + int n = get_irn_n_outs (b); + ir_node *succ = 0; + + assert (0 && "Wrongly implemented"); + // must check for _immediate_ dominance !!! + + if (is_handler_entry (graph, b) && dominates (graph, a, b)) + return (true); + + for (i = 0; i < n; i ++) + { + succ = get_irn_out (b, i); + + if (has_handler (graph, succ, a)) + return (true); + } + + return (false); +} + +/* + Return true iff the given node represents an exception jump +*/ +static bool is_exc_jmp (ir_node *node) +{ + ir_op *op = get_irn_op (node); + + // Proj_X (Load), Proj_X (Sto), Proj_X (Div_Int), + // Proj_X (Raise), Proj_X (Call), Proj_X (Alloc) + if (op == op_Proj) + { + op = get_irn_op (get_Proj_pred (node)); + + // ToDo: Check for proper Proj attr?!? + if ((op == op_Load) || (op == op_Store) || + (op == op_Div ) || (op == op_Raise) || + (op == op_Call) || (op == op_Alloc)) + return (true); + } + else + { + return (false); + } +} + +/* +Return true iff the given node represents a normal cfg jump +*/ +static bool is_cfg_jmp (ir_node *node) +{ + ir_op *op = get_irn_op (node); + + if (op == op_Proj) + { + op = get_irn_op (get_Proj_pred (node)); + + // Proj_X (Proj_Cmp (Cond)) + if (op_Proj == op) + return (true); /* check for op == op_Cmp and op == op_Cond */ + } + + return (false); +} + +/* + Return true iff a new exception region must be left upon entry of this block. + + If all CFG preds of this block are exception jumps, then we must + return true. +*/ +bool is_handler_entry (ir_graph *graph, ir_node *block) +{ + bool is_entry = true; + int i = 0; + int n = get_irn_arity (block); + ir_node *node = 0; + ir_op* op = op_Bad; + + if (exc_invalid == get_Block_exc (block)) + { + for (i = 0; (i < n) && is_entry; i ++) + if (is_exc_jmp (get_irn_n (block, i))) + continue; + else + is_entry = false; + + if (true == is_entry) + set_Block_exc (block, exc_entry); + } + + return (exc_entry == get_Block_exc (block)); +} + +/* + Return true iff a new exception region must be started upon entry of this block. + + If this block immediately dominates a handler entry, we must return true. +*/ +bool is_region_entry (ir_graph *graph, ir_node *block) +{ + assert (0 && "Not implemented"); + + if (exc_invalid == get_Block_exc (block)) + { + int i = 0; + int n = get_irn_n_outs (block); + ir_node *succ = 0; + + bool no_handler = true; + + for (i = 0; (i < n) && no_handler; i ++) + { + succ = get_irn_out (block, i); + + if (has_handler (graph, succ, block)) + no_handler = false; + } + + if (false == no_handler) + set_Block_exc (block, exc_region); + } + + return (exc_region == get_Block_exc (block)); + + return (TRUE); +} + +/* + Return true iff this block is part of handler code. + + If this block is dominated by a block for which {@link + is_handler_entry} is true, then this block is part of the handler. +*/ +bool is_handler_block (ir_graph *graph, ir_node *block) +{ + assert (0 && "Not implemented"); + + if (exc_invalid == get_Block_exc (block)) + { + bool no_handler = true; + dom_env_t *env = get_dom_env (graph, block); + int block_index = env->index_a; + bs_t block_mask = 0x00000001 << block_index; + int n_blocks = env->dt->n_blocks; + int i = 0; + + for (i = 0; (i < n_blocks) && no_handler; i ++) + if (0 != (env->dt->masks [i] & block_mask)) /* if dominator */ + if (is_handler_entry (graph, env->dt->blocks [i])) /* is handler entry */ + no_handler = false; + + delete_dom_env (env); + + if (false == no_handler) + set_Block_exc (block, exc_handler); + } + + return (exc_handler == get_Block_exc (block)); +} + +/* + Return true iff a new exception region must be left upon exit of the + non-exception blocks among the CFG predecessors of this block. + + If this block has CFG predecessors that are partly handler blocks and + partly normal blocks, then we must return true. +*/ +bool is_cont_entry (ir_graph *graph, ir_node *block) +{ + assert (0 && "Not implemented"); + + if (exc_invalid == get_Block_exc (block)) + { + bool has_exc = false; /* wether we have exception cfg predecessors */ + bool has_cfg = false; /* wether we have normal cfg predecessors */ + + int i = 0; + int n = get_irn_arity (block); + + ir_node *pred = 0; + + for (i = 0; (i < n) && (!has_exc && !has_cfg); i ++) + { + pred = get_irn_n (block, i); + + if (is_exc_jmp (pred)) + has_exc = true; + else if (is_cfg_jmp (pred)) + has_cfg = true; + } + + if (has_cfg && has_exc) + set_Block_exc (block, exc_cont); + } + + return (exc_cont == get_Block_exc (block)); +} diff --git a/ir/st/exc.h b/ir/st/exc.h new file mode 100644 index 000000000..96957703f --- /dev/null +++ b/ir/st/exc.h @@ -0,0 +1,38 @@ +/* Copyright (c) 2002 by Universität Karlsruhe (TH). All Rights Reserved */ +// +// Time-stamp: <02/03/22 17:03:05 liekweg> +// + +/*** + NAME + exc + PURPOSE + Helper functions for exceptions + NOTES + not quite complete + HISTORY + liekweg - Mar 4, 2002: Created. + CVS: + $Id$ +***/ + +# include "irnode.h" + +# ifndef _EXC_H_ +# define _EXC_H_ + +typedef enum { + exc_invalid, /* not yet computed */ + exc_normal, /* normal CF */ + exc_entry, /* handler entry */ + exc_handler, /* handler block */ + exc_region, /* region entry */ + exc_cont /* cont block */ +} exc_t; + +bool is_handler_entry (ir_graph*, ir_node*); +bool is_region_entry (ir_graph*, ir_node*); +bool is_handler_block (ir_graph*, ir_node*); +bool is_cont_entry (ir_graph*, ir_node*); + +# endif /* def _EXC_H_ */ diff --git a/ir/st/st.c b/ir/st/st.c new file mode 100644 index 000000000..680ebc90f --- /dev/null +++ b/ir/st/st.c @@ -0,0 +1,528 @@ +/* Copyright (c) 2002 by Universität Karlsruhe (TH). All Rights Reserved */ +// +// Time-stamp: <02/03/04 16:57:32 liekweg> +// + +/*** + NAME + st.h + PURPOSE + provide some auxilliary structures for firm graphs. + NOTES + not quite complete + HISTORY + liekweg - Feb 26, 2002: Created. + CVS: + $Id$ +***/ + +# include "st.h" + +# include "irgwalk.h" + +# include +# ifdef DEBUG_libfirm +# endif /* def DEBUG_libfirm */ +# include + +/* init globals: */ +static dtree_t *trees = 0; +static dtree_t *last = 0; + +// -------------------------------------------------------------------- +// Helper Functions +// -------------------------------------------------------------------- +/* + Helper function for get_n_blocks +*/ +static void count_block (ir_node *block, void *env) +{ + int *n = (int*) env; + +# ifdef DEBUG_libfirm + assert (block && "no block"); + assert (env && "no env"); +# endif /* def DEBUG_libfirm */ + + fprintf (stdout, "%s: Block(%p) has # (%i)\n", + __FILE__ ":" __PRETTY_FUNCTION__, block, *n); + + (*n) ++; +} + +/* + Count the number of blocks in the given graph +*/ +static int get_n_blocks (ir_graph *graph) +{ + int n = 0; + + ir_node *end_block = get_irg_end (graph); + +# ifdef DEBUG_libfirm + assert (graph && "no graph"); + assert (end_block && "no end block"); +# endif /* def DEBUG_libfirm */ + + irg_block_walk (end_block, count_block, NULL, &n); + // irg_block_walk (end_block, NULL, NULL, NULL); + + // return (24); + + fprintf (stdout, "%s: Graph(%p) has (%i) blocks\n", + __FILE__ ":" __PRETTY_FUNCTION__, graph, n); + + return (n); +} + +/* + Build an empty dominator relation entry +*/ +static dtree_t *new_dtree (dt_t *tree, ir_graph *graph) +{ + dtree_t *res = (dtree_t*) malloc (sizeof (dtree_t)); + +# ifdef DEBUG_libfirm + assert (res && "no memory for dtree"); +# endif /* def DEBUG_libfirm */ + + res->tree = tree; + res->graph = graph; + res->next = 0; + + return (res); +} + +/* + Build an empty dominator relation +*/ +static dt_t *new_dt (ir_graph *graph) +{ + int i; + int n_blocks = get_n_blocks (graph); + + dt_t *res = (dt_t*) malloc (sizeof (dt_t)); + +# ifdef DEBUG_libfirm + assert (n_blocks && "no blocks for dt"); + assert (res && "no memory for dt"); +# endif /* def DEBUG_libfirm */ + + res->n_blocks = n_blocks; + res->graph = graph; + res->blocks = (ir_node**) calloc (n_blocks, sizeof (ir_node*)); + res->idoms = (ir_node**) calloc (n_blocks, sizeof (ir_node*)); + res->masks = (bs_t*) calloc (n_blocks, sizeof (bs_t)); + + assert (res && "no dt"); + + return (res); +} + +static void free_dt (dt_t *dt) +{ + free (dt->blocks); dt->blocks = 0; + free (dt->masks); dt->masks = 0; + free (dt); +} + + +// -------------------------------------------------------------------- +// Private Functions +// -------------------------------------------------------------------- + +/* + Given a graph, find its dominator tree in the global list: + + @return The tree, if it exists, and 0 else +*/ +static dt_t *get_dominator_tree (ir_graph *graph) +{ + dtree_t *iter = trees; + +# ifdef DEBUG_libfirm + assert (graph && "no graph"); + // assert (iter && "no trees"); +# endif /* def DEBUG_libfirm */ + + while ((0 != iter) && (graph != iter->graph)) + iter = iter->next; + + if (0 != iter) + { +# ifdef DEBUG_libfirm + assert ((graph == iter->tree->graph) && "wrong graph"); +# endif /* def DEBUG_libfirm */ + + return (iter->tree); + } + else + { + return (0); + } +} + +/* + Given a dominator tree and a graph, enter the tree into the global list. +*/ +static void add_dominator_tree (dt_t *tree) +{ + dtree_t *dtree = 0; + ir_graph *graph = tree->graph; + +# ifdef DEBUG_libfirm + assert (tree && "no tree" ); + assert (graph && "no graph"); +# endif /* def DEBUG_libfirm */ + + dtree = new_dtree (tree, graph); + +# ifdef VERBOSE_libfirm + fprintf (stdout, "%s: Adding dtree(%p) into trees(%p)\n", + __FILE__ ":" __PRETTY_FUNCTION__, dtree, trees); +# endif /* def VERBOSE_libfirm */ + + //enter in global list: + dtree->next = trees; + trees = dtree; +} + +/* + Get (or create) the index for a given block +*/ +static int get_index (dt_t *dt, ir_node *block) +{ + int i; + +# ifdef DEBUG_libfirm + assert (dt && "no dt"); + assert (block && "no block"); +# endif /* def DEBUG_libfirm */ + + for (i = 0; (i < dt->n_blocks) && (0 != dt->blocks [i]); i ++) + if (block == dt->blocks [i]) + return (i); + + /* not found . . . enter new one: */ + dt->blocks [i] = block; + if (block == get_irg_start_block (dt->graph)) + { + dt->masks [i] = 0x00000001 << i; + +# ifdef VERBOSE_libfirm + fprintf (stdout, "%s: Adding block(%p)[%i] with [%#010lx]\n", + __FILE__ ":" __PRETTY_FUNCTION__, block, i, dt->masks [i]); +# endif /* def VERBOSE_libfirm */ + } + else + { + dt->masks [i] = ~0x00000000; + +# ifdef VERBOSE_libfirm + fprintf (stdout, "%s: Adding block(%p)[%i] with [%#010lx]\n", + __FILE__ ":" __PRETTY_FUNCTION__, block, i, dt->masks [i]); +# endif /* def VERBOSE_libfirm */ + } + + return (i); +} + +/* + Get the bit mask for a block +*/ +static bs_t _get_mask (dt_t*, int); +static bs_t get_mask (dt_t *dt, ir_node *block) +{ + int index = get_index (dt, block); + +# ifdef DEBUG_libfirm + assert (dt && "no dt"); + assert (block && "no block"); +# endif /* def DEBUG_libfirm */ + + return (_get_mask (dt, index)); +} + +/* + Get the bit mask for a block index +*/ +static bs_t _get_mask (dt_t *dt, int index) +{ +# ifdef DEBUG_libfirm + assert (dt && "no dt"); +# endif /* def DEBUG_libfirm */ + + return (dt->masks [index]); +} + +/* + Set the bit mask for a block +*/ +static void _set_mask (dt_t*, int, bs_t); +static void set_mask (dt_t *dt, ir_node *block, bs_t mask) +{ + int index = get_index (dt, block); + +# ifdef DEBUG_libfirm + assert (dt && "no dt"); + assert (block && "no block"); +# endif /* def DEBUG_libfirm */ + + _set_mask (dt, index, mask); +} + +/* + Set the bit mask for a block index +*/ +static void _set_mask (dt_t *dt, int index, bs_t mask) +{ +# ifdef DEBUG_libfirm + assert (dt && "no dt"); +# endif /* def DEBUG_libfirm */ + + dt->masks [index] = mask; +} + +/* + Update the list of dominators of a given block +*/ +typedef struct dt_walk_env_t // grrr +{ + dt_t *dt; // the dominator relation we're building + ir_node *start_block; // need to know the start block of this graph + bool changed; // wether the relation has changed recently +} +dt_walk_env_t; + +/* + Helper function for build_dominator_tree +*/ +static void update_dominators (ir_node *block, void *env) +{ + int i; + dt_walk_env_t *w = (dt_walk_env_t*) env; + dt_t *dt = w->dt; + + int block_index = get_index (dt, block); + int n_ins = get_irn_arity (block); + + bs_t old_mask = _get_mask (dt, block_index); + bs_t new_mask = ~0x00000000; + + // Special handling of Start Block: + if (block == w->start_block) + return; + + // check preds: + for (i = 0; i < n_ins; i ++) + { + ir_node *in = get_nodes_Block (get_irn_n (block, i)); // hope that's the block + bs_t in_mask = get_mask (dt, in); + + new_mask &= in_mask; + } + + // and remember ourselves: + new_mask |= (0x00000001 << block_index); + + if (new_mask != old_mask) + { + w->changed = TRUE; + _set_mask (dt, block_index, new_mask); + +# ifdef VERBOSE_libfirm + fprintf (stdout, "%s: Updating block(%p)[%i] from [%#010lx] to [%#010lx]\n", + __FILE__ ":" __PRETTY_FUNCTION__, + block, block_index, old_mask, new_mask); +# endif /* def VERBOSE_libfirm */ + } +} + +/* + Say wether a dominates b +*/ + +static bool _dominates (dt_t *dt, ir_node *a, ir_node *b) +{ + int index_a = get_index (dt, a); + bs_t b_mask = get_mask (dt, b); + + return (0 != (b_mask & (0x00000001 << index_a))); +} + +/* + Return the immediate dominator of block a +*/ +static ir_node *_get_idom (dt_t *dt, ir_node *block) +{ + ir_node *idom = 0; + int block_index = get_index (dt, block); + + if (0 != (idom = dt->idoms [block_index])) + return (idom); + + // check all CFG preds: + // Question: Shouldn't it be good enough to just ask our first CFG predecessor? + { + int i = 0; + int n = get_irn_arity (block); + ir_node *pred = 0; + + idom = block; // prime the loop: + + for (i = 0; i < n; i ++) + { + ir_node *ndom = 0; + + pred = get_nodes_Block (get_irn_n (block, i)); + ndom = _get_idom (dt, pred); + + if (ndom != idom) + if (_dominates (dt, idom, ndom)) + idom = ndom; + } + } + + assert (idom && "Something terribly wrong in _get_idom"); + +# ifdef VERBOSE_libfirm + fprintf (stdout, "%s: idom(%p) = %p\n", + __FILE__ ":" __PRETTY_FUNCTION__, + block, idom); +# endif /* def VERBOSE_libfirm */ + + // remember it: + dt->idoms [block_index] = idom; + + return (idom); +} + +// -------------------------------------------------------------------- +// Public Functions +// -------------------------------------------------------------------- + +/* + Say wether a dominates b +*/ +bool dominates (ir_graph *g, ir_node *a, ir_node *b) +{ + dt_t *dt = get_dominator_tree (g); + + return (_dominates (dt, a, b)); +} + +/* + Return the immediate dominator of block a +*/ +ir_node *get_idom (ir_graph *g, ir_node *a) +{ + dt_t *dt = get_dominator_tree (g); + + return (_get_idom (dt, a)); +} + +/* + Allow for precomputation of necessary data + This will allow for a slightly faster lookup of the dominator + relation if one node is checked for dominance against many other nodes. +*/ +dom_env_t *get_dom_env (ir_graph *graph, ir_node *a) +{ + dom_env_t *env = (dom_env_t*) calloc (1, sizeof (dom_env_t)); + + env->graph = graph; + env->dt = get_dominator_tree (graph); + env->a = a; + env->index_a = get_index (env->dt, a); +} + +/* + Dispose a dominator environment +*/ +void delete_dom_env (dom_env_t *env) +{ + env->dt = 0; + env->a = 0; + env->graph = 0; + env->index_a = -1; + + free (env); +} + +/* + Say wether the node in env dominates b + + see get_dom_env +*/ +bool dominates_l (dom_env_t *env, ir_node *b) +{ + int index_a = env->index_a; + dt_t *dt = env->dt; + bs_t b_mask = get_mask (dt, b); + + return (0 != (b_mask & (0x00000001 << index_a))); +} + +/* + Build a new dominator tree for the given graph +*/ +void build_dominator_tree (ir_graph *graph) +{ + /* + dt_walk_env_t *w = (dt_walk_env_t*) alloca (sizeof (dt_walk_env_t)); + + ir_node *end_block = get_irg_end_block (graph); + ir_node *start_block = get_irg_start_block (graph); + int n_blocks = get_n_blocks (graph); + dt_t *dt = get_dominator_tree (graph); + */ + + dt_walk_env_t *w = 0; + ir_node *end_block = 0; + ir_node *start_block = 0; + int n_blocks = 0; + dt_t *dt = 0; + + w = (dt_walk_env_t*) alloca (sizeof (dt_walk_env_t)); + end_block = get_irg_end_block (graph); + start_block = get_irg_start_block (graph); + n_blocks = get_n_blocks (graph); + dt = get_dominator_tree (graph); + +# ifdef DEBUG_libfirm + assert (graph && "no graph"); +# endif /* def DEBUG_libfirm */ + +# ifdef VERBOSE_libfirm + fprintf (stdout, "%s: for graph(%p)\n", __FILE__ ":" __PRETTY_FUNCTION__, graph); +# endif /* def VERBOSE_libfirm */ + + //if (0 != dt) + //free_dt (dt); + + dt = new_dt (graph); + + w->dt = dt; + w->start_block = start_block; // grrr + w->changed = TRUE; // at least one walk + + // do the walk: + { + int walks = 0; + + while (w->changed) + { + w->changed = FALSE; + irg_block_walk (end_block, update_dominators, update_dominators, (void*) w); + walks ++; + } + +# ifdef VERBOSE_libfirm + fprintf (stdout, "%s: for graph(%p): %i passes\n", + __FILE__ ":" __PRETTY_FUNCTION__, graph, walks); +# endif /* def VERBOSE_libfirm */ + } + + /* ok, now remember it: */ + add_dominator_tree (dt); +} diff --git a/ir/st/st.h b/ir/st/st.h new file mode 100644 index 000000000..3397fb71c --- /dev/null +++ b/ir/st/st.h @@ -0,0 +1,73 @@ +// Copyright (c) 2002 by Universität Karlsruhe (TH). All Rights Reserved + +/*** + NAME + st.h + PURPOSE + provide some auxilliary structures for firm graphs. + NOTES + not quite complete + HISTORY + liekweg - Feb 26, 2002: Created. + CVS: + $Id$ +***/ + +# ifndef _ST_H_ +# define _ST_H_ + +// Includes: +# include "irgraph.h" +# include "irnode.h" + +# include "bs.h" + +# include + +// Data Types: + +// One dominator tree +typedef struct +{ + int n_blocks; + ir_graph *graph; // PRE + ir_node **blocks; + ir_node **idoms; // idom [n] == immediate dominator of blocks [n] + bs_t *masks; +} +dt_t; + +// List entry: +typedef struct dtree_t +{ + dt_t *tree; + ir_graph *graph; + + struct dtree_t *next; +} +dtree_t; + +// dominator environment for a node @a in graph @graph +typedef struct dom_env_t +{ + dt_t *dt; + ir_graph *graph; + ir_node *a; + int index_a; + bs_t mask; +} dom_env_t; + +// Forwards for Globals: +extern dtree_t *trees; +extern dtree_t *last; + +// Prototypes: +void st_build_dominator_tree (ir_graph*); +bool dominates (ir_graph*, ir_node*, ir_node*); +ir_node *get_idom (ir_graph*, ir_node*); + +dom_env_t *get_dom_env (ir_graph*, ir_node*); +void delete_dom_env (dom_env_t*); +bool dominates_l (dom_env_t*, ir_node*); + +# endif /* defined _ST_H_ */ -- 2.20.1