gcc/sese.c

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