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