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)
 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   if (number_of_loops (fun) <= 1)
 182     return 0;
 183
 184   return 0;
 185 }
 186
 187 } // anon namespace
 188
 189 gimple_opt_pass *
 190 make_pass_tree_loop_init (gcc::context *ctxt)
 191 {
 192   return new pass_tree_loop_init (ctxt);
 193 }
 194
 195 /* Loop autovectorization.  */
 196
 197 namespace {
 198
 199 const pass_data pass_data_vectorize =
 200 {
 201   GIMPLE_PASS, /* type */
 202   "vect", /* name */
 203   OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */
 204   TV_TREE_VECTORIZATION, /* tv_id */
 205   ( PROP_cfg | PROP_ssa ), /* 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_vectorize : public gimple_opt_pass
 213 {
 214 public:
 215   pass_vectorize (gcc::context *ctxt)
 216     : gimple_opt_pass (pass_data_vectorize, ctxt)
 217   {}
 218
 219   /* opt_pass methods: */
 220   virtual bool gate (function *fun)
 221     {
 222       return flag_tree_loop_vectorize || fun->has_force_vectorize_loops;
 223     }
 224
 225   virtual unsigned int execute (function *);
 226
 227 }; // class pass_vectorize
 228
 229 unsigned int
 230 pass_vectorize::execute (function *fun)
 231 {
 232   if (number_of_loops (fun) <= 1)
 233     return 0;
 234
 235   return vectorize_loops ();
 236 }
 237
 238 } // anon namespace
 239
 240 gimple_opt_pass *
 241 make_pass_vectorize (gcc::context *ctxt)
 242 {
 243   return new pass_vectorize (ctxt);
 244 }
 245
 246 /* Check the correctness of the data dependence analyzers.  */
 247
 248 namespace {
 249
 250 const pass_data pass_data_check_data_deps =
 251 {
 252   GIMPLE_PASS, /* type */
 253   "ckdd", /* name */
 254   OPTGROUP_LOOP, /* optinfo_flags */
 255   TV_CHECK_DATA_DEPS, /* 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_check_data_deps : public gimple_opt_pass
 264 {
 265 public:
 266   pass_check_data_deps (gcc::context *ctxt)
 267     : gimple_opt_pass (pass_data_check_data_deps, ctxt)
 268   {}
 269
 270   /* opt_pass methods: */
 271   virtual bool gate (function *) { return flag_check_data_deps != 0; }
 272   virtual unsigned int execute (function *);
 273
 274 }; // class pass_check_data_deps
 275
 276 unsigned int
 277 pass_check_data_deps::execute (function *fun)
 278 {
 279   if (number_of_loops (fun) <= 1)
 280     return 0;
 281
 282   tree_check_data_deps ();
 283   return 0;
 284 }
 285
 286 } // anon namespace
 287
 288 gimple_opt_pass *
 289 make_pass_check_data_deps (gcc::context *ctxt)
 290 {
 291   return new pass_check_data_deps (ctxt);
 292 }
 293
 294 /* Propagation of constants using scev.  */
 295
 296 namespace {
 297
 298 const pass_data pass_data_scev_cprop =
 299 {
 300   GIMPLE_PASS, /* type */
 301   "sccp", /* name */
 302   OPTGROUP_LOOP, /* optinfo_flags */
 303   TV_SCEV_CONST, /* tv_id */
 304   ( PROP_cfg | PROP_ssa ), /* properties_required */
 305   0, /* properties_provided */
 306   0, /* properties_destroyed */
 307   0, /* todo_flags_start */
 308   ( TODO_cleanup_cfg
 309     | TODO_update_ssa_only_virtuals ), /* todo_flags_finish */
 310 };
 311
 312 class pass_scev_cprop : public gimple_opt_pass
 313 {
 314 public:
 315   pass_scev_cprop (gcc::context *ctxt)
 316     : gimple_opt_pass (pass_data_scev_cprop, ctxt)
 317   {}
 318
 319   /* opt_pass methods: */
 320   virtual bool gate (function *) { return flag_tree_scev_cprop; }
 321   virtual unsigned int execute (function *) { return scev_const_prop (); }
 322
 323 }; // class pass_scev_cprop
 324
 325 } // anon namespace
 326
 327 gimple_opt_pass *
 328 make_pass_scev_cprop (gcc::context *ctxt)
 329 {
 330   return new pass_scev_cprop (ctxt);
 331 }
 332
 333 /* Record bounds on numbers of iterations of loops.  */
 334
 335 namespace {
 336
 337 const pass_data pass_data_record_bounds =
 338 {
 339   GIMPLE_PASS, /* type */
 340   "*record_bounds", /* name */
 341   OPTGROUP_NONE, /* optinfo_flags */
 342   TV_TREE_LOOP_BOUNDS, /* tv_id */
 343   ( PROP_cfg | PROP_ssa ), /* properties_required */
 344   0, /* properties_provided */
 345   0, /* properties_destroyed */
 346   0, /* todo_flags_start */
 347   0, /* todo_flags_finish */
 348 };
 349
 350 class pass_record_bounds : public gimple_opt_pass
 351 {
 352 public:
 353   pass_record_bounds (gcc::context *ctxt)
 354     : gimple_opt_pass (pass_data_record_bounds, ctxt)
 355   {}
 356
 357   /* opt_pass methods: */
 358   virtual unsigned int execute (function *);
 359
 360 }; // class pass_record_bounds
 361
 362 unsigned int
 363 pass_record_bounds::execute (function *fun)
 364 {
 365   if (number_of_loops (fun) <= 1)
 366     return 0;
 367
 368   estimate_numbers_of_iterations ();
 369   scev_reset ();
 370   return 0;
 371 }
 372
 373 } // anon namespace
 374
 375 gimple_opt_pass *
 376 make_pass_record_bounds (gcc::context *ctxt)
 377 {
 378   return new pass_record_bounds (ctxt);
 379 }
 380
 381 /* Induction variable optimizations.  */
 382
 383 namespace {
 384
 385 const pass_data pass_data_iv_optimize =
 386 {
 387   GIMPLE_PASS, /* type */
 388   "ivopts", /* name */
 389   OPTGROUP_LOOP, /* optinfo_flags */
 390   TV_TREE_LOOP_IVOPTS, /* tv_id */
 391   ( PROP_cfg | PROP_ssa ), /* properties_required */
 392   0, /* properties_provided */
 393   0, /* properties_destroyed */
 394   0, /* todo_flags_start */
 395   TODO_update_ssa, /* todo_flags_finish */
 396 };
 397
 398 class pass_iv_optimize : public gimple_opt_pass
 399 {
 400 public:
 401   pass_iv_optimize (gcc::context *ctxt)
 402     : gimple_opt_pass (pass_data_iv_optimize, ctxt)
 403   {}
 404
 405   /* opt_pass methods: */
 406   virtual bool gate (function *) { return flag_ivopts != 0; }
 407   virtual unsigned int execute (function *);
 408
 409 }; // class pass_iv_optimize
 410
 411 unsigned int
 412 pass_iv_optimize::execute (function *fun)
 413 {
 414   if (number_of_loops (fun) <= 1)
 415     return 0;
 416
 417   tree_ssa_iv_optimize ();
 418   return 0;
 419 }
 420
 421 } // anon namespace
 422
 423 gimple_opt_pass *
 424 make_pass_iv_optimize (gcc::context *ctxt)
 425 {
 426   return new pass_iv_optimize (ctxt);
 427 }
 428
 429 /* Loop optimizer finalization.  */
 430
 431 static unsigned int
 432 tree_ssa_loop_done (void)
 433 {
 434   free_numbers_of_iterations_estimates ();
 435   scev_finalize ();
 436   loop_optimizer_finalize ();
 437   return 0;
 438 }
 439
 440 namespace {
 441
 442 const pass_data pass_data_tree_loop_done =
 443 {
 444   GIMPLE_PASS, /* type */
 445   "loopdone", /* name */
 446   OPTGROUP_LOOP, /* optinfo_flags */
 447   TV_NONE, /* tv_id */
 448   PROP_cfg, /* properties_required */
 449   0, /* properties_provided */
 450   0, /* properties_destroyed */
 451   0, /* todo_flags_start */
 452   TODO_cleanup_cfg, /* todo_flags_finish */
 453 };
 454
 455 class pass_tree_loop_done : public gimple_opt_pass
 456 {
 457 public:
 458   pass_tree_loop_done (gcc::context *ctxt)
 459     : gimple_opt_pass (pass_data_tree_loop_done, ctxt)
 460   {}
 461
 462   /* opt_pass methods: */
 463   virtual unsigned int execute (function *) { return tree_ssa_loop_done (); }
 464
 465 }; // class pass_tree_loop_done
 466
 467 } // anon namespace
 468
 469 gimple_opt_pass *
 470 make_pass_tree_loop_done (gcc::context *ctxt)
 471 {
 472   return new pass_tree_loop_done (ctxt);
 473 }
 474
 475 /* Calls CBCK for each index in memory reference ADDR_P.  There are two
 476    kinds situations handled; in each of these cases, the memory reference
 477    and DATA are passed to the callback:
 478
 479    Access to an array: ARRAY_{RANGE_}REF (base, index).  In this case we also
 480    pass the pointer to the index to the callback.
 481
 482    Pointer dereference: INDIRECT_REF (addr).  In this case we also pass the
 483    pointer to addr to the callback.
 484
 485    If the callback returns false, the whole search stops and false is returned.
 486    Otherwise the function returns true after traversing through the whole
 487    reference *ADDR_P.  */
 488
 489 bool
 490 for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
 491 {
 492   tree *nxt, *idx;
 493
 494   for (; ; addr_p = nxt)
 495     {
 496       switch (TREE_CODE (*addr_p))
 497         {
 498         case SSA_NAME:
 499           return cbck (*addr_p, addr_p, data);
 500
 501         case MEM_REF:
 502           nxt = &TREE_OPERAND (*addr_p, 0);
 503           return cbck (*addr_p, nxt, data);
 504
 505         case BIT_FIELD_REF:
 506         case VIEW_CONVERT_EXPR:
 507         case REALPART_EXPR:
 508         case IMAGPART_EXPR:
 509           nxt = &TREE_OPERAND (*addr_p, 0);
 510           break;
 511
 512         case COMPONENT_REF:
 513           /* If the component has varying offset, it behaves like index
 514              as well.  */
 515           idx = &TREE_OPERAND (*addr_p, 2);
 516           if (*idx
 517               && !cbck (*addr_p, idx, data))
 518             return false;
 519
 520           nxt = &TREE_OPERAND (*addr_p, 0);
 521           break;
 522
 523         case ARRAY_REF:
 524         case ARRAY_RANGE_REF:
 525           nxt = &TREE_OPERAND (*addr_p, 0);
 526           if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
 527             return false;
 528           break;
 529
 530         case VAR_DECL:
 531         case PARM_DECL:
 532         case CONST_DECL:
 533         case STRING_CST:
 534         case RESULT_DECL:
 535         case VECTOR_CST:
 536         case COMPLEX_CST:
 537         case INTEGER_CST:
 538         case REAL_CST:
 539         case FIXED_CST:
 540         case CONSTRUCTOR:
 541           return true;
 542
 543         case ADDR_EXPR:
 544           gcc_assert (is_gimple_min_invariant (*addr_p));
 545           return true;
 546
 547         case TARGET_MEM_REF:
 548           idx = &TMR_BASE (*addr_p);
 549           if (*idx
 550               && !cbck (*addr_p, idx, data))
 551             return false;
 552           idx = &TMR_INDEX (*addr_p);
 553           if (*idx
 554               && !cbck (*addr_p, idx, data))
 555             return false;
 556           idx = &TMR_INDEX2 (*addr_p);
 557           if (*idx
 558               && !cbck (*addr_p, idx, data))
 559             return false;
 560           return true;
 561
 562         default:
 563           gcc_unreachable ();
 564         }
 565     }
 566 }
 567
 568
 569 /* The name and the length of the currently generated variable
 570    for lsm.  */
 571 #define MAX_LSM_NAME_LENGTH 40
 572 static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
 573 static int lsm_tmp_name_length;
 574
 575 /* Adds S to lsm_tmp_name.  */
 576
 577 static void
 578 lsm_tmp_name_add (const char *s)
 579 {
 580   int l = strlen (s) + lsm_tmp_name_length;
 581   if (l > MAX_LSM_NAME_LENGTH)
 582     return;
 583
 584   strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
 585   lsm_tmp_name_length = l;
 586 }
 587
 588 /* Stores the name for temporary variable that replaces REF to
 589    lsm_tmp_name.  */
 590
 591 static void
 592 gen_lsm_tmp_name (tree ref)
 593 {
 594   const char *name;
 595
 596   switch (TREE_CODE (ref))
 597     {
 598     case MEM_REF:
 599     case TARGET_MEM_REF:
 600       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 601       lsm_tmp_name_add ("_");
 602       break;
 603
 604     case ADDR_EXPR:
 605       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 606       break;
 607
 608     case BIT_FIELD_REF:
 609     case VIEW_CONVERT_EXPR:
 610     case ARRAY_RANGE_REF:
 611       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 612       break;
 613
 614     case REALPART_EXPR:
 615       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 616       lsm_tmp_name_add ("_RE");
 617       break;
 618
 619     case IMAGPART_EXPR:
 620       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 621       lsm_tmp_name_add ("_IM");
 622       break;
 623
 624     case COMPONENT_REF:
 625       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 626       lsm_tmp_name_add ("_");
 627       name = get_name (TREE_OPERAND (ref, 1));
 628       if (!name)
 629         name = "F";
 630       lsm_tmp_name_add (name);
 631       break;
 632
 633     case ARRAY_REF:
 634       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 635       lsm_tmp_name_add ("_I");
 636       break;
 637
 638     case SSA_NAME:
 639     case VAR_DECL:
 640     case PARM_DECL:
 641       name = get_name (ref);
 642       if (!name)
 643         name = "D";
 644       lsm_tmp_name_add (name);
 645       break;
 646
 647     case STRING_CST:
 648       lsm_tmp_name_add ("S");
 649       break;
 650
 651     case RESULT_DECL:
 652       lsm_tmp_name_add ("R");
 653       break;
 654
 655     case INTEGER_CST:
 656       /* Nothing.  */
 657       break;
 658
 659     default:
 660       gcc_unreachable ();
 661     }
 662 }
 663
 664 /* Determines name for temporary variable that replaces REF.
 665    The name is accumulated into the lsm_tmp_name variable.
 666    N is added to the name of the temporary.  */
 667
 668 char *
 669 get_lsm_tmp_name (tree ref, unsigned n, const char *suffix)
 670 {
 671   char ns[2];
 672
 673   lsm_tmp_name_length = 0;
 674   gen_lsm_tmp_name (ref);
 675   lsm_tmp_name_add ("_lsm");
 676   if (n < 10)
 677     {
 678       ns[0] = '0' + n;
 679       ns[1] = 0;
 680       lsm_tmp_name_add (ns);
 681     }
 682   return lsm_tmp_name;
 683   if (suffix != NULL)
 684     lsm_tmp_name_add (suffix);
 685 }
 686
 687 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS.  */
 688
 689 unsigned
 690 tree_num_loop_insns (struct loop *loop, eni_weights *weights)
 691 {
 692   basic_block *body = get_loop_body (loop);
 693   gimple_stmt_iterator gsi;
 694   unsigned size = 0, i;
 695
 696   for (i = 0; i < loop->num_nodes; i++)
 697     for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
 698       size += estimate_num_insns (gsi_stmt (gsi), weights);
 699   free (body);
 700
 701   return size;
 702 }
 703
 704
 705