Prevent SSA construction from running into endless loops.

[libfirm] / ir / ana / cdep.c

diff --git a/ir/ana/cdep.c b/ir/ana/cdep.c
index baea84b..4af268e 100644 (file)
--- a/ir/ana/cdep.c
+++ b/ir/ana/cdep.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
+ * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
  *
  * This file is part of libFirm.
  *
@@ -20,6 +20,7 @@
 /**
  * @file
  * @brief   Implementation of cdep
+ * @author  Christoph Mallon
  * @version $Id$
  */
 #include <assert.h>
@@ -29,29 +30,36 @@
 #include "irgwalk.h"
 #include "irnode.h"
 #include "pmap.h"
+#include "obst.h"
 #include "xmalloc.h"
 #include "cdep.h"
 #include "irprintf.h"
 #include "irdump.h"
 
+typedef struct cdep_info {
+       pmap   *cdep_map;     /**< A map to find the list of all control dependence nodes for a block. */
+       struct obstack obst;  /**< An obstack where all cdep data lives on. */
+} cdep_info;
 
-static pmap *cdep_map;
+static cdep_info *cdep_data;
 
+/* Return a list of all control dependences of a block. */
 ir_cdep *find_cdep(const ir_node *block)
 {
-       return pmap_get(cdep_map, (void *)block);
+       return (ir_cdep*) pmap_get(cdep_data->cdep_map, block);
 }
 
-
+/* Replace the control dependence info of old by the info of nw. */
 void exchange_cdep(ir_node *old, const ir_node *nw)
 {
        ir_cdep *cdep = find_cdep(nw);
-
-       pmap_insert(cdep_map, old, cdep);
+       pmap_insert(cdep_data->cdep_map, old, cdep);
 }
 
-
-static void add_cdep(ir_node* node, ir_node* dep_on)
+/**
+ * Adds a control dependence from node to dep_on.
+ */
+static void add_cdep(ir_node *node, ir_node *dep_on)
 {
        ir_cdep *dep = find_cdep(node);
 #if 0
@@ -59,11 +67,11 @@ static void add_cdep(ir_node* node, ir_node* dep_on)
 #endif
 
        if (dep == NULL) {
-               ir_cdep *newdep = xmalloc(sizeof(*newdep));
+               ir_cdep *newdep = OALLOC(&cdep_data->obst, ir_cdep);
 
                newdep->node = dep_on;
                newdep->next = NULL;
-               pmap_insert(cdep_map, node, newdep);
+               pmap_insert(cdep_data->cdep_map, node, newdep);
        } else {
                ir_cdep *newdep;
 
@@ -72,7 +80,7 @@ static void add_cdep(ir_node* node, ir_node* dep_on)
                        if (dep->next == NULL) break;
                        dep = dep->next;
                }
-               newdep = xmalloc(sizeof(*newdep));
+               newdep = OALLOC(&cdep_data->obst, ir_cdep);
                newdep->node = dep_on;
                newdep->next = NULL;
                dep->next = newdep;
@@ -89,9 +97,8 @@ typedef struct cdep_env {
  */
 static void cdep_pre(ir_node *node, void *ctx)
 {
-       cdep_env *env = ctx;
-       unsigned int n;
-       unsigned int i;
+       cdep_env *env = (cdep_env*) ctx;
+       int i;
 
        /* special case:
         * start and end block have no control dependency
@@ -99,8 +106,7 @@ static void cdep_pre(ir_node *node, void *ctx)
        if (node == env->start_block) return;
        if (node == env->end_block) return;
 
-       n = get_Block_n_cfgpreds(node);
-       for (i = 0; i < n; i++) {
+       for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
                ir_node *pred = get_Block_cfgpred_block(node, i);
                ir_node *pdom;
                ir_node *dependee;
@@ -146,13 +152,17 @@ static int cdep_edge_hook(FILE *F, ir_node *block)
        return 0;
 }
 
-
+/* Compute the control dependence graph for a graph. */
 void compute_cdep(ir_graph *irg)
 {
-       ir_node *start_block, *rem;
+       ir_node *rem;
        cdep_env env;
 
-       cdep_map = pmap_create();
+       free_cdep(irg);
+       cdep_data = XMALLOC(cdep_info);
+       obstack_init(&cdep_data->obst);
+
+       cdep_data->cdep_map = pmap_create();
 
        assure_postdoms(irg);
 
@@ -160,12 +170,12 @@ void compute_cdep(ir_graph *irg)
           the ipdom of the startblock is the end block.
           Firm does NOT add the phantom edge from Start to End.
         */
-       start_block = get_irg_start_block(irg);
-       rem = get_Block_ipostdom(start_block);
-       set_Block_ipostdom(start_block, get_irg_end_block(irg));
-
        env.start_block = get_irg_start_block(irg);
        env.end_block   = get_irg_end_block(irg);
+
+       rem = get_Block_ipostdom(env.start_block);
+       set_Block_ipostdom(env.start_block, env.end_block);
+
        irg_block_walk_graph(irg, cdep_pre, NULL, &env);
 
 #if 0
@@ -177,17 +187,22 @@ void compute_cdep(ir_graph *irg)
 #endif
 
        /* restore the post dominator relation */
-       set_Block_ipostdom(start_block, rem);
+       set_Block_ipostdom(env.start_block, rem);
 }
 
-
+/* Free the control dependence info. */
 void free_cdep(ir_graph *irg)
 {
        (void) irg;
-       // TODO atm leaking more memory than a small memory leaking animal
+       if (cdep_data != NULL) {
+               pmap_destroy(cdep_data->cdep_map);
+               obstack_free(&cdep_data->obst, NULL);
+               xfree(cdep_data);
+               cdep_data = NULL;
+       }
 }
 
-
+/* Check whether dependee is (directly) control dependent on candidate. */
 int is_cdep_on(const ir_node *dependee, const ir_node *candidate)
 {
        const ir_cdep *dep;
@@ -198,7 +213,7 @@ int is_cdep_on(const ir_node *dependee, const ir_node *candidate)
        return 0;
 }
 
-
+/* Check whether dependee is (possible iterated) control dependent on candidate. */
 int is_iterated_cdep_on(ir_node *dependee, ir_node *candidate)
 {
        const ir_cdep *dep;
@@ -211,7 +226,7 @@ int is_iterated_cdep_on(ir_node *dependee, ir_node *candidate)
        return 0;
 }
 
-
+/* If block is control dependent on exactly one node, return this node, else NULL. */
 ir_node *get_unique_cdep(const ir_node *block)
 {
        ir_cdep *cdep = find_cdep(block);
@@ -219,7 +234,7 @@ ir_node *get_unique_cdep(const ir_node *block)
        return cdep != NULL && cdep->next == NULL ? cdep->node : NULL;
 }
 
-
+/* Check if the given block is control dependent of more than one node. */
 int has_multiple_cdep(const ir_node *block)
 {
        ir_cdep *cdep = find_cdep(block);