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