1/* Conditional constant propagation pass for the GNU compiler. 2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005 3 Free Software Foundation, Inc. 4 Adapted from original RTL SSA-CCP by Daniel Berlin <dberlin@dberlin.org> 5 Adapted to GIMPLE trees by Diego Novillo <dnovillo@redhat.com> 6 7This file is part of GCC. 8 9GCC is free software; you can redistribute it and/or modify it 10under the terms of the GNU General Public License as published by the 11Free Software Foundation; either version 2, or (at your option) any 12later version. 13 14GCC is distributed in the hope that it will be useful, but WITHOUT 15ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 16FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 17for more details. 18 19You should have received a copy of the GNU General Public License 20along with GCC; see the file COPYING. If not, write to the Free 21Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2202110-1301, USA. */ 23 24/* Conditional constant propagation (CCP) is based on the SSA 25 propagation engine (tree-ssa-propagate.c). Constant assignments of 26 the form VAR = CST are propagated from the assignments into uses of 27 VAR, which in turn may generate new constants. The simulation uses 28 a four level lattice to keep track of constant values associated 29 with SSA names. Given an SSA name V_i, it may take one of the 30 following values: 31 32 UNINITIALIZED -> This is the default starting value. V_i 33 has not been processed yet. 34 35 UNDEFINED -> V_i is a local variable whose definition 36 has not been processed yet. Therefore we 37 don't yet know if its value is a constant 38 or not. 39 40 CONSTANT -> V_i has been found to hold a constant 41 value C. 42 43 VARYING -> V_i cannot take a constant value, or if it 44 does, it is not possible to determine it 45 at compile time. 46 47 The core of SSA-CCP is in ccp_visit_stmt and ccp_visit_phi_node: 48 49 1- In ccp_visit_stmt, we are interested in assignments whose RHS 50 evaluates into a constant and conditional jumps whose predicate 51 evaluates into a boolean true or false. When an assignment of 52 the form V_i = CONST is found, V_i's lattice value is set to 53 CONSTANT and CONST is associated with it. This causes the 54 propagation engine to add all the SSA edges coming out the 55 assignment into the worklists, so that statements that use V_i 56 can be visited. 57 58 If the statement is a conditional with a constant predicate, we 59 mark the outgoing edges as executable or not executable 60 depending on the predicate's value. This is then used when 61 visiting PHI nodes to know when a PHI argument can be ignored. 62 63 64 2- In ccp_visit_phi_node, if all the PHI arguments evaluate to the 65 same constant C, then the LHS of the PHI is set to C. This 66 evaluation is known as the "meet operation". Since one of the 67 goals of this evaluation is to optimistically return constant 68 values as often as possible, it uses two main short cuts: 69 70 - If an argument is flowing in through a non-executable edge, it 71 is ignored. This is useful in cases like this: 72 73 if (PRED) 74 a_9 = 3; 75 else 76 a_10 = 100; 77 a_11 = PHI (a_9, a_10) 78 79 If PRED is known to always evaluate to false, then we can 80 assume that a_11 will always take its value from a_10, meaning 81 that instead of consider it VARYING (a_9 and a_10 have 82 different values), we can consider it CONSTANT 100. 83 84 - If an argument has an UNDEFINED value, then it does not affect 85 the outcome of the meet operation. If a variable V_i has an 86 UNDEFINED value, it means that either its defining statement 87 hasn't been visited yet or V_i has no defining statement, in 88 which case the original symbol 'V' is being used 89 uninitialized. Since 'V' is a local variable, the compiler 90 may assume any initial value for it. 91 92 93 After propagation, every variable V_i that ends up with a lattice 94 value of CONSTANT will have the associated constant value in the 95 array CONST_VAL[i].VALUE. That is fed into substitute_and_fold for 96 final substitution and folding. 97 98 99 Constant propagation in stores and loads (STORE-CCP) 100 ---------------------------------------------------- 101 102 While CCP has all the logic to propagate constants in GIMPLE 103 registers, it is missing the ability to associate constants with 104 stores and loads (i.e., pointer dereferences, structures and 105 global/aliased variables). We don't keep loads and stores in 106 SSA, but we do build a factored use-def web for them (in the 107 virtual operands). 108 109 For instance, consider the following code fragment: 110 111 struct A a; 112 const int B = 42; 113 114 void foo (int i) 115 { 116 if (i > 10) 117 a.a = 42; 118 else 119 { 120 a.b = 21; 121 a.a = a.b + 21; 122 } 123 124 if (a.a != B) 125 never_executed (); 126 } 127 128 We should be able to deduce that the predicate 'a.a != B' is always 129 false. To achieve this, we associate constant values to the SSA 130 names in the V_MAY_DEF and V_MUST_DEF operands for each store. 131 Additionally, since we also glob partial loads/stores with the base 132 symbol, we also keep track of the memory reference where the 133 constant value was stored (in the MEM_REF field of PROP_VALUE_T). 134 For instance, 135 136 # a_5 = V_MAY_DEF <a_4> 137 a.a = 2; 138 139 # VUSE <a_5> 140 x_3 = a.b; 141 142 In the example above, CCP will associate value '2' with 'a_5', but 143 it would be wrong to replace the load from 'a.b' with '2', because 144 '2' had been stored into a.a. 145 146 To support STORE-CCP, it is necessary to add a new value to the 147 constant propagation lattice. When evaluating a load for a memory 148 reference we can no longer assume a value of UNDEFINED if we 149 haven't seen a preceding store to the same memory location. 150 Consider, for instance global variables: 151 152 int A; 153 154 foo (int i) 155 { 156 if (i_3 > 10) 157 A_4 = 3; 158 # A_5 = PHI (A_4, A_2); 159 160 # VUSE <A_5> 161 A.0_6 = A; 162 163 return A.0_6; 164 } 165 166 The value of A_2 cannot be assumed to be UNDEFINED, as it may have 167 been defined outside of foo. If we were to assume it UNDEFINED, we 168 would erroneously optimize the above into 'return 3;'. Therefore, 169 when doing STORE-CCP, we introduce a fifth lattice value 170 (UNKNOWN_VAL), which overrides any other value when computing the 171 meet operation in PHI nodes. 172 173 Though STORE-CCP is not too expensive, it does have to do more work 174 than regular CCP, so it is only enabled at -O2. Both regular CCP 175 and STORE-CCP use the exact same algorithm. The only distinction 176 is that when doing STORE-CCP, the boolean variable DO_STORE_CCP is 177 set to true. This affects the evaluation of statements and PHI 178 nodes. 179 180 References: 181 182 Constant propagation with conditional branches, 183 Wegman and Zadeck, ACM TOPLAS 13(2):181-210. 184 185 Building an Optimizing Compiler, 186 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9. 187 188 Advanced Compiler Design and Implementation, 189 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */ 190 191#include "config.h" 192#include "system.h" 193#include "coretypes.h" 194#include "tm.h" 195#include "tree.h" 196#include "flags.h" 197#include "rtl.h" 198#include "tm_p.h" 199#include "ggc.h" 200#include "basic-block.h" 201#include "output.h" 202#include "expr.h" 203#include "function.h" 204#include "diagnostic.h" 205#include "timevar.h" 206#include "tree-dump.h" 207#include "tree-flow.h" 208#include "tree-pass.h" 209#include "tree-ssa-propagate.h" 210#include "langhooks.h" 211#include "target.h" 212 213 214/* Possible lattice values. */ 215typedef enum 216{ 217 UNINITIALIZED = 0, 218 UNDEFINED, 219 UNKNOWN_VAL, 220 CONSTANT, 221 VARYING 222} ccp_lattice_t; 223 224/* Array of propagated constant values. After propagation, 225 CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I). If 226 the constant is held in an SSA name representing a memory store 227 (i.e., a V_MAY_DEF or V_MUST_DEF), CONST_VAL[I].MEM_REF will 228 contain the actual memory reference used to store (i.e., the LHS of 229 the assignment doing the store). */ 230static prop_value_t *const_val; 231 232/* True if we are also propagating constants in stores and loads. */ 233static bool do_store_ccp; 234 235/* Dump constant propagation value VAL to file OUTF prefixed by PREFIX. */ 236 237static void 238dump_lattice_value (FILE *outf, const char *prefix, prop_value_t val) 239{ 240 switch (val.lattice_val) 241 { 242 case UNINITIALIZED: 243 fprintf (outf, "%sUNINITIALIZED", prefix); 244 break; 245 case UNDEFINED: 246 fprintf (outf, "%sUNDEFINED", prefix); 247 break; 248 case VARYING: 249 fprintf (outf, "%sVARYING", prefix); 250 break; 251 case UNKNOWN_VAL: 252 fprintf (outf, "%sUNKNOWN_VAL", prefix); 253 break; 254 case CONSTANT: 255 fprintf (outf, "%sCONSTANT ", prefix); 256 print_generic_expr (outf, val.value, dump_flags); 257 break; 258 default: 259 gcc_unreachable (); 260 } 261} 262 263 264/* Print lattice value VAL to stderr. */ 265 266void debug_lattice_value (prop_value_t val); 267 268void 269debug_lattice_value (prop_value_t val) 270{ 271 dump_lattice_value (stderr, "", val); 272 fprintf (stderr, "\n"); 273} 274 275 276/* The regular is_gimple_min_invariant does a shallow test of the object. 277 It assumes that full gimplification has happened, or will happen on the 278 object. For a value coming from DECL_INITIAL, this is not true, so we 279 have to be more strict outselves. */ 280 281static bool 282ccp_decl_initial_min_invariant (tree t) 283{ 284 if (!is_gimple_min_invariant (t)) 285 return false; 286 if (TREE_CODE (t) == ADDR_EXPR) 287 { 288 /* Inline and unroll is_gimple_addressable. */ 289 while (1) 290 { 291 t = TREE_OPERAND (t, 0); 292 if (is_gimple_id (t)) 293 return true; 294 if (!handled_component_p (t)) 295 return false; 296 } 297 } 298 return true; 299} 300 301 302/* Compute a default value for variable VAR and store it in the 303 CONST_VAL array. The following rules are used to get default 304 values: 305 306 1- Global and static variables that are declared constant are 307 considered CONSTANT. 308 309 2- Any other value is considered UNDEFINED. This is useful when 310 considering PHI nodes. PHI arguments that are undefined do not 311 change the constant value of the PHI node, which allows for more 312 constants to be propagated. 313 314 3- If SSA_NAME_VALUE is set and it is a constant, its value is 315 used. 316 317 4- Variables defined by statements other than assignments and PHI 318 nodes are considered VARYING. 319 320 5- Variables that are not GIMPLE registers are considered 321 UNKNOWN_VAL, which is really a stronger version of UNDEFINED. 322 It's used to avoid the short circuit evaluation implied by 323 UNDEFINED in ccp_lattice_meet. */ 324 325static prop_value_t 326get_default_value (tree var) 327{ 328 tree sym = SSA_NAME_VAR (var); 329 prop_value_t val = { UNINITIALIZED, NULL_TREE, NULL_TREE }; 330 331 if (!do_store_ccp && !is_gimple_reg (var)) 332 { 333 /* Short circuit for regular CCP. We are not interested in any 334 non-register when DO_STORE_CCP is false. */ 335 val.lattice_val = VARYING; 336 } 337 else if (SSA_NAME_VALUE (var) 338 && is_gimple_min_invariant (SSA_NAME_VALUE (var))) 339 { 340 val.lattice_val = CONSTANT; 341 val.value = SSA_NAME_VALUE (var); 342 } 343 else if (TREE_STATIC (sym) 344 && TREE_READONLY (sym) 345 && DECL_INITIAL (sym) 346 && ccp_decl_initial_min_invariant (DECL_INITIAL (sym))) 347 { 348 /* Globals and static variables declared 'const' take their 349 initial value. */ 350 val.lattice_val = CONSTANT; 351 val.value = DECL_INITIAL (sym); 352 val.mem_ref = sym; 353 } 354 else 355 { 356 tree stmt = SSA_NAME_DEF_STMT (var); 357 358 if (IS_EMPTY_STMT (stmt)) 359 { 360 /* Variables defined by an empty statement are those used 361 before being initialized. If VAR is a local variable, we 362 can assume initially that it is UNDEFINED. If we are 363 doing STORE-CCP, function arguments and non-register 364 variables are initially UNKNOWN_VAL, because we cannot 365 discard the value incoming from outside of this function 366 (see ccp_lattice_meet for details). */ 367 if (is_gimple_reg (sym) && TREE_CODE (sym) != PARM_DECL) 368 val.lattice_val = UNDEFINED; 369 else if (do_store_ccp) 370 val.lattice_val = UNKNOWN_VAL; 371 else 372 val.lattice_val = VARYING; 373 } 374 else if (TREE_CODE (stmt) == MODIFY_EXPR 375 || TREE_CODE (stmt) == PHI_NODE) 376 { 377 /* Any other variable defined by an assignment or a PHI node 378 is considered UNDEFINED (or UNKNOWN_VAL if VAR is not a 379 GIMPLE register). */ 380 val.lattice_val = is_gimple_reg (sym) ? UNDEFINED : UNKNOWN_VAL; 381 } 382 else 383 { 384 /* Otherwise, VAR will never take on a constant value. */ 385 val.lattice_val = VARYING; 386 } 387 } 388 389 return val; 390} 391 392 393/* Get the constant value associated with variable VAR. If 394 MAY_USE_DEFAULT_P is true, call get_default_value on variables that 395 have the lattice value UNINITIALIZED. */ 396 397static prop_value_t * 398get_value (tree var, bool may_use_default_p) 399{ 400 prop_value_t *val = &const_val[SSA_NAME_VERSION (var)]; 401 if (may_use_default_p && val->lattice_val == UNINITIALIZED) 402 *val = get_default_value (var); 403 404 return val; 405} 406 407 408/* Set the value for variable VAR to NEW_VAL. Return true if the new 409 value is different from VAR's previous value. */ 410 411static bool 412set_lattice_value (tree var, prop_value_t new_val) 413{ 414 prop_value_t *old_val = get_value (var, false); 415 416 /* Lattice transitions must always be monotonically increasing in 417 value. We allow two exceptions: 418 419 1- If *OLD_VAL and NEW_VAL are the same, return false to 420 inform the caller that this was a non-transition. 421 422 2- If we are doing store-ccp (i.e., DOING_STORE_CCP is true), 423 allow CONSTANT->UNKNOWN_VAL. The UNKNOWN_VAL state is a 424 special type of UNDEFINED state which prevents the short 425 circuit evaluation of PHI arguments (see ccp_visit_phi_node 426 and ccp_lattice_meet). */ 427 gcc_assert (old_val->lattice_val <= new_val.lattice_val 428 || (old_val->lattice_val == new_val.lattice_val 429 && old_val->value == new_val.value 430 && old_val->mem_ref == new_val.mem_ref) 431 || (do_store_ccp 432 && old_val->lattice_val == CONSTANT 433 && new_val.lattice_val == UNKNOWN_VAL)); 434 435 if (old_val->lattice_val != new_val.lattice_val) 436 { 437 if (dump_file && (dump_flags & TDF_DETAILS)) 438 { 439 dump_lattice_value (dump_file, "Lattice value changed to ", new_val); 440 fprintf (dump_file, ". %sdding SSA edges to worklist.\n", 441 new_val.lattice_val != UNDEFINED ? "A" : "Not a"); 442 } 443 444 *old_val = new_val; 445 446 /* Transitions UNINITIALIZED -> UNDEFINED are never interesting 447 for propagation purposes. In these cases return false to 448 avoid doing useless work. */ 449 return (new_val.lattice_val != UNDEFINED); 450 } 451 452 return false; 453} 454 455 456/* Return the likely CCP lattice value for STMT. 457 458 If STMT has no operands, then return CONSTANT. 459 460 Else if any operands of STMT are undefined, then return UNDEFINED. 461 462 Else if any operands of STMT are constants, then return CONSTANT. 463 464 Else return VARYING. */ 465 466static ccp_lattice_t 467likely_value (tree stmt) 468{ 469 bool found_constant; 470 stmt_ann_t ann; 471 tree use; 472 ssa_op_iter iter; 473 474 ann = stmt_ann (stmt); 475 476 /* If the statement has volatile operands, it won't fold to a 477 constant value. */ 478 if (ann->has_volatile_ops) 479 return VARYING; 480 481 /* If we are not doing store-ccp, statements with loads 482 and/or stores will never fold into a constant. */ 483 if (!do_store_ccp 484 && (ann->makes_aliased_stores 485 || ann->makes_aliased_loads 486 || !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))) 487 return VARYING; 488 489 490 /* A CALL_EXPR is assumed to be varying. NOTE: This may be overly 491 conservative, in the presence of const and pure calls. */ 492 if (get_call_expr_in (stmt) != NULL_TREE) 493 return VARYING; 494 495 /* Anything other than assignments and conditional jumps are not 496 interesting for CCP. */ 497 if (TREE_CODE (stmt) != MODIFY_EXPR 498 && TREE_CODE (stmt) != COND_EXPR 499 && TREE_CODE (stmt) != SWITCH_EXPR) 500 return VARYING; 501 502 if (is_gimple_min_invariant (get_rhs (stmt))) 503 return CONSTANT; 504 505 found_constant = false; 506 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE|SSA_OP_VUSE) 507 { 508 prop_value_t *val = get_value (use, true); 509 510 if (val->lattice_val == VARYING) 511 return VARYING; 512 513 if (val->lattice_val == UNKNOWN_VAL) 514 { 515 /* UNKNOWN_VAL is invalid when not doing STORE-CCP. */ 516 gcc_assert (do_store_ccp); 517 return UNKNOWN_VAL; 518 } 519 520 if (val->lattice_val == CONSTANT) 521 found_constant = true; 522 } 523 524 if (found_constant 525 || ZERO_SSA_OPERANDS (stmt, SSA_OP_USE) 526 || ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE)) 527 return CONSTANT; 528 529 return UNDEFINED; 530} 531 532 533/* Initialize local data structures for CCP. */ 534 535static void 536ccp_initialize (void) 537{ 538 basic_block bb; 539 540 const_val = xmalloc (num_ssa_names * sizeof (*const_val)); 541 memset (const_val, 0, num_ssa_names * sizeof (*const_val)); 542 543 /* Initialize simulation flags for PHI nodes and statements. */ 544 FOR_EACH_BB (bb) 545 { 546 block_stmt_iterator i; 547 548 for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i)) 549 { 550 bool is_varying = false; 551 tree stmt = bsi_stmt (i); 552 553 if (likely_value (stmt) == VARYING) 554 555 { 556 tree def; 557 ssa_op_iter iter; 558 559 /* If the statement will not produce a constant, mark 560 all its outputs VARYING. */ 561 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 562 get_value (def, false)->lattice_val = VARYING; 563 564 /* Never mark conditional jumps with DONT_SIMULATE_AGAIN, 565 otherwise the propagator will never add the outgoing 566 control edges. */ 567 if (TREE_CODE (stmt) != COND_EXPR 568 && TREE_CODE (stmt) != SWITCH_EXPR) 569 is_varying = true; 570 } 571 572 DONT_SIMULATE_AGAIN (stmt) = is_varying; 573 } 574 } 575 576 /* Now process PHI nodes. */ 577 FOR_EACH_BB (bb) 578 { 579 tree phi; 580 581 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 582 { 583 int i; 584 tree arg; 585 prop_value_t *val = get_value (PHI_RESULT (phi), false); 586 587 for (i = 0; i < PHI_NUM_ARGS (phi); i++) 588 { 589 arg = PHI_ARG_DEF (phi, i); 590 591 if (TREE_CODE (arg) == SSA_NAME 592 && get_value (arg, false)->lattice_val == VARYING) 593 { 594 val->lattice_val = VARYING; 595 break; 596 } 597 } 598 599 DONT_SIMULATE_AGAIN (phi) = (val->lattice_val == VARYING); 600 } 601 } 602} 603 604 605/* Do final substitution of propagated values, cleanup the flowgraph and 606 free allocated storage. */ 607 608static void 609ccp_finalize (void) 610{ 611 /* Perform substitutions based on the known constant values. */ 612 substitute_and_fold (const_val, false); 613 614 free (const_val); 615} 616 617 618/* Compute the meet operator between *VAL1 and *VAL2. Store the result 619 in VAL1. 620 621 any M UNDEFINED = any 622 any M UNKNOWN_VAL = UNKNOWN_VAL 623 any M VARYING = VARYING 624 Ci M Cj = Ci if (i == j) 625 Ci M Cj = VARYING if (i != j) 626 627 Lattice values UNKNOWN_VAL and UNDEFINED are similar but have 628 different semantics at PHI nodes. Both values imply that we don't 629 know whether the variable is constant or not. However, UNKNOWN_VAL 630 values override all others. For instance, suppose that A is a 631 global variable: 632 633 +------+ 634 | | 635 | / \ 636 | / \ 637 | | A_1 = 4 638 | \ / 639 | \ / 640 | A_3 = PHI (A_2, A_1) 641 | ... = A_3 642 | | 643 +----+ 644 645 If the edge into A_2 is not executable, the first visit to A_3 will 646 yield the constant 4. But the second visit to A_3 will be with A_2 647 in state UNKNOWN_VAL. We can no longer conclude that A_3 is 4 648 because A_2 may have been set in another function. If we had used 649 the lattice value UNDEFINED, we would have had wrongly concluded 650 that A_3 is 4. */ 651 652 653static void 654ccp_lattice_meet (prop_value_t *val1, prop_value_t *val2) 655{ 656 if (val1->lattice_val == UNDEFINED) 657 { 658 /* UNDEFINED M any = any */ 659 *val1 = *val2; 660 } 661 else if (val2->lattice_val == UNDEFINED) 662 { 663 /* any M UNDEFINED = any 664 Nothing to do. VAL1 already contains the value we want. */ 665 ; 666 } 667 else if (val1->lattice_val == UNKNOWN_VAL 668 || val2->lattice_val == UNKNOWN_VAL) 669 { 670 /* UNKNOWN_VAL values are invalid if we are not doing STORE-CCP. */ 671 gcc_assert (do_store_ccp); 672 673 /* any M UNKNOWN_VAL = UNKNOWN_VAL. */ 674 val1->lattice_val = UNKNOWN_VAL; 675 val1->value = NULL_TREE; 676 val1->mem_ref = NULL_TREE; 677 } 678 else if (val1->lattice_val == VARYING 679 || val2->lattice_val == VARYING) 680 { 681 /* any M VARYING = VARYING. */ 682 val1->lattice_val = VARYING; 683 val1->value = NULL_TREE; 684 val1->mem_ref = NULL_TREE; 685 } 686 else if (val1->lattice_val == CONSTANT 687 && val2->lattice_val == CONSTANT 688 && simple_cst_equal (val1->value, val2->value) == 1 689 && (!do_store_ccp 690 || (val1->mem_ref && val2->mem_ref 691 && operand_equal_p (val1->mem_ref, val2->mem_ref, 0)))) 692 { 693 /* Ci M Cj = Ci if (i == j) 694 Ci M Cj = VARYING if (i != j) 695 696 If these two values come from memory stores, make sure that 697 they come from the same memory reference. */ 698 val1->lattice_val = CONSTANT; 699 val1->value = val1->value; 700 val1->mem_ref = val1->mem_ref; 701 } 702 else 703 { 704 /* Any other combination is VARYING. */ 705 val1->lattice_val = VARYING; 706 val1->value = NULL_TREE; 707 val1->mem_ref = NULL_TREE; 708 } 709} 710 711 712/* Loop through the PHI_NODE's parameters for BLOCK and compare their 713 lattice values to determine PHI_NODE's lattice value. The value of a 714 PHI node is determined calling ccp_lattice_meet with all the arguments 715 of the PHI node that are incoming via executable edges. */ 716 717static enum ssa_prop_result 718ccp_visit_phi_node (tree phi) 719{ 720 int i; 721 prop_value_t *old_val, new_val; 722 723 if (dump_file && (dump_flags & TDF_DETAILS)) 724 { 725 fprintf (dump_file, "\nVisiting PHI node: "); 726 print_generic_expr (dump_file, phi, dump_flags); 727 } 728 729 old_val = get_value (PHI_RESULT (phi), false); 730 switch (old_val->lattice_val) 731 { 732 case VARYING: 733 return SSA_PROP_VARYING; 734 735 case CONSTANT: 736 new_val = *old_val; 737 break; 738 739 case UNKNOWN_VAL: 740 /* To avoid the default value of UNKNOWN_VAL overriding 741 that of its possible constant arguments, temporarily 742 set the PHI node's default lattice value to be 743 UNDEFINED. If the PHI node's old value was UNKNOWN_VAL and 744 the new value is UNDEFINED, then we prevent the invalid 745 transition by not calling set_lattice_value. */ 746 gcc_assert (do_store_ccp); 747 748 /* FALLTHRU */ 749 750 case UNDEFINED: 751 case UNINITIALIZED: 752 new_val.lattice_val = UNDEFINED; 753 new_val.value = NULL_TREE; 754 new_val.mem_ref = NULL_TREE; 755 break; 756 757 default: 758 gcc_unreachable (); 759 } 760 761 for (i = 0; i < PHI_NUM_ARGS (phi); i++) 762 { 763 /* Compute the meet operator over all the PHI arguments flowing 764 through executable edges. */ 765 edge e = PHI_ARG_EDGE (phi, i); 766 767 if (dump_file && (dump_flags & TDF_DETAILS)) 768 { 769 fprintf (dump_file, 770 "\n Argument #%d (%d -> %d %sexecutable)\n", 771 i, e->src->index, e->dest->index, 772 (e->flags & EDGE_EXECUTABLE) ? "" : "not "); 773 } 774 775 /* If the incoming edge is executable, Compute the meet operator for 776 the existing value of the PHI node and the current PHI argument. */ 777 if (e->flags & EDGE_EXECUTABLE) 778 { 779 tree arg = PHI_ARG_DEF (phi, i); 780 prop_value_t arg_val; 781 782 if (is_gimple_min_invariant (arg)) 783 { 784 arg_val.lattice_val = CONSTANT; 785 arg_val.value = arg; 786 arg_val.mem_ref = NULL_TREE; 787 } 788 else 789 arg_val = *(get_value (arg, true)); 790 791 ccp_lattice_meet (&new_val, &arg_val); 792 793 if (dump_file && (dump_flags & TDF_DETAILS)) 794 { 795 fprintf (dump_file, "\t"); 796 print_generic_expr (dump_file, arg, dump_flags); 797 dump_lattice_value (dump_file, "\tValue: ", arg_val); 798 fprintf (dump_file, "\n"); 799 } 800 801 if (new_val.lattice_val == VARYING) 802 break; 803 } 804 } 805 806 if (dump_file && (dump_flags & TDF_DETAILS)) 807 { 808 dump_lattice_value (dump_file, "\n PHI node value: ", new_val); 809 fprintf (dump_file, "\n\n"); 810 } 811 812 /* Check for an invalid change from UNKNOWN_VAL to UNDEFINED. */ 813 if (do_store_ccp 814 && old_val->lattice_val == UNKNOWN_VAL 815 && new_val.lattice_val == UNDEFINED) 816 return SSA_PROP_NOT_INTERESTING; 817 818 /* Otherwise, make the transition to the new value. */ 819 if (set_lattice_value (PHI_RESULT (phi), new_val)) 820 { 821 if (new_val.lattice_val == VARYING) 822 return SSA_PROP_VARYING; 823 else 824 return SSA_PROP_INTERESTING; 825 } 826 else 827 return SSA_PROP_NOT_INTERESTING; 828} 829 830 831/* CCP specific front-end to the non-destructive constant folding 832 routines. 833 834 Attempt to simplify the RHS of STMT knowing that one or more 835 operands are constants. 836 837 If simplification is possible, return the simplified RHS, 838 otherwise return the original RHS. */ 839 840static tree 841ccp_fold (tree stmt) 842{ 843 tree rhs = get_rhs (stmt); 844 enum tree_code code = TREE_CODE (rhs); 845 enum tree_code_class kind = TREE_CODE_CLASS (code); 846 tree retval = NULL_TREE; 847 848 if (TREE_CODE (rhs) == SSA_NAME) 849 { 850 /* If the RHS is an SSA_NAME, return its known constant value, 851 if any. */ 852 return get_value (rhs, true)->value; 853 } 854 else if (do_store_ccp && stmt_makes_single_load (stmt)) 855 { 856 /* If the RHS is a memory load, see if the VUSEs associated with 857 it are a valid constant for that memory load. */ 858 prop_value_t *val = get_value_loaded_by (stmt, const_val); 859 if (val && val->mem_ref 860 && operand_equal_p (val->mem_ref, rhs, 0)) 861 return val->value; 862 else 863 return NULL_TREE; 864 } 865 866 /* Unary operators. Note that we know the single operand must 867 be a constant. So this should almost always return a 868 simplified RHS. */ 869 if (kind == tcc_unary) 870 { 871 /* Handle unary operators which can appear in GIMPLE form. */ 872 tree op0 = TREE_OPERAND (rhs, 0); 873 874 /* Simplify the operand down to a constant. */ 875 if (TREE_CODE (op0) == SSA_NAME) 876 { 877 prop_value_t *val = get_value (op0, true); 878 if (val->lattice_val == CONSTANT) 879 op0 = get_value (op0, true)->value; 880 } 881 882 if ((code == NOP_EXPR || code == CONVERT_EXPR) 883 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (rhs), 884 TREE_TYPE (op0))) 885 return op0; 886 return fold_unary (code, TREE_TYPE (rhs), op0); 887 } 888 889 /* Binary and comparison operators. We know one or both of the 890 operands are constants. */ 891 else if (kind == tcc_binary 892 || kind == tcc_comparison 893 || code == TRUTH_AND_EXPR 894 || code == TRUTH_OR_EXPR 895 || code == TRUTH_XOR_EXPR) 896 { 897 /* Handle binary and comparison operators that can appear in 898 GIMPLE form. */ 899 tree op0 = TREE_OPERAND (rhs, 0); 900 tree op1 = TREE_OPERAND (rhs, 1); 901 902 /* Simplify the operands down to constants when appropriate. */ 903 if (TREE_CODE (op0) == SSA_NAME) 904 { 905 prop_value_t *val = get_value (op0, true); 906 if (val->lattice_val == CONSTANT) 907 op0 = val->value; 908 } 909 910 if (TREE_CODE (op1) == SSA_NAME) 911 { 912 prop_value_t *val = get_value (op1, true); 913 if (val->lattice_val == CONSTANT) 914 op1 = val->value; 915 } 916 917 return fold_binary (code, TREE_TYPE (rhs), op0, op1); 918 } 919 920 /* We may be able to fold away calls to builtin functions if their 921 arguments are constants. */ 922 else if (code == CALL_EXPR 923 && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR 924 && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)) 925 == FUNCTION_DECL) 926 && DECL_BUILT_IN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))) 927 { 928 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_USE)) 929 { 930 tree *orig, var; 931 tree fndecl, arglist; 932 size_t i = 0; 933 ssa_op_iter iter; 934 use_operand_p var_p; 935 936 /* Preserve the original values of every operand. */ 937 orig = xmalloc (sizeof (tree) * NUM_SSA_OPERANDS (stmt, SSA_OP_USE)); 938 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) 939 orig[i++] = var; 940 941 /* Substitute operands with their values and try to fold. */ 942 replace_uses_in (stmt, NULL, const_val); 943 fndecl = get_callee_fndecl (rhs); 944 arglist = TREE_OPERAND (rhs, 1); 945 retval = fold_builtin (fndecl, arglist, false); 946 947 /* Restore operands to their original form. */ 948 i = 0; 949 FOR_EACH_SSA_USE_OPERAND (var_p, stmt, iter, SSA_OP_USE) 950 SET_USE (var_p, orig[i++]); 951 free (orig); 952 } 953 } 954 else 955 return rhs; 956 957 /* If we got a simplified form, see if we need to convert its type. */ 958 if (retval) 959 return fold_convert (TREE_TYPE (rhs), retval); 960 961 /* No simplification was possible. */ 962 return rhs; 963} 964 965 966/* Return the tree representing the element referenced by T if T is an 967 ARRAY_REF or COMPONENT_REF into constant aggregates. Return 968 NULL_TREE otherwise. */ 969 970static tree 971fold_const_aggregate_ref (tree t) 972{ 973 prop_value_t *value; 974 tree base, ctor, idx, field; 975 unsigned HOST_WIDE_INT cnt; 976 tree cfield, cval; 977 978 switch (TREE_CODE (t)) 979 { 980 case ARRAY_REF: 981 /* Get a CONSTRUCTOR. If BASE is a VAR_DECL, get its 982 DECL_INITIAL. If BASE is a nested reference into another 983 ARRAY_REF or COMPONENT_REF, make a recursive call to resolve 984 the inner reference. */ 985 base = TREE_OPERAND (t, 0); 986 switch (TREE_CODE (base)) 987 { 988 case VAR_DECL: 989 if (!TREE_READONLY (base) 990 || TREE_CODE (TREE_TYPE (base)) != ARRAY_TYPE 991 || !targetm.binds_local_p (base)) 992 return NULL_TREE; 993 994 ctor = DECL_INITIAL (base); 995 break; 996 997 case ARRAY_REF: 998 case COMPONENT_REF: 999 ctor = fold_const_aggregate_ref (base); 1000 break; 1001 1002 default: 1003 return NULL_TREE; 1004 } 1005 1006 if (ctor == NULL_TREE 1007 || TREE_CODE (ctor) != CONSTRUCTOR 1008 || !TREE_STATIC (ctor)) 1009 return NULL_TREE; 1010 1011 /* Get the index. If we have an SSA_NAME, try to resolve it 1012 with the current lattice value for the SSA_NAME. */ 1013 idx = TREE_OPERAND (t, 1); 1014 switch (TREE_CODE (idx)) 1015 { 1016 case SSA_NAME: 1017 if ((value = get_value (idx, true)) 1018 && value->lattice_val == CONSTANT 1019 && TREE_CODE (value->value) == INTEGER_CST) 1020 idx = value->value; 1021 else 1022 return NULL_TREE; 1023 break; 1024 1025 case INTEGER_CST: 1026 break; 1027 1028 default: 1029 return NULL_TREE; 1030 } 1031 1032 /* Whoo-hoo! I'll fold ya baby. Yeah! */ 1033 FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval) 1034 if (tree_int_cst_equal (cfield, idx)) 1035 return cval; 1036 break; 1037 1038 case COMPONENT_REF: 1039 /* Get a CONSTRUCTOR. If BASE is a VAR_DECL, get its 1040 DECL_INITIAL. If BASE is a nested reference into another 1041 ARRAY_REF or COMPONENT_REF, make a recursive call to resolve 1042 the inner reference. */ 1043 base = TREE_OPERAND (t, 0); 1044 switch (TREE_CODE (base)) 1045 { 1046 case VAR_DECL: 1047 if (!TREE_READONLY (base) 1048 || TREE_CODE (TREE_TYPE (base)) != RECORD_TYPE 1049 || !targetm.binds_local_p (base)) 1050 return NULL_TREE; 1051 1052 ctor = DECL_INITIAL (base); 1053 break; 1054 1055 case ARRAY_REF: 1056 case COMPONENT_REF: 1057 ctor = fold_const_aggregate_ref (base); 1058 break; 1059 1060 default: 1061 return NULL_TREE; 1062 } 1063 1064 if (ctor == NULL_TREE 1065 || TREE_CODE (ctor) != CONSTRUCTOR 1066 || !TREE_STATIC (ctor)) 1067 return NULL_TREE; 1068 1069 field = TREE_OPERAND (t, 1); 1070 1071 FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval) 1072 if (cfield == field 1073 /* FIXME: Handle bit-fields. */ 1074 && ! DECL_BIT_FIELD (cfield)) 1075 return cval; 1076 break; 1077 1078 case REALPART_EXPR: 1079 case IMAGPART_EXPR: 1080 { 1081 tree c = fold_const_aggregate_ref (TREE_OPERAND (t, 0)); 1082 if (c && TREE_CODE (c) == COMPLEX_CST) 1083 return fold_build1 (TREE_CODE (t), TREE_TYPE (t), c); 1084 break; 1085 } 1086 1087 default: 1088 break; 1089 } 1090 1091 return NULL_TREE; 1092} 1093 1094/* Evaluate statement STMT. */ 1095 1096static prop_value_t 1097evaluate_stmt (tree stmt) 1098{ 1099 prop_value_t val; 1100 tree simplified; 1101 ccp_lattice_t likelyvalue = likely_value (stmt); 1102 1103 val.mem_ref = NULL_TREE; 1104 1105 /* If the statement is likely to have a CONSTANT result, then try 1106 to fold the statement to determine the constant value. */ 1107 if (likelyvalue == CONSTANT) 1108 simplified = ccp_fold (stmt); 1109 /* If the statement is likely to have a VARYING result, then do not 1110 bother folding the statement. */ 1111 else if (likelyvalue == VARYING) 1112 simplified = get_rhs (stmt); 1113 /* If the statement is an ARRAY_REF or COMPONENT_REF into constant 1114 aggregates, extract the referenced constant. Otherwise the 1115 statement is likely to have an UNDEFINED value, and there will be 1116 nothing to do. Note that fold_const_aggregate_ref returns 1117 NULL_TREE if the first case does not match. */ 1118 else 1119 simplified = fold_const_aggregate_ref (get_rhs (stmt)); 1120 1121 if (simplified && is_gimple_min_invariant (simplified)) 1122 { 1123 /* The statement produced a constant value. */ 1124 val.lattice_val = CONSTANT; 1125 val.value = simplified; 1126 } 1127 else 1128 { 1129 /* The statement produced a nonconstant value. If the statement 1130 had UNDEFINED operands, then the result of the statement 1131 should be UNDEFINED. Otherwise, the statement is VARYING. */ 1132 if (likelyvalue == UNDEFINED || likelyvalue == UNKNOWN_VAL) 1133 val.lattice_val = likelyvalue; 1134 else 1135 val.lattice_val = VARYING; 1136 1137 val.value = NULL_TREE; 1138 } 1139 1140 return val; 1141} 1142 1143 1144/* Visit the assignment statement STMT. Set the value of its LHS to the 1145 value computed by the RHS and store LHS in *OUTPUT_P. If STMT 1146 creates virtual definitions, set the value of each new name to that 1147 of the RHS (if we can derive a constant out of the RHS). */ 1148 1149static enum ssa_prop_result 1150visit_assignment (tree stmt, tree *output_p) 1151{ 1152 prop_value_t val; 1153 tree lhs, rhs; 1154 enum ssa_prop_result retval; 1155 1156 lhs = TREE_OPERAND (stmt, 0); 1157 rhs = TREE_OPERAND (stmt, 1); 1158 1159 if (TREE_CODE (rhs) == SSA_NAME) 1160 { 1161 /* For a simple copy operation, we copy the lattice values. */ 1162 prop_value_t *nval = get_value (rhs, true); 1163 val = *nval; 1164 } 1165 else if (do_store_ccp && stmt_makes_single_load (stmt)) 1166 { 1167 /* Same as above, but the RHS is not a gimple register and yet 1168 has a known VUSE. If STMT is loading from the same memory 1169 location that created the SSA_NAMEs for the virtual operands, 1170 we can propagate the value on the RHS. */ 1171 prop_value_t *nval = get_value_loaded_by (stmt, const_val); 1172 1173 if (nval && nval->mem_ref 1174 && operand_equal_p (nval->mem_ref, rhs, 0)) 1175 val = *nval; 1176 else 1177 val = evaluate_stmt (stmt); 1178 } 1179 else 1180 /* Evaluate the statement. */ 1181 val = evaluate_stmt (stmt); 1182 1183 /* If the original LHS was a VIEW_CONVERT_EXPR, modify the constant 1184 value to be a VIEW_CONVERT_EXPR of the old constant value. 1185 1186 ??? Also, if this was a definition of a bitfield, we need to widen 1187 the constant value into the type of the destination variable. This 1188 should not be necessary if GCC represented bitfields properly. */ 1189 { 1190 tree orig_lhs = TREE_OPERAND (stmt, 0); 1191 1192 if (TREE_CODE (orig_lhs) == VIEW_CONVERT_EXPR 1193 && val.lattice_val == CONSTANT) 1194 { 1195 tree w = fold_build1 (VIEW_CONVERT_EXPR, 1196 TREE_TYPE (TREE_OPERAND (orig_lhs, 0)), 1197 val.value); 1198 1199 orig_lhs = TREE_OPERAND (orig_lhs, 0); 1200 if (w && is_gimple_min_invariant (w)) 1201 val.value = w; 1202 else 1203 { 1204 val.lattice_val = VARYING; 1205 val.value = NULL; 1206 } 1207 } 1208 1209 if (val.lattice_val == CONSTANT 1210 && TREE_CODE (orig_lhs) == COMPONENT_REF 1211 && DECL_BIT_FIELD (TREE_OPERAND (orig_lhs, 1))) 1212 { 1213 tree w = widen_bitfield (val.value, TREE_OPERAND (orig_lhs, 1), 1214 orig_lhs); 1215 1216 if (w && is_gimple_min_invariant (w)) 1217 val.value = w; 1218 else 1219 { 1220 val.lattice_val = VARYING; 1221 val.value = NULL_TREE; 1222 val.mem_ref = NULL_TREE; 1223 } 1224 } 1225 } 1226 1227 retval = SSA_PROP_NOT_INTERESTING; 1228 1229 /* Set the lattice value of the statement's output. */ 1230 if (TREE_CODE (lhs) == SSA_NAME) 1231 { 1232 /* If STMT is an assignment to an SSA_NAME, we only have one 1233 value to set. */ 1234 if (set_lattice_value (lhs, val)) 1235 { 1236 *output_p = lhs; 1237 if (val.lattice_val == VARYING) 1238 retval = SSA_PROP_VARYING; 1239 else 1240 retval = SSA_PROP_INTERESTING; 1241 } 1242 } 1243 else if (do_store_ccp && stmt_makes_single_store (stmt)) 1244 { 1245 /* Otherwise, set the names in V_MAY_DEF/V_MUST_DEF operands 1246 to the new constant value and mark the LHS as the memory 1247 reference associated with VAL. */ 1248 ssa_op_iter i; 1249 tree vdef; 1250 bool changed; 1251 1252 /* Stores cannot take on an UNDEFINED value. */ 1253 if (val.lattice_val == UNDEFINED) 1254 val.lattice_val = UNKNOWN_VAL; 1255 1256 /* Mark VAL as stored in the LHS of this assignment. */ 1257 val.mem_ref = lhs; 1258 1259 /* Set the value of every VDEF to VAL. */ 1260 changed = false; 1261 FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VIRTUAL_DEFS) 1262 changed |= set_lattice_value (vdef, val); 1263 1264 /* Note that for propagation purposes, we are only interested in 1265 visiting statements that load the exact same memory reference 1266 stored here. Those statements will have the exact same list 1267 of virtual uses, so it is enough to set the output of this 1268 statement to be its first virtual definition. */ 1269 *output_p = first_vdef (stmt); 1270 if (changed) 1271 { 1272 if (val.lattice_val == VARYING) 1273 retval = SSA_PROP_VARYING; 1274 else 1275 retval = SSA_PROP_INTERESTING; 1276 } 1277 } 1278 1279 return retval; 1280} 1281 1282 1283/* Visit the conditional statement STMT. Return SSA_PROP_INTERESTING 1284 if it can determine which edge will be taken. Otherwise, return 1285 SSA_PROP_VARYING. */ 1286 1287static enum ssa_prop_result 1288visit_cond_stmt (tree stmt, edge *taken_edge_p) 1289{ 1290 prop_value_t val; 1291 basic_block block; 1292 1293 block = bb_for_stmt (stmt); 1294 val = evaluate_stmt (stmt); 1295 1296 /* Find which edge out of the conditional block will be taken and add it 1297 to the worklist. If no single edge can be determined statically, 1298 return SSA_PROP_VARYING to feed all the outgoing edges to the 1299 propagation engine. */ 1300 *taken_edge_p = val.value ? find_taken_edge (block, val.value) : 0; 1301 if (*taken_edge_p) 1302 return SSA_PROP_INTERESTING; 1303 else 1304 return SSA_PROP_VARYING; 1305} 1306 1307 1308/* Evaluate statement STMT. If the statement produces an output value and 1309 its evaluation changes the lattice value of its output, return 1310 SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the 1311 output value. 1312 1313 If STMT is a conditional branch and we can determine its truth 1314 value, set *TAKEN_EDGE_P accordingly. If STMT produces a varying 1315 value, return SSA_PROP_VARYING. */ 1316 1317static enum ssa_prop_result 1318ccp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p) 1319{ 1320 tree def; 1321 ssa_op_iter iter; 1322 1323 if (dump_file && (dump_flags & TDF_DETAILS)) 1324 { 1325 fprintf (dump_file, "\nVisiting statement:\n"); 1326 print_generic_stmt (dump_file, stmt, dump_flags); 1327 fprintf (dump_file, "\n"); 1328 } 1329 1330 if (TREE_CODE (stmt) == MODIFY_EXPR) 1331 { 1332 /* If the statement is an assignment that produces a single 1333 output value, evaluate its RHS to see if the lattice value of 1334 its output has changed. */ 1335 return visit_assignment (stmt, output_p); 1336 } 1337 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR) 1338 { 1339 /* If STMT is a conditional branch, see if we can determine 1340 which branch will be taken. */ 1341 return visit_cond_stmt (stmt, taken_edge_p); 1342 } 1343 1344 /* Any other kind of statement is not interesting for constant 1345 propagation and, therefore, not worth simulating. */ 1346 if (dump_file && (dump_flags & TDF_DETAILS)) 1347 fprintf (dump_file, "No interesting values produced. Marked VARYING.\n"); 1348 1349 /* Definitions made by statements other than assignments to 1350 SSA_NAMEs represent unknown modifications to their outputs. 1351 Mark them VARYING. */ 1352 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 1353 { 1354 prop_value_t v = { VARYING, NULL_TREE, NULL_TREE }; 1355 set_lattice_value (def, v); 1356 } 1357 1358 return SSA_PROP_VARYING; 1359} 1360 1361 1362/* Main entry point for SSA Conditional Constant Propagation. */ 1363 1364static void 1365execute_ssa_ccp (bool store_ccp) 1366{ 1367 do_store_ccp = store_ccp; 1368 ccp_initialize (); 1369 ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node); 1370 ccp_finalize (); 1371} 1372 1373 1374static void 1375do_ssa_ccp (void) 1376{ 1377 execute_ssa_ccp (false); 1378} 1379 1380 1381static bool 1382gate_ccp (void) 1383{ 1384 return flag_tree_ccp != 0; 1385} 1386 1387 1388struct tree_opt_pass pass_ccp = 1389{ 1390 "ccp", /* name */ 1391 gate_ccp, /* gate */ 1392 do_ssa_ccp, /* execute */ 1393 NULL, /* sub */ 1394 NULL, /* next */ 1395 0, /* static_pass_number */ 1396 TV_TREE_CCP, /* tv_id */ 1397 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 1398 0, /* properties_provided */ 1399 0, /* properties_destroyed */ 1400 0, /* todo_flags_start */ 1401 TODO_cleanup_cfg | TODO_dump_func | TODO_update_ssa 1402 | TODO_ggc_collect | TODO_verify_ssa 1403 | TODO_verify_stmts, /* todo_flags_finish */ 1404 0 /* letter */ 1405}; 1406 1407 1408static void 1409do_ssa_store_ccp (void) 1410{ 1411 /* If STORE-CCP is not enabled, we just run regular CCP. */ 1412 execute_ssa_ccp (flag_tree_store_ccp != 0); 1413} 1414 1415static bool 1416gate_store_ccp (void) 1417{ 1418 /* STORE-CCP is enabled only with -ftree-store-ccp, but when 1419 -fno-tree-store-ccp is specified, we should run regular CCP. 1420 That's why the pass is enabled with either flag. */ 1421 return flag_tree_store_ccp != 0 || flag_tree_ccp != 0; 1422} 1423 1424 1425struct tree_opt_pass pass_store_ccp = 1426{ 1427 "store_ccp", /* name */ 1428 gate_store_ccp, /* gate */ 1429 do_ssa_store_ccp, /* execute */ 1430 NULL, /* sub */ 1431 NULL, /* next */ 1432 0, /* static_pass_number */ 1433 TV_TREE_STORE_CCP, /* tv_id */ 1434 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 1435 0, /* properties_provided */ 1436 0, /* properties_destroyed */ 1437 0, /* todo_flags_start */ 1438 TODO_dump_func | TODO_update_ssa 1439 | TODO_ggc_collect | TODO_verify_ssa 1440 | TODO_cleanup_cfg 1441 | TODO_verify_stmts, /* todo_flags_finish */ 1442 0 /* letter */ 1443}; 1444 1445/* Given a constant value VAL for bitfield FIELD, and a destination 1446 variable VAR, return VAL appropriately widened to fit into VAR. If 1447 FIELD is wider than HOST_WIDE_INT, NULL is returned. */ 1448 1449tree 1450widen_bitfield (tree val, tree field, tree var) 1451{ 1452 unsigned HOST_WIDE_INT var_size, field_size; 1453 tree wide_val; 1454 unsigned HOST_WIDE_INT mask; 1455 unsigned int i; 1456 1457 /* We can only do this if the size of the type and field and VAL are 1458 all constants representable in HOST_WIDE_INT. */ 1459 if (!host_integerp (TYPE_SIZE (TREE_TYPE (var)), 1) 1460 || !host_integerp (DECL_SIZE (field), 1) 1461 || !host_integerp (val, 0)) 1462 return NULL_TREE; 1463 1464 var_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (var)), 1); 1465 field_size = tree_low_cst (DECL_SIZE (field), 1); 1466 1467 /* Give up if either the bitfield or the variable are too wide. */ 1468 if (field_size > HOST_BITS_PER_WIDE_INT || var_size > HOST_BITS_PER_WIDE_INT) 1469 return NULL_TREE; 1470 1471 gcc_assert (var_size >= field_size); 1472 1473 /* If the sign bit of the value is not set or the field's type is unsigned, 1474 just mask off the high order bits of the value. */ 1475 if (DECL_UNSIGNED (field) 1476 || !(tree_low_cst (val, 0) & (((HOST_WIDE_INT)1) << (field_size - 1)))) 1477 { 1478 /* Zero extension. Build a mask with the lower 'field_size' bits 1479 set and a BIT_AND_EXPR node to clear the high order bits of 1480 the value. */ 1481 for (i = 0, mask = 0; i < field_size; i++) 1482 mask |= ((HOST_WIDE_INT) 1) << i; 1483 1484 wide_val = fold_build2 (BIT_AND_EXPR, TREE_TYPE (var), val, 1485 build_int_cst (TREE_TYPE (var), mask)); 1486 } 1487 else 1488 { 1489 /* Sign extension. Create a mask with the upper 'field_size' 1490 bits set and a BIT_IOR_EXPR to set the high order bits of the 1491 value. */ 1492 for (i = 0, mask = 0; i < (var_size - field_size); i++) 1493 mask |= ((HOST_WIDE_INT) 1) << (var_size - i - 1); 1494 1495 wide_val = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (var), val, 1496 build_int_cst (TREE_TYPE (var), mask)); 1497 } 1498 1499 return wide_val; 1500} 1501 1502 1503/* A subroutine of fold_stmt_r. Attempts to fold *(A+O) to A[X]. 1504 BASE is an array type. OFFSET is a byte displacement. ORIG_TYPE 1505 is the desired result type. */ 1506 1507static tree 1508maybe_fold_offset_to_array_ref (tree base, tree offset, tree orig_type) 1509{ 1510 tree min_idx, idx, elt_offset = integer_zero_node; 1511 tree array_type, elt_type, elt_size; 1512 1513 /* If BASE is an ARRAY_REF, we can pick up another offset (this time 1514 measured in units of the size of elements type) from that ARRAY_REF). 1515 We can't do anything if either is variable. 1516 1517 The case we handle here is *(&A[N]+O). */ 1518 if (TREE_CODE (base) == ARRAY_REF) 1519 { 1520 tree low_bound = array_ref_low_bound (base); 1521 1522 elt_offset = TREE_OPERAND (base, 1); 1523 if (TREE_CODE (low_bound) != INTEGER_CST 1524 || TREE_CODE (elt_offset) != INTEGER_CST) 1525 return NULL_TREE; 1526 1527 elt_offset = int_const_binop (MINUS_EXPR, elt_offset, low_bound, 0); 1528 base = TREE_OPERAND (base, 0); 1529 } 1530 1531 /* Ignore stupid user tricks of indexing non-array variables. */ 1532 array_type = TREE_TYPE (base); 1533 if (TREE_CODE (array_type) != ARRAY_TYPE) 1534 return NULL_TREE; 1535 elt_type = TREE_TYPE (array_type); 1536 if (!lang_hooks.types_compatible_p (orig_type, elt_type)) 1537 return NULL_TREE; 1538 1539 /* If OFFSET and ELT_OFFSET are zero, we don't care about the size of the 1540 element type (so we can use the alignment if it's not constant). 1541 Otherwise, compute the offset as an index by using a division. If the 1542 division isn't exact, then don't do anything. */ 1543 elt_size = TYPE_SIZE_UNIT (elt_type); 1544 if (integer_zerop (offset)) 1545 { 1546 if (TREE_CODE (elt_size) != INTEGER_CST) 1547 elt_size = size_int (TYPE_ALIGN (elt_type)); 1548 1549 idx = integer_zero_node; 1550 } 1551 else 1552 { 1553 unsigned HOST_WIDE_INT lquo, lrem; 1554 HOST_WIDE_INT hquo, hrem; 1555 1556 if (TREE_CODE (elt_size) != INTEGER_CST 1557 || div_and_round_double (TRUNC_DIV_EXPR, 1, 1558 TREE_INT_CST_LOW (offset), 1559 TREE_INT_CST_HIGH (offset), 1560 TREE_INT_CST_LOW (elt_size), 1561 TREE_INT_CST_HIGH (elt_size), 1562 &lquo, &hquo, &lrem, &hrem) 1563 || lrem || hrem) 1564 return NULL_TREE; 1565 1566 idx = build_int_cst_wide (NULL_TREE, lquo, hquo); 1567 } 1568 1569 /* Assume the low bound is zero. If there is a domain type, get the 1570 low bound, if any, convert the index into that type, and add the 1571 low bound. */ 1572 min_idx = integer_zero_node; 1573 if (TYPE_DOMAIN (array_type)) 1574 { 1575 if (TYPE_MIN_VALUE (TYPE_DOMAIN (array_type))) 1576 min_idx = TYPE_MIN_VALUE (TYPE_DOMAIN (array_type)); 1577 else 1578 min_idx = fold_convert (TYPE_DOMAIN (array_type), min_idx); 1579 1580 if (TREE_CODE (min_idx) != INTEGER_CST) 1581 return NULL_TREE; 1582 1583 idx = fold_convert (TYPE_DOMAIN (array_type), idx); 1584 elt_offset = fold_convert (TYPE_DOMAIN (array_type), elt_offset); 1585 } 1586 1587 if (!integer_zerop (min_idx)) 1588 idx = int_const_binop (PLUS_EXPR, idx, min_idx, 0); 1589 if (!integer_zerop (elt_offset)) 1590 idx = int_const_binop (PLUS_EXPR, idx, elt_offset, 0); 1591 1592 return build (ARRAY_REF, orig_type, base, idx, min_idx, 1593 size_int (tree_low_cst (elt_size, 1) 1594 / (TYPE_ALIGN_UNIT (elt_type)))); 1595} 1596 1597 1598/* A subroutine of fold_stmt_r. Attempts to fold *(S+O) to S.X. 1599 BASE is a record type. OFFSET is a byte displacement. ORIG_TYPE 1600 is the desired result type. */ 1601/* ??? This doesn't handle class inheritance. */ 1602 1603static tree 1604maybe_fold_offset_to_component_ref (tree record_type, tree base, tree offset, 1605 tree orig_type, bool base_is_ptr) 1606{ 1607 tree f, t, field_type, tail_array_field, field_offset; 1608 1609 if (TREE_CODE (record_type) != RECORD_TYPE 1610 && TREE_CODE (record_type) != UNION_TYPE 1611 && TREE_CODE (record_type) != QUAL_UNION_TYPE) 1612 return NULL_TREE; 1613 1614 /* Short-circuit silly cases. */ 1615 if (lang_hooks.types_compatible_p (record_type, orig_type)) 1616 return NULL_TREE; 1617 1618 tail_array_field = NULL_TREE; 1619 for (f = TYPE_FIELDS (record_type); f ; f = TREE_CHAIN (f)) 1620 { 1621 int cmp; 1622 1623 if (TREE_CODE (f) != FIELD_DECL) 1624 continue; 1625 if (DECL_BIT_FIELD (f)) 1626 continue; 1627 1628 field_offset = byte_position (f); 1629 if (TREE_CODE (field_offset) != INTEGER_CST) 1630 continue; 1631 1632 /* ??? Java creates "interesting" fields for representing base classes. 1633 They have no name, and have no context. With no context, we get into 1634 trouble with nonoverlapping_component_refs_p. Skip them. */ 1635 if (!DECL_FIELD_CONTEXT (f)) 1636 continue; 1637 1638 /* The previous array field isn't at the end. */ 1639 tail_array_field = NULL_TREE; 1640 1641 /* Check to see if this offset overlaps with the field. */ 1642 cmp = tree_int_cst_compare (field_offset, offset); 1643 if (cmp > 0) 1644 continue; 1645 1646 field_type = TREE_TYPE (f); 1647 1648 /* Here we exactly match the offset being checked. If the types match, 1649 then we can return that field. */ 1650 if (cmp == 0 1651 && lang_hooks.types_compatible_p (orig_type, field_type)) 1652 { 1653 if (base_is_ptr) 1654 base = build1 (INDIRECT_REF, record_type, base); 1655 t = build (COMPONENT_REF, field_type, base, f, NULL_TREE); 1656 return t; 1657 } 1658 1659 /* Don't care about offsets into the middle of scalars. */ 1660 if (!AGGREGATE_TYPE_P (field_type)) 1661 continue; 1662 1663 /* Check for array at the end of the struct. This is often 1664 used as for flexible array members. We should be able to 1665 turn this into an array access anyway. */ 1666 if (TREE_CODE (field_type) == ARRAY_TYPE) 1667 tail_array_field = f; 1668 1669 /* Check the end of the field against the offset. */ 1670 if (!DECL_SIZE_UNIT (f) 1671 || TREE_CODE (DECL_SIZE_UNIT (f)) != INTEGER_CST) 1672 continue; 1673 t = int_const_binop (MINUS_EXPR, offset, field_offset, 1); 1674 if (!tree_int_cst_lt (t, DECL_SIZE_UNIT (f))) 1675 continue; 1676 1677 /* If we matched, then set offset to the displacement into 1678 this field. */ 1679 offset = t; 1680 goto found; 1681 } 1682 1683 if (!tail_array_field) 1684 return NULL_TREE; 1685 1686 f = tail_array_field; 1687 field_type = TREE_TYPE (f); 1688 offset = int_const_binop (MINUS_EXPR, offset, byte_position (f), 1); 1689 1690 found: 1691 /* If we get here, we've got an aggregate field, and a possibly 1692 nonzero offset into them. Recurse and hope for a valid match. */ 1693 if (base_is_ptr) 1694 base = build1 (INDIRECT_REF, record_type, base); 1695 base = build (COMPONENT_REF, field_type, base, f, NULL_TREE); 1696 1697 t = maybe_fold_offset_to_array_ref (base, offset, orig_type); 1698 if (t) 1699 return t; 1700 return maybe_fold_offset_to_component_ref (field_type, base, offset, 1701 orig_type, false); 1702} 1703 1704 1705/* A subroutine of fold_stmt_r. Attempt to simplify *(BASE+OFFSET). 1706 Return the simplified expression, or NULL if nothing could be done. */ 1707 1708static tree 1709maybe_fold_stmt_indirect (tree expr, tree base, tree offset) 1710{ 1711 tree t; 1712 1713 /* We may well have constructed a double-nested PLUS_EXPR via multiple 1714 substitutions. Fold that down to one. Remove NON_LVALUE_EXPRs that 1715 are sometimes added. */ 1716 base = fold (base); 1717 STRIP_TYPE_NOPS (base); 1718 TREE_OPERAND (expr, 0) = base; 1719 1720 /* One possibility is that the address reduces to a string constant. */ 1721 t = fold_read_from_constant_string (expr); 1722 if (t) 1723 return t; 1724 1725 /* Add in any offset from a PLUS_EXPR. */ 1726 if (TREE_CODE (base) == PLUS_EXPR) 1727 { 1728 tree offset2; 1729 1730 offset2 = TREE_OPERAND (base, 1); 1731 if (TREE_CODE (offset2) != INTEGER_CST) 1732 return NULL_TREE; 1733 base = TREE_OPERAND (base, 0); 1734 1735 offset = int_const_binop (PLUS_EXPR, offset, offset2, 1); 1736 } 1737 1738 if (TREE_CODE (base) == ADDR_EXPR) 1739 { 1740 /* Strip the ADDR_EXPR. */ 1741 base = TREE_OPERAND (base, 0); 1742 1743 /* Fold away CONST_DECL to its value, if the type is scalar. */ 1744 if (TREE_CODE (base) == CONST_DECL 1745 && ccp_decl_initial_min_invariant (DECL_INITIAL (base))) 1746 return DECL_INITIAL (base); 1747 1748 /* Try folding *(&B+O) to B[X]. */ 1749 t = maybe_fold_offset_to_array_ref (base, offset, TREE_TYPE (expr)); 1750 if (t) 1751 return t; 1752 1753 /* Try folding *(&B+O) to B.X. */ 1754 t = maybe_fold_offset_to_component_ref (TREE_TYPE (base), base, offset, 1755 TREE_TYPE (expr), false); 1756 if (t) 1757 return t; 1758 1759 /* Fold *&B to B. We can only do this if EXPR is the same type 1760 as BASE. We can't do this if EXPR is the element type of an array 1761 and BASE is the array. */ 1762 if (integer_zerop (offset) 1763 && lang_hooks.types_compatible_p (TREE_TYPE (base), 1764 TREE_TYPE (expr))) 1765 return base; 1766 } 1767 else 1768 { 1769 /* We can get here for out-of-range string constant accesses, 1770 such as "_"[3]. Bail out of the entire substitution search 1771 and arrange for the entire statement to be replaced by a 1772 call to __builtin_trap. In all likelihood this will all be 1773 constant-folded away, but in the meantime we can't leave with 1774 something that get_expr_operands can't understand. */ 1775 1776 t = base; 1777 STRIP_NOPS (t); 1778 if (TREE_CODE (t) == ADDR_EXPR 1779 && TREE_CODE (TREE_OPERAND (t, 0)) == STRING_CST) 1780 { 1781 /* FIXME: Except that this causes problems elsewhere with dead 1782 code not being deleted, and we die in the rtl expanders 1783 because we failed to remove some ssa_name. In the meantime, 1784 just return zero. */ 1785 /* FIXME2: This condition should be signaled by 1786 fold_read_from_constant_string directly, rather than 1787 re-checking for it here. */ 1788 return integer_zero_node; 1789 } 1790 1791 /* Try folding *(B+O) to B->X. Still an improvement. */ 1792 if (POINTER_TYPE_P (TREE_TYPE (base))) 1793 { 1794 t = maybe_fold_offset_to_component_ref (TREE_TYPE (TREE_TYPE (base)), 1795 base, offset, 1796 TREE_TYPE (expr), true); 1797 if (t) 1798 return t; 1799 } 1800 } 1801 1802 /* Otherwise we had an offset that we could not simplify. */ 1803 return NULL_TREE; 1804} 1805 1806 1807/* A subroutine of fold_stmt_r. EXPR is a PLUS_EXPR. 1808 1809 A quaint feature extant in our address arithmetic is that there 1810 can be hidden type changes here. The type of the result need 1811 not be the same as the type of the input pointer. 1812 1813 What we're after here is an expression of the form 1814 (T *)(&array + const) 1815 where the cast doesn't actually exist, but is implicit in the 1816 type of the PLUS_EXPR. We'd like to turn this into 1817 &array[x] 1818 which may be able to propagate further. */ 1819 1820static tree 1821maybe_fold_stmt_addition (tree expr) 1822{ 1823 tree op0 = TREE_OPERAND (expr, 0); 1824 tree op1 = TREE_OPERAND (expr, 1); 1825 tree ptr_type = TREE_TYPE (expr); 1826 tree ptd_type; 1827 tree t; 1828 bool subtract = (TREE_CODE (expr) == MINUS_EXPR); 1829 1830 /* We're only interested in pointer arithmetic. */ 1831 if (!POINTER_TYPE_P (ptr_type)) 1832 return NULL_TREE; 1833 /* Canonicalize the integral operand to op1. */ 1834 if (INTEGRAL_TYPE_P (TREE_TYPE (op0))) 1835 { 1836 if (subtract) 1837 return NULL_TREE; 1838 t = op0, op0 = op1, op1 = t; 1839 } 1840 /* It had better be a constant. */ 1841 if (TREE_CODE (op1) != INTEGER_CST) 1842 return NULL_TREE; 1843 /* The first operand should be an ADDR_EXPR. */ 1844 if (TREE_CODE (op0) != ADDR_EXPR) 1845 return NULL_TREE; 1846 op0 = TREE_OPERAND (op0, 0); 1847 1848 /* If the first operand is an ARRAY_REF, expand it so that we can fold 1849 the offset into it. */ 1850 while (TREE_CODE (op0) == ARRAY_REF) 1851 { 1852 tree array_obj = TREE_OPERAND (op0, 0); 1853 tree array_idx = TREE_OPERAND (op0, 1); 1854 tree elt_type = TREE_TYPE (op0); 1855 tree elt_size = TYPE_SIZE_UNIT (elt_type); 1856 tree min_idx; 1857 1858 if (TREE_CODE (array_idx) != INTEGER_CST) 1859 break; 1860 if (TREE_CODE (elt_size) != INTEGER_CST) 1861 break; 1862 1863 /* Un-bias the index by the min index of the array type. */ 1864 min_idx = TYPE_DOMAIN (TREE_TYPE (array_obj)); 1865 if (min_idx) 1866 { 1867 min_idx = TYPE_MIN_VALUE (min_idx); 1868 if (min_idx) 1869 { 1870 if (TREE_CODE (min_idx) != INTEGER_CST) 1871 break; 1872 1873 array_idx = convert (TREE_TYPE (min_idx), array_idx); 1874 if (!integer_zerop (min_idx)) 1875 array_idx = int_const_binop (MINUS_EXPR, array_idx, 1876 min_idx, 0); 1877 } 1878 } 1879 1880 /* Convert the index to a byte offset. */ 1881 array_idx = convert (sizetype, array_idx); 1882 array_idx = int_const_binop (MULT_EXPR, array_idx, elt_size, 0); 1883 1884 /* Update the operands for the next round, or for folding. */ 1885 /* If we're manipulating unsigned types, then folding into negative 1886 values can produce incorrect results. Particularly if the type 1887 is smaller than the width of the pointer. */ 1888 if (subtract 1889 && TYPE_UNSIGNED (TREE_TYPE (op1)) 1890 && tree_int_cst_lt (array_idx, op1)) 1891 return NULL; 1892 op1 = int_const_binop (subtract ? MINUS_EXPR : PLUS_EXPR, 1893 array_idx, op1, 0); 1894 subtract = false; 1895 op0 = array_obj; 1896 } 1897 1898 /* If we weren't able to fold the subtraction into another array reference, 1899 canonicalize the integer for passing to the array and component ref 1900 simplification functions. */ 1901 if (subtract) 1902 { 1903 if (TYPE_UNSIGNED (TREE_TYPE (op1))) 1904 return NULL; 1905 op1 = fold_build1 (NEGATE_EXPR, TREE_TYPE (op1), op1); 1906 /* ??? In theory fold should always produce another integer. */ 1907 if (TREE_CODE (op1) != INTEGER_CST) 1908 return NULL; 1909 } 1910 1911 ptd_type = TREE_TYPE (ptr_type); 1912 1913 /* At which point we can try some of the same things as for indirects. */ 1914 t = maybe_fold_offset_to_array_ref (op0, op1, ptd_type); 1915 if (!t) 1916 t = maybe_fold_offset_to_component_ref (TREE_TYPE (op0), op0, op1, 1917 ptd_type, false); 1918 if (t) 1919 t = build1 (ADDR_EXPR, ptr_type, t); 1920 1921 return t; 1922} 1923 1924/* Subroutine of fold_stmt called via walk_tree. We perform several 1925 simplifications of EXPR_P, mostly having to do with pointer arithmetic. */ 1926 1927static tree 1928fold_stmt_r (tree *expr_p, int *walk_subtrees, void *data) 1929{ 1930 bool *changed_p = data; 1931 tree expr = *expr_p, t; 1932 1933 /* ??? It'd be nice if walk_tree had a pre-order option. */ 1934 switch (TREE_CODE (expr)) 1935 { 1936 case INDIRECT_REF: 1937 t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL); 1938 if (t) 1939 return t; 1940 *walk_subtrees = 0; 1941 1942 t = maybe_fold_stmt_indirect (expr, TREE_OPERAND (expr, 0), 1943 integer_zero_node); 1944 break; 1945 1946 /* ??? Could handle ARRAY_REF here, as a variant of INDIRECT_REF. 1947 We'd only want to bother decomposing an existing ARRAY_REF if 1948 the base array is found to have another offset contained within. 1949 Otherwise we'd be wasting time. */ 1950 1951 case ADDR_EXPR: 1952 t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL); 1953 if (t) 1954 return t; 1955 *walk_subtrees = 0; 1956 1957 /* Set TREE_INVARIANT properly so that the value is properly 1958 considered constant, and so gets propagated as expected. */ 1959 if (*changed_p) 1960 recompute_tree_invarant_for_addr_expr (expr); 1961 return NULL_TREE; 1962 1963 case PLUS_EXPR: 1964 case MINUS_EXPR: 1965 t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL); 1966 if (t) 1967 return t; 1968 t = walk_tree (&TREE_OPERAND (expr, 1), fold_stmt_r, data, NULL); 1969 if (t) 1970 return t; 1971 *walk_subtrees = 0; 1972 1973 t = maybe_fold_stmt_addition (expr); 1974 break; 1975 1976 case COMPONENT_REF: 1977 t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL); 1978 if (t) 1979 return t; 1980 *walk_subtrees = 0; 1981 1982 /* Make sure the FIELD_DECL is actually a field in the type on the lhs. 1983 We've already checked that the records are compatible, so we should 1984 come up with a set of compatible fields. */ 1985 { 1986 tree expr_record = TREE_TYPE (TREE_OPERAND (expr, 0)); 1987 tree expr_field = TREE_OPERAND (expr, 1); 1988 1989 if (DECL_FIELD_CONTEXT (expr_field) != TYPE_MAIN_VARIANT (expr_record)) 1990 { 1991 expr_field = find_compatible_field (expr_record, expr_field); 1992 TREE_OPERAND (expr, 1) = expr_field; 1993 } 1994 } 1995 break; 1996 1997 case TARGET_MEM_REF: 1998 t = maybe_fold_tmr (expr); 1999 break; 2000 2001 default: 2002 return NULL_TREE; 2003 } 2004 2005 if (t) 2006 { 2007 *expr_p = t; 2008 *changed_p = true; 2009 } 2010 2011 return NULL_TREE; 2012} 2013 2014 2015/* Return the string length, maximum string length or maximum value of 2016 ARG in LENGTH. 2017 If ARG is an SSA name variable, follow its use-def chains. If LENGTH 2018 is not NULL and, for TYPE == 0, its value is not equal to the length 2019 we determine or if we are unable to determine the length or value, 2020 return false. VISITED is a bitmap of visited variables. 2021 TYPE is 0 if string length should be returned, 1 for maximum string 2022 length and 2 for maximum value ARG can have. */ 2023 2024static bool 2025get_maxval_strlen (tree arg, tree *length, bitmap visited, int type) 2026{ 2027 tree var, def_stmt, val; 2028 2029 if (TREE_CODE (arg) != SSA_NAME) 2030 { 2031 if (type == 2) 2032 { 2033 val = arg; 2034 if (TREE_CODE (val) != INTEGER_CST 2035 || tree_int_cst_sgn (val) < 0) 2036 return false; 2037 } 2038 else 2039 val = c_strlen (arg, 1); 2040 if (!val) 2041 return false; 2042 2043 if (*length) 2044 { 2045 if (type > 0) 2046 { 2047 if (TREE_CODE (*length) != INTEGER_CST 2048 || TREE_CODE (val) != INTEGER_CST) 2049 return false; 2050 2051 if (tree_int_cst_lt (*length, val)) 2052 *length = val; 2053 return true; 2054 } 2055 else if (simple_cst_equal (val, *length) != 1) 2056 return false; 2057 } 2058 2059 *length = val; 2060 return true; 2061 } 2062 2063 /* If we were already here, break the infinite cycle. */ 2064 if (bitmap_bit_p (visited, SSA_NAME_VERSION (arg))) 2065 return true; 2066 bitmap_set_bit (visited, SSA_NAME_VERSION (arg)); 2067 2068 var = arg; 2069 def_stmt = SSA_NAME_DEF_STMT (var); 2070 2071 switch (TREE_CODE (def_stmt)) 2072 { 2073 case MODIFY_EXPR: 2074 { 2075 tree rhs; 2076 2077 /* The RHS of the statement defining VAR must either have a 2078 constant length or come from another SSA_NAME with a constant 2079 length. */ 2080 rhs = TREE_OPERAND (def_stmt, 1); 2081 STRIP_NOPS (rhs); 2082 return get_maxval_strlen (rhs, length, visited, type); 2083 } 2084 2085 case PHI_NODE: 2086 { 2087 /* All the arguments of the PHI node must have the same constant 2088 length. */ 2089 int i; 2090 2091 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) 2092 { 2093 tree arg = PHI_ARG_DEF (def_stmt, i); 2094 2095 /* If this PHI has itself as an argument, we cannot 2096 determine the string length of this argument. However, 2097 if we can find a constant string length for the other 2098 PHI args then we can still be sure that this is a 2099 constant string length. So be optimistic and just 2100 continue with the next argument. */ 2101 if (arg == PHI_RESULT (def_stmt)) 2102 continue; 2103 2104 if (!get_maxval_strlen (arg, length, visited, type)) 2105 return false; 2106 } 2107 2108 return true; 2109 } 2110 2111 default: 2112 break; 2113 } 2114 2115 2116 return false; 2117} 2118 2119 2120/* Fold builtin call FN in statement STMT. If it cannot be folded into a 2121 constant, return NULL_TREE. Otherwise, return its constant value. */ 2122 2123static tree 2124ccp_fold_builtin (tree stmt, tree fn) 2125{ 2126 tree result, val[3]; 2127 tree callee, arglist, a; 2128 int arg_mask, i, type; 2129 bitmap visited; 2130 bool ignore; 2131 2132 ignore = TREE_CODE (stmt) != MODIFY_EXPR; 2133 2134 /* First try the generic builtin folder. If that succeeds, return the 2135 result directly. */ 2136 callee = get_callee_fndecl (fn); 2137 arglist = TREE_OPERAND (fn, 1); 2138 result = fold_builtin (callee, arglist, ignore); 2139 if (result) 2140 { 2141 if (ignore) 2142 STRIP_NOPS (result); 2143 return result; 2144 } 2145 2146 /* Ignore MD builtins. */ 2147 if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_MD) 2148 return NULL_TREE; 2149 2150 /* If the builtin could not be folded, and it has no argument list, 2151 we're done. */ 2152 if (!arglist) 2153 return NULL_TREE; 2154 2155 /* Limit the work only for builtins we know how to simplify. */ 2156 switch (DECL_FUNCTION_CODE (callee)) 2157 { 2158 case BUILT_IN_STRLEN: 2159 case BUILT_IN_FPUTS: 2160 case BUILT_IN_FPUTS_UNLOCKED: 2161 arg_mask = 1; 2162 type = 0; 2163 break; 2164 case BUILT_IN_STRCPY: 2165 case BUILT_IN_STRNCPY: 2166 arg_mask = 2; 2167 type = 0; 2168 break; 2169 case BUILT_IN_MEMCPY_CHK: 2170 case BUILT_IN_MEMPCPY_CHK: 2171 case BUILT_IN_MEMMOVE_CHK: 2172 case BUILT_IN_MEMSET_CHK: 2173 case BUILT_IN_STRNCPY_CHK: 2174 arg_mask = 4; 2175 type = 2; 2176 break; 2177 case BUILT_IN_STRCPY_CHK: 2178 case BUILT_IN_STPCPY_CHK: 2179 arg_mask = 2; 2180 type = 1; 2181 break; 2182 case BUILT_IN_SNPRINTF_CHK: 2183 case BUILT_IN_VSNPRINTF_CHK: 2184 arg_mask = 2; 2185 type = 2; 2186 break; 2187 default: 2188 return NULL_TREE; 2189 } 2190 2191 /* Try to use the dataflow information gathered by the CCP process. */ 2192 visited = BITMAP_ALLOC (NULL); 2193 2194 memset (val, 0, sizeof (val)); 2195 for (i = 0, a = arglist; 2196 arg_mask; 2197 i++, arg_mask >>= 1, a = TREE_CHAIN (a)) 2198 if (arg_mask & 1) 2199 { 2200 bitmap_clear (visited); 2201 if (!get_maxval_strlen (TREE_VALUE (a), &val[i], visited, type)) 2202 val[i] = NULL_TREE; 2203 } 2204 2205 BITMAP_FREE (visited); 2206 2207 result = NULL_TREE; 2208 switch (DECL_FUNCTION_CODE (callee)) 2209 { 2210 case BUILT_IN_STRLEN: 2211 if (val[0]) 2212 { 2213 tree new = fold_convert (TREE_TYPE (fn), val[0]); 2214 2215 /* If the result is not a valid gimple value, or not a cast 2216 of a valid gimple value, then we can not use the result. */ 2217 if (is_gimple_val (new) 2218 || (is_gimple_cast (new) 2219 && is_gimple_val (TREE_OPERAND (new, 0)))) 2220 return new; 2221 } 2222 break; 2223 2224 case BUILT_IN_STRCPY: 2225 if (val[1] && is_gimple_val (val[1])) 2226 result = fold_builtin_strcpy (callee, arglist, val[1]); 2227 break; 2228 2229 case BUILT_IN_STRNCPY: 2230 if (val[1] && is_gimple_val (val[1])) 2231 result = fold_builtin_strncpy (callee, arglist, val[1]); 2232 break; 2233 2234 case BUILT_IN_FPUTS: 2235 result = fold_builtin_fputs (arglist, 2236 TREE_CODE (stmt) != MODIFY_EXPR, 0, 2237 val[0]); 2238 break; 2239 2240 case BUILT_IN_FPUTS_UNLOCKED: 2241 result = fold_builtin_fputs (arglist, 2242 TREE_CODE (stmt) != MODIFY_EXPR, 1, 2243 val[0]); 2244 break; 2245 2246 case BUILT_IN_MEMCPY_CHK: 2247 case BUILT_IN_MEMPCPY_CHK: 2248 case BUILT_IN_MEMMOVE_CHK: 2249 case BUILT_IN_MEMSET_CHK: 2250 if (val[2] && is_gimple_val (val[2])) 2251 result = fold_builtin_memory_chk (callee, arglist, val[2], ignore, 2252 DECL_FUNCTION_CODE (callee)); 2253 break; 2254 2255 case BUILT_IN_STRCPY_CHK: 2256 case BUILT_IN_STPCPY_CHK: 2257 if (val[1] && is_gimple_val (val[1])) 2258 result = fold_builtin_stxcpy_chk (callee, arglist, val[1], ignore, 2259 DECL_FUNCTION_CODE (callee)); 2260 break; 2261 2262 case BUILT_IN_STRNCPY_CHK: 2263 if (val[2] && is_gimple_val (val[2])) 2264 result = fold_builtin_strncpy_chk (arglist, val[2]); 2265 break; 2266 2267 case BUILT_IN_SNPRINTF_CHK: 2268 case BUILT_IN_VSNPRINTF_CHK: 2269 if (val[1] && is_gimple_val (val[1])) 2270 result = fold_builtin_snprintf_chk (arglist, val[1], 2271 DECL_FUNCTION_CODE (callee)); 2272 break; 2273 2274 default: 2275 gcc_unreachable (); 2276 } 2277 2278 if (result && ignore) 2279 result = fold_ignored_result (result); 2280 return result; 2281} 2282 2283 2284/* Fold the statement pointed to by STMT_P. In some cases, this function may 2285 replace the whole statement with a new one. Returns true iff folding 2286 makes any changes. */ 2287 2288bool 2289fold_stmt (tree *stmt_p) 2290{ 2291 tree rhs, result, stmt; 2292 bool changed = false; 2293 2294 stmt = *stmt_p; 2295 2296 /* If we replaced constants and the statement makes pointer dereferences, 2297 then we may need to fold instances of *&VAR into VAR, etc. */ 2298 if (walk_tree (stmt_p, fold_stmt_r, &changed, NULL)) 2299 { 2300 *stmt_p 2301 = build_function_call_expr (implicit_built_in_decls[BUILT_IN_TRAP], 2302 NULL); 2303 return true; 2304 } 2305 2306 rhs = get_rhs (stmt); 2307 if (!rhs) 2308 return changed; 2309 result = NULL_TREE; 2310 2311 if (TREE_CODE (rhs) == CALL_EXPR) 2312 { 2313 tree callee; 2314 2315 /* Check for builtins that CCP can handle using information not 2316 available in the generic fold routines. */ 2317 callee = get_callee_fndecl (rhs); 2318 if (callee && DECL_BUILT_IN (callee)) 2319 result = ccp_fold_builtin (stmt, rhs); 2320 else 2321 { 2322 /* Check for resolvable OBJ_TYPE_REF. The only sorts we can resolve 2323 here are when we've propagated the address of a decl into the 2324 object slot. */ 2325 /* ??? Should perhaps do this in fold proper. However, doing it 2326 there requires that we create a new CALL_EXPR, and that requires 2327 copying EH region info to the new node. Easier to just do it 2328 here where we can just smash the call operand. */ 2329 callee = TREE_OPERAND (rhs, 0); 2330 if (TREE_CODE (callee) == OBJ_TYPE_REF 2331 && lang_hooks.fold_obj_type_ref 2332 && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR 2333 && DECL_P (TREE_OPERAND 2334 (OBJ_TYPE_REF_OBJECT (callee), 0))) 2335 { 2336 tree t; 2337 2338 /* ??? Caution: Broken ADDR_EXPR semantics means that 2339 looking at the type of the operand of the addr_expr 2340 can yield an array type. See silly exception in 2341 check_pointer_types_r. */ 2342 2343 t = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (callee))); 2344 t = lang_hooks.fold_obj_type_ref (callee, t); 2345 if (t) 2346 { 2347 TREE_OPERAND (rhs, 0) = t; 2348 changed = true; 2349 } 2350 } 2351 } 2352 } 2353 2354 /* If we couldn't fold the RHS, hand over to the generic fold routines. */ 2355 if (result == NULL_TREE) 2356 result = fold (rhs); 2357 2358 /* Strip away useless type conversions. Both the NON_LVALUE_EXPR that 2359 may have been added by fold, and "useless" type conversions that might 2360 now be apparent due to propagation. */ 2361 STRIP_USELESS_TYPE_CONVERSION (result); 2362 2363 if (result != rhs) 2364 changed |= set_rhs (stmt_p, result); 2365 2366 return changed; 2367} 2368 2369/* Perform the minimal folding on statement STMT. Only operations like 2370 *&x created by constant propagation are handled. The statement cannot 2371 be replaced with a new one. */ 2372 2373bool 2374fold_stmt_inplace (tree stmt) 2375{ 2376 tree old_stmt = stmt, rhs, new_rhs; 2377 bool changed = false; 2378 2379 walk_tree (&stmt, fold_stmt_r, &changed, NULL); 2380 gcc_assert (stmt == old_stmt); 2381 2382 rhs = get_rhs (stmt); 2383 if (!rhs || rhs == stmt) 2384 return changed; 2385 2386 new_rhs = fold (rhs); 2387 STRIP_USELESS_TYPE_CONVERSION (new_rhs); 2388 if (new_rhs == rhs) 2389 return changed; 2390 2391 changed |= set_rhs (&stmt, new_rhs); 2392 gcc_assert (stmt == old_stmt); 2393 2394 return changed; 2395} 2396 2397/* Convert EXPR into a GIMPLE value suitable for substitution on the 2398 RHS of an assignment. Insert the necessary statements before 2399 iterator *SI_P. */ 2400 2401static tree 2402convert_to_gimple_builtin (block_stmt_iterator *si_p, tree expr) 2403{ 2404 tree_stmt_iterator ti; 2405 tree stmt = bsi_stmt (*si_p); 2406 tree tmp, stmts = NULL; 2407 2408 push_gimplify_context (); 2409 tmp = get_initialized_tmp_var (expr, &stmts, NULL); 2410 pop_gimplify_context (NULL); 2411 2412 if (EXPR_HAS_LOCATION (stmt)) 2413 annotate_all_with_locus (&stmts, EXPR_LOCATION (stmt)); 2414 2415 /* The replacement can expose previously unreferenced variables. */ 2416 for (ti = tsi_start (stmts); !tsi_end_p (ti); tsi_next (&ti)) 2417 { 2418 tree new_stmt = tsi_stmt (ti); 2419 find_new_referenced_vars (tsi_stmt_ptr (ti)); 2420 bsi_insert_before (si_p, new_stmt, BSI_NEW_STMT); 2421 mark_new_vars_to_rename (bsi_stmt (*si_p)); 2422 bsi_next (si_p); 2423 } 2424 2425 return tmp; 2426} 2427 2428 2429/* A simple pass that attempts to fold all builtin functions. This pass 2430 is run after we've propagated as many constants as we can. */ 2431 2432static void 2433execute_fold_all_builtins (void) 2434{ 2435 bool cfg_changed = false; 2436 basic_block bb; 2437 FOR_EACH_BB (bb) 2438 { 2439 block_stmt_iterator i; 2440 for (i = bsi_start (bb); !bsi_end_p (i); ) 2441 { 2442 tree *stmtp = bsi_stmt_ptr (i); 2443 tree old_stmt = *stmtp; 2444 tree call = get_rhs (*stmtp); 2445 tree callee, result; 2446 enum built_in_function fcode; 2447 2448 if (!call || TREE_CODE (call) != CALL_EXPR) 2449 { 2450 bsi_next (&i); 2451 continue; 2452 } 2453 callee = get_callee_fndecl (call); 2454 if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL) 2455 { 2456 bsi_next (&i); 2457 continue; 2458 } 2459 fcode = DECL_FUNCTION_CODE (callee); 2460 2461 result = ccp_fold_builtin (*stmtp, call); 2462 if (!result) 2463 switch (DECL_FUNCTION_CODE (callee)) 2464 { 2465 case BUILT_IN_CONSTANT_P: 2466 /* Resolve __builtin_constant_p. If it hasn't been 2467 folded to integer_one_node by now, it's fairly 2468 certain that the value simply isn't constant. */ 2469 result = integer_zero_node; 2470 break; 2471 2472 default: 2473 bsi_next (&i); 2474 continue; 2475 } 2476 2477 if (dump_file && (dump_flags & TDF_DETAILS)) 2478 { 2479 fprintf (dump_file, "Simplified\n "); 2480 print_generic_stmt (dump_file, *stmtp, dump_flags); 2481 } 2482 2483 if (!set_rhs (stmtp, result)) 2484 { 2485 result = convert_to_gimple_builtin (&i, result); 2486 if (result) 2487 { 2488 bool ok = set_rhs (stmtp, result); 2489 2490 gcc_assert (ok); 2491 } 2492 } 2493 mark_new_vars_to_rename (*stmtp); 2494 if (maybe_clean_or_replace_eh_stmt (old_stmt, *stmtp) 2495 && tree_purge_dead_eh_edges (bb)) 2496 cfg_changed = true; 2497 2498 if (dump_file && (dump_flags & TDF_DETAILS)) 2499 { 2500 fprintf (dump_file, "to\n "); 2501 print_generic_stmt (dump_file, *stmtp, dump_flags); 2502 fprintf (dump_file, "\n"); 2503 } 2504 2505 /* Retry the same statement if it changed into another 2506 builtin, there might be new opportunities now. */ 2507 call = get_rhs (*stmtp); 2508 if (!call || TREE_CODE (call) != CALL_EXPR) 2509 { 2510 bsi_next (&i); 2511 continue; 2512 } 2513 callee = get_callee_fndecl (call); 2514 if (!callee 2515 || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL 2516 || DECL_FUNCTION_CODE (callee) == fcode) 2517 bsi_next (&i); 2518 } 2519 } 2520 2521 /* Delete unreachable blocks. */ 2522 if (cfg_changed) 2523 cleanup_tree_cfg (); 2524} 2525 2526 2527struct tree_opt_pass pass_fold_builtins = 2528{ 2529 "fab", /* name */ 2530 NULL, /* gate */ 2531 execute_fold_all_builtins, /* execute */ 2532 NULL, /* sub */ 2533 NULL, /* next */ 2534 0, /* static_pass_number */ 2535 0, /* tv_id */ 2536 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 2537 0, /* properties_provided */ 2538 0, /* properties_destroyed */ 2539 0, /* todo_flags_start */ 2540 TODO_dump_func 2541 | TODO_verify_ssa 2542 | TODO_update_ssa, /* todo_flags_finish */ 2543 0 /* letter */ 2544}; 2545