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