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[]) {
 281         ir_region *reg;
 282         int i, len = ARR_LEN(nset);
 283
 284         ALLOC_REG(obst, reg, ir_rk_Sequence);
 285
 286         reg->nr    = nset[0]->nr;
 287         reg->parts = CLONE_ARR_D(ir_reg_or_blk, obst, nset);
 288         reg->pred  = DUP_ARR_D(ir_region *, obst, nset[0]->pred);
 289         reg->succ  = DUP_ARR_D(ir_region *, obst, nset[len - 1]->succ);
 290
 291         for (i = 0; i < len; ++i) {
 292                 reg->parts[i].region = nset[i];
 293                 nset[i]->parent = reg;
 294         }
 295
 296         DEBUG_ONLY(
 297                 DB((dbg, LEVEL_2, " Created Sequence "));
 298                 for (i = 0; i < len; ++i) {
 299                         DB((dbg, LEVEL_2, "(%u)", reg->parts[i].region->nr));
 300                 }
 301                 DB((dbg, LEVEL_2, "\n"));
 302         )
 303         return reg;
 304 }  /* new_Sequence */
 305
 306 /**
 307  * Create a new IfThenElse region.
 308  */
 309 static ir_region *new_IfThenElse(struct obstack *obst, ir_region *if_b, ir_region *then_b, ir_region *else_b) {
 310         ir_region *reg;
 311
 312         ALLOC_REG(obst, reg, ir_rk_IfThenElse);
 313
 314         reg->nr    = if_b->nr;
 315         reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 3);
 316
 317         reg->parts[0].region = if_b;   if_b->parent   = reg;
 318         reg->parts[1].region = then_b; then_b->parent = reg;
 319         reg->parts[2].region = else_b; else_b->parent = reg;
 320
 321         reg->pred = DUP_ARR_D(ir_region *, obst, if_b->pred);
 322         reg->succ = DUP_ARR_D(ir_region *, obst, then_b->succ);
 323
 324         DB((dbg, LEVEL_2, " Created If(%u)Then(%u)Else(%u)\n", reg->nr, then_b->nr, else_b->nr));
 325
 326         return reg;
 327 }  /* new_IfThenElse */
 328
 329 /**
 330  * Create a new IfThen region.
 331  */
 332 static ir_region *new_IfThen(struct obstack *obst, ir_region *if_b, ir_region *then_b) {
 333         ir_region *reg;
 334
 335         ALLOC_REG(obst, reg, ir_rk_IfThen);
 336
 337         reg->nr    = if_b->nr;
 338         reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 2);
 339
 340         reg->parts[0].region = if_b;   if_b->parent   = reg;
 341         reg->parts[1].region = then_b; then_b->parent = reg;
 342
 343         reg->pred = DUP_ARR_D(ir_region *, obst, if_b->pred);
 344         reg->succ = DUP_ARR_D(ir_region *, obst, then_b->succ);
 345
 346         DB((dbg, LEVEL_2, " Created If(%u)Then(%u)\n", reg->nr, then_b->nr));
 347
 348         return reg;
 349 }  /* new_IfThenElse */
 350
 351 /**
 352  * Create a new Switch/case region.
 353  */
 354 static ir_region *new_SwitchCase(struct obstack *obst, ir_region_kind type, ir_region *head, ir_region *end, pset *cases) {
 355         ir_region *reg, *c;
 356         int i;
 357
 358         ALLOC_REG(obst, reg, type);
 359
 360         reg->nr    = head->nr;
 361         reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, pset_count(cases) + 1);
 362
 363         reg->parts[0].region = head; head->parent = reg;
 364         i = 0;
 365         foreach_pset(cases, c) {
 366                 reg->parts[i].region = c;
 367                 c->parent = reg;
 368         }
 369
 370         reg->pred = DUP_ARR_D(ir_region *, obst, head->pred);
 371         reg->succ = NEW_ARR_D(ir_region *, obst, 1);
 372         reg->succ[0] = end;
 373
 374         DB((dbg, LEVEL_2, " Created Switch(%u)Exit(%u)\n", reg->nr, end->nr));
 375
 376         del_pset(cases);
 377         return reg;
 378 }  /* new_SwitchCase */
 379
 380 /**
 381  * Create a new SelfLoop region.
 382  */
 383 static ir_region *new_SelfLoop(struct obstack *obst, ir_region *head) {
 384         ir_region *reg, *succ;
 385         int i, j, len;
 386
 387         ALLOC_REG(obst, reg, ir_rk_SelfLoop);
 388
 389         reg->nr      = head->nr;
 390         reg->parts   = NEW_ARR_D(ir_reg_or_blk, obst, 1);
 391
 392         reg->parts[0].region = head; head->parent = reg;
 393
 394         len = ARR_LEN(head->pred);
 395         reg->pred = NEW_ARR_D(ir_region *, obst, len - 1);
 396         for (i = j = 0; i < len; ++i) {
 397                 ir_region *pred = get_region_pred(head, i);
 398                 if (pred != head)
 399                         reg->pred[j++] = pred;
 400         }
 401         assert(j == len - 1);
 402
 403         reg->succ = NEW_ARR_D(ir_region *, obst, 1);
 404         assert(ARR_LEN(head->succ) == 2);
 405
 406         succ = get_region_succ(head, 0);
 407         if (succ != head)
 408                 reg->succ[0] = succ;
 409         else
 410                 reg->succ[0] = get_region_succ(head, 1);
 411
 412         DB((dbg, LEVEL_2, " Created SelfLoop(%u)\n", reg->nr));
 413
 414         return reg;
 415 }  /* new_SelfLoop */
 416
 417 /**
 418  * Create a new RepeatLoop region.
 419  */
 420 static ir_region *new_RepeatLoop(struct obstack *obst, ir_region *head, ir_region *body) {
 421         ir_region *reg, *succ;
 422
 423         ALLOC_REG(obst, reg, ir_rk_RepeatLoop);
 424
 425         reg->nr      = head->nr;
 426         reg->parts   = NEW_ARR_D(ir_reg_or_blk, obst, 2);
 427
 428         reg->parts[0].region = head; head->parent = reg;
 429         reg->parts[1].region = body; body->parent = reg;
 430
 431         reg->pred = DUP_ARR_D(ir_region *, obst, head->pred);
 432         reg->succ = NEW_ARR_D(ir_region *, obst, 1);
 433         assert(ARR_LEN(body->succ) == 2);
 434
 435         succ = get_region_succ(body, 0);
 436         if (succ != head)
 437                 reg->succ[0] = succ;
 438         else
 439                 reg->succ[0] = get_region_succ(body, 1);
 440
 441         DB((dbg, LEVEL_2, " Created RepeatLoop(%u)Body(%u)\n", reg->nr, body->nr));
 442
 443         return reg;
 444 }  /* new_RepeatLoop */
 445
 446 /**
 447  * Create a new WhileLoop region.
 448  */
 449 static ir_region *new_WhileLoop(struct obstack *obst, ir_region *head) {
 450         ir_region *reg, *succ;
 451         ir_region *body = head->link;
 452         int i, j, len;
 453
 454         head->link = NULL;
 455
 456         ALLOC_REG(obst, reg, ir_rk_WhileLoop);
 457
 458         reg->nr      = head->nr;
 459         reg->parts   = NEW_ARR_D(ir_reg_or_blk, obst, 2);
 460
 461         reg->parts[0].region = head; head->parent = reg;
 462         reg->parts[1].region = body; body->parent = reg;
 463
 464         len = ARR_LEN(head->pred);
 465         reg->pred = NEW_ARR_D(ir_region *, obst, len - 1);
 466         for (i = j = 0; i < len; ++i) {
 467                 ir_region *pred = get_region_pred(head, i);
 468                 if (pred != body)
 469                         reg->pred[j++] = pred;
 470         }
 471         assert(j == len - 1);
 472
 473         reg->succ = NEW_ARR_D(ir_region *, obst, 1);
 474         assert(ARR_LEN(head->succ) == 2);
 475
 476         succ = get_region_succ(head, 0);
 477         if (succ != body)
 478                 reg->succ[0] = succ;
 479         else
 480                 reg->succ[0] = get_region_succ(head, 1);
 481
 482         DB((dbg, LEVEL_2, " Created WhileLoop(%u)Body(%u)\n", reg->nr, body->nr));
 483
 484         return reg;
 485 }  /* new_WhileLoop */
 486
 487 /**
 488  * Return true if a is an ancestor of b in DFS search.
 489  */
 490 static int is_ancestor(const ir_region *a, const ir_region *b) {
 491         return (a->prenum <= b->prenum && a->postnum > b->postnum);
 492 }
 493
 494 /**
 495  *  Return true if region succ is a successor of region n.
 496  */
 497 static int succ_of(const ir_region *succ, const ir_region *n) {
 498         int i;
 499         for (i = get_region_n_succs(n) - 1; i >= 0; --i) {
 500                 if (get_region_succ(n, i) == succ)
 501                         return 1;
 502         }
 503         return 0;
 504 }
 505
 506 /**
 507  *  Reverse linked list.
 508  */
 509 static struct ir_region *reverse_list(ir_region *n) {
 510         ir_region *prev = NULL, *next;
 511
 512         for (; n; n = next) {
 513                 next = n->link;
 514                 n->link = prev;
 515                 prev = n;
 516         }
 517         return prev;
 518 }
 519
 520 /**
 521  * Find the cyclic region in the subgraph entered by node.
 522  */
 523 static ir_region *find_cyclic_region(ir_region *node) {
 524         int i;
 525         ir_region *last = node;
 526         int improper = 0;
 527
 528         for (i = get_region_n_preds(node) - 1; i >= 0; --i) {
 529                 ir_region *pred = get_region_pred(node, i);
 530
 531                 /* search backedges */
 532                 if (!pred->link && pred != last && is_ancestor(node, pred)) {
 533                         ir_region *rem = last;
 534                         int j;
 535
 536                         last->link = pred;
 537                         last       = pred;
 538                         for (j = get_region_n_preds(pred) - 1; j >= 0; --j) {
 539                                 ir_region *p = get_region_pred(pred, j);
 540
 541                                 /* Search regions we didn't visited yet and
 542                                    link them into the list. */
 543                                 if (!p->link && p != last) {
 544                                         if (is_ancestor(node, p)) {
 545                                                 last->link = p;
 546                                                 last       = p;
 547                                         } else {
 548                                                 improper = 1;
 549                                         }
 550                                 }
 551                         }
 552                         /* reverse the list. */
 553                         last = rem->link;
 554                         rem->link = reverse_list(rem->link);
 555                 }
 556         }
 557
 558         if (node->link && improper) {
 559                 /* found an improper region */
 560         }
 561         return node;
 562 }
 563
 564 #define LINK(list) ((ir_region *)list->link)
 565
 566 /**
 567  * Detect a cyclic region.
 568  */
 569 static ir_region *cyclic_region_type(struct obstack *obst, ir_region *node) {
 570         ir_region *list;
 571
 572         /* simple cases first */
 573         if (succ_of(node, node)) {
 574                 return new_SelfLoop(obst, node);
 575         }
 576         if (get_region_n_succs(node) == 1) {
 577                 ir_region *succ = get_region_succ(node, 0);
 578                 if (get_region_n_preds(succ) == 1 && succ_of(node, succ)) {
 579                         return new_RepeatLoop(obst, node, succ);
 580                 }
 581         }
 582         list = find_cyclic_region(node);
 583
 584         if (list->link && !LINK(list)->link && get_region_n_succs(list->link) == 1) {
 585                 return new_WhileLoop(obst, list);
 586         }
 587
 588         return NULL;
 589 }
 590
 591 /**
 592  * Detect an acyclic region.
 593  */
 594 static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node) {
 595         ir_region *n, *m;
 596         int p, s, i, k;
 597         ir_region **nset = NEW_ARR_F(ir_region *, 0);
 598         pset *set;
 599         ir_region *res;
 600
 601         /* check for a block containing node */
 602         n = node;
 603         p = get_region_n_preds(n) == 1;
 604         s = 1;
 605         while (p & s) {
 606                 n = get_region_pred(n, 0);
 607                 p = get_region_n_preds(n) == 1;
 608                 s = get_region_n_succs(n) == 1;
 609         }
 610         p = 1;
 611         s = get_region_n_succs(n) == 1;
 612         while (p & s) {
 613                 ARR_APP1(ir_region *, nset, n);
 614                 n = get_region_succ(n, 0);
 615                 p = get_region_n_preds(n) == 1;
 616                 s = get_region_n_succs(n) == 1;
 617         }
 618         if (p) {
 619                 ARR_APP1(ir_region *, nset, n);
 620         }
 621         if (ARR_LEN(nset) >= 2) {
 622                 /* node --> .. --> .. */
 623                 res = new_Sequence(obst, nset);
 624                 DEL_ARR_F(nset);
 625                 return res;
 626         }
 627         DEL_ARR_F(nset);
 628         node = n;
 629
 630         /* check for IfThenElse */
 631         k = get_region_n_succs(node);
 632         if (k == 2) {
 633                 int n_succs, m_succs, n_preds, m_preds;
 634
 635                 n = get_region_succ(node, 0);
 636                 m = get_region_succ(node, 1);
 637
 638                 n_succs = get_region_n_succs(n);
 639                 m_succs = get_region_n_succs(m);
 640                 n_preds = get_region_n_preds(n);
 641                 m_preds = get_region_n_preds(m);
 642                 if (n_succs == 1 && n_succs == m_succs && n_preds == m_preds &&
 643                     get_region_succ(n, 0) == get_region_succ(m, 0)) {
 644                         /*
 645                          *    /-->n---\
 646                          * node      ...
 647                          *    \-->m---/
 648                          */
 649                         return new_IfThenElse(obst, node, n, m);
 650                 }
 651                 if (n_succs == 1 && m_preds == 2 &&
 652                     get_region_succ(n, 0) == m &&
 653                     (get_region_pred(m, 0) == node ||
 654                      get_region_pred(m, 1) == node)) {
 655                         /*
 656                          * node -->n-->m
 657                          *    \-------/
 658                          */
 659                         return new_IfThen(obst, node, n);
 660                 }
 661                 if (m_succs == 1 && n_preds == 2 &&
 662                     get_region_succ(m, 0) == m &&
 663                     (get_region_pred(n, 0) == node ||
 664                      get_region_pred(n, 1) == node)) {
 665                         /*
 666                          * node -->m-->n
 667                          *    \-------/
 668                          */
 669                         return new_IfThen(obst, node, m);
 670                 }
 671         }
 672         /* check for Switch, case */
 673         set = pset_new_ptr_default();
 674         p   = k > 0;
 675         for (i = k - 1; i >= 0; --i) {
 676                 n = get_region_succ(node, i);
 677                 pset_insert_ptr(set, n);
 678                 if (get_region_n_succs(n) != 1) {
 679                         p = 0;
 680                         break;
 681                 }
 682         }
 683         if (p) {
 684                 ir_region_kind kind = ir_rk_Case;
 685
 686                 m = pset_first(set);
 687                 if (pset_find_ptr(set, m) != NULL) {
 688                         /* must be a switch, if any, find the exit */
 689                         kind = ir_rk_Switch;
 690
 691                         for (m = pset_next(set); m != NULL; m = pset_next(set)) {
 692                                 if (pset_find_ptr(set, m) == NULL) {
 693                                         pset_break(set);
 694                                         break;
 695                                 }
 696                         }
 697                 }
 698                 if (m != NULL) {
 699                         /* m ist the exit, do the checks */
 700                         foreach_pset(set, n) {
 701                                 if (n == m) {
 702                                         /* good, switch to exit */
 703                                         continue;
 704                                 }
 705                                 if (pset_find_ptr(set, n) == NULL) {
 706                                         /* another exit */
 707                                         pset_break(set);
 708                                         break;
 709                                 }
 710                                 kind = ir_rk_Switch;
 711                         }
 712
 713                         if (n == NULL) {
 714                                 /* detected */
 715                                 return new_SwitchCase(obst, kind, node, m, set);
 716                         }
 717                 }
 718         }
 719         /* check for proper */
 720
 721         return NULL;
 722 }
 723
 724 /**
 725  * Fill the given set recursively with all parts of the region (including itself)
 726  */
 727 static void fill_parts(pset *set, ir_region *reg) {
 728         int i;
 729
 730         if (reg->type == ir_rk_Block) {
 731                 pset_insert_ptr(set, reg);
 732                 return;
 733         }
 734
 735         for (i = ARR_LEN(reg->parts) - 1; i >= 0; --i) {
 736                 fill_parts(set, reg->parts[i].region);
 737         }
 738 }
 739
 740 /**
 741  * replace all pred edges from region pred that points to any of the set set
 742  * to ONE edge to reg.
 743  */
 744 static void replace_pred(ir_region *succ, ir_region *reg) {
 745         int i, len = get_region_n_preds(succ);
 746         int have_one = 0;
 747
 748         for (i = 0; i < len; ++i) {
 749                 ir_region *pred = get_region_pred(succ, i);
 750
 751                 if (pred->parent == reg) {
 752                         ir_region *r;
 753
 754                         if (have_one) {
 755                                 /* kill it */
 756                                 r = get_region_pred(succ, --len);
 757                         } else {
 758                                 /* replace it */
 759                                 have_one = 1;
 760                                 r = reg;
 761                         }
 762                         set_region_pred(succ, i, r);
 763                 }
 764         }
 765         ARR_SHRINKLEN(succ->pred, len);
 766 }
 767
 768 /**
 769  * replace all succ edges from region pred that points to any of the set set
 770  * to ONE edge to reg.
 771  */
 772 static void replace_succ(ir_region *pred, ir_region *reg) {
 773         int i, len = get_region_n_succs(pred);
 774         int have_one = 0;
 775
 776         for (i = 0; i < len; ++i) {
 777                 ir_region *succ = get_region_succ(pred, i);
 778
 779                 if (succ->parent == reg) {
 780                         ir_region *r;
 781
 782                         if (have_one) {
 783                                 /* kill it */
 784                                 r = get_region_succ(pred, --len);
 785                         } else {
 786                                 /* replace it */
 787                                 have_one = 1;
 788                                 r = reg;
 789                         }
 790                         set_region_succ(pred, i, r);
 791                 }
 792         }
 793         ARR_SHRINKLEN(pred->succ, len);
 794 }
 795
 796 /**
 797  * Reduce the graph by the node reg.
 798  */
 799 static void reduce(walk_env *env, ir_region *reg) {
 800         int i;
 801         ir_region *head = reg->parts[0].region;
 802         unsigned maxorder = head->postnum;
 803         unsigned minorder = head->prenum;
 804
 805         /* second step: replace all preds in successors */
 806         for (i = get_region_n_succs(reg) - 1; i >= 0; --i) {
 807                 ir_region *succ = get_region_succ(reg, i);
 808
 809                 replace_pred(succ, reg);
 810         }
 811
 812         /* second third: replace all succs in predessors */
 813         for (i = get_region_n_preds(reg) - 1; i >= 0; --i) {
 814                 ir_region *pred = get_region_pred(reg, i);
 815
 816                 replace_succ(pred, reg);
 817         }
 818
 819         reg->prenum  = minorder;
 820         reg->postnum = maxorder;
 821         env->post[maxorder] = reg;
 822 }
 823
 824 /**
 825  * Construct the region tree of a graph by doing
 826  * structural analysis.
 827  *
 828  * Uses link fields of nodes.
 829  *
 830  * @param irg  the graph
 831  */
 832 ir_reg_tree *construct_region_tree(ir_graph *irg) {
 833         walk_env env;
 834         ir_graph *rem = current_ir_graph;
 835         ir_reg_tree *res = xmalloc(sizeof(*res));
 836
 837         obstack_init(&res->obst);
 838
 839         current_ir_graph = irg;
 840
 841         FIRM_DBG_REGISTER(dbg, "firm.ana.structure");
 842         firm_dbg_set_mask(dbg, SET_LEVEL_5);
 843
 844         DB((dbg, LEVEL_1, "Structural analysis on %+F starts...\n", irg));
 845
 846         dump_ir_block_graph(irg, "-structure_start");
 847
 848         /* we need dominance info */
 849         assure_doms(irg);
 850         /* and out edges */
 851         assure_irg_outs(irg);
 852
 853         env.start_block = get_irg_start_block(irg);
 854         env.end_block   = get_irg_end_block(irg);
 855
 856         /* create the Block wrapper and count them */
 857         env.l_post = 0;
 858         env.obst   = &res->obst;
 859         irg_block_walk_graph(irg, NULL, wrap_blocks, &env);
 860         irg_block_walk_graph(irg, NULL, update_Block_regions, &env);
 861
 862         env.post = NEW_ARR_F(ir_region *, env.l_post);
 863
 864         /* do the DFS walk */
 865         dfs_walk(irg, &env);
 866
 867         DB((dbg, LEVEL_1, "%d regions left\n", env.postmax));
 868         if (env.postmax > 1) {
 869                 unsigned postctr = 0;
 870                 do {
 871                         ir_region *reg, *n = env.post[postctr];
 872                         do {
 873                                 if (n->parent) {
 874                                         /* already folded */
 875                                         break;
 876                                 }
 877                                 /* locate an acyclic region if present */
 878                                 reg = acyclic_region_type(env.obst, n);
 879                                 if (reg == NULL) {
 880                                         /* locate a cyclic region */
 881                                         reg = cyclic_region_type(env.obst, n);
 882                                 }
 883                                 if (reg != NULL) {
 884                                         /* found a new region */
 885                                         reduce(&env, reg);
 886                                         n = reg;
 887                                 }
 888                         } while (reg != NULL);
 889                         ++postctr;
 890                 } while (postctr < env.postmax);
 891         }
 892         DB((dbg, LEVEL_1, "Structural analysis finished.\n"));
 893
 894         DEL_ARR_F(env.post);
 895         current_ir_graph = rem;
 896
 897         res->top = env.post[0];
 898         res->irg = irg;
 899         return res;
 900 }
 901
 902 /**
 903  * Walk over the region tree.
 904  *
 905  * @param reg   a region node
 906  * @param pre   walker function, executed before the children of a tree node are visited
 907  * @param post  walker function, executed after the children of a tree node are visited
 908  * @param env   environment, passed to pre and post
 909  */
 910 static void region_tree_walk2(ir_region *reg, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env) {
 911         int i, n;
 912
 913         if (pre)
 914                 pre(reg, env);
 915         if (reg->type != ir_rk_Block) {
 916                 for (i = 0, n = ARR_LEN(reg->parts); i < n; ++i)
 917                         region_tree_walk2(reg->parts[i].region, pre, post, env);
 918         }
 919         if (post)
 920                 post(reg, env);
 921 }
 922
 923 /**
 924  * Walk over the region tree.
 925  *
 926  * @param tree  the tree
 927  * @param pre   walker function, executed before the children of a tree node are visited
 928  * @param post  walker function, executed after the children of a tree node are visited
 929  * @param env   environment, passed to pre and post
 930  */
 931 void region_tree_walk(ir_reg_tree *tree, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env) {
 932         region_tree_walk2(tree->top, pre, post, env);
 933 }