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  */
  25 #include <assert.h>
  26 #include <stdlib.h>
  27 #include "irdom.h"
  28 #include "irgraph.h"
  29 #include "irgwalk.h"
  30 #include "irnode.h"
  31 #include "pmap.h"
  32 #include "obst.h"
  33 #include "xmalloc.h"
  34 #include "cdep_t.h"
  35 #include "irprintf.h"
  36 #include "irdump.h"
  37
  38 typedef struct cdep_info {
  39         pmap   *cdep_map;     /**< A map to find the list of all control dependence nodes for a block. */
  40         struct obstack obst;  /**< An obstack where all cdep data lives on. */
  41 } cdep_info;
  42
  43 static cdep_info *cdep_data;
  44
  45 ir_node *(get_cdep_node)(const ir_cdep *cdep)
  46 {
  47         return _get_cdep_node(cdep);
  48 }
  49
  50 ir_cdep *(get_cdep_next)(const ir_cdep *cdep)
  51 {
  52         return _get_cdep_next(cdep);
  53 }
  54
  55 /* Return a list of all control dependences of a block. */
  56 ir_cdep *find_cdep(const ir_node *block)
  57 {
  58         assert(is_Block(block));
  59         return (ir_cdep*) pmap_get(cdep_data->cdep_map, block);
  60 }
  61
  62 void exchange_cdep(ir_node *old, const ir_node *nw)
  63 {
  64         ir_cdep *cdep = find_cdep(nw);
  65         assert(is_Block(old));
  66         pmap_insert(cdep_data->cdep_map, old, cdep);
  67 }
  68
  69 /**
  70  * Adds a control dependence from node to dep_on.
  71  */
  72 static void add_cdep(ir_node *node, ir_node *dep_on)
  73 {
  74         ir_cdep *dep = find_cdep(node);
  75
  76         assert(is_Block(dep_on));
  77         if (dep == NULL) {
  78                 ir_cdep *newdep = OALLOC(&cdep_data->obst, ir_cdep);
  79
  80                 newdep->node = dep_on;
  81                 newdep->next = NULL;
  82                 pmap_insert(cdep_data->cdep_map, node, newdep);
  83         } else {
  84                 ir_cdep *newdep;
  85
  86                 for (;;) {
  87                         if (get_cdep_node(dep) == dep_on) return;
  88                         if (dep->next == NULL) break;
  89                         dep = dep->next;
  90                 }
  91                 newdep = OALLOC(&cdep_data->obst, ir_cdep);
  92                 newdep->node = dep_on;
  93                 newdep->next = NULL;
  94                 dep->next = newdep;
  95         }
  96 }
  97
  98 typedef struct cdep_env {
  99         ir_node *start_block;
 100         ir_node *end_block;
 101 } cdep_env;
 102
 103 /**
 104  * Pre-block-walker: calculate the control dependence
 105  */
 106 static void cdep_pre(ir_node *node, void *ctx)
 107 {
 108         cdep_env *env = (cdep_env*) ctx;
 109         int i;
 110
 111         /* special case:
 112          * start and end block have no control dependency
 113          */
 114         if (node == env->start_block) return;
 115         if (node == env->end_block) return;
 116
 117         for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
 118                 ir_node *pred = get_Block_cfgpred_block(node, i);
 119                 ir_node *pdom;
 120                 ir_node *dependee;
 121
 122                 if (is_Bad(pred)) continue;
 123
 124                 pdom = get_Block_ipostdom(pred);
 125                 for (dependee = node; dependee != pdom; dependee = get_Block_ipostdom(dependee)) {
 126                         assert(!is_Bad(pdom));
 127                         add_cdep(dependee, pred);
 128                 }
 129         }
 130 }
 131
 132
 133 /**
 134  * A block edge hook: add all cdep edges of block.
 135  */
 136 static int cdep_edge_hook(FILE *F, ir_node *block)
 137 {
 138         ir_cdep *cd;
 139
 140         for (cd = find_cdep(block); cd != NULL; cd = cd->next) {
 141                 fprintf(
 142                         F,
 143                         "edge:{sourcename:\"n%ld\" targetname:\"n%ld\" "
 144                         "linestyle:dashed color:gold}\n",
 145                         get_irn_node_nr(block), get_irn_node_nr(cd->node)
 146                 );
 147         }
 148
 149         return 0;
 150 }
 151
 152 void compute_cdep(ir_graph *irg)
 153 {
 154         ir_node *rem;
 155         cdep_env env;
 156
 157         free_cdep(irg);
 158         cdep_data = XMALLOC(cdep_info);
 159         obstack_init(&cdep_data->obst);
 160
 161         cdep_data->cdep_map = pmap_create();
 162
 163         assure_postdoms(irg);
 164
 165         /* we must temporary change the post dominator relation:
 166            the ipdom of the startblock is the end block.
 167            Firm does NOT add the phantom edge from Start to End.
 168          */
 169         env.start_block = get_irg_start_block(irg);
 170         env.end_block   = get_irg_end_block(irg);
 171
 172         rem = get_Block_ipostdom(env.start_block);
 173         set_Block_ipostdom(env.start_block, env.end_block);
 174
 175         irg_block_walk_graph(irg, cdep_pre, NULL, &env);
 176
 177 #if 0
 178         set_dump_block_edge_hook(cdep_edge_hook);
 179         dump_ir_block_graph(irg, "_cdep");
 180         set_dump_block_edge_hook(NULL);
 181 #else
 182         (void) cdep_edge_hook;
 183 #endif
 184
 185         /* restore the post dominator relation */
 186         set_Block_ipostdom(env.start_block, rem);
 187 }
 188
 189 void free_cdep(ir_graph *irg)
 190 {
 191         (void) irg;
 192         if (cdep_data != NULL) {
 193                 pmap_destroy(cdep_data->cdep_map);
 194                 obstack_free(&cdep_data->obst, NULL);
 195                 xfree(cdep_data);
 196                 cdep_data = NULL;
 197         }
 198 }
 199
 200 int is_cdep_on(const ir_node *dependee, const ir_node *candidate)
 201 {
 202         const ir_cdep *dep;
 203
 204         for (dep = find_cdep(dependee); dep != NULL; dep = dep->next) {
 205                 if (get_cdep_node(dep) == candidate) return 1;
 206         }
 207         return 0;
 208 }
 209
 210 ir_node *get_unique_cdep(const ir_node *block)
 211 {
 212         ir_cdep *cdep = find_cdep(block);
 213
 214         return cdep != NULL && cdep->next == NULL ? get_cdep_node(cdep) : NULL;
 215 }
 216
 217 int has_multiple_cdep(const ir_node *block)
 218 {
 219         ir_cdep *cdep = find_cdep(block);
 220
 221         return cdep != NULL && cdep->next != NULL;
 222 }