gcc/tree-ssa-loop.c

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