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"
29 typedef union ir_reg_or_blk ir_reg_or_blk;
31 /* The structure tree. */
33 struct obstack obst; /**< The obstack where the data is allocated. */
34 ir_region *top; /**< The top region. */
35 ir_graph *irg; /**< Associated graph. */
40 firm_kind kind; /**< Must be k_ir_region. */
41 ir_region_kind type; /**< The type of this region. */
42 ir_region *parent; /**< points to the parent. */
43 ir_reg_or_blk *parts; /**< The list of all region parts. */
44 ir_region **pred; /**< The predecessor (control flow) regions of this region. */
45 ir_region **succ; /**< The successor (control flow) regions of this region. */
46 unsigned prenum; /**< DFS pre-oder number */
47 unsigned postnum; /**< DFS post-oder number */
48 void *link; /**< A link field. */
49 unsigned long nr; /**< for debugging */
50 unsigned visited:1; /**< The visited flag. */
51 unsigned exit:1; /**< If set, the parent region can be left by this node. */
52 unsigned enter:1; /**< If set, the parent region can be entered by this node. */
55 /* A helper type for unioning blocks and regions. */
57 firm_kind *kind; /**< For easier check. */
58 ir_node *blk; /**< A node */
59 ir_region *region; /**< A region. */
62 /* The debug handle. */
63 DEBUG_ONLY(firm_dbg_module_t *dbg;)
66 * Returns the link of a region.
68 void *get_region_link(const ir_region *reg) {
73 * Sets the link of a region.
75 void set_region_link(ir_region *reg, void *data) {
80 * Get the immediate region of a block.
82 ir_region *get_block_region(const ir_node *block) {
83 assert(is_Block(block));
84 return block->attr.block.region;
88 * Sets the immediate region of a block.
90 void set_block_region(ir_node *block, ir_region *reg) {
91 assert(is_Block(block));
92 block->attr.block.region = reg;
96 * Get the immediate region of a node.
98 ir_region *get_irn_region(ir_node *n) {
100 n = get_nodes_block(n);
101 return get_block_region(n);
105 * Return non-if a given firm thing is a region.
107 int is_region(const void *thing) {
108 const firm_kind *kind = thing;
109 return *kind == k_ir_region;
113 * Return the number of predecessors in a region.
115 int get_region_n_preds(const ir_region *reg) {
116 return ARR_LEN(reg->pred);
120 * Return the predecessor region at position pos.
122 ir_region *get_region_pred(const ir_region *reg, int pos) {
123 assert(0 <= pos && pos <= get_region_n_preds(reg));
124 return reg->pred[pos];
128 * Set the predecessor region at position pos.
130 void set_region_pred(ir_region *reg, int pos, ir_region *n) {
131 assert(0 <= pos && pos <= get_region_n_preds(reg));
136 * Return the number of successors in a region.
138 int get_region_n_succs(const ir_region *reg) {
139 return ARR_LEN(reg->succ);
143 * Return the successor region at position pos.
145 ir_region *get_region_succ(const ir_region *reg, int pos) {
146 assert(0 <= pos && pos <= get_region_n_succs(reg));
147 return reg->succ[pos];
151 * Set the successor region at position pos.
153 void set_region_succ(ir_region *reg, int pos, ir_region *n) {
154 assert(0 <= pos && pos <= get_region_n_succs(reg));
158 /* ----------------------- construction -------------------------- */
160 /** Walker environment. */
161 typedef struct walk_env {
162 struct obstack *obst; /**< an obstack to allocate from. */
163 ir_region **post; /**< The list of all currently existent top regions. */
164 unsigned l_post; /**< length of the allocated regions array. */
165 unsigned premax; /**< maximum pre counter */
166 unsigned postmax; /**< maximum post counter */
167 ir_node *start_block; /**< the start block of the graph. */
168 ir_node *end_block; /**< the end block of the graph. */
172 * Do a DFS search on the initial regions, assign a prenum and a postnum to every
173 * node and store the region nodes into the post array.
175 static void dfs_walk2(ir_region *reg, walk_env *env) {
178 if (reg->visited == 0) {
181 reg->prenum = env->premax++;
182 for (i = 0, n = get_region_n_succs(reg); i < n; ++i) {
184 ir_region *succ = get_region_succ(reg, i);
185 dfs_walk2(succ, env);
188 env->post[env->postmax] = reg;
189 reg->postnum = env->postmax++;
194 * Do a DFS search on the initial regions, assign a prenum and a postnum to every
195 * node and store the region nodes into the post array.
197 static void dfs_walk(ir_graph *irg, walk_env *env) {
198 ir_graph *rem = current_ir_graph;
201 current_ir_graph = irg;
202 reg = get_irn_link(get_irg_start_block(irg));
207 current_ir_graph = rem;
211 * Post-walker: wrap all blocks with a BasicBlock region
214 static void wrap_BasicBlocks(ir_node *block, void *ctx) {
218 /* Allocate a Block wrapper */
219 reg = obstack_alloc(env->obst, sizeof(*reg));
220 reg->kind = k_ir_region;
221 reg->type = ir_rk_BasicBlock;
229 reg->nr = get_irn_node_nr(block);
230 reg->parts = NEW_ARR_D(ir_reg_or_blk, env->obst, 1);
232 reg->parts[0].blk = block;
233 set_irn_link(block, reg);
236 } /* wrap_BasicBlocks */
239 * Create the pred and succ edges for Block wrapper.
240 * Kill edges to the Start and End blocks.
242 static void update_BasicBlock_regions(ir_node *blk, void *ctx) {
244 ir_region *reg = get_irn_link(blk);
247 if (blk == env->start_block) {
248 /* handle Firm's self loop */
249 reg->pred = NEW_ARR_D(ir_region *, env->obst, 0);
251 len = get_Block_n_cfgpreds(blk);
252 reg->pred = NEW_ARR_D(ir_region *, env->obst, len);
253 for (i = j = 0; i < len; ++i) {
254 ir_node *pred = get_Block_cfgpred_block(blk, i);
255 reg->pred[j++] = get_irn_link(pred);
257 ARR_SHRINKLEN(reg->pred, j);
260 len = get_Block_n_cfg_outs(blk);
261 reg->succ = NEW_ARR_D(ir_region *, env->obst, len);
262 for (i = j = 0; i < len; ++i) {
263 ir_node *succ = get_Block_cfg_out(blk, i);
264 reg->succ[j++] = get_irn_link(succ);
266 ARR_SHRINKLEN(reg->succ, j);
267 } /* update_BasicBlock_regions */
269 /** Allocate a new region of a obstack */
270 #define ALLOC_REG(obst, reg, tp) \
272 (reg) = obstack_alloc((obst), sizeof(*(reg))); \
273 (reg)->kind = k_ir_region; \
275 (reg)->parent = NULL; \
277 (reg)->postnum = 0; \
278 (reg)->visited = 0; \
281 (reg)->link = NULL; \
285 * Creates a new Sequence region.
287 static ir_region *new_Sequence(struct obstack *obst, ir_region *nset, int nset_len) {
288 ir_region *reg, *next;
291 ALLOC_REG(obst, reg, ir_rk_Sequence);
293 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, nset_len);
295 /* beware: list is in reverse order, reverse */
297 for (i = nset_len - 1; i >= 0; --i) {
299 reg->parts[i].region = nset;
305 reg->nr = reg->parts[0].region->nr;
306 reg->pred = DUP_ARR_D(ir_region *, obst, reg->parts[0].region->pred);
307 reg->succ = DUP_ARR_D(ir_region *, obst, reg->parts[nset_len - 1].region->succ);
310 DB((dbg, LEVEL_2, " Created Sequence "));
311 for (i = 0; i < nset_len; ++i) {
312 DB((dbg, LEVEL_2, "(%u)", reg->parts[i].region->nr));
314 DB((dbg, LEVEL_2, "\n"));
320 * Create a new IfThenElse region.
322 static ir_region *new_IfThenElse(struct obstack *obst, ir_region *if_b, ir_region *then_b, ir_region *else_b) {
325 ALLOC_REG(obst, reg, ir_rk_IfThenElse);
328 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 3);
330 reg->parts[0].region = if_b; if_b->parent = reg;
331 reg->parts[1].region = then_b; then_b->parent = reg;
332 reg->parts[2].region = else_b; else_b->parent = reg;
334 reg->pred = DUP_ARR_D(ir_region *, obst, if_b->pred);
335 reg->succ = DUP_ARR_D(ir_region *, obst, then_b->succ);
337 DB((dbg, LEVEL_2, " Created If(%u)Then(%u)Else(%u)\n", reg->nr, then_b->nr, else_b->nr));
340 } /* new_IfThenElse */
343 * Create a new IfThen region.
345 static ir_region *new_IfThen(struct obstack *obst, ir_region *if_b, ir_region *then_b) {
348 ALLOC_REG(obst, reg, ir_rk_IfThen);
351 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 2);
353 reg->parts[0].region = if_b; if_b->parent = reg;
354 reg->parts[1].region = then_b; then_b->parent = reg;
356 reg->pred = DUP_ARR_D(ir_region *, obst, if_b->pred);
357 reg->succ = DUP_ARR_D(ir_region *, obst, then_b->succ);
359 DB((dbg, LEVEL_2, " Created If(%u)Then(%u)\n", reg->nr, then_b->nr));
362 } /* new_IfThenElse */
365 * Create a new Switch/case region.
367 static ir_region *new_SwitchCase(struct obstack *obst, ir_region_kind type, ir_region *head, ir_region *exit,
368 ir_region *cases, int cases_len) {
369 ir_region *reg, *c, *n;
373 /* check, if the exit block is in the list */
374 for (c = cases; c != NULL; c = c->link) {
381 ALLOC_REG(obst, reg, type);
384 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, cases_len + add);
386 reg->parts[0].region = head; head->parent = reg;
388 for (c = cases; c != NULL; c = n) {
391 reg->parts[i++].region = c;
397 reg->pred = DUP_ARR_D(ir_region *, obst, head->pred);
398 reg->succ = NEW_ARR_D(ir_region *, obst, 1);
402 DB((dbg, LEVEL_2, " Created %s(%u)\n", reg->type == ir_rk_Switch ? "Switch" : "Case", reg->nr));
403 for (i = 1; i < ARR_LEN(reg->parts); ++i) {
404 DB((dbg, LEVEL_2, " Case(%u)\n", reg->parts[i].region->nr));
406 DB((dbg, LEVEL_2, " Exit(%u)\n", exit->nr));
409 } /* new_SwitchCase */
412 * Create a new SelfLoop region.
414 static ir_region *new_SelfLoop(struct obstack *obst, ir_region *head) {
415 ir_region *reg, *succ;
418 ALLOC_REG(obst, reg, ir_rk_SelfLoop);
421 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 1);
423 reg->parts[0].region = head; head->parent = reg;
425 len = ARR_LEN(head->pred);
426 reg->pred = NEW_ARR_D(ir_region *, obst, len - 1);
427 for (i = j = 0; i < len; ++i) {
428 ir_region *pred = get_region_pred(head, i);
430 reg->pred[j++] = pred;
432 assert(j == len - 1);
434 reg->succ = NEW_ARR_D(ir_region *, obst, 1);
435 assert(ARR_LEN(head->succ) == 2);
437 succ = get_region_succ(head, 0);
441 reg->succ[0] = get_region_succ(head, 1);
443 DB((dbg, LEVEL_2, " Created SelfLoop(%u)\n", reg->nr));
449 * Create a new RepeatLoop region.
451 static ir_region *new_RepeatLoop(struct obstack *obst, ir_region *head, ir_region *body) {
452 ir_region *reg, *succ;
454 ALLOC_REG(obst, reg, ir_rk_RepeatLoop);
457 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 2);
459 reg->parts[0].region = head; head->parent = reg;
460 reg->parts[1].region = body; body->parent = reg;
462 reg->pred = DUP_ARR_D(ir_region *, obst, head->pred);
463 reg->succ = NEW_ARR_D(ir_region *, obst, 1);
464 assert(ARR_LEN(body->succ) == 2);
466 succ = get_region_succ(body, 0);
470 reg->succ[0] = get_region_succ(body, 1);
472 DB((dbg, LEVEL_2, " Created RepeatLoop(%u)Body(%u)\n", reg->nr, body->nr));
475 } /* new_RepeatLoop */
478 * Create a new WhileLoop region.
480 static ir_region *new_WhileLoop(struct obstack *obst, ir_region *head) {
481 ir_region *reg, *succ;
482 ir_region *body = head->link;
487 ALLOC_REG(obst, reg, ir_rk_WhileLoop);
490 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 2);
492 reg->parts[0].region = head; head->parent = reg;
493 reg->parts[1].region = body; body->parent = reg;
495 len = ARR_LEN(head->pred);
496 reg->pred = NEW_ARR_D(ir_region *, obst, len - 1);
497 for (i = j = 0; i < len; ++i) {
498 ir_region *pred = get_region_pred(head, i);
500 reg->pred[j++] = pred;
502 assert(j == len - 1);
504 reg->succ = NEW_ARR_D(ir_region *, obst, 1);
505 assert(ARR_LEN(head->succ) == 2);
507 succ = get_region_succ(head, 0);
511 reg->succ[0] = get_region_succ(head, 1);
513 DB((dbg, LEVEL_2, " Created WhileLoop(%u)Body(%u)\n", reg->nr, body->nr));
516 } /* new_WhileLoop */
519 * Create a new new_NaturalLoop region.
521 static ir_region *new_NaturalLoop(struct obstack *obst, ir_region *head) {
522 ir_region *reg, *c, *n;
523 int i, j, k, len, n_pred, n_succ;
525 /* count number of parts */
526 for (len = 0, c = head; c != NULL; c = c->link)
529 ALLOC_REG(obst, reg, ir_rk_WhileLoop);
532 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, len);
534 /* enter all parts */
535 for (i = 0, c = head; c != NULL; c = n) {
536 reg->parts[i++].region = c;
542 /* count number of preds */
544 for (i = get_region_n_preds(head) - 1; i >= 0; --i) {
545 ir_region *pred = get_region_pred(head, i);
546 if (pred->parent != reg)
549 reg->pred = NEW_ARR_D(ir_region *, obst, n_pred);
550 for (j = 0, i = get_region_n_preds(head) - 1; i >= 0; --i) {
551 ir_region *pred = get_region_pred(head, i);
552 if (pred->parent != reg)
553 reg->pred[j++] = pred;
556 /* count number of succs */
558 for (j = 0; j < len; ++j) {
559 ir_region *c = reg->parts[j].region;
560 for (i = get_region_n_succs(c) - 1; i >= 0; --i) {
561 ir_region *succ = get_region_succ(c, i);
562 if (succ->parent != reg)
566 reg->succ = NEW_ARR_D(ir_region *, obst, n_succ);
568 for (j = 0; j < len; ++j) {
569 ir_region *c = reg->parts[j].region;
570 for (i = get_region_n_succs(c) - 1; i >= 0; --i) {
571 ir_region *succ = get_region_succ(c, i);
572 if (succ->parent != reg)
573 reg->succ[k++] = succ;
578 DB((dbg, LEVEL_2, " Created NaturalLoop(%u)Head(%u)\n", reg->nr, head->nr));
579 for (i = 1; i < len; ++i) {
580 ir_region *p = reg->parts[i].region;
581 DB((dbg, LEVEL_2, " Body(%u)\n", p->nr));
585 } /* new_NaturalLoop */
588 * Return true if a is an ancestor of b in DFS search.
590 static int is_ancestor(const ir_region *a, const ir_region *b) {
591 return (a->prenum <= b->prenum && a->postnum > b->postnum);
595 * Return true if region pred is a predecessor of region n.
597 static int pred_of(const ir_region *pred, const ir_region *n) {
599 for (i = get_region_n_preds(n) - 1; i >= 0; --i) {
600 if (get_region_pred(n, i) == pred)
607 * Return true if region succ is a successor of region n.
609 static int succ_of(const ir_region *succ, const ir_region *n) {
611 for (i = get_region_n_succs(n) - 1; i >= 0; --i) {
612 if (get_region_succ(n, i) == succ)
619 * Reverse linked list.
621 static struct ir_region *reverse_list(ir_region *n) {
622 ir_region *prev = NULL, *next;
624 for (; n; n = next) {
633 * Find the cyclic region in the subgraph entered by node.
635 static ir_region *find_cyclic_region(ir_region *node) {
637 ir_region *last = node;
640 for (i = get_region_n_preds(node) - 1; i >= 0; --i) {
641 ir_region *pred = get_region_pred(node, i);
643 /* search backedges */
644 if (!pred->link && pred != last && is_ancestor(node, pred)) {
645 ir_region *rem = last;
650 for (j = get_region_n_preds(pred) - 1; j >= 0; --j) {
651 ir_region *p = get_region_pred(pred, j);
653 /* Search regions we didn't visited yet and
654 link them into the list. */
655 if (!p->link && p != last) {
656 if (is_ancestor(node, p)) {
664 /* reverse the list. */
666 rem->link = reverse_list(rem->link);
670 if (node->link && improper) {
671 /* found an improper region, do minimization */
677 #define LINK(list) ((ir_region *)list->link)
680 * Detect a cyclic region.
682 static ir_region *cyclic_region_type(struct obstack *obst, ir_region *node) {
685 /* simple cases first */
686 if (succ_of(node, node)) {
687 return new_SelfLoop(obst, node);
689 if (get_region_n_succs(node) == 1) {
690 ir_region *succ = get_region_succ(node, 0);
691 if (get_region_n_preds(succ) == 1 && succ_of(node, succ)) {
692 return new_RepeatLoop(obst, node, succ);
695 list = find_cyclic_region(node);
698 if (!LINK(list)->link && get_region_n_succs(list->link) == 1) {
699 /* only one body block with only one successor (the head) */
700 return new_WhileLoop(obst, list);
702 /* A Loop with one head */
703 return new_NaturalLoop(obst, list);
710 * Clear all links on a list. Needed, because we expect cleared links-
712 static void clear_list(ir_region *list) {
715 for (next = list; next; list = next) {
721 #define ADD_LIST(list, n) do { n->link = list; list = n; ++list##_len; } while(0)
724 * Detect an acyclic region.
726 static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node) {
729 ir_region *nset = NULL;
733 /* check for a block containing node */
735 p = get_region_n_preds(n) == 1;
738 n = get_region_pred(n, 0);
739 p = get_region_n_preds(n) == 1;
740 s = get_region_n_succs(n) == 1;
743 s = get_region_n_succs(n) == 1;
746 n = get_region_succ(n, 0);
747 p = get_region_n_preds(n) == 1;
748 s = get_region_n_succs(n) == 1;
754 /* node --> .. --> .. */
755 res = new_Sequence(obst, nset, nset_len);
760 /* check for IfThenElse */
761 k = get_region_n_succs(node);
763 int n_succs, m_succs, n_preds, m_preds;
765 n = get_region_succ(node, 0);
766 m = get_region_succ(node, 1);
768 n_succs = get_region_n_succs(n);
769 m_succs = get_region_n_succs(m);
770 n_preds = get_region_n_preds(n);
771 m_preds = get_region_n_preds(m);
772 if (n_succs == 1 && n_succs == m_succs && n_preds == m_preds &&
773 get_region_succ(n, 0) == get_region_succ(m, 0)) {
779 return new_IfThenElse(obst, node, n, m);
782 get_region_succ(n, 0) == m &&
788 return new_IfThen(obst, node, n);
791 get_region_succ(m, 0) == m &&
797 return new_IfThen(obst, node, m);
800 /* check for Switch, case */
802 ir_region *exit = NULL;
803 nset = NULL; nset_len = 0;
805 for (i = k - 1; i >= 0; --i) {
806 n = get_region_succ(node, i);
808 if (get_region_n_succs(n) != 1) {
809 /* must be the exit */
817 ir_region_kind kind = ir_rk_Case;
818 ir_region *pos_exit_1 = NULL;
819 ir_region *pos_exit_2 = NULL;
822 for (m = nset; m != NULL; m = m->link) {
823 if (get_region_n_succs(m) != 1) {
824 /* must be the exit block */
827 } else if (exit != m) {
833 ir_region *succ = get_region_succ(m, 0);
835 if (succ->link == NULL) {
837 if (succ == pos_exit_1)
839 else if (succ == pos_exit_2)
841 else if (pos_exit_1 == NULL)
843 else if (pos_exit_2 == NULL)
846 /* more than two possible exits */
849 } else if (exit != succ) {
859 for (n = nset; n != NULL; n = n->link) {
862 /* good, default fall through */
865 succ = get_region_succ(n, 0);
867 /* good, switch to exit */
870 if (succ->link == NULL) {
881 return new_SwitchCase(obst, kind, node, exit, nset, nset_len);
891 * replace all pred edges from region pred that points to any of the set set
892 * to ONE edge to reg.
894 static void replace_pred(ir_region *succ, ir_region *reg) {
895 int i, len = get_region_n_preds(succ);
898 for (i = 0; i < len; ++i) {
899 ir_region *pred = get_region_pred(succ, i);
901 if (pred->parent == reg) {
906 r = get_region_pred(succ, --len);
912 set_region_pred(succ, i, r);
914 /* the current region can be entered by this node */
918 ARR_SHRINKLEN(succ->pred, len);
922 * replace all succ edges from region pred that points to any of the set set
923 * to ONE edge to reg.
925 static void replace_succ(ir_region *pred, ir_region *reg) {
926 int i, len = get_region_n_succs(pred);
929 for (i = 0; i < len; ++i) {
930 ir_region *succ = get_region_succ(pred, i);
932 if (succ->parent == reg) {
937 r = get_region_succ(pred, --len);
943 set_region_succ(pred, i, r);
945 /* current region can be left by this node */
949 ARR_SHRINKLEN(pred->succ, len);
953 * Reduce the graph by the node reg.
955 static void reduce(walk_env *env, ir_region *reg) {
957 ir_region *head = reg->parts[0].region;
958 unsigned maxorder = head->postnum;
959 unsigned minorder = head->prenum;
961 /* second step: replace all preds in successors */
962 for (i = get_region_n_succs(reg) - 1; i >= 0; --i) {
963 ir_region *succ = get_region_succ(reg, i);
965 replace_pred(succ, reg);
968 /* second third: replace all succs in predessors */
969 for (i = get_region_n_preds(reg) - 1; i >= 0; --i) {
970 ir_region *pred = get_region_pred(reg, i);
972 replace_succ(pred, reg);
975 reg->prenum = minorder;
976 reg->postnum = maxorder;
977 env->post[maxorder] = reg;
981 * Construct the region tree of a graph by doing
982 * structural analysis.
984 * Uses link fields of nodes.
986 * @param irg the graph
988 ir_reg_tree *construct_region_tree(ir_graph *irg) {
990 ir_graph *rem = current_ir_graph;
991 ir_reg_tree *res = xmalloc(sizeof(*res));
993 obstack_init(&res->obst);
995 current_ir_graph = irg;
997 FIRM_DBG_REGISTER(dbg, "firm.ana.structure");
998 firm_dbg_set_mask(dbg, SET_LEVEL_5);
1000 DB((dbg, LEVEL_1, "Structural analysis on %+F starts...\n", irg));
1002 dump_ir_block_graph(irg, "-structure_start");
1004 /* we need dominance info */
1007 assure_irg_outs(irg);
1009 env.start_block = get_irg_start_block(irg);
1010 env.end_block = get_irg_end_block(irg);
1012 /* create the Block wrapper and count them */
1014 env.obst = &res->obst;
1015 irg_block_walk_graph(irg, NULL, wrap_BasicBlocks, &env);
1016 irg_block_walk_graph(irg, NULL, update_BasicBlock_regions, &env);
1018 env.post = NEW_ARR_F(ir_region *, env.l_post);
1020 /* do the DFS walk */
1021 dfs_walk(irg, &env);
1023 DB((dbg, LEVEL_1, "%d regions left\n", env.postmax));
1024 if (env.postmax > 1) {
1025 unsigned postctr = 0;
1027 ir_region *reg, *n = env.post[postctr];
1030 /* already folded */
1033 /* locate an acyclic region if present */
1034 reg = acyclic_region_type(env.obst, n);
1036 /* locate a cyclic region */
1037 reg = cyclic_region_type(env.obst, n);
1040 /* found a new region */
1044 } while (reg != NULL);
1046 } while (postctr < env.postmax);
1048 DB((dbg, LEVEL_1, "Structural analysis finished.\n"));
1050 DEL_ARR_F(env.post);
1051 current_ir_graph = rem;
1053 res->top = env.post[0];
1059 * Walk over the region tree.
1061 * @param reg a region node
1062 * @param pre walker function, executed before the children of a tree node are visited
1063 * @param post walker function, executed after the children of a tree node are visited
1064 * @param env environment, passed to pre and post
1066 static void region_tree_walk2(ir_region *reg, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env) {
1071 if (reg->type != ir_rk_BasicBlock) {
1072 for (i = 0, n = ARR_LEN(reg->parts); i < n; ++i)
1073 region_tree_walk2(reg->parts[i].region, pre, post, env);
1080 * Walk over the region tree.
1082 * @param tree the tree
1083 * @param pre walker function, executed before the children of a tree node are visited
1084 * @param post walker function, executed after the children of a tree node are visited
1085 * @param env environment, passed to pre and post
1087 void region_tree_walk(ir_reg_tree *tree, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env) {
1088 region_tree_walk2(tree->top, pre, post, env);