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