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 "irgwalk.h"
   9 #include "irdom.h"
  10 #include "domtree.h"
  11
  12
  13 struct _domtree_t {
  14         ir_node *block;
  15         struct _domtree_t *up, *right, *down;
  16 };
  17
  18 struct _dominfo_t {
  19         domtree_t *root;
  20         pmap *b2dom;
  21 };
  22
  23
  24 domtree_t *domtree_find(dominfo_t *dom, ir_node *block) {
  25         assert(is_Block(block));
  26         return (domtree_t *)pmap_find(dom->b2dom, block);
  27 }
  28
  29
  30 static void domtree_insert(dominfo_t *dom, ir_node *idom, ir_node *dominated) {
  31         domtree_t *parent, *child;
  32
  33         parent = domtree_find(dom, idom);
  34         if (!parent) {
  35                 parent = malloc(sizeof(domtree_t));
  36                 parent->block = idom;
  37                 parent->up = parent->right = parent->down = NULL;
  38                 pmap_insert(dom->b2dom, idom, parent);
  39         }
  40
  41         child = domtree_find(dom, dominated);
  42         if (!child) {
  43                 child = malloc(sizeof(domtree_t));
  44                 child->block = dominated;
  45                 child->up = child->right = child->down = NULL;
  46                 pmap_insert(dom->b2dom, dominated, child);
  47         }
  48
  49         child->right = parent->down;
  50         child->up = parent;
  51         parent->down = child;
  52 }
  53
  54
  55 static void block_walker(ir_node *node, void *env) {
  56         ir_node *idom;
  57         if (!is_Block(node))
  58                 return;
  59
  60         idom = get_Block_idom(node);
  61         domtree_insert((dominfo_t *)env, idom, node);
  62 }
  63
  64
  65 dominfo_t *domtree_create(ir_graph *irg) {
  66         dominfo_t *res;
  67         domtree_t *dom;
  68
  69         res = malloc(sizeof(dominfo_t));
  70         res->b2dom = pmap_create();
  71
  72         /* construct domtree */
  73         compute_doms(irg);
  74         irg_walk_graph(irg, block_walker, NULL, res);
  75         free_dom_and_peace(irg);
  76
  77         /* determine root of dom tree and store in dominfo. */
  78         dom = pmap_first(res->b2dom)->value;
  79         while (dom->up)
  80                 dom = dom->up;
  81         res->root = dom;
  82
  83         return res;
  84 }
  85
  86
  87 void domtree_free(dominfo_t *dom) {
  88         pmap_entry *e;
  89
  90         for (e = pmap_first(dom->b2dom); e; e = pmap_next(dom->b2dom))
  91                 free(e->value);
  92
  93         pmap_destroy(dom->b2dom);
  94         free(dom);
  95 }