gcc/sese.c

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