gcc/tree-ssa-scopedtables.c

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