OSDN Git Service

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