1 /* Header file for SSA dominator optimizations. 2 Copyright (C) 2013-2016 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 37 static bool hashable_expr_equal_p (const struct hashable_expr *, 38 const struct hashable_expr *); 39 40 /* Initialize local stacks for this optimizer and record equivalences 41 upon entry to BB. Equivalences can come from the edge traversed to 42 reach BB or they may come from PHI nodes at the start of BB. */ 43 44 /* Pop items off the unwinding stack, removing each from the hash table 45 until a marker is encountered. */ 46 47 void 48 avail_exprs_stack::pop_to_marker () 49 { 50 /* Remove all the expressions made available in this block. */ 51 while (m_stack.length () > 0) 52 { 53 std::pair<expr_hash_elt_t, expr_hash_elt_t> victim = m_stack.pop (); 54 expr_hash_elt **slot; 55 56 if (victim.first == NULL) 57 break; 58 59 /* This must precede the actual removal from the hash table, 60 as ELEMENT and the table entry may share a call argument 61 vector which will be freed during removal. */ 62 if (dump_file && (dump_flags & TDF_DETAILS)) 63 { 64 fprintf (dump_file, "<<<< "); 65 victim.first->print (dump_file); 66 } 67 68 slot = m_avail_exprs->find_slot (victim.first, NO_INSERT); 69 gcc_assert (slot && *slot == victim.first); 70 if (victim.second != NULL) 71 { 72 delete *slot; 73 *slot = victim.second; 74 } 75 else 76 m_avail_exprs->clear_slot (slot); 77 } 78 } 79 80 /* Add <ELT1,ELT2> to the unwinding stack so they can be later removed 81 from the hash table. */ 82 83 void 84 avail_exprs_stack::record_expr (class expr_hash_elt *elt1, 85 class expr_hash_elt *elt2, 86 char type) 87 { 88 if (elt1 && dump_file && (dump_flags & TDF_DETAILS)) 89 { 90 fprintf (dump_file, "%c>>> ", type); 91 elt1->print (dump_file); 92 } 93 94 m_stack.safe_push (std::pair<expr_hash_elt_t, expr_hash_elt_t> (elt1, elt2)); 95 } 96 97 /* Generate a hash value for a pair of expressions. This can be used 98 iteratively by passing a previous result in HSTATE. 99 100 The same hash value is always returned for a given pair of expressions, 101 regardless of the order in which they are presented. This is useful in 102 hashing the operands of commutative functions. */ 103 104 namespace inchash 105 { 106 107 static void 108 add_expr_commutative (const_tree t1, const_tree t2, hash &hstate) 109 { 110 hash one, two; 111 112 inchash::add_expr (t1, one); 113 inchash::add_expr (t2, two); 114 hstate.add_commutative (one, two); 115 } 116 117 /* Compute a hash value for a hashable_expr value EXPR and a 118 previously accumulated hash value VAL. If two hashable_expr 119 values compare equal with hashable_expr_equal_p, they must 120 hash to the same value, given an identical value of VAL. 121 The logic is intended to follow inchash::add_expr in tree.c. */ 122 123 static void 124 add_hashable_expr (const struct hashable_expr *expr, hash &hstate) 125 { 126 switch (expr->kind) 127 { 128 case EXPR_SINGLE: 129 inchash::add_expr (expr->ops.single.rhs, hstate); 130 break; 131 132 case EXPR_UNARY: 133 hstate.add_object (expr->ops.unary.op); 134 135 /* Make sure to include signedness in the hash computation. 136 Don't hash the type, that can lead to having nodes which 137 compare equal according to operand_equal_p, but which 138 have different hash codes. */ 139 if (CONVERT_EXPR_CODE_P (expr->ops.unary.op) 140 || expr->ops.unary.op == NON_LVALUE_EXPR) 141 hstate.add_int (TYPE_UNSIGNED (expr->type)); 142 143 inchash::add_expr (expr->ops.unary.opnd, hstate); 144 break; 145 146 case EXPR_BINARY: 147 hstate.add_object (expr->ops.binary.op); 148 if (commutative_tree_code (expr->ops.binary.op)) 149 inchash::add_expr_commutative (expr->ops.binary.opnd0, 150 expr->ops.binary.opnd1, hstate); 151 else 152 { 153 inchash::add_expr (expr->ops.binary.opnd0, hstate); 154 inchash::add_expr (expr->ops.binary.opnd1, hstate); 155 } 156 break; 157 158 case EXPR_TERNARY: 159 hstate.add_object (expr->ops.ternary.op); 160 if (commutative_ternary_tree_code (expr->ops.ternary.op)) 161 inchash::add_expr_commutative (expr->ops.ternary.opnd0, 162 expr->ops.ternary.opnd1, hstate); 163 else 164 { 165 inchash::add_expr (expr->ops.ternary.opnd0, hstate); 166 inchash::add_expr (expr->ops.ternary.opnd1, hstate); 167 } 168 inchash::add_expr (expr->ops.ternary.opnd2, hstate); 169 break; 170 171 case EXPR_CALL: 172 { 173 size_t i; 174 enum tree_code code = CALL_EXPR; 175 gcall *fn_from; 176 177 hstate.add_object (code); 178 fn_from = expr->ops.call.fn_from; 179 if (gimple_call_internal_p (fn_from)) 180 hstate.merge_hash ((hashval_t) gimple_call_internal_fn (fn_from)); 181 else 182 inchash::add_expr (gimple_call_fn (fn_from), hstate); 183 for (i = 0; i < expr->ops.call.nargs; i++) 184 inchash::add_expr (expr->ops.call.args[i], hstate); 185 } 186 break; 187 188 case EXPR_PHI: 189 { 190 size_t i; 191 192 for (i = 0; i < expr->ops.phi.nargs; i++) 193 inchash::add_expr (expr->ops.phi.args[i], hstate); 194 } 195 break; 196 197 default: 198 gcc_unreachable (); 199 } 200 } 201 202 } 203 204 /* Hashing and equality functions. We compute a value number for expressions 205 using the code of the expression and the SSA numbers of its operands. */ 206 207 static hashval_t 208 avail_expr_hash (class expr_hash_elt *p) 209 { 210 const struct hashable_expr *expr = p->expr (); 211 inchash::hash hstate; 212 213 if (expr->kind == EXPR_SINGLE) 214 { 215 /* T could potentially be a switch index or a goto dest. */ 216 tree t = expr->ops.single.rhs; 217 if (TREE_CODE (t) == MEM_REF || handled_component_p (t)) 218 { 219 /* Make equivalent statements of both these kinds hash together. 220 Dealing with both MEM_REF and ARRAY_REF allows us not to care 221 about equivalence with other statements not considered here. */ 222 bool reverse; 223 HOST_WIDE_INT offset, size, max_size; 224 tree base = get_ref_base_and_extent (t, &offset, &size, &max_size, 225 &reverse); 226 /* Strictly, we could try to normalize variable-sized accesses too, 227 but here we just deal with the common case. */ 228 if (size != -1 229 && size == max_size) 230 { 231 enum tree_code code = MEM_REF; 232 hstate.add_object (code); 233 inchash::add_expr (base, hstate); 234 hstate.add_object (offset); 235 hstate.add_object (size); 236 return hstate.end (); 237 } 238 } 239 } 240 241 inchash::add_hashable_expr (expr, hstate); 242 243 return hstate.end (); 244 } 245 246 /* Compares trees T0 and T1 to see if they are MEM_REF or ARRAY_REFs equivalent 247 to each other. (That is, they return the value of the same bit of memory.) 248 249 Return TRUE if the two are so equivalent; FALSE if not (which could still 250 mean the two are equivalent by other means). */ 251 252 static bool 253 equal_mem_array_ref_p (tree t0, tree t1) 254 { 255 if (TREE_CODE (t0) != MEM_REF && ! handled_component_p (t0)) 256 return false; 257 if (TREE_CODE (t1) != MEM_REF && ! handled_component_p (t1)) 258 return false; 259 260 if (!types_compatible_p (TREE_TYPE (t0), TREE_TYPE (t1))) 261 return false; 262 bool rev0; 263 HOST_WIDE_INT off0, sz0, max0; 264 tree base0 = get_ref_base_and_extent (t0, &off0, &sz0, &max0, &rev0); 265 if (sz0 == -1 266 || sz0 != max0) 267 return false; 268 269 bool rev1; 270 HOST_WIDE_INT off1, sz1, max1; 271 tree base1 = get_ref_base_and_extent (t1, &off1, &sz1, &max1, &rev1); 272 if (sz1 == -1 273 || sz1 != max1) 274 return false; 275 276 if (rev0 != rev1) 277 return false; 278 279 /* Types were compatible, so this is a sanity check. */ 280 gcc_assert (sz0 == sz1); 281 282 return (off0 == off1) && operand_equal_p (base0, base1, 0); 283 } 284 285 /* Compare two hashable_expr structures for equivalence. They are 286 considered equivalent when the expressions they denote must 287 necessarily be equal. The logic is intended to follow that of 288 operand_equal_p in fold-const.c */ 289 290 static bool 291 hashable_expr_equal_p (const struct hashable_expr *expr0, 292 const struct hashable_expr *expr1) 293 { 294 tree type0 = expr0->type; 295 tree type1 = expr1->type; 296 297 /* If either type is NULL, there is nothing to check. */ 298 if ((type0 == NULL_TREE) ^ (type1 == NULL_TREE)) 299 return false; 300 301 /* If both types don't have the same signedness, precision, and mode, 302 then we can't consider them equal. */ 303 if (type0 != type1 304 && (TREE_CODE (type0) == ERROR_MARK 305 || TREE_CODE (type1) == ERROR_MARK 306 || TYPE_UNSIGNED (type0) != TYPE_UNSIGNED (type1) 307 || TYPE_PRECISION (type0) != TYPE_PRECISION (type1) 308 || TYPE_MODE (type0) != TYPE_MODE (type1))) 309 return false; 310 311 if (expr0->kind != expr1->kind) 312 return false; 313 314 switch (expr0->kind) 315 { 316 case EXPR_SINGLE: 317 return equal_mem_array_ref_p (expr0->ops.single.rhs, 318 expr1->ops.single.rhs) 319 || operand_equal_p (expr0->ops.single.rhs, 320 expr1->ops.single.rhs, 0); 321 case EXPR_UNARY: 322 if (expr0->ops.unary.op != expr1->ops.unary.op) 323 return false; 324 325 if ((CONVERT_EXPR_CODE_P (expr0->ops.unary.op) 326 || expr0->ops.unary.op == NON_LVALUE_EXPR) 327 && TYPE_UNSIGNED (expr0->type) != TYPE_UNSIGNED (expr1->type)) 328 return false; 329 330 return operand_equal_p (expr0->ops.unary.opnd, 331 expr1->ops.unary.opnd, 0); 332 333 case EXPR_BINARY: 334 if (expr0->ops.binary.op != expr1->ops.binary.op) 335 return false; 336 337 if (operand_equal_p (expr0->ops.binary.opnd0, 338 expr1->ops.binary.opnd0, 0) 339 && operand_equal_p (expr0->ops.binary.opnd1, 340 expr1->ops.binary.opnd1, 0)) 341 return true; 342 343 /* For commutative ops, allow the other order. */ 344 return (commutative_tree_code (expr0->ops.binary.op) 345 && operand_equal_p (expr0->ops.binary.opnd0, 346 expr1->ops.binary.opnd1, 0) 347 && operand_equal_p (expr0->ops.binary.opnd1, 348 expr1->ops.binary.opnd0, 0)); 349 350 case EXPR_TERNARY: 351 if (expr0->ops.ternary.op != expr1->ops.ternary.op 352 || !operand_equal_p (expr0->ops.ternary.opnd2, 353 expr1->ops.ternary.opnd2, 0)) 354 return false; 355 356 if (operand_equal_p (expr0->ops.ternary.opnd0, 357 expr1->ops.ternary.opnd0, 0) 358 && operand_equal_p (expr0->ops.ternary.opnd1, 359 expr1->ops.ternary.opnd1, 0)) 360 return true; 361 362 /* For commutative ops, allow the other order. */ 363 return (commutative_ternary_tree_code (expr0->ops.ternary.op) 364 && operand_equal_p (expr0->ops.ternary.opnd0, 365 expr1->ops.ternary.opnd1, 0) 366 && operand_equal_p (expr0->ops.ternary.opnd1, 367 expr1->ops.ternary.opnd0, 0)); 368 369 case EXPR_CALL: 370 { 371 size_t i; 372 373 /* If the calls are to different functions, then they 374 clearly cannot be equal. */ 375 if (!gimple_call_same_target_p (expr0->ops.call.fn_from, 376 expr1->ops.call.fn_from)) 377 return false; 378 379 if (! expr0->ops.call.pure) 380 return false; 381 382 if (expr0->ops.call.nargs != expr1->ops.call.nargs) 383 return false; 384 385 for (i = 0; i < expr0->ops.call.nargs; i++) 386 if (! operand_equal_p (expr0->ops.call.args[i], 387 expr1->ops.call.args[i], 0)) 388 return false; 389 390 if (stmt_could_throw_p (expr0->ops.call.fn_from)) 391 { 392 int lp0 = lookup_stmt_eh_lp (expr0->ops.call.fn_from); 393 int lp1 = lookup_stmt_eh_lp (expr1->ops.call.fn_from); 394 if ((lp0 > 0 || lp1 > 0) && lp0 != lp1) 395 return false; 396 } 397 398 return true; 399 } 400 401 case EXPR_PHI: 402 { 403 size_t i; 404 405 if (expr0->ops.phi.nargs != expr1->ops.phi.nargs) 406 return false; 407 408 for (i = 0; i < expr0->ops.phi.nargs; i++) 409 if (! operand_equal_p (expr0->ops.phi.args[i], 410 expr1->ops.phi.args[i], 0)) 411 return false; 412 413 return true; 414 } 415 416 default: 417 gcc_unreachable (); 418 } 419 } 420 421 /* Given a statement STMT, construct a hash table element. */ 422 423 expr_hash_elt::expr_hash_elt (gimple *stmt, tree orig_lhs) 424 { 425 enum gimple_code code = gimple_code (stmt); 426 struct hashable_expr *expr = this->expr (); 427 428 if (code == GIMPLE_ASSIGN) 429 { 430 enum tree_code subcode = gimple_assign_rhs_code (stmt); 431 432 switch (get_gimple_rhs_class (subcode)) 433 { 434 case GIMPLE_SINGLE_RHS: 435 expr->kind = EXPR_SINGLE; 436 expr->type = TREE_TYPE (gimple_assign_rhs1 (stmt)); 437 expr->ops.single.rhs = gimple_assign_rhs1 (stmt); 438 break; 439 case GIMPLE_UNARY_RHS: 440 expr->kind = EXPR_UNARY; 441 expr->type = TREE_TYPE (gimple_assign_lhs (stmt)); 442 if (CONVERT_EXPR_CODE_P (subcode)) 443 subcode = NOP_EXPR; 444 expr->ops.unary.op = subcode; 445 expr->ops.unary.opnd = gimple_assign_rhs1 (stmt); 446 break; 447 case GIMPLE_BINARY_RHS: 448 expr->kind = EXPR_BINARY; 449 expr->type = TREE_TYPE (gimple_assign_lhs (stmt)); 450 expr->ops.binary.op = subcode; 451 expr->ops.binary.opnd0 = gimple_assign_rhs1 (stmt); 452 expr->ops.binary.opnd1 = gimple_assign_rhs2 (stmt); 453 break; 454 case GIMPLE_TERNARY_RHS: 455 expr->kind = EXPR_TERNARY; 456 expr->type = TREE_TYPE (gimple_assign_lhs (stmt)); 457 expr->ops.ternary.op = subcode; 458 expr->ops.ternary.opnd0 = gimple_assign_rhs1 (stmt); 459 expr->ops.ternary.opnd1 = gimple_assign_rhs2 (stmt); 460 expr->ops.ternary.opnd2 = gimple_assign_rhs3 (stmt); 461 break; 462 default: 463 gcc_unreachable (); 464 } 465 } 466 else if (code == GIMPLE_COND) 467 { 468 expr->type = boolean_type_node; 469 expr->kind = EXPR_BINARY; 470 expr->ops.binary.op = gimple_cond_code (stmt); 471 expr->ops.binary.opnd0 = gimple_cond_lhs (stmt); 472 expr->ops.binary.opnd1 = gimple_cond_rhs (stmt); 473 } 474 else if (gcall *call_stmt = dyn_cast <gcall *> (stmt)) 475 { 476 size_t nargs = gimple_call_num_args (call_stmt); 477 size_t i; 478 479 gcc_assert (gimple_call_lhs (call_stmt)); 480 481 expr->type = TREE_TYPE (gimple_call_lhs (call_stmt)); 482 expr->kind = EXPR_CALL; 483 expr->ops.call.fn_from = call_stmt; 484 485 if (gimple_call_flags (call_stmt) & (ECF_CONST | ECF_PURE)) 486 expr->ops.call.pure = true; 487 else 488 expr->ops.call.pure = false; 489 490 expr->ops.call.nargs = nargs; 491 expr->ops.call.args = XCNEWVEC (tree, nargs); 492 for (i = 0; i < nargs; i++) 493 expr->ops.call.args[i] = gimple_call_arg (call_stmt, i); 494 } 495 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt)) 496 { 497 expr->type = TREE_TYPE (gimple_switch_index (swtch_stmt)); 498 expr->kind = EXPR_SINGLE; 499 expr->ops.single.rhs = gimple_switch_index (swtch_stmt); 500 } 501 else if (code == GIMPLE_GOTO) 502 { 503 expr->type = TREE_TYPE (gimple_goto_dest (stmt)); 504 expr->kind = EXPR_SINGLE; 505 expr->ops.single.rhs = gimple_goto_dest (stmt); 506 } 507 else if (code == GIMPLE_PHI) 508 { 509 size_t nargs = gimple_phi_num_args (stmt); 510 size_t i; 511 512 expr->type = TREE_TYPE (gimple_phi_result (stmt)); 513 expr->kind = EXPR_PHI; 514 expr->ops.phi.nargs = nargs; 515 expr->ops.phi.args = XCNEWVEC (tree, nargs); 516 for (i = 0; i < nargs; i++) 517 expr->ops.phi.args[i] = gimple_phi_arg_def (stmt, i); 518 } 519 else 520 gcc_unreachable (); 521 522 m_lhs = orig_lhs; 523 m_vop = gimple_vuse (stmt); 524 m_hash = avail_expr_hash (this); 525 m_stamp = this; 526 } 527 528 /* Given a hashable_expr expression ORIG and an ORIG_LHS, 529 construct a hash table element. */ 530 531 expr_hash_elt::expr_hash_elt (struct hashable_expr *orig, tree orig_lhs) 532 { 533 m_expr = *orig; 534 m_lhs = orig_lhs; 535 m_vop = NULL_TREE; 536 m_hash = avail_expr_hash (this); 537 m_stamp = this; 538 } 539 540 /* Copy constructor for a hash table element. */ 541 542 expr_hash_elt::expr_hash_elt (class expr_hash_elt &old_elt) 543 { 544 m_expr = old_elt.m_expr; 545 m_lhs = old_elt.m_lhs; 546 m_vop = old_elt.m_vop; 547 m_hash = old_elt.m_hash; 548 m_stamp = this; 549 550 /* Now deep copy the malloc'd space for CALL and PHI args. */ 551 if (old_elt.m_expr.kind == EXPR_CALL) 552 { 553 size_t nargs = old_elt.m_expr.ops.call.nargs; 554 size_t i; 555 556 m_expr.ops.call.args = XCNEWVEC (tree, nargs); 557 for (i = 0; i < nargs; i++) 558 m_expr.ops.call.args[i] = old_elt.m_expr.ops.call.args[i]; 559 } 560 else if (old_elt.m_expr.kind == EXPR_PHI) 561 { 562 size_t nargs = old_elt.m_expr.ops.phi.nargs; 563 size_t i; 564 565 m_expr.ops.phi.args = XCNEWVEC (tree, nargs); 566 for (i = 0; i < nargs; i++) 567 m_expr.ops.phi.args[i] = old_elt.m_expr.ops.phi.args[i]; 568 } 569 } 570 571 /* Calls and PHIs have a variable number of arguments that are allocated 572 on the heap. Thus we have to have a special dtor to release them. */ 573 574 expr_hash_elt::~expr_hash_elt () 575 { 576 if (m_expr.kind == EXPR_CALL) 577 free (m_expr.ops.call.args); 578 else if (m_expr.kind == EXPR_PHI) 579 free (m_expr.ops.phi.args); 580 } 581 582 /* Print a diagnostic dump of an expression hash table entry. */ 583 584 void 585 expr_hash_elt::print (FILE *stream) 586 { 587 fprintf (stream, "STMT "); 588 589 if (m_lhs) 590 { 591 print_generic_expr (stream, m_lhs, 0); 592 fprintf (stream, " = "); 593 } 594 595 switch (m_expr.kind) 596 { 597 case EXPR_SINGLE: 598 print_generic_expr (stream, m_expr.ops.single.rhs, 0); 599 break; 600 601 case EXPR_UNARY: 602 fprintf (stream, "%s ", get_tree_code_name (m_expr.ops.unary.op)); 603 print_generic_expr (stream, m_expr.ops.unary.opnd, 0); 604 break; 605 606 case EXPR_BINARY: 607 print_generic_expr (stream, m_expr.ops.binary.opnd0, 0); 608 fprintf (stream, " %s ", get_tree_code_name (m_expr.ops.binary.op)); 609 print_generic_expr (stream, m_expr.ops.binary.opnd1, 0); 610 break; 611 612 case EXPR_TERNARY: 613 fprintf (stream, " %s <", get_tree_code_name (m_expr.ops.ternary.op)); 614 print_generic_expr (stream, m_expr.ops.ternary.opnd0, 0); 615 fputs (", ", stream); 616 print_generic_expr (stream, m_expr.ops.ternary.opnd1, 0); 617 fputs (", ", stream); 618 print_generic_expr (stream, m_expr.ops.ternary.opnd2, 0); 619 fputs (">", stream); 620 break; 621 622 case EXPR_CALL: 623 { 624 size_t i; 625 size_t nargs = m_expr.ops.call.nargs; 626 gcall *fn_from; 627 628 fn_from = m_expr.ops.call.fn_from; 629 if (gimple_call_internal_p (fn_from)) 630 fputs (internal_fn_name (gimple_call_internal_fn (fn_from)), 631 stream); 632 else 633 print_generic_expr (stream, gimple_call_fn (fn_from), 0); 634 fprintf (stream, " ("); 635 for (i = 0; i < nargs; i++) 636 { 637 print_generic_expr (stream, m_expr.ops.call.args[i], 0); 638 if (i + 1 < nargs) 639 fprintf (stream, ", "); 640 } 641 fprintf (stream, ")"); 642 } 643 break; 644 645 case EXPR_PHI: 646 { 647 size_t i; 648 size_t nargs = m_expr.ops.phi.nargs; 649 650 fprintf (stream, "PHI <"); 651 for (i = 0; i < nargs; i++) 652 { 653 print_generic_expr (stream, m_expr.ops.phi.args[i], 0); 654 if (i + 1 < nargs) 655 fprintf (stream, ", "); 656 } 657 fprintf (stream, ">"); 658 } 659 break; 660 } 661 662 if (m_vop) 663 { 664 fprintf (stream, " with "); 665 print_generic_expr (stream, m_vop, 0); 666 } 667 668 fprintf (stream, "\n"); 669 } 670 671 /* Pop entries off the stack until we hit the NULL marker. 672 For each entry popped, use the SRC/DEST pair to restore 673 SRC to its prior value. */ 674 675 void 676 const_and_copies::pop_to_marker (void) 677 { 678 while (m_stack.length () > 0) 679 { 680 tree prev_value, dest; 681 682 dest = m_stack.pop (); 683 684 /* A NULL value indicates we should stop unwinding, otherwise 685 pop off the next entry as they're recorded in pairs. */ 686 if (dest == NULL) 687 break; 688 689 if (dump_file && (dump_flags & TDF_DETAILS)) 690 { 691 fprintf (dump_file, "<<<< COPY "); 692 print_generic_expr (dump_file, dest, 0); 693 fprintf (dump_file, " = "); 694 print_generic_expr (dump_file, SSA_NAME_VALUE (dest), 0); 695 fprintf (dump_file, "\n"); 696 } 697 698 prev_value = m_stack.pop (); 699 set_ssa_name_value (dest, prev_value); 700 } 701 } 702 703 /* Record that X has the value Y and that X's previous value is PREV_X. 704 705 This variant does not follow the value chain for Y. */ 706 707 void 708 const_and_copies::record_const_or_copy_raw (tree x, tree y, tree prev_x) 709 { 710 if (dump_file && (dump_flags & TDF_DETAILS)) 711 { 712 fprintf (dump_file, "0>>> COPY "); 713 print_generic_expr (dump_file, x, 0); 714 fprintf (dump_file, " = "); 715 print_generic_expr (dump_file, y, 0); 716 fprintf (dump_file, "\n"); 717 } 718 719 set_ssa_name_value (x, y); 720 m_stack.reserve (2); 721 m_stack.quick_push (prev_x); 722 m_stack.quick_push (x); 723 } 724 725 /* Record that X has the value Y. */ 726 727 void 728 const_and_copies::record_const_or_copy (tree x, tree y) 729 { 730 record_const_or_copy (x, y, SSA_NAME_VALUE (x)); 731 } 732 733 /* Record that X has the value Y and that X's previous value is PREV_X. 734 735 This variant follow's Y value chain. */ 736 737 void 738 const_and_copies::record_const_or_copy (tree x, tree y, tree prev_x) 739 { 740 /* Y may be NULL if we are invalidating entries in the table. */ 741 if (y && TREE_CODE (y) == SSA_NAME) 742 { 743 tree tmp = SSA_NAME_VALUE (y); 744 y = tmp ? tmp : y; 745 } 746 747 record_const_or_copy_raw (x, y, prev_x); 748 } 749 750 bool 751 expr_elt_hasher::equal (const value_type &p1, const compare_type &p2) 752 { 753 const struct hashable_expr *expr1 = p1->expr (); 754 const struct expr_hash_elt *stamp1 = p1->stamp (); 755 const struct hashable_expr *expr2 = p2->expr (); 756 const struct expr_hash_elt *stamp2 = p2->stamp (); 757 758 /* This case should apply only when removing entries from the table. */ 759 if (stamp1 == stamp2) 760 return true; 761 762 if (p1->hash () != p2->hash ()) 763 return false; 764 765 /* In case of a collision, both RHS have to be identical and have the 766 same VUSE operands. */ 767 if (hashable_expr_equal_p (expr1, expr2) 768 && types_compatible_p (expr1->type, expr2->type)) 769 return true; 770 771 return false; 772 } 773 774 /* Given a conditional expression COND as a tree, initialize 775 a hashable_expr expression EXPR. The conditional must be a 776 comparison or logical negation. A constant or a variable is 777 not permitted. */ 778 779 void 780 initialize_expr_from_cond (tree cond, struct hashable_expr *expr) 781 { 782 expr->type = boolean_type_node; 783 784 if (COMPARISON_CLASS_P (cond)) 785 { 786 expr->kind = EXPR_BINARY; 787 expr->ops.binary.op = TREE_CODE (cond); 788 expr->ops.binary.opnd0 = TREE_OPERAND (cond, 0); 789 expr->ops.binary.opnd1 = TREE_OPERAND (cond, 1); 790 } 791 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR) 792 { 793 expr->kind = EXPR_UNARY; 794 expr->ops.unary.op = TRUTH_NOT_EXPR; 795 expr->ops.unary.opnd = TREE_OPERAND (cond, 0); 796 } 797 else 798 gcc_unreachable (); 799 } 800 801