gcc/gimple-ssa-backprop.c

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