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 static pmap *cdep_map;
  13
  14 cdep *find_cdep(const ir_node *block)
  15 {
  16         return pmap_get(cdep_map, (void *)block);
  17 }
  18
  19
  20 void exchange_cdep(ir_node *old, const ir_node *nw)
  21 {
  22         cdep *cdep = find_cdep(nw);
  23
  24         pmap_insert(cdep_map, old, cdep);
  25 }
  26
  27
  28 static void add_cdep(ir_node* node, ir_node* dep_on)
  29 {
  30         cdep *dep = find_cdep(node);
  31 #if 0
  32         ir_fprintf(stderr, "Adding cdep of %+F on %+F\n", node, dep_on);
  33 #endif
  34
  35         if (dep == NULL) {
  36                 cdep *newdep = xmalloc(sizeof(*newdep));
  37
  38                 newdep->node = dep_on;
  39                 newdep->next = NULL;
  40                 pmap_insert(cdep_map, node, newdep);
  41         } else {
  42                 cdep *newdep;
  43
  44                 for (;;) {
  45                         if (dep->node == dep_on) return;
  46                         if (dep->next == NULL) break;
  47                         dep = dep->next;
  48                 }
  49                 newdep = xmalloc(sizeof(*newdep));
  50                 newdep->node = dep_on;
  51                 newdep->next = NULL;
  52                 dep->next = newdep;
  53         }
  54 }
  55
  56 typedef struct cdep_env {
  57         ir_node *start_block;
  58         ir_node *end_block;
  59 } cdep_env;
  60
  61 /**
  62  * Pre-block-walker: calculate the control dependence
  63  */
  64 static void cdep_pre(ir_node *node, void *ctx)
  65 {
  66         cdep_env *env = ctx;
  67         unsigned int n;
  68         unsigned int i;
  69
  70         /* special case:
  71          * start and end block have no control dependency
  72          */
  73         if (node == env->start_block) return;
  74         if (node == env->end_block) return;
  75
  76         n = get_Block_n_cfgpreds(node);
  77         for (i = 0; i < n; i++) {
  78                 ir_node *pred = get_Block_cfgpred_block(node, i);
  79                 ir_node *pdom;
  80                 ir_node *dependee;
  81
  82                 if (is_Bad(pred)) continue;
  83
  84                 pdom = get_Block_ipostdom(pred);
  85                 for (dependee = node; dependee != pdom; dependee = get_Block_ipostdom(dependee)) {
  86                         assert(!is_Bad(pdom));
  87                         add_cdep(dependee, pred);
  88                 }
  89         }
  90 }
  91
  92
  93 #include "irdump.h"
  94
  95 /**
  96  * A block edge hook: add all cdep edges of block.
  97  */
  98 static int cdep_edge_hook(FILE *F, ir_node *block)
  99 {
 100         cdep *cd;
 101
 102 #if 0
 103         ir_node *pdom = get_Block_ipostdom(block);
 104         if (pdom != NULL) {
 105                 fprintf(
 106                         F,
 107                         "edge:{sourcename:\"n%ld\" targetname:\"n%ld\" color:gold}\n",
 108                         get_irn_node_nr(pdom), get_irn_node_nr(block)
 109                 );
 110         }
 111 #endif
 112
 113         for (cd = find_cdep(block); cd != NULL; cd = cd->next) {
 114                 fprintf(
 115                         F,
 116                         "edge:{sourcename:\"n%ld\" targetname:\"n%ld\" "
 117                         "linestyle:dashed color:gold}\n",
 118                         get_irn_node_nr(block), get_irn_node_nr(cd->node)
 119                 );
 120         }
 121
 122         return 0;
 123 }
 124
 125
 126 void compute_cdep(ir_graph *irg)
 127 {
 128         ir_node *start_block, *rem;
 129         cdep_env env;
 130
 131         cdep_map = pmap_create();
 132
 133         assure_postdoms(irg);
 134
 135         /* we must temporary change the post dominator relation */
 136         start_block = get_irg_start_block(irg);
 137         rem = get_Block_ipostdom(start_block);
 138         set_Block_ipostdom(start_block, get_irg_end_block(irg));
 139
 140         env.start_block = get_irg_start_block(irg);
 141         env.end_block   = get_irg_end_block(irg);
 142         irg_block_walk_graph(irg, cdep_pre, NULL, &env);
 143
 144 #if 0
 145         set_dump_block_edge_hook(cdep_edge_hook);
 146         dump_ir_block_graph(irg, "_cdep");
 147         set_dump_block_edge_hook(NULL);
 148 #else
 149         (void) cdep_edge_hook;
 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 }