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