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