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