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