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