OSDN Git Service

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