X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fcdep.c;h=4af268ed2071daff205ad4c93c6f0c176d1e68af;hb=971bb3d4ab2da19de4f3edc07e56e4249d765efd;hp=4070ca0a459b806df20e1a648174187ad509fdc1;hpb=0c206cf66ead39ebfc0e2fc3f310e8a26af4a82a;p=libfirm diff --git a/ir/ana/cdep.c b/ir/ana/cdep.c index 4070ca0a4..4af268ed2 100644 --- a/ir/ana/cdep.c +++ b/ir/ana/cdep.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -20,6 +20,7 @@ /** * @file * @brief Implementation of cdep + * @author Christoph Mallon * @version $Id$ */ #include @@ -29,50 +30,57 @@ #include "irgwalk.h" #include "irnode.h" #include "pmap.h" +#include "obst.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) { - 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) { - cdep *newdep = xmalloc(sizeof(*newdep)); + ir_cdep *newdep = OALLOC(&cdep_data->obst, ir_cdep); newdep->node = dep_on; newdep->next = NULL; - pmap_insert(cdep_map, node, newdep); + pmap_insert(cdep_data->cdep_map, node, newdep); } else { - cdep *newdep; + ir_cdep *newdep; 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; @@ -89,9 +97,8 @@ typedef struct cdep_env { */ 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 @@ -99,8 +106,7 @@ static void cdep_pre(ir_node *node, void *ctx) 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; @@ -121,7 +127,7 @@ static void cdep_pre(ir_node *node, void *ctx) */ static int cdep_edge_hook(FILE *F, ir_node *block) { - cdep *cd; + ir_cdep *cd; #if 0 ir_node *pdom = get_Block_ipostdom(block); @@ -146,13 +152,17 @@ static int cdep_edge_hook(FILE *F, ir_node *block) return 0; } - +/* Compute the control dependence graph for a graph. */ void compute_cdep(ir_graph *irg) { - ir_node *start_block, *rem; + ir_node *rem; cdep_env env; - cdep_map = pmap_create(); + free_cdep(irg); + cdep_data = XMALLOC(cdep_info); + obstack_init(&cdep_data->obst); + + cdep_data->cdep_map = pmap_create(); assure_postdoms(irg); @@ -160,12 +170,12 @@ void compute_cdep(ir_graph *irg) the ipdom of the startblock is the end block. Firm does NOT add the phantom edge from Start to End. */ - start_block = get_irg_start_block(irg); - rem = get_Block_ipostdom(start_block); - set_Block_ipostdom(start_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 @@ -177,20 +187,25 @@ void compute_cdep(ir_graph *irg) #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) irg; - // TODO atm leaking more memory than a small memory leaking animal + 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) { - const cdep *dep; + const ir_cdep *dep; for (dep = find_cdep(dependee); dep != NULL; dep = dep->next) { if (dep->node == candidate) return 1; @@ -198,10 +213,10 @@ int is_cdep_on(const ir_node *dependee, const ir_node *candidate) return 0; } - +/* Check whether dependee is (possible iterated) control dependent on 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; @@ -211,18 +226,18 @@ int is_iterated_cdep_on(ir_node *dependee, ir_node *candidate) 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) { - cdep *cdep = find_cdep(block); + ir_cdep *cdep = find_cdep(block); 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) { - cdep *cdep = find_cdep(block); + ir_cdep *cdep = find_cdep(block); return cdep != NULL && cdep->next != NULL; }