nsz Git - libfirm/blob - ir/ana/structure.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ana/structure.c
   4  * Purpose:     Structure Analysis
   5  * Author:      Michael Beck
   6  * Modified by:
   7  * Created:     5.4.2007
   8  * CVS-ID:      $Id: $
   9  * Copyright:   (c) 2007 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12 #ifdef HAVE_CONFIG_H
  13 #include "config.h"
  14 #endif
  15
  16 #include "firm_common.h"
  17 #include "irnode_t.h"
  18 #include "structure.h"
  19 #include "irdom.h"
  20 #include "irouts.h"
  21 #include "irtools.h"
  22 #include "irgwalk.h"
  23 #include "array.h"
  24 #include "irphase_t.h"
  25
  26 #include "debug.h"
  27
  28 typedef union ir_reg_or_blk ir_reg_or_blk;
  29
  30 /* The structure tree. */
  31 struct ir_reg_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. */
  35 };
  36
  37 /* A region. */
  38 struct ir_region {
  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. */
  50 };
  51
  52 /* A helper type for unioning blocks and regions. */
  53 union ir_reg_or_blk {
  54         firm_kind *kind;    /**< For easier check. */
  55         ir_node   *blk;     /**< A node */
  56         ir_region *region;  /**< A region. */
  57 };
  58
  59 /* The debug handle. */
  60 DEBUG_ONLY(firm_dbg_module_t *dbg;)
  61
  62 /**
  63  * Returns the link of a region.
  64  */
  65 void *get_region_link(const ir_region *reg) {
  66         return reg->link;
  67 }
  68
  69 /**
  70  * Sets the link of a region.
  71  */
  72 void set_region_link(ir_region *reg, void *data) {
  73         reg->link = data;
  74 }
  75
  76 /**
  77  * Get the immediate region of a block.
  78  */
  79 ir_region *get_block_region(const ir_node *block) {
  80         assert(is_Block(block));
  81         return get_irn_link(block);
  82 }
  83
  84 /**
  85  * Sets the immediate region of a block.
  86  */
  87 void set_block_region(ir_node *block, ir_region *reg) {
  88         assert(is_Block(block));
  89         set_irn_link(block, reg);
  90 }
  91
  92 /**
  93  * Get the immediate region of a node.
  94  */
  95 ir_region *get_irn_region(ir_node *n) {
  96         if (is_no_Block(n))
  97                 n = get_nodes_block(n);
  98         return get_block_region(n);
  99 }
 100
 101 /**
 102  * Return non-if a given firm thing is a region.
 103  */
 104 int is_region(const void *thing) {
 105         const firm_kind *kind = thing;
 106         return *kind == k_ir_region;
 107 }
 108
 109 /**
 110  * Return the number of predecessors in a region.
 111  */
 112 int get_region_n_preds(const ir_region *reg) {
 113         return ARR_LEN(reg->pred);
 114 }
 115
 116 /**
 117  * Return the predecessor region at position pos.
 118  */
 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];
 122 }
 123
 124 /**
 125  * Set the predecessor region at position pos.
 126  */
 127 void set_region_pred(ir_region *reg, int pos, ir_region *n) {
 128         assert(0 <= pos && pos <= get_region_n_preds(reg));
 129         reg->pred[pos] = n;
 130 }
 131
 132 /**
 133  * Return the number of successors in a region.
 134  */
 135 int get_region_n_succs(const ir_region *reg) {
 136         return ARR_LEN(reg->succ);
 137 }
 138
 139 /**
 140  * Return the successor region at position pos.
 141  */
 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];
 145 }
 146
 147 /**
 148  * Set the successor region at position pos.
 149  */
 150 void set_region_succ(ir_region *reg, int pos, ir_region *n) {
 151         assert(0 <= pos && pos <= get_region_n_succs(reg));
 152         reg->succ[pos] = n;
 153 }
 154
 155 /* ----------------------- construction -------------------------- */
 156
 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. */
 166 } walk_env;
 167
 168 /**
 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.
 171  */
 172 static void dfs_walk2(ir_region *reg, walk_env *env) {
 173         int i, n;
 174
 175         if (reg->visited == 0) {
 176                 reg->visited = 1;
 177
 178                 reg->prenum = env->premax++;
 179                 for (i = 0, n = get_region_n_succs(reg); i < n; ++i) {
 180                         /* recursion */
 181                         ir_region *succ = get_region_succ(reg, i);
 182                         dfs_walk2(succ, env);
 183                 }
 184
 185                 env->post[env->postmax] = reg;
 186                 reg->postnum = env->postmax++;
 187         }
 188 }
 189
 190 /**
 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.
 193  */
 194 static void dfs_walk(ir_graph *irg, walk_env *env) {
 195         ir_graph *rem = current_ir_graph;
 196         ir_region *reg;
 197
 198         current_ir_graph = irg;
 199         reg              = get_irn_link(get_irg_start_block(irg));
 200
 201         env->premax  = 0;
 202         env->postmax = 0;
 203         dfs_walk2(reg, env);
 204         current_ir_graph = rem;
 205 }
 206
 207 /**
 208  * Post-walker: wrap all blocks with a Block region
 209  * and count them
 210  */
 211 static void wrap_blocks(ir_node *block, void *ctx) {
 212         walk_env *env = ctx;
 213         ir_region *reg;
 214
 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;
 219         reg->parent  = NULL;
 220         reg->prenum  = 0;
 221         reg->postnum = 0;
 222         reg->visited = 0;
 223         reg->link    = NULL;
 224         reg->nr      = get_irn_node_nr(block);
 225         reg->parts   = NEW_ARR_D(ir_reg_or_blk, env->obst, 1);
 226
 227         reg->parts[0].blk = block;
 228         set_irn_link(block, reg);
 229
 230         ++env->l_post;
 231 }  /* wrap_blocks */
 232
 233 /**
 234  * Create the pred and succ edges for Block wrapper.
 235  * Kill edges to the Start and End blocks.
 236  */
 237 static void update_Block_regions(ir_node *blk, void *ctx) {
 238         walk_env *env = ctx;
 239         ir_region *reg = get_irn_link(blk);
 240         int i, j, len;
 241
 242         if (blk == env->start_block) {
 243                 /* handle Firm's self loop */
 244                 reg->pred = NEW_ARR_D(ir_region *, env->obst, 0);
 245         } else {
 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);
 251                 }
 252                 ARR_SHRINKLEN(reg->pred, j);
 253         }
 254
 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);
 260         }
 261         ARR_SHRINKLEN(reg->succ, j);
 262 }
 263
 264 /** Allocate a new region of a obstack */
 265 #define ALLOC_REG(obst, reg, tp) \
 266         do { \
 267                 (reg)          = obstack_alloc((obst), sizeof(*(reg))); \
 268                 (reg)->kind    = k_ir_region; \
 269                 (reg)->type    = tp; \
 270                 (reg)->parent  = NULL; \
 271                 (reg)->prenum  = 0; \
 272                 (reg)->postnum = 0; \
 273                 (reg)->visited = 0; \
 274                 (reg)->link    = NULL; \
 275         } while (0)
 276
 277 /**
 278  * Creates a new Sequence region.
 279  */
 280 static ir_region *new_Sequence(struct obstack *obst, ir_region *nset, int nset_len) {
 281         ir_region *reg;
 282         int i;
 283
 284         ALLOC_REG(obst, reg, ir_rk_Sequence);
 285
 286         reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, nset_len);
 287
 288         /* beware: list is in reverse order, reverse */
 289         for (i = nset_len - 1; i >= 0; --i) {
 290                 reg->parts[i].region = nset;
 291                 nset->parent = reg;
 292                 nset = nset->link;
 293         }
 294
 295         reg->nr   = reg->parts[0].region->nr;
 296         reg->pred = DUP_ARR_D(ir_region *, obst, reg->parts[0].region->pred);
 297         reg->succ = DUP_ARR_D(ir_region *, obst, reg->parts[nset_len - 1].region->succ);
 298
 299         DEBUG_ONLY(
 300                 DB((dbg, LEVEL_2, " Created Sequence "));
 301                 for (i = 0; i < nset_len; ++i) {
 302                         DB((dbg, LEVEL_2, "(%u)", reg->parts[i].region->nr));
 303                 }
 304                 DB((dbg, LEVEL_2, "\n"));
 305         )
 306         return reg;
 307 }  /* new_Sequence */
 308
 309 /**
 310  * Create a new IfThenElse region.
 311  */
 312 static ir_region *new_IfThenElse(struct obstack *obst, ir_region *if_b, ir_region *then_b, ir_region *else_b) {
 313         ir_region *reg;
 314
 315         ALLOC_REG(obst, reg, ir_rk_IfThenElse);
 316
 317         reg->nr    = if_b->nr;
 318         reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 3);
 319
 320         reg->parts[0].region = if_b;   if_b->parent   = reg;
 321         reg->parts[1].region = then_b; then_b->parent = reg;
 322         reg->parts[2].region = else_b; else_b->parent = reg;
 323
 324         reg->pred = DUP_ARR_D(ir_region *, obst, if_b->pred);
 325         reg->succ = DUP_ARR_D(ir_region *, obst, then_b->succ);
 326
 327         DB((dbg, LEVEL_2, " Created If(%u)Then(%u)Else(%u)\n", reg->nr, then_b->nr, else_b->nr));
 328
 329         return reg;
 330 }  /* new_IfThenElse */
 331
 332 /**
 333  * Create a new IfThen region.
 334  */
 335 static ir_region *new_IfThen(struct obstack *obst, ir_region *if_b, ir_region *then_b) {
 336         ir_region *reg;
 337
 338         ALLOC_REG(obst, reg, ir_rk_IfThen);
 339
 340         reg->nr    = if_b->nr;
 341         reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 2);
 342
 343         reg->parts[0].region = if_b;   if_b->parent   = reg;
 344         reg->parts[1].region = then_b; then_b->parent = reg;
 345
 346         reg->pred = DUP_ARR_D(ir_region *, obst, if_b->pred);
 347         reg->succ = DUP_ARR_D(ir_region *, obst, then_b->succ);
 348
 349         DB((dbg, LEVEL_2, " Created If(%u)Then(%u)\n", reg->nr, then_b->nr));
 350
 351         return reg;
 352 }  /* new_IfThenElse */
 353
 354 /**
 355  * Create a new Switch/case region.
 356  */
 357 static ir_region *new_SwitchCase(struct obstack *obst, ir_region_kind type, ir_region *head, ir_region *exit,
 358                                  ir_region *cases, int cases_len) {
 359         ir_region *reg, *c, *n;
 360         int i;
 361         int add = 1;
 362
 363         /* check, if the exit block is in the list */
 364         for (c = cases; c != NULL; c = c->link) {
 365                 if (c == exit) {
 366                         add = 0;
 367                         break;
 368                 }
 369         }
 370
 371         ALLOC_REG(obst, reg, type);
 372
 373         reg->nr    = head->nr;
 374         reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, cases_len + add);
 375
 376         reg->parts[0].region = head; head->parent = reg;
 377         i = 1;
 378         for (c = cases; c != NULL; c = n) {
 379                 n = c->link;
 380                 if (c != exit) {
 381                         reg->parts[i++].region = c;
 382                         c->parent = reg;
 383                 }
 384                 c->link = NULL;
 385         }
 386
 387         reg->pred = DUP_ARR_D(ir_region *, obst, head->pred);
 388         reg->succ = NEW_ARR_D(ir_region *, obst, 1);
 389         reg->succ[0] = exit;
 390
 391         DEBUG_ONLY(
 392                 DB((dbg, LEVEL_2, " Created %s(%u)\n", reg->type == ir_rk_Switch ? "Switch" : "Case", reg->nr));
 393                 for (i = 1; i < ARR_LEN(reg->parts); ++i) {
 394                         DB((dbg, LEVEL_2, "  Case(%u)\n", reg->parts[i].region->nr));
 395                 }
 396                 DB((dbg, LEVEL_2, "  Exit(%u)\n", exit->nr));
 397         )
 398         return reg;
 399 }  /* new_SwitchCase */
 400
 401 /**
 402  * Create a new SelfLoop region.
 403  */
 404 static ir_region *new_SelfLoop(struct obstack *obst, ir_region *head) {
 405         ir_region *reg, *succ;
 406         int i, j, len;
 407
 408         ALLOC_REG(obst, reg, ir_rk_SelfLoop);
 409
 410         reg->nr      = head->nr;
 411         reg->parts   = NEW_ARR_D(ir_reg_or_blk, obst, 1);
 412
 413         reg->parts[0].region = head; head->parent = reg;
 414
 415         len = ARR_LEN(head->pred);
 416         reg->pred = NEW_ARR_D(ir_region *, obst, len - 1);
 417         for (i = j = 0; i < len; ++i) {
 418                 ir_region *pred = get_region_pred(head, i);
 419                 if (pred != head)
 420                         reg->pred[j++] = pred;
 421         }
 422         assert(j == len - 1);
 423
 424         reg->succ = NEW_ARR_D(ir_region *, obst, 1);
 425         assert(ARR_LEN(head->succ) == 2);
 426
 427         succ = get_region_succ(head, 0);
 428         if (succ != head)
 429                 reg->succ[0] = succ;
 430         else
 431                 reg->succ[0] = get_region_succ(head, 1);
 432
 433         DB((dbg, LEVEL_2, " Created SelfLoop(%u)\n", reg->nr));
 434
 435         return reg;
 436 }  /* new_SelfLoop */
 437
 438 /**
 439  * Create a new RepeatLoop region.
 440  */
 441 static ir_region *new_RepeatLoop(struct obstack *obst, ir_region *head, ir_region *body) {
 442         ir_region *reg, *succ;
 443
 444         ALLOC_REG(obst, reg, ir_rk_RepeatLoop);
 445
 446         reg->nr      = head->nr;
 447         reg->parts   = NEW_ARR_D(ir_reg_or_blk, obst, 2);
 448
 449         reg->parts[0].region = head; head->parent = reg;
 450         reg->parts[1].region = body; body->parent = reg;
 451
 452         reg->pred = DUP_ARR_D(ir_region *, obst, head->pred);
 453         reg->succ = NEW_ARR_D(ir_region *, obst, 1);
 454         assert(ARR_LEN(body->succ) == 2);
 455
 456         succ = get_region_succ(body, 0);
 457         if (succ != head)
 458                 reg->succ[0] = succ;
 459         else
 460                 reg->succ[0] = get_region_succ(body, 1);
 461
 462         DB((dbg, LEVEL_2, " Created RepeatLoop(%u)Body(%u)\n", reg->nr, body->nr));
 463
 464         return reg;
 465 }  /* new_RepeatLoop */
 466
 467 /**
 468  * Create a new WhileLoop region.
 469  */
 470 static ir_region *new_WhileLoop(struct obstack *obst, ir_region *head) {
 471         ir_region *reg, *succ;
 472         ir_region *body = head->link;
 473         int i, j, len;
 474
 475         head->link = NULL;
 476
 477         ALLOC_REG(obst, reg, ir_rk_WhileLoop);
 478
 479         reg->nr      = head->nr;
 480         reg->parts   = NEW_ARR_D(ir_reg_or_blk, obst, 2);
 481
 482         reg->parts[0].region = head; head->parent = reg;
 483         reg->parts[1].region = body; body->parent = reg;
 484
 485         len = ARR_LEN(head->pred);
 486         reg->pred = NEW_ARR_D(ir_region *, obst, len - 1);
 487         for (i = j = 0; i < len; ++i) {
 488                 ir_region *pred = get_region_pred(head, i);
 489                 if (pred != body)
 490                         reg->pred[j++] = pred;
 491         }
 492         assert(j == len - 1);
 493
 494         reg->succ = NEW_ARR_D(ir_region *, obst, 1);
 495         assert(ARR_LEN(head->succ) == 2);
 496
 497         succ = get_region_succ(head, 0);
 498         if (succ != body)
 499                 reg->succ[0] = succ;
 500         else
 501                 reg->succ[0] = get_region_succ(head, 1);
 502
 503         DB((dbg, LEVEL_2, " Created WhileLoop(%u)Body(%u)\n", reg->nr, body->nr));
 504
 505         return reg;
 506 }  /* new_WhileLoop */
 507
 508 /**
 509  * Return true if a is an ancestor of b in DFS search.
 510  */
 511 static int is_ancestor(const ir_region *a, const ir_region *b) {
 512         return (a->prenum <= b->prenum && a->postnum > b->postnum);
 513 }
 514
 515 /**
 516  *  Return true if region succ is a successor of region n.
 517  */
 518 static int succ_of(const ir_region *succ, const ir_region *n) {
 519         int i;
 520         for (i = get_region_n_succs(n) - 1; i >= 0; --i) {
 521                 if (get_region_succ(n, i) == succ)
 522                         return 1;
 523         }
 524         return 0;
 525 }
 526
 527 /**
 528  *  Reverse linked list.
 529  */
 530 static struct ir_region *reverse_list(ir_region *n) {
 531         ir_region *prev = NULL, *next;
 532
 533         for (; n; n = next) {
 534                 next = n->link;
 535                 n->link = prev;
 536                 prev = n;
 537         }
 538         return prev;
 539 }
 540
 541 /**
 542  * Find the cyclic region in the subgraph entered by node.
 543  */
 544 static ir_region *find_cyclic_region(ir_region *node) {
 545         int i;
 546         ir_region *last = node;
 547         int improper = 0;
 548
 549         for (i = get_region_n_preds(node) - 1; i >= 0; --i) {
 550                 ir_region *pred = get_region_pred(node, i);
 551
 552                 /* search backedges */
 553                 if (!pred->link && pred != last && is_ancestor(node, pred)) {
 554                         ir_region *rem = last;
 555                         int j;
 556
 557                         last->link = pred;
 558                         last       = pred;
 559                         for (j = get_region_n_preds(pred) - 1; j >= 0; --j) {
 560                                 ir_region *p = get_region_pred(pred, j);
 561
 562                                 /* Search regions we didn't visited yet and
 563                                    link them into the list. */
 564                                 if (!p->link && p != last) {
 565                                         if (is_ancestor(node, p)) {
 566                                                 last->link = p;
 567                                                 last       = p;
 568                                         } else {
 569                                                 improper = 1;
 570                                         }
 571                                 }
 572                         }
 573                         /* reverse the list. */
 574                         last = rem->link;
 575                         rem->link = reverse_list(rem->link);
 576                 }
 577         }
 578
 579         if (node->link && improper) {
 580                 /* found an improper region */
 581         }
 582         return node;
 583 }
 584
 585 #define LINK(list) ((ir_region *)list->link)
 586
 587 /**
 588  * Detect a cyclic region.
 589  */
 590 static ir_region *cyclic_region_type(struct obstack *obst, ir_region *node) {
 591         ir_region *list;
 592
 593         /* simple cases first */
 594         if (succ_of(node, node)) {
 595                 return new_SelfLoop(obst, node);
 596         }
 597         if (get_region_n_succs(node) == 1) {
 598                 ir_region *succ = get_region_succ(node, 0);
 599                 if (get_region_n_preds(succ) == 1 && succ_of(node, succ)) {
 600                         return new_RepeatLoop(obst, node, succ);
 601                 }
 602         }
 603         list = find_cyclic_region(node);
 604
 605         if (list->link && !LINK(list)->link && get_region_n_succs(list->link) == 1) {
 606                 return new_WhileLoop(obst, list);
 607         }
 608
 609         return NULL;
 610 }
 611
 612 /**
 613  * Clear all links on a list. Needed, because we expect cleared links-
 614  */
 615 static void clear_list(ir_region *list) {
 616         ir_region *next;
 617
 618         for (next = list; next; list = next) {
 619                 next = list->link;
 620                 list->link = NULL;
 621         }
 622 }
 623
 624 #define ADD_LIST(list, n) do { n->link = list; list = n; ++list##_len; } while(0)
 625
 626 /**
 627  * Detect an acyclic region.
 628  */
 629 static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node) {
 630         ir_region *n, *m;
 631         int p, s, i, k;
 632         ir_region *nset = NULL;
 633         int nset_len = 0;
 634         ir_region *res;
 635
 636         /* check for a block containing node */
 637         n = node;
 638         p = get_region_n_preds(n) == 1;
 639         s = 1;
 640         while (p & s) {
 641                 n = get_region_pred(n, 0);
 642                 p = get_region_n_preds(n) == 1;
 643                 s = get_region_n_succs(n) == 1;
 644         }
 645         p = 1;
 646         s = get_region_n_succs(n) == 1;
 647         while (p & s) {
 648                 ADD_LIST(nset, n);
 649                 n = get_region_succ(n, 0);
 650                 p = get_region_n_preds(n) == 1;
 651                 s = get_region_n_succs(n) == 1;
 652         }
 653         if (p) {
 654                 ADD_LIST(nset, n);
 655         }
 656         if (nset_len > 1) {
 657                 /* node --> .. --> .. */
 658                 res = new_Sequence(obst, nset, nset_len);
 659                 return res;
 660         }
 661         node = n;
 662
 663         /* check for IfThenElse */
 664         k = get_region_n_succs(node);
 665         if (k == 2) {
 666                 int n_succs, m_succs, n_preds, m_preds;
 667
 668                 n = get_region_succ(node, 0);
 669                 m = get_region_succ(node, 1);
 670
 671                 n_succs = get_region_n_succs(n);
 672                 m_succs = get_region_n_succs(m);
 673                 n_preds = get_region_n_preds(n);
 674                 m_preds = get_region_n_preds(m);
 675                 if (n_succs == 1 && n_succs == m_succs && n_preds == m_preds &&
 676                     get_region_succ(n, 0) == get_region_succ(m, 0)) {
 677                         /*
 678                          *    /-->n---\
 679                          * node      ...
 680                          *    \-->m---/
 681                          */
 682                         return new_IfThenElse(obst, node, n, m);
 683                 }
 684                 if (n_succs == 1 && m_preds == 2 &&
 685                     get_region_succ(n, 0) == m &&
 686                     (get_region_pred(m, 0) == node ||
 687                      get_region_pred(m, 1) == node)) {
 688                         /*
 689                          * node -->n-->m
 690                          *    \-------/
 691                          */
 692                         return new_IfThen(obst, node, n);
 693                 }
 694                 if (m_succs == 1 && n_preds == 2 &&
 695                     get_region_succ(m, 0) == m &&
 696                     (get_region_pred(n, 0) == node ||
 697                      get_region_pred(n, 1) == node)) {
 698                         /*
 699                          * node -->m-->n
 700                          *    \-------/
 701                          */
 702                         return new_IfThen(obst, node, m);
 703                 }
 704         }
 705         /* check for Switch, case */
 706         if (k > 0) {
 707                 ir_region *exit = NULL;
 708                 nset = NULL; nset_len = 0;
 709                 p = 0;
 710                 for (i = k - 1; i >= 0; --i) {
 711                         n = get_region_succ(node, i);
 712                         ADD_LIST(nset, n);
 713                         if (get_region_n_succs(n) != 1) {
 714                                 /* must be the exit */
 715                                 exit = n;
 716                                 ++p;
 717                                 if (p > 1)
 718                                         break;
 719                         }
 720                 }
 721                 if (p <= 1) {
 722                         ir_region_kind kind = ir_rk_Case;
 723                         ir_region *pos_exit_1 = NULL;
 724                         ir_region *pos_exit_2 = NULL;
 725
 726                         /* find the exit */
 727                         for (m = nset; m != NULL; m = m->link) {
 728                                 if (get_region_n_succs(m) != 1) {
 729                                         /* must be the exit block */
 730                                         if (exit == NULL) {
 731                                                 exit = m;
 732                                         } else if (exit != m) {
 733                                                 /* two exits */
 734                                                 exit = NULL;
 735                                                 break;
 736                                         }
 737                                 } else {
 738                                         ir_region *succ = get_region_succ(m, 0);
 739
 740                                         if (succ->link == NULL) {
 741                                                 if (exit == NULL) {
 742                                                         if (succ == pos_exit_1)
 743                                                                 exit = succ;
 744                                                         else if (succ == pos_exit_2)
 745                                                                 exit = succ;
 746                                                         else if (pos_exit_1 == NULL)
 747                                                                 pos_exit_1 = succ;
 748                                                         else if (pos_exit_2 == NULL)
 749                                                                 pos_exit_2 = succ;
 750                                                         else {
 751                                                                 /* more than two possible exits */
 752                                                                 break;
 753                                                         }
 754                                                 } else if (exit != succ) {
 755                                                         /* two exits */
 756                                                         exit = NULL;
 757                                                         break;
 758                                                 }
 759                                         }
 760                                 }
 761                         }
 762                         if (exit != NULL) {
 763                                 /* do the checks */
 764                                 for (n = nset; n != NULL; n = n->link) {
 765                                         ir_region *succ;
 766                                         if (n == exit) {
 767                                                 /* good, default fall through */
 768                                                 continue;
 769                                         }
 770                                         succ = get_region_succ(n, 0);
 771                                         if (succ == exit) {
 772                                                 /* good, switch to exit */
 773                                                 continue;
 774                                         }
 775                                         if (succ->link == NULL) {
 776                                                 /* another exit */
 777                                                 break;
 778                                         } else {
 779                                                 /* a fall through */
 780                                                 kind = ir_rk_Switch;
 781                                         }
 782                                 }
 783
 784                                 if (n == NULL) {
 785                                         /* detected */
 786                                         return new_SwitchCase(obst, kind, node, exit, nset, nset_len);
 787                                 }
 788                         }
 789                 }
 790                 clear_list(nset);
 791         }
 792         return NULL;
 793 }
 794
 795 /**
 796  * Fill the given set recursively with all parts of the region (including itself)
 797  */
 798 static void fill_parts(pset *set, ir_region *reg) {
 799         int i;
 800
 801         if (reg->type == ir_rk_Block) {
 802                 pset_insert_ptr(set, reg);
 803                 return;
 804         }
 805
 806         for (i = ARR_LEN(reg->parts) - 1; i >= 0; --i) {
 807                 fill_parts(set, reg->parts[i].region);
 808         }
 809 }
 810
 811 /**
 812  * replace all pred edges from region pred that points to any of the set set
 813  * to ONE edge to reg.
 814  */
 815 static void replace_pred(ir_region *succ, ir_region *reg) {
 816         int i, len = get_region_n_preds(succ);
 817         int have_one = 0;
 818
 819         for (i = 0; i < len; ++i) {
 820                 ir_region *pred = get_region_pred(succ, i);
 821
 822                 if (pred->parent == reg) {
 823                         ir_region *r;
 824
 825                         if (have_one) {
 826                                 /* kill it */
 827                                 r = get_region_pred(succ, --len);
 828                         } else {
 829                                 /* replace it */
 830                                 have_one = 1;
 831                                 r = reg;
 832                         }
 833                         set_region_pred(succ, i, r);
 834                 }
 835         }
 836         ARR_SHRINKLEN(succ->pred, len);
 837 }
 838
 839 /**
 840  * replace all succ edges from region pred that points to any of the set set
 841  * to ONE edge to reg.
 842  */
 843 static void replace_succ(ir_region *pred, ir_region *reg) {
 844         int i, len = get_region_n_succs(pred);
 845         int have_one = 0;
 846
 847         for (i = 0; i < len; ++i) {
 848                 ir_region *succ = get_region_succ(pred, i);
 849
 850                 if (succ->parent == reg) {
 851                         ir_region *r;
 852
 853                         if (have_one) {
 854                                 /* kill it */
 855                                 r = get_region_succ(pred, --len);
 856                         } else {
 857                                 /* replace it */
 858                                 have_one = 1;
 859                                 r = reg;
 860                         }
 861                         set_region_succ(pred, i, r);
 862                 }
 863         }
 864         ARR_SHRINKLEN(pred->succ, len);
 865 }
 866
 867 /**
 868  * Reduce the graph by the node reg.
 869  */
 870 static void reduce(walk_env *env, ir_region *reg) {
 871         int i;
 872         ir_region *head = reg->parts[0].region;
 873         unsigned maxorder = head->postnum;
 874         unsigned minorder = head->prenum;
 875
 876         /* second step: replace all preds in successors */
 877         for (i = get_region_n_succs(reg) - 1; i >= 0; --i) {
 878                 ir_region *succ = get_region_succ(reg, i);
 879
 880                 replace_pred(succ, reg);
 881         }
 882
 883         /* second third: replace all succs in predessors */
 884         for (i = get_region_n_preds(reg) - 1; i >= 0; --i) {
 885                 ir_region *pred = get_region_pred(reg, i);
 886
 887                 replace_succ(pred, reg);
 888         }
 889
 890         reg->prenum  = minorder;
 891         reg->postnum = maxorder;
 892         env->post[maxorder] = reg;
 893 }
 894
 895 /**
 896  * Construct the region tree of a graph by doing
 897  * structural analysis.
 898  *
 899  * Uses link fields of nodes.
 900  *
 901  * @param irg  the graph
 902  */
 903 ir_reg_tree *construct_region_tree(ir_graph *irg) {
 904         walk_env env;
 905         ir_graph *rem = current_ir_graph;
 906         ir_reg_tree *res = xmalloc(sizeof(*res));
 907
 908         obstack_init(&res->obst);
 909
 910         current_ir_graph = irg;
 911
 912         FIRM_DBG_REGISTER(dbg, "firm.ana.structure");
 913         firm_dbg_set_mask(dbg, SET_LEVEL_5);
 914
 915         DB((dbg, LEVEL_1, "Structural analysis on %+F starts...\n", irg));
 916
 917         dump_ir_block_graph(irg, "-structure_start");
 918
 919         /* we need dominance info */
 920         assure_doms(irg);
 921         /* and out edges */
 922         assure_irg_outs(irg);
 923
 924         env.start_block = get_irg_start_block(irg);
 925         env.end_block   = get_irg_end_block(irg);
 926
 927         /* create the Block wrapper and count them */
 928         env.l_post = 0;
 929         env.obst   = &res->obst;
 930         irg_block_walk_graph(irg, NULL, wrap_blocks, &env);
 931         irg_block_walk_graph(irg, NULL, update_Block_regions, &env);
 932
 933         env.post = NEW_ARR_F(ir_region *, env.l_post);
 934
 935         /* do the DFS walk */
 936         dfs_walk(irg, &env);
 937
 938         DB((dbg, LEVEL_1, "%d regions left\n", env.postmax));
 939         if (env.postmax > 1) {
 940                 unsigned postctr = 0;
 941                 do {
 942                         ir_region *reg, *n = env.post[postctr];
 943                         do {
 944                                 if (n->parent) {
 945                                         /* already folded */
 946                                         break;
 947                                 }
 948                                 /* locate an acyclic region if present */
 949                                 reg = acyclic_region_type(env.obst, n);
 950                                 if (reg == NULL) {
 951                                         /* locate a cyclic region */
 952                                         reg = cyclic_region_type(env.obst, n);
 953                                 }
 954                                 if (reg != NULL) {
 955                                         /* found a new region */
 956                                         reduce(&env, reg);
 957                                         n = reg;
 958                                 }
 959                         } while (reg != NULL);
 960                         ++postctr;
 961                 } while (postctr < env.postmax);
 962         }
 963         DB((dbg, LEVEL_1, "Structural analysis finished.\n"));
 964
 965         DEL_ARR_F(env.post);
 966         current_ir_graph = rem;
 967
 968         res->top = env.post[0];
 969         res->irg = irg;
 970         return res;
 971 }
 972
 973 /**
 974  * Walk over the region tree.
 975  *
 976  * @param reg   a region node
 977  * @param pre   walker function, executed before the children of a tree node are visited
 978  * @param post  walker function, executed after the children of a tree node are visited
 979  * @param env   environment, passed to pre and post
 980  */
 981 static void region_tree_walk2(ir_region *reg, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env) {
 982         int i, n;
 983
 984         if (pre)
 985                 pre(reg, env);
 986         if (reg->type != ir_rk_Block) {
 987                 for (i = 0, n = ARR_LEN(reg->parts); i < n; ++i)
 988                         region_tree_walk2(reg->parts[i].region, pre, post, env);
 989         }
 990         if (post)
 991                 post(reg, env);
 992 }
 993
 994 /**
 995  * Walk over the region tree.
 996  *
 997  * @param tree  the tree
 998  * @param pre   walker function, executed before the children of a tree node are visited
 999  * @param post  walker function, executed after the children of a tree node are visited
1000  * @param env   environment, passed to pre and post
1001  */
1002 void region_tree_walk(ir_reg_tree *tree, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env) {
1003         region_tree_walk2(tree->top, pre, post, env);
1004 }