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