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