gcc/sese.c

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