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

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