gcc/tree-ssa-loop.cc

   1 /* Loop optimizations over tree-ssa.
   2    Copyright (C) 2003-2024 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 3, or (at your option) any
   9 later version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT
  12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "backend.h"
  24 #include "tree.h"
  25 #include "gimple.h"
  26 #include "tree-pass.h"
  27 #include "memmodel.h"
  28 #include "tm_p.h"
  29 #include "fold-const.h"
  30 #include "gimple-iterator.h"
  31 #include "tree-ssa-loop-ivopts.h"
  32 #include "tree-ssa-loop-manip.h"
  33 #include "tree-ssa-loop-niter.h"
  34 #include "tree-ssa-loop.h"
  35 #include "cfgloop.h"
  36 #include "tree-inline.h"
  37 #include "tree-scalar-evolution.h"
  38 #include "omp-general.h"
  39 #include "diagnostic-core.h"
  40 #include "stringpool.h"
  41 #include "attribs.h"
  42
  43
  44 /* A pass making sure loops are fixed up.  */
  45
  46 namespace {
  47
  48 const pass_data pass_data_fix_loops =
  49 {
  50   GIMPLE_PASS, /* type */
  51   "fix_loops", /* name */
  52   OPTGROUP_LOOP, /* optinfo_flags */
  53   TV_TREE_LOOP, /* tv_id */
  54   PROP_cfg, /* properties_required */
  55   0, /* properties_provided */
  56   0, /* properties_destroyed */
  57   0, /* todo_flags_start */
  58   0, /* todo_flags_finish */
  59 };
  60
  61 class pass_fix_loops : public gimple_opt_pass
  62 {
  63 public:
  64   pass_fix_loops (gcc::context *ctxt)
  65     : gimple_opt_pass (pass_data_fix_loops, ctxt)
  66   {}
  67
  68   /* opt_pass methods: */
  69   bool gate (function *) final override { return flag_tree_loop_optimize; }
  70
  71   unsigned int execute (function *fn) final override;
  72 }; // class pass_fix_loops
  73
  74 unsigned int
  75 pass_fix_loops::execute (function *)
  76 {
  77   if (loops_state_satisfies_p (LOOPS_NEED_FIXUP))
  78     {
  79       calculate_dominance_info (CDI_DOMINATORS);
  80       fix_loop_structure (NULL);
  81     }
  82   return 0;
  83 }
  84
  85 } // anon namespace
  86
  87 gimple_opt_pass *
  88 make_pass_fix_loops (gcc::context *ctxt)
  89 {
  90   return new pass_fix_loops (ctxt);
  91 }
  92
  93
  94 /* Gate for loop pass group.  The group is controlled by -ftree-loop-optimize
  95    but we also avoid running it when the IL doesn't contain any loop.  */
  96
  97 static bool
  98 gate_loop (function *fn)
  99 {
 100   if (!flag_tree_loop_optimize)
 101     return false;
 102
 103   /* For -fdump-passes which runs before loop discovery print the
 104      state of -ftree-loop-optimize.  */
 105   if (!loops_for_fn (fn))
 106     return true;
 107
 108   return number_of_loops (fn) > 1;
 109 }
 110
 111 /* The loop superpass.  */
 112
 113 namespace {
 114
 115 const pass_data pass_data_tree_loop =
 116 {
 117   GIMPLE_PASS, /* type */
 118   "loop", /* name */
 119   OPTGROUP_LOOP, /* optinfo_flags */
 120   TV_TREE_LOOP, /* tv_id */
 121   PROP_cfg, /* properties_required */
 122   0, /* properties_provided */
 123   0, /* properties_destroyed */
 124   0, /* todo_flags_start */
 125   0, /* todo_flags_finish */
 126 };
 127
 128 class pass_tree_loop : public gimple_opt_pass
 129 {
 130 public:
 131   pass_tree_loop (gcc::context *ctxt)
 132     : gimple_opt_pass (pass_data_tree_loop, ctxt)
 133   {}
 134
 135   /* opt_pass methods: */
 136   bool gate (function *fn) final override { return gate_loop (fn); }
 137
 138 }; // class pass_tree_loop
 139
 140 } // anon namespace
 141
 142 gimple_opt_pass *
 143 make_pass_tree_loop (gcc::context *ctxt)
 144 {
 145   return new pass_tree_loop (ctxt);
 146 }
 147
 148 /* Gate for oacc kernels pass group.  */
 149
 150 static bool
 151 gate_oacc_kernels (function *fn)
 152 {
 153   if (!flag_openacc)
 154     return false;
 155
 156   if (!lookup_attribute ("oacc kernels", DECL_ATTRIBUTES (fn->decl)))
 157     return false;
 158
 159   for (auto loop : loops_list (cfun, 0))
 160     if (loop->in_oacc_kernels_region)
 161       return true;
 162
 163   return false;
 164 }
 165
 166 /* The oacc kernels superpass.  */
 167
 168 namespace {
 169
 170 const pass_data pass_data_oacc_kernels =
 171 {
 172   GIMPLE_PASS, /* type */
 173   "oacc_kernels", /* name */
 174   OPTGROUP_LOOP, /* optinfo_flags */
 175   TV_TREE_LOOP, /* tv_id */
 176   PROP_cfg, /* properties_required */
 177   0, /* properties_provided */
 178   0, /* properties_destroyed */
 179   0, /* todo_flags_start */
 180   0, /* todo_flags_finish */
 181 };
 182
 183 class pass_oacc_kernels : public gimple_opt_pass
 184 {
 185 public:
 186   pass_oacc_kernels (gcc::context *ctxt)
 187     : gimple_opt_pass (pass_data_oacc_kernels, ctxt)
 188   {}
 189
 190   /* opt_pass methods: */
 191   bool gate (function *fn) final override { return gate_oacc_kernels (fn); }
 192
 193 }; // class pass_oacc_kernels
 194
 195 } // anon namespace
 196
 197 gimple_opt_pass *
 198 make_pass_oacc_kernels (gcc::context *ctxt)
 199 {
 200   return new pass_oacc_kernels (ctxt);
 201 }
 202
 203 /* The ipa oacc superpass.  */
 204
 205 namespace {
 206
 207 const pass_data pass_data_ipa_oacc =
 208 {
 209   SIMPLE_IPA_PASS, /* type */
 210   "ipa_oacc", /* name */
 211   OPTGROUP_LOOP, /* optinfo_flags */
 212   TV_TREE_LOOP, /* tv_id */
 213   PROP_cfg, /* properties_required */
 214   0, /* properties_provided */
 215   0, /* properties_destroyed */
 216   0, /* todo_flags_start */
 217   0, /* todo_flags_finish */
 218 };
 219
 220 class pass_ipa_oacc : public simple_ipa_opt_pass
 221 {
 222 public:
 223   pass_ipa_oacc (gcc::context *ctxt)
 224     : simple_ipa_opt_pass (pass_data_ipa_oacc, ctxt)
 225   {}
 226
 227   /* opt_pass methods: */
 228   bool gate (function *) final override
 229   {
 230     return (optimize
 231             && flag_openacc
 232             /* Don't bother doing anything if the program has errors.  */
 233             && !seen_error ());
 234   }
 235
 236 }; // class pass_ipa_oacc
 237
 238 } // anon namespace
 239
 240 simple_ipa_opt_pass *
 241 make_pass_ipa_oacc (gcc::context *ctxt)
 242 {
 243   return new pass_ipa_oacc (ctxt);
 244 }
 245
 246 /* The ipa oacc kernels pass.  */
 247
 248 namespace {
 249
 250 const pass_data pass_data_ipa_oacc_kernels =
 251 {
 252   SIMPLE_IPA_PASS, /* type */
 253   "ipa_oacc_kernels", /* name */
 254   OPTGROUP_LOOP, /* optinfo_flags */
 255   TV_TREE_LOOP, /* tv_id */
 256   PROP_cfg, /* properties_required */
 257   0, /* properties_provided */
 258   0, /* properties_destroyed */
 259   0, /* todo_flags_start */
 260   0, /* todo_flags_finish */
 261 };
 262
 263 class pass_ipa_oacc_kernels : public simple_ipa_opt_pass
 264 {
 265 public:
 266   pass_ipa_oacc_kernels (gcc::context *ctxt)
 267     : simple_ipa_opt_pass (pass_data_ipa_oacc_kernels, ctxt)
 268   {}
 269
 270 }; // class pass_ipa_oacc_kernels
 271
 272 } // anon namespace
 273
 274 simple_ipa_opt_pass *
 275 make_pass_ipa_oacc_kernels (gcc::context *ctxt)
 276 {
 277   return new pass_ipa_oacc_kernels (ctxt);
 278 }
 279
 280 /* The no-loop superpass.  */
 281
 282 namespace {
 283
 284 const pass_data pass_data_tree_no_loop =
 285 {
 286   GIMPLE_PASS, /* type */
 287   "no_loop", /* name */
 288   OPTGROUP_NONE, /* optinfo_flags */
 289   TV_TREE_NOLOOP, /* tv_id */
 290   PROP_cfg, /* properties_required */
 291   0, /* properties_provided */
 292   0, /* properties_destroyed */
 293   0, /* todo_flags_start */
 294   0, /* todo_flags_finish */
 295 };
 296
 297 class pass_tree_no_loop : public gimple_opt_pass
 298 {
 299 public:
 300   pass_tree_no_loop (gcc::context *ctxt)
 301     : gimple_opt_pass (pass_data_tree_no_loop, ctxt)
 302   {}
 303
 304   /* opt_pass methods: */
 305   bool gate (function *fn) final override { return !gate_loop (fn); }
 306
 307 }; // class pass_tree_no_loop
 308
 309 } // anon namespace
 310
 311 gimple_opt_pass *
 312 make_pass_tree_no_loop (gcc::context *ctxt)
 313 {
 314   return new pass_tree_no_loop (ctxt);
 315 }
 316
 317
 318 /* Loop optimizer initialization.  */
 319
 320 namespace {
 321
 322 const pass_data pass_data_tree_loop_init =
 323 {
 324   GIMPLE_PASS, /* type */
 325   "loopinit", /* name */
 326   OPTGROUP_LOOP, /* optinfo_flags */
 327   TV_NONE, /* tv_id */
 328   PROP_cfg, /* properties_required */
 329   0, /* properties_provided */
 330   0, /* properties_destroyed */
 331   TODO_update_address_taken, /* todo_flags_start */
 332   0, /* todo_flags_finish */
 333 };
 334
 335 class pass_tree_loop_init : public gimple_opt_pass
 336 {
 337 public:
 338   pass_tree_loop_init (gcc::context *ctxt)
 339     : gimple_opt_pass (pass_data_tree_loop_init, ctxt)
 340   {}
 341
 342   /* opt_pass methods: */
 343   unsigned int execute (function *) final override;
 344
 345 }; // class pass_tree_loop_init
 346
 347 unsigned int
 348 pass_tree_loop_init::execute (function *fun ATTRIBUTE_UNUSED)
 349 {
 350   /* When processing a loop in the loop pipeline, we should be able to assert
 351      that:
 352        (loops_state_satisfies_p (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS
 353                                               | LOOP_CLOSED_SSA)
 354         && scev_initialized_p ())
 355   */
 356   loop_optimizer_init (LOOPS_NORMAL
 357                        | LOOPS_HAVE_RECORDED_EXITS);
 358   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
 359   scev_initialize ();
 360
 361   return 0;
 362 }
 363
 364 } // anon namespace
 365
 366 gimple_opt_pass *
 367 make_pass_tree_loop_init (gcc::context *ctxt)
 368 {
 369   return new pass_tree_loop_init (ctxt);
 370 }
 371
 372 /* Propagation of constants using scev.  */
 373
 374 namespace {
 375
 376 const pass_data pass_data_scev_cprop =
 377 {
 378   GIMPLE_PASS, /* type */
 379   "sccp", /* name */
 380   OPTGROUP_LOOP, /* optinfo_flags */
 381   TV_SCEV_CONST, /* tv_id */
 382   ( PROP_cfg | PROP_ssa ), /* properties_required */
 383   0, /* properties_provided */
 384   0, /* properties_destroyed */
 385   0, /* todo_flags_start */
 386   0, /* todo_flags_finish */
 387 };
 388
 389 class pass_scev_cprop : public gimple_opt_pass
 390 {
 391 public:
 392   pass_scev_cprop (gcc::context *ctxt)
 393     : gimple_opt_pass (pass_data_scev_cprop, ctxt)
 394   {}
 395
 396   /* opt_pass methods: */
 397   bool gate (function *) final override { return flag_tree_scev_cprop; }
 398   unsigned int execute (function *) final override;
 399
 400 }; // class pass_scev_cprop
 401
 402 unsigned
 403 pass_scev_cprop::execute (function *)
 404 {
 405   bool any = false;
 406
 407   /* Perform final value replacement in loops, in case the replacement
 408      expressions are cheap.  */
 409   for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
 410     any |= final_value_replacement_loop (loop);
 411
 412   return any ? TODO_cleanup_cfg | TODO_update_ssa_only_virtuals : 0;
 413 }
 414
 415 } // anon namespace
 416
 417 gimple_opt_pass *
 418 make_pass_scev_cprop (gcc::context *ctxt)
 419 {
 420   return new pass_scev_cprop (ctxt);
 421 }
 422
 423 /* Induction variable optimizations.  */
 424
 425 namespace {
 426
 427 const pass_data pass_data_iv_optimize =
 428 {
 429   GIMPLE_PASS, /* type */
 430   "ivopts", /* name */
 431   OPTGROUP_LOOP, /* optinfo_flags */
 432   TV_TREE_LOOP_IVOPTS, /* tv_id */
 433   ( PROP_cfg | PROP_ssa ), /* properties_required */
 434   0, /* properties_provided */
 435   0, /* properties_destroyed */
 436   0, /* todo_flags_start */
 437   TODO_update_ssa, /* todo_flags_finish */
 438 };
 439
 440 class pass_iv_optimize : public gimple_opt_pass
 441 {
 442 public:
 443   pass_iv_optimize (gcc::context *ctxt)
 444     : gimple_opt_pass (pass_data_iv_optimize, ctxt)
 445   {}
 446
 447   /* opt_pass methods: */
 448   bool gate (function *) final override { return flag_ivopts != 0; }
 449   unsigned int execute (function *) final override;
 450
 451 }; // class pass_iv_optimize
 452
 453 unsigned int
 454 pass_iv_optimize::execute (function *fun)
 455 {
 456   if (number_of_loops (fun) <= 1)
 457     return 0;
 458
 459   tree_ssa_iv_optimize ();
 460   return 0;
 461 }
 462
 463 } // anon namespace
 464
 465 gimple_opt_pass *
 466 make_pass_iv_optimize (gcc::context *ctxt)
 467 {
 468   return new pass_iv_optimize (ctxt);
 469 }
 470
 471 /* Loop optimizer finalization.  */
 472
 473 static unsigned int
 474 tree_ssa_loop_done (void)
 475 {
 476   free_numbers_of_iterations_estimates (cfun);
 477   scev_finalize ();
 478   loop_optimizer_finalize (cfun, true);
 479   return 0;
 480 }
 481
 482 namespace {
 483
 484 const pass_data pass_data_tree_loop_done =
 485 {
 486   GIMPLE_PASS, /* type */
 487   "loopdone", /* name */
 488   OPTGROUP_LOOP, /* optinfo_flags */
 489   TV_NONE, /* tv_id */
 490   PROP_cfg, /* properties_required */
 491   PROP_loop_opts_done, /* properties_provided */
 492   0, /* properties_destroyed */
 493   0, /* todo_flags_start */
 494   TODO_cleanup_cfg, /* todo_flags_finish */
 495 };
 496
 497 class pass_tree_loop_done : public gimple_opt_pass
 498 {
 499 public:
 500   pass_tree_loop_done (gcc::context *ctxt)
 501     : gimple_opt_pass (pass_data_tree_loop_done, ctxt)
 502   {}
 503
 504   /* opt_pass methods: */
 505   unsigned int execute (function *) final override
 506   {
 507     return tree_ssa_loop_done ();
 508   }
 509
 510 }; // class pass_tree_loop_done
 511
 512 } // anon namespace
 513
 514 gimple_opt_pass *
 515 make_pass_tree_loop_done (gcc::context *ctxt)
 516 {
 517   return new pass_tree_loop_done (ctxt);
 518 }
 519
 520 /* Calls CBCK for each index in memory reference ADDR_P.  There are two
 521    kinds situations handled; in each of these cases, the memory reference
 522    and DATA are passed to the callback:
 523
 524    Access to an array: ARRAY_{RANGE_}REF (base, index).  In this case we also
 525    pass the pointer to the index to the callback.
 526
 527    Pointer dereference: INDIRECT_REF (addr).  In this case we also pass the
 528    pointer to addr to the callback.
 529
 530    If the callback returns false, the whole search stops and false is returned.
 531    Otherwise the function returns true after traversing through the whole
 532    reference *ADDR_P.  */
 533
 534 bool
 535 for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
 536 {
 537   tree *nxt, *idx;
 538
 539   for (; ; addr_p = nxt)
 540     {
 541       switch (TREE_CODE (*addr_p))
 542         {
 543         case SSA_NAME:
 544           return cbck (*addr_p, addr_p, data);
 545
 546         case MEM_REF:
 547           nxt = &TREE_OPERAND (*addr_p, 0);
 548           return cbck (*addr_p, nxt, data);
 549
 550         case BIT_FIELD_REF:
 551         case VIEW_CONVERT_EXPR:
 552         case REALPART_EXPR:
 553         case IMAGPART_EXPR:
 554           nxt = &TREE_OPERAND (*addr_p, 0);
 555           break;
 556
 557         case COMPONENT_REF:
 558           /* If the component has varying offset, it behaves like index
 559              as well.  */
 560           idx = &TREE_OPERAND (*addr_p, 2);
 561           if (*idx
 562               && !cbck (*addr_p, idx, data))
 563             return false;
 564
 565           nxt = &TREE_OPERAND (*addr_p, 0);
 566           break;
 567
 568         case ARRAY_REF:
 569         case ARRAY_RANGE_REF:
 570           nxt = &TREE_OPERAND (*addr_p, 0);
 571           if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
 572             return false;
 573           break;
 574
 575         case CONSTRUCTOR:
 576           return true;
 577
 578         case ADDR_EXPR:
 579           gcc_assert (is_gimple_min_invariant (*addr_p));
 580           return true;
 581
 582         case TARGET_MEM_REF:
 583           idx = &TMR_BASE (*addr_p);
 584           if (*idx
 585               && !cbck (*addr_p, idx, data))
 586             return false;
 587           idx = &TMR_INDEX (*addr_p);
 588           if (*idx
 589               && !cbck (*addr_p, idx, data))
 590             return false;
 591           idx = &TMR_INDEX2 (*addr_p);
 592           if (*idx
 593               && !cbck (*addr_p, idx, data))
 594             return false;
 595           return true;
 596
 597         default:
 598           if (DECL_P (*addr_p)
 599               || CONSTANT_CLASS_P (*addr_p))
 600             return true;
 601           gcc_unreachable ();
 602         }
 603     }
 604 }
 605
 606
 607 /* The name and the length of the currently generated variable
 608    for lsm.  */
 609 #define MAX_LSM_NAME_LENGTH 40
 610 static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
 611 static int lsm_tmp_name_length;
 612
 613 /* Adds S to lsm_tmp_name.  */
 614
 615 static void
 616 lsm_tmp_name_add (const char *s)
 617 {
 618   int l = strlen (s) + lsm_tmp_name_length;
 619   if (l > MAX_LSM_NAME_LENGTH)
 620     return;
 621
 622   strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
 623   lsm_tmp_name_length = l;
 624 }
 625
 626 /* Stores the name for temporary variable that replaces REF to
 627    lsm_tmp_name.  */
 628
 629 static void
 630 gen_lsm_tmp_name (tree ref)
 631 {
 632   const char *name;
 633
 634   switch (TREE_CODE (ref))
 635     {
 636     case MEM_REF:
 637     case TARGET_MEM_REF:
 638       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 639       lsm_tmp_name_add ("_");
 640       break;
 641
 642     case ADDR_EXPR:
 643       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 644       break;
 645
 646     case BIT_FIELD_REF:
 647     case VIEW_CONVERT_EXPR:
 648     case ARRAY_RANGE_REF:
 649       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 650       break;
 651
 652     case REALPART_EXPR:
 653       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 654       lsm_tmp_name_add ("_RE");
 655       break;
 656
 657     case IMAGPART_EXPR:
 658       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 659       lsm_tmp_name_add ("_IM");
 660       break;
 661
 662     case COMPONENT_REF:
 663       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 664       lsm_tmp_name_add ("_");
 665       name = get_name (TREE_OPERAND (ref, 1));
 666       if (!name)
 667         name = "F";
 668       lsm_tmp_name_add (name);
 669       break;
 670
 671     case ARRAY_REF:
 672       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 673       lsm_tmp_name_add ("_I");
 674       break;
 675
 676     case SSA_NAME:
 677     case VAR_DECL:
 678     case PARM_DECL:
 679     case FUNCTION_DECL:
 680     case LABEL_DECL:
 681       name = get_name (ref);
 682       if (!name)
 683         name = "D";
 684       lsm_tmp_name_add (name);
 685       break;
 686
 687     case STRING_CST:
 688       lsm_tmp_name_add ("S");
 689       break;
 690
 691     case RESULT_DECL:
 692       lsm_tmp_name_add ("R");
 693       break;
 694
 695     case INTEGER_CST:
 696     default:
 697       /* Nothing.  */
 698       break;
 699     }
 700 }
 701
 702 /* Determines name for temporary variable that replaces REF.
 703    The name is accumulated into the lsm_tmp_name variable.
 704    N is added to the name of the temporary.  */
 705
 706 char *
 707 get_lsm_tmp_name (tree ref, unsigned n, const char *suffix)
 708 {
 709   char ns[2];
 710
 711   lsm_tmp_name_length = 0;
 712   gen_lsm_tmp_name (ref);
 713   lsm_tmp_name_add ("_lsm");
 714   if (n < 10)
 715     {
 716       ns[0] = '0' + n;
 717       ns[1] = 0;
 718       lsm_tmp_name_add (ns);
 719     }
 720   if (suffix != NULL)
 721     lsm_tmp_name_add (suffix);
 722   return lsm_tmp_name;
 723 }
 724
 725 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS.  */
 726
 727 unsigned
 728 tree_num_loop_insns (class loop *loop, eni_weights *weights)
 729 {
 730   basic_block *body = get_loop_body (loop);
 731   gimple_stmt_iterator gsi;
 732   unsigned size = 0, i;
 733
 734   for (i = 0; i < loop->num_nodes; i++)
 735     for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
 736       size += estimate_num_insns (gsi_stmt (gsi), weights);
 737   free (body);
 738
 739   return size;
 740 }
 741
 742
 743