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