gcc/tree-ssa-copy.c

   1 /* Copy propagation and SSA_NAME replacement support routines.
   2    Copyright (C) 2004-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
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 3, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License 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 "ssa.h"
  28 #include "alias.h"
  29 #include "fold-const.h"
  30 #include "flags.h"
  31 #include "tm_p.h"
  32 #include "gimple-pretty-print.h"
  33 #include "internal-fn.h"
  34 #include "gimple-iterator.h"
  35 #include "tree-cfg.h"
  36 #include "tree-pass.h"
  37 #include "tree-ssa-propagate.h"
  38 #include "langhooks.h"
  39 #include "cfgloop.h"
  40 #include "tree-scalar-evolution.h"
  41 #include "tree-ssa-dom.h"
  42 #include "tree-ssa-loop-niter.h"
  43
  44
  45 /* This file implements the copy propagation pass and provides a
  46    handful of interfaces for performing const/copy propagation and
  47    simple expression replacement which keep variable annotations
  48    up-to-date.
  49
  50    We require that for any copy operation where the RHS and LHS have
  51    a non-null memory tag the memory tag be the same.   It is OK
  52    for one or both of the memory tags to be NULL.
  53
  54    We also require tracking if a variable is dereferenced in a load or
  55    store operation.
  56
  57    We enforce these requirements by having all copy propagation and
  58    replacements of one SSA_NAME with a different SSA_NAME to use the
  59    APIs defined in this file.  */
  60
  61 /*---------------------------------------------------------------------------
  62                                 Copy propagation
  63 ---------------------------------------------------------------------------*/
  64 /* Lattice for copy-propagation.  The lattice is initialized to
  65    UNDEFINED (value == NULL) for SSA names that can become a copy
  66    of something or VARYING (value == self) if not (see get_copy_of_val
  67    and stmt_may_generate_copy).  Other values make the name a COPY
  68    of that value.
  69
  70    When visiting a statement or PHI node the lattice value for an
  71    SSA name can transition from UNDEFINED to COPY to VARYING.  */
  72
  73 struct prop_value_t {
  74     /* Copy-of value.  */
  75     tree value;
  76 };
  77
  78 static prop_value_t *copy_of;
  79 static unsigned n_copy_of;
  80
  81
  82 /* Return true if this statement may generate a useful copy.  */
  83
  84 static bool
  85 stmt_may_generate_copy (gimple *stmt)
  86 {
  87   if (gimple_code (stmt) == GIMPLE_PHI)
  88     return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt));
  89
  90   if (gimple_code (stmt) != GIMPLE_ASSIGN)
  91     return false;
  92
  93   /* If the statement has volatile operands, it won't generate a
  94      useful copy.  */
  95   if (gimple_has_volatile_ops (stmt))
  96     return false;
  97
  98   /* Statements with loads and/or stores will never generate a useful copy.  */
  99   if (gimple_vuse (stmt))
 100     return false;
 101
 102   /* Otherwise, the only statements that generate useful copies are
 103      assignments whose RHS is just an SSA name that doesn't flow
 104      through abnormal edges.  */
 105   return ((gimple_assign_rhs_code (stmt) == SSA_NAME
 106            && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
 107           || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)));
 108 }
 109
 110
 111 /* Return the copy-of value for VAR.  */
 112
 113 static inline prop_value_t *
 114 get_copy_of_val (tree var)
 115 {
 116   prop_value_t *val = &copy_of[SSA_NAME_VERSION (var)];
 117
 118   if (val->value == NULL_TREE
 119       && !stmt_may_generate_copy (SSA_NAME_DEF_STMT (var)))
 120     {
 121       /* If the variable will never generate a useful copy relation,
 122          make it its own copy.  */
 123       val->value = var;
 124     }
 125
 126   return val;
 127 }
 128
 129 /* Return the variable VAR is a copy of or VAR if VAR isn't the result
 130    of a copy.  */
 131
 132 static inline tree
 133 valueize_val (tree var)
 134 {
 135   if (TREE_CODE (var) == SSA_NAME)
 136     {
 137       tree val = get_copy_of_val (var)->value;
 138       if (val)
 139         return val;
 140     }
 141   return var;
 142 }
 143
 144 /* Set VAL to be the copy of VAR.  If that changed return true.  */
 145
 146 static inline bool
 147 set_copy_of_val (tree var, tree val)
 148 {
 149   unsigned int ver = SSA_NAME_VERSION (var);
 150   tree old;
 151
 152   /* Set FIRST to be the first link in COPY_OF[DEST].  If that
 153      changed, return true.  */
 154   old = copy_of[ver].value;
 155   copy_of[ver].value = val;
 156
 157   if (old != val
 158       || (val && !operand_equal_p (old, val, 0)))
 159     return true;
 160
 161   return false;
 162 }
 163
 164
 165 /* Dump the copy-of value for variable VAR to FILE.  */
 166
 167 static void
 168 dump_copy_of (FILE *file, tree var)
 169 {
 170   tree val;
 171
 172   print_generic_expr (file, var, dump_flags);
 173   if (TREE_CODE (var) != SSA_NAME)
 174     return;
 175
 176   val = copy_of[SSA_NAME_VERSION (var)].value;
 177   fprintf (file, " copy-of chain: ");
 178   print_generic_expr (file, var, 0);
 179   fprintf (file, " ");
 180   if (!val)
 181     fprintf (file, "[UNDEFINED]");
 182   else if (val == var)
 183     fprintf (file, "[NOT A COPY]");
 184   else
 185     {
 186       fprintf (file, "-> ");
 187       print_generic_expr (file, val, 0);
 188       fprintf (file, " ");
 189       fprintf (file, "[COPY]");
 190     }
 191 }
 192
 193
 194 /* Evaluate the RHS of STMT.  If it produces a valid copy, set the LHS
 195    value and store the LHS into *RESULT_P.  */
 196
 197 static enum ssa_prop_result
 198 copy_prop_visit_assignment (gimple *stmt, tree *result_p)
 199 {
 200   tree lhs, rhs;
 201
 202   lhs = gimple_assign_lhs (stmt);
 203   rhs = valueize_val (gimple_assign_rhs1 (stmt));
 204
 205   if (TREE_CODE (lhs) == SSA_NAME)
 206     {
 207       /* Straight copy between two SSA names.  First, make sure that
 208          we can propagate the RHS into uses of LHS.  */
 209       if (!may_propagate_copy (lhs, rhs))
 210         return SSA_PROP_VARYING;
 211
 212       *result_p = lhs;
 213       if (set_copy_of_val (*result_p, rhs))
 214         return SSA_PROP_INTERESTING;
 215       else
 216         return SSA_PROP_NOT_INTERESTING;
 217     }
 218
 219   return SSA_PROP_VARYING;
 220 }
 221
 222
 223 /* Visit the GIMPLE_COND STMT.  Return SSA_PROP_INTERESTING
 224    if it can determine which edge will be taken.  Otherwise, return
 225    SSA_PROP_VARYING.  */
 226
 227 static enum ssa_prop_result
 228 copy_prop_visit_cond_stmt (gimple *stmt, edge *taken_edge_p)
 229 {
 230   enum ssa_prop_result retval = SSA_PROP_VARYING;
 231   location_t loc = gimple_location (stmt);
 232
 233   tree op0 = valueize_val (gimple_cond_lhs (stmt));
 234   tree op1 = valueize_val (gimple_cond_rhs (stmt));
 235
 236   /* See if we can determine the predicate's value.  */
 237   if (dump_file && (dump_flags & TDF_DETAILS))
 238     {
 239       fprintf (dump_file, "Trying to determine truth value of ");
 240       fprintf (dump_file, "predicate ");
 241       print_gimple_stmt (dump_file, stmt, 0, 0);
 242     }
 243
 244   /* Fold COND and see whether we get a useful result.  */
 245   tree folded_cond = fold_binary_loc (loc, gimple_cond_code (stmt),
 246                                       boolean_type_node, op0, op1);
 247   if (folded_cond)
 248     {
 249       basic_block bb = gimple_bb (stmt);
 250       *taken_edge_p = find_taken_edge (bb, folded_cond);
 251       if (*taken_edge_p)
 252         retval = SSA_PROP_INTERESTING;
 253     }
 254
 255   if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p)
 256     fprintf (dump_file, "\nConditional will always take edge %d->%d\n",
 257              (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index);
 258
 259   return retval;
 260 }
 261
 262
 263 /* Evaluate statement STMT.  If the statement produces a new output
 264    value, return SSA_PROP_INTERESTING and store the SSA_NAME holding
 265    the new value in *RESULT_P.
 266
 267    If STMT is a conditional branch and we can determine its truth
 268    value, set *TAKEN_EDGE_P accordingly.
 269
 270    If the new value produced by STMT is varying, return
 271    SSA_PROP_VARYING.  */
 272
 273 static enum ssa_prop_result
 274 copy_prop_visit_stmt (gimple *stmt, edge *taken_edge_p, tree *result_p)
 275 {
 276   enum ssa_prop_result retval;
 277
 278   if (dump_file && (dump_flags & TDF_DETAILS))
 279     {
 280       fprintf (dump_file, "\nVisiting statement:\n");
 281       print_gimple_stmt (dump_file, stmt, 0, dump_flags);
 282       fprintf (dump_file, "\n");
 283     }
 284
 285   if (gimple_assign_single_p (stmt)
 286       && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
 287       && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
 288           || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
 289     {
 290       /* If the statement is a copy assignment, evaluate its RHS to
 291          see if the lattice value of its output has changed.  */
 292       retval = copy_prop_visit_assignment (stmt, result_p);
 293     }
 294   else if (gimple_code (stmt) == GIMPLE_COND)
 295     {
 296       /* See if we can determine which edge goes out of a conditional
 297          jump.  */
 298       retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p);
 299     }
 300   else
 301     retval = SSA_PROP_VARYING;
 302
 303   if (retval == SSA_PROP_VARYING)
 304     {
 305       tree def;
 306       ssa_op_iter i;
 307
 308       /* Any other kind of statement is not interesting for constant
 309          propagation and, therefore, not worth simulating.  */
 310       if (dump_file && (dump_flags & TDF_DETAILS))
 311         fprintf (dump_file, "No interesting values produced.\n");
 312
 313       /* The assignment is not a copy operation.  Don't visit this
 314          statement again and mark all the definitions in the statement
 315          to be copies of nothing.  */
 316       FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS)
 317         set_copy_of_val (def, def);
 318     }
 319
 320   return retval;
 321 }
 322
 323
 324 /* Visit PHI node PHI.  If all the arguments produce the same value,
 325    set it to be the value of the LHS of PHI.  */
 326
 327 static enum ssa_prop_result
 328 copy_prop_visit_phi_node (gphi *phi)
 329 {
 330   enum ssa_prop_result retval;
 331   unsigned i;
 332   prop_value_t phi_val = { NULL_TREE };
 333
 334   tree lhs = gimple_phi_result (phi);
 335
 336   if (dump_file && (dump_flags & TDF_DETAILS))
 337     {
 338       fprintf (dump_file, "\nVisiting PHI node: ");
 339       print_gimple_stmt (dump_file, phi, 0, dump_flags);
 340     }
 341
 342   for (i = 0; i < gimple_phi_num_args (phi); i++)
 343     {
 344       prop_value_t *arg_val;
 345       tree arg_value;
 346       tree arg = gimple_phi_arg_def (phi, i);
 347       edge e = gimple_phi_arg_edge (phi, i);
 348
 349       /* We don't care about values flowing through non-executable
 350          edges.  */
 351       if (!(e->flags & EDGE_EXECUTABLE))
 352         continue;
 353
 354       /* Names that flow through abnormal edges cannot be used to
 355          derive copies.  */
 356       if (TREE_CODE (arg) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg))
 357         {
 358           phi_val.value = lhs;
 359           break;
 360         }
 361
 362       if (dump_file && (dump_flags & TDF_DETAILS))
 363         {
 364           fprintf (dump_file, "\tArgument #%d: ", i);
 365           dump_copy_of (dump_file, arg);
 366           fprintf (dump_file, "\n");
 367         }
 368
 369       if (TREE_CODE (arg) == SSA_NAME)
 370         {
 371           arg_val = get_copy_of_val (arg);
 372
 373           /* If we didn't visit the definition of arg yet treat it as
 374              UNDEFINED.  This also handles PHI arguments that are the
 375              same as lhs.  We'll come here again.  */
 376           if (!arg_val->value)
 377             continue;
 378
 379           arg_value = arg_val->value;
 380         }
 381       else
 382         arg_value = valueize_val (arg);
 383
 384       /* In loop-closed SSA form do not copy-propagate SSA-names across
 385          loop exit edges.  */
 386       if (loops_state_satisfies_p (LOOP_CLOSED_SSA)
 387           && TREE_CODE (arg_value) == SSA_NAME
 388           && loop_exit_edge_p (e->src->loop_father, e))
 389         {
 390           phi_val.value = lhs;
 391           break;
 392         }
 393
 394       /* If the LHS didn't have a value yet, make it a copy of the
 395          first argument we find.   */
 396       if (phi_val.value == NULL_TREE)
 397         {
 398           phi_val.value = arg_value;
 399           continue;
 400         }
 401
 402       /* If PHI_VAL and ARG don't have a common copy-of chain, then
 403          this PHI node cannot be a copy operation.  */
 404       if (phi_val.value != arg_value
 405           && !operand_equal_p (phi_val.value, arg_value, 0))
 406         {
 407           phi_val.value = lhs;
 408           break;
 409         }
 410     }
 411
 412   if (phi_val.value
 413       && may_propagate_copy (lhs, phi_val.value)
 414       && set_copy_of_val (lhs, phi_val.value))
 415     retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
 416   else
 417     retval = SSA_PROP_NOT_INTERESTING;
 418
 419   if (dump_file && (dump_flags & TDF_DETAILS))
 420     {
 421       fprintf (dump_file, "PHI node ");
 422       dump_copy_of (dump_file, lhs);
 423       fprintf (dump_file, "\nTelling the propagator to ");
 424       if (retval == SSA_PROP_INTERESTING)
 425         fprintf (dump_file, "add SSA edges out of this PHI and continue.");
 426       else if (retval == SSA_PROP_VARYING)
 427         fprintf (dump_file, "add SSA edges out of this PHI and never visit again.");
 428       else
 429         fprintf (dump_file, "do nothing with SSA edges and keep iterating.");
 430       fprintf (dump_file, "\n\n");
 431     }
 432
 433   return retval;
 434 }
 435
 436
 437 /* Initialize structures used for copy propagation.  */
 438
 439 static void
 440 init_copy_prop (void)
 441 {
 442   basic_block bb;
 443
 444   n_copy_of = num_ssa_names;
 445   copy_of = XCNEWVEC (prop_value_t, n_copy_of);
 446
 447   FOR_EACH_BB_FN (bb, cfun)
 448     {
 449       for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
 450            gsi_next (&si))
 451         {
 452           gimple *stmt = gsi_stmt (si);
 453           ssa_op_iter iter;
 454           tree def;
 455
 456           /* The only statements that we care about are those that may
 457              generate useful copies.  We also need to mark conditional
 458              jumps so that their outgoing edges are added to the work
 459              lists of the propagator.  */
 460           if (stmt_ends_bb_p (stmt))
 461             prop_set_simulate_again (stmt, true);
 462           else if (stmt_may_generate_copy (stmt))
 463             prop_set_simulate_again (stmt, true);
 464           else
 465             prop_set_simulate_again (stmt, false);
 466
 467           /* Mark all the outputs of this statement as not being
 468              the copy of anything.  */
 469           FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 470             if (!prop_simulate_again_p (stmt))
 471               set_copy_of_val (def, def);
 472         }
 473
 474       for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
 475            gsi_next (&si))
 476         {
 477           gphi *phi = si.phi ();
 478           tree def;
 479
 480           def = gimple_phi_result (phi);
 481           if (virtual_operand_p (def))
 482             prop_set_simulate_again (phi, false);
 483           else
 484             prop_set_simulate_again (phi, true);
 485
 486           if (!prop_simulate_again_p (phi))
 487             set_copy_of_val (def, def);
 488         }
 489     }
 490 }
 491
 492 /* Callback for substitute_and_fold to get at the final copy-of values.  */
 493
 494 static tree
 495 get_value (tree name)
 496 {
 497   tree val;
 498   if (SSA_NAME_VERSION (name) >= n_copy_of)
 499     return NULL_TREE;
 500   val = copy_of[SSA_NAME_VERSION (name)].value;
 501   if (val && val != name)
 502     return val;
 503   return NULL_TREE;
 504 }
 505
 506 /* Deallocate memory used in copy propagation and do final
 507    substitution.  */
 508
 509 static bool
 510 fini_copy_prop (void)
 511 {
 512   unsigned i;
 513
 514   /* Set the final copy-of value for each variable by traversing the
 515      copy-of chains.  */
 516   for (i = 1; i < num_ssa_names; i++)
 517     {
 518       tree var = ssa_name (i);
 519       if (!var
 520           || !copy_of[i].value
 521           || copy_of[i].value == var)
 522         continue;
 523
 524       /* In theory the points-to solution of all members of the
 525          copy chain is their intersection.  For now we do not bother
 526          to compute this but only make sure we do not lose points-to
 527          information completely by setting the points-to solution
 528          of the representative to the first solution we find if
 529          it doesn't have one already.  */
 530       if (copy_of[i].value != var
 531           && TREE_CODE (copy_of[i].value) == SSA_NAME)
 532         {
 533           basic_block copy_of_bb
 534             = gimple_bb (SSA_NAME_DEF_STMT (copy_of[i].value));
 535           basic_block var_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
 536           if (POINTER_TYPE_P (TREE_TYPE (var))
 537               && SSA_NAME_PTR_INFO (var)
 538               && !SSA_NAME_PTR_INFO (copy_of[i].value))
 539             {
 540               duplicate_ssa_name_ptr_info (copy_of[i].value,
 541                                            SSA_NAME_PTR_INFO (var));
 542               /* Points-to information is cfg insensitive,
 543                  but alignment info might be cfg sensitive, if it
 544                  e.g. is derived from VRP derived non-zero bits.
 545                  So, do not copy alignment info if the two SSA_NAMEs
 546                  aren't defined in the same basic block.  */
 547               if (var_bb != copy_of_bb)
 548                 mark_ptr_info_alignment_unknown
 549                                 (SSA_NAME_PTR_INFO (copy_of[i].value));
 550             }
 551           else if (!POINTER_TYPE_P (TREE_TYPE (var))
 552                    && SSA_NAME_RANGE_INFO (var)
 553                    && !SSA_NAME_RANGE_INFO (copy_of[i].value)
 554                    && var_bb == copy_of_bb)
 555             duplicate_ssa_name_range_info (copy_of[i].value,
 556                                            SSA_NAME_RANGE_TYPE (var),
 557                                            SSA_NAME_RANGE_INFO (var));
 558         }
 559     }
 560
 561   bool changed = substitute_and_fold (get_value, NULL, true);
 562   if (changed)
 563     {
 564       free_numbers_of_iterations_estimates (cfun);
 565       if (scev_initialized_p ())
 566         scev_reset ();
 567     }
 568
 569   free (copy_of);
 570
 571   return changed;
 572 }
 573
 574
 575 /* Main entry point to the copy propagator.
 576
 577    PHIS_ONLY is true if we should only consider PHI nodes as generating
 578    copy propagation opportunities.
 579
 580    The algorithm propagates the value COPY-OF using ssa_propagate.  For
 581    every variable X_i, COPY-OF(X_i) indicates which variable is X_i created
 582    from.  The following example shows how the algorithm proceeds at a
 583    high level:
 584
 585             1   a_24 = x_1
 586             2   a_2 = PHI <a_24, x_1>
 587             3   a_5 = PHI <a_2>
 588             4   x_1 = PHI <x_298, a_5, a_2>
 589
 590    The end result should be that a_2, a_5, a_24 and x_1 are a copy of
 591    x_298.  Propagation proceeds as follows.
 592
 593    Visit #1: a_24 is copy-of x_1.  Value changed.
 594    Visit #2: a_2 is copy-of x_1.  Value changed.
 595    Visit #3: a_5 is copy-of x_1.  Value changed.
 596    Visit #4: x_1 is copy-of x_298.  Value changed.
 597    Visit #1: a_24 is copy-of x_298.  Value changed.
 598    Visit #2: a_2 is copy-of x_298.  Value changed.
 599    Visit #3: a_5 is copy-of x_298.  Value changed.
 600    Visit #4: x_1 is copy-of x_298.  Stable state reached.
 601
 602    When visiting PHI nodes, we only consider arguments that flow
 603    through edges marked executable by the propagation engine.  So,
 604    when visiting statement #2 for the first time, we will only look at
 605    the first argument (a_24) and optimistically assume that its value
 606    is the copy of a_24 (x_1).  */
 607
 608 static unsigned int
 609 execute_copy_prop (void)
 610 {
 611   init_copy_prop ();
 612   ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node);
 613   if (fini_copy_prop ())
 614     return TODO_cleanup_cfg;
 615   return 0;
 616 }
 617
 618 namespace {
 619
 620 const pass_data pass_data_copy_prop =
 621 {
 622   GIMPLE_PASS, /* type */
 623   "copyprop", /* name */
 624   OPTGROUP_NONE, /* optinfo_flags */
 625   TV_TREE_COPY_PROP, /* tv_id */
 626   ( PROP_ssa | PROP_cfg ), /* properties_required */
 627   0, /* properties_provided */
 628   0, /* properties_destroyed */
 629   0, /* todo_flags_start */
 630   0, /* todo_flags_finish */
 631 };
 632
 633 class pass_copy_prop : public gimple_opt_pass
 634 {
 635 public:
 636   pass_copy_prop (gcc::context *ctxt)
 637     : gimple_opt_pass (pass_data_copy_prop, ctxt)
 638   {}
 639
 640   /* opt_pass methods: */
 641   opt_pass * clone () { return new pass_copy_prop (m_ctxt); }
 642   virtual bool gate (function *) { return flag_tree_copy_prop != 0; }
 643   virtual unsigned int execute (function *) { return execute_copy_prop (); }
 644
 645 }; // class pass_copy_prop
 646
 647 } // anon namespace
 648
 649 gimple_opt_pass *
 650 make_pass_copy_prop (gcc::context *ctxt)
 651 {
 652   return new pass_copy_prop (ctxt);
 653 }