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