gcc/sese.c

   1 /* Single entry single exit control flow regions.
   2    Copyright (C) 2008, 2009, 2010
   3    Free Software Foundation, Inc.
   4    Contributed by Jan Sjodin <jan.sjodin@amd.com> and
   5    Sebastian Pop <sebastian.pop@amd.com>.
   6
   7 This file is part of GCC.
   8
   9 GCC is free software; you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation; either version 3, or (at your option)
  12 any later version.
  13
  14 GCC is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GCC; see the file COPYING3.  If not see
  21 <http://www.gnu.org/licenses/>.  */
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "ggc.h"
  28 #include "tree.h"
  29 #include "rtl.h"
  30 #include "basic-block.h"
  31 #include "diagnostic.h"
  32 #include "tree-pretty-print.h"
  33 #include "tree-flow.h"
  34 #include "toplev.h"
  35 #include "tree-dump.h"
  36 #include "timevar.h"
  37 #include "cfgloop.h"
  38 #include "tree-chrec.h"
  39 #include "tree-data-ref.h"
  40 #include "tree-scalar-evolution.h"
  41 #include "tree-pass.h"
  42 #include "domwalk.h"
  43 #include "value-prof.h"
  44 #include "pointer-set.h"
  45 #include "gimple.h"
  46 #include "sese.h"
  47
  48 /* Print to stderr the element ELT.  */
  49
  50 static void
  51 debug_rename_elt (rename_map_elt elt)
  52 {
  53   fprintf (stderr, "(");
  54   print_generic_expr (stderr, elt->old_name, 0);
  55   fprintf (stderr, ", ");
  56   print_generic_expr (stderr, elt->expr, 0);
  57   fprintf (stderr, ")\n");
  58 }
  59
  60 /* Helper function for debug_rename_map.  */
  61
  62 static int
  63 debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
  64 {
  65   struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot;
  66   debug_rename_elt (entry);
  67   return 1;
  68 }
  69
  70 /* Print to stderr all the elements of RENAME_MAP.  */
  71
  72 DEBUG_FUNCTION void
  73 debug_rename_map (htab_t rename_map)
  74 {
  75   htab_traverse (rename_map, debug_rename_map_1, NULL);
  76 }
  77
  78 /* Computes a hash function for database element ELT.  */
  79
  80 hashval_t
  81 rename_map_elt_info (const void *elt)
  82 {
  83   return SSA_NAME_VERSION (((const struct rename_map_elt_s *) elt)->old_name);
  84 }
  85
  86 /* Compares database elements E1 and E2.  */
  87
  88 int
  89 eq_rename_map_elts (const void *e1, const void *e2)
  90 {
  91   const struct rename_map_elt_s *elt1 = (const struct rename_map_elt_s *) e1;
  92   const struct rename_map_elt_s *elt2 = (const struct rename_map_elt_s *) e2;
  93
  94   return (elt1->old_name == elt2->old_name);
  95 }
  96
  97 \f
  98
  99 /* Print to stderr the element ELT.  */
 100
 101 static void
 102 debug_ivtype_elt (ivtype_map_elt elt)
 103 {
 104   fprintf (stderr, "(%s, ", elt->cloog_iv);
 105   print_generic_expr (stderr, elt->type, 0);
 106   fprintf (stderr, ")\n");
 107 }
 108
 109 /* Helper function for debug_ivtype_map.  */
 110
 111 static int
 112 debug_ivtype_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
 113 {
 114   struct ivtype_map_elt_s *entry = (struct ivtype_map_elt_s *) *slot;
 115   debug_ivtype_elt (entry);
 116   return 1;
 117 }
 118
 119 /* Print to stderr all the elements of MAP.  */
 120
 121 DEBUG_FUNCTION void
 122 debug_ivtype_map (htab_t map)
 123 {
 124   htab_traverse (map, debug_ivtype_map_1, NULL);
 125 }
 126
 127 /* Computes a hash function for database element ELT.  */
 128
 129 hashval_t
 130 ivtype_map_elt_info (const void *elt)
 131 {
 132   return htab_hash_pointer (((const struct ivtype_map_elt_s *) elt)->cloog_iv);
 133 }
 134
 135 /* Compares database elements E1 and E2.  */
 136
 137 int
 138 eq_ivtype_map_elts (const void *e1, const void *e2)
 139 {
 140   const struct ivtype_map_elt_s *elt1 = (const struct ivtype_map_elt_s *) e1;
 141   const struct ivtype_map_elt_s *elt2 = (const struct ivtype_map_elt_s *) e2;
 142
 143   return (elt1->cloog_iv == elt2->cloog_iv);
 144 }
 145
 146 \f
 147
 148 /* Record LOOP as occuring in REGION.  */
 149
 150 static void
 151 sese_record_loop (sese region, loop_p loop)
 152 {
 153   if (sese_contains_loop (region, loop))
 154     return;
 155
 156   bitmap_set_bit (SESE_LOOPS (region), loop->num);
 157   VEC_safe_push (loop_p, heap, SESE_LOOP_NEST (region), loop);
 158 }
 159
 160 /* Build the loop nests contained in REGION.  Returns true when the
 161    operation was successful.  */
 162
 163 void
 164 build_sese_loop_nests (sese region)
 165 {
 166   unsigned i;
 167   basic_block bb;
 168   struct loop *loop0, *loop1;
 169
 170   FOR_EACH_BB (bb)
 171     if (bb_in_sese_p (bb, region))
 172       {
 173         struct loop *loop = bb->loop_father;
 174
 175         /* Only add loops if they are completely contained in the SCoP.  */
 176         if (loop->header == bb
 177             && bb_in_sese_p (loop->latch, region))
 178           sese_record_loop (region, loop);
 179       }
 180
 181   /* Make sure that the loops in the SESE_LOOP_NEST are ordered.  It
 182      can be the case that an inner loop is inserted before an outer
 183      loop.  To avoid this, semi-sort once.  */
 184   FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop0)
 185     {
 186       if (VEC_length (loop_p, SESE_LOOP_NEST (region)) == i + 1)
 187         break;
 188
 189       loop1 = VEC_index (loop_p, SESE_LOOP_NEST (region), i + 1);
 190       if (loop0->num > loop1->num)
 191         {
 192           VEC_replace (loop_p, SESE_LOOP_NEST (region), i, loop1);
 193           VEC_replace (loop_p, SESE_LOOP_NEST (region), i + 1, loop0);
 194         }
 195     }
 196 }
 197
 198 /* For a USE in BB, if BB is outside REGION, mark the USE in the
 199    LIVEOUTS set.  */
 200
 201 static void
 202 sese_build_liveouts_use (sese region, bitmap liveouts, basic_block bb,
 203                          tree use)
 204 {
 205   unsigned ver;
 206   basic_block def_bb;
 207
 208   if (TREE_CODE (use) != SSA_NAME)
 209     return;
 210
 211   ver = SSA_NAME_VERSION (use);
 212   def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
 213
 214   if (!def_bb
 215       || !bb_in_sese_p (def_bb, region)
 216       || bb_in_sese_p (bb, region))
 217     return;
 218
 219   bitmap_set_bit (liveouts, ver);
 220 }
 221
 222 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
 223    used in BB that is outside of the REGION.  */
 224
 225 static void
 226 sese_build_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
 227 {
 228   gimple_stmt_iterator bsi;
 229   edge e;
 230   edge_iterator ei;
 231   ssa_op_iter iter;
 232   use_operand_p use_p;
 233
 234   FOR_EACH_EDGE (e, ei, bb->succs)
 235     for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
 236       sese_build_liveouts_use (region, liveouts, bb,
 237                                PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e));
 238
 239   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 240     {
 241       gimple stmt = gsi_stmt (bsi);
 242
 243       if (is_gimple_debug (stmt))
 244         continue;
 245
 246       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 247         sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
 248     }
 249 }
 250
 251 /* For a USE in BB, return true if BB is outside REGION and it's not
 252    in the LIVEOUTS set.  */
 253
 254 static bool
 255 sese_bad_liveouts_use (sese region, bitmap liveouts, basic_block bb,
 256                        tree use)
 257 {
 258   unsigned ver;
 259   basic_block def_bb;
 260
 261   if (TREE_CODE (use) != SSA_NAME)
 262     return false;
 263
 264   ver = SSA_NAME_VERSION (use);
 265
 266   /* If it's in liveouts, the variable will get a new PHI node, and
 267      the debug use will be properly adjusted.  */
 268   if (bitmap_bit_p (liveouts, ver))
 269     return false;
 270
 271   def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
 272
 273   if (!def_bb
 274       || !bb_in_sese_p (def_bb, region)
 275       || bb_in_sese_p (bb, region))
 276     return false;
 277
 278   return true;
 279 }
 280
 281 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
 282    are not marked as liveouts.  */
 283
 284 static void
 285 sese_reset_debug_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
 286 {
 287   gimple_stmt_iterator bsi;
 288   ssa_op_iter iter;
 289   use_operand_p use_p;
 290
 291   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 292     {
 293       gimple stmt = gsi_stmt (bsi);
 294
 295       if (!is_gimple_debug (stmt))
 296         continue;
 297
 298       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 299         if (sese_bad_liveouts_use (region, liveouts, bb,
 300                                    USE_FROM_PTR (use_p)))
 301           {
 302             gimple_debug_bind_reset_value (stmt);
 303             update_stmt (stmt);
 304             break;
 305           }
 306     }
 307 }
 308
 309 /* Build the LIVEOUTS of REGION: the set of variables defined inside
 310    and used outside the REGION.  */
 311
 312 static void
 313 sese_build_liveouts (sese region, bitmap liveouts)
 314 {
 315   basic_block bb;
 316
 317   FOR_EACH_BB (bb)
 318     sese_build_liveouts_bb (region, liveouts, bb);
 319   if (MAY_HAVE_DEBUG_INSNS)
 320     FOR_EACH_BB (bb)
 321       sese_reset_debug_liveouts_bb (region, liveouts, bb);
 322 }
 323
 324 /* Builds a new SESE region from edges ENTRY and EXIT.  */
 325
 326 sese
 327 new_sese (edge entry, edge exit)
 328 {
 329   sese region = XNEW (struct sese_s);
 330
 331   SESE_ENTRY (region) = entry;
 332   SESE_EXIT (region) = exit;
 333   SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
 334   SESE_LOOP_NEST (region) = VEC_alloc (loop_p, heap, 3);
 335   SESE_ADD_PARAMS (region) = true;
 336   SESE_PARAMS (region) = VEC_alloc (tree, heap, 3);
 337
 338   return region;
 339 }
 340
 341 /* Deletes REGION.  */
 342
 343 void
 344 free_sese (sese region)
 345 {
 346   if (SESE_LOOPS (region))
 347     SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
 348
 349   VEC_free (tree, heap, SESE_PARAMS (region));
 350   VEC_free (loop_p, heap, SESE_LOOP_NEST (region));
 351
 352   XDELETE (region);
 353 }
 354
 355 /* Add exit phis for USE on EXIT.  */
 356
 357 static void
 358 sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
 359 {
 360   gimple phi = create_phi_node (use, exit);
 361
 362   create_new_def_for (gimple_phi_result (phi), phi,
 363                       gimple_phi_result_ptr (phi));
 364   add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION);
 365   add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
 366 }
 367
 368 /* Insert in the block BB phi nodes for variables defined in REGION
 369    and used outside the REGION.  The code generation moves REGION in
 370    the else clause of an "if (1)" and generates code in the then
 371    clause that is at this point empty:
 372
 373    | if (1)
 374    |   empty;
 375    | else
 376    |   REGION;
 377 */
 378
 379 void
 380 sese_insert_phis_for_liveouts (sese region, basic_block bb,
 381                                edge false_e, edge true_e)
 382 {
 383   unsigned i;
 384   bitmap_iterator bi;
 385   bitmap liveouts = BITMAP_ALLOC (NULL);
 386
 387   update_ssa (TODO_update_ssa);
 388
 389   sese_build_liveouts (region, liveouts);
 390   EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi)
 391     sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
 392   BITMAP_FREE (liveouts);
 393
 394   update_ssa (TODO_update_ssa);
 395 }
 396
 397 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set.  */
 398
 399 edge
 400 get_true_edge_from_guard_bb (basic_block bb)
 401 {
 402   edge e;
 403   edge_iterator ei;
 404
 405   FOR_EACH_EDGE (e, ei, bb->succs)
 406     if (e->flags & EDGE_TRUE_VALUE)
 407       return e;
 408
 409   gcc_unreachable ();
 410   return NULL;
 411 }
 412
 413 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared.  */
 414
 415 edge
 416 get_false_edge_from_guard_bb (basic_block bb)
 417 {
 418   edge e;
 419   edge_iterator ei;
 420
 421   FOR_EACH_EDGE (e, ei, bb->succs)
 422     if (!(e->flags & EDGE_TRUE_VALUE))
 423       return e;
 424
 425   gcc_unreachable ();
 426   return NULL;
 427 }
 428
 429 /* Returns the expression associated to OLD_NAME in RENAME_MAP.  */
 430
 431 static tree
 432 get_rename (htab_t rename_map, tree old_name)
 433 {
 434   struct rename_map_elt_s tmp;
 435   PTR *slot;
 436
 437   gcc_assert (TREE_CODE (old_name) == SSA_NAME);
 438   tmp.old_name = old_name;
 439   slot = htab_find_slot (rename_map, &tmp, NO_INSERT);
 440
 441   if (slot && *slot)
 442     return ((rename_map_elt) *slot)->expr;
 443
 444   return NULL_TREE;
 445 }
 446
 447 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).  */
 448
 449 static void
 450 set_rename (htab_t rename_map, tree old_name, tree expr)
 451 {
 452   struct rename_map_elt_s tmp;
 453   PTR *slot;
 454
 455   if (old_name == expr)
 456     return;
 457
 458   tmp.old_name = old_name;
 459   slot = htab_find_slot (rename_map, &tmp, INSERT);
 460
 461   if (!slot)
 462     return;
 463
 464   if (*slot)
 465     free (*slot);
 466
 467   *slot = new_rename_map_elt (old_name, expr);
 468 }
 469
 470 /* Renames the scalar uses of the statement COPY, using the
 471    substitution map RENAME_MAP, inserting the gimplification code at
 472    GSI_TGT, for the translation REGION, with the original copied
 473    statement in LOOP, and using the induction variable renaming map
 474    IV_MAP.  */
 475
 476 static void
 477 rename_uses (gimple copy, htab_t rename_map, gimple_stmt_iterator *gsi_tgt,
 478              sese region, loop_p loop, VEC (tree, heap) *iv_map)
 479 {
 480   use_operand_p use_p;
 481   ssa_op_iter op_iter;
 482
 483   if (is_gimple_debug (copy))
 484     {
 485       if (gimple_debug_bind_p (copy))
 486         gimple_debug_bind_reset_value (copy);
 487       else
 488         gcc_unreachable ();
 489
 490       return;
 491     }
 492
 493   FOR_EACH_SSA_USE_OPERAND (use_p, copy, op_iter, SSA_OP_ALL_USES)
 494     {
 495       tree old_name = USE_FROM_PTR (use_p);
 496       tree new_expr, scev;
 497       gimple_seq stmts;
 498
 499       if (TREE_CODE (old_name) != SSA_NAME
 500           || !is_gimple_reg (old_name)
 501           || SSA_NAME_IS_DEFAULT_DEF (old_name))
 502         continue;
 503
 504       new_expr = get_rename (rename_map, old_name);
 505       if (new_expr)
 506         {
 507           tree type_old_name = TREE_TYPE (old_name);
 508           tree type_new_expr = TREE_TYPE (new_expr);
 509
 510           if (type_old_name != type_new_expr
 511               || (TREE_CODE (new_expr) != SSA_NAME
 512                   && is_gimple_reg (old_name)))
 513             {
 514               tree var = create_tmp_var (type_old_name, "var");
 515
 516               if (type_old_name != type_new_expr)
 517                 new_expr = fold_convert (type_old_name, new_expr);
 518
 519               new_expr = build2 (MODIFY_EXPR, type_old_name, var, new_expr);
 520               new_expr = force_gimple_operand (new_expr, &stmts, true, NULL);
 521               gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT);
 522             }
 523
 524           replace_exp (use_p, new_expr);
 525           continue;
 526         }
 527
 528       scev = scalar_evolution_in_region (region, loop, old_name);
 529
 530       /* At this point we should know the exact scev for each
 531          scalar SSA_NAME used in the scop: all the other scalar
 532          SSA_NAMEs should have been translated out of SSA using
 533          arrays with one element.  */
 534       gcc_assert (!chrec_contains_undetermined (scev));
 535
 536       new_expr = chrec_apply_map (scev, iv_map);
 537
 538       /* The apply should produce an expression tree containing
 539          the uses of the new induction variables.  We should be
 540          able to use new_expr instead of the old_name in the newly
 541          generated loop nest.  */
 542       gcc_assert (!chrec_contains_undetermined (new_expr)
 543                   && !tree_contains_chrecs (new_expr, NULL));
 544
 545       /* Replace the old_name with the new_expr.  */
 546       new_expr = force_gimple_operand (unshare_expr (new_expr), &stmts,
 547                                        true, NULL_TREE);
 548       gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT);
 549       replace_exp (use_p, new_expr);
 550       set_rename (rename_map, old_name, new_expr);
 551     }
 552 }
 553
 554 /* Duplicates the statements of basic block BB into basic block NEW_BB
 555    and compute the new induction variables according to the IV_MAP.  */
 556
 557 static void
 558 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb,
 559                                 htab_t rename_map,
 560                                 VEC (tree, heap) *iv_map, sese region)
 561 {
 562   gimple_stmt_iterator gsi, gsi_tgt;
 563   loop_p loop = bb->loop_father;
 564
 565   gsi_tgt = gsi_start_bb (new_bb);
 566   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 567     {
 568       def_operand_p def_p;
 569       ssa_op_iter op_iter;
 570       gimple stmt = gsi_stmt (gsi);
 571       gimple copy;
 572       tree lhs;
 573
 574       /* Do not copy labels or conditions.  */
 575       if (gimple_code (stmt) == GIMPLE_LABEL
 576           || gimple_code (stmt) == GIMPLE_COND)
 577         continue;
 578
 579       /* Do not copy induction variables.  */
 580       if (is_gimple_assign (stmt)
 581           && (lhs = gimple_assign_lhs (stmt))
 582           && TREE_CODE (lhs) == SSA_NAME
 583           && is_gimple_reg (lhs)
 584           && scev_analyzable_p (lhs, region))
 585         continue;
 586
 587       /* Create a new copy of STMT and duplicate STMT's virtual
 588          operands.  */
 589       copy = gimple_copy (stmt);
 590       gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
 591       mark_sym_for_renaming (gimple_vop (cfun));
 592
 593       maybe_duplicate_eh_stmt (copy, stmt);
 594       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
 595
 596       /* Create new names for all the definitions created by COPY and
 597          add replacement mappings for each new name.  */
 598       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
 599         {
 600           tree old_name = DEF_FROM_PTR (def_p);
 601           tree new_name = create_new_def_for (old_name, copy, def_p);
 602           set_rename (rename_map, old_name, new_name);
 603         }
 604
 605       rename_uses (copy, rename_map, &gsi_tgt, region, loop, iv_map);
 606
 607       update_stmt (copy);
 608     }
 609 }
 610
 611 /* Copies BB and includes in the copied BB all the statements that can
 612    be reached following the use-def chains from the memory accesses,
 613    and returns the next edge following this new block.  */
 614
 615 edge
 616 copy_bb_and_scalar_dependences (basic_block bb, sese region,
 617                                 edge next_e, VEC (tree, heap) *iv_map)
 618 {
 619   basic_block new_bb = split_edge (next_e);
 620   htab_t rename_map = htab_create (10, rename_map_elt_info,
 621                                    eq_rename_map_elts, free);
 622
 623   next_e = single_succ_edge (new_bb);
 624   graphite_copy_stmts_from_block (bb, new_bb, rename_map, iv_map, region);
 625   remove_phi_nodes (new_bb);
 626   htab_delete (rename_map);
 627
 628   return next_e;
 629 }
 630
 631 /* Returns the outermost loop in SCOP that contains BB.  */
 632
 633 struct loop *
 634 outermost_loop_in_sese (sese region, basic_block bb)
 635 {
 636   struct loop *nest;
 637
 638   nest = bb->loop_father;
 639   while (loop_outer (nest)
 640          && loop_in_sese_p (loop_outer (nest), region))
 641     nest = loop_outer (nest);
 642
 643   return nest;
 644 }
 645
 646 /* Sets the false region of an IF_REGION to REGION.  */
 647
 648 void
 649 if_region_set_false_region (ifsese if_region, sese region)
 650 {
 651   basic_block condition = if_region_get_condition_block (if_region);
 652   edge false_edge = get_false_edge_from_guard_bb (condition);
 653   basic_block dummy = false_edge->dest;
 654   edge entry_region = SESE_ENTRY (region);
 655   edge exit_region = SESE_EXIT (region);
 656   basic_block before_region = entry_region->src;
 657   basic_block last_in_region = exit_region->src;
 658   void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
 659                                           htab_hash_pointer (exit_region),
 660                                           NO_INSERT);
 661
 662   entry_region->flags = false_edge->flags;
 663   false_edge->flags = exit_region->flags;
 664
 665   redirect_edge_pred (entry_region, condition);
 666   redirect_edge_pred (exit_region, before_region);
 667   redirect_edge_pred (false_edge, last_in_region);
 668   redirect_edge_succ (false_edge, single_succ (dummy));
 669   delete_basic_block (dummy);
 670
 671   exit_region->flags = EDGE_FALLTHRU;
 672   recompute_all_dominators ();
 673
 674   SESE_EXIT (region) = false_edge;
 675
 676   if (if_region->false_region)
 677     free (if_region->false_region);
 678   if_region->false_region = region;
 679
 680   if (slot)
 681     {
 682       struct loop_exit *loop_exit = ggc_alloc_cleared_loop_exit ();
 683
 684       memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
 685       htab_clear_slot (current_loops->exits, slot);
 686
 687       slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
 688                                        htab_hash_pointer (false_edge),
 689                                        INSERT);
 690       loop_exit->e = false_edge;
 691       *slot = loop_exit;
 692       false_edge->src->loop_father->exits->next = loop_exit;
 693     }
 694 }
 695
 696 /* Creates an IFSESE with CONDITION on edge ENTRY.  */
 697
 698 static ifsese
 699 create_if_region_on_edge (edge entry, tree condition)
 700 {
 701   edge e;
 702   edge_iterator ei;
 703   sese sese_region = XNEW (struct sese_s);
 704   sese true_region = XNEW (struct sese_s);
 705   sese false_region = XNEW (struct sese_s);
 706   ifsese if_region = XNEW (struct ifsese_s);
 707   edge exit = create_empty_if_region_on_edge (entry, condition);
 708
 709   if_region->region = sese_region;
 710   if_region->region->entry = entry;
 711   if_region->region->exit = exit;
 712
 713   FOR_EACH_EDGE (e, ei, entry->dest->succs)
 714     {
 715       if (e->flags & EDGE_TRUE_VALUE)
 716         {
 717           true_region->entry = e;
 718           true_region->exit = single_succ_edge (e->dest);
 719           if_region->true_region = true_region;
 720         }
 721       else if (e->flags & EDGE_FALSE_VALUE)
 722         {
 723           false_region->entry = e;
 724           false_region->exit = single_succ_edge (e->dest);
 725           if_region->false_region = false_region;
 726         }
 727     }
 728
 729   return if_region;
 730 }
 731
 732 /* Moves REGION in a condition expression:
 733    | if (1)
 734    |   ;
 735    | else
 736    |   REGION;
 737 */
 738
 739 ifsese
 740 move_sese_in_condition (sese region)
 741 {
 742   basic_block pred_block = split_edge (SESE_ENTRY (region));
 743   ifsese if_region;
 744
 745   SESE_ENTRY (region) = single_succ_edge (pred_block);
 746   if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
 747   if_region_set_false_region (if_region, region);
 748
 749   return if_region;
 750 }
 751
 752 /* Replaces the condition of the IF_REGION with CONDITION:
 753    | if (CONDITION)
 754    |   true_region;
 755    | else
 756    |   false_region;
 757 */
 758
 759 void
 760 set_ifsese_condition (ifsese if_region, tree condition)
 761 {
 762   sese region = if_region->region;
 763   edge entry = region->entry;
 764   basic_block bb = entry->dest;
 765   gimple last = last_stmt (bb);
 766   gimple_stmt_iterator gsi = gsi_last_bb (bb);
 767   gimple cond_stmt;
 768
 769   gcc_assert (gimple_code (last) == GIMPLE_COND);
 770
 771   gsi_remove (&gsi, true);
 772   gsi = gsi_last_bb (bb);
 773   condition = force_gimple_operand_gsi (&gsi, condition, true, NULL,
 774                                         false, GSI_NEW_STMT);
 775   cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE);
 776   gsi = gsi_last_bb (bb);
 777   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
 778 }
 779
 780 /* Returns the scalar evolution of T in REGION.  Every variable that
 781    is not defined in the REGION is considered a parameter.  */
 782
 783 tree
 784 scalar_evolution_in_region (sese region, loop_p loop, tree t)
 785 {
 786   gimple def;
 787   struct loop *def_loop;
 788   basic_block before = block_before_sese (region);
 789
 790   if (TREE_CODE (t) != SSA_NAME
 791       || loop_in_sese_p (loop, region))
 792     return instantiate_scev (before, loop,
 793                              analyze_scalar_evolution (loop, t));
 794
 795   if (!defined_in_sese_p (t, region))
 796     return t;
 797
 798   def = SSA_NAME_DEF_STMT (t);
 799   def_loop = loop_containing_stmt (def);
 800
 801   if (loop_in_sese_p (def_loop, region))
 802     {
 803       t = analyze_scalar_evolution (def_loop, t);
 804       def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1);
 805       t = compute_overall_effect_of_inner_loop (def_loop, t);
 806       return t;
 807     }
 808   else
 809     return instantiate_scev (before, loop, t);
 810 }