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

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