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 if (gimple_assign_ssa_name_copy_p (stmt)) 1748 insert_clobber_before_stack_restore (gimple_assign_lhs (stmt), var, 1749 visited); 1750 else 1751 gcc_assert (is_gimple_debug (stmt)); 1752 } 1753 1754 /* Advance the iterator to the previous non-debug gimple statement in the same 1755 or dominating basic block. */ 1756 1757 static inline void 1758 gsi_prev_dom_bb_nondebug (gimple_stmt_iterator *i) 1759 { 1760 basic_block dom; 1761 1762 gsi_prev_nondebug (i); 1763 while (gsi_end_p (*i)) 1764 { 1765 dom = get_immediate_dominator (CDI_DOMINATORS, i->bb); 1766 if (dom == NULL || dom == ENTRY_BLOCK_PTR) 1767 return; 1768 1769 *i = gsi_last_bb (dom); 1770 } 1771 } 1772 1773 /* Find a BUILT_IN_STACK_SAVE dominating gsi_stmt (I), and insert 1774 a clobber of VAR before each matching BUILT_IN_STACK_RESTORE. 1775 1776 It is possible that BUILT_IN_STACK_SAVE cannot be find in a dominator when a 1777 previous pass (such as DOM) duplicated it along multiple paths to a BB. In 1778 that case the function gives up without inserting the clobbers. */ 1779 1780 static void 1781 insert_clobbers_for_var (gimple_stmt_iterator i, tree var) 1782 { 1783 gimple stmt; 1784 tree saved_val; 1785 htab_t visited = NULL; 1786 1787 for (; !gsi_end_p (i); gsi_prev_dom_bb_nondebug (&i)) 1788 { 1789 stmt = gsi_stmt (i); 1790 1791 if (!gimple_call_builtin_p (stmt, BUILT_IN_STACK_SAVE)) 1792 continue; 1793 1794 saved_val = gimple_call_lhs (stmt); 1795 if (saved_val == NULL_TREE) 1796 continue; 1797 1798 insert_clobber_before_stack_restore (saved_val, var, &visited); 1799 break; 1800 } 1801 1802 if (visited != NULL) 1803 htab_delete (visited); 1804 } 1805 1806 /* Detects a __builtin_alloca_with_align with constant size argument. Declares 1807 fixed-size array and returns the address, if found, otherwise returns 1808 NULL_TREE. */ 1809 1810 static tree 1811 fold_builtin_alloca_with_align (gimple stmt) 1812 { 1813 unsigned HOST_WIDE_INT size, threshold, n_elem; 1814 tree lhs, arg, block, var, elem_type, array_type; 1815 1816 /* Get lhs. */ 1817 lhs = gimple_call_lhs (stmt); 1818 if (lhs == NULL_TREE) 1819 return NULL_TREE; 1820 1821 /* Detect constant argument. */ 1822 arg = get_constant_value (gimple_call_arg (stmt, 0)); 1823 if (arg == NULL_TREE 1824 || TREE_CODE (arg) != INTEGER_CST 1825 || !host_integerp (arg, 1)) 1826 return NULL_TREE; 1827 1828 size = TREE_INT_CST_LOW (arg); 1829 1830 /* Heuristic: don't fold large allocas. */ 1831 threshold = (unsigned HOST_WIDE_INT)PARAM_VALUE (PARAM_LARGE_STACK_FRAME); 1832 /* In case the alloca is located at function entry, it has the same lifetime 1833 as a declared array, so we allow a larger size. */ 1834 block = gimple_block (stmt); 1835 if (!(cfun->after_inlining 1836 && TREE_CODE (BLOCK_SUPERCONTEXT (block)) == FUNCTION_DECL)) 1837 threshold /= 10; 1838 if (size > threshold) 1839 return NULL_TREE; 1840 1841 /* Declare array. */ 1842 elem_type = build_nonstandard_integer_type (BITS_PER_UNIT, 1); 1843 n_elem = size * 8 / BITS_PER_UNIT; 1844 array_type = build_array_type_nelts (elem_type, n_elem); 1845 var = create_tmp_var (array_type, NULL); 1846 DECL_ALIGN (var) = TREE_INT_CST_LOW (gimple_call_arg (stmt, 1)); 1847 { 1848 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (lhs); 1849 if (pi != NULL && !pi->pt.anything) 1850 { 1851 bool singleton_p; 1852 unsigned uid; 1853 singleton_p = pt_solution_singleton_p (&pi->pt, &uid); 1854 gcc_assert (singleton_p); 1855 SET_DECL_PT_UID (var, uid); 1856 } 1857 } 1858 1859 /* Fold alloca to the address of the array. */ 1860 return fold_convert (TREE_TYPE (lhs), build_fold_addr_expr (var)); 1861 } 1862 1863 /* Fold the stmt at *GSI with CCP specific information that propagating 1864 and regular folding does not catch. */ 1865 1866 static bool 1867 ccp_fold_stmt (gimple_stmt_iterator *gsi) 1868 { 1869 gimple stmt = gsi_stmt (*gsi); 1870 1871 switch (gimple_code (stmt)) 1872 { 1873 case GIMPLE_COND: 1874 { 1875 prop_value_t val; 1876 /* Statement evaluation will handle type mismatches in constants 1877 more gracefully than the final propagation. This allows us to 1878 fold more conditionals here. */ 1879 val = evaluate_stmt (stmt); 1880 if (val.lattice_val != CONSTANT 1881 || !double_int_zero_p (val.mask)) 1882 return false; 1883 1884 if (dump_file) 1885 { 1886 fprintf (dump_file, "Folding predicate "); 1887 print_gimple_expr (dump_file, stmt, 0, 0); 1888 fprintf (dump_file, " to "); 1889 print_generic_expr (dump_file, val.value, 0); 1890 fprintf (dump_file, "\n"); 1891 } 1892 1893 if (integer_zerop (val.value)) 1894 gimple_cond_make_false (stmt); 1895 else 1896 gimple_cond_make_true (stmt); 1897 1898 return true; 1899 } 1900 1901 case GIMPLE_CALL: 1902 { 1903 tree lhs = gimple_call_lhs (stmt); 1904 int flags = gimple_call_flags (stmt); 1905 tree val; 1906 tree argt; 1907 bool changed = false; 1908 unsigned i; 1909 1910 /* If the call was folded into a constant make sure it goes 1911 away even if we cannot propagate into all uses because of 1912 type issues. */ 1913 if (lhs 1914 && TREE_CODE (lhs) == SSA_NAME 1915 && (val = get_constant_value (lhs)) 1916 /* Don't optimize away calls that have side-effects. */ 1917 && (flags & (ECF_CONST|ECF_PURE)) != 0 1918 && (flags & ECF_LOOPING_CONST_OR_PURE) == 0) 1919 { 1920 tree new_rhs = unshare_expr (val); 1921 bool res; 1922 if (!useless_type_conversion_p (TREE_TYPE (lhs), 1923 TREE_TYPE (new_rhs))) 1924 new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs); 1925 res = update_call_from_tree (gsi, new_rhs); 1926 gcc_assert (res); 1927 return true; 1928 } 1929 1930 /* Internal calls provide no argument types, so the extra laxity 1931 for normal calls does not apply. */ 1932 if (gimple_call_internal_p (stmt)) 1933 return false; 1934 1935 /* The heuristic of fold_builtin_alloca_with_align differs before and 1936 after inlining, so we don't require the arg to be changed into a 1937 constant for folding, but just to be constant. */ 1938 if (gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN)) 1939 { 1940 tree new_rhs = fold_builtin_alloca_with_align (stmt); 1941 if (new_rhs) 1942 { 1943 bool res = update_call_from_tree (gsi, new_rhs); 1944 tree var = TREE_OPERAND (TREE_OPERAND (new_rhs, 0),0); 1945 gcc_assert (res); 1946 insert_clobbers_for_var (*gsi, var); 1947 return true; 1948 } 1949 } 1950 1951 /* Propagate into the call arguments. Compared to replace_uses_in 1952 this can use the argument slot types for type verification 1953 instead of the current argument type. We also can safely 1954 drop qualifiers here as we are dealing with constants anyway. */ 1955 argt = TYPE_ARG_TYPES (gimple_call_fntype (stmt)); 1956 for (i = 0; i < gimple_call_num_args (stmt) && argt; 1957 ++i, argt = TREE_CHAIN (argt)) 1958 { 1959 tree arg = gimple_call_arg (stmt, i); 1960 if (TREE_CODE (arg) == SSA_NAME 1961 && (val = get_constant_value (arg)) 1962 && useless_type_conversion_p 1963 (TYPE_MAIN_VARIANT (TREE_VALUE (argt)), 1964 TYPE_MAIN_VARIANT (TREE_TYPE (val)))) 1965 { 1966 gimple_call_set_arg (stmt, i, unshare_expr (val)); 1967 changed = true; 1968 } 1969 } 1970 1971 return changed; 1972 } 1973 1974 case GIMPLE_ASSIGN: 1975 { 1976 tree lhs = gimple_assign_lhs (stmt); 1977 tree val; 1978 1979 /* If we have a load that turned out to be constant replace it 1980 as we cannot propagate into all uses in all cases. */ 1981 if (gimple_assign_single_p (stmt) 1982 && TREE_CODE (lhs) == SSA_NAME 1983 && (val = get_constant_value (lhs))) 1984 { 1985 tree rhs = unshare_expr (val); 1986 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs))) 1987 rhs = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs); 1988 gimple_assign_set_rhs_from_tree (gsi, rhs); 1989 return true; 1990 } 1991 1992 return false; 1993 } 1994 1995 default: 1996 return false; 1997 } 1998 } 1999 2000 /* Visit the assignment statement STMT. Set the value of its LHS to the 2001 value computed by the RHS and store LHS in *OUTPUT_P. If STMT 2002 creates virtual definitions, set the value of each new name to that 2003 of the RHS (if we can derive a constant out of the RHS). 2004 Value-returning call statements also perform an assignment, and 2005 are handled here. */ 2006 2007 static enum ssa_prop_result 2008 visit_assignment (gimple stmt, tree *output_p) 2009 { 2010 prop_value_t val; 2011 enum ssa_prop_result retval; 2012 2013 tree lhs = gimple_get_lhs (stmt); 2014 2015 gcc_assert (gimple_code (stmt) != GIMPLE_CALL 2016 || gimple_call_lhs (stmt) != NULL_TREE); 2017 2018 if (gimple_assign_single_p (stmt) 2019 && gimple_assign_rhs_code (stmt) == SSA_NAME) 2020 /* For a simple copy operation, we copy the lattice values. */ 2021 val = *get_value (gimple_assign_rhs1 (stmt)); 2022 else 2023 /* Evaluate the statement, which could be 2024 either a GIMPLE_ASSIGN or a GIMPLE_CALL. */ 2025 val = evaluate_stmt (stmt); 2026 2027 retval = SSA_PROP_NOT_INTERESTING; 2028 2029 /* Set the lattice value of the statement's output. */ 2030 if (TREE_CODE (lhs) == SSA_NAME) 2031 { 2032 /* If STMT is an assignment to an SSA_NAME, we only have one 2033 value to set. */ 2034 if (set_lattice_value (lhs, val)) 2035 { 2036 *output_p = lhs; 2037 if (val.lattice_val == VARYING) 2038 retval = SSA_PROP_VARYING; 2039 else 2040 retval = SSA_PROP_INTERESTING; 2041 } 2042 } 2043 2044 return retval; 2045 } 2046 2047 2048 /* Visit the conditional statement STMT. Return SSA_PROP_INTERESTING 2049 if it can determine which edge will be taken. Otherwise, return 2050 SSA_PROP_VARYING. */ 2051 2052 static enum ssa_prop_result 2053 visit_cond_stmt (gimple stmt, edge *taken_edge_p) 2054 { 2055 prop_value_t val; 2056 basic_block block; 2057 2058 block = gimple_bb (stmt); 2059 val = evaluate_stmt (stmt); 2060 if (val.lattice_val != CONSTANT 2061 || !double_int_zero_p (val.mask)) 2062 return SSA_PROP_VARYING; 2063 2064 /* Find which edge out of the conditional block will be taken and add it 2065 to the worklist. If no single edge can be determined statically, 2066 return SSA_PROP_VARYING to feed all the outgoing edges to the 2067 propagation engine. */ 2068 *taken_edge_p = find_taken_edge (block, val.value); 2069 if (*taken_edge_p) 2070 return SSA_PROP_INTERESTING; 2071 else 2072 return SSA_PROP_VARYING; 2073 } 2074 2075 2076 /* Evaluate statement STMT. If the statement produces an output value and 2077 its evaluation changes the lattice value of its output, return 2078 SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the 2079 output value. 2080 2081 If STMT is a conditional branch and we can determine its truth 2082 value, set *TAKEN_EDGE_P accordingly. If STMT produces a varying 2083 value, return SSA_PROP_VARYING. */ 2084 2085 static enum ssa_prop_result 2086 ccp_visit_stmt (gimple stmt, edge *taken_edge_p, tree *output_p) 2087 { 2088 tree def; 2089 ssa_op_iter iter; 2090 2091 if (dump_file && (dump_flags & TDF_DETAILS)) 2092 { 2093 fprintf (dump_file, "\nVisiting statement:\n"); 2094 print_gimple_stmt (dump_file, stmt, 0, dump_flags); 2095 } 2096 2097 switch (gimple_code (stmt)) 2098 { 2099 case GIMPLE_ASSIGN: 2100 /* If the statement is an assignment that produces a single 2101 output value, evaluate its RHS to see if the lattice value of 2102 its output has changed. */ 2103 return visit_assignment (stmt, output_p); 2104 2105 case GIMPLE_CALL: 2106 /* A value-returning call also performs an assignment. */ 2107 if (gimple_call_lhs (stmt) != NULL_TREE) 2108 return visit_assignment (stmt, output_p); 2109 break; 2110 2111 case GIMPLE_COND: 2112 case GIMPLE_SWITCH: 2113 /* If STMT is a conditional branch, see if we can determine 2114 which branch will be taken. */ 2115 /* FIXME. It appears that we should be able to optimize 2116 computed GOTOs here as well. */ 2117 return visit_cond_stmt (stmt, taken_edge_p); 2118 2119 default: 2120 break; 2121 } 2122 2123 /* Any other kind of statement is not interesting for constant 2124 propagation and, therefore, not worth simulating. */ 2125 if (dump_file && (dump_flags & TDF_DETAILS)) 2126 fprintf (dump_file, "No interesting values produced. Marked VARYING.\n"); 2127 2128 /* Definitions made by statements other than assignments to 2129 SSA_NAMEs represent unknown modifications to their outputs. 2130 Mark them VARYING. */ 2131 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 2132 { 2133 prop_value_t v = { VARYING, NULL_TREE, { -1, (HOST_WIDE_INT) -1 } }; 2134 set_lattice_value (def, v); 2135 } 2136 2137 return SSA_PROP_VARYING; 2138 } 2139 2140 2141 /* Main entry point for SSA Conditional Constant Propagation. */ 2142 2143 static unsigned int 2144 do_ssa_ccp (void) 2145 { 2146 unsigned int todo = 0; 2147 calculate_dominance_info (CDI_DOMINATORS); 2148 ccp_initialize (); 2149 ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node); 2150 if (ccp_finalize ()) 2151 todo = (TODO_cleanup_cfg | TODO_update_ssa | TODO_remove_unused_locals); 2152 free_dominance_info (CDI_DOMINATORS); 2153 return todo; 2154 } 2155 2156 2157 static bool 2158 gate_ccp (void) 2159 { 2160 return flag_tree_ccp != 0; 2161 } 2162 2163 2164 struct gimple_opt_pass pass_ccp = 2165 { 2166 { 2167 GIMPLE_PASS, 2168 "ccp", /* name */ 2169 gate_ccp, /* gate */ 2170 do_ssa_ccp, /* execute */ 2171 NULL, /* sub */ 2172 NULL, /* next */ 2173 0, /* static_pass_number */ 2174 TV_TREE_CCP, /* tv_id */ 2175 PROP_cfg | PROP_ssa, /* properties_required */ 2176 0, /* properties_provided */ 2177 0, /* properties_destroyed */ 2178 0, /* todo_flags_start */ 2179 TODO_verify_ssa 2180 | TODO_verify_stmts | TODO_ggc_collect/* todo_flags_finish */ 2181 } 2182 }; 2183 2184 2185 2186 /* Try to optimize out __builtin_stack_restore. Optimize it out 2187 if there is another __builtin_stack_restore in the same basic 2188 block and no calls or ASM_EXPRs are in between, or if this block's 2189 only outgoing edge is to EXIT_BLOCK and there are no calls or 2190 ASM_EXPRs after this __builtin_stack_restore. */ 2191 2192 static tree 2193 optimize_stack_restore (gimple_stmt_iterator i) 2194 { 2195 tree callee; 2196 gimple stmt; 2197 2198 basic_block bb = gsi_bb (i); 2199 gimple call = gsi_stmt (i); 2200 2201 if (gimple_code (call) != GIMPLE_CALL 2202 || gimple_call_num_args (call) != 1 2203 || TREE_CODE (gimple_call_arg (call, 0)) != SSA_NAME 2204 || !POINTER_TYPE_P (TREE_TYPE (gimple_call_arg (call, 0)))) 2205 return NULL_TREE; 2206 2207 for (gsi_next (&i); !gsi_end_p (i); gsi_next (&i)) 2208 { 2209 stmt = gsi_stmt (i); 2210 if (gimple_code (stmt) == GIMPLE_ASM) 2211 return NULL_TREE; 2212 if (gimple_code (stmt) != GIMPLE_CALL) 2213 continue; 2214 2215 callee = gimple_call_fndecl (stmt); 2216 if (!callee 2217 || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL 2218 /* All regular builtins are ok, just obviously not alloca. */ 2219 || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALLOCA 2220 || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALLOCA_WITH_ALIGN) 2221 return NULL_TREE; 2222 2223 if (DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_RESTORE) 2224 goto second_stack_restore; 2225 } 2226 2227 if (!gsi_end_p (i)) 2228 return NULL_TREE; 2229 2230 /* Allow one successor of the exit block, or zero successors. */ 2231 switch (EDGE_COUNT (bb->succs)) 2232 { 2233 case 0: 2234 break; 2235 case 1: 2236 if (single_succ_edge (bb)->dest != EXIT_BLOCK_PTR) 2237 return NULL_TREE; 2238 break; 2239 default: 2240 return NULL_TREE; 2241 } 2242 second_stack_restore: 2243 2244 /* If there's exactly one use, then zap the call to __builtin_stack_save. 2245 If there are multiple uses, then the last one should remove the call. 2246 In any case, whether the call to __builtin_stack_save can be removed 2247 or not is irrelevant to removing the call to __builtin_stack_restore. */ 2248 if (has_single_use (gimple_call_arg (call, 0))) 2249 { 2250 gimple stack_save = SSA_NAME_DEF_STMT (gimple_call_arg (call, 0)); 2251 if (is_gimple_call (stack_save)) 2252 { 2253 callee = gimple_call_fndecl (stack_save); 2254 if (callee 2255 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL 2256 && DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_SAVE) 2257 { 2258 gimple_stmt_iterator stack_save_gsi; 2259 tree rhs; 2260 2261 stack_save_gsi = gsi_for_stmt (stack_save); 2262 rhs = build_int_cst (TREE_TYPE (gimple_call_arg (call, 0)), 0); 2263 update_call_from_tree (&stack_save_gsi, rhs); 2264 } 2265 } 2266 } 2267 2268 /* No effect, so the statement will be deleted. */ 2269 return integer_zero_node; 2270 } 2271 2272 /* If va_list type is a simple pointer and nothing special is needed, 2273 optimize __builtin_va_start (&ap, 0) into ap = __builtin_next_arg (0), 2274 __builtin_va_end (&ap) out as NOP and __builtin_va_copy into a simple 2275 pointer assignment. */ 2276 2277 static tree 2278 optimize_stdarg_builtin (gimple call) 2279 { 2280 tree callee, lhs, rhs, cfun_va_list; 2281 bool va_list_simple_ptr; 2282 location_t loc = gimple_location (call); 2283 2284 if (gimple_code (call) != GIMPLE_CALL) 2285 return NULL_TREE; 2286 2287 callee = gimple_call_fndecl (call); 2288 2289 cfun_va_list = targetm.fn_abi_va_list (callee); 2290 va_list_simple_ptr = POINTER_TYPE_P (cfun_va_list) 2291 && (TREE_TYPE (cfun_va_list) == void_type_node 2292 || TREE_TYPE (cfun_va_list) == char_type_node); 2293 2294 switch (DECL_FUNCTION_CODE (callee)) 2295 { 2296 case BUILT_IN_VA_START: 2297 if (!va_list_simple_ptr 2298 || targetm.expand_builtin_va_start != NULL 2299 || !builtin_decl_explicit_p (BUILT_IN_NEXT_ARG)) 2300 return NULL_TREE; 2301 2302 if (gimple_call_num_args (call) != 2) 2303 return NULL_TREE; 2304 2305 lhs = gimple_call_arg (call, 0); 2306 if (!POINTER_TYPE_P (TREE_TYPE (lhs)) 2307 || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs))) 2308 != TYPE_MAIN_VARIANT (cfun_va_list)) 2309 return NULL_TREE; 2310 2311 lhs = build_fold_indirect_ref_loc (loc, lhs); 2312 rhs = build_call_expr_loc (loc, builtin_decl_explicit (BUILT_IN_NEXT_ARG), 2313 1, integer_zero_node); 2314 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs); 2315 return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs); 2316 2317 case BUILT_IN_VA_COPY: 2318 if (!va_list_simple_ptr) 2319 return NULL_TREE; 2320 2321 if (gimple_call_num_args (call) != 2) 2322 return NULL_TREE; 2323 2324 lhs = gimple_call_arg (call, 0); 2325 if (!POINTER_TYPE_P (TREE_TYPE (lhs)) 2326 || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs))) 2327 != TYPE_MAIN_VARIANT (cfun_va_list)) 2328 return NULL_TREE; 2329 2330 lhs = build_fold_indirect_ref_loc (loc, lhs); 2331 rhs = gimple_call_arg (call, 1); 2332 if (TYPE_MAIN_VARIANT (TREE_TYPE (rhs)) 2333 != TYPE_MAIN_VARIANT (cfun_va_list)) 2334 return NULL_TREE; 2335 2336 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs); 2337 return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs); 2338 2339 case BUILT_IN_VA_END: 2340 /* No effect, so the statement will be deleted. */ 2341 return integer_zero_node; 2342 2343 default: 2344 gcc_unreachable (); 2345 } 2346 } 2347 2348 /* A simple pass that attempts to fold all builtin functions. This pass 2349 is run after we've propagated as many constants as we can. */ 2350 2351 static unsigned int 2352 execute_fold_all_builtins (void) 2353 { 2354 bool cfg_changed = false; 2355 basic_block bb; 2356 unsigned int todoflags = 0; 2357 2358 FOR_EACH_BB (bb) 2359 { 2360 gimple_stmt_iterator i; 2361 for (i = gsi_start_bb (bb); !gsi_end_p (i); ) 2362 { 2363 gimple stmt, old_stmt; 2364 tree callee, result; 2365 enum built_in_function fcode; 2366 2367 stmt = gsi_stmt (i); 2368 2369 if (gimple_code (stmt) != GIMPLE_CALL) 2370 { 2371 gsi_next (&i); 2372 continue; 2373 } 2374 callee = gimple_call_fndecl (stmt); 2375 if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL) 2376 { 2377 gsi_next (&i); 2378 continue; 2379 } 2380 fcode = DECL_FUNCTION_CODE (callee); 2381 2382 result = gimple_fold_builtin (stmt); 2383 2384 if (result) 2385 gimple_remove_stmt_histograms (cfun, stmt); 2386 2387 if (!result) 2388 switch (DECL_FUNCTION_CODE (callee)) 2389 { 2390 case BUILT_IN_CONSTANT_P: 2391 /* Resolve __builtin_constant_p. If it hasn't been 2392 folded to integer_one_node by now, it's fairly 2393 certain that the value simply isn't constant. */ 2394 result = integer_zero_node; 2395 break; 2396 2397 case BUILT_IN_ASSUME_ALIGNED: 2398 /* Remove __builtin_assume_aligned. */ 2399 result = gimple_call_arg (stmt, 0); 2400 break; 2401 2402 case BUILT_IN_STACK_RESTORE: 2403 result = optimize_stack_restore (i); 2404 if (result) 2405 break; 2406 gsi_next (&i); 2407 continue; 2408 2409 case BUILT_IN_VA_START: 2410 case BUILT_IN_VA_END: 2411 case BUILT_IN_VA_COPY: 2412 /* These shouldn't be folded before pass_stdarg. */ 2413 result = optimize_stdarg_builtin (stmt); 2414 if (result) 2415 break; 2416 /* FALLTHRU */ 2417 2418 default: 2419 gsi_next (&i); 2420 continue; 2421 } 2422 2423 if (dump_file && (dump_flags & TDF_DETAILS)) 2424 { 2425 fprintf (dump_file, "Simplified\n "); 2426 print_gimple_stmt (dump_file, stmt, 0, dump_flags); 2427 } 2428 2429 old_stmt = stmt; 2430 if (!update_call_from_tree (&i, result)) 2431 { 2432 gimplify_and_update_call_from_tree (&i, result); 2433 todoflags |= TODO_update_address_taken; 2434 } 2435 2436 stmt = gsi_stmt (i); 2437 update_stmt (stmt); 2438 2439 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt) 2440 && gimple_purge_dead_eh_edges (bb)) 2441 cfg_changed = true; 2442 2443 if (dump_file && (dump_flags & TDF_DETAILS)) 2444 { 2445 fprintf (dump_file, "to\n "); 2446 print_gimple_stmt (dump_file, stmt, 0, dump_flags); 2447 fprintf (dump_file, "\n"); 2448 } 2449 2450 /* Retry the same statement if it changed into another 2451 builtin, there might be new opportunities now. */ 2452 if (gimple_code (stmt) != GIMPLE_CALL) 2453 { 2454 gsi_next (&i); 2455 continue; 2456 } 2457 callee = gimple_call_fndecl (stmt); 2458 if (!callee 2459 || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL 2460 || DECL_FUNCTION_CODE (callee) == fcode) 2461 gsi_next (&i); 2462 } 2463 } 2464 2465 /* Delete unreachable blocks. */ 2466 if (cfg_changed) 2467 todoflags |= TODO_cleanup_cfg; 2468 2469 return todoflags; 2470 } 2471 2472 2473 struct gimple_opt_pass pass_fold_builtins = 2474 { 2475 { 2476 GIMPLE_PASS, 2477 "fab", /* name */ 2478 NULL, /* gate */ 2479 execute_fold_all_builtins, /* execute */ 2480 NULL, /* sub */ 2481 NULL, /* next */ 2482 0, /* static_pass_number */ 2483 TV_NONE, /* tv_id */ 2484 PROP_cfg | PROP_ssa, /* properties_required */ 2485 0, /* properties_provided */ 2486 0, /* properties_destroyed */ 2487 0, /* todo_flags_start */ 2488 TODO_verify_ssa 2489 | TODO_update_ssa /* todo_flags_finish */ 2490 } 2491 }; 2492