gcc/sese.cc

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