gcc/sese.c

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