gcc/sese.c

   1 /* Single entry single exit control flow regions.
   2    Copyright (C) 2008-2016 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 "backend.h"
  26 #include "tree.h"
  27 #include "gimple.h"
  28 #include "cfghooks.h"
  29 #include "tree-pass.h"
  30 #include "ssa.h"
  31 #include "tree-pretty-print.h"
  32 #include "fold-const.h"
  33 #include "gimplify.h"
  34 #include "gimple-iterator.h"
  35 #include "gimple-pretty-print.h"
  36 #include "gimplify-me.h"
  37 #include "tree-cfg.h"
  38 #include "tree-ssa-loop.h"
  39 #include "tree-into-ssa.h"
  40 #include "cfgloop.h"
  41 #include "tree-data-ref.h"
  42 #include "tree-scalar-evolution.h"
  43 #include "sese.h"
  44 #include "tree-ssa-propagate.h"
  45
  46 /* For a USE in BB, if BB is outside REGION, mark the USE in the
  47    LIVEOUTS set.  */
  48
  49 static void
  50 sese_build_liveouts_use (sese_info_p region, bitmap liveouts, basic_block bb,
  51                          tree use)
  52 {
  53   gcc_assert (!bb_in_sese_p (bb, region->region));
  54   if (TREE_CODE (use) != SSA_NAME)
  55     return;
  56
  57   basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
  58
  59   if (!def_bb || !bb_in_sese_p (def_bb, region->region))
  60     return;
  61
  62   unsigned ver = SSA_NAME_VERSION (use);
  63   bitmap_set_bit (liveouts, ver);
  64 }
  65
  66 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
  67    used in BB that is outside of the REGION.  */
  68
  69 static void
  70 sese_build_liveouts_bb (sese_info_p region, bitmap liveouts, basic_block bb)
  71 {
  72   edge e;
  73   edge_iterator ei;
  74   ssa_op_iter iter;
  75   use_operand_p use_p;
  76
  77   FOR_EACH_EDGE (e, ei, bb->succs)
  78     for (gphi_iterator bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi);
  79          gsi_next (&bsi))
  80       sese_build_liveouts_use (region, liveouts, bb,
  81                                PHI_ARG_DEF_FROM_EDGE (bsi.phi (), e));
  82
  83   for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
  84        gsi_next (&bsi))
  85     {
  86       gimple *stmt = gsi_stmt (bsi);
  87
  88       if (is_gimple_debug (stmt))
  89         continue;
  90
  91       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
  92         sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
  93     }
  94 }
  95
  96 /* For a USE in BB, return true if BB is outside REGION and it's not
  97    in the LIVEOUTS set.  */
  98
  99 static bool
 100 sese_bad_liveouts_use (sese_info_p region, bitmap liveouts, basic_block bb,
 101                        tree use)
 102 {
 103   gcc_assert (!bb_in_sese_p (bb, region->region));
 104
 105   if (TREE_CODE (use) != SSA_NAME)
 106     return false;
 107
 108   unsigned ver = SSA_NAME_VERSION (use);
 109
 110   /* If it's in liveouts, the variable will get a new PHI node, and
 111      the debug use will be properly adjusted.  */
 112   if (bitmap_bit_p (liveouts, ver))
 113     return false;
 114
 115   basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
 116
 117   if (!def_bb || !bb_in_sese_p (def_bb, region->region))
 118     return false;
 119
 120   return true;
 121 }
 122
 123 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
 124    are not marked as liveouts.  */
 125
 126 static void
 127 sese_reset_debug_liveouts_bb (sese_info_p region, bitmap liveouts,
 128                               basic_block bb)
 129 {
 130   gimple_stmt_iterator bsi;
 131   ssa_op_iter iter;
 132   use_operand_p use_p;
 133
 134   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 135     {
 136       gimple *stmt = gsi_stmt (bsi);
 137
 138       if (!is_gimple_debug (stmt))
 139         continue;
 140
 141       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 142         if (sese_bad_liveouts_use (region, liveouts, bb,
 143                                    USE_FROM_PTR (use_p)))
 144           {
 145             gimple_debug_bind_reset_value (stmt);
 146             update_stmt (stmt);
 147             break;
 148           }
 149     }
 150 }
 151
 152 /* Build the LIVEOUTS of REGION: the set of variables defined inside
 153    and used outside the REGION.  */
 154
 155 static void
 156 sese_build_liveouts (sese_info_p region, bitmap liveouts)
 157 {
 158   basic_block bb;
 159
 160   /* FIXME: We could start iterating form the successor of sese.  */
 161   FOR_EACH_BB_FN (bb, cfun)
 162     if (!bb_in_sese_p (bb, region->region))
 163       sese_build_liveouts_bb (region, liveouts, bb);
 164
 165   /* FIXME: We could start iterating form the successor of sese.  */
 166   if (MAY_HAVE_DEBUG_STMTS)
 167     FOR_EACH_BB_FN (bb, cfun)
 168       if (!bb_in_sese_p (bb, region->region))
 169         sese_reset_debug_liveouts_bb (region, liveouts, bb);
 170 }
 171
 172 /* Builds a new SESE region from edges ENTRY and EXIT.  */
 173
 174 sese_info_p
 175 new_sese_info (edge entry, edge exit)
 176 {
 177   sese_info_p region = XNEW (struct sese_info_t);
 178
 179   region->region.entry = entry;
 180   region->region.exit = exit;
 181   region->loop_nest.create (3);
 182   region->params.create (3);
 183   region->rename_map = new rename_map_t;
 184   region->parameter_rename_map = new parameter_rename_map_t;
 185   region->copied_bb_map = new bb_map_t;
 186   region->bbs.create (3);
 187   region->incomplete_phis.create (3);
 188
 189
 190   return region;
 191 }
 192
 193 /* Deletes REGION.  */
 194
 195 void
 196 free_sese_info (sese_info_p region)
 197 {
 198   region->params.release ();
 199   region->loop_nest.release ();
 200
 201   for (rename_map_t::iterator it = region->rename_map->begin ();
 202        it != region->rename_map->begin (); ++it)
 203     (*it).second.release ();
 204
 205   for (bb_map_t::iterator it = region->copied_bb_map->begin ();
 206        it != region->copied_bb_map->begin (); ++it)
 207     (*it).second.release ();
 208
 209   delete region->rename_map;
 210   delete region->parameter_rename_map;
 211   delete region->copied_bb_map;
 212
 213   region->rename_map = NULL;
 214   region->parameter_rename_map = NULL;
 215   region->copied_bb_map = NULL;
 216
 217   region->bbs.release ();
 218   region->incomplete_phis.release ();
 219
 220   XDELETE (region);
 221 }
 222
 223 /* Add exit phis for USE on EXIT.  */
 224
 225 static void
 226 sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
 227 {
 228   gphi *phi = create_phi_node (NULL_TREE, exit);
 229   create_new_def_for (use, phi, gimple_phi_result_ptr (phi));
 230   add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION);
 231   add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
 232   update_stmt (phi);
 233 }
 234
 235 /* Insert in the block BB phi nodes for variables defined in REGION
 236    and used outside the REGION.  The code generation moves REGION in
 237    the else clause of an "if (1)" and generates code in the then
 238    clause that is at this point empty:
 239
 240    | if (1)
 241    |   empty;
 242    | else
 243    |   REGION;
 244 */
 245
 246 void
 247 sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb,
 248                                edge false_e, edge true_e)
 249 {
 250   unsigned i;
 251   bitmap_iterator bi;
 252   bitmap liveouts = BITMAP_ALLOC (NULL);
 253
 254   sese_build_liveouts (region, liveouts);
 255
 256   EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi)
 257     if (!virtual_operand_p (ssa_name (i)))
 258       sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
 259
 260   BITMAP_FREE (liveouts);
 261 }
 262
 263 /* Returns the outermost loop in SCOP that contains BB.  */
 264
 265 struct loop *
 266 outermost_loop_in_sese_1 (sese_l &region, basic_block bb)
 267 {
 268   struct loop *nest;
 269
 270   nest = bb->loop_father;
 271   while (loop_outer (nest)
 272          && loop_in_sese_p (loop_outer (nest), region))
 273     nest = loop_outer (nest);
 274
 275   return nest;
 276 }
 277
 278 /* Same as outermost_loop_in_sese_1, returns the outermost loop
 279    containing BB in REGION, but makes sure that the returned loop
 280    belongs to the REGION, and so this returns the first loop in the
 281    REGION when the loop containing BB does not belong to REGION.  */
 282
 283 loop_p
 284 outermost_loop_in_sese (sese_l &region, basic_block bb)
 285 {
 286   loop_p nest = outermost_loop_in_sese_1 (region, bb);
 287
 288   if (loop_in_sese_p (nest, region))
 289     return nest;
 290
 291   /* When the basic block BB does not belong to a loop in the region,
 292      return the first loop in the region.  */
 293   nest = nest->inner;
 294   while (nest)
 295     if (loop_in_sese_p (nest, region))
 296       break;
 297     else
 298       nest = nest->next;
 299
 300   gcc_assert (nest);
 301   return nest;
 302 }
 303
 304 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set.  */
 305
 306 edge
 307 get_true_edge_from_guard_bb (basic_block bb)
 308 {
 309   edge e;
 310   edge_iterator ei;
 311
 312   FOR_EACH_EDGE (e, ei, bb->succs)
 313     if (e->flags & EDGE_TRUE_VALUE)
 314       return e;
 315
 316   gcc_unreachable ();
 317   return NULL;
 318 }
 319
 320 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared.  */
 321
 322 edge
 323 get_false_edge_from_guard_bb (basic_block bb)
 324 {
 325   edge e;
 326   edge_iterator ei;
 327
 328   FOR_EACH_EDGE (e, ei, bb->succs)
 329     if (!(e->flags & EDGE_TRUE_VALUE))
 330       return e;
 331
 332   gcc_unreachable ();
 333   return NULL;
 334 }
 335
 336 /* Sets the false region of an IF_REGION to REGION.  */
 337
 338 void
 339 if_region_set_false_region (ifsese if_region, sese_info_p region)
 340 {
 341   basic_block condition = if_region_get_condition_block (if_region);
 342   edge false_edge = get_false_edge_from_guard_bb (condition);
 343   basic_block dummy = false_edge->dest;
 344   edge entry_region = region->region.entry;
 345   edge exit_region = region->region.exit;
 346   basic_block before_region = entry_region->src;
 347   basic_block last_in_region = exit_region->src;
 348   hashval_t hash = htab_hash_pointer (exit_region);
 349   loop_exit **slot
 350     = current_loops->exits->find_slot_with_hash (exit_region, hash, NO_INSERT);
 351
 352   entry_region->flags = false_edge->flags;
 353   false_edge->flags = exit_region->flags;
 354
 355   redirect_edge_pred (entry_region, condition);
 356   redirect_edge_pred (exit_region, before_region);
 357   redirect_edge_pred (false_edge, last_in_region);
 358   redirect_edge_succ (false_edge, single_succ (dummy));
 359   delete_basic_block (dummy);
 360
 361   exit_region->flags = EDGE_FALLTHRU;
 362   recompute_all_dominators ();
 363
 364   region->region.exit = false_edge;
 365
 366   free (if_region->false_region);
 367   if_region->false_region = region;
 368
 369   if (slot)
 370     {
 371       struct loop_exit *loop_exit = ggc_cleared_alloc<struct loop_exit> ();
 372
 373       memcpy (loop_exit, *((struct loop_exit **) slot),
 374               sizeof (struct loop_exit));
 375       current_loops->exits->clear_slot (slot);
 376
 377       hashval_t hash = htab_hash_pointer (false_edge);
 378       slot = current_loops->exits->find_slot_with_hash (false_edge, hash,
 379                                                         INSERT);
 380       loop_exit->e = false_edge;
 381       *slot = loop_exit;
 382       false_edge->src->loop_father->exits->next = loop_exit;
 383     }
 384 }
 385
 386 /* Creates an IFSESE with CONDITION on edge ENTRY.  */
 387
 388 static ifsese
 389 create_if_region_on_edge (edge entry, tree condition)
 390 {
 391   edge e;
 392   edge_iterator ei;
 393   sese_info_p sese_region = XNEW (struct sese_info_t);
 394   sese_info_p true_region = XNEW (struct sese_info_t);
 395   sese_info_p false_region = XNEW (struct sese_info_t);
 396   ifsese if_region = XNEW (struct ifsese_s);
 397   edge exit = create_empty_if_region_on_edge (entry, condition);
 398
 399   if_region->region = sese_region;
 400   if_region->region->region.entry = entry;
 401   if_region->region->region.exit = exit;
 402
 403   FOR_EACH_EDGE (e, ei, entry->dest->succs)
 404     {
 405       if (e->flags & EDGE_TRUE_VALUE)
 406         {
 407           true_region->region.entry = e;
 408           true_region->region.exit = single_succ_edge (e->dest);
 409           if_region->true_region = true_region;
 410         }
 411       else if (e->flags & EDGE_FALSE_VALUE)
 412         {
 413           false_region->region.entry = e;
 414           false_region->region.exit = single_succ_edge (e->dest);
 415           if_region->false_region = false_region;
 416         }
 417     }
 418
 419   return if_region;
 420 }
 421
 422 /* Moves REGION in a condition expression:
 423    | if (1)
 424    |   ;
 425    | else
 426    |   REGION;
 427 */
 428
 429 ifsese
 430 move_sese_in_condition (sese_info_p region)
 431 {
 432   basic_block pred_block = split_edge (region->region.entry);
 433   ifsese if_region;
 434
 435   region->region.entry = single_succ_edge (pred_block);
 436   if_region = create_if_region_on_edge (single_pred_edge (pred_block),
 437                                         integer_one_node);
 438   if_region_set_false_region (if_region, region);
 439
 440   return if_region;
 441 }
 442
 443 /* Replaces the condition of the IF_REGION with CONDITION:
 444    | if (CONDITION)
 445    |   true_region;
 446    | else
 447    |   false_region;
 448 */
 449
 450 void
 451 set_ifsese_condition (ifsese if_region, tree condition)
 452 {
 453   sese_info_p region = if_region->region;
 454   edge entry = region->region.entry;
 455   basic_block bb = entry->dest;
 456   gimple *last = last_stmt (bb);
 457   gimple_stmt_iterator gsi = gsi_last_bb (bb);
 458   gcond *cond_stmt;
 459
 460   gcc_assert (gimple_code (last) == GIMPLE_COND);
 461
 462   gsi_remove (&gsi, true);
 463   gsi = gsi_last_bb (bb);
 464   condition = force_gimple_operand_gsi (&gsi, condition, true, NULL,
 465                                         false, GSI_NEW_STMT);
 466   cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE);
 467   gsi = gsi_last_bb (bb);
 468   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
 469 }
 470
 471 /* Return true when T is defined outside REGION or when no definitions are
 472    variant in REGION.  When HAS_VDEFS is a valid pointer, sets HAS_VDEFS to true
 473    when T depends on memory that may change in REGION.  */
 474
 475 bool
 476 invariant_in_sese_p_rec (tree t, const sese_l &region, bool *has_vdefs)
 477 {
 478   if (!defined_in_sese_p (t, region))
 479     return true;
 480
 481   gimple *stmt = SSA_NAME_DEF_STMT (t);
 482
 483   if (gimple_code (stmt) == GIMPLE_PHI
 484       || gimple_code (stmt) == GIMPLE_CALL)
 485     return false;
 486
 487   /* VDEF is variant when it is in the region.  */
 488   if (gimple_vdef (stmt))
 489     {
 490       if (has_vdefs)
 491         *has_vdefs = true;
 492       return false;
 493     }
 494
 495   /* A VUSE may or may not be variant following the VDEFs.  */
 496   if (tree vuse = gimple_vuse (stmt))
 497     return invariant_in_sese_p_rec (vuse, region, has_vdefs);
 498
 499   ssa_op_iter iter;
 500   use_operand_p use_p;
 501   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
 502     {
 503       tree use = USE_FROM_PTR (use_p);
 504
 505       if (!defined_in_sese_p (use, region))
 506         continue;
 507
 508       if (!invariant_in_sese_p_rec (use, region, has_vdefs))
 509         return false;
 510     }
 511
 512   return true;
 513 }
 514
 515 /* Return true when DEF can be analyzed in REGION by the scalar
 516    evolution analyzer.  */
 517
 518 bool
 519 scev_analyzable_p (tree def, sese_l &region)
 520 {
 521   loop_p loop;
 522   tree scev;
 523   tree type = TREE_TYPE (def);
 524
 525   /* When Graphite generates code for a scev, the code generator
 526      expresses the scev in function of a single induction variable.
 527      This is unsafe for floating point computations, as it may replace
 528      a floating point sum reduction with a multiplication.  The
 529      following test returns false for non integer types to avoid such
 530      problems.  */
 531   if (!INTEGRAL_TYPE_P (type)
 532       && !POINTER_TYPE_P (type))
 533     return false;
 534
 535   loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
 536   scev = scalar_evolution_in_region (region, loop, def);
 537
 538   return !chrec_contains_undetermined (scev)
 539     && (TREE_CODE (scev) != SSA_NAME
 540         || !defined_in_sese_p (scev, region))
 541     && (tree_does_not_contain_chrecs (scev)
 542         || evolution_function_is_affine_p (scev));
 543 }
 544
 545 /* Returns the scalar evolution of T in REGION.  Every variable that
 546    is not defined in the REGION is considered a parameter.  */
 547
 548 tree
 549 scalar_evolution_in_region (const sese_l &region, loop_p loop, tree t)
 550 {
 551   gimple *def;
 552   struct loop *def_loop;
 553   basic_block before = region.entry->src;
 554
 555   /* SCOP parameters.  */
 556   if (TREE_CODE (t) == SSA_NAME
 557       && !defined_in_sese_p (t, region))
 558     return t;
 559
 560   if (TREE_CODE (t) != SSA_NAME
 561       || loop_in_sese_p (loop, region))
 562     /* FIXME: we would need instantiate SCEV to work on a region, and be more
 563        flexible wrt. memory loads that may be invariant in the region.  */
 564     return instantiate_scev (before, loop,
 565                              analyze_scalar_evolution (loop, t));
 566
 567   def = SSA_NAME_DEF_STMT (t);
 568   def_loop = loop_containing_stmt (def);
 569
 570   if (loop_in_sese_p (def_loop, region))
 571     {
 572       t = analyze_scalar_evolution (def_loop, t);
 573       def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1);
 574       t = compute_overall_effect_of_inner_loop (def_loop, t);
 575       return t;
 576     }
 577
 578   bool has_vdefs = false;
 579   if (invariant_in_sese_p_rec (t, region, &has_vdefs))
 580     return t;
 581
 582   /* T variates in REGION.  */
 583   if (has_vdefs)
 584     return chrec_dont_know;
 585
 586   return instantiate_scev (before, loop, t);
 587 }
 588
 589 /* Pretty print edge E to FILE.  */
 590
 591 void
 592 print_edge (FILE *file, const_edge e)
 593 {
 594   fprintf (file, "edge (bb_%d, bb_%d)", e->src->index, e->dest->index);
 595 }
 596
 597 /* Pretty print sese S to FILE.  */
 598
 599 void
 600 print_sese (FILE *file, const sese_l &s)
 601 {
 602   fprintf (file, "(entry_"); print_edge (file, s.entry);
 603   fprintf (file, ", exit_"); print_edge (file, s.exit);
 604   fprintf (file, ")\n");
 605 }
 606
 607 /* Pretty print edge E to STDERR.  */
 608
 609 DEBUG_FUNCTION void
 610 debug_edge (const_edge e)
 611 {
 612   print_edge (stderr, e);
 613 }
 614
 615 /* Pretty print sese S to STDERR.  */
 616
 617 DEBUG_FUNCTION void
 618 debug_sese (const sese_l &s)
 619 {
 620   print_sese (stderr, s);
 621 }