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