gcc/gimple-ssa-backprop.cc

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