Disable anchors and msdata for ASAN test-case (PR sanirizer/85174).
[official-gcc.git] / gcc / tree-ssa-sccvn.c
blob4e5f3385f9d80da11491cc27ec4a0773d4ffab41
1 /* SCC value numbering for trees
2 Copyright (C) 2006-2018 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 "backend.h"
25 #include "rtl.h"
26 #include "tree.h"
27 #include "gimple.h"
28 #include "alloc-pool.h"
29 #include "ssa.h"
30 #include "expmed.h"
31 #include "insn-config.h"
32 #include "memmodel.h"
33 #include "emit-rtl.h"
34 #include "cgraph.h"
35 #include "gimple-pretty-print.h"
36 #include "alias.h"
37 #include "fold-const.h"
38 #include "stor-layout.h"
39 #include "cfganal.h"
40 #include "tree-inline.h"
41 #include "internal-fn.h"
42 #include "gimple-fold.h"
43 #include "tree-eh.h"
44 #include "gimplify.h"
45 #include "flags.h"
46 #include "dojump.h"
47 #include "explow.h"
48 #include "calls.h"
49 #include "varasm.h"
50 #include "stmt.h"
51 #include "expr.h"
52 #include "tree-dfa.h"
53 #include "tree-ssa.h"
54 #include "dumpfile.h"
55 #include "cfgloop.h"
56 #include "params.h"
57 #include "tree-ssa-propagate.h"
58 #include "tree-cfg.h"
59 #include "domwalk.h"
60 #include "gimple-iterator.h"
61 #include "gimple-match.h"
62 #include "stringpool.h"
63 #include "attribs.h"
64 #include "tree-pass.h"
65 #include "statistics.h"
66 #include "langhooks.h"
67 #include "ipa-utils.h"
68 #include "dbgcnt.h"
69 #include "tree-cfgcleanup.h"
70 #include "tree-ssa-loop.h"
71 #include "tree-scalar-evolution.h"
72 #include "tree-ssa-sccvn.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;
135 bitmap const_parms;
137 /* vn_nary_op hashtable helpers. */
139 struct vn_nary_op_hasher : nofree_ptr_hash <vn_nary_op_s>
141 typedef vn_nary_op_s *compare_type;
142 static inline hashval_t hash (const vn_nary_op_s *);
143 static inline bool equal (const vn_nary_op_s *, const vn_nary_op_s *);
146 /* Return the computed hashcode for nary operation P1. */
148 inline hashval_t
149 vn_nary_op_hasher::hash (const vn_nary_op_s *vno1)
151 return vno1->hashcode;
154 /* Compare nary operations P1 and P2 and return true if they are
155 equivalent. */
157 inline bool
158 vn_nary_op_hasher::equal (const vn_nary_op_s *vno1, const vn_nary_op_s *vno2)
160 return vn_nary_op_eq (vno1, vno2);
163 typedef hash_table<vn_nary_op_hasher> vn_nary_op_table_type;
164 typedef vn_nary_op_table_type::iterator vn_nary_op_iterator_type;
167 /* vn_phi hashtable helpers. */
169 static int
170 vn_phi_eq (const_vn_phi_t const vp1, const_vn_phi_t const vp2);
172 struct vn_phi_hasher : pointer_hash <vn_phi_s>
174 static inline hashval_t hash (const vn_phi_s *);
175 static inline bool equal (const vn_phi_s *, const vn_phi_s *);
176 static inline void remove (vn_phi_s *);
179 /* Return the computed hashcode for phi operation P1. */
181 inline hashval_t
182 vn_phi_hasher::hash (const vn_phi_s *vp1)
184 return vp1->hashcode;
187 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
189 inline bool
190 vn_phi_hasher::equal (const vn_phi_s *vp1, const vn_phi_s *vp2)
192 return vn_phi_eq (vp1, vp2);
195 /* Free a phi operation structure VP. */
197 inline void
198 vn_phi_hasher::remove (vn_phi_s *phi)
200 phi->phiargs.release ();
203 typedef hash_table<vn_phi_hasher> vn_phi_table_type;
204 typedef vn_phi_table_type::iterator vn_phi_iterator_type;
207 /* Compare two reference operands P1 and P2 for equality. Return true if
208 they are equal, and false otherwise. */
210 static int
211 vn_reference_op_eq (const void *p1, const void *p2)
213 const_vn_reference_op_t const vro1 = (const_vn_reference_op_t) p1;
214 const_vn_reference_op_t const vro2 = (const_vn_reference_op_t) p2;
216 return (vro1->opcode == vro2->opcode
217 /* We do not care for differences in type qualification. */
218 && (vro1->type == vro2->type
219 || (vro1->type && vro2->type
220 && types_compatible_p (TYPE_MAIN_VARIANT (vro1->type),
221 TYPE_MAIN_VARIANT (vro2->type))))
222 && expressions_equal_p (vro1->op0, vro2->op0)
223 && expressions_equal_p (vro1->op1, vro2->op1)
224 && expressions_equal_p (vro1->op2, vro2->op2));
227 /* Free a reference operation structure VP. */
229 static inline void
230 free_reference (vn_reference_s *vr)
232 vr->operands.release ();
236 /* vn_reference hashtable helpers. */
238 struct vn_reference_hasher : pointer_hash <vn_reference_s>
240 static inline hashval_t hash (const vn_reference_s *);
241 static inline bool equal (const vn_reference_s *, const vn_reference_s *);
242 static inline void remove (vn_reference_s *);
245 /* Return the hashcode for a given reference operation P1. */
247 inline hashval_t
248 vn_reference_hasher::hash (const vn_reference_s *vr1)
250 return vr1->hashcode;
253 inline bool
254 vn_reference_hasher::equal (const vn_reference_s *v, const vn_reference_s *c)
256 return vn_reference_eq (v, c);
259 inline void
260 vn_reference_hasher::remove (vn_reference_s *v)
262 free_reference (v);
265 typedef hash_table<vn_reference_hasher> vn_reference_table_type;
266 typedef vn_reference_table_type::iterator vn_reference_iterator_type;
269 /* The set of hashtables and alloc_pool's for their items. */
271 typedef struct vn_tables_s
273 vn_nary_op_table_type *nary;
274 vn_phi_table_type *phis;
275 vn_reference_table_type *references;
276 struct obstack nary_obstack;
277 object_allocator<vn_phi_s> *phis_pool;
278 object_allocator<vn_reference_s> *references_pool;
279 } *vn_tables_t;
282 /* vn_constant hashtable helpers. */
284 struct vn_constant_hasher : free_ptr_hash <vn_constant_s>
286 static inline hashval_t hash (const vn_constant_s *);
287 static inline bool equal (const vn_constant_s *, const vn_constant_s *);
290 /* Hash table hash function for vn_constant_t. */
292 inline hashval_t
293 vn_constant_hasher::hash (const vn_constant_s *vc1)
295 return vc1->hashcode;
298 /* Hash table equality function for vn_constant_t. */
300 inline bool
301 vn_constant_hasher::equal (const vn_constant_s *vc1, const vn_constant_s *vc2)
303 if (vc1->hashcode != vc2->hashcode)
304 return false;
306 return vn_constant_eq_with_type (vc1->constant, vc2->constant);
309 static hash_table<vn_constant_hasher> *constant_to_value_id;
310 static bitmap constant_value_ids;
313 /* Valid hashtables storing information we have proven to be
314 correct. */
316 static vn_tables_t valid_info;
318 /* Optimistic hashtables storing information we are making assumptions about
319 during iterations. */
321 static vn_tables_t optimistic_info;
323 /* Pointer to the set of hashtables that is currently being used.
324 Should always point to either the optimistic_info, or the
325 valid_info. */
327 static vn_tables_t current_info;
330 /* Reverse post order index for each basic block. */
332 static int *rpo_numbers;
334 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
336 /* Return the SSA value of the VUSE x, supporting released VDEFs
337 during elimination which will value-number the VDEF to the
338 associated VUSE (but not substitute in the whole lattice). */
340 static inline tree
341 vuse_ssa_val (tree x)
343 if (!x)
344 return NULL_TREE;
348 tree tem = SSA_VAL (x);
349 /* stmt walking can walk over a backedge and reach code we didn't
350 value-number yet. */
351 if (tem == VN_TOP)
352 return x;
353 x = tem;
355 while (SSA_NAME_IN_FREE_LIST (x));
357 return x;
360 /* This represents the top of the VN lattice, which is the universal
361 value. */
363 tree VN_TOP;
365 /* Unique counter for our value ids. */
367 static unsigned int next_value_id;
369 /* Next DFS number and the stack for strongly connected component
370 detection. */
372 static unsigned int next_dfs_num;
373 static vec<tree> sccstack;
377 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
378 are allocated on an obstack for locality reasons, and to free them
379 without looping over the vec. */
381 static vec<vn_ssa_aux_t> vn_ssa_aux_table;
382 static struct obstack vn_ssa_aux_obstack;
384 /* Return whether there is value numbering information for a given SSA name. */
386 bool
387 has_VN_INFO (tree name)
389 if (SSA_NAME_VERSION (name) < vn_ssa_aux_table.length ())
390 return vn_ssa_aux_table[SSA_NAME_VERSION (name)] != NULL;
391 return false;
394 /* Return the value numbering information for a given SSA name. */
396 vn_ssa_aux_t
397 VN_INFO (tree name)
399 vn_ssa_aux_t res = vn_ssa_aux_table[SSA_NAME_VERSION (name)];
400 gcc_checking_assert (res);
401 return res;
404 /* Set the value numbering info for a given SSA name to a given
405 value. */
407 static inline void
408 VN_INFO_SET (tree name, vn_ssa_aux_t value)
410 vn_ssa_aux_table[SSA_NAME_VERSION (name)] = value;
413 /* Initialize the value numbering info for a given SSA name.
414 This should be called just once for every SSA name. */
416 vn_ssa_aux_t
417 VN_INFO_GET (tree name)
419 vn_ssa_aux_t newinfo;
421 gcc_assert (SSA_NAME_VERSION (name) >= vn_ssa_aux_table.length ()
422 || vn_ssa_aux_table[SSA_NAME_VERSION (name)] == NULL);
423 newinfo = XOBNEW (&vn_ssa_aux_obstack, struct vn_ssa_aux);
424 memset (newinfo, 0, sizeof (struct vn_ssa_aux));
425 if (SSA_NAME_VERSION (name) >= vn_ssa_aux_table.length ())
426 vn_ssa_aux_table.safe_grow_cleared (SSA_NAME_VERSION (name) + 1);
427 vn_ssa_aux_table[SSA_NAME_VERSION (name)] = newinfo;
428 return newinfo;
432 /* Return the vn_kind the expression computed by the stmt should be
433 associated with. */
435 enum vn_kind
436 vn_get_stmt_kind (gimple *stmt)
438 switch (gimple_code (stmt))
440 case GIMPLE_CALL:
441 return VN_REFERENCE;
442 case GIMPLE_PHI:
443 return VN_PHI;
444 case GIMPLE_ASSIGN:
446 enum tree_code code = gimple_assign_rhs_code (stmt);
447 tree rhs1 = gimple_assign_rhs1 (stmt);
448 switch (get_gimple_rhs_class (code))
450 case GIMPLE_UNARY_RHS:
451 case GIMPLE_BINARY_RHS:
452 case GIMPLE_TERNARY_RHS:
453 return VN_NARY;
454 case GIMPLE_SINGLE_RHS:
455 switch (TREE_CODE_CLASS (code))
457 case tcc_reference:
458 /* VOP-less references can go through unary case. */
459 if ((code == REALPART_EXPR
460 || code == IMAGPART_EXPR
461 || code == VIEW_CONVERT_EXPR
462 || code == BIT_FIELD_REF)
463 && TREE_CODE (TREE_OPERAND (rhs1, 0)) == SSA_NAME)
464 return VN_NARY;
466 /* Fallthrough. */
467 case tcc_declaration:
468 return VN_REFERENCE;
470 case tcc_constant:
471 return VN_CONSTANT;
473 default:
474 if (code == ADDR_EXPR)
475 return (is_gimple_min_invariant (rhs1)
476 ? VN_CONSTANT : VN_REFERENCE);
477 else if (code == CONSTRUCTOR)
478 return VN_NARY;
479 return VN_NONE;
481 default:
482 return VN_NONE;
485 default:
486 return VN_NONE;
490 /* Lookup a value id for CONSTANT and return it. If it does not
491 exist returns 0. */
493 unsigned int
494 get_constant_value_id (tree constant)
496 vn_constant_s **slot;
497 struct vn_constant_s vc;
499 vc.hashcode = vn_hash_constant_with_type (constant);
500 vc.constant = constant;
501 slot = constant_to_value_id->find_slot (&vc, NO_INSERT);
502 if (slot)
503 return (*slot)->value_id;
504 return 0;
507 /* Lookup a value id for CONSTANT, and if it does not exist, create a
508 new one and return it. If it does exist, return it. */
510 unsigned int
511 get_or_alloc_constant_value_id (tree constant)
513 vn_constant_s **slot;
514 struct vn_constant_s vc;
515 vn_constant_t vcp;
517 vc.hashcode = vn_hash_constant_with_type (constant);
518 vc.constant = constant;
519 slot = constant_to_value_id->find_slot (&vc, INSERT);
520 if (*slot)
521 return (*slot)->value_id;
523 vcp = XNEW (struct vn_constant_s);
524 vcp->hashcode = vc.hashcode;
525 vcp->constant = constant;
526 vcp->value_id = get_next_value_id ();
527 *slot = vcp;
528 bitmap_set_bit (constant_value_ids, vcp->value_id);
529 return vcp->value_id;
532 /* Return true if V is a value id for a constant. */
534 bool
535 value_id_constant_p (unsigned int v)
537 return bitmap_bit_p (constant_value_ids, v);
540 /* Compute the hash for a reference operand VRO1. */
542 static void
543 vn_reference_op_compute_hash (const vn_reference_op_t vro1, inchash::hash &hstate)
545 hstate.add_int (vro1->opcode);
546 if (vro1->op0)
547 inchash::add_expr (vro1->op0, hstate);
548 if (vro1->op1)
549 inchash::add_expr (vro1->op1, hstate);
550 if (vro1->op2)
551 inchash::add_expr (vro1->op2, hstate);
554 /* Compute a hash for the reference operation VR1 and return it. */
556 static hashval_t
557 vn_reference_compute_hash (const vn_reference_t vr1)
559 inchash::hash hstate;
560 hashval_t result;
561 int i;
562 vn_reference_op_t vro;
563 poly_int64 off = -1;
564 bool deref = false;
566 FOR_EACH_VEC_ELT (vr1->operands, i, vro)
568 if (vro->opcode == MEM_REF)
569 deref = true;
570 else if (vro->opcode != ADDR_EXPR)
571 deref = false;
572 if (maybe_ne (vro->off, -1))
574 if (known_eq (off, -1))
575 off = 0;
576 off += vro->off;
578 else
580 if (maybe_ne (off, -1)
581 && maybe_ne (off, 0))
582 hstate.add_poly_int (off);
583 off = -1;
584 if (deref
585 && vro->opcode == ADDR_EXPR)
587 if (vro->op0)
589 tree op = TREE_OPERAND (vro->op0, 0);
590 hstate.add_int (TREE_CODE (op));
591 inchash::add_expr (op, hstate);
594 else
595 vn_reference_op_compute_hash (vro, hstate);
598 result = hstate.end ();
599 /* ??? We would ICE later if we hash instead of adding that in. */
600 if (vr1->vuse)
601 result += SSA_NAME_VERSION (vr1->vuse);
603 return result;
606 /* Return true if reference operations VR1 and VR2 are equivalent. This
607 means they have the same set of operands and vuses. */
609 bool
610 vn_reference_eq (const_vn_reference_t const vr1, const_vn_reference_t const vr2)
612 unsigned i, j;
614 /* Early out if this is not a hash collision. */
615 if (vr1->hashcode != vr2->hashcode)
616 return false;
618 /* The VOP needs to be the same. */
619 if (vr1->vuse != vr2->vuse)
620 return false;
622 /* If the operands are the same we are done. */
623 if (vr1->operands == vr2->operands)
624 return true;
626 if (!expressions_equal_p (TYPE_SIZE (vr1->type), TYPE_SIZE (vr2->type)))
627 return false;
629 if (INTEGRAL_TYPE_P (vr1->type)
630 && INTEGRAL_TYPE_P (vr2->type))
632 if (TYPE_PRECISION (vr1->type) != TYPE_PRECISION (vr2->type))
633 return false;
635 else if (INTEGRAL_TYPE_P (vr1->type)
636 && (TYPE_PRECISION (vr1->type)
637 != TREE_INT_CST_LOW (TYPE_SIZE (vr1->type))))
638 return false;
639 else if (INTEGRAL_TYPE_P (vr2->type)
640 && (TYPE_PRECISION (vr2->type)
641 != TREE_INT_CST_LOW (TYPE_SIZE (vr2->type))))
642 return false;
644 i = 0;
645 j = 0;
648 poly_int64 off1 = 0, off2 = 0;
649 vn_reference_op_t vro1, vro2;
650 vn_reference_op_s tem1, tem2;
651 bool deref1 = false, deref2 = false;
652 for (; vr1->operands.iterate (i, &vro1); i++)
654 if (vro1->opcode == MEM_REF)
655 deref1 = true;
656 /* Do not look through a storage order barrier. */
657 else if (vro1->opcode == VIEW_CONVERT_EXPR && vro1->reverse)
658 return false;
659 if (known_eq (vro1->off, -1))
660 break;
661 off1 += vro1->off;
663 for (; vr2->operands.iterate (j, &vro2); j++)
665 if (vro2->opcode == MEM_REF)
666 deref2 = true;
667 /* Do not look through a storage order barrier. */
668 else if (vro2->opcode == VIEW_CONVERT_EXPR && vro2->reverse)
669 return false;
670 if (known_eq (vro2->off, -1))
671 break;
672 off2 += vro2->off;
674 if (maybe_ne (off1, off2))
675 return false;
676 if (deref1 && vro1->opcode == ADDR_EXPR)
678 memset (&tem1, 0, sizeof (tem1));
679 tem1.op0 = TREE_OPERAND (vro1->op0, 0);
680 tem1.type = TREE_TYPE (tem1.op0);
681 tem1.opcode = TREE_CODE (tem1.op0);
682 vro1 = &tem1;
683 deref1 = false;
685 if (deref2 && vro2->opcode == ADDR_EXPR)
687 memset (&tem2, 0, sizeof (tem2));
688 tem2.op0 = TREE_OPERAND (vro2->op0, 0);
689 tem2.type = TREE_TYPE (tem2.op0);
690 tem2.opcode = TREE_CODE (tem2.op0);
691 vro2 = &tem2;
692 deref2 = false;
694 if (deref1 != deref2)
695 return false;
696 if (!vn_reference_op_eq (vro1, vro2))
697 return false;
698 ++j;
699 ++i;
701 while (vr1->operands.length () != i
702 || vr2->operands.length () != j);
704 return true;
707 /* Copy the operations present in load/store REF into RESULT, a vector of
708 vn_reference_op_s's. */
710 static void
711 copy_reference_ops_from_ref (tree ref, vec<vn_reference_op_s> *result)
713 if (TREE_CODE (ref) == TARGET_MEM_REF)
715 vn_reference_op_s temp;
717 result->reserve (3);
719 memset (&temp, 0, sizeof (temp));
720 temp.type = TREE_TYPE (ref);
721 temp.opcode = TREE_CODE (ref);
722 temp.op0 = TMR_INDEX (ref);
723 temp.op1 = TMR_STEP (ref);
724 temp.op2 = TMR_OFFSET (ref);
725 temp.off = -1;
726 temp.clique = MR_DEPENDENCE_CLIQUE (ref);
727 temp.base = MR_DEPENDENCE_BASE (ref);
728 result->quick_push (temp);
730 memset (&temp, 0, sizeof (temp));
731 temp.type = NULL_TREE;
732 temp.opcode = ERROR_MARK;
733 temp.op0 = TMR_INDEX2 (ref);
734 temp.off = -1;
735 result->quick_push (temp);
737 memset (&temp, 0, sizeof (temp));
738 temp.type = NULL_TREE;
739 temp.opcode = TREE_CODE (TMR_BASE (ref));
740 temp.op0 = TMR_BASE (ref);
741 temp.off = -1;
742 result->quick_push (temp);
743 return;
746 /* For non-calls, store the information that makes up the address. */
747 tree orig = ref;
748 while (ref)
750 vn_reference_op_s temp;
752 memset (&temp, 0, sizeof (temp));
753 temp.type = TREE_TYPE (ref);
754 temp.opcode = TREE_CODE (ref);
755 temp.off = -1;
757 switch (temp.opcode)
759 case MODIFY_EXPR:
760 temp.op0 = TREE_OPERAND (ref, 1);
761 break;
762 case WITH_SIZE_EXPR:
763 temp.op0 = TREE_OPERAND (ref, 1);
764 temp.off = 0;
765 break;
766 case MEM_REF:
767 /* The base address gets its own vn_reference_op_s structure. */
768 temp.op0 = TREE_OPERAND (ref, 1);
769 if (!mem_ref_offset (ref).to_shwi (&temp.off))
770 temp.off = -1;
771 temp.clique = MR_DEPENDENCE_CLIQUE (ref);
772 temp.base = MR_DEPENDENCE_BASE (ref);
773 temp.reverse = REF_REVERSE_STORAGE_ORDER (ref);
774 break;
775 case BIT_FIELD_REF:
776 /* Record bits, position and storage order. */
777 temp.op0 = TREE_OPERAND (ref, 1);
778 temp.op1 = TREE_OPERAND (ref, 2);
779 if (!multiple_p (bit_field_offset (ref), BITS_PER_UNIT, &temp.off))
780 temp.off = -1;
781 temp.reverse = REF_REVERSE_STORAGE_ORDER (ref);
782 break;
783 case COMPONENT_REF:
784 /* The field decl is enough to unambiguously specify the field,
785 a matching type is not necessary and a mismatching type
786 is always a spurious difference. */
787 temp.type = NULL_TREE;
788 temp.op0 = TREE_OPERAND (ref, 1);
789 temp.op1 = TREE_OPERAND (ref, 2);
791 tree this_offset = component_ref_field_offset (ref);
792 if (this_offset
793 && poly_int_tree_p (this_offset))
795 tree bit_offset = DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1));
796 if (TREE_INT_CST_LOW (bit_offset) % BITS_PER_UNIT == 0)
798 poly_offset_int off
799 = (wi::to_poly_offset (this_offset)
800 + (wi::to_offset (bit_offset) >> LOG2_BITS_PER_UNIT));
801 /* Probibit value-numbering zero offset components
802 of addresses the same before the pass folding
803 __builtin_object_size had a chance to run
804 (checking cfun->after_inlining does the
805 trick here). */
806 if (TREE_CODE (orig) != ADDR_EXPR
807 || maybe_ne (off, 0)
808 || cfun->after_inlining)
809 off.to_shwi (&temp.off);
813 break;
814 case ARRAY_RANGE_REF:
815 case ARRAY_REF:
817 tree eltype = TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref, 0)));
818 /* Record index as operand. */
819 temp.op0 = TREE_OPERAND (ref, 1);
820 /* Always record lower bounds and element size. */
821 temp.op1 = array_ref_low_bound (ref);
822 /* But record element size in units of the type alignment. */
823 temp.op2 = TREE_OPERAND (ref, 3);
824 temp.align = eltype->type_common.align;
825 if (! temp.op2)
826 temp.op2 = size_binop (EXACT_DIV_EXPR, TYPE_SIZE_UNIT (eltype),
827 size_int (TYPE_ALIGN_UNIT (eltype)));
828 if (poly_int_tree_p (temp.op0)
829 && poly_int_tree_p (temp.op1)
830 && TREE_CODE (temp.op2) == INTEGER_CST)
832 poly_offset_int off = ((wi::to_poly_offset (temp.op0)
833 - wi::to_poly_offset (temp.op1))
834 * wi::to_offset (temp.op2)
835 * vn_ref_op_align_unit (&temp));
836 off.to_shwi (&temp.off);
839 break;
840 case VAR_DECL:
841 if (DECL_HARD_REGISTER (ref))
843 temp.op0 = ref;
844 break;
846 /* Fallthru. */
847 case PARM_DECL:
848 case CONST_DECL:
849 case RESULT_DECL:
850 /* Canonicalize decls to MEM[&decl] which is what we end up with
851 when valueizing MEM[ptr] with ptr = &decl. */
852 temp.opcode = MEM_REF;
853 temp.op0 = build_int_cst (build_pointer_type (TREE_TYPE (ref)), 0);
854 temp.off = 0;
855 result->safe_push (temp);
856 temp.opcode = ADDR_EXPR;
857 temp.op0 = build1 (ADDR_EXPR, TREE_TYPE (temp.op0), ref);
858 temp.type = TREE_TYPE (temp.op0);
859 temp.off = -1;
860 break;
861 case STRING_CST:
862 case INTEGER_CST:
863 case COMPLEX_CST:
864 case VECTOR_CST:
865 case REAL_CST:
866 case FIXED_CST:
867 case CONSTRUCTOR:
868 case SSA_NAME:
869 temp.op0 = ref;
870 break;
871 case ADDR_EXPR:
872 if (is_gimple_min_invariant (ref))
874 temp.op0 = ref;
875 break;
877 break;
878 /* These are only interesting for their operands, their
879 existence, and their type. They will never be the last
880 ref in the chain of references (IE they require an
881 operand), so we don't have to put anything
882 for op* as it will be handled by the iteration */
883 case REALPART_EXPR:
884 temp.off = 0;
885 break;
886 case VIEW_CONVERT_EXPR:
887 temp.off = 0;
888 temp.reverse = storage_order_barrier_p (ref);
889 break;
890 case IMAGPART_EXPR:
891 /* This is only interesting for its constant offset. */
892 temp.off = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref)));
893 break;
894 default:
895 gcc_unreachable ();
897 result->safe_push (temp);
899 if (REFERENCE_CLASS_P (ref)
900 || TREE_CODE (ref) == MODIFY_EXPR
901 || TREE_CODE (ref) == WITH_SIZE_EXPR
902 || (TREE_CODE (ref) == ADDR_EXPR
903 && !is_gimple_min_invariant (ref)))
904 ref = TREE_OPERAND (ref, 0);
905 else
906 ref = NULL_TREE;
910 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
911 operands in *OPS, the reference alias set SET and the reference type TYPE.
912 Return true if something useful was produced. */
914 bool
915 ao_ref_init_from_vn_reference (ao_ref *ref,
916 alias_set_type set, tree type,
917 vec<vn_reference_op_s> ops)
919 vn_reference_op_t op;
920 unsigned i;
921 tree base = NULL_TREE;
922 tree *op0_p = &base;
923 poly_offset_int offset = 0;
924 poly_offset_int max_size;
925 poly_offset_int size = -1;
926 tree size_tree = NULL_TREE;
927 alias_set_type base_alias_set = -1;
929 /* First get the final access size from just the outermost expression. */
930 op = &ops[0];
931 if (op->opcode == COMPONENT_REF)
932 size_tree = DECL_SIZE (op->op0);
933 else if (op->opcode == BIT_FIELD_REF)
934 size_tree = op->op0;
935 else
937 machine_mode mode = TYPE_MODE (type);
938 if (mode == BLKmode)
939 size_tree = TYPE_SIZE (type);
940 else
941 size = GET_MODE_BITSIZE (mode);
943 if (size_tree != NULL_TREE
944 && poly_int_tree_p (size_tree))
945 size = wi::to_poly_offset (size_tree);
947 /* Initially, maxsize is the same as the accessed element size.
948 In the following it will only grow (or become -1). */
949 max_size = size;
951 /* Compute cumulative bit-offset for nested component-refs and array-refs,
952 and find the ultimate containing object. */
953 FOR_EACH_VEC_ELT (ops, i, op)
955 switch (op->opcode)
957 /* These may be in the reference ops, but we cannot do anything
958 sensible with them here. */
959 case ADDR_EXPR:
960 /* Apart from ADDR_EXPR arguments to MEM_REF. */
961 if (base != NULL_TREE
962 && TREE_CODE (base) == MEM_REF
963 && op->op0
964 && DECL_P (TREE_OPERAND (op->op0, 0)))
966 vn_reference_op_t pop = &ops[i-1];
967 base = TREE_OPERAND (op->op0, 0);
968 if (known_eq (pop->off, -1))
970 max_size = -1;
971 offset = 0;
973 else
974 offset += pop->off * BITS_PER_UNIT;
975 op0_p = NULL;
976 break;
978 /* Fallthru. */
979 case CALL_EXPR:
980 return false;
982 /* Record the base objects. */
983 case MEM_REF:
984 base_alias_set = get_deref_alias_set (op->op0);
985 *op0_p = build2 (MEM_REF, op->type,
986 NULL_TREE, op->op0);
987 MR_DEPENDENCE_CLIQUE (*op0_p) = op->clique;
988 MR_DEPENDENCE_BASE (*op0_p) = op->base;
989 op0_p = &TREE_OPERAND (*op0_p, 0);
990 break;
992 case VAR_DECL:
993 case PARM_DECL:
994 case RESULT_DECL:
995 case SSA_NAME:
996 *op0_p = op->op0;
997 op0_p = NULL;
998 break;
1000 /* And now the usual component-reference style ops. */
1001 case BIT_FIELD_REF:
1002 offset += wi::to_offset (op->op1);
1003 break;
1005 case COMPONENT_REF:
1007 tree field = op->op0;
1008 /* We do not have a complete COMPONENT_REF tree here so we
1009 cannot use component_ref_field_offset. Do the interesting
1010 parts manually. */
1011 tree this_offset = DECL_FIELD_OFFSET (field);
1013 if (op->op1 || !poly_int_tree_p (this_offset))
1014 max_size = -1;
1015 else
1017 poly_offset_int woffset = (wi::to_poly_offset (this_offset)
1018 << LOG2_BITS_PER_UNIT);
1019 woffset += wi::to_offset (DECL_FIELD_BIT_OFFSET (field));
1020 offset += woffset;
1022 break;
1025 case ARRAY_RANGE_REF:
1026 case ARRAY_REF:
1027 /* We recorded the lower bound and the element size. */
1028 if (!poly_int_tree_p (op->op0)
1029 || !poly_int_tree_p (op->op1)
1030 || TREE_CODE (op->op2) != INTEGER_CST)
1031 max_size = -1;
1032 else
1034 poly_offset_int woffset
1035 = wi::sext (wi::to_poly_offset (op->op0)
1036 - wi::to_poly_offset (op->op1),
1037 TYPE_PRECISION (TREE_TYPE (op->op0)));
1038 woffset *= wi::to_offset (op->op2) * vn_ref_op_align_unit (op);
1039 woffset <<= LOG2_BITS_PER_UNIT;
1040 offset += woffset;
1042 break;
1044 case REALPART_EXPR:
1045 break;
1047 case IMAGPART_EXPR:
1048 offset += size;
1049 break;
1051 case VIEW_CONVERT_EXPR:
1052 break;
1054 case STRING_CST:
1055 case INTEGER_CST:
1056 case COMPLEX_CST:
1057 case VECTOR_CST:
1058 case REAL_CST:
1059 case CONSTRUCTOR:
1060 case CONST_DECL:
1061 return false;
1063 default:
1064 return false;
1068 if (base == NULL_TREE)
1069 return false;
1071 ref->ref = NULL_TREE;
1072 ref->base = base;
1073 ref->ref_alias_set = set;
1074 if (base_alias_set != -1)
1075 ref->base_alias_set = base_alias_set;
1076 else
1077 ref->base_alias_set = get_alias_set (base);
1078 /* We discount volatiles from value-numbering elsewhere. */
1079 ref->volatile_p = false;
1081 if (!size.to_shwi (&ref->size) || maybe_lt (ref->size, 0))
1083 ref->offset = 0;
1084 ref->size = -1;
1085 ref->max_size = -1;
1086 return true;
1089 if (!offset.to_shwi (&ref->offset))
1091 ref->offset = 0;
1092 ref->max_size = -1;
1093 return true;
1096 if (!max_size.to_shwi (&ref->max_size) || maybe_lt (ref->max_size, 0))
1097 ref->max_size = -1;
1099 return true;
1102 /* Copy the operations present in load/store/call REF into RESULT, a vector of
1103 vn_reference_op_s's. */
1105 static void
1106 copy_reference_ops_from_call (gcall *call,
1107 vec<vn_reference_op_s> *result)
1109 vn_reference_op_s temp;
1110 unsigned i;
1111 tree lhs = gimple_call_lhs (call);
1112 int lr;
1114 /* If 2 calls have a different non-ssa lhs, vdef value numbers should be
1115 different. By adding the lhs here in the vector, we ensure that the
1116 hashcode is different, guaranteeing a different value number. */
1117 if (lhs && TREE_CODE (lhs) != SSA_NAME)
1119 memset (&temp, 0, sizeof (temp));
1120 temp.opcode = MODIFY_EXPR;
1121 temp.type = TREE_TYPE (lhs);
1122 temp.op0 = lhs;
1123 temp.off = -1;
1124 result->safe_push (temp);
1127 /* Copy the type, opcode, function, static chain and EH region, if any. */
1128 memset (&temp, 0, sizeof (temp));
1129 temp.type = gimple_call_return_type (call);
1130 temp.opcode = CALL_EXPR;
1131 temp.op0 = gimple_call_fn (call);
1132 temp.op1 = gimple_call_chain (call);
1133 if (stmt_could_throw_p (call) && (lr = lookup_stmt_eh_lp (call)) > 0)
1134 temp.op2 = size_int (lr);
1135 temp.off = -1;
1136 if (gimple_call_with_bounds_p (call))
1137 temp.with_bounds = 1;
1138 result->safe_push (temp);
1140 /* Copy the call arguments. As they can be references as well,
1141 just chain them together. */
1142 for (i = 0; i < gimple_call_num_args (call); ++i)
1144 tree callarg = gimple_call_arg (call, i);
1145 copy_reference_ops_from_ref (callarg, result);
1149 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1150 *I_P to point to the last element of the replacement. */
1151 static bool
1152 vn_reference_fold_indirect (vec<vn_reference_op_s> *ops,
1153 unsigned int *i_p)
1155 unsigned int i = *i_p;
1156 vn_reference_op_t op = &(*ops)[i];
1157 vn_reference_op_t mem_op = &(*ops)[i - 1];
1158 tree addr_base;
1159 poly_int64 addr_offset = 0;
1161 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1162 from .foo.bar to the preceding MEM_REF offset and replace the
1163 address with &OBJ. */
1164 addr_base = get_addr_base_and_unit_offset (TREE_OPERAND (op->op0, 0),
1165 &addr_offset);
1166 gcc_checking_assert (addr_base && TREE_CODE (addr_base) != MEM_REF);
1167 if (addr_base != TREE_OPERAND (op->op0, 0))
1169 poly_offset_int off
1170 = (poly_offset_int::from (wi::to_poly_wide (mem_op->op0),
1171 SIGNED)
1172 + addr_offset);
1173 mem_op->op0 = wide_int_to_tree (TREE_TYPE (mem_op->op0), off);
1174 op->op0 = build_fold_addr_expr (addr_base);
1175 if (tree_fits_shwi_p (mem_op->op0))
1176 mem_op->off = tree_to_shwi (mem_op->op0);
1177 else
1178 mem_op->off = -1;
1179 return true;
1181 return false;
1184 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1185 *I_P to point to the last element of the replacement. */
1186 static bool
1187 vn_reference_maybe_forwprop_address (vec<vn_reference_op_s> *ops,
1188 unsigned int *i_p)
1190 unsigned int i = *i_p;
1191 vn_reference_op_t op = &(*ops)[i];
1192 vn_reference_op_t mem_op = &(*ops)[i - 1];
1193 gimple *def_stmt;
1194 enum tree_code code;
1195 poly_offset_int off;
1197 def_stmt = SSA_NAME_DEF_STMT (op->op0);
1198 if (!is_gimple_assign (def_stmt))
1199 return false;
1201 code = gimple_assign_rhs_code (def_stmt);
1202 if (code != ADDR_EXPR
1203 && code != POINTER_PLUS_EXPR)
1204 return false;
1206 off = poly_offset_int::from (wi::to_poly_wide (mem_op->op0), SIGNED);
1208 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1209 from .foo.bar to the preceding MEM_REF offset and replace the
1210 address with &OBJ. */
1211 if (code == ADDR_EXPR)
1213 tree addr, addr_base;
1214 poly_int64 addr_offset;
1216 addr = gimple_assign_rhs1 (def_stmt);
1217 addr_base = get_addr_base_and_unit_offset (TREE_OPERAND (addr, 0),
1218 &addr_offset);
1219 /* If that didn't work because the address isn't invariant propagate
1220 the reference tree from the address operation in case the current
1221 dereference isn't offsetted. */
1222 if (!addr_base
1223 && *i_p == ops->length () - 1
1224 && known_eq (off, 0)
1225 /* This makes us disable this transform for PRE where the
1226 reference ops might be also used for code insertion which
1227 is invalid. */
1228 && default_vn_walk_kind == VN_WALKREWRITE)
1230 auto_vec<vn_reference_op_s, 32> tem;
1231 copy_reference_ops_from_ref (TREE_OPERAND (addr, 0), &tem);
1232 /* Make sure to preserve TBAA info. The only objects not
1233 wrapped in MEM_REFs that can have their address taken are
1234 STRING_CSTs. */
1235 if (tem.length () >= 2
1236 && tem[tem.length () - 2].opcode == MEM_REF)
1238 vn_reference_op_t new_mem_op = &tem[tem.length () - 2];
1239 new_mem_op->op0
1240 = wide_int_to_tree (TREE_TYPE (mem_op->op0),
1241 wi::to_poly_wide (new_mem_op->op0));
1243 else
1244 gcc_assert (tem.last ().opcode == STRING_CST);
1245 ops->pop ();
1246 ops->pop ();
1247 ops->safe_splice (tem);
1248 --*i_p;
1249 return true;
1251 if (!addr_base
1252 || TREE_CODE (addr_base) != MEM_REF
1253 || (TREE_CODE (TREE_OPERAND (addr_base, 0)) == SSA_NAME
1254 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (addr_base, 0))))
1255 return false;
1257 off += addr_offset;
1258 off += mem_ref_offset (addr_base);
1259 op->op0 = TREE_OPERAND (addr_base, 0);
1261 else
1263 tree ptr, ptroff;
1264 ptr = gimple_assign_rhs1 (def_stmt);
1265 ptroff = gimple_assign_rhs2 (def_stmt);
1266 if (TREE_CODE (ptr) != SSA_NAME
1267 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr)
1268 || TREE_CODE (ptroff) != INTEGER_CST)
1269 return false;
1271 off += wi::to_offset (ptroff);
1272 op->op0 = ptr;
1275 mem_op->op0 = wide_int_to_tree (TREE_TYPE (mem_op->op0), off);
1276 if (tree_fits_shwi_p (mem_op->op0))
1277 mem_op->off = tree_to_shwi (mem_op->op0);
1278 else
1279 mem_op->off = -1;
1280 if (TREE_CODE (op->op0) == SSA_NAME)
1281 op->op0 = SSA_VAL (op->op0);
1282 if (TREE_CODE (op->op0) != SSA_NAME)
1283 op->opcode = TREE_CODE (op->op0);
1285 /* And recurse. */
1286 if (TREE_CODE (op->op0) == SSA_NAME)
1287 vn_reference_maybe_forwprop_address (ops, i_p);
1288 else if (TREE_CODE (op->op0) == ADDR_EXPR)
1289 vn_reference_fold_indirect (ops, i_p);
1290 return true;
1293 /* Optimize the reference REF to a constant if possible or return
1294 NULL_TREE if not. */
1296 tree
1297 fully_constant_vn_reference_p (vn_reference_t ref)
1299 vec<vn_reference_op_s> operands = ref->operands;
1300 vn_reference_op_t op;
1302 /* Try to simplify the translated expression if it is
1303 a call to a builtin function with at most two arguments. */
1304 op = &operands[0];
1305 if (op->opcode == CALL_EXPR
1306 && TREE_CODE (op->op0) == ADDR_EXPR
1307 && TREE_CODE (TREE_OPERAND (op->op0, 0)) == FUNCTION_DECL
1308 && DECL_BUILT_IN (TREE_OPERAND (op->op0, 0))
1309 && operands.length () >= 2
1310 && operands.length () <= 3)
1312 vn_reference_op_t arg0, arg1 = NULL;
1313 bool anyconst = false;
1314 arg0 = &operands[1];
1315 if (operands.length () > 2)
1316 arg1 = &operands[2];
1317 if (TREE_CODE_CLASS (arg0->opcode) == tcc_constant
1318 || (arg0->opcode == ADDR_EXPR
1319 && is_gimple_min_invariant (arg0->op0)))
1320 anyconst = true;
1321 if (arg1
1322 && (TREE_CODE_CLASS (arg1->opcode) == tcc_constant
1323 || (arg1->opcode == ADDR_EXPR
1324 && is_gimple_min_invariant (arg1->op0))))
1325 anyconst = true;
1326 if (anyconst)
1328 tree folded = build_call_expr (TREE_OPERAND (op->op0, 0),
1329 arg1 ? 2 : 1,
1330 arg0->op0,
1331 arg1 ? arg1->op0 : NULL);
1332 if (folded
1333 && TREE_CODE (folded) == NOP_EXPR)
1334 folded = TREE_OPERAND (folded, 0);
1335 if (folded
1336 && is_gimple_min_invariant (folded))
1337 return folded;
1341 /* Simplify reads from constants or constant initializers. */
1342 else if (BITS_PER_UNIT == 8
1343 && is_gimple_reg_type (ref->type)
1344 && (!INTEGRAL_TYPE_P (ref->type)
1345 || TYPE_PRECISION (ref->type) % BITS_PER_UNIT == 0))
1347 poly_int64 off = 0;
1348 HOST_WIDE_INT size;
1349 if (INTEGRAL_TYPE_P (ref->type))
1350 size = TYPE_PRECISION (ref->type);
1351 else
1352 size = tree_to_shwi (TYPE_SIZE (ref->type));
1353 if (size % BITS_PER_UNIT != 0
1354 || size > MAX_BITSIZE_MODE_ANY_MODE)
1355 return NULL_TREE;
1356 size /= BITS_PER_UNIT;
1357 unsigned i;
1358 for (i = 0; i < operands.length (); ++i)
1360 if (TREE_CODE_CLASS (operands[i].opcode) == tcc_constant)
1362 ++i;
1363 break;
1365 if (known_eq (operands[i].off, -1))
1366 return NULL_TREE;
1367 off += operands[i].off;
1368 if (operands[i].opcode == MEM_REF)
1370 ++i;
1371 break;
1374 vn_reference_op_t base = &operands[--i];
1375 tree ctor = error_mark_node;
1376 tree decl = NULL_TREE;
1377 if (TREE_CODE_CLASS (base->opcode) == tcc_constant)
1378 ctor = base->op0;
1379 else if (base->opcode == MEM_REF
1380 && base[1].opcode == ADDR_EXPR
1381 && (TREE_CODE (TREE_OPERAND (base[1].op0, 0)) == VAR_DECL
1382 || TREE_CODE (TREE_OPERAND (base[1].op0, 0)) == CONST_DECL
1383 || TREE_CODE (TREE_OPERAND (base[1].op0, 0)) == STRING_CST))
1385 decl = TREE_OPERAND (base[1].op0, 0);
1386 if (TREE_CODE (decl) == STRING_CST)
1387 ctor = decl;
1388 else
1389 ctor = ctor_for_folding (decl);
1391 if (ctor == NULL_TREE)
1392 return build_zero_cst (ref->type);
1393 else if (ctor != error_mark_node)
1395 HOST_WIDE_INT const_off;
1396 if (decl)
1398 tree res = fold_ctor_reference (ref->type, ctor,
1399 off * BITS_PER_UNIT,
1400 size * BITS_PER_UNIT, decl);
1401 if (res)
1403 STRIP_USELESS_TYPE_CONVERSION (res);
1404 if (is_gimple_min_invariant (res))
1405 return res;
1408 else if (off.is_constant (&const_off))
1410 unsigned char buf[MAX_BITSIZE_MODE_ANY_MODE / BITS_PER_UNIT];
1411 int len = native_encode_expr (ctor, buf, size, const_off);
1412 if (len > 0)
1413 return native_interpret_expr (ref->type, buf, len);
1418 return NULL_TREE;
1421 /* Return true if OPS contain a storage order barrier. */
1423 static bool
1424 contains_storage_order_barrier_p (vec<vn_reference_op_s> ops)
1426 vn_reference_op_t op;
1427 unsigned i;
1429 FOR_EACH_VEC_ELT (ops, i, op)
1430 if (op->opcode == VIEW_CONVERT_EXPR && op->reverse)
1431 return true;
1433 return false;
1436 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1437 structures into their value numbers. This is done in-place, and
1438 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1439 whether any operands were valueized. */
1441 static vec<vn_reference_op_s>
1442 valueize_refs_1 (vec<vn_reference_op_s> orig, bool *valueized_anything)
1444 vn_reference_op_t vro;
1445 unsigned int i;
1447 *valueized_anything = false;
1449 FOR_EACH_VEC_ELT (orig, i, vro)
1451 if (vro->opcode == SSA_NAME
1452 || (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME))
1454 tree tem = SSA_VAL (vro->op0);
1455 if (tem != vro->op0)
1457 *valueized_anything = true;
1458 vro->op0 = tem;
1460 /* If it transforms from an SSA_NAME to a constant, update
1461 the opcode. */
1462 if (TREE_CODE (vro->op0) != SSA_NAME && vro->opcode == SSA_NAME)
1463 vro->opcode = TREE_CODE (vro->op0);
1465 if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
1467 tree tem = SSA_VAL (vro->op1);
1468 if (tem != vro->op1)
1470 *valueized_anything = true;
1471 vro->op1 = tem;
1474 if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
1476 tree tem = SSA_VAL (vro->op2);
1477 if (tem != vro->op2)
1479 *valueized_anything = true;
1480 vro->op2 = tem;
1483 /* If it transforms from an SSA_NAME to an address, fold with
1484 a preceding indirect reference. */
1485 if (i > 0
1486 && vro->op0
1487 && TREE_CODE (vro->op0) == ADDR_EXPR
1488 && orig[i - 1].opcode == MEM_REF)
1490 if (vn_reference_fold_indirect (&orig, &i))
1491 *valueized_anything = true;
1493 else if (i > 0
1494 && vro->opcode == SSA_NAME
1495 && orig[i - 1].opcode == MEM_REF)
1497 if (vn_reference_maybe_forwprop_address (&orig, &i))
1498 *valueized_anything = true;
1500 /* If it transforms a non-constant ARRAY_REF into a constant
1501 one, adjust the constant offset. */
1502 else if (vro->opcode == ARRAY_REF
1503 && known_eq (vro->off, -1)
1504 && poly_int_tree_p (vro->op0)
1505 && poly_int_tree_p (vro->op1)
1506 && TREE_CODE (vro->op2) == INTEGER_CST)
1508 poly_offset_int off = ((wi::to_poly_offset (vro->op0)
1509 - wi::to_poly_offset (vro->op1))
1510 * wi::to_offset (vro->op2)
1511 * vn_ref_op_align_unit (vro));
1512 off.to_shwi (&vro->off);
1516 return orig;
1519 static vec<vn_reference_op_s>
1520 valueize_refs (vec<vn_reference_op_s> orig)
1522 bool tem;
1523 return valueize_refs_1 (orig, &tem);
1526 static vec<vn_reference_op_s> shared_lookup_references;
1528 /* Create a vector of vn_reference_op_s structures from REF, a
1529 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1530 this function. *VALUEIZED_ANYTHING will specify whether any
1531 operands were valueized. */
1533 static vec<vn_reference_op_s>
1534 valueize_shared_reference_ops_from_ref (tree ref, bool *valueized_anything)
1536 if (!ref)
1537 return vNULL;
1538 shared_lookup_references.truncate (0);
1539 copy_reference_ops_from_ref (ref, &shared_lookup_references);
1540 shared_lookup_references = valueize_refs_1 (shared_lookup_references,
1541 valueized_anything);
1542 return shared_lookup_references;
1545 /* Create a vector of vn_reference_op_s structures from CALL, a
1546 call statement. The vector is shared among all callers of
1547 this function. */
1549 static vec<vn_reference_op_s>
1550 valueize_shared_reference_ops_from_call (gcall *call)
1552 if (!call)
1553 return vNULL;
1554 shared_lookup_references.truncate (0);
1555 copy_reference_ops_from_call (call, &shared_lookup_references);
1556 shared_lookup_references = valueize_refs (shared_lookup_references);
1557 return shared_lookup_references;
1560 /* Lookup a SCCVN reference operation VR in the current hash table.
1561 Returns the resulting value number if it exists in the hash table,
1562 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1563 vn_reference_t stored in the hashtable if something is found. */
1565 static tree
1566 vn_reference_lookup_1 (vn_reference_t vr, vn_reference_t *vnresult)
1568 vn_reference_s **slot;
1569 hashval_t hash;
1571 hash = vr->hashcode;
1572 slot = current_info->references->find_slot_with_hash (vr, hash, NO_INSERT);
1573 if (!slot && current_info == optimistic_info)
1574 slot = valid_info->references->find_slot_with_hash (vr, hash, NO_INSERT);
1575 if (slot)
1577 if (vnresult)
1578 *vnresult = (vn_reference_t)*slot;
1579 return ((vn_reference_t)*slot)->result;
1582 return NULL_TREE;
1585 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1586 with the current VUSE and performs the expression lookup. */
1588 static void *
1589 vn_reference_lookup_2 (ao_ref *op ATTRIBUTE_UNUSED, tree vuse,
1590 unsigned int cnt, void *vr_)
1592 vn_reference_t vr = (vn_reference_t)vr_;
1593 vn_reference_s **slot;
1594 hashval_t hash;
1596 /* This bounds the stmt walks we perform on reference lookups
1597 to O(1) instead of O(N) where N is the number of dominating
1598 stores. */
1599 if (cnt > (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS))
1600 return (void *)-1;
1602 if (last_vuse_ptr)
1603 *last_vuse_ptr = vuse;
1605 /* Fixup vuse and hash. */
1606 if (vr->vuse)
1607 vr->hashcode = vr->hashcode - SSA_NAME_VERSION (vr->vuse);
1608 vr->vuse = vuse_ssa_val (vuse);
1609 if (vr->vuse)
1610 vr->hashcode = vr->hashcode + SSA_NAME_VERSION (vr->vuse);
1612 hash = vr->hashcode;
1613 slot = current_info->references->find_slot_with_hash (vr, hash, NO_INSERT);
1614 if (!slot && current_info == optimistic_info)
1615 slot = valid_info->references->find_slot_with_hash (vr, hash, NO_INSERT);
1616 if (slot)
1617 return *slot;
1619 return NULL;
1622 /* Lookup an existing or insert a new vn_reference entry into the
1623 value table for the VUSE, SET, TYPE, OPERANDS reference which
1624 has the value VALUE which is either a constant or an SSA name. */
1626 static vn_reference_t
1627 vn_reference_lookup_or_insert_for_pieces (tree vuse,
1628 alias_set_type set,
1629 tree type,
1630 vec<vn_reference_op_s,
1631 va_heap> operands,
1632 tree value)
1634 vn_reference_s vr1;
1635 vn_reference_t result;
1636 unsigned value_id;
1637 vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
1638 vr1.operands = operands;
1639 vr1.type = type;
1640 vr1.set = set;
1641 vr1.hashcode = vn_reference_compute_hash (&vr1);
1642 if (vn_reference_lookup_1 (&vr1, &result))
1643 return result;
1644 if (TREE_CODE (value) == SSA_NAME)
1645 value_id = VN_INFO (value)->value_id;
1646 else
1647 value_id = get_or_alloc_constant_value_id (value);
1648 return vn_reference_insert_pieces (vuse, set, type,
1649 operands.copy (), value, value_id);
1652 static vn_nary_op_t vn_nary_op_insert_stmt (gimple *stmt, tree result);
1653 static unsigned mprts_hook_cnt;
1655 /* Hook for maybe_push_res_to_seq, lookup the expression in the VN tables. */
1657 static tree
1658 vn_lookup_simplify_result (code_helper rcode, tree type, tree *ops_)
1660 if (!rcode.is_tree_code ())
1661 return NULL_TREE;
1662 tree *ops = ops_;
1663 unsigned int length = TREE_CODE_LENGTH ((tree_code) rcode);
1664 if (rcode == CONSTRUCTOR
1665 /* ??? We're arriving here with SCCVNs view, decomposed CONSTRUCTOR
1666 and GIMPLEs / match-and-simplifies, CONSTRUCTOR as GENERIC tree. */
1667 && TREE_CODE (ops_[0]) == CONSTRUCTOR)
1669 length = CONSTRUCTOR_NELTS (ops_[0]);
1670 ops = XALLOCAVEC (tree, length);
1671 for (unsigned i = 0; i < length; ++i)
1672 ops[i] = CONSTRUCTOR_ELT (ops_[0], i)->value;
1674 vn_nary_op_t vnresult = NULL;
1675 tree res = vn_nary_op_lookup_pieces (length, (tree_code) rcode,
1676 type, ops, &vnresult);
1677 /* We can end up endlessly recursing simplifications if the lookup above
1678 presents us with a def-use chain that mirrors the original simplification.
1679 See PR80887 for an example. Limit successful lookup artificially
1680 to 10 times if we are called as mprts_hook. */
1681 if (res
1682 && mprts_hook
1683 && --mprts_hook_cnt == 0)
1685 if (dump_file && (dump_flags & TDF_DETAILS))
1686 fprintf (dump_file, "Resetting mprts_hook after too many "
1687 "invocations.\n");
1688 mprts_hook = NULL;
1690 return res;
1693 /* Return a value-number for RCODE OPS... either by looking up an existing
1694 value-number for the simplified result or by inserting the operation if
1695 INSERT is true. */
1697 static tree
1698 vn_nary_build_or_lookup_1 (code_helper rcode, tree type, tree *ops,
1699 bool insert)
1701 tree result = NULL_TREE;
1702 /* We will be creating a value number for
1703 RCODE (OPS...).
1704 So first simplify and lookup this expression to see if it
1705 is already available. */
1706 mprts_hook = vn_lookup_simplify_result;
1707 mprts_hook_cnt = 9;
1708 bool res = false;
1709 switch (TREE_CODE_LENGTH ((tree_code) rcode))
1711 case 1:
1712 res = gimple_resimplify1 (NULL, &rcode, type, ops, vn_valueize);
1713 break;
1714 case 2:
1715 res = gimple_resimplify2 (NULL, &rcode, type, ops, vn_valueize);
1716 break;
1717 case 3:
1718 res = gimple_resimplify3 (NULL, &rcode, type, ops, vn_valueize);
1719 break;
1721 mprts_hook = NULL;
1722 gimple *new_stmt = NULL;
1723 if (res
1724 && gimple_simplified_result_is_gimple_val (rcode, ops))
1725 /* The expression is already available. */
1726 result = ops[0];
1727 else
1729 tree val = vn_lookup_simplify_result (rcode, type, ops);
1730 if (!val && insert)
1732 gimple_seq stmts = NULL;
1733 result = maybe_push_res_to_seq (rcode, type, ops, &stmts);
1734 if (result)
1736 gcc_assert (gimple_seq_singleton_p (stmts));
1737 new_stmt = gimple_seq_first_stmt (stmts);
1740 else
1741 /* The expression is already available. */
1742 result = val;
1744 if (new_stmt)
1746 /* The expression is not yet available, value-number lhs to
1747 the new SSA_NAME we created. */
1748 /* Initialize value-number information properly. */
1749 VN_INFO_GET (result)->valnum = result;
1750 VN_INFO (result)->value_id = get_next_value_id ();
1751 gimple_seq_add_stmt_without_update (&VN_INFO (result)->expr,
1752 new_stmt);
1753 VN_INFO (result)->needs_insertion = true;
1754 /* ??? PRE phi-translation inserts NARYs without corresponding
1755 SSA name result. Re-use those but set their result according
1756 to the stmt we just built. */
1757 vn_nary_op_t nary = NULL;
1758 vn_nary_op_lookup_stmt (new_stmt, &nary);
1759 if (nary)
1761 gcc_assert (nary->result == NULL_TREE);
1762 nary->result = gimple_assign_lhs (new_stmt);
1764 /* As all "inserted" statements are singleton SCCs, insert
1765 to the valid table. This is strictly needed to
1766 avoid re-generating new value SSA_NAMEs for the same
1767 expression during SCC iteration over and over (the
1768 optimistic table gets cleared after each iteration).
1769 We do not need to insert into the optimistic table, as
1770 lookups there will fall back to the valid table. */
1771 else if (current_info == optimistic_info)
1773 current_info = valid_info;
1774 vn_nary_op_insert_stmt (new_stmt, result);
1775 current_info = optimistic_info;
1777 else
1778 vn_nary_op_insert_stmt (new_stmt, result);
1779 if (dump_file && (dump_flags & TDF_DETAILS))
1781 fprintf (dump_file, "Inserting name ");
1782 print_generic_expr (dump_file, result);
1783 fprintf (dump_file, " for expression ");
1784 print_gimple_expr (dump_file, new_stmt, 0, TDF_SLIM);
1785 fprintf (dump_file, "\n");
1788 return result;
1791 /* Return a value-number for RCODE OPS... either by looking up an existing
1792 value-number for the simplified result or by inserting the operation. */
1794 static tree
1795 vn_nary_build_or_lookup (code_helper rcode, tree type, tree *ops)
1797 return vn_nary_build_or_lookup_1 (rcode, type, ops, true);
1800 /* Try to simplify the expression RCODE OPS... of type TYPE and return
1801 its value if present. */
1803 tree
1804 vn_nary_simplify (vn_nary_op_t nary)
1806 if (nary->length > 3)
1807 return NULL_TREE;
1808 tree ops[3];
1809 memcpy (ops, nary->op, sizeof (tree) * nary->length);
1810 return vn_nary_build_or_lookup_1 (nary->opcode, nary->type, ops, false);
1814 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1815 from the statement defining VUSE and if not successful tries to
1816 translate *REFP and VR_ through an aggregate copy at the definition
1817 of VUSE. If *DISAMBIGUATE_ONLY is true then do not perform translation
1818 of *REF and *VR. If only disambiguation was performed then
1819 *DISAMBIGUATE_ONLY is set to true. */
1821 static void *
1822 vn_reference_lookup_3 (ao_ref *ref, tree vuse, void *vr_,
1823 bool *disambiguate_only)
1825 vn_reference_t vr = (vn_reference_t)vr_;
1826 gimple *def_stmt = SSA_NAME_DEF_STMT (vuse);
1827 tree base = ao_ref_base (ref);
1828 HOST_WIDE_INT offseti, maxsizei;
1829 static vec<vn_reference_op_s> lhs_ops;
1830 ao_ref lhs_ref;
1831 bool lhs_ref_ok = false;
1832 poly_int64 copy_size;
1834 /* If the reference is based on a parameter that was determined as
1835 pointing to readonly memory it doesn't change. */
1836 if (TREE_CODE (base) == MEM_REF
1837 && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME
1838 && SSA_NAME_IS_DEFAULT_DEF (TREE_OPERAND (base, 0))
1839 && bitmap_bit_p (const_parms,
1840 SSA_NAME_VERSION (TREE_OPERAND (base, 0))))
1842 *disambiguate_only = true;
1843 return NULL;
1846 /* First try to disambiguate after value-replacing in the definitions LHS. */
1847 if (is_gimple_assign (def_stmt))
1849 tree lhs = gimple_assign_lhs (def_stmt);
1850 bool valueized_anything = false;
1851 /* Avoid re-allocation overhead. */
1852 lhs_ops.truncate (0);
1853 copy_reference_ops_from_ref (lhs, &lhs_ops);
1854 lhs_ops = valueize_refs_1 (lhs_ops, &valueized_anything);
1855 if (valueized_anything)
1857 lhs_ref_ok = ao_ref_init_from_vn_reference (&lhs_ref,
1858 get_alias_set (lhs),
1859 TREE_TYPE (lhs), lhs_ops);
1860 if (lhs_ref_ok
1861 && !refs_may_alias_p_1 (ref, &lhs_ref, true))
1863 *disambiguate_only = true;
1864 return NULL;
1867 else
1869 ao_ref_init (&lhs_ref, lhs);
1870 lhs_ref_ok = true;
1873 /* If we reach a clobbering statement try to skip it and see if
1874 we find a VN result with exactly the same value as the
1875 possible clobber. In this case we can ignore the clobber
1876 and return the found value.
1877 Note that we don't need to worry about partial overlapping
1878 accesses as we then can use TBAA to disambiguate against the
1879 clobbering statement when looking up a load (thus the
1880 VN_WALKREWRITE guard). */
1881 if (vn_walk_kind == VN_WALKREWRITE
1882 && is_gimple_reg_type (TREE_TYPE (lhs))
1883 && types_compatible_p (TREE_TYPE (lhs), vr->type))
1885 tree *saved_last_vuse_ptr = last_vuse_ptr;
1886 /* Do not update last_vuse_ptr in vn_reference_lookup_2. */
1887 last_vuse_ptr = NULL;
1888 tree saved_vuse = vr->vuse;
1889 hashval_t saved_hashcode = vr->hashcode;
1890 void *res = vn_reference_lookup_2 (ref,
1891 gimple_vuse (def_stmt), 0, vr);
1892 /* Need to restore vr->vuse and vr->hashcode. */
1893 vr->vuse = saved_vuse;
1894 vr->hashcode = saved_hashcode;
1895 last_vuse_ptr = saved_last_vuse_ptr;
1896 if (res && res != (void *)-1)
1898 vn_reference_t vnresult = (vn_reference_t) res;
1899 if (vnresult->result
1900 && operand_equal_p (vnresult->result,
1901 gimple_assign_rhs1 (def_stmt), 0))
1902 return res;
1906 else if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL)
1907 && gimple_call_num_args (def_stmt) <= 4)
1909 /* For builtin calls valueize its arguments and call the
1910 alias oracle again. Valueization may improve points-to
1911 info of pointers and constify size and position arguments.
1912 Originally this was motivated by PR61034 which has
1913 conditional calls to free falsely clobbering ref because
1914 of imprecise points-to info of the argument. */
1915 tree oldargs[4];
1916 bool valueized_anything = false;
1917 for (unsigned i = 0; i < gimple_call_num_args (def_stmt); ++i)
1919 oldargs[i] = gimple_call_arg (def_stmt, i);
1920 tree val = vn_valueize (oldargs[i]);
1921 if (val != oldargs[i])
1923 gimple_call_set_arg (def_stmt, i, val);
1924 valueized_anything = true;
1927 if (valueized_anything)
1929 bool res = call_may_clobber_ref_p_1 (as_a <gcall *> (def_stmt),
1930 ref);
1931 for (unsigned i = 0; i < gimple_call_num_args (def_stmt); ++i)
1932 gimple_call_set_arg (def_stmt, i, oldargs[i]);
1933 if (!res)
1935 *disambiguate_only = true;
1936 return NULL;
1941 if (*disambiguate_only)
1942 return (void *)-1;
1944 /* If we cannot constrain the size of the reference we cannot
1945 test if anything kills it. */
1946 if (!ref->max_size_known_p ())
1947 return (void *)-1;
1949 poly_int64 offset = ref->offset;
1950 poly_int64 maxsize = ref->max_size;
1952 /* We can't deduce anything useful from clobbers. */
1953 if (gimple_clobber_p (def_stmt))
1954 return (void *)-1;
1956 /* def_stmt may-defs *ref. See if we can derive a value for *ref
1957 from that definition.
1958 1) Memset. */
1959 if (is_gimple_reg_type (vr->type)
1960 && gimple_call_builtin_p (def_stmt, BUILT_IN_MEMSET)
1961 && integer_zerop (gimple_call_arg (def_stmt, 1))
1962 && poly_int_tree_p (gimple_call_arg (def_stmt, 2))
1963 && TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR)
1965 tree ref2 = TREE_OPERAND (gimple_call_arg (def_stmt, 0), 0);
1966 tree base2;
1967 poly_int64 offset2, size2, maxsize2;
1968 bool reverse;
1969 base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &maxsize2,
1970 &reverse);
1971 tree len = gimple_call_arg (def_stmt, 2);
1972 if (known_size_p (maxsize2)
1973 && operand_equal_p (base, base2, 0)
1974 && known_subrange_p (offset, maxsize, offset2,
1975 wi::to_poly_offset (len) << LOG2_BITS_PER_UNIT))
1977 tree val = build_zero_cst (vr->type);
1978 return vn_reference_lookup_or_insert_for_pieces
1979 (vuse, vr->set, vr->type, vr->operands, val);
1983 /* 2) Assignment from an empty CONSTRUCTOR. */
1984 else if (is_gimple_reg_type (vr->type)
1985 && gimple_assign_single_p (def_stmt)
1986 && gimple_assign_rhs_code (def_stmt) == CONSTRUCTOR
1987 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt)) == 0)
1989 tree base2;
1990 poly_int64 offset2, size2, maxsize2;
1991 bool reverse;
1992 base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
1993 &offset2, &size2, &maxsize2, &reverse);
1994 if (known_size_p (maxsize2)
1995 && operand_equal_p (base, base2, 0)
1996 && known_subrange_p (offset, maxsize, offset2, size2))
1998 tree val = build_zero_cst (vr->type);
1999 return vn_reference_lookup_or_insert_for_pieces
2000 (vuse, vr->set, vr->type, vr->operands, val);
2004 /* 3) Assignment from a constant. We can use folds native encode/interpret
2005 routines to extract the assigned bits. */
2006 else if (known_eq (ref->size, maxsize)
2007 && is_gimple_reg_type (vr->type)
2008 && !contains_storage_order_barrier_p (vr->operands)
2009 && gimple_assign_single_p (def_stmt)
2010 && CHAR_BIT == 8 && BITS_PER_UNIT == 8
2011 /* native_encode and native_decode operate on arrays of bytes
2012 and so fundamentally need a compile-time size and offset. */
2013 && maxsize.is_constant (&maxsizei)
2014 && maxsizei % BITS_PER_UNIT == 0
2015 && offset.is_constant (&offseti)
2016 && offseti % BITS_PER_UNIT == 0
2017 && (is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt))
2018 || (TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME
2019 && is_gimple_min_invariant (SSA_VAL (gimple_assign_rhs1 (def_stmt))))))
2021 tree base2;
2022 HOST_WIDE_INT offset2, size2;
2023 bool reverse;
2024 base2 = get_ref_base_and_extent_hwi (gimple_assign_lhs (def_stmt),
2025 &offset2, &size2, &reverse);
2026 if (base2
2027 && !reverse
2028 && size2 % BITS_PER_UNIT == 0
2029 && offset2 % BITS_PER_UNIT == 0
2030 && operand_equal_p (base, base2, 0)
2031 && known_subrange_p (offseti, maxsizei, offset2, size2))
2033 /* We support up to 512-bit values (for V8DFmode). */
2034 unsigned char buffer[64];
2035 int len;
2037 tree rhs = gimple_assign_rhs1 (def_stmt);
2038 if (TREE_CODE (rhs) == SSA_NAME)
2039 rhs = SSA_VAL (rhs);
2040 len = native_encode_expr (gimple_assign_rhs1 (def_stmt),
2041 buffer, sizeof (buffer));
2042 if (len > 0)
2044 tree type = vr->type;
2045 /* Make sure to interpret in a type that has a range
2046 covering the whole access size. */
2047 if (INTEGRAL_TYPE_P (vr->type)
2048 && maxsizei != TYPE_PRECISION (vr->type))
2049 type = build_nonstandard_integer_type (maxsizei,
2050 TYPE_UNSIGNED (type));
2051 tree val = native_interpret_expr (type,
2052 buffer
2053 + ((offseti - offset2)
2054 / BITS_PER_UNIT),
2055 maxsizei / BITS_PER_UNIT);
2056 /* If we chop off bits because the types precision doesn't
2057 match the memory access size this is ok when optimizing
2058 reads but not when called from the DSE code during
2059 elimination. */
2060 if (val
2061 && type != vr->type)
2063 if (! int_fits_type_p (val, vr->type))
2064 val = NULL_TREE;
2065 else
2066 val = fold_convert (vr->type, val);
2069 if (val)
2070 return vn_reference_lookup_or_insert_for_pieces
2071 (vuse, vr->set, vr->type, vr->operands, val);
2076 /* 4) Assignment from an SSA name which definition we may be able
2077 to access pieces from. */
2078 else if (known_eq (ref->size, maxsize)
2079 && is_gimple_reg_type (vr->type)
2080 && !contains_storage_order_barrier_p (vr->operands)
2081 && gimple_assign_single_p (def_stmt)
2082 && TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME)
2084 tree base2;
2085 poly_int64 offset2, size2, maxsize2;
2086 bool reverse;
2087 base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt),
2088 &offset2, &size2, &maxsize2,
2089 &reverse);
2090 if (!reverse
2091 && known_size_p (maxsize2)
2092 && known_eq (maxsize2, size2)
2093 && operand_equal_p (base, base2, 0)
2094 && known_subrange_p (offset, maxsize, offset2, size2)
2095 /* ??? We can't handle bitfield precision extracts without
2096 either using an alternate type for the BIT_FIELD_REF and
2097 then doing a conversion or possibly adjusting the offset
2098 according to endianness. */
2099 && (! INTEGRAL_TYPE_P (vr->type)
2100 || known_eq (ref->size, TYPE_PRECISION (vr->type)))
2101 && multiple_p (ref->size, BITS_PER_UNIT))
2103 code_helper rcode = BIT_FIELD_REF;
2104 tree ops[3];
2105 ops[0] = SSA_VAL (gimple_assign_rhs1 (def_stmt));
2106 ops[1] = bitsize_int (ref->size);
2107 ops[2] = bitsize_int (offset - offset2);
2108 tree val = vn_nary_build_or_lookup (rcode, vr->type, ops);
2109 if (val
2110 && (TREE_CODE (val) != SSA_NAME
2111 || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val)))
2113 vn_reference_t res = vn_reference_lookup_or_insert_for_pieces
2114 (vuse, vr->set, vr->type, vr->operands, val);
2115 return res;
2120 /* 5) For aggregate copies translate the reference through them if
2121 the copy kills ref. */
2122 else if (vn_walk_kind == VN_WALKREWRITE
2123 && gimple_assign_single_p (def_stmt)
2124 && (DECL_P (gimple_assign_rhs1 (def_stmt))
2125 || TREE_CODE (gimple_assign_rhs1 (def_stmt)) == MEM_REF
2126 || handled_component_p (gimple_assign_rhs1 (def_stmt))))
2128 tree base2;
2129 int i, j, k;
2130 auto_vec<vn_reference_op_s> rhs;
2131 vn_reference_op_t vro;
2132 ao_ref r;
2134 if (!lhs_ref_ok)
2135 return (void *)-1;
2137 /* See if the assignment kills REF. */
2138 base2 = ao_ref_base (&lhs_ref);
2139 if (!lhs_ref.max_size_known_p ()
2140 || (base != base2
2141 && (TREE_CODE (base) != MEM_REF
2142 || TREE_CODE (base2) != MEM_REF
2143 || TREE_OPERAND (base, 0) != TREE_OPERAND (base2, 0)
2144 || !tree_int_cst_equal (TREE_OPERAND (base, 1),
2145 TREE_OPERAND (base2, 1))))
2146 || !stmt_kills_ref_p (def_stmt, ref))
2147 return (void *)-1;
2149 /* Find the common base of ref and the lhs. lhs_ops already
2150 contains valueized operands for the lhs. */
2151 i = vr->operands.length () - 1;
2152 j = lhs_ops.length () - 1;
2153 while (j >= 0 && i >= 0
2154 && vn_reference_op_eq (&vr->operands[i], &lhs_ops[j]))
2156 i--;
2157 j--;
2160 /* ??? The innermost op should always be a MEM_REF and we already
2161 checked that the assignment to the lhs kills vr. Thus for
2162 aggregate copies using char[] types the vn_reference_op_eq
2163 may fail when comparing types for compatibility. But we really
2164 don't care here - further lookups with the rewritten operands
2165 will simply fail if we messed up types too badly. */
2166 poly_int64 extra_off = 0;
2167 if (j == 0 && i >= 0
2168 && lhs_ops[0].opcode == MEM_REF
2169 && maybe_ne (lhs_ops[0].off, -1))
2171 if (known_eq (lhs_ops[0].off, vr->operands[i].off))
2172 i--, j--;
2173 else if (vr->operands[i].opcode == MEM_REF
2174 && maybe_ne (vr->operands[i].off, -1))
2176 extra_off = vr->operands[i].off - lhs_ops[0].off;
2177 i--, j--;
2181 /* i now points to the first additional op.
2182 ??? LHS may not be completely contained in VR, one or more
2183 VIEW_CONVERT_EXPRs could be in its way. We could at least
2184 try handling outermost VIEW_CONVERT_EXPRs. */
2185 if (j != -1)
2186 return (void *)-1;
2188 /* Punt if the additional ops contain a storage order barrier. */
2189 for (k = i; k >= 0; k--)
2191 vro = &vr->operands[k];
2192 if (vro->opcode == VIEW_CONVERT_EXPR && vro->reverse)
2193 return (void *)-1;
2196 /* Now re-write REF to be based on the rhs of the assignment. */
2197 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt), &rhs);
2199 /* Apply an extra offset to the inner MEM_REF of the RHS. */
2200 if (maybe_ne (extra_off, 0))
2202 if (rhs.length () < 2
2203 || rhs[0].opcode != MEM_REF
2204 || known_eq (rhs[0].off, -1))
2205 return (void *)-1;
2206 rhs[0].off += extra_off;
2207 rhs[0].op0 = int_const_binop (PLUS_EXPR, rhs[0].op0,
2208 build_int_cst (TREE_TYPE (rhs[0].op0),
2209 extra_off));
2212 /* We need to pre-pend vr->operands[0..i] to rhs. */
2213 vec<vn_reference_op_s> old = vr->operands;
2214 if (i + 1 + rhs.length () > vr->operands.length ())
2215 vr->operands.safe_grow (i + 1 + rhs.length ());
2216 else
2217 vr->operands.truncate (i + 1 + rhs.length ());
2218 FOR_EACH_VEC_ELT (rhs, j, vro)
2219 vr->operands[i + 1 + j] = *vro;
2220 vr->operands = valueize_refs (vr->operands);
2221 if (old == shared_lookup_references)
2222 shared_lookup_references = vr->operands;
2223 vr->hashcode = vn_reference_compute_hash (vr);
2225 /* Try folding the new reference to a constant. */
2226 tree val = fully_constant_vn_reference_p (vr);
2227 if (val)
2228 return vn_reference_lookup_or_insert_for_pieces
2229 (vuse, vr->set, vr->type, vr->operands, val);
2231 /* Adjust *ref from the new operands. */
2232 if (!ao_ref_init_from_vn_reference (&r, vr->set, vr->type, vr->operands))
2233 return (void *)-1;
2234 /* This can happen with bitfields. */
2235 if (maybe_ne (ref->size, r.size))
2236 return (void *)-1;
2237 *ref = r;
2239 /* Do not update last seen VUSE after translating. */
2240 last_vuse_ptr = NULL;
2242 /* Keep looking for the adjusted *REF / VR pair. */
2243 return NULL;
2246 /* 6) For memcpy copies translate the reference through them if
2247 the copy kills ref. */
2248 else if (vn_walk_kind == VN_WALKREWRITE
2249 && is_gimple_reg_type (vr->type)
2250 /* ??? Handle BCOPY as well. */
2251 && (gimple_call_builtin_p (def_stmt, BUILT_IN_MEMCPY)
2252 || gimple_call_builtin_p (def_stmt, BUILT_IN_MEMPCPY)
2253 || gimple_call_builtin_p (def_stmt, BUILT_IN_MEMMOVE))
2254 && (TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR
2255 || TREE_CODE (gimple_call_arg (def_stmt, 0)) == SSA_NAME)
2256 && (TREE_CODE (gimple_call_arg (def_stmt, 1)) == ADDR_EXPR
2257 || TREE_CODE (gimple_call_arg (def_stmt, 1)) == SSA_NAME)
2258 && poly_int_tree_p (gimple_call_arg (def_stmt, 2), &copy_size))
2260 tree lhs, rhs;
2261 ao_ref r;
2262 poly_int64 rhs_offset, lhs_offset;
2263 vn_reference_op_s op;
2264 poly_uint64 mem_offset;
2265 poly_int64 at, byte_maxsize;
2267 /* Only handle non-variable, addressable refs. */
2268 if (maybe_ne (ref->size, maxsize)
2269 || !multiple_p (offset, BITS_PER_UNIT, &at)
2270 || !multiple_p (maxsize, BITS_PER_UNIT, &byte_maxsize))
2271 return (void *)-1;
2273 /* Extract a pointer base and an offset for the destination. */
2274 lhs = gimple_call_arg (def_stmt, 0);
2275 lhs_offset = 0;
2276 if (TREE_CODE (lhs) == SSA_NAME)
2278 lhs = SSA_VAL (lhs);
2279 if (TREE_CODE (lhs) == SSA_NAME)
2281 gimple *def_stmt = SSA_NAME_DEF_STMT (lhs);
2282 if (gimple_assign_single_p (def_stmt)
2283 && gimple_assign_rhs_code (def_stmt) == ADDR_EXPR)
2284 lhs = gimple_assign_rhs1 (def_stmt);
2287 if (TREE_CODE (lhs) == ADDR_EXPR)
2289 tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (lhs, 0),
2290 &lhs_offset);
2291 if (!tem)
2292 return (void *)-1;
2293 if (TREE_CODE (tem) == MEM_REF
2294 && poly_int_tree_p (TREE_OPERAND (tem, 1), &mem_offset))
2296 lhs = TREE_OPERAND (tem, 0);
2297 if (TREE_CODE (lhs) == SSA_NAME)
2298 lhs = SSA_VAL (lhs);
2299 lhs_offset += mem_offset;
2301 else if (DECL_P (tem))
2302 lhs = build_fold_addr_expr (tem);
2303 else
2304 return (void *)-1;
2306 if (TREE_CODE (lhs) != SSA_NAME
2307 && TREE_CODE (lhs) != ADDR_EXPR)
2308 return (void *)-1;
2310 /* Extract a pointer base and an offset for the source. */
2311 rhs = gimple_call_arg (def_stmt, 1);
2312 rhs_offset = 0;
2313 if (TREE_CODE (rhs) == SSA_NAME)
2314 rhs = SSA_VAL (rhs);
2315 if (TREE_CODE (rhs) == ADDR_EXPR)
2317 tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs, 0),
2318 &rhs_offset);
2319 if (!tem)
2320 return (void *)-1;
2321 if (TREE_CODE (tem) == MEM_REF
2322 && poly_int_tree_p (TREE_OPERAND (tem, 1), &mem_offset))
2324 rhs = TREE_OPERAND (tem, 0);
2325 rhs_offset += mem_offset;
2327 else if (DECL_P (tem)
2328 || TREE_CODE (tem) == STRING_CST)
2329 rhs = build_fold_addr_expr (tem);
2330 else
2331 return (void *)-1;
2333 if (TREE_CODE (rhs) != SSA_NAME
2334 && TREE_CODE (rhs) != ADDR_EXPR)
2335 return (void *)-1;
2337 /* The bases of the destination and the references have to agree. */
2338 if (TREE_CODE (base) == MEM_REF)
2340 if (TREE_OPERAND (base, 0) != lhs
2341 || !poly_int_tree_p (TREE_OPERAND (base, 1), &mem_offset))
2342 return (void *) -1;
2343 at += mem_offset;
2345 else if (!DECL_P (base)
2346 || TREE_CODE (lhs) != ADDR_EXPR
2347 || TREE_OPERAND (lhs, 0) != base)
2348 return (void *)-1;
2350 /* If the access is completely outside of the memcpy destination
2351 area there is no aliasing. */
2352 if (!ranges_maybe_overlap_p (lhs_offset, copy_size, at, byte_maxsize))
2353 return NULL;
2354 /* And the access has to be contained within the memcpy destination. */
2355 if (!known_subrange_p (at, byte_maxsize, lhs_offset, copy_size))
2356 return (void *)-1;
2358 /* Make room for 2 operands in the new reference. */
2359 if (vr->operands.length () < 2)
2361 vec<vn_reference_op_s> old = vr->operands;
2362 vr->operands.safe_grow_cleared (2);
2363 if (old == shared_lookup_references)
2364 shared_lookup_references = vr->operands;
2366 else
2367 vr->operands.truncate (2);
2369 /* The looked-through reference is a simple MEM_REF. */
2370 memset (&op, 0, sizeof (op));
2371 op.type = vr->type;
2372 op.opcode = MEM_REF;
2373 op.op0 = build_int_cst (ptr_type_node, at - lhs_offset + rhs_offset);
2374 op.off = at - lhs_offset + rhs_offset;
2375 vr->operands[0] = op;
2376 op.type = TREE_TYPE (rhs);
2377 op.opcode = TREE_CODE (rhs);
2378 op.op0 = rhs;
2379 op.off = -1;
2380 vr->operands[1] = op;
2381 vr->hashcode = vn_reference_compute_hash (vr);
2383 /* Try folding the new reference to a constant. */
2384 tree val = fully_constant_vn_reference_p (vr);
2385 if (val)
2386 return vn_reference_lookup_or_insert_for_pieces
2387 (vuse, vr->set, vr->type, vr->operands, val);
2389 /* Adjust *ref from the new operands. */
2390 if (!ao_ref_init_from_vn_reference (&r, vr->set, vr->type, vr->operands))
2391 return (void *)-1;
2392 /* This can happen with bitfields. */
2393 if (maybe_ne (ref->size, r.size))
2394 return (void *)-1;
2395 *ref = r;
2397 /* Do not update last seen VUSE after translating. */
2398 last_vuse_ptr = NULL;
2400 /* Keep looking for the adjusted *REF / VR pair. */
2401 return NULL;
2404 /* Bail out and stop walking. */
2405 return (void *)-1;
2408 /* Return a reference op vector from OP that can be used for
2409 vn_reference_lookup_pieces. The caller is responsible for releasing
2410 the vector. */
2412 vec<vn_reference_op_s>
2413 vn_reference_operands_for_lookup (tree op)
2415 bool valueized;
2416 return valueize_shared_reference_ops_from_ref (op, &valueized).copy ();
2419 /* Lookup a reference operation by it's parts, in the current hash table.
2420 Returns the resulting value number if it exists in the hash table,
2421 NULL_TREE otherwise. VNRESULT will be filled in with the actual
2422 vn_reference_t stored in the hashtable if something is found. */
2424 tree
2425 vn_reference_lookup_pieces (tree vuse, alias_set_type set, tree type,
2426 vec<vn_reference_op_s> operands,
2427 vn_reference_t *vnresult, vn_lookup_kind kind)
2429 struct vn_reference_s vr1;
2430 vn_reference_t tmp;
2431 tree cst;
2433 if (!vnresult)
2434 vnresult = &tmp;
2435 *vnresult = NULL;
2437 vr1.vuse = vuse_ssa_val (vuse);
2438 shared_lookup_references.truncate (0);
2439 shared_lookup_references.safe_grow (operands.length ());
2440 memcpy (shared_lookup_references.address (),
2441 operands.address (),
2442 sizeof (vn_reference_op_s)
2443 * operands.length ());
2444 vr1.operands = operands = shared_lookup_references
2445 = valueize_refs (shared_lookup_references);
2446 vr1.type = type;
2447 vr1.set = set;
2448 vr1.hashcode = vn_reference_compute_hash (&vr1);
2449 if ((cst = fully_constant_vn_reference_p (&vr1)))
2450 return cst;
2452 vn_reference_lookup_1 (&vr1, vnresult);
2453 if (!*vnresult
2454 && kind != VN_NOWALK
2455 && vr1.vuse)
2457 ao_ref r;
2458 vn_walk_kind = kind;
2459 if (ao_ref_init_from_vn_reference (&r, set, type, vr1.operands))
2460 *vnresult =
2461 (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse,
2462 vn_reference_lookup_2,
2463 vn_reference_lookup_3,
2464 vuse_ssa_val, &vr1);
2465 gcc_checking_assert (vr1.operands == shared_lookup_references);
2468 if (*vnresult)
2469 return (*vnresult)->result;
2471 return NULL_TREE;
2474 /* Lookup OP in the current hash table, and return the resulting value
2475 number if it exists in the hash table. Return NULL_TREE if it does
2476 not exist in the hash table or if the result field of the structure
2477 was NULL.. VNRESULT will be filled in with the vn_reference_t
2478 stored in the hashtable if one exists. When TBAA_P is false assume
2479 we are looking up a store and treat it as having alias-set zero. */
2481 tree
2482 vn_reference_lookup (tree op, tree vuse, vn_lookup_kind kind,
2483 vn_reference_t *vnresult, bool tbaa_p)
2485 vec<vn_reference_op_s> operands;
2486 struct vn_reference_s vr1;
2487 tree cst;
2488 bool valuezied_anything;
2490 if (vnresult)
2491 *vnresult = NULL;
2493 vr1.vuse = vuse_ssa_val (vuse);
2494 vr1.operands = operands
2495 = valueize_shared_reference_ops_from_ref (op, &valuezied_anything);
2496 vr1.type = TREE_TYPE (op);
2497 vr1.set = tbaa_p ? get_alias_set (op) : 0;
2498 vr1.hashcode = vn_reference_compute_hash (&vr1);
2499 if ((cst = fully_constant_vn_reference_p (&vr1)))
2500 return cst;
2502 if (kind != VN_NOWALK
2503 && vr1.vuse)
2505 vn_reference_t wvnresult;
2506 ao_ref r;
2507 /* Make sure to use a valueized reference if we valueized anything.
2508 Otherwise preserve the full reference for advanced TBAA. */
2509 if (!valuezied_anything
2510 || !ao_ref_init_from_vn_reference (&r, vr1.set, vr1.type,
2511 vr1.operands))
2512 ao_ref_init (&r, op);
2513 if (! tbaa_p)
2514 r.ref_alias_set = r.base_alias_set = 0;
2515 vn_walk_kind = kind;
2516 wvnresult =
2517 (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse,
2518 vn_reference_lookup_2,
2519 vn_reference_lookup_3,
2520 vuse_ssa_val, &vr1);
2521 gcc_checking_assert (vr1.operands == shared_lookup_references);
2522 if (wvnresult)
2524 if (vnresult)
2525 *vnresult = wvnresult;
2526 return wvnresult->result;
2529 return NULL_TREE;
2532 return vn_reference_lookup_1 (&vr1, vnresult);
2535 /* Lookup CALL in the current hash table and return the entry in
2536 *VNRESULT if found. Populates *VR for the hashtable lookup. */
2538 void
2539 vn_reference_lookup_call (gcall *call, vn_reference_t *vnresult,
2540 vn_reference_t vr)
2542 if (vnresult)
2543 *vnresult = NULL;
2545 tree vuse = gimple_vuse (call);
2547 vr->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
2548 vr->operands = valueize_shared_reference_ops_from_call (call);
2549 vr->type = gimple_expr_type (call);
2550 vr->set = 0;
2551 vr->hashcode = vn_reference_compute_hash (vr);
2552 vn_reference_lookup_1 (vr, vnresult);
2555 /* Insert OP into the current hash table with a value number of
2556 RESULT, and return the resulting reference structure we created. */
2558 static vn_reference_t
2559 vn_reference_insert (tree op, tree result, tree vuse, tree vdef)
2561 vn_reference_s **slot;
2562 vn_reference_t vr1;
2563 bool tem;
2565 vr1 = current_info->references_pool->allocate ();
2566 if (TREE_CODE (result) == SSA_NAME)
2567 vr1->value_id = VN_INFO (result)->value_id;
2568 else
2569 vr1->value_id = get_or_alloc_constant_value_id (result);
2570 vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
2571 vr1->operands = valueize_shared_reference_ops_from_ref (op, &tem).copy ();
2572 vr1->type = TREE_TYPE (op);
2573 vr1->set = get_alias_set (op);
2574 vr1->hashcode = vn_reference_compute_hash (vr1);
2575 vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result;
2576 vr1->result_vdef = vdef;
2578 slot = current_info->references->find_slot_with_hash (vr1, vr1->hashcode,
2579 INSERT);
2581 /* Because we lookup stores using vuses, and value number failures
2582 using the vdefs (see visit_reference_op_store for how and why),
2583 it's possible that on failure we may try to insert an already
2584 inserted store. This is not wrong, there is no ssa name for a
2585 store that we could use as a differentiator anyway. Thus, unlike
2586 the other lookup functions, you cannot gcc_assert (!*slot)
2587 here. */
2589 /* But free the old slot in case of a collision. */
2590 if (*slot)
2591 free_reference (*slot);
2593 *slot = vr1;
2594 return vr1;
2597 /* Insert a reference by it's pieces into the current hash table with
2598 a value number of RESULT. Return the resulting reference
2599 structure we created. */
2601 vn_reference_t
2602 vn_reference_insert_pieces (tree vuse, alias_set_type set, tree type,
2603 vec<vn_reference_op_s> operands,
2604 tree result, unsigned int value_id)
2607 vn_reference_s **slot;
2608 vn_reference_t vr1;
2610 vr1 = current_info->references_pool->allocate ();
2611 vr1->value_id = value_id;
2612 vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
2613 vr1->operands = valueize_refs (operands);
2614 vr1->type = type;
2615 vr1->set = set;
2616 vr1->hashcode = vn_reference_compute_hash (vr1);
2617 if (result && TREE_CODE (result) == SSA_NAME)
2618 result = SSA_VAL (result);
2619 vr1->result = result;
2621 slot = current_info->references->find_slot_with_hash (vr1, vr1->hashcode,
2622 INSERT);
2624 /* At this point we should have all the things inserted that we have
2625 seen before, and we should never try inserting something that
2626 already exists. */
2627 gcc_assert (!*slot);
2628 if (*slot)
2629 free_reference (*slot);
2631 *slot = vr1;
2632 return vr1;
2635 /* Compute and return the hash value for nary operation VBO1. */
2637 static hashval_t
2638 vn_nary_op_compute_hash (const vn_nary_op_t vno1)
2640 inchash::hash hstate;
2641 unsigned i;
2643 for (i = 0; i < vno1->length; ++i)
2644 if (TREE_CODE (vno1->op[i]) == SSA_NAME)
2645 vno1->op[i] = SSA_VAL (vno1->op[i]);
2647 if (((vno1->length == 2
2648 && commutative_tree_code (vno1->opcode))
2649 || (vno1->length == 3
2650 && commutative_ternary_tree_code (vno1->opcode)))
2651 && tree_swap_operands_p (vno1->op[0], vno1->op[1]))
2652 std::swap (vno1->op[0], vno1->op[1]);
2653 else if (TREE_CODE_CLASS (vno1->opcode) == tcc_comparison
2654 && tree_swap_operands_p (vno1->op[0], vno1->op[1]))
2656 std::swap (vno1->op[0], vno1->op[1]);
2657 vno1->opcode = swap_tree_comparison (vno1->opcode);
2660 hstate.add_int (vno1->opcode);
2661 for (i = 0; i < vno1->length; ++i)
2662 inchash::add_expr (vno1->op[i], hstate);
2664 return hstate.end ();
2667 /* Compare nary operations VNO1 and VNO2 and return true if they are
2668 equivalent. */
2670 bool
2671 vn_nary_op_eq (const_vn_nary_op_t const vno1, const_vn_nary_op_t const vno2)
2673 unsigned i;
2675 if (vno1->hashcode != vno2->hashcode)
2676 return false;
2678 if (vno1->length != vno2->length)
2679 return false;
2681 if (vno1->opcode != vno2->opcode
2682 || !types_compatible_p (vno1->type, vno2->type))
2683 return false;
2685 for (i = 0; i < vno1->length; ++i)
2686 if (!expressions_equal_p (vno1->op[i], vno2->op[i]))
2687 return false;
2689 /* BIT_INSERT_EXPR has an implict operand as the type precision
2690 of op1. Need to check to make sure they are the same. */
2691 if (vno1->opcode == BIT_INSERT_EXPR
2692 && TREE_CODE (vno1->op[1]) == INTEGER_CST
2693 && TYPE_PRECISION (TREE_TYPE (vno1->op[1]))
2694 != TYPE_PRECISION (TREE_TYPE (vno2->op[1])))
2695 return false;
2697 return true;
2700 /* Initialize VNO from the pieces provided. */
2702 static void
2703 init_vn_nary_op_from_pieces (vn_nary_op_t vno, unsigned int length,
2704 enum tree_code code, tree type, tree *ops)
2706 vno->opcode = code;
2707 vno->length = length;
2708 vno->type = type;
2709 memcpy (&vno->op[0], ops, sizeof (tree) * length);
2712 /* Initialize VNO from OP. */
2714 static void
2715 init_vn_nary_op_from_op (vn_nary_op_t vno, tree op)
2717 unsigned i;
2719 vno->opcode = TREE_CODE (op);
2720 vno->length = TREE_CODE_LENGTH (TREE_CODE (op));
2721 vno->type = TREE_TYPE (op);
2722 for (i = 0; i < vno->length; ++i)
2723 vno->op[i] = TREE_OPERAND (op, i);
2726 /* Return the number of operands for a vn_nary ops structure from STMT. */
2728 static unsigned int
2729 vn_nary_length_from_stmt (gimple *stmt)
2731 switch (gimple_assign_rhs_code (stmt))
2733 case REALPART_EXPR:
2734 case IMAGPART_EXPR:
2735 case VIEW_CONVERT_EXPR:
2736 return 1;
2738 case BIT_FIELD_REF:
2739 return 3;
2741 case CONSTRUCTOR:
2742 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
2744 default:
2745 return gimple_num_ops (stmt) - 1;
2749 /* Initialize VNO from STMT. */
2751 static void
2752 init_vn_nary_op_from_stmt (vn_nary_op_t vno, gimple *stmt)
2754 unsigned i;
2756 vno->opcode = gimple_assign_rhs_code (stmt);
2757 vno->type = gimple_expr_type (stmt);
2758 switch (vno->opcode)
2760 case REALPART_EXPR:
2761 case IMAGPART_EXPR:
2762 case VIEW_CONVERT_EXPR:
2763 vno->length = 1;
2764 vno->op[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
2765 break;
2767 case BIT_FIELD_REF:
2768 vno->length = 3;
2769 vno->op[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
2770 vno->op[1] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 1);
2771 vno->op[2] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 2);
2772 break;
2774 case CONSTRUCTOR:
2775 vno->length = CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
2776 for (i = 0; i < vno->length; ++i)
2777 vno->op[i] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt), i)->value;
2778 break;
2780 default:
2781 gcc_checking_assert (!gimple_assign_single_p (stmt));
2782 vno->length = gimple_num_ops (stmt) - 1;
2783 for (i = 0; i < vno->length; ++i)
2784 vno->op[i] = gimple_op (stmt, i + 1);
2788 /* Compute the hashcode for VNO and look for it in the hash table;
2789 return the resulting value number if it exists in the hash table.
2790 Return NULL_TREE if it does not exist in the hash table or if the
2791 result field of the operation is NULL. VNRESULT will contain the
2792 vn_nary_op_t from the hashtable if it exists. */
2794 static tree
2795 vn_nary_op_lookup_1 (vn_nary_op_t vno, vn_nary_op_t *vnresult)
2797 vn_nary_op_s **slot;
2799 if (vnresult)
2800 *vnresult = NULL;
2802 vno->hashcode = vn_nary_op_compute_hash (vno);
2803 slot = current_info->nary->find_slot_with_hash (vno, vno->hashcode,
2804 NO_INSERT);
2805 if (!slot && current_info == optimistic_info)
2806 slot = valid_info->nary->find_slot_with_hash (vno, vno->hashcode,
2807 NO_INSERT);
2808 if (!slot)
2809 return NULL_TREE;
2810 if (vnresult)
2811 *vnresult = *slot;
2812 return (*slot)->result;
2815 /* Lookup a n-ary operation by its pieces and return the resulting value
2816 number if it exists in the hash table. Return NULL_TREE if it does
2817 not exist in the hash table or if the result field of the operation
2818 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2819 if it exists. */
2821 tree
2822 vn_nary_op_lookup_pieces (unsigned int length, enum tree_code code,
2823 tree type, tree *ops, vn_nary_op_t *vnresult)
2825 vn_nary_op_t vno1 = XALLOCAVAR (struct vn_nary_op_s,
2826 sizeof_vn_nary_op (length));
2827 init_vn_nary_op_from_pieces (vno1, length, code, type, ops);
2828 return vn_nary_op_lookup_1 (vno1, vnresult);
2831 /* Lookup OP in the current hash table, and return the resulting value
2832 number if it exists in the hash table. Return NULL_TREE if it does
2833 not exist in the hash table or if the result field of the operation
2834 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
2835 if it exists. */
2837 tree
2838 vn_nary_op_lookup (tree op, vn_nary_op_t *vnresult)
2840 vn_nary_op_t vno1
2841 = XALLOCAVAR (struct vn_nary_op_s,
2842 sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op))));
2843 init_vn_nary_op_from_op (vno1, op);
2844 return vn_nary_op_lookup_1 (vno1, vnresult);
2847 /* Lookup the rhs of STMT in the current hash table, and return the resulting
2848 value number if it exists in the hash table. Return NULL_TREE if
2849 it does not exist in the hash table. VNRESULT will contain the
2850 vn_nary_op_t from the hashtable if it exists. */
2852 tree
2853 vn_nary_op_lookup_stmt (gimple *stmt, vn_nary_op_t *vnresult)
2855 vn_nary_op_t vno1
2856 = XALLOCAVAR (struct vn_nary_op_s,
2857 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt)));
2858 init_vn_nary_op_from_stmt (vno1, stmt);
2859 return vn_nary_op_lookup_1 (vno1, vnresult);
2862 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
2864 static vn_nary_op_t
2865 alloc_vn_nary_op_noinit (unsigned int length, struct obstack *stack)
2867 return (vn_nary_op_t) obstack_alloc (stack, sizeof_vn_nary_op (length));
2870 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
2871 obstack. */
2873 static vn_nary_op_t
2874 alloc_vn_nary_op (unsigned int length, tree result, unsigned int value_id)
2876 vn_nary_op_t vno1 = alloc_vn_nary_op_noinit (length,
2877 &current_info->nary_obstack);
2879 vno1->value_id = value_id;
2880 vno1->length = length;
2881 vno1->result = result;
2883 return vno1;
2886 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
2887 VNO->HASHCODE first. */
2889 static vn_nary_op_t
2890 vn_nary_op_insert_into (vn_nary_op_t vno, vn_nary_op_table_type *table,
2891 bool compute_hash)
2893 vn_nary_op_s **slot;
2895 if (compute_hash)
2896 vno->hashcode = vn_nary_op_compute_hash (vno);
2898 slot = table->find_slot_with_hash (vno, vno->hashcode, INSERT);
2899 /* While we do not want to insert things twice it's awkward to
2900 avoid it in the case where visit_nary_op pattern-matches stuff
2901 and ends up simplifying the replacement to itself. We then
2902 get two inserts, one from visit_nary_op and one from
2903 vn_nary_build_or_lookup.
2904 So allow inserts with the same value number. */
2905 if (*slot && (*slot)->result == vno->result)
2906 return *slot;
2908 gcc_assert (!*slot);
2910 *slot = vno;
2911 return vno;
2914 /* Insert a n-ary operation into the current hash table using it's
2915 pieces. Return the vn_nary_op_t structure we created and put in
2916 the hashtable. */
2918 vn_nary_op_t
2919 vn_nary_op_insert_pieces (unsigned int length, enum tree_code code,
2920 tree type, tree *ops,
2921 tree result, unsigned int value_id)
2923 vn_nary_op_t vno1 = alloc_vn_nary_op (length, result, value_id);
2924 init_vn_nary_op_from_pieces (vno1, length, code, type, ops);
2925 return vn_nary_op_insert_into (vno1, current_info->nary, true);
2928 /* Insert OP into the current hash table with a value number of
2929 RESULT. Return the vn_nary_op_t structure we created and put in
2930 the hashtable. */
2932 vn_nary_op_t
2933 vn_nary_op_insert (tree op, tree result)
2935 unsigned length = TREE_CODE_LENGTH (TREE_CODE (op));
2936 vn_nary_op_t vno1;
2938 vno1 = alloc_vn_nary_op (length, result, VN_INFO (result)->value_id);
2939 init_vn_nary_op_from_op (vno1, op);
2940 return vn_nary_op_insert_into (vno1, current_info->nary, true);
2943 /* Insert the rhs of STMT into the current hash table with a value number of
2944 RESULT. */
2946 static vn_nary_op_t
2947 vn_nary_op_insert_stmt (gimple *stmt, tree result)
2949 vn_nary_op_t vno1
2950 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt),
2951 result, VN_INFO (result)->value_id);
2952 init_vn_nary_op_from_stmt (vno1, stmt);
2953 return vn_nary_op_insert_into (vno1, current_info->nary, true);
2956 /* Compute a hashcode for PHI operation VP1 and return it. */
2958 static inline hashval_t
2959 vn_phi_compute_hash (vn_phi_t vp1)
2961 inchash::hash hstate (vp1->phiargs.length () > 2
2962 ? vp1->block->index : vp1->phiargs.length ());
2963 tree phi1op;
2964 tree type;
2965 edge e;
2966 edge_iterator ei;
2968 /* If all PHI arguments are constants we need to distinguish
2969 the PHI node via its type. */
2970 type = vp1->type;
2971 hstate.merge_hash (vn_hash_type (type));
2973 FOR_EACH_EDGE (e, ei, vp1->block->preds)
2975 /* Don't hash backedge values they need to be handled as VN_TOP
2976 for optimistic value-numbering. */
2977 if (e->flags & EDGE_DFS_BACK)
2978 continue;
2980 phi1op = vp1->phiargs[e->dest_idx];
2981 if (phi1op == VN_TOP)
2982 continue;
2983 inchash::add_expr (phi1op, hstate);
2986 return hstate.end ();
2990 /* Return true if COND1 and COND2 represent the same condition, set
2991 *INVERTED_P if one needs to be inverted to make it the same as
2992 the other. */
2994 static bool
2995 cond_stmts_equal_p (gcond *cond1, tree lhs1, tree rhs1,
2996 gcond *cond2, tree lhs2, tree rhs2, bool *inverted_p)
2998 enum tree_code code1 = gimple_cond_code (cond1);
2999 enum tree_code code2 = gimple_cond_code (cond2);
3001 *inverted_p = false;
3002 if (code1 == code2)
3004 else if (code1 == swap_tree_comparison (code2))
3005 std::swap (lhs2, rhs2);
3006 else if (code1 == invert_tree_comparison (code2, HONOR_NANS (lhs2)))
3007 *inverted_p = true;
3008 else if (code1 == invert_tree_comparison
3009 (swap_tree_comparison (code2), HONOR_NANS (lhs2)))
3011 std::swap (lhs2, rhs2);
3012 *inverted_p = true;
3014 else
3015 return false;
3017 return ((expressions_equal_p (lhs1, lhs2)
3018 && expressions_equal_p (rhs1, rhs2))
3019 || (commutative_tree_code (code1)
3020 && expressions_equal_p (lhs1, rhs2)
3021 && expressions_equal_p (rhs1, lhs2)));
3024 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
3026 static int
3027 vn_phi_eq (const_vn_phi_t const vp1, const_vn_phi_t const vp2)
3029 if (vp1->hashcode != vp2->hashcode)
3030 return false;
3032 if (vp1->block != vp2->block)
3034 if (vp1->phiargs.length () != vp2->phiargs.length ())
3035 return false;
3037 switch (vp1->phiargs.length ())
3039 case 1:
3040 /* Single-arg PHIs are just copies. */
3041 break;
3043 case 2:
3045 /* Rule out backedges into the PHI. */
3046 if (vp1->block->loop_father->header == vp1->block
3047 || vp2->block->loop_father->header == vp2->block)
3048 return false;
3050 /* If the PHI nodes do not have compatible types
3051 they are not the same. */
3052 if (!types_compatible_p (vp1->type, vp2->type))
3053 return false;
3055 basic_block idom1
3056 = get_immediate_dominator (CDI_DOMINATORS, vp1->block);
3057 basic_block idom2
3058 = get_immediate_dominator (CDI_DOMINATORS, vp2->block);
3059 /* If the immediate dominator end in switch stmts multiple
3060 values may end up in the same PHI arg via intermediate
3061 CFG merges. */
3062 if (EDGE_COUNT (idom1->succs) != 2
3063 || EDGE_COUNT (idom2->succs) != 2)
3064 return false;
3066 /* Verify the controlling stmt is the same. */
3067 gcond *last1 = safe_dyn_cast <gcond *> (last_stmt (idom1));
3068 gcond *last2 = safe_dyn_cast <gcond *> (last_stmt (idom2));
3069 if (! last1 || ! last2)
3070 return false;
3071 bool inverted_p;
3072 if (! cond_stmts_equal_p (last1, vp1->cclhs, vp1->ccrhs,
3073 last2, vp2->cclhs, vp2->ccrhs,
3074 &inverted_p))
3075 return false;
3077 /* Get at true/false controlled edges into the PHI. */
3078 edge te1, te2, fe1, fe2;
3079 if (! extract_true_false_controlled_edges (idom1, vp1->block,
3080 &te1, &fe1)
3081 || ! extract_true_false_controlled_edges (idom2, vp2->block,
3082 &te2, &fe2))
3083 return false;
3085 /* Swap edges if the second condition is the inverted of the
3086 first. */
3087 if (inverted_p)
3088 std::swap (te2, fe2);
3090 /* ??? Handle VN_TOP specially. */
3091 if (! expressions_equal_p (vp1->phiargs[te1->dest_idx],
3092 vp2->phiargs[te2->dest_idx])
3093 || ! expressions_equal_p (vp1->phiargs[fe1->dest_idx],
3094 vp2->phiargs[fe2->dest_idx]))
3095 return false;
3097 return true;
3100 default:
3101 return false;
3105 /* If the PHI nodes do not have compatible types
3106 they are not the same. */
3107 if (!types_compatible_p (vp1->type, vp2->type))
3108 return false;
3110 /* Any phi in the same block will have it's arguments in the
3111 same edge order, because of how we store phi nodes. */
3112 int i;
3113 tree phi1op;
3114 FOR_EACH_VEC_ELT (vp1->phiargs, i, phi1op)
3116 tree phi2op = vp2->phiargs[i];
3117 if (phi1op == VN_TOP || phi2op == VN_TOP)
3118 continue;
3119 if (!expressions_equal_p (phi1op, phi2op))
3120 return false;
3123 return true;
3126 static vec<tree> shared_lookup_phiargs;
3128 /* Lookup PHI in the current hash table, and return the resulting
3129 value number if it exists in the hash table. Return NULL_TREE if
3130 it does not exist in the hash table. */
3132 static tree
3133 vn_phi_lookup (gimple *phi)
3135 vn_phi_s **slot;
3136 struct vn_phi_s vp1;
3137 edge e;
3138 edge_iterator ei;
3140 shared_lookup_phiargs.truncate (0);
3141 shared_lookup_phiargs.safe_grow (gimple_phi_num_args (phi));
3143 /* Canonicalize the SSA_NAME's to their value number. */
3144 FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds)
3146 tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
3147 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
3148 shared_lookup_phiargs[e->dest_idx] = def;
3150 vp1.type = TREE_TYPE (gimple_phi_result (phi));
3151 vp1.phiargs = shared_lookup_phiargs;
3152 vp1.block = gimple_bb (phi);
3153 /* Extract values of the controlling condition. */
3154 vp1.cclhs = NULL_TREE;
3155 vp1.ccrhs = NULL_TREE;
3156 basic_block idom1 = get_immediate_dominator (CDI_DOMINATORS, vp1.block);
3157 if (EDGE_COUNT (idom1->succs) == 2)
3158 if (gcond *last1 = safe_dyn_cast <gcond *> (last_stmt (idom1)))
3160 vp1.cclhs = vn_valueize (gimple_cond_lhs (last1));
3161 vp1.ccrhs = vn_valueize (gimple_cond_rhs (last1));
3163 vp1.hashcode = vn_phi_compute_hash (&vp1);
3164 slot = current_info->phis->find_slot_with_hash (&vp1, vp1.hashcode,
3165 NO_INSERT);
3166 if (!slot && current_info == optimistic_info)
3167 slot = valid_info->phis->find_slot_with_hash (&vp1, vp1.hashcode,
3168 NO_INSERT);
3169 if (!slot)
3170 return NULL_TREE;
3171 return (*slot)->result;
3174 /* Insert PHI into the current hash table with a value number of
3175 RESULT. */
3177 static vn_phi_t
3178 vn_phi_insert (gimple *phi, tree result)
3180 vn_phi_s **slot;
3181 vn_phi_t vp1 = current_info->phis_pool->allocate ();
3182 vec<tree> args = vNULL;
3183 edge e;
3184 edge_iterator ei;
3186 args.safe_grow (gimple_phi_num_args (phi));
3188 /* Canonicalize the SSA_NAME's to their value number. */
3189 FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds)
3191 tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
3192 def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
3193 args[e->dest_idx] = def;
3195 vp1->value_id = VN_INFO (result)->value_id;
3196 vp1->type = TREE_TYPE (gimple_phi_result (phi));
3197 vp1->phiargs = args;
3198 vp1->block = gimple_bb (phi);
3199 /* Extract values of the controlling condition. */
3200 vp1->cclhs = NULL_TREE;
3201 vp1->ccrhs = NULL_TREE;
3202 basic_block idom1 = get_immediate_dominator (CDI_DOMINATORS, vp1->block);
3203 if (EDGE_COUNT (idom1->succs) == 2)
3204 if (gcond *last1 = safe_dyn_cast <gcond *> (last_stmt (idom1)))
3206 vp1->cclhs = vn_valueize (gimple_cond_lhs (last1));
3207 vp1->ccrhs = vn_valueize (gimple_cond_rhs (last1));
3209 vp1->result = result;
3210 vp1->hashcode = vn_phi_compute_hash (vp1);
3212 slot = current_info->phis->find_slot_with_hash (vp1, vp1->hashcode, INSERT);
3214 /* Because we iterate over phi operations more than once, it's
3215 possible the slot might already exist here, hence no assert.*/
3216 *slot = vp1;
3217 return vp1;
3221 /* Print set of components in strongly connected component SCC to OUT. */
3223 static void
3224 print_scc (FILE *out, vec<tree> scc)
3226 tree var;
3227 unsigned int i;
3229 fprintf (out, "SCC consists of %u:", scc.length ());
3230 FOR_EACH_VEC_ELT (scc, i, var)
3232 fprintf (out, " ");
3233 print_generic_expr (out, var);
3235 fprintf (out, "\n");
3238 /* Return true if BB1 is dominated by BB2 taking into account edges
3239 that are not executable. */
3241 static bool
3242 dominated_by_p_w_unex (basic_block bb1, basic_block bb2)
3244 edge_iterator ei;
3245 edge e;
3247 if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
3248 return true;
3250 /* Before iterating we'd like to know if there exists a
3251 (executable) path from bb2 to bb1 at all, if not we can
3252 directly return false. For now simply iterate once. */
3254 /* Iterate to the single executable bb1 predecessor. */
3255 if (EDGE_COUNT (bb1->preds) > 1)
3257 edge prede = NULL;
3258 FOR_EACH_EDGE (e, ei, bb1->preds)
3259 if (e->flags & EDGE_EXECUTABLE)
3261 if (prede)
3263 prede = NULL;
3264 break;
3266 prede = e;
3268 if (prede)
3270 bb1 = prede->src;
3272 /* Re-do the dominance check with changed bb1. */
3273 if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
3274 return true;
3278 /* Iterate to the single executable bb2 successor. */
3279 edge succe = NULL;
3280 FOR_EACH_EDGE (e, ei, bb2->succs)
3281 if (e->flags & EDGE_EXECUTABLE)
3283 if (succe)
3285 succe = NULL;
3286 break;
3288 succe = e;
3290 if (succe)
3292 /* Verify the reached block is only reached through succe.
3293 If there is only one edge we can spare us the dominator
3294 check and iterate directly. */
3295 if (EDGE_COUNT (succe->dest->preds) > 1)
3297 FOR_EACH_EDGE (e, ei, succe->dest->preds)
3298 if (e != succe
3299 && (e->flags & EDGE_EXECUTABLE))
3301 succe = NULL;
3302 break;
3305 if (succe)
3307 bb2 = succe->dest;
3309 /* Re-do the dominance check with changed bb2. */
3310 if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
3311 return true;
3315 /* We could now iterate updating bb1 / bb2. */
3316 return false;
3319 /* Set the value number of FROM to TO, return true if it has changed
3320 as a result. */
3322 static inline bool
3323 set_ssa_val_to (tree from, tree to)
3325 tree currval = SSA_VAL (from);
3326 poly_int64 toff, coff;
3328 /* The only thing we allow as value numbers are ssa_names
3329 and invariants. So assert that here. We don't allow VN_TOP
3330 as visiting a stmt should produce a value-number other than
3331 that.
3332 ??? Still VN_TOP can happen for unreachable code, so force
3333 it to varying in that case. Not all code is prepared to
3334 get VN_TOP on valueization. */
3335 if (to == VN_TOP)
3337 if (dump_file && (dump_flags & TDF_DETAILS))
3338 fprintf (dump_file, "Forcing value number to varying on "
3339 "receiving VN_TOP\n");
3340 to = from;
3343 gcc_assert (to != NULL_TREE
3344 && ((TREE_CODE (to) == SSA_NAME
3345 && (to == from || SSA_VAL (to) == to))
3346 || is_gimple_min_invariant (to)));
3348 if (from != to)
3350 if (currval == from)
3352 if (dump_file && (dump_flags & TDF_DETAILS))
3354 fprintf (dump_file, "Not changing value number of ");
3355 print_generic_expr (dump_file, from);
3356 fprintf (dump_file, " from VARYING to ");
3357 print_generic_expr (dump_file, to);
3358 fprintf (dump_file, "\n");
3360 return false;
3362 else if (currval != VN_TOP
3363 && ! is_gimple_min_invariant (currval)
3364 && is_gimple_min_invariant (to))
3366 if (dump_file && (dump_flags & TDF_DETAILS))
3368 fprintf (dump_file, "Forcing VARYING instead of changing "
3369 "value number of ");
3370 print_generic_expr (dump_file, from);
3371 fprintf (dump_file, " from ");
3372 print_generic_expr (dump_file, currval);
3373 fprintf (dump_file, " (non-constant) to ");
3374 print_generic_expr (dump_file, to);
3375 fprintf (dump_file, " (constant)\n");
3377 to = from;
3379 else if (TREE_CODE (to) == SSA_NAME
3380 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to))
3381 to = from;
3384 if (dump_file && (dump_flags & TDF_DETAILS))
3386 fprintf (dump_file, "Setting value number of ");
3387 print_generic_expr (dump_file, from);
3388 fprintf (dump_file, " to ");
3389 print_generic_expr (dump_file, to);
3392 if (currval != to
3393 && !operand_equal_p (currval, to, 0)
3394 /* Different undefined SSA names are not actually different. See
3395 PR82320 for a testcase were we'd otherwise not terminate iteration. */
3396 && !(TREE_CODE (currval) == SSA_NAME
3397 && TREE_CODE (to) == SSA_NAME
3398 && ssa_undefined_value_p (currval, false)
3399 && ssa_undefined_value_p (to, false))
3400 /* ??? For addresses involving volatile objects or types operand_equal_p
3401 does not reliably detect ADDR_EXPRs as equal. We know we are only
3402 getting invariant gimple addresses here, so can use
3403 get_addr_base_and_unit_offset to do this comparison. */
3404 && !(TREE_CODE (currval) == ADDR_EXPR
3405 && TREE_CODE (to) == ADDR_EXPR
3406 && (get_addr_base_and_unit_offset (TREE_OPERAND (currval, 0), &coff)
3407 == get_addr_base_and_unit_offset (TREE_OPERAND (to, 0), &toff))
3408 && known_eq (coff, toff)))
3410 if (dump_file && (dump_flags & TDF_DETAILS))
3411 fprintf (dump_file, " (changed)\n");
3413 /* If we equate two SSA names we have to make the side-band info
3414 of the leader conservative (and remember whatever original value
3415 was present). */
3416 if (TREE_CODE (to) == SSA_NAME)
3418 if (INTEGRAL_TYPE_P (TREE_TYPE (to))
3419 && SSA_NAME_RANGE_INFO (to))
3421 if (SSA_NAME_IS_DEFAULT_DEF (to)
3422 || dominated_by_p_w_unex
3423 (gimple_bb (SSA_NAME_DEF_STMT (from)),
3424 gimple_bb (SSA_NAME_DEF_STMT (to))))
3425 /* Keep the info from the dominator. */
3427 else
3429 /* Save old info. */
3430 if (! VN_INFO (to)->info.range_info)
3432 VN_INFO (to)->info.range_info = SSA_NAME_RANGE_INFO (to);
3433 VN_INFO (to)->range_info_anti_range_p
3434 = SSA_NAME_ANTI_RANGE_P (to);
3436 /* Rather than allocating memory and unioning the info
3437 just clear it. */
3438 if (dump_file && (dump_flags & TDF_DETAILS))
3440 fprintf (dump_file, "clearing range info of ");
3441 print_generic_expr (dump_file, to);
3442 fprintf (dump_file, "\n");
3444 SSA_NAME_RANGE_INFO (to) = NULL;
3447 else if (POINTER_TYPE_P (TREE_TYPE (to))
3448 && SSA_NAME_PTR_INFO (to))
3450 if (SSA_NAME_IS_DEFAULT_DEF (to)
3451 || dominated_by_p_w_unex
3452 (gimple_bb (SSA_NAME_DEF_STMT (from)),
3453 gimple_bb (SSA_NAME_DEF_STMT (to))))
3454 /* Keep the info from the dominator. */
3456 else if (! SSA_NAME_PTR_INFO (from)
3457 /* Handle the case of trivially equivalent info. */
3458 || memcmp (SSA_NAME_PTR_INFO (to),
3459 SSA_NAME_PTR_INFO (from),
3460 sizeof (ptr_info_def)) != 0)
3462 /* Save old info. */
3463 if (! VN_INFO (to)->info.ptr_info)
3464 VN_INFO (to)->info.ptr_info = SSA_NAME_PTR_INFO (to);
3465 /* Rather than allocating memory and unioning the info
3466 just clear it. */
3467 if (dump_file && (dump_flags & TDF_DETAILS))
3469 fprintf (dump_file, "clearing points-to info of ");
3470 print_generic_expr (dump_file, to);
3471 fprintf (dump_file, "\n");
3473 SSA_NAME_PTR_INFO (to) = NULL;
3478 VN_INFO (from)->valnum = to;
3479 return true;
3481 if (dump_file && (dump_flags & TDF_DETAILS))
3482 fprintf (dump_file, "\n");
3483 return false;
3486 /* Mark as processed all the definitions in the defining stmt of USE, or
3487 the USE itself. */
3489 static void
3490 mark_use_processed (tree use)
3492 ssa_op_iter iter;
3493 def_operand_p defp;
3494 gimple *stmt = SSA_NAME_DEF_STMT (use);
3496 if (SSA_NAME_IS_DEFAULT_DEF (use) || gimple_code (stmt) == GIMPLE_PHI)
3498 VN_INFO (use)->use_processed = true;
3499 return;
3502 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
3504 tree def = DEF_FROM_PTR (defp);
3506 VN_INFO (def)->use_processed = true;
3510 /* Set all definitions in STMT to value number to themselves.
3511 Return true if a value number changed. */
3513 static bool
3514 defs_to_varying (gimple *stmt)
3516 bool changed = false;
3517 ssa_op_iter iter;
3518 def_operand_p defp;
3520 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
3522 tree def = DEF_FROM_PTR (defp);
3523 changed |= set_ssa_val_to (def, def);
3525 return changed;
3528 /* Visit a copy between LHS and RHS, return true if the value number
3529 changed. */
3531 static bool
3532 visit_copy (tree lhs, tree rhs)
3534 /* Valueize. */
3535 rhs = SSA_VAL (rhs);
3537 return set_ssa_val_to (lhs, rhs);
3540 /* Lookup a value for OP in type WIDE_TYPE where the value in type of OP
3541 is the same. */
3543 static tree
3544 valueized_wider_op (tree wide_type, tree op)
3546 if (TREE_CODE (op) == SSA_NAME)
3547 op = SSA_VAL (op);
3549 /* Either we have the op widened available. */
3550 tree ops[3] = {};
3551 ops[0] = op;
3552 tree tem = vn_nary_op_lookup_pieces (1, NOP_EXPR,
3553 wide_type, ops, NULL);
3554 if (tem)
3555 return tem;
3557 /* Or the op is truncated from some existing value. */
3558 if (TREE_CODE (op) == SSA_NAME)
3560 gimple *def = SSA_NAME_DEF_STMT (op);
3561 if (is_gimple_assign (def)
3562 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
3564 tem = gimple_assign_rhs1 (def);
3565 if (useless_type_conversion_p (wide_type, TREE_TYPE (tem)))
3567 if (TREE_CODE (tem) == SSA_NAME)
3568 tem = SSA_VAL (tem);
3569 return tem;
3574 /* For constants simply extend it. */
3575 if (TREE_CODE (op) == INTEGER_CST)
3576 return wide_int_to_tree (wide_type, wi::to_wide (op));
3578 return NULL_TREE;
3581 /* Visit a nary operator RHS, value number it, and return true if the
3582 value number of LHS has changed as a result. */
3584 static bool
3585 visit_nary_op (tree lhs, gassign *stmt)
3587 tree result = vn_nary_op_lookup_stmt (stmt, NULL);
3588 if (result)
3589 return set_ssa_val_to (lhs, result);
3591 /* Do some special pattern matching for redundancies of operations
3592 in different types. */
3593 enum tree_code code = gimple_assign_rhs_code (stmt);
3594 tree type = TREE_TYPE (lhs);
3595 tree rhs1 = gimple_assign_rhs1 (stmt);
3596 switch (code)
3598 CASE_CONVERT:
3599 /* Match arithmetic done in a different type where we can easily
3600 substitute the result from some earlier sign-changed or widened
3601 operation. */
3602 if (INTEGRAL_TYPE_P (type)
3603 && TREE_CODE (rhs1) == SSA_NAME
3604 /* We only handle sign-changes or zero-extension -> & mask. */
3605 && ((TYPE_UNSIGNED (TREE_TYPE (rhs1))
3606 && TYPE_PRECISION (type) > TYPE_PRECISION (TREE_TYPE (rhs1)))
3607 || TYPE_PRECISION (type) == TYPE_PRECISION (TREE_TYPE (rhs1))))
3609 gassign *def = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (rhs1));
3610 if (def
3611 && (gimple_assign_rhs_code (def) == PLUS_EXPR
3612 || gimple_assign_rhs_code (def) == MINUS_EXPR
3613 || gimple_assign_rhs_code (def) == MULT_EXPR))
3615 tree ops[3] = {};
3616 /* Either we have the op widened available. */
3617 ops[0] = valueized_wider_op (type,
3618 gimple_assign_rhs1 (def));
3619 if (ops[0])
3620 ops[1] = valueized_wider_op (type,
3621 gimple_assign_rhs2 (def));
3622 if (ops[0] && ops[1])
3624 ops[0] = vn_nary_op_lookup_pieces
3625 (2, gimple_assign_rhs_code (def), type, ops, NULL);
3626 /* We have wider operation available. */
3627 if (ops[0])
3629 unsigned lhs_prec = TYPE_PRECISION (type);
3630 unsigned rhs_prec = TYPE_PRECISION (TREE_TYPE (rhs1));
3631 if (lhs_prec == rhs_prec)
3633 ops[1] = NULL_TREE;
3634 result = vn_nary_build_or_lookup (NOP_EXPR,
3635 type, ops);
3636 if (result)
3638 bool changed = set_ssa_val_to (lhs, result);
3639 vn_nary_op_insert_stmt (stmt, result);
3640 return changed;
3643 else
3645 ops[1] = wide_int_to_tree (type,
3646 wi::mask (rhs_prec, false,
3647 lhs_prec));
3648 result = vn_nary_build_or_lookup (BIT_AND_EXPR,
3649 TREE_TYPE (lhs),
3650 ops);
3651 if (result)
3653 bool changed = set_ssa_val_to (lhs, result);
3654 vn_nary_op_insert_stmt (stmt, result);
3655 return changed;
3662 default:;
3665 bool changed = set_ssa_val_to (lhs, lhs);
3666 vn_nary_op_insert_stmt (stmt, lhs);
3667 return changed;
3670 /* Visit a call STMT storing into LHS. Return true if the value number
3671 of the LHS has changed as a result. */
3673 static bool
3674 visit_reference_op_call (tree lhs, gcall *stmt)
3676 bool changed = false;
3677 struct vn_reference_s vr1;
3678 vn_reference_t vnresult = NULL;
3679 tree vdef = gimple_vdef (stmt);
3681 /* Non-ssa lhs is handled in copy_reference_ops_from_call. */
3682 if (lhs && TREE_CODE (lhs) != SSA_NAME)
3683 lhs = NULL_TREE;
3685 vn_reference_lookup_call (stmt, &vnresult, &vr1);
3686 if (vnresult)
3688 if (vnresult->result_vdef && vdef)
3689 changed |= set_ssa_val_to (vdef, vnresult->result_vdef);
3690 else if (vdef)
3691 /* If the call was discovered to be pure or const reflect
3692 that as far as possible. */
3693 changed |= set_ssa_val_to (vdef, vuse_ssa_val (gimple_vuse (stmt)));
3695 if (!vnresult->result && lhs)
3696 vnresult->result = lhs;
3698 if (vnresult->result && lhs)
3699 changed |= set_ssa_val_to (lhs, vnresult->result);
3701 else
3703 vn_reference_t vr2;
3704 vn_reference_s **slot;
3705 tree vdef_val = vdef;
3706 if (vdef)
3708 /* If we value numbered an indirect functions function to
3709 one not clobbering memory value number its VDEF to its
3710 VUSE. */
3711 tree fn = gimple_call_fn (stmt);
3712 if (fn && TREE_CODE (fn) == SSA_NAME)
3714 fn = SSA_VAL (fn);
3715 if (TREE_CODE (fn) == ADDR_EXPR
3716 && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL
3717 && (flags_from_decl_or_type (TREE_OPERAND (fn, 0))
3718 & (ECF_CONST | ECF_PURE)))
3719 vdef_val = vuse_ssa_val (gimple_vuse (stmt));
3721 changed |= set_ssa_val_to (vdef, vdef_val);
3723 if (lhs)
3724 changed |= set_ssa_val_to (lhs, lhs);
3725 vr2 = current_info->references_pool->allocate ();
3726 vr2->vuse = vr1.vuse;
3727 /* As we are not walking the virtual operand chain we know the
3728 shared_lookup_references are still original so we can re-use
3729 them here. */
3730 vr2->operands = vr1.operands.copy ();
3731 vr2->type = vr1.type;
3732 vr2->set = vr1.set;
3733 vr2->hashcode = vr1.hashcode;
3734 vr2->result = lhs;
3735 vr2->result_vdef = vdef_val;
3736 slot = current_info->references->find_slot_with_hash (vr2, vr2->hashcode,
3737 INSERT);
3738 gcc_assert (!*slot);
3739 *slot = vr2;
3742 return changed;
3745 /* Visit a load from a reference operator RHS, part of STMT, value number it,
3746 and return true if the value number of the LHS has changed as a result. */
3748 static bool
3749 visit_reference_op_load (tree lhs, tree op, gimple *stmt)
3751 bool changed = false;
3752 tree last_vuse;
3753 tree result;
3755 last_vuse = gimple_vuse (stmt);
3756 last_vuse_ptr = &last_vuse;
3757 result = vn_reference_lookup (op, gimple_vuse (stmt),
3758 default_vn_walk_kind, NULL, true);
3759 last_vuse_ptr = NULL;
3761 /* We handle type-punning through unions by value-numbering based
3762 on offset and size of the access. Be prepared to handle a
3763 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
3764 if (result
3765 && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (op)))
3767 /* We will be setting the value number of lhs to the value number
3768 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
3769 So first simplify and lookup this expression to see if it
3770 is already available. */
3771 code_helper rcode = VIEW_CONVERT_EXPR;
3772 tree ops[3] = { result };
3773 result = vn_nary_build_or_lookup (rcode, TREE_TYPE (op), ops);
3776 if (result)
3777 changed = set_ssa_val_to (lhs, result);
3778 else
3780 changed = set_ssa_val_to (lhs, lhs);
3781 vn_reference_insert (op, lhs, last_vuse, NULL_TREE);
3784 return changed;
3788 /* Visit a store to a reference operator LHS, part of STMT, value number it,
3789 and return true if the value number of the LHS has changed as a result. */
3791 static bool
3792 visit_reference_op_store (tree lhs, tree op, gimple *stmt)
3794 bool changed = false;
3795 vn_reference_t vnresult = NULL;
3796 tree assign;
3797 bool resultsame = false;
3798 tree vuse = gimple_vuse (stmt);
3799 tree vdef = gimple_vdef (stmt);
3801 if (TREE_CODE (op) == SSA_NAME)
3802 op = SSA_VAL (op);
3804 /* First we want to lookup using the *vuses* from the store and see
3805 if there the last store to this location with the same address
3806 had the same value.
3808 The vuses represent the memory state before the store. If the
3809 memory state, address, and value of the store is the same as the
3810 last store to this location, then this store will produce the
3811 same memory state as that store.
3813 In this case the vdef versions for this store are value numbered to those
3814 vuse versions, since they represent the same memory state after
3815 this store.
3817 Otherwise, the vdefs for the store are used when inserting into
3818 the table, since the store generates a new memory state. */
3820 vn_reference_lookup (lhs, vuse, VN_NOWALK, &vnresult, false);
3821 if (vnresult
3822 && vnresult->result)
3824 tree result = vnresult->result;
3825 if (TREE_CODE (result) == SSA_NAME)
3826 result = SSA_VAL (result);
3827 resultsame = expressions_equal_p (result, op);
3828 if (resultsame)
3830 /* If the TBAA state isn't compatible for downstream reads
3831 we cannot value-number the VDEFs the same. */
3832 alias_set_type set = get_alias_set (lhs);
3833 if (vnresult->set != set
3834 && ! alias_set_subset_of (set, vnresult->set))
3835 resultsame = false;
3839 if (!resultsame)
3841 /* Only perform the following when being called from PRE
3842 which embeds tail merging. */
3843 if (default_vn_walk_kind == VN_WALK)
3845 assign = build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, op);
3846 vn_reference_lookup (assign, vuse, VN_NOWALK, &vnresult, false);
3847 if (vnresult)
3849 VN_INFO (vdef)->use_processed = true;
3850 return set_ssa_val_to (vdef, vnresult->result_vdef);
3854 if (dump_file && (dump_flags & TDF_DETAILS))
3856 fprintf (dump_file, "No store match\n");
3857 fprintf (dump_file, "Value numbering store ");
3858 print_generic_expr (dump_file, lhs);
3859 fprintf (dump_file, " to ");
3860 print_generic_expr (dump_file, op);
3861 fprintf (dump_file, "\n");
3863 /* Have to set value numbers before insert, since insert is
3864 going to valueize the references in-place. */
3865 if (vdef)
3866 changed |= set_ssa_val_to (vdef, vdef);
3868 /* Do not insert structure copies into the tables. */
3869 if (is_gimple_min_invariant (op)
3870 || is_gimple_reg (op))
3871 vn_reference_insert (lhs, op, vdef, NULL);
3873 /* Only perform the following when being called from PRE
3874 which embeds tail merging. */
3875 if (default_vn_walk_kind == VN_WALK)
3877 assign = build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, op);
3878 vn_reference_insert (assign, lhs, vuse, vdef);
3881 else
3883 /* We had a match, so value number the vdef to have the value
3884 number of the vuse it came from. */
3886 if (dump_file && (dump_flags & TDF_DETAILS))
3887 fprintf (dump_file, "Store matched earlier value, "
3888 "value numbering store vdefs to matching vuses.\n");
3890 changed |= set_ssa_val_to (vdef, SSA_VAL (vuse));
3893 return changed;
3896 /* Visit and value number PHI, return true if the value number
3897 changed. */
3899 static bool
3900 visit_phi (gimple *phi)
3902 tree result, sameval = VN_TOP, seen_undef = NULL_TREE;
3903 unsigned n_executable = 0;
3904 bool allsame = true;
3905 edge_iterator ei;
3906 edge e;
3908 /* TODO: We could check for this in init_sccvn, and replace this
3909 with a gcc_assert. */
3910 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
3911 return set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
3913 /* See if all non-TOP arguments have the same value. TOP is
3914 equivalent to everything, so we can ignore it. */
3915 FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds)
3916 if (e->flags & EDGE_EXECUTABLE)
3918 tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
3920 ++n_executable;
3921 if (TREE_CODE (def) == SSA_NAME)
3922 def = SSA_VAL (def);
3923 if (def == VN_TOP)
3925 /* Ignore undefined defs for sameval but record one. */
3926 else if (TREE_CODE (def) == SSA_NAME
3927 && ssa_undefined_value_p (def, false))
3928 seen_undef = def;
3929 else if (sameval == VN_TOP)
3930 sameval = def;
3931 else if (!expressions_equal_p (def, sameval))
3933 allsame = false;
3934 break;
3939 /* If none of the edges was executable keep the value-number at VN_TOP,
3940 if only a single edge is exectuable use its value. */
3941 if (n_executable <= 1)
3942 result = seen_undef ? seen_undef : sameval;
3943 /* If we saw only undefined values and VN_TOP use one of the
3944 undefined values. */
3945 else if (sameval == VN_TOP)
3946 result = seen_undef ? seen_undef : sameval;
3947 /* First see if it is equivalent to a phi node in this block. We prefer
3948 this as it allows IV elimination - see PRs 66502 and 67167. */
3949 else if ((result = vn_phi_lookup (phi)))
3951 /* If all values are the same use that, unless we've seen undefined
3952 values as well and the value isn't constant.
3953 CCP/copyprop have the same restriction to not remove uninit warnings. */
3954 else if (allsame
3955 && (! seen_undef || is_gimple_min_invariant (sameval)))
3956 result = sameval;
3957 else
3959 result = PHI_RESULT (phi);
3960 /* Only insert PHIs that are varying, for constant value numbers
3961 we mess up equivalences otherwise as we are only comparing
3962 the immediate controlling predicates. */
3963 vn_phi_insert (phi, result);
3966 return set_ssa_val_to (PHI_RESULT (phi), result);
3969 /* Try to simplify RHS using equivalences and constant folding. */
3971 static tree
3972 try_to_simplify (gassign *stmt)
3974 enum tree_code code = gimple_assign_rhs_code (stmt);
3975 tree tem;
3977 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
3978 in this case, there is no point in doing extra work. */
3979 if (code == SSA_NAME)
3980 return NULL_TREE;
3982 /* First try constant folding based on our current lattice. */
3983 mprts_hook = vn_lookup_simplify_result;
3984 mprts_hook_cnt = 9;
3985 tem = gimple_fold_stmt_to_constant_1 (stmt, vn_valueize, vn_valueize);
3986 mprts_hook = NULL;
3987 if (tem
3988 && (TREE_CODE (tem) == SSA_NAME
3989 || is_gimple_min_invariant (tem)))
3990 return tem;
3992 return NULL_TREE;
3995 /* Visit and value number USE, return true if the value number
3996 changed. */
3998 static bool
3999 visit_use (tree use)
4001 bool changed = false;
4002 gimple *stmt = SSA_NAME_DEF_STMT (use);
4004 mark_use_processed (use);
4006 gcc_assert (!SSA_NAME_IN_FREE_LIST (use)
4007 && !SSA_NAME_IS_DEFAULT_DEF (use));
4009 if (dump_file && (dump_flags & TDF_DETAILS))
4011 fprintf (dump_file, "Value numbering ");
4012 print_generic_expr (dump_file, use);
4013 fprintf (dump_file, " stmt = ");
4014 print_gimple_stmt (dump_file, stmt, 0);
4017 if (gimple_code (stmt) == GIMPLE_PHI)
4018 changed = visit_phi (stmt);
4019 else if (gimple_has_volatile_ops (stmt))
4020 changed = defs_to_varying (stmt);
4021 else if (gassign *ass = dyn_cast <gassign *> (stmt))
4023 enum tree_code code = gimple_assign_rhs_code (ass);
4024 tree lhs = gimple_assign_lhs (ass);
4025 tree rhs1 = gimple_assign_rhs1 (ass);
4026 tree simplified;
4028 /* Shortcut for copies. Simplifying copies is pointless,
4029 since we copy the expression and value they represent. */
4030 if (code == SSA_NAME
4031 && TREE_CODE (lhs) == SSA_NAME)
4033 changed = visit_copy (lhs, rhs1);
4034 goto done;
4036 simplified = try_to_simplify (ass);
4037 if (simplified)
4039 if (dump_file && (dump_flags & TDF_DETAILS))
4041 fprintf (dump_file, "RHS ");
4042 print_gimple_expr (dump_file, ass, 0);
4043 fprintf (dump_file, " simplified to ");
4044 print_generic_expr (dump_file, simplified);
4045 fprintf (dump_file, "\n");
4048 /* Setting value numbers to constants will occasionally
4049 screw up phi congruence because constants are not
4050 uniquely associated with a single ssa name that can be
4051 looked up. */
4052 if (simplified
4053 && is_gimple_min_invariant (simplified)
4054 && TREE_CODE (lhs) == SSA_NAME)
4056 changed = set_ssa_val_to (lhs, simplified);
4057 goto done;
4059 else if (simplified
4060 && TREE_CODE (simplified) == SSA_NAME
4061 && TREE_CODE (lhs) == SSA_NAME)
4063 changed = visit_copy (lhs, simplified);
4064 goto done;
4067 if ((TREE_CODE (lhs) == SSA_NAME
4068 /* We can substitute SSA_NAMEs that are live over
4069 abnormal edges with their constant value. */
4070 && !(gimple_assign_copy_p (ass)
4071 && is_gimple_min_invariant (rhs1))
4072 && !(simplified
4073 && is_gimple_min_invariant (simplified))
4074 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
4075 /* Stores or copies from SSA_NAMEs that are live over
4076 abnormal edges are a problem. */
4077 || (code == SSA_NAME
4078 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1)))
4079 changed = defs_to_varying (ass);
4080 else if (REFERENCE_CLASS_P (lhs)
4081 || DECL_P (lhs))
4082 changed = visit_reference_op_store (lhs, rhs1, ass);
4083 else if (TREE_CODE (lhs) == SSA_NAME)
4085 if ((gimple_assign_copy_p (ass)
4086 && is_gimple_min_invariant (rhs1))
4087 || (simplified
4088 && is_gimple_min_invariant (simplified)))
4090 if (simplified)
4091 changed = set_ssa_val_to (lhs, simplified);
4092 else
4093 changed = set_ssa_val_to (lhs, rhs1);
4095 else
4097 /* Visit the original statement. */
4098 switch (vn_get_stmt_kind (ass))
4100 case VN_NARY:
4101 changed = visit_nary_op (lhs, ass);
4102 break;
4103 case VN_REFERENCE:
4104 changed = visit_reference_op_load (lhs, rhs1, ass);
4105 break;
4106 default:
4107 changed = defs_to_varying (ass);
4108 break;
4112 else
4113 changed = defs_to_varying (ass);
4115 else if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
4117 tree lhs = gimple_call_lhs (call_stmt);
4118 if (lhs && TREE_CODE (lhs) == SSA_NAME)
4120 /* Try constant folding based on our current lattice. */
4121 tree simplified = gimple_fold_stmt_to_constant_1 (call_stmt,
4122 vn_valueize);
4123 if (simplified)
4125 if (dump_file && (dump_flags & TDF_DETAILS))
4127 fprintf (dump_file, "call ");
4128 print_gimple_expr (dump_file, call_stmt, 0);
4129 fprintf (dump_file, " simplified to ");
4130 print_generic_expr (dump_file, simplified);
4131 fprintf (dump_file, "\n");
4134 /* Setting value numbers to constants will occasionally
4135 screw up phi congruence because constants are not
4136 uniquely associated with a single ssa name that can be
4137 looked up. */
4138 if (simplified
4139 && is_gimple_min_invariant (simplified))
4141 changed = set_ssa_val_to (lhs, simplified);
4142 if (gimple_vdef (call_stmt))
4143 changed |= set_ssa_val_to (gimple_vdef (call_stmt),
4144 SSA_VAL (gimple_vuse (call_stmt)));
4145 goto done;
4147 else if (simplified
4148 && TREE_CODE (simplified) == SSA_NAME)
4150 changed = visit_copy (lhs, simplified);
4151 if (gimple_vdef (call_stmt))
4152 changed |= set_ssa_val_to (gimple_vdef (call_stmt),
4153 SSA_VAL (gimple_vuse (call_stmt)));
4154 goto done;
4156 else if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
4158 changed = defs_to_varying (call_stmt);
4159 goto done;
4163 /* Pick up flags from a devirtualization target. */
4164 tree fn = gimple_call_fn (stmt);
4165 int extra_fnflags = 0;
4166 if (fn && TREE_CODE (fn) == SSA_NAME)
4168 fn = SSA_VAL (fn);
4169 if (TREE_CODE (fn) == ADDR_EXPR
4170 && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL)
4171 extra_fnflags = flags_from_decl_or_type (TREE_OPERAND (fn, 0));
4173 if (!gimple_call_internal_p (call_stmt)
4174 && (/* Calls to the same function with the same vuse
4175 and the same operands do not necessarily return the same
4176 value, unless they're pure or const. */
4177 ((gimple_call_flags (call_stmt) | extra_fnflags)
4178 & (ECF_PURE | ECF_CONST))
4179 /* If calls have a vdef, subsequent calls won't have
4180 the same incoming vuse. So, if 2 calls with vdef have the
4181 same vuse, we know they're not subsequent.
4182 We can value number 2 calls to the same function with the
4183 same vuse and the same operands which are not subsequent
4184 the same, because there is no code in the program that can
4185 compare the 2 values... */
4186 || (gimple_vdef (call_stmt)
4187 /* ... unless the call returns a pointer which does
4188 not alias with anything else. In which case the
4189 information that the values are distinct are encoded
4190 in the IL. */
4191 && !(gimple_call_return_flags (call_stmt) & ERF_NOALIAS)
4192 /* Only perform the following when being called from PRE
4193 which embeds tail merging. */
4194 && default_vn_walk_kind == VN_WALK)))
4195 changed = visit_reference_op_call (lhs, call_stmt);
4196 else
4197 changed = defs_to_varying (call_stmt);
4199 else
4200 changed = defs_to_varying (stmt);
4201 done:
4202 return changed;
4205 /* Compare two operands by reverse postorder index */
4207 static int
4208 compare_ops (const void *pa, const void *pb)
4210 const tree opa = *((const tree *)pa);
4211 const tree opb = *((const tree *)pb);
4212 gimple *opstmta = SSA_NAME_DEF_STMT (opa);
4213 gimple *opstmtb = SSA_NAME_DEF_STMT (opb);
4214 basic_block bba;
4215 basic_block bbb;
4217 if (gimple_nop_p (opstmta) && gimple_nop_p (opstmtb))
4218 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
4219 else if (gimple_nop_p (opstmta))
4220 return -1;
4221 else if (gimple_nop_p (opstmtb))
4222 return 1;
4224 bba = gimple_bb (opstmta);
4225 bbb = gimple_bb (opstmtb);
4227 if (!bba && !bbb)
4228 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
4229 else if (!bba)
4230 return -1;
4231 else if (!bbb)
4232 return 1;
4234 if (bba == bbb)
4236 if (gimple_code (opstmta) == GIMPLE_PHI
4237 && gimple_code (opstmtb) == GIMPLE_PHI)
4238 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
4239 else if (gimple_code (opstmta) == GIMPLE_PHI)
4240 return -1;
4241 else if (gimple_code (opstmtb) == GIMPLE_PHI)
4242 return 1;
4243 else if (gimple_uid (opstmta) != gimple_uid (opstmtb))
4244 return gimple_uid (opstmta) - gimple_uid (opstmtb);
4245 else
4246 return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
4248 return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
4251 /* Sort an array containing members of a strongly connected component
4252 SCC so that the members are ordered by RPO number.
4253 This means that when the sort is complete, iterating through the
4254 array will give you the members in RPO order. */
4256 static void
4257 sort_scc (vec<tree> scc)
4259 scc.qsort (compare_ops);
4262 /* Insert the no longer used nary ONARY to the hash INFO. */
4264 static void
4265 copy_nary (vn_nary_op_t onary, vn_tables_t info)
4267 size_t size = sizeof_vn_nary_op (onary->length);
4268 vn_nary_op_t nary = alloc_vn_nary_op_noinit (onary->length,
4269 &info->nary_obstack);
4270 memcpy (nary, onary, size);
4271 vn_nary_op_insert_into (nary, info->nary, false);
4274 /* Insert the no longer used phi OPHI to the hash INFO. */
4276 static void
4277 copy_phi (vn_phi_t ophi, vn_tables_t info)
4279 vn_phi_t phi = info->phis_pool->allocate ();
4280 vn_phi_s **slot;
4281 memcpy (phi, ophi, sizeof (*phi));
4282 ophi->phiargs.create (0);
4283 slot = info->phis->find_slot_with_hash (phi, phi->hashcode, INSERT);
4284 gcc_assert (!*slot);
4285 *slot = phi;
4288 /* Insert the no longer used reference OREF to the hash INFO. */
4290 static void
4291 copy_reference (vn_reference_t oref, vn_tables_t info)
4293 vn_reference_t ref;
4294 vn_reference_s **slot;
4295 ref = info->references_pool->allocate ();
4296 memcpy (ref, oref, sizeof (*ref));
4297 oref->operands.create (0);
4298 slot = info->references->find_slot_with_hash (ref, ref->hashcode, INSERT);
4299 if (*slot)
4300 free_reference (*slot);
4301 *slot = ref;
4304 /* Process a strongly connected component in the SSA graph. */
4306 static void
4307 process_scc (vec<tree> scc)
4309 tree var;
4310 unsigned int i;
4311 unsigned int iterations = 0;
4312 bool changed = true;
4313 vn_nary_op_iterator_type hin;
4314 vn_phi_iterator_type hip;
4315 vn_reference_iterator_type hir;
4316 vn_nary_op_t nary;
4317 vn_phi_t phi;
4318 vn_reference_t ref;
4320 /* If the SCC has a single member, just visit it. */
4321 if (scc.length () == 1)
4323 tree use = scc[0];
4324 if (VN_INFO (use)->use_processed)
4325 return;
4326 /* We need to make sure it doesn't form a cycle itself, which can
4327 happen for self-referential PHI nodes. In that case we would
4328 end up inserting an expression with VN_TOP operands into the
4329 valid table which makes us derive bogus equivalences later.
4330 The cheapest way to check this is to assume it for all PHI nodes. */
4331 if (gimple_code (SSA_NAME_DEF_STMT (use)) == GIMPLE_PHI)
4332 /* Fallthru to iteration. */ ;
4333 else
4335 visit_use (use);
4336 return;
4340 if (dump_file && (dump_flags & TDF_DETAILS))
4341 print_scc (dump_file, scc);
4343 /* Iterate over the SCC with the optimistic table until it stops
4344 changing. */
4345 current_info = optimistic_info;
4346 while (changed)
4348 changed = false;
4349 iterations++;
4350 if (dump_file && (dump_flags & TDF_DETAILS))
4351 fprintf (dump_file, "Starting iteration %d\n", iterations);
4352 /* As we are value-numbering optimistically we have to
4353 clear the expression tables and the simplified expressions
4354 in each iteration until we converge. */
4355 optimistic_info->nary->empty ();
4356 optimistic_info->phis->empty ();
4357 optimistic_info->references->empty ();
4358 obstack_free (&optimistic_info->nary_obstack, NULL);
4359 gcc_obstack_init (&optimistic_info->nary_obstack);
4360 optimistic_info->phis_pool->release ();
4361 optimistic_info->references_pool->release ();
4362 FOR_EACH_VEC_ELT (scc, i, var)
4363 gcc_assert (!VN_INFO (var)->needs_insertion
4364 && VN_INFO (var)->expr == NULL);
4365 FOR_EACH_VEC_ELT (scc, i, var)
4366 changed |= visit_use (var);
4369 if (dump_file && (dump_flags & TDF_DETAILS))
4370 fprintf (dump_file, "Processing SCC needed %d iterations\n", iterations);
4371 statistics_histogram_event (cfun, "SCC iterations", iterations);
4373 /* Finally, copy the contents of the no longer used optimistic
4374 table to the valid table. */
4375 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info->nary, nary, vn_nary_op_t, hin)
4376 copy_nary (nary, valid_info);
4377 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info->phis, phi, vn_phi_t, hip)
4378 copy_phi (phi, valid_info);
4379 FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info->references,
4380 ref, vn_reference_t, hir)
4381 copy_reference (ref, valid_info);
4383 current_info = valid_info;
4387 /* Pop the components of the found SCC for NAME off the SCC stack
4388 and process them. Returns true if all went well, false if
4389 we run into resource limits. */
4391 static void
4392 extract_and_process_scc_for_name (tree name)
4394 auto_vec<tree> scc;
4395 tree x;
4397 /* Found an SCC, pop the components off the SCC stack and
4398 process them. */
4401 x = sccstack.pop ();
4403 VN_INFO (x)->on_sccstack = false;
4404 scc.safe_push (x);
4405 } while (x != name);
4407 /* Drop all defs in the SCC to varying in case a SCC turns out to be
4408 incredibly large.
4409 ??? Just switch to a non-optimistic mode that avoids any iteration. */
4410 if (scc.length () > (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE))
4412 if (dump_file)
4414 print_scc (dump_file, scc);
4415 fprintf (dump_file, "WARNING: Giving up value-numbering SCC due to "
4416 "size %u exceeding %u\n", scc.length (),
4417 (unsigned)PARAM_VALUE (PARAM_SCCVN_MAX_SCC_SIZE));
4419 tree var;
4420 unsigned i;
4421 FOR_EACH_VEC_ELT (scc, i, var)
4423 gimple *def = SSA_NAME_DEF_STMT (var);
4424 mark_use_processed (var);
4425 if (SSA_NAME_IS_DEFAULT_DEF (var)
4426 || gimple_code (def) == GIMPLE_PHI)
4427 set_ssa_val_to (var, var);
4428 else
4429 defs_to_varying (def);
4431 return;
4434 if (scc.length () > 1)
4435 sort_scc (scc);
4437 process_scc (scc);
4440 /* Depth first search on NAME to discover and process SCC's in the SSA
4441 graph.
4442 Execution of this algorithm relies on the fact that the SCC's are
4443 popped off the stack in topological order.
4444 Returns true if successful, false if we stopped processing SCC's due
4445 to resource constraints. */
4447 static void
4448 DFS (tree name)
4450 auto_vec<ssa_op_iter> itervec;
4451 auto_vec<tree> namevec;
4452 use_operand_p usep = NULL;
4453 gimple *defstmt;
4454 tree use;
4455 ssa_op_iter iter;
4457 start_over:
4458 /* SCC info */
4459 VN_INFO (name)->dfsnum = next_dfs_num++;
4460 VN_INFO (name)->visited = true;
4461 VN_INFO (name)->low = VN_INFO (name)->dfsnum;
4463 sccstack.safe_push (name);
4464 VN_INFO (name)->on_sccstack = true;
4465 defstmt = SSA_NAME_DEF_STMT (name);
4467 /* Recursively DFS on our operands, looking for SCC's. */
4468 if (!gimple_nop_p (defstmt))
4470 /* Push a new iterator. */
4471 if (gphi *phi = dyn_cast <gphi *> (defstmt))
4472 usep = op_iter_init_phiuse (&iter, phi, SSA_OP_ALL_USES);
4473 else
4474 usep = op_iter_init_use (&iter, defstmt, SSA_OP_ALL_USES);
4476 else
4477 clear_and_done_ssa_iter (&iter);
4479 while (1)
4481 /* If we are done processing uses of a name, go up the stack
4482 of iterators and process SCCs as we found them. */
4483 if (op_iter_done (&iter))
4485 /* See if we found an SCC. */
4486 if (VN_INFO (name)->low == VN_INFO (name)->dfsnum)
4487 extract_and_process_scc_for_name (name);
4489 /* Check if we are done. */
4490 if (namevec.is_empty ())
4491 return;
4493 /* Restore the last use walker and continue walking there. */
4494 use = name;
4495 name = namevec.pop ();
4496 memcpy (&iter, &itervec.last (),
4497 sizeof (ssa_op_iter));
4498 itervec.pop ();
4499 goto continue_walking;
4502 use = USE_FROM_PTR (usep);
4504 /* Since we handle phi nodes, we will sometimes get
4505 invariants in the use expression. */
4506 if (TREE_CODE (use) == SSA_NAME)
4508 if (! (VN_INFO (use)->visited))
4510 /* Recurse by pushing the current use walking state on
4511 the stack and starting over. */
4512 itervec.safe_push (iter);
4513 namevec.safe_push (name);
4514 name = use;
4515 goto start_over;
4517 continue_walking:
4518 VN_INFO (name)->low = MIN (VN_INFO (name)->low,
4519 VN_INFO (use)->low);
4521 if (VN_INFO (use)->dfsnum < VN_INFO (name)->dfsnum
4522 && VN_INFO (use)->on_sccstack)
4524 VN_INFO (name)->low = MIN (VN_INFO (use)->dfsnum,
4525 VN_INFO (name)->low);
4529 usep = op_iter_next_use (&iter);
4533 /* Allocate a value number table. */
4535 static void
4536 allocate_vn_table (vn_tables_t table)
4538 table->phis = new vn_phi_table_type (23);
4539 table->nary = new vn_nary_op_table_type (23);
4540 table->references = new vn_reference_table_type (23);
4542 gcc_obstack_init (&table->nary_obstack);
4543 table->phis_pool = new object_allocator<vn_phi_s> ("VN phis");
4544 table->references_pool = new object_allocator<vn_reference_s>
4545 ("VN references");
4548 /* Free a value number table. */
4550 static void
4551 free_vn_table (vn_tables_t table)
4553 delete table->phis;
4554 table->phis = NULL;
4555 delete table->nary;
4556 table->nary = NULL;
4557 delete table->references;
4558 table->references = NULL;
4559 obstack_free (&table->nary_obstack, NULL);
4560 delete table->phis_pool;
4561 delete table->references_pool;
4564 static void
4565 init_scc_vn (void)
4567 int j;
4568 int *rpo_numbers_temp;
4570 calculate_dominance_info (CDI_DOMINATORS);
4571 mark_dfs_back_edges ();
4573 sccstack.create (0);
4574 constant_to_value_id = new hash_table<vn_constant_hasher> (23);
4576 constant_value_ids = BITMAP_ALLOC (NULL);
4578 next_dfs_num = 1;
4579 next_value_id = 1;
4581 vn_ssa_aux_table.create (num_ssa_names + 1);
4582 /* VEC_alloc doesn't actually grow it to the right size, it just
4583 preallocates the space to do so. */
4584 vn_ssa_aux_table.safe_grow_cleared (num_ssa_names + 1);
4585 gcc_obstack_init (&vn_ssa_aux_obstack);
4587 shared_lookup_phiargs.create (0);
4588 shared_lookup_references.create (0);
4589 rpo_numbers = XNEWVEC (int, last_basic_block_for_fn (cfun));
4590 rpo_numbers_temp =
4591 XNEWVEC (int, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS);
4592 pre_and_rev_post_order_compute (NULL, rpo_numbers_temp, false);
4594 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
4595 the i'th block in RPO order is bb. We want to map bb's to RPO
4596 numbers, so we need to rearrange this array. */
4597 for (j = 0; j < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; j++)
4598 rpo_numbers[rpo_numbers_temp[j]] = j;
4600 XDELETE (rpo_numbers_temp);
4602 VN_TOP = build_decl (UNKNOWN_LOCATION, VAR_DECL,
4603 get_identifier ("VN_TOP"), error_mark_node);
4605 renumber_gimple_stmt_uids ();
4607 /* Create the valid and optimistic value numbering tables. */
4608 valid_info = XCNEW (struct vn_tables_s);
4609 allocate_vn_table (valid_info);
4610 optimistic_info = XCNEW (struct vn_tables_s);
4611 allocate_vn_table (optimistic_info);
4612 current_info = valid_info;
4614 /* Create the VN_INFO structures, and initialize value numbers to
4615 TOP or VARYING for parameters. */
4616 size_t i;
4617 tree name;
4619 FOR_EACH_SSA_NAME (i, name, cfun)
4621 VN_INFO_GET (name)->valnum = VN_TOP;
4622 VN_INFO (name)->needs_insertion = false;
4623 VN_INFO (name)->expr = NULL;
4624 VN_INFO (name)->value_id = 0;
4626 if (!SSA_NAME_IS_DEFAULT_DEF (name))
4627 continue;
4629 switch (TREE_CODE (SSA_NAME_VAR (name)))
4631 case VAR_DECL:
4632 /* All undefined vars are VARYING. */
4633 VN_INFO (name)->valnum = name;
4634 VN_INFO (name)->visited = true;
4635 break;
4637 case PARM_DECL:
4638 /* Parameters are VARYING but we can record a condition
4639 if we know it is a non-NULL pointer. */
4640 VN_INFO (name)->visited = true;
4641 VN_INFO (name)->valnum = name;
4642 if (POINTER_TYPE_P (TREE_TYPE (name))
4643 && nonnull_arg_p (SSA_NAME_VAR (name)))
4645 tree ops[2];
4646 ops[0] = name;
4647 ops[1] = build_int_cst (TREE_TYPE (name), 0);
4648 vn_nary_op_insert_pieces (2, NE_EXPR, boolean_type_node, ops,
4649 boolean_true_node, 0);
4650 if (dump_file && (dump_flags & TDF_DETAILS))
4652 fprintf (dump_file, "Recording ");
4653 print_generic_expr (dump_file, name, TDF_SLIM);
4654 fprintf (dump_file, " != 0\n");
4657 break;
4659 case RESULT_DECL:
4660 /* If the result is passed by invisible reference the default
4661 def is initialized, otherwise it's uninitialized. Still
4662 undefined is varying. */
4663 VN_INFO (name)->visited = true;
4664 VN_INFO (name)->valnum = name;
4665 break;
4667 default:
4668 gcc_unreachable ();
4673 /* Restore SSA info that has been reset on value leaders. */
4675 void
4676 scc_vn_restore_ssa_info (void)
4678 unsigned i;
4679 tree name;
4681 FOR_EACH_SSA_NAME (i, name, cfun)
4683 if (has_VN_INFO (name))
4685 if (VN_INFO (name)->needs_insertion)
4687 else if (POINTER_TYPE_P (TREE_TYPE (name))
4688 && VN_INFO (name)->info.ptr_info)
4689 SSA_NAME_PTR_INFO (name) = VN_INFO (name)->info.ptr_info;
4690 else if (INTEGRAL_TYPE_P (TREE_TYPE (name))
4691 && VN_INFO (name)->info.range_info)
4693 SSA_NAME_RANGE_INFO (name) = VN_INFO (name)->info.range_info;
4694 SSA_NAME_ANTI_RANGE_P (name)
4695 = VN_INFO (name)->range_info_anti_range_p;
4701 void
4702 free_scc_vn (void)
4704 size_t i;
4705 tree name;
4707 delete constant_to_value_id;
4708 constant_to_value_id = NULL;
4709 BITMAP_FREE (constant_value_ids);
4710 shared_lookup_phiargs.release ();
4711 shared_lookup_references.release ();
4712 XDELETEVEC (rpo_numbers);
4714 FOR_EACH_SSA_NAME (i, name, cfun)
4716 if (has_VN_INFO (name)
4717 && VN_INFO (name)->needs_insertion)
4718 release_ssa_name (name);
4720 obstack_free (&vn_ssa_aux_obstack, NULL);
4721 vn_ssa_aux_table.release ();
4723 sccstack.release ();
4724 free_vn_table (valid_info);
4725 XDELETE (valid_info);
4726 free_vn_table (optimistic_info);
4727 XDELETE (optimistic_info);
4729 BITMAP_FREE (const_parms);
4732 /* Set *ID according to RESULT. */
4734 static void
4735 set_value_id_for_result (tree result, unsigned int *id)
4737 if (result && TREE_CODE (result) == SSA_NAME)
4738 *id = VN_INFO (result)->value_id;
4739 else if (result && is_gimple_min_invariant (result))
4740 *id = get_or_alloc_constant_value_id (result);
4741 else
4742 *id = get_next_value_id ();
4745 /* Set the value ids in the valid hash tables. */
4747 static void
4748 set_hashtable_value_ids (void)
4750 vn_nary_op_iterator_type hin;
4751 vn_phi_iterator_type hip;
4752 vn_reference_iterator_type hir;
4753 vn_nary_op_t vno;
4754 vn_reference_t vr;
4755 vn_phi_t vp;
4757 /* Now set the value ids of the things we had put in the hash
4758 table. */
4760 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info->nary, vno, vn_nary_op_t, hin)
4761 set_value_id_for_result (vno->result, &vno->value_id);
4763 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info->phis, vp, vn_phi_t, hip)
4764 set_value_id_for_result (vp->result, &vp->value_id);
4766 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info->references, vr, vn_reference_t,
4767 hir)
4768 set_value_id_for_result (vr->result, &vr->value_id);
4771 class sccvn_dom_walker : public dom_walker
4773 public:
4774 sccvn_dom_walker ()
4775 : dom_walker (CDI_DOMINATORS, REACHABLE_BLOCKS), cond_stack (0) {}
4777 virtual edge before_dom_children (basic_block);
4778 virtual void after_dom_children (basic_block);
4780 void record_cond (basic_block,
4781 enum tree_code code, tree lhs, tree rhs, bool value);
4782 void record_conds (basic_block,
4783 enum tree_code code, tree lhs, tree rhs, bool value);
4785 auto_vec<std::pair <basic_block, std::pair <vn_nary_op_t, vn_nary_op_t> > >
4786 cond_stack;
4789 /* Record a temporary condition for the BB and its dominated blocks. */
4791 void
4792 sccvn_dom_walker::record_cond (basic_block bb,
4793 enum tree_code code, tree lhs, tree rhs,
4794 bool value)
4796 tree ops[2] = { lhs, rhs };
4797 vn_nary_op_t old = NULL;
4798 if (vn_nary_op_lookup_pieces (2, code, boolean_type_node, ops, &old))
4799 current_info->nary->remove_elt_with_hash (old, old->hashcode);
4800 vn_nary_op_t cond
4801 = vn_nary_op_insert_pieces (2, code, boolean_type_node, ops,
4802 value
4803 ? boolean_true_node
4804 : boolean_false_node, 0);
4805 if (dump_file && (dump_flags & TDF_DETAILS))
4807 fprintf (dump_file, "Recording temporarily ");
4808 print_generic_expr (dump_file, ops[0], TDF_SLIM);
4809 fprintf (dump_file, " %s ", get_tree_code_name (code));
4810 print_generic_expr (dump_file, ops[1], TDF_SLIM);
4811 fprintf (dump_file, " == %s%s\n",
4812 value ? "true" : "false",
4813 old ? " (old entry saved)" : "");
4815 cond_stack.safe_push (std::make_pair (bb, std::make_pair (cond, old)));
4818 /* Record temporary conditions for the BB and its dominated blocks
4819 according to LHS CODE RHS == VALUE and its dominated conditions. */
4821 void
4822 sccvn_dom_walker::record_conds (basic_block bb,
4823 enum tree_code code, tree lhs, tree rhs,
4824 bool value)
4826 /* Record the original condition. */
4827 record_cond (bb, code, lhs, rhs, value);
4829 if (!value)
4830 return;
4832 /* Record dominated conditions if the condition is true. Note that
4833 the inversion is already recorded. */
4834 switch (code)
4836 case LT_EXPR:
4837 case GT_EXPR:
4838 record_cond (bb, code == LT_EXPR ? LE_EXPR : GE_EXPR, lhs, rhs, true);
4839 record_cond (bb, NE_EXPR, lhs, rhs, true);
4840 record_cond (bb, EQ_EXPR, lhs, rhs, false);
4841 break;
4843 case EQ_EXPR:
4844 record_cond (bb, LE_EXPR, lhs, rhs, true);
4845 record_cond (bb, GE_EXPR, lhs, rhs, true);
4846 record_cond (bb, LT_EXPR, lhs, rhs, false);
4847 record_cond (bb, GT_EXPR, lhs, rhs, false);
4848 break;
4850 default:
4851 break;
4855 /* Restore expressions and values derived from conditionals. */
4857 void
4858 sccvn_dom_walker::after_dom_children (basic_block bb)
4860 while (!cond_stack.is_empty ()
4861 && cond_stack.last ().first == bb)
4863 vn_nary_op_t cond = cond_stack.last ().second.first;
4864 vn_nary_op_t old = cond_stack.last ().second.second;
4865 current_info->nary->remove_elt_with_hash (cond, cond->hashcode);
4866 if (old)
4867 vn_nary_op_insert_into (old, current_info->nary, false);
4868 cond_stack.pop ();
4872 /* Value number all statements in BB. */
4874 edge
4875 sccvn_dom_walker::before_dom_children (basic_block bb)
4877 if (dump_file && (dump_flags & TDF_DETAILS))
4878 fprintf (dump_file, "Visiting BB %d\n", bb->index);
4880 /* If we have a single predecessor record the equivalence from a
4881 possible condition on the predecessor edge. */
4882 edge pred_e = single_pred_edge_ignoring_loop_edges (bb, false);
4883 if (pred_e)
4885 /* Check if there are multiple executable successor edges in
4886 the source block. Otherwise there is no additional info
4887 to be recorded. */
4888 edge_iterator ei;
4889 edge e2;
4890 FOR_EACH_EDGE (e2, ei, pred_e->src->succs)
4891 if (e2 != pred_e
4892 && e2->flags & EDGE_EXECUTABLE)
4893 break;
4894 if (e2 && (e2->flags & EDGE_EXECUTABLE))
4896 gimple *stmt = last_stmt (pred_e->src);
4897 if (stmt
4898 && gimple_code (stmt) == GIMPLE_COND)
4900 enum tree_code code = gimple_cond_code (stmt);
4901 tree lhs = gimple_cond_lhs (stmt);
4902 tree rhs = gimple_cond_rhs (stmt);
4903 record_conds (bb, code, lhs, rhs,
4904 (pred_e->flags & EDGE_TRUE_VALUE) != 0);
4905 code = invert_tree_comparison (code, HONOR_NANS (lhs));
4906 if (code != ERROR_MARK)
4907 record_conds (bb, code, lhs, rhs,
4908 (pred_e->flags & EDGE_TRUE_VALUE) == 0);
4913 /* Value-number all defs in the basic-block. */
4914 for (gphi_iterator gsi = gsi_start_phis (bb);
4915 !gsi_end_p (gsi); gsi_next (&gsi))
4917 gphi *phi = gsi.phi ();
4918 tree res = PHI_RESULT (phi);
4919 if (!VN_INFO (res)->visited)
4920 DFS (res);
4922 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
4923 !gsi_end_p (gsi); gsi_next (&gsi))
4925 ssa_op_iter i;
4926 tree op;
4927 FOR_EACH_SSA_TREE_OPERAND (op, gsi_stmt (gsi), i, SSA_OP_ALL_DEFS)
4928 if (!VN_INFO (op)->visited)
4929 DFS (op);
4932 /* Finally look at the last stmt. */
4933 gimple *stmt = last_stmt (bb);
4934 if (!stmt)
4935 return NULL;
4937 enum gimple_code code = gimple_code (stmt);
4938 if (code != GIMPLE_COND
4939 && code != GIMPLE_SWITCH
4940 && code != GIMPLE_GOTO)
4941 return NULL;
4943 if (dump_file && (dump_flags & TDF_DETAILS))
4945 fprintf (dump_file, "Visiting control stmt ending BB %d: ", bb->index);
4946 print_gimple_stmt (dump_file, stmt, 0);
4949 /* ??? We can even handle stmts with outgoing EH or ABNORMAL edges
4950 if value-numbering can prove they are not reachable. Handling
4951 computed gotos is also possible. */
4952 tree val;
4953 switch (code)
4955 case GIMPLE_COND:
4957 tree lhs = vn_valueize (gimple_cond_lhs (stmt));
4958 tree rhs = vn_valueize (gimple_cond_rhs (stmt));
4959 val = gimple_simplify (gimple_cond_code (stmt),
4960 boolean_type_node, lhs, rhs,
4961 NULL, vn_valueize);
4962 /* If that didn't simplify to a constant see if we have recorded
4963 temporary expressions from taken edges. */
4964 if (!val || TREE_CODE (val) != INTEGER_CST)
4966 tree ops[2];
4967 ops[0] = lhs;
4968 ops[1] = rhs;
4969 val = vn_nary_op_lookup_pieces (2, gimple_cond_code (stmt),
4970 boolean_type_node, ops, NULL);
4972 break;
4974 case GIMPLE_SWITCH:
4975 val = gimple_switch_index (as_a <gswitch *> (stmt));
4976 break;
4977 case GIMPLE_GOTO:
4978 val = gimple_goto_dest (stmt);
4979 break;
4980 default:
4981 gcc_unreachable ();
4983 if (!val)
4984 return NULL;
4986 edge taken = find_taken_edge (bb, vn_valueize (val));
4987 if (!taken)
4988 return NULL;
4990 if (dump_file && (dump_flags & TDF_DETAILS))
4991 fprintf (dump_file, "Marking all edges out of BB %d but (%d -> %d) as "
4992 "not executable\n", bb->index, bb->index, taken->dest->index);
4994 return taken;
4997 /* Do SCCVN. Returns true if it finished, false if we bailed out
4998 due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies
4999 how we use the alias oracle walking during the VN process. */
5001 void
5002 run_scc_vn (vn_lookup_kind default_vn_walk_kind_)
5004 size_t i;
5006 default_vn_walk_kind = default_vn_walk_kind_;
5008 init_scc_vn ();
5010 /* Collect pointers we know point to readonly memory. */
5011 const_parms = BITMAP_ALLOC (NULL);
5012 tree fnspec = lookup_attribute ("fn spec",
5013 TYPE_ATTRIBUTES (TREE_TYPE (cfun->decl)));
5014 if (fnspec)
5016 fnspec = TREE_VALUE (TREE_VALUE (fnspec));
5017 i = 1;
5018 for (tree arg = DECL_ARGUMENTS (cfun->decl);
5019 arg; arg = DECL_CHAIN (arg), ++i)
5021 if (i >= (unsigned) TREE_STRING_LENGTH (fnspec))
5022 break;
5023 if (TREE_STRING_POINTER (fnspec)[i] == 'R'
5024 || TREE_STRING_POINTER (fnspec)[i] == 'r')
5026 tree name = ssa_default_def (cfun, arg);
5027 if (name)
5028 bitmap_set_bit (const_parms, SSA_NAME_VERSION (name));
5033 /* Walk all blocks in dominator order, value-numbering stmts
5034 SSA defs and decide whether outgoing edges are not executable. */
5035 sccvn_dom_walker walker;
5036 walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
5038 /* Initialize the value ids and prune out remaining VN_TOPs
5039 from dead code. */
5040 tree name;
5041 FOR_EACH_SSA_NAME (i, name, cfun)
5043 vn_ssa_aux_t info = VN_INFO (name);
5044 if (!info->visited
5045 || info->valnum == VN_TOP)
5046 info->valnum = name;
5047 if (info->valnum == name)
5048 info->value_id = get_next_value_id ();
5049 else if (is_gimple_min_invariant (info->valnum))
5050 info->value_id = get_or_alloc_constant_value_id (info->valnum);
5053 /* Propagate. */
5054 FOR_EACH_SSA_NAME (i, name, cfun)
5056 vn_ssa_aux_t info = VN_INFO (name);
5057 if (TREE_CODE (info->valnum) == SSA_NAME
5058 && info->valnum != name
5059 && info->value_id != VN_INFO (info->valnum)->value_id)
5060 info->value_id = VN_INFO (info->valnum)->value_id;
5063 set_hashtable_value_ids ();
5065 if (dump_file && (dump_flags & TDF_DETAILS))
5067 fprintf (dump_file, "Value numbers:\n");
5068 FOR_EACH_SSA_NAME (i, name, cfun)
5070 if (VN_INFO (name)->visited
5071 && SSA_VAL (name) != name)
5073 print_generic_expr (dump_file, name);
5074 fprintf (dump_file, " = ");
5075 print_generic_expr (dump_file, SSA_VAL (name));
5076 fprintf (dump_file, "\n");
5082 /* Return the maximum value id we have ever seen. */
5084 unsigned int
5085 get_max_value_id (void)
5087 return next_value_id;
5090 /* Return the next unique value id. */
5092 unsigned int
5093 get_next_value_id (void)
5095 return next_value_id++;
5099 /* Compare two expressions E1 and E2 and return true if they are equal. */
5101 bool
5102 expressions_equal_p (tree e1, tree e2)
5104 /* The obvious case. */
5105 if (e1 == e2)
5106 return true;
5108 /* If either one is VN_TOP consider them equal. */
5109 if (e1 == VN_TOP || e2 == VN_TOP)
5110 return true;
5112 /* If only one of them is null, they cannot be equal. */
5113 if (!e1 || !e2)
5114 return false;
5116 /* Now perform the actual comparison. */
5117 if (TREE_CODE (e1) == TREE_CODE (e2)
5118 && operand_equal_p (e1, e2, OEP_PURE_SAME))
5119 return true;
5121 return false;
5125 /* Return true if the nary operation NARY may trap. This is a copy
5126 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
5128 bool
5129 vn_nary_may_trap (vn_nary_op_t nary)
5131 tree type;
5132 tree rhs2 = NULL_TREE;
5133 bool honor_nans = false;
5134 bool honor_snans = false;
5135 bool fp_operation = false;
5136 bool honor_trapv = false;
5137 bool handled, ret;
5138 unsigned i;
5140 if (TREE_CODE_CLASS (nary->opcode) == tcc_comparison
5141 || TREE_CODE_CLASS (nary->opcode) == tcc_unary
5142 || TREE_CODE_CLASS (nary->opcode) == tcc_binary)
5144 type = nary->type;
5145 fp_operation = FLOAT_TYPE_P (type);
5146 if (fp_operation)
5148 honor_nans = flag_trapping_math && !flag_finite_math_only;
5149 honor_snans = flag_signaling_nans != 0;
5151 else if (INTEGRAL_TYPE_P (type)
5152 && TYPE_OVERFLOW_TRAPS (type))
5153 honor_trapv = true;
5155 if (nary->length >= 2)
5156 rhs2 = nary->op[1];
5157 ret = operation_could_trap_helper_p (nary->opcode, fp_operation,
5158 honor_trapv,
5159 honor_nans, honor_snans, rhs2,
5160 &handled);
5161 if (handled
5162 && ret)
5163 return true;
5165 for (i = 0; i < nary->length; ++i)
5166 if (tree_could_trap_p (nary->op[i]))
5167 return true;
5169 return false;
5173 class eliminate_dom_walker : public dom_walker
5175 public:
5176 eliminate_dom_walker (cdi_direction, bitmap);
5177 ~eliminate_dom_walker ();
5179 virtual edge before_dom_children (basic_block);
5180 virtual void after_dom_children (basic_block);
5182 tree eliminate_avail (tree op);
5183 void eliminate_push_avail (tree op);
5184 tree eliminate_insert (gimple_stmt_iterator *gsi, tree val);
5186 bool do_pre;
5187 unsigned int el_todo;
5188 unsigned int eliminations;
5189 unsigned int insertions;
5191 /* SSA names that had their defs inserted by PRE if do_pre. */
5192 bitmap inserted_exprs;
5194 /* Blocks with statements that have had their EH properties changed. */
5195 bitmap need_eh_cleanup;
5197 /* Blocks with statements that have had their AB properties changed. */
5198 bitmap need_ab_cleanup;
5200 auto_vec<gimple *> to_remove;
5201 auto_vec<gimple *> to_fixup;
5202 auto_vec<tree> avail;
5203 auto_vec<tree> avail_stack;
5206 eliminate_dom_walker::eliminate_dom_walker (cdi_direction direction,
5207 bitmap inserted_exprs_)
5208 : dom_walker (direction), do_pre (inserted_exprs_ != NULL),
5209 el_todo (0), eliminations (0), insertions (0),
5210 inserted_exprs (inserted_exprs_)
5212 need_eh_cleanup = BITMAP_ALLOC (NULL);
5213 need_ab_cleanup = BITMAP_ALLOC (NULL);
5216 eliminate_dom_walker::~eliminate_dom_walker ()
5218 BITMAP_FREE (need_eh_cleanup);
5219 BITMAP_FREE (need_ab_cleanup);
5222 /* Return a leader for OP that is available at the current point of the
5223 eliminate domwalk. */
5225 tree
5226 eliminate_dom_walker::eliminate_avail (tree op)
5228 tree valnum = VN_INFO (op)->valnum;
5229 if (TREE_CODE (valnum) == SSA_NAME)
5231 if (SSA_NAME_IS_DEFAULT_DEF (valnum))
5232 return valnum;
5233 if (avail.length () > SSA_NAME_VERSION (valnum))
5234 return avail[SSA_NAME_VERSION (valnum)];
5236 else if (is_gimple_min_invariant (valnum))
5237 return valnum;
5238 return NULL_TREE;
5241 /* At the current point of the eliminate domwalk make OP available. */
5243 void
5244 eliminate_dom_walker::eliminate_push_avail (tree op)
5246 tree valnum = VN_INFO (op)->valnum;
5247 if (TREE_CODE (valnum) == SSA_NAME)
5249 if (avail.length () <= SSA_NAME_VERSION (valnum))
5250 avail.safe_grow_cleared (SSA_NAME_VERSION (valnum) + 1);
5251 tree pushop = op;
5252 if (avail[SSA_NAME_VERSION (valnum)])
5253 pushop = avail[SSA_NAME_VERSION (valnum)];
5254 avail_stack.safe_push (pushop);
5255 avail[SSA_NAME_VERSION (valnum)] = op;
5259 /* Insert the expression recorded by SCCVN for VAL at *GSI. Returns
5260 the leader for the expression if insertion was successful. */
5262 tree
5263 eliminate_dom_walker::eliminate_insert (gimple_stmt_iterator *gsi, tree val)
5265 /* We can insert a sequence with a single assignment only. */
5266 gimple_seq stmts = VN_INFO (val)->expr;
5267 if (!gimple_seq_singleton_p (stmts))
5268 return NULL_TREE;
5269 gassign *stmt = dyn_cast <gassign *> (gimple_seq_first_stmt (stmts));
5270 if (!stmt
5271 || (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
5272 && gimple_assign_rhs_code (stmt) != VIEW_CONVERT_EXPR
5273 && gimple_assign_rhs_code (stmt) != BIT_FIELD_REF
5274 && (gimple_assign_rhs_code (stmt) != BIT_AND_EXPR
5275 || TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)))
5276 return NULL_TREE;
5278 tree op = gimple_assign_rhs1 (stmt);
5279 if (gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR
5280 || gimple_assign_rhs_code (stmt) == BIT_FIELD_REF)
5281 op = TREE_OPERAND (op, 0);
5282 tree leader = TREE_CODE (op) == SSA_NAME ? eliminate_avail (op) : op;
5283 if (!leader)
5284 return NULL_TREE;
5286 tree res;
5287 stmts = NULL;
5288 if (gimple_assign_rhs_code (stmt) == BIT_FIELD_REF)
5289 res = gimple_build (&stmts, BIT_FIELD_REF,
5290 TREE_TYPE (val), leader,
5291 TREE_OPERAND (gimple_assign_rhs1 (stmt), 1),
5292 TREE_OPERAND (gimple_assign_rhs1 (stmt), 2));
5293 else if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR)
5294 res = gimple_build (&stmts, BIT_AND_EXPR,
5295 TREE_TYPE (val), leader, gimple_assign_rhs2 (stmt));
5296 else
5297 res = gimple_build (&stmts, gimple_assign_rhs_code (stmt),
5298 TREE_TYPE (val), leader);
5299 if (TREE_CODE (res) != SSA_NAME
5300 || SSA_NAME_IS_DEFAULT_DEF (res)
5301 || gimple_bb (SSA_NAME_DEF_STMT (res)))
5303 gimple_seq_discard (stmts);
5305 /* During propagation we have to treat SSA info conservatively
5306 and thus we can end up simplifying the inserted expression
5307 at elimination time to sth not defined in stmts. */
5308 /* But then this is a redundancy we failed to detect. Which means
5309 res now has two values. That doesn't play well with how
5310 we track availability here, so give up. */
5311 if (dump_file && (dump_flags & TDF_DETAILS))
5313 if (TREE_CODE (res) == SSA_NAME)
5314 res = eliminate_avail (res);
5315 if (res)
5317 fprintf (dump_file, "Failed to insert expression for value ");
5318 print_generic_expr (dump_file, val);
5319 fprintf (dump_file, " which is really fully redundant to ");
5320 print_generic_expr (dump_file, res);
5321 fprintf (dump_file, "\n");
5325 return NULL_TREE;
5327 else
5329 gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
5330 VN_INFO_GET (res)->valnum = val;
5333 insertions++;
5334 if (dump_file && (dump_flags & TDF_DETAILS))
5336 fprintf (dump_file, "Inserted ");
5337 print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (res), 0);
5340 return res;
5345 /* Perform elimination for the basic-block B during the domwalk. */
5347 edge
5348 eliminate_dom_walker::before_dom_children (basic_block b)
5350 /* Mark new bb. */
5351 avail_stack.safe_push (NULL_TREE);
5353 /* Skip unreachable blocks marked unreachable during the SCCVN domwalk. */
5354 edge_iterator ei;
5355 edge e;
5356 FOR_EACH_EDGE (e, ei, b->preds)
5357 if (e->flags & EDGE_EXECUTABLE)
5358 break;
5359 if (! e)
5360 return NULL;
5362 for (gphi_iterator gsi = gsi_start_phis (b); !gsi_end_p (gsi);)
5364 gphi *phi = gsi.phi ();
5365 tree res = PHI_RESULT (phi);
5367 if (virtual_operand_p (res))
5369 gsi_next (&gsi);
5370 continue;
5373 tree sprime = eliminate_avail (res);
5374 if (sprime
5375 && sprime != res)
5377 if (dump_file && (dump_flags & TDF_DETAILS))
5379 fprintf (dump_file, "Replaced redundant PHI node defining ");
5380 print_generic_expr (dump_file, res);
5381 fprintf (dump_file, " with ");
5382 print_generic_expr (dump_file, sprime);
5383 fprintf (dump_file, "\n");
5386 /* If we inserted this PHI node ourself, it's not an elimination. */
5387 if (! inserted_exprs
5388 || ! bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (res)))
5389 eliminations++;
5391 /* If we will propagate into all uses don't bother to do
5392 anything. */
5393 if (may_propagate_copy (res, sprime))
5395 /* Mark the PHI for removal. */
5396 to_remove.safe_push (phi);
5397 gsi_next (&gsi);
5398 continue;
5401 remove_phi_node (&gsi, false);
5403 if (!useless_type_conversion_p (TREE_TYPE (res), TREE_TYPE (sprime)))
5404 sprime = fold_convert (TREE_TYPE (res), sprime);
5405 gimple *stmt = gimple_build_assign (res, sprime);
5406 gimple_stmt_iterator gsi2 = gsi_after_labels (b);
5407 gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
5408 continue;
5411 eliminate_push_avail (res);
5412 gsi_next (&gsi);
5415 for (gimple_stmt_iterator gsi = gsi_start_bb (b);
5416 !gsi_end_p (gsi);
5417 gsi_next (&gsi))
5419 tree sprime = NULL_TREE;
5420 gimple *stmt = gsi_stmt (gsi);
5421 tree lhs = gimple_get_lhs (stmt);
5422 if (lhs && TREE_CODE (lhs) == SSA_NAME
5423 && !gimple_has_volatile_ops (stmt)
5424 /* See PR43491. Do not replace a global register variable when
5425 it is a the RHS of an assignment. Do replace local register
5426 variables since gcc does not guarantee a local variable will
5427 be allocated in register.
5428 ??? The fix isn't effective here. This should instead
5429 be ensured by not value-numbering them the same but treating
5430 them like volatiles? */
5431 && !(gimple_assign_single_p (stmt)
5432 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == VAR_DECL
5433 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt))
5434 && is_global_var (gimple_assign_rhs1 (stmt)))))
5436 sprime = eliminate_avail (lhs);
5437 if (!sprime)
5439 /* If there is no existing usable leader but SCCVN thinks
5440 it has an expression it wants to use as replacement,
5441 insert that. */
5442 tree val = VN_INFO (lhs)->valnum;
5443 if (val != VN_TOP
5444 && TREE_CODE (val) == SSA_NAME
5445 && VN_INFO (val)->needs_insertion
5446 && VN_INFO (val)->expr != NULL
5447 && (sprime = eliminate_insert (&gsi, val)) != NULL_TREE)
5448 eliminate_push_avail (sprime);
5451 /* If this now constitutes a copy duplicate points-to
5452 and range info appropriately. This is especially
5453 important for inserted code. See tree-ssa-copy.c
5454 for similar code. */
5455 if (sprime
5456 && TREE_CODE (sprime) == SSA_NAME)
5458 basic_block sprime_b = gimple_bb (SSA_NAME_DEF_STMT (sprime));
5459 if (POINTER_TYPE_P (TREE_TYPE (lhs))
5460 && VN_INFO_PTR_INFO (lhs)
5461 && ! VN_INFO_PTR_INFO (sprime))
5463 duplicate_ssa_name_ptr_info (sprime,
5464 VN_INFO_PTR_INFO (lhs));
5465 if (b != sprime_b)
5466 mark_ptr_info_alignment_unknown
5467 (SSA_NAME_PTR_INFO (sprime));
5469 else if (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
5470 && VN_INFO_RANGE_INFO (lhs)
5471 && ! VN_INFO_RANGE_INFO (sprime)
5472 && b == sprime_b)
5473 duplicate_ssa_name_range_info (sprime,
5474 VN_INFO_RANGE_TYPE (lhs),
5475 VN_INFO_RANGE_INFO (lhs));
5478 /* Inhibit the use of an inserted PHI on a loop header when
5479 the address of the memory reference is a simple induction
5480 variable. In other cases the vectorizer won't do anything
5481 anyway (either it's loop invariant or a complicated
5482 expression). */
5483 if (sprime
5484 && TREE_CODE (sprime) == SSA_NAME
5485 && do_pre
5486 && (flag_tree_loop_vectorize || flag_tree_parallelize_loops > 1)
5487 && loop_outer (b->loop_father)
5488 && has_zero_uses (sprime)
5489 && bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (sprime))
5490 && gimple_assign_load_p (stmt))
5492 gimple *def_stmt = SSA_NAME_DEF_STMT (sprime);
5493 basic_block def_bb = gimple_bb (def_stmt);
5494 if (gimple_code (def_stmt) == GIMPLE_PHI
5495 && def_bb->loop_father->header == def_bb)
5497 loop_p loop = def_bb->loop_father;
5498 ssa_op_iter iter;
5499 tree op;
5500 bool found = false;
5501 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
5503 affine_iv iv;
5504 def_bb = gimple_bb (SSA_NAME_DEF_STMT (op));
5505 if (def_bb
5506 && flow_bb_inside_loop_p (loop, def_bb)
5507 && simple_iv (loop, loop, op, &iv, true))
5509 found = true;
5510 break;
5513 if (found)
5515 if (dump_file && (dump_flags & TDF_DETAILS))
5517 fprintf (dump_file, "Not replacing ");
5518 print_gimple_expr (dump_file, stmt, 0);
5519 fprintf (dump_file, " with ");
5520 print_generic_expr (dump_file, sprime);
5521 fprintf (dump_file, " which would add a loop"
5522 " carried dependence to loop %d\n",
5523 loop->num);
5525 /* Don't keep sprime available. */
5526 sprime = NULL_TREE;
5531 if (sprime)
5533 /* If we can propagate the value computed for LHS into
5534 all uses don't bother doing anything with this stmt. */
5535 if (may_propagate_copy (lhs, sprime))
5537 /* Mark it for removal. */
5538 to_remove.safe_push (stmt);
5540 /* ??? Don't count copy/constant propagations. */
5541 if (gimple_assign_single_p (stmt)
5542 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
5543 || gimple_assign_rhs1 (stmt) == sprime))
5544 continue;
5546 if (dump_file && (dump_flags & TDF_DETAILS))
5548 fprintf (dump_file, "Replaced ");
5549 print_gimple_expr (dump_file, stmt, 0);
5550 fprintf (dump_file, " with ");
5551 print_generic_expr (dump_file, sprime);
5552 fprintf (dump_file, " in all uses of ");
5553 print_gimple_stmt (dump_file, stmt, 0);
5556 eliminations++;
5557 continue;
5560 /* If this is an assignment from our leader (which
5561 happens in the case the value-number is a constant)
5562 then there is nothing to do. */
5563 if (gimple_assign_single_p (stmt)
5564 && sprime == gimple_assign_rhs1 (stmt))
5565 continue;
5567 /* Else replace its RHS. */
5568 bool can_make_abnormal_goto
5569 = is_gimple_call (stmt)
5570 && stmt_can_make_abnormal_goto (stmt);
5572 if (dump_file && (dump_flags & TDF_DETAILS))
5574 fprintf (dump_file, "Replaced ");
5575 print_gimple_expr (dump_file, stmt, 0);
5576 fprintf (dump_file, " with ");
5577 print_generic_expr (dump_file, sprime);
5578 fprintf (dump_file, " in ");
5579 print_gimple_stmt (dump_file, stmt, 0);
5582 eliminations++;
5583 gimple *orig_stmt = stmt;
5584 if (!useless_type_conversion_p (TREE_TYPE (lhs),
5585 TREE_TYPE (sprime)))
5586 sprime = fold_convert (TREE_TYPE (lhs), sprime);
5587 tree vdef = gimple_vdef (stmt);
5588 tree vuse = gimple_vuse (stmt);
5589 propagate_tree_value_into_stmt (&gsi, sprime);
5590 stmt = gsi_stmt (gsi);
5591 update_stmt (stmt);
5592 if (vdef != gimple_vdef (stmt))
5593 VN_INFO (vdef)->valnum = vuse;
5595 /* If we removed EH side-effects from the statement, clean
5596 its EH information. */
5597 if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
5599 bitmap_set_bit (need_eh_cleanup,
5600 gimple_bb (stmt)->index);
5601 if (dump_file && (dump_flags & TDF_DETAILS))
5602 fprintf (dump_file, " Removed EH side-effects.\n");
5605 /* Likewise for AB side-effects. */
5606 if (can_make_abnormal_goto
5607 && !stmt_can_make_abnormal_goto (stmt))
5609 bitmap_set_bit (need_ab_cleanup,
5610 gimple_bb (stmt)->index);
5611 if (dump_file && (dump_flags & TDF_DETAILS))
5612 fprintf (dump_file, " Removed AB side-effects.\n");
5615 continue;
5619 /* If the statement is a scalar store, see if the expression
5620 has the same value number as its rhs. If so, the store is
5621 dead. */
5622 if (gimple_assign_single_p (stmt)
5623 && !gimple_has_volatile_ops (stmt)
5624 && !is_gimple_reg (gimple_assign_lhs (stmt))
5625 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
5626 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
5628 tree val;
5629 tree rhs = gimple_assign_rhs1 (stmt);
5630 vn_reference_t vnresult;
5631 val = vn_reference_lookup (lhs, gimple_vuse (stmt), VN_WALKREWRITE,
5632 &vnresult, false);
5633 if (TREE_CODE (rhs) == SSA_NAME)
5634 rhs = VN_INFO (rhs)->valnum;
5635 if (val
5636 && operand_equal_p (val, rhs, 0))
5638 /* We can only remove the later store if the former aliases
5639 at least all accesses the later one does or if the store
5640 was to readonly memory storing the same value. */
5641 alias_set_type set = get_alias_set (lhs);
5642 if (! vnresult
5643 || vnresult->set == set
5644 || alias_set_subset_of (set, vnresult->set))
5646 if (dump_file && (dump_flags & TDF_DETAILS))
5648 fprintf (dump_file, "Deleted redundant store ");
5649 print_gimple_stmt (dump_file, stmt, 0);
5652 /* Queue stmt for removal. */
5653 to_remove.safe_push (stmt);
5654 continue;
5659 /* If this is a control statement value numbering left edges
5660 unexecuted on force the condition in a way consistent with
5661 that. */
5662 if (gcond *cond = dyn_cast <gcond *> (stmt))
5664 if ((EDGE_SUCC (b, 0)->flags & EDGE_EXECUTABLE)
5665 ^ (EDGE_SUCC (b, 1)->flags & EDGE_EXECUTABLE))
5667 if (dump_file && (dump_flags & TDF_DETAILS))
5669 fprintf (dump_file, "Removing unexecutable edge from ");
5670 print_gimple_stmt (dump_file, stmt, 0);
5672 if (((EDGE_SUCC (b, 0)->flags & EDGE_TRUE_VALUE) != 0)
5673 == ((EDGE_SUCC (b, 0)->flags & EDGE_EXECUTABLE) != 0))
5674 gimple_cond_make_true (cond);
5675 else
5676 gimple_cond_make_false (cond);
5677 update_stmt (cond);
5678 el_todo |= TODO_cleanup_cfg;
5679 continue;
5683 bool can_make_abnormal_goto = stmt_can_make_abnormal_goto (stmt);
5684 bool was_noreturn = (is_gimple_call (stmt)
5685 && gimple_call_noreturn_p (stmt));
5686 tree vdef = gimple_vdef (stmt);
5687 tree vuse = gimple_vuse (stmt);
5689 /* If we didn't replace the whole stmt (or propagate the result
5690 into all uses), replace all uses on this stmt with their
5691 leaders. */
5692 bool modified = false;
5693 use_operand_p use_p;
5694 ssa_op_iter iter;
5695 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
5697 tree use = USE_FROM_PTR (use_p);
5698 /* ??? The call code above leaves stmt operands un-updated. */
5699 if (TREE_CODE (use) != SSA_NAME)
5700 continue;
5701 tree sprime = eliminate_avail (use);
5702 if (sprime && sprime != use
5703 && may_propagate_copy (use, sprime)
5704 /* We substitute into debug stmts to avoid excessive
5705 debug temporaries created by removed stmts, but we need
5706 to avoid doing so for inserted sprimes as we never want
5707 to create debug temporaries for them. */
5708 && (!inserted_exprs
5709 || TREE_CODE (sprime) != SSA_NAME
5710 || !is_gimple_debug (stmt)
5711 || !bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (sprime))))
5713 propagate_value (use_p, sprime);
5714 modified = true;
5718 /* Fold the stmt if modified, this canonicalizes MEM_REFs we propagated
5719 into which is a requirement for the IPA devirt machinery. */
5720 gimple *old_stmt = stmt;
5721 if (modified)
5723 /* If a formerly non-invariant ADDR_EXPR is turned into an
5724 invariant one it was on a separate stmt. */
5725 if (gimple_assign_single_p (stmt)
5726 && TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR)
5727 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
5728 gimple_stmt_iterator prev = gsi;
5729 gsi_prev (&prev);
5730 if (fold_stmt (&gsi))
5732 /* fold_stmt may have created new stmts inbetween
5733 the previous stmt and the folded stmt. Mark
5734 all defs created there as varying to not confuse
5735 the SCCVN machinery as we're using that even during
5736 elimination. */
5737 if (gsi_end_p (prev))
5738 prev = gsi_start_bb (b);
5739 else
5740 gsi_next (&prev);
5741 if (gsi_stmt (prev) != gsi_stmt (gsi))
5744 tree def;
5745 ssa_op_iter dit;
5746 FOR_EACH_SSA_TREE_OPERAND (def, gsi_stmt (prev),
5747 dit, SSA_OP_ALL_DEFS)
5748 /* As existing DEFs may move between stmts
5749 we have to guard VN_INFO_GET. */
5750 if (! has_VN_INFO (def))
5751 VN_INFO_GET (def)->valnum = def;
5752 if (gsi_stmt (prev) == gsi_stmt (gsi))
5753 break;
5754 gsi_next (&prev);
5756 while (1);
5758 stmt = gsi_stmt (gsi);
5759 /* In case we folded the stmt away schedule the NOP for removal. */
5760 if (gimple_nop_p (stmt))
5761 to_remove.safe_push (stmt);
5764 /* Visit indirect calls and turn them into direct calls if
5765 possible using the devirtualization machinery. Do this before
5766 checking for required EH/abnormal/noreturn cleanup as devird
5767 may expose more of those. */
5768 if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
5770 tree fn = gimple_call_fn (call_stmt);
5771 if (fn
5772 && flag_devirtualize
5773 && virtual_method_call_p (fn))
5775 tree otr_type = obj_type_ref_class (fn);
5776 unsigned HOST_WIDE_INT otr_tok
5777 = tree_to_uhwi (OBJ_TYPE_REF_TOKEN (fn));
5778 tree instance;
5779 ipa_polymorphic_call_context context (current_function_decl,
5780 fn, stmt, &instance);
5781 context.get_dynamic_type (instance, OBJ_TYPE_REF_OBJECT (fn),
5782 otr_type, stmt);
5783 bool final;
5784 vec <cgraph_node *> targets
5785 = possible_polymorphic_call_targets (obj_type_ref_class (fn),
5786 otr_tok, context, &final);
5787 if (dump_file)
5788 dump_possible_polymorphic_call_targets (dump_file,
5789 obj_type_ref_class (fn),
5790 otr_tok, context);
5791 if (final && targets.length () <= 1 && dbg_cnt (devirt))
5793 tree fn;
5794 if (targets.length () == 1)
5795 fn = targets[0]->decl;
5796 else
5797 fn = builtin_decl_implicit (BUILT_IN_UNREACHABLE);
5798 if (dump_enabled_p ())
5800 location_t loc = gimple_location (stmt);
5801 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
5802 "converting indirect call to "
5803 "function %s\n",
5804 lang_hooks.decl_printable_name (fn, 2));
5806 gimple_call_set_fndecl (call_stmt, fn);
5807 /* If changing the call to __builtin_unreachable
5808 or similar noreturn function, adjust gimple_call_fntype
5809 too. */
5810 if (gimple_call_noreturn_p (call_stmt)
5811 && VOID_TYPE_P (TREE_TYPE (TREE_TYPE (fn)))
5812 && TYPE_ARG_TYPES (TREE_TYPE (fn))
5813 && (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fn)))
5814 == void_type_node))
5815 gimple_call_set_fntype (call_stmt, TREE_TYPE (fn));
5816 maybe_remove_unused_call_args (cfun, call_stmt);
5817 modified = true;
5822 if (modified)
5824 /* When changing a call into a noreturn call, cfg cleanup
5825 is needed to fix up the noreturn call. */
5826 if (!was_noreturn
5827 && is_gimple_call (stmt) && gimple_call_noreturn_p (stmt))
5828 to_fixup.safe_push (stmt);
5829 /* When changing a condition or switch into one we know what
5830 edge will be executed, schedule a cfg cleanup. */
5831 if ((gimple_code (stmt) == GIMPLE_COND
5832 && (gimple_cond_true_p (as_a <gcond *> (stmt))
5833 || gimple_cond_false_p (as_a <gcond *> (stmt))))
5834 || (gimple_code (stmt) == GIMPLE_SWITCH
5835 && TREE_CODE (gimple_switch_index
5836 (as_a <gswitch *> (stmt))) == INTEGER_CST))
5837 el_todo |= TODO_cleanup_cfg;
5838 /* If we removed EH side-effects from the statement, clean
5839 its EH information. */
5840 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
5842 bitmap_set_bit (need_eh_cleanup,
5843 gimple_bb (stmt)->index);
5844 if (dump_file && (dump_flags & TDF_DETAILS))
5845 fprintf (dump_file, " Removed EH side-effects.\n");
5847 /* Likewise for AB side-effects. */
5848 if (can_make_abnormal_goto
5849 && !stmt_can_make_abnormal_goto (stmt))
5851 bitmap_set_bit (need_ab_cleanup,
5852 gimple_bb (stmt)->index);
5853 if (dump_file && (dump_flags & TDF_DETAILS))
5854 fprintf (dump_file, " Removed AB side-effects.\n");
5856 update_stmt (stmt);
5857 if (vdef != gimple_vdef (stmt))
5858 VN_INFO (vdef)->valnum = vuse;
5861 /* Make new values available - for fully redundant LHS we
5862 continue with the next stmt above and skip this. */
5863 def_operand_p defp;
5864 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_DEF)
5865 eliminate_push_avail (DEF_FROM_PTR (defp));
5868 /* Replace destination PHI arguments. */
5869 FOR_EACH_EDGE (e, ei, b->succs)
5870 if (e->flags & EDGE_EXECUTABLE)
5871 for (gphi_iterator gsi = gsi_start_phis (e->dest);
5872 !gsi_end_p (gsi);
5873 gsi_next (&gsi))
5875 gphi *phi = gsi.phi ();
5876 use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
5877 tree arg = USE_FROM_PTR (use_p);
5878 if (TREE_CODE (arg) != SSA_NAME
5879 || virtual_operand_p (arg))
5880 continue;
5881 tree sprime = eliminate_avail (arg);
5882 if (sprime && may_propagate_copy (arg, sprime))
5883 propagate_value (use_p, sprime);
5885 return NULL;
5888 /* Make no longer available leaders no longer available. */
5890 void
5891 eliminate_dom_walker::after_dom_children (basic_block)
5893 tree entry;
5894 while ((entry = avail_stack.pop ()) != NULL_TREE)
5896 tree valnum = VN_INFO (entry)->valnum;
5897 tree old = avail[SSA_NAME_VERSION (valnum)];
5898 if (old == entry)
5899 avail[SSA_NAME_VERSION (valnum)] = NULL_TREE;
5900 else
5901 avail[SSA_NAME_VERSION (valnum)] = entry;
5905 /* Eliminate fully redundant computations. */
5907 unsigned int
5908 vn_eliminate (bitmap inserted_exprs)
5910 eliminate_dom_walker el (CDI_DOMINATORS, inserted_exprs);
5911 el.avail.reserve (num_ssa_names);
5913 el.walk (cfun->cfg->x_entry_block_ptr);
5915 /* We cannot remove stmts during BB walk, especially not release SSA
5916 names there as this confuses the VN machinery. The stmts ending
5917 up in to_remove are either stores or simple copies.
5918 Remove stmts in reverse order to make debug stmt creation possible. */
5919 while (!el.to_remove.is_empty ())
5921 gimple *stmt = el.to_remove.pop ();
5923 if (dump_file && (dump_flags & TDF_DETAILS))
5925 fprintf (dump_file, "Removing dead stmt ");
5926 print_gimple_stmt (dump_file, stmt, 0, 0);
5929 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
5930 if (gimple_code (stmt) == GIMPLE_PHI)
5931 remove_phi_node (&gsi, true);
5932 else
5934 basic_block bb = gimple_bb (stmt);
5935 unlink_stmt_vdef (stmt);
5936 if (gsi_remove (&gsi, true))
5937 bitmap_set_bit (el.need_eh_cleanup, bb->index);
5938 if (is_gimple_call (stmt) && stmt_can_make_abnormal_goto (stmt))
5939 bitmap_set_bit (el.need_ab_cleanup, bb->index);
5940 release_defs (stmt);
5943 /* Removing a stmt may expose a forwarder block. */
5944 el.el_todo |= TODO_cleanup_cfg;
5947 /* Fixup stmts that became noreturn calls. This may require splitting
5948 blocks and thus isn't possible during the dominator walk. Do this
5949 in reverse order so we don't inadvertedly remove a stmt we want to
5950 fixup by visiting a dominating now noreturn call first. */
5951 while (!el.to_fixup.is_empty ())
5953 gimple *stmt = el.to_fixup.pop ();
5955 if (dump_file && (dump_flags & TDF_DETAILS))
5957 fprintf (dump_file, "Fixing up noreturn call ");
5958 print_gimple_stmt (dump_file, stmt, 0);
5961 if (fixup_noreturn_call (stmt))
5962 el.el_todo |= TODO_cleanup_cfg;
5965 bool do_eh_cleanup = !bitmap_empty_p (el.need_eh_cleanup);
5966 bool do_ab_cleanup = !bitmap_empty_p (el.need_ab_cleanup);
5968 if (do_eh_cleanup)
5969 gimple_purge_all_dead_eh_edges (el.need_eh_cleanup);
5971 if (do_ab_cleanup)
5972 gimple_purge_all_dead_abnormal_call_edges (el.need_ab_cleanup);
5974 if (do_eh_cleanup || do_ab_cleanup)
5975 el.el_todo |= TODO_cleanup_cfg;
5977 statistics_counter_event (cfun, "Eliminated", el.eliminations);
5978 statistics_counter_event (cfun, "Insertions", el.insertions);
5980 return el.el_todo;
5984 namespace {
5986 const pass_data pass_data_fre =
5988 GIMPLE_PASS, /* type */
5989 "fre", /* name */
5990 OPTGROUP_NONE, /* optinfo_flags */
5991 TV_TREE_FRE, /* tv_id */
5992 ( PROP_cfg | PROP_ssa ), /* properties_required */
5993 0, /* properties_provided */
5994 0, /* properties_destroyed */
5995 0, /* todo_flags_start */
5996 0, /* todo_flags_finish */
5999 class pass_fre : public gimple_opt_pass
6001 public:
6002 pass_fre (gcc::context *ctxt)
6003 : gimple_opt_pass (pass_data_fre, ctxt)
6006 /* opt_pass methods: */
6007 opt_pass * clone () { return new pass_fre (m_ctxt); }
6008 virtual bool gate (function *) { return flag_tree_fre != 0; }
6009 virtual unsigned int execute (function *);
6011 }; // class pass_fre
6013 unsigned int
6014 pass_fre::execute (function *)
6016 unsigned int todo = 0;
6018 run_scc_vn (VN_WALKREWRITE);
6020 /* Remove all the redundant expressions. */
6021 todo |= vn_eliminate (NULL);
6023 scc_vn_restore_ssa_info ();
6024 free_scc_vn ();
6026 return todo;
6029 } // anon namespace
6031 gimple_opt_pass *
6032 make_pass_fre (gcc::context *ctxt)
6034 return new pass_fre (ctxt);