OSDN Git Service

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