1/* Back-propagation of usage information to definitions. 2 Copyright (C) 2015-2020 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify 7it under the terms of the GNU General Public License as published by 8the Free Software Foundation; either version 3, or (at your option) 9any later version. 10 11GCC is distributed in the hope that it will be useful, 12but WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14GNU General Public License for more details. 15 16You should have received a copy of the GNU General Public License 17along 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 107namespace { 108 109/* Information about a group of uses of an SSA name. */ 110class usage_info 111{ 112public: 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 137usage_info 138usage_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 148usage_info & 149usage_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 158usage_info 159usage_info::operator & (const usage_info &other) const 160{ 161 usage_info info (*this); 162 info &= other; 163 return info; 164} 165 166bool 167usage_info::operator == (const usage_info &other) const 168{ 169 return flag_word == other.flag_word; 170} 171 172bool 173usage_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 180bool 181usage_info::is_useful () const 182{ 183 return flag_word != 0; 184} 185 186/* Start a dump line about SSA name VAR. */ 187 188static void 189dump_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 198static void 199dump_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. */ 209class backprop 210{ 211public: 212 backprop (function *); 213 ~backprop (); 214 215 void execute (); 216 217private: 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 278backprop::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 287backprop::~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 295const usage_info * 296backprop::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 309void 310backprop::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 326tree 327backprop::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 343void 344backprop::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 410void 411backprop::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 459void 460backprop::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 469void 470backprop::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 496bool 497backprop::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 538void 539backprop::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 554static void 555dump_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 566void 567backprop::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 628void 629backprop::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 650static void 651remove_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 666static void 667note_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 680static tree 681strip_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 721static tree 722strip_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 737void 738backprop::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 749void 750backprop::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 767void 768backprop::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 788void 789backprop::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 808void 809backprop::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 842void 843backprop::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 874void 875backprop::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 927const 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 940class pass_backprop : public gimple_opt_pass 941{ 942public: 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 954unsigned int 955pass_backprop::execute (function *fn) 956{ 957 backprop (fn).execute (); 958 return 0; 959} 960 961} // anon namespace 962 963gimple_opt_pass * 964make_pass_backprop (gcc::context *ctxt) 965{ 966 return new pass_backprop (ctxt); 967} 968