gcc/tree-ssa-loop.c

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