gcc/tree-ssa-loop.c

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