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"
30 #include "insn-config.h"
34 #include "gimple-pretty-print.h"
36 #include "fold-const.h"
37 #include "stor-layout.h"
39 #include "tree-inline.h"
40 #include "internal-fn.h"
41 #include "gimple-fold.h"
56 #include "tree-ssa-propagate.h"
59 #include "gimple-iterator.h"
60 #include "gimple-match.h"
61 #include "stringpool.h"
63 #include "tree-pass.h"
64 #include "statistics.h"
65 #include "langhooks.h"
66 #include "ipa-utils.h"
68 #include "tree-cfgcleanup.h"
69 #include "tree-ssa-loop.h"
70 #include "tree-scalar-evolution.h"
71 #include "tree-ssa-loop-niter.h"
72 #include "tree-ssa-sccvn.h"
74 /* This algorithm is based on the SCC algorithm presented by Keith
75 Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
76 (http://citeseer.ist.psu.edu/41805.html). In
77 straight line code, it is equivalent to a regular hash based value
78 numbering that is performed in reverse postorder.
80 For code with cycles, there are two alternatives, both of which
81 require keeping the hashtables separate from the actual list of
82 value numbers for SSA names.
84 1. Iterate value numbering in an RPO walk of the blocks, removing
85 all the entries from the hashtable after each iteration (but
86 keeping the SSA name->value number mapping between iterations).
87 Iterate until it does not change.
89 2. Perform value numbering as part of an SCC walk on the SSA graph,
90 iterating only the cycles in the SSA graph until they do not change
91 (using a separate, optimistic hashtable for value numbering the SCC
94 The second is not just faster in practice (because most SSA graph
95 cycles do not involve all the variables in the graph), it also has
98 One of these nice properties is that when we pop an SCC off the
99 stack, we are guaranteed to have processed all the operands coming from
100 *outside of that SCC*, so we do not need to do anything special to
101 ensure they have value numbers.
103 Another nice property is that the SCC walk is done as part of a DFS
104 of the SSA graph, which makes it easy to perform combining and
105 simplifying operations at the same time.
107 The code below is deliberately written in a way that makes it easy
108 to separate the SCC walk from the other work it does.
110 In order to propagate constants through the code, we track which
111 expressions contain constants, and use those while folding. In
112 theory, we could also track expressions whose value numbers are
113 replaced, in case we end up folding based on expression
116 In order to value number memory, we assign value numbers to vuses.
117 This enables us to note that, for example, stores to the same
118 address of the same value from the same starting memory states are
122 1. We can iterate only the changing portions of the SCC's, but
123 I have not seen an SCC big enough for this to be a win.
124 2. If you differentiate between phi nodes for loops and phi nodes
125 for if-then-else, you can properly consider phi nodes in different
126 blocks for equivalence.
127 3. We could value number vuses in more cases, particularly, whole
131 /* There's no BB_EXECUTABLE but we can use BB_VISITED. */
132 #define BB_EXECUTABLE BB_VISITED
134 static tree
*last_vuse_ptr
;
135 static vn_lookup_kind vn_walk_kind
;
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
*);
366 /* Return whether there is value numbering information for a given SSA name. */
369 has_VN_INFO (tree name
)
371 return vn_ssa_aux_hash
->find_with_hash (name
, SSA_NAME_VERSION (name
));
378 = vn_ssa_aux_hash
->find_slot_with_hash (name
, SSA_NAME_VERSION (name
),
383 vn_ssa_aux_t newinfo
= *res
= XOBNEW (&vn_ssa_aux_obstack
, struct vn_ssa_aux
);
384 memset (newinfo
, 0, sizeof (struct vn_ssa_aux
));
385 newinfo
->name
= name
;
386 newinfo
->valnum
= VN_TOP
;
387 /* We are using the visited flag to handle uses with defs not within the
388 region being value-numbered. */
389 newinfo
->visited
= false;
391 /* Given we create the VN_INFOs on-demand now we have to do initialization
392 different than VN_TOP here. */
393 if (SSA_NAME_IS_DEFAULT_DEF (name
))
394 switch (TREE_CODE (SSA_NAME_VAR (name
)))
397 /* All undefined vars are VARYING. */
398 newinfo
->valnum
= name
;
399 newinfo
->visited
= true;
403 /* Parameters are VARYING but we can record a condition
404 if we know it is a non-NULL pointer. */
405 newinfo
->visited
= true;
406 newinfo
->valnum
= name
;
407 if (POINTER_TYPE_P (TREE_TYPE (name
))
408 && nonnull_arg_p (SSA_NAME_VAR (name
)))
412 ops
[1] = build_int_cst (TREE_TYPE (name
), 0);
414 /* Allocate from non-unwinding stack. */
415 nary
= alloc_vn_nary_op_noinit (2, &vn_tables_insert_obstack
);
416 init_vn_nary_op_from_pieces (nary
, 2, NE_EXPR
,
417 boolean_type_node
, ops
);
418 nary
->predicated_values
= 0;
419 nary
->u
.result
= boolean_true_node
;
420 vn_nary_op_insert_into (nary
, valid_info
->nary
, true);
421 gcc_assert (nary
->unwind_to
== NULL
);
422 /* Also do not link it into the undo chain. */
423 last_inserted_nary
= nary
->next
;
424 nary
->next
= (vn_nary_op_t
)(void *)-1;
425 nary
= alloc_vn_nary_op_noinit (2, &vn_tables_insert_obstack
);
426 init_vn_nary_op_from_pieces (nary
, 2, EQ_EXPR
,
427 boolean_type_node
, ops
);
428 nary
->predicated_values
= 0;
429 nary
->u
.result
= boolean_false_node
;
430 vn_nary_op_insert_into (nary
, valid_info
->nary
, true);
431 gcc_assert (nary
->unwind_to
== NULL
);
432 last_inserted_nary
= nary
->next
;
433 nary
->next
= (vn_nary_op_t
)(void *)-1;
434 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
436 fprintf (dump_file
, "Recording ");
437 print_generic_expr (dump_file
, name
, TDF_SLIM
);
438 fprintf (dump_file
, " != 0\n");
444 /* If the result is passed by invisible reference the default
445 def is initialized, otherwise it's uninitialized. Still
446 undefined is varying. */
447 newinfo
->visited
= true;
448 newinfo
->valnum
= name
;
457 /* Return the SSA value of X. */
460 SSA_VAL (tree x
, bool *visited
= NULL
)
462 vn_ssa_aux_t tem
= vn_ssa_aux_hash
->find_with_hash (x
, SSA_NAME_VERSION (x
));
464 *visited
= tem
&& tem
->visited
;
465 return tem
&& tem
->visited
? tem
->valnum
: x
;
468 /* Return the SSA value of the VUSE x, supporting released VDEFs
469 during elimination which will value-number the VDEF to the
470 associated VUSE (but not substitute in the whole lattice). */
473 vuse_ssa_val (tree x
)
481 gcc_assert (x
!= VN_TOP
);
483 while (SSA_NAME_IN_FREE_LIST (x
));
488 /* Similar to the above but used as callback for walk_non_aliases_vuses
489 and thus should stop at unvisited VUSE to not walk across region
493 vuse_valueize (tree vuse
)
498 vuse
= SSA_VAL (vuse
, &visited
);
501 gcc_assert (vuse
!= VN_TOP
);
503 while (SSA_NAME_IN_FREE_LIST (vuse
));
508 /* Return the vn_kind the expression computed by the stmt should be
512 vn_get_stmt_kind (gimple
*stmt
)
514 switch (gimple_code (stmt
))
522 enum tree_code code
= gimple_assign_rhs_code (stmt
);
523 tree rhs1
= gimple_assign_rhs1 (stmt
);
524 switch (get_gimple_rhs_class (code
))
526 case GIMPLE_UNARY_RHS
:
527 case GIMPLE_BINARY_RHS
:
528 case GIMPLE_TERNARY_RHS
:
530 case GIMPLE_SINGLE_RHS
:
531 switch (TREE_CODE_CLASS (code
))
534 /* VOP-less references can go through unary case. */
535 if ((code
== REALPART_EXPR
536 || code
== IMAGPART_EXPR
537 || code
== VIEW_CONVERT_EXPR
538 || code
== BIT_FIELD_REF
)
539 && TREE_CODE (TREE_OPERAND (rhs1
, 0)) == SSA_NAME
)
543 case tcc_declaration
:
550 if (code
== ADDR_EXPR
)
551 return (is_gimple_min_invariant (rhs1
)
552 ? VN_CONSTANT
: VN_REFERENCE
);
553 else if (code
== CONSTRUCTOR
)
566 /* Lookup a value id for CONSTANT and return it. If it does not
570 get_constant_value_id (tree constant
)
572 vn_constant_s
**slot
;
573 struct vn_constant_s vc
;
575 vc
.hashcode
= vn_hash_constant_with_type (constant
);
576 vc
.constant
= constant
;
577 slot
= constant_to_value_id
->find_slot (&vc
, NO_INSERT
);
579 return (*slot
)->value_id
;
583 /* Lookup a value id for CONSTANT, and if it does not exist, create a
584 new one and return it. If it does exist, return it. */
587 get_or_alloc_constant_value_id (tree constant
)
589 vn_constant_s
**slot
;
590 struct vn_constant_s vc
;
593 /* If the hashtable isn't initialized we're not running from PRE and thus
594 do not need value-ids. */
595 if (!constant_to_value_id
)
598 vc
.hashcode
= vn_hash_constant_with_type (constant
);
599 vc
.constant
= constant
;
600 slot
= constant_to_value_id
->find_slot (&vc
, INSERT
);
602 return (*slot
)->value_id
;
604 vcp
= XNEW (struct vn_constant_s
);
605 vcp
->hashcode
= vc
.hashcode
;
606 vcp
->constant
= constant
;
607 vcp
->value_id
= get_next_value_id ();
609 bitmap_set_bit (constant_value_ids
, vcp
->value_id
);
610 return vcp
->value_id
;
613 /* Return true if V is a value id for a constant. */
616 value_id_constant_p (unsigned int v
)
618 return bitmap_bit_p (constant_value_ids
, v
);
621 /* Compute the hash for a reference operand VRO1. */
624 vn_reference_op_compute_hash (const vn_reference_op_t vro1
, inchash::hash
&hstate
)
626 hstate
.add_int (vro1
->opcode
);
628 inchash::add_expr (vro1
->op0
, hstate
);
630 inchash::add_expr (vro1
->op1
, hstate
);
632 inchash::add_expr (vro1
->op2
, hstate
);
635 /* Compute a hash for the reference operation VR1 and return it. */
638 vn_reference_compute_hash (const vn_reference_t vr1
)
640 inchash::hash hstate
;
643 vn_reference_op_t vro
;
647 FOR_EACH_VEC_ELT (vr1
->operands
, i
, vro
)
649 if (vro
->opcode
== MEM_REF
)
651 else if (vro
->opcode
!= ADDR_EXPR
)
653 if (maybe_ne (vro
->off
, -1))
655 if (known_eq (off
, -1))
661 if (maybe_ne (off
, -1)
662 && maybe_ne (off
, 0))
663 hstate
.add_poly_int (off
);
666 && vro
->opcode
== ADDR_EXPR
)
670 tree op
= TREE_OPERAND (vro
->op0
, 0);
671 hstate
.add_int (TREE_CODE (op
));
672 inchash::add_expr (op
, hstate
);
676 vn_reference_op_compute_hash (vro
, hstate
);
679 result
= hstate
.end ();
680 /* ??? We would ICE later if we hash instead of adding that in. */
682 result
+= SSA_NAME_VERSION (vr1
->vuse
);
687 /* Return true if reference operations VR1 and VR2 are equivalent. This
688 means they have the same set of operands and vuses. */
691 vn_reference_eq (const_vn_reference_t
const vr1
, const_vn_reference_t
const vr2
)
695 /* Early out if this is not a hash collision. */
696 if (vr1
->hashcode
!= vr2
->hashcode
)
699 /* The VOP needs to be the same. */
700 if (vr1
->vuse
!= vr2
->vuse
)
703 /* If the operands are the same we are done. */
704 if (vr1
->operands
== vr2
->operands
)
707 if (!expressions_equal_p (TYPE_SIZE (vr1
->type
), TYPE_SIZE (vr2
->type
)))
710 if (INTEGRAL_TYPE_P (vr1
->type
)
711 && INTEGRAL_TYPE_P (vr2
->type
))
713 if (TYPE_PRECISION (vr1
->type
) != TYPE_PRECISION (vr2
->type
))
716 else if (INTEGRAL_TYPE_P (vr1
->type
)
717 && (TYPE_PRECISION (vr1
->type
)
718 != TREE_INT_CST_LOW (TYPE_SIZE (vr1
->type
))))
720 else if (INTEGRAL_TYPE_P (vr2
->type
)
721 && (TYPE_PRECISION (vr2
->type
)
722 != TREE_INT_CST_LOW (TYPE_SIZE (vr2
->type
))))
729 poly_int64 off1
= 0, off2
= 0;
730 vn_reference_op_t vro1
, vro2
;
731 vn_reference_op_s tem1
, tem2
;
732 bool deref1
= false, deref2
= false;
733 for (; vr1
->operands
.iterate (i
, &vro1
); i
++)
735 if (vro1
->opcode
== MEM_REF
)
737 /* Do not look through a storage order barrier. */
738 else if (vro1
->opcode
== VIEW_CONVERT_EXPR
&& vro1
->reverse
)
740 if (known_eq (vro1
->off
, -1))
744 for (; vr2
->operands
.iterate (j
, &vro2
); j
++)
746 if (vro2
->opcode
== MEM_REF
)
748 /* Do not look through a storage order barrier. */
749 else if (vro2
->opcode
== VIEW_CONVERT_EXPR
&& vro2
->reverse
)
751 if (known_eq (vro2
->off
, -1))
755 if (maybe_ne (off1
, off2
))
757 if (deref1
&& vro1
->opcode
== ADDR_EXPR
)
759 memset (&tem1
, 0, sizeof (tem1
));
760 tem1
.op0
= TREE_OPERAND (vro1
->op0
, 0);
761 tem1
.type
= TREE_TYPE (tem1
.op0
);
762 tem1
.opcode
= TREE_CODE (tem1
.op0
);
766 if (deref2
&& vro2
->opcode
== ADDR_EXPR
)
768 memset (&tem2
, 0, sizeof (tem2
));
769 tem2
.op0
= TREE_OPERAND (vro2
->op0
, 0);
770 tem2
.type
= TREE_TYPE (tem2
.op0
);
771 tem2
.opcode
= TREE_CODE (tem2
.op0
);
775 if (deref1
!= deref2
)
777 if (!vn_reference_op_eq (vro1
, vro2
))
782 while (vr1
->operands
.length () != i
783 || vr2
->operands
.length () != j
);
788 /* Copy the operations present in load/store REF into RESULT, a vector of
789 vn_reference_op_s's. */
792 copy_reference_ops_from_ref (tree ref
, vec
<vn_reference_op_s
> *result
)
794 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
796 vn_reference_op_s temp
;
800 memset (&temp
, 0, sizeof (temp
));
801 temp
.type
= TREE_TYPE (ref
);
802 temp
.opcode
= TREE_CODE (ref
);
803 temp
.op0
= TMR_INDEX (ref
);
804 temp
.op1
= TMR_STEP (ref
);
805 temp
.op2
= TMR_OFFSET (ref
);
807 temp
.clique
= MR_DEPENDENCE_CLIQUE (ref
);
808 temp
.base
= MR_DEPENDENCE_BASE (ref
);
809 result
->quick_push (temp
);
811 memset (&temp
, 0, sizeof (temp
));
812 temp
.type
= NULL_TREE
;
813 temp
.opcode
= ERROR_MARK
;
814 temp
.op0
= TMR_INDEX2 (ref
);
816 result
->quick_push (temp
);
818 memset (&temp
, 0, sizeof (temp
));
819 temp
.type
= NULL_TREE
;
820 temp
.opcode
= TREE_CODE (TMR_BASE (ref
));
821 temp
.op0
= TMR_BASE (ref
);
823 result
->quick_push (temp
);
827 /* For non-calls, store the information that makes up the address. */
831 vn_reference_op_s temp
;
833 memset (&temp
, 0, sizeof (temp
));
834 temp
.type
= TREE_TYPE (ref
);
835 temp
.opcode
= TREE_CODE (ref
);
841 temp
.op0
= TREE_OPERAND (ref
, 1);
844 temp
.op0
= TREE_OPERAND (ref
, 1);
848 /* The base address gets its own vn_reference_op_s structure. */
849 temp
.op0
= TREE_OPERAND (ref
, 1);
850 if (!mem_ref_offset (ref
).to_shwi (&temp
.off
))
852 temp
.clique
= MR_DEPENDENCE_CLIQUE (ref
);
853 temp
.base
= MR_DEPENDENCE_BASE (ref
);
854 temp
.reverse
= REF_REVERSE_STORAGE_ORDER (ref
);
857 /* Record bits, position and storage order. */
858 temp
.op0
= TREE_OPERAND (ref
, 1);
859 temp
.op1
= TREE_OPERAND (ref
, 2);
860 if (!multiple_p (bit_field_offset (ref
), BITS_PER_UNIT
, &temp
.off
))
862 temp
.reverse
= REF_REVERSE_STORAGE_ORDER (ref
);
865 /* The field decl is enough to unambiguously specify the field,
866 a matching type is not necessary and a mismatching type
867 is always a spurious difference. */
868 temp
.type
= NULL_TREE
;
869 temp
.op0
= TREE_OPERAND (ref
, 1);
870 temp
.op1
= TREE_OPERAND (ref
, 2);
872 tree this_offset
= component_ref_field_offset (ref
);
874 && poly_int_tree_p (this_offset
))
876 tree bit_offset
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
877 if (TREE_INT_CST_LOW (bit_offset
) % BITS_PER_UNIT
== 0)
880 = (wi::to_poly_offset (this_offset
)
881 + (wi::to_offset (bit_offset
) >> LOG2_BITS_PER_UNIT
));
882 /* Probibit value-numbering zero offset components
883 of addresses the same before the pass folding
884 __builtin_object_size had a chance to run
885 (checking cfun->after_inlining does the
887 if (TREE_CODE (orig
) != ADDR_EXPR
889 || cfun
->after_inlining
)
890 off
.to_shwi (&temp
.off
);
895 case ARRAY_RANGE_REF
:
898 tree eltype
= TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref
, 0)));
899 /* Record index as operand. */
900 temp
.op0
= TREE_OPERAND (ref
, 1);
901 /* Always record lower bounds and element size. */
902 temp
.op1
= array_ref_low_bound (ref
);
903 /* But record element size in units of the type alignment. */
904 temp
.op2
= TREE_OPERAND (ref
, 3);
905 temp
.align
= eltype
->type_common
.align
;
907 temp
.op2
= size_binop (EXACT_DIV_EXPR
, TYPE_SIZE_UNIT (eltype
),
908 size_int (TYPE_ALIGN_UNIT (eltype
)));
909 if (poly_int_tree_p (temp
.op0
)
910 && poly_int_tree_p (temp
.op1
)
911 && TREE_CODE (temp
.op2
) == INTEGER_CST
)
913 poly_offset_int off
= ((wi::to_poly_offset (temp
.op0
)
914 - wi::to_poly_offset (temp
.op1
))
915 * wi::to_offset (temp
.op2
)
916 * vn_ref_op_align_unit (&temp
));
917 off
.to_shwi (&temp
.off
);
922 if (DECL_HARD_REGISTER (ref
))
931 /* Canonicalize decls to MEM[&decl] which is what we end up with
932 when valueizing MEM[ptr] with ptr = &decl. */
933 temp
.opcode
= MEM_REF
;
934 temp
.op0
= build_int_cst (build_pointer_type (TREE_TYPE (ref
)), 0);
936 result
->safe_push (temp
);
937 temp
.opcode
= ADDR_EXPR
;
938 temp
.op0
= build1 (ADDR_EXPR
, TREE_TYPE (temp
.op0
), ref
);
939 temp
.type
= TREE_TYPE (temp
.op0
);
953 if (is_gimple_min_invariant (ref
))
959 /* These are only interesting for their operands, their
960 existence, and their type. They will never be the last
961 ref in the chain of references (IE they require an
962 operand), so we don't have to put anything
963 for op* as it will be handled by the iteration */
967 case VIEW_CONVERT_EXPR
:
969 temp
.reverse
= storage_order_barrier_p (ref
);
972 /* This is only interesting for its constant offset. */
973 temp
.off
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref
)));
978 result
->safe_push (temp
);
980 if (REFERENCE_CLASS_P (ref
)
981 || TREE_CODE (ref
) == MODIFY_EXPR
982 || TREE_CODE (ref
) == WITH_SIZE_EXPR
983 || (TREE_CODE (ref
) == ADDR_EXPR
984 && !is_gimple_min_invariant (ref
)))
985 ref
= TREE_OPERAND (ref
, 0);
991 /* Build a alias-oracle reference abstraction in *REF from the vn_reference
992 operands in *OPS, the reference alias set SET and the reference type TYPE.
993 Return true if something useful was produced. */
996 ao_ref_init_from_vn_reference (ao_ref
*ref
,
997 alias_set_type set
, tree type
,
998 vec
<vn_reference_op_s
> ops
)
1000 vn_reference_op_t op
;
1002 tree base
= NULL_TREE
;
1003 tree
*op0_p
= &base
;
1004 poly_offset_int offset
= 0;
1005 poly_offset_int max_size
;
1006 poly_offset_int size
= -1;
1007 tree size_tree
= NULL_TREE
;
1008 alias_set_type base_alias_set
= -1;
1010 /* First get the final access size from just the outermost expression. */
1012 if (op
->opcode
== COMPONENT_REF
)
1013 size_tree
= DECL_SIZE (op
->op0
);
1014 else if (op
->opcode
== BIT_FIELD_REF
)
1015 size_tree
= op
->op0
;
1018 machine_mode mode
= TYPE_MODE (type
);
1019 if (mode
== BLKmode
)
1020 size_tree
= TYPE_SIZE (type
);
1022 size
= GET_MODE_BITSIZE (mode
);
1024 if (size_tree
!= NULL_TREE
1025 && poly_int_tree_p (size_tree
))
1026 size
= wi::to_poly_offset (size_tree
);
1028 /* Initially, maxsize is the same as the accessed element size.
1029 In the following it will only grow (or become -1). */
1032 /* Compute cumulative bit-offset for nested component-refs and array-refs,
1033 and find the ultimate containing object. */
1034 FOR_EACH_VEC_ELT (ops
, i
, op
)
1038 /* These may be in the reference ops, but we cannot do anything
1039 sensible with them here. */
1041 /* Apart from ADDR_EXPR arguments to MEM_REF. */
1042 if (base
!= NULL_TREE
1043 && TREE_CODE (base
) == MEM_REF
1045 && DECL_P (TREE_OPERAND (op
->op0
, 0)))
1047 vn_reference_op_t pop
= &ops
[i
-1];
1048 base
= TREE_OPERAND (op
->op0
, 0);
1049 if (known_eq (pop
->off
, -1))
1055 offset
+= pop
->off
* BITS_PER_UNIT
;
1063 /* Record the base objects. */
1065 base_alias_set
= get_deref_alias_set (op
->op0
);
1066 *op0_p
= build2 (MEM_REF
, op
->type
,
1067 NULL_TREE
, op
->op0
);
1068 MR_DEPENDENCE_CLIQUE (*op0_p
) = op
->clique
;
1069 MR_DEPENDENCE_BASE (*op0_p
) = op
->base
;
1070 op0_p
= &TREE_OPERAND (*op0_p
, 0);
1081 /* And now the usual component-reference style ops. */
1083 offset
+= wi::to_poly_offset (op
->op1
);
1088 tree field
= op
->op0
;
1089 /* We do not have a complete COMPONENT_REF tree here so we
1090 cannot use component_ref_field_offset. Do the interesting
1092 tree this_offset
= DECL_FIELD_OFFSET (field
);
1094 if (op
->op1
|| !poly_int_tree_p (this_offset
))
1098 poly_offset_int woffset
= (wi::to_poly_offset (this_offset
)
1099 << LOG2_BITS_PER_UNIT
);
1100 woffset
+= wi::to_offset (DECL_FIELD_BIT_OFFSET (field
));
1106 case ARRAY_RANGE_REF
:
1108 /* We recorded the lower bound and the element size. */
1109 if (!poly_int_tree_p (op
->op0
)
1110 || !poly_int_tree_p (op
->op1
)
1111 || TREE_CODE (op
->op2
) != INTEGER_CST
)
1115 poly_offset_int woffset
1116 = wi::sext (wi::to_poly_offset (op
->op0
)
1117 - wi::to_poly_offset (op
->op1
),
1118 TYPE_PRECISION (TREE_TYPE (op
->op0
)));
1119 woffset
*= wi::to_offset (op
->op2
) * vn_ref_op_align_unit (op
);
1120 woffset
<<= LOG2_BITS_PER_UNIT
;
1132 case VIEW_CONVERT_EXPR
:
1149 if (base
== NULL_TREE
)
1152 ref
->ref
= NULL_TREE
;
1154 ref
->ref_alias_set
= set
;
1155 if (base_alias_set
!= -1)
1156 ref
->base_alias_set
= base_alias_set
;
1158 ref
->base_alias_set
= get_alias_set (base
);
1159 /* We discount volatiles from value-numbering elsewhere. */
1160 ref
->volatile_p
= false;
1162 if (!size
.to_shwi (&ref
->size
) || maybe_lt (ref
->size
, 0))
1170 if (!offset
.to_shwi (&ref
->offset
))
1177 if (!max_size
.to_shwi (&ref
->max_size
) || maybe_lt (ref
->max_size
, 0))
1183 /* Copy the operations present in load/store/call REF into RESULT, a vector of
1184 vn_reference_op_s's. */
1187 copy_reference_ops_from_call (gcall
*call
,
1188 vec
<vn_reference_op_s
> *result
)
1190 vn_reference_op_s temp
;
1192 tree lhs
= gimple_call_lhs (call
);
1195 /* If 2 calls have a different non-ssa lhs, vdef value numbers should be
1196 different. By adding the lhs here in the vector, we ensure that the
1197 hashcode is different, guaranteeing a different value number. */
1198 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
1200 memset (&temp
, 0, sizeof (temp
));
1201 temp
.opcode
= MODIFY_EXPR
;
1202 temp
.type
= TREE_TYPE (lhs
);
1205 result
->safe_push (temp
);
1208 /* Copy the type, opcode, function, static chain and EH region, if any. */
1209 memset (&temp
, 0, sizeof (temp
));
1210 temp
.type
= gimple_call_fntype (call
);
1211 temp
.opcode
= CALL_EXPR
;
1212 temp
.op0
= gimple_call_fn (call
);
1213 temp
.op1
= gimple_call_chain (call
);
1214 if (stmt_could_throw_p (cfun
, call
) && (lr
= lookup_stmt_eh_lp (call
)) > 0)
1215 temp
.op2
= size_int (lr
);
1217 result
->safe_push (temp
);
1219 /* Copy the call arguments. As they can be references as well,
1220 just chain them together. */
1221 for (i
= 0; i
< gimple_call_num_args (call
); ++i
)
1223 tree callarg
= gimple_call_arg (call
, i
);
1224 copy_reference_ops_from_ref (callarg
, result
);
1228 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1229 *I_P to point to the last element of the replacement. */
1231 vn_reference_fold_indirect (vec
<vn_reference_op_s
> *ops
,
1234 unsigned int i
= *i_p
;
1235 vn_reference_op_t op
= &(*ops
)[i
];
1236 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1238 poly_int64 addr_offset
= 0;
1240 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1241 from .foo.bar to the preceding MEM_REF offset and replace the
1242 address with &OBJ. */
1243 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (op
->op0
, 0),
1245 gcc_checking_assert (addr_base
&& TREE_CODE (addr_base
) != MEM_REF
);
1246 if (addr_base
!= TREE_OPERAND (op
->op0
, 0))
1249 = (poly_offset_int::from (wi::to_poly_wide (mem_op
->op0
),
1252 mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1253 op
->op0
= build_fold_addr_expr (addr_base
);
1254 if (tree_fits_shwi_p (mem_op
->op0
))
1255 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1263 /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates
1264 *I_P to point to the last element of the replacement. */
1266 vn_reference_maybe_forwprop_address (vec
<vn_reference_op_s
> *ops
,
1269 unsigned int i
= *i_p
;
1270 vn_reference_op_t op
= &(*ops
)[i
];
1271 vn_reference_op_t mem_op
= &(*ops
)[i
- 1];
1273 enum tree_code code
;
1274 poly_offset_int off
;
1276 def_stmt
= SSA_NAME_DEF_STMT (op
->op0
);
1277 if (!is_gimple_assign (def_stmt
))
1280 code
= gimple_assign_rhs_code (def_stmt
);
1281 if (code
!= ADDR_EXPR
1282 && code
!= POINTER_PLUS_EXPR
)
1285 off
= poly_offset_int::from (wi::to_poly_wide (mem_op
->op0
), SIGNED
);
1287 /* The only thing we have to do is from &OBJ.foo.bar add the offset
1288 from .foo.bar to the preceding MEM_REF offset and replace the
1289 address with &OBJ. */
1290 if (code
== ADDR_EXPR
)
1292 tree addr
, addr_base
;
1293 poly_int64 addr_offset
;
1295 addr
= gimple_assign_rhs1 (def_stmt
);
1296 addr_base
= get_addr_base_and_unit_offset (TREE_OPERAND (addr
, 0),
1298 /* If that didn't work because the address isn't invariant propagate
1299 the reference tree from the address operation in case the current
1300 dereference isn't offsetted. */
1302 && *i_p
== ops
->length () - 1
1303 && known_eq (off
, 0)
1304 /* This makes us disable this transform for PRE where the
1305 reference ops might be also used for code insertion which
1307 && default_vn_walk_kind
== VN_WALKREWRITE
)
1309 auto_vec
<vn_reference_op_s
, 32> tem
;
1310 copy_reference_ops_from_ref (TREE_OPERAND (addr
, 0), &tem
);
1311 /* Make sure to preserve TBAA info. The only objects not
1312 wrapped in MEM_REFs that can have their address taken are
1314 if (tem
.length () >= 2
1315 && tem
[tem
.length () - 2].opcode
== MEM_REF
)
1317 vn_reference_op_t new_mem_op
= &tem
[tem
.length () - 2];
1319 = wide_int_to_tree (TREE_TYPE (mem_op
->op0
),
1320 wi::to_poly_wide (new_mem_op
->op0
));
1323 gcc_assert (tem
.last ().opcode
== STRING_CST
);
1326 ops
->safe_splice (tem
);
1331 || TREE_CODE (addr_base
) != MEM_REF
1332 || (TREE_CODE (TREE_OPERAND (addr_base
, 0)) == SSA_NAME
1333 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (addr_base
, 0))))
1337 off
+= mem_ref_offset (addr_base
);
1338 op
->op0
= TREE_OPERAND (addr_base
, 0);
1343 ptr
= gimple_assign_rhs1 (def_stmt
);
1344 ptroff
= gimple_assign_rhs2 (def_stmt
);
1345 if (TREE_CODE (ptr
) != SSA_NAME
1346 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
)
1347 /* Make sure to not endlessly recurse.
1348 See gcc.dg/tree-ssa/20040408-1.c for an example. Can easily
1349 happen when we value-number a PHI to its backedge value. */
1350 || SSA_VAL (ptr
) == op
->op0
1351 || !poly_int_tree_p (ptroff
))
1354 off
+= wi::to_poly_offset (ptroff
);
1358 mem_op
->op0
= wide_int_to_tree (TREE_TYPE (mem_op
->op0
), off
);
1359 if (tree_fits_shwi_p (mem_op
->op0
))
1360 mem_op
->off
= tree_to_shwi (mem_op
->op0
);
1363 /* ??? Can end up with endless recursion here!?
1364 gcc.c-torture/execute/strcmp-1.c */
1365 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1366 op
->op0
= SSA_VAL (op
->op0
);
1367 if (TREE_CODE (op
->op0
) != SSA_NAME
)
1368 op
->opcode
= TREE_CODE (op
->op0
);
1371 if (TREE_CODE (op
->op0
) == SSA_NAME
)
1372 vn_reference_maybe_forwprop_address (ops
, i_p
);
1373 else if (TREE_CODE (op
->op0
) == ADDR_EXPR
)
1374 vn_reference_fold_indirect (ops
, i_p
);
1378 /* Optimize the reference REF to a constant if possible or return
1379 NULL_TREE if not. */
1382 fully_constant_vn_reference_p (vn_reference_t ref
)
1384 vec
<vn_reference_op_s
> operands
= ref
->operands
;
1385 vn_reference_op_t op
;
1387 /* Try to simplify the translated expression if it is
1388 a call to a builtin function with at most two arguments. */
1390 if (op
->opcode
== CALL_EXPR
1391 && TREE_CODE (op
->op0
) == ADDR_EXPR
1392 && TREE_CODE (TREE_OPERAND (op
->op0
, 0)) == FUNCTION_DECL
1393 && fndecl_built_in_p (TREE_OPERAND (op
->op0
, 0))
1394 && operands
.length () >= 2
1395 && operands
.length () <= 3)
1397 vn_reference_op_t arg0
, arg1
= NULL
;
1398 bool anyconst
= false;
1399 arg0
= &operands
[1];
1400 if (operands
.length () > 2)
1401 arg1
= &operands
[2];
1402 if (TREE_CODE_CLASS (arg0
->opcode
) == tcc_constant
1403 || (arg0
->opcode
== ADDR_EXPR
1404 && is_gimple_min_invariant (arg0
->op0
)))
1407 && (TREE_CODE_CLASS (arg1
->opcode
) == tcc_constant
1408 || (arg1
->opcode
== ADDR_EXPR
1409 && is_gimple_min_invariant (arg1
->op0
))))
1413 tree folded
= build_call_expr (TREE_OPERAND (op
->op0
, 0),
1416 arg1
? arg1
->op0
: NULL
);
1418 && TREE_CODE (folded
) == NOP_EXPR
)
1419 folded
= TREE_OPERAND (folded
, 0);
1421 && is_gimple_min_invariant (folded
))
1426 /* Simplify reads from constants or constant initializers. */
1427 else if (BITS_PER_UNIT
== 8
1428 && COMPLETE_TYPE_P (ref
->type
)
1429 && is_gimple_reg_type (ref
->type
))
1433 if (INTEGRAL_TYPE_P (ref
->type
))
1434 size
= TYPE_PRECISION (ref
->type
);
1435 else if (tree_fits_shwi_p (TYPE_SIZE (ref
->type
)))
1436 size
= tree_to_shwi (TYPE_SIZE (ref
->type
));
1439 if (size
% BITS_PER_UNIT
!= 0
1440 || size
> MAX_BITSIZE_MODE_ANY_MODE
)
1442 size
/= BITS_PER_UNIT
;
1444 for (i
= 0; i
< operands
.length (); ++i
)
1446 if (TREE_CODE_CLASS (operands
[i
].opcode
) == tcc_constant
)
1451 if (known_eq (operands
[i
].off
, -1))
1453 off
+= operands
[i
].off
;
1454 if (operands
[i
].opcode
== MEM_REF
)
1460 vn_reference_op_t base
= &operands
[--i
];
1461 tree ctor
= error_mark_node
;
1462 tree decl
= NULL_TREE
;
1463 if (TREE_CODE_CLASS (base
->opcode
) == tcc_constant
)
1465 else if (base
->opcode
== MEM_REF
1466 && base
[1].opcode
== ADDR_EXPR
1467 && (TREE_CODE (TREE_OPERAND (base
[1].op0
, 0)) == VAR_DECL
1468 || TREE_CODE (TREE_OPERAND (base
[1].op0
, 0)) == CONST_DECL
1469 || TREE_CODE (TREE_OPERAND (base
[1].op0
, 0)) == STRING_CST
))
1471 decl
= TREE_OPERAND (base
[1].op0
, 0);
1472 if (TREE_CODE (decl
) == STRING_CST
)
1475 ctor
= ctor_for_folding (decl
);
1477 if (ctor
== NULL_TREE
)
1478 return build_zero_cst (ref
->type
);
1479 else if (ctor
!= error_mark_node
)
1481 HOST_WIDE_INT const_off
;
1484 tree res
= fold_ctor_reference (ref
->type
, ctor
,
1485 off
* BITS_PER_UNIT
,
1486 size
* BITS_PER_UNIT
, decl
);
1489 STRIP_USELESS_TYPE_CONVERSION (res
);
1490 if (is_gimple_min_invariant (res
))
1494 else if (off
.is_constant (&const_off
))
1496 unsigned char buf
[MAX_BITSIZE_MODE_ANY_MODE
/ BITS_PER_UNIT
];
1497 int len
= native_encode_expr (ctor
, buf
, size
, const_off
);
1499 return native_interpret_expr (ref
->type
, buf
, len
);
1507 /* Return true if OPS contain a storage order barrier. */
1510 contains_storage_order_barrier_p (vec
<vn_reference_op_s
> ops
)
1512 vn_reference_op_t op
;
1515 FOR_EACH_VEC_ELT (ops
, i
, op
)
1516 if (op
->opcode
== VIEW_CONVERT_EXPR
&& op
->reverse
)
1522 /* Transform any SSA_NAME's in a vector of vn_reference_op_s
1523 structures into their value numbers. This is done in-place, and
1524 the vector passed in is returned. *VALUEIZED_ANYTHING will specify
1525 whether any operands were valueized. */
1527 static vec
<vn_reference_op_s
>
1528 valueize_refs_1 (vec
<vn_reference_op_s
> orig
, bool *valueized_anything
,
1529 bool with_avail
= false)
1531 vn_reference_op_t vro
;
1534 *valueized_anything
= false;
1536 FOR_EACH_VEC_ELT (orig
, i
, vro
)
1538 if (vro
->opcode
== SSA_NAME
1539 || (vro
->op0
&& TREE_CODE (vro
->op0
) == SSA_NAME
))
1541 tree tem
= with_avail
? vn_valueize (vro
->op0
) : SSA_VAL (vro
->op0
);
1542 if (tem
!= vro
->op0
)
1544 *valueized_anything
= true;
1547 /* If it transforms from an SSA_NAME to a constant, update
1549 if (TREE_CODE (vro
->op0
) != SSA_NAME
&& vro
->opcode
== SSA_NAME
)
1550 vro
->opcode
= TREE_CODE (vro
->op0
);
1552 if (vro
->op1
&& TREE_CODE (vro
->op1
) == SSA_NAME
)
1554 tree tem
= with_avail
? vn_valueize (vro
->op1
) : SSA_VAL (vro
->op1
);
1555 if (tem
!= vro
->op1
)
1557 *valueized_anything
= true;
1561 if (vro
->op2
&& TREE_CODE (vro
->op2
) == SSA_NAME
)
1563 tree tem
= with_avail
? vn_valueize (vro
->op2
) : SSA_VAL (vro
->op2
);
1564 if (tem
!= vro
->op2
)
1566 *valueized_anything
= true;
1570 /* If it transforms from an SSA_NAME to an address, fold with
1571 a preceding indirect reference. */
1574 && TREE_CODE (vro
->op0
) == ADDR_EXPR
1575 && orig
[i
- 1].opcode
== MEM_REF
)
1577 if (vn_reference_fold_indirect (&orig
, &i
))
1578 *valueized_anything
= true;
1581 && vro
->opcode
== SSA_NAME
1582 && orig
[i
- 1].opcode
== MEM_REF
)
1584 if (vn_reference_maybe_forwprop_address (&orig
, &i
))
1585 *valueized_anything
= true;
1587 /* If it transforms a non-constant ARRAY_REF into a constant
1588 one, adjust the constant offset. */
1589 else if (vro
->opcode
== ARRAY_REF
1590 && known_eq (vro
->off
, -1)
1591 && poly_int_tree_p (vro
->op0
)
1592 && poly_int_tree_p (vro
->op1
)
1593 && TREE_CODE (vro
->op2
) == INTEGER_CST
)
1595 poly_offset_int off
= ((wi::to_poly_offset (vro
->op0
)
1596 - wi::to_poly_offset (vro
->op1
))
1597 * wi::to_offset (vro
->op2
)
1598 * vn_ref_op_align_unit (vro
));
1599 off
.to_shwi (&vro
->off
);
1606 static vec
<vn_reference_op_s
>
1607 valueize_refs (vec
<vn_reference_op_s
> orig
)
1610 return valueize_refs_1 (orig
, &tem
);
1613 static vec
<vn_reference_op_s
> shared_lookup_references
;
1615 /* Create a vector of vn_reference_op_s structures from REF, a
1616 REFERENCE_CLASS_P tree. The vector is shared among all callers of
1617 this function. *VALUEIZED_ANYTHING will specify whether any
1618 operands were valueized. */
1620 static vec
<vn_reference_op_s
>
1621 valueize_shared_reference_ops_from_ref (tree ref
, bool *valueized_anything
)
1625 shared_lookup_references
.truncate (0);
1626 copy_reference_ops_from_ref (ref
, &shared_lookup_references
);
1627 shared_lookup_references
= valueize_refs_1 (shared_lookup_references
,
1628 valueized_anything
);
1629 return shared_lookup_references
;
1632 /* Create a vector of vn_reference_op_s structures from CALL, a
1633 call statement. The vector is shared among all callers of
1636 static vec
<vn_reference_op_s
>
1637 valueize_shared_reference_ops_from_call (gcall
*call
)
1641 shared_lookup_references
.truncate (0);
1642 copy_reference_ops_from_call (call
, &shared_lookup_references
);
1643 shared_lookup_references
= valueize_refs (shared_lookup_references
);
1644 return shared_lookup_references
;
1647 /* Lookup a SCCVN reference operation VR in the current hash table.
1648 Returns the resulting value number if it exists in the hash table,
1649 NULL_TREE otherwise. VNRESULT will be filled in with the actual
1650 vn_reference_t stored in the hashtable if something is found. */
1653 vn_reference_lookup_1 (vn_reference_t vr
, vn_reference_t
*vnresult
)
1655 vn_reference_s
**slot
;
1658 hash
= vr
->hashcode
;
1659 slot
= valid_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1663 *vnresult
= (vn_reference_t
)*slot
;
1664 return ((vn_reference_t
)*slot
)->result
;
1670 /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
1671 with the current VUSE and performs the expression lookup. */
1674 vn_reference_lookup_2 (ao_ref
*op ATTRIBUTE_UNUSED
, tree vuse
, void *vr_
)
1676 vn_reference_t vr
= (vn_reference_t
)vr_
;
1677 vn_reference_s
**slot
;
1681 *last_vuse_ptr
= vuse
;
1683 /* Fixup vuse and hash. */
1685 vr
->hashcode
= vr
->hashcode
- SSA_NAME_VERSION (vr
->vuse
);
1686 vr
->vuse
= vuse_ssa_val (vuse
);
1688 vr
->hashcode
= vr
->hashcode
+ SSA_NAME_VERSION (vr
->vuse
);
1690 hash
= vr
->hashcode
;
1691 slot
= valid_info
->references
->find_slot_with_hash (vr
, hash
, NO_INSERT
);
1698 /* Lookup an existing or insert a new vn_reference entry into the
1699 value table for the VUSE, SET, TYPE, OPERANDS reference which
1700 has the value VALUE which is either a constant or an SSA name. */
1702 static vn_reference_t
1703 vn_reference_lookup_or_insert_for_pieces (tree vuse
,
1706 vec
<vn_reference_op_s
,
1711 vn_reference_t result
;
1713 vr1
.vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
1714 vr1
.operands
= operands
;
1717 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
1718 if (vn_reference_lookup_1 (&vr1
, &result
))
1720 if (TREE_CODE (value
) == SSA_NAME
)
1721 value_id
= VN_INFO (value
)->value_id
;
1723 value_id
= get_or_alloc_constant_value_id (value
);
1724 return vn_reference_insert_pieces (vuse
, set
, type
,
1725 operands
.copy (), value
, value_id
);
1728 /* Return a value-number for RCODE OPS... either by looking up an existing
1729 value-number for the simplified result or by inserting the operation if
1733 vn_nary_build_or_lookup_1 (gimple_match_op
*res_op
, bool insert
)
1735 tree result
= NULL_TREE
;
1736 /* We will be creating a value number for
1738 So first simplify and lookup this expression to see if it
1739 is already available. */
1740 mprts_hook
= vn_lookup_simplify_result
;
1742 switch (TREE_CODE_LENGTH ((tree_code
) res_op
->code
))
1745 res
= gimple_resimplify1 (NULL
, res_op
, vn_valueize
);
1748 res
= gimple_resimplify2 (NULL
, res_op
, vn_valueize
);
1751 res
= gimple_resimplify3 (NULL
, res_op
, vn_valueize
);
1755 gimple
*new_stmt
= NULL
;
1757 && gimple_simplified_result_is_gimple_val (res_op
))
1759 /* The expression is already available. */
1760 result
= res_op
->ops
[0];
1761 /* Valueize it, simplification returns sth in AVAIL only. */
1762 if (TREE_CODE (result
) == SSA_NAME
)
1763 result
= SSA_VAL (result
);
1767 tree val
= vn_lookup_simplify_result (res_op
);
1770 gimple_seq stmts
= NULL
;
1771 result
= maybe_push_res_to_seq (res_op
, &stmts
);
1774 gcc_assert (gimple_seq_singleton_p (stmts
));
1775 new_stmt
= gimple_seq_first_stmt (stmts
);
1779 /* The expression is already available. */
1784 /* The expression is not yet available, value-number lhs to
1785 the new SSA_NAME we created. */
1786 /* Initialize value-number information properly. */
1787 vn_ssa_aux_t result_info
= VN_INFO (result
);
1788 result_info
->valnum
= result
;
1789 result_info
->value_id
= get_next_value_id ();
1790 result_info
->visited
= 1;
1791 gimple_seq_add_stmt_without_update (&VN_INFO (result
)->expr
,
1793 result_info
->needs_insertion
= true;
1794 /* ??? PRE phi-translation inserts NARYs without corresponding
1795 SSA name result. Re-use those but set their result according
1796 to the stmt we just built. */
1797 vn_nary_op_t nary
= NULL
;
1798 vn_nary_op_lookup_stmt (new_stmt
, &nary
);
1801 gcc_assert (! nary
->predicated_values
&& nary
->u
.result
== NULL_TREE
);
1802 nary
->u
.result
= gimple_assign_lhs (new_stmt
);
1804 /* As all "inserted" statements are singleton SCCs, insert
1805 to the valid table. This is strictly needed to
1806 avoid re-generating new value SSA_NAMEs for the same
1807 expression during SCC iteration over and over (the
1808 optimistic table gets cleared after each iteration).
1809 We do not need to insert into the optimistic table, as
1810 lookups there will fall back to the valid table. */
1813 unsigned int length
= vn_nary_length_from_stmt (new_stmt
);
1815 = alloc_vn_nary_op_noinit (length
, &vn_tables_insert_obstack
);
1816 vno1
->value_id
= result_info
->value_id
;
1817 vno1
->length
= length
;
1818 vno1
->predicated_values
= 0;
1819 vno1
->u
.result
= result
;
1820 init_vn_nary_op_from_stmt (vno1
, new_stmt
);
1821 vn_nary_op_insert_into (vno1
, valid_info
->nary
, true);
1822 /* Also do not link it into the undo chain. */
1823 last_inserted_nary
= vno1
->next
;
1824 vno1
->next
= (vn_nary_op_t
)(void *)-1;
1826 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1828 fprintf (dump_file
, "Inserting name ");
1829 print_generic_expr (dump_file
, result
);
1830 fprintf (dump_file
, " for expression ");
1831 print_gimple_expr (dump_file
, new_stmt
, 0, TDF_SLIM
);
1832 fprintf (dump_file
, "\n");
1838 /* Return a value-number for RCODE OPS... either by looking up an existing
1839 value-number for the simplified result or by inserting the operation. */
1842 vn_nary_build_or_lookup (gimple_match_op
*res_op
)
1844 return vn_nary_build_or_lookup_1 (res_op
, true);
1847 /* Try to simplify the expression RCODE OPS... of type TYPE and return
1848 its value if present. */
1851 vn_nary_simplify (vn_nary_op_t nary
)
1853 if (nary
->length
> gimple_match_op::MAX_NUM_OPS
)
1855 gimple_match_op
op (gimple_match_cond::UNCOND
, nary
->opcode
,
1856 nary
->type
, nary
->length
);
1857 memcpy (op
.ops
, nary
->op
, sizeof (tree
) * nary
->length
);
1858 return vn_nary_build_or_lookup_1 (&op
, false);
1861 /* Elimination engine. */
1863 class eliminate_dom_walker
: public dom_walker
1866 eliminate_dom_walker (cdi_direction
, bitmap
);
1867 ~eliminate_dom_walker ();
1869 virtual edge
before_dom_children (basic_block
);
1870 virtual void after_dom_children (basic_block
);
1872 virtual tree
eliminate_avail (basic_block
, tree op
);
1873 virtual void eliminate_push_avail (basic_block
, tree op
);
1874 tree
eliminate_insert (basic_block
, gimple_stmt_iterator
*gsi
, tree val
);
1876 void eliminate_stmt (basic_block
, gimple_stmt_iterator
*);
1878 unsigned eliminate_cleanup (bool region_p
= false);
1881 unsigned int el_todo
;
1882 unsigned int eliminations
;
1883 unsigned int insertions
;
1885 /* SSA names that had their defs inserted by PRE if do_pre. */
1886 bitmap inserted_exprs
;
1888 /* Blocks with statements that have had their EH properties changed. */
1889 bitmap need_eh_cleanup
;
1891 /* Blocks with statements that have had their AB properties changed. */
1892 bitmap need_ab_cleanup
;
1894 /* Local state for the eliminate domwalk. */
1895 auto_vec
<gimple
*> to_remove
;
1896 auto_vec
<gimple
*> to_fixup
;
1897 auto_vec
<tree
> avail
;
1898 auto_vec
<tree
> avail_stack
;
1901 /* Adaptor to the elimination engine using RPO availability. */
1903 class rpo_elim
: public eliminate_dom_walker
1906 rpo_elim(basic_block entry_
)
1907 : eliminate_dom_walker (CDI_DOMINATORS
, NULL
), entry (entry_
) {}
1910 virtual tree
eliminate_avail (basic_block
, tree op
);
1912 virtual void eliminate_push_avail (basic_block
, tree
);
1915 /* Instead of having a local availability lattice for each
1916 basic-block and availability at X defined as union of
1917 the local availabilities at X and its dominators we're
1918 turning this upside down and track availability per
1919 value given values are usually made available at very
1920 few points (at least one).
1921 So we have a value -> vec<location, leader> map where
1922 LOCATION is specifying the basic-block LEADER is made
1923 available for VALUE. We push to this vector in RPO
1924 order thus for iteration we can simply pop the last
1926 LOCATION is the basic-block index and LEADER is its
1927 SSA name version. */
1928 /* ??? We'd like to use auto_vec here with embedded storage
1929 but that doesn't play well until we can provide move
1930 constructors and use std::move on hash-table expansion.
1931 So for now this is a bit more expensive than necessary.
1932 We eventually want to switch to a chaining scheme like
1933 for hashtable entries for unwinding which would make
1934 making the vector part of the vn_ssa_aux structure possible. */
1935 typedef hash_map
<tree
, vec
<std::pair
<int, int> > > rpo_avail_t
;
1936 rpo_avail_t m_rpo_avail
;
1939 /* Global RPO state for access from hooks. */
1940 static rpo_elim
*rpo_avail
;
1941 basic_block vn_context_bb
;
1943 /* Callback for walk_non_aliased_vuses. Tries to perform a lookup
1944 from the statement defining VUSE and if not successful tries to
1945 translate *REFP and VR_ through an aggregate copy at the definition
1946 of VUSE. If *DISAMBIGUATE_ONLY is true then do not perform translation
1947 of *REF and *VR. If only disambiguation was performed then
1948 *DISAMBIGUATE_ONLY is set to true. */
1951 vn_reference_lookup_3 (ao_ref
*ref
, tree vuse
, void *vr_
,
1952 bool *disambiguate_only
)
1954 vn_reference_t vr
= (vn_reference_t
)vr_
;
1955 gimple
*def_stmt
= SSA_NAME_DEF_STMT (vuse
);
1956 tree base
= ao_ref_base (ref
);
1957 HOST_WIDE_INT offseti
, maxsizei
;
1958 static vec
<vn_reference_op_s
> lhs_ops
;
1960 bool lhs_ref_ok
= false;
1961 poly_int64 copy_size
;
1963 /* First try to disambiguate after value-replacing in the definitions LHS. */
1964 if (is_gimple_assign (def_stmt
))
1966 tree lhs
= gimple_assign_lhs (def_stmt
);
1967 bool valueized_anything
= false;
1968 /* Avoid re-allocation overhead. */
1969 lhs_ops
.truncate (0);
1970 basic_block saved_rpo_bb
= vn_context_bb
;
1971 vn_context_bb
= gimple_bb (def_stmt
);
1972 copy_reference_ops_from_ref (lhs
, &lhs_ops
);
1973 lhs_ops
= valueize_refs_1 (lhs_ops
, &valueized_anything
, true);
1974 vn_context_bb
= saved_rpo_bb
;
1975 if (valueized_anything
)
1977 lhs_ref_ok
= ao_ref_init_from_vn_reference (&lhs_ref
,
1978 get_alias_set (lhs
),
1979 TREE_TYPE (lhs
), lhs_ops
);
1981 && !refs_may_alias_p_1 (ref
, &lhs_ref
, true))
1983 *disambiguate_only
= true;
1989 ao_ref_init (&lhs_ref
, lhs
);
1993 /* If we reach a clobbering statement try to skip it and see if
1994 we find a VN result with exactly the same value as the
1995 possible clobber. In this case we can ignore the clobber
1996 and return the found value.
1997 Note that we don't need to worry about partial overlapping
1998 accesses as we then can use TBAA to disambiguate against the
1999 clobbering statement when looking up a load (thus the
2000 VN_WALKREWRITE guard). */
2001 if (vn_walk_kind
== VN_WALKREWRITE
2002 && is_gimple_reg_type (TREE_TYPE (lhs
))
2003 && types_compatible_p (TREE_TYPE (lhs
), vr
->type
)
2004 /* The overlap restriction breaks down when either access
2005 alias-set is zero. Still for accesses of the size of
2006 an addressable unit there can be no overlaps. Overlaps
2007 between different union members are not an issue since
2008 activation of a union member via a store makes the
2009 values of untouched bytes unspecified. */
2010 && (known_eq (ref
->size
, BITS_PER_UNIT
)
2011 || (get_alias_set (lhs
) != 0
2012 && ao_ref_alias_set (ref
) != 0)))
2014 tree
*saved_last_vuse_ptr
= last_vuse_ptr
;
2015 /* Do not update last_vuse_ptr in vn_reference_lookup_2. */
2016 last_vuse_ptr
= NULL
;
2017 tree saved_vuse
= vr
->vuse
;
2018 hashval_t saved_hashcode
= vr
->hashcode
;
2019 void *res
= vn_reference_lookup_2 (ref
, gimple_vuse (def_stmt
), vr
);
2020 /* Need to restore vr->vuse and vr->hashcode. */
2021 vr
->vuse
= saved_vuse
;
2022 vr
->hashcode
= saved_hashcode
;
2023 last_vuse_ptr
= saved_last_vuse_ptr
;
2024 if (res
&& res
!= (void *)-1)
2026 vn_reference_t vnresult
= (vn_reference_t
) res
;
2027 if (vnresult
->result
2028 && operand_equal_p (vnresult
->result
,
2029 gimple_assign_rhs1 (def_stmt
), 0))
2034 else if (gimple_call_builtin_p (def_stmt
, BUILT_IN_NORMAL
)
2035 && gimple_call_num_args (def_stmt
) <= 4)
2037 /* For builtin calls valueize its arguments and call the
2038 alias oracle again. Valueization may improve points-to
2039 info of pointers and constify size and position arguments.
2040 Originally this was motivated by PR61034 which has
2041 conditional calls to free falsely clobbering ref because
2042 of imprecise points-to info of the argument. */
2044 bool valueized_anything
= false;
2045 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
2047 oldargs
[i
] = gimple_call_arg (def_stmt
, i
);
2048 tree val
= vn_valueize (oldargs
[i
]);
2049 if (val
!= oldargs
[i
])
2051 gimple_call_set_arg (def_stmt
, i
, val
);
2052 valueized_anything
= true;
2055 if (valueized_anything
)
2057 bool res
= call_may_clobber_ref_p_1 (as_a
<gcall
*> (def_stmt
),
2059 for (unsigned i
= 0; i
< gimple_call_num_args (def_stmt
); ++i
)
2060 gimple_call_set_arg (def_stmt
, i
, oldargs
[i
]);
2063 *disambiguate_only
= true;
2069 if (*disambiguate_only
)
2072 /* If we cannot constrain the size of the reference we cannot
2073 test if anything kills it. */
2074 if (!ref
->max_size_known_p ())
2077 poly_int64 offset
= ref
->offset
;
2078 poly_int64 maxsize
= ref
->max_size
;
2080 /* We can't deduce anything useful from clobbers. */
2081 if (gimple_clobber_p (def_stmt
))
2084 /* def_stmt may-defs *ref. See if we can derive a value for *ref
2085 from that definition.
2087 if (is_gimple_reg_type (vr
->type
)
2088 && gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMSET
)
2089 && (integer_zerop (gimple_call_arg (def_stmt
, 1))
2090 || ((TREE_CODE (gimple_call_arg (def_stmt
, 1)) == INTEGER_CST
2091 || (INTEGRAL_TYPE_P (vr
->type
) && known_eq (ref
->size
, 8)))
2092 && CHAR_BIT
== 8 && BITS_PER_UNIT
== 8
2093 && offset
.is_constant (&offseti
)
2094 && offseti
% BITS_PER_UNIT
== 0))
2095 && poly_int_tree_p (gimple_call_arg (def_stmt
, 2))
2096 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
2097 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
))
2100 poly_int64 offset2
, size2
, maxsize2
;
2102 tree ref2
= gimple_call_arg (def_stmt
, 0);
2103 if (TREE_CODE (ref2
) == SSA_NAME
)
2105 ref2
= SSA_VAL (ref2
);
2106 if (TREE_CODE (ref2
) == SSA_NAME
2107 && (TREE_CODE (base
) != MEM_REF
2108 || TREE_OPERAND (base
, 0) != ref2
))
2110 gimple
*def_stmt
= SSA_NAME_DEF_STMT (ref2
);
2111 if (gimple_assign_single_p (def_stmt
)
2112 && gimple_assign_rhs_code (def_stmt
) == ADDR_EXPR
)
2113 ref2
= gimple_assign_rhs1 (def_stmt
);
2116 if (TREE_CODE (ref2
) == ADDR_EXPR
)
2118 ref2
= TREE_OPERAND (ref2
, 0);
2119 base2
= get_ref_base_and_extent (ref2
, &offset2
, &size2
, &maxsize2
,
2121 if (!known_size_p (maxsize2
)
2122 || !known_eq (maxsize2
, size2
)
2123 || !operand_equal_p (base
, base2
, OEP_ADDRESS_OF
))
2126 else if (TREE_CODE (ref2
) == SSA_NAME
)
2129 if (TREE_CODE (base
) != MEM_REF
2130 || !(mem_ref_offset (base
) << LOG2_BITS_PER_UNIT
).to_shwi (&soff
))
2134 if (TREE_OPERAND (base
, 0) != ref2
)
2136 gimple
*def
= SSA_NAME_DEF_STMT (ref2
);
2137 if (is_gimple_assign (def
)
2138 && gimple_assign_rhs_code (def
) == POINTER_PLUS_EXPR
2139 && gimple_assign_rhs1 (def
) == TREE_OPERAND (base
, 0)
2140 && poly_int_tree_p (gimple_assign_rhs2 (def
))
2141 && (wi::to_poly_offset (gimple_assign_rhs2 (def
))
2142 << LOG2_BITS_PER_UNIT
).to_shwi (&offset2
))
2144 ref2
= gimple_assign_rhs1 (def
);
2145 if (TREE_CODE (ref2
) == SSA_NAME
)
2146 ref2
= SSA_VAL (ref2
);
2154 tree len
= gimple_call_arg (def_stmt
, 2);
2155 if (known_subrange_p (offset
, maxsize
, offset2
,
2156 wi::to_poly_offset (len
) << LOG2_BITS_PER_UNIT
))
2159 if (integer_zerop (gimple_call_arg (def_stmt
, 1)))
2160 val
= build_zero_cst (vr
->type
);
2161 else if (INTEGRAL_TYPE_P (vr
->type
)
2162 && known_eq (ref
->size
, 8))
2164 gimple_match_op
res_op (gimple_match_cond::UNCOND
, NOP_EXPR
,
2165 vr
->type
, gimple_call_arg (def_stmt
, 1));
2166 val
= vn_nary_build_or_lookup (&res_op
);
2168 || (TREE_CODE (val
) == SSA_NAME
2169 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
)))
2174 unsigned len
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (vr
->type
));
2175 unsigned char *buf
= XALLOCAVEC (unsigned char, len
);
2176 memset (buf
, TREE_INT_CST_LOW (gimple_call_arg (def_stmt
, 1)),
2178 val
= native_interpret_expr (vr
->type
, buf
, len
);
2182 return vn_reference_lookup_or_insert_for_pieces
2183 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
2187 /* 2) Assignment from an empty CONSTRUCTOR. */
2188 else if (is_gimple_reg_type (vr
->type
)
2189 && gimple_assign_single_p (def_stmt
)
2190 && gimple_assign_rhs_code (def_stmt
) == CONSTRUCTOR
2191 && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt
)) == 0)
2194 poly_int64 offset2
, size2
, maxsize2
;
2196 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
2197 &offset2
, &size2
, &maxsize2
, &reverse
);
2198 if (known_size_p (maxsize2
)
2199 && known_eq (maxsize2
, size2
)
2200 && operand_equal_p (base
, base2
, 0)
2201 && known_subrange_p (offset
, maxsize
, offset2
, size2
))
2203 tree val
= build_zero_cst (vr
->type
);
2204 return vn_reference_lookup_or_insert_for_pieces
2205 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
2209 /* 3) Assignment from a constant. We can use folds native encode/interpret
2210 routines to extract the assigned bits. */
2211 else if (known_eq (ref
->size
, maxsize
)
2212 && is_gimple_reg_type (vr
->type
)
2213 && !contains_storage_order_barrier_p (vr
->operands
)
2214 && gimple_assign_single_p (def_stmt
)
2215 && CHAR_BIT
== 8 && BITS_PER_UNIT
== 8
2216 /* native_encode and native_decode operate on arrays of bytes
2217 and so fundamentally need a compile-time size and offset. */
2218 && maxsize
.is_constant (&maxsizei
)
2219 && maxsizei
% BITS_PER_UNIT
== 0
2220 && offset
.is_constant (&offseti
)
2221 && offseti
% BITS_PER_UNIT
== 0
2222 && (is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
))
2223 || (TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
2224 && is_gimple_min_invariant (SSA_VAL (gimple_assign_rhs1 (def_stmt
))))))
2227 HOST_WIDE_INT offset2
, size2
;
2229 base2
= get_ref_base_and_extent_hwi (gimple_assign_lhs (def_stmt
),
2230 &offset2
, &size2
, &reverse
);
2233 && size2
% BITS_PER_UNIT
== 0
2234 && offset2
% BITS_PER_UNIT
== 0
2235 && operand_equal_p (base
, base2
, 0)
2236 && known_subrange_p (offseti
, maxsizei
, offset2
, size2
))
2238 /* We support up to 512-bit values (for V8DFmode). */
2239 unsigned char buffer
[64];
2242 tree rhs
= gimple_assign_rhs1 (def_stmt
);
2243 if (TREE_CODE (rhs
) == SSA_NAME
)
2244 rhs
= SSA_VAL (rhs
);
2245 len
= native_encode_expr (gimple_assign_rhs1 (def_stmt
),
2246 buffer
, sizeof (buffer
),
2247 (offseti
- offset2
) / BITS_PER_UNIT
);
2248 if (len
> 0 && len
* BITS_PER_UNIT
>= maxsizei
)
2250 tree type
= vr
->type
;
2251 /* Make sure to interpret in a type that has a range
2252 covering the whole access size. */
2253 if (INTEGRAL_TYPE_P (vr
->type
)
2254 && maxsizei
!= TYPE_PRECISION (vr
->type
))
2255 type
= build_nonstandard_integer_type (maxsizei
,
2256 TYPE_UNSIGNED (type
));
2257 tree val
= native_interpret_expr (type
, buffer
,
2258 maxsizei
/ BITS_PER_UNIT
);
2259 /* If we chop off bits because the types precision doesn't
2260 match the memory access size this is ok when optimizing
2261 reads but not when called from the DSE code during
2264 && type
!= vr
->type
)
2266 if (! int_fits_type_p (val
, vr
->type
))
2269 val
= fold_convert (vr
->type
, val
);
2273 return vn_reference_lookup_or_insert_for_pieces
2274 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
2279 /* 4) Assignment from an SSA name which definition we may be able
2280 to access pieces from. */
2281 else if (known_eq (ref
->size
, maxsize
)
2282 && is_gimple_reg_type (vr
->type
)
2283 && !contains_storage_order_barrier_p (vr
->operands
)
2284 && gimple_assign_single_p (def_stmt
)
2285 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
)
2288 poly_int64 offset2
, size2
, maxsize2
;
2290 base2
= get_ref_base_and_extent (gimple_assign_lhs (def_stmt
),
2291 &offset2
, &size2
, &maxsize2
,
2293 tree def_rhs
= gimple_assign_rhs1 (def_stmt
);
2295 && known_size_p (maxsize2
)
2296 && known_eq (maxsize2
, size2
)
2297 && operand_equal_p (base
, base2
, 0)
2298 && known_subrange_p (offset
, maxsize
, offset2
, size2
)
2299 /* ??? We can't handle bitfield precision extracts without
2300 either using an alternate type for the BIT_FIELD_REF and
2301 then doing a conversion or possibly adjusting the offset
2302 according to endianness. */
2303 && (! INTEGRAL_TYPE_P (vr
->type
)
2304 || known_eq (ref
->size
, TYPE_PRECISION (vr
->type
)))
2305 && multiple_p (ref
->size
, BITS_PER_UNIT
)
2306 && (! INTEGRAL_TYPE_P (TREE_TYPE (def_rhs
))
2307 || type_has_mode_precision_p (TREE_TYPE (def_rhs
))))
2309 gimple_match_op
op (gimple_match_cond::UNCOND
,
2310 BIT_FIELD_REF
, vr
->type
,
2311 vn_valueize (def_rhs
),
2312 bitsize_int (ref
->size
),
2313 bitsize_int (offset
- offset2
));
2314 tree val
= vn_nary_build_or_lookup (&op
);
2316 && (TREE_CODE (val
) != SSA_NAME
2317 || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
)))
2319 vn_reference_t res
= vn_reference_lookup_or_insert_for_pieces
2320 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
2326 /* 5) For aggregate copies translate the reference through them if
2327 the copy kills ref. */
2328 else if (vn_walk_kind
== VN_WALKREWRITE
2329 && gimple_assign_single_p (def_stmt
)
2330 && (DECL_P (gimple_assign_rhs1 (def_stmt
))
2331 || TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == MEM_REF
2332 || handled_component_p (gimple_assign_rhs1 (def_stmt
))))
2336 auto_vec
<vn_reference_op_s
> rhs
;
2337 vn_reference_op_t vro
;
2343 /* See if the assignment kills REF. */
2344 base2
= ao_ref_base (&lhs_ref
);
2345 if (!lhs_ref
.max_size_known_p ()
2347 && (TREE_CODE (base
) != MEM_REF
2348 || TREE_CODE (base2
) != MEM_REF
2349 || TREE_OPERAND (base
, 0) != TREE_OPERAND (base2
, 0)
2350 || !tree_int_cst_equal (TREE_OPERAND (base
, 1),
2351 TREE_OPERAND (base2
, 1))))
2352 || !stmt_kills_ref_p (def_stmt
, ref
))
2355 /* Find the common base of ref and the lhs. lhs_ops already
2356 contains valueized operands for the lhs. */
2357 i
= vr
->operands
.length () - 1;
2358 j
= lhs_ops
.length () - 1;
2359 while (j
>= 0 && i
>= 0
2360 && vn_reference_op_eq (&vr
->operands
[i
], &lhs_ops
[j
]))
2366 /* ??? The innermost op should always be a MEM_REF and we already
2367 checked that the assignment to the lhs kills vr. Thus for
2368 aggregate copies using char[] types the vn_reference_op_eq
2369 may fail when comparing types for compatibility. But we really
2370 don't care here - further lookups with the rewritten operands
2371 will simply fail if we messed up types too badly. */
2372 poly_int64 extra_off
= 0;
2373 if (j
== 0 && i
>= 0
2374 && lhs_ops
[0].opcode
== MEM_REF
2375 && maybe_ne (lhs_ops
[0].off
, -1))
2377 if (known_eq (lhs_ops
[0].off
, vr
->operands
[i
].off
))
2379 else if (vr
->operands
[i
].opcode
== MEM_REF
2380 && maybe_ne (vr
->operands
[i
].off
, -1))
2382 extra_off
= vr
->operands
[i
].off
- lhs_ops
[0].off
;
2387 /* i now points to the first additional op.
2388 ??? LHS may not be completely contained in VR, one or more
2389 VIEW_CONVERT_EXPRs could be in its way. We could at least
2390 try handling outermost VIEW_CONVERT_EXPRs. */
2394 /* Punt if the additional ops contain a storage order barrier. */
2395 for (k
= i
; k
>= 0; k
--)
2397 vro
= &vr
->operands
[k
];
2398 if (vro
->opcode
== VIEW_CONVERT_EXPR
&& vro
->reverse
)
2402 /* Now re-write REF to be based on the rhs of the assignment. */
2403 copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt
), &rhs
);
2405 /* Apply an extra offset to the inner MEM_REF of the RHS. */
2406 if (maybe_ne (extra_off
, 0))
2408 if (rhs
.length () < 2)
2410 int ix
= rhs
.length () - 2;
2411 if (rhs
[ix
].opcode
!= MEM_REF
2412 || known_eq (rhs
[ix
].off
, -1))
2414 rhs
[ix
].off
+= extra_off
;
2415 rhs
[ix
].op0
= int_const_binop (PLUS_EXPR
, rhs
[ix
].op0
,
2416 build_int_cst (TREE_TYPE (rhs
[ix
].op0
),
2420 /* We need to pre-pend vr->operands[0..i] to rhs. */
2421 vec
<vn_reference_op_s
> old
= vr
->operands
;
2422 if (i
+ 1 + rhs
.length () > vr
->operands
.length ())
2423 vr
->operands
.safe_grow (i
+ 1 + rhs
.length ());
2425 vr
->operands
.truncate (i
+ 1 + rhs
.length ());
2426 FOR_EACH_VEC_ELT (rhs
, j
, vro
)
2427 vr
->operands
[i
+ 1 + j
] = *vro
;
2428 vr
->operands
= valueize_refs (vr
->operands
);
2429 if (old
== shared_lookup_references
)
2430 shared_lookup_references
= vr
->operands
;
2431 vr
->hashcode
= vn_reference_compute_hash (vr
);
2433 /* Try folding the new reference to a constant. */
2434 tree val
= fully_constant_vn_reference_p (vr
);
2436 return vn_reference_lookup_or_insert_for_pieces
2437 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
2439 /* Adjust *ref from the new operands. */
2440 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
2442 /* This can happen with bitfields. */
2443 if (maybe_ne (ref
->size
, r
.size
))
2447 /* Do not update last seen VUSE after translating. */
2448 last_vuse_ptr
= NULL
;
2450 /* Keep looking for the adjusted *REF / VR pair. */
2454 /* 6) For memcpy copies translate the reference through them if
2455 the copy kills ref. */
2456 else if (vn_walk_kind
== VN_WALKREWRITE
2457 && is_gimple_reg_type (vr
->type
)
2458 /* ??? Handle BCOPY as well. */
2459 && (gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMCPY
)
2460 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMPCPY
)
2461 || gimple_call_builtin_p (def_stmt
, BUILT_IN_MEMMOVE
))
2462 && (TREE_CODE (gimple_call_arg (def_stmt
, 0)) == ADDR_EXPR
2463 || TREE_CODE (gimple_call_arg (def_stmt
, 0)) == SSA_NAME
)
2464 && (TREE_CODE (gimple_call_arg (def_stmt
, 1)) == ADDR_EXPR
2465 || TREE_CODE (gimple_call_arg (def_stmt
, 1)) == SSA_NAME
)
2466 && poly_int_tree_p (gimple_call_arg (def_stmt
, 2), ©_size
))
2470 poly_int64 rhs_offset
, lhs_offset
;
2471 vn_reference_op_s op
;
2472 poly_uint64 mem_offset
;
2473 poly_int64 at
, byte_maxsize
;
2475 /* Only handle non-variable, addressable refs. */
2476 if (maybe_ne (ref
->size
, maxsize
)
2477 || !multiple_p (offset
, BITS_PER_UNIT
, &at
)
2478 || !multiple_p (maxsize
, BITS_PER_UNIT
, &byte_maxsize
))
2481 /* Extract a pointer base and an offset for the destination. */
2482 lhs
= gimple_call_arg (def_stmt
, 0);
2484 if (TREE_CODE (lhs
) == SSA_NAME
)
2486 lhs
= vn_valueize (lhs
);
2487 if (TREE_CODE (lhs
) == SSA_NAME
)
2489 gimple
*def_stmt
= SSA_NAME_DEF_STMT (lhs
);
2490 if (gimple_assign_single_p (def_stmt
)
2491 && gimple_assign_rhs_code (def_stmt
) == ADDR_EXPR
)
2492 lhs
= gimple_assign_rhs1 (def_stmt
);
2495 if (TREE_CODE (lhs
) == ADDR_EXPR
)
2497 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (lhs
, 0),
2501 if (TREE_CODE (tem
) == MEM_REF
2502 && poly_int_tree_p (TREE_OPERAND (tem
, 1), &mem_offset
))
2504 lhs
= TREE_OPERAND (tem
, 0);
2505 if (TREE_CODE (lhs
) == SSA_NAME
)
2506 lhs
= vn_valueize (lhs
);
2507 lhs_offset
+= mem_offset
;
2509 else if (DECL_P (tem
))
2510 lhs
= build_fold_addr_expr (tem
);
2514 if (TREE_CODE (lhs
) != SSA_NAME
2515 && TREE_CODE (lhs
) != ADDR_EXPR
)
2518 /* Extract a pointer base and an offset for the source. */
2519 rhs
= gimple_call_arg (def_stmt
, 1);
2521 if (TREE_CODE (rhs
) == SSA_NAME
)
2522 rhs
= vn_valueize (rhs
);
2523 if (TREE_CODE (rhs
) == ADDR_EXPR
)
2525 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs
, 0),
2529 if (TREE_CODE (tem
) == MEM_REF
2530 && poly_int_tree_p (TREE_OPERAND (tem
, 1), &mem_offset
))
2532 rhs
= TREE_OPERAND (tem
, 0);
2533 rhs_offset
+= mem_offset
;
2535 else if (DECL_P (tem
)
2536 || TREE_CODE (tem
) == STRING_CST
)
2537 rhs
= build_fold_addr_expr (tem
);
2541 if (TREE_CODE (rhs
) != SSA_NAME
2542 && TREE_CODE (rhs
) != ADDR_EXPR
)
2545 /* The bases of the destination and the references have to agree. */
2546 if (TREE_CODE (base
) == MEM_REF
)
2548 if (TREE_OPERAND (base
, 0) != lhs
2549 || !poly_int_tree_p (TREE_OPERAND (base
, 1), &mem_offset
))
2553 else if (!DECL_P (base
)
2554 || TREE_CODE (lhs
) != ADDR_EXPR
2555 || TREE_OPERAND (lhs
, 0) != base
)
2558 /* If the access is completely outside of the memcpy destination
2559 area there is no aliasing. */
2560 if (!ranges_maybe_overlap_p (lhs_offset
, copy_size
, at
, byte_maxsize
))
2562 /* And the access has to be contained within the memcpy destination. */
2563 if (!known_subrange_p (at
, byte_maxsize
, lhs_offset
, copy_size
))
2566 /* Make room for 2 operands in the new reference. */
2567 if (vr
->operands
.length () < 2)
2569 vec
<vn_reference_op_s
> old
= vr
->operands
;
2570 vr
->operands
.safe_grow_cleared (2);
2571 if (old
== shared_lookup_references
)
2572 shared_lookup_references
= vr
->operands
;
2575 vr
->operands
.truncate (2);
2577 /* The looked-through reference is a simple MEM_REF. */
2578 memset (&op
, 0, sizeof (op
));
2580 op
.opcode
= MEM_REF
;
2581 op
.op0
= build_int_cst (ptr_type_node
, at
- lhs_offset
+ rhs_offset
);
2582 op
.off
= at
- lhs_offset
+ rhs_offset
;
2583 vr
->operands
[0] = op
;
2584 op
.type
= TREE_TYPE (rhs
);
2585 op
.opcode
= TREE_CODE (rhs
);
2588 vr
->operands
[1] = op
;
2589 vr
->hashcode
= vn_reference_compute_hash (vr
);
2591 /* Try folding the new reference to a constant. */
2592 tree val
= fully_constant_vn_reference_p (vr
);
2594 return vn_reference_lookup_or_insert_for_pieces
2595 (vuse
, vr
->set
, vr
->type
, vr
->operands
, val
);
2597 /* Adjust *ref from the new operands. */
2598 if (!ao_ref_init_from_vn_reference (&r
, vr
->set
, vr
->type
, vr
->operands
))
2600 /* This can happen with bitfields. */
2601 if (maybe_ne (ref
->size
, r
.size
))
2605 /* Do not update last seen VUSE after translating. */
2606 last_vuse_ptr
= NULL
;
2608 /* Keep looking for the adjusted *REF / VR pair. */
2612 /* Bail out and stop walking. */
2616 /* Return a reference op vector from OP that can be used for
2617 vn_reference_lookup_pieces. The caller is responsible for releasing
2620 vec
<vn_reference_op_s
>
2621 vn_reference_operands_for_lookup (tree op
)
2624 return valueize_shared_reference_ops_from_ref (op
, &valueized
).copy ();
2627 /* Lookup a reference operation by it's parts, in the current hash table.
2628 Returns the resulting value number if it exists in the hash table,
2629 NULL_TREE otherwise. VNRESULT will be filled in with the actual
2630 vn_reference_t stored in the hashtable if something is found. */
2633 vn_reference_lookup_pieces (tree vuse
, alias_set_type set
, tree type
,
2634 vec
<vn_reference_op_s
> operands
,
2635 vn_reference_t
*vnresult
, vn_lookup_kind kind
)
2637 struct vn_reference_s vr1
;
2645 vr1
.vuse
= vuse_ssa_val (vuse
);
2646 shared_lookup_references
.truncate (0);
2647 shared_lookup_references
.safe_grow (operands
.length ());
2648 memcpy (shared_lookup_references
.address (),
2649 operands
.address (),
2650 sizeof (vn_reference_op_s
)
2651 * operands
.length ());
2652 vr1
.operands
= operands
= shared_lookup_references
2653 = valueize_refs (shared_lookup_references
);
2656 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2657 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2660 vn_reference_lookup_1 (&vr1
, vnresult
);
2662 && kind
!= VN_NOWALK
2666 unsigned limit
= PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS
);
2667 vn_walk_kind
= kind
;
2668 if (ao_ref_init_from_vn_reference (&r
, set
, type
, vr1
.operands
))
2670 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2671 vn_reference_lookup_2
,
2672 vn_reference_lookup_3
,
2673 vuse_valueize
, limit
, &vr1
);
2674 gcc_checking_assert (vr1
.operands
== shared_lookup_references
);
2678 return (*vnresult
)->result
;
2683 /* Lookup OP in the current hash table, and return the resulting value
2684 number if it exists in the hash table. Return NULL_TREE if it does
2685 not exist in the hash table or if the result field of the structure
2686 was NULL.. VNRESULT will be filled in with the vn_reference_t
2687 stored in the hashtable if one exists. When TBAA_P is false assume
2688 we are looking up a store and treat it as having alias-set zero. */
2691 vn_reference_lookup (tree op
, tree vuse
, vn_lookup_kind kind
,
2692 vn_reference_t
*vnresult
, bool tbaa_p
)
2694 vec
<vn_reference_op_s
> operands
;
2695 struct vn_reference_s vr1
;
2697 bool valuezied_anything
;
2702 vr1
.vuse
= vuse_ssa_val (vuse
);
2703 vr1
.operands
= operands
2704 = valueize_shared_reference_ops_from_ref (op
, &valuezied_anything
);
2705 vr1
.type
= TREE_TYPE (op
);
2706 vr1
.set
= tbaa_p
? get_alias_set (op
) : 0;
2707 vr1
.hashcode
= vn_reference_compute_hash (&vr1
);
2708 if ((cst
= fully_constant_vn_reference_p (&vr1
)))
2711 if (kind
!= VN_NOWALK
2714 vn_reference_t wvnresult
;
2716 unsigned limit
= PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS
);
2717 /* Make sure to use a valueized reference if we valueized anything.
2718 Otherwise preserve the full reference for advanced TBAA. */
2719 if (!valuezied_anything
2720 || !ao_ref_init_from_vn_reference (&r
, vr1
.set
, vr1
.type
,
2722 ao_ref_init (&r
, op
);
2724 r
.ref_alias_set
= r
.base_alias_set
= 0;
2725 vn_walk_kind
= kind
;
2727 (vn_reference_t
)walk_non_aliased_vuses (&r
, vr1
.vuse
,
2728 vn_reference_lookup_2
,
2729 vn_reference_lookup_3
,
2730 vuse_valueize
, limit
, &vr1
);
2731 gcc_checking_assert (vr1
.operands
== shared_lookup_references
);
2735 *vnresult
= wvnresult
;
2736 return wvnresult
->result
;
2742 return vn_reference_lookup_1 (&vr1
, vnresult
);
2745 /* Lookup CALL in the current hash table and return the entry in
2746 *VNRESULT if found. Populates *VR for the hashtable lookup. */
2749 vn_reference_lookup_call (gcall
*call
, vn_reference_t
*vnresult
,
2755 tree vuse
= gimple_vuse (call
);
2757 vr
->vuse
= vuse
? SSA_VAL (vuse
) : NULL_TREE
;
2758 vr
->operands
= valueize_shared_reference_ops_from_call (call
);
2759 vr
->type
= gimple_expr_type (call
);
2761 vr
->hashcode
= vn_reference_compute_hash (vr
);
2762 vn_reference_lookup_1 (vr
, vnresult
);
2765 /* Insert OP into the current hash table with a value number of RESULT. */
2768 vn_reference_insert (tree op
, tree result
, tree vuse
, tree vdef
)
2770 vn_reference_s
**slot
;
2774 vr1
= XOBNEW (&vn_tables_obstack
, vn_reference_s
);
2775 if (TREE_CODE (result
) == SSA_NAME
)
2776 vr1
->value_id
= VN_INFO (result
)->value_id
;
2778 vr1
->value_id
= get_or_alloc_constant_value_id (result
);
2779 vr1
->vuse
= vuse_ssa_val (vuse
);
2780 vr1
->operands
= valueize_shared_reference_ops_from_ref (op
, &tem
).copy ();
2781 vr1
->type
= TREE_TYPE (op
);
2782 vr1
->set
= get_alias_set (op
);
2783 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2784 vr1
->result
= TREE_CODE (result
) == SSA_NAME
? SSA_VAL (result
) : result
;
2785 vr1
->result_vdef
= vdef
;
2787 slot
= valid_info
->references
->find_slot_with_hash (vr1
, vr1
->hashcode
,
2790 /* Because IL walking on reference lookup can end up visiting
2791 a def that is only to be visited later in iteration order
2792 when we are about to make an irreducible region reducible
2793 the def can be effectively processed and its ref being inserted
2794 by vn_reference_lookup_3 already. So we cannot assert (!*slot)
2795 but save a lookup if we deal with already inserted refs here. */
2798 /* We cannot assert that we have the same value either because
2799 when disentangling an irreducible region we may end up visiting
2800 a use before the corresponding def. That's a missed optimization
2801 only though. See gcc.dg/tree-ssa/pr87126.c for example. */
2802 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
2803 && !operand_equal_p ((*slot
)->result
, vr1
->result
, 0))
2805 fprintf (dump_file
, "Keeping old value ");
2806 print_generic_expr (dump_file
, (*slot
)->result
);
2807 fprintf (dump_file
, " because of collision\n");
2809 free_reference (vr1
);
2810 obstack_free (&vn_tables_obstack
, vr1
);
2815 vr1
->next
= last_inserted_ref
;
2816 last_inserted_ref
= vr1
;
2819 /* Insert a reference by it's pieces into the current hash table with
2820 a value number of RESULT. Return the resulting reference
2821 structure we created. */
2824 vn_reference_insert_pieces (tree vuse
, alias_set_type set
, tree type
,
2825 vec
<vn_reference_op_s
> operands
,
2826 tree result
, unsigned int value_id
)
2829 vn_reference_s
**slot
;
2832 vr1
= XOBNEW (&vn_tables_obstack
, vn_reference_s
);
2833 vr1
->value_id
= value_id
;
2834 vr1
->vuse
= vuse_ssa_val (vuse
);
2835 vr1
->operands
= valueize_refs (operands
);
2838 vr1
->hashcode
= vn_reference_compute_hash (vr1
);
2839 if (result
&& TREE_CODE (result
) == SSA_NAME
)
2840 result
= SSA_VAL (result
);
2841 vr1
->result
= result
;
2843 slot
= valid_info
->references
->find_slot_with_hash (vr1
, vr1
->hashcode
,
2846 /* At this point we should have all the things inserted that we have
2847 seen before, and we should never try inserting something that
2849 gcc_assert (!*slot
);
2852 vr1
->next
= last_inserted_ref
;
2853 last_inserted_ref
= vr1
;
2857 /* Compute and return the hash value for nary operation VBO1. */
2860 vn_nary_op_compute_hash (const vn_nary_op_t vno1
)
2862 inchash::hash hstate
;
2865 for (i
= 0; i
< vno1
->length
; ++i
)
2866 if (TREE_CODE (vno1
->op
[i
]) == SSA_NAME
)
2867 vno1
->op
[i
] = SSA_VAL (vno1
->op
[i
]);
2869 if (((vno1
->length
== 2
2870 && commutative_tree_code (vno1
->opcode
))
2871 || (vno1
->length
== 3
2872 && commutative_ternary_tree_code (vno1
->opcode
)))
2873 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1]))
2874 std::swap (vno1
->op
[0], vno1
->op
[1]);
2875 else if (TREE_CODE_CLASS (vno1
->opcode
) == tcc_comparison
2876 && tree_swap_operands_p (vno1
->op
[0], vno1
->op
[1]))
2878 std::swap (vno1
->op
[0], vno1
->op
[1]);
2879 vno1
->opcode
= swap_tree_comparison (vno1
->opcode
);
2882 hstate
.add_int (vno1
->opcode
);
2883 for (i
= 0; i
< vno1
->length
; ++i
)
2884 inchash::add_expr (vno1
->op
[i
], hstate
);
2886 return hstate
.end ();
2889 /* Compare nary operations VNO1 and VNO2 and return true if they are
2893 vn_nary_op_eq (const_vn_nary_op_t
const vno1
, const_vn_nary_op_t
const vno2
)
2897 if (vno1
->hashcode
!= vno2
->hashcode
)
2900 if (vno1
->length
!= vno2
->length
)
2903 if (vno1
->opcode
!= vno2
->opcode
2904 || !types_compatible_p (vno1
->type
, vno2
->type
))
2907 for (i
= 0; i
< vno1
->length
; ++i
)
2908 if (!expressions_equal_p (vno1
->op
[i
], vno2
->op
[i
]))
2911 /* BIT_INSERT_EXPR has an implict operand as the type precision
2912 of op1. Need to check to make sure they are the same. */
2913 if (vno1
->opcode
== BIT_INSERT_EXPR
2914 && TREE_CODE (vno1
->op
[1]) == INTEGER_CST
2915 && TYPE_PRECISION (TREE_TYPE (vno1
->op
[1]))
2916 != TYPE_PRECISION (TREE_TYPE (vno2
->op
[1])))
2922 /* Initialize VNO from the pieces provided. */
2925 init_vn_nary_op_from_pieces (vn_nary_op_t vno
, unsigned int length
,
2926 enum tree_code code
, tree type
, tree
*ops
)
2929 vno
->length
= length
;
2931 memcpy (&vno
->op
[0], ops
, sizeof (tree
) * length
);
2934 /* Initialize VNO from OP. */
2937 init_vn_nary_op_from_op (vn_nary_op_t vno
, tree op
)
2941 vno
->opcode
= TREE_CODE (op
);
2942 vno
->length
= TREE_CODE_LENGTH (TREE_CODE (op
));
2943 vno
->type
= TREE_TYPE (op
);
2944 for (i
= 0; i
< vno
->length
; ++i
)
2945 vno
->op
[i
] = TREE_OPERAND (op
, i
);
2948 /* Return the number of operands for a vn_nary ops structure from STMT. */
2951 vn_nary_length_from_stmt (gimple
*stmt
)
2953 switch (gimple_assign_rhs_code (stmt
))
2957 case VIEW_CONVERT_EXPR
:
2964 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2967 return gimple_num_ops (stmt
) - 1;
2971 /* Initialize VNO from STMT. */
2974 init_vn_nary_op_from_stmt (vn_nary_op_t vno
, gimple
*stmt
)
2978 vno
->opcode
= gimple_assign_rhs_code (stmt
);
2979 vno
->type
= gimple_expr_type (stmt
);
2980 switch (vno
->opcode
)
2984 case VIEW_CONVERT_EXPR
:
2986 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2991 vno
->op
[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
2992 vno
->op
[1] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1);
2993 vno
->op
[2] = TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
2997 vno
->length
= CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
2998 for (i
= 0; i
< vno
->length
; ++i
)
2999 vno
->op
[i
] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt
), i
)->value
;
3003 gcc_checking_assert (!gimple_assign_single_p (stmt
));
3004 vno
->length
= gimple_num_ops (stmt
) - 1;
3005 for (i
= 0; i
< vno
->length
; ++i
)
3006 vno
->op
[i
] = gimple_op (stmt
, i
+ 1);
3010 /* Compute the hashcode for VNO and look for it in the hash table;
3011 return the resulting value number if it exists in the hash table.
3012 Return NULL_TREE if it does not exist in the hash table or if the
3013 result field of the operation is NULL. VNRESULT will contain the
3014 vn_nary_op_t from the hashtable if it exists. */
3017 vn_nary_op_lookup_1 (vn_nary_op_t vno
, vn_nary_op_t
*vnresult
)
3019 vn_nary_op_s
**slot
;
3024 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
3025 slot
= valid_info
->nary
->find_slot_with_hash (vno
, vno
->hashcode
, NO_INSERT
);
3030 return (*slot
)->predicated_values
? NULL_TREE
: (*slot
)->u
.result
;
3033 /* Lookup a n-ary operation by its pieces and return the resulting value
3034 number if it exists in the hash table. Return NULL_TREE if it does
3035 not exist in the hash table or if the result field of the operation
3036 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
3040 vn_nary_op_lookup_pieces (unsigned int length
, enum tree_code code
,
3041 tree type
, tree
*ops
, vn_nary_op_t
*vnresult
)
3043 vn_nary_op_t vno1
= XALLOCAVAR (struct vn_nary_op_s
,
3044 sizeof_vn_nary_op (length
));
3045 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
3046 return vn_nary_op_lookup_1 (vno1
, vnresult
);
3049 /* Lookup OP in the current hash table, and return the resulting value
3050 number if it exists in the hash table. Return NULL_TREE if it does
3051 not exist in the hash table or if the result field of the operation
3052 is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
3056 vn_nary_op_lookup (tree op
, vn_nary_op_t
*vnresult
)
3059 = XALLOCAVAR (struct vn_nary_op_s
,
3060 sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op
))));
3061 init_vn_nary_op_from_op (vno1
, op
);
3062 return vn_nary_op_lookup_1 (vno1
, vnresult
);
3065 /* Lookup the rhs of STMT in the current hash table, and return the resulting
3066 value number if it exists in the hash table. Return NULL_TREE if
3067 it does not exist in the hash table. VNRESULT will contain the
3068 vn_nary_op_t from the hashtable if it exists. */
3071 vn_nary_op_lookup_stmt (gimple
*stmt
, vn_nary_op_t
*vnresult
)
3074 = XALLOCAVAR (struct vn_nary_op_s
,
3075 sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt
)));
3076 init_vn_nary_op_from_stmt (vno1
, stmt
);
3077 return vn_nary_op_lookup_1 (vno1
, vnresult
);
3080 /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */
3083 alloc_vn_nary_op_noinit (unsigned int length
, struct obstack
*stack
)
3085 return (vn_nary_op_t
) obstack_alloc (stack
, sizeof_vn_nary_op (length
));
3088 /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's
3092 alloc_vn_nary_op (unsigned int length
, tree result
, unsigned int value_id
)
3094 vn_nary_op_t vno1
= alloc_vn_nary_op_noinit (length
, &vn_tables_obstack
);
3096 vno1
->value_id
= value_id
;
3097 vno1
->length
= length
;
3098 vno1
->predicated_values
= 0;
3099 vno1
->u
.result
= result
;
3104 /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute
3105 VNO->HASHCODE first. */
3108 vn_nary_op_insert_into (vn_nary_op_t vno
, vn_nary_op_table_type
*table
,
3111 vn_nary_op_s
**slot
;
3115 vno
->hashcode
= vn_nary_op_compute_hash (vno
);
3116 gcc_assert (! vno
->predicated_values
3117 || (! vno
->u
.values
->next
3118 && vno
->u
.values
->n
== 1));
3121 slot
= table
->find_slot_with_hash (vno
, vno
->hashcode
, INSERT
);
3122 vno
->unwind_to
= *slot
;
3125 /* Prefer non-predicated values.
3126 ??? Only if those are constant, otherwise, with constant predicated
3127 value, turn them into predicated values with entry-block validity
3128 (??? but we always find the first valid result currently). */
3129 if ((*slot
)->predicated_values
3130 && ! vno
->predicated_values
)
3132 /* ??? We cannot remove *slot from the unwind stack list.
3133 For the moment we deal with this by skipping not found
3134 entries but this isn't ideal ... */
3136 /* ??? Maintain a stack of states we can unwind in
3137 vn_nary_op_s? But how far do we unwind? In reality
3138 we need to push change records somewhere... Or not
3139 unwind vn_nary_op_s and linking them but instead
3140 unwind the results "list", linking that, which also
3141 doesn't move on hashtable resize. */
3142 /* We can also have a ->unwind_to recording *slot there.
3143 That way we can make u.values a fixed size array with
3144 recording the number of entries but of course we then
3145 have always N copies for each unwind_to-state. Or we
3146 make sure to only ever append and each unwinding will
3147 pop off one entry (but how to deal with predicated
3148 replaced with non-predicated here?) */
3149 vno
->next
= last_inserted_nary
;
3150 last_inserted_nary
= vno
;
3153 else if (vno
->predicated_values
3154 && ! (*slot
)->predicated_values
)
3156 else if (vno
->predicated_values
3157 && (*slot
)->predicated_values
)
3159 /* ??? Factor this all into a insert_single_predicated_value
3161 gcc_assert (!vno
->u
.values
->next
&& vno
->u
.values
->n
== 1);
3163 = BASIC_BLOCK_FOR_FN (cfun
, vno
->u
.values
->valid_dominated_by_p
[0]);
3164 vn_pval
*nval
= vno
->u
.values
;
3165 vn_pval
**next
= &vno
->u
.values
;
3167 for (vn_pval
*val
= (*slot
)->u
.values
; val
; val
= val
->next
)
3169 if (expressions_equal_p (val
->result
, vno
->u
.values
->result
))
3172 for (unsigned i
= 0; i
< val
->n
; ++i
)
3175 = BASIC_BLOCK_FOR_FN (cfun
,
3176 val
->valid_dominated_by_p
[i
]);
3177 if (dominated_by_p (CDI_DOMINATORS
, vno_bb
, val_bb
))
3178 /* Value registered with more generic predicate. */
3180 else if (dominated_by_p (CDI_DOMINATORS
, val_bb
, vno_bb
))
3181 /* Shouldn't happen, we insert in RPO order. */
3185 *next
= (vn_pval
*) obstack_alloc (&vn_tables_obstack
,
3187 + val
->n
* sizeof (int));
3188 (*next
)->next
= NULL
;
3189 (*next
)->result
= val
->result
;
3190 (*next
)->n
= val
->n
+ 1;
3191 memcpy ((*next
)->valid_dominated_by_p
,
3192 val
->valid_dominated_by_p
,
3193 val
->n
* sizeof (int));
3194 (*next
)->valid_dominated_by_p
[val
->n
] = vno_bb
->index
;
3195 next
= &(*next
)->next
;
3196 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3197 fprintf (dump_file
, "Appending predicate to value.\n");
3200 /* Copy other predicated values. */
3201 *next
= (vn_pval
*) obstack_alloc (&vn_tables_obstack
,
3203 + (val
->n
-1) * sizeof (int));
3204 memcpy (*next
, val
, sizeof (vn_pval
) + (val
->n
-1) * sizeof (int));
3205 (*next
)->next
= NULL
;
3206 next
= &(*next
)->next
;
3212 vno
->next
= last_inserted_nary
;
3213 last_inserted_nary
= vno
;
3217 /* While we do not want to insert things twice it's awkward to
3218 avoid it in the case where visit_nary_op pattern-matches stuff
3219 and ends up simplifying the replacement to itself. We then
3220 get two inserts, one from visit_nary_op and one from
3221 vn_nary_build_or_lookup.
3222 So allow inserts with the same value number. */
3223 if ((*slot
)->u
.result
== vno
->u
.result
)
3227 /* ??? There's also optimistic vs. previous commited state merging
3228 that is problematic for the case of unwinding. */
3230 /* ??? We should return NULL if we do not use 'vno' and have the
3231 caller release it. */
3232 gcc_assert (!*slot
);
3235 vno
->next
= last_inserted_nary
;
3236 last_inserted_nary
= vno
;
3240 /* Insert a n-ary operation into the current hash table using it's
3241 pieces. Return the vn_nary_op_t structure we created and put in
3245 vn_nary_op_insert_pieces (unsigned int length
, enum tree_code code
,
3246 tree type
, tree
*ops
,
3247 tree result
, unsigned int value_id
)
3249 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, result
, value_id
);
3250 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
3251 return vn_nary_op_insert_into (vno1
, valid_info
->nary
, true);
3255 vn_nary_op_insert_pieces_predicated (unsigned int length
, enum tree_code code
,
3256 tree type
, tree
*ops
,
3257 tree result
, unsigned int value_id
,
3260 /* ??? Currently tracking BBs. */
3261 if (! single_pred_p (pred_e
->dest
))
3263 /* Never record for backedges. */
3264 if (pred_e
->flags
& EDGE_DFS_BACK
)
3269 /* Ignore backedges. */
3270 FOR_EACH_EDGE (e
, ei
, pred_e
->dest
->preds
)
3271 if (! dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
3276 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
3277 /* ??? Fix dumping, but currently we only get comparisons. */
3278 && TREE_CODE_CLASS (code
) == tcc_comparison
)
3280 fprintf (dump_file
, "Recording on edge %d->%d ", pred_e
->src
->index
,
3281 pred_e
->dest
->index
);
3282 print_generic_expr (dump_file
, ops
[0], TDF_SLIM
);
3283 fprintf (dump_file
, " %s ", get_tree_code_name (code
));
3284 print_generic_expr (dump_file
, ops
[1], TDF_SLIM
);
3285 fprintf (dump_file
, " == %s\n",
3286 integer_zerop (result
) ? "false" : "true");
3288 vn_nary_op_t vno1
= alloc_vn_nary_op (length
, NULL_TREE
, value_id
);
3289 init_vn_nary_op_from_pieces (vno1
, length
, code
, type
, ops
);
3290 vno1
->predicated_values
= 1;
3291 vno1
->u
.values
= (vn_pval
*) obstack_alloc (&vn_tables_obstack
,
3293 vno1
->u
.values
->next
= NULL
;
3294 vno1
->u
.values
->result
= result
;
3295 vno1
->u
.values
->n
= 1;
3296 vno1
->u
.values
->valid_dominated_by_p
[0] = pred_e
->dest
->index
;
3297 return vn_nary_op_insert_into (vno1
, valid_info
->nary
, true);
3301 dominated_by_p_w_unex (basic_block bb1
, basic_block bb2
);
3304 vn_nary_op_get_predicated_value (vn_nary_op_t vno
, basic_block bb
)
3306 if (! vno
->predicated_values
)
3307 return vno
->u
.result
;
3308 for (vn_pval
*val
= vno
->u
.values
; val
; val
= val
->next
)
3309 for (unsigned i
= 0; i
< val
->n
; ++i
)
3310 if (dominated_by_p_w_unex (bb
,
3312 (cfun
, val
->valid_dominated_by_p
[i
])))
3317 /* Insert OP into the current hash table with a value number of
3318 RESULT. Return the vn_nary_op_t structure we created and put in
3322 vn_nary_op_insert (tree op
, tree result
)
3324 unsigned length
= TREE_CODE_LENGTH (TREE_CODE (op
));
3327 vno1
= alloc_vn_nary_op (length
, result
, VN_INFO (result
)->value_id
);
3328 init_vn_nary_op_from_op (vno1
, op
);
3329 return vn_nary_op_insert_into (vno1
, valid_info
->nary
, true);
3332 /* Insert the rhs of STMT into the current hash table with a value number of
3336 vn_nary_op_insert_stmt (gimple
*stmt
, tree result
)
3339 = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt
),
3340 result
, VN_INFO (result
)->value_id
);
3341 init_vn_nary_op_from_stmt (vno1
, stmt
);
3342 return vn_nary_op_insert_into (vno1
, valid_info
->nary
, true);
3345 /* Compute a hashcode for PHI operation VP1 and return it. */
3347 static inline hashval_t
3348 vn_phi_compute_hash (vn_phi_t vp1
)
3350 inchash::hash
hstate (EDGE_COUNT (vp1
->block
->preds
) > 2
3351 ? vp1
->block
->index
: EDGE_COUNT (vp1
->block
->preds
));
3357 /* If all PHI arguments are constants we need to distinguish
3358 the PHI node via its type. */
3360 hstate
.merge_hash (vn_hash_type (type
));
3362 FOR_EACH_EDGE (e
, ei
, vp1
->block
->preds
)
3364 /* Don't hash backedge values they need to be handled as VN_TOP
3365 for optimistic value-numbering. */
3366 if (e
->flags
& EDGE_DFS_BACK
)
3369 phi1op
= vp1
->phiargs
[e
->dest_idx
];
3370 if (phi1op
== VN_TOP
)
3372 inchash::add_expr (phi1op
, hstate
);
3375 return hstate
.end ();
3379 /* Return true if COND1 and COND2 represent the same condition, set
3380 *INVERTED_P if one needs to be inverted to make it the same as
3384 cond_stmts_equal_p (gcond
*cond1
, tree lhs1
, tree rhs1
,
3385 gcond
*cond2
, tree lhs2
, tree rhs2
, bool *inverted_p
)
3387 enum tree_code code1
= gimple_cond_code (cond1
);
3388 enum tree_code code2
= gimple_cond_code (cond2
);
3390 *inverted_p
= false;
3393 else if (code1
== swap_tree_comparison (code2
))
3394 std::swap (lhs2
, rhs2
);
3395 else if (code1
== invert_tree_comparison (code2
, HONOR_NANS (lhs2
)))
3397 else if (code1
== invert_tree_comparison
3398 (swap_tree_comparison (code2
), HONOR_NANS (lhs2
)))
3400 std::swap (lhs2
, rhs2
);
3406 return ((expressions_equal_p (lhs1
, lhs2
)
3407 && expressions_equal_p (rhs1
, rhs2
))
3408 || (commutative_tree_code (code1
)
3409 && expressions_equal_p (lhs1
, rhs2
)
3410 && expressions_equal_p (rhs1
, lhs2
)));
3413 /* Compare two phi entries for equality, ignoring VN_TOP arguments. */
3416 vn_phi_eq (const_vn_phi_t
const vp1
, const_vn_phi_t
const vp2
)
3418 if (vp1
->hashcode
!= vp2
->hashcode
)
3421 if (vp1
->block
!= vp2
->block
)
3423 if (EDGE_COUNT (vp1
->block
->preds
) != EDGE_COUNT (vp2
->block
->preds
))
3426 switch (EDGE_COUNT (vp1
->block
->preds
))
3429 /* Single-arg PHIs are just copies. */
3434 /* Rule out backedges into the PHI. */
3435 if (vp1
->block
->loop_father
->header
== vp1
->block
3436 || vp2
->block
->loop_father
->header
== vp2
->block
)
3439 /* If the PHI nodes do not have compatible types
3440 they are not the same. */
3441 if (!types_compatible_p (vp1
->type
, vp2
->type
))
3445 = get_immediate_dominator (CDI_DOMINATORS
, vp1
->block
);
3447 = get_immediate_dominator (CDI_DOMINATORS
, vp2
->block
);
3448 /* If the immediate dominator end in switch stmts multiple
3449 values may end up in the same PHI arg via intermediate
3451 if (EDGE_COUNT (idom1
->succs
) != 2
3452 || EDGE_COUNT (idom2
->succs
) != 2)
3455 /* Verify the controlling stmt is the same. */
3456 gcond
*last1
= safe_dyn_cast
<gcond
*> (last_stmt (idom1
));
3457 gcond
*last2
= safe_dyn_cast
<gcond
*> (last_stmt (idom2
));
3458 if (! last1
|| ! last2
)
3461 if (! cond_stmts_equal_p (last1
, vp1
->cclhs
, vp1
->ccrhs
,
3462 last2
, vp2
->cclhs
, vp2
->ccrhs
,
3466 /* Get at true/false controlled edges into the PHI. */
3467 edge te1
, te2
, fe1
, fe2
;
3468 if (! extract_true_false_controlled_edges (idom1
, vp1
->block
,
3470 || ! extract_true_false_controlled_edges (idom2
, vp2
->block
,
3474 /* Swap edges if the second condition is the inverted of the
3477 std::swap (te2
, fe2
);
3479 /* ??? Handle VN_TOP specially. */
3480 if (! expressions_equal_p (vp1
->phiargs
[te1
->dest_idx
],
3481 vp2
->phiargs
[te2
->dest_idx
])
3482 || ! expressions_equal_p (vp1
->phiargs
[fe1
->dest_idx
],
3483 vp2
->phiargs
[fe2
->dest_idx
]))
3494 /* If the PHI nodes do not have compatible types
3495 they are not the same. */
3496 if (!types_compatible_p (vp1
->type
, vp2
->type
))
3499 /* Any phi in the same block will have it's arguments in the
3500 same edge order, because of how we store phi nodes. */
3501 for (unsigned i
= 0; i
< EDGE_COUNT (vp1
->block
->preds
); ++i
)
3503 tree phi1op
= vp1
->phiargs
[i
];
3504 tree phi2op
= vp2
->phiargs
[i
];
3505 if (phi1op
== VN_TOP
|| phi2op
== VN_TOP
)
3507 if (!expressions_equal_p (phi1op
, phi2op
))
3514 /* Lookup PHI in the current hash table, and return the resulting
3515 value number if it exists in the hash table. Return NULL_TREE if
3516 it does not exist in the hash table. */
3519 vn_phi_lookup (gimple
*phi
, bool backedges_varying_p
)
3522 struct vn_phi_s
*vp1
;
3526 vp1
= XALLOCAVAR (struct vn_phi_s
,
3527 sizeof (struct vn_phi_s
)
3528 + (gimple_phi_num_args (phi
) - 1) * sizeof (tree
));
3530 /* Canonicalize the SSA_NAME's to their value number. */
3531 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
3533 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
3534 if (TREE_CODE (def
) == SSA_NAME
3535 && (!backedges_varying_p
|| !(e
->flags
& EDGE_DFS_BACK
)))
3536 def
= SSA_VAL (def
);
3537 vp1
->phiargs
[e
->dest_idx
] = def
;
3539 vp1
->type
= TREE_TYPE (gimple_phi_result (phi
));
3540 vp1
->block
= gimple_bb (phi
);
3541 /* Extract values of the controlling condition. */
3542 vp1
->cclhs
= NULL_TREE
;
3543 vp1
->ccrhs
= NULL_TREE
;
3544 basic_block idom1
= get_immediate_dominator (CDI_DOMINATORS
, vp1
->block
);
3545 if (EDGE_COUNT (idom1
->succs
) == 2)
3546 if (gcond
*last1
= safe_dyn_cast
<gcond
*> (last_stmt (idom1
)))
3548 /* ??? We want to use SSA_VAL here. But possibly not
3550 vp1
->cclhs
= vn_valueize (gimple_cond_lhs (last1
));
3551 vp1
->ccrhs
= vn_valueize (gimple_cond_rhs (last1
));
3553 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
3554 slot
= valid_info
->phis
->find_slot_with_hash (vp1
, vp1
->hashcode
, NO_INSERT
);
3557 return (*slot
)->result
;
3560 /* Insert PHI into the current hash table with a value number of
3564 vn_phi_insert (gimple
*phi
, tree result
, bool backedges_varying_p
)
3567 vn_phi_t vp1
= (vn_phi_t
) obstack_alloc (&vn_tables_obstack
,
3569 + ((gimple_phi_num_args (phi
) - 1)
3574 /* Canonicalize the SSA_NAME's to their value number. */
3575 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
3577 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
3578 if (TREE_CODE (def
) == SSA_NAME
3579 && (!backedges_varying_p
|| !(e
->flags
& EDGE_DFS_BACK
)))
3580 def
= SSA_VAL (def
);
3581 vp1
->phiargs
[e
->dest_idx
] = def
;
3583 vp1
->value_id
= VN_INFO (result
)->value_id
;
3584 vp1
->type
= TREE_TYPE (gimple_phi_result (phi
));
3585 vp1
->block
= gimple_bb (phi
);
3586 /* Extract values of the controlling condition. */
3587 vp1
->cclhs
= NULL_TREE
;
3588 vp1
->ccrhs
= NULL_TREE
;
3589 basic_block idom1
= get_immediate_dominator (CDI_DOMINATORS
, vp1
->block
);
3590 if (EDGE_COUNT (idom1
->succs
) == 2)
3591 if (gcond
*last1
= safe_dyn_cast
<gcond
*> (last_stmt (idom1
)))
3593 /* ??? We want to use SSA_VAL here. But possibly not
3595 vp1
->cclhs
= vn_valueize (gimple_cond_lhs (last1
));
3596 vp1
->ccrhs
= vn_valueize (gimple_cond_rhs (last1
));
3598 vp1
->result
= result
;
3599 vp1
->hashcode
= vn_phi_compute_hash (vp1
);
3601 slot
= valid_info
->phis
->find_slot_with_hash (vp1
, vp1
->hashcode
, INSERT
);
3602 gcc_assert (!*slot
);
3605 vp1
->next
= last_inserted_phi
;
3606 last_inserted_phi
= vp1
;
3611 /* Return true if BB1 is dominated by BB2 taking into account edges
3612 that are not executable. */
3615 dominated_by_p_w_unex (basic_block bb1
, basic_block bb2
)
3620 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
3623 /* Before iterating we'd like to know if there exists a
3624 (executable) path from bb2 to bb1 at all, if not we can
3625 directly return false. For now simply iterate once. */
3627 /* Iterate to the single executable bb1 predecessor. */
3628 if (EDGE_COUNT (bb1
->preds
) > 1)
3631 FOR_EACH_EDGE (e
, ei
, bb1
->preds
)
3632 if (e
->flags
& EDGE_EXECUTABLE
)
3645 /* Re-do the dominance check with changed bb1. */
3646 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
3651 /* Iterate to the single executable bb2 successor. */
3653 FOR_EACH_EDGE (e
, ei
, bb2
->succs
)
3654 if (e
->flags
& EDGE_EXECUTABLE
)
3665 /* Verify the reached block is only reached through succe.
3666 If there is only one edge we can spare us the dominator
3667 check and iterate directly. */
3668 if (EDGE_COUNT (succe
->dest
->preds
) > 1)
3670 FOR_EACH_EDGE (e
, ei
, succe
->dest
->preds
)
3672 && (e
->flags
& EDGE_EXECUTABLE
))
3682 /* Re-do the dominance check with changed bb2. */
3683 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
3688 /* We could now iterate updating bb1 / bb2. */
3692 /* Set the value number of FROM to TO, return true if it has changed
3696 set_ssa_val_to (tree from
, tree to
)
3698 vn_ssa_aux_t from_info
= VN_INFO (from
);
3699 tree currval
= from_info
->valnum
; // SSA_VAL (from)
3700 poly_int64 toff
, coff
;
3702 /* The only thing we allow as value numbers are ssa_names
3703 and invariants. So assert that here. We don't allow VN_TOP
3704 as visiting a stmt should produce a value-number other than
3706 ??? Still VN_TOP can happen for unreachable code, so force
3707 it to varying in that case. Not all code is prepared to
3708 get VN_TOP on valueization. */
3711 /* ??? When iterating and visiting PHI <undef, backedge-value>
3712 for the first time we rightfully get VN_TOP and we need to
3713 preserve that to optimize for example gcc.dg/tree-ssa/ssa-sccvn-2.c.
3714 With SCCVN we were simply lucky we iterated the other PHI
3715 cycles first and thus visited the backedge-value DEF. */
3716 if (currval
== VN_TOP
)
3718 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3719 fprintf (dump_file
, "Forcing value number to varying on "
3720 "receiving VN_TOP\n");
3724 gcc_checking_assert (to
!= NULL_TREE
3725 && ((TREE_CODE (to
) == SSA_NAME
3726 && (to
== from
|| SSA_VAL (to
) == to
))
3727 || is_gimple_min_invariant (to
)));
3731 if (currval
== from
)
3733 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3735 fprintf (dump_file
, "Not changing value number of ");
3736 print_generic_expr (dump_file
, from
);
3737 fprintf (dump_file
, " from VARYING to ");
3738 print_generic_expr (dump_file
, to
);
3739 fprintf (dump_file
, "\n");
3743 bool curr_invariant
= is_gimple_min_invariant (currval
);
3744 bool curr_undefined
= (TREE_CODE (currval
) == SSA_NAME
3745 && ssa_undefined_value_p (currval
, false));
3746 if (currval
!= VN_TOP
3749 && is_gimple_min_invariant (to
))
3751 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3753 fprintf (dump_file
, "Forcing VARYING instead of changing "
3754 "value number of ");
3755 print_generic_expr (dump_file
, from
);
3756 fprintf (dump_file
, " from ");
3757 print_generic_expr (dump_file
, currval
);
3758 fprintf (dump_file
, " (non-constant) to ");
3759 print_generic_expr (dump_file
, to
);
3760 fprintf (dump_file
, " (constant)\n");
3764 else if (currval
!= VN_TOP
3766 && TREE_CODE (to
) == SSA_NAME
3767 && ssa_undefined_value_p (to
, false))
3769 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3771 fprintf (dump_file
, "Forcing VARYING instead of changing "
3772 "value number of ");
3773 print_generic_expr (dump_file
, from
);
3774 fprintf (dump_file
, " from ");
3775 print_generic_expr (dump_file
, currval
);
3776 fprintf (dump_file
, " (non-undefined) to ");
3777 print_generic_expr (dump_file
, to
);
3778 fprintf (dump_file
, " (undefined)\n");
3782 else if (TREE_CODE (to
) == SSA_NAME
3783 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to
))
3788 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3790 fprintf (dump_file
, "Setting value number of ");
3791 print_generic_expr (dump_file
, from
);
3792 fprintf (dump_file
, " to ");
3793 print_generic_expr (dump_file
, to
);
3797 && !operand_equal_p (currval
, to
, 0)
3798 /* Different undefined SSA names are not actually different. See
3799 PR82320 for a testcase were we'd otherwise not terminate iteration. */
3800 && !(TREE_CODE (currval
) == SSA_NAME
3801 && TREE_CODE (to
) == SSA_NAME
3802 && ssa_undefined_value_p (currval
, false)
3803 && ssa_undefined_value_p (to
, false))
3804 /* ??? For addresses involving volatile objects or types operand_equal_p
3805 does not reliably detect ADDR_EXPRs as equal. We know we are only
3806 getting invariant gimple addresses here, so can use
3807 get_addr_base_and_unit_offset to do this comparison. */
3808 && !(TREE_CODE (currval
) == ADDR_EXPR
3809 && TREE_CODE (to
) == ADDR_EXPR
3810 && (get_addr_base_and_unit_offset (TREE_OPERAND (currval
, 0), &coff
)
3811 == get_addr_base_and_unit_offset (TREE_OPERAND (to
, 0), &toff
))
3812 && known_eq (coff
, toff
)))
3814 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3815 fprintf (dump_file
, " (changed)\n");
3816 from_info
->valnum
= to
;
3819 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3820 fprintf (dump_file
, "\n");
3824 /* Set all definitions in STMT to value number to themselves.
3825 Return true if a value number changed. */
3828 defs_to_varying (gimple
*stmt
)
3830 bool changed
= false;
3834 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_ALL_DEFS
)
3836 tree def
= DEF_FROM_PTR (defp
);
3837 changed
|= set_ssa_val_to (def
, def
);
3842 /* Visit a copy between LHS and RHS, return true if the value number
3846 visit_copy (tree lhs
, tree rhs
)
3849 rhs
= SSA_VAL (rhs
);
3851 return set_ssa_val_to (lhs
, rhs
);
3854 /* Lookup a value for OP in type WIDE_TYPE where the value in type of OP
3858 valueized_wider_op (tree wide_type
, tree op
)
3860 if (TREE_CODE (op
) == SSA_NAME
)
3861 op
= vn_valueize (op
);
3863 /* Either we have the op widened available. */
3866 tree tem
= vn_nary_op_lookup_pieces (1, NOP_EXPR
,
3867 wide_type
, ops
, NULL
);
3871 /* Or the op is truncated from some existing value. */
3872 if (TREE_CODE (op
) == SSA_NAME
)
3874 gimple
*def
= SSA_NAME_DEF_STMT (op
);
3875 if (is_gimple_assign (def
)
3876 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def
)))
3878 tem
= gimple_assign_rhs1 (def
);
3879 if (useless_type_conversion_p (wide_type
, TREE_TYPE (tem
)))
3881 if (TREE_CODE (tem
) == SSA_NAME
)
3882 tem
= vn_valueize (tem
);
3888 /* For constants simply extend it. */
3889 if (TREE_CODE (op
) == INTEGER_CST
)
3890 return wide_int_to_tree (wide_type
, wi::to_wide (op
));
3895 /* Visit a nary operator RHS, value number it, and return true if the
3896 value number of LHS has changed as a result. */
3899 visit_nary_op (tree lhs
, gassign
*stmt
)
3901 vn_nary_op_t vnresult
;
3902 tree result
= vn_nary_op_lookup_stmt (stmt
, &vnresult
);
3903 if (! result
&& vnresult
)
3904 result
= vn_nary_op_get_predicated_value (vnresult
, gimple_bb (stmt
));
3906 return set_ssa_val_to (lhs
, result
);
3908 /* Do some special pattern matching for redundancies of operations
3909 in different types. */
3910 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3911 tree type
= TREE_TYPE (lhs
);
3912 tree rhs1
= gimple_assign_rhs1 (stmt
);
3916 /* Match arithmetic done in a different type where we can easily
3917 substitute the result from some earlier sign-changed or widened
3919 if (INTEGRAL_TYPE_P (type
)
3920 && TREE_CODE (rhs1
) == SSA_NAME
3921 /* We only handle sign-changes or zero-extension -> & mask. */
3922 && ((TYPE_UNSIGNED (TREE_TYPE (rhs1
))
3923 && TYPE_PRECISION (type
) > TYPE_PRECISION (TREE_TYPE (rhs1
)))
3924 || TYPE_PRECISION (type
) == TYPE_PRECISION (TREE_TYPE (rhs1
))))
3926 gassign
*def
= dyn_cast
<gassign
*> (SSA_NAME_DEF_STMT (rhs1
));
3928 && (gimple_assign_rhs_code (def
) == PLUS_EXPR
3929 || gimple_assign_rhs_code (def
) == MINUS_EXPR
3930 || gimple_assign_rhs_code (def
) == MULT_EXPR
))
3933 /* Either we have the op widened available. */
3934 ops
[0] = valueized_wider_op (type
,
3935 gimple_assign_rhs1 (def
));
3937 ops
[1] = valueized_wider_op (type
,
3938 gimple_assign_rhs2 (def
));
3939 if (ops
[0] && ops
[1])
3941 ops
[0] = vn_nary_op_lookup_pieces
3942 (2, gimple_assign_rhs_code (def
), type
, ops
, NULL
);
3943 /* We have wider operation available. */
3945 /* If the leader is a wrapping operation we can
3946 insert it for code hoisting w/o introducing
3947 undefined overflow. If it is not it has to
3948 be available. See PR86554. */
3949 && (TYPE_OVERFLOW_WRAPS (TREE_TYPE (ops
[0]))
3950 || (rpo_avail
&& vn_context_bb
3951 && rpo_avail
->eliminate_avail (vn_context_bb
,
3954 unsigned lhs_prec
= TYPE_PRECISION (type
);
3955 unsigned rhs_prec
= TYPE_PRECISION (TREE_TYPE (rhs1
));
3956 if (lhs_prec
== rhs_prec
)
3958 gimple_match_op
match_op (gimple_match_cond::UNCOND
,
3959 NOP_EXPR
, type
, ops
[0]);
3960 result
= vn_nary_build_or_lookup (&match_op
);
3963 bool changed
= set_ssa_val_to (lhs
, result
);
3964 vn_nary_op_insert_stmt (stmt
, result
);
3970 tree mask
= wide_int_to_tree
3971 (type
, wi::mask (rhs_prec
, false, lhs_prec
));
3972 gimple_match_op
match_op (gimple_match_cond::UNCOND
,
3976 result
= vn_nary_build_or_lookup (&match_op
);
3979 bool changed
= set_ssa_val_to (lhs
, result
);
3980 vn_nary_op_insert_stmt (stmt
, result
);
3991 bool changed
= set_ssa_val_to (lhs
, lhs
);
3992 vn_nary_op_insert_stmt (stmt
, lhs
);
3996 /* Visit a call STMT storing into LHS. Return true if the value number
3997 of the LHS has changed as a result. */
4000 visit_reference_op_call (tree lhs
, gcall
*stmt
)
4002 bool changed
= false;
4003 struct vn_reference_s vr1
;
4004 vn_reference_t vnresult
= NULL
;
4005 tree vdef
= gimple_vdef (stmt
);
4007 /* Non-ssa lhs is handled in copy_reference_ops_from_call. */
4008 if (lhs
&& TREE_CODE (lhs
) != SSA_NAME
)
4011 vn_reference_lookup_call (stmt
, &vnresult
, &vr1
);
4014 if (vnresult
->result_vdef
&& vdef
)
4015 changed
|= set_ssa_val_to (vdef
, vnresult
->result_vdef
);
4017 /* If the call was discovered to be pure or const reflect
4018 that as far as possible. */
4019 changed
|= set_ssa_val_to (vdef
, vuse_ssa_val (gimple_vuse (stmt
)));
4021 if (!vnresult
->result
&& lhs
)
4022 vnresult
->result
= lhs
;
4024 if (vnresult
->result
&& lhs
)
4025 changed
|= set_ssa_val_to (lhs
, vnresult
->result
);
4030 vn_reference_s
**slot
;
4031 tree vdef_val
= vdef
;
4034 /* If we value numbered an indirect functions function to
4035 one not clobbering memory value number its VDEF to its
4037 tree fn
= gimple_call_fn (stmt
);
4038 if (fn
&& TREE_CODE (fn
) == SSA_NAME
)
4041 if (TREE_CODE (fn
) == ADDR_EXPR
4042 && TREE_CODE (TREE_OPERAND (fn
, 0)) == FUNCTION_DECL
4043 && (flags_from_decl_or_type (TREE_OPERAND (fn
, 0))
4044 & (ECF_CONST
| ECF_PURE
)))
4045 vdef_val
= vuse_ssa_val (gimple_vuse (stmt
));
4047 changed
|= set_ssa_val_to (vdef
, vdef_val
);
4050 changed
|= set_ssa_val_to (lhs
, lhs
);
4051 vr2
= XOBNEW (&vn_tables_obstack
, vn_reference_s
);
4052 vr2
->vuse
= vr1
.vuse
;
4053 /* As we are not walking the virtual operand chain we know the
4054 shared_lookup_references are still original so we can re-use
4056 vr2
->operands
= vr1
.operands
.copy ();
4057 vr2
->type
= vr1
.type
;
4059 vr2
->hashcode
= vr1
.hashcode
;
4061 vr2
->result_vdef
= vdef_val
;
4063 slot
= valid_info
->references
->find_slot_with_hash (vr2
, vr2
->hashcode
,
4065 gcc_assert (!*slot
);
4067 vr2
->next
= last_inserted_ref
;
4068 last_inserted_ref
= vr2
;
4074 /* Visit a load from a reference operator RHS, part of STMT, value number it,
4075 and return true if the value number of the LHS has changed as a result. */
4078 visit_reference_op_load (tree lhs
, tree op
, gimple
*stmt
)
4080 bool changed
= false;
4084 last_vuse
= gimple_vuse (stmt
);
4085 last_vuse_ptr
= &last_vuse
;
4086 result
= vn_reference_lookup (op
, gimple_vuse (stmt
),
4087 default_vn_walk_kind
, NULL
, true);
4088 last_vuse_ptr
= NULL
;
4090 /* We handle type-punning through unions by value-numbering based
4091 on offset and size of the access. Be prepared to handle a
4092 type-mismatch here via creating a VIEW_CONVERT_EXPR. */
4094 && !useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (op
)))
4096 /* We will be setting the value number of lhs to the value number
4097 of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
4098 So first simplify and lookup this expression to see if it
4099 is already available. */
4100 gimple_match_op
res_op (gimple_match_cond::UNCOND
,
4101 VIEW_CONVERT_EXPR
, TREE_TYPE (op
), result
);
4102 result
= vn_nary_build_or_lookup (&res_op
);
4103 /* When building the conversion fails avoid inserting the reference
4106 return set_ssa_val_to (lhs
, lhs
);
4110 changed
= set_ssa_val_to (lhs
, result
);
4113 changed
= set_ssa_val_to (lhs
, lhs
);
4114 vn_reference_insert (op
, lhs
, last_vuse
, NULL_TREE
);
4121 /* Visit a store to a reference operator LHS, part of STMT, value number it,
4122 and return true if the value number of the LHS has changed as a result. */
4125 visit_reference_op_store (tree lhs
, tree op
, gimple
*stmt
)
4127 bool changed
= false;
4128 vn_reference_t vnresult
= NULL
;
4130 bool resultsame
= false;
4131 tree vuse
= gimple_vuse (stmt
);
4132 tree vdef
= gimple_vdef (stmt
);
4134 if (TREE_CODE (op
) == SSA_NAME
)
4137 /* First we want to lookup using the *vuses* from the store and see
4138 if there the last store to this location with the same address
4141 The vuses represent the memory state before the store. If the
4142 memory state, address, and value of the store is the same as the
4143 last store to this location, then this store will produce the
4144 same memory state as that store.
4146 In this case the vdef versions for this store are value numbered to those
4147 vuse versions, since they represent the same memory state after
4150 Otherwise, the vdefs for the store are used when inserting into
4151 the table, since the store generates a new memory state. */
4153 vn_reference_lookup (lhs
, vuse
, VN_NOWALK
, &vnresult
, false);
4155 && vnresult
->result
)
4157 tree result
= vnresult
->result
;
4158 gcc_checking_assert (TREE_CODE (result
) != SSA_NAME
4159 || result
== SSA_VAL (result
));
4160 resultsame
= expressions_equal_p (result
, op
);
4163 /* If the TBAA state isn't compatible for downstream reads
4164 we cannot value-number the VDEFs the same. */
4165 alias_set_type set
= get_alias_set (lhs
);
4166 if (vnresult
->set
!= set
4167 && ! alias_set_subset_of (set
, vnresult
->set
))
4174 /* Only perform the following when being called from PRE
4175 which embeds tail merging. */
4176 if (default_vn_walk_kind
== VN_WALK
)
4178 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
4179 vn_reference_lookup (assign
, vuse
, VN_NOWALK
, &vnresult
, false);
4182 VN_INFO (vdef
)->visited
= true;
4183 return set_ssa_val_to (vdef
, vnresult
->result_vdef
);
4187 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4189 fprintf (dump_file
, "No store match\n");
4190 fprintf (dump_file
, "Value numbering store ");
4191 print_generic_expr (dump_file
, lhs
);
4192 fprintf (dump_file
, " to ");
4193 print_generic_expr (dump_file
, op
);
4194 fprintf (dump_file
, "\n");
4196 /* Have to set value numbers before insert, since insert is
4197 going to valueize the references in-place. */
4199 changed
|= set_ssa_val_to (vdef
, vdef
);
4201 /* Do not insert structure copies into the tables. */
4202 if (is_gimple_min_invariant (op
)
4203 || is_gimple_reg (op
))
4204 vn_reference_insert (lhs
, op
, vdef
, NULL
);
4206 /* Only perform the following when being called from PRE
4207 which embeds tail merging. */
4208 if (default_vn_walk_kind
== VN_WALK
)
4210 assign
= build2 (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, op
);
4211 vn_reference_insert (assign
, lhs
, vuse
, vdef
);
4216 /* We had a match, so value number the vdef to have the value
4217 number of the vuse it came from. */
4219 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4220 fprintf (dump_file
, "Store matched earlier value, "
4221 "value numbering store vdefs to matching vuses.\n");
4223 changed
|= set_ssa_val_to (vdef
, SSA_VAL (vuse
));
4229 /* Visit and value number PHI, return true if the value number
4230 changed. When BACKEDGES_VARYING_P is true then assume all
4231 backedge values are varying. When INSERTED is not NULL then
4232 this is just a ahead query for a possible iteration, set INSERTED
4233 to true if we'd insert into the hashtable. */
4236 visit_phi (gimple
*phi
, bool *inserted
, bool backedges_varying_p
)
4238 tree result
, sameval
= VN_TOP
, seen_undef
= NULL_TREE
;
4239 tree backedge_val
= NULL_TREE
;
4240 bool seen_non_backedge
= false;
4241 tree sameval_base
= NULL_TREE
;
4242 poly_int64 soff
, doff
;
4243 unsigned n_executable
= 0;
4247 /* TODO: We could check for this in initialization, and replace this
4248 with a gcc_assert. */
4249 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
4250 return set_ssa_val_to (PHI_RESULT (phi
), PHI_RESULT (phi
));
4252 /* We track whether a PHI was CSEd to to avoid excessive iterations
4253 that would be necessary only because the PHI changed arguments
4256 gimple_set_plf (phi
, GF_PLF_1
, false);
4258 /* See if all non-TOP arguments have the same value. TOP is
4259 equivalent to everything, so we can ignore it. */
4260 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
4261 if (e
->flags
& EDGE_EXECUTABLE
)
4263 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
4266 if (TREE_CODE (def
) == SSA_NAME
)
4268 if (!backedges_varying_p
|| !(e
->flags
& EDGE_DFS_BACK
))
4269 def
= SSA_VAL (def
);
4270 if (e
->flags
& EDGE_DFS_BACK
)
4273 if (!(e
->flags
& EDGE_DFS_BACK
))
4274 seen_non_backedge
= true;
4277 /* Ignore undefined defs for sameval but record one. */
4278 else if (TREE_CODE (def
) == SSA_NAME
4279 && ! virtual_operand_p (def
)
4280 && ssa_undefined_value_p (def
, false))
4282 else if (sameval
== VN_TOP
)
4284 else if (!expressions_equal_p (def
, sameval
))
4286 /* We know we're arriving only with invariant addresses here,
4287 try harder comparing them. We can do some caching here
4288 which we cannot do in expressions_equal_p. */
4289 if (TREE_CODE (def
) == ADDR_EXPR
4290 && TREE_CODE (sameval
) == ADDR_EXPR
4291 && sameval_base
!= (void *)-1)
4294 sameval_base
= get_addr_base_and_unit_offset
4295 (TREE_OPERAND (sameval
, 0), &soff
);
4297 sameval_base
= (tree
)(void *)-1;
4298 else if ((get_addr_base_and_unit_offset
4299 (TREE_OPERAND (def
, 0), &doff
) == sameval_base
)
4300 && known_eq (soff
, doff
))
4303 sameval
= NULL_TREE
;
4308 /* If the value we want to use is flowing over the backedge and we
4309 should take it as VARYING but it has a non-VARYING value drop to
4311 If we value-number a virtual operand never value-number to the
4312 value from the backedge as that confuses the alias-walking code.
4313 See gcc.dg/torture/pr87176.c. If the value is the same on a
4314 non-backedge everything is OK though. */
4317 && !seen_non_backedge
4318 && TREE_CODE (backedge_val
) == SSA_NAME
4319 && sameval
== backedge_val
4320 && (SSA_NAME_IS_VIRTUAL_OPERAND (backedge_val
)
4321 || SSA_VAL (backedge_val
) != backedge_val
))
4322 /* Do not value-number a virtual operand to sth not visited though
4323 given that allows us to escape a region in alias walking. */
4325 && TREE_CODE (sameval
) == SSA_NAME
4326 && !SSA_NAME_IS_DEFAULT_DEF (sameval
)
4327 && SSA_NAME_IS_VIRTUAL_OPERAND (sameval
)
4328 && (SSA_VAL (sameval
, &visited_p
), !visited_p
)))
4329 /* Note this just drops to VARYING without inserting the PHI into
4331 result
= PHI_RESULT (phi
);
4332 /* If none of the edges was executable keep the value-number at VN_TOP,
4333 if only a single edge is exectuable use its value. */
4334 else if (n_executable
<= 1)
4335 result
= seen_undef
? seen_undef
: sameval
;
4336 /* If we saw only undefined values and VN_TOP use one of the
4337 undefined values. */
4338 else if (sameval
== VN_TOP
)
4339 result
= seen_undef
? seen_undef
: sameval
;
4340 /* First see if it is equivalent to a phi node in this block. We prefer
4341 this as it allows IV elimination - see PRs 66502 and 67167. */
4342 else if ((result
= vn_phi_lookup (phi
, backedges_varying_p
)))
4345 && TREE_CODE (result
) == SSA_NAME
4346 && gimple_code (SSA_NAME_DEF_STMT (result
)) == GIMPLE_PHI
)
4348 gimple_set_plf (SSA_NAME_DEF_STMT (result
), GF_PLF_1
, true);
4349 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4351 fprintf (dump_file
, "Marking CSEd to PHI node ");
4352 print_gimple_expr (dump_file
, SSA_NAME_DEF_STMT (result
),
4354 fprintf (dump_file
, "\n");
4358 /* If all values are the same use that, unless we've seen undefined
4359 values as well and the value isn't constant.
4360 CCP/copyprop have the same restriction to not remove uninit warnings. */
4362 && (! seen_undef
|| is_gimple_min_invariant (sameval
)))
4366 result
= PHI_RESULT (phi
);
4367 /* Only insert PHIs that are varying, for constant value numbers
4368 we mess up equivalences otherwise as we are only comparing
4369 the immediate controlling predicates. */
4370 vn_phi_insert (phi
, result
, backedges_varying_p
);
4375 return set_ssa_val_to (PHI_RESULT (phi
), result
);
4378 /* Try to simplify RHS using equivalences and constant folding. */
4381 try_to_simplify (gassign
*stmt
)
4383 enum tree_code code
= gimple_assign_rhs_code (stmt
);
4386 /* For stores we can end up simplifying a SSA_NAME rhs. Just return
4387 in this case, there is no point in doing extra work. */
4388 if (code
== SSA_NAME
)
4391 /* First try constant folding based on our current lattice. */
4392 mprts_hook
= vn_lookup_simplify_result
;
4393 tem
= gimple_fold_stmt_to_constant_1 (stmt
, vn_valueize
, vn_valueize
);
4396 && (TREE_CODE (tem
) == SSA_NAME
4397 || is_gimple_min_invariant (tem
)))
4403 /* Visit and value number STMT, return true if the value number
4407 visit_stmt (gimple
*stmt
, bool backedges_varying_p
= false)
4409 bool changed
= false;
4411 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4413 fprintf (dump_file
, "Value numbering stmt = ");
4414 print_gimple_stmt (dump_file
, stmt
, 0);
4417 if (gimple_code (stmt
) == GIMPLE_PHI
)
4418 changed
= visit_phi (stmt
, NULL
, backedges_varying_p
);
4419 else if (gimple_has_volatile_ops (stmt
))
4420 changed
= defs_to_varying (stmt
);
4421 else if (gassign
*ass
= dyn_cast
<gassign
*> (stmt
))
4423 enum tree_code code
= gimple_assign_rhs_code (ass
);
4424 tree lhs
= gimple_assign_lhs (ass
);
4425 tree rhs1
= gimple_assign_rhs1 (ass
);
4428 /* Shortcut for copies. Simplifying copies is pointless,
4429 since we copy the expression and value they represent. */
4430 if (code
== SSA_NAME
4431 && TREE_CODE (lhs
) == SSA_NAME
)
4433 changed
= visit_copy (lhs
, rhs1
);
4436 simplified
= try_to_simplify (ass
);
4439 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4441 fprintf (dump_file
, "RHS ");
4442 print_gimple_expr (dump_file
, ass
, 0);
4443 fprintf (dump_file
, " simplified to ");
4444 print_generic_expr (dump_file
, simplified
);
4445 fprintf (dump_file
, "\n");
4448 /* Setting value numbers to constants will occasionally
4449 screw up phi congruence because constants are not
4450 uniquely associated with a single ssa name that can be
4453 && is_gimple_min_invariant (simplified
)
4454 && TREE_CODE (lhs
) == SSA_NAME
)
4456 changed
= set_ssa_val_to (lhs
, simplified
);
4460 && TREE_CODE (simplified
) == SSA_NAME
4461 && TREE_CODE (lhs
) == SSA_NAME
)
4463 changed
= visit_copy (lhs
, simplified
);
4467 if ((TREE_CODE (lhs
) == SSA_NAME
4468 /* We can substitute SSA_NAMEs that are live over
4469 abnormal edges with their constant value. */
4470 && !(gimple_assign_copy_p (ass
)
4471 && is_gimple_min_invariant (rhs1
))
4473 && is_gimple_min_invariant (simplified
))
4474 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
4475 /* Stores or copies from SSA_NAMEs that are live over
4476 abnormal edges are a problem. */
4477 || (code
== SSA_NAME
4478 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
)))
4479 changed
= defs_to_varying (ass
);
4480 else if (REFERENCE_CLASS_P (lhs
)
4482 changed
= visit_reference_op_store (lhs
, rhs1
, ass
);
4483 else if (TREE_CODE (lhs
) == SSA_NAME
)
4485 if ((gimple_assign_copy_p (ass
)
4486 && is_gimple_min_invariant (rhs1
))
4488 && is_gimple_min_invariant (simplified
)))
4491 changed
= set_ssa_val_to (lhs
, simplified
);
4493 changed
= set_ssa_val_to (lhs
, rhs1
);
4497 /* Visit the original statement. */
4498 switch (vn_get_stmt_kind (ass
))
4501 changed
= visit_nary_op (lhs
, ass
);
4504 changed
= visit_reference_op_load (lhs
, rhs1
, ass
);
4507 changed
= defs_to_varying (ass
);
4513 changed
= defs_to_varying (ass
);
4515 else if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
4517 tree lhs
= gimple_call_lhs (call_stmt
);
4518 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
4520 /* Try constant folding based on our current lattice. */
4521 tree simplified
= gimple_fold_stmt_to_constant_1 (call_stmt
,
4525 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4527 fprintf (dump_file
, "call ");
4528 print_gimple_expr (dump_file
, call_stmt
, 0);
4529 fprintf (dump_file
, " simplified to ");
4530 print_generic_expr (dump_file
, simplified
);
4531 fprintf (dump_file
, "\n");
4534 /* Setting value numbers to constants will occasionally
4535 screw up phi congruence because constants are not
4536 uniquely associated with a single ssa name that can be
4539 && is_gimple_min_invariant (simplified
))
4541 changed
= set_ssa_val_to (lhs
, simplified
);
4542 if (gimple_vdef (call_stmt
))
4543 changed
|= set_ssa_val_to (gimple_vdef (call_stmt
),
4544 SSA_VAL (gimple_vuse (call_stmt
)));
4548 && TREE_CODE (simplified
) == SSA_NAME
)
4550 changed
= visit_copy (lhs
, simplified
);
4551 if (gimple_vdef (call_stmt
))
4552 changed
|= set_ssa_val_to (gimple_vdef (call_stmt
),
4553 SSA_VAL (gimple_vuse (call_stmt
)));
4556 else if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
4558 changed
= defs_to_varying (call_stmt
);
4563 /* Pick up flags from a devirtualization target. */
4564 tree fn
= gimple_call_fn (stmt
);
4565 int extra_fnflags
= 0;
4566 if (fn
&& TREE_CODE (fn
) == SSA_NAME
)
4569 if (TREE_CODE (fn
) == ADDR_EXPR
4570 && TREE_CODE (TREE_OPERAND (fn
, 0)) == FUNCTION_DECL
)
4571 extra_fnflags
= flags_from_decl_or_type (TREE_OPERAND (fn
, 0));
4573 if (!gimple_call_internal_p (call_stmt
)
4574 && (/* Calls to the same function with the same vuse
4575 and the same operands do not necessarily return the same
4576 value, unless they're pure or const. */
4577 ((gimple_call_flags (call_stmt
) | extra_fnflags
)
4578 & (ECF_PURE
| ECF_CONST
))
4579 /* If calls have a vdef, subsequent calls won't have
4580 the same incoming vuse. So, if 2 calls with vdef have the
4581 same vuse, we know they're not subsequent.
4582 We can value number 2 calls to the same function with the
4583 same vuse and the same operands which are not subsequent
4584 the same, because there is no code in the program that can
4585 compare the 2 values... */
4586 || (gimple_vdef (call_stmt
)
4587 /* ... unless the call returns a pointer which does
4588 not alias with anything else. In which case the
4589 information that the values are distinct are encoded
4591 && !(gimple_call_return_flags (call_stmt
) & ERF_NOALIAS
)
4592 /* Only perform the following when being called from PRE
4593 which embeds tail merging. */
4594 && default_vn_walk_kind
== VN_WALK
)))
4595 changed
= visit_reference_op_call (lhs
, call_stmt
);
4597 changed
= defs_to_varying (call_stmt
);
4600 changed
= defs_to_varying (stmt
);
4606 /* Allocate a value number table. */
4609 allocate_vn_table (vn_tables_t table
, unsigned size
)
4611 table
->phis
= new vn_phi_table_type (size
);
4612 table
->nary
= new vn_nary_op_table_type (size
);
4613 table
->references
= new vn_reference_table_type (size
);
4616 /* Free a value number table. */
4619 free_vn_table (vn_tables_t table
)
4621 /* Walk over elements and release vectors. */
4622 vn_reference_iterator_type hir
;
4624 FOR_EACH_HASH_TABLE_ELEMENT (*table
->references
, vr
, vn_reference_t
, hir
)
4625 vr
->operands
.release ();
4630 delete table
->references
;
4631 table
->references
= NULL
;
4634 /* Set *ID according to RESULT. */
4637 set_value_id_for_result (tree result
, unsigned int *id
)
4639 if (result
&& TREE_CODE (result
) == SSA_NAME
)
4640 *id
= VN_INFO (result
)->value_id
;
4641 else if (result
&& is_gimple_min_invariant (result
))
4642 *id
= get_or_alloc_constant_value_id (result
);
4644 *id
= get_next_value_id ();
4647 /* Set the value ids in the valid hash tables. */
4650 set_hashtable_value_ids (void)
4652 vn_nary_op_iterator_type hin
;
4653 vn_phi_iterator_type hip
;
4654 vn_reference_iterator_type hir
;
4659 /* Now set the value ids of the things we had put in the hash
4662 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->nary
, vno
, vn_nary_op_t
, hin
)
4663 if (! vno
->predicated_values
)
4664 set_value_id_for_result (vno
->u
.result
, &vno
->value_id
);
4666 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->phis
, vp
, vn_phi_t
, hip
)
4667 set_value_id_for_result (vp
->result
, &vp
->value_id
);
4669 FOR_EACH_HASH_TABLE_ELEMENT (*valid_info
->references
, vr
, vn_reference_t
,
4671 set_value_id_for_result (vr
->result
, &vr
->value_id
);
4674 /* Return the maximum value id we have ever seen. */
4677 get_max_value_id (void)
4679 return next_value_id
;
4682 /* Return the next unique value id. */
4685 get_next_value_id (void)
4687 return next_value_id
++;
4691 /* Compare two expressions E1 and E2 and return true if they are equal. */
4694 expressions_equal_p (tree e1
, tree e2
)
4696 /* The obvious case. */
4700 /* If either one is VN_TOP consider them equal. */
4701 if (e1
== VN_TOP
|| e2
== VN_TOP
)
4704 /* If only one of them is null, they cannot be equal. */
4708 /* Now perform the actual comparison. */
4709 if (TREE_CODE (e1
) == TREE_CODE (e2
)
4710 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
4717 /* Return true if the nary operation NARY may trap. This is a copy
4718 of stmt_could_throw_1_p adjusted to the SCCVN IL. */
4721 vn_nary_may_trap (vn_nary_op_t nary
)
4724 tree rhs2
= NULL_TREE
;
4725 bool honor_nans
= false;
4726 bool honor_snans
= false;
4727 bool fp_operation
= false;
4728 bool honor_trapv
= false;
4732 if (TREE_CODE_CLASS (nary
->opcode
) == tcc_comparison
4733 || TREE_CODE_CLASS (nary
->opcode
) == tcc_unary
4734 || TREE_CODE_CLASS (nary
->opcode
) == tcc_binary
)
4737 fp_operation
= FLOAT_TYPE_P (type
);
4740 honor_nans
= flag_trapping_math
&& !flag_finite_math_only
;
4741 honor_snans
= flag_signaling_nans
!= 0;
4743 else if (INTEGRAL_TYPE_P (type
)
4744 && TYPE_OVERFLOW_TRAPS (type
))
4747 if (nary
->length
>= 2)
4749 ret
= operation_could_trap_helper_p (nary
->opcode
, fp_operation
,
4751 honor_nans
, honor_snans
, rhs2
,
4757 for (i
= 0; i
< nary
->length
; ++i
)
4758 if (tree_could_trap_p (nary
->op
[i
]))
4764 /* Return true if the reference operation REF may trap. */
4767 vn_reference_may_trap (vn_reference_t ref
)
4769 switch (ref
->operands
[0].opcode
)
4773 /* We do not handle calls. */
4775 /* And toplevel address computations never trap. */
4780 vn_reference_op_t op
;
4782 FOR_EACH_VEC_ELT (ref
->operands
, i
, op
)
4786 case WITH_SIZE_EXPR
:
4787 case TARGET_MEM_REF
:
4788 /* Always variable. */
4791 if (op
->op1
&& TREE_CODE (op
->op1
) == SSA_NAME
)
4794 case ARRAY_RANGE_REF
:
4796 if (TREE_CODE (op
->op0
) == SSA_NAME
)
4800 /* Nothing interesting in itself, the base is separate. */
4802 /* The following are the address bases. */
4807 return tree_could_trap_p (TREE_OPERAND (op
->op0
, 0));
4815 eliminate_dom_walker::eliminate_dom_walker (cdi_direction direction
,
4816 bitmap inserted_exprs_
)
4817 : dom_walker (direction
), do_pre (inserted_exprs_
!= NULL
),
4818 el_todo (0), eliminations (0), insertions (0),
4819 inserted_exprs (inserted_exprs_
)
4821 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
4822 need_ab_cleanup
= BITMAP_ALLOC (NULL
);
4825 eliminate_dom_walker::~eliminate_dom_walker ()
4827 BITMAP_FREE (need_eh_cleanup
);
4828 BITMAP_FREE (need_ab_cleanup
);
4831 /* Return a leader for OP that is available at the current point of the
4832 eliminate domwalk. */
4835 eliminate_dom_walker::eliminate_avail (basic_block
, tree op
)
4837 tree valnum
= VN_INFO (op
)->valnum
;
4838 if (TREE_CODE (valnum
) == SSA_NAME
)
4840 if (SSA_NAME_IS_DEFAULT_DEF (valnum
))
4842 if (avail
.length () > SSA_NAME_VERSION (valnum
))
4843 return avail
[SSA_NAME_VERSION (valnum
)];
4845 else if (is_gimple_min_invariant (valnum
))
4850 /* At the current point of the eliminate domwalk make OP available. */
4853 eliminate_dom_walker::eliminate_push_avail (basic_block
, tree op
)
4855 tree valnum
= VN_INFO (op
)->valnum
;
4856 if (TREE_CODE (valnum
) == SSA_NAME
)
4858 if (avail
.length () <= SSA_NAME_VERSION (valnum
))
4859 avail
.safe_grow_cleared (SSA_NAME_VERSION (valnum
) + 1);
4861 if (avail
[SSA_NAME_VERSION (valnum
)])
4862 pushop
= avail
[SSA_NAME_VERSION (valnum
)];
4863 avail_stack
.safe_push (pushop
);
4864 avail
[SSA_NAME_VERSION (valnum
)] = op
;
4868 /* Insert the expression recorded by SCCVN for VAL at *GSI. Returns
4869 the leader for the expression if insertion was successful. */
4872 eliminate_dom_walker::eliminate_insert (basic_block bb
,
4873 gimple_stmt_iterator
*gsi
, tree val
)
4875 /* We can insert a sequence with a single assignment only. */
4876 gimple_seq stmts
= VN_INFO (val
)->expr
;
4877 if (!gimple_seq_singleton_p (stmts
))
4879 gassign
*stmt
= dyn_cast
<gassign
*> (gimple_seq_first_stmt (stmts
));
4881 || (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt
))
4882 && gimple_assign_rhs_code (stmt
) != VIEW_CONVERT_EXPR
4883 && gimple_assign_rhs_code (stmt
) != BIT_FIELD_REF
4884 && (gimple_assign_rhs_code (stmt
) != BIT_AND_EXPR
4885 || TREE_CODE (gimple_assign_rhs2 (stmt
)) != INTEGER_CST
)))
4888 tree op
= gimple_assign_rhs1 (stmt
);
4889 if (gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
4890 || gimple_assign_rhs_code (stmt
) == BIT_FIELD_REF
)
4891 op
= TREE_OPERAND (op
, 0);
4892 tree leader
= TREE_CODE (op
) == SSA_NAME
? eliminate_avail (bb
, op
) : op
;
4898 if (gimple_assign_rhs_code (stmt
) == BIT_FIELD_REF
)
4899 res
= gimple_build (&stmts
, BIT_FIELD_REF
,
4900 TREE_TYPE (val
), leader
,
4901 TREE_OPERAND (gimple_assign_rhs1 (stmt
), 1),
4902 TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2));
4903 else if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
)
4904 res
= gimple_build (&stmts
, BIT_AND_EXPR
,
4905 TREE_TYPE (val
), leader
, gimple_assign_rhs2 (stmt
));
4907 res
= gimple_build (&stmts
, gimple_assign_rhs_code (stmt
),
4908 TREE_TYPE (val
), leader
);
4909 if (TREE_CODE (res
) != SSA_NAME
4910 || SSA_NAME_IS_DEFAULT_DEF (res
)
4911 || gimple_bb (SSA_NAME_DEF_STMT (res
)))
4913 gimple_seq_discard (stmts
);
4915 /* During propagation we have to treat SSA info conservatively
4916 and thus we can end up simplifying the inserted expression
4917 at elimination time to sth not defined in stmts. */
4918 /* But then this is a redundancy we failed to detect. Which means
4919 res now has two values. That doesn't play well with how
4920 we track availability here, so give up. */
4921 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4923 if (TREE_CODE (res
) == SSA_NAME
)
4924 res
= eliminate_avail (bb
, res
);
4927 fprintf (dump_file
, "Failed to insert expression for value ");
4928 print_generic_expr (dump_file
, val
);
4929 fprintf (dump_file
, " which is really fully redundant to ");
4930 print_generic_expr (dump_file
, res
);
4931 fprintf (dump_file
, "\n");
4939 gsi_insert_seq_before (gsi
, stmts
, GSI_SAME_STMT
);
4940 VN_INFO (res
)->valnum
= val
;
4941 VN_INFO (res
)->visited
= true;
4945 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4947 fprintf (dump_file
, "Inserted ");
4948 print_gimple_stmt (dump_file
, SSA_NAME_DEF_STMT (res
), 0);
4955 eliminate_dom_walker::eliminate_stmt (basic_block b
, gimple_stmt_iterator
*gsi
)
4957 tree sprime
= NULL_TREE
;
4958 gimple
*stmt
= gsi_stmt (*gsi
);
4959 tree lhs
= gimple_get_lhs (stmt
);
4960 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
4961 && !gimple_has_volatile_ops (stmt
)
4962 /* See PR43491. Do not replace a global register variable when
4963 it is a the RHS of an assignment. Do replace local register
4964 variables since gcc does not guarantee a local variable will
4965 be allocated in register.
4966 ??? The fix isn't effective here. This should instead
4967 be ensured by not value-numbering them the same but treating
4968 them like volatiles? */
4969 && !(gimple_assign_single_p (stmt
)
4970 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == VAR_DECL
4971 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt
))
4972 && is_global_var (gimple_assign_rhs1 (stmt
)))))
4974 sprime
= eliminate_avail (b
, lhs
);
4977 /* If there is no existing usable leader but SCCVN thinks
4978 it has an expression it wants to use as replacement,
4980 tree val
= VN_INFO (lhs
)->valnum
;
4982 && TREE_CODE (val
) == SSA_NAME
4983 && VN_INFO (val
)->needs_insertion
4984 && VN_INFO (val
)->expr
!= NULL
4985 && (sprime
= eliminate_insert (b
, gsi
, val
)) != NULL_TREE
)
4986 eliminate_push_avail (b
, sprime
);
4989 /* If this now constitutes a copy duplicate points-to
4990 and range info appropriately. This is especially
4991 important for inserted code. See tree-ssa-copy.c
4992 for similar code. */
4994 && TREE_CODE (sprime
) == SSA_NAME
)
4996 basic_block sprime_b
= gimple_bb (SSA_NAME_DEF_STMT (sprime
));
4997 if (POINTER_TYPE_P (TREE_TYPE (lhs
))
4998 && SSA_NAME_PTR_INFO (lhs
)
4999 && ! SSA_NAME_PTR_INFO (sprime
))
5001 duplicate_ssa_name_ptr_info (sprime
,
5002 SSA_NAME_PTR_INFO (lhs
));
5004 mark_ptr_info_alignment_unknown
5005 (SSA_NAME_PTR_INFO (sprime
));
5007 else if (INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
5008 && SSA_NAME_RANGE_INFO (lhs
)
5009 && ! SSA_NAME_RANGE_INFO (sprime
)
5011 duplicate_ssa_name_range_info (sprime
,
5012 SSA_NAME_RANGE_TYPE (lhs
),
5013 SSA_NAME_RANGE_INFO (lhs
));
5016 /* Inhibit the use of an inserted PHI on a loop header when
5017 the address of the memory reference is a simple induction
5018 variable. In other cases the vectorizer won't do anything
5019 anyway (either it's loop invariant or a complicated
5022 && TREE_CODE (sprime
) == SSA_NAME
5024 && (flag_tree_loop_vectorize
|| flag_tree_parallelize_loops
> 1)
5025 && loop_outer (b
->loop_father
)
5026 && has_zero_uses (sprime
)
5027 && bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (sprime
))
5028 && gimple_assign_load_p (stmt
))
5030 gimple
*def_stmt
= SSA_NAME_DEF_STMT (sprime
);
5031 basic_block def_bb
= gimple_bb (def_stmt
);
5032 if (gimple_code (def_stmt
) == GIMPLE_PHI
5033 && def_bb
->loop_father
->header
== def_bb
)
5035 loop_p loop
= def_bb
->loop_father
;
5039 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
5042 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (op
));
5044 && flow_bb_inside_loop_p (loop
, def_bb
)
5045 && simple_iv (loop
, loop
, op
, &iv
, true))
5053 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5055 fprintf (dump_file
, "Not replacing ");
5056 print_gimple_expr (dump_file
, stmt
, 0);
5057 fprintf (dump_file
, " with ");
5058 print_generic_expr (dump_file
, sprime
);
5059 fprintf (dump_file
, " which would add a loop"
5060 " carried dependence to loop %d\n",
5063 /* Don't keep sprime available. */
5071 /* If we can propagate the value computed for LHS into
5072 all uses don't bother doing anything with this stmt. */
5073 if (may_propagate_copy (lhs
, sprime
))
5075 /* Mark it for removal. */
5076 to_remove
.safe_push (stmt
);
5078 /* ??? Don't count copy/constant propagations. */
5079 if (gimple_assign_single_p (stmt
)
5080 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
5081 || gimple_assign_rhs1 (stmt
) == sprime
))
5084 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5086 fprintf (dump_file
, "Replaced ");
5087 print_gimple_expr (dump_file
, stmt
, 0);
5088 fprintf (dump_file
, " with ");
5089 print_generic_expr (dump_file
, sprime
);
5090 fprintf (dump_file
, " in all uses of ");
5091 print_gimple_stmt (dump_file
, stmt
, 0);
5098 /* If this is an assignment from our leader (which
5099 happens in the case the value-number is a constant)
5100 then there is nothing to do. */
5101 if (gimple_assign_single_p (stmt
)
5102 && sprime
== gimple_assign_rhs1 (stmt
))
5105 /* Else replace its RHS. */
5106 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5108 fprintf (dump_file
, "Replaced ");
5109 print_gimple_expr (dump_file
, stmt
, 0);
5110 fprintf (dump_file
, " with ");
5111 print_generic_expr (dump_file
, sprime
);
5112 fprintf (dump_file
, " in ");
5113 print_gimple_stmt (dump_file
, stmt
, 0);
5117 bool can_make_abnormal_goto
= (is_gimple_call (stmt
)
5118 && stmt_can_make_abnormal_goto (stmt
));
5119 gimple
*orig_stmt
= stmt
;
5120 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
5121 TREE_TYPE (sprime
)))
5123 /* We preserve conversions to but not from function or method
5124 types. This asymmetry makes it necessary to re-instantiate
5125 conversions here. */
5126 if (POINTER_TYPE_P (TREE_TYPE (lhs
))
5127 && FUNC_OR_METHOD_TYPE_P (TREE_TYPE (TREE_TYPE (lhs
))))
5128 sprime
= fold_convert (TREE_TYPE (lhs
), sprime
);
5132 tree vdef
= gimple_vdef (stmt
);
5133 tree vuse
= gimple_vuse (stmt
);
5134 propagate_tree_value_into_stmt (gsi
, sprime
);
5135 stmt
= gsi_stmt (*gsi
);
5137 /* In case the VDEF on the original stmt was released, value-number
5138 it to the VUSE. This is to make vuse_ssa_val able to skip
5139 released virtual operands. */
5140 if (vdef
!= gimple_vdef (stmt
))
5142 gcc_assert (SSA_NAME_IN_FREE_LIST (vdef
));
5143 VN_INFO (vdef
)->valnum
= vuse
;
5146 /* If we removed EH side-effects from the statement, clean
5147 its EH information. */
5148 if (maybe_clean_or_replace_eh_stmt (orig_stmt
, stmt
))
5150 bitmap_set_bit (need_eh_cleanup
,
5151 gimple_bb (stmt
)->index
);
5152 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5153 fprintf (dump_file
, " Removed EH side-effects.\n");
5156 /* Likewise for AB side-effects. */
5157 if (can_make_abnormal_goto
5158 && !stmt_can_make_abnormal_goto (stmt
))
5160 bitmap_set_bit (need_ab_cleanup
,
5161 gimple_bb (stmt
)->index
);
5162 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5163 fprintf (dump_file
, " Removed AB side-effects.\n");
5170 /* If the statement is a scalar store, see if the expression
5171 has the same value number as its rhs. If so, the store is
5173 if (gimple_assign_single_p (stmt
)
5174 && !gimple_has_volatile_ops (stmt
)
5175 && !is_gimple_reg (gimple_assign_lhs (stmt
))
5176 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
5177 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
5180 tree rhs
= gimple_assign_rhs1 (stmt
);
5181 vn_reference_t vnresult
;
5182 val
= vn_reference_lookup (lhs
, gimple_vuse (stmt
), VN_WALKREWRITE
,
5184 if (TREE_CODE (rhs
) == SSA_NAME
)
5185 rhs
= VN_INFO (rhs
)->valnum
;
5187 && operand_equal_p (val
, rhs
, 0))
5189 /* We can only remove the later store if the former aliases
5190 at least all accesses the later one does or if the store
5191 was to readonly memory storing the same value. */
5192 alias_set_type set
= get_alias_set (lhs
);
5194 || vnresult
->set
== set
5195 || alias_set_subset_of (set
, vnresult
->set
))
5197 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5199 fprintf (dump_file
, "Deleted redundant store ");
5200 print_gimple_stmt (dump_file
, stmt
, 0);
5203 /* Queue stmt for removal. */
5204 to_remove
.safe_push (stmt
);
5210 /* If this is a control statement value numbering left edges
5211 unexecuted on force the condition in a way consistent with
5213 if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
5215 if ((EDGE_SUCC (b
, 0)->flags
& EDGE_EXECUTABLE
)
5216 ^ (EDGE_SUCC (b
, 1)->flags
& EDGE_EXECUTABLE
))
5218 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5220 fprintf (dump_file
, "Removing unexecutable edge from ");
5221 print_gimple_stmt (dump_file
, stmt
, 0);
5223 if (((EDGE_SUCC (b
, 0)->flags
& EDGE_TRUE_VALUE
) != 0)
5224 == ((EDGE_SUCC (b
, 0)->flags
& EDGE_EXECUTABLE
) != 0))
5225 gimple_cond_make_true (cond
);
5227 gimple_cond_make_false (cond
);
5229 el_todo
|= TODO_cleanup_cfg
;
5234 bool can_make_abnormal_goto
= stmt_can_make_abnormal_goto (stmt
);
5235 bool was_noreturn
= (is_gimple_call (stmt
)
5236 && gimple_call_noreturn_p (stmt
));
5237 tree vdef
= gimple_vdef (stmt
);
5238 tree vuse
= gimple_vuse (stmt
);
5240 /* If we didn't replace the whole stmt (or propagate the result
5241 into all uses), replace all uses on this stmt with their
5243 bool modified
= false;
5244 use_operand_p use_p
;
5246 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
5248 tree use
= USE_FROM_PTR (use_p
);
5249 /* ??? The call code above leaves stmt operands un-updated. */
5250 if (TREE_CODE (use
) != SSA_NAME
)
5253 if (SSA_NAME_IS_DEFAULT_DEF (use
))
5254 /* ??? For default defs BB shouldn't matter, but we have to
5255 solve the inconsistency between rpo eliminate and
5256 dom eliminate avail valueization first. */
5257 sprime
= eliminate_avail (b
, use
);
5259 /* Look for sth available at the definition block of the argument.
5260 This avoids inconsistencies between availability there which
5261 decides if the stmt can be removed and availability at the
5262 use site. The SSA property ensures that things available
5263 at the definition are also available at uses. */
5264 sprime
= eliminate_avail (gimple_bb (SSA_NAME_DEF_STMT (use
)), use
);
5265 if (sprime
&& sprime
!= use
5266 && may_propagate_copy (use
, sprime
)
5267 /* We substitute into debug stmts to avoid excessive
5268 debug temporaries created by removed stmts, but we need
5269 to avoid doing so for inserted sprimes as we never want
5270 to create debug temporaries for them. */
5272 || TREE_CODE (sprime
) != SSA_NAME
5273 || !is_gimple_debug (stmt
)
5274 || !bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (sprime
))))
5276 propagate_value (use_p
, sprime
);
5281 /* Fold the stmt if modified, this canonicalizes MEM_REFs we propagated
5282 into which is a requirement for the IPA devirt machinery. */
5283 gimple
*old_stmt
= stmt
;
5286 /* If a formerly non-invariant ADDR_EXPR is turned into an
5287 invariant one it was on a separate stmt. */
5288 if (gimple_assign_single_p (stmt
)
5289 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ADDR_EXPR
)
5290 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt
));
5291 gimple_stmt_iterator prev
= *gsi
;
5293 if (fold_stmt (gsi
))
5295 /* fold_stmt may have created new stmts inbetween
5296 the previous stmt and the folded stmt. Mark
5297 all defs created there as varying to not confuse
5298 the SCCVN machinery as we're using that even during
5300 if (gsi_end_p (prev
))
5301 prev
= gsi_start_bb (b
);
5304 if (gsi_stmt (prev
) != gsi_stmt (*gsi
))
5309 FOR_EACH_SSA_TREE_OPERAND (def
, gsi_stmt (prev
),
5310 dit
, SSA_OP_ALL_DEFS
)
5311 /* As existing DEFs may move between stmts
5312 only process new ones. */
5313 if (! has_VN_INFO (def
))
5315 VN_INFO (def
)->valnum
= def
;
5316 VN_INFO (def
)->visited
= true;
5318 if (gsi_stmt (prev
) == gsi_stmt (*gsi
))
5324 stmt
= gsi_stmt (*gsi
);
5325 /* In case we folded the stmt away schedule the NOP for removal. */
5326 if (gimple_nop_p (stmt
))
5327 to_remove
.safe_push (stmt
);
5330 /* Visit indirect calls and turn them into direct calls if
5331 possible using the devirtualization machinery. Do this before
5332 checking for required EH/abnormal/noreturn cleanup as devird
5333 may expose more of those. */
5334 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
5336 tree fn
= gimple_call_fn (call_stmt
);
5338 && flag_devirtualize
5339 && virtual_method_call_p (fn
))
5341 tree otr_type
= obj_type_ref_class (fn
);
5342 unsigned HOST_WIDE_INT otr_tok
5343 = tree_to_uhwi (OBJ_TYPE_REF_TOKEN (fn
));
5345 ipa_polymorphic_call_context
context (current_function_decl
,
5346 fn
, stmt
, &instance
);
5347 context
.get_dynamic_type (instance
, OBJ_TYPE_REF_OBJECT (fn
),
5348 otr_type
, stmt
, NULL
);
5350 vec
<cgraph_node
*> targets
5351 = possible_polymorphic_call_targets (obj_type_ref_class (fn
),
5352 otr_tok
, context
, &final
);
5354 dump_possible_polymorphic_call_targets (dump_file
,
5355 obj_type_ref_class (fn
),
5357 if (final
&& targets
.length () <= 1 && dbg_cnt (devirt
))
5360 if (targets
.length () == 1)
5361 fn
= targets
[0]->decl
;
5363 fn
= builtin_decl_implicit (BUILT_IN_UNREACHABLE
);
5364 if (dump_enabled_p ())
5366 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
5367 "converting indirect call to "
5369 lang_hooks
.decl_printable_name (fn
, 2));
5371 gimple_call_set_fndecl (call_stmt
, fn
);
5372 /* If changing the call to __builtin_unreachable
5373 or similar noreturn function, adjust gimple_call_fntype
5375 if (gimple_call_noreturn_p (call_stmt
)
5376 && VOID_TYPE_P (TREE_TYPE (TREE_TYPE (fn
)))
5377 && TYPE_ARG_TYPES (TREE_TYPE (fn
))
5378 && (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fn
)))
5380 gimple_call_set_fntype (call_stmt
, TREE_TYPE (fn
));
5381 maybe_remove_unused_call_args (cfun
, call_stmt
);
5389 /* When changing a call into a noreturn call, cfg cleanup
5390 is needed to fix up the noreturn call. */
5392 && is_gimple_call (stmt
) && gimple_call_noreturn_p (stmt
))
5393 to_fixup
.safe_push (stmt
);
5394 /* When changing a condition or switch into one we know what
5395 edge will be executed, schedule a cfg cleanup. */
5396 if ((gimple_code (stmt
) == GIMPLE_COND
5397 && (gimple_cond_true_p (as_a
<gcond
*> (stmt
))
5398 || gimple_cond_false_p (as_a
<gcond
*> (stmt
))))
5399 || (gimple_code (stmt
) == GIMPLE_SWITCH
5400 && TREE_CODE (gimple_switch_index
5401 (as_a
<gswitch
*> (stmt
))) == INTEGER_CST
))
5402 el_todo
|= TODO_cleanup_cfg
;
5403 /* If we removed EH side-effects from the statement, clean
5404 its EH information. */
5405 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
5407 bitmap_set_bit (need_eh_cleanup
,
5408 gimple_bb (stmt
)->index
);
5409 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5410 fprintf (dump_file
, " Removed EH side-effects.\n");
5412 /* Likewise for AB side-effects. */
5413 if (can_make_abnormal_goto
5414 && !stmt_can_make_abnormal_goto (stmt
))
5416 bitmap_set_bit (need_ab_cleanup
,
5417 gimple_bb (stmt
)->index
);
5418 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5419 fprintf (dump_file
, " Removed AB side-effects.\n");
5422 /* In case the VDEF on the original stmt was released, value-number
5423 it to the VUSE. This is to make vuse_ssa_val able to skip
5424 released virtual operands. */
5425 if (vdef
&& SSA_NAME_IN_FREE_LIST (vdef
))
5426 VN_INFO (vdef
)->valnum
= vuse
;
5429 /* Make new values available - for fully redundant LHS we
5430 continue with the next stmt above and skip this. */
5432 FOR_EACH_SSA_DEF_OPERAND (defp
, stmt
, iter
, SSA_OP_DEF
)
5433 eliminate_push_avail (b
, DEF_FROM_PTR (defp
));
5436 /* Perform elimination for the basic-block B during the domwalk. */
5439 eliminate_dom_walker::before_dom_children (basic_block b
)
5442 avail_stack
.safe_push (NULL_TREE
);
5444 /* Skip unreachable blocks marked unreachable during the SCCVN domwalk. */
5445 if (!(b
->flags
& BB_EXECUTABLE
))
5450 for (gphi_iterator gsi
= gsi_start_phis (b
); !gsi_end_p (gsi
);)
5452 gphi
*phi
= gsi
.phi ();
5453 tree res
= PHI_RESULT (phi
);
5455 if (virtual_operand_p (res
))
5461 tree sprime
= eliminate_avail (b
, res
);
5465 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5467 fprintf (dump_file
, "Replaced redundant PHI node defining ");
5468 print_generic_expr (dump_file
, res
);
5469 fprintf (dump_file
, " with ");
5470 print_generic_expr (dump_file
, sprime
);
5471 fprintf (dump_file
, "\n");
5474 /* If we inserted this PHI node ourself, it's not an elimination. */
5475 if (! inserted_exprs
5476 || ! bitmap_bit_p (inserted_exprs
, SSA_NAME_VERSION (res
)))
5479 /* If we will propagate into all uses don't bother to do
5481 if (may_propagate_copy (res
, sprime
))
5483 /* Mark the PHI for removal. */
5484 to_remove
.safe_push (phi
);
5489 remove_phi_node (&gsi
, false);
5491 if (!useless_type_conversion_p (TREE_TYPE (res
), TREE_TYPE (sprime
)))
5492 sprime
= fold_convert (TREE_TYPE (res
), sprime
);
5493 gimple
*stmt
= gimple_build_assign (res
, sprime
);
5494 gimple_stmt_iterator gsi2
= gsi_after_labels (b
);
5495 gsi_insert_before (&gsi2
, stmt
, GSI_NEW_STMT
);
5499 eliminate_push_avail (b
, res
);
5503 for (gimple_stmt_iterator gsi
= gsi_start_bb (b
);
5506 eliminate_stmt (b
, &gsi
);
5508 /* Replace destination PHI arguments. */
5511 FOR_EACH_EDGE (e
, ei
, b
->succs
)
5512 if (e
->flags
& EDGE_EXECUTABLE
)
5513 for (gphi_iterator gsi
= gsi_start_phis (e
->dest
);
5517 gphi
*phi
= gsi
.phi ();
5518 use_operand_p use_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
5519 tree arg
= USE_FROM_PTR (use_p
);
5520 if (TREE_CODE (arg
) != SSA_NAME
5521 || virtual_operand_p (arg
))
5523 tree sprime
= eliminate_avail (b
, arg
);
5524 if (sprime
&& may_propagate_copy (arg
, sprime
))
5525 propagate_value (use_p
, sprime
);
5528 vn_context_bb
= NULL
;
5533 /* Make no longer available leaders no longer available. */
5536 eliminate_dom_walker::after_dom_children (basic_block
)
5539 while ((entry
= avail_stack
.pop ()) != NULL_TREE
)
5541 tree valnum
= VN_INFO (entry
)->valnum
;
5542 tree old
= avail
[SSA_NAME_VERSION (valnum
)];
5544 avail
[SSA_NAME_VERSION (valnum
)] = NULL_TREE
;
5546 avail
[SSA_NAME_VERSION (valnum
)] = entry
;
5550 /* Remove queued stmts and perform delayed cleanups. */
5553 eliminate_dom_walker::eliminate_cleanup (bool region_p
)
5555 statistics_counter_event (cfun
, "Eliminated", eliminations
);
5556 statistics_counter_event (cfun
, "Insertions", insertions
);
5558 /* We cannot remove stmts during BB walk, especially not release SSA
5559 names there as this confuses the VN machinery. The stmts ending
5560 up in to_remove are either stores or simple copies.
5561 Remove stmts in reverse order to make debug stmt creation possible. */
5562 while (!to_remove
.is_empty ())
5564 bool do_release_defs
= true;
5565 gimple
*stmt
= to_remove
.pop ();
5567 /* When we are value-numbering a region we do not require exit PHIs to
5568 be present so we have to make sure to deal with uses outside of the
5569 region of stmts that we thought are eliminated.
5570 ??? Note we may be confused by uses in dead regions we didn't run
5571 elimination on. Rather than checking individual uses we accept
5572 dead copies to be generated here (gcc.c-torture/execute/20060905-1.c
5573 contains such example). */
5576 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
5578 tree lhs
= gimple_phi_result (phi
);
5579 if (!has_zero_uses (lhs
))
5581 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5582 fprintf (dump_file
, "Keeping eliminated stmt live "
5583 "as copy because of out-of-region uses\n");
5584 tree sprime
= eliminate_avail (gimple_bb (stmt
), lhs
);
5585 gimple
*copy
= gimple_build_assign (lhs
, sprime
);
5586 gimple_stmt_iterator gsi
5587 = gsi_after_labels (gimple_bb (stmt
));
5588 gsi_insert_before (&gsi
, copy
, GSI_SAME_STMT
);
5589 do_release_defs
= false;
5592 else if (tree lhs
= gimple_get_lhs (stmt
))
5593 if (TREE_CODE (lhs
) == SSA_NAME
5594 && !has_zero_uses (lhs
))
5596 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5597 fprintf (dump_file
, "Keeping eliminated stmt live "
5598 "as copy because of out-of-region uses\n");
5599 tree sprime
= eliminate_avail (gimple_bb (stmt
), lhs
);
5600 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
5601 if (is_gimple_assign (stmt
))
5603 gimple_assign_set_rhs_from_tree (&gsi
, sprime
);
5604 stmt
= gsi_stmt (gsi
);
5606 if (maybe_clean_or_replace_eh_stmt (stmt
, stmt
))
5607 bitmap_set_bit (need_eh_cleanup
, gimple_bb (stmt
)->index
);
5612 gimple
*copy
= gimple_build_assign (lhs
, sprime
);
5613 gsi_insert_before (&gsi
, copy
, GSI_SAME_STMT
);
5614 do_release_defs
= false;
5619 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5621 fprintf (dump_file
, "Removing dead stmt ");
5622 print_gimple_stmt (dump_file
, stmt
, 0, TDF_NONE
);
5625 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
5626 if (gimple_code (stmt
) == GIMPLE_PHI
)
5627 remove_phi_node (&gsi
, do_release_defs
);
5630 basic_block bb
= gimple_bb (stmt
);
5631 unlink_stmt_vdef (stmt
);
5632 if (gsi_remove (&gsi
, true))
5633 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
5634 if (is_gimple_call (stmt
) && stmt_can_make_abnormal_goto (stmt
))
5635 bitmap_set_bit (need_ab_cleanup
, bb
->index
);
5636 if (do_release_defs
)
5637 release_defs (stmt
);
5640 /* Removing a stmt may expose a forwarder block. */
5641 el_todo
|= TODO_cleanup_cfg
;
5644 /* Fixup stmts that became noreturn calls. This may require splitting
5645 blocks and thus isn't possible during the dominator walk. Do this
5646 in reverse order so we don't inadvertedly remove a stmt we want to
5647 fixup by visiting a dominating now noreturn call first. */
5648 while (!to_fixup
.is_empty ())
5650 gimple
*stmt
= to_fixup
.pop ();
5652 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5654 fprintf (dump_file
, "Fixing up noreturn call ");
5655 print_gimple_stmt (dump_file
, stmt
, 0);
5658 if (fixup_noreturn_call (stmt
))
5659 el_todo
|= TODO_cleanup_cfg
;
5662 bool do_eh_cleanup
= !bitmap_empty_p (need_eh_cleanup
);
5663 bool do_ab_cleanup
= !bitmap_empty_p (need_ab_cleanup
);
5666 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
5669 gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup
);
5671 if (do_eh_cleanup
|| do_ab_cleanup
)
5672 el_todo
|= TODO_cleanup_cfg
;
5677 /* Eliminate fully redundant computations. */
5680 eliminate_with_rpo_vn (bitmap inserted_exprs
)
5682 eliminate_dom_walker
walker (CDI_DOMINATORS
, inserted_exprs
);
5684 walker
.walk (cfun
->cfg
->x_entry_block_ptr
);
5685 return walker
.eliminate_cleanup ();
5689 do_rpo_vn (function
*fn
, edge entry
, bitmap exit_bbs
,
5690 bool iterate
, bool eliminate
);
5693 run_rpo_vn (vn_lookup_kind kind
)
5695 default_vn_walk_kind
= kind
;
5696 do_rpo_vn (cfun
, NULL
, NULL
, true, false);
5698 /* ??? Prune requirement of these. */
5699 constant_to_value_id
= new hash_table
<vn_constant_hasher
> (23);
5700 constant_value_ids
= BITMAP_ALLOC (NULL
);
5702 /* Initialize the value ids and prune out remaining VN_TOPs
5706 FOR_EACH_SSA_NAME (i
, name
, cfun
)
5708 vn_ssa_aux_t info
= VN_INFO (name
);
5710 || info
->valnum
== VN_TOP
)
5711 info
->valnum
= name
;
5712 if (info
->valnum
== name
)
5713 info
->value_id
= get_next_value_id ();
5714 else if (is_gimple_min_invariant (info
->valnum
))
5715 info
->value_id
= get_or_alloc_constant_value_id (info
->valnum
);
5719 FOR_EACH_SSA_NAME (i
, name
, cfun
)
5721 vn_ssa_aux_t info
= VN_INFO (name
);
5722 if (TREE_CODE (info
->valnum
) == SSA_NAME
5723 && info
->valnum
!= name
5724 && info
->value_id
!= VN_INFO (info
->valnum
)->value_id
)
5725 info
->value_id
= VN_INFO (info
->valnum
)->value_id
;
5728 set_hashtable_value_ids ();
5730 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5732 fprintf (dump_file
, "Value numbers:\n");
5733 FOR_EACH_SSA_NAME (i
, name
, cfun
)
5735 if (VN_INFO (name
)->visited
5736 && SSA_VAL (name
) != name
)
5738 print_generic_expr (dump_file
, name
);
5739 fprintf (dump_file
, " = ");
5740 print_generic_expr (dump_file
, SSA_VAL (name
));
5741 fprintf (dump_file
, " (%04d)\n", VN_INFO (name
)->value_id
);
5747 /* Free VN associated data structures. */
5752 free_vn_table (valid_info
);
5753 XDELETE (valid_info
);
5754 obstack_free (&vn_tables_obstack
, NULL
);
5755 obstack_free (&vn_tables_insert_obstack
, NULL
);
5757 vn_ssa_aux_iterator_type it
;
5759 FOR_EACH_HASH_TABLE_ELEMENT (*vn_ssa_aux_hash
, info
, vn_ssa_aux_t
, it
)
5760 if (info
->needs_insertion
)
5761 release_ssa_name (info
->name
);
5762 obstack_free (&vn_ssa_aux_obstack
, NULL
);
5763 delete vn_ssa_aux_hash
;
5765 delete constant_to_value_id
;
5766 constant_to_value_id
= NULL
;
5767 BITMAP_FREE (constant_value_ids
);
5770 /* Hook for maybe_push_res_to_seq, lookup the expression in the VN tables. */
5773 vn_lookup_simplify_result (gimple_match_op
*res_op
)
5775 if (!res_op
->code
.is_tree_code ())
5777 tree
*ops
= res_op
->ops
;
5778 unsigned int length
= res_op
->num_ops
;
5779 if (res_op
->code
== CONSTRUCTOR
5780 /* ??? We're arriving here with SCCVNs view, decomposed CONSTRUCTOR
5781 and GIMPLEs / match-and-simplifies, CONSTRUCTOR as GENERIC tree. */
5782 && TREE_CODE (res_op
->ops
[0]) == CONSTRUCTOR
)
5784 length
= CONSTRUCTOR_NELTS (res_op
->ops
[0]);
5785 ops
= XALLOCAVEC (tree
, length
);
5786 for (unsigned i
= 0; i
< length
; ++i
)
5787 ops
[i
] = CONSTRUCTOR_ELT (res_op
->ops
[0], i
)->value
;
5789 vn_nary_op_t vnresult
= NULL
;
5790 tree res
= vn_nary_op_lookup_pieces (length
, (tree_code
) res_op
->code
,
5791 res_op
->type
, ops
, &vnresult
);
5792 /* If this is used from expression simplification make sure to
5793 return an available expression. */
5794 if (res
&& TREE_CODE (res
) == SSA_NAME
&& mprts_hook
&& rpo_avail
)
5795 res
= rpo_avail
->eliminate_avail (vn_context_bb
, res
);
5799 rpo_elim::~rpo_elim ()
5801 /* Release the avail vectors. */
5802 for (rpo_avail_t::iterator i
= m_rpo_avail
.begin ();
5803 i
!= m_rpo_avail
.end (); ++i
)
5804 (*i
).second
.release ();
5807 /* Return a leader for OPs value that is valid at BB. */
5810 rpo_elim::eliminate_avail (basic_block bb
, tree op
)
5813 tree valnum
= SSA_VAL (op
, &visited
);
5814 /* If we didn't visit OP then it must be defined outside of the
5815 region we process and also dominate it. So it is available. */
5818 if (TREE_CODE (valnum
) == SSA_NAME
)
5820 if (SSA_NAME_IS_DEFAULT_DEF (valnum
))
5822 vec
<std::pair
<int, int> > *av
= m_rpo_avail
.get (valnum
);
5823 if (!av
|| av
->is_empty ())
5825 int i
= av
->length () - 1;
5826 if ((*av
)[i
].first
== bb
->index
)
5827 /* On tramp3d 90% of the cases are here. */
5828 return ssa_name ((*av
)[i
].second
);
5831 basic_block abb
= BASIC_BLOCK_FOR_FN (cfun
, (*av
)[i
].first
);
5832 /* ??? During elimination we have to use availability at the
5833 definition site of a use we try to replace. This
5834 is required to not run into inconsistencies because
5835 of dominated_by_p_w_unex behavior and removing a definition
5836 while not replacing all uses.
5837 ??? We could try to consistently walk dominators
5838 ignoring non-executable regions. The nearest common
5839 dominator of bb and abb is where we can stop walking. We
5840 may also be able to "pre-compute" (bits of) the next immediate
5841 (non-)dominator during the RPO walk when marking edges as
5843 if (dominated_by_p_w_unex (bb
, abb
))
5845 tree leader
= ssa_name ((*av
)[i
].second
);
5846 /* Prevent eliminations that break loop-closed SSA. */
5847 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
)
5848 && ! SSA_NAME_IS_DEFAULT_DEF (leader
)
5849 && ! flow_bb_inside_loop_p (gimple_bb (SSA_NAME_DEF_STMT
5850 (leader
))->loop_father
,
5853 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5855 print_generic_expr (dump_file
, leader
);
5856 fprintf (dump_file
, " is available for ");
5857 print_generic_expr (dump_file
, valnum
);
5858 fprintf (dump_file
, "\n");
5860 /* On tramp3d 99% of the _remaining_ cases succeed at
5864 /* ??? Can we somehow skip to the immediate dominator
5865 RPO index (bb_to_rpo)? Again, maybe not worth, on
5866 tramp3d the worst number of elements in the vector is 9. */
5870 else if (valnum
!= VN_TOP
)
5871 /* valnum is is_gimple_min_invariant. */
5876 /* Make LEADER a leader for its value at BB. */
5879 rpo_elim::eliminate_push_avail (basic_block bb
, tree leader
)
5881 tree valnum
= VN_INFO (leader
)->valnum
;
5882 if (valnum
== VN_TOP
)
5884 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5886 fprintf (dump_file
, "Making available beyond BB%d ", bb
->index
);
5887 print_generic_expr (dump_file
, leader
);
5888 fprintf (dump_file
, " for value ");
5889 print_generic_expr (dump_file
, valnum
);
5890 fprintf (dump_file
, "\n");
5893 vec
<std::pair
<int, int> > &av
= m_rpo_avail
.get_or_insert (valnum
, &existed
);
5896 new (&av
) vec
<std::pair
<int, int> >;
5898 av
.reserve_exact (2);
5900 av
.safe_push (std::make_pair (bb
->index
, SSA_NAME_VERSION (leader
)));
5903 /* Valueization hook for RPO VN plus required state. */
5906 rpo_vn_valueize (tree name
)
5908 if (TREE_CODE (name
) == SSA_NAME
)
5910 vn_ssa_aux_t val
= VN_INFO (name
);
5913 tree tem
= val
->valnum
;
5914 if (tem
!= VN_TOP
&& tem
!= name
)
5916 if (TREE_CODE (tem
) != SSA_NAME
)
5918 /* For all values we only valueize to an available leader
5919 which means we can use SSA name info without restriction. */
5920 tem
= rpo_avail
->eliminate_avail (vn_context_bb
, tem
);
5929 /* Insert on PRED_E predicates derived from CODE OPS being true besides the
5930 inverted condition. */
5933 insert_related_predicates_on_edge (enum tree_code code
, tree
*ops
, edge pred_e
)
5938 /* a < b -> a {!,<}= b */
5939 vn_nary_op_insert_pieces_predicated (2, NE_EXPR
, boolean_type_node
,
5940 ops
, boolean_true_node
, 0, pred_e
);
5941 vn_nary_op_insert_pieces_predicated (2, LE_EXPR
, boolean_type_node
,
5942 ops
, boolean_true_node
, 0, pred_e
);
5943 /* a < b -> ! a {>,=} b */
5944 vn_nary_op_insert_pieces_predicated (2, GT_EXPR
, boolean_type_node
,
5945 ops
, boolean_false_node
, 0, pred_e
);
5946 vn_nary_op_insert_pieces_predicated (2, EQ_EXPR
, boolean_type_node
,
5947 ops
, boolean_false_node
, 0, pred_e
);
5950 /* a > b -> a {!,>}= b */
5951 vn_nary_op_insert_pieces_predicated (2, NE_EXPR
, boolean_type_node
,
5952 ops
, boolean_true_node
, 0, pred_e
);
5953 vn_nary_op_insert_pieces_predicated (2, GE_EXPR
, boolean_type_node
,
5954 ops
, boolean_true_node
, 0, pred_e
);
5955 /* a > b -> ! a {<,=} b */
5956 vn_nary_op_insert_pieces_predicated (2, LT_EXPR
, boolean_type_node
,
5957 ops
, boolean_false_node
, 0, pred_e
);
5958 vn_nary_op_insert_pieces_predicated (2, EQ_EXPR
, boolean_type_node
,
5959 ops
, boolean_false_node
, 0, pred_e
);
5962 /* a == b -> ! a {<,>} b */
5963 vn_nary_op_insert_pieces_predicated (2, LT_EXPR
, boolean_type_node
,
5964 ops
, boolean_false_node
, 0, pred_e
);
5965 vn_nary_op_insert_pieces_predicated (2, GT_EXPR
, boolean_type_node
,
5966 ops
, boolean_false_node
, 0, pred_e
);
5971 /* Nothing besides inverted condition. */
5977 /* Main stmt worker for RPO VN, process BB. */
5980 process_bb (rpo_elim
&avail
, basic_block bb
,
5981 bool bb_visited
, bool iterate_phis
, bool iterate
, bool eliminate
,
5982 bool do_region
, bitmap exit_bbs
, bool skip_phis
)
5990 /* If we are in loop-closed SSA preserve this state. This is
5991 relevant when called on regions from outside of FRE/PRE. */
5992 bool lc_phi_nodes
= false;
5994 && loops_state_satisfies_p (LOOP_CLOSED_SSA
))
5995 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
5996 if (e
->src
->loop_father
!= e
->dest
->loop_father
5997 && flow_loop_nested_p (e
->dest
->loop_father
,
5998 e
->src
->loop_father
))
6000 lc_phi_nodes
= true;
6004 /* When we visit a loop header substitute into loop info. */
6005 if (!iterate
&& eliminate
&& bb
->loop_father
->header
== bb
)
6007 /* Keep fields in sync with substitute_in_loop_info. */
6008 if (bb
->loop_father
->nb_iterations
)
6009 bb
->loop_father
->nb_iterations
6010 = simplify_replace_tree (bb
->loop_father
->nb_iterations
,
6011 NULL_TREE
, NULL_TREE
, vn_valueize
);
6014 /* Value-number all defs in the basic-block. */
6016 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
6019 gphi
*phi
= gsi
.phi ();
6020 tree res
= PHI_RESULT (phi
);
6021 vn_ssa_aux_t res_info
= VN_INFO (res
);
6024 gcc_assert (!res_info
->visited
);
6025 res_info
->valnum
= VN_TOP
;
6026 res_info
->visited
= true;
6029 /* When not iterating force backedge values to varying. */
6030 visit_stmt (phi
, !iterate_phis
);
6031 if (virtual_operand_p (res
))
6035 /* The interesting case is gcc.dg/tree-ssa/pr22230.c for correctness
6036 how we handle backedges and availability.
6037 And gcc.dg/tree-ssa/ssa-sccvn-2.c for optimization. */
6038 tree val
= res_info
->valnum
;
6039 if (res
!= val
&& !iterate
&& eliminate
)
6041 if (tree leader
= avail
.eliminate_avail (bb
, res
))
6044 /* Preserve loop-closed SSA form. */
6046 || is_gimple_min_invariant (leader
)))
6048 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6050 fprintf (dump_file
, "Replaced redundant PHI node "
6052 print_generic_expr (dump_file
, res
);
6053 fprintf (dump_file
, " with ");
6054 print_generic_expr (dump_file
, leader
);
6055 fprintf (dump_file
, "\n");
6057 avail
.eliminations
++;
6059 if (may_propagate_copy (res
, leader
))
6061 /* Schedule for removal. */
6062 avail
.to_remove
.safe_push (phi
);
6065 /* ??? Else generate a copy stmt. */
6069 /* Only make defs available that not already are. But make
6070 sure loop-closed SSA PHI node defs are picked up for
6074 || ! avail
.eliminate_avail (bb
, res
))
6075 avail
.eliminate_push_avail (bb
, res
);
6078 /* For empty BBs mark outgoing edges executable. For non-empty BBs
6079 we do this when processing the last stmt as we have to do this
6080 before elimination which otherwise forces GIMPLE_CONDs to
6081 if (1 != 0) style when seeing non-executable edges. */
6082 if (gsi_end_p (gsi_start_bb (bb
)))
6084 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
6086 if (!(e
->flags
& EDGE_EXECUTABLE
))
6088 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6090 "marking outgoing edge %d -> %d executable\n",
6091 e
->src
->index
, e
->dest
->index
);
6092 e
->flags
|= EDGE_EXECUTABLE
;
6093 e
->dest
->flags
|= BB_EXECUTABLE
;
6095 else if (!(e
->dest
->flags
& BB_EXECUTABLE
))
6097 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6099 "marking destination block %d reachable\n",
6101 e
->dest
->flags
|= BB_EXECUTABLE
;
6105 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
6106 !gsi_end_p (gsi
); gsi_next (&gsi
))
6112 FOR_EACH_SSA_TREE_OPERAND (op
, gsi_stmt (gsi
), i
, SSA_OP_ALL_DEFS
)
6114 vn_ssa_aux_t op_info
= VN_INFO (op
);
6115 gcc_assert (!op_info
->visited
);
6116 op_info
->valnum
= VN_TOP
;
6117 op_info
->visited
= true;
6120 /* We somehow have to deal with uses that are not defined
6121 in the processed region. Forcing unvisited uses to
6122 varying here doesn't play well with def-use following during
6123 expression simplification, so we deal with this by checking
6124 the visited flag in SSA_VAL. */
6127 visit_stmt (gsi_stmt (gsi
));
6129 gimple
*last
= gsi_stmt (gsi
);
6131 switch (gimple_code (last
))
6134 e
= find_taken_edge (bb
, vn_valueize (gimple_switch_index
6135 (as_a
<gswitch
*> (last
))));
6139 tree lhs
= vn_valueize (gimple_cond_lhs (last
));
6140 tree rhs
= vn_valueize (gimple_cond_rhs (last
));
6141 tree val
= gimple_simplify (gimple_cond_code (last
),
6142 boolean_type_node
, lhs
, rhs
,
6144 /* If the condition didn't simplfy see if we have recorded
6145 an expression from sofar taken edges. */
6146 if (! val
|| TREE_CODE (val
) != INTEGER_CST
)
6148 vn_nary_op_t vnresult
;
6152 val
= vn_nary_op_lookup_pieces (2, gimple_cond_code (last
),
6153 boolean_type_node
, ops
,
6155 /* Did we get a predicated value? */
6156 if (! val
&& vnresult
&& vnresult
->predicated_values
)
6158 val
= vn_nary_op_get_predicated_value (vnresult
, bb
);
6159 if (val
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
6161 fprintf (dump_file
, "Got predicated value ");
6162 print_generic_expr (dump_file
, val
, TDF_NONE
);
6163 fprintf (dump_file
, " for ");
6164 print_gimple_stmt (dump_file
, last
, TDF_SLIM
);
6169 e
= find_taken_edge (bb
, val
);
6172 /* If we didn't manage to compute the taken edge then
6173 push predicated expressions for the condition itself
6174 and related conditions to the hashtables. This allows
6175 simplification of redundant conditions which is
6176 important as early cleanup. */
6177 edge true_e
, false_e
;
6178 extract_true_false_edges_from_block (bb
, &true_e
, &false_e
);
6179 enum tree_code code
= gimple_cond_code (last
);
6180 enum tree_code icode
6181 = invert_tree_comparison (code
, HONOR_NANS (lhs
));
6186 && bitmap_bit_p (exit_bbs
, true_e
->dest
->index
))
6189 && bitmap_bit_p (exit_bbs
, false_e
->dest
->index
))
6192 vn_nary_op_insert_pieces_predicated
6193 (2, code
, boolean_type_node
, ops
,
6194 boolean_true_node
, 0, true_e
);
6196 vn_nary_op_insert_pieces_predicated
6197 (2, code
, boolean_type_node
, ops
,
6198 boolean_false_node
, 0, false_e
);
6199 if (icode
!= ERROR_MARK
)
6202 vn_nary_op_insert_pieces_predicated
6203 (2, icode
, boolean_type_node
, ops
,
6204 boolean_false_node
, 0, true_e
);
6206 vn_nary_op_insert_pieces_predicated
6207 (2, icode
, boolean_type_node
, ops
,
6208 boolean_true_node
, 0, false_e
);
6210 /* Relax for non-integers, inverted condition handled
6212 if (INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
6215 insert_related_predicates_on_edge (code
, ops
, true_e
);
6217 insert_related_predicates_on_edge (icode
, ops
, false_e
);
6223 e
= find_taken_edge (bb
, vn_valueize (gimple_goto_dest (last
)));
6230 todo
= TODO_cleanup_cfg
;
6231 if (!(e
->flags
& EDGE_EXECUTABLE
))
6233 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6235 "marking known outgoing %sedge %d -> %d executable\n",
6236 e
->flags
& EDGE_DFS_BACK
? "back-" : "",
6237 e
->src
->index
, e
->dest
->index
);
6238 e
->flags
|= EDGE_EXECUTABLE
;
6239 e
->dest
->flags
|= BB_EXECUTABLE
;
6241 else if (!(e
->dest
->flags
& BB_EXECUTABLE
))
6243 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6245 "marking destination block %d reachable\n",
6247 e
->dest
->flags
|= BB_EXECUTABLE
;
6250 else if (gsi_one_before_end_p (gsi
))
6252 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
6254 if (!(e
->flags
& EDGE_EXECUTABLE
))
6256 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6258 "marking outgoing edge %d -> %d executable\n",
6259 e
->src
->index
, e
->dest
->index
);
6260 e
->flags
|= EDGE_EXECUTABLE
;
6261 e
->dest
->flags
|= BB_EXECUTABLE
;
6263 else if (!(e
->dest
->flags
& BB_EXECUTABLE
))
6265 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6267 "marking destination block %d reachable\n",
6269 e
->dest
->flags
|= BB_EXECUTABLE
;
6274 /* Eliminate. That also pushes to avail. */
6275 if (eliminate
&& ! iterate
)
6276 avail
.eliminate_stmt (bb
, &gsi
);
6278 /* If not eliminating, make all not already available defs
6280 FOR_EACH_SSA_TREE_OPERAND (op
, gsi_stmt (gsi
), i
, SSA_OP_DEF
)
6281 if (! avail
.eliminate_avail (bb
, op
))
6282 avail
.eliminate_push_avail (bb
, op
);
6285 /* Eliminate in destination PHI arguments. Always substitute in dest
6286 PHIs, even for non-executable edges. This handles region
6288 if (!iterate
&& eliminate
)
6289 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
6290 for (gphi_iterator gsi
= gsi_start_phis (e
->dest
);
6291 !gsi_end_p (gsi
); gsi_next (&gsi
))
6293 gphi
*phi
= gsi
.phi ();
6294 use_operand_p use_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
6295 tree arg
= USE_FROM_PTR (use_p
);
6296 if (TREE_CODE (arg
) != SSA_NAME
6297 || virtual_operand_p (arg
))
6300 if (SSA_NAME_IS_DEFAULT_DEF (arg
))
6302 sprime
= SSA_VAL (arg
);
6303 gcc_assert (TREE_CODE (sprime
) != SSA_NAME
6304 || SSA_NAME_IS_DEFAULT_DEF (sprime
));
6307 /* Look for sth available at the definition block of the argument.
6308 This avoids inconsistencies between availability there which
6309 decides if the stmt can be removed and availability at the
6310 use site. The SSA property ensures that things available
6311 at the definition are also available at uses. */
6312 sprime
= avail
.eliminate_avail (gimple_bb (SSA_NAME_DEF_STMT (arg
)),
6316 && may_propagate_copy (arg
, sprime
))
6317 propagate_value (use_p
, sprime
);
6320 vn_context_bb
= NULL
;
6324 /* Unwind state per basic-block. */
6328 /* Times this block has been visited. */
6330 /* Whether to handle this as iteration point or whether to treat
6331 incoming backedge PHI values as varying. */
6333 /* Maximum RPO index this block is reachable from. */
6337 vn_reference_t ref_top
;
6339 vn_nary_op_t nary_top
;
6342 /* Unwind the RPO VN state for iteration. */
6345 do_unwind (unwind_state
*to
, int rpo_idx
, rpo_elim
&avail
, int *bb_to_rpo
)
6347 gcc_assert (to
->iterate
);
6348 for (; last_inserted_nary
!= to
->nary_top
;
6349 last_inserted_nary
= last_inserted_nary
->next
)
6352 slot
= valid_info
->nary
->find_slot_with_hash
6353 (last_inserted_nary
, last_inserted_nary
->hashcode
, NO_INSERT
);
6354 /* Predication causes the need to restore previous state. */
6355 if ((*slot
)->unwind_to
)
6356 *slot
= (*slot
)->unwind_to
;
6358 valid_info
->nary
->clear_slot (slot
);
6360 for (; last_inserted_phi
!= to
->phi_top
;
6361 last_inserted_phi
= last_inserted_phi
->next
)
6364 slot
= valid_info
->phis
->find_slot_with_hash
6365 (last_inserted_phi
, last_inserted_phi
->hashcode
, NO_INSERT
);
6366 valid_info
->phis
->clear_slot (slot
);
6368 for (; last_inserted_ref
!= to
->ref_top
;
6369 last_inserted_ref
= last_inserted_ref
->next
)
6371 vn_reference_t
*slot
;
6372 slot
= valid_info
->references
->find_slot_with_hash
6373 (last_inserted_ref
, last_inserted_ref
->hashcode
, NO_INSERT
);
6374 (*slot
)->operands
.release ();
6375 valid_info
->references
->clear_slot (slot
);
6377 obstack_free (&vn_tables_obstack
, to
->ob_top
);
6379 /* Prune [rpo_idx, ] from avail. */
6380 /* ??? This is O(number-of-values-in-region) which is
6381 O(region-size) rather than O(iteration-piece). */
6382 for (rpo_elim::rpo_avail_t::iterator i
6383 = avail
.m_rpo_avail
.begin ();
6384 i
!= avail
.m_rpo_avail
.end (); ++i
)
6386 while (! (*i
).second
.is_empty ())
6388 if (bb_to_rpo
[(*i
).second
.last ().first
] < rpo_idx
)
6395 /* Do VN on a SEME region specified by ENTRY and EXIT_BBS in FN.
6396 If ITERATE is true then treat backedges optimistically as not
6397 executed and iterate. If ELIMINATE is true then perform
6398 elimination, otherwise leave that to the caller. */
6401 do_rpo_vn (function
*fn
, edge entry
, bitmap exit_bbs
,
6402 bool iterate
, bool eliminate
)
6406 /* We currently do not support region-based iteration when
6407 elimination is requested. */
6408 gcc_assert (!entry
|| !iterate
|| !eliminate
);
6409 /* When iterating we need loop info up-to-date. */
6410 gcc_assert (!iterate
|| !loops_state_satisfies_p (LOOPS_NEED_FIXUP
));
6412 bool do_region
= entry
!= NULL
;
6415 entry
= single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (fn
));
6416 exit_bbs
= BITMAP_ALLOC (NULL
);
6417 bitmap_set_bit (exit_bbs
, EXIT_BLOCK
);
6420 /* Clear EDGE_DFS_BACK on "all" entry edges, RPO order compute will
6421 re-mark those that are contained in the region. */
6424 FOR_EACH_EDGE (e
, ei
, entry
->dest
->preds
)
6425 e
->flags
&= ~EDGE_DFS_BACK
;
6427 int *rpo
= XNEWVEC (int, n_basic_blocks_for_fn (fn
) - NUM_FIXED_BLOCKS
);
6428 int n
= rev_post_order_and_mark_dfs_back_seme
6429 (fn
, entry
, exit_bbs
, !loops_state_satisfies_p (LOOPS_NEED_FIXUP
), rpo
);
6430 /* rev_post_order_and_mark_dfs_back_seme fills RPO in reverse order. */
6431 for (int i
= 0; i
< n
/ 2; ++i
)
6432 std::swap (rpo
[i
], rpo
[n
-i
-1]);
6435 BITMAP_FREE (exit_bbs
);
6437 /* If there are any non-DFS_BACK edges into entry->dest skip
6438 processing PHI nodes for that block. This supports
6439 value-numbering loop bodies w/o the actual loop. */
6440 FOR_EACH_EDGE (e
, ei
, entry
->dest
->preds
)
6442 && !(e
->flags
& EDGE_DFS_BACK
))
6444 bool skip_entry_phis
= e
!= NULL
;
6445 if (skip_entry_phis
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
6446 fprintf (dump_file
, "Region does not contain all edges into "
6447 "the entry block, skipping its PHIs.\n");
6449 int *bb_to_rpo
= XNEWVEC (int, last_basic_block_for_fn (fn
));
6450 for (int i
= 0; i
< n
; ++i
)
6451 bb_to_rpo
[rpo
[i
]] = i
;
6453 unwind_state
*rpo_state
= XNEWVEC (unwind_state
, n
);
6455 rpo_elim
avail (entry
->dest
);
6458 /* Verify we have no extra entries into the region. */
6459 if (flag_checking
&& do_region
)
6461 auto_bb_flag
bb_in_region (fn
);
6462 for (int i
= 0; i
< n
; ++i
)
6464 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
6465 bb
->flags
|= bb_in_region
;
6467 /* We can't merge the first two loops because we cannot rely
6468 on EDGE_DFS_BACK for edges not within the region. But if
6469 we decide to always have the bb_in_region flag we can
6470 do the checking during the RPO walk itself (but then it's
6471 also easy to handle MEME conservatively). */
6472 for (int i
= 0; i
< n
; ++i
)
6474 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
6477 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
6478 gcc_assert (e
== entry
6479 || (skip_entry_phis
&& bb
== entry
->dest
)
6480 || (e
->src
->flags
& bb_in_region
));
6482 for (int i
= 0; i
< n
; ++i
)
6484 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
6485 bb
->flags
&= ~bb_in_region
;
6489 /* Create the VN state. For the initial size of the various hashtables
6490 use a heuristic based on region size and number of SSA names. */
6491 unsigned region_size
= (((unsigned HOST_WIDE_INT
)n
* num_ssa_names
)
6492 / (n_basic_blocks_for_fn (fn
) - NUM_FIXED_BLOCKS
));
6493 VN_TOP
= create_tmp_var_raw (void_type_node
, "vn_top");
6496 vn_ssa_aux_hash
= new hash_table
<vn_ssa_aux_hasher
> (region_size
* 2);
6497 gcc_obstack_init (&vn_ssa_aux_obstack
);
6499 gcc_obstack_init (&vn_tables_obstack
);
6500 gcc_obstack_init (&vn_tables_insert_obstack
);
6501 valid_info
= XCNEW (struct vn_tables_s
);
6502 allocate_vn_table (valid_info
, region_size
);
6503 last_inserted_ref
= NULL
;
6504 last_inserted_phi
= NULL
;
6505 last_inserted_nary
= NULL
;
6507 vn_valueize
= rpo_vn_valueize
;
6509 /* Initialize the unwind state and edge/BB executable state. */
6510 bool need_max_rpo_iterate
= false;
6511 for (int i
= 0; i
< n
; ++i
)
6513 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
6514 rpo_state
[i
].visited
= 0;
6515 rpo_state
[i
].max_rpo
= i
;
6516 bb
->flags
&= ~BB_EXECUTABLE
;
6517 bool has_backedges
= false;
6520 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
6522 if (e
->flags
& EDGE_DFS_BACK
)
6523 has_backedges
= true;
6524 e
->flags
&= ~EDGE_EXECUTABLE
;
6525 if (iterate
|| e
== entry
|| (skip_entry_phis
&& bb
== entry
->dest
))
6527 if (bb_to_rpo
[e
->src
->index
] > i
)
6529 rpo_state
[i
].max_rpo
= MAX (rpo_state
[i
].max_rpo
,
6530 bb_to_rpo
[e
->src
->index
]);
6531 need_max_rpo_iterate
= true;
6534 rpo_state
[i
].max_rpo
6535 = MAX (rpo_state
[i
].max_rpo
,
6536 rpo_state
[bb_to_rpo
[e
->src
->index
]].max_rpo
);
6538 rpo_state
[i
].iterate
= iterate
&& has_backedges
;
6540 entry
->flags
|= EDGE_EXECUTABLE
;
6541 entry
->dest
->flags
|= BB_EXECUTABLE
;
6543 /* When there are irreducible regions the simplistic max_rpo computation
6544 above for the case of backedges doesn't work and we need to iterate
6545 until there are no more changes. */
6547 while (need_max_rpo_iterate
)
6550 need_max_rpo_iterate
= false;
6551 for (int i
= 0; i
< n
; ++i
)
6553 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
6556 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
6558 if (e
== entry
|| (skip_entry_phis
&& bb
== entry
->dest
))
6560 int max_rpo
= MAX (rpo_state
[i
].max_rpo
,
6561 rpo_state
[bb_to_rpo
[e
->src
->index
]].max_rpo
);
6562 if (rpo_state
[i
].max_rpo
!= max_rpo
)
6564 rpo_state
[i
].max_rpo
= max_rpo
;
6565 need_max_rpo_iterate
= true;
6570 statistics_histogram_event (cfun
, "RPO max_rpo iterations", nit
);
6572 /* As heuristic to improve compile-time we handle only the N innermost
6573 loops and the outermost one optimistically. */
6577 unsigned max_depth
= PARAM_VALUE (PARAM_RPO_VN_MAX_LOOP_DEPTH
);
6578 FOR_EACH_LOOP (loop
, LI_ONLY_INNERMOST
)
6579 if (loop_depth (loop
) > max_depth
)
6580 for (unsigned i
= 2;
6581 i
< loop_depth (loop
) - max_depth
; ++i
)
6583 basic_block header
= superloop_at_depth (loop
, i
)->header
;
6584 bool non_latch_backedge
= false;
6587 FOR_EACH_EDGE (e
, ei
, header
->preds
)
6588 if (e
->flags
& EDGE_DFS_BACK
)
6590 /* There can be a non-latch backedge into the header
6591 which is part of an outer irreducible region. We
6592 cannot avoid iterating this block then. */
6593 if (!dominated_by_p (CDI_DOMINATORS
,
6596 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6597 fprintf (dump_file
, "non-latch backedge %d -> %d "
6598 "forces iteration of loop %d\n",
6599 e
->src
->index
, e
->dest
->index
, loop
->num
);
6600 non_latch_backedge
= true;
6603 e
->flags
|= EDGE_EXECUTABLE
;
6605 rpo_state
[bb_to_rpo
[header
->index
]].iterate
= non_latch_backedge
;
6612 /* Go and process all blocks, iterating as necessary. */
6615 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[idx
]);
6617 /* If the block has incoming backedges remember unwind state. This
6618 is required even for non-executable blocks since in irreducible
6619 regions we might reach them via the backedge and re-start iterating
6621 Note we can individually mark blocks with incoming backedges to
6622 not iterate where we then handle PHIs conservatively. We do that
6623 heuristically to reduce compile-time for degenerate cases. */
6624 if (rpo_state
[idx
].iterate
)
6626 rpo_state
[idx
].ob_top
= obstack_alloc (&vn_tables_obstack
, 0);
6627 rpo_state
[idx
].ref_top
= last_inserted_ref
;
6628 rpo_state
[idx
].phi_top
= last_inserted_phi
;
6629 rpo_state
[idx
].nary_top
= last_inserted_nary
;
6632 if (!(bb
->flags
& BB_EXECUTABLE
))
6634 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6635 fprintf (dump_file
, "Block %d: BB%d found not executable\n",
6641 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6642 fprintf (dump_file
, "Processing block %d: BB%d\n", idx
, bb
->index
);
6644 todo
|= process_bb (avail
, bb
,
6645 rpo_state
[idx
].visited
!= 0,
6646 rpo_state
[idx
].iterate
,
6647 iterate
, eliminate
, do_region
, exit_bbs
, false);
6648 rpo_state
[idx
].visited
++;
6650 /* Verify if changed values flow over executable outgoing backedges
6651 and those change destination PHI values (that's the thing we
6652 can easily verify). Reduce over all such edges to the farthest
6654 int iterate_to
= -1;
6657 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
6658 if ((e
->flags
& (EDGE_DFS_BACK
|EDGE_EXECUTABLE
))
6659 == (EDGE_DFS_BACK
|EDGE_EXECUTABLE
)
6660 && rpo_state
[bb_to_rpo
[e
->dest
->index
]].iterate
)
6662 int destidx
= bb_to_rpo
[e
->dest
->index
];
6663 if (!rpo_state
[destidx
].visited
)
6665 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6666 fprintf (dump_file
, "Unvisited destination %d\n",
6668 if (iterate_to
== -1 || destidx
< iterate_to
)
6669 iterate_to
= destidx
;
6672 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6673 fprintf (dump_file
, "Looking for changed values of backedge"
6674 " %d->%d destination PHIs\n",
6675 e
->src
->index
, e
->dest
->index
);
6676 vn_context_bb
= e
->dest
;
6678 for (gsi
= gsi_start_phis (e
->dest
);
6679 !gsi_end_p (gsi
); gsi_next (&gsi
))
6681 bool inserted
= false;
6682 /* While we'd ideally just iterate on value changes
6683 we CSE PHIs and do that even across basic-block
6684 boundaries. So even hashtable state changes can
6685 be important (which is roughly equivalent to
6686 PHI argument value changes). To not excessively
6687 iterate because of that we track whether a PHI
6688 was CSEd to with GF_PLF_1. */
6689 bool phival_changed
;
6690 if ((phival_changed
= visit_phi (gsi
.phi (),
6692 || (inserted
&& gimple_plf (gsi
.phi (), GF_PLF_1
)))
6695 && dump_file
&& (dump_flags
& TDF_DETAILS
))
6696 fprintf (dump_file
, "PHI was CSEd and hashtable "
6697 "state (changed)\n");
6698 if (iterate_to
== -1 || destidx
< iterate_to
)
6699 iterate_to
= destidx
;
6703 vn_context_bb
= NULL
;
6705 if (iterate_to
!= -1)
6707 do_unwind (&rpo_state
[iterate_to
], iterate_to
, avail
, bb_to_rpo
);
6709 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6710 fprintf (dump_file
, "Iterating to %d BB%d\n",
6711 iterate_to
, rpo
[iterate_to
]);
6721 /* Process all blocks greedily with a worklist that enforces RPO
6722 processing of reachable blocks. */
6723 auto_bitmap worklist
;
6724 bitmap_set_bit (worklist
, 0);
6725 while (!bitmap_empty_p (worklist
))
6727 int idx
= bitmap_first_set_bit (worklist
);
6728 bitmap_clear_bit (worklist
, idx
);
6729 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[idx
]);
6730 gcc_assert ((bb
->flags
& BB_EXECUTABLE
)
6731 && !rpo_state
[idx
].visited
);
6733 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6734 fprintf (dump_file
, "Processing block %d: BB%d\n", idx
, bb
->index
);
6736 /* When we run into predecessor edges where we cannot trust its
6737 executable state mark them executable so PHI processing will
6739 ??? Do we need to force arguments flowing over that edge
6740 to be varying or will they even always be? */
6743 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
6744 if (!(e
->flags
& EDGE_EXECUTABLE
)
6745 && (bb
== entry
->dest
6746 || (!rpo_state
[bb_to_rpo
[e
->src
->index
]].visited
6747 && (rpo_state
[bb_to_rpo
[e
->src
->index
]].max_rpo
6750 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6751 fprintf (dump_file
, "Cannot trust state of predecessor "
6752 "edge %d -> %d, marking executable\n",
6753 e
->src
->index
, e
->dest
->index
);
6754 e
->flags
|= EDGE_EXECUTABLE
;
6758 todo
|= process_bb (avail
, bb
, false, false, false, eliminate
,
6759 do_region
, exit_bbs
,
6760 skip_entry_phis
&& bb
== entry
->dest
);
6761 rpo_state
[idx
].visited
++;
6763 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
6764 if ((e
->flags
& EDGE_EXECUTABLE
)
6765 && e
->dest
->index
!= EXIT_BLOCK
6766 && (!do_region
|| !bitmap_bit_p (exit_bbs
, e
->dest
->index
))
6767 && !rpo_state
[bb_to_rpo
[e
->dest
->index
]].visited
)
6768 bitmap_set_bit (worklist
, bb_to_rpo
[e
->dest
->index
]);
6772 /* If statistics or dump file active. */
6774 unsigned max_visited
= 1;
6775 for (int i
= 0; i
< n
; ++i
)
6777 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rpo
[i
]);
6778 if (bb
->flags
& BB_EXECUTABLE
)
6780 statistics_histogram_event (cfun
, "RPO block visited times",
6781 rpo_state
[i
].visited
);
6782 if (rpo_state
[i
].visited
> max_visited
)
6783 max_visited
= rpo_state
[i
].visited
;
6785 unsigned nvalues
= 0, navail
= 0;
6786 for (rpo_elim::rpo_avail_t::iterator i
= avail
.m_rpo_avail
.begin ();
6787 i
!= avail
.m_rpo_avail
.end (); ++i
)
6790 navail
+= (*i
).second
.length ();
6792 statistics_counter_event (cfun
, "RPO blocks", n
);
6793 statistics_counter_event (cfun
, "RPO blocks visited", nblk
);
6794 statistics_counter_event (cfun
, "RPO blocks executable", nex
);
6795 statistics_histogram_event (cfun
, "RPO iterations", 10*nblk
/ nex
);
6796 statistics_histogram_event (cfun
, "RPO num values", nvalues
);
6797 statistics_histogram_event (cfun
, "RPO num avail", navail
);
6798 statistics_histogram_event (cfun
, "RPO num lattice",
6799 vn_ssa_aux_hash
->elements ());
6800 if (dump_file
&& (dump_flags
& (TDF_DETAILS
|TDF_STATS
)))
6802 fprintf (dump_file
, "RPO iteration over %d blocks visited %" PRIu64
6803 " blocks in total discovering %d executable blocks iterating "
6804 "%d.%d times, a block was visited max. %u times\n",
6806 (int)((10*nblk
/ nex
)/10), (int)((10*nblk
/ nex
)%10),
6808 fprintf (dump_file
, "RPO tracked %d values available at %d locations "
6809 "and %" PRIu64
" lattice elements\n",
6810 nvalues
, navail
, (uint64_t) vn_ssa_aux_hash
->elements ());
6815 /* When !iterate we already performed elimination during the RPO
6819 /* Elimination for region-based VN needs to be done within the
6821 gcc_assert (! do_region
);
6822 /* Note we can't use avail.walk here because that gets confused
6823 by the existing availability and it will be less efficient
6825 todo
|= eliminate_with_rpo_vn (NULL
);
6828 todo
|= avail
.eliminate_cleanup (do_region
);
6834 XDELETEVEC (bb_to_rpo
);
6836 XDELETEVEC (rpo_state
);
6841 /* Region-based entry for RPO VN. Performs value-numbering and elimination
6842 on the SEME region specified by ENTRY and EXIT_BBS. If ENTRY is not
6843 the only edge into the region at ENTRY->dest PHI nodes in ENTRY->dest
6844 are not considered. */
6847 do_rpo_vn (function
*fn
, edge entry
, bitmap exit_bbs
)
6849 default_vn_walk_kind
= VN_WALKREWRITE
;
6850 unsigned todo
= do_rpo_vn (fn
, entry
, exit_bbs
, false, true);
6858 const pass_data pass_data_fre
=
6860 GIMPLE_PASS
, /* type */
6862 OPTGROUP_NONE
, /* optinfo_flags */
6863 TV_TREE_FRE
, /* tv_id */
6864 ( PROP_cfg
| PROP_ssa
), /* properties_required */
6865 0, /* properties_provided */
6866 0, /* properties_destroyed */
6867 0, /* todo_flags_start */
6868 0, /* todo_flags_finish */
6871 class pass_fre
: public gimple_opt_pass
6874 pass_fre (gcc::context
*ctxt
)
6875 : gimple_opt_pass (pass_data_fre
, ctxt
)
6878 /* opt_pass methods: */
6879 opt_pass
* clone () { return new pass_fre (m_ctxt
); }
6880 virtual bool gate (function
*) { return flag_tree_fre
!= 0; }
6881 virtual unsigned int execute (function
*);
6883 }; // class pass_fre
6886 pass_fre::execute (function
*fun
)
6890 /* At -O[1g] use the cheap non-iterating mode. */
6891 calculate_dominance_info (CDI_DOMINATORS
);
6893 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
6895 default_vn_walk_kind
= VN_WALKREWRITE
;
6896 todo
= do_rpo_vn (fun
, NULL
, NULL
, optimize
> 1, true);
6900 loop_optimizer_finalize ();
6908 make_pass_fre (gcc::context
*ctxt
)
6910 return new pass_fre (ctxt
);
6913 #undef BB_EXECUTABLE