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