OSDN Git Service

2007-07-04 Daniel Berlin <dberlin@dberlin.org>
[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   /* The only thing we allow as value numbers are ssa_names and
1021      invariants.  So assert that here.  */
1022   gcc_assert (TREE_CODE (to) == SSA_NAME || is_gimple_min_invariant (to));
1023
1024   if (dump_file && (dump_flags & TDF_DETAILS))
1025     {
1026       fprintf (dump_file, "Setting value number of ");
1027       print_generic_expr (dump_file, from, 0);
1028       fprintf (dump_file, " to ");
1029       print_generic_expr (dump_file, to, 0);
1030       fprintf (dump_file, "\n");
1031     }
1032
1033   currval = SSA_VAL (from);
1034
1035   if (currval != to  && !operand_equal_p (currval, to, OEP_PURE_SAME))
1036     {
1037       SSA_VAL (from) = to;
1038       return true;
1039     }
1040   return false;
1041 }
1042
1043 /* Set all definitions in STMT to value number to themselves.
1044    Return true if a value number changed. */
1045
1046 static bool
1047 defs_to_varying (tree stmt)
1048 {
1049   bool changed = false;
1050   ssa_op_iter iter;
1051   def_operand_p defp;
1052
1053   FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
1054     {
1055       tree def = DEF_FROM_PTR (defp);
1056
1057       VN_INFO (def)->use_processed = true;
1058       changed |= set_ssa_val_to (def, def);
1059     }
1060   return changed;
1061 }
1062
1063 /* Visit a copy between LHS and RHS, return true if the value number
1064    changed.  */
1065
1066 static bool
1067 visit_copy (tree lhs, tree rhs)
1068 {
1069
1070   /* Follow chains of copies to their destination.  */
1071   while (SSA_VAL (rhs) != rhs && TREE_CODE (SSA_VAL (rhs)) == SSA_NAME)
1072     rhs = SSA_VAL (rhs);
1073   
1074   /* The copy may have a more interesting constant filled expression
1075      (we don't, since we know our RHS is just an SSA name).  */
1076   VN_INFO (lhs)->has_constants = VN_INFO (rhs)->has_constants;
1077   VN_INFO (lhs)->expr = VN_INFO (rhs)->expr;
1078
1079   return set_ssa_val_to (lhs, rhs);
1080 }
1081
1082 /* Visit a unary operator RHS, value number it, and return true if the
1083    value number of LHS has changed as a result.  */
1084
1085 static bool
1086 visit_unary_op (tree lhs, tree op)
1087 {
1088   bool changed = false;
1089   tree result = vn_unary_op_lookup (op);
1090
1091   if (result)
1092     {
1093       changed = set_ssa_val_to (lhs, result);
1094     }
1095   else
1096     {
1097       changed = set_ssa_val_to (lhs, lhs);
1098       vn_unary_op_insert (op, lhs);
1099     }
1100
1101   return changed;
1102 }
1103
1104 /* Visit a binary operator RHS, value number it, and return true if the
1105    value number of LHS has changed as a result.  */
1106
1107 static bool
1108 visit_binary_op (tree lhs, tree op)
1109 {
1110   bool changed = false;
1111   tree result = vn_binary_op_lookup (op);
1112
1113   if (result)
1114     {
1115       changed = set_ssa_val_to (lhs, result);
1116     }
1117   else
1118     {
1119       changed = set_ssa_val_to (lhs, lhs);
1120       vn_binary_op_insert (op, lhs);
1121     }
1122
1123   return changed;
1124 }
1125
1126 /* Visit a load from a reference operator RHS, part of STMT, value number it,
1127    and return true if the value number of the LHS has changed as a result.  */
1128
1129 static bool
1130 visit_reference_op_load (tree lhs, tree op, tree stmt)
1131 {
1132   bool changed = false;
1133   tree result = vn_reference_lookup (op, shared_vuses_from_stmt (stmt));
1134
1135   if (result)
1136     {
1137       changed = set_ssa_val_to (lhs, result);
1138     }
1139   else
1140     {
1141       changed = set_ssa_val_to (lhs, lhs);
1142       vn_reference_insert (op, lhs, copy_vuses_from_stmt (stmt));
1143     }
1144
1145   return changed;
1146 }
1147
1148
1149 /* Visit a store to a reference operator LHS, part of STMT, value number it,
1150    and return true if the value number of the LHS has changed as a result.  */
1151
1152 static bool
1153 visit_reference_op_store (tree lhs, tree op, tree stmt)
1154 {
1155   bool changed = false;
1156   tree result;
1157   bool resultsame = false;
1158
1159   /* First we want to lookup using the *vuses* from the store and see
1160      if there the last store to this location with the same address
1161      had the same value.
1162
1163      The vuses represent the memory state before the store.  If the
1164      memory state, address, and value of the store is the same as the
1165      last store to this location, then this store will produce the
1166      same memory state as that store.
1167
1168      In this case the vdef versions for this store are value numbered to those
1169      vuse versions, since they represent the same memory state after
1170      this store.
1171
1172      Otherwise, the vdefs for the store are used when inserting into
1173      the table, since the store generates a new memory state.  */
1174
1175   result = vn_reference_lookup (lhs, shared_vuses_from_stmt (stmt));
1176
1177   if (result)
1178     {
1179       if (TREE_CODE (result) == SSA_NAME)
1180         result = SSA_VAL (result);
1181       resultsame = expressions_equal_p (result, op);
1182     }
1183
1184   if (!result || !resultsame)
1185     {
1186       VEC(tree, gc) *vdefs = copy_vdefs_from_stmt (stmt);
1187       int i;
1188       tree vdef;
1189
1190       if (dump_file && (dump_flags & TDF_DETAILS))
1191         {
1192           fprintf (dump_file, "No store match\n");
1193           fprintf (dump_file, "Value numbering store ");
1194           print_generic_expr (dump_file, lhs, 0);
1195           fprintf (dump_file, " to ");
1196           print_generic_expr (dump_file, op, 0);
1197           fprintf (dump_file, "\n");
1198         }
1199       /* Have to set value numbers before insert, since insert is
1200          going to valueize the references in-place.  */
1201       for (i = 0; VEC_iterate (tree, vdefs, i, vdef); i++)
1202         {
1203           VN_INFO (vdef)->use_processed = true;
1204           changed |= set_ssa_val_to (vdef, vdef);
1205         }
1206
1207       vn_reference_insert (lhs, op, vdefs);
1208     }
1209   else
1210     {
1211       /* We had a match, so value number the vdefs to have the value
1212          number of the vuses they came from.  */
1213       ssa_op_iter op_iter;
1214       def_operand_p var;
1215       vuse_vec_p vv;
1216
1217       if (dump_file && (dump_flags & TDF_DETAILS))
1218         fprintf (dump_file, "Store matched earlier value,"
1219                  "value numbering store vdefs to matching vuses.\n");
1220
1221       FOR_EACH_SSA_VDEF_OPERAND (var, vv, stmt, op_iter)
1222         {
1223           tree def = DEF_FROM_PTR (var);
1224           tree use;
1225
1226           /* Uh, if the vuse is a multiuse, we can't really do much
1227              here, sadly, since we don't know which value number of
1228              which vuse to use.  */
1229           if (VUSE_VECT_NUM_ELEM (*vv) != 1)
1230             use = def;
1231           else
1232             use = VUSE_ELEMENT_VAR (*vv, 0);
1233
1234           VN_INFO (def)->use_processed = true;
1235           changed |= set_ssa_val_to (def, SSA_VAL (use));
1236         }
1237     }
1238
1239   return changed;
1240 }
1241
1242 /* Visit and value number PHI, return true if the value number
1243    changed.  */
1244
1245 static bool
1246 visit_phi (tree phi)
1247 {
1248   bool changed = false;
1249   tree result;
1250   tree sameval = VN_TOP;
1251   bool allsame = true;
1252   int i;
1253
1254   /* See if all non-TOP arguments have the same value.  TOP is
1255      equivalent to everything, so we can ignore it.  */
1256   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1257     {
1258       tree def = PHI_ARG_DEF (phi, i);
1259
1260       if (TREE_CODE (def) == SSA_NAME)
1261         def = SSA_VAL (def);
1262       if (def == VN_TOP)
1263         continue;
1264       if (sameval == VN_TOP)
1265         {
1266           sameval = def;
1267         }
1268       else
1269         {
1270           if (!expressions_equal_p (def, sameval))
1271             {
1272               allsame = false;
1273               break;
1274             }
1275         }
1276     }
1277
1278   /* If all value numbered to the same value, the phi node has that
1279      value.  */
1280   if (allsame)
1281     {
1282       if (is_gimple_min_invariant (sameval))
1283         {
1284           VN_INFO (PHI_RESULT (phi))->has_constants = true;
1285           VN_INFO (PHI_RESULT (phi))->expr = sameval;
1286         }
1287       else
1288         {
1289           VN_INFO (PHI_RESULT (phi))->has_constants = false;
1290           VN_INFO (PHI_RESULT (phi))->expr = sameval;
1291         }
1292       
1293       if (TREE_CODE (sameval) == SSA_NAME)
1294         return visit_copy (PHI_RESULT (phi), sameval);
1295       
1296       return set_ssa_val_to (PHI_RESULT (phi), sameval);
1297     }
1298
1299   /* Otherwise, see if it is equivalent to a phi node in this block.  */
1300   result = vn_phi_lookup (phi);
1301   if (result)
1302     {
1303       if (TREE_CODE (result) == SSA_NAME)
1304         changed = visit_copy (PHI_RESULT (phi), result);
1305       else
1306         changed = set_ssa_val_to (PHI_RESULT (phi), result);
1307     }
1308   else
1309     {
1310       vn_phi_insert (phi, PHI_RESULT (phi));
1311       VN_INFO (PHI_RESULT (phi))->has_constants = false;
1312       VN_INFO (PHI_RESULT (phi))->expr = PHI_RESULT (phi);
1313       changed = set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
1314     }
1315
1316   return changed;
1317 }
1318
1319 /* Return true if EXPR contains constants.  */
1320
1321 static bool
1322 expr_has_constants (tree expr)
1323 {
1324   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1325     {
1326     case tcc_unary:
1327       return is_gimple_min_invariant (TREE_OPERAND (expr, 0));
1328
1329     case tcc_binary:
1330       return is_gimple_min_invariant (TREE_OPERAND (expr, 0))
1331         || is_gimple_min_invariant (TREE_OPERAND (expr, 1));
1332       /* Constants inside reference ops are rarely interesting, but
1333          it can take a lot of looking to find them.  */
1334     case tcc_reference:
1335       return false;
1336     default:
1337       return is_gimple_min_invariant (expr);
1338     }
1339   return false;
1340 }
1341
1342 /* Replace SSA_NAMES in expr with their value numbers, and return the
1343    result.
1344    This is performed in place. */
1345
1346 static tree
1347 valueize_expr (tree expr)
1348 {
1349   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1350     {
1351     case tcc_unary:
1352       if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
1353           && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
1354         TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
1355       break;
1356     case tcc_binary:
1357       if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
1358           && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
1359         TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
1360       if (TREE_CODE (TREE_OPERAND (expr, 1)) == SSA_NAME
1361           && SSA_VAL (TREE_OPERAND (expr, 1)) != VN_TOP)
1362         TREE_OPERAND (expr, 1) = SSA_VAL (TREE_OPERAND (expr, 1));
1363       break;
1364     default:
1365       break;
1366     }
1367   return expr;
1368 }
1369
1370 /* Simplify the binary expression RHS, and return the result if
1371    simplified. */
1372
1373 static tree
1374 simplify_binary_expression (tree rhs)
1375 {
1376   tree result = NULL_TREE;
1377   tree op0 = TREE_OPERAND (rhs, 0);
1378   tree op1 = TREE_OPERAND (rhs, 1);
1379
1380   /* This will not catch every single case we could combine, but will
1381      catch those with constants.  The goal here is to simultaneously
1382      combine constants between expressions, but avoid infinite
1383      expansion of expressions during simplification.  */
1384   if (TREE_CODE (op0) == SSA_NAME)
1385     {
1386       if (VN_INFO (op0)->has_constants)
1387         op0 = valueize_expr (VN_INFO (op0)->expr);
1388       else if (SSA_VAL (op0) != VN_TOP && SSA_VAL (op0) != op0)
1389         op0 = VN_INFO (op0)->valnum;      
1390     }
1391
1392   if (TREE_CODE (op1) == SSA_NAME)
1393     {
1394       if (VN_INFO (op1)->has_constants)
1395         op1 = valueize_expr (VN_INFO (op1)->expr);
1396       else if (SSA_VAL (op1) != VN_TOP && SSA_VAL (op1) != op1)
1397         op1 = VN_INFO (op1)->valnum;
1398     }
1399   result = fold_binary (TREE_CODE (rhs), TREE_TYPE (rhs), op0, op1);
1400
1401   /* Make sure result is not a complex expression consiting
1402      of operators of operators (IE (a + b) + (a + c))
1403      Otherwise, we will end up with unbounded expressions if
1404      fold does anything at all.  */
1405   if (result)
1406     {
1407       if (is_gimple_min_invariant (result))
1408         return result;
1409       else if (SSA_VAR_P (result))
1410         return result;
1411       else if (EXPR_P (result))
1412         {
1413           switch (TREE_CODE_CLASS (TREE_CODE (result)))
1414             {
1415             case tcc_unary:
1416               {
1417                 tree op0 = TREE_OPERAND (result, 0);
1418                 if (!EXPR_P (op0))
1419                   return result;
1420               }
1421               break;
1422             case tcc_binary:
1423               {
1424                 tree op0 = TREE_OPERAND (result, 0);
1425                 tree op1 = TREE_OPERAND (result, 1);
1426                 if (!EXPR_P (op0) && !EXPR_P (op1))
1427                   return result;
1428               }
1429               break;
1430             default:
1431               break;
1432             }
1433         }
1434     }
1435   return NULL_TREE;
1436 }
1437
1438 /* Try to simplify RHS using equivalences and constant folding.  */
1439
1440 static tree
1441 try_to_simplify (tree stmt, tree rhs)
1442 {
1443   if (TREE_CODE (rhs) == SSA_NAME)
1444     {
1445       if (is_gimple_min_invariant (SSA_VAL (rhs)))
1446         return SSA_VAL (rhs);
1447       else if (VN_INFO (rhs)->has_constants)
1448         return VN_INFO (rhs)->expr;
1449     }
1450   else
1451     {
1452       switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
1453         {
1454           /* For references, see if we find a result for the lookup,
1455              and use it if we do.  */
1456
1457         case tcc_reference:
1458           {
1459             tree result = vn_reference_lookup (rhs,
1460                                                shared_vuses_from_stmt (stmt));
1461             if (result)
1462               return result;
1463           }
1464           break;
1465           /* We could do a little more with unary ops, if they expand
1466              into binary ops, but it's debatable whether it is worth it. */
1467         case tcc_unary:
1468           {
1469             tree result = NULL_TREE;
1470             tree op0 = TREE_OPERAND (rhs, 0);
1471             if (TREE_CODE (op0) == SSA_NAME && VN_INFO (op0)->has_constants)
1472               op0 = VN_INFO (op0)->expr;
1473             else if (TREE_CODE (op0) == SSA_NAME && SSA_VAL (op0) != op0)
1474               op0 = SSA_VAL (op0);
1475             result = fold_unary (TREE_CODE (rhs), TREE_TYPE (rhs), op0);
1476             if (result)
1477               return result;
1478           }
1479           break;
1480         case tcc_comparison:
1481         case tcc_binary:
1482           return simplify_binary_expression (rhs);
1483           break;
1484         default:
1485           break;
1486         }
1487     }
1488   return rhs;
1489 }
1490
1491 /* Visit and value number USE, return true if the value number
1492    changed. */
1493
1494 static bool
1495 visit_use (tree use)
1496 {
1497   bool changed = false;
1498   tree stmt = SSA_NAME_DEF_STMT (use);
1499   stmt_ann_t ann;
1500
1501   VN_INFO (use)->use_processed = true;
1502
1503   gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
1504   if (dump_file && (dump_flags & TDF_DETAILS))
1505     {
1506       fprintf (dump_file, "Value numbering ");
1507       print_generic_expr (dump_file, use, 0);
1508       fprintf (dump_file, " stmt = ");
1509       print_generic_stmt (dump_file, stmt, 0);
1510     }
1511
1512   /* RETURN_EXPR may have an embedded MODIFY_STMT.  */
1513   if (TREE_CODE (stmt) == RETURN_EXPR
1514       && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
1515     stmt = TREE_OPERAND (stmt, 0);
1516
1517   ann = stmt_ann (stmt);
1518
1519   /* Handle uninitialized uses.  */
1520   if (IS_EMPTY_STMT (stmt))
1521     {
1522       changed = set_ssa_val_to (use, use);
1523     }
1524   else
1525     {
1526       if (TREE_CODE (stmt) == PHI_NODE)
1527         {
1528           changed = visit_phi (stmt);
1529         }
1530       else if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT
1531                || (ann && ann->has_volatile_ops))
1532         {
1533           changed = defs_to_varying (stmt);
1534         }
1535       else
1536         {
1537           tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1538           tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1539           tree simplified;
1540
1541           STRIP_USELESS_TYPE_CONVERSION (rhs);
1542
1543           /* Shortcut for copies. Simplifying copies is pointless,
1544              since we copy the expression and value they represent.  */
1545           if (TREE_CODE (rhs) == SSA_NAME && TREE_CODE (lhs) == SSA_NAME)
1546             {
1547               changed = visit_copy (lhs, rhs);
1548               goto done;
1549             }
1550           simplified = try_to_simplify (stmt, rhs);
1551           if (simplified && simplified != rhs)
1552             {
1553               if (dump_file && (dump_flags & TDF_DETAILS))
1554                 {
1555                   fprintf (dump_file, "RHS ");
1556                   print_generic_expr (dump_file, rhs, 0);
1557                   fprintf (dump_file, " simplified to ");
1558                   print_generic_expr (dump_file, simplified, 0);
1559                   if (TREE_CODE (lhs) == SSA_NAME)
1560                     fprintf (dump_file, " has constants %d\n",
1561                              VN_INFO (lhs)->has_constants);
1562                   else
1563                     fprintf (dump_file, "\n");
1564
1565                 }
1566             }
1567           /* Setting value numbers to constants will occasionally
1568              screw up phi congruence because constants are not
1569              uniquely associated with a single ssa name that can be
1570              looked up.  */
1571           if (simplified && is_gimple_min_invariant (simplified)
1572               && TREE_CODE (lhs) == SSA_NAME
1573               && simplified != rhs)
1574             {
1575               VN_INFO (lhs)->expr = simplified;
1576               VN_INFO (lhs)->has_constants = true;
1577               changed = set_ssa_val_to (lhs, simplified);
1578               goto done;
1579             }
1580           else if (simplified && TREE_CODE (simplified) == SSA_NAME
1581                    && TREE_CODE (lhs) == SSA_NAME)
1582             {
1583               changed = visit_copy (lhs, simplified);
1584               goto done;
1585             }
1586           else if (simplified)
1587             {
1588               if (TREE_CODE (lhs) == SSA_NAME)
1589                 {
1590                   VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
1591                   /* We have to unshare the expression or else
1592                      valuizing may change the IL stream.  */
1593                   VN_INFO (lhs)->expr = unshare_expr (simplified);
1594                 }
1595               rhs = simplified;
1596             }
1597           else if (expr_has_constants (rhs) && TREE_CODE (lhs) == SSA_NAME)
1598             {
1599               VN_INFO (lhs)->has_constants = true;
1600               VN_INFO (lhs)->expr = unshare_expr (rhs);
1601             }
1602           else if (TREE_CODE (lhs) == SSA_NAME)
1603             {
1604               /* We reset expr and constantness here because we may
1605                  have been value numbering optimistically, and
1606                  iterating. They may become non-constant in this case,
1607                  even if they were optimistically constant. */
1608                  
1609               VN_INFO (lhs)->has_constants = false;
1610               VN_INFO (lhs)->expr = lhs;
1611             }
1612
1613           if (TREE_CODE (lhs) == SSA_NAME
1614               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1615             changed = defs_to_varying (stmt);
1616           else if (REFERENCE_CLASS_P (lhs))
1617             {
1618               changed = visit_reference_op_store (lhs, rhs, stmt);
1619             }
1620           else if (TREE_CODE (lhs) == SSA_NAME)
1621             {
1622               if (is_gimple_min_invariant (rhs))
1623                 {
1624                   VN_INFO (lhs)->has_constants = true;
1625                   VN_INFO (lhs)->expr = rhs;
1626                   changed = set_ssa_val_to (lhs, rhs);
1627                 }
1628               else
1629                 {
1630                   switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
1631                     {
1632                     case tcc_unary:
1633                       changed = visit_unary_op (lhs, rhs);
1634                       break;
1635                     case tcc_binary:
1636                       changed = visit_binary_op (lhs, rhs);
1637                       break;
1638                       /* If tcc_vl_expr ever encompasses more than
1639                          CALL_EXPR, this will need to be changed.  */
1640                     case tcc_vl_exp:
1641                       if (call_expr_flags (rhs)  & (ECF_PURE | ECF_CONST))
1642                         changed = visit_reference_op_load (lhs, rhs, stmt);
1643                       else
1644                         changed = defs_to_varying (stmt);
1645                       break;
1646                     case tcc_declaration:
1647                     case tcc_reference:
1648                       changed = visit_reference_op_load (lhs, rhs, stmt);
1649                       break;
1650                     case tcc_expression:
1651                       if (TREE_CODE (rhs) == ADDR_EXPR)
1652                         {
1653                           changed = visit_unary_op (lhs, rhs);
1654                           goto done;
1655                         }
1656                       /* Fallthrough.  */
1657                     default:
1658                       changed = defs_to_varying (stmt);
1659                       break;
1660                     }
1661                 }
1662             }
1663           else
1664             changed = defs_to_varying (stmt);
1665         }
1666     }
1667  done:
1668   return changed;
1669 }
1670
1671 /* Compare two operands by reverse postorder index */
1672
1673 static int
1674 compare_ops (const void *pa, const void *pb)
1675 {
1676   const tree opa = *((const tree *)pa);
1677   const tree opb = *((const tree *)pb);
1678   tree opstmta = SSA_NAME_DEF_STMT (opa);
1679   tree opstmtb = SSA_NAME_DEF_STMT (opb);
1680   basic_block bba;
1681   basic_block bbb;
1682
1683   if (IS_EMPTY_STMT (opstmta) && IS_EMPTY_STMT (opstmtb))
1684     return 0;
1685   else if (IS_EMPTY_STMT (opstmta))
1686     return -1;
1687   else if (IS_EMPTY_STMT (opstmtb))
1688     return 1;
1689
1690   bba = bb_for_stmt (opstmta);
1691   bbb = bb_for_stmt (opstmtb);
1692
1693   if (!bba && !bbb)
1694     return 0;
1695   else if (!bba)
1696     return -1;
1697   else if (!bbb)
1698     return 1;
1699
1700   if (bba == bbb)
1701     {
1702       if (TREE_CODE (opstmta) == PHI_NODE && TREE_CODE (opstmtb) == PHI_NODE)
1703         return 0;
1704       else if (TREE_CODE (opstmta) == PHI_NODE)
1705         return -1;
1706       else if (TREE_CODE (opstmtb) == PHI_NODE)
1707         return 1;
1708       return stmt_ann (opstmta)->uid - stmt_ann (opstmtb)->uid;
1709     }
1710   return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
1711 }
1712
1713 /* Sort an array containing members of a strongly connected component
1714    SCC so that the members are ordered by RPO number.
1715    This means that when the sort is complete, iterating through the
1716    array will give you the members in RPO order.  */
1717
1718 static void
1719 sort_scc (VEC (tree, heap) *scc)
1720 {
1721   qsort (VEC_address (tree, scc),
1722          VEC_length (tree, scc),
1723          sizeof (tree),
1724          compare_ops);
1725 }
1726
1727 /* Process a strongly connected component in the SSA graph.  */
1728
1729 static void
1730 process_scc (VEC (tree, heap) *scc)
1731 {
1732   /* If the SCC has a single member, just visit it.  */
1733
1734   if (VEC_length (tree, scc) == 1)
1735     {
1736       tree use = VEC_index (tree, scc, 0);
1737       if (!VN_INFO (use)->use_processed) 
1738         visit_use (use);
1739     }
1740   else
1741     {
1742       tree var;
1743       unsigned int i;
1744       unsigned int iterations = 0;
1745       bool changed = true;
1746
1747       /* Iterate over the SCC with the optimistic table until it stops
1748          changing.  */
1749       current_info = optimistic_info;
1750       while (changed)
1751         {
1752           changed = false;
1753           iterations++;
1754           for (i = 0; VEC_iterate (tree, scc, i, var); i++)
1755             changed |= visit_use (var);
1756         }
1757
1758       if (dump_file && (dump_flags & TDF_STATS))
1759         fprintf (dump_file, "Processing SCC required %d iterations\n",
1760                  iterations);
1761
1762       /* Finally, visit the SCC once using the valid table.  */
1763       current_info = valid_info;
1764       for (i = 0; VEC_iterate (tree, scc, i, var); i++)
1765         visit_use (var);
1766     }
1767 }
1768
1769 /* Depth first search on NAME to discover and process SCC's in the SSA
1770    graph.
1771    Execution of this algorithm relies on the fact that the SCC's are
1772    popped off the stack in topological order.  */
1773
1774 static void
1775 DFS (tree name)
1776 {
1777   ssa_op_iter iter;
1778   use_operand_p usep;
1779   tree defstmt;
1780
1781   /* SCC info */
1782   VN_INFO (name)->dfsnum = next_dfs_num++;
1783   VN_INFO (name)->visited = true;
1784   VN_INFO (name)->low = VN_INFO (name)->dfsnum;
1785
1786   VEC_safe_push (tree, heap, sccstack, name);
1787   VN_INFO (name)->on_sccstack = true;
1788   defstmt = SSA_NAME_DEF_STMT (name);
1789
1790   /* Recursively DFS on our operands, looking for SCC's.  */
1791   if (!IS_EMPTY_STMT (defstmt))
1792     {
1793       FOR_EACH_PHI_OR_STMT_USE (usep, SSA_NAME_DEF_STMT (name), iter,
1794                                 SSA_OP_ALL_USES)
1795         {
1796           tree use = USE_FROM_PTR (usep);
1797
1798           /* Since we handle phi nodes, we will sometimes get
1799              invariants in the use expression.  */
1800           if (TREE_CODE (use) != SSA_NAME)
1801             continue;
1802
1803           if (! (VN_INFO (use)->visited))
1804             {
1805               DFS (use);
1806               VN_INFO (name)->low = MIN (VN_INFO (name)->low,
1807                                          VN_INFO (use)->low);
1808             }
1809           if (VN_INFO (use)->dfsnum < VN_INFO (name)->dfsnum
1810               && VN_INFO (use)->on_sccstack)
1811             {
1812               VN_INFO (name)->low = MIN (VN_INFO (use)->dfsnum,
1813                                          VN_INFO (name)->low);
1814             }
1815         }
1816     }
1817
1818   /* See if we found an SCC.  */
1819   if (VN_INFO (name)->low == VN_INFO (name)->dfsnum)
1820     {
1821       VEC (tree, heap) *scc = NULL;
1822       tree x;
1823
1824       /* Found an SCC, pop the components off the SCC stack and
1825          process them.  */
1826       do
1827         {
1828           x = VEC_pop (tree, sccstack);
1829
1830           VN_INFO (x)->on_sccstack = false;
1831           VEC_safe_push (tree, heap, scc, x);
1832         } while (x != name);
1833
1834       if (VEC_length (tree, scc) > 1)
1835         sort_scc (scc);
1836
1837       if (dump_file && (dump_flags & TDF_DETAILS))
1838         print_scc (dump_file, scc);
1839
1840       process_scc (scc);
1841
1842       VEC_free (tree, heap, scc);
1843     }
1844 }
1845
1846 static void
1847 free_phi (void *vp)
1848 {
1849   vn_phi_t phi = vp;
1850   VEC_free (tree, heap, phi->phiargs);
1851 }
1852
1853
1854 /* Free a reference operation structure VP.  */
1855
1856 static void
1857 free_reference (void *vp)
1858 {
1859   vn_reference_t vr = vp;
1860   VEC_free (vn_reference_op_s, heap, vr->operands);
1861 }
1862
1863 /* Allocate a value number table.  */
1864
1865 static void
1866 allocate_vn_table (vn_tables_t table)
1867 {
1868   table->phis = htab_create (23, vn_phi_hash, vn_phi_eq, free_phi);
1869   table->unary = htab_create (23, vn_unary_op_hash, vn_unary_op_eq, NULL);
1870   table->binary = htab_create (23, vn_binary_op_hash, vn_binary_op_eq, NULL);
1871   table->references = htab_create (23, vn_reference_hash, vn_reference_eq,
1872                                    free_reference);
1873
1874   table->unary_op_pool = create_alloc_pool ("VN unary operations",
1875                                             sizeof (struct vn_unary_op_s),
1876                                             30);
1877   table->binary_op_pool = create_alloc_pool ("VN binary operations",
1878                                              sizeof (struct vn_binary_op_s),
1879                                              30);
1880   table->phis_pool = create_alloc_pool ("VN phis",
1881                                         sizeof (struct vn_phi_s),
1882                                         30);
1883   table->references_pool = create_alloc_pool ("VN references",
1884                                               sizeof (struct vn_reference_s),
1885                                               30);
1886 }
1887
1888 /* Free a value number table.  */
1889
1890 static void
1891 free_vn_table (vn_tables_t table)
1892 {
1893   htab_delete (table->phis);
1894   htab_delete (table->unary);
1895   htab_delete (table->binary);
1896   htab_delete (table->references);
1897   free_alloc_pool (table->unary_op_pool);
1898   free_alloc_pool (table->binary_op_pool);
1899   free_alloc_pool (table->phis_pool);
1900   free_alloc_pool (table->references_pool);
1901 }
1902
1903 static void
1904 init_scc_vn (void)
1905 {
1906   size_t i;
1907   int j;
1908   int *rpo_numbers_temp;
1909   basic_block bb;
1910   size_t id = 0;
1911
1912   calculate_dominance_info (CDI_DOMINATORS);
1913   sccstack = NULL;
1914   next_dfs_num = 1;
1915
1916   vn_ssa_aux_table = VEC_alloc (vn_ssa_aux_t, heap, num_ssa_names + 1);
1917   /* VEC_alloc doesn't actually grow it to the right size, it just
1918      preallocates the space to do so.  */
1919   VEC_safe_grow (vn_ssa_aux_t, heap, vn_ssa_aux_table, num_ssa_names + 1);
1920   shared_lookup_phiargs = NULL;
1921   shared_lookup_vops = NULL;
1922   shared_lookup_references = NULL;
1923   rpo_numbers = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
1924   rpo_numbers_temp = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
1925   pre_and_rev_post_order_compute (NULL, rpo_numbers_temp, false);
1926
1927   /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
1928      the i'th block in RPO order is bb.  We want to map bb's to RPO
1929      numbers, so we need to rearrange this array.  */
1930   for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
1931     rpo_numbers[rpo_numbers_temp[j]] = j;
1932
1933   free (rpo_numbers_temp);
1934
1935   VN_TOP = create_tmp_var_raw (void_type_node, "vn_top");
1936
1937   /* Create the VN_INFO structures, and initialize value numbers to
1938      TOP.  */
1939   for (i = 0; i < num_ssa_names; i++)
1940     {
1941       tree name = ssa_name (i);
1942       if (name)
1943         {
1944           VN_INFO_GET (name)->valnum = VN_TOP;
1945           VN_INFO (name)->expr = name;
1946         }
1947     }
1948
1949   FOR_ALL_BB (bb)
1950     {
1951       block_stmt_iterator bsi;
1952       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1953         {
1954           tree stmt = bsi_stmt (bsi);
1955           stmt_ann (stmt)->uid = id++;
1956         }
1957     }
1958
1959   /* Create the valid and optimistic value numbering tables.  */
1960   valid_info = XCNEW (struct vn_tables_s);
1961   allocate_vn_table (valid_info);
1962   optimistic_info = XCNEW (struct vn_tables_s);
1963   allocate_vn_table (optimistic_info);
1964   pre_info = NULL;
1965 }
1966
1967 void
1968 switch_to_PRE_table (void)
1969 {
1970   pre_info = XCNEW (struct vn_tables_s);
1971   allocate_vn_table (pre_info);
1972   current_info = pre_info;
1973 }
1974
1975 void
1976 free_scc_vn (void)
1977 {
1978   size_t i;
1979
1980   VEC_free (tree, heap, shared_lookup_phiargs);
1981   VEC_free (tree, gc, shared_lookup_vops);
1982   VEC_free (vn_reference_op_s, heap, shared_lookup_references);
1983   XDELETEVEC (rpo_numbers);
1984   for (i = 0; i < num_ssa_names; i++)
1985     {
1986       tree name = ssa_name (i);
1987       if (name)
1988         {
1989           XDELETE (VN_INFO (name));
1990           if (SSA_NAME_VALUE (name) &&
1991               TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
1992             SSA_NAME_VALUE (name) = NULL;
1993         }
1994     }
1995       
1996   VEC_free (vn_ssa_aux_t, heap, vn_ssa_aux_table);
1997   VEC_free (tree, heap, sccstack);
1998   free_vn_table (valid_info);
1999   XDELETE (valid_info);
2000   free_vn_table (optimistic_info);
2001   XDELETE (optimistic_info);
2002   if (pre_info)
2003     {
2004       free_vn_table (pre_info);
2005       XDELETE (pre_info);
2006     }
2007 }
2008
2009 void
2010 run_scc_vn (void)
2011 {
2012   size_t i;
2013   tree param;
2014
2015   init_scc_vn ();
2016   current_info = valid_info;
2017
2018   for (param = DECL_ARGUMENTS (current_function_decl);
2019        param;
2020        param = TREE_CHAIN (param))
2021     {
2022       if (gimple_default_def (cfun, param) != NULL)
2023         {
2024           tree def = gimple_default_def (cfun, param);
2025           SSA_VAL (def) = def;
2026         }
2027     }
2028
2029   for (i = num_ssa_names - 1; i > 0; i--)
2030     {
2031       tree name = ssa_name (i);
2032       if (name
2033           && VN_INFO (name)->visited == false
2034           && !has_zero_uses (name))
2035         DFS (name);
2036     }
2037
2038   if (dump_file && (dump_flags & TDF_DETAILS))
2039     {
2040       fprintf (dump_file, "Value numbers:\n");
2041       for (i = 0; i < num_ssa_names; i++)
2042         {
2043           tree name = ssa_name (i);
2044           if (name && VN_INFO (name)->visited
2045               && (SSA_VAL (name) != name
2046                   || is_gimple_min_invariant (VN_INFO (name)->expr)))
2047             {
2048               print_generic_expr (dump_file, name, 0);
2049               fprintf (dump_file, " = ");
2050               if (is_gimple_min_invariant (VN_INFO (name)->expr))
2051                 print_generic_expr (dump_file, VN_INFO (name)->expr, 0);
2052               else
2053                 print_generic_expr (dump_file, SSA_VAL (name), 0);
2054               fprintf (dump_file, "\n");
2055             }
2056         }
2057     }
2058 }