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* new)
  23 {
  24         cdep* cdep = find_cdep(new);
  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
  59 static void cdep_pre(ir_node* node, void* env)
  60 {
  61   uint n;
  62   uint i;
  63
  64   /* special case:
  65    * start and end block have no control depency
  66    */
  67   if (node == get_irg_start_block(get_irn_irg(node))) return;
  68   if (node == get_irg_end_block(get_irn_irg(node))) return;
  69
  70   n = get_Block_n_cfgpreds(node);
  71   for (i = 0; i < n; i++) {
  72     ir_node* pred = get_Block_cfgpred_block(node, i);
  73     ir_node* pdom;
  74     ir_node* dependee;
  75
  76     if (is_Bad(pred)) continue;
  77
  78     pdom = get_Block_ipostdom(pred);
  79     for (dependee = node; dependee != pdom; dependee = get_Block_ipostdom(dependee)) {
  80       assert(!is_Bad(pdom));
  81       add_cdep(dependee, pred);
  82     }
  83   }
  84 }
  85
  86
  87 #include "irdump.h"
  88
  89
  90 static int cdep_edge_hook(FILE* F, ir_node* block)
  91 {
  92 #if 0
  93         ir_node* pdom;
  94 #endif
  95   cdep* cd;
  96
  97 #if 0
  98         pdom = get_Block_ipostdom(block);
  99         if (pdom != NULL) {
 100                 fprintf(
 101                         F,
 102                         "edge:{sourcename:\"n%ld\" targetname:\"n%ld\" color:gold}\n",
 103                         get_irn_node_nr(pdom), get_irn_node_nr(block)
 104                 );
 105         }
 106 #endif
 107
 108   for (cd = find_cdep(block); cd != NULL; cd = cd->next) {
 109     fprintf(
 110       F,
 111                         "edge:{sourcename:\"n%ld\" targetname:\"n%ld\" "
 112                         "linestyle:dashed color:gold}\n",
 113                         get_irn_node_nr(block), get_irn_node_nr(cd->node)
 114                 );
 115   }
 116
 117         return 0;
 118 }
 119
 120
 121 void compute_cdep(ir_graph* irg)
 122 {
 123   cdep_map = pmap_create();
 124
 125   compute_postdoms(irg);
 126         set_Block_ipostdom(get_irg_start_block(irg), get_irg_end_block(irg));
 127
 128   irg_block_walk_graph(irg, cdep_pre, NULL, NULL);
 129
 130 #if 1
 131         set_dump_block_edge_hook(cdep_edge_hook);
 132   dump_ir_block_graph(irg, "_cdep");
 133         set_dump_block_edge_hook(NULL);
 134 #endif
 135
 136   free_postdom(irg);
 137 }
 138
 139
 140 void free_cdep(ir_graph* irg)
 141 {
 142   // TODO atm leaking more memory than a small memory leaking animal
 143 }
 144
 145
 146 int is_cdep_on(const ir_node* dependee, const ir_node* candidate)
 147 {
 148         const cdep* dep;
 149
 150         for (dep = find_cdep(dependee); dep != NULL; dep = dep->next) {
 151                 if (dep->node == candidate) return 1;
 152         }
 153         return 0;
 154 }
 155
 156
 157 int is_iterated_cdep_on(ir_node* dependee, ir_node* candidate)
 158 {
 159         const cdep* dep;
 160
 161         while ((dep = find_cdep(dependee)) != NULL) {
 162                 if (dep->next != NULL) return 0;
 163                 if (dep->node == candidate) return 1;
 164                 dependee = dep->node;
 165         }
 166         return 0;
 167 }
 168
 169
 170 ir_node* get_unique_cdep(const ir_node* block)
 171 {
 172         cdep* cdep = find_cdep(block);
 173
 174         return cdep != NULL && cdep->next == NULL ? cdep->node : NULL;
 175 }
 176
 177
 178 int has_multiple_cdep(const ir_node* block)
 179 {
 180         cdep* cdep = find_cdep(block);
 181
 182         return cdep != NULL && cdep->next != NULL;
 183 }