gcc/sese.c

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