gcc/sese.cc

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