1 /* SCC value numbering for trees
2 Copyright (C) 2006-2021 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)
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/>. */
23 #include "coretypes.h"
24 #include "splay-tree.h"
31 #include "insn-config.h"
35 #include "gimple-pretty-print.h"
37 #include "fold-const.h"
38 #include "stor-layout.h"
40 #include "tree-inline.h"
41 #include "internal-fn.h"
42 #include "gimple-fold.h"
56 #include "tree-ssa-propagate.h"
59 #include "gimple-iterator.h"
60 #include "gimple-match.h"
61 #include "stringpool.h"
63 #include "tree-pass.h"
64 #include "statistics.h"
65 #include "langhooks.h"
66 #include "ipa-utils.h"
68 #include "tree-cfgcleanup.h"
69 #include "tree-ssa-loop.h"
70 #include "tree-scalar-evolution.h"
71 #include "tree-ssa-loop-niter.h"
73 #include "tree-ssa-sccvn.h"
75 /* This algorithm is based on the SCC algorithm presented by Keith
76 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
77 (http://citeseer.ist.psu.edu/41805.html). In
78 straight line code, it is equivalent to a regular hash based value
79 numbering that is performed in reverse postorder.
81 For code with cycles, there are two alternatives, both of which
82 require keeping the hashtables separate from the actual list of
83 value numbers for SSA names.
85 1. Iterate value numbering in an RPO walk of the blocks, removing
86 all the entries from the hashtable after each iteration (but
87 keeping the SSA name->value number mapping between iterations).
88 Iterate until it does not change.
90 2. Perform value numbering as part of an SCC walk on the SSA graph,
91 iterating only the cycles in the SSA graph until they do not change
92 (using a separate, optimistic hashtable for value numbering the SCC
95 The second is not just faster in practice (because most SSA graph
96 cycles do not involve all the variables in the graph), it also has
99 One of these nice properties is that when we pop an SCC off the
100 stack, we are guaranteed to have processed all the operands coming from
101 *outside of that SCC*, so we do not need to do anything special to
102 ensure they have value numbers.
104 Another nice property is that the SCC walk is done as part of a DFS
105 of the SSA graph, which makes it easy to perform combining and
106 simplifying operations at the same time.
108 The code below is deliberately written in a way that makes it easy
109 to separate the SCC walk from the other work it does.
111 In order to propagate constants through the code, we track which
112 expressions contain constants, and use those while folding. In
113 theory, we could also track expressions whose value numbers are
114 replaced, in case we end up folding based on expression
117 In order to value number memory, we assign value numbers to vuses.
118 This enables us to note that, for example, stores to the same
119 address of the same value from the same starting memory states are
123 1. We can iterate only the changing portions of the SCC's, but
124 I have not seen an SCC big enough for this to be a win.
125 2. If you differentiate between phi nodes for loops and phi nodes
126 for if-then-else, you can properly consider phi nodes in different
127 blocks for equivalence.
128 3. We could value number vuses in more cases, particularly, whole
132 /* There's no BB_EXECUTABLE but we can use BB_VISITED. */
133 #define BB_EXECUTABLE BB_VISITED
135 static vn_lookup_kind default_vn_walk_kind
;
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. */
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
158 vn_nary_op_hasher::equal (const vn_nary_op_s
*vno1
, const vn_nary_op_s
*vno2
)
160 return vno1
== vno2
|| 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. */
170 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
);
172 struct vn_phi_hasher
: nofree_ptr_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
*);
178 /* Return the computed hashcode for phi operation P1. */
181 vn_phi_hasher::hash (const vn_phi_s
*vp1
)
183 return vp1
->hashcode
;
186 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
189 vn_phi_hasher::equal (const vn_phi_s
*vp1
, const vn_phi_s
*vp2
)
191 return vp1
== vp2
|| vn_phi_eq (vp1
, vp2
);
194 typedef hash_table
<vn_phi_hasher
> vn_phi_table_type
;
195 typedef vn_phi_table_type::iterator vn_phi_iterator_type
;
198 /* Compare two reference operands P1 and P2 for equality. Return true if
199 they are equal, and false otherwise. */
202 vn_reference_op_eq (const void *p1
, const void *p2
)
204 const_vn_reference_op_t
const vro1
= (const_vn_reference_op_t
) p1
;
205 const_vn_reference_op_t
const vro2
= (const_vn_reference_op_t
) p2
;
207 return (vro1
->opcode
== vro2
->opcode
208 /* We do not care for differences in type qualification. */
209 && (vro1
->type
== vro2
->type
210 || (vro1
->type
&& vro2
->type
211 && types_compatible_p (TYPE_MAIN_VARIANT (vro1
->type
),
212 TYPE_MAIN_VARIANT (vro2
->type
))))
213 && expressions_equal_p (vro1
->op0
, vro2
->op0
)
214 && expressions_equal_p (vro1
->op1
, vro2
->op1
)
215 && expressions_equal_p (vro1
->op2
, vro2
->op2
));
218 /* Free a reference operation structure VP. */
221 free_reference (vn_reference_s
*vr
)
223 vr
->operands
.release ();
227 /* vn_reference hashtable helpers. */
229 struct vn_reference_hasher
: nofree_ptr_hash
<vn_reference_s
>
231 static inline hashval_t
hash (const vn_reference_s
*);
232 static inline bool equal (const vn_reference_s
*, const vn_reference_s
*);
235 /* Return the hashcode for a given reference operation P1. */
238 vn_reference_hasher::hash (const vn_reference_s
*vr1
)
240 return vr1
->hashcode
;
244 vn_reference_hasher::equal (const vn_reference_s
*v
, const vn_reference_s
*c
)
246 return v
== c
|| vn_reference_eq (v
, c
);
249 typedef hash_table
<vn_reference_hasher
> vn_reference_table_type
;
250 typedef vn_reference_table_type::iterator vn_reference_iterator_type
;
253 /* The set of VN hashtables. */
255 typedef struct vn_tables_s
257 vn_nary_op_table_type
*nary
;
258 vn_phi_table_type
*phis
;
259 vn_reference_table_type
*references
;
263 /* vn_constant hashtable helpers. */
265 struct vn_constant_hasher
: free_ptr_hash
<vn_constant_s
>
267 static inline hashval_t
hash (const vn_constant_s
*);
268 static inline bool equal (const vn_constant_s
*, const vn_constant_s
*);
271 /* Hash table hash function for vn_constant_t. */
274 vn_constant_hasher::hash (const vn_constant_s
*vc1
)
276 return vc1
->hashcode
;
279 /* Hash table equality function for vn_constant_t. */
282 vn_constant_hasher::equal (const vn_constant_s
*vc1
, const vn_constant_s
*vc2
)
284 if (vc1
->hashcode
!= vc2
->hashcode
)
287 return vn_constant_eq_with_type (vc1
->constant
, vc2
->constant
);
290 static hash_table
<vn_constant_hasher
> *constant_to_value_id
;
293 /* Obstack we allocate the vn-tables elements from. */
294 static obstack vn_tables_obstack
;
295 /* Special obstack we never unwind. */
296 static obstack vn_tables_insert_obstack
;
298 static vn_reference_t last_inserted_ref
;
299 static vn_phi_t last_inserted_phi
;
300 static vn_nary_op_t last_inserted_nary
;
302 /* Valid hashtables storing information we have proven to be
304 static vn_tables_t valid_info
;
307 /* Valueization hook for simplify_replace_tree. Valueize NAME if it is
308 an SSA name, otherwise just return it. */
309 tree (*vn_valueize
) (tree
);
311 vn_valueize_for_srt (tree t
, void* context ATTRIBUTE_UNUSED
)
313 basic_block saved_vn_context_bb
= vn_context_bb
;
314 /* Look for sth available at the definition block of the argument.
315 This avoids inconsistencies between availability there which
316 decides if the stmt can be removed and availability at the
317 use site. The SSA property ensures that things available
318 at the definition are also available at uses. */
319 if (!SSA_NAME_IS_DEFAULT_DEF (t
))
320 vn_context_bb
= gimple_bb (SSA_NAME_DEF_STMT (t
));
321 tree res
= vn_valueize (t
);
322 vn_context_bb
= saved_vn_context_bb
;
327 /* This represents the top of the VN lattice, which is the universal
332 /* Unique counter for our value ids. */
334 static unsigned int next_value_id
;
335 static int next_constant_value_id
;
338 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
339 are allocated on an obstack for locality reasons, and to free them
340 without looping over the vec. */
342 struct vn_ssa_aux_hasher
: typed_noop_remove
<vn_ssa_aux_t
>
344 typedef vn_ssa_aux_t value_type
;
345 typedef tree compare_type
;
346 static inline hashval_t
hash (const value_type
&);
347 static inline bool equal (const value_type
&, const compare_type
&);
348 static inline void mark_deleted (value_type
&) {}
349 static const bool empty_zero_p
= true;
350 static inline void mark_empty (value_type
&e
) { e
= NULL
; }
351 static inline bool is_deleted (value_type
&) { return false; }
352 static inline bool is_empty (value_type
&e
) { return e
== NULL
; }
356 vn_ssa_aux_hasher::hash (const value_type
&entry
)
358 return SSA_NAME_VERSION (entry
->name
);
362 vn_ssa_aux_hasher::equal (const value_type
&entry
, const compare_type
&name
)
364 return name
== entry
->name
;
367 static hash_table
<vn_ssa_aux_hasher
> *vn_ssa_aux_hash
;
368 typedef hash_table
<vn_ssa_aux_hasher
>::iterator vn_ssa_aux_iterator_type
;
369 static struct obstack vn_ssa_aux_obstack
;
371 static vn_nary_op_t
vn_nary_op_insert_stmt (gimple
*, tree
);
372 static unsigned int vn_nary_length_from_stmt (gimple
*);
373 static vn_nary_op_t
alloc_vn_nary_op_noinit (unsigned int, obstack
*);
374 static vn_nary_op_t
vn_nary_op_insert_into (vn_nary_op_t
,
375 vn_nary_op_table_type
*, bool);
376 static void init_vn_nary_op_from_stmt (vn_nary_op_t
, gimple
*);
377 static void init_vn_nary_op_from_pieces (vn_nary_op_t
, unsigned int,
378 enum tree_code
, tree
, tree
*);
379 static tree
vn_lookup_simplify_result (gimple_match_op
*);
380 static vn_reference_t vn_reference_lookup_or_insert_for_pieces
381 (tree
, alias_set_type
, alias_set_type
, tree
,
382 vec
<vn_reference_op_s
, va_heap
>, tree
);
384 /* Return whether there is value numbering information for a given SSA name. */
387 has_VN_INFO (tree name
)
389 return vn_ssa_aux_hash
->find_with_hash (name
, SSA_NAME_VERSION (name
));
396 = vn_ssa_aux_hash
->find_slot_with_hash (name
, SSA_NAME_VERSION (name
),
401 vn_ssa_aux_t newinfo
= *res
= XOBNEW (&vn_ssa_aux_obstack
, struct vn_ssa_aux
);
402 memset (newinfo
, 0, sizeof (struct vn_ssa_aux
));
403 newinfo
->name
= name
;
404 newinfo
->valnum
= VN_TOP
;
405 /* We are using the visited flag to handle uses with defs not within the
406 region being value-numbered. */
407 newinfo
->visited
= false;
409 /* Given we create the VN_INFOs on-demand now we have to do initialization
410 different than VN_TOP here. */
411 if (SSA_NAME_IS_DEFAULT_DEF (name
))
412 switch (TREE_CODE (SSA_NAME_VAR (name
)))
415 /* All undefined vars are VARYING. */
416 newinfo
->valnum
= name
;
417 newinfo
->visited
= true;
421 /* Parameters are VARYING but we can record a condition
422 if we know it is a non-NULL pointer. */
423 newinfo
->visited
= true;
424 newinfo
->valnum
= name
;
425 if (POINTER_TYPE_P (TREE_TYPE (name
))
426 && nonnull_arg_p (SSA_NAME_VAR (name
)))
430 ops
[1] = build_int_cst (TREE_TYPE (name
), 0);
432 /* Allocate from non-unwinding stack. */
433 nary
= alloc_vn_nary_op_noinit (2, &vn_tables_insert_obstack
);
434 init_vn_nary_op_from_pieces (nary
, 2, NE_EXPR
,
435 boolean_type_node
, ops
);
436 nary
->predicated_values
= 0;
437 nary
->u
.result
= boolean_true_node
;
438 vn_nary_op_insert_into (nary
, valid_info
->nary
, true);
439 gcc_assert (nary
->unwind_to
== NULL
);
440 /* Also do not link it into the undo chain. */
441 last_inserted_nary
= nary
->next
;
442 nary
->next
= (vn_nary_op_t
)(void *)-1;
443 nary
= alloc_vn_nary_op_noinit (2, &vn_tables_insert_obstack
);
444 init_vn_nary_op_from_pieces (nary
, 2, EQ_EXPR
,
445 boolean_type_node
, ops
);
446 nary
->predicated_values
= 0;
447 nary
->u
.result
= boolean_false_node
;
448 vn_nary_op_insert_into (nary
, valid_info
->nary
, true);
449 gcc_assert (nary
->unwind_to
== NULL
);
450 last_inserted_nary
= nary
->next
;
451 nary
->next
= (vn_nary_op_t
)(void *)-1;
452 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
454 fprintf (dump_file
, "Recording ");
455 print_generic_expr (dump_file
, name
, TDF_SLIM
);
456 fprintf (dump_file
, " != 0\n");
462 /* If the result is passed by invisible reference the default
463 def is initialized, otherwise it's uninitialized. Still
464 undefined is varying. */
465 newinfo
->visited
= true;
466 newinfo
->valnum
= name
;
475 /* Return the SSA value of X. */
478 SSA_VAL (tree x
, bool *visited
= NULL
)
480 vn_ssa_aux_t tem
= vn_ssa_aux_hash
->find_with_hash (x
, SSA_NAME_VERSION (x
));
482 *visited
= tem
&& tem
->visited
;
483 return tem
&& tem
->visited
? tem
->valnum
: x
;
486 /* Return the SSA value of the VUSE x, supporting released VDEFs
487 during elimination which will value-number the VDEF to the
488 associated VUSE (but not substitute in the whole lattice). */
491 vuse_ssa_val (tree x
)
499 gcc_assert (x
!= VN_TOP
);
501 while (SSA_NAME_IN_FREE_LIST (x
));
506 /* Similar to the above but used as callback for walk_non_aliases_vuses
507 and thus should stop at unvisited VUSE to not walk across region
511 vuse_valueize (tree vuse
)
516 vuse
= SSA_VAL (vuse
, &visited
);
519 gcc_assert (vuse
!= VN_TOP
);
521 while (SSA_NAME_IN_FREE_LIST (vuse
));
526 /* Return the vn_kind the expression computed by the stmt should be
530 vn_get_stmt_kind (gimple
*stmt
)
532 switch (gimple_code (stmt
))
540 enum tree_code code
= gimple_assign_rhs_code (stmt
);
541 tree rhs1
= gimple_assign_rhs1 (stmt
);
542 switch (get_gimple_rhs_class (code
))
544 case GIMPLE_UNARY_RHS
:
545 case GIMPLE_BINARY_RHS
:
546 case GIMPLE_TERNARY_RHS
:
548 case GIMPLE_SINGLE_RHS
:
549 switch (TREE_CODE_CLASS (code
))
552 /* VOP-less references can go through unary case. */
553 if ((code
== REALPART_EXPR
554 || code
== IMAGPART_EXPR
555 || code
== VIEW_CONVERT_EXPR
556 || code
== BIT_FIELD_REF
)
557 && (TREE_CODE (TREE_OPERAND (rhs1
, 0)) == SSA_NAME
558 || is_gimple_min_invariant (TREE_OPERAND (rhs1
, 0))))
562 case tcc_declaration
:
569 if (code
== ADDR_EXPR
)
570 return (is_gimple_min_invariant (rhs1
)
571 ? VN_CONSTANT
: VN_REFERENCE
);
572 else if (code
== CONSTRUCTOR
)
585 /* Lookup a value id for CONSTANT and return it. If it does not
589 get_constant_value_id (tree constant
)
591 vn_constant_s
**slot
;
592 struct vn_constant_s vc
;
594 vc
.hashcode
= vn_hash_constant_with_type (constant
);
595 vc
.constant
= constant
;
596 slot
= constant_to_value_id
->find_slot (&vc
, NO_INSERT
);
598 return (*slot
)->value_id
;
602 /* Lookup a value id for CONSTANT, and if it does not exist, create a
603 new one and return it. If it does exist, return it. */
606 get_or_alloc_constant_value_id (tree constant
)
608 vn_constant_s
**slot
;
609 struct vn_constant_s vc
;
612 /* If the hashtable isn't initialized we're not running from PRE and thus
613 do not need value-ids. */
614 if (!constant_to_value_id
)
617 vc
.hashcode
= vn_hash_constant_with_type (constant
);
618 vc
.constant
= constant
;
619 slot
= constant_to_value_id
->find_slot (&vc
, INSERT
);
621 return (*slot
)->value_id
;
623 vcp
= XNEW (struct vn_constant_s
);
624 vcp
->hashcode
= vc
.hashcode
;
625 vcp
->constant
= constant
;
626 vcp
->value_id
= get_next_constant_value_id ();
628 return vcp
->value_id
;
631 /* Compute the hash for a reference operand VRO1. */
634 vn_reference_op_compute_hash (const vn_reference_op_t vro1
, inchash::hash
&hstate
)
636 hstate
.add_int (vro1
->opcode
);
638 inchash::add_expr (vro1
->op0
, hstate
);
640 inchash::add_expr (vro1
->op1
, hstate
);
642 inchash::add_expr (vro1
->op2
, hstate
);
645 /* Compute a hash for the reference operation VR1 and return it. */
648 vn_reference_compute_hash (const vn_reference_t vr1
)
650 inchash::hash hstate
;
653 vn_reference_op_t vro
;
657 FOR_EACH_VEC_ELT (vr1
->operands
, i
, vro
)
659 if (vro
->opcode
== MEM_REF
)
661 else if (vro
->opcode
!= ADDR_EXPR
)
663 if (maybe_ne (vro
->off
, -1))
665 if (known_eq (off
, -1))
671 if (maybe_ne (off
, -1)
672 && maybe_ne (off
, 0))
673 hstate
.add_poly_int (off
);
676 && vro
->opcode
== ADDR_EXPR
)
680 tree op
= TREE_OPERAND (vro
->op0
, 0);
681 hstate
.add_int (TREE_CODE (op
));
682 inchash::add_expr (op
, hstate
);
686 vn_reference_op_compute_hash (vro
, hstate
);
689 result
= hstate
.end ();
690 /* ??? We would ICE later if we hash instead of adding that in. */
692 result
+= SSA_NAME_VERSION (vr1
->vuse
);
697 /* Return true if reference operations VR1 and VR2 are equivalent. This
698 means they have the same set of operands and vuses. */
701 vn_reference_eq (const_vn_reference_t
const vr1
, const_vn_reference_t
const vr2
)
705 /* Early out if this is not a hash collision. */
706 if (vr1
->hashcode
!= vr2
->hashcode
)
709 /* The VOP needs to be the same. */
710 if (vr1
->vuse
!= vr2
->vuse
)
713 /* If the operands are the same we are done. */
714 if (vr1
->operands
== vr2
->operands
)
717 if (COMPLETE_TYPE_P (vr1
->type
) != COMPLETE_TYPE_P (vr2
->type
)
718 || (COMPLETE_TYPE_P (vr1
->type
)
719 && !expressions_equal_p (TYPE_SIZE (vr1
->type
),
720 TYPE_SIZE (vr2
->type
))))
723 if (INTEGRAL_TYPE_P (vr1
->type
)
724 && INTEGRAL_TYPE_P (vr2
->type
))
726 if (TYPE_PRECISION (vr1
->type
) != TYPE_PRECISION (vr2
->type
))
729 else if (INTEGRAL_TYPE_P (vr1
->type
)
730 && (TYPE_PRECISION (vr1
->type
)
731 != TREE_INT_CST_LOW (TYPE_SIZE (vr1
->type
))))
733 else if (INTEGRAL_TYPE_P (vr2
->type
)
734 && (TYPE_PRECISION (vr2
->type
)
735 != TREE_INT_CST_LOW (TYPE_SIZE (vr2
->type
))))
742 poly_int64 off1
= 0, off2
= 0;
743 vn_reference_op_t vro1
, vro2
;
744 vn_reference_op_s tem1
, tem2
;
745 bool deref1
= false, deref2
= false;
746 for (; vr1
->operands
.iterate (i
, &vro1
); i
++)
748 if (vro1
->opcode
== MEM_REF
)
750 /* Do not look through a storage order barrier. */
751 else if (vro1
->opcode
== VIEW_CONVERT_EXPR
&& vro1
->reverse
)
753 if (known_eq (vro1
->off
, -1))
757 for (; vr2
->operands
.iterate (j
, &vro2
); j
++)
759 if (vro2
->opcode
== MEM_REF
)
761 /* Do not look through a storage order barrier. */
762 else if (vro2
->opcode
== VIEW_CONVERT_EXPR
&& vro2
->reverse
)
764 if (known_eq (vro2
->off
, -1))
768 if (maybe_ne (off1
, off2
))
770 if (deref1
&& vro1
->opcode
== ADDR_EXPR
)
772 memset (&tem1
, 0, sizeof (tem1
));
773 tem1
.op0
= TREE_OPERAND (vro1
->op0
, 0);
774 tem1
.type
= TREE_TYPE (tem1
.op0
);
775 tem1
.opcode
= TREE_CODE (tem1
.op0
);
779 if (deref2
&& vro2
->opcode
== ADDR_EXPR
)
781 memset (&tem2
, 0, sizeof (tem2
));
782 tem2
.op0
= TREE_OPERAND (vro2
->op0
, 0);
783 tem2
.type
= TREE_TYPE (tem2
.op0
);
784 tem2
.opcode
= TREE_CODE (tem2
.op0
);
788 if (deref1
!= deref2
)
790 if (!vn_reference_op_eq (vro1
, vro2
))
795 while (vr1
->operands
.length () != i
796 || vr2
->operands
.length () != j
);
801 /* Copy the operations present in load/store REF into RESULT, a vector of
802 vn_reference_op_s's. */
805 copy_reference_ops_from_ref (tree ref
, vec
<vn_reference_op_s
> *result
)
807 /* For non-calls, store the information that makes up the address. */
811 vn_reference_op_s temp
;
813 memset (&temp
, 0, sizeof (temp
));
814 temp
.type
= TREE_TYPE (ref
);
815 temp
.opcode
= TREE_CODE (ref
);
821 temp
.op0
= TREE_OPERAND (ref
, 1);
824 temp
.op0
= TREE_OPERAND (ref
, 1);
828 /* The base address gets its own vn_reference_op_s structure. */
829 temp
.op0
= TREE_OPERAND (ref
, 1);
830 if (!mem_ref_offset (ref
).to_shwi (&temp
.off
))
832 temp
.clique
= MR_DEPENDENCE_CLIQUE (ref
);
833 temp
.base
= MR_DEPENDENCE_BASE (ref
);
834 temp
.reverse
= REF_REVERSE_STORAGE_ORDER (ref
);
837 /* The base address gets its own vn_reference_op_s structure. */
838 temp
.op0
= TMR_INDEX (ref
);
839 temp
.op1
= TMR_STEP (ref
);
840 temp
.op2
= TMR_OFFSET (ref
);
841 temp
.clique
= MR_DEPENDENCE_CLIQUE (ref
);
842 temp
.base
= MR_DEPENDENCE_BASE (ref
);
843 result
->safe_push (temp
);
844 memset (&temp
, 0, sizeof (temp
));
845 temp
.type
= NULL_TREE
;
846 temp
.opcode
= ERROR_MARK
;
847 temp
.op0
= TMR_INDEX2 (ref
);
851 /* Record bits, position and storage order. */
852 temp
.op0
= TREE_OPERAND (ref
, 1);
853 temp
.op1
= TREE_OPERAND (ref
, 2);
854 if (!multiple_p (bit_field_offset (ref
), BITS_PER_UNIT
, &temp
.off
))
856 temp
.reverse
= REF_REVERSE_STORAGE_ORDER (ref
);
859 /* The field decl is enough to unambiguously specify the field,
860 a matching type is not necessary and a mismatching type
861 is always a spurious difference. */
862 temp
.type
= NULL_TREE
;
863 temp
.op0
= TREE_OPERAND (ref
, 1);
864 temp
.op1
= TREE_OPERAND (ref
, 2);
866 tree this_offset
= component_ref_field_offset (ref
);
868 && poly_int_tree_p (this_offset
))
870 tree bit_offset
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
871 if (TREE_INT_CST_LOW (bit_offset
) % BITS_PER_UNIT
== 0)
874 = (wi::to_poly_offset (this_offset
)
875 + (wi::to_offset (bit_offset
) >> LOG2_BITS_PER_UNIT
));
876 /* Probibit value-numbering zero offset components
877 of addresses the same before the pass folding
878 __builtin_object_size had a chance to run
879 (checking cfun->after_inlining does the
881 if (TREE_CODE (orig
) != ADDR_EXPR
883 || cfun
->after_inlining
)
884 off
.to_shwi (&temp
.off
);
889 case ARRAY_RANGE_REF
:
892 tree eltype
= TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref
, 0)));
893 /* Record index as operand. */
894 temp
.op0
= TREE_OPERAND (ref
, 1);
895 /* Always record lower bounds and element size. */
896 temp
.op1
= array_ref_low_bound (ref
);
897 /* But record element size in units of the type alignment. */
898 temp
.op2
= TREE_OPERAND (ref
, 3);
899 temp
.align
= eltype
->type_common
.align
;
901 temp
.op2
= size_binop (EXACT_DIV_EXPR
, TYPE_SIZE_UNIT (eltype
),
902 size_int (TYPE_ALIGN_UNIT (eltype
)));
903 if (poly_int_tree_p (temp
.op0
)
904 && poly_int_tree_p (temp
.op1
)
905 && TREE_CODE (temp
.op2
) == INTEGER_CST
)
907 poly_offset_int off
= ((wi::to_poly_offset (temp
.op0
)
908 - wi::to_poly_offset (temp
.op1
))
909 * wi::to_offset (temp
.op2
)
910 * vn_ref_op_align_unit (&temp
));
911 off
.to_shwi (&temp
.off
);
916 if (DECL_HARD_REGISTER (ref
))
925 /* Canonicalize decls to MEM[&decl] which is what we end up with
926 when valueizing MEM[ptr] with ptr = &decl. */
927 temp
.opcode
= MEM_REF
;
928 temp
.op0
= build_int_cst (build_pointer_type (TREE_TYPE (ref
)), 0);
930 result
->safe_push (temp
);
931 temp
.opcode
= ADDR_EXPR
;
932 temp
.op0
= build1 (ADDR_EXPR
, TREE_TYPE (temp
.op0
), ref
);
933 temp
.type
= TREE_TYPE (temp
.op0
);
948 if (is_gimple_min_invariant (ref
))
954 /* These are only interesting for their operands, their
955 existence, and their type. They will never be the last
956 ref in the chain of references (IE they require an
957 operand), so we don't have to put anything
958 for op* as it will be handled by the iteration */
962 case VIEW_CONVERT_EXPR
:
964 temp
.reverse
= storage_order_barrier_p (ref
);
967 /* This is only interesting for its constant offset. */
968 temp
.off
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref
)));
973 result
->safe_push (temp
);
975 if (REFERENCE_CLASS_P (ref
)
976 || TREE_CODE (ref
) == MODIFY_EXPR
977 || TREE_CODE (ref
) == WITH_SIZE_EXPR
978 || (TREE_CODE (ref
) == ADDR_EXPR
979 && !is_gimple_min_invariant (ref
)))
980 ref
= TREE_OPERAND (ref
, 0);
986 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
987 operands in *OPS, the reference alias set SET and the reference type TYPE.
988 Return true if something useful was produced. */
991 ao_ref_init_from_vn_reference (ao_ref
*ref
,
992 alias_set_type set
, alias_set_type base_set
,
993 tree type
, vec
<vn_reference_op_s
> ops
)
995 vn_reference_op_t op
;
997 tree base
= NULL_TREE
;
999 poly_offset_int offset
= 0;
1000 poly_offset_int max_size
;
1001 poly_offset_int size
= -1;
1002 tree size_tree
= NULL_TREE
;
1004 /* First get the final access size from just the outermost expression. */
1006 if (op
->opcode
== COMPONENT_REF
)
1007 size_tree
= DECL_SIZE (op
->op0
);
1008 else if (op
->opcode
== BIT_FIELD_REF
)
1009 size_tree
= op
->op0
;
1012 machine_mode mode
= TYPE_MODE (type
);
1013 if (mode
== BLKmode
)
1014 size_tree
= TYPE_SIZE (type
);
1016 size
= GET_MODE_BITSIZE (mode
);
1018 if (size_tree
!= NULL_TREE
1019 && poly_int_tree_p (size_tree
))
1020 size
= wi::to_poly_offset (size_tree
);
1022 /* Initially, maxsize is the same as the accessed element size.
1023 In the following it will only grow (or become -1). */
1026 /* Compute cumulative bit-offset for nested component-refs and array-refs,
1027 and find the ultimate containing object. */
1028 FOR_EACH_VEC_ELT (ops
, i
, op
)
1032 /* These may be in the reference ops, but we cannot do anything
1033 sensible with them here. */
1035 /* Apart from ADDR_EXPR arguments to MEM_REF. */
1036 if (base
!= NULL_TREE
1037 && TREE_CODE (base
) == MEM_REF
1039 && DECL_P (TREE_OPERAND (op
->op0
, 0)))
1041 vn_reference_op_t pop
= &ops
[i
-1];
1042 base
= TREE_OPERAND (op
->op0
, 0);
1043 if (known_eq (pop
->off
, -1))
1049 offset
+= pop
->off
* BITS_PER_UNIT
;
1057 /* Record the base objects. */
1059 *op0_p
= build2 (MEM_REF
, op
->type
,
1060 NULL_TREE
, op
->op0
);
1061 MR_DEPENDENCE_CLIQUE (*op0_p
) = op
->clique
;
1062 MR_DEPENDENCE_BASE (*op0_p
) = op
->base
;
1063 op0_p
= &TREE_OPERAND (*op0_p
, 0);
1074 /* And now the usual component-reference style ops. */
1076 offset
+= wi::to_poly_offset (op
->op1
);
1081 tree field
= op
->op0
;
1082 /* We do not have a complete COMPONENT_REF tree here so we
1083 cannot use component_ref_field_offset. Do the interesting
1085 tree this_offset
= DECL_FIELD_OFFSET (field
);
1087 if (op
->op1
|| !poly_int_tree_p (this_offset
))
1091 poly_offset_int woffset
= (wi::to_poly_offset (this_offset
)
1092 << LOG2_BITS_PER_UNIT
);
1093 woffset
+= wi::to_offset (DECL_FIELD_BIT_OFFSET (field
));
1099 case ARRAY_RANGE_REF
:
1101 /* We recorded the lower bound and the element size. */
1102 if (!poly_int_tree_p (op
->op0
)
1103 || !poly_int_tree_p (op
->op1
)
1104 || TREE_CODE (op
->op2
) != INTEGER_CST
)
1108 poly_offset_int woffset
1109 = wi::sext (wi::to_poly_offset (op
->op0
)
1110 - wi::to_poly_offset (op
->op1
),
1111 TYPE_PRECISION (TREE_TYPE (op
->op0
)));
1112 woffset
*= wi::to_offset (op
->op2
) * vn_ref_op_align_unit (op
);
1113 woffset
<<= LOG2_BITS_PER_UNIT
;
1125 case VIEW_CONVERT_EXPR
:
1142 if (base
== NULL_TREE
)
1145 ref
->ref
= NULL_TREE
;
1147 ref
->ref_alias_set
= set
;
1148 ref
->base_alias_set
= base_set
;
1149 /* We discount volatiles from value-numbering elsewhere. */
1150 ref
->volatile_p
= false;
1152 if (!size
.to_shwi (&ref
->size
) || maybe_lt (ref
->size
, 0))
1160 if (!offset
.to_shwi (&ref
->offset
))
1167 if (!max_size
.to_shwi (&ref
->max_size
) || maybe_lt (ref
->max_size
, 0))
1173 /* Copy the operations present in load/store/call REF into RESULT, a vector of
1174 vn_reference_op_s's. */
1177 copy_reference_ops_from_call (gcall
*call
,
1178 vec
<vn_reference_op_s
> *result
)
1180 vn_reference_op_s temp
;
1182 tree lhs
= gimple_call_lhs (call
);
1185 /* If 2 calls have a different non-ssa lhs, vdef value numbers should be
1186 different. By adding the lhs here in the vector, we ensure that the
1187 hashcode is different, guaranteeing a different value number. */
1188 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
1190 memset (&temp
, 0, sizeof (temp
));
1191 temp
.opcode
= MODIFY_EXPR
;
1192 temp
.type
= TREE_TYPE (lhs
);
1195 result
->safe_push (temp
);
1198 /* Copy the type, opcode, function, static chain and EH region, if any. */
1199 memset (&temp
, 0, sizeof (temp
));
1200 temp
.type
= gimple_call_fntype (call
);
1201 temp
.opcode
= CALL_EXPR
;
1202 temp
.op0
= gimple_call_fn (call
);
1203 temp
.op1
= gimple_call_chain (call
);
1204 if (stmt_could_throw_p (cfun
, call
) && (lr
= lookup_stmt_eh_lp (call
)) > 0)
1205 temp
.op2
= size_int (lr
);
1207 result
->safe_push (temp
);
1209 /* Copy the call arguments. As they can be references as well,
1210 just chain them together. */
1211 for (i
= 0; i
< gimple_call_num_args (call
); ++i
)
1213 tree callarg
= gimple_call_arg (call
, i
);
1214 copy_reference_ops_from_ref (callarg
, result
);
1218 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1219 *I_P to point to the last element of the replacement. */
1221 vn_reference_fold_indirect (vec
<vn_reference_op_s
> *ops
,
1224 unsigned int i
= *i_p
;
1225 vn_reference_op_t op
= &(*ops
)[i
];
1226 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1228 poly_int64 addr_offset
= 0;
1230 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1231 from .foo.bar to the preceding MEM_REF offset and replace the
1232 address with &OBJ. */
1233 addr_base
= get_addr_base_and_unit_offset_1 (TREE_OPERAND (op
->op0
, 0),
1234 &addr_offset
, vn_valueize
);
1235 gcc_checking_assert (addr_base
&& TREE_CODE (addr_base
) != MEM_REF
);
1236 if (addr_base
!= TREE_OPERAND (op
->op0
, 0))
1239 = (poly_offset_int::from (wi::to_poly_wide (mem_op
->op0
),
1242 mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1243 op
->op0
= build_fold_addr_expr (addr_base
);
1244 if (tree_fits_shwi_p (mem_op
->op0
))
1245 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1253 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1254 *I_P to point to the last element of the replacement. */
1256 vn_reference_maybe_forwprop_address (vec
<vn_reference_op_s
> *ops
,
1259 bool changed
= false;
1260 vn_reference_op_t op
;
1264 unsigned int i
= *i_p
;
1266 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1268 enum tree_code code
;
1269 poly_offset_int off
;
1271 def_stmt
= SSA_NAME_DEF_STMT (op
->op0
);
1272 if (!is_gimple_assign (def_stmt
))
1275 code
= gimple_assign_rhs_code (def_stmt
);
1276 if (code
!= ADDR_EXPR
1277 && code
!= POINTER_PLUS_EXPR
)
1280 off
= poly_offset_int::from (wi::to_poly_wide (mem_op
->op0
), SIGNED
);
1282 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1283 from .foo.bar to the preceding MEM_REF offset and replace the
1284 address with &OBJ. */
1285 if (code
== ADDR_EXPR
)
1287 tree addr
, addr_base
;
1288 poly_int64 addr_offset
;
1290 addr
= gimple_assign_rhs1 (def_stmt
);
1291 addr_base
= get_addr_base_and_unit_offset_1 (TREE_OPERAND (addr
, 0),
1294 /* If that didn't work because the address isn't invariant propagate
1295 the reference tree from the address operation in case the current
1296 dereference isn't offsetted. */
1298 && *i_p
== ops
->length () - 1
1299 && known_eq (off
, 0)
1300 /* This makes us disable this transform for PRE where the
1301 reference ops might be also used for code insertion which
1303 && default_vn_walk_kind
== VN_WALKREWRITE
)
1305 auto_vec
<vn_reference_op_s
, 32> tem
;
1306 copy_reference_ops_from_ref (TREE_OPERAND (addr
, 0), &tem
);
1307 /* Make sure to preserve TBAA info. The only objects not
1308 wrapped in MEM_REFs that can have their address taken are
1310 if (tem
.length () >= 2
1311 && tem
[tem
.length () - 2].opcode
== MEM_REF
)
1313 vn_reference_op_t new_mem_op
= &tem
[tem
.length () - 2];
1315 = wide_int_to_tree (TREE_TYPE (mem_op
->op0
),
1316 wi::to_poly_wide (new_mem_op
->op0
));
1319 gcc_assert (tem
.last ().opcode
== STRING_CST
);
1322 ops
->safe_splice (tem
);
1327 || TREE_CODE (addr_base
) != MEM_REF
1328 || (TREE_CODE (TREE_OPERAND (addr_base
, 0)) == SSA_NAME
1329 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (addr_base
,
1334 off
+= mem_ref_offset (addr_base
);
1335 op
->op0
= TREE_OPERAND (addr_base
, 0);
1340 ptr
= gimple_assign_rhs1 (def_stmt
);
1341 ptroff
= gimple_assign_rhs2 (def_stmt
);
1342 if (TREE_CODE (ptr
) != SSA_NAME
1343 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
)
1344 /* Make sure to not endlessly recurse.
1345 See gcc.dg/tree-ssa/20040408-1.c for an example. Can easily
1346 happen when we value-number a PHI to its backedge value. */
1347 || SSA_VAL (ptr
) == op
->op0
1348 || !poly_int_tree_p (ptroff
))
1351 off
+= wi::to_poly_offset (ptroff
);
1355 mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1356 if (tree_fits_shwi_p (mem_op
->op0
))
1357 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1360 /* ??? Can end up with endless recursion here!?
1361 gcc.c-torture/execute/strcmp-1.c */
1362 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1363 op
->op0
= SSA_VAL (op
->op0
);
1364 if (TREE_CODE (op
->op0
) != SSA_NAME
)
1365 op
->opcode
= TREE_CODE (op
->op0
);
1370 while (TREE_CODE (op
->op0
) == SSA_NAME
);
1372 /* Fold a remaining *&. */
1373 if (TREE_CODE (op
->op0
) == ADDR_EXPR
)
1374 vn_reference_fold_indirect (ops
, i_p
);
1379 /* Optimize the reference REF to a constant if possible or return
1380 NULL_TREE if not. */
1383 fully_constant_vn_reference_p (vn_reference_t ref
)
1385 vec
<vn_reference_op_s
> operands
= ref
->operands
;
1386 vn_reference_op_t op
;
1388 /* Try to simplify the translated expression if it is
1389 a call to a builtin function with at most two arguments. */
1391 if (op
->opcode
== CALL_EXPR
1392 && TREE_CODE (op
->op0
) == ADDR_EXPR
1393 && TREE_CODE (TREE_OPERAND (op
->op0
, 0)) == FUNCTION_DECL
1394 && fndecl_built_in_p (TREE_OPERAND (op
->op0
, 0))
1395 && operands
.length () >= 2
1396 && operands
.length () <= 3)
1398 vn_reference_op_t arg0
, arg1
= NULL
;
1399 bool anyconst
= false;
1400 arg0
= &operands
[1];
1401 if (operands
.length () > 2)
1402 arg1
= &operands
[2];
1403 if (TREE_CODE_CLASS (arg0
->opcode
) == tcc_constant
1404 || (arg0
->opcode
== ADDR_EXPR
1405 && is_gimple_min_invariant (arg0
->op0
)))
1408 && (TREE_CODE_CLASS (arg1
->opcode
) == tcc_constant
1409 || (arg1
->opcode
== ADDR_EXPR
1410 && is_gimple_min_invariant (arg1
->op0
))))
1414 tree folded
= build_call_expr (TREE_OPERAND (op
->op0
, 0),
1417 arg1
? arg1
->op0
: NULL
);
1419 && TREE_CODE (folded
) == NOP_EXPR
)
1420 folded
= TREE_OPERAND (folded
, 0);
1422 && is_gimple_min_invariant (folded
))
1427 /* Simplify reads from constants or constant initializers. */
1428 else if (BITS_PER_UNIT
== 8
1429 && COMPLETE_TYPE_P (ref
->type
)
1430 && is_gimple_reg_type (ref
->type
))
1434 if (INTEGRAL_TYPE_P (ref
->type
))
1435 size
= TYPE_PRECISION (ref
->type
);
1436 else if (tree_fits_shwi_p (TYPE_SIZE (ref
->type
)))
1437 size
= tree_to_shwi (TYPE_SIZE (ref
->type
));
1440 if (size
% BITS_PER_UNIT
!= 0
1441 || size
> MAX_BITSIZE_MODE_ANY_MODE
)
1443 size
/= BITS_PER_UNIT
;
1445 for (i
= 0; i
< operands
.length (); ++i
)
1447 if (TREE_CODE_CLASS (operands
[i
].opcode
) == tcc_constant
)
1452 if (known_eq (operands
[i
].off
, -1))
1454 off
+= operands
[i
].off
;
1455 if (operands
[i
].opcode
== MEM_REF
)
1461 vn_reference_op_t base
= &operands
[--i
];
1462 tree ctor
= error_mark_node
;
1463 tree decl
= NULL_TREE
;
1464 if (TREE_CODE_CLASS (base
->opcode
) == tcc_constant
)
1466 else if (base
->opcode
== MEM_REF
1467 && base
[1].opcode
== ADDR_EXPR
1468 && (TREE_CODE (TREE_OPERAND (base
[1].op0
, 0)) == VAR_DECL
1469 || TREE_CODE (TREE_OPERAND (base
[1].op0
, 0)) == CONST_DECL
1470 || TREE_CODE (TREE_OPERAND (base
[1].op0
, 0)) == STRING_CST
))
1472 decl
= TREE_OPERAND (base
[1].op0
, 0);
1473 if (TREE_CODE (decl
) == STRING_CST
)
1476 ctor
= ctor_for_folding (decl
);
1478 if (ctor
== NULL_TREE
)
1479 return build_zero_cst (ref
->type
);
1480 else if (ctor
!= error_mark_node
)
1482 HOST_WIDE_INT const_off
;
1485 tree res
= fold_ctor_reference (ref
->type
, ctor
,
1486 off
* BITS_PER_UNIT
,
1487 size
* BITS_PER_UNIT
, decl
);
1490 STRIP_USELESS_TYPE_CONVERSION (res
);
1491 if (is_gimple_min_invariant (res
))
1495 else if (off
.is_constant (&const_off
))
1497 unsigned char buf
[MAX_BITSIZE_MODE_ANY_MODE
/ BITS_PER_UNIT
];
1498 int len
= native_encode_expr (ctor
, buf
, size
, const_off
);
1500 return native_interpret_expr (ref
->type
, buf
, len
);
1508 /* Return true if OPS contain a storage order barrier. */
1511 contains_storage_order_barrier_p (vec
<vn_reference_op_s
> ops
)
1513 vn_reference_op_t op
;
1516 FOR_EACH_VEC_ELT (ops
, i
, op
)
1517 if (op
->opcode
== VIEW_CONVERT_EXPR
&& op
->reverse
)
1523 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1524 structures into their value numbers. This is done in-place, and
1525 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1526 whether any operands were valueized. */
1528 static vec
<vn_reference_op_s
>
1529 valueize_refs_1 (vec
<vn_reference_op_s
> orig
, bool *valueized_anything
,
1530 bool with_avail
= false)
1532 vn_reference_op_t vro
;
1535 *valueized_anything
= false;
1537 FOR_EACH_VEC_ELT (orig
, i
, vro
)
1539 if (vro
->opcode
== SSA_NAME
1540 || (vro
->op0
&& TREE_CODE (vro
->op0
) == SSA_NAME
))
1542 tree tem
= with_avail
? vn_valueize (vro
->op0
) : SSA_VAL (vro
->op0
);
1543 if (tem
!= vro
->op0
)
1545 *valueized_anything
= true;
1548 /* If it transforms from an SSA_NAME to a constant, update
1550 if (TREE_CODE (vro
->op0
) != SSA_NAME
&& vro
->opcode
== SSA_NAME
)
1551 vro
->opcode
= TREE_CODE (vro
->op0
);
1553 if (vro
->op1
&& TREE_CODE (vro
->op1
) == SSA_NAME
)
1555 tree tem
= with_avail
? vn_valueize (vro
->op1
) : SSA_VAL (vro
->op1
);
1556 if (tem
!= vro
->op1
)
1558 *valueized_anything
= true;
1562 if (vro
->op2
&& TREE_CODE (vro
->op2
) == SSA_NAME
)
1564 tree tem
= with_avail
? vn_valueize (vro
->op2
) : SSA_VAL (vro
->op2
);
1565 if (tem
!= vro
->op2
)
1567 *valueized_anything
= true;
1571 /* If it transforms from an SSA_NAME to an address, fold with
1572 a preceding indirect reference. */
1575 && TREE_CODE (vro
->op0
) == ADDR_EXPR
1576 && orig
[i
- 1].opcode
== MEM_REF
)
1578 if (vn_reference_fold_indirect (&orig
, &i
))
1579 *valueized_anything
= true;
1582 && vro
->opcode
== SSA_NAME
1583 && orig
[i
- 1].opcode
== MEM_REF
)
1585 if (vn_reference_maybe_forwprop_address (&orig
, &i
))
1586 *valueized_anything
= true;
1588 /* If it transforms a non-constant ARRAY_REF into a constant
1589 one, adjust the constant offset. */
1590 else if (vro
->opcode
== ARRAY_REF
1591 && known_eq (vro
->off
, -1)
1592 && poly_int_tree_p (vro
->op0
)
1593 && poly_int_tree_p (vro
->op1
)
1594 && TREE_CODE (vro
->op2
) == INTEGER_CST
)
1596 poly_offset_int off
= ((wi::to_poly_offset (vro
->op0
)
1597 - wi::to_poly_offset (vro
->op1
))
1598 * wi::to_offset (vro
->op2
)
1599 * vn_ref_op_align_unit (vro
));
1600 off
.to_shwi (&vro
->off
);
1607 static vec
<vn_reference_op_s
>
1608 valueize_refs (vec
<vn_reference_op_s
> orig
)
1611 return valueize_refs_1 (orig
, &tem
);
1614 static vec
<vn_reference_op_s
> shared_lookup_references
;
1616 /* Create a vector of vn_reference_op_s structures from REF, a
1617 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1618 this function. *VALUEIZED_ANYTHING will specify whether any
1619 operands were valueized. */
1621 static vec
<vn_reference_op_s
>
1622 valueize_shared_reference_ops_from_ref (tree ref
, bool *valueized_anything
)
1626 shared_lookup_references
.truncate (0);
1627 copy_reference_ops_from_ref (ref
, &shared_lookup_references
);
1628 shared_lookup_references
= valueize_refs_1 (shared_lookup_references
,
1629 valueized_anything
);
1630 return shared_lookup_references
;
1633 /* Create a vector of vn_reference_op_s structures from CALL, a
1634 call statement. The vector is shared among all callers of
1637 static vec
<vn_reference_op_s
>
1638 valueize_shared_reference_ops_from_call (gcall
*call
)
1642 shared_lookup_references
.truncate (0);
1643 copy_reference_ops_from_call (call
, &shared_lookup_references
);
1644 shared_lookup_references
= valueize_refs (shared_lookup_references
);
1645 return shared_lookup_references
;
1648 /* Lookup a SCCVN reference operation VR in the current hash table.
1649 Returns the resulting value number if it exists in the hash table,
1650 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1651 vn_reference_t stored in the hashtable if something is found. */
1654 vn_reference_lookup_1 (vn_reference_t vr
, vn_reference_t
*vnresult
)
1656 vn_reference_s
**slot
;
1659 hash
= vr
->hashcode
;
1660 slot
= valid_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1664 *vnresult
= (vn_reference_t
)*slot
;
1665 return ((vn_reference_t
)*slot
)->result
;
1672 /* Partial definition tracking support. */
1676 HOST_WIDE_INT offset
;
1683 HOST_WIDE_INT offset
;
1687 /* Context for alias walking. */
1689 struct vn_walk_cb_data
1691 vn_walk_cb_data (vn_reference_t vr_
, tree orig_ref_
, tree
*last_vuse_ptr_
,
1692 vn_lookup_kind vn_walk_kind_
, bool tbaa_p_
, tree mask_
)
1693 : vr (vr_
), last_vuse_ptr (last_vuse_ptr_
), last_vuse (NULL_TREE
),
1694 mask (mask_
), masked_result (NULL_TREE
), vn_walk_kind (vn_walk_kind_
),
1695 tbaa_p (tbaa_p_
), saved_operands (vNULL
), first_set (-2),
1696 first_base_set (-2), known_ranges (NULL
)
1699 last_vuse_ptr
= &last_vuse
;
1700 ao_ref_init (&orig_ref
, orig_ref_
);
1703 wide_int w
= wi::to_wide (mask
);
1704 unsigned int pos
= 0, prec
= w
.get_precision ();
1706 pd
.rhs
= build_constructor (NULL_TREE
, NULL
);
1707 /* When bitwise and with a constant is done on a memory load,
1708 we don't really need all the bits to be defined or defined
1709 to constants, we don't really care what is in the position
1710 corresponding to 0 bits in the mask.
1711 So, push the ranges of those 0 bits in the mask as artificial
1712 zero stores and let the partial def handling code do the
1716 int tz
= wi::ctz (w
);
1717 if (pos
+ tz
> prec
)
1721 if (BYTES_BIG_ENDIAN
)
1722 pd
.offset
= prec
- pos
- tz
;
1726 void *r
= push_partial_def (pd
, 0, 0, 0, prec
);
1727 gcc_assert (r
== NULL_TREE
);
1732 w
= wi::lrshift (w
, tz
);
1733 tz
= wi::ctz (wi::bit_not (w
));
1734 if (pos
+ tz
> prec
)
1737 w
= wi::lrshift (w
, tz
);
1741 ~vn_walk_cb_data ();
1742 void *finish (alias_set_type
, alias_set_type
, tree
);
1743 void *push_partial_def (pd_data pd
,
1744 alias_set_type
, alias_set_type
, HOST_WIDE_INT
,
1749 tree
*last_vuse_ptr
;
1753 vn_lookup_kind vn_walk_kind
;
1755 vec
<vn_reference_op_s
> saved_operands
;
1757 /* The VDEFs of partial defs we come along. */
1758 auto_vec
<pd_data
, 2> partial_defs
;
1759 /* The first defs range to avoid splay tree setup in most cases. */
1760 pd_range first_range
;
1761 alias_set_type first_set
;
1762 alias_set_type first_base_set
;
1763 splay_tree known_ranges
;
1764 obstack ranges_obstack
;
1767 vn_walk_cb_data::~vn_walk_cb_data ()
1771 splay_tree_delete (known_ranges
);
1772 obstack_free (&ranges_obstack
, NULL
);
1774 saved_operands
.release ();
1778 vn_walk_cb_data::finish (alias_set_type set
, alias_set_type base_set
, tree val
)
1780 if (first_set
!= -2)
1783 base_set
= first_base_set
;
1787 masked_result
= val
;
1790 vec
<vn_reference_op_s
> &operands
1791 = saved_operands
.exists () ? saved_operands
: vr
->operands
;
1792 return vn_reference_lookup_or_insert_for_pieces (last_vuse
, set
, base_set
,
1793 vr
->type
, operands
, val
);
1796 /* pd_range splay-tree helpers. */
1799 pd_range_compare (splay_tree_key offset1p
, splay_tree_key offset2p
)
1801 HOST_WIDE_INT offset1
= *(HOST_WIDE_INT
*)offset1p
;
1802 HOST_WIDE_INT offset2
= *(HOST_WIDE_INT
*)offset2p
;
1803 if (offset1
< offset2
)
1805 else if (offset1
> offset2
)
1811 pd_tree_alloc (int size
, void *data_
)
1813 vn_walk_cb_data
*data
= (vn_walk_cb_data
*)data_
;
1814 return obstack_alloc (&data
->ranges_obstack
, size
);
1818 pd_tree_dealloc (void *, void *)
1822 /* Push PD to the vector of partial definitions returning a
1823 value when we are ready to combine things with VUSE, SET and MAXSIZEI,
1824 NULL when we want to continue looking for partial defs or -1
1828 vn_walk_cb_data::push_partial_def (pd_data pd
,
1829 alias_set_type set
, alias_set_type base_set
,
1830 HOST_WIDE_INT offseti
,
1831 HOST_WIDE_INT maxsizei
)
1833 const HOST_WIDE_INT bufsize
= 64;
1834 /* We're using a fixed buffer for encoding so fail early if the object
1835 we want to interpret is bigger. */
1836 if (maxsizei
> bufsize
* BITS_PER_UNIT
1838 || BITS_PER_UNIT
!= 8
1839 /* Not prepared to handle PDP endian. */
1840 || BYTES_BIG_ENDIAN
!= WORDS_BIG_ENDIAN
)
1843 /* Turn too large constant stores into non-constant stores. */
1844 if (CONSTANT_CLASS_P (pd
.rhs
) && pd
.size
> bufsize
* BITS_PER_UNIT
)
1845 pd
.rhs
= error_mark_node
;
1847 /* And for non-constant or CONSTRUCTOR stores shrink them to only keep at
1848 most a partial byte before and/or after the region. */
1849 if (!CONSTANT_CLASS_P (pd
.rhs
))
1851 if (pd
.offset
< offseti
)
1853 HOST_WIDE_INT o
= ROUND_DOWN (offseti
- pd
.offset
, BITS_PER_UNIT
);
1854 gcc_assert (pd
.size
> o
);
1858 if (pd
.size
> maxsizei
)
1859 pd
.size
= maxsizei
+ ((pd
.size
- maxsizei
) % BITS_PER_UNIT
);
1862 pd
.offset
-= offseti
;
1864 bool pd_constant_p
= (TREE_CODE (pd
.rhs
) == CONSTRUCTOR
1865 || CONSTANT_CLASS_P (pd
.rhs
));
1866 if (partial_defs
.is_empty ())
1868 /* If we get a clobber upfront, fail. */
1869 if (TREE_CLOBBER_P (pd
.rhs
))
1873 partial_defs
.safe_push (pd
);
1874 first_range
.offset
= pd
.offset
;
1875 first_range
.size
= pd
.size
;
1877 first_base_set
= base_set
;
1878 last_vuse_ptr
= NULL
;
1879 /* Continue looking for partial defs. */
1885 /* ??? Optimize the case where the 2nd partial def completes things. */
1886 gcc_obstack_init (&ranges_obstack
);
1887 known_ranges
= splay_tree_new_with_allocator (pd_range_compare
, 0, 0,
1889 pd_tree_dealloc
, this);
1890 splay_tree_insert (known_ranges
,
1891 (splay_tree_key
)&first_range
.offset
,
1892 (splay_tree_value
)&first_range
);
1895 pd_range newr
= { pd
.offset
, pd
.size
};
1898 /* Lookup the predecessor of offset + 1 and see if we need to merge. */
1899 HOST_WIDE_INT loffset
= newr
.offset
+ 1;
1900 if ((n
= splay_tree_predecessor (known_ranges
, (splay_tree_key
)&loffset
))
1901 && ((r
= (pd_range
*)n
->value
), true)
1902 && ranges_known_overlap_p (r
->offset
, r
->size
+ 1,
1903 newr
.offset
, newr
.size
))
1905 /* Ignore partial defs already covered. Here we also drop shadowed
1906 clobbers arriving here at the floor. */
1907 if (known_subrange_p (newr
.offset
, newr
.size
, r
->offset
, r
->size
))
1909 r
->size
= MAX (r
->offset
+ r
->size
, newr
.offset
+ newr
.size
) - r
->offset
;
1913 /* newr.offset wasn't covered yet, insert the range. */
1914 r
= XOBNEW (&ranges_obstack
, pd_range
);
1916 splay_tree_insert (known_ranges
, (splay_tree_key
)&r
->offset
,
1917 (splay_tree_value
)r
);
1919 /* Merge r which now contains newr and is a member of the splay tree with
1920 adjacent overlapping ranges. */
1922 while ((n
= splay_tree_successor (known_ranges
, (splay_tree_key
)&r
->offset
))
1923 && ((rafter
= (pd_range
*)n
->value
), true)
1924 && ranges_known_overlap_p (r
->offset
, r
->size
+ 1,
1925 rafter
->offset
, rafter
->size
))
1927 r
->size
= MAX (r
->offset
+ r
->size
,
1928 rafter
->offset
+ rafter
->size
) - r
->offset
;
1929 splay_tree_remove (known_ranges
, (splay_tree_key
)&rafter
->offset
);
1931 /* If we get a clobber, fail. */
1932 if (TREE_CLOBBER_P (pd
.rhs
))
1934 /* Non-constants are OK as long as they are shadowed by a constant. */
1937 partial_defs
.safe_push (pd
);
1939 /* Now we have merged newr into the range tree. When we have covered
1940 [offseti, sizei] then the tree will contain exactly one node which has
1941 the desired properties and it will be 'r'. */
1942 if (!known_subrange_p (0, maxsizei
, r
->offset
, r
->size
))
1943 /* Continue looking for partial defs. */
1946 /* Now simply native encode all partial defs in reverse order. */
1947 unsigned ndefs
= partial_defs
.length ();
1948 /* We support up to 512-bit values (for V8DFmode). */
1949 unsigned char buffer
[bufsize
+ 1];
1950 unsigned char this_buffer
[bufsize
+ 1];
1953 memset (buffer
, 0, bufsize
+ 1);
1954 unsigned needed_len
= ROUND_UP (maxsizei
, BITS_PER_UNIT
) / BITS_PER_UNIT
;
1955 while (!partial_defs
.is_empty ())
1957 pd_data pd
= partial_defs
.pop ();
1959 if (TREE_CODE (pd
.rhs
) == CONSTRUCTOR
)
1961 /* Empty CONSTRUCTOR. */
1962 if (pd
.size
>= needed_len
* BITS_PER_UNIT
)
1965 len
= ROUND_UP (pd
.size
, BITS_PER_UNIT
) / BITS_PER_UNIT
;
1966 memset (this_buffer
, 0, len
);
1970 len
= native_encode_expr (pd
.rhs
, this_buffer
, bufsize
,
1971 MAX (0, -pd
.offset
) / BITS_PER_UNIT
);
1973 || len
< (ROUND_UP (pd
.size
, BITS_PER_UNIT
) / BITS_PER_UNIT
1974 - MAX (0, -pd
.offset
) / BITS_PER_UNIT
))
1976 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1977 fprintf (dump_file
, "Failed to encode %u "
1978 "partial definitions\n", ndefs
);
1983 unsigned char *p
= buffer
;
1984 HOST_WIDE_INT size
= pd
.size
;
1986 size
-= ROUND_DOWN (-pd
.offset
, BITS_PER_UNIT
);
1987 this_buffer
[len
] = 0;
1988 if (BYTES_BIG_ENDIAN
)
1990 /* LSB of this_buffer[len - 1] byte should be at
1991 pd.offset + pd.size - 1 bits in buffer. */
1992 amnt
= ((unsigned HOST_WIDE_INT
) pd
.offset
1993 + pd
.size
) % BITS_PER_UNIT
;
1995 shift_bytes_in_array_right (this_buffer
, len
+ 1, amnt
);
1996 unsigned char *q
= this_buffer
;
1997 unsigned int off
= 0;
2001 off
= pd
.offset
/ BITS_PER_UNIT
;
2002 gcc_assert (off
< needed_len
);
2006 msk
= ((1 << size
) - 1) << (BITS_PER_UNIT
- amnt
);
2007 *p
= (*p
& ~msk
) | (this_buffer
[len
] & msk
);
2012 if (TREE_CODE (pd
.rhs
) != CONSTRUCTOR
)
2013 q
= (this_buffer
+ len
2014 - (ROUND_UP (size
- amnt
, BITS_PER_UNIT
)
2016 if (pd
.offset
% BITS_PER_UNIT
)
2018 msk
= -1U << (BITS_PER_UNIT
2019 - (pd
.offset
% BITS_PER_UNIT
));
2020 *p
= (*p
& msk
) | (*q
& ~msk
);
2024 size
-= BITS_PER_UNIT
- (pd
.offset
% BITS_PER_UNIT
);
2025 gcc_assert (size
>= 0);
2029 else if (TREE_CODE (pd
.rhs
) != CONSTRUCTOR
)
2031 q
= (this_buffer
+ len
2032 - (ROUND_UP (size
- amnt
, BITS_PER_UNIT
)
2034 if (pd
.offset
% BITS_PER_UNIT
)
2037 size
-= BITS_PER_UNIT
- ((unsigned HOST_WIDE_INT
) pd
.offset
2039 gcc_assert (size
>= 0);
2042 if ((unsigned HOST_WIDE_INT
) size
/ BITS_PER_UNIT
+ off
2044 size
= (needed_len
- off
) * BITS_PER_UNIT
;
2045 memcpy (p
, q
, size
/ BITS_PER_UNIT
);
2046 if (size
% BITS_PER_UNIT
)
2049 = -1U << (BITS_PER_UNIT
- (size
% BITS_PER_UNIT
));
2050 p
+= size
/ BITS_PER_UNIT
;
2051 q
+= size
/ BITS_PER_UNIT
;
2052 *p
= (*q
& msk
) | (*p
& ~msk
);
2059 /* LSB of this_buffer[0] byte should be at pd.offset bits
2062 size
= MIN (size
, (HOST_WIDE_INT
) needed_len
* BITS_PER_UNIT
);
2063 amnt
= pd
.offset
% BITS_PER_UNIT
;
2065 shift_bytes_in_array_left (this_buffer
, len
+ 1, amnt
);
2066 unsigned int off
= pd
.offset
/ BITS_PER_UNIT
;
2067 gcc_assert (off
< needed_len
);
2069 (HOST_WIDE_INT
) (needed_len
- off
) * BITS_PER_UNIT
);
2071 if (amnt
+ size
< BITS_PER_UNIT
)
2073 /* Low amnt bits come from *p, then size bits
2074 from this_buffer[0] and the remaining again from
2076 msk
= ((1 << size
) - 1) << amnt
;
2077 *p
= (*p
& ~msk
) | (this_buffer
[0] & msk
);
2083 *p
= (*p
& ~msk
) | (this_buffer
[0] & msk
);
2085 size
-= (BITS_PER_UNIT
- amnt
);
2090 amnt
= (unsigned HOST_WIDE_INT
) pd
.offset
% BITS_PER_UNIT
;
2092 size
-= BITS_PER_UNIT
- amnt
;
2093 size
= MIN (size
, (HOST_WIDE_INT
) needed_len
* BITS_PER_UNIT
);
2095 shift_bytes_in_array_left (this_buffer
, len
+ 1, amnt
);
2097 memcpy (p
, this_buffer
+ (amnt
!= 0), size
/ BITS_PER_UNIT
);
2098 p
+= size
/ BITS_PER_UNIT
;
2099 if (size
% BITS_PER_UNIT
)
2101 unsigned int msk
= -1U << (size
% BITS_PER_UNIT
);
2102 *p
= (this_buffer
[(amnt
!= 0) + size
/ BITS_PER_UNIT
]
2103 & ~msk
) | (*p
& msk
);
2108 tree type
= vr
->type
;
2109 /* Make sure to interpret in a type that has a range covering the whole
2111 if (INTEGRAL_TYPE_P (vr
->type
) && maxsizei
!= TYPE_PRECISION (vr
->type
))
2112 type
= build_nonstandard_integer_type (maxsizei
, TYPE_UNSIGNED (type
));
2114 if (BYTES_BIG_ENDIAN
)
2116 unsigned sz
= needed_len
;
2117 if (maxsizei
% BITS_PER_UNIT
)
2118 shift_bytes_in_array_right (buffer
, needed_len
,
2120 - (maxsizei
% BITS_PER_UNIT
));
2121 if (INTEGRAL_TYPE_P (type
))
2122 sz
= GET_MODE_SIZE (SCALAR_INT_TYPE_MODE (type
));
2123 if (sz
> needed_len
)
2125 memcpy (this_buffer
+ (sz
- needed_len
), buffer
, needed_len
);
2126 val
= native_interpret_expr (type
, this_buffer
, sz
);
2129 val
= native_interpret_expr (type
, buffer
, needed_len
);
2132 val
= native_interpret_expr (type
, buffer
, bufsize
);
2133 /* If we chop off bits because the types precision doesn't match the memory
2134 access size this is ok when optimizing reads but not when called from
2135 the DSE code during elimination. */
2136 if (val
&& type
!= vr
->type
)
2138 if (! int_fits_type_p (val
, vr
->type
))
2141 val
= fold_convert (vr
->type
, val
);
2146 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2148 "Successfully combined %u partial definitions\n", ndefs
);
2149 /* We are using the alias-set of the first store we encounter which
2150 should be appropriate here. */
2151 return finish (first_set
, first_base_set
, val
);
2155 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2157 "Failed to interpret %u encoded partial definitions\n", ndefs
);
2162 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
2163 with the current VUSE and performs the expression lookup. */
2166 vn_reference_lookup_2 (ao_ref
*op ATTRIBUTE_UNUSED
, tree vuse
, void *data_
)
2168 vn_walk_cb_data
*data
= (vn_walk_cb_data
*)data_
;
2169 vn_reference_t vr
= data
->vr
;
2170 vn_reference_s
**slot
;
2173 /* If we have partial definitions recorded we have to go through
2174 vn_reference_lookup_3. */
2175 if (!data
->partial_defs
.is_empty ())
2178 if (data
->last_vuse_ptr
)
2180 *data
->last_vuse_ptr
= vuse
;
2181 data
->last_vuse
= vuse
;
2184 /* Fixup vuse and hash. */
2186 vr
->hashcode
= vr
->hashcode
- SSA_NAME_VERSION (vr
->vuse
);
2187 vr
->vuse
= vuse_ssa_val (vuse
);
2189 vr
->hashcode
= vr
->hashcode
+ SSA_NAME_VERSION (vr
->vuse
);
2191 hash
= vr
->hashcode
;
2192 slot
= valid_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
2195 if ((*slot
)->result
&& data
->saved_operands
.exists ())
2196 return data
->finish (vr
->set
, vr
->base_set
, (*slot
)->result
);
2203 /* Lookup an existing or insert a new vn_reference entry into the
2204 value table for the VUSE, SET, TYPE, OPERANDS reference which
2205 has the value VALUE which is either a constant or an SSA name. */
2207 static vn_reference_t
2208 vn_reference_lookup_or_insert_for_pieces (tree vuse
,
2210 alias_set_type base_set
,
2212 vec
<vn_reference_op_s
,
2217 vn_reference_t result
;
2219 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2220 vr1
.operands
= operands
;
2223 vr1
.base_set
= base_set
;
2224 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2225 if (vn_reference_lookup_1 (&vr1
, &result
))
2227 if (TREE_CODE (value
) == SSA_NAME
)
2228 value_id
= VN_INFO (value
)->value_id
;
2230 value_id
= get_or_alloc_constant_value_id (value
);
2231 return vn_reference_insert_pieces (vuse
, set
, base_set
, type
,
2232 operands
.copy (), value
, value_id
);
2235 /* Return a value-number for RCODE OPS... either by looking up an existing
2236 value-number for the simplified result or by inserting the operation if
2240 vn_nary_build_or_lookup_1 (gimple_match_op
*res_op
, bool insert
)
2242 tree result
= NULL_TREE
;
2243 /* We will be creating a value number for
2245 So first simplify and lookup this expression to see if it
2246 is already available. */
2247 /* For simplification valueize. */
2249 for (i
= 0; i
< res_op
->num_ops
; ++i
)
2250 if (TREE_CODE (res_op
->ops
[i
]) == SSA_NAME
)
2252 tree tem
= vn_valueize (res_op
->ops
[i
]);
2255 res_op
->ops
[i
] = tem
;
2257 /* If valueization of an operand fails (it is not available), skip
2260 if (i
== res_op
->num_ops
)
2262 mprts_hook
= vn_lookup_simplify_result
;
2263 res
= res_op
->resimplify (NULL
, vn_valueize
);
2266 gimple
*new_stmt
= NULL
;
2268 && gimple_simplified_result_is_gimple_val (res_op
))
2270 /* The expression is already available. */
2271 result
= res_op
->ops
[0];
2272 /* Valueize it, simplification returns sth in AVAIL only. */
2273 if (TREE_CODE (result
) == SSA_NAME
)
2274 result
= SSA_VAL (result
);
2278 tree val
= vn_lookup_simplify_result (res_op
);
2281 gimple_seq stmts
= NULL
;
2282 result
= maybe_push_res_to_seq (res_op
, &stmts
);
2285 gcc_assert (gimple_seq_singleton_p (stmts
));
2286 new_stmt
= gimple_seq_first_stmt (stmts
);
2290 /* The expression is already available. */
2295 /* The expression is not yet available, value-number lhs to
2296 the new SSA_NAME we created. */
2297 /* Initialize value-number information properly. */
2298 vn_ssa_aux_t result_info
= VN_INFO (result
);
2299 result_info
->valnum
= result
;
2300 result_info
->value_id
= get_next_value_id ();
2301 result_info
->visited
= 1;
2302 gimple_seq_add_stmt_without_update (&VN_INFO (result
)->expr
,
2304 result_info
->needs_insertion
= true;
2305 /* ??? PRE phi-translation inserts NARYs without corresponding
2306 SSA name result. Re-use those but set their result according
2307 to the stmt we just built. */
2308 vn_nary_op_t nary
= NULL
;
2309 vn_nary_op_lookup_stmt (new_stmt
, &nary
);
2312 gcc_assert (! nary
->predicated_values
&& nary
->u
.result
== NULL_TREE
);
2313 nary
->u
.result
= gimple_assign_lhs (new_stmt
);
2315 /* As all "inserted" statements are singleton SCCs, insert
2316 to the valid table. This is strictly needed to
2317 avoid re-generating new value SSA_NAMEs for the same
2318 expression during SCC iteration over and over (the
2319 optimistic table gets cleared after each iteration).
2320 We do not need to insert into the optimistic table, as
2321 lookups there will fall back to the valid table. */
2324 unsigned int length
= vn_nary_length_from_stmt (new_stmt
);
2326 = alloc_vn_nary_op_noinit (length
, &vn_tables_insert_obstack
);
2327 vno1
->value_id
= result_info
->value_id
;
2328 vno1
->length
= length
;
2329 vno1
->predicated_values
= 0;
2330 vno1
->u
.result
= result
;
2331 init_vn_nary_op_from_stmt (vno1
, new_stmt
);
2332 vn_nary_op_insert_into (vno1
, valid_info
->nary
, true);
2333 /* Also do not link it into the undo chain. */
2334 last_inserted_nary
= vno1
->next
;
2335 vno1
->next
= (vn_nary_op_t
)(void *)-1;
2337 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2339 fprintf (dump_file
, "Inserting name ");
2340 print_generic_expr (dump_file
, result
);
2341 fprintf (dump_file
, " for expression ");
2342 print_gimple_expr (dump_file
, new_stmt
, 0, TDF_SLIM
);
2343 fprintf (dump_file
, "\n");
2349 /* Return a value-number for RCODE OPS... either by looking up an existing
2350 value-number for the simplified result or by inserting the operation. */
2353 vn_nary_build_or_lookup (gimple_match_op
*res_op
)
2355 return vn_nary_build_or_lookup_1 (res_op
, true);
2358 /* Try to simplify the expression RCODE OPS... of type TYPE and return
2359 its value if present. */
2362 vn_nary_simplify (vn_nary_op_t nary
)
2364 if (nary
->length
> gimple_match_op::MAX_NUM_OPS
)
2366 gimple_match_op
op (gimple_match_cond::UNCOND
, nary
->opcode
,
2367 nary
->type
, nary
->length
);
2368 memcpy (op
.ops
, nary
->op
, sizeof (tree
) * nary
->length
);
2369 return vn_nary_build_or_lookup_1 (&op
, false);
2372 /* Elimination engine. */
2374 class eliminate_dom_walker
: public dom_walker
2377 eliminate_dom_walker (cdi_direction
, bitmap
);
2378 ~eliminate_dom_walker ();
2380 virtual edge
before_dom_children (basic_block
);
2381 virtual void after_dom_children (basic_block
);
2383 virtual tree
eliminate_avail (basic_block
, tree op
);
2384 virtual void eliminate_push_avail (basic_block
, tree op
);
2385 tree
eliminate_insert (basic_block
, gimple_stmt_iterator
*gsi
, tree val
);
2387 void eliminate_stmt (basic_block
, gimple_stmt_iterator
*);
2389 unsigned eliminate_cleanup (bool region_p
= false);
2392 unsigned int el_todo
;
2393 unsigned int eliminations
;
2394 unsigned int insertions
;
2396 /* SSA names that had their defs inserted by PRE if do_pre. */
2397 bitmap inserted_exprs
;
2399 /* Blocks with statements that have had their EH properties changed. */
2400 bitmap need_eh_cleanup
;
2402 /* Blocks with statements that have had their AB properties changed. */
2403 bitmap need_ab_cleanup
;
2405 /* Local state for the eliminate domwalk. */
2406 auto_vec
<gimple
*> to_remove
;
2407 auto_vec
<gimple
*> to_fixup
;
2408 auto_vec
<tree
> avail
;
2409 auto_vec
<tree
> avail_stack
;
2412 /* Adaptor to the elimination engine using RPO availability. */
2414 class rpo_elim
: public eliminate_dom_walker
2417 rpo_elim(basic_block entry_
)
2418 : eliminate_dom_walker (CDI_DOMINATORS
, NULL
), entry (entry_
),
2419 m_avail_freelist (NULL
) {}
2421 virtual tree
eliminate_avail (basic_block
, tree op
);
2423 virtual void eliminate_push_avail (basic_block
, tree
);
2426 /* Freelist of avail entries which are allocated from the vn_ssa_aux
2428 vn_avail
*m_avail_freelist
;
2431 /* Global RPO state for access from hooks. */
2432 static eliminate_dom_walker
*rpo_avail
;
2433 basic_block vn_context_bb
;
2435 /* Return true if BASE1 and BASE2 can be adjusted so they have the
2436 same address and adjust *OFFSET1 and *OFFSET2 accordingly.
2437 Otherwise return false. */
2440 adjust_offsets_for_equal_base_address (tree base1
, poly_int64
*offset1
,
2441 tree base2
, poly_int64
*offset2
)
2444 if (TREE_CODE (base1
) == MEM_REF
2445 && TREE_CODE (base2
) == MEM_REF
)
2447 if (mem_ref_offset (base1
).to_shwi (&soff
))
2449 base1
= TREE_OPERAND (base1
, 0);
2450 *offset1
+= soff
* BITS_PER_UNIT
;
2452 if (mem_ref_offset (base2
).to_shwi (&soff
))
2454 base2
= TREE_OPERAND (base2
, 0);
2455 *offset2
+= soff
* BITS_PER_UNIT
;
2457 return operand_equal_p (base1
, base2
, 0);
2459 return operand_equal_p (base1
, base2
, OEP_ADDRESS_OF
);
2462 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
2463 from the statement defining VUSE and if not successful tries to
2464 translate *REFP and VR_ through an aggregate copy at the definition
2465 of VUSE. If *DISAMBIGUATE_ONLY is true then do not perform translation
2466 of *REF and *VR. If only disambiguation was performed then
2467 *DISAMBIGUATE_ONLY is set to true. */
2470 vn_reference_lookup_3 (ao_ref
*ref
, tree vuse
, void *data_
,
2471 translate_flags
*disambiguate_only
)
2473 vn_walk_cb_data
*data
= (vn_walk_cb_data
*)data_
;
2474 vn_reference_t vr
= data
->vr
;
2475 gimple
*def_stmt
= SSA_NAME_DEF_STMT (vuse
);
2476 tree base
= ao_ref_base (ref
);
2477 HOST_WIDE_INT offseti
= 0, maxsizei
, sizei
= 0;
2478 static vec
<vn_reference_op_s
> lhs_ops
;
2480 bool lhs_ref_ok
= false;
2481 poly_int64 copy_size
;
2483 /* First try to disambiguate after value-replacing in the definitions LHS. */
2484 if (is_gimple_assign (def_stmt
))
2486 tree lhs
= gimple_assign_lhs (def_stmt
);
2487 bool valueized_anything
= false;
2488 /* Avoid re-allocation overhead. */
2489 lhs_ops
.truncate (0);
2490 basic_block saved_rpo_bb
= vn_context_bb
;
2491 vn_context_bb
= gimple_bb (def_stmt
);
2492 if (*disambiguate_only
<= TR_VALUEIZE_AND_DISAMBIGUATE
)
2494 copy_reference_ops_from_ref (lhs
, &lhs_ops
);
2495 lhs_ops
= valueize_refs_1 (lhs_ops
, &valueized_anything
, true);
2497 vn_context_bb
= saved_rpo_bb
;
2498 ao_ref_init (&lhs_ref
, lhs
);
2500 if (valueized_anything
2501 && ao_ref_init_from_vn_reference
2502 (&lhs_ref
, ao_ref_alias_set (&lhs_ref
),
2503 ao_ref_base_alias_set (&lhs_ref
), TREE_TYPE (lhs
), lhs_ops
)
2504 && !refs_may_alias_p_1 (ref
, &lhs_ref
, data
->tbaa_p
))
2506 *disambiguate_only
= TR_VALUEIZE_AND_DISAMBIGUATE
;
2510 /* Besides valueizing the LHS we can also use access-path based
2511 disambiguation on the original non-valueized ref. */
2514 && data
->orig_ref
.ref
)
2516 /* We want to use the non-valueized LHS for this, but avoid redundant
2518 ao_ref
*lref
= &lhs_ref
;
2520 if (valueized_anything
)
2522 ao_ref_init (&lref_alt
, lhs
);
2525 if (!refs_may_alias_p_1 (&data
->orig_ref
, lref
, data
->tbaa_p
))
2527 *disambiguate_only
= (valueized_anything
2528 ? TR_VALUEIZE_AND_DISAMBIGUATE
2534 /* If we reach a clobbering statement try to skip it and see if
2535 we find a VN result with exactly the same value as the
2536 possible clobber. In this case we can ignore the clobber
2537 and return the found value. */
2538 if (is_gimple_reg_type (TREE_TYPE (lhs
))
2539 && types_compatible_p (TREE_TYPE (lhs
), vr
->type
)
2540 && (ref
->ref
|| data
->orig_ref
.ref
))
2542 tree
*saved_last_vuse_ptr
= data
->last_vuse_ptr
;
2543 /* Do not update last_vuse_ptr in vn_reference_lookup_2. */
2544 data
->last_vuse_ptr
= NULL
;
2545 tree saved_vuse
= vr
->vuse
;
2546 hashval_t saved_hashcode
= vr
->hashcode
;
2547 void *res
= vn_reference_lookup_2 (ref
, gimple_vuse (def_stmt
), data
);
2548 /* Need to restore vr->vuse and vr->hashcode. */
2549 vr
->vuse
= saved_vuse
;
2550 vr
->hashcode
= saved_hashcode
;
2551 data
->last_vuse_ptr
= saved_last_vuse_ptr
;
2552 if (res
&& res
!= (void *)-1)
2554 vn_reference_t vnresult
= (vn_reference_t
) res
;
2555 tree rhs
= gimple_assign_rhs1 (def_stmt
);
2556 if (TREE_CODE (rhs
) == SSA_NAME
)
2557 rhs
= SSA_VAL (rhs
);
2558 if (vnresult
->result
2559 && operand_equal_p (vnresult
->result
, rhs
, 0)
2560 /* We have to honor our promise about union type punning
2561 and also support arbitrary overlaps with
2562 -fno-strict-aliasing. So simply resort to alignment to
2563 rule out overlaps. Do this check last because it is
2564 quite expensive compared to the hash-lookup above. */
2565 && multiple_p (get_object_alignment
2566 (ref
->ref
? ref
->ref
: data
->orig_ref
.ref
),
2568 && multiple_p (get_object_alignment (lhs
), ref
->size
))
2573 else if (*disambiguate_only
<= TR_VALUEIZE_AND_DISAMBIGUATE
2574 && gimple_call_builtin_p (def_stmt
, BUILT_IN_NORMAL
)
2575 && gimple_call_num_args (def_stmt
) <= 4)
2577 /* For builtin calls valueize its arguments and call the
2578 alias oracle again. Valueization may improve points-to
2579 info of pointers and constify size and position arguments.
2580 Originally this was motivated by PR61034 which has
2581 conditional calls to free falsely clobbering ref because
2582 of imprecise points-to info of the argument. */
2584 bool valueized_anything
= false;
2585 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
2587 oldargs
[i
] = gimple_call_arg (def_stmt
, i
);
2588 tree val
= vn_valueize (oldargs
[i
]);
2589 if (val
!= oldargs
[i
])
2591 gimple_call_set_arg (def_stmt
, i
, val
);
2592 valueized_anything
= true;
2595 if (valueized_anything
)
2597 bool res
= call_may_clobber_ref_p_1 (as_a
<gcall
*> (def_stmt
),
2599 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
2600 gimple_call_set_arg (def_stmt
, i
, oldargs
[i
]);
2603 *disambiguate_only
= TR_VALUEIZE_AND_DISAMBIGUATE
;
2609 if (*disambiguate_only
> TR_TRANSLATE
)
2612 /* If we cannot constrain the size of the reference we cannot
2613 test if anything kills it. */
2614 if (!ref
->max_size_known_p ())
2617 poly_int64 offset
= ref
->offset
;
2618 poly_int64 maxsize
= ref
->max_size
;
2620 /* def_stmt may-defs *ref. See if we can derive a value for *ref
2621 from that definition.
2623 if (is_gimple_reg_type (vr
->type
)
2624 && (gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMSET
)
2625 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMSET_CHK
))
2626 && (integer_zerop (gimple_call_arg (def_stmt
, 1))
2627 || ((TREE_CODE (gimple_call_arg (def_stmt
, 1)) == INTEGER_CST
2628 || (INTEGRAL_TYPE_P (vr
->type
) && known_eq (ref
->size
, 8)))
2630 && BITS_PER_UNIT
== 8
2631 && BYTES_BIG_ENDIAN
== WORDS_BIG_ENDIAN
2632 && offset
.is_constant (&offseti
)
2633 && ref
->size
.is_constant (&sizei
)
2634 && (offseti
% BITS_PER_UNIT
== 0
2635 || TREE_CODE (gimple_call_arg (def_stmt
, 1)) == INTEGER_CST
)))
2636 && (poly_int_tree_p (gimple_call_arg (def_stmt
, 2))
2637 || (TREE_CODE (gimple_call_arg (def_stmt
, 2)) == SSA_NAME
2638 && poly_int_tree_p (SSA_VAL (gimple_call_arg (def_stmt
, 2)))))
2639 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
2640 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
))
2643 poly_int64 offset2
, size2
, maxsize2
;
2645 tree ref2
= gimple_call_arg (def_stmt
, 0);
2646 if (TREE_CODE (ref2
) == SSA_NAME
)
2648 ref2
= SSA_VAL (ref2
);
2649 if (TREE_CODE (ref2
) == SSA_NAME
2650 && (TREE_CODE (base
) != MEM_REF
2651 || TREE_OPERAND (base
, 0) != ref2
))
2653 gimple
*def_stmt
= SSA_NAME_DEF_STMT (ref2
);
2654 if (gimple_assign_single_p (def_stmt
)
2655 && gimple_assign_rhs_code (def_stmt
) == ADDR_EXPR
)
2656 ref2
= gimple_assign_rhs1 (def_stmt
);
2659 if (TREE_CODE (ref2
) == ADDR_EXPR
)
2661 ref2
= TREE_OPERAND (ref2
, 0);
2662 base2
= get_ref_base_and_extent (ref2
, &offset2
, &size2
, &maxsize2
,
2664 if (!known_size_p (maxsize2
)
2665 || !known_eq (maxsize2
, size2
)
2666 || !operand_equal_p (base
, base2
, OEP_ADDRESS_OF
))
2669 else if (TREE_CODE (ref2
) == SSA_NAME
)
2672 if (TREE_CODE (base
) != MEM_REF
2673 || !(mem_ref_offset (base
)
2674 << LOG2_BITS_PER_UNIT
).to_shwi (&soff
))
2678 if (TREE_OPERAND (base
, 0) != ref2
)
2680 gimple
*def
= SSA_NAME_DEF_STMT (ref2
);
2681 if (is_gimple_assign (def
)
2682 && gimple_assign_rhs_code (def
) == POINTER_PLUS_EXPR
2683 && gimple_assign_rhs1 (def
) == TREE_OPERAND (base
, 0)
2684 && poly_int_tree_p (gimple_assign_rhs2 (def
)))
2686 tree rhs2
= gimple_assign_rhs2 (def
);
2687 if (!(poly_offset_int::from (wi::to_poly_wide (rhs2
),
2689 << LOG2_BITS_PER_UNIT
).to_shwi (&offset2
))
2691 ref2
= gimple_assign_rhs1 (def
);
2692 if (TREE_CODE (ref2
) == SSA_NAME
)
2693 ref2
= SSA_VAL (ref2
);
2701 tree len
= gimple_call_arg (def_stmt
, 2);
2702 HOST_WIDE_INT leni
, offset2i
;
2703 if (TREE_CODE (len
) == SSA_NAME
)
2704 len
= SSA_VAL (len
);
2705 /* Sometimes the above trickery is smarter than alias analysis. Take
2706 advantage of that. */
2707 if (!ranges_maybe_overlap_p (offset
, maxsize
, offset2
,
2708 (wi::to_poly_offset (len
)
2709 << LOG2_BITS_PER_UNIT
)))
2711 if (data
->partial_defs
.is_empty ()
2712 && known_subrange_p (offset
, maxsize
, offset2
,
2713 wi::to_poly_offset (len
) << LOG2_BITS_PER_UNIT
))
2716 if (integer_zerop (gimple_call_arg (def_stmt
, 1)))
2717 val
= build_zero_cst (vr
->type
);
2718 else if (INTEGRAL_TYPE_P (vr
->type
)
2719 && known_eq (ref
->size
, 8)
2720 && offseti
% BITS_PER_UNIT
== 0)
2722 gimple_match_op
res_op (gimple_match_cond::UNCOND
, NOP_EXPR
,
2723 vr
->type
, gimple_call_arg (def_stmt
, 1));
2724 val
= vn_nary_build_or_lookup (&res_op
);
2726 || (TREE_CODE (val
) == SSA_NAME
2727 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
)))
2732 unsigned buflen
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (vr
->type
)) + 1;
2733 if (INTEGRAL_TYPE_P (vr
->type
))
2734 buflen
= GET_MODE_SIZE (SCALAR_INT_TYPE_MODE (vr
->type
)) + 1;
2735 unsigned char *buf
= XALLOCAVEC (unsigned char, buflen
);
2736 memset (buf
, TREE_INT_CST_LOW (gimple_call_arg (def_stmt
, 1)),
2738 if (BYTES_BIG_ENDIAN
)
2741 = (((unsigned HOST_WIDE_INT
) offseti
+ sizei
)
2745 shift_bytes_in_array_right (buf
, buflen
,
2746 BITS_PER_UNIT
- amnt
);
2751 else if (offseti
% BITS_PER_UNIT
!= 0)
2754 = BITS_PER_UNIT
- ((unsigned HOST_WIDE_INT
) offseti
2756 shift_bytes_in_array_left (buf
, buflen
, amnt
);
2760 val
= native_interpret_expr (vr
->type
, buf
, buflen
);
2764 return data
->finish (0, 0, val
);
2766 /* For now handle clearing memory with partial defs. */
2767 else if (known_eq (ref
->size
, maxsize
)
2768 && integer_zerop (gimple_call_arg (def_stmt
, 1))
2769 && tree_fits_poly_int64_p (len
)
2770 && tree_to_poly_int64 (len
).is_constant (&leni
)
2771 && leni
<= INTTYPE_MAXIMUM (HOST_WIDE_INT
) / BITS_PER_UNIT
2772 && offset
.is_constant (&offseti
)
2773 && offset2
.is_constant (&offset2i
)
2774 && maxsize
.is_constant (&maxsizei
)
2775 && ranges_known_overlap_p (offseti
, maxsizei
, offset2i
,
2776 leni
<< LOG2_BITS_PER_UNIT
))
2779 pd
.rhs
= build_constructor (NULL_TREE
, NULL
);
2780 pd
.offset
= offset2i
;
2781 pd
.size
= leni
<< LOG2_BITS_PER_UNIT
;
2782 return data
->push_partial_def (pd
, 0, 0, offseti
, maxsizei
);
2786 /* 2) Assignment from an empty CONSTRUCTOR. */
2787 else if (is_gimple_reg_type (vr
->type
)
2788 && gimple_assign_single_p (def_stmt
)
2789 && gimple_assign_rhs_code (def_stmt
) == CONSTRUCTOR
2790 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt
)) == 0)
2793 poly_int64 offset2
, size2
, maxsize2
;
2794 HOST_WIDE_INT offset2i
, size2i
;
2795 gcc_assert (lhs_ref_ok
);
2796 base2
= ao_ref_base (&lhs_ref
);
2797 offset2
= lhs_ref
.offset
;
2798 size2
= lhs_ref
.size
;
2799 maxsize2
= lhs_ref
.max_size
;
2800 if (known_size_p (maxsize2
)
2801 && known_eq (maxsize2
, size2
)
2802 && adjust_offsets_for_equal_base_address (base
, &offset
,
2805 if (data
->partial_defs
.is_empty ()
2806 && known_subrange_p (offset
, maxsize
, offset2
, size2
))
2808 /* While technically undefined behavior do not optimize
2809 a full read from a clobber. */
2810 if (gimple_clobber_p (def_stmt
))
2812 tree val
= build_zero_cst (vr
->type
);
2813 return data
->finish (ao_ref_alias_set (&lhs_ref
),
2814 ao_ref_base_alias_set (&lhs_ref
), val
);
2816 else if (known_eq (ref
->size
, maxsize
)
2817 && maxsize
.is_constant (&maxsizei
)
2818 && offset
.is_constant (&offseti
)
2819 && offset2
.is_constant (&offset2i
)
2820 && size2
.is_constant (&size2i
)
2821 && ranges_known_overlap_p (offseti
, maxsizei
,
2824 /* Let clobbers be consumed by the partial-def tracker
2825 which can choose to ignore them if they are shadowed
2828 pd
.rhs
= gimple_assign_rhs1 (def_stmt
);
2829 pd
.offset
= offset2i
;
2831 return data
->push_partial_def (pd
, ao_ref_alias_set (&lhs_ref
),
2832 ao_ref_base_alias_set (&lhs_ref
),
2838 /* 3) Assignment from a constant. We can use folds native encode/interpret
2839 routines to extract the assigned bits. */
2840 else if (known_eq (ref
->size
, maxsize
)
2841 && is_gimple_reg_type (vr
->type
)
2842 && !contains_storage_order_barrier_p (vr
->operands
)
2843 && gimple_assign_single_p (def_stmt
)
2845 && BITS_PER_UNIT
== 8
2846 && BYTES_BIG_ENDIAN
== WORDS_BIG_ENDIAN
2847 /* native_encode and native_decode operate on arrays of bytes
2848 and so fundamentally need a compile-time size and offset. */
2849 && maxsize
.is_constant (&maxsizei
)
2850 && offset
.is_constant (&offseti
)
2851 && (is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
))
2852 || (TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
2853 && is_gimple_min_invariant (SSA_VAL (gimple_assign_rhs1 (def_stmt
))))))
2855 tree lhs
= gimple_assign_lhs (def_stmt
);
2857 poly_int64 offset2
, size2
, maxsize2
;
2858 HOST_WIDE_INT offset2i
, size2i
;
2860 gcc_assert (lhs_ref_ok
);
2861 base2
= ao_ref_base (&lhs_ref
);
2862 offset2
= lhs_ref
.offset
;
2863 size2
= lhs_ref
.size
;
2864 maxsize2
= lhs_ref
.max_size
;
2865 reverse
= reverse_storage_order_for_component_p (lhs
);
2868 && !storage_order_barrier_p (lhs
)
2869 && known_eq (maxsize2
, size2
)
2870 && adjust_offsets_for_equal_base_address (base
, &offset
,
2872 && offset
.is_constant (&offseti
)
2873 && offset2
.is_constant (&offset2i
)
2874 && size2
.is_constant (&size2i
))
2876 if (data
->partial_defs
.is_empty ()
2877 && known_subrange_p (offseti
, maxsizei
, offset2
, size2
))
2879 /* We support up to 512-bit values (for V8DFmode). */
2880 unsigned char buffer
[65];
2883 tree rhs
= gimple_assign_rhs1 (def_stmt
);
2884 if (TREE_CODE (rhs
) == SSA_NAME
)
2885 rhs
= SSA_VAL (rhs
);
2886 len
= native_encode_expr (rhs
,
2887 buffer
, sizeof (buffer
) - 1,
2888 (offseti
- offset2i
) / BITS_PER_UNIT
);
2889 if (len
> 0 && len
* BITS_PER_UNIT
>= maxsizei
)
2891 tree type
= vr
->type
;
2892 unsigned char *buf
= buffer
;
2893 unsigned int amnt
= 0;
2894 /* Make sure to interpret in a type that has a range
2895 covering the whole access size. */
2896 if (INTEGRAL_TYPE_P (vr
->type
)
2897 && maxsizei
!= TYPE_PRECISION (vr
->type
))
2898 type
= build_nonstandard_integer_type (maxsizei
,
2899 TYPE_UNSIGNED (type
));
2900 if (BYTES_BIG_ENDIAN
)
2902 /* For big-endian native_encode_expr stored the rhs
2903 such that the LSB of it is the LSB of buffer[len - 1].
2904 That bit is stored into memory at position
2905 offset2 + size2 - 1, i.e. in byte
2906 base + (offset2 + size2 - 1) / BITS_PER_UNIT.
2907 E.g. for offset2 1 and size2 14, rhs -1 and memory
2908 previously cleared that is:
2911 Now, if we want to extract offset 2 and size 12 from
2912 it using native_interpret_expr (which actually works
2913 for integral bitfield types in terms of byte size of
2914 the mode), the native_encode_expr stored the value
2917 and returned len 2 (the X bits are outside of
2919 Let sz be maxsize / BITS_PER_UNIT if not extracting
2920 a bitfield, and GET_MODE_SIZE otherwise.
2921 We need to align the LSB of the value we want to
2922 extract as the LSB of buf[sz - 1].
2923 The LSB from memory we need to read is at position
2924 offset + maxsize - 1. */
2925 HOST_WIDE_INT sz
= maxsizei
/ BITS_PER_UNIT
;
2926 if (INTEGRAL_TYPE_P (type
))
2927 sz
= GET_MODE_SIZE (SCALAR_INT_TYPE_MODE (type
));
2928 amnt
= ((unsigned HOST_WIDE_INT
) offset2i
+ size2i
2929 - offseti
- maxsizei
) % BITS_PER_UNIT
;
2931 shift_bytes_in_array_right (buffer
, len
, amnt
);
2932 amnt
= ((unsigned HOST_WIDE_INT
) offset2i
+ size2i
2933 - offseti
- maxsizei
- amnt
) / BITS_PER_UNIT
;
2934 if ((unsigned HOST_WIDE_INT
) sz
+ amnt
> (unsigned) len
)
2938 buf
= buffer
+ len
- sz
- amnt
;
2939 len
-= (buf
- buffer
);
2944 amnt
= ((unsigned HOST_WIDE_INT
) offset2i
2945 - offseti
) % BITS_PER_UNIT
;
2949 shift_bytes_in_array_left (buffer
, len
+ 1, amnt
);
2953 tree val
= native_interpret_expr (type
, buf
, len
);
2954 /* If we chop off bits because the types precision doesn't
2955 match the memory access size this is ok when optimizing
2956 reads but not when called from the DSE code during
2959 && type
!= vr
->type
)
2961 if (! int_fits_type_p (val
, vr
->type
))
2964 val
= fold_convert (vr
->type
, val
);
2968 return data
->finish (ao_ref_alias_set (&lhs_ref
),
2969 ao_ref_base_alias_set (&lhs_ref
), val
);
2972 else if (ranges_known_overlap_p (offseti
, maxsizei
, offset2i
,
2976 tree rhs
= gimple_assign_rhs1 (def_stmt
);
2977 if (TREE_CODE (rhs
) == SSA_NAME
)
2978 rhs
= SSA_VAL (rhs
);
2980 pd
.offset
= offset2i
;
2982 return data
->push_partial_def (pd
, ao_ref_alias_set (&lhs_ref
),
2983 ao_ref_base_alias_set (&lhs_ref
),
2989 /* 4) Assignment from an SSA name which definition we may be able
2990 to access pieces from or we can combine to a larger entity. */
2991 else if (known_eq (ref
->size
, maxsize
)
2992 && is_gimple_reg_type (vr
->type
)
2993 && !contains_storage_order_barrier_p (vr
->operands
)
2994 && gimple_assign_single_p (def_stmt
)
2995 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
)
2997 tree lhs
= gimple_assign_lhs (def_stmt
);
2999 poly_int64 offset2
, size2
, maxsize2
;
3000 HOST_WIDE_INT offset2i
, size2i
, offseti
;
3002 gcc_assert (lhs_ref_ok
);
3003 base2
= ao_ref_base (&lhs_ref
);
3004 offset2
= lhs_ref
.offset
;
3005 size2
= lhs_ref
.size
;
3006 maxsize2
= lhs_ref
.max_size
;
3007 reverse
= reverse_storage_order_for_component_p (lhs
);
3008 tree def_rhs
= gimple_assign_rhs1 (def_stmt
);
3010 && !storage_order_barrier_p (lhs
)
3011 && known_size_p (maxsize2
)
3012 && known_eq (maxsize2
, size2
)
3013 && adjust_offsets_for_equal_base_address (base
, &offset
,
3016 if (data
->partial_defs
.is_empty ()
3017 && known_subrange_p (offset
, maxsize
, offset2
, size2
)
3018 /* ??? We can't handle bitfield precision extracts without
3019 either using an alternate type for the BIT_FIELD_REF and
3020 then doing a conversion or possibly adjusting the offset
3021 according to endianness. */
3022 && (! INTEGRAL_TYPE_P (vr
->type
)
3023 || known_eq (ref
->size
, TYPE_PRECISION (vr
->type
)))
3024 && multiple_p (ref
->size
, BITS_PER_UNIT
))
3026 tree val
= NULL_TREE
;
3027 if (! INTEGRAL_TYPE_P (TREE_TYPE (def_rhs
))
3028 || type_has_mode_precision_p (TREE_TYPE (def_rhs
)))
3030 gimple_match_op
op (gimple_match_cond::UNCOND
,
3031 BIT_FIELD_REF
, vr
->type
,
3033 bitsize_int (ref
->size
),
3034 bitsize_int (offset
- offset2
));
3035 val
= vn_nary_build_or_lookup (&op
);
3037 else if (known_eq (ref
->size
, size2
))
3039 gimple_match_op
op (gimple_match_cond::UNCOND
,
3040 VIEW_CONVERT_EXPR
, vr
->type
,
3042 val
= vn_nary_build_or_lookup (&op
);
3045 && (TREE_CODE (val
) != SSA_NAME
3046 || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
)))
3047 return data
->finish (ao_ref_alias_set (&lhs_ref
),
3048 ao_ref_base_alias_set (&lhs_ref
), val
);
3050 else if (maxsize
.is_constant (&maxsizei
)
3051 && offset
.is_constant (&offseti
)
3052 && offset2
.is_constant (&offset2i
)
3053 && size2
.is_constant (&size2i
)
3054 && ranges_known_overlap_p (offset
, maxsize
, offset2
, size2
))
3057 pd
.rhs
= SSA_VAL (def_rhs
);
3058 pd
.offset
= offset2i
;
3060 return data
->push_partial_def (pd
, ao_ref_alias_set (&lhs_ref
),
3061 ao_ref_base_alias_set (&lhs_ref
),
3067 /* 5) For aggregate copies translate the reference through them if
3068 the copy kills ref. */
3069 else if (data
->vn_walk_kind
== VN_WALKREWRITE
3070 && gimple_assign_single_p (def_stmt
)
3071 && (DECL_P (gimple_assign_rhs1 (def_stmt
))
3072 || TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == MEM_REF
3073 || handled_component_p (gimple_assign_rhs1 (def_stmt
))))
3077 auto_vec
<vn_reference_op_s
> rhs
;
3078 vn_reference_op_t vro
;
3081 gcc_assert (lhs_ref_ok
);
3083 /* See if the assignment kills REF. */
3084 base2
= ao_ref_base (&lhs_ref
);
3085 if (!lhs_ref
.max_size_known_p ()
3087 && (TREE_CODE (base
) != MEM_REF
3088 || TREE_CODE (base2
) != MEM_REF
3089 || TREE_OPERAND (base
, 0) != TREE_OPERAND (base2
, 0)
3090 || !tree_int_cst_equal (TREE_OPERAND (base
, 1),
3091 TREE_OPERAND (base2
, 1))))
3092 || !stmt_kills_ref_p (def_stmt
, ref
))
3095 /* Find the common base of ref and the lhs. lhs_ops already
3096 contains valueized operands for the lhs. */
3097 i
= vr
->operands
.length () - 1;
3098 j
= lhs_ops
.length () - 1;
3099 while (j
>= 0 && i
>= 0
3100 && vn_reference_op_eq (&vr
->operands
[i
], &lhs_ops
[j
]))
3106 /* ??? The innermost op should always be a MEM_REF and we already
3107 checked that the assignment to the lhs kills vr. Thus for
3108 aggregate copies using char[] types the vn_reference_op_eq
3109 may fail when comparing types for compatibility. But we really
3110 don't care here - further lookups with the rewritten operands
3111 will simply fail if we messed up types too badly. */
3112 poly_int64 extra_off
= 0;
3113 if (j
== 0 && i
>= 0
3114 && lhs_ops
[0].opcode
== MEM_REF
3115 && maybe_ne (lhs_ops
[0].off
, -1))
3117 if (known_eq (lhs_ops
[0].off
, vr
->operands
[i
].off
))
3119 else if (vr
->operands
[i
].opcode
== MEM_REF
3120 && maybe_ne (vr
->operands
[i
].off
, -1))
3122 extra_off
= vr
->operands
[i
].off
- lhs_ops
[0].off
;
3127 /* i now points to the first additional op.
3128 ??? LHS may not be completely contained in VR, one or more
3129 VIEW_CONVERT_EXPRs could be in its way. We could at least
3130 try handling outermost VIEW_CONVERT_EXPRs. */
3134 /* Punt if the additional ops contain a storage order barrier. */
3135 for (k
= i
; k
>= 0; k
--)
3137 vro
= &vr
->operands
[k
];
3138 if (vro
->opcode
== VIEW_CONVERT_EXPR
&& vro
->reverse
)
3142 /* Now re-write REF to be based on the rhs of the assignment. */
3143 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
3144 copy_reference_ops_from_ref (rhs1
, &rhs
);
3146 /* Apply an extra offset to the inner MEM_REF of the RHS. */
3147 if (maybe_ne (extra_off
, 0))
3149 if (rhs
.length () < 2)
3151 int ix
= rhs
.length () - 2;
3152 if (rhs
[ix
].opcode
!= MEM_REF
3153 || known_eq (rhs
[ix
].off
, -1))
3155 rhs
[ix
].off
+= extra_off
;
3156 rhs
[ix
].op0
= int_const_binop (PLUS_EXPR
, rhs
[ix
].op0
,
3157 build_int_cst (TREE_TYPE (rhs
[ix
].op0
),
3161 /* Save the operands since we need to use the original ones for
3162 the hash entry we use. */
3163 if (!data
->saved_operands
.exists ())
3164 data
->saved_operands
= vr
->operands
.copy ();
3166 /* We need to pre-pend vr->operands[0..i] to rhs. */
3167 vec
<vn_reference_op_s
> old
= vr
->operands
;
3168 if (i
+ 1 + rhs
.length () > vr
->operands
.length ())
3169 vr
->operands
.safe_grow (i
+ 1 + rhs
.length (), true);
3171 vr
->operands
.truncate (i
+ 1 + rhs
.length ());
3172 FOR_EACH_VEC_ELT (rhs
, j
, vro
)
3173 vr
->operands
[i
+ 1 + j
] = *vro
;
3174 vr
->operands
= valueize_refs (vr
->operands
);
3175 if (old
== shared_lookup_references
)
3176 shared_lookup_references
= vr
->operands
;
3177 vr
->hashcode
= vn_reference_compute_hash (vr
);
3179 /* Try folding the new reference to a constant. */
3180 tree val
= fully_constant_vn_reference_p (vr
);
3183 if (data
->partial_defs
.is_empty ())
3184 return data
->finish (ao_ref_alias_set (&lhs_ref
),
3185 ao_ref_base_alias_set (&lhs_ref
), val
);
3186 /* This is the only interesting case for partial-def handling
3187 coming from targets that like to gimplify init-ctors as
3188 aggregate copies from constant data like aarch64 for
3190 if (maxsize
.is_constant (&maxsizei
) && known_eq (ref
->size
, maxsize
))
3196 return data
->push_partial_def (pd
, ao_ref_alias_set (&lhs_ref
),
3197 ao_ref_base_alias_set (&lhs_ref
),
3202 /* Continuing with partial defs isn't easily possible here, we
3203 have to find a full def from further lookups from here. Probably
3204 not worth the special-casing everywhere. */
3205 if (!data
->partial_defs
.is_empty ())
3208 /* Adjust *ref from the new operands. */
3210 ao_ref_init (&rhs1_ref
, rhs1
);
3211 if (!ao_ref_init_from_vn_reference (&r
, ao_ref_alias_set (&rhs1_ref
),
3212 ao_ref_base_alias_set (&rhs1_ref
),
3213 vr
->type
, vr
->operands
))
3215 /* This can happen with bitfields. */
3216 if (maybe_ne (ref
->size
, r
.size
))
3220 /* Do not update last seen VUSE after translating. */
3221 data
->last_vuse_ptr
= NULL
;
3222 /* Invalidate the original access path since it now contains
3224 data
->orig_ref
.ref
= NULL_TREE
;
3225 /* Use the alias-set of this LHS for recording an eventual result. */
3226 if (data
->first_set
== -2)
3228 data
->first_set
= ao_ref_alias_set (&lhs_ref
);
3229 data
->first_base_set
= ao_ref_base_alias_set (&lhs_ref
);
3232 /* Keep looking for the adjusted *REF / VR pair. */
3236 /* 6) For memcpy copies translate the reference through them if the copy
3237 kills ref. But we cannot (easily) do this translation if the memcpy is
3238 a storage order barrier, i.e. is equivalent to a VIEW_CONVERT_EXPR that
3239 can modify the storage order of objects (see storage_order_barrier_p). */
3240 else if (data
->vn_walk_kind
== VN_WALKREWRITE
3241 && is_gimple_reg_type (vr
->type
)
3242 /* ??? Handle BCOPY as well. */
3243 && (gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMCPY
)
3244 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMCPY_CHK
)
3245 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMPCPY
)
3246 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMPCPY_CHK
)
3247 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMMOVE
)
3248 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMMOVE_CHK
))
3249 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
3250 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
)
3251 && (TREE_CODE (gimple_call_arg (def_stmt
, 1)) == ADDR_EXPR
3252 || TREE_CODE (gimple_call_arg (def_stmt
, 1)) == SSA_NAME
)
3253 && (poly_int_tree_p (gimple_call_arg (def_stmt
, 2), ©_size
)
3254 || (TREE_CODE (gimple_call_arg (def_stmt
, 2)) == SSA_NAME
3255 && poly_int_tree_p (SSA_VAL (gimple_call_arg (def_stmt
, 2)),
3257 /* Handling this is more complicated, give up for now. */
3258 && data
->partial_defs
.is_empty ())
3262 poly_int64 rhs_offset
, lhs_offset
;
3263 vn_reference_op_s op
;
3264 poly_uint64 mem_offset
;
3265 poly_int64 at
, byte_maxsize
;
3267 /* Only handle non-variable, addressable refs. */
3268 if (maybe_ne (ref
->size
, maxsize
)
3269 || !multiple_p (offset
, BITS_PER_UNIT
, &at
)
3270 || !multiple_p (maxsize
, BITS_PER_UNIT
, &byte_maxsize
))
3273 /* Extract a pointer base and an offset for the destination. */
3274 lhs
= gimple_call_arg (def_stmt
, 0);
3276 if (TREE_CODE (lhs
) == SSA_NAME
)
3278 lhs
= vn_valueize (lhs
);
3279 if (TREE_CODE (lhs
) == SSA_NAME
)
3281 gimple
*def_stmt
= SSA_NAME_DEF_STMT (lhs
);
3282 if (gimple_assign_single_p (def_stmt
)
3283 && gimple_assign_rhs_code (def_stmt
) == ADDR_EXPR
)
3284 lhs
= gimple_assign_rhs1 (def_stmt
);
3287 if (TREE_CODE (lhs
) == ADDR_EXPR
)
3289 if (AGGREGATE_TYPE_P (TREE_TYPE (TREE_TYPE (lhs
)))
3290 && TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (TREE_TYPE (lhs
))))
3292 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (lhs
, 0),
3296 if (TREE_CODE (tem
) == MEM_REF
3297 && poly_int_tree_p (TREE_OPERAND (tem
, 1), &mem_offset
))
3299 lhs
= TREE_OPERAND (tem
, 0);
3300 if (TREE_CODE (lhs
) == SSA_NAME
)
3301 lhs
= vn_valueize (lhs
);
3302 lhs_offset
+= mem_offset
;
3304 else if (DECL_P (tem
))
3305 lhs
= build_fold_addr_expr (tem
);
3309 if (TREE_CODE (lhs
) != SSA_NAME
3310 && TREE_CODE (lhs
) != ADDR_EXPR
)
3313 /* Extract a pointer base and an offset for the source. */
3314 rhs
= gimple_call_arg (def_stmt
, 1);
3316 if (TREE_CODE (rhs
) == SSA_NAME
)
3317 rhs
= vn_valueize (rhs
);
3318 if (TREE_CODE (rhs
) == ADDR_EXPR
)
3320 if (AGGREGATE_TYPE_P (TREE_TYPE (TREE_TYPE (rhs
)))
3321 && TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (TREE_TYPE (rhs
))))
3323 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs
, 0),
3327 if (TREE_CODE (tem
) == MEM_REF
3328 && poly_int_tree_p (TREE_OPERAND (tem
, 1), &mem_offset
))
3330 rhs
= TREE_OPERAND (tem
, 0);
3331 rhs_offset
+= mem_offset
;
3333 else if (DECL_P (tem
)
3334 || TREE_CODE (tem
) == STRING_CST
)
3335 rhs
= build_fold_addr_expr (tem
);
3339 if (TREE_CODE (rhs
) == SSA_NAME
)
3340 rhs
= SSA_VAL (rhs
);
3341 else if (TREE_CODE (rhs
) != ADDR_EXPR
)
3344 /* The bases of the destination and the references have to agree. */
3345 if (TREE_CODE (base
) == MEM_REF
)
3347 if (TREE_OPERAND (base
, 0) != lhs
3348 || !poly_int_tree_p (TREE_OPERAND (base
, 1), &mem_offset
))
3352 else if (!DECL_P (base
)
3353 || TREE_CODE (lhs
) != ADDR_EXPR
3354 || TREE_OPERAND (lhs
, 0) != base
)
3357 /* If the access is completely outside of the memcpy destination
3358 area there is no aliasing. */
3359 if (!ranges_maybe_overlap_p (lhs_offset
, copy_size
, at
, byte_maxsize
))
3361 /* And the access has to be contained within the memcpy destination. */
3362 if (!known_subrange_p (at
, byte_maxsize
, lhs_offset
, copy_size
))
3365 /* Save the operands since we need to use the original ones for
3366 the hash entry we use. */
3367 if (!data
->saved_operands
.exists ())
3368 data
->saved_operands
= vr
->operands
.copy ();
3370 /* Make room for 2 operands in the new reference. */
3371 if (vr
->operands
.length () < 2)
3373 vec
<vn_reference_op_s
> old
= vr
->operands
;
3374 vr
->operands
.safe_grow_cleared (2, true);
3375 if (old
== shared_lookup_references
)
3376 shared_lookup_references
= vr
->operands
;
3379 vr
->operands
.truncate (2);
3381 /* The looked-through reference is a simple MEM_REF. */
3382 memset (&op
, 0, sizeof (op
));
3384 op
.opcode
= MEM_REF
;
3385 op
.op0
= build_int_cst (ptr_type_node
, at
- lhs_offset
+ rhs_offset
);
3386 op
.off
= at
- lhs_offset
+ rhs_offset
;
3387 vr
->operands
[0] = op
;
3388 op
.type
= TREE_TYPE (rhs
);
3389 op
.opcode
= TREE_CODE (rhs
);
3392 vr
->operands
[1] = op
;
3393 vr
->hashcode
= vn_reference_compute_hash (vr
);
3395 /* Try folding the new reference to a constant. */
3396 tree val
= fully_constant_vn_reference_p (vr
);
3398 return data
->finish (0, 0, val
);
3400 /* Adjust *ref from the new operands. */
3401 if (!ao_ref_init_from_vn_reference (&r
, 0, 0, vr
->type
, vr
->operands
))
3403 /* This can happen with bitfields. */
3404 if (maybe_ne (ref
->size
, r
.size
))
3408 /* Do not update last seen VUSE after translating. */
3409 data
->last_vuse_ptr
= NULL
;
3410 /* Invalidate the original access path since it now contains
3412 data
->orig_ref
.ref
= NULL_TREE
;
3413 /* Use the alias-set of this stmt for recording an eventual result. */
3414 if (data
->first_set
== -2)
3416 data
->first_set
= 0;
3417 data
->first_base_set
= 0;
3420 /* Keep looking for the adjusted *REF / VR pair. */
3424 /* Bail out and stop walking. */
3428 /* Return a reference op vector from OP that can be used for
3429 vn_reference_lookup_pieces. The caller is responsible for releasing
3432 vec
<vn_reference_op_s
>
3433 vn_reference_operands_for_lookup (tree op
)
3436 return valueize_shared_reference_ops_from_ref (op
, &valueized
).copy ();
3439 /* Lookup a reference operation by it's parts, in the current hash table.
3440 Returns the resulting value number if it exists in the hash table,
3441 NULL_TREE otherwise. VNRESULT will be filled in with the actual
3442 vn_reference_t stored in the hashtable if something is found. */
3445 vn_reference_lookup_pieces (tree vuse
, alias_set_type set
,
3446 alias_set_type base_set
, tree type
,
3447 vec
<vn_reference_op_s
> operands
,
3448 vn_reference_t
*vnresult
, vn_lookup_kind kind
)
3450 struct vn_reference_s vr1
;
3458 vr1
.vuse
= vuse_ssa_val (vuse
);
3459 shared_lookup_references
.truncate (0);
3460 shared_lookup_references
.safe_grow (operands
.length (), true);
3461 memcpy (shared_lookup_references
.address (),
3462 operands
.address (),
3463 sizeof (vn_reference_op_s
)
3464 * operands
.length ());
3465 vr1
.operands
= operands
= shared_lookup_references
3466 = valueize_refs (shared_lookup_references
);
3469 vr1
.base_set
= base_set
;
3470 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
3471 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
3474 vn_reference_lookup_1 (&vr1
, vnresult
);
3476 && kind
!= VN_NOWALK
3480 unsigned limit
= param_sccvn_max_alias_queries_per_access
;
3481 vn_walk_cb_data
data (&vr1
, NULL_TREE
, NULL
, kind
, true, NULL_TREE
);
3482 if (ao_ref_init_from_vn_reference (&r
, set
, base_set
, type
,
3486 walk_non_aliased_vuses (&r
, vr1
.vuse
, true, vn_reference_lookup_2
,
3487 vn_reference_lookup_3
, vuse_valueize
,
3489 gcc_checking_assert (vr1
.operands
== shared_lookup_references
);
3493 return (*vnresult
)->result
;
3498 /* Lookup OP in the current hash table, and return the resulting value
3499 number if it exists in the hash table. Return NULL_TREE if it does
3500 not exist in the hash table or if the result field of the structure
3501 was NULL.. VNRESULT will be filled in with the vn_reference_t
3502 stored in the hashtable if one exists. When TBAA_P is false assume
3503 we are looking up a store and treat it as having alias-set zero.
3504 *LAST_VUSE_PTR will be updated with the VUSE the value lookup succeeded.
3505 MASK is either NULL_TREE, or can be an INTEGER_CST if the result of the
3506 load is bitwise anded with MASK and so we are only interested in a subset
3507 of the bits and can ignore if the other bits are uninitialized or
3508 not initialized with constants. */
3511 vn_reference_lookup (tree op
, tree vuse
, vn_lookup_kind kind
,
3512 vn_reference_t
*vnresult
, bool tbaa_p
,
3513 tree
*last_vuse_ptr
, tree mask
)
3515 vec
<vn_reference_op_s
> operands
;
3516 struct vn_reference_s vr1
;
3517 bool valuezied_anything
;
3522 vr1
.vuse
= vuse_ssa_val (vuse
);
3523 vr1
.operands
= operands
3524 = valueize_shared_reference_ops_from_ref (op
, &valuezied_anything
);
3525 vr1
.type
= TREE_TYPE (op
);
3527 ao_ref_init (&op_ref
, op
);
3528 vr1
.set
= ao_ref_alias_set (&op_ref
);
3529 vr1
.base_set
= ao_ref_base_alias_set (&op_ref
);
3530 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
3531 if (mask
== NULL_TREE
)
3532 if (tree cst
= fully_constant_vn_reference_p (&vr1
))
3535 if (kind
!= VN_NOWALK
&& vr1
.vuse
)
3537 vn_reference_t wvnresult
;
3539 unsigned limit
= param_sccvn_max_alias_queries_per_access
;
3540 /* Make sure to use a valueized reference if we valueized anything.
3541 Otherwise preserve the full reference for advanced TBAA. */
3542 if (!valuezied_anything
3543 || !ao_ref_init_from_vn_reference (&r
, vr1
.set
, vr1
.base_set
,
3544 vr1
.type
, vr1
.operands
))
3545 ao_ref_init (&r
, op
);
3546 vn_walk_cb_data
data (&vr1
, r
.ref
? NULL_TREE
: op
,
3547 last_vuse_ptr
, kind
, tbaa_p
, mask
);
3551 walk_non_aliased_vuses (&r
, vr1
.vuse
, tbaa_p
, vn_reference_lookup_2
,
3552 vn_reference_lookup_3
, vuse_valueize
, limit
,
3554 gcc_checking_assert (vr1
.operands
== shared_lookup_references
);
3557 gcc_assert (mask
== NULL_TREE
);
3559 *vnresult
= wvnresult
;
3560 return wvnresult
->result
;
3563 return data
.masked_result
;
3569 *last_vuse_ptr
= vr1
.vuse
;
3572 return vn_reference_lookup_1 (&vr1
, vnresult
);
3575 /* Lookup CALL in the current hash table and return the entry in
3576 *VNRESULT if found. Populates *VR for the hashtable lookup. */
3579 vn_reference_lookup_call (gcall
*call
, vn_reference_t
*vnresult
,
3585 tree vuse
= gimple_vuse (call
);
3587 vr
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
3588 vr
->operands
= valueize_shared_reference_ops_from_call (call
);
3589 vr
->type
= gimple_expr_type (call
);
3593 vr
->hashcode
= vn_reference_compute_hash (vr
);
3594 vn_reference_lookup_1 (vr
, vnresult
);
3597 /* Insert OP into the current hash table with a value number of RESULT. */
3600 vn_reference_insert (tree op
, tree result
, tree vuse
, tree vdef
)
3602 vn_reference_s
**slot
;
3606 vr1
= XOBNEW (&vn_tables_obstack
, vn_reference_s
);
3607 if (TREE_CODE (result
) == SSA_NAME
)
3608 vr1
->value_id
= VN_INFO (result
)->value_id
;
3610 vr1
->value_id
= get_or_alloc_constant_value_id (result
);
3611 vr1
->vuse
= vuse_ssa_val (vuse
);
3612 vr1
->operands
= valueize_shared_reference_ops_from_ref (op
, &tem
).copy ();
3613 vr1
->type
= TREE_TYPE (op
);
3614 vr1
->punned
= false;
3616 ao_ref_init (&op_ref
, op
);
3617 vr1
->set
= ao_ref_alias_set (&op_ref
);
3618 vr1
->base_set
= ao_ref_base_alias_set (&op_ref
);
3619 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
3620 vr1
->result
= TREE_CODE (result
) == SSA_NAME
? SSA_VAL (result
) : result
;
3621 vr1
->result_vdef
= vdef
;
3623 slot
= valid_info
->references
->find_slot_with_hash (vr1
, vr1
->hashcode
,
3626 /* Because IL walking on reference lookup can end up visiting
3627 a def that is only to be visited later in iteration order
3628 when we are about to make an irreducible region reducible
3629 the def can be effectively processed and its ref being inserted
3630 by vn_reference_lookup_3 already. So we cannot assert (!*slot)
3631 but save a lookup if we deal with already inserted refs here. */
3634 /* We cannot assert that we have the same value either because
3635 when disentangling an irreducible region we may end up visiting
3636 a use before the corresponding def. That's a missed optimization
3637 only though. See gcc.dg/tree-ssa/pr87126.c for example. */
3638 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
3639 && !operand_equal_p ((*slot
)->result
, vr1
->result
, 0))
3641 fprintf (dump_file
, "Keeping old value ");
3642 print_generic_expr (dump_file
, (*slot
)->result
);
3643 fprintf (dump_file
, " because of collision\n");
3645 free_reference (vr1
);
3646 obstack_free (&vn_tables_obstack
, vr1
);
3651 vr1
->next
= last_inserted_ref
;
3652 last_inserted_ref
= vr1
;
3655 /* Insert a reference by it's pieces into the current hash table with
3656 a value number of RESULT. Return the resulting reference
3657 structure we created. */
3660 vn_reference_insert_pieces (tree vuse
, alias_set_type set
,
3661 alias_set_type base_set
, tree type
,
3662 vec
<vn_reference_op_s
> operands
,
3663 tree result
, unsigned int value_id
)
3666 vn_reference_s
**slot
;
3669 vr1
= XOBNEW (&vn_tables_obstack
, vn_reference_s
);
3670 vr1
->value_id
= value_id
;
3671 vr1
->vuse
= vuse_ssa_val (vuse
);
3672 vr1
->operands
= valueize_refs (operands
);
3674 vr1
->punned
= false;
3676 vr1
->base_set
= base_set
;
3677 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
3678 if (result
&& TREE_CODE (result
) == SSA_NAME
)
3679 result
= SSA_VAL (result
);
3680 vr1
->result
= result
;
3682 slot
= valid_info
->references
->find_slot_with_hash (vr1
, vr1
->hashcode
,
3685 /* At this point we should have all the things inserted that we have
3686 seen before, and we should never try inserting something that
3688 gcc_assert (!*slot
);
3691 vr1
->next
= last_inserted_ref
;
3692 last_inserted_ref
= vr1
;
3696 /* Compute and return the hash value for nary operation VBO1. */
3699 vn_nary_op_compute_hash (const vn_nary_op_t vno1
)
3701 inchash::hash hstate
;
3704 for (i
= 0; i
< vno1
->length
; ++i
)
3705 if (TREE_CODE (vno1
->op
[i
]) == SSA_NAME
)
3706 vno1
->op
[i
] = SSA_VAL (vno1
->op
[i
]);
3708 if (((vno1
->length
== 2
3709 && commutative_tree_code (vno1
->opcode
))
3710 || (vno1
->length
== 3
3711 && commutative_ternary_tree_code (vno1
->opcode
)))
3712 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1]))
3713 std::swap (vno1
->op
[0], vno1
->op
[1]);
3714 else if (TREE_CODE_CLASS (vno1
->opcode
) == tcc_comparison
3715 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1]))
3717 std::swap (vno1
->op
[0], vno1
->op
[1]);
3718 vno1
->opcode
= swap_tree_comparison (vno1
->opcode
);
3721 hstate
.add_int (vno1
->opcode
);
3722 for (i
= 0; i
< vno1
->length
; ++i
)
3723 inchash::add_expr (vno1
->op
[i
], hstate
);
3725 return hstate
.end ();
3728 /* Compare nary operations VNO1 and VNO2 and return true if they are
3732 vn_nary_op_eq (const_vn_nary_op_t
const vno1
, const_vn_nary_op_t
const vno2
)
3736 if (vno1
->hashcode
!= vno2
->hashcode
)
3739 if (vno1
->length
!= vno2
->length
)
3742 if (vno1
->opcode
!= vno2
->opcode
3743 || !types_compatible_p (vno1
->type
, vno2
->type
))
3746 for (i
= 0; i
< vno1
->length
; ++i
)
3747 if (!expressions_equal_p (vno1
->op
[i
], vno2
->op
[i
]))
3750 /* BIT_INSERT_EXPR has an implict operand as the type precision
3751 of op1. Need to check to make sure they are the same. */
3752 if (vno1
->opcode
== BIT_INSERT_EXPR
3753 && TREE_CODE (vno1
->op
[1]) == INTEGER_CST
3754 && TYPE_PRECISION (TREE_TYPE (vno1
->op
[1]))
3755 != TYPE_PRECISION (TREE_TYPE (vno2
->op
[1])))
3761 /* Initialize VNO from the pieces provided. */
3764 init_vn_nary_op_from_pieces (vn_nary_op_t vno
, unsigned int length
,
3765 enum tree_code code
, tree type
, tree
*ops
)
3768 vno
->length
= length
;
3770 memcpy (&vno
->op
[0], ops
, sizeof (tree
) * length
);
3773 /* Return the number of operands for a vn_nary ops structure from STMT. */
3776 vn_nary_length_from_stmt (gimple
*stmt
)
3778 switch (gimple_assign_rhs_code (stmt
))
3782 case VIEW_CONVERT_EXPR
:
3789 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
3792 return gimple_num_ops (stmt
) - 1;
3796 /* Initialize VNO from STMT. */
3799 init_vn_nary_op_from_stmt (vn_nary_op_t vno
, gimple
*stmt
)
3803 vno
->opcode
= gimple_assign_rhs_code (stmt
);
3804 vno
->type
= gimple_expr_type (stmt
);
3805 switch (vno
->opcode
)
3809 case VIEW_CONVERT_EXPR
:
3811 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
3816 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
3817 vno
->op
[1] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1);
3818 vno
->op
[2] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
3822 vno
->length
= CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
3823 for (i
= 0; i
< vno
->length
; ++i
)
3824 vno
->op
[i
] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt
), i
)->value
;
3828 gcc_checking_assert (!gimple_assign_single_p (stmt
));
3829 vno
->length
= gimple_num_ops (stmt
) - 1;
3830 for (i
= 0; i
< vno
->length
; ++i
)
3831 vno
->op
[i
] = gimple_op (stmt
, i
+ 1);
3835 /* Compute the hashcode for VNO and look for it in the hash table;
3836 return the resulting value number if it exists in the hash table.
3837 Return NULL_TREE if it does not exist in the hash table or if the
3838 result field of the operation is NULL. VNRESULT will contain the
3839 vn_nary_op_t from the hashtable if it exists. */
3842 vn_nary_op_lookup_1 (vn_nary_op_t vno
, vn_nary_op_t
*vnresult
)
3844 vn_nary_op_s
**slot
;
3849 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
3850 slot
= valid_info
->nary
->find_slot_with_hash (vno
, vno
->hashcode
, NO_INSERT
);
3855 return (*slot
)->predicated_values
? NULL_TREE
: (*slot
)->u
.result
;
3858 /* Lookup a n-ary operation by its pieces and return the resulting value
3859 number if it exists in the hash table. Return NULL_TREE if it does
3860 not exist in the hash table or if the result field of the operation
3861 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
3865 vn_nary_op_lookup_pieces (unsigned int length
, enum tree_code code
,
3866 tree type
, tree
*ops
, vn_nary_op_t
*vnresult
)
3868 vn_nary_op_t vno1
= XALLOCAVAR (struct vn_nary_op_s
,
3869 sizeof_vn_nary_op (length
));
3870 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
3871 return vn_nary_op_lookup_1 (vno1
, vnresult
);
3874 /* Lookup the rhs of STMT in the current hash table, and return the resulting
3875 value number if it exists in the hash table. Return NULL_TREE if
3876 it does not exist in the hash table. VNRESULT will contain the
3877 vn_nary_op_t from the hashtable if it exists. */
3880 vn_nary_op_lookup_stmt (gimple
*stmt
, vn_nary_op_t
*vnresult
)
3883 = XALLOCAVAR (struct vn_nary_op_s
,
3884 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt
)));
3885 init_vn_nary_op_from_stmt (vno1
, stmt
);
3886 return vn_nary_op_lookup_1 (vno1
, vnresult
);
3889 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
3892 alloc_vn_nary_op_noinit (unsigned int length
, struct obstack
*stack
)
3894 return (vn_nary_op_t
) obstack_alloc (stack
, sizeof_vn_nary_op (length
));
3897 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
3901 alloc_vn_nary_op (unsigned int length
, tree result
, unsigned int value_id
)
3903 vn_nary_op_t vno1
= alloc_vn_nary_op_noinit (length
, &vn_tables_obstack
);
3905 vno1
->value_id
= value_id
;
3906 vno1
->length
= length
;
3907 vno1
->predicated_values
= 0;
3908 vno1
->u
.result
= result
;
3913 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
3914 VNO->HASHCODE first. */
3917 vn_nary_op_insert_into (vn_nary_op_t vno
, vn_nary_op_table_type
*table
,
3920 vn_nary_op_s
**slot
;
3924 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
3925 gcc_assert (! vno
->predicated_values
3926 || (! vno
->u
.values
->next
3927 && vno
->u
.values
->n
== 1));
3930 slot
= table
->find_slot_with_hash (vno
, vno
->hashcode
, INSERT
);
3931 vno
->unwind_to
= *slot
;
3934 /* Prefer non-predicated values.
3935 ??? Only if those are constant, otherwise, with constant predicated
3936 value, turn them into predicated values with entry-block validity
3937 (??? but we always find the first valid result currently). */
3938 if ((*slot
)->predicated_values
3939 && ! vno
->predicated_values
)
3941 /* ??? We cannot remove *slot from the unwind stack list.
3942 For the moment we deal with this by skipping not found
3943 entries but this isn't ideal ... */
3945 /* ??? Maintain a stack of states we can unwind in
3946 vn_nary_op_s? But how far do we unwind? In reality
3947 we need to push change records somewhere... Or not
3948 unwind vn_nary_op_s and linking them but instead
3949 unwind the results "list", linking that, which also
3950 doesn't move on hashtable resize. */
3951 /* We can also have a ->unwind_to recording *slot there.
3952 That way we can make u.values a fixed size array with
3953 recording the number of entries but of course we then
3954 have always N copies for each unwind_to-state. Or we
3955 make sure to only ever append and each unwinding will
3956 pop off one entry (but how to deal with predicated
3957 replaced with non-predicated here?) */
3958 vno
->next
= last_inserted_nary
;
3959 last_inserted_nary
= vno
;
3962 else if (vno
->predicated_values
3963 && ! (*slot
)->predicated_values
)
3965 else if (vno
->predicated_values
3966 && (*slot
)->predicated_values
)
3968 /* ??? Factor this all into a insert_single_predicated_value
3970 gcc_assert (!vno
->u
.values
->next
&& vno
->u
.values
->n
== 1);
3972 = BASIC_BLOCK_FOR_FN (cfun
, vno
->u
.values
->valid_dominated_by_p
[0]);
3973 vn_pval
*nval
= vno
->u
.values
;
3974 vn_pval
**next
= &vno
->u
.values
;
3976 for (vn_pval
*val
= (*slot
)->u
.values
; val
; val
= val
->next
)
3978 if (expressions_equal_p (val
->result
, vno
->u
.values
->result
))
3981 for (unsigned i
= 0; i
< val
->n
; ++i
)
3984 = BASIC_BLOCK_FOR_FN (cfun
,
3985 val
->valid_dominated_by_p
[i
]);
3986 if (dominated_by_p (CDI_DOMINATORS
, vno_bb
, val_bb
))
3987 /* Value registered with more generic predicate. */
3989 else if (dominated_by_p (CDI_DOMINATORS
, val_bb
, vno_bb
))
3990 /* Shouldn't happen, we insert in RPO order. */
3994 *next
= (vn_pval
*) obstack_alloc (&vn_tables_obstack
,
3996 + val
->n
* sizeof (int));
3997 (*next
)->next
= NULL
;
3998 (*next
)->result
= val
->result
;
3999 (*next
)->n
= val
->n
+ 1;
4000 memcpy ((*next
)->valid_dominated_by_p
,
4001 val
->valid_dominated_by_p
,
4002 val
->n
* sizeof (int));
4003 (*next
)->valid_dominated_by_p
[val
->n
] = vno_bb
->index
;
4004 next
= &(*next
)->next
;
4005 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4006 fprintf (dump_file
, "Appending predicate to value.\n");
4009 /* Copy other predicated values. */
4010 *next
= (vn_pval
*) obstack_alloc (&vn_tables_obstack
,
4012 + (val
->n
-1) * sizeof (int));
4013 memcpy (*next
, val
, sizeof (vn_pval
) + (val
->n
-1) * sizeof (int));
4014 (*next
)->next
= NULL
;
4015 next
= &(*next
)->next
;
4021 vno
->next
= last_inserted_nary
;
4022 last_inserted_nary
= vno
;
4026 /* While we do not want to insert things twice it's awkward to
4027 avoid it in the case where visit_nary_op pattern-matches stuff
4028 and ends up simplifying the replacement to itself. We then
4029 get two inserts, one from visit_nary_op and one from
4030 vn_nary_build_or_lookup.
4031 So allow inserts with the same value number. */
4032 if ((*slot
)->u
.result
== vno
->u
.result
)
4036 /* ??? There's also optimistic vs. previous commited state merging
4037 that is problematic for the case of unwinding. */
4039 /* ??? We should return NULL if we do not use 'vno' and have the
4040 caller release it. */
4041 gcc_assert (!*slot
);
4044 vno
->next
= last_inserted_nary
;
4045 last_inserted_nary
= vno
;
4049 /* Insert a n-ary operation into the current hash table using it's
4050 pieces. Return the vn_nary_op_t structure we created and put in
4054 vn_nary_op_insert_pieces (unsigned int length
, enum tree_code code
,
4055 tree type
, tree
*ops
,
4056 tree result
, unsigned int value_id
)
4058 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, result
, value_id
);
4059 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
4060 return vn_nary_op_insert_into (vno1
, valid_info
->nary
, true);
4064 vn_nary_op_insert_pieces_predicated (unsigned int length
, enum tree_code code
,
4065 tree type
, tree
*ops
,
4066 tree result
, unsigned int value_id
,
4069 /* ??? Currently tracking BBs. */
4070 if (! single_pred_p (pred_e
->dest
))
4072 /* Never record for backedges. */
4073 if (pred_e
->flags
& EDGE_DFS_BACK
)
4078 /* Ignore backedges. */
4079 FOR_EACH_EDGE (e
, ei
, pred_e
->dest
->preds
)
4080 if (! dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
4085 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
4086 /* ??? Fix dumping, but currently we only get comparisons. */
4087 && TREE_CODE_CLASS (code
) == tcc_comparison
)
4089 fprintf (dump_file
, "Recording on edge %d->%d ", pred_e
->src
->index
,
4090 pred_e
->dest
->index
);
4091 print_generic_expr (dump_file
, ops
[0], TDF_SLIM
);
4092 fprintf (dump_file
, " %s ", get_tree_code_name (code
));
4093 print_generic_expr (dump_file
, ops
[1], TDF_SLIM
);
4094 fprintf (dump_file
, " == %s\n",
4095 integer_zerop (result
) ? "false" : "true");
4097 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, NULL_TREE
, value_id
);
4098 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
4099 vno1
->predicated_values
= 1;
4100 vno1
->u
.values
= (vn_pval
*) obstack_alloc (&vn_tables_obstack
,
4102 vno1
->u
.values
->next
= NULL
;
4103 vno1
->u
.values
->result
= result
;
4104 vno1
->u
.values
->n
= 1;
4105 vno1
->u
.values
->valid_dominated_by_p
[0] = pred_e
->dest
->index
;
4106 return vn_nary_op_insert_into (vno1
, valid_info
->nary
, true);
4110 dominated_by_p_w_unex (basic_block bb1
, basic_block bb2
);
4113 vn_nary_op_get_predicated_value (vn_nary_op_t vno
, basic_block bb
)
4115 if (! vno
->predicated_values
)
4116 return vno
->u
.result
;
4117 for (vn_pval
*val
= vno
->u
.values
; val
; val
= val
->next
)
4118 for (unsigned i
= 0; i
< val
->n
; ++i
)
4119 if (dominated_by_p_w_unex (bb
,
4121 (cfun
, val
->valid_dominated_by_p
[i
])))
4126 /* Insert the rhs of STMT into the current hash table with a value number of
4130 vn_nary_op_insert_stmt (gimple
*stmt
, tree result
)
4133 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt
),
4134 result
, VN_INFO (result
)->value_id
);
4135 init_vn_nary_op_from_stmt (vno1
, stmt
);
4136 return vn_nary_op_insert_into (vno1
, valid_info
->nary
, true);
4139 /* Compute a hashcode for PHI operation VP1 and return it. */
4141 static inline hashval_t
4142 vn_phi_compute_hash (vn_phi_t vp1
)
4144 inchash::hash hstate
;
4150 hstate
.add_int (EDGE_COUNT (vp1
->block
->preds
));
4151 switch (EDGE_COUNT (vp1
->block
->preds
))
4156 if (vp1
->block
->loop_father
->header
== vp1
->block
)
4162 hstate
.add_int (vp1
->block
->index
);
4165 /* If all PHI arguments are constants we need to distinguish
4166 the PHI node via its type. */
4168 hstate
.merge_hash (vn_hash_type (type
));
4170 FOR_EACH_EDGE (e
, ei
, vp1
->block
->preds
)
4172 /* Don't hash backedge values they need to be handled as VN_TOP
4173 for optimistic value-numbering. */
4174 if (e
->flags
& EDGE_DFS_BACK
)
4177 phi1op
= vp1
->phiargs
[e
->dest_idx
];
4178 if (phi1op
== VN_TOP
)
4180 inchash::add_expr (phi1op
, hstate
);
4183 return hstate
.end ();
4187 /* Return true if COND1 and COND2 represent the same condition, set
4188 *INVERTED_P if one needs to be inverted to make it the same as
4192 cond_stmts_equal_p (gcond
*cond1
, tree lhs1
, tree rhs1
,
4193 gcond
*cond2
, tree lhs2
, tree rhs2
, bool *inverted_p
)
4195 enum tree_code code1
= gimple_cond_code (cond1
);
4196 enum tree_code code2
= gimple_cond_code (cond2
);
4198 *inverted_p
= false;
4201 else if (code1
== swap_tree_comparison (code2
))
4202 std::swap (lhs2
, rhs2
);
4203 else if (code1
== invert_tree_comparison (code2
, HONOR_NANS (lhs2
)))
4205 else if (code1
== invert_tree_comparison
4206 (swap_tree_comparison (code2
), HONOR_NANS (lhs2
)))
4208 std::swap (lhs2
, rhs2
);
4214 return ((expressions_equal_p (lhs1
, lhs2
)
4215 && expressions_equal_p (rhs1
, rhs2
))
4216 || (commutative_tree_code (code1
)
4217 && expressions_equal_p (lhs1
, rhs2
)
4218 && expressions_equal_p (rhs1
, lhs2
)));
4221 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
4224 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
)
4226 if (vp1
->hashcode
!= vp2
->hashcode
)
4229 if (vp1
->block
!= vp2
->block
)
4231 if (EDGE_COUNT (vp1
->block
->preds
) != EDGE_COUNT (vp2
->block
->preds
))
4234 switch (EDGE_COUNT (vp1
->block
->preds
))
4237 /* Single-arg PHIs are just copies. */
4242 /* Rule out backedges into the PHI. */
4243 if (vp1
->block
->loop_father
->header
== vp1
->block
4244 || vp2
->block
->loop_father
->header
== vp2
->block
)
4247 /* If the PHI nodes do not have compatible types
4248 they are not the same. */
4249 if (!types_compatible_p (vp1
->type
, vp2
->type
))
4253 = get_immediate_dominator (CDI_DOMINATORS
, vp1
->block
);
4255 = get_immediate_dominator (CDI_DOMINATORS
, vp2
->block
);
4256 /* If the immediate dominator end in switch stmts multiple
4257 values may end up in the same PHI arg via intermediate
4259 if (EDGE_COUNT (idom1
->succs
) != 2
4260 || EDGE_COUNT (idom2
->succs
) != 2)
4263 /* Verify the controlling stmt is the same. */
4264 gcond
*last1
= safe_dyn_cast
<gcond
*> (last_stmt (idom1
));
4265 gcond
*last2
= safe_dyn_cast
<gcond
*> (last_stmt (idom2
));
4266 if (! last1
|| ! last2
)
4269 if (! cond_stmts_equal_p (last1
, vp1
->cclhs
, vp1
->ccrhs
,
4270 last2
, vp2
->cclhs
, vp2
->ccrhs
,
4274 /* Get at true/false controlled edges into the PHI. */
4275 edge te1
, te2
, fe1
, fe2
;
4276 if (! extract_true_false_controlled_edges (idom1
, vp1
->block
,
4278 || ! extract_true_false_controlled_edges (idom2
, vp2
->block
,
4282 /* Swap edges if the second condition is the inverted of the
4285 std::swap (te2
, fe2
);
4287 /* ??? Handle VN_TOP specially. */
4288 if (! expressions_equal_p (vp1
->phiargs
[te1
->dest_idx
],
4289 vp2
->phiargs
[te2
->dest_idx
])
4290 || ! expressions_equal_p (vp1
->phiargs
[fe1
->dest_idx
],
4291 vp2
->phiargs
[fe2
->dest_idx
]))
4302 /* If the PHI nodes do not have compatible types
4303 they are not the same. */
4304 if (!types_compatible_p (vp1
->type
, vp2
->type
))
4307 /* Any phi in the same block will have it's arguments in the
4308 same edge order, because of how we store phi nodes. */
4309 unsigned nargs
= EDGE_COUNT (vp1
->block
->preds
);
4310 for (unsigned i
= 0; i
< nargs
; ++i
)
4312 tree phi1op
= vp1
->phiargs
[i
];
4313 tree phi2op
= vp2
->phiargs
[i
];
4314 if (phi1op
== phi2op
)
4316 if (!expressions_equal_p (phi1op
, phi2op
))
4323 /* Lookup PHI in the current hash table, and return the resulting
4324 value number if it exists in the hash table. Return NULL_TREE if
4325 it does not exist in the hash table. */
4328 vn_phi_lookup (gimple
*phi
, bool backedges_varying_p
)
4331 struct vn_phi_s
*vp1
;
4335 vp1
= XALLOCAVAR (struct vn_phi_s
,
4336 sizeof (struct vn_phi_s
)
4337 + (gimple_phi_num_args (phi
) - 1) * sizeof (tree
));
4339 /* Canonicalize the SSA_NAME's to their value number. */
4340 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
4342 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
4343 if (TREE_CODE (def
) == SSA_NAME
4344 && (!backedges_varying_p
|| !(e
->flags
& EDGE_DFS_BACK
)))
4345 def
= SSA_VAL (def
);
4346 vp1
->phiargs
[e
->dest_idx
] = def
;
4348 vp1
->type
= TREE_TYPE (gimple_phi_result (phi
));
4349 vp1
->block
= gimple_bb (phi
);
4350 /* Extract values of the controlling condition. */
4351 vp1
->cclhs
= NULL_TREE
;
4352 vp1
->ccrhs
= NULL_TREE
;
4353 basic_block idom1
= get_immediate_dominator (CDI_DOMINATORS
, vp1
->block
);
4354 if (EDGE_COUNT (idom1
->succs
) == 2)
4355 if (gcond
*last1
= safe_dyn_cast
<gcond
*> (last_stmt (idom1
)))
4357 /* ??? We want to use SSA_VAL here. But possibly not
4359 vp1
->cclhs
= vn_valueize (gimple_cond_lhs (last1
));
4360 vp1
->ccrhs
= vn_valueize (gimple_cond_rhs (last1
));
4362 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
4363 slot
= valid_info
->phis
->find_slot_with_hash (vp1
, vp1
->hashcode
, NO_INSERT
);
4366 return (*slot
)->result
;
4369 /* Insert PHI into the current hash table with a value number of
4373 vn_phi_insert (gimple
*phi
, tree result
, bool backedges_varying_p
)
4376 vn_phi_t vp1
= (vn_phi_t
) obstack_alloc (&vn_tables_obstack
,
4378 + ((gimple_phi_num_args (phi
) - 1)
4383 /* Canonicalize the SSA_NAME's to their value number. */
4384 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
4386 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
4387 if (TREE_CODE (def
) == SSA_NAME
4388 && (!backedges_varying_p
|| !(e
->flags
& EDGE_DFS_BACK
)))
4389 def
= SSA_VAL (def
);
4390 vp1
->phiargs
[e
->dest_idx
] = def
;
4392 vp1
->value_id
= VN_INFO (result
)->value_id
;
4393 vp1
->type
= TREE_TYPE (gimple_phi_result (phi
));
4394 vp1
->block
= gimple_bb (phi
);
4395 /* Extract values of the controlling condition. */
4396 vp1
->cclhs
= NULL_TREE
;
4397 vp1
->ccrhs
= NULL_TREE
;
4398 basic_block idom1
= get_immediate_dominator (CDI_DOMINATORS
, vp1
->block
);
4399 if (EDGE_COUNT (idom1
->succs
) == 2)
4400 if (gcond
*last1
= safe_dyn_cast
<gcond
*> (last_stmt (idom1
)))
4402 /* ??? We want to use SSA_VAL here. But possibly not
4404 vp1
->cclhs
= vn_valueize (gimple_cond_lhs (last1
));
4405 vp1
->ccrhs
= vn_valueize (gimple_cond_rhs (last1
));
4407 vp1
->result
= result
;
4408 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
4410 slot
= valid_info
->phis
->find_slot_with_hash (vp1
, vp1
->hashcode
, INSERT
);
4411 gcc_assert (!*slot
);
4414 vp1
->next
= last_inserted_phi
;
4415 last_inserted_phi
= vp1
;
4420 /* Return true if BB1 is dominated by BB2 taking into account edges
4421 that are not executable. */
4424 dominated_by_p_w_unex (basic_block bb1
, basic_block bb2
)
4429 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
4432 /* Before iterating we'd like to know if there exists a
4433 (executable) path from bb2 to bb1 at all, if not we can
4434 directly return false. For now simply iterate once. */
4436 /* Iterate to the single executable bb1 predecessor. */
4437 if (EDGE_COUNT (bb1
->preds
) > 1)
4440 FOR_EACH_EDGE (e
, ei
, bb1
->preds
)
4441 if (e
->flags
& EDGE_EXECUTABLE
)
4454 /* Re-do the dominance check with changed bb1. */
4455 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
4460 /* Iterate to the single executable bb2 successor. */
4462 FOR_EACH_EDGE (e
, ei
, bb2
->succs
)
4463 if (e
->flags
& EDGE_EXECUTABLE
)
4474 /* Verify the reached block is only reached through succe.
4475 If there is only one edge we can spare us the dominator
4476 check and iterate directly. */
4477 if (EDGE_COUNT (succe
->dest
->preds
) > 1)
4479 FOR_EACH_EDGE (e
, ei
, succe
->dest
->preds
)
4481 && (e
->flags
& EDGE_EXECUTABLE
))
4491 /* Re-do the dominance check with changed bb2. */
4492 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
4497 /* We could now iterate updating bb1 / bb2. */
4501 /* Set the value number of FROM to TO, return true if it has changed
4505 set_ssa_val_to (tree from
, tree to
)
4507 vn_ssa_aux_t from_info
= VN_INFO (from
);
4508 tree currval
= from_info
->valnum
; // SSA_VAL (from)
4509 poly_int64 toff
, coff
;
4510 bool curr_undefined
= false;
4511 bool curr_invariant
= false;
4513 /* The only thing we allow as value numbers are ssa_names
4514 and invariants. So assert that here. We don't allow VN_TOP
4515 as visiting a stmt should produce a value-number other than
4517 ??? Still VN_TOP can happen for unreachable code, so force
4518 it to varying in that case. Not all code is prepared to
4519 get VN_TOP on valueization. */
4522 /* ??? When iterating and visiting PHI <undef, backedge-value>
4523 for the first time we rightfully get VN_TOP and we need to
4524 preserve that to optimize for example gcc.dg/tree-ssa/ssa-sccvn-2.c.
4525 With SCCVN we were simply lucky we iterated the other PHI
4526 cycles first and thus visited the backedge-value DEF. */
4527 if (currval
== VN_TOP
)
4529 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4530 fprintf (dump_file
, "Forcing value number to varying on "
4531 "receiving VN_TOP\n");
4535 gcc_checking_assert (to
!= NULL_TREE
4536 && ((TREE_CODE (to
) == SSA_NAME
4537 && (to
== from
|| SSA_VAL (to
) == to
))
4538 || is_gimple_min_invariant (to
)));
4542 if (currval
== from
)
4544 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4546 fprintf (dump_file
, "Not changing value number of ");
4547 print_generic_expr (dump_file
, from
);
4548 fprintf (dump_file
, " from VARYING to ");
4549 print_generic_expr (dump_file
, to
);
4550 fprintf (dump_file
, "\n");
4554 curr_invariant
= is_gimple_min_invariant (currval
);
4555 curr_undefined
= (TREE_CODE (currval
) == SSA_NAME
4556 && ssa_undefined_value_p (currval
, false));
4557 if (currval
!= VN_TOP
4560 && is_gimple_min_invariant (to
))
4562 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4564 fprintf (dump_file
, "Forcing VARYING instead of changing "
4565 "value number of ");
4566 print_generic_expr (dump_file
, from
);
4567 fprintf (dump_file
, " from ");
4568 print_generic_expr (dump_file
, currval
);
4569 fprintf (dump_file
, " (non-constant) to ");
4570 print_generic_expr (dump_file
, to
);
4571 fprintf (dump_file
, " (constant)\n");
4575 else if (currval
!= VN_TOP
4577 && TREE_CODE (to
) == SSA_NAME
4578 && ssa_undefined_value_p (to
, false))
4580 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4582 fprintf (dump_file
, "Forcing VARYING instead of changing "
4583 "value number of ");
4584 print_generic_expr (dump_file
, from
);
4585 fprintf (dump_file
, " from ");
4586 print_generic_expr (dump_file
, currval
);
4587 fprintf (dump_file
, " (non-undefined) to ");
4588 print_generic_expr (dump_file
, to
);
4589 fprintf (dump_file
, " (undefined)\n");
4593 else if (TREE_CODE (to
) == SSA_NAME
4594 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to
))
4599 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4601 fprintf (dump_file
, "Setting value number of ");
4602 print_generic_expr (dump_file
, from
);
4603 fprintf (dump_file
, " to ");
4604 print_generic_expr (dump_file
, to
);
4608 && !operand_equal_p (currval
, to
, 0)
4609 /* Different undefined SSA names are not actually different. See
4610 PR82320 for a testcase were we'd otherwise not terminate iteration. */
4612 && TREE_CODE (to
) == SSA_NAME
4613 && ssa_undefined_value_p (to
, false))
4614 /* ??? For addresses involving volatile objects or types operand_equal_p
4615 does not reliably detect ADDR_EXPRs as equal. We know we are only
4616 getting invariant gimple addresses here, so can use
4617 get_addr_base_and_unit_offset to do this comparison. */
4618 && !(TREE_CODE (currval
) == ADDR_EXPR
4619 && TREE_CODE (to
) == ADDR_EXPR
4620 && (get_addr_base_and_unit_offset (TREE_OPERAND (currval
, 0), &coff
)
4621 == get_addr_base_and_unit_offset (TREE_OPERAND (to
, 0), &toff
))
4622 && known_eq (coff
, toff
)))
4625 && currval
!= VN_TOP
4627 /* We do not want to allow lattice transitions from one value
4628 to another since that may lead to not terminating iteration
4629 (see PR95049). Since there's no convenient way to check
4630 for the allowed transition of VAL -> PHI (loop entry value,
4631 same on two PHIs, to same PHI result) we restrict the check
4634 && is_gimple_min_invariant (to
))
4636 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4637 fprintf (dump_file
, " forced VARYING");
4640 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4641 fprintf (dump_file
, " (changed)\n");
4642 from_info
->valnum
= to
;
4645 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4646 fprintf (dump_file
, "\n");
4650 /* Set all definitions in STMT to value number to themselves.
4651 Return true if a value number changed. */
4654 defs_to_varying (gimple
*stmt
)
4656 bool changed
= false;
4660 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
4662 tree def
= DEF_FROM_PTR (defp
);
4663 changed
|= set_ssa_val_to (def
, def
);
4668 /* Visit a copy between LHS and RHS, return true if the value number
4672 visit_copy (tree lhs
, tree rhs
)
4675 rhs
= SSA_VAL (rhs
);
4677 return set_ssa_val_to (lhs
, rhs
);
4680 /* Lookup a value for OP in type WIDE_TYPE where the value in type of OP
4684 valueized_wider_op (tree wide_type
, tree op
, bool allow_truncate
)
4686 if (TREE_CODE (op
) == SSA_NAME
)
4687 op
= vn_valueize (op
);
4689 /* Either we have the op widened available. */
4692 tree tem
= vn_nary_op_lookup_pieces (1, NOP_EXPR
,
4693 wide_type
, ops
, NULL
);
4697 /* Or the op is truncated from some existing value. */
4698 if (allow_truncate
&& TREE_CODE (op
) == SSA_NAME
)
4700 gimple
*def
= SSA_NAME_DEF_STMT (op
);
4701 if (is_gimple_assign (def
)
4702 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def
)))
4704 tem
= gimple_assign_rhs1 (def
);
4705 if (useless_type_conversion_p (wide_type
, TREE_TYPE (tem
)))
4707 if (TREE_CODE (tem
) == SSA_NAME
)
4708 tem
= vn_valueize (tem
);
4714 /* For constants simply extend it. */
4715 if (TREE_CODE (op
) == INTEGER_CST
)
4716 return wide_int_to_tree (wide_type
, wi::to_wide (op
));
4721 /* Visit a nary operator RHS, value number it, and return true if the
4722 value number of LHS has changed as a result. */
4725 visit_nary_op (tree lhs
, gassign
*stmt
)
4727 vn_nary_op_t vnresult
;
4728 tree result
= vn_nary_op_lookup_stmt (stmt
, &vnresult
);
4729 if (! result
&& vnresult
)
4730 result
= vn_nary_op_get_predicated_value (vnresult
, gimple_bb (stmt
));
4732 return set_ssa_val_to (lhs
, result
);
4734 /* Do some special pattern matching for redundancies of operations
4735 in different types. */
4736 enum tree_code code
= gimple_assign_rhs_code (stmt
);
4737 tree type
= TREE_TYPE (lhs
);
4738 tree rhs1
= gimple_assign_rhs1 (stmt
);
4742 /* Match arithmetic done in a different type where we can easily
4743 substitute the result from some earlier sign-changed or widened
4745 if (INTEGRAL_TYPE_P (type
)
4746 && TREE_CODE (rhs1
) == SSA_NAME
4747 /* We only handle sign-changes, zero-extension -> & mask or
4748 sign-extension if we know the inner operation doesn't
4750 && (((TYPE_UNSIGNED (TREE_TYPE (rhs1
))
4751 || (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
4752 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (rhs1
))))
4753 && TYPE_PRECISION (type
) > TYPE_PRECISION (TREE_TYPE (rhs1
)))
4754 || TYPE_PRECISION (type
) == TYPE_PRECISION (TREE_TYPE (rhs1
))))
4756 gassign
*def
= dyn_cast
<gassign
*> (SSA_NAME_DEF_STMT (rhs1
));
4758 && (gimple_assign_rhs_code (def
) == PLUS_EXPR
4759 || gimple_assign_rhs_code (def
) == MINUS_EXPR
4760 || gimple_assign_rhs_code (def
) == MULT_EXPR
))
4763 /* When requiring a sign-extension we cannot model a
4764 previous truncation with a single op so don't bother. */
4765 bool allow_truncate
= TYPE_UNSIGNED (TREE_TYPE (rhs1
));
4766 /* Either we have the op widened available. */
4767 ops
[0] = valueized_wider_op (type
, gimple_assign_rhs1 (def
),
4770 ops
[1] = valueized_wider_op (type
, gimple_assign_rhs2 (def
),
4772 if (ops
[0] && ops
[1])
4774 ops
[0] = vn_nary_op_lookup_pieces
4775 (2, gimple_assign_rhs_code (def
), type
, ops
, NULL
);
4776 /* We have wider operation available. */
4778 /* If the leader is a wrapping operation we can
4779 insert it for code hoisting w/o introducing
4780 undefined overflow. If it is not it has to
4781 be available. See PR86554. */
4782 && (TYPE_OVERFLOW_WRAPS (TREE_TYPE (ops
[0]))
4783 || (rpo_avail
&& vn_context_bb
4784 && rpo_avail
->eliminate_avail (vn_context_bb
,
4787 unsigned lhs_prec
= TYPE_PRECISION (type
);
4788 unsigned rhs_prec
= TYPE_PRECISION (TREE_TYPE (rhs1
));
4789 if (lhs_prec
== rhs_prec
4790 || (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
4791 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (rhs1
))))
4793 gimple_match_op
match_op (gimple_match_cond::UNCOND
,
4794 NOP_EXPR
, type
, ops
[0]);
4795 result
= vn_nary_build_or_lookup (&match_op
);
4798 bool changed
= set_ssa_val_to (lhs
, result
);
4799 vn_nary_op_insert_stmt (stmt
, result
);
4805 tree mask
= wide_int_to_tree
4806 (type
, wi::mask (rhs_prec
, false, lhs_prec
));
4807 gimple_match_op
match_op (gimple_match_cond::UNCOND
,
4811 result
= vn_nary_build_or_lookup (&match_op
);
4814 bool changed
= set_ssa_val_to (lhs
, result
);
4815 vn_nary_op_insert_stmt (stmt
, result
);
4825 if (INTEGRAL_TYPE_P (type
)
4826 && TREE_CODE (rhs1
) == SSA_NAME
4827 && TREE_CODE (gimple_assign_rhs2 (stmt
)) == INTEGER_CST
4828 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
)
4829 && default_vn_walk_kind
!= VN_NOWALK
4831 && BITS_PER_UNIT
== 8
4832 && BYTES_BIG_ENDIAN
== WORDS_BIG_ENDIAN
4833 && !integer_all_onesp (gimple_assign_rhs2 (stmt
))
4834 && !integer_zerop (gimple_assign_rhs2 (stmt
)))
4836 gassign
*ass
= dyn_cast
<gassign
*> (SSA_NAME_DEF_STMT (rhs1
));
4838 && !gimple_has_volatile_ops (ass
)
4839 && vn_get_stmt_kind (ass
) == VN_REFERENCE
)
4841 tree last_vuse
= gimple_vuse (ass
);
4842 tree op
= gimple_assign_rhs1 (ass
);
4843 tree result
= vn_reference_lookup (op
, gimple_vuse (ass
),
4844 default_vn_walk_kind
,
4845 NULL
, true, &last_vuse
,
4846 gimple_assign_rhs2 (stmt
));
4848 && useless_type_conversion_p (TREE_TYPE (result
),
4850 return set_ssa_val_to (lhs
, result
);
4854 case TRUNC_DIV_EXPR
:
4855 if (TYPE_UNSIGNED (type
))
4860 /* Match up ([-]a){/,*}([-])b with v=a{/,*}b, replacing it with -v. */
4861 if (! HONOR_SIGN_DEPENDENT_ROUNDING (type
))
4865 rhs
[1] = gimple_assign_rhs2 (stmt
);
4866 for (unsigned i
= 0; i
<= 1; ++i
)
4868 unsigned j
= i
== 0 ? 1 : 0;
4870 gimple_match_op
match_op (gimple_match_cond::UNCOND
,
4871 NEGATE_EXPR
, type
, rhs
[i
]);
4872 ops
[i
] = vn_nary_build_or_lookup_1 (&match_op
, false);
4875 && (ops
[0] = vn_nary_op_lookup_pieces (2, code
,
4878 gimple_match_op
match_op (gimple_match_cond::UNCOND
,
4879 NEGATE_EXPR
, type
, ops
[0]);
4880 result
= vn_nary_build_or_lookup (&match_op
);
4883 bool changed
= set_ssa_val_to (lhs
, result
);
4884 vn_nary_op_insert_stmt (stmt
, result
);
4895 bool changed
= set_ssa_val_to (lhs
, lhs
);
4896 vn_nary_op_insert_stmt (stmt
, lhs
);
4900 /* Visit a call STMT storing into LHS. Return true if the value number
4901 of the LHS has changed as a result. */
4904 visit_reference_op_call (tree lhs
, gcall
*stmt
)
4906 bool changed
= false;
4907 struct vn_reference_s vr1
;
4908 vn_reference_t vnresult
= NULL
;
4909 tree vdef
= gimple_vdef (stmt
);
4911 /* Non-ssa lhs is handled in copy_reference_ops_from_call. */
4912 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
4915 vn_reference_lookup_call (stmt
, &vnresult
, &vr1
);
4918 if (vnresult
->result_vdef
&& vdef
)
4919 changed
|= set_ssa_val_to (vdef
, vnresult
->result_vdef
);
4921 /* If the call was discovered to be pure or const reflect
4922 that as far as possible. */
4923 changed
|= set_ssa_val_to (vdef
, vuse_ssa_val (gimple_vuse (stmt
)));
4925 if (!vnresult
->result
&& lhs
)
4926 vnresult
->result
= lhs
;
4928 if (vnresult
->result
&& lhs
)
4929 changed
|= set_ssa_val_to (lhs
, vnresult
->result
);
4934 vn_reference_s
**slot
;
4935 tree vdef_val
= vdef
;
4938 /* If we value numbered an indirect functions function to
4939 one not clobbering memory value number its VDEF to its
4941 tree fn
= gimple_call_fn (stmt
);
4942 if (fn
&& TREE_CODE (fn
) == SSA_NAME
)
4945 if (TREE_CODE (fn
) == ADDR_EXPR
4946 && TREE_CODE (TREE_OPERAND (fn
, 0)) == FUNCTION_DECL
4947 && (flags_from_decl_or_type (TREE_OPERAND (fn
, 0))
4948 & (ECF_CONST
| ECF_PURE
)))
4949 vdef_val
= vuse_ssa_val (gimple_vuse (stmt
));
4951 changed
|= set_ssa_val_to (vdef
, vdef_val
);
4954 changed
|= set_ssa_val_to (lhs
, lhs
);
4955 vr2
= XOBNEW (&vn_tables_obstack
, vn_reference_s
);
4956 vr2
->vuse
= vr1
.vuse
;
4957 /* As we are not walking the virtual operand chain we know the
4958 shared_lookup_references are still original so we can re-use
4960 vr2
->operands
= vr1
.operands
.copy ();
4961 vr2
->type
= vr1
.type
;
4962 vr2
->punned
= vr1
.punned
;
4964 vr2
->base_set
= vr1
.base_set
;
4965 vr2
->hashcode
= vr1
.hashcode
;
4967 vr2
->result_vdef
= vdef_val
;
4969 slot
= valid_info
->references
->find_slot_with_hash (vr2
, vr2
->hashcode
,
4971 gcc_assert (!*slot
);
4973 vr2
->next
= last_inserted_ref
;
4974 last_inserted_ref
= vr2
;
4980 /* Visit a load from a reference operator RHS, part of STMT, value number it,
4981 and return true if the value number of the LHS has changed as a result. */
4984 visit_reference_op_load (tree lhs
, tree op
, gimple
*stmt
)
4986 bool changed
= false;
4991 last_vuse
= gimple_vuse (stmt
);
4992 result
= vn_reference_lookup (op
, gimple_vuse (stmt
),
4993 default_vn_walk_kind
, &res
, true, &last_vuse
);
4995 /* We handle type-punning through unions by value-numbering based
4996 on offset and size of the access. Be prepared to handle a
4997 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
4999 && !useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (op
)))
5001 /* Avoid the type punning in case the result mode has padding where
5002 the op we lookup has not. */
5003 if (maybe_lt (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (result
))),
5004 GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (op
)))))
5008 /* We will be setting the value number of lhs to the value number
5009 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
5010 So first simplify and lookup this expression to see if it
5011 is already available. */
5012 gimple_match_op
res_op (gimple_match_cond::UNCOND
,
5013 VIEW_CONVERT_EXPR
, TREE_TYPE (op
), result
);
5014 result
= vn_nary_build_or_lookup (&res_op
);
5016 && TREE_CODE (result
) == SSA_NAME
5017 && VN_INFO (result
)->needs_insertion
)
5018 /* Track whether this is the canonical expression for different
5019 typed loads. We use that as a stopgap measure for code
5020 hoisting when dealing with floating point loads. */
5024 /* When building the conversion fails avoid inserting the reference
5027 return set_ssa_val_to (lhs
, lhs
);
5031 changed
= set_ssa_val_to (lhs
, result
);
5034 changed
= set_ssa_val_to (lhs
, lhs
);
5035 vn_reference_insert (op
, lhs
, last_vuse
, NULL_TREE
);
5042 /* Visit a store to a reference operator LHS, part of STMT, value number it,
5043 and return true if the value number of the LHS has changed as a result. */
5046 visit_reference_op_store (tree lhs
, tree op
, gimple
*stmt
)
5048 bool changed
= false;
5049 vn_reference_t vnresult
= NULL
;
5051 bool resultsame
= false;
5052 tree vuse
= gimple_vuse (stmt
);
5053 tree vdef
= gimple_vdef (stmt
);
5055 if (TREE_CODE (op
) == SSA_NAME
)
5058 /* First we want to lookup using the *vuses* from the store and see
5059 if there the last store to this location with the same address
5062 The vuses represent the memory state before the store. If the
5063 memory state, address, and value of the store is the same as the
5064 last store to this location, then this store will produce the
5065 same memory state as that store.
5067 In this case the vdef versions for this store are value numbered to those
5068 vuse versions, since they represent the same memory state after
5071 Otherwise, the vdefs for the store are used when inserting into
5072 the table, since the store generates a new memory state. */
5074 vn_reference_lookup (lhs
, vuse
, VN_NOWALK
, &vnresult
, false);
5076 && vnresult
->result
)
5078 tree result
= vnresult
->result
;
5079 gcc_checking_assert (TREE_CODE (result
) != SSA_NAME
5080 || result
== SSA_VAL (result
));
5081 resultsame
= expressions_equal_p (result
, op
);
5084 /* If the TBAA state isn't compatible for downstream reads
5085 we cannot value-number the VDEFs the same. */
5087 ao_ref_init (&lhs_ref
, lhs
);
5088 alias_set_type set
= ao_ref_alias_set (&lhs_ref
);
5089 alias_set_type base_set
= ao_ref_base_alias_set (&lhs_ref
);
5090 if ((vnresult
->set
!= set
5091 && ! alias_set_subset_of (set
, vnresult
->set
))
5092 || (vnresult
->base_set
!= base_set
5093 && ! alias_set_subset_of (base_set
, vnresult
->base_set
)))
5100 /* Only perform the following when being called from PRE
5101 which embeds tail merging. */
5102 if (default_vn_walk_kind
== VN_WALK
)
5104 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
5105 vn_reference_lookup (assign
, vuse
, VN_NOWALK
, &vnresult
, false);
5108 VN_INFO (vdef
)->visited
= true;
5109 return set_ssa_val_to (vdef
, vnresult
->result_vdef
);
5113 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5115 fprintf (dump_file
, "No store match\n");
5116 fprintf (dump_file
, "Value numbering store ");
5117 print_generic_expr (dump_file
, lhs
);
5118 fprintf (dump_file
, " to ");
5119 print_generic_expr (dump_file
, op
);
5120 fprintf (dump_file
, "\n");
5122 /* Have to set value numbers before insert, since insert is
5123 going to valueize the references in-place. */
5125 changed
|= set_ssa_val_to (vdef
, vdef
);
5127 /* Do not insert structure copies into the tables. */
5128 if (is_gimple_min_invariant (op
)
5129 || is_gimple_reg (op
))
5130 vn_reference_insert (lhs
, op
, vdef
, NULL
);
5132 /* Only perform the following when being called from PRE
5133 which embeds tail merging. */
5134 if (default_vn_walk_kind
== VN_WALK
)
5136 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
5137 vn_reference_insert (assign
, lhs
, vuse
, vdef
);
5142 /* We had a match, so value number the vdef to have the value
5143 number of the vuse it came from. */
5145 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5146 fprintf (dump_file
, "Store matched earlier value, "
5147 "value numbering store vdefs to matching vuses.\n");
5149 changed
|= set_ssa_val_to (vdef
, SSA_VAL (vuse
));
5155 /* Visit and value number PHI, return true if the value number
5156 changed. When BACKEDGES_VARYING_P is true then assume all
5157 backedge values are varying. When INSERTED is not NULL then
5158 this is just a ahead query for a possible iteration, set INSERTED
5159 to true if we'd insert into the hashtable. */
5162 visit_phi (gimple
*phi
, bool *inserted
, bool backedges_varying_p
)
5164 tree result
, sameval
= VN_TOP
, seen_undef
= NULL_TREE
;
5165 tree backedge_val
= NULL_TREE
;
5166 bool seen_non_backedge
= false;
5167 tree sameval_base
= NULL_TREE
;
5168 poly_int64 soff
, doff
;
5169 unsigned n_executable
= 0;
5173 /* TODO: We could check for this in initialization, and replace this
5174 with a gcc_assert. */
5175 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
5176 return set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
5178 /* We track whether a PHI was CSEd to to avoid excessive iterations
5179 that would be necessary only because the PHI changed arguments
5182 gimple_set_plf (phi
, GF_PLF_1
, false);
5184 /* See if all non-TOP arguments have the same value. TOP is
5185 equivalent to everything, so we can ignore it. */
5186 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
5187 if (e
->flags
& EDGE_EXECUTABLE
)
5189 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
5192 if (TREE_CODE (def
) == SSA_NAME
)
5194 if (!backedges_varying_p
|| !(e
->flags
& EDGE_DFS_BACK
))
5195 def
= SSA_VAL (def
);
5196 if (e
->flags
& EDGE_DFS_BACK
)
5199 if (!(e
->flags
& EDGE_DFS_BACK
))
5200 seen_non_backedge
= true;
5203 /* Ignore undefined defs for sameval but record one. */
5204 else if (TREE_CODE (def
) == SSA_NAME
5205 && ! virtual_operand_p (def
)
5206 && ssa_undefined_value_p (def
, false))
5208 else if (sameval
== VN_TOP
)
5210 else if (!expressions_equal_p (def
, sameval
))
5212 /* We know we're arriving only with invariant addresses here,
5213 try harder comparing them. We can do some caching here
5214 which we cannot do in expressions_equal_p. */
5215 if (TREE_CODE (def
) == ADDR_EXPR
5216 && TREE_CODE (sameval
) == ADDR_EXPR
5217 && sameval_base
!= (void *)-1)
5220 sameval_base
= get_addr_base_and_unit_offset
5221 (TREE_OPERAND (sameval
, 0), &soff
);
5223 sameval_base
= (tree
)(void *)-1;
5224 else if ((get_addr_base_and_unit_offset
5225 (TREE_OPERAND (def
, 0), &doff
) == sameval_base
)
5226 && known_eq (soff
, doff
))
5229 sameval
= NULL_TREE
;
5234 /* If the value we want to use is flowing over the backedge and we
5235 should take it as VARYING but it has a non-VARYING value drop to
5237 If we value-number a virtual operand never value-number to the
5238 value from the backedge as that confuses the alias-walking code.
5239 See gcc.dg/torture/pr87176.c. If the value is the same on a
5240 non-backedge everything is OK though. */
5243 && !seen_non_backedge
5244 && TREE_CODE (backedge_val
) == SSA_NAME
5245 && sameval
== backedge_val
5246 && (SSA_NAME_IS_VIRTUAL_OPERAND (backedge_val
)
5247 || SSA_VAL (backedge_val
) != backedge_val
))
5248 /* Do not value-number a virtual operand to sth not visited though
5249 given that allows us to escape a region in alias walking. */
5251 && TREE_CODE (sameval
) == SSA_NAME
5252 && !SSA_NAME_IS_DEFAULT_DEF (sameval
)
5253 && SSA_NAME_IS_VIRTUAL_OPERAND (sameval
)
5254 && (SSA_VAL (sameval
, &visited_p
), !visited_p
)))
5255 /* Note this just drops to VARYING without inserting the PHI into
5257 result
= PHI_RESULT (phi
);
5258 /* If none of the edges was executable keep the value-number at VN_TOP,
5259 if only a single edge is exectuable use its value. */
5260 else if (n_executable
<= 1)
5261 result
= seen_undef
? seen_undef
: sameval
;
5262 /* If we saw only undefined values and VN_TOP use one of the
5263 undefined values. */
5264 else if (sameval
== VN_TOP
)
5265 result
= seen_undef
? seen_undef
: sameval
;
5266 /* First see if it is equivalent to a phi node in this block. We prefer
5267 this as it allows IV elimination - see PRs 66502 and 67167. */
5268 else if ((result
= vn_phi_lookup (phi
, backedges_varying_p
)))
5271 && TREE_CODE (result
) == SSA_NAME
5272 && gimple_code (SSA_NAME_DEF_STMT (result
)) == GIMPLE_PHI
)
5274 gimple_set_plf (SSA_NAME_DEF_STMT (result
), GF_PLF_1
, true);
5275 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5277 fprintf (dump_file
, "Marking CSEd to PHI node ");
5278 print_gimple_expr (dump_file
, SSA_NAME_DEF_STMT (result
),
5280 fprintf (dump_file
, "\n");
5284 /* If all values are the same use that, unless we've seen undefined
5285 values as well and the value isn't constant.
5286 CCP/copyprop have the same restriction to not remove uninit warnings. */
5288 && (! seen_undef
|| is_gimple_min_invariant (sameval
)))
5292 result
= PHI_RESULT (phi
);
5293 /* Only insert PHIs that are varying, for constant value numbers
5294 we mess up equivalences otherwise as we are only comparing
5295 the immediate controlling predicates. */
5296 vn_phi_insert (phi
, result
, backedges_varying_p
);
5301 return set_ssa_val_to (PHI_RESULT (phi
), result
);
5304 /* Try to simplify RHS using equivalences and constant folding. */
5307 try_to_simplify (gassign
*stmt
)
5309 enum tree_code code
= gimple_assign_rhs_code (stmt
);
5312 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
5313 in this case, there is no point in doing extra work. */
5314 if (code
== SSA_NAME
)
5317 /* First try constant folding based on our current lattice. */
5318 mprts_hook
= vn_lookup_simplify_result
;
5319 tem
= gimple_fold_stmt_to_constant_1 (stmt
, vn_valueize
, vn_valueize
);
5322 && (TREE_CODE (tem
) == SSA_NAME
5323 || is_gimple_min_invariant (tem
)))
5329 /* Visit and value number STMT, return true if the value number
5333 visit_stmt (gimple
*stmt
, bool backedges_varying_p
= false)
5335 bool changed
= false;
5337 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5339 fprintf (dump_file
, "Value numbering stmt = ");
5340 print_gimple_stmt (dump_file
, stmt
, 0);
5343 if (gimple_code (stmt
) == GIMPLE_PHI
)
5344 changed
= visit_phi (stmt
, NULL
, backedges_varying_p
);
5345 else if (gimple_has_volatile_ops (stmt
))
5346 changed
= defs_to_varying (stmt
);
5347 else if (gassign
*ass
= dyn_cast
<gassign
*> (stmt
))
5349 enum tree_code code
= gimple_assign_rhs_code (ass
);
5350 tree lhs
= gimple_assign_lhs (ass
);
5351 tree rhs1
= gimple_assign_rhs1 (ass
);
5354 /* Shortcut for copies. Simplifying copies is pointless,
5355 since we copy the expression and value they represent. */
5356 if (code
== SSA_NAME
5357 && TREE_CODE (lhs
) == SSA_NAME
)
5359 changed
= visit_copy (lhs
, rhs1
);
5362 simplified
= try_to_simplify (ass
);
5365 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5367 fprintf (dump_file
, "RHS ");
5368 print_gimple_expr (dump_file
, ass
, 0);
5369 fprintf (dump_file
, " simplified to ");
5370 print_generic_expr (dump_file
, simplified
);
5371 fprintf (dump_file
, "\n");
5374 /* Setting value numbers to constants will occasionally
5375 screw up phi congruence because constants are not
5376 uniquely associated with a single ssa name that can be
5379 && is_gimple_min_invariant (simplified
)
5380 && TREE_CODE (lhs
) == SSA_NAME
)
5382 changed
= set_ssa_val_to (lhs
, simplified
);
5386 && TREE_CODE (simplified
) == SSA_NAME
5387 && TREE_CODE (lhs
) == SSA_NAME
)
5389 changed
= visit_copy (lhs
, simplified
);
5393 if ((TREE_CODE (lhs
) == SSA_NAME
5394 /* We can substitute SSA_NAMEs that are live over
5395 abnormal edges with their constant value. */
5396 && !(gimple_assign_copy_p (ass
)
5397 && is_gimple_min_invariant (rhs1
))
5399 && is_gimple_min_invariant (simplified
))
5400 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
5401 /* Stores or copies from SSA_NAMEs that are live over
5402 abnormal edges are a problem. */
5403 || (code
== SSA_NAME
5404 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
)))
5405 changed
= defs_to_varying (ass
);
5406 else if (REFERENCE_CLASS_P (lhs
)
5408 changed
= visit_reference_op_store (lhs
, rhs1
, ass
);
5409 else if (TREE_CODE (lhs
) == SSA_NAME
)
5411 if ((gimple_assign_copy_p (ass
)
5412 && is_gimple_min_invariant (rhs1
))
5414 && is_gimple_min_invariant (simplified
)))
5417 changed
= set_ssa_val_to (lhs
, simplified
);
5419 changed
= set_ssa_val_to (lhs
, rhs1
);
5423 /* Visit the original statement. */
5424 switch (vn_get_stmt_kind (ass
))
5427 changed
= visit_nary_op (lhs
, ass
);
5430 changed
= visit_reference_op_load (lhs
, rhs1
, ass
);
5433 changed
= defs_to_varying (ass
);
5439 changed
= defs_to_varying (ass
);
5441 else if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
5443 tree lhs
= gimple_call_lhs (call_stmt
);
5444 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
5446 /* Try constant folding based on our current lattice. */
5447 tree simplified
= gimple_fold_stmt_to_constant_1 (call_stmt
,
5451 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5453 fprintf (dump_file
, "call ");
5454 print_gimple_expr (dump_file
, call_stmt
, 0);
5455 fprintf (dump_file
, " simplified to ");
5456 print_generic_expr (dump_file
, simplified
);
5457 fprintf (dump_file
, "\n");
5460 /* Setting value numbers to constants will occasionally
5461 screw up phi congruence because constants are not
5462 uniquely associated with a single ssa name that can be
5465 && is_gimple_min_invariant (simplified
))
5467 changed
= set_ssa_val_to (lhs
, simplified
);
5468 if (gimple_vdef (call_stmt
))
5469 changed
|= set_ssa_val_to (gimple_vdef (call_stmt
),
5470 SSA_VAL (gimple_vuse (call_stmt
)));
5474 && TREE_CODE (simplified
) == SSA_NAME
)
5476 changed
= visit_copy (lhs
, simplified
);
5477 if (gimple_vdef (call_stmt
))
5478 changed
|= set_ssa_val_to (gimple_vdef (call_stmt
),
5479 SSA_VAL (gimple_vuse (call_stmt
)));
5482 else if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
5484 changed
= defs_to_varying (call_stmt
);
5489 /* Pick up flags from a devirtualization target. */
5490 tree fn
= gimple_call_fn (stmt
);
5491 int extra_fnflags
= 0;
5492 if (fn
&& TREE_CODE (fn
) == SSA_NAME
)
5495 if (TREE_CODE (fn
) == ADDR_EXPR
5496 && TREE_CODE (TREE_OPERAND (fn
, 0)) == FUNCTION_DECL
)
5497 extra_fnflags
= flags_from_decl_or_type (TREE_OPERAND (fn
, 0));
5499 if (!gimple_call_internal_p (call_stmt
)
5500 && (/* Calls to the same function with the same vuse
5501 and the same operands do not necessarily return the same
5502 value, unless they're pure or const. */
5503 ((gimple_call_flags (call_stmt
) | extra_fnflags
)
5504 & (ECF_PURE
| ECF_CONST
))
5505 /* If calls have a vdef, subsequent calls won't have
5506 the same incoming vuse. So, if 2 calls with vdef have the
5507 same vuse, we know they're not subsequent.
5508 We can value number 2 calls to the same function with the
5509 same vuse and the same operands which are not subsequent
5510 the same, because there is no code in the program that can
5511 compare the 2 values... */
5512 || (gimple_vdef (call_stmt
)
5513 /* ... unless the call returns a pointer which does
5514 not alias with anything else. In which case the
5515 information that the values are distinct are encoded
5517 && !(gimple_call_return_flags (call_stmt
) & ERF_NOALIAS
)
5518 /* Only perform the following when being called from PRE
5519 which embeds tail merging. */
5520 && default_vn_walk_kind
== VN_WALK
)))
5521 changed
= visit_reference_op_call (lhs
, call_stmt
);
5523 changed
= defs_to_varying (call_stmt
);
5526 changed
= defs_to_varying (stmt
);
5532 /* Allocate a value number table. */
5535 allocate_vn_table (vn_tables_t table
, unsigned size
)
5537 table
->phis
= new vn_phi_table_type (size
);
5538 table
->nary
= new vn_nary_op_table_type (size
);
5539 table
->references
= new vn_reference_table_type (size
);
5542 /* Free a value number table. */
5545 free_vn_table (vn_tables_t table
)
5547 /* Walk over elements and release vectors. */
5548 vn_reference_iterator_type hir
;
5550 FOR_EACH_HASH_TABLE_ELEMENT (*table
->references
, vr
, vn_reference_t
, hir
)
5551 vr
->operands
.release ();
5556 delete table
->references
;
5557 table
->references
= NULL
;
5560 /* Set *ID according to RESULT. */
5563 set_value_id_for_result (tree result
, unsigned int *id
)
5565 if (result
&& TREE_CODE (result
) == SSA_NAME
)
5566 *id
= VN_INFO (result
)->value_id
;
5567 else if (result
&& is_gimple_min_invariant (result
))
5568 *id
= get_or_alloc_constant_value_id (result
);
5570 *id
= get_next_value_id ();
5573 /* Set the value ids in the valid hash tables. */
5576 set_hashtable_value_ids (void)
5578 vn_nary_op_iterator_type hin
;
5579 vn_phi_iterator_type hip
;
5580 vn_reference_iterator_type hir
;
5585 /* Now set the value ids of the things we had put in the hash
5588 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->nary
, vno
, vn_nary_op_t
, hin
)
5589 if (! vno
->predicated_values
)
5590 set_value_id_for_result (vno
->u
.result
, &vno
->value_id
);
5592 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->phis
, vp
, vn_phi_t
, hip
)
5593 set_value_id_for_result (vp
->result
, &vp
->value_id
);
5595 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->references
, vr
, vn_reference_t
,
5597 set_value_id_for_result (vr
->result
, &vr
->value_id
);
5600 /* Return the maximum value id we have ever seen. */
5603 get_max_value_id (void)
5605 return next_value_id
;
5608 /* Return the maximum constant value id we have ever seen. */
5611 get_max_constant_value_id (void)
5613 return -next_constant_value_id
;
5616 /* Return the next unique value id. */
5619 get_next_value_id (void)
5621 gcc_checking_assert ((int)next_value_id
> 0);
5622 return next_value_id
++;
5625 /* Return the next unique value id for constants. */
5628 get_next_constant_value_id (void)
5630 gcc_checking_assert (next_constant_value_id
< 0);
5631 return next_constant_value_id
--;
5635 /* Compare two expressions E1 and E2 and return true if they are equal. */
5638 expressions_equal_p (tree e1
, tree e2
)
5640 /* The obvious case. */
5644 /* If either one is VN_TOP consider them equal. */
5645 if (e1
== VN_TOP
|| e2
== VN_TOP
)
5648 /* SSA_NAME compare pointer equal. */
5649 if (TREE_CODE (e1
) == SSA_NAME
|| TREE_CODE (e2
) == SSA_NAME
)
5652 /* Now perform the actual comparison. */
5653 if (TREE_CODE (e1
) == TREE_CODE (e2
)
5654 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
5661 /* Return true if the nary operation NARY may trap. This is a copy
5662 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
5665 vn_nary_may_trap (vn_nary_op_t nary
)
5668 tree rhs2
= NULL_TREE
;
5669 bool honor_nans
= false;
5670 bool honor_snans
= false;
5671 bool fp_operation
= false;
5672 bool honor_trapv
= false;
5676 if (TREE_CODE_CLASS (nary
->opcode
) == tcc_comparison
5677 || TREE_CODE_CLASS (nary
->opcode
) == tcc_unary
5678 || TREE_CODE_CLASS (nary
->opcode
) == tcc_binary
)
5681 fp_operation
= FLOAT_TYPE_P (type
);
5684 honor_nans
= flag_trapping_math
&& !flag_finite_math_only
;
5685 honor_snans
= flag_signaling_nans
!= 0;
5687 else if (INTEGRAL_TYPE_P (type
) && TYPE_OVERFLOW_TRAPS (type
))
5690 if (nary
->length
>= 2)
5692 ret
= operation_could_trap_helper_p (nary
->opcode
, fp_operation
,
5693 honor_trapv
, honor_nans
, honor_snans
,
5698 for (i
= 0; i
< nary
->length
; ++i
)
5699 if (tree_could_trap_p (nary
->op
[i
]))
5705 /* Return true if the reference operation REF may trap. */
5708 vn_reference_may_trap (vn_reference_t ref
)
5710 switch (ref
->operands
[0].opcode
)
5714 /* We do not handle calls. */
5716 /* And toplevel address computations never trap. */
5721 vn_reference_op_t op
;
5723 FOR_EACH_VEC_ELT (ref
->operands
, i
, op
)
5727 case WITH_SIZE_EXPR
:
5728 case TARGET_MEM_REF
:
5729 /* Always variable. */
5732 if (op
->op1
&& TREE_CODE (op
->op1
) == SSA_NAME
)
5735 case ARRAY_RANGE_REF
:
5737 if (TREE_CODE (op
->op0
) == SSA_NAME
)
5741 /* Nothing interesting in itself, the base is separate. */
5743 /* The following are the address bases. */
5748 return tree_could_trap_p (TREE_OPERAND (op
->op0
, 0));
5756 eliminate_dom_walker::eliminate_dom_walker (cdi_direction direction
,
5757 bitmap inserted_exprs_
)
5758 : dom_walker (direction
), do_pre (inserted_exprs_
!= NULL
),
5759 el_todo (0), eliminations (0), insertions (0),
5760 inserted_exprs (inserted_exprs_
)
5762 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
5763 need_ab_cleanup
= BITMAP_ALLOC (NULL
);
5766 eliminate_dom_walker::~eliminate_dom_walker ()
5768 BITMAP_FREE (need_eh_cleanup
);
5769 BITMAP_FREE (need_ab_cleanup
);
5772 /* Return a leader for OP that is available at the current point of the
5773 eliminate domwalk. */
5776 eliminate_dom_walker::eliminate_avail (basic_block
, tree op
)
5778 tree valnum
= VN_INFO (op
)->valnum
;
5779 if (TREE_CODE (valnum
) == SSA_NAME
)
5781 if (SSA_NAME_IS_DEFAULT_DEF (valnum
))
5783 if (avail
.length () > SSA_NAME_VERSION (valnum
))
5784 return avail
[SSA_NAME_VERSION (valnum
)];
5786 else if (is_gimple_min_invariant (valnum
))
5791 /* At the current point of the eliminate domwalk make OP available. */
5794 eliminate_dom_walker::eliminate_push_avail (basic_block
, tree op
)
5796 tree valnum
= VN_INFO (op
)->valnum
;
5797 if (TREE_CODE (valnum
) == SSA_NAME
)
5799 if (avail
.length () <= SSA_NAME_VERSION (valnum
))
5800 avail
.safe_grow_cleared (SSA_NAME_VERSION (valnum
) + 1, true);
5802 if (avail
[SSA_NAME_VERSION (valnum
)])
5803 pushop
= avail
[SSA_NAME_VERSION (valnum
)];
5804 avail_stack
.safe_push (pushop
);
5805 avail
[SSA_NAME_VERSION (valnum
)] = op
;
5809 /* Insert the expression recorded by SCCVN for VAL at *GSI. Returns
5810 the leader for the expression if insertion was successful. */
5813 eliminate_dom_walker::eliminate_insert (basic_block bb
,
5814 gimple_stmt_iterator
*gsi
, tree val
)
5816 /* We can insert a sequence with a single assignment only. */
5817 gimple_seq stmts
= VN_INFO (val
)->expr
;
5818 if (!gimple_seq_singleton_p (stmts
))
5820 gassign
*stmt
= dyn_cast
<gassign
*> (gimple_seq_first_stmt (stmts
));
5822 || (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt
))
5823 && gimple_assign_rhs_code (stmt
) != VIEW_CONVERT_EXPR
5824 && gimple_assign_rhs_code (stmt
) != NEGATE_EXPR
5825 && gimple_assign_rhs_code (stmt
) != BIT_FIELD_REF
5826 && (gimple_assign_rhs_code (stmt
) != BIT_AND_EXPR
5827 || TREE_CODE (gimple_assign_rhs2 (stmt
)) != INTEGER_CST
)))
5830 tree op
= gimple_assign_rhs1 (stmt
);
5831 if (gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
5832 || gimple_assign_rhs_code (stmt
) == BIT_FIELD_REF
)
5833 op
= TREE_OPERAND (op
, 0);
5834 tree leader
= TREE_CODE (op
) == SSA_NAME
? eliminate_avail (bb
, op
) : op
;
5840 if (gimple_assign_rhs_code (stmt
) == BIT_FIELD_REF
)
5841 res
= gimple_build (&stmts
, BIT_FIELD_REF
,
5842 TREE_TYPE (val
), leader
,
5843 TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1),
5844 TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2));
5845 else if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
)
5846 res
= gimple_build (&stmts
, BIT_AND_EXPR
,
5847 TREE_TYPE (val
), leader
, gimple_assign_rhs2 (stmt
));
5849 res
= gimple_build (&stmts
, gimple_assign_rhs_code (stmt
),
5850 TREE_TYPE (val
), leader
);
5851 if (TREE_CODE (res
) != SSA_NAME
5852 || SSA_NAME_IS_DEFAULT_DEF (res
)
5853 || gimple_bb (SSA_NAME_DEF_STMT (res
)))
5855 gimple_seq_discard (stmts
);
5857 /* During propagation we have to treat SSA info conservatively
5858 and thus we can end up simplifying the inserted expression
5859 at elimination time to sth not defined in stmts. */
5860 /* But then this is a redundancy we failed to detect. Which means
5861 res now has two values. That doesn't play well with how
5862 we track availability here, so give up. */
5863 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5865 if (TREE_CODE (res
) == SSA_NAME
)
5866 res
= eliminate_avail (bb
, res
);
5869 fprintf (dump_file
, "Failed to insert expression for value ");
5870 print_generic_expr (dump_file
, val
);
5871 fprintf (dump_file
, " which is really fully redundant to ");
5872 print_generic_expr (dump_file
, res
);
5873 fprintf (dump_file
, "\n");
5881 gsi_insert_seq_before (gsi
, stmts
, GSI_SAME_STMT
);
5882 vn_ssa_aux_t vn_info
= VN_INFO (res
);
5883 vn_info
->valnum
= val
;
5884 vn_info
->visited
= true;
5888 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5890 fprintf (dump_file
, "Inserted ");
5891 print_gimple_stmt (dump_file
, SSA_NAME_DEF_STMT (res
), 0);
5898 eliminate_dom_walker::eliminate_stmt (basic_block b
, gimple_stmt_iterator
*gsi
)
5900 tree sprime
= NULL_TREE
;
5901 gimple
*stmt
= gsi_stmt (*gsi
);
5902 tree lhs
= gimple_get_lhs (stmt
);
5903 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
5904 && !gimple_has_volatile_ops (stmt
)
5905 /* See PR43491. Do not replace a global register variable when
5906 it is a the RHS of an assignment. Do replace local register
5907 variables since gcc does not guarantee a local variable will
5908 be allocated in register.
5909 ??? The fix isn't effective here. This should instead
5910 be ensured by not value-numbering them the same but treating
5911 them like volatiles? */
5912 && !(gimple_assign_single_p (stmt
)
5913 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == VAR_DECL
5914 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt
))
5915 && is_global_var (gimple_assign_rhs1 (stmt
)))))
5917 sprime
= eliminate_avail (b
, lhs
);
5920 /* If there is no existing usable leader but SCCVN thinks
5921 it has an expression it wants to use as replacement,
5923 tree val
= VN_INFO (lhs
)->valnum
;
5924 vn_ssa_aux_t vn_info
;
5926 && TREE_CODE (val
) == SSA_NAME
5927 && (vn_info
= VN_INFO (val
), true)
5928 && vn_info
->needs_insertion
5929 && vn_info
->expr
!= NULL
5930 && (sprime
= eliminate_insert (b
, gsi
, val
)) != NULL_TREE
)
5931 eliminate_push_avail (b
, sprime
);
5934 /* If this now constitutes a copy duplicate points-to
5935 and range info appropriately. This is especially
5936 important for inserted code. See tree-ssa-copy.c
5937 for similar code. */
5939 && TREE_CODE (sprime
) == SSA_NAME
)
5941 basic_block sprime_b
= gimple_bb (SSA_NAME_DEF_STMT (sprime
));
5942 if (POINTER_TYPE_P (TREE_TYPE (lhs
))
5943 && SSA_NAME_PTR_INFO (lhs
)
5944 && ! SSA_NAME_PTR_INFO (sprime
))
5946 duplicate_ssa_name_ptr_info (sprime
,
5947 SSA_NAME_PTR_INFO (lhs
));
5949 reset_flow_sensitive_info (sprime
);
5951 else if (INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
5952 && SSA_NAME_RANGE_INFO (lhs
)
5953 && ! SSA_NAME_RANGE_INFO (sprime
)
5955 duplicate_ssa_name_range_info (sprime
,
5956 SSA_NAME_RANGE_TYPE (lhs
),
5957 SSA_NAME_RANGE_INFO (lhs
));
5960 /* Inhibit the use of an inserted PHI on a loop header when
5961 the address of the memory reference is a simple induction
5962 variable. In other cases the vectorizer won't do anything
5963 anyway (either it's loop invariant or a complicated
5966 && TREE_CODE (sprime
) == SSA_NAME
5968 && (flag_tree_loop_vectorize
|| flag_tree_parallelize_loops
> 1)
5969 && loop_outer (b
->loop_father
)
5970 && has_zero_uses (sprime
)
5971 && bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (sprime
))
5972 && gimple_assign_load_p (stmt
))
5974 gimple
*def_stmt
= SSA_NAME_DEF_STMT (sprime
);
5975 basic_block def_bb
= gimple_bb (def_stmt
);
5976 if (gimple_code (def_stmt
) == GIMPLE_PHI
5977 && def_bb
->loop_father
->header
== def_bb
)
5979 loop_p loop
= def_bb
->loop_father
;
5983 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
5986 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (op
));
5988 && flow_bb_inside_loop_p (loop
, def_bb
)
5989 && simple_iv (loop
, loop
, op
, &iv
, true))
5997 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5999 fprintf (dump_file
, "Not replacing ");
6000 print_gimple_expr (dump_file
, stmt
, 0);
6001 fprintf (dump_file
, " with ");
6002 print_generic_expr (dump_file
, sprime
);
6003 fprintf (dump_file
, " which would add a loop"
6004 " carried dependence to loop %d\n",
6007 /* Don't keep sprime available. */
6015 /* If we can propagate the value computed for LHS into
6016 all uses don't bother doing anything with this stmt. */
6017 if (may_propagate_copy (lhs
, sprime
))
6019 /* Mark it for removal. */
6020 to_remove
.safe_push (stmt
);
6022 /* ??? Don't count copy/constant propagations. */
6023 if (gimple_assign_single_p (stmt
)
6024 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
6025 || gimple_assign_rhs1 (stmt
) == sprime
))
6028 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6030 fprintf (dump_file
, "Replaced ");
6031 print_gimple_expr (dump_file
, stmt
, 0);
6032 fprintf (dump_file
, " with ");
6033 print_generic_expr (dump_file
, sprime
);
6034 fprintf (dump_file
, " in all uses of ");
6035 print_gimple_stmt (dump_file
, stmt
, 0);
6042 /* If this is an assignment from our leader (which
6043 happens in the case the value-number is a constant)
6044 then there is nothing to do. Likewise if we run into
6045 inserted code that needed a conversion because of
6046 our type-agnostic value-numbering of loads. */
6047 if ((gimple_assign_single_p (stmt
)
6048 || (is_gimple_assign (stmt
)
6049 && (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt
))
6050 || gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
)))
6051 && sprime
== gimple_assign_rhs1 (stmt
))
6054 /* Else replace its RHS. */
6055 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6057 fprintf (dump_file
, "Replaced ");
6058 print_gimple_expr (dump_file
, stmt
, 0);
6059 fprintf (dump_file
, " with ");
6060 print_generic_expr (dump_file
, sprime
);
6061 fprintf (dump_file
, " in ");
6062 print_gimple_stmt (dump_file
, stmt
, 0);
6066 bool can_make_abnormal_goto
= (is_gimple_call (stmt
)
6067 && stmt_can_make_abnormal_goto (stmt
));
6068 gimple
*orig_stmt
= stmt
;
6069 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
6070 TREE_TYPE (sprime
)))
6072 /* We preserve conversions to but not from function or method
6073 types. This asymmetry makes it necessary to re-instantiate
6074 conversions here. */
6075 if (POINTER_TYPE_P (TREE_TYPE (lhs
))
6076 && FUNC_OR_METHOD_TYPE_P (TREE_TYPE (TREE_TYPE (lhs
))))
6077 sprime
= fold_convert (TREE_TYPE (lhs
), sprime
);
6081 tree vdef
= gimple_vdef (stmt
);
6082 tree vuse
= gimple_vuse (stmt
);
6083 propagate_tree_value_into_stmt (gsi
, sprime
);
6084 stmt
= gsi_stmt (*gsi
);
6086 /* In case the VDEF on the original stmt was released, value-number
6087 it to the VUSE. This is to make vuse_ssa_val able to skip
6088 released virtual operands. */
6089 if (vdef
!= gimple_vdef (stmt
))
6091 gcc_assert (SSA_NAME_IN_FREE_LIST (vdef
));
6092 VN_INFO (vdef
)->valnum
= vuse
;
6095 /* If we removed EH side-effects from the statement, clean
6096 its EH information. */
6097 if (maybe_clean_or_replace_eh_stmt (orig_stmt
, stmt
))
6099 bitmap_set_bit (need_eh_cleanup
,
6100 gimple_bb (stmt
)->index
);
6101 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6102 fprintf (dump_file
, " Removed EH side-effects.\n");
6105 /* Likewise for AB side-effects. */
6106 if (can_make_abnormal_goto
6107 && !stmt_can_make_abnormal_goto (stmt
))
6109 bitmap_set_bit (need_ab_cleanup
,
6110 gimple_bb (stmt
)->index
);
6111 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6112 fprintf (dump_file
, " Removed AB side-effects.\n");
6119 /* If the statement is a scalar store, see if the expression
6120 has the same value number as its rhs. If so, the store is
6122 if (gimple_assign_single_p (stmt
)
6123 && !gimple_has_volatile_ops (stmt
)
6124 && !is_gimple_reg (gimple_assign_lhs (stmt
))
6125 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
6126 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
6128 tree rhs
= gimple_assign_rhs1 (stmt
);
6129 vn_reference_t vnresult
;
6130 /* ??? gcc.dg/torture/pr91445.c shows that we lookup a boolean
6131 typed load of a byte known to be 0x11 as 1 so a store of
6132 a boolean 1 is detected as redundant. Because of this we
6133 have to make sure to lookup with a ref where its size
6134 matches the precision. */
6135 tree lookup_lhs
= lhs
;
6136 if (INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
6137 && (TREE_CODE (lhs
) != COMPONENT_REF
6138 || !DECL_BIT_FIELD_TYPE (TREE_OPERAND (lhs
, 1)))
6139 && !type_has_mode_precision_p (TREE_TYPE (lhs
)))
6141 if (TREE_CODE (lhs
) == COMPONENT_REF
6142 || TREE_CODE (lhs
) == MEM_REF
)
6144 tree ltype
= build_nonstandard_integer_type
6145 (TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (lhs
))),
6146 TYPE_UNSIGNED (TREE_TYPE (lhs
)));
6147 if (TREE_CODE (lhs
) == COMPONENT_REF
)
6149 tree foff
= component_ref_field_offset (lhs
);
6150 tree f
= TREE_OPERAND (lhs
, 1);
6151 if (!poly_int_tree_p (foff
))
6152 lookup_lhs
= NULL_TREE
;
6154 lookup_lhs
= build3 (BIT_FIELD_REF
, ltype
,
6155 TREE_OPERAND (lhs
, 0),
6156 TYPE_SIZE (TREE_TYPE (lhs
)),
6158 (foff
, DECL_FIELD_BIT_OFFSET (f
)));
6161 lookup_lhs
= build2 (MEM_REF
, ltype
,
6162 TREE_OPERAND (lhs
, 0),
6163 TREE_OPERAND (lhs
, 1));
6166 lookup_lhs
= NULL_TREE
;
6168 tree val
= NULL_TREE
;
6170 val
= vn_reference_lookup (lookup_lhs
, gimple_vuse (stmt
),
6171 VN_WALKREWRITE
, &vnresult
, false);
6172 if (TREE_CODE (rhs
) == SSA_NAME
)
6173 rhs
= VN_INFO (rhs
)->valnum
;
6175 && (operand_equal_p (val
, rhs
, 0)
6176 /* Due to the bitfield lookups above we can get bit
6177 interpretations of the same RHS as values here. Those
6178 are redundant as well. */
6179 || (TREE_CODE (val
) == SSA_NAME
6180 && gimple_assign_single_p (SSA_NAME_DEF_STMT (val
))
6181 && (val
= gimple_assign_rhs1 (SSA_NAME_DEF_STMT (val
)))
6182 && TREE_CODE (val
) == VIEW_CONVERT_EXPR
6183 && TREE_OPERAND (val
, 0) == rhs
)))
6185 /* We can only remove the later store if the former aliases
6186 at least all accesses the later one does or if the store
6187 was to readonly memory storing the same value. */
6189 ao_ref_init (&lhs_ref
, lhs
);
6190 alias_set_type set
= ao_ref_alias_set (&lhs_ref
);
6191 alias_set_type base_set
= ao_ref_base_alias_set (&lhs_ref
);
6193 || ((vnresult
->set
== set
6194 || alias_set_subset_of (set
, vnresult
->set
))
6195 && (vnresult
->base_set
== base_set
6196 || alias_set_subset_of (base_set
, vnresult
->base_set
))))
6198 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6200 fprintf (dump_file
, "Deleted redundant store ");
6201 print_gimple_stmt (dump_file
, stmt
, 0);
6204 /* Queue stmt for removal. */
6205 to_remove
.safe_push (stmt
);
6211 /* If this is a control statement value numbering left edges
6212 unexecuted on force the condition in a way consistent with
6214 if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
6216 if ((EDGE_SUCC (b
, 0)->flags
& EDGE_EXECUTABLE
)
6217 ^ (EDGE_SUCC (b
, 1)->flags
& EDGE_EXECUTABLE
))
6219 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6221 fprintf (dump_file
, "Removing unexecutable edge from ");
6222 print_gimple_stmt (dump_file
, stmt
, 0);
6224 if (((EDGE_SUCC (b
, 0)->flags
& EDGE_TRUE_VALUE
) != 0)
6225 == ((EDGE_SUCC (b
, 0)->flags
& EDGE_EXECUTABLE
) != 0))
6226 gimple_cond_make_true (cond
);
6228 gimple_cond_make_false (cond
);
6230 el_todo
|= TODO_cleanup_cfg
;
6235 bool can_make_abnormal_goto
= stmt_can_make_abnormal_goto (stmt
);
6236 bool was_noreturn
= (is_gimple_call (stmt
)
6237 && gimple_call_noreturn_p (stmt
));
6238 tree vdef
= gimple_vdef (stmt
);
6239 tree vuse
= gimple_vuse (stmt
);
6241 /* If we didn't replace the whole stmt (or propagate the result
6242 into all uses), replace all uses on this stmt with their
6244 bool modified
= false;
6245 use_operand_p use_p
;
6247 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
6249 tree use
= USE_FROM_PTR (use_p
);
6250 /* ??? The call code above leaves stmt operands un-updated. */
6251 if (TREE_CODE (use
) != SSA_NAME
)
6254 if (SSA_NAME_IS_DEFAULT_DEF (use
))
6255 /* ??? For default defs BB shouldn't matter, but we have to
6256 solve the inconsistency between rpo eliminate and
6257 dom eliminate avail valueization first. */
6258 sprime
= eliminate_avail (b
, use
);
6260 /* Look for sth available at the definition block of the argument.
6261 This avoids inconsistencies between availability there which
6262 decides if the stmt can be removed and availability at the
6263 use site. The SSA property ensures that things available
6264 at the definition are also available at uses. */
6265 sprime
= eliminate_avail (gimple_bb (SSA_NAME_DEF_STMT (use
)), use
);
6266 if (sprime
&& sprime
!= use
6267 && may_propagate_copy (use
, sprime
)
6268 /* We substitute into debug stmts to avoid excessive
6269 debug temporaries created by removed stmts, but we need
6270 to avoid doing so for inserted sprimes as we never want
6271 to create debug temporaries for them. */
6273 || TREE_CODE (sprime
) != SSA_NAME
6274 || !is_gimple_debug (stmt
)
6275 || !bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (sprime
))))
6277 propagate_value (use_p
, sprime
);
6282 /* Fold the stmt if modified, this canonicalizes MEM_REFs we propagated
6283 into which is a requirement for the IPA devirt machinery. */
6284 gimple
*old_stmt
= stmt
;
6287 /* If a formerly non-invariant ADDR_EXPR is turned into an
6288 invariant one it was on a separate stmt. */
6289 if (gimple_assign_single_p (stmt
)
6290 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ADDR_EXPR
)
6291 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt
));
6292 gimple_stmt_iterator prev
= *gsi
;
6294 if (fold_stmt (gsi
))
6296 /* fold_stmt may have created new stmts inbetween
6297 the previous stmt and the folded stmt. Mark
6298 all defs created there as varying to not confuse
6299 the SCCVN machinery as we're using that even during
6301 if (gsi_end_p (prev
))
6302 prev
= gsi_start_bb (b
);
6305 if (gsi_stmt (prev
) != gsi_stmt (*gsi
))
6310 FOR_EACH_SSA_TREE_OPERAND (def
, gsi_stmt (prev
),
6311 dit
, SSA_OP_ALL_DEFS
)
6312 /* As existing DEFs may move between stmts
6313 only process new ones. */
6314 if (! has_VN_INFO (def
))
6316 vn_ssa_aux_t vn_info
= VN_INFO (def
);
6317 vn_info
->valnum
= def
;
6318 vn_info
->visited
= true;
6320 if (gsi_stmt (prev
) == gsi_stmt (*gsi
))
6326 stmt
= gsi_stmt (*gsi
);
6327 /* In case we folded the stmt away schedule the NOP for removal. */
6328 if (gimple_nop_p (stmt
))
6329 to_remove
.safe_push (stmt
);
6332 /* Visit indirect calls and turn them into direct calls if
6333 possible using the devirtualization machinery. Do this before
6334 checking for required EH/abnormal/noreturn cleanup as devird
6335 may expose more of those. */
6336 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
6338 tree fn
= gimple_call_fn (call_stmt
);
6340 && flag_devirtualize
6341 && virtual_method_call_p (fn
))
6343 tree otr_type
= obj_type_ref_class (fn
);
6344 unsigned HOST_WIDE_INT otr_tok
6345 = tree_to_uhwi (OBJ_TYPE_REF_TOKEN (fn
));
6347 ipa_polymorphic_call_context
context (current_function_decl
,
6348 fn
, stmt
, &instance
);
6349 context
.get_dynamic_type (instance
, OBJ_TYPE_REF_OBJECT (fn
),
6350 otr_type
, stmt
, NULL
);
6352 vec
<cgraph_node
*> targets
6353 = possible_polymorphic_call_targets (obj_type_ref_class (fn
),
6354 otr_tok
, context
, &final
);
6356 dump_possible_polymorphic_call_targets (dump_file
,
6357 obj_type_ref_class (fn
),
6359 if (final
&& targets
.length () <= 1 && dbg_cnt (devirt
))
6362 if (targets
.length () == 1)
6363 fn
= targets
[0]->decl
;
6365 fn
= builtin_decl_implicit (BUILT_IN_UNREACHABLE
);
6366 if (dump_enabled_p ())
6368 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
6369 "converting indirect call to "
6371 lang_hooks
.decl_printable_name (fn
, 2));
6373 gimple_call_set_fndecl (call_stmt
, fn
);
6374 /* If changing the call to __builtin_unreachable
6375 or similar noreturn function, adjust gimple_call_fntype
6377 if (gimple_call_noreturn_p (call_stmt
)
6378 && VOID_TYPE_P (TREE_TYPE (TREE_TYPE (fn
)))
6379 && TYPE_ARG_TYPES (TREE_TYPE (fn
))
6380 && (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fn
)))
6382 gimple_call_set_fntype (call_stmt
, TREE_TYPE (fn
));
6383 maybe_remove_unused_call_args (cfun
, call_stmt
);
6391 /* When changing a call into a noreturn call, cfg cleanup
6392 is needed to fix up the noreturn call. */
6394 && is_gimple_call (stmt
) && gimple_call_noreturn_p (stmt
))
6395 to_fixup
.safe_push (stmt
);
6396 /* When changing a condition or switch into one we know what
6397 edge will be executed, schedule a cfg cleanup. */
6398 if ((gimple_code (stmt
) == GIMPLE_COND
6399 && (gimple_cond_true_p (as_a
<gcond
*> (stmt
))
6400 || gimple_cond_false_p (as_a
<gcond
*> (stmt
))))
6401 || (gimple_code (stmt
) == GIMPLE_SWITCH
6402 && TREE_CODE (gimple_switch_index
6403 (as_a
<gswitch
*> (stmt
))) == INTEGER_CST
))
6404 el_todo
|= TODO_cleanup_cfg
;
6405 /* If we removed EH side-effects from the statement, clean
6406 its EH information. */
6407 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
6409 bitmap_set_bit (need_eh_cleanup
,
6410 gimple_bb (stmt
)->index
);
6411 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6412 fprintf (dump_file
, " Removed EH side-effects.\n");
6414 /* Likewise for AB side-effects. */
6415 if (can_make_abnormal_goto
6416 && !stmt_can_make_abnormal_goto (stmt
))
6418 bitmap_set_bit (need_ab_cleanup
,
6419 gimple_bb (stmt
)->index
);
6420 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6421 fprintf (dump_file
, " Removed AB side-effects.\n");
6424 /* In case the VDEF on the original stmt was released, value-number
6425 it to the VUSE. This is to make vuse_ssa_val able to skip
6426 released virtual operands. */
6427 if (vdef
&& SSA_NAME_IN_FREE_LIST (vdef
))
6428 VN_INFO (vdef
)->valnum
= vuse
;
6431 /* Make new values available - for fully redundant LHS we
6432 continue with the next stmt above and skip this. */
6434 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_DEF
)
6435 eliminate_push_avail (b
, DEF_FROM_PTR (defp
));
6438 /* Perform elimination for the basic-block B during the domwalk. */
6441 eliminate_dom_walker::before_dom_children (basic_block b
)
6444 avail_stack
.safe_push (NULL_TREE
);
6446 /* Skip unreachable blocks marked unreachable during the SCCVN domwalk. */
6447 if (!(b
->flags
& BB_EXECUTABLE
))
6452 for (gphi_iterator gsi
= gsi_start_phis (b
); !gsi_end_p (gsi
);)
6454 gphi
*phi
= gsi
.phi ();
6455 tree res
= PHI_RESULT (phi
);
6457 if (virtual_operand_p (res
))
6463 tree sprime
= eliminate_avail (b
, res
);
6467 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6469 fprintf (dump_file
, "Replaced redundant PHI node defining ");
6470 print_generic_expr (dump_file
, res
);
6471 fprintf (dump_file
, " with ");
6472 print_generic_expr (dump_file
, sprime
);
6473 fprintf (dump_file
, "\n");
6476 /* If we inserted this PHI node ourself, it's not an elimination. */
6477 if (! inserted_exprs
6478 || ! bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (res
)))
6481 /* If we will propagate into all uses don't bother to do
6483 if (may_propagate_copy (res
, sprime
))
6485 /* Mark the PHI for removal. */
6486 to_remove
.safe_push (phi
);
6491 remove_phi_node (&gsi
, false);
6493 if (!useless_type_conversion_p (TREE_TYPE (res
), TREE_TYPE (sprime
)))
6494 sprime
= fold_convert (TREE_TYPE (res
), sprime
);
6495 gimple
*stmt
= gimple_build_assign (res
, sprime
);
6496 gimple_stmt_iterator gsi2
= gsi_after_labels (b
);
6497 gsi_insert_before (&gsi2
, stmt
, GSI_NEW_STMT
);
6501 eliminate_push_avail (b
, res
);
6505 for (gimple_stmt_iterator gsi
= gsi_start_bb (b
);
6508 eliminate_stmt (b
, &gsi
);
6510 /* Replace destination PHI arguments. */
6513 FOR_EACH_EDGE (e
, ei
, b
->succs
)
6514 if (e
->flags
& EDGE_EXECUTABLE
)
6515 for (gphi_iterator gsi
= gsi_start_phis (e
->dest
);
6519 gphi
*phi
= gsi
.phi ();
6520 use_operand_p use_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
6521 tree arg
= USE_FROM_PTR (use_p
);
6522 if (TREE_CODE (arg
) != SSA_NAME
6523 || virtual_operand_p (arg
))
6525 tree sprime
= eliminate_avail (b
, arg
);
6526 if (sprime
&& may_propagate_copy (arg
, sprime
))
6527 propagate_value (use_p
, sprime
);
6530 vn_context_bb
= NULL
;
6535 /* Make no longer available leaders no longer available. */
6538 eliminate_dom_walker::after_dom_children (basic_block
)
6541 while ((entry
= avail_stack
.pop ()) != NULL_TREE
)
6543 tree valnum
= VN_INFO (entry
)->valnum
;
6544 tree old
= avail
[SSA_NAME_VERSION (valnum
)];
6546 avail
[SSA_NAME_VERSION (valnum
)] = NULL_TREE
;
6548 avail
[SSA_NAME_VERSION (valnum
)] = entry
;
6552 /* Remove queued stmts and perform delayed cleanups. */
6555 eliminate_dom_walker::eliminate_cleanup (bool region_p
)
6557 statistics_counter_event (cfun
, "Eliminated", eliminations
);
6558 statistics_counter_event (cfun
, "Insertions", insertions
);
6560 /* We cannot remove stmts during BB walk, especially not release SSA
6561 names there as this confuses the VN machinery. The stmts ending
6562 up in to_remove are either stores or simple copies.
6563 Remove stmts in reverse order to make debug stmt creation possible. */
6564 while (!to_remove
.is_empty ())
6566 bool do_release_defs
= true;
6567 gimple
*stmt
= to_remove
.pop ();
6569 /* When we are value-numbering a region we do not require exit PHIs to
6570 be present so we have to make sure to deal with uses outside of the
6571 region of stmts that we thought are eliminated.
6572 ??? Note we may be confused by uses in dead regions we didn't run
6573 elimination on. Rather than checking individual uses we accept
6574 dead copies to be generated here (gcc.c-torture/execute/20060905-1.c
6575 contains such example). */
6578 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
6580 tree lhs
= gimple_phi_result (phi
);
6581 if (!has_zero_uses (lhs
))
6583 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6584 fprintf (dump_file
, "Keeping eliminated stmt live "
6585 "as copy because of out-of-region uses\n");
6586 tree sprime
= eliminate_avail (gimple_bb (stmt
), lhs
);
6587 gimple
*copy
= gimple_build_assign (lhs
, sprime
);
6588 gimple_stmt_iterator gsi
6589 = gsi_after_labels (gimple_bb (stmt
));
6590 gsi_insert_before (&gsi
, copy
, GSI_SAME_STMT
);
6591 do_release_defs
= false;
6594 else if (tree lhs
= gimple_get_lhs (stmt
))
6595 if (TREE_CODE (lhs
) == SSA_NAME
6596 && !has_zero_uses (lhs
))
6598 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6599 fprintf (dump_file
, "Keeping eliminated stmt live "
6600 "as copy because of out-of-region uses\n");
6601 tree sprime
= eliminate_avail (gimple_bb (stmt
), lhs
);
6602 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
6603 if (is_gimple_assign (stmt
))
6605 gimple_assign_set_rhs_from_tree (&gsi
, sprime
);
6606 stmt
= gsi_stmt (gsi
);
6608 if (maybe_clean_or_replace_eh_stmt (stmt
, stmt
))
6609 bitmap_set_bit (need_eh_cleanup
, gimple_bb (stmt
)->index
);
6614 gimple
*copy
= gimple_build_assign (lhs
, sprime
);
6615 gsi_insert_before (&gsi
, copy
, GSI_SAME_STMT
);
6616 do_release_defs
= false;
6621 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6623 fprintf (dump_file
, "Removing dead stmt ");
6624 print_gimple_stmt (dump_file
, stmt
, 0, TDF_NONE
);
6627 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
6628 if (gimple_code (stmt
) == GIMPLE_PHI
)
6629 remove_phi_node (&gsi
, do_release_defs
);
6632 basic_block bb
= gimple_bb (stmt
);
6633 unlink_stmt_vdef (stmt
);
6634 if (gsi_remove (&gsi
, true))
6635 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
6636 if (is_gimple_call (stmt
) && stmt_can_make_abnormal_goto (stmt
))
6637 bitmap_set_bit (need_ab_cleanup
, bb
->index
);
6638 if (do_release_defs
)
6639 release_defs (stmt
);
6642 /* Removing a stmt may expose a forwarder block. */
6643 el_todo
|= TODO_cleanup_cfg
;
6646 /* Fixup stmts that became noreturn calls. This may require splitting
6647 blocks and thus isn't possible during the dominator walk. Do this
6648 in reverse order so we don't inadvertedly remove a stmt we want to
6649 fixup by visiting a dominating now noreturn call first. */
6650 while (!to_fixup
.is_empty ())
6652 gimple
*stmt
= to_fixup
.pop ();
6654 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6656 fprintf (dump_file
, "Fixing up noreturn call ");
6657 print_gimple_stmt (dump_file
, stmt
, 0);
6660 if (fixup_noreturn_call (stmt
))
6661 el_todo
|= TODO_cleanup_cfg
;
6664 bool do_eh_cleanup
= !bitmap_empty_p (need_eh_cleanup
);
6665 bool do_ab_cleanup
= !bitmap_empty_p (need_ab_cleanup
);
6668 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
6671 gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup
);
6673 if (do_eh_cleanup
|| do_ab_cleanup
)
6674 el_todo
|= TODO_cleanup_cfg
;
6679 /* Eliminate fully redundant computations. */
6682 eliminate_with_rpo_vn (bitmap inserted_exprs
)
6684 eliminate_dom_walker
walker (CDI_DOMINATORS
, inserted_exprs
);
6686 eliminate_dom_walker
*saved_rpo_avail
= rpo_avail
;
6687 rpo_avail
= &walker
;
6688 walker
.walk (cfun
->cfg
->x_entry_block_ptr
);
6689 rpo_avail
= saved_rpo_avail
;
6691 return walker
.eliminate_cleanup ();
6695 do_rpo_vn (function
*fn
, edge entry
, bitmap exit_bbs
,
6696 bool iterate
, bool eliminate
);
6699 run_rpo_vn (vn_lookup_kind kind
)
6701 default_vn_walk_kind
= kind
;
6702 do_rpo_vn (cfun
, NULL
, NULL
, true, false);
6704 /* ??? Prune requirement of these. */
6705 constant_to_value_id
= new hash_table
<vn_constant_hasher
> (23);
6707 /* Initialize the value ids and prune out remaining VN_TOPs
6711 FOR_EACH_SSA_NAME (i
, name
, cfun
)
6713 vn_ssa_aux_t info
= VN_INFO (name
);
6715 || info
->valnum
== VN_TOP
)
6716 info
->valnum
= name
;
6717 if (info
->valnum
== name
)
6718 info
->value_id
= get_next_value_id ();
6719 else if (is_gimple_min_invariant (info
->valnum
))
6720 info
->value_id
= get_or_alloc_constant_value_id (info
->valnum
);
6724 FOR_EACH_SSA_NAME (i
, name
, cfun
)
6726 vn_ssa_aux_t info
= VN_INFO (name
);
6727 if (TREE_CODE (info
->valnum
) == SSA_NAME
6728 && info
->valnum
!= name
6729 && info
->value_id
!= VN_INFO (info
->valnum
)->value_id
)
6730 info
->value_id
= VN_INFO (info
->valnum
)->value_id
;
6733 set_hashtable_value_ids ();
6735 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6737 fprintf (dump_file
, "Value numbers:\n");
6738 FOR_EACH_SSA_NAME (i
, name
, cfun
)
6740 if (VN_INFO (name
)->visited
6741 && SSA_VAL (name
) != name
)
6743 print_generic_expr (dump_file
, name
);
6744 fprintf (dump_file
, " = ");
6745 print_generic_expr (dump_file
, SSA_VAL (name
));
6746 fprintf (dump_file
, " (%04d)\n", VN_INFO (name
)->value_id
);
6752 /* Free VN associated data structures. */
6757 free_vn_table (valid_info
);
6758 XDELETE (valid_info
);
6759 obstack_free (&vn_tables_obstack
, NULL
);
6760 obstack_free (&vn_tables_insert_obstack
, NULL
);
6762 vn_ssa_aux_iterator_type it
;
6764 FOR_EACH_HASH_TABLE_ELEMENT (*vn_ssa_aux_hash
, info
, vn_ssa_aux_t
, it
)
6765 if (info
->needs_insertion
)
6766 release_ssa_name (info
->name
);
6767 obstack_free (&vn_ssa_aux_obstack
, NULL
);
6768 delete vn_ssa_aux_hash
;
6770 delete constant_to_value_id
;
6771 constant_to_value_id
= NULL
;
6774 /* Hook for maybe_push_res_to_seq, lookup the expression in the VN tables. */
6777 vn_lookup_simplify_result (gimple_match_op
*res_op
)
6779 if (!res_op
->code
.is_tree_code ())
6781 tree
*ops
= res_op
->ops
;
6782 unsigned int length
= res_op
->num_ops
;
6783 if (res_op
->code
== CONSTRUCTOR
6784 /* ??? We're arriving here with SCCVNs view, decomposed CONSTRUCTOR
6785 and GIMPLEs / match-and-simplifies, CONSTRUCTOR as GENERIC tree. */
6786 && TREE_CODE (res_op
->ops
[0]) == CONSTRUCTOR
)
6788 length
= CONSTRUCTOR_NELTS (res_op
->ops
[0]);
6789 ops
= XALLOCAVEC (tree
, length
);
6790 for (unsigned i
= 0; i
< length
; ++i
)
6791 ops
[i
] = CONSTRUCTOR_ELT (res_op
->ops
[0], i
)->value
;
6793 vn_nary_op_t vnresult
= NULL
;
6794 tree res
= vn_nary_op_lookup_pieces (length
, (tree_code
) res_op
->code
,
6795 res_op
->type
, ops
, &vnresult
);
6796 /* If this is used from expression simplification make sure to
6797 return an available expression. */
6798 if (res
&& TREE_CODE (res
) == SSA_NAME
&& mprts_hook
&& rpo_avail
)
6799 res
= rpo_avail
->eliminate_avail (vn_context_bb
, res
);
6803 /* Return a leader for OPs value that is valid at BB. */
6806 rpo_elim::eliminate_avail (basic_block bb
, tree op
)
6809 tree valnum
= SSA_VAL (op
, &visited
);
6810 /* If we didn't visit OP then it must be defined outside of the
6811 region we process and also dominate it. So it is available. */
6814 if (TREE_CODE (valnum
) == SSA_NAME
)
6816 if (SSA_NAME_IS_DEFAULT_DEF (valnum
))
6818 vn_avail
*av
= VN_INFO (valnum
)->avail
;
6821 if (av
->location
== bb
->index
)
6822 /* On tramp3d 90% of the cases are here. */
6823 return ssa_name (av
->leader
);
6826 basic_block abb
= BASIC_BLOCK_FOR_FN (cfun
, av
->location
);
6827 /* ??? During elimination we have to use availability at the
6828 definition site of a use we try to replace. This
6829 is required to not run into inconsistencies because
6830 of dominated_by_p_w_unex behavior and removing a definition
6831 while not replacing all uses.
6832 ??? We could try to consistently walk dominators
6833 ignoring non-executable regions. The nearest common
6834 dominator of bb and abb is where we can stop walking. We
6835 may also be able to "pre-compute" (bits of) the next immediate
6836 (non-)dominator during the RPO walk when marking edges as
6838 if (dominated_by_p_w_unex (bb
, abb
))
6840 tree leader
= ssa_name (av
->leader
);
6841 /* Prevent eliminations that break loop-closed SSA. */
6842 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
)
6843 && ! SSA_NAME_IS_DEFAULT_DEF (leader
)
6844 && ! flow_bb_inside_loop_p (gimple_bb (SSA_NAME_DEF_STMT
6845 (leader
))->loop_father
,
6848 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6850 print_generic_expr (dump_file
, leader
);
6851 fprintf (dump_file
, " is available for ");
6852 print_generic_expr (dump_file
, valnum
);
6853 fprintf (dump_file
, "\n");
6855 /* On tramp3d 99% of the _remaining_ cases succeed at
6859 /* ??? Can we somehow skip to the immediate dominator
6860 RPO index (bb_to_rpo)? Again, maybe not worth, on
6861 tramp3d the worst number of elements in the vector is 9. */
6866 else if (valnum
!= VN_TOP
)
6867 /* valnum is is_gimple_min_invariant. */
6872 /* Make LEADER a leader for its value at BB. */
6875 rpo_elim::eliminate_push_avail (basic_block bb
, tree leader
)
6877 tree valnum
= VN_INFO (leader
)->valnum
;
6878 if (valnum
== VN_TOP
6879 || is_gimple_min_invariant (valnum
))
6881 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6883 fprintf (dump_file
, "Making available beyond BB%d ", bb
->index
);
6884 print_generic_expr (dump_file
, leader
);
6885 fprintf (dump_file
, " for value ");
6886 print_generic_expr (dump_file
, valnum
);
6887 fprintf (dump_file
, "\n");
6889 vn_ssa_aux_t value
= VN_INFO (valnum
);
6891 if (m_avail_freelist
)
6893 av
= m_avail_freelist
;
6894 m_avail_freelist
= m_avail_freelist
->next
;
6897 av
= XOBNEW (&vn_ssa_aux_obstack
, vn_avail
);
6898 av
->location
= bb
->index
;
6899 av
->leader
= SSA_NAME_VERSION (leader
);
6900 av
->next
= value
->avail
;
6904 /* Valueization hook for RPO VN plus required state. */
6907 rpo_vn_valueize (tree name
)
6909 if (TREE_CODE (name
) == SSA_NAME
)
6911 vn_ssa_aux_t val
= VN_INFO (name
);
6914 tree tem
= val
->valnum
;
6915 if (tem
!= VN_TOP
&& tem
!= name
)
6917 if (TREE_CODE (tem
) != SSA_NAME
)
6919 /* For all values we only valueize to an available leader
6920 which means we can use SSA name info without restriction. */
6921 tem
= rpo_avail
->eliminate_avail (vn_context_bb
, tem
);
6930 /* Insert on PRED_E predicates derived from CODE OPS being true besides the
6931 inverted condition. */
6934 insert_related_predicates_on_edge (enum tree_code code
, tree
*ops
, edge pred_e
)
6939 /* a < b -> a {!,<}= b */
6940 vn_nary_op_insert_pieces_predicated (2, NE_EXPR
, boolean_type_node
,
6941 ops
, boolean_true_node
, 0, pred_e
);
6942 vn_nary_op_insert_pieces_predicated (2, LE_EXPR
, boolean_type_node
,
6943 ops
, boolean_true_node
, 0, pred_e
);
6944 /* a < b -> ! a {>,=} b */
6945 vn_nary_op_insert_pieces_predicated (2, GT_EXPR
, boolean_type_node
,
6946 ops
, boolean_false_node
, 0, pred_e
);
6947 vn_nary_op_insert_pieces_predicated (2, EQ_EXPR
, boolean_type_node
,
6948 ops
, boolean_false_node
, 0, pred_e
);
6951 /* a > b -> a {!,>}= b */
6952 vn_nary_op_insert_pieces_predicated (2, NE_EXPR
, boolean_type_node
,
6953 ops
, boolean_true_node
, 0, pred_e
);
6954 vn_nary_op_insert_pieces_predicated (2, GE_EXPR
, boolean_type_node
,
6955 ops
, boolean_true_node
, 0, pred_e
);
6956 /* a > b -> ! a {<,=} b */
6957 vn_nary_op_insert_pieces_predicated (2, LT_EXPR
, boolean_type_node
,
6958 ops
, boolean_false_node
, 0, pred_e
);
6959 vn_nary_op_insert_pieces_predicated (2, EQ_EXPR
, boolean_type_node
,
6960 ops
, boolean_false_node
, 0, pred_e
);
6963 /* a == b -> ! a {<,>} b */
6964 vn_nary_op_insert_pieces_predicated (2, LT_EXPR
, boolean_type_node
,
6965 ops
, boolean_false_node
, 0, pred_e
);
6966 vn_nary_op_insert_pieces_predicated (2, GT_EXPR
, boolean_type_node
,
6967 ops
, boolean_false_node
, 0, pred_e
);
6972 /* Nothing besides inverted condition. */
6978 /* Main stmt worker for RPO VN, process BB. */
6981 process_bb (rpo_elim
&avail
, basic_block bb
,
6982 bool bb_visited
, bool iterate_phis
, bool iterate
, bool eliminate
,
6983 bool do_region
, bitmap exit_bbs
, bool skip_phis
)
6991 /* If we are in loop-closed SSA preserve this state. This is
6992 relevant when called on regions from outside of FRE/PRE. */
6993 bool lc_phi_nodes
= false;
6995 && loops_state_satisfies_p (LOOP_CLOSED_SSA
))
6996 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
6997 if (e
->src
->loop_father
!= e
->dest
->loop_father
6998 && flow_loop_nested_p (e
->dest
->loop_father
,
6999 e
->src
->loop_father
))
7001 lc_phi_nodes
= true;
7005 /* When we visit a loop header substitute into loop info. */
7006 if (!iterate
&& eliminate
&& bb
->loop_father
->header
== bb
)
7008 /* Keep fields in sync with substitute_in_loop_info. */
7009 if (bb
->loop_father
->nb_iterations
)
7010 bb
->loop_father
->nb_iterations
7011 = simplify_replace_tree (bb
->loop_father
->nb_iterations
,
7012 NULL_TREE
, NULL_TREE
, &vn_valueize_for_srt
);
7015 /* Value-number all defs in the basic-block. */
7017 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
7020 gphi
*phi
= gsi
.phi ();
7021 tree res
= PHI_RESULT (phi
);
7022 vn_ssa_aux_t res_info
= VN_INFO (res
);
7025 gcc_assert (!res_info
->visited
);
7026 res_info
->valnum
= VN_TOP
;
7027 res_info
->visited
= true;
7030 /* When not iterating force backedge values to varying. */
7031 visit_stmt (phi
, !iterate_phis
);
7032 if (virtual_operand_p (res
))
7036 /* The interesting case is gcc.dg/tree-ssa/pr22230.c for correctness
7037 how we handle backedges and availability.
7038 And gcc.dg/tree-ssa/ssa-sccvn-2.c for optimization. */
7039 tree val
= res_info
->valnum
;
7040 if (res
!= val
&& !iterate
&& eliminate
)
7042 if (tree leader
= avail
.eliminate_avail (bb
, res
))
7045 /* Preserve loop-closed SSA form. */
7047 || is_gimple_min_invariant (leader
)))
7049 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7051 fprintf (dump_file
, "Replaced redundant PHI node "
7053 print_generic_expr (dump_file
, res
);
7054 fprintf (dump_file
, " with ");
7055 print_generic_expr (dump_file
, leader
);
7056 fprintf (dump_file
, "\n");
7058 avail
.eliminations
++;
7060 if (may_propagate_copy (res
, leader
))
7062 /* Schedule for removal. */
7063 avail
.to_remove
.safe_push (phi
);
7066 /* ??? Else generate a copy stmt. */
7070 /* Only make defs available that not already are. But make
7071 sure loop-closed SSA PHI node defs are picked up for
7075 || ! avail
.eliminate_avail (bb
, res
))
7076 avail
.eliminate_push_avail (bb
, res
);
7079 /* For empty BBs mark outgoing edges executable. For non-empty BBs
7080 we do this when processing the last stmt as we have to do this
7081 before elimination which otherwise forces GIMPLE_CONDs to
7082 if (1 != 0) style when seeing non-executable edges. */
7083 if (gsi_end_p (gsi_start_bb (bb
)))
7085 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
7087 if (!(e
->flags
& EDGE_EXECUTABLE
))
7089 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7091 "marking outgoing edge %d -> %d executable\n",
7092 e
->src
->index
, e
->dest
->index
);
7093 e
->flags
|= EDGE_EXECUTABLE
;
7094 e
->dest
->flags
|= BB_EXECUTABLE
;
7096 else if (!(e
->dest
->flags
& BB_EXECUTABLE
))
7098 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7100 "marking destination block %d reachable\n",
7102 e
->dest
->flags
|= BB_EXECUTABLE
;
7106 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
7107 !gsi_end_p (gsi
); gsi_next (&gsi
))
7113 FOR_EACH_SSA_TREE_OPERAND (op
, gsi_stmt (gsi
), i
, SSA_OP_ALL_DEFS
)
7115 vn_ssa_aux_t op_info
= VN_INFO (op
);
7116 gcc_assert (!op_info
->visited
);
7117 op_info
->valnum
= VN_TOP
;
7118 op_info
->visited
= true;
7121 /* We somehow have to deal with uses that are not defined
7122 in the processed region. Forcing unvisited uses to
7123 varying here doesn't play well with def-use following during
7124 expression simplification, so we deal with this by checking
7125 the visited flag in SSA_VAL. */
7128 visit_stmt (gsi_stmt (gsi
));
7130 gimple
*last
= gsi_stmt (gsi
);
7132 switch (gimple_code (last
))
7135 e
= find_taken_edge (bb
, vn_valueize (gimple_switch_index
7136 (as_a
<gswitch
*> (last
))));
7140 tree lhs
= vn_valueize (gimple_cond_lhs (last
));
7141 tree rhs
= vn_valueize (gimple_cond_rhs (last
));
7142 tree val
= gimple_simplify (gimple_cond_code (last
),
7143 boolean_type_node
, lhs
, rhs
,
7145 /* If the condition didn't simplfy see if we have recorded
7146 an expression from sofar taken edges. */
7147 if (! val
|| TREE_CODE (val
) != INTEGER_CST
)
7149 vn_nary_op_t vnresult
;
7153 val
= vn_nary_op_lookup_pieces (2, gimple_cond_code (last
),
7154 boolean_type_node
, ops
,
7156 /* Did we get a predicated value? */
7157 if (! val
&& vnresult
&& vnresult
->predicated_values
)
7159 val
= vn_nary_op_get_predicated_value (vnresult
, bb
);
7160 if (val
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
7162 fprintf (dump_file
, "Got predicated value ");
7163 print_generic_expr (dump_file
, val
, TDF_NONE
);
7164 fprintf (dump_file
, " for ");
7165 print_gimple_stmt (dump_file
, last
, TDF_SLIM
);
7170 e
= find_taken_edge (bb
, val
);
7173 /* If we didn't manage to compute the taken edge then
7174 push predicated expressions for the condition itself
7175 and related conditions to the hashtables. This allows
7176 simplification of redundant conditions which is
7177 important as early cleanup. */
7178 edge true_e
, false_e
;
7179 extract_true_false_edges_from_block (bb
, &true_e
, &false_e
);
7180 enum tree_code code
= gimple_cond_code (last
);
7181 enum tree_code icode
7182 = invert_tree_comparison (code
, HONOR_NANS (lhs
));
7187 && bitmap_bit_p (exit_bbs
, true_e
->dest
->index
))
7190 && bitmap_bit_p (exit_bbs
, false_e
->dest
->index
))
7193 vn_nary_op_insert_pieces_predicated
7194 (2, code
, boolean_type_node
, ops
,
7195 boolean_true_node
, 0, true_e
);
7197 vn_nary_op_insert_pieces_predicated
7198 (2, code
, boolean_type_node
, ops
,
7199 boolean_false_node
, 0, false_e
);
7200 if (icode
!= ERROR_MARK
)
7203 vn_nary_op_insert_pieces_predicated
7204 (2, icode
, boolean_type_node
, ops
,
7205 boolean_false_node
, 0, true_e
);
7207 vn_nary_op_insert_pieces_predicated
7208 (2, icode
, boolean_type_node
, ops
,
7209 boolean_true_node
, 0, false_e
);
7211 /* Relax for non-integers, inverted condition handled
7213 if (INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
7216 insert_related_predicates_on_edge (code
, ops
, true_e
);
7218 insert_related_predicates_on_edge (icode
, ops
, false_e
);
7224 e
= find_taken_edge (bb
, vn_valueize (gimple_goto_dest (last
)));
7231 todo
= TODO_cleanup_cfg
;
7232 if (!(e
->flags
& EDGE_EXECUTABLE
))
7234 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7236 "marking known outgoing %sedge %d -> %d executable\n",
7237 e
->flags
& EDGE_DFS_BACK
? "back-" : "",
7238 e
->src
->index
, e
->dest
->index
);
7239 e
->flags
|= EDGE_EXECUTABLE
;
7240 e
->dest
->flags
|= BB_EXECUTABLE
;
7242 else if (!(e
->dest
->flags
& BB_EXECUTABLE
))
7244 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7246 "marking destination block %d reachable\n",
7248 e
->dest
->flags
|= BB_EXECUTABLE
;
7251 else if (gsi_one_before_end_p (gsi
))
7253 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
7255 if (!(e
->flags
& EDGE_EXECUTABLE
))
7257 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7259 "marking outgoing edge %d -> %d executable\n",
7260 e
->src
->index
, e
->dest
->index
);
7261 e
->flags
|= EDGE_EXECUTABLE
;
7262 e
->dest
->flags
|= BB_EXECUTABLE
;
7264 else if (!(e
->dest
->flags
& BB_EXECUTABLE
))
7266 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7268 "marking destination block %d reachable\n",
7270 e
->dest
->flags
|= BB_EXECUTABLE
;
7275 /* Eliminate. That also pushes to avail. */
7276 if (eliminate
&& ! iterate
)
7277 avail
.eliminate_stmt (bb
, &gsi
);
7279 /* If not eliminating, make all not already available defs
7281 FOR_EACH_SSA_TREE_OPERAND (op
, gsi_stmt (gsi
), i
, SSA_OP_DEF
)
7282 if (! avail
.eliminate_avail (bb
, op
))
7283 avail
.eliminate_push_avail (bb
, op
);
7286 /* Eliminate in destination PHI arguments. Always substitute in dest
7287 PHIs, even for non-executable edges. This handles region
7289 if (!iterate
&& eliminate
)
7290 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
7291 for (gphi_iterator gsi
= gsi_start_phis (e
->dest
);
7292 !gsi_end_p (gsi
); gsi_next (&gsi
))
7294 gphi
*phi
= gsi
.phi ();
7295 use_operand_p use_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
7296 tree arg
= USE_FROM_PTR (use_p
);
7297 if (TREE_CODE (arg
) != SSA_NAME
7298 || virtual_operand_p (arg
))
7301 if (SSA_NAME_IS_DEFAULT_DEF (arg
))
7303 sprime
= SSA_VAL (arg
);
7304 gcc_assert (TREE_CODE (sprime
) != SSA_NAME
7305 || SSA_NAME_IS_DEFAULT_DEF (sprime
));
7308 /* Look for sth available at the definition block of the argument.
7309 This avoids inconsistencies between availability there which
7310 decides if the stmt can be removed and availability at the
7311 use site. The SSA property ensures that things available
7312 at the definition are also available at uses. */
7313 sprime
= avail
.eliminate_avail (gimple_bb (SSA_NAME_DEF_STMT (arg
)),
7317 && may_propagate_copy (arg
, sprime
))
7318 propagate_value (use_p
, sprime
);
7321 vn_context_bb
= NULL
;
7325 /* Unwind state per basic-block. */
7329 /* Times this block has been visited. */
7331 /* Whether to handle this as iteration point or whether to treat
7332 incoming backedge PHI values as varying. */
7334 /* Maximum RPO index this block is reachable from. */
7338 vn_reference_t ref_top
;
7340 vn_nary_op_t nary_top
;
7343 /* Unwind the RPO VN state for iteration. */
7346 do_unwind (unwind_state
*to
, int rpo_idx
, rpo_elim
&avail
, int *bb_to_rpo
)
7348 gcc_assert (to
->iterate
);
7349 for (; last_inserted_nary
!= to
->nary_top
;
7350 last_inserted_nary
= last_inserted_nary
->next
)
7353 slot
= valid_info
->nary
->find_slot_with_hash
7354 (last_inserted_nary
, last_inserted_nary
->hashcode
, NO_INSERT
);
7355 /* Predication causes the need to restore previous state. */
7356 if ((*slot
)->unwind_to
)
7357 *slot
= (*slot
)->unwind_to
;
7359 valid_info
->nary
->clear_slot (slot
);
7361 for (; last_inserted_phi
!= to
->phi_top
;
7362 last_inserted_phi
= last_inserted_phi
->next
)
7365 slot
= valid_info
->phis
->find_slot_with_hash
7366 (last_inserted_phi
, last_inserted_phi
->hashcode
, NO_INSERT
);
7367 valid_info
->phis
->clear_slot (slot
);
7369 for (; last_inserted_ref
!= to
->ref_top
;
7370 last_inserted_ref
= last_inserted_ref
->next
)
7372 vn_reference_t
*slot
;
7373 slot
= valid_info
->references
->find_slot_with_hash
7374 (last_inserted_ref
, last_inserted_ref
->hashcode
, NO_INSERT
);
7375 (*slot
)->operands
.release ();
7376 valid_info
->references
->clear_slot (slot
);
7378 obstack_free (&vn_tables_obstack
, to
->ob_top
);
7380 /* Prune [rpo_idx, ] from avail. */
7381 /* ??? This is O(number-of-values-in-region) which is
7382 O(region-size) rather than O(iteration-piece). */
7383 for (hash_table
<vn_ssa_aux_hasher
>::iterator i
= vn_ssa_aux_hash
->begin ();
7384 i
!= vn_ssa_aux_hash
->end (); ++i
)
7388 if (bb_to_rpo
[(*i
)->avail
->location
] < rpo_idx
)
7390 vn_avail
*av
= (*i
)->avail
;
7391 (*i
)->avail
= (*i
)->avail
->next
;
7392 av
->next
= avail
.m_avail_freelist
;
7393 avail
.m_avail_freelist
= av
;
7398 /* Do VN on a SEME region specified by ENTRY and EXIT_BBS in FN.
7399 If ITERATE is true then treat backedges optimistically as not
7400 executed and iterate. If ELIMINATE is true then perform
7401 elimination, otherwise leave that to the caller. */
7404 do_rpo_vn (function
*fn
, edge entry
, bitmap exit_bbs
,
7405 bool iterate
, bool eliminate
)
7409 /* We currently do not support region-based iteration when
7410 elimination is requested. */
7411 gcc_assert (!entry
|| !iterate
|| !eliminate
);
7412 /* When iterating we need loop info up-to-date. */
7413 gcc_assert (!iterate
|| !loops_state_satisfies_p (LOOPS_NEED_FIXUP
));
7415 bool do_region
= entry
!= NULL
;
7418 entry
= single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (fn
));
7419 exit_bbs
= BITMAP_ALLOC (NULL
);
7420 bitmap_set_bit (exit_bbs
, EXIT_BLOCK
);
7423 /* Clear EDGE_DFS_BACK on "all" entry edges, RPO order compute will
7424 re-mark those that are contained in the region. */
7427 FOR_EACH_EDGE (e
, ei
, entry
->dest
->preds
)
7428 e
->flags
&= ~EDGE_DFS_BACK
;
7430 int *rpo
= XNEWVEC (int, n_basic_blocks_for_fn (fn
) - NUM_FIXED_BLOCKS
);
7431 auto_vec
<std::pair
<int, int> > toplevel_scc_extents
;
7432 int n
= rev_post_order_and_mark_dfs_back_seme
7433 (fn
, entry
, exit_bbs
, true, rpo
, !iterate
? &toplevel_scc_extents
: NULL
);
7436 BITMAP_FREE (exit_bbs
);
7438 /* If there are any non-DFS_BACK edges into entry->dest skip
7439 processing PHI nodes for that block. This supports
7440 value-numbering loop bodies w/o the actual loop. */
7441 FOR_EACH_EDGE (e
, ei
, entry
->dest
->preds
)
7443 && !(e
->flags
& EDGE_DFS_BACK
))
7445 bool skip_entry_phis
= e
!= NULL
;
7446 if (skip_entry_phis
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
7447 fprintf (dump_file
, "Region does not contain all edges into "
7448 "the entry block, skipping its PHIs.\n");
7450 int *bb_to_rpo
= XNEWVEC (int, last_basic_block_for_fn (fn
));
7451 for (int i
= 0; i
< n
; ++i
)
7452 bb_to_rpo
[rpo
[i
]] = i
;
7454 unwind_state
*rpo_state
= XNEWVEC (unwind_state
, n
);
7456 rpo_elim
avail (entry
->dest
);
7459 /* Verify we have no extra entries into the region. */
7460 if (flag_checking
&& do_region
)
7462 auto_bb_flag
bb_in_region (fn
);
7463 for (int i
= 0; i
< n
; ++i
)
7465 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
7466 bb
->flags
|= bb_in_region
;
7468 /* We can't merge the first two loops because we cannot rely
7469 on EDGE_DFS_BACK for edges not within the region. But if
7470 we decide to always have the bb_in_region flag we can
7471 do the checking during the RPO walk itself (but then it's
7472 also easy to handle MEME conservatively). */
7473 for (int i
= 0; i
< n
; ++i
)
7475 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
7478 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
7479 gcc_assert (e
== entry
7480 || (skip_entry_phis
&& bb
== entry
->dest
)
7481 || (e
->src
->flags
& bb_in_region
));
7483 for (int i
= 0; i
< n
; ++i
)
7485 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
7486 bb
->flags
&= ~bb_in_region
;
7490 /* Create the VN state. For the initial size of the various hashtables
7491 use a heuristic based on region size and number of SSA names. */
7492 unsigned region_size
= (((unsigned HOST_WIDE_INT
)n
* num_ssa_names
)
7493 / (n_basic_blocks_for_fn (fn
) - NUM_FIXED_BLOCKS
));
7494 VN_TOP
= create_tmp_var_raw (void_type_node
, "vn_top");
7496 next_constant_value_id
= -1;
7498 vn_ssa_aux_hash
= new hash_table
<vn_ssa_aux_hasher
> (region_size
* 2);
7499 gcc_obstack_init (&vn_ssa_aux_obstack
);
7501 gcc_obstack_init (&vn_tables_obstack
);
7502 gcc_obstack_init (&vn_tables_insert_obstack
);
7503 valid_info
= XCNEW (struct vn_tables_s
);
7504 allocate_vn_table (valid_info
, region_size
);
7505 last_inserted_ref
= NULL
;
7506 last_inserted_phi
= NULL
;
7507 last_inserted_nary
= NULL
;
7509 vn_valueize
= rpo_vn_valueize
;
7511 /* Initialize the unwind state and edge/BB executable state. */
7512 unsigned curr_scc
= 0;
7513 for (int i
= 0; i
< n
; ++i
)
7515 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
7516 rpo_state
[i
].visited
= 0;
7517 rpo_state
[i
].max_rpo
= i
;
7518 if (!iterate
&& curr_scc
< toplevel_scc_extents
.length ())
7520 if (i
>= toplevel_scc_extents
[curr_scc
].first
7521 && i
<= toplevel_scc_extents
[curr_scc
].second
)
7522 rpo_state
[i
].max_rpo
= toplevel_scc_extents
[curr_scc
].second
;
7523 if (i
== toplevel_scc_extents
[curr_scc
].second
)
7526 bb
->flags
&= ~BB_EXECUTABLE
;
7527 bool has_backedges
= false;
7530 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
7532 if (e
->flags
& EDGE_DFS_BACK
)
7533 has_backedges
= true;
7534 e
->flags
&= ~EDGE_EXECUTABLE
;
7535 if (iterate
|| e
== entry
|| (skip_entry_phis
&& bb
== entry
->dest
))
7538 rpo_state
[i
].iterate
= iterate
&& has_backedges
;
7540 entry
->flags
|= EDGE_EXECUTABLE
;
7541 entry
->dest
->flags
|= BB_EXECUTABLE
;
7543 /* As heuristic to improve compile-time we handle only the N innermost
7544 loops and the outermost one optimistically. */
7548 unsigned max_depth
= param_rpo_vn_max_loop_depth
;
7549 FOR_EACH_LOOP (loop
, LI_ONLY_INNERMOST
)
7550 if (loop_depth (loop
) > max_depth
)
7551 for (unsigned i
= 2;
7552 i
< loop_depth (loop
) - max_depth
; ++i
)
7554 basic_block header
= superloop_at_depth (loop
, i
)->header
;
7555 bool non_latch_backedge
= false;
7558 FOR_EACH_EDGE (e
, ei
, header
->preds
)
7559 if (e
->flags
& EDGE_DFS_BACK
)
7561 /* There can be a non-latch backedge into the header
7562 which is part of an outer irreducible region. We
7563 cannot avoid iterating this block then. */
7564 if (!dominated_by_p (CDI_DOMINATORS
,
7567 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7568 fprintf (dump_file
, "non-latch backedge %d -> %d "
7569 "forces iteration of loop %d\n",
7570 e
->src
->index
, e
->dest
->index
, loop
->num
);
7571 non_latch_backedge
= true;
7574 e
->flags
|= EDGE_EXECUTABLE
;
7576 rpo_state
[bb_to_rpo
[header
->index
]].iterate
= non_latch_backedge
;
7583 /* Go and process all blocks, iterating as necessary. */
7586 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[idx
]);
7588 /* If the block has incoming backedges remember unwind state. This
7589 is required even for non-executable blocks since in irreducible
7590 regions we might reach them via the backedge and re-start iterating
7592 Note we can individually mark blocks with incoming backedges to
7593 not iterate where we then handle PHIs conservatively. We do that
7594 heuristically to reduce compile-time for degenerate cases. */
7595 if (rpo_state
[idx
].iterate
)
7597 rpo_state
[idx
].ob_top
= obstack_alloc (&vn_tables_obstack
, 0);
7598 rpo_state
[idx
].ref_top
= last_inserted_ref
;
7599 rpo_state
[idx
].phi_top
= last_inserted_phi
;
7600 rpo_state
[idx
].nary_top
= last_inserted_nary
;
7603 if (!(bb
->flags
& BB_EXECUTABLE
))
7605 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7606 fprintf (dump_file
, "Block %d: BB%d found not executable\n",
7612 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7613 fprintf (dump_file
, "Processing block %d: BB%d\n", idx
, bb
->index
);
7615 todo
|= process_bb (avail
, bb
,
7616 rpo_state
[idx
].visited
!= 0,
7617 rpo_state
[idx
].iterate
,
7618 iterate
, eliminate
, do_region
, exit_bbs
, false);
7619 rpo_state
[idx
].visited
++;
7621 /* Verify if changed values flow over executable outgoing backedges
7622 and those change destination PHI values (that's the thing we
7623 can easily verify). Reduce over all such edges to the farthest
7625 int iterate_to
= -1;
7628 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
7629 if ((e
->flags
& (EDGE_DFS_BACK
|EDGE_EXECUTABLE
))
7630 == (EDGE_DFS_BACK
|EDGE_EXECUTABLE
)
7631 && rpo_state
[bb_to_rpo
[e
->dest
->index
]].iterate
)
7633 int destidx
= bb_to_rpo
[e
->dest
->index
];
7634 if (!rpo_state
[destidx
].visited
)
7636 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7637 fprintf (dump_file
, "Unvisited destination %d\n",
7639 if (iterate_to
== -1 || destidx
< iterate_to
)
7640 iterate_to
= destidx
;
7643 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7644 fprintf (dump_file
, "Looking for changed values of backedge"
7645 " %d->%d destination PHIs\n",
7646 e
->src
->index
, e
->dest
->index
);
7647 vn_context_bb
= e
->dest
;
7649 for (gsi
= gsi_start_phis (e
->dest
);
7650 !gsi_end_p (gsi
); gsi_next (&gsi
))
7652 bool inserted
= false;
7653 /* While we'd ideally just iterate on value changes
7654 we CSE PHIs and do that even across basic-block
7655 boundaries. So even hashtable state changes can
7656 be important (which is roughly equivalent to
7657 PHI argument value changes). To not excessively
7658 iterate because of that we track whether a PHI
7659 was CSEd to with GF_PLF_1. */
7660 bool phival_changed
;
7661 if ((phival_changed
= visit_phi (gsi
.phi (),
7663 || (inserted
&& gimple_plf (gsi
.phi (), GF_PLF_1
)))
7666 && dump_file
&& (dump_flags
& TDF_DETAILS
))
7667 fprintf (dump_file
, "PHI was CSEd and hashtable "
7668 "state (changed)\n");
7669 if (iterate_to
== -1 || destidx
< iterate_to
)
7670 iterate_to
= destidx
;
7674 vn_context_bb
= NULL
;
7676 if (iterate_to
!= -1)
7678 do_unwind (&rpo_state
[iterate_to
], iterate_to
, avail
, bb_to_rpo
);
7680 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7681 fprintf (dump_file
, "Iterating to %d BB%d\n",
7682 iterate_to
, rpo
[iterate_to
]);
7692 /* Process all blocks greedily with a worklist that enforces RPO
7693 processing of reachable blocks. */
7694 auto_bitmap worklist
;
7695 bitmap_set_bit (worklist
, 0);
7696 while (!bitmap_empty_p (worklist
))
7698 int idx
= bitmap_first_set_bit (worklist
);
7699 bitmap_clear_bit (worklist
, idx
);
7700 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[idx
]);
7701 gcc_assert ((bb
->flags
& BB_EXECUTABLE
)
7702 && !rpo_state
[idx
].visited
);
7704 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7705 fprintf (dump_file
, "Processing block %d: BB%d\n", idx
, bb
->index
);
7707 /* When we run into predecessor edges where we cannot trust its
7708 executable state mark them executable so PHI processing will
7710 ??? Do we need to force arguments flowing over that edge
7711 to be varying or will they even always be? */
7714 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
7715 if (!(e
->flags
& EDGE_EXECUTABLE
)
7716 && (bb
== entry
->dest
7717 || (!rpo_state
[bb_to_rpo
[e
->src
->index
]].visited
7718 && (rpo_state
[bb_to_rpo
[e
->src
->index
]].max_rpo
7721 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7722 fprintf (dump_file
, "Cannot trust state of predecessor "
7723 "edge %d -> %d, marking executable\n",
7724 e
->src
->index
, e
->dest
->index
);
7725 e
->flags
|= EDGE_EXECUTABLE
;
7729 todo
|= process_bb (avail
, bb
, false, false, false, eliminate
,
7730 do_region
, exit_bbs
,
7731 skip_entry_phis
&& bb
== entry
->dest
);
7732 rpo_state
[idx
].visited
++;
7734 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
7735 if ((e
->flags
& EDGE_EXECUTABLE
)
7736 && e
->dest
->index
!= EXIT_BLOCK
7737 && (!do_region
|| !bitmap_bit_p (exit_bbs
, e
->dest
->index
))
7738 && !rpo_state
[bb_to_rpo
[e
->dest
->index
]].visited
)
7739 bitmap_set_bit (worklist
, bb_to_rpo
[e
->dest
->index
]);
7743 /* If statistics or dump file active. */
7745 unsigned max_visited
= 1;
7746 for (int i
= 0; i
< n
; ++i
)
7748 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
7749 if (bb
->flags
& BB_EXECUTABLE
)
7751 statistics_histogram_event (cfun
, "RPO block visited times",
7752 rpo_state
[i
].visited
);
7753 if (rpo_state
[i
].visited
> max_visited
)
7754 max_visited
= rpo_state
[i
].visited
;
7756 unsigned nvalues
= 0, navail
= 0;
7757 for (hash_table
<vn_ssa_aux_hasher
>::iterator i
= vn_ssa_aux_hash
->begin ();
7758 i
!= vn_ssa_aux_hash
->end (); ++i
)
7761 vn_avail
*av
= (*i
)->avail
;
7768 statistics_counter_event (cfun
, "RPO blocks", n
);
7769 statistics_counter_event (cfun
, "RPO blocks visited", nblk
);
7770 statistics_counter_event (cfun
, "RPO blocks executable", nex
);
7771 statistics_histogram_event (cfun
, "RPO iterations", 10*nblk
/ nex
);
7772 statistics_histogram_event (cfun
, "RPO num values", nvalues
);
7773 statistics_histogram_event (cfun
, "RPO num avail", navail
);
7774 statistics_histogram_event (cfun
, "RPO num lattice",
7775 vn_ssa_aux_hash
->elements ());
7776 if (dump_file
&& (dump_flags
& (TDF_DETAILS
|TDF_STATS
)))
7778 fprintf (dump_file
, "RPO iteration over %d blocks visited %" PRIu64
7779 " blocks in total discovering %d executable blocks iterating "
7780 "%d.%d times, a block was visited max. %u times\n",
7782 (int)((10*nblk
/ nex
)/10), (int)((10*nblk
/ nex
)%10),
7784 fprintf (dump_file
, "RPO tracked %d values available at %d locations "
7785 "and %" PRIu64
" lattice elements\n",
7786 nvalues
, navail
, (uint64_t) vn_ssa_aux_hash
->elements ());
7791 /* When !iterate we already performed elimination during the RPO
7795 /* Elimination for region-based VN needs to be done within the
7797 gcc_assert (! do_region
);
7798 /* Note we can't use avail.walk here because that gets confused
7799 by the existing availability and it will be less efficient
7801 todo
|= eliminate_with_rpo_vn (NULL
);
7804 todo
|= avail
.eliminate_cleanup (do_region
);
7810 XDELETEVEC (bb_to_rpo
);
7812 XDELETEVEC (rpo_state
);
7817 /* Region-based entry for RPO VN. Performs value-numbering and elimination
7818 on the SEME region specified by ENTRY and EXIT_BBS. If ENTRY is not
7819 the only edge into the region at ENTRY->dest PHI nodes in ENTRY->dest
7820 are not considered. */
7823 do_rpo_vn (function
*fn
, edge entry
, bitmap exit_bbs
)
7825 default_vn_walk_kind
= VN_WALKREWRITE
;
7826 unsigned todo
= do_rpo_vn (fn
, entry
, exit_bbs
, false, true);
7834 const pass_data pass_data_fre
=
7836 GIMPLE_PASS
, /* type */
7838 OPTGROUP_NONE
, /* optinfo_flags */
7839 TV_TREE_FRE
, /* tv_id */
7840 ( PROP_cfg
| PROP_ssa
), /* properties_required */
7841 0, /* properties_provided */
7842 0, /* properties_destroyed */
7843 0, /* todo_flags_start */
7844 0, /* todo_flags_finish */
7847 class pass_fre
: public gimple_opt_pass
7850 pass_fre (gcc::context
*ctxt
)
7851 : gimple_opt_pass (pass_data_fre
, ctxt
), may_iterate (true)
7854 /* opt_pass methods: */
7855 opt_pass
* clone () { return new pass_fre (m_ctxt
); }
7856 void set_pass_param (unsigned int n
, bool param
)
7858 gcc_assert (n
== 0);
7859 may_iterate
= param
;
7861 virtual bool gate (function
*)
7863 return flag_tree_fre
!= 0 && (may_iterate
|| optimize
> 1);
7865 virtual unsigned int execute (function
*);
7869 }; // class pass_fre
7872 pass_fre::execute (function
*fun
)
7876 /* At -O[1g] use the cheap non-iterating mode. */
7877 bool iterate_p
= may_iterate
&& (optimize
> 1);
7878 calculate_dominance_info (CDI_DOMINATORS
);
7880 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
7882 default_vn_walk_kind
= VN_WALKREWRITE
;
7883 todo
= do_rpo_vn (fun
, NULL
, NULL
, iterate_p
, true);
7887 loop_optimizer_finalize ();
7889 if (scev_initialized_p ())
7892 /* For late FRE after IVOPTs and unrolling, see if we can
7893 remove some TREE_ADDRESSABLE and rewrite stuff into SSA. */
7895 todo
|= TODO_update_address_taken
;
7903 make_pass_fre (gcc::context
*ctxt
)
7905 return new pass_fre (ctxt
);
7908 #undef BB_EXECUTABLE