3 * File name: ir/ana/structure.c
4 * Purpose: Structure Analysis
9 * Copyright: (c) 2007 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
16 #include "firm_common.h"
18 #include "structure.h"
24 #include "irphase_t.h"
28 typedef union ir_reg_or_blk ir_reg_or_blk;
30 /* The structure tree. */
32 struct obstack obst; /**< The obstack where the data is allocated. */
33 ir_region *top; /**< The top region. */
34 ir_graph *irg; /**< Associated graph. */
39 firm_kind kind; /**< Must be k_ir_region. */
40 ir_region_kind type; /**< The type of this region. */
41 ir_region *parent; /**< points to the parent. */
42 ir_reg_or_blk *parts; /**< The list of all region parts. */
43 ir_region **pred; /**< The predecessor (control flow) regions of this region. */
44 ir_region **succ; /**< The successor (control flow) regions of this region. */
45 unsigned prenum; /**< DFS pre-oder number */
46 unsigned postnum; /**< DFS post-oder number */
47 void *link; /**< A link field. */
48 unsigned long nr; /**< for debugging */
49 char visited; /**< The visited flag. */
52 /* A helper type for unioning blocks and regions. */
54 firm_kind *kind; /**< For easier check. */
55 ir_node *blk; /**< A node */
56 ir_region *region; /**< A region. */
59 /* The debug handle. */
60 DEBUG_ONLY(firm_dbg_module_t *dbg;)
63 * Returns the link of a region.
65 void *get_region_link(const ir_region *reg) {
70 * Sets the link of a region.
72 void set_region_link(ir_region *reg, void *data) {
77 * Get the immediate region of a block.
79 ir_region *get_block_region(const ir_node *block) {
80 assert(is_Block(block));
81 return get_irn_link(block);
85 * Sets the immediate region of a block.
87 void set_block_region(ir_node *block, ir_region *reg) {
88 assert(is_Block(block));
89 set_irn_link(block, reg);
93 * Get the immediate region of a node.
95 ir_region *get_irn_region(ir_node *n) {
97 n = get_nodes_block(n);
98 return get_block_region(n);
102 * Return non-if a given firm thing is a region.
104 int is_region(const void *thing) {
105 const firm_kind *kind = thing;
106 return *kind == k_ir_region;
110 * Return the number of predecessors in a region.
112 int get_region_n_preds(const ir_region *reg) {
113 return ARR_LEN(reg->pred);
117 * Return the predecessor region at position pos.
119 ir_region *get_region_pred(const ir_region *reg, int pos) {
120 assert(0 <= pos && pos <= get_region_n_preds(reg));
121 return reg->pred[pos];
125 * Set the predecessor region at position pos.
127 void set_region_pred(ir_region *reg, int pos, ir_region *n) {
128 assert(0 <= pos && pos <= get_region_n_preds(reg));
133 * Return the number of successors in a region.
135 int get_region_n_succs(const ir_region *reg) {
136 return ARR_LEN(reg->succ);
140 * Return the successor region at position pos.
142 ir_region *get_region_succ(const ir_region *reg, int pos) {
143 assert(0 <= pos && pos <= get_region_n_succs(reg));
144 return reg->succ[pos];
148 * Set the successor region at position pos.
150 void set_region_succ(ir_region *reg, int pos, ir_region *n) {
151 assert(0 <= pos && pos <= get_region_n_succs(reg));
155 /* ----------------------- construction -------------------------- */
157 /** Walker environment. */
158 typedef struct walk_env {
159 struct obstack *obst; /**< an obstack to allocate from. */
160 ir_region **post; /**< The list of all currently existent top regions. */
161 unsigned l_post; /**< length of the allocated regions array. */
162 unsigned premax; /**< maximum pre counter */
163 unsigned postmax; /**< maximum post counter */
164 ir_node *start_block; /**< the start block of the graph. */
165 ir_node *end_block; /**< the end block of the graph. */
169 * Do a DFS search on the initial regions, assign a prenum and a postnum to every
170 * node and store the region nodes into the post array.
172 static void dfs_walk2(ir_region *reg, walk_env *env) {
175 if (reg->visited == 0) {
178 reg->prenum = env->premax++;
179 for (i = 0, n = get_region_n_succs(reg); i < n; ++i) {
181 ir_region *succ = get_region_succ(reg, i);
182 dfs_walk2(succ, env);
185 env->post[env->postmax] = reg;
186 reg->postnum = env->postmax++;
191 * Do a DFS search on the initial regions, assign a prenum and a postnum to every
192 * node and store the region nodes into the post array.
194 static void dfs_walk(ir_graph *irg, walk_env *env) {
195 ir_graph *rem = current_ir_graph;
198 current_ir_graph = irg;
199 reg = get_irn_link(get_irg_start_block(irg));
204 current_ir_graph = rem;
208 * Post-walker: wrap all blocks with a Block region
211 static void wrap_blocks(ir_node *block, void *ctx) {
215 /* Allocate a Block wrapper */
216 reg = obstack_alloc(env->obst, sizeof(*reg));
217 reg->kind = k_ir_region;
218 reg->type = ir_rk_Block;
224 reg->nr = get_irn_node_nr(block);
225 reg->parts = NEW_ARR_D(ir_reg_or_blk, env->obst, 1);
227 reg->parts[0].blk = block;
228 set_irn_link(block, reg);
234 * Create the pred and succ edges for Block wrapper.
235 * Kill edges to the Start and End blocks.
237 static void update_Block_regions(ir_node *blk, void *ctx) {
239 ir_region *reg = get_irn_link(blk);
242 if (blk == env->start_block) {
243 /* handle Firm's self loop */
244 reg->pred = NEW_ARR_D(ir_region *, env->obst, 0);
246 len = get_Block_n_cfgpreds(blk);
247 reg->pred = NEW_ARR_D(ir_region *, env->obst, len);
248 for (i = j = 0; i < len; ++i) {
249 ir_node *pred = get_Block_cfgpred_block(blk, i);
250 reg->pred[j++] = get_irn_link(pred);
252 ARR_SHRINKLEN(reg->pred, j);
255 len = get_Block_n_cfg_outs(blk);
256 reg->succ = NEW_ARR_D(ir_region *, env->obst, len);
257 for (i = j = 0; i < len; ++i) {
258 ir_node *succ = get_Block_cfg_out(blk, i);
259 reg->succ[j++] = get_irn_link(succ);
261 ARR_SHRINKLEN(reg->succ, j);
264 /** Allocate a new region of a obstack */
265 #define ALLOC_REG(obst, reg, tp) \
267 (reg) = obstack_alloc((obst), sizeof(*(reg))); \
268 (reg)->kind = k_ir_region; \
270 (reg)->parent = NULL; \
272 (reg)->postnum = 0; \
273 (reg)->visited = 0; \
274 (reg)->link = NULL; \
278 * Creates a new Sequence region.
280 static ir_region *new_Sequence(struct obstack *obst, ir_region *nset[]) {
282 int i, len = ARR_LEN(nset);
284 ALLOC_REG(obst, reg, ir_rk_Sequence);
286 reg->nr = nset[0]->nr;
287 reg->parts = CLONE_ARR_D(ir_reg_or_blk, obst, nset);
288 reg->pred = DUP_ARR_D(ir_region *, obst, nset[0]->pred);
289 reg->succ = DUP_ARR_D(ir_region *, obst, nset[len - 1]->succ);
291 for (i = 0; i < len; ++i) {
292 reg->parts[i].region = nset[i];
293 nset[i]->parent = reg;
297 DB((dbg, LEVEL_2, " Created Sequence "));
298 for (i = 0; i < len; ++i) {
299 DB((dbg, LEVEL_2, "(%u)", reg->parts[i].region->nr));
301 DB((dbg, LEVEL_2, "\n"));
307 * Create a new IfThenElse region.
309 static ir_region *new_IfThenElse(struct obstack *obst, ir_region *if_b, ir_region *then_b, ir_region *else_b) {
312 ALLOC_REG(obst, reg, ir_rk_IfThenElse);
315 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 3);
317 reg->parts[0].region = if_b; if_b->parent = reg;
318 reg->parts[1].region = then_b; then_b->parent = reg;
319 reg->parts[2].region = else_b; else_b->parent = reg;
321 reg->pred = DUP_ARR_D(ir_region *, obst, if_b->pred);
322 reg->succ = DUP_ARR_D(ir_region *, obst, then_b->succ);
324 DB((dbg, LEVEL_2, " Created If(%u)Then(%u)Else(%u)\n", reg->nr, then_b->nr, else_b->nr));
327 } /* new_IfThenElse */
330 * Create a new IfThen region.
332 static ir_region *new_IfThen(struct obstack *obst, ir_region *if_b, ir_region *then_b) {
335 ALLOC_REG(obst, reg, ir_rk_IfThen);
338 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 2);
340 reg->parts[0].region = if_b; if_b->parent = reg;
341 reg->parts[1].region = then_b; then_b->parent = reg;
343 reg->pred = DUP_ARR_D(ir_region *, obst, if_b->pred);
344 reg->succ = DUP_ARR_D(ir_region *, obst, then_b->succ);
346 DB((dbg, LEVEL_2, " Created If(%u)Then(%u)\n", reg->nr, then_b->nr));
349 } /* new_IfThenElse */
352 * Create a new Switch/case region.
354 static ir_region *new_SwitchCase(struct obstack *obst, ir_region_kind type, ir_region *head, ir_region *end, pset *cases) {
358 ALLOC_REG(obst, reg, type);
361 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, pset_count(cases) + 1);
363 reg->parts[0].region = head; head->parent = reg;
365 foreach_pset(cases, c) {
366 reg->parts[i].region = c;
370 reg->pred = DUP_ARR_D(ir_region *, obst, head->pred);
371 reg->succ = NEW_ARR_D(ir_region *, obst, 1);
374 DB((dbg, LEVEL_2, " Created Switch(%u)Exit(%u)\n", reg->nr, end->nr));
378 } /* new_SwitchCase */
381 * Create a new SelfLoop region.
383 static ir_region *new_SelfLoop(struct obstack *obst, ir_region *head) {
384 ir_region *reg, *succ;
387 ALLOC_REG(obst, reg, ir_rk_SelfLoop);
390 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 1);
392 reg->parts[0].region = head; head->parent = reg;
394 len = ARR_LEN(head->pred);
395 reg->pred = NEW_ARR_D(ir_region *, obst, len - 1);
396 for (i = j = 0; i < len; ++i) {
397 ir_region *pred = get_region_pred(head, i);
399 reg->pred[j++] = pred;
401 assert(j == len - 1);
403 reg->succ = NEW_ARR_D(ir_region *, obst, 1);
404 assert(ARR_LEN(head->succ) == 2);
406 succ = get_region_succ(head, 0);
410 reg->succ[0] = get_region_succ(head, 1);
412 DB((dbg, LEVEL_2, " Created SelfLoop(%u)\n", reg->nr));
418 * Create a new RepeatLoop region.
420 static ir_region *new_RepeatLoop(struct obstack *obst, ir_region *head, ir_region *body) {
421 ir_region *reg, *succ;
423 ALLOC_REG(obst, reg, ir_rk_RepeatLoop);
426 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 2);
428 reg->parts[0].region = head; head->parent = reg;
429 reg->parts[1].region = body; body->parent = reg;
431 reg->pred = DUP_ARR_D(ir_region *, obst, head->pred);
432 reg->succ = NEW_ARR_D(ir_region *, obst, 1);
433 assert(ARR_LEN(body->succ) == 2);
435 succ = get_region_succ(body, 0);
439 reg->succ[0] = get_region_succ(body, 1);
441 DB((dbg, LEVEL_2, " Created RepeatLoop(%u)Body(%u)\n", reg->nr, body->nr));
444 } /* new_RepeatLoop */
447 * Create a new WhileLoop region.
449 static ir_region *new_WhileLoop(struct obstack *obst, ir_region *head) {
450 ir_region *reg, *succ;
451 ir_region *body = head->link;
456 ALLOC_REG(obst, reg, ir_rk_WhileLoop);
459 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 2);
461 reg->parts[0].region = head; head->parent = reg;
462 reg->parts[1].region = body; body->parent = reg;
464 len = ARR_LEN(head->pred);
465 reg->pred = NEW_ARR_D(ir_region *, obst, len - 1);
466 for (i = j = 0; i < len; ++i) {
467 ir_region *pred = get_region_pred(head, i);
469 reg->pred[j++] = pred;
471 assert(j == len - 1);
473 reg->succ = NEW_ARR_D(ir_region *, obst, 1);
474 assert(ARR_LEN(head->succ) == 2);
476 succ = get_region_succ(head, 0);
480 reg->succ[0] = get_region_succ(head, 1);
482 DB((dbg, LEVEL_2, " Created WhileLoop(%u)Body(%u)\n", reg->nr, body->nr));
485 } /* new_WhileLoop */
488 * Return true if a is an ancestor of b in DFS search.
490 static int is_ancestor(const ir_region *a, const ir_region *b) {
491 return (a->prenum <= b->prenum && a->postnum > b->postnum);
495 * Return true if region succ is a successor of region n.
497 static int succ_of(const ir_region *succ, const ir_region *n) {
499 for (i = get_region_n_succs(n) - 1; i >= 0; --i) {
500 if (get_region_succ(n, i) == succ)
507 * Reverse linked list.
509 static struct ir_region *reverse_list(ir_region *n) {
510 ir_region *prev = NULL, *next;
512 for (; n; n = next) {
521 * Find the cyclic region in the subgraph entered by node.
523 static ir_region *find_cyclic_region(ir_region *node) {
525 ir_region *last = node;
528 for (i = get_region_n_preds(node) - 1; i >= 0; --i) {
529 ir_region *pred = get_region_pred(node, i);
531 /* search backedges */
532 if (!pred->link && pred != last && is_ancestor(node, pred)) {
533 ir_region *rem = last;
538 for (j = get_region_n_preds(pred) - 1; j >= 0; --j) {
539 ir_region *p = get_region_pred(pred, j);
541 /* Search regions we didn't visited yet and
542 link them into the list. */
543 if (!p->link && p != last) {
544 if (is_ancestor(node, p)) {
552 /* reverse the list. */
554 rem->link = reverse_list(rem->link);
558 if (node->link && improper) {
559 /* found an improper region */
564 #define LINK(list) ((ir_region *)list->link)
567 * Detect a cyclic region.
569 static ir_region *cyclic_region_type(struct obstack *obst, ir_region *node) {
572 /* simple cases first */
573 if (succ_of(node, node)) {
574 return new_SelfLoop(obst, node);
576 if (get_region_n_succs(node) == 1) {
577 ir_region *succ = get_region_succ(node, 0);
578 if (get_region_n_preds(succ) == 1 && succ_of(node, succ)) {
579 return new_RepeatLoop(obst, node, succ);
582 list = find_cyclic_region(node);
584 if (list->link && !LINK(list)->link && get_region_n_succs(list->link) == 1) {
585 return new_WhileLoop(obst, list);
592 * Detect an acyclic region.
594 static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node) {
597 ir_region **nset = NEW_ARR_F(ir_region *, 0);
601 /* check for a block containing node */
603 p = get_region_n_preds(n) == 1;
606 n = get_region_pred(n, 0);
607 p = get_region_n_preds(n) == 1;
608 s = get_region_n_succs(n) == 1;
611 s = get_region_n_succs(n) == 1;
613 ARR_APP1(ir_region *, nset, n);
614 n = get_region_succ(n, 0);
615 p = get_region_n_preds(n) == 1;
616 s = get_region_n_succs(n) == 1;
619 ARR_APP1(ir_region *, nset, n);
621 if (ARR_LEN(nset) >= 2) {
622 /* node --> .. --> .. */
623 res = new_Sequence(obst, nset);
630 /* check for IfThenElse */
631 k = get_region_n_succs(node);
633 int n_succs, m_succs, n_preds, m_preds;
635 n = get_region_succ(node, 0);
636 m = get_region_succ(node, 1);
638 n_succs = get_region_n_succs(n);
639 m_succs = get_region_n_succs(m);
640 n_preds = get_region_n_preds(n);
641 m_preds = get_region_n_preds(m);
642 if (n_succs == 1 && n_succs == m_succs && n_preds == m_preds &&
643 get_region_succ(n, 0) == get_region_succ(m, 0)) {
649 return new_IfThenElse(obst, node, n, m);
651 if (n_succs == 1 && m_preds == 2 &&
652 get_region_succ(n, 0) == m &&
653 (get_region_pred(m, 0) == node ||
654 get_region_pred(m, 1) == node)) {
659 return new_IfThen(obst, node, n);
661 if (m_succs == 1 && n_preds == 2 &&
662 get_region_succ(m, 0) == m &&
663 (get_region_pred(n, 0) == node ||
664 get_region_pred(n, 1) == node)) {
669 return new_IfThen(obst, node, m);
672 /* check for Switch, case */
673 set = pset_new_ptr_default();
675 for (i = k - 1; i >= 0; --i) {
676 n = get_region_succ(node, i);
677 pset_insert_ptr(set, n);
678 if (get_region_n_succs(n) != 1) {
684 ir_region_kind kind = ir_rk_Case;
687 if (pset_find_ptr(set, m) != NULL) {
688 /* must be a switch, if any, find the exit */
691 for (m = pset_next(set); m != NULL; m = pset_next(set)) {
692 if (pset_find_ptr(set, m) == NULL) {
699 /* m ist the exit, do the checks */
700 foreach_pset(set, n) {
702 /* good, switch to exit */
705 if (pset_find_ptr(set, n) == NULL) {
715 return new_SwitchCase(obst, kind, node, m, set);
719 /* check for proper */
725 * Fill the given set recursively with all parts of the region (including itself)
727 static void fill_parts(pset *set, ir_region *reg) {
730 if (reg->type == ir_rk_Block) {
731 pset_insert_ptr(set, reg);
735 for (i = ARR_LEN(reg->parts) - 1; i >= 0; --i) {
736 fill_parts(set, reg->parts[i].region);
741 * replace all pred edges from region pred that points to any of the set set
742 * to ONE edge to reg.
744 static void replace_pred(ir_region *succ, ir_region *reg) {
745 int i, len = get_region_n_preds(succ);
748 for (i = 0; i < len; ++i) {
749 ir_region *pred = get_region_pred(succ, i);
751 if (pred->parent == reg) {
756 r = get_region_pred(succ, --len);
762 set_region_pred(succ, i, r);
765 ARR_SHRINKLEN(succ->pred, len);
769 * replace all succ edges from region pred that points to any of the set set
770 * to ONE edge to reg.
772 static void replace_succ(ir_region *pred, ir_region *reg) {
773 int i, len = get_region_n_succs(pred);
776 for (i = 0; i < len; ++i) {
777 ir_region *succ = get_region_succ(pred, i);
779 if (succ->parent == reg) {
784 r = get_region_succ(pred, --len);
790 set_region_succ(pred, i, r);
793 ARR_SHRINKLEN(pred->succ, len);
797 * Reduce the graph by the node reg.
799 static void reduce(walk_env *env, ir_region *reg) {
801 ir_region *head = reg->parts[0].region;
802 unsigned maxorder = head->postnum;
803 unsigned minorder = head->prenum;
805 /* second step: replace all preds in successors */
806 for (i = get_region_n_succs(reg) - 1; i >= 0; --i) {
807 ir_region *succ = get_region_succ(reg, i);
809 replace_pred(succ, reg);
812 /* second third: replace all succs in predessors */
813 for (i = get_region_n_preds(reg) - 1; i >= 0; --i) {
814 ir_region *pred = get_region_pred(reg, i);
816 replace_succ(pred, reg);
819 reg->prenum = minorder;
820 reg->postnum = maxorder;
821 env->post[maxorder] = reg;
825 * Construct the region tree of a graph by doing
826 * structural analysis.
828 * Uses link fields of nodes.
830 * @param irg the graph
832 ir_reg_tree *construct_region_tree(ir_graph *irg) {
834 ir_graph *rem = current_ir_graph;
835 ir_reg_tree *res = xmalloc(sizeof(*res));
837 obstack_init(&res->obst);
839 current_ir_graph = irg;
841 FIRM_DBG_REGISTER(dbg, "firm.ana.structure");
842 firm_dbg_set_mask(dbg, SET_LEVEL_5);
844 DB((dbg, LEVEL_1, "Structural analysis on %+F starts...\n", irg));
846 dump_ir_block_graph(irg, "-structure_start");
848 /* we need dominance info */
851 assure_irg_outs(irg);
853 env.start_block = get_irg_start_block(irg);
854 env.end_block = get_irg_end_block(irg);
856 /* create the Block wrapper and count them */
858 env.obst = &res->obst;
859 irg_block_walk_graph(irg, NULL, wrap_blocks, &env);
860 irg_block_walk_graph(irg, NULL, update_Block_regions, &env);
862 env.post = NEW_ARR_F(ir_region *, env.l_post);
864 /* do the DFS walk */
867 DB((dbg, LEVEL_1, "%d regions left\n", env.postmax));
868 if (env.postmax > 1) {
869 unsigned postctr = 0;
871 ir_region *reg, *n = env.post[postctr];
877 /* locate an acyclic region if present */
878 reg = acyclic_region_type(env.obst, n);
880 /* locate a cyclic region */
881 reg = cyclic_region_type(env.obst, n);
884 /* found a new region */
888 } while (reg != NULL);
890 } while (postctr < env.postmax);
892 DB((dbg, LEVEL_1, "Structural analysis finished.\n"));
895 current_ir_graph = rem;
897 res->top = env.post[0];
903 * Walk over the region tree.
905 * @param reg a region node
906 * @param pre walker function, executed before the children of a tree node are visited
907 * @param post walker function, executed after the children of a tree node are visited
908 * @param env environment, passed to pre and post
910 static void region_tree_walk2(ir_region *reg, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env) {
915 if (reg->type != ir_rk_Block) {
916 for (i = 0, n = ARR_LEN(reg->parts); i < n; ++i)
917 region_tree_walk2(reg->parts[i].region, pre, post, env);
924 * Walk over the region tree.
926 * @param tree the tree
927 * @param pre walker function, executed before the children of a tree node are visited
928 * @param post walker function, executed after the children of a tree node are visited
929 * @param env environment, passed to pre and post
931 void region_tree_walk(ir_reg_tree *tree, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env) {
932 region_tree_walk2(tree->top, pre, post, env);