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