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