projects
/
libfirm
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
fix wrong usage of ircons functions
[libfirm]
/
ir
/
ana
/
cdep.c
diff --git
a/ir/ana/cdep.c
b/ir/ana/cdep.c
index
f2b0fb5
..
4af268e
100644
(file)
--- a/
ir/ana/cdep.c
+++ b/
ir/ana/cdep.c
@@
-1,5
+1,5
@@
/*
/*
- * Copyrig
th (C) 1995-2007
University of Karlsruhe. All right reserved.
+ * Copyrig
ht (C) 1995-2008
University of Karlsruhe. All right reserved.
*
* This file is part of libFirm.
*
*
* This file is part of libFirm.
*
@@
-20,6
+20,7
@@
/**
* @file
* @brief Implementation of cdep
/**
* @file
* @brief Implementation of cdep
+ * @author Christoph Mallon
* @version $Id$
*/
#include <assert.h>
* @version $Id$
*/
#include <assert.h>
@@
-29,48
+30,57
@@
#include "irgwalk.h"
#include "irnode.h"
#include "pmap.h"
#include "irgwalk.h"
#include "irnode.h"
#include "pmap.h"
+#include "obst.h"
#include "xmalloc.h"
#include "cdep.h"
#include "irprintf.h"
#include "xmalloc.h"
#include "cdep.h"
#include "irprintf.h"
+#include "irdump.h"
+
+typedef struct cdep_info {
+ pmap *cdep_map; /**< A map to find the list of all control dependence nodes for a block. */
+ struct obstack obst; /**< An obstack where all cdep data lives on. */
+} cdep_info;
-static
pmap *cdep_map
;
+static
cdep_info *cdep_data
;
-cdep *find_cdep(const ir_node *block)
+/* Return a list of all control dependences of a block. */
+ir_cdep *find_cdep(const ir_node *block)
{
{
- return
pmap_get(cdep_map, (void *)
block);
+ return
(ir_cdep*) pmap_get(cdep_data->cdep_map,
block);
}
}
-
+/* Replace the control dependence info of old by the info of nw. */
void exchange_cdep(ir_node *old, const ir_node *nw)
{
void exchange_cdep(ir_node *old, const ir_node *nw)
{
- cdep *cdep = find_cdep(nw);
-
- pmap_insert(cdep_map, old, cdep);
+ ir_cdep *cdep = find_cdep(nw);
+ pmap_insert(cdep_data->cdep_map, old, cdep);
}
}
-
-static void add_cdep(ir_node* node, ir_node* dep_on)
+/**
+ * Adds a control dependence from node to dep_on.
+ */
+static void add_cdep(ir_node *node, ir_node *dep_on)
{
{
- cdep *dep = find_cdep(node);
+
ir_
cdep *dep = find_cdep(node);
#if 0
ir_fprintf(stderr, "Adding cdep of %+F on %+F\n", node, dep_on);
#endif
if (dep == NULL) {
#if 0
ir_fprintf(stderr, "Adding cdep of %+F on %+F\n", node, dep_on);
#endif
if (dep == NULL) {
-
cdep *newdep = xmalloc(sizeof(*newdep)
);
+
ir_cdep *newdep = OALLOC(&cdep_data->obst, ir_cdep
);
newdep->node = dep_on;
newdep->next = NULL;
newdep->node = dep_on;
newdep->next = NULL;
- pmap_insert(cdep_map, node, newdep);
+ pmap_insert(cdep_
data->cdep_
map, node, newdep);
} else {
} else {
- cdep *newdep;
+
ir_
cdep *newdep;
for (;;) {
if (dep->node == dep_on) return;
if (dep->next == NULL) break;
dep = dep->next;
}
for (;;) {
if (dep->node == dep_on) return;
if (dep->next == NULL) break;
dep = dep->next;
}
- newdep =
xmalloc(sizeof(*newdep)
);
+ newdep =
OALLOC(&cdep_data->obst, ir_cdep
);
newdep->node = dep_on;
newdep->next = NULL;
dep->next = newdep;
newdep->node = dep_on;
newdep->next = NULL;
dep->next = newdep;
@@
-87,9
+97,8
@@
typedef struct cdep_env {
*/
static void cdep_pre(ir_node *node, void *ctx)
{
*/
static void cdep_pre(ir_node *node, void *ctx)
{
- cdep_env *env = ctx;
- unsigned int n;
- unsigned int i;
+ cdep_env *env = (cdep_env*) ctx;
+ int i;
/* special case:
* start and end block have no control dependency
/* special case:
* start and end block have no control dependency
@@
-97,8
+106,7
@@
static void cdep_pre(ir_node *node, void *ctx)
if (node == env->start_block) return;
if (node == env->end_block) return;
if (node == env->start_block) return;
if (node == env->end_block) return;
- n = get_Block_n_cfgpreds(node);
- for (i = 0; i < n; i++) {
+ for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
ir_node *pred = get_Block_cfgpred_block(node, i);
ir_node *pdom;
ir_node *dependee;
ir_node *pred = get_Block_cfgpred_block(node, i);
ir_node *pdom;
ir_node *dependee;
@@
-114,14
+122,12
@@
static void cdep_pre(ir_node *node, void *ctx)
}
}
-#include "irdump.h"
-
/**
* A block edge hook: add all cdep edges of block.
*/
static int cdep_edge_hook(FILE *F, ir_node *block)
{
/**
* A block edge hook: add all cdep edges of block.
*/
static int cdep_edge_hook(FILE *F, ir_node *block)
{
- cdep *cd;
+
ir_
cdep *cd;
#if 0
ir_node *pdom = get_Block_ipostdom(block);
#if 0
ir_node *pdom = get_Block_ipostdom(block);
@@
-146,23
+152,30
@@
static int cdep_edge_hook(FILE *F, ir_node *block)
return 0;
}
return 0;
}
-
+/* Compute the control dependence graph for a graph. */
void compute_cdep(ir_graph *irg)
{
void compute_cdep(ir_graph *irg)
{
- ir_node *
start_block, *
rem;
+ ir_node *rem;
cdep_env env;
cdep_env env;
- cdep_map = pmap_create();
+ free_cdep(irg);
+ cdep_data = XMALLOC(cdep_info);
+ obstack_init(&cdep_data->obst);
-
assure_postdoms(irg
);
+
cdep_data->cdep_map = pmap_create(
);
- /* we must temporary change the post dominator relation */
- start_block = get_irg_start_block(irg);
- rem = get_Block_ipostdom(start_block);
- set_Block_ipostdom(start_block, get_irg_end_block(irg));
+ assure_postdoms(irg);
+ /* we must temporary change the post dominator relation:
+ the ipdom of the startblock is the end block.
+ Firm does NOT add the phantom edge from Start to End.
+ */
env.start_block = get_irg_start_block(irg);
env.end_block = get_irg_end_block(irg);
env.start_block = get_irg_start_block(irg);
env.end_block = get_irg_end_block(irg);
+
+ rem = get_Block_ipostdom(env.start_block);
+ set_Block_ipostdom(env.start_block, env.end_block);
+
irg_block_walk_graph(irg, cdep_pre, NULL, &env);
#if 0
irg_block_walk_graph(irg, cdep_pre, NULL, &env);
#if 0
@@
-174,19
+187,25
@@
void compute_cdep(ir_graph *irg)
#endif
/* restore the post dominator relation */
#endif
/* restore the post dominator relation */
- set_Block_ipostdom(start_block, rem);
+ set_Block_ipostdom(
env.
start_block, rem);
}
}
-
+/* Free the control dependence info. */
void free_cdep(ir_graph *irg)
{
void free_cdep(ir_graph *irg)
{
- // TODO atm leaking more memory than a small memory leaking animal
+ (void) irg;
+ if (cdep_data != NULL) {
+ pmap_destroy(cdep_data->cdep_map);
+ obstack_free(&cdep_data->obst, NULL);
+ xfree(cdep_data);
+ cdep_data = NULL;
+ }
}
}
-
+/* Check whether dependee is (directly) control dependent on candidate. */
int is_cdep_on(const ir_node *dependee, const ir_node *candidate)
{
int is_cdep_on(const ir_node *dependee, const ir_node *candidate)
{
- const cdep *dep;
+ const
ir_
cdep *dep;
for (dep = find_cdep(dependee); dep != NULL; dep = dep->next) {
if (dep->node == candidate) return 1;
for (dep = find_cdep(dependee); dep != NULL; dep = dep->next) {
if (dep->node == candidate) return 1;
@@
-194,10
+213,10
@@
int is_cdep_on(const ir_node *dependee, const ir_node *candidate)
return 0;
}
return 0;
}
-
+/* Check whether dependee is (possible iterated) control dependent on candidate. */
int is_iterated_cdep_on(ir_node *dependee, ir_node *candidate)
{
int is_iterated_cdep_on(ir_node *dependee, ir_node *candidate)
{
- const cdep *dep;
+ const
ir_
cdep *dep;
while ((dep = find_cdep(dependee)) != NULL) {
if (dep->next != NULL) return 0;
while ((dep = find_cdep(dependee)) != NULL) {
if (dep->next != NULL) return 0;
@@
-207,18
+226,18
@@
int is_iterated_cdep_on(ir_node *dependee, ir_node *candidate)
return 0;
}
return 0;
}
-
+/* If block is control dependent on exactly one node, return this node, else NULL. */
ir_node *get_unique_cdep(const ir_node *block)
{
ir_node *get_unique_cdep(const ir_node *block)
{
- cdep *cdep = find_cdep(block);
+
ir_
cdep *cdep = find_cdep(block);
return cdep != NULL && cdep->next == NULL ? cdep->node : NULL;
}
return cdep != NULL && cdep->next == NULL ? cdep->node : NULL;
}
-
+/* Check if the given block is control dependent of more than one node. */
int has_multiple_cdep(const ir_node *block)
{
int has_multiple_cdep(const ir_node *block)
{
- cdep *cdep = find_cdep(block);
+
ir_
cdep *cdep = find_cdep(block);
return cdep != NULL && cdep->next != NULL;
}
return cdep != NULL && cdep->next != NULL;
}