gcc/gimple-ssa-backprop.c

   1 /* Back-propagation of usage information to definitions.
   2    Copyright (C) 2015 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 3, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 /* 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
 106 namespace {
 107
 108 /* Information about a group of uses of an SSA name.  */
 109 struct usage_info
 110 {
 111   usage_info () : flag_word (0) {}
 112   usage_info &operator &= (const usage_info &);
 113   usage_info operator & (const usage_info &) const;
 114   bool operator == (const usage_info &) const;
 115   bool operator != (const usage_info &) const;
 116   bool is_useful () const;
 117
 118   static usage_info intersection_identity ();
 119
 120   union
 121   {
 122     struct
 123     {
 124       /* True if the uses treat x and -x in the same way.  */
 125       unsigned int ignore_sign : 1;
 126     } flags;
 127     /* All the flag bits as a single int.  */
 128     unsigned int flag_word;
 129   };
 130 };
 131
 132 /* Return an X such that X & Y == Y for all Y.  This is the most
 133    optimistic assumption possible.  */
 134
 135 usage_info
 136 usage_info::intersection_identity ()
 137 {
 138   usage_info ret;
 139   ret.flag_word = -1;
 140   return ret;
 141 }
 142
 143 /* Intersect *THIS with OTHER, so that *THIS describes all uses covered
 144    by the original *THIS and OTHER.  */
 145
 146 usage_info &
 147 usage_info::operator &= (const usage_info &other)
 148 {
 149   flag_word &= other.flag_word;
 150   return *this;
 151 }
 152
 153 /* Return the intersection of *THIS and OTHER, i.e. a structure that
 154    describes all uses covered by *THIS and OTHER.  */
 155
 156 usage_info
 157 usage_info::operator & (const usage_info &other) const
 158 {
 159   usage_info info (*this);
 160   info &= other;
 161   return info;
 162 }
 163
 164 bool
 165 usage_info::operator == (const usage_info &other) const
 166 {
 167   return flag_word == other.flag_word;
 168 }
 169
 170 bool
 171 usage_info::operator != (const usage_info &other) const
 172 {
 173   return !operator == (other);
 174 }
 175
 176 /* Return true if *THIS is not simply the default, safe assumption.  */
 177
 178 bool
 179 usage_info::is_useful () const
 180 {
 181   return flag_word != 0;
 182 }
 183
 184 /* Start a dump line about SSA name VAR.  */
 185
 186 static void
 187 dump_usage_prefix (FILE *file, tree var)
 188 {
 189   fprintf (file, "  ");
 190   print_generic_expr (file, var, 0);
 191   fprintf (file, ": ");
 192 }
 193
 194 /* Print INFO to FILE.  */
 195
 196 static void
 197 dump_usage_info (FILE *file, tree var, usage_info *info)
 198 {
 199   if (info->flags.ignore_sign)
 200     {
 201       dump_usage_prefix (file, var);
 202       fprintf (file, "sign bit not important\n");
 203     }
 204 }
 205
 206 /* Represents one execution of the pass.  */
 207 class backprop
 208 {
 209 public:
 210   backprop (function *);
 211   ~backprop ();
 212
 213   void execute ();
 214
 215 private:
 216   const usage_info *lookup_operand (tree);
 217
 218   void push_to_worklist (tree);
 219   tree pop_from_worklist ();
 220
 221   void process_builtin_call_use (gcall *, tree, usage_info *);
 222   void process_assign_use (gassign *, tree, usage_info *);
 223   void process_phi_use (gphi *, usage_info *);
 224   void process_use (gimple *, tree, usage_info *);
 225   bool intersect_uses (tree, usage_info *);
 226   void reprocess_inputs (gimple *);
 227   void process_var (tree);
 228   void process_block (basic_block);
 229
 230   void prepare_change (tree);
 231   void complete_change (gimple *);
 232   void optimize_builtin_call (gcall *, tree, const usage_info *);
 233   void replace_assign_rhs (gassign *, tree, tree, tree, tree);
 234   void optimize_assign (gassign *, tree, const usage_info *);
 235   void optimize_phi (gphi *, tree, const usage_info *);
 236
 237   typedef hash_map <tree_ssa_name_hash, usage_info *> info_map_type;
 238   typedef std::pair <tree, usage_info *> var_info_pair;
 239
 240   /* The function we're optimizing.  */
 241   function *m_fn;
 242
 243   /* Pool for allocating usage_info structures.  */
 244   object_allocator <usage_info> m_info_pool;
 245
 246   /* Maps an SSA name to a description of all uses of that SSA name.
 247      All the usage_infos satisfy is_useful.
 248
 249      We use a hash_map because the map is expected to be sparse
 250      (i.e. most SSA names won't have useful information attached to them).
 251      We could move to a directly-indexed array if that situation changes.  */
 252   info_map_type m_info_map;
 253
 254   /* Post-ordered list of all potentially-interesting SSA names,
 255      along with information that describes all uses.  */
 256   auto_vec <var_info_pair, 128> m_vars;
 257
 258   /* A bitmap of blocks that we have finished processing in the initial
 259      post-order walk.  */
 260   sbitmap m_visited_blocks;
 261
 262   /* A worklist of SSA names whose definitions need to be reconsidered.  */
 263   auto_vec <tree, 64> m_worklist;
 264
 265   /* The SSA names in M_WORKLIST, identified by their SSA_NAME_VERSION.
 266      We use a bitmap rather than an sbitmap because most SSA names are
 267      never added to the worklist.  */
 268   bitmap m_worklist_names;
 269 };
 270
 271 backprop::backprop (function *fn)
 272   : m_fn (fn),
 273     m_info_pool ("usage_info"),
 274     m_visited_blocks (sbitmap_alloc (last_basic_block_for_fn (m_fn))),
 275     m_worklist_names (BITMAP_ALLOC (NULL))
 276 {
 277   bitmap_clear (m_visited_blocks);
 278 }
 279
 280 backprop::~backprop ()
 281 {
 282   BITMAP_FREE (m_worklist_names);
 283   sbitmap_free (m_visited_blocks);
 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, 0);
 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, 0);
 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   enum built_in_function fn = DECL_FUNCTION_CODE (gimple_call_fndecl (call));
 341   tree lhs = gimple_call_lhs (call);
 342   switch (fn)
 343     {
 344     CASE_FLT_FN (BUILT_IN_COS):
 345     CASE_FLT_FN (BUILT_IN_COSH):
 346     CASE_FLT_FN (BUILT_IN_CCOS):
 347     CASE_FLT_FN (BUILT_IN_CCOSH):
 348     CASE_FLT_FN (BUILT_IN_HYPOT):
 349       /* The signs of all inputs are ignored.  */
 350       info->flags.ignore_sign = true;
 351       break;
 352
 353     CASE_FLT_FN (BUILT_IN_COPYSIGN):
 354       /* The sign of the first input is ignored.  */
 355       if (rhs != gimple_call_arg (call, 1))
 356         info->flags.ignore_sign = true;
 357       break;
 358
 359     CASE_FLT_FN (BUILT_IN_POW):
 360       {
 361         /* The sign of the first input is ignored as long as the second
 362            input is an even real.  */
 363         tree power = gimple_call_arg (call, 1);
 364         HOST_WIDE_INT n;
 365         if (TREE_CODE (power) == REAL_CST
 366             && real_isinteger (&TREE_REAL_CST (power), &n)
 367             && (n & 1) == 0)
 368           info->flags.ignore_sign = true;
 369         break;
 370       }
 371
 372     CASE_FLT_FN (BUILT_IN_FMA):
 373       /* In X * X + Y, where Y is distinct from X, the sign of X doesn't
 374          matter.  */
 375       if (gimple_call_arg (call, 0) == rhs
 376           && gimple_call_arg (call, 1) == rhs
 377           && gimple_call_arg (call, 2) != rhs)
 378         info->flags.ignore_sign = true;
 379       break;
 380
 381     default:
 382       if (negate_mathfn_p (fn))
 383         {
 384           /* The sign of the (single) input doesn't matter provided
 385              that the sign of the output doesn't matter.  */
 386           const usage_info *lhs_info = lookup_operand (lhs);
 387           if (lhs_info)
 388             info->flags.ignore_sign = lhs_info->flags.ignore_sign;
 389         }
 390       break;
 391     }
 392 }
 393
 394 /* Make INFO describe all uses of RHS in ASSIGN.  */
 395
 396 void
 397 backprop::process_assign_use (gassign *assign, tree rhs, usage_info *info)
 398 {
 399   tree lhs = gimple_assign_lhs (assign);
 400   switch (gimple_assign_rhs_code (assign))
 401     {
 402     case ABS_EXPR:
 403       /* The sign of the input doesn't matter.  */
 404       info->flags.ignore_sign = true;
 405       break;
 406
 407     case COND_EXPR:
 408       /* For A = B ? C : D, propagate information about all uses of A
 409          to C and D.  */
 410       if (rhs != gimple_assign_rhs1 (assign))
 411         {
 412           const usage_info *lhs_info = lookup_operand (lhs);
 413           if (lhs_info)
 414             *info = *lhs_info;
 415         }
 416       break;
 417
 418     case FMA_EXPR:
 419       /* In X * X + Y, where Y is distinct from X, the sign of X doesn't
 420          matter.  */
 421       if (gimple_assign_rhs1 (assign) == rhs
 422           && gimple_assign_rhs2 (assign) == rhs
 423           && gimple_assign_rhs3 (assign) != rhs)
 424         info->flags.ignore_sign = true;
 425       break;
 426
 427     case MULT_EXPR:
 428       /* In X * X, the sign of X doesn't matter.  */
 429       if (gimple_assign_rhs1 (assign) == rhs
 430           && gimple_assign_rhs2 (assign) == rhs)
 431         info->flags.ignore_sign = true;
 432       /* Fall through.  */
 433
 434     case NEGATE_EXPR:
 435     case RDIV_EXPR:
 436       /* If the sign of the result doesn't matter, the sign of the inputs
 437          doesn't matter either.  */
 438       if (FLOAT_TYPE_P (TREE_TYPE (rhs)))
 439         {
 440           const usage_info *lhs_info = lookup_operand (lhs);
 441           if (lhs_info)
 442             info->flags.ignore_sign = lhs_info->flags.ignore_sign;
 443         }
 444       break;
 445
 446     default:
 447       break;
 448     }
 449 }
 450
 451 /* Make INFO describe the uses of PHI's result.  */
 452
 453 void
 454 backprop::process_phi_use (gphi *phi, usage_info *info)
 455 {
 456   tree result = gimple_phi_result (phi);
 457   if (const usage_info *result_info = lookup_operand (result))
 458     *info = *result_info;
 459 }
 460
 461 /* Make INFO describe all uses of RHS in STMT.  */
 462
 463 void
 464 backprop::process_use (gimple *stmt, tree rhs, usage_info *info)
 465 {
 466   if (dump_file && (dump_flags & TDF_DETAILS))
 467     {
 468       fprintf (dump_file, "[USE] ");
 469       print_generic_expr (dump_file, rhs, 0);
 470       fprintf (dump_file, " in ");
 471       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 472     }
 473
 474   if (gcall *call = dyn_cast <gcall *> (stmt))
 475     {
 476       if (gimple_call_builtin_p (call, BUILT_IN_NORMAL))
 477         process_builtin_call_use (call, rhs, info);
 478     }
 479   else if (gassign *assign = dyn_cast <gassign *> (stmt))
 480     process_assign_use (assign, rhs, info);
 481   else if (gphi *phi = dyn_cast <gphi *> (stmt))
 482     process_phi_use (phi, info);
 483
 484   if (dump_file && (dump_flags & TDF_DETAILS))
 485     dump_usage_info (dump_file, rhs, info);
 486 }
 487
 488 /* Make INFO describe all uses of VAR, returning true if the result
 489    is useful.  If the uses include phis that haven't been processed yet,
 490    make the most optimistic assumption possible, so that we aim for
 491    a maximum rather than a minimum fixed point.  */
 492
 493 bool
 494 backprop::intersect_uses (tree var, usage_info *info)
 495 {
 496   imm_use_iterator iter;
 497   gimple *stmt;
 498   *info = usage_info::intersection_identity ();
 499   FOR_EACH_IMM_USE_STMT (stmt, iter, var)
 500     {
 501       if (is_gimple_debug (stmt))
 502         continue;
 503       if (is_a <gphi *> (stmt)
 504           && !bitmap_bit_p (m_visited_blocks, gimple_bb (stmt)->index))
 505         {
 506           /* Skip unprocessed phis.  */
 507           if (dump_file && (dump_flags & TDF_DETAILS))
 508             {
 509               fprintf (dump_file, "[BACKEDGE] ");
 510               print_generic_expr (dump_file, var, 0);
 511               fprintf (dump_file, " in ");
 512               print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 513             }
 514         }
 515       else
 516         {
 517           usage_info subinfo;
 518           process_use (stmt, var, &subinfo);
 519           *info &= subinfo;
 520           if (!info->is_useful ())
 521             {
 522               BREAK_FROM_IMM_USE_STMT (iter);
 523               return false;
 524             }
 525         }
 526     }
 527   return true;
 528 }
 529
 530 /* Queue for reconsideration any input of STMT that has information
 531    associated with it.  This is used if that information might be
 532    too optimistic.  */
 533
 534 void
 535 backprop::reprocess_inputs (gimple *stmt)
 536 {
 537   use_operand_p use_p;
 538   ssa_op_iter oi;
 539   FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
 540     {
 541       tree var = get_use_from_ptr (use_p);
 542       if (lookup_operand (var))
 543         push_to_worklist (var);
 544     }
 545 }
 546
 547 /* Say that we're recording INFO for SSA name VAR, or that we're deleting
 548    existing information if INFO is null.  INTRO describes the change.  */
 549
 550 static void
 551 dump_var_info (tree var, usage_info *info, const char *intro)
 552 {
 553   fprintf (dump_file, "[DEF] %s for ", intro);
 554   print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (var), 0, TDF_SLIM);
 555   if (info)
 556     dump_usage_info (dump_file, var, info);
 557 }
 558
 559 /* Process all uses of VAR and record or update the result in
 560    M_INFO_MAP and M_VARS.  */
 561
 562 void
 563 backprop::process_var (tree var)
 564 {
 565   if (has_zero_uses (var))
 566     return;
 567
 568   usage_info info;
 569   intersect_uses (var, &info);
 570
 571   gimple *stmt = SSA_NAME_DEF_STMT (var);
 572   if (info.is_useful ())
 573     {
 574       bool existed;
 575       usage_info *&map_info = m_info_map.get_or_insert (var, &existed);
 576       if (!existed)
 577         {
 578           /* Recording information about VAR for the first time.  */
 579           map_info = m_info_pool.allocate ();
 580           *map_info = info;
 581           m_vars.safe_push (var_info_pair (var, map_info));
 582           if (dump_file && (dump_flags & TDF_DETAILS))
 583             dump_var_info (var, map_info, "Recording new information");
 584
 585           /* If STMT is a phi, reprocess any backedge uses.  This is a
 586              no-op for other uses, which won't have any information
 587              associated with them.  */
 588           if (is_a <gphi *> (stmt))
 589             reprocess_inputs (stmt);
 590         }
 591       else if (info != *map_info)
 592         {
 593           /* Recording information that is less optimistic than before.  */
 594           gcc_checking_assert ((info & *map_info) == info);
 595           *map_info = info;
 596           if (dump_file && (dump_flags & TDF_DETAILS))
 597             dump_var_info (var, map_info, "Updating information");
 598           reprocess_inputs (stmt);
 599         }
 600     }
 601   else
 602     {
 603       if (usage_info **slot = m_info_map.get (var))
 604         {
 605           /* Removing previously-recorded information.  */
 606           **slot = info;
 607           m_info_map.remove (var);
 608           if (dump_file && (dump_flags & TDF_DETAILS))
 609             dump_var_info (var, NULL, "Deleting information");
 610           reprocess_inputs (stmt);
 611         }
 612       else
 613         {
 614           /* If STMT is a phi, remove any information recorded for
 615              its arguments.  */
 616           if (is_a <gphi *> (stmt))
 617             reprocess_inputs (stmt);
 618         }
 619     }
 620 }
 621
 622 /* Process all statements and phis in BB, during the first post-order walk.  */
 623
 624 void
 625 backprop::process_block (basic_block bb)
 626 {
 627   for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);
 628        gsi_prev (&gsi))
 629     {
 630       tree lhs = gimple_get_lhs (gsi_stmt (gsi));
 631       if (lhs && TREE_CODE (lhs) == SSA_NAME)
 632         process_var (lhs);
 633     }
 634   for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi);
 635        gsi_next (&gpi))
 636     process_var (gimple_phi_result (gpi.phi ()));
 637 }
 638
 639 /* Delete the definition of VAR, which has no uses.  */
 640
 641 static void
 642 remove_unused_var (tree var)
 643 {
 644   gimple *stmt = SSA_NAME_DEF_STMT (var);
 645   if (dump_file && (dump_flags & TDF_DETAILS))
 646     {
 647       fprintf (dump_file, "Deleting ");
 648       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 649     }
 650   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 651   gsi_remove (&gsi, true);
 652   release_defs (stmt);
 653 }
 654
 655 /* Note that we're replacing OLD_RHS with NEW_RHS in STMT.  */
 656
 657 static void
 658 note_replacement (gimple *stmt, tree old_rhs, tree new_rhs)
 659 {
 660   fprintf (dump_file, "Replacing use of ");
 661   print_generic_expr (dump_file, old_rhs, 0);
 662   fprintf (dump_file, " with ");
 663   print_generic_expr (dump_file, new_rhs, 0);
 664   fprintf (dump_file, " in ");
 665   print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 666 }
 667
 668 /* If RHS is an SSA name whose definition just changes the sign of a value,
 669    return that other value, otherwise return null.  */
 670
 671 static tree
 672 strip_sign_op_1 (tree rhs)
 673 {
 674   if (TREE_CODE (rhs) != SSA_NAME)
 675     return NULL_TREE;
 676
 677   gimple *def_stmt = SSA_NAME_DEF_STMT (rhs);
 678   if (gassign *assign = dyn_cast <gassign *> (def_stmt))
 679     switch (gimple_assign_rhs_code (assign))
 680       {
 681       case ABS_EXPR:
 682       case NEGATE_EXPR:
 683         return gimple_assign_rhs1 (assign);
 684
 685       default:
 686         break;
 687       }
 688   else if (gcall *call = dyn_cast <gcall *> (def_stmt))
 689     {
 690       if (gimple_call_builtin_p (call, BUILT_IN_NORMAL))
 691         switch (DECL_FUNCTION_CODE (gimple_call_fndecl (call)))
 692           {
 693           CASE_FLT_FN (BUILT_IN_COPYSIGN):
 694             return gimple_call_arg (call, 0);
 695
 696           default:
 697             break;
 698           }
 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_STMTS)
 733     insert_debug_temp_for_var_def (NULL, var);
 734 }
 735
 736 /* STMT has been changed.  Give the fold machinery a chance to simplify
 737    and canonicalize it (e.g. by ensuring that commutative operands have
 738    the right order), then record the updates.  */
 739
 740 void
 741 backprop::complete_change (gimple *stmt)
 742 {
 743   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 744   if (fold_stmt (&gsi))
 745     {
 746       if (dump_file && (dump_flags & TDF_DETAILS))
 747         {
 748           fprintf (dump_file, "  which folds to: ");
 749           print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, TDF_SLIM);
 750         }
 751     }
 752   update_stmt (gsi_stmt (gsi));
 753 }
 754
 755 /* Optimize CALL, a call to a built-in function with lhs LHS, on the
 756    basis that INFO describes all uses of LHS.  */
 757
 758 void
 759 backprop::optimize_builtin_call (gcall *call, tree lhs, const usage_info *info)
 760 {
 761   tree fndecl = gimple_call_fndecl (call);
 762   enum built_in_function fn = DECL_FUNCTION_CODE (fndecl);
 763   /* If we have an f such that -f(x) = f(-x), and if the sign of the result
 764      doesn't matter, strip any sign operations from the input.  */
 765   if (info->flags.ignore_sign && negate_mathfn_p (fn))
 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, strip sign operations
 838      from all arguments.  */
 839   if (info->flags.ignore_sign)
 840     {
 841       use_operand_p use;
 842       ssa_op_iter oi;
 843       bool replaced = false;
 844       FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
 845         {
 846           tree new_arg = strip_sign_op (USE_FROM_PTR (use));
 847           if (new_arg)
 848             {
 849               if (!replaced)
 850                 prepare_change (var);
 851               if (dump_file && (dump_flags & TDF_DETAILS))
 852                 note_replacement (phi, USE_FROM_PTR (use), new_arg);
 853               replace_exp (use, new_arg);
 854               replaced = true;
 855             }
 856         }
 857     }
 858 }
 859
 860 void
 861 backprop::execute ()
 862 {
 863   /* Phase 1: Traverse the function, making optimistic assumptions
 864      about any phi whose definition we haven't seen.  */
 865   int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (m_fn));
 866   unsigned int postorder_num = post_order_compute (postorder, false, false);
 867   for (unsigned int i = 0; i < postorder_num; ++i)
 868     {
 869       process_block (BASIC_BLOCK_FOR_FN (m_fn, postorder[i]));
 870       bitmap_set_bit (m_visited_blocks, postorder[i]);
 871     }
 872   XDELETEVEC (postorder);
 873
 874   /* Phase 2: Use the initial (perhaps overly optimistic) information
 875      to create a maximal fixed point solution.  */
 876   while (!m_worklist.is_empty ())
 877     process_var (pop_from_worklist ());
 878
 879   if (dump_file && (dump_flags & TDF_DETAILS))
 880     fprintf (dump_file, "\n");
 881
 882   /* Phase 3: Do a reverse post-order walk, using information about
 883      the uses of SSA names to optimize their definitions.  */
 884   for (unsigned int i = m_vars.length (); i-- > 0;)
 885     {
 886       usage_info *info = m_vars[i].second;
 887       if (info->is_useful ())
 888         {
 889           tree var = m_vars[i].first;
 890           gimple *stmt = SSA_NAME_DEF_STMT (var);
 891           if (gcall *call = dyn_cast <gcall *> (stmt))
 892             {
 893               if (gimple_call_builtin_p (call, BUILT_IN_NORMAL))
 894                 optimize_builtin_call (call, var, info);
 895             }
 896           else if (gassign *assign = dyn_cast <gassign *> (stmt))
 897             optimize_assign (assign, var, info);
 898           else if (gphi *phi = dyn_cast <gphi *> (stmt))
 899             optimize_phi (phi, var, info);
 900         }
 901     }
 902
 903   /* Phase 4: Do a post-order walk, deleting statements that are no
 904      longer needed.  */
 905   for (unsigned int i = 0; i < m_vars.length (); ++i)
 906     {
 907       tree var = m_vars[i].first;
 908       if (has_zero_uses (var))
 909         remove_unused_var (var);
 910     }
 911
 912   if (dump_file && (dump_flags & TDF_DETAILS))
 913     fprintf (dump_file, "\n");
 914 }
 915
 916 const pass_data pass_data_backprop =
 917 {
 918   GIMPLE_PASS, /* type */
 919   "backprop", /* name */
 920   OPTGROUP_NONE, /* optinfo_flags */
 921   TV_TREE_BACKPROP, /* tv_id */
 922   ( PROP_cfg | PROP_ssa ), /* properties_required */
 923   0, /* properties_provided */
 924   0, /* properties_destroyed */
 925   0, /* todo_flags_start */
 926   0, /* todo_flags_finish */
 927 };
 928
 929 class pass_backprop : public gimple_opt_pass
 930 {
 931 public:
 932   pass_backprop (gcc::context *ctxt)
 933     : gimple_opt_pass (pass_data_backprop, ctxt)
 934   {}
 935
 936   /* opt_pass methods: */
 937   opt_pass * clone () { return new pass_backprop (m_ctxt); }
 938   virtual bool gate (function *) { return flag_ssa_backprop; }
 939   virtual unsigned int execute (function *);
 940
 941 }; // class pass_backprop
 942
 943 unsigned int
 944 pass_backprop::execute (function *fn)
 945 {
 946   backprop (fn).execute ();
 947   return 0;
 948 }
 949
 950 } // anon namespace
 951
 952 gimple_opt_pass *
 953 make_pass_backprop (gcc::context *ctxt)
 954 {
 955   return new pass_backprop (ctxt);
 956 }