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

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