1 /* Forward propagation of expressions for single use variables. 2 Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010, 2011 3 Free Software Foundation, Inc. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 3, or (at your option) 10 any later version. 11 12 GCC is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "tm.h" 25 #include "tree.h" 26 #include "tm_p.h" 27 #include "basic-block.h" 28 #include "timevar.h" 29 #include "gimple-pretty-print.h" 30 #include "tree-flow.h" 31 #include "tree-pass.h" 32 #include "tree-dump.h" 33 #include "langhooks.h" 34 #include "flags.h" 35 #include "gimple.h" 36 #include "expr.h" 37 38 /* This pass propagates the RHS of assignment statements into use 39 sites of the LHS of the assignment. It's basically a specialized 40 form of tree combination. It is hoped all of this can disappear 41 when we have a generalized tree combiner. 42 43 One class of common cases we handle is forward propagating a single use 44 variable into a COND_EXPR. 45 46 bb0: 47 x = a COND b; 48 if (x) goto ... else goto ... 49 50 Will be transformed into: 51 52 bb0: 53 if (a COND b) goto ... else goto ... 54 55 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1). 56 57 Or (assuming c1 and c2 are constants): 58 59 bb0: 60 x = a + c1; 61 if (x EQ/NEQ c2) goto ... else goto ... 62 63 Will be transformed into: 64 65 bb0: 66 if (a EQ/NEQ (c2 - c1)) goto ... else goto ... 67 68 Similarly for x = a - c1. 69 70 Or 71 72 bb0: 73 x = !a 74 if (x) goto ... else goto ... 75 76 Will be transformed into: 77 78 bb0: 79 if (a == 0) goto ... else goto ... 80 81 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1). 82 For these cases, we propagate A into all, possibly more than one, 83 COND_EXPRs that use X. 84 85 Or 86 87 bb0: 88 x = (typecast) a 89 if (x) goto ... else goto ... 90 91 Will be transformed into: 92 93 bb0: 94 if (a != 0) goto ... else goto ... 95 96 (Assuming a is an integral type and x is a boolean or x is an 97 integral and a is a boolean.) 98 99 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1). 100 For these cases, we propagate A into all, possibly more than one, 101 COND_EXPRs that use X. 102 103 In addition to eliminating the variable and the statement which assigns 104 a value to the variable, we may be able to later thread the jump without 105 adding insane complexity in the dominator optimizer. 106 107 Also note these transformations can cascade. We handle this by having 108 a worklist of COND_EXPR statements to examine. As we make a change to 109 a statement, we put it back on the worklist to examine on the next 110 iteration of the main loop. 111 112 A second class of propagation opportunities arises for ADDR_EXPR 113 nodes. 114 115 ptr = &x->y->z; 116 res = *ptr; 117 118 Will get turned into 119 120 res = x->y->z; 121 122 Or 123 ptr = (type1*)&type2var; 124 res = *ptr 125 126 Will get turned into (if type1 and type2 are the same size 127 and neither have volatile on them): 128 res = VIEW_CONVERT_EXPR<type1>(type2var) 129 130 Or 131 132 ptr = &x[0]; 133 ptr2 = ptr + <constant>; 134 135 Will get turned into 136 137 ptr2 = &x[constant/elementsize]; 138 139 Or 140 141 ptr = &x[0]; 142 offset = index * element_size; 143 offset_p = (pointer) offset; 144 ptr2 = ptr + offset_p 145 146 Will get turned into: 147 148 ptr2 = &x[index]; 149 150 Or 151 ssa = (int) decl 152 res = ssa & 1 153 154 Provided that decl has known alignment >= 2, will get turned into 155 156 res = 0 157 158 We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to 159 allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent 160 {NOT_EXPR,NEG_EXPR}. 161 162 This will (of course) be extended as other needs arise. */ 163 164 static bool forward_propagate_addr_expr (tree name, tree rhs); 165 166 /* Set to true if we delete EH edges during the optimization. */ 167 static bool cfg_changed; 168 169 static tree rhs_to_tree (tree type, gimple stmt); 170 171 /* Get the next statement we can propagate NAME's value into skipping 172 trivial copies. Returns the statement that is suitable as a 173 propagation destination or NULL_TREE if there is no such one. 174 This only returns destinations in a single-use chain. FINAL_NAME_P 175 if non-NULL is written to the ssa name that represents the use. */ 176 177 static gimple 178 get_prop_dest_stmt (tree name, tree *final_name_p) 179 { 180 use_operand_p use; 181 gimple use_stmt; 182 183 do { 184 /* If name has multiple uses, bail out. */ 185 if (!single_imm_use (name, &use, &use_stmt)) 186 return NULL; 187 188 /* If this is not a trivial copy, we found it. */ 189 if (!gimple_assign_ssa_name_copy_p (use_stmt) 190 || gimple_assign_rhs1 (use_stmt) != name) 191 break; 192 193 /* Continue searching uses of the copy destination. */ 194 name = gimple_assign_lhs (use_stmt); 195 } while (1); 196 197 if (final_name_p) 198 *final_name_p = name; 199 200 return use_stmt; 201 } 202 203 /* Get the statement we can propagate from into NAME skipping 204 trivial copies. Returns the statement which defines the 205 propagation source or NULL_TREE if there is no such one. 206 If SINGLE_USE_ONLY is set considers only sources which have 207 a single use chain up to NAME. If SINGLE_USE_P is non-null, 208 it is set to whether the chain to NAME is a single use chain 209 or not. SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set. */ 210 211 static gimple 212 get_prop_source_stmt (tree name, bool single_use_only, bool *single_use_p) 213 { 214 bool single_use = true; 215 216 do { 217 gimple def_stmt = SSA_NAME_DEF_STMT (name); 218 219 if (!has_single_use (name)) 220 { 221 single_use = false; 222 if (single_use_only) 223 return NULL; 224 } 225 226 /* If name is defined by a PHI node or is the default def, bail out. */ 227 if (!is_gimple_assign (def_stmt)) 228 return NULL; 229 230 /* If def_stmt is not a simple copy, we possibly found it. */ 231 if (!gimple_assign_ssa_name_copy_p (def_stmt)) 232 { 233 tree rhs; 234 235 if (!single_use_only && single_use_p) 236 *single_use_p = single_use; 237 238 /* We can look through pointer conversions in the search 239 for a useful stmt for the comparison folding. */ 240 rhs = gimple_assign_rhs1 (def_stmt); 241 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)) 242 && TREE_CODE (rhs) == SSA_NAME 243 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (def_stmt))) 244 && POINTER_TYPE_P (TREE_TYPE (rhs))) 245 name = rhs; 246 else 247 return def_stmt; 248 } 249 else 250 { 251 /* Continue searching the def of the copy source name. */ 252 name = gimple_assign_rhs1 (def_stmt); 253 } 254 } while (1); 255 } 256 257 /* Checks if the destination ssa name in DEF_STMT can be used as 258 propagation source. Returns true if so, otherwise false. */ 259 260 static bool 261 can_propagate_from (gimple def_stmt) 262 { 263 gcc_assert (is_gimple_assign (def_stmt)); 264 265 /* If the rhs has side-effects we cannot propagate from it. */ 266 if (gimple_has_volatile_ops (def_stmt)) 267 return false; 268 269 /* If the rhs is a load we cannot propagate from it. */ 270 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_reference 271 || TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_declaration) 272 return false; 273 274 /* Constants can be always propagated. */ 275 if (gimple_assign_single_p (def_stmt) 276 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt))) 277 return true; 278 279 /* We cannot propagate ssa names that occur in abnormal phi nodes. */ 280 if (stmt_references_abnormal_ssa_name (def_stmt)) 281 return false; 282 283 /* If the definition is a conversion of a pointer to a function type, 284 then we can not apply optimizations as some targets require 285 function pointers to be canonicalized and in this case this 286 optimization could eliminate a necessary canonicalization. */ 287 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))) 288 { 289 tree rhs = gimple_assign_rhs1 (def_stmt); 290 if (POINTER_TYPE_P (TREE_TYPE (rhs)) 291 && TREE_CODE (TREE_TYPE (TREE_TYPE (rhs))) == FUNCTION_TYPE) 292 return false; 293 } 294 295 return true; 296 } 297 298 /* Remove a chain of dead statements starting at the definition of 299 NAME. The chain is linked via the first operand of the defining statements. 300 If NAME was replaced in its only use then this function can be used 301 to clean up dead stmts. The function handles already released SSA 302 names gracefully. 303 Returns true if cleanup-cfg has to run. */ 304 305 static bool 306 remove_prop_source_from_use (tree name) 307 { 308 gimple_stmt_iterator gsi; 309 gimple stmt; 310 bool cfg_changed = false; 311 312 do { 313 basic_block bb; 314 315 if (SSA_NAME_IN_FREE_LIST (name) 316 || SSA_NAME_IS_DEFAULT_DEF (name) 317 || !has_zero_uses (name)) 318 return cfg_changed; 319 320 stmt = SSA_NAME_DEF_STMT (name); 321 if (gimple_code (stmt) == GIMPLE_PHI 322 || gimple_has_side_effects (stmt)) 323 return cfg_changed; 324 325 bb = gimple_bb (stmt); 326 gsi = gsi_for_stmt (stmt); 327 unlink_stmt_vdef (stmt); 328 gsi_remove (&gsi, true); 329 release_defs (stmt); 330 cfg_changed |= gimple_purge_dead_eh_edges (bb); 331 332 name = is_gimple_assign (stmt) ? gimple_assign_rhs1 (stmt) : NULL_TREE; 333 } while (name && TREE_CODE (name) == SSA_NAME); 334 335 return cfg_changed; 336 } 337 338 /* Return the rhs of a gimple_assign STMT in a form of a single tree, 339 converted to type TYPE. 340 341 This should disappear, but is needed so we can combine expressions and use 342 the fold() interfaces. Long term, we need to develop folding and combine 343 routines that deal with gimple exclusively . */ 344 345 static tree 346 rhs_to_tree (tree type, gimple stmt) 347 { 348 location_t loc = gimple_location (stmt); 349 enum tree_code code = gimple_assign_rhs_code (stmt); 350 if (get_gimple_rhs_class (code) == GIMPLE_TERNARY_RHS) 351 return fold_build3_loc (loc, code, type, gimple_assign_rhs1 (stmt), 352 gimple_assign_rhs2 (stmt), 353 gimple_assign_rhs3 (stmt)); 354 else if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS) 355 return fold_build2_loc (loc, code, type, gimple_assign_rhs1 (stmt), 356 gimple_assign_rhs2 (stmt)); 357 else if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS) 358 return build1 (code, type, gimple_assign_rhs1 (stmt)); 359 else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS) 360 return gimple_assign_rhs1 (stmt); 361 else 362 gcc_unreachable (); 363 } 364 365 /* Combine OP0 CODE OP1 in the context of a COND_EXPR. Returns 366 the folded result in a form suitable for COND_EXPR_COND or 367 NULL_TREE, if there is no suitable simplified form. If 368 INVARIANT_ONLY is true only gimple_min_invariant results are 369 considered simplified. */ 370 371 static tree 372 combine_cond_expr_cond (gimple stmt, enum tree_code code, tree type, 373 tree op0, tree op1, bool invariant_only) 374 { 375 tree t; 376 377 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison); 378 379 fold_defer_overflow_warnings (); 380 t = fold_binary_loc (gimple_location (stmt), code, type, op0, op1); 381 if (!t) 382 { 383 fold_undefer_overflow_warnings (false, NULL, 0); 384 return NULL_TREE; 385 } 386 387 /* Require that we got a boolean type out if we put one in. */ 388 gcc_assert (TREE_CODE (TREE_TYPE (t)) == TREE_CODE (type)); 389 390 /* Canonicalize the combined condition for use in a COND_EXPR. */ 391 t = canonicalize_cond_expr_cond (t); 392 393 /* Bail out if we required an invariant but didn't get one. */ 394 if (!t || (invariant_only && !is_gimple_min_invariant (t))) 395 { 396 fold_undefer_overflow_warnings (false, NULL, 0); 397 return NULL_TREE; 398 } 399 400 fold_undefer_overflow_warnings (!gimple_no_warning_p (stmt), stmt, 0); 401 402 return t; 403 } 404 405 /* Combine the comparison OP0 CODE OP1 at LOC with the defining statements 406 of its operand. Return a new comparison tree or NULL_TREE if there 407 were no simplifying combines. */ 408 409 static tree 410 forward_propagate_into_comparison_1 (gimple stmt, 411 enum tree_code code, tree type, 412 tree op0, tree op1) 413 { 414 tree tmp = NULL_TREE; 415 tree rhs0 = NULL_TREE, rhs1 = NULL_TREE; 416 bool single_use0_p = false, single_use1_p = false; 417 418 /* For comparisons use the first operand, that is likely to 419 simplify comparisons against constants. */ 420 if (TREE_CODE (op0) == SSA_NAME) 421 { 422 gimple def_stmt = get_prop_source_stmt (op0, false, &single_use0_p); 423 if (def_stmt && can_propagate_from (def_stmt)) 424 { 425 rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt); 426 tmp = combine_cond_expr_cond (stmt, code, type, 427 rhs0, op1, !single_use0_p); 428 if (tmp) 429 return tmp; 430 } 431 } 432 433 /* If that wasn't successful, try the second operand. */ 434 if (TREE_CODE (op1) == SSA_NAME) 435 { 436 gimple def_stmt = get_prop_source_stmt (op1, false, &single_use1_p); 437 if (def_stmt && can_propagate_from (def_stmt)) 438 { 439 rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt); 440 tmp = combine_cond_expr_cond (stmt, code, type, 441 op0, rhs1, !single_use1_p); 442 if (tmp) 443 return tmp; 444 } 445 } 446 447 /* If that wasn't successful either, try both operands. */ 448 if (rhs0 != NULL_TREE 449 && rhs1 != NULL_TREE) 450 tmp = combine_cond_expr_cond (stmt, code, type, 451 rhs0, rhs1, 452 !(single_use0_p && single_use1_p)); 453 454 return tmp; 455 } 456 457 /* Propagate from the ssa name definition statements of the assignment 458 from a comparison at *GSI into the conditional if that simplifies it. 459 Returns 1 if the stmt was modified and 2 if the CFG needs cleanup, 460 otherwise returns 0. */ 461 462 static int 463 forward_propagate_into_comparison (gimple_stmt_iterator *gsi) 464 { 465 gimple stmt = gsi_stmt (*gsi); 466 tree tmp; 467 bool cfg_changed = false; 468 tree type = TREE_TYPE (gimple_assign_lhs (stmt)); 469 tree rhs1 = gimple_assign_rhs1 (stmt); 470 tree rhs2 = gimple_assign_rhs2 (stmt); 471 472 /* Combine the comparison with defining statements. */ 473 tmp = forward_propagate_into_comparison_1 (stmt, 474 gimple_assign_rhs_code (stmt), 475 type, rhs1, rhs2); 476 if (tmp && useless_type_conversion_p (type, TREE_TYPE (tmp))) 477 { 478 gimple_assign_set_rhs_from_tree (gsi, tmp); 479 fold_stmt (gsi); 480 update_stmt (gsi_stmt (*gsi)); 481 482 if (TREE_CODE (rhs1) == SSA_NAME) 483 cfg_changed |= remove_prop_source_from_use (rhs1); 484 if (TREE_CODE (rhs2) == SSA_NAME) 485 cfg_changed |= remove_prop_source_from_use (rhs2); 486 return cfg_changed ? 2 : 1; 487 } 488 489 return 0; 490 } 491 492 /* Propagate from the ssa name definition statements of COND_EXPR 493 in GIMPLE_COND statement STMT into the conditional if that simplifies it. 494 Returns zero if no statement was changed, one if there were 495 changes and two if cfg_cleanup needs to run. 496 497 This must be kept in sync with forward_propagate_into_cond. */ 498 499 static int 500 forward_propagate_into_gimple_cond (gimple stmt) 501 { 502 tree tmp; 503 enum tree_code code = gimple_cond_code (stmt); 504 bool cfg_changed = false; 505 tree rhs1 = gimple_cond_lhs (stmt); 506 tree rhs2 = gimple_cond_rhs (stmt); 507 508 /* We can do tree combining on SSA_NAME and comparison expressions. */ 509 if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison) 510 return 0; 511 512 tmp = forward_propagate_into_comparison_1 (stmt, code, 513 boolean_type_node, 514 rhs1, rhs2); 515 if (tmp) 516 { 517 if (dump_file && tmp) 518 { 519 fprintf (dump_file, " Replaced '"); 520 print_gimple_expr (dump_file, stmt, 0, 0); 521 fprintf (dump_file, "' with '"); 522 print_generic_expr (dump_file, tmp, 0); 523 fprintf (dump_file, "'\n"); 524 } 525 526 gimple_cond_set_condition_from_tree (stmt, unshare_expr (tmp)); 527 update_stmt (stmt); 528 529 if (TREE_CODE (rhs1) == SSA_NAME) 530 cfg_changed |= remove_prop_source_from_use (rhs1); 531 if (TREE_CODE (rhs2) == SSA_NAME) 532 cfg_changed |= remove_prop_source_from_use (rhs2); 533 return (cfg_changed || is_gimple_min_invariant (tmp)) ? 2 : 1; 534 } 535 536 /* Canonicalize _Bool == 0 and _Bool != 1 to _Bool != 0 by swapping edges. */ 537 if ((TREE_CODE (TREE_TYPE (rhs1)) == BOOLEAN_TYPE 538 || (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)) 539 && TYPE_PRECISION (TREE_TYPE (rhs1)) == 1)) 540 && ((code == EQ_EXPR 541 && integer_zerop (rhs2)) 542 || (code == NE_EXPR 543 && integer_onep (rhs2)))) 544 { 545 basic_block bb = gimple_bb (stmt); 546 gimple_cond_set_code (stmt, NE_EXPR); 547 gimple_cond_set_rhs (stmt, build_zero_cst (TREE_TYPE (rhs1))); 548 EDGE_SUCC (bb, 0)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE); 549 EDGE_SUCC (bb, 1)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE); 550 return 1; 551 } 552 553 return 0; 554 } 555 556 557 /* Propagate from the ssa name definition statements of COND_EXPR 558 in the rhs of statement STMT into the conditional if that simplifies it. 559 Returns true zero if the stmt was changed. */ 560 561 static bool 562 forward_propagate_into_cond (gimple_stmt_iterator *gsi_p) 563 { 564 gimple stmt = gsi_stmt (*gsi_p); 565 tree tmp = NULL_TREE; 566 tree cond = gimple_assign_rhs1 (stmt); 567 bool swap = false; 568 569 /* We can do tree combining on SSA_NAME and comparison expressions. */ 570 if (COMPARISON_CLASS_P (cond)) 571 tmp = forward_propagate_into_comparison_1 (stmt, TREE_CODE (cond), 572 boolean_type_node, 573 TREE_OPERAND (cond, 0), 574 TREE_OPERAND (cond, 1)); 575 else if (TREE_CODE (cond) == SSA_NAME) 576 { 577 enum tree_code code; 578 tree name = cond; 579 gimple def_stmt = get_prop_source_stmt (name, true, NULL); 580 if (!def_stmt || !can_propagate_from (def_stmt)) 581 return 0; 582 583 code = gimple_assign_rhs_code (def_stmt); 584 if (TREE_CODE_CLASS (code) == tcc_comparison) 585 tmp = fold_build2_loc (gimple_location (def_stmt), 586 code, 587 boolean_type_node, 588 gimple_assign_rhs1 (def_stmt), 589 gimple_assign_rhs2 (def_stmt)); 590 else if ((code == BIT_NOT_EXPR 591 && TYPE_PRECISION (TREE_TYPE (cond)) == 1) 592 || (code == BIT_XOR_EXPR 593 && integer_onep (gimple_assign_rhs2 (def_stmt)))) 594 { 595 tmp = gimple_assign_rhs1 (def_stmt); 596 swap = true; 597 } 598 } 599 600 if (tmp 601 && is_gimple_condexpr (tmp)) 602 { 603 if (dump_file && tmp) 604 { 605 fprintf (dump_file, " Replaced '"); 606 print_generic_expr (dump_file, cond, 0); 607 fprintf (dump_file, "' with '"); 608 print_generic_expr (dump_file, tmp, 0); 609 fprintf (dump_file, "'\n"); 610 } 611 612 if (integer_onep (tmp)) 613 gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs2 (stmt)); 614 else if (integer_zerop (tmp)) 615 gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs3 (stmt)); 616 else 617 { 618 gimple_assign_set_rhs1 (stmt, unshare_expr (tmp)); 619 if (swap) 620 { 621 tree t = gimple_assign_rhs2 (stmt); 622 gimple_assign_set_rhs2 (stmt, gimple_assign_rhs3 (stmt)); 623 gimple_assign_set_rhs3 (stmt, t); 624 } 625 } 626 stmt = gsi_stmt (*gsi_p); 627 update_stmt (stmt); 628 629 return true; 630 } 631 632 return 0; 633 } 634 635 /* We've just substituted an ADDR_EXPR into stmt. Update all the 636 relevant data structures to match. */ 637 638 static void 639 tidy_after_forward_propagate_addr (gimple stmt) 640 { 641 /* We may have turned a trapping insn into a non-trapping insn. */ 642 if (maybe_clean_or_replace_eh_stmt (stmt, stmt) 643 && gimple_purge_dead_eh_edges (gimple_bb (stmt))) 644 cfg_changed = true; 645 646 if (TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR) 647 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt)); 648 } 649 650 /* DEF_RHS contains the address of the 0th element in an array. 651 USE_STMT uses type of DEF_RHS to compute the address of an 652 arbitrary element within the array. The (variable) byte offset 653 of the element is contained in OFFSET. 654 655 We walk back through the use-def chains of OFFSET to verify that 656 it is indeed computing the offset of an element within the array 657 and extract the index corresponding to the given byte offset. 658 659 We then try to fold the entire address expression into a form 660 &array[index]. 661 662 If we are successful, we replace the right hand side of USE_STMT 663 with the new address computation. */ 664 665 static bool 666 forward_propagate_addr_into_variable_array_index (tree offset, 667 tree def_rhs, 668 gimple_stmt_iterator *use_stmt_gsi) 669 { 670 tree index, tunit; 671 gimple offset_def, use_stmt = gsi_stmt (*use_stmt_gsi); 672 tree new_rhs, tmp; 673 674 if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == ARRAY_REF) 675 tunit = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs))); 676 else if (TREE_CODE (TREE_TYPE (TREE_OPERAND (def_rhs, 0))) == ARRAY_TYPE) 677 tunit = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (TREE_TYPE (def_rhs)))); 678 else 679 return false; 680 if (!host_integerp (tunit, 1)) 681 return false; 682 683 /* Get the offset's defining statement. */ 684 offset_def = SSA_NAME_DEF_STMT (offset); 685 686 /* Try to find an expression for a proper index. This is either a 687 multiplication expression by the element size or just the ssa name we came 688 along in case the element size is one. In that case, however, we do not 689 allow multiplications because they can be computing index to a higher 690 level dimension (PR 37861). */ 691 if (integer_onep (tunit)) 692 { 693 if (is_gimple_assign (offset_def) 694 && gimple_assign_rhs_code (offset_def) == MULT_EXPR) 695 return false; 696 697 index = offset; 698 } 699 else 700 { 701 /* The statement which defines OFFSET before type conversion 702 must be a simple GIMPLE_ASSIGN. */ 703 if (!is_gimple_assign (offset_def)) 704 return false; 705 706 /* The RHS of the statement which defines OFFSET must be a 707 multiplication of an object by the size of the array elements. 708 This implicitly verifies that the size of the array elements 709 is constant. */ 710 if (gimple_assign_rhs_code (offset_def) == MULT_EXPR 711 && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST 712 && tree_int_cst_equal (gimple_assign_rhs2 (offset_def), tunit)) 713 { 714 /* The first operand to the MULT_EXPR is the desired index. */ 715 index = gimple_assign_rhs1 (offset_def); 716 } 717 /* If we have idx * tunit + CST * tunit re-associate that. */ 718 else if ((gimple_assign_rhs_code (offset_def) == PLUS_EXPR 719 || gimple_assign_rhs_code (offset_def) == MINUS_EXPR) 720 && TREE_CODE (gimple_assign_rhs1 (offset_def)) == SSA_NAME 721 && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST 722 && (tmp = div_if_zero_remainder (EXACT_DIV_EXPR, 723 gimple_assign_rhs2 (offset_def), 724 tunit)) != NULL_TREE) 725 { 726 gimple offset_def2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (offset_def)); 727 if (is_gimple_assign (offset_def2) 728 && gimple_assign_rhs_code (offset_def2) == MULT_EXPR 729 && TREE_CODE (gimple_assign_rhs2 (offset_def2)) == INTEGER_CST 730 && tree_int_cst_equal (gimple_assign_rhs2 (offset_def2), tunit)) 731 { 732 index = fold_build2 (gimple_assign_rhs_code (offset_def), 733 TREE_TYPE (offset), 734 gimple_assign_rhs1 (offset_def2), tmp); 735 } 736 else 737 return false; 738 } 739 else 740 return false; 741 } 742 743 /* Replace the pointer addition with array indexing. */ 744 index = force_gimple_operand_gsi (use_stmt_gsi, index, true, NULL_TREE, 745 true, GSI_SAME_STMT); 746 if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == ARRAY_REF) 747 { 748 new_rhs = unshare_expr (def_rhs); 749 TREE_OPERAND (TREE_OPERAND (new_rhs, 0), 1) = index; 750 } 751 else 752 { 753 new_rhs = build4 (ARRAY_REF, TREE_TYPE (TREE_TYPE (TREE_TYPE (def_rhs))), 754 unshare_expr (TREE_OPERAND (def_rhs, 0)), 755 index, integer_zero_node, NULL_TREE); 756 new_rhs = build_fold_addr_expr (new_rhs); 757 if (!useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (use_stmt)), 758 TREE_TYPE (new_rhs))) 759 { 760 new_rhs = force_gimple_operand_gsi (use_stmt_gsi, new_rhs, true, 761 NULL_TREE, true, GSI_SAME_STMT); 762 new_rhs = fold_convert (TREE_TYPE (gimple_assign_lhs (use_stmt)), 763 new_rhs); 764 } 765 } 766 gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs); 767 fold_stmt (use_stmt_gsi); 768 tidy_after_forward_propagate_addr (gsi_stmt (*use_stmt_gsi)); 769 return true; 770 } 771 772 /* NAME is a SSA_NAME representing DEF_RHS which is of the form 773 ADDR_EXPR <whatever>. 774 775 Try to forward propagate the ADDR_EXPR into the use USE_STMT. 776 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF 777 node or for recovery of array indexing from pointer arithmetic. 778 779 Return true if the propagation was successful (the propagation can 780 be not totally successful, yet things may have been changed). */ 781 782 static bool 783 forward_propagate_addr_expr_1 (tree name, tree def_rhs, 784 gimple_stmt_iterator *use_stmt_gsi, 785 bool single_use_p) 786 { 787 tree lhs, rhs, rhs2, array_ref; 788 gimple use_stmt = gsi_stmt (*use_stmt_gsi); 789 enum tree_code rhs_code; 790 bool res = true; 791 792 gcc_assert (TREE_CODE (def_rhs) == ADDR_EXPR); 793 794 lhs = gimple_assign_lhs (use_stmt); 795 rhs_code = gimple_assign_rhs_code (use_stmt); 796 rhs = gimple_assign_rhs1 (use_stmt); 797 798 /* Trivial cases. The use statement could be a trivial copy or a 799 useless conversion. Recurse to the uses of the lhs as copyprop does 800 not copy through different variant pointers and FRE does not catch 801 all useless conversions. Treat the case of a single-use name and 802 a conversion to def_rhs type separate, though. */ 803 if (TREE_CODE (lhs) == SSA_NAME 804 && ((rhs_code == SSA_NAME && rhs == name) 805 || CONVERT_EXPR_CODE_P (rhs_code))) 806 { 807 /* Only recurse if we don't deal with a single use or we cannot 808 do the propagation to the current statement. In particular 809 we can end up with a conversion needed for a non-invariant 810 address which we cannot do in a single statement. */ 811 if (!single_use_p 812 || (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)) 813 && (!is_gimple_min_invariant (def_rhs) 814 || (INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 815 && POINTER_TYPE_P (TREE_TYPE (def_rhs)) 816 && (TYPE_PRECISION (TREE_TYPE (lhs)) 817 > TYPE_PRECISION (TREE_TYPE (def_rhs))))))) 818 return forward_propagate_addr_expr (lhs, def_rhs); 819 820 gimple_assign_set_rhs1 (use_stmt, unshare_expr (def_rhs)); 821 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs))) 822 gimple_assign_set_rhs_code (use_stmt, TREE_CODE (def_rhs)); 823 else 824 gimple_assign_set_rhs_code (use_stmt, NOP_EXPR); 825 return true; 826 } 827 828 /* Propagate through constant pointer adjustments. */ 829 if (TREE_CODE (lhs) == SSA_NAME 830 && rhs_code == POINTER_PLUS_EXPR 831 && rhs == name 832 && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST) 833 { 834 tree new_def_rhs; 835 /* As we come here with non-invariant addresses in def_rhs we need 836 to make sure we can build a valid constant offsetted address 837 for further propagation. Simply rely on fold building that 838 and check after the fact. */ 839 new_def_rhs = fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (rhs)), 840 def_rhs, 841 fold_convert (ptr_type_node, 842 gimple_assign_rhs2 (use_stmt))); 843 if (TREE_CODE (new_def_rhs) == MEM_REF 844 && !is_gimple_mem_ref_addr (TREE_OPERAND (new_def_rhs, 0))) 845 return false; 846 new_def_rhs = build_fold_addr_expr_with_type (new_def_rhs, 847 TREE_TYPE (rhs)); 848 849 /* Recurse. If we could propagate into all uses of lhs do not 850 bother to replace into the current use but just pretend we did. */ 851 if (TREE_CODE (new_def_rhs) == ADDR_EXPR 852 && forward_propagate_addr_expr (lhs, new_def_rhs)) 853 return true; 854 855 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (new_def_rhs))) 856 gimple_assign_set_rhs_with_ops (use_stmt_gsi, TREE_CODE (new_def_rhs), 857 new_def_rhs, NULL_TREE); 858 else if (is_gimple_min_invariant (new_def_rhs)) 859 gimple_assign_set_rhs_with_ops (use_stmt_gsi, NOP_EXPR, 860 new_def_rhs, NULL_TREE); 861 else 862 return false; 863 gcc_assert (gsi_stmt (*use_stmt_gsi) == use_stmt); 864 update_stmt (use_stmt); 865 return true; 866 } 867 868 /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS. 869 ADDR_EXPR will not appear on the LHS. */ 870 lhs = gimple_assign_lhs (use_stmt); 871 while (handled_component_p (lhs)) 872 lhs = TREE_OPERAND (lhs, 0); 873 874 /* Now see if the LHS node is a MEM_REF using NAME. If so, 875 propagate the ADDR_EXPR into the use of NAME and fold the result. */ 876 if (TREE_CODE (lhs) == MEM_REF 877 && TREE_OPERAND (lhs, 0) == name) 878 { 879 tree def_rhs_base; 880 HOST_WIDE_INT def_rhs_offset; 881 /* If the address is invariant we can always fold it. */ 882 if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0), 883 &def_rhs_offset))) 884 { 885 double_int off = mem_ref_offset (lhs); 886 tree new_ptr; 887 off = double_int_add (off, 888 shwi_to_double_int (def_rhs_offset)); 889 if (TREE_CODE (def_rhs_base) == MEM_REF) 890 { 891 off = double_int_add (off, mem_ref_offset (def_rhs_base)); 892 new_ptr = TREE_OPERAND (def_rhs_base, 0); 893 } 894 else 895 new_ptr = build_fold_addr_expr (def_rhs_base); 896 TREE_OPERAND (lhs, 0) = new_ptr; 897 TREE_OPERAND (lhs, 1) 898 = double_int_to_tree (TREE_TYPE (TREE_OPERAND (lhs, 1)), off); 899 tidy_after_forward_propagate_addr (use_stmt); 900 /* Continue propagating into the RHS if this was not the only use. */ 901 if (single_use_p) 902 return true; 903 } 904 /* If the LHS is a plain dereference and the value type is the same as 905 that of the pointed-to type of the address we can put the 906 dereferenced address on the LHS preserving the original alias-type. */ 907 else if (gimple_assign_lhs (use_stmt) == lhs 908 && integer_zerop (TREE_OPERAND (lhs, 1)) 909 && useless_type_conversion_p 910 (TREE_TYPE (TREE_OPERAND (def_rhs, 0)), 911 TREE_TYPE (gimple_assign_rhs1 (use_stmt)))) 912 { 913 tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0); 914 tree new_offset, new_base, saved, new_lhs; 915 while (handled_component_p (*def_rhs_basep)) 916 def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0); 917 saved = *def_rhs_basep; 918 if (TREE_CODE (*def_rhs_basep) == MEM_REF) 919 { 920 new_base = TREE_OPERAND (*def_rhs_basep, 0); 921 new_offset = fold_convert (TREE_TYPE (TREE_OPERAND (lhs, 1)), 922 TREE_OPERAND (*def_rhs_basep, 1)); 923 } 924 else 925 { 926 new_base = build_fold_addr_expr (*def_rhs_basep); 927 new_offset = TREE_OPERAND (lhs, 1); 928 } 929 *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep), 930 new_base, new_offset); 931 TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (lhs); 932 TREE_SIDE_EFFECTS (*def_rhs_basep) = TREE_SIDE_EFFECTS (lhs); 933 TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (lhs); 934 new_lhs = unshare_expr (TREE_OPERAND (def_rhs, 0)); 935 gimple_assign_set_lhs (use_stmt, new_lhs); 936 TREE_THIS_VOLATILE (new_lhs) = TREE_THIS_VOLATILE (lhs); 937 TREE_SIDE_EFFECTS (new_lhs) = TREE_SIDE_EFFECTS (lhs); 938 *def_rhs_basep = saved; 939 tidy_after_forward_propagate_addr (use_stmt); 940 /* Continue propagating into the RHS if this was not the 941 only use. */ 942 if (single_use_p) 943 return true; 944 } 945 else 946 /* We can have a struct assignment dereferencing our name twice. 947 Note that we didn't propagate into the lhs to not falsely 948 claim we did when propagating into the rhs. */ 949 res = false; 950 } 951 952 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR 953 nodes from the RHS. */ 954 rhs = gimple_assign_rhs1 (use_stmt); 955 if (TREE_CODE (rhs) == ADDR_EXPR) 956 rhs = TREE_OPERAND (rhs, 0); 957 while (handled_component_p (rhs)) 958 rhs = TREE_OPERAND (rhs, 0); 959 960 /* Now see if the RHS node is a MEM_REF using NAME. If so, 961 propagate the ADDR_EXPR into the use of NAME and fold the result. */ 962 if (TREE_CODE (rhs) == MEM_REF 963 && TREE_OPERAND (rhs, 0) == name) 964 { 965 tree def_rhs_base; 966 HOST_WIDE_INT def_rhs_offset; 967 if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0), 968 &def_rhs_offset))) 969 { 970 double_int off = mem_ref_offset (rhs); 971 tree new_ptr; 972 off = double_int_add (off, 973 shwi_to_double_int (def_rhs_offset)); 974 if (TREE_CODE (def_rhs_base) == MEM_REF) 975 { 976 off = double_int_add (off, mem_ref_offset (def_rhs_base)); 977 new_ptr = TREE_OPERAND (def_rhs_base, 0); 978 } 979 else 980 new_ptr = build_fold_addr_expr (def_rhs_base); 981 TREE_OPERAND (rhs, 0) = new_ptr; 982 TREE_OPERAND (rhs, 1) 983 = double_int_to_tree (TREE_TYPE (TREE_OPERAND (rhs, 1)), off); 984 fold_stmt_inplace (use_stmt_gsi); 985 tidy_after_forward_propagate_addr (use_stmt); 986 return res; 987 } 988 /* If the RHS is a plain dereference and the value type is the same as 989 that of the pointed-to type of the address we can put the 990 dereferenced address on the RHS preserving the original alias-type. */ 991 else if (gimple_assign_rhs1 (use_stmt) == rhs 992 && integer_zerop (TREE_OPERAND (rhs, 1)) 993 && useless_type_conversion_p 994 (TREE_TYPE (gimple_assign_lhs (use_stmt)), 995 TREE_TYPE (TREE_OPERAND (def_rhs, 0)))) 996 { 997 tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0); 998 tree new_offset, new_base, saved, new_rhs; 999 while (handled_component_p (*def_rhs_basep)) 1000 def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0); 1001 saved = *def_rhs_basep; 1002 if (TREE_CODE (*def_rhs_basep) == MEM_REF) 1003 { 1004 new_base = TREE_OPERAND (*def_rhs_basep, 0); 1005 new_offset = fold_convert (TREE_TYPE (TREE_OPERAND (rhs, 1)), 1006 TREE_OPERAND (*def_rhs_basep, 1)); 1007 } 1008 else 1009 { 1010 new_base = build_fold_addr_expr (*def_rhs_basep); 1011 new_offset = TREE_OPERAND (rhs, 1); 1012 } 1013 *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep), 1014 new_base, new_offset); 1015 TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (rhs); 1016 TREE_SIDE_EFFECTS (*def_rhs_basep) = TREE_SIDE_EFFECTS (rhs); 1017 TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (rhs); 1018 new_rhs = unshare_expr (TREE_OPERAND (def_rhs, 0)); 1019 gimple_assign_set_rhs1 (use_stmt, new_rhs); 1020 TREE_THIS_VOLATILE (new_rhs) = TREE_THIS_VOLATILE (rhs); 1021 TREE_SIDE_EFFECTS (new_rhs) = TREE_SIDE_EFFECTS (rhs); 1022 *def_rhs_basep = saved; 1023 fold_stmt_inplace (use_stmt_gsi); 1024 tidy_after_forward_propagate_addr (use_stmt); 1025 return res; 1026 } 1027 } 1028 1029 /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there 1030 is nothing to do. */ 1031 if (gimple_assign_rhs_code (use_stmt) != POINTER_PLUS_EXPR 1032 || gimple_assign_rhs1 (use_stmt) != name) 1033 return false; 1034 1035 /* The remaining cases are all for turning pointer arithmetic into 1036 array indexing. They only apply when we have the address of 1037 element zero in an array. If that is not the case then there 1038 is nothing to do. */ 1039 array_ref = TREE_OPERAND (def_rhs, 0); 1040 if ((TREE_CODE (array_ref) != ARRAY_REF 1041 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE 1042 || TREE_CODE (TREE_OPERAND (array_ref, 1)) != INTEGER_CST) 1043 && TREE_CODE (TREE_TYPE (array_ref)) != ARRAY_TYPE) 1044 return false; 1045 1046 rhs2 = gimple_assign_rhs2 (use_stmt); 1047 /* Optimize &x[C1] p+ C2 to &x p+ C3 with C3 = C1 * element_size + C2. */ 1048 if (TREE_CODE (rhs2) == INTEGER_CST) 1049 { 1050 tree new_rhs = build1_loc (gimple_location (use_stmt), 1051 ADDR_EXPR, TREE_TYPE (def_rhs), 1052 fold_build2 (MEM_REF, 1053 TREE_TYPE (TREE_TYPE (def_rhs)), 1054 unshare_expr (def_rhs), 1055 fold_convert (ptr_type_node, 1056 rhs2))); 1057 gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs); 1058 use_stmt = gsi_stmt (*use_stmt_gsi); 1059 update_stmt (use_stmt); 1060 tidy_after_forward_propagate_addr (use_stmt); 1061 return true; 1062 } 1063 1064 /* Try to optimize &x[0] p+ OFFSET where OFFSET is defined by 1065 converting a multiplication of an index by the size of the 1066 array elements, then the result is converted into the proper 1067 type for the arithmetic. */ 1068 if (TREE_CODE (rhs2) == SSA_NAME 1069 && (TREE_CODE (array_ref) != ARRAY_REF 1070 || integer_zerop (TREE_OPERAND (array_ref, 1))) 1071 && useless_type_conversion_p (TREE_TYPE (name), TREE_TYPE (def_rhs)) 1072 /* Avoid problems with IVopts creating PLUS_EXPRs with a 1073 different type than their operands. */ 1074 && useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs))) 1075 return forward_propagate_addr_into_variable_array_index (rhs2, def_rhs, 1076 use_stmt_gsi); 1077 return false; 1078 } 1079 1080 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>. 1081 1082 Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME. 1083 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF 1084 node or for recovery of array indexing from pointer arithmetic. 1085 Returns true, if all uses have been propagated into. */ 1086 1087 static bool 1088 forward_propagate_addr_expr (tree name, tree rhs) 1089 { 1090 int stmt_loop_depth = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_depth; 1091 imm_use_iterator iter; 1092 gimple use_stmt; 1093 bool all = true; 1094 bool single_use_p = has_single_use (name); 1095 1096 FOR_EACH_IMM_USE_STMT (use_stmt, iter, name) 1097 { 1098 bool result; 1099 tree use_rhs; 1100 1101 /* If the use is not in a simple assignment statement, then 1102 there is nothing we can do. */ 1103 if (gimple_code (use_stmt) != GIMPLE_ASSIGN) 1104 { 1105 if (!is_gimple_debug (use_stmt)) 1106 all = false; 1107 continue; 1108 } 1109 1110 /* If the use is in a deeper loop nest, then we do not want 1111 to propagate non-invariant ADDR_EXPRs into the loop as that 1112 is likely adding expression evaluations into the loop. */ 1113 if (gimple_bb (use_stmt)->loop_depth > stmt_loop_depth 1114 && !is_gimple_min_invariant (rhs)) 1115 { 1116 all = false; 1117 continue; 1118 } 1119 1120 { 1121 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); 1122 result = forward_propagate_addr_expr_1 (name, rhs, &gsi, 1123 single_use_p); 1124 /* If the use has moved to a different statement adjust 1125 the update machinery for the old statement too. */ 1126 if (use_stmt != gsi_stmt (gsi)) 1127 { 1128 update_stmt (use_stmt); 1129 use_stmt = gsi_stmt (gsi); 1130 } 1131 1132 update_stmt (use_stmt); 1133 } 1134 all &= result; 1135 1136 /* Remove intermediate now unused copy and conversion chains. */ 1137 use_rhs = gimple_assign_rhs1 (use_stmt); 1138 if (result 1139 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME 1140 && TREE_CODE (use_rhs) == SSA_NAME 1141 && has_zero_uses (gimple_assign_lhs (use_stmt))) 1142 { 1143 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); 1144 release_defs (use_stmt); 1145 gsi_remove (&gsi, true); 1146 } 1147 } 1148 1149 return all && has_zero_uses (name); 1150 } 1151 1152 1153 /* Forward propagate the comparison defined in STMT like 1154 cond_1 = x CMP y to uses of the form 1155 a_1 = (T')cond_1 1156 a_1 = !cond_1 1157 a_1 = cond_1 != 0 1158 Returns true if stmt is now unused. */ 1159 1160 static bool 1161 forward_propagate_comparison (gimple stmt) 1162 { 1163 tree name = gimple_assign_lhs (stmt); 1164 gimple use_stmt; 1165 tree tmp = NULL_TREE; 1166 gimple_stmt_iterator gsi; 1167 enum tree_code code; 1168 tree lhs; 1169 1170 /* Don't propagate ssa names that occur in abnormal phis. */ 1171 if ((TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME 1172 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt))) 1173 || (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME 1174 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs2 (stmt)))) 1175 return false; 1176 1177 /* Do not un-cse comparisons. But propagate through copies. */ 1178 use_stmt = get_prop_dest_stmt (name, &name); 1179 if (!use_stmt 1180 || !is_gimple_assign (use_stmt)) 1181 return false; 1182 1183 code = gimple_assign_rhs_code (use_stmt); 1184 lhs = gimple_assign_lhs (use_stmt); 1185 if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs))) 1186 return false; 1187 1188 /* We can propagate the condition into a statement that 1189 computes the logical negation of the comparison result. */ 1190 if ((code == BIT_NOT_EXPR 1191 && TYPE_PRECISION (TREE_TYPE (lhs)) == 1) 1192 || (code == BIT_XOR_EXPR 1193 && integer_onep (gimple_assign_rhs2 (use_stmt)))) 1194 { 1195 tree type = TREE_TYPE (gimple_assign_rhs1 (stmt)); 1196 bool nans = HONOR_NANS (TYPE_MODE (type)); 1197 enum tree_code inv_code; 1198 inv_code = invert_tree_comparison (gimple_assign_rhs_code (stmt), nans); 1199 if (inv_code == ERROR_MARK) 1200 return false; 1201 1202 tmp = build2 (inv_code, TREE_TYPE (lhs), gimple_assign_rhs1 (stmt), 1203 gimple_assign_rhs2 (stmt)); 1204 } 1205 else 1206 return false; 1207 1208 gsi = gsi_for_stmt (use_stmt); 1209 gimple_assign_set_rhs_from_tree (&gsi, unshare_expr (tmp)); 1210 use_stmt = gsi_stmt (gsi); 1211 update_stmt (use_stmt); 1212 1213 if (dump_file && (dump_flags & TDF_DETAILS)) 1214 { 1215 fprintf (dump_file, " Replaced '"); 1216 print_gimple_expr (dump_file, stmt, 0, dump_flags); 1217 fprintf (dump_file, "' with '"); 1218 print_gimple_expr (dump_file, use_stmt, 0, dump_flags); 1219 fprintf (dump_file, "'\n"); 1220 } 1221 1222 /* Remove defining statements. */ 1223 return remove_prop_source_from_use (name); 1224 } 1225 1226 1227 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y. 1228 If so, we can change STMT into lhs = y which can later be copy 1229 propagated. Similarly for negation. 1230 1231 This could trivially be formulated as a forward propagation 1232 to immediate uses. However, we already had an implementation 1233 from DOM which used backward propagation via the use-def links. 1234 1235 It turns out that backward propagation is actually faster as 1236 there's less work to do for each NOT/NEG expression we find. 1237 Backwards propagation needs to look at the statement in a single 1238 backlink. Forward propagation needs to look at potentially more 1239 than one forward link. 1240 1241 Returns true when the statement was changed. */ 1242 1243 static bool 1244 simplify_not_neg_expr (gimple_stmt_iterator *gsi_p) 1245 { 1246 gimple stmt = gsi_stmt (*gsi_p); 1247 tree rhs = gimple_assign_rhs1 (stmt); 1248 gimple rhs_def_stmt = SSA_NAME_DEF_STMT (rhs); 1249 1250 /* See if the RHS_DEF_STMT has the same form as our statement. */ 1251 if (is_gimple_assign (rhs_def_stmt) 1252 && gimple_assign_rhs_code (rhs_def_stmt) == gimple_assign_rhs_code (stmt)) 1253 { 1254 tree rhs_def_operand = gimple_assign_rhs1 (rhs_def_stmt); 1255 1256 /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME. */ 1257 if (TREE_CODE (rhs_def_operand) == SSA_NAME 1258 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand)) 1259 { 1260 gimple_assign_set_rhs_from_tree (gsi_p, rhs_def_operand); 1261 stmt = gsi_stmt (*gsi_p); 1262 update_stmt (stmt); 1263 return true; 1264 } 1265 } 1266 1267 return false; 1268 } 1269 1270 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of 1271 the condition which we may be able to optimize better. */ 1272 1273 static bool 1274 simplify_gimple_switch (gimple stmt) 1275 { 1276 tree cond = gimple_switch_index (stmt); 1277 tree def, to, ti; 1278 gimple def_stmt; 1279 1280 /* The optimization that we really care about is removing unnecessary 1281 casts. That will let us do much better in propagating the inferred 1282 constant at the switch target. */ 1283 if (TREE_CODE (cond) == SSA_NAME) 1284 { 1285 def_stmt = SSA_NAME_DEF_STMT (cond); 1286 if (is_gimple_assign (def_stmt)) 1287 { 1288 if (gimple_assign_rhs_code (def_stmt) == NOP_EXPR) 1289 { 1290 int need_precision; 1291 bool fail; 1292 1293 def = gimple_assign_rhs1 (def_stmt); 1294 1295 /* ??? Why was Jeff testing this? We are gimple... */ 1296 gcc_checking_assert (is_gimple_val (def)); 1297 1298 to = TREE_TYPE (cond); 1299 ti = TREE_TYPE (def); 1300 1301 /* If we have an extension that preserves value, then we 1302 can copy the source value into the switch. */ 1303 1304 need_precision = TYPE_PRECISION (ti); 1305 fail = false; 1306 if (! INTEGRAL_TYPE_P (ti)) 1307 fail = true; 1308 else if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti)) 1309 fail = true; 1310 else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti)) 1311 need_precision += 1; 1312 if (TYPE_PRECISION (to) < need_precision) 1313 fail = true; 1314 1315 if (!fail) 1316 { 1317 gimple_switch_set_index (stmt, def); 1318 update_stmt (stmt); 1319 return true; 1320 } 1321 } 1322 } 1323 } 1324 1325 return false; 1326 } 1327 1328 /* For pointers p2 and p1 return p2 - p1 if the 1329 difference is known and constant, otherwise return NULL. */ 1330 1331 static tree 1332 constant_pointer_difference (tree p1, tree p2) 1333 { 1334 int i, j; 1335 #define CPD_ITERATIONS 5 1336 tree exps[2][CPD_ITERATIONS]; 1337 tree offs[2][CPD_ITERATIONS]; 1338 int cnt[2]; 1339 1340 for (i = 0; i < 2; i++) 1341 { 1342 tree p = i ? p1 : p2; 1343 tree off = size_zero_node; 1344 gimple stmt; 1345 enum tree_code code; 1346 1347 /* For each of p1 and p2 we need to iterate at least 1348 twice, to handle ADDR_EXPR directly in p1/p2, 1349 SSA_NAME with ADDR_EXPR or POINTER_PLUS_EXPR etc. 1350 on definition's stmt RHS. Iterate a few extra times. */ 1351 j = 0; 1352 do 1353 { 1354 if (!POINTER_TYPE_P (TREE_TYPE (p))) 1355 break; 1356 if (TREE_CODE (p) == ADDR_EXPR) 1357 { 1358 tree q = TREE_OPERAND (p, 0); 1359 HOST_WIDE_INT offset; 1360 tree base = get_addr_base_and_unit_offset (q, &offset); 1361 if (base) 1362 { 1363 q = base; 1364 if (offset) 1365 off = size_binop (PLUS_EXPR, off, size_int (offset)); 1366 } 1367 if (TREE_CODE (q) == MEM_REF 1368 && TREE_CODE (TREE_OPERAND (q, 0)) == SSA_NAME) 1369 { 1370 p = TREE_OPERAND (q, 0); 1371 off = size_binop (PLUS_EXPR, off, 1372 double_int_to_tree (sizetype, 1373 mem_ref_offset (q))); 1374 } 1375 else 1376 { 1377 exps[i][j] = q; 1378 offs[i][j++] = off; 1379 break; 1380 } 1381 } 1382 if (TREE_CODE (p) != SSA_NAME) 1383 break; 1384 exps[i][j] = p; 1385 offs[i][j++] = off; 1386 if (j == CPD_ITERATIONS) 1387 break; 1388 stmt = SSA_NAME_DEF_STMT (p); 1389 if (!is_gimple_assign (stmt) || gimple_assign_lhs (stmt) != p) 1390 break; 1391 code = gimple_assign_rhs_code (stmt); 1392 if (code == POINTER_PLUS_EXPR) 1393 { 1394 if (TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST) 1395 break; 1396 off = size_binop (PLUS_EXPR, off, gimple_assign_rhs2 (stmt)); 1397 p = gimple_assign_rhs1 (stmt); 1398 } 1399 else if (code == ADDR_EXPR || code == NOP_EXPR) 1400 p = gimple_assign_rhs1 (stmt); 1401 else 1402 break; 1403 } 1404 while (1); 1405 cnt[i] = j; 1406 } 1407 1408 for (i = 0; i < cnt[0]; i++) 1409 for (j = 0; j < cnt[1]; j++) 1410 if (exps[0][i] == exps[1][j]) 1411 return size_binop (MINUS_EXPR, offs[0][i], offs[1][j]); 1412 1413 return NULL_TREE; 1414 } 1415 1416 /* *GSI_P is a GIMPLE_CALL to a builtin function. 1417 Optimize 1418 memcpy (p, "abcd", 4); 1419 memset (p + 4, ' ', 3); 1420 into 1421 memcpy (p, "abcd ", 7); 1422 call if the latter can be stored by pieces during expansion. */ 1423 1424 static bool 1425 simplify_builtin_call (gimple_stmt_iterator *gsi_p, tree callee2) 1426 { 1427 gimple stmt1, stmt2 = gsi_stmt (*gsi_p); 1428 tree vuse = gimple_vuse (stmt2); 1429 if (vuse == NULL) 1430 return false; 1431 stmt1 = SSA_NAME_DEF_STMT (vuse); 1432 1433 switch (DECL_FUNCTION_CODE (callee2)) 1434 { 1435 case BUILT_IN_MEMSET: 1436 if (gimple_call_num_args (stmt2) != 3 1437 || gimple_call_lhs (stmt2) 1438 || CHAR_BIT != 8 1439 || BITS_PER_UNIT != 8) 1440 break; 1441 else 1442 { 1443 tree callee1; 1444 tree ptr1, src1, str1, off1, len1, lhs1; 1445 tree ptr2 = gimple_call_arg (stmt2, 0); 1446 tree val2 = gimple_call_arg (stmt2, 1); 1447 tree len2 = gimple_call_arg (stmt2, 2); 1448 tree diff, vdef, new_str_cst; 1449 gimple use_stmt; 1450 unsigned int ptr1_align; 1451 unsigned HOST_WIDE_INT src_len; 1452 char *src_buf; 1453 use_operand_p use_p; 1454 1455 if (!host_integerp (val2, 0) 1456 || !host_integerp (len2, 1)) 1457 break; 1458 if (is_gimple_call (stmt1)) 1459 { 1460 /* If first stmt is a call, it needs to be memcpy 1461 or mempcpy, with string literal as second argument and 1462 constant length. */ 1463 callee1 = gimple_call_fndecl (stmt1); 1464 if (callee1 == NULL_TREE 1465 || DECL_BUILT_IN_CLASS (callee1) != BUILT_IN_NORMAL 1466 || gimple_call_num_args (stmt1) != 3) 1467 break; 1468 if (DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMCPY 1469 && DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMPCPY) 1470 break; 1471 ptr1 = gimple_call_arg (stmt1, 0); 1472 src1 = gimple_call_arg (stmt1, 1); 1473 len1 = gimple_call_arg (stmt1, 2); 1474 lhs1 = gimple_call_lhs (stmt1); 1475 if (!host_integerp (len1, 1)) 1476 break; 1477 str1 = string_constant (src1, &off1); 1478 if (str1 == NULL_TREE) 1479 break; 1480 if (!host_integerp (off1, 1) 1481 || compare_tree_int (off1, TREE_STRING_LENGTH (str1) - 1) > 0 1482 || compare_tree_int (len1, TREE_STRING_LENGTH (str1) 1483 - tree_low_cst (off1, 1)) > 0 1484 || TREE_CODE (TREE_TYPE (str1)) != ARRAY_TYPE 1485 || TYPE_MODE (TREE_TYPE (TREE_TYPE (str1))) 1486 != TYPE_MODE (char_type_node)) 1487 break; 1488 } 1489 else if (gimple_assign_single_p (stmt1)) 1490 { 1491 /* Otherwise look for length 1 memcpy optimized into 1492 assignment. */ 1493 ptr1 = gimple_assign_lhs (stmt1); 1494 src1 = gimple_assign_rhs1 (stmt1); 1495 if (TREE_CODE (ptr1) != MEM_REF 1496 || TYPE_MODE (TREE_TYPE (ptr1)) != TYPE_MODE (char_type_node) 1497 || !host_integerp (src1, 0)) 1498 break; 1499 ptr1 = build_fold_addr_expr (ptr1); 1500 callee1 = NULL_TREE; 1501 len1 = size_one_node; 1502 lhs1 = NULL_TREE; 1503 off1 = size_zero_node; 1504 str1 = NULL_TREE; 1505 } 1506 else 1507 break; 1508 1509 diff = constant_pointer_difference (ptr1, ptr2); 1510 if (diff == NULL && lhs1 != NULL) 1511 { 1512 diff = constant_pointer_difference (lhs1, ptr2); 1513 if (DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY 1514 && diff != NULL) 1515 diff = size_binop (PLUS_EXPR, diff, 1516 fold_convert (sizetype, len1)); 1517 } 1518 /* If the difference between the second and first destination pointer 1519 is not constant, or is bigger than memcpy length, bail out. */ 1520 if (diff == NULL 1521 || !host_integerp (diff, 1) 1522 || tree_int_cst_lt (len1, diff)) 1523 break; 1524 1525 /* Use maximum of difference plus memset length and memcpy length 1526 as the new memcpy length, if it is too big, bail out. */ 1527 src_len = tree_low_cst (diff, 1); 1528 src_len += tree_low_cst (len2, 1); 1529 if (src_len < (unsigned HOST_WIDE_INT) tree_low_cst (len1, 1)) 1530 src_len = tree_low_cst (len1, 1); 1531 if (src_len > 1024) 1532 break; 1533 1534 /* If mempcpy value is used elsewhere, bail out, as mempcpy 1535 with bigger length will return different result. */ 1536 if (lhs1 != NULL_TREE 1537 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY 1538 && (TREE_CODE (lhs1) != SSA_NAME 1539 || !single_imm_use (lhs1, &use_p, &use_stmt) 1540 || use_stmt != stmt2)) 1541 break; 1542 1543 /* If anything reads memory in between memcpy and memset 1544 call, the modified memcpy call might change it. */ 1545 vdef = gimple_vdef (stmt1); 1546 if (vdef != NULL 1547 && (!single_imm_use (vdef, &use_p, &use_stmt) 1548 || use_stmt != stmt2)) 1549 break; 1550 1551 ptr1_align = get_pointer_alignment (ptr1); 1552 /* Construct the new source string literal. */ 1553 src_buf = XALLOCAVEC (char, src_len + 1); 1554 if (callee1) 1555 memcpy (src_buf, 1556 TREE_STRING_POINTER (str1) + tree_low_cst (off1, 1), 1557 tree_low_cst (len1, 1)); 1558 else 1559 src_buf[0] = tree_low_cst (src1, 0); 1560 memset (src_buf + tree_low_cst (diff, 1), 1561 tree_low_cst (val2, 1), tree_low_cst (len2, 1)); 1562 src_buf[src_len] = '\0'; 1563 /* Neither builtin_strncpy_read_str nor builtin_memcpy_read_str 1564 handle embedded '\0's. */ 1565 if (strlen (src_buf) != src_len) 1566 break; 1567 rtl_profile_for_bb (gimple_bb (stmt2)); 1568 /* If the new memcpy wouldn't be emitted by storing the literal 1569 by pieces, this optimization might enlarge .rodata too much, 1570 as commonly used string literals couldn't be shared any 1571 longer. */ 1572 if (!can_store_by_pieces (src_len, 1573 builtin_strncpy_read_str, 1574 src_buf, ptr1_align, false)) 1575 break; 1576 1577 new_str_cst = build_string_literal (src_len, src_buf); 1578 if (callee1) 1579 { 1580 /* If STMT1 is a mem{,p}cpy call, adjust it and remove 1581 memset call. */ 1582 if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY) 1583 gimple_call_set_lhs (stmt1, NULL_TREE); 1584 gimple_call_set_arg (stmt1, 1, new_str_cst); 1585 gimple_call_set_arg (stmt1, 2, 1586 build_int_cst (TREE_TYPE (len1), src_len)); 1587 update_stmt (stmt1); 1588 unlink_stmt_vdef (stmt2); 1589 gsi_remove (gsi_p, true); 1590 release_defs (stmt2); 1591 if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY) 1592 release_ssa_name (lhs1); 1593 return true; 1594 } 1595 else 1596 { 1597 /* Otherwise, if STMT1 is length 1 memcpy optimized into 1598 assignment, remove STMT1 and change memset call into 1599 memcpy call. */ 1600 gimple_stmt_iterator gsi = gsi_for_stmt (stmt1); 1601 1602 if (!is_gimple_val (ptr1)) 1603 ptr1 = force_gimple_operand_gsi (gsi_p, ptr1, true, NULL_TREE, 1604 true, GSI_SAME_STMT); 1605 gimple_call_set_fndecl (stmt2, 1606 builtin_decl_explicit (BUILT_IN_MEMCPY)); 1607 gimple_call_set_arg (stmt2, 0, ptr1); 1608 gimple_call_set_arg (stmt2, 1, new_str_cst); 1609 gimple_call_set_arg (stmt2, 2, 1610 build_int_cst (TREE_TYPE (len2), src_len)); 1611 unlink_stmt_vdef (stmt1); 1612 gsi_remove (&gsi, true); 1613 release_defs (stmt1); 1614 update_stmt (stmt2); 1615 return false; 1616 } 1617 } 1618 break; 1619 default: 1620 break; 1621 } 1622 return false; 1623 } 1624 1625 /* Checks if expression has type of one-bit precision, or is a known 1626 truth-valued expression. */ 1627 static bool 1628 truth_valued_ssa_name (tree name) 1629 { 1630 gimple def; 1631 tree type = TREE_TYPE (name); 1632 1633 if (!INTEGRAL_TYPE_P (type)) 1634 return false; 1635 /* Don't check here for BOOLEAN_TYPE as the precision isn't 1636 necessarily one and so ~X is not equal to !X. */ 1637 if (TYPE_PRECISION (type) == 1) 1638 return true; 1639 def = SSA_NAME_DEF_STMT (name); 1640 if (is_gimple_assign (def)) 1641 return truth_value_p (gimple_assign_rhs_code (def)); 1642 return false; 1643 } 1644 1645 /* Helper routine for simplify_bitwise_binary_1 function. 1646 Return for the SSA name NAME the expression X if it mets condition 1647 NAME = !X. Otherwise return NULL_TREE. 1648 Detected patterns for NAME = !X are: 1649 !X and X == 0 for X with integral type. 1650 X ^ 1, X != 1,or ~X for X with integral type with precision of one. */ 1651 static tree 1652 lookup_logical_inverted_value (tree name) 1653 { 1654 tree op1, op2; 1655 enum tree_code code; 1656 gimple def; 1657 1658 /* If name has none-intergal type, or isn't a SSA_NAME, then 1659 return. */ 1660 if (TREE_CODE (name) != SSA_NAME 1661 || !INTEGRAL_TYPE_P (TREE_TYPE (name))) 1662 return NULL_TREE; 1663 def = SSA_NAME_DEF_STMT (name); 1664 if (!is_gimple_assign (def)) 1665 return NULL_TREE; 1666 1667 code = gimple_assign_rhs_code (def); 1668 op1 = gimple_assign_rhs1 (def); 1669 op2 = NULL_TREE; 1670 1671 /* Get for EQ_EXPR or BIT_XOR_EXPR operation the second operand. 1672 If CODE isn't an EQ_EXPR, BIT_XOR_EXPR, or BIT_NOT_EXPR, then return. */ 1673 if (code == EQ_EXPR || code == NE_EXPR 1674 || code == BIT_XOR_EXPR) 1675 op2 = gimple_assign_rhs2 (def); 1676 1677 switch (code) 1678 { 1679 case BIT_NOT_EXPR: 1680 if (truth_valued_ssa_name (name)) 1681 return op1; 1682 break; 1683 case EQ_EXPR: 1684 /* Check if we have X == 0 and X has an integral type. */ 1685 if (!INTEGRAL_TYPE_P (TREE_TYPE (op1))) 1686 break; 1687 if (integer_zerop (op2)) 1688 return op1; 1689 break; 1690 case NE_EXPR: 1691 /* Check if we have X != 1 and X is a truth-valued. */ 1692 if (!INTEGRAL_TYPE_P (TREE_TYPE (op1))) 1693 break; 1694 if (integer_onep (op2) && truth_valued_ssa_name (op1)) 1695 return op1; 1696 break; 1697 case BIT_XOR_EXPR: 1698 /* Check if we have X ^ 1 and X is truth valued. */ 1699 if (integer_onep (op2) && truth_valued_ssa_name (op1)) 1700 return op1; 1701 break; 1702 default: 1703 break; 1704 } 1705 1706 return NULL_TREE; 1707 } 1708 1709 /* Optimize ARG1 CODE ARG2 to a constant for bitwise binary 1710 operations CODE, if one operand has the logically inverted 1711 value of the other. */ 1712 static tree 1713 simplify_bitwise_binary_1 (enum tree_code code, tree type, 1714 tree arg1, tree arg2) 1715 { 1716 tree anot; 1717 1718 /* If CODE isn't a bitwise binary operation, return NULL_TREE. */ 1719 if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR 1720 && code != BIT_XOR_EXPR) 1721 return NULL_TREE; 1722 1723 /* First check if operands ARG1 and ARG2 are equal. If so 1724 return NULL_TREE as this optimization is handled fold_stmt. */ 1725 if (arg1 == arg2) 1726 return NULL_TREE; 1727 /* See if we have in arguments logical-not patterns. */ 1728 if (((anot = lookup_logical_inverted_value (arg1)) == NULL_TREE 1729 || anot != arg2) 1730 && ((anot = lookup_logical_inverted_value (arg2)) == NULL_TREE 1731 || anot != arg1)) 1732 return NULL_TREE; 1733 1734 /* X & !X -> 0. */ 1735 if (code == BIT_AND_EXPR) 1736 return fold_convert (type, integer_zero_node); 1737 /* X | !X -> 1 and X ^ !X -> 1, if X is truth-valued. */ 1738 if (truth_valued_ssa_name (anot)) 1739 return fold_convert (type, integer_one_node); 1740 1741 /* ??? Otherwise result is (X != 0 ? X : 1). not handled. */ 1742 return NULL_TREE; 1743 } 1744 1745 /* Simplify bitwise binary operations. 1746 Return true if a transformation applied, otherwise return false. */ 1747 1748 static bool 1749 simplify_bitwise_binary (gimple_stmt_iterator *gsi) 1750 { 1751 gimple stmt = gsi_stmt (*gsi); 1752 tree arg1 = gimple_assign_rhs1 (stmt); 1753 tree arg2 = gimple_assign_rhs2 (stmt); 1754 enum tree_code code = gimple_assign_rhs_code (stmt); 1755 tree res; 1756 gimple def1 = NULL, def2 = NULL; 1757 tree def1_arg1, def2_arg1; 1758 enum tree_code def1_code, def2_code; 1759 1760 def1_code = TREE_CODE (arg1); 1761 def1_arg1 = arg1; 1762 if (TREE_CODE (arg1) == SSA_NAME) 1763 { 1764 def1 = SSA_NAME_DEF_STMT (arg1); 1765 if (is_gimple_assign (def1)) 1766 { 1767 def1_code = gimple_assign_rhs_code (def1); 1768 def1_arg1 = gimple_assign_rhs1 (def1); 1769 } 1770 } 1771 1772 def2_code = TREE_CODE (arg2); 1773 def2_arg1 = arg2; 1774 if (TREE_CODE (arg2) == SSA_NAME) 1775 { 1776 def2 = SSA_NAME_DEF_STMT (arg2); 1777 if (is_gimple_assign (def2)) 1778 { 1779 def2_code = gimple_assign_rhs_code (def2); 1780 def2_arg1 = gimple_assign_rhs1 (def2); 1781 } 1782 } 1783 1784 /* Try to fold (type) X op CST -> (type) (X op ((type-x) CST)). */ 1785 if (TREE_CODE (arg2) == INTEGER_CST 1786 && CONVERT_EXPR_CODE_P (def1_code) 1787 && INTEGRAL_TYPE_P (TREE_TYPE (def1_arg1)) 1788 && int_fits_type_p (arg2, TREE_TYPE (def1_arg1))) 1789 { 1790 gimple newop; 1791 tree tem = create_tmp_reg (TREE_TYPE (def1_arg1), NULL); 1792 newop = 1793 gimple_build_assign_with_ops (code, tem, def1_arg1, 1794 fold_convert_loc (gimple_location (stmt), 1795 TREE_TYPE (def1_arg1), 1796 arg2)); 1797 tem = make_ssa_name (tem, newop); 1798 gimple_assign_set_lhs (newop, tem); 1799 gimple_set_location (newop, gimple_location (stmt)); 1800 gsi_insert_before (gsi, newop, GSI_SAME_STMT); 1801 gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR, 1802 tem, NULL_TREE, NULL_TREE); 1803 update_stmt (gsi_stmt (*gsi)); 1804 return true; 1805 } 1806 1807 /* For bitwise binary operations apply operand conversions to the 1808 binary operation result instead of to the operands. This allows 1809 to combine successive conversions and bitwise binary operations. */ 1810 if (CONVERT_EXPR_CODE_P (def1_code) 1811 && CONVERT_EXPR_CODE_P (def2_code) 1812 && types_compatible_p (TREE_TYPE (def1_arg1), TREE_TYPE (def2_arg1)) 1813 /* Make sure that the conversion widens the operands, or has same 1814 precision, or that it changes the operation to a bitfield 1815 precision. */ 1816 && ((TYPE_PRECISION (TREE_TYPE (def1_arg1)) 1817 <= TYPE_PRECISION (TREE_TYPE (arg1))) 1818 || (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (arg1))) 1819 != MODE_INT) 1820 || (TYPE_PRECISION (TREE_TYPE (arg1)) 1821 != GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (arg1)))))) 1822 { 1823 gimple newop; 1824 tree tem = create_tmp_reg (TREE_TYPE (def1_arg1), 1825 NULL); 1826 newop = gimple_build_assign_with_ops (code, tem, def1_arg1, def2_arg1); 1827 tem = make_ssa_name (tem, newop); 1828 gimple_assign_set_lhs (newop, tem); 1829 gimple_set_location (newop, gimple_location (stmt)); 1830 gsi_insert_before (gsi, newop, GSI_SAME_STMT); 1831 gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR, 1832 tem, NULL_TREE, NULL_TREE); 1833 update_stmt (gsi_stmt (*gsi)); 1834 return true; 1835 } 1836 1837 /* (a | CST1) & CST2 -> (a & CST2) | (CST1 & CST2). */ 1838 if (code == BIT_AND_EXPR 1839 && def1_code == BIT_IOR_EXPR 1840 && TREE_CODE (arg2) == INTEGER_CST 1841 && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST) 1842 { 1843 tree cst = fold_build2 (BIT_AND_EXPR, TREE_TYPE (arg2), 1844 arg2, gimple_assign_rhs2 (def1)); 1845 tree tem; 1846 gimple newop; 1847 if (integer_zerop (cst)) 1848 { 1849 gimple_assign_set_rhs1 (stmt, def1_arg1); 1850 update_stmt (stmt); 1851 return true; 1852 } 1853 tem = create_tmp_reg (TREE_TYPE (arg2), NULL); 1854 newop = gimple_build_assign_with_ops (BIT_AND_EXPR, 1855 tem, def1_arg1, arg2); 1856 tem = make_ssa_name (tem, newop); 1857 gimple_assign_set_lhs (newop, tem); 1858 gimple_set_location (newop, gimple_location (stmt)); 1859 /* Make sure to re-process the new stmt as it's walking upwards. */ 1860 gsi_insert_before (gsi, newop, GSI_NEW_STMT); 1861 gimple_assign_set_rhs1 (stmt, tem); 1862 gimple_assign_set_rhs2 (stmt, cst); 1863 gimple_assign_set_rhs_code (stmt, BIT_IOR_EXPR); 1864 update_stmt (stmt); 1865 return true; 1866 } 1867 1868 /* Combine successive equal operations with constants. */ 1869 if ((code == BIT_AND_EXPR 1870 || code == BIT_IOR_EXPR 1871 || code == BIT_XOR_EXPR) 1872 && def1_code == code 1873 && TREE_CODE (arg2) == INTEGER_CST 1874 && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST) 1875 { 1876 tree cst = fold_build2 (code, TREE_TYPE (arg2), 1877 arg2, gimple_assign_rhs2 (def1)); 1878 gimple_assign_set_rhs1 (stmt, def1_arg1); 1879 gimple_assign_set_rhs2 (stmt, cst); 1880 update_stmt (stmt); 1881 return true; 1882 } 1883 1884 /* Canonicalize X ^ ~0 to ~X. */ 1885 if (code == BIT_XOR_EXPR 1886 && TREE_CODE (arg2) == INTEGER_CST 1887 && integer_all_onesp (arg2)) 1888 { 1889 gimple_assign_set_rhs_with_ops (gsi, BIT_NOT_EXPR, arg1, NULL_TREE); 1890 gcc_assert (gsi_stmt (*gsi) == stmt); 1891 update_stmt (stmt); 1892 return true; 1893 } 1894 1895 /* Try simple folding for X op !X, and X op X. */ 1896 res = simplify_bitwise_binary_1 (code, TREE_TYPE (arg1), arg1, arg2); 1897 if (res != NULL_TREE) 1898 { 1899 gimple_assign_set_rhs_from_tree (gsi, res); 1900 update_stmt (gsi_stmt (*gsi)); 1901 return true; 1902 } 1903 1904 return false; 1905 } 1906 1907 1908 /* Perform re-associations of the plus or minus statement STMT that are 1909 always permitted. Returns true if the CFG was changed. */ 1910 1911 static bool 1912 associate_plusminus (gimple_stmt_iterator *gsi) 1913 { 1914 gimple stmt = gsi_stmt (*gsi); 1915 tree rhs1 = gimple_assign_rhs1 (stmt); 1916 tree rhs2 = gimple_assign_rhs2 (stmt); 1917 enum tree_code code = gimple_assign_rhs_code (stmt); 1918 bool changed; 1919 1920 /* We can't reassociate at all for saturating types. */ 1921 if (TYPE_SATURATING (TREE_TYPE (rhs1))) 1922 return false; 1923 1924 /* First contract negates. */ 1925 do 1926 { 1927 changed = false; 1928 1929 /* A +- (-B) -> A -+ B. */ 1930 if (TREE_CODE (rhs2) == SSA_NAME) 1931 { 1932 gimple def_stmt = SSA_NAME_DEF_STMT (rhs2); 1933 if (is_gimple_assign (def_stmt) 1934 && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR 1935 && can_propagate_from (def_stmt)) 1936 { 1937 code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR; 1938 gimple_assign_set_rhs_code (stmt, code); 1939 rhs2 = gimple_assign_rhs1 (def_stmt); 1940 gimple_assign_set_rhs2 (stmt, rhs2); 1941 gimple_set_modified (stmt, true); 1942 changed = true; 1943 } 1944 } 1945 1946 /* (-A) + B -> B - A. */ 1947 if (TREE_CODE (rhs1) == SSA_NAME 1948 && code == PLUS_EXPR) 1949 { 1950 gimple def_stmt = SSA_NAME_DEF_STMT (rhs1); 1951 if (is_gimple_assign (def_stmt) 1952 && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR 1953 && can_propagate_from (def_stmt)) 1954 { 1955 code = MINUS_EXPR; 1956 gimple_assign_set_rhs_code (stmt, code); 1957 rhs1 = rhs2; 1958 gimple_assign_set_rhs1 (stmt, rhs1); 1959 rhs2 = gimple_assign_rhs1 (def_stmt); 1960 gimple_assign_set_rhs2 (stmt, rhs2); 1961 gimple_set_modified (stmt, true); 1962 changed = true; 1963 } 1964 } 1965 } 1966 while (changed); 1967 1968 /* We can't reassociate floating-point or fixed-point plus or minus 1969 because of saturation to +-Inf. */ 1970 if (FLOAT_TYPE_P (TREE_TYPE (rhs1)) 1971 || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1))) 1972 goto out; 1973 1974 /* Second match patterns that allow contracting a plus-minus pair 1975 irrespective of overflow issues. 1976 1977 (A +- B) - A -> +- B 1978 (A +- B) -+ B -> A 1979 (CST +- A) +- CST -> CST +- A 1980 (A + CST) +- CST -> A + CST 1981 ~A + A -> -1 1982 ~A + 1 -> -A 1983 A - (A +- B) -> -+ B 1984 A +- (B +- A) -> +- B 1985 CST +- (CST +- A) -> CST +- A 1986 CST +- (A +- CST) -> CST +- A 1987 A + ~A -> -1 1988 1989 via commutating the addition and contracting operations to zero 1990 by reassociation. */ 1991 1992 if (TREE_CODE (rhs1) == SSA_NAME) 1993 { 1994 gimple def_stmt = SSA_NAME_DEF_STMT (rhs1); 1995 if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt)) 1996 { 1997 enum tree_code def_code = gimple_assign_rhs_code (def_stmt); 1998 if (def_code == PLUS_EXPR 1999 || def_code == MINUS_EXPR) 2000 { 2001 tree def_rhs1 = gimple_assign_rhs1 (def_stmt); 2002 tree def_rhs2 = gimple_assign_rhs2 (def_stmt); 2003 if (operand_equal_p (def_rhs1, rhs2, 0) 2004 && code == MINUS_EXPR) 2005 { 2006 /* (A +- B) - A -> +- B. */ 2007 code = ((def_code == PLUS_EXPR) 2008 ? TREE_CODE (def_rhs2) : NEGATE_EXPR); 2009 rhs1 = def_rhs2; 2010 rhs2 = NULL_TREE; 2011 gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE); 2012 gcc_assert (gsi_stmt (*gsi) == stmt); 2013 gimple_set_modified (stmt, true); 2014 } 2015 else if (operand_equal_p (def_rhs2, rhs2, 0) 2016 && code != def_code) 2017 { 2018 /* (A +- B) -+ B -> A. */ 2019 code = TREE_CODE (def_rhs1); 2020 rhs1 = def_rhs1; 2021 rhs2 = NULL_TREE; 2022 gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE); 2023 gcc_assert (gsi_stmt (*gsi) == stmt); 2024 gimple_set_modified (stmt, true); 2025 } 2026 else if (TREE_CODE (rhs2) == INTEGER_CST 2027 && TREE_CODE (def_rhs1) == INTEGER_CST) 2028 { 2029 /* (CST +- A) +- CST -> CST +- A. */ 2030 tree cst = fold_binary (code, TREE_TYPE (rhs1), 2031 def_rhs1, rhs2); 2032 if (cst && !TREE_OVERFLOW (cst)) 2033 { 2034 code = def_code; 2035 gimple_assign_set_rhs_code (stmt, code); 2036 rhs1 = cst; 2037 gimple_assign_set_rhs1 (stmt, rhs1); 2038 rhs2 = def_rhs2; 2039 gimple_assign_set_rhs2 (stmt, rhs2); 2040 gimple_set_modified (stmt, true); 2041 } 2042 } 2043 else if (TREE_CODE (rhs2) == INTEGER_CST 2044 && TREE_CODE (def_rhs2) == INTEGER_CST 2045 && def_code == PLUS_EXPR) 2046 { 2047 /* (A + CST) +- CST -> A + CST. */ 2048 tree cst = fold_binary (code, TREE_TYPE (rhs1), 2049 def_rhs2, rhs2); 2050 if (cst && !TREE_OVERFLOW (cst)) 2051 { 2052 code = PLUS_EXPR; 2053 gimple_assign_set_rhs_code (stmt, code); 2054 rhs1 = def_rhs1; 2055 gimple_assign_set_rhs1 (stmt, rhs1); 2056 rhs2 = cst; 2057 gimple_assign_set_rhs2 (stmt, rhs2); 2058 gimple_set_modified (stmt, true); 2059 } 2060 } 2061 } 2062 else if (def_code == BIT_NOT_EXPR 2063 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))) 2064 { 2065 tree def_rhs1 = gimple_assign_rhs1 (def_stmt); 2066 if (code == PLUS_EXPR 2067 && operand_equal_p (def_rhs1, rhs2, 0)) 2068 { 2069 /* ~A + A -> -1. */ 2070 code = INTEGER_CST; 2071 rhs1 = build_int_cst_type (TREE_TYPE (rhs2), -1); 2072 rhs2 = NULL_TREE; 2073 gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE); 2074 gcc_assert (gsi_stmt (*gsi) == stmt); 2075 gimple_set_modified (stmt, true); 2076 } 2077 else if (code == PLUS_EXPR 2078 && integer_onep (rhs1)) 2079 { 2080 /* ~A + 1 -> -A. */ 2081 code = NEGATE_EXPR; 2082 rhs1 = def_rhs1; 2083 rhs2 = NULL_TREE; 2084 gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE); 2085 gcc_assert (gsi_stmt (*gsi) == stmt); 2086 gimple_set_modified (stmt, true); 2087 } 2088 } 2089 } 2090 } 2091 2092 if (rhs2 && TREE_CODE (rhs2) == SSA_NAME) 2093 { 2094 gimple def_stmt = SSA_NAME_DEF_STMT (rhs2); 2095 if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt)) 2096 { 2097 enum tree_code def_code = gimple_assign_rhs_code (def_stmt); 2098 if (def_code == PLUS_EXPR 2099 || def_code == MINUS_EXPR) 2100 { 2101 tree def_rhs1 = gimple_assign_rhs1 (def_stmt); 2102 tree def_rhs2 = gimple_assign_rhs2 (def_stmt); 2103 if (operand_equal_p (def_rhs1, rhs1, 0) 2104 && code == MINUS_EXPR) 2105 { 2106 /* A - (A +- B) -> -+ B. */ 2107 code = ((def_code == PLUS_EXPR) 2108 ? NEGATE_EXPR : TREE_CODE (def_rhs2)); 2109 rhs1 = def_rhs2; 2110 rhs2 = NULL_TREE; 2111 gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE); 2112 gcc_assert (gsi_stmt (*gsi) == stmt); 2113 gimple_set_modified (stmt, true); 2114 } 2115 else if (operand_equal_p (def_rhs2, rhs1, 0) 2116 && code != def_code) 2117 { 2118 /* A +- (B +- A) -> +- B. */ 2119 code = ((code == PLUS_EXPR) 2120 ? TREE_CODE (def_rhs1) : NEGATE_EXPR); 2121 rhs1 = def_rhs1; 2122 rhs2 = NULL_TREE; 2123 gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE); 2124 gcc_assert (gsi_stmt (*gsi) == stmt); 2125 gimple_set_modified (stmt, true); 2126 } 2127 else if (TREE_CODE (rhs1) == INTEGER_CST 2128 && TREE_CODE (def_rhs1) == INTEGER_CST) 2129 { 2130 /* CST +- (CST +- A) -> CST +- A. */ 2131 tree cst = fold_binary (code, TREE_TYPE (rhs2), 2132 rhs1, def_rhs1); 2133 if (cst && !TREE_OVERFLOW (cst)) 2134 { 2135 code = (code == def_code ? PLUS_EXPR : MINUS_EXPR); 2136 gimple_assign_set_rhs_code (stmt, code); 2137 rhs1 = cst; 2138 gimple_assign_set_rhs1 (stmt, rhs1); 2139 rhs2 = def_rhs2; 2140 gimple_assign_set_rhs2 (stmt, rhs2); 2141 gimple_set_modified (stmt, true); 2142 } 2143 } 2144 else if (TREE_CODE (rhs1) == INTEGER_CST 2145 && TREE_CODE (def_rhs2) == INTEGER_CST) 2146 { 2147 /* CST +- (A +- CST) -> CST +- A. */ 2148 tree cst = fold_binary (def_code == code 2149 ? PLUS_EXPR : MINUS_EXPR, 2150 TREE_TYPE (rhs2), 2151 rhs1, def_rhs2); 2152 if (cst && !TREE_OVERFLOW (cst)) 2153 { 2154 rhs1 = cst; 2155 gimple_assign_set_rhs1 (stmt, rhs1); 2156 rhs2 = def_rhs1; 2157 gimple_assign_set_rhs2 (stmt, rhs2); 2158 gimple_set_modified (stmt, true); 2159 } 2160 } 2161 } 2162 else if (def_code == BIT_NOT_EXPR 2163 && INTEGRAL_TYPE_P (TREE_TYPE (rhs2))) 2164 { 2165 tree def_rhs1 = gimple_assign_rhs1 (def_stmt); 2166 if (code == PLUS_EXPR 2167 && operand_equal_p (def_rhs1, rhs1, 0)) 2168 { 2169 /* A + ~A -> -1. */ 2170 code = INTEGER_CST; 2171 rhs1 = build_int_cst_type (TREE_TYPE (rhs1), -1); 2172 rhs2 = NULL_TREE; 2173 gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE); 2174 gcc_assert (gsi_stmt (*gsi) == stmt); 2175 gimple_set_modified (stmt, true); 2176 } 2177 } 2178 } 2179 } 2180 2181 out: 2182 if (gimple_modified_p (stmt)) 2183 { 2184 fold_stmt_inplace (gsi); 2185 update_stmt (stmt); 2186 if (maybe_clean_or_replace_eh_stmt (stmt, stmt) 2187 && gimple_purge_dead_eh_edges (gimple_bb (stmt))) 2188 return true; 2189 } 2190 2191 return false; 2192 } 2193 2194 /* Combine two conversions in a row for the second conversion at *GSI. 2195 Returns 1 if there were any changes made, 2 if cfg-cleanup needs to 2196 run. Else it returns 0. */ 2197 2198 static int 2199 combine_conversions (gimple_stmt_iterator *gsi) 2200 { 2201 gimple stmt = gsi_stmt (*gsi); 2202 gimple def_stmt; 2203 tree op0, lhs; 2204 enum tree_code code = gimple_assign_rhs_code (stmt); 2205 2206 gcc_checking_assert (CONVERT_EXPR_CODE_P (code) 2207 || code == FLOAT_EXPR 2208 || code == FIX_TRUNC_EXPR); 2209 2210 lhs = gimple_assign_lhs (stmt); 2211 op0 = gimple_assign_rhs1 (stmt); 2212 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (op0))) 2213 { 2214 gimple_assign_set_rhs_code (stmt, TREE_CODE (op0)); 2215 return 1; 2216 } 2217 2218 if (TREE_CODE (op0) != SSA_NAME) 2219 return 0; 2220 2221 def_stmt = SSA_NAME_DEF_STMT (op0); 2222 if (!is_gimple_assign (def_stmt)) 2223 return 0; 2224 2225 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))) 2226 { 2227 tree defop0 = gimple_assign_rhs1 (def_stmt); 2228 tree type = TREE_TYPE (lhs); 2229 tree inside_type = TREE_TYPE (defop0); 2230 tree inter_type = TREE_TYPE (op0); 2231 int inside_int = INTEGRAL_TYPE_P (inside_type); 2232 int inside_ptr = POINTER_TYPE_P (inside_type); 2233 int inside_float = FLOAT_TYPE_P (inside_type); 2234 int inside_vec = TREE_CODE (inside_type) == VECTOR_TYPE; 2235 unsigned int inside_prec = TYPE_PRECISION (inside_type); 2236 int inside_unsignedp = TYPE_UNSIGNED (inside_type); 2237 int inter_int = INTEGRAL_TYPE_P (inter_type); 2238 int inter_ptr = POINTER_TYPE_P (inter_type); 2239 int inter_float = FLOAT_TYPE_P (inter_type); 2240 int inter_vec = TREE_CODE (inter_type) == VECTOR_TYPE; 2241 unsigned int inter_prec = TYPE_PRECISION (inter_type); 2242 int inter_unsignedp = TYPE_UNSIGNED (inter_type); 2243 int final_int = INTEGRAL_TYPE_P (type); 2244 int final_ptr = POINTER_TYPE_P (type); 2245 int final_float = FLOAT_TYPE_P (type); 2246 int final_vec = TREE_CODE (type) == VECTOR_TYPE; 2247 unsigned int final_prec = TYPE_PRECISION (type); 2248 int final_unsignedp = TYPE_UNSIGNED (type); 2249 2250 /* Don't propagate ssa names that occur in abnormal phis. */ 2251 if (TREE_CODE (defop0) == SSA_NAME 2252 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defop0)) 2253 return 0; 2254 2255 /* In addition to the cases of two conversions in a row 2256 handled below, if we are converting something to its own 2257 type via an object of identical or wider precision, neither 2258 conversion is needed. */ 2259 if (useless_type_conversion_p (type, inside_type) 2260 && (((inter_int || inter_ptr) && final_int) 2261 || (inter_float && final_float)) 2262 && inter_prec >= final_prec) 2263 { 2264 gimple_assign_set_rhs1 (stmt, unshare_expr (defop0)); 2265 gimple_assign_set_rhs_code (stmt, TREE_CODE (defop0)); 2266 update_stmt (stmt); 2267 return remove_prop_source_from_use (op0) ? 2 : 1; 2268 } 2269 2270 /* Likewise, if the intermediate and initial types are either both 2271 float or both integer, we don't need the middle conversion if the 2272 former is wider than the latter and doesn't change the signedness 2273 (for integers). Avoid this if the final type is a pointer since 2274 then we sometimes need the middle conversion. Likewise if the 2275 final type has a precision not equal to the size of its mode. */ 2276 if (((inter_int && inside_int) 2277 || (inter_float && inside_float) 2278 || (inter_vec && inside_vec)) 2279 && inter_prec >= inside_prec 2280 && (inter_float || inter_vec 2281 || inter_unsignedp == inside_unsignedp) 2282 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (type)) 2283 && TYPE_MODE (type) == TYPE_MODE (inter_type)) 2284 && ! final_ptr 2285 && (! final_vec || inter_prec == inside_prec)) 2286 { 2287 gimple_assign_set_rhs1 (stmt, defop0); 2288 update_stmt (stmt); 2289 return remove_prop_source_from_use (op0) ? 2 : 1; 2290 } 2291 2292 /* If we have a sign-extension of a zero-extended value, we can 2293 replace that by a single zero-extension. */ 2294 if (inside_int && inter_int && final_int 2295 && inside_prec < inter_prec && inter_prec < final_prec 2296 && inside_unsignedp && !inter_unsignedp) 2297 { 2298 gimple_assign_set_rhs1 (stmt, defop0); 2299 update_stmt (stmt); 2300 return remove_prop_source_from_use (op0) ? 2 : 1; 2301 } 2302 2303 /* Two conversions in a row are not needed unless: 2304 - some conversion is floating-point (overstrict for now), or 2305 - some conversion is a vector (overstrict for now), or 2306 - the intermediate type is narrower than both initial and 2307 final, or 2308 - the intermediate type and innermost type differ in signedness, 2309 and the outermost type is wider than the intermediate, or 2310 - the initial type is a pointer type and the precisions of the 2311 intermediate and final types differ, or 2312 - the final type is a pointer type and the precisions of the 2313 initial and intermediate types differ. */ 2314 if (! inside_float && ! inter_float && ! final_float 2315 && ! inside_vec && ! inter_vec && ! final_vec 2316 && (inter_prec >= inside_prec || inter_prec >= final_prec) 2317 && ! (inside_int && inter_int 2318 && inter_unsignedp != inside_unsignedp 2319 && inter_prec < final_prec) 2320 && ((inter_unsignedp && inter_prec > inside_prec) 2321 == (final_unsignedp && final_prec > inter_prec)) 2322 && ! (inside_ptr && inter_prec != final_prec) 2323 && ! (final_ptr && inside_prec != inter_prec) 2324 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (type)) 2325 && TYPE_MODE (type) == TYPE_MODE (inter_type))) 2326 { 2327 gimple_assign_set_rhs1 (stmt, defop0); 2328 update_stmt (stmt); 2329 return remove_prop_source_from_use (op0) ? 2 : 1; 2330 } 2331 2332 /* A truncation to an unsigned type should be canonicalized as 2333 bitwise and of a mask. */ 2334 if (final_int && inter_int && inside_int 2335 && final_prec == inside_prec 2336 && final_prec > inter_prec 2337 && inter_unsignedp) 2338 { 2339 tree tem; 2340 tem = fold_build2 (BIT_AND_EXPR, inside_type, 2341 defop0, 2342 double_int_to_tree 2343 (inside_type, double_int_mask (inter_prec))); 2344 if (!useless_type_conversion_p (type, inside_type)) 2345 { 2346 tem = force_gimple_operand_gsi (gsi, tem, true, NULL_TREE, true, 2347 GSI_SAME_STMT); 2348 gimple_assign_set_rhs1 (stmt, tem); 2349 } 2350 else 2351 gimple_assign_set_rhs_from_tree (gsi, tem); 2352 update_stmt (gsi_stmt (*gsi)); 2353 return 1; 2354 } 2355 } 2356 2357 return 0; 2358 } 2359 2360 /* Main entry point for the forward propagation and statement combine 2361 optimizer. */ 2362 2363 static unsigned int 2364 ssa_forward_propagate_and_combine (void) 2365 { 2366 basic_block bb; 2367 unsigned int todoflags = 0; 2368 2369 cfg_changed = false; 2370 2371 FOR_EACH_BB (bb) 2372 { 2373 gimple_stmt_iterator gsi, prev; 2374 bool prev_initialized; 2375 2376 /* Apply forward propagation to all stmts in the basic-block. 2377 Note we update GSI within the loop as necessary. */ 2378 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) 2379 { 2380 gimple stmt = gsi_stmt (gsi); 2381 tree lhs, rhs; 2382 enum tree_code code; 2383 2384 if (!is_gimple_assign (stmt)) 2385 { 2386 gsi_next (&gsi); 2387 continue; 2388 } 2389 2390 lhs = gimple_assign_lhs (stmt); 2391 rhs = gimple_assign_rhs1 (stmt); 2392 code = gimple_assign_rhs_code (stmt); 2393 if (TREE_CODE (lhs) != SSA_NAME 2394 || has_zero_uses (lhs)) 2395 { 2396 gsi_next (&gsi); 2397 continue; 2398 } 2399 2400 /* If this statement sets an SSA_NAME to an address, 2401 try to propagate the address into the uses of the SSA_NAME. */ 2402 if (code == ADDR_EXPR 2403 /* Handle pointer conversions on invariant addresses 2404 as well, as this is valid gimple. */ 2405 || (CONVERT_EXPR_CODE_P (code) 2406 && TREE_CODE (rhs) == ADDR_EXPR 2407 && POINTER_TYPE_P (TREE_TYPE (lhs)))) 2408 { 2409 tree base = get_base_address (TREE_OPERAND (rhs, 0)); 2410 if ((!base 2411 || !DECL_P (base) 2412 || decl_address_invariant_p (base)) 2413 && !stmt_references_abnormal_ssa_name (stmt) 2414 && forward_propagate_addr_expr (lhs, rhs)) 2415 { 2416 release_defs (stmt); 2417 todoflags |= TODO_remove_unused_locals; 2418 gsi_remove (&gsi, true); 2419 } 2420 else 2421 gsi_next (&gsi); 2422 } 2423 else if (code == POINTER_PLUS_EXPR) 2424 { 2425 tree off = gimple_assign_rhs2 (stmt); 2426 if (TREE_CODE (off) == INTEGER_CST 2427 && can_propagate_from (stmt) 2428 && !simple_iv_increment_p (stmt) 2429 /* ??? Better adjust the interface to that function 2430 instead of building new trees here. */ 2431 && forward_propagate_addr_expr 2432 (lhs, 2433 build1_loc (gimple_location (stmt), 2434 ADDR_EXPR, TREE_TYPE (rhs), 2435 fold_build2 (MEM_REF, 2436 TREE_TYPE (TREE_TYPE (rhs)), 2437 rhs, 2438 fold_convert (ptr_type_node, 2439 off))))) 2440 { 2441 release_defs (stmt); 2442 todoflags |= TODO_remove_unused_locals; 2443 gsi_remove (&gsi, true); 2444 } 2445 else if (is_gimple_min_invariant (rhs)) 2446 { 2447 /* Make sure to fold &a[0] + off_1 here. */ 2448 fold_stmt_inplace (&gsi); 2449 update_stmt (stmt); 2450 if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR) 2451 gsi_next (&gsi); 2452 } 2453 else 2454 gsi_next (&gsi); 2455 } 2456 else if (TREE_CODE_CLASS (code) == tcc_comparison) 2457 { 2458 if (forward_propagate_comparison (stmt)) 2459 cfg_changed = true; 2460 gsi_next (&gsi); 2461 } 2462 else 2463 gsi_next (&gsi); 2464 } 2465 2466 /* Combine stmts with the stmts defining their operands. 2467 Note we update GSI within the loop as necessary. */ 2468 prev_initialized = false; 2469 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);) 2470 { 2471 gimple stmt = gsi_stmt (gsi); 2472 bool changed = false; 2473 2474 switch (gimple_code (stmt)) 2475 { 2476 case GIMPLE_ASSIGN: 2477 { 2478 tree rhs1 = gimple_assign_rhs1 (stmt); 2479 enum tree_code code = gimple_assign_rhs_code (stmt); 2480 2481 if ((code == BIT_NOT_EXPR 2482 || code == NEGATE_EXPR) 2483 && TREE_CODE (rhs1) == SSA_NAME) 2484 changed = simplify_not_neg_expr (&gsi); 2485 else if (code == COND_EXPR) 2486 { 2487 /* In this case the entire COND_EXPR is in rhs1. */ 2488 changed |= forward_propagate_into_cond (&gsi); 2489 stmt = gsi_stmt (gsi); 2490 } 2491 else if (TREE_CODE_CLASS (code) == tcc_comparison) 2492 { 2493 int did_something; 2494 did_something = forward_propagate_into_comparison (&gsi); 2495 if (did_something == 2) 2496 cfg_changed = true; 2497 changed = did_something != 0; 2498 } 2499 else if (code == BIT_AND_EXPR 2500 || code == BIT_IOR_EXPR 2501 || code == BIT_XOR_EXPR) 2502 changed = simplify_bitwise_binary (&gsi); 2503 else if (code == PLUS_EXPR 2504 || code == MINUS_EXPR) 2505 changed = associate_plusminus (&gsi); 2506 else if (CONVERT_EXPR_CODE_P (code) 2507 || code == FLOAT_EXPR 2508 || code == FIX_TRUNC_EXPR) 2509 { 2510 int did_something = combine_conversions (&gsi); 2511 if (did_something == 2) 2512 cfg_changed = true; 2513 changed = did_something != 0; 2514 } 2515 break; 2516 } 2517 2518 case GIMPLE_SWITCH: 2519 changed = simplify_gimple_switch (stmt); 2520 break; 2521 2522 case GIMPLE_COND: 2523 { 2524 int did_something; 2525 did_something = forward_propagate_into_gimple_cond (stmt); 2526 if (did_something == 2) 2527 cfg_changed = true; 2528 changed = did_something != 0; 2529 break; 2530 } 2531 2532 case GIMPLE_CALL: 2533 { 2534 tree callee = gimple_call_fndecl (stmt); 2535 if (callee != NULL_TREE 2536 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL) 2537 changed = simplify_builtin_call (&gsi, callee); 2538 break; 2539 } 2540 2541 default:; 2542 } 2543 2544 if (changed) 2545 { 2546 /* If the stmt changed then re-visit it and the statements 2547 inserted before it. */ 2548 if (!prev_initialized) 2549 gsi = gsi_start_bb (bb); 2550 else 2551 { 2552 gsi = prev; 2553 gsi_next (&gsi); 2554 } 2555 } 2556 else 2557 { 2558 prev = gsi; 2559 prev_initialized = true; 2560 gsi_next (&gsi); 2561 } 2562 } 2563 } 2564 2565 if (cfg_changed) 2566 todoflags |= TODO_cleanup_cfg; 2567 2568 return todoflags; 2569 } 2570 2571 2572 static bool 2573 gate_forwprop (void) 2574 { 2575 return flag_tree_forwprop; 2576 } 2577 2578 struct gimple_opt_pass pass_forwprop = 2579 { 2580 { 2581 GIMPLE_PASS, 2582 "forwprop", /* name */ 2583 gate_forwprop, /* gate */ 2584 ssa_forward_propagate_and_combine, /* execute */ 2585 NULL, /* sub */ 2586 NULL, /* next */ 2587 0, /* static_pass_number */ 2588 TV_TREE_FORWPROP, /* tv_id */ 2589 PROP_cfg | PROP_ssa, /* properties_required */ 2590 0, /* properties_provided */ 2591 0, /* properties_destroyed */ 2592 0, /* todo_flags_start */ 2593 TODO_ggc_collect 2594 | TODO_update_ssa 2595 | TODO_verify_ssa /* todo_flags_finish */ 2596 } 2597 }; 2598