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
;
252 /* Pretty-print OPS to OUTFILE. */
255 print_vn_reference_ops (FILE *outfile
, const vec
<vn_reference_op_s
> ops
)
257 vn_reference_op_t vro
;
259 fprintf (outfile
, "{");
260 for (i
= 0; ops
.iterate (i
, &vro
); i
++)
262 bool closebrace
= false;
263 if (vro
->opcode
!= SSA_NAME
264 && TREE_CODE_CLASS (vro
->opcode
) != tcc_declaration
)
266 fprintf (outfile
, "%s", get_tree_code_name (vro
->opcode
));
269 fprintf (outfile
, "<");
275 print_generic_expr (outfile
, vro
->op0
);
278 fprintf (outfile
, ",");
279 print_generic_expr (outfile
, vro
->op1
);
283 fprintf (outfile
, ",");
284 print_generic_expr (outfile
, vro
->op2
);
288 fprintf (outfile
, ">");
289 if (i
!= ops
.length () - 1)
290 fprintf (outfile
, ",");
292 fprintf (outfile
, "}");
296 debug_vn_reference_ops (const vec
<vn_reference_op_s
> ops
)
298 print_vn_reference_ops (stderr
, ops
);
299 fputc ('\n', stderr
);
302 /* The set of VN hashtables. */
304 typedef struct vn_tables_s
306 vn_nary_op_table_type
*nary
;
307 vn_phi_table_type
*phis
;
308 vn_reference_table_type
*references
;
312 /* vn_constant hashtable helpers. */
314 struct vn_constant_hasher
: free_ptr_hash
<vn_constant_s
>
316 static inline hashval_t
hash (const vn_constant_s
*);
317 static inline bool equal (const vn_constant_s
*, const vn_constant_s
*);
320 /* Hash table hash function for vn_constant_t. */
323 vn_constant_hasher::hash (const vn_constant_s
*vc1
)
325 return vc1
->hashcode
;
328 /* Hash table equality function for vn_constant_t. */
331 vn_constant_hasher::equal (const vn_constant_s
*vc1
, const vn_constant_s
*vc2
)
333 if (vc1
->hashcode
!= vc2
->hashcode
)
336 return vn_constant_eq_with_type (vc1
->constant
, vc2
->constant
);
339 static hash_table
<vn_constant_hasher
> *constant_to_value_id
;
342 /* Obstack we allocate the vn-tables elements from. */
343 static obstack vn_tables_obstack
;
344 /* Special obstack we never unwind. */
345 static obstack vn_tables_insert_obstack
;
347 static vn_reference_t last_inserted_ref
;
348 static vn_phi_t last_inserted_phi
;
349 static vn_nary_op_t last_inserted_nary
;
350 static vn_ssa_aux_t last_pushed_avail
;
352 /* Valid hashtables storing information we have proven to be
354 static vn_tables_t valid_info
;
357 /* Valueization hook for simplify_replace_tree. Valueize NAME if it is
358 an SSA name, otherwise just return it. */
359 tree (*vn_valueize
) (tree
);
361 vn_valueize_for_srt (tree t
, void* context ATTRIBUTE_UNUSED
)
363 basic_block saved_vn_context_bb
= vn_context_bb
;
364 /* Look for sth available at the definition block of the argument.
365 This avoids inconsistencies between availability there which
366 decides if the stmt can be removed and availability at the
367 use site. The SSA property ensures that things available
368 at the definition are also available at uses. */
369 if (!SSA_NAME_IS_DEFAULT_DEF (t
))
370 vn_context_bb
= gimple_bb (SSA_NAME_DEF_STMT (t
));
371 tree res
= vn_valueize (t
);
372 vn_context_bb
= saved_vn_context_bb
;
377 /* This represents the top of the VN lattice, which is the universal
382 /* Unique counter for our value ids. */
384 static unsigned int next_value_id
;
385 static int next_constant_value_id
;
388 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
389 are allocated on an obstack for locality reasons, and to free them
390 without looping over the vec. */
392 struct vn_ssa_aux_hasher
: typed_noop_remove
<vn_ssa_aux_t
>
394 typedef vn_ssa_aux_t value_type
;
395 typedef tree compare_type
;
396 static inline hashval_t
hash (const value_type
&);
397 static inline bool equal (const value_type
&, const compare_type
&);
398 static inline void mark_deleted (value_type
&) {}
399 static const bool empty_zero_p
= true;
400 static inline void mark_empty (value_type
&e
) { e
= NULL
; }
401 static inline bool is_deleted (value_type
&) { return false; }
402 static inline bool is_empty (value_type
&e
) { return e
== NULL
; }
406 vn_ssa_aux_hasher::hash (const value_type
&entry
)
408 return SSA_NAME_VERSION (entry
->name
);
412 vn_ssa_aux_hasher::equal (const value_type
&entry
, const compare_type
&name
)
414 return name
== entry
->name
;
417 static hash_table
<vn_ssa_aux_hasher
> *vn_ssa_aux_hash
;
418 typedef hash_table
<vn_ssa_aux_hasher
>::iterator vn_ssa_aux_iterator_type
;
419 static struct obstack vn_ssa_aux_obstack
;
421 static vn_nary_op_t
vn_nary_op_insert_stmt (gimple
*, tree
);
422 static unsigned int vn_nary_length_from_stmt (gimple
*);
423 static vn_nary_op_t
alloc_vn_nary_op_noinit (unsigned int, obstack
*);
424 static vn_nary_op_t
vn_nary_op_insert_into (vn_nary_op_t
,
425 vn_nary_op_table_type
*, bool);
426 static void init_vn_nary_op_from_stmt (vn_nary_op_t
, gassign
*);
427 static void init_vn_nary_op_from_pieces (vn_nary_op_t
, unsigned int,
428 enum tree_code
, tree
, tree
*);
429 static tree
vn_lookup_simplify_result (gimple_match_op
*);
430 static vn_reference_t vn_reference_lookup_or_insert_for_pieces
431 (tree
, alias_set_type
, alias_set_type
, tree
,
432 vec
<vn_reference_op_s
, va_heap
>, tree
);
434 /* Return whether there is value numbering information for a given SSA name. */
437 has_VN_INFO (tree name
)
439 return vn_ssa_aux_hash
->find_with_hash (name
, SSA_NAME_VERSION (name
));
446 = vn_ssa_aux_hash
->find_slot_with_hash (name
, SSA_NAME_VERSION (name
),
451 vn_ssa_aux_t newinfo
= *res
= XOBNEW (&vn_ssa_aux_obstack
, struct vn_ssa_aux
);
452 memset (newinfo
, 0, sizeof (struct vn_ssa_aux
));
453 newinfo
->name
= name
;
454 newinfo
->valnum
= VN_TOP
;
455 /* We are using the visited flag to handle uses with defs not within the
456 region being value-numbered. */
457 newinfo
->visited
= false;
459 /* Given we create the VN_INFOs on-demand now we have to do initialization
460 different than VN_TOP here. */
461 if (SSA_NAME_IS_DEFAULT_DEF (name
))
462 switch (TREE_CODE (SSA_NAME_VAR (name
)))
465 /* All undefined vars are VARYING. */
466 newinfo
->valnum
= name
;
467 newinfo
->visited
= true;
471 /* Parameters are VARYING but we can record a condition
472 if we know it is a non-NULL pointer. */
473 newinfo
->visited
= true;
474 newinfo
->valnum
= name
;
475 if (POINTER_TYPE_P (TREE_TYPE (name
))
476 && nonnull_arg_p (SSA_NAME_VAR (name
)))
480 ops
[1] = build_int_cst (TREE_TYPE (name
), 0);
482 /* Allocate from non-unwinding stack. */
483 nary
= alloc_vn_nary_op_noinit (2, &vn_tables_insert_obstack
);
484 init_vn_nary_op_from_pieces (nary
, 2, NE_EXPR
,
485 boolean_type_node
, ops
);
486 nary
->predicated_values
= 0;
487 nary
->u
.result
= boolean_true_node
;
488 vn_nary_op_insert_into (nary
, valid_info
->nary
, true);
489 gcc_assert (nary
->unwind_to
== NULL
);
490 /* Also do not link it into the undo chain. */
491 last_inserted_nary
= nary
->next
;
492 nary
->next
= (vn_nary_op_t
)(void *)-1;
493 nary
= alloc_vn_nary_op_noinit (2, &vn_tables_insert_obstack
);
494 init_vn_nary_op_from_pieces (nary
, 2, EQ_EXPR
,
495 boolean_type_node
, ops
);
496 nary
->predicated_values
= 0;
497 nary
->u
.result
= boolean_false_node
;
498 vn_nary_op_insert_into (nary
, valid_info
->nary
, true);
499 gcc_assert (nary
->unwind_to
== NULL
);
500 last_inserted_nary
= nary
->next
;
501 nary
->next
= (vn_nary_op_t
)(void *)-1;
502 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
504 fprintf (dump_file
, "Recording ");
505 print_generic_expr (dump_file
, name
, TDF_SLIM
);
506 fprintf (dump_file
, " != 0\n");
512 /* If the result is passed by invisible reference the default
513 def is initialized, otherwise it's uninitialized. Still
514 undefined is varying. */
515 newinfo
->visited
= true;
516 newinfo
->valnum
= name
;
525 /* Return the SSA value of X. */
528 SSA_VAL (tree x
, bool *visited
= NULL
)
530 vn_ssa_aux_t tem
= vn_ssa_aux_hash
->find_with_hash (x
, SSA_NAME_VERSION (x
));
532 *visited
= tem
&& tem
->visited
;
533 return tem
&& tem
->visited
? tem
->valnum
: x
;
536 /* Return the SSA value of the VUSE x, supporting released VDEFs
537 during elimination which will value-number the VDEF to the
538 associated VUSE (but not substitute in the whole lattice). */
541 vuse_ssa_val (tree x
)
549 gcc_assert (x
!= VN_TOP
);
551 while (SSA_NAME_IN_FREE_LIST (x
));
556 /* Similar to the above but used as callback for walk_non_aliased_vuses
557 and thus should stop at unvisited VUSE to not walk across region
561 vuse_valueize (tree vuse
)
566 vuse
= SSA_VAL (vuse
, &visited
);
569 gcc_assert (vuse
!= VN_TOP
);
571 while (SSA_NAME_IN_FREE_LIST (vuse
));
576 /* Return the vn_kind the expression computed by the stmt should be
580 vn_get_stmt_kind (gimple
*stmt
)
582 switch (gimple_code (stmt
))
590 enum tree_code code
= gimple_assign_rhs_code (stmt
);
591 tree rhs1
= gimple_assign_rhs1 (stmt
);
592 switch (get_gimple_rhs_class (code
))
594 case GIMPLE_UNARY_RHS
:
595 case GIMPLE_BINARY_RHS
:
596 case GIMPLE_TERNARY_RHS
:
598 case GIMPLE_SINGLE_RHS
:
599 switch (TREE_CODE_CLASS (code
))
602 /* VOP-less references can go through unary case. */
603 if ((code
== REALPART_EXPR
604 || code
== IMAGPART_EXPR
605 || code
== VIEW_CONVERT_EXPR
606 || code
== BIT_FIELD_REF
)
607 && (TREE_CODE (TREE_OPERAND (rhs1
, 0)) == SSA_NAME
608 || is_gimple_min_invariant (TREE_OPERAND (rhs1
, 0))))
612 case tcc_declaration
:
619 if (code
== ADDR_EXPR
)
620 return (is_gimple_min_invariant (rhs1
)
621 ? VN_CONSTANT
: VN_REFERENCE
);
622 else if (code
== CONSTRUCTOR
)
635 /* Lookup a value id for CONSTANT and return it. If it does not
639 get_constant_value_id (tree constant
)
641 vn_constant_s
**slot
;
642 struct vn_constant_s vc
;
644 vc
.hashcode
= vn_hash_constant_with_type (constant
);
645 vc
.constant
= constant
;
646 slot
= constant_to_value_id
->find_slot (&vc
, NO_INSERT
);
648 return (*slot
)->value_id
;
652 /* Lookup a value id for CONSTANT, and if it does not exist, create a
653 new one and return it. If it does exist, return it. */
656 get_or_alloc_constant_value_id (tree constant
)
658 vn_constant_s
**slot
;
659 struct vn_constant_s vc
;
662 /* If the hashtable isn't initialized we're not running from PRE and thus
663 do not need value-ids. */
664 if (!constant_to_value_id
)
667 vc
.hashcode
= vn_hash_constant_with_type (constant
);
668 vc
.constant
= constant
;
669 slot
= constant_to_value_id
->find_slot (&vc
, INSERT
);
671 return (*slot
)->value_id
;
673 vcp
= XNEW (struct vn_constant_s
);
674 vcp
->hashcode
= vc
.hashcode
;
675 vcp
->constant
= constant
;
676 vcp
->value_id
= get_next_constant_value_id ();
678 return vcp
->value_id
;
681 /* Compute the hash for a reference operand VRO1. */
684 vn_reference_op_compute_hash (const vn_reference_op_t vro1
, inchash::hash
&hstate
)
686 hstate
.add_int (vro1
->opcode
);
688 inchash::add_expr (vro1
->op0
, hstate
);
690 inchash::add_expr (vro1
->op1
, hstate
);
692 inchash::add_expr (vro1
->op2
, hstate
);
695 /* Compute a hash for the reference operation VR1 and return it. */
698 vn_reference_compute_hash (const vn_reference_t vr1
)
700 inchash::hash hstate
;
703 vn_reference_op_t vro
;
707 FOR_EACH_VEC_ELT (vr1
->operands
, i
, vro
)
709 if (vro
->opcode
== MEM_REF
)
711 else if (vro
->opcode
!= ADDR_EXPR
)
713 if (maybe_ne (vro
->off
, -1))
715 if (known_eq (off
, -1))
721 if (maybe_ne (off
, -1)
722 && maybe_ne (off
, 0))
723 hstate
.add_poly_int (off
);
726 && vro
->opcode
== ADDR_EXPR
)
730 tree op
= TREE_OPERAND (vro
->op0
, 0);
731 hstate
.add_int (TREE_CODE (op
));
732 inchash::add_expr (op
, hstate
);
736 vn_reference_op_compute_hash (vro
, hstate
);
739 result
= hstate
.end ();
740 /* ??? We would ICE later if we hash instead of adding that in. */
742 result
+= SSA_NAME_VERSION (vr1
->vuse
);
747 /* Return true if reference operations VR1 and VR2 are equivalent. This
748 means they have the same set of operands and vuses. */
751 vn_reference_eq (const_vn_reference_t
const vr1
, const_vn_reference_t
const vr2
)
755 /* Early out if this is not a hash collision. */
756 if (vr1
->hashcode
!= vr2
->hashcode
)
759 /* The VOP needs to be the same. */
760 if (vr1
->vuse
!= vr2
->vuse
)
763 /* If the operands are the same we are done. */
764 if (vr1
->operands
== vr2
->operands
)
767 if (!vr1
->type
|| !vr2
->type
)
769 if (vr1
->type
!= vr2
->type
)
772 else if (COMPLETE_TYPE_P (vr1
->type
) != COMPLETE_TYPE_P (vr2
->type
)
773 || (COMPLETE_TYPE_P (vr1
->type
)
774 && !expressions_equal_p (TYPE_SIZE (vr1
->type
),
775 TYPE_SIZE (vr2
->type
))))
777 else if (INTEGRAL_TYPE_P (vr1
->type
)
778 && INTEGRAL_TYPE_P (vr2
->type
))
780 if (TYPE_PRECISION (vr1
->type
) != TYPE_PRECISION (vr2
->type
))
783 else if (INTEGRAL_TYPE_P (vr1
->type
)
784 && (TYPE_PRECISION (vr1
->type
)
785 != TREE_INT_CST_LOW (TYPE_SIZE (vr1
->type
))))
787 else if (INTEGRAL_TYPE_P (vr2
->type
)
788 && (TYPE_PRECISION (vr2
->type
)
789 != TREE_INT_CST_LOW (TYPE_SIZE (vr2
->type
))))
796 poly_int64 off1
= 0, off2
= 0;
797 vn_reference_op_t vro1
, vro2
;
798 vn_reference_op_s tem1
, tem2
;
799 bool deref1
= false, deref2
= false;
800 for (; vr1
->operands
.iterate (i
, &vro1
); i
++)
802 if (vro1
->opcode
== MEM_REF
)
804 /* Do not look through a storage order barrier. */
805 else if (vro1
->opcode
== VIEW_CONVERT_EXPR
&& vro1
->reverse
)
807 if (known_eq (vro1
->off
, -1))
811 for (; vr2
->operands
.iterate (j
, &vro2
); j
++)
813 if (vro2
->opcode
== MEM_REF
)
815 /* Do not look through a storage order barrier. */
816 else if (vro2
->opcode
== VIEW_CONVERT_EXPR
&& vro2
->reverse
)
818 if (known_eq (vro2
->off
, -1))
822 if (maybe_ne (off1
, off2
))
824 if (deref1
&& vro1
->opcode
== ADDR_EXPR
)
826 memset (&tem1
, 0, sizeof (tem1
));
827 tem1
.op0
= TREE_OPERAND (vro1
->op0
, 0);
828 tem1
.type
= TREE_TYPE (tem1
.op0
);
829 tem1
.opcode
= TREE_CODE (tem1
.op0
);
833 if (deref2
&& vro2
->opcode
== ADDR_EXPR
)
835 memset (&tem2
, 0, sizeof (tem2
));
836 tem2
.op0
= TREE_OPERAND (vro2
->op0
, 0);
837 tem2
.type
= TREE_TYPE (tem2
.op0
);
838 tem2
.opcode
= TREE_CODE (tem2
.op0
);
842 if (deref1
!= deref2
)
844 if (!vn_reference_op_eq (vro1
, vro2
))
849 while (vr1
->operands
.length () != i
850 || vr2
->operands
.length () != j
);
855 /* Copy the operations present in load/store REF into RESULT, a vector of
856 vn_reference_op_s's. */
859 copy_reference_ops_from_ref (tree ref
, vec
<vn_reference_op_s
> *result
)
861 /* For non-calls, store the information that makes up the address. */
865 vn_reference_op_s temp
;
867 memset (&temp
, 0, sizeof (temp
));
868 temp
.type
= TREE_TYPE (ref
);
869 temp
.opcode
= TREE_CODE (ref
);
875 temp
.op0
= TREE_OPERAND (ref
, 1);
878 temp
.op0
= TREE_OPERAND (ref
, 1);
882 /* The base address gets its own vn_reference_op_s structure. */
883 temp
.op0
= TREE_OPERAND (ref
, 1);
884 if (!mem_ref_offset (ref
).to_shwi (&temp
.off
))
886 temp
.clique
= MR_DEPENDENCE_CLIQUE (ref
);
887 temp
.base
= MR_DEPENDENCE_BASE (ref
);
888 temp
.reverse
= REF_REVERSE_STORAGE_ORDER (ref
);
891 /* The base address gets its own vn_reference_op_s structure. */
892 temp
.op0
= TMR_INDEX (ref
);
893 temp
.op1
= TMR_STEP (ref
);
894 temp
.op2
= TMR_OFFSET (ref
);
895 temp
.clique
= MR_DEPENDENCE_CLIQUE (ref
);
896 temp
.base
= MR_DEPENDENCE_BASE (ref
);
897 result
->safe_push (temp
);
898 memset (&temp
, 0, sizeof (temp
));
899 temp
.type
= NULL_TREE
;
900 temp
.opcode
= ERROR_MARK
;
901 temp
.op0
= TMR_INDEX2 (ref
);
905 /* Record bits, position and storage order. */
906 temp
.op0
= TREE_OPERAND (ref
, 1);
907 temp
.op1
= TREE_OPERAND (ref
, 2);
908 if (!multiple_p (bit_field_offset (ref
), BITS_PER_UNIT
, &temp
.off
))
910 temp
.reverse
= REF_REVERSE_STORAGE_ORDER (ref
);
913 /* The field decl is enough to unambiguously specify the field,
914 a matching type is not necessary and a mismatching type
915 is always a spurious difference. */
916 temp
.type
= NULL_TREE
;
917 temp
.op0
= TREE_OPERAND (ref
, 1);
918 temp
.op1
= TREE_OPERAND (ref
, 2);
920 tree this_offset
= component_ref_field_offset (ref
);
922 && poly_int_tree_p (this_offset
))
924 tree bit_offset
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
925 if (TREE_INT_CST_LOW (bit_offset
) % BITS_PER_UNIT
== 0)
928 = (wi::to_poly_offset (this_offset
)
929 + (wi::to_offset (bit_offset
) >> LOG2_BITS_PER_UNIT
));
930 /* Probibit value-numbering zero offset components
931 of addresses the same before the pass folding
932 __builtin_object_size had a chance to run. */
933 if (TREE_CODE (orig
) != ADDR_EXPR
935 || (cfun
->curr_properties
& PROP_objsz
))
936 off
.to_shwi (&temp
.off
);
941 case ARRAY_RANGE_REF
:
944 tree eltype
= TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref
, 0)));
945 /* Record index as operand. */
946 temp
.op0
= TREE_OPERAND (ref
, 1);
947 /* Always record lower bounds and element size. */
948 temp
.op1
= array_ref_low_bound (ref
);
949 /* But record element size in units of the type alignment. */
950 temp
.op2
= TREE_OPERAND (ref
, 3);
951 temp
.align
= eltype
->type_common
.align
;
953 temp
.op2
= size_binop (EXACT_DIV_EXPR
, TYPE_SIZE_UNIT (eltype
),
954 size_int (TYPE_ALIGN_UNIT (eltype
)));
955 if (poly_int_tree_p (temp
.op0
)
956 && poly_int_tree_p (temp
.op1
)
957 && TREE_CODE (temp
.op2
) == INTEGER_CST
)
959 poly_offset_int off
= ((wi::to_poly_offset (temp
.op0
)
960 - wi::to_poly_offset (temp
.op1
))
961 * wi::to_offset (temp
.op2
)
962 * vn_ref_op_align_unit (&temp
));
963 off
.to_shwi (&temp
.off
);
968 if (DECL_HARD_REGISTER (ref
))
977 /* Canonicalize decls to MEM[&decl] which is what we end up with
978 when valueizing MEM[ptr] with ptr = &decl. */
979 temp
.opcode
= MEM_REF
;
980 temp
.op0
= build_int_cst (build_pointer_type (TREE_TYPE (ref
)), 0);
982 result
->safe_push (temp
);
983 temp
.opcode
= ADDR_EXPR
;
984 temp
.op0
= build1 (ADDR_EXPR
, TREE_TYPE (temp
.op0
), ref
);
985 temp
.type
= TREE_TYPE (temp
.op0
);
1000 if (is_gimple_min_invariant (ref
))
1006 /* These are only interesting for their operands, their
1007 existence, and their type. They will never be the last
1008 ref in the chain of references (IE they require an
1009 operand), so we don't have to put anything
1010 for op* as it will be handled by the iteration */
1014 case VIEW_CONVERT_EXPR
:
1016 temp
.reverse
= storage_order_barrier_p (ref
);
1019 /* This is only interesting for its constant offset. */
1020 temp
.off
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref
)));
1025 result
->safe_push (temp
);
1027 if (REFERENCE_CLASS_P (ref
)
1028 || TREE_CODE (ref
) == MODIFY_EXPR
1029 || TREE_CODE (ref
) == WITH_SIZE_EXPR
1030 || (TREE_CODE (ref
) == ADDR_EXPR
1031 && !is_gimple_min_invariant (ref
)))
1032 ref
= TREE_OPERAND (ref
, 0);
1038 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
1039 operands in *OPS, the reference alias set SET and the reference type TYPE.
1040 Return true if something useful was produced. */
1043 ao_ref_init_from_vn_reference (ao_ref
*ref
,
1044 alias_set_type set
, alias_set_type base_set
,
1045 tree type
, const vec
<vn_reference_op_s
> &ops
)
1048 tree base
= NULL_TREE
;
1049 tree
*op0_p
= &base
;
1050 poly_offset_int offset
= 0;
1051 poly_offset_int max_size
;
1052 poly_offset_int size
= -1;
1053 tree size_tree
= NULL_TREE
;
1055 /* We don't handle calls. */
1059 machine_mode mode
= TYPE_MODE (type
);
1060 if (mode
== BLKmode
)
1061 size_tree
= TYPE_SIZE (type
);
1063 size
= GET_MODE_BITSIZE (mode
);
1064 if (size_tree
!= NULL_TREE
1065 && poly_int_tree_p (size_tree
))
1066 size
= wi::to_poly_offset (size_tree
);
1068 /* Lower the final access size from the outermost expression. */
1069 const_vn_reference_op_t cst_op
= &ops
[0];
1070 /* Cast away constness for the sake of the const-unsafe
1071 FOR_EACH_VEC_ELT(). */
1072 vn_reference_op_t op
= const_cast<vn_reference_op_t
>(cst_op
);
1073 size_tree
= NULL_TREE
;
1074 if (op
->opcode
== COMPONENT_REF
)
1075 size_tree
= DECL_SIZE (op
->op0
);
1076 else if (op
->opcode
== BIT_FIELD_REF
)
1077 size_tree
= op
->op0
;
1078 if (size_tree
!= NULL_TREE
1079 && poly_int_tree_p (size_tree
)
1080 && (!known_size_p (size
)
1081 || known_lt (wi::to_poly_offset (size_tree
), size
)))
1082 size
= wi::to_poly_offset (size_tree
);
1084 /* Initially, maxsize is the same as the accessed element size.
1085 In the following it will only grow (or become -1). */
1088 /* Compute cumulative bit-offset for nested component-refs and array-refs,
1089 and find the ultimate containing object. */
1090 FOR_EACH_VEC_ELT (ops
, i
, op
)
1094 /* These may be in the reference ops, but we cannot do anything
1095 sensible with them here. */
1097 /* Apart from ADDR_EXPR arguments to MEM_REF. */
1098 if (base
!= NULL_TREE
1099 && TREE_CODE (base
) == MEM_REF
1101 && DECL_P (TREE_OPERAND (op
->op0
, 0)))
1103 const_vn_reference_op_t pop
= &ops
[i
-1];
1104 base
= TREE_OPERAND (op
->op0
, 0);
1105 if (known_eq (pop
->off
, -1))
1111 offset
+= pop
->off
* BITS_PER_UNIT
;
1119 /* Record the base objects. */
1121 *op0_p
= build2 (MEM_REF
, op
->type
,
1122 NULL_TREE
, op
->op0
);
1123 MR_DEPENDENCE_CLIQUE (*op0_p
) = op
->clique
;
1124 MR_DEPENDENCE_BASE (*op0_p
) = op
->base
;
1125 op0_p
= &TREE_OPERAND (*op0_p
, 0);
1136 /* And now the usual component-reference style ops. */
1138 offset
+= wi::to_poly_offset (op
->op1
);
1143 tree field
= op
->op0
;
1144 /* We do not have a complete COMPONENT_REF tree here so we
1145 cannot use component_ref_field_offset. Do the interesting
1147 tree this_offset
= DECL_FIELD_OFFSET (field
);
1149 if (op
->op1
|| !poly_int_tree_p (this_offset
))
1153 poly_offset_int woffset
= (wi::to_poly_offset (this_offset
)
1154 << LOG2_BITS_PER_UNIT
);
1155 woffset
+= wi::to_offset (DECL_FIELD_BIT_OFFSET (field
));
1161 case ARRAY_RANGE_REF
:
1163 /* We recorded the lower bound and the element size. */
1164 if (!poly_int_tree_p (op
->op0
)
1165 || !poly_int_tree_p (op
->op1
)
1166 || TREE_CODE (op
->op2
) != INTEGER_CST
)
1170 poly_offset_int woffset
1171 = wi::sext (wi::to_poly_offset (op
->op0
)
1172 - wi::to_poly_offset (op
->op1
),
1173 TYPE_PRECISION (sizetype
));
1174 woffset
*= wi::to_offset (op
->op2
) * vn_ref_op_align_unit (op
);
1175 woffset
<<= LOG2_BITS_PER_UNIT
;
1187 case VIEW_CONVERT_EXPR
:
1204 if (base
== NULL_TREE
)
1207 ref
->ref
= NULL_TREE
;
1209 ref
->ref_alias_set
= set
;
1210 ref
->base_alias_set
= base_set
;
1211 /* We discount volatiles from value-numbering elsewhere. */
1212 ref
->volatile_p
= false;
1214 if (!size
.to_shwi (&ref
->size
) || maybe_lt (ref
->size
, 0))
1222 if (!offset
.to_shwi (&ref
->offset
))
1229 if (!max_size
.to_shwi (&ref
->max_size
) || maybe_lt (ref
->max_size
, 0))
1235 /* Copy the operations present in load/store/call REF into RESULT, a vector of
1236 vn_reference_op_s's. */
1239 copy_reference_ops_from_call (gcall
*call
,
1240 vec
<vn_reference_op_s
> *result
)
1242 vn_reference_op_s temp
;
1244 tree lhs
= gimple_call_lhs (call
);
1247 /* If 2 calls have a different non-ssa lhs, vdef value numbers should be
1248 different. By adding the lhs here in the vector, we ensure that the
1249 hashcode is different, guaranteeing a different value number. */
1250 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
1252 memset (&temp
, 0, sizeof (temp
));
1253 temp
.opcode
= MODIFY_EXPR
;
1254 temp
.type
= TREE_TYPE (lhs
);
1257 result
->safe_push (temp
);
1260 /* Copy the type, opcode, function, static chain and EH region, if any. */
1261 memset (&temp
, 0, sizeof (temp
));
1262 temp
.type
= gimple_call_fntype (call
);
1263 temp
.opcode
= CALL_EXPR
;
1264 temp
.op0
= gimple_call_fn (call
);
1265 temp
.op1
= gimple_call_chain (call
);
1266 if (stmt_could_throw_p (cfun
, call
) && (lr
= lookup_stmt_eh_lp (call
)) > 0)
1267 temp
.op2
= size_int (lr
);
1269 result
->safe_push (temp
);
1271 /* Copy the call arguments. As they can be references as well,
1272 just chain them together. */
1273 for (i
= 0; i
< gimple_call_num_args (call
); ++i
)
1275 tree callarg
= gimple_call_arg (call
, i
);
1276 copy_reference_ops_from_ref (callarg
, result
);
1280 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1281 *I_P to point to the last element of the replacement. */
1283 vn_reference_fold_indirect (vec
<vn_reference_op_s
> *ops
,
1286 unsigned int i
= *i_p
;
1287 vn_reference_op_t op
= &(*ops
)[i
];
1288 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1290 poly_int64 addr_offset
= 0;
1292 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1293 from .foo.bar to the preceding MEM_REF offset and replace the
1294 address with &OBJ. */
1295 addr_base
= get_addr_base_and_unit_offset_1 (TREE_OPERAND (op
->op0
, 0),
1296 &addr_offset
, vn_valueize
);
1297 gcc_checking_assert (addr_base
&& TREE_CODE (addr_base
) != MEM_REF
);
1298 if (addr_base
!= TREE_OPERAND (op
->op0
, 0))
1301 = (poly_offset_int::from (wi::to_poly_wide (mem_op
->op0
),
1304 mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1305 op
->op0
= build_fold_addr_expr (addr_base
);
1306 if (tree_fits_shwi_p (mem_op
->op0
))
1307 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1315 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1316 *I_P to point to the last element of the replacement. */
1318 vn_reference_maybe_forwprop_address (vec
<vn_reference_op_s
> *ops
,
1321 bool changed
= false;
1322 vn_reference_op_t op
;
1326 unsigned int i
= *i_p
;
1328 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1330 enum tree_code code
;
1331 poly_offset_int off
;
1333 def_stmt
= SSA_NAME_DEF_STMT (op
->op0
);
1334 if (!is_gimple_assign (def_stmt
))
1337 code
= gimple_assign_rhs_code (def_stmt
);
1338 if (code
!= ADDR_EXPR
1339 && code
!= POINTER_PLUS_EXPR
)
1342 off
= poly_offset_int::from (wi::to_poly_wide (mem_op
->op0
), SIGNED
);
1344 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1345 from .foo.bar to the preceding MEM_REF offset and replace the
1346 address with &OBJ. */
1347 if (code
== ADDR_EXPR
)
1349 tree addr
, addr_base
;
1350 poly_int64 addr_offset
;
1352 addr
= gimple_assign_rhs1 (def_stmt
);
1353 addr_base
= get_addr_base_and_unit_offset_1 (TREE_OPERAND (addr
, 0),
1356 /* If that didn't work because the address isn't invariant propagate
1357 the reference tree from the address operation in case the current
1358 dereference isn't offsetted. */
1360 && *i_p
== ops
->length () - 1
1361 && known_eq (off
, 0)
1362 /* This makes us disable this transform for PRE where the
1363 reference ops might be also used for code insertion which
1365 && default_vn_walk_kind
== VN_WALKREWRITE
)
1367 auto_vec
<vn_reference_op_s
, 32> tem
;
1368 copy_reference_ops_from_ref (TREE_OPERAND (addr
, 0), &tem
);
1369 /* Make sure to preserve TBAA info. The only objects not
1370 wrapped in MEM_REFs that can have their address taken are
1372 if (tem
.length () >= 2
1373 && tem
[tem
.length () - 2].opcode
== MEM_REF
)
1375 vn_reference_op_t new_mem_op
= &tem
[tem
.length () - 2];
1377 = wide_int_to_tree (TREE_TYPE (mem_op
->op0
),
1378 wi::to_poly_wide (new_mem_op
->op0
));
1381 gcc_assert (tem
.last ().opcode
== STRING_CST
);
1384 ops
->safe_splice (tem
);
1389 || TREE_CODE (addr_base
) != MEM_REF
1390 || (TREE_CODE (TREE_OPERAND (addr_base
, 0)) == SSA_NAME
1391 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (addr_base
,
1396 off
+= mem_ref_offset (addr_base
);
1397 op
->op0
= TREE_OPERAND (addr_base
, 0);
1402 ptr
= gimple_assign_rhs1 (def_stmt
);
1403 ptroff
= gimple_assign_rhs2 (def_stmt
);
1404 if (TREE_CODE (ptr
) != SSA_NAME
1405 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
)
1406 /* Make sure to not endlessly recurse.
1407 See gcc.dg/tree-ssa/20040408-1.c for an example. Can easily
1408 happen when we value-number a PHI to its backedge value. */
1409 || SSA_VAL (ptr
) == op
->op0
1410 || !poly_int_tree_p (ptroff
))
1413 off
+= wi::to_poly_offset (ptroff
);
1417 mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1418 if (tree_fits_shwi_p (mem_op
->op0
))
1419 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1422 /* ??? Can end up with endless recursion here!?
1423 gcc.c-torture/execute/strcmp-1.c */
1424 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1425 op
->op0
= SSA_VAL (op
->op0
);
1426 if (TREE_CODE (op
->op0
) != SSA_NAME
)
1427 op
->opcode
= TREE_CODE (op
->op0
);
1432 while (TREE_CODE (op
->op0
) == SSA_NAME
);
1434 /* Fold a remaining *&. */
1435 if (TREE_CODE (op
->op0
) == ADDR_EXPR
)
1436 vn_reference_fold_indirect (ops
, i_p
);
1441 /* Optimize the reference REF to a constant if possible or return
1442 NULL_TREE if not. */
1445 fully_constant_vn_reference_p (vn_reference_t ref
)
1447 vec
<vn_reference_op_s
> operands
= ref
->operands
;
1448 vn_reference_op_t op
;
1450 /* Try to simplify the translated expression if it is
1451 a call to a builtin function with at most two arguments. */
1453 if (op
->opcode
== CALL_EXPR
1454 && TREE_CODE (op
->op0
) == ADDR_EXPR
1455 && TREE_CODE (TREE_OPERAND (op
->op0
, 0)) == FUNCTION_DECL
1456 && fndecl_built_in_p (TREE_OPERAND (op
->op0
, 0))
1457 && operands
.length () >= 2
1458 && operands
.length () <= 3)
1460 vn_reference_op_t arg0
, arg1
= NULL
;
1461 bool anyconst
= false;
1462 arg0
= &operands
[1];
1463 if (operands
.length () > 2)
1464 arg1
= &operands
[2];
1465 if (TREE_CODE_CLASS (arg0
->opcode
) == tcc_constant
1466 || (arg0
->opcode
== ADDR_EXPR
1467 && is_gimple_min_invariant (arg0
->op0
)))
1470 && (TREE_CODE_CLASS (arg1
->opcode
) == tcc_constant
1471 || (arg1
->opcode
== ADDR_EXPR
1472 && is_gimple_min_invariant (arg1
->op0
))))
1476 tree folded
= build_call_expr (TREE_OPERAND (op
->op0
, 0),
1479 arg1
? arg1
->op0
: NULL
);
1481 && TREE_CODE (folded
) == NOP_EXPR
)
1482 folded
= TREE_OPERAND (folded
, 0);
1484 && is_gimple_min_invariant (folded
))
1489 /* Simplify reads from constants or constant initializers. */
1490 else if (BITS_PER_UNIT
== 8
1492 && COMPLETE_TYPE_P (ref
->type
)
1493 && is_gimple_reg_type (ref
->type
))
1497 if (INTEGRAL_TYPE_P (ref
->type
))
1498 size
= TYPE_PRECISION (ref
->type
);
1499 else if (tree_fits_shwi_p (TYPE_SIZE (ref
->type
)))
1500 size
= tree_to_shwi (TYPE_SIZE (ref
->type
));
1503 if (size
% BITS_PER_UNIT
!= 0
1504 || size
> MAX_BITSIZE_MODE_ANY_MODE
)
1506 size
/= BITS_PER_UNIT
;
1508 for (i
= 0; i
< operands
.length (); ++i
)
1510 if (TREE_CODE_CLASS (operands
[i
].opcode
) == tcc_constant
)
1515 if (known_eq (operands
[i
].off
, -1))
1517 off
+= operands
[i
].off
;
1518 if (operands
[i
].opcode
== MEM_REF
)
1524 vn_reference_op_t base
= &operands
[--i
];
1525 tree ctor
= error_mark_node
;
1526 tree decl
= NULL_TREE
;
1527 if (TREE_CODE_CLASS (base
->opcode
) == tcc_constant
)
1529 else if (base
->opcode
== MEM_REF
1530 && base
[1].opcode
== ADDR_EXPR
1531 && (TREE_CODE (TREE_OPERAND (base
[1].op0
, 0)) == VAR_DECL
1532 || TREE_CODE (TREE_OPERAND (base
[1].op0
, 0)) == CONST_DECL
1533 || TREE_CODE (TREE_OPERAND (base
[1].op0
, 0)) == STRING_CST
))
1535 decl
= TREE_OPERAND (base
[1].op0
, 0);
1536 if (TREE_CODE (decl
) == STRING_CST
)
1539 ctor
= ctor_for_folding (decl
);
1541 if (ctor
== NULL_TREE
)
1542 return build_zero_cst (ref
->type
);
1543 else if (ctor
!= error_mark_node
)
1545 HOST_WIDE_INT const_off
;
1548 tree res
= fold_ctor_reference (ref
->type
, ctor
,
1549 off
* BITS_PER_UNIT
,
1550 size
* BITS_PER_UNIT
, decl
);
1553 STRIP_USELESS_TYPE_CONVERSION (res
);
1554 if (is_gimple_min_invariant (res
))
1558 else if (off
.is_constant (&const_off
))
1560 unsigned char buf
[MAX_BITSIZE_MODE_ANY_MODE
/ BITS_PER_UNIT
];
1561 int len
= native_encode_expr (ctor
, buf
, size
, const_off
);
1563 return native_interpret_expr (ref
->type
, buf
, len
);
1571 /* Return true if OPS contain a storage order barrier. */
1574 contains_storage_order_barrier_p (vec
<vn_reference_op_s
> ops
)
1576 vn_reference_op_t op
;
1579 FOR_EACH_VEC_ELT (ops
, i
, op
)
1580 if (op
->opcode
== VIEW_CONVERT_EXPR
&& op
->reverse
)
1586 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1587 structures into their value numbers. This is done in-place, and
1588 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1589 whether any operands were valueized. */
1592 valueize_refs_1 (vec
<vn_reference_op_s
> *orig
, bool *valueized_anything
,
1593 bool with_avail
= false)
1595 vn_reference_op_t vro
;
1598 *valueized_anything
= false;
1600 FOR_EACH_VEC_ELT (*orig
, i
, vro
)
1602 if (vro
->opcode
== SSA_NAME
1603 || (vro
->op0
&& TREE_CODE (vro
->op0
) == SSA_NAME
))
1605 tree tem
= with_avail
? vn_valueize (vro
->op0
) : SSA_VAL (vro
->op0
);
1606 if (tem
!= vro
->op0
)
1608 *valueized_anything
= true;
1611 /* If it transforms from an SSA_NAME to a constant, update
1613 if (TREE_CODE (vro
->op0
) != SSA_NAME
&& vro
->opcode
== SSA_NAME
)
1614 vro
->opcode
= TREE_CODE (vro
->op0
);
1616 if (vro
->op1
&& TREE_CODE (vro
->op1
) == SSA_NAME
)
1618 tree tem
= with_avail
? vn_valueize (vro
->op1
) : SSA_VAL (vro
->op1
);
1619 if (tem
!= vro
->op1
)
1621 *valueized_anything
= true;
1625 if (vro
->op2
&& TREE_CODE (vro
->op2
) == SSA_NAME
)
1627 tree tem
= with_avail
? vn_valueize (vro
->op2
) : SSA_VAL (vro
->op2
);
1628 if (tem
!= vro
->op2
)
1630 *valueized_anything
= true;
1634 /* If it transforms from an SSA_NAME to an address, fold with
1635 a preceding indirect reference. */
1638 && TREE_CODE (vro
->op0
) == ADDR_EXPR
1639 && (*orig
)[i
- 1].opcode
== MEM_REF
)
1641 if (vn_reference_fold_indirect (orig
, &i
))
1642 *valueized_anything
= true;
1645 && vro
->opcode
== SSA_NAME
1646 && (*orig
)[i
- 1].opcode
== MEM_REF
)
1648 if (vn_reference_maybe_forwprop_address (orig
, &i
))
1649 *valueized_anything
= true;
1651 /* If it transforms a non-constant ARRAY_REF into a constant
1652 one, adjust the constant offset. */
1653 else if (vro
->opcode
== ARRAY_REF
1654 && known_eq (vro
->off
, -1)
1655 && poly_int_tree_p (vro
->op0
)
1656 && poly_int_tree_p (vro
->op1
)
1657 && TREE_CODE (vro
->op2
) == INTEGER_CST
)
1659 poly_offset_int off
= ((wi::to_poly_offset (vro
->op0
)
1660 - wi::to_poly_offset (vro
->op1
))
1661 * wi::to_offset (vro
->op2
)
1662 * vn_ref_op_align_unit (vro
));
1663 off
.to_shwi (&vro
->off
);
1669 valueize_refs (vec
<vn_reference_op_s
> *orig
)
1672 valueize_refs_1 (orig
, &tem
);
1675 static vec
<vn_reference_op_s
> shared_lookup_references
;
1677 /* Create a vector of vn_reference_op_s structures from REF, a
1678 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1679 this function. *VALUEIZED_ANYTHING will specify whether any
1680 operands were valueized. */
1682 static vec
<vn_reference_op_s
>
1683 valueize_shared_reference_ops_from_ref (tree ref
, bool *valueized_anything
)
1687 shared_lookup_references
.truncate (0);
1688 copy_reference_ops_from_ref (ref
, &shared_lookup_references
);
1689 valueize_refs_1 (&shared_lookup_references
, valueized_anything
);
1690 return shared_lookup_references
;
1693 /* Create a vector of vn_reference_op_s structures from CALL, a
1694 call statement. The vector is shared among all callers of
1697 static vec
<vn_reference_op_s
>
1698 valueize_shared_reference_ops_from_call (gcall
*call
)
1702 shared_lookup_references
.truncate (0);
1703 copy_reference_ops_from_call (call
, &shared_lookup_references
);
1704 valueize_refs (&shared_lookup_references
);
1705 return shared_lookup_references
;
1708 /* Lookup a SCCVN reference operation VR in the current hash table.
1709 Returns the resulting value number if it exists in the hash table,
1710 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1711 vn_reference_t stored in the hashtable if something is found. */
1714 vn_reference_lookup_1 (vn_reference_t vr
, vn_reference_t
*vnresult
)
1716 vn_reference_s
**slot
;
1719 hash
= vr
->hashcode
;
1720 slot
= valid_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1724 *vnresult
= (vn_reference_t
)*slot
;
1725 return ((vn_reference_t
)*slot
)->result
;
1732 /* Partial definition tracking support. */
1736 HOST_WIDE_INT offset
;
1743 HOST_WIDE_INT offset
;
1747 /* Context for alias walking. */
1749 struct vn_walk_cb_data
1751 vn_walk_cb_data (vn_reference_t vr_
, tree orig_ref_
, tree
*last_vuse_ptr_
,
1752 vn_lookup_kind vn_walk_kind_
, bool tbaa_p_
, tree mask_
)
1753 : vr (vr_
), last_vuse_ptr (last_vuse_ptr_
), last_vuse (NULL_TREE
),
1754 mask (mask_
), masked_result (NULL_TREE
), vn_walk_kind (vn_walk_kind_
),
1755 tbaa_p (tbaa_p_
), saved_operands (vNULL
), first_set (-2),
1756 first_base_set (-2), known_ranges (NULL
)
1759 last_vuse_ptr
= &last_vuse
;
1760 ao_ref_init (&orig_ref
, orig_ref_
);
1763 wide_int w
= wi::to_wide (mask
);
1764 unsigned int pos
= 0, prec
= w
.get_precision ();
1766 pd
.rhs
= build_constructor (NULL_TREE
, NULL
);
1767 /* When bitwise and with a constant is done on a memory load,
1768 we don't really need all the bits to be defined or defined
1769 to constants, we don't really care what is in the position
1770 corresponding to 0 bits in the mask.
1771 So, push the ranges of those 0 bits in the mask as artificial
1772 zero stores and let the partial def handling code do the
1776 int tz
= wi::ctz (w
);
1777 if (pos
+ tz
> prec
)
1781 if (BYTES_BIG_ENDIAN
)
1782 pd
.offset
= prec
- pos
- tz
;
1786 void *r
= push_partial_def (pd
, 0, 0, 0, prec
);
1787 gcc_assert (r
== NULL_TREE
);
1792 w
= wi::lrshift (w
, tz
);
1793 tz
= wi::ctz (wi::bit_not (w
));
1794 if (pos
+ tz
> prec
)
1797 w
= wi::lrshift (w
, tz
);
1801 ~vn_walk_cb_data ();
1802 void *finish (alias_set_type
, alias_set_type
, tree
);
1803 void *push_partial_def (pd_data pd
,
1804 alias_set_type
, alias_set_type
, HOST_WIDE_INT
,
1809 tree
*last_vuse_ptr
;
1813 vn_lookup_kind vn_walk_kind
;
1815 vec
<vn_reference_op_s
> saved_operands
;
1817 /* The VDEFs of partial defs we come along. */
1818 auto_vec
<pd_data
, 2> partial_defs
;
1819 /* The first defs range to avoid splay tree setup in most cases. */
1820 pd_range first_range
;
1821 alias_set_type first_set
;
1822 alias_set_type first_base_set
;
1823 splay_tree known_ranges
;
1824 obstack ranges_obstack
;
1827 vn_walk_cb_data::~vn_walk_cb_data ()
1831 splay_tree_delete (known_ranges
);
1832 obstack_free (&ranges_obstack
, NULL
);
1834 saved_operands
.release ();
1838 vn_walk_cb_data::finish (alias_set_type set
, alias_set_type base_set
, tree val
)
1840 if (first_set
!= -2)
1843 base_set
= first_base_set
;
1847 masked_result
= val
;
1850 vec
<vn_reference_op_s
> &operands
1851 = saved_operands
.exists () ? saved_operands
: vr
->operands
;
1852 return vn_reference_lookup_or_insert_for_pieces (last_vuse
, set
, base_set
,
1853 vr
->type
, operands
, val
);
1856 /* pd_range splay-tree helpers. */
1859 pd_range_compare (splay_tree_key offset1p
, splay_tree_key offset2p
)
1861 HOST_WIDE_INT offset1
= *(HOST_WIDE_INT
*)offset1p
;
1862 HOST_WIDE_INT offset2
= *(HOST_WIDE_INT
*)offset2p
;
1863 if (offset1
< offset2
)
1865 else if (offset1
> offset2
)
1871 pd_tree_alloc (int size
, void *data_
)
1873 vn_walk_cb_data
*data
= (vn_walk_cb_data
*)data_
;
1874 return obstack_alloc (&data
->ranges_obstack
, size
);
1878 pd_tree_dealloc (void *, void *)
1882 /* Push PD to the vector of partial definitions returning a
1883 value when we are ready to combine things with VUSE, SET and MAXSIZEI,
1884 NULL when we want to continue looking for partial defs or -1
1888 vn_walk_cb_data::push_partial_def (pd_data pd
,
1889 alias_set_type set
, alias_set_type base_set
,
1890 HOST_WIDE_INT offseti
,
1891 HOST_WIDE_INT maxsizei
)
1893 const HOST_WIDE_INT bufsize
= 64;
1894 /* We're using a fixed buffer for encoding so fail early if the object
1895 we want to interpret is bigger. */
1896 if (maxsizei
> bufsize
* BITS_PER_UNIT
1898 || BITS_PER_UNIT
!= 8
1899 /* Not prepared to handle PDP endian. */
1900 || BYTES_BIG_ENDIAN
!= WORDS_BIG_ENDIAN
)
1903 /* Turn too large constant stores into non-constant stores. */
1904 if (CONSTANT_CLASS_P (pd
.rhs
) && pd
.size
> bufsize
* BITS_PER_UNIT
)
1905 pd
.rhs
= error_mark_node
;
1907 /* And for non-constant or CONSTRUCTOR stores shrink them to only keep at
1908 most a partial byte before and/or after the region. */
1909 if (!CONSTANT_CLASS_P (pd
.rhs
))
1911 if (pd
.offset
< offseti
)
1913 HOST_WIDE_INT o
= ROUND_DOWN (offseti
- pd
.offset
, BITS_PER_UNIT
);
1914 gcc_assert (pd
.size
> o
);
1918 if (pd
.size
> maxsizei
)
1919 pd
.size
= maxsizei
+ ((pd
.size
- maxsizei
) % BITS_PER_UNIT
);
1922 pd
.offset
-= offseti
;
1924 bool pd_constant_p
= (TREE_CODE (pd
.rhs
) == CONSTRUCTOR
1925 || CONSTANT_CLASS_P (pd
.rhs
));
1926 if (partial_defs
.is_empty ())
1928 /* If we get a clobber upfront, fail. */
1929 if (TREE_CLOBBER_P (pd
.rhs
))
1933 partial_defs
.safe_push (pd
);
1934 first_range
.offset
= pd
.offset
;
1935 first_range
.size
= pd
.size
;
1937 first_base_set
= base_set
;
1938 last_vuse_ptr
= NULL
;
1939 /* Continue looking for partial defs. */
1945 /* ??? Optimize the case where the 2nd partial def completes things. */
1946 gcc_obstack_init (&ranges_obstack
);
1947 known_ranges
= splay_tree_new_with_allocator (pd_range_compare
, 0, 0,
1949 pd_tree_dealloc
, this);
1950 splay_tree_insert (known_ranges
,
1951 (splay_tree_key
)&first_range
.offset
,
1952 (splay_tree_value
)&first_range
);
1955 pd_range newr
= { pd
.offset
, pd
.size
};
1958 /* Lookup the predecessor of offset + 1 and see if we need to merge. */
1959 HOST_WIDE_INT loffset
= newr
.offset
+ 1;
1960 if ((n
= splay_tree_predecessor (known_ranges
, (splay_tree_key
)&loffset
))
1961 && ((r
= (pd_range
*)n
->value
), true)
1962 && ranges_known_overlap_p (r
->offset
, r
->size
+ 1,
1963 newr
.offset
, newr
.size
))
1965 /* Ignore partial defs already covered. Here we also drop shadowed
1966 clobbers arriving here at the floor. */
1967 if (known_subrange_p (newr
.offset
, newr
.size
, r
->offset
, r
->size
))
1969 r
->size
= MAX (r
->offset
+ r
->size
, newr
.offset
+ newr
.size
) - r
->offset
;
1973 /* newr.offset wasn't covered yet, insert the range. */
1974 r
= XOBNEW (&ranges_obstack
, pd_range
);
1976 splay_tree_insert (known_ranges
, (splay_tree_key
)&r
->offset
,
1977 (splay_tree_value
)r
);
1979 /* Merge r which now contains newr and is a member of the splay tree with
1980 adjacent overlapping ranges. */
1982 while ((n
= splay_tree_successor (known_ranges
, (splay_tree_key
)&r
->offset
))
1983 && ((rafter
= (pd_range
*)n
->value
), true)
1984 && ranges_known_overlap_p (r
->offset
, r
->size
+ 1,
1985 rafter
->offset
, rafter
->size
))
1987 r
->size
= MAX (r
->offset
+ r
->size
,
1988 rafter
->offset
+ rafter
->size
) - r
->offset
;
1989 splay_tree_remove (known_ranges
, (splay_tree_key
)&rafter
->offset
);
1991 /* If we get a clobber, fail. */
1992 if (TREE_CLOBBER_P (pd
.rhs
))
1994 /* Non-constants are OK as long as they are shadowed by a constant. */
1997 partial_defs
.safe_push (pd
);
1999 /* Now we have merged newr into the range tree. When we have covered
2000 [offseti, sizei] then the tree will contain exactly one node which has
2001 the desired properties and it will be 'r'. */
2002 if (!known_subrange_p (0, maxsizei
, r
->offset
, r
->size
))
2003 /* Continue looking for partial defs. */
2006 /* Now simply native encode all partial defs in reverse order. */
2007 unsigned ndefs
= partial_defs
.length ();
2008 /* We support up to 512-bit values (for V8DFmode). */
2009 unsigned char buffer
[bufsize
+ 1];
2010 unsigned char this_buffer
[bufsize
+ 1];
2013 memset (buffer
, 0, bufsize
+ 1);
2014 unsigned needed_len
= ROUND_UP (maxsizei
, BITS_PER_UNIT
) / BITS_PER_UNIT
;
2015 while (!partial_defs
.is_empty ())
2017 pd_data pd
= partial_defs
.pop ();
2019 if (TREE_CODE (pd
.rhs
) == CONSTRUCTOR
)
2021 /* Empty CONSTRUCTOR. */
2022 if (pd
.size
>= needed_len
* BITS_PER_UNIT
)
2025 len
= ROUND_UP (pd
.size
, BITS_PER_UNIT
) / BITS_PER_UNIT
;
2026 memset (this_buffer
, 0, len
);
2030 len
= native_encode_expr (pd
.rhs
, this_buffer
, bufsize
,
2031 MAX (0, -pd
.offset
) / BITS_PER_UNIT
);
2033 || len
< (ROUND_UP (pd
.size
, BITS_PER_UNIT
) / BITS_PER_UNIT
2034 - MAX (0, -pd
.offset
) / BITS_PER_UNIT
))
2036 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2037 fprintf (dump_file
, "Failed to encode %u "
2038 "partial definitions\n", ndefs
);
2043 unsigned char *p
= buffer
;
2044 HOST_WIDE_INT size
= pd
.size
;
2046 size
-= ROUND_DOWN (-pd
.offset
, BITS_PER_UNIT
);
2047 this_buffer
[len
] = 0;
2048 if (BYTES_BIG_ENDIAN
)
2050 /* LSB of this_buffer[len - 1] byte should be at
2051 pd.offset + pd.size - 1 bits in buffer. */
2052 amnt
= ((unsigned HOST_WIDE_INT
) pd
.offset
2053 + pd
.size
) % BITS_PER_UNIT
;
2055 shift_bytes_in_array_right (this_buffer
, len
+ 1, amnt
);
2056 unsigned char *q
= this_buffer
;
2057 unsigned int off
= 0;
2061 off
= pd
.offset
/ BITS_PER_UNIT
;
2062 gcc_assert (off
< needed_len
);
2066 msk
= ((1 << size
) - 1) << (BITS_PER_UNIT
- amnt
);
2067 *p
= (*p
& ~msk
) | (this_buffer
[len
] & msk
);
2072 if (TREE_CODE (pd
.rhs
) != CONSTRUCTOR
)
2073 q
= (this_buffer
+ len
2074 - (ROUND_UP (size
- amnt
, BITS_PER_UNIT
)
2076 if (pd
.offset
% BITS_PER_UNIT
)
2078 msk
= -1U << (BITS_PER_UNIT
2079 - (pd
.offset
% BITS_PER_UNIT
));
2080 *p
= (*p
& msk
) | (*q
& ~msk
);
2084 size
-= BITS_PER_UNIT
- (pd
.offset
% BITS_PER_UNIT
);
2085 gcc_assert (size
>= 0);
2089 else if (TREE_CODE (pd
.rhs
) != CONSTRUCTOR
)
2091 q
= (this_buffer
+ len
2092 - (ROUND_UP (size
- amnt
, BITS_PER_UNIT
)
2094 if (pd
.offset
% BITS_PER_UNIT
)
2097 size
-= BITS_PER_UNIT
- ((unsigned HOST_WIDE_INT
) pd
.offset
2099 gcc_assert (size
>= 0);
2102 if ((unsigned HOST_WIDE_INT
) size
/ BITS_PER_UNIT
+ off
2104 size
= (needed_len
- off
) * BITS_PER_UNIT
;
2105 memcpy (p
, q
, size
/ BITS_PER_UNIT
);
2106 if (size
% BITS_PER_UNIT
)
2109 = -1U << (BITS_PER_UNIT
- (size
% BITS_PER_UNIT
));
2110 p
+= size
/ BITS_PER_UNIT
;
2111 q
+= size
/ BITS_PER_UNIT
;
2112 *p
= (*q
& msk
) | (*p
& ~msk
);
2119 /* LSB of this_buffer[0] byte should be at pd.offset bits
2122 size
= MIN (size
, (HOST_WIDE_INT
) needed_len
* BITS_PER_UNIT
);
2123 amnt
= pd
.offset
% BITS_PER_UNIT
;
2125 shift_bytes_in_array_left (this_buffer
, len
+ 1, amnt
);
2126 unsigned int off
= pd
.offset
/ BITS_PER_UNIT
;
2127 gcc_assert (off
< needed_len
);
2129 (HOST_WIDE_INT
) (needed_len
- off
) * BITS_PER_UNIT
);
2131 if (amnt
+ size
< BITS_PER_UNIT
)
2133 /* Low amnt bits come from *p, then size bits
2134 from this_buffer[0] and the remaining again from
2136 msk
= ((1 << size
) - 1) << amnt
;
2137 *p
= (*p
& ~msk
) | (this_buffer
[0] & msk
);
2143 *p
= (*p
& ~msk
) | (this_buffer
[0] & msk
);
2145 size
-= (BITS_PER_UNIT
- amnt
);
2150 amnt
= (unsigned HOST_WIDE_INT
) pd
.offset
% BITS_PER_UNIT
;
2152 size
-= BITS_PER_UNIT
- amnt
;
2153 size
= MIN (size
, (HOST_WIDE_INT
) needed_len
* BITS_PER_UNIT
);
2155 shift_bytes_in_array_left (this_buffer
, len
+ 1, amnt
);
2157 memcpy (p
, this_buffer
+ (amnt
!= 0), size
/ BITS_PER_UNIT
);
2158 p
+= size
/ BITS_PER_UNIT
;
2159 if (size
% BITS_PER_UNIT
)
2161 unsigned int msk
= -1U << (size
% BITS_PER_UNIT
);
2162 *p
= (this_buffer
[(amnt
!= 0) + size
/ BITS_PER_UNIT
]
2163 & ~msk
) | (*p
& msk
);
2168 tree type
= vr
->type
;
2169 /* Make sure to interpret in a type that has a range covering the whole
2171 if (INTEGRAL_TYPE_P (vr
->type
) && maxsizei
!= TYPE_PRECISION (vr
->type
))
2172 type
= build_nonstandard_integer_type (maxsizei
, TYPE_UNSIGNED (type
));
2174 if (BYTES_BIG_ENDIAN
)
2176 unsigned sz
= needed_len
;
2177 if (maxsizei
% BITS_PER_UNIT
)
2178 shift_bytes_in_array_right (buffer
, needed_len
,
2180 - (maxsizei
% BITS_PER_UNIT
));
2181 if (INTEGRAL_TYPE_P (type
))
2182 sz
= GET_MODE_SIZE (SCALAR_INT_TYPE_MODE (type
));
2183 if (sz
> needed_len
)
2185 memcpy (this_buffer
+ (sz
- needed_len
), buffer
, needed_len
);
2186 val
= native_interpret_expr (type
, this_buffer
, sz
);
2189 val
= native_interpret_expr (type
, buffer
, needed_len
);
2192 val
= native_interpret_expr (type
, buffer
, bufsize
);
2193 /* If we chop off bits because the types precision doesn't match the memory
2194 access size this is ok when optimizing reads but not when called from
2195 the DSE code during elimination. */
2196 if (val
&& type
!= vr
->type
)
2198 if (! int_fits_type_p (val
, vr
->type
))
2201 val
= fold_convert (vr
->type
, val
);
2206 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2208 "Successfully combined %u partial definitions\n", ndefs
);
2209 /* We are using the alias-set of the first store we encounter which
2210 should be appropriate here. */
2211 return finish (first_set
, first_base_set
, val
);
2215 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2217 "Failed to interpret %u encoded partial definitions\n", ndefs
);
2222 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
2223 with the current VUSE and performs the expression lookup. */
2226 vn_reference_lookup_2 (ao_ref
*op ATTRIBUTE_UNUSED
, tree vuse
, void *data_
)
2228 vn_walk_cb_data
*data
= (vn_walk_cb_data
*)data_
;
2229 vn_reference_t vr
= data
->vr
;
2230 vn_reference_s
**slot
;
2233 /* If we have partial definitions recorded we have to go through
2234 vn_reference_lookup_3. */
2235 if (!data
->partial_defs
.is_empty ())
2238 if (data
->last_vuse_ptr
)
2240 *data
->last_vuse_ptr
= vuse
;
2241 data
->last_vuse
= vuse
;
2244 /* Fixup vuse and hash. */
2246 vr
->hashcode
= vr
->hashcode
- SSA_NAME_VERSION (vr
->vuse
);
2247 vr
->vuse
= vuse_ssa_val (vuse
);
2249 vr
->hashcode
= vr
->hashcode
+ SSA_NAME_VERSION (vr
->vuse
);
2251 hash
= vr
->hashcode
;
2252 slot
= valid_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
2255 if ((*slot
)->result
&& data
->saved_operands
.exists ())
2256 return data
->finish (vr
->set
, vr
->base_set
, (*slot
)->result
);
2263 /* Lookup an existing or insert a new vn_reference entry into the
2264 value table for the VUSE, SET, TYPE, OPERANDS reference which
2265 has the value VALUE which is either a constant or an SSA name. */
2267 static vn_reference_t
2268 vn_reference_lookup_or_insert_for_pieces (tree vuse
,
2270 alias_set_type base_set
,
2272 vec
<vn_reference_op_s
,
2277 vn_reference_t result
;
2279 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2280 vr1
.operands
= operands
;
2283 vr1
.base_set
= base_set
;
2284 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2285 if (vn_reference_lookup_1 (&vr1
, &result
))
2287 if (TREE_CODE (value
) == SSA_NAME
)
2288 value_id
= VN_INFO (value
)->value_id
;
2290 value_id
= get_or_alloc_constant_value_id (value
);
2291 return vn_reference_insert_pieces (vuse
, set
, base_set
, type
,
2292 operands
.copy (), value
, value_id
);
2295 /* Return a value-number for RCODE OPS... either by looking up an existing
2296 value-number for the simplified result or by inserting the operation if
2300 vn_nary_build_or_lookup_1 (gimple_match_op
*res_op
, bool insert
)
2302 tree result
= NULL_TREE
;
2303 /* We will be creating a value number for
2305 So first simplify and lookup this expression to see if it
2306 is already available. */
2307 /* For simplification valueize. */
2309 for (i
= 0; i
< res_op
->num_ops
; ++i
)
2310 if (TREE_CODE (res_op
->ops
[i
]) == SSA_NAME
)
2312 tree tem
= vn_valueize (res_op
->ops
[i
]);
2315 res_op
->ops
[i
] = tem
;
2317 /* If valueization of an operand fails (it is not available), skip
2320 if (i
== res_op
->num_ops
)
2322 mprts_hook
= vn_lookup_simplify_result
;
2323 res
= res_op
->resimplify (NULL
, vn_valueize
);
2326 gimple
*new_stmt
= NULL
;
2328 && gimple_simplified_result_is_gimple_val (res_op
))
2330 /* The expression is already available. */
2331 result
= res_op
->ops
[0];
2332 /* Valueize it, simplification returns sth in AVAIL only. */
2333 if (TREE_CODE (result
) == SSA_NAME
)
2334 result
= SSA_VAL (result
);
2338 tree val
= vn_lookup_simplify_result (res_op
);
2341 gimple_seq stmts
= NULL
;
2342 result
= maybe_push_res_to_seq (res_op
, &stmts
);
2345 gcc_assert (gimple_seq_singleton_p (stmts
));
2346 new_stmt
= gimple_seq_first_stmt (stmts
);
2350 /* The expression is already available. */
2355 /* The expression is not yet available, value-number lhs to
2356 the new SSA_NAME we created. */
2357 /* Initialize value-number information properly. */
2358 vn_ssa_aux_t result_info
= VN_INFO (result
);
2359 result_info
->valnum
= result
;
2360 result_info
->value_id
= get_next_value_id ();
2361 result_info
->visited
= 1;
2362 gimple_seq_add_stmt_without_update (&VN_INFO (result
)->expr
,
2364 result_info
->needs_insertion
= true;
2365 /* ??? PRE phi-translation inserts NARYs without corresponding
2366 SSA name result. Re-use those but set their result according
2367 to the stmt we just built. */
2368 vn_nary_op_t nary
= NULL
;
2369 vn_nary_op_lookup_stmt (new_stmt
, &nary
);
2372 gcc_assert (! nary
->predicated_values
&& nary
->u
.result
== NULL_TREE
);
2373 nary
->u
.result
= gimple_assign_lhs (new_stmt
);
2375 /* As all "inserted" statements are singleton SCCs, insert
2376 to the valid table. This is strictly needed to
2377 avoid re-generating new value SSA_NAMEs for the same
2378 expression during SCC iteration over and over (the
2379 optimistic table gets cleared after each iteration).
2380 We do not need to insert into the optimistic table, as
2381 lookups there will fall back to the valid table. */
2384 unsigned int length
= vn_nary_length_from_stmt (new_stmt
);
2386 = alloc_vn_nary_op_noinit (length
, &vn_tables_insert_obstack
);
2387 vno1
->value_id
= result_info
->value_id
;
2388 vno1
->length
= length
;
2389 vno1
->predicated_values
= 0;
2390 vno1
->u
.result
= result
;
2391 init_vn_nary_op_from_stmt (vno1
, as_a
<gassign
*> (new_stmt
));
2392 vn_nary_op_insert_into (vno1
, valid_info
->nary
, true);
2393 /* Also do not link it into the undo chain. */
2394 last_inserted_nary
= vno1
->next
;
2395 vno1
->next
= (vn_nary_op_t
)(void *)-1;
2397 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2399 fprintf (dump_file
, "Inserting name ");
2400 print_generic_expr (dump_file
, result
);
2401 fprintf (dump_file
, " for expression ");
2402 print_gimple_expr (dump_file
, new_stmt
, 0, TDF_SLIM
);
2403 fprintf (dump_file
, "\n");
2409 /* Return a value-number for RCODE OPS... either by looking up an existing
2410 value-number for the simplified result or by inserting the operation. */
2413 vn_nary_build_or_lookup (gimple_match_op
*res_op
)
2415 return vn_nary_build_or_lookup_1 (res_op
, true);
2418 /* Try to simplify the expression RCODE OPS... of type TYPE and return
2419 its value if present. */
2422 vn_nary_simplify (vn_nary_op_t nary
)
2424 if (nary
->length
> gimple_match_op::MAX_NUM_OPS
)
2426 gimple_match_op
op (gimple_match_cond::UNCOND
, nary
->opcode
,
2427 nary
->type
, nary
->length
);
2428 memcpy (op
.ops
, nary
->op
, sizeof (tree
) * nary
->length
);
2429 return vn_nary_build_or_lookup_1 (&op
, false);
2432 /* Elimination engine. */
2434 class eliminate_dom_walker
: public dom_walker
2437 eliminate_dom_walker (cdi_direction
, bitmap
);
2438 ~eliminate_dom_walker ();
2440 virtual edge
before_dom_children (basic_block
);
2441 virtual void after_dom_children (basic_block
);
2443 virtual tree
eliminate_avail (basic_block
, tree op
);
2444 virtual void eliminate_push_avail (basic_block
, tree op
);
2445 tree
eliminate_insert (basic_block
, gimple_stmt_iterator
*gsi
, tree val
);
2447 void eliminate_stmt (basic_block
, gimple_stmt_iterator
*);
2449 unsigned eliminate_cleanup (bool region_p
= false);
2452 unsigned int el_todo
;
2453 unsigned int eliminations
;
2454 unsigned int insertions
;
2456 /* SSA names that had their defs inserted by PRE if do_pre. */
2457 bitmap inserted_exprs
;
2459 /* Blocks with statements that have had their EH properties changed. */
2460 bitmap need_eh_cleanup
;
2462 /* Blocks with statements that have had their AB properties changed. */
2463 bitmap need_ab_cleanup
;
2465 /* Local state for the eliminate domwalk. */
2466 auto_vec
<gimple
*> to_remove
;
2467 auto_vec
<gimple
*> to_fixup
;
2468 auto_vec
<tree
> avail
;
2469 auto_vec
<tree
> avail_stack
;
2472 /* Adaptor to the elimination engine using RPO availability. */
2474 class rpo_elim
: public eliminate_dom_walker
2477 rpo_elim(basic_block entry_
)
2478 : eliminate_dom_walker (CDI_DOMINATORS
, NULL
), entry (entry_
),
2479 m_avail_freelist (NULL
) {}
2481 virtual tree
eliminate_avail (basic_block
, tree op
);
2483 virtual void eliminate_push_avail (basic_block
, tree
);
2486 /* Freelist of avail entries which are allocated from the vn_ssa_aux
2488 vn_avail
*m_avail_freelist
;
2491 /* Global RPO state for access from hooks. */
2492 static eliminate_dom_walker
*rpo_avail
;
2493 basic_block vn_context_bb
;
2495 /* Return true if BASE1 and BASE2 can be adjusted so they have the
2496 same address and adjust *OFFSET1 and *OFFSET2 accordingly.
2497 Otherwise return false. */
2500 adjust_offsets_for_equal_base_address (tree base1
, poly_int64
*offset1
,
2501 tree base2
, poly_int64
*offset2
)
2504 if (TREE_CODE (base1
) == MEM_REF
2505 && TREE_CODE (base2
) == MEM_REF
)
2507 if (mem_ref_offset (base1
).to_shwi (&soff
))
2509 base1
= TREE_OPERAND (base1
, 0);
2510 *offset1
+= soff
* BITS_PER_UNIT
;
2512 if (mem_ref_offset (base2
).to_shwi (&soff
))
2514 base2
= TREE_OPERAND (base2
, 0);
2515 *offset2
+= soff
* BITS_PER_UNIT
;
2517 return operand_equal_p (base1
, base2
, 0);
2519 return operand_equal_p (base1
, base2
, OEP_ADDRESS_OF
);
2522 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
2523 from the statement defining VUSE and if not successful tries to
2524 translate *REFP and VR_ through an aggregate copy at the definition
2525 of VUSE. If *DISAMBIGUATE_ONLY is true then do not perform translation
2526 of *REF and *VR. If only disambiguation was performed then
2527 *DISAMBIGUATE_ONLY is set to true. */
2530 vn_reference_lookup_3 (ao_ref
*ref
, tree vuse
, void *data_
,
2531 translate_flags
*disambiguate_only
)
2533 vn_walk_cb_data
*data
= (vn_walk_cb_data
*)data_
;
2534 vn_reference_t vr
= data
->vr
;
2535 gimple
*def_stmt
= SSA_NAME_DEF_STMT (vuse
);
2536 tree base
= ao_ref_base (ref
);
2537 HOST_WIDE_INT offseti
= 0, maxsizei
, sizei
= 0;
2538 static vec
<vn_reference_op_s
> lhs_ops
;
2540 bool lhs_ref_ok
= false;
2541 poly_int64 copy_size
;
2543 /* First try to disambiguate after value-replacing in the definitions LHS. */
2544 if (is_gimple_assign (def_stmt
))
2546 tree lhs
= gimple_assign_lhs (def_stmt
);
2547 bool valueized_anything
= false;
2548 /* Avoid re-allocation overhead. */
2549 lhs_ops
.truncate (0);
2550 basic_block saved_rpo_bb
= vn_context_bb
;
2551 vn_context_bb
= gimple_bb (def_stmt
);
2552 if (*disambiguate_only
<= TR_VALUEIZE_AND_DISAMBIGUATE
)
2554 copy_reference_ops_from_ref (lhs
, &lhs_ops
);
2555 valueize_refs_1 (&lhs_ops
, &valueized_anything
, true);
2557 vn_context_bb
= saved_rpo_bb
;
2558 ao_ref_init (&lhs_ref
, lhs
);
2560 if (valueized_anything
2561 && ao_ref_init_from_vn_reference
2562 (&lhs_ref
, ao_ref_alias_set (&lhs_ref
),
2563 ao_ref_base_alias_set (&lhs_ref
), TREE_TYPE (lhs
), lhs_ops
)
2564 && !refs_may_alias_p_1 (ref
, &lhs_ref
, data
->tbaa_p
))
2566 *disambiguate_only
= TR_VALUEIZE_AND_DISAMBIGUATE
;
2570 /* Besides valueizing the LHS we can also use access-path based
2571 disambiguation on the original non-valueized ref. */
2574 && data
->orig_ref
.ref
)
2576 /* We want to use the non-valueized LHS for this, but avoid redundant
2578 ao_ref
*lref
= &lhs_ref
;
2580 if (valueized_anything
)
2582 ao_ref_init (&lref_alt
, lhs
);
2585 if (!refs_may_alias_p_1 (&data
->orig_ref
, lref
, data
->tbaa_p
))
2587 *disambiguate_only
= (valueized_anything
2588 ? TR_VALUEIZE_AND_DISAMBIGUATE
2594 /* If we reach a clobbering statement try to skip it and see if
2595 we find a VN result with exactly the same value as the
2596 possible clobber. In this case we can ignore the clobber
2597 and return the found value. */
2598 if (is_gimple_reg_type (TREE_TYPE (lhs
))
2599 && types_compatible_p (TREE_TYPE (lhs
), vr
->type
)
2600 && (ref
->ref
|| data
->orig_ref
.ref
))
2602 tree
*saved_last_vuse_ptr
= data
->last_vuse_ptr
;
2603 /* Do not update last_vuse_ptr in vn_reference_lookup_2. */
2604 data
->last_vuse_ptr
= NULL
;
2605 tree saved_vuse
= vr
->vuse
;
2606 hashval_t saved_hashcode
= vr
->hashcode
;
2607 void *res
= vn_reference_lookup_2 (ref
, gimple_vuse (def_stmt
), data
);
2608 /* Need to restore vr->vuse and vr->hashcode. */
2609 vr
->vuse
= saved_vuse
;
2610 vr
->hashcode
= saved_hashcode
;
2611 data
->last_vuse_ptr
= saved_last_vuse_ptr
;
2612 if (res
&& res
!= (void *)-1)
2614 vn_reference_t vnresult
= (vn_reference_t
) res
;
2615 tree rhs
= gimple_assign_rhs1 (def_stmt
);
2616 if (TREE_CODE (rhs
) == SSA_NAME
)
2617 rhs
= SSA_VAL (rhs
);
2618 if (vnresult
->result
2619 && operand_equal_p (vnresult
->result
, rhs
, 0)
2620 /* We have to honor our promise about union type punning
2621 and also support arbitrary overlaps with
2622 -fno-strict-aliasing. So simply resort to alignment to
2623 rule out overlaps. Do this check last because it is
2624 quite expensive compared to the hash-lookup above. */
2625 && multiple_p (get_object_alignment
2626 (ref
->ref
? ref
->ref
: data
->orig_ref
.ref
),
2628 && multiple_p (get_object_alignment (lhs
), ref
->size
))
2633 else if (*disambiguate_only
<= TR_VALUEIZE_AND_DISAMBIGUATE
2634 && gimple_call_builtin_p (def_stmt
, BUILT_IN_NORMAL
)
2635 && gimple_call_num_args (def_stmt
) <= 4)
2637 /* For builtin calls valueize its arguments and call the
2638 alias oracle again. Valueization may improve points-to
2639 info of pointers and constify size and position arguments.
2640 Originally this was motivated by PR61034 which has
2641 conditional calls to free falsely clobbering ref because
2642 of imprecise points-to info of the argument. */
2644 bool valueized_anything
= false;
2645 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
2647 oldargs
[i
] = gimple_call_arg (def_stmt
, i
);
2648 tree val
= vn_valueize (oldargs
[i
]);
2649 if (val
!= oldargs
[i
])
2651 gimple_call_set_arg (def_stmt
, i
, val
);
2652 valueized_anything
= true;
2655 if (valueized_anything
)
2657 bool res
= call_may_clobber_ref_p_1 (as_a
<gcall
*> (def_stmt
),
2659 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
2660 gimple_call_set_arg (def_stmt
, i
, oldargs
[i
]);
2663 *disambiguate_only
= TR_VALUEIZE_AND_DISAMBIGUATE
;
2669 if (*disambiguate_only
> TR_TRANSLATE
)
2672 /* If we cannot constrain the size of the reference we cannot
2673 test if anything kills it. */
2674 if (!ref
->max_size_known_p ())
2677 poly_int64 offset
= ref
->offset
;
2678 poly_int64 maxsize
= ref
->max_size
;
2680 /* def_stmt may-defs *ref. See if we can derive a value for *ref
2681 from that definition.
2683 if (is_gimple_reg_type (vr
->type
)
2684 && (gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMSET
)
2685 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMSET_CHK
))
2686 && (integer_zerop (gimple_call_arg (def_stmt
, 1))
2687 || ((TREE_CODE (gimple_call_arg (def_stmt
, 1)) == INTEGER_CST
2688 || (INTEGRAL_TYPE_P (vr
->type
) && known_eq (ref
->size
, 8)))
2690 && BITS_PER_UNIT
== 8
2691 && BYTES_BIG_ENDIAN
== WORDS_BIG_ENDIAN
2692 && offset
.is_constant (&offseti
)
2693 && ref
->size
.is_constant (&sizei
)
2694 && (offseti
% BITS_PER_UNIT
== 0
2695 || TREE_CODE (gimple_call_arg (def_stmt
, 1)) == INTEGER_CST
)))
2696 && (poly_int_tree_p (gimple_call_arg (def_stmt
, 2))
2697 || (TREE_CODE (gimple_call_arg (def_stmt
, 2)) == SSA_NAME
2698 && poly_int_tree_p (SSA_VAL (gimple_call_arg (def_stmt
, 2)))))
2699 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
2700 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
))
2703 poly_int64 offset2
, size2
, maxsize2
;
2705 tree ref2
= gimple_call_arg (def_stmt
, 0);
2706 if (TREE_CODE (ref2
) == SSA_NAME
)
2708 ref2
= SSA_VAL (ref2
);
2709 if (TREE_CODE (ref2
) == SSA_NAME
2710 && (TREE_CODE (base
) != MEM_REF
2711 || TREE_OPERAND (base
, 0) != ref2
))
2713 gimple
*def_stmt
= SSA_NAME_DEF_STMT (ref2
);
2714 if (gimple_assign_single_p (def_stmt
)
2715 && gimple_assign_rhs_code (def_stmt
) == ADDR_EXPR
)
2716 ref2
= gimple_assign_rhs1 (def_stmt
);
2719 if (TREE_CODE (ref2
) == ADDR_EXPR
)
2721 ref2
= TREE_OPERAND (ref2
, 0);
2722 base2
= get_ref_base_and_extent (ref2
, &offset2
, &size2
, &maxsize2
,
2724 if (!known_size_p (maxsize2
)
2725 || !known_eq (maxsize2
, size2
)
2726 || !operand_equal_p (base
, base2
, OEP_ADDRESS_OF
))
2729 else if (TREE_CODE (ref2
) == SSA_NAME
)
2732 if (TREE_CODE (base
) != MEM_REF
2733 || !(mem_ref_offset (base
)
2734 << LOG2_BITS_PER_UNIT
).to_shwi (&soff
))
2738 if (TREE_OPERAND (base
, 0) != ref2
)
2740 gimple
*def
= SSA_NAME_DEF_STMT (ref2
);
2741 if (is_gimple_assign (def
)
2742 && gimple_assign_rhs_code (def
) == POINTER_PLUS_EXPR
2743 && gimple_assign_rhs1 (def
) == TREE_OPERAND (base
, 0)
2744 && poly_int_tree_p (gimple_assign_rhs2 (def
)))
2746 tree rhs2
= gimple_assign_rhs2 (def
);
2747 if (!(poly_offset_int::from (wi::to_poly_wide (rhs2
),
2749 << LOG2_BITS_PER_UNIT
).to_shwi (&offset2
))
2751 ref2
= gimple_assign_rhs1 (def
);
2752 if (TREE_CODE (ref2
) == SSA_NAME
)
2753 ref2
= SSA_VAL (ref2
);
2761 tree len
= gimple_call_arg (def_stmt
, 2);
2762 HOST_WIDE_INT leni
, offset2i
;
2763 if (TREE_CODE (len
) == SSA_NAME
)
2764 len
= SSA_VAL (len
);
2765 /* Sometimes the above trickery is smarter than alias analysis. Take
2766 advantage of that. */
2767 if (!ranges_maybe_overlap_p (offset
, maxsize
, offset2
,
2768 (wi::to_poly_offset (len
)
2769 << LOG2_BITS_PER_UNIT
)))
2771 if (data
->partial_defs
.is_empty ()
2772 && known_subrange_p (offset
, maxsize
, offset2
,
2773 wi::to_poly_offset (len
) << LOG2_BITS_PER_UNIT
))
2776 if (integer_zerop (gimple_call_arg (def_stmt
, 1)))
2777 val
= build_zero_cst (vr
->type
);
2778 else if (INTEGRAL_TYPE_P (vr
->type
)
2779 && known_eq (ref
->size
, 8)
2780 && offseti
% BITS_PER_UNIT
== 0)
2782 gimple_match_op
res_op (gimple_match_cond::UNCOND
, NOP_EXPR
,
2783 vr
->type
, gimple_call_arg (def_stmt
, 1));
2784 val
= vn_nary_build_or_lookup (&res_op
);
2786 || (TREE_CODE (val
) == SSA_NAME
2787 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
)))
2792 unsigned buflen
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (vr
->type
)) + 1;
2793 if (INTEGRAL_TYPE_P (vr
->type
))
2794 buflen
= GET_MODE_SIZE (SCALAR_INT_TYPE_MODE (vr
->type
)) + 1;
2795 unsigned char *buf
= XALLOCAVEC (unsigned char, buflen
);
2796 memset (buf
, TREE_INT_CST_LOW (gimple_call_arg (def_stmt
, 1)),
2798 if (BYTES_BIG_ENDIAN
)
2801 = (((unsigned HOST_WIDE_INT
) offseti
+ sizei
)
2805 shift_bytes_in_array_right (buf
, buflen
,
2806 BITS_PER_UNIT
- amnt
);
2811 else if (offseti
% BITS_PER_UNIT
!= 0)
2814 = BITS_PER_UNIT
- ((unsigned HOST_WIDE_INT
) offseti
2816 shift_bytes_in_array_left (buf
, buflen
, amnt
);
2820 val
= native_interpret_expr (vr
->type
, buf
, buflen
);
2824 return data
->finish (0, 0, val
);
2826 /* For now handle clearing memory with partial defs. */
2827 else if (known_eq (ref
->size
, maxsize
)
2828 && integer_zerop (gimple_call_arg (def_stmt
, 1))
2829 && tree_fits_poly_int64_p (len
)
2830 && tree_to_poly_int64 (len
).is_constant (&leni
)
2831 && leni
<= INTTYPE_MAXIMUM (HOST_WIDE_INT
) / BITS_PER_UNIT
2832 && offset
.is_constant (&offseti
)
2833 && offset2
.is_constant (&offset2i
)
2834 && maxsize
.is_constant (&maxsizei
)
2835 && ranges_known_overlap_p (offseti
, maxsizei
, offset2i
,
2836 leni
<< LOG2_BITS_PER_UNIT
))
2839 pd
.rhs
= build_constructor (NULL_TREE
, NULL
);
2840 pd
.offset
= offset2i
;
2841 pd
.size
= leni
<< LOG2_BITS_PER_UNIT
;
2842 return data
->push_partial_def (pd
, 0, 0, offseti
, maxsizei
);
2846 /* 2) Assignment from an empty CONSTRUCTOR. */
2847 else if (is_gimple_reg_type (vr
->type
)
2848 && gimple_assign_single_p (def_stmt
)
2849 && gimple_assign_rhs_code (def_stmt
) == CONSTRUCTOR
2850 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt
)) == 0)
2853 poly_int64 offset2
, size2
, maxsize2
;
2854 HOST_WIDE_INT offset2i
, size2i
;
2855 gcc_assert (lhs_ref_ok
);
2856 base2
= ao_ref_base (&lhs_ref
);
2857 offset2
= lhs_ref
.offset
;
2858 size2
= lhs_ref
.size
;
2859 maxsize2
= lhs_ref
.max_size
;
2860 if (known_size_p (maxsize2
)
2861 && known_eq (maxsize2
, size2
)
2862 && adjust_offsets_for_equal_base_address (base
, &offset
,
2865 if (data
->partial_defs
.is_empty ()
2866 && known_subrange_p (offset
, maxsize
, offset2
, size2
))
2868 /* While technically undefined behavior do not optimize
2869 a full read from a clobber. */
2870 if (gimple_clobber_p (def_stmt
))
2872 tree val
= build_zero_cst (vr
->type
);
2873 return data
->finish (ao_ref_alias_set (&lhs_ref
),
2874 ao_ref_base_alias_set (&lhs_ref
), val
);
2876 else if (known_eq (ref
->size
, maxsize
)
2877 && maxsize
.is_constant (&maxsizei
)
2878 && offset
.is_constant (&offseti
)
2879 && offset2
.is_constant (&offset2i
)
2880 && size2
.is_constant (&size2i
)
2881 && ranges_known_overlap_p (offseti
, maxsizei
,
2884 /* Let clobbers be consumed by the partial-def tracker
2885 which can choose to ignore them if they are shadowed
2888 pd
.rhs
= gimple_assign_rhs1 (def_stmt
);
2889 pd
.offset
= offset2i
;
2891 return data
->push_partial_def (pd
, ao_ref_alias_set (&lhs_ref
),
2892 ao_ref_base_alias_set (&lhs_ref
),
2898 /* 3) Assignment from a constant. We can use folds native encode/interpret
2899 routines to extract the assigned bits. */
2900 else if (known_eq (ref
->size
, maxsize
)
2901 && is_gimple_reg_type (vr
->type
)
2902 && !contains_storage_order_barrier_p (vr
->operands
)
2903 && gimple_assign_single_p (def_stmt
)
2905 && BITS_PER_UNIT
== 8
2906 && BYTES_BIG_ENDIAN
== WORDS_BIG_ENDIAN
2907 /* native_encode and native_decode operate on arrays of bytes
2908 and so fundamentally need a compile-time size and offset. */
2909 && maxsize
.is_constant (&maxsizei
)
2910 && offset
.is_constant (&offseti
)
2911 && (is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
))
2912 || (TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
2913 && is_gimple_min_invariant (SSA_VAL (gimple_assign_rhs1 (def_stmt
))))))
2915 tree lhs
= gimple_assign_lhs (def_stmt
);
2917 poly_int64 offset2
, size2
, maxsize2
;
2918 HOST_WIDE_INT offset2i
, size2i
;
2920 gcc_assert (lhs_ref_ok
);
2921 base2
= ao_ref_base (&lhs_ref
);
2922 offset2
= lhs_ref
.offset
;
2923 size2
= lhs_ref
.size
;
2924 maxsize2
= lhs_ref
.max_size
;
2925 reverse
= reverse_storage_order_for_component_p (lhs
);
2928 && !storage_order_barrier_p (lhs
)
2929 && known_eq (maxsize2
, size2
)
2930 && adjust_offsets_for_equal_base_address (base
, &offset
,
2932 && offset
.is_constant (&offseti
)
2933 && offset2
.is_constant (&offset2i
)
2934 && size2
.is_constant (&size2i
))
2936 if (data
->partial_defs
.is_empty ()
2937 && known_subrange_p (offseti
, maxsizei
, offset2
, size2
))
2939 /* We support up to 512-bit values (for V8DFmode). */
2940 unsigned char buffer
[65];
2943 tree rhs
= gimple_assign_rhs1 (def_stmt
);
2944 if (TREE_CODE (rhs
) == SSA_NAME
)
2945 rhs
= SSA_VAL (rhs
);
2946 len
= native_encode_expr (rhs
,
2947 buffer
, sizeof (buffer
) - 1,
2948 (offseti
- offset2i
) / BITS_PER_UNIT
);
2949 if (len
> 0 && len
* BITS_PER_UNIT
>= maxsizei
)
2951 tree type
= vr
->type
;
2952 unsigned char *buf
= buffer
;
2953 unsigned int amnt
= 0;
2954 /* Make sure to interpret in a type that has a range
2955 covering the whole access size. */
2956 if (INTEGRAL_TYPE_P (vr
->type
)
2957 && maxsizei
!= TYPE_PRECISION (vr
->type
))
2958 type
= build_nonstandard_integer_type (maxsizei
,
2959 TYPE_UNSIGNED (type
));
2960 if (BYTES_BIG_ENDIAN
)
2962 /* For big-endian native_encode_expr stored the rhs
2963 such that the LSB of it is the LSB of buffer[len - 1].
2964 That bit is stored into memory at position
2965 offset2 + size2 - 1, i.e. in byte
2966 base + (offset2 + size2 - 1) / BITS_PER_UNIT.
2967 E.g. for offset2 1 and size2 14, rhs -1 and memory
2968 previously cleared that is:
2971 Now, if we want to extract offset 2 and size 12 from
2972 it using native_interpret_expr (which actually works
2973 for integral bitfield types in terms of byte size of
2974 the mode), the native_encode_expr stored the value
2977 and returned len 2 (the X bits are outside of
2979 Let sz be maxsize / BITS_PER_UNIT if not extracting
2980 a bitfield, and GET_MODE_SIZE otherwise.
2981 We need to align the LSB of the value we want to
2982 extract as the LSB of buf[sz - 1].
2983 The LSB from memory we need to read is at position
2984 offset + maxsize - 1. */
2985 HOST_WIDE_INT sz
= maxsizei
/ BITS_PER_UNIT
;
2986 if (INTEGRAL_TYPE_P (type
))
2987 sz
= GET_MODE_SIZE (SCALAR_INT_TYPE_MODE (type
));
2988 amnt
= ((unsigned HOST_WIDE_INT
) offset2i
+ size2i
2989 - offseti
- maxsizei
) % BITS_PER_UNIT
;
2991 shift_bytes_in_array_right (buffer
, len
, amnt
);
2992 amnt
= ((unsigned HOST_WIDE_INT
) offset2i
+ size2i
2993 - offseti
- maxsizei
- amnt
) / BITS_PER_UNIT
;
2994 if ((unsigned HOST_WIDE_INT
) sz
+ amnt
> (unsigned) len
)
2998 buf
= buffer
+ len
- sz
- amnt
;
2999 len
-= (buf
- buffer
);
3004 amnt
= ((unsigned HOST_WIDE_INT
) offset2i
3005 - offseti
) % BITS_PER_UNIT
;
3009 shift_bytes_in_array_left (buffer
, len
+ 1, amnt
);
3013 tree val
= native_interpret_expr (type
, buf
, len
);
3014 /* If we chop off bits because the types precision doesn't
3015 match the memory access size this is ok when optimizing
3016 reads but not when called from the DSE code during
3019 && type
!= vr
->type
)
3021 if (! int_fits_type_p (val
, vr
->type
))
3024 val
= fold_convert (vr
->type
, val
);
3028 return data
->finish (ao_ref_alias_set (&lhs_ref
),
3029 ao_ref_base_alias_set (&lhs_ref
), val
);
3032 else if (ranges_known_overlap_p (offseti
, maxsizei
, offset2i
,
3036 tree rhs
= gimple_assign_rhs1 (def_stmt
);
3037 if (TREE_CODE (rhs
) == SSA_NAME
)
3038 rhs
= SSA_VAL (rhs
);
3040 pd
.offset
= offset2i
;
3042 return data
->push_partial_def (pd
, ao_ref_alias_set (&lhs_ref
),
3043 ao_ref_base_alias_set (&lhs_ref
),
3049 /* 4) Assignment from an SSA name which definition we may be able
3050 to access pieces from or we can combine to a larger entity. */
3051 else if (known_eq (ref
->size
, maxsize
)
3052 && is_gimple_reg_type (vr
->type
)
3053 && !contains_storage_order_barrier_p (vr
->operands
)
3054 && gimple_assign_single_p (def_stmt
)
3055 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
)
3057 tree lhs
= gimple_assign_lhs (def_stmt
);
3059 poly_int64 offset2
, size2
, maxsize2
;
3060 HOST_WIDE_INT offset2i
, size2i
, offseti
;
3062 gcc_assert (lhs_ref_ok
);
3063 base2
= ao_ref_base (&lhs_ref
);
3064 offset2
= lhs_ref
.offset
;
3065 size2
= lhs_ref
.size
;
3066 maxsize2
= lhs_ref
.max_size
;
3067 reverse
= reverse_storage_order_for_component_p (lhs
);
3068 tree def_rhs
= gimple_assign_rhs1 (def_stmt
);
3070 && !storage_order_barrier_p (lhs
)
3071 && known_size_p (maxsize2
)
3072 && known_eq (maxsize2
, size2
)
3073 && adjust_offsets_for_equal_base_address (base
, &offset
,
3076 if (data
->partial_defs
.is_empty ()
3077 && known_subrange_p (offset
, maxsize
, offset2
, size2
)
3078 /* ??? We can't handle bitfield precision extracts without
3079 either using an alternate type for the BIT_FIELD_REF and
3080 then doing a conversion or possibly adjusting the offset
3081 according to endianness. */
3082 && (! INTEGRAL_TYPE_P (vr
->type
)
3083 || known_eq (ref
->size
, TYPE_PRECISION (vr
->type
)))
3084 && multiple_p (ref
->size
, BITS_PER_UNIT
))
3086 tree val
= NULL_TREE
;
3087 if (! INTEGRAL_TYPE_P (TREE_TYPE (def_rhs
))
3088 || type_has_mode_precision_p (TREE_TYPE (def_rhs
)))
3090 gimple_match_op
op (gimple_match_cond::UNCOND
,
3091 BIT_FIELD_REF
, vr
->type
,
3093 bitsize_int (ref
->size
),
3094 bitsize_int (offset
- offset2
));
3095 val
= vn_nary_build_or_lookup (&op
);
3097 else if (known_eq (ref
->size
, size2
))
3099 gimple_match_op
op (gimple_match_cond::UNCOND
,
3100 VIEW_CONVERT_EXPR
, vr
->type
,
3102 val
= vn_nary_build_or_lookup (&op
);
3105 && (TREE_CODE (val
) != SSA_NAME
3106 || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
)))
3107 return data
->finish (ao_ref_alias_set (&lhs_ref
),
3108 ao_ref_base_alias_set (&lhs_ref
), val
);
3110 else if (maxsize
.is_constant (&maxsizei
)
3111 && offset
.is_constant (&offseti
)
3112 && offset2
.is_constant (&offset2i
)
3113 && size2
.is_constant (&size2i
)
3114 && ranges_known_overlap_p (offset
, maxsize
, offset2
, size2
))
3117 pd
.rhs
= SSA_VAL (def_rhs
);
3118 pd
.offset
= offset2i
;
3120 return data
->push_partial_def (pd
, ao_ref_alias_set (&lhs_ref
),
3121 ao_ref_base_alias_set (&lhs_ref
),
3127 /* 5) For aggregate copies translate the reference through them if
3128 the copy kills ref. */
3129 else if (data
->vn_walk_kind
== VN_WALKREWRITE
3130 && gimple_assign_single_p (def_stmt
)
3131 && (DECL_P (gimple_assign_rhs1 (def_stmt
))
3132 || TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == MEM_REF
3133 || handled_component_p (gimple_assign_rhs1 (def_stmt
))))
3137 auto_vec
<vn_reference_op_s
> rhs
;
3138 vn_reference_op_t vro
;
3141 gcc_assert (lhs_ref_ok
);
3143 /* See if the assignment kills REF. */
3144 base2
= ao_ref_base (&lhs_ref
);
3145 if (!lhs_ref
.max_size_known_p ()
3147 && (TREE_CODE (base
) != MEM_REF
3148 || TREE_CODE (base2
) != MEM_REF
3149 || TREE_OPERAND (base
, 0) != TREE_OPERAND (base2
, 0)
3150 || !tree_int_cst_equal (TREE_OPERAND (base
, 1),
3151 TREE_OPERAND (base2
, 1))))
3152 || !stmt_kills_ref_p (def_stmt
, ref
))
3155 /* Find the common base of ref and the lhs. lhs_ops already
3156 contains valueized operands for the lhs. */
3157 i
= vr
->operands
.length () - 1;
3158 j
= lhs_ops
.length () - 1;
3159 while (j
>= 0 && i
>= 0
3160 && vn_reference_op_eq (&vr
->operands
[i
], &lhs_ops
[j
]))
3166 /* ??? The innermost op should always be a MEM_REF and we already
3167 checked that the assignment to the lhs kills vr. Thus for
3168 aggregate copies using char[] types the vn_reference_op_eq
3169 may fail when comparing types for compatibility. But we really
3170 don't care here - further lookups with the rewritten operands
3171 will simply fail if we messed up types too badly. */
3172 poly_int64 extra_off
= 0;
3173 if (j
== 0 && i
>= 0
3174 && lhs_ops
[0].opcode
== MEM_REF
3175 && maybe_ne (lhs_ops
[0].off
, -1))
3177 if (known_eq (lhs_ops
[0].off
, vr
->operands
[i
].off
))
3179 else if (vr
->operands
[i
].opcode
== MEM_REF
3180 && maybe_ne (vr
->operands
[i
].off
, -1))
3182 extra_off
= vr
->operands
[i
].off
- lhs_ops
[0].off
;
3187 /* i now points to the first additional op.
3188 ??? LHS may not be completely contained in VR, one or more
3189 VIEW_CONVERT_EXPRs could be in its way. We could at least
3190 try handling outermost VIEW_CONVERT_EXPRs. */
3194 /* Punt if the additional ops contain a storage order barrier. */
3195 for (k
= i
; k
>= 0; k
--)
3197 vro
= &vr
->operands
[k
];
3198 if (vro
->opcode
== VIEW_CONVERT_EXPR
&& vro
->reverse
)
3202 /* Now re-write REF to be based on the rhs of the assignment. */
3203 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
3204 copy_reference_ops_from_ref (rhs1
, &rhs
);
3206 /* Apply an extra offset to the inner MEM_REF of the RHS. */
3207 if (maybe_ne (extra_off
, 0))
3209 if (rhs
.length () < 2)
3211 int ix
= rhs
.length () - 2;
3212 if (rhs
[ix
].opcode
!= MEM_REF
3213 || known_eq (rhs
[ix
].off
, -1))
3215 rhs
[ix
].off
+= extra_off
;
3216 rhs
[ix
].op0
= int_const_binop (PLUS_EXPR
, rhs
[ix
].op0
,
3217 build_int_cst (TREE_TYPE (rhs
[ix
].op0
),
3221 /* Save the operands since we need to use the original ones for
3222 the hash entry we use. */
3223 if (!data
->saved_operands
.exists ())
3224 data
->saved_operands
= vr
->operands
.copy ();
3226 /* We need to pre-pend vr->operands[0..i] to rhs. */
3227 vec
<vn_reference_op_s
> old
= vr
->operands
;
3228 if (i
+ 1 + rhs
.length () > vr
->operands
.length ())
3229 vr
->operands
.safe_grow (i
+ 1 + rhs
.length (), true);
3231 vr
->operands
.truncate (i
+ 1 + rhs
.length ());
3232 FOR_EACH_VEC_ELT (rhs
, j
, vro
)
3233 vr
->operands
[i
+ 1 + j
] = *vro
;
3234 valueize_refs (&vr
->operands
);
3235 if (old
== shared_lookup_references
)
3236 shared_lookup_references
= vr
->operands
;
3237 vr
->hashcode
= vn_reference_compute_hash (vr
);
3239 /* Try folding the new reference to a constant. */
3240 tree val
= fully_constant_vn_reference_p (vr
);
3243 if (data
->partial_defs
.is_empty ())
3244 return data
->finish (ao_ref_alias_set (&lhs_ref
),
3245 ao_ref_base_alias_set (&lhs_ref
), val
);
3246 /* This is the only interesting case for partial-def handling
3247 coming from targets that like to gimplify init-ctors as
3248 aggregate copies from constant data like aarch64 for
3250 if (maxsize
.is_constant (&maxsizei
) && known_eq (ref
->size
, maxsize
))
3256 return data
->push_partial_def (pd
, ao_ref_alias_set (&lhs_ref
),
3257 ao_ref_base_alias_set (&lhs_ref
),
3262 /* Continuing with partial defs isn't easily possible here, we
3263 have to find a full def from further lookups from here. Probably
3264 not worth the special-casing everywhere. */
3265 if (!data
->partial_defs
.is_empty ())
3268 /* Adjust *ref from the new operands. */
3270 ao_ref_init (&rhs1_ref
, rhs1
);
3271 if (!ao_ref_init_from_vn_reference (&r
, ao_ref_alias_set (&rhs1_ref
),
3272 ao_ref_base_alias_set (&rhs1_ref
),
3273 vr
->type
, vr
->operands
))
3275 /* This can happen with bitfields. */
3276 if (maybe_ne (ref
->size
, r
.size
))
3278 /* If the access lacks some subsetting simply apply that by
3279 shortening it. That in the end can only be successful
3280 if we can pun the lookup result which in turn requires
3282 if (known_eq (r
.size
, r
.max_size
)
3283 && known_lt (ref
->size
, r
.size
))
3284 r
.size
= r
.max_size
= ref
->size
;
3290 /* Do not update last seen VUSE after translating. */
3291 data
->last_vuse_ptr
= NULL
;
3292 /* Invalidate the original access path since it now contains
3294 data
->orig_ref
.ref
= NULL_TREE
;
3295 /* Use the alias-set of this LHS for recording an eventual result. */
3296 if (data
->first_set
== -2)
3298 data
->first_set
= ao_ref_alias_set (&lhs_ref
);
3299 data
->first_base_set
= ao_ref_base_alias_set (&lhs_ref
);
3302 /* Keep looking for the adjusted *REF / VR pair. */
3306 /* 6) For memcpy copies translate the reference through them if the copy
3307 kills ref. But we cannot (easily) do this translation if the memcpy is
3308 a storage order barrier, i.e. is equivalent to a VIEW_CONVERT_EXPR that
3309 can modify the storage order of objects (see storage_order_barrier_p). */
3310 else if (data
->vn_walk_kind
== VN_WALKREWRITE
3311 && is_gimple_reg_type (vr
->type
)
3312 /* ??? Handle BCOPY as well. */
3313 && (gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMCPY
)
3314 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMCPY_CHK
)
3315 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMPCPY
)
3316 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMPCPY_CHK
)
3317 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMMOVE
)
3318 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMMOVE_CHK
))
3319 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
3320 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
)
3321 && (TREE_CODE (gimple_call_arg (def_stmt
, 1)) == ADDR_EXPR
3322 || TREE_CODE (gimple_call_arg (def_stmt
, 1)) == SSA_NAME
)
3323 && (poly_int_tree_p (gimple_call_arg (def_stmt
, 2), ©_size
)
3324 || (TREE_CODE (gimple_call_arg (def_stmt
, 2)) == SSA_NAME
3325 && poly_int_tree_p (SSA_VAL (gimple_call_arg (def_stmt
, 2)),
3327 /* Handling this is more complicated, give up for now. */
3328 && data
->partial_defs
.is_empty ())
3332 poly_int64 rhs_offset
, lhs_offset
;
3333 vn_reference_op_s op
;
3334 poly_uint64 mem_offset
;
3335 poly_int64 at
, byte_maxsize
;
3337 /* Only handle non-variable, addressable refs. */
3338 if (maybe_ne (ref
->size
, maxsize
)
3339 || !multiple_p (offset
, BITS_PER_UNIT
, &at
)
3340 || !multiple_p (maxsize
, BITS_PER_UNIT
, &byte_maxsize
))
3343 /* Extract a pointer base and an offset for the destination. */
3344 lhs
= gimple_call_arg (def_stmt
, 0);
3346 if (TREE_CODE (lhs
) == SSA_NAME
)
3348 lhs
= vn_valueize (lhs
);
3349 if (TREE_CODE (lhs
) == SSA_NAME
)
3351 gimple
*def_stmt
= SSA_NAME_DEF_STMT (lhs
);
3352 if (gimple_assign_single_p (def_stmt
)
3353 && gimple_assign_rhs_code (def_stmt
) == ADDR_EXPR
)
3354 lhs
= gimple_assign_rhs1 (def_stmt
);
3357 if (TREE_CODE (lhs
) == ADDR_EXPR
)
3359 if (AGGREGATE_TYPE_P (TREE_TYPE (TREE_TYPE (lhs
)))
3360 && TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (TREE_TYPE (lhs
))))
3362 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (lhs
, 0),
3366 if (TREE_CODE (tem
) == MEM_REF
3367 && poly_int_tree_p (TREE_OPERAND (tem
, 1), &mem_offset
))
3369 lhs
= TREE_OPERAND (tem
, 0);
3370 if (TREE_CODE (lhs
) == SSA_NAME
)
3371 lhs
= vn_valueize (lhs
);
3372 lhs_offset
+= mem_offset
;
3374 else if (DECL_P (tem
))
3375 lhs
= build_fold_addr_expr (tem
);
3379 if (TREE_CODE (lhs
) != SSA_NAME
3380 && TREE_CODE (lhs
) != ADDR_EXPR
)
3383 /* Extract a pointer base and an offset for the source. */
3384 rhs
= gimple_call_arg (def_stmt
, 1);
3386 if (TREE_CODE (rhs
) == SSA_NAME
)
3387 rhs
= vn_valueize (rhs
);
3388 if (TREE_CODE (rhs
) == ADDR_EXPR
)
3390 if (AGGREGATE_TYPE_P (TREE_TYPE (TREE_TYPE (rhs
)))
3391 && TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (TREE_TYPE (rhs
))))
3393 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs
, 0),
3397 if (TREE_CODE (tem
) == MEM_REF
3398 && poly_int_tree_p (TREE_OPERAND (tem
, 1), &mem_offset
))
3400 rhs
= TREE_OPERAND (tem
, 0);
3401 rhs_offset
+= mem_offset
;
3403 else if (DECL_P (tem
)
3404 || TREE_CODE (tem
) == STRING_CST
)
3405 rhs
= build_fold_addr_expr (tem
);
3409 if (TREE_CODE (rhs
) == SSA_NAME
)
3410 rhs
= SSA_VAL (rhs
);
3411 else if (TREE_CODE (rhs
) != ADDR_EXPR
)
3414 /* The bases of the destination and the references have to agree. */
3415 if (TREE_CODE (base
) == MEM_REF
)
3417 if (TREE_OPERAND (base
, 0) != lhs
3418 || !poly_int_tree_p (TREE_OPERAND (base
, 1), &mem_offset
))
3422 else if (!DECL_P (base
)
3423 || TREE_CODE (lhs
) != ADDR_EXPR
3424 || TREE_OPERAND (lhs
, 0) != base
)
3427 /* If the access is completely outside of the memcpy destination
3428 area there is no aliasing. */
3429 if (!ranges_maybe_overlap_p (lhs_offset
, copy_size
, at
, byte_maxsize
))
3431 /* And the access has to be contained within the memcpy destination. */
3432 if (!known_subrange_p (at
, byte_maxsize
, lhs_offset
, copy_size
))
3435 /* Save the operands since we need to use the original ones for
3436 the hash entry we use. */
3437 if (!data
->saved_operands
.exists ())
3438 data
->saved_operands
= vr
->operands
.copy ();
3440 /* Make room for 2 operands in the new reference. */
3441 if (vr
->operands
.length () < 2)
3443 vec
<vn_reference_op_s
> old
= vr
->operands
;
3444 vr
->operands
.safe_grow_cleared (2, true);
3445 if (old
== shared_lookup_references
)
3446 shared_lookup_references
= vr
->operands
;
3449 vr
->operands
.truncate (2);
3451 /* The looked-through reference is a simple MEM_REF. */
3452 memset (&op
, 0, sizeof (op
));
3454 op
.opcode
= MEM_REF
;
3455 op
.op0
= build_int_cst (ptr_type_node
, at
- lhs_offset
+ rhs_offset
);
3456 op
.off
= at
- lhs_offset
+ rhs_offset
;
3457 vr
->operands
[0] = op
;
3458 op
.type
= TREE_TYPE (rhs
);
3459 op
.opcode
= TREE_CODE (rhs
);
3462 vr
->operands
[1] = op
;
3463 vr
->hashcode
= vn_reference_compute_hash (vr
);
3465 /* Try folding the new reference to a constant. */
3466 tree val
= fully_constant_vn_reference_p (vr
);
3468 return data
->finish (0, 0, val
);
3470 /* Adjust *ref from the new operands. */
3471 if (!ao_ref_init_from_vn_reference (&r
, 0, 0, vr
->type
, vr
->operands
))
3473 /* This can happen with bitfields. */
3474 if (maybe_ne (ref
->size
, r
.size
))
3478 /* Do not update last seen VUSE after translating. */
3479 data
->last_vuse_ptr
= NULL
;
3480 /* Invalidate the original access path since it now contains
3482 data
->orig_ref
.ref
= NULL_TREE
;
3483 /* Use the alias-set of this stmt for recording an eventual result. */
3484 if (data
->first_set
== -2)
3486 data
->first_set
= 0;
3487 data
->first_base_set
= 0;
3490 /* Keep looking for the adjusted *REF / VR pair. */
3494 /* Bail out and stop walking. */
3498 /* Return a reference op vector from OP that can be used for
3499 vn_reference_lookup_pieces. The caller is responsible for releasing
3502 vec
<vn_reference_op_s
>
3503 vn_reference_operands_for_lookup (tree op
)
3506 return valueize_shared_reference_ops_from_ref (op
, &valueized
).copy ();
3509 /* Lookup a reference operation by it's parts, in the current hash table.
3510 Returns the resulting value number if it exists in the hash table,
3511 NULL_TREE otherwise. VNRESULT will be filled in with the actual
3512 vn_reference_t stored in the hashtable if something is found. */
3515 vn_reference_lookup_pieces (tree vuse
, alias_set_type set
,
3516 alias_set_type base_set
, tree type
,
3517 vec
<vn_reference_op_s
> operands
,
3518 vn_reference_t
*vnresult
, vn_lookup_kind kind
)
3520 struct vn_reference_s vr1
;
3528 vr1
.vuse
= vuse_ssa_val (vuse
);
3529 shared_lookup_references
.truncate (0);
3530 shared_lookup_references
.safe_grow (operands
.length (), true);
3531 memcpy (shared_lookup_references
.address (),
3532 operands
.address (),
3533 sizeof (vn_reference_op_s
)
3534 * operands
.length ());
3536 valueize_refs_1 (&shared_lookup_references
, &valueized_p
);
3537 vr1
.operands
= shared_lookup_references
;
3540 vr1
.base_set
= base_set
;
3541 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
3542 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
3545 vn_reference_lookup_1 (&vr1
, vnresult
);
3547 && kind
!= VN_NOWALK
3551 unsigned limit
= param_sccvn_max_alias_queries_per_access
;
3552 vn_walk_cb_data
data (&vr1
, NULL_TREE
, NULL
, kind
, true, NULL_TREE
);
3553 vec
<vn_reference_op_s
> ops_for_ref
;
3555 ops_for_ref
= vr1
.operands
;
3558 /* For ao_ref_from_mem we have to ensure only available SSA names
3559 end up in base and the only convenient way to make this work
3560 for PRE is to re-valueize with that in mind. */
3561 ops_for_ref
.create (operands
.length ());
3562 ops_for_ref
.quick_grow (operands
.length ());
3563 memcpy (ops_for_ref
.address (),
3564 operands
.address (),
3565 sizeof (vn_reference_op_s
)
3566 * operands
.length ());
3567 valueize_refs_1 (&ops_for_ref
, &valueized_p
, true);
3569 if (ao_ref_init_from_vn_reference (&r
, set
, base_set
, type
,
3573 walk_non_aliased_vuses (&r
, vr1
.vuse
, true, vn_reference_lookup_2
,
3574 vn_reference_lookup_3
, vuse_valueize
,
3576 if (ops_for_ref
!= shared_lookup_references
)
3577 ops_for_ref
.release ();
3578 gcc_checking_assert (vr1
.operands
== shared_lookup_references
);
3582 return (*vnresult
)->result
;
3587 /* Lookup OP in the current hash table, and return the resulting value
3588 number if it exists in the hash table. Return NULL_TREE if it does
3589 not exist in the hash table or if the result field of the structure
3590 was NULL.. VNRESULT will be filled in with the vn_reference_t
3591 stored in the hashtable if one exists. When TBAA_P is false assume
3592 we are looking up a store and treat it as having alias-set zero.
3593 *LAST_VUSE_PTR will be updated with the VUSE the value lookup succeeded.
3594 MASK is either NULL_TREE, or can be an INTEGER_CST if the result of the
3595 load is bitwise anded with MASK and so we are only interested in a subset
3596 of the bits and can ignore if the other bits are uninitialized or
3597 not initialized with constants. */
3600 vn_reference_lookup (tree op
, tree vuse
, vn_lookup_kind kind
,
3601 vn_reference_t
*vnresult
, bool tbaa_p
,
3602 tree
*last_vuse_ptr
, tree mask
)
3604 vec
<vn_reference_op_s
> operands
;
3605 struct vn_reference_s vr1
;
3606 bool valueized_anything
;
3611 vr1
.vuse
= vuse_ssa_val (vuse
);
3612 vr1
.operands
= operands
3613 = valueize_shared_reference_ops_from_ref (op
, &valueized_anything
);
3614 vr1
.type
= TREE_TYPE (op
);
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 if (mask
== NULL_TREE
)
3621 if (tree cst
= fully_constant_vn_reference_p (&vr1
))
3624 if (kind
!= VN_NOWALK
&& vr1
.vuse
)
3626 vn_reference_t wvnresult
;
3628 unsigned limit
= param_sccvn_max_alias_queries_per_access
;
3629 auto_vec
<vn_reference_op_s
> ops_for_ref
;
3630 if (valueized_anything
)
3632 copy_reference_ops_from_ref (op
, &ops_for_ref
);
3634 valueize_refs_1 (&ops_for_ref
, &tem
, true);
3636 /* Make sure to use a valueized reference if we valueized anything.
3637 Otherwise preserve the full reference for advanced TBAA. */
3638 if (!valueized_anything
3639 || !ao_ref_init_from_vn_reference (&r
, vr1
.set
, vr1
.base_set
,
3640 vr1
.type
, ops_for_ref
))
3641 ao_ref_init (&r
, op
);
3642 vn_walk_cb_data
data (&vr1
, r
.ref
? NULL_TREE
: op
,
3643 last_vuse_ptr
, kind
, tbaa_p
, mask
);
3647 walk_non_aliased_vuses (&r
, vr1
.vuse
, tbaa_p
, vn_reference_lookup_2
,
3648 vn_reference_lookup_3
, vuse_valueize
, limit
,
3650 gcc_checking_assert (vr1
.operands
== shared_lookup_references
);
3653 gcc_assert (mask
== NULL_TREE
);
3655 *vnresult
= wvnresult
;
3656 return wvnresult
->result
;
3659 return data
.masked_result
;
3665 *last_vuse_ptr
= vr1
.vuse
;
3668 return vn_reference_lookup_1 (&vr1
, vnresult
);
3671 /* Lookup CALL in the current hash table and return the entry in
3672 *VNRESULT if found. Populates *VR for the hashtable lookup. */
3675 vn_reference_lookup_call (gcall
*call
, vn_reference_t
*vnresult
,
3681 tree vuse
= gimple_vuse (call
);
3683 vr
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
3684 vr
->operands
= valueize_shared_reference_ops_from_call (call
);
3685 tree lhs
= gimple_call_lhs (call
);
3686 /* For non-SSA return values the referece ops contain the LHS. */
3687 vr
->type
= ((lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
3688 ? TREE_TYPE (lhs
) : NULL_TREE
);
3692 vr
->hashcode
= vn_reference_compute_hash (vr
);
3693 vn_reference_lookup_1 (vr
, vnresult
);
3696 /* Insert OP into the current hash table with a value number of RESULT. */
3699 vn_reference_insert (tree op
, tree result
, tree vuse
, tree vdef
)
3701 vn_reference_s
**slot
;
3705 vr1
= XOBNEW (&vn_tables_obstack
, vn_reference_s
);
3706 if (TREE_CODE (result
) == SSA_NAME
)
3707 vr1
->value_id
= VN_INFO (result
)->value_id
;
3709 vr1
->value_id
= get_or_alloc_constant_value_id (result
);
3710 vr1
->vuse
= vuse_ssa_val (vuse
);
3711 vr1
->operands
= valueize_shared_reference_ops_from_ref (op
, &tem
).copy ();
3712 vr1
->type
= TREE_TYPE (op
);
3713 vr1
->punned
= false;
3715 ao_ref_init (&op_ref
, op
);
3716 vr1
->set
= ao_ref_alias_set (&op_ref
);
3717 vr1
->base_set
= ao_ref_base_alias_set (&op_ref
);
3718 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
3719 vr1
->result
= TREE_CODE (result
) == SSA_NAME
? SSA_VAL (result
) : result
;
3720 vr1
->result_vdef
= vdef
;
3722 slot
= valid_info
->references
->find_slot_with_hash (vr1
, vr1
->hashcode
,
3725 /* Because IL walking on reference lookup can end up visiting
3726 a def that is only to be visited later in iteration order
3727 when we are about to make an irreducible region reducible
3728 the def can be effectively processed and its ref being inserted
3729 by vn_reference_lookup_3 already. So we cannot assert (!*slot)
3730 but save a lookup if we deal with already inserted refs here. */
3733 /* We cannot assert that we have the same value either because
3734 when disentangling an irreducible region we may end up visiting
3735 a use before the corresponding def. That's a missed optimization
3736 only though. See gcc.dg/tree-ssa/pr87126.c for example. */
3737 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
3738 && !operand_equal_p ((*slot
)->result
, vr1
->result
, 0))
3740 fprintf (dump_file
, "Keeping old value ");
3741 print_generic_expr (dump_file
, (*slot
)->result
);
3742 fprintf (dump_file
, " because of collision\n");
3744 free_reference (vr1
);
3745 obstack_free (&vn_tables_obstack
, vr1
);
3750 vr1
->next
= last_inserted_ref
;
3751 last_inserted_ref
= vr1
;
3754 /* Insert a reference by it's pieces into the current hash table with
3755 a value number of RESULT. Return the resulting reference
3756 structure we created. */
3759 vn_reference_insert_pieces (tree vuse
, alias_set_type set
,
3760 alias_set_type base_set
, tree type
,
3761 vec
<vn_reference_op_s
> operands
,
3762 tree result
, unsigned int value_id
)
3765 vn_reference_s
**slot
;
3768 vr1
= XOBNEW (&vn_tables_obstack
, vn_reference_s
);
3769 vr1
->value_id
= value_id
;
3770 vr1
->vuse
= vuse_ssa_val (vuse
);
3771 vr1
->operands
= operands
;
3772 valueize_refs (&vr1
->operands
);
3774 vr1
->punned
= false;
3776 vr1
->base_set
= base_set
;
3777 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
3778 if (result
&& TREE_CODE (result
) == SSA_NAME
)
3779 result
= SSA_VAL (result
);
3780 vr1
->result
= result
;
3782 slot
= valid_info
->references
->find_slot_with_hash (vr1
, vr1
->hashcode
,
3785 /* At this point we should have all the things inserted that we have
3786 seen before, and we should never try inserting something that
3788 gcc_assert (!*slot
);
3791 vr1
->next
= last_inserted_ref
;
3792 last_inserted_ref
= vr1
;
3796 /* Compute and return the hash value for nary operation VBO1. */
3799 vn_nary_op_compute_hash (const vn_nary_op_t vno1
)
3801 inchash::hash hstate
;
3804 for (i
= 0; i
< vno1
->length
; ++i
)
3805 if (TREE_CODE (vno1
->op
[i
]) == SSA_NAME
)
3806 vno1
->op
[i
] = SSA_VAL (vno1
->op
[i
]);
3808 if (((vno1
->length
== 2
3809 && commutative_tree_code (vno1
->opcode
))
3810 || (vno1
->length
== 3
3811 && commutative_ternary_tree_code (vno1
->opcode
)))
3812 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1]))
3813 std::swap (vno1
->op
[0], vno1
->op
[1]);
3814 else if (TREE_CODE_CLASS (vno1
->opcode
) == tcc_comparison
3815 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1]))
3817 std::swap (vno1
->op
[0], vno1
->op
[1]);
3818 vno1
->opcode
= swap_tree_comparison (vno1
->opcode
);
3821 hstate
.add_int (vno1
->opcode
);
3822 for (i
= 0; i
< vno1
->length
; ++i
)
3823 inchash::add_expr (vno1
->op
[i
], hstate
);
3825 return hstate
.end ();
3828 /* Compare nary operations VNO1 and VNO2 and return true if they are
3832 vn_nary_op_eq (const_vn_nary_op_t
const vno1
, const_vn_nary_op_t
const vno2
)
3836 if (vno1
->hashcode
!= vno2
->hashcode
)
3839 if (vno1
->length
!= vno2
->length
)
3842 if (vno1
->opcode
!= vno2
->opcode
3843 || !types_compatible_p (vno1
->type
, vno2
->type
))
3846 for (i
= 0; i
< vno1
->length
; ++i
)
3847 if (!expressions_equal_p (vno1
->op
[i
], vno2
->op
[i
]))
3850 /* BIT_INSERT_EXPR has an implict operand as the type precision
3851 of op1. Need to check to make sure they are the same. */
3852 if (vno1
->opcode
== BIT_INSERT_EXPR
3853 && TREE_CODE (vno1
->op
[1]) == INTEGER_CST
3854 && TYPE_PRECISION (TREE_TYPE (vno1
->op
[1]))
3855 != TYPE_PRECISION (TREE_TYPE (vno2
->op
[1])))
3861 /* Initialize VNO from the pieces provided. */
3864 init_vn_nary_op_from_pieces (vn_nary_op_t vno
, unsigned int length
,
3865 enum tree_code code
, tree type
, tree
*ops
)
3868 vno
->length
= length
;
3870 memcpy (&vno
->op
[0], ops
, sizeof (tree
) * length
);
3873 /* Return the number of operands for a vn_nary ops structure from STMT. */
3876 vn_nary_length_from_stmt (gimple
*stmt
)
3878 switch (gimple_assign_rhs_code (stmt
))
3882 case VIEW_CONVERT_EXPR
:
3889 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
3892 return gimple_num_ops (stmt
) - 1;
3896 /* Initialize VNO from STMT. */
3899 init_vn_nary_op_from_stmt (vn_nary_op_t vno
, gassign
*stmt
)
3903 vno
->opcode
= gimple_assign_rhs_code (stmt
);
3904 vno
->type
= TREE_TYPE (gimple_assign_lhs (stmt
));
3905 switch (vno
->opcode
)
3909 case VIEW_CONVERT_EXPR
:
3911 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
3916 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
3917 vno
->op
[1] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1);
3918 vno
->op
[2] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
3922 vno
->length
= CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
3923 for (i
= 0; i
< vno
->length
; ++i
)
3924 vno
->op
[i
] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt
), i
)->value
;
3928 gcc_checking_assert (!gimple_assign_single_p (stmt
));
3929 vno
->length
= gimple_num_ops (stmt
) - 1;
3930 for (i
= 0; i
< vno
->length
; ++i
)
3931 vno
->op
[i
] = gimple_op (stmt
, i
+ 1);
3935 /* Compute the hashcode for VNO and look for it in the hash table;
3936 return the resulting value number if it exists in the hash table.
3937 Return NULL_TREE if it does not exist in the hash table or if the
3938 result field of the operation is NULL. VNRESULT will contain the
3939 vn_nary_op_t from the hashtable if it exists. */
3942 vn_nary_op_lookup_1 (vn_nary_op_t vno
, vn_nary_op_t
*vnresult
)
3944 vn_nary_op_s
**slot
;
3949 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
3950 slot
= valid_info
->nary
->find_slot_with_hash (vno
, vno
->hashcode
, NO_INSERT
);
3955 return (*slot
)->predicated_values
? NULL_TREE
: (*slot
)->u
.result
;
3958 /* Lookup a n-ary operation by its pieces and return the resulting value
3959 number if it exists in the hash table. Return NULL_TREE if it does
3960 not exist in the hash table or if the result field of the operation
3961 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
3965 vn_nary_op_lookup_pieces (unsigned int length
, enum tree_code code
,
3966 tree type
, tree
*ops
, vn_nary_op_t
*vnresult
)
3968 vn_nary_op_t vno1
= XALLOCAVAR (struct vn_nary_op_s
,
3969 sizeof_vn_nary_op (length
));
3970 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
3971 return vn_nary_op_lookup_1 (vno1
, vnresult
);
3974 /* Lookup the rhs of STMT in the current hash table, and return the resulting
3975 value number if it exists in the hash table. Return NULL_TREE if
3976 it does not exist in the hash table. VNRESULT will contain the
3977 vn_nary_op_t from the hashtable if it exists. */
3980 vn_nary_op_lookup_stmt (gimple
*stmt
, vn_nary_op_t
*vnresult
)
3983 = XALLOCAVAR (struct vn_nary_op_s
,
3984 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt
)));
3985 init_vn_nary_op_from_stmt (vno1
, as_a
<gassign
*> (stmt
));
3986 return vn_nary_op_lookup_1 (vno1
, vnresult
);
3989 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
3992 alloc_vn_nary_op_noinit (unsigned int length
, struct obstack
*stack
)
3994 return (vn_nary_op_t
) obstack_alloc (stack
, sizeof_vn_nary_op (length
));
3997 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
4001 alloc_vn_nary_op (unsigned int length
, tree result
, unsigned int value_id
)
4003 vn_nary_op_t vno1
= alloc_vn_nary_op_noinit (length
, &vn_tables_obstack
);
4005 vno1
->value_id
= value_id
;
4006 vno1
->length
= length
;
4007 vno1
->predicated_values
= 0;
4008 vno1
->u
.result
= result
;
4013 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
4014 VNO->HASHCODE first. */
4017 vn_nary_op_insert_into (vn_nary_op_t vno
, vn_nary_op_table_type
*table
,
4020 vn_nary_op_s
**slot
;
4024 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
4025 gcc_assert (! vno
->predicated_values
4026 || (! vno
->u
.values
->next
4027 && vno
->u
.values
->n
== 1));
4030 slot
= table
->find_slot_with_hash (vno
, vno
->hashcode
, INSERT
);
4031 vno
->unwind_to
= *slot
;
4034 /* Prefer non-predicated values.
4035 ??? Only if those are constant, otherwise, with constant predicated
4036 value, turn them into predicated values with entry-block validity
4037 (??? but we always find the first valid result currently). */
4038 if ((*slot
)->predicated_values
4039 && ! vno
->predicated_values
)
4041 /* ??? We cannot remove *slot from the unwind stack list.
4042 For the moment we deal with this by skipping not found
4043 entries but this isn't ideal ... */
4045 /* ??? Maintain a stack of states we can unwind in
4046 vn_nary_op_s? But how far do we unwind? In reality
4047 we need to push change records somewhere... Or not
4048 unwind vn_nary_op_s and linking them but instead
4049 unwind the results "list", linking that, which also
4050 doesn't move on hashtable resize. */
4051 /* We can also have a ->unwind_to recording *slot there.
4052 That way we can make u.values a fixed size array with
4053 recording the number of entries but of course we then
4054 have always N copies for each unwind_to-state. Or we
4055 make sure to only ever append and each unwinding will
4056 pop off one entry (but how to deal with predicated
4057 replaced with non-predicated here?) */
4058 vno
->next
= last_inserted_nary
;
4059 last_inserted_nary
= vno
;
4062 else if (vno
->predicated_values
4063 && ! (*slot
)->predicated_values
)
4065 else if (vno
->predicated_values
4066 && (*slot
)->predicated_values
)
4068 /* ??? Factor this all into a insert_single_predicated_value
4070 gcc_assert (!vno
->u
.values
->next
&& vno
->u
.values
->n
== 1);
4072 = BASIC_BLOCK_FOR_FN (cfun
, vno
->u
.values
->valid_dominated_by_p
[0]);
4073 vn_pval
*nval
= vno
->u
.values
;
4074 vn_pval
**next
= &vno
->u
.values
;
4076 for (vn_pval
*val
= (*slot
)->u
.values
; val
; val
= val
->next
)
4078 if (expressions_equal_p (val
->result
, vno
->u
.values
->result
))
4081 for (unsigned i
= 0; i
< val
->n
; ++i
)
4084 = BASIC_BLOCK_FOR_FN (cfun
,
4085 val
->valid_dominated_by_p
[i
]);
4086 if (dominated_by_p (CDI_DOMINATORS
, vno_bb
, val_bb
))
4087 /* Value registered with more generic predicate. */
4089 else if (dominated_by_p (CDI_DOMINATORS
, val_bb
, vno_bb
))
4090 /* Shouldn't happen, we insert in RPO order. */
4094 *next
= (vn_pval
*) obstack_alloc (&vn_tables_obstack
,
4096 + val
->n
* sizeof (int));
4097 (*next
)->next
= NULL
;
4098 (*next
)->result
= val
->result
;
4099 (*next
)->n
= val
->n
+ 1;
4100 memcpy ((*next
)->valid_dominated_by_p
,
4101 val
->valid_dominated_by_p
,
4102 val
->n
* sizeof (int));
4103 (*next
)->valid_dominated_by_p
[val
->n
] = vno_bb
->index
;
4104 next
= &(*next
)->next
;
4105 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4106 fprintf (dump_file
, "Appending predicate to value.\n");
4109 /* Copy other predicated values. */
4110 *next
= (vn_pval
*) obstack_alloc (&vn_tables_obstack
,
4112 + (val
->n
-1) * sizeof (int));
4113 memcpy (*next
, val
, sizeof (vn_pval
) + (val
->n
-1) * sizeof (int));
4114 (*next
)->next
= NULL
;
4115 next
= &(*next
)->next
;
4121 vno
->next
= last_inserted_nary
;
4122 last_inserted_nary
= vno
;
4126 /* While we do not want to insert things twice it's awkward to
4127 avoid it in the case where visit_nary_op pattern-matches stuff
4128 and ends up simplifying the replacement to itself. We then
4129 get two inserts, one from visit_nary_op and one from
4130 vn_nary_build_or_lookup.
4131 So allow inserts with the same value number. */
4132 if ((*slot
)->u
.result
== vno
->u
.result
)
4136 /* ??? There's also optimistic vs. previous commited state merging
4137 that is problematic for the case of unwinding. */
4139 /* ??? We should return NULL if we do not use 'vno' and have the
4140 caller release it. */
4141 gcc_assert (!*slot
);
4144 vno
->next
= last_inserted_nary
;
4145 last_inserted_nary
= vno
;
4149 /* Insert a n-ary operation into the current hash table using it's
4150 pieces. Return the vn_nary_op_t structure we created and put in
4154 vn_nary_op_insert_pieces (unsigned int length
, enum tree_code code
,
4155 tree type
, tree
*ops
,
4156 tree result
, unsigned int value_id
)
4158 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, result
, value_id
);
4159 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
4160 return vn_nary_op_insert_into (vno1
, valid_info
->nary
, true);
4164 vn_nary_op_insert_pieces_predicated (unsigned int length
, enum tree_code code
,
4165 tree type
, tree
*ops
,
4166 tree result
, unsigned int value_id
,
4169 /* ??? Currently tracking BBs. */
4170 if (! single_pred_p (pred_e
->dest
))
4172 /* Never record for backedges. */
4173 if (pred_e
->flags
& EDGE_DFS_BACK
)
4178 /* Ignore backedges. */
4179 FOR_EACH_EDGE (e
, ei
, pred_e
->dest
->preds
)
4180 if (! dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
4185 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
4186 /* ??? Fix dumping, but currently we only get comparisons. */
4187 && TREE_CODE_CLASS (code
) == tcc_comparison
)
4189 fprintf (dump_file
, "Recording on edge %d->%d ", pred_e
->src
->index
,
4190 pred_e
->dest
->index
);
4191 print_generic_expr (dump_file
, ops
[0], TDF_SLIM
);
4192 fprintf (dump_file
, " %s ", get_tree_code_name (code
));
4193 print_generic_expr (dump_file
, ops
[1], TDF_SLIM
);
4194 fprintf (dump_file
, " == %s\n",
4195 integer_zerop (result
) ? "false" : "true");
4197 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, NULL_TREE
, value_id
);
4198 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
4199 vno1
->predicated_values
= 1;
4200 vno1
->u
.values
= (vn_pval
*) obstack_alloc (&vn_tables_obstack
,
4202 vno1
->u
.values
->next
= NULL
;
4203 vno1
->u
.values
->result
= result
;
4204 vno1
->u
.values
->n
= 1;
4205 vno1
->u
.values
->valid_dominated_by_p
[0] = pred_e
->dest
->index
;
4206 return vn_nary_op_insert_into (vno1
, valid_info
->nary
, true);
4210 dominated_by_p_w_unex (basic_block bb1
, basic_block bb2
, bool);
4213 vn_nary_op_get_predicated_value (vn_nary_op_t vno
, basic_block bb
)
4215 if (! vno
->predicated_values
)
4216 return vno
->u
.result
;
4217 for (vn_pval
*val
= vno
->u
.values
; val
; val
= val
->next
)
4218 for (unsigned i
= 0; i
< val
->n
; ++i
)
4219 /* Do not handle backedge executability optimistically since
4220 when figuring out whether to iterate we do not consider
4221 changed predication. */
4222 if (dominated_by_p_w_unex
4223 (bb
, BASIC_BLOCK_FOR_FN (cfun
, val
->valid_dominated_by_p
[i
]),
4229 /* Insert the rhs of STMT into the current hash table with a value number of
4233 vn_nary_op_insert_stmt (gimple
*stmt
, tree result
)
4236 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt
),
4237 result
, VN_INFO (result
)->value_id
);
4238 init_vn_nary_op_from_stmt (vno1
, as_a
<gassign
*> (stmt
));
4239 return vn_nary_op_insert_into (vno1
, valid_info
->nary
, true);
4242 /* Compute a hashcode for PHI operation VP1 and return it. */
4244 static inline hashval_t
4245 vn_phi_compute_hash (vn_phi_t vp1
)
4247 inchash::hash hstate
;
4253 hstate
.add_int (EDGE_COUNT (vp1
->block
->preds
));
4254 switch (EDGE_COUNT (vp1
->block
->preds
))
4259 if (vp1
->block
->loop_father
->header
== vp1
->block
)
4265 hstate
.add_int (vp1
->block
->index
);
4268 /* If all PHI arguments are constants we need to distinguish
4269 the PHI node via its type. */
4271 hstate
.merge_hash (vn_hash_type (type
));
4273 FOR_EACH_EDGE (e
, ei
, vp1
->block
->preds
)
4275 /* Don't hash backedge values they need to be handled as VN_TOP
4276 for optimistic value-numbering. */
4277 if (e
->flags
& EDGE_DFS_BACK
)
4280 phi1op
= vp1
->phiargs
[e
->dest_idx
];
4281 if (phi1op
== VN_TOP
)
4283 inchash::add_expr (phi1op
, hstate
);
4286 return hstate
.end ();
4290 /* Return true if COND1 and COND2 represent the same condition, set
4291 *INVERTED_P if one needs to be inverted to make it the same as
4295 cond_stmts_equal_p (gcond
*cond1
, tree lhs1
, tree rhs1
,
4296 gcond
*cond2
, tree lhs2
, tree rhs2
, bool *inverted_p
)
4298 enum tree_code code1
= gimple_cond_code (cond1
);
4299 enum tree_code code2
= gimple_cond_code (cond2
);
4301 *inverted_p
= false;
4304 else if (code1
== swap_tree_comparison (code2
))
4305 std::swap (lhs2
, rhs2
);
4306 else if (code1
== invert_tree_comparison (code2
, HONOR_NANS (lhs2
)))
4308 else if (code1
== invert_tree_comparison
4309 (swap_tree_comparison (code2
), HONOR_NANS (lhs2
)))
4311 std::swap (lhs2
, rhs2
);
4317 return ((expressions_equal_p (lhs1
, lhs2
)
4318 && expressions_equal_p (rhs1
, rhs2
))
4319 || (commutative_tree_code (code1
)
4320 && expressions_equal_p (lhs1
, rhs2
)
4321 && expressions_equal_p (rhs1
, lhs2
)));
4324 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
4327 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
)
4329 if (vp1
->hashcode
!= vp2
->hashcode
)
4332 if (vp1
->block
!= vp2
->block
)
4334 if (EDGE_COUNT (vp1
->block
->preds
) != EDGE_COUNT (vp2
->block
->preds
))
4337 switch (EDGE_COUNT (vp1
->block
->preds
))
4340 /* Single-arg PHIs are just copies. */
4345 /* Rule out backedges into the PHI. */
4346 if (vp1
->block
->loop_father
->header
== vp1
->block
4347 || vp2
->block
->loop_father
->header
== vp2
->block
)
4350 /* If the PHI nodes do not have compatible types
4351 they are not the same. */
4352 if (!types_compatible_p (vp1
->type
, vp2
->type
))
4356 = get_immediate_dominator (CDI_DOMINATORS
, vp1
->block
);
4358 = get_immediate_dominator (CDI_DOMINATORS
, vp2
->block
);
4359 /* If the immediate dominator end in switch stmts multiple
4360 values may end up in the same PHI arg via intermediate
4362 if (EDGE_COUNT (idom1
->succs
) != 2
4363 || EDGE_COUNT (idom2
->succs
) != 2)
4366 /* Verify the controlling stmt is the same. */
4367 gcond
*last1
= safe_dyn_cast
<gcond
*> (last_stmt (idom1
));
4368 gcond
*last2
= safe_dyn_cast
<gcond
*> (last_stmt (idom2
));
4369 if (! last1
|| ! last2
)
4372 if (! cond_stmts_equal_p (last1
, vp1
->cclhs
, vp1
->ccrhs
,
4373 last2
, vp2
->cclhs
, vp2
->ccrhs
,
4377 /* Get at true/false controlled edges into the PHI. */
4378 edge te1
, te2
, fe1
, fe2
;
4379 if (! extract_true_false_controlled_edges (idom1
, vp1
->block
,
4381 || ! extract_true_false_controlled_edges (idom2
, vp2
->block
,
4385 /* Swap edges if the second condition is the inverted of the
4388 std::swap (te2
, fe2
);
4390 /* ??? Handle VN_TOP specially. */
4391 if (! expressions_equal_p (vp1
->phiargs
[te1
->dest_idx
],
4392 vp2
->phiargs
[te2
->dest_idx
])
4393 || ! expressions_equal_p (vp1
->phiargs
[fe1
->dest_idx
],
4394 vp2
->phiargs
[fe2
->dest_idx
]))
4405 /* If the PHI nodes do not have compatible types
4406 they are not the same. */
4407 if (!types_compatible_p (vp1
->type
, vp2
->type
))
4410 /* Any phi in the same block will have it's arguments in the
4411 same edge order, because of how we store phi nodes. */
4412 unsigned nargs
= EDGE_COUNT (vp1
->block
->preds
);
4413 for (unsigned i
= 0; i
< nargs
; ++i
)
4415 tree phi1op
= vp1
->phiargs
[i
];
4416 tree phi2op
= vp2
->phiargs
[i
];
4417 if (phi1op
== phi2op
)
4419 if (!expressions_equal_p (phi1op
, phi2op
))
4426 /* Lookup PHI in the current hash table, and return the resulting
4427 value number if it exists in the hash table. Return NULL_TREE if
4428 it does not exist in the hash table. */
4431 vn_phi_lookup (gimple
*phi
, bool backedges_varying_p
)
4434 struct vn_phi_s
*vp1
;
4438 vp1
= XALLOCAVAR (struct vn_phi_s
,
4439 sizeof (struct vn_phi_s
)
4440 + (gimple_phi_num_args (phi
) - 1) * sizeof (tree
));
4442 /* Canonicalize the SSA_NAME's to their value number. */
4443 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
4445 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
4446 if (TREE_CODE (def
) == SSA_NAME
4447 && (!backedges_varying_p
|| !(e
->flags
& EDGE_DFS_BACK
)))
4448 def
= SSA_VAL (def
);
4449 vp1
->phiargs
[e
->dest_idx
] = def
;
4451 vp1
->type
= TREE_TYPE (gimple_phi_result (phi
));
4452 vp1
->block
= gimple_bb (phi
);
4453 /* Extract values of the controlling condition. */
4454 vp1
->cclhs
= NULL_TREE
;
4455 vp1
->ccrhs
= NULL_TREE
;
4456 basic_block idom1
= get_immediate_dominator (CDI_DOMINATORS
, vp1
->block
);
4457 if (EDGE_COUNT (idom1
->succs
) == 2)
4458 if (gcond
*last1
= safe_dyn_cast
<gcond
*> (last_stmt (idom1
)))
4460 /* ??? We want to use SSA_VAL here. But possibly not
4462 vp1
->cclhs
= vn_valueize (gimple_cond_lhs (last1
));
4463 vp1
->ccrhs
= vn_valueize (gimple_cond_rhs (last1
));
4465 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
4466 slot
= valid_info
->phis
->find_slot_with_hash (vp1
, vp1
->hashcode
, NO_INSERT
);
4469 return (*slot
)->result
;
4472 /* Insert PHI into the current hash table with a value number of
4476 vn_phi_insert (gimple
*phi
, tree result
, bool backedges_varying_p
)
4479 vn_phi_t vp1
= (vn_phi_t
) obstack_alloc (&vn_tables_obstack
,
4481 + ((gimple_phi_num_args (phi
) - 1)
4486 /* Canonicalize the SSA_NAME's to their value number. */
4487 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
4489 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
4490 if (TREE_CODE (def
) == SSA_NAME
4491 && (!backedges_varying_p
|| !(e
->flags
& EDGE_DFS_BACK
)))
4492 def
= SSA_VAL (def
);
4493 vp1
->phiargs
[e
->dest_idx
] = def
;
4495 vp1
->value_id
= VN_INFO (result
)->value_id
;
4496 vp1
->type
= TREE_TYPE (gimple_phi_result (phi
));
4497 vp1
->block
= gimple_bb (phi
);
4498 /* Extract values of the controlling condition. */
4499 vp1
->cclhs
= NULL_TREE
;
4500 vp1
->ccrhs
= NULL_TREE
;
4501 basic_block idom1
= get_immediate_dominator (CDI_DOMINATORS
, vp1
->block
);
4502 if (EDGE_COUNT (idom1
->succs
) == 2)
4503 if (gcond
*last1
= safe_dyn_cast
<gcond
*> (last_stmt (idom1
)))
4505 /* ??? We want to use SSA_VAL here. But possibly not
4507 vp1
->cclhs
= vn_valueize (gimple_cond_lhs (last1
));
4508 vp1
->ccrhs
= vn_valueize (gimple_cond_rhs (last1
));
4510 vp1
->result
= result
;
4511 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
4513 slot
= valid_info
->phis
->find_slot_with_hash (vp1
, vp1
->hashcode
, INSERT
);
4514 gcc_assert (!*slot
);
4517 vp1
->next
= last_inserted_phi
;
4518 last_inserted_phi
= vp1
;
4523 /* Return true if BB1 is dominated by BB2 taking into account edges
4524 that are not executable. When ALLOW_BACK is false consider not
4525 executable backedges as executable. */
4528 dominated_by_p_w_unex (basic_block bb1
, basic_block bb2
, bool allow_back
)
4533 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
4536 /* Before iterating we'd like to know if there exists a
4537 (executable) path from bb2 to bb1 at all, if not we can
4538 directly return false. For now simply iterate once. */
4540 /* Iterate to the single executable bb1 predecessor. */
4541 if (EDGE_COUNT (bb1
->preds
) > 1)
4544 FOR_EACH_EDGE (e
, ei
, bb1
->preds
)
4545 if ((e
->flags
& EDGE_EXECUTABLE
)
4546 || (!allow_back
&& (e
->flags
& EDGE_DFS_BACK
)))
4559 /* Re-do the dominance check with changed bb1. */
4560 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
4565 /* Iterate to the single executable bb2 successor. */
4567 FOR_EACH_EDGE (e
, ei
, bb2
->succs
)
4568 if ((e
->flags
& EDGE_EXECUTABLE
)
4569 || (!allow_back
&& (e
->flags
& EDGE_DFS_BACK
)))
4580 /* Verify the reached block is only reached through succe.
4581 If there is only one edge we can spare us the dominator
4582 check and iterate directly. */
4583 if (EDGE_COUNT (succe
->dest
->preds
) > 1)
4585 FOR_EACH_EDGE (e
, ei
, succe
->dest
->preds
)
4587 && ((e
->flags
& EDGE_EXECUTABLE
)
4588 || (!allow_back
&& (e
->flags
& EDGE_DFS_BACK
))))
4598 /* Re-do the dominance check with changed bb2. */
4599 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
4604 /* We could now iterate updating bb1 / bb2. */
4608 /* Set the value number of FROM to TO, return true if it has changed
4612 set_ssa_val_to (tree from
, tree to
)
4614 vn_ssa_aux_t from_info
= VN_INFO (from
);
4615 tree currval
= from_info
->valnum
; // SSA_VAL (from)
4616 poly_int64 toff
, coff
;
4617 bool curr_undefined
= false;
4618 bool curr_invariant
= false;
4620 /* The only thing we allow as value numbers are ssa_names
4621 and invariants. So assert that here. We don't allow VN_TOP
4622 as visiting a stmt should produce a value-number other than
4624 ??? Still VN_TOP can happen for unreachable code, so force
4625 it to varying in that case. Not all code is prepared to
4626 get VN_TOP on valueization. */
4629 /* ??? When iterating and visiting PHI <undef, backedge-value>
4630 for the first time we rightfully get VN_TOP and we need to
4631 preserve that to optimize for example gcc.dg/tree-ssa/ssa-sccvn-2.c.
4632 With SCCVN we were simply lucky we iterated the other PHI
4633 cycles first and thus visited the backedge-value DEF. */
4634 if (currval
== VN_TOP
)
4636 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4637 fprintf (dump_file
, "Forcing value number to varying on "
4638 "receiving VN_TOP\n");
4642 gcc_checking_assert (to
!= NULL_TREE
4643 && ((TREE_CODE (to
) == SSA_NAME
4644 && (to
== from
|| SSA_VAL (to
) == to
))
4645 || is_gimple_min_invariant (to
)));
4649 if (currval
== from
)
4651 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4653 fprintf (dump_file
, "Not changing value number of ");
4654 print_generic_expr (dump_file
, from
);
4655 fprintf (dump_file
, " from VARYING to ");
4656 print_generic_expr (dump_file
, to
);
4657 fprintf (dump_file
, "\n");
4661 curr_invariant
= is_gimple_min_invariant (currval
);
4662 curr_undefined
= (TREE_CODE (currval
) == SSA_NAME
4663 && ssa_undefined_value_p (currval
, false));
4664 if (currval
!= VN_TOP
4667 && is_gimple_min_invariant (to
))
4669 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4671 fprintf (dump_file
, "Forcing VARYING instead of changing "
4672 "value number of ");
4673 print_generic_expr (dump_file
, from
);
4674 fprintf (dump_file
, " from ");
4675 print_generic_expr (dump_file
, currval
);
4676 fprintf (dump_file
, " (non-constant) to ");
4677 print_generic_expr (dump_file
, to
);
4678 fprintf (dump_file
, " (constant)\n");
4682 else if (currval
!= VN_TOP
4684 && TREE_CODE (to
) == SSA_NAME
4685 && ssa_undefined_value_p (to
, false))
4687 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4689 fprintf (dump_file
, "Forcing VARYING instead of changing "
4690 "value number of ");
4691 print_generic_expr (dump_file
, from
);
4692 fprintf (dump_file
, " from ");
4693 print_generic_expr (dump_file
, currval
);
4694 fprintf (dump_file
, " (non-undefined) to ");
4695 print_generic_expr (dump_file
, to
);
4696 fprintf (dump_file
, " (undefined)\n");
4700 else if (TREE_CODE (to
) == SSA_NAME
4701 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to
))
4706 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4708 fprintf (dump_file
, "Setting value number of ");
4709 print_generic_expr (dump_file
, from
);
4710 fprintf (dump_file
, " to ");
4711 print_generic_expr (dump_file
, to
);
4715 && !operand_equal_p (currval
, to
, 0)
4716 /* Different undefined SSA names are not actually different. See
4717 PR82320 for a testcase were we'd otherwise not terminate iteration. */
4719 && TREE_CODE (to
) == SSA_NAME
4720 && ssa_undefined_value_p (to
, false))
4721 /* ??? For addresses involving volatile objects or types operand_equal_p
4722 does not reliably detect ADDR_EXPRs as equal. We know we are only
4723 getting invariant gimple addresses here, so can use
4724 get_addr_base_and_unit_offset to do this comparison. */
4725 && !(TREE_CODE (currval
) == ADDR_EXPR
4726 && TREE_CODE (to
) == ADDR_EXPR
4727 && (get_addr_base_and_unit_offset (TREE_OPERAND (currval
, 0), &coff
)
4728 == get_addr_base_and_unit_offset (TREE_OPERAND (to
, 0), &toff
))
4729 && known_eq (coff
, toff
)))
4732 && currval
!= VN_TOP
4734 /* We do not want to allow lattice transitions from one value
4735 to another since that may lead to not terminating iteration
4736 (see PR95049). Since there's no convenient way to check
4737 for the allowed transition of VAL -> PHI (loop entry value,
4738 same on two PHIs, to same PHI result) we restrict the check
4741 && is_gimple_min_invariant (to
))
4743 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4744 fprintf (dump_file
, " forced VARYING");
4747 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4748 fprintf (dump_file
, " (changed)\n");
4749 from_info
->valnum
= to
;
4752 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4753 fprintf (dump_file
, "\n");
4757 /* Set all definitions in STMT to value number to themselves.
4758 Return true if a value number changed. */
4761 defs_to_varying (gimple
*stmt
)
4763 bool changed
= false;
4767 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
4769 tree def
= DEF_FROM_PTR (defp
);
4770 changed
|= set_ssa_val_to (def
, def
);
4775 /* Visit a copy between LHS and RHS, return true if the value number
4779 visit_copy (tree lhs
, tree rhs
)
4782 rhs
= SSA_VAL (rhs
);
4784 return set_ssa_val_to (lhs
, rhs
);
4787 /* Lookup a value for OP in type WIDE_TYPE where the value in type of OP
4791 valueized_wider_op (tree wide_type
, tree op
, bool allow_truncate
)
4793 if (TREE_CODE (op
) == SSA_NAME
)
4794 op
= vn_valueize (op
);
4796 /* Either we have the op widened available. */
4799 tree tem
= vn_nary_op_lookup_pieces (1, NOP_EXPR
,
4800 wide_type
, ops
, NULL
);
4804 /* Or the op is truncated from some existing value. */
4805 if (allow_truncate
&& TREE_CODE (op
) == SSA_NAME
)
4807 gimple
*def
= SSA_NAME_DEF_STMT (op
);
4808 if (is_gimple_assign (def
)
4809 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def
)))
4811 tem
= gimple_assign_rhs1 (def
);
4812 if (useless_type_conversion_p (wide_type
, TREE_TYPE (tem
)))
4814 if (TREE_CODE (tem
) == SSA_NAME
)
4815 tem
= vn_valueize (tem
);
4821 /* For constants simply extend it. */
4822 if (TREE_CODE (op
) == INTEGER_CST
)
4823 return wide_int_to_tree (wide_type
, wi::to_wide (op
));
4828 /* Visit a nary operator RHS, value number it, and return true if the
4829 value number of LHS has changed as a result. */
4832 visit_nary_op (tree lhs
, gassign
*stmt
)
4834 vn_nary_op_t vnresult
;
4835 tree result
= vn_nary_op_lookup_stmt (stmt
, &vnresult
);
4836 if (! result
&& vnresult
)
4837 result
= vn_nary_op_get_predicated_value (vnresult
, gimple_bb (stmt
));
4839 return set_ssa_val_to (lhs
, result
);
4841 /* Do some special pattern matching for redundancies of operations
4842 in different types. */
4843 enum tree_code code
= gimple_assign_rhs_code (stmt
);
4844 tree type
= TREE_TYPE (lhs
);
4845 tree rhs1
= gimple_assign_rhs1 (stmt
);
4849 /* Match arithmetic done in a different type where we can easily
4850 substitute the result from some earlier sign-changed or widened
4852 if (INTEGRAL_TYPE_P (type
)
4853 && TREE_CODE (rhs1
) == SSA_NAME
4854 /* We only handle sign-changes, zero-extension -> & mask or
4855 sign-extension if we know the inner operation doesn't
4857 && (((TYPE_UNSIGNED (TREE_TYPE (rhs1
))
4858 || (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
4859 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (rhs1
))))
4860 && TYPE_PRECISION (type
) > TYPE_PRECISION (TREE_TYPE (rhs1
)))
4861 || TYPE_PRECISION (type
) == TYPE_PRECISION (TREE_TYPE (rhs1
))))
4863 gassign
*def
= dyn_cast
<gassign
*> (SSA_NAME_DEF_STMT (rhs1
));
4865 && (gimple_assign_rhs_code (def
) == PLUS_EXPR
4866 || gimple_assign_rhs_code (def
) == MINUS_EXPR
4867 || gimple_assign_rhs_code (def
) == MULT_EXPR
))
4870 /* When requiring a sign-extension we cannot model a
4871 previous truncation with a single op so don't bother. */
4872 bool allow_truncate
= TYPE_UNSIGNED (TREE_TYPE (rhs1
));
4873 /* Either we have the op widened available. */
4874 ops
[0] = valueized_wider_op (type
, gimple_assign_rhs1 (def
),
4877 ops
[1] = valueized_wider_op (type
, gimple_assign_rhs2 (def
),
4879 if (ops
[0] && ops
[1])
4881 ops
[0] = vn_nary_op_lookup_pieces
4882 (2, gimple_assign_rhs_code (def
), type
, ops
, NULL
);
4883 /* We have wider operation available. */
4885 /* If the leader is a wrapping operation we can
4886 insert it for code hoisting w/o introducing
4887 undefined overflow. If it is not it has to
4888 be available. See PR86554. */
4889 && (TYPE_OVERFLOW_WRAPS (TREE_TYPE (ops
[0]))
4890 || (rpo_avail
&& vn_context_bb
4891 && rpo_avail
->eliminate_avail (vn_context_bb
,
4894 unsigned lhs_prec
= TYPE_PRECISION (type
);
4895 unsigned rhs_prec
= TYPE_PRECISION (TREE_TYPE (rhs1
));
4896 if (lhs_prec
== rhs_prec
4897 || (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
4898 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (rhs1
))))
4900 gimple_match_op
match_op (gimple_match_cond::UNCOND
,
4901 NOP_EXPR
, type
, ops
[0]);
4902 result
= vn_nary_build_or_lookup (&match_op
);
4905 bool changed
= set_ssa_val_to (lhs
, result
);
4906 vn_nary_op_insert_stmt (stmt
, result
);
4912 tree mask
= wide_int_to_tree
4913 (type
, wi::mask (rhs_prec
, false, lhs_prec
));
4914 gimple_match_op
match_op (gimple_match_cond::UNCOND
,
4918 result
= vn_nary_build_or_lookup (&match_op
);
4921 bool changed
= set_ssa_val_to (lhs
, result
);
4922 vn_nary_op_insert_stmt (stmt
, result
);
4932 if (INTEGRAL_TYPE_P (type
)
4933 && TREE_CODE (rhs1
) == SSA_NAME
4934 && TREE_CODE (gimple_assign_rhs2 (stmt
)) == INTEGER_CST
4935 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
)
4936 && default_vn_walk_kind
!= VN_NOWALK
4938 && BITS_PER_UNIT
== 8
4939 && BYTES_BIG_ENDIAN
== WORDS_BIG_ENDIAN
4940 && !integer_all_onesp (gimple_assign_rhs2 (stmt
))
4941 && !integer_zerop (gimple_assign_rhs2 (stmt
)))
4943 gassign
*ass
= dyn_cast
<gassign
*> (SSA_NAME_DEF_STMT (rhs1
));
4945 && !gimple_has_volatile_ops (ass
)
4946 && vn_get_stmt_kind (ass
) == VN_REFERENCE
)
4948 tree last_vuse
= gimple_vuse (ass
);
4949 tree op
= gimple_assign_rhs1 (ass
);
4950 tree result
= vn_reference_lookup (op
, gimple_vuse (ass
),
4951 default_vn_walk_kind
,
4952 NULL
, true, &last_vuse
,
4953 gimple_assign_rhs2 (stmt
));
4955 && useless_type_conversion_p (TREE_TYPE (result
),
4957 return set_ssa_val_to (lhs
, result
);
4961 case TRUNC_DIV_EXPR
:
4962 if (TYPE_UNSIGNED (type
))
4967 /* Match up ([-]a){/,*}([-])b with v=a{/,*}b, replacing it with -v. */
4968 if (! HONOR_SIGN_DEPENDENT_ROUNDING (type
))
4972 rhs
[1] = gimple_assign_rhs2 (stmt
);
4973 for (unsigned i
= 0; i
<= 1; ++i
)
4975 unsigned j
= i
== 0 ? 1 : 0;
4977 gimple_match_op
match_op (gimple_match_cond::UNCOND
,
4978 NEGATE_EXPR
, type
, rhs
[i
]);
4979 ops
[i
] = vn_nary_build_or_lookup_1 (&match_op
, false);
4982 && (ops
[0] = vn_nary_op_lookup_pieces (2, code
,
4985 gimple_match_op
match_op (gimple_match_cond::UNCOND
,
4986 NEGATE_EXPR
, type
, ops
[0]);
4987 result
= vn_nary_build_or_lookup (&match_op
);
4990 bool changed
= set_ssa_val_to (lhs
, result
);
4991 vn_nary_op_insert_stmt (stmt
, result
);
5002 bool changed
= set_ssa_val_to (lhs
, lhs
);
5003 vn_nary_op_insert_stmt (stmt
, lhs
);
5007 /* Visit a call STMT storing into LHS. Return true if the value number
5008 of the LHS has changed as a result. */
5011 visit_reference_op_call (tree lhs
, gcall
*stmt
)
5013 bool changed
= false;
5014 struct vn_reference_s vr1
;
5015 vn_reference_t vnresult
= NULL
;
5016 tree vdef
= gimple_vdef (stmt
);
5018 /* Non-ssa lhs is handled in copy_reference_ops_from_call. */
5019 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
5022 vn_reference_lookup_call (stmt
, &vnresult
, &vr1
);
5025 if (vnresult
->result_vdef
&& vdef
)
5026 changed
|= set_ssa_val_to (vdef
, vnresult
->result_vdef
);
5028 /* If the call was discovered to be pure or const reflect
5029 that as far as possible. */
5030 changed
|= set_ssa_val_to (vdef
, vuse_ssa_val (gimple_vuse (stmt
)));
5032 if (!vnresult
->result
&& lhs
)
5033 vnresult
->result
= lhs
;
5035 if (vnresult
->result
&& lhs
)
5036 changed
|= set_ssa_val_to (lhs
, vnresult
->result
);
5041 vn_reference_s
**slot
;
5042 tree vdef_val
= vdef
;
5045 /* If we value numbered an indirect functions function to
5046 one not clobbering memory value number its VDEF to its
5048 tree fn
= gimple_call_fn (stmt
);
5049 if (fn
&& TREE_CODE (fn
) == SSA_NAME
)
5052 if (TREE_CODE (fn
) == ADDR_EXPR
5053 && TREE_CODE (TREE_OPERAND (fn
, 0)) == FUNCTION_DECL
5054 && (flags_from_decl_or_type (TREE_OPERAND (fn
, 0))
5055 & (ECF_CONST
| ECF_PURE
)))
5056 vdef_val
= vuse_ssa_val (gimple_vuse (stmt
));
5058 changed
|= set_ssa_val_to (vdef
, vdef_val
);
5061 changed
|= set_ssa_val_to (lhs
, lhs
);
5062 vr2
= XOBNEW (&vn_tables_obstack
, vn_reference_s
);
5063 vr2
->vuse
= vr1
.vuse
;
5064 /* As we are not walking the virtual operand chain we know the
5065 shared_lookup_references are still original so we can re-use
5067 vr2
->operands
= vr1
.operands
.copy ();
5068 vr2
->type
= vr1
.type
;
5069 vr2
->punned
= vr1
.punned
;
5071 vr2
->base_set
= vr1
.base_set
;
5072 vr2
->hashcode
= vr1
.hashcode
;
5074 vr2
->result_vdef
= vdef_val
;
5076 slot
= valid_info
->references
->find_slot_with_hash (vr2
, vr2
->hashcode
,
5078 gcc_assert (!*slot
);
5080 vr2
->next
= last_inserted_ref
;
5081 last_inserted_ref
= vr2
;
5087 /* Visit a load from a reference operator RHS, part of STMT, value number it,
5088 and return true if the value number of the LHS has changed as a result. */
5091 visit_reference_op_load (tree lhs
, tree op
, gimple
*stmt
)
5093 bool changed
= false;
5098 last_vuse
= gimple_vuse (stmt
);
5099 result
= vn_reference_lookup (op
, gimple_vuse (stmt
),
5100 default_vn_walk_kind
, &res
, true, &last_vuse
);
5102 /* We handle type-punning through unions by value-numbering based
5103 on offset and size of the access. Be prepared to handle a
5104 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
5106 && !useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (op
)))
5108 /* Avoid the type punning in case the result mode has padding where
5109 the op we lookup has not. */
5110 if (maybe_lt (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (result
))),
5111 GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (op
)))))
5115 /* We will be setting the value number of lhs to the value number
5116 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
5117 So first simplify and lookup this expression to see if it
5118 is already available. */
5119 gimple_match_op
res_op (gimple_match_cond::UNCOND
,
5120 VIEW_CONVERT_EXPR
, TREE_TYPE (op
), result
);
5121 result
= vn_nary_build_or_lookup (&res_op
);
5123 && TREE_CODE (result
) == SSA_NAME
5124 && VN_INFO (result
)->needs_insertion
)
5125 /* Track whether this is the canonical expression for different
5126 typed loads. We use that as a stopgap measure for code
5127 hoisting when dealing with floating point loads. */
5131 /* When building the conversion fails avoid inserting the reference
5134 return set_ssa_val_to (lhs
, lhs
);
5138 changed
= set_ssa_val_to (lhs
, result
);
5141 changed
= set_ssa_val_to (lhs
, lhs
);
5142 vn_reference_insert (op
, lhs
, last_vuse
, NULL_TREE
);
5149 /* Visit a store to a reference operator LHS, part of STMT, value number it,
5150 and return true if the value number of the LHS has changed as a result. */
5153 visit_reference_op_store (tree lhs
, tree op
, gimple
*stmt
)
5155 bool changed
= false;
5156 vn_reference_t vnresult
= NULL
;
5158 bool resultsame
= false;
5159 tree vuse
= gimple_vuse (stmt
);
5160 tree vdef
= gimple_vdef (stmt
);
5162 if (TREE_CODE (op
) == SSA_NAME
)
5165 /* First we want to lookup using the *vuses* from the store and see
5166 if there the last store to this location with the same address
5169 The vuses represent the memory state before the store. If the
5170 memory state, address, and value of the store is the same as the
5171 last store to this location, then this store will produce the
5172 same memory state as that store.
5174 In this case the vdef versions for this store are value numbered to those
5175 vuse versions, since they represent the same memory state after
5178 Otherwise, the vdefs for the store are used when inserting into
5179 the table, since the store generates a new memory state. */
5181 vn_reference_lookup (lhs
, vuse
, VN_NOWALK
, &vnresult
, false);
5183 && vnresult
->result
)
5185 tree result
= vnresult
->result
;
5186 gcc_checking_assert (TREE_CODE (result
) != SSA_NAME
5187 || result
== SSA_VAL (result
));
5188 resultsame
= expressions_equal_p (result
, op
);
5191 /* If the TBAA state isn't compatible for downstream reads
5192 we cannot value-number the VDEFs the same. */
5194 ao_ref_init (&lhs_ref
, lhs
);
5195 alias_set_type set
= ao_ref_alias_set (&lhs_ref
);
5196 alias_set_type base_set
= ao_ref_base_alias_set (&lhs_ref
);
5197 if ((vnresult
->set
!= set
5198 && ! alias_set_subset_of (set
, vnresult
->set
))
5199 || (vnresult
->base_set
!= base_set
5200 && ! alias_set_subset_of (base_set
, vnresult
->base_set
)))
5207 /* Only perform the following when being called from PRE
5208 which embeds tail merging. */
5209 if (default_vn_walk_kind
== VN_WALK
)
5211 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
5212 vn_reference_lookup (assign
, vuse
, VN_NOWALK
, &vnresult
, false);
5215 VN_INFO (vdef
)->visited
= true;
5216 return set_ssa_val_to (vdef
, vnresult
->result_vdef
);
5220 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5222 fprintf (dump_file
, "No store match\n");
5223 fprintf (dump_file
, "Value numbering store ");
5224 print_generic_expr (dump_file
, lhs
);
5225 fprintf (dump_file
, " to ");
5226 print_generic_expr (dump_file
, op
);
5227 fprintf (dump_file
, "\n");
5229 /* Have to set value numbers before insert, since insert is
5230 going to valueize the references in-place. */
5232 changed
|= set_ssa_val_to (vdef
, vdef
);
5234 /* Do not insert structure copies into the tables. */
5235 if (is_gimple_min_invariant (op
)
5236 || is_gimple_reg (op
))
5237 vn_reference_insert (lhs
, op
, vdef
, NULL
);
5239 /* Only perform the following when being called from PRE
5240 which embeds tail merging. */
5241 if (default_vn_walk_kind
== VN_WALK
)
5243 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
5244 vn_reference_insert (assign
, lhs
, vuse
, vdef
);
5249 /* We had a match, so value number the vdef to have the value
5250 number of the vuse it came from. */
5252 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5253 fprintf (dump_file
, "Store matched earlier value, "
5254 "value numbering store vdefs to matching vuses.\n");
5256 changed
|= set_ssa_val_to (vdef
, SSA_VAL (vuse
));
5262 /* Visit and value number PHI, return true if the value number
5263 changed. When BACKEDGES_VARYING_P is true then assume all
5264 backedge values are varying. When INSERTED is not NULL then
5265 this is just a ahead query for a possible iteration, set INSERTED
5266 to true if we'd insert into the hashtable. */
5269 visit_phi (gimple
*phi
, bool *inserted
, bool backedges_varying_p
)
5271 tree result
, sameval
= VN_TOP
, seen_undef
= NULL_TREE
;
5272 tree backedge_val
= NULL_TREE
;
5273 bool seen_non_backedge
= false;
5274 tree sameval_base
= NULL_TREE
;
5275 poly_int64 soff
, doff
;
5276 unsigned n_executable
= 0;
5280 /* TODO: We could check for this in initialization, and replace this
5281 with a gcc_assert. */
5282 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
5283 return set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
5285 /* We track whether a PHI was CSEd to to avoid excessive iterations
5286 that would be necessary only because the PHI changed arguments
5289 gimple_set_plf (phi
, GF_PLF_1
, false);
5291 /* See if all non-TOP arguments have the same value. TOP is
5292 equivalent to everything, so we can ignore it. */
5293 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
5294 if (e
->flags
& EDGE_EXECUTABLE
)
5296 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
5298 if (def
== PHI_RESULT (phi
))
5301 if (TREE_CODE (def
) == SSA_NAME
)
5303 if (!backedges_varying_p
|| !(e
->flags
& EDGE_DFS_BACK
))
5304 def
= SSA_VAL (def
);
5305 if (e
->flags
& EDGE_DFS_BACK
)
5308 if (!(e
->flags
& EDGE_DFS_BACK
))
5309 seen_non_backedge
= true;
5312 /* Ignore undefined defs for sameval but record one. */
5313 else if (TREE_CODE (def
) == SSA_NAME
5314 && ! virtual_operand_p (def
)
5315 && ssa_undefined_value_p (def
, false))
5317 else if (sameval
== VN_TOP
)
5319 else if (!expressions_equal_p (def
, sameval
))
5321 /* We know we're arriving only with invariant addresses here,
5322 try harder comparing them. We can do some caching here
5323 which we cannot do in expressions_equal_p. */
5324 if (TREE_CODE (def
) == ADDR_EXPR
5325 && TREE_CODE (sameval
) == ADDR_EXPR
5326 && sameval_base
!= (void *)-1)
5329 sameval_base
= get_addr_base_and_unit_offset
5330 (TREE_OPERAND (sameval
, 0), &soff
);
5332 sameval_base
= (tree
)(void *)-1;
5333 else if ((get_addr_base_and_unit_offset
5334 (TREE_OPERAND (def
, 0), &doff
) == sameval_base
)
5335 && known_eq (soff
, doff
))
5338 sameval
= NULL_TREE
;
5343 /* If the value we want to use is flowing over the backedge and we
5344 should take it as VARYING but it has a non-VARYING value drop to
5346 If we value-number a virtual operand never value-number to the
5347 value from the backedge as that confuses the alias-walking code.
5348 See gcc.dg/torture/pr87176.c. If the value is the same on a
5349 non-backedge everything is OK though. */
5352 && !seen_non_backedge
5353 && TREE_CODE (backedge_val
) == SSA_NAME
5354 && sameval
== backedge_val
5355 && (SSA_NAME_IS_VIRTUAL_OPERAND (backedge_val
)
5356 || SSA_VAL (backedge_val
) != backedge_val
))
5357 /* Do not value-number a virtual operand to sth not visited though
5358 given that allows us to escape a region in alias walking. */
5360 && TREE_CODE (sameval
) == SSA_NAME
5361 && !SSA_NAME_IS_DEFAULT_DEF (sameval
)
5362 && SSA_NAME_IS_VIRTUAL_OPERAND (sameval
)
5363 && (SSA_VAL (sameval
, &visited_p
), !visited_p
)))
5364 /* Note this just drops to VARYING without inserting the PHI into
5366 result
= PHI_RESULT (phi
);
5367 /* If none of the edges was executable keep the value-number at VN_TOP,
5368 if only a single edge is exectuable use its value. */
5369 else if (n_executable
<= 1)
5370 result
= seen_undef
? seen_undef
: sameval
;
5371 /* If we saw only undefined values and VN_TOP use one of the
5372 undefined values. */
5373 else if (sameval
== VN_TOP
)
5374 result
= seen_undef
? seen_undef
: sameval
;
5375 /* First see if it is equivalent to a phi node in this block. We prefer
5376 this as it allows IV elimination - see PRs 66502 and 67167. */
5377 else if ((result
= vn_phi_lookup (phi
, backedges_varying_p
)))
5380 && TREE_CODE (result
) == SSA_NAME
5381 && gimple_code (SSA_NAME_DEF_STMT (result
)) == GIMPLE_PHI
)
5383 gimple_set_plf (SSA_NAME_DEF_STMT (result
), GF_PLF_1
, true);
5384 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5386 fprintf (dump_file
, "Marking CSEd to PHI node ");
5387 print_gimple_expr (dump_file
, SSA_NAME_DEF_STMT (result
),
5389 fprintf (dump_file
, "\n");
5393 /* If all values are the same use that, unless we've seen undefined
5394 values as well and the value isn't constant.
5395 CCP/copyprop have the same restriction to not remove uninit warnings. */
5397 && (! seen_undef
|| is_gimple_min_invariant (sameval
)))
5401 result
= PHI_RESULT (phi
);
5402 /* Only insert PHIs that are varying, for constant value numbers
5403 we mess up equivalences otherwise as we are only comparing
5404 the immediate controlling predicates. */
5405 vn_phi_insert (phi
, result
, backedges_varying_p
);
5410 return set_ssa_val_to (PHI_RESULT (phi
), result
);
5413 /* Try to simplify RHS using equivalences and constant folding. */
5416 try_to_simplify (gassign
*stmt
)
5418 enum tree_code code
= gimple_assign_rhs_code (stmt
);
5421 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
5422 in this case, there is no point in doing extra work. */
5423 if (code
== SSA_NAME
)
5426 /* First try constant folding based on our current lattice. */
5427 mprts_hook
= vn_lookup_simplify_result
;
5428 tem
= gimple_fold_stmt_to_constant_1 (stmt
, vn_valueize
, vn_valueize
);
5431 && (TREE_CODE (tem
) == SSA_NAME
5432 || is_gimple_min_invariant (tem
)))
5438 /* Visit and value number STMT, return true if the value number
5442 visit_stmt (gimple
*stmt
, bool backedges_varying_p
= false)
5444 bool changed
= false;
5446 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5448 fprintf (dump_file
, "Value numbering stmt = ");
5449 print_gimple_stmt (dump_file
, stmt
, 0);
5452 if (gimple_code (stmt
) == GIMPLE_PHI
)
5453 changed
= visit_phi (stmt
, NULL
, backedges_varying_p
);
5454 else if (gimple_has_volatile_ops (stmt
))
5455 changed
= defs_to_varying (stmt
);
5456 else if (gassign
*ass
= dyn_cast
<gassign
*> (stmt
))
5458 enum tree_code code
= gimple_assign_rhs_code (ass
);
5459 tree lhs
= gimple_assign_lhs (ass
);
5460 tree rhs1
= gimple_assign_rhs1 (ass
);
5463 /* Shortcut for copies. Simplifying copies is pointless,
5464 since we copy the expression and value they represent. */
5465 if (code
== SSA_NAME
5466 && TREE_CODE (lhs
) == SSA_NAME
)
5468 changed
= visit_copy (lhs
, rhs1
);
5471 simplified
= try_to_simplify (ass
);
5474 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5476 fprintf (dump_file
, "RHS ");
5477 print_gimple_expr (dump_file
, ass
, 0);
5478 fprintf (dump_file
, " simplified to ");
5479 print_generic_expr (dump_file
, simplified
);
5480 fprintf (dump_file
, "\n");
5483 /* Setting value numbers to constants will occasionally
5484 screw up phi congruence because constants are not
5485 uniquely associated with a single ssa name that can be
5488 && is_gimple_min_invariant (simplified
)
5489 && TREE_CODE (lhs
) == SSA_NAME
)
5491 changed
= set_ssa_val_to (lhs
, simplified
);
5495 && TREE_CODE (simplified
) == SSA_NAME
5496 && TREE_CODE (lhs
) == SSA_NAME
)
5498 changed
= visit_copy (lhs
, simplified
);
5502 if ((TREE_CODE (lhs
) == SSA_NAME
5503 /* We can substitute SSA_NAMEs that are live over
5504 abnormal edges with their constant value. */
5505 && !(gimple_assign_copy_p (ass
)
5506 && is_gimple_min_invariant (rhs1
))
5508 && is_gimple_min_invariant (simplified
))
5509 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
5510 /* Stores or copies from SSA_NAMEs that are live over
5511 abnormal edges are a problem. */
5512 || (code
== SSA_NAME
5513 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
)))
5514 changed
= defs_to_varying (ass
);
5515 else if (REFERENCE_CLASS_P (lhs
)
5517 changed
= visit_reference_op_store (lhs
, rhs1
, ass
);
5518 else if (TREE_CODE (lhs
) == SSA_NAME
)
5520 if ((gimple_assign_copy_p (ass
)
5521 && is_gimple_min_invariant (rhs1
))
5523 && is_gimple_min_invariant (simplified
)))
5526 changed
= set_ssa_val_to (lhs
, simplified
);
5528 changed
= set_ssa_val_to (lhs
, rhs1
);
5532 /* Visit the original statement. */
5533 switch (vn_get_stmt_kind (ass
))
5536 changed
= visit_nary_op (lhs
, ass
);
5539 changed
= visit_reference_op_load (lhs
, rhs1
, ass
);
5542 changed
= defs_to_varying (ass
);
5548 changed
= defs_to_varying (ass
);
5550 else if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
5552 tree lhs
= gimple_call_lhs (call_stmt
);
5553 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
5555 /* Try constant folding based on our current lattice. */
5556 tree simplified
= gimple_fold_stmt_to_constant_1 (call_stmt
,
5560 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5562 fprintf (dump_file
, "call ");
5563 print_gimple_expr (dump_file
, call_stmt
, 0);
5564 fprintf (dump_file
, " simplified to ");
5565 print_generic_expr (dump_file
, simplified
);
5566 fprintf (dump_file
, "\n");
5569 /* Setting value numbers to constants will occasionally
5570 screw up phi congruence because constants are not
5571 uniquely associated with a single ssa name that can be
5574 && is_gimple_min_invariant (simplified
))
5576 changed
= set_ssa_val_to (lhs
, simplified
);
5577 if (gimple_vdef (call_stmt
))
5578 changed
|= set_ssa_val_to (gimple_vdef (call_stmt
),
5579 SSA_VAL (gimple_vuse (call_stmt
)));
5583 && TREE_CODE (simplified
) == SSA_NAME
)
5585 changed
= visit_copy (lhs
, simplified
);
5586 if (gimple_vdef (call_stmt
))
5587 changed
|= set_ssa_val_to (gimple_vdef (call_stmt
),
5588 SSA_VAL (gimple_vuse (call_stmt
)));
5591 else if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
5593 changed
= defs_to_varying (call_stmt
);
5598 /* Pick up flags from a devirtualization target. */
5599 tree fn
= gimple_call_fn (stmt
);
5600 int extra_fnflags
= 0;
5601 if (fn
&& TREE_CODE (fn
) == SSA_NAME
)
5604 if (TREE_CODE (fn
) == ADDR_EXPR
5605 && TREE_CODE (TREE_OPERAND (fn
, 0)) == FUNCTION_DECL
)
5606 extra_fnflags
= flags_from_decl_or_type (TREE_OPERAND (fn
, 0));
5608 if (!gimple_call_internal_p (call_stmt
)
5609 && (/* Calls to the same function with the same vuse
5610 and the same operands do not necessarily return the same
5611 value, unless they're pure or const. */
5612 ((gimple_call_flags (call_stmt
) | extra_fnflags
)
5613 & (ECF_PURE
| ECF_CONST
))
5614 /* If calls have a vdef, subsequent calls won't have
5615 the same incoming vuse. So, if 2 calls with vdef have the
5616 same vuse, we know they're not subsequent.
5617 We can value number 2 calls to the same function with the
5618 same vuse and the same operands which are not subsequent
5619 the same, because there is no code in the program that can
5620 compare the 2 values... */
5621 || (gimple_vdef (call_stmt
)
5622 /* ... unless the call returns a pointer which does
5623 not alias with anything else. In which case the
5624 information that the values are distinct are encoded
5626 && !(gimple_call_return_flags (call_stmt
) & ERF_NOALIAS
)
5627 /* Only perform the following when being called from PRE
5628 which embeds tail merging. */
5629 && default_vn_walk_kind
== VN_WALK
)))
5630 changed
= visit_reference_op_call (lhs
, call_stmt
);
5632 changed
= defs_to_varying (call_stmt
);
5635 changed
= defs_to_varying (stmt
);
5641 /* Allocate a value number table. */
5644 allocate_vn_table (vn_tables_t table
, unsigned size
)
5646 table
->phis
= new vn_phi_table_type (size
);
5647 table
->nary
= new vn_nary_op_table_type (size
);
5648 table
->references
= new vn_reference_table_type (size
);
5651 /* Free a value number table. */
5654 free_vn_table (vn_tables_t table
)
5656 /* Walk over elements and release vectors. */
5657 vn_reference_iterator_type hir
;
5659 FOR_EACH_HASH_TABLE_ELEMENT (*table
->references
, vr
, vn_reference_t
, hir
)
5660 vr
->operands
.release ();
5665 delete table
->references
;
5666 table
->references
= NULL
;
5669 /* Set *ID according to RESULT. */
5672 set_value_id_for_result (tree result
, unsigned int *id
)
5674 if (result
&& TREE_CODE (result
) == SSA_NAME
)
5675 *id
= VN_INFO (result
)->value_id
;
5676 else if (result
&& is_gimple_min_invariant (result
))
5677 *id
= get_or_alloc_constant_value_id (result
);
5679 *id
= get_next_value_id ();
5682 /* Set the value ids in the valid hash tables. */
5685 set_hashtable_value_ids (void)
5687 vn_nary_op_iterator_type hin
;
5688 vn_phi_iterator_type hip
;
5689 vn_reference_iterator_type hir
;
5694 /* Now set the value ids of the things we had put in the hash
5697 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->nary
, vno
, vn_nary_op_t
, hin
)
5698 if (! vno
->predicated_values
)
5699 set_value_id_for_result (vno
->u
.result
, &vno
->value_id
);
5701 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->phis
, vp
, vn_phi_t
, hip
)
5702 set_value_id_for_result (vp
->result
, &vp
->value_id
);
5704 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->references
, vr
, vn_reference_t
,
5706 set_value_id_for_result (vr
->result
, &vr
->value_id
);
5709 /* Return the maximum value id we have ever seen. */
5712 get_max_value_id (void)
5714 return next_value_id
;
5717 /* Return the maximum constant value id we have ever seen. */
5720 get_max_constant_value_id (void)
5722 return -next_constant_value_id
;
5725 /* Return the next unique value id. */
5728 get_next_value_id (void)
5730 gcc_checking_assert ((int)next_value_id
> 0);
5731 return next_value_id
++;
5734 /* Return the next unique value id for constants. */
5737 get_next_constant_value_id (void)
5739 gcc_checking_assert (next_constant_value_id
< 0);
5740 return next_constant_value_id
--;
5744 /* Compare two expressions E1 and E2 and return true if they are equal. */
5747 expressions_equal_p (tree e1
, tree e2
)
5749 /* The obvious case. */
5753 /* If either one is VN_TOP consider them equal. */
5754 if (e1
== VN_TOP
|| e2
== VN_TOP
)
5757 /* SSA_NAME compare pointer equal. */
5758 if (TREE_CODE (e1
) == SSA_NAME
|| TREE_CODE (e2
) == SSA_NAME
)
5761 /* Now perform the actual comparison. */
5762 if (TREE_CODE (e1
) == TREE_CODE (e2
)
5763 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
5770 /* Return true if the nary operation NARY may trap. This is a copy
5771 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
5774 vn_nary_may_trap (vn_nary_op_t nary
)
5777 tree rhs2
= NULL_TREE
;
5778 bool honor_nans
= false;
5779 bool honor_snans
= false;
5780 bool fp_operation
= false;
5781 bool honor_trapv
= false;
5785 if (TREE_CODE_CLASS (nary
->opcode
) == tcc_comparison
5786 || TREE_CODE_CLASS (nary
->opcode
) == tcc_unary
5787 || TREE_CODE_CLASS (nary
->opcode
) == tcc_binary
)
5790 fp_operation
= FLOAT_TYPE_P (type
);
5793 honor_nans
= flag_trapping_math
&& !flag_finite_math_only
;
5794 honor_snans
= flag_signaling_nans
!= 0;
5796 else if (INTEGRAL_TYPE_P (type
) && TYPE_OVERFLOW_TRAPS (type
))
5799 if (nary
->length
>= 2)
5801 ret
= operation_could_trap_helper_p (nary
->opcode
, fp_operation
,
5802 honor_trapv
, honor_nans
, honor_snans
,
5807 for (i
= 0; i
< nary
->length
; ++i
)
5808 if (tree_could_trap_p (nary
->op
[i
]))
5814 /* Return true if the reference operation REF may trap. */
5817 vn_reference_may_trap (vn_reference_t ref
)
5819 switch (ref
->operands
[0].opcode
)
5823 /* We do not handle calls. */
5825 /* And toplevel address computations never trap. */
5830 vn_reference_op_t op
;
5832 FOR_EACH_VEC_ELT (ref
->operands
, i
, op
)
5836 case WITH_SIZE_EXPR
:
5837 case TARGET_MEM_REF
:
5838 /* Always variable. */
5841 if (op
->op1
&& TREE_CODE (op
->op1
) == SSA_NAME
)
5844 case ARRAY_RANGE_REF
:
5846 if (TREE_CODE (op
->op0
) == SSA_NAME
)
5850 /* Nothing interesting in itself, the base is separate. */
5852 /* The following are the address bases. */
5857 return tree_could_trap_p (TREE_OPERAND (op
->op0
, 0));
5865 eliminate_dom_walker::eliminate_dom_walker (cdi_direction direction
,
5866 bitmap inserted_exprs_
)
5867 : dom_walker (direction
), do_pre (inserted_exprs_
!= NULL
),
5868 el_todo (0), eliminations (0), insertions (0),
5869 inserted_exprs (inserted_exprs_
)
5871 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
5872 need_ab_cleanup
= BITMAP_ALLOC (NULL
);
5875 eliminate_dom_walker::~eliminate_dom_walker ()
5877 BITMAP_FREE (need_eh_cleanup
);
5878 BITMAP_FREE (need_ab_cleanup
);
5881 /* Return a leader for OP that is available at the current point of the
5882 eliminate domwalk. */
5885 eliminate_dom_walker::eliminate_avail (basic_block
, tree op
)
5887 tree valnum
= VN_INFO (op
)->valnum
;
5888 if (TREE_CODE (valnum
) == SSA_NAME
)
5890 if (SSA_NAME_IS_DEFAULT_DEF (valnum
))
5892 if (avail
.length () > SSA_NAME_VERSION (valnum
))
5893 return avail
[SSA_NAME_VERSION (valnum
)];
5895 else if (is_gimple_min_invariant (valnum
))
5900 /* At the current point of the eliminate domwalk make OP available. */
5903 eliminate_dom_walker::eliminate_push_avail (basic_block
, tree op
)
5905 tree valnum
= VN_INFO (op
)->valnum
;
5906 if (TREE_CODE (valnum
) == SSA_NAME
)
5908 if (avail
.length () <= SSA_NAME_VERSION (valnum
))
5909 avail
.safe_grow_cleared (SSA_NAME_VERSION (valnum
) + 1, true);
5911 if (avail
[SSA_NAME_VERSION (valnum
)])
5912 pushop
= avail
[SSA_NAME_VERSION (valnum
)];
5913 avail_stack
.safe_push (pushop
);
5914 avail
[SSA_NAME_VERSION (valnum
)] = op
;
5918 /* Insert the expression recorded by SCCVN for VAL at *GSI. Returns
5919 the leader for the expression if insertion was successful. */
5922 eliminate_dom_walker::eliminate_insert (basic_block bb
,
5923 gimple_stmt_iterator
*gsi
, tree val
)
5925 /* We can insert a sequence with a single assignment only. */
5926 gimple_seq stmts
= VN_INFO (val
)->expr
;
5927 if (!gimple_seq_singleton_p (stmts
))
5929 gassign
*stmt
= dyn_cast
<gassign
*> (gimple_seq_first_stmt (stmts
));
5931 || (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt
))
5932 && gimple_assign_rhs_code (stmt
) != VIEW_CONVERT_EXPR
5933 && gimple_assign_rhs_code (stmt
) != NEGATE_EXPR
5934 && gimple_assign_rhs_code (stmt
) != BIT_FIELD_REF
5935 && (gimple_assign_rhs_code (stmt
) != BIT_AND_EXPR
5936 || TREE_CODE (gimple_assign_rhs2 (stmt
)) != INTEGER_CST
)))
5939 tree op
= gimple_assign_rhs1 (stmt
);
5940 if (gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
5941 || gimple_assign_rhs_code (stmt
) == BIT_FIELD_REF
)
5942 op
= TREE_OPERAND (op
, 0);
5943 tree leader
= TREE_CODE (op
) == SSA_NAME
? eliminate_avail (bb
, op
) : op
;
5949 if (gimple_assign_rhs_code (stmt
) == BIT_FIELD_REF
)
5950 res
= gimple_build (&stmts
, BIT_FIELD_REF
,
5951 TREE_TYPE (val
), leader
,
5952 TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1),
5953 TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2));
5954 else if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
)
5955 res
= gimple_build (&stmts
, BIT_AND_EXPR
,
5956 TREE_TYPE (val
), leader
, gimple_assign_rhs2 (stmt
));
5958 res
= gimple_build (&stmts
, gimple_assign_rhs_code (stmt
),
5959 TREE_TYPE (val
), leader
);
5960 if (TREE_CODE (res
) != SSA_NAME
5961 || SSA_NAME_IS_DEFAULT_DEF (res
)
5962 || gimple_bb (SSA_NAME_DEF_STMT (res
)))
5964 gimple_seq_discard (stmts
);
5966 /* During propagation we have to treat SSA info conservatively
5967 and thus we can end up simplifying the inserted expression
5968 at elimination time to sth not defined in stmts. */
5969 /* But then this is a redundancy we failed to detect. Which means
5970 res now has two values. That doesn't play well with how
5971 we track availability here, so give up. */
5972 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5974 if (TREE_CODE (res
) == SSA_NAME
)
5975 res
= eliminate_avail (bb
, res
);
5978 fprintf (dump_file
, "Failed to insert expression for value ");
5979 print_generic_expr (dump_file
, val
);
5980 fprintf (dump_file
, " which is really fully redundant to ");
5981 print_generic_expr (dump_file
, res
);
5982 fprintf (dump_file
, "\n");
5990 gsi_insert_seq_before (gsi
, stmts
, GSI_SAME_STMT
);
5991 vn_ssa_aux_t vn_info
= VN_INFO (res
);
5992 vn_info
->valnum
= val
;
5993 vn_info
->visited
= true;
5997 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5999 fprintf (dump_file
, "Inserted ");
6000 print_gimple_stmt (dump_file
, SSA_NAME_DEF_STMT (res
), 0);
6007 eliminate_dom_walker::eliminate_stmt (basic_block b
, gimple_stmt_iterator
*gsi
)
6009 tree sprime
= NULL_TREE
;
6010 gimple
*stmt
= gsi_stmt (*gsi
);
6011 tree lhs
= gimple_get_lhs (stmt
);
6012 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
6013 && !gimple_has_volatile_ops (stmt
)
6014 /* See PR43491. Do not replace a global register variable when
6015 it is a the RHS of an assignment. Do replace local register
6016 variables since gcc does not guarantee a local variable will
6017 be allocated in register.
6018 ??? The fix isn't effective here. This should instead
6019 be ensured by not value-numbering them the same but treating
6020 them like volatiles? */
6021 && !(gimple_assign_single_p (stmt
)
6022 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == VAR_DECL
6023 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt
))
6024 && is_global_var (gimple_assign_rhs1 (stmt
)))))
6026 sprime
= eliminate_avail (b
, lhs
);
6029 /* If there is no existing usable leader but SCCVN thinks
6030 it has an expression it wants to use as replacement,
6032 tree val
= VN_INFO (lhs
)->valnum
;
6033 vn_ssa_aux_t vn_info
;
6035 && TREE_CODE (val
) == SSA_NAME
6036 && (vn_info
= VN_INFO (val
), true)
6037 && vn_info
->needs_insertion
6038 && vn_info
->expr
!= NULL
6039 && (sprime
= eliminate_insert (b
, gsi
, val
)) != NULL_TREE
)
6040 eliminate_push_avail (b
, sprime
);
6043 /* If this now constitutes a copy duplicate points-to
6044 and range info appropriately. This is especially
6045 important for inserted code. See tree-ssa-copy.c
6046 for similar code. */
6048 && TREE_CODE (sprime
) == SSA_NAME
)
6050 basic_block sprime_b
= gimple_bb (SSA_NAME_DEF_STMT (sprime
));
6051 if (POINTER_TYPE_P (TREE_TYPE (lhs
))
6052 && SSA_NAME_PTR_INFO (lhs
)
6053 && ! SSA_NAME_PTR_INFO (sprime
))
6055 duplicate_ssa_name_ptr_info (sprime
,
6056 SSA_NAME_PTR_INFO (lhs
));
6058 reset_flow_sensitive_info (sprime
);
6060 else if (INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
6061 && SSA_NAME_RANGE_INFO (lhs
)
6062 && ! SSA_NAME_RANGE_INFO (sprime
)
6064 duplicate_ssa_name_range_info (sprime
,
6065 SSA_NAME_RANGE_TYPE (lhs
),
6066 SSA_NAME_RANGE_INFO (lhs
));
6069 /* Inhibit the use of an inserted PHI on a loop header when
6070 the address of the memory reference is a simple induction
6071 variable. In other cases the vectorizer won't do anything
6072 anyway (either it's loop invariant or a complicated
6075 && TREE_CODE (sprime
) == SSA_NAME
6077 && (flag_tree_loop_vectorize
|| flag_tree_parallelize_loops
> 1)
6078 && loop_outer (b
->loop_father
)
6079 && has_zero_uses (sprime
)
6080 && bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (sprime
))
6081 && gimple_assign_load_p (stmt
))
6083 gimple
*def_stmt
= SSA_NAME_DEF_STMT (sprime
);
6084 basic_block def_bb
= gimple_bb (def_stmt
);
6085 if (gimple_code (def_stmt
) == GIMPLE_PHI
6086 && def_bb
->loop_father
->header
== def_bb
)
6088 loop_p loop
= def_bb
->loop_father
;
6092 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
6095 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (op
));
6097 && flow_bb_inside_loop_p (loop
, def_bb
)
6098 && simple_iv (loop
, loop
, op
, &iv
, true))
6106 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6108 fprintf (dump_file
, "Not replacing ");
6109 print_gimple_expr (dump_file
, stmt
, 0);
6110 fprintf (dump_file
, " with ");
6111 print_generic_expr (dump_file
, sprime
);
6112 fprintf (dump_file
, " which would add a loop"
6113 " carried dependence to loop %d\n",
6116 /* Don't keep sprime available. */
6124 /* If we can propagate the value computed for LHS into
6125 all uses don't bother doing anything with this stmt. */
6126 if (may_propagate_copy (lhs
, sprime
))
6128 /* Mark it for removal. */
6129 to_remove
.safe_push (stmt
);
6131 /* ??? Don't count copy/constant propagations. */
6132 if (gimple_assign_single_p (stmt
)
6133 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
6134 || gimple_assign_rhs1 (stmt
) == sprime
))
6137 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6139 fprintf (dump_file
, "Replaced ");
6140 print_gimple_expr (dump_file
, stmt
, 0);
6141 fprintf (dump_file
, " with ");
6142 print_generic_expr (dump_file
, sprime
);
6143 fprintf (dump_file
, " in all uses of ");
6144 print_gimple_stmt (dump_file
, stmt
, 0);
6151 /* If this is an assignment from our leader (which
6152 happens in the case the value-number is a constant)
6153 then there is nothing to do. Likewise if we run into
6154 inserted code that needed a conversion because of
6155 our type-agnostic value-numbering of loads. */
6156 if ((gimple_assign_single_p (stmt
)
6157 || (is_gimple_assign (stmt
)
6158 && (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt
))
6159 || gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
)))
6160 && sprime
== gimple_assign_rhs1 (stmt
))
6163 /* Else replace its RHS. */
6164 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6166 fprintf (dump_file
, "Replaced ");
6167 print_gimple_expr (dump_file
, stmt
, 0);
6168 fprintf (dump_file
, " with ");
6169 print_generic_expr (dump_file
, sprime
);
6170 fprintf (dump_file
, " in ");
6171 print_gimple_stmt (dump_file
, stmt
, 0);
6175 bool can_make_abnormal_goto
= (is_gimple_call (stmt
)
6176 && stmt_can_make_abnormal_goto (stmt
));
6177 gimple
*orig_stmt
= stmt
;
6178 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
6179 TREE_TYPE (sprime
)))
6181 /* We preserve conversions to but not from function or method
6182 types. This asymmetry makes it necessary to re-instantiate
6183 conversions here. */
6184 if (POINTER_TYPE_P (TREE_TYPE (lhs
))
6185 && FUNC_OR_METHOD_TYPE_P (TREE_TYPE (TREE_TYPE (lhs
))))
6186 sprime
= fold_convert (TREE_TYPE (lhs
), sprime
);
6190 tree vdef
= gimple_vdef (stmt
);
6191 tree vuse
= gimple_vuse (stmt
);
6192 propagate_tree_value_into_stmt (gsi
, sprime
);
6193 stmt
= gsi_stmt (*gsi
);
6195 /* In case the VDEF on the original stmt was released, value-number
6196 it to the VUSE. This is to make vuse_ssa_val able to skip
6197 released virtual operands. */
6198 if (vdef
!= gimple_vdef (stmt
))
6200 gcc_assert (SSA_NAME_IN_FREE_LIST (vdef
));
6201 VN_INFO (vdef
)->valnum
= vuse
;
6204 /* If we removed EH side-effects from the statement, clean
6205 its EH information. */
6206 if (maybe_clean_or_replace_eh_stmt (orig_stmt
, stmt
))
6208 bitmap_set_bit (need_eh_cleanup
,
6209 gimple_bb (stmt
)->index
);
6210 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6211 fprintf (dump_file
, " Removed EH side-effects.\n");
6214 /* Likewise for AB side-effects. */
6215 if (can_make_abnormal_goto
6216 && !stmt_can_make_abnormal_goto (stmt
))
6218 bitmap_set_bit (need_ab_cleanup
,
6219 gimple_bb (stmt
)->index
);
6220 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6221 fprintf (dump_file
, " Removed AB side-effects.\n");
6228 /* If the statement is a scalar store, see if the expression
6229 has the same value number as its rhs. If so, the store is
6231 if (gimple_assign_single_p (stmt
)
6232 && !gimple_has_volatile_ops (stmt
)
6233 && !is_gimple_reg (gimple_assign_lhs (stmt
))
6234 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
6235 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
6237 tree rhs
= gimple_assign_rhs1 (stmt
);
6238 vn_reference_t vnresult
;
6239 /* ??? gcc.dg/torture/pr91445.c shows that we lookup a boolean
6240 typed load of a byte known to be 0x11 as 1 so a store of
6241 a boolean 1 is detected as redundant. Because of this we
6242 have to make sure to lookup with a ref where its size
6243 matches the precision. */
6244 tree lookup_lhs
= lhs
;
6245 if (INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
6246 && (TREE_CODE (lhs
) != COMPONENT_REF
6247 || !DECL_BIT_FIELD_TYPE (TREE_OPERAND (lhs
, 1)))
6248 && !type_has_mode_precision_p (TREE_TYPE (lhs
)))
6250 if (TREE_CODE (lhs
) == COMPONENT_REF
6251 || TREE_CODE (lhs
) == MEM_REF
)
6253 tree ltype
= build_nonstandard_integer_type
6254 (TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (lhs
))),
6255 TYPE_UNSIGNED (TREE_TYPE (lhs
)));
6256 if (TREE_CODE (lhs
) == COMPONENT_REF
)
6258 tree foff
= component_ref_field_offset (lhs
);
6259 tree f
= TREE_OPERAND (lhs
, 1);
6260 if (!poly_int_tree_p (foff
))
6261 lookup_lhs
= NULL_TREE
;
6263 lookup_lhs
= build3 (BIT_FIELD_REF
, ltype
,
6264 TREE_OPERAND (lhs
, 0),
6265 TYPE_SIZE (TREE_TYPE (lhs
)),
6267 (foff
, DECL_FIELD_BIT_OFFSET (f
)));
6270 lookup_lhs
= build2 (MEM_REF
, ltype
,
6271 TREE_OPERAND (lhs
, 0),
6272 TREE_OPERAND (lhs
, 1));
6275 lookup_lhs
= NULL_TREE
;
6277 tree val
= NULL_TREE
;
6279 val
= vn_reference_lookup (lookup_lhs
, gimple_vuse (stmt
),
6280 VN_WALKREWRITE
, &vnresult
, false);
6281 if (TREE_CODE (rhs
) == SSA_NAME
)
6282 rhs
= VN_INFO (rhs
)->valnum
;
6284 && (operand_equal_p (val
, rhs
, 0)
6285 /* Due to the bitfield lookups above we can get bit
6286 interpretations of the same RHS as values here. Those
6287 are redundant as well. */
6288 || (TREE_CODE (val
) == SSA_NAME
6289 && gimple_assign_single_p (SSA_NAME_DEF_STMT (val
))
6290 && (val
= gimple_assign_rhs1 (SSA_NAME_DEF_STMT (val
)))
6291 && TREE_CODE (val
) == VIEW_CONVERT_EXPR
6292 && TREE_OPERAND (val
, 0) == rhs
)))
6294 /* We can only remove the later store if the former aliases
6295 at least all accesses the later one does or if the store
6296 was to readonly memory storing the same value. */
6298 ao_ref_init (&lhs_ref
, lhs
);
6299 alias_set_type set
= ao_ref_alias_set (&lhs_ref
);
6300 alias_set_type base_set
= ao_ref_base_alias_set (&lhs_ref
);
6302 || ((vnresult
->set
== set
6303 || alias_set_subset_of (set
, vnresult
->set
))
6304 && (vnresult
->base_set
== base_set
6305 || alias_set_subset_of (base_set
, vnresult
->base_set
))))
6307 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6309 fprintf (dump_file
, "Deleted redundant store ");
6310 print_gimple_stmt (dump_file
, stmt
, 0);
6313 /* Queue stmt for removal. */
6314 to_remove
.safe_push (stmt
);
6320 /* If this is a control statement value numbering left edges
6321 unexecuted on force the condition in a way consistent with
6323 if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
6325 if ((EDGE_SUCC (b
, 0)->flags
& EDGE_EXECUTABLE
)
6326 ^ (EDGE_SUCC (b
, 1)->flags
& EDGE_EXECUTABLE
))
6328 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6330 fprintf (dump_file
, "Removing unexecutable edge from ");
6331 print_gimple_stmt (dump_file
, stmt
, 0);
6333 if (((EDGE_SUCC (b
, 0)->flags
& EDGE_TRUE_VALUE
) != 0)
6334 == ((EDGE_SUCC (b
, 0)->flags
& EDGE_EXECUTABLE
) != 0))
6335 gimple_cond_make_true (cond
);
6337 gimple_cond_make_false (cond
);
6339 el_todo
|= TODO_cleanup_cfg
;
6344 bool can_make_abnormal_goto
= stmt_can_make_abnormal_goto (stmt
);
6345 bool was_noreturn
= (is_gimple_call (stmt
)
6346 && gimple_call_noreturn_p (stmt
));
6347 tree vdef
= gimple_vdef (stmt
);
6348 tree vuse
= gimple_vuse (stmt
);
6350 /* If we didn't replace the whole stmt (or propagate the result
6351 into all uses), replace all uses on this stmt with their
6353 bool modified
= false;
6354 use_operand_p use_p
;
6356 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
6358 tree use
= USE_FROM_PTR (use_p
);
6359 /* ??? The call code above leaves stmt operands un-updated. */
6360 if (TREE_CODE (use
) != SSA_NAME
)
6363 if (SSA_NAME_IS_DEFAULT_DEF (use
))
6364 /* ??? For default defs BB shouldn't matter, but we have to
6365 solve the inconsistency between rpo eliminate and
6366 dom eliminate avail valueization first. */
6367 sprime
= eliminate_avail (b
, use
);
6369 /* Look for sth available at the definition block of the argument.
6370 This avoids inconsistencies between availability there which
6371 decides if the stmt can be removed and availability at the
6372 use site. The SSA property ensures that things available
6373 at the definition are also available at uses. */
6374 sprime
= eliminate_avail (gimple_bb (SSA_NAME_DEF_STMT (use
)), use
);
6375 if (sprime
&& sprime
!= use
6376 && may_propagate_copy (use
, sprime
)
6377 /* We substitute into debug stmts to avoid excessive
6378 debug temporaries created by removed stmts, but we need
6379 to avoid doing so for inserted sprimes as we never want
6380 to create debug temporaries for them. */
6382 || TREE_CODE (sprime
) != SSA_NAME
6383 || !is_gimple_debug (stmt
)
6384 || !bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (sprime
))))
6386 propagate_value (use_p
, sprime
);
6391 /* Fold the stmt if modified, this canonicalizes MEM_REFs we propagated
6392 into which is a requirement for the IPA devirt machinery. */
6393 gimple
*old_stmt
= stmt
;
6396 /* If a formerly non-invariant ADDR_EXPR is turned into an
6397 invariant one it was on a separate stmt. */
6398 if (gimple_assign_single_p (stmt
)
6399 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ADDR_EXPR
)
6400 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt
));
6401 gimple_stmt_iterator prev
= *gsi
;
6403 if (fold_stmt (gsi
, follow_all_ssa_edges
))
6405 /* fold_stmt may have created new stmts inbetween
6406 the previous stmt and the folded stmt. Mark
6407 all defs created there as varying to not confuse
6408 the SCCVN machinery as we're using that even during
6410 if (gsi_end_p (prev
))
6411 prev
= gsi_start_bb (b
);
6414 if (gsi_stmt (prev
) != gsi_stmt (*gsi
))
6419 FOR_EACH_SSA_TREE_OPERAND (def
, gsi_stmt (prev
),
6420 dit
, SSA_OP_ALL_DEFS
)
6421 /* As existing DEFs may move between stmts
6422 only process new ones. */
6423 if (! has_VN_INFO (def
))
6425 vn_ssa_aux_t vn_info
= VN_INFO (def
);
6426 vn_info
->valnum
= def
;
6427 vn_info
->visited
= true;
6429 if (gsi_stmt (prev
) == gsi_stmt (*gsi
))
6435 stmt
= gsi_stmt (*gsi
);
6436 /* In case we folded the stmt away schedule the NOP for removal. */
6437 if (gimple_nop_p (stmt
))
6438 to_remove
.safe_push (stmt
);
6441 /* Visit indirect calls and turn them into direct calls if
6442 possible using the devirtualization machinery. Do this before
6443 checking for required EH/abnormal/noreturn cleanup as devird
6444 may expose more of those. */
6445 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
6447 tree fn
= gimple_call_fn (call_stmt
);
6449 && flag_devirtualize
6450 && virtual_method_call_p (fn
))
6452 tree otr_type
= obj_type_ref_class (fn
);
6453 unsigned HOST_WIDE_INT otr_tok
6454 = tree_to_uhwi (OBJ_TYPE_REF_TOKEN (fn
));
6456 ipa_polymorphic_call_context
context (current_function_decl
,
6457 fn
, stmt
, &instance
);
6458 context
.get_dynamic_type (instance
, OBJ_TYPE_REF_OBJECT (fn
),
6459 otr_type
, stmt
, NULL
);
6461 vec
<cgraph_node
*> targets
6462 = possible_polymorphic_call_targets (obj_type_ref_class (fn
),
6463 otr_tok
, context
, &final
);
6465 dump_possible_polymorphic_call_targets (dump_file
,
6466 obj_type_ref_class (fn
),
6468 if (final
&& targets
.length () <= 1 && dbg_cnt (devirt
))
6471 if (targets
.length () == 1)
6472 fn
= targets
[0]->decl
;
6474 fn
= builtin_decl_implicit (BUILT_IN_UNREACHABLE
);
6475 if (dump_enabled_p ())
6477 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
6478 "converting indirect call to "
6480 lang_hooks
.decl_printable_name (fn
, 2));
6482 gimple_call_set_fndecl (call_stmt
, fn
);
6483 /* If changing the call to __builtin_unreachable
6484 or similar noreturn function, adjust gimple_call_fntype
6486 if (gimple_call_noreturn_p (call_stmt
)
6487 && VOID_TYPE_P (TREE_TYPE (TREE_TYPE (fn
)))
6488 && TYPE_ARG_TYPES (TREE_TYPE (fn
))
6489 && (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fn
)))
6491 gimple_call_set_fntype (call_stmt
, TREE_TYPE (fn
));
6492 maybe_remove_unused_call_args (cfun
, call_stmt
);
6500 /* When changing a call into a noreturn call, cfg cleanup
6501 is needed to fix up the noreturn call. */
6503 && is_gimple_call (stmt
) && gimple_call_noreturn_p (stmt
))
6504 to_fixup
.safe_push (stmt
);
6505 /* When changing a condition or switch into one we know what
6506 edge will be executed, schedule a cfg cleanup. */
6507 if ((gimple_code (stmt
) == GIMPLE_COND
6508 && (gimple_cond_true_p (as_a
<gcond
*> (stmt
))
6509 || gimple_cond_false_p (as_a
<gcond
*> (stmt
))))
6510 || (gimple_code (stmt
) == GIMPLE_SWITCH
6511 && TREE_CODE (gimple_switch_index
6512 (as_a
<gswitch
*> (stmt
))) == INTEGER_CST
))
6513 el_todo
|= TODO_cleanup_cfg
;
6514 /* If we removed EH side-effects from the statement, clean
6515 its EH information. */
6516 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
6518 bitmap_set_bit (need_eh_cleanup
,
6519 gimple_bb (stmt
)->index
);
6520 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6521 fprintf (dump_file
, " Removed EH side-effects.\n");
6523 /* Likewise for AB side-effects. */
6524 if (can_make_abnormal_goto
6525 && !stmt_can_make_abnormal_goto (stmt
))
6527 bitmap_set_bit (need_ab_cleanup
,
6528 gimple_bb (stmt
)->index
);
6529 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6530 fprintf (dump_file
, " Removed AB side-effects.\n");
6533 /* In case the VDEF on the original stmt was released, value-number
6534 it to the VUSE. This is to make vuse_ssa_val able to skip
6535 released virtual operands. */
6536 if (vdef
&& SSA_NAME_IN_FREE_LIST (vdef
))
6537 VN_INFO (vdef
)->valnum
= vuse
;
6540 /* Make new values available - for fully redundant LHS we
6541 continue with the next stmt above and skip this. */
6543 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_DEF
)
6544 eliminate_push_avail (b
, DEF_FROM_PTR (defp
));
6547 /* Perform elimination for the basic-block B during the domwalk. */
6550 eliminate_dom_walker::before_dom_children (basic_block b
)
6553 avail_stack
.safe_push (NULL_TREE
);
6555 /* Skip unreachable blocks marked unreachable during the SCCVN domwalk. */
6556 if (!(b
->flags
& BB_EXECUTABLE
))
6561 for (gphi_iterator gsi
= gsi_start_phis (b
); !gsi_end_p (gsi
);)
6563 gphi
*phi
= gsi
.phi ();
6564 tree res
= PHI_RESULT (phi
);
6566 if (virtual_operand_p (res
))
6572 tree sprime
= eliminate_avail (b
, res
);
6576 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6578 fprintf (dump_file
, "Replaced redundant PHI node defining ");
6579 print_generic_expr (dump_file
, res
);
6580 fprintf (dump_file
, " with ");
6581 print_generic_expr (dump_file
, sprime
);
6582 fprintf (dump_file
, "\n");
6585 /* If we inserted this PHI node ourself, it's not an elimination. */
6586 if (! inserted_exprs
6587 || ! bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (res
)))
6590 /* If we will propagate into all uses don't bother to do
6592 if (may_propagate_copy (res
, sprime
))
6594 /* Mark the PHI for removal. */
6595 to_remove
.safe_push (phi
);
6600 remove_phi_node (&gsi
, false);
6602 if (!useless_type_conversion_p (TREE_TYPE (res
), TREE_TYPE (sprime
)))
6603 sprime
= fold_convert (TREE_TYPE (res
), sprime
);
6604 gimple
*stmt
= gimple_build_assign (res
, sprime
);
6605 gimple_stmt_iterator gsi2
= gsi_after_labels (b
);
6606 gsi_insert_before (&gsi2
, stmt
, GSI_NEW_STMT
);
6610 eliminate_push_avail (b
, res
);
6614 for (gimple_stmt_iterator gsi
= gsi_start_bb (b
);
6617 eliminate_stmt (b
, &gsi
);
6619 /* Replace destination PHI arguments. */
6622 FOR_EACH_EDGE (e
, ei
, b
->succs
)
6623 if (e
->flags
& EDGE_EXECUTABLE
)
6624 for (gphi_iterator gsi
= gsi_start_phis (e
->dest
);
6628 gphi
*phi
= gsi
.phi ();
6629 use_operand_p use_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
6630 tree arg
= USE_FROM_PTR (use_p
);
6631 if (TREE_CODE (arg
) != SSA_NAME
6632 || virtual_operand_p (arg
))
6634 tree sprime
= eliminate_avail (b
, arg
);
6635 if (sprime
&& may_propagate_copy (arg
, sprime
))
6636 propagate_value (use_p
, sprime
);
6639 vn_context_bb
= NULL
;
6644 /* Make no longer available leaders no longer available. */
6647 eliminate_dom_walker::after_dom_children (basic_block
)
6650 while ((entry
= avail_stack
.pop ()) != NULL_TREE
)
6652 tree valnum
= VN_INFO (entry
)->valnum
;
6653 tree old
= avail
[SSA_NAME_VERSION (valnum
)];
6655 avail
[SSA_NAME_VERSION (valnum
)] = NULL_TREE
;
6657 avail
[SSA_NAME_VERSION (valnum
)] = entry
;
6661 /* Remove queued stmts and perform delayed cleanups. */
6664 eliminate_dom_walker::eliminate_cleanup (bool region_p
)
6666 statistics_counter_event (cfun
, "Eliminated", eliminations
);
6667 statistics_counter_event (cfun
, "Insertions", insertions
);
6669 /* We cannot remove stmts during BB walk, especially not release SSA
6670 names there as this confuses the VN machinery. The stmts ending
6671 up in to_remove are either stores or simple copies.
6672 Remove stmts in reverse order to make debug stmt creation possible. */
6673 while (!to_remove
.is_empty ())
6675 bool do_release_defs
= true;
6676 gimple
*stmt
= to_remove
.pop ();
6678 /* When we are value-numbering a region we do not require exit PHIs to
6679 be present so we have to make sure to deal with uses outside of the
6680 region of stmts that we thought are eliminated.
6681 ??? Note we may be confused by uses in dead regions we didn't run
6682 elimination on. Rather than checking individual uses we accept
6683 dead copies to be generated here (gcc.c-torture/execute/20060905-1.c
6684 contains such example). */
6687 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
6689 tree lhs
= gimple_phi_result (phi
);
6690 if (!has_zero_uses (lhs
))
6692 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6693 fprintf (dump_file
, "Keeping eliminated stmt live "
6694 "as copy because of out-of-region uses\n");
6695 tree sprime
= eliminate_avail (gimple_bb (stmt
), lhs
);
6696 gimple
*copy
= gimple_build_assign (lhs
, sprime
);
6697 gimple_stmt_iterator gsi
6698 = gsi_after_labels (gimple_bb (stmt
));
6699 gsi_insert_before (&gsi
, copy
, GSI_SAME_STMT
);
6700 do_release_defs
= false;
6703 else if (tree lhs
= gimple_get_lhs (stmt
))
6704 if (TREE_CODE (lhs
) == SSA_NAME
6705 && !has_zero_uses (lhs
))
6707 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6708 fprintf (dump_file
, "Keeping eliminated stmt live "
6709 "as copy because of out-of-region uses\n");
6710 tree sprime
= eliminate_avail (gimple_bb (stmt
), lhs
);
6711 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
6712 if (is_gimple_assign (stmt
))
6714 gimple_assign_set_rhs_from_tree (&gsi
, sprime
);
6715 stmt
= gsi_stmt (gsi
);
6717 if (maybe_clean_or_replace_eh_stmt (stmt
, stmt
))
6718 bitmap_set_bit (need_eh_cleanup
, gimple_bb (stmt
)->index
);
6723 gimple
*copy
= gimple_build_assign (lhs
, sprime
);
6724 gsi_insert_before (&gsi
, copy
, GSI_SAME_STMT
);
6725 do_release_defs
= false;
6730 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6732 fprintf (dump_file
, "Removing dead stmt ");
6733 print_gimple_stmt (dump_file
, stmt
, 0, TDF_NONE
);
6736 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
6737 if (gimple_code (stmt
) == GIMPLE_PHI
)
6738 remove_phi_node (&gsi
, do_release_defs
);
6741 basic_block bb
= gimple_bb (stmt
);
6742 unlink_stmt_vdef (stmt
);
6743 if (gsi_remove (&gsi
, true))
6744 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
6745 if (is_gimple_call (stmt
) && stmt_can_make_abnormal_goto (stmt
))
6746 bitmap_set_bit (need_ab_cleanup
, bb
->index
);
6747 if (do_release_defs
)
6748 release_defs (stmt
);
6751 /* Removing a stmt may expose a forwarder block. */
6752 el_todo
|= TODO_cleanup_cfg
;
6755 /* Fixup stmts that became noreturn calls. This may require splitting
6756 blocks and thus isn't possible during the dominator walk. Do this
6757 in reverse order so we don't inadvertedly remove a stmt we want to
6758 fixup by visiting a dominating now noreturn call first. */
6759 while (!to_fixup
.is_empty ())
6761 gimple
*stmt
= to_fixup
.pop ();
6763 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6765 fprintf (dump_file
, "Fixing up noreturn call ");
6766 print_gimple_stmt (dump_file
, stmt
, 0);
6769 if (fixup_noreturn_call (stmt
))
6770 el_todo
|= TODO_cleanup_cfg
;
6773 bool do_eh_cleanup
= !bitmap_empty_p (need_eh_cleanup
);
6774 bool do_ab_cleanup
= !bitmap_empty_p (need_ab_cleanup
);
6777 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
6780 gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup
);
6782 if (do_eh_cleanup
|| do_ab_cleanup
)
6783 el_todo
|= TODO_cleanup_cfg
;
6788 /* Eliminate fully redundant computations. */
6791 eliminate_with_rpo_vn (bitmap inserted_exprs
)
6793 eliminate_dom_walker
walker (CDI_DOMINATORS
, inserted_exprs
);
6795 eliminate_dom_walker
*saved_rpo_avail
= rpo_avail
;
6796 rpo_avail
= &walker
;
6797 walker
.walk (cfun
->cfg
->x_entry_block_ptr
);
6798 rpo_avail
= saved_rpo_avail
;
6800 return walker
.eliminate_cleanup ();
6804 do_rpo_vn (function
*fn
, edge entry
, bitmap exit_bbs
,
6805 bool iterate
, bool eliminate
);
6808 run_rpo_vn (vn_lookup_kind kind
)
6810 default_vn_walk_kind
= kind
;
6811 do_rpo_vn (cfun
, NULL
, NULL
, true, false);
6813 /* ??? Prune requirement of these. */
6814 constant_to_value_id
= new hash_table
<vn_constant_hasher
> (23);
6816 /* Initialize the value ids and prune out remaining VN_TOPs
6820 FOR_EACH_SSA_NAME (i
, name
, cfun
)
6822 vn_ssa_aux_t info
= VN_INFO (name
);
6824 || info
->valnum
== VN_TOP
)
6825 info
->valnum
= name
;
6826 if (info
->valnum
== name
)
6827 info
->value_id
= get_next_value_id ();
6828 else if (is_gimple_min_invariant (info
->valnum
))
6829 info
->value_id
= get_or_alloc_constant_value_id (info
->valnum
);
6833 FOR_EACH_SSA_NAME (i
, name
, cfun
)
6835 vn_ssa_aux_t info
= VN_INFO (name
);
6836 if (TREE_CODE (info
->valnum
) == SSA_NAME
6837 && info
->valnum
!= name
6838 && info
->value_id
!= VN_INFO (info
->valnum
)->value_id
)
6839 info
->value_id
= VN_INFO (info
->valnum
)->value_id
;
6842 set_hashtable_value_ids ();
6844 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6846 fprintf (dump_file
, "Value numbers:\n");
6847 FOR_EACH_SSA_NAME (i
, name
, cfun
)
6849 if (VN_INFO (name
)->visited
6850 && SSA_VAL (name
) != name
)
6852 print_generic_expr (dump_file
, name
);
6853 fprintf (dump_file
, " = ");
6854 print_generic_expr (dump_file
, SSA_VAL (name
));
6855 fprintf (dump_file
, " (%04d)\n", VN_INFO (name
)->value_id
);
6861 /* Free VN associated data structures. */
6866 free_vn_table (valid_info
);
6867 XDELETE (valid_info
);
6868 obstack_free (&vn_tables_obstack
, NULL
);
6869 obstack_free (&vn_tables_insert_obstack
, NULL
);
6871 vn_ssa_aux_iterator_type it
;
6873 FOR_EACH_HASH_TABLE_ELEMENT (*vn_ssa_aux_hash
, info
, vn_ssa_aux_t
, it
)
6874 if (info
->needs_insertion
)
6875 release_ssa_name (info
->name
);
6876 obstack_free (&vn_ssa_aux_obstack
, NULL
);
6877 delete vn_ssa_aux_hash
;
6879 delete constant_to_value_id
;
6880 constant_to_value_id
= NULL
;
6883 /* Hook for maybe_push_res_to_seq, lookup the expression in the VN tables. */
6886 vn_lookup_simplify_result (gimple_match_op
*res_op
)
6888 if (!res_op
->code
.is_tree_code ())
6890 tree
*ops
= res_op
->ops
;
6891 unsigned int length
= res_op
->num_ops
;
6892 if (res_op
->code
== CONSTRUCTOR
6893 /* ??? We're arriving here with SCCVNs view, decomposed CONSTRUCTOR
6894 and GIMPLEs / match-and-simplifies, CONSTRUCTOR as GENERIC tree. */
6895 && TREE_CODE (res_op
->ops
[0]) == CONSTRUCTOR
)
6897 length
= CONSTRUCTOR_NELTS (res_op
->ops
[0]);
6898 ops
= XALLOCAVEC (tree
, length
);
6899 for (unsigned i
= 0; i
< length
; ++i
)
6900 ops
[i
] = CONSTRUCTOR_ELT (res_op
->ops
[0], i
)->value
;
6902 vn_nary_op_t vnresult
= NULL
;
6903 tree res
= vn_nary_op_lookup_pieces (length
, (tree_code
) res_op
->code
,
6904 res_op
->type
, ops
, &vnresult
);
6905 /* If this is used from expression simplification make sure to
6906 return an available expression. */
6907 if (res
&& TREE_CODE (res
) == SSA_NAME
&& mprts_hook
&& rpo_avail
)
6908 res
= rpo_avail
->eliminate_avail (vn_context_bb
, res
);
6912 /* Return a leader for OPs value that is valid at BB. */
6915 rpo_elim::eliminate_avail (basic_block bb
, tree op
)
6918 tree valnum
= SSA_VAL (op
, &visited
);
6919 /* If we didn't visit OP then it must be defined outside of the
6920 region we process and also dominate it. So it is available. */
6923 if (TREE_CODE (valnum
) == SSA_NAME
)
6925 if (SSA_NAME_IS_DEFAULT_DEF (valnum
))
6927 vn_avail
*av
= VN_INFO (valnum
)->avail
;
6930 if (av
->location
== bb
->index
)
6931 /* On tramp3d 90% of the cases are here. */
6932 return ssa_name (av
->leader
);
6935 basic_block abb
= BASIC_BLOCK_FOR_FN (cfun
, av
->location
);
6936 /* ??? During elimination we have to use availability at the
6937 definition site of a use we try to replace. This
6938 is required to not run into inconsistencies because
6939 of dominated_by_p_w_unex behavior and removing a definition
6940 while not replacing all uses.
6941 ??? We could try to consistently walk dominators
6942 ignoring non-executable regions. The nearest common
6943 dominator of bb and abb is where we can stop walking. We
6944 may also be able to "pre-compute" (bits of) the next immediate
6945 (non-)dominator during the RPO walk when marking edges as
6947 if (dominated_by_p_w_unex (bb
, abb
, true))
6949 tree leader
= ssa_name (av
->leader
);
6950 /* Prevent eliminations that break loop-closed SSA. */
6951 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
)
6952 && ! SSA_NAME_IS_DEFAULT_DEF (leader
)
6953 && ! flow_bb_inside_loop_p (gimple_bb (SSA_NAME_DEF_STMT
6954 (leader
))->loop_father
,
6957 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6959 print_generic_expr (dump_file
, leader
);
6960 fprintf (dump_file
, " is available for ");
6961 print_generic_expr (dump_file
, valnum
);
6962 fprintf (dump_file
, "\n");
6964 /* On tramp3d 99% of the _remaining_ cases succeed at
6968 /* ??? Can we somehow skip to the immediate dominator
6969 RPO index (bb_to_rpo)? Again, maybe not worth, on
6970 tramp3d the worst number of elements in the vector is 9. */
6975 else if (valnum
!= VN_TOP
)
6976 /* valnum is is_gimple_min_invariant. */
6981 /* Make LEADER a leader for its value at BB. */
6984 rpo_elim::eliminate_push_avail (basic_block bb
, tree leader
)
6986 tree valnum
= VN_INFO (leader
)->valnum
;
6987 if (valnum
== VN_TOP
6988 || is_gimple_min_invariant (valnum
))
6990 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6992 fprintf (dump_file
, "Making available beyond BB%d ", bb
->index
);
6993 print_generic_expr (dump_file
, leader
);
6994 fprintf (dump_file
, " for value ");
6995 print_generic_expr (dump_file
, valnum
);
6996 fprintf (dump_file
, "\n");
6998 vn_ssa_aux_t value
= VN_INFO (valnum
);
7000 if (m_avail_freelist
)
7002 av
= m_avail_freelist
;
7003 m_avail_freelist
= m_avail_freelist
->next
;
7006 av
= XOBNEW (&vn_ssa_aux_obstack
, vn_avail
);
7007 av
->location
= bb
->index
;
7008 av
->leader
= SSA_NAME_VERSION (leader
);
7009 av
->next
= value
->avail
;
7010 av
->next_undo
= last_pushed_avail
;
7011 last_pushed_avail
= value
;
7015 /* Valueization hook for RPO VN plus required state. */
7018 rpo_vn_valueize (tree name
)
7020 if (TREE_CODE (name
) == SSA_NAME
)
7022 vn_ssa_aux_t val
= VN_INFO (name
);
7025 tree tem
= val
->valnum
;
7026 if (tem
!= VN_TOP
&& tem
!= name
)
7028 if (TREE_CODE (tem
) != SSA_NAME
)
7030 /* For all values we only valueize to an available leader
7031 which means we can use SSA name info without restriction. */
7032 tem
= rpo_avail
->eliminate_avail (vn_context_bb
, tem
);
7041 /* Insert on PRED_E predicates derived from CODE OPS being true besides the
7042 inverted condition. */
7045 insert_related_predicates_on_edge (enum tree_code code
, tree
*ops
, edge pred_e
)
7050 /* a < b -> a {!,<}= b */
7051 vn_nary_op_insert_pieces_predicated (2, NE_EXPR
, boolean_type_node
,
7052 ops
, boolean_true_node
, 0, pred_e
);
7053 vn_nary_op_insert_pieces_predicated (2, LE_EXPR
, boolean_type_node
,
7054 ops
, boolean_true_node
, 0, pred_e
);
7055 /* a < b -> ! a {>,=} b */
7056 vn_nary_op_insert_pieces_predicated (2, GT_EXPR
, boolean_type_node
,
7057 ops
, boolean_false_node
, 0, pred_e
);
7058 vn_nary_op_insert_pieces_predicated (2, EQ_EXPR
, boolean_type_node
,
7059 ops
, boolean_false_node
, 0, pred_e
);
7062 /* a > b -> a {!,>}= b */
7063 vn_nary_op_insert_pieces_predicated (2, NE_EXPR
, boolean_type_node
,
7064 ops
, boolean_true_node
, 0, pred_e
);
7065 vn_nary_op_insert_pieces_predicated (2, GE_EXPR
, boolean_type_node
,
7066 ops
, boolean_true_node
, 0, pred_e
);
7067 /* a > b -> ! a {<,=} b */
7068 vn_nary_op_insert_pieces_predicated (2, LT_EXPR
, boolean_type_node
,
7069 ops
, boolean_false_node
, 0, pred_e
);
7070 vn_nary_op_insert_pieces_predicated (2, EQ_EXPR
, boolean_type_node
,
7071 ops
, boolean_false_node
, 0, pred_e
);
7074 /* a == b -> ! a {<,>} b */
7075 vn_nary_op_insert_pieces_predicated (2, LT_EXPR
, boolean_type_node
,
7076 ops
, boolean_false_node
, 0, pred_e
);
7077 vn_nary_op_insert_pieces_predicated (2, GT_EXPR
, boolean_type_node
,
7078 ops
, boolean_false_node
, 0, pred_e
);
7083 /* Nothing besides inverted condition. */
7089 /* Main stmt worker for RPO VN, process BB. */
7092 process_bb (rpo_elim
&avail
, basic_block bb
,
7093 bool bb_visited
, bool iterate_phis
, bool iterate
, bool eliminate
,
7094 bool do_region
, bitmap exit_bbs
, bool skip_phis
)
7102 /* If we are in loop-closed SSA preserve this state. This is
7103 relevant when called on regions from outside of FRE/PRE. */
7104 bool lc_phi_nodes
= false;
7106 && loops_state_satisfies_p (LOOP_CLOSED_SSA
))
7107 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
7108 if (e
->src
->loop_father
!= e
->dest
->loop_father
7109 && flow_loop_nested_p (e
->dest
->loop_father
,
7110 e
->src
->loop_father
))
7112 lc_phi_nodes
= true;
7116 /* When we visit a loop header substitute into loop info. */
7117 if (!iterate
&& eliminate
&& bb
->loop_father
->header
== bb
)
7119 /* Keep fields in sync with substitute_in_loop_info. */
7120 if (bb
->loop_father
->nb_iterations
)
7121 bb
->loop_father
->nb_iterations
7122 = simplify_replace_tree (bb
->loop_father
->nb_iterations
,
7123 NULL_TREE
, NULL_TREE
, &vn_valueize_for_srt
);
7126 /* Value-number all defs in the basic-block. */
7128 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
7131 gphi
*phi
= gsi
.phi ();
7132 tree res
= PHI_RESULT (phi
);
7133 vn_ssa_aux_t res_info
= VN_INFO (res
);
7136 gcc_assert (!res_info
->visited
);
7137 res_info
->valnum
= VN_TOP
;
7138 res_info
->visited
= true;
7141 /* When not iterating force backedge values to varying. */
7142 visit_stmt (phi
, !iterate_phis
);
7143 if (virtual_operand_p (res
))
7147 /* The interesting case is gcc.dg/tree-ssa/pr22230.c for correctness
7148 how we handle backedges and availability.
7149 And gcc.dg/tree-ssa/ssa-sccvn-2.c for optimization. */
7150 tree val
= res_info
->valnum
;
7151 if (res
!= val
&& !iterate
&& eliminate
)
7153 if (tree leader
= avail
.eliminate_avail (bb
, res
))
7156 /* Preserve loop-closed SSA form. */
7158 || is_gimple_min_invariant (leader
)))
7160 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7162 fprintf (dump_file
, "Replaced redundant PHI node "
7164 print_generic_expr (dump_file
, res
);
7165 fprintf (dump_file
, " with ");
7166 print_generic_expr (dump_file
, leader
);
7167 fprintf (dump_file
, "\n");
7169 avail
.eliminations
++;
7171 if (may_propagate_copy (res
, leader
))
7173 /* Schedule for removal. */
7174 avail
.to_remove
.safe_push (phi
);
7177 /* ??? Else generate a copy stmt. */
7181 /* Only make defs available that not already are. But make
7182 sure loop-closed SSA PHI node defs are picked up for
7186 || ! avail
.eliminate_avail (bb
, res
))
7187 avail
.eliminate_push_avail (bb
, res
);
7190 /* For empty BBs mark outgoing edges executable. For non-empty BBs
7191 we do this when processing the last stmt as we have to do this
7192 before elimination which otherwise forces GIMPLE_CONDs to
7193 if (1 != 0) style when seeing non-executable edges. */
7194 if (gsi_end_p (gsi_start_bb (bb
)))
7196 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
7198 if (!(e
->flags
& EDGE_EXECUTABLE
))
7200 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7202 "marking outgoing edge %d -> %d executable\n",
7203 e
->src
->index
, e
->dest
->index
);
7204 e
->flags
|= EDGE_EXECUTABLE
;
7205 e
->dest
->flags
|= BB_EXECUTABLE
;
7207 else if (!(e
->dest
->flags
& BB_EXECUTABLE
))
7209 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7211 "marking destination block %d reachable\n",
7213 e
->dest
->flags
|= BB_EXECUTABLE
;
7217 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
7218 !gsi_end_p (gsi
); gsi_next (&gsi
))
7224 FOR_EACH_SSA_TREE_OPERAND (op
, gsi_stmt (gsi
), i
, SSA_OP_ALL_DEFS
)
7226 vn_ssa_aux_t op_info
= VN_INFO (op
);
7227 gcc_assert (!op_info
->visited
);
7228 op_info
->valnum
= VN_TOP
;
7229 op_info
->visited
= true;
7232 /* We somehow have to deal with uses that are not defined
7233 in the processed region. Forcing unvisited uses to
7234 varying here doesn't play well with def-use following during
7235 expression simplification, so we deal with this by checking
7236 the visited flag in SSA_VAL. */
7239 visit_stmt (gsi_stmt (gsi
));
7241 gimple
*last
= gsi_stmt (gsi
);
7243 switch (gimple_code (last
))
7246 e
= find_taken_edge (bb
, vn_valueize (gimple_switch_index
7247 (as_a
<gswitch
*> (last
))));
7251 tree lhs
= vn_valueize (gimple_cond_lhs (last
));
7252 tree rhs
= vn_valueize (gimple_cond_rhs (last
));
7253 tree val
= gimple_simplify (gimple_cond_code (last
),
7254 boolean_type_node
, lhs
, rhs
,
7256 /* If the condition didn't simplfy see if we have recorded
7257 an expression from sofar taken edges. */
7258 if (! val
|| TREE_CODE (val
) != INTEGER_CST
)
7260 vn_nary_op_t vnresult
;
7264 val
= vn_nary_op_lookup_pieces (2, gimple_cond_code (last
),
7265 boolean_type_node
, ops
,
7267 /* Did we get a predicated value? */
7268 if (! val
&& vnresult
&& vnresult
->predicated_values
)
7270 val
= vn_nary_op_get_predicated_value (vnresult
, bb
);
7271 if (val
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
7273 fprintf (dump_file
, "Got predicated value ");
7274 print_generic_expr (dump_file
, val
, TDF_NONE
);
7275 fprintf (dump_file
, " for ");
7276 print_gimple_stmt (dump_file
, last
, TDF_SLIM
);
7281 e
= find_taken_edge (bb
, val
);
7284 /* If we didn't manage to compute the taken edge then
7285 push predicated expressions for the condition itself
7286 and related conditions to the hashtables. This allows
7287 simplification of redundant conditions which is
7288 important as early cleanup. */
7289 edge true_e
, false_e
;
7290 extract_true_false_edges_from_block (bb
, &true_e
, &false_e
);
7291 enum tree_code code
= gimple_cond_code (last
);
7292 enum tree_code icode
7293 = invert_tree_comparison (code
, HONOR_NANS (lhs
));
7298 && bitmap_bit_p (exit_bbs
, true_e
->dest
->index
))
7301 && bitmap_bit_p (exit_bbs
, false_e
->dest
->index
))
7304 vn_nary_op_insert_pieces_predicated
7305 (2, code
, boolean_type_node
, ops
,
7306 boolean_true_node
, 0, true_e
);
7308 vn_nary_op_insert_pieces_predicated
7309 (2, code
, boolean_type_node
, ops
,
7310 boolean_false_node
, 0, false_e
);
7311 if (icode
!= ERROR_MARK
)
7314 vn_nary_op_insert_pieces_predicated
7315 (2, icode
, boolean_type_node
, ops
,
7316 boolean_false_node
, 0, true_e
);
7318 vn_nary_op_insert_pieces_predicated
7319 (2, icode
, boolean_type_node
, ops
,
7320 boolean_true_node
, 0, false_e
);
7322 /* Relax for non-integers, inverted condition handled
7324 if (INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
7327 insert_related_predicates_on_edge (code
, ops
, true_e
);
7329 insert_related_predicates_on_edge (icode
, ops
, false_e
);
7335 e
= find_taken_edge (bb
, vn_valueize (gimple_goto_dest (last
)));
7342 todo
= TODO_cleanup_cfg
;
7343 if (!(e
->flags
& EDGE_EXECUTABLE
))
7345 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7347 "marking known outgoing %sedge %d -> %d executable\n",
7348 e
->flags
& EDGE_DFS_BACK
? "back-" : "",
7349 e
->src
->index
, e
->dest
->index
);
7350 e
->flags
|= EDGE_EXECUTABLE
;
7351 e
->dest
->flags
|= BB_EXECUTABLE
;
7353 else if (!(e
->dest
->flags
& BB_EXECUTABLE
))
7355 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7357 "marking destination block %d reachable\n",
7359 e
->dest
->flags
|= BB_EXECUTABLE
;
7362 else if (gsi_one_before_end_p (gsi
))
7364 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
7366 if (!(e
->flags
& EDGE_EXECUTABLE
))
7368 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7370 "marking outgoing edge %d -> %d executable\n",
7371 e
->src
->index
, e
->dest
->index
);
7372 e
->flags
|= EDGE_EXECUTABLE
;
7373 e
->dest
->flags
|= BB_EXECUTABLE
;
7375 else if (!(e
->dest
->flags
& BB_EXECUTABLE
))
7377 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7379 "marking destination block %d reachable\n",
7381 e
->dest
->flags
|= BB_EXECUTABLE
;
7386 /* Eliminate. That also pushes to avail. */
7387 if (eliminate
&& ! iterate
)
7388 avail
.eliminate_stmt (bb
, &gsi
);
7390 /* If not eliminating, make all not already available defs
7392 FOR_EACH_SSA_TREE_OPERAND (op
, gsi_stmt (gsi
), i
, SSA_OP_DEF
)
7393 if (! avail
.eliminate_avail (bb
, op
))
7394 avail
.eliminate_push_avail (bb
, op
);
7397 /* Eliminate in destination PHI arguments. Always substitute in dest
7398 PHIs, even for non-executable edges. This handles region
7400 if (!iterate
&& eliminate
)
7401 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
7402 for (gphi_iterator gsi
= gsi_start_phis (e
->dest
);
7403 !gsi_end_p (gsi
); gsi_next (&gsi
))
7405 gphi
*phi
= gsi
.phi ();
7406 use_operand_p use_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
7407 tree arg
= USE_FROM_PTR (use_p
);
7408 if (TREE_CODE (arg
) != SSA_NAME
7409 || virtual_operand_p (arg
))
7412 if (SSA_NAME_IS_DEFAULT_DEF (arg
))
7414 sprime
= SSA_VAL (arg
);
7415 gcc_assert (TREE_CODE (sprime
) != SSA_NAME
7416 || SSA_NAME_IS_DEFAULT_DEF (sprime
));
7419 /* Look for sth available at the definition block of the argument.
7420 This avoids inconsistencies between availability there which
7421 decides if the stmt can be removed and availability at the
7422 use site. The SSA property ensures that things available
7423 at the definition are also available at uses. */
7424 sprime
= avail
.eliminate_avail (gimple_bb (SSA_NAME_DEF_STMT (arg
)),
7428 && may_propagate_copy (arg
, sprime
))
7429 propagate_value (use_p
, sprime
);
7432 vn_context_bb
= NULL
;
7436 /* Unwind state per basic-block. */
7440 /* Times this block has been visited. */
7442 /* Whether to handle this as iteration point or whether to treat
7443 incoming backedge PHI values as varying. */
7445 /* Maximum RPO index this block is reachable from. */
7449 vn_reference_t ref_top
;
7451 vn_nary_op_t nary_top
;
7452 vn_avail
*avail_top
;
7455 /* Unwind the RPO VN state for iteration. */
7458 do_unwind (unwind_state
*to
, rpo_elim
&avail
)
7460 gcc_assert (to
->iterate
);
7461 for (; last_inserted_nary
!= to
->nary_top
;
7462 last_inserted_nary
= last_inserted_nary
->next
)
7465 slot
= valid_info
->nary
->find_slot_with_hash
7466 (last_inserted_nary
, last_inserted_nary
->hashcode
, NO_INSERT
);
7467 /* Predication causes the need to restore previous state. */
7468 if ((*slot
)->unwind_to
)
7469 *slot
= (*slot
)->unwind_to
;
7471 valid_info
->nary
->clear_slot (slot
);
7473 for (; last_inserted_phi
!= to
->phi_top
;
7474 last_inserted_phi
= last_inserted_phi
->next
)
7477 slot
= valid_info
->phis
->find_slot_with_hash
7478 (last_inserted_phi
, last_inserted_phi
->hashcode
, NO_INSERT
);
7479 valid_info
->phis
->clear_slot (slot
);
7481 for (; last_inserted_ref
!= to
->ref_top
;
7482 last_inserted_ref
= last_inserted_ref
->next
)
7484 vn_reference_t
*slot
;
7485 slot
= valid_info
->references
->find_slot_with_hash
7486 (last_inserted_ref
, last_inserted_ref
->hashcode
, NO_INSERT
);
7487 (*slot
)->operands
.release ();
7488 valid_info
->references
->clear_slot (slot
);
7490 obstack_free (&vn_tables_obstack
, to
->ob_top
);
7492 /* Prune [rpo_idx, ] from avail. */
7493 for (; last_pushed_avail
&& last_pushed_avail
->avail
!= to
->avail_top
;)
7495 vn_ssa_aux_t val
= last_pushed_avail
;
7496 vn_avail
*av
= val
->avail
;
7497 val
->avail
= av
->next
;
7498 last_pushed_avail
= av
->next_undo
;
7499 av
->next
= avail
.m_avail_freelist
;
7500 avail
.m_avail_freelist
= av
;
7504 /* Do VN on a SEME region specified by ENTRY and EXIT_BBS in FN.
7505 If ITERATE is true then treat backedges optimistically as not
7506 executed and iterate. If ELIMINATE is true then perform
7507 elimination, otherwise leave that to the caller. */
7510 do_rpo_vn (function
*fn
, edge entry
, bitmap exit_bbs
,
7511 bool iterate
, bool eliminate
)
7515 /* We currently do not support region-based iteration when
7516 elimination is requested. */
7517 gcc_assert (!entry
|| !iterate
|| !eliminate
);
7518 /* When iterating we need loop info up-to-date. */
7519 gcc_assert (!iterate
|| !loops_state_satisfies_p (LOOPS_NEED_FIXUP
));
7521 bool do_region
= entry
!= NULL
;
7524 entry
= single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (fn
));
7525 exit_bbs
= BITMAP_ALLOC (NULL
);
7526 bitmap_set_bit (exit_bbs
, EXIT_BLOCK
);
7529 /* Clear EDGE_DFS_BACK on "all" entry edges, RPO order compute will
7530 re-mark those that are contained in the region. */
7533 FOR_EACH_EDGE (e
, ei
, entry
->dest
->preds
)
7534 e
->flags
&= ~EDGE_DFS_BACK
;
7536 int *rpo
= XNEWVEC (int, n_basic_blocks_for_fn (fn
) - NUM_FIXED_BLOCKS
);
7537 auto_vec
<std::pair
<int, int> > toplevel_scc_extents
;
7538 int n
= rev_post_order_and_mark_dfs_back_seme
7539 (fn
, entry
, exit_bbs
, true, rpo
, !iterate
? &toplevel_scc_extents
: NULL
);
7542 BITMAP_FREE (exit_bbs
);
7544 /* If there are any non-DFS_BACK edges into entry->dest skip
7545 processing PHI nodes for that block. This supports
7546 value-numbering loop bodies w/o the actual loop. */
7547 FOR_EACH_EDGE (e
, ei
, entry
->dest
->preds
)
7549 && !(e
->flags
& EDGE_DFS_BACK
))
7551 bool skip_entry_phis
= e
!= NULL
;
7552 if (skip_entry_phis
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
7553 fprintf (dump_file
, "Region does not contain all edges into "
7554 "the entry block, skipping its PHIs.\n");
7556 int *bb_to_rpo
= XNEWVEC (int, last_basic_block_for_fn (fn
));
7557 for (int i
= 0; i
< n
; ++i
)
7558 bb_to_rpo
[rpo
[i
]] = i
;
7560 unwind_state
*rpo_state
= XNEWVEC (unwind_state
, n
);
7562 rpo_elim
avail (entry
->dest
);
7565 /* Verify we have no extra entries into the region. */
7566 if (flag_checking
&& do_region
)
7568 auto_bb_flag
bb_in_region (fn
);
7569 for (int i
= 0; i
< n
; ++i
)
7571 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
7572 bb
->flags
|= bb_in_region
;
7574 /* We can't merge the first two loops because we cannot rely
7575 on EDGE_DFS_BACK for edges not within the region. But if
7576 we decide to always have the bb_in_region flag we can
7577 do the checking during the RPO walk itself (but then it's
7578 also easy to handle MEME conservatively). */
7579 for (int i
= 0; i
< n
; ++i
)
7581 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
7584 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
7585 gcc_assert (e
== entry
7586 || (skip_entry_phis
&& bb
== entry
->dest
)
7587 || (e
->src
->flags
& bb_in_region
));
7589 for (int i
= 0; i
< n
; ++i
)
7591 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
7592 bb
->flags
&= ~bb_in_region
;
7596 /* Create the VN state. For the initial size of the various hashtables
7597 use a heuristic based on region size and number of SSA names. */
7598 unsigned region_size
= (((unsigned HOST_WIDE_INT
)n
* num_ssa_names
)
7599 / (n_basic_blocks_for_fn (fn
) - NUM_FIXED_BLOCKS
));
7600 VN_TOP
= create_tmp_var_raw (void_type_node
, "vn_top");
7602 next_constant_value_id
= -1;
7604 vn_ssa_aux_hash
= new hash_table
<vn_ssa_aux_hasher
> (region_size
* 2);
7605 gcc_obstack_init (&vn_ssa_aux_obstack
);
7607 gcc_obstack_init (&vn_tables_obstack
);
7608 gcc_obstack_init (&vn_tables_insert_obstack
);
7609 valid_info
= XCNEW (struct vn_tables_s
);
7610 allocate_vn_table (valid_info
, region_size
);
7611 last_inserted_ref
= NULL
;
7612 last_inserted_phi
= NULL
;
7613 last_inserted_nary
= NULL
;
7614 last_pushed_avail
= NULL
;
7616 vn_valueize
= rpo_vn_valueize
;
7618 /* Initialize the unwind state and edge/BB executable state. */
7619 unsigned curr_scc
= 0;
7620 for (int i
= 0; i
< n
; ++i
)
7622 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
7623 rpo_state
[i
].visited
= 0;
7624 rpo_state
[i
].max_rpo
= i
;
7625 if (!iterate
&& curr_scc
< toplevel_scc_extents
.length ())
7627 if (i
>= toplevel_scc_extents
[curr_scc
].first
7628 && i
<= toplevel_scc_extents
[curr_scc
].second
)
7629 rpo_state
[i
].max_rpo
= toplevel_scc_extents
[curr_scc
].second
;
7630 if (i
== toplevel_scc_extents
[curr_scc
].second
)
7633 bb
->flags
&= ~BB_EXECUTABLE
;
7634 bool has_backedges
= false;
7637 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
7639 if (e
->flags
& EDGE_DFS_BACK
)
7640 has_backedges
= true;
7641 e
->flags
&= ~EDGE_EXECUTABLE
;
7642 if (iterate
|| e
== entry
|| (skip_entry_phis
&& bb
== entry
->dest
))
7645 rpo_state
[i
].iterate
= iterate
&& has_backedges
;
7647 entry
->flags
|= EDGE_EXECUTABLE
;
7648 entry
->dest
->flags
|= BB_EXECUTABLE
;
7650 /* As heuristic to improve compile-time we handle only the N innermost
7651 loops and the outermost one optimistically. */
7654 unsigned max_depth
= param_rpo_vn_max_loop_depth
;
7655 for (auto loop
: loops_list (cfun
, LI_ONLY_INNERMOST
))
7656 if (loop_depth (loop
) > max_depth
)
7657 for (unsigned i
= 2;
7658 i
< loop_depth (loop
) - max_depth
; ++i
)
7660 basic_block header
= superloop_at_depth (loop
, i
)->header
;
7661 bool non_latch_backedge
= false;
7664 FOR_EACH_EDGE (e
, ei
, header
->preds
)
7665 if (e
->flags
& EDGE_DFS_BACK
)
7667 /* There can be a non-latch backedge into the header
7668 which is part of an outer irreducible region. We
7669 cannot avoid iterating this block then. */
7670 if (!dominated_by_p (CDI_DOMINATORS
,
7673 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7674 fprintf (dump_file
, "non-latch backedge %d -> %d "
7675 "forces iteration of loop %d\n",
7676 e
->src
->index
, e
->dest
->index
, loop
->num
);
7677 non_latch_backedge
= true;
7680 e
->flags
|= EDGE_EXECUTABLE
;
7682 rpo_state
[bb_to_rpo
[header
->index
]].iterate
= non_latch_backedge
;
7689 /* Go and process all blocks, iterating as necessary. */
7692 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[idx
]);
7694 /* If the block has incoming backedges remember unwind state. This
7695 is required even for non-executable blocks since in irreducible
7696 regions we might reach them via the backedge and re-start iterating
7698 Note we can individually mark blocks with incoming backedges to
7699 not iterate where we then handle PHIs conservatively. We do that
7700 heuristically to reduce compile-time for degenerate cases. */
7701 if (rpo_state
[idx
].iterate
)
7703 rpo_state
[idx
].ob_top
= obstack_alloc (&vn_tables_obstack
, 0);
7704 rpo_state
[idx
].ref_top
= last_inserted_ref
;
7705 rpo_state
[idx
].phi_top
= last_inserted_phi
;
7706 rpo_state
[idx
].nary_top
= last_inserted_nary
;
7707 rpo_state
[idx
].avail_top
7708 = last_pushed_avail
? last_pushed_avail
->avail
: NULL
;
7711 if (!(bb
->flags
& BB_EXECUTABLE
))
7713 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7714 fprintf (dump_file
, "Block %d: BB%d found not executable\n",
7720 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7721 fprintf (dump_file
, "Processing block %d: BB%d\n", idx
, bb
->index
);
7723 todo
|= process_bb (avail
, bb
,
7724 rpo_state
[idx
].visited
!= 0,
7725 rpo_state
[idx
].iterate
,
7726 iterate
, eliminate
, do_region
, exit_bbs
, false);
7727 rpo_state
[idx
].visited
++;
7729 /* Verify if changed values flow over executable outgoing backedges
7730 and those change destination PHI values (that's the thing we
7731 can easily verify). Reduce over all such edges to the farthest
7733 int iterate_to
= -1;
7736 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
7737 if ((e
->flags
& (EDGE_DFS_BACK
|EDGE_EXECUTABLE
))
7738 == (EDGE_DFS_BACK
|EDGE_EXECUTABLE
)
7739 && rpo_state
[bb_to_rpo
[e
->dest
->index
]].iterate
)
7741 int destidx
= bb_to_rpo
[e
->dest
->index
];
7742 if (!rpo_state
[destidx
].visited
)
7744 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7745 fprintf (dump_file
, "Unvisited destination %d\n",
7747 if (iterate_to
== -1 || destidx
< iterate_to
)
7748 iterate_to
= destidx
;
7751 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7752 fprintf (dump_file
, "Looking for changed values of backedge"
7753 " %d->%d destination PHIs\n",
7754 e
->src
->index
, e
->dest
->index
);
7755 vn_context_bb
= e
->dest
;
7757 for (gsi
= gsi_start_phis (e
->dest
);
7758 !gsi_end_p (gsi
); gsi_next (&gsi
))
7760 bool inserted
= false;
7761 /* While we'd ideally just iterate on value changes
7762 we CSE PHIs and do that even across basic-block
7763 boundaries. So even hashtable state changes can
7764 be important (which is roughly equivalent to
7765 PHI argument value changes). To not excessively
7766 iterate because of that we track whether a PHI
7767 was CSEd to with GF_PLF_1. */
7768 bool phival_changed
;
7769 if ((phival_changed
= visit_phi (gsi
.phi (),
7771 || (inserted
&& gimple_plf (gsi
.phi (), GF_PLF_1
)))
7774 && dump_file
&& (dump_flags
& TDF_DETAILS
))
7775 fprintf (dump_file
, "PHI was CSEd and hashtable "
7776 "state (changed)\n");
7777 if (iterate_to
== -1 || destidx
< iterate_to
)
7778 iterate_to
= destidx
;
7782 vn_context_bb
= NULL
;
7784 if (iterate_to
!= -1)
7786 do_unwind (&rpo_state
[iterate_to
], avail
);
7788 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7789 fprintf (dump_file
, "Iterating to %d BB%d\n",
7790 iterate_to
, rpo
[iterate_to
]);
7800 /* Process all blocks greedily with a worklist that enforces RPO
7801 processing of reachable blocks. */
7802 auto_bitmap worklist
;
7803 bitmap_set_bit (worklist
, 0);
7804 while (!bitmap_empty_p (worklist
))
7806 int idx
= bitmap_first_set_bit (worklist
);
7807 bitmap_clear_bit (worklist
, idx
);
7808 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[idx
]);
7809 gcc_assert ((bb
->flags
& BB_EXECUTABLE
)
7810 && !rpo_state
[idx
].visited
);
7812 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7813 fprintf (dump_file
, "Processing block %d: BB%d\n", idx
, bb
->index
);
7815 /* When we run into predecessor edges where we cannot trust its
7816 executable state mark them executable so PHI processing will
7818 ??? Do we need to force arguments flowing over that edge
7819 to be varying or will they even always be? */
7822 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
7823 if (!(e
->flags
& EDGE_EXECUTABLE
)
7824 && (bb
== entry
->dest
7825 || (!rpo_state
[bb_to_rpo
[e
->src
->index
]].visited
7826 && (rpo_state
[bb_to_rpo
[e
->src
->index
]].max_rpo
7829 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7830 fprintf (dump_file
, "Cannot trust state of predecessor "
7831 "edge %d -> %d, marking executable\n",
7832 e
->src
->index
, e
->dest
->index
);
7833 e
->flags
|= EDGE_EXECUTABLE
;
7837 todo
|= process_bb (avail
, bb
, false, false, false, eliminate
,
7838 do_region
, exit_bbs
,
7839 skip_entry_phis
&& bb
== entry
->dest
);
7840 rpo_state
[idx
].visited
++;
7842 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
7843 if ((e
->flags
& EDGE_EXECUTABLE
)
7844 && e
->dest
->index
!= EXIT_BLOCK
7845 && (!do_region
|| !bitmap_bit_p (exit_bbs
, e
->dest
->index
))
7846 && !rpo_state
[bb_to_rpo
[e
->dest
->index
]].visited
)
7847 bitmap_set_bit (worklist
, bb_to_rpo
[e
->dest
->index
]);
7851 /* If statistics or dump file active. */
7853 unsigned max_visited
= 1;
7854 for (int i
= 0; i
< n
; ++i
)
7856 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
7857 if (bb
->flags
& BB_EXECUTABLE
)
7859 statistics_histogram_event (cfun
, "RPO block visited times",
7860 rpo_state
[i
].visited
);
7861 if (rpo_state
[i
].visited
> max_visited
)
7862 max_visited
= rpo_state
[i
].visited
;
7864 unsigned nvalues
= 0, navail
= 0;
7865 for (hash_table
<vn_ssa_aux_hasher
>::iterator i
= vn_ssa_aux_hash
->begin ();
7866 i
!= vn_ssa_aux_hash
->end (); ++i
)
7869 vn_avail
*av
= (*i
)->avail
;
7876 statistics_counter_event (cfun
, "RPO blocks", n
);
7877 statistics_counter_event (cfun
, "RPO blocks visited", nblk
);
7878 statistics_counter_event (cfun
, "RPO blocks executable", nex
);
7879 statistics_histogram_event (cfun
, "RPO iterations", 10*nblk
/ nex
);
7880 statistics_histogram_event (cfun
, "RPO num values", nvalues
);
7881 statistics_histogram_event (cfun
, "RPO num avail", navail
);
7882 statistics_histogram_event (cfun
, "RPO num lattice",
7883 vn_ssa_aux_hash
->elements ());
7884 if (dump_file
&& (dump_flags
& (TDF_DETAILS
|TDF_STATS
)))
7886 fprintf (dump_file
, "RPO iteration over %d blocks visited %" PRIu64
7887 " blocks in total discovering %d executable blocks iterating "
7888 "%d.%d times, a block was visited max. %u times\n",
7890 (int)((10*nblk
/ nex
)/10), (int)((10*nblk
/ nex
)%10),
7892 fprintf (dump_file
, "RPO tracked %d values available at %d locations "
7893 "and %" PRIu64
" lattice elements\n",
7894 nvalues
, navail
, (uint64_t) vn_ssa_aux_hash
->elements ());
7899 /* When !iterate we already performed elimination during the RPO
7903 /* Elimination for region-based VN needs to be done within the
7905 gcc_assert (! do_region
);
7906 /* Note we can't use avail.walk here because that gets confused
7907 by the existing availability and it will be less efficient
7909 todo
|= eliminate_with_rpo_vn (NULL
);
7912 todo
|= avail
.eliminate_cleanup (do_region
);
7918 XDELETEVEC (bb_to_rpo
);
7920 XDELETEVEC (rpo_state
);
7925 /* Region-based entry for RPO VN. Performs value-numbering and elimination
7926 on the SEME region specified by ENTRY and EXIT_BBS. If ENTRY is not
7927 the only edge into the region at ENTRY->dest PHI nodes in ENTRY->dest
7928 are not considered. */
7931 do_rpo_vn (function
*fn
, edge entry
, bitmap exit_bbs
)
7933 default_vn_walk_kind
= VN_WALKREWRITE
;
7934 unsigned todo
= do_rpo_vn (fn
, entry
, exit_bbs
, false, true);
7942 const pass_data pass_data_fre
=
7944 GIMPLE_PASS
, /* type */
7946 OPTGROUP_NONE
, /* optinfo_flags */
7947 TV_TREE_FRE
, /* tv_id */
7948 ( PROP_cfg
| PROP_ssa
), /* properties_required */
7949 0, /* properties_provided */
7950 0, /* properties_destroyed */
7951 0, /* todo_flags_start */
7952 0, /* todo_flags_finish */
7955 class pass_fre
: public gimple_opt_pass
7958 pass_fre (gcc::context
*ctxt
)
7959 : gimple_opt_pass (pass_data_fre
, ctxt
), may_iterate (true)
7962 /* opt_pass methods: */
7963 opt_pass
* clone () { return new pass_fre (m_ctxt
); }
7964 void set_pass_param (unsigned int n
, bool param
)
7966 gcc_assert (n
== 0);
7967 may_iterate
= param
;
7969 virtual bool gate (function
*)
7971 return flag_tree_fre
!= 0 && (may_iterate
|| optimize
> 1);
7973 virtual unsigned int execute (function
*);
7977 }; // class pass_fre
7980 pass_fre::execute (function
*fun
)
7984 /* At -O[1g] use the cheap non-iterating mode. */
7985 bool iterate_p
= may_iterate
&& (optimize
> 1);
7986 calculate_dominance_info (CDI_DOMINATORS
);
7988 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
7990 default_vn_walk_kind
= VN_WALKREWRITE
;
7991 todo
= do_rpo_vn (fun
, NULL
, NULL
, iterate_p
, true);
7995 loop_optimizer_finalize ();
7997 if (scev_initialized_p ())
8000 /* For late FRE after IVOPTs and unrolling, see if we can
8001 remove some TREE_ADDRESSABLE and rewrite stuff into SSA. */
8003 todo
|= TODO_update_address_taken
;
8011 make_pass_fre (gcc::context
*ctxt
)
8013 return new pass_fre (ctxt
);
8016 #undef BB_EXECUTABLE