gcc/sese.c

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