1 /* Loop optimizations over tree-ssa. 2 Copyright (C) 2003-2018 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 struct loop *loop; 161 FOR_EACH_LOOP (loop, 0) 162 if (loop->in_oacc_kernels_region) 163 return true; 164 165 return false; 166 } 167 168 /* The oacc kernels superpass. */ 169 170 namespace { 171 172 const pass_data pass_data_oacc_kernels = 173 { 174 GIMPLE_PASS, /* type */ 175 "oacc_kernels", /* name */ 176 OPTGROUP_LOOP, /* optinfo_flags */ 177 TV_TREE_LOOP, /* tv_id */ 178 PROP_cfg, /* properties_required */ 179 0, /* properties_provided */ 180 0, /* properties_destroyed */ 181 0, /* todo_flags_start */ 182 0, /* todo_flags_finish */ 183 }; 184 185 class pass_oacc_kernels : public gimple_opt_pass 186 { 187 public: 188 pass_oacc_kernels (gcc::context *ctxt) 189 : gimple_opt_pass (pass_data_oacc_kernels, ctxt) 190 {} 191 192 /* opt_pass methods: */ 193 virtual bool gate (function *fn) { return gate_oacc_kernels (fn); } 194 195 }; // class pass_oacc_kernels 196 197 } // anon namespace 198 199 gimple_opt_pass * 200 make_pass_oacc_kernels (gcc::context *ctxt) 201 { 202 return new pass_oacc_kernels (ctxt); 203 } 204 205 /* The ipa oacc superpass. */ 206 207 namespace { 208 209 const pass_data pass_data_ipa_oacc = 210 { 211 SIMPLE_IPA_PASS, /* type */ 212 "ipa_oacc", /* name */ 213 OPTGROUP_LOOP, /* optinfo_flags */ 214 TV_TREE_LOOP, /* tv_id */ 215 PROP_cfg, /* properties_required */ 216 0, /* properties_provided */ 217 0, /* properties_destroyed */ 218 0, /* todo_flags_start */ 219 0, /* todo_flags_finish */ 220 }; 221 222 class pass_ipa_oacc : public simple_ipa_opt_pass 223 { 224 public: 225 pass_ipa_oacc (gcc::context *ctxt) 226 : simple_ipa_opt_pass (pass_data_ipa_oacc, ctxt) 227 {} 228 229 /* opt_pass methods: */ 230 virtual bool gate (function *) 231 { 232 return (optimize 233 && flag_openacc 234 /* Don't bother doing anything if the program has errors. */ 235 && !seen_error ()); 236 } 237 238 }; // class pass_ipa_oacc 239 240 } // anon namespace 241 242 simple_ipa_opt_pass * 243 make_pass_ipa_oacc (gcc::context *ctxt) 244 { 245 return new pass_ipa_oacc (ctxt); 246 } 247 248 /* The ipa oacc kernels pass. */ 249 250 namespace { 251 252 const pass_data pass_data_ipa_oacc_kernels = 253 { 254 SIMPLE_IPA_PASS, /* type */ 255 "ipa_oacc_kernels", /* name */ 256 OPTGROUP_LOOP, /* optinfo_flags */ 257 TV_TREE_LOOP, /* tv_id */ 258 PROP_cfg, /* properties_required */ 259 0, /* properties_provided */ 260 0, /* properties_destroyed */ 261 0, /* todo_flags_start */ 262 0, /* todo_flags_finish */ 263 }; 264 265 class pass_ipa_oacc_kernels : public simple_ipa_opt_pass 266 { 267 public: 268 pass_ipa_oacc_kernels (gcc::context *ctxt) 269 : simple_ipa_opt_pass (pass_data_ipa_oacc_kernels, ctxt) 270 {} 271 272 }; // class pass_ipa_oacc_kernels 273 274 } // anon namespace 275 276 simple_ipa_opt_pass * 277 make_pass_ipa_oacc_kernels (gcc::context *ctxt) 278 { 279 return new pass_ipa_oacc_kernels (ctxt); 280 } 281 282 /* The no-loop superpass. */ 283 284 namespace { 285 286 const pass_data pass_data_tree_no_loop = 287 { 288 GIMPLE_PASS, /* type */ 289 "no_loop", /* name */ 290 OPTGROUP_NONE, /* optinfo_flags */ 291 TV_TREE_NOLOOP, /* tv_id */ 292 PROP_cfg, /* properties_required */ 293 0, /* properties_provided */ 294 0, /* properties_destroyed */ 295 0, /* todo_flags_start */ 296 0, /* todo_flags_finish */ 297 }; 298 299 class pass_tree_no_loop : public gimple_opt_pass 300 { 301 public: 302 pass_tree_no_loop (gcc::context *ctxt) 303 : gimple_opt_pass (pass_data_tree_no_loop, ctxt) 304 {} 305 306 /* opt_pass methods: */ 307 virtual bool gate (function *fn) { return !gate_loop (fn); } 308 309 }; // class pass_tree_no_loop 310 311 } // anon namespace 312 313 gimple_opt_pass * 314 make_pass_tree_no_loop (gcc::context *ctxt) 315 { 316 return new pass_tree_no_loop (ctxt); 317 } 318 319 320 /* Loop optimizer initialization. */ 321 322 namespace { 323 324 const pass_data pass_data_tree_loop_init = 325 { 326 GIMPLE_PASS, /* type */ 327 "loopinit", /* name */ 328 OPTGROUP_LOOP, /* optinfo_flags */ 329 TV_NONE, /* tv_id */ 330 PROP_cfg, /* properties_required */ 331 0, /* properties_provided */ 332 0, /* properties_destroyed */ 333 0, /* todo_flags_start */ 334 0, /* todo_flags_finish */ 335 }; 336 337 class pass_tree_loop_init : public gimple_opt_pass 338 { 339 public: 340 pass_tree_loop_init (gcc::context *ctxt) 341 : gimple_opt_pass (pass_data_tree_loop_init, ctxt) 342 {} 343 344 /* opt_pass methods: */ 345 virtual unsigned int execute (function *); 346 347 }; // class pass_tree_loop_init 348 349 unsigned int 350 pass_tree_loop_init::execute (function *fun ATTRIBUTE_UNUSED) 351 { 352 /* When processing a loop in the loop pipeline, we should be able to assert 353 that: 354 (loops_state_satisfies_p (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS 355 | LOOP_CLOSED_SSA) 356 && scev_initialized_p ()) 357 */ 358 loop_optimizer_init (LOOPS_NORMAL 359 | LOOPS_HAVE_RECORDED_EXITS); 360 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); 361 scev_initialize (); 362 363 return 0; 364 } 365 366 } // anon namespace 367 368 gimple_opt_pass * 369 make_pass_tree_loop_init (gcc::context *ctxt) 370 { 371 return new pass_tree_loop_init (ctxt); 372 } 373 374 /* Loop autovectorization. */ 375 376 namespace { 377 378 const pass_data pass_data_vectorize = 379 { 380 GIMPLE_PASS, /* type */ 381 "vect", /* name */ 382 OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */ 383 TV_TREE_VECTORIZATION, /* tv_id */ 384 ( PROP_cfg | PROP_ssa ), /* properties_required */ 385 0, /* properties_provided */ 386 0, /* properties_destroyed */ 387 0, /* todo_flags_start */ 388 0, /* todo_flags_finish */ 389 }; 390 391 class pass_vectorize : public gimple_opt_pass 392 { 393 public: 394 pass_vectorize (gcc::context *ctxt) 395 : gimple_opt_pass (pass_data_vectorize, ctxt) 396 {} 397 398 /* opt_pass methods: */ 399 virtual bool gate (function *fun) 400 { 401 return flag_tree_loop_vectorize || fun->has_force_vectorize_loops; 402 } 403 404 virtual unsigned int execute (function *); 405 406 }; // class pass_vectorize 407 408 unsigned int 409 pass_vectorize::execute (function *fun) 410 { 411 if (number_of_loops (fun) <= 1) 412 return 0; 413 414 return vectorize_loops (); 415 } 416 417 } // anon namespace 418 419 gimple_opt_pass * 420 make_pass_vectorize (gcc::context *ctxt) 421 { 422 return new pass_vectorize (ctxt); 423 } 424 425 /* Propagation of constants using scev. */ 426 427 namespace { 428 429 const pass_data pass_data_scev_cprop = 430 { 431 GIMPLE_PASS, /* type */ 432 "sccp", /* name */ 433 OPTGROUP_LOOP, /* optinfo_flags */ 434 TV_SCEV_CONST, /* tv_id */ 435 ( PROP_cfg | PROP_ssa ), /* properties_required */ 436 0, /* properties_provided */ 437 0, /* properties_destroyed */ 438 0, /* todo_flags_start */ 439 ( TODO_cleanup_cfg 440 | TODO_update_ssa_only_virtuals ), /* todo_flags_finish */ 441 }; 442 443 class pass_scev_cprop : public gimple_opt_pass 444 { 445 public: 446 pass_scev_cprop (gcc::context *ctxt) 447 : gimple_opt_pass (pass_data_scev_cprop, ctxt) 448 {} 449 450 /* opt_pass methods: */ 451 virtual bool gate (function *) { return flag_tree_scev_cprop; } 452 virtual unsigned int execute (function *) { return scev_const_prop (); } 453 454 }; // class pass_scev_cprop 455 456 } // anon namespace 457 458 gimple_opt_pass * 459 make_pass_scev_cprop (gcc::context *ctxt) 460 { 461 return new pass_scev_cprop (ctxt); 462 } 463 464 /* Induction variable optimizations. */ 465 466 namespace { 467 468 const pass_data pass_data_iv_optimize = 469 { 470 GIMPLE_PASS, /* type */ 471 "ivopts", /* name */ 472 OPTGROUP_LOOP, /* optinfo_flags */ 473 TV_TREE_LOOP_IVOPTS, /* tv_id */ 474 ( PROP_cfg | PROP_ssa ), /* properties_required */ 475 0, /* properties_provided */ 476 0, /* properties_destroyed */ 477 0, /* todo_flags_start */ 478 TODO_update_ssa, /* todo_flags_finish */ 479 }; 480 481 class pass_iv_optimize : public gimple_opt_pass 482 { 483 public: 484 pass_iv_optimize (gcc::context *ctxt) 485 : gimple_opt_pass (pass_data_iv_optimize, ctxt) 486 {} 487 488 /* opt_pass methods: */ 489 virtual bool gate (function *) { return flag_ivopts != 0; } 490 virtual unsigned int execute (function *); 491 492 }; // class pass_iv_optimize 493 494 unsigned int 495 pass_iv_optimize::execute (function *fun) 496 { 497 if (number_of_loops (fun) <= 1) 498 return 0; 499 500 tree_ssa_iv_optimize (); 501 return 0; 502 } 503 504 } // anon namespace 505 506 gimple_opt_pass * 507 make_pass_iv_optimize (gcc::context *ctxt) 508 { 509 return new pass_iv_optimize (ctxt); 510 } 511 512 /* Loop optimizer finalization. */ 513 514 static unsigned int 515 tree_ssa_loop_done (void) 516 { 517 free_numbers_of_iterations_estimates (cfun); 518 scev_finalize (); 519 loop_optimizer_finalize (); 520 return 0; 521 } 522 523 namespace { 524 525 const pass_data pass_data_tree_loop_done = 526 { 527 GIMPLE_PASS, /* type */ 528 "loopdone", /* name */ 529 OPTGROUP_LOOP, /* optinfo_flags */ 530 TV_NONE, /* tv_id */ 531 PROP_cfg, /* properties_required */ 532 0, /* properties_provided */ 533 0, /* properties_destroyed */ 534 0, /* todo_flags_start */ 535 TODO_cleanup_cfg, /* todo_flags_finish */ 536 }; 537 538 class pass_tree_loop_done : public gimple_opt_pass 539 { 540 public: 541 pass_tree_loop_done (gcc::context *ctxt) 542 : gimple_opt_pass (pass_data_tree_loop_done, ctxt) 543 {} 544 545 /* opt_pass methods: */ 546 virtual unsigned int execute (function *) { return tree_ssa_loop_done (); } 547 548 }; // class pass_tree_loop_done 549 550 } // anon namespace 551 552 gimple_opt_pass * 553 make_pass_tree_loop_done (gcc::context *ctxt) 554 { 555 return new pass_tree_loop_done (ctxt); 556 } 557 558 /* Calls CBCK for each index in memory reference ADDR_P. There are two 559 kinds situations handled; in each of these cases, the memory reference 560 and DATA are passed to the callback: 561 562 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also 563 pass the pointer to the index to the callback. 564 565 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the 566 pointer to addr to the callback. 567 568 If the callback returns false, the whole search stops and false is returned. 569 Otherwise the function returns true after traversing through the whole 570 reference *ADDR_P. */ 571 572 bool 573 for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data) 574 { 575 tree *nxt, *idx; 576 577 for (; ; addr_p = nxt) 578 { 579 switch (TREE_CODE (*addr_p)) 580 { 581 case SSA_NAME: 582 return cbck (*addr_p, addr_p, data); 583 584 case MEM_REF: 585 nxt = &TREE_OPERAND (*addr_p, 0); 586 return cbck (*addr_p, nxt, data); 587 588 case BIT_FIELD_REF: 589 case VIEW_CONVERT_EXPR: 590 case REALPART_EXPR: 591 case IMAGPART_EXPR: 592 nxt = &TREE_OPERAND (*addr_p, 0); 593 break; 594 595 case COMPONENT_REF: 596 /* If the component has varying offset, it behaves like index 597 as well. */ 598 idx = &TREE_OPERAND (*addr_p, 2); 599 if (*idx 600 && !cbck (*addr_p, idx, data)) 601 return false; 602 603 nxt = &TREE_OPERAND (*addr_p, 0); 604 break; 605 606 case ARRAY_REF: 607 case ARRAY_RANGE_REF: 608 nxt = &TREE_OPERAND (*addr_p, 0); 609 if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data)) 610 return false; 611 break; 612 613 case VAR_DECL: 614 case PARM_DECL: 615 case CONST_DECL: 616 case STRING_CST: 617 case RESULT_DECL: 618 case VECTOR_CST: 619 case COMPLEX_CST: 620 case INTEGER_CST: 621 case POLY_INT_CST: 622 case REAL_CST: 623 case FIXED_CST: 624 case CONSTRUCTOR: 625 return true; 626 627 case ADDR_EXPR: 628 gcc_assert (is_gimple_min_invariant (*addr_p)); 629 return true; 630 631 case TARGET_MEM_REF: 632 idx = &TMR_BASE (*addr_p); 633 if (*idx 634 && !cbck (*addr_p, idx, data)) 635 return false; 636 idx = &TMR_INDEX (*addr_p); 637 if (*idx 638 && !cbck (*addr_p, idx, data)) 639 return false; 640 idx = &TMR_INDEX2 (*addr_p); 641 if (*idx 642 && !cbck (*addr_p, idx, data)) 643 return false; 644 return true; 645 646 default: 647 gcc_unreachable (); 648 } 649 } 650 } 651 652 653 /* The name and the length of the currently generated variable 654 for lsm. */ 655 #define MAX_LSM_NAME_LENGTH 40 656 static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1]; 657 static int lsm_tmp_name_length; 658 659 /* Adds S to lsm_tmp_name. */ 660 661 static void 662 lsm_tmp_name_add (const char *s) 663 { 664 int l = strlen (s) + lsm_tmp_name_length; 665 if (l > MAX_LSM_NAME_LENGTH) 666 return; 667 668 strcpy (lsm_tmp_name + lsm_tmp_name_length, s); 669 lsm_tmp_name_length = l; 670 } 671 672 /* Stores the name for temporary variable that replaces REF to 673 lsm_tmp_name. */ 674 675 static void 676 gen_lsm_tmp_name (tree ref) 677 { 678 const char *name; 679 680 switch (TREE_CODE (ref)) 681 { 682 case MEM_REF: 683 case TARGET_MEM_REF: 684 gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); 685 lsm_tmp_name_add ("_"); 686 break; 687 688 case ADDR_EXPR: 689 gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); 690 break; 691 692 case BIT_FIELD_REF: 693 case VIEW_CONVERT_EXPR: 694 case ARRAY_RANGE_REF: 695 gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); 696 break; 697 698 case REALPART_EXPR: 699 gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); 700 lsm_tmp_name_add ("_RE"); 701 break; 702 703 case IMAGPART_EXPR: 704 gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); 705 lsm_tmp_name_add ("_IM"); 706 break; 707 708 case COMPONENT_REF: 709 gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); 710 lsm_tmp_name_add ("_"); 711 name = get_name (TREE_OPERAND (ref, 1)); 712 if (!name) 713 name = "F"; 714 lsm_tmp_name_add (name); 715 break; 716 717 case ARRAY_REF: 718 gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); 719 lsm_tmp_name_add ("_I"); 720 break; 721 722 case SSA_NAME: 723 case VAR_DECL: 724 case PARM_DECL: 725 case FUNCTION_DECL: 726 case LABEL_DECL: 727 name = get_name (ref); 728 if (!name) 729 name = "D"; 730 lsm_tmp_name_add (name); 731 break; 732 733 case STRING_CST: 734 lsm_tmp_name_add ("S"); 735 break; 736 737 case RESULT_DECL: 738 lsm_tmp_name_add ("R"); 739 break; 740 741 case INTEGER_CST: 742 default: 743 /* Nothing. */ 744 break; 745 } 746 } 747 748 /* Determines name for temporary variable that replaces REF. 749 The name is accumulated into the lsm_tmp_name variable. 750 N is added to the name of the temporary. */ 751 752 char * 753 get_lsm_tmp_name (tree ref, unsigned n, const char *suffix) 754 { 755 char ns[2]; 756 757 lsm_tmp_name_length = 0; 758 gen_lsm_tmp_name (ref); 759 lsm_tmp_name_add ("_lsm"); 760 if (n < 10) 761 { 762 ns[0] = '0' + n; 763 ns[1] = 0; 764 lsm_tmp_name_add (ns); 765 } 766 return lsm_tmp_name; 767 if (suffix != NULL) 768 lsm_tmp_name_add (suffix); 769 } 770 771 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */ 772 773 unsigned 774 tree_num_loop_insns (struct loop *loop, eni_weights *weights) 775 { 776 basic_block *body = get_loop_body (loop); 777 gimple_stmt_iterator gsi; 778 unsigned size = 0, i; 779 780 for (i = 0; i < loop->num_nodes; i++) 781 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi)) 782 size += estimate_num_insns (gsi_stmt (gsi), weights); 783 free (body); 784 785 return size; 786 } 787 788 789 790