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