1 /* Header file for SSA dominator optimizations. 2 Copyright (C) 2013-2018 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it under 7 the terms of the GNU General Public License as published by the Free 8 Software Foundation; either version 3, or (at your option) any later 9 version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12 WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20 #include "config.h" 21 #include "system.h" 22 #include "coretypes.h" 23 #include "function.h" 24 #include "basic-block.h" 25 #include "tree.h" 26 #include "gimple.h" 27 #include "tree-pass.h" 28 #include "tree-pretty-print.h" 29 #include "tree-ssa-scopedtables.h" 30 #include "tree-ssa-threadedge.h" 31 #include "stor-layout.h" 32 #include "fold-const.h" 33 #include "tree-eh.h" 34 #include "internal-fn.h" 35 #include "tree-dfa.h" 36 #include "options.h" 37 #include "params.h" 38 39 static bool hashable_expr_equal_p (const struct hashable_expr *, 40 const struct hashable_expr *); 41 42 /* Initialize local stacks for this optimizer and record equivalences 43 upon entry to BB. Equivalences can come from the edge traversed to 44 reach BB or they may come from PHI nodes at the start of BB. */ 45 46 /* Pop items off the unwinding stack, removing each from the hash table 47 until a marker is encountered. */ 48 49 void 50 avail_exprs_stack::pop_to_marker () 51 { 52 /* Remove all the expressions made available in this block. */ 53 while (m_stack.length () > 0) 54 { 55 std::pair<expr_hash_elt_t, expr_hash_elt_t> victim = m_stack.pop (); 56 expr_hash_elt **slot; 57 58 if (victim.first == NULL) 59 break; 60 61 /* This must precede the actual removal from the hash table, 62 as ELEMENT and the table entry may share a call argument 63 vector which will be freed during removal. */ 64 if (dump_file && (dump_flags & TDF_DETAILS)) 65 { 66 fprintf (dump_file, "<<<< "); 67 victim.first->print (dump_file); 68 } 69 70 slot = m_avail_exprs->find_slot (victim.first, NO_INSERT); 71 gcc_assert (slot && *slot == victim.first); 72 if (victim.second != NULL) 73 { 74 delete *slot; 75 *slot = victim.second; 76 } 77 else 78 m_avail_exprs->clear_slot (slot); 79 } 80 } 81 82 /* Add <ELT1,ELT2> to the unwinding stack so they can be later removed 83 from the hash table. */ 84 85 void 86 avail_exprs_stack::record_expr (class expr_hash_elt *elt1, 87 class expr_hash_elt *elt2, 88 char type) 89 { 90 if (elt1 && dump_file && (dump_flags & TDF_DETAILS)) 91 { 92 fprintf (dump_file, "%c>>> ", type); 93 elt1->print (dump_file); 94 } 95 96 m_stack.safe_push (std::pair<expr_hash_elt_t, expr_hash_elt_t> (elt1, elt2)); 97 } 98 99 /* Helper for walk_non_aliased_vuses. Determine if we arrived at 100 the desired memory state. */ 101 102 static void * 103 vuse_eq (ao_ref *, tree vuse1, unsigned int cnt, void *data) 104 { 105 tree vuse2 = (tree) data; 106 if (vuse1 == vuse2) 107 return data; 108 109 /* This bounds the stmt walks we perform on reference lookups 110 to O(1) instead of O(N) where N is the number of dominating 111 stores leading to a candidate. We re-use the SCCVN param 112 for this as it is basically the same complexity. */ 113 if (cnt > (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS)) 114 return (void *)-1; 115 116 return NULL; 117 } 118 119 /* We looked for STMT in the hash table, but did not find it. 120 121 If STMT is an assignment from a binary operator, we may know something 122 about the operands relationship to each other which would allow 123 us to derive a constant value for the RHS of STMT. */ 124 125 tree 126 avail_exprs_stack::simplify_binary_operation (gimple *stmt, 127 class expr_hash_elt element) 128 { 129 if (is_gimple_assign (stmt)) 130 { 131 struct hashable_expr *expr = element.expr (); 132 if (expr->kind == EXPR_BINARY) 133 { 134 enum tree_code code = expr->ops.binary.op; 135 136 switch (code) 137 { 138 /* For these cases, if we know the operands 139 are equal, then we know the result. */ 140 case MIN_EXPR: 141 case MAX_EXPR: 142 case BIT_IOR_EXPR: 143 case BIT_AND_EXPR: 144 case BIT_XOR_EXPR: 145 case MINUS_EXPR: 146 case TRUNC_DIV_EXPR: 147 case CEIL_DIV_EXPR: 148 case FLOOR_DIV_EXPR: 149 case ROUND_DIV_EXPR: 150 case EXACT_DIV_EXPR: 151 case TRUNC_MOD_EXPR: 152 case CEIL_MOD_EXPR: 153 case FLOOR_MOD_EXPR: 154 case ROUND_MOD_EXPR: 155 { 156 /* Build a simple equality expr and query the hash table 157 for it. */ 158 struct hashable_expr expr; 159 expr.type = boolean_type_node; 160 expr.kind = EXPR_BINARY; 161 expr.ops.binary.op = EQ_EXPR; 162 expr.ops.binary.opnd0 = gimple_assign_rhs1 (stmt); 163 expr.ops.binary.opnd1 = gimple_assign_rhs2 (stmt); 164 class expr_hash_elt element2 (&expr, NULL_TREE); 165 expr_hash_elt **slot 166 = m_avail_exprs->find_slot (&element2, NO_INSERT); 167 tree result_type = TREE_TYPE (gimple_assign_lhs (stmt)); 168 169 /* If the query was successful and returned a nonzero 170 result, then we know that the operands of the binary 171 expression are the same. In many cases this allows 172 us to compute a constant result of the expression 173 at compile time, even if we do not know the exact 174 values of the operands. */ 175 if (slot && *slot && integer_onep ((*slot)->lhs ())) 176 { 177 switch (code) 178 { 179 case MIN_EXPR: 180 case MAX_EXPR: 181 case BIT_IOR_EXPR: 182 case BIT_AND_EXPR: 183 return gimple_assign_rhs1 (stmt); 184 185 case MINUS_EXPR: 186 /* This is unsafe for certain floats even in non-IEEE 187 formats. In IEEE, it is unsafe because it does 188 wrong for NaNs. */ 189 if (FLOAT_TYPE_P (result_type) 190 && HONOR_NANS (result_type)) 191 break; 192 /* FALLTHRU */ 193 case BIT_XOR_EXPR: 194 case TRUNC_MOD_EXPR: 195 case CEIL_MOD_EXPR: 196 case FLOOR_MOD_EXPR: 197 case ROUND_MOD_EXPR: 198 return build_zero_cst (result_type); 199 200 case TRUNC_DIV_EXPR: 201 case CEIL_DIV_EXPR: 202 case FLOOR_DIV_EXPR: 203 case ROUND_DIV_EXPR: 204 case EXACT_DIV_EXPR: 205 /* Avoid _Fract types where we can't build 1. */ 206 if (ALL_FRACT_MODE_P (TYPE_MODE (result_type))) 207 break; 208 return build_one_cst (result_type); 209 210 default: 211 gcc_unreachable (); 212 } 213 } 214 break; 215 } 216 217 default: 218 break; 219 } 220 } 221 } 222 return NULL_TREE; 223 } 224 225 /* Search for an existing instance of STMT in the AVAIL_EXPRS_STACK table. 226 If found, return its LHS. Otherwise insert STMT in the table and 227 return NULL_TREE. 228 229 Also, when an expression is first inserted in the table, it is also 230 is also added to AVAIL_EXPRS_STACK, so that it can be removed when 231 we finish processing this block and its children. */ 232 233 tree 234 avail_exprs_stack::lookup_avail_expr (gimple *stmt, bool insert, bool tbaa_p) 235 { 236 expr_hash_elt **slot; 237 tree lhs; 238 239 /* Get LHS of phi, assignment, or call; else NULL_TREE. */ 240 if (gimple_code (stmt) == GIMPLE_PHI) 241 lhs = gimple_phi_result (stmt); 242 else 243 lhs = gimple_get_lhs (stmt); 244 245 class expr_hash_elt element (stmt, lhs); 246 247 if (dump_file && (dump_flags & TDF_DETAILS)) 248 { 249 fprintf (dump_file, "LKUP "); 250 element.print (dump_file); 251 } 252 253 /* Don't bother remembering constant assignments and copy operations. 254 Constants and copy operations are handled by the constant/copy propagator 255 in optimize_stmt. */ 256 if (element.expr()->kind == EXPR_SINGLE 257 && (TREE_CODE (element.expr()->ops.single.rhs) == SSA_NAME 258 || is_gimple_min_invariant (element.expr()->ops.single.rhs))) 259 return NULL_TREE; 260 261 /* Finally try to find the expression in the main expression hash table. */ 262 slot = m_avail_exprs->find_slot (&element, (insert ? INSERT : NO_INSERT)); 263 if (slot == NULL) 264 { 265 return NULL_TREE; 266 } 267 else if (*slot == NULL) 268 { 269 /* If we did not find the expression in the hash table, we may still 270 be able to produce a result for some expressions. */ 271 tree retval = avail_exprs_stack::simplify_binary_operation (stmt, 272 element); 273 274 /* We have, in effect, allocated *SLOT for ELEMENT at this point. 275 We must initialize *SLOT to a real entry, even if we found a 276 way to prove ELEMENT was a constant after not finding ELEMENT 277 in the hash table. 278 279 An uninitialized or empty slot is an indication no prior objects 280 entered into the hash table had a hash collection with ELEMENT. 281 282 If we fail to do so and had such entries in the table, they 283 would become unreachable. */ 284 class expr_hash_elt *element2 = new expr_hash_elt (element); 285 *slot = element2; 286 287 record_expr (element2, NULL, '2'); 288 return retval; 289 } 290 291 /* If we found a redundant memory operation do an alias walk to 292 check if we can re-use it. */ 293 if (gimple_vuse (stmt) != (*slot)->vop ()) 294 { 295 tree vuse1 = (*slot)->vop (); 296 tree vuse2 = gimple_vuse (stmt); 297 /* If we have a load of a register and a candidate in the 298 hash with vuse1 then try to reach its stmt by walking 299 up the virtual use-def chain using walk_non_aliased_vuses. 300 But don't do this when removing expressions from the hash. */ 301 ao_ref ref; 302 if (!(vuse1 && vuse2 303 && gimple_assign_single_p (stmt) 304 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME 305 && (ao_ref_init (&ref, gimple_assign_rhs1 (stmt)), 306 ref.base_alias_set = ref.ref_alias_set = tbaa_p ? -1 : 0, true) 307 && walk_non_aliased_vuses (&ref, vuse2, 308 vuse_eq, NULL, NULL, vuse1) != NULL)) 309 { 310 if (insert) 311 { 312 class expr_hash_elt *element2 = new expr_hash_elt (element); 313 314 /* Insert the expr into the hash by replacing the current 315 entry and recording the value to restore in the 316 avail_exprs_stack. */ 317 record_expr (element2, *slot, '2'); 318 *slot = element2; 319 } 320 return NULL_TREE; 321 } 322 } 323 324 /* Extract the LHS of the assignment so that it can be used as the current 325 definition of another variable. */ 326 lhs = (*slot)->lhs (); 327 328 /* Valueize the result. */ 329 if (TREE_CODE (lhs) == SSA_NAME) 330 { 331 tree tem = SSA_NAME_VALUE (lhs); 332 if (tem) 333 lhs = tem; 334 } 335 336 if (dump_file && (dump_flags & TDF_DETAILS)) 337 { 338 fprintf (dump_file, "FIND: "); 339 print_generic_expr (dump_file, lhs); 340 fprintf (dump_file, "\n"); 341 } 342 343 return lhs; 344 } 345 346 /* Enter condition equivalence P into the hash table. 347 348 This indicates that a conditional expression has a known 349 boolean value. */ 350 351 void 352 avail_exprs_stack::record_cond (cond_equivalence *p) 353 { 354 class expr_hash_elt *element = new expr_hash_elt (&p->cond, p->value); 355 expr_hash_elt **slot; 356 357 slot = m_avail_exprs->find_slot_with_hash (element, element->hash (), INSERT); 358 if (*slot == NULL) 359 { 360 *slot = element; 361 record_expr (element, NULL, '1'); 362 } 363 else 364 delete element; 365 } 366 367 /* Generate a hash value for a pair of expressions. This can be used 368 iteratively by passing a previous result in HSTATE. 369 370 The same hash value is always returned for a given pair of expressions, 371 regardless of the order in which they are presented. This is useful in 372 hashing the operands of commutative functions. */ 373 374 namespace inchash 375 { 376 377 static void 378 add_expr_commutative (const_tree t1, const_tree t2, hash &hstate) 379 { 380 hash one, two; 381 382 inchash::add_expr (t1, one); 383 inchash::add_expr (t2, two); 384 hstate.add_commutative (one, two); 385 } 386 387 /* Compute a hash value for a hashable_expr value EXPR and a 388 previously accumulated hash value VAL. If two hashable_expr 389 values compare equal with hashable_expr_equal_p, they must 390 hash to the same value, given an identical value of VAL. 391 The logic is intended to follow inchash::add_expr in tree.c. */ 392 393 static void 394 add_hashable_expr (const struct hashable_expr *expr, hash &hstate) 395 { 396 switch (expr->kind) 397 { 398 case EXPR_SINGLE: 399 inchash::add_expr (expr->ops.single.rhs, hstate); 400 break; 401 402 case EXPR_UNARY: 403 hstate.add_object (expr->ops.unary.op); 404 405 /* Make sure to include signedness in the hash computation. 406 Don't hash the type, that can lead to having nodes which 407 compare equal according to operand_equal_p, but which 408 have different hash codes. */ 409 if (CONVERT_EXPR_CODE_P (expr->ops.unary.op) 410 || expr->ops.unary.op == NON_LVALUE_EXPR) 411 hstate.add_int (TYPE_UNSIGNED (expr->type)); 412 413 inchash::add_expr (expr->ops.unary.opnd, hstate); 414 break; 415 416 case EXPR_BINARY: 417 hstate.add_object (expr->ops.binary.op); 418 if (commutative_tree_code (expr->ops.binary.op)) 419 inchash::add_expr_commutative (expr->ops.binary.opnd0, 420 expr->ops.binary.opnd1, hstate); 421 else 422 { 423 inchash::add_expr (expr->ops.binary.opnd0, hstate); 424 inchash::add_expr (expr->ops.binary.opnd1, hstate); 425 } 426 break; 427 428 case EXPR_TERNARY: 429 hstate.add_object (expr->ops.ternary.op); 430 if (commutative_ternary_tree_code (expr->ops.ternary.op)) 431 inchash::add_expr_commutative (expr->ops.ternary.opnd0, 432 expr->ops.ternary.opnd1, hstate); 433 else 434 { 435 inchash::add_expr (expr->ops.ternary.opnd0, hstate); 436 inchash::add_expr (expr->ops.ternary.opnd1, hstate); 437 } 438 inchash::add_expr (expr->ops.ternary.opnd2, hstate); 439 break; 440 441 case EXPR_CALL: 442 { 443 size_t i; 444 enum tree_code code = CALL_EXPR; 445 gcall *fn_from; 446 447 hstate.add_object (code); 448 fn_from = expr->ops.call.fn_from; 449 if (gimple_call_internal_p (fn_from)) 450 hstate.merge_hash ((hashval_t) gimple_call_internal_fn (fn_from)); 451 else 452 inchash::add_expr (gimple_call_fn (fn_from), hstate); 453 for (i = 0; i < expr->ops.call.nargs; i++) 454 inchash::add_expr (expr->ops.call.args[i], hstate); 455 } 456 break; 457 458 case EXPR_PHI: 459 { 460 size_t i; 461 462 for (i = 0; i < expr->ops.phi.nargs; i++) 463 inchash::add_expr (expr->ops.phi.args[i], hstate); 464 } 465 break; 466 467 default: 468 gcc_unreachable (); 469 } 470 } 471 472 } 473 474 /* Hashing and equality functions. We compute a value number for expressions 475 using the code of the expression and the SSA numbers of its operands. */ 476 477 static hashval_t 478 avail_expr_hash (class expr_hash_elt *p) 479 { 480 const struct hashable_expr *expr = p->expr (); 481 inchash::hash hstate; 482 483 if (expr->kind == EXPR_SINGLE) 484 { 485 /* T could potentially be a switch index or a goto dest. */ 486 tree t = expr->ops.single.rhs; 487 if (TREE_CODE (t) == MEM_REF || handled_component_p (t)) 488 { 489 /* Make equivalent statements of both these kinds hash together. 490 Dealing with both MEM_REF and ARRAY_REF allows us not to care 491 about equivalence with other statements not considered here. */ 492 bool reverse; 493 poly_int64 offset, size, max_size; 494 tree base = get_ref_base_and_extent (t, &offset, &size, &max_size, 495 &reverse); 496 /* Strictly, we could try to normalize variable-sized accesses too, 497 but here we just deal with the common case. */ 498 if (known_size_p (max_size) 499 && known_eq (size, max_size)) 500 { 501 enum tree_code code = MEM_REF; 502 hstate.add_object (code); 503 inchash::add_expr (base, hstate); 504 hstate.add_object (offset); 505 hstate.add_object (size); 506 return hstate.end (); 507 } 508 } 509 } 510 511 inchash::add_hashable_expr (expr, hstate); 512 513 return hstate.end (); 514 } 515 516 /* Compares trees T0 and T1 to see if they are MEM_REF or ARRAY_REFs equivalent 517 to each other. (That is, they return the value of the same bit of memory.) 518 519 Return TRUE if the two are so equivalent; FALSE if not (which could still 520 mean the two are equivalent by other means). */ 521 522 static bool 523 equal_mem_array_ref_p (tree t0, tree t1) 524 { 525 if (TREE_CODE (t0) != MEM_REF && ! handled_component_p (t0)) 526 return false; 527 if (TREE_CODE (t1) != MEM_REF && ! handled_component_p (t1)) 528 return false; 529 530 if (!types_compatible_p (TREE_TYPE (t0), TREE_TYPE (t1))) 531 return false; 532 bool rev0; 533 poly_int64 off0, sz0, max0; 534 tree base0 = get_ref_base_and_extent (t0, &off0, &sz0, &max0, &rev0); 535 if (!known_size_p (max0) 536 || maybe_ne (sz0, max0)) 537 return false; 538 539 bool rev1; 540 poly_int64 off1, sz1, max1; 541 tree base1 = get_ref_base_and_extent (t1, &off1, &sz1, &max1, &rev1); 542 if (!known_size_p (max1) 543 || maybe_ne (sz1, max1)) 544 return false; 545 546 if (rev0 != rev1) 547 return false; 548 549 /* Types were compatible, so this is a sanity check. */ 550 gcc_assert (known_eq (sz0, sz1)); 551 552 return known_eq (off0, off1) && operand_equal_p (base0, base1, 0); 553 } 554 555 /* Compare two hashable_expr structures for equivalence. They are 556 considered equivalent when the expressions they denote must 557 necessarily be equal. The logic is intended to follow that of 558 operand_equal_p in fold-const.c */ 559 560 static bool 561 hashable_expr_equal_p (const struct hashable_expr *expr0, 562 const struct hashable_expr *expr1) 563 { 564 tree type0 = expr0->type; 565 tree type1 = expr1->type; 566 567 /* If either type is NULL, there is nothing to check. */ 568 if ((type0 == NULL_TREE) ^ (type1 == NULL_TREE)) 569 return false; 570 571 /* If both types don't have the same signedness, precision, and mode, 572 then we can't consider them equal. */ 573 if (type0 != type1 574 && (TREE_CODE (type0) == ERROR_MARK 575 || TREE_CODE (type1) == ERROR_MARK 576 || TYPE_UNSIGNED (type0) != TYPE_UNSIGNED (type1) 577 || TYPE_PRECISION (type0) != TYPE_PRECISION (type1) 578 || TYPE_MODE (type0) != TYPE_MODE (type1))) 579 return false; 580 581 if (expr0->kind != expr1->kind) 582 return false; 583 584 switch (expr0->kind) 585 { 586 case EXPR_SINGLE: 587 return equal_mem_array_ref_p (expr0->ops.single.rhs, 588 expr1->ops.single.rhs) 589 || operand_equal_p (expr0->ops.single.rhs, 590 expr1->ops.single.rhs, 0); 591 case EXPR_UNARY: 592 if (expr0->ops.unary.op != expr1->ops.unary.op) 593 return false; 594 595 if ((CONVERT_EXPR_CODE_P (expr0->ops.unary.op) 596 || expr0->ops.unary.op == NON_LVALUE_EXPR) 597 && TYPE_UNSIGNED (expr0->type) != TYPE_UNSIGNED (expr1->type)) 598 return false; 599 600 return operand_equal_p (expr0->ops.unary.opnd, 601 expr1->ops.unary.opnd, 0); 602 603 case EXPR_BINARY: 604 if (expr0->ops.binary.op != expr1->ops.binary.op) 605 return false; 606 607 if (operand_equal_p (expr0->ops.binary.opnd0, 608 expr1->ops.binary.opnd0, 0) 609 && operand_equal_p (expr0->ops.binary.opnd1, 610 expr1->ops.binary.opnd1, 0)) 611 return true; 612 613 /* For commutative ops, allow the other order. */ 614 return (commutative_tree_code (expr0->ops.binary.op) 615 && operand_equal_p (expr0->ops.binary.opnd0, 616 expr1->ops.binary.opnd1, 0) 617 && operand_equal_p (expr0->ops.binary.opnd1, 618 expr1->ops.binary.opnd0, 0)); 619 620 case EXPR_TERNARY: 621 if (expr0->ops.ternary.op != expr1->ops.ternary.op 622 || !operand_equal_p (expr0->ops.ternary.opnd2, 623 expr1->ops.ternary.opnd2, 0)) 624 return false; 625 626 /* BIT_INSERT_EXPR has an implict operand as the type precision 627 of op1. Need to check to make sure they are the same. */ 628 if (expr0->ops.ternary.op == BIT_INSERT_EXPR 629 && TREE_CODE (expr0->ops.ternary.opnd1) == INTEGER_CST 630 && TREE_CODE (expr1->ops.ternary.opnd1) == INTEGER_CST 631 && TYPE_PRECISION (TREE_TYPE (expr0->ops.ternary.opnd1)) 632 != TYPE_PRECISION (TREE_TYPE (expr1->ops.ternary.opnd1))) 633 return false; 634 635 if (operand_equal_p (expr0->ops.ternary.opnd0, 636 expr1->ops.ternary.opnd0, 0) 637 && operand_equal_p (expr0->ops.ternary.opnd1, 638 expr1->ops.ternary.opnd1, 0)) 639 return true; 640 641 /* For commutative ops, allow the other order. */ 642 return (commutative_ternary_tree_code (expr0->ops.ternary.op) 643 && operand_equal_p (expr0->ops.ternary.opnd0, 644 expr1->ops.ternary.opnd1, 0) 645 && operand_equal_p (expr0->ops.ternary.opnd1, 646 expr1->ops.ternary.opnd0, 0)); 647 648 case EXPR_CALL: 649 { 650 size_t i; 651 652 /* If the calls are to different functions, then they 653 clearly cannot be equal. */ 654 if (!gimple_call_same_target_p (expr0->ops.call.fn_from, 655 expr1->ops.call.fn_from)) 656 return false; 657 658 if (! expr0->ops.call.pure) 659 return false; 660 661 if (expr0->ops.call.nargs != expr1->ops.call.nargs) 662 return false; 663 664 for (i = 0; i < expr0->ops.call.nargs; i++) 665 if (! operand_equal_p (expr0->ops.call.args[i], 666 expr1->ops.call.args[i], 0)) 667 return false; 668 669 if (stmt_could_throw_p (expr0->ops.call.fn_from)) 670 { 671 int lp0 = lookup_stmt_eh_lp (expr0->ops.call.fn_from); 672 int lp1 = lookup_stmt_eh_lp (expr1->ops.call.fn_from); 673 if ((lp0 > 0 || lp1 > 0) && lp0 != lp1) 674 return false; 675 } 676 677 return true; 678 } 679 680 case EXPR_PHI: 681 { 682 size_t i; 683 684 if (expr0->ops.phi.nargs != expr1->ops.phi.nargs) 685 return false; 686 687 for (i = 0; i < expr0->ops.phi.nargs; i++) 688 if (! operand_equal_p (expr0->ops.phi.args[i], 689 expr1->ops.phi.args[i], 0)) 690 return false; 691 692 return true; 693 } 694 695 default: 696 gcc_unreachable (); 697 } 698 } 699 700 /* Given a statement STMT, construct a hash table element. */ 701 702 expr_hash_elt::expr_hash_elt (gimple *stmt, tree orig_lhs) 703 { 704 enum gimple_code code = gimple_code (stmt); 705 struct hashable_expr *expr = this->expr (); 706 707 if (code == GIMPLE_ASSIGN) 708 { 709 enum tree_code subcode = gimple_assign_rhs_code (stmt); 710 711 switch (get_gimple_rhs_class (subcode)) 712 { 713 case GIMPLE_SINGLE_RHS: 714 expr->kind = EXPR_SINGLE; 715 expr->type = TREE_TYPE (gimple_assign_rhs1 (stmt)); 716 expr->ops.single.rhs = gimple_assign_rhs1 (stmt); 717 break; 718 case GIMPLE_UNARY_RHS: 719 expr->kind = EXPR_UNARY; 720 expr->type = TREE_TYPE (gimple_assign_lhs (stmt)); 721 if (CONVERT_EXPR_CODE_P (subcode)) 722 subcode = NOP_EXPR; 723 expr->ops.unary.op = subcode; 724 expr->ops.unary.opnd = gimple_assign_rhs1 (stmt); 725 break; 726 case GIMPLE_BINARY_RHS: 727 expr->kind = EXPR_BINARY; 728 expr->type = TREE_TYPE (gimple_assign_lhs (stmt)); 729 expr->ops.binary.op = subcode; 730 expr->ops.binary.opnd0 = gimple_assign_rhs1 (stmt); 731 expr->ops.binary.opnd1 = gimple_assign_rhs2 (stmt); 732 break; 733 case GIMPLE_TERNARY_RHS: 734 expr->kind = EXPR_TERNARY; 735 expr->type = TREE_TYPE (gimple_assign_lhs (stmt)); 736 expr->ops.ternary.op = subcode; 737 expr->ops.ternary.opnd0 = gimple_assign_rhs1 (stmt); 738 expr->ops.ternary.opnd1 = gimple_assign_rhs2 (stmt); 739 expr->ops.ternary.opnd2 = gimple_assign_rhs3 (stmt); 740 break; 741 default: 742 gcc_unreachable (); 743 } 744 } 745 else if (code == GIMPLE_COND) 746 { 747 expr->type = boolean_type_node; 748 expr->kind = EXPR_BINARY; 749 expr->ops.binary.op = gimple_cond_code (stmt); 750 expr->ops.binary.opnd0 = gimple_cond_lhs (stmt); 751 expr->ops.binary.opnd1 = gimple_cond_rhs (stmt); 752 } 753 else if (gcall *call_stmt = dyn_cast <gcall *> (stmt)) 754 { 755 size_t nargs = gimple_call_num_args (call_stmt); 756 size_t i; 757 758 gcc_assert (gimple_call_lhs (call_stmt)); 759 760 expr->type = TREE_TYPE (gimple_call_lhs (call_stmt)); 761 expr->kind = EXPR_CALL; 762 expr->ops.call.fn_from = call_stmt; 763 764 if (gimple_call_flags (call_stmt) & (ECF_CONST | ECF_PURE)) 765 expr->ops.call.pure = true; 766 else 767 expr->ops.call.pure = false; 768 769 expr->ops.call.nargs = nargs; 770 expr->ops.call.args = XCNEWVEC (tree, nargs); 771 for (i = 0; i < nargs; i++) 772 expr->ops.call.args[i] = gimple_call_arg (call_stmt, i); 773 } 774 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt)) 775 { 776 expr->type = TREE_TYPE (gimple_switch_index (swtch_stmt)); 777 expr->kind = EXPR_SINGLE; 778 expr->ops.single.rhs = gimple_switch_index (swtch_stmt); 779 } 780 else if (code == GIMPLE_GOTO) 781 { 782 expr->type = TREE_TYPE (gimple_goto_dest (stmt)); 783 expr->kind = EXPR_SINGLE; 784 expr->ops.single.rhs = gimple_goto_dest (stmt); 785 } 786 else if (code == GIMPLE_PHI) 787 { 788 size_t nargs = gimple_phi_num_args (stmt); 789 size_t i; 790 791 expr->type = TREE_TYPE (gimple_phi_result (stmt)); 792 expr->kind = EXPR_PHI; 793 expr->ops.phi.nargs = nargs; 794 expr->ops.phi.args = XCNEWVEC (tree, nargs); 795 for (i = 0; i < nargs; i++) 796 expr->ops.phi.args[i] = gimple_phi_arg_def (stmt, i); 797 } 798 else 799 gcc_unreachable (); 800 801 m_lhs = orig_lhs; 802 m_vop = gimple_vuse (stmt); 803 m_hash = avail_expr_hash (this); 804 m_stamp = this; 805 } 806 807 /* Given a hashable_expr expression ORIG and an ORIG_LHS, 808 construct a hash table element. */ 809 810 expr_hash_elt::expr_hash_elt (struct hashable_expr *orig, tree orig_lhs) 811 { 812 m_expr = *orig; 813 m_lhs = orig_lhs; 814 m_vop = NULL_TREE; 815 m_hash = avail_expr_hash (this); 816 m_stamp = this; 817 } 818 819 /* Copy constructor for a hash table element. */ 820 821 expr_hash_elt::expr_hash_elt (class expr_hash_elt &old_elt) 822 { 823 m_expr = old_elt.m_expr; 824 m_lhs = old_elt.m_lhs; 825 m_vop = old_elt.m_vop; 826 m_hash = old_elt.m_hash; 827 m_stamp = this; 828 829 /* Now deep copy the malloc'd space for CALL and PHI args. */ 830 if (old_elt.m_expr.kind == EXPR_CALL) 831 { 832 size_t nargs = old_elt.m_expr.ops.call.nargs; 833 size_t i; 834 835 m_expr.ops.call.args = XCNEWVEC (tree, nargs); 836 for (i = 0; i < nargs; i++) 837 m_expr.ops.call.args[i] = old_elt.m_expr.ops.call.args[i]; 838 } 839 else if (old_elt.m_expr.kind == EXPR_PHI) 840 { 841 size_t nargs = old_elt.m_expr.ops.phi.nargs; 842 size_t i; 843 844 m_expr.ops.phi.args = XCNEWVEC (tree, nargs); 845 for (i = 0; i < nargs; i++) 846 m_expr.ops.phi.args[i] = old_elt.m_expr.ops.phi.args[i]; 847 } 848 } 849 850 /* Calls and PHIs have a variable number of arguments that are allocated 851 on the heap. Thus we have to have a special dtor to release them. */ 852 853 expr_hash_elt::~expr_hash_elt () 854 { 855 if (m_expr.kind == EXPR_CALL) 856 free (m_expr.ops.call.args); 857 else if (m_expr.kind == EXPR_PHI) 858 free (m_expr.ops.phi.args); 859 } 860 861 /* Print a diagnostic dump of an expression hash table entry. */ 862 863 void 864 expr_hash_elt::print (FILE *stream) 865 { 866 fprintf (stream, "STMT "); 867 868 if (m_lhs) 869 { 870 print_generic_expr (stream, m_lhs); 871 fprintf (stream, " = "); 872 } 873 874 switch (m_expr.kind) 875 { 876 case EXPR_SINGLE: 877 print_generic_expr (stream, m_expr.ops.single.rhs); 878 break; 879 880 case EXPR_UNARY: 881 fprintf (stream, "%s ", get_tree_code_name (m_expr.ops.unary.op)); 882 print_generic_expr (stream, m_expr.ops.unary.opnd); 883 break; 884 885 case EXPR_BINARY: 886 print_generic_expr (stream, m_expr.ops.binary.opnd0); 887 fprintf (stream, " %s ", get_tree_code_name (m_expr.ops.binary.op)); 888 print_generic_expr (stream, m_expr.ops.binary.opnd1); 889 break; 890 891 case EXPR_TERNARY: 892 fprintf (stream, " %s <", get_tree_code_name (m_expr.ops.ternary.op)); 893 print_generic_expr (stream, m_expr.ops.ternary.opnd0); 894 fputs (", ", stream); 895 print_generic_expr (stream, m_expr.ops.ternary.opnd1); 896 fputs (", ", stream); 897 print_generic_expr (stream, m_expr.ops.ternary.opnd2); 898 fputs (">", stream); 899 break; 900 901 case EXPR_CALL: 902 { 903 size_t i; 904 size_t nargs = m_expr.ops.call.nargs; 905 gcall *fn_from; 906 907 fn_from = m_expr.ops.call.fn_from; 908 if (gimple_call_internal_p (fn_from)) 909 fputs (internal_fn_name (gimple_call_internal_fn (fn_from)), 910 stream); 911 else 912 print_generic_expr (stream, gimple_call_fn (fn_from)); 913 fprintf (stream, " ("); 914 for (i = 0; i < nargs; i++) 915 { 916 print_generic_expr (stream, m_expr.ops.call.args[i]); 917 if (i + 1 < nargs) 918 fprintf (stream, ", "); 919 } 920 fprintf (stream, ")"); 921 } 922 break; 923 924 case EXPR_PHI: 925 { 926 size_t i; 927 size_t nargs = m_expr.ops.phi.nargs; 928 929 fprintf (stream, "PHI <"); 930 for (i = 0; i < nargs; i++) 931 { 932 print_generic_expr (stream, m_expr.ops.phi.args[i]); 933 if (i + 1 < nargs) 934 fprintf (stream, ", "); 935 } 936 fprintf (stream, ">"); 937 } 938 break; 939 } 940 941 if (m_vop) 942 { 943 fprintf (stream, " with "); 944 print_generic_expr (stream, m_vop); 945 } 946 947 fprintf (stream, "\n"); 948 } 949 950 /* Pop entries off the stack until we hit the NULL marker. 951 For each entry popped, use the SRC/DEST pair to restore 952 SRC to its prior value. */ 953 954 void 955 const_and_copies::pop_to_marker (void) 956 { 957 while (m_stack.length () > 0) 958 { 959 tree prev_value, dest; 960 961 dest = m_stack.pop (); 962 963 /* A NULL value indicates we should stop unwinding, otherwise 964 pop off the next entry as they're recorded in pairs. */ 965 if (dest == NULL) 966 break; 967 968 if (dump_file && (dump_flags & TDF_DETAILS)) 969 { 970 fprintf (dump_file, "<<<< COPY "); 971 print_generic_expr (dump_file, dest); 972 fprintf (dump_file, " = "); 973 print_generic_expr (dump_file, SSA_NAME_VALUE (dest)); 974 fprintf (dump_file, "\n"); 975 } 976 977 prev_value = m_stack.pop (); 978 set_ssa_name_value (dest, prev_value); 979 } 980 } 981 982 /* Record that X has the value Y and that X's previous value is PREV_X. 983 984 This variant does not follow the value chain for Y. */ 985 986 void 987 const_and_copies::record_const_or_copy_raw (tree x, tree y, tree prev_x) 988 { 989 if (dump_file && (dump_flags & TDF_DETAILS)) 990 { 991 fprintf (dump_file, "0>>> COPY "); 992 print_generic_expr (dump_file, x); 993 fprintf (dump_file, " = "); 994 print_generic_expr (dump_file, y); 995 fprintf (dump_file, "\n"); 996 } 997 998 set_ssa_name_value (x, y); 999 m_stack.reserve (2); 1000 m_stack.quick_push (prev_x); 1001 m_stack.quick_push (x); 1002 } 1003 1004 /* Record that X has the value Y. */ 1005 1006 void 1007 const_and_copies::record_const_or_copy (tree x, tree y) 1008 { 1009 record_const_or_copy (x, y, SSA_NAME_VALUE (x)); 1010 } 1011 1012 /* Record that X has the value Y and that X's previous value is PREV_X. 1013 1014 This variant follow's Y value chain. */ 1015 1016 void 1017 const_and_copies::record_const_or_copy (tree x, tree y, tree prev_x) 1018 { 1019 /* Y may be NULL if we are invalidating entries in the table. */ 1020 if (y && TREE_CODE (y) == SSA_NAME) 1021 { 1022 tree tmp = SSA_NAME_VALUE (y); 1023 y = tmp ? tmp : y; 1024 } 1025 1026 record_const_or_copy_raw (x, y, prev_x); 1027 } 1028 1029 bool 1030 expr_elt_hasher::equal (const value_type &p1, const compare_type &p2) 1031 { 1032 const struct hashable_expr *expr1 = p1->expr (); 1033 const struct expr_hash_elt *stamp1 = p1->stamp (); 1034 const struct hashable_expr *expr2 = p2->expr (); 1035 const struct expr_hash_elt *stamp2 = p2->stamp (); 1036 1037 /* This case should apply only when removing entries from the table. */ 1038 if (stamp1 == stamp2) 1039 return true; 1040 1041 if (p1->hash () != p2->hash ()) 1042 return false; 1043 1044 /* In case of a collision, both RHS have to be identical and have the 1045 same VUSE operands. */ 1046 if (hashable_expr_equal_p (expr1, expr2) 1047 && types_compatible_p (expr1->type, expr2->type)) 1048 return true; 1049 1050 return false; 1051 } 1052 1053 /* Given a conditional expression COND as a tree, initialize 1054 a hashable_expr expression EXPR. The conditional must be a 1055 comparison or logical negation. A constant or a variable is 1056 not permitted. */ 1057 1058 void 1059 initialize_expr_from_cond (tree cond, struct hashable_expr *expr) 1060 { 1061 expr->type = boolean_type_node; 1062 1063 if (COMPARISON_CLASS_P (cond)) 1064 { 1065 expr->kind = EXPR_BINARY; 1066 expr->ops.binary.op = TREE_CODE (cond); 1067 expr->ops.binary.opnd0 = TREE_OPERAND (cond, 0); 1068 expr->ops.binary.opnd1 = TREE_OPERAND (cond, 1); 1069 } 1070 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR) 1071 { 1072 expr->kind = EXPR_UNARY; 1073 expr->ops.unary.op = TRUTH_NOT_EXPR; 1074 expr->ops.unary.opnd = TREE_OPERAND (cond, 0); 1075 } 1076 else 1077 gcc_unreachable (); 1078 } 1079 1080 /* Build a cond_equivalence record indicating that the comparison 1081 CODE holds between operands OP0 and OP1 and push it to **P. */ 1082 1083 static void 1084 build_and_record_new_cond (enum tree_code code, 1085 tree op0, tree op1, 1086 vec<cond_equivalence> *p, 1087 bool val = true) 1088 { 1089 cond_equivalence c; 1090 struct hashable_expr *cond = &c.cond; 1091 1092 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison); 1093 1094 cond->type = boolean_type_node; 1095 cond->kind = EXPR_BINARY; 1096 cond->ops.binary.op = code; 1097 cond->ops.binary.opnd0 = op0; 1098 cond->ops.binary.opnd1 = op1; 1099 1100 c.value = val ? boolean_true_node : boolean_false_node; 1101 p->safe_push (c); 1102 } 1103 1104 /* Record that COND is true and INVERTED is false into the edge information 1105 structure. Also record that any conditions dominated by COND are true 1106 as well. 1107 1108 For example, if a < b is true, then a <= b must also be true. */ 1109 1110 void 1111 record_conditions (vec<cond_equivalence> *p, tree cond, tree inverted) 1112 { 1113 tree op0, op1; 1114 cond_equivalence c; 1115 1116 if (!COMPARISON_CLASS_P (cond)) 1117 return; 1118 1119 op0 = TREE_OPERAND (cond, 0); 1120 op1 = TREE_OPERAND (cond, 1); 1121 1122 switch (TREE_CODE (cond)) 1123 { 1124 case LT_EXPR: 1125 case GT_EXPR: 1126 if (FLOAT_TYPE_P (TREE_TYPE (op0))) 1127 { 1128 build_and_record_new_cond (ORDERED_EXPR, op0, op1, p); 1129 build_and_record_new_cond (LTGT_EXPR, op0, op1, p); 1130 } 1131 1132 build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR 1133 ? LE_EXPR : GE_EXPR), 1134 op0, op1, p); 1135 build_and_record_new_cond (NE_EXPR, op0, op1, p); 1136 build_and_record_new_cond (EQ_EXPR, op0, op1, p, false); 1137 break; 1138 1139 case GE_EXPR: 1140 case LE_EXPR: 1141 if (FLOAT_TYPE_P (TREE_TYPE (op0))) 1142 { 1143 build_and_record_new_cond (ORDERED_EXPR, op0, op1, p); 1144 } 1145 break; 1146 1147 case EQ_EXPR: 1148 if (FLOAT_TYPE_P (TREE_TYPE (op0))) 1149 { 1150 build_and_record_new_cond (ORDERED_EXPR, op0, op1, p); 1151 } 1152 build_and_record_new_cond (LE_EXPR, op0, op1, p); 1153 build_and_record_new_cond (GE_EXPR, op0, op1, p); 1154 break; 1155 1156 case UNORDERED_EXPR: 1157 build_and_record_new_cond (NE_EXPR, op0, op1, p); 1158 build_and_record_new_cond (UNLE_EXPR, op0, op1, p); 1159 build_and_record_new_cond (UNGE_EXPR, op0, op1, p); 1160 build_and_record_new_cond (UNEQ_EXPR, op0, op1, p); 1161 build_and_record_new_cond (UNLT_EXPR, op0, op1, p); 1162 build_and_record_new_cond (UNGT_EXPR, op0, op1, p); 1163 break; 1164 1165 case UNLT_EXPR: 1166 case UNGT_EXPR: 1167 build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR 1168 ? UNLE_EXPR : UNGE_EXPR), 1169 op0, op1, p); 1170 build_and_record_new_cond (NE_EXPR, op0, op1, p); 1171 break; 1172 1173 case UNEQ_EXPR: 1174 build_and_record_new_cond (UNLE_EXPR, op0, op1, p); 1175 build_and_record_new_cond (UNGE_EXPR, op0, op1, p); 1176 break; 1177 1178 case LTGT_EXPR: 1179 build_and_record_new_cond (NE_EXPR, op0, op1, p); 1180 build_and_record_new_cond (ORDERED_EXPR, op0, op1, p); 1181 break; 1182 1183 default: 1184 break; 1185 } 1186 1187 /* Now store the original true and false conditions into the first 1188 two slots. */ 1189 initialize_expr_from_cond (cond, &c.cond); 1190 c.value = boolean_true_node; 1191 p->safe_push (c); 1192 1193 /* It is possible for INVERTED to be the negation of a comparison, 1194 and not a valid RHS or GIMPLE_COND condition. This happens because 1195 invert_truthvalue may return such an expression when asked to invert 1196 a floating-point comparison. These comparisons are not assumed to 1197 obey the trichotomy law. */ 1198 initialize_expr_from_cond (inverted, &c.cond); 1199 c.value = boolean_false_node; 1200 p->safe_push (c); 1201 } 1202