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