1/* Forward propagation of expressions for single use variables. 2 Copyright (C) 2004, 2005 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 2, 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 COPYING. If not, write to 18the Free Software Foundation, 51 Franklin Street, Fifth Floor, 19Boston, MA 02110-1301, USA. */ 20 21#include "config.h" 22#include "system.h" 23#include "coretypes.h" 24#include "tm.h" 25#include "ggc.h" 26#include "tree.h" 27#include "rtl.h" 28#include "tm_p.h" 29#include "basic-block.h" 30#include "timevar.h" 31#include "diagnostic.h" 32#include "tree-flow.h" 33#include "tree-pass.h" 34#include "tree-dump.h" 35#include "langhooks.h" 36 37/* This pass propagates the RHS of assignment statements into use 38 sites of the LHS of the assignment. It's basically a specialized 39 form of tree combination. It is hoped all of this can disappear 40 when we have a generalized tree combiner. 41 42 Note carefully that after propagation the resulting statement 43 must still be a proper gimple statement. Right now we simply 44 only perform propagations we know will result in valid gimple 45 code. One day we'll want to generalize this code. 46 47 One class of common cases we handle is forward propagating a single use 48 variable into a COND_EXPR. 49 50 bb0: 51 x = a COND b; 52 if (x) goto ... else goto ... 53 54 Will be transformed into: 55 56 bb0: 57 if (a COND b) goto ... else goto ... 58 59 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1). 60 61 Or (assuming c1 and c2 are constants): 62 63 bb0: 64 x = a + c1; 65 if (x EQ/NEQ c2) goto ... else goto ... 66 67 Will be transformed into: 68 69 bb0: 70 if (a EQ/NEQ (c2 - c1)) goto ... else goto ... 71 72 Similarly for x = a - c1. 73 74 Or 75 76 bb0: 77 x = !a 78 if (x) goto ... else goto ... 79 80 Will be transformed into: 81 82 bb0: 83 if (a == 0) goto ... else goto ... 84 85 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1). 86 For these cases, we propagate A into all, possibly more than one, 87 COND_EXPRs that use X. 88 89 Or 90 91 bb0: 92 x = (typecast) a 93 if (x) goto ... else goto ... 94 95 Will be transformed into: 96 97 bb0: 98 if (a != 0) goto ... else goto ... 99 100 (Assuming a is an integral type and x is a boolean or x is an 101 integral and a is a boolean.) 102 103 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1). 104 For these cases, we propagate A into all, possibly more than one, 105 COND_EXPRs that use X. 106 107 In addition to eliminating the variable and the statement which assigns 108 a value to the variable, we may be able to later thread the jump without 109 adding insane complexity in the dominator optimizer. 110 111 Also note these transformations can cascade. We handle this by having 112 a worklist of COND_EXPR statements to examine. As we make a change to 113 a statement, we put it back on the worklist to examine on the next 114 iteration of the main loop. 115 116 A second class of propagation opportunities arises for ADDR_EXPR 117 nodes. 118 119 ptr = &x->y->z; 120 res = *ptr; 121 122 Will get turned into 123 124 res = x->y->z; 125 126 Or 127 128 ptr = &x[0]; 129 ptr2 = ptr + <constant>; 130 131 Will get turned into 132 133 ptr2 = &x[constant/elementsize]; 134 135 Or 136 137 ptr = &x[0]; 138 offset = index * element_size; 139 offset_p = (pointer) offset; 140 ptr2 = ptr + offset_p 141 142 Will get turned into: 143 144 ptr2 = &x[index]; 145 146 We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to 147 allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent 148 {NOT_EXPR,NEG_EXPR}. 149 150 This will (of course) be extended as other needs arise. */ 151 152 153/* Set to true if we delete EH edges during the optimization. */ 154static bool cfg_changed; 155 156 157/* Given an SSA_NAME VAR, return true if and only if VAR is defined by 158 a comparison. */ 159 160static bool 161ssa_name_defined_by_comparison_p (tree var) 162{ 163 tree def = SSA_NAME_DEF_STMT (var); 164 165 if (TREE_CODE (def) == MODIFY_EXPR) 166 { 167 tree rhs = TREE_OPERAND (def, 1); 168 return COMPARISON_CLASS_P (rhs); 169 } 170 171 return 0; 172} 173 174/* Forward propagate a single-use variable into COND once. Return a 175 new condition if successful. Return NULL_TREE otherwise. */ 176 177static tree 178forward_propagate_into_cond_1 (tree cond, tree *test_var_p) 179{ 180 tree new_cond = NULL_TREE; 181 enum tree_code cond_code = TREE_CODE (cond); 182 tree test_var = NULL_TREE; 183 tree def; 184 tree def_rhs; 185 186 /* If the condition is not a lone variable or an equality test of an 187 SSA_NAME against an integral constant, then we do not have an 188 optimizable case. 189 190 Note these conditions also ensure the COND_EXPR has no 191 virtual operands or other side effects. */ 192 if (cond_code != SSA_NAME 193 && !((cond_code == EQ_EXPR || cond_code == NE_EXPR) 194 && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME 195 && CONSTANT_CLASS_P (TREE_OPERAND (cond, 1)) 196 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1))))) 197 return NULL_TREE; 198 199 /* Extract the single variable used in the test into TEST_VAR. */ 200 if (cond_code == SSA_NAME) 201 test_var = cond; 202 else 203 test_var = TREE_OPERAND (cond, 0); 204 205 /* Now get the defining statement for TEST_VAR. Skip this case if 206 it's not defined by some MODIFY_EXPR. */ 207 def = SSA_NAME_DEF_STMT (test_var); 208 if (TREE_CODE (def) != MODIFY_EXPR) 209 return NULL_TREE; 210 211 def_rhs = TREE_OPERAND (def, 1); 212 213 /* If TEST_VAR is set by adding or subtracting a constant 214 from an SSA_NAME, then it is interesting to us as we 215 can adjust the constant in the conditional and thus 216 eliminate the arithmetic operation. */ 217 if (TREE_CODE (def_rhs) == PLUS_EXPR 218 || TREE_CODE (def_rhs) == MINUS_EXPR) 219 { 220 tree op0 = TREE_OPERAND (def_rhs, 0); 221 tree op1 = TREE_OPERAND (def_rhs, 1); 222 223 /* The first operand must be an SSA_NAME and the second 224 operand must be a constant. */ 225 if (TREE_CODE (op0) != SSA_NAME 226 || !CONSTANT_CLASS_P (op1) 227 || !INTEGRAL_TYPE_P (TREE_TYPE (op1))) 228 return NULL_TREE; 229 230 /* Don't propagate if the first operand occurs in 231 an abnormal PHI. */ 232 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)) 233 return NULL_TREE; 234 235 if (has_single_use (test_var)) 236 { 237 enum tree_code new_code; 238 tree t; 239 240 /* If the variable was defined via X + C, then we must 241 subtract C from the constant in the conditional. 242 Otherwise we add C to the constant in the 243 conditional. The result must fold into a valid 244 gimple operand to be optimizable. */ 245 new_code = (TREE_CODE (def_rhs) == PLUS_EXPR 246 ? MINUS_EXPR : PLUS_EXPR); 247 t = int_const_binop (new_code, TREE_OPERAND (cond, 1), op1, 0); 248 if (!is_gimple_val (t)) 249 return NULL_TREE; 250 251 new_cond = build2 (cond_code, boolean_type_node, op0, t); 252 } 253 } 254 255 /* These cases require comparisons of a naked SSA_NAME or 256 comparison of an SSA_NAME against zero or one. */ 257 else if (TREE_CODE (cond) == SSA_NAME 258 || integer_zerop (TREE_OPERAND (cond, 1)) 259 || integer_onep (TREE_OPERAND (cond, 1))) 260 { 261 /* If TEST_VAR is set from a relational operation 262 between two SSA_NAMEs or a combination of an SSA_NAME 263 and a constant, then it is interesting. */ 264 if (COMPARISON_CLASS_P (def_rhs)) 265 { 266 tree op0 = TREE_OPERAND (def_rhs, 0); 267 tree op1 = TREE_OPERAND (def_rhs, 1); 268 269 /* Both operands of DEF_RHS must be SSA_NAMEs or 270 constants. */ 271 if ((TREE_CODE (op0) != SSA_NAME 272 && !is_gimple_min_invariant (op0)) 273 || (TREE_CODE (op1) != SSA_NAME 274 && !is_gimple_min_invariant (op1))) 275 return NULL_TREE; 276 277 /* Don't propagate if the first operand occurs in 278 an abnormal PHI. */ 279 if (TREE_CODE (op0) == SSA_NAME 280 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)) 281 return NULL_TREE; 282 283 /* Don't propagate if the second operand occurs in 284 an abnormal PHI. */ 285 if (TREE_CODE (op1) == SSA_NAME 286 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1)) 287 return NULL_TREE; 288 289 if (has_single_use (test_var)) 290 { 291 /* TEST_VAR was set from a relational operator. */ 292 new_cond = build2 (TREE_CODE (def_rhs), 293 boolean_type_node, op0, op1); 294 295 /* Invert the conditional if necessary. */ 296 if ((cond_code == EQ_EXPR 297 && integer_zerop (TREE_OPERAND (cond, 1))) 298 || (cond_code == NE_EXPR 299 && integer_onep (TREE_OPERAND (cond, 1)))) 300 { 301 new_cond = invert_truthvalue (new_cond); 302 303 /* If we did not get a simple relational 304 expression or bare SSA_NAME, then we can 305 not optimize this case. */ 306 if (!COMPARISON_CLASS_P (new_cond) 307 && TREE_CODE (new_cond) != SSA_NAME) 308 new_cond = NULL_TREE; 309 } 310 } 311 } 312 313 /* If TEST_VAR is set from a TRUTH_NOT_EXPR, then it 314 is interesting. */ 315 else if (TREE_CODE (def_rhs) == TRUTH_NOT_EXPR) 316 { 317 enum tree_code new_code; 318 319 def_rhs = TREE_OPERAND (def_rhs, 0); 320 321 /* DEF_RHS must be an SSA_NAME or constant. */ 322 if (TREE_CODE (def_rhs) != SSA_NAME 323 && !is_gimple_min_invariant (def_rhs)) 324 return NULL_TREE; 325 326 /* Don't propagate if the operand occurs in 327 an abnormal PHI. */ 328 if (TREE_CODE (def_rhs) == SSA_NAME 329 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_rhs)) 330 return NULL_TREE; 331 332 if (cond_code == SSA_NAME 333 || (cond_code == NE_EXPR 334 && integer_zerop (TREE_OPERAND (cond, 1))) 335 || (cond_code == EQ_EXPR 336 && integer_onep (TREE_OPERAND (cond, 1)))) 337 new_code = EQ_EXPR; 338 else 339 new_code = NE_EXPR; 340 341 new_cond = build2 (new_code, boolean_type_node, def_rhs, 342 fold_convert (TREE_TYPE (def_rhs), 343 integer_zero_node)); 344 } 345 346 /* If TEST_VAR was set from a cast of an integer type 347 to a boolean type or a cast of a boolean to an 348 integral, then it is interesting. */ 349 else if (TREE_CODE (def_rhs) == NOP_EXPR 350 || TREE_CODE (def_rhs) == CONVERT_EXPR) 351 { 352 tree outer_type; 353 tree inner_type; 354 355 outer_type = TREE_TYPE (def_rhs); 356 inner_type = TREE_TYPE (TREE_OPERAND (def_rhs, 0)); 357 358 if ((TREE_CODE (outer_type) == BOOLEAN_TYPE 359 && INTEGRAL_TYPE_P (inner_type)) 360 || (TREE_CODE (inner_type) == BOOLEAN_TYPE 361 && INTEGRAL_TYPE_P (outer_type))) 362 ; 363 else if (INTEGRAL_TYPE_P (outer_type) 364 && INTEGRAL_TYPE_P (inner_type) 365 && TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME 366 && ssa_name_defined_by_comparison_p (TREE_OPERAND (def_rhs, 367 0))) 368 ; 369 else 370 return NULL_TREE; 371 372 /* Don't propagate if the operand occurs in 373 an abnormal PHI. */ 374 if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME 375 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND 376 (def_rhs, 0))) 377 return NULL_TREE; 378 379 if (has_single_use (test_var)) 380 { 381 enum tree_code new_code; 382 tree new_arg; 383 384 if (cond_code == SSA_NAME 385 || (cond_code == NE_EXPR 386 && integer_zerop (TREE_OPERAND (cond, 1))) 387 || (cond_code == EQ_EXPR 388 && integer_onep (TREE_OPERAND (cond, 1)))) 389 new_code = NE_EXPR; 390 else 391 new_code = EQ_EXPR; 392 393 new_arg = TREE_OPERAND (def_rhs, 0); 394 new_cond = build2 (new_code, boolean_type_node, new_arg, 395 fold_convert (TREE_TYPE (new_arg), 396 integer_zero_node)); 397 } 398 } 399 } 400 401 *test_var_p = test_var; 402 return new_cond; 403} 404 405/* COND is a condition of the form: 406 407 x == const or x != const 408 409 Look back to x's defining statement and see if x is defined as 410 411 x = (type) y; 412 413 If const is unchanged if we convert it to type, then we can build 414 the equivalent expression: 415 416 417 y == const or y != const 418 419 Which may allow further optimizations. 420 421 Return the equivalent comparison or NULL if no such equivalent comparison 422 was found. */ 423 424static tree 425find_equivalent_equality_comparison (tree cond) 426{ 427 tree op0 = TREE_OPERAND (cond, 0); 428 tree op1 = TREE_OPERAND (cond, 1); 429 tree def_stmt = SSA_NAME_DEF_STMT (op0); 430 431 while (def_stmt 432 && TREE_CODE (def_stmt) == MODIFY_EXPR 433 && TREE_CODE (TREE_OPERAND (def_stmt, 1)) == SSA_NAME) 434 def_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (def_stmt, 1)); 435 436 /* OP0 might have been a parameter, so first make sure it 437 was defined by a MODIFY_EXPR. */ 438 if (def_stmt && TREE_CODE (def_stmt) == MODIFY_EXPR) 439 { 440 tree def_rhs = TREE_OPERAND (def_stmt, 1); 441 442 /* If either operand to the comparison is a pointer to 443 a function, then we can not apply this optimization 444 as some targets require function pointers to be 445 canonicalized and in this case this optimization would 446 eliminate a necessary canonicalization. */ 447 if ((POINTER_TYPE_P (TREE_TYPE (op0)) 448 && TREE_CODE (TREE_TYPE (TREE_TYPE (op0))) == FUNCTION_TYPE) 449 || (POINTER_TYPE_P (TREE_TYPE (op1)) 450 && TREE_CODE (TREE_TYPE (TREE_TYPE (op1))) == FUNCTION_TYPE)) 451 return NULL; 452 453 /* Now make sure the RHS of the MODIFY_EXPR is a typecast. */ 454 if ((TREE_CODE (def_rhs) == NOP_EXPR 455 || TREE_CODE (def_rhs) == CONVERT_EXPR) 456 && TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME) 457 { 458 tree def_rhs_inner = TREE_OPERAND (def_rhs, 0); 459 tree def_rhs_inner_type = TREE_TYPE (def_rhs_inner); 460 tree new; 461 462 if (TYPE_PRECISION (def_rhs_inner_type) 463 > TYPE_PRECISION (TREE_TYPE (def_rhs))) 464 return NULL; 465 466 /* If the inner type of the conversion is a pointer to 467 a function, then we can not apply this optimization 468 as some targets require function pointers to be 469 canonicalized. This optimization would result in 470 canonicalization of the pointer when it was not originally 471 needed/intended. */ 472 if (POINTER_TYPE_P (def_rhs_inner_type) 473 && TREE_CODE (TREE_TYPE (def_rhs_inner_type)) == FUNCTION_TYPE) 474 return NULL; 475 476 /* What we want to prove is that if we convert OP1 to 477 the type of the object inside the NOP_EXPR that the 478 result is still equivalent to SRC. 479 480 If that is true, the build and return new equivalent 481 condition which uses the source of the typecast and the 482 new constant (which has only changed its type). */ 483 new = fold_build1 (TREE_CODE (def_rhs), def_rhs_inner_type, op1); 484 STRIP_USELESS_TYPE_CONVERSION (new); 485 if (is_gimple_val (new) && tree_int_cst_equal (new, op1)) 486 return build2 (TREE_CODE (cond), TREE_TYPE (cond), 487 def_rhs_inner, new); 488 } 489 } 490 return NULL; 491} 492 493/* STMT is a COND_EXPR 494 495 This routine attempts to find equivalent forms of the condition 496 which we may be able to optimize better. */ 497 498static void 499simplify_cond (tree stmt) 500{ 501 tree cond = COND_EXPR_COND (stmt); 502 503 if (COMPARISON_CLASS_P (cond)) 504 { 505 tree op0 = TREE_OPERAND (cond, 0); 506 tree op1 = TREE_OPERAND (cond, 1); 507 508 if (TREE_CODE (op0) == SSA_NAME && is_gimple_min_invariant (op1)) 509 { 510 /* First see if we have test of an SSA_NAME against a constant 511 where the SSA_NAME is defined by an earlier typecast which 512 is irrelevant when performing tests against the given 513 constant. */ 514 if (TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR) 515 { 516 tree new_cond = find_equivalent_equality_comparison (cond); 517 518 if (new_cond) 519 { 520 COND_EXPR_COND (stmt) = new_cond; 521 update_stmt (stmt); 522 } 523 } 524 } 525 } 526} 527 528/* Forward propagate a single-use variable into COND_EXPR as many 529 times as possible. */ 530 531static void 532forward_propagate_into_cond (tree cond_expr) 533{ 534 gcc_assert (TREE_CODE (cond_expr) == COND_EXPR); 535 536 while (1) 537 { 538 tree test_var = NULL_TREE; 539 tree cond = COND_EXPR_COND (cond_expr); 540 tree new_cond = forward_propagate_into_cond_1 (cond, &test_var); 541 542 /* Return if unsuccessful. */ 543 if (new_cond == NULL_TREE) 544 break; 545 546 /* Dump details. */ 547 if (dump_file && (dump_flags & TDF_DETAILS)) 548 { 549 fprintf (dump_file, " Replaced '"); 550 print_generic_expr (dump_file, cond, dump_flags); 551 fprintf (dump_file, "' with '"); 552 print_generic_expr (dump_file, new_cond, dump_flags); 553 fprintf (dump_file, "'\n"); 554 } 555 556 COND_EXPR_COND (cond_expr) = new_cond; 557 update_stmt (cond_expr); 558 559 if (has_zero_uses (test_var)) 560 { 561 tree def = SSA_NAME_DEF_STMT (test_var); 562 block_stmt_iterator bsi = bsi_for_stmt (def); 563 bsi_remove (&bsi, true); 564 } 565 } 566 567 /* There are further simplifications that can be performed 568 on COND_EXPRs. Specifically, when comparing an SSA_NAME 569 against a constant where the SSA_NAME is the result of a 570 conversion. Perhaps this should be folded into the rest 571 of the COND_EXPR simplification code. */ 572 simplify_cond (cond_expr); 573} 574 575/* We've just substituted an ADDR_EXPR into stmt. Update all the 576 relevant data structures to match. */ 577 578static void 579tidy_after_forward_propagate_addr (tree stmt) 580{ 581 /* We may have turned a trapping insn into a non-trapping insn. */ 582 if (maybe_clean_or_replace_eh_stmt (stmt, stmt) 583 && tree_purge_dead_eh_edges (bb_for_stmt (stmt))) 584 cfg_changed = true; 585 586 if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR) 587 recompute_tree_invariant_for_addr_expr (TREE_OPERAND (stmt, 1)); 588 589 mark_new_vars_to_rename (stmt); 590} 591 592/* STMT defines LHS which is contains the address of the 0th element 593 in an array. USE_STMT uses LHS to compute the address of an 594 arbitrary element within the array. The (variable) byte offset 595 of the element is contained in OFFSET. 596 597 We walk back through the use-def chains of OFFSET to verify that 598 it is indeed computing the offset of an element within the array 599 and extract the index corresponding to the given byte offset. 600 601 We then try to fold the entire address expression into a form 602 &array[index]. 603 604 If we are successful, we replace the right hand side of USE_STMT 605 with the new address computation. */ 606 607static bool 608forward_propagate_addr_into_variable_array_index (tree offset, tree lhs, 609 tree stmt, tree use_stmt) 610{ 611 tree index; 612 613 /* The offset must be defined by a simple MODIFY_EXPR statement. */ 614 if (TREE_CODE (offset) != MODIFY_EXPR) 615 return false; 616 617 /* The RHS of the statement which defines OFFSET must be a gimple 618 cast of another SSA_NAME. */ 619 offset = TREE_OPERAND (offset, 1); 620 if (!is_gimple_cast (offset)) 621 return false; 622 623 offset = TREE_OPERAND (offset, 0); 624 if (TREE_CODE (offset) != SSA_NAME) 625 return false; 626 627 /* Get the defining statement of the offset before type 628 conversion. */ 629 offset = SSA_NAME_DEF_STMT (offset); 630 631 /* The statement which defines OFFSET before type conversion 632 must be a simple MODIFY_EXPR. */ 633 if (TREE_CODE (offset) != MODIFY_EXPR) 634 return false; 635 636 /* The RHS of the statement which defines OFFSET must be a 637 multiplication of an object by the size of the array elements. 638 This implicitly verifies that the size of the array elements 639 is constant. */ 640 offset = TREE_OPERAND (offset, 1); 641 if (TREE_CODE (offset) != MULT_EXPR 642 || TREE_CODE (TREE_OPERAND (offset, 1)) != INTEGER_CST 643 || !simple_cst_equal (TREE_OPERAND (offset, 1), 644 TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (lhs))))) 645 return false; 646 647 /* The first operand to the MULT_EXPR is the desired index. */ 648 index = TREE_OPERAND (offset, 0); 649 650 /* Replace the pointer addition with array indexing. */ 651 TREE_OPERAND (use_stmt, 1) = unshare_expr (TREE_OPERAND (stmt, 1)); 652 TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 0), 1) = index; 653 654 /* That should have created gimple, so there is no need to 655 record information to undo the propagation. */ 656 fold_stmt_inplace (use_stmt); 657 tidy_after_forward_propagate_addr (use_stmt); 658 return true; 659} 660 661/* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>. 662 663 Try to forward propagate the ADDR_EXPR into the use USE_STMT. 664 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF 665 node or for recovery of array indexing from pointer arithmetic. 666 667 CHANGED is an optional pointer to a boolean variable set to true if 668 either the LHS or RHS was changed in the USE_STMT. 669 670 Return true if the propagation was successful (the propagation can 671 be not totally successful, yet things may have been changed). */ 672 673static bool 674forward_propagate_addr_expr_1 (tree stmt, tree use_stmt, bool *changed) 675{ 676 tree name = TREE_OPERAND (stmt, 0); 677 tree lhs, rhs, array_ref; 678 679 /* Strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS. 680 ADDR_EXPR will not appear on the LHS. */ 681 lhs = TREE_OPERAND (use_stmt, 0); 682 while (TREE_CODE (lhs) == COMPONENT_REF || TREE_CODE (lhs) == ARRAY_REF) 683 lhs = TREE_OPERAND (lhs, 0); 684 685 /* Now see if the LHS node is an INDIRECT_REF using NAME. If so, 686 propagate the ADDR_EXPR into the use of NAME and fold the result. */ 687 if (TREE_CODE (lhs) == INDIRECT_REF && TREE_OPERAND (lhs, 0) == name) 688 { 689 /* This should always succeed in creating gimple, so there is 690 no need to save enough state to undo this propagation. */ 691 TREE_OPERAND (lhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1)); 692 fold_stmt_inplace (use_stmt); 693 tidy_after_forward_propagate_addr (use_stmt); 694 if (changed) 695 *changed = true; 696 } 697 698 /* Trivial case. The use statement could be a trivial copy. We 699 go ahead and handle that case here since it's trivial and 700 removes the need to run copy-prop before this pass to get 701 the best results. Also note that by handling this case here 702 we can catch some cascading effects, ie the single use is 703 in a copy, and the copy is used later by a single INDIRECT_REF 704 for example. */ 705 else if (TREE_CODE (lhs) == SSA_NAME && TREE_OPERAND (use_stmt, 1) == name) 706 { 707 TREE_OPERAND (use_stmt, 1) = unshare_expr (TREE_OPERAND (stmt, 1)); 708 tidy_after_forward_propagate_addr (use_stmt); 709 if (changed) 710 *changed = true; 711 return true; 712 } 713 714 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR 715 nodes from the RHS. */ 716 rhs = TREE_OPERAND (use_stmt, 1); 717 while (TREE_CODE (rhs) == COMPONENT_REF 718 || TREE_CODE (rhs) == ARRAY_REF 719 || TREE_CODE (rhs) == ADDR_EXPR) 720 rhs = TREE_OPERAND (rhs, 0); 721 722 /* Now see if the RHS node is an INDIRECT_REF using NAME. If so, 723 propagate the ADDR_EXPR into the use of NAME and fold the result. */ 724 if (TREE_CODE (rhs) == INDIRECT_REF && TREE_OPERAND (rhs, 0) == name) 725 { 726 /* This should always succeed in creating gimple, so there is 727 no need to save enough state to undo this propagation. */ 728 TREE_OPERAND (rhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1)); 729 fold_stmt_inplace (use_stmt); 730 tidy_after_forward_propagate_addr (use_stmt); 731 if (changed) 732 *changed = true; 733 return true; 734 } 735 736 /* The remaining cases are all for turning pointer arithmetic into 737 array indexing. They only apply when we have the address of 738 element zero in an array. If that is not the case then there 739 is nothing to do. */ 740 array_ref = TREE_OPERAND (TREE_OPERAND (stmt, 1), 0); 741 if (TREE_CODE (array_ref) != ARRAY_REF 742 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE 743 || !integer_zerop (TREE_OPERAND (array_ref, 1))) 744 return false; 745 746 /* If the use of the ADDR_EXPR must be a PLUS_EXPR, or else there 747 is nothing to do. */ 748 if (TREE_CODE (rhs) != PLUS_EXPR) 749 return false; 750 751 /* Try to optimize &x[0] + C where C is a multiple of the size 752 of the elements in X into &x[C/element size]. */ 753 if (TREE_OPERAND (rhs, 0) == name 754 && TREE_CODE (TREE_OPERAND (rhs, 1)) == INTEGER_CST) 755 { 756 tree orig = unshare_expr (rhs); 757 TREE_OPERAND (rhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1)); 758 759 /* If folding succeeds, then we have just exposed new variables 760 in USE_STMT which will need to be renamed. If folding fails, 761 then we need to put everything back the way it was. */ 762 if (fold_stmt_inplace (use_stmt)) 763 { 764 tidy_after_forward_propagate_addr (use_stmt); 765 if (changed) 766 *changed = true; 767 return true; 768 } 769 else 770 { 771 TREE_OPERAND (use_stmt, 1) = orig; 772 update_stmt (use_stmt); 773 return false; 774 } 775 } 776 777 /* Try to optimize &x[0] + OFFSET where OFFSET is defined by 778 converting a multiplication of an index by the size of the 779 array elements, then the result is converted into the proper 780 type for the arithmetic. */ 781 if (TREE_OPERAND (rhs, 0) == name 782 && TREE_CODE (TREE_OPERAND (rhs, 1)) == SSA_NAME 783 /* Avoid problems with IVopts creating PLUS_EXPRs with a 784 different type than their operands. */ 785 && lang_hooks.types_compatible_p (TREE_TYPE (name), TREE_TYPE (rhs))) 786 { 787 bool res; 788 tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1)); 789 790 res = forward_propagate_addr_into_variable_array_index (offset_stmt, lhs, 791 stmt, use_stmt); 792 if (res && changed) 793 *changed = true; 794 return res; 795 } 796 797 /* Same as the previous case, except the operands of the PLUS_EXPR 798 were reversed. */ 799 if (TREE_OPERAND (rhs, 1) == name 800 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME 801 /* Avoid problems with IVopts creating PLUS_EXPRs with a 802 different type than their operands. */ 803 && lang_hooks.types_compatible_p (TREE_TYPE (name), TREE_TYPE (rhs))) 804 { 805 bool res; 806 tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0)); 807 res = forward_propagate_addr_into_variable_array_index (offset_stmt, lhs, 808 stmt, use_stmt); 809 if (res && changed) 810 *changed = true; 811 return res; 812 } 813 return false; 814} 815 816/* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>. 817 SOME is a pointer to a boolean value indicating whether we 818 propagated the address expression anywhere. 819 820 Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME. 821 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF 822 node or for recovery of array indexing from pointer arithmetic. 823 Returns true, if all uses have been propagated into. */ 824 825static bool 826forward_propagate_addr_expr (tree stmt, bool *some) 827{ 828 int stmt_loop_depth = bb_for_stmt (stmt)->loop_depth; 829 tree name = TREE_OPERAND (stmt, 0); 830 imm_use_iterator iter; 831 tree use_stmt; 832 bool all = true; 833 834 FOR_EACH_IMM_USE_STMT (use_stmt, iter, name) 835 { 836 bool result; 837 838 /* If the use is not in a simple assignment statement, then 839 there is nothing we can do. */ 840 if (TREE_CODE (use_stmt) != MODIFY_EXPR) 841 { 842 all = false; 843 continue; 844 } 845 846 /* If the use is in a deeper loop nest, then we do not want 847 to propagate the ADDR_EXPR into the loop as that is likely 848 adding expression evaluations into the loop. */ 849 if (bb_for_stmt (use_stmt)->loop_depth > stmt_loop_depth) 850 { 851 all = false; 852 continue; 853 } 854 855 /* If the use_stmt has side-effects, don't propagate into it. */ 856 if (stmt_ann (use_stmt)->has_volatile_ops) 857 { 858 all = false; 859 continue; 860 } 861 862 result = forward_propagate_addr_expr_1 (stmt, use_stmt, some); 863 *some |= result; 864 all &= result; 865 } 866 867 return all; 868} 869 870/* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y. 871 If so, we can change STMT into lhs = y which can later be copy 872 propagated. Similarly for negation. 873 874 This could trivially be formulated as a forward propagation 875 to immediate uses. However, we already had an implementation 876 from DOM which used backward propagation via the use-def links. 877 878 It turns out that backward propagation is actually faster as 879 there's less work to do for each NOT/NEG expression we find. 880 Backwards propagation needs to look at the statement in a single 881 backlink. Forward propagation needs to look at potentially more 882 than one forward link. */ 883 884static void 885simplify_not_neg_expr (tree stmt) 886{ 887 tree rhs = TREE_OPERAND (stmt, 1); 888 tree rhs_def_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0)); 889 890 /* See if the RHS_DEF_STMT has the same form as our statement. */ 891 if (TREE_CODE (rhs_def_stmt) == MODIFY_EXPR 892 && TREE_CODE (TREE_OPERAND (rhs_def_stmt, 1)) == TREE_CODE (rhs)) 893 { 894 tree rhs_def_operand = TREE_OPERAND (TREE_OPERAND (rhs_def_stmt, 1), 0); 895 896 /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME. */ 897 if (TREE_CODE (rhs_def_operand) == SSA_NAME 898 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand)) 899 { 900 TREE_OPERAND (stmt, 1) = rhs_def_operand; 901 update_stmt (stmt); 902 } 903 } 904} 905 906/* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of 907 the condition which we may be able to optimize better. */ 908 909static void 910simplify_switch_expr (tree stmt) 911{ 912 tree cond = SWITCH_COND (stmt); 913 tree def, to, ti; 914 915 /* The optimization that we really care about is removing unnecessary 916 casts. That will let us do much better in propagating the inferred 917 constant at the switch target. */ 918 if (TREE_CODE (cond) == SSA_NAME) 919 { 920 def = SSA_NAME_DEF_STMT (cond); 921 if (TREE_CODE (def) == MODIFY_EXPR) 922 { 923 def = TREE_OPERAND (def, 1); 924 if (TREE_CODE (def) == NOP_EXPR) 925 { 926 int need_precision; 927 bool fail; 928 929 def = TREE_OPERAND (def, 0); 930 931#ifdef ENABLE_CHECKING 932 /* ??? Why was Jeff testing this? We are gimple... */ 933 gcc_assert (is_gimple_val (def)); 934#endif 935 936 to = TREE_TYPE (cond); 937 ti = TREE_TYPE (def); 938 939 /* If we have an extension that preserves value, then we 940 can copy the source value into the switch. */ 941 942 need_precision = TYPE_PRECISION (ti); 943 fail = false; 944 if (! INTEGRAL_TYPE_P (ti)) 945 fail = true; 946 else if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti)) 947 fail = true; 948 else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti)) 949 need_precision += 1; 950 if (TYPE_PRECISION (to) < need_precision) 951 fail = true; 952 953 if (!fail) 954 { 955 SWITCH_COND (stmt) = def; 956 update_stmt (stmt); 957 } 958 } 959 } 960 } 961} 962 963/* Main entry point for the forward propagation optimizer. */ 964 965static unsigned int 966tree_ssa_forward_propagate_single_use_vars (void) 967{ 968 basic_block bb; 969 unsigned int todoflags = 0; 970 971 cfg_changed = false; 972 973 FOR_EACH_BB (bb) 974 { 975 block_stmt_iterator bsi; 976 977 /* Note we update BSI within the loop as necessary. */ 978 for (bsi = bsi_start (bb); !bsi_end_p (bsi); ) 979 { 980 tree stmt = bsi_stmt (bsi); 981 982 /* If this statement sets an SSA_NAME to an address, 983 try to propagate the address into the uses of the SSA_NAME. */ 984 if (TREE_CODE (stmt) == MODIFY_EXPR) 985 { 986 tree lhs = TREE_OPERAND (stmt, 0); 987 tree rhs = TREE_OPERAND (stmt, 1); 988 989 990 if (TREE_CODE (lhs) != SSA_NAME) 991 { 992 bsi_next (&bsi); 993 continue; 994 } 995 996 if (TREE_CODE (rhs) == ADDR_EXPR) 997 { 998 bool some = false; 999 if (forward_propagate_addr_expr (stmt, &some)) 1000 bsi_remove (&bsi, true); 1001 else 1002 bsi_next (&bsi); 1003 if (some) 1004 todoflags |= TODO_update_smt_usage; 1005 } 1006 else if ((TREE_CODE (rhs) == BIT_NOT_EXPR 1007 || TREE_CODE (rhs) == NEGATE_EXPR) 1008 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME) 1009 { 1010 simplify_not_neg_expr (stmt); 1011 bsi_next (&bsi); 1012 } 1013 else 1014 bsi_next (&bsi); 1015 } 1016 else if (TREE_CODE (stmt) == SWITCH_EXPR) 1017 { 1018 simplify_switch_expr (stmt); 1019 bsi_next (&bsi); 1020 } 1021 else if (TREE_CODE (stmt) == COND_EXPR) 1022 { 1023 forward_propagate_into_cond (stmt); 1024 bsi_next (&bsi); 1025 } 1026 else 1027 bsi_next (&bsi); 1028 } 1029 } 1030 1031 if (cfg_changed) 1032 cleanup_tree_cfg (); 1033 return todoflags; 1034} 1035 1036 1037static bool 1038gate_forwprop (void) 1039{ 1040 return 1; 1041} 1042 1043struct tree_opt_pass pass_forwprop = { 1044 "forwprop", /* name */ 1045 gate_forwprop, /* gate */ 1046 tree_ssa_forward_propagate_single_use_vars, /* execute */ 1047 NULL, /* sub */ 1048 NULL, /* next */ 1049 0, /* static_pass_number */ 1050 TV_TREE_FORWPROP, /* tv_id */ 1051 PROP_cfg | PROP_ssa 1052 | PROP_alias, /* properties_required */ 1053 0, /* properties_provided */ 1054 PROP_smt_usage, /* properties_destroyed */ 1055 0, /* todo_flags_start */ 1056 TODO_dump_func /* todo_flags_finish */ 1057 | TODO_ggc_collect 1058 | TODO_update_ssa | TODO_verify_ssa, 1059 0 /* letter */ 1060}; 1061