2 * Copyright (C) 1995-2007 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 unsigned prenum; /**< DFS pre-oder number */
61 unsigned 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(firm_dbg_module_t *dbg;)
80 * Returns the link of a region.
82 void *get_region_link(const ir_region *reg) {
87 * Sets the link of a region.
89 void set_region_link(ir_region *reg, void *data) {
94 * Get the immediate region of a block.
96 ir_region *get_block_region(const ir_node *block) {
97 assert(is_Block(block));
98 return block->attr.block.region;
102 * Sets the immediate region of a block.
104 void set_block_region(ir_node *block, ir_region *reg) {
105 assert(is_Block(block));
106 block->attr.block.region = reg;
110 * Get the immediate region of a node.
112 ir_region *get_irn_region(ir_node *n) {
114 n = get_nodes_block(n);
115 return get_block_region(n);
119 * Return non-if a given firm thing is a region.
121 int is_region(const void *thing) {
122 const firm_kind *kind = thing;
123 return *kind == k_ir_region;
127 * Return the number of predecessors in a region.
129 int get_region_n_preds(const ir_region *reg) {
130 return ARR_LEN(reg->pred);
134 * Return the predecessor region at position pos.
136 ir_region *get_region_pred(const ir_region *reg, int pos) {
137 assert(0 <= pos && pos <= get_region_n_preds(reg));
138 return reg->pred[pos];
142 * Set the predecessor region at position pos.
144 void set_region_pred(ir_region *reg, int pos, ir_region *n) {
145 assert(0 <= pos && pos <= get_region_n_preds(reg));
150 * Return the number of successors in a region.
152 int get_region_n_succs(const ir_region *reg) {
153 return ARR_LEN(reg->succ);
157 * Return the successor region at position pos.
159 ir_region *get_region_succ(const ir_region *reg, int pos) {
160 assert(0 <= pos && pos <= get_region_n_succs(reg));
161 return reg->succ[pos];
165 * Set the successor region at position pos.
167 void set_region_succ(ir_region *reg, int pos, ir_region *n) {
168 assert(0 <= pos && pos <= get_region_n_succs(reg));
172 /* ----------------------- construction -------------------------- */
174 /** Walker environment. */
175 typedef struct walk_env {
176 struct obstack *obst; /**< an obstack to allocate from. */
177 ir_region **post; /**< The list of all currently existent top regions. */
178 unsigned l_post; /**< length of the allocated regions array. */
179 unsigned premax; /**< maximum pre counter */
180 unsigned postmax; /**< maximum post counter */
181 ir_node *start_block; /**< the start block of the graph. */
182 ir_node *end_block; /**< the end block of the graph. */
186 * Do a DFS search on the initial regions, assign a prenum and a postnum to every
187 * node and store the region nodes into the post array.
189 static void dfs_walk2(ir_region *reg, walk_env *env) {
192 if (reg->visited == 0) {
195 reg->prenum = env->premax++;
196 for (i = 0, n = get_region_n_succs(reg); i < n; ++i) {
198 ir_region *succ = get_region_succ(reg, i);
199 dfs_walk2(succ, env);
202 env->post[env->postmax] = reg;
203 reg->postnum = env->postmax++;
208 * Do a DFS search on the initial regions, assign a prenum and a postnum to every
209 * node and store the region nodes into the post array.
211 static void dfs_walk(ir_graph *irg, walk_env *env) {
212 ir_graph *rem = current_ir_graph;
215 current_ir_graph = irg;
216 reg = get_irn_link(get_irg_start_block(irg));
221 current_ir_graph = rem;
225 * Post-walker: wrap all blocks with a BasicBlock region
228 static void wrap_BasicBlocks(ir_node *block, void *ctx) {
232 /* Allocate a Block wrapper */
233 reg = obstack_alloc(env->obst, sizeof(*reg));
234 reg->kind = k_ir_region;
235 reg->type = ir_rk_BasicBlock;
243 reg->nr = get_irn_node_nr(block);
244 reg->parts = NEW_ARR_D(ir_reg_or_blk, env->obst, 1);
246 reg->parts[0].blk = block;
247 set_irn_link(block, reg);
250 } /* wrap_BasicBlocks */
253 * Create the pred and succ edges for Block wrapper.
254 * Kill edges to the Start and End blocks.
256 static void update_BasicBlock_regions(ir_node *blk, void *ctx) {
258 ir_region *reg = get_irn_link(blk);
261 if (blk == env->start_block) {
262 /* handle Firm's self loop */
263 reg->pred = NEW_ARR_D(ir_region *, env->obst, 0);
265 len = get_Block_n_cfgpreds(blk);
266 reg->pred = NEW_ARR_D(ir_region *, env->obst, len);
267 for (i = j = 0; i < len; ++i) {
268 ir_node *pred = get_Block_cfgpred_block(blk, i);
269 reg->pred[j++] = get_irn_link(pred);
271 ARR_SHRINKLEN(reg->pred, j);
274 len = get_Block_n_cfg_outs(blk);
275 reg->succ = NEW_ARR_D(ir_region *, env->obst, len);
276 for (i = j = 0; i < len; ++i) {
277 ir_node *succ = get_Block_cfg_out(blk, i);
278 reg->succ[j++] = get_irn_link(succ);
280 ARR_SHRINKLEN(reg->succ, j);
281 } /* update_BasicBlock_regions */
283 /** Allocate a new region of a obstack */
284 #define ALLOC_REG(obst, reg, tp) \
286 (reg) = obstack_alloc((obst), sizeof(*(reg))); \
287 (reg)->kind = k_ir_region; \
289 (reg)->parent = NULL; \
291 (reg)->postnum = 0; \
292 (reg)->visited = 0; \
295 (reg)->link = NULL; \
299 * Creates a new Sequence region.
301 static ir_region *new_Sequence(struct obstack *obst, ir_region *nset, int nset_len) {
302 ir_region *reg, *next;
305 ALLOC_REG(obst, reg, ir_rk_Sequence);
307 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, nset_len);
309 /* beware: list is in reverse order, reverse */
311 for (i = nset_len - 1; i >= 0; --i) {
313 reg->parts[i].region = nset;
319 reg->nr = reg->parts[0].region->nr;
320 reg->pred = DUP_ARR_D(ir_region *, obst, reg->parts[0].region->pred);
321 reg->succ = DUP_ARR_D(ir_region *, obst, reg->parts[nset_len - 1].region->succ);
324 DB((dbg, LEVEL_2, " Created Sequence "));
325 for (i = 0; i < nset_len; ++i) {
326 DB((dbg, LEVEL_2, "(%u)", reg->parts[i].region->nr));
328 DB((dbg, LEVEL_2, "\n"));
334 * Create a new IfThenElse region.
336 static ir_region *new_IfThenElse(struct obstack *obst, ir_region *if_b, ir_region *then_b, ir_region *else_b) {
339 ALLOC_REG(obst, reg, ir_rk_IfThenElse);
342 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 3);
344 reg->parts[0].region = if_b; if_b->parent = reg;
345 reg->parts[1].region = then_b; then_b->parent = reg;
346 reg->parts[2].region = else_b; else_b->parent = reg;
348 reg->pred = DUP_ARR_D(ir_region *, obst, if_b->pred);
349 reg->succ = DUP_ARR_D(ir_region *, obst, then_b->succ);
351 DB((dbg, LEVEL_2, " Created If(%u)Then(%u)Else(%u)\n", reg->nr, then_b->nr, else_b->nr));
354 } /* new_IfThenElse */
357 * Create a new IfThen region.
359 static ir_region *new_IfThen(struct obstack *obst, ir_region *if_b, ir_region *then_b) {
362 ALLOC_REG(obst, reg, ir_rk_IfThen);
365 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 2);
367 reg->parts[0].region = if_b; if_b->parent = reg;
368 reg->parts[1].region = then_b; then_b->parent = reg;
370 reg->pred = DUP_ARR_D(ir_region *, obst, if_b->pred);
371 reg->succ = DUP_ARR_D(ir_region *, obst, then_b->succ);
373 DB((dbg, LEVEL_2, " Created If(%u)Then(%u)\n", reg->nr, then_b->nr));
376 } /* new_IfThenElse */
379 * Create a new Switch/case region.
381 static ir_region *new_SwitchCase(struct obstack *obst, ir_region_kind type, ir_region *head, ir_region *exit,
382 ir_region *cases, int cases_len) {
383 ir_region *reg, *c, *n;
387 /* check, if the exit block is in the list */
388 for (c = cases; c != NULL; c = c->link) {
395 ALLOC_REG(obst, reg, type);
398 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, cases_len + add);
400 reg->parts[0].region = head; head->parent = reg;
402 for (c = cases; c != NULL; c = n) {
405 reg->parts[i++].region = c;
411 reg->pred = DUP_ARR_D(ir_region *, obst, head->pred);
412 reg->succ = NEW_ARR_D(ir_region *, obst, 1);
416 DB((dbg, LEVEL_2, " Created %s(%u)\n", reg->type == ir_rk_Switch ? "Switch" : "Case", reg->nr));
417 for (i = 1; i < ARR_LEN(reg->parts); ++i) {
418 DB((dbg, LEVEL_2, " Case(%u)\n", reg->parts[i].region->nr));
420 DB((dbg, LEVEL_2, " Exit(%u)\n", exit->nr));
423 } /* new_SwitchCase */
426 * Create a new SelfLoop region.
428 static ir_region *new_SelfLoop(struct obstack *obst, ir_region *head) {
429 ir_region *reg, *succ;
432 ALLOC_REG(obst, reg, ir_rk_SelfLoop);
435 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 1);
437 reg->parts[0].region = head; head->parent = reg;
439 len = ARR_LEN(head->pred);
440 reg->pred = NEW_ARR_D(ir_region *, obst, len - 1);
441 for (i = j = 0; i < len; ++i) {
442 ir_region *pred = get_region_pred(head, i);
444 reg->pred[j++] = pred;
446 assert(j == len - 1);
448 reg->succ = NEW_ARR_D(ir_region *, obst, 1);
449 assert(ARR_LEN(head->succ) == 2);
451 succ = get_region_succ(head, 0);
455 reg->succ[0] = get_region_succ(head, 1);
457 DB((dbg, LEVEL_2, " Created SelfLoop(%u)\n", reg->nr));
463 * Create a new RepeatLoop region.
465 static ir_region *new_RepeatLoop(struct obstack *obst, ir_region *head, ir_region *body) {
466 ir_region *reg, *succ;
468 ALLOC_REG(obst, reg, ir_rk_RepeatLoop);
471 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 2);
473 reg->parts[0].region = head; head->parent = reg;
474 reg->parts[1].region = body; body->parent = reg;
476 reg->pred = DUP_ARR_D(ir_region *, obst, head->pred);
477 reg->succ = NEW_ARR_D(ir_region *, obst, 1);
478 assert(ARR_LEN(body->succ) == 2);
480 succ = get_region_succ(body, 0);
484 reg->succ[0] = get_region_succ(body, 1);
486 DB((dbg, LEVEL_2, " Created RepeatLoop(%u)Body(%u)\n", reg->nr, body->nr));
489 } /* new_RepeatLoop */
492 * Create a new WhileLoop region.
494 static ir_region *new_WhileLoop(struct obstack *obst, ir_region *head) {
495 ir_region *reg, *succ;
496 ir_region *body = head->link;
501 ALLOC_REG(obst, reg, ir_rk_WhileLoop);
504 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 2);
506 reg->parts[0].region = head; head->parent = reg;
507 reg->parts[1].region = body; body->parent = reg;
509 len = ARR_LEN(head->pred);
510 reg->pred = NEW_ARR_D(ir_region *, obst, len - 1);
511 for (i = j = 0; i < len; ++i) {
512 ir_region *pred = get_region_pred(head, i);
514 reg->pred[j++] = pred;
516 assert(j == len - 1);
518 reg->succ = NEW_ARR_D(ir_region *, obst, 1);
519 assert(ARR_LEN(head->succ) == 2);
521 succ = get_region_succ(head, 0);
525 reg->succ[0] = get_region_succ(head, 1);
527 DB((dbg, LEVEL_2, " Created WhileLoop(%u)Body(%u)\n", reg->nr, body->nr));
530 } /* new_WhileLoop */
533 * Create a new new_NaturalLoop region.
535 static ir_region *new_NaturalLoop(struct obstack *obst, ir_region *head) {
536 ir_region *reg, *c, *n;
537 int i, j, k, len, n_pred, n_succ;
539 /* count number of parts */
540 for (len = 0, c = head; c != NULL; c = c->link)
543 ALLOC_REG(obst, reg, ir_rk_WhileLoop);
546 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, len);
548 /* enter all parts */
549 for (i = 0, c = head; c != NULL; c = n) {
550 reg->parts[i++].region = c;
556 /* count number of preds */
558 for (i = get_region_n_preds(head) - 1; i >= 0; --i) {
559 ir_region *pred = get_region_pred(head, i);
560 if (pred->parent != reg)
563 reg->pred = NEW_ARR_D(ir_region *, obst, n_pred);
564 for (j = 0, i = get_region_n_preds(head) - 1; i >= 0; --i) {
565 ir_region *pred = get_region_pred(head, i);
566 if (pred->parent != reg)
567 reg->pred[j++] = pred;
570 /* count number of succs */
572 for (j = 0; j < len; ++j) {
573 ir_region *c = reg->parts[j].region;
574 for (i = get_region_n_succs(c) - 1; i >= 0; --i) {
575 ir_region *succ = get_region_succ(c, i);
576 if (succ->parent != reg)
580 reg->succ = NEW_ARR_D(ir_region *, obst, n_succ);
582 for (j = 0; j < len; ++j) {
583 ir_region *c = reg->parts[j].region;
584 for (i = get_region_n_succs(c) - 1; i >= 0; --i) {
585 ir_region *succ = get_region_succ(c, i);
586 if (succ->parent != reg)
587 reg->succ[k++] = succ;
592 DB((dbg, LEVEL_2, " Created NaturalLoop(%u)Head(%u)\n", reg->nr, head->nr));
593 for (i = 1; i < len; ++i) {
594 ir_region *p = reg->parts[i].region;
595 DB((dbg, LEVEL_2, " Body(%u)\n", p->nr));
599 } /* new_NaturalLoop */
602 * Return true if a is an ancestor of b in DFS search.
604 static int is_ancestor(const ir_region *a, const ir_region *b) {
605 return (a->prenum <= b->prenum && a->postnum > b->postnum);
609 * Return true if region pred is a predecessor of region n.
611 static int pred_of(const ir_region *pred, const ir_region *n) {
613 for (i = get_region_n_preds(n) - 1; i >= 0; --i) {
614 if (get_region_pred(n, i) == pred)
621 * Return true if region succ is a successor of region n.
623 static int succ_of(const ir_region *succ, const ir_region *n) {
625 for (i = get_region_n_succs(n) - 1; i >= 0; --i) {
626 if (get_region_succ(n, i) == succ)
633 * Reverse linked list.
635 static struct ir_region *reverse_list(ir_region *n) {
636 ir_region *prev = NULL, *next;
638 for (; n; n = next) {
647 * Find the cyclic region in the subgraph entered by node.
649 static ir_region *find_cyclic_region(ir_region *node) {
651 ir_region *last = node;
654 for (i = get_region_n_preds(node) - 1; i >= 0; --i) {
655 ir_region *pred = get_region_pred(node, i);
657 /* search backedges */
658 if (!pred->link && pred != last && is_ancestor(node, pred)) {
659 ir_region *rem = last;
664 for (j = get_region_n_preds(pred) - 1; j >= 0; --j) {
665 ir_region *p = get_region_pred(pred, j);
667 /* Search regions we didn't visited yet and
668 link them into the list. */
669 if (!p->link && p != last) {
670 if (is_ancestor(node, p)) {
678 /* reverse the list. */
680 rem->link = reverse_list(rem->link);
684 if (node->link && improper) {
685 /* found an improper region, do minimization */
691 #define LINK(list) ((ir_region *)list->link)
694 * Detect a cyclic region.
696 static ir_region *cyclic_region_type(struct obstack *obst, ir_region *node) {
699 /* simple cases first */
700 if (succ_of(node, node)) {
701 return new_SelfLoop(obst, node);
703 if (get_region_n_succs(node) == 1) {
704 ir_region *succ = get_region_succ(node, 0);
705 if (get_region_n_preds(succ) == 1 && succ_of(node, succ)) {
706 return new_RepeatLoop(obst, node, succ);
709 list = find_cyclic_region(node);
712 if (!LINK(list)->link && get_region_n_succs(list->link) == 1) {
713 /* only one body block with only one successor (the head) */
714 return new_WhileLoop(obst, list);
716 /* A Loop with one head */
717 return new_NaturalLoop(obst, list);
724 * Clear all links on a list. Needed, because we expect cleared links-
726 static void clear_list(ir_region *list) {
729 for (next = list; next; list = next) {
735 #define ADD_LIST(list, n) do { n->link = list; list = n; ++list##_len; } while(0)
738 * Detect an acyclic region.
740 static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node) {
743 ir_region *nset = NULL;
747 /* check for a block containing node */
749 p = get_region_n_preds(n) == 1;
752 n = get_region_pred(n, 0);
753 p = get_region_n_preds(n) == 1;
754 s = get_region_n_succs(n) == 1;
757 s = get_region_n_succs(n) == 1;
760 n = get_region_succ(n, 0);
761 p = get_region_n_preds(n) == 1;
762 s = get_region_n_succs(n) == 1;
768 /* node --> .. --> .. */
769 res = new_Sequence(obst, nset, nset_len);
774 /* check for IfThenElse */
775 k = get_region_n_succs(node);
777 int n_succs, m_succs, n_preds, m_preds;
779 n = get_region_succ(node, 0);
780 m = get_region_succ(node, 1);
782 n_succs = get_region_n_succs(n);
783 m_succs = get_region_n_succs(m);
784 n_preds = get_region_n_preds(n);
785 m_preds = get_region_n_preds(m);
786 if (n_succs == 1 && n_succs == m_succs && n_preds == m_preds &&
787 get_region_succ(n, 0) == get_region_succ(m, 0)) {
793 return new_IfThenElse(obst, node, n, m);
796 get_region_succ(n, 0) == m &&
802 return new_IfThen(obst, node, n);
805 get_region_succ(m, 0) == m &&
811 return new_IfThen(obst, node, m);
814 /* check for Switch, case */
816 ir_region *exit = NULL;
817 nset = NULL; nset_len = 0;
819 for (i = k - 1; i >= 0; --i) {
820 n = get_region_succ(node, i);
822 if (get_region_n_succs(n) != 1) {
823 /* must be the exit */
831 ir_region_kind kind = ir_rk_Case;
832 ir_region *pos_exit_1 = NULL;
833 ir_region *pos_exit_2 = NULL;
836 for (m = nset; m != NULL; m = m->link) {
837 if (get_region_n_succs(m) != 1) {
838 /* must be the exit block */
841 } else if (exit != m) {
847 ir_region *succ = get_region_succ(m, 0);
849 if (succ->link == NULL) {
851 if (succ == pos_exit_1)
853 else if (succ == pos_exit_2)
855 else if (pos_exit_1 == NULL)
857 else if (pos_exit_2 == NULL)
860 /* more than two possible exits */
863 } else if (exit != succ) {
873 for (n = nset; n != NULL; n = n->link) {
876 /* good, default fall through */
879 succ = get_region_succ(n, 0);
881 /* good, switch to exit */
884 if (succ->link == NULL) {
895 return new_SwitchCase(obst, kind, node, exit, nset, nset_len);
905 * replace all pred edges from region pred that points to any of the set set
906 * to ONE edge to reg.
908 static void replace_pred(ir_region *succ, ir_region *reg) {
909 int i, len = get_region_n_preds(succ);
912 for (i = 0; i < len; ++i) {
913 ir_region *pred = get_region_pred(succ, i);
915 if (pred->parent == reg) {
920 r = get_region_pred(succ, --len);
926 set_region_pred(succ, i, r);
928 /* the current region can be entered by this node */
932 ARR_SHRINKLEN(succ->pred, len);
936 * replace all succ edges from region pred that points to any of the set set
937 * to ONE edge to reg.
939 static void replace_succ(ir_region *pred, ir_region *reg) {
940 int i, len = get_region_n_succs(pred);
943 for (i = 0; i < len; ++i) {
944 ir_region *succ = get_region_succ(pred, i);
946 if (succ->parent == reg) {
951 r = get_region_succ(pred, --len);
957 set_region_succ(pred, i, r);
959 /* current region can be left by this node */
963 ARR_SHRINKLEN(pred->succ, len);
967 * Reduce the graph by the node reg.
969 static void reduce(walk_env *env, ir_region *reg) {
971 ir_region *head = reg->parts[0].region;
972 unsigned maxorder = head->postnum;
973 unsigned minorder = head->prenum;
975 /* second step: replace all preds in successors */
976 for (i = get_region_n_succs(reg) - 1; i >= 0; --i) {
977 ir_region *succ = get_region_succ(reg, i);
979 replace_pred(succ, reg);
982 /* second third: replace all succs in predessors */
983 for (i = get_region_n_preds(reg) - 1; i >= 0; --i) {
984 ir_region *pred = get_region_pred(reg, i);
986 replace_succ(pred, reg);
989 reg->prenum = minorder;
990 reg->postnum = maxorder;
991 env->post[maxorder] = reg;
995 * Construct the region tree of a graph by doing
996 * structural analysis.
998 * Uses link fields of nodes.
1000 * @param irg the graph
1002 ir_reg_tree *construct_region_tree(ir_graph *irg) {
1004 ir_graph *rem = current_ir_graph;
1005 ir_reg_tree *res = xmalloc(sizeof(*res));
1007 obstack_init(&res->obst);
1009 current_ir_graph = irg;
1011 FIRM_DBG_REGISTER(dbg, "firm.ana.structure");
1012 firm_dbg_set_mask(dbg, SET_LEVEL_5);
1014 DB((dbg, LEVEL_1, "Structural analysis on %+F starts...\n", irg));
1016 dump_ir_block_graph(irg, "-structure_start");
1018 /* we need dominance info */
1021 assure_irg_outs(irg);
1023 env.start_block = get_irg_start_block(irg);
1024 env.end_block = get_irg_end_block(irg);
1026 /* create the Block wrapper and count them */
1028 env.obst = &res->obst;
1029 irg_block_walk_graph(irg, NULL, wrap_BasicBlocks, &env);
1030 irg_block_walk_graph(irg, NULL, update_BasicBlock_regions, &env);
1032 env.post = NEW_ARR_F(ir_region *, env.l_post);
1034 /* do the DFS walk */
1035 dfs_walk(irg, &env);
1037 DB((dbg, LEVEL_1, "%d regions left\n", env.postmax));
1038 if (env.postmax > 1) {
1039 unsigned postctr = 0;
1041 ir_region *reg, *n = env.post[postctr];
1044 /* already folded */
1047 /* locate an acyclic region if present */
1048 reg = acyclic_region_type(env.obst, n);
1050 /* locate a cyclic region */
1051 reg = cyclic_region_type(env.obst, n);
1054 /* found a new region */
1058 } while (reg != NULL);
1060 } while (postctr < env.postmax);
1062 DB((dbg, LEVEL_1, "Structural analysis finished.\n"));
1064 DEL_ARR_F(env.post);
1065 current_ir_graph = rem;
1067 res->top = env.post[0];
1073 * Walk over the region tree.
1075 * @param reg a region node
1076 * @param pre walker function, executed before the children of a tree node are visited
1077 * @param post walker function, executed after the children of a tree node are visited
1078 * @param env environment, passed to pre and post
1080 static void region_tree_walk2(ir_region *reg, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env) {
1085 if (reg->type != ir_rk_BasicBlock) {
1086 for (i = 0, n = ARR_LEN(reg->parts); i < n; ++i)
1087 region_tree_walk2(reg->parts[i].region, pre, post, env);
1094 * Walk over the region tree.
1096 * @param tree the tree
1097 * @param pre walker function, executed before the children of a tree node are visited
1098 * @param post walker function, executed after the children of a tree node are visited
1099 * @param env environment, passed to pre and post
1101 void region_tree_walk(ir_reg_tree *tree, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env) {
1102 region_tree_walk2(tree->top, pre, post, env);