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