gcc/
[official-gcc.git] / gcc / tree-ssa-sccvn.c
blobe2b36a63930b9983eb890ae853744b0482f51615
1 /* SCC value numbering for trees
2 Copyright (C) 2006-2015 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "alias.h"
26 #include "symtab.h"
27 #include "tree.h"
28 #include "fold-const.h"
29 #include "stor-layout.h"
30 #include "predict.h"
31 #include "hard-reg-set.h"
32 #include "function.h"
33 #include "dominance.h"
34 #include "cfg.h"
35 #include "cfganal.h"
36 #include "basic-block.h"
37 #include "gimple-pretty-print.h"
38 #include "tree-inline.h"
39 #include "tree-ssa-alias.h"
40 #include "internal-fn.h"
41 #include "gimple-fold.h"
42 #include "tree-eh.h"
43 #include "gimple-expr.h"
44 #include "gimple.h"
45 #include "gimplify.h"
46 #include "gimple-ssa.h"
47 #include "tree-phinodes.h"
48 #include "ssa-iterators.h"
49 #include "stringpool.h"
50 #include "tree-ssanames.h"
51 #include "rtl.h"
52 #include "flags.h"
53 #include "insn-config.h"
54 #include "expmed.h"
55 #include "dojump.h"
56 #include "explow.h"
57 #include "calls.h"
58 #include "emit-rtl.h"
59 #include "varasm.h"
60 #include "stmt.h"
61 #include "expr.h"
62 #include "tree-dfa.h"
63 #include "tree-ssa.h"
64 #include "dumpfile.h"
65 #include "alloc-pool.h"
66 #include "cfgloop.h"
67 #include "params.h"
68 #include "tree-ssa-propagate.h"
69 #include "tree-ssa-sccvn.h"
70 #include "tree-cfg.h"
71 #include "domwalk.h"
72 #include "cgraph.h"
74 /* This algorithm is based on the SCC algorithm presented by Keith
75 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
76 (http://citeseer.ist.psu.edu/41805.html). In
77 straight line code, it is equivalent to a regular hash based value
78 numbering that is performed in reverse postorder.
80 For code with cycles, there are two alternatives, both of which
81 require keeping the hashtables separate from the actual list of
82 value numbers for SSA names.
84 1. Iterate value numbering in an RPO walk of the blocks, removing
85 all the entries from the hashtable after each iteration (but
86 keeping the SSA name->value number mapping between iterations).
87 Iterate until it does not change.
89 2. Perform value numbering as part of an SCC walk on the SSA graph,
90 iterating only the cycles in the SSA graph until they do not change
91 (using a separate, optimistic hashtable for value numbering the SCC
92 operands).
94 The second is not just faster in practice (because most SSA graph
95 cycles do not involve all the variables in the graph), it also has
96 some nice properties.
98 One of these nice properties is that when we pop an SCC off the
99 stack, we are guaranteed to have processed all the operands coming from
100 *outside of that SCC*, so we do not need to do anything special to
101 ensure they have value numbers.
103 Another nice property is that the SCC walk is done as part of a DFS
104 of the SSA graph, which makes it easy to perform combining and
105 simplifying operations at the same time.
107 The code below is deliberately written in a way that makes it easy
108 to separate the SCC walk from the other work it does.
110 In order to propagate constants through the code, we track which
111 expressions contain constants, and use those while folding. In
112 theory, we could also track expressions whose value numbers are
113 replaced, in case we end up folding based on expression
114 identities.
116 In order to value number memory, we assign value numbers to vuses.
117 This enables us to note that, for example, stores to the same
118 address of the same value from the same starting memory states are
119 equivalent.
120 TODO:
122 1. We can iterate only the changing portions of the SCC's, but
123 I have not seen an SCC big enough for this to be a win.
124 2. If you differentiate between phi nodes for loops and phi nodes
125 for if-then-else, you can properly consider phi nodes in different
126 blocks for equivalence.
127 3. We could value number vuses in more cases, particularly, whole
128 structure copies.
132 static tree *last_vuse_ptr;
133 static vn_lookup_kind vn_walk_kind;
134 static vn_lookup_kind default_vn_walk_kind;
136 /* vn_nary_op hashtable helpers. */
138 struct vn_nary_op_hasher : nofree_ptr_hash <vn_nary_op_s>
140 typedef vn_nary_op_s *compare_type;
141 static inline hashval_t hash (const vn_nary_op_s *);
142 static inline bool equal (const vn_nary_op_s *, const vn_nary_op_s *);
145 /* Return the computed hashcode for nary operation P1. */
147 inline hashval_t
148 vn_nary_op_hasher::hash (const vn_nary_op_s *vno1)
150 return vno1->hashcode;
153 /* Compare nary operations P1 and P2 and return true if they are
154 equivalent. */
156 inline bool
157 vn_nary_op_hasher::equal (const vn_nary_op_s *vno1, const vn_nary_op_s *vno2)
159 return vn_nary_op_eq (vno1, vno2);
162 typedef hash_table<vn_nary_op_hasher> vn_nary_op_table_type;
163 typedef vn_nary_op_table_type::iterator vn_nary_op_iterator_type;
166 /* vn_phi hashtable helpers. */
168 static int
169 vn_phi_eq (const_vn_phi_t const vp1, const_vn_phi_t const vp2);
171 struct vn_phi_hasher : pointer_hash <vn_phi_s>
173 static inline hashval_t hash (const vn_phi_s *);
174 static inline bool equal (const vn_phi_s *, const vn_phi_s *);
175 static inline void remove (vn_phi_s *);
178 /* Return the computed hashcode for phi operation P1. */
180 inline hashval_t
181 vn_phi_hasher::hash (const vn_phi_s *vp1)
183 return vp1->hashcode;
186 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
188 inline bool
189 vn_phi_hasher::equal (const vn_phi_s *vp1, const vn_phi_s *vp2)
191 return vn_phi_eq (vp1, vp2);
194 /* Free a phi operation structure VP. */
196 inline void
197 vn_phi_hasher::remove (vn_phi_s *phi)
199 phi->phiargs.release ();
202 typedef hash_table<vn_phi_hasher> vn_phi_table_type;
203 typedef vn_phi_table_type::iterator vn_phi_iterator_type;
206 /* Compare two reference operands P1 and P2 for equality. Return true if
207 they are equal, and false otherwise. */
209 static int
210 vn_reference_op_eq (const void *p1, const void *p2)
212 const_vn_reference_op_t const vro1 = (const_vn_reference_op_t) p1;
213 const_vn_reference_op_t const vro2 = (const_vn_reference_op_t) p2;
215 return (vro1->opcode == vro2->opcode
216 /* We do not care for differences in type qualification. */
217 && (vro1->type == vro2->type
218 || (vro1->type && vro2->type
219 && types_compatible_p (TYPE_MAIN_VARIANT (vro1->type),
220 TYPE_MAIN_VARIANT (vro2->type))))
221 && expressions_equal_p (vro1->op0, vro2->op0)
222 && expressions_equal_p (vro1->op1, vro2->op1)
223 && expressions_equal_p (vro1->op2, vro2->op2));
226 /* Free a reference operation structure VP. */
228 static inline void
229 free_reference (vn_reference_s *vr)
231 vr->operands.release ();
235 /* vn_reference hashtable helpers. */
237 struct vn_reference_hasher : pointer_hash <vn_reference_s>
239 static inline hashval_t hash (const vn_reference_s *);
240 static inline bool equal (const vn_reference_s *, const vn_reference_s *);
241 static inline void remove (vn_reference_s *);
244 /* Return the hashcode for a given reference operation P1. */
246 inline hashval_t
247 vn_reference_hasher::hash (const vn_reference_s *vr1)
249 return vr1->hashcode;
252 inline bool
253 vn_reference_hasher::equal (const vn_reference_s *v, const vn_reference_s *c)
255 return vn_reference_eq (v, c);
258 inline void
259 vn_reference_hasher::remove (vn_reference_s *v)
261 free_reference (v);
264 typedef hash_table<vn_reference_hasher> vn_reference_table_type;
265 typedef vn_reference_table_type::iterator vn_reference_iterator_type;
268 /* The set of hashtables and alloc_pool's for their items. */
270 typedef struct vn_tables_s
272 vn_nary_op_table_type *nary;
273 vn_phi_table_type *phis;
274 vn_reference_table_type *references;
275 struct obstack nary_obstack;
276 pool_allocator<vn_phi_s> *phis_pool;
277 pool_allocator<vn_reference_s> *references_pool;
278 } *vn_tables_t;
281 /* vn_constant hashtable helpers. */
283 struct vn_constant_hasher : free_ptr_hash <vn_constant_s>
285 static inline hashval_t hash (const vn_constant_s *);
286 static inline bool equal (const vn_constant_s *, const vn_constant_s *);
289 /* Hash table hash function for vn_constant_t. */
291 inline hashval_t
292 vn_constant_hasher::hash (const vn_constant_s *vc1)
294 return vc1->hashcode;
297 /* Hash table equality function for vn_constant_t. */
299 inline bool
300 vn_constant_hasher::equal (const vn_constant_s *vc1, const vn_constant_s *vc2)
302 if (vc1->hashcode != vc2->hashcode)
303 return false;
305 return vn_constant_eq_with_type (vc1->constant, vc2->constant);
308 static hash_table<vn_constant_hasher> *constant_to_value_id;
309 static bitmap constant_value_ids;
312 /* Valid hashtables storing information we have proven to be
313 correct. */
315 static vn_tables_t valid_info;
317 /* Optimistic hashtables storing information we are making assumptions about
318 during iterations. */
320 static vn_tables_t optimistic_info;
322 /* Pointer to the set of hashtables that is currently being used.
323 Should always point to either the optimistic_info, or the
324 valid_info. */
326 static vn_tables_t current_info;
329 /* Reverse post order index for each basic block. */
331 static int *rpo_numbers;
333 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
335 /* Return the SSA value of the VUSE x, supporting released VDEFs
336 during elimination which will value-number the VDEF to the
337 associated VUSE (but not substitute in the whole lattice). */
339 static inline tree
340 vuse_ssa_val (tree x)
342 if (!x)
343 return NULL_TREE;
347 x = SSA_VAL (x);
349 while (SSA_NAME_IN_FREE_LIST (x));
351 return x;
354 /* This represents the top of the VN lattice, which is the universal
355 value. */
357 tree VN_TOP;
359 /* Unique counter for our value ids. */
361 static unsigned int next_value_id;
363 /* Next DFS number and the stack for strongly connected component
364 detection. */
366 static unsigned int next_dfs_num;
367 static vec<tree> sccstack;
371 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
372 are allocated on an obstack for locality reasons, and to free them
373 without looping over the vec. */
375 static vec<vn_ssa_aux_t> vn_ssa_aux_table;
376 static struct obstack vn_ssa_aux_obstack;
378 /* Return the value numbering information for a given SSA name. */
380 vn_ssa_aux_t
381 VN_INFO (tree name)
383 vn_ssa_aux_t res = vn_ssa_aux_table[SSA_NAME_VERSION (name)];
384 gcc_checking_assert (res);
385 return res;
388 /* Set the value numbering info for a given SSA name to a given
389 value. */
391 static inline void
392 VN_INFO_SET (tree name, vn_ssa_aux_t value)
394 vn_ssa_aux_table[SSA_NAME_VERSION (name)] = value;
397 /* Initialize the value numbering info for a given SSA name.
398 This should be called just once for every SSA name. */
400 vn_ssa_aux_t
401 VN_INFO_GET (tree name)
403 vn_ssa_aux_t newinfo;
405 newinfo = XOBNEW (&vn_ssa_aux_obstack, struct vn_ssa_aux);
406 memset (newinfo, 0, sizeof (struct vn_ssa_aux));
407 if (SSA_NAME_VERSION (name) >= vn_ssa_aux_table.length ())
408 vn_ssa_aux_table.safe_grow (SSA_NAME_VERSION (name) + 1);
409 vn_ssa_aux_table[SSA_NAME_VERSION (name)] = newinfo;
410 return newinfo;
414 /* Get the representative expression for the SSA_NAME NAME. Returns
415 the representative SSA_NAME if there is no expression associated with it. */
417 tree
418 vn_get_expr_for (tree name)
420 vn_ssa_aux_t vn = VN_INFO (name);
421 gimple def_stmt;
422 tree expr = NULL_TREE;
423 enum tree_code code;
425 if (vn->valnum == VN_TOP)
426 return name;
428 /* If the value-number is a constant it is the representative
429 expression. */
430 if (TREE_CODE (vn->valnum) != SSA_NAME)
431 return vn->valnum;
433 /* Get to the information of the value of this SSA_NAME. */
434 vn = VN_INFO (vn->valnum);
436 /* If the value-number is a constant it is the representative
437 expression. */
438 if (TREE_CODE (vn->valnum) != SSA_NAME)
439 return vn->valnum;
441 /* Else if we have an expression, return it. */
442 if (vn->expr != NULL_TREE)
443 return vn->expr;
445 /* Otherwise use the defining statement to build the expression. */
446 def_stmt = SSA_NAME_DEF_STMT (vn->valnum);
448 /* If the value number is not an assignment use it directly. */
449 if (!is_gimple_assign (def_stmt))
450 return vn->valnum;
452 /* Note that we can valueize here because we clear the cached
453 simplified expressions after each optimistic iteration. */
454 code = gimple_assign_rhs_code (def_stmt);
455 switch (TREE_CODE_CLASS (code))
457 case tcc_reference:
458 if ((code == REALPART_EXPR
459 || code == IMAGPART_EXPR
460 || code == VIEW_CONVERT_EXPR)
461 && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (def_stmt),
462 0)) == SSA_NAME)
463 expr = fold_build1 (code,
464 gimple_expr_type (def_stmt),
465 vn_valueize (TREE_OPERAND
466 (gimple_assign_rhs1 (def_stmt), 0)));
467 break;
469 case tcc_unary:
470 expr = fold_build1 (code,
471 gimple_expr_type (def_stmt),
472 vn_valueize (gimple_assign_rhs1 (def_stmt)));
473 break;
475 case tcc_binary:
476 expr = fold_build2 (code,
477 gimple_expr_type (def_stmt),
478 vn_valueize (gimple_assign_rhs1 (def_stmt)),
479 vn_valueize (gimple_assign_rhs2 (def_stmt)));
480 break;
482 case tcc_exceptional:
483 if (code == CONSTRUCTOR
484 && TREE_CODE
485 (TREE_TYPE (gimple_assign_rhs1 (def_stmt))) == VECTOR_TYPE)
486 expr = gimple_assign_rhs1 (def_stmt);
487 break;
489 default:;
491 if (expr == NULL_TREE)
492 return vn->valnum;
494 /* Cache the expression. */
495 vn->expr = expr;
497 return expr;
500 /* Return the vn_kind the expression computed by the stmt should be
501 associated with. */
503 enum vn_kind
504 vn_get_stmt_kind (gimple stmt)
506 switch (gimple_code (stmt))
508 case GIMPLE_CALL:
509 return VN_REFERENCE;
510 case GIMPLE_PHI:
511 return VN_PHI;
512 case GIMPLE_ASSIGN:
514 enum tree_code code = gimple_assign_rhs_code (stmt);
515 tree rhs1 = gimple_assign_rhs1 (stmt);
516 switch (get_gimple_rhs_class (code))
518 case GIMPLE_UNARY_RHS:
519 case GIMPLE_BINARY_RHS:
520 case GIMPLE_TERNARY_RHS:
521 return VN_NARY;
522 case GIMPLE_SINGLE_RHS:
523 switch (TREE_CODE_CLASS (code))
525 case tcc_reference:
526 /* VOP-less references can go through unary case. */
527 if ((code == REALPART_EXPR
528 || code == IMAGPART_EXPR
529 || code == VIEW_CONVERT_EXPR
530 || code == BIT_FIELD_REF)
531 && TREE_CODE (TREE_OPERAND (rhs1, 0)) == SSA_NAME)
532 return VN_NARY;
534 /* Fallthrough. */
535 case tcc_declaration:
536 return VN_REFERENCE;
538 case tcc_constant:
539 return VN_CONSTANT;
541 default:
542 if (code == ADDR_EXPR)
543 return (is_gimple_min_invariant (rhs1)
544 ? VN_CONSTANT : VN_REFERENCE);
545 else if (code == CONSTRUCTOR)
546 return VN_NARY;
547 return VN_NONE;
549 default:
550 return VN_NONE;
553 default:
554 return VN_NONE;
558 /* Lookup a value id for CONSTANT and return it. If it does not
559 exist returns 0. */
561 unsigned int
562 get_constant_value_id (tree constant)
564 vn_constant_s **slot;
565 struct vn_constant_s vc;
567 vc.hashcode = vn_hash_constant_with_type (constant);
568 vc.constant = constant;
569 slot = constant_to_value_id->find_slot (&vc, NO_INSERT);
570 if (slot)
571 return (*slot)->value_id;
572 return 0;
575 /* Lookup a value id for CONSTANT, and if it does not exist, create a
576 new one and return it. If it does exist, return it. */
578 unsigned int
579 get_or_alloc_constant_value_id (tree constant)
581 vn_constant_s **slot;
582 struct vn_constant_s vc;
583 vn_constant_t vcp;
585 vc.hashcode = vn_hash_constant_with_type (constant);
586 vc.constant = constant;
587 slot = constant_to_value_id->find_slot (&vc, INSERT);
588 if (*slot)
589 return (*slot)->value_id;
591 vcp = XNEW (struct vn_constant_s);
592 vcp->hashcode = vc.hashcode;
593 vcp->constant = constant;
594 vcp->value_id = get_next_value_id ();
595 *slot = vcp;
596 bitmap_set_bit (constant_value_ids, vcp->value_id);
597 return vcp->value_id;
600 /* Return true if V is a value id for a constant. */
602 bool
603 value_id_constant_p (unsigned int v)
605 return bitmap_bit_p (constant_value_ids, v);
608 /* Compute the hash for a reference operand VRO1. */
610 static void
611 vn_reference_op_compute_hash (const vn_reference_op_t vro1, inchash::hash &hstate)
613 hstate.add_int (vro1->opcode);
614 if (vro1->op0)
615 inchash::add_expr (vro1->op0, hstate);
616 if (vro1->op1)
617 inchash::add_expr (vro1->op1, hstate);
618 if (vro1->op2)
619 inchash::add_expr (vro1->op2, hstate);
622 /* Compute a hash for the reference operation VR1 and return it. */
624 static hashval_t
625 vn_reference_compute_hash (const vn_reference_t vr1)
627 inchash::hash hstate;
628 hashval_t result;
629 int i;
630 vn_reference_op_t vro;
631 HOST_WIDE_INT off = -1;
632 bool deref = false;
634 FOR_EACH_VEC_ELT (vr1->operands, i, vro)
636 if (vro->opcode == MEM_REF)
637 deref = true;
638 else if (vro->opcode != ADDR_EXPR)
639 deref = false;
640 if (vro->off != -1)
642 if (off == -1)
643 off = 0;
644 off += vro->off;
646 else
648 if (off != -1
649 && off != 0)
650 hstate.add_int (off);
651 off = -1;
652 if (deref
653 && vro->opcode == ADDR_EXPR)
655 if (vro->op0)
657 tree op = TREE_OPERAND (vro->op0, 0);
658 hstate.add_int (TREE_CODE (op));
659 inchash::add_expr (op, hstate);
662 else
663 vn_reference_op_compute_hash (vro, hstate);
666 result = hstate.end ();
667 /* ??? We would ICE later if we hash instead of adding that in. */
668 if (vr1->vuse)
669 result += SSA_NAME_VERSION (vr1->vuse);
671 return result;
674 /* Return true if reference operations VR1 and VR2 are equivalent. This
675 means they have the same set of operands and vuses. */
677 bool
678 vn_reference_eq (const_vn_reference_t const vr1, const_vn_reference_t const vr2)
680 unsigned i, j;
682 /* Early out if this is not a hash collision. */
683 if (vr1->hashcode != vr2->hashcode)
684 return false;
686 /* The VOP needs to be the same. */
687 if (vr1->vuse != vr2->vuse)
688 return false;
690 /* If the operands are the same we are done. */
691 if (vr1->operands == vr2->operands)
692 return true;
694 if (!expressions_equal_p (TYPE_SIZE (vr1->type), TYPE_SIZE (vr2->type)))
695 return false;
697 if (INTEGRAL_TYPE_P (vr1->type)
698 && INTEGRAL_TYPE_P (vr2->type))
700 if (TYPE_PRECISION (vr1->type) != TYPE_PRECISION (vr2->type))
701 return false;
703 else if (INTEGRAL_TYPE_P (vr1->type)
704 && (TYPE_PRECISION (vr1->type)
705 != TREE_INT_CST_LOW (TYPE_SIZE (vr1->type))))
706 return false;
707 else if (INTEGRAL_TYPE_P (vr2->type)
708 && (TYPE_PRECISION (vr2->type)
709 != TREE_INT_CST_LOW (TYPE_SIZE (vr2->type))))
710 return false;
712 i = 0;
713 j = 0;
716 HOST_WIDE_INT off1 = 0, off2 = 0;
717 vn_reference_op_t vro1, vro2;
718 vn_reference_op_s tem1, tem2;
719 bool deref1 = false, deref2 = false;
720 for (; vr1->operands.iterate (i, &vro1); i++)
722 if (vro1->opcode == MEM_REF)
723 deref1 = true;
724 if (vro1->off == -1)
725 break;
726 off1 += vro1->off;
728 for (; vr2->operands.iterate (j, &vro2); j++)
730 if (vro2->opcode == MEM_REF)
731 deref2 = true;
732 if (vro2->off == -1)
733 break;
734 off2 += vro2->off;
736 if (off1 != off2)
737 return false;
738 if (deref1 && vro1->opcode == ADDR_EXPR)
740 memset (&tem1, 0, sizeof (tem1));
741 tem1.op0 = TREE_OPERAND (vro1->op0, 0);
742 tem1.type = TREE_TYPE (tem1.op0);
743 tem1.opcode = TREE_CODE (tem1.op0);
744 vro1 = &tem1;
745 deref1 = false;
747 if (deref2 && vro2->opcode == ADDR_EXPR)
749 memset (&tem2, 0, sizeof (tem2));
750 tem2.op0 = TREE_OPERAND (vro2->op0, 0);
751 tem2.type = TREE_TYPE (tem2.op0);
752 tem2.opcode = TREE_CODE (tem2.op0);
753 vro2 = &tem2;
754 deref2 = false;
756 if (deref1 != deref2)
757 return false;
758 if (!vn_reference_op_eq (vro1, vro2))
759 return false;
760 ++j;
761 ++i;
763 while (vr1->operands.length () != i
764 || vr2->operands.length () != j);
766 return true;
769 /* Copy the operations present in load/store REF into RESULT, a vector of
770 vn_reference_op_s's. */
772 static void
773 copy_reference_ops_from_ref (tree ref, vec<vn_reference_op_s> *result)
775 if (TREE_CODE (ref) == TARGET_MEM_REF)
777 vn_reference_op_s temp;
779 result->reserve (3);
781 memset (&temp, 0, sizeof (temp));
782 temp.type = TREE_TYPE (ref);
783 temp.opcode = TREE_CODE (ref);
784 temp.op0 = TMR_INDEX (ref);
785 temp.op1 = TMR_STEP (ref);
786 temp.op2 = TMR_OFFSET (ref);
787 temp.off = -1;
788 result->quick_push (temp);
790 memset (&temp, 0, sizeof (temp));
791 temp.type = NULL_TREE;
792 temp.opcode = ERROR_MARK;
793 temp.op0 = TMR_INDEX2 (ref);
794 temp.off = -1;
795 result->quick_push (temp);
797 memset (&temp, 0, sizeof (temp));
798 temp.type = NULL_TREE;
799 temp.opcode = TREE_CODE (TMR_BASE (ref));
800 temp.op0 = TMR_BASE (ref);
801 temp.off = -1;
802 result->quick_push (temp);
803 return;
806 /* For non-calls, store the information that makes up the address. */
807 tree orig = ref;
808 while (ref)
810 vn_reference_op_s temp;
812 memset (&temp, 0, sizeof (temp));
813 temp.type = TREE_TYPE (ref);
814 temp.opcode = TREE_CODE (ref);
815 temp.off = -1;
817 switch (temp.opcode)
819 case MODIFY_EXPR:
820 temp.op0 = TREE_OPERAND (ref, 1);
821 break;
822 case WITH_SIZE_EXPR:
823 temp.op0 = TREE_OPERAND (ref, 1);
824 temp.off = 0;
825 break;
826 case MEM_REF:
827 /* The base address gets its own vn_reference_op_s structure. */
828 temp.op0 = TREE_OPERAND (ref, 1);
829 if (tree_fits_shwi_p (TREE_OPERAND (ref, 1)))
830 temp.off = tree_to_shwi (TREE_OPERAND (ref, 1));
831 break;
832 case BIT_FIELD_REF:
833 /* Record bits and position. */
834 temp.op0 = TREE_OPERAND (ref, 1);
835 temp.op1 = TREE_OPERAND (ref, 2);
836 break;
837 case COMPONENT_REF:
838 /* The field decl is enough to unambiguously specify the field,
839 a matching type is not necessary and a mismatching type
840 is always a spurious difference. */
841 temp.type = NULL_TREE;
842 temp.op0 = TREE_OPERAND (ref, 1);
843 temp.op1 = TREE_OPERAND (ref, 2);
845 tree this_offset = component_ref_field_offset (ref);
846 if (this_offset
847 && TREE_CODE (this_offset) == INTEGER_CST)
849 tree bit_offset = DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1));
850 if (TREE_INT_CST_LOW (bit_offset) % BITS_PER_UNIT == 0)
852 offset_int off
853 = (wi::to_offset (this_offset)
854 + wi::lrshift (wi::to_offset (bit_offset),
855 LOG2_BITS_PER_UNIT));
856 if (wi::fits_shwi_p (off)
857 /* Probibit value-numbering zero offset components
858 of addresses the same before the pass folding
859 __builtin_object_size had a chance to run
860 (checking cfun->after_inlining does the
861 trick here). */
862 && (TREE_CODE (orig) != ADDR_EXPR
863 || off != 0
864 || cfun->after_inlining))
865 temp.off = off.to_shwi ();
869 break;
870 case ARRAY_RANGE_REF:
871 case ARRAY_REF:
872 /* Record index as operand. */
873 temp.op0 = TREE_OPERAND (ref, 1);
874 /* Always record lower bounds and element size. */
875 temp.op1 = array_ref_low_bound (ref);
876 temp.op2 = array_ref_element_size (ref);
877 if (TREE_CODE (temp.op0) == INTEGER_CST
878 && TREE_CODE (temp.op1) == INTEGER_CST
879 && TREE_CODE (temp.op2) == INTEGER_CST)
881 offset_int off = ((wi::to_offset (temp.op0)
882 - wi::to_offset (temp.op1))
883 * wi::to_offset (temp.op2));
884 if (wi::fits_shwi_p (off))
885 temp.off = off.to_shwi();
887 break;
888 case VAR_DECL:
889 if (DECL_HARD_REGISTER (ref))
891 temp.op0 = ref;
892 break;
894 /* Fallthru. */
895 case PARM_DECL:
896 case CONST_DECL:
897 case RESULT_DECL:
898 /* Canonicalize decls to MEM[&decl] which is what we end up with
899 when valueizing MEM[ptr] with ptr = &decl. */
900 temp.opcode = MEM_REF;
901 temp.op0 = build_int_cst (build_pointer_type (TREE_TYPE (ref)), 0);
902 temp.off = 0;
903 result->safe_push (temp);
904 temp.opcode = ADDR_EXPR;
905 temp.op0 = build1 (ADDR_EXPR, TREE_TYPE (temp.op0), ref);
906 temp.type = TREE_TYPE (temp.op0);
907 temp.off = -1;
908 break;
909 case STRING_CST:
910 case INTEGER_CST:
911 case COMPLEX_CST:
912 case VECTOR_CST:
913 case REAL_CST:
914 case FIXED_CST:
915 case CONSTRUCTOR:
916 case SSA_NAME:
917 temp.op0 = ref;
918 break;
919 case ADDR_EXPR:
920 if (is_gimple_min_invariant (ref))
922 temp.op0 = ref;
923 break;
925 break;
926 /* These are only interesting for their operands, their
927 existence, and their type. They will never be the last
928 ref in the chain of references (IE they require an
929 operand), so we don't have to put anything
930 for op* as it will be handled by the iteration */
931 case REALPART_EXPR:
932 case VIEW_CONVERT_EXPR:
933 temp.off = 0;
934 break;
935 case IMAGPART_EXPR:
936 /* This is only interesting for its constant offset. */
937 temp.off = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref)));
938 break;
939 default:
940 gcc_unreachable ();
942 result->safe_push (temp);
944 if (REFERENCE_CLASS_P (ref)
945 || TREE_CODE (ref) == MODIFY_EXPR
946 || TREE_CODE (ref) == WITH_SIZE_EXPR
947 || (TREE_CODE (ref) == ADDR_EXPR
948 && !is_gimple_min_invariant (ref)))
949 ref = TREE_OPERAND (ref, 0);
950 else
951 ref = NULL_TREE;
955 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
956 operands in *OPS, the reference alias set SET and the reference type TYPE.
957 Return true if something useful was produced. */
959 bool
960 ao_ref_init_from_vn_reference (ao_ref *ref,
961 alias_set_type set, tree type,
962 vec<vn_reference_op_s> ops)
964 vn_reference_op_t op;
965 unsigned i;
966 tree base = NULL_TREE;
967 tree *op0_p = &base;
968 HOST_WIDE_INT offset = 0;
969 HOST_WIDE_INT max_size;
970 HOST_WIDE_INT size = -1;
971 tree size_tree = NULL_TREE;
972 alias_set_type base_alias_set = -1;
974 /* First get the final access size from just the outermost expression. */
975 op = &ops[0];
976 if (op->opcode == COMPONENT_REF)
977 size_tree = DECL_SIZE (op->op0);
978 else if (op->opcode == BIT_FIELD_REF)
979 size_tree = op->op0;
980 else
982 machine_mode mode = TYPE_MODE (type);
983 if (mode == BLKmode)
984 size_tree = TYPE_SIZE (type);
985 else
986 size = GET_MODE_BITSIZE (mode);
988 if (size_tree != NULL_TREE)
990 if (!tree_fits_uhwi_p (size_tree))
991 size = -1;
992 else
993 size = tree_to_uhwi (size_tree);
996 /* Initially, maxsize is the same as the accessed element size.
997 In the following it will only grow (or become -1). */
998 max_size = size;
1000 /* Compute cumulative bit-offset for nested component-refs and array-refs,
1001 and find the ultimate containing object. */
1002 FOR_EACH_VEC_ELT (ops, i, op)
1004 switch (op->opcode)
1006 /* These may be in the reference ops, but we cannot do anything
1007 sensible with them here. */
1008 case ADDR_EXPR:
1009 /* Apart from ADDR_EXPR arguments to MEM_REF. */
1010 if (base != NULL_TREE
1011 && TREE_CODE (base) == MEM_REF
1012 && op->op0
1013 && DECL_P (TREE_OPERAND (op->op0, 0)))
1015 vn_reference_op_t pop = &ops[i-1];
1016 base = TREE_OPERAND (op->op0, 0);
1017 if (pop->off == -1)
1019 max_size = -1;
1020 offset = 0;
1022 else
1023 offset += pop->off * BITS_PER_UNIT;
1024 op0_p = NULL;
1025 break;
1027 /* Fallthru. */
1028 case CALL_EXPR:
1029 return false;
1031 /* Record the base objects. */
1032 case MEM_REF:
1033 base_alias_set = get_deref_alias_set (op->op0);
1034 *op0_p = build2 (MEM_REF, op->type,
1035 NULL_TREE, op->op0);
1036 op0_p = &TREE_OPERAND (*op0_p, 0);
1037 break;
1039 case VAR_DECL:
1040 case PARM_DECL:
1041 case RESULT_DECL:
1042 case SSA_NAME:
1043 *op0_p = op->op0;
1044 op0_p = NULL;
1045 break;
1047 /* And now the usual component-reference style ops. */
1048 case BIT_FIELD_REF:
1049 offset += tree_to_shwi (op->op1);
1050 break;
1052 case COMPONENT_REF:
1054 tree field = op->op0;
1055 /* We do not have a complete COMPONENT_REF tree here so we
1056 cannot use component_ref_field_offset. Do the interesting
1057 parts manually. */
1059 if (op->op1
1060 || !tree_fits_uhwi_p (DECL_FIELD_OFFSET (field)))
1061 max_size = -1;
1062 else
1064 offset += (tree_to_uhwi (DECL_FIELD_OFFSET (field))
1065 * BITS_PER_UNIT);
1066 offset += TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field));
1068 break;
1071 case ARRAY_RANGE_REF:
1072 case ARRAY_REF:
1073 /* We recorded the lower bound and the element size. */
1074 if (!tree_fits_shwi_p (op->op0)
1075 || !tree_fits_shwi_p (op->op1)
1076 || !tree_fits_shwi_p (op->op2))
1077 max_size = -1;
1078 else
1080 HOST_WIDE_INT hindex = tree_to_shwi (op->op0);
1081 hindex -= tree_to_shwi (op->op1);
1082 hindex *= tree_to_shwi (op->op2);
1083 hindex *= BITS_PER_UNIT;
1084 offset += hindex;
1086 break;
1088 case REALPART_EXPR:
1089 break;
1091 case IMAGPART_EXPR:
1092 offset += size;
1093 break;
1095 case VIEW_CONVERT_EXPR:
1096 break;
1098 case STRING_CST:
1099 case INTEGER_CST:
1100 case COMPLEX_CST:
1101 case VECTOR_CST:
1102 case REAL_CST:
1103 case CONSTRUCTOR:
1104 case CONST_DECL:
1105 return false;
1107 default:
1108 return false;
1112 if (base == NULL_TREE)
1113 return false;
1115 ref->ref = NULL_TREE;
1116 ref->base = base;
1117 ref->offset = offset;
1118 ref->size = size;
1119 ref->max_size = max_size;
1120 ref->ref_alias_set = set;
1121 if (base_alias_set != -1)
1122 ref->base_alias_set = base_alias_set;
1123 else
1124 ref->base_alias_set = get_alias_set (base);
1125 /* We discount volatiles from value-numbering elsewhere. */
1126 ref->volatile_p = false;
1128 return true;
1131 /* Copy the operations present in load/store/call REF into RESULT, a vector of
1132 vn_reference_op_s's. */
1134 static void
1135 copy_reference_ops_from_call (gcall *call,
1136 vec<vn_reference_op_s> *result)
1138 vn_reference_op_s temp;
1139 unsigned i;
1140 tree lhs = gimple_call_lhs (call);
1141 int lr;
1143 /* If 2 calls have a different non-ssa lhs, vdef value numbers should be
1144 different. By adding the lhs here in the vector, we ensure that the
1145 hashcode is different, guaranteeing a different value number. */
1146 if (lhs && TREE_CODE (lhs) != SSA_NAME)
1148 memset (&temp, 0, sizeof (temp));
1149 temp.opcode = MODIFY_EXPR;
1150 temp.type = TREE_TYPE (lhs);
1151 temp.op0 = lhs;
1152 temp.off = -1;
1153 result->safe_push (temp);
1156 /* Copy the type, opcode, function, static chain and EH region, if any. */
1157 memset (&temp, 0, sizeof (temp));
1158 temp.type = gimple_call_return_type (call);
1159 temp.opcode = CALL_EXPR;
1160 temp.op0 = gimple_call_fn (call);
1161 temp.op1 = gimple_call_chain (call);
1162 if (stmt_could_throw_p (call) && (lr = lookup_stmt_eh_lp (call)) > 0)
1163 temp.op2 = size_int (lr);
1164 temp.off = -1;
1165 if (gimple_call_with_bounds_p (call))
1166 temp.with_bounds = 1;
1167 result->safe_push (temp);
1169 /* Copy the call arguments. As they can be references as well,
1170 just chain them together. */
1171 for (i = 0; i < gimple_call_num_args (call); ++i)
1173 tree callarg = gimple_call_arg (call, i);
1174 copy_reference_ops_from_ref (callarg, result);
1178 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1179 *I_P to point to the last element of the replacement. */
1180 void
1181 vn_reference_fold_indirect (vec<vn_reference_op_s> *ops,
1182 unsigned int *i_p)
1184 unsigned int i = *i_p;
1185 vn_reference_op_t op = &(*ops)[i];
1186 vn_reference_op_t mem_op = &(*ops)[i - 1];
1187 tree addr_base;
1188 HOST_WIDE_INT addr_offset = 0;
1190 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1191 from .foo.bar to the preceding MEM_REF offset and replace the
1192 address with &OBJ. */
1193 addr_base = get_addr_base_and_unit_offset (TREE_OPERAND (op->op0, 0),
1194 &addr_offset);
1195 gcc_checking_assert (addr_base && TREE_CODE (addr_base) != MEM_REF);
1196 if (addr_base != TREE_OPERAND (op->op0, 0))
1198 offset_int off = offset_int::from (mem_op->op0, SIGNED);
1199 off += addr_offset;
1200 mem_op->op0 = wide_int_to_tree (TREE_TYPE (mem_op->op0), off);
1201 op->op0 = build_fold_addr_expr (addr_base);
1202 if (tree_fits_shwi_p (mem_op->op0))
1203 mem_op->off = tree_to_shwi (mem_op->op0);
1204 else
1205 mem_op->off = -1;
1209 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1210 *I_P to point to the last element of the replacement. */
1211 static void
1212 vn_reference_maybe_forwprop_address (vec<vn_reference_op_s> *ops,
1213 unsigned int *i_p)
1215 unsigned int i = *i_p;
1216 vn_reference_op_t op = &(*ops)[i];
1217 vn_reference_op_t mem_op = &(*ops)[i - 1];
1218 gimple def_stmt;
1219 enum tree_code code;
1220 offset_int off;
1222 def_stmt = SSA_NAME_DEF_STMT (op->op0);
1223 if (!is_gimple_assign (def_stmt))
1224 return;
1226 code = gimple_assign_rhs_code (def_stmt);
1227 if (code != ADDR_EXPR
1228 && code != POINTER_PLUS_EXPR)
1229 return;
1231 off = offset_int::from (mem_op->op0, SIGNED);
1233 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1234 from .foo.bar to the preceding MEM_REF offset and replace the
1235 address with &OBJ. */
1236 if (code == ADDR_EXPR)
1238 tree addr, addr_base;
1239 HOST_WIDE_INT addr_offset;
1241 addr = gimple_assign_rhs1 (def_stmt);
1242 addr_base = get_addr_base_and_unit_offset (TREE_OPERAND (addr, 0),
1243 &addr_offset);
1244 /* If that didn't work because the address isn't invariant propagate
1245 the reference tree from the address operation in case the current
1246 dereference isn't offsetted. */
1247 if (!addr_base
1248 && *i_p == ops->length () - 1
1249 && off == 0
1250 /* This makes us disable this transform for PRE where the
1251 reference ops might be also used for code insertion which
1252 is invalid. */
1253 && default_vn_walk_kind == VN_WALKREWRITE)
1255 auto_vec<vn_reference_op_s, 32> tem;
1256 copy_reference_ops_from_ref (TREE_OPERAND (addr, 0), &tem);
1257 ops->pop ();
1258 ops->pop ();
1259 ops->safe_splice (tem);
1260 --*i_p;
1261 return;
1263 if (!addr_base
1264 || TREE_CODE (addr_base) != MEM_REF)
1265 return;
1267 off += addr_offset;
1268 off += mem_ref_offset (addr_base);
1269 op->op0 = TREE_OPERAND (addr_base, 0);
1271 else
1273 tree ptr, ptroff;
1274 ptr = gimple_assign_rhs1 (def_stmt);
1275 ptroff = gimple_assign_rhs2 (def_stmt);
1276 if (TREE_CODE (ptr) != SSA_NAME
1277 || TREE_CODE (ptroff) != INTEGER_CST)
1278 return;
1280 off += wi::to_offset (ptroff);
1281 op->op0 = ptr;
1284 mem_op->op0 = wide_int_to_tree (TREE_TYPE (mem_op->op0), off);
1285 if (tree_fits_shwi_p (mem_op->op0))
1286 mem_op->off = tree_to_shwi (mem_op->op0);
1287 else
1288 mem_op->off = -1;
1289 if (TREE_CODE (op->op0) == SSA_NAME)
1290 op->op0 = SSA_VAL (op->op0);
1291 if (TREE_CODE (op->op0) != SSA_NAME)
1292 op->opcode = TREE_CODE (op->op0);
1294 /* And recurse. */
1295 if (TREE_CODE (op->op0) == SSA_NAME)
1296 vn_reference_maybe_forwprop_address (ops, i_p);
1297 else if (TREE_CODE (op->op0) == ADDR_EXPR)
1298 vn_reference_fold_indirect (ops, i_p);
1301 /* Optimize the reference REF to a constant if possible or return
1302 NULL_TREE if not. */
1304 tree
1305 fully_constant_vn_reference_p (vn_reference_t ref)
1307 vec<vn_reference_op_s> operands = ref->operands;
1308 vn_reference_op_t op;
1310 /* Try to simplify the translated expression if it is
1311 a call to a builtin function with at most two arguments. */
1312 op = &operands[0];
1313 if (op->opcode == CALL_EXPR
1314 && TREE_CODE (op->op0) == ADDR_EXPR
1315 && TREE_CODE (TREE_OPERAND (op->op0, 0)) == FUNCTION_DECL
1316 && DECL_BUILT_IN (TREE_OPERAND (op->op0, 0))
1317 && operands.length () >= 2
1318 && operands.length () <= 3)
1320 vn_reference_op_t arg0, arg1 = NULL;
1321 bool anyconst = false;
1322 arg0 = &operands[1];
1323 if (operands.length () > 2)
1324 arg1 = &operands[2];
1325 if (TREE_CODE_CLASS (arg0->opcode) == tcc_constant
1326 || (arg0->opcode == ADDR_EXPR
1327 && is_gimple_min_invariant (arg0->op0)))
1328 anyconst = true;
1329 if (arg1
1330 && (TREE_CODE_CLASS (arg1->opcode) == tcc_constant
1331 || (arg1->opcode == ADDR_EXPR
1332 && is_gimple_min_invariant (arg1->op0))))
1333 anyconst = true;
1334 if (anyconst)
1336 tree folded = build_call_expr (TREE_OPERAND (op->op0, 0),
1337 arg1 ? 2 : 1,
1338 arg0->op0,
1339 arg1 ? arg1->op0 : NULL);
1340 if (folded
1341 && TREE_CODE (folded) == NOP_EXPR)
1342 folded = TREE_OPERAND (folded, 0);
1343 if (folded
1344 && is_gimple_min_invariant (folded))
1345 return folded;
1349 /* Simplify reads from constants or constant initializers. */
1350 else if (BITS_PER_UNIT == 8
1351 && is_gimple_reg_type (ref->type)
1352 && (!INTEGRAL_TYPE_P (ref->type)
1353 || TYPE_PRECISION (ref->type) % BITS_PER_UNIT == 0))
1355 HOST_WIDE_INT off = 0;
1356 HOST_WIDE_INT size;
1357 if (INTEGRAL_TYPE_P (ref->type))
1358 size = TYPE_PRECISION (ref->type);
1359 else
1360 size = tree_to_shwi (TYPE_SIZE (ref->type));
1361 if (size % BITS_PER_UNIT != 0
1362 || size > MAX_BITSIZE_MODE_ANY_MODE)
1363 return NULL_TREE;
1364 size /= BITS_PER_UNIT;
1365 unsigned i;
1366 for (i = 0; i < operands.length (); ++i)
1368 if (operands[i].off == -1)
1369 return NULL_TREE;
1370 off += operands[i].off;
1371 if (operands[i].opcode == MEM_REF)
1373 ++i;
1374 break;
1377 vn_reference_op_t base = &operands[--i];
1378 tree ctor = error_mark_node;
1379 tree decl = NULL_TREE;
1380 if (TREE_CODE_CLASS (base->opcode) == tcc_constant)
1381 ctor = base->op0;
1382 else if (base->opcode == MEM_REF
1383 && base[1].opcode == ADDR_EXPR
1384 && (TREE_CODE (TREE_OPERAND (base[1].op0, 0)) == VAR_DECL
1385 || TREE_CODE (TREE_OPERAND (base[1].op0, 0)) == CONST_DECL))
1387 decl = TREE_OPERAND (base[1].op0, 0);
1388 ctor = ctor_for_folding (decl);
1390 if (ctor == NULL_TREE)
1391 return build_zero_cst (ref->type);
1392 else if (ctor != error_mark_node)
1394 if (decl)
1396 tree res = fold_ctor_reference (ref->type, ctor,
1397 off * BITS_PER_UNIT,
1398 size * BITS_PER_UNIT, decl);
1399 if (res)
1401 STRIP_USELESS_TYPE_CONVERSION (res);
1402 if (is_gimple_min_invariant (res))
1403 return res;
1406 else
1408 unsigned char buf[MAX_BITSIZE_MODE_ANY_MODE / BITS_PER_UNIT];
1409 if (native_encode_expr (ctor, buf, size, off) > 0)
1410 return native_interpret_expr (ref->type, buf, size);
1415 return NULL_TREE;
1418 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1419 structures into their value numbers. This is done in-place, and
1420 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1421 whether any operands were valueized. */
1423 static vec<vn_reference_op_s>
1424 valueize_refs_1 (vec<vn_reference_op_s> orig, bool *valueized_anything)
1426 vn_reference_op_t vro;
1427 unsigned int i;
1429 *valueized_anything = false;
1431 FOR_EACH_VEC_ELT (orig, i, vro)
1433 if (vro->opcode == SSA_NAME
1434 || (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME))
1436 tree tem = SSA_VAL (vro->op0);
1437 if (tem != vro->op0)
1439 *valueized_anything = true;
1440 vro->op0 = tem;
1442 /* If it transforms from an SSA_NAME to a constant, update
1443 the opcode. */
1444 if (TREE_CODE (vro->op0) != SSA_NAME && vro->opcode == SSA_NAME)
1445 vro->opcode = TREE_CODE (vro->op0);
1447 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
1449 tree tem = SSA_VAL (vro->op1);
1450 if (tem != vro->op1)
1452 *valueized_anything = true;
1453 vro->op1 = tem;
1456 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
1458 tree tem = SSA_VAL (vro->op2);
1459 if (tem != vro->op2)
1461 *valueized_anything = true;
1462 vro->op2 = tem;
1465 /* If it transforms from an SSA_NAME to an address, fold with
1466 a preceding indirect reference. */
1467 if (i > 0
1468 && vro->op0
1469 && TREE_CODE (vro->op0) == ADDR_EXPR
1470 && orig[i - 1].opcode == MEM_REF)
1471 vn_reference_fold_indirect (&orig, &i);
1472 else if (i > 0
1473 && vro->opcode == SSA_NAME
1474 && orig[i - 1].opcode == MEM_REF)
1475 vn_reference_maybe_forwprop_address (&orig, &i);
1476 /* If it transforms a non-constant ARRAY_REF into a constant
1477 one, adjust the constant offset. */
1478 else if (vro->opcode == ARRAY_REF
1479 && vro->off == -1
1480 && TREE_CODE (vro->op0) == INTEGER_CST
1481 && TREE_CODE (vro->op1) == INTEGER_CST
1482 && TREE_CODE (vro->op2) == INTEGER_CST)
1484 offset_int off = ((wi::to_offset (vro->op0)
1485 - wi::to_offset (vro->op1))
1486 * wi::to_offset (vro->op2));
1487 if (wi::fits_shwi_p (off))
1488 vro->off = off.to_shwi ();
1492 return orig;
1495 static vec<vn_reference_op_s>
1496 valueize_refs (vec<vn_reference_op_s> orig)
1498 bool tem;
1499 return valueize_refs_1 (orig, &tem);
1502 static vec<vn_reference_op_s> shared_lookup_references;
1504 /* Create a vector of vn_reference_op_s structures from REF, a
1505 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1506 this function. *VALUEIZED_ANYTHING will specify whether any
1507 operands were valueized. */
1509 static vec<vn_reference_op_s>
1510 valueize_shared_reference_ops_from_ref (tree ref, bool *valueized_anything)
1512 if (!ref)
1513 return vNULL;
1514 shared_lookup_references.truncate (0);
1515 copy_reference_ops_from_ref (ref, &shared_lookup_references);
1516 shared_lookup_references = valueize_refs_1 (shared_lookup_references,
1517 valueized_anything);
1518 return shared_lookup_references;
1521 /* Create a vector of vn_reference_op_s structures from CALL, a
1522 call statement. The vector is shared among all callers of
1523 this function. */
1525 static vec<vn_reference_op_s>
1526 valueize_shared_reference_ops_from_call (gcall *call)
1528 if (!call)
1529 return vNULL;
1530 shared_lookup_references.truncate (0);
1531 copy_reference_ops_from_call (call, &shared_lookup_references);
1532 shared_lookup_references = valueize_refs (shared_lookup_references);
1533 return shared_lookup_references;
1536 /* Lookup a SCCVN reference operation VR in the current hash table.
1537 Returns the resulting value number if it exists in the hash table,
1538 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1539 vn_reference_t stored in the hashtable if something is found. */
1541 static tree
1542 vn_reference_lookup_1 (vn_reference_t vr, vn_reference_t *vnresult)
1544 vn_reference_s **slot;
1545 hashval_t hash;
1547 hash = vr->hashcode;
1548 slot = current_info->references->find_slot_with_hash (vr, hash, NO_INSERT);
1549 if (!slot && current_info == optimistic_info)
1550 slot = valid_info->references->find_slot_with_hash (vr, hash, NO_INSERT);
1551 if (slot)
1553 if (vnresult)
1554 *vnresult = (vn_reference_t)*slot;
1555 return ((vn_reference_t)*slot)->result;
1558 return NULL_TREE;
1561 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1562 with the current VUSE and performs the expression lookup. */
1564 static void *
1565 vn_reference_lookup_2 (ao_ref *op ATTRIBUTE_UNUSED, tree vuse,
1566 unsigned int cnt, void *vr_)
1568 vn_reference_t vr = (vn_reference_t)vr_;
1569 vn_reference_s **slot;
1570 hashval_t hash;
1572 /* This bounds the stmt walks we perform on reference lookups
1573 to O(1) instead of O(N) where N is the number of dominating
1574 stores. */
1575 if (cnt > (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS))
1576 return (void *)-1;
1578 if (last_vuse_ptr)
1579 *last_vuse_ptr = vuse;
1581 /* Fixup vuse and hash. */
1582 if (vr->vuse)
1583 vr->hashcode = vr->hashcode - SSA_NAME_VERSION (vr->vuse);
1584 vr->vuse = vuse_ssa_val (vuse);
1585 if (vr->vuse)
1586 vr->hashcode = vr->hashcode + SSA_NAME_VERSION (vr->vuse);
1588 hash = vr->hashcode;
1589 slot = current_info->references->find_slot_with_hash (vr, hash, NO_INSERT);
1590 if (!slot && current_info == optimistic_info)
1591 slot = valid_info->references->find_slot_with_hash (vr, hash, NO_INSERT);
1592 if (slot)
1593 return *slot;
1595 return NULL;
1598 /* Lookup an existing or insert a new vn_reference entry into the
1599 value table for the VUSE, SET, TYPE, OPERANDS reference which
1600 has the value VALUE which is either a constant or an SSA name. */
1602 static vn_reference_t
1603 vn_reference_lookup_or_insert_for_pieces (tree vuse,
1604 alias_set_type set,
1605 tree type,
1606 vec<vn_reference_op_s,
1607 va_heap> operands,
1608 tree value)
1610 vn_reference_s vr1;
1611 vn_reference_t result;
1612 unsigned value_id;
1613 vr1.vuse = vuse;
1614 vr1.operands = operands;
1615 vr1.type = type;
1616 vr1.set = set;
1617 vr1.hashcode = vn_reference_compute_hash (&vr1);
1618 if (vn_reference_lookup_1 (&vr1, &result))
1619 return result;
1620 if (TREE_CODE (value) == SSA_NAME)
1621 value_id = VN_INFO (value)->value_id;
1622 else
1623 value_id = get_or_alloc_constant_value_id (value);
1624 return vn_reference_insert_pieces (vuse, set, type,
1625 operands.copy (), value, value_id);
1628 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1629 from the statement defining VUSE and if not successful tries to
1630 translate *REFP and VR_ through an aggregate copy at the definition
1631 of VUSE. */
1633 static void *
1634 vn_reference_lookup_3 (ao_ref *ref, tree vuse, void *vr_,
1635 bool disambiguate_only)
1637 vn_reference_t vr = (vn_reference_t)vr_;
1638 gimple def_stmt = SSA_NAME_DEF_STMT (vuse);
1639 tree base;
1640 HOST_WIDE_INT offset, maxsize;
1641 static vec<vn_reference_op_s>
1642 lhs_ops = vNULL;
1643 ao_ref lhs_ref;
1644 bool lhs_ref_ok = false;
1646 /* First try to disambiguate after value-replacing in the definitions LHS. */
1647 if (is_gimple_assign (def_stmt))
1649 tree lhs = gimple_assign_lhs (def_stmt);
1650 bool valueized_anything = false;
1651 /* Avoid re-allocation overhead. */
1652 lhs_ops.truncate (0);
1653 copy_reference_ops_from_ref (lhs, &lhs_ops);
1654 lhs_ops = valueize_refs_1 (lhs_ops, &valueized_anything);
1655 if (valueized_anything)
1657 lhs_ref_ok = ao_ref_init_from_vn_reference (&lhs_ref,
1658 get_alias_set (lhs),
1659 TREE_TYPE (lhs), lhs_ops);
1660 if (lhs_ref_ok
1661 && !refs_may_alias_p_1 (ref, &lhs_ref, true))
1662 return NULL;
1664 else
1666 ao_ref_init (&lhs_ref, lhs);
1667 lhs_ref_ok = true;
1670 else if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL)
1671 && gimple_call_num_args (def_stmt) <= 4)
1673 /* For builtin calls valueize its arguments and call the
1674 alias oracle again. Valueization may improve points-to
1675 info of pointers and constify size and position arguments.
1676 Originally this was motivated by PR61034 which has
1677 conditional calls to free falsely clobbering ref because
1678 of imprecise points-to info of the argument. */
1679 tree oldargs[4];
1680 bool valueized_anything = false;
1681 for (unsigned i = 0; i < gimple_call_num_args (def_stmt); ++i)
1683 oldargs[i] = gimple_call_arg (def_stmt, i);
1684 if (TREE_CODE (oldargs[i]) == SSA_NAME
1685 && VN_INFO (oldargs[i])->valnum != oldargs[i])
1687 gimple_call_set_arg (def_stmt, i, VN_INFO (oldargs[i])->valnum);
1688 valueized_anything = true;
1691 if (valueized_anything)
1693 bool res = call_may_clobber_ref_p_1 (as_a <gcall *> (def_stmt),
1694 ref);
1695 for (unsigned i = 0; i < gimple_call_num_args (def_stmt); ++i)
1696 gimple_call_set_arg (def_stmt, i, oldargs[i]);
1697 if (!res)
1698 return NULL;
1702 if (disambiguate_only)
1703 return (void *)-1;
1705 base = ao_ref_base (ref);
1706 offset = ref->offset;
1707 maxsize = ref->max_size;
1709 /* If we cannot constrain the size of the reference we cannot
1710 test if anything kills it. */
1711 if (maxsize == -1)
1712 return (void *)-1;
1714 /* We can't deduce anything useful from clobbers. */
1715 if (gimple_clobber_p (def_stmt))
1716 return (void *)-1;
1718 /* def_stmt may-defs *ref. See if we can derive a value for *ref
1719 from that definition.
1720 1) Memset. */
1721 if (is_gimple_reg_type (vr->type)
1722 && gimple_call_builtin_p (def_stmt, BUILT_IN_MEMSET)
1723 && integer_zerop (gimple_call_arg (def_stmt, 1))
1724 && tree_fits_uhwi_p (gimple_call_arg (def_stmt, 2))
1725 && TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR)
1727 tree ref2 = TREE_OPERAND (gimple_call_arg (def_stmt, 0), 0);
1728 tree base2;
1729 HOST_WIDE_INT offset2, size2, maxsize2;
1730 base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &maxsize2);
1731 size2 = tree_to_uhwi (gimple_call_arg (def_stmt, 2)) * 8;
1732 if ((unsigned HOST_WIDE_INT)size2 / 8
1733 == tree_to_uhwi (gimple_call_arg (def_stmt, 2))
1734 && maxsize2 != -1
1735 && operand_equal_p (base, base2, 0)
1736 && offset2 <= offset
1737 && offset2 + size2 >= offset + maxsize)
1739 tree val = build_zero_cst (vr->type);
1740 return vn_reference_lookup_or_insert_for_pieces
1741 (vuse, vr->set, vr->type, vr->operands, val);
1745 /* 2) Assignment from an empty CONSTRUCTOR. */
1746 else if (is_gimple_reg_type (vr->type)
1747 && gimple_assign_single_p (def_stmt)
1748 && gimple_assign_rhs_code (def_stmt) == CONSTRUCTOR
1749 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt)) == 0)
1751 tree base2;
1752 HOST_WIDE_INT offset2, size2, maxsize2;
1753 base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
1754 &offset2, &size2, &maxsize2);
1755 if (maxsize2 != -1
1756 && operand_equal_p (base, base2, 0)
1757 && offset2 <= offset
1758 && offset2 + size2 >= offset + maxsize)
1760 tree val = build_zero_cst (vr->type);
1761 return vn_reference_lookup_or_insert_for_pieces
1762 (vuse, vr->set, vr->type, vr->operands, val);
1766 /* 3) Assignment from a constant. We can use folds native encode/interpret
1767 routines to extract the assigned bits. */
1768 else if (vn_walk_kind == VN_WALKREWRITE
1769 && CHAR_BIT == 8 && BITS_PER_UNIT == 8
1770 && ref->size == maxsize
1771 && maxsize % BITS_PER_UNIT == 0
1772 && offset % BITS_PER_UNIT == 0
1773 && is_gimple_reg_type (vr->type)
1774 && gimple_assign_single_p (def_stmt)
1775 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt)))
1777 tree base2;
1778 HOST_WIDE_INT offset2, size2, maxsize2;
1779 base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
1780 &offset2, &size2, &maxsize2);
1781 if (maxsize2 != -1
1782 && maxsize2 == size2
1783 && size2 % BITS_PER_UNIT == 0
1784 && offset2 % BITS_PER_UNIT == 0
1785 && operand_equal_p (base, base2, 0)
1786 && offset2 <= offset
1787 && offset2 + size2 >= offset + maxsize)
1789 /* We support up to 512-bit values (for V8DFmode). */
1790 unsigned char buffer[64];
1791 int len;
1793 len = native_encode_expr (gimple_assign_rhs1 (def_stmt),
1794 buffer, sizeof (buffer));
1795 if (len > 0)
1797 tree val = native_interpret_expr (vr->type,
1798 buffer
1799 + ((offset - offset2)
1800 / BITS_PER_UNIT),
1801 ref->size / BITS_PER_UNIT);
1802 if (val)
1803 return vn_reference_lookup_or_insert_for_pieces
1804 (vuse, vr->set, vr->type, vr->operands, val);
1809 /* 4) Assignment from an SSA name which definition we may be able
1810 to access pieces from. */
1811 else if (ref->size == maxsize
1812 && is_gimple_reg_type (vr->type)
1813 && gimple_assign_single_p (def_stmt)
1814 && TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME)
1816 tree rhs1 = gimple_assign_rhs1 (def_stmt);
1817 gimple def_stmt2 = SSA_NAME_DEF_STMT (rhs1);
1818 if (is_gimple_assign (def_stmt2)
1819 && (gimple_assign_rhs_code (def_stmt2) == COMPLEX_EXPR
1820 || gimple_assign_rhs_code (def_stmt2) == CONSTRUCTOR)
1821 && types_compatible_p (vr->type, TREE_TYPE (TREE_TYPE (rhs1))))
1823 tree base2;
1824 HOST_WIDE_INT offset2, size2, maxsize2, off;
1825 base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
1826 &offset2, &size2, &maxsize2);
1827 off = offset - offset2;
1828 if (maxsize2 != -1
1829 && maxsize2 == size2
1830 && operand_equal_p (base, base2, 0)
1831 && offset2 <= offset
1832 && offset2 + size2 >= offset + maxsize)
1834 tree val = NULL_TREE;
1835 HOST_WIDE_INT elsz
1836 = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (TREE_TYPE (rhs1))));
1837 if (gimple_assign_rhs_code (def_stmt2) == COMPLEX_EXPR)
1839 if (off == 0)
1840 val = gimple_assign_rhs1 (def_stmt2);
1841 else if (off == elsz)
1842 val = gimple_assign_rhs2 (def_stmt2);
1844 else if (gimple_assign_rhs_code (def_stmt2) == CONSTRUCTOR
1845 && off % elsz == 0)
1847 tree ctor = gimple_assign_rhs1 (def_stmt2);
1848 unsigned i = off / elsz;
1849 if (i < CONSTRUCTOR_NELTS (ctor))
1851 constructor_elt *elt = CONSTRUCTOR_ELT (ctor, i);
1852 if (TREE_CODE (TREE_TYPE (rhs1)) == VECTOR_TYPE)
1854 if (TREE_CODE (TREE_TYPE (elt->value))
1855 != VECTOR_TYPE)
1856 val = elt->value;
1860 if (val)
1861 return vn_reference_lookup_or_insert_for_pieces
1862 (vuse, vr->set, vr->type, vr->operands, val);
1867 /* 5) For aggregate copies translate the reference through them if
1868 the copy kills ref. */
1869 else if (vn_walk_kind == VN_WALKREWRITE
1870 && gimple_assign_single_p (def_stmt)
1871 && (DECL_P (gimple_assign_rhs1 (def_stmt))
1872 || TREE_CODE (gimple_assign_rhs1 (def_stmt)) == MEM_REF
1873 || handled_component_p (gimple_assign_rhs1 (def_stmt))))
1875 tree base2;
1876 HOST_WIDE_INT offset2, size2, maxsize2;
1877 int i, j;
1878 auto_vec<vn_reference_op_s> rhs;
1879 vn_reference_op_t vro;
1880 ao_ref r;
1882 if (!lhs_ref_ok)
1883 return (void *)-1;
1885 /* See if the assignment kills REF. */
1886 base2 = ao_ref_base (&lhs_ref);
1887 offset2 = lhs_ref.offset;
1888 size2 = lhs_ref.size;
1889 maxsize2 = lhs_ref.max_size;
1890 if (maxsize2 == -1
1891 || (base != base2
1892 && (TREE_CODE (base) != MEM_REF
1893 || TREE_CODE (base2) != MEM_REF
1894 || TREE_OPERAND (base, 0) != TREE_OPERAND (base2, 0)
1895 || !tree_int_cst_equal (TREE_OPERAND (base, 1),
1896 TREE_OPERAND (base2, 1))))
1897 || offset2 > offset
1898 || offset2 + size2 < offset + maxsize)
1899 return (void *)-1;
1901 /* Find the common base of ref and the lhs. lhs_ops already
1902 contains valueized operands for the lhs. */
1903 i = vr->operands.length () - 1;
1904 j = lhs_ops.length () - 1;
1905 while (j >= 0 && i >= 0
1906 && vn_reference_op_eq (&vr->operands[i], &lhs_ops[j]))
1908 i--;
1909 j--;
1912 /* ??? The innermost op should always be a MEM_REF and we already
1913 checked that the assignment to the lhs kills vr. Thus for
1914 aggregate copies using char[] types the vn_reference_op_eq
1915 may fail when comparing types for compatibility. But we really
1916 don't care here - further lookups with the rewritten operands
1917 will simply fail if we messed up types too badly. */
1918 HOST_WIDE_INT extra_off = 0;
1919 if (j == 0 && i >= 0
1920 && lhs_ops[0].opcode == MEM_REF
1921 && lhs_ops[0].off != -1)
1923 if (lhs_ops[0].off == vr->operands[i].off)
1924 i--, j--;
1925 else if (vr->operands[i].opcode == MEM_REF
1926 && vr->operands[i].off != -1)
1928 extra_off = vr->operands[i].off - lhs_ops[0].off;
1929 i--, j--;
1933 /* i now points to the first additional op.
1934 ??? LHS may not be completely contained in VR, one or more
1935 VIEW_CONVERT_EXPRs could be in its way. We could at least
1936 try handling outermost VIEW_CONVERT_EXPRs. */
1937 if (j != -1)
1938 return (void *)-1;
1940 /* Now re-write REF to be based on the rhs of the assignment. */
1941 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt), &rhs);
1943 /* Apply an extra offset to the inner MEM_REF of the RHS. */
1944 if (extra_off != 0)
1946 if (rhs.length () < 2
1947 || rhs[0].opcode != MEM_REF
1948 || rhs[0].off == -1)
1949 return (void *)-1;
1950 rhs[0].off += extra_off;
1951 rhs[0].op0 = int_const_binop (PLUS_EXPR, rhs[0].op0,
1952 build_int_cst (TREE_TYPE (rhs[0].op0),
1953 extra_off));
1956 /* We need to pre-pend vr->operands[0..i] to rhs. */
1957 vec<vn_reference_op_s> old = vr->operands;
1958 if (i + 1 + rhs.length () > vr->operands.length ())
1960 vr->operands.safe_grow (i + 1 + rhs.length ());
1961 if (old == shared_lookup_references)
1962 shared_lookup_references = vr->operands;
1964 else
1965 vr->operands.truncate (i + 1 + rhs.length ());
1966 FOR_EACH_VEC_ELT (rhs, j, vro)
1967 vr->operands[i + 1 + j] = *vro;
1968 vr->operands = valueize_refs (vr->operands);
1969 if (old == shared_lookup_references)
1970 shared_lookup_references = vr->operands;
1971 vr->hashcode = vn_reference_compute_hash (vr);
1973 /* Try folding the new reference to a constant. */
1974 tree val = fully_constant_vn_reference_p (vr);
1975 if (val)
1976 return vn_reference_lookup_or_insert_for_pieces
1977 (vuse, vr->set, vr->type, vr->operands, val);
1979 /* Adjust *ref from the new operands. */
1980 if (!ao_ref_init_from_vn_reference (&r, vr->set, vr->type, vr->operands))
1981 return (void *)-1;
1982 /* This can happen with bitfields. */
1983 if (ref->size != r.size)
1984 return (void *)-1;
1985 *ref = r;
1987 /* Do not update last seen VUSE after translating. */
1988 last_vuse_ptr = NULL;
1990 /* Keep looking for the adjusted *REF / VR pair. */
1991 return NULL;
1994 /* 6) For memcpy copies translate the reference through them if
1995 the copy kills ref. */
1996 else if (vn_walk_kind == VN_WALKREWRITE
1997 && is_gimple_reg_type (vr->type)
1998 /* ??? Handle BCOPY as well. */
1999 && (gimple_call_builtin_p (def_stmt, BUILT_IN_MEMCPY)
2000 || gimple_call_builtin_p (def_stmt, BUILT_IN_MEMPCPY)
2001 || gimple_call_builtin_p (def_stmt, BUILT_IN_MEMMOVE))
2002 && (TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR
2003 || TREE_CODE (gimple_call_arg (def_stmt, 0)) == SSA_NAME)
2004 && (TREE_CODE (gimple_call_arg (def_stmt, 1)) == ADDR_EXPR
2005 || TREE_CODE (gimple_call_arg (def_stmt, 1)) == SSA_NAME)
2006 && tree_fits_uhwi_p (gimple_call_arg (def_stmt, 2)))
2008 tree lhs, rhs;
2009 ao_ref r;
2010 HOST_WIDE_INT rhs_offset, copy_size, lhs_offset;
2011 vn_reference_op_s op;
2012 HOST_WIDE_INT at;
2015 /* Only handle non-variable, addressable refs. */
2016 if (ref->size != maxsize
2017 || offset % BITS_PER_UNIT != 0
2018 || ref->size % BITS_PER_UNIT != 0)
2019 return (void *)-1;
2021 /* Extract a pointer base and an offset for the destination. */
2022 lhs = gimple_call_arg (def_stmt, 0);
2023 lhs_offset = 0;
2024 if (TREE_CODE (lhs) == SSA_NAME)
2026 lhs = SSA_VAL (lhs);
2027 if (TREE_CODE (lhs) == SSA_NAME)
2029 gimple def_stmt = SSA_NAME_DEF_STMT (lhs);
2030 if (gimple_assign_single_p (def_stmt)
2031 && gimple_assign_rhs_code (def_stmt) == ADDR_EXPR)
2032 lhs = gimple_assign_rhs1 (def_stmt);
2035 if (TREE_CODE (lhs) == ADDR_EXPR)
2037 tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (lhs, 0),
2038 &lhs_offset);
2039 if (!tem)
2040 return (void *)-1;
2041 if (TREE_CODE (tem) == MEM_REF
2042 && tree_fits_uhwi_p (TREE_OPERAND (tem, 1)))
2044 lhs = TREE_OPERAND (tem, 0);
2045 if (TREE_CODE (lhs) == SSA_NAME)
2046 lhs = SSA_VAL (lhs);
2047 lhs_offset += tree_to_uhwi (TREE_OPERAND (tem, 1));
2049 else if (DECL_P (tem))
2050 lhs = build_fold_addr_expr (tem);
2051 else
2052 return (void *)-1;
2054 if (TREE_CODE (lhs) != SSA_NAME
2055 && TREE_CODE (lhs) != ADDR_EXPR)
2056 return (void *)-1;
2058 /* Extract a pointer base and an offset for the source. */
2059 rhs = gimple_call_arg (def_stmt, 1);
2060 rhs_offset = 0;
2061 if (TREE_CODE (rhs) == SSA_NAME)
2062 rhs = SSA_VAL (rhs);
2063 if (TREE_CODE (rhs) == ADDR_EXPR)
2065 tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs, 0),
2066 &rhs_offset);
2067 if (!tem)
2068 return (void *)-1;
2069 if (TREE_CODE (tem) == MEM_REF
2070 && tree_fits_uhwi_p (TREE_OPERAND (tem, 1)))
2072 rhs = TREE_OPERAND (tem, 0);
2073 rhs_offset += tree_to_uhwi (TREE_OPERAND (tem, 1));
2075 else if (DECL_P (tem))
2076 rhs = build_fold_addr_expr (tem);
2077 else
2078 return (void *)-1;
2080 if (TREE_CODE (rhs) != SSA_NAME
2081 && TREE_CODE (rhs) != ADDR_EXPR)
2082 return (void *)-1;
2084 copy_size = tree_to_uhwi (gimple_call_arg (def_stmt, 2));
2086 /* The bases of the destination and the references have to agree. */
2087 if ((TREE_CODE (base) != MEM_REF
2088 && !DECL_P (base))
2089 || (TREE_CODE (base) == MEM_REF
2090 && (TREE_OPERAND (base, 0) != lhs
2091 || !tree_fits_uhwi_p (TREE_OPERAND (base, 1))))
2092 || (DECL_P (base)
2093 && (TREE_CODE (lhs) != ADDR_EXPR
2094 || TREE_OPERAND (lhs, 0) != base)))
2095 return (void *)-1;
2097 at = offset / BITS_PER_UNIT;
2098 if (TREE_CODE (base) == MEM_REF)
2099 at += tree_to_uhwi (TREE_OPERAND (base, 1));
2100 /* If the access is completely outside of the memcpy destination
2101 area there is no aliasing. */
2102 if (lhs_offset >= at + maxsize / BITS_PER_UNIT
2103 || lhs_offset + copy_size <= at)
2104 return NULL;
2105 /* And the access has to be contained within the memcpy destination. */
2106 if (lhs_offset > at
2107 || lhs_offset + copy_size < at + maxsize / BITS_PER_UNIT)
2108 return (void *)-1;
2110 /* Make room for 2 operands in the new reference. */
2111 if (vr->operands.length () < 2)
2113 vec<vn_reference_op_s> old = vr->operands;
2114 vr->operands.safe_grow_cleared (2);
2115 if (old == shared_lookup_references
2116 && vr->operands != old)
2117 shared_lookup_references = vr->operands;
2119 else
2120 vr->operands.truncate (2);
2122 /* The looked-through reference is a simple MEM_REF. */
2123 memset (&op, 0, sizeof (op));
2124 op.type = vr->type;
2125 op.opcode = MEM_REF;
2126 op.op0 = build_int_cst (ptr_type_node, at - rhs_offset);
2127 op.off = at - lhs_offset + rhs_offset;
2128 vr->operands[0] = op;
2129 op.type = TREE_TYPE (rhs);
2130 op.opcode = TREE_CODE (rhs);
2131 op.op0 = rhs;
2132 op.off = -1;
2133 vr->operands[1] = op;
2134 vr->hashcode = vn_reference_compute_hash (vr);
2136 /* Adjust *ref from the new operands. */
2137 if (!ao_ref_init_from_vn_reference (&r, vr->set, vr->type, vr->operands))
2138 return (void *)-1;
2139 /* This can happen with bitfields. */
2140 if (ref->size != r.size)
2141 return (void *)-1;
2142 *ref = r;
2144 /* Do not update last seen VUSE after translating. */
2145 last_vuse_ptr = NULL;
2147 /* Keep looking for the adjusted *REF / VR pair. */
2148 return NULL;
2151 /* Bail out and stop walking. */
2152 return (void *)-1;
2155 /* Lookup a reference operation by it's parts, in the current hash table.
2156 Returns the resulting value number if it exists in the hash table,
2157 NULL_TREE otherwise. VNRESULT will be filled in with the actual
2158 vn_reference_t stored in the hashtable if something is found. */
2160 tree
2161 vn_reference_lookup_pieces (tree vuse, alias_set_type set, tree type,
2162 vec<vn_reference_op_s> operands,
2163 vn_reference_t *vnresult, vn_lookup_kind kind)
2165 struct vn_reference_s vr1;
2166 vn_reference_t tmp;
2167 tree cst;
2169 if (!vnresult)
2170 vnresult = &tmp;
2171 *vnresult = NULL;
2173 vr1.vuse = vuse_ssa_val (vuse);
2174 shared_lookup_references.truncate (0);
2175 shared_lookup_references.safe_grow (operands.length ());
2176 memcpy (shared_lookup_references.address (),
2177 operands.address (),
2178 sizeof (vn_reference_op_s)
2179 * operands.length ());
2180 vr1.operands = operands = shared_lookup_references
2181 = valueize_refs (shared_lookup_references);
2182 vr1.type = type;
2183 vr1.set = set;
2184 vr1.hashcode = vn_reference_compute_hash (&vr1);
2185 if ((cst = fully_constant_vn_reference_p (&vr1)))
2186 return cst;
2188 vn_reference_lookup_1 (&vr1, vnresult);
2189 if (!*vnresult
2190 && kind != VN_NOWALK
2191 && vr1.vuse)
2193 ao_ref r;
2194 vn_walk_kind = kind;
2195 if (ao_ref_init_from_vn_reference (&r, set, type, vr1.operands))
2196 *vnresult =
2197 (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse,
2198 vn_reference_lookup_2,
2199 vn_reference_lookup_3,
2200 vuse_ssa_val, &vr1);
2201 gcc_checking_assert (vr1.operands == shared_lookup_references);
2204 if (*vnresult)
2205 return (*vnresult)->result;
2207 return NULL_TREE;
2210 /* Lookup OP in the current hash table, and return the resulting value
2211 number if it exists in the hash table. Return NULL_TREE if it does
2212 not exist in the hash table or if the result field of the structure
2213 was NULL.. VNRESULT will be filled in with the vn_reference_t
2214 stored in the hashtable if one exists. */
2216 tree
2217 vn_reference_lookup (tree op, tree vuse, vn_lookup_kind kind,
2218 vn_reference_t *vnresult)
2220 vec<vn_reference_op_s> operands;
2221 struct vn_reference_s vr1;
2222 tree cst;
2223 bool valuezied_anything;
2225 if (vnresult)
2226 *vnresult = NULL;
2228 vr1.vuse = vuse_ssa_val (vuse);
2229 vr1.operands = operands
2230 = valueize_shared_reference_ops_from_ref (op, &valuezied_anything);
2231 vr1.type = TREE_TYPE (op);
2232 vr1.set = get_alias_set (op);
2233 vr1.hashcode = vn_reference_compute_hash (&vr1);
2234 if ((cst = fully_constant_vn_reference_p (&vr1)))
2235 return cst;
2237 if (kind != VN_NOWALK
2238 && vr1.vuse)
2240 vn_reference_t wvnresult;
2241 ao_ref r;
2242 /* Make sure to use a valueized reference if we valueized anything.
2243 Otherwise preserve the full reference for advanced TBAA. */
2244 if (!valuezied_anything
2245 || !ao_ref_init_from_vn_reference (&r, vr1.set, vr1.type,
2246 vr1.operands))
2247 ao_ref_init (&r, op);
2248 vn_walk_kind = kind;
2249 wvnresult =
2250 (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse,
2251 vn_reference_lookup_2,
2252 vn_reference_lookup_3,
2253 vuse_ssa_val, &vr1);
2254 gcc_checking_assert (vr1.operands == shared_lookup_references);
2255 if (wvnresult)
2257 if (vnresult)
2258 *vnresult = wvnresult;
2259 return wvnresult->result;
2262 return NULL_TREE;
2265 return vn_reference_lookup_1 (&vr1, vnresult);
2268 /* Lookup CALL in the current hash table and return the entry in
2269 *VNRESULT if found. Populates *VR for the hashtable lookup. */
2271 void
2272 vn_reference_lookup_call (gcall *call, vn_reference_t *vnresult,
2273 vn_reference_t vr)
2275 if (vnresult)
2276 *vnresult = NULL;
2278 tree vuse = gimple_vuse (call);
2280 vr->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
2281 vr->operands = valueize_shared_reference_ops_from_call (call);
2282 vr->type = gimple_expr_type (call);
2283 vr->set = 0;
2284 vr->hashcode = vn_reference_compute_hash (vr);
2285 vn_reference_lookup_1 (vr, vnresult);
2288 /* Insert OP into the current hash table with a value number of
2289 RESULT, and return the resulting reference structure we created. */
2291 static vn_reference_t
2292 vn_reference_insert (tree op, tree result, tree vuse, tree vdef)
2294 vn_reference_s **slot;
2295 vn_reference_t vr1;
2296 bool tem;
2298 vr1 = current_info->references_pool->allocate ();
2299 if (TREE_CODE (result) == SSA_NAME)
2300 vr1->value_id = VN_INFO (result)->value_id;
2301 else
2302 vr1->value_id = get_or_alloc_constant_value_id (result);
2303 vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
2304 vr1->operands = valueize_shared_reference_ops_from_ref (op, &tem).copy ();
2305 vr1->type = TREE_TYPE (op);
2306 vr1->set = get_alias_set (op);
2307 vr1->hashcode = vn_reference_compute_hash (vr1);
2308 vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result;
2309 vr1->result_vdef = vdef;
2311 slot = current_info->references->find_slot_with_hash (vr1, vr1->hashcode,
2312 INSERT);
2314 /* Because we lookup stores using vuses, and value number failures
2315 using the vdefs (see visit_reference_op_store for how and why),
2316 it's possible that on failure we may try to insert an already
2317 inserted store. This is not wrong, there is no ssa name for a
2318 store that we could use as a differentiator anyway. Thus, unlike
2319 the other lookup functions, you cannot gcc_assert (!*slot)
2320 here. */
2322 /* But free the old slot in case of a collision. */
2323 if (*slot)
2324 free_reference (*slot);
2326 *slot = vr1;
2327 return vr1;
2330 /* Insert a reference by it's pieces into the current hash table with
2331 a value number of RESULT. Return the resulting reference
2332 structure we created. */
2334 vn_reference_t
2335 vn_reference_insert_pieces (tree vuse, alias_set_type set, tree type,
2336 vec<vn_reference_op_s> operands,
2337 tree result, unsigned int value_id)
2340 vn_reference_s **slot;
2341 vn_reference_t vr1;
2343 vr1 = current_info->references_pool->allocate ();
2344 vr1->value_id = value_id;
2345 vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
2346 vr1->operands = valueize_refs (operands);
2347 vr1->type = type;
2348 vr1->set = set;
2349 vr1->hashcode = vn_reference_compute_hash (vr1);
2350 if (result && TREE_CODE (result) == SSA_NAME)
2351 result = SSA_VAL (result);
2352 vr1->result = result;
2354 slot = current_info->references->find_slot_with_hash (vr1, vr1->hashcode,
2355 INSERT);
2357 /* At this point we should have all the things inserted that we have
2358 seen before, and we should never try inserting something that
2359 already exists. */
2360 gcc_assert (!*slot);
2361 if (*slot)
2362 free_reference (*slot);
2364 *slot = vr1;
2365 return vr1;
2368 /* Compute and return the hash value for nary operation VBO1. */
2370 static hashval_t
2371 vn_nary_op_compute_hash (const vn_nary_op_t vno1)
2373 inchash::hash hstate;
2374 unsigned i;
2376 for (i = 0; i < vno1->length; ++i)
2377 if (TREE_CODE (vno1->op[i]) == SSA_NAME)
2378 vno1->op[i] = SSA_VAL (vno1->op[i]);
2380 if (vno1->length == 2
2381 && commutative_tree_code (vno1->opcode)
2382 && tree_swap_operands_p (vno1->op[0], vno1->op[1], false))
2383 std::swap (vno1->op[0], vno1->op[1]);
2385 hstate.add_int (vno1->opcode);
2386 for (i = 0; i < vno1->length; ++i)
2387 inchash::add_expr (vno1->op[i], hstate);
2389 return hstate.end ();
2392 /* Compare nary operations VNO1 and VNO2 and return true if they are
2393 equivalent. */
2395 bool
2396 vn_nary_op_eq (const_vn_nary_op_t const vno1, const_vn_nary_op_t const vno2)
2398 unsigned i;
2400 if (vno1->hashcode != vno2->hashcode)
2401 return false;
2403 if (vno1->length != vno2->length)
2404 return false;
2406 if (vno1->opcode != vno2->opcode
2407 || !types_compatible_p (vno1->type, vno2->type))
2408 return false;
2410 for (i = 0; i < vno1->length; ++i)
2411 if (!expressions_equal_p (vno1->op[i], vno2->op[i]))
2412 return false;
2414 return true;
2417 /* Initialize VNO from the pieces provided. */
2419 static void
2420 init_vn_nary_op_from_pieces (vn_nary_op_t vno, unsigned int length,
2421 enum tree_code code, tree type, tree *ops)
2423 vno->opcode = code;
2424 vno->length = length;
2425 vno->type = type;
2426 memcpy (&vno->op[0], ops, sizeof (tree) * length);
2429 /* Initialize VNO from OP. */
2431 static void
2432 init_vn_nary_op_from_op (vn_nary_op_t vno, tree op)
2434 unsigned i;
2436 vno->opcode = TREE_CODE (op);
2437 vno->length = TREE_CODE_LENGTH (TREE_CODE (op));
2438 vno->type = TREE_TYPE (op);
2439 for (i = 0; i < vno->length; ++i)
2440 vno->op[i] = TREE_OPERAND (op, i);
2443 /* Return the number of operands for a vn_nary ops structure from STMT. */
2445 static unsigned int
2446 vn_nary_length_from_stmt (gimple stmt)
2448 switch (gimple_assign_rhs_code (stmt))
2450 case REALPART_EXPR:
2451 case IMAGPART_EXPR:
2452 case VIEW_CONVERT_EXPR:
2453 return 1;
2455 case BIT_FIELD_REF:
2456 return 3;
2458 case CONSTRUCTOR:
2459 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
2461 default:
2462 return gimple_num_ops (stmt) - 1;
2466 /* Initialize VNO from STMT. */
2468 static void
2469 init_vn_nary_op_from_stmt (vn_nary_op_t vno, gimple stmt)
2471 unsigned i;
2473 vno->opcode = gimple_assign_rhs_code (stmt);
2474 vno->type = gimple_expr_type (stmt);
2475 switch (vno->opcode)
2477 case REALPART_EXPR:
2478 case IMAGPART_EXPR:
2479 case VIEW_CONVERT_EXPR:
2480 vno->length = 1;
2481 vno->op[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
2482 break;
2484 case BIT_FIELD_REF:
2485 vno->length = 3;
2486 vno->op[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
2487 vno->op[1] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 1);
2488 vno->op[2] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 2);
2489 break;
2491 case CONSTRUCTOR:
2492 vno->length = CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
2493 for (i = 0; i < vno->length; ++i)
2494 vno->op[i] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt), i)->value;
2495 break;
2497 default:
2498 gcc_checking_assert (!gimple_assign_single_p (stmt));
2499 vno->length = gimple_num_ops (stmt) - 1;
2500 for (i = 0; i < vno->length; ++i)
2501 vno->op[i] = gimple_op (stmt, i + 1);
2505 /* Compute the hashcode for VNO and look for it in the hash table;
2506 return the resulting value number if it exists in the hash table.
2507 Return NULL_TREE if it does not exist in the hash table or if the
2508 result field of the operation is NULL. VNRESULT will contain the
2509 vn_nary_op_t from the hashtable if it exists. */
2511 static tree
2512 vn_nary_op_lookup_1 (vn_nary_op_t vno, vn_nary_op_t *vnresult)
2514 vn_nary_op_s **slot;
2516 if (vnresult)
2517 *vnresult = NULL;
2519 vno->hashcode = vn_nary_op_compute_hash (vno);
2520 slot = current_info->nary->find_slot_with_hash (vno, vno->hashcode,
2521 NO_INSERT);
2522 if (!slot && current_info == optimistic_info)
2523 slot = valid_info->nary->find_slot_with_hash (vno, vno->hashcode,
2524 NO_INSERT);
2525 if (!slot)
2526 return NULL_TREE;
2527 if (vnresult)
2528 *vnresult = *slot;
2529 return (*slot)->result;
2532 /* Lookup a n-ary operation by its pieces and return the resulting value
2533 number if it exists in the hash table. Return NULL_TREE if it does
2534 not exist in the hash table or if the result field of the operation
2535 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2536 if it exists. */
2538 tree
2539 vn_nary_op_lookup_pieces (unsigned int length, enum tree_code code,
2540 tree type, tree *ops, vn_nary_op_t *vnresult)
2542 vn_nary_op_t vno1 = XALLOCAVAR (struct vn_nary_op_s,
2543 sizeof_vn_nary_op (length));
2544 init_vn_nary_op_from_pieces (vno1, length, code, type, ops);
2545 return vn_nary_op_lookup_1 (vno1, vnresult);
2548 /* Lookup OP in the current hash table, and return the resulting value
2549 number if it exists in the hash table. Return NULL_TREE if it does
2550 not exist in the hash table or if the result field of the operation
2551 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2552 if it exists. */
2554 tree
2555 vn_nary_op_lookup (tree op, vn_nary_op_t *vnresult)
2557 vn_nary_op_t vno1
2558 = XALLOCAVAR (struct vn_nary_op_s,
2559 sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op))));
2560 init_vn_nary_op_from_op (vno1, op);
2561 return vn_nary_op_lookup_1 (vno1, vnresult);
2564 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2565 value number if it exists in the hash table. Return NULL_TREE if
2566 it does not exist in the hash table. VNRESULT will contain the
2567 vn_nary_op_t from the hashtable if it exists. */
2569 tree
2570 vn_nary_op_lookup_stmt (gimple stmt, vn_nary_op_t *vnresult)
2572 vn_nary_op_t vno1
2573 = XALLOCAVAR (struct vn_nary_op_s,
2574 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt)));
2575 init_vn_nary_op_from_stmt (vno1, stmt);
2576 return vn_nary_op_lookup_1 (vno1, vnresult);
2579 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
2581 static vn_nary_op_t
2582 alloc_vn_nary_op_noinit (unsigned int length, struct obstack *stack)
2584 return (vn_nary_op_t) obstack_alloc (stack, sizeof_vn_nary_op (length));
2587 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
2588 obstack. */
2590 static vn_nary_op_t
2591 alloc_vn_nary_op (unsigned int length, tree result, unsigned int value_id)
2593 vn_nary_op_t vno1 = alloc_vn_nary_op_noinit (length,
2594 &current_info->nary_obstack);
2596 vno1->value_id = value_id;
2597 vno1->length = length;
2598 vno1->result = result;
2600 return vno1;
2603 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
2604 VNO->HASHCODE first. */
2606 static vn_nary_op_t
2607 vn_nary_op_insert_into (vn_nary_op_t vno, vn_nary_op_table_type *table,
2608 bool compute_hash)
2610 vn_nary_op_s **slot;
2612 if (compute_hash)
2613 vno->hashcode = vn_nary_op_compute_hash (vno);
2615 slot = table->find_slot_with_hash (vno, vno->hashcode, INSERT);
2616 gcc_assert (!*slot);
2618 *slot = vno;
2619 return vno;
2622 /* Insert a n-ary operation into the current hash table using it's
2623 pieces. Return the vn_nary_op_t structure we created and put in
2624 the hashtable. */
2626 vn_nary_op_t
2627 vn_nary_op_insert_pieces (unsigned int length, enum tree_code code,
2628 tree type, tree *ops,
2629 tree result, unsigned int value_id)
2631 vn_nary_op_t vno1 = alloc_vn_nary_op (length, result, value_id);
2632 init_vn_nary_op_from_pieces (vno1, length, code, type, ops);
2633 return vn_nary_op_insert_into (vno1, current_info->nary, true);
2636 /* Insert OP into the current hash table with a value number of
2637 RESULT. Return the vn_nary_op_t structure we created and put in
2638 the hashtable. */
2640 vn_nary_op_t
2641 vn_nary_op_insert (tree op, tree result)
2643 unsigned length = TREE_CODE_LENGTH (TREE_CODE (op));
2644 vn_nary_op_t vno1;
2646 vno1 = alloc_vn_nary_op (length, result, VN_INFO (result)->value_id);
2647 init_vn_nary_op_from_op (vno1, op);
2648 return vn_nary_op_insert_into (vno1, current_info->nary, true);
2651 /* Insert the rhs of STMT into the current hash table with a value number of
2652 RESULT. */
2654 vn_nary_op_t
2655 vn_nary_op_insert_stmt (gimple stmt, tree result)
2657 vn_nary_op_t vno1
2658 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt),
2659 result, VN_INFO (result)->value_id);
2660 init_vn_nary_op_from_stmt (vno1, stmt);
2661 return vn_nary_op_insert_into (vno1, current_info->nary, true);
2664 /* Compute a hashcode for PHI operation VP1 and return it. */
2666 static inline hashval_t
2667 vn_phi_compute_hash (vn_phi_t vp1)
2669 inchash::hash hstate (vp1->block->index);
2670 int i;
2671 tree phi1op;
2672 tree type;
2674 /* If all PHI arguments are constants we need to distinguish
2675 the PHI node via its type. */
2676 type = vp1->type;
2677 hstate.merge_hash (vn_hash_type (type));
2679 FOR_EACH_VEC_ELT (vp1->phiargs, i, phi1op)
2681 if (phi1op == VN_TOP)
2682 continue;
2683 inchash::add_expr (phi1op, hstate);
2686 return hstate.end ();
2689 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
2691 static int
2692 vn_phi_eq (const_vn_phi_t const vp1, const_vn_phi_t const vp2)
2694 if (vp1->hashcode != vp2->hashcode)
2695 return false;
2697 if (vp1->block == vp2->block)
2699 int i;
2700 tree phi1op;
2702 /* If the PHI nodes do not have compatible types
2703 they are not the same. */
2704 if (!types_compatible_p (vp1->type, vp2->type))
2705 return false;
2707 /* Any phi in the same block will have it's arguments in the
2708 same edge order, because of how we store phi nodes. */
2709 FOR_EACH_VEC_ELT (vp1->phiargs, i, phi1op)
2711 tree phi2op = vp2->phiargs[i];
2712 if (phi1op == VN_TOP || phi2op == VN_TOP)
2713 continue;
2714 if (!expressions_equal_p (phi1op, phi2op))
2715 return false;
2717 return true;
2719 return false;
2722 static vec<tree> shared_lookup_phiargs;
2724 /* Lookup PHI in the current hash table, and return the resulting
2725 value number if it exists in the hash table. Return NULL_TREE if
2726 it does not exist in the hash table. */
2728 static tree
2729 vn_phi_lookup (gimple phi)
2731 vn_phi_s **slot;
2732 struct vn_phi_s vp1;
2733 unsigned i;
2735 shared_lookup_phiargs.truncate (0);
2737 /* Canonicalize the SSA_NAME's to their value number. */
2738 for (i = 0; i < gimple_phi_num_args (phi); i++)
2740 tree def = PHI_ARG_DEF (phi, i);
2741 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
2742 shared_lookup_phiargs.safe_push (def);
2744 vp1.type = TREE_TYPE (gimple_phi_result (phi));
2745 vp1.phiargs = shared_lookup_phiargs;
2746 vp1.block = gimple_bb (phi);
2747 vp1.hashcode = vn_phi_compute_hash (&vp1);
2748 slot = current_info->phis->find_slot_with_hash (&vp1, vp1.hashcode,
2749 NO_INSERT);
2750 if (!slot && current_info == optimistic_info)
2751 slot = valid_info->phis->find_slot_with_hash (&vp1, vp1.hashcode,
2752 NO_INSERT);
2753 if (!slot)
2754 return NULL_TREE;
2755 return (*slot)->result;
2758 /* Insert PHI into the current hash table with a value number of
2759 RESULT. */
2761 static vn_phi_t
2762 vn_phi_insert (gimple phi, tree result)
2764 vn_phi_s **slot;
2765 vn_phi_t vp1 = current_info->phis_pool->allocate ();
2766 unsigned i;
2767 vec<tree> args = vNULL;
2769 /* Canonicalize the SSA_NAME's to their value number. */
2770 for (i = 0; i < gimple_phi_num_args (phi); i++)
2772 tree def = PHI_ARG_DEF (phi, i);
2773 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
2774 args.safe_push (def);
2776 vp1->value_id = VN_INFO (result)->value_id;
2777 vp1->type = TREE_TYPE (gimple_phi_result (phi));
2778 vp1->phiargs = args;
2779 vp1->block = gimple_bb (phi);
2780 vp1->result = result;
2781 vp1->hashcode = vn_phi_compute_hash (vp1);
2783 slot = current_info->phis->find_slot_with_hash (vp1, vp1->hashcode, INSERT);
2785 /* Because we iterate over phi operations more than once, it's
2786 possible the slot might already exist here, hence no assert.*/
2787 *slot = vp1;
2788 return vp1;
2792 /* Print set of components in strongly connected component SCC to OUT. */
2794 static void
2795 print_scc (FILE *out, vec<tree> scc)
2797 tree var;
2798 unsigned int i;
2800 fprintf (out, "SCC consists of:");
2801 FOR_EACH_VEC_ELT (scc, i, var)
2803 fprintf (out, " ");
2804 print_generic_expr (out, var, 0);
2806 fprintf (out, "\n");
2809 /* Set the value number of FROM to TO, return true if it has changed
2810 as a result. */
2812 static inline bool
2813 set_ssa_val_to (tree from, tree to)
2815 tree currval = SSA_VAL (from);
2816 HOST_WIDE_INT toff, coff;
2818 /* The only thing we allow as value numbers are ssa_names
2819 and invariants. So assert that here. We don't allow VN_TOP
2820 as visiting a stmt should produce a value-number other than
2821 that.
2822 ??? Still VN_TOP can happen for unreachable code, so force
2823 it to varying in that case. Not all code is prepared to
2824 get VN_TOP on valueization. */
2825 if (to == VN_TOP)
2827 if (dump_file && (dump_flags & TDF_DETAILS))
2828 fprintf (dump_file, "Forcing value number to varying on "
2829 "receiving VN_TOP\n");
2830 to = from;
2833 gcc_assert (to != NULL_TREE
2834 && ((TREE_CODE (to) == SSA_NAME
2835 && (to == from || SSA_VAL (to) == to))
2836 || is_gimple_min_invariant (to)));
2838 if (from != to)
2840 if (currval == from)
2842 if (dump_file && (dump_flags & TDF_DETAILS))
2844 fprintf (dump_file, "Not changing value number of ");
2845 print_generic_expr (dump_file, from, 0);
2846 fprintf (dump_file, " from VARYING to ");
2847 print_generic_expr (dump_file, to, 0);
2848 fprintf (dump_file, "\n");
2850 return false;
2852 else if (TREE_CODE (to) == SSA_NAME
2853 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to))
2854 to = from;
2857 if (dump_file && (dump_flags & TDF_DETAILS))
2859 fprintf (dump_file, "Setting value number of ");
2860 print_generic_expr (dump_file, from, 0);
2861 fprintf (dump_file, " to ");
2862 print_generic_expr (dump_file, to, 0);
2865 if (currval != to
2866 && !operand_equal_p (currval, to, 0)
2867 /* ??? For addresses involving volatile objects or types operand_equal_p
2868 does not reliably detect ADDR_EXPRs as equal. We know we are only
2869 getting invariant gimple addresses here, so can use
2870 get_addr_base_and_unit_offset to do this comparison. */
2871 && !(TREE_CODE (currval) == ADDR_EXPR
2872 && TREE_CODE (to) == ADDR_EXPR
2873 && (get_addr_base_and_unit_offset (TREE_OPERAND (currval, 0), &coff)
2874 == get_addr_base_and_unit_offset (TREE_OPERAND (to, 0), &toff))
2875 && coff == toff))
2877 VN_INFO (from)->valnum = to;
2878 if (dump_file && (dump_flags & TDF_DETAILS))
2879 fprintf (dump_file, " (changed)\n");
2880 return true;
2882 if (dump_file && (dump_flags & TDF_DETAILS))
2883 fprintf (dump_file, "\n");
2884 return false;
2887 /* Mark as processed all the definitions in the defining stmt of USE, or
2888 the USE itself. */
2890 static void
2891 mark_use_processed (tree use)
2893 ssa_op_iter iter;
2894 def_operand_p defp;
2895 gimple stmt = SSA_NAME_DEF_STMT (use);
2897 if (SSA_NAME_IS_DEFAULT_DEF (use) || gimple_code (stmt) == GIMPLE_PHI)
2899 VN_INFO (use)->use_processed = true;
2900 return;
2903 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
2905 tree def = DEF_FROM_PTR (defp);
2907 VN_INFO (def)->use_processed = true;
2911 /* Set all definitions in STMT to value number to themselves.
2912 Return true if a value number changed. */
2914 static bool
2915 defs_to_varying (gimple stmt)
2917 bool changed = false;
2918 ssa_op_iter iter;
2919 def_operand_p defp;
2921 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
2923 tree def = DEF_FROM_PTR (defp);
2924 changed |= set_ssa_val_to (def, def);
2926 return changed;
2929 static bool expr_has_constants (tree expr);
2931 /* Visit a copy between LHS and RHS, return true if the value number
2932 changed. */
2934 static bool
2935 visit_copy (tree lhs, tree rhs)
2937 /* The copy may have a more interesting constant filled expression
2938 (we don't, since we know our RHS is just an SSA name). */
2939 VN_INFO (lhs)->has_constants = VN_INFO (rhs)->has_constants;
2940 VN_INFO (lhs)->expr = VN_INFO (rhs)->expr;
2942 /* And finally valueize. */
2943 rhs = SSA_VAL (rhs);
2945 return set_ssa_val_to (lhs, rhs);
2948 /* Visit a nary operator RHS, value number it, and return true if the
2949 value number of LHS has changed as a result. */
2951 static bool
2952 visit_nary_op (tree lhs, gimple stmt)
2954 bool changed = false;
2955 tree result = vn_nary_op_lookup_stmt (stmt, NULL);
2957 if (result)
2958 changed = set_ssa_val_to (lhs, result);
2959 else
2961 changed = set_ssa_val_to (lhs, lhs);
2962 vn_nary_op_insert_stmt (stmt, lhs);
2965 return changed;
2968 /* Visit a call STMT storing into LHS. Return true if the value number
2969 of the LHS has changed as a result. */
2971 static bool
2972 visit_reference_op_call (tree lhs, gcall *stmt)
2974 bool changed = false;
2975 struct vn_reference_s vr1;
2976 vn_reference_t vnresult = NULL;
2977 tree vdef = gimple_vdef (stmt);
2979 /* Non-ssa lhs is handled in copy_reference_ops_from_call. */
2980 if (lhs && TREE_CODE (lhs) != SSA_NAME)
2981 lhs = NULL_TREE;
2983 vn_reference_lookup_call (stmt, &vnresult, &vr1);
2984 if (vnresult)
2986 if (vnresult->result_vdef && vdef)
2987 changed |= set_ssa_val_to (vdef, vnresult->result_vdef);
2989 if (!vnresult->result && lhs)
2990 vnresult->result = lhs;
2992 if (vnresult->result && lhs)
2994 changed |= set_ssa_val_to (lhs, vnresult->result);
2996 if (VN_INFO (vnresult->result)->has_constants)
2997 VN_INFO (lhs)->has_constants = true;
3000 else
3002 vn_reference_t vr2;
3003 vn_reference_s **slot;
3004 if (vdef)
3005 changed |= set_ssa_val_to (vdef, vdef);
3006 if (lhs)
3007 changed |= set_ssa_val_to (lhs, lhs);
3008 vr2 = current_info->references_pool->allocate ();
3009 vr2->vuse = vr1.vuse;
3010 /* As we are not walking the virtual operand chain we know the
3011 shared_lookup_references are still original so we can re-use
3012 them here. */
3013 vr2->operands = vr1.operands.copy ();
3014 vr2->type = vr1.type;
3015 vr2->set = vr1.set;
3016 vr2->hashcode = vr1.hashcode;
3017 vr2->result = lhs;
3018 vr2->result_vdef = vdef;
3019 slot = current_info->references->find_slot_with_hash (vr2, vr2->hashcode,
3020 INSERT);
3021 gcc_assert (!*slot);
3022 *slot = vr2;
3025 return changed;
3028 /* Visit a load from a reference operator RHS, part of STMT, value number it,
3029 and return true if the value number of the LHS has changed as a result. */
3031 static bool
3032 visit_reference_op_load (tree lhs, tree op, gimple stmt)
3034 bool changed = false;
3035 tree last_vuse;
3036 tree result;
3038 last_vuse = gimple_vuse (stmt);
3039 last_vuse_ptr = &last_vuse;
3040 result = vn_reference_lookup (op, gimple_vuse (stmt),
3041 default_vn_walk_kind, NULL);
3042 last_vuse_ptr = NULL;
3044 /* We handle type-punning through unions by value-numbering based
3045 on offset and size of the access. Be prepared to handle a
3046 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
3047 if (result
3048 && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (op)))
3050 /* We will be setting the value number of lhs to the value number
3051 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
3052 So first simplify and lookup this expression to see if it
3053 is already available. */
3054 tree val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (op), result);
3055 if ((CONVERT_EXPR_P (val)
3056 || TREE_CODE (val) == VIEW_CONVERT_EXPR)
3057 && TREE_CODE (TREE_OPERAND (val, 0)) == SSA_NAME)
3059 tree tem = vn_get_expr_for (TREE_OPERAND (val, 0));
3060 if ((CONVERT_EXPR_P (tem)
3061 || TREE_CODE (tem) == VIEW_CONVERT_EXPR)
3062 && (tem = fold_unary_ignore_overflow (TREE_CODE (val),
3063 TREE_TYPE (val), tem)))
3064 val = tem;
3066 result = val;
3067 if (!is_gimple_min_invariant (val)
3068 && TREE_CODE (val) != SSA_NAME)
3069 result = vn_nary_op_lookup (val, NULL);
3070 /* If the expression is not yet available, value-number lhs to
3071 a new SSA_NAME we create. */
3072 if (!result)
3074 result = make_temp_ssa_name (TREE_TYPE (lhs), gimple_build_nop (),
3075 "vntemp");
3076 /* Initialize value-number information properly. */
3077 VN_INFO_GET (result)->valnum = result;
3078 VN_INFO (result)->value_id = get_next_value_id ();
3079 VN_INFO (result)->expr = val;
3080 VN_INFO (result)->has_constants = expr_has_constants (val);
3081 VN_INFO (result)->needs_insertion = true;
3082 /* As all "inserted" statements are singleton SCCs, insert
3083 to the valid table. This is strictly needed to
3084 avoid re-generating new value SSA_NAMEs for the same
3085 expression during SCC iteration over and over (the
3086 optimistic table gets cleared after each iteration).
3087 We do not need to insert into the optimistic table, as
3088 lookups there will fall back to the valid table. */
3089 if (current_info == optimistic_info)
3091 current_info = valid_info;
3092 vn_nary_op_insert (val, result);
3093 current_info = optimistic_info;
3095 else
3096 vn_nary_op_insert (val, result);
3097 if (dump_file && (dump_flags & TDF_DETAILS))
3099 fprintf (dump_file, "Inserting name ");
3100 print_generic_expr (dump_file, result, 0);
3101 fprintf (dump_file, " for expression ");
3102 print_generic_expr (dump_file, val, 0);
3103 fprintf (dump_file, "\n");
3108 if (result)
3110 changed = set_ssa_val_to (lhs, result);
3111 if (TREE_CODE (result) == SSA_NAME
3112 && VN_INFO (result)->has_constants)
3114 VN_INFO (lhs)->expr = VN_INFO (result)->expr;
3115 VN_INFO (lhs)->has_constants = true;
3118 else
3120 changed = set_ssa_val_to (lhs, lhs);
3121 vn_reference_insert (op, lhs, last_vuse, NULL_TREE);
3124 return changed;
3128 /* Visit a store to a reference operator LHS, part of STMT, value number it,
3129 and return true if the value number of the LHS has changed as a result. */
3131 static bool
3132 visit_reference_op_store (tree lhs, tree op, gimple stmt)
3134 bool changed = false;
3135 vn_reference_t vnresult = NULL;
3136 tree result, assign;
3137 bool resultsame = false;
3138 tree vuse = gimple_vuse (stmt);
3139 tree vdef = gimple_vdef (stmt);
3141 if (TREE_CODE (op) == SSA_NAME)
3142 op = SSA_VAL (op);
3144 /* First we want to lookup using the *vuses* from the store and see
3145 if there the last store to this location with the same address
3146 had the same value.
3148 The vuses represent the memory state before the store. If the
3149 memory state, address, and value of the store is the same as the
3150 last store to this location, then this store will produce the
3151 same memory state as that store.
3153 In this case the vdef versions for this store are value numbered to those
3154 vuse versions, since they represent the same memory state after
3155 this store.
3157 Otherwise, the vdefs for the store are used when inserting into
3158 the table, since the store generates a new memory state. */
3160 result = vn_reference_lookup (lhs, vuse, VN_NOWALK, NULL);
3162 if (result)
3164 if (TREE_CODE (result) == SSA_NAME)
3165 result = SSA_VAL (result);
3166 resultsame = expressions_equal_p (result, op);
3169 if ((!result || !resultsame)
3170 /* Only perform the following when being called from PRE
3171 which embeds tail merging. */
3172 && default_vn_walk_kind == VN_WALK)
3174 assign = build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, op);
3175 vn_reference_lookup (assign, vuse, VN_NOWALK, &vnresult);
3176 if (vnresult)
3178 VN_INFO (vdef)->use_processed = true;
3179 return set_ssa_val_to (vdef, vnresult->result_vdef);
3183 if (!result || !resultsame)
3185 if (dump_file && (dump_flags & TDF_DETAILS))
3187 fprintf (dump_file, "No store match\n");
3188 fprintf (dump_file, "Value numbering store ");
3189 print_generic_expr (dump_file, lhs, 0);
3190 fprintf (dump_file, " to ");
3191 print_generic_expr (dump_file, op, 0);
3192 fprintf (dump_file, "\n");
3194 /* Have to set value numbers before insert, since insert is
3195 going to valueize the references in-place. */
3196 if (vdef)
3198 changed |= set_ssa_val_to (vdef, vdef);
3201 /* Do not insert structure copies into the tables. */
3202 if (is_gimple_min_invariant (op)
3203 || is_gimple_reg (op))
3204 vn_reference_insert (lhs, op, vdef, NULL);
3206 /* Only perform the following when being called from PRE
3207 which embeds tail merging. */
3208 if (default_vn_walk_kind == VN_WALK)
3210 assign = build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, op);
3211 vn_reference_insert (assign, lhs, vuse, vdef);
3214 else
3216 /* We had a match, so value number the vdef to have the value
3217 number of the vuse it came from. */
3219 if (dump_file && (dump_flags & TDF_DETAILS))
3220 fprintf (dump_file, "Store matched earlier value,"
3221 "value numbering store vdefs to matching vuses.\n");
3223 changed |= set_ssa_val_to (vdef, SSA_VAL (vuse));
3226 return changed;
3229 /* Visit and value number PHI, return true if the value number
3230 changed. */
3232 static bool
3233 visit_phi (gimple phi)
3235 bool changed = false;
3236 tree result;
3237 tree sameval = VN_TOP;
3238 bool allsame = true;
3240 /* TODO: We could check for this in init_sccvn, and replace this
3241 with a gcc_assert. */
3242 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
3243 return set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
3245 /* See if all non-TOP arguments have the same value. TOP is
3246 equivalent to everything, so we can ignore it. */
3247 edge_iterator ei;
3248 edge e;
3249 FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds)
3250 if (e->flags & EDGE_EXECUTABLE)
3252 tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
3254 if (TREE_CODE (def) == SSA_NAME)
3255 def = SSA_VAL (def);
3256 if (def == VN_TOP)
3257 continue;
3258 if (sameval == VN_TOP)
3260 sameval = def;
3262 else
3264 if (!expressions_equal_p (def, sameval))
3266 allsame = false;
3267 break;
3272 /* If all value numbered to the same value, the phi node has that
3273 value. */
3274 if (allsame)
3275 return set_ssa_val_to (PHI_RESULT (phi), sameval);
3277 /* Otherwise, see if it is equivalent to a phi node in this block. */
3278 result = vn_phi_lookup (phi);
3279 if (result)
3280 changed = set_ssa_val_to (PHI_RESULT (phi), result);
3281 else
3283 vn_phi_insert (phi, PHI_RESULT (phi));
3284 VN_INFO (PHI_RESULT (phi))->has_constants = false;
3285 VN_INFO (PHI_RESULT (phi))->expr = PHI_RESULT (phi);
3286 changed = set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
3289 return changed;
3292 /* Return true if EXPR contains constants. */
3294 static bool
3295 expr_has_constants (tree expr)
3297 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
3299 case tcc_unary:
3300 return is_gimple_min_invariant (TREE_OPERAND (expr, 0));
3302 case tcc_binary:
3303 return is_gimple_min_invariant (TREE_OPERAND (expr, 0))
3304 || is_gimple_min_invariant (TREE_OPERAND (expr, 1));
3305 /* Constants inside reference ops are rarely interesting, but
3306 it can take a lot of looking to find them. */
3307 case tcc_reference:
3308 case tcc_declaration:
3309 return false;
3310 default:
3311 return is_gimple_min_invariant (expr);
3313 return false;
3316 /* Return true if STMT contains constants. */
3318 static bool
3319 stmt_has_constants (gimple stmt)
3321 tree tem;
3323 if (gimple_code (stmt) != GIMPLE_ASSIGN)
3324 return false;
3326 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
3328 case GIMPLE_TERNARY_RHS:
3329 tem = gimple_assign_rhs3 (stmt);
3330 if (TREE_CODE (tem) == SSA_NAME)
3331 tem = SSA_VAL (tem);
3332 if (is_gimple_min_invariant (tem))
3333 return true;
3334 /* Fallthru. */
3336 case GIMPLE_BINARY_RHS:
3337 tem = gimple_assign_rhs2 (stmt);
3338 if (TREE_CODE (tem) == SSA_NAME)
3339 tem = SSA_VAL (tem);
3340 if (is_gimple_min_invariant (tem))
3341 return true;
3342 /* Fallthru. */
3344 case GIMPLE_SINGLE_RHS:
3345 /* Constants inside reference ops are rarely interesting, but
3346 it can take a lot of looking to find them. */
3347 case GIMPLE_UNARY_RHS:
3348 tem = gimple_assign_rhs1 (stmt);
3349 if (TREE_CODE (tem) == SSA_NAME)
3350 tem = SSA_VAL (tem);
3351 return is_gimple_min_invariant (tem);
3353 default:
3354 gcc_unreachable ();
3356 return false;
3359 /* Simplify the binary expression RHS, and return the result if
3360 simplified. */
3362 static tree
3363 simplify_binary_expression (gimple stmt)
3365 tree result = NULL_TREE;
3366 tree op0 = gimple_assign_rhs1 (stmt);
3367 tree op1 = gimple_assign_rhs2 (stmt);
3368 enum tree_code code = gimple_assign_rhs_code (stmt);
3370 /* This will not catch every single case we could combine, but will
3371 catch those with constants. The goal here is to simultaneously
3372 combine constants between expressions, but avoid infinite
3373 expansion of expressions during simplification. */
3374 op0 = vn_valueize (op0);
3375 if (TREE_CODE (op0) == SSA_NAME
3376 && (VN_INFO (op0)->has_constants
3377 || TREE_CODE_CLASS (code) == tcc_comparison
3378 || code == COMPLEX_EXPR))
3379 op0 = vn_get_expr_for (op0);
3381 op1 = vn_valueize (op1);
3382 if (TREE_CODE (op1) == SSA_NAME
3383 && (VN_INFO (op1)->has_constants
3384 || code == COMPLEX_EXPR))
3385 op1 = vn_get_expr_for (op1);
3387 /* Pointer plus constant can be represented as invariant address.
3388 Do so to allow further propatation, see also tree forwprop. */
3389 if (code == POINTER_PLUS_EXPR
3390 && tree_fits_uhwi_p (op1)
3391 && TREE_CODE (op0) == ADDR_EXPR
3392 && is_gimple_min_invariant (op0))
3393 return build_invariant_address (TREE_TYPE (op0),
3394 TREE_OPERAND (op0, 0),
3395 tree_to_uhwi (op1));
3397 /* Avoid folding if nothing changed. */
3398 if (op0 == gimple_assign_rhs1 (stmt)
3399 && op1 == gimple_assign_rhs2 (stmt))
3400 return NULL_TREE;
3402 fold_defer_overflow_warnings ();
3404 result = fold_binary (code, gimple_expr_type (stmt), op0, op1);
3405 if (result)
3406 STRIP_USELESS_TYPE_CONVERSION (result);
3408 fold_undefer_overflow_warnings (result && valid_gimple_rhs_p (result),
3409 stmt, 0);
3411 /* Make sure result is not a complex expression consisting
3412 of operators of operators (IE (a + b) + (a + c))
3413 Otherwise, we will end up with unbounded expressions if
3414 fold does anything at all. */
3415 if (result && valid_gimple_rhs_p (result))
3416 return result;
3418 return NULL_TREE;
3421 /* Simplify the unary expression RHS, and return the result if
3422 simplified. */
3424 static tree
3425 simplify_unary_expression (gassign *stmt)
3427 tree result = NULL_TREE;
3428 tree orig_op0, op0 = gimple_assign_rhs1 (stmt);
3429 enum tree_code code = gimple_assign_rhs_code (stmt);
3431 /* We handle some tcc_reference codes here that are all
3432 GIMPLE_ASSIGN_SINGLE codes. */
3433 if (code == REALPART_EXPR
3434 || code == IMAGPART_EXPR
3435 || code == VIEW_CONVERT_EXPR
3436 || code == BIT_FIELD_REF)
3437 op0 = TREE_OPERAND (op0, 0);
3439 orig_op0 = op0;
3440 op0 = vn_valueize (op0);
3441 if (TREE_CODE (op0) == SSA_NAME)
3443 if (VN_INFO (op0)->has_constants)
3444 op0 = vn_get_expr_for (op0);
3445 else if (CONVERT_EXPR_CODE_P (code)
3446 || code == REALPART_EXPR
3447 || code == IMAGPART_EXPR
3448 || code == VIEW_CONVERT_EXPR
3449 || code == BIT_FIELD_REF)
3451 /* We want to do tree-combining on conversion-like expressions.
3452 Make sure we feed only SSA_NAMEs or constants to fold though. */
3453 tree tem = vn_get_expr_for (op0);
3454 if (UNARY_CLASS_P (tem)
3455 || BINARY_CLASS_P (tem)
3456 || TREE_CODE (tem) == VIEW_CONVERT_EXPR
3457 || TREE_CODE (tem) == SSA_NAME
3458 || TREE_CODE (tem) == CONSTRUCTOR
3459 || is_gimple_min_invariant (tem))
3460 op0 = tem;
3464 /* Avoid folding if nothing changed, but remember the expression. */
3465 if (op0 == orig_op0)
3466 return NULL_TREE;
3468 if (code == BIT_FIELD_REF)
3470 tree rhs = gimple_assign_rhs1 (stmt);
3471 result = fold_ternary (BIT_FIELD_REF, TREE_TYPE (rhs),
3472 op0, TREE_OPERAND (rhs, 1), TREE_OPERAND (rhs, 2));
3474 else
3475 result = fold_unary_ignore_overflow (code, gimple_expr_type (stmt), op0);
3476 if (result)
3478 STRIP_USELESS_TYPE_CONVERSION (result);
3479 if (valid_gimple_rhs_p (result))
3480 return result;
3483 return NULL_TREE;
3486 /* Try to simplify RHS using equivalences and constant folding. */
3488 static tree
3489 try_to_simplify (gassign *stmt)
3491 enum tree_code code = gimple_assign_rhs_code (stmt);
3492 tree tem;
3494 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
3495 in this case, there is no point in doing extra work. */
3496 if (code == SSA_NAME)
3497 return NULL_TREE;
3499 /* First try constant folding based on our current lattice. */
3500 tem = gimple_fold_stmt_to_constant_1 (stmt, vn_valueize, vn_valueize);
3501 if (tem
3502 && (TREE_CODE (tem) == SSA_NAME
3503 || is_gimple_min_invariant (tem)))
3504 return tem;
3506 /* If that didn't work try combining multiple statements. */
3507 switch (TREE_CODE_CLASS (code))
3509 case tcc_reference:
3510 /* Fallthrough for some unary codes that can operate on registers. */
3511 if (!(code == REALPART_EXPR
3512 || code == IMAGPART_EXPR
3513 || code == VIEW_CONVERT_EXPR
3514 || code == BIT_FIELD_REF))
3515 break;
3516 /* We could do a little more with unary ops, if they expand
3517 into binary ops, but it's debatable whether it is worth it. */
3518 case tcc_unary:
3519 return simplify_unary_expression (stmt);
3521 case tcc_comparison:
3522 case tcc_binary:
3523 return simplify_binary_expression (stmt);
3525 default:
3526 break;
3529 return NULL_TREE;
3532 /* Visit and value number USE, return true if the value number
3533 changed. */
3535 static bool
3536 visit_use (tree use)
3538 bool changed = false;
3539 gimple stmt = SSA_NAME_DEF_STMT (use);
3541 mark_use_processed (use);
3543 gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
3544 if (dump_file && (dump_flags & TDF_DETAILS)
3545 && !SSA_NAME_IS_DEFAULT_DEF (use))
3547 fprintf (dump_file, "Value numbering ");
3548 print_generic_expr (dump_file, use, 0);
3549 fprintf (dump_file, " stmt = ");
3550 print_gimple_stmt (dump_file, stmt, 0, 0);
3553 /* Handle uninitialized uses. */
3554 if (SSA_NAME_IS_DEFAULT_DEF (use))
3555 changed = set_ssa_val_to (use, use);
3556 else
3558 if (gimple_code (stmt) == GIMPLE_PHI)
3559 changed = visit_phi (stmt);
3560 else if (gimple_has_volatile_ops (stmt))
3561 changed = defs_to_varying (stmt);
3562 else if (is_gimple_assign (stmt))
3564 enum tree_code code = gimple_assign_rhs_code (stmt);
3565 tree lhs = gimple_assign_lhs (stmt);
3566 tree rhs1 = gimple_assign_rhs1 (stmt);
3567 tree simplified;
3569 /* Shortcut for copies. Simplifying copies is pointless,
3570 since we copy the expression and value they represent. */
3571 if (code == SSA_NAME
3572 && TREE_CODE (lhs) == SSA_NAME)
3574 changed = visit_copy (lhs, rhs1);
3575 goto done;
3577 simplified = try_to_simplify (as_a <gassign *> (stmt));
3578 if (simplified)
3580 if (dump_file && (dump_flags & TDF_DETAILS))
3582 fprintf (dump_file, "RHS ");
3583 print_gimple_expr (dump_file, stmt, 0, 0);
3584 fprintf (dump_file, " simplified to ");
3585 print_generic_expr (dump_file, simplified, 0);
3586 if (TREE_CODE (lhs) == SSA_NAME)
3587 fprintf (dump_file, " has constants %d\n",
3588 expr_has_constants (simplified));
3589 else
3590 fprintf (dump_file, "\n");
3593 /* Setting value numbers to constants will occasionally
3594 screw up phi congruence because constants are not
3595 uniquely associated with a single ssa name that can be
3596 looked up. */
3597 if (simplified
3598 && is_gimple_min_invariant (simplified)
3599 && TREE_CODE (lhs) == SSA_NAME)
3601 VN_INFO (lhs)->expr = simplified;
3602 VN_INFO (lhs)->has_constants = true;
3603 changed = set_ssa_val_to (lhs, simplified);
3604 goto done;
3606 else if (simplified
3607 && TREE_CODE (simplified) == SSA_NAME
3608 && TREE_CODE (lhs) == SSA_NAME)
3610 changed = visit_copy (lhs, simplified);
3611 goto done;
3613 else if (simplified)
3615 if (TREE_CODE (lhs) == SSA_NAME)
3617 VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
3618 /* We have to unshare the expression or else
3619 valuizing may change the IL stream. */
3620 VN_INFO (lhs)->expr = unshare_expr (simplified);
3623 else if (stmt_has_constants (stmt)
3624 && TREE_CODE (lhs) == SSA_NAME)
3625 VN_INFO (lhs)->has_constants = true;
3626 else if (TREE_CODE (lhs) == SSA_NAME)
3628 /* We reset expr and constantness here because we may
3629 have been value numbering optimistically, and
3630 iterating. They may become non-constant in this case,
3631 even if they were optimistically constant. */
3633 VN_INFO (lhs)->has_constants = false;
3634 VN_INFO (lhs)->expr = NULL_TREE;
3637 if ((TREE_CODE (lhs) == SSA_NAME
3638 /* We can substitute SSA_NAMEs that are live over
3639 abnormal edges with their constant value. */
3640 && !(gimple_assign_copy_p (stmt)
3641 && is_gimple_min_invariant (rhs1))
3642 && !(simplified
3643 && is_gimple_min_invariant (simplified))
3644 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
3645 /* Stores or copies from SSA_NAMEs that are live over
3646 abnormal edges are a problem. */
3647 || (code == SSA_NAME
3648 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1)))
3649 changed = defs_to_varying (stmt);
3650 else if (REFERENCE_CLASS_P (lhs)
3651 || DECL_P (lhs))
3652 changed = visit_reference_op_store (lhs, rhs1, stmt);
3653 else if (TREE_CODE (lhs) == SSA_NAME)
3655 if ((gimple_assign_copy_p (stmt)
3656 && is_gimple_min_invariant (rhs1))
3657 || (simplified
3658 && is_gimple_min_invariant (simplified)))
3660 VN_INFO (lhs)->has_constants = true;
3661 if (simplified)
3662 changed = set_ssa_val_to (lhs, simplified);
3663 else
3664 changed = set_ssa_val_to (lhs, rhs1);
3666 else
3668 /* First try to lookup the simplified expression. */
3669 if (simplified)
3671 enum gimple_rhs_class rhs_class;
3674 rhs_class = get_gimple_rhs_class (TREE_CODE (simplified));
3675 if ((rhs_class == GIMPLE_UNARY_RHS
3676 || rhs_class == GIMPLE_BINARY_RHS
3677 || rhs_class == GIMPLE_TERNARY_RHS)
3678 && valid_gimple_rhs_p (simplified))
3680 tree result = vn_nary_op_lookup (simplified, NULL);
3681 if (result)
3683 changed = set_ssa_val_to (lhs, result);
3684 goto done;
3689 /* Otherwise visit the original statement. */
3690 switch (vn_get_stmt_kind (stmt))
3692 case VN_NARY:
3693 changed = visit_nary_op (lhs, stmt);
3694 break;
3695 case VN_REFERENCE:
3696 changed = visit_reference_op_load (lhs, rhs1, stmt);
3697 break;
3698 default:
3699 changed = defs_to_varying (stmt);
3700 break;
3704 else
3705 changed = defs_to_varying (stmt);
3707 else if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
3709 tree lhs = gimple_call_lhs (stmt);
3710 if (lhs && TREE_CODE (lhs) == SSA_NAME)
3712 /* Try constant folding based on our current lattice. */
3713 tree simplified = gimple_fold_stmt_to_constant_1 (stmt,
3714 vn_valueize);
3715 if (simplified)
3717 if (dump_file && (dump_flags & TDF_DETAILS))
3719 fprintf (dump_file, "call ");
3720 print_gimple_expr (dump_file, stmt, 0, 0);
3721 fprintf (dump_file, " simplified to ");
3722 print_generic_expr (dump_file, simplified, 0);
3723 if (TREE_CODE (lhs) == SSA_NAME)
3724 fprintf (dump_file, " has constants %d\n",
3725 expr_has_constants (simplified));
3726 else
3727 fprintf (dump_file, "\n");
3730 /* Setting value numbers to constants will occasionally
3731 screw up phi congruence because constants are not
3732 uniquely associated with a single ssa name that can be
3733 looked up. */
3734 if (simplified
3735 && is_gimple_min_invariant (simplified))
3737 VN_INFO (lhs)->expr = simplified;
3738 VN_INFO (lhs)->has_constants = true;
3739 changed = set_ssa_val_to (lhs, simplified);
3740 if (gimple_vdef (stmt))
3741 changed |= set_ssa_val_to (gimple_vdef (stmt),
3742 SSA_VAL (gimple_vuse (stmt)));
3743 goto done;
3745 else if (simplified
3746 && TREE_CODE (simplified) == SSA_NAME)
3748 changed = visit_copy (lhs, simplified);
3749 if (gimple_vdef (stmt))
3750 changed |= set_ssa_val_to (gimple_vdef (stmt),
3751 SSA_VAL (gimple_vuse (stmt)));
3752 goto done;
3754 else
3756 if (stmt_has_constants (stmt))
3757 VN_INFO (lhs)->has_constants = true;
3758 else
3760 /* We reset expr and constantness here because we may
3761 have been value numbering optimistically, and
3762 iterating. They may become non-constant in this case,
3763 even if they were optimistically constant. */
3764 VN_INFO (lhs)->has_constants = false;
3765 VN_INFO (lhs)->expr = NULL_TREE;
3768 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
3770 changed = defs_to_varying (stmt);
3771 goto done;
3776 if (!gimple_call_internal_p (stmt)
3777 && (/* Calls to the same function with the same vuse
3778 and the same operands do not necessarily return the same
3779 value, unless they're pure or const. */
3780 gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST)
3781 /* If calls have a vdef, subsequent calls won't have
3782 the same incoming vuse. So, if 2 calls with vdef have the
3783 same vuse, we know they're not subsequent.
3784 We can value number 2 calls to the same function with the
3785 same vuse and the same operands which are not subsequent
3786 the same, because there is no code in the program that can
3787 compare the 2 values... */
3788 || (gimple_vdef (stmt)
3789 /* ... unless the call returns a pointer which does
3790 not alias with anything else. In which case the
3791 information that the values are distinct are encoded
3792 in the IL. */
3793 && !(gimple_call_return_flags (call_stmt) & ERF_NOALIAS)
3794 /* Only perform the following when being called from PRE
3795 which embeds tail merging. */
3796 && default_vn_walk_kind == VN_WALK)))
3797 changed = visit_reference_op_call (lhs, call_stmt);
3798 else
3799 changed = defs_to_varying (stmt);
3801 else
3802 changed = defs_to_varying (stmt);
3804 done:
3805 return changed;
3808 /* Compare two operands by reverse postorder index */
3810 static int
3811 compare_ops (const void *pa, const void *pb)
3813 const tree opa = *((const tree *)pa);
3814 const tree opb = *((const tree *)pb);
3815 gimple opstmta = SSA_NAME_DEF_STMT (opa);
3816 gimple opstmtb = SSA_NAME_DEF_STMT (opb);
3817 basic_block bba;
3818 basic_block bbb;
3820 if (gimple_nop_p (opstmta) && gimple_nop_p (opstmtb))
3821 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3822 else if (gimple_nop_p (opstmta))
3823 return -1;
3824 else if (gimple_nop_p (opstmtb))
3825 return 1;
3827 bba = gimple_bb (opstmta);
3828 bbb = gimple_bb (opstmtb);
3830 if (!bba && !bbb)
3831 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3832 else if (!bba)
3833 return -1;
3834 else if (!bbb)
3835 return 1;
3837 if (bba == bbb)
3839 if (gimple_code (opstmta) == GIMPLE_PHI
3840 && gimple_code (opstmtb) == GIMPLE_PHI)
3841 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3842 else if (gimple_code (opstmta) == GIMPLE_PHI)
3843 return -1;
3844 else if (gimple_code (opstmtb) == GIMPLE_PHI)
3845 return 1;
3846 else if (gimple_uid (opstmta) != gimple_uid (opstmtb))
3847 return gimple_uid (opstmta) - gimple_uid (opstmtb);
3848 else
3849 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
3851 return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
3854 /* Sort an array containing members of a strongly connected component
3855 SCC so that the members are ordered by RPO number.
3856 This means that when the sort is complete, iterating through the
3857 array will give you the members in RPO order. */
3859 static void
3860 sort_scc (vec<tree> scc)
3862 scc.qsort (compare_ops);
3865 /* Insert the no longer used nary ONARY to the hash INFO. */
3867 static void
3868 copy_nary (vn_nary_op_t onary, vn_tables_t info)
3870 size_t size = sizeof_vn_nary_op (onary->length);
3871 vn_nary_op_t nary = alloc_vn_nary_op_noinit (onary->length,
3872 &info->nary_obstack);
3873 memcpy (nary, onary, size);
3874 vn_nary_op_insert_into (nary, info->nary, false);
3877 /* Insert the no longer used phi OPHI to the hash INFO. */
3879 static void
3880 copy_phi (vn_phi_t ophi, vn_tables_t info)
3882 vn_phi_t phi = info->phis_pool->allocate ();
3883 vn_phi_s **slot;
3884 memcpy (phi, ophi, sizeof (*phi));
3885 ophi->phiargs.create (0);
3886 slot = info->phis->find_slot_with_hash (phi, phi->hashcode, INSERT);
3887 gcc_assert (!*slot);
3888 *slot = phi;
3891 /* Insert the no longer used reference OREF to the hash INFO. */
3893 static void
3894 copy_reference (vn_reference_t oref, vn_tables_t info)
3896 vn_reference_t ref;
3897 vn_reference_s **slot;
3898 ref = info->references_pool->allocate ();
3899 memcpy (ref, oref, sizeof (*ref));
3900 oref->operands.create (0);
3901 slot = info->references->find_slot_with_hash (ref, ref->hashcode, INSERT);
3902 if (*slot)
3903 free_reference (*slot);
3904 *slot = ref;
3907 /* Process a strongly connected component in the SSA graph. */
3909 static void
3910 process_scc (vec<tree> scc)
3912 tree var;
3913 unsigned int i;
3914 unsigned int iterations = 0;
3915 bool changed = true;
3916 vn_nary_op_iterator_type hin;
3917 vn_phi_iterator_type hip;
3918 vn_reference_iterator_type hir;
3919 vn_nary_op_t nary;
3920 vn_phi_t phi;
3921 vn_reference_t ref;
3923 /* If the SCC has a single member, just visit it. */
3924 if (scc.length () == 1)
3926 tree use = scc[0];
3927 if (VN_INFO (use)->use_processed)
3928 return;
3929 /* We need to make sure it doesn't form a cycle itself, which can
3930 happen for self-referential PHI nodes. In that case we would
3931 end up inserting an expression with VN_TOP operands into the
3932 valid table which makes us derive bogus equivalences later.
3933 The cheapest way to check this is to assume it for all PHI nodes. */
3934 if (gimple_code (SSA_NAME_DEF_STMT (use)) == GIMPLE_PHI)
3935 /* Fallthru to iteration. */ ;
3936 else
3938 visit_use (use);
3939 return;
3943 if (dump_file && (dump_flags & TDF_DETAILS))
3944 print_scc (dump_file, scc);
3946 /* Iterate over the SCC with the optimistic table until it stops
3947 changing. */
3948 current_info = optimistic_info;
3949 while (changed)
3951 changed = false;
3952 iterations++;
3953 if (dump_file && (dump_flags & TDF_DETAILS))
3954 fprintf (dump_file, "Starting iteration %d\n", iterations);
3955 /* As we are value-numbering optimistically we have to
3956 clear the expression tables and the simplified expressions
3957 in each iteration until we converge. */
3958 optimistic_info->nary->empty ();
3959 optimistic_info->phis->empty ();
3960 optimistic_info->references->empty ();
3961 obstack_free (&optimistic_info->nary_obstack, NULL);
3962 gcc_obstack_init (&optimistic_info->nary_obstack);
3963 optimistic_info->phis_pool->release ();
3964 optimistic_info->references_pool->release ();
3965 FOR_EACH_VEC_ELT (scc, i, var)
3966 VN_INFO (var)->expr = NULL_TREE;
3967 FOR_EACH_VEC_ELT (scc, i, var)
3968 changed |= visit_use (var);
3971 if (dump_file && (dump_flags & TDF_DETAILS))
3972 fprintf (dump_file, "Processing SCC needed %d iterations\n", iterations);
3973 statistics_histogram_event (cfun, "SCC iterations", iterations);
3975 /* Finally, copy the contents of the no longer used optimistic
3976 table to the valid table. */
3977 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info->nary, nary, vn_nary_op_t, hin)
3978 copy_nary (nary, valid_info);
3979 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info->phis, phi, vn_phi_t, hip)
3980 copy_phi (phi, valid_info);
3981 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info->references,
3982 ref, vn_reference_t, hir)
3983 copy_reference (ref, valid_info);
3985 current_info = valid_info;
3989 /* Pop the components of the found SCC for NAME off the SCC stack
3990 and process them. Returns true if all went well, false if
3991 we run into resource limits. */
3993 static bool
3994 extract_and_process_scc_for_name (tree name)
3996 auto_vec<tree> scc;
3997 tree x;
3999 /* Found an SCC, pop the components off the SCC stack and
4000 process them. */
4003 x = sccstack.pop ();
4005 VN_INFO (x)->on_sccstack = false;
4006 scc.safe_push (x);
4007 } while (x != name);
4009 /* Bail out of SCCVN in case a SCC turns out to be incredibly large. */
4010 if (scc.length ()
4011 > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE))
4013 if (dump_file)
4014 fprintf (dump_file, "WARNING: Giving up with SCCVN due to "
4015 "SCC size %u exceeding %u\n", scc.length (),
4016 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE));
4018 return false;
4021 if (scc.length () > 1)
4022 sort_scc (scc);
4024 process_scc (scc);
4026 return true;
4029 /* Depth first search on NAME to discover and process SCC's in the SSA
4030 graph.
4031 Execution of this algorithm relies on the fact that the SCC's are
4032 popped off the stack in topological order.
4033 Returns true if successful, false if we stopped processing SCC's due
4034 to resource constraints. */
4036 static bool
4037 DFS (tree name)
4039 vec<ssa_op_iter> itervec = vNULL;
4040 vec<tree> namevec = vNULL;
4041 use_operand_p usep = NULL;
4042 gimple defstmt;
4043 tree use;
4044 ssa_op_iter iter;
4046 start_over:
4047 /* SCC info */
4048 VN_INFO (name)->dfsnum = next_dfs_num++;
4049 VN_INFO (name)->visited = true;
4050 VN_INFO (name)->low = VN_INFO (name)->dfsnum;
4052 sccstack.safe_push (name);
4053 VN_INFO (name)->on_sccstack = true;
4054 defstmt = SSA_NAME_DEF_STMT (name);
4056 /* Recursively DFS on our operands, looking for SCC's. */
4057 if (!gimple_nop_p (defstmt))
4059 /* Push a new iterator. */
4060 if (gphi *phi = dyn_cast <gphi *> (defstmt))
4061 usep = op_iter_init_phiuse (&iter, phi, SSA_OP_ALL_USES);
4062 else
4063 usep = op_iter_init_use (&iter, defstmt, SSA_OP_ALL_USES);
4065 else
4066 clear_and_done_ssa_iter (&iter);
4068 while (1)
4070 /* If we are done processing uses of a name, go up the stack
4071 of iterators and process SCCs as we found them. */
4072 if (op_iter_done (&iter))
4074 /* See if we found an SCC. */
4075 if (VN_INFO (name)->low == VN_INFO (name)->dfsnum)
4076 if (!extract_and_process_scc_for_name (name))
4078 namevec.release ();
4079 itervec.release ();
4080 return false;
4083 /* Check if we are done. */
4084 if (namevec.is_empty ())
4086 namevec.release ();
4087 itervec.release ();
4088 return true;
4091 /* Restore the last use walker and continue walking there. */
4092 use = name;
4093 name = namevec.pop ();
4094 memcpy (&iter, &itervec.last (),
4095 sizeof (ssa_op_iter));
4096 itervec.pop ();
4097 goto continue_walking;
4100 use = USE_FROM_PTR (usep);
4102 /* Since we handle phi nodes, we will sometimes get
4103 invariants in the use expression. */
4104 if (TREE_CODE (use) == SSA_NAME)
4106 if (! (VN_INFO (use)->visited))
4108 /* Recurse by pushing the current use walking state on
4109 the stack and starting over. */
4110 itervec.safe_push (iter);
4111 namevec.safe_push (name);
4112 name = use;
4113 goto start_over;
4115 continue_walking:
4116 VN_INFO (name)->low = MIN (VN_INFO (name)->low,
4117 VN_INFO (use)->low);
4119 if (VN_INFO (use)->dfsnum < VN_INFO (name)->dfsnum
4120 && VN_INFO (use)->on_sccstack)
4122 VN_INFO (name)->low = MIN (VN_INFO (use)->dfsnum,
4123 VN_INFO (name)->low);
4127 usep = op_iter_next_use (&iter);
4131 /* Allocate a value number table. */
4133 static void
4134 allocate_vn_table (vn_tables_t table)
4136 table->phis = new vn_phi_table_type (23);
4137 table->nary = new vn_nary_op_table_type (23);
4138 table->references = new vn_reference_table_type (23);
4140 gcc_obstack_init (&table->nary_obstack);
4141 table->phis_pool = new pool_allocator<vn_phi_s> ("VN phis", 30);
4142 table->references_pool = new pool_allocator<vn_reference_s> ("VN references",
4143 30);
4146 /* Free a value number table. */
4148 static void
4149 free_vn_table (vn_tables_t table)
4151 delete table->phis;
4152 table->phis = NULL;
4153 delete table->nary;
4154 table->nary = NULL;
4155 delete table->references;
4156 table->references = NULL;
4157 obstack_free (&table->nary_obstack, NULL);
4158 delete table->phis_pool;
4159 delete table->references_pool;
4162 static void
4163 init_scc_vn (void)
4165 size_t i;
4166 int j;
4167 int *rpo_numbers_temp;
4169 calculate_dominance_info (CDI_DOMINATORS);
4170 sccstack.create (0);
4171 constant_to_value_id = new hash_table<vn_constant_hasher> (23);
4173 constant_value_ids = BITMAP_ALLOC (NULL);
4175 next_dfs_num = 1;
4176 next_value_id = 1;
4178 vn_ssa_aux_table.create (num_ssa_names + 1);
4179 /* VEC_alloc doesn't actually grow it to the right size, it just
4180 preallocates the space to do so. */
4181 vn_ssa_aux_table.safe_grow_cleared (num_ssa_names + 1);
4182 gcc_obstack_init (&vn_ssa_aux_obstack);
4184 shared_lookup_phiargs.create (0);
4185 shared_lookup_references.create (0);
4186 rpo_numbers = XNEWVEC (int, last_basic_block_for_fn (cfun));
4187 rpo_numbers_temp =
4188 XNEWVEC (int, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS);
4189 pre_and_rev_post_order_compute (NULL, rpo_numbers_temp, false);
4191 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
4192 the i'th block in RPO order is bb. We want to map bb's to RPO
4193 numbers, so we need to rearrange this array. */
4194 for (j = 0; j < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; j++)
4195 rpo_numbers[rpo_numbers_temp[j]] = j;
4197 XDELETE (rpo_numbers_temp);
4199 VN_TOP = create_tmp_var_raw (void_type_node, "vn_top");
4201 /* Create the VN_INFO structures, and initialize value numbers to
4202 TOP. */
4203 for (i = 0; i < num_ssa_names; i++)
4205 tree name = ssa_name (i);
4206 if (name)
4208 VN_INFO_GET (name)->valnum = VN_TOP;
4209 VN_INFO (name)->expr = NULL_TREE;
4210 VN_INFO (name)->value_id = 0;
4214 renumber_gimple_stmt_uids ();
4216 /* Create the valid and optimistic value numbering tables. */
4217 valid_info = XCNEW (struct vn_tables_s);
4218 allocate_vn_table (valid_info);
4219 optimistic_info = XCNEW (struct vn_tables_s);
4220 allocate_vn_table (optimistic_info);
4223 void
4224 free_scc_vn (void)
4226 size_t i;
4228 delete constant_to_value_id;
4229 constant_to_value_id = NULL;
4230 BITMAP_FREE (constant_value_ids);
4231 shared_lookup_phiargs.release ();
4232 shared_lookup_references.release ();
4233 XDELETEVEC (rpo_numbers);
4235 for (i = 0; i < num_ssa_names; i++)
4237 tree name = ssa_name (i);
4238 if (name
4239 && VN_INFO (name)->needs_insertion)
4240 release_ssa_name (name);
4242 obstack_free (&vn_ssa_aux_obstack, NULL);
4243 vn_ssa_aux_table.release ();
4245 sccstack.release ();
4246 free_vn_table (valid_info);
4247 XDELETE (valid_info);
4248 free_vn_table (optimistic_info);
4249 XDELETE (optimistic_info);
4252 /* Set *ID according to RESULT. */
4254 static void
4255 set_value_id_for_result (tree result, unsigned int *id)
4257 if (result && TREE_CODE (result) == SSA_NAME)
4258 *id = VN_INFO (result)->value_id;
4259 else if (result && is_gimple_min_invariant (result))
4260 *id = get_or_alloc_constant_value_id (result);
4261 else
4262 *id = get_next_value_id ();
4265 /* Set the value ids in the valid hash tables. */
4267 static void
4268 set_hashtable_value_ids (void)
4270 vn_nary_op_iterator_type hin;
4271 vn_phi_iterator_type hip;
4272 vn_reference_iterator_type hir;
4273 vn_nary_op_t vno;
4274 vn_reference_t vr;
4275 vn_phi_t vp;
4277 /* Now set the value ids of the things we had put in the hash
4278 table. */
4280 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info->nary, vno, vn_nary_op_t, hin)
4281 set_value_id_for_result (vno->result, &vno->value_id);
4283 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info->phis, vp, vn_phi_t, hip)
4284 set_value_id_for_result (vp->result, &vp->value_id);
4286 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info->references, vr, vn_reference_t,
4287 hir)
4288 set_value_id_for_result (vr->result, &vr->value_id);
4291 class cond_dom_walker : public dom_walker
4293 public:
4294 cond_dom_walker () : dom_walker (CDI_DOMINATORS), fail (false) {}
4296 virtual void before_dom_children (basic_block);
4298 bool fail;
4301 void
4302 cond_dom_walker::before_dom_children (basic_block bb)
4304 edge e;
4305 edge_iterator ei;
4307 if (fail)
4308 return;
4310 /* If any of the predecessor edges that do not come from blocks dominated
4311 by us are still marked as possibly executable consider this block
4312 reachable. */
4313 bool reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (cfun);
4314 FOR_EACH_EDGE (e, ei, bb->preds)
4315 if (!dominated_by_p (CDI_DOMINATORS, e->src, bb))
4316 reachable |= (e->flags & EDGE_EXECUTABLE);
4318 /* If the block is not reachable all outgoing edges are not
4319 executable. */
4320 if (!reachable)
4322 if (dump_file && (dump_flags & TDF_DETAILS))
4323 fprintf (dump_file, "Marking all outgoing edges of unreachable "
4324 "BB %d as not executable\n", bb->index);
4326 FOR_EACH_EDGE (e, ei, bb->succs)
4327 e->flags &= ~EDGE_EXECUTABLE;
4328 return;
4331 gimple stmt = last_stmt (bb);
4332 if (!stmt)
4333 return;
4335 enum gimple_code code = gimple_code (stmt);
4336 if (code != GIMPLE_COND
4337 && code != GIMPLE_SWITCH
4338 && code != GIMPLE_GOTO)
4339 return;
4341 if (dump_file && (dump_flags & TDF_DETAILS))
4343 fprintf (dump_file, "Value-numbering operands of stmt ending BB %d: ",
4344 bb->index);
4345 print_gimple_stmt (dump_file, stmt, 0, 0);
4348 /* Value-number the last stmts SSA uses. */
4349 ssa_op_iter i;
4350 tree op;
4351 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
4352 if (VN_INFO (op)->visited == false
4353 && !DFS (op))
4355 fail = true;
4356 return;
4359 /* ??? We can even handle stmts with outgoing EH or ABNORMAL edges
4360 if value-numbering can prove they are not reachable. Handling
4361 computed gotos is also possible. */
4362 tree val;
4363 switch (code)
4365 case GIMPLE_COND:
4367 tree lhs = gimple_cond_lhs (stmt);
4368 tree rhs = gimple_cond_rhs (stmt);
4369 /* Work hard in computing the condition and take into account
4370 the valueization of the defining stmt. */
4371 if (TREE_CODE (lhs) == SSA_NAME)
4372 lhs = vn_get_expr_for (lhs);
4373 if (TREE_CODE (rhs) == SSA_NAME)
4374 rhs = vn_get_expr_for (rhs);
4375 val = fold_binary (gimple_cond_code (stmt),
4376 boolean_type_node, lhs, rhs);
4377 break;
4379 case GIMPLE_SWITCH:
4380 val = gimple_switch_index (as_a <gswitch *> (stmt));
4381 break;
4382 case GIMPLE_GOTO:
4383 val = gimple_goto_dest (stmt);
4384 break;
4385 default:
4386 gcc_unreachable ();
4388 if (!val)
4389 return;
4391 edge taken = find_taken_edge (bb, vn_valueize (val));
4392 if (!taken)
4393 return;
4395 if (dump_file && (dump_flags & TDF_DETAILS))
4396 fprintf (dump_file, "Marking all edges out of BB %d but (%d -> %d) as "
4397 "not executable\n", bb->index, bb->index, taken->dest->index);
4399 FOR_EACH_EDGE (e, ei, bb->succs)
4400 if (e != taken)
4401 e->flags &= ~EDGE_EXECUTABLE;
4404 /* Do SCCVN. Returns true if it finished, false if we bailed out
4405 due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies
4406 how we use the alias oracle walking during the VN process. */
4408 bool
4409 run_scc_vn (vn_lookup_kind default_vn_walk_kind_)
4411 basic_block bb;
4412 size_t i;
4413 tree param;
4415 default_vn_walk_kind = default_vn_walk_kind_;
4417 init_scc_vn ();
4418 current_info = valid_info;
4420 for (param = DECL_ARGUMENTS (current_function_decl);
4421 param;
4422 param = DECL_CHAIN (param))
4424 tree def = ssa_default_def (cfun, param);
4425 if (def)
4427 VN_INFO (def)->visited = true;
4428 VN_INFO (def)->valnum = def;
4432 /* Mark all edges as possibly executable. */
4433 FOR_ALL_BB_FN (bb, cfun)
4435 edge_iterator ei;
4436 edge e;
4437 FOR_EACH_EDGE (e, ei, bb->succs)
4438 e->flags |= EDGE_EXECUTABLE;
4441 /* Walk all blocks in dominator order, value-numbering the last stmts
4442 SSA uses and decide whether outgoing edges are not executable. */
4443 cond_dom_walker walker;
4444 walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
4445 if (walker.fail)
4447 free_scc_vn ();
4448 return false;
4451 /* Value-number remaining SSA names. */
4452 for (i = 1; i < num_ssa_names; ++i)
4454 tree name = ssa_name (i);
4455 if (name
4456 && VN_INFO (name)->visited == false
4457 && !has_zero_uses (name))
4458 if (!DFS (name))
4460 free_scc_vn ();
4461 return false;
4465 /* Initialize the value ids. */
4467 for (i = 1; i < num_ssa_names; ++i)
4469 tree name = ssa_name (i);
4470 vn_ssa_aux_t info;
4471 if (!name)
4472 continue;
4473 info = VN_INFO (name);
4474 if (info->valnum == name
4475 || info->valnum == VN_TOP)
4476 info->value_id = get_next_value_id ();
4477 else if (is_gimple_min_invariant (info->valnum))
4478 info->value_id = get_or_alloc_constant_value_id (info->valnum);
4481 /* Propagate. */
4482 for (i = 1; i < num_ssa_names; ++i)
4484 tree name = ssa_name (i);
4485 vn_ssa_aux_t info;
4486 if (!name)
4487 continue;
4488 info = VN_INFO (name);
4489 if (TREE_CODE (info->valnum) == SSA_NAME
4490 && info->valnum != name
4491 && info->value_id != VN_INFO (info->valnum)->value_id)
4492 info->value_id = VN_INFO (info->valnum)->value_id;
4495 set_hashtable_value_ids ();
4497 if (dump_file && (dump_flags & TDF_DETAILS))
4499 fprintf (dump_file, "Value numbers:\n");
4500 for (i = 0; i < num_ssa_names; i++)
4502 tree name = ssa_name (i);
4503 if (name
4504 && VN_INFO (name)->visited
4505 && SSA_VAL (name) != name)
4507 print_generic_expr (dump_file, name, 0);
4508 fprintf (dump_file, " = ");
4509 print_generic_expr (dump_file, SSA_VAL (name), 0);
4510 fprintf (dump_file, "\n");
4515 return true;
4518 /* Return the maximum value id we have ever seen. */
4520 unsigned int
4521 get_max_value_id (void)
4523 return next_value_id;
4526 /* Return the next unique value id. */
4528 unsigned int
4529 get_next_value_id (void)
4531 return next_value_id++;
4535 /* Compare two expressions E1 and E2 and return true if they are equal. */
4537 bool
4538 expressions_equal_p (tree e1, tree e2)
4540 /* The obvious case. */
4541 if (e1 == e2)
4542 return true;
4544 /* If only one of them is null, they cannot be equal. */
4545 if (!e1 || !e2)
4546 return false;
4548 /* Now perform the actual comparison. */
4549 if (TREE_CODE (e1) == TREE_CODE (e2)
4550 && operand_equal_p (e1, e2, OEP_PURE_SAME))
4551 return true;
4553 return false;
4557 /* Return true if the nary operation NARY may trap. This is a copy
4558 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
4560 bool
4561 vn_nary_may_trap (vn_nary_op_t nary)
4563 tree type;
4564 tree rhs2 = NULL_TREE;
4565 bool honor_nans = false;
4566 bool honor_snans = false;
4567 bool fp_operation = false;
4568 bool honor_trapv = false;
4569 bool handled, ret;
4570 unsigned i;
4572 if (TREE_CODE_CLASS (nary->opcode) == tcc_comparison
4573 || TREE_CODE_CLASS (nary->opcode) == tcc_unary
4574 || TREE_CODE_CLASS (nary->opcode) == tcc_binary)
4576 type = nary->type;
4577 fp_operation = FLOAT_TYPE_P (type);
4578 if (fp_operation)
4580 honor_nans = flag_trapping_math && !flag_finite_math_only;
4581 honor_snans = flag_signaling_nans != 0;
4583 else if (INTEGRAL_TYPE_P (type)
4584 && TYPE_OVERFLOW_TRAPS (type))
4585 honor_trapv = true;
4587 if (nary->length >= 2)
4588 rhs2 = nary->op[1];
4589 ret = operation_could_trap_helper_p (nary->opcode, fp_operation,
4590 honor_trapv,
4591 honor_nans, honor_snans, rhs2,
4592 &handled);
4593 if (handled
4594 && ret)
4595 return true;
4597 for (i = 0; i < nary->length; ++i)
4598 if (tree_could_trap_p (nary->op[i]))
4599 return true;
4601 return false;