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