gcc/sese.c

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