OSDN Git Service

e8eb437d3e607ca97a259b338ee1aa8573c844f8
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-sccvn.c
1 /* SCC value numbering for trees
2    Copyright (C) 2006, 2007
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 "ggc.h"
27 #include "tree.h"
28 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "tree-inline.h"
31 #include "tree-flow.h"
32 #include "tree-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 "real.h"
39 #include "alloc-pool.h"
40 #include "tree-pass.h"
41 #include "flags.h"
42 #include "bitmap.h"
43 #include "langhooks.h"
44 #include "cfgloop.h"
45 #include "params.h"
46 #include "tree-ssa-propagate.h"
47 #include "tree-ssa-sccvn.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 /* Nary operations in the hashtable consist of length operands, an
119    opcode, and a type.  Result is the value number of the operation,
120    and hashcode is stored to avoid having to calculate it
121    repeatedly.  */
122
123 typedef struct vn_nary_op_s
124 {
125   ENUM_BITFIELD(tree_code) opcode : 16;
126   unsigned length : 16;
127   hashval_t hashcode;
128   tree result;
129   tree type;
130   tree op[4];
131 } *vn_nary_op_t;
132 typedef const struct vn_nary_op_s *const_vn_nary_op_t;
133
134 /* Phi nodes in the hashtable consist of their non-VN_TOP phi
135    arguments, and the basic block the phi is in. Result is the value
136    number of the operation, and hashcode is stored to avoid having to
137    calculate it repeatedly.  Phi nodes not in the same block are never
138    considered equivalent.  */
139
140 typedef struct vn_phi_s
141 {
142   VEC (tree, heap) *phiargs;
143   basic_block block;
144   hashval_t hashcode;
145   tree result;
146 } *vn_phi_t;
147 typedef const struct vn_phi_s *const_vn_phi_t;
148
149 /* Reference operands only exist in reference operations structures.
150    They consist of an opcode, type, and some number of operands.  For
151    a given opcode, some, all, or none of the operands may be used.
152    The operands are there to store the information that makes up the
153    portion of the addressing calculation that opcode performs.  */
154
155 typedef struct vn_reference_op_struct
156 {
157   enum tree_code opcode;
158   tree type;
159   tree op0;
160   tree op1;
161 } vn_reference_op_s;
162 typedef vn_reference_op_s *vn_reference_op_t;
163 typedef const vn_reference_op_s *const_vn_reference_op_t;
164
165 DEF_VEC_O(vn_reference_op_s);
166 DEF_VEC_ALLOC_O(vn_reference_op_s, heap);
167
168 /* A reference operation in the hashtable is representation as a
169    collection of vuses, representing the memory state at the time of
170    the operation, and a collection of operands that make up the
171    addressing calculation.  If two vn_reference_t's have the same set
172    of operands, they access the same memory location. We also store
173    the resulting value number, and the hashcode.  The vuses are
174    always stored in order sorted by ssa name version.  */
175
176 typedef struct vn_reference_s
177 {
178   VEC (tree, gc) *vuses;
179   VEC (vn_reference_op_s, heap) *operands;
180   hashval_t hashcode;
181   tree result;
182 } *vn_reference_t;
183 typedef const struct vn_reference_s *const_vn_reference_t;
184
185 /* Valid hashtables storing information we have proven to be
186    correct.  */
187
188 static vn_tables_t valid_info;
189
190 /* Optimistic hashtables storing information we are making assumptions about
191    during iterations.  */
192
193 static vn_tables_t optimistic_info;
194
195 /* PRE hashtables storing information about mapping from expressions to
196    value handles.  */
197
198 static vn_tables_t pre_info;
199
200 /* Pointer to the set of hashtables that is currently being used.
201    Should always point to either the optimistic_info, or the
202    valid_info.  */
203
204 static vn_tables_t current_info;
205
206
207 /* Reverse post order index for each basic block.  */
208
209 static int *rpo_numbers;
210
211 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
212
213 /* This represents the top of the VN lattice, which is the universal
214    value.  */
215
216 tree VN_TOP;
217
218 /* Next DFS number and the stack for strongly connected component
219    detection. */
220
221 static unsigned int next_dfs_num;
222 static VEC (tree, heap) *sccstack;
223
224 static bool may_insert;
225
226
227 DEF_VEC_P(vn_ssa_aux_t);
228 DEF_VEC_ALLOC_P(vn_ssa_aux_t, heap);
229
230 /* Table of vn_ssa_aux_t's, one per ssa_name.  The vn_ssa_aux_t objects
231    are allocated on an obstack for locality reasons, and to free them
232    without looping over the VEC.  */
233
234 static VEC (vn_ssa_aux_t, heap) *vn_ssa_aux_table;
235 static struct obstack vn_ssa_aux_obstack;
236
237 /* Return the value numbering information for a given SSA name.  */
238
239 vn_ssa_aux_t
240 VN_INFO (tree name)
241 {
242   return VEC_index (vn_ssa_aux_t, vn_ssa_aux_table,
243                     SSA_NAME_VERSION (name));
244 }
245
246 /* Set the value numbering info for a given SSA name to a given
247    value.  */
248
249 static inline void
250 VN_INFO_SET (tree name, vn_ssa_aux_t value)
251 {
252   VEC_replace (vn_ssa_aux_t, vn_ssa_aux_table,
253                SSA_NAME_VERSION (name), value);
254 }
255
256 /* Initialize the value numbering info for a given SSA name.
257    This should be called just once for every SSA name.  */
258
259 vn_ssa_aux_t
260 VN_INFO_GET (tree name)
261 {
262   vn_ssa_aux_t newinfo;
263
264   newinfo = obstack_alloc (&vn_ssa_aux_obstack, sizeof (struct vn_ssa_aux));
265   memset (newinfo, 0, sizeof (struct vn_ssa_aux));
266   if (SSA_NAME_VERSION (name) >= VEC_length (vn_ssa_aux_t, vn_ssa_aux_table))
267     VEC_safe_grow (vn_ssa_aux_t, heap, vn_ssa_aux_table,
268                    SSA_NAME_VERSION (name) + 1);
269   VEC_replace (vn_ssa_aux_t, vn_ssa_aux_table,
270                SSA_NAME_VERSION (name), newinfo);
271   return newinfo;
272 }
273
274
275 /* Free a phi operation structure VP.  */
276
277 static void
278 free_phi (void *vp)
279 {
280   vn_phi_t phi = vp;
281   VEC_free (tree, heap, phi->phiargs);
282 }
283
284 /* Free a reference operation structure VP.  */
285
286 static void
287 free_reference (void *vp)
288 {
289   vn_reference_t vr = vp;
290   VEC_free (vn_reference_op_s, heap, vr->operands);
291 }
292
293 /* Compare two reference operands P1 and P2 for equality.  return true if
294    they are equal, and false otherwise.  */
295
296 static int
297 vn_reference_op_eq (const void *p1, const void *p2)
298 {
299   const_vn_reference_op_t const vro1 = (const_vn_reference_op_t) p1;
300   const_vn_reference_op_t const vro2 = (const_vn_reference_op_t) p2;
301   return vro1->opcode == vro2->opcode
302     && vro1->type == vro2->type
303     && expressions_equal_p (vro1->op0, vro2->op0)
304     && expressions_equal_p (vro1->op1, vro2->op1);
305 }
306
307 /* Compute the hash for a reference operand VRO1  */
308
309 static hashval_t
310 vn_reference_op_compute_hash (const vn_reference_op_t vro1)
311 {
312   return iterative_hash_expr (vro1->op0, vro1->opcode)
313     + iterative_hash_expr (vro1->op1, vro1->opcode);
314 }
315
316 /* Return the hashcode for a given reference operation P1.  */
317
318 static hashval_t
319 vn_reference_hash (const void *p1)
320 {
321   const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
322   return vr1->hashcode;
323 }
324
325 /* Compute a hash for the reference operation VR1 and return it.  */
326
327 static inline hashval_t
328 vn_reference_compute_hash (const vn_reference_t vr1)
329 {
330   hashval_t result = 0;
331   tree v;
332   int i;
333   vn_reference_op_t vro;
334
335   for (i = 0; VEC_iterate (tree, vr1->vuses, i, v); i++)
336     result += iterative_hash_expr (v, 0);
337   for (i = 0; VEC_iterate (vn_reference_op_s, vr1->operands, i, vro); i++)
338     result += vn_reference_op_compute_hash (vro);
339
340   return result;
341 }
342
343 /* Return true if reference operations P1 and P2 are equivalent.  This
344    means they have the same set of operands and vuses.  */
345
346 static int
347 vn_reference_eq (const void *p1, const void *p2)
348 {
349   tree v;
350   int i;
351   vn_reference_op_t vro;
352
353   const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
354   const_vn_reference_t const vr2 = (const_vn_reference_t) p2;
355
356   if (vr1->vuses == vr2->vuses
357       && vr1->operands == vr2->operands)
358     return true;
359
360   /* Impossible for them to be equivalent if they have different
361      number of vuses.  */
362   if (VEC_length (tree, vr1->vuses) != VEC_length (tree, vr2->vuses))
363     return false;
364
365   /* We require that address operands be canonicalized in a way that
366      two memory references will have the same operands if they are
367      equivalent.  */
368   if (VEC_length (vn_reference_op_s, vr1->operands)
369       != VEC_length (vn_reference_op_s, vr2->operands))
370     return false;
371
372   /* The memory state is more often different than the address of the
373      store/load, so check it first.  */
374   for (i = 0; VEC_iterate (tree, vr1->vuses, i, v); i++)
375     {
376       if (VEC_index (tree, vr2->vuses, i) != v)
377         return false;
378     }
379
380   for (i = 0; VEC_iterate (vn_reference_op_s, vr1->operands, i, vro); i++)
381     {
382       if (!vn_reference_op_eq (VEC_index (vn_reference_op_s, vr2->operands, i),
383                                vro))
384         return false;
385     }
386   return true;
387 }
388
389 /* Place the vuses from STMT into *result */
390
391 static inline void
392 vuses_to_vec (tree stmt, VEC (tree, gc) **result)
393 {
394   ssa_op_iter iter;
395   tree vuse;
396
397   if (!stmt)
398     return;
399
400   VEC_reserve_exact (tree, gc, *result,
401                      num_ssa_operands (stmt, SSA_OP_VIRTUAL_USES));
402
403   FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VIRTUAL_USES)
404     VEC_quick_push (tree, *result, vuse);
405 }
406
407
408 /* Copy the VUSE names in STMT into a vector, and return
409    the vector.  */
410
411 VEC (tree, gc) *
412 copy_vuses_from_stmt (tree stmt)
413 {
414   VEC (tree, gc) *vuses = NULL;
415
416   vuses_to_vec (stmt, &vuses);
417
418   return vuses;
419 }
420
421 /* Place the vdefs from STMT into *result */
422
423 static inline void
424 vdefs_to_vec (tree stmt, VEC (tree, gc) **result)
425 {
426   ssa_op_iter iter;
427   tree vdef;
428
429   if (!stmt)
430     return;
431
432   *result = VEC_alloc (tree, gc, num_ssa_operands (stmt, SSA_OP_VIRTUAL_DEFS));
433
434   FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, iter, SSA_OP_VIRTUAL_DEFS)
435     VEC_quick_push (tree, *result, vdef);
436 }
437
438 /* Copy the names of vdef results in STMT into a vector, and return
439    the vector.  */
440
441 static VEC (tree, gc) *
442 copy_vdefs_from_stmt (tree stmt)
443 {
444   VEC (tree, gc) *vdefs = NULL;
445
446   vdefs_to_vec (stmt, &vdefs);
447
448   return vdefs;
449 }
450
451 /* Place for shared_v{uses/defs}_from_stmt to shove vuses/vdefs.  */
452 static VEC (tree, gc) *shared_lookup_vops;
453
454 /* Copy the virtual uses from STMT into SHARED_LOOKUP_VOPS.
455    This function will overwrite the current SHARED_LOOKUP_VOPS
456    variable.  */
457
458 VEC (tree, gc) *
459 shared_vuses_from_stmt (tree stmt)
460 {
461   VEC_truncate (tree, shared_lookup_vops, 0);
462   vuses_to_vec (stmt, &shared_lookup_vops);
463
464   return shared_lookup_vops;
465 }
466
467 /* Copy the operations present in load/store/call REF into RESULT, a vector of
468    vn_reference_op_s's.  */
469
470 static void
471 copy_reference_ops_from_ref (tree ref, VEC(vn_reference_op_s, heap) **result)
472 {
473   /* Calls are different from all other reference operations.  */
474   if (TREE_CODE (ref) == CALL_EXPR)
475     {
476       vn_reference_op_s temp;
477       tree callfn;
478       call_expr_arg_iterator iter;
479       tree callarg;
480
481       /* Copy the call_expr opcode, type, function being called, and
482          arguments.  */
483       memset (&temp, 0, sizeof (temp));
484       temp.type = TREE_TYPE (ref);
485       temp.opcode = CALL_EXPR;
486       VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
487
488       callfn = get_callee_fndecl (ref);
489       if (!callfn)
490         callfn = CALL_EXPR_FN (ref);
491       temp.type = TREE_TYPE (callfn);
492       temp.opcode = TREE_CODE (callfn);
493       temp.op0 = callfn;
494       VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
495
496       FOR_EACH_CALL_EXPR_ARG (callarg, iter, ref)
497         {
498           memset (&temp, 0, sizeof (temp));
499           temp.type = TREE_TYPE (callarg);
500           temp.opcode = TREE_CODE (callarg);
501           temp.op0 = callarg;
502           VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
503         }
504       return;
505     }
506
507   if (TREE_CODE (ref) == TARGET_MEM_REF)
508     {
509       vn_reference_op_s temp;
510
511       memset (&temp, 0, sizeof (temp));
512       /* We do not care for spurious type qualifications.  */
513       temp.type = TYPE_MAIN_VARIANT (TREE_TYPE (ref));
514       temp.opcode = TREE_CODE (ref);
515       temp.op0 = TMR_SYMBOL (ref) ? TMR_SYMBOL (ref) : TMR_BASE (ref);
516       temp.op1 = TMR_INDEX (ref);
517       VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
518
519       memset (&temp, 0, sizeof (temp));
520       temp.type = NULL_TREE;
521       temp.opcode = TREE_CODE (ref);
522       temp.op0 = TMR_STEP (ref);
523       temp.op1 = TMR_OFFSET (ref);
524       VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
525       return;
526     }
527
528   /* For non-calls, store the information that makes up the address.  */
529
530   while (ref)
531     {
532       vn_reference_op_s temp;
533
534       memset (&temp, 0, sizeof (temp));
535       /* We do not care for spurious type qualifications.  */
536       temp.type = TYPE_MAIN_VARIANT (TREE_TYPE (ref));
537       temp.opcode = TREE_CODE (ref);
538
539       switch (temp.opcode)
540         {
541         case ALIGN_INDIRECT_REF:
542         case MISALIGNED_INDIRECT_REF:
543         case INDIRECT_REF:
544           /* The only operand is the address, which gets its own
545              vn_reference_op_s structure.  */
546           break;
547         case BIT_FIELD_REF:
548           /* Record bits and position.  */
549           temp.op0 = TREE_OPERAND (ref, 1);
550           temp.op1 = TREE_OPERAND (ref, 2);
551           break;
552         case COMPONENT_REF:
553           /* The field decl is enough to unambiguously specify the field,
554              a matching type is not necessary and a mismatching type
555              is always a spurious difference.  */
556           temp.type = NULL_TREE;
557           /* If this is a reference to a union member, record the union
558              member size as operand.  Do so only if we are doing
559              expression insertion (during FRE), as PRE currently gets
560              confused with this.  */
561           if (may_insert
562               && TREE_CODE (DECL_CONTEXT (TREE_OPERAND (ref, 1))) == UNION_TYPE
563               && integer_zerop (DECL_FIELD_OFFSET (TREE_OPERAND (ref, 1)))
564               && integer_zerop (DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1))))
565             temp.op0 = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (ref, 1)));
566           else
567             /* Record field as operand.  */
568             temp.op0 = TREE_OPERAND (ref, 1);
569           break;
570         case ARRAY_RANGE_REF:
571         case ARRAY_REF:
572           /* Record index as operand.  */
573           temp.op0 = TREE_OPERAND (ref, 1);
574           temp.op1 = TREE_OPERAND (ref, 3);
575           break;
576         case STRING_CST:
577         case INTEGER_CST:
578         case COMPLEX_CST:
579         case VECTOR_CST:
580         case REAL_CST:
581         case CONSTRUCTOR:
582         case VALUE_HANDLE:
583         case VAR_DECL:
584         case PARM_DECL:
585         case CONST_DECL:
586         case RESULT_DECL:
587         case SSA_NAME:
588           temp.op0 = ref;
589           break;
590           /* These are only interesting for their operands, their
591              existence, and their type.  They will never be the last
592              ref in the chain of references (IE they require an
593              operand), so we don't have to put anything
594              for op* as it will be handled by the iteration  */
595         case IMAGPART_EXPR:
596         case REALPART_EXPR:
597         case VIEW_CONVERT_EXPR:
598         case ADDR_EXPR:
599           break;
600         default:
601           gcc_unreachable ();
602
603         }
604       VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
605
606       if (REFERENCE_CLASS_P (ref) || TREE_CODE (ref) == ADDR_EXPR)
607         ref = TREE_OPERAND (ref, 0);
608       else
609         ref = NULL_TREE;
610     }
611 }
612
613 /* Create a vector of vn_reference_op_s structures from REF, a
614    REFERENCE_CLASS_P tree.  The vector is not shared. */
615
616 static VEC(vn_reference_op_s, heap) *
617 create_reference_ops_from_ref (tree ref)
618 {
619   VEC (vn_reference_op_s, heap) *result = NULL;
620
621   copy_reference_ops_from_ref (ref, &result);
622   return result;
623 }
624
625 static VEC(vn_reference_op_s, heap) *shared_lookup_references;
626
627 /* Create a vector of vn_reference_op_s structures from REF, a
628    REFERENCE_CLASS_P tree.  The vector is shared among all callers of
629    this function.  */
630
631 static VEC(vn_reference_op_s, heap) *
632 shared_reference_ops_from_ref (tree ref)
633 {
634   if (!ref)
635     return NULL;
636   VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
637   copy_reference_ops_from_ref (ref, &shared_lookup_references);
638   return shared_lookup_references;
639 }
640
641
642 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
643    structures into their value numbers.  This is done in-place, and
644    the vector passed in is returned.  */
645
646 static VEC (vn_reference_op_s, heap) *
647 valueize_refs (VEC (vn_reference_op_s, heap) *orig)
648 {
649   vn_reference_op_t vro;
650   int i;
651
652   for (i = 0; VEC_iterate (vn_reference_op_s, orig, i, vro); i++)
653     {
654       if (vro->opcode == SSA_NAME
655           || (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME))
656         vro->op0 = SSA_VAL (vro->op0);
657     }
658
659   return orig;
660 }
661
662 /* Transform any SSA_NAME's in ORIG, a vector of vuse trees, into
663    their value numbers. This is done in-place, and the vector passed
664    in is returned.  */
665
666 static VEC (tree, gc) *
667 valueize_vuses (VEC (tree, gc) *orig)
668 {
669   bool made_replacement = false;
670   tree vuse;
671   int i;
672
673   for (i = 0; VEC_iterate (tree, orig, i, vuse); i++)
674     {
675       if (vuse != SSA_VAL (vuse))
676         {
677           made_replacement = true;
678           VEC_replace (tree, orig, i, SSA_VAL (vuse));
679         }
680     }
681
682   if (made_replacement && VEC_length (tree, orig) > 1)
683     sort_vuses (orig);
684
685   return orig;
686 }
687
688 /* Return the single reference statement defining all virtual uses
689    in VUSES or NULL_TREE, if there are multiple defining statements.
690    Take into account only definitions that alias REF if following
691    back-edges.  */
692
693 static tree
694 get_def_ref_stmt_vuses (tree ref, VEC (tree, gc) *vuses)
695 {
696   tree def_stmt, vuse;
697   unsigned int i;
698
699   gcc_assert (VEC_length (tree, vuses) >= 1);
700
701   def_stmt = SSA_NAME_DEF_STMT (VEC_index (tree, vuses, 0));
702   if (TREE_CODE (def_stmt) == PHI_NODE)
703     {
704       /* We can only handle lookups over PHI nodes for a single
705          virtual operand.  */
706       if (VEC_length (tree, vuses) == 1)
707         {
708           def_stmt = get_single_def_stmt_from_phi (ref, def_stmt);
709           goto cont;
710         }
711       else
712         return NULL_TREE;
713     }
714
715   /* Verify each VUSE reaches the same defining stmt.  */
716   for (i = 1; VEC_iterate (tree, vuses, i, vuse); ++i)
717     {
718       tree tmp = SSA_NAME_DEF_STMT (vuse);
719       if (tmp != def_stmt)
720         return NULL_TREE;
721     }
722
723   /* Now see if the definition aliases ref, and loop until it does.  */
724 cont:
725   while (def_stmt
726          && TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
727          && !get_call_expr_in (def_stmt)
728          && !refs_may_alias_p (ref, GIMPLE_STMT_OPERAND (def_stmt, 0)))
729     def_stmt = get_single_def_stmt_with_phi (ref, def_stmt);
730
731   return def_stmt;
732 }
733
734 /* Lookup a SCCVN reference operation VR in the current hash table.
735    Returns the resulting value number if it exists in the hash table,
736    NULL_TREE otherwise.  */
737
738 static tree
739 vn_reference_lookup_1 (vn_reference_t vr)
740 {
741   void **slot;
742   hashval_t hash;
743
744   hash = vr->hashcode;
745   slot = htab_find_slot_with_hash (current_info->references, vr,
746                                    hash, NO_INSERT);
747   if (!slot && current_info == optimistic_info)
748     slot = htab_find_slot_with_hash (valid_info->references, vr,
749                                      hash, NO_INSERT);
750   if (slot)
751     return ((vn_reference_t)*slot)->result;
752
753   return NULL_TREE;
754 }
755
756 /* Lookup OP in the current hash table, and return the resulting
757    value number if it exists in the hash table.  Return NULL_TREE if
758    it does not exist in the hash table. */
759
760 tree
761 vn_reference_lookup (tree op, VEC (tree, gc) *vuses, bool maywalk)
762 {
763   struct vn_reference_s vr1;
764   tree result, def_stmt;
765
766   vr1.vuses = valueize_vuses (vuses);
767   vr1.operands = valueize_refs (shared_reference_ops_from_ref (op));
768   vr1.hashcode = vn_reference_compute_hash (&vr1);
769   result = vn_reference_lookup_1 (&vr1);
770
771   /* If there is a single defining statement for all virtual uses, we can
772      use that, following virtual use-def chains.  */
773   if (!result
774       && maywalk
775       && vr1.vuses
776       && VEC_length (tree, vr1.vuses) >= 1
777       && !get_call_expr_in (op)
778       && (def_stmt = get_def_ref_stmt_vuses (op, vr1.vuses))
779       && TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
780       /* If there is a call involved, op must be assumed to
781          be clobbered.  */
782       && !get_call_expr_in (def_stmt))
783     {
784       /* We are now at an aliasing definition for the vuses we want to
785          look up.  Re-do the lookup with the vdefs for this stmt.  */
786       vdefs_to_vec (def_stmt, &vuses);
787       vr1.vuses = valueize_vuses (vuses);
788       vr1.hashcode = vn_reference_compute_hash (&vr1);
789       result = vn_reference_lookup_1 (&vr1);
790     }
791
792   return result;
793 }
794
795 /* Insert OP into the current hash table with a value number of
796    RESULT.  */
797
798 void
799 vn_reference_insert (tree op, tree result, VEC (tree, gc) *vuses)
800 {
801   void **slot;
802   vn_reference_t vr1;
803
804   vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
805
806   vr1->vuses = valueize_vuses (vuses);
807   vr1->operands = valueize_refs (create_reference_ops_from_ref (op));
808   vr1->hashcode = vn_reference_compute_hash (vr1);
809   vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result;
810
811   slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
812                                    INSERT);
813
814   /* Because we lookup stores using vuses, and value number failures
815      using the vdefs (see visit_reference_op_store for how and why),
816      it's possible that on failure we may try to insert an already
817      inserted store.  This is not wrong, there is no ssa name for a
818      store that we could use as a differentiator anyway.  Thus, unlike
819      the other lookup functions, you cannot gcc_assert (!*slot)
820      here.  */
821
822   /* But free the old slot in case of a collision.  */
823   if (*slot)
824     free_reference (*slot);
825
826   *slot = vr1;
827 }
828
829 /* Compute and return the hash value for nary operation VBO1.  */
830
831 static inline hashval_t
832 vn_nary_op_compute_hash (const vn_nary_op_t vno1)
833 {
834   hashval_t hash = 0;
835   unsigned i;
836
837   for (i = 0; i < vno1->length; ++i)
838     if (TREE_CODE (vno1->op[i]) == SSA_NAME)
839       vno1->op[i] = SSA_VAL (vno1->op[i]);
840
841   if (vno1->length == 2
842       && commutative_tree_code (vno1->opcode)
843       && tree_swap_operands_p (vno1->op[0], vno1->op[1], false))
844     {
845       tree temp = vno1->op[0];
846       vno1->op[0] = vno1->op[1];
847       vno1->op[1] = temp;
848     }
849
850   for (i = 0; i < vno1->length; ++i)
851     hash += iterative_hash_expr (vno1->op[i], vno1->opcode);
852
853   return hash;
854 }
855
856 /* Return the computed hashcode for nary operation P1.  */
857
858 static hashval_t
859 vn_nary_op_hash (const void *p1)
860 {
861   const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
862   return vno1->hashcode;
863 }
864
865 /* Compare nary operations P1 and P2 and return true if they are
866    equivalent.  */
867
868 static int
869 vn_nary_op_eq (const void *p1, const void *p2)
870 {
871   const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
872   const_vn_nary_op_t const vno2 = (const_vn_nary_op_t) p2;
873   unsigned i;
874
875   if (vno1->opcode != vno2->opcode
876       || vno1->type != vno2->type)
877     return false;
878
879   for (i = 0; i < vno1->length; ++i)
880     if (!expressions_equal_p (vno1->op[i], vno2->op[i]))
881       return false;
882
883   return true;
884 }
885
886 /* Lookup OP in the current hash table, and return the resulting
887    value number if it exists in the hash table.  Return NULL_TREE if
888    it does not exist in the hash table. */
889
890 tree
891 vn_nary_op_lookup (tree op)
892 {
893   void **slot;
894   struct vn_nary_op_s vno1;
895   unsigned i;
896
897   vno1.opcode = TREE_CODE (op);
898   vno1.length = TREE_CODE_LENGTH (TREE_CODE (op));
899   vno1.type = TREE_TYPE (op);
900   for (i = 0; i < vno1.length; ++i)
901     vno1.op[i] = TREE_OPERAND (op, i);
902   vno1.hashcode = vn_nary_op_compute_hash (&vno1);
903   slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
904                                    NO_INSERT);
905   if (!slot && current_info == optimistic_info)
906     slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
907                                      NO_INSERT);
908   if (!slot)
909     return NULL_TREE;
910   return ((vn_nary_op_t)*slot)->result;
911 }
912
913 /* Insert OP into the current hash table with a value number of
914    RESULT.  */
915
916 void
917 vn_nary_op_insert (tree op, tree result)
918 {
919   unsigned length = TREE_CODE_LENGTH (TREE_CODE (op));
920   void **slot;
921   vn_nary_op_t vno1;
922   unsigned i;
923
924   vno1 = obstack_alloc (&current_info->nary_obstack,
925                         (sizeof (struct vn_nary_op_s)
926                          - sizeof (tree) * (4 - length)));
927   vno1->opcode = TREE_CODE (op);
928   vno1->length = length;
929   vno1->type = TREE_TYPE (op);
930   for (i = 0; i < vno1->length; ++i)
931     vno1->op[i] = TREE_OPERAND (op, i);
932   vno1->result = result;
933   vno1->hashcode = vn_nary_op_compute_hash (vno1);
934   slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
935                                    INSERT);
936   gcc_assert (!*slot);
937
938   *slot = vno1;
939 }
940
941 /* Compute a hashcode for PHI operation VP1 and return it.  */
942
943 static inline hashval_t
944 vn_phi_compute_hash (vn_phi_t vp1)
945 {
946   hashval_t result = 0;
947   int i;
948   tree phi1op;
949
950   result = vp1->block->index;
951
952   for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
953     {
954       if (phi1op == VN_TOP)
955         continue;
956       result += iterative_hash_expr (phi1op, result);
957     }
958
959   return result;
960 }
961
962 /* Return the computed hashcode for phi operation P1.  */
963
964 static hashval_t
965 vn_phi_hash (const void *p1)
966 {
967   const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
968   return vp1->hashcode;
969 }
970
971 /* Compare two phi entries for equality, ignoring VN_TOP arguments.  */
972
973 static int
974 vn_phi_eq (const void *p1, const void *p2)
975 {
976   const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
977   const_vn_phi_t const vp2 = (const_vn_phi_t) p2;
978
979   if (vp1->block == vp2->block)
980     {
981       int i;
982       tree phi1op;
983
984       /* Any phi in the same block will have it's arguments in the
985          same edge order, because of how we store phi nodes.  */
986       for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
987         {
988           tree phi2op = VEC_index (tree, vp2->phiargs, i);
989           if (phi1op == VN_TOP || phi2op == VN_TOP)
990             continue;
991           if (!expressions_equal_p (phi1op, phi2op))
992             return false;
993         }
994       return true;
995     }
996   return false;
997 }
998
999 static VEC(tree, heap) *shared_lookup_phiargs;
1000
1001 /* Lookup PHI in the current hash table, and return the resulting
1002    value number if it exists in the hash table.  Return NULL_TREE if
1003    it does not exist in the hash table. */
1004
1005 static tree
1006 vn_phi_lookup (tree phi)
1007 {
1008   void **slot;
1009   struct vn_phi_s vp1;
1010   int i;
1011
1012   VEC_truncate (tree, shared_lookup_phiargs, 0);
1013
1014   /* Canonicalize the SSA_NAME's to their value number.  */
1015   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1016     {
1017       tree def = PHI_ARG_DEF (phi, i);
1018       def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
1019       VEC_safe_push (tree, heap, shared_lookup_phiargs, def);
1020     }
1021   vp1.phiargs = shared_lookup_phiargs;
1022   vp1.block = bb_for_stmt (phi);
1023   vp1.hashcode = vn_phi_compute_hash (&vp1);
1024   slot = htab_find_slot_with_hash (current_info->phis, &vp1, vp1.hashcode,
1025                                    NO_INSERT);
1026   if (!slot && current_info == optimistic_info)
1027     slot = htab_find_slot_with_hash (valid_info->phis, &vp1, vp1.hashcode,
1028                                      NO_INSERT);
1029   if (!slot)
1030     return NULL_TREE;
1031   return ((vn_phi_t)*slot)->result;
1032 }
1033
1034 /* Insert PHI into the current hash table with a value number of
1035    RESULT.  */
1036
1037 static void
1038 vn_phi_insert (tree phi, tree result)
1039 {
1040   void **slot;
1041   vn_phi_t vp1 = (vn_phi_t) pool_alloc (current_info->phis_pool);
1042   int i;
1043   VEC (tree, heap) *args = NULL;
1044
1045   /* Canonicalize the SSA_NAME's to their value number.  */
1046   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1047     {
1048       tree def = PHI_ARG_DEF (phi, i);
1049       def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
1050       VEC_safe_push (tree, heap, args, def);
1051     }
1052   vp1->phiargs = args;
1053   vp1->block = bb_for_stmt (phi);
1054   vp1->result = result;
1055   vp1->hashcode = vn_phi_compute_hash (vp1);
1056
1057   slot = htab_find_slot_with_hash (current_info->phis, vp1, vp1->hashcode,
1058                                    INSERT);
1059
1060   /* Because we iterate over phi operations more than once, it's
1061      possible the slot might already exist here, hence no assert.*/
1062   *slot = vp1;
1063 }
1064
1065
1066 /* Print set of components in strongly connected component SCC to OUT. */
1067
1068 static void
1069 print_scc (FILE *out, VEC (tree, heap) *scc)
1070 {
1071   tree var;
1072   unsigned int i;
1073
1074   fprintf (out, "SCC consists of: ");
1075   for (i = 0; VEC_iterate (tree, scc, i, var); i++)
1076     {
1077       print_generic_expr (out, var, 0);
1078       fprintf (out, " ");
1079     }
1080   fprintf (out, "\n");
1081 }
1082
1083 /* Set the value number of FROM to TO, return true if it has changed
1084    as a result.  */
1085
1086 static inline bool
1087 set_ssa_val_to (tree from, tree to)
1088 {
1089   tree currval;
1090
1091   if (from != to
1092       && TREE_CODE (to) == SSA_NAME
1093       && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to))
1094     to = from;
1095
1096   /* The only thing we allow as value numbers are VN_TOP, ssa_names
1097      and invariants.  So assert that here.  */
1098   gcc_assert (to != NULL_TREE
1099               && (to == VN_TOP
1100                   || TREE_CODE (to) == SSA_NAME
1101                   || is_gimple_min_invariant (to)));
1102
1103   if (dump_file && (dump_flags & TDF_DETAILS))
1104     {
1105       fprintf (dump_file, "Setting value number of ");
1106       print_generic_expr (dump_file, from, 0);
1107       fprintf (dump_file, " to ");
1108       print_generic_expr (dump_file, to, 0);
1109       fprintf (dump_file, "\n");
1110     }
1111
1112   currval = SSA_VAL (from);
1113
1114   if (currval != to  && !operand_equal_p (currval, to, OEP_PURE_SAME))
1115     {
1116       SSA_VAL (from) = to;
1117       return true;
1118     }
1119   return false;
1120 }
1121
1122 /* Set all definitions in STMT to value number to themselves.
1123    Return true if a value number changed. */
1124
1125 static bool
1126 defs_to_varying (tree stmt)
1127 {
1128   bool changed = false;
1129   ssa_op_iter iter;
1130   def_operand_p defp;
1131
1132   FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
1133     {
1134       tree def = DEF_FROM_PTR (defp);
1135
1136       VN_INFO (def)->use_processed = true;
1137       changed |= set_ssa_val_to (def, def);
1138     }
1139   return changed;
1140 }
1141
1142 static tree
1143 try_to_simplify (tree stmt, tree rhs);
1144
1145 /* Visit a copy between LHS and RHS, return true if the value number
1146    changed.  */
1147
1148 static bool
1149 visit_copy (tree lhs, tree rhs)
1150 {
1151
1152   /* Follow chains of copies to their destination.  */
1153   while (SSA_VAL (rhs) != rhs && TREE_CODE (SSA_VAL (rhs)) == SSA_NAME)
1154     rhs = SSA_VAL (rhs);
1155
1156   /* The copy may have a more interesting constant filled expression
1157      (we don't, since we know our RHS is just an SSA name).  */
1158   VN_INFO (lhs)->has_constants = VN_INFO (rhs)->has_constants;
1159   VN_INFO (lhs)->expr = VN_INFO (rhs)->expr;
1160
1161   return set_ssa_val_to (lhs, rhs);
1162 }
1163
1164 /* Visit a unary operator RHS, value number it, and return true if the
1165    value number of LHS has changed as a result.  */
1166
1167 static bool
1168 visit_unary_op (tree lhs, tree op)
1169 {
1170   bool changed = false;
1171   tree result = vn_nary_op_lookup (op);
1172
1173   if (result)
1174     {
1175       changed = set_ssa_val_to (lhs, result);
1176     }
1177   else
1178     {
1179       changed = set_ssa_val_to (lhs, lhs);
1180       vn_nary_op_insert (op, lhs);
1181     }
1182
1183   return changed;
1184 }
1185
1186 /* Visit a binary operator RHS, value number it, and return true if the
1187    value number of LHS has changed as a result.  */
1188
1189 static bool
1190 visit_binary_op (tree lhs, tree op)
1191 {
1192   bool changed = false;
1193   tree result = vn_nary_op_lookup (op);
1194
1195   if (result)
1196     {
1197       changed = set_ssa_val_to (lhs, result);
1198     }
1199   else
1200     {
1201       changed = set_ssa_val_to (lhs, lhs);
1202       vn_nary_op_insert (op, lhs);
1203     }
1204
1205   return changed;
1206 }
1207
1208 /* Visit a load from a reference operator RHS, part of STMT, value number it,
1209    and return true if the value number of the LHS has changed as a result.  */
1210
1211 static bool
1212 visit_reference_op_load (tree lhs, tree op, tree stmt)
1213 {
1214   bool changed = false;
1215   tree result = vn_reference_lookup (op, shared_vuses_from_stmt (stmt), true);
1216
1217   /* We handle type-punning through unions by value-numbering based
1218      on offset and size of the access.  Be prepared to handle a
1219      type-mismatch here via creating a VIEW_CONVERT_EXPR.  */
1220   if (result
1221       && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (op)))
1222     {
1223       /* We will be setting the value number of lhs to the value number
1224          of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
1225          So first simplify and lookup this expression to see if it
1226          is already available.  */
1227       tree val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (op), result);
1228       if (stmt
1229           && !is_gimple_min_invariant (val)
1230           && TREE_CODE (val) != SSA_NAME)
1231         {
1232           tree tem = try_to_simplify (stmt, val);
1233           if (tem)
1234             val = tem;
1235         }
1236       result = val;
1237       if (!is_gimple_min_invariant (val)
1238           && TREE_CODE (val) != SSA_NAME)
1239         result = vn_nary_op_lookup (val);
1240       /* If the expression is not yet available, value-number lhs to
1241          a new SSA_NAME we create.  */
1242       if (!result && may_insert)
1243         {
1244           result = make_ssa_name (SSA_NAME_VAR (lhs), NULL_TREE);
1245           /* Initialize value-number information properly.  */
1246           VN_INFO_GET (result)->valnum = result;
1247           VN_INFO (result)->expr = val;
1248           VN_INFO (result)->needs_insertion = true;
1249           /* As all "inserted" statements are singleton SCCs, insert
1250              to the valid table.  This is strictly needed to
1251              avoid re-generating new value SSA_NAMEs for the same
1252              expression during SCC iteration over and over (the
1253              optimistic table gets cleared after each iteration).
1254              We do not need to insert into the optimistic table, as
1255              lookups there will fall back to the valid table.  */
1256           if (current_info == optimistic_info)
1257             {
1258               current_info = valid_info;
1259               vn_nary_op_insert (val, result);
1260               current_info = optimistic_info;
1261             }
1262           else
1263             vn_nary_op_insert (val, result);
1264           if (dump_file && (dump_flags & TDF_DETAILS))
1265             {
1266               fprintf (dump_file, "Inserting name ");
1267               print_generic_expr (dump_file, result, 0);
1268               fprintf (dump_file, " for expression ");
1269               print_generic_expr (dump_file, val, 0);
1270               fprintf (dump_file, "\n");
1271             }
1272         }
1273     }
1274
1275   if (result)
1276     {
1277       changed = set_ssa_val_to (lhs, result);
1278       if (TREE_CODE (result) == SSA_NAME
1279           && VN_INFO (result)->has_constants)
1280         {
1281           VN_INFO (lhs)->expr = VN_INFO (result)->expr;
1282           VN_INFO (lhs)->has_constants = true;
1283         }
1284     }
1285   else
1286     {
1287       changed = set_ssa_val_to (lhs, lhs);
1288       vn_reference_insert (op, lhs, copy_vuses_from_stmt (stmt));
1289     }
1290
1291   return changed;
1292 }
1293
1294
1295 /* Visit a store to a reference operator LHS, part of STMT, value number it,
1296    and return true if the value number of the LHS has changed as a result.  */
1297
1298 static bool
1299 visit_reference_op_store (tree lhs, tree op, tree stmt)
1300 {
1301   bool changed = false;
1302   tree result;
1303   bool resultsame = false;
1304
1305   /* First we want to lookup using the *vuses* from the store and see
1306      if there the last store to this location with the same address
1307      had the same value.
1308
1309      The vuses represent the memory state before the store.  If the
1310      memory state, address, and value of the store is the same as the
1311      last store to this location, then this store will produce the
1312      same memory state as that store.
1313
1314      In this case the vdef versions for this store are value numbered to those
1315      vuse versions, since they represent the same memory state after
1316      this store.
1317
1318      Otherwise, the vdefs for the store are used when inserting into
1319      the table, since the store generates a new memory state.  */
1320
1321   result = vn_reference_lookup (lhs, shared_vuses_from_stmt (stmt), false);
1322
1323   if (result)
1324     {
1325       if (TREE_CODE (result) == SSA_NAME)
1326         result = SSA_VAL (result);
1327       if (TREE_CODE (op) == SSA_NAME)
1328         op = SSA_VAL (op);
1329       resultsame = expressions_equal_p (result, op);
1330     }
1331
1332   if (!result || !resultsame)
1333     {
1334       VEC(tree, gc) *vdefs = copy_vdefs_from_stmt (stmt);
1335       int i;
1336       tree vdef;
1337
1338       if (dump_file && (dump_flags & TDF_DETAILS))
1339         {
1340           fprintf (dump_file, "No store match\n");
1341           fprintf (dump_file, "Value numbering store ");
1342           print_generic_expr (dump_file, lhs, 0);
1343           fprintf (dump_file, " to ");
1344           print_generic_expr (dump_file, op, 0);
1345           fprintf (dump_file, "\n");
1346         }
1347       /* Have to set value numbers before insert, since insert is
1348          going to valueize the references in-place.  */
1349       for (i = 0; VEC_iterate (tree, vdefs, i, vdef); i++)
1350         {
1351           VN_INFO (vdef)->use_processed = true;
1352           changed |= set_ssa_val_to (vdef, vdef);
1353         }
1354
1355       /* Do not insert structure copies into the tables.  */
1356       if (is_gimple_min_invariant (op)
1357           || is_gimple_reg (op))
1358         vn_reference_insert (lhs, op, vdefs);
1359     }
1360   else
1361     {
1362       /* We had a match, so value number the vdefs to have the value
1363          number of the vuses they came from.  */
1364       ssa_op_iter op_iter;
1365       def_operand_p var;
1366       vuse_vec_p vv;
1367
1368       if (dump_file && (dump_flags & TDF_DETAILS))
1369         fprintf (dump_file, "Store matched earlier value,"
1370                  "value numbering store vdefs to matching vuses.\n");
1371
1372       FOR_EACH_SSA_VDEF_OPERAND (var, vv, stmt, op_iter)
1373         {
1374           tree def = DEF_FROM_PTR (var);
1375           tree use;
1376
1377           /* Uh, if the vuse is a multiuse, we can't really do much
1378              here, sadly, since we don't know which value number of
1379              which vuse to use.  */
1380           if (VUSE_VECT_NUM_ELEM (*vv) != 1)
1381             use = def;
1382           else
1383             use = VUSE_ELEMENT_VAR (*vv, 0);
1384
1385           VN_INFO (def)->use_processed = true;
1386           changed |= set_ssa_val_to (def, SSA_VAL (use));
1387         }
1388     }
1389
1390   return changed;
1391 }
1392
1393 /* Visit and value number PHI, return true if the value number
1394    changed.  */
1395
1396 static bool
1397 visit_phi (tree phi)
1398 {
1399   bool changed = false;
1400   tree result;
1401   tree sameval = VN_TOP;
1402   bool allsame = true;
1403   int i;
1404
1405   /* TODO: We could check for this in init_sccvn, and replace this
1406      with a gcc_assert.  */
1407   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
1408     return set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
1409
1410   /* See if all non-TOP arguments have the same value.  TOP is
1411      equivalent to everything, so we can ignore it.  */
1412   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1413     {
1414       tree def = PHI_ARG_DEF (phi, i);
1415
1416       if (TREE_CODE (def) == SSA_NAME)
1417         def = SSA_VAL (def);
1418       if (def == VN_TOP)
1419         continue;
1420       if (sameval == VN_TOP)
1421         {
1422           sameval = def;
1423         }
1424       else
1425         {
1426           if (!expressions_equal_p (def, sameval))
1427             {
1428               allsame = false;
1429               break;
1430             }
1431         }
1432     }
1433
1434   /* If all value numbered to the same value, the phi node has that
1435      value.  */
1436   if (allsame)
1437     {
1438       if (is_gimple_min_invariant (sameval))
1439         {
1440           VN_INFO (PHI_RESULT (phi))->has_constants = true;
1441           VN_INFO (PHI_RESULT (phi))->expr = sameval;
1442         }
1443       else
1444         {
1445           VN_INFO (PHI_RESULT (phi))->has_constants = false;
1446           VN_INFO (PHI_RESULT (phi))->expr = sameval;
1447         }
1448
1449       if (TREE_CODE (sameval) == SSA_NAME)
1450         return visit_copy (PHI_RESULT (phi), sameval);
1451
1452       return set_ssa_val_to (PHI_RESULT (phi), sameval);
1453     }
1454
1455   /* Otherwise, see if it is equivalent to a phi node in this block.  */
1456   result = vn_phi_lookup (phi);
1457   if (result)
1458     {
1459       if (TREE_CODE (result) == SSA_NAME)
1460         changed = visit_copy (PHI_RESULT (phi), result);
1461       else
1462         changed = set_ssa_val_to (PHI_RESULT (phi), result);
1463     }
1464   else
1465     {
1466       vn_phi_insert (phi, PHI_RESULT (phi));
1467       VN_INFO (PHI_RESULT (phi))->has_constants = false;
1468       VN_INFO (PHI_RESULT (phi))->expr = PHI_RESULT (phi);
1469       changed = set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
1470     }
1471
1472   return changed;
1473 }
1474
1475 /* Return true if EXPR contains constants.  */
1476
1477 static bool
1478 expr_has_constants (tree expr)
1479 {
1480   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1481     {
1482     case tcc_unary:
1483       return is_gimple_min_invariant (TREE_OPERAND (expr, 0));
1484
1485     case tcc_binary:
1486       return is_gimple_min_invariant (TREE_OPERAND (expr, 0))
1487         || is_gimple_min_invariant (TREE_OPERAND (expr, 1));
1488       /* Constants inside reference ops are rarely interesting, but
1489          it can take a lot of looking to find them.  */
1490     case tcc_reference:
1491     case tcc_declaration:
1492       return false;
1493     default:
1494       return is_gimple_min_invariant (expr);
1495     }
1496   return false;
1497 }
1498
1499 /* Replace SSA_NAMES in expr with their value numbers, and return the
1500    result.
1501    This is performed in place. */
1502
1503 static tree
1504 valueize_expr (tree expr)
1505 {
1506   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1507     {
1508     case tcc_unary:
1509       if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
1510           && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
1511         TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
1512       break;
1513     case tcc_binary:
1514       if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
1515           && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
1516         TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
1517       if (TREE_CODE (TREE_OPERAND (expr, 1)) == SSA_NAME
1518           && SSA_VAL (TREE_OPERAND (expr, 1)) != VN_TOP)
1519         TREE_OPERAND (expr, 1) = SSA_VAL (TREE_OPERAND (expr, 1));
1520       break;
1521     default:
1522       break;
1523     }
1524   return expr;
1525 }
1526
1527 /* Simplify the binary expression RHS, and return the result if
1528    simplified. */
1529
1530 static tree
1531 simplify_binary_expression (tree stmt, tree rhs)
1532 {
1533   tree result = NULL_TREE;
1534   tree op0 = TREE_OPERAND (rhs, 0);
1535   tree op1 = TREE_OPERAND (rhs, 1);
1536
1537   /* This will not catch every single case we could combine, but will
1538      catch those with constants.  The goal here is to simultaneously
1539      combine constants between expressions, but avoid infinite
1540      expansion of expressions during simplification.  */
1541   if (TREE_CODE (op0) == SSA_NAME)
1542     {
1543       if (VN_INFO (op0)->has_constants)
1544         op0 = valueize_expr (VN_INFO (op0)->expr);
1545       else if (SSA_VAL (op0) != VN_TOP && SSA_VAL (op0) != op0)
1546         op0 = SSA_VAL (op0);
1547     }
1548
1549   if (TREE_CODE (op1) == SSA_NAME)
1550     {
1551       if (VN_INFO (op1)->has_constants)
1552         op1 = valueize_expr (VN_INFO (op1)->expr);
1553       else if (SSA_VAL (op1) != VN_TOP && SSA_VAL (op1) != op1)
1554         op1 = SSA_VAL (op1);
1555     }
1556
1557   /* Avoid folding if nothing changed.  */
1558   if (op0 == TREE_OPERAND (rhs, 0)
1559       && op1 == TREE_OPERAND (rhs, 1))
1560     return NULL_TREE;
1561
1562   fold_defer_overflow_warnings ();
1563
1564   result = fold_binary (TREE_CODE (rhs), TREE_TYPE (rhs), op0, op1);
1565
1566   fold_undefer_overflow_warnings (result && valid_gimple_expression_p (result),
1567                                   stmt, 0);
1568
1569   /* Make sure result is not a complex expression consisting
1570      of operators of operators (IE (a + b) + (a + c))
1571      Otherwise, we will end up with unbounded expressions if
1572      fold does anything at all.  */
1573   if (result && valid_gimple_expression_p (result))
1574     return result;
1575
1576   return NULL_TREE;
1577 }
1578
1579 /* Simplify the unary expression RHS, and return the result if
1580    simplified. */
1581
1582 static tree
1583 simplify_unary_expression (tree rhs)
1584 {
1585   tree result = NULL_TREE;
1586   tree op0 = TREE_OPERAND (rhs, 0);
1587
1588   if (TREE_CODE (op0) != SSA_NAME)
1589     return NULL_TREE;
1590
1591   if (VN_INFO (op0)->has_constants)
1592     op0 = valueize_expr (VN_INFO (op0)->expr);
1593   else if (CONVERT_EXPR_P (rhs)
1594            || TREE_CODE (rhs) == REALPART_EXPR
1595            || TREE_CODE (rhs) == IMAGPART_EXPR
1596            || TREE_CODE (rhs) == VIEW_CONVERT_EXPR)
1597     {
1598       /* We want to do tree-combining on conversion-like expressions.
1599          Make sure we feed only SSA_NAMEs or constants to fold though.  */
1600       tree tem = valueize_expr (VN_INFO (op0)->expr);
1601       if (UNARY_CLASS_P (tem)
1602           || BINARY_CLASS_P (tem)
1603           || TREE_CODE (tem) == VIEW_CONVERT_EXPR
1604           || TREE_CODE (tem) == SSA_NAME
1605           || is_gimple_min_invariant (tem))
1606         op0 = tem;
1607     }
1608
1609   /* Avoid folding if nothing changed, but remember the expression.  */
1610   if (op0 == TREE_OPERAND (rhs, 0))
1611     return rhs;
1612
1613   result = fold_unary (TREE_CODE (rhs), TREE_TYPE (rhs), op0);
1614   if (result)
1615     {
1616       STRIP_USELESS_TYPE_CONVERSION (result);
1617       if (valid_gimple_expression_p (result))
1618         return result;
1619     }
1620
1621   return rhs;
1622 }
1623
1624 /* Try to simplify RHS using equivalences and constant folding.  */
1625
1626 static tree
1627 try_to_simplify (tree stmt, tree rhs)
1628 {
1629   tree tem;
1630
1631   /* For stores we can end up simplifying a SSA_NAME rhs.  Just return
1632      in this case, there is no point in doing extra work.  */
1633   if (TREE_CODE (rhs) == SSA_NAME)
1634     return rhs;
1635
1636   switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
1637     {
1638     case tcc_declaration:
1639       tem = get_symbol_constant_value (rhs);
1640       if (tem)
1641         return tem;
1642       break;
1643
1644     case tcc_reference:
1645       /* Do not do full-blown reference lookup here, but simplify
1646          reads from constant aggregates.  */
1647       tem = fold_const_aggregate_ref (rhs);
1648       if (tem)
1649         return tem;
1650
1651       /* Fallthrough for some codes that can operate on registers.  */
1652       if (!(TREE_CODE (rhs) == REALPART_EXPR
1653             || TREE_CODE (rhs) == IMAGPART_EXPR
1654             || TREE_CODE (rhs) == VIEW_CONVERT_EXPR))
1655         break;
1656       /* We could do a little more with unary ops, if they expand
1657          into binary ops, but it's debatable whether it is worth it. */
1658     case tcc_unary:
1659       return simplify_unary_expression (rhs);
1660       break;
1661     case tcc_comparison:
1662     case tcc_binary:
1663       return simplify_binary_expression (stmt, rhs);
1664       break;
1665     default:
1666       break;
1667     }
1668
1669   return rhs;
1670 }
1671
1672 /* Visit and value number USE, return true if the value number
1673    changed. */
1674
1675 static bool
1676 visit_use (tree use)
1677 {
1678   bool changed = false;
1679   tree stmt = SSA_NAME_DEF_STMT (use);
1680   stmt_ann_t ann;
1681
1682   VN_INFO (use)->use_processed = true;
1683
1684   gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
1685   if (dump_file && (dump_flags & TDF_DETAILS)
1686       && !IS_EMPTY_STMT (stmt))
1687     {
1688       fprintf (dump_file, "Value numbering ");
1689       print_generic_expr (dump_file, use, 0);
1690       fprintf (dump_file, " stmt = ");
1691       print_generic_stmt (dump_file, stmt, 0);
1692     }
1693
1694   /* RETURN_EXPR may have an embedded MODIFY_STMT.  */
1695   if (TREE_CODE (stmt) == RETURN_EXPR
1696       && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
1697     stmt = TREE_OPERAND (stmt, 0);
1698
1699   ann = stmt_ann (stmt);
1700
1701   /* Handle uninitialized uses.  */
1702   if (IS_EMPTY_STMT (stmt))
1703     {
1704       changed = set_ssa_val_to (use, use);
1705     }
1706   else
1707     {
1708       if (TREE_CODE (stmt) == PHI_NODE)
1709         {
1710           changed = visit_phi (stmt);
1711         }
1712       else if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT
1713                || (ann && ann->has_volatile_ops)
1714                || tree_could_throw_p (stmt))
1715         {
1716           changed = defs_to_varying (stmt);
1717         }
1718       else
1719         {
1720           tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1721           tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1722           tree simplified;
1723
1724           STRIP_USELESS_TYPE_CONVERSION (rhs);
1725
1726           /* Shortcut for copies. Simplifying copies is pointless,
1727              since we copy the expression and value they represent.  */
1728           if (TREE_CODE (rhs) == SSA_NAME && TREE_CODE (lhs) == SSA_NAME)
1729             {
1730               changed = visit_copy (lhs, rhs);
1731               goto done;
1732             }
1733           simplified = try_to_simplify (stmt, rhs);
1734           if (simplified && simplified != rhs)
1735             {
1736               if (dump_file && (dump_flags & TDF_DETAILS))
1737                 {
1738                   fprintf (dump_file, "RHS ");
1739                   print_generic_expr (dump_file, rhs, 0);
1740                   fprintf (dump_file, " simplified to ");
1741                   print_generic_expr (dump_file, simplified, 0);
1742                   if (TREE_CODE (lhs) == SSA_NAME)
1743                     fprintf (dump_file, " has constants %d\n",
1744                              expr_has_constants (simplified));
1745                   else
1746                     fprintf (dump_file, "\n");
1747                 }
1748             }
1749           /* Setting value numbers to constants will occasionally
1750              screw up phi congruence because constants are not
1751              uniquely associated with a single ssa name that can be
1752              looked up.  */
1753           if (simplified && is_gimple_min_invariant (simplified)
1754               && TREE_CODE (lhs) == SSA_NAME
1755               && simplified != rhs)
1756             {
1757               VN_INFO (lhs)->expr = simplified;
1758               VN_INFO (lhs)->has_constants = true;
1759               changed = set_ssa_val_to (lhs, simplified);
1760               goto done;
1761             }
1762           else if (simplified && TREE_CODE (simplified) == SSA_NAME
1763                    && TREE_CODE (lhs) == SSA_NAME)
1764             {
1765               changed = visit_copy (lhs, simplified);
1766               goto done;
1767             }
1768           else if (simplified)
1769             {
1770               if (TREE_CODE (lhs) == SSA_NAME)
1771                 {
1772                   VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
1773                   /* We have to unshare the expression or else
1774                      valuizing may change the IL stream.  */
1775                   VN_INFO (lhs)->expr = unshare_expr (simplified);
1776                 }
1777               rhs = simplified;
1778             }
1779           else if (expr_has_constants (rhs) && TREE_CODE (lhs) == SSA_NAME)
1780             {
1781               VN_INFO (lhs)->has_constants = true;
1782               VN_INFO (lhs)->expr = unshare_expr (rhs);
1783             }
1784           else if (TREE_CODE (lhs) == SSA_NAME)
1785             {
1786               /* We reset expr and constantness here because we may
1787                  have been value numbering optimistically, and
1788                  iterating. They may become non-constant in this case,
1789                  even if they were optimistically constant. */
1790
1791               VN_INFO (lhs)->has_constants = false;
1792               VN_INFO (lhs)->expr = lhs;
1793             }
1794
1795           if (TREE_CODE (lhs) == SSA_NAME
1796               /* We can substitute SSA_NAMEs that are live over
1797                  abnormal edges with their constant value.  */
1798               && !is_gimple_min_invariant (rhs)
1799               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1800             changed = defs_to_varying (stmt);
1801           else if (REFERENCE_CLASS_P (lhs) || DECL_P (lhs))
1802             {
1803               changed = visit_reference_op_store (lhs, rhs, stmt);
1804             }
1805           else if (TREE_CODE (lhs) == SSA_NAME)
1806             {
1807               if (is_gimple_min_invariant (rhs))
1808                 {
1809                   VN_INFO (lhs)->has_constants = true;
1810                   VN_INFO (lhs)->expr = rhs;
1811                   changed = set_ssa_val_to (lhs, rhs);
1812                 }
1813               else
1814                 {
1815                   switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
1816                     {
1817                     case tcc_unary:
1818                       changed = visit_unary_op (lhs, rhs);
1819                       break;
1820                     case tcc_binary:
1821                       changed = visit_binary_op (lhs, rhs);
1822                       break;
1823                       /* If tcc_vl_expr ever encompasses more than
1824                          CALL_EXPR, this will need to be changed.  */
1825                     case tcc_vl_exp:
1826                       if (call_expr_flags (rhs)  & (ECF_PURE | ECF_CONST))
1827                         changed = visit_reference_op_load (lhs, rhs, stmt);
1828                       else
1829                         changed = defs_to_varying (stmt);
1830                       break;
1831                     case tcc_declaration:
1832                     case tcc_reference:
1833                       changed = visit_reference_op_load (lhs, rhs, stmt);
1834                       break;
1835                     case tcc_expression:
1836                       if (TREE_CODE (rhs) == ADDR_EXPR)
1837                         {
1838                           changed = visit_unary_op (lhs, rhs);
1839                           goto done;
1840                         }
1841                       /* Fallthrough.  */
1842                     default:
1843                       changed = defs_to_varying (stmt);
1844                       break;
1845                     }
1846                 }
1847             }
1848           else
1849             changed = defs_to_varying (stmt);
1850         }
1851     }
1852  done:
1853   return changed;
1854 }
1855
1856 /* Compare two operands by reverse postorder index */
1857
1858 static int
1859 compare_ops (const void *pa, const void *pb)
1860 {
1861   const tree opa = *((const tree *)pa);
1862   const tree opb = *((const tree *)pb);
1863   tree opstmta = SSA_NAME_DEF_STMT (opa);
1864   tree opstmtb = SSA_NAME_DEF_STMT (opb);
1865   basic_block bba;
1866   basic_block bbb;
1867
1868   if (IS_EMPTY_STMT (opstmta) && IS_EMPTY_STMT (opstmtb))
1869     return 0;
1870   else if (IS_EMPTY_STMT (opstmta))
1871     return -1;
1872   else if (IS_EMPTY_STMT (opstmtb))
1873     return 1;
1874
1875   bba = bb_for_stmt (opstmta);
1876   bbb = bb_for_stmt (opstmtb);
1877
1878   if (!bba && !bbb)
1879     return 0;
1880   else if (!bba)
1881     return -1;
1882   else if (!bbb)
1883     return 1;
1884
1885   if (bba == bbb)
1886     {
1887       if (TREE_CODE (opstmta) == PHI_NODE && TREE_CODE (opstmtb) == PHI_NODE)
1888         return 0;
1889       else if (TREE_CODE (opstmta) == PHI_NODE)
1890         return -1;
1891       else if (TREE_CODE (opstmtb) == PHI_NODE)
1892         return 1;
1893       return stmt_ann (opstmta)->uid - stmt_ann (opstmtb)->uid;
1894     }
1895   return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
1896 }
1897
1898 /* Sort an array containing members of a strongly connected component
1899    SCC so that the members are ordered by RPO number.
1900    This means that when the sort is complete, iterating through the
1901    array will give you the members in RPO order.  */
1902
1903 static void
1904 sort_scc (VEC (tree, heap) *scc)
1905 {
1906   qsort (VEC_address (tree, scc),
1907          VEC_length (tree, scc),
1908          sizeof (tree),
1909          compare_ops);
1910 }
1911
1912 /* Process a strongly connected component in the SSA graph.  */
1913
1914 static void
1915 process_scc (VEC (tree, heap) *scc)
1916 {
1917   /* If the SCC has a single member, just visit it.  */
1918
1919   if (VEC_length (tree, scc) == 1)
1920     {
1921       tree use = VEC_index (tree, scc, 0);
1922       if (!VN_INFO (use)->use_processed)
1923         visit_use (use);
1924     }
1925   else
1926     {
1927       tree var;
1928       unsigned int i;
1929       unsigned int iterations = 0;
1930       bool changed = true;
1931
1932       /* Iterate over the SCC with the optimistic table until it stops
1933          changing.  */
1934       current_info = optimistic_info;
1935       while (changed)
1936         {
1937           changed = false;
1938           iterations++;
1939           htab_empty (optimistic_info->nary);
1940           htab_empty (optimistic_info->phis);
1941           htab_empty (optimistic_info->references);
1942           obstack_free (&optimistic_info->nary_obstack, NULL);
1943           gcc_obstack_init (&optimistic_info->nary_obstack);
1944           empty_alloc_pool (optimistic_info->phis_pool);
1945           empty_alloc_pool (optimistic_info->references_pool);
1946           for (i = 0; VEC_iterate (tree, scc, i, var); i++)
1947             changed |= visit_use (var);
1948         }
1949
1950       if (dump_file && (dump_flags & TDF_STATS))
1951         fprintf (dump_file, "Processing SCC required %d iterations\n",
1952                  iterations);
1953
1954       /* Finally, visit the SCC once using the valid table.  */
1955       current_info = valid_info;
1956       for (i = 0; VEC_iterate (tree, scc, i, var); i++)
1957         visit_use (var);
1958     }
1959 }
1960
1961 /* Depth first search on NAME to discover and process SCC's in the SSA
1962    graph.
1963    Execution of this algorithm relies on the fact that the SCC's are
1964    popped off the stack in topological order.
1965    Returns true if successful, false if we stopped processing SCC's due
1966    to ressource constraints.  */
1967
1968 static bool
1969 DFS (tree name)
1970 {
1971   ssa_op_iter iter;
1972   use_operand_p usep;
1973   tree defstmt;
1974
1975   /* SCC info */
1976   VN_INFO (name)->dfsnum = next_dfs_num++;
1977   VN_INFO (name)->visited = true;
1978   VN_INFO (name)->low = VN_INFO (name)->dfsnum;
1979
1980   VEC_safe_push (tree, heap, sccstack, name);
1981   VN_INFO (name)->on_sccstack = true;
1982   defstmt = SSA_NAME_DEF_STMT (name);
1983
1984   /* Recursively DFS on our operands, looking for SCC's.  */
1985   if (!IS_EMPTY_STMT (defstmt))
1986     {
1987       FOR_EACH_PHI_OR_STMT_USE (usep, SSA_NAME_DEF_STMT (name), iter,
1988                                 SSA_OP_ALL_USES)
1989         {
1990           tree use = USE_FROM_PTR (usep);
1991
1992           /* Since we handle phi nodes, we will sometimes get
1993              invariants in the use expression.  */
1994           if (TREE_CODE (use) != SSA_NAME)
1995             continue;
1996
1997           if (! (VN_INFO (use)->visited))
1998             {
1999               if (!DFS (use))
2000                 return false;
2001               VN_INFO (name)->low = MIN (VN_INFO (name)->low,
2002                                          VN_INFO (use)->low);
2003             }
2004           if (VN_INFO (use)->dfsnum < VN_INFO (name)->dfsnum
2005               && VN_INFO (use)->on_sccstack)
2006             {
2007               VN_INFO (name)->low = MIN (VN_INFO (use)->dfsnum,
2008                                          VN_INFO (name)->low);
2009             }
2010         }
2011     }
2012
2013   /* See if we found an SCC.  */
2014   if (VN_INFO (name)->low == VN_INFO (name)->dfsnum)
2015     {
2016       VEC (tree, heap) *scc = NULL;
2017       tree x;
2018
2019       /* Found an SCC, pop the components off the SCC stack and
2020          process them.  */
2021       do
2022         {
2023           x = VEC_pop (tree, sccstack);
2024
2025           VN_INFO (x)->on_sccstack = false;
2026           VEC_safe_push (tree, heap, scc, x);
2027         } while (x != name);
2028
2029       /* Bail out of SCCVN in case a SCC turns out to be incredibly large.  */
2030       if (VEC_length (tree, scc)
2031             > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE))
2032         {
2033           if (dump_file)
2034             fprintf (dump_file, "WARNING: Giving up with SCCVN due to "
2035                      "SCC size %u exceeding %u\n", VEC_length (tree, scc),
2036                      (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE));
2037           return false;
2038         }
2039
2040       if (VEC_length (tree, scc) > 1)
2041         sort_scc (scc);
2042
2043       if (dump_file && (dump_flags & TDF_DETAILS))
2044         print_scc (dump_file, scc);
2045
2046       process_scc (scc);
2047
2048       VEC_free (tree, heap, scc);
2049     }
2050
2051   return true;
2052 }
2053
2054 /* Allocate a value number table.  */
2055
2056 static void
2057 allocate_vn_table (vn_tables_t table)
2058 {
2059   table->phis = htab_create (23, vn_phi_hash, vn_phi_eq, free_phi);
2060   table->nary = htab_create (23, vn_nary_op_hash, vn_nary_op_eq, NULL);
2061   table->references = htab_create (23, vn_reference_hash, vn_reference_eq,
2062                                    free_reference);
2063
2064   gcc_obstack_init (&table->nary_obstack);
2065   table->phis_pool = create_alloc_pool ("VN phis",
2066                                         sizeof (struct vn_phi_s),
2067                                         30);
2068   table->references_pool = create_alloc_pool ("VN references",
2069                                               sizeof (struct vn_reference_s),
2070                                               30);
2071 }
2072
2073 /* Free a value number table.  */
2074
2075 static void
2076 free_vn_table (vn_tables_t table)
2077 {
2078   htab_delete (table->phis);
2079   htab_delete (table->nary);
2080   htab_delete (table->references);
2081   obstack_free (&table->nary_obstack, NULL);
2082   free_alloc_pool (table->phis_pool);
2083   free_alloc_pool (table->references_pool);
2084 }
2085
2086 static void
2087 init_scc_vn (void)
2088 {
2089   size_t i;
2090   int j;
2091   int *rpo_numbers_temp;
2092   basic_block bb;
2093   size_t id = 0;
2094
2095   calculate_dominance_info (CDI_DOMINATORS);
2096   sccstack = NULL;
2097   next_dfs_num = 1;
2098
2099   vn_ssa_aux_table = VEC_alloc (vn_ssa_aux_t, heap, num_ssa_names + 1);
2100   /* VEC_alloc doesn't actually grow it to the right size, it just
2101      preallocates the space to do so.  */
2102   VEC_safe_grow (vn_ssa_aux_t, heap, vn_ssa_aux_table, num_ssa_names + 1);
2103   gcc_obstack_init (&vn_ssa_aux_obstack);
2104
2105   shared_lookup_phiargs = NULL;
2106   shared_lookup_vops = NULL;
2107   shared_lookup_references = NULL;
2108   rpo_numbers = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
2109   rpo_numbers_temp = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
2110   pre_and_rev_post_order_compute (NULL, rpo_numbers_temp, false);
2111
2112   /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
2113      the i'th block in RPO order is bb.  We want to map bb's to RPO
2114      numbers, so we need to rearrange this array.  */
2115   for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
2116     rpo_numbers[rpo_numbers_temp[j]] = j;
2117
2118   XDELETE (rpo_numbers_temp);
2119
2120   VN_TOP = create_tmp_var_raw (void_type_node, "vn_top");
2121
2122   /* Create the VN_INFO structures, and initialize value numbers to
2123      TOP.  */
2124   for (i = 0; i < num_ssa_names; i++)
2125     {
2126       tree name = ssa_name (i);
2127       if (name)
2128         {
2129           VN_INFO_GET (name)->valnum = VN_TOP;
2130           VN_INFO (name)->expr = name;
2131         }
2132     }
2133
2134   FOR_ALL_BB (bb)
2135     {
2136       block_stmt_iterator bsi;
2137       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2138         {
2139           tree stmt = bsi_stmt (bsi);
2140           stmt_ann (stmt)->uid = id++;
2141         }
2142     }
2143
2144   /* Create the valid and optimistic value numbering tables.  */
2145   valid_info = XCNEW (struct vn_tables_s);
2146   allocate_vn_table (valid_info);
2147   optimistic_info = XCNEW (struct vn_tables_s);
2148   allocate_vn_table (optimistic_info);
2149   pre_info = NULL;
2150 }
2151
2152 void
2153 switch_to_PRE_table (void)
2154 {
2155   pre_info = XCNEW (struct vn_tables_s);
2156   allocate_vn_table (pre_info);
2157   current_info = pre_info;
2158 }
2159
2160 void
2161 free_scc_vn (void)
2162 {
2163   size_t i;
2164
2165   VEC_free (tree, heap, shared_lookup_phiargs);
2166   VEC_free (tree, gc, shared_lookup_vops);
2167   VEC_free (vn_reference_op_s, heap, shared_lookup_references);
2168   XDELETEVEC (rpo_numbers);
2169
2170   for (i = 0; i < num_ssa_names; i++)
2171     {
2172       tree name = ssa_name (i);
2173       if (name
2174           && SSA_NAME_VALUE (name)
2175           && TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
2176         SSA_NAME_VALUE (name) = NULL;
2177       if (name
2178           && VN_INFO (name)->needs_insertion)
2179         release_ssa_name (name);
2180     }
2181   obstack_free (&vn_ssa_aux_obstack, NULL);
2182   VEC_free (vn_ssa_aux_t, heap, vn_ssa_aux_table);
2183
2184   VEC_free (tree, heap, sccstack);
2185   free_vn_table (valid_info);
2186   XDELETE (valid_info);
2187   free_vn_table (optimistic_info);
2188   XDELETE (optimistic_info);
2189   if (pre_info)
2190     {
2191       free_vn_table (pre_info);
2192       XDELETE (pre_info);
2193     }
2194 }
2195
2196 /* Do SCCVN.  Returns true if it finished, false if we bailed out
2197    due to ressource constraints.  */
2198
2199 bool
2200 run_scc_vn (bool may_insert_arg)
2201 {
2202   size_t i;
2203   tree param;
2204
2205   may_insert = may_insert_arg;
2206
2207   init_scc_vn ();
2208   current_info = valid_info;
2209
2210   for (param = DECL_ARGUMENTS (current_function_decl);
2211        param;
2212        param = TREE_CHAIN (param))
2213     {
2214       if (gimple_default_def (cfun, param) != NULL)
2215         {
2216           tree def = gimple_default_def (cfun, param);
2217           SSA_VAL (def) = def;
2218         }
2219     }
2220
2221   for (i = 1; i < num_ssa_names; ++i)
2222     {
2223       tree name = ssa_name (i);
2224       if (name
2225           && VN_INFO (name)->visited == false
2226           && !has_zero_uses (name))
2227         if (!DFS (name))
2228           {
2229             free_scc_vn ();
2230             may_insert = false;
2231             return false;
2232           }
2233     }
2234
2235   if (dump_file && (dump_flags & TDF_DETAILS))
2236     {
2237       fprintf (dump_file, "Value numbers:\n");
2238       for (i = 0; i < num_ssa_names; i++)
2239         {
2240           tree name = ssa_name (i);
2241           if (name && VN_INFO (name)->visited
2242               && (SSA_VAL (name) != name
2243                   || is_gimple_min_invariant (VN_INFO (name)->expr)))
2244             {
2245               print_generic_expr (dump_file, name, 0);
2246               fprintf (dump_file, " = ");
2247               if (is_gimple_min_invariant (VN_INFO (name)->expr))
2248                 print_generic_expr (dump_file, VN_INFO (name)->expr, 0);
2249               else
2250                 print_generic_expr (dump_file, SSA_VAL (name), 0);
2251               fprintf (dump_file, "\n");
2252             }
2253         }
2254     }
2255
2256   may_insert = false;
2257   return true;
2258 }