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