X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fstructure.c;h=356225f2c63a5a2469949e3512d6e709edb75d58;hb=0f234e2d94155d13c0e4727871125beda0eaa66d;hp=b59a4c1d13f9319165f0b12f3d1d1dc237cef553;hpb=cad5a73c70accbe9a0807ddec67e94d3ba799984;p=libfirm diff --git a/ir/ana/structure.c b/ir/ana/structure.c index b59a4c1d1..356225f2c 100644 --- a/ir/ana/structure.c +++ b/ir/ana/structure.c @@ -1,17 +1,30 @@ /* - * 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-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$ + */ #include "config.h" -#endif #include "firm_common.h" #include "irnode_t.h" @@ -21,7 +34,7 @@ #include "irtools.h" #include "irgwalk.h" #include "array.h" -#include "irphase_t.h" +#include "irdump.h" #include "debug.h" @@ -36,17 +49,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 +72,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. @@ -78,7 +93,7 @@ void set_region_link(ir_region *reg, void *data) { */ ir_region *get_block_region(const ir_node *block) { assert(is_Block(block)); - return get_irn_link(block); + return block->attr.block.region; } /** @@ -86,7 +101,7 @@ ir_region *get_block_region(const ir_node *block) { */ void set_block_region(ir_node *block, ir_region *reg) { assert(is_Block(block)); - set_irn_link(block, reg); + block->attr.block.region = reg; } /** @@ -99,7 +114,7 @@ ir_region *get_irn_region(ir_node *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; @@ -107,7 +122,7 @@ int is_region(const void *thing) { } /** - * 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) { return ARR_LEN(reg->pred); @@ -156,13 +171,13 @@ 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 l_post; /**< The 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. */ + ir_node *start_block; /**< The start block of the graph. */ + ir_node *end_block; /**< The end block of the graph. */ } walk_env; /** @@ -205,21 +220,23 @@ 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) { +static void wrap_BasicBlocks(ir_node *block, void *ctx) { walk_env *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,19 +245,19 @@ 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) { +static void update_BasicBlock_regions(ir_node *blk, void *ctx) { walk_env *env = ctx; ir_region *reg = get_irn_link(blk); int i, j, len; 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); @@ -259,43 +276,51 @@ static void update_Block_regions(ir_node *blk, void *ctx) { reg->succ[j++] = get_irn_link(succ); } ARR_SHRINKLEN(reg->succ, j); -} +} /* update_BasicBlock_regions */ -/** Allocate a new region of a obstack */ +/** Allocate a new region on an obstack */ #define ALLOC_REG(obst, reg, tp) \ do { \ - (reg) = obstack_alloc((obst), sizeof(*(reg))); \ + (reg) = OALLOC((obst), ir_region); \ (reg)->kind = k_ir_region; \ (reg)->type = tp; \ (reg)->parent = NULL; \ (reg)->prenum = 0; \ (reg)->postnum = 0; \ (reg)->visited = 0; \ + (reg)->exit = 0; \ + (reg)->enter = 0; \ (reg)->link = NULL; \ } while (0) /** * 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); +static ir_region *new_Sequence(struct obstack *obst, ir_region *nset, int nset_len) { + ir_region *reg, *next; + int i; 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); + reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, nset_len); - for (i = 0; i < len; ++i) { - reg->parts[i].region = nset[i]; - nset[i]->parent = reg; + /* 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; + next = 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) { + for (i = 0; i < nset_len; ++i) { DB((dbg, LEVEL_2, "(%u)", reg->parts[i].region->nr)); } DB((dbg, LEVEL_2, "\n")); @@ -351,29 +376,47 @@ 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; +static ir_region *new_SwitchCase(struct obstack *obst, ir_region_kind type, ir_region *head, ir_region *exit, + ir_region *cases, int cases_len) { + ir_region *reg, *c, *n; int i; + int add = 1; + + /* check, if the exit block is in the list */ + for (c = cases; c != NULL; c = c->link) { + if (c == exit) { + add = 0; + break; + } + } ALLOC_REG(obst, reg, type); 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 = 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; - - DB((dbg, LEVEL_2, " Created Switch(%u)Exit(%u)\n", reg->nr, end->nr)); + reg->succ[0] = exit; - del_pset(cases); + DEBUG_ONLY( + 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(%u)\n", reg->parts[i].region->nr)); + } + DB((dbg, LEVEL_2, " Exit(%u)\n", exit->nr)); + ) return reg; } /* new_SwitchCase */ @@ -485,14 +528,95 @@ static ir_region *new_WhileLoop(struct obstack *obst, ir_region *head) { } /* new_WhileLoop */ /** - * Return true if a is an ancestor of b in DFS search. + * 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 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 int pred_of(const ir_region *pred, const ir_region *n) { + int i; + for (i = get_region_n_preds(n) - 1; i >= 0; --i) { + if (get_region_pred(n, i) == pred) + return 1; + } + return 0; +} + +/** + * 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; @@ -504,7 +628,7 @@ static int succ_of(const ir_region *succ, const ir_region *n) { } /** - * Reverse linked list. + * Reverse a linked list of regions. */ static struct ir_region *reverse_list(ir_region *n) { ir_region *prev = NULL, *next; @@ -556,7 +680,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; } @@ -581,21 +706,40 @@ 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; } +/** + * 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 = 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) { ir_region *n, *m; int p, s, i, k; - ir_region **nset = NEW_ARR_F(ir_region *, 0); - pset *set; + ir_region *nset = NULL; + int nset_len = 0; ir_region *res; /* check for a block containing node */ @@ -610,21 +754,19 @@ static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node) { p = 1; 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 */ @@ -648,20 +790,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,73 +810,95 @@ 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 *exit = NULL; + nset = NULL; nset_len = 0; + p = 0; + for (i = k - 1; i >= 0; --i) { + n = get_region_succ(node, i); + ADD_LIST(nset, n); + if (get_region_n_succs(n) != 1) { + /* must be the exit */ + exit = 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 = m->link) { + if (get_region_n_succs(m) != 1) { + /* must be the exit block */ + if (exit == NULL) { + exit = m; + } else if (exit != m) { + /* two exits */ + exit = NULL; + break; + } + } else { + ir_region *succ = get_region_succ(m, 0); + + if (succ->link == NULL) { + if (exit == NULL) { + if (succ == pos_exit_1) + exit = succ; + else if (succ == pos_exit_2) + exit = 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 (exit != succ) { + /* two exits */ + exit = NULL; + break; + } + } } - kind = ir_rk_Switch; } + if (exit != NULL) { + /* do the checks */ + for (n = nset; n != NULL; n = n->link) { + ir_region *succ; + if (n == exit) { + /* good, default fall through */ + continue; + } + succ = get_region_succ(n, 0); + if (succ == exit) { + /* 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, exit, 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. @@ -760,6 +922,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); @@ -788,6 +953,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); @@ -809,7 +977,7 @@ static void reduce(walk_env *env, ir_region *reg) { replace_pred(succ, reg); } - /* second third: replace all succs in predessors */ + /* third step: replace all succs in predessors */ for (i = get_region_n_preds(reg) - 1; i >= 0; --i) { ir_region *pred = get_region_pred(reg, i); @@ -832,7 +1000,7 @@ static void reduce(walk_env *env, ir_region *reg) { 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); @@ -856,8 +1024,8 @@ ir_reg_tree *construct_region_tree(ir_graph *irg) { /* 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); @@ -870,7 +1038,7 @@ ir_reg_tree *construct_region_tree(ir_graph *irg) { do { ir_region *reg, *n = env.post[postctr]; do { - if (n->parent) { + if (n->parent != NULL) { /* already folded */ break; } @@ -912,7 +1080,7 @@ static void region_tree_walk2(ir_region *reg, irg_reg_walk_func *pre, irg_reg_wa 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); }