gcc/gimple-ssa-backprop.c

   1 /* Back-propagation of usage information to definitions.
   2    Copyright (C) 2015-2018 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);
 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   auto_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 (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   m_info_pool.release ();
 285 }
 286
 287 /* Return usage information for general operand OP, or null if none.  */
 288
 289 const usage_info *
 290 backprop::lookup_operand (tree op)
 291 {
 292   if (op && TREE_CODE (op) == SSA_NAME)
 293     {
 294       usage_info **slot = m_info_map.get (op);
 295       if (slot)
 296         return *slot;
 297     }
 298   return NULL;
 299 }
 300
 301 /* Add SSA name VAR to the worklist, if it isn't on the worklist already.  */
 302
 303 void
 304 backprop::push_to_worklist (tree var)
 305 {
 306   if (!bitmap_set_bit (m_worklist_names, SSA_NAME_VERSION (var)))
 307     return;
 308   m_worklist.safe_push (var);
 309   if (dump_file && (dump_flags & TDF_DETAILS))
 310     {
 311       fprintf (dump_file, "[WORKLIST] Pushing ");
 312       print_generic_expr (dump_file, var);
 313       fprintf (dump_file, "\n");
 314     }
 315 }
 316
 317 /* Remove and return the next SSA name from the worklist.  The worklist
 318    is known to be nonempty.  */
 319
 320 tree
 321 backprop::pop_from_worklist ()
 322 {
 323   tree var = m_worklist.pop ();
 324   bitmap_clear_bit (m_worklist_names, SSA_NAME_VERSION (var));
 325   if (dump_file && (dump_flags & TDF_DETAILS))
 326     {
 327       fprintf (dump_file, "[WORKLIST] Popping ");
 328       print_generic_expr (dump_file, var);
 329       fprintf (dump_file, "\n");
 330     }
 331   return var;
 332 }
 333
 334 /* Make INFO describe all uses of RHS in CALL, which is a call to a
 335    built-in function.  */
 336
 337 void
 338 backprop::process_builtin_call_use (gcall *call, tree rhs, usage_info *info)
 339 {
 340   combined_fn fn = gimple_call_combined_fn (call);
 341   tree lhs = gimple_call_lhs (call);
 342   switch (fn)
 343     {
 344     case CFN_LAST:
 345       break;
 346
 347     CASE_CFN_COS:
 348     CASE_CFN_COSH:
 349     CASE_CFN_CCOS:
 350     CASE_CFN_CCOSH:
 351     CASE_CFN_HYPOT:
 352       /* The signs of all inputs are ignored.  */
 353       info->flags.ignore_sign = true;
 354       break;
 355
 356     CASE_CFN_COPYSIGN:
 357     CASE_CFN_COPYSIGN_FN:
 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     CASE_CFN_FMA_FN:
 378       /* In X * X + Y, where Y is distinct from X, the sign of X doesn't
 379          matter.  */
 380       if (gimple_call_arg (call, 0) == rhs
 381           && gimple_call_arg (call, 1) == rhs
 382           && gimple_call_arg (call, 2) != rhs)
 383         info->flags.ignore_sign = true;
 384       break;
 385
 386     default:
 387       if (negate_mathfn_p (fn))
 388         {
 389           /* The sign of the (single) input doesn't matter provided
 390              that the sign of the output doesn't matter.  */
 391           const usage_info *lhs_info = lookup_operand (lhs);
 392           if (lhs_info)
 393             info->flags.ignore_sign = lhs_info->flags.ignore_sign;
 394         }
 395       break;
 396     }
 397 }
 398
 399 /* Make INFO describe all uses of RHS in ASSIGN.  */
 400
 401 void
 402 backprop::process_assign_use (gassign *assign, tree rhs, usage_info *info)
 403 {
 404   tree lhs = gimple_assign_lhs (assign);
 405   switch (gimple_assign_rhs_code (assign))
 406     {
 407     case ABS_EXPR:
 408       /* The sign of the input doesn't matter.  */
 409       info->flags.ignore_sign = true;
 410       break;
 411
 412     case COND_EXPR:
 413       /* For A = B ? C : D, propagate information about all uses of A
 414          to C and D.  */
 415       if (rhs != gimple_assign_rhs1 (assign))
 416         {
 417           const usage_info *lhs_info = lookup_operand (lhs);
 418           if (lhs_info)
 419             *info = *lhs_info;
 420         }
 421       break;
 422
 423     case FMA_EXPR:
 424       /* In X * X + Y, where Y is distinct from X, the sign of X doesn't
 425          matter.  */
 426       if (gimple_assign_rhs1 (assign) == rhs
 427           && gimple_assign_rhs2 (assign) == rhs
 428           && gimple_assign_rhs3 (assign) != rhs)
 429         info->flags.ignore_sign = true;
 430       break;
 431
 432     case MULT_EXPR:
 433       /* In X * X, the sign of X doesn't matter.  */
 434       if (gimple_assign_rhs1 (assign) == rhs
 435           && gimple_assign_rhs2 (assign) == rhs)
 436         info->flags.ignore_sign = true;
 437       /* Fall through.  */
 438
 439     case NEGATE_EXPR:
 440     case RDIV_EXPR:
 441       /* If the sign of the result doesn't matter, the sign of the inputs
 442          doesn't matter either.  */
 443       if (FLOAT_TYPE_P (TREE_TYPE (rhs)))
 444         {
 445           const usage_info *lhs_info = lookup_operand (lhs);
 446           if (lhs_info)
 447             info->flags.ignore_sign = lhs_info->flags.ignore_sign;
 448         }
 449       break;
 450
 451     default:
 452       break;
 453     }
 454 }
 455
 456 /* Make INFO describe the uses of PHI's result.  */
 457
 458 void
 459 backprop::process_phi_use (gphi *phi, usage_info *info)
 460 {
 461   tree result = gimple_phi_result (phi);
 462   if (const usage_info *result_info = lookup_operand (result))
 463     *info = *result_info;
 464 }
 465
 466 /* Make INFO describe all uses of RHS in STMT.  */
 467
 468 void
 469 backprop::process_use (gimple *stmt, tree rhs, usage_info *info)
 470 {
 471   if (dump_file && (dump_flags & TDF_DETAILS))
 472     {
 473       fprintf (dump_file, "[USE] ");
 474       print_generic_expr (dump_file, rhs);
 475       fprintf (dump_file, " in ");
 476       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 477     }
 478
 479   if (gcall *call = dyn_cast <gcall *> (stmt))
 480     process_builtin_call_use (call, rhs, info);
 481   else if (gassign *assign = dyn_cast <gassign *> (stmt))
 482     process_assign_use (assign, rhs, info);
 483   else if (gphi *phi = dyn_cast <gphi *> (stmt))
 484     process_phi_use (phi, info);
 485
 486   if (dump_file && (dump_flags & TDF_DETAILS))
 487     dump_usage_info (dump_file, rhs, info);
 488 }
 489
 490 /* Make INFO describe all uses of VAR, returning true if the result
 491    is useful.  If the uses include phis that haven't been processed yet,
 492    make the most optimistic assumption possible, so that we aim for
 493    a maximum rather than a minimum fixed point.  */
 494
 495 bool
 496 backprop::intersect_uses (tree var, usage_info *info)
 497 {
 498   imm_use_iterator iter;
 499   gimple *stmt;
 500   *info = usage_info::intersection_identity ();
 501   FOR_EACH_IMM_USE_STMT (stmt, iter, var)
 502     {
 503       if (is_gimple_debug (stmt))
 504         continue;
 505       if (is_a <gphi *> (stmt)
 506           && !bitmap_bit_p (m_visited_blocks, gimple_bb (stmt)->index))
 507         {
 508           /* Skip unprocessed phis.  */
 509           if (dump_file && (dump_flags & TDF_DETAILS))
 510             {
 511               fprintf (dump_file, "[BACKEDGE] ");
 512               print_generic_expr (dump_file, var);
 513               fprintf (dump_file, " in ");
 514               print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 515             }
 516         }
 517       else
 518         {
 519           usage_info subinfo;
 520           process_use (stmt, var, &subinfo);
 521           *info &= subinfo;
 522           if (!info->is_useful ())
 523             {
 524               BREAK_FROM_IMM_USE_STMT (iter);
 525               return false;
 526             }
 527         }
 528     }
 529   return true;
 530 }
 531
 532 /* Queue for reconsideration any input of STMT that has information
 533    associated with it.  This is used if that information might be
 534    too optimistic.  */
 535
 536 void
 537 backprop::reprocess_inputs (gimple *stmt)
 538 {
 539   use_operand_p use_p;
 540   ssa_op_iter oi;
 541   FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
 542     {
 543       tree var = get_use_from_ptr (use_p);
 544       if (lookup_operand (var))
 545         push_to_worklist (var);
 546     }
 547 }
 548
 549 /* Say that we're recording INFO for SSA name VAR, or that we're deleting
 550    existing information if INFO is null.  INTRO describes the change.  */
 551
 552 static void
 553 dump_var_info (tree var, usage_info *info, const char *intro)
 554 {
 555   fprintf (dump_file, "[DEF] %s for ", intro);
 556   print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (var), 0, TDF_SLIM);
 557   if (info)
 558     dump_usage_info (dump_file, var, info);
 559 }
 560
 561 /* Process all uses of VAR and record or update the result in
 562    M_INFO_MAP and M_VARS.  */
 563
 564 void
 565 backprop::process_var (tree var)
 566 {
 567   if (has_zero_uses (var))
 568     return;
 569
 570   usage_info info;
 571   intersect_uses (var, &info);
 572
 573   gimple *stmt = SSA_NAME_DEF_STMT (var);
 574   if (info.is_useful ())
 575     {
 576       bool existed;
 577       usage_info *&map_info = m_info_map.get_or_insert (var, &existed);
 578       if (!existed)
 579         {
 580           /* Recording information about VAR for the first time.  */
 581           map_info = m_info_pool.allocate ();
 582           *map_info = info;
 583           m_vars.safe_push (var_info_pair (var, map_info));
 584           if (dump_file && (dump_flags & TDF_DETAILS))
 585             dump_var_info (var, map_info, "Recording new information");
 586
 587           /* If STMT is a phi, reprocess any backedge uses.  This is a
 588              no-op for other uses, which won't have any information
 589              associated with them.  */
 590           if (is_a <gphi *> (stmt))
 591             reprocess_inputs (stmt);
 592         }
 593       else if (info != *map_info)
 594         {
 595           /* Recording information that is less optimistic than before.  */
 596           gcc_checking_assert ((info & *map_info) == info);
 597           *map_info = info;
 598           if (dump_file && (dump_flags & TDF_DETAILS))
 599             dump_var_info (var, map_info, "Updating information");
 600           reprocess_inputs (stmt);
 601         }
 602     }
 603   else
 604     {
 605       if (usage_info **slot = m_info_map.get (var))
 606         {
 607           /* Removing previously-recorded information.  */
 608           **slot = info;
 609           m_info_map.remove (var);
 610           if (dump_file && (dump_flags & TDF_DETAILS))
 611             dump_var_info (var, NULL, "Deleting information");
 612           reprocess_inputs (stmt);
 613         }
 614       else
 615         {
 616           /* If STMT is a phi, remove any information recorded for
 617              its arguments.  */
 618           if (is_a <gphi *> (stmt))
 619             reprocess_inputs (stmt);
 620         }
 621     }
 622 }
 623
 624 /* Process all statements and phis in BB, during the first post-order walk.  */
 625
 626 void
 627 backprop::process_block (basic_block bb)
 628 {
 629   for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);
 630        gsi_prev (&gsi))
 631     {
 632       tree lhs = gimple_get_lhs (gsi_stmt (gsi));
 633       if (lhs && TREE_CODE (lhs) == SSA_NAME)
 634         process_var (lhs);
 635     }
 636   for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi);
 637        gsi_next (&gpi))
 638     process_var (gimple_phi_result (gpi.phi ()));
 639 }
 640
 641 /* Delete the definition of VAR, which has no uses.  */
 642
 643 static void
 644 remove_unused_var (tree var)
 645 {
 646   gimple *stmt = SSA_NAME_DEF_STMT (var);
 647   if (dump_file && (dump_flags & TDF_DETAILS))
 648     {
 649       fprintf (dump_file, "Deleting ");
 650       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 651     }
 652   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 653   gsi_remove (&gsi, true);
 654   release_defs (stmt);
 655 }
 656
 657 /* Note that we're replacing OLD_RHS with NEW_RHS in STMT.  */
 658
 659 static void
 660 note_replacement (gimple *stmt, tree old_rhs, tree new_rhs)
 661 {
 662   fprintf (dump_file, "Replacing use of ");
 663   print_generic_expr (dump_file, old_rhs);
 664   fprintf (dump_file, " with ");
 665   print_generic_expr (dump_file, new_rhs);
 666   fprintf (dump_file, " in ");
 667   print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 668 }
 669
 670 /* If RHS is an SSA name whose definition just changes the sign of a value,
 671    return that other value, otherwise return null.  */
 672
 673 static tree
 674 strip_sign_op_1 (tree rhs)
 675 {
 676   if (TREE_CODE (rhs) != SSA_NAME)
 677     return NULL_TREE;
 678
 679   gimple *def_stmt = SSA_NAME_DEF_STMT (rhs);
 680   if (gassign *assign = dyn_cast <gassign *> (def_stmt))
 681     switch (gimple_assign_rhs_code (assign))
 682       {
 683       case ABS_EXPR:
 684       case NEGATE_EXPR:
 685         return gimple_assign_rhs1 (assign);
 686
 687       default:
 688         break;
 689       }
 690   else if (gcall *call = dyn_cast <gcall *> (def_stmt))
 691     switch (gimple_call_combined_fn (call))
 692       {
 693       CASE_CFN_COPYSIGN:
 694       CASE_CFN_COPYSIGN_FN:
 695         return gimple_call_arg (call, 0);
 696
 697       default:
 698         break;
 699       }
 700
 701   return NULL_TREE;
 702 }
 703
 704 /* If RHS is an SSA name whose definition just changes the sign of a value,
 705    strip all such operations and return the ultimate input to them.
 706    Return null otherwise.
 707
 708    Although this could in principle lead to quadratic searching,
 709    in practice a long sequence of sign manipulations should already
 710    have been folded down.  E.g. --x -> x, abs(-x) -> abs(x).  We search
 711    for more than one operation in order to catch cases like -abs(x).  */
 712
 713 static tree
 714 strip_sign_op (tree rhs)
 715 {
 716   tree new_rhs = strip_sign_op_1 (rhs);
 717   if (!new_rhs)
 718     return NULL_TREE;
 719   while (tree next = strip_sign_op_1 (new_rhs))
 720     new_rhs = next;
 721   return new_rhs;
 722 }
 723
 724 /* Start a change in the value of VAR that is suitable for all non-debug
 725    uses of VAR.  We need to make sure that debug statements continue to
 726    use the original definition of VAR where possible, or are nullified
 727    otherwise.  */
 728
 729 void
 730 backprop::prepare_change (tree var)
 731 {
 732   if (MAY_HAVE_DEBUG_BIND_STMTS)
 733     insert_debug_temp_for_var_def (NULL, var);
 734   reset_flow_sensitive_info (var);
 735 }
 736
 737 /* STMT has been changed.  Give the fold machinery a chance to simplify
 738    and canonicalize it (e.g. by ensuring that commutative operands have
 739    the right order), then record the updates.  */
 740
 741 void
 742 backprop::complete_change (gimple *stmt)
 743 {
 744   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 745   if (fold_stmt (&gsi))
 746     {
 747       if (dump_file && (dump_flags & TDF_DETAILS))
 748         {
 749           fprintf (dump_file, "  which folds to: ");
 750           print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, TDF_SLIM);
 751         }
 752     }
 753   update_stmt (gsi_stmt (gsi));
 754 }
 755
 756 /* Optimize CALL, a call to a built-in function with lhs LHS, on the
 757    basis that INFO describes all uses of LHS.  */
 758
 759 void
 760 backprop::optimize_builtin_call (gcall *call, tree lhs, const usage_info *info)
 761 {
 762   /* If we have an f such that -f(x) = f(-x), and if the sign of the result
 763      doesn't matter, strip any sign operations from the input.  */
 764   if (info->flags.ignore_sign
 765       && negate_mathfn_p (gimple_call_combined_fn (call)))
 766     {
 767       tree new_arg = strip_sign_op (gimple_call_arg (call, 0));
 768       if (new_arg)
 769         {
 770           prepare_change (lhs);
 771           gimple_call_set_arg (call, 0, new_arg);
 772           complete_change (call);
 773         }
 774     }
 775 }
 776
 777 /* Optimize ASSIGN, an assignment to LHS, by replacing rhs operand N
 778    with RHS<N>, if RHS<N> is nonnull.  This may change the value of LHS.  */
 779
 780 void
 781 backprop::replace_assign_rhs (gassign *assign, tree lhs, tree rhs1,
 782                               tree rhs2, tree rhs3)
 783 {
 784   if (!rhs1 && !rhs2 && !rhs3)
 785     return;
 786
 787   prepare_change (lhs);
 788   if (rhs1)
 789     gimple_assign_set_rhs1 (assign, rhs1);
 790   if (rhs2)
 791     gimple_assign_set_rhs2 (assign, rhs2);
 792   if (rhs3)
 793     gimple_assign_set_rhs3 (assign, rhs3);
 794   complete_change (assign);
 795 }
 796
 797 /* Optimize ASSIGN, an assignment to LHS, on the basis that INFO
 798    describes all uses of LHS.  */
 799
 800 void
 801 backprop::optimize_assign (gassign *assign, tree lhs, const usage_info *info)
 802 {
 803   switch (gimple_assign_rhs_code (assign))
 804     {
 805     case MULT_EXPR:
 806     case RDIV_EXPR:
 807       /* If the sign of the result doesn't matter, strip sign operations
 808          from both inputs.  */
 809       if (info->flags.ignore_sign)
 810         replace_assign_rhs (assign, lhs,
 811                             strip_sign_op (gimple_assign_rhs1 (assign)),
 812                             strip_sign_op (gimple_assign_rhs2 (assign)),
 813                             NULL_TREE);
 814       break;
 815
 816     case COND_EXPR:
 817       /* If the sign of A ? B : C doesn't matter, strip sign operations
 818          from both B and C.  */
 819       if (info->flags.ignore_sign)
 820         replace_assign_rhs (assign, lhs,
 821                             NULL_TREE,
 822                             strip_sign_op (gimple_assign_rhs2 (assign)),
 823                             strip_sign_op (gimple_assign_rhs3 (assign)));
 824       break;
 825
 826     default:
 827       break;
 828     }
 829 }
 830
 831 /* Optimize PHI, which defines VAR, on the basis that INFO describes all
 832    uses of the result.  */
 833
 834 void
 835 backprop::optimize_phi (gphi *phi, tree var, const usage_info *info)
 836 {
 837   /* If the sign of the result doesn't matter, try to strip sign operations
 838      from arguments.  */
 839   if (info->flags.ignore_sign)
 840     {
 841       basic_block bb = gimple_bb (phi);
 842       use_operand_p use;
 843       ssa_op_iter oi;
 844       bool replaced = false;
 845       FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
 846         {
 847           /* Propagating along abnormal edges is delicate, punt for now.  */
 848           const int index = PHI_ARG_INDEX_FROM_USE (use);
 849           if (EDGE_PRED (bb, index)->flags & EDGE_ABNORMAL)
 850             continue;
 851
 852           tree new_arg = strip_sign_op (USE_FROM_PTR (use));
 853           if (new_arg)
 854             {
 855               if (!replaced)
 856                 prepare_change (var);
 857               if (dump_file && (dump_flags & TDF_DETAILS))
 858                 note_replacement (phi, USE_FROM_PTR (use), new_arg);
 859               replace_exp (use, new_arg);
 860               replaced = true;
 861             }
 862         }
 863     }
 864 }
 865
 866 void
 867 backprop::execute ()
 868 {
 869   /* Phase 1: Traverse the function, making optimistic assumptions
 870      about any phi whose definition we haven't seen.  */
 871   int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (m_fn));
 872   unsigned int postorder_num = post_order_compute (postorder, false, false);
 873   for (unsigned int i = 0; i < postorder_num; ++i)
 874     {
 875       process_block (BASIC_BLOCK_FOR_FN (m_fn, postorder[i]));
 876       bitmap_set_bit (m_visited_blocks, postorder[i]);
 877     }
 878   XDELETEVEC (postorder);
 879
 880   /* Phase 2: Use the initial (perhaps overly optimistic) information
 881      to create a maximal fixed point solution.  */
 882   while (!m_worklist.is_empty ())
 883     process_var (pop_from_worklist ());
 884
 885   if (dump_file && (dump_flags & TDF_DETAILS))
 886     fprintf (dump_file, "\n");
 887
 888   /* Phase 3: Do a reverse post-order walk, using information about
 889      the uses of SSA names to optimize their definitions.  */
 890   for (unsigned int i = m_vars.length (); i-- > 0;)
 891     {
 892       usage_info *info = m_vars[i].second;
 893       if (info->is_useful ())
 894         {
 895           tree var = m_vars[i].first;
 896           gimple *stmt = SSA_NAME_DEF_STMT (var);
 897           if (gcall *call = dyn_cast <gcall *> (stmt))
 898             optimize_builtin_call (call, var, info);
 899           else if (gassign *assign = dyn_cast <gassign *> (stmt))
 900             optimize_assign (assign, var, info);
 901           else if (gphi *phi = dyn_cast <gphi *> (stmt))
 902             optimize_phi (phi, var, info);
 903         }
 904     }
 905
 906   /* Phase 4: Do a post-order walk, deleting statements that are no
 907      longer needed.  */
 908   for (unsigned int i = 0; i < m_vars.length (); ++i)
 909     {
 910       tree var = m_vars[i].first;
 911       if (has_zero_uses (var))
 912         remove_unused_var (var);
 913     }
 914
 915   if (dump_file && (dump_flags & TDF_DETAILS))
 916     fprintf (dump_file, "\n");
 917 }
 918
 919 const pass_data pass_data_backprop =
 920 {
 921   GIMPLE_PASS, /* type */
 922   "backprop", /* name */
 923   OPTGROUP_NONE, /* optinfo_flags */
 924   TV_TREE_BACKPROP, /* tv_id */
 925   ( PROP_cfg | PROP_ssa ), /* properties_required */
 926   0, /* properties_provided */
 927   0, /* properties_destroyed */
 928   0, /* todo_flags_start */
 929   0, /* todo_flags_finish */
 930 };
 931
 932 class pass_backprop : public gimple_opt_pass
 933 {
 934 public:
 935   pass_backprop (gcc::context *ctxt)
 936     : gimple_opt_pass (pass_data_backprop, ctxt)
 937   {}
 938
 939   /* opt_pass methods: */
 940   opt_pass * clone () { return new pass_backprop (m_ctxt); }
 941   virtual bool gate (function *) { return flag_ssa_backprop; }
 942   virtual unsigned int execute (function *);
 943
 944 }; // class pass_backprop
 945
 946 unsigned int
 947 pass_backprop::execute (function *fn)
 948 {
 949   backprop (fn).execute ();
 950   return 0;
 951 }
 952
 953 } // anon namespace
 954
 955 gimple_opt_pass *
 956 make_pass_backprop (gcc::context *ctxt)
 957 {
 958   return new pass_backprop (ctxt);
 959 }