OSDN Git Service

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