X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fstructure.c;h=cf554445b23c9219dd4787989e1e402a57b8f9fa;hb=d5d7159c209a9e5c5fa276f770b5b28a217990a8;hp=b59a4c1d13f9319165f0b12f3d1d1dc237cef553;hpb=cad5a73c70accbe9a0807ddec67e94d3ba799984;p=libfirm

diff --git a/ir/ana/structure.c b/ir/ana/structure.c
index b59a4c1d1..cf554445b 100644
--- a/ir/ana/structure.c
+++ b/ir/ana/structure.c
@@ -1,17 +1,32 @@
 /*
- * Project:     libFIRM
- * File name:   ir/ana/structure.c
- * Purpose:     Structure Analysis
- * Author:      Michael Beck
- * Modified by:
- * Created:     5.4.2007
- * CVS-ID:      $Id: $
- * Copyright:   (c) 2007 Universität Karlsruhe
- * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
- */
-#ifdef HAVE_CONFIG_H
+ * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
+ *
+ * This file is part of libFirm.
+ *
+ * This file may be distributed and/or modified under the terms of the
+ * GNU General Public License version 2 as published by the Free Software
+ * Foundation and appearing in the file LICENSE.GPL included in the
+ * packaging of this file.
+ *
+ * Licensees holding valid libFirm Professional Edition licenses may use
+ * this file in accordance with the libFirm Commercial License.
+ * Agreement provided with the Software.
+ *
+ * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+ * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE.
+ */
+
+/**
+ * @file
+ * @brief    Structure Analysis
+ * @author   Michael Beck
+ * @date     5.4.2007
+ * @version  $Id$
+ */
 #include "config.h"
-#endif
+
+#include <stdbool.h>
 
 #include "firm_common.h"
 #include "irnode_t.h"
@@ -21,7 +36,7 @@
 #include "irtools.h"
 #include "irgwalk.h"
 #include "array.h"
-#include "irphase_t.h"
+#include "irdump.h"
 
 #include "debug.h"
 
