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 lhs = gimple_assign_lhs (copy);
 554           tree rhs = gimple_assign_rhs1 (copy);
 555
 556           if (TREE_CODE (lhs) == ADDR_EXPR)
 557             recompute_tree_invariant_for_addr_expr (lhs);
 558           if (TREE_CODE (rhs) == ADDR_EXPR)
 559             recompute_tree_invariant_for_addr_expr (rhs);
 560         }
 561
 562       set_rename (rename_map, old_name, new_expr);
 563     }
 564 }
 565
 566 /* Duplicates the statements of basic block BB into basic block NEW_BB
 567    and compute the new induction variables according to the IV_MAP.  */
 568
 569 static void
 570 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb,
 571                                 htab_t rename_map,
 572                                 VEC (tree, heap) *iv_map, sese region)
 573 {
 574   gimple_stmt_iterator gsi, gsi_tgt;
 575   loop_p loop = bb->loop_father;
 576
 577   gsi_tgt = gsi_start_bb (new_bb);
 578   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 579     {
 580       def_operand_p def_p;
 581       ssa_op_iter op_iter;
 582       gimple stmt = gsi_stmt (gsi);
 583       gimple copy;
 584       tree lhs;
 585
 586       /* Do not copy labels or conditions.  */
 587       if (gimple_code (stmt) == GIMPLE_LABEL
 588           || gimple_code (stmt) == GIMPLE_COND)
 589         continue;
 590
 591       /* Do not copy induction variables.  */
 592       if (is_gimple_assign (stmt)
 593           && (lhs = gimple_assign_lhs (stmt))
 594           && TREE_CODE (lhs) == SSA_NAME
 595           && is_gimple_reg (lhs)
 596           && scev_analyzable_p (lhs, region))
 597         continue;
 598
 599       /* Create a new copy of STMT and duplicate STMT's virtual
 600          operands.  */
 601       copy = gimple_copy (stmt);
 602       gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
 603       mark_sym_for_renaming (gimple_vop (cfun));
 604
 605       maybe_duplicate_eh_stmt (copy, stmt);
 606       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
 607
 608       /* Create new names for all the definitions created by COPY and
 609          add replacement mappings for each new name.  */
 610       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
 611         {
 612           tree old_name = DEF_FROM_PTR (def_p);
 613           tree new_name = create_new_def_for (old_name, copy, def_p);
 614           set_rename (rename_map, old_name, new_name);
 615         }
 616
 617       rename_uses (copy, rename_map, &gsi_tgt, region, loop, iv_map);
 618
 619       update_stmt (copy);
 620     }
 621 }
 622
 623 /* Copies BB and includes in the copied BB all the statements that can
 624    be reached following the use-def chains from the memory accesses,
 625    and returns the next edge following this new block.  */
 626
 627 edge
 628 copy_bb_and_scalar_dependences (basic_block bb, sese region,
 629                                 edge next_e, VEC (tree, heap) *iv_map)
 630 {
 631   basic_block new_bb = split_edge (next_e);
 632   htab_t rename_map = htab_create (10, rename_map_elt_info,
 633                                    eq_rename_map_elts, free);
 634
 635   next_e = single_succ_edge (new_bb);
 636   graphite_copy_stmts_from_block (bb, new_bb, rename_map, iv_map, region);
 637   remove_phi_nodes (new_bb);
 638   htab_delete (rename_map);
 639
 640   return next_e;
 641 }
 642
 643 /* Returns the outermost loop in SCOP that contains BB.  */
 644
 645 struct loop *
 646 outermost_loop_in_sese (sese region, basic_block bb)
 647 {
 648   struct loop *nest;
 649
 650   nest = bb->loop_father;
 651   while (loop_outer (nest)
 652          && loop_in_sese_p (loop_outer (nest), region))
 653     nest = loop_outer (nest);
 654
 655   return nest;
 656 }
 657
 658 /* Sets the false region of an IF_REGION to REGION.  */
 659
 660 void
 661 if_region_set_false_region (ifsese if_region, sese region)
 662 {
 663   basic_block condition = if_region_get_condition_block (if_region);
 664   edge false_edge = get_false_edge_from_guard_bb (condition);
 665   basic_block dummy = false_edge->dest;
 666   edge entry_region = SESE_ENTRY (region);
 667   edge exit_region = SESE_EXIT (region);
 668   basic_block before_region = entry_region->src;
 669   basic_block last_in_region = exit_region->src;
 670   void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
 671                                           htab_hash_pointer (exit_region),
 672                                           NO_INSERT);
 673
 674   entry_region->flags = false_edge->flags;
 675   false_edge->flags = exit_region->flags;
 676
 677   redirect_edge_pred (entry_region, condition);
 678   redirect_edge_pred (exit_region, before_region);
 679   redirect_edge_pred (false_edge, last_in_region);
 680   redirect_edge_succ (false_edge, single_succ (dummy));
 681   delete_basic_block (dummy);
 682
 683   exit_region->flags = EDGE_FALLTHRU;
 684   recompute_all_dominators ();
 685
 686   SESE_EXIT (region) = false_edge;
 687
 688   if (if_region->false_region)
 689     free (if_region->false_region);
 690   if_region->false_region = region;
 691
 692   if (slot)
 693     {
 694       struct loop_exit *loop_exit = ggc_alloc_cleared_loop_exit ();
 695
 696       memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
 697       htab_clear_slot (current_loops->exits, slot);
 698
 699       slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
 700                                        htab_hash_pointer (false_edge),
 701                                        INSERT);
 702       loop_exit->e = false_edge;
 703       *slot = loop_exit;
 704       false_edge->src->loop_father->exits->next = loop_exit;
 705     }
 706 }
 707
 708 /* Creates an IFSESE with CONDITION on edge ENTRY.  */
 709
 710 static ifsese
 711 create_if_region_on_edge (edge entry, tree condition)
 712 {
 713   edge e;
 714   edge_iterator ei;
 715   sese sese_region = XNEW (struct sese_s);
 716   sese true_region = XNEW (struct sese_s);
 717   sese false_region = XNEW (struct sese_s);
 718   ifsese if_region = XNEW (struct ifsese_s);
 719   edge exit = create_empty_if_region_on_edge (entry, condition);
 720
 721   if_region->region = sese_region;
 722   if_region->region->entry = entry;
 723   if_region->region->exit = exit;
 724
 725   FOR_EACH_EDGE (e, ei, entry->dest->succs)
 726     {
 727       if (e->flags & EDGE_TRUE_VALUE)
 728         {
 729           true_region->entry = e;
 730           true_region->exit = single_succ_edge (e->dest);
 731           if_region->true_region = true_region;
 732         }
 733       else if (e->flags & EDGE_FALSE_VALUE)
 734         {
 735           false_region->entry = e;
 736           false_region->exit = single_succ_edge (e->dest);
 737           if_region->false_region = false_region;
 738         }
 739     }
 740
 741   return if_region;
 742 }
 743
 744 /* Moves REGION in a condition expression:
 745    | if (1)
 746    |   ;
 747    | else
 748    |   REGION;
 749 */
 750
 751 ifsese
 752 move_sese_in_condition (sese region)
 753 {
 754   basic_block pred_block = split_edge (SESE_ENTRY (region));
 755   ifsese if_region;
 756
 757   SESE_ENTRY (region) = single_succ_edge (pred_block);
 758   if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
 759   if_region_set_false_region (if_region, region);
 760
 761   return if_region;
 762 }
 763
 764 /* Replaces the condition of the IF_REGION with CONDITION:
 765    | if (CONDITION)
 766    |   true_region;
 767    | else
 768    |   false_region;
 769 */
 770
 771 void
 772 set_ifsese_condition (ifsese if_region, tree condition)
 773 {
 774   sese region = if_region->region;
 775   edge entry = region->entry;
 776   basic_block bb = entry->dest;
 777   gimple last = last_stmt (bb);
 778   gimple_stmt_iterator gsi = gsi_last_bb (bb);
 779   gimple cond_stmt;
 780
 781   gcc_assert (gimple_code (last) == GIMPLE_COND);
 782
 783   gsi_remove (&gsi, true);
 784   gsi = gsi_last_bb (bb);
 785   condition = force_gimple_operand_gsi (&gsi, condition, true, NULL,
 786                                         false, GSI_NEW_STMT);
 787   cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE);
 788   gsi = gsi_last_bb (bb);
 789   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
 790 }
 791
 792 /* Returns the scalar evolution of T in REGION.  Every variable that
 793    is not defined in the REGION is considered a parameter.  */
 794
 795 tree
 796 scalar_evolution_in_region (sese region, loop_p loop, tree t)
 797 {
 798   gimple def;
 799   struct loop *def_loop;
 800   basic_block before = block_before_sese (region);
 801
 802   if (TREE_CODE (t) != SSA_NAME
 803       || loop_in_sese_p (loop, region))
 804     return instantiate_scev (before, loop,
 805                              analyze_scalar_evolution (loop, t));
 806
 807   if (!defined_in_sese_p (t, region))
 808     return t;
 809
 810   def = SSA_NAME_DEF_STMT (t);
 811   def_loop = loop_containing_stmt (def);
 812
 813   if (loop_in_sese_p (def_loop, region))
 814     {
 815       t = analyze_scalar_evolution (def_loop, t);
 816       def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1);
 817       t = compute_overall_effect_of_inner_loop (def_loop, t);
 818       return t;
 819     }
 820   else
 821     return instantiate_scev (before, loop, t);
 822 }