1 /* Conditional constant propagation pass for the GNU compiler. 2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 3 2010, 2011, 2012, 2013 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 7 This file is part of GCC. 8 9 GCC is free software; you can redistribute it and/or modify it 10 under the terms of the GNU General Public License as published by the 11 Free Software Foundation; either version 3, or (at your option) any 12 later version. 13 14 GCC is distributed in the hope that it will be useful, but WITHOUT 15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 17 for more details. 18 19 You should have received a copy of the GNU General Public License 20 along with GCC; see the file COPYING3. If not see 21 <http://www.gnu.org/licenses/>. */ 22 23 /* Conditional constant propagation (CCP) is based on the SSA 24 propagation engine (tree-ssa-propagate.c). Constant assignments of 25 the form VAR = CST are propagated from the assignments into uses of 26 VAR, which in turn may generate new constants. The simulation uses 27 a four level lattice to keep track of constant values associated 28 with SSA names. Given an SSA name V_i, it may take one of the 29 following values: 30 31 UNINITIALIZED -> the initial state of the value. This value 32 is replaced with a correct initial value 33 the first time the value is used, so the 34 rest of the pass does not need to care about 35 it. Using this value simplifies initialization 36 of the pass, and prevents us from needlessly 37 scanning statements that are never reached. 38 39 UNDEFINED -> V_i is a local variable whose definition 40 has not been processed yet. Therefore we 41 don't yet know if its value is a constant 42 or not. 43 44 CONSTANT -> V_i has been found to hold a constant 45 value C. 46 47 VARYING -> V_i cannot take a constant value, or if it 48 does, it is not possible to determine it 49 at compile time. 50 51 The core of SSA-CCP is in ccp_visit_stmt and ccp_visit_phi_node: 52 53 1- In ccp_visit_stmt, we are interested in assignments whose RHS 54 evaluates into a constant and conditional jumps whose predicate 55 evaluates into a boolean true or false. When an assignment of 56 the form V_i = CONST is found, V_i's lattice value is set to 57 CONSTANT and CONST is associated with it. This causes the 58 propagation engine to add all the SSA edges coming out the 59 assignment into the worklists, so that statements that use V_i 60 can be visited. 61 62 If the statement is a conditional with a constant predicate, we 63 mark the outgoing edges as executable or not executable 64 depending on the predicate's value. This is then used when 65 visiting PHI nodes to know when a PHI argument can be ignored. 66 67 68 2- In ccp_visit_phi_node, if all the PHI arguments evaluate to the 69 same constant C, then the LHS of the PHI is set to C. This 70 evaluation is known as the "meet operation". Since one of the 71 goals of this evaluation is to optimistically return constant 72 values as often as possible, it uses two main short cuts: 73 74 - If an argument is flowing in through a non-executable edge, it 75 is ignored. This is useful in cases like this: 76 77 if (PRED) 78 a_9 = 3; 79 else 80 a_10 = 100; 81 a_11 = PHI (a_9, a_10) 82 83 If PRED is known to always evaluate to false, then we can 84 assume that a_11 will always take its value from a_10, meaning 85 that instead of consider it VARYING (a_9 and a_10 have 86 different values), we can consider it CONSTANT 100. 87 88 - If an argument has an UNDEFINED value, then it does not affect 89 the outcome of the meet operation. If a variable V_i has an 90 UNDEFINED value, it means that either its defining statement 91 hasn't been visited yet or V_i has no defining statement, in 92 which case the original symbol 'V' is being used 93 uninitialized. Since 'V' is a local variable, the compiler 94 may assume any initial value for it. 95 96 97 After propagation, every variable V_i that ends up with a lattice 98 value of CONSTANT will have the associated constant value in the 99 array CONST_VAL[i].VALUE. That is fed into substitute_and_fold for 100 final substitution and folding. 101 102 References: 103 104 Constant propagation with conditional branches, 105 Wegman and Zadeck, ACM TOPLAS 13(2):181-210. 106 107 Building an Optimizing Compiler, 108 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9. 109 110 Advanced Compiler Design and Implementation, 111 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */ 112 113 #include "config.h" 114 #include "system.h" 115 #include "coretypes.h" 116 #include "tm.h" 117 #include "tree.h" 118 #include "flags.h" 119 #include "tm_p.h" 120 #include "basic-block.h" 121 #include "output.h" 122 #include "function.h" 123 #include "tree-pretty-print.h" 124 #include "gimple-pretty-print.h" 125 #include "timevar.h" 126 #include "tree-dump.h" 127 #include "tree-flow.h" 128 #include "tree-pass.h" 129 #include "tree-ssa-propagate.h" 130 #include "value-prof.h" 131 #include "langhooks.h" 132 #include "target.h" 133 #include "diagnostic-core.h" 134 #include "dbgcnt.h" 135 #include "gimple-fold.h" 136 #include "params.h" 137 138 139 /* Possible lattice values. */ 140 typedef enum 141 { 142 UNINITIALIZED, 143 UNDEFINED, 144 CONSTANT, 145 VARYING 146 } ccp_lattice_t; 147 148 struct prop_value_d { 149 /* Lattice value. */ 150 ccp_lattice_t lattice_val; 151 152 /* Propagated value. */ 153 tree value; 154 155 /* Mask that applies to the propagated value during CCP. For 156 X with a CONSTANT lattice value X & ~mask == value & ~mask. */ 157 double_int mask; 158 }; 159 160 typedef struct prop_value_d prop_value_t; 161 162 /* Array of propagated constant values. After propagation, 163 CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I). If 164 the constant is held in an SSA name representing a memory store 165 (i.e., a VDEF), CONST_VAL[I].MEM_REF will contain the actual 166 memory reference used to store (i.e., the LHS of the assignment 167 doing the store). */ 168 static prop_value_t *const_val; 169 170 static void canonicalize_float_value (prop_value_t *); 171 static bool ccp_fold_stmt (gimple_stmt_iterator *); 172 173 /* Dump constant propagation value VAL to file OUTF prefixed by PREFIX. */ 174 175 static void 176 dump_lattice_value (FILE *outf, const char *prefix, prop_value_t val) 177 { 178 switch (val.lattice_val) 179 { 180 case UNINITIALIZED: 181 fprintf (outf, "%sUNINITIALIZED", prefix); 182 break; 183 case UNDEFINED: 184 fprintf (outf, "%sUNDEFINED", prefix); 185 break; 186 case VARYING: 187 fprintf (outf, "%sVARYING", prefix); 188 break; 189 case CONSTANT: 190 fprintf (outf, "%sCONSTANT ", prefix); 191 if (TREE_CODE (val.value) != INTEGER_CST 192 || double_int_zero_p (val.mask)) 193 print_generic_expr (outf, val.value, dump_flags); 194 else 195 { 196 double_int cval = double_int_and_not (tree_to_double_int (val.value), 197 val.mask); 198 fprintf (outf, "%sCONSTANT " HOST_WIDE_INT_PRINT_DOUBLE_HEX, 199 prefix, cval.high, cval.low); 200 fprintf (outf, " (" HOST_WIDE_INT_PRINT_DOUBLE_HEX ")", 201 val.mask.high, val.mask.low); 202 } 203 break; 204 default: 205 gcc_unreachable (); 206 } 207 } 208 209 210 /* Print lattice value VAL to stderr. */ 211 212 void debug_lattice_value (prop_value_t val); 213 214 DEBUG_FUNCTION void 215 debug_lattice_value (prop_value_t val) 216 { 217 dump_lattice_value (stderr, "", val); 218 fprintf (stderr, "\n"); 219 } 220 221 222 /* Compute a default value for variable VAR and store it in the 223 CONST_VAL array. The following rules are used to get default 224 values: 225 226 1- Global and static variables that are declared constant are 227 considered CONSTANT. 228 229 2- Any other value is considered UNDEFINED. This is useful when 230 considering PHI nodes. PHI arguments that are undefined do not 231 change the constant value of the PHI node, which allows for more 232 constants to be propagated. 233 234 3- Variables defined by statements other than assignments and PHI 235 nodes are considered VARYING. 236 237 4- Initial values of variables that are not GIMPLE registers are 238 considered VARYING. */ 239 240 static prop_value_t 241 get_default_value (tree var) 242 { 243 tree sym = SSA_NAME_VAR (var); 244 prop_value_t val = { UNINITIALIZED, NULL_TREE, { 0, 0 } }; 245 gimple stmt; 246 247 stmt = SSA_NAME_DEF_STMT (var); 248 249 if (gimple_nop_p (stmt)) 250 { 251 /* Variables defined by an empty statement are those used 252 before being initialized. If VAR is a local variable, we 253 can assume initially that it is UNDEFINED, otherwise we must 254 consider it VARYING. */ 255 if (is_gimple_reg (sym) 256 && TREE_CODE (sym) == VAR_DECL) 257 val.lattice_val = UNDEFINED; 258 else 259 { 260 val.lattice_val = VARYING; 261 val.mask = double_int_minus_one; 262 } 263 } 264 else if (is_gimple_assign (stmt) 265 /* Value-returning GIMPLE_CALL statements assign to 266 a variable, and are treated similarly to GIMPLE_ASSIGN. */ 267 || (is_gimple_call (stmt) 268 && gimple_call_lhs (stmt) != NULL_TREE) 269 || gimple_code (stmt) == GIMPLE_PHI) 270 { 271 tree cst; 272 if (gimple_assign_single_p (stmt) 273 && DECL_P (gimple_assign_rhs1 (stmt)) 274 && (cst = get_symbol_constant_value (gimple_assign_rhs1 (stmt)))) 275 { 276 val.lattice_val = CONSTANT; 277 val.value = cst; 278 } 279 else 280 /* Any other variable defined by an assignment or a PHI node 281 is considered UNDEFINED. */ 282 val.lattice_val = UNDEFINED; 283 } 284 else 285 { 286 /* Otherwise, VAR will never take on a constant value. */ 287 val.lattice_val = VARYING; 288 val.mask = double_int_minus_one; 289 } 290 291 return val; 292 } 293 294 295 /* Get the constant value associated with variable VAR. */ 296 297 static inline prop_value_t * 298 get_value (tree var) 299 { 300 prop_value_t *val; 301 302 if (const_val == NULL) 303 return NULL; 304 305 val = &const_val[SSA_NAME_VERSION (var)]; 306 if (val->lattice_val == UNINITIALIZED) 307 *val = get_default_value (var); 308 309 canonicalize_float_value (val); 310 311 return val; 312 } 313 314 /* Return the constant tree value associated with VAR. */ 315 316 static inline tree 317 get_constant_value (tree var) 318 { 319 prop_value_t *val; 320 if (TREE_CODE (var) != SSA_NAME) 321 { 322 if (is_gimple_min_invariant (var)) 323 return var; 324 return NULL_TREE; 325 } 326 val = get_value (var); 327 if (val 328 && val->lattice_val == CONSTANT 329 && (TREE_CODE (val->value) != INTEGER_CST 330 || double_int_zero_p (val->mask))) 331 return val->value; 332 return NULL_TREE; 333 } 334 335 /* Sets the value associated with VAR to VARYING. */ 336 337 static inline void 338 set_value_varying (tree var) 339 { 340 prop_value_t *val = &const_val[SSA_NAME_VERSION (var)]; 341 342 val->lattice_val = VARYING; 343 val->value = NULL_TREE; 344 val->mask = double_int_minus_one; 345 } 346 347 /* For float types, modify the value of VAL to make ccp work correctly 348 for non-standard values (-0, NaN): 349 350 If HONOR_SIGNED_ZEROS is false, and VAL = -0, we canonicalize it to 0. 351 If HONOR_NANS is false, and VAL is NaN, we canonicalize it to UNDEFINED. 352 This is to fix the following problem (see PR 29921): Suppose we have 353 354 x = 0.0 * y 355 356 and we set value of y to NaN. This causes value of x to be set to NaN. 357 When we later determine that y is in fact VARYING, fold uses the fact 358 that HONOR_NANS is false, and we try to change the value of x to 0, 359 causing an ICE. With HONOR_NANS being false, the real appearance of 360 NaN would cause undefined behavior, though, so claiming that y (and x) 361 are UNDEFINED initially is correct. */ 362 363 static void 364 canonicalize_float_value (prop_value_t *val) 365 { 366 enum machine_mode mode; 367 tree type; 368 REAL_VALUE_TYPE d; 369 370 if (val->lattice_val != CONSTANT 371 || TREE_CODE (val->value) != REAL_CST) 372 return; 373 374 d = TREE_REAL_CST (val->value); 375 type = TREE_TYPE (val->value); 376 mode = TYPE_MODE (type); 377 378 if (!HONOR_SIGNED_ZEROS (mode) 379 && REAL_VALUE_MINUS_ZERO (d)) 380 { 381 val->value = build_real (type, dconst0); 382 return; 383 } 384 385 if (!HONOR_NANS (mode) 386 && REAL_VALUE_ISNAN (d)) 387 { 388 val->lattice_val = UNDEFINED; 389 val->value = NULL; 390 return; 391 } 392 } 393 394 /* Return whether the lattice transition is valid. */ 395 396 static bool 397 valid_lattice_transition (prop_value_t old_val, prop_value_t new_val) 398 { 399 /* Lattice transitions must always be monotonically increasing in 400 value. */ 401 if (old_val.lattice_val < new_val.lattice_val) 402 return true; 403 404 if (old_val.lattice_val != new_val.lattice_val) 405 return false; 406 407 if (!old_val.value && !new_val.value) 408 return true; 409 410 /* Now both lattice values are CONSTANT. */ 411 412 /* Allow transitioning from PHI <&x, not executable> == &x 413 to PHI <&x, &y> == common alignment. */ 414 if (TREE_CODE (old_val.value) != INTEGER_CST 415 && TREE_CODE (new_val.value) == INTEGER_CST) 416 return true; 417 418 /* Bit-lattices have to agree in the still valid bits. */ 419 if (TREE_CODE (old_val.value) == INTEGER_CST 420 && TREE_CODE (new_val.value) == INTEGER_CST) 421 return double_int_equal_p 422 (double_int_and_not (tree_to_double_int (old_val.value), 423 new_val.mask), 424 double_int_and_not (tree_to_double_int (new_val.value), 425 new_val.mask)); 426 427 /* Otherwise constant values have to agree. */ 428 return operand_equal_p (old_val.value, new_val.value, 0); 429 } 430 431 /* Set the value for variable VAR to NEW_VAL. Return true if the new 432 value is different from VAR's previous value. */ 433 434 static bool 435 set_lattice_value (tree var, prop_value_t new_val) 436 { 437 /* We can deal with old UNINITIALIZED values just fine here. */ 438 prop_value_t *old_val = &const_val[SSA_NAME_VERSION (var)]; 439 440 canonicalize_float_value (&new_val); 441 442 /* We have to be careful to not go up the bitwise lattice 443 represented by the mask. 444 ??? This doesn't seem to be the best place to enforce this. */ 445 if (new_val.lattice_val == CONSTANT 446 && old_val->lattice_val == CONSTANT 447 && TREE_CODE (new_val.value) == INTEGER_CST 448 && TREE_CODE (old_val->value) == INTEGER_CST) 449 { 450 double_int diff; 451 diff = double_int_xor (tree_to_double_int (new_val.value), 452 tree_to_double_int (old_val->value)); 453 new_val.mask = double_int_ior (new_val.mask, 454 double_int_ior (old_val->mask, diff)); 455 } 456 457 gcc_assert (valid_lattice_transition (*old_val, new_val)); 458 459 /* If *OLD_VAL and NEW_VAL are the same, return false to inform the 460 caller that this was a non-transition. */ 461 if (old_val->lattice_val != new_val.lattice_val 462 || (new_val.lattice_val == CONSTANT 463 && TREE_CODE (new_val.value) == INTEGER_CST 464 && (TREE_CODE (old_val->value) != INTEGER_CST 465 || !double_int_equal_p (new_val.mask, old_val->mask)))) 466 { 467 /* ??? We would like to delay creation of INTEGER_CSTs from 468 partially constants here. */ 469 470 if (dump_file && (dump_flags & TDF_DETAILS)) 471 { 472 dump_lattice_value (dump_file, "Lattice value changed to ", new_val); 473 fprintf (dump_file, ". Adding SSA edges to worklist.\n"); 474 } 475 476 *old_val = new_val; 477 478 gcc_assert (new_val.lattice_val != UNINITIALIZED); 479 return true; 480 } 481 482 return false; 483 } 484 485 static prop_value_t get_value_for_expr (tree, bool); 486 static prop_value_t bit_value_binop (enum tree_code, tree, tree, tree); 487 static void bit_value_binop_1 (enum tree_code, tree, double_int *, double_int *, 488 tree, double_int, double_int, 489 tree, double_int, double_int); 490 491 /* Return a double_int that can be used for bitwise simplifications 492 from VAL. */ 493 494 static double_int 495 value_to_double_int (prop_value_t val) 496 { 497 if (val.value 498 && TREE_CODE (val.value) == INTEGER_CST) 499 return tree_to_double_int (val.value); 500 else 501 return double_int_zero; 502 } 503 504 /* Return the value for the address expression EXPR based on alignment 505 information. */ 506 507 static prop_value_t 508 get_value_from_alignment (tree expr) 509 { 510 tree type = TREE_TYPE (expr); 511 prop_value_t val; 512 unsigned HOST_WIDE_INT bitpos; 513 unsigned int align; 514 515 gcc_assert (TREE_CODE (expr) == ADDR_EXPR); 516 517 align = get_object_alignment_1 (TREE_OPERAND (expr, 0), &bitpos); 518 val.mask 519 = double_int_and_not (POINTER_TYPE_P (type) || TYPE_UNSIGNED (type) 520 ? double_int_mask (TYPE_PRECISION (type)) 521 : double_int_minus_one, 522 uhwi_to_double_int (align / BITS_PER_UNIT - 1)); 523 val.lattice_val = double_int_minus_one_p (val.mask) ? VARYING : CONSTANT; 524 if (val.lattice_val == CONSTANT) 525 val.value 526 = double_int_to_tree (type, uhwi_to_double_int (bitpos / BITS_PER_UNIT)); 527 else 528 val.value = NULL_TREE; 529 530 return val; 531 } 532 533 /* Return the value for the tree operand EXPR. If FOR_BITS_P is true 534 return constant bits extracted from alignment information for 535 invariant addresses. */ 536 537 static prop_value_t 538 get_value_for_expr (tree expr, bool for_bits_p) 539 { 540 prop_value_t val; 541 542 if (TREE_CODE (expr) == SSA_NAME) 543 { 544 val = *get_value (expr); 545 if (for_bits_p 546 && val.lattice_val == CONSTANT 547 && TREE_CODE (val.value) == ADDR_EXPR) 548 val = get_value_from_alignment (val.value); 549 } 550 else if (is_gimple_min_invariant (expr) 551 && (!for_bits_p || TREE_CODE (expr) != ADDR_EXPR)) 552 { 553 val.lattice_val = CONSTANT; 554 val.value = expr; 555 val.mask = double_int_zero; 556 canonicalize_float_value (&val); 557 } 558 else if (TREE_CODE (expr) == ADDR_EXPR) 559 val = get_value_from_alignment (expr); 560 else 561 { 562 val.lattice_val = VARYING; 563 val.mask = double_int_minus_one; 564 val.value = NULL_TREE; 565 } 566 return val; 567 } 568 569 /* Return the likely CCP lattice value for STMT. 570 571 If STMT has no operands, then return CONSTANT. 572 573 Else if undefinedness of operands of STMT cause its value to be 574 undefined, then return UNDEFINED. 575 576 Else if any operands of STMT are constants, then return CONSTANT. 577 578 Else return VARYING. */ 579 580 static ccp_lattice_t 581 likely_value (gimple stmt) 582 { 583 bool has_constant_operand, has_undefined_operand, all_undefined_operands; 584 tree use; 585 ssa_op_iter iter; 586 unsigned i; 587 588 enum gimple_code code = gimple_code (stmt); 589 590 /* This function appears to be called only for assignments, calls, 591 conditionals, and switches, due to the logic in visit_stmt. */ 592 gcc_assert (code == GIMPLE_ASSIGN 593 || code == GIMPLE_CALL 594 || code == GIMPLE_COND 595 || code == GIMPLE_SWITCH); 596 597 /* If the statement has volatile operands, it won't fold to a 598 constant value. */ 599 if (gimple_has_volatile_ops (stmt)) 600 return VARYING; 601 602 /* Arrive here for more complex cases. */ 603 has_constant_operand = false; 604 has_undefined_operand = false; 605 all_undefined_operands = true; 606 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) 607 { 608 prop_value_t *val = get_value (use); 609 610 if (val->lattice_val == UNDEFINED) 611 has_undefined_operand = true; 612 else 613 all_undefined_operands = false; 614 615 if (val->lattice_val == CONSTANT) 616 has_constant_operand = true; 617 } 618 619 /* There may be constants in regular rhs operands. For calls we 620 have to ignore lhs, fndecl and static chain, otherwise only 621 the lhs. */ 622 for (i = (is_gimple_call (stmt) ? 2 : 0) + gimple_has_lhs (stmt); 623 i < gimple_num_ops (stmt); ++i) 624 { 625 tree op = gimple_op (stmt, i); 626 if (!op || TREE_CODE (op) == SSA_NAME) 627 continue; 628 if (is_gimple_min_invariant (op)) 629 has_constant_operand = true; 630 } 631 632 if (has_constant_operand) 633 all_undefined_operands = false; 634 635 /* If the operation combines operands like COMPLEX_EXPR make sure to 636 not mark the result UNDEFINED if only one part of the result is 637 undefined. */ 638 if (has_undefined_operand && all_undefined_operands) 639 return UNDEFINED; 640 else if (code == GIMPLE_ASSIGN && has_undefined_operand) 641 { 642 switch (gimple_assign_rhs_code (stmt)) 643 { 644 /* Unary operators are handled with all_undefined_operands. */ 645 case PLUS_EXPR: 646 case MINUS_EXPR: 647 case POINTER_PLUS_EXPR: 648 /* Not MIN_EXPR, MAX_EXPR. One VARYING operand may be selected. 649 Not bitwise operators, one VARYING operand may specify the 650 result completely. Not logical operators for the same reason. 651 Not COMPLEX_EXPR as one VARYING operand makes the result partly 652 not UNDEFINED. Not *DIV_EXPR, comparisons and shifts because 653 the undefined operand may be promoted. */ 654 return UNDEFINED; 655 656 case ADDR_EXPR: 657 /* If any part of an address is UNDEFINED, like the index 658 of an ARRAY_EXPR, then treat the result as UNDEFINED. */ 659 return UNDEFINED; 660 661 default: 662 ; 663 } 664 } 665 /* If there was an UNDEFINED operand but the result may be not UNDEFINED 666 fall back to CONSTANT. During iteration UNDEFINED may still drop 667 to CONSTANT. */ 668 if (has_undefined_operand) 669 return CONSTANT; 670 671 /* We do not consider virtual operands here -- load from read-only 672 memory may have only VARYING virtual operands, but still be 673 constant. */ 674 if (has_constant_operand 675 || gimple_references_memory_p (stmt)) 676 return CONSTANT; 677 678 return VARYING; 679 } 680 681 /* Returns true if STMT cannot be constant. */ 682 683 static bool 684 surely_varying_stmt_p (gimple stmt) 685 { 686 /* If the statement has operands that we cannot handle, it cannot be 687 constant. */ 688 if (gimple_has_volatile_ops (stmt)) 689 return true; 690 691 /* If it is a call and does not return a value or is not a 692 builtin and not an indirect call, it is varying. */ 693 if (is_gimple_call (stmt)) 694 { 695 tree fndecl; 696 if (!gimple_call_lhs (stmt) 697 || ((fndecl = gimple_call_fndecl (stmt)) != NULL_TREE 698 && !DECL_BUILT_IN (fndecl))) 699 return true; 700 } 701 702 /* Any other store operation is not interesting. */ 703 else if (gimple_vdef (stmt)) 704 return true; 705 706 /* Anything other than assignments and conditional jumps are not 707 interesting for CCP. */ 708 if (gimple_code (stmt) != GIMPLE_ASSIGN 709 && gimple_code (stmt) != GIMPLE_COND 710 && gimple_code (stmt) != GIMPLE_SWITCH 711 && gimple_code (stmt) != GIMPLE_CALL) 712 return true; 713 714 return false; 715 } 716 717 /* Initialize local data structures for CCP. */ 718 719 static void 720 ccp_initialize (void) 721 { 722 basic_block bb; 723 724 const_val = XCNEWVEC (prop_value_t, num_ssa_names); 725 726 /* Initialize simulation flags for PHI nodes and statements. */ 727 FOR_EACH_BB (bb) 728 { 729 gimple_stmt_iterator i; 730 731 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i)) 732 { 733 gimple stmt = gsi_stmt (i); 734 bool is_varying; 735 736 /* If the statement is a control insn, then we do not 737 want to avoid simulating the statement once. Failure 738 to do so means that those edges will never get added. */ 739 if (stmt_ends_bb_p (stmt)) 740 is_varying = false; 741 else 742 is_varying = surely_varying_stmt_p (stmt); 743 744 if (is_varying) 745 { 746 tree def; 747 ssa_op_iter iter; 748 749 /* If the statement will not produce a constant, mark 750 all its outputs VARYING. */ 751 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 752 set_value_varying (def); 753 } 754 prop_set_simulate_again (stmt, !is_varying); 755 } 756 } 757 758 /* Now process PHI nodes. We never clear the simulate_again flag on 759 phi nodes, since we do not know which edges are executable yet, 760 except for phi nodes for virtual operands when we do not do store ccp. */ 761 FOR_EACH_BB (bb) 762 { 763 gimple_stmt_iterator i; 764 765 for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i)) 766 { 767 gimple phi = gsi_stmt (i); 768 769 if (!is_gimple_reg (gimple_phi_result (phi))) 770 prop_set_simulate_again (phi, false); 771 else 772 prop_set_simulate_again (phi, true); 773 } 774 } 775 } 776 777 /* Debug count support. Reset the values of ssa names 778 VARYING when the total number ssa names analyzed is 779 beyond the debug count specified. */ 780 781 static void 782 do_dbg_cnt (void) 783 { 784 unsigned i; 785 for (i = 0; i < num_ssa_names; i++) 786 { 787 if (!dbg_cnt (ccp)) 788 { 789 const_val[i].lattice_val = VARYING; 790 const_val[i].mask = double_int_minus_one; 791 const_val[i].value = NULL_TREE; 792 } 793 } 794 } 795 796 797 /* Do final substitution of propagated values, cleanup the flowgraph and 798 free allocated storage. 799 800 Return TRUE when something was optimized. */ 801 802 static bool 803 ccp_finalize (void) 804 { 805 bool something_changed; 806 unsigned i; 807 808 do_dbg_cnt (); 809 810 /* Derive alignment and misalignment information from partially 811 constant pointers in the lattice. */ 812 for (i = 1; i < num_ssa_names; ++i) 813 { 814 tree name = ssa_name (i); 815 prop_value_t *val; 816 struct ptr_info_def *pi; 817 unsigned int tem, align; 818 819 if (!name 820 || !POINTER_TYPE_P (TREE_TYPE (name))) 821 continue; 822 823 val = get_value (name); 824 if (val->lattice_val != CONSTANT 825 || TREE_CODE (val->value) != INTEGER_CST) 826 continue; 827 828 /* Trailing constant bits specify the alignment, trailing value 829 bits the misalignment. */ 830 tem = val->mask.low; 831 align = (tem & -tem); 832 if (align == 1) 833 continue; 834 835 pi = get_ptr_info (name); 836 pi->align = align; 837 pi->misalign = TREE_INT_CST_LOW (val->value) & (align - 1); 838 } 839 840 /* Perform substitutions based on the known constant values. */ 841 something_changed = substitute_and_fold (get_constant_value, 842 ccp_fold_stmt, true); 843 844 free (const_val); 845 const_val = NULL; 846 return something_changed;; 847 } 848 849 850 /* Compute the meet operator between *VAL1 and *VAL2. Store the result 851 in VAL1. 852 853 any M UNDEFINED = any 854 any M VARYING = VARYING 855 Ci M Cj = Ci if (i == j) 856 Ci M Cj = VARYING if (i != j) 857 */ 858 859 static void 860 ccp_lattice_meet (prop_value_t *val1, prop_value_t *val2) 861 { 862 if (val1->lattice_val == UNDEFINED) 863 { 864 /* UNDEFINED M any = any */ 865 *val1 = *val2; 866 } 867 else if (val2->lattice_val == UNDEFINED) 868 { 869 /* any M UNDEFINED = any 870 Nothing to do. VAL1 already contains the value we want. */ 871 ; 872 } 873 else if (val1->lattice_val == VARYING 874 || val2->lattice_val == VARYING) 875 { 876 /* any M VARYING = VARYING. */ 877 val1->lattice_val = VARYING; 878 val1->mask = double_int_minus_one; 879 val1->value = NULL_TREE; 880 } 881 else if (val1->lattice_val == CONSTANT 882 && val2->lattice_val == CONSTANT 883 && TREE_CODE (val1->value) == INTEGER_CST 884 && TREE_CODE (val2->value) == INTEGER_CST) 885 { 886 /* Ci M Cj = Ci if (i == j) 887 Ci M Cj = VARYING if (i != j) 888 889 For INTEGER_CSTs mask unequal bits. If no equal bits remain, 890 drop to varying. */ 891 val1->mask 892 = double_int_ior (double_int_ior (val1->mask, 893 val2->mask), 894 double_int_xor (tree_to_double_int (val1->value), 895 tree_to_double_int (val2->value))); 896 if (double_int_minus_one_p (val1->mask)) 897 { 898 val1->lattice_val = VARYING; 899 val1->value = NULL_TREE; 900 } 901 } 902 else if (val1->lattice_val == CONSTANT 903 && val2->lattice_val == CONSTANT 904 && simple_cst_equal (val1->value, val2->value) == 1) 905 { 906 /* Ci M Cj = Ci if (i == j) 907 Ci M Cj = VARYING if (i != j) 908 909 VAL1 already contains the value we want for equivalent values. */ 910 } 911 else if (val1->lattice_val == CONSTANT 912 && val2->lattice_val == CONSTANT 913 && (TREE_CODE (val1->value) == ADDR_EXPR 914 || TREE_CODE (val2->value) == ADDR_EXPR)) 915 { 916 /* When not equal addresses are involved try meeting for 917 alignment. */ 918 prop_value_t tem = *val2; 919 if (TREE_CODE (val1->value) == ADDR_EXPR) 920 *val1 = get_value_for_expr (val1->value, true); 921 if (TREE_CODE (val2->value) == ADDR_EXPR) 922 tem = get_value_for_expr (val2->value, true); 923 ccp_lattice_meet (val1, &tem); 924 } 925 else 926 { 927 /* Any other combination is VARYING. */ 928 val1->lattice_val = VARYING; 929 val1->mask = double_int_minus_one; 930 val1->value = NULL_TREE; 931 } 932 } 933 934 935 /* Loop through the PHI_NODE's parameters for BLOCK and compare their 936 lattice values to determine PHI_NODE's lattice value. The value of a 937 PHI node is determined calling ccp_lattice_meet with all the arguments 938 of the PHI node that are incoming via executable edges. */ 939 940 static enum ssa_prop_result 941 ccp_visit_phi_node (gimple phi) 942 { 943 unsigned i; 944 prop_value_t *old_val, new_val; 945 946 if (dump_file && (dump_flags & TDF_DETAILS)) 947 { 948 fprintf (dump_file, "\nVisiting PHI node: "); 949 print_gimple_stmt (dump_file, phi, 0, dump_flags); 950 } 951 952 old_val = get_value (gimple_phi_result (phi)); 953 switch (old_val->lattice_val) 954 { 955 case VARYING: 956 return SSA_PROP_VARYING; 957 958 case CONSTANT: 959 new_val = *old_val; 960 break; 961 962 case UNDEFINED: 963 new_val.lattice_val = UNDEFINED; 964 new_val.value = NULL_TREE; 965 break; 966 967 default: 968 gcc_unreachable (); 969 } 970 971 for (i = 0; i < gimple_phi_num_args (phi); i++) 972 { 973 /* Compute the meet operator over all the PHI arguments flowing 974 through executable edges. */ 975 edge e = gimple_phi_arg_edge (phi, i); 976 977 if (dump_file && (dump_flags & TDF_DETAILS)) 978 { 979 fprintf (dump_file, 980 "\n Argument #%d (%d -> %d %sexecutable)\n", 981 i, e->src->index, e->dest->index, 982 (e->flags & EDGE_EXECUTABLE) ? "" : "not "); 983 } 984 985 /* If the incoming edge is executable, Compute the meet operator for 986 the existing value of the PHI node and the current PHI argument. */ 987 if (e->flags & EDGE_EXECUTABLE) 988 { 989 tree arg = gimple_phi_arg (phi, i)->def; 990 prop_value_t arg_val = get_value_for_expr (arg, false); 991 992 ccp_lattice_meet (&new_val, &arg_val); 993 994 if (dump_file && (dump_flags & TDF_DETAILS)) 995 { 996 fprintf (dump_file, "\t"); 997 print_generic_expr (dump_file, arg, dump_flags); 998 dump_lattice_value (dump_file, "\tValue: ", arg_val); 999 fprintf (dump_file, "\n"); 1000 } 1001 1002 if (new_val.lattice_val == VARYING) 1003 break; 1004 } 1005 } 1006 1007 if (dump_file && (dump_flags & TDF_DETAILS)) 1008 { 1009 dump_lattice_value (dump_file, "\n PHI node value: ", new_val); 1010 fprintf (dump_file, "\n\n"); 1011 } 1012 1013 /* Make the transition to the new value. */ 1014 if (set_lattice_value (gimple_phi_result (phi), new_val)) 1015 { 1016 if (new_val.lattice_val == VARYING) 1017 return SSA_PROP_VARYING; 1018 else 1019 return SSA_PROP_INTERESTING; 1020 } 1021 else 1022 return SSA_PROP_NOT_INTERESTING; 1023 } 1024 1025 /* Return the constant value for OP or OP otherwise. */ 1026 1027 static tree 1028 valueize_op (tree op) 1029 { 1030 if (TREE_CODE (op) == SSA_NAME) 1031 { 1032 tree tem = get_constant_value (op); 1033 if (tem) 1034 return tem; 1035 } 1036 return op; 1037 } 1038 1039 /* CCP specific front-end to the non-destructive constant folding 1040 routines. 1041 1042 Attempt to simplify the RHS of STMT knowing that one or more 1043 operands are constants. 1044 1045 If simplification is possible, return the simplified RHS, 1046 otherwise return the original RHS or NULL_TREE. */ 1047 1048 static tree 1049 ccp_fold (gimple stmt) 1050 { 1051 location_t loc = gimple_location (stmt); 1052 switch (gimple_code (stmt)) 1053 { 1054 case GIMPLE_COND: 1055 { 1056 /* Handle comparison operators that can appear in GIMPLE form. */ 1057 tree op0 = valueize_op (gimple_cond_lhs (stmt)); 1058 tree op1 = valueize_op (gimple_cond_rhs (stmt)); 1059 enum tree_code code = gimple_cond_code (stmt); 1060 return fold_binary_loc (loc, code, boolean_type_node, op0, op1); 1061 } 1062 1063 case GIMPLE_SWITCH: 1064 { 1065 /* Return the constant switch index. */ 1066 return valueize_op (gimple_switch_index (stmt)); 1067 } 1068 1069 case GIMPLE_ASSIGN: 1070 case GIMPLE_CALL: 1071 return gimple_fold_stmt_to_constant_1 (stmt, valueize_op); 1072 1073 default: 1074 gcc_unreachable (); 1075 } 1076 } 1077 1078 /* Apply the operation CODE in type TYPE to the value, mask pair 1079 RVAL and RMASK representing a value of type RTYPE and set 1080 the value, mask pair *VAL and *MASK to the result. */ 1081 1082 static void 1083 bit_value_unop_1 (enum tree_code code, tree type, 1084 double_int *val, double_int *mask, 1085 tree rtype, double_int rval, double_int rmask) 1086 { 1087 switch (code) 1088 { 1089 case BIT_NOT_EXPR: 1090 *mask = rmask; 1091 *val = double_int_not (rval); 1092 break; 1093 1094 case NEGATE_EXPR: 1095 { 1096 double_int temv, temm; 1097 /* Return ~rval + 1. */ 1098 bit_value_unop_1 (BIT_NOT_EXPR, type, &temv, &temm, type, rval, rmask); 1099 bit_value_binop_1 (PLUS_EXPR, type, val, mask, 1100 type, temv, temm, 1101 type, double_int_one, double_int_zero); 1102 break; 1103 } 1104 1105 CASE_CONVERT: 1106 { 1107 bool uns; 1108 1109 /* First extend mask and value according to the original type. */ 1110 uns = (TREE_CODE (rtype) == INTEGER_TYPE && TYPE_IS_SIZETYPE (rtype) 1111 ? 0 : TYPE_UNSIGNED (rtype)); 1112 *mask = double_int_ext (rmask, TYPE_PRECISION (rtype), uns); 1113 *val = double_int_ext (rval, TYPE_PRECISION (rtype), uns); 1114 1115 /* Then extend mask and value according to the target type. */ 1116 uns = (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type) 1117 ? 0 : TYPE_UNSIGNED (type)); 1118 *mask = double_int_ext (*mask, TYPE_PRECISION (type), uns); 1119 *val = double_int_ext (*val, TYPE_PRECISION (type), uns); 1120 break; 1121 } 1122 1123 default: 1124 *mask = double_int_minus_one; 1125 break; 1126 } 1127 } 1128 1129 /* Apply the operation CODE in type TYPE to the value, mask pairs 1130 R1VAL, R1MASK and R2VAL, R2MASK representing a values of type R1TYPE 1131 and R2TYPE and set the value, mask pair *VAL and *MASK to the result. */ 1132 1133 static void 1134 bit_value_binop_1 (enum tree_code code, tree type, 1135 double_int *val, double_int *mask, 1136 tree r1type, double_int r1val, double_int r1mask, 1137 tree r2type, double_int r2val, double_int r2mask) 1138 { 1139 bool uns = (TREE_CODE (type) == INTEGER_TYPE 1140 && TYPE_IS_SIZETYPE (type) ? 0 : TYPE_UNSIGNED (type)); 1141 /* Assume we'll get a constant result. Use an initial varying value, 1142 we fall back to varying in the end if necessary. */ 1143 *mask = double_int_minus_one; 1144 switch (code) 1145 { 1146 case BIT_AND_EXPR: 1147 /* The mask is constant where there is a known not 1148 set bit, (m1 | m2) & ((v1 | m1) & (v2 | m2)) */ 1149 *mask = double_int_and (double_int_ior (r1mask, r2mask), 1150 double_int_and (double_int_ior (r1val, r1mask), 1151 double_int_ior (r2val, r2mask))); 1152 *val = double_int_and (r1val, r2val); 1153 break; 1154 1155 case BIT_IOR_EXPR: 1156 /* The mask is constant where there is a known 1157 set bit, (m1 | m2) & ~((v1 & ~m1) | (v2 & ~m2)). */ 1158 *mask = double_int_and_not 1159 (double_int_ior (r1mask, r2mask), 1160 double_int_ior (double_int_and_not (r1val, r1mask), 1161 double_int_and_not (r2val, r2mask))); 1162 *val = double_int_ior (r1val, r2val); 1163 break; 1164 1165 case BIT_XOR_EXPR: 1166 /* m1 | m2 */ 1167 *mask = double_int_ior (r1mask, r2mask); 1168 *val = double_int_xor (r1val, r2val); 1169 break; 1170 1171 case LROTATE_EXPR: 1172 case RROTATE_EXPR: 1173 if (double_int_zero_p (r2mask)) 1174 { 1175 HOST_WIDE_INT shift = r2val.low; 1176 if (code == RROTATE_EXPR) 1177 shift = -shift; 1178 *mask = double_int_lrotate (r1mask, shift, TYPE_PRECISION (type)); 1179 *val = double_int_lrotate (r1val, shift, TYPE_PRECISION (type)); 1180 } 1181 break; 1182 1183 case LSHIFT_EXPR: 1184 case RSHIFT_EXPR: 1185 /* ??? We can handle partially known shift counts if we know 1186 its sign. That way we can tell that (x << (y | 8)) & 255 1187 is zero. */ 1188 if (double_int_zero_p (r2mask)) 1189 { 1190 HOST_WIDE_INT shift = r2val.low; 1191 if (code == RSHIFT_EXPR) 1192 shift = -shift; 1193 /* We need to know if we are doing a left or a right shift 1194 to properly shift in zeros for left shift and unsigned 1195 right shifts and the sign bit for signed right shifts. 1196 For signed right shifts we shift in varying in case 1197 the sign bit was varying. */ 1198 if (shift > 0) 1199 { 1200 *mask = double_int_lshift (r1mask, shift, 1201 TYPE_PRECISION (type), false); 1202 *val = double_int_lshift (r1val, shift, 1203 TYPE_PRECISION (type), false); 1204 } 1205 else if (shift < 0) 1206 { 1207 /* ??? We can have sizetype related inconsistencies in 1208 the IL. */ 1209 if ((TREE_CODE (r1type) == INTEGER_TYPE 1210 && (TYPE_IS_SIZETYPE (r1type) 1211 ? 0 : TYPE_UNSIGNED (r1type))) != uns) 1212 break; 1213 1214 shift = -shift; 1215 *mask = double_int_rshift (r1mask, shift, 1216 TYPE_PRECISION (type), !uns); 1217 *val = double_int_rshift (r1val, shift, 1218 TYPE_PRECISION (type), !uns); 1219 } 1220 else 1221 { 1222 *mask = r1mask; 1223 *val = r1val; 1224 } 1225 } 1226 break; 1227 1228 case PLUS_EXPR: 1229 case POINTER_PLUS_EXPR: 1230 { 1231 double_int lo, hi; 1232 /* Do the addition with unknown bits set to zero, to give carry-ins of 1233 zero wherever possible. */ 1234 lo = double_int_add (double_int_and_not (r1val, r1mask), 1235 double_int_and_not (r2val, r2mask)); 1236 lo = double_int_ext (lo, TYPE_PRECISION (type), uns); 1237 /* Do the addition with unknown bits set to one, to give carry-ins of 1238 one wherever possible. */ 1239 hi = double_int_add (double_int_ior (r1val, r1mask), 1240 double_int_ior (r2val, r2mask)); 1241 hi = double_int_ext (hi, TYPE_PRECISION (type), uns); 1242 /* Each bit in the result is known if (a) the corresponding bits in 1243 both inputs are known, and (b) the carry-in to that bit position 1244 is known. We can check condition (b) by seeing if we got the same 1245 result with minimised carries as with maximised carries. */ 1246 *mask = double_int_ior (double_int_ior (r1mask, r2mask), 1247 double_int_xor (lo, hi)); 1248 *mask = double_int_ext (*mask, TYPE_PRECISION (type), uns); 1249 /* It shouldn't matter whether we choose lo or hi here. */ 1250 *val = lo; 1251 break; 1252 } 1253 1254 case MINUS_EXPR: 1255 { 1256 double_int temv, temm; 1257 bit_value_unop_1 (NEGATE_EXPR, r2type, &temv, &temm, 1258 r2type, r2val, r2mask); 1259 bit_value_binop_1 (PLUS_EXPR, type, val, mask, 1260 r1type, r1val, r1mask, 1261 r2type, temv, temm); 1262 break; 1263 } 1264 1265 case MULT_EXPR: 1266 { 1267 /* Just track trailing zeros in both operands and transfer 1268 them to the other. */ 1269 int r1tz = double_int_ctz (double_int_ior (r1val, r1mask)); 1270 int r2tz = double_int_ctz (double_int_ior (r2val, r2mask)); 1271 if (r1tz + r2tz >= HOST_BITS_PER_DOUBLE_INT) 1272 { 1273 *mask = double_int_zero; 1274 *val = double_int_zero; 1275 } 1276 else if (r1tz + r2tz > 0) 1277 { 1278 *mask = double_int_not (double_int_mask (r1tz + r2tz)); 1279 *mask = double_int_ext (*mask, TYPE_PRECISION (type), uns); 1280 *val = double_int_zero; 1281 } 1282 break; 1283 } 1284 1285 case EQ_EXPR: 1286 case NE_EXPR: 1287 { 1288 double_int m = double_int_ior (r1mask, r2mask); 1289 if (!double_int_equal_p (double_int_and_not (r1val, m), 1290 double_int_and_not (r2val, m))) 1291 { 1292 *mask = double_int_zero; 1293 *val = ((code == EQ_EXPR) ? double_int_zero : double_int_one); 1294 } 1295 else 1296 { 1297 /* We know the result of a comparison is always one or zero. */ 1298 *mask = double_int_one; 1299 *val = double_int_zero; 1300 } 1301 break; 1302 } 1303 1304 case GE_EXPR: 1305 case GT_EXPR: 1306 { 1307 double_int tem = r1val; 1308 r1val = r2val; 1309 r2val = tem; 1310 tem = r1mask; 1311 r1mask = r2mask; 1312 r2mask = tem; 1313 code = swap_tree_comparison (code); 1314 } 1315 /* Fallthru. */ 1316 case LT_EXPR: 1317 case LE_EXPR: 1318 { 1319 int minmax, maxmin; 1320 /* If the most significant bits are not known we know nothing. */ 1321 if (double_int_negative_p (r1mask) || double_int_negative_p (r2mask)) 1322 break; 1323 1324 /* For comparisons the signedness is in the comparison operands. */ 1325 uns = (TREE_CODE (r1type) == INTEGER_TYPE 1326 && TYPE_IS_SIZETYPE (r1type) ? 0 : TYPE_UNSIGNED (r1type)); 1327 /* ??? We can have sizetype related inconsistencies in the IL. */ 1328 if ((TREE_CODE (r2type) == INTEGER_TYPE 1329 && TYPE_IS_SIZETYPE (r2type) ? 0 : TYPE_UNSIGNED (r2type)) != uns) 1330 break; 1331 1332 /* If we know the most significant bits we know the values 1333 value ranges by means of treating varying bits as zero 1334 or one. Do a cross comparison of the max/min pairs. */ 1335 maxmin = double_int_cmp (double_int_ior (r1val, r1mask), 1336 double_int_and_not (r2val, r2mask), uns); 1337 minmax = double_int_cmp (double_int_and_not (r1val, r1mask), 1338 double_int_ior (r2val, r2mask), uns); 1339 if (maxmin < 0) /* r1 is less than r2. */ 1340 { 1341 *mask = double_int_zero; 1342 *val = double_int_one; 1343 } 1344 else if (minmax > 0) /* r1 is not less or equal to r2. */ 1345 { 1346 *mask = double_int_zero; 1347 *val = double_int_zero; 1348 } 1349 else if (maxmin == minmax) /* r1 and r2 are equal. */ 1350 { 1351 /* This probably should never happen as we'd have 1352 folded the thing during fully constant value folding. */ 1353 *mask = double_int_zero; 1354 *val = (code == LE_EXPR ? double_int_one : double_int_zero); 1355 } 1356 else 1357 { 1358 /* We know the result of a comparison is always one or zero. */ 1359 *mask = double_int_one; 1360 *val = double_int_zero; 1361 } 1362 break; 1363 } 1364 1365 default:; 1366 } 1367 } 1368 1369 /* Return the propagation value when applying the operation CODE to 1370 the value RHS yielding type TYPE. */ 1371 1372 static prop_value_t 1373 bit_value_unop (enum tree_code code, tree type, tree rhs) 1374 { 1375 prop_value_t rval = get_value_for_expr (rhs, true); 1376 double_int value, mask; 1377 prop_value_t val; 1378 1379 if (rval.lattice_val == UNDEFINED) 1380 return rval; 1381 1382 gcc_assert ((rval.lattice_val == CONSTANT 1383 && TREE_CODE (rval.value) == INTEGER_CST) 1384 || double_int_minus_one_p (rval.mask)); 1385 bit_value_unop_1 (code, type, &value, &mask, 1386 TREE_TYPE (rhs), value_to_double_int (rval), rval.mask); 1387 if (!double_int_minus_one_p (mask)) 1388 { 1389 val.lattice_val = CONSTANT; 1390 val.mask = mask; 1391 /* ??? Delay building trees here. */ 1392 val.value = double_int_to_tree (type, value); 1393 } 1394 else 1395 { 1396 val.lattice_val = VARYING; 1397 val.value = NULL_TREE; 1398 val.mask = double_int_minus_one; 1399 } 1400 return val; 1401 } 1402 1403 /* Return the propagation value when applying the operation CODE to 1404 the values RHS1 and RHS2 yielding type TYPE. */ 1405 1406 static prop_value_t 1407 bit_value_binop (enum tree_code code, tree type, tree rhs1, tree rhs2) 1408 { 1409 prop_value_t r1val = get_value_for_expr (rhs1, true); 1410 prop_value_t r2val = get_value_for_expr (rhs2, true); 1411 double_int value, mask; 1412 prop_value_t val; 1413 1414 if (r1val.lattice_val == UNDEFINED 1415 || r2val.lattice_val == UNDEFINED) 1416 { 1417 val.lattice_val = VARYING; 1418 val.value = NULL_TREE; 1419 val.mask = double_int_minus_one; 1420 return val; 1421 } 1422 1423 gcc_assert ((r1val.lattice_val == CONSTANT 1424 && TREE_CODE (r1val.value) == INTEGER_CST) 1425 || double_int_minus_one_p (r1val.mask)); 1426 gcc_assert ((r2val.lattice_val == CONSTANT 1427 && TREE_CODE (r2val.value) == INTEGER_CST) 1428 || double_int_minus_one_p (r2val.mask)); 1429 bit_value_binop_1 (code, type, &value, &mask, 1430 TREE_TYPE (rhs1), value_to_double_int (r1val), r1val.mask, 1431 TREE_TYPE (rhs2), value_to_double_int (r2val), r2val.mask); 1432 if (!double_int_minus_one_p (mask)) 1433 { 1434 val.lattice_val = CONSTANT; 1435 val.mask = mask; 1436 /* ??? Delay building trees here. */ 1437 val.value = double_int_to_tree (type, value); 1438 } 1439 else 1440 { 1441 val.lattice_val = VARYING; 1442 val.value = NULL_TREE; 1443 val.mask = double_int_minus_one; 1444 } 1445 return val; 1446 } 1447 1448 /* Return the propagation value when applying __builtin_assume_aligned to 1449 its arguments. */ 1450 1451 static prop_value_t 1452 bit_value_assume_aligned (gimple stmt) 1453 { 1454 tree ptr = gimple_call_arg (stmt, 0), align, misalign = NULL_TREE; 1455 tree type = TREE_TYPE (ptr); 1456 unsigned HOST_WIDE_INT aligni, misaligni = 0; 1457 prop_value_t ptrval = get_value_for_expr (ptr, true); 1458 prop_value_t alignval; 1459 double_int value, mask; 1460 prop_value_t val; 1461 if (ptrval.lattice_val == UNDEFINED) 1462 return ptrval; 1463 gcc_assert ((ptrval.lattice_val == CONSTANT 1464 && TREE_CODE (ptrval.value) == INTEGER_CST) 1465 || double_int_minus_one_p (ptrval.mask)); 1466 align = gimple_call_arg (stmt, 1); 1467 if (!host_integerp (align, 1)) 1468 return ptrval; 1469 aligni = tree_low_cst (align, 1); 1470 if (aligni <= 1 1471 || (aligni & (aligni - 1)) != 0) 1472 return ptrval; 1473 if (gimple_call_num_args (stmt) > 2) 1474 { 1475 misalign = gimple_call_arg (stmt, 2); 1476 if (!host_integerp (misalign, 1)) 1477 return ptrval; 1478 misaligni = tree_low_cst (misalign, 1); 1479 if (misaligni >= aligni) 1480 return ptrval; 1481 } 1482 align = build_int_cst_type (type, -aligni); 1483 alignval = get_value_for_expr (align, true); 1484 bit_value_binop_1 (BIT_AND_EXPR, type, &value, &mask, 1485 type, value_to_double_int (ptrval), ptrval.mask, 1486 type, value_to_double_int (alignval), alignval.mask); 1487 if (!double_int_minus_one_p (mask)) 1488 { 1489 val.lattice_val = CONSTANT; 1490 val.mask = mask; 1491 gcc_assert ((mask.low & (aligni - 1)) == 0); 1492 gcc_assert ((value.low & (aligni - 1)) == 0); 1493 value.low |= misaligni; 1494 /* ??? Delay building trees here. */ 1495 val.value = double_int_to_tree (type, value); 1496 } 1497 else 1498 { 1499 val.lattice_val = VARYING; 1500 val.value = NULL_TREE; 1501 val.mask = double_int_minus_one; 1502 } 1503 return val; 1504 } 1505 1506 /* Evaluate statement STMT. 1507 Valid only for assignments, calls, conditionals, and switches. */ 1508 1509 static prop_value_t 1510 evaluate_stmt (gimple stmt) 1511 { 1512 prop_value_t val; 1513 tree simplified = NULL_TREE; 1514 ccp_lattice_t likelyvalue = likely_value (stmt); 1515 bool is_constant = false; 1516 unsigned int align; 1517 1518 if (dump_file && (dump_flags & TDF_DETAILS)) 1519 { 1520 fprintf (dump_file, "which is likely "); 1521 switch (likelyvalue) 1522 { 1523 case CONSTANT: 1524 fprintf (dump_file, "CONSTANT"); 1525 break; 1526 case UNDEFINED: 1527 fprintf (dump_file, "UNDEFINED"); 1528 break; 1529 case VARYING: 1530 fprintf (dump_file, "VARYING"); 1531 break; 1532 default:; 1533 } 1534 fprintf (dump_file, "\n"); 1535 } 1536 1537 /* If the statement is likely to have a CONSTANT result, then try 1538 to fold the statement to determine the constant value. */ 1539 /* FIXME. This is the only place that we call ccp_fold. 1540 Since likely_value never returns CONSTANT for calls, we will 1541 not attempt to fold them, including builtins that may profit. */ 1542 if (likelyvalue == CONSTANT) 1543 { 1544 fold_defer_overflow_warnings (); 1545 simplified = ccp_fold (stmt); 1546 is_constant = simplified && is_gimple_min_invariant (simplified); 1547 fold_undefer_overflow_warnings (is_constant, stmt, 0); 1548 if (is_constant) 1549 { 1550 /* The statement produced a constant value. */ 1551 val.lattice_val = CONSTANT; 1552 val.value = simplified; 1553 val.mask = double_int_zero; 1554 } 1555 } 1556 /* If the statement is likely to have a VARYING result, then do not 1557 bother folding the statement. */ 1558 else if (likelyvalue == VARYING) 1559 { 1560 enum gimple_code code = gimple_code (stmt); 1561 if (code == GIMPLE_ASSIGN) 1562 { 1563 enum tree_code subcode = gimple_assign_rhs_code (stmt); 1564 1565 /* Other cases cannot satisfy is_gimple_min_invariant 1566 without folding. */ 1567 if (get_gimple_rhs_class (subcode) == GIMPLE_SINGLE_RHS) 1568 simplified = gimple_assign_rhs1 (stmt); 1569 } 1570 else if (code == GIMPLE_SWITCH) 1571 simplified = gimple_switch_index (stmt); 1572 else 1573 /* These cannot satisfy is_gimple_min_invariant without folding. */ 1574 gcc_assert (code == GIMPLE_CALL || code == GIMPLE_COND); 1575 is_constant = simplified && is_gimple_min_invariant (simplified); 1576 if (is_constant) 1577 { 1578 /* The statement produced a constant value. */ 1579 val.lattice_val = CONSTANT; 1580 val.value = simplified; 1581 val.mask = double_int_zero; 1582 } 1583 } 1584 1585 /* Resort to simplification for bitwise tracking. */ 1586 if (flag_tree_bit_ccp 1587 && (likelyvalue == CONSTANT || is_gimple_call (stmt)) 1588 && !is_constant) 1589 { 1590 enum gimple_code code = gimple_code (stmt); 1591 val.lattice_val = VARYING; 1592 val.value = NULL_TREE; 1593 val.mask = double_int_minus_one; 1594 if (code == GIMPLE_ASSIGN) 1595 { 1596 enum tree_code subcode = gimple_assign_rhs_code (stmt); 1597 tree rhs1 = gimple_assign_rhs1 (stmt); 1598 switch (get_gimple_rhs_class (subcode)) 1599 { 1600 case GIMPLE_SINGLE_RHS: 1601 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)) 1602 || POINTER_TYPE_P (TREE_TYPE (rhs1))) 1603 val = get_value_for_expr (rhs1, true); 1604 break; 1605 1606 case GIMPLE_UNARY_RHS: 1607 if ((INTEGRAL_TYPE_P (TREE_TYPE (rhs1)) 1608 || POINTER_TYPE_P (TREE_TYPE (rhs1))) 1609 && (INTEGRAL_TYPE_P (gimple_expr_type (stmt)) 1610 || POINTER_TYPE_P (gimple_expr_type (stmt)))) 1611 val = bit_value_unop (subcode, gimple_expr_type (stmt), rhs1); 1612 break; 1613 1614 case GIMPLE_BINARY_RHS: 1615 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)) 1616 || POINTER_TYPE_P (TREE_TYPE (rhs1))) 1617 { 1618 tree lhs = gimple_assign_lhs (stmt); 1619 tree rhs2 = gimple_assign_rhs2 (stmt); 1620 val = bit_value_binop (subcode, 1621 TREE_TYPE (lhs), rhs1, rhs2); 1622 } 1623 break; 1624 1625 default:; 1626 } 1627 } 1628 else if (code == GIMPLE_COND) 1629 { 1630 enum tree_code code = gimple_cond_code (stmt); 1631 tree rhs1 = gimple_cond_lhs (stmt); 1632 tree rhs2 = gimple_cond_rhs (stmt); 1633 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)) 1634 || POINTER_TYPE_P (TREE_TYPE (rhs1))) 1635 val = bit_value_binop (code, TREE_TYPE (rhs1), rhs1, rhs2); 1636 } 1637 else if (gimple_call_builtin_class_p (stmt, BUILT_IN_NORMAL)) 1638 { 1639 tree fndecl = gimple_call_fndecl (stmt); 1640 switch (DECL_FUNCTION_CODE (fndecl)) 1641 { 1642 case BUILT_IN_MALLOC: 1643 case BUILT_IN_REALLOC: 1644 case BUILT_IN_CALLOC: 1645 case BUILT_IN_STRDUP: 1646 case BUILT_IN_STRNDUP: 1647 val.lattice_val = CONSTANT; 1648 val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0); 1649 val.mask = shwi_to_double_int 1650 (~(((HOST_WIDE_INT) MALLOC_ABI_ALIGNMENT) 1651 / BITS_PER_UNIT - 1)); 1652 break; 1653 1654 case BUILT_IN_ALLOCA: 1655 case BUILT_IN_ALLOCA_WITH_ALIGN: 1656 align = (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_ALLOCA_WITH_ALIGN 1657 ? TREE_INT_CST_LOW (gimple_call_arg (stmt, 1)) 1658 : BIGGEST_ALIGNMENT); 1659 val.lattice_val = CONSTANT; 1660 val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0); 1661 val.mask = shwi_to_double_int 1662 (~(((HOST_WIDE_INT) align) 1663 / BITS_PER_UNIT - 1)); 1664 break; 1665 1666 /* These builtins return their first argument, unmodified. */ 1667 case BUILT_IN_MEMCPY: 1668 case BUILT_IN_MEMMOVE: 1669 case BUILT_IN_MEMSET: 1670 case BUILT_IN_STRCPY: 1671 case BUILT_IN_STRNCPY: 1672 case BUILT_IN_MEMCPY_CHK: 1673 case BUILT_IN_MEMMOVE_CHK: 1674 case BUILT_IN_MEMSET_CHK: 1675 case BUILT_IN_STRCPY_CHK: 1676 case BUILT_IN_STRNCPY_CHK: 1677 val = get_value_for_expr (gimple_call_arg (stmt, 0), true); 1678 break; 1679 1680 case BUILT_IN_ASSUME_ALIGNED: 1681 val = bit_value_assume_aligned (stmt); 1682 break; 1683 1684 default:; 1685 } 1686 } 1687 is_constant = (val.lattice_val == CONSTANT); 1688 } 1689 1690 if (!is_constant) 1691 { 1692 /* The statement produced a nonconstant value. If the statement 1693 had UNDEFINED operands, then the result of the statement 1694 should be UNDEFINED. Otherwise, the statement is VARYING. */ 1695 if (likelyvalue == UNDEFINED) 1696 { 1697 val.lattice_val = likelyvalue; 1698 val.mask = double_int_zero; 1699 } 1700 else 1701 { 1702 val.lattice_val = VARYING; 1703 val.mask = double_int_minus_one; 1704 } 1705 1706 val.value = NULL_TREE; 1707 } 1708 1709 return val; 1710 } 1711 1712 /* Given a BUILT_IN_STACK_SAVE value SAVED_VAL, insert a clobber of VAR before 1713 each matching BUILT_IN_STACK_RESTORE. Mark visited phis in VISITED. */ 1714 1715 static void 1716 insert_clobber_before_stack_restore (tree saved_val, tree var, htab_t *visited) 1717 { 1718 gimple stmt, clobber_stmt; 1719 tree clobber; 1720 imm_use_iterator iter; 1721 gimple_stmt_iterator i; 1722 gimple *slot; 1723 1724 FOR_EACH_IMM_USE_STMT (stmt, iter, saved_val) 1725 if (gimple_call_builtin_p (stmt, BUILT_IN_STACK_RESTORE)) 1726 { 1727 clobber = build_constructor (TREE_TYPE (var), NULL); 1728 TREE_THIS_VOLATILE (clobber) = 1; 1729 clobber_stmt = gimple_build_assign (var, clobber); 1730 1731 i = gsi_for_stmt (stmt); 1732 gsi_insert_before (&i, clobber_stmt, GSI_SAME_STMT); 1733 } 1734 else if (gimple_code (stmt) == GIMPLE_PHI) 1735 { 1736 if (*visited == NULL) 1737 *visited = htab_create (10, htab_hash_pointer, htab_eq_pointer, NULL); 1738 1739 slot = (gimple *)htab_find_slot (*visited, stmt, INSERT); 1740 if (*slot != NULL) 1741 continue; 1742 1743 *slot = stmt; 1744 insert_clobber_before_stack_restore (gimple_phi_result (stmt), var, 1745 visited); 1746 } 1747 else 1748 gcc_assert (is_gimple_debug (stmt)); 1749 } 1750 1751 /* Advance the iterator to the previous non-debug gimple statement in the same 1752 or dominating basic block. */ 1753 1754 static inline void 1755 gsi_prev_dom_bb_nondebug (gimple_stmt_iterator *i) 1756 { 1757 basic_block dom; 1758 1759 gsi_prev_nondebug (i); 1760 while (gsi_end_p (*i)) 1761 { 1762 dom = get_immediate_dominator (CDI_DOMINATORS, i->bb); 1763 if (dom == NULL || dom == ENTRY_BLOCK_PTR) 1764 return; 1765 1766 *i = gsi_last_bb (dom); 1767 } 1768 } 1769 1770 /* Find a BUILT_IN_STACK_SAVE dominating gsi_stmt (I), and insert 1771 a clobber of VAR before each matching BUILT_IN_STACK_RESTORE. 1772 1773 It is possible that BUILT_IN_STACK_SAVE cannot be find in a dominator when a 1774 previous pass (such as DOM) duplicated it along multiple paths to a BB. In 1775 that case the function gives up without inserting the clobbers. */ 1776 1777 static void 1778 insert_clobbers_for_var (gimple_stmt_iterator i, tree var) 1779 { 1780 gimple stmt; 1781 tree saved_val; 1782 htab_t visited = NULL; 1783 1784 for (; !gsi_end_p (i); gsi_prev_dom_bb_nondebug (&i)) 1785 { 1786 stmt = gsi_stmt (i); 1787 1788 if (!gimple_call_builtin_p (stmt, BUILT_IN_STACK_SAVE)) 1789 continue; 1790 1791 saved_val = gimple_call_lhs (stmt); 1792 if (saved_val == NULL_TREE) 1793 continue; 1794 1795 insert_clobber_before_stack_restore (saved_val, var, &visited); 1796 break; 1797 } 1798 1799 if (visited != NULL) 1800 htab_delete (visited); 1801 } 1802 1803 /* Detects a __builtin_alloca_with_align with constant size argument. Declares 1804 fixed-size array and returns the address, if found, otherwise returns 1805 NULL_TREE. */ 1806 1807 static tree 1808 fold_builtin_alloca_with_align (gimple stmt) 1809 { 1810 unsigned HOST_WIDE_INT size, threshold, n_elem; 1811 tree lhs, arg, block, var, elem_type, array_type; 1812 1813 /* Get lhs. */ 1814 lhs = gimple_call_lhs (stmt); 1815 if (lhs == NULL_TREE) 1816 return NULL_TREE; 1817 1818 /* Detect constant argument. */ 1819 arg = get_constant_value (gimple_call_arg (stmt, 0)); 1820 if (arg == NULL_TREE 1821 || TREE_CODE (arg) != INTEGER_CST 1822 || !host_integerp (arg, 1)) 1823 return NULL_TREE; 1824 1825 size = TREE_INT_CST_LOW (arg); 1826 1827 /* Heuristic: don't fold large allocas. */ 1828 threshold = (unsigned HOST_WIDE_INT)PARAM_VALUE (PARAM_LARGE_STACK_FRAME); 1829 /* In case the alloca is located at function entry, it has the same lifetime 1830 as a declared array, so we allow a larger size. */ 1831 block = gimple_block (stmt); 1832 if (!(cfun->after_inlining 1833 && TREE_CODE (BLOCK_SUPERCONTEXT (block)) == FUNCTION_DECL)) 1834 threshold /= 10; 1835 if (size > threshold) 1836 return NULL_TREE; 1837 1838 /* Declare array. */ 1839 elem_type = build_nonstandard_integer_type (BITS_PER_UNIT, 1); 1840 n_elem = size * 8 / BITS_PER_UNIT; 1841 array_type = build_array_type_nelts (elem_type, n_elem); 1842 var = create_tmp_var (array_type, NULL); 1843 DECL_ALIGN (var) = TREE_INT_CST_LOW (gimple_call_arg (stmt, 1)); 1844 { 1845 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (lhs); 1846 if (pi != NULL && !pi->pt.anything) 1847 { 1848 bool singleton_p; 1849 unsigned uid; 1850 singleton_p = pt_solution_singleton_p (&pi->pt, &uid); 1851 gcc_assert (singleton_p); 1852 SET_DECL_PT_UID (var, uid); 1853 } 1854 } 1855 1856 /* Fold alloca to the address of the array. */ 1857 return fold_convert (TREE_TYPE (lhs), build_fold_addr_expr (var)); 1858 } 1859 1860 /* Fold the stmt at *GSI with CCP specific information that propagating 1861 and regular folding does not catch. */ 1862 1863 static bool 1864 ccp_fold_stmt (gimple_stmt_iterator *gsi) 1865 { 1866 gimple stmt = gsi_stmt (*gsi); 1867 1868 switch (gimple_code (stmt)) 1869 { 1870 case GIMPLE_COND: 1871 { 1872 prop_value_t val; 1873 /* Statement evaluation will handle type mismatches in constants 1874 more gracefully than the final propagation. This allows us to 1875 fold more conditionals here. */ 1876 val = evaluate_stmt (stmt); 1877 if (val.lattice_val != CONSTANT 1878 || !double_int_zero_p (val.mask)) 1879 return false; 1880 1881 if (dump_file) 1882 { 1883 fprintf (dump_file, "Folding predicate "); 1884 print_gimple_expr (dump_file, stmt, 0, 0); 1885 fprintf (dump_file, " to "); 1886 print_generic_expr (dump_file, val.value, 0); 1887 fprintf (dump_file, "\n"); 1888 } 1889 1890 if (integer_zerop (val.value)) 1891 gimple_cond_make_false (stmt); 1892 else 1893 gimple_cond_make_true (stmt); 1894 1895 return true; 1896 } 1897 1898 case GIMPLE_CALL: 1899 { 1900 tree lhs = gimple_call_lhs (stmt); 1901 int flags = gimple_call_flags (stmt); 1902 tree val; 1903 tree argt; 1904 bool changed = false; 1905 unsigned i; 1906 1907 /* If the call was folded into a constant make sure it goes 1908 away even if we cannot propagate into all uses because of 1909 type issues. */ 1910 if (lhs 1911 && TREE_CODE (lhs) == SSA_NAME 1912 && (val = get_constant_value (lhs)) 1913 /* Don't optimize away calls that have side-effects. */ 1914 && (flags & (ECF_CONST|ECF_PURE)) != 0 1915 && (flags & ECF_LOOPING_CONST_OR_PURE) == 0) 1916 { 1917 tree new_rhs = unshare_expr (val); 1918 bool res; 1919 if (!useless_type_conversion_p (TREE_TYPE (lhs), 1920 TREE_TYPE (new_rhs))) 1921 new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs); 1922 res = update_call_from_tree (gsi, new_rhs); 1923 gcc_assert (res); 1924 return true; 1925 } 1926 1927 /* Internal calls provide no argument types, so the extra laxity 1928 for normal calls does not apply. */ 1929 if (gimple_call_internal_p (stmt)) 1930 return false; 1931 1932 /* The heuristic of fold_builtin_alloca_with_align differs before and 1933 after inlining, so we don't require the arg to be changed into a 1934 constant for folding, but just to be constant. */ 1935 if (gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN)) 1936 { 1937 tree new_rhs = fold_builtin_alloca_with_align (stmt); 1938 if (new_rhs) 1939 { 1940 bool res = update_call_from_tree (gsi, new_rhs); 1941 tree var = TREE_OPERAND (TREE_OPERAND (new_rhs, 0),0); 1942 gcc_assert (res); 1943 insert_clobbers_for_var (*gsi, var); 1944 return true; 1945 } 1946 } 1947 1948 /* Propagate into the call arguments. Compared to replace_uses_in 1949 this can use the argument slot types for type verification 1950 instead of the current argument type. We also can safely 1951 drop qualifiers here as we are dealing with constants anyway. */ 1952 argt = TYPE_ARG_TYPES (gimple_call_fntype (stmt)); 1953 for (i = 0; i < gimple_call_num_args (stmt) && argt; 1954 ++i, argt = TREE_CHAIN (argt)) 1955 { 1956 tree arg = gimple_call_arg (stmt, i); 1957 if (TREE_CODE (arg) == SSA_NAME 1958 && (val = get_constant_value (arg)) 1959 && useless_type_conversion_p 1960 (TYPE_MAIN_VARIANT (TREE_VALUE (argt)), 1961 TYPE_MAIN_VARIANT (TREE_TYPE (val)))) 1962 { 1963 gimple_call_set_arg (stmt, i, unshare_expr (val)); 1964 changed = true; 1965 } 1966 } 1967 1968 return changed; 1969 } 1970 1971 case GIMPLE_ASSIGN: 1972 { 1973 tree lhs = gimple_assign_lhs (stmt); 1974 tree val; 1975 1976 /* If we have a load that turned out to be constant replace it 1977 as we cannot propagate into all uses in all cases. */ 1978 if (gimple_assign_single_p (stmt) 1979 && TREE_CODE (lhs) == SSA_NAME 1980 && (val = get_constant_value (lhs))) 1981 { 1982 tree rhs = unshare_expr (val); 1983 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs))) 1984 rhs = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs); 1985 gimple_assign_set_rhs_from_tree (gsi, rhs); 1986 return true; 1987 } 1988 1989 return false; 1990 } 1991 1992 default: 1993 return false; 1994 } 1995 } 1996 1997 /* Visit the assignment statement STMT. Set the value of its LHS to the 1998 value computed by the RHS and store LHS in *OUTPUT_P. If STMT 1999 creates virtual definitions, set the value of each new name to that 2000 of the RHS (if we can derive a constant out of the RHS). 2001 Value-returning call statements also perform an assignment, and 2002 are handled here. */ 2003 2004 static enum ssa_prop_result 2005 visit_assignment (gimple stmt, tree *output_p) 2006 { 2007 prop_value_t val; 2008 enum ssa_prop_result retval; 2009 2010 tree lhs = gimple_get_lhs (stmt); 2011 2012 gcc_assert (gimple_code (stmt) != GIMPLE_CALL 2013 || gimple_call_lhs (stmt) != NULL_TREE); 2014 2015 if (gimple_assign_single_p (stmt) 2016 && gimple_assign_rhs_code (stmt) == SSA_NAME) 2017 /* For a simple copy operation, we copy the lattice values. */ 2018 val = *get_value (gimple_assign_rhs1 (stmt)); 2019 else 2020 /* Evaluate the statement, which could be 2021 either a GIMPLE_ASSIGN or a GIMPLE_CALL. */ 2022 val = evaluate_stmt (stmt); 2023 2024 retval = SSA_PROP_NOT_INTERESTING; 2025 2026 /* Set the lattice value of the statement's output. */ 2027 if (TREE_CODE (lhs) == SSA_NAME) 2028 { 2029 /* If STMT is an assignment to an SSA_NAME, we only have one 2030 value to set. */ 2031 if (set_lattice_value (lhs, val)) 2032 { 2033 *output_p = lhs; 2034 if (val.lattice_val == VARYING) 2035 retval = SSA_PROP_VARYING; 2036 else 2037 retval = SSA_PROP_INTERESTING; 2038 } 2039 } 2040 2041 return retval; 2042 } 2043 2044 2045 /* Visit the conditional statement STMT. Return SSA_PROP_INTERESTING 2046 if it can determine which edge will be taken. Otherwise, return 2047 SSA_PROP_VARYING. */ 2048 2049 static enum ssa_prop_result 2050 visit_cond_stmt (gimple stmt, edge *taken_edge_p) 2051 { 2052 prop_value_t val; 2053 basic_block block; 2054 2055 block = gimple_bb (stmt); 2056 val = evaluate_stmt (stmt); 2057 if (val.lattice_val != CONSTANT 2058 || !double_int_zero_p (val.mask)) 2059 return SSA_PROP_VARYING; 2060 2061 /* Find which edge out of the conditional block will be taken and add it 2062 to the worklist. If no single edge can be determined statically, 2063 return SSA_PROP_VARYING to feed all the outgoing edges to the 2064 propagation engine. */ 2065 *taken_edge_p = find_taken_edge (block, val.value); 2066 if (*taken_edge_p) 2067 return SSA_PROP_INTERESTING; 2068 else 2069 return SSA_PROP_VARYING; 2070 } 2071 2072 2073 /* Evaluate statement STMT. If the statement produces an output value and 2074 its evaluation changes the lattice value of its output, return 2075 SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the 2076 output value. 2077 2078 If STMT is a conditional branch and we can determine its truth 2079 value, set *TAKEN_EDGE_P accordingly. If STMT produces a varying 2080 value, return SSA_PROP_VARYING. */ 2081 2082 static enum ssa_prop_result 2083 ccp_visit_stmt (gimple stmt, edge *taken_edge_p, tree *output_p) 2084 { 2085 tree def; 2086 ssa_op_iter iter; 2087 2088 if (dump_file && (dump_flags & TDF_DETAILS)) 2089 { 2090 fprintf (dump_file, "\nVisiting statement:\n"); 2091 print_gimple_stmt (dump_file, stmt, 0, dump_flags); 2092 } 2093 2094 switch (gimple_code (stmt)) 2095 { 2096 case GIMPLE_ASSIGN: 2097 /* If the statement is an assignment that produces a single 2098 output value, evaluate its RHS to see if the lattice value of 2099 its output has changed. */ 2100 return visit_assignment (stmt, output_p); 2101 2102 case GIMPLE_CALL: 2103 /* A value-returning call also performs an assignment. */ 2104 if (gimple_call_lhs (stmt) != NULL_TREE) 2105 return visit_assignment (stmt, output_p); 2106 break; 2107 2108 case GIMPLE_COND: 2109 case GIMPLE_SWITCH: 2110 /* If STMT is a conditional branch, see if we can determine 2111 which branch will be taken. */ 2112 /* FIXME. It appears that we should be able to optimize 2113 computed GOTOs here as well. */ 2114 return visit_cond_stmt (stmt, taken_edge_p); 2115 2116 default: 2117 break; 2118 } 2119 2120 /* Any other kind of statement is not interesting for constant 2121 propagation and, therefore, not worth simulating. */ 2122 if (dump_file && (dump_flags & TDF_DETAILS)) 2123 fprintf (dump_file, "No interesting values produced. Marked VARYING.\n"); 2124 2125 /* Definitions made by statements other than assignments to 2126 SSA_NAMEs represent unknown modifications to their outputs. 2127 Mark them VARYING. */ 2128 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 2129 { 2130 prop_value_t v = { VARYING, NULL_TREE, { -1, (HOST_WIDE_INT) -1 } }; 2131 set_lattice_value (def, v); 2132 } 2133 2134 return SSA_PROP_VARYING; 2135 } 2136 2137 2138 /* Main entry point for SSA Conditional Constant Propagation. */ 2139 2140 static unsigned int 2141 do_ssa_ccp (void) 2142 { 2143 unsigned int todo = 0; 2144 calculate_dominance_info (CDI_DOMINATORS); 2145 ccp_initialize (); 2146 ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node); 2147 if (ccp_finalize ()) 2148 todo = (TODO_cleanup_cfg | TODO_update_ssa | TODO_remove_unused_locals); 2149 free_dominance_info (CDI_DOMINATORS); 2150 return todo; 2151 } 2152 2153 2154 static bool 2155 gate_ccp (void) 2156 { 2157 return flag_tree_ccp != 0; 2158 } 2159 2160 2161 struct gimple_opt_pass pass_ccp = 2162 { 2163 { 2164 GIMPLE_PASS, 2165 "ccp", /* name */ 2166 gate_ccp, /* gate */ 2167 do_ssa_ccp, /* execute */ 2168 NULL, /* sub */ 2169 NULL, /* next */ 2170 0, /* static_pass_number */ 2171 TV_TREE_CCP, /* tv_id */ 2172 PROP_cfg | PROP_ssa, /* properties_required */ 2173 0, /* properties_provided */ 2174 0, /* properties_destroyed */ 2175 0, /* todo_flags_start */ 2176 TODO_verify_ssa 2177 | TODO_verify_stmts | TODO_ggc_collect/* todo_flags_finish */ 2178 } 2179 }; 2180 2181 2182 2183 /* Try to optimize out __builtin_stack_restore. Optimize it out 2184 if there is another __builtin_stack_restore in the same basic 2185 block and no calls or ASM_EXPRs are in between, or if this block's 2186 only outgoing edge is to EXIT_BLOCK and there are no calls or 2187 ASM_EXPRs after this __builtin_stack_restore. */ 2188 2189 static tree 2190 optimize_stack_restore (gimple_stmt_iterator i) 2191 { 2192 tree callee; 2193 gimple stmt; 2194 2195 basic_block bb = gsi_bb (i); 2196 gimple call = gsi_stmt (i); 2197 2198 if (gimple_code (call) != GIMPLE_CALL 2199 || gimple_call_num_args (call) != 1 2200 || TREE_CODE (gimple_call_arg (call, 0)) != SSA_NAME 2201 || !POINTER_TYPE_P (TREE_TYPE (gimple_call_arg (call, 0)))) 2202 return NULL_TREE; 2203 2204 for (gsi_next (&i); !gsi_end_p (i); gsi_next (&i)) 2205 { 2206 stmt = gsi_stmt (i); 2207 if (gimple_code (stmt) == GIMPLE_ASM) 2208 return NULL_TREE; 2209 if (gimple_code (stmt) != GIMPLE_CALL) 2210 continue; 2211 2212 callee = gimple_call_fndecl (stmt); 2213 if (!callee 2214 || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL 2215 /* All regular builtins are ok, just obviously not alloca. */ 2216 || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALLOCA 2217 || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALLOCA_WITH_ALIGN) 2218 return NULL_TREE; 2219 2220 if (DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_RESTORE) 2221 goto second_stack_restore; 2222 } 2223 2224 if (!gsi_end_p (i)) 2225 return NULL_TREE; 2226 2227 /* Allow one successor of the exit block, or zero successors. */ 2228 switch (EDGE_COUNT (bb->succs)) 2229 { 2230 case 0: 2231 break; 2232 case 1: 2233 if (single_succ_edge (bb)->dest != EXIT_BLOCK_PTR) 2234 return NULL_TREE; 2235 break; 2236 default: 2237 return NULL_TREE; 2238 } 2239 second_stack_restore: 2240 2241 /* If there's exactly one use, then zap the call to __builtin_stack_save. 2242 If there are multiple uses, then the last one should remove the call. 2243 In any case, whether the call to __builtin_stack_save can be removed 2244 or not is irrelevant to removing the call to __builtin_stack_restore. */ 2245 if (has_single_use (gimple_call_arg (call, 0))) 2246 { 2247 gimple stack_save = SSA_NAME_DEF_STMT (gimple_call_arg (call, 0)); 2248 if (is_gimple_call (stack_save)) 2249 { 2250 callee = gimple_call_fndecl (stack_save); 2251 if (callee 2252 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL 2253 && DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_SAVE) 2254 { 2255 gimple_stmt_iterator stack_save_gsi; 2256 tree rhs; 2257 2258 stack_save_gsi = gsi_for_stmt (stack_save); 2259 rhs = build_int_cst (TREE_TYPE (gimple_call_arg (call, 0)), 0); 2260 update_call_from_tree (&stack_save_gsi, rhs); 2261 } 2262 } 2263 } 2264 2265 /* No effect, so the statement will be deleted. */ 2266 return integer_zero_node; 2267 } 2268 2269 /* If va_list type is a simple pointer and nothing special is needed, 2270 optimize __builtin_va_start (&ap, 0) into ap = __builtin_next_arg (0), 2271 __builtin_va_end (&ap) out as NOP and __builtin_va_copy into a simple 2272 pointer assignment. */ 2273 2274 static tree 2275 optimize_stdarg_builtin (gimple call) 2276 { 2277 tree callee, lhs, rhs, cfun_va_list; 2278 bool va_list_simple_ptr; 2279 location_t loc = gimple_location (call); 2280 2281 if (gimple_code (call) != GIMPLE_CALL) 2282 return NULL_TREE; 2283 2284 callee = gimple_call_fndecl (call); 2285 2286 cfun_va_list = targetm.fn_abi_va_list (callee); 2287 va_list_simple_ptr = POINTER_TYPE_P (cfun_va_list) 2288 && (TREE_TYPE (cfun_va_list) == void_type_node 2289 || TREE_TYPE (cfun_va_list) == char_type_node); 2290 2291 switch (DECL_FUNCTION_CODE (callee)) 2292 { 2293 case BUILT_IN_VA_START: 2294 if (!va_list_simple_ptr 2295 || targetm.expand_builtin_va_start != NULL 2296 || !builtin_decl_explicit_p (BUILT_IN_NEXT_ARG)) 2297 return NULL_TREE; 2298 2299 if (gimple_call_num_args (call) != 2) 2300 return NULL_TREE; 2301 2302 lhs = gimple_call_arg (call, 0); 2303 if (!POINTER_TYPE_P (TREE_TYPE (lhs)) 2304 || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs))) 2305 != TYPE_MAIN_VARIANT (cfun_va_list)) 2306 return NULL_TREE; 2307 2308 lhs = build_fold_indirect_ref_loc (loc, lhs); 2309 rhs = build_call_expr_loc (loc, builtin_decl_explicit (BUILT_IN_NEXT_ARG), 2310 1, integer_zero_node); 2311 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs); 2312 return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs); 2313 2314 case BUILT_IN_VA_COPY: 2315 if (!va_list_simple_ptr) 2316 return NULL_TREE; 2317 2318 if (gimple_call_num_args (call) != 2) 2319 return NULL_TREE; 2320 2321 lhs = gimple_call_arg (call, 0); 2322 if (!POINTER_TYPE_P (TREE_TYPE (lhs)) 2323 || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs))) 2324 != TYPE_MAIN_VARIANT (cfun_va_list)) 2325 return NULL_TREE; 2326 2327 lhs = build_fold_indirect_ref_loc (loc, lhs); 2328 rhs = gimple_call_arg (call, 1); 2329 if (TYPE_MAIN_VARIANT (TREE_TYPE (rhs)) 2330 != TYPE_MAIN_VARIANT (cfun_va_list)) 2331 return NULL_TREE; 2332 2333 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs); 2334 return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs); 2335 2336 case BUILT_IN_VA_END: 2337 /* No effect, so the statement will be deleted. */ 2338 return integer_zero_node; 2339 2340 default: 2341 gcc_unreachable (); 2342 } 2343 } 2344 2345 /* A simple pass that attempts to fold all builtin functions. This pass 2346 is run after we've propagated as many constants as we can. */ 2347 2348 static unsigned int 2349 execute_fold_all_builtins (void) 2350 { 2351 bool cfg_changed = false; 2352 basic_block bb; 2353 unsigned int todoflags = 0; 2354 2355 FOR_EACH_BB (bb) 2356 { 2357 gimple_stmt_iterator i; 2358 for (i = gsi_start_bb (bb); !gsi_end_p (i); ) 2359 { 2360 gimple stmt, old_stmt; 2361 tree callee, result; 2362 enum built_in_function fcode; 2363 2364 stmt = gsi_stmt (i); 2365 2366 if (gimple_code (stmt) != GIMPLE_CALL) 2367 { 2368 gsi_next (&i); 2369 continue; 2370 } 2371 callee = gimple_call_fndecl (stmt); 2372 if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL) 2373 { 2374 gsi_next (&i); 2375 continue; 2376 } 2377 fcode = DECL_FUNCTION_CODE (callee); 2378 2379 result = gimple_fold_builtin (stmt); 2380 2381 if (result) 2382 gimple_remove_stmt_histograms (cfun, stmt); 2383 2384 if (!result) 2385 switch (DECL_FUNCTION_CODE (callee)) 2386 { 2387 case BUILT_IN_CONSTANT_P: 2388 /* Resolve __builtin_constant_p. If it hasn't been 2389 folded to integer_one_node by now, it's fairly 2390 certain that the value simply isn't constant. */ 2391 result = integer_zero_node; 2392 break; 2393 2394 case BUILT_IN_ASSUME_ALIGNED: 2395 /* Remove __builtin_assume_aligned. */ 2396 result = gimple_call_arg (stmt, 0); 2397 break; 2398 2399 case BUILT_IN_STACK_RESTORE: 2400 result = optimize_stack_restore (i); 2401 if (result) 2402 break; 2403 gsi_next (&i); 2404 continue; 2405 2406 case BUILT_IN_VA_START: 2407 case BUILT_IN_VA_END: 2408 case BUILT_IN_VA_COPY: 2409 /* These shouldn't be folded before pass_stdarg. */ 2410 result = optimize_stdarg_builtin (stmt); 2411 if (result) 2412 break; 2413 /* FALLTHRU */ 2414 2415 default: 2416 gsi_next (&i); 2417 continue; 2418 } 2419 2420 if (dump_file && (dump_flags & TDF_DETAILS)) 2421 { 2422 fprintf (dump_file, "Simplified\n "); 2423 print_gimple_stmt (dump_file, stmt, 0, dump_flags); 2424 } 2425 2426 old_stmt = stmt; 2427 if (!update_call_from_tree (&i, result)) 2428 { 2429 gimplify_and_update_call_from_tree (&i, result); 2430 todoflags |= TODO_update_address_taken; 2431 } 2432 2433 stmt = gsi_stmt (i); 2434 update_stmt (stmt); 2435 2436 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt) 2437 && gimple_purge_dead_eh_edges (bb)) 2438 cfg_changed = true; 2439 2440 if (dump_file && (dump_flags & TDF_DETAILS)) 2441 { 2442 fprintf (dump_file, "to\n "); 2443 print_gimple_stmt (dump_file, stmt, 0, dump_flags); 2444 fprintf (dump_file, "\n"); 2445 } 2446 2447 /* Retry the same statement if it changed into another 2448 builtin, there might be new opportunities now. */ 2449 if (gimple_code (stmt) != GIMPLE_CALL) 2450 { 2451 gsi_next (&i); 2452 continue; 2453 } 2454 callee = gimple_call_fndecl (stmt); 2455 if (!callee 2456 || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL 2457 || DECL_FUNCTION_CODE (callee) == fcode) 2458 gsi_next (&i); 2459 } 2460 } 2461 2462 /* Delete unreachable blocks. */ 2463 if (cfg_changed) 2464 todoflags |= TODO_cleanup_cfg; 2465 2466 return todoflags; 2467 } 2468 2469 2470 struct gimple_opt_pass pass_fold_builtins = 2471 { 2472 { 2473 GIMPLE_PASS, 2474 "fab", /* name */ 2475 NULL, /* gate */ 2476 execute_fold_all_builtins, /* execute */ 2477 NULL, /* sub */ 2478 NULL, /* next */ 2479 0, /* static_pass_number */ 2480 TV_NONE, /* tv_id */ 2481 PROP_cfg | PROP_ssa, /* properties_required */ 2482 0, /* properties_provided */ 2483 0, /* properties_destroyed */ 2484 0, /* todo_flags_start */ 2485 TODO_verify_ssa 2486 | TODO_update_ssa /* todo_flags_finish */ 2487 } 2488 }; 2489