gcc/tree-ssa-loop.c

   1 /* Loop optimizations over tree-ssa.
   2    Copyright (C) 2003-2021 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   virtual bool gate (function *) { return flag_tree_loop_optimize; }
  71
  72   virtual unsigned int execute (function *fn);
  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   virtual bool gate (function *fn) { 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   virtual bool gate (function *fn) { 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   virtual bool gate (function *)
 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   virtual bool gate (function *fn) { 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   virtual unsigned int execute (function *);
 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   virtual bool gate (function *) { return flag_tree_scev_cprop; }
 399   virtual unsigned int execute (function *);
 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   virtual bool gate (function *) { return flag_ivopts != 0; }
 450   virtual unsigned int execute (function *);
 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   virtual unsigned int execute (function *) { return tree_ssa_loop_done (); }
 507
 508 }; // class pass_tree_loop_done
 509
 510 } // anon namespace
 511
 512 gimple_opt_pass *
 513 make_pass_tree_loop_done (gcc::context *ctxt)
 514 {
 515   return new pass_tree_loop_done (ctxt);
 516 }
 517
 518 /* Calls CBCK for each index in memory reference ADDR_P.  There are two
 519    kinds situations handled; in each of these cases, the memory reference
 520    and DATA are passed to the callback:
 521
 522    Access to an array: ARRAY_{RANGE_}REF (base, index).  In this case we also
 523    pass the pointer to the index to the callback.
 524
 525    Pointer dereference: INDIRECT_REF (addr).  In this case we also pass the
 526    pointer to addr to the callback.
 527
 528    If the callback returns false, the whole search stops and false is returned.
 529    Otherwise the function returns true after traversing through the whole
 530    reference *ADDR_P.  */
 531
 532 bool
 533 for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
 534 {
 535   tree *nxt, *idx;
 536
 537   for (; ; addr_p = nxt)
 538     {
 539       switch (TREE_CODE (*addr_p))
 540         {
 541         case SSA_NAME:
 542           return cbck (*addr_p, addr_p, data);
 543
 544         case MEM_REF:
 545           nxt = &TREE_OPERAND (*addr_p, 0);
 546           return cbck (*addr_p, nxt, data);
 547
 548         case BIT_FIELD_REF:
 549         case VIEW_CONVERT_EXPR:
 550         case REALPART_EXPR:
 551         case IMAGPART_EXPR:
 552           nxt = &TREE_OPERAND (*addr_p, 0);
 553           break;
 554
 555         case COMPONENT_REF:
 556           /* If the component has varying offset, it behaves like index
 557              as well.  */
 558           idx = &TREE_OPERAND (*addr_p, 2);
 559           if (*idx
 560               && !cbck (*addr_p, idx, data))
 561             return false;
 562
 563           nxt = &TREE_OPERAND (*addr_p, 0);
 564           break;
 565
 566         case ARRAY_REF:
 567         case ARRAY_RANGE_REF:
 568           nxt = &TREE_OPERAND (*addr_p, 0);
 569           if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
 570             return false;
 571           break;
 572
 573         case CONSTRUCTOR:
 574           return true;
 575
 576         case ADDR_EXPR:
 577           gcc_assert (is_gimple_min_invariant (*addr_p));
 578           return true;
 579
 580         case TARGET_MEM_REF:
 581           idx = &TMR_BASE (*addr_p);
 582           if (*idx
 583               && !cbck (*addr_p, idx, data))
 584             return false;
 585           idx = &TMR_INDEX (*addr_p);
 586           if (*idx
 587               && !cbck (*addr_p, idx, data))
 588             return false;
 589           idx = &TMR_INDEX2 (*addr_p);
 590           if (*idx
 591               && !cbck (*addr_p, idx, data))
 592             return false;
 593           return true;
 594
 595         default:
 596           if (DECL_P (*addr_p)
 597               || CONSTANT_CLASS_P (*addr_p))
 598             return true;
 599           gcc_unreachable ();
 600         }
 601     }
 602 }
 603
 604
 605 /* The name and the length of the currently generated variable
 606    for lsm.  */
 607 #define MAX_LSM_NAME_LENGTH 40
 608 static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
 609 static int lsm_tmp_name_length;
 610
 611 /* Adds S to lsm_tmp_name.  */
 612
 613 static void
 614 lsm_tmp_name_add (const char *s)
 615 {
 616   int l = strlen (s) + lsm_tmp_name_length;
 617   if (l > MAX_LSM_NAME_LENGTH)
 618     return;
 619
 620   strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
 621   lsm_tmp_name_length = l;
 622 }
 623
 624 /* Stores the name for temporary variable that replaces REF to
 625    lsm_tmp_name.  */
 626
 627 static void
 628 gen_lsm_tmp_name (tree ref)
 629 {
 630   const char *name;
 631
 632   switch (TREE_CODE (ref))
 633     {
 634     case MEM_REF:
 635     case TARGET_MEM_REF:
 636       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 637       lsm_tmp_name_add ("_");
 638       break;
 639
 640     case ADDR_EXPR:
 641       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 642       break;
 643
 644     case BIT_FIELD_REF:
 645     case VIEW_CONVERT_EXPR:
 646     case ARRAY_RANGE_REF:
 647       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 648       break;
 649
 650     case REALPART_EXPR:
 651       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 652       lsm_tmp_name_add ("_RE");
 653       break;
 654
 655     case IMAGPART_EXPR:
 656       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 657       lsm_tmp_name_add ("_IM");
 658       break;
 659
 660     case COMPONENT_REF:
 661       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 662       lsm_tmp_name_add ("_");
 663       name = get_name (TREE_OPERAND (ref, 1));
 664       if (!name)
 665         name = "F";
 666       lsm_tmp_name_add (name);
 667       break;
 668
 669     case ARRAY_REF:
 670       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 671       lsm_tmp_name_add ("_I");
 672       break;
 673
 674     case SSA_NAME:
 675     case VAR_DECL:
 676     case PARM_DECL:
 677     case FUNCTION_DECL:
 678     case LABEL_DECL:
 679       name = get_name (ref);
 680       if (!name)
 681         name = "D";
 682       lsm_tmp_name_add (name);
 683       break;
 684
 685     case STRING_CST:
 686       lsm_tmp_name_add ("S");
 687       break;
 688
 689     case RESULT_DECL:
 690       lsm_tmp_name_add ("R");
 691       break;
 692
 693     case INTEGER_CST:
 694     default:
 695       /* Nothing.  */
 696       break;
 697     }
 698 }
 699
 700 /* Determines name for temporary variable that replaces REF.
 701    The name is accumulated into the lsm_tmp_name variable.
 702    N is added to the name of the temporary.  */
 703
 704 char *
 705 get_lsm_tmp_name (tree ref, unsigned n, const char *suffix)
 706 {
 707   char ns[2];
 708
 709   lsm_tmp_name_length = 0;
 710   gen_lsm_tmp_name (ref);
 711   lsm_tmp_name_add ("_lsm");
 712   if (n < 10)
 713     {
 714       ns[0] = '0' + n;
 715       ns[1] = 0;
 716       lsm_tmp_name_add (ns);
 717     }
 718   if (suffix != NULL)
 719     lsm_tmp_name_add (suffix);
 720   return lsm_tmp_name;
 721 }
 722
 723 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS.  */
 724
 725 unsigned
 726 tree_num_loop_insns (class loop *loop, eni_weights *weights)
 727 {
 728   basic_block *body = get_loop_body (loop);
 729   gimple_stmt_iterator gsi;
 730   unsigned size = 0, i;
 731
 732   for (i = 0; i < loop->num_nodes; i++)
 733     for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
 734       size += estimate_num_insns (gsi_stmt (gsi), weights);
 735   free (body);
 736
 737   return size;
 738 }
 739
 740
 741