gcc/tree-ssa-loop.cc

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