gcc/sese.c

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