-/* Copyright (c) 2002 by Universität Karlsruhe (TH). All Rights Reserved */
-//
-// Time-stamp: <02/03/04 16:57:32 liekweg>
-//
-
-/***
+/*
+ * Project: libFIRM
+ * File name: ir/st/st.c
+ * Purpose: Provide some auxilliary structures for firm graphs.
+ * Author: Florian Liekweg
+ * Modified by:
+ * Created: 26.2.2002
+ * CVS-ID: $Id$
+ * Copyright: (c) 2002-2003 Universität Karlsruhe
+ * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
+ */
+
+/**
NAME
st.h
PURPOSE
provide some auxilliary structures for firm graphs.
- NOTES
+ S
not quite complete
- HISTORY
- liekweg - Feb 26, 2002: Created.
- CVS:
- $Id$
***/
-# include "st.h"
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <assert.h>
+
+#ifdef HAVE_STDIO_H
+# include <stdio.h>
+#endif
+#ifdef HAVE_STDLIB_H
+# include <stdlib.h>
+#endif
+#ifdef HAVE_MALLOC_H
+# include <malloc.h>
+#endif
+#ifdef HAVE_ALLOCA_H
+# include <alloca.h>
+#endif
+# include "st.h"
# include "irgwalk.h"
-
-# include <stdio.h>
-# ifdef DEBUG_libfirm
-# endif /* def DEBUG_libfirm */
-# include <malloc.h>
+# include "xmalloc.h"
/* init globals: */
-static dtree_t *trees = 0;
+/*static*/ dtree_t *trees = 0;
+/*
static dtree_t *last = 0;
+*/
-// --------------------------------------------------------------------
-// Helper Functions
-// --------------------------------------------------------------------
+/* --------------------------------------------------------------------
+* Helper Functions
+* -------------------------------------------------------------------- */
/*
Helper function for get_n_blocks
*/
# endif /* def DEBUG_libfirm */
fprintf (stdout, "%s: Block(%p) has # (%i)\n",
- __FILE__ ":" __PRETTY_FUNCTION__, block, *n);
+ __FILE__ ":count_block", (void *)block, *n);
(*n) ++;
}
# 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);
+ __FILE__ ":get_n_blocks", (void *)graph, n);
return (n);
}
*/
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));
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));
+ res->blocks = xcalloc(n_blocks, sizeof(res->blocks[0]));
+ res->idoms = xcalloc(n_blocks, sizeof(res->idoms[0]));
+ res->masks = xcalloc(n_blocks, sizeof(res->masks[0]));
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
-// --------------------------------------------------------------------
+/* --------------------------------------------------------------------
+* Private Functions
+* -------------------------------------------------------------------- */
/*
Given a graph, find its dominator tree in the global list:
# ifdef DEBUG_libfirm
assert (graph && "no graph");
- // assert (iter && "no trees");
# endif /* def DEBUG_libfirm */
while ((0 != iter) && (graph != iter->graph))
__FILE__ ":" __PRETTY_FUNCTION__, dtree, trees);
# endif /* def VERBOSE_libfirm */
- //enter in global list:
+ /* enter in global list: */
dtree->next = trees;
trees = dtree;
}
/*
Set the bit mask for a block
*/
+#if 0
static void _set_mask (dt_t*, int, bs_t);
static void set_mask (dt_t *dt, ir_node *block, bs_t mask)
{
# ifdef DEBUG_libfirm
assert (dt && "no dt");
assert (block && "no block");
-# endif /* def DEBUG_libfirm */
+ # endif /* def DEBUG_libfirm */
_set_mask (dt, index, mask);
}
-
+#endif
/*
Set the bit mask for a block index
*/
/*
Update the list of dominators of a given block
*/
-typedef struct dt_walk_env_t // grrr
+typedef struct dt_walk_env_t
{
- 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_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;
bs_t old_mask = _get_mask (dt, block_index);
bs_t new_mask = ~0x00000000;
- // Special handling of Start Block:
+ /* Special handling of Start Block: */
if (block == w->start_block)
return;
- // check preds:
+ /* 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);
+ {
+ ir_node *in = get_nodes_block (get_irn_n (block, i));
+ bs_t in_mask = get_mask (dt, in);
- new_mask &= in_mask;
- }
+ new_mask &= in_mask;
+ }
- // and remember ourselves:
+ /* and remember ourselves: */
new_mask |= (0x00000001 << block_index);
if (new_mask != old_mask)
{
- w->changed = TRUE;
+ w->changed = true;
_set_mask (dt, block_index, new_mask);
# ifdef VERBOSE_libfirm
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?
+ /* 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:
+ idom = block; /* prime the loop: */
for (i = 0; i < n; i ++)
{
ir_node *ndom = 0;
- pred = get_nodes_Block (get_irn_n (block, i));
+ pred = get_nodes_block (get_irn_n (block, i));
ndom = _get_idom (dt, pred);
if (ndom != idom)
block, idom);
# endif /* def VERBOSE_libfirm */
- // remember it:
+ /* remember it: */
dt->idoms [block_index] = idom;
return (idom);
}
-// --------------------------------------------------------------------
-// Public Functions
-// --------------------------------------------------------------------
+/* --------------------------------------------------------------------
+* Public Functions
+* -------------------------------------------------------------------- */
/*
Say wether a dominates b
*/
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));
+ dom_env_t *env = xcalloc(1, sizeof(*env));
env->graph = graph;
env->dt = get_dominator_tree (graph);
env->a = a;
env->index_a = get_index (env->dt, a);
+ return env;
}
/*
fprintf (stdout, "%s: for graph(%p)\n", __FILE__ ":" __PRETTY_FUNCTION__, graph);
# endif /* def VERBOSE_libfirm */
- //if (0 != dt)
- //free_dt (dt);
+ /*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
+ w->start_block = start_block;
+ w->changed = true; /* at least one walk */
- // do the walk:
+ /* do the walk: */
{
int walks = 0;
while (w->changed)
{
- w->changed = FALSE;
+ w->changed = false;
irg_block_walk (end_block, update_dominators, update_dominators, (void*) w);
walks ++;
}