gcc/gimple-ssa-backprop.c

   1 /* Back-propagation of usage information to definitions.
   2    Copyright (C) 2015-2016 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 /* This pass propagates information that is common to all uses of an SSA
  21    name back up through the sequence of statements that generate it,
  22    simplifying the statements where possible.  Sometimes this can expose
  23    fully or partially dead code, but the main focus is simplifying
  24    computations.
  25
  26    At the moment the pass only handles one piece of information: whether the
  27    sign of a value matters, and therefore whether sign-changing operations
  28    can be skipped.  The pass could be extended to more interesting
  29    information in future, such as which bits of an integer are significant.
  30
  31    For example, take the function:
  32
  33      double
  34      f (double *a, int n, double start)
  35      {
  36        double x = fabs (start);
  37        for (int i = 0; i < n; ++i)
  38          x *= a[i];
  39        return __builtin_cos (x);
  40      }
  41
  42    cos(x) == cos(-x), so the sign of the final x doesn't matter.
  43    That x is the result of a series of multiplications, and if
  44    the sign of the result of a multiplication doesn't matter,
  45    the signs of the inputs don't matter either.
  46
  47    The pass would replace the incoming value of x (i.e. fabs(start))
  48    with start.  Since there are no other uses of the fabs result,
  49    the call would get deleted as dead.
  50
  51    The algorithm is:
  52
  53    (1) Do a post-order traversal of the blocks in the function, walking
  54        each block backwards.  For each potentially-simplifiable statement
  55        that defines an SSA name X, examine all uses of X to see what
  56        information is actually significant.  Record this as INFO_MAP[X].
  57        Optimistically ignore for now any back-edge references to
  58        unprocessed phis.
  59
  60        (An alternative would be to record each use when we visit its
  61        statement and take the intersection as we go along.  However,
  62        this would lead to more SSA names being entered into INFO_MAP
  63        unnecessarily, only to be taken out again later.  At the moment
  64        very few SSA names end up with useful information.)
  65
  66    (2) Iteratively reduce the optimistic result of (1) until we reach
  67        a maximal fixed point (which at the moment would mean revisiting
  68        statements at most once).  First push all SSA names that used an
  69        optimistic assumption about a backedge phi onto a worklist.
  70        While the worklist is nonempty, pick off an SSA name X and recompute
  71        INFO_MAP[X].  If the value changes, push all SSA names used in the
  72        definition of X onto the worklist.
  73
  74    (3) Iterate over each SSA name X with info in INFO_MAP, in the
  75        opposite order to (1), i.e. a forward reverse-post-order walk.
  76        Try to optimize the definition of X using INFO_MAP[X] and fold
  77        the result.  (This ensures that we fold definitions before uses.)
  78
  79    (4) Iterate over each SSA name X with info in INFO_MAP, in the same
  80        order as (1), and delete any statements that are now dead.
  81        (This ensures that if a sequence of statements is dead,
  82        we delete the last statement first.)
  83
  84    Note that this pass does not deal with direct redundancies,
  85    such as cos(-x)->cos(x).  match.pd handles those cases instead.  */
  86
  87 #include "config.h"
  88 #include "system.h"
  89 #include "coretypes.h"
  90 #include "backend.h"
  91 #include "tree.h"
  92 #include "gimple.h"
  93 #include "gimple-iterator.h"
  94 #include "ssa.h"
  95 #include "fold-const.h"
  96 #include "tree-pass.h"
  97 #include "cfganal.h"
  98 #include "gimple-pretty-print.h"
  99 #include "tree-cfg.h"
 100 #include "tree-ssa.h"
 101 #include "tree-ssa-propagate.h"
 102 #include "gimple-fold.h"
 103 #include "alloc-pool.h"
 104 #include "tree-hash-traits.h"
 105 #include "case-cfn-macros.h"
 106
 107 namespace {
 108
 109 /* Information about a group of uses of an SSA name.  */
 110 struct usage_info
 111 {
 112   usage_info () : flag_word (0) {}
 113   usage_info &operator &= (const usage_info &);
 114   usage_info operator & (const usage_info &) const;
 115   bool operator == (const usage_info &) const;
 116   bool operator != (const usage_info &) const;
 117   bool is_useful () const;
 118
 119   static usage_info intersection_identity ();
 120
 121   union
 122   {
 123     struct
 124     {
 125       /* True if the uses treat x and -x in the same way.  */
 126       unsigned int ignore_sign : 1;
 127     } flags;
 128     /* All the flag bits as a single int.  */
 129     unsigned int flag_word;
 130   };
 131 };
 132
 133 /* Return an X such that X & Y == Y for all Y.  This is the most
 134    optimistic assumption possible.  */
 135
 136 usage_info
 137 usage_info::intersection_identity ()
 138 {
 139   usage_info ret;
 140   ret.flag_word = -1;
 141   return ret;
 142 }
 143
 144 /* Intersect *THIS with OTHER, so that *THIS describes all uses covered
 145    by the original *THIS and OTHER.  */
 146
 147 usage_info &
 148 usage_info::operator &= (const usage_info &other)
 149 {
 150   flag_word &= other.flag_word;
 151   return *this;
 152 }
 153
 154 /* Return the intersection of *THIS and OTHER, i.e. a structure that
 155    describes all uses covered by *THIS and OTHER.  */
 156
 157 usage_info
 158 usage_info::operator & (const usage_info &other) const
 159 {
 160   usage_info info (*this);
 161   info &= other;
 162   return info;
 163 }
 164
 165 bool
 166 usage_info::operator == (const usage_info &other) const
 167 {
 168   return flag_word == other.flag_word;
 169 }
 170
 171 bool
 172 usage_info::operator != (const usage_info &other) const
 173 {
 174   return !operator == (other);
 175 }
 176
 177 /* Return true if *THIS is not simply the default, safe assumption.  */
 178
 179 bool
 180 usage_info::is_useful () const
 181 {
 182   return flag_word != 0;
 183 }
 184
 185 /* Start a dump line about SSA name VAR.  */
 186
 187 static void
 188 dump_usage_prefix (FILE *file, tree var)
 189 {
 190   fprintf (file, "  ");
 191   print_generic_expr (file, var, 0);
 192   fprintf (file, ": ");
 193 }
 194
 195 /* Print INFO to FILE.  */
 196
 197 static void
 198 dump_usage_info (FILE *file, tree var, usage_info *info)
 199 {
 200   if (info->flags.ignore_sign)
 201     {
 202       dump_usage_prefix (file, var);
 203       fprintf (file, "sign bit not important\n");
 204     }
 205 }
 206
 207 /* Represents one execution of the pass.  */
 208 class backprop
 209 {
 210 public:
 211   backprop (function *);
 212   ~backprop ();
 213
 214   void execute ();
 215
 216 private:
 217   const usage_info *lookup_operand (tree);
 218
 219   void push_to_worklist (tree);
 220   tree pop_from_worklist ();
 221
 222   void process_builtin_call_use (gcall *, tree, usage_info *);
 223   void process_assign_use (gassign *, tree, usage_info *);
 224   void process_phi_use (gphi *, usage_info *);
 225   void process_use (gimple *, tree, usage_info *);
 226   bool intersect_uses (tree, usage_info *);
 227   void reprocess_inputs (gimple *);
 228   void process_var (tree);
 229   void process_block (basic_block);
 230
 231   void prepare_change (tree);
 232   void complete_change (gimple *);
 233   void optimize_builtin_call (gcall *, tree, const usage_info *);
 234   void replace_assign_rhs (gassign *, tree, tree, tree, tree);
 235   void optimize_assign (gassign *, tree, const usage_info *);
 236   void optimize_phi (gphi *, tree, const usage_info *);
 237
 238   typedef hash_map <tree_ssa_name_hash, usage_info *> info_map_type;
 239   typedef std::pair <tree, usage_info *> var_info_pair;
 240
 241   /* The function we're optimizing.  */
 242   function *m_fn;
 243
 244   /* Pool for allocating usage_info structures.  */
 245   object_allocator <usage_info> m_info_pool;
 246
 247   /* Maps an SSA name to a description of all uses of that SSA name.
 248      All the usage_infos satisfy is_useful.
 249
 250      We use a hash_map because the map is expected to be sparse
 251      (i.e. most SSA names won't have useful information attached to them).
 252      We could move to a directly-indexed array if that situation changes.  */
 253   info_map_type m_info_map;
 254
 255   /* Post-ordered list of all potentially-interesting SSA names,
 256      along with information that describes all uses.  */
 257   auto_vec <var_info_pair, 128> m_vars;
 258
 259   /* A bitmap of blocks that we have finished processing in the initial
 260      post-order walk.  */
 261   sbitmap m_visited_blocks;
 262
 263   /* A worklist of SSA names whose definitions need to be reconsidered.  */
 264   auto_vec <tree, 64> m_worklist;
 265
 266   /* The SSA names in M_WORKLIST, identified by their SSA_NAME_VERSION.
 267      We use a bitmap rather than an sbitmap because most SSA names are
 268      never added to the worklist.  */
 269   bitmap m_worklist_names;
 270 };
 271
 272 backprop::backprop (function *fn)
 273   : m_fn (fn),
 274     m_info_pool ("usage_info"),
 275     m_visited_blocks (sbitmap_alloc (last_basic_block_for_fn (m_fn))),
 276     m_worklist_names (BITMAP_ALLOC (NULL))
 277 {
 278   bitmap_clear (m_visited_blocks);
 279 }
 280
 281 backprop::~backprop ()
 282 {
 283   BITMAP_FREE (m_worklist_names);
 284   sbitmap_free (m_visited_blocks);
 285   m_info_pool.release ();
 286 }
 287
 288 /* Return usage information for general operand OP, or null if none.  */
 289
 290 const usage_info *
 291 backprop::lookup_operand (tree op)
 292 {
 293   if (op && TREE_CODE (op) == SSA_NAME)
 294     {
 295       usage_info **slot = m_info_map.get (op);
 296       if (slot)
 297         return *slot;
 298     }
 299   return NULL;
 300 }
 301
 302 /* Add SSA name VAR to the worklist, if it isn't on the worklist already.  */
 303
 304 void
 305 backprop::push_to_worklist (tree var)
 306 {
 307   if (!bitmap_set_bit (m_worklist_names, SSA_NAME_VERSION (var)))
 308     return;
 309   m_worklist.safe_push (var);
 310   if (dump_file && (dump_flags & TDF_DETAILS))
 311     {
 312       fprintf (dump_file, "[WORKLIST] Pushing ");
 313       print_generic_expr (dump_file, var, 0);
 314       fprintf (dump_file, "\n");
 315     }
 316 }
 317
 318 /* Remove and return the next SSA name from the worklist.  The worklist
 319    is known to be nonempty.  */
 320
 321 tree
 322 backprop::pop_from_worklist ()
 323 {
 324   tree var = m_worklist.pop ();
 325   bitmap_clear_bit (m_worklist_names, SSA_NAME_VERSION (var));
 326   if (dump_file && (dump_flags & TDF_DETAILS))
 327     {
 328       fprintf (dump_file, "[WORKLIST] Popping ");
 329       print_generic_expr (dump_file, var, 0);
 330       fprintf (dump_file, "\n");
 331     }
 332   return var;
 333 }
 334
 335 /* Make INFO describe all uses of RHS in CALL, which is a call to a
 336    built-in function.  */
 337
 338 void
 339 backprop::process_builtin_call_use (gcall *call, tree rhs, usage_info *info)
 340 {
 341   combined_fn fn = gimple_call_combined_fn (call);
 342   tree lhs = gimple_call_lhs (call);
 343   switch (fn)
 344     {
 345     case CFN_LAST:
 346       break;
 347
 348     CASE_CFN_COS:
 349     CASE_CFN_COSH:
 350     CASE_CFN_CCOS:
 351     CASE_CFN_CCOSH:
 352     CASE_CFN_HYPOT:
 353       /* The signs of all inputs are ignored.  */
 354       info->flags.ignore_sign = true;
 355       break;
 356
 357     CASE_CFN_COPYSIGN:
 358       /* The sign of the first input is ignored.  */
 359       if (rhs != gimple_call_arg (call, 1))
 360         info->flags.ignore_sign = true;
 361       break;
 362
 363     CASE_CFN_POW:
 364       {
 365         /* The sign of the first input is ignored as long as the second
 366            input is an even real.  */
 367         tree power = gimple_call_arg (call, 1);
 368         HOST_WIDE_INT n;
 369         if (TREE_CODE (power) == REAL_CST
 370             && real_isinteger (&TREE_REAL_CST (power), &n)
 371             && (n & 1) == 0)
 372           info->flags.ignore_sign = true;
 373         break;
 374       }
 375
 376     CASE_CFN_FMA:
 377       /* In X * X + Y, where Y is distinct from X, the sign of X doesn't
 378          matter.  */
 379       if (gimple_call_arg (call, 0) == rhs
 380           && gimple_call_arg (call, 1) == rhs
 381           && gimple_call_arg (call, 2) != rhs)
 382         info->flags.ignore_sign = true;
 383       break;
 384
 385     default:
 386       if (negate_mathfn_p (fn))
 387         {
 388           /* The sign of the (single) input doesn't matter provided
 389              that the sign of the output doesn't matter.  */
 390           const usage_info *lhs_info = lookup_operand (lhs);
 391           if (lhs_info)
 392             info->flags.ignore_sign = lhs_info->flags.ignore_sign;
 393         }
 394       break;
 395     }
 396 }
 397
 398 /* Make INFO describe all uses of RHS in ASSIGN.  */
 399
 400 void
 401 backprop::process_assign_use (gassign *assign, tree rhs, usage_info *info)
 402 {
 403   tree lhs = gimple_assign_lhs (assign);
 404   switch (gimple_assign_rhs_code (assign))
 405     {
 406     case ABS_EXPR:
 407       /* The sign of the input doesn't matter.  */
 408       info->flags.ignore_sign = true;
 409       break;
 410
 411     case COND_EXPR:
 412       /* For A = B ? C : D, propagate information about all uses of A
 413          to C and D.  */
 414       if (rhs != gimple_assign_rhs1 (assign))
 415         {
 416           const usage_info *lhs_info = lookup_operand (lhs);
 417           if (lhs_info)
 418             *info = *lhs_info;
 419         }
 420       break;
 421
 422     case FMA_EXPR:
 423       /* In X * X + Y, where Y is distinct from X, the sign of X doesn't
 424          matter.  */
 425       if (gimple_assign_rhs1 (assign) == rhs
 426           && gimple_assign_rhs2 (assign) == rhs
 427           && gimple_assign_rhs3 (assign) != rhs)
 428         info->flags.ignore_sign = true;
 429       break;
 430
 431     case MULT_EXPR:
 432       /* In X * X, the sign of X doesn't matter.  */
 433       if (gimple_assign_rhs1 (assign) == rhs
 434           && gimple_assign_rhs2 (assign) == rhs)
 435         info->flags.ignore_sign = true;
 436       /* Fall through.  */
 437
 438     case NEGATE_EXPR:
 439     case RDIV_EXPR:
 440       /* If the sign of the result doesn't matter, the sign of the inputs
 441          doesn't matter either.  */
 442       if (FLOAT_TYPE_P (TREE_TYPE (rhs)))
 443         {
 444           const usage_info *lhs_info = lookup_operand (lhs);
 445           if (lhs_info)
 446             info->flags.ignore_sign = lhs_info->flags.ignore_sign;
 447         }
 448       break;
 449
 450     default:
 451       break;
 452     }
 453 }
 454
 455 /* Make INFO describe the uses of PHI's result.  */
 456
 457 void
 458 backprop::process_phi_use (gphi *phi, usage_info *info)
 459 {
 460   tree result = gimple_phi_result (phi);
 461   if (const usage_info *result_info = lookup_operand (result))
 462     *info = *result_info;
 463 }
 464
 465 /* Make INFO describe all uses of RHS in STMT.  */
 466
 467 void
 468 backprop::process_use (gimple *stmt, tree rhs, usage_info *info)
 469 {
 470   if (dump_file && (dump_flags & TDF_DETAILS))
 471     {
 472       fprintf (dump_file, "[USE] ");
 473       print_generic_expr (dump_file, rhs, 0);
 474       fprintf (dump_file, " in ");
 475       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 476     }
 477
 478   if (gcall *call = dyn_cast <gcall *> (stmt))
 479     process_builtin_call_use (call, rhs, info);
 480   else if (gassign *assign = dyn_cast <gassign *> (stmt))
 481     process_assign_use (assign, rhs, info);
 482   else if (gphi *phi = dyn_cast <gphi *> (stmt))
 483     process_phi_use (phi, info);
 484
 485   if (dump_file && (dump_flags & TDF_DETAILS))
 486     dump_usage_info (dump_file, rhs, info);
 487 }
 488
 489 /* Make INFO describe all uses of VAR, returning true if the result
 490    is useful.  If the uses include phis that haven't been processed yet,
 491    make the most optimistic assumption possible, so that we aim for
 492    a maximum rather than a minimum fixed point.  */
 493
 494 bool
 495 backprop::intersect_uses (tree var, usage_info *info)
 496 {
 497   imm_use_iterator iter;
 498   gimple *stmt;
 499   *info = usage_info::intersection_identity ();
 500   FOR_EACH_IMM_USE_STMT (stmt, iter, var)
 501     {
 502       if (is_gimple_debug (stmt))
 503         continue;
 504       if (is_a <gphi *> (stmt)
 505           && !bitmap_bit_p (m_visited_blocks, gimple_bb (stmt)->index))
 506         {
 507           /* Skip unprocessed phis.  */
 508           if (dump_file && (dump_flags & TDF_DETAILS))
 509             {
 510               fprintf (dump_file, "[BACKEDGE] ");
 511               print_generic_expr (dump_file, var, 0);
 512               fprintf (dump_file, " in ");
 513               print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 514             }
 515         }
 516       else
 517         {
 518           usage_info subinfo;
 519           process_use (stmt, var, &subinfo);
 520           *info &= subinfo;
 521           if (!info->is_useful ())
 522             {
 523               BREAK_FROM_IMM_USE_STMT (iter);
 524               return false;
 525             }
 526         }
 527     }
 528   return true;
 529 }
 530
 531 /* Queue for reconsideration any input of STMT that has information
 532    associated with it.  This is used if that information might be
 533    too optimistic.  */
 534
 535 void
 536 backprop::reprocess_inputs (gimple *stmt)
 537 {
 538   use_operand_p use_p;
 539   ssa_op_iter oi;
 540   FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
 541     {
 542       tree var = get_use_from_ptr (use_p);
 543       if (lookup_operand (var))
 544         push_to_worklist (var);
 545     }
 546 }
 547
 548 /* Say that we're recording INFO for SSA name VAR, or that we're deleting
 549    existing information if INFO is null.  INTRO describes the change.  */
 550
 551 static void
 552 dump_var_info (tree var, usage_info *info, const char *intro)
 553 {
 554   fprintf (dump_file, "[DEF] %s for ", intro);
 555   print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (var), 0, TDF_SLIM);
 556   if (info)
 557     dump_usage_info (dump_file, var, info);
 558 }
 559
 560 /* Process all uses of VAR and record or update the result in
 561    M_INFO_MAP and M_VARS.  */
 562
 563 void
 564 backprop::process_var (tree var)
 565 {
 566   if (has_zero_uses (var))
 567     return;
 568
 569   usage_info info;
 570   intersect_uses (var, &info);
 571
 572   gimple *stmt = SSA_NAME_DEF_STMT (var);
 573   if (info.is_useful ())
 574     {
 575       bool existed;
 576       usage_info *&map_info = m_info_map.get_or_insert (var, &existed);
 577       if (!existed)
 578         {
 579           /* Recording information about VAR for the first time.  */
 580           map_info = m_info_pool.allocate ();
 581           *map_info = info;
 582           m_vars.safe_push (var_info_pair (var, map_info));
 583           if (dump_file && (dump_flags & TDF_DETAILS))
 584             dump_var_info (var, map_info, "Recording new information");
 585
 586           /* If STMT is a phi, reprocess any backedge uses.  This is a
 587              no-op for other uses, which won't have any information
 588              associated with them.  */
 589           if (is_a <gphi *> (stmt))
 590             reprocess_inputs (stmt);
 591         }
 592       else if (info != *map_info)
 593         {
 594           /* Recording information that is less optimistic than before.  */
 595           gcc_checking_assert ((info & *map_info) == info);
 596           *map_info = info;
 597           if (dump_file && (dump_flags & TDF_DETAILS))
 598             dump_var_info (var, map_info, "Updating information");
 599           reprocess_inputs (stmt);
 600         }
 601     }
 602   else
 603     {
 604       if (usage_info **slot = m_info_map.get (var))
 605         {
 606           /* Removing previously-recorded information.  */
 607           **slot = info;
 608           m_info_map.remove (var);
 609           if (dump_file && (dump_flags & TDF_DETAILS))
 610             dump_var_info (var, NULL, "Deleting information");
 611           reprocess_inputs (stmt);
 612         }
 613       else
 614         {
 615           /* If STMT is a phi, remove any information recorded for
 616              its arguments.  */
 617           if (is_a <gphi *> (stmt))
 618             reprocess_inputs (stmt);
 619         }
 620     }
 621 }
 622
 623 /* Process all statements and phis in BB, during the first post-order walk.  */
 624
 625 void
 626 backprop::process_block (basic_block bb)
 627 {
 628   for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);
 629        gsi_prev (&gsi))
 630     {
 631       tree lhs = gimple_get_lhs (gsi_stmt (gsi));
 632       if (lhs && TREE_CODE (lhs) == SSA_NAME)
 633         process_var (lhs);
 634     }
 635   for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi);
 636        gsi_next (&gpi))
 637     process_var (gimple_phi_result (gpi.phi ()));
 638 }
 639
 640 /* Delete the definition of VAR, which has no uses.  */
 641
 642 static void
 643 remove_unused_var (tree var)
 644 {
 645   gimple *stmt = SSA_NAME_DEF_STMT (var);
 646   if (dump_file && (dump_flags & TDF_DETAILS))
 647     {
 648       fprintf (dump_file, "Deleting ");
 649       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 650     }
 651   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 652   gsi_remove (&gsi, true);
 653   release_defs (stmt);
 654 }
 655
 656 /* Note that we're replacing OLD_RHS with NEW_RHS in STMT.  */
 657
 658 static void
 659 note_replacement (gimple *stmt, tree old_rhs, tree new_rhs)
 660 {
 661   fprintf (dump_file, "Replacing use of ");
 662   print_generic_expr (dump_file, old_rhs, 0);
 663   fprintf (dump_file, " with ");
 664   print_generic_expr (dump_file, new_rhs, 0);
 665   fprintf (dump_file, " in ");
 666   print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 667 }
 668
 669 /* If RHS is an SSA name whose definition just changes the sign of a value,
 670    return that other value, otherwise return null.  */
 671
 672 static tree
 673 strip_sign_op_1 (tree rhs)
 674 {
 675   if (TREE_CODE (rhs) != SSA_NAME)
 676     return NULL_TREE;
 677
 678   gimple *def_stmt = SSA_NAME_DEF_STMT (rhs);
 679   if (gassign *assign = dyn_cast <gassign *> (def_stmt))
 680     switch (gimple_assign_rhs_code (assign))
 681       {
 682       case ABS_EXPR:
 683       case NEGATE_EXPR:
 684         return gimple_assign_rhs1 (assign);
 685
 686       default:
 687         break;
 688       }
 689   else if (gcall *call = dyn_cast <gcall *> (def_stmt))
 690     switch (gimple_call_combined_fn (call))
 691       {
 692       CASE_CFN_COPYSIGN:
 693         return gimple_call_arg (call, 0);
 694
 695       default:
 696         break;
 697       }
 698
 699   return NULL_TREE;
 700 }
 701
 702 /* If RHS is an SSA name whose definition just changes the sign of a value,
 703    strip all such operations and return the ultimate input to them.
 704    Return null otherwise.
 705
 706    Although this could in principle lead to quadratic searching,
 707    in practice a long sequence of sign manipulations should already
 708    have been folded down.  E.g. --x -> x, abs(-x) -> abs(x).  We search
 709    for more than one operation in order to catch cases like -abs(x).  */
 710
 711 static tree
 712 strip_sign_op (tree rhs)
 713 {
 714   tree new_rhs = strip_sign_op_1 (rhs);
 715   if (!new_rhs)
 716     return NULL_TREE;
 717   while (tree next = strip_sign_op_1 (new_rhs))
 718     new_rhs = next;
 719   return new_rhs;
 720 }
 721
 722 /* Start a change in the value of VAR that is suitable for all non-debug
 723    uses of VAR.  We need to make sure that debug statements continue to
 724    use the original definition of VAR where possible, or are nullified
 725    otherwise.  */
 726
 727 void
 728 backprop::prepare_change (tree var)
 729 {
 730   if (MAY_HAVE_DEBUG_STMTS)
 731     insert_debug_temp_for_var_def (NULL, var);
 732 }
 733
 734 /* STMT has been changed.  Give the fold machinery a chance to simplify
 735    and canonicalize it (e.g. by ensuring that commutative operands have
 736    the right order), then record the updates.  */
 737
 738 void
 739 backprop::complete_change (gimple *stmt)
 740 {
 741   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 742   if (fold_stmt (&gsi))
 743     {
 744       if (dump_file && (dump_flags & TDF_DETAILS))
 745         {
 746           fprintf (dump_file, "  which folds to: ");
 747           print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, TDF_SLIM);
 748         }
 749     }
 750   update_stmt (gsi_stmt (gsi));
 751 }
 752
 753 /* Optimize CALL, a call to a built-in function with lhs LHS, on the
 754    basis that INFO describes all uses of LHS.  */
 755
 756 void
 757 backprop::optimize_builtin_call (gcall *call, tree lhs, const usage_info *info)
 758 {
 759   /* If we have an f such that -f(x) = f(-x), and if the sign of the result
 760      doesn't matter, strip any sign operations from the input.  */
 761   if (info->flags.ignore_sign
 762       && negate_mathfn_p (gimple_call_combined_fn (call)))
 763     {
 764       tree new_arg = strip_sign_op (gimple_call_arg (call, 0));
 765       if (new_arg)
 766         {
 767           prepare_change (lhs);
 768           gimple_call_set_arg (call, 0, new_arg);
 769           complete_change (call);
 770         }
 771     }
 772 }
 773
 774 /* Optimize ASSIGN, an assignment to LHS, by replacing rhs operand N
 775    with RHS<N>, if RHS<N> is nonnull.  This may change the value of LHS.  */
 776
 777 void
 778 backprop::replace_assign_rhs (gassign *assign, tree lhs, tree rhs1,
 779                               tree rhs2, tree rhs3)
 780 {
 781   if (!rhs1 && !rhs2 && !rhs3)
 782     return;
 783
 784   prepare_change (lhs);
 785   if (rhs1)
 786     gimple_assign_set_rhs1 (assign, rhs1);
 787   if (rhs2)
 788     gimple_assign_set_rhs2 (assign, rhs2);
 789   if (rhs3)
 790     gimple_assign_set_rhs3 (assign, rhs3);
 791   complete_change (assign);
 792 }
 793
 794 /* Optimize ASSIGN, an assignment to LHS, on the basis that INFO
 795    describes all uses of LHS.  */
 796
 797 void
 798 backprop::optimize_assign (gassign *assign, tree lhs, const usage_info *info)
 799 {
 800   switch (gimple_assign_rhs_code (assign))
 801     {
 802     case MULT_EXPR:
 803     case RDIV_EXPR:
 804       /* If the sign of the result doesn't matter, strip sign operations
 805          from both inputs.  */
 806       if (info->flags.ignore_sign)
 807         replace_assign_rhs (assign, lhs,
 808                             strip_sign_op (gimple_assign_rhs1 (assign)),
 809                             strip_sign_op (gimple_assign_rhs2 (assign)),
 810                             NULL_TREE);
 811       break;
 812
 813     case COND_EXPR:
 814       /* If the sign of A ? B : C doesn't matter, strip sign operations
 815          from both B and C.  */
 816       if (info->flags.ignore_sign)
 817         replace_assign_rhs (assign, lhs,
 818                             NULL_TREE,
 819                             strip_sign_op (gimple_assign_rhs2 (assign)),
 820                             strip_sign_op (gimple_assign_rhs3 (assign)));
 821       break;
 822
 823     default:
 824       break;
 825     }
 826 }
 827
 828 /* Optimize PHI, which defines VAR, on the basis that INFO describes all
 829    uses of the result.  */
 830
 831 void
 832 backprop::optimize_phi (gphi *phi, tree var, const usage_info *info)
 833 {
 834   /* If the sign of the result doesn't matter, strip sign operations
 835      from all arguments.  */
 836   if (info->flags.ignore_sign)
 837     {
 838       use_operand_p use;
 839       ssa_op_iter oi;
 840       bool replaced = false;
 841       FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
 842         {
 843           tree new_arg = strip_sign_op (USE_FROM_PTR (use));
 844           if (new_arg)
 845             {
 846               if (!replaced)
 847                 prepare_change (var);
 848               if (dump_file && (dump_flags & TDF_DETAILS))
 849                 note_replacement (phi, USE_FROM_PTR (use), new_arg);
 850               replace_exp (use, new_arg);
 851               replaced = true;
 852             }
 853         }
 854     }
 855 }
 856
 857 void
 858 backprop::execute ()
 859 {
 860   /* Phase 1: Traverse the function, making optimistic assumptions
 861      about any phi whose definition we haven't seen.  */
 862   int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (m_fn));
 863   unsigned int postorder_num = post_order_compute (postorder, false, false);
 864   for (unsigned int i = 0; i < postorder_num; ++i)
 865     {
 866       process_block (BASIC_BLOCK_FOR_FN (m_fn, postorder[i]));
 867       bitmap_set_bit (m_visited_blocks, postorder[i]);
 868     }
 869   XDELETEVEC (postorder);
 870
 871   /* Phase 2: Use the initial (perhaps overly optimistic) information
 872      to create a maximal fixed point solution.  */
 873   while (!m_worklist.is_empty ())
 874     process_var (pop_from_worklist ());
 875
 876   if (dump_file && (dump_flags & TDF_DETAILS))
 877     fprintf (dump_file, "\n");
 878
 879   /* Phase 3: Do a reverse post-order walk, using information about
 880      the uses of SSA names to optimize their definitions.  */
 881   for (unsigned int i = m_vars.length (); i-- > 0;)
 882     {
 883       usage_info *info = m_vars[i].second;
 884       if (info->is_useful ())
 885         {
 886           tree var = m_vars[i].first;
 887           gimple *stmt = SSA_NAME_DEF_STMT (var);
 888           if (gcall *call = dyn_cast <gcall *> (stmt))
 889             optimize_builtin_call (call, var, info);
 890           else if (gassign *assign = dyn_cast <gassign *> (stmt))
 891             optimize_assign (assign, var, info);
 892           else if (gphi *phi = dyn_cast <gphi *> (stmt))
 893             optimize_phi (phi, var, info);
 894         }
 895     }
 896
 897   /* Phase 4: Do a post-order walk, deleting statements that are no
 898      longer needed.  */
 899   for (unsigned int i = 0; i < m_vars.length (); ++i)
 900     {
 901       tree var = m_vars[i].first;
 902       if (has_zero_uses (var))
 903         remove_unused_var (var);
 904     }
 905
 906   if (dump_file && (dump_flags & TDF_DETAILS))
 907     fprintf (dump_file, "\n");
 908 }
 909
 910 const pass_data pass_data_backprop =
 911 {
 912   GIMPLE_PASS, /* type */
 913   "backprop", /* name */
 914   OPTGROUP_NONE, /* optinfo_flags */
 915   TV_TREE_BACKPROP, /* tv_id */
 916   ( PROP_cfg | PROP_ssa ), /* properties_required */
 917   0, /* properties_provided */
 918   0, /* properties_destroyed */
 919   0, /* todo_flags_start */
 920   0, /* todo_flags_finish */
 921 };
 922
 923 class pass_backprop : public gimple_opt_pass
 924 {
 925 public:
 926   pass_backprop (gcc::context *ctxt)
 927     : gimple_opt_pass (pass_data_backprop, ctxt)
 928   {}
 929
 930   /* opt_pass methods: */
 931   opt_pass * clone () { return new pass_backprop (m_ctxt); }
 932   virtual bool gate (function *) { return flag_ssa_backprop; }
 933   virtual unsigned int execute (function *);
 934
 935 }; // class pass_backprop
 936
 937 unsigned int
 938 pass_backprop::execute (function *fn)
 939 {
 940   backprop (fn).execute ();
 941   return 0;
 942 }
 943
 944 } // anon namespace
 945
 946 gimple_opt_pass *
 947 make_pass_backprop (gcc::context *ctxt)
 948 {
 949   return new pass_backprop (ctxt);
 950 }