contrib/gcc-4.7/gcc/sese.c

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