OSDN Git Service

2012-05-03 Richard Guenther <rguenther@suse.de>
[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 value VALUE which is either a constant or an SSA name.  */
1352
1353 static vn_reference_t
1354 vn_reference_lookup_or_insert_for_pieces (tree vuse,
1355                                           alias_set_type set,
1356                                           tree type,
1357                                           VEC (vn_reference_op_s,
1358                                                heap) *operands,
1359                                           tree value)
1360 {
1361   struct vn_reference_s vr1;
1362   vn_reference_t result;
1363   unsigned value_id;
1364   vr1.vuse = vuse;
1365   vr1.operands = operands;
1366   vr1.type = type;
1367   vr1.set = set;
1368   vr1.hashcode = vn_reference_compute_hash (&vr1);
1369   if (vn_reference_lookup_1 (&vr1, &result))
1370     return result;
1371   if (TREE_CODE (value) == SSA_NAME)
1372     value_id = VN_INFO (value)->value_id;
1373   else
1374     value_id = get_or_alloc_constant_value_id (value);
1375   return vn_reference_insert_pieces (vuse, set, type,
1376                                      VEC_copy (vn_reference_op_s, heap,
1377                                                operands), value, value_id);
1378 }
1379
1380 /* Callback for walk_non_aliased_vuses.  Tries to perform a lookup
1381    from the statement defining VUSE and if not successful tries to
1382    translate *REFP and VR_ through an aggregate copy at the defintion
1383    of VUSE.  */
1384
1385 static void *
1386 vn_reference_lookup_3 (ao_ref *ref, tree vuse, void *vr_)
1387 {
1388   vn_reference_t vr = (vn_reference_t)vr_;
1389   gimple def_stmt = SSA_NAME_DEF_STMT (vuse);
1390   tree base;
1391   HOST_WIDE_INT offset, maxsize;
1392   static VEC (vn_reference_op_s, heap) *lhs_ops = NULL;
1393   ao_ref lhs_ref;
1394   bool lhs_ref_ok = false;
1395
1396   /* First try to disambiguate after value-replacing in the definitions LHS.  */
1397   if (is_gimple_assign (def_stmt))
1398     {
1399       VEC (vn_reference_op_s, heap) *tem;
1400       tree lhs = gimple_assign_lhs (def_stmt);
1401       bool valueized_anything = false;
1402       /* Avoid re-allocation overhead.  */
1403       VEC_truncate (vn_reference_op_s, lhs_ops, 0);
1404       copy_reference_ops_from_ref (lhs, &lhs_ops);
1405       tem = lhs_ops;
1406       lhs_ops = valueize_refs_1 (lhs_ops, &valueized_anything);
1407       gcc_assert (lhs_ops == tem);
1408       if (valueized_anything)
1409         {
1410           lhs_ref_ok = ao_ref_init_from_vn_reference (&lhs_ref,
1411                                                       get_alias_set (lhs),
1412                                                       TREE_TYPE (lhs), lhs_ops);
1413           if (lhs_ref_ok
1414               && !refs_may_alias_p_1 (ref, &lhs_ref, true))
1415             return NULL;
1416         }
1417       else
1418         {
1419           ao_ref_init (&lhs_ref, lhs);
1420           lhs_ref_ok = true;
1421         }
1422     }
1423
1424   base = ao_ref_base (ref);
1425   offset = ref->offset;
1426   maxsize = ref->max_size;
1427
1428   /* If we cannot constrain the size of the reference we cannot
1429      test if anything kills it.  */
1430   if (maxsize == -1)
1431     return (void *)-1;
1432
1433   /* We can't deduce anything useful from clobbers.  */
1434   if (gimple_clobber_p (def_stmt))
1435     return (void *)-1;
1436
1437   /* def_stmt may-defs *ref.  See if we can derive a value for *ref
1438      from that definition.
1439      1) Memset.  */
1440   if (is_gimple_reg_type (vr->type)
1441       && gimple_call_builtin_p (def_stmt, BUILT_IN_MEMSET)
1442       && integer_zerop (gimple_call_arg (def_stmt, 1))
1443       && host_integerp (gimple_call_arg (def_stmt, 2), 1)
1444       && TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR)
1445     {
1446       tree ref2 = TREE_OPERAND (gimple_call_arg (def_stmt, 0), 0);
1447       tree base2;
1448       HOST_WIDE_INT offset2, size2, maxsize2;
1449       base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &maxsize2);
1450       size2 = TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 2)) * 8;
1451       if ((unsigned HOST_WIDE_INT)size2 / 8
1452           == TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 2))
1453           && maxsize2 != -1
1454           && operand_equal_p (base, base2, 0)
1455           && offset2 <= offset
1456           && offset2 + size2 >= offset + maxsize)
1457         {
1458           tree val = build_zero_cst (vr->type);
1459           return vn_reference_lookup_or_insert_for_pieces
1460                    (vuse, vr->set, vr->type, vr->operands, val);
1461         }
1462     }
1463
1464   /* 2) Assignment from an empty CONSTRUCTOR.  */
1465   else if (is_gimple_reg_type (vr->type)
1466            && gimple_assign_single_p (def_stmt)
1467            && gimple_assign_rhs_code (def_stmt) == CONSTRUCTOR
1468            && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt)) == 0)
1469     {
1470       tree base2;
1471       HOST_WIDE_INT offset2, size2, maxsize2;
1472       base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
1473                                        &offset2, &size2, &maxsize2);
1474       if (maxsize2 != -1
1475           && operand_equal_p (base, base2, 0)
1476           && offset2 <= offset
1477           && offset2 + size2 >= offset + maxsize)
1478         {
1479           tree val = build_zero_cst (vr->type);
1480           return vn_reference_lookup_or_insert_for_pieces
1481                    (vuse, vr->set, vr->type, vr->operands, val);
1482         }
1483     }
1484
1485   /* 3) Assignment from a constant.  We can use folds native encode/interpret
1486      routines to extract the assigned bits.  */
1487   else if (CHAR_BIT == 8 && BITS_PER_UNIT == 8
1488            && ref->size == maxsize
1489            && maxsize % BITS_PER_UNIT == 0
1490            && offset % BITS_PER_UNIT == 0
1491            && is_gimple_reg_type (vr->type)
1492            && gimple_assign_single_p (def_stmt)
1493            && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt)))
1494     {
1495       tree base2;
1496       HOST_WIDE_INT offset2, size2, maxsize2;
1497       base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
1498                                        &offset2, &size2, &maxsize2);
1499       if (maxsize2 != -1
1500           && maxsize2 == size2
1501           && size2 % BITS_PER_UNIT == 0
1502           && offset2 % BITS_PER_UNIT == 0
1503           && operand_equal_p (base, base2, 0)
1504           && offset2 <= offset
1505           && offset2 + size2 >= offset + maxsize)
1506         {
1507           /* We support up to 512-bit values (for V8DFmode).  */
1508           unsigned char buffer[64];
1509           int len;
1510
1511           len = native_encode_expr (gimple_assign_rhs1 (def_stmt),
1512                                     buffer, sizeof (buffer));
1513           if (len > 0)
1514             {
1515               tree val = native_interpret_expr (vr->type,
1516                                                 buffer
1517                                                 + ((offset - offset2)
1518                                                    / BITS_PER_UNIT),
1519                                                 ref->size / BITS_PER_UNIT);
1520               if (val)
1521                 return vn_reference_lookup_or_insert_for_pieces
1522                          (vuse, vr->set, vr->type, vr->operands, val);
1523             }
1524         }
1525     }
1526
1527   /* 4) Assignment from an SSA name which definition we may be able
1528      to access pieces from.  */
1529   else if (ref->size == maxsize
1530            && is_gimple_reg_type (vr->type)
1531            && gimple_assign_single_p (def_stmt)
1532            && TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME)
1533     {
1534       tree rhs1 = gimple_assign_rhs1 (def_stmt);
1535       gimple def_stmt2 = SSA_NAME_DEF_STMT (rhs1);
1536       if (is_gimple_assign (def_stmt2)
1537           && (gimple_assign_rhs_code (def_stmt2) == COMPLEX_EXPR
1538               || gimple_assign_rhs_code (def_stmt2) == CONSTRUCTOR)
1539           && types_compatible_p (vr->type, TREE_TYPE (TREE_TYPE (rhs1))))
1540         {
1541           tree base2;
1542           HOST_WIDE_INT offset2, size2, maxsize2, off;
1543           base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
1544                                            &offset2, &size2, &maxsize2);
1545           off = offset - offset2;
1546           if (maxsize2 != -1
1547               && maxsize2 == size2
1548               && operand_equal_p (base, base2, 0)
1549               && offset2 <= offset
1550               && offset2 + size2 >= offset + maxsize)
1551             {
1552               tree val = NULL_TREE;
1553               HOST_WIDE_INT elsz
1554                 = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (TREE_TYPE (rhs1))));
1555               if (gimple_assign_rhs_code (def_stmt2) == COMPLEX_EXPR)
1556                 {
1557                   if (off == 0)
1558                     val = gimple_assign_rhs1 (def_stmt2);
1559                   else if (off == elsz)
1560                     val = gimple_assign_rhs2 (def_stmt2);
1561                 }
1562               else if (gimple_assign_rhs_code (def_stmt2) == CONSTRUCTOR
1563                        && off % elsz == 0)
1564                 {
1565                   tree ctor = gimple_assign_rhs1 (def_stmt2);
1566                   unsigned i = off / elsz;
1567                   if (i < CONSTRUCTOR_NELTS (ctor))
1568                     {
1569                       constructor_elt *elt = CONSTRUCTOR_ELT (ctor, i);
1570                       if (compare_tree_int (elt->index, i) == 0)
1571                         val = elt->value;
1572                     }
1573                 }
1574               if (val)
1575                 return vn_reference_lookup_or_insert_for_pieces
1576                          (vuse, vr->set, vr->type, vr->operands, val);
1577             }
1578         }
1579     }
1580
1581   /* 5) For aggregate copies translate the reference through them if
1582      the copy kills ref.  */
1583   else if (vn_walk_kind == VN_WALKREWRITE
1584            && gimple_assign_single_p (def_stmt)
1585            && (DECL_P (gimple_assign_rhs1 (def_stmt))
1586                || TREE_CODE (gimple_assign_rhs1 (def_stmt)) == MEM_REF
1587                || handled_component_p (gimple_assign_rhs1 (def_stmt))))
1588     {
1589       tree base2;
1590       HOST_WIDE_INT offset2, size2, maxsize2;
1591       int i, j;
1592       VEC (vn_reference_op_s, heap) *rhs = NULL;
1593       vn_reference_op_t vro;
1594       ao_ref r;
1595
1596       if (!lhs_ref_ok)
1597         return (void *)-1;
1598
1599       /* See if the assignment kills REF.  */
1600       base2 = ao_ref_base (&lhs_ref);
1601       offset2 = lhs_ref.offset;
1602       size2 = lhs_ref.size;
1603       maxsize2 = lhs_ref.max_size;
1604       if (maxsize2 == -1
1605           || (base != base2 && !operand_equal_p (base, base2, 0))
1606           || offset2 > offset
1607           || offset2 + size2 < offset + maxsize)
1608         return (void *)-1;
1609
1610       /* Find the common base of ref and the lhs.  lhs_ops already
1611          contains valueized operands for the lhs.  */
1612       i = VEC_length (vn_reference_op_s, vr->operands) - 1;
1613       j = VEC_length (vn_reference_op_s, lhs_ops) - 1;
1614       while (j >= 0 && i >= 0
1615              && vn_reference_op_eq (VEC_index (vn_reference_op_s,
1616                                                vr->operands, i),
1617                                     VEC_index (vn_reference_op_s, lhs_ops, j)))
1618         {
1619           i--;
1620           j--;
1621         }
1622
1623       /* ???  The innermost op should always be a MEM_REF and we already
1624          checked that the assignment to the lhs kills vr.  Thus for
1625          aggregate copies using char[] types the vn_reference_op_eq
1626          may fail when comparing types for compatibility.  But we really
1627          don't care here - further lookups with the rewritten operands
1628          will simply fail if we messed up types too badly.  */
1629       if (j == 0 && i >= 0
1630           && VEC_index (vn_reference_op_s, lhs_ops, 0)->opcode == MEM_REF
1631           && VEC_index (vn_reference_op_s, lhs_ops, 0)->off != -1
1632           && (VEC_index (vn_reference_op_s, lhs_ops, 0)->off
1633               == VEC_index (vn_reference_op_s, vr->operands, i)->off))
1634         i--, j--;
1635
1636       /* i now points to the first additional op.
1637          ???  LHS may not be completely contained in VR, one or more
1638          VIEW_CONVERT_EXPRs could be in its way.  We could at least
1639          try handling outermost VIEW_CONVERT_EXPRs.  */
1640       if (j != -1)
1641         return (void *)-1;
1642
1643       /* Now re-write REF to be based on the rhs of the assignment.  */
1644       copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt), &rhs);
1645       /* We need to pre-pend vr->operands[0..i] to rhs.  */
1646       if (i + 1 + VEC_length (vn_reference_op_s, rhs)
1647           > VEC_length (vn_reference_op_s, vr->operands))
1648         {
1649           VEC (vn_reference_op_s, heap) *old = vr->operands;
1650           VEC_safe_grow (vn_reference_op_s, heap, vr->operands,
1651                          i + 1 + VEC_length (vn_reference_op_s, rhs));
1652           if (old == shared_lookup_references
1653               && vr->operands != old)
1654             shared_lookup_references = NULL;
1655         }
1656       else
1657         VEC_truncate (vn_reference_op_s, vr->operands,
1658                       i + 1 + VEC_length (vn_reference_op_s, rhs));
1659       FOR_EACH_VEC_ELT (vn_reference_op_s, rhs, j, vro)
1660         VEC_replace (vn_reference_op_s, vr->operands, i + 1 + j, vro);
1661       VEC_free (vn_reference_op_s, heap, rhs);
1662       vr->operands = valueize_refs (vr->operands);
1663       vr->hashcode = vn_reference_compute_hash (vr);
1664
1665       /* Adjust *ref from the new operands.  */
1666       if (!ao_ref_init_from_vn_reference (&r, vr->set, vr->type, vr->operands))
1667         return (void *)-1;
1668       /* This can happen with bitfields.  */
1669       if (ref->size != r.size)
1670         return (void *)-1;
1671       *ref = r;
1672
1673       /* Do not update last seen VUSE after translating.  */
1674       last_vuse_ptr = NULL;
1675
1676       /* Keep looking for the adjusted *REF / VR pair.  */
1677       return NULL;
1678     }
1679
1680   /* 6) For memcpy copies translate the reference through them if
1681      the copy kills ref.  */
1682   else if (vn_walk_kind == VN_WALKREWRITE
1683            && is_gimple_reg_type (vr->type)
1684            /* ???  Handle BCOPY as well.  */
1685            && (gimple_call_builtin_p (def_stmt, BUILT_IN_MEMCPY)
1686                || gimple_call_builtin_p (def_stmt, BUILT_IN_MEMPCPY)
1687                || gimple_call_builtin_p (def_stmt, BUILT_IN_MEMMOVE))
1688            && (TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR
1689                || TREE_CODE (gimple_call_arg (def_stmt, 0)) == SSA_NAME)
1690            && (TREE_CODE (gimple_call_arg (def_stmt, 1)) == ADDR_EXPR
1691                || TREE_CODE (gimple_call_arg (def_stmt, 1)) == SSA_NAME)
1692            && host_integerp (gimple_call_arg (def_stmt, 2), 1))
1693     {
1694       tree lhs, rhs;
1695       ao_ref r;
1696       HOST_WIDE_INT rhs_offset, copy_size, lhs_offset;
1697       vn_reference_op_s op;
1698       HOST_WIDE_INT at;
1699
1700
1701       /* Only handle non-variable, addressable refs.  */
1702       if (ref->size != maxsize
1703           || offset % BITS_PER_UNIT != 0
1704           || ref->size % BITS_PER_UNIT != 0)
1705         return (void *)-1;
1706
1707       /* Extract a pointer base and an offset for the destination.  */
1708       lhs = gimple_call_arg (def_stmt, 0);
1709       lhs_offset = 0;
1710       if (TREE_CODE (lhs) == SSA_NAME)
1711         lhs = SSA_VAL (lhs);
1712       if (TREE_CODE (lhs) == ADDR_EXPR)
1713         {
1714           tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (lhs, 0),
1715                                                     &lhs_offset);
1716           if (!tem)
1717             return (void *)-1;
1718           if (TREE_CODE (tem) == MEM_REF
1719               && host_integerp (TREE_OPERAND (tem, 1), 1))
1720             {
1721               lhs = TREE_OPERAND (tem, 0);
1722               lhs_offset += TREE_INT_CST_LOW (TREE_OPERAND (tem, 1));
1723             }
1724           else if (DECL_P (tem))
1725             lhs = build_fold_addr_expr (tem);
1726           else
1727             return (void *)-1;
1728         }
1729       if (TREE_CODE (lhs) != SSA_NAME
1730           && TREE_CODE (lhs) != ADDR_EXPR)
1731         return (void *)-1;
1732
1733       /* Extract a pointer base and an offset for the source.  */
1734       rhs = gimple_call_arg (def_stmt, 1);
1735       rhs_offset = 0;
1736       if (TREE_CODE (rhs) == SSA_NAME)
1737         rhs = SSA_VAL (rhs);
1738       if (TREE_CODE (rhs) == ADDR_EXPR)
1739         {
1740           tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs, 0),
1741                                                     &rhs_offset);
1742           if (!tem)
1743             return (void *)-1;
1744           if (TREE_CODE (tem) == MEM_REF
1745               && host_integerp (TREE_OPERAND (tem, 1), 1))
1746             {
1747               rhs = TREE_OPERAND (tem, 0);
1748               rhs_offset += TREE_INT_CST_LOW (TREE_OPERAND (tem, 1));
1749             }
1750           else if (DECL_P (tem))
1751             rhs = build_fold_addr_expr (tem);
1752           else
1753             return (void *)-1;
1754         }
1755       if (TREE_CODE (rhs) != SSA_NAME
1756           && TREE_CODE (rhs) != ADDR_EXPR)
1757         return (void *)-1;
1758
1759       copy_size = TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 2));
1760
1761       /* The bases of the destination and the references have to agree.  */
1762       if ((TREE_CODE (base) != MEM_REF
1763            && !DECL_P (base))
1764           || (TREE_CODE (base) == MEM_REF
1765               && (TREE_OPERAND (base, 0) != lhs
1766                   || !host_integerp (TREE_OPERAND (base, 1), 1)))
1767           || (DECL_P (base)
1768               && (TREE_CODE (lhs) != ADDR_EXPR
1769                   || TREE_OPERAND (lhs, 0) != base)))
1770         return (void *)-1;
1771
1772       /* And the access has to be contained within the memcpy destination.  */
1773       at = offset / BITS_PER_UNIT;
1774       if (TREE_CODE (base) == MEM_REF)
1775         at += TREE_INT_CST_LOW (TREE_OPERAND (base, 1));
1776       if (lhs_offset > at
1777           || lhs_offset + copy_size < at + maxsize / BITS_PER_UNIT)
1778         return (void *)-1;
1779
1780       /* Make room for 2 operands in the new reference.  */
1781       if (VEC_length (vn_reference_op_s, vr->operands) < 2)
1782         {
1783           VEC (vn_reference_op_s, heap) *old = vr->operands;
1784           VEC_safe_grow (vn_reference_op_s, heap, vr->operands, 2);
1785           if (old == shared_lookup_references
1786               && vr->operands != old)
1787             shared_lookup_references = NULL;
1788         }
1789       else
1790         VEC_truncate (vn_reference_op_s, vr->operands, 2);
1791
1792       /* The looked-through reference is a simple MEM_REF.  */
1793       memset (&op, 0, sizeof (op));
1794       op.type = vr->type;
1795       op.opcode = MEM_REF;
1796       op.op0 = build_int_cst (ptr_type_node, at - rhs_offset);
1797       op.off = at - lhs_offset + rhs_offset;
1798       VEC_replace (vn_reference_op_s, vr->operands, 0, &op);
1799       op.type = TREE_TYPE (rhs);
1800       op.opcode = TREE_CODE (rhs);
1801       op.op0 = rhs;
1802       op.off = -1;
1803       VEC_replace (vn_reference_op_s, vr->operands, 1, &op);
1804       vr->hashcode = vn_reference_compute_hash (vr);
1805
1806       /* Adjust *ref from the new operands.  */
1807       if (!ao_ref_init_from_vn_reference (&r, vr->set, vr->type, vr->operands))
1808         return (void *)-1;
1809       /* This can happen with bitfields.  */
1810       if (ref->size != r.size)
1811         return (void *)-1;
1812       *ref = r;
1813
1814       /* Do not update last seen VUSE after translating.  */
1815       last_vuse_ptr = NULL;
1816
1817       /* Keep looking for the adjusted *REF / VR pair.  */
1818       return NULL;
1819     }
1820
1821   /* Bail out and stop walking.  */
1822   return (void *)-1;
1823 }
1824
1825 /* Lookup a reference operation by it's parts, in the current hash table.
1826    Returns the resulting value number if it exists in the hash table,
1827    NULL_TREE otherwise.  VNRESULT will be filled in with the actual
1828    vn_reference_t stored in the hashtable if something is found.  */
1829
1830 tree
1831 vn_reference_lookup_pieces (tree vuse, alias_set_type set, tree type,
1832                             VEC (vn_reference_op_s, heap) *operands,
1833                             vn_reference_t *vnresult, vn_lookup_kind kind)
1834 {
1835   struct vn_reference_s vr1;
1836   vn_reference_t tmp;
1837   tree cst;
1838
1839   if (!vnresult)
1840     vnresult = &tmp;
1841   *vnresult = NULL;
1842
1843   vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1844   VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
1845   VEC_safe_grow (vn_reference_op_s, heap, shared_lookup_references,
1846                  VEC_length (vn_reference_op_s, operands));
1847   memcpy (VEC_address (vn_reference_op_s, shared_lookup_references),
1848           VEC_address (vn_reference_op_s, operands),
1849           sizeof (vn_reference_op_s)
1850           * VEC_length (vn_reference_op_s, operands));
1851   vr1.operands = operands = shared_lookup_references
1852     = valueize_refs (shared_lookup_references);
1853   vr1.type = type;
1854   vr1.set = set;
1855   vr1.hashcode = vn_reference_compute_hash (&vr1);
1856   if ((cst = fully_constant_vn_reference_p (&vr1)))
1857     return cst;
1858
1859   vn_reference_lookup_1 (&vr1, vnresult);
1860   if (!*vnresult
1861       && kind != VN_NOWALK
1862       && vr1.vuse)
1863     {
1864       ao_ref r;
1865       vn_walk_kind = kind;
1866       if (ao_ref_init_from_vn_reference (&r, set, type, vr1.operands))
1867         *vnresult =
1868           (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse,
1869                                                   vn_reference_lookup_2,
1870                                                   vn_reference_lookup_3, &vr1);
1871       if (vr1.operands != operands)
1872         VEC_free (vn_reference_op_s, heap, vr1.operands);
1873     }
1874
1875   if (*vnresult)
1876      return (*vnresult)->result;
1877
1878   return NULL_TREE;
1879 }
1880
1881 /* Lookup OP in the current hash table, and return the resulting value
1882    number if it exists in the hash table.  Return NULL_TREE if it does
1883    not exist in the hash table or if the result field of the structure
1884    was NULL..  VNRESULT will be filled in with the vn_reference_t
1885    stored in the hashtable if one exists.  */
1886
1887 tree
1888 vn_reference_lookup (tree op, tree vuse, vn_lookup_kind kind,
1889                      vn_reference_t *vnresult)
1890 {
1891   VEC (vn_reference_op_s, heap) *operands;
1892   struct vn_reference_s vr1;
1893   tree cst;
1894   bool valuezied_anything;
1895
1896   if (vnresult)
1897     *vnresult = NULL;
1898
1899   vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1900   vr1.operands = operands
1901     = valueize_shared_reference_ops_from_ref (op, &valuezied_anything);
1902   vr1.type = TREE_TYPE (op);
1903   vr1.set = get_alias_set (op);
1904   vr1.hashcode = vn_reference_compute_hash (&vr1);
1905   if ((cst = fully_constant_vn_reference_p (&vr1)))
1906     return cst;
1907
1908   if (kind != VN_NOWALK
1909       && vr1.vuse)
1910     {
1911       vn_reference_t wvnresult;
1912       ao_ref r;
1913       /* Make sure to use a valueized reference if we valueized anything.
1914          Otherwise preserve the full reference for advanced TBAA.  */
1915       if (!valuezied_anything
1916           || !ao_ref_init_from_vn_reference (&r, vr1.set, vr1.type,
1917                                              vr1.operands))
1918         ao_ref_init (&r, op);
1919       vn_walk_kind = kind;
1920       wvnresult =
1921         (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse,
1922                                                 vn_reference_lookup_2,
1923                                                 vn_reference_lookup_3, &vr1);
1924       if (vr1.operands != operands)
1925         VEC_free (vn_reference_op_s, heap, vr1.operands);
1926       if (wvnresult)
1927         {
1928           if (vnresult)
1929             *vnresult = wvnresult;
1930           return wvnresult->result;
1931         }
1932
1933       return NULL_TREE;
1934     }
1935
1936   return vn_reference_lookup_1 (&vr1, vnresult);
1937 }
1938
1939
1940 /* Insert OP into the current hash table with a value number of
1941    RESULT, and return the resulting reference structure we created.  */
1942
1943 vn_reference_t
1944 vn_reference_insert (tree op, tree result, tree vuse)
1945 {
1946   void **slot;
1947   vn_reference_t vr1;
1948
1949   vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
1950   if (TREE_CODE (result) == SSA_NAME)
1951     vr1->value_id = VN_INFO (result)->value_id;
1952   else
1953     vr1->value_id = get_or_alloc_constant_value_id (result);
1954   vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1955   vr1->operands = valueize_refs (create_reference_ops_from_ref (op));
1956   vr1->type = TREE_TYPE (op);
1957   vr1->set = get_alias_set (op);
1958   vr1->hashcode = vn_reference_compute_hash (vr1);
1959   vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result;
1960
1961   slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
1962                                    INSERT);
1963
1964   /* Because we lookup stores using vuses, and value number failures
1965      using the vdefs (see visit_reference_op_store for how and why),
1966      it's possible that on failure we may try to insert an already
1967      inserted store.  This is not wrong, there is no ssa name for a
1968      store that we could use as a differentiator anyway.  Thus, unlike
1969      the other lookup functions, you cannot gcc_assert (!*slot)
1970      here.  */
1971
1972   /* But free the old slot in case of a collision.  */
1973   if (*slot)
1974     free_reference (*slot);
1975
1976   *slot = vr1;
1977   return vr1;
1978 }
1979
1980 /* Insert a reference by it's pieces into the current hash table with
1981    a value number of RESULT.  Return the resulting reference
1982    structure we created.  */
1983
1984 vn_reference_t
1985 vn_reference_insert_pieces (tree vuse, alias_set_type set, tree type,
1986                             VEC (vn_reference_op_s, heap) *operands,
1987                             tree result, unsigned int value_id)
1988
1989 {
1990   void **slot;
1991   vn_reference_t vr1;
1992
1993   vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
1994   vr1->value_id = value_id;
1995   vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1996   vr1->operands = valueize_refs (operands);
1997   vr1->type = type;
1998   vr1->set = set;
1999   vr1->hashcode = vn_reference_compute_hash (vr1);
2000   if (result && TREE_CODE (result) == SSA_NAME)
2001     result = SSA_VAL (result);
2002   vr1->result = result;
2003
2004   slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
2005                                    INSERT);
2006
2007   /* At this point we should have all the things inserted that we have
2008      seen before, and we should never try inserting something that
2009      already exists.  */
2010   gcc_assert (!*slot);
2011   if (*slot)
2012     free_reference (*slot);
2013
2014   *slot = vr1;
2015   return vr1;
2016 }
2017
2018 /* Compute and return the hash value for nary operation VBO1.  */
2019
2020 hashval_t
2021 vn_nary_op_compute_hash (const vn_nary_op_t vno1)
2022 {
2023   hashval_t hash;
2024   unsigned i;
2025
2026   for (i = 0; i < vno1->length; ++i)
2027     if (TREE_CODE (vno1->op[i]) == SSA_NAME)
2028       vno1->op[i] = SSA_VAL (vno1->op[i]);
2029
2030   if (vno1->length == 2
2031       && commutative_tree_code (vno1->opcode)
2032       && tree_swap_operands_p (vno1->op[0], vno1->op[1], false))
2033     {
2034       tree temp = vno1->op[0];
2035       vno1->op[0] = vno1->op[1];
2036       vno1->op[1] = temp;
2037     }
2038
2039   hash = iterative_hash_hashval_t (vno1->opcode, 0);
2040   for (i = 0; i < vno1->length; ++i)
2041     hash = iterative_hash_expr (vno1->op[i], hash);
2042
2043   return hash;
2044 }
2045
2046 /* Return the computed hashcode for nary operation P1.  */
2047
2048 static hashval_t
2049 vn_nary_op_hash (const void *p1)
2050 {
2051   const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
2052   return vno1->hashcode;
2053 }
2054
2055 /* Compare nary operations P1 and P2 and return true if they are
2056    equivalent.  */
2057
2058 int
2059 vn_nary_op_eq (const void *p1, const void *p2)
2060 {
2061   const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
2062   const_vn_nary_op_t const vno2 = (const_vn_nary_op_t) p2;
2063   unsigned i;
2064
2065   if (vno1->hashcode != vno2->hashcode)
2066     return false;
2067
2068   if (vno1->length != vno2->length)
2069     return false;
2070
2071   if (vno1->opcode != vno2->opcode
2072       || !types_compatible_p (vno1->type, vno2->type))
2073     return false;
2074
2075   for (i = 0; i < vno1->length; ++i)
2076     if (!expressions_equal_p (vno1->op[i], vno2->op[i]))
2077       return false;
2078
2079   return true;
2080 }
2081
2082 /* Initialize VNO from the pieces provided.  */
2083
2084 static void
2085 init_vn_nary_op_from_pieces (vn_nary_op_t vno, unsigned int length,
2086                              enum tree_code code, tree type, tree *ops)
2087 {
2088   vno->opcode = code;
2089   vno->length = length;
2090   vno->type = type;
2091   memcpy (&vno->op[0], ops, sizeof (tree) * length);
2092 }
2093
2094 /* Initialize VNO from OP.  */
2095
2096 static void
2097 init_vn_nary_op_from_op (vn_nary_op_t vno, tree op)
2098 {
2099   unsigned i;
2100
2101   vno->opcode = TREE_CODE (op);
2102   vno->length = TREE_CODE_LENGTH (TREE_CODE (op));
2103   vno->type = TREE_TYPE (op);
2104   for (i = 0; i < vno->length; ++i)
2105     vno->op[i] = TREE_OPERAND (op, i);
2106 }
2107
2108 /* Return the number of operands for a vn_nary ops structure from STMT.  */
2109
2110 static unsigned int
2111 vn_nary_length_from_stmt (gimple stmt)
2112 {
2113   switch (gimple_assign_rhs_code (stmt))
2114     {
2115     case REALPART_EXPR:
2116     case IMAGPART_EXPR:
2117     case VIEW_CONVERT_EXPR:
2118       return 1;
2119
2120     case CONSTRUCTOR:
2121       return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
2122
2123     default:
2124       return gimple_num_ops (stmt) - 1;
2125     }
2126 }
2127
2128 /* Initialize VNO from STMT.  */
2129
2130 static void
2131 init_vn_nary_op_from_stmt (vn_nary_op_t vno, gimple stmt)
2132 {
2133   unsigned i;
2134
2135   vno->opcode = gimple_assign_rhs_code (stmt);
2136   vno->type = gimple_expr_type (stmt);
2137   switch (vno->opcode)
2138     {
2139     case REALPART_EXPR:
2140     case IMAGPART_EXPR:
2141     case VIEW_CONVERT_EXPR:
2142       vno->length = 1;
2143       vno->op[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
2144       break;
2145
2146     case CONSTRUCTOR:
2147       vno->length = CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
2148       for (i = 0; i < vno->length; ++i)
2149         vno->op[i] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt), i)->value;
2150       break;
2151
2152     default:
2153       vno->length = gimple_num_ops (stmt) - 1;
2154       for (i = 0; i < vno->length; ++i)
2155         vno->op[i] = gimple_op (stmt, i + 1);
2156     }
2157 }
2158
2159 /* Compute the hashcode for VNO and look for it in the hash table;
2160    return the resulting value number if it exists in the hash table.
2161    Return NULL_TREE if it does not exist in the hash table or if the
2162    result field of the operation is NULL.  VNRESULT will contain the
2163    vn_nary_op_t from the hashtable if it exists.  */
2164
2165 static tree
2166 vn_nary_op_lookup_1 (vn_nary_op_t vno, vn_nary_op_t *vnresult)
2167 {
2168   void **slot;
2169
2170   if (vnresult)
2171     *vnresult = NULL;
2172
2173   vno->hashcode = vn_nary_op_compute_hash (vno);
2174   slot = htab_find_slot_with_hash (current_info->nary, vno, vno->hashcode,
2175                                    NO_INSERT);
2176   if (!slot && current_info == optimistic_info)
2177     slot = htab_find_slot_with_hash (valid_info->nary, vno, vno->hashcode,
2178                                      NO_INSERT);
2179   if (!slot)
2180     return NULL_TREE;
2181   if (vnresult)
2182     *vnresult = (vn_nary_op_t)*slot;
2183   return ((vn_nary_op_t)*slot)->result;
2184 }
2185
2186 /* Lookup a n-ary operation by its pieces and return the resulting value
2187    number if it exists in the hash table.  Return NULL_TREE if it does
2188    not exist in the hash table or if the result field of the operation
2189    is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2190    if it exists.  */
2191
2192 tree
2193 vn_nary_op_lookup_pieces (unsigned int length, enum tree_code code,
2194                           tree type, tree *ops, vn_nary_op_t *vnresult)
2195 {
2196   vn_nary_op_t vno1 = XALLOCAVAR (struct vn_nary_op_s,
2197                                   sizeof_vn_nary_op (length));
2198   init_vn_nary_op_from_pieces (vno1, length, code, type, ops);
2199   return vn_nary_op_lookup_1 (vno1, vnresult);
2200 }
2201
2202 /* Lookup OP in the current hash table, and return the resulting value
2203    number if it exists in the hash table.  Return NULL_TREE if it does
2204    not exist in the hash table or if the result field of the operation
2205    is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2206    if it exists.  */
2207
2208 tree
2209 vn_nary_op_lookup (tree op, vn_nary_op_t *vnresult)
2210 {
2211   vn_nary_op_t vno1
2212     = XALLOCAVAR (struct vn_nary_op_s,
2213                   sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op))));
2214   init_vn_nary_op_from_op (vno1, op);
2215   return vn_nary_op_lookup_1 (vno1, vnresult);
2216 }
2217
2218 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2219    value number if it exists in the hash table.  Return NULL_TREE if
2220    it does not exist in the hash table.  VNRESULT will contain the
2221    vn_nary_op_t from the hashtable if it exists.  */
2222
2223 tree
2224 vn_nary_op_lookup_stmt (gimple stmt, vn_nary_op_t *vnresult)
2225 {
2226   vn_nary_op_t vno1
2227     = XALLOCAVAR (struct vn_nary_op_s,
2228                   sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt)));
2229   init_vn_nary_op_from_stmt (vno1, stmt);
2230   return vn_nary_op_lookup_1 (vno1, vnresult);
2231 }
2232
2233 /* Allocate a vn_nary_op_t with LENGTH operands on STACK.  */
2234
2235 static vn_nary_op_t
2236 alloc_vn_nary_op_noinit (unsigned int length, struct obstack *stack)
2237 {
2238   return (vn_nary_op_t) obstack_alloc (stack, sizeof_vn_nary_op (length));
2239 }
2240
2241 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
2242    obstack.  */
2243
2244 static vn_nary_op_t
2245 alloc_vn_nary_op (unsigned int length, tree result, unsigned int value_id)
2246 {
2247   vn_nary_op_t vno1 = alloc_vn_nary_op_noinit (length,
2248                                                &current_info->nary_obstack);
2249
2250   vno1->value_id = value_id;
2251   vno1->length = length;
2252   vno1->result = result;
2253
2254   return vno1;
2255 }
2256
2257 /* Insert VNO into TABLE.  If COMPUTE_HASH is true, then compute
2258    VNO->HASHCODE first.  */
2259
2260 static vn_nary_op_t
2261 vn_nary_op_insert_into (vn_nary_op_t vno, htab_t table, bool compute_hash)
2262 {
2263   void **slot;
2264
2265   if (compute_hash)
2266     vno->hashcode = vn_nary_op_compute_hash (vno);
2267
2268   slot = htab_find_slot_with_hash (table, vno, vno->hashcode, INSERT);
2269   gcc_assert (!*slot);
2270
2271   *slot = vno;
2272   return vno;
2273 }
2274
2275 /* Insert a n-ary operation into the current hash table using it's
2276    pieces.  Return the vn_nary_op_t structure we created and put in
2277    the hashtable.  */
2278
2279 vn_nary_op_t
2280 vn_nary_op_insert_pieces (unsigned int length, enum tree_code code,
2281                           tree type, tree *ops,
2282                           tree result, unsigned int value_id)
2283 {
2284   vn_nary_op_t vno1 = alloc_vn_nary_op (length, result, value_id);
2285   init_vn_nary_op_from_pieces (vno1, length, code, type, ops);
2286   return vn_nary_op_insert_into (vno1, current_info->nary, true);
2287 }
2288
2289 /* Insert OP into the current hash table with a value number of
2290    RESULT.  Return the vn_nary_op_t structure we created and put in
2291    the hashtable.  */
2292
2293 vn_nary_op_t
2294 vn_nary_op_insert (tree op, tree result)
2295 {
2296   unsigned length = TREE_CODE_LENGTH (TREE_CODE (op));
2297   vn_nary_op_t vno1;
2298
2299   vno1 = alloc_vn_nary_op (length, result, VN_INFO (result)->value_id);
2300   init_vn_nary_op_from_op (vno1, op);
2301   return vn_nary_op_insert_into (vno1, current_info->nary, true);
2302 }
2303
2304 /* Insert the rhs of STMT into the current hash table with a value number of
2305    RESULT.  */
2306
2307 vn_nary_op_t
2308 vn_nary_op_insert_stmt (gimple stmt, tree result)
2309 {
2310   vn_nary_op_t vno1
2311     = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt),
2312                         result, VN_INFO (result)->value_id);
2313   init_vn_nary_op_from_stmt (vno1, stmt);
2314   return vn_nary_op_insert_into (vno1, current_info->nary, true);
2315 }
2316
2317 /* Compute a hashcode for PHI operation VP1 and return it.  */
2318
2319 static inline hashval_t
2320 vn_phi_compute_hash (vn_phi_t vp1)
2321 {
2322   hashval_t result;
2323   int i;
2324   tree phi1op;
2325   tree type;
2326
2327   result = vp1->block->index;
2328
2329   /* If all PHI arguments are constants we need to distinguish
2330      the PHI node via its type.  */
2331   type = TREE_TYPE (VEC_index (tree, vp1->phiargs, 0));
2332   result += (INTEGRAL_TYPE_P (type)
2333              + (INTEGRAL_TYPE_P (type)
2334                 ? TYPE_PRECISION (type) + TYPE_UNSIGNED (type) : 0));
2335
2336   FOR_EACH_VEC_ELT (tree, vp1->phiargs, i, phi1op)
2337     {
2338       if (phi1op == VN_TOP)
2339         continue;
2340       result = iterative_hash_expr (phi1op, result);
2341     }
2342
2343   return result;
2344 }
2345
2346 /* Return the computed hashcode for phi operation P1.  */
2347
2348 static hashval_t
2349 vn_phi_hash (const void *p1)
2350 {
2351   const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
2352   return vp1->hashcode;
2353 }
2354
2355 /* Compare two phi entries for equality, ignoring VN_TOP arguments.  */
2356
2357 static int
2358 vn_phi_eq (const void *p1, const void *p2)
2359 {
2360   const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
2361   const_vn_phi_t const vp2 = (const_vn_phi_t) p2;
2362
2363   if (vp1->hashcode != vp2->hashcode)
2364     return false;
2365
2366   if (vp1->block == vp2->block)
2367     {
2368       int i;
2369       tree phi1op;
2370
2371       /* If the PHI nodes do not have compatible types
2372          they are not the same.  */
2373       if (!types_compatible_p (TREE_TYPE (VEC_index (tree, vp1->phiargs, 0)),
2374                                TREE_TYPE (VEC_index (tree, vp2->phiargs, 0))))
2375         return false;
2376
2377       /* Any phi in the same block will have it's arguments in the
2378          same edge order, because of how we store phi nodes.  */
2379       FOR_EACH_VEC_ELT (tree, vp1->phiargs, i, phi1op)
2380         {
2381           tree phi2op = VEC_index (tree, vp2->phiargs, i);
2382           if (phi1op == VN_TOP || phi2op == VN_TOP)
2383             continue;
2384           if (!expressions_equal_p (phi1op, phi2op))
2385             return false;
2386         }
2387       return true;
2388     }
2389   return false;
2390 }
2391
2392 static VEC(tree, heap) *shared_lookup_phiargs;
2393
2394 /* Lookup PHI in the current hash table, and return the resulting
2395    value number if it exists in the hash table.  Return NULL_TREE if
2396    it does not exist in the hash table. */
2397
2398 static tree
2399 vn_phi_lookup (gimple phi)
2400 {
2401   void **slot;
2402   struct vn_phi_s vp1;
2403   unsigned i;
2404
2405   VEC_truncate (tree, shared_lookup_phiargs, 0);
2406
2407   /* Canonicalize the SSA_NAME's to their value number.  */
2408   for (i = 0; i < gimple_phi_num_args (phi); i++)
2409     {
2410       tree def = PHI_ARG_DEF (phi, i);
2411       def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
2412       VEC_safe_push (tree, heap, shared_lookup_phiargs, def);
2413     }
2414   vp1.phiargs = shared_lookup_phiargs;
2415   vp1.block = gimple_bb (phi);
2416   vp1.hashcode = vn_phi_compute_hash (&vp1);
2417   slot = htab_find_slot_with_hash (current_info->phis, &vp1, vp1.hashcode,
2418                                    NO_INSERT);
2419   if (!slot && current_info == optimistic_info)
2420     slot = htab_find_slot_with_hash (valid_info->phis, &vp1, vp1.hashcode,
2421                                      NO_INSERT);
2422   if (!slot)
2423     return NULL_TREE;
2424   return ((vn_phi_t)*slot)->result;
2425 }
2426
2427 /* Insert PHI into the current hash table with a value number of
2428    RESULT.  */
2429
2430 static vn_phi_t
2431 vn_phi_insert (gimple phi, tree result)
2432 {
2433   void **slot;
2434   vn_phi_t vp1 = (vn_phi_t) pool_alloc (current_info->phis_pool);
2435   unsigned i;
2436   VEC (tree, heap) *args = NULL;
2437
2438   /* Canonicalize the SSA_NAME's to their value number.  */
2439   for (i = 0; i < gimple_phi_num_args (phi); i++)
2440     {
2441       tree def = PHI_ARG_DEF (phi, i);
2442       def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
2443       VEC_safe_push (tree, heap, args, def);
2444     }
2445   vp1->value_id = VN_INFO (result)->value_id;
2446   vp1->phiargs = args;
2447   vp1->block = gimple_bb (phi);
2448   vp1->result = result;
2449   vp1->hashcode = vn_phi_compute_hash (vp1);
2450
2451   slot = htab_find_slot_with_hash (current_info->phis, vp1, vp1->hashcode,
2452                                    INSERT);
2453
2454   /* Because we iterate over phi operations more than once, it's
2455      possible the slot might already exist here, hence no assert.*/
2456   *slot = vp1;
2457   return vp1;
2458 }
2459
2460
2461 /* Print set of components in strongly connected component SCC to OUT. */
2462
2463 static void
2464 print_scc (FILE *out, VEC (tree, heap) *scc)
2465 {
2466   tree var;
2467   unsigned int i;
2468
2469   fprintf (out, "SCC consists of:");
2470   FOR_EACH_VEC_ELT (tree, scc, i, var)
2471     {
2472       fprintf (out, " ");
2473       print_generic_expr (out, var, 0);
2474     }
2475   fprintf (out, "\n");
2476 }
2477
2478 /* Set the value number of FROM to TO, return true if it has changed
2479    as a result.  */
2480
2481 static inline bool
2482 set_ssa_val_to (tree from, tree to)
2483 {
2484   tree currval = SSA_VAL (from);
2485
2486   if (from != to)
2487     {
2488       if (currval == from)
2489         {
2490           if (dump_file && (dump_flags & TDF_DETAILS))
2491             {
2492               fprintf (dump_file, "Not changing value number of ");
2493               print_generic_expr (dump_file, from, 0);
2494               fprintf (dump_file, " from VARYING to ");
2495               print_generic_expr (dump_file, to, 0);
2496               fprintf (dump_file, "\n");
2497             }
2498           return false;
2499         }
2500       else if (TREE_CODE (to) == SSA_NAME
2501                && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to))
2502         to = from;
2503     }
2504
2505   /* The only thing we allow as value numbers are VN_TOP, ssa_names
2506      and invariants.  So assert that here.  */
2507   gcc_assert (to != NULL_TREE
2508               && (to == VN_TOP
2509                   || TREE_CODE (to) == SSA_NAME
2510                   || is_gimple_min_invariant (to)));
2511
2512   if (dump_file && (dump_flags & TDF_DETAILS))
2513     {
2514       fprintf (dump_file, "Setting value number of ");
2515       print_generic_expr (dump_file, from, 0);
2516       fprintf (dump_file, " to ");
2517       print_generic_expr (dump_file, to, 0);
2518     }
2519
2520   if (currval != to  && !operand_equal_p (currval, to, OEP_PURE_SAME))
2521     {
2522       VN_INFO (from)->valnum = to;
2523       if (dump_file && (dump_flags & TDF_DETAILS))
2524         fprintf (dump_file, " (changed)\n");
2525       return true;
2526     }
2527   if (dump_file && (dump_flags & TDF_DETAILS))
2528     fprintf (dump_file, "\n");
2529   return false;
2530 }
2531
2532 /* Set all definitions in STMT to value number to themselves.
2533    Return true if a value number changed. */
2534
2535 static bool
2536 defs_to_varying (gimple stmt)
2537 {
2538   bool changed = false;
2539   ssa_op_iter iter;
2540   def_operand_p defp;
2541
2542   FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
2543     {
2544       tree def = DEF_FROM_PTR (defp);
2545
2546       VN_INFO (def)->use_processed = true;
2547       changed |= set_ssa_val_to (def, def);
2548     }
2549   return changed;
2550 }
2551
2552 static bool expr_has_constants (tree expr);
2553 static tree valueize_expr (tree expr);
2554
2555 /* Visit a copy between LHS and RHS, return true if the value number
2556    changed.  */
2557
2558 static bool
2559 visit_copy (tree lhs, tree rhs)
2560 {
2561   /* Follow chains of copies to their destination.  */
2562   while (TREE_CODE (rhs) == SSA_NAME
2563          && SSA_VAL (rhs) != rhs)
2564     rhs = SSA_VAL (rhs);
2565
2566   /* The copy may have a more interesting constant filled expression
2567      (we don't, since we know our RHS is just an SSA name).  */
2568   if (TREE_CODE (rhs) == SSA_NAME)
2569     {
2570       VN_INFO (lhs)->has_constants = VN_INFO (rhs)->has_constants;
2571       VN_INFO (lhs)->expr = VN_INFO (rhs)->expr;
2572     }
2573
2574   return set_ssa_val_to (lhs, rhs);
2575 }
2576
2577 /* Visit a nary operator RHS, value number it, and return true if the
2578    value number of LHS has changed as a result.  */
2579
2580 static bool
2581 visit_nary_op (tree lhs, gimple stmt)
2582 {
2583   bool changed = false;
2584   tree result = vn_nary_op_lookup_stmt (stmt, NULL);
2585
2586   if (result)
2587     changed = set_ssa_val_to (lhs, result);
2588   else
2589     {
2590       changed = set_ssa_val_to (lhs, lhs);
2591       vn_nary_op_insert_stmt (stmt, lhs);
2592     }
2593
2594   return changed;
2595 }
2596
2597 /* Visit a call STMT storing into LHS.  Return true if the value number
2598    of the LHS has changed as a result.  */
2599
2600 static bool
2601 visit_reference_op_call (tree lhs, gimple stmt)
2602 {
2603   bool changed = false;
2604   struct vn_reference_s vr1;
2605   tree result;
2606   tree vuse = gimple_vuse (stmt);
2607
2608   vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
2609   vr1.operands = valueize_shared_reference_ops_from_call (stmt);
2610   vr1.type = gimple_expr_type (stmt);
2611   vr1.set = 0;
2612   vr1.hashcode = vn_reference_compute_hash (&vr1);
2613   result = vn_reference_lookup_1 (&vr1, NULL);
2614   if (result)
2615     {
2616       changed = set_ssa_val_to (lhs, result);
2617       if (TREE_CODE (result) == SSA_NAME
2618           && VN_INFO (result)->has_constants)
2619         VN_INFO (lhs)->has_constants = true;
2620     }
2621   else
2622     {
2623       void **slot;
2624       vn_reference_t vr2;
2625       changed = set_ssa_val_to (lhs, lhs);
2626       vr2 = (vn_reference_t) pool_alloc (current_info->references_pool);
2627       vr2->vuse = vr1.vuse;
2628       vr2->operands = valueize_refs (create_reference_ops_from_call (stmt));
2629       vr2->type = vr1.type;
2630       vr2->set = vr1.set;
2631       vr2->hashcode = vr1.hashcode;
2632       vr2->result = lhs;
2633       slot = htab_find_slot_with_hash (current_info->references,
2634                                        vr2, vr2->hashcode, INSERT);
2635       if (*slot)
2636         free_reference (*slot);
2637       *slot = vr2;
2638     }
2639
2640   return changed;
2641 }
2642
2643 /* Visit a load from a reference operator RHS, part of STMT, value number it,
2644    and return true if the value number of the LHS has changed as a result.  */
2645
2646 static bool
2647 visit_reference_op_load (tree lhs, tree op, gimple stmt)
2648 {
2649   bool changed = false;
2650   tree last_vuse;
2651   tree result;
2652
2653   last_vuse = gimple_vuse (stmt);
2654   last_vuse_ptr = &last_vuse;
2655   result = vn_reference_lookup (op, gimple_vuse (stmt),
2656                                 default_vn_walk_kind, NULL);
2657   last_vuse_ptr = NULL;
2658
2659   /* If we have a VCE, try looking up its operand as it might be stored in
2660      a different type.  */
2661   if (!result && TREE_CODE (op) == VIEW_CONVERT_EXPR)
2662     result = vn_reference_lookup (TREE_OPERAND (op, 0), gimple_vuse (stmt),
2663                                   default_vn_walk_kind, NULL);
2664
2665   /* We handle type-punning through unions by value-numbering based
2666      on offset and size of the access.  Be prepared to handle a
2667      type-mismatch here via creating a VIEW_CONVERT_EXPR.  */
2668   if (result
2669       && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (op)))
2670     {
2671       /* We will be setting the value number of lhs to the value number
2672          of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
2673          So first simplify and lookup this expression to see if it
2674          is already available.  */
2675       tree val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (op), result);
2676       if ((CONVERT_EXPR_P (val)
2677            || TREE_CODE (val) == VIEW_CONVERT_EXPR)
2678           && TREE_CODE (TREE_OPERAND (val, 0)) == SSA_NAME)
2679         {
2680           tree tem = valueize_expr (vn_get_expr_for (TREE_OPERAND (val, 0)));
2681           if ((CONVERT_EXPR_P (tem)
2682                || TREE_CODE (tem) == VIEW_CONVERT_EXPR)
2683               && (tem = fold_unary_ignore_overflow (TREE_CODE (val),
2684                                                     TREE_TYPE (val), tem)))
2685             val = tem;
2686         }
2687       result = val;
2688       if (!is_gimple_min_invariant (val)
2689           && TREE_CODE (val) != SSA_NAME)
2690         result = vn_nary_op_lookup (val, NULL);
2691       /* If the expression is not yet available, value-number lhs to
2692          a new SSA_NAME we create.  */
2693       if (!result)
2694         {
2695           result = make_ssa_name (SSA_NAME_VAR (lhs), gimple_build_nop ());
2696           /* Initialize value-number information properly.  */
2697           VN_INFO_GET (result)->valnum = result;
2698           VN_INFO (result)->value_id = get_next_value_id ();
2699           VN_INFO (result)->expr = val;
2700           VN_INFO (result)->has_constants = expr_has_constants (val);
2701           VN_INFO (result)->needs_insertion = true;
2702           /* As all "inserted" statements are singleton SCCs, insert
2703              to the valid table.  This is strictly needed to
2704              avoid re-generating new value SSA_NAMEs for the same
2705              expression during SCC iteration over and over (the
2706              optimistic table gets cleared after each iteration).
2707              We do not need to insert into the optimistic table, as
2708              lookups there will fall back to the valid table.  */
2709           if (current_info == optimistic_info)
2710             {
2711               current_info = valid_info;
2712               vn_nary_op_insert (val, result);
2713               current_info = optimistic_info;
2714             }
2715           else
2716             vn_nary_op_insert (val, result);
2717           if (dump_file && (dump_flags & TDF_DETAILS))
2718             {
2719               fprintf (dump_file, "Inserting name ");
2720               print_generic_expr (dump_file, result, 0);
2721               fprintf (dump_file, " for expression ");
2722               print_generic_expr (dump_file, val, 0);
2723               fprintf (dump_file, "\n");
2724             }
2725         }
2726     }
2727
2728   if (result)
2729     {
2730       changed = set_ssa_val_to (lhs, result);
2731       if (TREE_CODE (result) == SSA_NAME
2732           && VN_INFO (result)->has_constants)
2733         {
2734           VN_INFO (lhs)->expr = VN_INFO (result)->expr;
2735           VN_INFO (lhs)->has_constants = true;
2736         }
2737     }
2738   else
2739     {
2740       changed = set_ssa_val_to (lhs, lhs);
2741       vn_reference_insert (op, lhs, last_vuse);
2742     }
2743
2744   return changed;
2745 }
2746
2747
2748 /* Visit a store to a reference operator LHS, part of STMT, value number it,
2749    and return true if the value number of the LHS has changed as a result.  */
2750
2751 static bool
2752 visit_reference_op_store (tree lhs, tree op, gimple stmt)
2753 {
2754   bool changed = false;
2755   tree result;
2756   bool resultsame = false;
2757
2758   /* First we want to lookup using the *vuses* from the store and see
2759      if there the last store to this location with the same address
2760      had the same value.
2761
2762      The vuses represent the memory state before the store.  If the
2763      memory state, address, and value of the store is the same as the
2764      last store to this location, then this store will produce the
2765      same memory state as that store.
2766
2767      In this case the vdef versions for this store are value numbered to those
2768      vuse versions, since they represent the same memory state after
2769      this store.
2770
2771      Otherwise, the vdefs for the store are used when inserting into
2772      the table, since the store generates a new memory state.  */
2773
2774   result = vn_reference_lookup (lhs, gimple_vuse (stmt), VN_NOWALK, NULL);
2775
2776   if (result)
2777     {
2778       if (TREE_CODE (result) == SSA_NAME)
2779         result = SSA_VAL (result);
2780       if (TREE_CODE (op) == SSA_NAME)
2781         op = SSA_VAL (op);
2782       resultsame = expressions_equal_p (result, op);
2783     }
2784
2785   if (!result || !resultsame)
2786     {
2787       tree vdef;
2788
2789       if (dump_file && (dump_flags & TDF_DETAILS))
2790         {
2791           fprintf (dump_file, "No store match\n");
2792           fprintf (dump_file, "Value numbering store ");
2793           print_generic_expr (dump_file, lhs, 0);
2794           fprintf (dump_file, " to ");
2795           print_generic_expr (dump_file, op, 0);
2796           fprintf (dump_file, "\n");
2797         }
2798       /* Have to set value numbers before insert, since insert is
2799          going to valueize the references in-place.  */
2800       if ((vdef = gimple_vdef (stmt)))
2801         {
2802           VN_INFO (vdef)->use_processed = true;
2803           changed |= set_ssa_val_to (vdef, vdef);
2804         }
2805
2806       /* Do not insert structure copies into the tables.  */
2807       if (is_gimple_min_invariant (op)
2808           || is_gimple_reg (op))
2809         vn_reference_insert (lhs, op, vdef);
2810     }
2811   else
2812     {
2813       /* We had a match, so value number the vdef to have the value
2814          number of the vuse it came from.  */
2815       tree def, use;
2816
2817       if (dump_file && (dump_flags & TDF_DETAILS))
2818         fprintf (dump_file, "Store matched earlier value,"
2819                  "value numbering store vdefs to matching vuses.\n");
2820
2821       def = gimple_vdef (stmt);
2822       use = gimple_vuse (stmt);
2823
2824       VN_INFO (def)->use_processed = true;
2825       changed |= set_ssa_val_to (def, SSA_VAL (use));
2826     }
2827
2828   return changed;
2829 }
2830
2831 /* Visit and value number PHI, return true if the value number
2832    changed.  */
2833
2834 static bool
2835 visit_phi (gimple phi)
2836 {
2837   bool changed = false;
2838   tree result;
2839   tree sameval = VN_TOP;
2840   bool allsame = true;
2841   unsigned i;
2842
2843   /* TODO: We could check for this in init_sccvn, and replace this
2844      with a gcc_assert.  */
2845   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
2846     return set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
2847
2848   /* See if all non-TOP arguments have the same value.  TOP is
2849      equivalent to everything, so we can ignore it.  */
2850   for (i = 0; i < gimple_phi_num_args (phi); i++)
2851     {
2852       tree def = PHI_ARG_DEF (phi, i);
2853
2854       if (TREE_CODE (def) == SSA_NAME)
2855         def = SSA_VAL (def);
2856       if (def == VN_TOP)
2857         continue;
2858       if (sameval == VN_TOP)
2859         {
2860           sameval = def;
2861         }
2862       else
2863         {
2864           if (!expressions_equal_p (def, sameval))
2865             {
2866               allsame = false;
2867               break;
2868             }
2869         }
2870     }
2871
2872   /* If all value numbered to the same value, the phi node has that
2873      value.  */
2874   if (allsame)
2875     {
2876       if (is_gimple_min_invariant (sameval))
2877         {
2878           VN_INFO (PHI_RESULT (phi))->has_constants = true;
2879           VN_INFO (PHI_RESULT (phi))->expr = sameval;
2880         }
2881       else
2882         {
2883           VN_INFO (PHI_RESULT (phi))->has_constants = false;
2884           VN_INFO (PHI_RESULT (phi))->expr = sameval;
2885         }
2886
2887       if (TREE_CODE (sameval) == SSA_NAME)
2888         return visit_copy (PHI_RESULT (phi), sameval);
2889
2890       return set_ssa_val_to (PHI_RESULT (phi), sameval);
2891     }
2892
2893   /* Otherwise, see if it is equivalent to a phi node in this block.  */
2894   result = vn_phi_lookup (phi);
2895   if (result)
2896     {
2897       if (TREE_CODE (result) == SSA_NAME)
2898         changed = visit_copy (PHI_RESULT (phi), result);
2899       else
2900         changed = set_ssa_val_to (PHI_RESULT (phi), result);
2901     }
2902   else
2903     {
2904       vn_phi_insert (phi, PHI_RESULT (phi));
2905       VN_INFO (PHI_RESULT (phi))->has_constants = false;
2906       VN_INFO (PHI_RESULT (phi))->expr = PHI_RESULT (phi);
2907       changed = set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
2908     }
2909
2910   return changed;
2911 }
2912
2913 /* Return true if EXPR contains constants.  */
2914
2915 static bool
2916 expr_has_constants (tree expr)
2917 {
2918   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
2919     {
2920     case tcc_unary:
2921       return is_gimple_min_invariant (TREE_OPERAND (expr, 0));
2922
2923     case tcc_binary:
2924       return is_gimple_min_invariant (TREE_OPERAND (expr, 0))
2925         || is_gimple_min_invariant (TREE_OPERAND (expr, 1));
2926       /* Constants inside reference ops are rarely interesting, but
2927          it can take a lot of looking to find them.  */
2928     case tcc_reference:
2929     case tcc_declaration:
2930       return false;
2931     default:
2932       return is_gimple_min_invariant (expr);
2933     }
2934   return false;
2935 }
2936
2937 /* Return true if STMT contains constants.  */
2938
2939 static bool
2940 stmt_has_constants (gimple stmt)
2941 {
2942   if (gimple_code (stmt) != GIMPLE_ASSIGN)
2943     return false;
2944
2945   switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
2946     {
2947     case GIMPLE_UNARY_RHS:
2948       return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
2949
2950     case GIMPLE_BINARY_RHS:
2951       return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))
2952               || is_gimple_min_invariant (gimple_assign_rhs2 (stmt)));
2953     case GIMPLE_TERNARY_RHS:
2954       return (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))
2955               || is_gimple_min_invariant (gimple_assign_rhs2 (stmt))
2956               || is_gimple_min_invariant (gimple_assign_rhs3 (stmt)));
2957     case GIMPLE_SINGLE_RHS:
2958       /* Constants inside reference ops are rarely interesting, but
2959          it can take a lot of looking to find them.  */
2960       return is_gimple_min_invariant (gimple_assign_rhs1 (stmt));
2961     default:
2962       gcc_unreachable ();
2963     }
2964   return false;
2965 }
2966
2967 /* Replace SSA_NAMES in expr with their value numbers, and return the
2968    result.
2969    This is performed in place. */
2970
2971 static tree
2972 valueize_expr (tree expr)
2973 {
2974   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
2975     {
2976     case tcc_binary:
2977       TREE_OPERAND (expr, 1) = vn_valueize (TREE_OPERAND (expr, 1));
2978       /* Fallthru.  */
2979     case tcc_unary:
2980       TREE_OPERAND (expr, 0) = vn_valueize (TREE_OPERAND (expr, 0));
2981       break;
2982     default:;
2983     }
2984   return expr;
2985 }
2986
2987 /* Simplify the binary expression RHS, and return the result if
2988    simplified. */
2989
2990 static tree
2991 simplify_binary_expression (gimple stmt)
2992 {
2993   tree result = NULL_TREE;
2994   tree op0 = gimple_assign_rhs1 (stmt);
2995   tree op1 = gimple_assign_rhs2 (stmt);
2996   enum tree_code code = gimple_assign_rhs_code (stmt);
2997
2998   /* This will not catch every single case we could combine, but will
2999      catch those with constants.  The goal here is to simultaneously
3000      combine constants between expressions, but avoid infinite
3001      expansion of expressions during simplification.  */
3002   if (TREE_CODE (op0) == SSA_NAME)
3003     {
3004       if (VN_INFO (op0)->has_constants
3005           || TREE_CODE_CLASS (code) == tcc_comparison
3006           || code == COMPLEX_EXPR)
3007         op0 = valueize_expr (vn_get_expr_for (op0));
3008       else
3009         op0 = vn_valueize (op0);
3010     }
3011
3012   if (TREE_CODE (op1) == SSA_NAME)
3013     {
3014       if (VN_INFO (op1)->has_constants
3015           || code == COMPLEX_EXPR)
3016         op1 = valueize_expr (vn_get_expr_for (op1));
3017       else
3018         op1 = vn_valueize (op1);
3019     }
3020
3021   /* Pointer plus constant can be represented as invariant address.
3022      Do so to allow further propatation, see also tree forwprop.  */
3023   if (code == POINTER_PLUS_EXPR
3024       && host_integerp (op1, 1)
3025       && TREE_CODE (op0) == ADDR_EXPR
3026       && is_gimple_min_invariant (op0))
3027     return build_invariant_address (TREE_TYPE (op0),
3028                                     TREE_OPERAND (op0, 0),
3029                                     TREE_INT_CST_LOW (op1));
3030
3031   /* Avoid folding if nothing changed.  */
3032   if (op0 == gimple_assign_rhs1 (stmt)
3033       && op1 == gimple_assign_rhs2 (stmt))
3034     return NULL_TREE;
3035
3036   fold_defer_overflow_warnings ();
3037
3038   result = fold_binary (code, gimple_expr_type (stmt), op0, op1);
3039   if (result)
3040     STRIP_USELESS_TYPE_CONVERSION (result);
3041
3042   fold_undefer_overflow_warnings (result && valid_gimple_rhs_p (result),
3043                                   stmt, 0);
3044
3045   /* Make sure result is not a complex expression consisting
3046      of operators of operators (IE (a + b) + (a + c))
3047      Otherwise, we will end up with unbounded expressions if
3048      fold does anything at all.  */
3049   if (result && valid_gimple_rhs_p (result))
3050     return result;
3051
3052   return NULL_TREE;
3053 }
3054
3055 /* Simplify the unary expression RHS, and return the result if
3056    simplified. */
3057
3058 static tree
3059 simplify_unary_expression (gimple stmt)
3060 {
3061   tree result = NULL_TREE;
3062   tree orig_op0, op0 = gimple_assign_rhs1 (stmt);
3063   enum tree_code code = gimple_assign_rhs_code (stmt);
3064
3065   /* We handle some tcc_reference codes here that are all
3066      GIMPLE_ASSIGN_SINGLE codes.  */
3067   if (code == REALPART_EXPR
3068       || code == IMAGPART_EXPR
3069       || code == VIEW_CONVERT_EXPR
3070       || code == BIT_FIELD_REF)
3071     op0 = TREE_OPERAND (op0, 0);
3072
3073   if (TREE_CODE (op0) != SSA_NAME)
3074     return NULL_TREE;
3075
3076   orig_op0 = op0;
3077   if (VN_INFO (op0)->has_constants)
3078     op0 = valueize_expr (vn_get_expr_for (op0));
3079   else if (CONVERT_EXPR_CODE_P (code)
3080            || code == REALPART_EXPR
3081            || code == IMAGPART_EXPR
3082            || code == VIEW_CONVERT_EXPR
3083            || code == BIT_FIELD_REF)
3084     {
3085       /* We want to do tree-combining on conversion-like expressions.
3086          Make sure we feed only SSA_NAMEs or constants to fold though.  */
3087       tree tem = valueize_expr (vn_get_expr_for (op0));
3088       if (UNARY_CLASS_P (tem)
3089           || BINARY_CLASS_P (tem)
3090           || TREE_CODE (tem) == VIEW_CONVERT_EXPR
3091           || TREE_CODE (tem) == SSA_NAME
3092           || TREE_CODE (tem) == CONSTRUCTOR
3093           || is_gimple_min_invariant (tem))
3094         op0 = tem;
3095     }
3096
3097   /* Avoid folding if nothing changed, but remember the expression.  */
3098   if (op0 == orig_op0)
3099     return NULL_TREE;
3100
3101   if (code == BIT_FIELD_REF)
3102     {
3103       tree rhs = gimple_assign_rhs1 (stmt);
3104       result = fold_ternary (BIT_FIELD_REF, TREE_TYPE (rhs),
3105                              op0, TREE_OPERAND (rhs, 1), TREE_OPERAND (rhs, 2));
3106     }
3107   else
3108     result = fold_unary_ignore_overflow (code, gimple_expr_type (stmt), op0);
3109   if (result)
3110     {
3111       STRIP_USELESS_TYPE_CONVERSION (result);
3112       if (valid_gimple_rhs_p (result))
3113         return result;
3114     }
3115
3116   return NULL_TREE;
3117 }
3118
3119 /* Try to simplify RHS using equivalences and constant folding.  */
3120
3121 static tree
3122 try_to_simplify (gimple stmt)
3123 {
3124   enum tree_code code = gimple_assign_rhs_code (stmt);
3125   tree tem;
3126
3127   /* For stores we can end up simplifying a SSA_NAME rhs.  Just return
3128      in this case, there is no point in doing extra work.  */
3129   if (code == SSA_NAME)
3130     return NULL_TREE;
3131
3132   /* First try constant folding based on our current lattice.  */
3133   tem = gimple_fold_stmt_to_constant_1 (stmt, vn_valueize);
3134   if (tem
3135       && (TREE_CODE (tem) == SSA_NAME
3136           || is_gimple_min_invariant (tem)))
3137     return tem;
3138
3139   /* If that didn't work try combining multiple statements.  */
3140   switch (TREE_CODE_CLASS (code))
3141     {
3142     case tcc_reference:
3143       /* Fallthrough for some unary codes that can operate on registers.  */
3144       if (!(code == REALPART_EXPR
3145             || code == IMAGPART_EXPR
3146             || code == VIEW_CONVERT_EXPR
3147             || code == BIT_FIELD_REF))
3148         break;
3149       /* We could do a little more with unary ops, if they expand
3150          into binary ops, but it's debatable whether it is worth it. */
3151     case tcc_unary:
3152       return simplify_unary_expression (stmt);
3153
3154     case tcc_comparison:
3155     case tcc_binary:
3156       return simplify_binary_expression (stmt);
3157
3158     default:
3159       break;
3160     }
3161
3162   return NULL_TREE;
3163 }
3164
3165 /* Visit and value number USE, return true if the value number
3166    changed. */
3167
3168 static bool
3169 visit_use (tree use)
3170 {
3171   bool changed = false;
3172   gimple stmt = SSA_NAME_DEF_STMT (use);
3173
3174   VN_INFO (use)->use_processed = true;
3175
3176   gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
3177   if (dump_file && (dump_flags & TDF_DETAILS)
3178       && !SSA_NAME_IS_DEFAULT_DEF (use))
3179     {
3180       fprintf (dump_file, "Value numbering ");
3181       print_generic_expr (dump_file, use, 0);
3182       fprintf (dump_file, " stmt = ");
3183       print_gimple_stmt (dump_file, stmt, 0, 0);
3184     }
3185
3186   /* Handle uninitialized uses.  */
3187   if (SSA_NAME_IS_DEFAULT_DEF (use))
3188     changed = set_ssa_val_to (use, use);
3189   else
3190     {
3191       if (gimple_code (stmt) == GIMPLE_PHI)
3192         changed = visit_phi (stmt);
3193       else if (!gimple_has_lhs (stmt)
3194                || gimple_has_volatile_ops (stmt))
3195         changed = defs_to_varying (stmt);
3196       else if (is_gimple_assign (stmt))
3197         {
3198           enum tree_code code = gimple_assign_rhs_code (stmt);
3199           tree lhs = gimple_assign_lhs (stmt);
3200           tree rhs1 = gimple_assign_rhs1 (stmt);
3201           tree simplified;
3202
3203           /* Shortcut for copies. Simplifying copies is pointless,
3204              since we copy the expression and value they represent.  */
3205           if (code == SSA_NAME
3206               && TREE_CODE (lhs) == SSA_NAME)
3207             {
3208               changed = visit_copy (lhs, rhs1);
3209               goto done;
3210             }
3211           simplified = try_to_simplify (stmt);
3212           if (simplified)
3213             {
3214               if (dump_file && (dump_flags & TDF_DETAILS))
3215                 {
3216                   fprintf (dump_file, "RHS ");
3217                   print_gimple_expr (dump_file, stmt, 0, 0);
3218                   fprintf (dump_file, " simplified to ");
3219                   print_generic_expr (dump_file, simplified, 0);
3220                   if (TREE_CODE (lhs) == SSA_NAME)
3221                     fprintf (dump_file, " has constants %d\n",
3222                              expr_has_constants (simplified));
3223                   else
3224                     fprintf (dump_file, "\n");
3225                 }
3226             }
3227           /* Setting value numbers to constants will occasionally
3228              screw up phi congruence because constants are not
3229              uniquely associated with a single ssa name that can be
3230              looked up.  */
3231           if (simplified
3232               && is_gimple_min_invariant (simplified)
3233               && TREE_CODE (lhs) == SSA_NAME)
3234             {
3235               VN_INFO (lhs)->expr = simplified;
3236               VN_INFO (lhs)->has_constants = true;
3237               changed = set_ssa_val_to (lhs, simplified);
3238               goto done;
3239             }
3240           else if (simplified
3241                    && TREE_CODE (simplified) == SSA_NAME
3242                    && TREE_CODE (lhs) == SSA_NAME)
3243             {
3244               changed = visit_copy (lhs, simplified);
3245               goto done;
3246             }
3247           else if (simplified)
3248             {
3249               if (TREE_CODE (lhs) == SSA_NAME)
3250                 {
3251                   VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
3252                   /* We have to unshare the expression or else
3253                      valuizing may change the IL stream.  */
3254                   VN_INFO (lhs)->expr = unshare_expr (simplified);
3255                 }
3256             }
3257           else if (stmt_has_constants (stmt)
3258                    && TREE_CODE (lhs) == SSA_NAME)
3259             VN_INFO (lhs)->has_constants = true;
3260           else if (TREE_CODE (lhs) == SSA_NAME)
3261             {
3262               /* We reset expr and constantness here because we may
3263                  have been value numbering optimistically, and
3264                  iterating. They may become non-constant in this case,
3265                  even if they were optimistically constant. */
3266
3267               VN_INFO (lhs)->has_constants = false;
3268               VN_INFO (lhs)->expr = NULL_TREE;
3269             }
3270
3271           if ((TREE_CODE (lhs) == SSA_NAME
3272                /* We can substitute SSA_NAMEs that are live over
3273                   abnormal edges with their constant value.  */
3274                && !(gimple_assign_copy_p (stmt)
3275                     && is_gimple_min_invariant (rhs1))
3276                && !(simplified
3277                     && is_gimple_min_invariant (simplified))
3278                && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
3279               /* Stores or copies from SSA_NAMEs that are live over
3280                  abnormal edges are a problem.  */
3281               || (code == SSA_NAME
3282                   && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1)))
3283             changed = defs_to_varying (stmt);
3284           else if (REFERENCE_CLASS_P (lhs)
3285                    || DECL_P (lhs))
3286             changed = visit_reference_op_store (lhs, rhs1, stmt);
3287           else if (TREE_CODE (lhs) == SSA_NAME)
3288             {
3289               if ((gimple_assign_copy_p (stmt)
3290                    && is_gimple_min_invariant (rhs1))
3291                   || (simplified
3292                       && is_gimple_min_invariant (simplified)))
3293                 {
3294                   VN_INFO (lhs)->has_constants = true;
3295                   if (simplified)
3296                     changed = set_ssa_val_to (lhs, simplified);
3297                   else
3298                     changed = set_ssa_val_to (lhs, rhs1);
3299                 }
3300               else
3301                 {
3302                   switch (get_gimple_rhs_class (code))
3303                     {
3304                     case GIMPLE_UNARY_RHS:
3305                     case GIMPLE_BINARY_RHS:
3306                     case GIMPLE_TERNARY_RHS:
3307                       changed = visit_nary_op (lhs, stmt);
3308                       break;
3309                     case GIMPLE_SINGLE_RHS:
3310                       switch (TREE_CODE_CLASS (code))
3311                         {
3312                         case tcc_reference:
3313                           /* VOP-less references can go through unary case.  */
3314                           if ((code == REALPART_EXPR
3315                                || code == IMAGPART_EXPR
3316                                || code == VIEW_CONVERT_EXPR
3317                                || code == BIT_FIELD_REF)
3318                               && TREE_CODE (TREE_OPERAND (rhs1, 0)) == SSA_NAME)
3319                             {
3320                               changed = visit_nary_op (lhs, stmt);
3321                               break;
3322                             }
3323                           /* Fallthrough.  */
3324                         case tcc_declaration:
3325                           changed = visit_reference_op_load (lhs, rhs1, stmt);
3326                           break;
3327                         default:
3328                           if (code == ADDR_EXPR)
3329                             {
3330                               changed = visit_nary_op (lhs, stmt);
3331                               break;
3332                             }
3333                           else if (code == CONSTRUCTOR)
3334                             {
3335                               changed = visit_nary_op (lhs, stmt);
3336                               break;
3337                             }
3338                           changed = defs_to_varying (stmt);
3339                         }
3340                       break;
3341                     default:
3342                       changed = defs_to_varying (stmt);
3343                       break;
3344                     }
3345                 }
3346             }
3347           else
3348             changed = defs_to_varying (stmt);
3349         }
3350       else if (is_gimple_call (stmt))
3351         {
3352           tree lhs = gimple_call_lhs (stmt);
3353
3354           /* ???  We could try to simplify calls.  */
3355
3356           if (stmt_has_constants (stmt)
3357               && TREE_CODE (lhs) == SSA_NAME)
3358             VN_INFO (lhs)->has_constants = true;
3359           else if (TREE_CODE (lhs) == SSA_NAME)
3360             {
3361               /* We reset expr and constantness here because we may
3362                  have been value numbering optimistically, and
3363                  iterating. They may become non-constant in this case,
3364                  even if they were optimistically constant. */
3365               VN_INFO (lhs)->has_constants = false;
3366               VN_INFO (lhs)->expr = NULL_TREE;
3367             }
3368
3369           if (TREE_CODE (lhs) == SSA_NAME
3370               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
3371             changed = defs_to_varying (stmt);
3372           /* ???  We should handle stores from calls.  */
3373           else if (TREE_CODE (lhs) == SSA_NAME)
3374             {
3375               if (!gimple_call_internal_p (stmt)
3376                   && gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST))
3377                 changed = visit_reference_op_call (lhs, stmt);
3378               else
3379                 changed = defs_to_varying (stmt);
3380             }
3381           else
3382             changed = defs_to_varying (stmt);
3383         }
3384     }
3385  done:
3386   return changed;
3387 }
3388
3389 /* Compare two operands by reverse postorder index */
3390
3391 static int
3392 compare_ops (const void *pa, const void *pb)
3393 {
3394   const tree opa = *((const tree *)pa);
3395   const tree opb = *((const tree *)pb);
3396   gimple opstmta = SSA_NAME_DEF_STMT (opa);
3397   gimple opstmtb = SSA_NAME_DEF_STMT (opb);
3398   basic_block bba;
3399   basic_block bbb;
3400
3401   if (gimple_nop_p (opstmta) && gimple_nop_p (opstmtb))
3402     return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3403   else if (gimple_nop_p (opstmta))
3404     return -1;
3405   else if (gimple_nop_p (opstmtb))
3406     return 1;
3407
3408   bba = gimple_bb (opstmta);
3409   bbb = gimple_bb (opstmtb);
3410
3411   if (!bba && !bbb)
3412     return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3413   else if (!bba)
3414     return -1;
3415   else if (!bbb)
3416     return 1;
3417
3418   if (bba == bbb)
3419     {
3420       if (gimple_code (opstmta) == GIMPLE_PHI
3421           && gimple_code (opstmtb) == GIMPLE_PHI)
3422         return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3423       else if (gimple_code (opstmta) == GIMPLE_PHI)
3424         return -1;
3425       else if (gimple_code (opstmtb) == GIMPLE_PHI)
3426         return 1;
3427       else if (gimple_uid (opstmta) != gimple_uid (opstmtb))
3428         return gimple_uid (opstmta) - gimple_uid (opstmtb);
3429       else
3430         return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3431     }
3432   return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
3433 }
3434
3435 /* Sort an array containing members of a strongly connected component
3436    SCC so that the members are ordered by RPO number.
3437    This means that when the sort is complete, iterating through the
3438    array will give you the members in RPO order.  */
3439
3440 static void
3441 sort_scc (VEC (tree, heap) *scc)
3442 {
3443   VEC_qsort (tree, scc, compare_ops);
3444 }
3445
3446 /* Insert the no longer used nary ONARY to the hash INFO.  */
3447
3448 static void
3449 copy_nary (vn_nary_op_t onary, vn_tables_t info)
3450 {
3451   size_t size = sizeof_vn_nary_op (onary->length);
3452   vn_nary_op_t nary = alloc_vn_nary_op_noinit (onary->length,
3453                                                &info->nary_obstack);
3454   memcpy (nary, onary,&nbs