@@ -36,17 +51,19 @@ struct ir_reg_tree {
 
 /* A region. */
 struct ir_region {
-	firm_kind      kind;    /**< Must be k_ir_region. */
-	ir_region_kind type;    /**< The type of this region. */
-	ir_region      *parent; /**< points to the parent. */
-	ir_reg_or_blk  *parts;  /**< The list of all region parts. */
-	ir_region      **pred;  /**< The predecessor (control flow) regions of this region. */
-	ir_region      **succ;  /**< The successor (control flow) regions of this region. */
-	unsigned       prenum;  /**< DFS pre-oder number */
-	unsigned       postnum; /**< DFS post-oder number */
-	void           *link;   /**< A link field. */
-	unsigned long  nr;      /**< for debugging */
-	char           visited; /**< The visited flag. */
+	firm_kind      kind;      /**< Must be k_ir_region. */
+	ir_region_kind type;      /**< The type of this region. */
+	ir_region      *parent;   /**< points to the parent. */
+	ir_reg_or_blk  *parts;    /**< The list of all region parts. */
+	ir_region      **pred;    /**< The predecessor (control flow) regions of this region. */
+	ir_region      **succ;    /**< The successor (control flow) regions of this region. */
+	size_t         prenum;    /**< DFS pre-oder number */
+	size_t         postnum;   /**< DFS post-oder number */
+	void           *link;     /**< A link field. */
+	unsigned long  nr;        /**< for debugging */
+	unsigned       visited:1; /**< The visited flag. */
+	unsigned       exit:1;    /**< If set, the parent region can be left by this node. */
+	unsigned       enter:1;   /**< If set, the parent region can be entered by this node. */
 };
 
 /* A helper type for unioning blocks and regions. */
@@ -57,98 +74,110 @@ union ir_reg_or_blk {
 };
 
 /* The debug handle. */
-DEBUG_ONLY(firm_dbg_module_t *dbg;)
+DEBUG_ONLY(static firm_dbg_module_t *dbg;)
 
 /**
  * Returns the link of a region.
  */
-void *get_region_link(const ir_region *reg) {
+void *get_region_link(const ir_region *reg)
+{
 	return reg->link;
 }
 
 /**
  * Sets the link of a region.
  */
-void set_region_link(ir_region *reg, void *data) {
+void set_region_link(ir_region *reg, void *data)
+{
 	reg->link = data;
 }
 
 /**
  * Get the immediate region of a block.
  */
-ir_region *get_block_region(const ir_node *block) {
+ir_region *get_block_region(const ir_node *block)
+{
 	assert(is_Block(block));
-	return get_irn_link(block);
+	return block->attr.block.region;
 }
 
 /**
  * Sets the immediate region of a block.
  */
-void set_block_region(ir_node *block, ir_region *reg) {
+void set_block_region(ir_node *block, ir_region *reg)
+{
 	assert(is_Block(block));
-	set_irn_link(block, reg);
+	block->attr.block.region = reg;
 }
 
 /**
  * Get the immediate region of a node.
  */
-ir_region *get_irn_region(ir_node *n) {
-	if (is_no_Block(n))
+ir_region *get_irn_region(ir_node *n)
+{
+	if (!is_Block(n))
 		n = get_nodes_block(n);
 	return get_block_region(n);
 }
 
 /**
- * Return non-if a given firm thing is a region.
+ * Return non-zero if a given firm thing is a region.
  */
-int is_region(const void *thing) {
-	const firm_kind *kind = thing;
+int is_region(const void *thing)
+{
+	const firm_kind *kind = (const firm_kind*) thing;
 	return *kind == k_ir_region;
 }
 
 /**
- * Return the number of predecessors in a region.
+ * Return the number of predecessors of a region.
  */
-int get_region_n_preds(const ir_region *reg) {
+size_t get_region_n_preds(const ir_region *reg)
+{
 	return ARR_LEN(reg->pred);
 }
 
 /**
  * Return the predecessor region at position pos.
  */
-ir_region *get_region_pred(const ir_region *reg, int pos) {
-	assert(0 <= pos && pos <= get_region_n_preds(reg));
+ir_region *get_region_pred(const ir_region *reg, size_t pos)
+{
+	assert(pos <= get_region_n_preds(reg));
 	return reg->pred[pos];
 }
 
 /**
  * Set the predecessor region at position pos.
  */
-void set_region_pred(ir_region *reg, int pos, ir_region *n) {
-	assert(0 <= pos && pos <= get_region_n_preds(reg));
+void set_region_pred(ir_region *reg, size_t pos, ir_region *n)
+{
+	assert(pos <= get_region_n_preds(reg));
 	reg->pred[pos] = n;
 }
 
 /**
  * Return the number of successors in a region.
  */
-int get_region_n_succs(const ir_region *reg) {
+size_t get_region_n_succs(const ir_region *reg)
+{
 	return ARR_LEN(reg->succ);
 }
 
 /**
  * Return the successor region at position pos.
  */
-ir_region *get_region_succ(const ir_region *reg, int pos) {
-	assert(0 <= pos && pos <= get_region_n_succs(reg));
+ir_region *get_region_succ(const ir_region *reg, size_t pos)
+{
+	assert(pos <= get_region_n_succs(reg));
 	return reg->succ[pos];
 }
 
 /**
  * Set the successor region at position pos.
  */
-void set_region_succ(ir_region *reg, int pos, ir_region *n) {
-	assert(0 <= pos && pos <= get_region_n_succs(reg));
+void set_region_succ(ir_region *reg, size_t pos, ir_region *n)
+{
+	assert(pos <= get_region_n_succs(reg));
 	reg->succ[pos] = n;
 }
 
@@ -156,21 +185,22 @@ void set_region_succ(ir_region *reg, int pos, ir_region *n) {
 
 /** Walker environment. */
 typedef struct walk_env {
-	struct obstack *obst;  /**< an obstack to allocate from. */
+	struct obstack *obst;  /**< An obstack to allocate from. */
 	ir_region **post;      /**< The list of all currently existent top regions. */
-	unsigned l_post;       /**< length of the allocated regions array. */
-	unsigned premax;       /**< maximum pre counter */
-	unsigned postmax;      /**< maximum post counter */
-	ir_node *start_block;  /**< the start block of the graph. */
-	ir_node *end_block;    /**< the end block of the graph. */
+	size_t l_post;         /**< The length of the allocated regions array. */
+	size_t premax;         /**< maximum pre counter */
+	size_t postmax;        /**< maximum post counter */
+	ir_node *start_block;  /**< The start block of the graph. */
+	ir_node *end_block;    /**< The end block of the graph. */
 } walk_env;
 
 /**
  * Do a DFS search on the initial regions, assign a prenum and a postnum to every
  * node and store the region nodes into the post array.
  */
-static void dfs_walk2(ir_region *reg, walk_env *env) {
-	int i, n;
+static void dfs_walk2(ir_region *reg, walk_env *env)
+{
+	size_t i, n;
 
 	if (reg->visited == 0) {
 		reg->visited = 1;
@@ -191,12 +221,13 @@ static void dfs_walk2(ir_region *reg, walk_env *env) {
  * Do a DFS search on the initial regions, assign a prenum and a postnum to every
  * node and store the region nodes into the post array.
  */
-static void dfs_walk(ir_graph *irg, walk_env *env) {
+static void dfs_walk(ir_graph *irg, walk_env *env)
+{
 	ir_graph *rem = current_ir_graph;
 	ir_region *reg;
 
 	current_ir_graph = irg;
-	reg              = get_irn_link(get_irg_start_block(irg));
+	reg              = (ir_region*) get_irn_link(get_irg_start_block(irg));
 
 	env->premax  = 0;
 	env->postmax = 0;
@@ -205,21 +236,24 @@ static void dfs_walk(ir_graph *irg, walk_env *env) {
 }
 
 /**
- * Post-walker: wrap all blocks with a Block region
+ * Post-walker: wrap all blocks with a BasicBlock region
  * and count them
  */
-static void wrap_blocks(ir_node *block, void *ctx) {
-	walk_env *env = ctx;
+static void wrap_BasicBlocks(ir_node *block, void *ctx)
+{
+	walk_env *env = (walk_env*) ctx;
 	ir_region *reg;
 
 	/* Allocate a Block wrapper */
-	reg          = obstack_alloc(env->obst, sizeof(*reg));
+	reg          = OALLOC(env->obst, ir_region);
 	reg->kind    = k_ir_region;
-	reg->type    = ir_rk_Block;
+	reg->type    = ir_rk_BasicBlock;
 	reg->parent  = NULL;
 	reg->prenum  = 0;
 	reg->postnum = 0;
 	reg->visited = 0;
+	reg->exit    = 0;
+	reg->enter   = 0;
 	reg->link    = NULL;
 	reg->nr      = get_irn_node_nr(block);
 	reg->parts   = NEW_ARR_D(ir_reg_or_blk, env->obst, 1);
@@ -228,75 +262,88 @@ static void wrap_blocks(ir_node *block, void *ctx) {
 	set_irn_link(block, reg);
 
 	++env->l_post;
-}  /* wrap_blocks */
+}  /* wrap_BasicBlocks */
 
 /**
- * Create the pred and succ edges for Block wrapper.
+ * Post-walker: Create the pred and succ edges for Block wrapper.
  * Kill edges to the Start and End blocks.
  */
-static void update_Block_regions(ir_node *blk, void *ctx) {
-	walk_env *env = ctx;
-	ir_region *reg = get_irn_link(blk);
-	int i, j, len;
+static void update_BasicBlock_regions(ir_node *blk, void *ctx)
+{
+	walk_env *env = (walk_env*) ctx;
+	ir_region *reg = (ir_region*) get_irn_link(blk);
+	int i, len;
+	size_t j;
 
 	if (blk == env->start_block) {
-		/* handle Firm's self loop */
+		/* handle Firm's self loop: Start block has no predecessors */
 		reg->pred = NEW_ARR_D(ir_region *, env->obst, 0);
 	} else {
 		len = get_Block_n_cfgpreds(blk);
 		reg->pred = NEW_ARR_D(ir_region *, env->obst, len);
-		for (i = j = 0; i < len; ++i) {
+		for (j = i = 0; i < len; ++i) {
 			ir_node *pred = get_Block_cfgpred_block(blk, i);
-			reg->pred[j++] = get_irn_link(pred);
+			reg->pred[j++] = (ir_region*) get_irn_link(pred);
 		}
 		ARR_SHRINKLEN(reg->pred, j);
 	}
 
 	len = get_Block_n_cfg_outs(blk);
 	reg->succ = NEW_ARR_D(ir_region *, env->obst, len);
-	for (i = j = 0; i < len; ++i) {
+	for (j = i = 0; i < len; ++i) {
 		ir_node *succ = get_Block_cfg_out(blk, i);
-		reg->succ[j++] = get_irn_link(succ);
+		reg->succ[j++] = (ir_region*) get_irn_link(succ);
 	}
 	ARR_SHRINKLEN(reg->succ, j);
-}
+}  /* update_BasicBlock_regions */
 
-/** Allocate a new region of a obstack */
-#define ALLOC_REG(obst, reg, tp) \
-	do { \
-		(reg)          = obstack_alloc((obst), sizeof(*(reg))); \
-		(reg)->kind    = k_ir_region; \
-		(reg)->type    = tp; \
-		(reg)->parent  = NULL; \
-		(reg)->prenum  = 0; \
-		(reg)->postnum = 0; \
-		(reg)->visited = 0; \
-		(reg)->link    = NULL; \
-	} while (0)
+/** Allocate a new region on an obstack */
+static ir_region *alloc_region(struct obstack *obst, ir_region_kind type)
+{
+	ir_region *reg = OALLOC(obst, ir_region);
+	reg->kind    = k_ir_region;
+	reg->type    = type;
+	reg->parent  = NULL;
+	reg->prenum  = 0;
+	reg->postnum = 0;
+	reg->visited = 0;
+	reg->exit    = 0;
+	reg->enter   = 0;
+	reg->link    = NULL;
+
+	return reg;
+}  /* alloc_region */
 
 /**
  * Creates a new Sequence region.
  */
-static ir_region *new_Sequence(struct obstack *obst, ir_region *nset[]) {
-	ir_region *reg;
-	int i, len = ARR_LEN(nset);
-
-	ALLOC_REG(obst, reg, ir_rk_Sequence);
-
-	reg->nr    = nset[0]->nr;
-	reg->parts = CLONE_ARR_D(ir_reg_or_blk, obst, nset);
-	reg->pred  = DUP_ARR_D(ir_region *, obst, nset[0]->pred);
-	reg->succ  = DUP_ARR_D(ir_region *, obst, nset[len - 1]->succ);
-
-	for (i = 0; i < len; ++i) {
-		reg->parts[i].region = nset[i];
-		nset[i]->parent = reg;
+static ir_region *new_Sequence(struct obstack *obst, ir_region *nset, size_t nset_len)
+{
+	ir_region *reg  = alloc_region(obst, ir_rk_Sequence);
+	ir_region *next;
+	size_t    i;
+
+	reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, nset_len);
+
+	/* beware: list is in reverse order, reverse */
+	next = nset;
+	for (i = nset_len; i > 0;) {
+		--i;
+		nset = next;
+		reg->parts[i].region = nset;
+		nset->parent = reg;
+		next = (ir_region*) nset->link;
+		nset->link = NULL;
 	}
 
+	reg->nr   = reg->parts[0].region->nr;
+	reg->pred = DUP_ARR_D(ir_region *, obst, reg->parts[0].region->pred);
+	reg->succ = DUP_ARR_D(ir_region *, obst, reg->parts[nset_len - 1].region->succ);
+
 	DEBUG_ONLY(
 		DB((dbg, LEVEL_2, " Created Sequence "));
-		for (i = 0; i < len; ++i) {
-			DB((dbg, LEVEL_2, "(%u)", reg->parts[i].region->nr));
+		for (i = 0; i < nset_len; ++i) {
+			DB((dbg, LEVEL_2, "(%lu)", reg->parts[i].region->nr));
 		}
 		DB((dbg, LEVEL_2, "\n"));
 	)
@@ -306,10 +353,9 @@ static ir_region *new_Sequence(struct obstack *obst, ir_region *nset[]) {
 /**
  * Create a new IfThenElse region.
  */
-static ir_region *new_IfThenElse(struct obstack *obst, ir_region *if_b, ir_region *then_b, ir_region *else_b) {
-	ir_region *reg;
-
-	ALLOC_REG(obst, reg, ir_rk_IfThenElse);
+static ir_region *new_IfThenElse(struct obstack *obst, ir_region *if_b, ir_region *then_b, ir_region *else_b)
+{
+	ir_region *reg = alloc_region(obst, ir_rk_IfThenElse);
 
 	reg->nr    = if_b->nr;
 	reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 3);
@@ -321,7 +367,7 @@ static ir_region *new_IfThenElse(struct obstack *obst, ir_region *if_b, ir_regio
 	reg->pred = DUP_ARR_D(ir_region *, obst, if_b->pred);
 	reg->succ = DUP_ARR_D(ir_region *, obst, then_b->succ);
 
-	DB((dbg, LEVEL_2, " Created If(%u)Then(%u)Else(%u)\n", reg->nr, then_b->nr, else_b->nr));
+	DB((dbg, LEVEL_2, " Created If(%lu)Then(%lu)Else(%lu)\n", reg->nr, then_b->nr, else_b->nr));
 
 	return reg;
 }  /* new_IfThenElse */
@@ -329,10 +375,9 @@ static ir_region *new_IfThenElse(struct obstack *obst, ir_region *if_b, ir_regio
 /**
  * Create a new IfThen region.
  */
-static ir_region *new_IfThen(struct obstack *obst, ir_region *if_b, ir_region *then_b) {
-	ir_region *reg;
-
-	ALLOC_REG(obst, reg, ir_rk_IfThen);
+static ir_region *new_IfThen(struct obstack *obst, ir_region *if_b, ir_region *then_b)
+{
+	ir_region *reg = alloc_region(obst, ir_rk_IfThen);
 
 	reg->nr    = if_b->nr;
 	reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 2);
@@ -343,7 +388,7 @@ static ir_region *new_IfThen(struct obstack *obst, ir_region *if_b, ir_region *t
 	reg->pred = DUP_ARR_D(ir_region *, obst, if_b->pred);
 	reg->succ = DUP_ARR_D(ir_region *, obst, then_b->succ);
 
-	DB((dbg, LEVEL_2, " Created If(%u)Then(%u)\n", reg->nr, then_b->nr));
+	DB((dbg, LEVEL_2, " Created If(%lu)Then(%lu)\n", reg->nr, then_b->nr));
 
 	return reg;
 }  /* new_IfThenElse */
@@ -351,43 +396,62 @@ static ir_region *new_IfThen(struct obstack *obst, ir_region *if_b, ir_region *t
 /**
  * Create a new Switch/case region.
  */
-static ir_region *new_SwitchCase(struct obstack *obst, ir_region_kind type, ir_region *head, ir_region *end, pset *cases) {
-	ir_region *reg, *c;
-	int i;
-
-	ALLOC_REG(obst, reg, type);
+static ir_region *new_SwitchCase(struct obstack *obst, ir_region_kind type, ir_region *head, ir_region *exit,
+                                 ir_region *cases, size_t cases_len)
+{
+	ir_region *reg = alloc_region(obst, type);
+	ir_region *c, *n;
+	int       add = 1;
+	size_t    i;
+
+	/* check, if the exit block is in the list */
+	for (c = cases; c != NULL; c = (ir_region*) c->link) {
+		if (c == exit) {
+			add = 0;
+			break;
+		}
+	}
 
 	reg->nr    = head->nr;
-	reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, pset_count(cases) + 1);
+	reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, cases_len + add);
 
 	reg->parts[0].region = head; head->parent = reg;
-	i = 0;
-	foreach_pset(cases, c) {
-		reg->parts[i].region = c;
-		c->parent = reg;
+	i = 1;
+	for (c = cases; c != NULL; c = n) {
+		n = (ir_region*) c->link;
+		if (c != exit) {
+			reg->parts[i++].region = c;
+			c->parent = reg;
+		}
+		c->link = NULL;
 	}
 
 	reg->pred = DUP_ARR_D(ir_region *, obst, head->pred);
 	reg->succ = NEW_ARR_D(ir_region *, obst, 1);
-	reg->succ[0] = end;
+	reg->succ[0] = exit;
 
-	DB((dbg, LEVEL_2, " Created Switch(%u)Exit(%u)\n", reg->nr, end->nr));
-
-	del_pset(cases);
+	DEBUG_ONLY({
+		size_t i;
+		DB((dbg, LEVEL_2, " Created %s(%u)\n", reg->type == ir_rk_Switch ? "Switch" : "Case", reg->nr));
+		for (i = 1; i < ARR_LEN(reg->parts); ++i) {
+			DB((dbg, LEVEL_2, "  Case(%lu)\n", reg->parts[i].region->nr));
+		}
+		DB((dbg, LEVEL_2, "  Exit(%lu)\n", exit->nr));
+	})
 	return reg;
 }  /* new_SwitchCase */
 
 /**
  * Create a new SelfLoop region.
  */
-static ir_region *new_SelfLoop(struct obstack *obst, ir_region *head) {
-	ir_region *reg, *succ;
-	int i, j, len;
+static ir_region *new_SelfLoop(struct obstack *obst, ir_region *head)
+{
+	ir_region *reg = alloc_region(obst, ir_rk_SelfLoop);
+	ir_region *succ;
+	size_t i, j, len;
 
-	ALLOC_REG(obst, reg, ir_rk_SelfLoop);
-
-	reg->nr      = head->nr;
-	reg->parts   = NEW_ARR_D(ir_reg_or_blk, obst, 1);
+	reg->nr    = head->nr;
+	reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 1);
 
 	reg->parts[0].region = head; head->parent = reg;
 
@@ -409,7 +473,7 @@ static ir_region *new_SelfLoop(struct obstack *obst, ir_region *head) {
 	else
 		reg->succ[0] = get_region_succ(head, 1);
 
-	DB((dbg, LEVEL_2, " Created SelfLoop(%u)\n", reg->nr));
+	DB((dbg, LEVEL_2, " Created SelfLoop(%lu)\n", reg->nr));
 
 	return reg;
 }  /* new_SelfLoop */
@@ -417,13 +481,13 @@ static ir_region *new_SelfLoop(struct obstack *obst, ir_region *head) {
 /**
  * Create a new RepeatLoop region.
  */
-static ir_region *new_RepeatLoop(struct obstack *obst, ir_region *head, ir_region *body) {
-	ir_region *reg, *succ;
+static ir_region *new_RepeatLoop(struct obstack *obst, ir_region *head, ir_region *body)
+{
+	ir_region *reg = alloc_region(obst, ir_rk_RepeatLoop);
+	ir_region *succ;
 
-	ALLOC_REG(obst, reg, ir_rk_RepeatLoop);
-
-	reg->nr      = head->nr;
-	reg->parts   = NEW_ARR_D(ir_reg_or_blk, obst, 2);
+	reg->nr    = head->nr;
+	reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 2);
 
 	reg->parts[0].region = head; head->parent = reg;
 	reg->parts[1].region = body; body->parent = reg;
@@ -438,7 +502,7 @@ static ir_region *new_RepeatLoop(struct obstack *obst, ir_region *head, ir_regio
 	else
 		reg->succ[0] = get_region_succ(body, 1);
 
-	DB((dbg, LEVEL_2, " Created RepeatLoop(%u)Body(%u)\n", reg->nr, body->nr));
+	DB((dbg, LEVEL_2, " Created RepeatLoop(%lu)Body(%lu)\n", reg->nr, body->nr));
 
 	return reg;
 }  /* new_RepeatLoop */
@@ -446,17 +510,17 @@ static ir_region *new_RepeatLoop(struct obstack *obst, ir_region *head, ir_regio
 /**
  * Create a new WhileLoop region.
  */
-static ir_region *new_WhileLoop(struct obstack *obst, ir_region *head) {
-	ir_region *reg, *succ;
-	ir_region *body = head->link;
-	int i, j, len;
+static ir_region *new_WhileLoop(struct obstack *obst, ir_region *head)
+{
+	ir_region *reg  = alloc_region(obst, ir_rk_WhileLoop);
+	ir_region *body = (ir_region*) head->link;
+	ir_region *succ;
+	size_t i, j, len;
 
 	head->link = NULL;
 
-	ALLOC_REG(obst, reg, ir_rk_WhileLoop);
-
-	reg->nr      = head->nr;
-	reg->parts   = NEW_ARR_D(ir_reg_or_blk, obst, 2);
+	reg->nr    = head->nr;
+	reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 2);
 
 	reg->parts[0].region = head; head->parent = reg;
 	reg->parts[1].region = body; body->parent = reg;
@@ -479,38 +543,123 @@ static ir_region *new_WhileLoop(struct obstack *obst, ir_region *head) {
 	else
 		reg->succ[0] = get_region_succ(head, 1);
 
-	DB((dbg, LEVEL_2, " Created WhileLoop(%u)Body(%u)\n", reg->nr, body->nr));
+	DB((dbg, LEVEL_2, " Created WhileLoop(%lu)Body(%lu)\n", reg->nr, body->nr));
 
 	return reg;
 }  /* new_WhileLoop */
 
 /**
- * Return true if a is an ancestor of b in DFS search.
+ * Create a new new_NaturalLoop region.
  */
-static int is_ancestor(const ir_region *a, const ir_region *b) {
+static ir_region *new_NaturalLoop(struct obstack *obst, ir_region *head)
+{
+	ir_region *reg = alloc_region(obst, ir_rk_WhileLoop);
+	ir_region *c, *n;
+	size_t i, j, k, len, n_pred, n_succ;
+
+	/* count number of parts */
+	for (len = 0, c = head; c != NULL; c = (ir_region*) c->link)
+		++len;
+
+	reg->nr    = head->nr;
+	reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, len);
+
+	/* enter all parts */
+	for (i = 0, c = head; c != NULL; c = n) {
+		reg->parts[i++].region = c;
+		c->parent = reg;
+		n = (ir_region*) c->link;
+		c->link = NULL;
+	}
+
+	/* count number of preds */
+	n_pred = 0;
+	for (i = get_region_n_preds(head); i > 0;) {
+		ir_region *pred = get_region_pred(head, --i);
+		if (pred->parent != reg)
+			++n_pred;
+	}
+	reg->pred = NEW_ARR_D(ir_region *, obst, n_pred);
+	for (j = 0, i = get_region_n_preds(head); i > 0;) {
+		ir_region *pred = get_region_pred(head, --i);
+		if (pred->parent != reg)
+			reg->pred[j++] = pred;
+	}
+
+	/* count number of succs */
+	n_succ = 0;
+	for (j = 0; j < len; ++j) {
+		ir_region *pc = reg->parts[j].region;
+		for (i = get_region_n_succs(pc); i > 0;) {
+			ir_region *succ = get_region_succ(pc, --i);
+			if (succ->parent != reg)
+				++n_succ;
+		}
+	}
+	reg->succ = NEW_ARR_D(ir_region *, obst, n_succ);
+	k = 0;
+	for (j = 0; j < len; ++j) {
+		ir_region *pc = reg->parts[j].region;
+		for (i = get_region_n_succs(pc); i > 0;) {
+			ir_region *succ = get_region_succ(pc, --i);
+			if (succ->parent != reg)
+				reg->succ[k++] = succ;
+		}
+	}
+
+	DEBUG_ONLY(
+		DB((dbg, LEVEL_2, " Created NaturalLoop(%u)Head(%u)\n", reg->nr, head->nr));
+		for (i = 1; i < len; ++i) {
+			ir_region *p = reg->parts[i].region;
+			DB((dbg, LEVEL_2, "  Body(%u)\n", p->nr));
+		}
+	)
+	return reg;
+}  /* new_NaturalLoop */
+
+/**
+ * Return true if region a is an ancestor of region b in DFS search.
+ */
+static int is_ancestor(const ir_region *a, const ir_region *b)
+{
 	return (a->prenum <= b->prenum && a->postnum > b->postnum);
 }
 
 /**
- *  Return true if region succ is a successor of region n.
+ * Return true if region pred is a predecessor of region n.
+ */
+static bool pred_of(const ir_region *pred, const ir_region *n)
+{
+	size_t i, n_preds;
+	for (i = 0, n_preds = get_region_n_preds(n); i < n_preds; ++i) {
+		if (get_region_pred(n, i) == pred)
+			return true;
+	}
+	return false;
+}
+
+/**
+ * Return true if region succ is a successor of region n.
  */
-static int succ_of(const ir_region *succ, const ir_region *n) {
-	int i;
-	for (i = get_region_n_succs(n) - 1; i >= 0; --i) {
+static bool succ_of(const ir_region *succ, const ir_region *n)
+{
+	size_t i, n_succs;
+	for (i = 0, n_succs = get_region_n_succs(n); i < n_succs; ++i) {
 		if (get_region_succ(n, i) == succ)
-			return 1;
+			return true;
 	}
-	return 0;
+	return false;
 }
 
 /**
- *  Reverse linked list.
+ * Reverse a linked list of regions.
  */
-static struct ir_region *reverse_list(ir_region *n) {
+static struct ir_region *reverse_list(ir_region *n)
+{
 	ir_region *prev = NULL, *next;
 
 	for (; n; n = next) {
-		next = n->link;
+		next = (ir_region*) n->link;
 		n->link = prev;
 		prev = n;
 	}
@@ -520,23 +669,24 @@ static struct ir_region *reverse_list(ir_region *n) {
 /**
  * Find the cyclic region in the subgraph entered by node.
  */
-static ir_region *find_cyclic_region(ir_region *node) {
-	int i;
+static ir_region *find_cyclic_region(ir_region *node)
+{
+	size_t i;
 	ir_region *last = node;
 	int improper = 0;
 
-	for (i = get_region_n_preds(node) - 1; i >= 0; --i) {
-		ir_region *pred = get_region_pred(node, i);
+	for (i = get_region_n_preds(node); i > 0;) {
+		ir_region *pred = get_region_pred(node, --i);
 
 		/* search backedges */
 		if (!pred->link && pred != last && is_ancestor(node, pred)) {
 			ir_region *rem = last;
-			int j;
+			size_t j;
 
 			last->link = pred;
 			last       = pred;
-			for (j = get_region_n_preds(pred) - 1; j >= 0; --j) {
-				ir_region *p = get_region_pred(pred, j);
+			for (j = get_region_n_preds(pred); j > 0;) {
+				ir_region *p = get_region_pred(pred, --j);
 
 				/* Search regions we didn't visited yet and
 				   link them into the list. */
@@ -550,24 +700,24 @@ static ir_region *find_cyclic_region(ir_region *node) {
 				}
 			}
 			/* reverse the list. */
-			last = rem->link;
-			rem->link = reverse_list(rem->link);
+			last = (ir_region*) rem->link;
+			rem->link = reverse_list(last);
 		}
 	}
 
 	if (node->link && improper) {
-		/* found an improper region */
+		/* found an improper region, do minimization */
+
 	}
 	return node;
 }
 
-#define LINK(list) ((ir_region *)list->link)
-
 /**
  * Detect a cyclic region.
  */
-static ir_region *cyclic_region_type(struct obstack *obst, ir_region *node) {
-	ir_region *list;
+static ir_region *cyclic_region_type(struct obstack *obst, ir_region *node)
+{
+	ir_region *list, *next;
 
 	/* simple cases first */
 	if (succ_of(node, node)) {
@@ -581,56 +731,77 @@ static ir_region *cyclic_region_type(struct obstack *obst, ir_region *node) {
 	}
 	list = find_cyclic_region(node);
 
-	if (list->link && !LINK(list)->link && get_region_n_succs(list->link) == 1) {
-		return new_WhileLoop(obst, list);
+	next = (ir_region*) list->link;
+	if (next) {
+		if (!next->link && get_region_n_succs(next) == 1) {
+			/* only one body block with only one successor (the head) */
+			return new_WhileLoop(obst, list);
+		}
+		/* A Loop with one head */
+		return new_NaturalLoop(obst, list);
 	}
 
 	return NULL;
 }
 
+/**
+ * Clear all links on a list. Needed, because we expect cleared links.
+ */
+static void clear_list(ir_region *list)
+{
+	ir_region *next;
+
+	for (next = list; next; list = next) {
+		next = (ir_region*) list->link;
+		list->link = NULL;
+	}
+}
+
+#define ADD_LIST(list, n) do { n->link = list; list = n; ++list##_len; } while (0)
+
 /**
  * Detect an acyclic region.
  */
-static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node) {
+static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node)
+{
 	ir_region *n, *m;
-	int p, s, i, k;
-	ir_region **nset = NEW_ARR_F(ir_region *, 0);
-	pset *set;
+	bool p, s;
+	size_t k;
+	ir_region *nset = NULL;
+	size_t nset_len = 0;
 	ir_region *res;
 
 	/* check for a block containing node */
 	n = node;
 	p = get_region_n_preds(n) == 1;
-	s = 1;
+	s = true;
 	while (p & s) {
 		n = get_region_pred(n, 0);
 		p = get_region_n_preds(n) == 1;
 		s = get_region_n_succs(n) == 1;
 	}
-	p = 1;
+	p = true;
 	s = get_region_n_succs(n) == 1;
 	while (p & s) {
-		ARR_APP1(ir_region *, nset, n);
+		ADD_LIST(nset, n);
 		n = get_region_succ(n, 0);
 		p = get_region_n_preds(n) == 1;
 		s = get_region_n_succs(n) == 1;
 	}
 	if (p) {
-		ARR_APP1(ir_region *, nset, n);
+		ADD_LIST(nset, n);
 	}
-	if (ARR_LEN(nset) >= 2) {
+	if (nset_len > 1) {
 		/* node --> .. --> .. */
-		res = new_Sequence(obst, nset);
-		DEL_ARR_F(nset);
+		res = new_Sequence(obst, nset, nset_len);
 		return res;
 	}
-	DEL_ARR_F(nset);
 	node = n;
 
 	/* check for IfThenElse */
 	k = get_region_n_succs(node);
 	if (k == 2) {
-		int n_succs, m_succs, n_preds, m_preds;
+		size_t n_succs, m_succs, n_preds, m_preds;
 
 		n = get_region_succ(node, 0);
 		m = get_region_succ(node, 1);
@@ -648,20 +819,18 @@ static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node) {
 			 */
 			return new_IfThenElse(obst, node, n, m);
 		}
-		if (n_succs == 1 && m_preds == 2 &&
+		if (n_succs == 1 &&
 		    get_region_succ(n, 0) == m &&
-		    (get_region_pred(m, 0) == node ||
-		     get_region_pred(m, 1) == node)) {
+		    pred_of(node, m)) {
 			/*
 			 * node -->n-->m
 			 *    \-------/
 			 */
 			return new_IfThen(obst, node, n);
 		}
-		if (m_succs == 1 && n_preds == 2 &&
+		if (m_succs == 1 &&
 		    get_region_succ(m, 0) == m &&
-		    (get_region_pred(n, 0) == node ||
-		     get_region_pred(n, 1) == node)) {
+		    pred_of(node, n)) {
 			/*
 			 * node -->m-->n
 			 *    \-------/
@@ -670,80 +839,104 @@ static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node) {
 		}
 	}
 	/* check for Switch, case */
-	set = pset_new_ptr_default();
-	p   = k > 0;
-	for (i = k - 1; i >= 0; --i) {
-		n = get_region_succ(node, i);
-		pset_insert_ptr(set, n);
-		if (get_region_n_succs(n) != 1) {
-			p = 0;
-			break;
-		}
-	}
-	if (p) {
-		ir_region_kind kind = ir_rk_Case;
-
-		m = pset_first(set);
-		if (pset_find_ptr(set, m) != NULL) {
-			/* must be a switch, if any, find the exit */
-			kind = ir_rk_Switch;
-
-			for (m = pset_next(set); m != NULL; m = pset_next(set)) {
-				if (pset_find_ptr(set, m) == NULL) {
-					pset_break(set);
+	if (k > 0) {
+		ir_region *rexit = NULL;
+		size_t i, p = 0;
+		nset = NULL; nset_len = 0;
+		for (i = k; i > 0;) {
+			n = get_region_succ(node, i--);
+			ADD_LIST(nset, n);
+			if (get_region_n_succs(n) != 1) {
+				/* must be the exit */
+				rexit = n;
+				++p;
+				if (p > 1)
 					break;
-				}
 			}
 		}
-		if (m != NULL) {
-			/* m ist the exit, do the checks */
-			foreach_pset(set, n) {
-				if (n == m) {
-					/* good, switch to exit */
-					continue;
-				}
-				if (pset_find_ptr(set, n) == NULL) {
-					/* another exit */
-					pset_break(set);
-					break;
+		if (p <= 1) {
+			ir_region_kind kind = ir_rk_Case;
+			ir_region *pos_exit_1 = NULL;
+			ir_region *pos_exit_2 = NULL;
+
+			/* find the exit */
+			for (m = nset; m != NULL; m = (ir_region*) m->link) {
+				if (get_region_n_succs(m) != 1) {
+					/* must be the exit block */
+					if (rexit == NULL) {
+						rexit = m;
+					} else if (rexit != m) {
+						/* two exits */
+						rexit = NULL;
+						break;
+					}
+				} else {
+					ir_region *succ = get_region_succ(m, 0);
+
+					if (succ->link == NULL) {
+						if (rexit == NULL) {
+							if (succ == pos_exit_1)
+								rexit = succ;
+							else if (succ == pos_exit_2)
+								rexit = succ;
+							else if (pos_exit_1 == NULL)
+								pos_exit_1 = succ;
+							else if (pos_exit_2 == NULL)
+								pos_exit_2 = succ;
+							else {
+								/* more than two possible exits */
+								break;
+							}
+						} else if (rexit != succ) {
+							/* two exits */
+							rexit = NULL;
+							break;
+						}
+					}
 				}
-				kind = ir_rk_Switch;
 			}
+			if (rexit != NULL) {
+				/* do the checks */
+				for (n = nset; n != NULL; n = (ir_region*) n->link) {
+					ir_region *succ;
+					if (n == rexit) {
+						/* good, default fall through */
+						continue;
+					}
+					succ = get_region_succ(n, 0);
+					if (succ == rexit) {
+						/* good, switch to exit */
+						continue;
+					}
+					if (succ->link == NULL) {
+						/* another exit */
+						break;
+					} else {
+						/* a fall through */
+						kind = ir_rk_Switch;
+					}
+				}
 
-			if (n == NULL) {
-				/* detected */
-				return new_SwitchCase(obst, kind, node, m, set);
+				if (n == NULL) {
+					/* detected */
+					return new_SwitchCase(obst, kind, node, rexit, nset, nset_len);
+				}
 			}
 		}
+		clear_list(nset);
 	}
-	/* check for proper */
-
 	return NULL;
 }
 
-/**
- * Fill the given set recursively with all parts of the region (including itself)
- */
-static void fill_parts(pset *set, ir_region *reg) {
-	int i;
-
-	if (reg->type == ir_rk_Block) {
-		pset_insert_ptr(set, reg);
-		return;
-	}
-
-	for (i = ARR_LEN(reg->parts) - 1; i >= 0; --i) {
-		fill_parts(set, reg->parts[i].region);
-	}
-}
-
 /**
  * replace all pred edges from region pred that points to any of the set set
  * to ONE edge to reg.
  */
-static void replace_pred(ir_region *succ, ir_region *reg) {
-	int i, len = get_region_n_preds(succ);
-	int have_one = 0;
+static void replace_pred(ir_region *succ, ir_region *reg)
+{
+	int    have_one = 0;
+	size_t len      = get_region_n_preds(succ);
+	size_t i;
 
 	for (i = 0; i < len; ++i) {
 		ir_region *pred = get_region_pred(succ, i);
@@ -760,6 +953,9 @@ static void replace_pred(ir_region *succ, ir_region *reg) {
 				r = reg;
 			}
 			set_region_pred(succ, i, r);
+		} else {
+			/* the current region can be entered by this node */
+			pred->enter = 1;
 		}
 	}
 	ARR_SHRINKLEN(succ->pred, len);
@@ -769,9 +965,11 @@ static void replace_pred(ir_region *succ, ir_region *reg) {
  * replace all succ edges from region pred that points to any of the set set
  * to ONE edge to reg.
  */
-static void replace_succ(ir_region *pred, ir_region *reg) {
-	int i, len = get_region_n_succs(pred);
-	int have_one = 0;
+static void replace_succ(ir_region *pred, ir_region *reg)
+{
+	int    have_one = 0;
+	size_t len      = get_region_n_succs(pred);
+	size_t i;
 
 	for (i = 0; i < len; ++i) {
 		ir_region *succ = get_region_succ(pred, i);
@@ -788,6 +986,9 @@ static void replace_succ(ir_region *pred, ir_region *reg) {
 				r = reg;
 			}
 			set_region_succ(pred, i, r);
+		} else {
+			/* current region can be left by this node */
+			succ->exit = 1;
 		}
 	}
 	ARR_SHRINKLEN(pred->succ, len);
@@ -796,22 +997,23 @@ static void replace_succ(ir_region *pred, ir_region *reg) {
 /**
  * Reduce the graph by the node reg.
  */
-static void reduce(walk_env *env, ir_region *reg) {
-	int i;
+static void reduce(walk_env *env, ir_region *reg)
+{
+	size_t i;
 	ir_region *head = reg->parts[0].region;
-	unsigned maxorder = head->postnum;
-	unsigned minorder = head->prenum;
+	size_t maxorder = head->postnum;
+	size_t minorder = head->prenum;
 
 	/* second step: replace all preds in successors */
-	for (i = get_region_n_succs(reg) - 1; i >= 0; --i) {
-		ir_region *succ = get_region_succ(reg, i);
+	for (i = get_region_n_succs(reg); i > 0;) {
+		ir_region *succ = get_region_succ(reg, --i);
 
 		replace_pred(succ, reg);
 	}
 
-	/* second third: replace all succs in predessors */
-	for (i = get_region_n_preds(reg) - 1; i >= 0; --i) {
-		ir_region *pred = get_region_pred(reg, i);
+	/* third step: replace all succs in predessors */
+	for (i = get_region_n_preds(reg); i > 0;) {
+		ir_region *pred = get_region_pred(reg, --i);
 
 		replace_succ(pred, reg);
 	}
@@ -829,10 +1031,11 @@ static void reduce(walk_env *env, ir_region *reg) {
  *
  * @param irg  the graph
  */
-ir_reg_tree *construct_region_tree(ir_graph *irg) {
+ir_reg_tree *construct_region_tree(ir_graph *irg)
+{
 	walk_env env;
 	ir_graph *rem = current_ir_graph;
-	ir_reg_tree *res = xmalloc(sizeof(*res));
+	ir_reg_tree *res = XMALLOC(ir_reg_tree);
 
 	obstack_init(&res->obst);
 
@@ -841,9 +1044,7 @@ ir_reg_tree *construct_region_tree(ir_graph *irg) {
 	FIRM_DBG_REGISTER(dbg, "firm.ana.structure");
 	firm_dbg_set_mask(dbg, SET_LEVEL_5);
 
-	DB((dbg, LEVEL_1, "Structural analysis on %+F starts...\n", irg));
-
-	dump_ir_block_graph(irg, "-structure_start");
+	DB((dbg, LEVEL_1, "Structural analysis on %+F started ...\n", irg));
 
 	/* we need dominance info */
 	assure_doms(irg);
@@ -853,24 +1054,26 @@ ir_reg_tree *construct_region_tree(ir_graph *irg) {
 	env.start_block = get_irg_start_block(irg);
 	env.end_block   = get_irg_end_block(irg);
 
+	ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
+
 	/* create the Block wrapper and count them */
 	env.l_post = 0;
 	env.obst   = &res->obst;
-	irg_block_walk_graph(irg, NULL, wrap_blocks, &env);
-	irg_block_walk_graph(irg, NULL, update_Block_regions, &env);
+	irg_block_walk_graph(irg, NULL, wrap_BasicBlocks, &env);
+	irg_block_walk_graph(irg, NULL, update_BasicBlock_regions, &env);
 
 	env.post = NEW_ARR_F(ir_region *, env.l_post);
 
 	/* do the DFS walk */
 	dfs_walk(irg, &env);
 
-	DB((dbg, LEVEL_1, "%d regions left\n", env.postmax));
+	DB((dbg, LEVEL_1, "%zu regions left\n", env.postmax));
 	if (env.postmax > 1) {
-		unsigned postctr = 0;
+		size_t postctr = 0;
 		do {
 			ir_region *reg, *n = env.post[postctr];
 			do {
-				if (n->parent) {
+				if (n->parent != NULL) {
 					/* already folded */
 					break;
 				}
@@ -891,6 +1094,8 @@ ir_reg_tree *construct_region_tree(ir_graph *irg) {
 	}
 	DB((dbg, LEVEL_1, "Structural analysis finished.\n"));
 
+	ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
+
 	DEL_ARR_F(env.post);
 	current_ir_graph = rem;
 
@@ -907,12 +1112,13 @@ ir_reg_tree *construct_region_tree(ir_graph *irg) {
  * @param post  walker function, executed after the children of a tree node are visited
  * @param env   environment, passed to pre and post
  */
-static void region_tree_walk2(ir_region *reg, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env) {
-	int i, n;
+static void region_tree_walk2(ir_region *reg, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env)
+{
+	size_t i, n;
 
 	if (pre)
 		pre(reg, env);
-	if (reg->type != ir_rk_Block) {
+	if (reg->type != ir_rk_BasicBlock) {
 		for (i = 0, n = ARR_LEN(reg->parts); i < n; ++i)
 			region_tree_walk2(reg->parts[i].region, pre, post, env);
 	}
@@ -928,6 +1134,7 @@ static void region_tree_walk2(ir_region *reg, irg_reg_walk_func *pre, irg_reg_wa
  * @param post  walker function, executed after the children of a tree node are visited
  * @param env   environment, passed to pre and post
  */
-void region_tree_walk(ir_reg_tree *tree, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env) {
+void region_tree_walk(ir_reg_tree *tree, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env)
+{
 	region_tree_walk2(tree->top, pre, post, env);
 }