X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fstructure.c;h=96b8247fcc5105862dfd59e2f94da0c475804e42;hb=5dfe14ff917ce1b96df2fc89c7074175d66587b8;hp=08b2bef2fe220408e5b84fe6c62f075815da6766;hpb=b5d7f94e82eff9d852eaa2b3b181de4570311f78;p=libfirm diff --git a/ir/ana/structure.c b/ir/ana/structure.c index 08b2bef2f..96b8247fc 100644 --- a/ir/ana/structure.c +++ b/ir/ana/structure.c @@ -1,13 +1,28 @@ /* - * 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. + * Copyright (C) 1995-2008 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$ */ #ifdef HAVE_CONFIG_H #include "config.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. */ + unsigned prenum; /**< DFS pre-oder number */ + unsigned 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,7 +74,7 @@ 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. @@ -220,6 +237,8 @@ static void wrap_BasicBlocks(ir_node *block, void *ctx) { 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); @@ -271,6 +290,8 @@ static void update_BasicBlock_regions(ir_node *blk, void *ctx) { (reg)->prenum = 0; \ (reg)->postnum = 0; \ (reg)->visited = 0; \ + (reg)->exit = 0; \ + (reg)->enter = 0; \ (reg)->link = NULL; \ } while (0) @@ -278,7 +299,7 @@ static void update_BasicBlock_regions(ir_node *blk, void *ctx) { * Creates a new Sequence region. */ static ir_region *new_Sequence(struct obstack *obst, ir_region *nset, int nset_len) { - ir_region *reg; + ir_region *reg, *next; int i; ALLOC_REG(obst, reg, ir_rk_Sequence); @@ -286,10 +307,13 @@ static ir_region *new_Sequence(struct obstack *obst, ir_region *nset, int nset_l 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 - 1; i >= 0; --i) { + nset = next; reg->parts[i].region = nset; nset->parent = reg; - nset = nset->link; + next = nset->link; + nset->link = NULL; } reg->nr = reg->parts[0].region->nr; @@ -505,6 +529,75 @@ static ir_region *new_WhileLoop(struct obstack *obst, ir_region *head) { return reg; } /* new_WhileLoop */ +/** + * Create a new new_NaturalLoop region. + */ +static ir_region *new_NaturalLoop(struct obstack *obst, ir_region *head) { + ir_region *reg, *c, *n; + int i, j, k, len, n_pred, n_succ; + + /* count number of parts */ + for (len = 0, c = head; c != NULL; c = c->link) + ++len; + + ALLOC_REG(obst, reg, ir_rk_WhileLoop); + + 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 = c->link; + c->link = NULL; + } + + /* count number of preds */ + n_pred = 0; + for (i = get_region_n_preds(head) - 1; i >= 0; --i) { + 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) - 1; i >= 0; --i) { + 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 *c = reg->parts[j].region; + for (i = get_region_n_succs(c) - 1; i >= 0; --i) { + ir_region *succ = get_region_succ(c, 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 *c = reg->parts[j].region; + for (i = get_region_n_succs(c) - 1; i >= 0; --i) { + ir_region *succ = get_region_succ(c, 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 a is an ancestor of b in DFS search. */ @@ -589,7 +682,8 @@ static ir_region *find_cyclic_region(ir_region *node) { } if (node->link && improper) { - /* found an improper region */ + /* found an improper region, do minimization */ + } return node; } @@ -614,8 +708,13 @@ 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); + if (list->link) { + if (!LINK(list)->link && get_region_n_succs(list->link) == 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; @@ -825,6 +924,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); @@ -853,6 +955,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);