nsz Git - libfirm/blob - ir/ana/cdep.c

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   Implementation of cdep
  23  * @author  Christoph Mallon
  24  * @version $Id$
  25  */
  26 #include <assert.h>
  27 #include <stdlib.h>
  28 #include "irdom.h"
  29 #include "irgraph.h"
  30 #include "irgwalk.h"
  31 #include "irnode.h"
  32 #include "pmap.h"
  33 #include "obst.h"
  34 #include "xmalloc.h"
  35 #include "cdep.h"
  36 #include "irprintf.h"
  37 #include "irdump.h"
  38
  39 typedef struct cdep_info {
  40         pmap   *cdep_map;     /**< A map to find the list of all control dependence nodes for a block. */
  41         struct obstack obst;  /**< An obstack where all cdep data lives on. */
  42 } cdep_info;
  43
  44 static cdep_info *cdep_data;
  45
  46 /* Return a list of all control dependences of a block. */
  47 ir_cdep *find_cdep(const ir_node *block)
  48 {
  49         return (ir_cdep*) pmap_get(cdep_data->cdep_map, block);
  50 }
  51
  52 /* Replace the control dependence info of old by the info of nw. */
  53 void exchange_cdep(ir_node *old, const ir_node *nw)
  54 {
  55         ir_cdep *cdep = find_cdep(nw);
  56         pmap_insert(cdep_data->cdep_map, old, cdep);
  57 }
  58
  59 /**
  60  * Adds a control dependence from node to dep_on.
  61  */
  62 static void add_cdep(ir_node *node, ir_node *dep_on)
  63 {
  64         ir_cdep *dep = find_cdep(node);
  65 #if 0
  66         ir_fprintf(stderr, "Adding cdep of %+F on %+F\n", node, dep_on);
  67 #endif
  68
  69         if (dep == NULL) {
  70                 ir_cdep *newdep = OALLOC(&cdep_data->obst, ir_cdep);
  71
  72                 newdep->node = dep_on;
  73                 newdep->next = NULL;
  74                 pmap_insert(cdep_data->cdep_map, node, newdep);
  75         } else {
  76                 ir_cdep *newdep;
  77
  78                 for (;;) {
  79                         if (dep->node == dep_on) return;
  80                         if (dep->next == NULL) break;
  81                         dep = dep->next;
  82                 }
  83                 newdep = OALLOC(&cdep_data->obst, ir_cdep);
  84                 newdep->node = dep_on;
  85                 newdep->next = NULL;
  86                 dep->next = newdep;
  87         }
  88 }
  89
  90 typedef struct cdep_env {
  91         ir_node *start_block;
  92         ir_node *end_block;
  93 } cdep_env;
  94
  95 /**
  96  * Pre-block-walker: calculate the control dependence
  97  */
  98 static void cdep_pre(ir_node *node, void *ctx)
  99 {
 100         cdep_env *env = (cdep_env*) ctx;
 101         int i;
 102
 103         /* special case:
 104          * start and end block have no control dependency
 105          */
 106         if (node == env->start_block) return;
 107         if (node == env->end_block) return;
 108
 109         for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
 110                 ir_node *pred = get_Block_cfgpred_block(node, i);
 111                 ir_node *pdom;
 112                 ir_node *dependee;
 113
 114                 if (is_Bad(pred)) continue;
 115
 116                 pdom = get_Block_ipostdom(pred);
 117                 for (dependee = node; dependee != pdom; dependee = get_Block_ipostdom(dependee)) {
 118                         assert(!is_Bad(pdom));
 119                         add_cdep(dependee, pred);
 120                 }
 121         }
 122 }
 123
 124
 125 /**
 126  * A block edge hook: add all cdep edges of block.
 127  */
 128 static int cdep_edge_hook(FILE *F, ir_node *block)
 129 {
 130         ir_cdep *cd;
 131
 132 #if 0
 133         ir_node *pdom = get_Block_ipostdom(block);
 134         if (pdom != NULL) {
 135                 fprintf(
 136                         F,
 137                         "edge:{sourcename:\"n%ld\" targetname:\"n%ld\" color:gold}\n",
 138                         get_irn_node_nr(pdom), get_irn_node_nr(block)
 139                 );
 140         }
 141 #endif
 142
 143         for (cd = find_cdep(block); cd != NULL; cd = cd->next) {
 144                 fprintf(
 145                         F,
 146                         "edge:{sourcename:\"n%ld\" targetname:\"n%ld\" "
 147                         "linestyle:dashed color:gold}\n",
 148                         get_irn_node_nr(block), get_irn_node_nr(cd->node)
 149                 );
 150         }
 151
 152         return 0;
 153 }
 154
 155 /* Compute the control dependence graph for a graph. */
 156 void compute_cdep(ir_graph *irg)
 157 {
 158         ir_node *rem;
 159         cdep_env env;
 160
 161         free_cdep(irg);
 162         cdep_data = XMALLOC(cdep_info);
 163         obstack_init(&cdep_data->obst);
 164
 165         cdep_data->cdep_map = pmap_create();
 166
 167         assure_postdoms(irg);
 168
 169         /* we must temporary change the post dominator relation:
 170            the ipdom of the startblock is the end block.
 171            Firm does NOT add the phantom edge from Start to End.
 172          */
 173         env.start_block = get_irg_start_block(irg);
 174         env.end_block   = get_irg_end_block(irg);
 175
 176         rem = get_Block_ipostdom(env.start_block);
 177         set_Block_ipostdom(env.start_block, env.end_block);
 178
 179         irg_block_walk_graph(irg, cdep_pre, NULL, &env);
 180
 181 #if 0
 182         set_dump_block_edge_hook(cdep_edge_hook);
 183         dump_ir_block_graph(irg, "_cdep");
 184         set_dump_block_edge_hook(NULL);
 185 #else
 186         (void) cdep_edge_hook;
 187 #endif
 188
 189         /* restore the post dominator relation */
 190         set_Block_ipostdom(env.start_block, rem);
 191 }
 192
 193 /* Free the control dependence info. */
 194 void free_cdep(ir_graph *irg)
 195 {
 196         (void) irg;
 197         if (cdep_data != NULL) {
 198                 pmap_destroy(cdep_data->cdep_map);
 199                 obstack_free(&cdep_data->obst, NULL);
 200                 xfree(cdep_data);
 201                 cdep_data = NULL;
 202         }
 203 }
 204
 205 /* Check whether dependee is (directly) control dependent on candidate. */
 206 int is_cdep_on(const ir_node *dependee, const ir_node *candidate)
 207 {
 208         const ir_cdep *dep;
 209
 210         for (dep = find_cdep(dependee); dep != NULL; dep = dep->next) {
 211                 if (dep->node == candidate) return 1;
 212         }
 213         return 0;
 214 }
 215
 216 /* Check whether dependee is (possible iterated) control dependent on candidate. */
 217 int is_iterated_cdep_on(ir_node *dependee, ir_node *candidate)
 218 {
 219         const ir_cdep *dep;
 220
 221         while ((dep = find_cdep(dependee)) != NULL) {
 222                 if (dep->next != NULL) return 0;
 223                 if (dep->node == candidate) return 1;
 224                 dependee = dep->node;
 225         }
 226         return 0;
 227 }
 228
 229 /* If block is control dependent on exactly one node, return this node, else NULL. */
 230 ir_node *get_unique_cdep(const ir_node *block)
 231 {
 232         ir_cdep *cdep = find_cdep(block);
 233
 234         return cdep != NULL && cdep->next == NULL ? cdep->node : NULL;
 235 }
 236
 237 /* Check if the given block is control dependent of more than one node. */
 238 int has_multiple_cdep(const ir_node *block)
 239 {
 240         ir_cdep *cdep = find_cdep(block);
 241
 242         return cdep != NULL && cdep->next != NULL;
 243 }