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 (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop0); i++)
 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   FOR_EACH_SSA_USE_OPERAND (use_p, copy, op_iter, SSA_OP_ALL_USES)
 484     {
 485       tree old_name = USE_FROM_PTR (use_p);
 486       tree new_expr, scev;
 487       gimple_seq stmts;
 488
 489       if (TREE_CODE (old_name) != SSA_NAME
 490           || !is_gimple_reg (old_name)
 491           || SSA_NAME_IS_DEFAULT_DEF (old_name))
 492         continue;
 493
 494       new_expr = get_rename (rename_map, old_name);
 495       if (new_expr)
 496         {
 497           tree type_old_name = TREE_TYPE (old_name);
 498           tree type_new_expr = TREE_TYPE (new_expr);
 499
 500           if (type_old_name != type_new_expr
 501               || (TREE_CODE (new_expr) != SSA_NAME
 502                   && is_gimple_reg (old_name)))
 503             {
 504               tree var;
 505
 506               if (is_gimple_debug (copy))
 507                 {
 508                   if (gimple_debug_bind_p (copy))
 509                     gimple_debug_bind_reset_value (copy);
 510                   else
 511                     gcc_unreachable ();
 512
 513                   break;
 514                 }
 515
 516               var = create_tmp_var (type_old_name, "var");
 517
 518               if (type_old_name != type_new_expr)
 519                 new_expr = fold_convert (type_old_name, new_expr);
 520
 521               new_expr = build2 (MODIFY_EXPR, type_old_name, var, new_expr);
 522               new_expr = force_gimple_operand (new_expr, &stmts, true, NULL);
 523               gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT);
 524             }
 525
 526           replace_exp (use_p, new_expr);
 527           continue;
 528         }
 529
 530       scev = scalar_evolution_in_region (region, loop, old_name);
 531
 532       /* At this point we should know the exact scev for each
 533          scalar SSA_NAME used in the scop: all the other scalar
 534          SSA_NAMEs should have been translated out of SSA using
 535          arrays with one element.  */
 536       gcc_assert (!chrec_contains_undetermined (scev));
 537
 538       new_expr = chrec_apply_map (scev, iv_map);
 539
 540       /* The apply should produce an expression tree containing
 541          the uses of the new induction variables.  We should be
 542          able to use new_expr instead of the old_name in the newly
 543          generated loop nest.  */
 544       gcc_assert (!chrec_contains_undetermined (new_expr)
 545                   && !tree_contains_chrecs (new_expr, NULL));
 546
 547       /* Replace the old_name with the new_expr.  */
 548       new_expr = force_gimple_operand (new_expr, &stmts, true, NULL);
 549       gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT);
 550       replace_exp (use_p, new_expr);
 551       set_rename (rename_map, old_name, new_expr);
 552     }
 553 }
 554
 555 /* Duplicates the statements of basic block BB into basic block NEW_BB
 556    and compute the new induction variables according to the IV_MAP.  */
 557
 558 static void
 559 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb,
 560                                 htab_t rename_map,
 561                                 VEC (tree, heap) *iv_map, sese region)
 562 {
 563   gimple_stmt_iterator gsi, gsi_tgt;
 564   loop_p loop = bb->loop_father;
 565
 566   gsi_tgt = gsi_start_bb (new_bb);
 567   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 568     {
 569       def_operand_p def_p;
 570       ssa_op_iter op_iter;
 571       gimple stmt = gsi_stmt (gsi);
 572       gimple copy;
 573       tree lhs;
 574
 575       /* Do not copy labels or conditions.  */
 576       if (gimple_code (stmt) == GIMPLE_LABEL
 577           || gimple_code (stmt) == GIMPLE_COND)
 578         continue;
 579
 580       /* Do not copy induction variables.  */
 581       if (is_gimple_assign (stmt)
 582           && (lhs = gimple_assign_lhs (stmt))
 583           && TREE_CODE (lhs) == SSA_NAME
 584           && is_gimple_reg (lhs)
 585           && scev_analyzable_p (lhs, region))
 586         continue;
 587
 588       /* Create a new copy of STMT and duplicate STMT's virtual
 589          operands.  */
 590       copy = gimple_copy (stmt);
 591       gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
 592       mark_sym_for_renaming (gimple_vop (cfun));
 593
 594       maybe_duplicate_eh_stmt (copy, stmt);
 595       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
 596
 597       /* Create new names for all the definitions created by COPY and
 598          add replacement mappings for each new name.  */
 599       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
 600         {
 601           tree old_name = DEF_FROM_PTR (def_p);
 602           tree new_name = create_new_def_for (old_name, copy, def_p);
 603           set_rename (rename_map, old_name, new_name);
 604         }
 605
 606       rename_uses (copy, rename_map, &gsi_tgt, region, loop, iv_map);
 607
 608       update_stmt (copy);
 609     }
 610 }
 611
 612 /* Copies BB and includes in the copied BB all the statements that can
 613    be reached following the use-def chains from the memory accesses,
 614    and returns the next edge following this new block.  */
 615
 616 edge
 617 copy_bb_and_scalar_dependences (basic_block bb, sese region,
 618                                 edge next_e, VEC (tree, heap) *iv_map)
 619 {
 620   basic_block new_bb = split_edge (next_e);
 621   htab_t rename_map = htab_create (10, rename_map_elt_info,
 622                                    eq_rename_map_elts, free);
 623
 624   next_e = single_succ_edge (new_bb);
 625   graphite_copy_stmts_from_block (bb, new_bb, rename_map, iv_map, region);
 626   remove_phi_nodes (new_bb);
 627   htab_delete (rename_map);
 628
 629   return next_e;
 630 }
 631
 632 /* Returns the outermost loop in SCOP that contains BB.  */
 633
 634 struct loop *
 635 outermost_loop_in_sese (sese region, basic_block bb)
 636 {
 637   struct loop *nest;
 638
 639   nest = bb->loop_father;
 640   while (loop_outer (nest)
 641          && loop_in_sese_p (loop_outer (nest), region))
 642     nest = loop_outer (nest);
 643
 644   return nest;
 645 }
 646
 647 /* Sets the false region of an IF_REGION to REGION.  */
 648
 649 void
 650 if_region_set_false_region (ifsese if_region, sese region)
 651 {
 652   basic_block condition = if_region_get_condition_block (if_region);
 653   edge false_edge = get_false_edge_from_guard_bb (condition);
 654   basic_block dummy = false_edge->dest;
 655   edge entry_region = SESE_ENTRY (region);
 656   edge exit_region = SESE_EXIT (region);
 657   basic_block before_region = entry_region->src;
 658   basic_block last_in_region = exit_region->src;
 659   void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
 660                                           htab_hash_pointer (exit_region),
 661                                           NO_INSERT);
 662
 663   entry_region->flags = false_edge->flags;
 664   false_edge->flags = exit_region->flags;
 665
 666   redirect_edge_pred (entry_region, condition);
 667   redirect_edge_pred (exit_region, before_region);
 668   redirect_edge_pred (false_edge, last_in_region);
 669   redirect_edge_succ (false_edge, single_succ (dummy));
 670   delete_basic_block (dummy);
 671
 672   exit_region->flags = EDGE_FALLTHRU;
 673   recompute_all_dominators ();
 674
 675   SESE_EXIT (region) = false_edge;
 676
 677   if (if_region->false_region)
 678     free (if_region->false_region);
 679   if_region->false_region = region;
 680
 681   if (slot)
 682     {
 683       struct loop_exit *loop_exit = ggc_alloc_cleared_loop_exit ();
 684
 685       memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
 686       htab_clear_slot (current_loops->exits, slot);
 687
 688       slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
 689                                        htab_hash_pointer (false_edge),
 690                                        INSERT);
 691       loop_exit->e = false_edge;
 692       *slot = loop_exit;
 693       false_edge->src->loop_father->exits->next = loop_exit;
 694     }
 695 }
 696
 697 /* Creates an IFSESE with CONDITION on edge ENTRY.  */
 698
 699 static ifsese
 700 create_if_region_on_edge (edge entry, tree condition)
 701 {
 702   edge e;
 703   edge_iterator ei;
 704   sese sese_region = XNEW (struct sese_s);
 705   sese true_region = XNEW (struct sese_s);
 706   sese false_region = XNEW (struct sese_s);
 707   ifsese if_region = XNEW (struct ifsese_s);
 708   edge exit = create_empty_if_region_on_edge (entry, condition);
 709
 710   if_region->region = sese_region;
 711   if_region->region->entry = entry;
 712   if_region->region->exit = exit;
 713
 714   FOR_EACH_EDGE (e, ei, entry->dest->succs)
 715     {
 716       if (e->flags & EDGE_TRUE_VALUE)
 717         {
 718           true_region->entry = e;
 719           true_region->exit = single_succ_edge (e->dest);
 720           if_region->true_region = true_region;
 721         }
 722       else if (e->flags & EDGE_FALSE_VALUE)
 723         {
 724           false_region->entry = e;
 725           false_region->exit = single_succ_edge (e->dest);
 726           if_region->false_region = false_region;
 727         }
 728     }
 729
 730   return if_region;
 731 }
 732
 733 /* Moves REGION in a condition expression:
 734    | if (1)
 735    |   ;
 736    | else
 737    |   REGION;
 738 */
 739
 740 ifsese
 741 move_sese_in_condition (sese region)
 742 {
 743   basic_block pred_block = split_edge (SESE_ENTRY (region));
 744   ifsese if_region;
 745
 746   SESE_ENTRY (region) = single_succ_edge (pred_block);
 747   if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
 748   if_region_set_false_region (if_region, region);
 749
 750   return if_region;
 751 }
 752
 753 /* Replaces the condition of the IF_REGION with CONDITION:
 754    | if (CONDITION)
 755    |   true_region;
 756    | else
 757    |   false_region;
 758 */
 759
 760 void
 761 set_ifsese_condition (ifsese if_region, tree condition)
 762 {
 763   sese region = if_region->region;
 764   edge entry = region->entry;
 765   basic_block bb = entry->dest;
 766   gimple last = last_stmt (bb);
 767   gimple_stmt_iterator gsi = gsi_last_bb (bb);
 768   gimple cond_stmt;
 769
 770   gcc_assert (gimple_code (last) == GIMPLE_COND);
 771
 772   gsi_remove (&gsi, true);
 773   gsi = gsi_last_bb (bb);
 774   condition = force_gimple_operand_gsi (&gsi, condition, true, NULL,
 775                                         false, GSI_NEW_STMT);
 776   cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE);
 777   gsi = gsi_last_bb (bb);
 778   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
 779 }
 780
 781 /* Returns the scalar evolution of T in REGION.  Every variable that
 782    is not defined in the REGION is considered a parameter.  */
 783
 784 tree
 785 scalar_evolution_in_region (sese region, loop_p loop, tree t)
 786 {
 787   gimple def;
 788   struct loop *def_loop;
 789   basic_block before = block_before_sese (region);
 790
 791   if (TREE_CODE (t) != SSA_NAME
 792       || loop_in_sese_p (loop, region))
 793     return instantiate_scev (before, loop,
 794                              analyze_scalar_evolution (loop, t));
 795
 796   if (!defined_in_sese_p (t, region))
 797     return t;
 798
 799   def = SSA_NAME_DEF_STMT (t);
 800   def_loop = loop_containing_stmt (def);
 801
 802   if (loop_in_sese_p (def_loop, region))
 803     {
 804       t = analyze_scalar_evolution (def_loop, t);
 805       def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1);
 806       t = compute_overall_effect_of_inner_loop (def_loop, t);
 807       return t;
 808     }
 809   else
 810     return instantiate_scev (before, loop, t);
 811 }