gcc/sese.c

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