1 /* Back-propagation of usage information to definitions. 2 Copyright (C) 2015-2018 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 3, or (at your option) 9 any later version. 10 11 GCC is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20 /* This pass propagates information that is common to all uses of an SSA 21 name back up through the sequence of statements that generate it, 22 simplifying the statements where possible. Sometimes this can expose 23 fully or partially dead code, but the main focus is simplifying 24 computations. 25 26 At the moment the pass only handles one piece of information: whether the 27 sign of a value matters, and therefore whether sign-changing operations 28 can be skipped. The pass could be extended to more interesting 29 information in future, such as which bits of an integer are significant. 30 31 For example, take the function: 32 33 double 34 f (double *a, int n, double start) 35 { 36 double x = fabs (start); 37 for (int i = 0; i < n; ++i) 38 x *= a[i]; 39 return __builtin_cos (x); 40 } 41 42 cos(x) == cos(-x), so the sign of the final x doesn't matter. 43 That x is the result of a series of multiplications, and if 44 the sign of the result of a multiplication doesn't matter, 45 the signs of the inputs don't matter either. 46 47 The pass would replace the incoming value of x (i.e. fabs(start)) 48 with start. Since there are no other uses of the fabs result, 49 the call would get deleted as dead. 50 51 The algorithm is: 52 53 (1) Do a post-order traversal of the blocks in the function, walking 54 each block backwards. For each potentially-simplifiable statement 55 that defines an SSA name X, examine all uses of X to see what 56 information is actually significant. Record this as INFO_MAP[X]. 57 Optimistically ignore for now any back-edge references to 58 unprocessed phis. 59 60 (An alternative would be to record each use when we visit its 61 statement and take the intersection as we go along. However, 62 this would lead to more SSA names being entered into INFO_MAP 63 unnecessarily, only to be taken out again later. At the moment 64 very few SSA names end up with useful information.) 65 66 (2) Iteratively reduce the optimistic result of (1) until we reach 67 a maximal fixed point (which at the moment would mean revisiting 68 statements at most once). First push all SSA names that used an 69 optimistic assumption about a backedge phi onto a worklist. 70 While the worklist is nonempty, pick off an SSA name X and recompute 71 INFO_MAP[X]. If the value changes, push all SSA names used in the 72 definition of X onto the worklist. 73 74 (3) Iterate over each SSA name X with info in INFO_MAP, in the 75 opposite order to (1), i.e. a forward reverse-post-order walk. 76 Try to optimize the definition of X using INFO_MAP[X] and fold 77 the result. (This ensures that we fold definitions before uses.) 78 79 (4) Iterate over each SSA name X with info in INFO_MAP, in the same 80 order as (1), and delete any statements that are now dead. 81 (This ensures that if a sequence of statements is dead, 82 we delete the last statement first.) 83 84 Note that this pass does not deal with direct redundancies, 85 such as cos(-x)->cos(x). match.pd handles those cases instead. */ 86 87 #include "config.h" 88 #include "system.h" 89 #include "coretypes.h" 90 #include "backend.h" 91 #include "tree.h" 92 #include "gimple.h" 93 #include "gimple-iterator.h" 94 #include "ssa.h" 95 #include "fold-const.h" 96 #include "tree-pass.h" 97 #include "cfganal.h" 98 #include "gimple-pretty-print.h" 99 #include "tree-cfg.h" 100 #include "tree-ssa.h" 101 #include "tree-ssa-propagate.h" 102 #include "gimple-fold.h" 103 #include "alloc-pool.h" 104 #include "tree-hash-traits.h" 105 #include "case-cfn-macros.h" 106 107 namespace { 108 109 /* Information about a group of uses of an SSA name. */ 110 struct usage_info 111 { 112 usage_info () : flag_word (0) {} 113 usage_info &operator &= (const usage_info &); 114 usage_info operator & (const usage_info &) const; 115 bool operator == (const usage_info &) const; 116 bool operator != (const usage_info &) const; 117 bool is_useful () const; 118 119 static usage_info intersection_identity (); 120 121 union 122 { 123 struct 124 { 125 /* True if the uses treat x and -x in the same way. */ 126 unsigned int ignore_sign : 1; 127 } flags; 128 /* All the flag bits as a single int. */ 129 unsigned int flag_word; 130 }; 131 }; 132 133 /* Return an X such that X & Y == Y for all Y. This is the most 134 optimistic assumption possible. */ 135 136 usage_info 137 usage_info::intersection_identity () 138 { 139 usage_info ret; 140 ret.flag_word = -1; 141 return ret; 142 } 143 144 /* Intersect *THIS with OTHER, so that *THIS describes all uses covered 145 by the original *THIS and OTHER. */ 146 147 usage_info & 148 usage_info::operator &= (const usage_info &other) 149 { 150 flag_word &= other.flag_word; 151 return *this; 152 } 153 154 /* Return the intersection of *THIS and OTHER, i.e. a structure that 155 describes all uses covered by *THIS and OTHER. */ 156 157 usage_info 158 usage_info::operator & (const usage_info &other) const 159 { 160 usage_info info (*this); 161 info &= other; 162 return info; 163 } 164 165 bool 166 usage_info::operator == (const usage_info &other) const 167 { 168 return flag_word == other.flag_word; 169 } 170 171 bool 172 usage_info::operator != (const usage_info &other) const 173 { 174 return !operator == (other); 175 } 176 177 /* Return true if *THIS is not simply the default, safe assumption. */ 178 179 bool 180 usage_info::is_useful () const 181 { 182 return flag_word != 0; 183 } 184 185 /* Start a dump line about SSA name VAR. */ 186 187 static void 188 dump_usage_prefix (FILE *file, tree var) 189 { 190 fprintf (file, " "); 191 print_generic_expr (file, var); 192 fprintf (file, ": "); 193 } 194 195 /* Print INFO to FILE. */ 196 197 static void 198 dump_usage_info (FILE *file, tree var, usage_info *info) 199 { 200 if (info->flags.ignore_sign) 201 { 202 dump_usage_prefix (file, var); 203 fprintf (file, "sign bit not important\n"); 204 } 205 } 206 207 /* Represents one execution of the pass. */ 208 class backprop 209 { 210 public: 211 backprop (function *); 212 ~backprop (); 213 214 void execute (); 215 216 private: 217 const usage_info *lookup_operand (tree); 218 219 void push_to_worklist (tree); 220 tree pop_from_worklist (); 221 222 void process_builtin_call_use (gcall *, tree, usage_info *); 223 void process_assign_use (gassign *, tree, usage_info *); 224 void process_phi_use (gphi *, usage_info *); 225 void process_use (gimple *, tree, usage_info *); 226 bool intersect_uses (tree, usage_info *); 227 void reprocess_inputs (gimple *); 228 void process_var (tree); 229 void process_block (basic_block); 230 231 void prepare_change (tree); 232 void complete_change (gimple *); 233 void optimize_builtin_call (gcall *, tree, const usage_info *); 234 void replace_assign_rhs (gassign *, tree, tree, tree, tree); 235 void optimize_assign (gassign *, tree, const usage_info *); 236 void optimize_phi (gphi *, tree, const usage_info *); 237 238 typedef hash_map <tree_ssa_name_hash, usage_info *> info_map_type; 239 typedef std::pair <tree, usage_info *> var_info_pair; 240 241 /* The function we're optimizing. */ 242 function *m_fn; 243 244 /* Pool for allocating usage_info structures. */ 245 object_allocator <usage_info> m_info_pool; 246 247 /* Maps an SSA name to a description of all uses of that SSA name. 248 All the usage_infos satisfy is_useful. 249 250 We use a hash_map because the map is expected to be sparse 251 (i.e. most SSA names won't have useful information attached to them). 252 We could move to a directly-indexed array if that situation changes. */ 253 info_map_type m_info_map; 254 255 /* Post-ordered list of all potentially-interesting SSA names, 256 along with information that describes all uses. */ 257 auto_vec <var_info_pair, 128> m_vars; 258 259 /* A bitmap of blocks that we have finished processing in the initial 260 post-order walk. */ 261 auto_sbitmap m_visited_blocks; 262 263 /* A worklist of SSA names whose definitions need to be reconsidered. */ 264 auto_vec <tree, 64> m_worklist; 265 266 /* The SSA names in M_WORKLIST, identified by their SSA_NAME_VERSION. 267 We use a bitmap rather than an sbitmap because most SSA names are 268 never added to the worklist. */ 269 bitmap m_worklist_names; 270 }; 271 272 backprop::backprop (function *fn) 273 : m_fn (fn), 274 m_info_pool ("usage_info"), 275 m_visited_blocks (last_basic_block_for_fn (m_fn)), 276 m_worklist_names (BITMAP_ALLOC (NULL)) 277 { 278 bitmap_clear (m_visited_blocks); 279 } 280 281 backprop::~backprop () 282 { 283 BITMAP_FREE (m_worklist_names); 284 m_info_pool.release (); 285 } 286 287 /* Return usage information for general operand OP, or null if none. */ 288 289 const usage_info * 290 backprop::lookup_operand (tree op) 291 { 292 if (op && TREE_CODE (op) == SSA_NAME) 293 { 294 usage_info **slot = m_info_map.get (op); 295 if (slot) 296 return *slot; 297 } 298 return NULL; 299 } 300 301 /* Add SSA name VAR to the worklist, if it isn't on the worklist already. */ 302 303 void 304 backprop::push_to_worklist (tree var) 305 { 306 if (!bitmap_set_bit (m_worklist_names, SSA_NAME_VERSION (var))) 307 return; 308 m_worklist.safe_push (var); 309 if (dump_file && (dump_flags & TDF_DETAILS)) 310 { 311 fprintf (dump_file, "[WORKLIST] Pushing "); 312 print_generic_expr (dump_file, var); 313 fprintf (dump_file, "\n"); 314 } 315 } 316 317 /* Remove and return the next SSA name from the worklist. The worklist 318 is known to be nonempty. */ 319 320 tree 321 backprop::pop_from_worklist () 322 { 323 tree var = m_worklist.pop (); 324 bitmap_clear_bit (m_worklist_names, SSA_NAME_VERSION (var)); 325 if (dump_file && (dump_flags & TDF_DETAILS)) 326 { 327 fprintf (dump_file, "[WORKLIST] Popping "); 328 print_generic_expr (dump_file, var); 329 fprintf (dump_file, "\n"); 330 } 331 return var; 332 } 333 334 /* Make INFO describe all uses of RHS in CALL, which is a call to a 335 built-in function. */ 336 337 void 338 backprop::process_builtin_call_use (gcall *call, tree rhs, usage_info *info) 339 { 340 combined_fn fn = gimple_call_combined_fn (call); 341 tree lhs = gimple_call_lhs (call); 342 switch (fn) 343 { 344 case CFN_LAST: 345 break; 346 347 CASE_CFN_COS: 348 CASE_CFN_COSH: 349 CASE_CFN_CCOS: 350 CASE_CFN_CCOSH: 351 CASE_CFN_HYPOT: 352 /* The signs of all inputs are ignored. */ 353 info->flags.ignore_sign = true; 354 break; 355 356 CASE_CFN_COPYSIGN: 357 CASE_CFN_COPYSIGN_FN: 358 /* The sign of the first input is ignored. */ 359 if (rhs != gimple_call_arg (call, 1)) 360 info->flags.ignore_sign = true; 361 break; 362 363 CASE_CFN_POW: 364 { 365 /* The sign of the first input is ignored as long as the second 366 input is an even real. */ 367 tree power = gimple_call_arg (call, 1); 368 HOST_WIDE_INT n; 369 if (TREE_CODE (power) == REAL_CST 370 && real_isinteger (&TREE_REAL_CST (power), &n) 371 && (n & 1) == 0) 372 info->flags.ignore_sign = true; 373 break; 374 } 375 376 CASE_CFN_FMA: 377 CASE_CFN_FMA_FN: 378 /* In X * X + Y, where Y is distinct from X, the sign of X doesn't 379 matter. */ 380 if (gimple_call_arg (call, 0) == rhs 381 && gimple_call_arg (call, 1) == rhs 382 && gimple_call_arg (call, 2) != rhs) 383 info->flags.ignore_sign = true; 384 break; 385 386 default: 387 if (negate_mathfn_p (fn)) 388 { 389 /* The sign of the (single) input doesn't matter provided 390 that the sign of the output doesn't matter. */ 391 const usage_info *lhs_info = lookup_operand (lhs); 392 if (lhs_info) 393 info->flags.ignore_sign = lhs_info->flags.ignore_sign; 394 } 395 break; 396 } 397 } 398 399 /* Make INFO describe all uses of RHS in ASSIGN. */ 400 401 void 402 backprop::process_assign_use (gassign *assign, tree rhs, usage_info *info) 403 { 404 tree lhs = gimple_assign_lhs (assign); 405 switch (gimple_assign_rhs_code (assign)) 406 { 407 case ABS_EXPR: 408 /* The sign of the input doesn't matter. */ 409 info->flags.ignore_sign = true; 410 break; 411 412 case COND_EXPR: 413 /* For A = B ? C : D, propagate information about all uses of A 414 to C and D. */ 415 if (rhs != gimple_assign_rhs1 (assign)) 416 { 417 const usage_info *lhs_info = lookup_operand (lhs); 418 if (lhs_info) 419 *info = *lhs_info; 420 } 421 break; 422 423 case FMA_EXPR: 424 /* In X * X + Y, where Y is distinct from X, the sign of X doesn't 425 matter. */ 426 if (gimple_assign_rhs1 (assign) == rhs 427 && gimple_assign_rhs2 (assign) == rhs 428 && gimple_assign_rhs3 (assign) != rhs) 429 info->flags.ignore_sign = true; 430 break; 431 432 case MULT_EXPR: 433 /* In X * X, the sign of X doesn't matter. */ 434 if (gimple_assign_rhs1 (assign) == rhs 435 && gimple_assign_rhs2 (assign) == rhs) 436 info->flags.ignore_sign = true; 437 /* Fall through. */ 438 439 case NEGATE_EXPR: 440 case RDIV_EXPR: 441 /* If the sign of the result doesn't matter, the sign of the inputs 442 doesn't matter either. */ 443 if (FLOAT_TYPE_P (TREE_TYPE (rhs))) 444 { 445 const usage_info *lhs_info = lookup_operand (lhs); 446 if (lhs_info) 447 info->flags.ignore_sign = lhs_info->flags.ignore_sign; 448 } 449 break; 450 451 default: 452 break; 453 } 454 } 455 456 /* Make INFO describe the uses of PHI's result. */ 457 458 void 459 backprop::process_phi_use (gphi *phi, usage_info *info) 460 { 461 tree result = gimple_phi_result (phi); 462 if (const usage_info *result_info = lookup_operand (result)) 463 *info = *result_info; 464 } 465 466 /* Make INFO describe all uses of RHS in STMT. */ 467 468 void 469 backprop::process_use (gimple *stmt, tree rhs, usage_info *info) 470 { 471 if (dump_file && (dump_flags & TDF_DETAILS)) 472 { 473 fprintf (dump_file, "[USE] "); 474 print_generic_expr (dump_file, rhs); 475 fprintf (dump_file, " in "); 476 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 477 } 478 479 if (gcall *call = dyn_cast <gcall *> (stmt)) 480 process_builtin_call_use (call, rhs, info); 481 else if (gassign *assign = dyn_cast <gassign *> (stmt)) 482 process_assign_use (assign, rhs, info); 483 else if (gphi *phi = dyn_cast <gphi *> (stmt)) 484 process_phi_use (phi, info); 485 486 if (dump_file && (dump_flags & TDF_DETAILS)) 487 dump_usage_info (dump_file, rhs, info); 488 } 489 490 /* Make INFO describe all uses of VAR, returning true if the result 491 is useful. If the uses include phis that haven't been processed yet, 492 make the most optimistic assumption possible, so that we aim for 493 a maximum rather than a minimum fixed point. */ 494 495 bool 496 backprop::intersect_uses (tree var, usage_info *info) 497 { 498 imm_use_iterator iter; 499 gimple *stmt; 500 *info = usage_info::intersection_identity (); 501 FOR_EACH_IMM_USE_STMT (stmt, iter, var) 502 { 503 if (is_gimple_debug (stmt)) 504 continue; 505 if (is_a <gphi *> (stmt) 506 && !bitmap_bit_p (m_visited_blocks, gimple_bb (stmt)->index)) 507 { 508 /* Skip unprocessed phis. */ 509 if (dump_file && (dump_flags & TDF_DETAILS)) 510 { 511 fprintf (dump_file, "[BACKEDGE] "); 512 print_generic_expr (dump_file, var); 513 fprintf (dump_file, " in "); 514 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 515 } 516 } 517 else 518 { 519 usage_info subinfo; 520 process_use (stmt, var, &subinfo); 521 *info &= subinfo; 522 if (!info->is_useful ()) 523 { 524 BREAK_FROM_IMM_USE_STMT (iter); 525 return false; 526 } 527 } 528 } 529 return true; 530 } 531 532 /* Queue for reconsideration any input of STMT that has information 533 associated with it. This is used if that information might be 534 too optimistic. */ 535 536 void 537 backprop::reprocess_inputs (gimple *stmt) 538 { 539 use_operand_p use_p; 540 ssa_op_iter oi; 541 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE) 542 { 543 tree var = get_use_from_ptr (use_p); 544 if (lookup_operand (var)) 545 push_to_worklist (var); 546 } 547 } 548 549 /* Say that we're recording INFO for SSA name VAR, or that we're deleting 550 existing information if INFO is null. INTRO describes the change. */ 551 552 static void 553 dump_var_info (tree var, usage_info *info, const char *intro) 554 { 555 fprintf (dump_file, "[DEF] %s for ", intro); 556 print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (var), 0, TDF_SLIM); 557 if (info) 558 dump_usage_info (dump_file, var, info); 559 } 560 561 /* Process all uses of VAR and record or update the result in 562 M_INFO_MAP and M_VARS. */ 563 564 void 565 backprop::process_var (tree var) 566 { 567 if (has_zero_uses (var)) 568 return; 569 570 usage_info info; 571 intersect_uses (var, &info); 572 573 gimple *stmt = SSA_NAME_DEF_STMT (var); 574 if (info.is_useful ()) 575 { 576 bool existed; 577 usage_info *&map_info = m_info_map.get_or_insert (var, &existed); 578 if (!existed) 579 { 580 /* Recording information about VAR for the first time. */ 581 map_info = m_info_pool.allocate (); 582 *map_info = info; 583 m_vars.safe_push (var_info_pair (var, map_info)); 584 if (dump_file && (dump_flags & TDF_DETAILS)) 585 dump_var_info (var, map_info, "Recording new information"); 586 587 /* If STMT is a phi, reprocess any backedge uses. This is a 588 no-op for other uses, which won't have any information 589 associated with them. */ 590 if (is_a <gphi *> (stmt)) 591 reprocess_inputs (stmt); 592 } 593 else if (info != *map_info) 594 { 595 /* Recording information that is less optimistic than before. */ 596 gcc_checking_assert ((info & *map_info) == info); 597 *map_info = info; 598 if (dump_file && (dump_flags & TDF_DETAILS)) 599 dump_var_info (var, map_info, "Updating information"); 600 reprocess_inputs (stmt); 601 } 602 } 603 else 604 { 605 if (usage_info **slot = m_info_map.get (var)) 606 { 607 /* Removing previously-recorded information. */ 608 **slot = info; 609 m_info_map.remove (var); 610 if (dump_file && (dump_flags & TDF_DETAILS)) 611 dump_var_info (var, NULL, "Deleting information"); 612 reprocess_inputs (stmt); 613 } 614 else 615 { 616 /* If STMT is a phi, remove any information recorded for 617 its arguments. */ 618 if (is_a <gphi *> (stmt)) 619 reprocess_inputs (stmt); 620 } 621 } 622 } 623 624 /* Process all statements and phis in BB, during the first post-order walk. */ 625 626 void 627 backprop::process_block (basic_block bb) 628 { 629 for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi); 630 gsi_prev (&gsi)) 631 { 632 tree lhs = gimple_get_lhs (gsi_stmt (gsi)); 633 if (lhs && TREE_CODE (lhs) == SSA_NAME) 634 process_var (lhs); 635 } 636 for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi); 637 gsi_next (&gpi)) 638 process_var (gimple_phi_result (gpi.phi ())); 639 } 640 641 /* Delete the definition of VAR, which has no uses. */ 642 643 static void 644 remove_unused_var (tree var) 645 { 646 gimple *stmt = SSA_NAME_DEF_STMT (var); 647 if (dump_file && (dump_flags & TDF_DETAILS)) 648 { 649 fprintf (dump_file, "Deleting "); 650 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 651 } 652 gimple_stmt_iterator gsi = gsi_for_stmt (stmt); 653 gsi_remove (&gsi, true); 654 release_defs (stmt); 655 } 656 657 /* Note that we're replacing OLD_RHS with NEW_RHS in STMT. */ 658 659 static void 660 note_replacement (gimple *stmt, tree old_rhs, tree new_rhs) 661 { 662 fprintf (dump_file, "Replacing use of "); 663 print_generic_expr (dump_file, old_rhs); 664 fprintf (dump_file, " with "); 665 print_generic_expr (dump_file, new_rhs); 666 fprintf (dump_file, " in "); 667 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 668 } 669 670 /* If RHS is an SSA name whose definition just changes the sign of a value, 671 return that other value, otherwise return null. */ 672 673 static tree 674 strip_sign_op_1 (tree rhs) 675 { 676 if (TREE_CODE (rhs) != SSA_NAME) 677 return NULL_TREE; 678 679 gimple *def_stmt = SSA_NAME_DEF_STMT (rhs); 680 if (gassign *assign = dyn_cast <gassign *> (def_stmt)) 681 switch (gimple_assign_rhs_code (assign)) 682 { 683 case ABS_EXPR: 684 case NEGATE_EXPR: 685 return gimple_assign_rhs1 (assign); 686 687 default: 688 break; 689 } 690 else if (gcall *call = dyn_cast <gcall *> (def_stmt)) 691 switch (gimple_call_combined_fn (call)) 692 { 693 CASE_CFN_COPYSIGN: 694 CASE_CFN_COPYSIGN_FN: 695 return gimple_call_arg (call, 0); 696 697 default: 698 break; 699 } 700 701 return NULL_TREE; 702 } 703 704 /* If RHS is an SSA name whose definition just changes the sign of a value, 705 strip all such operations and return the ultimate input to them. 706 Return null otherwise. 707 708 Although this could in principle lead to quadratic searching, 709 in practice a long sequence of sign manipulations should already 710 have been folded down. E.g. --x -> x, abs(-x) -> abs(x). We search 711 for more than one operation in order to catch cases like -abs(x). */ 712 713 static tree 714 strip_sign_op (tree rhs) 715 { 716 tree new_rhs = strip_sign_op_1 (rhs); 717 if (!new_rhs) 718 return NULL_TREE; 719 while (tree next = strip_sign_op_1 (new_rhs)) 720 new_rhs = next; 721 return new_rhs; 722 } 723 724 /* Start a change in the value of VAR that is suitable for all non-debug 725 uses of VAR. We need to make sure that debug statements continue to 726 use the original definition of VAR where possible, or are nullified 727 otherwise. */ 728 729 void 730 backprop::prepare_change (tree var) 731 { 732 if (MAY_HAVE_DEBUG_BIND_STMTS) 733 insert_debug_temp_for_var_def (NULL, var); 734 reset_flow_sensitive_info (var); 735 } 736 737 /* STMT has been changed. Give the fold machinery a chance to simplify 738 and canonicalize it (e.g. by ensuring that commutative operands have 739 the right order), then record the updates. */ 740 741 void 742 backprop::complete_change (gimple *stmt) 743 { 744 gimple_stmt_iterator gsi = gsi_for_stmt (stmt); 745 if (fold_stmt (&gsi)) 746 { 747 if (dump_file && (dump_flags & TDF_DETAILS)) 748 { 749 fprintf (dump_file, " which folds to: "); 750 print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, TDF_SLIM); 751 } 752 } 753 update_stmt (gsi_stmt (gsi)); 754 } 755 756 /* Optimize CALL, a call to a built-in function with lhs LHS, on the 757 basis that INFO describes all uses of LHS. */ 758 759 void 760 backprop::optimize_builtin_call (gcall *call, tree lhs, const usage_info *info) 761 { 762 /* If we have an f such that -f(x) = f(-x), and if the sign of the result 763 doesn't matter, strip any sign operations from the input. */ 764 if (info->flags.ignore_sign 765 && negate_mathfn_p (gimple_call_combined_fn (call))) 766 { 767 tree new_arg = strip_sign_op (gimple_call_arg (call, 0)); 768 if (new_arg) 769 { 770 prepare_change (lhs); 771 gimple_call_set_arg (call, 0, new_arg); 772 complete_change (call); 773 } 774 } 775 } 776 777 /* Optimize ASSIGN, an assignment to LHS, by replacing rhs operand N 778 with RHS<N>, if RHS<N> is nonnull. This may change the value of LHS. */ 779 780 void 781 backprop::replace_assign_rhs (gassign *assign, tree lhs, tree rhs1, 782 tree rhs2, tree rhs3) 783 { 784 if (!rhs1 && !rhs2 && !rhs3) 785 return; 786 787 prepare_change (lhs); 788 if (rhs1) 789 gimple_assign_set_rhs1 (assign, rhs1); 790 if (rhs2) 791 gimple_assign_set_rhs2 (assign, rhs2); 792 if (rhs3) 793 gimple_assign_set_rhs3 (assign, rhs3); 794 complete_change (assign); 795 } 796 797 /* Optimize ASSIGN, an assignment to LHS, on the basis that INFO 798 describes all uses of LHS. */ 799 800 void 801 backprop::optimize_assign (gassign *assign, tree lhs, const usage_info *info) 802 { 803 switch (gimple_assign_rhs_code (assign)) 804 { 805 case MULT_EXPR: 806 case RDIV_EXPR: 807 /* If the sign of the result doesn't matter, strip sign operations 808 from both inputs. */ 809 if (info->flags.ignore_sign) 810 replace_assign_rhs (assign, lhs, 811 strip_sign_op (gimple_assign_rhs1 (assign)), 812 strip_sign_op (gimple_assign_rhs2 (assign)), 813 NULL_TREE); 814 break; 815 816 case COND_EXPR: 817 /* If the sign of A ? B : C doesn't matter, strip sign operations 818 from both B and C. */ 819 if (info->flags.ignore_sign) 820 replace_assign_rhs (assign, lhs, 821 NULL_TREE, 822 strip_sign_op (gimple_assign_rhs2 (assign)), 823 strip_sign_op (gimple_assign_rhs3 (assign))); 824 break; 825 826 default: 827 break; 828 } 829 } 830 831 /* Optimize PHI, which defines VAR, on the basis that INFO describes all 832 uses of the result. */ 833 834 void 835 backprop::optimize_phi (gphi *phi, tree var, const usage_info *info) 836 { 837 /* If the sign of the result doesn't matter, try to strip sign operations 838 from arguments. */ 839 if (info->flags.ignore_sign) 840 { 841 basic_block bb = gimple_bb (phi); 842 use_operand_p use; 843 ssa_op_iter oi; 844 bool replaced = false; 845 FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE) 846 { 847 /* Propagating along abnormal edges is delicate, punt for now. */ 848 const int index = PHI_ARG_INDEX_FROM_USE (use); 849 if (EDGE_PRED (bb, index)->flags & EDGE_ABNORMAL) 850 continue; 851 852 tree new_arg = strip_sign_op (USE_FROM_PTR (use)); 853 if (new_arg) 854 { 855 if (!replaced) 856 prepare_change (var); 857 if (dump_file && (dump_flags & TDF_DETAILS)) 858 note_replacement (phi, USE_FROM_PTR (use), new_arg); 859 replace_exp (use, new_arg); 860 replaced = true; 861 } 862 } 863 } 864 } 865 866 void 867 backprop::execute () 868 { 869 /* Phase 1: Traverse the function, making optimistic assumptions 870 about any phi whose definition we haven't seen. */ 871 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (m_fn)); 872 unsigned int postorder_num = post_order_compute (postorder, false, false); 873 for (unsigned int i = 0; i < postorder_num; ++i) 874 { 875 process_block (BASIC_BLOCK_FOR_FN (m_fn, postorder[i])); 876 bitmap_set_bit (m_visited_blocks, postorder[i]); 877 } 878 XDELETEVEC (postorder); 879 880 /* Phase 2: Use the initial (perhaps overly optimistic) information 881 to create a maximal fixed point solution. */ 882 while (!m_worklist.is_empty ()) 883 process_var (pop_from_worklist ()); 884 885 if (dump_file && (dump_flags & TDF_DETAILS)) 886 fprintf (dump_file, "\n"); 887 888 /* Phase 3: Do a reverse post-order walk, using information about 889 the uses of SSA names to optimize their definitions. */ 890 for (unsigned int i = m_vars.length (); i-- > 0;) 891 { 892 usage_info *info = m_vars[i].second; 893 if (info->is_useful ()) 894 { 895 tree var = m_vars[i].first; 896 gimple *stmt = SSA_NAME_DEF_STMT (var); 897 if (gcall *call = dyn_cast <gcall *> (stmt)) 898 optimize_builtin_call (call, var, info); 899 else if (gassign *assign = dyn_cast <gassign *> (stmt)) 900 optimize_assign (assign, var, info); 901 else if (gphi *phi = dyn_cast <gphi *> (stmt)) 902 optimize_phi (phi, var, info); 903 } 904 } 905 906 /* Phase 4: Do a post-order walk, deleting statements that are no 907 longer needed. */ 908 for (unsigned int i = 0; i < m_vars.length (); ++i) 909 { 910 tree var = m_vars[i].first; 911 if (has_zero_uses (var)) 912 remove_unused_var (var); 913 } 914 915 if (dump_file && (dump_flags & TDF_DETAILS)) 916 fprintf (dump_file, "\n"); 917 } 918 919 const pass_data pass_data_backprop = 920 { 921 GIMPLE_PASS, /* type */ 922 "backprop", /* name */ 923 OPTGROUP_NONE, /* optinfo_flags */ 924 TV_TREE_BACKPROP, /* tv_id */ 925 ( PROP_cfg | PROP_ssa ), /* properties_required */ 926 0, /* properties_provided */ 927 0, /* properties_destroyed */ 928 0, /* todo_flags_start */ 929 0, /* todo_flags_finish */ 930 }; 931 932 class pass_backprop : public gimple_opt_pass 933 { 934 public: 935 pass_backprop (gcc::context *ctxt) 936 : gimple_opt_pass (pass_data_backprop, ctxt) 937 {} 938 939 /* opt_pass methods: */ 940 opt_pass * clone () { return new pass_backprop (m_ctxt); } 941 virtual bool gate (function *) { return flag_ssa_backprop; } 942 virtual unsigned int execute (function *); 943 944 }; // class pass_backprop 945 946 unsigned int 947 pass_backprop::execute (function *fn) 948 { 949 backprop (fn).execute (); 950 return 0; 951 } 952 953 } // anon namespace 954 955 gimple_opt_pass * 956 make_pass_backprop (gcc::context *ctxt) 957 { 958 return new pass_backprop (ctxt); 959 } 960