gcc/sese.c

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