gcc/tree-ssa-sccvn.c

   1 /* SCC value numbering for trees
   2    Copyright (C) 2006-2013 Free Software Foundation, Inc.
   3    Contributed by Daniel Berlin <dan@dberlin.org>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "basic-block.h"
  27 #include "gimple-pretty-print.h"
  28 #include "tree-inline.h"
  29 #include "tree-flow.h"
  30 #include "gimple.h"
  31 #include "dumpfile.h"
  32 #include "hashtab.h"
  33 #include "alloc-pool.h"
  34 #include "flags.h"
  35 #include "bitmap.h"
  36 #include "cfgloop.h"
  37 #include "params.h"
  38 #include "tree-ssa-propagate.h"
  39 #include "tree-ssa-sccvn.h"
  40 #include "gimple-fold.h"
  41
  42 /* This algorithm is based on the SCC algorithm presented by Keith
  43    Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
  44    (http://citeseer.ist.psu.edu/41805.html).  In
  45    straight line code, it is equivalent to a regular hash based value
  46    numbering that is performed in reverse postorder.
  47
  48    For code with cycles, there are two alternatives, both of which
  49    require keeping the hashtables separate from the actual list of
  50    value numbers for SSA names.
  51
  52    1. Iterate value numbering in an RPO walk of the blocks, removing
  53    all the entries from the hashtable after each iteration (but
  54    keeping the SSA name->value number mapping between iterations).
  55    Iterate until it does not change.
  56
  57    2. Perform value numbering as part of an SCC walk on the SSA graph,
  58    iterating only the cycles in the SSA graph until they do not change
  59    (using a separate, optimistic hashtable for value numbering the SCC
  60    operands).
  61
  62    The second is not just faster in practice (because most SSA graph
  63    cycles do not involve all the variables in the graph), it also has
  64    some nice properties.
  65
  66    One of these nice properties is that when we pop an SCC off the
  67    stack, we are guaranteed to have processed all the operands coming from
  68    *outside of that SCC*, so we do not need to do anything special to
  69    ensure they have value numbers.
  70
  71    Another nice property is that the SCC walk is done as part of a DFS
  72    of the SSA graph, which makes it easy to perform combining and
  73    simplifying operations at the same time.
  74
  75    The code below is deliberately written in a way that makes it easy
  76    to separate the SCC walk from the other work it does.
  77
  78    In order to propagate constants through the code, we track which
  79    expressions contain constants, and use those while folding.  In
  80    theory, we could also track expressions whose value numbers are
  81    replaced, in case we end up folding based on expression
  82    identities.
  83
  84    In order to value number memory, we assign value numbers to vuses.
  85    This enables us to note that, for example, stores to the same
  86    address of the same value from the same starting memory states are
  87    equivalent.
  88    TODO:
  89
  90    1. We can iterate only the changing portions of the SCC's, but
  91    I have not seen an SCC big enough for this to be a win.
  92    2. If you differentiate between phi nodes for loops and phi nodes
  93    for if-then-else, you can properly consider phi nodes in different
  94    blocks for equivalence.
  95    3. We could value number vuses in more cases, particularly, whole
  96    structure copies.
  97 */
  98
  99 /* The set of hashtables and alloc_pool's for their items.  */
 100
 101 typedef struct vn_tables_s
 102 {
 103   htab_t nary;
 104   htab_t phis;
 105   htab_t references;
 106   struct obstack nary_obstack;
 107   alloc_pool phis_pool;
 108   alloc_pool references_pool;
 109 } *vn_tables_t;
 110
 111 static htab_t constant_to_value_id;
 112 static bitmap constant_value_ids;
 113
 114
 115 /* Valid hashtables storing information we have proven to be
 116    correct.  */
 117
 118 static vn_tables_t valid_info;
 119
 120 /* Optimistic hashtables storing information we are making assumptions about
 121    during iterations.  */
 122
 123 static vn_tables_t optimistic_info;
 124
 125 /* Pointer to the set of hashtables that is currently being used.
 126    Should always point to either the optimistic_info, or the
 127    valid_info.  */
 128
 129 static vn_tables_t current_info;
 130
 131
 132 /* Reverse post order index for each basic block.  */
 133
 134 static int *rpo_numbers;
 135
 136 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
 137
 138 /* This represents the top of the VN lattice, which is the universal
 139    value.  */
 140
 141 tree VN_TOP;
 142
 143 /* Unique counter for our value ids.  */
 144
 145 static unsigned int next_value_id;
 146
 147 /* Next DFS number and the stack for strongly connected component
 148    detection. */
 149
 150 static unsigned int next_dfs_num;
 151 static vec<tree> sccstack;
 152
 153
 154
 155 /* Table of vn_ssa_aux_t's, one per ssa_name.  The vn_ssa_aux_t objects
 156    are allocated on an obstack for locality reasons, and to free them
 157    without looping over the vec.  */
 158
 159 static vec<vn_ssa_aux_t> vn_ssa_aux_table;
 160 static struct obstack vn_ssa_aux_obstack;
 161
 162 /* Return the value numbering information for a given SSA name.  */
 163
 164 vn_ssa_aux_t
 165 VN_INFO (tree name)
 166 {
 167   vn_ssa_aux_t res = vn_ssa_aux_table[SSA_NAME_VERSION (name)];
 168   gcc_checking_assert (res);
 169   return res;
 170 }
 171
 172 /* Set the value numbering info for a given SSA name to a given
 173    value.  */
 174
 175 static inline void
 176 VN_INFO_SET (tree name, vn_ssa_aux_t value)
 177 {
 178   vn_ssa_aux_table[SSA_NAME_VERSION (name)] = value;
 179 }
 180
 181 /* Initialize the value numbering info for a given SSA name.
 182    This should be called just once for every SSA name.  */
 183
 184 vn_ssa_aux_t
 185 VN_INFO_GET (tree name)
 186 {
 187   vn_ssa_aux_t newinfo;
 188
 189   newinfo = XOBNEW (&vn_ssa_aux_obstack, struct vn_ssa_aux);
 190   memset (newinfo, 0, sizeof (struct vn_ssa_aux));
 191   if (SSA_NAME_VERSION (name) >= vn_ssa_aux_table.length ())
 192     vn_ssa_aux_table.safe_grow (SSA_NAME_VERSION (name) + 1);
 193   vn_ssa_aux_table[SSA_NAME_VERSION (name)] = newinfo;
 194   return newinfo;
 195 }
 196
 197
 198 /* Get the representative expression for the SSA_NAME NAME.  Returns
 199    the representative SSA_NAME if there is no expression associated with it.  */
 200
 201 tree
 202 vn_get_expr_for (tree name)
 203 {
 204   vn_ssa_aux_t vn = VN_INFO (name);
 205   gimple def_stmt;
 206   tree expr = NULL_TREE;
 207   enum tree_code code;
 208
 209   if (vn->valnum == VN_TOP)
 210     return name;
 211
 212   /* If the value-number is a constant it is the representative
 213      expression.  */
 214   if (TREE_CODE (vn->valnum) != SSA_NAME)
 215     return vn->valnum;
 216
 217   /* Get to the information of the value of this SSA_NAME.  */
 218   vn = VN_INFO (vn->valnum);
 219
 220   /* If the value-number is a constant it is the representative
 221      expression.  */
 222   if (TREE_CODE (vn->valnum) != SSA_NAME)
 223     return vn->valnum;
 224
 225   /* Else if we have an expression, return it.  */
 226   if (vn->expr != NULL_TREE)
 227     return vn->expr;
 228
 229   /* Otherwise use the defining statement to build the expression.  */
 230   def_stmt = SSA_NAME_DEF_STMT (vn->valnum);
 231
 232   /* If the value number is not an assignment use it directly.  */
 233   if (!is_gimple_assign (def_stmt))
 234     return vn->valnum;
 235
 236   /* FIXME tuples.  This is incomplete and likely will miss some
 237      simplifications.  */
 238   code = gimple_assign_rhs_code (def_stmt);
 239   switch (TREE_CODE_CLASS (code))
 240     {
 241     case tcc_reference:
 242       if ((code == REALPART_EXPR
 243            || code == IMAGPART_EXPR
 244            || code == VIEW_CONVERT_EXPR)
 245           && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (def_stmt),
 246                                       0)) == SSA_NAME)
 247         expr = fold_build1 (code,
 248                             gimple_expr_type (def_stmt),
 249                             TREE_OPERAND (gimple_assign_rhs1 (def_stmt), 0));
 250       break;
 251
 252     case tcc_unary:
 253       expr = fold_build1 (code,
 254                           gimple_expr_type (def_stmt),
 255                           gimple_assign_rhs1 (def_stmt));
 256       break;
 257
 258     case tcc_binary:
 259       expr = fold_build2 (code,
 260                           gimple_expr_type (def_stmt),
 261                           gimple_assign_rhs1 (def_stmt),
 262                           gimple_assign_rhs2 (def_stmt));
 263       break;
 264
 265     case tcc_exceptional:
 266       if (code == CONSTRUCTOR
 267           && TREE_CODE
 268                (TREE_TYPE (gimple_assign_rhs1 (def_stmt))) == VECTOR_TYPE)
 269         expr = gimple_assign_rhs1 (def_stmt);
 270       break;
 271
 272     default:;
 273     }
 274   if (expr == NULL_TREE)
 275     return vn->valnum;
 276
 277   /* Cache the expression.  */
 278   vn->expr = expr;
 279
 280   return expr;
 281 }
 282
 283 /* Return the vn_kind the expression computed by the stmt should be
 284    associated with.  */
 285
 286 enum vn_kind
 287 vn_get_stmt_kind (gimple stmt)
 288 {
 289   switch (gimple_code (stmt))
 290     {
 291     case GIMPLE_CALL:
 292       return VN_REFERENCE;
 293     case GIMPLE_PHI:
 294       return VN_PHI;
 295     case GIMPLE_ASSIGN:
 296       {
 297         enum tree_code code = gimple_assign_rhs_code (stmt);
 298         tree rhs1 = gimple_assign_rhs1 (stmt);
 299         switch (get_gimple_rhs_class (code))
 300           {
 301           case GIMPLE_UNARY_RHS:
 302           case GIMPLE_BINARY_RHS:
 303           case GIMPLE_TERNARY_RHS:
 304             return VN_NARY;
 305           case GIMPLE_SINGLE_RHS:
 306             switch (TREE_CODE_CLASS (code))
 307               {
 308               case tcc_reference:
 309                 /* VOP-less references can go through unary case.  */
 310                 if ((code == REALPART_EXPR
 311                      || code == IMAGPART_EXPR
 312                      || code == VIEW_CONVERT_EXPR
 313                      || code == BIT_FIELD_REF)
 314                     && TREE_CODE (TREE_OPERAND (rhs1, 0)) == SSA_NAME)
 315                   return VN_NARY;
 316
 317                 /* Fallthrough.  */
 318               case tcc_declaration:
 319                 return VN_REFERENCE;
 320
 321               case tcc_constant:
 322                 return VN_CONSTANT;
 323
 324               default:
 325                 if (code == ADDR_EXPR)
 326                   return (is_gimple_min_invariant (rhs1)
 327                           ? VN_CONSTANT : VN_REFERENCE);
 328                 else if (code == CONSTRUCTOR)
 329                   return VN_NARY;
 330                 return VN_NONE;
 331               }
 332           default:
 333             return VN_NONE;
 334           }
 335       }
 336     default:
 337       return VN_NONE;
 338     }
 339 }
 340
 341 /* Free a phi operation structure VP.  */
 342
 343 static void
 344 free_phi (void *vp)
 345 {
 346   vn_phi_t phi = (vn_phi_t) vp;
 347   phi->phiargs.release ();
 348 }
 349
 350 /* Free a reference operation structure VP.  */
 351
 352 static void
 353 free_reference (void *vp)
 354 {
 355   vn_reference_t vr = (vn_reference_t) vp;
 356   vr->operands.release ();
 357 }
 358
 359 /* Hash table equality function for vn_constant_t.  */
 360
 361 static int
 362 vn_constant_eq (const void *p1, const void *p2)
 363 {
 364   const struct vn_constant_s *vc1 = (const struct vn_constant_s *) p1;
 365   const struct vn_constant_s *vc2 = (const struct vn_constant_s *) p2;
 366
 367   if (vc1->hashcode != vc2->hashcode)
 368     return false;
 369
 370   return vn_constant_eq_with_type (vc1->constant, vc2->constant);
 371 }
 372
 373 /* Hash table hash function for vn_constant_t.  */
 374
 375 static hashval_t
 376 vn_constant_hash (const void *p1)
 377 {
 378   const struct vn_constant_s *vc1 = (const struct vn_constant_s *) p1;
 379   return vc1->hashcode;
 380 }
 381
 382 /* Lookup a value id for CONSTANT and return it.  If it does not
 383    exist returns 0.  */
 384
 385 unsigned int
 386 get_constant_value_id (tree constant)
 387 {
 388   void **slot;
 389   struct vn_constant_s vc;
 390
 391   vc.hashcode = vn_hash_constant_with_type (constant);
 392   vc.constant = constant;
 393   slot = htab_find_slot_with_hash (constant_to_value_id, &vc,
 394                                    vc.hashcode, NO_INSERT);
 395   if (slot)
 396     return ((vn_constant_t)*slot)->value_id;
 397   return 0;
 398 }
 399
 400 /* Lookup a value id for CONSTANT, and if it does not exist, create a
 401    new one and return it.  If it does exist, return it.  */
 402
 403 unsigned int
 404 get_or_alloc_constant_value_id (tree constant)
 405 {
 406   void **slot;
 407   struct vn_constant_s vc;
 408   vn_constant_t vcp;
 409
 410   vc.hashcode = vn_hash_constant_with_type (constant);
 411   vc.constant = constant;
 412   slot = htab_find_slot_with_hash (constant_to_value_id, &vc,
 413                                    vc.hashcode, INSERT);
 414   if (*slot)
 415     return ((vn_constant_t)*slot)->value_id;
 416
 417   vcp = XNEW (struct vn_constant_s);
 418   vcp->hashcode = vc.hashcode;
 419   vcp->constant = constant;
 420   vcp->value_id = get_next_value_id ();
 421   *slot = (void *) vcp;
 422   bitmap_set_bit (constant_value_ids, vcp->value_id);
 423   return vcp->value_id;
 424 }
 425
 426 /* Return true if V is a value id for a constant.  */
 427
 428 bool
 429 value_id_constant_p (unsigned int v)
 430 {
 431   return bitmap_bit_p (constant_value_ids, v);
 432 }
 433
 434 /* Compare two reference operands P1 and P2 for equality.  Return true if
 435    they are equal, and false otherwise.  */
 436
 437 static int
 438 vn_reference_op_eq (const void *p1, const void *p2)
 439 {
 440   const_vn_reference_op_t const vro1 = (const_vn_reference_op_t) p1;
 441   const_vn_reference_op_t const vro2 = (const_vn_reference_op_t) p2;
 442
 443   return (vro1->opcode == vro2->opcode
 444           /* We do not care for differences in type qualification.  */
 445           && (vro1->type == vro2->type
 446               || (vro1->type && vro2->type
 447                   && types_compatible_p (TYPE_MAIN_VARIANT (vro1->type),
 448                                          TYPE_MAIN_VARIANT (vro2->type))))
 449           && expressions_equal_p (vro1->op0, vro2->op0)
 450           && expressions_equal_p (vro1->op1, vro2->op1)
 451           && expressions_equal_p (vro1->op2, vro2->op2));
 452 }
 453
 454 /* Compute the hash for a reference operand VRO1.  */
 455
 456 static hashval_t
 457 vn_reference_op_compute_hash (const vn_reference_op_t vro1, hashval_t result)
 458 {
 459   result = iterative_hash_hashval_t (vro1->opcode, result);
 460   if (vro1->op0)
 461     result = iterative_hash_expr (vro1->op0, result);
 462   if (vro1->op1)
 463     result = iterative_hash_expr (vro1->op1, result);
 464   if (vro1->op2)
 465     result = iterative_hash_expr (vro1->op2, result);
 466   return result;
 467 }
 468
 469 /* Return the hashcode for a given reference operation P1.  */
 470
 471 static hashval_t
 472 vn_reference_hash (const void *p1)
 473 {
 474   const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
 475   return vr1->hashcode;
 476 }
 477
 478 /* Compute a hash for the reference operation VR1 and return it.  */
 479
 480 hashval_t
 481 vn_reference_compute_hash (const vn_reference_t vr1)
 482 {
 483   hashval_t result = 0;
 484   int i;
 485   vn_reference_op_t vro;
 486   HOST_WIDE_INT off = -1;
 487   bool deref = false;
 488
 489   FOR_EACH_VEC_ELT (vr1->operands, i, vro)
 490     {
 491       if (vro->opcode == MEM_REF)
 492         deref = true;
 493       else if (vro->opcode != ADDR_EXPR)
 494         deref = false;
 495       if (vro->off != -1)
 496         {
 497           if (off == -1)
 498             off = 0;
 499           off += vro->off;
 500         }
 501       else
 502         {
 503           if (off != -1
 504               && off != 0)
 505             result = iterative_hash_hashval_t (off, result);
 506           off = -1;
 507           if (deref
 508               && vro->opcode == ADDR_EXPR)
 509             {
 510               if (vro->op0)
 511                 {
 512                   tree op = TREE_OPERAND (vro->op0, 0);
 513                   result = iterative_hash_hashval_t (TREE_CODE (op), result);
 514                   result = iterative_hash_expr (op, result);
 515                 }
 516             }
 517           else
 518             result = vn_reference_op_compute_hash (vro, result);
 519         }
 520     }
 521   if (vr1->vuse)
 522     result += SSA_NAME_VERSION (vr1->vuse);
 523
 524   return result;
 525 }
 526
 527 /* Return true if reference operations P1 and P2 are equivalent.  This
 528    means they have the same set of operands and vuses.  */
 529
 530 int
 531 vn_reference_eq (const void *p1, const void *p2)
 532 {
 533   unsigned i, j;
 534
 535   const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
 536   const_vn_reference_t const vr2 = (const_vn_reference_t) p2;
 537   if (vr1->hashcode != vr2->hashcode)
 538     return false;
 539
 540   /* Early out if this is not a hash collision.  */
 541   if (vr1->hashcode != vr2->hashcode)
 542     return false;
 543
 544   /* The VOP needs to be the same.  */
 545   if (vr1->vuse != vr2->vuse)
 546     return false;
 547
 548   /* If the operands are the same we are done.  */
 549   if (vr1->operands == vr2->operands)
 550     return true;
 551
 552   if (!expressions_equal_p (TYPE_SIZE (vr1->type), TYPE_SIZE (vr2->type)))
 553     return false;
 554
 555   if (INTEGRAL_TYPE_P (vr1->type)
 556       && INTEGRAL_TYPE_P (vr2->type))
 557     {
 558       if (TYPE_PRECISION (vr1->type) != TYPE_PRECISION (vr2->type))
 559         return false;
 560     }
 561   else if (INTEGRAL_TYPE_P (vr1->type)
 562            && (TYPE_PRECISION (vr1->type)
 563                != TREE_INT_CST_LOW (TYPE_SIZE (vr1->type))))
 564     return false;
 565   else if (INTEGRAL_TYPE_P (vr2->type)
 566            && (TYPE_PRECISION (vr2->type)
 567                != TREE_INT_CST_LOW (TYPE_SIZE (vr2->type))))
 568     return false;
 569
 570   i = 0;
 571   j = 0;
 572   do
 573     {
 574       HOST_WIDE_INT off1 = 0, off2 = 0;
 575       vn_reference_op_t vro1, vro2;
 576       vn_reference_op_s tem1, tem2;
 577       bool deref1 = false, deref2 = false;
 578       for (; vr1->operands.iterate (i, &vro1); i++)
 579         {
 580           if (vro1->opcode == MEM_REF)
 581             deref1 = true;
 582           if (vro1->off == -1)
 583             break;
 584           off1 += vro1->off;
 585         }
 586       for (; vr2->operands.iterate (j, &vro2); j++)
 587         {
 588           if (vro2->opcode == MEM_REF)
 589             deref2 = true;
 590           if (vro2->off == -1)
 591             break;
 592           off2 += vro2->off;
 593         }
 594       if (off1 != off2)
 595         return false;
 596       if (deref1 && vro1->opcode == ADDR_EXPR)
 597         {
 598           memset (&tem1, 0, sizeof (tem1));
 599           tem1.op0 = TREE_OPERAND (vro1->op0, 0);
 600           tem1.type = TREE_TYPE (tem1.op0);
 601           tem1.opcode = TREE_CODE (tem1.op0);
 602           vro1 = &tem1;
 603           deref1 = false;
 604         }
 605       if (deref2 && vro2->opcode == ADDR_EXPR)
 606         {
 607           memset (&tem2, 0, sizeof (tem2));
 608           tem2.op0 = TREE_OPERAND (vro2->op0, 0);
 609           tem2.type = TREE_TYPE (tem2.op0);
 610           tem2.opcode = TREE_CODE (tem2.op0);
 611           vro2 = &tem2;
 612           deref2 = false;
 613         }
 614       if (deref1 != deref2)
 615         return false;
 616       if (!vn_reference_op_eq (vro1, vro2))
 617         return false;
 618       ++j;
 619       ++i;
 620     }
 621   while (vr1->operands.length () != i
 622          || vr2->operands.length () != j);
 623
 624   return true;
 625 }
 626
 627 /* Copy the operations present in load/store REF into RESULT, a vector of
 628    vn_reference_op_s's.  */
 629
 630 void
 631 copy_reference_ops_from_ref (tree ref, vec<vn_reference_op_s> *result)
 632 {
 633   if (TREE_CODE (ref) == TARGET_MEM_REF)
 634     {
 635       vn_reference_op_s temp;
 636
 637       memset (&temp, 0, sizeof (temp));
 638       temp.type = TREE_TYPE (ref);
 639       temp.opcode = TREE_CODE (ref);
 640       temp.op0 = TMR_INDEX (ref);
 641       temp.op1 = TMR_STEP (ref);
 642       temp.op2 = TMR_OFFSET (ref);
 643       temp.off = -1;
 644       result->safe_push (temp);
 645
 646       memset (&temp, 0, sizeof (temp));
 647       temp.type = NULL_TREE;
 648       temp.opcode = ERROR_MARK;
 649       temp.op0 = TMR_INDEX2 (ref);
 650       temp.off = -1;
 651       result->safe_push (temp);
 652
 653       memset (&temp, 0, sizeof (temp));
 654       temp.type = NULL_TREE;
 655       temp.opcode = TREE_CODE (TMR_BASE (ref));
 656       temp.op0 = TMR_BASE (ref);
 657       temp.off = -1;
 658       result->safe_push (temp);
 659       return;
 660     }
 661
 662   /* For non-calls, store the information that makes up the address.  */
 663
 664   while (ref)
 665     {
 666       vn_reference_op_s temp;
 667
 668       memset (&temp, 0, sizeof (temp));
 669       temp.type = TREE_TYPE (ref);
 670       temp.opcode = TREE_CODE (ref);
 671       temp.off = -1;
 672
 673       switch (temp.opcode)
 674         {
 675         case MODIFY_EXPR:
 676           temp.op0 = TREE_OPERAND (ref, 1);
 677           break;
 678         case WITH_SIZE_EXPR:
 679           temp.op0 = TREE_OPERAND (ref, 1);
 680           temp.off = 0;
 681           break;
 682         case MEM_REF:
 683           /* The base address gets its own vn_reference_op_s structure.  */
 684           temp.op0 = TREE_OPERAND (ref, 1);
 685           if (host_integerp (TREE_OPERAND (ref, 1), 0))
 686             temp.off = TREE_INT_CST_LOW (TREE_OPERAND (ref, 1));
 687           break;
 688         case BIT_FIELD_REF:
 689           /* Record bits and position.  */
 690           temp.op0 = TREE_OPERAND (ref, 1);
 691           temp.op1 = TREE_OPERAND (ref, 2);
 692           break;
 693         case COMPONENT_REF:
 694           /* The field decl is enough to unambiguously specify the field,
 695              a matching type is not necessary and a mismatching type
 696              is always a spurious difference.  */
 697           temp.type = NULL_TREE;
 698           temp.op0 = TREE_OPERAND (ref, 1);
 699           temp.op1 = TREE_OPERAND (ref, 2);
 700           {
 701             tree this_offset = component_ref_field_offset (ref);
 702             if (this_offset
 703                 && TREE_CODE (this_offset) == INTEGER_CST)
 704               {
 705                 tree bit_offset = DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1));
 706                 if (TREE_INT_CST_LOW (bit_offset) % BITS_PER_UNIT == 0)
 707                   {
 708                     double_int off
 709                       = tree_to_double_int (this_offset)
 710                         + tree_to_double_int (bit_offset)
 711                           .arshift (BITS_PER_UNIT == 8
 712                                     ? 3 : exact_log2 (BITS_PER_UNIT),
 713                                     HOST_BITS_PER_DOUBLE_INT);
 714                     if (off.fits_shwi ())
 715                       temp.off = off.low;
 716                   }
 717               }
 718           }
 719           break;
 720         case ARRAY_RANGE_REF:
 721         case ARRAY_REF:
 722           /* Record index as operand.  */
 723           temp.op0 = TREE_OPERAND (ref, 1);
 724           /* Always record lower bounds and element size.  */
 725           temp.op1 = array_ref_low_bound (ref);
 726           temp.op2 = array_ref_element_size (ref);
 727           if (TREE_CODE (temp.op0) == INTEGER_CST
 728               && TREE_CODE (temp.op1) == INTEGER_CST
 729               && TREE_CODE (temp.op2) == INTEGER_CST)
 730             {
 731               double_int off = tree_to_double_int (temp.op0);
 732               off += -tree_to_double_int (temp.op1);
 733               off *= tree_to_double_int (temp.op2);
 734               if (off.fits_shwi ())
 735                 temp.off = off.low;
 736             }
 737           break;
 738         case VAR_DECL:
 739           if (DECL_HARD_REGISTER (ref))
 740             {
 741               temp.op0 = ref;
 742               break;
 743             }
 744           /* Fallthru.  */
 745         case PARM_DECL:
 746         case CONST_DECL:
 747         case RESULT_DECL:
 748           /* Canonicalize decls to MEM[&decl] which is what we end up with
 749              when valueizing MEM[ptr] with ptr = &decl.  */
 750           temp.opcode = MEM_REF;
 751           temp.op0 = build_int_cst (build_pointer_type (TREE_TYPE (ref)), 0);
 752           temp.off = 0;
 753           result->safe_push (temp);
 754           temp.opcode = ADDR_EXPR;
 755           temp.op0 = build_fold_addr_expr (ref);
 756           temp.type = TREE_TYPE (temp.op0);
 757           temp.off = -1;
 758           break;
 759         case STRING_CST:
 760         case INTEGER_CST:
 761         case COMPLEX_CST:
 762         case VECTOR_CST:
 763         case REAL_CST:
 764         case FIXED_CST:
 765         case CONSTRUCTOR:
 766         case SSA_NAME:
 767           temp.op0 = ref;
 768           break;
 769         case ADDR_EXPR:
 770           if (is_gimple_min_invariant (ref))
 771             {
 772               temp.op0 = ref;
 773               break;
 774             }
 775           /* Fallthrough.  */
 776           /* These are only interesting for their operands, their
 777              existence, and their type.  They will never be the last
 778              ref in the chain of references (IE they require an
 779              operand), so we don't have to put anything
 780              for op* as it will be handled by the iteration  */
 781         case REALPART_EXPR:
 782         case VIEW_CONVERT_EXPR:
 783           temp.off = 0;
 784           break;
 785         case IMAGPART_EXPR:
 786           /* This is only interesting for its constant offset.  */
 787           temp.off = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref)));
 788           break;
 789         default:
 790           gcc_unreachable ();
 791         }
 792       result->safe_push (temp);
 793
 794       if (REFERENCE_CLASS_P (ref)
 795           || TREE_CODE (ref) == MODIFY_EXPR
 796           || TREE_CODE (ref) == WITH_SIZE_EXPR
 797           || (TREE_CODE (ref) == ADDR_EXPR
 798               && !is_gimple_min_invariant (ref)))
 799         ref = TREE_OPERAND (ref, 0);
 800       else
 801         ref = NULL_TREE;
 802     }
 803 }
 804
 805 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
 806    operands in *OPS, the reference alias set SET and the reference type TYPE.
 807    Return true if something useful was produced.  */
 808
 809 bool
 810 ao_ref_init_from_vn_reference (ao_ref *ref,
 811                                alias_set_type set, tree type,
 812                                vec<vn_reference_op_s> ops)
 813 {
 814   vn_reference_op_t op;
 815   unsigned i;
 816   tree base = NULL_TREE;
 817   tree *op0_p = &base;
 818   HOST_WIDE_INT offset = 0;
 819   HOST_WIDE_INT max_size;
 820   HOST_WIDE_INT size = -1;
 821   tree size_tree = NULL_TREE;
 822   alias_set_type base_alias_set = -1;
 823
 824   /* First get the final access size from just the outermost expression.  */
 825   op = &ops[0];
 826   if (op->opcode == COMPONENT_REF)
 827     size_tree = DECL_SIZE (op->op0);
 828   else if (op->opcode == BIT_FIELD_REF)
 829     size_tree = op->op0;
 830   else
 831     {
 832       enum machine_mode mode = TYPE_MODE (type);
 833       if (mode == BLKmode)
 834         size_tree = TYPE_SIZE (type);
 835       else
 836         size = GET_MODE_BITSIZE (mode);
 837     }
 838   if (size_tree != NULL_TREE)
 839     {
 840       if (!host_integerp (size_tree, 1))
 841         size = -1;
 842       else
 843         size = TREE_INT_CST_LOW (size_tree);
 844     }
 845
 846   /* Initially, maxsize is the same as the accessed element size.
 847      In the following it will only grow (or become -1).  */
 848   max_size = size;
 849
 850   /* Compute cumulative bit-offset for nested component-refs and array-refs,
 851      and find the ultimate containing object.  */
 852   FOR_EACH_VEC_ELT (ops, i, op)
 853     {
 854       switch (op->opcode)
 855         {
 856         /* These may be in the reference ops, but we cannot do anything
 857            sensible with them here.  */
 858         case ADDR_EXPR:
 859           /* Apart from ADDR_EXPR arguments to MEM_REF.  */
 860           if (base != NULL_TREE
 861               && TREE_CODE (base) == MEM_REF
 862               && op->op0
 863               && DECL_P (TREE_OPERAND (op->op0, 0)))
 864             {
 865               vn_reference_op_t pop = &ops[i-1];
 866               base = TREE_OPERAND (op->op0, 0);
 867               if (pop->off == -1)
 868                 {
 869                   max_size = -1;
 870                   offset = 0;
 871                 }
 872               else
 873                 offset += pop->off * BITS_PER_UNIT;
 874               op0_p = NULL;
 875               break;
 876             }
 877           /* Fallthru.  */
 878         case CALL_EXPR:
 879           return false;
 880
 881         /* Record the base objects.  */
 882         case MEM_REF:
 883           base_alias_set = get_deref_alias_set (op->op0);
 884           *op0_p = build2 (MEM_REF, op->type,
 885                            NULL_TREE, op->op0);
 886           op0_p = &TREE_OPERAND (*op0_p, 0);
 887           break;
 888
 889         case VAR_DECL:
 890         case PARM_DECL:
 891         case RESULT_DECL:
 892         case SSA_NAME:
 893           *op0_p = op->op0;
 894           op0_p = NULL;
 895           break;
 896
 897         /* And now the usual component-reference style ops.  */
 898         case BIT_FIELD_REF:
 899           offset += tree_low_cst (op->op1, 0);
 900           break;
 901
 902         case COMPONENT_REF:
 903           {
 904             tree field = op->op0;
 905             /* We do not have a complete COMPONENT_REF tree here so we
 906                cannot use component_ref_field_offset.  Do the interesting
 907                parts manually.  */
 908
 909             if (op->op1
 910                 || !host_integerp (DECL_FIELD_OFFSET (field), 1))
 911               max_size = -1;
 912             else
 913               {
 914                 offset += (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (field))
 915                            * BITS_PER_UNIT);
 916                 offset += TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field));
 917               }
 918             break;
 919           }
 920
 921         case ARRAY_RANGE_REF:
 922         case ARRAY_REF:
 923           /* We recorded the lower bound and the element size.  */
 924           if (!host_integerp (op->op0, 0)
 925               || !host_integerp (op->op1, 0)
 926               || !host_integerp (op->op2, 0))
 927             max_size = -1;
 928           else
 929             {
 930               HOST_WIDE_INT hindex = TREE_INT_CST_LOW (op->op0);
 931               hindex -= TREE_INT_CST_LOW (op->op1);
 932               hindex *= TREE_INT_CST_LOW (op->op2);
 933               hindex *= BITS_PER_UNIT;
 934               offset += hindex;
 935             }
 936           break;
 937
 938         case REALPART_EXPR:
 939           break;
 940
 941         case IMAGPART_EXPR:
 942           offset += size;
 943           break;
 944
 945         case VIEW_CONVERT_EXPR:
 946           break;
 947
 948         case STRING_CST:
 949         case INTEGER_CST:
 950         case COMPLEX_CST:
 951         case VECTOR_CST:
 952         case REAL_CST:
 953         case CONSTRUCTOR:
 954         case CONST_DECL:
 955           return false;
 956
 957         default:
 958           return false;
 959         }
 960     }
 961
 962   if (base == NULL_TREE)
 963     return false;
 964
 965   ref->ref = NULL_TREE;
 966   ref->base = base;
 967   ref->offset = offset;
 968   ref->size = size;
 969   ref->max_size = max_size;
 970   ref->ref_alias_set = set;
 971   if (base_alias_set != -1)
 972     ref->base_alias_set = base_alias_set;
 973   else
 974     ref->base_alias_set = get_alias_set (base);
 975   /* We discount volatiles from value-numbering elsewhere.  */
 976   ref->volatile_p = false;
 977
 978   return true;
 979 }
 980
 981 /* Copy the operations present in load/store/call REF into RESULT, a vector of
 982    vn_reference_op_s's.  */
 983
 984 void
 985 copy_reference_ops_from_call (gimple call,
 986                               vec<vn_reference_op_s> *result)
 987 {
 988   vn_reference_op_s temp;
 989   unsigned i;
 990   tree lhs = gimple_call_lhs (call);
 991
 992   /* If 2 calls have a different non-ssa lhs, vdef value numbers should be
 993      different.  By adding the lhs here in the vector, we ensure that the
 994      hashcode is different, guaranteeing a different value number.  */
 995   if (lhs && TREE_CODE (lhs) != SSA_NAME)
 996     {
 997       memset (&temp, 0, sizeof (temp));
 998       temp.opcode = MODIFY_EXPR;
 999       temp.type = TREE_TYPE (lhs);
1000       temp.op0 = lhs;
1001       temp.off = -1;
1002       result->safe_push (temp);
1003     }
1004
1005   /* Copy the type, opcode, function being called and static chain.  */
1006   memset (&temp, 0, sizeof (temp));
1007   temp.type = gimple_call_return_type (call);
1008   temp.opcode = CALL_EXPR;
1009   temp.op0 = gimple_call_fn (call);
1010   temp.op1 = gimple_call_chain (call);
1011   temp.off = -1;
1012   result->safe_push (temp);
1013
1014   /* Copy the call arguments.  As they can be references as well,
1015      just chain them together.  */
1016   for (i = 0; i < gimple_call_num_args (call); ++i)
1017     {
1018       tree callarg = gimple_call_arg (call, i);
1019       copy_reference_ops_from_ref (callarg, result);
1020     }
1021 }
1022
1023 /* Create a vector of vn_reference_op_s structures from REF, a
1024    REFERENCE_CLASS_P tree.  The vector is not shared. */
1025
1026 static vec<vn_reference_op_s>
1027 create_reference_ops_from_ref (tree ref)
1028 {
1029   vec<vn_reference_op_s> result = vNULL;
1030
1031   copy_reference_ops_from_ref (ref, &result);
1032   return result;
1033 }
1034
1035 /* Create a vector of vn_reference_op_s structures from CALL, a
1036    call statement.  The vector is not shared.  */
1037
1038 static vec<vn_reference_op_s>
1039 create_reference_ops_from_call (gimple call)
1040 {
1041   vec<vn_reference_op_s> result = vNULL;
1042
1043   copy_reference_ops_from_call (call, &result);
1044   return result;
1045 }
1046
1047 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS.  Updates
1048    *I_P to point to the last element of the replacement.  */
1049 void
1050 vn_reference_fold_indirect (vec<vn_reference_op_s> *ops,
1051                             unsigned int *i_p)
1052 {
1053   unsigned int i = *i_p;
1054   vn_reference_op_t op = &(*ops)[i];
1055   vn_reference_op_t mem_op = &(*ops)[i - 1];
1056   tree addr_base;
1057   HOST_WIDE_INT addr_offset = 0;
1058
1059   /* The only thing we have to do is from &OBJ.foo.bar add the offset
1060      from .foo.bar to the preceding MEM_REF offset and replace the
1061      address with &OBJ.  */
1062   addr_base = get_addr_base_and_unit_offset (TREE_OPERAND (op->op0, 0),
1063                                              &addr_offset);
1064   gcc_checking_assert (addr_base && TREE_CODE (addr_base) != MEM_REF);
1065   if (addr_base != op->op0)
1066     {
1067       double_int off = tree_to_double_int (mem_op->op0);
1068       off = off.sext (TYPE_PRECISION (TREE_TYPE (mem_op->op0)));
1069       off += double_int::from_shwi (addr_offset);
1070       mem_op->op0 = double_int_to_tree (TREE_TYPE (mem_op->op0), off);
1071       op->op0 = build_fold_addr_expr (addr_base);
1072       if (host_integerp (mem_op->op0, 0))
1073         mem_op->off = TREE_INT_CST_LOW (mem_op->op0);
1074       else
1075         mem_op->off = -1;
1076     }
1077 }
1078
1079 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS.  Updates
1080    *I_P to point to the last element of the replacement.  */
1081 static void
1082 vn_reference_maybe_forwprop_address (vec<vn_reference_op_s> *ops,
1083                                      unsigned int *i_p)
1084 {
1085   unsigned int i = *i_p;
1086   vn_reference_op_t op = &(*ops)[i];
1087   vn_reference_op_t mem_op = &(*ops)[i - 1];
1088   gimple def_stmt;
1089   enum tree_code code;
1090   double_int off;
1091
1092   def_stmt = SSA_NAME_DEF_STMT (op->op0);
1093   if (!is_gimple_assign (def_stmt))
1094     return;
1095
1096   code = gimple_assign_rhs_code (def_stmt);
1097   if (code != ADDR_EXPR
1098       && code != POINTER_PLUS_EXPR)
1099     return;
1100
1101   off = tree_to_double_int (mem_op->op0);
1102   off = off.sext (TYPE_PRECISION (TREE_TYPE (mem_op->op0)));
1103
1104   /* The only thing we have to do is from &OBJ.foo.bar add the offset
1105      from .foo.bar to the preceding MEM_REF offset and replace the
1106      address with &OBJ.  */
1107   if (code == ADDR_EXPR)
1108     {
1109       tree addr, addr_base;
1110       HOST_WIDE_INT addr_offset;
1111
1112       addr = gimple_assign_rhs1 (def_stmt);
1113       addr_base = get_addr_base_and_unit_offset (TREE_OPERAND (addr, 0),
1114                                                  &addr_offset);
1115       if (!addr_base
1116           || TREE_CODE (addr_base) != MEM_REF)
1117         return;
1118
1119       off += double_int::from_shwi (addr_offset);
1120       off += mem_ref_offset (addr_base);
1121       op->op0 = TREE_OPERAND (addr_base, 0);
1122     }
1123   else
1124     {
1125       tree ptr, ptroff;
1126       ptr = gimple_assign_rhs1 (def_stmt);
1127       ptroff = gimple_assign_rhs2 (def_stmt);
1128       if (TREE_CODE (ptr) != SSA_NAME
1129           || TREE_CODE (ptroff) != INTEGER_CST)
1130         return;
1131
1132       off += tree_to_double_int (ptroff);
1133       op->op0 = ptr;
1134     }
1135
1136   mem_op->op0 = double_int_to_tree (TREE_TYPE (mem_op->op0), off);
1137   if (host_integerp (mem_op->op0, 0))
1138     mem_op->off = TREE_INT_CST_LOW (mem_op->op0);
1139   else
1140     mem_op->off = -1;
1141   if (TREE_CODE (op->op0) == SSA_NAME)
1142     op->op0 = SSA_VAL (op->op0);
1143   if (TREE_CODE (op->op0) != SSA_NAME)
1144     op->opcode = TREE_CODE (op->op0);
1145
1146   /* And recurse.  */
1147   if (TREE_CODE (op->op0) == SSA_NAME)
1148     vn_reference_maybe_forwprop_address (ops, i_p);
1149   else if (TREE_CODE (op->op0) == ADDR_EXPR)
1150     vn_reference_fold_indirect (ops, i_p);
1151 }
1152
1153 /* Optimize the reference REF to a constant if possible or return
1154    NULL_TREE if not.  */
1155
1156 tree
1157 fully_constant_vn_reference_p (vn_reference_t ref)
1158 {
1159   vec<vn_reference_op_s> operands = ref->operands;
1160   vn_reference_op_t op;
1161
1162   /* Try to simplify the translated expression if it is
1163      a call to a builtin function with at most two arguments.  */
1164   op = &operands[0];
1165   if (op->opcode == CALL_EXPR
1166       && TREE_CODE (op->op0) == ADDR_EXPR
1167       && TREE_CODE (TREE_OPERAND (op->op0, 0)) == FUNCTION_DECL
1168       && DECL_BUILT_IN (TREE_OPERAND (op->op0, 0))
1169       && operands.length () >= 2
1170       && operands.length () <= 3)
1171     {
1172       vn_reference_op_t arg0, arg1 = NULL;
1173       bool anyconst = false;
1174       arg0 = &operands[1];
1175       if (operands.length () > 2)
1176         arg1 = &operands[2];
1177       if (TREE_CODE_CLASS (arg0->opcode) == tcc_constant
1178           || (arg0->opcode == ADDR_EXPR
1179               && is_gimple_min_invariant (arg0->op0)))
1180         anyconst = true;
1181       if (arg1
1182           && (TREE_CODE_CLASS (arg1->opcode) == tcc_constant
1183               || (arg1->opcode == ADDR_EXPR
1184                   && is_gimple_min_invariant (arg1->op0))))
1185         anyconst = true;
1186       if (anyconst)
1187         {
1188           tree folded = build_call_expr (TREE_OPERAND (op->op0, 0),
1189                                          arg1 ? 2 : 1,
1190                                          arg0->op0,
1191                                          arg1 ? arg1->op0 : NULL);
1192           if (folded
1193               && TREE_CODE (folded) == NOP_EXPR)
1194             folded = TREE_OPERAND (folded, 0);
1195           if (folded
1196               && is_gimple_min_invariant (folded))
1197             return folded;
1198         }
1199     }
1200
1201   /* Simplify reads from constant strings.  */
1202   else if (op->opcode == ARRAY_REF
1203            && TREE_CODE (op->op0) == INTEGER_CST
1204            && integer_zerop (op->op1)
1205            && operands.length () == 2)
1206     {
1207       vn_reference_op_t arg0;
1208       arg0 = &operands[1];
1209       if (arg0->opcode == STRING_CST
1210           && (TYPE_MODE (op->type)
1211               == TYPE_MODE (TREE_TYPE (TREE_TYPE (arg0->op0))))
1212           && GET_MODE_CLASS (TYPE_MODE (op->type)) == MODE_INT
1213           && GET_MODE_SIZE (TYPE_MODE (op->type)) == 1
1214           && compare_tree_int (op->op0, TREE_STRING_LENGTH (arg0->op0)) < 0)
1215         return build_int_cst_type (op->type,
1216                                    (TREE_STRING_POINTER (arg0->op0)
1217                                     [TREE_INT_CST_LOW (op->op0)]));
1218     }
1219
1220   return NULL_TREE;
1221 }
1222
1223 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1224    structures into their value numbers.  This is done in-place, and
1225    the vector passed in is returned.  *VALUEIZED_ANYTHING will specify
1226    whether any operands were valueized.  */
1227
1228 static vec<vn_reference_op_s>
1229 valueize_refs_1 (vec<vn_reference_op_s> orig, bool *valueized_anything)
1230 {
1231   vn_reference_op_t vro;
1232   unsigned int i;
1233
1234   *valueized_anything = false;
1235
1236   FOR_EACH_VEC_ELT (orig, i, vro)
1237     {
1238       if (vro->opcode == SSA_NAME
1239           || (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME))
1240         {
1241           tree tem = SSA_VAL (vro->op0);
1242           if (tem != vro->op0)
1243             {
1244               *valueized_anything = true;
1245               vro->op0 = tem;
1246             }
1247           /* If it transforms from an SSA_NAME to a constant, update
1248              the opcode.  */
1249           if (TREE_CODE (vro->op0) != SSA_NAME && vro->opcode == SSA_NAME)
1250             vro->opcode = TREE_CODE (vro->op0);
1251         }
1252       if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
1253         {
1254           tree tem = SSA_VAL (vro->op1);
1255           if (tem != vro->op1)
1256             {
1257               *valueized_anything = true;
1258               vro->op1 = tem;
1259             }
1260         }
1261       if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
1262         {
1263           tree tem = SSA_VAL (vro->op2);
1264           if (tem != vro->op2)
1265             {
1266               *valueized_anything = true;
1267               vro->op2 = tem;
1268             }
1269         }
1270       /* If it transforms from an SSA_NAME to an address, fold with
1271          a preceding indirect reference.  */
1272       if (i > 0
1273           && vro->op0
1274           && TREE_CODE (vro->op0) == ADDR_EXPR
1275           && orig[i - 1].opcode == MEM_REF)
1276         vn_reference_fold_indirect (&orig, &i);
1277       else if (i > 0
1278                && vro->opcode == SSA_NAME
1279                && orig[i - 1].opcode == MEM_REF)
1280         vn_reference_maybe_forwprop_address (&orig, &i);
1281       /* If it transforms a non-constant ARRAY_REF into a constant
1282          one, adjust the constant offset.  */
1283       else if (vro->opcode == ARRAY_REF
1284                && vro->off == -1
1285                && TREE_CODE (vro->op0) == INTEGER_CST
1286                && TREE_CODE (vro->op1) == INTEGER_CST
1287                && TREE_CODE (vro->op2) == INTEGER_CST)
1288         {
1289           double_int off = tree_to_double_int (vro->op0);
1290           off += -tree_to_double_int (vro->op1);
1291           off *= tree_to_double_int (vro->op2);
1292           if (off.fits_shwi ())
1293             vro->off = off.low;
1294         }
1295     }
1296
1297   return orig;
1298 }
1299
1300 static vec<vn_reference_op_s>
1301 valueize_refs (vec<vn_reference_op_s> orig)
1302 {
1303   bool tem;
1304   return valueize_refs_1 (orig, &tem);
1305 }
1306
1307 static vec<vn_reference_op_s> shared_lookup_references;
1308
1309 /* Create a vector of vn_reference_op_s structures from REF, a
1310    REFERENCE_CLASS_P tree.  The vector is shared among all callers of
1311    this function.  *VALUEIZED_ANYTHING will specify whether any
1312    operands were valueized.  */
1313
1314 static vec<vn_reference_op_s>
1315 valueize_shared_reference_ops_from_ref (tree ref, bool *valueized_anything)
1316 {
1317   if (!ref)
1318     return vNULL;
1319   shared_lookup_references.truncate (0);
1320   copy_reference_ops_from_ref (ref, &shared_lookup_references);
1321   shared_lookup_references = valueize_refs_1 (shared_lookup_references,
1322                                               valueized_anything);
1323   return shared_lookup_references;
1324 }
1325
1326 /* Create a vector of vn_reference_op_s structures from CALL, a
1327    call statement.  The vector is shared among all callers of
1328    this function.  */
1329
1330 static vec<vn_reference_op_s>
1331 valueize_shared_reference_ops_from_call (gimple call)
1332 {
1333   if (!call)
1334     return vNULL;
1335   shared_lookup_references.truncate (0);
1336   copy_reference_ops_from_call (call, &shared_lookup_references);
1337   shared_lookup_references = valueize_refs (shared_lookup_references);
1338   return shared_lookup_references;
1339 }
1340
1341 /* Lookup a SCCVN reference operation VR in the current hash table.
1342    Returns the resulting value number if it exists in the hash table,
1343    NULL_TREE otherwise.  VNRESULT will be filled in with the actual
1344    vn_reference_t stored in the hashtable if something is found.  */
1345
1346 static tree
1347 vn_reference_lookup_1 (vn_reference_t vr, vn_reference_t *vnresult)
1348 {
1349   void **slot;
1350   hashval_t hash;
1351
1352   hash = vr->hashcode;
1353   slot = htab_find_slot_with_hash (current_info->references, vr,
1354                                    hash, NO_INSERT);
1355   if (!slot && current_info == optimistic_info)
1356     slot = htab_find_slot_with_hash (valid_info->references, vr,
1357                                      hash, NO_INSERT);
1358   if (slot)
1359     {
1360       if (vnresult)
1361         *vnresult = (vn_reference_t)*slot;
1362       return ((vn_reference_t)*slot)->result;
1363     }
1364
1365   return NULL_TREE;
1366 }
1367
1368 static tree *last_vuse_ptr;
1369 static vn_lookup_kind vn_walk_kind;
1370 static vn_lookup_kind default_vn_walk_kind;
1371
1372 /* Callback for walk_non_aliased_vuses.  Adjusts the vn_reference_t VR_
1373    with the current VUSE and performs the expression lookup.  */
1374
1375 static void *
1376 vn_reference_lookup_2 (ao_ref *op ATTRIBUTE_UNUSED, tree vuse,
1377                        unsigned int cnt, void *vr_)
1378 {
1379   vn_reference_t vr = (vn_reference_t)vr_;
1380   void **slot;
1381   hashval_t hash;
1382
1383   /* This bounds the stmt walks we perform on reference lookups
1384      to O(1) instead of O(N) where N is the number of dominating
1385      stores.  */
1386   if (cnt > (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS))
1387     return (void *)-1;
1388
1389   if (last_vuse_ptr)
1390     *last_vuse_ptr = vuse;
1391
1392   /* Fixup vuse and hash.  */
1393   if (vr->vuse)
1394     vr->hashcode = vr->hashcode - SSA_NAME_VERSION (vr->vuse);
1395   vr->vuse = SSA_VAL (vuse);
1396   if (vr->vuse)
1397     vr->hashcode = vr->hashcode + SSA_NAME_VERSION (vr->vuse);
1398
1399   hash = vr->hashcode;
1400   slot = htab_find_slot_with_hash (current_info->references, vr,
1401                                    hash, NO_INSERT);
1402   if (!slot && current_info == optimistic_info)
1403     slot = htab_find_slot_with_hash (valid_info->references, vr,
1404                                      hash, NO_INSERT);
1405   if (slot)
1406     return *slot;
1407
1408   return NULL;
1409 }
1410
1411 /* Lookup an existing or insert a new vn_reference entry into the
1412    value table for the VUSE, SET, TYPE, OPERANDS reference which
1413    has the value VALUE which is either a constant or an SSA name.  */
1414
1415 static vn_reference_t
1416 vn_reference_lookup_or_insert_for_pieces (tree vuse,
1417                                           alias_set_type set,
1418                                           tree type,
1419                                           vec<vn_reference_op_s,
1420                                                 va_heap> operands,
1421                                           tree value)
1422 {
1423   struct vn_reference_s vr1;
1424   vn_reference_t result;
1425   unsigned value_id;
1426   vr1.vuse = vuse;
1427   vr1.operands = operands;
1428   vr1.type = type;
1429   vr1.set = set;
1430   vr1.hashcode = vn_reference_compute_hash (&vr1);
1431   if (vn_reference_lookup_1 (&vr1, &result))
1432     return result;
1433   if (TREE_CODE (value) == SSA_NAME)
1434     value_id = VN_INFO (value)->value_id;
1435   else
1436     value_id = get_or_alloc_constant_value_id (value);
1437   return vn_reference_insert_pieces (vuse, set, type,
1438                                      operands.copy (), value, value_id);
1439 }
1440
1441 /* Callback for walk_non_aliased_vuses.  Tries to perform a lookup
1442    from the statement defining VUSE and if not successful tries to
1443    translate *REFP and VR_ through an aggregate copy at the definition
1444    of VUSE.  */
1445
1446 static void *
1447 vn_reference_lookup_3 (ao_ref *ref, tree vuse, void *vr_)
1448 {
1449   vn_reference_t vr = (vn_reference_t)vr_;
1450   gimple def_stmt = SSA_NAME_DEF_STMT (vuse);
1451   tree base;
1452   HOST_WIDE_INT offset, maxsize;
1453   static vec<vn_reference_op_s>
1454     lhs_ops = vNULL;
1455   ao_ref lhs_ref;
1456   bool lhs_ref_ok = false;
1457
1458   /* First try to disambiguate after value-replacing in the definitions LHS.  */
1459   if (is_gimple_assign (def_stmt))
1460     {
1461       vec<vn_reference_op_s> tem;
1462       tree lhs = gimple_assign_lhs (def_stmt);
1463       bool valueized_anything = false;
1464       /* Avoid re-allocation overhead.  */
1465       lhs_ops.truncate (0);
1466       copy_reference_ops_from_ref (lhs, &lhs_ops);
1467       tem = lhs_ops;
1468       lhs_ops = valueize_refs_1 (lhs_ops, &valueized_anything);
1469       gcc_assert (lhs_ops == tem);
1470       if (valueized_anything)
1471         {
1472           lhs_ref_ok = ao_ref_init_from_vn_reference (&lhs_ref,
1473                                                       get_alias_set (lhs),
1474                                                       TREE_TYPE (lhs), lhs_ops);
1475           if (lhs_ref_ok
1476               && !refs_may_alias_p_1 (ref, &lhs_ref, true))
1477             return NULL;
1478         }
1479       else
1480         {
1481           ao_ref_init (&lhs_ref, lhs);
1482           lhs_ref_ok = true;
1483         }
1484     }
1485
1486   base = ao_ref_base (ref);
1487   offset = ref->offset;
1488   maxsize = ref->max_size;
1489
1490   /* If we cannot constrain the size of the reference we cannot
1491      test if anything kills it.  */
1492   if (maxsize == -1)
1493     return (void *)-1;
1494
1495   /* We can't deduce anything useful from clobbers.  */
1496   if (gimple_clobber_p (def_stmt))
1497     return (void *)-1;
1498
1499   /* def_stmt may-defs *ref.  See if we can derive a value for *ref
1500      from that definition.
1501      1) Memset.  */
1502   if (is_gimple_reg_type (vr->type)
1503       && gimple_call_builtin_p (def_stmt, BUILT_IN_MEMSET)
1504       && integer_zerop (gimple_call_arg (def_stmt, 1))
1505       && host_integerp (gimple_call_arg (def_stmt, 2), 1)
1506       && TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR)
1507     {
1508       tree ref2 = TREE_OPERAND (gimple_call_arg (def_stmt, 0), 0);
1509       tree base2;
1510       HOST_WIDE_INT offset2, size2, maxsize2;
1511       base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &maxsize2);
1512       size2 = TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 2)) * 8;
1513       if ((unsigned HOST_WIDE_INT)size2 / 8
1514           == TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 2))
1515           && maxsize2 != -1
1516           && operand_equal_p (base, base2, 0)
1517           && offset2 <= offset
1518           && offset2 + size2 >= offset + maxsize)
1519         {
1520           tree val = build_zero_cst (vr->type);
1521           return vn_reference_lookup_or_insert_for_pieces
1522                    (vuse, vr->set, vr->type, vr->operands, val);
1523         }
1524     }
1525
1526   /* 2) Assignment from an empty CONSTRUCTOR.  */
1527   else if (is_gimple_reg_type (vr->type)
1528            && gimple_assign_single_p (def_stmt)
1529            && gimple_assign_rhs_code (def_stmt) == CONSTRUCTOR
1530            && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt)) == 0)
1531     {
1532       tree base2;
1533       HOST_WIDE_INT offset2, size2, maxsize2;
1534       base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
1535                                        &offset2, &size2, &maxsize2);
1536       if (maxsize2 != -1
1537           && operand_equal_p (base, base2, 0)
1538           && offset2 <= offset
1539           && offset2 + size2 >= offset + maxsize)
1540         {
1541           tree val = build_zero_cst (vr->type);
1542           return vn_reference_lookup_or_insert_for_pieces
1543                    (vuse, vr->set, vr->type, vr->operands, val);
1544         }
1545     }
1546
1547   /* 3) Assignment from a constant.  We can use folds native encode/interpret
1548      routines to extract the assigned bits.  */
1549   else if (vn_walk_kind == VN_WALKREWRITE
1550            && CHAR_BIT == 8 && BITS_PER_UNIT == 8
1551            && ref->size == maxsize
1552            && maxsize % BITS_PER_UNIT == 0
1553            && offset % BITS_PER_UNIT == 0
1554            && is_gimple_reg_type (vr->type)
1555            && gimple_assign_single_p (def_stmt)
1556            && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt)))
1557     {
1558       tree base2;
1559       HOST_WIDE_INT offset2, size2, maxsize2;
1560       base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
1561                                        &offset2, &size2, &maxsize2);
1562       if (maxsize2 != -1
1563           && maxsize2 == size2
1564           && size2 % BITS_PER_UNIT == 0
1565           && offset2 % BITS_PER_UNIT == 0
1566           && operand_equal_p (base, base2, 0)
1567           && offset2 <= offset
1568           && offset2 + size2 >= offset + maxsize)
1569         {
1570           /* We support up to 512-bit values (for V8DFmode).  */
1571           unsigned char buffer[64];
1572           int len;
1573
1574           len = native_encode_expr (gimple_assign_rhs1 (def_stmt),
1575                                     buffer, sizeof (buffer));
1576           if (len > 0)
1577             {
1578               tree val = native_interpret_expr (vr->type,
1579                                                 buffer
1580                                                 + ((offset - offset2)
1581                                                    / BITS_PER_UNIT),
1582                                                 ref->size / BITS_PER_UNIT);
1583               if (val)
1584                 return vn_reference_lookup_or_insert_for_pieces
1585                          (vuse, vr->set, vr->type, vr->operands, val);
1586             }
1587         }
1588     }
1589
1590   /* 4) Assignment from an SSA name which definition we may be able
1591      to access pieces from.  */
1592   else if (ref->size == maxsize
1593            && is_gimple_reg_type (vr->type)
1594            && gimple_assign_single_p (def_stmt)
1595            && TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME)
1596     {
1597       tree rhs1 = gimple_assign_rhs1 (def_stmt);
1598       gimple def_stmt2 = SSA_NAME_DEF_STMT (rhs1);
1599       if (is_gimple_assign (def_stmt2)
1600           && (gimple_assign_rhs_code (def_stmt2) == COMPLEX_EXPR
1601               || gimple_assign_rhs_code (def_stmt2) == CONSTRUCTOR)
1602           && types_compatible_p (vr->type, TREE_TYPE (TREE_TYPE (rhs1))))
1603         {
1604           tree base2;
1605           HOST_WIDE_INT offset2, size2, maxsize2, off;
1606           base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
1607                                            &offset2, &size2, &maxsize2);
1608           off = offset - offset2;
1609           if (maxsize2 != -1
1610               && maxsize2 == size2
1611               && operand_equal_p (base, base2, 0)
1612               && offset2 <= offset
1613               && offset2 + size2 >= offset + maxsize)
1614             {
1615               tree val = NULL_TREE;
1616               HOST_WIDE_INT elsz
1617                 = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (TREE_TYPE (rhs1))));
1618               if (gimple_assign_rhs_code (def_stmt2) == COMPLEX_EXPR)
1619                 {
1620                   if (off == 0)
1621                     val = gimple_assign_rhs1 (def_stmt2);
1622                   else if (off == elsz)
1623                     val = gimple_assign_rhs2 (def_stmt2);
1624                 }
1625               else if (gimple_assign_rhs_code (def_stmt2) == CONSTRUCTOR
1626                        && off % elsz == 0)
1627                 {
1628                   tree ctor = gimple_assign_rhs1 (def_stmt2);
1629                   unsigned i = off / elsz;
1630                   if (i < CONSTRUCTOR_NELTS (ctor))
1631                     {
1632                       constructor_elt *elt = CONSTRUCTOR_ELT (ctor, i);
1633                       if (TREE_CODE (TREE_TYPE (rhs1)) == VECTOR_TYPE)
1634                         {
1635                           if (TREE_CODE (TREE_TYPE (elt->value))
1636                               != VECTOR_TYPE)
1637                             val = elt->value;
1638                         }
1639                     }
1640                 }
1641               if (val)
1642                 return vn_reference_lookup_or_insert_for_pieces
1643                          (vuse, vr->set, vr->type, vr->operands, val);
1644             }
1645         }
1646     }
1647
1648   /* 5) For aggregate copies translate the reference through them if
1649      the copy kills ref.  */
1650   else if (vn_walk_kind == VN_WALKREWRITE
1651            && gimple_assign_single_p (def_stmt)
1652            && (DECL_P (gimple_assign_rhs1 (def_stmt))
1653                || TREE_CODE (gimple_assign_rhs1 (def_stmt)) == MEM_REF
1654                || handled_component_p (gimple_assign_rhs1 (def_stmt))))
1655     {
1656       tree base2;
1657       HOST_WIDE_INT offset2, size2, maxsize2;
1658       int i, j;
1659       vec<vn_reference_op_s>
1660           rhs = vNULL;
1661       vn_reference_op_t vro;
1662       ao_ref r;
1663
1664       if (!lhs_ref_ok)
1665         return (void *)-1;
1666
1667       /* See if the assignment kills REF.  */
1668       base2 = ao_ref_base (&lhs_ref);
1669       offset2 = lhs_ref.offset;
1670       size2 = lhs_ref.size;
1671       maxsize2 = lhs_ref.max_size;
1672       if (maxsize2 == -1
1673           || (base != base2 && !operand_equal_p (base, base2, 0))
1674           || offset2 > offset
1675           || offset2 + size2 < offset + maxsize)
1676         return (void *)-1;
1677
1678       /* Find the common base of ref and the lhs.  lhs_ops already
1679          contains valueized operands for the lhs.  */
1680       i = vr->operands.length () - 1;
1681       j = lhs_ops.length () - 1;
1682       while (j >= 0 && i >= 0
1683              && vn_reference_op_eq (&vr->operands[i], &lhs_ops[j]))
1684         {
1685           i--;
1686           j--;
1687         }
1688
1689       /* ???  The innermost op should always be a MEM_REF and we already
1690          checked that the assignment to the lhs kills vr.  Thus for
1691          aggregate copies using char[] types the vn_reference_op_eq
1692          may fail when comparing types for compatibility.  But we really
1693          don't care here - further lookups with the rewritten operands
1694          will simply fail if we messed up types too badly.  */
1695       if (j == 0 && i >= 0
1696           && lhs_ops[0].opcode == MEM_REF
1697           && lhs_ops[0].off != -1
1698           && (lhs_ops[0].off == vr->operands[i].off))
1699         i--, j--;
1700
1701       /* i now points to the first additional op.
1702          ???  LHS may not be completely contained in VR, one or more
1703          VIEW_CONVERT_EXPRs could be in its way.  We could at least
1704          try handling outermost VIEW_CONVERT_EXPRs.  */
1705       if (j != -1)
1706         return (void *)-1;
1707
1708       /* Now re-write REF to be based on the rhs of the assignment.  */
1709       copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt), &rhs);
1710       /* We need to pre-pend vr->operands[0..i] to rhs.  */
1711       if (i + 1 + rhs.length () > vr->operands.length ())
1712         {
1713           vec<vn_reference_op_s> old = vr->operands;
1714           vr->operands.safe_grow (i + 1 + rhs.length ());
1715           if (old == shared_lookup_references
1716               && vr->operands != old)
1717             shared_lookup_references = vNULL;
1718         }
1719       else
1720         vr->operands.truncate (i + 1 + rhs.length ());
1721       FOR_EACH_VEC_ELT (rhs, j, vro)
1722         vr->operands[i + 1 + j] = *vro;
1723       rhs.release ();
1724       vr->operands = valueize_refs (vr->operands);
1725       vr->hashcode = vn_reference_compute_hash (vr);
1726
1727       /* Adjust *ref from the new operands.  */
1728       if (!ao_ref_init_from_vn_reference (&r, vr->set, vr->type, vr->operands))
1729         return (void *)-1;
1730       /* This can happen with bitfields.  */
1731       if (ref->size != r.size)
1732         return (void *)-1;
1733       *ref = r;
1734
1735       /* Do not update last seen VUSE after translating.  */
1736       last_vuse_ptr = NULL;
1737
1738       /* Keep looking for the adjusted *REF / VR pair.  */
1739       return NULL;
1740     }
1741
1742   /* 6) For memcpy copies translate the reference through them if
1743      the copy kills ref.  */
1744   else if (vn_walk_kind == VN_WALKREWRITE
1745            && is_gimple_reg_type (vr->type)
1746            /* ???  Handle BCOPY as well.  */
1747            && (gimple_call_builtin_p (def_stmt, BUILT_IN_MEMCPY)
1748                || gimple_call_builtin_p (def_stmt, BUILT_IN_MEMPCPY)
1749                || gimple_call_builtin_p (def_stmt, BUILT_IN_MEMMOVE))
1750            && (TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR
1751                || TREE_CODE (gimple_call_arg (def_stmt, 0)) == SSA_NAME)
1752            && (TREE_CODE (gimple_call_arg (def_stmt, 1)) == ADDR_EXPR
1753                || TREE_CODE (gimple_call_arg (def_stmt, 1)) == SSA_NAME)
1754            && host_integerp (gimple_call_arg (def_stmt, 2), 1))
1755     {
1756       tree lhs, rhs;
1757       ao_ref r;
1758       HOST_WIDE_INT rhs_offset, copy_size, lhs_offset;
1759       vn_reference_op_s op;
1760       HOST_WIDE_INT at;
1761
1762
1763       /* Only handle non-variable, addressable refs.  */
1764       if (ref->size != maxsize
1765           || offset % BITS_PER_UNIT != 0
1766           || ref->size % BITS_PER_UNIT != 0)
1767         return (void *)-1;
1768
1769       /* Extract a pointer base and an offset for the destination.  */
1770       lhs = gimple_call_arg (def_stmt, 0);
1771       lhs_offset = 0;
1772       if (TREE_CODE (lhs) == SSA_NAME)
1773         lhs = SSA_VAL (lhs);
1774       if (TREE_CODE (lhs) == ADDR_EXPR)
1775         {
1776           tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (lhs, 0),
1777                                                     &lhs_offset);
1778           if (!tem)
1779             return (void *)-1;
1780           if (TREE_CODE (tem) == MEM_REF
1781               && host_integerp (TREE_OPERAND (tem, 1), 1))
1782             {
1783               lhs = TREE_OPERAND (tem, 0);
1784               lhs_offset += TREE_INT_CST_LOW (TREE_OPERAND (tem, 1));
1785             }
1786           else if (DECL_P (tem))
1787             lhs = build_fold_addr_expr (tem);
1788           else
1789             return (void *)-1;
1790         }
1791       if (TREE_CODE (lhs) != SSA_NAME
1792           && TREE_CODE (lhs) != ADDR_EXPR)
1793         return (void *)-1;
1794
1795       /* Extract a pointer base and an offset for the source.  */
1796       rhs = gimple_call_arg (def_stmt, 1);
1797       rhs_offset = 0;
1798       if (TREE_CODE (rhs) == SSA_NAME)
1799         rhs = SSA_VAL (rhs);
1800       if (TREE_CODE (rhs) == ADDR_EXPR)
1801         {
1802           tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs, 0),
1803                                                     &rhs_offset);
1804           if (!tem)
1805             return (void *)-1;
1806           if (TREE_CODE (tem) == MEM_REF
1807               && host_integerp (TREE_OPERAND (tem, 1), 1))
1808             {
1809               rhs = TREE_OPERAND (tem, 0);
1810               rhs_offset += TREE_INT_CST_LOW (TREE_OPERAND (tem, 1));
1811             }
1812           else if (DECL_P (tem))
1813             rhs = build_fold_addr_expr (tem);
1814           else
1815             return (void *)-1;
1816         }
1817       if (TREE_CODE (rhs) != SSA_NAME
1818           && TREE_CODE (rhs) != ADDR_EXPR)
1819         return (void *)-1;
1820
1821       copy_size = TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 2));
1822
1823       /* The bases of the destination and the references have to agree.  */
1824       if ((TREE_CODE (base) != MEM_REF
1825            && !DECL_P (base))
1826           || (TREE_CODE (base) == MEM_REF
1827               && (TREE_OPERAND (base, 0) != lhs
1828                   || !host_integerp (TREE_OPERAND (base, 1), 1)))
1829           || (DECL_P (base)
1830               && (TREE_CODE (lhs) != ADDR_EXPR
1831                   || TREE_OPERAND (lhs, 0) != base)))
1832         return (void *)-1;
1833
1834       /* And the access has to be contained within the memcpy destination.  */
1835       at = offset / BITS_PER_UNIT;
1836       if (TREE_CODE (base) == MEM_REF)
1837         at += TREE_INT_CST_LOW (TREE_OPERAND (base, 1));
1838       if (lhs_offset > at
1839           || lhs_offset + copy_size < at + maxsize / BITS_PER_UNIT)
1840         return (void *)-1;
1841
1842       /* Make room for 2 operands in the new reference.  */
1843       if (vr->operands.length () < 2)
1844         {
1845           vec<vn_reference_op_s> old = vr->operands;
1846           vr->operands.safe_grow_cleared (2);
1847           if (old == shared_lookup_references
1848               && vr->operands != old)
1849             shared_lookup_references.create (0);
1850         }
1851       else
1852         vr->operands.truncate (2);
1853
1854       /* The looked-through reference is a simple MEM_REF.  */
1855       memset (&op, 0, sizeof (op));
1856       op.type = vr->type;
1857       op.opcode = MEM_REF;
1858       op.op0 = build_int_cst (ptr_type_node, at - rhs_offset);
1859       op.off = at - lhs_offset + rhs_offset;
1860       vr->operands[0] = op;
1861       op.type = TREE_TYPE (rhs);
1862       op.opcode = TREE_CODE (rhs);
1863       op.op0 = rhs;
1864       op.off = -1;
1865       vr->operands[1] = op;
1866       vr->hashcode = vn_reference_compute_hash (vr);
1867
1868       /* Adjust *ref from the new operands.  */
1869       if (!ao_ref_init_from_vn_reference (&r, vr->set, vr->type, vr->operands))
1870         return (void *)-1;
1871       /* This can happen with bitfields.  */
1872       if (ref->size != r.size)
1873         return (void *)-1;
1874       *ref = r;
1875
1876       /* Do not update last seen VUSE after translating.  */
1877       last_vuse_ptr = NULL;
1878
1879       /* Keep looking for the adjusted *REF / VR pair.  */
1880       return NULL;
1881     }
1882
1883   /* Bail out and stop walking.  */
1884   return (void *)-1;
1885 }
1886
1887 /* Lookup a reference operation by it's parts, in the current hash table.
1888    Returns the resulting value number if it exists in the hash table,
1889    NULL_TREE otherwise.  VNRESULT will be filled in with the actual
1890    vn_reference_t stored in the hashtable if something is found.  */
1891
1892 tree
1893 vn_reference_lookup_pieces (tree vuse, alias_set_type set, tree type,
1894                             vec<vn_reference_op_s> operands,
1895                             vn_reference_t *vnresult, vn_lookup_kind kind)
1896 {
1897   struct vn_reference_s vr1;
1898   vn_reference_t tmp;
1899   tree cst;
1900
1901   if (!vnresult)
1902     vnresult = &tmp;
1903   *vnresult = NULL;
1904
1905   vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1906   shared_lookup_references.truncate (0);
1907   shared_lookup_references.safe_grow (operands.length ());
1908   memcpy (shared_lookup_references.address (),
1909           operands.address (),
1910           sizeof (vn_reference_op_s)
1911           * operands.length ());
1912   vr1.operands = operands = shared_lookup_references
1913     = valueize_refs (shared_lookup_references);
1914   vr1.type = type;
1915   vr1.set = set;
1916   vr1.hashcode = vn_reference_compute_hash (&vr1);
1917   if ((cst = fully_constant_vn_reference_p (&vr1)))
1918     return cst;
1919
1920   vn_reference_lookup_1 (&vr1, vnresult);
1921   if (!*vnresult
1922       && kind != VN_NOWALK
1923       && vr1.vuse)
1924     {
1925       ao_ref r;
1926       vn_walk_kind = kind;
1927       if (ao_ref_init_from_vn_reference (&r, set, type, vr1.operands))
1928         *vnresult =
1929           (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse,
1930                                                   vn_reference_lookup_2,
1931                                                   vn_reference_lookup_3, &vr1);
1932       if (vr1.operands != operands)
1933         vr1.operands.release ();
1934     }
1935
1936   if (*vnresult)
1937      return (*vnresult)->result;
1938
1939   return NULL_TREE;
1940 }
1941
1942 /* Lookup OP in the current hash table, and return the resulting value
1943    number if it exists in the hash table.  Return NULL_TREE if it does
1944    not exist in the hash table or if the result field of the structure
1945    was NULL..  VNRESULT will be filled in with the vn_reference_t
1946    stored in the hashtable if one exists.  */
1947
1948 tree
1949 vn_reference_lookup (tree op, tree vuse, vn_lookup_kind kind,
1950                      vn_reference_t *vnresult)
1951 {
1952   vec<vn_reference_op_s> operands;
1953   struct vn_reference_s vr1;
1954   tree cst;
1955   bool valuezied_anything;
1956
1957   if (vnresult)
1958     *vnresult = NULL;
1959
1960   vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1961   vr1.operands = operands
1962     = valueize_shared_reference_ops_from_ref (op, &valuezied_anything);
1963   vr1.type = TREE_TYPE (op);
1964   vr1.set = get_alias_set (op);
1965   vr1.hashcode = vn_reference_compute_hash (&vr1);
1966   if ((cst = fully_constant_vn_reference_p (&vr1)))
1967     return cst;
1968
1969   if (kind != VN_NOWALK
1970       && vr1.vuse)
1971     {
1972       vn_reference_t wvnresult;
1973       ao_ref r;
1974       /* Make sure to use a valueized reference if we valueized anything.
1975          Otherwise preserve the full reference for advanced TBAA.  */
1976       if (!valuezied_anything
1977           || !ao_ref_init_from_vn_reference (&r, vr1.set, vr1.type,
1978                                              vr1.operands))
1979         ao_ref_init (&r, op);
1980       vn_walk_kind = kind;
1981       wvnresult =
1982         (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse,
1983                                                 vn_reference_lookup_2,
1984                                                 vn_reference_lookup_3, &vr1);
1985       if (vr1.operands != operands)
1986         vr1.operands.release ();
1987       if (wvnresult)
1988         {
1989           if (vnresult)
1990             *vnresult = wvnresult;
1991           return wvnresult->result;
1992         }
1993
1994       return NULL_TREE;
1995     }
1996
1997   return vn_reference_lookup_1 (&vr1, vnresult);
1998 }
1999
2000
2001 /* Insert OP into the current hash table with a value number of
2002    RESULT, and return the resulting reference structure we created.  */
2003
2004 vn_reference_t
2005 vn_reference_insert (tree op, tree result, tree vuse, tree vdef)
2006 {
2007   void **slot;
2008   vn_reference_t vr1;
2009
2010   vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
2011   if (TREE_CODE (result) == SSA_NAME)
2012     vr1->value_id = VN_INFO (result)->value_id;
2013   else
2014     vr1->value_id = get_or_alloc_constant_value_id (result);
2015   vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
2016   vr1->operands = valueize_refs (create_reference_ops_from_ref (op));
2017   vr1->type = TREE_TYPE (op);
2018   vr1->set = get_alias_set (op);
2019   vr1->hashcode = vn_reference_compute_hash (vr1);
2020   vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result;
2021   vr1->result_vdef = vdef;
2022
2023   slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
2024                                    INSERT);
2025
2026   /* Because we lookup stores using vuses, and value number failures
2027      using the vdefs (see visit_reference_op_store for how and why),
2028      it's possible that on failure we may try to insert an already
2029      inserted store.  This is not wrong, there is no ssa name for a
2030      store that we could use as a differentiator anyway.  Thus, unlike
2031      the other lookup functions, you cannot gcc_assert (!*slot)
2032      here.  */
2033
2034   /* But free the old slot in case of a collision.  */
2035   if (*slot)
2036     free_reference (*slot);
2037
2038   *slot = vr1;
2039   return vr1;
2040 }
2041
2042 /* Insert a reference by it's pieces into the current hash table with
2043    a value number of RESULT.  Return the resulting reference
2044    structure we created.  */
2045
2046 vn_reference_t
2047 vn_reference_insert_pieces (tree vuse, alias_set_type set, tree type,
2048                             vec<vn_reference_op_s> operands,
2049                             tree result, unsigned int value_id)
2050
2051 {
2052   void **slot;
2053   vn_reference_t vr1;
2054
2055   vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
2056   vr1->value_id = value_id;
2057   vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
2058   vr1->operands = valueize_refs (operands);
2059   vr1->type = type;
2060   vr1->set = set;
2061   vr1->hashcode = vn_reference_compute_hash (vr1);
2062   if (result && TREE_CODE (result) == SSA_NAME)
2063     result = SSA_VAL (result);
2064   vr1->result = result;
2065
2066   slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
2067                                    INSERT);
2068
2069   /* At this point we should have all the things inserted that we have
2070      seen before, and we should never try inserting something that
2071      already exists.  */
2072   gcc_assert (!*slot);
2073   if (*slot)
2074     free_reference (*slot);
2075
2076   *slot = vr1;
2077   return vr1;
2078 }
2079
2080 /* Compute and return the hash value for nary operation VBO1.  */
2081
2082 hashval_t
2083 vn_nary_op_compute_hash (const vn_nary_op_t vno1)
2084 {
2085   hashval_t hash;
2086   unsigned i;
2087
2088   for (i = 0; i < vno1->length; ++i)
2089     if (TREE_CODE (vno1->op[i]) == SSA_NAME)
2090       vno1->op[i] = SSA_VAL (vno1->op[i]);
2091
2092   if (vno1->length == 2
2093       && commutative_tree_code (vno1->opcode)
2094       && tree_swap_operands_p (vno1->op[0], vno1->op[1], false))
2095     {
2096       tree temp = vno1->op[0];
2097       vno1->op[0] = vno1->op[1];
2098       vno1->op[1] = temp;
2099     }
2100
2101   hash = iterative_hash_hashval_t (vno1->opcode, 0);
2102   for (i = 0; i < vno1->length; ++i)
2103     hash = iterative_hash_expr (vno1->op[i], hash);
2104
2105   return hash;
2106 }
2107
2108 /* Return the computed hashcode for nary operation P1.  */
2109
2110 static hashval_t
2111 vn_nary_op_hash (const void *p1)
2112 {
2113   const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
2114   return vno1->hashcode;
2115 }
2116
2117 /* Compare nary operations P1 and P2 and return true if they are
2118    equivalent.  */
2119
2120 int
2121 vn_nary_op_eq (const void *p1, const void *p2)
2122 {
2123   const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
2124   const_vn_nary_op_t const vno2 = (const_vn_nary_op_t) p2;
2125   unsigned i;
2126
2127   if (vno1->hashcode != vno2->hashcode)
2128     return false;
2129
2130   if (vno1->length != vno2->length)
2131     return false;
2132
2133   if (vno1->opcode != vno2->opcode
2134       || !types_compatible_p (vno1->type, vno2->type))
2135     return false;
2136
2137   for (i = 0; i < vno1->length; ++i)
2138     if (!expressions_equal_p (vno1->op[i], vno2->op[i]))
2139       return false;
2140
2141   return true;
2142 }
2143
2144 /* Initialize VNO from the pieces provided.  */
2145
2146 static void
2147 init_vn_nary_op_from_pieces (vn_nary_op_t vno, unsigned int length,
2148                              enum tree_code code, tree type, tree *ops)
2149 {
2150   vno->opcode = code;
2151   vno->length = length;
2152   vno->type = type;
2153   memcpy (&vno->op[0], ops, sizeof (tree) * length);
2154 }
2155
2156 /* Initialize VNO from OP.  */
2157
2158 static void
2159 init_vn_nary_op_from_op (vn_nary_op_t vno, tree op)
2160 {
2161   unsigned i;
2162
2163   vno->opcode = TREE_CODE (op);
2164   vno->length = TREE_CODE_LENGTH (TREE_CODE (op));
2165   vno->type = TREE_TYPE (op);
2166   for (i = 0; i < vno->length; ++i)
2167     vno->op[i] = TREE_OPERAND (op, i);
2168 }
2169
2170 /* Return the number of operands for a vn_nary ops structure from STMT.  */
2171
2172 static unsigned int
2173 vn_nary_length_from_stmt (gimple stmt)
2174 {
2175   switch (gimple_assign_rhs_code (stmt))
2176     {
2177     case REALPART_EXPR:
2178     case IMAGPART_EXPR:
2179     case VIEW_CONVERT_EXPR:
2180       return 1;
2181
2182     case BIT_FIELD_REF:
2183       return 3;
2184
2185     case CONSTRUCTOR:
2186       return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
2187
2188     default:
2189       return gimple_num_ops (stmt) - 1;
2190     }
2191 }
2192
2193 /* Initialize VNO from STMT.  */
2194
2195 static void
2196 init_vn_nary_op_from_stmt (vn_nary_op_t vno, gimple stmt)
2197 {
2198   unsigned i;
2199
2200   vno->opcode = gimple_assign_rhs_code (stmt);
2201   vno->type = gimple_expr_type (stmt);
2202   switch (vno->opcode)
2203     {
2204     case REALPART_EXPR:
2205     case IMAGPART_EXPR:
2206     case VIEW_CONVERT_EXPR:
2207       vno->length = 1;
2208       vno->op[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
2209       break;
2210
2211     case BIT_FIELD_REF:
2212       vno->length = 3;
2213       vno->op[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
2214       vno->op[1] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 1);
2215       vno->op[2] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 2);
2216       break;
2217
2218     case CONSTRUCTOR:
2219       vno->length = CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
2220       for (i = 0; i < vno->length; ++i)
2221         vno->op[i] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt), i)->value;
2222       break;
2223
2224     default:
2225       gcc_checking_assert (!gimple_assign_single_p (stmt));
2226       vno->length = gimple_num_ops (stmt) - 1;
2227       for (i = 0; i < vno->length; ++i)
2228         vno->op[i] = gimple_op (stmt, i + 1);
2229     }
2230 }
2231
2232 /* Compute the hashcode for VNO and look for it in the hash table;
2233    return the resulting value number if it exists in the hash table.
2234    Return NULL_TREE if it does not exist in the hash table or if the
2235    result field of the operation is NULL.  VNRESULT will contain the
2236    vn_nary_op_t from the hashtable if it exists.  */
2237
2238 static tree
2239 vn_nary_op_lookup_1 (vn_nary_op_t vno, vn_nary_op_t *vnresult)
2240 {
2241   void **slot;
2242
2243   if (vnresult)
2244     *vnresult = NULL;
2245
2246   vno->hashcode = vn_nary_op_compute_hash (vno);
2247   slot = htab_find_slot_with_hash (current_info->nary, vno, vno->hashcode,
2248                                    NO_INSERT);
2249   if (!slot && current_info == optimistic_info)
2250     slot = htab_find_slot_with_hash (valid_info->nary, vno, vno->hashcode,
2251                                      NO_INSERT);
2252   if (!slot)
2253     return NULL_TREE;
2254   if (vnresult)
2255     *vnresult = (vn_nary_op_t)*slot;
2256   return ((vn_nary_op_t)*slot)->result;
2257 }
2258
2259 /* Lookup a n-ary operation by its pieces and return the resulting value
2260    number if it exists in the hash table.  Return NULL_TREE if it does
2261    not exist in the hash table or if the result field of the operation
2262    is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2263    if it exists.  */
2264
2265 tree
2266 vn_nary_op_lookup_pieces (unsigned int length, enum tree_code code,
2267                           tree type, tree *ops, vn_nary_op_t *vnresult)
2268 {
2269   vn_nary_op_t vno1 = XALLOCAVAR (struct vn_nary_op_s,
2270                                   sizeof_vn_nary_op (length));
2271   init_vn_nary_op_from_pieces (vno1, length, code, type, ops);
2272   return vn_nary_op_lookup_1 (vno1, vnresult);
2273 }
2274
2275 /* Lookup OP in the current hash table, and return the resulting value
2276    number if it exists in the hash table.  Return NULL_TREE if it does
2277    not exist in the hash table or if the result field of the operation
2278    is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2279    if it exists.  */
2280
2281 tree
2282 vn_nary_op_lookup (tree op, vn_nary_op_t *vnresult)
2283 {
2284   vn_nary_op_t vno1
2285     = XALLOCAVAR (struct vn_nary_op_s,
2286                   sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op))));
2287   init_vn_nary_op_from_op (vno1, op);
2288   return vn_nary_op_lookup_1 (vno1, vnresult);
2289 }
2290
2291 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2292    value number if it exists in the hash table.  Return NULL_TREE if
2293    it does not exist in the hash table.  VNRESULT will contain the
2294    vn_nary_op_t from the hashtable if it exists.  */
2295
2296 tree
2297 vn_nary_op_lookup_stmt (gimple stmt, vn_nary_op_t *vnresult)
2298 {
2299   vn_nary_op_t vno1
2300     = XALLOCAVAR (struct vn_nary_op_s,
2301                   sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt)));
2302   init_vn_nary_op_from_stmt (vno1, stmt);
2303   return vn_nary_op_lookup_1 (vno1, vnresult);
2304 }
2305
2306 /* Allocate a vn_nary_op_t with LENGTH operands on STACK.  */
2307
2308 static vn_nary_op_t
2309 alloc_vn_nary_op_noinit (unsigned int length, struct obstack *stack)
2310 {
2311   return (vn_nary_op_t) obstack_alloc (stack, sizeof_vn_nary_op (length));
2312 }
2313
2314 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
2315    obstack.  */
2316
2317 static vn_nary_op_t
2318 alloc_vn_nary_op (unsigned int length, tree result, unsigned int value_id)
2319 {
2320   vn_nary_op_t vno1 = alloc_vn_nary_op_noinit (length,
2321                                                &current_info->nary_obstack);
2322
2323   vno1->value_id = value_id;
2324   vno1->length = length;
2325   vno1->result = result;
2326
2327   return vno1;
2328 }
2329
2330 /* Insert VNO into TABLE.  If COMPUTE_HASH is true, then compute
2331    VNO->HASHCODE first.  */
2332
2333 static vn_nary_op_t
2334 vn_nary_op_insert_into (vn_nary_op_t vno, htab_t table, bool compute_hash)
2335 {
2336   void **slot;
2337
2338   if (compute_hash)
2339     vno->hashcode = vn_nary_op_compute_hash (vno);
2340
2341   slot = htab_find_slot_with_hash (table, vno, vno->hashcode, INSERT);
2342   gcc_assert (!*slot);
2343
2344   *slot = vno;
2345   return vno;
2346 }
2347
2348 /* Insert a n-ary operation into the current hash table using it's
2349    pieces.  Return the vn_nary_op_t structure we created and put in
2350    the hashtable.  */
2351
2352 vn_nary_op_t
2353 vn_nary_op_insert_pieces (unsigned int length, enum tree_code code,
2354                           tree type, tree *ops,
2355                           tree result, unsigned int value_id)
2356 {
2357   vn_nary_op_t vno1 = alloc_vn_nary_op (length, result, value_id);
2358   init_vn_nary_op_from_pieces (vno1, length, code, type, ops);
2359   return vn_nary_op_insert_into (vno1, current_info->nary, true);
2360 }
2361
2362 /* Insert OP into the current hash table with a value number of
2363    RESULT.  Return the vn_nary_op_t structure we created and put in
2364    the hashtable.  */
2365
2366 vn_nary_op_t
2367 vn_nary_op_insert (tree op, tree result)
2368 {
2369   unsigned length = TREE_CODE_LENGTH (TREE_CODE (op));
2370   vn_nary_op_t vno1;
2371
2372   vno1 = alloc_vn_nary_op (length, result, VN_INFO (result)->value_id);
2373   init_vn_nary_op_from_op (vno1, op);
2374   return vn_nary_op_insert_into (vno1, current_info->nary, true);
2375 }
2376
2377 /* Insert the rhs of STMT into the current hash table with a value number of
2378    RESULT.  */
2379
2380 vn_nary_op_t
2381 vn_nary_op_insert_stmt (gimple stmt, tree result)
2382 {
2383   vn_nary_op_t vno1
2384     = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt),
2385                         result, VN_INFO (result)->value_id);
2386   init_vn_nary_op_from_stmt (vno1, stmt);
2387   return vn_nary_op_insert_into (vno1, current_info->nary, true);
2388 }
2389
2390 /* Compute a hashcode for PHI operation VP1 and return it.  */
2391
2392 static inline hashval_t
2393 vn_phi_compute_hash (vn_phi_t vp1)
2394 {
2395   hashval_t result;
2396   int i;
2397   tree phi1op;
2398   tree type;
2399
2400   result = vp1->block->index;
2401
2402   /* If all PHI arguments are constants we need to distinguish
2403      the PHI node via its type.  */
2404   type = TREE_TYPE (vp1->phiargs[0]);
2405   result += (INTEGRAL_TYPE_P (type)
2406              + (INTEGRAL_TYPE_P (type)
2407                 ? TYPE_PRECISION (type) + TYPE_UNSIGNED (type) : 0));
2408
2409   FOR_EACH_VEC_ELT (vp1->phiargs, i, phi1op)
2410     {
2411       if (phi1op == VN_TOP)
2412         continue;
2413       result = iterative_hash_expr (phi1op, result);
2414     }
2415
2416   return result;
2417 }
2418
2419 /* Return the computed hashcode for phi operation P1.  */
2420
2421 static hashval_t
2422 vn_phi_hash (const void *p1)
2423 {
2424   const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
2425   return vp1->hashcode;
2426 }
2427
2428 /* Compare two phi entries for equality, ignoring VN_TOP arguments.  */
2429
2430 static int
2431 vn_phi_eq (const void *p1, const void *p2)
2432 {
2433   const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
2434   const_vn_phi_t const vp2 = (const_vn_phi_t) p2;
2435
2436   if (vp1->hashcode != vp2->hashcode)
2437     return false;
2438
2439   if (vp1->block == vp2->block)
2440     {
2441       int i;
2442       tree phi1op;
2443
2444       /* If the PHI nodes do not have compatible types
2445          they are not the same.  */
2446       if (!types_compatible_p (TREE_TYPE (vp1->phiargs[0]),
2447                                TREE_TYPE (vp2->phiargs[0])))
2448         return false;
2449
2450       /* Any phi in the same block will have it's arguments in the
2451          same edge order, because of how we store phi nodes.  */
2452       FOR_EACH_VEC_ELT (vp1->phiargs, i, phi1op)
2453         {
2454           tree phi2op = vp2->phiargs[i];
2455           if (phi1op == VN_TOP || phi2op == VN_TOP)
2456             continue;
2457           if (!expressions_equal_p (phi1op, phi2op))
2458             return false;
2459         }
2460       return true;
2461     }
2462   return false;
2463 }
2464
2465 static vec<tree> shared_lookup_phiargs;
2466
2467 /* Lookup PHI in the current hash table, and return the resulting
2468    value number if it exists in the hash table.  Return NULL_TREE if
2469    it does not exist in the hash table. */
2470
2471 static tree
2472 vn_phi_lookup (gimple phi)
2473 {
2474   void **slot;
2475   struct vn_phi_s vp1;
2476   unsigned i;
2477
2478   shared_lookup_phiargs.truncate (0);
2479
2480   /* Canonicalize the SSA_NAME's to their value number.  */
2481   for (i = 0; i < gimple_phi_num_args (phi); i++)
2482     {
2483       tree def = PHI_ARG_DEF (phi, i);
2484       def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
2485       shared_lookup_phiargs.safe_push (def);
2486     }
2487   vp1.phiargs = shared_lookup_phiargs;
2488   vp1.block = gimple_bb (phi);
2489   vp1.hashcode = vn_phi_compute_hash (&vp1);
2490   slot = htab_find_slot_with_hash (current_info->phis, &vp1, vp1.hashcode,
2491                                    NO_INSERT);
2492   if (!slot && current_info == optimistic_info)
2493     slot = htab_find_slot_with_hash (valid_info->phis, &vp1, vp1.hashcode,
2494                                      NO_INSERT);
2495   if (!slot)
2496     return NULL_TREE;
2497   return ((vn_phi_t)*slot)->result;
2498 }
2499
2500 /* Insert PHI into the current hash table with a value number of
2501    RESULT.  */
2502
2503 static vn_phi_t
2504 vn_phi_insert (gimple phi, tree result)
2505 {
2506   void **slot;
2507   vn_phi_t vp1 = (vn_phi_t) pool_alloc (current_info->phis_pool);
2508   unsigned i;
2509   vec<tree> args = vNULL;
2510
2511   /* Canonicalize the SSA_NAME's to their value number.  */
2512   for (i = 0; i < gimple_phi_num_args (phi); i++)
2513     {
2514       tree def = PHI_ARG_DEF (phi, i);
2515       def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
2516       args.safe_push (def);
2517     }
2518   vp1->value_id = VN_INFO (result)->value_id;
2519   vp1->phiargs = args;
2520   vp1->block = gimple_bb (phi);
2521   vp1->result = result;
2522   vp1->hashcode = vn_phi_compute_hash (vp1);
2523
2524   slot = htab_find_slot_with_hash (current_info->phis, vp1, vp1->hashcode,
2525                                    INSERT);
2526
2527   /* Because we iterate over phi operations more than once, it's
2528      possible the slot might already exist here, hence no assert.*/
2529   *slot = vp1;
2530   return vp1;
2531 }
2532
2533
2534 /* Print set of components in strongly connected component SCC to OUT. */
2535
2536 static void
2537 print_scc (FILE *out, vec<tree> scc)
2538 {
2539   tree var;
2540   unsigned int i;
2541
2542   fprintf (out, "SCC consists of:");
2543   FOR_EACH_VEC_ELT (scc, i, var)
2544     {
2545       fprintf (out, " ");
2546       print_generic_expr (out, var, 0);
2547     }
2548   fprintf (out, "\n");
2549 }
2550
2551 /* Set the value number of FROM to TO, return true if it has changed
2552    as a result.  */
2553
2554 static inline bool
2555 set_ssa_val_to (tree from, tree to)
2556 {
2557   tree currval = SSA_VAL (from);
2558
2559   if (from != to)
2560     {
2561       if (currval == from)
2562         {
2563           if (dump_file && (dump_flags & TDF_DETAILS))
2564             {
2565               fprintf (dump_file, "Not changing value number of ");
2566               print_generic_expr (dump_file, from, 0);
2567               fprintf (dump_file, " from VARYING to ");
2568               print_generic_expr (dump_file, to, 0);
2569               fprintf (dump_file, "\n");
2570             }
2571           return false;
2572         }
2573       else if (TREE_CODE (to) == SSA_NAME
2574                && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to))
2575         to = from;
2576     }
2577
2578   /* The only thing we allow as value numbers are VN_TOP, ssa_names
2579      and invariants.  So assert that here.  */
2580   gcc_assert (to != NULL_TREE
2581               && (to == VN_TOP
2582                   || TREE_CODE (to) == SSA_NAME
2583                   || is_gimple_min_invariant (to)));
2584
2585   if (dump_file && (dump_flags & TDF_DETAILS))
2586     {
2587       fprintf (dump_file, "Setting value number of ");
2588       print_generic_expr (dump_file, from, 0);
2589       fprintf (dump_file, " to ");
2590       print_generic_expr (dump_file, to, 0);
2591     }
2592
2593   if (currval != to  && !operand_equal_p (currval, to, OEP_PURE_SAME))
2594     {
2595       VN_INFO (from)->valnum = to;
2596       if (dump_file && (dump_flags & TDF_DETAILS))
2597         fprintf (dump_file, " (changed)\n");
2598       return true;
2599     }
2600   if (dump_file && (dump_flags & TDF_DETAILS))
2601     fprintf (dump_file, "\n");
2602   return false;
2603 }
2604
2605 /* Mark as processed all the definitions in the defining stmt of USE, or
2606    the USE itself.  */
2607
2608 static void
2609 mark_use_processed (tree use)
2610 {
2611   ssa_op_iter iter;
2612   def_operand_p defp;
2613   gimple stmt = SSA_NAME_DEF_STMT (use);
2614
2615   if (SSA_NAME_IS_DEFAULT_DEF (use) || gimple_code (stmt) == GIMPLE_PHI)
2616     {
2617       VN_INFO (use)->use_processed = true;
2618       return;
2619     }
2620
2621   FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
2622     {
2623       tree def = DEF_FROM_PTR (defp);
2624
2625       VN_INFO (def)->use_processed = true;
2626     }
2627 }
2628
2629 /* Set all definitions in STMT to value number to themselves.
2630    Return true if a value number changed. */
2631
2632 static bool
2633 defs_to_varying (gimple stmt)
2634 {
2635   bool changed = false;
2636   ssa_op_iter iter;
2637   def_operand_p defp;
2638
2639   FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
2640     {
2641       tree def = DEF_FROM_PTR (defp);
2642       changed |= set_ssa_val_to (def, def);
2643     }
2644   return changed;
2645 }
2646
2647 static bool expr_has_constants (tree expr);
2648 static tree valueize_expr (tree expr);
2649
2650 /* Visit a copy between LHS and RHS, return true if the value number
2651    changed.  */
2652
2653 static bool
2654 visit_copy (tree lhs, tree rhs)
2655 {
2656   /* Follow chains of copies to their destination.  */
2657   while (TREE_CODE (rhs) == SSA_NAME
2658          && SSA_VAL (rhs) != rhs)
2659     rhs = SSA_VAL (rhs);
2660
2661   /* The copy may have a more interesting constant filled expression
2662      (we don't, since we know our RHS is just an SSA name).  */
2663   if (TREE_CODE (rhs) == SSA_NAME)
2664     {
2665       VN_INFO (lhs)->has_constants = VN_INFO (rhs)->has_constants;
2666       VN_INFO (lhs)->expr = VN_INFO (rhs)->expr;
2667     }
2668
2669   return set_ssa_val_to (lhs, rhs);
2670 }
2671
2672 /* Visit a nary operator RHS, value number it, and return true if the
2673    value number of LHS has changed as a result.  */
2674
2675 static bool
2676 visit_nary_op (tree lhs, gimple stmt)
2677 {
2678   bool changed = false;
2679   tree result = vn_nary_op_lookup_stmt (stmt, NULL);
2680
2681   if (result)
2682     changed = set_ssa_val_to (lhs, result);
2683   else
2684     {
2685       changed = set_ssa_val_to (lhs, lhs);
2686       vn_nary_op_insert_stmt (stmt, lhs);
2687     }
2688
2689   return changed;
2690 }
2691
2692 /* Visit a call STMT storing into LHS.  Return true if the value number
2693    of the LHS has changed as a result.  */
2694
2695 static bool
2696 visit_reference_op_call (tree lhs, gimple stmt)
2697 {
2698   bool changed = false;
2699   struct vn_reference_s vr1;
2700   vn_reference_t vnresult = NULL;
2701   tree vuse = gimple_vuse (stmt);
2702   tree vdef = gimple_vdef (stmt);
2703
2704   /* Non-ssa lhs is handled in copy_reference_ops_from_call.  */
2705   if (lhs && TREE_CODE (lhs) != SSA_NAME)
2706     lhs = NULL_TREE;
2707
2708   vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
2709   vr1.operands = valueize_shared_reference_ops_from_call (stmt);
2710   vr1.type = gimple_expr_type (stmt);
2711   vr1.set = 0;
2712   vr1.hashcode = vn_reference_compute_hash (&vr1);
2713   vn_reference_lookup_1 (&vr1, &vnresult);
2714
2715   if (vnresult)
2716     {
2717       if (vnresult->result_vdef)
2718         changed |= set_ssa_val_to (vdef, vnresult->result_vdef);
2719
2720       if (!vnresult->result && lhs)
2721         vnresult->result = lhs;
2722
2723       if (vnresult->result && lhs)
2724         {
2725           changed |= set_ssa_val_to (lhs, vnresult->result);
2726
2727           if (VN_INFO (vnresult->result)->has_constants)
2728             VN_INFO (lhs)->has_constants = true;
2729         }
2730     }
2731   else
2732     {
2733       void **slot;
2734       vn_reference_t vr2;
2735       if (vdef)
2736         changed |= set_ssa_val_to (vdef, vdef);
2737       if (lhs)
2738         changed |= set_ssa_val_to (lhs, lhs);
2739       vr2 = (vn_reference_t) pool_alloc (current_info->references_pool);
2740       vr2->vuse = vr1.vuse;
2741       vr2->operands = valueize_refs (create_reference_ops_from_call (stmt));
2742       vr2->type = vr1.type;
2743       vr2->set = vr1.set;
2744       vr2->hashcode = vr1.hashcode;
2745       vr2->result = lhs;
2746       vr2->result_vdef = vdef;
2747       slot = htab_find_slot_with_hash (current_info->references,
2748                                        vr2, vr2->hashcode, INSERT);
2749       if (*slot)
2750         free_reference (*slot);
2751       *slot = vr2;
2752     }
2753
2754   return changed;
2755 }
2756
2757 /* Visit a load from a reference operator RHS, part of STMT, value number it,
2758    and return true if the value number of the LHS has changed as a result.  */
2759
2760 static bool
2761 visit_reference_op_load (tree lhs, tree op, gimple stmt)
2762 {
2763   bool changed = false;
2764   tree last_vuse;
2765   tree result;
2766
2767   last_vuse = gimple_vuse (stmt);
2768   last_vuse_ptr = &last_vuse;
2769   result = vn_reference_lookup (op, gimple_vuse (stmt),
2770                                 default_vn_walk_kind, NULL);
2771   last_vuse_ptr = NULL;
2772
2773   /* If we have a VCE, try looking up its operand as it might be stored in
2774      a different type.  */
2775   if (!result && TREE_CODE (op) == VIEW_CONVERT_EXPR)
2776     result = vn_reference_lookup (TREE_OPERAND (op, 0), gimple_vuse (stmt),
2777                                   default_vn_walk_kind, NULL);
2778
2779   /* We handle type-punning through unions by value-numbering based
2780      on offset and size of the access.  Be prepared to handle a
2781      type-mismatch here via creating a VIEW_CONVERT_EXPR.  */
2782   if (result
2783       && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (op)))
2784     {
2785       /* We will be setting the value number of lhs to the value number
2786          of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
2787          So first simplify and lookup this expression to see if it
2788          is already available.  */
2789       tree val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (op), result);
2790       if ((CONVERT_EXPR_P (val)
2791            || TREE_CODE (val) == VIEW_CONVERT_EXPR)
2792           && TREE_CODE (TREE_OPERAND (val, 0)) == SSA_NAME)
2793         {
2794           tree tem = valueize_expr (vn_get_expr_for (TREE_OPERAND (val, 0)));
2795           if ((CONVERT_EXPR_P (tem)
2796                || TREE_CODE (tem) == VIEW_CONVERT_EXPR)
2797               && (tem = fold_unary_ignore_overflow (TREE_CODE (val),
2798                                                     TREE_TYPE (val), tem)))
2799             val = tem;
2800         }
2801       result = val;
2802       if (!is_gimple_min_invariant (val)
2803           && TREE_CODE (val) != SSA_NAME)
2804         result = vn_nary_op_lookup (val, NULL);
2805       /* If the expression is not yet available, value-number lhs to
2806          a new SSA_NAME we create.  */
2807       if (!result)
2808         {
2809           result = make_temp_ssa_name (TREE_TYPE (lhs), gimple_build_nop (),
2810                                        "vntemp");
2811           /* Initialize value-number information properly.  */
2812           VN_INFO_GET (result)->valnum = result;
2813           VN_INFO (result)->value_id = get_next_value_id ();
2814           VN_INFO (result)->expr = val;
2815           VN_INFO (result)->has_constants = expr_has_constants (val);
2816           VN_INFO (result)->needs_insertion = true;
2817           /* As all "inserted" statements are singleton SCCs, insert
2818              to the valid table.  This is strictly needed to
2819              avoid re-generating new value SSA_NAMEs for the same
2820              expression during SCC iteration over and over (the
2821              optimistic table gets cleared after each iteration).
2822              We do not need to insert into the optimistic table, as
2823              lookups there will fall back to the valid table.  */
2824           if (current_info == optimistic_info)
2825             {
2826               current_info = valid_info;
2827               vn_nary_op_insert (val, result);
2828               current_info = optimistic_info;
2829             }
2830           else
2831             vn_nary_op_insert (val, result);
2832           if (dump_file && (dump_flags & TDF_DETAILS))
2833             {
2834               fprintf (dump_file, "Inserting name ");
2835               print_generic_expr (dump_file, result, 0);
2836               fprintf (dump_file, " for expression ");
2837               print_generic_expr (dump_file, val, 0);
2838               fprintf (dump_file, "\n");
2839             }
2840         }
2841     }
2842
2843   if (result)
2844     {
2845       changed = set_ssa_val_to (lhs, result);
2846       if (TREE_CODE (result) == SSA_NAME
2847           && VN_INFO (result)->has_constants)
2848         {
2849           VN_INFO (lhs)->expr = VN_INFO (result)->expr;
2850           VN_INFO (lhs)->has_constants = true;
2851         }
2852     }
2853   else
2854     {
2855       changed = set_ssa_val_to (lhs, lhs);
2856       vn_reference_insert (op, lhs, last_vuse, NULL_TREE);
2857     }
2858
2859   return changed;
2860 }
2861
2862
2863 /* Visit a store to a reference operator LHS, part of STMT, value number it,
2864    and return true if the value number of the LHS has changed as a result.  */
2865
2866 static bool
2867 visit_reference_op_store (tree lhs, tree op, gimple stmt)
2868 {
2869   bool changed = false;
2870   vn_reference_t vnresult = NULL;
2871   tree result, assign;
2872   bool resultsame = false;
2873   tree vuse = gimple_vuse (stmt);
2874   tree vdef = gimple_vdef (stmt);
2875
2876   /* First we want to lookup using the *vuses* from the store and see
2877      if there the last store to this location with the same address
2878      had the same value.
2879
2880      The vuses represent the memory state before the store.  If the
2881      memory state, address, and value of the store is the same as the
2882      last store to this location, then this store will produce the
2883      same memory state as that store.
2884
2885      In this case the vdef versions for this store are value numbered to those
2886      vuse versions, since they represent the same memory state after
2887      this store.
2888
2889      Otherwise, the vdefs for the store are used when inserting into
2890      the table, since the store generates a new memory state.  */
2891
2892   result = vn_reference_lookup (lhs, vuse, VN_NOWALK, NULL);
2893
2894   if (result)
2895     {
2896       if (TREE_CODE (result) == SSA_NAME)
2897         result = SSA_VAL (result);
2898       if (TREE_CODE (op) == SSA_NAME)
2899         op = SSA_VAL (op);
2900       resultsame = expressions_equal_p (result, op);
2901     }
2902
2903   if (!result || !resultsame)
2904     {
2905       assign = build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, op);
2906       vn_reference_lookup (assign, vuse, VN_NOWALK, &vnresult);
2907       if (vnresult)
2908         {
2909           VN_INFO (vdef)->use_processed = true;
2910           return set_ssa_val_to (vdef, vnresult->result_vdef);
2911         }
2912     }
2913
2914   if (!result || !resultsame)
2915     {
2916       if (dump_file && (dump_flags & TDF_DETAILS))
2917         {
2918           fprintf (dump_file, "No store match\n");
2919           fprintf (dump_file, "Value numbering store ");
2920           print_generic_expr (dump_file, lhs, 0);
2921           fprintf (dump_file, " to ");
2922           print_generic_expr (dump_file, op, 0);
2923           fprintf (dump_file, "\n");
2924         }
2925       /* Have to set value numbers before insert, since insert is
2926          going to valueize the references in-place.  */
2927       if (vdef)
2928         {
2929           changed |= set_ssa_val_to (vdef, vdef);
2930         }
2931
2932       /* Do not insert structure copies into the tables.  */
2933       if (is_gimple_min_invariant (op)
2934           || is_gimple_reg (op))
2935         vn_reference_insert (lhs, op, vdef, NULL);
2936
2937       assign = build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, op);
2938       vn_reference_insert (assign, lhs, vuse, vdef);
2939     }
2940   else
2941     {
2942       /* We had a match, so value number the vdef to have the value
2943          number of the vuse it came from.  */
2944
2945       if (dump_file && (dump_flags & TDF_DETAILS))
2946         fprintf (dump_file, "Store matched earlier value,"
2947                  "value numbering store vdefs to matching vuses.\n");
2948
2949       changed |= set_ssa_val_to (vdef, SSA_VAL (vuse));
2950     }
2951
2952   return changed;
2953 }
2954
2955 /* Visit and value number PHI, return true if the value number
2956    changed.  */
2957
2958 static bool
2959 visit_phi (gimple phi)
2960 {
2961   bool changed = false;
2962   tree result;
2963   tree sameval = VN_TOP;
2964   bool allsame = true;
2965   unsigned i;
2966
2967   /* TODO: We could check for this in init_sccvn, and replace this
2968      with a gcc_assert.  */
2969   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
2970     return set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
2971
2972   /* See if all non-TOP arguments have the same value.  TOP is
2973      equivalent to everything, so we can ignore it.  */
2974   for (i = 0; i < gimple_phi_num_args (phi); i++)
2975     {
2976       tree def = PHI_ARG_DEF (phi, i);
2977
2978       if (TREE_CODE (def) == SSA_NAME)
2979         def = SSA_VAL (def);
2980       if (def == VN_TOP)
2981         continue;
2982       if (sameval == VN_TOP)
2983         {
2984           sameval = def;
2985         }
2986       else
2987         {
2988           if (!expressions_equal_p (def, sameval))
2989             {
2990               allsame = false;
2991               break;
2992             }
2993         }
2994     }
2995
2996   /* If all value numbered to the same value, the phi node has that
2997      value.  */
2998   if (allsame)
2999     {
3000       if (is_gimple_min_invariant (sameval))
3001         {
3002           VN_INFO (PHI_RESULT (phi))->has_constants = true;
3003           VN_INFO (PHI_RESULT (phi))->expr = sameval;
3004         }
3005       else
3006         {
3007           VN_INFO (PHI_RESULT (phi))->has_constants = false;
3008           VN_INFO (PHI_RESULT (phi))->expr = sameval;
3009         }
3010
3011       if (TREE_CODE (sameval) == SSA_NAME)
3012         return visit_copy (PHI_RESULT (phi), sameval);
3013
3014       return set_ssa_val_to (PHI_RESULT (phi), sameval);
3015     }
3016
3017   /* Otherwise, see if it is equivalent to a phi node in this block.  */
3018   result = vn_phi_lookup (phi);
3019   if (result)
3020     {
3021       if (TREE_CODE (result) == SSA_NAME)
3022         changed = visit_copy (PHI_RESULT (phi), result);
3023       else
3024         changed = set_ssa_val_to (PHI_RESULT (phi), result);
3025     }
3026   else
3027     {
3028       vn_phi_insert (phi, PHI_RESULT (phi));
3029       VN_INFO (PHI_RESULT (phi))->has_constants = false;
3030       VN_INFO (PHI_RESULT (phi))->expr = PHI_RESULT (phi);
3031       changed = set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
3032     }
3033
3034   return changed;
3035 }
3036
3037 /* Return true if EXPR contains constants.  */
3038
3039 static bool
3040 expr_has_constants (tree expr)
3041 {
3042   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
3043     {
3044     case tcc_unary:
3045       return is_gimple_min_invariant (TREE_OPERAND (expr, 0));
3046
3047     case tcc_binary:
3048       return is_gimple_min_invariant (TREE_OPERAND (expr, 0))
3049         || is_gimple_min_invariant (TREE_OPERAND (expr, 1));
3050       /* Constants inside reference ops are rarely interesting, but
3051          it can take a lot of looking to find them.  */
3052     case tcc_reference:
3053     case tcc_declaration:
3054       return false;
3055     default:
3056       return is_gimple_min_invariant (expr);
3057     }
3058   return false;
3059 }
3060
3061 /* Return true if STMT contains constants.  */
3062
3063 static bool
3064 stmt_has_constants (gimple stmt)
3065 {
3066   if (gimple_code (stmt) != GIMPLE_ASSIGN)
3067     return false;
3068
3069   switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
3070     {
3071     case GIMPLE_UNARY_RHS:
3072       return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
3073
3074     case GIMPLE_BINARY_RHS:
3075       return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))
3076               || is_gimple_min_invariant (gimple_assign_rhs2 (stmt)));
3077     case GIMPLE_TERNARY_RHS:
3078       return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))
3079               || is_gimple_min_invariant (gimple_assign_rhs2 (stmt))
3080               || is_gimple_min_invariant (gimple_assign_rhs3 (stmt)));
3081     case GIMPLE_SINGLE_RHS:
3082       /* Constants inside reference ops are rarely interesting, but
3083          it can take a lot of looking to find them.  */
3084       return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
3085     default:
3086       gcc_unreachable ();
3087     }
3088   return false;
3089 }
3090
3091 /* Replace SSA_NAMES in expr with their value numbers, and return the
3092    result.
3093    This is performed in place. */
3094
3095 static tree
3096 valueize_expr (tree expr)
3097 {
3098   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
3099     {
3100     case tcc_binary:
3101       TREE_OPERAND (expr, 1) = vn_valueize (TREE_OPERAND (expr, 1));
3102       /* Fallthru.  */
3103     case tcc_unary:
3104       TREE_OPERAND (expr, 0) = vn_valueize (TREE_OPERAND (expr, 0));
3105       break;
3106     default:;
3107     }
3108   return expr;
3109 }
3110
3111 /* Simplify the binary expression RHS, and return the result if
3112    simplified. */
3113
3114 static tree
3115 simplify_binary_expression (gimple stmt)
3116 {
3117   tree result = NULL_TREE;
3118   tree op0 = gimple_assign_rhs1 (stmt);
3119   tree op1 = gimple_assign_rhs2 (stmt);
3120   enum tree_code code = gimple_assign_rhs_code (stmt);
3121
3122   /* This will not catch every single case we could combine, but will
3123      catch those with constants.  The goal here is to simultaneously
3124      combine constants between expressions, but avoid infinite
3125      expansion of expressions during simplification.  */
3126   if (TREE_CODE (op0) == SSA_NAME)
3127     {
3128       if (VN_INFO (op0)->has_constants
3129           || TREE_CODE_CLASS (code) == tcc_comparison
3130           || code == COMPLEX_EXPR)
3131         op0 = valueize_expr (vn_get_expr_for (op0));
3132       else
3133         op0 = vn_valueize (op0);
3134     }
3135
3136   if (TREE_CODE (op1) == SSA_NAME)
3137     {
3138       if (VN_INFO (op1)->has_constants
3139           || code == COMPLEX_EXPR)
3140         op1 = valueize_expr (vn_get_expr_for (op1));
3141       else
3142         op1 = vn_valueize (op1);
3143     }
3144
3145   /* Pointer plus constant can be represented as invariant address.
3146      Do so to allow further propatation, see also tree forwprop.  */
3147   if (code == POINTER_PLUS_EXPR
3148       && host_integerp (op1, 1)
3149       && TREE_CODE (op0) == ADDR_EXPR
3150       && is_gimple_min_invariant (op0))
3151     return build_invariant_address (TREE_TYPE (op0),
3152                                     TREE_OPERAND (op0, 0),
3153                                     TREE_INT_CST_LOW (op1));
3154
3155   /* Avoid folding if nothing changed.  */
3156   if (op0 == gimple_assign_rhs1 (stmt)
3157       && op1 == gimple_assign_rhs2 (stmt))
3158     return NULL_TREE;
3159
3160   fold_defer_overflow_warnings ();
3161
3162   result = fold_binary (code, gimple_expr_type (stmt), op0, op1);
3163   if (result)
3164     STRIP_USELESS_TYPE_CONVERSION (result);
3165
3166   fold_undefer_overflow_warnings (result && valid_gimple_rhs_p (result),
3167                                   stmt, 0);
3168
3169   /* Make sure result is not a complex expression consisting
3170      of operators of operators (IE (a + b) + (a + c))
3171      Otherwise, we will end up with unbounded expressions if
3172      fold does anything at all.  */
3173   if (result && valid_gimple_rhs_p (result))
3174     return result;
3175
3176   return NULL_TREE;
3177 }
3178
3179 /* Simplify the unary expression RHS, and return the result if
3180    simplified. */
3181
3182 static tree
3183 simplify_unary_expression (gimple stmt)
3184 {
3185   tree result = NULL_TREE;
3186   tree orig_op0, op0 = gimple_assign_rhs1 (stmt);
3187   enum tree_code code = gimple_assign_rhs_code (stmt);
3188
3189   /* We handle some tcc_reference codes here that are all
3190      GIMPLE_ASSIGN_SINGLE codes.  */
3191   if (code == REALPART_EXPR
3192       || code == IMAGPART_EXPR
3193       || code == VIEW_CONVERT_EXPR
3194       || code == BIT_FIELD_REF)
3195     op0 = TREE_OPERAND (op0, 0);
3196
3197   if (TREE_CODE (op0) != SSA_NAME)
3198     return NULL_TREE;
3199
3200   orig_op0 = op0;
3201   if (VN_INFO (op0)->has_constants)
3202     op0 = valueize_expr (vn_get_expr_for (op0));
3203   else if (CONVERT_EXPR_CODE_P (code)
3204            || code == REALPART_EXPR
3205            || code == IMAGPART_EXPR
3206            || code == VIEW_CONVERT_EXPR
3207            || code == BIT_FIELD_REF)
3208     {
3209       /* We want to do tree-combining on conversion-like expressions.
3210          Make sure we feed only SSA_NAMEs or constants to fold though.  */
3211       tree tem = valueize_expr (vn_get_expr_for (op0));
3212       if (UNARY_CLASS_P (tem)
3213           || BINARY_CLASS_P (tem)
3214           || TREE_CODE (tem) == VIEW_CONVERT_EXPR
3215           || TREE_CODE (tem) == SSA_NAME
3216           || TREE_CODE (tem) == CONSTRUCTOR
3217           || is_gimple_min_invariant (tem))
3218         op0 = tem;
3219     }
3220
3221   /* Avoid folding if nothing changed, but remember the expression.  */
3222   if (op0 == orig_op0)
3223     return NULL_TREE;
3224
3225   if (code == BIT_FIELD_REF)
3226     {
3227       tree rhs = gimple_assign_rhs1 (stmt);
3228       result = fold_ternary (BIT_FIELD_REF, TREE_TYPE (rhs),
3229                              op0, TREE_OPERAND (rhs, 1), TREE_OPERAND (rhs, 2));
3230     }
3231   else
3232     result = fold_unary_ignore_overflow (code, gimple_expr_type (stmt), op0);
3233   if (result)
3234     {
3235       STRIP_USELESS_TYPE_CONVERSION (result);
3236       if (valid_gimple_rhs_p (result))
3237         return result;
3238     }
3239
3240   return NULL_TREE;
3241 }
3242
3243 /* Try to simplify RHS using equivalences and constant folding.  */
3244
3245 static tree
3246 try_to_simplify (gimple stmt)
3247 {
3248   enum tree_code code = gimple_assign_rhs_code (stmt);
3249   tree tem;
3250
3251   /* For stores we can end up simplifying a SSA_NAME rhs.  Just return
3252      in this case, there is no point in doing extra work.  */
3253   if (code == SSA_NAME)
3254     return NULL_TREE;
3255
3256   /* First try constant folding based on our current lattice.  */
3257   tem = gimple_fold_stmt_to_constant_1 (stmt, vn_valueize);
3258   if (tem
3259       && (TREE_CODE (tem) == SSA_NAME
3260           || is_gimple_min_invariant (tem)))
3261     return tem;
3262
3263   /* If that didn't work try combining multiple statements.  */
3264   switch (TREE_CODE_CLASS (code))
3265     {
3266     case tcc_reference:
3267       /* Fallthrough for some unary codes that can operate on registers.  */
3268       if (!(code == REALPART_EXPR
3269             || code == IMAGPART_EXPR
3270             || code == VIEW_CONVERT_EXPR
3271             || code == BIT_FIELD_REF))
3272         break;
3273       /* We could do a little more with unary ops, if they expand
3274          into binary ops, but it's debatable whether it is worth it. */
3275     case tcc_unary:
3276       return simplify_unary_expression (stmt);
3277
3278     case tcc_comparison:
3279     case tcc_binary:
3280       return simplify_binary_expression (stmt);
3281
3282     default:
3283       break;
3284     }
3285
3286   return NULL_TREE;
3287 }
3288
3289 /* Visit and value number USE, return true if the value number
3290    changed. */
3291
3292 static bool
3293 visit_use (tree use)
3294 {
3295   bool changed = false;
3296   gimple stmt = SSA_NAME_DEF_STMT (use);
3297
3298   mark_use_processed (use);
3299
3300   gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
3301   if (dump_file && (dump_flags & TDF_DETAILS)
3302       && !SSA_NAME_IS_DEFAULT_DEF (use))
3303     {
3304       fprintf (dump_file, "Value numbering ");
3305       print_generic_expr (dump_file, use, 0);
3306       fprintf (dump_file, " stmt = ");
3307       print_gimple_stmt (dump_file, stmt, 0, 0);
3308     }
3309
3310   /* Handle uninitialized uses.  */
3311   if (SSA_NAME_IS_DEFAULT_DEF (use))
3312     changed = set_ssa_val_to (use, use);
3313   else
3314     {
3315       if (gimple_code (stmt) == GIMPLE_PHI)
3316         changed = visit_phi (stmt);
3317       else if (gimple_has_volatile_ops (stmt))
3318         changed = defs_to_varying (stmt);
3319       else if (is_gimple_assign (stmt))
3320         {
3321           enum tree_code code = gimple_assign_rhs_code (stmt);
3322           tree lhs = gimple_assign_lhs (stmt);
3323           tree rhs1 = gimple_assign_rhs1 (stmt);
3324           tree simplified;
3325
3326           /* Shortcut for copies. Simplifying copies is pointless,
3327              since we copy the expression and value they represent.  */
3328           if (code == SSA_NAME
3329               && TREE_CODE (lhs) == SSA_NAME)
3330             {
3331               changed = visit_copy (lhs, rhs1);
3332               goto done;
3333             }
3334           simplified = try_to_simplify (stmt);
3335           if (simplified)
3336             {
3337               if (dump_file && (dump_flags & TDF_DETAILS))
3338                 {
3339                   fprintf (dump_file, "RHS ");
3340                   print_gimple_expr (dump_file, stmt, 0, 0);
3341                   fprintf (dump_file, " simplified to ");
3342                   print_generic_expr (dump_file, simplified, 0);
3343                   if (TREE_CODE (lhs) == SSA_NAME)
3344                     fprintf (dump_file, " has constants %d\n",
3345                              expr_has_constants (simplified));
3346                   else
3347                     fprintf (dump_file, "\n");
3348                 }
3349             }
3350           /* Setting value numbers to constants will occasionally
3351              screw up phi congruence because constants are not
3352              uniquely associated with a single ssa name that can be
3353              looked up.  */
3354           if (simplified
3355               && is_gimple_min_invariant (simplified)
3356               && TREE_CODE (lhs) == SSA_NAME)
3357             {
3358               VN_INFO (lhs)->expr = simplified;
3359               VN_INFO (lhs)->has_constants = true;
3360               changed = set_ssa_val_to (lhs, simplified);
3361               goto done;
3362             }
3363           else if (simplified
3364                    && TREE_CODE (simplified) == SSA_NAME
3365                    && TREE_CODE (lhs) == SSA_NAME)
3366             {
3367               changed = visit_copy (lhs, simplified);
3368               goto done;
3369             }
3370           else if (simplified)
3371             {
3372               if (TREE_CODE (lhs) == SSA_NAME)
3373                 {
3374                   VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
3375                   /* We have to unshare the expression or else
3376                      valuizing may change the IL stream.  */
3377                   VN_INFO (lhs)->expr = unshare_expr (simplified);
3378                 }
3379             }
3380           else if (stmt_has_constants (stmt)
3381                    && TREE_CODE (lhs) == SSA_NAME)
3382             VN_INFO (lhs)->has_constants = true;
3383           else if (TREE_CODE (lhs) == SSA_NAME)
3384             {
3385               /* We reset expr and constantness here because we may
3386                  have been value numbering optimistically, and
3387                  iterating. They may become non-constant in this case,
3388                  even if they were optimistically constant. */
3389
3390               VN_INFO (lhs)->has_constants = false;
3391               VN_INFO (lhs)->expr = NULL_TREE;
3392             }
3393
3394           if ((TREE_CODE (lhs) == SSA_NAME
3395                /* We can substitute SSA_NAMEs that are live over
3396                   abnormal edges with their constant value.  */
3397                && !(gimple_assign_copy_p (stmt)
3398                     && is_gimple_min_invariant (rhs1))
3399                && !(simplified
3400                     && is_gimple_min_invariant (simplified))
3401                && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
3402               /* Stores or copies from SSA_NAMEs that are live over
3403                  abnormal edges are a problem.  */
3404               || (code == SSA_NAME
3405                   && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1)))
3406             changed = defs_to_varying (stmt);
3407           else if (REFERENCE_CLASS_P (lhs)
3408                    || DECL_P (lhs))
3409             changed = visit_reference_op_store (lhs, rhs1, stmt);
3410           else if (TREE_CODE (lhs) == SSA_NAME)
3411             {
3412               if ((gimple_assign_copy_p (stmt)
3413                    && is_gimple_min_invariant (rhs1))
3414                   || (simplified
3415                       && is_gimple_min_invariant (simplified)))
3416                 {
3417                   VN_INFO (lhs)->has_constants = true;
3418                   if (simplified)
3419                     changed = set_ssa_val_to (lhs, simplified);
3420                   else
3421                     changed = set_ssa_val_to (lhs, rhs1);
3422                 }
3423               else
3424                 {
3425                   /* First try to lookup the simplified expression.  */
3426                   if (simplified)
3427                     {
3428                       enum gimple_rhs_class rhs_class;
3429
3430
3431                       rhs_class = get_gimple_rhs_class (TREE_CODE (simplified));
3432                       if ((rhs_class == GIMPLE_UNARY_RHS
3433                            || rhs_class == GIMPLE_BINARY_RHS
3434                            || rhs_class == GIMPLE_TERNARY_RHS)
3435                           && valid_gimple_rhs_p (simplified))
3436                         {
3437                           tree result = vn_nary_op_lookup (simplified, NULL);
3438                           if (result)
3439                             {
3440                               changed = set_ssa_val_to (lhs, result);
3441                               goto done;
3442                             }
3443                         }
3444                     }
3445
3446                   /* Otherwise visit the original statement.  */
3447                   switch (vn_get_stmt_kind (stmt))
3448                     {
3449                     case VN_NARY:
3450                       changed = visit_nary_op (lhs, stmt);
3451                       break;
3452                     case VN_REFERENCE:
3453                       changed = visit_reference_op_load (lhs, rhs1, stmt);
3454                       break;
3455                     default:
3456                       changed = defs_to_varying (stmt);
3457                       break;
3458                     }
3459                 }
3460             }
3461           else
3462             changed = defs_to_varying (stmt);
3463         }
3464       else if (is_gimple_call (stmt))
3465         {
3466           tree lhs = gimple_call_lhs (stmt);
3467
3468           /* ???  We could try to simplify calls.  */
3469
3470           if (lhs && TREE_CODE (lhs) == SSA_NAME)
3471             {
3472               if (stmt_has_constants (stmt))
3473                 VN_INFO (lhs)->has_constants = true;
3474               else
3475                 {
3476                   /* We reset expr and constantness here because we may
3477                      have been value numbering optimistically, and
3478                      iterating.  They may become non-constant in this case,
3479                      even if they were optimistically constant.  */
3480                   VN_INFO (lhs)->has_constants = false;
3481                   VN_INFO (lhs)->expr = NULL_TREE;
3482                 }
3483
3484               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
3485                 {
3486                   changed = defs_to_varying (stmt);
3487                   goto done;
3488                 }
3489             }
3490
3491           if (!gimple_call_internal_p (stmt)
3492               && (/* Calls to the same function with the same vuse
3493                      and the same operands do not necessarily return the same
3494                      value, unless they're pure or const.  */
3495                   gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST)
3496                   /* If calls have a vdef, subsequent calls won't have
3497                      the same incoming vuse.  So, if 2 calls with vdef have the
3498                      same vuse, we know they're not subsequent.
3499                      We can value number 2 calls to the same function with the
3500                      same vuse and the same operands which are not subsequent
3501                      the same, because there is no code in the program that can
3502                      compare the 2 values.  */
3503                   || gimple_vdef (stmt)))
3504             changed = visit_reference_op_call (lhs, stmt);
3505           else
3506             changed = defs_to_varying (stmt);
3507         }
3508       else
3509         changed = defs_to_varying (stmt);
3510     }
3511  done:
3512   return changed;
3513 }
3514
3515 /* Compare two operands by reverse postorder index */
3516
3517 static int
3518 compare_ops (const void *pa, const void *pb)
3519 {
3520   const tree opa = *((const tree *)pa);
3521   const tree opb = *((const tree *)pb);
3522   gimple opstmta = SSA_NAME_DEF_STMT (opa);
3523   gimple opstmtb = SSA_NAME_DEF_STMT (opb);
3524   basic_block bba;
3525   basic_block bbb;
3526
3527   if (gimple_nop_p (opstmta) && gimple_nop_p (opstmtb))
3528     return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3529   else if (gimple_nop_p (opstmta))
3530     return -1;
3531   else if (gimple_nop_p (opstmtb))
3532     return 1;
3533
3534   bba = gimple_bb (opstmta);
3535   bbb = gimple_bb (opstmtb);
3536
3537   if (!bba && !bbb)
3538     return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3539   else if (!bba)
3540     return -1;
3541   else if (!bbb)
3542     return 1;
3543
3544   if (bba == bbb)
3545     {
3546       if (gimple_code (opstmta) == GIMPLE_PHI
3547           && gimple_code (opstmtb) == GIMPLE_PHI)
3548         return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3549       else if (gimple_code (opstmta) == GIMPLE_PHI)
3550         return -1;
3551       else if (gimple_code (opstmtb) == GIMPLE_PHI)
3552         return 1;
3553       else if (gimple_uid (opstmta) != gimple_uid (opstmtb))
3554         return gimple_uid (opstmta) - gimple_uid (opstmtb);
3555       else
3556         return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3557     }
3558   return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
3559 }
3560
3561 /* Sort an array containing members of a strongly connected component
3562    SCC so that the members are ordered by RPO number.
3563    This means that when the sort is complete, iterating through the
3564    array will give you the members in RPO order.  */
3565
3566 static void
3567 sort_scc (vec<tree> scc)
3568 {
3569   scc.qsort (compare_ops);
3570 }
3571
3572 /* Insert the no longer used nary ONARY to the hash INFO.  */
3573
3574 static void
3575 copy_nary (vn_nary_op_t onary, vn_tables_t info)
3576 {
3577   size_t size = sizeof_vn_nary_op (onary->length);
3578   vn_nary_op_t nary = alloc_vn_nary_op_noinit (onary->length,
3579                                                &info->nary_obstack);
3580   memcpy (nary, onary, size);
3581   vn_nary_op_insert_into (nary, info->nary, false);
3582 }
3583
3584 /* Insert the no longer used phi OPHI to the hash INFO.  */
3585
3586 static void
3587 copy_phi (vn_phi_t ophi, vn_tables_t info)
3588 {
3589   vn_phi_t phi = (vn_phi_t) pool_alloc (info->phis_pool);
3590   void **slot;
3591   memcpy (phi, ophi, sizeof (*phi));
3592   ophi->phiargs.create (0);
3593   slot = htab_find_slot_with_hash (info->phis, phi, phi->hashcode, INSERT);
3594   gcc_assert (!*slot);
3595   *slot = phi;
3596 }
3597
3598 /* Insert the no longer used reference OREF to the hash INFO.  */
3599
3600 static void
3601 copy_reference (vn_reference_t oref, vn_tables_t info)
3602 {
3603   vn_reference_t ref;
3604   void **slot;
3605   ref = (vn_reference_t) pool_alloc (info->references_pool);
3606   memcpy (ref, oref, sizeof (*ref));
3607   oref->operands.create (0);
3608   slot = htab_find_slot_with_hash (info->references, ref, ref->hashcode,
3609                                    INSERT);
3610   if (*slot)
3611     free_reference (*slot);
3612   *slot = ref;
3613 }
3614
3615 /* Process a strongly connected component in the SSA graph.  */
3616
3617 static void
3618 process_scc (vec<tree> scc)
3619 {
3620   tree var;
3621   unsigned int i;
3622   unsigned int iterations = 0;
3623   bool changed = true;
3624   htab_iterator hi;
3625   vn_nary_op_t nary;
3626   vn_phi_t phi;
3627   vn_reference_t ref;
3628
3629   /* If the SCC has a single member, just visit it.  */
3630   if (scc.length () == 1)
3631     {
3632       tree use = scc[0];
3633       if (VN_INFO (use)->use_processed)
3634         return;
3635       /* We need to make sure it doesn't form a cycle itself, which can
3636          happen for self-referential PHI nodes.  In that case we would
3637          end up inserting an expression with VN_TOP operands into the
3638          valid table which makes us derive bogus equivalences later.
3639          The cheapest way to check this is to assume it for all PHI nodes.  */
3640       if (gimple_code (SSA_NAME_DEF_STMT (use)) == GIMPLE_PHI)
3641         /* Fallthru to iteration.  */ ;
3642       else
3643         {
3644           visit_use (use);
3645           return;
3646         }
3647     }
3648
3649   /* Iterate over the SCC with the optimistic table until it stops
3650      changing.  */
3651   current_info = optimistic_info;
3652   while (changed)
3653     {
3654       changed = false;
3655       iterations++;
3656       if (dump_file && (dump_flags & TDF_DETAILS))
3657         fprintf (dump_file, "Starting iteration %d\n", iterations);
3658       /* As we are value-numbering optimistically we have to
3659          clear the expression tables and the simplified expressions
3660          in each iteration until we converge.  */
3661       htab_empty (optimistic_info->nary);
3662       htab_empty (optimistic_info->phis);
3663       htab_empty (optimistic_info->references);
3664       obstack_free (&optimistic_info->nary_obstack, NULL);
3665       gcc_obstack_init (&optimistic_info->nary_obstack);
3666       empty_alloc_pool (optimistic_info->phis_pool);
3667       empty_alloc_pool (optimistic_info->references_pool);
3668       FOR_EACH_VEC_ELT (scc, i, var)
3669         VN_INFO (var)->expr = NULL_TREE;
3670       FOR_EACH_VEC_ELT (scc, i, var)
3671         changed |= visit_use (var);
3672     }
3673
3674   statistics_histogram_event (cfun, "SCC iterations", iterations);
3675
3676   /* Finally, copy the contents of the no longer used optimistic
3677      table to the valid table.  */
3678   FOR_EACH_HTAB_ELEMENT (optimistic_info->nary, nary, vn_nary_op_t, hi)
3679     copy_nary (nary, valid_info);
3680   FOR_EACH_HTAB_ELEMENT (optimistic_info->phis, phi, vn_phi_t, hi)
3681     copy_phi (phi, valid_info);
3682   FOR_EACH_HTAB_ELEMENT (optimistic_info->references, ref, vn_reference_t, hi)
3683     copy_reference (ref, valid_info);
3684
3685   current_info = valid_info;
3686 }
3687
3688
3689 /* Pop the components of the found SCC for NAME off the SCC stack
3690    and process them.  Returns true if all went well, false if
3691    we run into resource limits.  */
3692
3693 static bool
3694 extract_and_process_scc_for_name (tree name)
3695 {
3696   vec<tree> scc = vNULL;
3697   tree x;
3698
3699   /* Found an SCC, pop the components off the SCC stack and
3700      process them.  */
3701   do
3702     {
3703       x = sccstack.pop ();
3704
3705       VN_INFO (x)->on_sccstack = false;
3706       scc.safe_push (x);
3707     } while (x != name);
3708
3709   /* Bail out of SCCVN in case a SCC turns out to be incredibly large.  */
3710   if (scc.length ()
3711       > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE))
3712     {
3713       if (dump_file)
3714         fprintf (dump_file, "WARNING: Giving up with SCCVN due to "
3715                  "SCC size %u exceeding %u\n", scc.length (),
3716                  (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE));
3717
3718       scc.release ();
3719       return false;
3720     }
3721
3722   if (scc.length () > 1)
3723     sort_scc (scc);
3724
3725   if (dump_file && (dump_flags & TDF_DETAILS))
3726     print_scc (dump_file, scc);
3727
3728   process_scc (scc);
3729
3730   scc.release ();
3731
3732   return true;
3733 }
3734
3735 /* Depth first search on NAME to discover and process SCC's in the SSA
3736    graph.
3737    Execution of this algorithm relies on the fact that the SCC's are
3738    popped off the stack in topological order.
3739    Returns true if successful, false if we stopped processing SCC's due
3740    to resource constraints.  */
3741
3742 static bool
3743 DFS (tree name)
3744 {
3745   vec<ssa_op_iter> itervec = vNULL;
3746   vec<tree> namevec = vNULL;
3747   use_operand_p usep = NULL;
3748   gimple defstmt;
3749   tree use;
3750   ssa_op_iter iter;
3751
3752 start_over:
3753   /* SCC info */
3754   VN_INFO (name)->dfsnum = next_dfs_num++;
3755   VN_INFO (name)->visited = true;
3756   VN_INFO (name)->low = VN_INFO (name)->dfsnum;
3757
3758   sccstack.safe_push (name);
3759   VN_INFO (name)->on_sccstack = true;
3760   defstmt = SSA_NAME_DEF_STMT (name);
3761
3762   /* Recursively DFS on our operands, looking for SCC's.  */
3763   if (!gimple_nop_p (defstmt))
3764     {
3765       /* Push a new iterator.  */
3766       if (gimple_code (defstmt) == GIMPLE_PHI)
3767         usep = op_iter_init_phiuse (&iter, defstmt, SSA_OP_ALL_USES);
3768       else
3769         usep = op_iter_init_use (&iter, defstmt, SSA_OP_ALL_USES);
3770     }
3771   else
3772     clear_and_done_ssa_iter (&iter);
3773
3774   while (1)
3775     {
3776       /* If we are done processing uses of a name, go up the stack
3777          of iterators and process SCCs as we found them.  */
3778       if (op_iter_done (&iter))
3779         {
3780           /* See if we found an SCC.  */
3781           if (VN_INFO (name)->low == VN_INFO (name)->dfsnum)
3782             if (!extract_and_process_scc_for_name (name))
3783               {
3784                 namevec.release ();
3785                 itervec.release ();
3786                 return false;
3787               }
3788
3789           /* Check if we are done.  */
3790           if (namevec.is_empty ())
3791             {
3792               namevec.release ();
3793               itervec.release ();
3794               return true;
3795             }
3796
3797           /* Restore the last use walker and continue walking there.  */
3798           use = name;
3799           name = namevec.pop ();
3800           memcpy (&iter, &itervec.last (),
3801                   sizeof (ssa_op_iter));
3802           itervec.pop ();
3803           goto continue_walking;
3804         }
3805
3806       use = USE_FROM_PTR (usep);
3807
3808       /* Since we handle phi nodes, we will sometimes get
3809          invariants in the use expression.  */
3810       if (TREE_CODE (use) == SSA_NAME)
3811         {
3812           if (! (VN_INFO (use)->visited))
3813             {
3814               /* Recurse by pushing the current use walking state on
3815                  the stack and starting over.  */
3816               itervec.safe_push (iter);
3817               namevec.safe_push (name);
3818               name = use;
3819               goto start_over;
3820
3821 continue_walking:
3822               VN_INFO (name)->low = MIN (VN_INFO (name)->low,
3823                                          VN_INFO (use)->low);
3824             }
3825           if (VN_INFO (use)->dfsnum < VN_INFO (name)->dfsnum
3826               && VN_INFO (use)->on_sccstack)
3827             {
3828               VN_INFO (name)->low = MIN (VN_INFO (use)->dfsnum,
3829                                          VN_INFO (name)->low);
3830             }
3831         }
3832
3833       usep = op_iter_next_use (&iter);
3834     }
3835 }
3836
3837 /* Allocate a value number table.  */
3838
3839 static void
3840 allocate_vn_table (vn_tables_t table)
3841 {
3842   table->phis = htab_create (23, vn_phi_hash, vn_phi_eq, free_phi);
3843   table->nary = htab_create (23, vn_nary_op_hash, vn_nary_op_eq, NULL);
3844   table->references = htab_create (23, vn_reference_hash, vn_reference_eq,
3845                                    free_reference);
3846
3847   gcc_obstack_init (&table->nary_obstack);
3848   table->phis_pool = create_alloc_pool ("VN phis",
3849                                         sizeof (struct vn_phi_s),
3850                                         30);
3851   table->references_pool = create_alloc_pool ("VN references",
3852                                               sizeof (struct vn_reference_s),
3853                                               30);
3854 }
3855
3856 /* Free a value number table.  */
3857
3858 static void
3859 free_vn_table (vn_tables_t table)
3860 {
3861   htab_delete (table->phis);
3862   htab_delete (table->nary);
3863   htab_delete (table->references);
3864   obstack_free (&table->nary_obstack, NULL);
3865   free_alloc_pool (table->phis_pool);
3866   free_alloc_pool (table->references_pool);
3867 }
3868
3869 static void
3870 init_scc_vn (void)
3871 {
3872   size_t i;
3873   int j;
3874   int *rpo_numbers_temp;
3875
3876   calculate_dominance_info (CDI_DOMINATORS);
3877   sccstack.create (0);
3878   constant_to_value_id = htab_create (23, vn_constant_hash, vn_constant_eq,
3879                                   free);
3880
3881   constant_value_ids = BITMAP_ALLOC (NULL);
3882
3883   next_dfs_num = 1;
3884   next_value_id = 1;
3885
3886   vn_ssa_aux_table.create (num_ssa_names + 1);
3887   /* VEC_alloc doesn't actually grow it to the right size, it just
3888      preallocates the space to do so.  */
3889   vn_ssa_aux_table.safe_grow_cleared (num_ssa_names + 1);
3890   gcc_obstack_init (&vn_ssa_aux_obstack);
3891
3892   shared_lookup_phiargs.create (0);
3893   shared_lookup_references.create (0);
3894   rpo_numbers = XNEWVEC (int, last_basic_block);
3895   rpo_numbers_temp = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
3896   pre_and_rev_post_order_compute (NULL, rpo_numbers_temp, false);
3897
3898   /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
3899      the i'th block in RPO order is bb.  We want to map bb's to RPO
3900      numbers, so we need to rearrange this array.  */
3901   for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
3902     rpo_numbers[rpo_numbers_temp[j]] = j;
3903
3904   XDELETE (rpo_numbers_temp);
3905
3906   VN_TOP = create_tmp_var_raw (void_type_node, "vn_top");
3907
3908   /* Create the VN_INFO structures, and initialize value numbers to
3909      TOP.  */
3910   for (i = 0; i < num_ssa_names; i++)
3911     {
3912       tree name = ssa_name (i);
3913       if (name)
3914         {
3915           VN_INFO_GET (name)->valnum = VN_TOP;
3916           VN_INFO (name)->expr = NULL_TREE;
3917           VN_INFO (name)->value_id = 0;
3918         }
3919     }
3920
3921   renumber_gimple_stmt_uids ();
3922
3923   /* Create the valid and optimistic value numbering tables.  */
3924   valid_info = XCNEW (struct vn_tables_s);
3925   allocate_vn_table (valid_info);
3926   optimistic_info = XCNEW (struct vn_tables_s);
3927   allocate_vn_table (optimistic_info);
3928 }
3929
3930 void
3931 free_scc_vn (void)
3932 {
3933   size_t i;
3934
3935   htab_delete (constant_to_value_id);
3936   BITMAP_FREE (constant_value_ids);
3937   shared_lookup_phiargs.release ();
3938   shared_lookup_references.release ();
3939   XDELETEVEC (rpo_numbers);
3940
3941   for (i = 0; i < num_ssa_names; i++)
3942     {
3943       tree name = ssa_name (i);
3944       if (name
3945           && VN_INFO (name)->needs_insertion)
3946         release_ssa_name (name);
3947     }
3948   obstack_free (&vn_ssa_aux_obstack, NULL);
3949   vn_ssa_aux_table.release ();
3950
3951   sccstack.release ();
3952   free_vn_table (valid_info);
3953   XDELETE (valid_info);
3954   free_vn_table (optimistic_info);
3955   XDELETE (optimistic_info);
3956 }
3957
3958 /* Set *ID if we computed something useful in RESULT.  */
3959
3960 static void
3961 set_value_id_for_result (tree result, unsigned int *id)
3962 {
3963   if (result)
3964     {
3965       if (TREE_CODE (result) == SSA_NAME)
3966         *id = VN_INFO (result)->value_id;
3967       else if (is_gimple_min_invariant (result))
3968         *id = get_or_alloc_constant_value_id (result);
3969     }
3970 }
3971
3972 /* Set the value ids in the valid hash tables.  */
3973
3974 static void
3975 set_hashtable_value_ids (void)
3976 {
3977   htab_iterator hi;
3978   vn_nary_op_t vno;
3979   vn_reference_t vr;
3980   vn_phi_t vp;
3981
3982   /* Now set the value ids of the things we had put in the hash
3983      table.  */
3984
3985   FOR_EACH_HTAB_ELEMENT (valid_info->nary,
3986                          vno, vn_nary_op_t, hi)
3987     set_value_id_for_result (vno->result, &vno->value_id);
3988
3989   FOR_EACH_HTAB_ELEMENT (valid_info->phis,
3990                          vp, vn_phi_t, hi)
3991     set_value_id_for_result (vp->result, &vp->value_id);
3992
3993   FOR_EACH_HTAB_ELEMENT (valid_info->references,
3994                          vr, vn_reference_t, hi)
3995     set_value_id_for_result (vr->result, &vr->value_id);
3996 }
3997
3998 /* Do SCCVN.  Returns true if it finished, false if we bailed out
3999    due to resource constraints.  DEFAULT_VN_WALK_KIND_ specifies
4000    how we use the alias oracle walking during the VN process.  */
4001
4002 bool
4003 run_scc_vn (vn_lookup_kind default_vn_walk_kind_)
4004 {
4005   size_t i;
4006   tree param;
4007
4008   default_vn_walk_kind = default_vn_walk_kind_;
4009
4010   init_scc_vn ();
4011   current_info = valid_info;
4012
4013   for (param = DECL_ARGUMENTS (current_function_decl);
4014        param;
4015        param = DECL_CHAIN (param))
4016     {
4017       tree def = ssa_default_def (cfun, param);
4018       if (def)
4019         VN_INFO (def)->valnum = def;
4020     }
4021
4022   for (i = 1; i < num_ssa_names; ++i)
4023     {
4024       tree name = ssa_name (i);
4025       if (name
4026           && VN_INFO (name)->visited == false
4027           && !has_zero_uses (name))
4028         if (!DFS (name))
4029           {
4030             free_scc_vn ();
4031             return false;
4032           }
4033     }
4034
4035   /* Initialize the value ids.  */
4036
4037   for (i = 1; i < num_ssa_names; ++i)
4038     {
4039       tree name = ssa_name (i);
4040       vn_ssa_aux_t info;
4041       if (!name)
4042         continue;
4043       info = VN_INFO (name);
4044       if (info->valnum == name
4045           || info->valnum == VN_TOP)
4046         info->value_id = get_next_value_id ();
4047       else if (is_gimple_min_invariant (info->valnum))
4048         info->value_id = get_or_alloc_constant_value_id (info->valnum);
4049     }
4050
4051   /* Propagate.  */
4052   for (i = 1; i < num_ssa_names; ++i)
4053     {
4054       tree name = ssa_name (i);
4055       vn_ssa_aux_t info;
4056       if (!name)
4057         continue;
4058       info = VN_INFO (name);
4059       if (TREE_CODE (info->valnum) == SSA_NAME
4060           && info->valnum != name
4061           && info->value_id != VN_INFO (info->valnum)->value_id)
4062         info->value_id = VN_INFO (info->valnum)->value_id;
4063     }
4064
4065   set_hashtable_value_ids ();
4066
4067   if (dump_file && (dump_flags & TDF_DETAILS))
4068     {
4069       fprintf (dump_file, "Value numbers:\n");
4070       for (i = 0; i < num_ssa_names; i++)
4071         {
4072           tree name = ssa_name (i);
4073           if (name
4074               && VN_INFO (name)->visited
4075               && SSA_VAL (name) != name)
4076             {
4077               print_generic_expr (dump_file, name, 0);
4078               fprintf (dump_file, " = ");
4079               print_generic_expr (dump_file, SSA_VAL (name), 0);
4080               fprintf (dump_file, "\n");
4081             }
4082         }
4083     }
4084
4085   return true;
4086 }
4087
4088 /* Return the maximum value id we have ever seen.  */
4089
4090 unsigned int
4091 get_max_value_id (void)
4092 {
4093   return next_value_id;
4094 }
4095
4096 /* Return the next unique value id.  */
4097
4098 unsigned int
4099 get_next_value_id (void)
4100 {
4101   return next_value_id++;
4102 }
4103
4104
4105 /* Compare two expressions E1 and E2 and return true if they are equal.  */
4106
4107 bool
4108 expressions_equal_p (tree e1, tree e2)
4109 {
4110   /* The obvious case.  */
4111   if (e1 == e2)
4112     return true;
4113
4114   /* If only one of them is null, they cannot be equal.  */
4115   if (!e1 || !e2)
4116     return false;
4117
4118   /* Now perform the actual comparison.  */
4119   if (TREE_CODE (e1) == TREE_CODE (e2)
4120       && operand_equal_p (e1, e2, OEP_PURE_SAME))
4121     return true;
4122
4123   return false;
4124 }
4125
4126
4127 /* Return true if the nary operation NARY may trap.  This is a copy
4128    of stmt_could_throw_1_p adjusted to the SCCVN IL.  */
4129
4130 bool
4131 vn_nary_may_trap (vn_nary_op_t nary)
4132 {
4133   tree type;
4134   tree rhs2 = NULL_TREE;
4135   bool honor_nans = false;
4136   bool honor_snans = false;
4137   bool fp_operation = false;
4138   bool honor_trapv = false;
4139   bool handled, ret;
4140   unsigned i;
4141
4142   if (TREE_CODE_CLASS (nary->opcode) == tcc_comparison
4143       || TREE_CODE_CLASS (nary->opcode) == tcc_unary
4144       || TREE_CODE_CLASS (nary->opcode) == tcc_binary)
4145     {
4146       type = nary->type;
4147       fp_operation = FLOAT_TYPE_P (type);
4148       if (fp_operation)
4149         {
4150           honor_nans = flag_trapping_math && !flag_finite_math_only;
4151           honor_snans = flag_signaling_nans != 0;
4152         }
4153       else if (INTEGRAL_TYPE_P (type)
4154                && TYPE_OVERFLOW_TRAPS (type))
4155         honor_trapv = true;
4156     }
4157   if (nary->length >= 2)
4158     rhs2 = nary->op[1];
4159   ret = operation_could_trap_helper_p (nary->opcode, fp_operation,
4160                                        honor_trapv,
4161                                        honor_nans, honor_snans, rhs2,
4162                                        &handled);
4163   if (handled
4164       && ret)
4165     return true;
4166
4167   for (i = 0; i < nary->length; ++i)
4168     if (tree_could_trap_p (nary->op[i]))
4169       return true;
4170
4171   return false;
4172 }