1 /* SCC value numbering for trees
2 Copyright (C) 2006-2019 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"
57 #include "tree-ssa-propagate.h"
60 #include "gimple-iterator.h"
61 #include "gimple-match.h"
62 #include "stringpool.h"
64 #include "tree-pass.h"
65 #include "statistics.h"
66 #include "langhooks.h"
67 #include "ipa-utils.h"
69 #include "tree-cfgcleanup.h"
70 #include "tree-ssa-loop.h"
71 #include "tree-scalar-evolution.h"
72 #include "tree-ssa-loop-niter.h"
74 #include "tree-ssa-sccvn.h"
76 /* This algorithm is based on the SCC algorithm presented by Keith
77 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
78 (http://citeseer.ist.psu.edu/41805.html). In
79 straight line code, it is equivalent to a regular hash based value
80 numbering that is performed in reverse postorder.
82 For code with cycles, there are two alternatives, both of which
83 require keeping the hashtables separate from the actual list of
84 value numbers for SSA names.
86 1. Iterate value numbering in an RPO walk of the blocks, removing
87 all the entries from the hashtable after each iteration (but
88 keeping the SSA name->value number mapping between iterations).
89 Iterate until it does not change.
91 2. Perform value numbering as part of an SCC walk on the SSA graph,
92 iterating only the cycles in the SSA graph until they do not change
93 (using a separate, optimistic hashtable for value numbering the SCC
96 The second is not just faster in practice (because most SSA graph
97 cycles do not involve all the variables in the graph), it also has
100 One of these nice properties is that when we pop an SCC off the
101 stack, we are guaranteed to have processed all the operands coming from
102 *outside of that SCC*, so we do not need to do anything special to
103 ensure they have value numbers.
105 Another nice property is that the SCC walk is done as part of a DFS
106 of the SSA graph, which makes it easy to perform combining and
107 simplifying operations at the same time.
109 The code below is deliberately written in a way that makes it easy
110 to separate the SCC walk from the other work it does.
112 In order to propagate constants through the code, we track which
113 expressions contain constants, and use those while folding. In
114 theory, we could also track expressions whose value numbers are
115 replaced, in case we end up folding based on expression
118 In order to value number memory, we assign value numbers to vuses.
119 This enables us to note that, for example, stores to the same
120 address of the same value from the same starting memory states are
124 1. We can iterate only the changing portions of the SCC's, but
125 I have not seen an SCC big enough for this to be a win.
126 2. If you differentiate between phi nodes for loops and phi nodes
127 for if-then-else, you can properly consider phi nodes in different
128 blocks for equivalence.
129 3. We could value number vuses in more cases, particularly, whole
133 /* There's no BB_EXECUTABLE but we can use BB_VISITED. */
134 #define BB_EXECUTABLE BB_VISITED
136 static vn_lookup_kind default_vn_walk_kind
;
138 /* vn_nary_op hashtable helpers. */
140 struct vn_nary_op_hasher
: nofree_ptr_hash
<vn_nary_op_s
>
142 typedef vn_nary_op_s
*compare_type
;
143 static inline hashval_t
hash (const vn_nary_op_s
*);
144 static inline bool equal (const vn_nary_op_s
*, const vn_nary_op_s
*);
147 /* Return the computed hashcode for nary operation P1. */
150 vn_nary_op_hasher::hash (const vn_nary_op_s
*vno1
)
152 return vno1
->hashcode
;
155 /* Compare nary operations P1 and P2 and return true if they are
159 vn_nary_op_hasher::equal (const vn_nary_op_s
*vno1
, const vn_nary_op_s
*vno2
)
161 return vno1
== vno2
|| vn_nary_op_eq (vno1
, vno2
);
164 typedef hash_table
<vn_nary_op_hasher
> vn_nary_op_table_type
;
165 typedef vn_nary_op_table_type::iterator vn_nary_op_iterator_type
;
168 /* vn_phi hashtable helpers. */
171 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
);
173 struct vn_phi_hasher
: nofree_ptr_hash
<vn_phi_s
>
175 static inline hashval_t
hash (const vn_phi_s
*);
176 static inline bool equal (const vn_phi_s
*, const vn_phi_s
*);
179 /* Return the computed hashcode for phi operation P1. */
182 vn_phi_hasher::hash (const vn_phi_s
*vp1
)
184 return vp1
->hashcode
;
187 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
190 vn_phi_hasher::equal (const vn_phi_s
*vp1
, const vn_phi_s
*vp2
)
192 return vp1
== vp2
|| vn_phi_eq (vp1
, vp2
);
195 typedef hash_table
<vn_phi_hasher
> vn_phi_table_type
;
196 typedef vn_phi_table_type::iterator vn_phi_iterator_type
;
199 /* Compare two reference operands P1 and P2 for equality. Return true if
200 they are equal, and false otherwise. */
203 vn_reference_op_eq (const void *p1
, const void *p2
)
205 const_vn_reference_op_t
const vro1
= (const_vn_reference_op_t
) p1
;
206 const_vn_reference_op_t
const vro2
= (const_vn_reference_op_t
) p2
;
208 return (vro1
->opcode
== vro2
->opcode
209 /* We do not care for differences in type qualification. */
210 && (vro1
->type
== vro2
->type
211 || (vro1
->type
&& vro2
->type
212 && types_compatible_p (TYPE_MAIN_VARIANT (vro1
->type
),
213 TYPE_MAIN_VARIANT (vro2
->type
))))
214 && expressions_equal_p (vro1
->op0
, vro2
->op0
)
215 && expressions_equal_p (vro1
->op1
, vro2
->op1
)
216 && expressions_equal_p (vro1
->op2
, vro2
->op2
));
219 /* Free a reference operation structure VP. */
222 free_reference (vn_reference_s
*vr
)
224 vr
->operands
.release ();
228 /* vn_reference hashtable helpers. */
230 struct vn_reference_hasher
: nofree_ptr_hash
<vn_reference_s
>
232 static inline hashval_t
hash (const vn_reference_s
*);
233 static inline bool equal (const vn_reference_s
*, const vn_reference_s
*);
236 /* Return the hashcode for a given reference operation P1. */
239 vn_reference_hasher::hash (const vn_reference_s
*vr1
)
241 return vr1
->hashcode
;
245 vn_reference_hasher::equal (const vn_reference_s
*v
, const vn_reference_s
*c
)
247 return v
== c
|| vn_reference_eq (v
, c
);
250 typedef hash_table
<vn_reference_hasher
> vn_reference_table_type
;
251 typedef vn_reference_table_type::iterator vn_reference_iterator_type
;
254 /* The set of VN hashtables. */
256 typedef struct vn_tables_s
258 vn_nary_op_table_type
*nary
;
259 vn_phi_table_type
*phis
;
260 vn_reference_table_type
*references
;
264 /* vn_constant hashtable helpers. */
266 struct vn_constant_hasher
: free_ptr_hash
<vn_constant_s
>
268 static inline hashval_t
hash (const vn_constant_s
*);
269 static inline bool equal (const vn_constant_s
*, const vn_constant_s
*);
272 /* Hash table hash function for vn_constant_t. */
275 vn_constant_hasher::hash (const vn_constant_s
*vc1
)
277 return vc1
->hashcode
;
280 /* Hash table equality function for vn_constant_t. */
283 vn_constant_hasher::equal (const vn_constant_s
*vc1
, const vn_constant_s
*vc2
)
285 if (vc1
->hashcode
!= vc2
->hashcode
)
288 return vn_constant_eq_with_type (vc1
->constant
, vc2
->constant
);
291 static hash_table
<vn_constant_hasher
> *constant_to_value_id
;
292 static bitmap constant_value_ids
;
295 /* Obstack we allocate the vn-tables elements from. */
296 static obstack vn_tables_obstack
;
297 /* Special obstack we never unwind. */
298 static obstack vn_tables_insert_obstack
;
300 static vn_reference_t last_inserted_ref
;
301 static vn_phi_t last_inserted_phi
;
302 static vn_nary_op_t last_inserted_nary
;
304 /* Valid hashtables storing information we have proven to be
306 static vn_tables_t valid_info
;
309 /* Valueization hook. Valueize NAME if it is an SSA name, otherwise
311 tree (*vn_valueize
) (tree
);
314 /* This represents the top of the VN lattice, which is the universal
319 /* Unique counter for our value ids. */
321 static unsigned int next_value_id
;
324 /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects
325 are allocated on an obstack for locality reasons, and to free them
326 without looping over the vec. */
328 struct vn_ssa_aux_hasher
: typed_noop_remove
<vn_ssa_aux_t
>
330 typedef vn_ssa_aux_t value_type
;
331 typedef tree compare_type
;
332 static inline hashval_t
hash (const value_type
&);
333 static inline bool equal (const value_type
&, const compare_type
&);
334 static inline void mark_deleted (value_type
&) {}
335 static inline void mark_empty (value_type
&e
) { e
= NULL
; }
336 static inline bool is_deleted (value_type
&) { return false; }
337 static inline bool is_empty (value_type
&e
) { return e
== NULL
; }
341 vn_ssa_aux_hasher::hash (const value_type
&entry
)
343 return SSA_NAME_VERSION (entry
->name
);
347 vn_ssa_aux_hasher::equal (const value_type
&entry
, const compare_type
&name
)
349 return name
== entry
->name
;
352 static hash_table
<vn_ssa_aux_hasher
> *vn_ssa_aux_hash
;
353 typedef hash_table
<vn_ssa_aux_hasher
>::iterator vn_ssa_aux_iterator_type
;
354 static struct obstack vn_ssa_aux_obstack
;
356 static vn_nary_op_t
vn_nary_op_insert_stmt (gimple
*, tree
);
357 static unsigned int vn_nary_length_from_stmt (gimple
*);
358 static vn_nary_op_t
alloc_vn_nary_op_noinit (unsigned int, obstack
*);
359 static vn_nary_op_t
vn_nary_op_insert_into (vn_nary_op_t
,
360 vn_nary_op_table_type
*, bool);
361 static void init_vn_nary_op_from_stmt (vn_nary_op_t
, gimple
*);
362 static void init_vn_nary_op_from_pieces (vn_nary_op_t
, unsigned int,
363 enum tree_code
, tree
, tree
*);
364 static tree
vn_lookup_simplify_result (gimple_match_op
*);
365 static vn_reference_t vn_reference_lookup_or_insert_for_pieces
366 (tree
, alias_set_type
, tree
, vec
<vn_reference_op_s
, va_heap
>, tree
);
368 /* Return whether there is value numbering information for a given SSA name. */
371 has_VN_INFO (tree name
)
373 return vn_ssa_aux_hash
->find_with_hash (name
, SSA_NAME_VERSION (name
));
380 = vn_ssa_aux_hash
->find_slot_with_hash (name
, SSA_NAME_VERSION (name
),
385 vn_ssa_aux_t newinfo
= *res
= XOBNEW (&vn_ssa_aux_obstack
, struct vn_ssa_aux
);
386 memset (newinfo
, 0, sizeof (struct vn_ssa_aux
));
387 newinfo
->name
= name
;
388 newinfo
->valnum
= VN_TOP
;
389 /* We are using the visited flag to handle uses with defs not within the
390 region being value-numbered. */
391 newinfo
->visited
= false;
393 /* Given we create the VN_INFOs on-demand now we have to do initialization
394 different than VN_TOP here. */
395 if (SSA_NAME_IS_DEFAULT_DEF (name
))
396 switch (TREE_CODE (SSA_NAME_VAR (name
)))
399 /* All undefined vars are VARYING. */
400 newinfo
->valnum
= name
;
401 newinfo
->visited
= true;
405 /* Parameters are VARYING but we can record a condition
406 if we know it is a non-NULL pointer. */
407 newinfo
->visited
= true;
408 newinfo
->valnum
= name
;
409 if (POINTER_TYPE_P (TREE_TYPE (name
))
410 && nonnull_arg_p (SSA_NAME_VAR (name
)))
414 ops
[1] = build_int_cst (TREE_TYPE (name
), 0);
416 /* Allocate from non-unwinding stack. */
417 nary
= alloc_vn_nary_op_noinit (2, &vn_tables_insert_obstack
);
418 init_vn_nary_op_from_pieces (nary
, 2, NE_EXPR
,
419 boolean_type_node
, ops
);
420 nary
->predicated_values
= 0;
421 nary
->u
.result
= boolean_true_node
;
422 vn_nary_op_insert_into (nary
, valid_info
->nary
, true);
423 gcc_assert (nary
->unwind_to
== NULL
);
424 /* Also do not link it into the undo chain. */
425 last_inserted_nary
= nary
->next
;
426 nary
->next
= (vn_nary_op_t
)(void *)-1;
427 nary
= alloc_vn_nary_op_noinit (2, &vn_tables_insert_obstack
);
428 init_vn_nary_op_from_pieces (nary
, 2, EQ_EXPR
,
429 boolean_type_node
, ops
);
430 nary
->predicated_values
= 0;
431 nary
->u
.result
= boolean_false_node
;
432 vn_nary_op_insert_into (nary
, valid_info
->nary
, true);
433 gcc_assert (nary
->unwind_to
== NULL
);
434 last_inserted_nary
= nary
->next
;
435 nary
->next
= (vn_nary_op_t
)(void *)-1;
436 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
438 fprintf (dump_file
, "Recording ");
439 print_generic_expr (dump_file
, name
, TDF_SLIM
);
440 fprintf (dump_file
, " != 0\n");
446 /* If the result is passed by invisible reference the default
447 def is initialized, otherwise it's uninitialized. Still
448 undefined is varying. */
449 newinfo
->visited
= true;
450 newinfo
->valnum
= name
;
459 /* Return the SSA value of X. */
462 SSA_VAL (tree x
, bool *visited
= NULL
)
464 vn_ssa_aux_t tem
= vn_ssa_aux_hash
->find_with_hash (x
, SSA_NAME_VERSION (x
));
466 *visited
= tem
&& tem
->visited
;
467 return tem
&& tem
->visited
? tem
->valnum
: x
;
470 /* Return the SSA value of the VUSE x, supporting released VDEFs
471 during elimination which will value-number the VDEF to the
472 associated VUSE (but not substitute in the whole lattice). */
475 vuse_ssa_val (tree x
)
483 gcc_assert (x
!= VN_TOP
);
485 while (SSA_NAME_IN_FREE_LIST (x
));
490 /* Similar to the above but used as callback for walk_non_aliases_vuses
491 and thus should stop at unvisited VUSE to not walk across region
495 vuse_valueize (tree vuse
)
500 vuse
= SSA_VAL (vuse
, &visited
);
503 gcc_assert (vuse
!= VN_TOP
);
505 while (SSA_NAME_IN_FREE_LIST (vuse
));
510 /* Return the vn_kind the expression computed by the stmt should be
514 vn_get_stmt_kind (gimple
*stmt
)
516 switch (gimple_code (stmt
))
524 enum tree_code code
= gimple_assign_rhs_code (stmt
);
525 tree rhs1
= gimple_assign_rhs1 (stmt
);
526 switch (get_gimple_rhs_class (code
))
528 case GIMPLE_UNARY_RHS
:
529 case GIMPLE_BINARY_RHS
:
530 case GIMPLE_TERNARY_RHS
:
532 case GIMPLE_SINGLE_RHS
:
533 switch (TREE_CODE_CLASS (code
))
536 /* VOP-less references can go through unary case. */
537 if ((code
== REALPART_EXPR
538 || code
== IMAGPART_EXPR
539 || code
== VIEW_CONVERT_EXPR
540 || code
== BIT_FIELD_REF
)
541 && TREE_CODE (TREE_OPERAND (rhs1
, 0)) == SSA_NAME
)
545 case tcc_declaration
:
552 if (code
== ADDR_EXPR
)
553 return (is_gimple_min_invariant (rhs1
)
554 ? VN_CONSTANT
: VN_REFERENCE
);
555 else if (code
== CONSTRUCTOR
)
568 /* Lookup a value id for CONSTANT and return it. If it does not
572 get_constant_value_id (tree constant
)
574 vn_constant_s
**slot
;
575 struct vn_constant_s vc
;
577 vc
.hashcode
= vn_hash_constant_with_type (constant
);
578 vc
.constant
= constant
;
579 slot
= constant_to_value_id
->find_slot (&vc
, NO_INSERT
);
581 return (*slot
)->value_id
;
585 /* Lookup a value id for CONSTANT, and if it does not exist, create a
586 new one and return it. If it does exist, return it. */
589 get_or_alloc_constant_value_id (tree constant
)
591 vn_constant_s
**slot
;
592 struct vn_constant_s vc
;
595 /* If the hashtable isn't initialized we're not running from PRE and thus
596 do not need value-ids. */
597 if (!constant_to_value_id
)
600 vc
.hashcode
= vn_hash_constant_with_type (constant
);
601 vc
.constant
= constant
;
602 slot
= constant_to_value_id
->find_slot (&vc
, INSERT
);
604 return (*slot
)->value_id
;
606 vcp
= XNEW (struct vn_constant_s
);
607 vcp
->hashcode
= vc
.hashcode
;
608 vcp
->constant
= constant
;
609 vcp
->value_id
= get_next_value_id ();
611 bitmap_set_bit (constant_value_ids
, vcp
->value_id
);
612 return vcp
->value_id
;
615 /* Return true if V is a value id for a constant. */
618 value_id_constant_p (unsigned int v
)
620 return bitmap_bit_p (constant_value_ids
, v
);
623 /* Compute the hash for a reference operand VRO1. */
626 vn_reference_op_compute_hash (const vn_reference_op_t vro1
, inchash::hash
&hstate
)
628 hstate
.add_int (vro1
->opcode
);
630 inchash::add_expr (vro1
->op0
, hstate
);
632 inchash::add_expr (vro1
->op1
, hstate
);
634 inchash::add_expr (vro1
->op2
, hstate
);
637 /* Compute a hash for the reference operation VR1 and return it. */
640 vn_reference_compute_hash (const vn_reference_t vr1
)
642 inchash::hash hstate
;
645 vn_reference_op_t vro
;
649 FOR_EACH_VEC_ELT (vr1
->operands
, i
, vro
)
651 if (vro
->opcode
== MEM_REF
)
653 else if (vro
->opcode
!= ADDR_EXPR
)
655 if (maybe_ne (vro
->off
, -1))
657 if (known_eq (off
, -1))
663 if (maybe_ne (off
, -1)
664 && maybe_ne (off
, 0))
665 hstate
.add_poly_int (off
);
668 && vro
->opcode
== ADDR_EXPR
)
672 tree op
= TREE_OPERAND (vro
->op0
, 0);
673 hstate
.add_int (TREE_CODE (op
));
674 inchash::add_expr (op
, hstate
);
678 vn_reference_op_compute_hash (vro
, hstate
);
681 result
= hstate
.end ();
682 /* ??? We would ICE later if we hash instead of adding that in. */
684 result
+= SSA_NAME_VERSION (vr1
->vuse
);
689 /* Return true if reference operations VR1 and VR2 are equivalent. This
690 means they have the same set of operands and vuses. */
693 vn_reference_eq (const_vn_reference_t
const vr1
, const_vn_reference_t
const vr2
)
697 /* Early out if this is not a hash collision. */
698 if (vr1
->hashcode
!= vr2
->hashcode
)
701 /* The VOP needs to be the same. */
702 if (vr1
->vuse
!= vr2
->vuse
)
705 /* If the operands are the same we are done. */
706 if (vr1
->operands
== vr2
->operands
)
709 if (!expressions_equal_p (TYPE_SIZE (vr1
->type
), TYPE_SIZE (vr2
->type
)))
712 if (INTEGRAL_TYPE_P (vr1
->type
)
713 && INTEGRAL_TYPE_P (vr2
->type
))
715 if (TYPE_PRECISION (vr1
->type
) != TYPE_PRECISION (vr2
->type
))
718 else if (INTEGRAL_TYPE_P (vr1
->type
)
719 && (TYPE_PRECISION (vr1
->type
)
720 != TREE_INT_CST_LOW (TYPE_SIZE (vr1
->type
))))
722 else if (INTEGRAL_TYPE_P (vr2
->type
)
723 && (TYPE_PRECISION (vr2
->type
)
724 != TREE_INT_CST_LOW (TYPE_SIZE (vr2
->type
))))
731 poly_int64 off1
= 0, off2
= 0;
732 vn_reference_op_t vro1
, vro2
;
733 vn_reference_op_s tem1
, tem2
;
734 bool deref1
= false, deref2
= false;
735 for (; vr1
->operands
.iterate (i
, &vro1
); i
++)
737 if (vro1
->opcode
== MEM_REF
)
739 /* Do not look through a storage order barrier. */
740 else if (vro1
->opcode
== VIEW_CONVERT_EXPR
&& vro1
->reverse
)
742 if (known_eq (vro1
->off
, -1))
746 for (; vr2
->operands
.iterate (j
, &vro2
); j
++)
748 if (vro2
->opcode
== MEM_REF
)
750 /* Do not look through a storage order barrier. */
751 else if (vro2
->opcode
== VIEW_CONVERT_EXPR
&& vro2
->reverse
)
753 if (known_eq (vro2
->off
, -1))
757 if (maybe_ne (off1
, off2
))
759 if (deref1
&& vro1
->opcode
== ADDR_EXPR
)
761 memset (&tem1
, 0, sizeof (tem1
));
762 tem1
.op0
= TREE_OPERAND (vro1
->op0
, 0);
763 tem1
.type
= TREE_TYPE (tem1
.op0
);
764 tem1
.opcode
= TREE_CODE (tem1
.op0
);
768 if (deref2
&& vro2
->opcode
== ADDR_EXPR
)
770 memset (&tem2
, 0, sizeof (tem2
));
771 tem2
.op0
= TREE_OPERAND (vro2
->op0
, 0);
772 tem2
.type
= TREE_TYPE (tem2
.op0
);
773 tem2
.opcode
= TREE_CODE (tem2
.op0
);
777 if (deref1
!= deref2
)
779 if (!vn_reference_op_eq (vro1
, vro2
))
784 while (vr1
->operands
.length () != i
785 || vr2
->operands
.length () != j
);
790 /* Copy the operations present in load/store REF into RESULT, a vector of
791 vn_reference_op_s's. */
794 copy_reference_ops_from_ref (tree ref
, vec
<vn_reference_op_s
> *result
)
796 /* For non-calls, store the information that makes up the address. */
800 vn_reference_op_s temp
;
802 memset (&temp
, 0, sizeof (temp
));
803 temp
.type
= TREE_TYPE (ref
);
804 temp
.opcode
= TREE_CODE (ref
);
810 temp
.op0
= TREE_OPERAND (ref
, 1);
813 temp
.op0
= TREE_OPERAND (ref
, 1);
817 /* The base address gets its own vn_reference_op_s structure. */
818 temp
.op0
= TREE_OPERAND (ref
, 1);
819 if (!mem_ref_offset (ref
).to_shwi (&temp
.off
))
821 temp
.clique
= MR_DEPENDENCE_CLIQUE (ref
);
822 temp
.base
= MR_DEPENDENCE_BASE (ref
);
823 temp
.reverse
= REF_REVERSE_STORAGE_ORDER (ref
);
826 /* The base address gets its own vn_reference_op_s structure. */
827 temp
.op0
= TMR_INDEX (ref
);
828 temp
.op1
= TMR_STEP (ref
);
829 temp
.op2
= TMR_OFFSET (ref
);
830 temp
.clique
= MR_DEPENDENCE_CLIQUE (ref
);
831 temp
.base
= MR_DEPENDENCE_BASE (ref
);
832 result
->safe_push (temp
);
833 memset (&temp
, 0, sizeof (temp
));
834 temp
.type
= NULL_TREE
;
835 temp
.opcode
= ERROR_MARK
;
836 temp
.op0
= TMR_INDEX2 (ref
);
840 /* Record bits, position and storage order. */
841 temp
.op0
= TREE_OPERAND (ref
, 1);
842 temp
.op1
= TREE_OPERAND (ref
, 2);
843 if (!multiple_p (bit_field_offset (ref
), BITS_PER_UNIT
, &temp
.off
))
845 temp
.reverse
= REF_REVERSE_STORAGE_ORDER (ref
);
848 /* The field decl is enough to unambiguously specify the field,
849 a matching type is not necessary and a mismatching type
850 is always a spurious difference. */
851 temp
.type
= NULL_TREE
;
852 temp
.op0
= TREE_OPERAND (ref
, 1);
853 temp
.op1
= TREE_OPERAND (ref
, 2);
855 tree this_offset
= component_ref_field_offset (ref
);
857 && poly_int_tree_p (this_offset
))
859 tree bit_offset
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
860 if (TREE_INT_CST_LOW (bit_offset
) % BITS_PER_UNIT
== 0)
863 = (wi::to_poly_offset (this_offset
)
864 + (wi::to_offset (bit_offset
) >> LOG2_BITS_PER_UNIT
));
865 /* Probibit value-numbering zero offset components
866 of addresses the same before the pass folding
867 __builtin_object_size had a chance to run
868 (checking cfun->after_inlining does the
870 if (TREE_CODE (orig
) != ADDR_EXPR
872 || cfun
->after_inlining
)
873 off
.to_shwi (&temp
.off
);
878 case ARRAY_RANGE_REF
:
881 tree eltype
= TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref
, 0)));
882 /* Record index as operand. */
883 temp
.op0
= TREE_OPERAND (ref
, 1);
884 /* Always record lower bounds and element size. */
885 temp
.op1
= array_ref_low_bound (ref
);
886 /* But record element size in units of the type alignment. */
887 temp
.op2
= TREE_OPERAND (ref
, 3);
888 temp
.align
= eltype
->type_common
.align
;
890 temp
.op2
= size_binop (EXACT_DIV_EXPR
, TYPE_SIZE_UNIT (eltype
),
891 size_int (TYPE_ALIGN_UNIT (eltype
)));
892 if (poly_int_tree_p (temp
.op0
)
893 && poly_int_tree_p (temp
.op1
)
894 && TREE_CODE (temp
.op2
) == INTEGER_CST
)
896 poly_offset_int off
= ((wi::to_poly_offset (temp
.op0
)
897 - wi::to_poly_offset (temp
.op1
))
898 * wi::to_offset (temp
.op2
)
899 * vn_ref_op_align_unit (&temp
));
900 off
.to_shwi (&temp
.off
);
905 if (DECL_HARD_REGISTER (ref
))
914 /* Canonicalize decls to MEM[&decl] which is what we end up with
915 when valueizing MEM[ptr] with ptr = &decl. */
916 temp
.opcode
= MEM_REF
;
917 temp
.op0
= build_int_cst (build_pointer_type (TREE_TYPE (ref
)), 0);
919 result
->safe_push (temp
);
920 temp
.opcode
= ADDR_EXPR
;
921 temp
.op0
= build1 (ADDR_EXPR
, TREE_TYPE (temp
.op0
), ref
);
922 temp
.type
= TREE_TYPE (temp
.op0
);
936 if (is_gimple_min_invariant (ref
))
942 /* These are only interesting for their operands, their
943 existence, and their type. They will never be the last
944 ref in the chain of references (IE they require an
945 operand), so we don't have to put anything
946 for op* as it will be handled by the iteration */
950 case VIEW_CONVERT_EXPR
:
952 temp
.reverse
= storage_order_barrier_p (ref
);
955 /* This is only interesting for its constant offset. */
956 temp
.off
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref
)));
961 result
->safe_push (temp
);
963 if (REFERENCE_CLASS_P (ref
)
964 || TREE_CODE (ref
) == MODIFY_EXPR
965 || TREE_CODE (ref
) == WITH_SIZE_EXPR
966 || (TREE_CODE (ref
) == ADDR_EXPR
967 && !is_gimple_min_invariant (ref
)))
968 ref
= TREE_OPERAND (ref
, 0);
974 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
975 operands in *OPS, the reference alias set SET and the reference type TYPE.
976 Return true if something useful was produced. */
979 ao_ref_init_from_vn_reference (ao_ref
*ref
,
980 alias_set_type set
, tree type
,
981 vec
<vn_reference_op_s
> ops
)
983 vn_reference_op_t op
;
985 tree base
= NULL_TREE
;
987 poly_offset_int offset
= 0;
988 poly_offset_int max_size
;
989 poly_offset_int size
= -1;
990 tree size_tree
= NULL_TREE
;
991 alias_set_type base_alias_set
= -1;
993 /* First get the final access size from just the outermost expression. */
995 if (op
->opcode
== COMPONENT_REF
)
996 size_tree
= DECL_SIZE (op
->op0
);
997 else if (op
->opcode
== BIT_FIELD_REF
)
1001 machine_mode mode
= TYPE_MODE (type
);
1002 if (mode
== BLKmode
)
1003 size_tree
= TYPE_SIZE (type
);
1005 size
= GET_MODE_BITSIZE (mode
);
1007 if (size_tree
!= NULL_TREE
1008 && poly_int_tree_p (size_tree
))
1009 size
= wi::to_poly_offset (size_tree
);
1011 /* Initially, maxsize is the same as the accessed element size.
1012 In the following it will only grow (or become -1). */
1015 /* Compute cumulative bit-offset for nested component-refs and array-refs,
1016 and find the ultimate containing object. */
1017 FOR_EACH_VEC_ELT (ops
, i
, op
)
1021 /* These may be in the reference ops, but we cannot do anything
1022 sensible with them here. */
1024 /* Apart from ADDR_EXPR arguments to MEM_REF. */
1025 if (base
!= NULL_TREE
1026 && TREE_CODE (base
) == MEM_REF
1028 && DECL_P (TREE_OPERAND (op
->op0
, 0)))
1030 vn_reference_op_t pop
= &ops
[i
-1];
1031 base
= TREE_OPERAND (op
->op0
, 0);
1032 if (known_eq (pop
->off
, -1))
1038 offset
+= pop
->off
* BITS_PER_UNIT
;
1046 /* Record the base objects. */
1048 base_alias_set
= get_deref_alias_set (op
->op0
);
1049 *op0_p
= build2 (MEM_REF
, op
->type
,
1050 NULL_TREE
, op
->op0
);
1051 MR_DEPENDENCE_CLIQUE (*op0_p
) = op
->clique
;
1052 MR_DEPENDENCE_BASE (*op0_p
) = op
->base
;
1053 op0_p
= &TREE_OPERAND (*op0_p
, 0);
1064 /* And now the usual component-reference style ops. */
1066 offset
+= wi::to_poly_offset (op
->op1
);
1071 tree field
= op
->op0
;
1072 /* We do not have a complete COMPONENT_REF tree here so we
1073 cannot use component_ref_field_offset. Do the interesting
1075 tree this_offset
= DECL_FIELD_OFFSET (field
);
1077 if (op
->op1
|| !poly_int_tree_p (this_offset
))
1081 poly_offset_int woffset
= (wi::to_poly_offset (this_offset
)
1082 << LOG2_BITS_PER_UNIT
);
1083 woffset
+= wi::to_offset (DECL_FIELD_BIT_OFFSET (field
));
1089 case ARRAY_RANGE_REF
:
1091 /* We recorded the lower bound and the element size. */
1092 if (!poly_int_tree_p (op
->op0
)
1093 || !poly_int_tree_p (op
->op1
)
1094 || TREE_CODE (op
->op2
) != INTEGER_CST
)
1098 poly_offset_int woffset
1099 = wi::sext (wi::to_poly_offset (op
->op0
)
1100 - wi::to_poly_offset (op
->op1
),
1101 TYPE_PRECISION (TREE_TYPE (op
->op0
)));
1102 woffset
*= wi::to_offset (op
->op2
) * vn_ref_op_align_unit (op
);
1103 woffset
<<= LOG2_BITS_PER_UNIT
;
1115 case VIEW_CONVERT_EXPR
:
1132 if (base
== NULL_TREE
)
1135 ref
->ref
= NULL_TREE
;
1137 ref
->ref_alias_set
= set
;
1138 if (base_alias_set
!= -1)
1139 ref
->base_alias_set
= base_alias_set
;
1141 ref
->base_alias_set
= get_alias_set (base
);
1142 /* We discount volatiles from value-numbering elsewhere. */
1143 ref
->volatile_p
= false;
1145 if (!size
.to_shwi (&ref
->size
) || maybe_lt (ref
->size
, 0))
1153 if (!offset
.to_shwi (&ref
->offset
))
1160 if (!max_size
.to_shwi (&ref
->max_size
) || maybe_lt (ref
->max_size
, 0))
1166 /* Copy the operations present in load/store/call REF into RESULT, a vector of
1167 vn_reference_op_s's. */
1170 copy_reference_ops_from_call (gcall
*call
,
1171 vec
<vn_reference_op_s
> *result
)
1173 vn_reference_op_s temp
;
1175 tree lhs
= gimple_call_lhs (call
);
1178 /* If 2 calls have a different non-ssa lhs, vdef value numbers should be
1179 different. By adding the lhs here in the vector, we ensure that the
1180 hashcode is different, guaranteeing a different value number. */
1181 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
1183 memset (&temp
, 0, sizeof (temp
));
1184 temp
.opcode
= MODIFY_EXPR
;
1185 temp
.type
= TREE_TYPE (lhs
);
1188 result
->safe_push (temp
);
1191 /* Copy the type, opcode, function, static chain and EH region, if any. */
1192 memset (&temp
, 0, sizeof (temp
));
1193 temp
.type
= gimple_call_fntype (call
);
1194 temp
.opcode
= CALL_EXPR
;
1195 temp
.op0
= gimple_call_fn (call
);
1196 temp
.op1
= gimple_call_chain (call
);
1197 if (stmt_could_throw_p (cfun
, call
) && (lr
= lookup_stmt_eh_lp (call
)) > 0)
1198 temp
.op2
= size_int (lr
);
1200 result
->safe_push (temp
);
1202 /* Copy the call arguments. As they can be references as well,
1203 just chain them together. */
1204 for (i
= 0; i
< gimple_call_num_args (call
); ++i
)
1206 tree callarg
= gimple_call_arg (call
, i
);
1207 copy_reference_ops_from_ref (callarg
, result
);
1211 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1212 *I_P to point to the last element of the replacement. */
1214 vn_reference_fold_indirect (vec
<vn_reference_op_s
> *ops
,
1217 unsigned int i
= *i_p
;
1218 vn_reference_op_t op
= &(*ops
)[i
];
1219 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1221 poly_int64 addr_offset
= 0;
1223 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1224 from .foo.bar to the preceding MEM_REF offset and replace the
1225 address with &OBJ. */
1226 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (op
->op0
, 0),
1228 gcc_checking_assert (addr_base
&& TREE_CODE (addr_base
) != MEM_REF
);
1229 if (addr_base
!= TREE_OPERAND (op
->op0
, 0))
1232 = (poly_offset_int::from (wi::to_poly_wide (mem_op
->op0
),
1235 mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1236 op
->op0
= build_fold_addr_expr (addr_base
);
1237 if (tree_fits_shwi_p (mem_op
->op0
))
1238 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1246 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1247 *I_P to point to the last element of the replacement. */
1249 vn_reference_maybe_forwprop_address (vec
<vn_reference_op_s
> *ops
,
1252 unsigned int i
= *i_p
;
1253 vn_reference_op_t op
= &(*ops
)[i
];
1254 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1256 enum tree_code code
;
1257 poly_offset_int off
;
1259 def_stmt
= SSA_NAME_DEF_STMT (op
->op0
);
1260 if (!is_gimple_assign (def_stmt
))
1263 code
= gimple_assign_rhs_code (def_stmt
);
1264 if (code
!= ADDR_EXPR
1265 && code
!= POINTER_PLUS_EXPR
)
1268 off
= poly_offset_int::from (wi::to_poly_wide (mem_op
->op0
), SIGNED
);
1270 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1271 from .foo.bar to the preceding MEM_REF offset and replace the
1272 address with &OBJ. */
1273 if (code
== ADDR_EXPR
)
1275 tree addr
, addr_base
;
1276 poly_int64 addr_offset
;
1278 addr
= gimple_assign_rhs1 (def_stmt
);
1279 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (addr
, 0),
1281 /* If that didn't work because the address isn't invariant propagate
1282 the reference tree from the address operation in case the current
1283 dereference isn't offsetted. */
1285 && *i_p
== ops
->length () - 1
1286 && known_eq (off
, 0)
1287 /* This makes us disable this transform for PRE where the
1288 reference ops might be also used for code insertion which
1290 && default_vn_walk_kind
== VN_WALKREWRITE
)
1292 auto_vec
<vn_reference_op_s
, 32> tem
;
1293 copy_reference_ops_from_ref (TREE_OPERAND (addr
, 0), &tem
);
1294 /* Make sure to preserve TBAA info. The only objects not
1295 wrapped in MEM_REFs that can have their address taken are
1297 if (tem
.length () >= 2
1298 && tem
[tem
.length () - 2].opcode
== MEM_REF
)
1300 vn_reference_op_t new_mem_op
= &tem
[tem
.length () - 2];
1302 = wide_int_to_tree (TREE_TYPE (mem_op
->op0
),
1303 wi::to_poly_wide (new_mem_op
->op0
));
1306 gcc_assert (tem
.last ().opcode
== STRING_CST
);
1309 ops
->safe_splice (tem
);
1314 || TREE_CODE (addr_base
) != MEM_REF
1315 || (TREE_CODE (TREE_OPERAND (addr_base
, 0)) == SSA_NAME
1316 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (addr_base
, 0))))
1320 off
+= mem_ref_offset (addr_base
);
1321 op
->op0
= TREE_OPERAND (addr_base
, 0);
1326 ptr
= gimple_assign_rhs1 (def_stmt
);
1327 ptroff
= gimple_assign_rhs2 (def_stmt
);
1328 if (TREE_CODE (ptr
) != SSA_NAME
1329 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
)
1330 /* Make sure to not endlessly recurse.
1331 See gcc.dg/tree-ssa/20040408-1.c for an example. Can easily
1332 happen when we value-number a PHI to its backedge value. */
1333 || SSA_VAL (ptr
) == op
->op0
1334 || !poly_int_tree_p (ptroff
))
1337 off
+= wi::to_poly_offset (ptroff
);
1341 mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1342 if (tree_fits_shwi_p (mem_op
->op0
))
1343 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1346 /* ??? Can end up with endless recursion here!?
1347 gcc.c-torture/execute/strcmp-1.c */
1348 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1349 op
->op0
= SSA_VAL (op
->op0
);
1350 if (TREE_CODE (op
->op0
) != SSA_NAME
)
1351 op
->opcode
= TREE_CODE (op
->op0
);
1354 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1355 vn_reference_maybe_forwprop_address (ops
, i_p
);
1356 else if (TREE_CODE (op
->op0
) == ADDR_EXPR
)
1357 vn_reference_fold_indirect (ops
, i_p
);
1361 /* Optimize the reference REF to a constant if possible or return
1362 NULL_TREE if not. */
1365 fully_constant_vn_reference_p (vn_reference_t ref
)
1367 vec
<vn_reference_op_s
> operands
= ref
->operands
;
1368 vn_reference_op_t op
;
1370 /* Try to simplify the translated expression if it is
1371 a call to a builtin function with at most two arguments. */
1373 if (op
->opcode
== CALL_EXPR
1374 && TREE_CODE (op
->op0
) == ADDR_EXPR
1375 && TREE_CODE (TREE_OPERAND (op
->op0
, 0)) == FUNCTION_DECL
1376 && fndecl_built_in_p (TREE_OPERAND (op
->op0
, 0))
1377 && operands
.length () >= 2
1378 && operands
.length () <= 3)
1380 vn_reference_op_t arg0
, arg1
= NULL
;
1381 bool anyconst
= false;
1382 arg0
= &operands
[1];
1383 if (operands
.length () > 2)
1384 arg1
= &operands
[2];
1385 if (TREE_CODE_CLASS (arg0
->opcode
) == tcc_constant
1386 || (arg0
->opcode
== ADDR_EXPR
1387 && is_gimple_min_invariant (arg0
->op0
)))
1390 && (TREE_CODE_CLASS (arg1
->opcode
) == tcc_constant
1391 || (arg1
->opcode
== ADDR_EXPR
1392 && is_gimple_min_invariant (arg1
->op0
))))
1396 tree folded
= build_call_expr (TREE_OPERAND (op
->op0
, 0),
1399 arg1
? arg1
->op0
: NULL
);
1401 && TREE_CODE (folded
) == NOP_EXPR
)
1402 folded
= TREE_OPERAND (folded
, 0);
1404 && is_gimple_min_invariant (folded
))
1409 /* Simplify reads from constants or constant initializers. */
1410 else if (BITS_PER_UNIT
== 8
1411 && COMPLETE_TYPE_P (ref
->type
)
1412 && is_gimple_reg_type (ref
->type
))
1416 if (INTEGRAL_TYPE_P (ref
->type
))
1417 size
= TYPE_PRECISION (ref
->type
);
1418 else if (tree_fits_shwi_p (TYPE_SIZE (ref
->type
)))
1419 size
= tree_to_shwi (TYPE_SIZE (ref
->type
));
1422 if (size
% BITS_PER_UNIT
!= 0
1423 || size
> MAX_BITSIZE_MODE_ANY_MODE
)
1425 size
/= BITS_PER_UNIT
;
1427 for (i
= 0; i
< operands
.length (); ++i
)
1429 if (TREE_CODE_CLASS (operands
[i
].opcode
) == tcc_constant
)
1434 if (known_eq (operands
[i
].off
, -1))
1436 off
+= operands
[i
].off
;
1437 if (operands
[i
].opcode
== MEM_REF
)
1443 vn_reference_op_t base
= &operands
[--i
];
1444 tree ctor
= error_mark_node
;
1445 tree decl
= NULL_TREE
;
1446 if (TREE_CODE_CLASS (base
->opcode
) == tcc_constant
)
1448 else if (base
->opcode
== MEM_REF
1449 && base
[1].opcode
== ADDR_EXPR
1450 && (TREE_CODE (TREE_OPERAND (base
[1].op0
, 0)) == VAR_DECL
1451 || TREE_CODE (TREE_OPERAND (base
[1].op0
, 0)) == CONST_DECL
1452 || TREE_CODE (TREE_OPERAND (base
[1].op0
, 0)) == STRING_CST
))
1454 decl
= TREE_OPERAND (base
[1].op0
, 0);
1455 if (TREE_CODE (decl
) == STRING_CST
)
1458 ctor
= ctor_for_folding (decl
);
1460 if (ctor
== NULL_TREE
)
1461 return build_zero_cst (ref
->type
);
1462 else if (ctor
!= error_mark_node
)
1464 HOST_WIDE_INT const_off
;
1467 tree res
= fold_ctor_reference (ref
->type
, ctor
,
1468 off
* BITS_PER_UNIT
,
1469 size
* BITS_PER_UNIT
, decl
);
1472 STRIP_USELESS_TYPE_CONVERSION (res
);
1473 if (is_gimple_min_invariant (res
))
1477 else if (off
.is_constant (&const_off
))
1479 unsigned char buf
[MAX_BITSIZE_MODE_ANY_MODE
/ BITS_PER_UNIT
];
1480 int len
= native_encode_expr (ctor
, buf
, size
, const_off
);
1482 return native_interpret_expr (ref
->type
, buf
, len
);
1490 /* Return true if OPS contain a storage order barrier. */
1493 contains_storage_order_barrier_p (vec
<vn_reference_op_s
> ops
)
1495 vn_reference_op_t op
;
1498 FOR_EACH_VEC_ELT (ops
, i
, op
)
1499 if (op
->opcode
== VIEW_CONVERT_EXPR
&& op
->reverse
)
1505 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1506 structures into their value numbers. This is done in-place, and
1507 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1508 whether any operands were valueized. */
1510 static vec
<vn_reference_op_s
>
1511 valueize_refs_1 (vec
<vn_reference_op_s
> orig
, bool *valueized_anything
,
1512 bool with_avail
= false)
1514 vn_reference_op_t vro
;
1517 *valueized_anything
= false;
1519 FOR_EACH_VEC_ELT (orig
, i
, vro
)
1521 if (vro
->opcode
== SSA_NAME
1522 || (vro
->op0
&& TREE_CODE (vro
->op0
) == SSA_NAME
))
1524 tree tem
= with_avail
? vn_valueize (vro
->op0
) : SSA_VAL (vro
->op0
);
1525 if (tem
!= vro
->op0
)
1527 *valueized_anything
= true;
1530 /* If it transforms from an SSA_NAME to a constant, update
1532 if (TREE_CODE (vro
->op0
) != SSA_NAME
&& vro
->opcode
== SSA_NAME
)
1533 vro
->opcode
= TREE_CODE (vro
->op0
);
1535 if (vro
->op1
&& TREE_CODE (vro
->op1
) == SSA_NAME
)
1537 tree tem
= with_avail
? vn_valueize (vro
->op1
) : SSA_VAL (vro
->op1
);
1538 if (tem
!= vro
->op1
)
1540 *valueized_anything
= true;
1544 if (vro
->op2
&& TREE_CODE (vro
->op2
) == SSA_NAME
)
1546 tree tem
= with_avail
? vn_valueize (vro
->op2
) : SSA_VAL (vro
->op2
);
1547 if (tem
!= vro
->op2
)
1549 *valueized_anything
= true;
1553 /* If it transforms from an SSA_NAME to an address, fold with
1554 a preceding indirect reference. */
1557 && TREE_CODE (vro
->op0
) == ADDR_EXPR
1558 && orig
[i
- 1].opcode
== MEM_REF
)
1560 if (vn_reference_fold_indirect (&orig
, &i
))
1561 *valueized_anything
= true;
1564 && vro
->opcode
== SSA_NAME
1565 && orig
[i
- 1].opcode
== MEM_REF
)
1567 if (vn_reference_maybe_forwprop_address (&orig
, &i
))
1568 *valueized_anything
= true;
1570 /* If it transforms a non-constant ARRAY_REF into a constant
1571 one, adjust the constant offset. */
1572 else if (vro
->opcode
== ARRAY_REF
1573 && known_eq (vro
->off
, -1)
1574 && poly_int_tree_p (vro
->op0
)
1575 && poly_int_tree_p (vro
->op1
)
1576 && TREE_CODE (vro
->op2
) == INTEGER_CST
)
1578 poly_offset_int off
= ((wi::to_poly_offset (vro
->op0
)
1579 - wi::to_poly_offset (vro
->op1
))
1580 * wi::to_offset (vro
->op2
)
1581 * vn_ref_op_align_unit (vro
));
1582 off
.to_shwi (&vro
->off
);
1589 static vec
<vn_reference_op_s
>
1590 valueize_refs (vec
<vn_reference_op_s
> orig
)
1593 return valueize_refs_1 (orig
, &tem
);
1596 static vec
<vn_reference_op_s
> shared_lookup_references
;
1598 /* Create a vector of vn_reference_op_s structures from REF, a
1599 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1600 this function. *VALUEIZED_ANYTHING will specify whether any
1601 operands were valueized. */
1603 static vec
<vn_reference_op_s
>
1604 valueize_shared_reference_ops_from_ref (tree ref
, bool *valueized_anything
)
1608 shared_lookup_references
.truncate (0);
1609 copy_reference_ops_from_ref (ref
, &shared_lookup_references
);
1610 shared_lookup_references
= valueize_refs_1 (shared_lookup_references
,
1611 valueized_anything
);
1612 return shared_lookup_references
;
1615 /* Create a vector of vn_reference_op_s structures from CALL, a
1616 call statement. The vector is shared among all callers of
1619 static vec
<vn_reference_op_s
>
1620 valueize_shared_reference_ops_from_call (gcall
*call
)
1624 shared_lookup_references
.truncate (0);
1625 copy_reference_ops_from_call (call
, &shared_lookup_references
);
1626 shared_lookup_references
= valueize_refs (shared_lookup_references
);
1627 return shared_lookup_references
;
1630 /* Lookup a SCCVN reference operation VR in the current hash table.
1631 Returns the resulting value number if it exists in the hash table,
1632 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1633 vn_reference_t stored in the hashtable if something is found. */
1636 vn_reference_lookup_1 (vn_reference_t vr
, vn_reference_t
*vnresult
)
1638 vn_reference_s
**slot
;
1641 hash
= vr
->hashcode
;
1642 slot
= valid_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1646 *vnresult
= (vn_reference_t
)*slot
;
1647 return ((vn_reference_t
)*slot
)->result
;
1654 /* Partial definition tracking support. */
1658 HOST_WIDE_INT offset
;
1665 HOST_WIDE_INT offset
;
1669 /* Context for alias walking. */
1671 struct vn_walk_cb_data
1673 vn_walk_cb_data (vn_reference_t vr_
, tree
*last_vuse_ptr_
,
1674 vn_lookup_kind vn_walk_kind_
, bool tbaa_p_
)
1675 : vr (vr_
), last_vuse_ptr (last_vuse_ptr_
), vn_walk_kind (vn_walk_kind_
),
1676 tbaa_p (tbaa_p_
), known_ranges (NULL
)
1678 ~vn_walk_cb_data ();
1679 void *push_partial_def (const pd_data
& pd
, tree
, HOST_WIDE_INT
);
1682 tree
*last_vuse_ptr
;
1683 vn_lookup_kind vn_walk_kind
;
1686 /* The VDEFs of partial defs we come along. */
1687 auto_vec
<pd_data
, 2> partial_defs
;
1688 /* The first defs range to avoid splay tree setup in most cases. */
1689 pd_range first_range
;
1691 splay_tree known_ranges
;
1692 obstack ranges_obstack
;
1695 vn_walk_cb_data::~vn_walk_cb_data ()
1699 splay_tree_delete (known_ranges
);
1700 obstack_free (&ranges_obstack
, NULL
);
1704 /* pd_range splay-tree helpers. */
1707 pd_range_compare (splay_tree_key offset1p
, splay_tree_key offset2p
)
1709 HOST_WIDE_INT offset1
= *(HOST_WIDE_INT
*)offset1p
;
1710 HOST_WIDE_INT offset2
= *(HOST_WIDE_INT
*)offset2p
;
1711 if (offset1
< offset2
)
1713 else if (offset1
> offset2
)
1719 pd_tree_alloc (int size
, void *data_
)
1721 vn_walk_cb_data
*data
= (vn_walk_cb_data
*)data_
;
1722 return obstack_alloc (&data
->ranges_obstack
, size
);
1726 pd_tree_dealloc (void *, void *)
1730 /* Push PD to the vector of partial definitions returning a
1731 value when we are ready to combine things with VUSE and MAXSIZEI,
1732 NULL when we want to continue looking for partial defs or -1
1736 vn_walk_cb_data::push_partial_def (const pd_data
&pd
, tree vuse
,
1737 HOST_WIDE_INT maxsizei
)
1739 if (partial_defs
.is_empty ())
1741 partial_defs
.safe_push (pd
);
1742 first_range
.offset
= pd
.offset
;
1743 first_range
.size
= pd
.size
;
1745 last_vuse_ptr
= NULL
;
1751 /* ??? Optimize the case where the second partial def
1752 completes things. */
1753 gcc_obstack_init (&ranges_obstack
);
1755 = splay_tree_new_with_allocator (pd_range_compare
, 0, 0,
1757 pd_tree_dealloc
, this);
1758 splay_tree_insert (known_ranges
,
1759 (splay_tree_key
)&first_range
.offset
,
1760 (splay_tree_value
)&first_range
);
1764 pd_range newr
= { pd
.offset
, pd
.size
};
1767 /* Lookup the predecessor of offset + 1 and see if
1768 we need to merge with it. */
1769 HOST_WIDE_INT loffset
= newr
.offset
+ 1;
1770 if ((n
= splay_tree_predecessor (known_ranges
,
1771 (splay_tree_key
)&loffset
))
1772 && ((r
= (pd_range
*)n
->value
), true)
1773 && ranges_known_overlap_p (r
->offset
, r
->size
+ 1,
1774 newr
.offset
, newr
.size
))
1776 /* Ignore partial defs already covered. */
1777 if (known_subrange_p (newr
.offset
, newr
.size
,
1778 r
->offset
, r
->size
))
1780 r
->size
= MAX (r
->offset
+ r
->size
,
1781 newr
.offset
+ newr
.size
) - r
->offset
;
1785 /* newr.offset wasn't covered yet, insert the
1787 r
= XOBNEW (&ranges_obstack
, pd_range
);
1789 splay_tree_insert (known_ranges
,
1790 (splay_tree_key
)&r
->offset
,
1791 (splay_tree_value
)r
);
1793 /* Merge r which now contains newr and is a member
1794 of the splay tree with adjacent overlapping ranges. */
1796 while ((n
= splay_tree_successor (known_ranges
,
1797 (splay_tree_key
)&r
->offset
))
1798 && ((rafter
= (pd_range
*)n
->value
), true)
1799 && ranges_known_overlap_p (r
->offset
, r
->size
+ 1,
1800 rafter
->offset
, rafter
->size
))
1802 r
->size
= MAX (r
->offset
+ r
->size
,
1803 rafter
->offset
+ rafter
->size
) - r
->offset
;
1804 splay_tree_remove (known_ranges
,
1805 (splay_tree_key
)&rafter
->offset
);
1807 partial_defs
.safe_push (pd
);
1809 /* Now we have merged newr into the range tree.
1810 When we have covered [offseti, sizei] then the
1811 tree will contain exactly one node which has
1812 the desired properties and it will be 'r'. */
1813 if (known_subrange_p (0, maxsizei
/ BITS_PER_UNIT
,
1814 r
->offset
, r
->size
))
1816 /* Now simply native encode all partial defs
1817 in reverse order. */
1818 unsigned ndefs
= partial_defs
.length ();
1819 /* We support up to 512-bit values (for V8DFmode). */
1820 unsigned char buffer
[64];
1823 while (!partial_defs
.is_empty ())
1825 pd_data pd
= partial_defs
.pop ();
1826 if (TREE_CODE (pd
.rhs
) == CONSTRUCTOR
)
1827 /* Empty CONSTRUCTOR. */
1828 memset (buffer
+ MAX (0, pd
.offset
),
1829 0, MIN ((HOST_WIDE_INT
)sizeof (buffer
), pd
.size
));
1832 len
= native_encode_expr (pd
.rhs
,
1833 buffer
+ MAX (0, pd
.offset
),
1834 sizeof (buffer
- MAX (0, pd
.offset
)),
1835 MAX (0, -pd
.offset
));
1837 || len
< (pd
.size
- MAX (0, -pd
.offset
)))
1839 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1840 fprintf (dump_file
, "Failed to encode %u "
1841 "partial definitions\n", ndefs
);
1847 tree type
= vr
->type
;
1848 /* Make sure to interpret in a type that has a range
1849 covering the whole access size. */
1850 if (INTEGRAL_TYPE_P (vr
->type
)
1851 && maxsizei
!= TYPE_PRECISION (vr
->type
))
1852 type
= build_nonstandard_integer_type (maxsizei
,
1853 TYPE_UNSIGNED (type
));
1854 tree val
= native_interpret_expr (type
, buffer
,
1855 maxsizei
/ BITS_PER_UNIT
);
1856 /* If we chop off bits because the types precision doesn't
1857 match the memory access size this is ok when optimizing
1858 reads but not when called from the DSE code during
1861 && type
!= vr
->type
)
1863 if (! int_fits_type_p (val
, vr
->type
))
1866 val
= fold_convert (vr
->type
, val
);
1871 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1872 fprintf (dump_file
, "Successfully combined %u "
1873 "partial definitions\n", ndefs
);
1874 return vn_reference_lookup_or_insert_for_pieces
1876 vr
->set
, vr
->type
, vr
->operands
, val
);
1880 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1881 fprintf (dump_file
, "Failed to interpret %u "
1882 "encoded partial definitions\n", ndefs
);
1888 /* Continue looking for partial defs. */
1892 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1893 with the current VUSE and performs the expression lookup. */
1896 vn_reference_lookup_2 (ao_ref
*op ATTRIBUTE_UNUSED
, tree vuse
, void *data_
)
1898 vn_walk_cb_data
*data
= (vn_walk_cb_data
*)data_
;
1899 vn_reference_t vr
= data
->vr
;
1900 vn_reference_s
**slot
;
1903 /* If we have partial definitions recorded we have to go through
1904 vn_reference_lookup_3. */
1905 if (!data
->partial_defs
.is_empty ())
1908 if (data
->last_vuse_ptr
)
1909 *data
->last_vuse_ptr
= vuse
;
1911 /* Fixup vuse and hash. */
1913 vr
->hashcode
= vr
->hashcode
- SSA_NAME_VERSION (vr
->vuse
);
1914 vr
->vuse
= vuse_ssa_val (vuse
);
1916 vr
->hashcode
= vr
->hashcode
+ SSA_NAME_VERSION (vr
->vuse
);
1918 hash
= vr
->hashcode
;
1919 slot
= valid_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1926 /* Lookup an existing or insert a new vn_reference entry into the
1927 value table for the VUSE, SET, TYPE, OPERANDS reference which
1928 has the value VALUE which is either a constant or an SSA name. */
1930 static vn_reference_t
1931 vn_reference_lookup_or_insert_for_pieces (tree vuse
,
1934 vec
<vn_reference_op_s
,
1939 vn_reference_t result
;
1941 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
1942 vr1
.operands
= operands
;
1945 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1946 if (vn_reference_lookup_1 (&vr1
, &result
))
1948 if (TREE_CODE (value
) == SSA_NAME
)
1949 value_id
= VN_INFO (value
)->value_id
;
1951 value_id
= get_or_alloc_constant_value_id (value
);
1952 return vn_reference_insert_pieces (vuse
, set
, type
,
1953 operands
.copy (), value
, value_id
);
1956 /* Return a value-number for RCODE OPS... either by looking up an existing
1957 value-number for the simplified result or by inserting the operation if
1961 vn_nary_build_or_lookup_1 (gimple_match_op
*res_op
, bool insert
)
1963 tree result
= NULL_TREE
;
1964 /* We will be creating a value number for
1966 So first simplify and lookup this expression to see if it
1967 is already available. */
1968 mprts_hook
= vn_lookup_simplify_result
;
1970 switch (TREE_CODE_LENGTH ((tree_code
) res_op
->code
))
1973 res
= gimple_resimplify1 (NULL
, res_op
, vn_valueize
);
1976 res
= gimple_resimplify2 (NULL
, res_op
, vn_valueize
);
1979 res
= gimple_resimplify3 (NULL
, res_op
, vn_valueize
);
1983 gimple
*new_stmt
= NULL
;
1985 && gimple_simplified_result_is_gimple_val (res_op
))
1987 /* The expression is already available. */
1988 result
= res_op
->ops
[0];
1989 /* Valueize it, simplification returns sth in AVAIL only. */
1990 if (TREE_CODE (result
) == SSA_NAME
)
1991 result
= SSA_VAL (result
);
1995 tree val
= vn_lookup_simplify_result (res_op
);
1998 gimple_seq stmts
= NULL
;
1999 result
= maybe_push_res_to_seq (res_op
, &stmts
);
2002 gcc_assert (gimple_seq_singleton_p (stmts
));
2003 new_stmt
= gimple_seq_first_stmt (stmts
);
2007 /* The expression is already available. */
2012 /* The expression is not yet available, value-number lhs to
2013 the new SSA_NAME we created. */
2014 /* Initialize value-number information properly. */
2015 vn_ssa_aux_t result_info
= VN_INFO (result
);
2016 result_info
->valnum
= result
;
2017 result_info
->value_id
= get_next_value_id ();
2018 result_info
->visited
= 1;
2019 gimple_seq_add_stmt_without_update (&VN_INFO (result
)->expr
,
2021 result_info
->needs_insertion
= true;
2022 /* ??? PRE phi-translation inserts NARYs without corresponding
2023 SSA name result. Re-use those but set their result according
2024 to the stmt we just built. */
2025 vn_nary_op_t nary
= NULL
;
2026 vn_nary_op_lookup_stmt (new_stmt
, &nary
);
2029 gcc_assert (! nary
->predicated_values
&& nary
->u
.result
== NULL_TREE
);
2030 nary
->u
.result
= gimple_assign_lhs (new_stmt
);
2032 /* As all "inserted" statements are singleton SCCs, insert
2033 to the valid table. This is strictly needed to
2034 avoid re-generating new value SSA_NAMEs for the same
2035 expression during SCC iteration over and over (the
2036 optimistic table gets cleared after each iteration).
2037 We do not need to insert into the optimistic table, as
2038 lookups there will fall back to the valid table. */
2041 unsigned int length
= vn_nary_length_from_stmt (new_stmt
);
2043 = alloc_vn_nary_op_noinit (length
, &vn_tables_insert_obstack
);
2044 vno1
->value_id
= result_info
->value_id
;
2045 vno1
->length
= length
;
2046 vno1
->predicated_values
= 0;
2047 vno1
->u
.result
= result
;
2048 init_vn_nary_op_from_stmt (vno1
, new_stmt
);
2049 vn_nary_op_insert_into (vno1
, valid_info
->nary
, true);
2050 /* Also do not link it into the undo chain. */
2051 last_inserted_nary
= vno1
->next
;
2052 vno1
->next
= (vn_nary_op_t
)(void *)-1;
2054 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2056 fprintf (dump_file
, "Inserting name ");
2057 print_generic_expr (dump_file
, result
);
2058 fprintf (dump_file
, " for expression ");
2059 print_gimple_expr (dump_file
, new_stmt
, 0, TDF_SLIM
);
2060 fprintf (dump_file
, "\n");
2066 /* Return a value-number for RCODE OPS... either by looking up an existing
2067 value-number for the simplified result or by inserting the operation. */
2070 vn_nary_build_or_lookup (gimple_match_op
*res_op
)
2072 return vn_nary_build_or_lookup_1 (res_op
, true);
2075 /* Try to simplify the expression RCODE OPS... of type TYPE and return
2076 its value if present. */
2079 vn_nary_simplify (vn_nary_op_t nary
)
2081 if (nary
->length
> gimple_match_op::MAX_NUM_OPS
)
2083 gimple_match_op
op (gimple_match_cond::UNCOND
, nary
->opcode
,
2084 nary
->type
, nary
->length
);
2085 memcpy (op
.ops
, nary
->op
, sizeof (tree
) * nary
->length
);
2086 return vn_nary_build_or_lookup_1 (&op
, false);
2089 /* Elimination engine. */
2091 class eliminate_dom_walker
: public dom_walker
2094 eliminate_dom_walker (cdi_direction
, bitmap
);
2095 ~eliminate_dom_walker ();
2097 virtual edge
before_dom_children (basic_block
);
2098 virtual void after_dom_children (basic_block
);
2100 virtual tree
eliminate_avail (basic_block
, tree op
);
2101 virtual void eliminate_push_avail (basic_block
, tree op
);
2102 tree
eliminate_insert (basic_block
, gimple_stmt_iterator
*gsi
, tree val
);
2104 void eliminate_stmt (basic_block
, gimple_stmt_iterator
*);
2106 unsigned eliminate_cleanup (bool region_p
= false);
2109 unsigned int el_todo
;
2110 unsigned int eliminations
;
2111 unsigned int insertions
;
2113 /* SSA names that had their defs inserted by PRE if do_pre. */
2114 bitmap inserted_exprs
;
2116 /* Blocks with statements that have had their EH properties changed. */
2117 bitmap need_eh_cleanup
;
2119 /* Blocks with statements that have had their AB properties changed. */
2120 bitmap need_ab_cleanup
;
2122 /* Local state for the eliminate domwalk. */
2123 auto_vec
<gimple
*> to_remove
;
2124 auto_vec
<gimple
*> to_fixup
;
2125 auto_vec
<tree
> avail
;
2126 auto_vec
<tree
> avail_stack
;
2129 /* Adaptor to the elimination engine using RPO availability. */
2131 class rpo_elim
: public eliminate_dom_walker
2134 rpo_elim(basic_block entry_
)
2135 : eliminate_dom_walker (CDI_DOMINATORS
, NULL
), entry (entry_
) {}
2138 virtual tree
eliminate_avail (basic_block
, tree op
);
2140 virtual void eliminate_push_avail (basic_block
, tree
);
2143 /* Instead of having a local availability lattice for each
2144 basic-block and availability at X defined as union of
2145 the local availabilities at X and its dominators we're
2146 turning this upside down and track availability per
2147 value given values are usually made available at very
2148 few points (at least one).
2149 So we have a value -> vec<location, leader> map where
2150 LOCATION is specifying the basic-block LEADER is made
2151 available for VALUE. We push to this vector in RPO
2152 order thus for iteration we can simply pop the last
2154 LOCATION is the basic-block index and LEADER is its
2155 SSA name version. */
2156 /* ??? We'd like to use auto_vec here with embedded storage
2157 but that doesn't play well until we can provide move
2158 constructors and use std::move on hash-table expansion.
2159 So for now this is a bit more expensive than necessary.
2160 We eventually want to switch to a chaining scheme like
2161 for hashtable entries for unwinding which would make
2162 making the vector part of the vn_ssa_aux structure possible. */
2163 typedef hash_map
<tree
, vec
<std::pair
<int, int> > > rpo_avail_t
;
2164 rpo_avail_t m_rpo_avail
;
2167 /* Global RPO state for access from hooks. */
2168 static rpo_elim
*rpo_avail
;
2169 basic_block vn_context_bb
;
2171 /* Return true if BASE1 and BASE2 can be adjusted so they have the
2172 same address and adjust *OFFSET1 and *OFFSET2 accordingly.
2173 Otherwise return false. */
2176 adjust_offsets_for_equal_base_address (tree base1
, poly_int64
*offset1
,
2177 tree base2
, poly_int64
*offset2
)
2180 if (TREE_CODE (base1
) == MEM_REF
2181 && TREE_CODE (base2
) == MEM_REF
)
2183 if (mem_ref_offset (base1
).to_shwi (&soff
))
2185 base1
= TREE_OPERAND (base1
, 0);
2186 *offset1
+= soff
* BITS_PER_UNIT
;
2188 if (mem_ref_offset (base2
).to_shwi (&soff
))
2190 base2
= TREE_OPERAND (base2
, 0);
2191 *offset2
+= soff
* BITS_PER_UNIT
;
2193 return operand_equal_p (base1
, base2
, 0);
2195 return operand_equal_p (base1
, base2
, OEP_ADDRESS_OF
);
2198 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
2199 from the statement defining VUSE and if not successful tries to
2200 translate *REFP and VR_ through an aggregate copy at the definition
2201 of VUSE. If *DISAMBIGUATE_ONLY is true then do not perform translation
2202 of *REF and *VR. If only disambiguation was performed then
2203 *DISAMBIGUATE_ONLY is set to true. */
2206 vn_reference_lookup_3 (ao_ref
*ref
, tree vuse
, void *data_
,
2207 bool *disambiguate_only
)
2209 vn_walk_cb_data
*data
= (vn_walk_cb_data
*)data_
;
2210 vn_reference_t vr
= data
->vr
;
2211 gimple
*def_stmt
= SSA_NAME_DEF_STMT (vuse
);
2212 tree base
= ao_ref_base (ref
);
2213 HOST_WIDE_INT offseti
, maxsizei
;
2214 static vec
<vn_reference_op_s
> lhs_ops
;
2216 bool lhs_ref_ok
= false;
2217 poly_int64 copy_size
;
2219 /* First try to disambiguate after value-replacing in the definitions LHS. */
2220 if (is_gimple_assign (def_stmt
))
2222 tree lhs
= gimple_assign_lhs (def_stmt
);
2223 bool valueized_anything
= false;
2224 /* Avoid re-allocation overhead. */
2225 lhs_ops
.truncate (0);
2226 basic_block saved_rpo_bb
= vn_context_bb
;
2227 vn_context_bb
= gimple_bb (def_stmt
);
2228 copy_reference_ops_from_ref (lhs
, &lhs_ops
);
2229 lhs_ops
= valueize_refs_1 (lhs_ops
, &valueized_anything
, true);
2230 vn_context_bb
= saved_rpo_bb
;
2231 if (valueized_anything
)
2233 lhs_ref_ok
= ao_ref_init_from_vn_reference (&lhs_ref
,
2234 get_alias_set (lhs
),
2235 TREE_TYPE (lhs
), lhs_ops
);
2237 && !refs_may_alias_p_1 (ref
, &lhs_ref
, data
->tbaa_p
))
2239 *disambiguate_only
= true;
2245 ao_ref_init (&lhs_ref
, lhs
);
2249 /* If we reach a clobbering statement try to skip it and see if
2250 we find a VN result with exactly the same value as the
2251 possible clobber. In this case we can ignore the clobber
2252 and return the found value. */
2253 if (is_gimple_reg_type (TREE_TYPE (lhs
))
2254 && types_compatible_p (TREE_TYPE (lhs
), vr
->type
)
2257 tree
*saved_last_vuse_ptr
= data
->last_vuse_ptr
;
2258 /* Do not update last_vuse_ptr in vn_reference_lookup_2. */
2259 data
->last_vuse_ptr
= NULL
;
2260 tree saved_vuse
= vr
->vuse
;
2261 hashval_t saved_hashcode
= vr
->hashcode
;
2262 void *res
= vn_reference_lookup_2 (ref
, gimple_vuse (def_stmt
), data
);
2263 /* Need to restore vr->vuse and vr->hashcode. */
2264 vr
->vuse
= saved_vuse
;
2265 vr
->hashcode
= saved_hashcode
;
2266 data
->last_vuse_ptr
= saved_last_vuse_ptr
;
2267 if (res
&& res
!= (void *)-1)
2269 vn_reference_t vnresult
= (vn_reference_t
) res
;
2270 tree rhs
= gimple_assign_rhs1 (def_stmt
);
2271 if (TREE_CODE (rhs
) == SSA_NAME
)
2272 rhs
= SSA_VAL (rhs
);
2273 if (vnresult
->result
2274 && operand_equal_p (vnresult
->result
, rhs
, 0)
2275 /* We have to honor our promise about union type punning
2276 and also support arbitrary overlaps with
2277 -fno-strict-aliasing. So simply resort to alignment to
2278 rule out overlaps. Do this check last because it is
2279 quite expensive compared to the hash-lookup above. */
2280 && multiple_p (get_object_alignment (ref
->ref
), ref
->size
)
2281 && multiple_p (get_object_alignment (lhs
), ref
->size
))
2286 else if (gimple_call_builtin_p (def_stmt
, BUILT_IN_NORMAL
)
2287 && gimple_call_num_args (def_stmt
) <= 4)
2289 /* For builtin calls valueize its arguments and call the
2290 alias oracle again. Valueization may improve points-to
2291 info of pointers and constify size and position arguments.
2292 Originally this was motivated by PR61034 which has
2293 conditional calls to free falsely clobbering ref because
2294 of imprecise points-to info of the argument. */
2296 bool valueized_anything
= false;
2297 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
2299 oldargs
[i
] = gimple_call_arg (def_stmt
, i
);
2300 tree val
= vn_valueize (oldargs
[i
]);
2301 if (val
!= oldargs
[i
])
2303 gimple_call_set_arg (def_stmt
, i
, val
);
2304 valueized_anything
= true;
2307 if (valueized_anything
)
2309 bool res
= call_may_clobber_ref_p_1 (as_a
<gcall
*> (def_stmt
),
2311 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
2312 gimple_call_set_arg (def_stmt
, i
, oldargs
[i
]);
2315 *disambiguate_only
= true;
2321 /* If we are looking for redundant stores do not create new hashtable
2322 entries from aliasing defs with made up alias-sets. */
2323 if (*disambiguate_only
|| !data
->tbaa_p
)
2326 /* If we cannot constrain the size of the reference we cannot
2327 test if anything kills it. */
2328 if (!ref
->max_size_known_p ())
2331 poly_int64 offset
= ref
->offset
;
2332 poly_int64 maxsize
= ref
->max_size
;
2334 /* We can't deduce anything useful from clobbers. */
2335 if (gimple_clobber_p (def_stmt
))
2338 /* def_stmt may-defs *ref. See if we can derive a value for *ref
2339 from that definition.
2341 if (is_gimple_reg_type (vr
->type
)
2342 && gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMSET
)
2343 && (integer_zerop (gimple_call_arg (def_stmt
, 1))
2344 || ((TREE_CODE (gimple_call_arg (def_stmt
, 1)) == INTEGER_CST
2345 || (INTEGRAL_TYPE_P (vr
->type
) && known_eq (ref
->size
, 8)))
2346 && CHAR_BIT
== 8 && BITS_PER_UNIT
== 8
2347 && offset
.is_constant (&offseti
)
2348 && offseti
% BITS_PER_UNIT
== 0))
2349 && poly_int_tree_p (gimple_call_arg (def_stmt
, 2))
2350 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
2351 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
))
2354 poly_int64 offset2
, size2
, maxsize2
;
2356 tree ref2
= gimple_call_arg (def_stmt
, 0);
2357 if (TREE_CODE (ref2
) == SSA_NAME
)
2359 ref2
= SSA_VAL (ref2
);
2360 if (TREE_CODE (ref2
) == SSA_NAME
2361 && (TREE_CODE (base
) != MEM_REF
2362 || TREE_OPERAND (base
, 0) != ref2
))
2364 gimple
*def_stmt
= SSA_NAME_DEF_STMT (ref2
);
2365 if (gimple_assign_single_p (def_stmt
)
2366 && gimple_assign_rhs_code (def_stmt
) == ADDR_EXPR
)
2367 ref2
= gimple_assign_rhs1 (def_stmt
);
2370 if (TREE_CODE (ref2
) == ADDR_EXPR
)
2372 ref2
= TREE_OPERAND (ref2
, 0);
2373 base2
= get_ref_base_and_extent (ref2
, &offset2
, &size2
, &maxsize2
,
2375 if (!known_size_p (maxsize2
)
2376 || !known_eq (maxsize2
, size2
)
2377 || !operand_equal_p (base
, base2
, OEP_ADDRESS_OF
))
2380 else if (TREE_CODE (ref2
) == SSA_NAME
)
2383 if (TREE_CODE (base
) != MEM_REF
2384 || !(mem_ref_offset (base
) << LOG2_BITS_PER_UNIT
).to_shwi (&soff
))
2388 if (TREE_OPERAND (base
, 0) != ref2
)
2390 gimple
*def
= SSA_NAME_DEF_STMT (ref2
);
2391 if (is_gimple_assign (def
)
2392 && gimple_assign_rhs_code (def
) == POINTER_PLUS_EXPR
2393 && gimple_assign_rhs1 (def
) == TREE_OPERAND (base
, 0)
2394 && poly_int_tree_p (gimple_assign_rhs2 (def
))
2395 && (wi::to_poly_offset (gimple_assign_rhs2 (def
))
2396 << LOG2_BITS_PER_UNIT
).to_shwi (&offset2
))
2398 ref2
= gimple_assign_rhs1 (def
);
2399 if (TREE_CODE (ref2
) == SSA_NAME
)
2400 ref2
= SSA_VAL (ref2
);
2408 tree len
= gimple_call_arg (def_stmt
, 2);
2409 HOST_WIDE_INT leni
, offset2i
, offseti
;
2410 if (data
->partial_defs
.is_empty ()
2411 && known_subrange_p (offset
, maxsize
, offset2
,
2412 wi::to_poly_offset (len
) << LOG2_BITS_PER_UNIT
))
2415 if (integer_zerop (gimple_call_arg (def_stmt
, 1)))
2416 val
= build_zero_cst (vr
->type
);
2417 else if (INTEGRAL_TYPE_P (vr
->type
)
2418 && known_eq (ref
->size
, 8))
2420 gimple_match_op
res_op (gimple_match_cond::UNCOND
, NOP_EXPR
,
2421 vr
->type
, gimple_call_arg (def_stmt
, 1));
2422 val
= vn_nary_build_or_lookup (&res_op
);
2424 || (TREE_CODE (val
) == SSA_NAME
2425 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
)))
2430 unsigned len
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (vr
->type
));
2431 unsigned char *buf
= XALLOCAVEC (unsigned char, len
);
2432 memset (buf
, TREE_INT_CST_LOW (gimple_call_arg (def_stmt
, 1)),
2434 val
= native_interpret_expr (vr
->type
, buf
, len
);
2438 return vn_reference_lookup_or_insert_for_pieces
2439 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
2441 /* For now handle clearing memory with partial defs. */
2442 else if (integer_zerop (gimple_call_arg (def_stmt
, 1))
2443 && tree_to_poly_int64 (len
).is_constant (&leni
)
2444 && offset
.is_constant (&offseti
)
2445 && offset2
.is_constant (&offset2i
)
2446 && maxsize
.is_constant (&maxsizei
))
2449 pd
.rhs
= build_constructor (NULL_TREE
, NULL
);
2450 pd
.offset
= offset2i
- offseti
;
2452 return data
->push_partial_def (pd
, vuse
, maxsizei
);
2456 /* 2) Assignment from an empty CONSTRUCTOR. */
2457 else if (is_gimple_reg_type (vr
->type
)
2458 && gimple_assign_single_p (def_stmt
)
2459 && gimple_assign_rhs_code (def_stmt
) == CONSTRUCTOR
2460 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt
)) == 0)
2463 poly_int64 offset2
, size2
, maxsize2
;
2464 HOST_WIDE_INT offset2i
, size2i
;
2466 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
2467 &offset2
, &size2
, &maxsize2
, &reverse
);
2468 if (known_size_p (maxsize2
)
2469 && known_eq (maxsize2
, size2
)
2470 && adjust_offsets_for_equal_base_address (base
, &offset
,
2473 if (data
->partial_defs
.is_empty ()
2474 && known_subrange_p (offset
, maxsize
, offset2
, size2
))
2476 tree val
= build_zero_cst (vr
->type
);
2477 return vn_reference_lookup_or_insert_for_pieces
2478 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
2480 else if (maxsize
.is_constant (&maxsizei
)
2481 && maxsizei
% BITS_PER_UNIT
== 0
2482 && offset
.is_constant (&offseti
)
2483 && offseti
% BITS_PER_UNIT
== 0
2484 && offset2
.is_constant (&offset2i
)
2485 && offset2i
% BITS_PER_UNIT
== 0
2486 && size2
.is_constant (&size2i
)
2487 && size2i
% BITS_PER_UNIT
== 0)
2490 pd
.rhs
= gimple_assign_rhs1 (def_stmt
);
2491 pd
.offset
= (offset2i
- offseti
) / BITS_PER_UNIT
;
2492 pd
.size
= size2i
/ BITS_PER_UNIT
;
2493 return data
->push_partial_def (pd
, vuse
, maxsizei
);
2498 /* 3) Assignment from a constant. We can use folds native encode/interpret
2499 routines to extract the assigned bits. */
2500 else if (known_eq (ref
->size
, maxsize
)
2501 && is_gimple_reg_type (vr
->type
)
2502 && !contains_storage_order_barrier_p (vr
->operands
)
2503 && gimple_assign_single_p (def_stmt
)
2504 && CHAR_BIT
== 8 && BITS_PER_UNIT
== 8
2505 /* native_encode and native_decode operate on arrays of bytes
2506 and so fundamentally need a compile-time size and offset. */
2507 && maxsize
.is_constant (&maxsizei
)
2508 && maxsizei
% BITS_PER_UNIT
== 0
2509 && offset
.is_constant (&offseti
)
2510 && offseti
% BITS_PER_UNIT
== 0
2511 && (is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
))
2512 || (TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
2513 && is_gimple_min_invariant (SSA_VAL (gimple_assign_rhs1 (def_stmt
))))))
2516 poly_int64 offset2
, size2
, maxsize2
;
2517 HOST_WIDE_INT offset2i
, size2i
;
2519 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
2520 &offset2
, &size2
, &maxsize2
, &reverse
);
2523 && known_eq (maxsize2
, size2
)
2524 && multiple_p (size2
, BITS_PER_UNIT
)
2525 && multiple_p (offset2
, BITS_PER_UNIT
)
2526 && adjust_offsets_for_equal_base_address (base
, &offset
,
2528 && offset
.is_constant (&offseti
)
2529 && offset2
.is_constant (&offset2i
)
2530 && size2
.is_constant (&size2i
))
2532 if (data
->partial_defs
.is_empty ()
2533 && known_subrange_p (offseti
, maxsizei
, offset2
, size2
))
2535 /* We support up to 512-bit values (for V8DFmode). */
2536 unsigned char buffer
[64];
2539 tree rhs
= gimple_assign_rhs1 (def_stmt
);
2540 if (TREE_CODE (rhs
) == SSA_NAME
)
2541 rhs
= SSA_VAL (rhs
);
2542 len
= native_encode_expr (rhs
,
2543 buffer
, sizeof (buffer
),
2544 (offseti
- offset2i
) / BITS_PER_UNIT
);
2545 if (len
> 0 && len
* BITS_PER_UNIT
>= maxsizei
)
2547 tree type
= vr
->type
;
2548 /* Make sure to interpret in a type that has a range
2549 covering the whole access size. */
2550 if (INTEGRAL_TYPE_P (vr
->type
)
2551 && maxsizei
!= TYPE_PRECISION (vr
->type
))
2552 type
= build_nonstandard_integer_type (maxsizei
,
2553 TYPE_UNSIGNED (type
));
2554 tree val
= native_interpret_expr (type
, buffer
,
2555 maxsizei
/ BITS_PER_UNIT
);
2556 /* If we chop off bits because the types precision doesn't
2557 match the memory access size this is ok when optimizing
2558 reads but not when called from the DSE code during
2561 && type
!= vr
->type
)
2563 if (! int_fits_type_p (val
, vr
->type
))
2566 val
= fold_convert (vr
->type
, val
);
2570 return vn_reference_lookup_or_insert_for_pieces
2571 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
2574 else if (ranges_known_overlap_p (offseti
, maxsizei
, offset2i
, size2i
))
2577 tree rhs
= gimple_assign_rhs1 (def_stmt
);
2578 if (TREE_CODE (rhs
) == SSA_NAME
)
2579 rhs
= SSA_VAL (rhs
);
2581 pd
.offset
= (offset2i
- offseti
) / BITS_PER_UNIT
;
2582 pd
.size
= size2i
/ BITS_PER_UNIT
;
2583 return data
->push_partial_def (pd
, vuse
, maxsizei
);
2588 /* 4) Assignment from an SSA name which definition we may be able
2589 to access pieces from. */
2590 else if (known_eq (ref
->size
, maxsize
)
2591 && is_gimple_reg_type (vr
->type
)
2592 && !contains_storage_order_barrier_p (vr
->operands
)
2593 && gimple_assign_single_p (def_stmt
)
2594 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
2595 /* A subset of partial defs from non-constants can be handled
2596 by for example inserting a CONSTRUCTOR, a COMPLEX_EXPR or
2597 even a (series of) BIT_INSERT_EXPR hoping for simplifications
2598 downstream, not so much for actually doing the insertion. */
2599 && data
->partial_defs
.is_empty ())
2602 poly_int64 offset2
, size2
, maxsize2
;
2604 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
2605 &offset2
, &size2
, &maxsize2
,
2607 tree def_rhs
= gimple_assign_rhs1 (def_stmt
);
2609 && known_size_p (maxsize2
)
2610 && known_eq (maxsize2
, size2
)
2611 && adjust_offsets_for_equal_base_address (base
, &offset
,
2613 && known_subrange_p (offset
, maxsize
, offset2
, size2
)
2614 /* ??? We can't handle bitfield precision extracts without
2615 either using an alternate type for the BIT_FIELD_REF and
2616 then doing a conversion or possibly adjusting the offset
2617 according to endianness. */
2618 && (! INTEGRAL_TYPE_P (vr
->type
)
2619 || known_eq (ref
->size
, TYPE_PRECISION (vr
->type
)))
2620 && multiple_p (ref
->size
, BITS_PER_UNIT
)
2621 && (! INTEGRAL_TYPE_P (TREE_TYPE (def_rhs
))
2622 || type_has_mode_precision_p (TREE_TYPE (def_rhs
))))
2624 gimple_match_op
op (gimple_match_cond::UNCOND
,
2625 BIT_FIELD_REF
, vr
->type
,
2626 vn_valueize (def_rhs
),
2627 bitsize_int (ref
->size
),
2628 bitsize_int (offset
- offset2
));
2629 tree val
= vn_nary_build_or_lookup (&op
);
2631 && (TREE_CODE (val
) != SSA_NAME
2632 || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
)))
2634 vn_reference_t res
= vn_reference_lookup_or_insert_for_pieces
2635 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
2641 /* 5) For aggregate copies translate the reference through them if
2642 the copy kills ref. */
2643 else if (data
->vn_walk_kind
== VN_WALKREWRITE
2644 && gimple_assign_single_p (def_stmt
)
2645 && (DECL_P (gimple_assign_rhs1 (def_stmt
))
2646 || TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == MEM_REF
2647 || handled_component_p (gimple_assign_rhs1 (def_stmt
)))
2648 /* Handling this is more complicated, give up for now. */
2649 && data
->partial_defs
.is_empty ())
2653 auto_vec
<vn_reference_op_s
> rhs
;
2654 vn_reference_op_t vro
;
2660 /* See if the assignment kills REF. */
2661 base2
= ao_ref_base (&lhs_ref
);
2662 if (!lhs_ref
.max_size_known_p ()
2664 && (TREE_CODE (base
) != MEM_REF
2665 || TREE_CODE (base2
) != MEM_REF
2666 || TREE_OPERAND (base
, 0) != TREE_OPERAND (base2
, 0)
2667 || !tree_int_cst_equal (TREE_OPERAND (base
, 1),
2668 TREE_OPERAND (base2
, 1))))
2669 || !stmt_kills_ref_p (def_stmt
, ref
))
2672 /* Find the common base of ref and the lhs. lhs_ops already
2673 contains valueized operands for the lhs. */
2674 i
= vr
->operands
.length () - 1;
2675 j
= lhs_ops
.length () - 1;
2676 while (j
>= 0 && i
>= 0
2677 && vn_reference_op_eq (&vr
->operands
[i
], &lhs_ops
[j
]))
2683 /* ??? The innermost op should always be a MEM_REF and we already
2684 checked that the assignment to the lhs kills vr. Thus for
2685 aggregate copies using char[] types the vn_reference_op_eq
2686 may fail when comparing types for compatibility. But we really
2687 don't care here - further lookups with the rewritten operands
2688 will simply fail if we messed up types too badly. */
2689 poly_int64 extra_off
= 0;
2690 if (j
== 0 && i
>= 0
2691 && lhs_ops
[0].opcode
== MEM_REF
2692 && maybe_ne (lhs_ops
[0].off
, -1))
2694 if (known_eq (lhs_ops
[0].off
, vr
->operands
[i
].off
))
2696 else if (vr
->operands
[i
].opcode
== MEM_REF
2697 && maybe_ne (vr
->operands
[i
].off
, -1))
2699 extra_off
= vr
->operands
[i
].off
- lhs_ops
[0].off
;
2704 /* i now points to the first additional op.
2705 ??? LHS may not be completely contained in VR, one or more
2706 VIEW_CONVERT_EXPRs could be in its way. We could at least
2707 try handling outermost VIEW_CONVERT_EXPRs. */
2711 /* Punt if the additional ops contain a storage order barrier. */
2712 for (k
= i
; k
>= 0; k
--)
2714 vro
= &vr
->operands
[k
];
2715 if (vro
->opcode
== VIEW_CONVERT_EXPR
&& vro
->reverse
)
2719 /* Now re-write REF to be based on the rhs of the assignment. */
2720 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt
), &rhs
);
2722 /* Apply an extra offset to the inner MEM_REF of the RHS. */
2723 if (maybe_ne (extra_off
, 0))
2725 if (rhs
.length () < 2)
2727 int ix
= rhs
.length () - 2;
2728 if (rhs
[ix
].opcode
!= MEM_REF
2729 || known_eq (rhs
[ix
].off
, -1))
2731 rhs
[ix
].off
+= extra_off
;
2732 rhs
[ix
].op0
= int_const_binop (PLUS_EXPR
, rhs
[ix
].op0
,
2733 build_int_cst (TREE_TYPE (rhs
[ix
].op0
),
2737 /* We need to pre-pend vr->operands[0..i] to rhs. */
2738 vec
<vn_reference_op_s
> old
= vr
->operands
;
2739 if (i
+ 1 + rhs
.length () > vr
->operands
.length ())
2740 vr
->operands
.safe_grow (i
+ 1 + rhs
.length ());
2742 vr
->operands
.truncate (i
+ 1 + rhs
.length ());
2743 FOR_EACH_VEC_ELT (rhs
, j
, vro
)
2744 vr
->operands
[i
+ 1 + j
] = *vro
;
2745 vr
->operands
= valueize_refs (vr
->operands
);
2746 if (old
== shared_lookup_references
)
2747 shared_lookup_references
= vr
->operands
;
2748 vr
->hashcode
= vn_reference_compute_hash (vr
);
2750 /* Try folding the new reference to a constant. */
2751 tree val
= fully_constant_vn_reference_p (vr
);
2753 return vn_reference_lookup_or_insert_for_pieces
2754 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
2756 /* Adjust *ref from the new operands. */
2757 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
2759 /* This can happen with bitfields. */
2760 if (maybe_ne (ref
->size
, r
.size
))
2764 /* Do not update last seen VUSE after translating. */
2765 data
->last_vuse_ptr
= NULL
;
2767 /* Keep looking for the adjusted *REF / VR pair. */
2771 /* 6) For memcpy copies translate the reference through them if
2772 the copy kills ref. */
2773 else if (data
->vn_walk_kind
== VN_WALKREWRITE
2774 && is_gimple_reg_type (vr
->type
)
2775 /* ??? Handle BCOPY as well. */
2776 && (gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMCPY
)
2777 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMPCPY
)
2778 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMMOVE
))
2779 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
2780 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
)
2781 && (TREE_CODE (gimple_call_arg (def_stmt
, 1)) == ADDR_EXPR
2782 || TREE_CODE (gimple_call_arg (def_stmt
, 1)) == SSA_NAME
)
2783 && poly_int_tree_p (gimple_call_arg (def_stmt
, 2), ©_size
)
2784 /* Handling this is more complicated, give up for now. */
2785 && data
->partial_defs
.is_empty ())
2789 poly_int64 rhs_offset
, lhs_offset
;
2790 vn_reference_op_s op
;
2791 poly_uint64 mem_offset
;
2792 poly_int64 at
, byte_maxsize
;
2794 /* Only handle non-variable, addressable refs. */
2795 if (maybe_ne (ref
->size
, maxsize
)
2796 || !multiple_p (offset
, BITS_PER_UNIT
, &at
)
2797 || !multiple_p (maxsize
, BITS_PER_UNIT
, &byte_maxsize
))
2800 /* Extract a pointer base and an offset for the destination. */
2801 lhs
= gimple_call_arg (def_stmt
, 0);
2803 if (TREE_CODE (lhs
) == SSA_NAME
)
2805 lhs
= vn_valueize (lhs
);
2806 if (TREE_CODE (lhs
) == SSA_NAME
)
2808 gimple
*def_stmt
= SSA_NAME_DEF_STMT (lhs
);
2809 if (gimple_assign_single_p (def_stmt
)
2810 && gimple_assign_rhs_code (def_stmt
) == ADDR_EXPR
)
2811 lhs
= gimple_assign_rhs1 (def_stmt
);
2814 if (TREE_CODE (lhs
) == ADDR_EXPR
)
2816 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (lhs
, 0),
2820 if (TREE_CODE (tem
) == MEM_REF
2821 && poly_int_tree_p (TREE_OPERAND (tem
, 1), &mem_offset
))
2823 lhs
= TREE_OPERAND (tem
, 0);
2824 if (TREE_CODE (lhs
) == SSA_NAME
)
2825 lhs
= vn_valueize (lhs
);
2826 lhs_offset
+= mem_offset
;
2828 else if (DECL_P (tem
))
2829 lhs
= build_fold_addr_expr (tem
);
2833 if (TREE_CODE (lhs
) != SSA_NAME
2834 && TREE_CODE (lhs
) != ADDR_EXPR
)
2837 /* Extract a pointer base and an offset for the source. */
2838 rhs
= gimple_call_arg (def_stmt
, 1);
2840 if (TREE_CODE (rhs
) == SSA_NAME
)
2841 rhs
= vn_valueize (rhs
);
2842 if (TREE_CODE (rhs
) == ADDR_EXPR
)
2844 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs
, 0),
2848 if (TREE_CODE (tem
) == MEM_REF
2849 && poly_int_tree_p (TREE_OPERAND (tem
, 1), &mem_offset
))
2851 rhs
= TREE_OPERAND (tem
, 0);
2852 rhs_offset
+= mem_offset
;
2854 else if (DECL_P (tem
)
2855 || TREE_CODE (tem
) == STRING_CST
)
2856 rhs
= build_fold_addr_expr (tem
);
2860 if (TREE_CODE (rhs
) != SSA_NAME
2861 && TREE_CODE (rhs
) != ADDR_EXPR
)
2864 /* The bases of the destination and the references have to agree. */
2865 if (TREE_CODE (base
) == MEM_REF
)
2867 if (TREE_OPERAND (base
, 0) != lhs
2868 || !poly_int_tree_p (TREE_OPERAND (base
, 1), &mem_offset
))
2872 else if (!DECL_P (base
)
2873 || TREE_CODE (lhs
) != ADDR_EXPR
2874 || TREE_OPERAND (lhs
, 0) != base
)
2877 /* If the access is completely outside of the memcpy destination
2878 area there is no aliasing. */
2879 if (!ranges_maybe_overlap_p (lhs_offset
, copy_size
, at
, byte_maxsize
))
2881 /* And the access has to be contained within the memcpy destination. */
2882 if (!known_subrange_p (at
, byte_maxsize
, lhs_offset
, copy_size
))
2885 /* Make room for 2 operands in the new reference. */
2886 if (vr
->operands
.length () < 2)
2888 vec
<vn_reference_op_s
> old
= vr
->operands
;
2889 vr
->operands
.safe_grow_cleared (2);
2890 if (old
== shared_lookup_references
)
2891 shared_lookup_references
= vr
->operands
;
2894 vr
->operands
.truncate (2);
2896 /* The looked-through reference is a simple MEM_REF. */
2897 memset (&op
, 0, sizeof (op
));
2899 op
.opcode
= MEM_REF
;
2900 op
.op0
= build_int_cst (ptr_type_node
, at
- lhs_offset
+ rhs_offset
);
2901 op
.off
= at
- lhs_offset
+ rhs_offset
;
2902 vr
->operands
[0] = op
;
2903 op
.type
= TREE_TYPE (rhs
);
2904 op
.opcode
= TREE_CODE (rhs
);
2907 vr
->operands
[1] = op
;
2908 vr
->hashcode
= vn_reference_compute_hash (vr
);
2910 /* Try folding the new reference to a constant. */
2911 tree val
= fully_constant_vn_reference_p (vr
);
2913 return vn_reference_lookup_or_insert_for_pieces
2914 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
2916 /* Adjust *ref from the new operands. */
2917 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
2919 /* This can happen with bitfields. */
2920 if (maybe_ne (ref
->size
, r
.size
))
2924 /* Do not update last seen VUSE after translating. */
2925 data
->last_vuse_ptr
= NULL
;
2927 /* Keep looking for the adjusted *REF / VR pair. */
2931 /* Bail out and stop walking. */
2935 /* Return a reference op vector from OP that can be used for
2936 vn_reference_lookup_pieces. The caller is responsible for releasing
2939 vec
<vn_reference_op_s
>
2940 vn_reference_operands_for_lookup (tree op
)
2943 return valueize_shared_reference_ops_from_ref (op
, &valueized
).copy ();
2946 /* Lookup a reference operation by it's parts, in the current hash table.
2947 Returns the resulting value number if it exists in the hash table,
2948 NULL_TREE otherwise. VNRESULT will be filled in with the actual
2949 vn_reference_t stored in the hashtable if something is found. */
2952 vn_reference_lookup_pieces (tree vuse
, alias_set_type set
, tree type
,
2953 vec
<vn_reference_op_s
> operands
,
2954 vn_reference_t
*vnresult
, vn_lookup_kind kind
)
2956 struct vn_reference_s vr1
;
2964 vr1
.vuse
= vuse_ssa_val (vuse
);
2965 shared_lookup_references
.truncate (0);
2966 shared_lookup_references
.safe_grow (operands
.length ());
2967 memcpy (shared_lookup_references
.address (),
2968 operands
.address (),
2969 sizeof (vn_reference_op_s
)
2970 * operands
.length ());
2971 vr1
.operands
= operands
= shared_lookup_references
2972 = valueize_refs (shared_lookup_references
);
2975 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2976 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2979 vn_reference_lookup_1 (&vr1
, vnresult
);
2981 && kind
!= VN_NOWALK
2985 unsigned limit
= PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS
);
2986 vn_walk_cb_data
data (&vr1
, NULL
, kind
, true);
2987 if (ao_ref_init_from_vn_reference (&r
, set
, type
, vr1
.operands
))
2989 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
, true,
2990 vn_reference_lookup_2
,
2991 vn_reference_lookup_3
,
2992 vuse_valueize
, limit
, &data
);
2993 gcc_checking_assert (vr1
.operands
== shared_lookup_references
);
2997 return (*vnresult
)->result
;
3002 /* Lookup OP in the current hash table, and return the resulting value
3003 number if it exists in the hash table. Return NULL_TREE if it does
3004 not exist in the hash table or if the result field of the structure
3005 was NULL.. VNRESULT will be filled in with the vn_reference_t
3006 stored in the hashtable if one exists. When TBAA_P is false assume
3007 we are looking up a store and treat it as having alias-set zero.
3008 *LAST_VUSE_PTR will be updated with the VUSE the value lookup succeeded. */
3011 vn_reference_lookup (tree op
, tree vuse
, vn_lookup_kind kind
,
3012 vn_reference_t
*vnresult
, bool tbaa_p
, tree
*last_vuse_ptr
)
3014 vec
<vn_reference_op_s
> operands
;
3015 struct vn_reference_s vr1
;
3017 bool valuezied_anything
;
3022 vr1
.vuse
= vuse_ssa_val (vuse
);
3023 vr1
.operands
= operands
3024 = valueize_shared_reference_ops_from_ref (op
, &valuezied_anything
);
3025 vr1
.type
= TREE_TYPE (op
);
3026 vr1
.set
= get_alias_set (op
);
3027 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
3028 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
3031 if (kind
!= VN_NOWALK
3034 vn_reference_t wvnresult
;
3036 unsigned limit
= PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS
);
3037 /* Make sure to use a valueized reference if we valueized anything.
3038 Otherwise preserve the full reference for advanced TBAA. */
3039 if (!valuezied_anything
3040 || !ao_ref_init_from_vn_reference (&r
, vr1
.set
, vr1
.type
,
3042 ao_ref_init (&r
, op
);
3043 vn_walk_cb_data
data (&vr1
, last_vuse_ptr
, kind
, tbaa_p
);
3045 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
, tbaa_p
,
3046 vn_reference_lookup_2
,
3047 vn_reference_lookup_3
,
3048 vuse_valueize
, limit
, &data
);
3049 gcc_checking_assert (vr1
.operands
== shared_lookup_references
);
3053 *vnresult
= wvnresult
;
3054 return wvnresult
->result
;
3060 return vn_reference_lookup_1 (&vr1
, vnresult
);
3063 /* Lookup CALL in the current hash table and return the entry in
3064 *VNRESULT if found. Populates *VR for the hashtable lookup. */
3067 vn_reference_lookup_call (gcall
*call
, vn_reference_t
*vnresult
,
3073 tree vuse
= gimple_vuse (call
);
3075 vr
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
3076 vr
->operands
= valueize_shared_reference_ops_from_call (call
);
3077 vr
->type
= gimple_expr_type (call
);
3079 vr
->hashcode
= vn_reference_compute_hash (vr
);
3080 vn_reference_lookup_1 (vr
, vnresult
);
3083 /* Insert OP into the current hash table with a value number of RESULT. */
3086 vn_reference_insert (tree op
, tree result
, tree vuse
, tree vdef
)
3088 vn_reference_s
**slot
;
3092 vr1
= XOBNEW (&vn_tables_obstack
, vn_reference_s
);
3093 if (TREE_CODE (result
) == SSA_NAME
)
3094 vr1
->value_id
= VN_INFO (result
)->value_id
;
3096 vr1
->value_id
= get_or_alloc_constant_value_id (result
);
3097 vr1
->vuse
= vuse_ssa_val (vuse
);
3098 vr1
->operands
= valueize_shared_reference_ops_from_ref (op
, &tem
).copy ();
3099 vr1
->type
= TREE_TYPE (op
);
3100 vr1
->set
= get_alias_set (op
);
3101 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
3102 vr1
->result
= TREE_CODE (result
) == SSA_NAME
? SSA_VAL (result
) : result
;
3103 vr1
->result_vdef
= vdef
;
3105 slot
= valid_info
->references
->find_slot_with_hash (vr1
, vr1
->hashcode
,
3108 /* Because IL walking on reference lookup can end up visiting
3109 a def that is only to be visited later in iteration order
3110 when we are about to make an irreducible region reducible
3111 the def can be effectively processed and its ref being inserted
3112 by vn_reference_lookup_3 already. So we cannot assert (!*slot)
3113 but save a lookup if we deal with already inserted refs here. */
3116 /* We cannot assert that we have the same value either because
3117 when disentangling an irreducible region we may end up visiting
3118 a use before the corresponding def. That's a missed optimization
3119 only though. See gcc.dg/tree-ssa/pr87126.c for example. */
3120 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
3121 && !operand_equal_p ((*slot
)->result
, vr1
->result
, 0))
3123 fprintf (dump_file
, "Keeping old value ");
3124 print_generic_expr (dump_file
, (*slot
)->result
);
3125 fprintf (dump_file
, " because of collision\n");
3127 free_reference (vr1
);
3128 obstack_free (&vn_tables_obstack
, vr1
);
3133 vr1
->next
= last_inserted_ref
;
3134 last_inserted_ref
= vr1
;
3137 /* Insert a reference by it's pieces into the current hash table with
3138 a value number of RESULT. Return the resulting reference
3139 structure we created. */
3142 vn_reference_insert_pieces (tree vuse
, alias_set_type set
, tree type
,
3143 vec
<vn_reference_op_s
> operands
,
3144 tree result
, unsigned int value_id
)
3147 vn_reference_s
**slot
;
3150 vr1
= XOBNEW (&vn_tables_obstack
, vn_reference_s
);
3151 vr1
->value_id
= value_id
;
3152 vr1
->vuse
= vuse_ssa_val (vuse
);
3153 vr1
->operands
= valueize_refs (operands
);
3156 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
3157 if (result
&& TREE_CODE (result
) == SSA_NAME
)
3158 result
= SSA_VAL (result
);
3159 vr1
->result
= result
;
3161 slot
= valid_info
->references
->find_slot_with_hash (vr1
, vr1
->hashcode
,
3164 /* At this point we should have all the things inserted that we have
3165 seen before, and we should never try inserting something that
3167 gcc_assert (!*slot
);
3170 vr1
->next
= last_inserted_ref
;
3171 last_inserted_ref
= vr1
;
3175 /* Compute and return the hash value for nary operation VBO1. */
3178 vn_nary_op_compute_hash (const vn_nary_op_t vno1
)
3180 inchash::hash hstate
;
3183 for (i
= 0; i
< vno1
->length
; ++i
)
3184 if (TREE_CODE (vno1
->op
[i
]) == SSA_NAME
)
3185 vno1
->op
[i
] = SSA_VAL (vno1
->op
[i
]);
3187 if (((vno1
->length
== 2
3188 && commutative_tree_code (vno1
->opcode
))
3189 || (vno1
->length
== 3
3190 && commutative_ternary_tree_code (vno1
->opcode
)))
3191 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1]))
3192 std::swap (vno1
->op
[0], vno1
->op
[1]);
3193 else if (TREE_CODE_CLASS (vno1
->opcode
) == tcc_comparison
3194 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1]))
3196 std::swap (vno1
->op
[0], vno1
->op
[1]);
3197 vno1
->opcode
= swap_tree_comparison (vno1
->opcode
);
3200 hstate
.add_int (vno1
->opcode
);
3201 for (i
= 0; i
< vno1
->length
; ++i
)
3202 inchash::add_expr (vno1
->op
[i
], hstate
);
3204 return hstate
.end ();
3207 /* Compare nary operations VNO1 and VNO2 and return true if they are
3211 vn_nary_op_eq (const_vn_nary_op_t
const vno1
, const_vn_nary_op_t
const vno2
)
3215 if (vno1
->hashcode
!= vno2
->hashcode
)
3218 if (vno1
->length
!= vno2
->length
)
3221 if (vno1
->opcode
!= vno2
->opcode
3222 || !types_compatible_p (vno1
->type
, vno2
->type
))
3225 for (i
= 0; i
< vno1
->length
; ++i
)
3226 if (!expressions_equal_p (vno1
->op
[i
], vno2
->op
[i
]))
3229 /* BIT_INSERT_EXPR has an implict operand as the type precision
3230 of op1. Need to check to make sure they are the same. */
3231 if (vno1
->opcode
== BIT_INSERT_EXPR
3232 && TREE_CODE (vno1
->op
[1]) == INTEGER_CST
3233 && TYPE_PRECISION (TREE_TYPE (vno1
->op
[1]))
3234 != TYPE_PRECISION (TREE_TYPE (vno2
->op
[1])))
3240 /* Initialize VNO from the pieces provided. */
3243 init_vn_nary_op_from_pieces (vn_nary_op_t vno
, unsigned int length
,
3244 enum tree_code code
, tree type
, tree
*ops
)
3247 vno
->length
= length
;
3249 memcpy (&vno
->op
[0], ops
, sizeof (tree
) * length
);
3252 /* Initialize VNO from OP. */
3255 init_vn_nary_op_from_op (vn_nary_op_t vno
, tree op
)
3259 vno
->opcode
= TREE_CODE (op
);
3260 vno
->length
= TREE_CODE_LENGTH (TREE_CODE (op
));
3261 vno
->type
= TREE_TYPE (op
);
3262 for (i
= 0; i
< vno
->length
; ++i
)
3263 vno
->op
[i
] = TREE_OPERAND (op
, i
);
3266 /* Return the number of operands for a vn_nary ops structure from STMT. */
3269 vn_nary_length_from_stmt (gimple
*stmt
)
3271 switch (gimple_assign_rhs_code (stmt
))
3275 case VIEW_CONVERT_EXPR
:
3282 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
3285 return gimple_num_ops (stmt
) - 1;
3289 /* Initialize VNO from STMT. */
3292 init_vn_nary_op_from_stmt (vn_nary_op_t vno
, gimple
*stmt
)
3296 vno
->opcode
= gimple_assign_rhs_code (stmt
);
3297 vno
->type
= gimple_expr_type (stmt
);
3298 switch (vno
->opcode
)
3302 case VIEW_CONVERT_EXPR
:
3304 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
3309 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
3310 vno
->op
[1] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1);
3311 vno
->op
[2] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
3315 vno
->length
= CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
3316 for (i
= 0; i
< vno
->length
; ++i
)
3317 vno
->op
[i
] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt
), i
)->value
;
3321 gcc_checking_assert (!gimple_assign_single_p (stmt
));
3322 vno
->length
= gimple_num_ops (stmt
) - 1;
3323 for (i
= 0; i
< vno
->length
; ++i
)
3324 vno
->op
[i
] = gimple_op (stmt
, i
+ 1);
3328 /* Compute the hashcode for VNO and look for it in the hash table;
3329 return the resulting value number if it exists in the hash table.
3330 Return NULL_TREE if it does not exist in the hash table or if the
3331 result field of the operation is NULL. VNRESULT will contain the
3332 vn_nary_op_t from the hashtable if it exists. */
3335 vn_nary_op_lookup_1 (vn_nary_op_t vno
, vn_nary_op_t
*vnresult
)
3337 vn_nary_op_s
**slot
;
3342 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
3343 slot
= valid_info
->nary
->find_slot_with_hash (vno
, vno
->hashcode
, NO_INSERT
);
3348 return (*slot
)->predicated_values
? NULL_TREE
: (*slot
)->u
.result
;
3351 /* Lookup a n-ary operation by its pieces and return the resulting value
3352 number if it exists in the hash table. Return NULL_TREE if it does
3353 not exist in the hash table or if the result field of the operation
3354 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
3358 vn_nary_op_lookup_pieces (unsigned int length
, enum tree_code code
,
3359 tree type
, tree
*ops
, vn_nary_op_t
*vnresult
)
3361 vn_nary_op_t vno1
= XALLOCAVAR (struct vn_nary_op_s
,
3362 sizeof_vn_nary_op (length
));
3363 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
3364 return vn_nary_op_lookup_1 (vno1
, vnresult
);
3367 /* Lookup OP in the current hash table, and return the resulting value
3368 number if it exists in the hash table. Return NULL_TREE if it does
3369 not exist in the hash table or if the result field of the operation
3370 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
3374 vn_nary_op_lookup (tree op
, vn_nary_op_t
*vnresult
)
3377 = XALLOCAVAR (struct vn_nary_op_s
,
3378 sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op
))));
3379 init_vn_nary_op_from_op (vno1
, op
);
3380 return vn_nary_op_lookup_1 (vno1
, vnresult
);
3383 /* Lookup the rhs of STMT in the current hash table, and return the resulting
3384 value number if it exists in the hash table. Return NULL_TREE if
3385 it does not exist in the hash table. VNRESULT will contain the
3386 vn_nary_op_t from the hashtable if it exists. */
3389 vn_nary_op_lookup_stmt (gimple
*stmt
, vn_nary_op_t
*vnresult
)
3392 = XALLOCAVAR (struct vn_nary_op_s
,
3393 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt
)));
3394 init_vn_nary_op_from_stmt (vno1
, stmt
);
3395 return vn_nary_op_lookup_1 (vno1
, vnresult
);
3398 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
3401 alloc_vn_nary_op_noinit (unsigned int length
, struct obstack
*stack
)
3403 return (vn_nary_op_t
) obstack_alloc (stack
, sizeof_vn_nary_op (length
));
3406 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
3410 alloc_vn_nary_op (unsigned int length
, tree result
, unsigned int value_id
)
3412 vn_nary_op_t vno1
= alloc_vn_nary_op_noinit (length
, &vn_tables_obstack
);
3414 vno1
->value_id
= value_id
;
3415 vno1
->length
= length
;
3416 vno1
->predicated_values
= 0;
3417 vno1
->u
.result
= result
;
3422 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
3423 VNO->HASHCODE first. */
3426 vn_nary_op_insert_into (vn_nary_op_t vno
, vn_nary_op_table_type
*table
,
3429 vn_nary_op_s
**slot
;
3433 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
3434 gcc_assert (! vno
->predicated_values
3435 || (! vno
->u
.values
->next
3436 && vno
->u
.values
->n
== 1));
3439 slot
= table
->find_slot_with_hash (vno
, vno
->hashcode
, INSERT
);
3440 vno
->unwind_to
= *slot
;
3443 /* Prefer non-predicated values.
3444 ??? Only if those are constant, otherwise, with constant predicated
3445 value, turn them into predicated values with entry-block validity
3446 (??? but we always find the first valid result currently). */
3447 if ((*slot
)->predicated_values
3448 && ! vno
->predicated_values
)
3450 /* ??? We cannot remove *slot from the unwind stack list.
3451 For the moment we deal with this by skipping not found
3452 entries but this isn't ideal ... */
3454 /* ??? Maintain a stack of states we can unwind in
3455 vn_nary_op_s? But how far do we unwind? In reality
3456 we need to push change records somewhere... Or not
3457 unwind vn_nary_op_s and linking them but instead
3458 unwind the results "list", linking that, which also
3459 doesn't move on hashtable resize. */
3460 /* We can also have a ->unwind_to recording *slot there.
3461 That way we can make u.values a fixed size array with
3462 recording the number of entries but of course we then
3463 have always N copies for each unwind_to-state. Or we
3464 make sure to only ever append and each unwinding will
3465 pop off one entry (but how to deal with predicated
3466 replaced with non-predicated here?) */
3467 vno
->next
= last_inserted_nary
;
3468 last_inserted_nary
= vno
;
3471 else if (vno
->predicated_values
3472 && ! (*slot
)->predicated_values
)
3474 else if (vno
->predicated_values
3475 && (*slot
)->predicated_values
)
3477 /* ??? Factor this all into a insert_single_predicated_value
3479 gcc_assert (!vno
->u
.values
->next
&& vno
->u
.values
->n
== 1);
3481 = BASIC_BLOCK_FOR_FN (cfun
, vno
->u
.values
->valid_dominated_by_p
[0]);
3482 vn_pval
*nval
= vno
->u
.values
;
3483 vn_pval
**next
= &vno
->u
.values
;
3485 for (vn_pval
*val
= (*slot
)->u
.values
; val
; val
= val
->next
)
3487 if (expressions_equal_p (val
->result
, vno
->u
.values
->result
))
3490 for (unsigned i
= 0; i
< val
->n
; ++i
)
3493 = BASIC_BLOCK_FOR_FN (cfun
,
3494 val
->valid_dominated_by_p
[i
]);
3495 if (dominated_by_p (CDI_DOMINATORS
, vno_bb
, val_bb
))
3496 /* Value registered with more generic predicate. */
3498 else if (dominated_by_p (CDI_DOMINATORS
, val_bb
, vno_bb
))
3499 /* Shouldn't happen, we insert in RPO order. */
3503 *next
= (vn_pval
*) obstack_alloc (&vn_tables_obstack
,
3505 + val
->n
* sizeof (int));
3506 (*next
)->next
= NULL
;
3507 (*next
)->result
= val
->result
;
3508 (*next
)->n
= val
->n
+ 1;
3509 memcpy ((*next
)->valid_dominated_by_p
,
3510 val
->valid_dominated_by_p
,
3511 val
->n
* sizeof (int));
3512 (*next
)->valid_dominated_by_p
[val
->n
] = vno_bb
->index
;
3513 next
= &(*next
)->next
;
3514 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3515 fprintf (dump_file
, "Appending predicate to value.\n");
3518 /* Copy other predicated values. */
3519 *next
= (vn_pval
*) obstack_alloc (&vn_tables_obstack
,
3521 + (val
->n
-1) * sizeof (int));
3522 memcpy (*next
, val
, sizeof (vn_pval
) + (val
->n
-1) * sizeof (int));
3523 (*next
)->next
= NULL
;
3524 next
= &(*next
)->next
;
3530 vno
->next
= last_inserted_nary
;
3531 last_inserted_nary
= vno
;
3535 /* While we do not want to insert things twice it's awkward to
3536 avoid it in the case where visit_nary_op pattern-matches stuff
3537 and ends up simplifying the replacement to itself. We then
3538 get two inserts, one from visit_nary_op and one from
3539 vn_nary_build_or_lookup.
3540 So allow inserts with the same value number. */
3541 if ((*slot
)->u
.result
== vno
->u
.result
)
3545 /* ??? There's also optimistic vs. previous commited state merging
3546 that is problematic for the case of unwinding. */
3548 /* ??? We should return NULL if we do not use 'vno' and have the
3549 caller release it. */
3550 gcc_assert (!*slot
);
3553 vno
->next
= last_inserted_nary
;
3554 last_inserted_nary
= vno
;
3558 /* Insert a n-ary operation into the current hash table using it's
3559 pieces. Return the vn_nary_op_t structure we created and put in
3563 vn_nary_op_insert_pieces (unsigned int length
, enum tree_code code
,
3564 tree type
, tree
*ops
,
3565 tree result
, unsigned int value_id
)
3567 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, result
, value_id
);
3568 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
3569 return vn_nary_op_insert_into (vno1
, valid_info
->nary
, true);
3573 vn_nary_op_insert_pieces_predicated (unsigned int length
, enum tree_code code
,
3574 tree type
, tree
*ops
,
3575 tree result
, unsigned int value_id
,
3578 /* ??? Currently tracking BBs. */
3579 if (! single_pred_p (pred_e
->dest
))
3581 /* Never record for backedges. */
3582 if (pred_e
->flags
& EDGE_DFS_BACK
)
3587 /* Ignore backedges. */
3588 FOR_EACH_EDGE (e
, ei
, pred_e
->dest
->preds
)
3589 if (! dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
3594 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
3595 /* ??? Fix dumping, but currently we only get comparisons. */
3596 && TREE_CODE_CLASS (code
) == tcc_comparison
)
3598 fprintf (dump_file
, "Recording on edge %d->%d ", pred_e
->src
->index
,
3599 pred_e
->dest
->index
);
3600 print_generic_expr (dump_file
, ops
[0], TDF_SLIM
);
3601 fprintf (dump_file
, " %s ", get_tree_code_name (code
));
3602 print_generic_expr (dump_file
, ops
[1], TDF_SLIM
);
3603 fprintf (dump_file
, " == %s\n",
3604 integer_zerop (result
) ? "false" : "true");
3606 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, NULL_TREE
, value_id
);
3607 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
3608 vno1
->predicated_values
= 1;
3609 vno1
->u
.values
= (vn_pval
*) obstack_alloc (&vn_tables_obstack
,
3611 vno1
->u
.values
->next
= NULL
;
3612 vno1
->u
.values
->result
= result
;
3613 vno1
->u
.values
->n
= 1;
3614 vno1
->u
.values
->valid_dominated_by_p
[0] = pred_e
->dest
->index
;
3615 return vn_nary_op_insert_into (vno1
, valid_info
->nary
, true);
3619 dominated_by_p_w_unex (basic_block bb1
, basic_block bb2
);
3622 vn_nary_op_get_predicated_value (vn_nary_op_t vno
, basic_block bb
)
3624 if (! vno
->predicated_values
)
3625 return vno
->u
.result
;
3626 for (vn_pval
*val
= vno
->u
.values
; val
; val
= val
->next
)
3627 for (unsigned i
= 0; i
< val
->n
; ++i
)
3628 if (dominated_by_p_w_unex (bb
,
3630 (cfun
, val
->valid_dominated_by_p
[i
])))
3635 /* Insert OP into the current hash table with a value number of
3636 RESULT. Return the vn_nary_op_t structure we created and put in
3640 vn_nary_op_insert (tree op
, tree result
)
3642 unsigned length
= TREE_CODE_LENGTH (TREE_CODE (op
));
3645 vno1
= alloc_vn_nary_op (length
, result
, VN_INFO (result
)->value_id
);
3646 init_vn_nary_op_from_op (vno1
, op
);
3647 return vn_nary_op_insert_into (vno1
, valid_info
->nary
, true);
3650 /* Insert the rhs of STMT into the current hash table with a value number of
3654 vn_nary_op_insert_stmt (gimple
*stmt
, tree result
)
3657 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt
),
3658 result
, VN_INFO (result
)->value_id
);
3659 init_vn_nary_op_from_stmt (vno1
, stmt
);
3660 return vn_nary_op_insert_into (vno1
, valid_info
->nary
, true);
3663 /* Compute a hashcode for PHI operation VP1 and return it. */
3665 static inline hashval_t
3666 vn_phi_compute_hash (vn_phi_t vp1
)
3668 inchash::hash
hstate (EDGE_COUNT (vp1
->block
->preds
) > 2
3669 ? vp1
->block
->index
: EDGE_COUNT (vp1
->block
->preds
));
3675 /* If all PHI arguments are constants we need to distinguish
3676 the PHI node via its type. */
3678 hstate
.merge_hash (vn_hash_type (type
));
3680 FOR_EACH_EDGE (e
, ei
, vp1
->block
->preds
)
3682 /* Don't hash backedge values they need to be handled as VN_TOP
3683 for optimistic value-numbering. */
3684 if (e
->flags
& EDGE_DFS_BACK
)
3687 phi1op
= vp1
->phiargs
[e
->dest_idx
];
3688 if (phi1op
== VN_TOP
)
3690 inchash::add_expr (phi1op
, hstate
);
3693 return hstate
.end ();
3697 /* Return true if COND1 and COND2 represent the same condition, set
3698 *INVERTED_P if one needs to be inverted to make it the same as
3702 cond_stmts_equal_p (gcond
*cond1
, tree lhs1
, tree rhs1
,
3703 gcond
*cond2
, tree lhs2
, tree rhs2
, bool *inverted_p
)
3705 enum tree_code code1
= gimple_cond_code (cond1
);
3706 enum tree_code code2
= gimple_cond_code (cond2
);
3708 *inverted_p
= false;
3711 else if (code1
== swap_tree_comparison (code2
))
3712 std::swap (lhs2
, rhs2
);
3713 else if (code1
== invert_tree_comparison (code2
, HONOR_NANS (lhs2
)))
3715 else if (code1
== invert_tree_comparison
3716 (swap_tree_comparison (code2
), HONOR_NANS (lhs2
)))
3718 std::swap (lhs2
, rhs2
);
3724 return ((expressions_equal_p (lhs1
, lhs2
)
3725 && expressions_equal_p (rhs1
, rhs2
))
3726 || (commutative_tree_code (code1
)
3727 && expressions_equal_p (lhs1
, rhs2
)
3728 && expressions_equal_p (rhs1
, lhs2
)));
3731 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
3734 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
)
3736 if (vp1
->hashcode
!= vp2
->hashcode
)
3739 if (vp1
->block
!= vp2
->block
)
3741 if (EDGE_COUNT (vp1
->block
->preds
) != EDGE_COUNT (vp2
->block
->preds
))
3744 switch (EDGE_COUNT (vp1
->block
->preds
))
3747 /* Single-arg PHIs are just copies. */
3752 /* Rule out backedges into the PHI. */
3753 if (vp1
->block
->loop_father
->header
== vp1
->block
3754 || vp2
->block
->loop_father
->header
== vp2
->block
)
3757 /* If the PHI nodes do not have compatible types
3758 they are not the same. */
3759 if (!types_compatible_p (vp1
->type
, vp2
->type
))
3763 = get_immediate_dominator (CDI_DOMINATORS
, vp1
->block
);
3765 = get_immediate_dominator (CDI_DOMINATORS
, vp2
->block
);
3766 /* If the immediate dominator end in switch stmts multiple
3767 values may end up in the same PHI arg via intermediate
3769 if (EDGE_COUNT (idom1
->succs
) != 2
3770 || EDGE_COUNT (idom2
->succs
) != 2)
3773 /* Verify the controlling stmt is the same. */
3774 gcond
*last1
= safe_dyn_cast
<gcond
*> (last_stmt (idom1
));
3775 gcond
*last2
= safe_dyn_cast
<gcond
*> (last_stmt (idom2
));
3776 if (! last1
|| ! last2
)
3779 if (! cond_stmts_equal_p (last1
, vp1
->cclhs
, vp1
->ccrhs
,
3780 last2
, vp2
->cclhs
, vp2
->ccrhs
,
3784 /* Get at true/false controlled edges into the PHI. */
3785 edge te1
, te2
, fe1
, fe2
;
3786 if (! extract_true_false_controlled_edges (idom1
, vp1
->block
,
3788 || ! extract_true_false_controlled_edges (idom2
, vp2
->block
,
3792 /* Swap edges if the second condition is the inverted of the
3795 std::swap (te2
, fe2
);
3797 /* ??? Handle VN_TOP specially. */
3798 if (! expressions_equal_p (vp1
->phiargs
[te1
->dest_idx
],
3799 vp2
->phiargs
[te2
->dest_idx
])
3800 || ! expressions_equal_p (vp1
->phiargs
[fe1
->dest_idx
],
3801 vp2
->phiargs
[fe2
->dest_idx
]))
3812 /* If the PHI nodes do not have compatible types
3813 they are not the same. */
3814 if (!types_compatible_p (vp1
->type
, vp2
->type
))
3817 /* Any phi in the same block will have it's arguments in the
3818 same edge order, because of how we store phi nodes. */
3819 for (unsigned i
= 0; i
< EDGE_COUNT (vp1
->block
->preds
); ++i
)
3821 tree phi1op
= vp1
->phiargs
[i
];
3822 tree phi2op
= vp2
->phiargs
[i
];
3823 if (phi1op
== VN_TOP
|| phi2op
== VN_TOP
)
3825 if (!expressions_equal_p (phi1op
, phi2op
))
3832 /* Lookup PHI in the current hash table, and return the resulting
3833 value number if it exists in the hash table. Return NULL_TREE if
3834 it does not exist in the hash table. */
3837 vn_phi_lookup (gimple
*phi
, bool backedges_varying_p
)
3840 struct vn_phi_s
*vp1
;
3844 vp1
= XALLOCAVAR (struct vn_phi_s
,
3845 sizeof (struct vn_phi_s
)
3846 + (gimple_phi_num_args (phi
) - 1) * sizeof (tree
));
3848 /* Canonicalize the SSA_NAME's to their value number. */
3849 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
3851 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
3852 if (TREE_CODE (def
) == SSA_NAME
3853 && (!backedges_varying_p
|| !(e
->flags
& EDGE_DFS_BACK
)))
3854 def
= SSA_VAL (def
);
3855 vp1
->phiargs
[e
->dest_idx
] = def
;
3857 vp1
->type
= TREE_TYPE (gimple_phi_result (phi
));
3858 vp1
->block
= gimple_bb (phi
);
3859 /* Extract values of the controlling condition. */
3860 vp1
->cclhs
= NULL_TREE
;
3861 vp1
->ccrhs
= NULL_TREE
;
3862 basic_block idom1
= get_immediate_dominator (CDI_DOMINATORS
, vp1
->block
);
3863 if (EDGE_COUNT (idom1
->succs
) == 2)
3864 if (gcond
*last1
= safe_dyn_cast
<gcond
*> (last_stmt (idom1
)))
3866 /* ??? We want to use SSA_VAL here. But possibly not
3868 vp1
->cclhs
= vn_valueize (gimple_cond_lhs (last1
));
3869 vp1
->ccrhs
= vn_valueize (gimple_cond_rhs (last1
));
3871 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
3872 slot
= valid_info
->phis
->find_slot_with_hash (vp1
, vp1
->hashcode
, NO_INSERT
);
3875 return (*slot
)->result
;
3878 /* Insert PHI into the current hash table with a value number of
3882 vn_phi_insert (gimple
*phi
, tree result
, bool backedges_varying_p
)
3885 vn_phi_t vp1
= (vn_phi_t
) obstack_alloc (&vn_tables_obstack
,
3887 + ((gimple_phi_num_args (phi
) - 1)
3892 /* Canonicalize the SSA_NAME's to their value number. */
3893 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
3895 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
3896 if (TREE_CODE (def
) == SSA_NAME
3897 && (!backedges_varying_p
|| !(e
->flags
& EDGE_DFS_BACK
)))
3898 def
= SSA_VAL (def
);
3899 vp1
->phiargs
[e
->dest_idx
] = def
;
3901 vp1
->value_id
= VN_INFO (result
)->value_id
;
3902 vp1
->type
= TREE_TYPE (gimple_phi_result (phi
));
3903 vp1
->block
= gimple_bb (phi
);
3904 /* Extract values of the controlling condition. */
3905 vp1
->cclhs
= NULL_TREE
;
3906 vp1
->ccrhs
= NULL_TREE
;
3907 basic_block idom1
= get_immediate_dominator (CDI_DOMINATORS
, vp1
->block
);
3908 if (EDGE_COUNT (idom1
->succs
) == 2)
3909 if (gcond
*last1
= safe_dyn_cast
<gcond
*> (last_stmt (idom1
)))
3911 /* ??? We want to use SSA_VAL here. But possibly not
3913 vp1
->cclhs
= vn_valueize (gimple_cond_lhs (last1
));
3914 vp1
->ccrhs
= vn_valueize (gimple_cond_rhs (last1
));
3916 vp1
->result
= result
;
3917 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
3919 slot
= valid_info
->phis
->find_slot_with_hash (vp1
, vp1
->hashcode
, INSERT
);
3920 gcc_assert (!*slot
);
3923 vp1
->next
= last_inserted_phi
;
3924 last_inserted_phi
= vp1
;
3929 /* Return true if BB1 is dominated by BB2 taking into account edges
3930 that are not executable. */
3933 dominated_by_p_w_unex (basic_block bb1
, basic_block bb2
)
3938 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
3941 /* Before iterating we'd like to know if there exists a
3942 (executable) path from bb2 to bb1 at all, if not we can
3943 directly return false. For now simply iterate once. */
3945 /* Iterate to the single executable bb1 predecessor. */
3946 if (EDGE_COUNT (bb1
->preds
) > 1)
3949 FOR_EACH_EDGE (e
, ei
, bb1
->preds
)
3950 if (e
->flags
& EDGE_EXECUTABLE
)
3963 /* Re-do the dominance check with changed bb1. */
3964 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
3969 /* Iterate to the single executable bb2 successor. */
3971 FOR_EACH_EDGE (e
, ei
, bb2
->succs
)
3972 if (e
->flags
& EDGE_EXECUTABLE
)
3983 /* Verify the reached block is only reached through succe.
3984 If there is only one edge we can spare us the dominator
3985 check and iterate directly. */
3986 if (EDGE_COUNT (succe
->dest
->preds
) > 1)
3988 FOR_EACH_EDGE (e
, ei
, succe
->dest
->preds
)
3990 && (e
->flags
& EDGE_EXECUTABLE
))
4000 /* Re-do the dominance check with changed bb2. */
4001 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
4006 /* We could now iterate updating bb1 / bb2. */
4010 /* Set the value number of FROM to TO, return true if it has changed
4014 set_ssa_val_to (tree from
, tree to
)
4016 vn_ssa_aux_t from_info
= VN_INFO (from
);
4017 tree currval
= from_info
->valnum
; // SSA_VAL (from)
4018 poly_int64 toff
, coff
;
4020 /* The only thing we allow as value numbers are ssa_names
4021 and invariants. So assert that here. We don't allow VN_TOP
4022 as visiting a stmt should produce a value-number other than
4024 ??? Still VN_TOP can happen for unreachable code, so force
4025 it to varying in that case. Not all code is prepared to
4026 get VN_TOP on valueization. */
4029 /* ??? When iterating and visiting PHI <undef, backedge-value>
4030 for the first time we rightfully get VN_TOP and we need to
4031 preserve that to optimize for example gcc.dg/tree-ssa/ssa-sccvn-2.c.
4032 With SCCVN we were simply lucky we iterated the other PHI
4033 cycles first and thus visited the backedge-value DEF. */
4034 if (currval
== VN_TOP
)
4036 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4037 fprintf (dump_file
, "Forcing value number to varying on "
4038 "receiving VN_TOP\n");
4042 gcc_checking_assert (to
!= NULL_TREE
4043 && ((TREE_CODE (to
) == SSA_NAME
4044 && (to
== from
|| SSA_VAL (to
) == to
))
4045 || is_gimple_min_invariant (to
)));
4049 if (currval
== from
)
4051 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4053 fprintf (dump_file
, "Not changing value number of ");
4054 print_generic_expr (dump_file
, from
);
4055 fprintf (dump_file
, " from VARYING to ");
4056 print_generic_expr (dump_file
, to
);
4057 fprintf (dump_file
, "\n");
4061 bool curr_invariant
= is_gimple_min_invariant (currval
);
4062 bool curr_undefined
= (TREE_CODE (currval
) == SSA_NAME
4063 && ssa_undefined_value_p (currval
, false));
4064 if (currval
!= VN_TOP
4067 && is_gimple_min_invariant (to
))
4069 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4071 fprintf (dump_file
, "Forcing VARYING instead of changing "
4072 "value number of ");
4073 print_generic_expr (dump_file
, from
);
4074 fprintf (dump_file
, " from ");
4075 print_generic_expr (dump_file
, currval
);
4076 fprintf (dump_file
, " (non-constant) to ");
4077 print_generic_expr (dump_file
, to
);
4078 fprintf (dump_file
, " (constant)\n");
4082 else if (currval
!= VN_TOP
4084 && TREE_CODE (to
) == SSA_NAME
4085 && ssa_undefined_value_p (to
, false))
4087 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4089 fprintf (dump_file
, "Forcing VARYING instead of changing "
4090 "value number of ");
4091 print_generic_expr (dump_file
, from
);
4092 fprintf (dump_file
, " from ");
4093 print_generic_expr (dump_file
, currval
);
4094 fprintf (dump_file
, " (non-undefined) to ");
4095 print_generic_expr (dump_file
, to
);
4096 fprintf (dump_file
, " (undefined)\n");
4100 else if (TREE_CODE (to
) == SSA_NAME
4101 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to
))
4106 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4108 fprintf (dump_file
, "Setting value number of ");
4109 print_generic_expr (dump_file
, from
);
4110 fprintf (dump_file
, " to ");
4111 print_generic_expr (dump_file
, to
);
4115 && !operand_equal_p (currval
, to
, 0)
4116 /* Different undefined SSA names are not actually different. See
4117 PR82320 for a testcase were we'd otherwise not terminate iteration. */
4118 && !(TREE_CODE (currval
) == SSA_NAME
4119 && TREE_CODE (to
) == SSA_NAME
4120 && ssa_undefined_value_p (currval
, false)
4121 && ssa_undefined_value_p (to
, false))
4122 /* ??? For addresses involving volatile objects or types operand_equal_p
4123 does not reliably detect ADDR_EXPRs as equal. We know we are only
4124 getting invariant gimple addresses here, so can use
4125 get_addr_base_and_unit_offset to do this comparison. */
4126 && !(TREE_CODE (currval
) == ADDR_EXPR
4127 && TREE_CODE (to
) == ADDR_EXPR
4128 && (get_addr_base_and_unit_offset (TREE_OPERAND (currval
, 0), &coff
)
4129 == get_addr_base_and_unit_offset (TREE_OPERAND (to
, 0), &toff
))
4130 && known_eq (coff
, toff
)))
4132 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4133 fprintf (dump_file
, " (changed)\n");
4134 from_info
->valnum
= to
;
4137 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4138 fprintf (dump_file
, "\n");
4142 /* Set all definitions in STMT to value number to themselves.
4143 Return true if a value number changed. */
4146 defs_to_varying (gimple
*stmt
)
4148 bool changed
= false;
4152 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
4154 tree def
= DEF_FROM_PTR (defp
);
4155 changed
|= set_ssa_val_to (def
, def
);
4160 /* Visit a copy between LHS and RHS, return true if the value number
4164 visit_copy (tree lhs
, tree rhs
)
4167 rhs
= SSA_VAL (rhs
);
4169 return set_ssa_val_to (lhs
, rhs
);
4172 /* Lookup a value for OP in type WIDE_TYPE where the value in type of OP
4176 valueized_wider_op (tree wide_type
, tree op
)
4178 if (TREE_CODE (op
) == SSA_NAME
)
4179 op
= vn_valueize (op
);
4181 /* Either we have the op widened available. */
4184 tree tem
= vn_nary_op_lookup_pieces (1, NOP_EXPR
,
4185 wide_type
, ops
, NULL
);
4189 /* Or the op is truncated from some existing value. */
4190 if (TREE_CODE (op
) == SSA_NAME
)
4192 gimple
*def
= SSA_NAME_DEF_STMT (op
);
4193 if (is_gimple_assign (def
)
4194 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def
)))
4196 tem
= gimple_assign_rhs1 (def
);
4197 if (useless_type_conversion_p (wide_type
, TREE_TYPE (tem
)))
4199 if (TREE_CODE (tem
) == SSA_NAME
)
4200 tem
= vn_valueize (tem
);
4206 /* For constants simply extend it. */
4207 if (TREE_CODE (op
) == INTEGER_CST
)
4208 return wide_int_to_tree (wide_type
, wi::to_wide (op
));
4213 /* Visit a nary operator RHS, value number it, and return true if the
4214 value number of LHS has changed as a result. */
4217 visit_nary_op (tree lhs
, gassign
*stmt
)
4219 vn_nary_op_t vnresult
;
4220 tree result
= vn_nary_op_lookup_stmt (stmt
, &vnresult
);
4221 if (! result
&& vnresult
)
4222 result
= vn_nary_op_get_predicated_value (vnresult
, gimple_bb (stmt
));
4224 return set_ssa_val_to (lhs
, result
);
4226 /* Do some special pattern matching for redundancies of operations
4227 in different types. */
4228 enum tree_code code
= gimple_assign_rhs_code (stmt
);
4229 tree type
= TREE_TYPE (lhs
);
4230 tree rhs1
= gimple_assign_rhs1 (stmt
);
4234 /* Match arithmetic done in a different type where we can easily
4235 substitute the result from some earlier sign-changed or widened
4237 if (INTEGRAL_TYPE_P (type
)
4238 && TREE_CODE (rhs1
) == SSA_NAME
4239 /* We only handle sign-changes or zero-extension -> & mask. */
4240 && ((TYPE_UNSIGNED (TREE_TYPE (rhs1
))
4241 && TYPE_PRECISION (type
) > TYPE_PRECISION (TREE_TYPE (rhs1
)))
4242 || TYPE_PRECISION (type
) == TYPE_PRECISION (TREE_TYPE (rhs1
))))
4244 gassign
*def
= dyn_cast
<gassign
*> (SSA_NAME_DEF_STMT (rhs1
));
4246 && (gimple_assign_rhs_code (def
) == PLUS_EXPR
4247 || gimple_assign_rhs_code (def
) == MINUS_EXPR
4248 || gimple_assign_rhs_code (def
) == MULT_EXPR
))
4251 /* Either we have the op widened available. */
4252 ops
[0] = valueized_wider_op (type
,
4253 gimple_assign_rhs1 (def
));
4255 ops
[1] = valueized_wider_op (type
,
4256 gimple_assign_rhs2 (def
));
4257 if (ops
[0] && ops
[1])
4259 ops
[0] = vn_nary_op_lookup_pieces
4260 (2, gimple_assign_rhs_code (def
), type
, ops
, NULL
);
4261 /* We have wider operation available. */
4263 /* If the leader is a wrapping operation we can
4264 insert it for code hoisting w/o introducing
4265 undefined overflow. If it is not it has to
4266 be available. See PR86554. */
4267 && (TYPE_OVERFLOW_WRAPS (TREE_TYPE (ops
[0]))
4268 || (rpo_avail
&& vn_context_bb
4269 && rpo_avail
->eliminate_avail (vn_context_bb
,
4272 unsigned lhs_prec
= TYPE_PRECISION (type
);
4273 unsigned rhs_prec
= TYPE_PRECISION (TREE_TYPE (rhs1
));
4274 if (lhs_prec
== rhs_prec
)
4276 gimple_match_op
match_op (gimple_match_cond::UNCOND
,
4277 NOP_EXPR
, type
, ops
[0]);
4278 result
= vn_nary_build_or_lookup (&match_op
);
4281 bool changed
= set_ssa_val_to (lhs
, result
);
4282 vn_nary_op_insert_stmt (stmt
, result
);
4288 tree mask
= wide_int_to_tree
4289 (type
, wi::mask (rhs_prec
, false, lhs_prec
));
4290 gimple_match_op
match_op (gimple_match_cond::UNCOND
,
4294 result
= vn_nary_build_or_lookup (&match_op
);
4297 bool changed
= set_ssa_val_to (lhs
, result
);
4298 vn_nary_op_insert_stmt (stmt
, result
);
4309 bool changed
= set_ssa_val_to (lhs
, lhs
);
4310 vn_nary_op_insert_stmt (stmt
, lhs
);
4314 /* Visit a call STMT storing into LHS. Return true if the value number
4315 of the LHS has changed as a result. */
4318 visit_reference_op_call (tree lhs
, gcall
*stmt
)
4320 bool changed
= false;
4321 struct vn_reference_s vr1
;
4322 vn_reference_t vnresult
= NULL
;
4323 tree vdef
= gimple_vdef (stmt
);
4325 /* Non-ssa lhs is handled in copy_reference_ops_from_call. */
4326 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
4329 vn_reference_lookup_call (stmt
, &vnresult
, &vr1
);
4332 if (vnresult
->result_vdef
&& vdef
)
4333 changed
|= set_ssa_val_to (vdef
, vnresult
->result_vdef
);
4335 /* If the call was discovered to be pure or const reflect
4336 that as far as possible. */
4337 changed
|= set_ssa_val_to (vdef
, vuse_ssa_val (gimple_vuse (stmt
)));
4339 if (!vnresult
->result
&& lhs
)
4340 vnresult
->result
= lhs
;
4342 if (vnresult
->result
&& lhs
)
4343 changed
|= set_ssa_val_to (lhs
, vnresult
->result
);
4348 vn_reference_s
**slot
;
4349 tree vdef_val
= vdef
;
4352 /* If we value numbered an indirect functions function to
4353 one not clobbering memory value number its VDEF to its
4355 tree fn
= gimple_call_fn (stmt
);
4356 if (fn
&& TREE_CODE (fn
) == SSA_NAME
)
4359 if (TREE_CODE (fn
) == ADDR_EXPR
4360 && TREE_CODE (TREE_OPERAND (fn
, 0)) == FUNCTION_DECL
4361 && (flags_from_decl_or_type (TREE_OPERAND (fn
, 0))
4362 & (ECF_CONST
| ECF_PURE
)))
4363 vdef_val
= vuse_ssa_val (gimple_vuse (stmt
));
4365 changed
|= set_ssa_val_to (vdef
, vdef_val
);
4368 changed
|= set_ssa_val_to (lhs
, lhs
);
4369 vr2
= XOBNEW (&vn_tables_obstack
, vn_reference_s
);
4370 vr2
->vuse
= vr1
.vuse
;
4371 /* As we are not walking the virtual operand chain we know the
4372 shared_lookup_references are still original so we can re-use
4374 vr2
->operands
= vr1
.operands
.copy ();
4375 vr2
->type
= vr1
.type
;
4377 vr2
->hashcode
= vr1
.hashcode
;
4379 vr2
->result_vdef
= vdef_val
;
4381 slot
= valid_info
->references
->find_slot_with_hash (vr2
, vr2
->hashcode
,
4383 gcc_assert (!*slot
);
4385 vr2
->next
= last_inserted_ref
;
4386 last_inserted_ref
= vr2
;
4392 /* Visit a load from a reference operator RHS, part of STMT, value number it,
4393 and return true if the value number of the LHS has changed as a result. */
4396 visit_reference_op_load (tree lhs
, tree op
, gimple
*stmt
)
4398 bool changed
= false;
4402 last_vuse
= gimple_vuse (stmt
);
4403 result
= vn_reference_lookup (op
, gimple_vuse (stmt
),
4404 default_vn_walk_kind
, NULL
, true, &last_vuse
);
4406 /* We handle type-punning through unions by value-numbering based
4407 on offset and size of the access. Be prepared to handle a
4408 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
4410 && !useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (op
)))
4412 /* We will be setting the value number of lhs to the value number
4413 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
4414 So first simplify and lookup this expression to see if it
4415 is already available. */
4416 gimple_match_op
res_op (gimple_match_cond::UNCOND
,
4417 VIEW_CONVERT_EXPR
, TREE_TYPE (op
), result
);
4418 result
= vn_nary_build_or_lookup (&res_op
);
4419 /* When building the conversion fails avoid inserting the reference
4422 return set_ssa_val_to (lhs
, lhs
);
4426 changed
= set_ssa_val_to (lhs
, result
);
4429 changed
= set_ssa_val_to (lhs
, lhs
);
4430 vn_reference_insert (op
, lhs
, last_vuse
, NULL_TREE
);
4437 /* Visit a store to a reference operator LHS, part of STMT, value number it,
4438 and return true if the value number of the LHS has changed as a result. */
4441 visit_reference_op_store (tree lhs
, tree op
, gimple
*stmt
)
4443 bool changed
= false;
4444 vn_reference_t vnresult
= NULL
;
4446 bool resultsame
= false;
4447 tree vuse
= gimple_vuse (stmt
);
4448 tree vdef
= gimple_vdef (stmt
);
4450 if (TREE_CODE (op
) == SSA_NAME
)
4453 /* First we want to lookup using the *vuses* from the store and see
4454 if there the last store to this location with the same address
4457 The vuses represent the memory state before the store. If the
4458 memory state, address, and value of the store is the same as the
4459 last store to this location, then this store will produce the
4460 same memory state as that store.
4462 In this case the vdef versions for this store are value numbered to those
4463 vuse versions, since they represent the same memory state after
4466 Otherwise, the vdefs for the store are used when inserting into
4467 the table, since the store generates a new memory state. */
4469 vn_reference_lookup (lhs
, vuse
, VN_NOWALK
, &vnresult
, false);
4471 && vnresult
->result
)
4473 tree result
= vnresult
->result
;
4474 gcc_checking_assert (TREE_CODE (result
) != SSA_NAME
4475 || result
== SSA_VAL (result
));
4476 resultsame
= expressions_equal_p (result
, op
);
4479 /* If the TBAA state isn't compatible for downstream reads
4480 we cannot value-number the VDEFs the same. */
4481 alias_set_type set
= get_alias_set (lhs
);
4482 if (vnresult
->set
!= set
4483 && ! alias_set_subset_of (set
, vnresult
->set
))
4490 /* Only perform the following when being called from PRE
4491 which embeds tail merging. */
4492 if (default_vn_walk_kind
== VN_WALK
)
4494 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
4495 vn_reference_lookup (assign
, vuse
, VN_NOWALK
, &vnresult
, false);
4498 VN_INFO (vdef
)->visited
= true;
4499 return set_ssa_val_to (vdef
, vnresult
->result_vdef
);
4503 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4505 fprintf (dump_file
, "No store match\n");
4506 fprintf (dump_file
, "Value numbering store ");
4507 print_generic_expr (dump_file
, lhs
);
4508 fprintf (dump_file
, " to ");
4509 print_generic_expr (dump_file
, op
);
4510 fprintf (dump_file
, "\n");
4512 /* Have to set value numbers before insert, since insert is
4513 going to valueize the references in-place. */
4515 changed
|= set_ssa_val_to (vdef
, vdef
);
4517 /* Do not insert structure copies into the tables. */
4518 if (is_gimple_min_invariant (op
)
4519 || is_gimple_reg (op
))
4520 vn_reference_insert (lhs
, op
, vdef
, NULL
);
4522 /* Only perform the following when being called from PRE
4523 which embeds tail merging. */
4524 if (default_vn_walk_kind
== VN_WALK
)
4526 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
4527 vn_reference_insert (assign
, lhs
, vuse
, vdef
);
4532 /* We had a match, so value number the vdef to have the value
4533 number of the vuse it came from. */
4535 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4536 fprintf (dump_file
, "Store matched earlier value, "
4537 "value numbering store vdefs to matching vuses.\n");
4539 changed
|= set_ssa_val_to (vdef
, SSA_VAL (vuse
));
4545 /* Visit and value number PHI, return true if the value number
4546 changed. When BACKEDGES_VARYING_P is true then assume all
4547 backedge values are varying. When INSERTED is not NULL then
4548 this is just a ahead query for a possible iteration, set INSERTED
4549 to true if we'd insert into the hashtable. */
4552 visit_phi (gimple
*phi
, bool *inserted
, bool backedges_varying_p
)
4554 tree result
, sameval
= VN_TOP
, seen_undef
= NULL_TREE
;
4555 tree backedge_val
= NULL_TREE
;
4556 bool seen_non_backedge
= false;
4557 tree sameval_base
= NULL_TREE
;
4558 poly_int64 soff
, doff
;
4559 unsigned n_executable
= 0;
4563 /* TODO: We could check for this in initialization, and replace this
4564 with a gcc_assert. */
4565 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
4566 return set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
4568 /* We track whether a PHI was CSEd to to avoid excessive iterations
4569 that would be necessary only because the PHI changed arguments
4572 gimple_set_plf (phi
, GF_PLF_1
, false);
4574 /* See if all non-TOP arguments have the same value. TOP is
4575 equivalent to everything, so we can ignore it. */
4576 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
4577 if (e
->flags
& EDGE_EXECUTABLE
)
4579 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
4582 if (TREE_CODE (def
) == SSA_NAME
)
4584 if (!backedges_varying_p
|| !(e
->flags
& EDGE_DFS_BACK
))
4585 def
= SSA_VAL (def
);
4586 if (e
->flags
& EDGE_DFS_BACK
)
4589 if (!(e
->flags
& EDGE_DFS_BACK
))
4590 seen_non_backedge
= true;
4593 /* Ignore undefined defs for sameval but record one. */
4594 else if (TREE_CODE (def
) == SSA_NAME
4595 && ! virtual_operand_p (def
)
4596 && ssa_undefined_value_p (def
, false))
4598 else if (sameval
== VN_TOP
)
4600 else if (!expressions_equal_p (def
, sameval
))
4602 /* We know we're arriving only with invariant addresses here,
4603 try harder comparing them. We can do some caching here
4604 which we cannot do in expressions_equal_p. */
4605 if (TREE_CODE (def
) == ADDR_EXPR
4606 && TREE_CODE (sameval
) == ADDR_EXPR
4607 && sameval_base
!= (void *)-1)
4610 sameval_base
= get_addr_base_and_unit_offset
4611 (TREE_OPERAND (sameval
, 0), &soff
);
4613 sameval_base
= (tree
)(void *)-1;
4614 else if ((get_addr_base_and_unit_offset
4615 (TREE_OPERAND (def
, 0), &doff
) == sameval_base
)
4616 && known_eq (soff
, doff
))
4619 sameval
= NULL_TREE
;
4624 /* If the value we want to use is flowing over the backedge and we
4625 should take it as VARYING but it has a non-VARYING value drop to
4627 If we value-number a virtual operand never value-number to the
4628 value from the backedge as that confuses the alias-walking code.
4629 See gcc.dg/torture/pr87176.c. If the value is the same on a
4630 non-backedge everything is OK though. */
4633 && !seen_non_backedge
4634 && TREE_CODE (backedge_val
) == SSA_NAME
4635 && sameval
== backedge_val
4636 && (SSA_NAME_IS_VIRTUAL_OPERAND (backedge_val
)
4637 || SSA_VAL (backedge_val
) != backedge_val
))
4638 /* Do not value-number a virtual operand to sth not visited though
4639 given that allows us to escape a region in alias walking. */
4641 && TREE_CODE (sameval
) == SSA_NAME
4642 && !SSA_NAME_IS_DEFAULT_DEF (sameval
)
4643 && SSA_NAME_IS_VIRTUAL_OPERAND (sameval
)
4644 && (SSA_VAL (sameval
, &visited_p
), !visited_p
)))
4645 /* Note this just drops to VARYING without inserting the PHI into
4647 result
= PHI_RESULT (phi
);
4648 /* If none of the edges was executable keep the value-number at VN_TOP,
4649 if only a single edge is exectuable use its value. */
4650 else if (n_executable
<= 1)
4651 result
= seen_undef
? seen_undef
: sameval
;
4652 /* If we saw only undefined values and VN_TOP use one of the
4653 undefined values. */
4654 else if (sameval
== VN_TOP
)
4655 result
= seen_undef
? seen_undef
: sameval
;
4656 /* First see if it is equivalent to a phi node in this block. We prefer
4657 this as it allows IV elimination - see PRs 66502 and 67167. */
4658 else if ((result
= vn_phi_lookup (phi
, backedges_varying_p
)))
4661 && TREE_CODE (result
) == SSA_NAME
4662 && gimple_code (SSA_NAME_DEF_STMT (result
)) == GIMPLE_PHI
)
4664 gimple_set_plf (SSA_NAME_DEF_STMT (result
), GF_PLF_1
, true);
4665 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4667 fprintf (dump_file
, "Marking CSEd to PHI node ");
4668 print_gimple_expr (dump_file
, SSA_NAME_DEF_STMT (result
),
4670 fprintf (dump_file
, "\n");
4674 /* If all values are the same use that, unless we've seen undefined
4675 values as well and the value isn't constant.
4676 CCP/copyprop have the same restriction to not remove uninit warnings. */
4678 && (! seen_undef
|| is_gimple_min_invariant (sameval
)))
4682 result
= PHI_RESULT (phi
);
4683 /* Only insert PHIs that are varying, for constant value numbers
4684 we mess up equivalences otherwise as we are only comparing
4685 the immediate controlling predicates. */
4686 vn_phi_insert (phi
, result
, backedges_varying_p
);
4691 return set_ssa_val_to (PHI_RESULT (phi
), result
);
4694 /* Try to simplify RHS using equivalences and constant folding. */
4697 try_to_simplify (gassign
*stmt
)
4699 enum tree_code code
= gimple_assign_rhs_code (stmt
);
4702 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
4703 in this case, there is no point in doing extra work. */
4704 if (code
== SSA_NAME
)
4707 /* First try constant folding based on our current lattice. */
4708 mprts_hook
= vn_lookup_simplify_result
;
4709 tem
= gimple_fold_stmt_to_constant_1 (stmt
, vn_valueize
, vn_valueize
);
4712 && (TREE_CODE (tem
) == SSA_NAME
4713 || is_gimple_min_invariant (tem
)))
4719 /* Visit and value number STMT, return true if the value number
4723 visit_stmt (gimple
*stmt
, bool backedges_varying_p
= false)
4725 bool changed
= false;
4727 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4729 fprintf (dump_file
, "Value numbering stmt = ");
4730 print_gimple_stmt (dump_file
, stmt
, 0);
4733 if (gimple_code (stmt
) == GIMPLE_PHI
)
4734 changed
= visit_phi (stmt
, NULL
, backedges_varying_p
);
4735 else if (gimple_has_volatile_ops (stmt
))
4736 changed
= defs_to_varying (stmt
);
4737 else if (gassign
*ass
= dyn_cast
<gassign
*> (stmt
))
4739 enum tree_code code
= gimple_assign_rhs_code (ass
);
4740 tree lhs
= gimple_assign_lhs (ass
);
4741 tree rhs1
= gimple_assign_rhs1 (ass
);
4744 /* Shortcut for copies. Simplifying copies is pointless,
4745 since we copy the expression and value they represent. */
4746 if (code
== SSA_NAME
4747 && TREE_CODE (lhs
) == SSA_NAME
)
4749 changed
= visit_copy (lhs
, rhs1
);
4752 simplified
= try_to_simplify (ass
);
4755 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4757 fprintf (dump_file
, "RHS ");
4758 print_gimple_expr (dump_file
, ass
, 0);
4759 fprintf (dump_file
, " simplified to ");
4760 print_generic_expr (dump_file
, simplified
);
4761 fprintf (dump_file
, "\n");
4764 /* Setting value numbers to constants will occasionally
4765 screw up phi congruence because constants are not
4766 uniquely associated with a single ssa name that can be
4769 && is_gimple_min_invariant (simplified
)
4770 && TREE_CODE (lhs
) == SSA_NAME
)
4772 changed
= set_ssa_val_to (lhs
, simplified
);
4776 && TREE_CODE (simplified
) == SSA_NAME
4777 && TREE_CODE (lhs
) == SSA_NAME
)
4779 changed
= visit_copy (lhs
, simplified
);
4783 if ((TREE_CODE (lhs
) == SSA_NAME
4784 /* We can substitute SSA_NAMEs that are live over
4785 abnormal edges with their constant value. */
4786 && !(gimple_assign_copy_p (ass
)
4787 && is_gimple_min_invariant (rhs1
))
4789 && is_gimple_min_invariant (simplified
))
4790 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
4791 /* Stores or copies from SSA_NAMEs that are live over
4792 abnormal edges are a problem. */
4793 || (code
== SSA_NAME
4794 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
)))
4795 changed
= defs_to_varying (ass
);
4796 else if (REFERENCE_CLASS_P (lhs
)
4798 changed
= visit_reference_op_store (lhs
, rhs1
, ass
);
4799 else if (TREE_CODE (lhs
) == SSA_NAME
)
4801 if ((gimple_assign_copy_p (ass
)
4802 && is_gimple_min_invariant (rhs1
))
4804 && is_gimple_min_invariant (simplified
)))
4807 changed
= set_ssa_val_to (lhs
, simplified
);
4809 changed
= set_ssa_val_to (lhs
, rhs1
);
4813 /* Visit the original statement. */
4814 switch (vn_get_stmt_kind (ass
))
4817 changed
= visit_nary_op (lhs
, ass
);
4820 changed
= visit_reference_op_load (lhs
, rhs1
, ass
);
4823 changed
= defs_to_varying (ass
);
4829 changed
= defs_to_varying (ass
);
4831 else if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
4833 tree lhs
= gimple_call_lhs (call_stmt
);
4834 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
4836 /* Try constant folding based on our current lattice. */
4837 tree simplified
= gimple_fold_stmt_to_constant_1 (call_stmt
,
4841 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4843 fprintf (dump_file
, "call ");
4844 print_gimple_expr (dump_file
, call_stmt
, 0);
4845 fprintf (dump_file
, " simplified to ");
4846 print_generic_expr (dump_file
, simplified
);
4847 fprintf (dump_file
, "\n");
4850 /* Setting value numbers to constants will occasionally
4851 screw up phi congruence because constants are not
4852 uniquely associated with a single ssa name that can be
4855 && is_gimple_min_invariant (simplified
))
4857 changed
= set_ssa_val_to (lhs
, simplified
);
4858 if (gimple_vdef (call_stmt
))
4859 changed
|= set_ssa_val_to (gimple_vdef (call_stmt
),
4860 SSA_VAL (gimple_vuse (call_stmt
)));
4864 && TREE_CODE (simplified
) == SSA_NAME
)
4866 changed
= visit_copy (lhs
, simplified
);
4867 if (gimple_vdef (call_stmt
))
4868 changed
|= set_ssa_val_to (gimple_vdef (call_stmt
),
4869 SSA_VAL (gimple_vuse (call_stmt
)));
4872 else if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
4874 changed
= defs_to_varying (call_stmt
);
4879 /* Pick up flags from a devirtualization target. */
4880 tree fn
= gimple_call_fn (stmt
);
4881 int extra_fnflags
= 0;
4882 if (fn
&& TREE_CODE (fn
) == SSA_NAME
)
4885 if (TREE_CODE (fn
) == ADDR_EXPR
4886 && TREE_CODE (TREE_OPERAND (fn
, 0)) == FUNCTION_DECL
)
4887 extra_fnflags
= flags_from_decl_or_type (TREE_OPERAND (fn
, 0));
4889 if (!gimple_call_internal_p (call_stmt
)
4890 && (/* Calls to the same function with the same vuse
4891 and the same operands do not necessarily return the same
4892 value, unless they're pure or const. */
4893 ((gimple_call_flags (call_stmt
) | extra_fnflags
)
4894 & (ECF_PURE
| ECF_CONST
))
4895 /* If calls have a vdef, subsequent calls won't have
4896 the same incoming vuse. So, if 2 calls with vdef have the
4897 same vuse, we know they're not subsequent.
4898 We can value number 2 calls to the same function with the
4899 same vuse and the same operands which are not subsequent
4900 the same, because there is no code in the program that can
4901 compare the 2 values... */
4902 || (gimple_vdef (call_stmt
)
4903 /* ... unless the call returns a pointer which does
4904 not alias with anything else. In which case the
4905 information that the values are distinct are encoded
4907 && !(gimple_call_return_flags (call_stmt
) & ERF_NOALIAS
)
4908 /* Only perform the following when being called from PRE
4909 which embeds tail merging. */
4910 && default_vn_walk_kind
== VN_WALK
)))
4911 changed
= visit_reference_op_call (lhs
, call_stmt
);
4913 changed
= defs_to_varying (call_stmt
);
4916 changed
= defs_to_varying (stmt
);
4922 /* Allocate a value number table. */
4925 allocate_vn_table (vn_tables_t table
, unsigned size
)
4927 table
->phis
= new vn_phi_table_type (size
);
4928 table
->nary
= new vn_nary_op_table_type (size
);
4929 table
->references
= new vn_reference_table_type (size
);
4932 /* Free a value number table. */
4935 free_vn_table (vn_tables_t table
)
4937 /* Walk over elements and release vectors. */
4938 vn_reference_iterator_type hir
;
4940 FOR_EACH_HASH_TABLE_ELEMENT (*table
->references
, vr
, vn_reference_t
, hir
)
4941 vr
->operands
.release ();
4946 delete table
->references
;
4947 table
->references
= NULL
;
4950 /* Set *ID according to RESULT. */
4953 set_value_id_for_result (tree result
, unsigned int *id
)
4955 if (result
&& TREE_CODE (result
) == SSA_NAME
)
4956 *id
= VN_INFO (result
)->value_id
;
4957 else if (result
&& is_gimple_min_invariant (result
))
4958 *id
= get_or_alloc_constant_value_id (result
);
4960 *id
= get_next_value_id ();
4963 /* Set the value ids in the valid hash tables. */
4966 set_hashtable_value_ids (void)
4968 vn_nary_op_iterator_type hin
;
4969 vn_phi_iterator_type hip
;
4970 vn_reference_iterator_type hir
;
4975 /* Now set the value ids of the things we had put in the hash
4978 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->nary
, vno
, vn_nary_op_t
, hin
)
4979 if (! vno
->predicated_values
)
4980 set_value_id_for_result (vno
->u
.result
, &vno
->value_id
);
4982 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->phis
, vp
, vn_phi_t
, hip
)
4983 set_value_id_for_result (vp
->result
, &vp
->value_id
);
4985 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->references
, vr
, vn_reference_t
,
4987 set_value_id_for_result (vr
->result
, &vr
->value_id
);
4990 /* Return the maximum value id we have ever seen. */
4993 get_max_value_id (void)
4995 return next_value_id
;
4998 /* Return the next unique value id. */
5001 get_next_value_id (void)
5003 return next_value_id
++;
5007 /* Compare two expressions E1 and E2 and return true if they are equal. */
5010 expressions_equal_p (tree e1
, tree e2
)
5012 /* The obvious case. */
5016 /* If either one is VN_TOP consider them equal. */
5017 if (e1
== VN_TOP
|| e2
== VN_TOP
)
5020 /* If only one of them is null, they cannot be equal. */
5024 /* Now perform the actual comparison. */
5025 if (TREE_CODE (e1
) == TREE_CODE (e2
)
5026 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
5033 /* Return true if the nary operation NARY may trap. This is a copy
5034 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
5037 vn_nary_may_trap (vn_nary_op_t nary
)
5040 tree rhs2
= NULL_TREE
;
5041 bool honor_nans
= false;
5042 bool honor_snans
= false;
5043 bool fp_operation
= false;
5044 bool honor_trapv
= false;
5048 if (TREE_CODE_CLASS (nary
->opcode
) == tcc_comparison
5049 || TREE_CODE_CLASS (nary
->opcode
) == tcc_unary
5050 || TREE_CODE_CLASS (nary
->opcode
) == tcc_binary
)
5053 fp_operation
= FLOAT_TYPE_P (type
);
5056 honor_nans
= flag_trapping_math
&& !flag_finite_math_only
;
5057 honor_snans
= flag_signaling_nans
!= 0;
5059 else if (INTEGRAL_TYPE_P (type
)
5060 && TYPE_OVERFLOW_TRAPS (type
))
5063 if (nary
->length
>= 2)
5065 ret
= operation_could_trap_helper_p (nary
->opcode
, fp_operation
,
5067 honor_nans
, honor_snans
, rhs2
,
5073 for (i
= 0; i
< nary
->length
; ++i
)
5074 if (tree_could_trap_p (nary
->op
[i
]))
5080 /* Return true if the reference operation REF may trap. */
5083 vn_reference_may_trap (vn_reference_t ref
)
5085 switch (ref
->operands
[0].opcode
)
5089 /* We do not handle calls. */
5091 /* And toplevel address computations never trap. */
5096 vn_reference_op_t op
;
5098 FOR_EACH_VEC_ELT (ref
->operands
, i
, op
)
5102 case WITH_SIZE_EXPR
:
5103 case TARGET_MEM_REF
:
5104 /* Always variable. */
5107 if (op
->op1
&& TREE_CODE (op
->op1
) == SSA_NAME
)
5110 case ARRAY_RANGE_REF
:
5112 if (TREE_CODE (op
->op0
) == SSA_NAME
)
5116 /* Nothing interesting in itself, the base is separate. */
5118 /* The following are the address bases. */
5123 return tree_could_trap_p (TREE_OPERAND (op
->op0
, 0));
5131 eliminate_dom_walker::eliminate_dom_walker (cdi_direction direction
,
5132 bitmap inserted_exprs_
)
5133 : dom_walker (direction
), do_pre (inserted_exprs_
!= NULL
),
5134 el_todo (0), eliminations (0), insertions (0),
5135 inserted_exprs (inserted_exprs_
)
5137 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
5138 need_ab_cleanup
= BITMAP_ALLOC (NULL
);
5141 eliminate_dom_walker::~eliminate_dom_walker ()
5143 BITMAP_FREE (need_eh_cleanup
);
5144 BITMAP_FREE (need_ab_cleanup
);
5147 /* Return a leader for OP that is available at the current point of the
5148 eliminate domwalk. */
5151 eliminate_dom_walker::eliminate_avail (basic_block
, tree op
)
5153 tree valnum
= VN_INFO (op
)->valnum
;
5154 if (TREE_CODE (valnum
) == SSA_NAME
)
5156 if (SSA_NAME_IS_DEFAULT_DEF (valnum
))
5158 if (avail
.length () > SSA_NAME_VERSION (valnum
))
5159 return avail
[SSA_NAME_VERSION (valnum
)];
5161 else if (is_gimple_min_invariant (valnum
))
5166 /* At the current point of the eliminate domwalk make OP available. */
5169 eliminate_dom_walker::eliminate_push_avail (basic_block
, tree op
)
5171 tree valnum
= VN_INFO (op
)->valnum
;
5172 if (TREE_CODE (valnum
) == SSA_NAME
)
5174 if (avail
.length () <= SSA_NAME_VERSION (valnum
))
5175 avail
.safe_grow_cleared (SSA_NAME_VERSION (valnum
) + 1);
5177 if (avail
[SSA_NAME_VERSION (valnum
)])
5178 pushop
= avail
[SSA_NAME_VERSION (valnum
)];
5179 avail_stack
.safe_push (pushop
);
5180 avail
[SSA_NAME_VERSION (valnum
)] = op
;
5184 /* Insert the expression recorded by SCCVN for VAL at *GSI. Returns
5185 the leader for the expression if insertion was successful. */
5188 eliminate_dom_walker::eliminate_insert (basic_block bb
,
5189 gimple_stmt_iterator
*gsi
, tree val
)
5191 /* We can insert a sequence with a single assignment only. */
5192 gimple_seq stmts
= VN_INFO (val
)->expr
;
5193 if (!gimple_seq_singleton_p (stmts
))
5195 gassign
*stmt
= dyn_cast
<gassign
*> (gimple_seq_first_stmt (stmts
));
5197 || (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt
))
5198 && gimple_assign_rhs_code (stmt
) != VIEW_CONVERT_EXPR
5199 && gimple_assign_rhs_code (stmt
) != BIT_FIELD_REF
5200 && (gimple_assign_rhs_code (stmt
) != BIT_AND_EXPR
5201 || TREE_CODE (gimple_assign_rhs2 (stmt
)) != INTEGER_CST
)))
5204 tree op
= gimple_assign_rhs1 (stmt
);
5205 if (gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
5206 || gimple_assign_rhs_code (stmt
) == BIT_FIELD_REF
)
5207 op
= TREE_OPERAND (op
, 0);
5208 tree leader
= TREE_CODE (op
) == SSA_NAME
? eliminate_avail (bb
, op
) : op
;
5214 if (gimple_assign_rhs_code (stmt
) == BIT_FIELD_REF
)
5215 res
= gimple_build (&stmts
, BIT_FIELD_REF
,
5216 TREE_TYPE (val
), leader
,
5217 TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1),
5218 TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2));
5219 else if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
)
5220 res
= gimple_build (&stmts
, BIT_AND_EXPR
,
5221 TREE_TYPE (val
), leader
, gimple_assign_rhs2 (stmt
));
5223 res
= gimple_build (&stmts
, gimple_assign_rhs_code (stmt
),
5224 TREE_TYPE (val
), leader
);
5225 if (TREE_CODE (res
) != SSA_NAME
5226 || SSA_NAME_IS_DEFAULT_DEF (res
)
5227 || gimple_bb (SSA_NAME_DEF_STMT (res
)))
5229 gimple_seq_discard (stmts
);
5231 /* During propagation we have to treat SSA info conservatively
5232 and thus we can end up simplifying the inserted expression
5233 at elimination time to sth not defined in stmts. */
5234 /* But then this is a redundancy we failed to detect. Which means
5235 res now has two values. That doesn't play well with how
5236 we track availability here, so give up. */
5237 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5239 if (TREE_CODE (res
) == SSA_NAME
)
5240 res
= eliminate_avail (bb
, res
);
5243 fprintf (dump_file
, "Failed to insert expression for value ");
5244 print_generic_expr (dump_file
, val
);
5245 fprintf (dump_file
, " which is really fully redundant to ");
5246 print_generic_expr (dump_file
, res
);
5247 fprintf (dump_file
, "\n");
5255 gsi_insert_seq_before (gsi
, stmts
, GSI_SAME_STMT
);
5256 VN_INFO (res
)->valnum
= val
;
5257 VN_INFO (res
)->visited
= true;
5261 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5263 fprintf (dump_file
, "Inserted ");
5264 print_gimple_stmt (dump_file
, SSA_NAME_DEF_STMT (res
), 0);
5271 eliminate_dom_walker::eliminate_stmt (basic_block b
, gimple_stmt_iterator
*gsi
)
5273 tree sprime
= NULL_TREE
;
5274 gimple
*stmt
= gsi_stmt (*gsi
);
5275 tree lhs
= gimple_get_lhs (stmt
);
5276 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
5277 && !gimple_has_volatile_ops (stmt
)
5278 /* See PR43491. Do not replace a global register variable when
5279 it is a the RHS of an assignment. Do replace local register
5280 variables since gcc does not guarantee a local variable will
5281 be allocated in register.
5282 ??? The fix isn't effective here. This should instead
5283 be ensured by not value-numbering them the same but treating
5284 them like volatiles? */
5285 && !(gimple_assign_single_p (stmt
)
5286 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == VAR_DECL
5287 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt
))
5288 && is_global_var (gimple_assign_rhs1 (stmt
)))))
5290 sprime
= eliminate_avail (b
, lhs
);
5293 /* If there is no existing usable leader but SCCVN thinks
5294 it has an expression it wants to use as replacement,
5296 tree val
= VN_INFO (lhs
)->valnum
;
5298 && TREE_CODE (val
) == SSA_NAME
5299 && VN_INFO (val
)->needs_insertion
5300 && VN_INFO (val
)->expr
!= NULL
5301 && (sprime
= eliminate_insert (b
, gsi
, val
)) != NULL_TREE
)
5302 eliminate_push_avail (b
, sprime
);
5305 /* If this now constitutes a copy duplicate points-to
5306 and range info appropriately. This is especially
5307 important for inserted code. See tree-ssa-copy.c
5308 for similar code. */
5310 && TREE_CODE (sprime
) == SSA_NAME
)
5312 basic_block sprime_b
= gimple_bb (SSA_NAME_DEF_STMT (sprime
));
5313 if (POINTER_TYPE_P (TREE_TYPE (lhs
))
5314 && SSA_NAME_PTR_INFO (lhs
)
5315 && ! SSA_NAME_PTR_INFO (sprime
))
5317 duplicate_ssa_name_ptr_info (sprime
,
5318 SSA_NAME_PTR_INFO (lhs
));
5320 mark_ptr_info_alignment_unknown
5321 (SSA_NAME_PTR_INFO (sprime
));
5323 else if (INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
5324 && SSA_NAME_RANGE_INFO (lhs
)
5325 && ! SSA_NAME_RANGE_INFO (sprime
)
5327 duplicate_ssa_name_range_info (sprime
,
5328 SSA_NAME_RANGE_TYPE (lhs
),
5329 SSA_NAME_RANGE_INFO (lhs
));
5332 /* Inhibit the use of an inserted PHI on a loop header when
5333 the address of the memory reference is a simple induction
5334 variable. In other cases the vectorizer won't do anything
5335 anyway (either it's loop invariant or a complicated
5338 && TREE_CODE (sprime
) == SSA_NAME
5340 && (flag_tree_loop_vectorize
|| flag_tree_parallelize_loops
> 1)
5341 && loop_outer (b
->loop_father
)
5342 && has_zero_uses (sprime
)
5343 && bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (sprime
))
5344 && gimple_assign_load_p (stmt
))
5346 gimple
*def_stmt
= SSA_NAME_DEF_STMT (sprime
);
5347 basic_block def_bb
= gimple_bb (def_stmt
);
5348 if (gimple_code (def_stmt
) == GIMPLE_PHI
5349 && def_bb
->loop_father
->header
== def_bb
)
5351 loop_p loop
= def_bb
->loop_father
;
5355 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
5358 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (op
));
5360 && flow_bb_inside_loop_p (loop
, def_bb
)
5361 && simple_iv (loop
, loop
, op
, &iv
, true))
5369 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5371 fprintf (dump_file
, "Not replacing ");
5372 print_gimple_expr (dump_file
, stmt
, 0);
5373 fprintf (dump_file
, " with ");
5374 print_generic_expr (dump_file
, sprime
);
5375 fprintf (dump_file
, " which would add a loop"
5376 " carried dependence to loop %d\n",
5379 /* Don't keep sprime available. */
5387 /* If we can propagate the value computed for LHS into
5388 all uses don't bother doing anything with this stmt. */
5389 if (may_propagate_copy (lhs
, sprime
))
5391 /* Mark it for removal. */
5392 to_remove
.safe_push (stmt
);
5394 /* ??? Don't count copy/constant propagations. */
5395 if (gimple_assign_single_p (stmt
)
5396 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
5397 || gimple_assign_rhs1 (stmt
) == sprime
))
5400 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5402 fprintf (dump_file
, "Replaced ");
5403 print_gimple_expr (dump_file
, stmt
, 0);
5404 fprintf (dump_file
, " with ");
5405 print_generic_expr (dump_file
, sprime
);
5406 fprintf (dump_file
, " in all uses of ");
5407 print_gimple_stmt (dump_file
, stmt
, 0);
5414 /* If this is an assignment from our leader (which
5415 happens in the case the value-number is a constant)
5416 then there is nothing to do. */
5417 if (gimple_assign_single_p (stmt
)
5418 && sprime
== gimple_assign_rhs1 (stmt
))
5421 /* Else replace its RHS. */
5422 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5424 fprintf (dump_file
, "Replaced ");
5425 print_gimple_expr (dump_file
, stmt
, 0);
5426 fprintf (dump_file
, " with ");
5427 print_generic_expr (dump_file
, sprime
);
5428 fprintf (dump_file
, " in ");
5429 print_gimple_stmt (dump_file
, stmt
, 0);
5433 bool can_make_abnormal_goto
= (is_gimple_call (stmt
)
5434 && stmt_can_make_abnormal_goto (stmt
));
5435 gimple
*orig_stmt
= stmt
;
5436 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
5437 TREE_TYPE (sprime
)))
5439 /* We preserve conversions to but not from function or method
5440 types. This asymmetry makes it necessary to re-instantiate
5441 conversions here. */
5442 if (POINTER_TYPE_P (TREE_TYPE (lhs
))
5443 && FUNC_OR_METHOD_TYPE_P (TREE_TYPE (TREE_TYPE (lhs
))))
5444 sprime
= fold_convert (TREE_TYPE (lhs
), sprime
);
5448 tree vdef
= gimple_vdef (stmt
);
5449 tree vuse
= gimple_vuse (stmt
);
5450 propagate_tree_value_into_stmt (gsi
, sprime
);
5451 stmt
= gsi_stmt (*gsi
);
5453 /* In case the VDEF on the original stmt was released, value-number
5454 it to the VUSE. This is to make vuse_ssa_val able to skip
5455 released virtual operands. */
5456 if (vdef
!= gimple_vdef (stmt
))
5458 gcc_assert (SSA_NAME_IN_FREE_LIST (vdef
));
5459 VN_INFO (vdef
)->valnum
= vuse
;
5462 /* If we removed EH side-effects from the statement, clean
5463 its EH information. */
5464 if (maybe_clean_or_replace_eh_stmt (orig_stmt
, stmt
))
5466 bitmap_set_bit (need_eh_cleanup
,
5467 gimple_bb (stmt
)->index
);
5468 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5469 fprintf (dump_file
, " Removed EH side-effects.\n");
5472 /* Likewise for AB side-effects. */
5473 if (can_make_abnormal_goto
5474 && !stmt_can_make_abnormal_goto (stmt
))
5476 bitmap_set_bit (need_ab_cleanup
,
5477 gimple_bb (stmt
)->index
);
5478 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5479 fprintf (dump_file
, " Removed AB side-effects.\n");
5486 /* If the statement is a scalar store, see if the expression
5487 has the same value number as its rhs. If so, the store is
5489 if (gimple_assign_single_p (stmt
)
5490 && !gimple_has_volatile_ops (stmt
)
5491 && !is_gimple_reg (gimple_assign_lhs (stmt
))
5492 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
5493 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
5496 tree rhs
= gimple_assign_rhs1 (stmt
);
5497 vn_reference_t vnresult
;
5498 val
= vn_reference_lookup (lhs
, gimple_vuse (stmt
), VN_WALKREWRITE
,
5500 if (TREE_CODE (rhs
) == SSA_NAME
)
5501 rhs
= VN_INFO (rhs
)->valnum
;
5503 && operand_equal_p (val
, rhs
, 0))
5505 /* We can only remove the later store if the former aliases
5506 at least all accesses the later one does or if the store
5507 was to readonly memory storing the same value. */
5508 alias_set_type set
= get_alias_set (lhs
);
5510 || vnresult
->set
== set
5511 || alias_set_subset_of (set
, vnresult
->set
))
5513 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5515 fprintf (dump_file
, "Deleted redundant store ");
5516 print_gimple_stmt (dump_file
, stmt
, 0);
5519 /* Queue stmt for removal. */
5520 to_remove
.safe_push (stmt
);
5526 /* If this is a control statement value numbering left edges
5527 unexecuted on force the condition in a way consistent with
5529 if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
5531 if ((EDGE_SUCC (b
, 0)->flags
& EDGE_EXECUTABLE
)
5532 ^ (EDGE_SUCC (b
, 1)->flags
& EDGE_EXECUTABLE
))
5534 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5536 fprintf (dump_file
, "Removing unexecutable edge from ");
5537 print_gimple_stmt (dump_file
, stmt
, 0);
5539 if (((EDGE_SUCC (b
, 0)->flags
& EDGE_TRUE_VALUE
) != 0)
5540 == ((EDGE_SUCC (b
, 0)->flags
& EDGE_EXECUTABLE
) != 0))
5541 gimple_cond_make_true (cond
);
5543 gimple_cond_make_false (cond
);
5545 el_todo
|= TODO_cleanup_cfg
;
5550 bool can_make_abnormal_goto
= stmt_can_make_abnormal_goto (stmt
);
5551 bool was_noreturn
= (is_gimple_call (stmt
)
5552 && gimple_call_noreturn_p (stmt
));
5553 tree vdef
= gimple_vdef (stmt
);
5554 tree vuse
= gimple_vuse (stmt
);
5556 /* If we didn't replace the whole stmt (or propagate the result
5557 into all uses), replace all uses on this stmt with their
5559 bool modified
= false;
5560 use_operand_p use_p
;
5562 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
5564 tree use
= USE_FROM_PTR (use_p
);
5565 /* ??? The call code above leaves stmt operands un-updated. */
5566 if (TREE_CODE (use
) != SSA_NAME
)
5569 if (SSA_NAME_IS_DEFAULT_DEF (use
))
5570 /* ??? For default defs BB shouldn't matter, but we have to
5571 solve the inconsistency between rpo eliminate and
5572 dom eliminate avail valueization first. */
5573 sprime
= eliminate_avail (b
, use
);
5575 /* Look for sth available at the definition block of the argument.
5576 This avoids inconsistencies between availability there which
5577 decides if the stmt can be removed and availability at the
5578 use site. The SSA property ensures that things available
5579 at the definition are also available at uses. */
5580 sprime
= eliminate_avail (gimple_bb (SSA_NAME_DEF_STMT (use
)), use
);
5581 if (sprime
&& sprime
!= use
5582 && may_propagate_copy (use
, sprime
)
5583 /* We substitute into debug stmts to avoid excessive
5584 debug temporaries created by removed stmts, but we need
5585 to avoid doing so for inserted sprimes as we never want
5586 to create debug temporaries for them. */
5588 || TREE_CODE (sprime
) != SSA_NAME
5589 || !is_gimple_debug (stmt
)
5590 || !bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (sprime
))))
5592 propagate_value (use_p
, sprime
);
5597 /* Fold the stmt if modified, this canonicalizes MEM_REFs we propagated
5598 into which is a requirement for the IPA devirt machinery. */
5599 gimple
*old_stmt
= stmt
;
5602 /* If a formerly non-invariant ADDR_EXPR is turned into an
5603 invariant one it was on a separate stmt. */
5604 if (gimple_assign_single_p (stmt
)
5605 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ADDR_EXPR
)
5606 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt
));
5607 gimple_stmt_iterator prev
= *gsi
;
5609 if (fold_stmt (gsi
))
5611 /* fold_stmt may have created new stmts inbetween
5612 the previous stmt and the folded stmt. Mark
5613 all defs created there as varying to not confuse
5614 the SCCVN machinery as we're using that even during
5616 if (gsi_end_p (prev
))
5617 prev
= gsi_start_bb (b
);
5620 if (gsi_stmt (prev
) != gsi_stmt (*gsi
))
5625 FOR_EACH_SSA_TREE_OPERAND (def
, gsi_stmt (prev
),
5626 dit
, SSA_OP_ALL_DEFS
)
5627 /* As existing DEFs may move between stmts
5628 only process new ones. */
5629 if (! has_VN_INFO (def
))
5631 VN_INFO (def
)->valnum
= def
;
5632 VN_INFO (def
)->visited
= true;
5634 if (gsi_stmt (prev
) == gsi_stmt (*gsi
))
5640 stmt
= gsi_stmt (*gsi
);
5641 /* In case we folded the stmt away schedule the NOP for removal. */
5642 if (gimple_nop_p (stmt
))
5643 to_remove
.safe_push (stmt
);
5646 /* Visit indirect calls and turn them into direct calls if
5647 possible using the devirtualization machinery. Do this before
5648 checking for required EH/abnormal/noreturn cleanup as devird
5649 may expose more of those. */
5650 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
5652 tree fn
= gimple_call_fn (call_stmt
);
5654 && flag_devirtualize
5655 && virtual_method_call_p (fn
))
5657 tree otr_type
= obj_type_ref_class (fn
);
5658 unsigned HOST_WIDE_INT otr_tok
5659 = tree_to_uhwi (OBJ_TYPE_REF_TOKEN (fn
));
5661 ipa_polymorphic_call_context
context (current_function_decl
,
5662 fn
, stmt
, &instance
);
5663 context
.get_dynamic_type (instance
, OBJ_TYPE_REF_OBJECT (fn
),
5664 otr_type
, stmt
, NULL
);
5666 vec
<cgraph_node
*> targets
5667 = possible_polymorphic_call_targets (obj_type_ref_class (fn
),
5668 otr_tok
, context
, &final
);
5670 dump_possible_polymorphic_call_targets (dump_file
,
5671 obj_type_ref_class (fn
),
5673 if (final
&& targets
.length () <= 1 && dbg_cnt (devirt
))
5676 if (targets
.length () == 1)
5677 fn
= targets
[0]->decl
;
5679 fn
= builtin_decl_implicit (BUILT_IN_UNREACHABLE
);
5680 if (dump_enabled_p ())
5682 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
5683 "converting indirect call to "
5685 lang_hooks
.decl_printable_name (fn
, 2));
5687 gimple_call_set_fndecl (call_stmt
, fn
);
5688 /* If changing the call to __builtin_unreachable
5689 or similar noreturn function, adjust gimple_call_fntype
5691 if (gimple_call_noreturn_p (call_stmt
)
5692 && VOID_TYPE_P (TREE_TYPE (TREE_TYPE (fn
)))
5693 && TYPE_ARG_TYPES (TREE_TYPE (fn
))
5694 && (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fn
)))
5696 gimple_call_set_fntype (call_stmt
, TREE_TYPE (fn
));
5697 maybe_remove_unused_call_args (cfun
, call_stmt
);
5705 /* When changing a call into a noreturn call, cfg cleanup
5706 is needed to fix up the noreturn call. */
5708 && is_gimple_call (stmt
) && gimple_call_noreturn_p (stmt
))
5709 to_fixup
.safe_push (stmt
);
5710 /* When changing a condition or switch into one we know what
5711 edge will be executed, schedule a cfg cleanup. */
5712 if ((gimple_code (stmt
) == GIMPLE_COND
5713 && (gimple_cond_true_p (as_a
<gcond
*> (stmt
))
5714 || gimple_cond_false_p (as_a
<gcond
*> (stmt
))))
5715 || (gimple_code (stmt
) == GIMPLE_SWITCH
5716 && TREE_CODE (gimple_switch_index
5717 (as_a
<gswitch
*> (stmt
))) == INTEGER_CST
))
5718 el_todo
|= TODO_cleanup_cfg
;
5719 /* If we removed EH side-effects from the statement, clean
5720 its EH information. */
5721 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
5723 bitmap_set_bit (need_eh_cleanup
,
5724 gimple_bb (stmt
)->index
);
5725 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5726 fprintf (dump_file
, " Removed EH side-effects.\n");
5728 /* Likewise for AB side-effects. */
5729 if (can_make_abnormal_goto
5730 && !stmt_can_make_abnormal_goto (stmt
))
5732 bitmap_set_bit (need_ab_cleanup
,
5733 gimple_bb (stmt
)->index
);
5734 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5735 fprintf (dump_file
, " Removed AB side-effects.\n");
5738 /* In case the VDEF on the original stmt was released, value-number
5739 it to the VUSE. This is to make vuse_ssa_val able to skip
5740 released virtual operands. */
5741 if (vdef
&& SSA_NAME_IN_FREE_LIST (vdef
))
5742 VN_INFO (vdef
)->valnum
= vuse
;
5745 /* Make new values available - for fully redundant LHS we
5746 continue with the next stmt above and skip this. */
5748 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_DEF
)
5749 eliminate_push_avail (b
, DEF_FROM_PTR (defp
));
5752 /* Perform elimination for the basic-block B during the domwalk. */
5755 eliminate_dom_walker::before_dom_children (basic_block b
)
5758 avail_stack
.safe_push (NULL_TREE
);
5760 /* Skip unreachable blocks marked unreachable during the SCCVN domwalk. */
5761 if (!(b
->flags
& BB_EXECUTABLE
))
5766 for (gphi_iterator gsi
= gsi_start_phis (b
); !gsi_end_p (gsi
);)
5768 gphi
*phi
= gsi
.phi ();
5769 tree res
= PHI_RESULT (phi
);
5771 if (virtual_operand_p (res
))
5777 tree sprime
= eliminate_avail (b
, res
);
5781 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5783 fprintf (dump_file
, "Replaced redundant PHI node defining ");
5784 print_generic_expr (dump_file
, res
);
5785 fprintf (dump_file
, " with ");
5786 print_generic_expr (dump_file
, sprime
);
5787 fprintf (dump_file
, "\n");
5790 /* If we inserted this PHI node ourself, it's not an elimination. */
5791 if (! inserted_exprs
5792 || ! bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (res
)))
5795 /* If we will propagate into all uses don't bother to do
5797 if (may_propagate_copy (res
, sprime
))
5799 /* Mark the PHI for removal. */
5800 to_remove
.safe_push (phi
);
5805 remove_phi_node (&gsi
, false);
5807 if (!useless_type_conversion_p (TREE_TYPE (res
), TREE_TYPE (sprime
)))
5808 sprime
= fold_convert (TREE_TYPE (res
), sprime
);
5809 gimple
*stmt
= gimple_build_assign (res
, sprime
);
5810 gimple_stmt_iterator gsi2
= gsi_after_labels (b
);
5811 gsi_insert_before (&gsi2
, stmt
, GSI_NEW_STMT
);
5815 eliminate_push_avail (b
, res
);
5819 for (gimple_stmt_iterator gsi
= gsi_start_bb (b
);
5822 eliminate_stmt (b
, &gsi
);
5824 /* Replace destination PHI arguments. */
5827 FOR_EACH_EDGE (e
, ei
, b
->succs
)
5828 if (e
->flags
& EDGE_EXECUTABLE
)
5829 for (gphi_iterator gsi
= gsi_start_phis (e
->dest
);
5833 gphi
*phi
= gsi
.phi ();
5834 use_operand_p use_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
5835 tree arg
= USE_FROM_PTR (use_p
);
5836 if (TREE_CODE (arg
) != SSA_NAME
5837 || virtual_operand_p (arg
))
5839 tree sprime
= eliminate_avail (b
, arg
);
5840 if (sprime
&& may_propagate_copy (arg
, sprime
))
5841 propagate_value (use_p
, sprime
);
5844 vn_context_bb
= NULL
;
5849 /* Make no longer available leaders no longer available. */
5852 eliminate_dom_walker::after_dom_children (basic_block
)
5855 while ((entry
= avail_stack
.pop ()) != NULL_TREE
)
5857 tree valnum
= VN_INFO (entry
)->valnum
;
5858 tree old
= avail
[SSA_NAME_VERSION (valnum
)];
5860 avail
[SSA_NAME_VERSION (valnum
)] = NULL_TREE
;
5862 avail
[SSA_NAME_VERSION (valnum
)] = entry
;
5866 /* Remove queued stmts and perform delayed cleanups. */
5869 eliminate_dom_walker::eliminate_cleanup (bool region_p
)
5871 statistics_counter_event (cfun
, "Eliminated", eliminations
);
5872 statistics_counter_event (cfun
, "Insertions", insertions
);
5874 /* We cannot remove stmts during BB walk, especially not release SSA
5875 names there as this confuses the VN machinery. The stmts ending
5876 up in to_remove are either stores or simple copies.
5877 Remove stmts in reverse order to make debug stmt creation possible. */
5878 while (!to_remove
.is_empty ())
5880 bool do_release_defs
= true;
5881 gimple
*stmt
= to_remove
.pop ();
5883 /* When we are value-numbering a region we do not require exit PHIs to
5884 be present so we have to make sure to deal with uses outside of the
5885 region of stmts that we thought are eliminated.
5886 ??? Note we may be confused by uses in dead regions we didn't run
5887 elimination on. Rather than checking individual uses we accept
5888 dead copies to be generated here (gcc.c-torture/execute/20060905-1.c
5889 contains such example). */
5892 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
5894 tree lhs
= gimple_phi_result (phi
);
5895 if (!has_zero_uses (lhs
))
5897 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5898 fprintf (dump_file
, "Keeping eliminated stmt live "
5899 "as copy because of out-of-region uses\n");
5900 tree sprime
= eliminate_avail (gimple_bb (stmt
), lhs
);
5901 gimple
*copy
= gimple_build_assign (lhs
, sprime
);
5902 gimple_stmt_iterator gsi
5903 = gsi_after_labels (gimple_bb (stmt
));
5904 gsi_insert_before (&gsi
, copy
, GSI_SAME_STMT
);
5905 do_release_defs
= false;
5908 else if (tree lhs
= gimple_get_lhs (stmt
))
5909 if (TREE_CODE (lhs
) == SSA_NAME
5910 && !has_zero_uses (lhs
))
5912 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5913 fprintf (dump_file
, "Keeping eliminated stmt live "
5914 "as copy because of out-of-region uses\n");
5915 tree sprime
= eliminate_avail (gimple_bb (stmt
), lhs
);
5916 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
5917 if (is_gimple_assign (stmt
))
5919 gimple_assign_set_rhs_from_tree (&gsi
, sprime
);
5920 stmt
= gsi_stmt (gsi
);
5922 if (maybe_clean_or_replace_eh_stmt (stmt
, stmt
))
5923 bitmap_set_bit (need_eh_cleanup
, gimple_bb (stmt
)->index
);
5928 gimple
*copy
= gimple_build_assign (lhs
, sprime
);
5929 gsi_insert_before (&gsi
, copy
, GSI_SAME_STMT
);
5930 do_release_defs
= false;
5935 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5937 fprintf (dump_file
, "Removing dead stmt ");
5938 print_gimple_stmt (dump_file
, stmt
, 0, TDF_NONE
);
5941 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
5942 if (gimple_code (stmt
) == GIMPLE_PHI
)
5943 remove_phi_node (&gsi
, do_release_defs
);
5946 basic_block bb
= gimple_bb (stmt
);
5947 unlink_stmt_vdef (stmt
);
5948 if (gsi_remove (&gsi
, true))
5949 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
5950 if (is_gimple_call (stmt
) && stmt_can_make_abnormal_goto (stmt
))
5951 bitmap_set_bit (need_ab_cleanup
, bb
->index
);
5952 if (do_release_defs
)
5953 release_defs (stmt
);
5956 /* Removing a stmt may expose a forwarder block. */
5957 el_todo
|= TODO_cleanup_cfg
;
5960 /* Fixup stmts that became noreturn calls. This may require splitting
5961 blocks and thus isn't possible during the dominator walk. Do this
5962 in reverse order so we don't inadvertedly remove a stmt we want to
5963 fixup by visiting a dominating now noreturn call first. */
5964 while (!to_fixup
.is_empty ())
5966 gimple
*stmt
= to_fixup
.pop ();
5968 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5970 fprintf (dump_file
, "Fixing up noreturn call ");
5971 print_gimple_stmt (dump_file
, stmt
, 0);
5974 if (fixup_noreturn_call (stmt
))
5975 el_todo
|= TODO_cleanup_cfg
;
5978 bool do_eh_cleanup
= !bitmap_empty_p (need_eh_cleanup
);
5979 bool do_ab_cleanup
= !bitmap_empty_p (need_ab_cleanup
);
5982 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
5985 gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup
);
5987 if (do_eh_cleanup
|| do_ab_cleanup
)
5988 el_todo
|= TODO_cleanup_cfg
;
5993 /* Eliminate fully redundant computations. */
5996 eliminate_with_rpo_vn (bitmap inserted_exprs
)
5998 eliminate_dom_walker
walker (CDI_DOMINATORS
, inserted_exprs
);
6000 walker
.walk (cfun
->cfg
->x_entry_block_ptr
);
6001 return walker
.eliminate_cleanup ();
6005 do_rpo_vn (function
*fn
, edge entry
, bitmap exit_bbs
,
6006 bool iterate
, bool eliminate
);
6009 run_rpo_vn (vn_lookup_kind kind
)
6011 default_vn_walk_kind
= kind
;
6012 do_rpo_vn (cfun
, NULL
, NULL
, true, false);
6014 /* ??? Prune requirement of these. */
6015 constant_to_value_id
= new hash_table
<vn_constant_hasher
> (23);
6016 constant_value_ids
= BITMAP_ALLOC (NULL
);
6018 /* Initialize the value ids and prune out remaining VN_TOPs
6022 FOR_EACH_SSA_NAME (i
, name
, cfun
)
6024 vn_ssa_aux_t info
= VN_INFO (name
);
6026 || info
->valnum
== VN_TOP
)
6027 info
->valnum
= name
;
6028 if (info
->valnum
== name
)
6029 info
->value_id
= get_next_value_id ();
6030 else if (is_gimple_min_invariant (info
->valnum
))
6031 info
->value_id
= get_or_alloc_constant_value_id (info
->valnum
);
6035 FOR_EACH_SSA_NAME (i
, name
, cfun
)
6037 vn_ssa_aux_t info
= VN_INFO (name
);
6038 if (TREE_CODE (info
->valnum
) == SSA_NAME
6039 && info
->valnum
!= name
6040 && info
->value_id
!= VN_INFO (info
->valnum
)->value_id
)
6041 info
->value_id
= VN_INFO (info
->valnum
)->value_id
;
6044 set_hashtable_value_ids ();
6046 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6048 fprintf (dump_file
, "Value numbers:\n");
6049 FOR_EACH_SSA_NAME (i
, name
, cfun
)
6051 if (VN_INFO (name
)->visited
6052 && SSA_VAL (name
) != name
)
6054 print_generic_expr (dump_file
, name
);
6055 fprintf (dump_file
, " = ");
6056 print_generic_expr (dump_file
, SSA_VAL (name
));
6057 fprintf (dump_file
, " (%04d)\n", VN_INFO (name
)->value_id
);
6063 /* Free VN associated data structures. */
6068 free_vn_table (valid_info
);
6069 XDELETE (valid_info
);
6070 obstack_free (&vn_tables_obstack
, NULL
);
6071 obstack_free (&vn_tables_insert_obstack
, NULL
);
6073 vn_ssa_aux_iterator_type it
;
6075 FOR_EACH_HASH_TABLE_ELEMENT (*vn_ssa_aux_hash
, info
, vn_ssa_aux_t
, it
)
6076 if (info
->needs_insertion
)
6077 release_ssa_name (info
->name
);
6078 obstack_free (&vn_ssa_aux_obstack
, NULL
);
6079 delete vn_ssa_aux_hash
;
6081 delete constant_to_value_id
;
6082 constant_to_value_id
= NULL
;
6083 BITMAP_FREE (constant_value_ids
);
6086 /* Hook for maybe_push_res_to_seq, lookup the expression in the VN tables. */
6089 vn_lookup_simplify_result (gimple_match_op
*res_op
)
6091 if (!res_op
->code
.is_tree_code ())
6093 tree
*ops
= res_op
->ops
;
6094 unsigned int length
= res_op
->num_ops
;
6095 if (res_op
->code
== CONSTRUCTOR
6096 /* ??? We're arriving here with SCCVNs view, decomposed CONSTRUCTOR
6097 and GIMPLEs / match-and-simplifies, CONSTRUCTOR as GENERIC tree. */
6098 && TREE_CODE (res_op
->ops
[0]) == CONSTRUCTOR
)
6100 length
= CONSTRUCTOR_NELTS (res_op
->ops
[0]);
6101 ops
= XALLOCAVEC (tree
, length
);
6102 for (unsigned i
= 0; i
< length
; ++i
)
6103 ops
[i
] = CONSTRUCTOR_ELT (res_op
->ops
[0], i
)->value
;
6105 vn_nary_op_t vnresult
= NULL
;
6106 tree res
= vn_nary_op_lookup_pieces (length
, (tree_code
) res_op
->code
,
6107 res_op
->type
, ops
, &vnresult
);
6108 /* If this is used from expression simplification make sure to
6109 return an available expression. */
6110 if (res
&& TREE_CODE (res
) == SSA_NAME
&& mprts_hook
&& rpo_avail
)
6111 res
= rpo_avail
->eliminate_avail (vn_context_bb
, res
);
6115 rpo_elim::~rpo_elim ()
6117 /* Release the avail vectors. */
6118 for (rpo_avail_t::iterator i
= m_rpo_avail
.begin ();
6119 i
!= m_rpo_avail
.end (); ++i
)
6120 (*i
).second
.release ();
6123 /* Return a leader for OPs value that is valid at BB. */
6126 rpo_elim::eliminate_avail (basic_block bb
, tree op
)
6129 tree valnum
= SSA_VAL (op
, &visited
);
6130 /* If we didn't visit OP then it must be defined outside of the
6131 region we process and also dominate it. So it is available. */
6134 if (TREE_CODE (valnum
) == SSA_NAME
)
6136 if (SSA_NAME_IS_DEFAULT_DEF (valnum
))
6138 vec
<std::pair
<int, int> > *av
= m_rpo_avail
.get (valnum
);
6139 if (!av
|| av
->is_empty ())
6141 int i
= av
->length () - 1;
6142 if ((*av
)[i
].first
== bb
->index
)
6143 /* On tramp3d 90% of the cases are here. */
6144 return ssa_name ((*av
)[i
].second
);
6147 basic_block abb
= BASIC_BLOCK_FOR_FN (cfun
, (*av
)[i
].first
);
6148 /* ??? During elimination we have to use availability at the
6149 definition site of a use we try to replace. This
6150 is required to not run into inconsistencies because
6151 of dominated_by_p_w_unex behavior and removing a definition
6152 while not replacing all uses.
6153 ??? We could try to consistently walk dominators
6154 ignoring non-executable regions. The nearest common
6155 dominator of bb and abb is where we can stop walking. We
6156 may also be able to "pre-compute" (bits of) the next immediate
6157 (non-)dominator during the RPO walk when marking edges as
6159 if (dominated_by_p_w_unex (bb
, abb
))
6161 tree leader
= ssa_name ((*av
)[i
].second
);
6162 /* Prevent eliminations that break loop-closed SSA. */
6163 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
)
6164 && ! SSA_NAME_IS_DEFAULT_DEF (leader
)
6165 && ! flow_bb_inside_loop_p (gimple_bb (SSA_NAME_DEF_STMT
6166 (leader
))->loop_father
,
6169 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6171 print_generic_expr (dump_file
, leader
);
6172 fprintf (dump_file
, " is available for ");
6173 print_generic_expr (dump_file
, valnum
);
6174 fprintf (dump_file
, "\n");
6176 /* On tramp3d 99% of the _remaining_ cases succeed at
6180 /* ??? Can we somehow skip to the immediate dominator
6181 RPO index (bb_to_rpo)? Again, maybe not worth, on
6182 tramp3d the worst number of elements in the vector is 9. */
6186 else if (valnum
!= VN_TOP
)
6187 /* valnum is is_gimple_min_invariant. */
6192 /* Make LEADER a leader for its value at BB. */
6195 rpo_elim::eliminate_push_avail (basic_block bb
, tree leader
)
6197 tree valnum
= VN_INFO (leader
)->valnum
;
6198 if (valnum
== VN_TOP
)
6200 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6202 fprintf (dump_file
, "Making available beyond BB%d ", bb
->index
);
6203 print_generic_expr (dump_file
, leader
);
6204 fprintf (dump_file
, " for value ");
6205 print_generic_expr (dump_file
, valnum
);
6206 fprintf (dump_file
, "\n");
6209 vec
<std::pair
<int, int> > &av
= m_rpo_avail
.get_or_insert (valnum
, &existed
);
6212 new (&av
) vec
<std::pair
<int, int> >;
6214 av
.reserve_exact (2);
6216 av
.safe_push (std::make_pair (bb
->index
, SSA_NAME_VERSION (leader
)));
6219 /* Valueization hook for RPO VN plus required state. */
6222 rpo_vn_valueize (tree name
)
6224 if (TREE_CODE (name
) == SSA_NAME
)
6226 vn_ssa_aux_t val
= VN_INFO (name
);
6229 tree tem
= val
->valnum
;
6230 if (tem
!= VN_TOP
&& tem
!= name
)
6232 if (TREE_CODE (tem
) != SSA_NAME
)
6234 /* For all values we only valueize to an available leader
6235 which means we can use SSA name info without restriction. */
6236 tem
= rpo_avail
->eliminate_avail (vn_context_bb
, tem
);
6245 /* Insert on PRED_E predicates derived from CODE OPS being true besides the
6246 inverted condition. */
6249 insert_related_predicates_on_edge (enum tree_code code
, tree
*ops
, edge pred_e
)
6254 /* a < b -> a {!,<}= b */
6255 vn_nary_op_insert_pieces_predicated (2, NE_EXPR
, boolean_type_node
,
6256 ops
, boolean_true_node
, 0, pred_e
);
6257 vn_nary_op_insert_pieces_predicated (2, LE_EXPR
, boolean_type_node
,
6258 ops
, boolean_true_node
, 0, pred_e
);
6259 /* a < b -> ! a {>,=} b */
6260 vn_nary_op_insert_pieces_predicated (2, GT_EXPR
, boolean_type_node
,
6261 ops
, boolean_false_node
, 0, pred_e
);
6262 vn_nary_op_insert_pieces_predicated (2, EQ_EXPR
, boolean_type_node
,
6263 ops
, boolean_false_node
, 0, pred_e
);
6266 /* a > b -> a {!,>}= b */
6267 vn_nary_op_insert_pieces_predicated (2, NE_EXPR
, boolean_type_node
,
6268 ops
, boolean_true_node
, 0, pred_e
);
6269 vn_nary_op_insert_pieces_predicated (2, GE_EXPR
, boolean_type_node
,
6270 ops
, boolean_true_node
, 0, pred_e
);
6271 /* a > b -> ! a {<,=} b */
6272 vn_nary_op_insert_pieces_predicated (2, LT_EXPR
, boolean_type_node
,
6273 ops
, boolean_false_node
, 0, pred_e
);
6274 vn_nary_op_insert_pieces_predicated (2, EQ_EXPR
, boolean_type_node
,
6275 ops
, boolean_false_node
, 0, pred_e
);
6278 /* a == b -> ! a {<,>} b */
6279 vn_nary_op_insert_pieces_predicated (2, LT_EXPR
, boolean_type_node
,
6280 ops
, boolean_false_node
, 0, pred_e
);
6281 vn_nary_op_insert_pieces_predicated (2, GT_EXPR
, boolean_type_node
,
6282 ops
, boolean_false_node
, 0, pred_e
);
6287 /* Nothing besides inverted condition. */
6293 /* Main stmt worker for RPO VN, process BB. */
6296 process_bb (rpo_elim
&avail
, basic_block bb
,
6297 bool bb_visited
, bool iterate_phis
, bool iterate
, bool eliminate
,
6298 bool do_region
, bitmap exit_bbs
, bool skip_phis
)
6306 /* If we are in loop-closed SSA preserve this state. This is
6307 relevant when called on regions from outside of FRE/PRE. */
6308 bool lc_phi_nodes
= false;
6310 && loops_state_satisfies_p (LOOP_CLOSED_SSA
))
6311 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
6312 if (e
->src
->loop_father
!= e
->dest
->loop_father
6313 && flow_loop_nested_p (e
->dest
->loop_father
,
6314 e
->src
->loop_father
))
6316 lc_phi_nodes
= true;
6320 /* When we visit a loop header substitute into loop info. */
6321 if (!iterate
&& eliminate
&& bb
->loop_father
->header
== bb
)
6323 /* Keep fields in sync with substitute_in_loop_info. */
6324 if (bb
->loop_father
->nb_iterations
)
6325 bb
->loop_father
->nb_iterations
6326 = simplify_replace_tree (bb
->loop_father
->nb_iterations
,
6327 NULL_TREE
, NULL_TREE
, vn_valueize
);
6330 /* Value-number all defs in the basic-block. */
6332 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
6335 gphi
*phi
= gsi
.phi ();
6336 tree res
= PHI_RESULT (phi
);
6337 vn_ssa_aux_t res_info
= VN_INFO (res
);
6340 gcc_assert (!res_info
->visited
);
6341 res_info
->valnum
= VN_TOP
;
6342 res_info
->visited
= true;
6345 /* When not iterating force backedge values to varying. */
6346 visit_stmt (phi
, !iterate_phis
);
6347 if (virtual_operand_p (res
))
6351 /* The interesting case is gcc.dg/tree-ssa/pr22230.c for correctness
6352 how we handle backedges and availability.
6353 And gcc.dg/tree-ssa/ssa-sccvn-2.c for optimization. */
6354 tree val
= res_info
->valnum
;
6355 if (res
!= val
&& !iterate
&& eliminate
)
6357 if (tree leader
= avail
.eliminate_avail (bb
, res
))
6360 /* Preserve loop-closed SSA form. */
6362 || is_gimple_min_invariant (leader
)))
6364 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6366 fprintf (dump_file
, "Replaced redundant PHI node "
6368 print_generic_expr (dump_file
, res
);
6369 fprintf (dump_file
, " with ");
6370 print_generic_expr (dump_file
, leader
);
6371 fprintf (dump_file
, "\n");
6373 avail
.eliminations
++;
6375 if (may_propagate_copy (res
, leader
))
6377 /* Schedule for removal. */
6378 avail
.to_remove
.safe_push (phi
);
6381 /* ??? Else generate a copy stmt. */
6385 /* Only make defs available that not already are. But make
6386 sure loop-closed SSA PHI node defs are picked up for
6390 || ! avail
.eliminate_avail (bb
, res
))
6391 avail
.eliminate_push_avail (bb
, res
);
6394 /* For empty BBs mark outgoing edges executable. For non-empty BBs
6395 we do this when processing the last stmt as we have to do this
6396 before elimination which otherwise forces GIMPLE_CONDs to
6397 if (1 != 0) style when seeing non-executable edges. */
6398 if (gsi_end_p (gsi_start_bb (bb
)))
6400 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
6402 if (!(e
->flags
& EDGE_EXECUTABLE
))
6404 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6406 "marking outgoing edge %d -> %d executable\n",
6407 e
->src
->index
, e
->dest
->index
);
6408 e
->flags
|= EDGE_EXECUTABLE
;
6409 e
->dest
->flags
|= BB_EXECUTABLE
;
6411 else if (!(e
->dest
->flags
& BB_EXECUTABLE
))
6413 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6415 "marking destination block %d reachable\n",
6417 e
->dest
->flags
|= BB_EXECUTABLE
;
6421 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
6422 !gsi_end_p (gsi
); gsi_next (&gsi
))
6428 FOR_EACH_SSA_TREE_OPERAND (op
, gsi_stmt (gsi
), i
, SSA_OP_ALL_DEFS
)
6430 vn_ssa_aux_t op_info
= VN_INFO (op
);
6431 gcc_assert (!op_info
->visited
);
6432 op_info
->valnum
= VN_TOP
;
6433 op_info
->visited
= true;
6436 /* We somehow have to deal with uses that are not defined
6437 in the processed region. Forcing unvisited uses to
6438 varying here doesn't play well with def-use following during
6439 expression simplification, so we deal with this by checking
6440 the visited flag in SSA_VAL. */
6443 visit_stmt (gsi_stmt (gsi
));
6445 gimple
*last
= gsi_stmt (gsi
);
6447 switch (gimple_code (last
))
6450 e
= find_taken_edge (bb
, vn_valueize (gimple_switch_index
6451 (as_a
<gswitch
*> (last
))));
6455 tree lhs
= vn_valueize (gimple_cond_lhs (last
));
6456 tree rhs
= vn_valueize (gimple_cond_rhs (last
));
6457 tree val
= gimple_simplify (gimple_cond_code (last
),
6458 boolean_type_node
, lhs
, rhs
,
6460 /* If the condition didn't simplfy see if we have recorded
6461 an expression from sofar taken edges. */
6462 if (! val
|| TREE_CODE (val
) != INTEGER_CST
)
6464 vn_nary_op_t vnresult
;
6468 val
= vn_nary_op_lookup_pieces (2, gimple_cond_code (last
),
6469 boolean_type_node
, ops
,
6471 /* Did we get a predicated value? */
6472 if (! val
&& vnresult
&& vnresult
->predicated_values
)
6474 val
= vn_nary_op_get_predicated_value (vnresult
, bb
);
6475 if (val
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
6477 fprintf (dump_file
, "Got predicated value ");
6478 print_generic_expr (dump_file
, val
, TDF_NONE
);
6479 fprintf (dump_file
, " for ");
6480 print_gimple_stmt (dump_file
, last
, TDF_SLIM
);
6485 e
= find_taken_edge (bb
, val
);
6488 /* If we didn't manage to compute the taken edge then
6489 push predicated expressions for the condition itself
6490 and related conditions to the hashtables. This allows
6491 simplification of redundant conditions which is
6492 important as early cleanup. */
6493 edge true_e
, false_e
;
6494 extract_true_false_edges_from_block (bb
, &true_e
, &false_e
);
6495 enum tree_code code
= gimple_cond_code (last
);
6496 enum tree_code icode
6497 = invert_tree_comparison (code
, HONOR_NANS (lhs
));
6502 && bitmap_bit_p (exit_bbs
, true_e
->dest
->index
))
6505 && bitmap_bit_p (exit_bbs
, false_e
->dest
->index
))
6508 vn_nary_op_insert_pieces_predicated
6509 (2, code
, boolean_type_node
, ops
,
6510 boolean_true_node
, 0, true_e
);
6512 vn_nary_op_insert_pieces_predicated
6513 (2, code
, boolean_type_node
, ops
,
6514 boolean_false_node
, 0, false_e
);
6515 if (icode
!= ERROR_MARK
)
6518 vn_nary_op_insert_pieces_predicated
6519 (2, icode
, boolean_type_node
, ops
,
6520 boolean_false_node
, 0, true_e
);
6522 vn_nary_op_insert_pieces_predicated
6523 (2, icode
, boolean_type_node
, ops
,
6524 boolean_true_node
, 0, false_e
);
6526 /* Relax for non-integers, inverted condition handled
6528 if (INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
6531 insert_related_predicates_on_edge (code
, ops
, true_e
);
6533 insert_related_predicates_on_edge (icode
, ops
, false_e
);
6539 e
= find_taken_edge (bb
, vn_valueize (gimple_goto_dest (last
)));
6546 todo
= TODO_cleanup_cfg
;
6547 if (!(e
->flags
& EDGE_EXECUTABLE
))
6549 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6551 "marking known outgoing %sedge %d -> %d executable\n",
6552 e
->flags
& EDGE_DFS_BACK
? "back-" : "",
6553 e
->src
->index
, e
->dest
->index
);
6554 e
->flags
|= EDGE_EXECUTABLE
;
6555 e
->dest
->flags
|= BB_EXECUTABLE
;
6557 else if (!(e
->dest
->flags
& BB_EXECUTABLE
))
6559 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6561 "marking destination block %d reachable\n",
6563 e
->dest
->flags
|= BB_EXECUTABLE
;
6566 else if (gsi_one_before_end_p (gsi
))
6568 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
6570 if (!(e
->flags
& EDGE_EXECUTABLE
))
6572 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6574 "marking outgoing edge %d -> %d executable\n",
6575 e
->src
->index
, e
->dest
->index
);
6576 e
->flags
|= EDGE_EXECUTABLE
;
6577 e
->dest
->flags
|= BB_EXECUTABLE
;
6579 else if (!(e
->dest
->flags
& BB_EXECUTABLE
))
6581 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6583 "marking destination block %d reachable\n",
6585 e
->dest
->flags
|= BB_EXECUTABLE
;
6590 /* Eliminate. That also pushes to avail. */
6591 if (eliminate
&& ! iterate
)
6592 avail
.eliminate_stmt (bb
, &gsi
);
6594 /* If not eliminating, make all not already available defs
6596 FOR_EACH_SSA_TREE_OPERAND (op
, gsi_stmt (gsi
), i
, SSA_OP_DEF
)
6597 if (! avail
.eliminate_avail (bb
, op
))
6598 avail
.eliminate_push_avail (bb
, op
);
6601 /* Eliminate in destination PHI arguments. Always substitute in dest
6602 PHIs, even for non-executable edges. This handles region
6604 if (!iterate
&& eliminate
)
6605 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
6606 for (gphi_iterator gsi
= gsi_start_phis (e
->dest
);
6607 !gsi_end_p (gsi
); gsi_next (&gsi
))
6609 gphi
*phi
= gsi
.phi ();
6610 use_operand_p use_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
6611 tree arg
= USE_FROM_PTR (use_p
);
6612 if (TREE_CODE (arg
) != SSA_NAME
6613 || virtual_operand_p (arg
))
6616 if (SSA_NAME_IS_DEFAULT_DEF (arg
))
6618 sprime
= SSA_VAL (arg
);
6619 gcc_assert (TREE_CODE (sprime
) != SSA_NAME
6620 || SSA_NAME_IS_DEFAULT_DEF (sprime
));
6623 /* Look for sth available at the definition block of the argument.
6624 This avoids inconsistencies between availability there which
6625 decides if the stmt can be removed and availability at the
6626 use site. The SSA property ensures that things available
6627 at the definition are also available at uses. */
6628 sprime
= avail
.eliminate_avail (gimple_bb (SSA_NAME_DEF_STMT (arg
)),
6632 && may_propagate_copy (arg
, sprime
))
6633 propagate_value (use_p
, sprime
);
6636 vn_context_bb
= NULL
;
6640 /* Unwind state per basic-block. */
6644 /* Times this block has been visited. */
6646 /* Whether to handle this as iteration point or whether to treat
6647 incoming backedge PHI values as varying. */
6649 /* Maximum RPO index this block is reachable from. */
6653 vn_reference_t ref_top
;
6655 vn_nary_op_t nary_top
;
6658 /* Unwind the RPO VN state for iteration. */
6661 do_unwind (unwind_state
*to
, int rpo_idx
, rpo_elim
&avail
, int *bb_to_rpo
)
6663 gcc_assert (to
->iterate
);
6664 for (; last_inserted_nary
!= to
->nary_top
;
6665 last_inserted_nary
= last_inserted_nary
->next
)
6668 slot
= valid_info
->nary
->find_slot_with_hash
6669 (last_inserted_nary
, last_inserted_nary
->hashcode
, NO_INSERT
);
6670 /* Predication causes the need to restore previous state. */
6671 if ((*slot
)->unwind_to
)
6672 *slot
= (*slot
)->unwind_to
;
6674 valid_info
->nary
->clear_slot (slot
);
6676 for (; last_inserted_phi
!= to
->phi_top
;
6677 last_inserted_phi
= last_inserted_phi
->next
)
6680 slot
= valid_info
->phis
->find_slot_with_hash
6681 (last_inserted_phi
, last_inserted_phi
->hashcode
, NO_INSERT
);
6682 valid_info
->phis
->clear_slot (slot
);
6684 for (; last_inserted_ref
!= to
->ref_top
;
6685 last_inserted_ref
= last_inserted_ref
->next
)
6687 vn_reference_t
*slot
;
6688 slot
= valid_info
->references
->find_slot_with_hash
6689 (last_inserted_ref
, last_inserted_ref
->hashcode
, NO_INSERT
);
6690 (*slot
)->operands
.release ();
6691 valid_info
->references
->clear_slot (slot
);
6693 obstack_free (&vn_tables_obstack
, to
->ob_top
);
6695 /* Prune [rpo_idx, ] from avail. */
6696 /* ??? This is O(number-of-values-in-region) which is
6697 O(region-size) rather than O(iteration-piece). */
6698 for (rpo_elim::rpo_avail_t::iterator i
6699 = avail
.m_rpo_avail
.begin ();
6700 i
!= avail
.m_rpo_avail
.end (); ++i
)
6702 while (! (*i
).second
.is_empty ())
6704 if (bb_to_rpo
[(*i
).second
.last ().first
] < rpo_idx
)
6711 /* Do VN on a SEME region specified by ENTRY and EXIT_BBS in FN.
6712 If ITERATE is true then treat backedges optimistically as not
6713 executed and iterate. If ELIMINATE is true then perform
6714 elimination, otherwise leave that to the caller. */
6717 do_rpo_vn (function
*fn
, edge entry
, bitmap exit_bbs
,
6718 bool iterate
, bool eliminate
)
6722 /* We currently do not support region-based iteration when
6723 elimination is requested. */
6724 gcc_assert (!entry
|| !iterate
|| !eliminate
);
6725 /* When iterating we need loop info up-to-date. */
6726 gcc_assert (!iterate
|| !loops_state_satisfies_p (LOOPS_NEED_FIXUP
));
6728 bool do_region
= entry
!= NULL
;
6731 entry
= single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (fn
));
6732 exit_bbs
= BITMAP_ALLOC (NULL
);
6733 bitmap_set_bit (exit_bbs
, EXIT_BLOCK
);
6736 /* Clear EDGE_DFS_BACK on "all" entry edges, RPO order compute will
6737 re-mark those that are contained in the region. */
6740 FOR_EACH_EDGE (e
, ei
, entry
->dest
->preds
)
6741 e
->flags
&= ~EDGE_DFS_BACK
;
6743 int *rpo
= XNEWVEC (int, n_basic_blocks_for_fn (fn
) - NUM_FIXED_BLOCKS
);
6744 int n
= rev_post_order_and_mark_dfs_back_seme
6745 (fn
, entry
, exit_bbs
, !loops_state_satisfies_p (LOOPS_NEED_FIXUP
), rpo
);
6746 /* rev_post_order_and_mark_dfs_back_seme fills RPO in reverse order. */
6747 for (int i
= 0; i
< n
/ 2; ++i
)
6748 std::swap (rpo
[i
], rpo
[n
-i
-1]);
6751 BITMAP_FREE (exit_bbs
);
6753 /* If there are any non-DFS_BACK edges into entry->dest skip
6754 processing PHI nodes for that block. This supports
6755 value-numbering loop bodies w/o the actual loop. */
6756 FOR_EACH_EDGE (e
, ei
, entry
->dest
->preds
)
6758 && !(e
->flags
& EDGE_DFS_BACK
))
6760 bool skip_entry_phis
= e
!= NULL
;
6761 if (skip_entry_phis
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
6762 fprintf (dump_file
, "Region does not contain all edges into "
6763 "the entry block, skipping its PHIs.\n");
6765 int *bb_to_rpo
= XNEWVEC (int, last_basic_block_for_fn (fn
));
6766 for (int i
= 0; i
< n
; ++i
)
6767 bb_to_rpo
[rpo
[i
]] = i
;
6769 unwind_state
*rpo_state
= XNEWVEC (unwind_state
, n
);
6771 rpo_elim
avail (entry
->dest
);
6774 /* Verify we have no extra entries into the region. */
6775 if (flag_checking
&& do_region
)
6777 auto_bb_flag
bb_in_region (fn
);
6778 for (int i
= 0; i
< n
; ++i
)
6780 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
6781 bb
->flags
|= bb_in_region
;
6783 /* We can't merge the first two loops because we cannot rely
6784 on EDGE_DFS_BACK for edges not within the region. But if
6785 we decide to always have the bb_in_region flag we can
6786 do the checking during the RPO walk itself (but then it's
6787 also easy to handle MEME conservatively). */
6788 for (int i
= 0; i
< n
; ++i
)
6790 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
6793 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
6794 gcc_assert (e
== entry
6795 || (skip_entry_phis
&& bb
== entry
->dest
)
6796 || (e
->src
->flags
& bb_in_region
));
6798 for (int i
= 0; i
< n
; ++i
)
6800 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
6801 bb
->flags
&= ~bb_in_region
;
6805 /* Create the VN state. For the initial size of the various hashtables
6806 use a heuristic based on region size and number of SSA names. */
6807 unsigned region_size
= (((unsigned HOST_WIDE_INT
)n
* num_ssa_names
)
6808 / (n_basic_blocks_for_fn (fn
) - NUM_FIXED_BLOCKS
));
6809 VN_TOP
= create_tmp_var_raw (void_type_node
, "vn_top");
6812 vn_ssa_aux_hash
= new hash_table
<vn_ssa_aux_hasher
> (region_size
* 2);
6813 gcc_obstack_init (&vn_ssa_aux_obstack
);
6815 gcc_obstack_init (&vn_tables_obstack
);
6816 gcc_obstack_init (&vn_tables_insert_obstack
);
6817 valid_info
= XCNEW (struct vn_tables_s
);
6818 allocate_vn_table (valid_info
, region_size
);
6819 last_inserted_ref
= NULL
;
6820 last_inserted_phi
= NULL
;
6821 last_inserted_nary
= NULL
;
6823 vn_valueize
= rpo_vn_valueize
;
6825 /* Initialize the unwind state and edge/BB executable state. */
6826 bool need_max_rpo_iterate
= false;
6827 for (int i
= 0; i
< n
; ++i
)
6829 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
6830 rpo_state
[i
].visited
= 0;
6831 rpo_state
[i
].max_rpo
= i
;
6832 bb
->flags
&= ~BB_EXECUTABLE
;
6833 bool has_backedges
= false;
6836 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
6838 if (e
->flags
& EDGE_DFS_BACK
)
6839 has_backedges
= true;
6840 e
->flags
&= ~EDGE_EXECUTABLE
;
6841 if (iterate
|| e
== entry
|| (skip_entry_phis
&& bb
== entry
->dest
))
6843 if (bb_to_rpo
[e
->src
->index
] > i
)
6845 rpo_state
[i
].max_rpo
= MAX (rpo_state
[i
].max_rpo
,
6846 bb_to_rpo
[e
->src
->index
]);
6847 need_max_rpo_iterate
= true;
6850 rpo_state
[i
].max_rpo
6851 = MAX (rpo_state
[i
].max_rpo
,
6852 rpo_state
[bb_to_rpo
[e
->src
->index
]].max_rpo
);
6854 rpo_state
[i
].iterate
= iterate
&& has_backedges
;
6856 entry
->flags
|= EDGE_EXECUTABLE
;
6857 entry
->dest
->flags
|= BB_EXECUTABLE
;
6859 /* When there are irreducible regions the simplistic max_rpo computation
6860 above for the case of backedges doesn't work and we need to iterate
6861 until there are no more changes. */
6863 while (need_max_rpo_iterate
)
6866 need_max_rpo_iterate
= false;
6867 for (int i
= 0; i
< n
; ++i
)
6869 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
6872 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
6874 if (e
== entry
|| (skip_entry_phis
&& bb
== entry
->dest
))
6876 int max_rpo
= MAX (rpo_state
[i
].max_rpo
,
6877 rpo_state
[bb_to_rpo
[e
->src
->index
]].max_rpo
);
6878 if (rpo_state
[i
].max_rpo
!= max_rpo
)
6880 rpo_state
[i
].max_rpo
= max_rpo
;
6881 need_max_rpo_iterate
= true;
6886 statistics_histogram_event (cfun
, "RPO max_rpo iterations", nit
);
6888 /* As heuristic to improve compile-time we handle only the N innermost
6889 loops and the outermost one optimistically. */
6893 unsigned max_depth
= PARAM_VALUE (PARAM_RPO_VN_MAX_LOOP_DEPTH
);
6894 FOR_EACH_LOOP (loop
, LI_ONLY_INNERMOST
)
6895 if (loop_depth (loop
) > max_depth
)
6896 for (unsigned i
= 2;
6897 i
< loop_depth (loop
) - max_depth
; ++i
)
6899 basic_block header
= superloop_at_depth (loop
, i
)->header
;
6900 bool non_latch_backedge
= false;
6903 FOR_EACH_EDGE (e
, ei
, header
->preds
)
6904 if (e
->flags
& EDGE_DFS_BACK
)
6906 /* There can be a non-latch backedge into the header
6907 which is part of an outer irreducible region. We
6908 cannot avoid iterating this block then. */
6909 if (!dominated_by_p (CDI_DOMINATORS
,
6912 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6913 fprintf (dump_file
, "non-latch backedge %d -> %d "
6914 "forces iteration of loop %d\n",
6915 e
->src
->index
, e
->dest
->index
, loop
->num
);
6916 non_latch_backedge
= true;
6919 e
->flags
|= EDGE_EXECUTABLE
;
6921 rpo_state
[bb_to_rpo
[header
->index
]].iterate
= non_latch_backedge
;
6928 /* Go and process all blocks, iterating as necessary. */
6931 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[idx
]);
6933 /* If the block has incoming backedges remember unwind state. This
6934 is required even for non-executable blocks since in irreducible
6935 regions we might reach them via the backedge and re-start iterating
6937 Note we can individually mark blocks with incoming backedges to
6938 not iterate where we then handle PHIs conservatively. We do that
6939 heuristically to reduce compile-time for degenerate cases. */
6940 if (rpo_state
[idx
].iterate
)
6942 rpo_state
[idx
].ob_top
= obstack_alloc (&vn_tables_obstack
, 0);
6943 rpo_state
[idx
].ref_top
= last_inserted_ref
;
6944 rpo_state
[idx
].phi_top
= last_inserted_phi
;
6945 rpo_state
[idx
].nary_top
= last_inserted_nary
;
6948 if (!(bb
->flags
& BB_EXECUTABLE
))
6950 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6951 fprintf (dump_file
, "Block %d: BB%d found not executable\n",
6957 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6958 fprintf (dump_file
, "Processing block %d: BB%d\n", idx
, bb
->index
);
6960 todo
|= process_bb (avail
, bb
,
6961 rpo_state
[idx
].visited
!= 0,
6962 rpo_state
[idx
].iterate
,
6963 iterate
, eliminate
, do_region
, exit_bbs
, false);
6964 rpo_state
[idx
].visited
++;
6966 /* Verify if changed values flow over executable outgoing backedges
6967 and those change destination PHI values (that's the thing we
6968 can easily verify). Reduce over all such edges to the farthest
6970 int iterate_to
= -1;
6973 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
6974 if ((e
->flags
& (EDGE_DFS_BACK
|EDGE_EXECUTABLE
))
6975 == (EDGE_DFS_BACK
|EDGE_EXECUTABLE
)
6976 && rpo_state
[bb_to_rpo
[e
->dest
->index
]].iterate
)
6978 int destidx
= bb_to_rpo
[e
->dest
->index
];
6979 if (!rpo_state
[destidx
].visited
)
6981 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6982 fprintf (dump_file
, "Unvisited destination %d\n",
6984 if (iterate_to
== -1 || destidx
< iterate_to
)
6985 iterate_to
= destidx
;
6988 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6989 fprintf (dump_file
, "Looking for changed values of backedge"
6990 " %d->%d destination PHIs\n",
6991 e
->src
->index
, e
->dest
->index
);
6992 vn_context_bb
= e
->dest
;
6994 for (gsi
= gsi_start_phis (e
->dest
);
6995 !gsi_end_p (gsi
); gsi_next (&gsi
))
6997 bool inserted
= false;
6998 /* While we'd ideally just iterate on value changes
6999 we CSE PHIs and do that even across basic-block
7000 boundaries. So even hashtable state changes can
7001 be important (which is roughly equivalent to
7002 PHI argument value changes). To not excessively
7003 iterate because of that we track whether a PHI
7004 was CSEd to with GF_PLF_1. */
7005 bool phival_changed
;
7006 if ((phival_changed
= visit_phi (gsi
.phi (),
7008 || (inserted
&& gimple_plf (gsi
.phi (), GF_PLF_1
)))
7011 && dump_file
&& (dump_flags
& TDF_DETAILS
))
7012 fprintf (dump_file
, "PHI was CSEd and hashtable "
7013 "state (changed)\n");
7014 if (iterate_to
== -1 || destidx
< iterate_to
)
7015 iterate_to
= destidx
;
7019 vn_context_bb
= NULL
;
7021 if (iterate_to
!= -1)
7023 do_unwind (&rpo_state
[iterate_to
], iterate_to
, avail
, bb_to_rpo
);
7025 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7026 fprintf (dump_file
, "Iterating to %d BB%d\n",
7027 iterate_to
, rpo
[iterate_to
]);
7037 /* Process all blocks greedily with a worklist that enforces RPO
7038 processing of reachable blocks. */
7039 auto_bitmap worklist
;
7040 bitmap_set_bit (worklist
, 0);
7041 while (!bitmap_empty_p (worklist
))
7043 int idx
= bitmap_first_set_bit (worklist
);
7044 bitmap_clear_bit (worklist
, idx
);
7045 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[idx
]);
7046 gcc_assert ((bb
->flags
& BB_EXECUTABLE
)
7047 && !rpo_state
[idx
].visited
);
7049 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7050 fprintf (dump_file
, "Processing block %d: BB%d\n", idx
, bb
->index
);
7052 /* When we run into predecessor edges where we cannot trust its
7053 executable state mark them executable so PHI processing will
7055 ??? Do we need to force arguments flowing over that edge
7056 to be varying or will they even always be? */
7059 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
7060 if (!(e
->flags
& EDGE_EXECUTABLE
)
7061 && (bb
== entry
->dest
7062 || (!rpo_state
[bb_to_rpo
[e
->src
->index
]].visited
7063 && (rpo_state
[bb_to_rpo
[e
->src
->index
]].max_rpo
7066 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7067 fprintf (dump_file
, "Cannot trust state of predecessor "
7068 "edge %d -> %d, marking executable\n",
7069 e
->src
->index
, e
->dest
->index
);
7070 e
->flags
|= EDGE_EXECUTABLE
;
7074 todo
|= process_bb (avail
, bb
, false, false, false, eliminate
,
7075 do_region
, exit_bbs
,
7076 skip_entry_phis
&& bb
== entry
->dest
);
7077 rpo_state
[idx
].visited
++;
7079 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
7080 if ((e
->flags
& EDGE_EXECUTABLE
)
7081 && e
->dest
->index
!= EXIT_BLOCK
7082 && (!do_region
|| !bitmap_bit_p (exit_bbs
, e
->dest
->index
))
7083 && !rpo_state
[bb_to_rpo
[e
->dest
->index
]].visited
)
7084 bitmap_set_bit (worklist
, bb_to_rpo
[e
->dest
->index
]);
7088 /* If statistics or dump file active. */
7090 unsigned max_visited
= 1;
7091 for (int i
= 0; i
< n
; ++i
)
7093 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
7094 if (bb
->flags
& BB_EXECUTABLE
)
7096 statistics_histogram_event (cfun
, "RPO block visited times",
7097 rpo_state
[i
].visited
);
7098 if (rpo_state
[i
].visited
> max_visited
)
7099 max_visited
= rpo_state
[i
].visited
;
7101 unsigned nvalues
= 0, navail
= 0;
7102 for (rpo_elim::rpo_avail_t::iterator i
= avail
.m_rpo_avail
.begin ();
7103 i
!= avail
.m_rpo_avail
.end (); ++i
)
7106 navail
+= (*i
).second
.length ();
7108 statistics_counter_event (cfun
, "RPO blocks", n
);
7109 statistics_counter_event (cfun
, "RPO blocks visited", nblk
);
7110 statistics_counter_event (cfun
, "RPO blocks executable", nex
);
7111 statistics_histogram_event (cfun
, "RPO iterations", 10*nblk
/ nex
);
7112 statistics_histogram_event (cfun
, "RPO num values", nvalues
);
7113 statistics_histogram_event (cfun
, "RPO num avail", navail
);
7114 statistics_histogram_event (cfun
, "RPO num lattice",
7115 vn_ssa_aux_hash
->elements ());
7116 if (dump_file
&& (dump_flags
& (TDF_DETAILS
|TDF_STATS
)))
7118 fprintf (dump_file
, "RPO iteration over %d blocks visited %" PRIu64
7119 " blocks in total discovering %d executable blocks iterating "
7120 "%d.%d times, a block was visited max. %u times\n",
7122 (int)((10*nblk
/ nex
)/10), (int)((10*nblk
/ nex
)%10),
7124 fprintf (dump_file
, "RPO tracked %d values available at %d locations "
7125 "and %" PRIu64
" lattice elements\n",
7126 nvalues
, navail
, (uint64_t) vn_ssa_aux_hash
->elements ());
7131 /* When !iterate we already performed elimination during the RPO
7135 /* Elimination for region-based VN needs to be done within the
7137 gcc_assert (! do_region
);
7138 /* Note we can't use avail.walk here because that gets confused
7139 by the existing availability and it will be less efficient
7141 todo
|= eliminate_with_rpo_vn (NULL
);
7144 todo
|= avail
.eliminate_cleanup (do_region
);
7150 XDELETEVEC (bb_to_rpo
);
7152 XDELETEVEC (rpo_state
);
7157 /* Region-based entry for RPO VN. Performs value-numbering and elimination
7158 on the SEME region specified by ENTRY and EXIT_BBS. If ENTRY is not
7159 the only edge into the region at ENTRY->dest PHI nodes in ENTRY->dest
7160 are not considered. */
7163 do_rpo_vn (function
*fn
, edge entry
, bitmap exit_bbs
)
7165 default_vn_walk_kind
= VN_WALKREWRITE
;
7166 unsigned todo
= do_rpo_vn (fn
, entry
, exit_bbs
, false, true);
7174 const pass_data pass_data_fre
=
7176 GIMPLE_PASS
, /* type */
7178 OPTGROUP_NONE
, /* optinfo_flags */
7179 TV_TREE_FRE
, /* tv_id */
7180 ( PROP_cfg
| PROP_ssa
), /* properties_required */
7181 0, /* properties_provided */
7182 0, /* properties_destroyed */
7183 0, /* todo_flags_start */
7184 0, /* todo_flags_finish */
7187 class pass_fre
: public gimple_opt_pass
7190 pass_fre (gcc::context
*ctxt
)
7191 : gimple_opt_pass (pass_data_fre
, ctxt
), may_iterate (true)
7194 /* opt_pass methods: */
7195 opt_pass
* clone () { return new pass_fre (m_ctxt
); }
7196 void set_pass_param (unsigned int n
, bool param
)
7198 gcc_assert (n
== 0);
7199 may_iterate
= param
;
7201 virtual bool gate (function
*)
7203 return flag_tree_fre
!= 0 && (may_iterate
|| optimize
> 1);
7205 virtual unsigned int execute (function
*);
7209 }; // class pass_fre
7212 pass_fre::execute (function
*fun
)
7216 /* At -O[1g] use the cheap non-iterating mode. */
7217 bool iterate_p
= may_iterate
&& (optimize
> 1);
7218 calculate_dominance_info (CDI_DOMINATORS
);
7220 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
7222 default_vn_walk_kind
= VN_WALKREWRITE
;
7223 todo
= do_rpo_vn (fun
, NULL
, NULL
, iterate_p
, true);
7227 loop_optimizer_finalize ();
7235 make_pass_fre (gcc::context
*ctxt
)
7237 return new pass_fre (ctxt
);
7240 #undef BB_EXECUTABLE