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