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
29 #include "firm_common.h"
31 #include "structure.h"
41 typedef union ir_reg_or_blk ir_reg_or_blk;
43 /* The structure tree. */
45 struct obstack obst; /**< The obstack where the data is allocated. */
46 ir_region *top; /**< The top region. */
47 ir_graph *irg; /**< Associated graph. */
52 firm_kind kind; /**< Must be k_ir_region. */
53 ir_region_kind type; /**< The type of this region. */
54 ir_region *parent; /**< points to the parent. */
55 ir_reg_or_blk *parts; /**< The list of all region parts. */
56 ir_region **pred; /**< The predecessor (control flow) regions of this region. */
57 ir_region **succ; /**< The successor (control flow) regions of this region. */
58 unsigned prenum; /**< DFS pre-oder number */
59 unsigned postnum; /**< DFS post-oder number */
60 void *link; /**< A link field. */
61 unsigned long nr; /**< for debugging */
62 unsigned visited:1; /**< The visited flag. */
63 unsigned exit:1; /**< If set, the parent region can be left by this node. */
64 unsigned enter:1; /**< If set, the parent region can be entered by this node. */
67 /* A helper type for unioning blocks and regions. */
69 firm_kind *kind; /**< For easier check. */
70 ir_node *blk; /**< A node */
71 ir_region *region; /**< A region. */
74 /* The debug handle. */
75 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
78 * Returns the link of a region.
80 void *get_region_link(const ir_region *reg)
86 * Sets the link of a region.
88 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)
98 assert(is_Block(block));
99 return block->attr.block.region;
103 * Sets the immediate region of a block.
105 void set_block_region(ir_node *block, ir_region *reg)
107 assert(is_Block(block));
108 block->attr.block.region = reg;
112 * Get the immediate region of a node.
114 ir_region *get_irn_region(ir_node *n)
117 n = get_nodes_block(n);
118 return get_block_region(n);
122 * Return non-zero if a given firm thing is a region.
124 int is_region(const void *thing)
126 const firm_kind *kind = (const firm_kind*) thing;
127 return *kind == k_ir_region;
131 * Return the number of predecessors of a region.
133 int get_region_n_preds(const ir_region *reg)
135 return ARR_LEN(reg->pred);
139 * Return the predecessor region at position pos.
141 ir_region *get_region_pred(const ir_region *reg, int pos)
143 assert(0 <= pos && pos <= get_region_n_preds(reg));
144 return reg->pred[pos];
148 * Set the predecessor region at position pos.
150 void set_region_pred(ir_region *reg, int pos, ir_region *n)
152 assert(0 <= pos && pos <= get_region_n_preds(reg));
157 * Return the number of successors in a region.
159 int get_region_n_succs(const ir_region *reg)
161 return ARR_LEN(reg->succ);
165 * Return the successor region at position pos.
167 ir_region *get_region_succ(const ir_region *reg, int pos)
169 assert(0 <= pos && pos <= get_region_n_succs(reg));
170 return reg->succ[pos];
174 * Set the successor region at position pos.
176 void set_region_succ(ir_region *reg, int pos, ir_region *n)
178 assert(0 <= pos && pos <= get_region_n_succs(reg));
182 /* ----------------------- construction -------------------------- */
184 /** Walker environment. */
185 typedef struct walk_env {
186 struct obstack *obst; /**< An obstack to allocate from. */
187 ir_region **post; /**< The list of all currently existent top regions. */
188 unsigned l_post; /**< The length of the allocated regions array. */
189 unsigned premax; /**< maximum pre counter */
190 unsigned postmax; /**< maximum post counter */
191 ir_node *start_block; /**< The start block of the graph. */
192 ir_node *end_block; /**< The end block of the graph. */
196 * Do a DFS search on the initial regions, assign a prenum and a postnum to every
197 * node and store the region nodes into the post array.
199 static void dfs_walk2(ir_region *reg, walk_env *env)
203 if (reg->visited == 0) {
206 reg->prenum = env->premax++;
207 for (i = 0, n = get_region_n_succs(reg); i < n; ++i) {
209 ir_region *succ = get_region_succ(reg, i);
210 dfs_walk2(succ, env);
213 env->post[env->postmax] = reg;
214 reg->postnum = env->postmax++;
219 * Do a DFS search on the initial regions, assign a prenum and a postnum to every
220 * node and store the region nodes into the post array.
222 static void dfs_walk(ir_graph *irg, walk_env *env)
224 ir_graph *rem = current_ir_graph;
227 current_ir_graph = irg;
228 reg = (ir_region*) get_irn_link(get_irg_start_block(irg));
233 current_ir_graph = rem;
237 * Post-walker: wrap all blocks with a BasicBlock region
240 static void wrap_BasicBlocks(ir_node *block, void *ctx)
242 walk_env *env = (walk_env*) ctx;
245 /* Allocate a Block wrapper */
246 reg = OALLOC(env->obst, ir_region);
247 reg->kind = k_ir_region;
248 reg->type = ir_rk_BasicBlock;
256 reg->nr = get_irn_node_nr(block);
257 reg->parts = NEW_ARR_D(ir_reg_or_blk, env->obst, 1);
259 reg->parts[0].blk = block;
260 set_irn_link(block, reg);
263 } /* wrap_BasicBlocks */
266 * Post-walker: Create the pred and succ edges for Block wrapper.
267 * Kill edges to the Start and End blocks.
269 static void update_BasicBlock_regions(ir_node *blk, void *ctx)
271 walk_env *env = (walk_env*) ctx;
272 ir_region *reg = (ir_region*) get_irn_link(blk);
276 if (blk == env->start_block) {
277 /* handle Firm's self loop: Start block has no predecessors */
278 reg->pred = NEW_ARR_D(ir_region *, env->obst, 0);
280 len = get_Block_n_cfgpreds(blk);
281 reg->pred = NEW_ARR_D(ir_region *, env->obst, len);
282 for (j = i = 0; i < len; ++i) {
283 ir_node *pred = get_Block_cfgpred_block(blk, i);
284 reg->pred[j++] = (ir_region*) get_irn_link(pred);
286 ARR_SHRINKLEN(reg->pred, j);
289 len = get_Block_n_cfg_outs(blk);
290 reg->succ = NEW_ARR_D(ir_region *, env->obst, len);
291 for (j = i = 0; i < len; ++i) {
292 ir_node *succ = get_Block_cfg_out(blk, i);
293 reg->succ[j++] = (ir_region*) get_irn_link(succ);
295 ARR_SHRINKLEN(reg->succ, j);
296 } /* update_BasicBlock_regions */
298 /** Allocate a new region on an obstack */
299 #define ALLOC_REG(obst, reg, tp) \
301 (reg) = OALLOC((obst), ir_region); \
302 (reg)->kind = k_ir_region; \
304 (reg)->parent = NULL; \
306 (reg)->postnum = 0; \
307 (reg)->visited = 0; \
310 (reg)->link = NULL; \
314 * Creates a new Sequence region.
316 static ir_region *new_Sequence(struct obstack *obst, ir_region *nset, int nset_len)
318 ir_region *reg, *next;
321 ALLOC_REG(obst, reg, ir_rk_Sequence);
323 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, nset_len);
325 /* beware: list is in reverse order, reverse */
327 for (i = nset_len - 1; i >= 0; --i) {
329 reg->parts[i].region = nset;
331 next = (ir_region*) nset->link;
335 reg->nr = reg->parts[0].region->nr;
336 reg->pred = DUP_ARR_D(ir_region *, obst, reg->parts[0].region->pred);
337 reg->succ = DUP_ARR_D(ir_region *, obst, reg->parts[nset_len - 1].region->succ);
340 DB((dbg, LEVEL_2, " Created Sequence "));
341 for (i = 0; i < nset_len; ++i) {
342 DB((dbg, LEVEL_2, "(%u)", reg->parts[i].region->nr));
344 DB((dbg, LEVEL_2, "\n"));
350 * Create a new IfThenElse region.
352 static ir_region *new_IfThenElse(struct obstack *obst, ir_region *if_b, ir_region *then_b, ir_region *else_b)
356 ALLOC_REG(obst, reg, ir_rk_IfThenElse);
359 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 3);
361 reg->parts[0].region = if_b; if_b->parent = reg;
362 reg->parts[1].region = then_b; then_b->parent = reg;
363 reg->parts[2].region = else_b; else_b->parent = reg;
365 reg->pred = DUP_ARR_D(ir_region *, obst, if_b->pred);
366 reg->succ = DUP_ARR_D(ir_region *, obst, then_b->succ);
368 DB((dbg, LEVEL_2, " Created If(%u)Then(%u)Else(%u)\n", reg->nr, then_b->nr, else_b->nr));
371 } /* new_IfThenElse */
374 * Create a new IfThen region.
376 static ir_region *new_IfThen(struct obstack *obst, ir_region *if_b, ir_region *then_b)
380 ALLOC_REG(obst, reg, 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(%u)Then(%u)\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, int cases_len)
402 ir_region *reg, *c, *n;
406 /* check, if the exit block is in the list */
407 for (c = cases; c != NULL; c = (ir_region*) c->link) {
414 ALLOC_REG(obst, reg, type);
417 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, cases_len + add);
419 reg->parts[0].region = head; head->parent = reg;
421 for (c = cases; c != NULL; c = n) {
422 n = (ir_region*) c->link;
424 reg->parts[i++].region = c;
430 reg->pred = DUP_ARR_D(ir_region *, obst, head->pred);
431 reg->succ = NEW_ARR_D(ir_region *, obst, 1);
436 DB((dbg, LEVEL_2, " Created %s(%u)\n", reg->type == ir_rk_Switch ? "Switch" : "Case", reg->nr));
437 for (i = 1; i < ARR_LEN(reg->parts); ++i) {
438 DB((dbg, LEVEL_2, " Case(%u)\n", reg->parts[i].region->nr));
440 DB((dbg, LEVEL_2, " Exit(%u)\n", exit->nr));
443 } /* new_SwitchCase */
446 * Create a new SelfLoop region.
448 static ir_region *new_SelfLoop(struct obstack *obst, ir_region *head)
450 ir_region *reg, *succ;
453 ALLOC_REG(obst, reg, ir_rk_SelfLoop);
456 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 1);
458 reg->parts[0].region = head; head->parent = reg;
460 len = ARR_LEN(head->pred);
461 reg->pred = NEW_ARR_D(ir_region *, obst, len - 1);
462 for (i = j = 0; i < len; ++i) {
463 ir_region *pred = get_region_pred(head, i);
465 reg->pred[j++] = pred;
467 assert(j == len - 1);
469 reg->succ = NEW_ARR_D(ir_region *, obst, 1);
470 assert(ARR_LEN(head->succ) == 2);
472 succ = get_region_succ(head, 0);
476 reg->succ[0] = get_region_succ(head, 1);
478 DB((dbg, LEVEL_2, " Created SelfLoop(%u)\n", reg->nr));
484 * Create a new RepeatLoop region.
486 static ir_region *new_RepeatLoop(struct obstack *obst, ir_region *head, ir_region *body)
488 ir_region *reg, *succ;
490 ALLOC_REG(obst, reg, ir_rk_RepeatLoop);
493 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 2);
495 reg->parts[0].region = head; head->parent = reg;
496 reg->parts[1].region = body; body->parent = reg;
498 reg->pred = DUP_ARR_D(ir_region *, obst, head->pred);
499 reg->succ = NEW_ARR_D(ir_region *, obst, 1);
500 assert(ARR_LEN(body->succ) == 2);
502 succ = get_region_succ(body, 0);
506 reg->succ[0] = get_region_succ(body, 1);
508 DB((dbg, LEVEL_2, " Created RepeatLoop(%u)Body(%u)\n", reg->nr, body->nr));
511 } /* new_RepeatLoop */
514 * Create a new WhileLoop region.
516 static ir_region *new_WhileLoop(struct obstack *obst, ir_region *head)
518 ir_region *reg, *succ;
519 ir_region *body = (ir_region*) head->link;
524 ALLOC_REG(obst, reg, ir_rk_WhileLoop);
527 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 2);
529 reg->parts[0].region = head; head->parent = reg;
530 reg->parts[1].region = body; body->parent = reg;
532 len = ARR_LEN(head->pred);
533 reg->pred = NEW_ARR_D(ir_region *, obst, len - 1);
534 for (i = j = 0; i < len; ++i) {
535 ir_region *pred = get_region_pred(head, i);
537 reg->pred[j++] = pred;
539 assert(j == len - 1);
541 reg->succ = NEW_ARR_D(ir_region *, obst, 1);
542 assert(ARR_LEN(head->succ) == 2);
544 succ = get_region_succ(head, 0);
548 reg->succ[0] = get_region_succ(head, 1);
550 DB((dbg, LEVEL_2, " Created WhileLoop(%u)Body(%u)\n", reg->nr, body->nr));
553 } /* new_WhileLoop */
556 * Create a new new_NaturalLoop region.
558 static ir_region *new_NaturalLoop(struct obstack *obst, ir_region *head)
560 ir_region *reg, *c, *n;
561 int i, j, k, len, n_pred, n_succ;
563 /* count number of parts */
564 for (len = 0, c = head; c != NULL; c = (ir_region*) c->link)
567 ALLOC_REG(obst, reg, ir_rk_WhileLoop);
570 reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, len);
572 /* enter all parts */
573 for (i = 0, c = head; c != NULL; c = n) {
574 reg->parts[i++].region = c;
576 n = (ir_region*) c->link;
580 /* count number of preds */
582 for (i = get_region_n_preds(head) - 1; i >= 0; --i) {
583 ir_region *pred = get_region_pred(head, i);
584 if (pred->parent != reg)
587 reg->pred = NEW_ARR_D(ir_region *, obst, n_pred);
588 for (j = 0, i = get_region_n_preds(head) - 1; i >= 0; --i) {
589 ir_region *pred = get_region_pred(head, i);
590 if (pred->parent != reg)
591 reg->pred[j++] = pred;
594 /* count number of succs */
596 for (j = 0; j < len; ++j) {
597 ir_region *pc = reg->parts[j].region;
598 for (i = get_region_n_succs(pc) - 1; i >= 0; --i) {
599 ir_region *succ = get_region_succ(pc, i);
600 if (succ->parent != reg)
604 reg->succ = NEW_ARR_D(ir_region *, obst, n_succ);
606 for (j = 0; j < len; ++j) {
607 ir_region *pc = reg->parts[j].region;
608 for (i = get_region_n_succs(pc) - 1; i >= 0; --i) {
609 ir_region *succ = get_region_succ(pc, i);
610 if (succ->parent != reg)
611 reg->succ[k++] = succ;
616 DB((dbg, LEVEL_2, " Created NaturalLoop(%u)Head(%u)\n", reg->nr, head->nr));
617 for (i = 1; i < len; ++i) {
618 ir_region *p = reg->parts[i].region;
619 DB((dbg, LEVEL_2, " Body(%u)\n", p->nr));
623 } /* new_NaturalLoop */
626 * Return true if region a is an ancestor of region b in DFS search.
628 static int is_ancestor(const ir_region *a, const ir_region *b)
630 return (a->prenum <= b->prenum && a->postnum > b->postnum);
634 * Return true if region pred is a predecessor of region n.
636 static int pred_of(const ir_region *pred, const ir_region *n)
639 for (i = get_region_n_preds(n) - 1; i >= 0; --i) {
640 if (get_region_pred(n, i) == pred)
647 * Return true if region succ is a successor of region n.
649 static int succ_of(const ir_region *succ, const ir_region *n)
652 for (i = get_region_n_succs(n) - 1; i >= 0; --i) {
653 if (get_region_succ(n, i) == succ)
660 * Reverse a linked list of regions.
662 static struct ir_region *reverse_list(ir_region *n)
664 ir_region *prev = NULL, *next;
666 for (; n; n = next) {
667 next = (ir_region*) n->link;
675 * Find the cyclic region in the subgraph entered by node.
677 static ir_region *find_cyclic_region(ir_region *node)
680 ir_region *last = node;
683 for (i = get_region_n_preds(node) - 1; i >= 0; --i) {
684 ir_region *pred = get_region_pred(node, i);
686 /* search backedges */
687 if (!pred->link && pred != last && is_ancestor(node, pred)) {
688 ir_region *rem = last;
693 for (j = get_region_n_preds(pred) - 1; j >= 0; --j) {
694 ir_region *p = get_region_pred(pred, j);
696 /* Search regions we didn't visited yet and
697 link them into the list. */
698 if (!p->link && p != last) {
699 if (is_ancestor(node, p)) {
707 /* reverse the list. */
708 last = (ir_region*) rem->link;
709 rem->link = reverse_list((ir_region*) rem->link);
713 if (node->link && improper) {
714 /* found an improper region, do minimization */
720 #define LINK(list) ((ir_region *)list->link)
723 * Detect a cyclic region.
725 static ir_region *cyclic_region_type(struct obstack *obst, ir_region *node)
729 /* simple cases first */
730 if (succ_of(node, node)) {
731 return new_SelfLoop(obst, node);
733 if (get_region_n_succs(node) == 1) {
734 ir_region *succ = get_region_succ(node, 0);
735 if (get_region_n_preds(succ) == 1 && succ_of(node, succ)) {
736 return new_RepeatLoop(obst, node, succ);
739 list = find_cyclic_region(node);
742 if (!LINK(list)->link && get_region_n_succs((ir_region*) list->link) == 1) {
743 /* only one body block with only one successor (the head) */
744 return new_WhileLoop(obst, list);
746 /* A Loop with one head */
747 return new_NaturalLoop(obst, list);
754 * Clear all links on a list. Needed, because we expect cleared links.
756 static void clear_list(ir_region *list)
760 for (next = list; next; list = next) {
761 next = (ir_region*) list->link;
766 #define ADD_LIST(list, n) do { n->link = list; list = n; ++list##_len; } while (0)
769 * Detect an acyclic region.
771 static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node)
775 ir_region *nset = NULL;
779 /* check for a block containing node */
781 p = get_region_n_preds(n) == 1;
784 n = get_region_pred(n, 0);
785 p = get_region_n_preds(n) == 1;
786 s = get_region_n_succs(n) == 1;
789 s = get_region_n_succs(n) == 1;
792 n = get_region_succ(n, 0);
793 p = get_region_n_preds(n) == 1;
794 s = get_region_n_succs(n) == 1;
800 /* node --> .. --> .. */
801 res = new_Sequence(obst, nset, nset_len);
806 /* check for IfThenElse */
807 k = get_region_n_succs(node);
809 int n_succs, m_succs, n_preds, m_preds;
811 n = get_region_succ(node, 0);
812 m = get_region_succ(node, 1);
814 n_succs = get_region_n_succs(n);
815 m_succs = get_region_n_succs(m);
816 n_preds = get_region_n_preds(n);
817 m_preds = get_region_n_preds(m);
818 if (n_succs == 1 && n_succs == m_succs && n_preds == m_preds &&
819 get_region_succ(n, 0) == get_region_succ(m, 0)) {
825 return new_IfThenElse(obst, node, n, m);
828 get_region_succ(n, 0) == m &&
834 return new_IfThen(obst, node, n);
837 get_region_succ(m, 0) == m &&
843 return new_IfThen(obst, node, m);
846 /* check for Switch, case */
848 ir_region *rexit = NULL;
849 nset = NULL; nset_len = 0;
851 for (i = k - 1; i >= 0; --i) {
852 n = get_region_succ(node, i);
854 if (get_region_n_succs(n) != 1) {
855 /* must be the exit */
863 ir_region_kind kind = ir_rk_Case;
864 ir_region *pos_exit_1 = NULL;
865 ir_region *pos_exit_2 = NULL;
868 for (m = (ir_region*) nset; m != NULL; m = (ir_region*) m->link) {
869 if (get_region_n_succs(m) != 1) {
870 /* must be the exit block */
873 } else if (rexit != m) {
879 ir_region *succ = get_region_succ(m, 0);
881 if (succ->link == NULL) {
883 if (succ == pos_exit_1)
885 else if (succ == pos_exit_2)
887 else if (pos_exit_1 == NULL)
889 else if (pos_exit_2 == NULL)
892 /* more than two possible exits */
895 } else if (rexit != succ) {
905 for (n = (ir_region*) nset; n != NULL; n = (ir_region*) n->link) {
908 /* good, default fall through */
911 succ = get_region_succ(n, 0);
913 /* good, switch to exit */
916 if (succ->link == NULL) {
927 return new_SwitchCase(obst, kind, node, rexit, nset, nset_len);
937 * replace all pred edges from region pred that points to any of the set set
938 * to ONE edge to reg.
940 static void replace_pred(ir_region *succ, ir_region *reg)
943 size_t len = get_region_n_preds(succ);
946 for (i = 0; i < len; ++i) {
947 ir_region *pred = get_region_pred(succ, i);
949 if (pred->parent == reg) {
954 r = get_region_pred(succ, --len);
960 set_region_pred(succ, i, r);
962 /* the current region can be entered by this node */
966 ARR_SHRINKLEN(succ->pred, len);
970 * replace all succ edges from region pred that points to any of the set set
971 * to ONE edge to reg.
973 static void replace_succ(ir_region *pred, ir_region *reg)
976 size_t len = get_region_n_succs(pred);
979 for (i = 0; i < len; ++i) {
980 ir_region *succ = get_region_succ(pred, i);
982 if (succ->parent == reg) {
987 r = get_region_succ(pred, --len);
993 set_region_succ(pred, i, r);
995 /* current region can be left by this node */
999 ARR_SHRINKLEN(pred->succ, len);
1003 * Reduce the graph by the node reg.
1005 static void reduce(walk_env *env, ir_region *reg)
1008 ir_region *head = reg->parts[0].region;
1009 unsigned maxorder = head->postnum;
1010 unsigned minorder = head->prenum;
1012 /* second step: replace all preds in successors */
1013 for (i = get_region_n_succs(reg) - 1; i >= 0; --i) {
1014 ir_region *succ = get_region_succ(reg, i);
1016 replace_pred(succ, reg);
1019 /* third step: replace all succs in predessors */
1020 for (i = get_region_n_preds(reg) - 1; i >= 0; --i) {
1021 ir_region *pred = get_region_pred(reg, i);
1023 replace_succ(pred, reg);
1026 reg->prenum = minorder;
1027 reg->postnum = maxorder;
1028 env->post[maxorder] = reg;
1032 * Construct the region tree of a graph by doing
1033 * structural analysis.
1035 * Uses link fields of nodes.
1037 * @param irg the graph
1039 ir_reg_tree *construct_region_tree(ir_graph *irg)
1042 ir_graph *rem = current_ir_graph;
1043 ir_reg_tree *res = XMALLOC(ir_reg_tree);
1045 obstack_init(&res->obst);
1047 current_ir_graph = irg;
1049 FIRM_DBG_REGISTER(dbg, "firm.ana.structure");
1050 firm_dbg_set_mask(dbg, SET_LEVEL_5);
1052 DB((dbg, LEVEL_1, "Structural analysis on %+F starts...\n", irg));
1054 /* we need dominance info */
1057 assure_irg_outs(irg);
1059 env.start_block = get_irg_start_block(irg);
1060 env.end_block = get_irg_end_block(irg);
1062 /* create the Block wrapper and count them */
1064 env.obst = &res->obst;
1065 irg_block_walk_graph(irg, NULL, wrap_BasicBlocks, &env);
1066 irg_block_walk_graph(irg, NULL, update_BasicBlock_regions, &env);
1068 env.post = NEW_ARR_F(ir_region *, env.l_post);
1070 /* do the DFS walk */
1071 dfs_walk(irg, &env);
1073 DB((dbg, LEVEL_1, "%d regions left\n", env.postmax));
1074 if (env.postmax > 1) {
1075 unsigned postctr = 0;
1077 ir_region *reg, *n = env.post[postctr];
1079 if (n->parent != NULL) {
1080 /* already folded */
1083 /* locate an acyclic region if present */
1084 reg = acyclic_region_type(env.obst, n);
1086 /* locate a cyclic region */
1087 reg = cyclic_region_type(env.obst, n);
1090 /* found a new region */
1094 } while (reg != NULL);
1096 } while (postctr < env.postmax);
1098 DB((dbg, LEVEL_1, "Structural analysis finished.\n"));
1100 DEL_ARR_F(env.post);
1101 current_ir_graph = rem;
1103 res->top = env.post[0];
1109 * Walk over the region tree.
1111 * @param reg a region node
1112 * @param pre walker function, executed before the children of a tree node are visited
1113 * @param post walker function, executed after the children of a tree node are visited
1114 * @param env environment, passed to pre and post
1116 static void region_tree_walk2(ir_region *reg, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env)
1122 if (reg->type != ir_rk_BasicBlock) {
1123 for (i = 0, n = ARR_LEN(reg->parts); i < n; ++i)
1124 region_tree_walk2(reg->parts[i].region, pre, post, env);
1131 * Walk over the region tree.
1133 * @param tree the tree
1134 * @param pre walker function, executed before the children of a tree node are visited
1135 * @param post walker function, executed after the children of a tree node are visited
1136 * @param env environment, passed to pre and post
1138 void region_tree_walk(ir_reg_tree *tree, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env)
1140 region_tree_walk2(tree->top, pre, post, env);