gcc/sese.c

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