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