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. 40 41 Note carefully that after propagation the resulting statement 42 must still be a proper gimple statement. Right now we simply 43 only perform propagations we know will result in valid gimple 44 code. One day we'll want to generalize this code. 45 46 One class of common cases we handle is forward propagating a single use 47 variable into a COND_EXPR. 48 49 bb0: 50 x = a COND b; 51 if (x) goto ... else goto ... 52 53 Will be transformed into: 54 55 bb0: 56 if (a COND b) goto ... else goto ... 57 58 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1). 59 60 Or (assuming c1 and c2 are constants): 61 62 bb0: 63 x = a + c1; 64 if (x EQ/NEQ c2) goto ... else goto ... 65 66 Will be transformed into: 67 68 bb0: 69 if (a EQ/NEQ (c2 - c1)) goto ... else goto ... 70 71 Similarly for x = a - c1. 72 73 Or 74 75 bb0: 76 x = !a 77 if (x) goto ... else goto ... 78 79 Will be transformed into: 80 81 bb0: 82 if (a == 0) goto ... else goto ... 83 84 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1). 85 For these cases, we propagate A into all, possibly more than one, 86 COND_EXPRs that use X. 87 88 Or 89 90 bb0: 91 x = (typecast) a 92 if (x) goto ... else goto ... 93 94 Will be transformed into: 95 96 bb0: 97 if (a != 0) goto ... else goto ... 98 99 (Assuming a is an integral type and x is a boolean or x is an 100 integral and a is a boolean.) 101 102 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1). 103 For these cases, we propagate A into all, possibly more than one, 104 COND_EXPRs that use X. 105 106 In addition to eliminating the variable and the statement which assigns 107 a value to the variable, we may be able to later thread the jump without 108 adding insane complexity in the dominator optimizer. 109 110 Also note these transformations can cascade. We handle this by having 111 a worklist of COND_EXPR statements to examine. As we make a change to 112 a statement, we put it back on the worklist to examine on the next 113 iteration of the main loop. 114 115 A second class of propagation opportunities arises for ADDR_EXPR 116 nodes. 117 118 ptr = &x->y->z; 119 res = *ptr; 120 121 Will get turned into 122 123 res = x->y->z; 124 125 Or 126 127 ptr = &x[0]; 128 ptr2 = ptr + <constant>; 129 130 Will get turned into 131 132 ptr2 = &x[constant/elementsize]; 133 134 Or 135 136 ptr = &x[0]; 137 offset = index * element_size; 138 offset_p = (pointer) offset; 139 ptr2 = ptr + offset_p 140 141 Will get turned into: 142 143 ptr2 = &x[index]; 144 145 146 This will (of course) be extended as other needs arise. */ 147 148 149/* Set to true if we delete EH edges during the optimization. */ 150static bool cfg_changed; 151 152 153/* Given an SSA_NAME VAR, return true if and only if VAR is defined by 154 a comparison. */ 155 156static bool 157ssa_name_defined_by_comparison_p (tree var) 158{ 159 tree def = SSA_NAME_DEF_STMT (var); 160 161 if (TREE_CODE (def) == MODIFY_EXPR) 162 { 163 tree rhs = TREE_OPERAND (def, 1); 164 return COMPARISON_CLASS_P (rhs); 165 } 166 167 return 0; 168} 169 170/* Forward propagate a single-use variable into COND once. Return a 171 new condition if successful. Return NULL_TREE otherwise. */ 172 173static tree 174forward_propagate_into_cond_1 (tree cond, tree *test_var_p) 175{ 176 tree new_cond = NULL_TREE; 177 enum tree_code cond_code = TREE_CODE (cond); 178 tree test_var = NULL_TREE; 179 tree def; 180 tree def_rhs; 181 182 /* If the condition is not a lone variable or an equality test of an 183 SSA_NAME against an integral constant, then we do not have an 184 optimizable case. 185 186 Note these conditions also ensure the COND_EXPR has no 187 virtual operands or other side effects. */ 188 if (cond_code != SSA_NAME 189 && !((cond_code == EQ_EXPR || cond_code == NE_EXPR) 190 && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME 191 && CONSTANT_CLASS_P (TREE_OPERAND (cond, 1)) 192 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1))))) 193 return NULL_TREE; 194 195 /* Extract the single variable used in the test into TEST_VAR. */ 196 if (cond_code == SSA_NAME) 197 test_var = cond; 198 else 199 test_var = TREE_OPERAND (cond, 0); 200 201 /* Now get the defining statement for TEST_VAR. Skip this case if 202 it's not defined by some MODIFY_EXPR. */ 203 def = SSA_NAME_DEF_STMT (test_var); 204 if (TREE_CODE (def) != MODIFY_EXPR) 205 return NULL_TREE; 206 207 def_rhs = TREE_OPERAND (def, 1); 208 209 /* If TEST_VAR is set by adding or subtracting a constant 210 from an SSA_NAME, then it is interesting to us as we 211 can adjust the constant in the conditional and thus 212 eliminate the arithmetic operation. */ 213 if (TREE_CODE (def_rhs) == PLUS_EXPR 214 || TREE_CODE (def_rhs) == MINUS_EXPR) 215 { 216 tree op0 = TREE_OPERAND (def_rhs, 0); 217 tree op1 = TREE_OPERAND (def_rhs, 1); 218 219 /* The first operand must be an SSA_NAME and the second 220 operand must be a constant. */ 221 if (TREE_CODE (op0) != SSA_NAME 222 || !CONSTANT_CLASS_P (op1) 223 || !INTEGRAL_TYPE_P (TREE_TYPE (op1))) 224 return NULL_TREE; 225 226 /* Don't propagate if the first operand occurs in 227 an abnormal PHI. */ 228 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)) 229 return NULL_TREE; 230 231 if (has_single_use (test_var)) 232 { 233 enum tree_code new_code; 234 tree t; 235 236 /* If the variable was defined via X + C, then we must 237 subtract C from the constant in the conditional. 238 Otherwise we add C to the constant in the 239 conditional. The result must fold into a valid 240 gimple operand to be optimizable. */ 241 new_code = (TREE_CODE (def_rhs) == PLUS_EXPR 242 ? MINUS_EXPR : PLUS_EXPR); 243 t = int_const_binop (new_code, TREE_OPERAND (cond, 1), op1, 0); 244 if (!is_gimple_val (t)) 245 return NULL_TREE; 246 247 new_cond = build (cond_code, boolean_type_node, op0, t); 248 } 249 } 250 251 /* These cases require comparisons of a naked SSA_NAME or 252 comparison of an SSA_NAME against zero or one. */ 253 else if (TREE_CODE (cond) == SSA_NAME 254 || integer_zerop (TREE_OPERAND (cond, 1)) 255 || integer_onep (TREE_OPERAND (cond, 1))) 256 { 257 /* If TEST_VAR is set from a relational operation 258 between two SSA_NAMEs or a combination of an SSA_NAME 259 and a constant, then it is interesting. */ 260 if (COMPARISON_CLASS_P (def_rhs)) 261 { 262 tree op0 = TREE_OPERAND (def_rhs, 0); 263 tree op1 = TREE_OPERAND (def_rhs, 1); 264 265 /* Both operands of DEF_RHS must be SSA_NAMEs or 266 constants. */ 267 if ((TREE_CODE (op0) != SSA_NAME 268 && !is_gimple_min_invariant (op0)) 269 || (TREE_CODE (op1) != SSA_NAME 270 && !is_gimple_min_invariant (op1))) 271 return NULL_TREE; 272 273 /* Don't propagate if the first operand occurs in 274 an abnormal PHI. */ 275 if (TREE_CODE (op0) == SSA_NAME 276 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)) 277 return NULL_TREE; 278 279 /* Don't propagate if the second operand occurs in 280 an abnormal PHI. */ 281 if (TREE_CODE (op1) == SSA_NAME 282 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1)) 283 return NULL_TREE; 284 285 if (has_single_use (test_var)) 286 { 287 /* TEST_VAR was set from a relational operator. */ 288 new_cond = build (TREE_CODE (def_rhs), 289 boolean_type_node, op0, op1); 290 291 /* Invert the conditional if necessary. */ 292 if ((cond_code == EQ_EXPR 293 && integer_zerop (TREE_OPERAND (cond, 1))) 294 || (cond_code == NE_EXPR 295 && integer_onep (TREE_OPERAND (cond, 1)))) 296 { 297 new_cond = invert_truthvalue (new_cond); 298 299 /* If we did not get a simple relational 300 expression or bare SSA_NAME, then we can 301 not optimize this case. */ 302 if (!COMPARISON_CLASS_P (new_cond) 303 && TREE_CODE (new_cond) != SSA_NAME) 304 new_cond = NULL_TREE; 305 } 306 } 307 } 308 309 /* If TEST_VAR is set from a TRUTH_NOT_EXPR, then it 310 is interesting. */ 311 else if (TREE_CODE (def_rhs) == TRUTH_NOT_EXPR) 312 { 313 enum tree_code new_code; 314 315 def_rhs = TREE_OPERAND (def_rhs, 0); 316 317 /* DEF_RHS must be an SSA_NAME or constant. */ 318 if (TREE_CODE (def_rhs) != SSA_NAME 319 && !is_gimple_min_invariant (def_rhs)) 320 return NULL_TREE; 321 322 /* Don't propagate if the operand occurs in 323 an abnormal PHI. */ 324 if (TREE_CODE (def_rhs) == SSA_NAME 325 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_rhs)) 326 return NULL_TREE; 327 328 if (cond_code == SSA_NAME 329 || (cond_code == NE_EXPR 330 && integer_zerop (TREE_OPERAND (cond, 1))) 331 || (cond_code == EQ_EXPR 332 && integer_onep (TREE_OPERAND (cond, 1)))) 333 new_code = EQ_EXPR; 334 else 335 new_code = NE_EXPR; 336 337 new_cond = build2 (new_code, boolean_type_node, def_rhs, 338 fold_convert (TREE_TYPE (def_rhs), 339 integer_zero_node)); 340 } 341 342 /* If TEST_VAR was set from a cast of an integer type 343 to a boolean type or a cast of a boolean to an 344 integral, then it is interesting. */ 345 else if (TREE_CODE (def_rhs) == NOP_EXPR 346 || TREE_CODE (def_rhs) == CONVERT_EXPR) 347 { 348 tree outer_type; 349 tree inner_type; 350 351 outer_type = TREE_TYPE (def_rhs); 352 inner_type = TREE_TYPE (TREE_OPERAND (def_rhs, 0)); 353 354 if ((TREE_CODE (outer_type) == BOOLEAN_TYPE 355 && INTEGRAL_TYPE_P (inner_type)) 356 || (TREE_CODE (inner_type) == BOOLEAN_TYPE 357 && INTEGRAL_TYPE_P (outer_type))) 358 ; 359 else if (INTEGRAL_TYPE_P (outer_type) 360 && INTEGRAL_TYPE_P (inner_type) 361 && TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME 362 && ssa_name_defined_by_comparison_p (TREE_OPERAND (def_rhs, 363 0))) 364 ; 365 else 366 return NULL_TREE; 367 368 /* Don't propagate if the operand occurs in 369 an abnormal PHI. */ 370 if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME 371 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND 372 (def_rhs, 0))) 373 return NULL_TREE; 374 375 if (has_single_use (test_var)) 376 { 377 enum tree_code new_code; 378 tree new_arg; 379 380 if (cond_code == SSA_NAME 381 || (cond_code == NE_EXPR 382 && integer_zerop (TREE_OPERAND (cond, 1))) 383 || (cond_code == EQ_EXPR 384 && integer_onep (TREE_OPERAND (cond, 1)))) 385 new_code = NE_EXPR; 386 else 387 new_code = EQ_EXPR; 388 389 new_arg = TREE_OPERAND (def_rhs, 0); 390 new_cond = build2 (new_code, boolean_type_node, new_arg, 391 fold_convert (TREE_TYPE (new_arg), 392 integer_zero_node)); 393 } 394 } 395 } 396 397 *test_var_p = test_var; 398 return new_cond; 399} 400 401/* Forward propagate a single-use variable into COND_EXPR as many 402 times as possible. */ 403 404static void 405forward_propagate_into_cond (tree cond_expr) 406{ 407 gcc_assert (TREE_CODE (cond_expr) == COND_EXPR); 408 409 while (1) 410 { 411 tree test_var = NULL_TREE; 412 tree cond = COND_EXPR_COND (cond_expr); 413 tree new_cond = forward_propagate_into_cond_1 (cond, &test_var); 414 415 /* Return if unsuccessful. */ 416 if (new_cond == NULL_TREE) 417 break; 418 419 /* Dump details. */ 420 if (dump_file && (dump_flags & TDF_DETAILS)) 421 { 422 fprintf (dump_file, " Replaced '"); 423 print_generic_expr (dump_file, cond, dump_flags); 424 fprintf (dump_file, "' with '"); 425 print_generic_expr (dump_file, new_cond, dump_flags); 426 fprintf (dump_file, "'\n"); 427 } 428 429 COND_EXPR_COND (cond_expr) = new_cond; 430 update_stmt (cond_expr); 431 432 if (has_zero_uses (test_var)) 433 { 434 tree def = SSA_NAME_DEF_STMT (test_var); 435 block_stmt_iterator bsi = bsi_for_stmt (def); 436 bsi_remove (&bsi); 437 } 438 } 439} 440 441/* We've just substituted an ADDR_EXPR into stmt. Update all the 442 relevant data structures to match. */ 443 444static void 445tidy_after_forward_propagate_addr (tree stmt) 446{ 447 mark_new_vars_to_rename (stmt); 448 449 /* We may have turned a trapping insn into a non-trapping insn. */ 450 if (maybe_clean_or_replace_eh_stmt (stmt, stmt) 451 && tree_purge_dead_eh_edges (bb_for_stmt (stmt))) 452 cfg_changed = true; 453 454 if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR) 455 recompute_tree_invarant_for_addr_expr (TREE_OPERAND (stmt, 1)); 456 457 update_stmt (stmt); 458} 459 460/* STMT defines LHS which is contains the address of the 0th element 461 in an array. USE_STMT uses LHS to compute the address of an 462 arbitrary element within the array. The (variable) byte offset 463 of the element is contained in OFFSET. 464 465 We walk back through the use-def chains of OFFSET to verify that 466 it is indeed computing the offset of an element within the array 467 and extract the index corresponding to the given byte offset. 468 469 We then try to fold the entire address expression into a form 470 &array[index]. 471 472 If we are successful, we replace the right hand side of USE_STMT 473 with the new address computation. */ 474 475static bool 476forward_propagate_addr_into_variable_array_index (tree offset, tree lhs, 477 tree stmt, tree use_stmt) 478{ 479 tree index; 480 481 /* The offset must be defined by a simple MODIFY_EXPR statement. */ 482 if (TREE_CODE (offset) != MODIFY_EXPR) 483 return false; 484 485 /* The RHS of the statement which defines OFFSET must be a gimple 486 cast of another SSA_NAME. */ 487 offset = TREE_OPERAND (offset, 1); 488 if (!is_gimple_cast (offset)) 489 return false; 490 491 offset = TREE_OPERAND (offset, 0); 492 if (TREE_CODE (offset) != SSA_NAME) 493 return false; 494 495 /* Get the defining statement of the offset before type 496 conversion. */ 497 offset = SSA_NAME_DEF_STMT (offset); 498 499 /* The statement which defines OFFSET before type conversion 500 must be a simple MODIFY_EXPR. */ 501 if (TREE_CODE (offset) != MODIFY_EXPR) 502 return false; 503 504 /* The RHS of the statement which defines OFFSET must be a 505 multiplication of an object by the size of the array elements. 506 This implicitly verifies that the size of the array elements 507 is constant. */ 508 offset = TREE_OPERAND (offset, 1); 509 if (TREE_CODE (offset) != MULT_EXPR 510 || TREE_CODE (TREE_OPERAND (offset, 1)) != INTEGER_CST 511 || !simple_cst_equal (TREE_OPERAND (offset, 1), 512 TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (lhs))))) 513 return false; 514 515 /* The first operand to the MULT_EXPR is the desired index. */ 516 index = TREE_OPERAND (offset, 0); 517 518 /* Replace the pointer addition with array indexing. */ 519 TREE_OPERAND (use_stmt, 1) = unshare_expr (TREE_OPERAND (stmt, 1)); 520 TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 0), 1) = index; 521 522 /* That should have created gimple, so there is no need to 523 record information to undo the propagation. */ 524 fold_stmt_inplace (use_stmt); 525 tidy_after_forward_propagate_addr (use_stmt); 526 return true; 527} 528 529/* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>. 530 531 Try to forward propagate the ADDR_EXPR into the uses of the SSA_NAME. 532 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF 533 node or for recovery of array indexing from pointer arithmetic. */ 534 535static bool 536forward_propagate_addr_expr (tree stmt) 537{ 538 int stmt_loop_depth = bb_for_stmt (stmt)->loop_depth; 539 tree name = TREE_OPERAND (stmt, 0); 540 use_operand_p imm_use; 541 tree use_stmt, lhs, rhs, array_ref; 542 543 /* We require that the SSA_NAME holding the result of the ADDR_EXPR 544 be used only once. That may be overly conservative in that we 545 could propagate into multiple uses. However, that would effectively 546 be un-cseing the ADDR_EXPR, which is probably not what we want. */ 547 single_imm_use (name, &imm_use, &use_stmt); 548 if (!use_stmt) 549 return false; 550 551 /* If the use is not in a simple assignment statement, then 552 there is nothing we can do. */ 553 if (TREE_CODE (use_stmt) != MODIFY_EXPR) 554 return false; 555 556 /* If the use is in a deeper loop nest, then we do not want 557 to propagate the ADDR_EXPR into the loop as that is likely 558 adding expression evaluations into the loop. */ 559 if (bb_for_stmt (use_stmt)->loop_depth > stmt_loop_depth) 560 return false; 561 562 /* Strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS. 563 ADDR_EXPR will not appear on the LHS. */ 564 lhs = TREE_OPERAND (use_stmt, 0); 565 while (TREE_CODE (lhs) == COMPONENT_REF || TREE_CODE (lhs) == ARRAY_REF) 566 lhs = TREE_OPERAND (lhs, 0); 567 568 /* Now see if the LHS node is an INDIRECT_REF using NAME. If so, 569 propagate the ADDR_EXPR into the use of NAME and fold the result. */ 570 if (TREE_CODE (lhs) == INDIRECT_REF && TREE_OPERAND (lhs, 0) == name) 571 { 572 /* This should always succeed in creating gimple, so there is 573 no need to save enough state to undo this propagation. */ 574 TREE_OPERAND (lhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1)); 575 fold_stmt_inplace (use_stmt); 576 tidy_after_forward_propagate_addr (use_stmt); 577 return true; 578 } 579 580 /* Trivial case. The use statement could be a trivial copy. We 581 go ahead and handle that case here since it's trivial and 582 removes the need to run copy-prop before this pass to get 583 the best results. Also note that by handling this case here 584 we can catch some cascading effects, ie the single use is 585 in a copy, and the copy is used later by a single INDIRECT_REF 586 for example. */ 587 if (TREE_CODE (lhs) == SSA_NAME && TREE_OPERAND (use_stmt, 1) == name) 588 { 589 TREE_OPERAND (use_stmt, 1) = unshare_expr (TREE_OPERAND (stmt, 1)); 590 tidy_after_forward_propagate_addr (use_stmt); 591 return true; 592 } 593 594 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR 595 nodes from the RHS. */ 596 rhs = TREE_OPERAND (use_stmt, 1); 597 while (TREE_CODE (rhs) == COMPONENT_REF 598 || TREE_CODE (rhs) == ARRAY_REF 599 || TREE_CODE (rhs) == ADDR_EXPR) 600 rhs = TREE_OPERAND (rhs, 0); 601 602 /* Now see if the RHS node is an INDIRECT_REF using NAME. If so, 603 propagate the ADDR_EXPR into the use of NAME and fold the result. */ 604 if (TREE_CODE (rhs) == INDIRECT_REF && TREE_OPERAND (rhs, 0) == name) 605 { 606 /* This should always succeed in creating gimple, so there is 607 no need to save enough state to undo this propagation. */ 608 TREE_OPERAND (rhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1)); 609 fold_stmt_inplace (use_stmt); 610 tidy_after_forward_propagate_addr (use_stmt); 611 return true; 612 } 613 614 /* The remaining cases are all for turning pointer arithmetic into 615 array indexing. They only apply when we have the address of 616 element zero in an array. If that is not the case then there 617 is nothing to do. */ 618 array_ref = TREE_OPERAND (TREE_OPERAND (stmt, 1), 0); 619 if (TREE_CODE (array_ref) != ARRAY_REF 620 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE 621 || !integer_zerop (TREE_OPERAND (array_ref, 1))) 622 return false; 623 624 /* If the use of the ADDR_EXPR must be a PLUS_EXPR, or else there 625 is nothing to do. */ 626 if (TREE_CODE (rhs) != PLUS_EXPR) 627 return false; 628 629 /* Try to optimize &x[0] + C where C is a multiple of the size 630 of the elements in X into &x[C/element size]. */ 631 if (TREE_OPERAND (rhs, 0) == name 632 && TREE_CODE (TREE_OPERAND (rhs, 1)) == INTEGER_CST) 633 { 634 tree orig = unshare_expr (rhs); 635 TREE_OPERAND (rhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1)); 636 637 /* If folding succeeds, then we have just exposed new variables 638 in USE_STMT which will need to be renamed. If folding fails, 639 then we need to put everything back the way it was. */ 640 if (fold_stmt_inplace (use_stmt)) 641 { 642 tidy_after_forward_propagate_addr (use_stmt); 643 return true; 644 } 645 else 646 { 647 TREE_OPERAND (use_stmt, 1) = orig; 648 update_stmt (use_stmt); 649 return false; 650 } 651 } 652 653 /* Try to optimize &x[0] + OFFSET where OFFSET is defined by 654 converting a multiplication of an index by the size of the 655 array elements, then the result is converted into the proper 656 type for the arithmetic. */ 657 if (TREE_OPERAND (rhs, 0) == name 658 && TREE_CODE (TREE_OPERAND (rhs, 1)) == SSA_NAME 659 /* Avoid problems with IVopts creating PLUS_EXPRs with a 660 different type than their operands. */ 661 && lang_hooks.types_compatible_p (TREE_TYPE (name), TREE_TYPE (rhs))) 662 { 663 tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1)); 664 return forward_propagate_addr_into_variable_array_index (offset_stmt, lhs, 665 stmt, use_stmt); 666 } 667 668 /* Same as the previous case, except the operands of the PLUS_EXPR 669 were reversed. */ 670 if (TREE_OPERAND (rhs, 1) == name 671 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME 672 /* Avoid problems with IVopts creating PLUS_EXPRs with a 673 different type than their operands. */ 674 && lang_hooks.types_compatible_p (TREE_TYPE (name), TREE_TYPE (rhs))) 675 { 676 tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0)); 677 return forward_propagate_addr_into_variable_array_index (offset_stmt, lhs, 678 stmt, use_stmt); 679 } 680 return false; 681} 682 683/* Main entry point for the forward propagation optimizer. */ 684 685static void 686tree_ssa_forward_propagate_single_use_vars (void) 687{ 688 basic_block bb; 689 690 cfg_changed = false; 691 692 FOR_EACH_BB (bb) 693 { 694 block_stmt_iterator bsi; 695 696 /* Note we update BSI within the loop as necessary. */ 697 for (bsi = bsi_start (bb); !bsi_end_p (bsi); ) 698 { 699 tree stmt = bsi_stmt (bsi); 700 701 /* If this statement sets an SSA_NAME to an address, 702 try to propagate the address into the uses of the SSA_NAME. */ 703 if (TREE_CODE (stmt) == MODIFY_EXPR 704 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR 705 && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME) 706 { 707 if (forward_propagate_addr_expr (stmt)) 708 bsi_remove (&bsi); 709 else 710 bsi_next (&bsi); 711 } 712 else if (TREE_CODE (stmt) == COND_EXPR) 713 { 714 forward_propagate_into_cond (stmt); 715 bsi_next (&bsi); 716 } 717 else 718 bsi_next (&bsi); 719 } 720 } 721 722 if (cfg_changed) 723 cleanup_tree_cfg (); 724} 725 726 727static bool 728gate_forwprop (void) 729{ 730 return 1; 731} 732 733struct tree_opt_pass pass_forwprop = { 734 "forwprop", /* name */ 735 gate_forwprop, /* gate */ 736 tree_ssa_forward_propagate_single_use_vars, /* execute */ 737 NULL, /* sub */ 738 NULL, /* next */ 739 0, /* static_pass_number */ 740 TV_TREE_FORWPROP, /* tv_id */ 741 PROP_cfg | PROP_ssa 742 | PROP_alias, /* properties_required */ 743 0, /* properties_provided */ 744 0, /* properties_destroyed */ 745 0, /* todo_flags_start */ 746 TODO_dump_func | TODO_ggc_collect /* todo_flags_finish */ 747 | TODO_update_ssa | TODO_verify_ssa, 748 0 /* letter */ 749}; 750