gcc/sese.c

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