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

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