nsz Git - libfirm/blob - ir/be/domtree.c

   1 /**
   2  * @author Daniel Grund
   3  * @date 05.01.2005
   4  */
   5
   6 #include <stdlib.h>
   7
   8 #include "debug.h"
   9 #include "hashptr.h"
  10 #include "set.h"
  11 #include "irprintf_t.h"
  12 #include "irgwalk.h"
  13
  14 #include "irdom.h"
  15 #include "domtree.h"
  16
  17 struct _domtree_t {
  18         ir_node *block;
  19         struct _domtree_t *up, *right, *down;
  20 };
  21
  22 struct _dominfo_t {
  23         domtree_t *root;
  24         set *b2dom;
  25 };
  26
  27
  28 static firm_dbg_module_t *dbg = NULL;
  29
  30
  31 int set_cmp_domtree(const void *x, const void *y, size_t size) {
  32         return ((domtree_t *)x)->block != ((domtree_t *)y)->block;
  33 }
  34
  35
  36 domtree_t *domtree_find(dominfo_t *dom, ir_node *block) {
  37         domtree_t d;
  38         DBG((dbg, 1, "%n\n", block));
  39         assert(is_Block(block));
  40         d.block = block;
  41         return set_find(dom->b2dom, &d, sizeof(d), HASH_PTR(block));
  42 }
  43
  44
  45 static void domtree_insert(dominfo_t *dom, ir_node *idom, ir_node *dominated) {
  46         domtree_t *parent, *child;
  47
  48         DBG((dbg, 1, "%n %n\n", idom, dominated));
  49         parent = domtree_find(dom, idom);
  50         if (!parent) {
  51                 domtree_t d;
  52                 d.block = idom;
  53                 d.up = d.right = d.down = NULL;
  54                 set_insert(dom->b2dom, &d, sizeof(d), HASH_PTR(idom));
  55         }
  56
  57         child = domtree_find(dom, dominated);
  58         if (!child) {
  59                 domtree_t d;
  60                 d.block = dominated;
  61                 d.up = d.right = d.down = NULL;
  62                 set_insert(dom->b2dom, &d, sizeof(d), HASH_PTR(dominated));
  63         }
  64
  65         /* get them (perhaps) again, cause they were _copied_ */
  66         parent = domtree_find(dom, idom);
  67         child = domtree_find(dom, dominated);
  68
  69         child->right = parent->down;
  70         child->up = parent;
  71         parent->down = child;
  72 }
  73
  74
  75 static void block_walker(ir_node *node, void *env) {
  76         ir_node *idom;
  77         if (!is_Block(node))
  78                 return;
  79
  80         idom = get_Block_idom(node);
  81
  82         if (idom)
  83                 domtree_insert((dominfo_t *)env, idom, node);
  84 }
  85
  86
  87 dominfo_t *domtree_create(ir_graph *irg) {
  88         dominfo_t *res;
  89         domtree_t *dom;
  90
  91         dbg = firm_dbg_register("Domtree");
  92         firm_dbg_set_mask(dbg, 1);
  93
  94         DBG((dbg, 1, "\n"));
  95         res = malloc(sizeof(dominfo_t));
  96         res->b2dom = new_set(set_cmp_domtree, 64);
  97
  98         /* construct domtree */
  99         compute_doms(irg);
 100         irg_walk_graph(irg, block_walker, NULL, res);
 101         free_dom_and_peace(irg);
 102
 103         /* determine root of dom tree and store in dominfo. */
 104         dom = set_first(res->b2dom);
 105         set_break(res->b2dom);
 106         while (dom->up)
 107                 dom = dom->up;
 108         res->root = dom;
 109
 110         return res;
 111 }
 112
 113
 114 void domtree_free(dominfo_t *dom) {
 115         DBG((dbg, 1, "\n"));
 116         del_set(dom->b2dom);
 117         free(dom);
 118 }