X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fcdep.c;h=4af268ed2071daff205ad4c93c6f0c176d1e68af;hb=2cb9bca5da82b2f96f303cb568f977e339ba87b7;hp=b6e9d91441da93603acf2ee2a5eb820301208a8d;hpb=64eae41a44856b8b13b1ea6edce58188f1de7e3e;p=libfirm diff --git a/ir/ana/cdep.c b/ir/ana/cdep.c index b6e9d9144..4af268ed2 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,88 +30,107 @@ #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 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) +/* 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) +{ + 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 = malloc(sizeof(*newdep)); - - newdep->node = dep_on; - newdep->next = NULL; - pmap_insert(cdep_map, node, newdep); - } else { - cdep* newdep; - - for (;;) { - if (dep->node == dep_on) return; - if (dep->next == NULL) break; - dep = dep->next; - } - newdep = malloc(sizeof(*newdep)); - newdep->node = dep_on; - newdep->next = NULL; - dep->next = newdep; - } + if (dep == NULL) { + ir_cdep *newdep = OALLOC(&cdep_data->obst, ir_cdep); + + newdep->node = dep_on; + newdep->next = NULL; + pmap_insert(cdep_data->cdep_map, node, newdep); + } else { + ir_cdep *newdep; + + for (;;) { + if (dep->node == dep_on) return; + if (dep->next == NULL) break; + dep = dep->next; + } + newdep = OALLOC(&cdep_data->obst, ir_cdep); + newdep->node = dep_on; + newdep->next = NULL; + dep->next = newdep; + } } +typedef struct cdep_env { + ir_node *start_block; + ir_node *end_block; +} cdep_env; -static void cdep_pre(ir_node* node, void* env) +/** + * Pre-block-walker: calculate the control dependence + */ +static void cdep_pre(ir_node *node, void *ctx) { - uint n; - uint i; - - /* special case: - * start and end block have no control depency - */ - if (node == get_irg_start_block(get_irn_irg(node))) return; - if (node == get_irg_end_block(get_irn_irg(node))) return; - - n = get_Block_n_cfgpreds(node); - for (i = 0; i < n; i++) { - ir_node* pred = get_Block_cfgpred_block(node, i); - ir_node* pdom; - ir_node* dependee; - - if (is_Bad(pred)) continue; - - pdom = get_Block_ipostdom(pred); - for (dependee = node; dependee != pdom; dependee = get_Block_ipostdom(dependee)) { - assert(!is_Bad(pdom)); - add_cdep(dependee, pred); - } - } + cdep_env *env = (cdep_env*) ctx; + int i; + + /* special case: + * start and end block have no control dependency + */ + if (node == env->start_block) return; + if (node == env->end_block) return; + + 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; + + if (is_Bad(pred)) continue; + + pdom = get_Block_ipostdom(pred); + for (dependee = node; dependee != pdom; dependee = get_Block_ipostdom(dependee)) { + assert(!is_Bad(pdom)); + add_cdep(dependee, pred); + } + } } -#include "irdump.h" - - -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) { -#if 0 - ir_node* pdom; -#endif - cdep* cd; + ir_cdep *cd; #if 0 - pdom = get_Block_ipostdom(block); + ir_node *pdom = get_Block_ipostdom(block); if (pdom != NULL) { fprintf( F, @@ -96,47 +140,72 @@ static int cdep_edge_hook(FILE* F, ir_node* block) } #endif - for (cd = find_cdep(block); cd != NULL; cd = cd->next) { - fprintf( - F, + for (cd = find_cdep(block); cd != NULL; cd = cd->next) { + fprintf( + F, "edge:{sourcename:\"n%ld\" targetname:\"n%ld\" " "linestyle:dashed color:gold}\n", get_irn_node_nr(block), get_irn_node_nr(cd->node) ); - } + } return 0; } - -void compute_cdep(ir_graph* irg) +/* Compute the control dependence graph for a graph. */ +void compute_cdep(ir_graph *irg) { - cdep_map = pmap_create(); + ir_node *rem; + cdep_env env; + + free_cdep(irg); + cdep_data = XMALLOC(cdep_info); + obstack_init(&cdep_data->obst); + + cdep_data->cdep_map = pmap_create(); - compute_postdoms(irg); - set_Block_ipostdom(get_irg_start_block(irg), get_irg_end_block(irg)); + assure_postdoms(irg); - irg_block_walk_graph(irg, cdep_pre, NULL, NULL); + /* 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); -#if 1 + 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"); + dump_ir_block_graph(irg, "_cdep"); set_dump_block_edge_hook(NULL); +#else + (void) cdep_edge_hook; #endif - free_postdom(irg); + /* restore the post dominator relation */ + set_Block_ipostdom(env.start_block, rem); } - -void free_cdep(ir_graph* irg) +/* Free the control dependence info. */ +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) +/* 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; @@ -144,10 +213,10 @@ int is_cdep_on(const ir_node* dependee, const ir_node* candidate) return 0; } - -int is_iterated_cdep_on(ir_node* dependee, ir_node* candidate) +/* 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; @@ -157,18 +226,18 @@ int is_iterated_cdep_on(ir_node* dependee, ir_node* candidate) return 0; } - -ir_node* get_unique_cdep(const ir_node* block) +/* 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; } - -int has_multiple_cdep(const ir_node* block) +/* 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; }