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