2 * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Structure Analysis
23 * @author Michael Beck
31 #include "firm_common.h"
33 #include "structure.h"
43 typedef union ir_reg_or_blk ir_reg_or_blk;
45 /* The structure tree. */
47 struct obstack obst; /**< The obstack where the data is allocated. */
48 ir_region *top; /**< The top region. */
49 ir_graph *irg; /**< Associated graph. */
54 firm_kind kind; /**< Must be k_ir_region. */
55 ir_region_kind type; /**< The type of this region. */
56 ir_region *parent; /**< points to the parent. */
57 ir_reg_or_blk *parts; /**< The list of all region parts. */
58 ir_region **pred; /**< The predecessor (control flow) regions of this region. */
59 ir_region **succ; /**< The successor (control flow) regions of this region. */
60 size_t prenum; /**< DFS pre-oder number */
61 size_t postnum; /**< DFS post-oder number */
62 void *link; /**< A link field. */
63 unsigned long nr; /**< for debugging */
64 unsigned visited:1; /**< The visited flag. */
65 unsigned exit:1; /**< If set, the parent region can be left by this node. */
66 unsigned enter:1; /**< If set, the parent region can be entered by this node. */
69 /* A helper type for unioning blocks and regions. */
71 firm_kind *kind; /**< For easier check. */
72 ir_node *blk; /**< A node */
73 ir_region *region; /**< A region. */
76 /* The debug handle. */
77 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
80 * Returns the link of a region.
82 void *get_region_link(const ir_region *reg)
88 * Sets the link of a region.
90 void set_region_link(ir_region *reg, void *data)
96 * Get the immediate region of a block.
98 ir_region *get_block_region(const ir_node *block)
100 assert(is_Block(block));
101 return block->attr.block.region;
105 * Sets the immediate region of a block.
107 void set_block_region(ir_node *block, ir_region *reg)
109 assert(is_Block(block));
110 block->attr.block.region = reg;
114 * Get the immediate region of a node.
116 ir_region *get_irn_region(ir_node *n)
119 n = get_nodes_block(n);
120 return get_block_region(n);
124 * Return non-zero if a given firm thing is a region.
126 int is_region(const void *thing)
128 const firm_kind *kind = (const firm_kind*) thing;
129 return *kind == k_ir_region;
133 * Return the number of predecessors of a region.
135 size_t get_region_n_preds(const ir_region *reg)
137 return ARR_LEN(reg->pred);
141 * Return the predecessor region at position pos.
143 ir_region *get_region_pred(const ir_region *reg, size_t pos)
145 assert(pos <= get_region_n_preds(reg));
146 return reg->pred[pos];
150 * Set the predecessor region at position pos.
152 void set_region_pred(ir_region *reg, size_t pos, ir_region *n)
154 assert(pos <= get_region_n_preds(reg));
159 * Return the number of successors in a region.
161 size_t get_region_n_succs(const ir_region *reg)
163 return ARR_LEN(reg->succ);
167 * Return the successor region at position pos.
169 ir_region *get_region_succ(const ir_region *reg, size_t pos)
171 assert(pos <= get_region_n_succs(reg));
172 return reg->succ[pos];
176 * Set the successor region at position pos.
178 void set_region_succ(ir_region *reg, size_t pos, ir_region *n)
180 assert(pos <= get_region_n_succs(reg));
184 /* ----------------------- construction -------------------------- */
186 /** Walker environment. */
187 typedef struct walk_env {
188 struct obstack *obst; /**< An obstack to allocate from. */
189 ir_region **post; /**< The list of all currently existent top regions. */
190 size_t l_post; /**< The length of the allocated regions array. */
191 size_t premax; /**< maximum pre counter */
192 size_t postmax; /**< maximum post counter */
193 ir_node *start_block; /**< The start block of the graph. */
194 ir_node *end_block; /**< The end block of the graph. */
198 * Do a DFS search on the initial regions, assign a prenum and a postnum to every
199 * node and store the region nodes into the post array.
201 static void dfs_walk2(ir_region *reg, walk_env *env)
205 if (reg->visited == 0) {
208 reg->prenum = env->premax++;
209 for (i = 0, n = get_region_n_succs(reg); i < n; ++i) {
211 ir_region *succ = get_region_succ(reg, i);
212 dfs_walk2(succ, env);
215 env->post[env->postmax] = reg;
216 reg->postnum = env->postmax++;
221 * Do a DFS search on the initial regions, assign a prenum and a postnum to every
222 * node and store the region nodes into the post array.
224 static void dfs_walk(ir_graph *irg, walk_env *env)
226 ir_graph *rem = current_ir_graph;
229 current_ir_graph = irg;
230 reg = (ir_region*) get_irn_link(get_irg_start_block(irg));
235 current_ir_graph = rem;
239 * Post-walker: wrap all blocks with a BasicBlock region
242 static void wrap_BasicBlocks(ir_node *block, void *ctx)
244 walk_env *env = (walk_env*) ctx;
247 /* Allocate a Block wrapper */
248 reg = OALLOC(env->obst, ir_region);
249 reg->kind = k_ir_region;
250 reg->type = ir_rk_BasicBlock;
258 reg->nr = get_irn_node_nr(block);
259 reg->parts = NEW_ARR_D(ir_reg_or_blk, env->obst, 1);
261 reg->parts[0].blk = block;
262 set_irn_link(block, reg);
265 } /* wrap_BasicBlocks */
268 * Post-walker: Create the pred and succ edges for Block wrapper.
269 * Kill edges to the Start and End blocks.
271 static void update_BasicBlock_regions(ir_node *blk, void *ctx)
273 walk_env *env = (walk_env*) ctx;
274 ir_region *reg = (ir_region*) get_irn_link(blk);
278 if (blk == env->start_block) {
279 /* handle Firm's self loop: Start block has no predecessors */
280 reg->pred = NEW_ARR_D(ir_region *, env->obst, 0);
282 len = get_Block_n_cfgpreds(blk);
283 reg->pred = NEW_ARR_D(ir_region *, env->obst, len);
284 for (j = i = 0; i < len; ++i) {
285 ir_node *pred = get_Block_cfgpred_block(blk, i);
286 reg->pred[j++] = (ir_region*) get_irn_link(pred);
288 ARR_SHRINKLEN(reg->pred, j);
291 len = get_Block_n_cfg_outs(blk);
292 reg->succ = NEW_ARR_D(ir_region *, env->obst, len);
293 for (j = i = 0; i < len; ++i) {
294 ir_node *succ = get_Block_cfg_out(blk, i);
295 reg->succ[j++] = (ir_region*) get_irn_link(succ);
297 ARR_SHRINKLEN(reg->succ, j);
298 } /* update_BasicBlock_regions */
300 /** Allocate a new region on an obstack */
301 static ir_region *alloc_region(struct obstack *obst, ir_region_kind type)
303 ir_region *reg = OALLOC(obst, ir_region);
304 reg->kind = k_ir_region;
318 * Creates a new Sequence region.
320 static ir_region *new_Sequence(struct obstack *obst, ir_region *nset, size_t nset_len)
322 ir_region *reg = alloc_region(obst, ir_rk_Sequence);
326 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, nset_len);
328 /* beware: list is in reverse order, reverse */
330 for (i = nset_len; i > 0;) {
333 reg->parts[i].region = nset;
335 next = (ir_region*) nset->link;
339 reg->nr = reg->parts[0].region->nr;
340 reg->pred = DUP_ARR_D(ir_region *, obst, reg->parts[0].region->pred);
341 reg->succ = DUP_ARR_D(ir_region *, obst, reg->parts[nset_len - 1].region->succ);
344 DB((dbg, LEVEL_2, " Created Sequence "));
345 for (i = 0; i < nset_len; ++i) {
346 DB((dbg, LEVEL_2, "(%lu)", reg->parts[i].region->nr));
348 DB((dbg, LEVEL_2, "\n"));
354 * Create a new IfThenElse region.
356 static ir_region *new_IfThenElse(struct obstack *obst, ir_region *if_b, ir_region *then_b, ir_region *else_b)
358 ir_region *reg = alloc_region(obst, ir_rk_IfThenElse);
361 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 3);
363 reg->parts[0].region = if_b; if_b->parent = reg;
364 reg->parts[1].region = then_b; then_b->parent = reg;
365 reg->parts[2].region = else_b; else_b->parent = reg;
367 reg->pred = DUP_ARR_D(ir_region *, obst, if_b->pred);
368 reg->succ = DUP_ARR_D(ir_region *, obst, then_b->succ);
370 DB((dbg, LEVEL_2, " Created If(%lu)Then(%lu)Else(%lu)\n", reg->nr, then_b->nr, else_b->nr));
373 } /* new_IfThenElse */
376 * Create a new IfThen region.
378 static ir_region *new_IfThen(struct obstack *obst, ir_region *if_b, ir_region *then_b)
380 ir_region *reg = alloc_region(obst, ir_rk_IfThen);
383 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 2);
385 reg->parts[0].region = if_b; if_b->parent = reg;
386 reg->parts[1].region = then_b; then_b->parent = reg;
388 reg->pred = DUP_ARR_D(ir_region *, obst, if_b->pred);
389 reg->succ = DUP_ARR_D(ir_region *, obst, then_b->succ);
391 DB((dbg, LEVEL_2, " Created If(%lu)Then(%lu)\n", reg->nr, then_b->nr));
394 } /* new_IfThenElse */
397 * Create a new Switch/case region.
399 static ir_region *new_SwitchCase(struct obstack *obst, ir_region_kind type, ir_region *head, ir_region *exit,
400 ir_region *cases, size_t cases_len)
402 ir_region *reg = alloc_region(obst, type);
407 /* check, if the exit block is in the list */
408 for (c = cases; c != NULL; c = (ir_region*) c->link) {
416 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, cases_len + add);
418 reg->parts[0].region = head; head->parent = reg;
420 for (c = cases; c != NULL; c = n) {
421 n = (ir_region*) c->link;
423 reg->parts[i++].region = c;
429 reg->pred = DUP_ARR_D(ir_region *, obst, head->pred);
430 reg->succ = NEW_ARR_D(ir_region *, obst, 1);
434 DB((dbg, LEVEL_2, " Created %s(%u)\n", reg->type == ir_rk_Switch ? "Switch" : "Case", reg->nr));
435 for (i = 1; i < ARR_LEN(reg->parts); ++i) {
436 DB((dbg, LEVEL_2, " Case(%lu)\n", reg->parts[i].region->nr));
438 DB((dbg, LEVEL_2, " Exit(%lu)\n", exit->nr));
441 } /* new_SwitchCase */
444 * Create a new SelfLoop region.
446 static ir_region *new_SelfLoop(struct obstack *obst, ir_region *head)
448 ir_region *reg = alloc_region(obst, ir_rk_SelfLoop);
453 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 1);
455 reg->parts[0].region = head; head->parent = reg;
457 len = ARR_LEN(head->pred);
458 reg->pred = NEW_ARR_D(ir_region *, obst, len - 1);
459 for (i = j = 0; i < len; ++i) {
460 ir_region *pred = get_region_pred(head, i);
462 reg->pred[j++] = pred;
464 assert(j == len - 1);
466 reg->succ = NEW_ARR_D(ir_region *, obst, 1);
467 assert(ARR_LEN(head->succ) == 2);
469 succ = get_region_succ(head, 0);
473 reg->succ[0] = get_region_succ(head, 1);
475 DB((dbg, LEVEL_2, " Created SelfLoop(%lu)\n", reg->nr));
481 * Create a new RepeatLoop region.
483 static ir_region *new_RepeatLoop(struct obstack *obst, ir_region *head, ir_region *body)
485 ir_region *reg = alloc_region(obst, ir_rk_RepeatLoop);
489 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 2);
491 reg->parts[0].region = head; head->parent = reg;
492 reg->parts[1].region = body; body->parent = reg;
494 reg->pred = DUP_ARR_D(ir_region *, obst, head->pred);
495 reg->succ = NEW_ARR_D(ir_region *, obst, 1);
496 assert(ARR_LEN(body->succ) == 2);
498 succ = get_region_succ(body, 0);
502 reg->succ[0] = get_region_succ(body, 1);
504 DB((dbg, LEVEL_2, " Created RepeatLoop(%lu)Body(%lu)\n", reg->nr, body->nr));
507 } /* new_RepeatLoop */
510 * Create a new WhileLoop region.
512 static ir_region *new_WhileLoop(struct obstack *obst, ir_region *head)
514 ir_region *reg = alloc_region(obst, ir_rk_WhileLoop);
515 ir_region *body = (ir_region*) head->link;
522 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 2);
524 reg->parts[0].region = head; head->parent = reg;
525 reg->parts[1].region = body; body->parent = reg;
527 len = ARR_LEN(head->pred);
528 reg->pred = NEW_ARR_D(ir_region *, obst, len - 1);
529 for (i = j = 0; i < len; ++i) {
530 ir_region *pred = get_region_pred(head, i);
532 reg->pred[j++] = pred;
534 assert(j == len - 1);
536 reg->succ = NEW_ARR_D(ir_region *, obst, 1);
537 assert(ARR_LEN(head->succ) == 2);
539 succ = get_region_succ(head, 0);
543 reg->succ[0] = get_region_succ(head, 1);
545 DB((dbg, LEVEL_2, " Created WhileLoop(%lu)Body(%lu)\n", reg->nr, body->nr));
548 } /* new_WhileLoop */
551 * Create a new new_NaturalLoop region.
553 static ir_region *new_NaturalLoop(struct obstack *obst, ir_region *head)
555 ir_region *reg = alloc_region(obst, ir_rk_WhileLoop);
557 size_t i, j, k, len, n_pred, n_succ;
559 /* count number of parts */
560 for (len = 0, c = head; c != NULL; c = (ir_region*) c->link)
564 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, len);
566 /* enter all parts */
567 for (i = 0, c = head; c != NULL; c = n) {
568 reg->parts[i++].region = c;
570 n = (ir_region*) c->link;
574 /* count number of preds */
576 for (i = get_region_n_preds(head); i > 0;) {
577 ir_region *pred = get_region_pred(head, --i);
578 if (pred->parent != reg)
581 reg->pred = NEW_ARR_D(ir_region *, obst, n_pred);
582 for (j = 0, i = get_region_n_preds(head); i > 0;) {
583 ir_region *pred = get_region_pred(head, --i);
584 if (pred->parent != reg)
585 reg->pred[j++] = pred;
588 /* count number of succs */
590 for (j = 0; j < len; ++j) {
591 ir_region *pc = reg->parts[j].region;
592 for (i = get_region_n_succs(pc); i > 0;) {
593 ir_region *succ = get_region_succ(pc, --i);
594 if (succ->parent != reg)
598 reg->succ = NEW_ARR_D(ir_region *, obst, n_succ);
600 for (j = 0; j < len; ++j) {
601 ir_region *pc = reg->parts[j].region;
602 for (i = get_region_n_succs(pc); i > 0;) {
603 ir_region *succ = get_region_succ(pc, --i);
604 if (succ->parent != reg)
605 reg->succ[k++] = succ;
610 DB((dbg, LEVEL_2, " Created NaturalLoop(%u)Head(%u)\n", reg->nr, head->nr));
611 for (i = 1; i < len; ++i) {
612 ir_region *p = reg->parts[i].region;
613 DB((dbg, LEVEL_2, " Body(%u)\n", p->nr));
617 } /* new_NaturalLoop */
620 * Return true if region a is an ancestor of region b in DFS search.
622 static int is_ancestor(const ir_region *a, const ir_region *b)
624 return (a->prenum <= b->prenum && a->postnum > b->postnum);
628 * Return true if region pred is a predecessor of region n.
630 static bool pred_of(const ir_region *pred, const ir_region *n)
633 for (i = 0, n_preds = get_region_n_preds(n); i < n_preds; ++i) {
634 if (get_region_pred(n, i) == pred)
641 * Return true if region succ is a successor of region n.
643 static bool succ_of(const ir_region *succ, const ir_region *n)
646 for (i = 0, n_succs = get_region_n_succs(n); i < n_succs; ++i) {
647 if (get_region_succ(n, i) == succ)
654 * Reverse a linked list of regions.
656 static struct ir_region *reverse_list(ir_region *n)
658 ir_region *prev = NULL, *next;
660 for (; n; n = next) {
661 next = (ir_region*) n->link;
669 * Find the cyclic region in the subgraph entered by node.
671 static ir_region *find_cyclic_region(ir_region *node)
674 ir_region *last = node;
677 for (i = get_region_n_preds(node); i > 0;) {
678 ir_region *pred = get_region_pred(node, --i);
680 /* search backedges */
681 if (!pred->link && pred != last && is_ancestor(node, pred)) {
682 ir_region *rem = last;
687 for (j = get_region_n_preds(pred); j > 0;) {
688 ir_region *p = get_region_pred(pred, --j);
690 /* Search regions we didn't visited yet and
691 link them into the list. */
692 if (!p->link && p != last) {
693 if (is_ancestor(node, p)) {
701 /* reverse the list. */
702 last = (ir_region*) rem->link;
703 rem->link = reverse_list(last);
707 if (node->link && improper) {
708 /* found an improper region, do minimization */
715 * Detect a cyclic region.
717 static ir_region *cyclic_region_type(struct obstack *obst, ir_region *node)
719 ir_region *list, *next;
721 /* simple cases first */
722 if (succ_of(node, node)) {
723 return new_SelfLoop(obst, node);
725 if (get_region_n_succs(node) == 1) {
726 ir_region *succ = get_region_succ(node, 0);
727 if (get_region_n_preds(succ) == 1 && succ_of(node, succ)) {
728 return new_RepeatLoop(obst, node, succ);
731 list = find_cyclic_region(node);
733 next = (ir_region*) list->link;
735 if (!next->link && get_region_n_succs(next) == 1) {
736 /* only one body block with only one successor (the head) */
737 return new_WhileLoop(obst, list);
739 /* A Loop with one head */
740 return new_NaturalLoop(obst, list);
747 * Clear all links on a list. Needed, because we expect cleared links.
749 static void clear_list(ir_region *list)
753 for (next = list; next; list = next) {
754 next = (ir_region*) list->link;
759 #define ADD_LIST(list, n) do { n->link = list; list = n; ++list##_len; } while (0)
762 * Detect an acyclic region.
764 static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node)
769 ir_region *nset = NULL;
773 /* check for a block containing node */
775 p = get_region_n_preds(n) == 1;
778 n = get_region_pred(n, 0);
779 p = get_region_n_preds(n) == 1;
780 s = get_region_n_succs(n) == 1;
783 s = get_region_n_succs(n) == 1;
786 n = get_region_succ(n, 0);
787 p = get_region_n_preds(n) == 1;
788 s = get_region_n_succs(n) == 1;
794 /* node --> .. --> .. */
795 res = new_Sequence(obst, nset, nset_len);
800 /* check for IfThenElse */
801 k = get_region_n_succs(node);
803 size_t n_succs, m_succs, n_preds, m_preds;
805 n = get_region_succ(node, 0);
806 m = get_region_succ(node, 1);
808 n_succs = get_region_n_succs(n);
809 m_succs = get_region_n_succs(m);
810 n_preds = get_region_n_preds(n);
811 m_preds = get_region_n_preds(m);
812 if (n_succs == 1 && n_succs == m_succs && n_preds == m_preds &&
813 get_region_succ(n, 0) == get_region_succ(m, 0)) {
819 return new_IfThenElse(obst, node, n, m);
822 get_region_succ(n, 0) == m &&
828 return new_IfThen(obst, node, n);
831 get_region_succ(m, 0) == m &&
837 return new_IfThen(obst, node, m);
840 /* check for Switch, case */
842 ir_region *rexit = NULL;
844 nset = NULL; nset_len = 0;
845 for (i = k; i > 0;) {
846 n = get_region_succ(node, i--);
848 if (get_region_n_succs(n) != 1) {
849 /* must be the exit */
857 ir_region_kind kind = ir_rk_Case;
858 ir_region *pos_exit_1 = NULL;
859 ir_region *pos_exit_2 = NULL;
862 for (m = nset; m != NULL; m = (ir_region*) m->link) {
863 if (get_region_n_succs(m) != 1) {
864 /* must be the exit block */
867 } else if (rexit != m) {
873 ir_region *succ = get_region_succ(m, 0);
875 if (succ->link == NULL) {
877 if (succ == pos_exit_1)
879 else if (succ == pos_exit_2)
881 else if (pos_exit_1 == NULL)
883 else if (pos_exit_2 == NULL)
886 /* more than two possible exits */
889 } else if (rexit != succ) {
899 for (n = nset; n != NULL; n = (ir_region*) n->link) {
902 /* good, default fall through */
905 succ = get_region_succ(n, 0);
907 /* good, switch to exit */
910 if (succ->link == NULL) {
921 return new_SwitchCase(obst, kind, node, rexit, nset, nset_len);
931 * replace all pred edges from region pred that points to any of the set set
932 * to ONE edge to reg.
934 static void replace_pred(ir_region *succ, ir_region *reg)
937 size_t len = get_region_n_preds(succ);
940 for (i = 0; i < len; ++i) {
941 ir_region *pred = get_region_pred(succ, i);
943 if (pred->parent == reg) {
948 r = get_region_pred(succ, --len);
954 set_region_pred(succ, i, r);
956 /* the current region can be entered by this node */
960 ARR_SHRINKLEN(succ->pred, len);
964 * replace all succ edges from region pred that points to any of the set set
965 * to ONE edge to reg.
967 static void replace_succ(ir_region *pred, ir_region *reg)
970 size_t len = get_region_n_succs(pred);
973 for (i = 0; i < len; ++i) {
974 ir_region *succ = get_region_succ(pred, i);
976 if (succ->parent == reg) {
981 r = get_region_succ(pred, --len);
987 set_region_succ(pred, i, r);
989 /* current region can be left by this node */
993 ARR_SHRINKLEN(pred->succ, len);
997 * Reduce the graph by the node reg.
999 static void reduce(walk_env *env, ir_region *reg)
1002 ir_region *head = reg->parts[0].region;
1003 size_t maxorder = head->postnum;
1004 size_t minorder = head->prenum;
1006 /* second step: replace all preds in successors */
1007 for (i = get_region_n_succs(reg); i > 0;) {
1008 ir_region *succ = get_region_succ(reg, --i);
1010 replace_pred(succ, reg);
1013 /* third step: replace all succs in predessors */
1014 for (i = get_region_n_preds(reg); i > 0;) {
1015 ir_region *pred = get_region_pred(reg, --i);
1017 replace_succ(pred, reg);
1020 reg->prenum = minorder;
1021 reg->postnum = maxorder;
1022 env->post[maxorder] = reg;
1026 * Construct the region tree of a graph by doing
1027 * structural analysis.
1029 * Uses link fields of nodes.
1031 * @param irg the graph
1033 ir_reg_tree *construct_region_tree(ir_graph *irg)
1036 ir_graph *rem = current_ir_graph;
1037 ir_reg_tree *res = XMALLOC(ir_reg_tree);
1039 obstack_init(&res->obst);
1041 current_ir_graph = irg;
1043 FIRM_DBG_REGISTER(dbg, "firm.ana.structure");
1044 firm_dbg_set_mask(dbg, SET_LEVEL_5);
1046 DB((dbg, LEVEL_1, "Structural analysis on %+F started ...\n", irg));
1048 /* we need dominance info */
1051 assure_irg_outs(irg);
1053 env.start_block = get_irg_start_block(irg);
1054 env.end_block = get_irg_end_block(irg);
1056 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
1058 /* create the Block wrapper and count them */
1060 env.obst = &res->obst;
1061 irg_block_walk_graph(irg, NULL, wrap_BasicBlocks, &env);
1062 irg_block_walk_graph(irg, NULL, update_BasicBlock_regions, &env);
1064 env.post = NEW_ARR_F(ir_region *, env.l_post);
1066 /* do the DFS walk */
1067 dfs_walk(irg, &env);
1069 DB((dbg, LEVEL_1, "%zu regions left\n", env.postmax));
1070 if (env.postmax > 1) {
1073 ir_region *reg, *n = env.post[postctr];
1075 if (n->parent != NULL) {
1076 /* already folded */
1079 /* locate an acyclic region if present */
1080 reg = acyclic_region_type(env.obst, n);
1082 /* locate a cyclic region */
1083 reg = cyclic_region_type(env.obst, n);
1086 /* found a new region */
1090 } while (reg != NULL);
1092 } while (postctr < env.postmax);
1094 DB((dbg, LEVEL_1, "Structural analysis finished.\n"));
1096 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
1098 DEL_ARR_F(env.post);
1099 current_ir_graph = rem;
1101 res->top = env.post[0];
1107 * Walk over the region tree.
1109 * @param reg a region node
1110 * @param pre walker function, executed before the children of a tree node are visited
1111 * @param post walker function, executed after the children of a tree node are visited
1112 * @param env environment, passed to pre and post
1114 static void region_tree_walk2(ir_region *reg, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env)
1120 if (reg->type != ir_rk_BasicBlock) {
1121 for (i = 0, n = ARR_LEN(reg->parts); i < n; ++i)
1122 region_tree_walk2(reg->parts[i].region, pre, post, env);
1129 * Walk over the region tree.
1131 * @param tree the tree
1132 * @param pre walker function, executed before the children of a tree node are visited
1133 * @param post walker function, executed after the children of a tree node are visited
1134 * @param env environment, passed to pre and post
1136 void region_tree_walk(ir_reg_tree *tree, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env)
1138 region_tree_walk2(tree->top, pre, post, env);