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

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