X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;ds=sidebyside;f=ir%2Fana%2Fcdep.c;h=498ffbd9b58e47341976fcb2dbdcbcff96e1ffec;hb=65daf5bc390b02d68581f4c431dbdbfaae11b88f;hp=eb8407669a4f241aa068d402df25ba10a0d82293;hpb=1a748f0bd3ce1c06637dd3670eb26adc456da9d9;p=libfirm diff --git a/ir/ana/cdep.c b/ir/ana/cdep.c index eb8407669..498ffbd9b 100644 --- a/ir/ana/cdep.c +++ b/ir/ana/cdep.c @@ -1,3 +1,28 @@ +/* + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. + */ + +/** + * @file + * @brief Implementation of cdep + * @author Christoph Mallon + * @version $Id$ + */ #include #include #include "irdom.h" @@ -5,50 +30,66 @@ #include "irgwalk.h" #include "irnode.h" #include "pmap.h" +#include "obst.h" #include "xmalloc.h" -#include "cdep.h" +#include "cdep_t.h" #include "irprintf.h" +#include "irdump.h" -typedef unsigned int uint; +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) +ir_node *(get_cdep_node)(const ir_cdep *cdep) { - return pmap_get(cdep_map, (void *)block); + return _get_cdep_node(cdep); } - -void exchange_cdep(ir_node *old, const ir_node *nw) +ir_cdep *(get_cdep_next)(const ir_cdep *cdep) { - cdep *cdep = find_cdep(nw); + return _get_cdep_next(cdep); +} - pmap_insert(cdep_map, old, cdep); +/* Return a list of all control dependences of a block. */ +ir_cdep *find_cdep(const ir_node *block) +{ + assert(is_Block(block)); + return (ir_cdep*) pmap_get(cdep_data->cdep_map, block); } +void exchange_cdep(ir_node *old, const ir_node *nw) +{ + ir_cdep *cdep = find_cdep(nw); + assert(is_Block(old)); + 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); -#if 0 - ir_fprintf(stderr, "Adding cdep of %+F on %+F\n", node, dep_on); -#endif + ir_cdep *dep = find_cdep(node); + assert(is_Block(dep_on)); 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 (get_cdep_node(dep) == 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; @@ -65,9 +106,8 @@ typedef struct cdep_env { */ static void cdep_pre(ir_node *node, void *ctx) { - cdep_env *env = ctx; - uint n; - uint i; + cdep_env *env = (cdep_env*) ctx; + int i; /* special case: * start and end block have no control dependency @@ -75,8 +115,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; @@ -92,25 +131,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) { - cdep *cd; - -#if 0 - ir_node *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 + ir_cdep *cd; for (cd = find_cdep(block); cd != NULL; cd = cd->next) { fprintf( @@ -124,77 +150,74 @@ static int cdep_edge_hook(FILE *F, ir_node *block) return 0; } - 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); - 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); + + 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 set_dump_block_edge_hook(cdep_edge_hook); dump_ir_block_graph(irg, "_cdep"); set_dump_block_edge_hook(NULL); +#else + (void) cdep_edge_hook; #endif /* restore the post dominator relation */ - set_Block_ipostdom(start_block, rem); + set_Block_ipostdom(env.start_block, rem); } - 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; + } } - 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; - } - return 0; -} - - -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; + if (get_cdep_node(dep) == candidate) return 1; } return 0; } - 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 ? get_cdep_node(cdep) : NULL; } - 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; }