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

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