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