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