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

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