gcc/tree-ssa-loop.c

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