gcc/sese.c

   1 /* Single entry single exit control flow regions.
   2    Copyright (C) 2008-2015 Free Software Foundation, Inc.
   3    Contributed by Jan Sjodin <jan.sjodin@amd.com> and
   4    Sebastian Pop <sebastian.pop@amd.com>.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "alias.h"
  26 #include "backend.h"
  27 #include "cfghooks.h"
  28 #include "tree.h"
  29 #include "gimple.h"
  30 #include "hard-reg-set.h"
  31 #include "ssa.h"
  32 #include "options.h"
  33 #include "fold-const.h"
  34 #include "tree-pretty-print.h"
  35 #include "internal-fn.h"
  36 #include "gimple-fold.h"
  37 #include "tree-eh.h"
  38 #include "gimplify.h"
  39 #include "gimple-iterator.h"
  40 #include "gimplify-me.h"
  41 #include "tree-cfg.h"
  42 #include "tree-ssa-loop.h"
  43 #include "tree-into-ssa.h"
  44 #include "cfgloop.h"
  45 #include "tree-chrec.h"
  46 #include "tree-data-ref.h"
  47 #include "tree-scalar-evolution.h"
  48 #include "tree-pass.h"
  49 #include "value-prof.h"
  50 #include "sese.h"
  51 #include "tree-ssa-propagate.h"
  52 #include "tree-hash-traits.h"
  53
  54 /* Helper function for debug_rename_map.  */
  55
  56 bool
  57 debug_rename_map_1 (tree_node *const &old_name, tree_node *const &expr,
  58                     void *)
  59 {
  60   fprintf (stderr, "(");
  61   print_generic_expr (stderr, old_name, 0);
  62   fprintf (stderr, ", ");
  63   print_generic_expr (stderr, expr, 0);
  64   fprintf (stderr, ")\n");
  65   return true;
  66 }
  67 \f
  68 typedef hash_map<tree_ssa_name_hash, tree> rename_map_type;
  69 \f
  70
  71 /* Print to stderr all the elements of RENAME_MAP.  */
  72
  73 DEBUG_FUNCTION void
  74 debug_rename_map (rename_map_type *rename_map)
  75 {
  76   rename_map->traverse <void *, debug_rename_map_1> (NULL);
  77 }
  78 \f
  79
  80 /* Record LOOP as occurring in REGION.  */
  81
  82 static void
  83 sese_record_loop (sese region, loop_p loop)
  84 {
  85   if (sese_contains_loop (region, loop))
  86     return;
  87
  88   bitmap_set_bit (SESE_LOOPS (region), loop->num);
  89   SESE_LOOP_NEST (region).safe_push (loop);
  90 }
  91
  92 /* Build the loop nests contained in REGION.  Returns true when the
  93    operation was successful.  */
  94
  95 void
  96 build_sese_loop_nests (sese region)
  97 {
  98   unsigned i;
  99   basic_block bb;
 100   struct loop *loop0, *loop1;
 101
 102   FOR_EACH_BB_FN (bb, cfun)
 103     if (bb_in_sese_p (bb, region))
 104       {
 105         struct loop *loop = bb->loop_father;
 106
 107         /* Only add loops if they are completely contained in the SCoP.  */
 108         if (loop->header == bb
 109             && bb_in_sese_p (loop->latch, region))
 110           sese_record_loop (region, loop);
 111       }
 112
 113   /* Make sure that the loops in the SESE_LOOP_NEST are ordered.  It
 114      can be the case that an inner loop is inserted before an outer
 115      loop.  To avoid this, semi-sort once.  */
 116   FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), i, loop0)
 117     {
 118       if (SESE_LOOP_NEST (region).length () == i + 1)
 119         break;
 120
 121       loop1 = SESE_LOOP_NEST (region)[i + 1];
 122       if (loop0->num > loop1->num)
 123         {
 124           SESE_LOOP_NEST (region)[i] = loop1;
 125           SESE_LOOP_NEST (region)[i + 1] = loop0;
 126         }
 127     }
 128 }
 129
 130 /* For a USE in BB, if BB is outside REGION, mark the USE in the
 131    LIVEOUTS set.  */
 132
 133 static void
 134 sese_build_liveouts_use (sese region, bitmap liveouts, basic_block bb,
 135                          tree use)
 136 {
 137   unsigned ver;
 138   basic_block def_bb;
 139
 140   if (TREE_CODE (use) != SSA_NAME)
 141     return;
 142
 143   ver = SSA_NAME_VERSION (use);
 144   def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
 145
 146   if (!def_bb
 147       || !bb_in_sese_p (def_bb, region)
 148       || bb_in_sese_p (bb, region))
 149     return;
 150
 151   bitmap_set_bit (liveouts, ver);
 152 }
 153
 154 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
 155    used in BB that is outside of the REGION.  */
 156
 157 static void
 158 sese_build_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
 159 {
 160   edge e;
 161   edge_iterator ei;
 162   ssa_op_iter iter;
 163   use_operand_p use_p;
 164
 165   FOR_EACH_EDGE (e, ei, bb->succs)
 166     for (gphi_iterator bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi);
 167          gsi_next (&bsi))
 168       sese_build_liveouts_use (region, liveouts, bb,
 169                                PHI_ARG_DEF_FROM_EDGE (bsi.phi (), e));
 170
 171   for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
 172        gsi_next (&bsi))
 173     {
 174       gimple *stmt = gsi_stmt (bsi);
 175
 176       if (is_gimple_debug (stmt))
 177         continue;
 178
 179       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 180         sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
 181     }
 182 }
 183
 184 /* For a USE in BB, return true if BB is outside REGION and it's not
 185    in the LIVEOUTS set.  */
 186
 187 static bool
 188 sese_bad_liveouts_use (sese region, bitmap liveouts, basic_block bb,
 189                        tree use)
 190 {
 191   unsigned ver;
 192   basic_block def_bb;
 193
 194   if (TREE_CODE (use) != SSA_NAME)
 195     return false;
 196
 197   ver = SSA_NAME_VERSION (use);
 198
 199   /* If it's in liveouts, the variable will get a new PHI node, and
 200      the debug use will be properly adjusted.  */
 201   if (bitmap_bit_p (liveouts, ver))
 202     return false;
 203
 204   def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
 205
 206   if (!def_bb
 207       || !bb_in_sese_p (def_bb, region)
 208       || bb_in_sese_p (bb, region))
 209     return false;
 210
 211   return true;
 212 }
 213
 214 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
 215    are not marked as liveouts.  */
 216
 217 static void
 218 sese_reset_debug_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
 219 {
 220   gimple_stmt_iterator bsi;
 221   ssa_op_iter iter;
 222   use_operand_p use_p;
 223
 224   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 225     {
 226       gimple *stmt = gsi_stmt (bsi);
 227
 228       if (!is_gimple_debug (stmt))
 229         continue;
 230
 231       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 232         if (sese_bad_liveouts_use (region, liveouts, bb,
 233                                    USE_FROM_PTR (use_p)))
 234           {
 235             gimple_debug_bind_reset_value (stmt);
 236             update_stmt (stmt);
 237             break;
 238           }
 239     }
 240 }
 241
 242 /* Build the LIVEOUTS of REGION: the set of variables defined inside
 243    and used outside the REGION.  */
 244
 245 static void
 246 sese_build_liveouts (sese region, bitmap liveouts)
 247 {
 248   basic_block bb;
 249
 250   FOR_EACH_BB_FN (bb, cfun)
 251     sese_build_liveouts_bb (region, liveouts, bb);
 252   if (MAY_HAVE_DEBUG_STMTS)
 253     FOR_EACH_BB_FN (bb, cfun)
 254       sese_reset_debug_liveouts_bb (region, liveouts, bb);
 255 }
 256
 257 /* Builds a new SESE region from edges ENTRY and EXIT.  */
 258
 259 sese
 260 new_sese (edge entry, edge exit)
 261 {
 262   sese region = XNEW (struct sese_s);
 263
 264   SESE_ENTRY (region) = entry;
 265   SESE_EXIT (region) = exit;
 266   SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
 267   SESE_LOOP_NEST (region).create (3);
 268   SESE_ADD_PARAMS (region) = true;
 269   SESE_PARAMS (region).create (3);
 270   region->parameter_rename_map = new parameter_rename_map_t;
 271
 272   return region;
 273 }
 274
 275 /* Deletes REGION.  */
 276
 277 void
 278 free_sese (sese region)
 279 {
 280   if (SESE_LOOPS (region))
 281     SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
 282
 283   SESE_PARAMS (region).release ();
 284   SESE_LOOP_NEST (region).release ();
 285   delete region->parameter_rename_map;
 286   region->parameter_rename_map = NULL;
 287
 288   XDELETE (region);
 289 }
 290
 291 /* Add exit phis for USE on EXIT.  */
 292
 293 static void
 294 sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
 295 {
 296   gphi *phi = create_phi_node (NULL_TREE, exit);
 297   create_new_def_for (use, phi, gimple_phi_result_ptr (phi));
 298   add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION);
 299   add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
 300   update_stmt (phi);
 301 }
 302
 303 /* Insert in the block BB phi nodes for variables defined in REGION
 304    and used outside the REGION.  The code generation moves REGION in
 305    the else clause of an "if (1)" and generates code in the then
 306    clause that is at this point empty:
 307
 308    | if (1)
 309    |   empty;
 310    | else
 311    |   REGION;
 312 */
 313
 314 void
 315 sese_insert_phis_for_liveouts (sese region, basic_block bb,
 316                                edge false_e, edge true_e)
 317 {
 318   unsigned i;
 319   bitmap_iterator bi;
 320   bitmap liveouts = BITMAP_ALLOC (NULL);
 321
 322   update_ssa (TODO_update_ssa);
 323
 324   sese_build_liveouts (region, liveouts);
 325   EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi)
 326     sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
 327   BITMAP_FREE (liveouts);
 328
 329   update_ssa (TODO_update_ssa);
 330 }
 331
 332 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set.  */
 333
 334 edge
 335 get_true_edge_from_guard_bb (basic_block bb)
 336 {
 337   edge e;
 338   edge_iterator ei;
 339
 340   FOR_EACH_EDGE (e, ei, bb->succs)
 341     if (e->flags & EDGE_TRUE_VALUE)
 342       return e;
 343
 344   gcc_unreachable ();
 345   return NULL;
 346 }
 347
 348 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared.  */
 349
 350 edge
 351 get_false_edge_from_guard_bb (basic_block bb)
 352 {
 353   edge e;
 354   edge_iterator ei;
 355
 356   FOR_EACH_EDGE (e, ei, bb->succs)
 357     if (!(e->flags & EDGE_TRUE_VALUE))
 358       return e;
 359
 360   gcc_unreachable ();
 361   return NULL;
 362 }
 363
 364 /* Returns the expression associated to OLD_NAME in RENAME_MAP.  */
 365
 366 static tree
 367 get_rename (rename_map_type *rename_map, tree old_name)
 368 {
 369   gcc_assert (TREE_CODE (old_name) == SSA_NAME);
 370   tree *expr = rename_map->get (old_name);
 371   if (expr)
 372     return *expr;
 373
 374   return NULL_TREE;
 375 }
 376
 377 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).  */
 378
 379 static void
 380 set_rename (rename_map_type *rename_map, tree old_name, tree expr, sese region)
 381 {
 382   if (old_name == expr)
 383     return;
 384
 385   rename_map->put (old_name, expr);
 386
 387   tree t;
 388   int i;
 389   /* For a parameter of a scop we dont want to rename it.  */
 390   FOR_EACH_VEC_ELT (SESE_PARAMS (region), i, t)
 391     if (old_name == t)
 392       region->parameter_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, region);
 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       /* Do not copy parameters that have been generated in the header of the
 540          scop.  */
 541       if (is_gimple_assign (stmt)
 542           && (lhs = gimple_assign_lhs (stmt))
 543           && TREE_CODE (lhs) == SSA_NAME
 544           && region->parameter_rename_map->get(lhs))
 545         continue;
 546
 547       /* Create a new copy of STMT and duplicate STMT's virtual
 548          operands.  */
 549       copy = gimple_copy (stmt);
 550       gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
 551
 552       maybe_duplicate_eh_stmt (copy, stmt);
 553       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
 554
 555       /* Create new names for all the definitions created by COPY and
 556          add replacement mappings for each new name.  */
 557       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
 558         {
 559           tree old_name = DEF_FROM_PTR (def_p);
 560           tree new_name = create_new_def_for (old_name, copy, def_p);
 561           set_rename (rename_map, old_name, new_name, region);
 562         }
 563
 564       if (rename_uses (copy, rename_map, &gsi_tgt, region, loop, iv_map,
 565                        gloog_error))
 566         {
 567           gcc_assert (gsi_stmt (gsi_tgt) == copy);
 568           fold_stmt_inplace (&gsi_tgt);
 569         }
 570
 571       /* For each SSA_NAME in the parameter_rename_map rename their usage.  */
 572       ssa_op_iter iter;
 573       use_operand_p use_p;
 574       if (!is_gimple_debug (copy))
 575         FOR_EACH_SSA_USE_OPERAND (use_p, copy, iter, SSA_OP_USE)
 576           {
 577             tree old_name = USE_FROM_PTR (use_p);
 578
 579             if (TREE_CODE (old_name) != SSA_NAME
 580                 || SSA_NAME_IS_DEFAULT_DEF (old_name))
 581               continue;
 582
 583             tree *new_expr = region->parameter_rename_map->get (old_name);
 584             if (!new_expr)
 585               continue;
 586
 587             replace_exp (use_p, *new_expr);
 588           }
 589
 590       update_stmt (copy);
 591     }
 592 }
 593
 594 /* Copies BB and includes in the copied BB all the statements that can
 595    be reached following the use-def chains from the memory accesses,
 596    and returns the next edge following this new block.  GLOOG_ERROR is
 597    set when the code generation cannot continue.  */
 598
 599 edge
 600 copy_bb_and_scalar_dependences (basic_block bb, sese region,
 601                                 edge next_e, vec<tree> iv_map,
 602                                 bool *gloog_error)
 603 {
 604   basic_block new_bb = split_edge (next_e);
 605   rename_map_type rename_map (10);
 606
 607   next_e = single_succ_edge (new_bb);
 608   graphite_copy_stmts_from_block (bb, new_bb, &rename_map, iv_map, region,
 609                                   gloog_error);
 610   remove_phi_nodes (new_bb);
 611
 612   return next_e;
 613 }
 614
 615 /* Returns the outermost loop in SCOP that contains BB.  */
 616
 617 struct loop *
 618 outermost_loop_in_sese_1 (sese region, basic_block bb)
 619 {
 620   struct loop *nest;
 621
 622   nest = bb->loop_father;
 623   while (loop_outer (nest)
 624          && loop_in_sese_p (loop_outer (nest), region))
 625     nest = loop_outer (nest);
 626
 627   return nest;
 628 }
 629
 630 /* Same as outermost_loop_in_sese_1, returns the outermost loop
 631    containing BB in REGION, but makes sure that the returned loop
 632    belongs to the REGION, and so this returns the first loop in the
 633    REGION when the loop containing BB does not belong to REGION.  */
 634
 635 loop_p
 636 outermost_loop_in_sese (sese region, basic_block bb)
 637 {
 638   loop_p nest = outermost_loop_in_sese_1 (region, bb);
 639
 640   if (loop_in_sese_p (nest, region))
 641     return nest;
 642
 643   /* When the basic block BB does not belong to a loop in the region,
 644      return the first loop in the region.  */
 645   nest = nest->inner;
 646   while (nest)
 647     if (loop_in_sese_p (nest, region))
 648       break;
 649     else
 650       nest = nest->next;
 651
 652   gcc_assert (nest);
 653   return nest;
 654 }
 655
 656 /* Sets the false region of an IF_REGION to REGION.  */
 657
 658 void
 659 if_region_set_false_region (ifsese if_region, sese region)
 660 {
 661   basic_block condition = if_region_get_condition_block (if_region);
 662   edge false_edge = get_false_edge_from_guard_bb (condition);
 663   basic_block dummy = false_edge->dest;
 664   edge entry_region = SESE_ENTRY (region);
 665   edge exit_region = SESE_EXIT (region);
 666   basic_block before_region = entry_region->src;
 667   basic_block last_in_region = exit_region->src;
 668   hashval_t hash = htab_hash_pointer (exit_region);
 669   loop_exit **slot
 670     = current_loops->exits->find_slot_with_hash (exit_region, hash, NO_INSERT);
 671
 672   entry_region->flags = false_edge->flags;
 673   false_edge->flags = exit_region->flags;
 674
 675   redirect_edge_pred (entry_region, condition);
 676   redirect_edge_pred (exit_region, before_region);
 677   redirect_edge_pred (false_edge, last_in_region);
 678   redirect_edge_succ (false_edge, single_succ (dummy));
 679   delete_basic_block (dummy);
 680
 681   exit_region->flags = EDGE_FALLTHRU;
 682   recompute_all_dominators ();
 683
 684   SESE_EXIT (region) = false_edge;
 685
 686   free (if_region->false_region);
 687   if_region->false_region = region;
 688
 689   if (slot)
 690     {
 691       struct loop_exit *loop_exit = ggc_cleared_alloc<struct loop_exit> ();
 692
 693       memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
 694       current_loops->exits->clear_slot (slot);
 695
 696       hashval_t hash = htab_hash_pointer (false_edge);
 697       slot = current_loops->exits->find_slot_with_hash (false_edge, hash,
 698                                                         INSERT);
 699       loop_exit->e = false_edge;
 700       *slot = loop_exit;
 701       false_edge->src->loop_father->exits->next = loop_exit;
 702     }
 703 }
 704
 705 /* Creates an IFSESE with CONDITION on edge ENTRY.  */
 706
 707 static ifsese
 708 create_if_region_on_edge (edge entry, tree condition)
 709 {
 710   edge e;
 711   edge_iterator ei;
 712   sese sese_region = XNEW (struct sese_s);
 713   sese true_region = XNEW (struct sese_s);
 714   sese false_region = XNEW (struct sese_s);
 715   ifsese if_region = XNEW (struct ifsese_s);
 716   edge exit = create_empty_if_region_on_edge (entry, condition);
 717
 718   if_region->region = sese_region;
 719   if_region->region->entry = entry;
 720   if_region->region->exit = exit;
 721
 722   FOR_EACH_EDGE (e, ei, entry->dest->succs)
 723     {
 724       if (e->flags & EDGE_TRUE_VALUE)
 725         {
 726           true_region->entry = e;
 727           true_region->exit = single_succ_edge (e->dest);
 728           if_region->true_region = true_region;
 729         }
 730       else if (e->flags & EDGE_FALSE_VALUE)
 731         {
 732           false_region->entry = e;
 733           false_region->exit = single_succ_edge (e->dest);
 734           if_region->false_region = false_region;
 735         }
 736     }
 737
 738   return if_region;
 739 }
 740
 741 /* Moves REGION in a condition expression:
 742    | if (1)
 743    |   ;
 744    | else
 745    |   REGION;
 746 */
 747
 748 ifsese
 749 move_sese_in_condition (sese region)
 750 {
 751   basic_block pred_block = split_edge (SESE_ENTRY (region));
 752   ifsese if_region;
 753
 754   SESE_ENTRY (region) = single_succ_edge (pred_block);
 755   if_region = create_if_region_on_edge (single_pred_edge (pred_block),
 756                                         integer_one_node);
 757   if_region_set_false_region (if_region, region);
 758
 759   return if_region;
 760 }
 761
 762 /* Replaces the condition of the IF_REGION with CONDITION:
 763    | if (CONDITION)
 764    |   true_region;
 765    | else
 766    |   false_region;
 767 */
 768
 769 void
 770 set_ifsese_condition (ifsese if_region, tree condition)
 771 {
 772   sese region = if_region->region;
 773   edge entry = region->entry;
 774   basic_block bb = entry->dest;
 775   gimple *last = last_stmt (bb);
 776   gimple_stmt_iterator gsi = gsi_last_bb (bb);
 777   gcond *cond_stmt;
 778
 779   gcc_assert (gimple_code (last) == GIMPLE_COND);
 780
 781   gsi_remove (&gsi, true);
 782   gsi = gsi_last_bb (bb);
 783   condition = force_gimple_operand_gsi (&gsi, condition, true, NULL,
 784                                         false, GSI_NEW_STMT);
 785   cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE);
 786   gsi = gsi_last_bb (bb);
 787   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
 788 }
 789
 790 /* Return true when T is defined outside REGION or when no definitions are
 791    variant in REGION.  */
 792
 793 bool
 794 invariant_in_sese_p_rec (tree t, sese region)
 795 {
 796   ssa_op_iter iter;
 797   use_operand_p use_p;
 798   if (!defined_in_sese_p (t, region))
 799     return true;
 800
 801   gimple *stmt = SSA_NAME_DEF_STMT (t);
 802
 803   if (gimple_code (stmt) == GIMPLE_PHI
 804       || gimple_code (stmt) == GIMPLE_CALL)
 805     return false;
 806
 807   /* VDEF is variant when it is in the region.  */
 808   if (gimple_vdef (stmt))
 809     return false;
 810
 811   /* A VUSE may or may not be variant following the VDEFs.  */
 812   if (tree vuse = gimple_vuse (stmt))
 813     return invariant_in_sese_p_rec (vuse, region);
 814
 815   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
 816     {
 817       tree use = USE_FROM_PTR (use_p);
 818
 819       if (!defined_in_sese_p (use, region))
 820         continue;
 821
 822       if (!invariant_in_sese_p_rec (use, region))
 823         return false;
 824     }
 825
 826   return true;
 827 }
 828
 829 /* Returns the scalar evolution of T in REGION.  Every variable that
 830    is not defined in the REGION is considered a parameter.  */
 831
 832 tree
 833 scalar_evolution_in_region (sese region, loop_p loop, tree t)
 834 {
 835   gimple *def;
 836   struct loop *def_loop;
 837   basic_block before = block_before_sese (region);
 838
 839   /* SCOP parameters.  */
 840   if (TREE_CODE (t) == SSA_NAME
 841       && !defined_in_sese_p (t, region))
 842     return t;
 843
 844   if (TREE_CODE (t) != SSA_NAME
 845       || loop_in_sese_p (loop, region))
 846     return instantiate_scev (before, loop,
 847                              analyze_scalar_evolution (loop, t));
 848
 849   def = SSA_NAME_DEF_STMT (t);
 850   def_loop = loop_containing_stmt (def);
 851
 852   if (loop_in_sese_p (def_loop, region))
 853     {
 854       t = analyze_scalar_evolution (def_loop, t);
 855       def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1);
 856       t = compute_overall_effect_of_inner_loop (def_loop, t);
 857       return t;
 858     }
 859
 860   if (invariant_in_sese_p_rec (t, region))
 861     return t;
 862
 863   return instantiate_scev (before, loop, t);
 864 }