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

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