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 "hard-reg-set.h"
  27 #include "alias.h"
  28 #include "fold-const.h"
  29 #include "tm_p.h"
  30 #include "internal-fn.h"
  31 #include "gimple-iterator.h"
  32 #include "tree-ssa-loop-ivopts.h"
  33 #include "tree-ssa-loop-manip.h"
  34 #include "tree-ssa-loop-niter.h"
  35 #include "tree-ssa-loop.h"
  36 #include "tree-pass.h"
  37 #include "cfgloop.h"
  38 #include "flags.h"
  39 #include "tree-inline.h"
  40 #include "tree-scalar-evolution.h"
  41 #include "diagnostic-core.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 /* Check the correctness of the data dependence analyzers.  */
 290
 291 namespace {
 292
 293 const pass_data pass_data_check_data_deps =
 294 {
 295   GIMPLE_PASS, /* type */
 296   "ckdd", /* name */
 297   OPTGROUP_LOOP, /* optinfo_flags */
 298   TV_CHECK_DATA_DEPS, /* tv_id */
 299   ( PROP_cfg | PROP_ssa ), /* properties_required */
 300   0, /* properties_provided */
 301   0, /* properties_destroyed */
 302   0, /* todo_flags_start */
 303   0, /* todo_flags_finish */
 304 };
 305
 306 class pass_check_data_deps : public gimple_opt_pass
 307 {
 308 public:
 309   pass_check_data_deps (gcc::context *ctxt)
 310     : gimple_opt_pass (pass_data_check_data_deps, ctxt)
 311   {}
 312
 313   /* opt_pass methods: */
 314   virtual bool gate (function *) { return flag_check_data_deps != 0; }
 315   virtual unsigned int execute (function *);
 316
 317 }; // class pass_check_data_deps
 318
 319 unsigned int
 320 pass_check_data_deps::execute (function *fun)
 321 {
 322   if (number_of_loops (fun) <= 1)
 323     return 0;
 324
 325   tree_check_data_deps ();
 326   return 0;
 327 }
 328
 329 } // anon namespace
 330
 331 gimple_opt_pass *
 332 make_pass_check_data_deps (gcc::context *ctxt)
 333 {
 334   return new pass_check_data_deps (ctxt);
 335 }
 336
 337 /* Propagation of constants using scev.  */
 338
 339 namespace {
 340
 341 const pass_data pass_data_scev_cprop =
 342 {
 343   GIMPLE_PASS, /* type */
 344   "sccp", /* name */
 345   OPTGROUP_LOOP, /* optinfo_flags */
 346   TV_SCEV_CONST, /* tv_id */
 347   ( PROP_cfg | PROP_ssa ), /* properties_required */
 348   0, /* properties_provided */
 349   0, /* properties_destroyed */
 350   0, /* todo_flags_start */
 351   ( TODO_cleanup_cfg
 352     | TODO_update_ssa_only_virtuals ), /* todo_flags_finish */
 353 };
 354
 355 class pass_scev_cprop : public gimple_opt_pass
 356 {
 357 public:
 358   pass_scev_cprop (gcc::context *ctxt)
 359     : gimple_opt_pass (pass_data_scev_cprop, ctxt)
 360   {}
 361
 362   /* opt_pass methods: */
 363   virtual bool gate (function *) { return flag_tree_scev_cprop; }
 364   virtual unsigned int execute (function *) { return scev_const_prop (); }
 365
 366 }; // class pass_scev_cprop
 367
 368 } // anon namespace
 369
 370 gimple_opt_pass *
 371 make_pass_scev_cprop (gcc::context *ctxt)
 372 {
 373   return new pass_scev_cprop (ctxt);
 374 }
 375
 376 /* Record bounds on numbers of iterations of loops.  */
 377
 378 namespace {
 379
 380 const pass_data pass_data_record_bounds =
 381 {
 382   GIMPLE_PASS, /* type */
 383   "*record_bounds", /* name */
 384   OPTGROUP_NONE, /* optinfo_flags */
 385   TV_TREE_LOOP_BOUNDS, /* tv_id */
 386   ( PROP_cfg | PROP_ssa ), /* properties_required */
 387   0, /* properties_provided */
 388   0, /* properties_destroyed */
 389   0, /* todo_flags_start */
 390   0, /* todo_flags_finish */
 391 };
 392
 393 class pass_record_bounds : public gimple_opt_pass
 394 {
 395 public:
 396   pass_record_bounds (gcc::context *ctxt)
 397     : gimple_opt_pass (pass_data_record_bounds, ctxt)
 398   {}
 399
 400   /* opt_pass methods: */
 401   virtual unsigned int execute (function *);
 402
 403 }; // class pass_record_bounds
 404
 405 unsigned int
 406 pass_record_bounds::execute (function *fun)
 407 {
 408   if (number_of_loops (fun) <= 1)
 409     return 0;
 410
 411   estimate_numbers_of_iterations ();
 412   scev_reset ();
 413   return 0;
 414 }
 415
 416 } // anon namespace
 417
 418 gimple_opt_pass *
 419 make_pass_record_bounds (gcc::context *ctxt)
 420 {
 421   return new pass_record_bounds (ctxt);
 422 }
 423
 424 /* Induction variable optimizations.  */
 425
 426 namespace {
 427
 428 const pass_data pass_data_iv_optimize =
 429 {
 430   GIMPLE_PASS, /* type */
 431   "ivopts", /* name */
 432   OPTGROUP_LOOP, /* optinfo_flags */
 433   TV_TREE_LOOP_IVOPTS, /* tv_id */
 434   ( PROP_cfg | PROP_ssa ), /* properties_required */
 435   0, /* properties_provided */
 436   0, /* properties_destroyed */
 437   0, /* todo_flags_start */
 438   TODO_update_ssa, /* todo_flags_finish */
 439 };
 440
 441 class pass_iv_optimize : public gimple_opt_pass
 442 {
 443 public:
 444   pass_iv_optimize (gcc::context *ctxt)
 445     : gimple_opt_pass (pass_data_iv_optimize, ctxt)
 446   {}
 447
 448   /* opt_pass methods: */
 449   virtual bool gate (function *) { return flag_ivopts != 0; }
 450   virtual unsigned int execute (function *);
 451
 452 }; // class pass_iv_optimize
 453
 454 unsigned int
 455 pass_iv_optimize::execute (function *fun)
 456 {
 457   if (number_of_loops (fun) <= 1)
 458     return 0;
 459
 460   tree_ssa_iv_optimize ();
 461   return 0;
 462 }
 463
 464 } // anon namespace
 465
 466 gimple_opt_pass *
 467 make_pass_iv_optimize (gcc::context *ctxt)
 468 {
 469   return new pass_iv_optimize (ctxt);
 470 }
 471
 472 /* Loop optimizer finalization.  */
 473
 474 static unsigned int
 475 tree_ssa_loop_done (void)
 476 {
 477   free_numbers_of_iterations_estimates ();
 478   scev_finalize ();
 479   loop_optimizer_finalize ();
 480   return 0;
 481 }
 482
 483 namespace {
 484
 485 const pass_data pass_data_tree_loop_done =
 486 {
 487   GIMPLE_PASS, /* type */
 488   "loopdone", /* name */
 489   OPTGROUP_LOOP, /* optinfo_flags */
 490   TV_NONE, /* tv_id */
 491   PROP_cfg, /* properties_required */
 492   0, /* properties_provided */
 493   0, /* properties_destroyed */
 494   0, /* todo_flags_start */
 495   TODO_cleanup_cfg, /* todo_flags_finish */
 496 };
 497
 498 class pass_tree_loop_done : public gimple_opt_pass
 499 {
 500 public:
 501   pass_tree_loop_done (gcc::context *ctxt)
 502     : gimple_opt_pass (pass_data_tree_loop_done, ctxt)
 503   {}
 504
 505   /* opt_pass methods: */
 506   virtual unsigned int execute (function *) { return tree_ssa_loop_done (); }
 507
 508 }; // class pass_tree_loop_done
 509
 510 } // anon namespace
 511
 512 gimple_opt_pass *
 513 make_pass_tree_loop_done (gcc::context *ctxt)
 514 {
 515   return new pass_tree_loop_done (ctxt);
 516 }
 517
 518 /* Calls CBCK for each index in memory reference ADDR_P.  There are two
 519    kinds situations handled; in each of these cases, the memory reference
 520    and DATA are passed to the callback:
 521
 522    Access to an array: ARRAY_{RANGE_}REF (base, index).  In this case we also
 523    pass the pointer to the index to the callback.
 524
 525    Pointer dereference: INDIRECT_REF (addr).  In this case we also pass the
 526    pointer to addr to the callback.
 527
 528    If the callback returns false, the whole search stops and false is returned.
 529    Otherwise the function returns true after traversing through the whole
 530    reference *ADDR_P.  */
 531
 532 bool
 533 for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
 534 {
 535   tree *nxt, *idx;
 536
 537   for (; ; addr_p = nxt)
 538     {
 539       switch (TREE_CODE (*addr_p))
 540         {
 541         case SSA_NAME:
 542           return cbck (*addr_p, addr_p, data);
 543
 544         case MEM_REF:
 545           nxt = &TREE_OPERAND (*addr_p, 0);
 546           return cbck (*addr_p, nxt, data);
 547
 548         case BIT_FIELD_REF:
 549         case VIEW_CONVERT_EXPR:
 550         case REALPART_EXPR:
 551         case IMAGPART_EXPR:
 552           nxt = &TREE_OPERAND (*addr_p, 0);
 553           break;
 554
 555         case COMPONENT_REF:
 556           /* If the component has varying offset, it behaves like index
 557              as well.  */
 558           idx = &TREE_OPERAND (*addr_p, 2);
 559           if (*idx
 560               && !cbck (*addr_p, idx, data))
 561             return false;
 562
 563           nxt = &TREE_OPERAND (*addr_p, 0);
 564           break;
 565
 566         case ARRAY_REF:
 567         case ARRAY_RANGE_REF:
 568           nxt = &TREE_OPERAND (*addr_p, 0);
 569           if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
 570             return false;
 571           break;
 572
 573         case VAR_DECL:
 574         case PARM_DECL:
 575         case CONST_DECL:
 576         case STRING_CST:
 577         case RESULT_DECL:
 578         case VECTOR_CST:
 579         case COMPLEX_CST:
 580         case INTEGER_CST:
 581         case REAL_CST:
 582         case FIXED_CST:
 583         case CONSTRUCTOR:
 584           return true;
 585
 586         case ADDR_EXPR:
 587           gcc_assert (is_gimple_min_invariant (*addr_p));
 588           return true;
 589
 590         case TARGET_MEM_REF:
 591           idx = &TMR_BASE (*addr_p);
 592           if (*idx
 593               && !cbck (*addr_p, idx, data))
 594             return false;
 595           idx = &TMR_INDEX (*addr_p);
 596           if (*idx
 597               && !cbck (*addr_p, idx, data))
 598             return false;
 599           idx = &TMR_INDEX2 (*addr_p);
 600           if (*idx
 601               && !cbck (*addr_p, idx, data))
 602             return false;
 603           return true;
 604
 605         default:
 606           gcc_unreachable ();
 607         }
 608     }
 609 }
 610
 611
 612 /* The name and the length of the currently generated variable
 613    for lsm.  */
 614 #define MAX_LSM_NAME_LENGTH 40
 615 static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
 616 static int lsm_tmp_name_length;
 617
 618 /* Adds S to lsm_tmp_name.  */
 619
 620 static void
 621 lsm_tmp_name_add (const char *s)
 622 {
 623   int l = strlen (s) + lsm_tmp_name_length;
 624   if (l > MAX_LSM_NAME_LENGTH)
 625     return;
 626
 627   strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
 628   lsm_tmp_name_length = l;
 629 }
 630
 631 /* Stores the name for temporary variable that replaces REF to
 632    lsm_tmp_name.  */
 633
 634 static void
 635 gen_lsm_tmp_name (tree ref)
 636 {
 637   const char *name;
 638
 639   switch (TREE_CODE (ref))
 640     {
 641     case MEM_REF:
 642     case TARGET_MEM_REF:
 643       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 644       lsm_tmp_name_add ("_");
 645       break;
 646
 647     case ADDR_EXPR:
 648       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 649       break;
 650
 651     case BIT_FIELD_REF:
 652     case VIEW_CONVERT_EXPR:
 653     case ARRAY_RANGE_REF:
 654       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 655       break;
 656
 657     case REALPART_EXPR:
 658       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 659       lsm_tmp_name_add ("_RE");
 660       break;
 661
 662     case IMAGPART_EXPR:
 663       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 664       lsm_tmp_name_add ("_IM");
 665       break;
 666
 667     case COMPONENT_REF:
 668       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 669       lsm_tmp_name_add ("_");
 670       name = get_name (TREE_OPERAND (ref, 1));
 671       if (!name)
 672         name = "F";
 673       lsm_tmp_name_add (name);
 674       break;
 675
 676     case ARRAY_REF:
 677       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 678       lsm_tmp_name_add ("_I");
 679       break;
 680
 681     case SSA_NAME:
 682     case VAR_DECL:
 683     case PARM_DECL:
 684       name = get_name (ref);
 685       if (!name)
 686         name = "D";
 687       lsm_tmp_name_add (name);
 688       break;
 689
 690     case STRING_CST:
 691       lsm_tmp_name_add ("S");
 692       break;
 693
 694     case RESULT_DECL:
 695       lsm_tmp_name_add ("R");
 696       break;
 697
 698     case INTEGER_CST:
 699       /* Nothing.  */
 700       break;
 701
 702     default:
 703       gcc_unreachable ();
 704     }
 705 }
 706
 707 /* Determines name for temporary variable that replaces REF.
 708    The name is accumulated into the lsm_tmp_name variable.
 709    N is added to the name of the temporary.  */
 710
 711 char *
 712 get_lsm_tmp_name (tree ref, unsigned n, const char *suffix)
 713 {
 714   char ns[2];
 715
 716   lsm_tmp_name_length = 0;
 717   gen_lsm_tmp_name (ref);
 718   lsm_tmp_name_add ("_lsm");
 719   if (n < 10)
 720     {
 721       ns[0] = '0' + n;
 722       ns[1] = 0;
 723       lsm_tmp_name_add (ns);
 724     }
 725   return lsm_tmp_name;
 726   if (suffix != NULL)
 727     lsm_tmp_name_add (suffix);
 728 }
 729
 730 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS.  */
 731
 732 unsigned
 733 tree_num_loop_insns (struct loop *loop, eni_weights *weights)
 734 {
 735   basic_block *body = get_loop_body (loop);
 736   gimple_stmt_iterator gsi;
 737   unsigned size = 0, i;
 738
 739   for (i = 0; i < loop->num_nodes; i++)
 740     for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
 741       size += estimate_num_insns (gsi_stmt (gsi), weights);
 742   free (body);
 743
 744   return size;
 745 }
 746
 747
 748