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