X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;ds=sidebyside;f=ir%2Fana%2Fstructure.c;h=c90a09483878f12fc3c7fa71ca8ea05baf260c1c;hb=7fb8d0d5cb80fa51fef49bcd1c05117801a59c77;hp=fe90fb4a4b30517d1a576278a56c9a1e192716ab;hpb=0fbcef83aa6060534172bb13e71cdadb04428806;p=libfirm diff --git a/ir/ana/structure.c b/ir/ana/structure.c index fe90fb4a4..c90a09483 100644 --- a/ir/ana/structure.c +++ b/ir/ana/structure.c @@ -77,21 +77,24 @@ 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 block->attr.block.region; } @@ -99,7 +102,8 @@ ir_region *get_block_region(const ir_node *block) { /** * 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)); block->attr.block.region = reg; } @@ -107,31 +111,35 @@ void set_block_region(ir_node *block, ir_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) { +int is_region(const void *thing) +{ const firm_kind *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) { +int 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) { +ir_region *get_region_pred(const ir_region *reg, int pos) +{ assert(0 <= pos && pos <= get_region_n_preds(reg)); return reg->pred[pos]; } @@ -139,7 +147,8 @@ ir_region *get_region_pred(const ir_region *reg, int pos) { /** * Set the predecessor region at position pos. */ -void set_region_pred(ir_region *reg, int pos, ir_region *n) { +void set_region_pred(ir_region *reg, int pos, ir_region *n) +{ assert(0 <= pos && pos <= get_region_n_preds(reg)); reg->pred[pos] = n; } @@ -147,14 +156,16 @@ void set_region_pred(ir_region *reg, int pos, ir_region *n) { /** * Return the number of successors in a region. */ -int get_region_n_succs(const ir_region *reg) { +int 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) { +ir_region *get_region_succ(const ir_region *reg, int pos) +{ assert(0 <= pos && pos <= get_region_n_succs(reg)); return reg->succ[pos]; } @@ -162,7 +173,8 @@ ir_region *get_region_succ(const ir_region *reg, int pos) { /** * Set the successor region at position pos. */ -void set_region_succ(ir_region *reg, int pos, ir_region *n) { +void set_region_succ(ir_region *reg, int pos, ir_region *n) +{ assert(0 <= pos && pos <= get_region_n_succs(reg)); reg->succ[pos] = n; } @@ -171,20 +183,21 @@ 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; /** * 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) { +static void dfs_walk2(ir_region *reg, walk_env *env) +{ int i, n; if (reg->visited == 0) { @@ -206,7 +219,8 @@ 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; @@ -223,12 +237,13 @@ static void dfs_walk(ir_graph *irg, walk_env *env) { * Post-walker: wrap all blocks with a BasicBlock region * and count them */ -static void wrap_BasicBlocks(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_BasicBlock; reg->parent = NULL; @@ -248,16 +263,17 @@ static void wrap_BasicBlocks(ir_node *block, void *ctx) { } /* 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_BasicBlock_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); @@ -278,10 +294,10 @@ static void update_BasicBlock_regions(ir_node *blk, void *ctx) { 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; \ @@ -296,7 +312,8 @@ 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) { +static ir_region *new_Sequence(struct obstack *obst, ir_region *nset, int nset_len) +{ ir_region *reg, *next; int i; @@ -331,7 +348,8 @@ static ir_region *new_Sequence(struct obstack *obst, ir_region *nset, int nset_l /** * 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) { +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); @@ -354,7 +372,8 @@ 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) { +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); @@ -377,7 +396,8 @@ 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 *exit, - ir_region *cases, int cases_len) { + ir_region *cases, int cases_len) +{ ir_region *reg, *c, *n; int i; int add = 1; @@ -423,7 +443,8 @@ static ir_region *new_SwitchCase(struct obstack *obst, ir_region_kind type, ir_r /** * Create a new SelfLoop region. */ -static ir_region *new_SelfLoop(struct obstack *obst, ir_region *head) { +static ir_region *new_SelfLoop(struct obstack *obst, ir_region *head) +{ ir_region *reg, *succ; int i, j, len; @@ -460,7 +481,8 @@ 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) { +static ir_region *new_RepeatLoop(struct obstack *obst, ir_region *head, ir_region *body) +{ ir_region *reg, *succ; ALLOC_REG(obst, reg, ir_rk_RepeatLoop); @@ -489,7 +511,8 @@ 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) { +static ir_region *new_WhileLoop(struct obstack *obst, ir_region *head) +{ ir_region *reg, *succ; ir_region *body = head->link; int i, j, len; @@ -530,7 +553,8 @@ static ir_region *new_WhileLoop(struct obstack *obst, ir_region *head) { /** * Create a new new_NaturalLoop region. */ -static ir_region *new_NaturalLoop(struct obstack *obst, ir_region *head) { +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; @@ -568,9 +592,9 @@ static ir_region *new_NaturalLoop(struct obstack *obst, ir_region *head) { /* 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); + ir_region *pc = reg->parts[j].region; + for (i = get_region_n_succs(pc) - 1; i >= 0; --i) { + ir_region *succ = get_region_succ(pc, i); if (succ->parent != reg) ++n_succ; } @@ -578,9 +602,9 @@ static ir_region *new_NaturalLoop(struct obstack *obst, ir_region *head) { 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); + ir_region *pc = reg->parts[j].region; + for (i = get_region_n_succs(pc) - 1; i >= 0; --i) { + ir_region *succ = get_region_succ(pc, i); if (succ->parent != reg) reg->succ[k++] = succ; } @@ -597,16 +621,18 @@ static ir_region *new_NaturalLoop(struct obstack *obst, ir_region *head) { } /* new_NaturalLoop */ /** - * Return true if a is an ancestor of b in DFS search. + * 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) { +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 pred is a predecessor 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) { +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) @@ -616,9 +642,10 @@ static int pred_of(const ir_region *pred, const ir_region *n) { } /** - * Return true if region succ is a successor of region n. + * Return true if region succ is a successor of region n. */ -static int succ_of(const ir_region *succ, const ir_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) { if (get_region_succ(n, i) == succ) @@ -628,9 +655,10 @@ 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) { +static struct ir_region *reverse_list(ir_region *n) +{ ir_region *prev = NULL, *next; for (; n; n = next) { @@ -644,7 +672,8 @@ 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) { +static ir_region *find_cyclic_region(ir_region *node) +{ int i; ir_region *last = node; int improper = 0; @@ -691,7 +720,8 @@ static ir_region *find_cyclic_region(ir_region *node) { /** * Detect a cyclic region. */ -static ir_region *cyclic_region_type(struct obstack *obst, ir_region *node) { +static ir_region *cyclic_region_type(struct obstack *obst, ir_region *node) +{ ir_region *list; /* simple cases first */ @@ -719,9 +749,10 @@ static ir_region *cyclic_region_type(struct obstack *obst, ir_region *node) { } /** - * Clear all links on a list. Needed, because we expect cleared links- + * Clear all links on a list. Needed, because we expect cleared links. */ -static void clear_list(ir_region *list) { +static void clear_list(ir_region *list) +{ ir_region *next; for (next = list; next; list = next) { @@ -730,12 +761,13 @@ static void clear_list(ir_region *list) { } } -#define ADD_LIST(list, n) do { n->link = list; list = n; ++list##_len; } while(0) +#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 = NULL; @@ -811,7 +843,7 @@ static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node) { } /* check for Switch, case */ if (k > 0) { - ir_region *exit = NULL; + ir_region *rexit = NULL; nset = NULL; nset_len = 0; p = 0; for (i = k - 1; i >= 0; --i) { @@ -819,7 +851,7 @@ static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node) { ADD_LIST(nset, n); if (get_region_n_succs(n) != 1) { /* must be the exit */ - exit = n; + rexit = n; ++p; if (p > 1) break; @@ -834,22 +866,22 @@ static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node) { 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) { + if (rexit == NULL) { + rexit = m; + } else if (rexit != m) { /* two exits */ - exit = NULL; + rexit = NULL; break; } } else { ir_region *succ = get_region_succ(m, 0); if (succ->link == NULL) { - if (exit == NULL) { + if (rexit == NULL) { if (succ == pos_exit_1) - exit = succ; + rexit = succ; else if (succ == pos_exit_2) - exit = succ; + rexit = succ; else if (pos_exit_1 == NULL) pos_exit_1 = succ; else if (pos_exit_2 == NULL) @@ -858,24 +890,24 @@ static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node) { /* more than two possible exits */ break; } - } else if (exit != succ) { + } else if (rexit != succ) { /* two exits */ - exit = NULL; + rexit = NULL; break; } } } } - if (exit != NULL) { + if (rexit != NULL) { /* do the checks */ for (n = nset; n != NULL; n = n->link) { ir_region *succ; - if (n == exit) { + if (n == rexit) { /* good, default fall through */ continue; } succ = get_region_succ(n, 0); - if (succ == exit) { + if (succ == rexit) { /* good, switch to exit */ continue; } @@ -890,7 +922,7 @@ static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node) { if (n == NULL) { /* detected */ - return new_SwitchCase(obst, kind, node, exit, nset, nset_len); + return new_SwitchCase(obst, kind, node, rexit, nset, nset_len); } } } @@ -903,7 +935,8 @@ static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node) { * 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) { +static void replace_pred(ir_region *succ, ir_region *reg) +{ int i, len = get_region_n_preds(succ); int have_one = 0; @@ -934,7 +967,8 @@ 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) { +static void replace_succ(ir_region *pred, ir_region *reg) +{ int i, len = get_region_n_succs(pred); int have_one = 0; @@ -964,7 +998,8 @@ 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) { +static void reduce(walk_env *env, ir_region *reg) +{ int i; ir_region *head = reg->parts[0].region; unsigned maxorder = head->postnum; @@ -977,7 +1012,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); @@ -997,7 +1032,8 @@ 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(ir_reg_tree); @@ -1011,8 +1047,6 @@ ir_reg_tree *construct_region_tree(ir_graph *irg) { DB((dbg, LEVEL_1, "Structural analysis on %+F starts...\n", irg)); - dump_ir_block_graph(irg, "-structure_start"); - /* we need dominance info */ assure_doms(irg); /* and out edges */ @@ -1038,7 +1072,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; } @@ -1075,7 +1109,8 @@ 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) { +static void region_tree_walk2(ir_region *reg, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env) +{ int i, n; if (pre) @@ -1096,6 +1131,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); }