+#include "ircons_t.h"
+#include "array_t.h"
+#include "iredges.h"
+
+
+#define get_dom_info(bl) (&(bl)->attr.block.dom)
+#define get_pdom_info(bl) (&(bl)->attr.block.pdom)
+
+/*--------------------------------------------------------------------*/
+/** Accessing the dominator and post dominator data structures **/
+/*--------------------------------------------------------------------*/
+
+ir_node *get_Block_idom(const ir_node *bl)
+{
+ assert(is_Block(bl));
+ if (get_Block_dom_depth(bl) == -1) {
+ /* This block is not reachable from Start */
+ return new_Bad();
+ }
+ return get_dom_info(bl)->idom;
+}
+
+void set_Block_idom(ir_node *bl, ir_node *n)
+{
+ ir_dom_info *bli = get_dom_info(bl);
+
+ assert(is_Block(bl));
+
+ /* Set the immediate dominator of bl to n */
+ bli->idom = n;
+
+ /*
+ * If we don't set the root of the dominator tree
+ * Append bl to the dominates queue of n.
+ */
+ if (n != NULL) {
+ ir_dom_info *ni = get_dom_info(n);
+
+ bli->next = ni->first;
+ ni->first = bl;
+ }
+}
+
+ir_node *get_Block_ipostdom(const ir_node *bl)
+{
+ assert(is_Block(bl));
+ if (get_Block_postdom_depth(bl) == -1) {
+ /* This block is not reachable from Start */
+ return new_Bad();
+ }
+ return get_pdom_info(bl)->idom;
+}
+
+void set_Block_ipostdom(ir_node *bl, ir_node *n)
+{
+ ir_dom_info *bli = get_pdom_info(bl);
+
+ assert(is_Block(bl));
+
+ /* Set the immediate post dominator of bl to n */
+ bli->idom = n;
+
+ /*
+ * If we don't set the root of the post dominator tree
+ * Append bl to the post dominates queue of n.
+ */
+ if (n != NULL) {
+ ir_dom_info *ni = get_pdom_info(n);
+
+ bli->next = ni->first;
+ ni->first = bl;
+ }
+}
+
+int get_Block_dom_pre_num(const ir_node *bl)
+{
+ assert(is_Block(bl));
+ return get_dom_info(bl)->pre_num;
+}
+
+void set_Block_dom_pre_num(ir_node *bl, int num)
+{
+ assert(is_Block(bl));
+ get_dom_info(bl)->pre_num = num;
+}
+
+int get_Block_dom_depth(const ir_node *bl)
+{
+ assert(is_Block(bl));
+ return get_dom_info(bl)->dom_depth;
+}
+
+void set_Block_dom_depth(ir_node *bl, int depth)
+{
+ assert(is_Block(bl));
+ get_dom_info(bl)->dom_depth = depth;
+}
+
+
+int get_Block_postdom_pre_num(const ir_node *bl)
+{
+ assert(is_Block(bl));
+ return get_pdom_info(bl)->pre_num;
+}
+
+void set_Block_postdom_pre_num(ir_node *bl, int num)
+{
+ assert(is_Block(bl));
+ get_pdom_info(bl)->pre_num = num;
+}
+
+int get_Block_postdom_depth(const ir_node *bl)
+{
+ assert(is_Block(bl));
+ return get_pdom_info(bl)->dom_depth;
+}
+
+void set_Block_postdom_depth(ir_node *bl, int depth)
+{
+ assert(is_Block(bl));
+ get_pdom_info(bl)->dom_depth = depth;
+}
+
+unsigned get_Block_dom_tree_pre_num(const ir_node *bl)
+{
+ assert(is_Block(bl));
+ return get_dom_info(bl)->tree_pre_num;
+}
+
+unsigned get_Block_dom_max_subtree_pre_num(const ir_node *bl)
+{
+ assert(is_Block(bl));
+ return get_dom_info(bl)->max_subtree_pre_num;
+}
+
+unsigned get_Block_pdom_tree_pre_num(const ir_node *bl)
+{
+ assert(is_Block(bl));
+ return get_pdom_info(bl)->tree_pre_num;
+}
+
+unsigned get_Block_pdom_max_subtree_pre_num(const ir_node *bl)
+{
+ assert(is_Block(bl));
+ return get_pdom_info(bl)->max_subtree_pre_num;
+}
+
+/* Check, if a block dominates another block. */
+int block_dominates(const ir_node *a, const ir_node *b)
+{
+ const ir_dom_info *ai, *bi;
+
+ if (is_Block(a) && is_Block(b)) {
+ ai = get_dom_info(a);
+ bi = get_dom_info(b);
+ return bi->tree_pre_num - ai->tree_pre_num
+ <= ai->max_subtree_pre_num - ai->tree_pre_num;
+ }
+
+ return 0;
+}
+
+/* Check, if a block strictly dominates another block. */
+int block_strictly_dominates(const ir_node *a, const ir_node *b)
+{
+ return (a != b) && block_dominates(a, b);
+}
+
+/* Returns the smallest common dominator block of two nodes. */
+ir_node *node_smallest_common_dominator(ir_node *a, ir_node *b)
+{
+ ir_node *bl_a = is_Block(a) ? a : get_nodes_block(a);
+ ir_node *bl_b = is_Block(b) ? b : get_nodes_block(b);
+ ir_node *dom_bl = NULL;
+
+ /* Check if block of a dominates block of b */
+ if (block_dominates(bl_a, bl_b))
+ dom_bl = bl_a;
+ /* Check if block of b dominates block of a */
+ else if (block_dominates(bl_b, bl_a))
+ dom_bl = bl_b;
+ else {
+ /* walk up dominator tree and search for first block dominating a and b */
+ while (! dom_bl) {
+ bl_a = get_Block_idom(bl_a);
+
+ assert(! is_Bad(bl_a) && "block is dead?");
+
+ if (block_dominates(bl_a, bl_b))
+ dom_bl = bl_a;
+ }
+ }
+
+ return dom_bl;
+}
+
+/* Returns the smallest common dominator block of all users of a node. */
+ir_node *node_users_smallest_common_dominator(ir_node *irn, int handle_phi)
+{
+ int n, j, i = 0, success;
+ ir_node **user_blocks, *dom_bl;
+ const ir_edge_t *edge;
+
+ assert(! is_Block(irn) && "WRONG USAGE of node_users_smallest_common_dominator");
+ assert(edges_activated(get_irn_irg(irn)) && "need edges activated");
+
+ n = get_irn_n_edges(irn);
+
+ /* get array to hold all block of the node users */
+ NEW_ARR_A(ir_node *, user_blocks, n);
+ foreach_out_edge(irn, edge) {
+ ir_node *src = get_edge_src_irn(edge);
+
+ if (is_Phi(src) && handle_phi) {
+ /* get the corresponding cfg predecessor block if phi handling requested */
+ j = get_edge_src_pos(edge);
+ assert(j >= 0 && "kaputt");
+ user_blocks[i++] = get_Block_cfgpred_block(get_nodes_block(src), j);
+ }
+ else
+ user_blocks[i++] = is_Block(src) ? src : get_nodes_block(src);
+ }
+
+ assert(i == n && "get_irn_n_edges probably broken");
+
+ /* in case of only one user: return the block of the user */
+ if (n == 1)
+ return user_blocks[0];
+
+ i = 0;
+ /* search the smallest block dominating all user blocks */
+ do {
+ dom_bl = node_smallest_common_dominator(user_blocks[i], user_blocks[i + 1]);
+ success = 1;
+
+ /* check if this block dominates all remaining blocks as well */
+ for (j = i + 2; j < n; j++) {
+ if (! block_dominates(dom_bl, user_blocks[j]))
+ success = 0;
+ }
+
+ if (success)
+ break;
+
+ /* inherit the dominator block of the first (i + 1) users */
+ user_blocks[++i] = dom_bl;
+ } while (i < n - 1);
+
+ assert(success && "no block found dominating all users");
+
+ return dom_bl;
+}