1 /* String length optimization
2 Copyright (C) 2011-2019 Free Software Foundation, Inc.
3 Contributed by Jakub Jelinek <jakub@redhat.com>
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"
28 #include "alloc-pool.h"
29 #include "tree-pass.h"
32 #include "gimple-pretty-print.h"
33 #include "gimple-ssa-warn-restrict.h"
34 #include "fold-const.h"
35 #include "stor-layout.h"
36 #include "gimple-fold.h"
39 #include "gimple-iterator.h"
40 #include "gimplify-me.h"
45 #include "tree-ssa-alias.h"
46 #include "tree-ssa-propagate.h"
47 #include "tree-ssa-strlen.h"
49 #include "tree-hash-traits.h"
50 #include "tree-object-size.h"
53 #include "diagnostic-core.h"
54 #include "diagnostic.h"
59 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
60 is an index into strinfo vector, negative value stands for
61 string length of a string literal (~strlen). */
62 static vec
<int> ssa_ver_to_stridx
;
64 /* Number of currently active string indexes plus one. */
65 static int max_stridx
;
67 /* String information record. */
70 /* Number of leading characters that are known to be nonzero. This is
71 also the length of the string if FULL_STRING_P.
73 The values in a list of related string pointers must be consistent;
74 that is, if strinfo B comes X bytes after strinfo A, it must be
75 the case that A->nonzero_chars == X + B->nonzero_chars. */
77 /* Any of the corresponding pointers for querying alias oracle. */
79 /* This is used for two things:
81 - To record the statement that should be used for delayed length
82 computations. We maintain the invariant that all related strinfos
83 have delayed lengths or none do.
85 - To record the malloc or calloc call that produced this result. */
87 /* Pointer to '\0' if known, if NULL, it can be computed as
90 /* Reference count. Any changes to strinfo entry possibly shared
91 with dominating basic blocks need unshare_strinfo first, except
92 for dont_invalidate which affects only the immediately next
95 /* Copy of index. get_strinfo (si->idx) should return si; */
97 /* These 3 fields are for chaining related string pointers together.
99 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
100 strcpy (c, d); e = c + dl;
101 strinfo(a) -> strinfo(c) -> strinfo(e)
102 All have ->first field equal to strinfo(a)->idx and are doubly
103 chained through prev/next fields. The later strinfos are required
104 to point into the same string with zero or more bytes after
105 the previous pointer and all bytes in between the two pointers
106 must be non-zero. Functions like strcpy or memcpy are supposed
107 to adjust all previous strinfo lengths, but not following strinfo
108 lengths (those are uncertain, usually invalidated during
109 maybe_invalidate, except when the alias oracle knows better).
110 Functions like strcat on the other side adjust the whole
111 related strinfo chain.
112 They are updated lazily, so to use the chain the same first fields
113 and si->prev->next == si->idx needs to be verified. */
117 /* A flag whether the string is known to be written in the current
120 /* A flag for the next maybe_invalidate that this strinfo shouldn't
121 be invalidated. Always cleared by maybe_invalidate. */
122 bool dont_invalidate
;
123 /* True if the string is known to be nul-terminated after NONZERO_CHARS
124 characters. False is useful when detecting strings that are built
125 up via successive memcpys. */
129 /* Pool for allocating strinfo_struct entries. */
130 static object_allocator
<strinfo
> strinfo_pool ("strinfo pool");
132 /* Vector mapping positive string indexes to strinfo, for the
133 current basic block. The first pointer in the vector is special,
134 it is either NULL, meaning the vector isn't shared, or it is
135 a basic block pointer to the owner basic_block if shared.
136 If some other bb wants to modify the vector, the vector needs
137 to be unshared first, and only the owner bb is supposed to free it. */
138 static vec
<strinfo
*, va_heap
, vl_embed
> *stridx_to_strinfo
;
140 /* One OFFSET->IDX mapping. */
143 struct stridxlist
*next
;
144 HOST_WIDE_INT offset
;
148 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
149 struct decl_stridxlist_map
151 struct tree_map_base base
;
152 struct stridxlist list
;
155 /* Hash table for mapping decls to a chained list of offset -> idx
157 static hash_map
<tree_decl_hash
, stridxlist
> *decl_to_stridxlist_htab
;
159 /* Hash table mapping strlen calls to stridx instances describing
160 the calls' arguments. Non-null only when warn_stringop_truncation
162 typedef std::pair
<int, location_t
> stridx_strlenloc
;
163 static hash_map
<tree
, stridx_strlenloc
> *strlen_to_stridx
;
165 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
166 static struct obstack stridx_obstack
;
168 /* Last memcpy statement if it could be adjusted if the trailing
169 '\0' written is immediately overwritten, or
170 *x = '\0' store that could be removed if it is immediately overwritten. */
171 struct laststmt_struct
178 static int get_stridx_plus_constant (strinfo
*, unsigned HOST_WIDE_INT
, tree
);
179 static void handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*);
183 - 1 if SI is known to start with more than OFF nonzero characters.
185 - 0 if SI is known to start with OFF nonzero characters,
186 but is not known to start with more.
188 - -1 if SI might not start with OFF nonzero characters. */
191 compare_nonzero_chars (strinfo
*si
, unsigned HOST_WIDE_INT off
)
193 if (si
->nonzero_chars
194 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
195 return compare_tree_int (si
->nonzero_chars
, off
);
200 /* Return true if SI is known to be a zero-length string. */
203 zero_length_string_p (strinfo
*si
)
205 return si
->full_string_p
&& integer_zerop (si
->nonzero_chars
);
208 /* Return strinfo vector entry IDX. */
210 static inline strinfo
*
211 get_strinfo (int idx
)
213 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
215 return (*stridx_to_strinfo
)[idx
];
218 /* Get the next strinfo in the chain after SI, or null if none. */
220 static inline strinfo
*
221 get_next_strinfo (strinfo
*si
)
225 strinfo
*nextsi
= get_strinfo (si
->next
);
226 if (nextsi
== NULL
|| nextsi
->first
!= si
->first
|| nextsi
->prev
!= si
->idx
)
231 /* Helper function for get_stridx. Return the strinfo index of the address
232 of EXP, which is available in PTR if nonnull. If OFFSET_OUT, it is
233 OK to return the index for some X <= &EXP and store &EXP - X in
237 get_addr_stridx (tree exp
, tree ptr
, unsigned HOST_WIDE_INT
*offset_out
)
240 struct stridxlist
*list
, *last
= NULL
;
243 if (!decl_to_stridxlist_htab
)
247 base
= get_addr_base_and_unit_offset (exp
, &poff
);
248 if (base
== NULL
|| !DECL_P (base
) || !poff
.is_constant (&off
))
251 list
= decl_to_stridxlist_htab
->get (base
);
257 if (list
->offset
== off
)
263 if (list
->offset
> off
)
270 if ((offset_out
|| ptr
) && last
&& last
->idx
> 0)
272 unsigned HOST_WIDE_INT rel_off
273 = (unsigned HOST_WIDE_INT
) off
- last
->offset
;
274 strinfo
*si
= get_strinfo (last
->idx
);
275 if (si
&& compare_nonzero_chars (si
, rel_off
) >= 0)
279 *offset_out
= rel_off
;
283 return get_stridx_plus_constant (si
, rel_off
, ptr
);
289 /* Return string index for EXP. */
292 get_stridx (tree exp
)
294 if (TREE_CODE (exp
) == SSA_NAME
)
296 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)])
297 return ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)];
300 HOST_WIDE_INT off
= 0;
301 for (i
= 0; i
< 5; i
++)
303 gimple
*def_stmt
= SSA_NAME_DEF_STMT (e
);
304 if (!is_gimple_assign (def_stmt
)
305 || gimple_assign_rhs_code (def_stmt
) != POINTER_PLUS_EXPR
)
307 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
308 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
309 if (TREE_CODE (rhs1
) != SSA_NAME
310 || !tree_fits_shwi_p (rhs2
))
312 HOST_WIDE_INT this_off
= tree_to_shwi (rhs2
);
315 off
= (unsigned HOST_WIDE_INT
) off
+ this_off
;
318 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)])
321 = get_strinfo (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)]);
322 if (si
&& compare_nonzero_chars (si
, off
) >= 0)
323 return get_stridx_plus_constant (si
, off
, exp
);
330 if (TREE_CODE (exp
) == ADDR_EXPR
)
332 int idx
= get_addr_stridx (TREE_OPERAND (exp
, 0), exp
, NULL
);
337 const char *p
= c_getstr (exp
);
339 return ~(int) strlen (p
);
344 /* Return true if strinfo vector is shared with the immediate dominator. */
347 strinfo_shared (void)
349 return vec_safe_length (stridx_to_strinfo
)
350 && (*stridx_to_strinfo
)[0] != NULL
;
353 /* Unshare strinfo vector that is shared with the immediate dominator. */
356 unshare_strinfo_vec (void)
361 gcc_assert (strinfo_shared ());
362 stridx_to_strinfo
= vec_safe_copy (stridx_to_strinfo
);
363 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
366 (*stridx_to_strinfo
)[0] = NULL
;
369 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
370 Return a pointer to the location where the string index can
371 be stored (if 0) or is stored, or NULL if this can't be tracked. */
374 addr_stridxptr (tree exp
)
379 tree base
= get_addr_base_and_unit_offset (exp
, &poff
);
380 if (base
== NULL_TREE
|| !DECL_P (base
) || !poff
.is_constant (&off
))
383 if (!decl_to_stridxlist_htab
)
385 decl_to_stridxlist_htab
386 = new hash_map
<tree_decl_hash
, stridxlist
> (64);
387 gcc_obstack_init (&stridx_obstack
);
391 stridxlist
*list
= &decl_to_stridxlist_htab
->get_or_insert (base
, &existed
);
395 stridxlist
*before
= NULL
;
396 for (i
= 0; i
< 32; i
++)
398 if (list
->offset
== off
)
400 if (list
->offset
> off
&& before
== NULL
)
402 if (list
->next
== NULL
)
411 before
= XOBNEW (&stridx_obstack
, struct stridxlist
);
418 list
->next
= XOBNEW (&stridx_obstack
, struct stridxlist
);
428 /* Create a new string index, or return 0 if reached limit. */
431 new_stridx (tree exp
)
434 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
436 if (TREE_CODE (exp
) == SSA_NAME
)
438 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
441 ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)] = idx
;
444 if (TREE_CODE (exp
) == ADDR_EXPR
)
446 int *pidx
= addr_stridxptr (TREE_OPERAND (exp
, 0));
449 gcc_assert (*pidx
== 0);
450 *pidx
= max_stridx
++;
457 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
460 new_addr_stridx (tree exp
)
463 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
465 pidx
= addr_stridxptr (exp
);
468 gcc_assert (*pidx
== 0);
469 *pidx
= max_stridx
++;
475 /* Create a new strinfo. */
478 new_strinfo (tree ptr
, int idx
, tree nonzero_chars
, bool full_string_p
)
480 strinfo
*si
= strinfo_pool
.allocate ();
481 si
->nonzero_chars
= nonzero_chars
;
484 si
->endptr
= NULL_TREE
;
490 si
->writable
= false;
491 si
->dont_invalidate
= false;
492 si
->full_string_p
= full_string_p
;
496 /* Decrease strinfo refcount and free it if not referenced anymore. */
499 free_strinfo (strinfo
*si
)
501 if (si
&& --si
->refcount
== 0)
502 strinfo_pool
.remove (si
);
505 /* Set strinfo in the vector entry IDX to SI. */
508 set_strinfo (int idx
, strinfo
*si
)
510 if (vec_safe_length (stridx_to_strinfo
) && (*stridx_to_strinfo
)[0])
511 unshare_strinfo_vec ();
512 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
513 vec_safe_grow_cleared (stridx_to_strinfo
, idx
+ 1);
514 (*stridx_to_strinfo
)[idx
] = si
;
517 /* Return the first strinfo in the related strinfo chain
518 if all strinfos in between belong to the chain, otherwise NULL. */
521 verify_related_strinfos (strinfo
*origsi
)
523 strinfo
*si
= origsi
, *psi
;
525 if (origsi
->first
== 0)
527 for (; si
->prev
; si
= psi
)
529 if (si
->first
!= origsi
->first
)
531 psi
= get_strinfo (si
->prev
);
534 if (psi
->next
!= si
->idx
)
537 if (si
->idx
!= si
->first
)
542 /* Set SI's endptr to ENDPTR and compute its length based on SI->ptr.
543 Use LOC for folding. */
546 set_endptr_and_length (location_t loc
, strinfo
*si
, tree endptr
)
550 tree start_as_size
= fold_convert_loc (loc
, size_type_node
, si
->ptr
);
551 tree end_as_size
= fold_convert_loc (loc
, size_type_node
, endptr
);
552 si
->nonzero_chars
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
553 end_as_size
, start_as_size
);
554 si
->full_string_p
= true;
557 /* Return string length, or NULL if it can't be computed. */
560 get_string_length (strinfo
*si
)
562 if (si
->nonzero_chars
)
563 return si
->full_string_p
? si
->nonzero_chars
: NULL
;
567 gimple
*stmt
= si
->stmt
, *lenstmt
;
568 tree callee
, lhs
, fn
, tem
;
570 gimple_stmt_iterator gsi
;
572 gcc_assert (is_gimple_call (stmt
));
573 callee
= gimple_call_fndecl (stmt
);
574 gcc_assert (callee
&& fndecl_built_in_p (callee
, BUILT_IN_NORMAL
));
575 lhs
= gimple_call_lhs (stmt
);
576 /* unshare_strinfo is intentionally not called here. The (delayed)
577 transformation of strcpy or strcat into stpcpy is done at the place
578 of the former strcpy/strcat call and so can affect all the strinfos
579 with the same stmt. If they were unshared before and transformation
580 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
581 just compute the right length. */
582 switch (DECL_FUNCTION_CODE (callee
))
584 case BUILT_IN_STRCAT
:
585 case BUILT_IN_STRCAT_CHK
:
586 gsi
= gsi_for_stmt (stmt
);
587 fn
= builtin_decl_implicit (BUILT_IN_STRLEN
);
588 gcc_assert (lhs
== NULL_TREE
);
589 tem
= unshare_expr (gimple_call_arg (stmt
, 0));
590 lenstmt
= gimple_build_call (fn
, 1, tem
);
591 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), lenstmt
);
592 gimple_call_set_lhs (lenstmt
, lhs
);
593 gimple_set_vuse (lenstmt
, gimple_vuse (stmt
));
594 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
595 tem
= gimple_call_arg (stmt
, 0);
596 if (!ptrofftype_p (TREE_TYPE (lhs
)))
598 lhs
= convert_to_ptrofftype (lhs
);
599 lhs
= force_gimple_operand_gsi (&gsi
, lhs
, true, NULL_TREE
,
600 true, GSI_SAME_STMT
);
602 lenstmt
= gimple_build_assign
603 (make_ssa_name (TREE_TYPE (gimple_call_arg (stmt
, 0))),
604 POINTER_PLUS_EXPR
,tem
, lhs
);
605 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
606 gimple_call_set_arg (stmt
, 0, gimple_assign_lhs (lenstmt
));
609 case BUILT_IN_STRCPY
:
610 case BUILT_IN_STRCPY_CHK
:
611 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY
));
612 if (gimple_call_num_args (stmt
) == 2)
613 fn
= builtin_decl_implicit (BUILT_IN_STPCPY
);
615 fn
= builtin_decl_explicit (BUILT_IN_STPCPY_CHK
);
616 gcc_assert (lhs
== NULL_TREE
);
617 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
619 fprintf (dump_file
, "Optimizing: ");
620 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
622 gimple_call_set_fndecl (stmt
, fn
);
623 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), stmt
);
624 gimple_call_set_lhs (stmt
, lhs
);
626 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
628 fprintf (dump_file
, "into: ");
629 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
632 case BUILT_IN_STPCPY
:
633 case BUILT_IN_STPCPY_CHK
:
634 gcc_assert (lhs
!= NULL_TREE
);
635 loc
= gimple_location (stmt
);
636 set_endptr_and_length (loc
, si
, lhs
);
637 for (strinfo
*chainsi
= verify_related_strinfos (si
);
639 chainsi
= get_next_strinfo (chainsi
))
640 if (chainsi
->nonzero_chars
== NULL
)
641 set_endptr_and_length (loc
, chainsi
, lhs
);
643 case BUILT_IN_MALLOC
:
645 /* BUILT_IN_CALLOC always has si->nonzero_chars set. */
652 return si
->nonzero_chars
;
655 /* Invalidate string length information for strings whose length
656 might change due to stores in stmt. */
659 maybe_invalidate (gimple
*stmt
)
663 bool nonempty
= false;
665 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
668 if (!si
->dont_invalidate
)
671 /* Do not use si->nonzero_chars. */
672 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, NULL_TREE
);
673 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
675 set_strinfo (i
, NULL
);
680 si
->dont_invalidate
= false;
686 /* Unshare strinfo record SI, if it has refcount > 1 or
687 if stridx_to_strinfo vector is shared with some other
691 unshare_strinfo (strinfo
*si
)
695 if (si
->refcount
== 1 && !strinfo_shared ())
698 nsi
= new_strinfo (si
->ptr
, si
->idx
, si
->nonzero_chars
, si
->full_string_p
);
699 nsi
->stmt
= si
->stmt
;
700 nsi
->endptr
= si
->endptr
;
701 nsi
->first
= si
->first
;
702 nsi
->prev
= si
->prev
;
703 nsi
->next
= si
->next
;
704 nsi
->writable
= si
->writable
;
705 set_strinfo (si
->idx
, nsi
);
710 /* Attempt to create a new strinfo for BASESI + OFF, or find existing
711 strinfo if there is any. Return it's idx, or 0 if no strinfo has
715 get_stridx_plus_constant (strinfo
*basesi
, unsigned HOST_WIDE_INT off
,
718 if (TREE_CODE (ptr
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
721 if (compare_nonzero_chars (basesi
, off
) < 0
722 || !tree_fits_uhwi_p (basesi
->nonzero_chars
))
725 unsigned HOST_WIDE_INT nonzero_chars
726 = tree_to_uhwi (basesi
->nonzero_chars
) - off
;
727 strinfo
*si
= basesi
, *chainsi
;
728 if (si
->first
|| si
->prev
|| si
->next
)
729 si
= verify_related_strinfos (basesi
);
731 || si
->nonzero_chars
== NULL_TREE
732 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
735 if (TREE_CODE (ptr
) == SSA_NAME
736 && ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
737 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
739 gcc_checking_assert (compare_tree_int (si
->nonzero_chars
, off
) != -1);
740 for (chainsi
= si
; chainsi
->next
; chainsi
= si
)
742 si
= get_next_strinfo (chainsi
);
744 || si
->nonzero_chars
== NULL_TREE
745 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
747 int r
= compare_tree_int (si
->nonzero_chars
, nonzero_chars
);
752 if (TREE_CODE (ptr
) == SSA_NAME
)
753 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = si
->idx
;
756 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
757 if (pidx
!= NULL
&& *pidx
== 0)
766 int idx
= new_stridx (ptr
);
769 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, nonzero_chars
),
770 basesi
->full_string_p
);
771 set_strinfo (idx
, si
);
772 if (strinfo
*nextsi
= get_strinfo (chainsi
->next
))
774 nextsi
= unshare_strinfo (nextsi
);
775 si
->next
= nextsi
->idx
;
778 chainsi
= unshare_strinfo (chainsi
);
779 if (chainsi
->first
== 0)
780 chainsi
->first
= chainsi
->idx
;
782 if (chainsi
->endptr
== NULL_TREE
&& zero_length_string_p (si
))
783 chainsi
->endptr
= ptr
;
784 si
->endptr
= chainsi
->endptr
;
785 si
->prev
= chainsi
->idx
;
786 si
->first
= chainsi
->first
;
787 si
->writable
= chainsi
->writable
;
791 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
792 to a zero-length string and if possible chain it to a related strinfo
793 chain whose part is or might be CHAINSI. */
796 zero_length_string (tree ptr
, strinfo
*chainsi
)
800 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
801 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
802 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
803 && ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] == 0);
805 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
809 si
= verify_related_strinfos (chainsi
);
814 /* We shouldn't mix delayed and non-delayed lengths. */
815 gcc_assert (si
->full_string_p
);
816 if (si
->endptr
== NULL_TREE
)
818 si
= unshare_strinfo (si
);
822 si
= get_next_strinfo (si
);
825 if (zero_length_string_p (chainsi
))
829 chainsi
= unshare_strinfo (chainsi
);
832 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = chainsi
->idx
;
838 /* We shouldn't mix delayed and non-delayed lengths. */
839 gcc_assert (chainsi
->full_string_p
);
840 if (chainsi
->first
|| chainsi
->prev
|| chainsi
->next
)
842 chainsi
= unshare_strinfo (chainsi
);
849 idx
= new_stridx (ptr
);
852 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, 0), true);
853 set_strinfo (idx
, si
);
857 chainsi
= unshare_strinfo (chainsi
);
858 if (chainsi
->first
== 0)
859 chainsi
->first
= chainsi
->idx
;
861 if (chainsi
->endptr
== NULL_TREE
)
862 chainsi
->endptr
= ptr
;
863 si
->prev
= chainsi
->idx
;
864 si
->first
= chainsi
->first
;
865 si
->writable
= chainsi
->writable
;
870 /* For strinfo ORIGSI whose length has been just updated, adjust other
871 related strinfos so that they match the new ORIGSI. This involves:
873 - adding ADJ to the nonzero_chars fields
874 - copying full_string_p from the new ORIGSI. */
877 adjust_related_strinfos (location_t loc
, strinfo
*origsi
, tree adj
)
879 strinfo
*si
= verify_related_strinfos (origsi
);
892 si
= unshare_strinfo (si
);
893 /* We shouldn't see delayed lengths here; the caller must have
894 calculated the old length in order to calculate the
896 gcc_assert (si
->nonzero_chars
);
897 tem
= fold_convert_loc (loc
, TREE_TYPE (si
->nonzero_chars
), adj
);
898 si
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
899 TREE_TYPE (si
->nonzero_chars
),
900 si
->nonzero_chars
, tem
);
901 si
->full_string_p
= origsi
->full_string_p
;
903 si
->endptr
= NULL_TREE
;
904 si
->dont_invalidate
= true;
906 nsi
= get_next_strinfo (si
);
913 /* Find if there are other SSA_NAME pointers equal to PTR
914 for which we don't track their string lengths yet. If so, use
918 find_equal_ptrs (tree ptr
, int idx
)
920 if (TREE_CODE (ptr
) != SSA_NAME
)
924 gimple
*stmt
= SSA_NAME_DEF_STMT (ptr
);
925 if (!is_gimple_assign (stmt
))
927 ptr
= gimple_assign_rhs1 (stmt
);
928 switch (gimple_assign_rhs_code (stmt
))
933 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)))
935 if (TREE_CODE (ptr
) == SSA_NAME
)
937 if (TREE_CODE (ptr
) != ADDR_EXPR
)
942 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
943 if (pidx
!= NULL
&& *pidx
== 0)
951 /* We might find an endptr created in this pass. Grow the
952 vector in that case. */
953 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
954 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
956 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] != 0)
958 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = idx
;
962 /* Return true if STMT is a call to a builtin function with the right
963 arguments and attributes that should be considered for optimization
967 valid_builtin_call (gimple
*stmt
)
969 if (!gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
972 tree callee
= gimple_call_fndecl (stmt
);
973 switch (DECL_FUNCTION_CODE (callee
))
975 case BUILT_IN_MEMCMP
:
976 case BUILT_IN_MEMCMP_EQ
:
977 case BUILT_IN_STRCHR
:
978 case BUILT_IN_STRLEN
:
979 /* The above functions should be pure. Punt if they aren't. */
980 if (gimple_vdef (stmt
) || gimple_vuse (stmt
) == NULL_TREE
)
984 case BUILT_IN_CALLOC
:
985 case BUILT_IN_MALLOC
:
986 case BUILT_IN_MEMCPY
:
987 case BUILT_IN_MEMCPY_CHK
:
988 case BUILT_IN_MEMPCPY
:
989 case BUILT_IN_MEMPCPY_CHK
:
990 case BUILT_IN_MEMSET
:
991 case BUILT_IN_STPCPY
:
992 case BUILT_IN_STPCPY_CHK
:
993 case BUILT_IN_STRCAT
:
994 case BUILT_IN_STRCAT_CHK
:
995 case BUILT_IN_STRCPY
:
996 case BUILT_IN_STRCPY_CHK
:
997 /* The above functions should be neither const nor pure. Punt if they
999 if (gimple_vdef (stmt
) == NULL_TREE
|| gimple_vuse (stmt
) == NULL_TREE
)
1010 /* If the last .MEM setter statement before STMT is
1011 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
1012 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
1013 just memcpy (x, y, strlen (y)). SI must be the zero length
1017 adjust_last_stmt (strinfo
*si
, gimple
*stmt
, bool is_strcat
)
1019 tree vuse
, callee
, len
;
1020 struct laststmt_struct last
= laststmt
;
1021 strinfo
*lastsi
, *firstsi
;
1022 unsigned len_arg_no
= 2;
1024 laststmt
.stmt
= NULL
;
1025 laststmt
.len
= NULL_TREE
;
1026 laststmt
.stridx
= 0;
1028 if (last
.stmt
== NULL
)
1031 vuse
= gimple_vuse (stmt
);
1032 if (vuse
== NULL_TREE
1033 || SSA_NAME_DEF_STMT (vuse
) != last
.stmt
1034 || !has_single_use (vuse
))
1037 gcc_assert (last
.stridx
> 0);
1038 lastsi
= get_strinfo (last
.stridx
);
1044 if (lastsi
->first
== 0 || lastsi
->first
!= si
->first
)
1047 firstsi
= verify_related_strinfos (si
);
1048 if (firstsi
== NULL
)
1050 while (firstsi
!= lastsi
)
1052 firstsi
= get_next_strinfo (firstsi
);
1053 if (firstsi
== NULL
)
1058 if (!is_strcat
&& !zero_length_string_p (si
))
1061 if (is_gimple_assign (last
.stmt
))
1063 gimple_stmt_iterator gsi
;
1065 if (!integer_zerop (gimple_assign_rhs1 (last
.stmt
)))
1067 if (stmt_could_throw_p (cfun
, last
.stmt
))
1069 gsi
= gsi_for_stmt (last
.stmt
);
1070 unlink_stmt_vdef (last
.stmt
);
1071 release_defs (last
.stmt
);
1072 gsi_remove (&gsi
, true);
1076 if (!valid_builtin_call (last
.stmt
))
1079 callee
= gimple_call_fndecl (last
.stmt
);
1080 switch (DECL_FUNCTION_CODE (callee
))
1082 case BUILT_IN_MEMCPY
:
1083 case BUILT_IN_MEMCPY_CHK
:
1089 len
= gimple_call_arg (last
.stmt
, len_arg_no
);
1090 if (tree_fits_uhwi_p (len
))
1092 if (!tree_fits_uhwi_p (last
.len
)
1093 || integer_zerop (len
)
1094 || tree_to_uhwi (len
) != tree_to_uhwi (last
.len
) + 1)
1096 /* Don't adjust the length if it is divisible by 4, it is more efficient
1097 to store the extra '\0' in that case. */
1098 if ((tree_to_uhwi (len
) & 3) == 0)
1101 /* Don't fold away an out of bounds access, as this defeats proper
1103 tree dst
= gimple_call_arg (last
.stmt
, 0);
1104 tree size
= compute_objsize (dst
, 0);
1105 if (size
&& tree_int_cst_lt (size
, len
))
1108 else if (TREE_CODE (len
) == SSA_NAME
)
1110 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1111 if (!is_gimple_assign (def_stmt
)
1112 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1113 || gimple_assign_rhs1 (def_stmt
) != last
.len
1114 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1120 gimple_call_set_arg (last
.stmt
, len_arg_no
, last
.len
);
1121 update_stmt (last
.stmt
);
1124 /* For an LHS that is an SSA_NAME that is the result of a strlen()
1125 call, or when BOUND is non-null, of a strnlen() call, set LHS
1126 range info to [0, min (MAX, BOUND)] when the range includes more
1127 than one value and return LHS. Otherwise, when the range
1128 [MIN, MAX] is such that MIN == MAX, return the tree representation
1129 of (MIN). The latter allows callers to fold suitable strnlen() calls
1133 set_strlen_range (tree lhs
, wide_int max
, tree bound
/* = NULL_TREE */)
1135 if (TREE_CODE (lhs
) != SSA_NAME
1136 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
1139 wide_int min
= wi::zero (max
.get_precision ());
1143 /* For strnlen, adjust MIN and MAX as necessary. If the bound
1144 is less than the size of the array set MAX to it. It it's
1145 greater than MAX and MAX is non-zero bump MAX down to account
1146 for the necessary terminating nul. Otherwise leave it alone. */
1147 if (TREE_CODE (bound
) == INTEGER_CST
)
1149 wide_int wibnd
= wi::to_wide (bound
);
1150 int cmp
= wi::cmpu (wibnd
, max
);
1153 else if (cmp
&& wi::ne_p (max
, min
))
1156 else if (TREE_CODE (bound
) == SSA_NAME
)
1158 wide_int minbound
, maxbound
;
1159 value_range_kind rng
= get_range_info (bound
, &minbound
, &maxbound
);
1160 if (rng
== VR_RANGE
)
1162 /* For a bound in a known range, adjust the range determined
1163 above as necessary. For a bound in some anti-range or
1164 in an unknown range, use the range determined by callers. */
1165 if (wi::ltu_p (minbound
, min
))
1167 if (wi::ltu_p (maxbound
, max
))
1174 return wide_int_to_tree (size_type_node
, min
);
1176 set_range_info (lhs
, VR_RANGE
, min
, max
);
1180 /* For an LHS that is an SSA_NAME and for strlen() or strnlen() argument
1181 SRC, set LHS range info to [0, min (N, BOUND)] if SRC refers to
1182 a character array A[N] with unknown length bounded by N, and for
1183 strnlen(), by min (N, BOUND). */
1186 maybe_set_strlen_range (tree lhs
, tree src
, tree bound
)
1188 if (TREE_CODE (lhs
) != SSA_NAME
1189 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
1192 if (TREE_CODE (src
) == SSA_NAME
)
1194 gimple
*def
= SSA_NAME_DEF_STMT (src
);
1195 if (is_gimple_assign (def
)
1196 && gimple_assign_rhs_code (def
) == ADDR_EXPR
)
1197 src
= gimple_assign_rhs1 (def
);
1200 /* The longest string is PTRDIFF_MAX - 1 bytes including the final
1201 NUL so that the difference between a pointer to just past it and
1202 one to its beginning is positive. */
1203 wide_int max
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
)) - 2;
1205 if (TREE_CODE (src
) == ADDR_EXPR
)
1207 /* The last array member of a struct can be bigger than its size
1208 suggests if it's treated as a poor-man's flexible array member. */
1209 src
= TREE_OPERAND (src
, 0);
1210 if (TREE_CODE (src
) != MEM_REF
1211 && !array_at_struct_end_p (src
))
1213 tree type
= TREE_TYPE (src
);
1214 tree size
= TYPE_SIZE_UNIT (type
);
1216 && TREE_CODE (size
) == INTEGER_CST
1217 && !integer_zerop (size
))
1219 /* Even though such uses of strlen would be undefined,
1220 avoid relying on arrays of arrays in case some genius
1221 decides to call strlen on an unterminated array element
1222 that's followed by a terminated one. Likewise, avoid
1223 assuming that a struct array member is necessarily
1224 nul-terminated (the nul may be in the member that
1225 follows). In those cases, assume that the length
1226 of the string stored in such an array is bounded
1227 by the size of the enclosing object if one can be
1229 tree base
= get_base_address (src
);
1232 if (tree size
= DECL_SIZE_UNIT (base
))
1234 && TREE_CODE (size
) == INTEGER_CST
1235 && TREE_CODE (TREE_TYPE (base
)) != POINTER_TYPE
)
1236 max
= wi::to_wide (size
);
1240 /* For strlen() the upper bound above is equal to
1241 the longest string that can be stored in the array
1242 (i.e., it accounts for the terminating nul. For
1243 strnlen() bump up the maximum by one since the array
1244 need not be nul-terminated. */
1245 if (!bound
&& max
!= 0)
1250 return set_strlen_range (lhs
, max
, bound
);
1253 /* Handle a strlen call. If strlen of the argument is known, replace
1254 the strlen call with the known value, otherwise remember that strlen
1255 of the argument is stored in the lhs SSA_NAME. */
1258 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
1260 gimple
*stmt
= gsi_stmt (*gsi
);
1261 tree lhs
= gimple_call_lhs (stmt
);
1263 if (lhs
== NULL_TREE
)
1266 location_t loc
= gimple_location (stmt
);
1267 tree callee
= gimple_call_fndecl (stmt
);
1268 tree src
= gimple_call_arg (stmt
, 0);
1269 tree bound
= (DECL_FUNCTION_CODE (callee
) == BUILT_IN_STRNLEN
1270 ? gimple_call_arg (stmt
, 1) : NULL_TREE
);
1271 int idx
= get_stridx (src
);
1278 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
1282 si
= get_strinfo (idx
);
1284 rhs
= get_string_length (si
);
1286 if (rhs
!= NULL_TREE
)
1288 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1290 fprintf (dump_file
, "Optimizing: ");
1291 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1293 rhs
= unshare_expr (rhs
);
1294 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
1295 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1297 /* Set for strnlen() calls with a non-constant bound. */
1298 bool noncst_bound
= false;
1302 = fold_build2_loc (loc
, MIN_EXPR
, TREE_TYPE (rhs
), rhs
, bound
);
1304 noncst_bound
= (TREE_CODE (new_rhs
) != INTEGER_CST
1305 || tree_int_cst_lt (new_rhs
, rhs
));
1310 if (!update_call_from_tree (gsi
, rhs
))
1311 gimplify_and_update_call_from_tree (gsi
, rhs
);
1312 stmt
= gsi_stmt (*gsi
);
1314 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1316 fprintf (dump_file
, "into: ");
1317 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1320 /* Avoid storing the length for calls to strnlen() with
1321 a non-constant bound. */
1326 && TREE_CODE (si
->nonzero_chars
) != SSA_NAME
1327 && TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
1328 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1330 si
= unshare_strinfo (si
);
1331 si
->nonzero_chars
= lhs
;
1332 gcc_assert (si
->full_string_p
);
1335 if (strlen_to_stridx
)
1336 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1341 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1345 idx
= new_stridx (src
);
1348 strinfo
*si
= get_strinfo (idx
);
1351 if (!si
->full_string_p
&& !si
->stmt
)
1353 /* Until now we only had a lower bound on the string length.
1354 Install LHS as the actual length. */
1355 si
= unshare_strinfo (si
);
1356 tree old
= si
->nonzero_chars
;
1357 si
->nonzero_chars
= lhs
;
1358 si
->full_string_p
= true;
1359 if (TREE_CODE (old
) == INTEGER_CST
)
1361 old
= fold_convert_loc (loc
, TREE_TYPE (lhs
), old
);
1362 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1363 TREE_TYPE (lhs
), lhs
, old
);
1364 adjust_related_strinfos (loc
, si
, adj
);
1380 /* Only store the new length information for calls to strlen(),
1381 not for those to strnlen(). */
1382 strinfo
*si
= new_strinfo (src
, idx
, lhs
, true);
1383 set_strinfo (idx
, si
);
1384 find_equal_ptrs (src
, idx
);
1387 /* For SRC that is an array of N elements, set LHS's range
1388 to [0, min (N, BOUND)]. A constant return value means
1389 the range would have consisted of a single value. In
1390 that case, fold the result into the returned constant. */
1391 if (tree ret
= maybe_set_strlen_range (lhs
, src
, bound
))
1392 if (TREE_CODE (ret
) == INTEGER_CST
)
1394 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1396 fprintf (dump_file
, "Optimizing: ");
1397 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1399 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (ret
)))
1400 ret
= fold_convert_loc (loc
, TREE_TYPE (lhs
), ret
);
1401 if (!update_call_from_tree (gsi
, ret
))
1402 gimplify_and_update_call_from_tree (gsi
, ret
);
1403 stmt
= gsi_stmt (*gsi
);
1405 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1407 fprintf (dump_file
, "into: ");
1408 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1412 if (strlen_to_stridx
&& !bound
)
1413 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1417 /* Handle a strchr call. If strlen of the first argument is known, replace
1418 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
1419 that lhs of the call is endptr and strlen of the argument is endptr - x. */
1422 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
1426 gimple
*stmt
= gsi_stmt (*gsi
);
1427 tree lhs
= gimple_call_lhs (stmt
);
1429 if (lhs
== NULL_TREE
)
1432 if (!integer_zerop (gimple_call_arg (stmt
, 1)))
1435 src
= gimple_call_arg (stmt
, 0);
1436 idx
= get_stridx (src
);
1443 rhs
= build_int_cst (size_type_node
, ~idx
);
1447 si
= get_strinfo (idx
);
1449 rhs
= get_string_length (si
);
1451 if (rhs
!= NULL_TREE
)
1453 location_t loc
= gimple_location (stmt
);
1455 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1457 fprintf (dump_file
, "Optimizing: ");
1458 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1460 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
1462 rhs
= unshare_expr (si
->endptr
);
1463 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1465 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1469 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1470 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1471 TREE_TYPE (src
), src
, rhs
);
1472 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1474 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1476 if (!update_call_from_tree (gsi
, rhs
))
1477 gimplify_and_update_call_from_tree (gsi
, rhs
);
1478 stmt
= gsi_stmt (*gsi
);
1480 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1482 fprintf (dump_file
, "into: ");
1483 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1486 && si
->endptr
== NULL_TREE
1487 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1489 si
= unshare_strinfo (si
);
1492 zero_length_string (lhs
, si
);
1496 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1498 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1501 idx
= new_stridx (src
);
1502 else if (get_strinfo (idx
) != NULL
)
1504 zero_length_string (lhs
, NULL
);
1509 location_t loc
= gimple_location (stmt
);
1510 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1511 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1512 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1513 size_type_node
, lhsu
, srcu
);
1514 strinfo
*si
= new_strinfo (src
, idx
, length
, true);
1516 set_strinfo (idx
, si
);
1517 find_equal_ptrs (src
, idx
);
1518 zero_length_string (lhs
, si
);
1522 zero_length_string (lhs
, NULL
);
1525 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1526 If strlen of the second argument is known, strlen of the first argument
1527 is the same after this call. Furthermore, attempt to convert it to
1531 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1534 tree src
, dst
, srclen
, len
, lhs
, type
, fn
, oldlen
;
1536 gimple
*stmt
= gsi_stmt (*gsi
);
1537 strinfo
*si
, *dsi
, *olddsi
, *zsi
;
1540 src
= gimple_call_arg (stmt
, 1);
1541 dst
= gimple_call_arg (stmt
, 0);
1542 lhs
= gimple_call_lhs (stmt
);
1543 idx
= get_stridx (src
);
1546 si
= get_strinfo (idx
);
1548 didx
= get_stridx (dst
);
1552 olddsi
= get_strinfo (didx
);
1557 adjust_last_stmt (olddsi
, stmt
, false);
1561 srclen
= get_string_length (si
);
1563 srclen
= build_int_cst (size_type_node
, ~idx
);
1565 loc
= gimple_location (stmt
);
1566 if (srclen
== NULL_TREE
)
1569 case BUILT_IN_STRCPY
:
1570 case BUILT_IN_STRCPY_CHK
:
1571 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1574 case BUILT_IN_STPCPY
:
1575 case BUILT_IN_STPCPY_CHK
:
1576 if (lhs
== NULL_TREE
)
1580 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1581 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1582 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1592 didx
= new_stridx (dst
);
1598 oldlen
= olddsi
->nonzero_chars
;
1599 dsi
= unshare_strinfo (olddsi
);
1600 dsi
->nonzero_chars
= srclen
;
1601 dsi
->full_string_p
= (srclen
!= NULL_TREE
);
1602 /* Break the chain, so adjust_related_strinfo on later pointers in
1603 the chain won't adjust this one anymore. */
1606 dsi
->endptr
= NULL_TREE
;
1610 dsi
= new_strinfo (dst
, didx
, srclen
, srclen
!= NULL_TREE
);
1611 set_strinfo (didx
, dsi
);
1612 find_equal_ptrs (dst
, didx
);
1614 dsi
->writable
= true;
1615 dsi
->dont_invalidate
= true;
1617 if (dsi
->nonzero_chars
== NULL_TREE
)
1621 /* If string length of src is unknown, use delayed length
1622 computation. If string lenth of dst will be needed, it
1623 can be computed by transforming this strcpy call into
1624 stpcpy and subtracting dst from the return value. */
1626 /* Look for earlier strings whose length could be determined if
1627 this strcpy is turned into an stpcpy. */
1629 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1631 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1633 /* When setting a stmt for delayed length computation
1634 prevent all strinfos through dsi from being
1636 chainsi
= unshare_strinfo (chainsi
);
1637 chainsi
->stmt
= stmt
;
1638 chainsi
->nonzero_chars
= NULL_TREE
;
1639 chainsi
->full_string_p
= false;
1640 chainsi
->endptr
= NULL_TREE
;
1641 chainsi
->dont_invalidate
= true;
1646 /* Try to detect overlap before returning. This catches cases
1647 like strcpy (d, d + n) where n is non-constant whose range
1648 is such that (n <= strlen (d) holds).
1650 OLDDSI->NONZERO_chars may have been reset by this point with
1651 oldlen holding it original value. */
1652 if (olddsi
&& oldlen
)
1654 /* Add 1 for the terminating NUL. */
1655 tree type
= TREE_TYPE (oldlen
);
1656 oldlen
= fold_build2 (PLUS_EXPR
, type
, oldlen
,
1657 build_int_cst (type
, 1));
1658 check_bounds_or_overlap (stmt
, olddsi
->ptr
, src
, oldlen
, NULL_TREE
);
1666 tree adj
= NULL_TREE
;
1667 if (oldlen
== NULL_TREE
)
1669 else if (integer_zerop (oldlen
))
1671 else if (TREE_CODE (oldlen
) == INTEGER_CST
1672 || TREE_CODE (srclen
) == INTEGER_CST
)
1673 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1674 TREE_TYPE (srclen
), srclen
,
1675 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1677 if (adj
!= NULL_TREE
)
1678 adjust_related_strinfos (loc
, dsi
, adj
);
1682 /* strcpy src may not overlap dst, so src doesn't need to be
1683 invalidated either. */
1685 si
->dont_invalidate
= true;
1691 case BUILT_IN_STRCPY
:
1692 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1694 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1696 case BUILT_IN_STRCPY_CHK
:
1697 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1699 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1701 case BUILT_IN_STPCPY
:
1702 /* This would need adjustment of the lhs (subtract one),
1703 or detection that the trailing '\0' doesn't need to be
1704 written, if it will be immediately overwritten.
1705 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1709 zsi
= zero_length_string (lhs
, dsi
);
1712 case BUILT_IN_STPCPY_CHK
:
1713 /* This would need adjustment of the lhs (subtract one),
1714 or detection that the trailing '\0' doesn't need to be
1715 written, if it will be immediately overwritten.
1716 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1720 zsi
= zero_length_string (lhs
, dsi
);
1727 zsi
->dont_invalidate
= true;
1731 tree args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1732 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1735 type
= size_type_node
;
1737 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1738 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1740 /* Set the no-warning bit on the transformed statement? */
1741 bool set_no_warning
= false;
1743 if (const strinfo
*chksi
= olddsi
? olddsi
: dsi
)
1745 && check_bounds_or_overlap (stmt
, chksi
->ptr
, si
->ptr
, NULL_TREE
, len
))
1747 gimple_set_no_warning (stmt
, true);
1748 set_no_warning
= true;
1751 if (fn
== NULL_TREE
)
1754 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1756 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1758 fprintf (dump_file
, "Optimizing: ");
1759 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1761 if (gimple_call_num_args (stmt
) == 2)
1762 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1764 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1765 gimple_call_arg (stmt
, 2));
1768 stmt
= gsi_stmt (*gsi
);
1770 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1772 fprintf (dump_file
, "into: ");
1773 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1775 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1776 laststmt
.stmt
= stmt
;
1777 laststmt
.len
= srclen
;
1778 laststmt
.stridx
= dsi
->idx
;
1780 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1781 fprintf (dump_file
, "not possible.\n");
1784 gimple_set_no_warning (stmt
, true);
1787 /* Check the size argument to the built-in forms of stpncpy and strncpy
1788 for out-of-bounds offsets or overlapping access, and to see if the
1789 size argument is derived from a call to strlen() on the source argument,
1790 and if so, issue an appropriate warning. */
1793 handle_builtin_strncat (built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1795 /* Same as stxncpy(). */
1796 handle_builtin_stxncpy (bcode
, gsi
);
1799 /* Return true if LEN depends on a call to strlen(SRC) in an interesting
1800 way. LEN can either be an integer expression, or a pointer (to char).
1801 When it is the latter (such as in recursive calls to self) is is
1802 assumed to be the argument in some call to strlen() whose relationship
1803 to SRC is being ascertained. */
1806 is_strlen_related_p (tree src
, tree len
)
1808 if (TREE_CODE (TREE_TYPE (len
)) == POINTER_TYPE
1809 && operand_equal_p (src
, len
, 0))
1812 if (TREE_CODE (len
) != SSA_NAME
)
1815 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1819 if (is_gimple_call (def_stmt
))
1821 tree func
= gimple_call_fndecl (def_stmt
);
1822 if (!valid_builtin_call (def_stmt
)
1823 || DECL_FUNCTION_CODE (func
) != BUILT_IN_STRLEN
)
1826 tree arg
= gimple_call_arg (def_stmt
, 0);
1827 return is_strlen_related_p (src
, arg
);
1830 if (!is_gimple_assign (def_stmt
))
1833 tree_code code
= gimple_assign_rhs_code (def_stmt
);
1834 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1835 tree rhstype
= TREE_TYPE (rhs1
);
1837 if ((TREE_CODE (rhstype
) == POINTER_TYPE
&& code
== POINTER_PLUS_EXPR
)
1838 || (INTEGRAL_TYPE_P (rhstype
)
1839 && (code
== BIT_AND_EXPR
1840 || code
== NOP_EXPR
)))
1842 /* Pointer plus (an integer), and truncation are considered among
1843 the (potentially) related expressions to strlen. */
1844 return is_strlen_related_p (src
, rhs1
);
1847 if (tree rhs2
= gimple_assign_rhs2 (def_stmt
))
1849 /* Integer subtraction is considered strlen-related when both
1850 arguments are integers and second one is strlen-related. */
1851 rhstype
= TREE_TYPE (rhs2
);
1852 if (INTEGRAL_TYPE_P (rhstype
) && code
== MINUS_EXPR
)
1853 return is_strlen_related_p (src
, rhs2
);
1859 /* Called by handle_builtin_stxncpy and by gimple_fold_builtin_strncpy
1861 Check to see if the specified bound is a) equal to the size of
1862 the destination DST and if so, b) if it's immediately followed by
1863 DST[CNT - 1] = '\0'. If a) holds and b) does not, warn. Otherwise,
1864 do nothing. Return true if diagnostic has been issued.
1866 The purpose is to diagnose calls to strncpy and stpncpy that do
1867 not nul-terminate the copy while allowing for the idiom where
1868 such a call is immediately followed by setting the last element
1871 strncpy (a, s, sizeof a);
1872 a[sizeof a - 1] = '\0';
1876 maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi
, tree src
, tree cnt
)
1878 gimple
*stmt
= gsi_stmt (gsi
);
1879 if (gimple_no_warning_p (stmt
))
1882 wide_int cntrange
[2];
1884 if (TREE_CODE (cnt
) == INTEGER_CST
)
1885 cntrange
[0] = cntrange
[1] = wi::to_wide (cnt
);
1886 else if (TREE_CODE (cnt
) == SSA_NAME
)
1888 enum value_range_kind rng
= get_range_info (cnt
, cntrange
, cntrange
+ 1);
1889 if (rng
== VR_RANGE
)
1891 else if (rng
== VR_ANTI_RANGE
)
1893 wide_int maxobjsize
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
));
1895 if (wi::ltu_p (cntrange
[1], maxobjsize
))
1897 cntrange
[0] = cntrange
[1] + 1;
1898 cntrange
[1] = maxobjsize
;
1902 cntrange
[1] = cntrange
[0] - 1;
1903 cntrange
[0] = wi::zero (TYPE_PRECISION (TREE_TYPE (cnt
)));
1912 /* Negative value is the constant string length. If it's less than
1913 the lower bound there is no truncation. Avoid calling get_stridx()
1914 when ssa_ver_to_stridx is empty. That implies the caller isn't
1915 running under the control of this pass and ssa_ver_to_stridx hasn't
1916 been created yet. */
1917 int sidx
= ssa_ver_to_stridx
.length () ? get_stridx (src
) : 0;
1918 if (sidx
< 0 && wi::gtu_p (cntrange
[0], ~sidx
))
1921 tree dst
= gimple_call_arg (stmt
, 0);
1923 if (TREE_CODE (dstdecl
) == ADDR_EXPR
)
1924 dstdecl
= TREE_OPERAND (dstdecl
, 0);
1926 tree ref
= NULL_TREE
;
1930 /* If the source is a non-string return early to avoid warning
1931 for possible truncation (if the truncation is certain SIDX
1933 tree srcdecl
= gimple_call_arg (stmt
, 1);
1934 if (TREE_CODE (srcdecl
) == ADDR_EXPR
)
1935 srcdecl
= TREE_OPERAND (srcdecl
, 0);
1936 if (get_attr_nonstring_decl (srcdecl
, &ref
))
1940 /* Likewise, if the destination refers to a an array/pointer declared
1941 nonstring return early. */
1942 if (get_attr_nonstring_decl (dstdecl
, &ref
))
1945 /* Look for dst[i] = '\0'; after the stxncpy() call and if found
1946 avoid the truncation warning. */
1947 gsi_next_nondebug (&gsi
);
1948 gimple
*next_stmt
= gsi_stmt (gsi
);
1951 /* When there is no statement in the same basic block check
1952 the immediate successor block. */
1953 if (basic_block bb
= gimple_bb (stmt
))
1955 if (single_succ_p (bb
))
1957 /* For simplicity, ignore blocks with multiple outgoing
1958 edges for now and only consider successor blocks along
1960 edge e
= EDGE_SUCC (bb
, 0);
1961 if (!(e
->flags
& EDGE_ABNORMAL
))
1963 gsi
= gsi_start_bb (e
->dest
);
1964 next_stmt
= gsi_stmt (gsi
);
1965 if (next_stmt
&& is_gimple_debug (next_stmt
))
1967 gsi_next_nondebug (&gsi
);
1968 next_stmt
= gsi_stmt (gsi
);
1975 if (next_stmt
&& is_gimple_assign (next_stmt
))
1977 tree lhs
= gimple_assign_lhs (next_stmt
);
1978 tree_code code
= TREE_CODE (lhs
);
1979 if (code
== ARRAY_REF
|| code
== MEM_REF
)
1980 lhs
= TREE_OPERAND (lhs
, 0);
1982 tree func
= gimple_call_fndecl (stmt
);
1983 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STPNCPY
)
1985 tree ret
= gimple_call_lhs (stmt
);
1986 if (ret
&& operand_equal_p (ret
, lhs
, 0))
1990 /* Determine the base address and offset of the reference,
1991 ignoring the innermost array index. */
1992 if (TREE_CODE (ref
) == ARRAY_REF
)
1993 ref
= TREE_OPERAND (ref
, 0);
1996 tree dstbase
= get_addr_base_and_unit_offset (ref
, &dstoff
);
1999 tree lhsbase
= get_addr_base_and_unit_offset (lhs
, &lhsoff
);
2002 && known_eq (dstoff
, lhsoff
)
2003 && operand_equal_p (dstbase
, lhsbase
, 0))
2007 int prec
= TYPE_PRECISION (TREE_TYPE (cnt
));
2008 wide_int lenrange
[2];
2009 if (strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
)
2011 lenrange
[0] = (sisrc
->nonzero_chars
2012 && TREE_CODE (sisrc
->nonzero_chars
) == INTEGER_CST
2013 ? wi::to_wide (sisrc
->nonzero_chars
)
2015 lenrange
[1] = lenrange
[0];
2018 lenrange
[0] = lenrange
[1] = wi::shwi (~sidx
, prec
);
2021 c_strlen_data lendata
= { };
2022 get_range_strlen (src
, &lendata
, /* eltsize = */1);
2023 if (TREE_CODE (lendata
.minlen
) == INTEGER_CST
2024 && TREE_CODE (lendata
.maxbound
) == INTEGER_CST
)
2026 /* When LENDATA.MAXLEN is unknown, reset LENDATA.MINLEN
2027 which stores the length of the shortest known string. */
2028 if (integer_all_onesp (lendata
.maxlen
))
2029 lenrange
[0] = wi::shwi (0, prec
);
2031 lenrange
[0] = wi::to_wide (lendata
.minlen
, prec
);
2032 lenrange
[1] = wi::to_wide (lendata
.maxbound
, prec
);
2036 lenrange
[0] = wi::shwi (0, prec
);
2037 lenrange
[1] = wi::shwi (-1, prec
);
2041 location_t callloc
= gimple_nonartificial_location (stmt
);
2042 callloc
= expansion_point_location_if_in_system_header (callloc
);
2044 tree func
= gimple_call_fndecl (stmt
);
2046 if (lenrange
[0] != 0 || !wi::neg_p (lenrange
[1]))
2048 /* If the longest source string is shorter than the lower bound
2049 of the specified count the copy is definitely nul-terminated. */
2050 if (wi::ltu_p (lenrange
[1], cntrange
[0]))
2053 if (wi::neg_p (lenrange
[1]))
2055 /* The length of one of the strings is unknown but at least
2056 one has non-zero length and that length is stored in
2057 LENRANGE[1]. Swap the bounds to force a "may be truncated"
2059 lenrange
[1] = lenrange
[0];
2060 lenrange
[0] = wi::shwi (0, prec
);
2063 /* Set to true for strncat whose bound is derived from the length
2064 of the destination (the expected usage pattern). */
2065 bool cat_dstlen_bounded
= false;
2066 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STRNCAT
)
2067 cat_dstlen_bounded
= is_strlen_related_p (dst
, cnt
);
2069 if (lenrange
[0] == cntrange
[1] && cntrange
[0] == cntrange
[1])
2070 return warning_n (callloc
, OPT_Wstringop_truncation
,
2071 cntrange
[0].to_uhwi (),
2072 "%G%qD output truncated before terminating "
2073 "nul copying %E byte from a string of the "
2075 "%G%qD output truncated before terminating nul "
2076 "copying %E bytes from a string of the same "
2079 else if (!cat_dstlen_bounded
)
2081 if (wi::geu_p (lenrange
[0], cntrange
[1]))
2083 /* The shortest string is longer than the upper bound of
2084 the count so the truncation is certain. */
2085 if (cntrange
[0] == cntrange
[1])
2086 return warning_n (callloc
, OPT_Wstringop_truncation
,
2087 cntrange
[0].to_uhwi (),
2088 "%G%qD output truncated copying %E byte "
2089 "from a string of length %wu",
2090 "%G%qD output truncated copying %E bytes "
2091 "from a string of length %wu",
2092 stmt
, func
, cnt
, lenrange
[0].to_uhwi ());
2094 return warning_at (callloc
, OPT_Wstringop_truncation
,
2095 "%G%qD output truncated copying between %wu "
2096 "and %wu bytes from a string of length %wu",
2097 stmt
, func
, cntrange
[0].to_uhwi (),
2098 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
2100 else if (wi::geu_p (lenrange
[1], cntrange
[1]))
2102 /* The longest string is longer than the upper bound of
2103 the count so the truncation is possible. */
2104 if (cntrange
[0] == cntrange
[1])
2105 return warning_n (callloc
, OPT_Wstringop_truncation
,
2106 cntrange
[0].to_uhwi (),
2107 "%G%qD output may be truncated copying %E "
2108 "byte from a string of length %wu",
2109 "%G%qD output may be truncated copying %E "
2110 "bytes from a string of length %wu",
2111 stmt
, func
, cnt
, lenrange
[1].to_uhwi ());
2113 return warning_at (callloc
, OPT_Wstringop_truncation
,
2114 "%G%qD output may be truncated copying between "
2115 "%wu and %wu bytes from a string of length %wu",
2116 stmt
, func
, cntrange
[0].to_uhwi (),
2117 cntrange
[1].to_uhwi (), lenrange
[1].to_uhwi ());
2121 if (!cat_dstlen_bounded
2122 && cntrange
[0] != cntrange
[1]
2123 && wi::leu_p (cntrange
[0], lenrange
[0])
2124 && wi::leu_p (cntrange
[1], lenrange
[0] + 1))
2126 /* If the source (including the terminating nul) is longer than
2127 the lower bound of the specified count but shorter than the
2128 upper bound the copy may (but need not) be truncated. */
2129 return warning_at (callloc
, OPT_Wstringop_truncation
,
2130 "%G%qD output may be truncated copying between "
2131 "%wu and %wu bytes from a string of length %wu",
2132 stmt
, func
, cntrange
[0].to_uhwi (),
2133 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
2137 if (tree dstsize
= compute_objsize (dst
, 1))
2139 /* The source length is uknown. Try to determine the destination
2140 size and see if it matches the specified bound. If not, bail.
2141 Otherwise go on to see if it should be diagnosed for possible
2146 if (wi::to_wide (dstsize
) != cntrange
[1])
2149 /* Avoid warning for strncpy(a, b, N) calls where the following
2151 N == sizeof a && N == sizeof b */
2152 if (tree srcsize
= compute_objsize (src
, 1))
2153 if (wi::to_wide (srcsize
) == cntrange
[1])
2156 if (cntrange
[0] == cntrange
[1])
2157 return warning_at (callloc
, OPT_Wstringop_truncation
,
2158 "%G%qD specified bound %E equals destination size",
2165 /* Check the arguments to the built-in forms of stpncpy and strncpy for
2166 out-of-bounds offsets or overlapping access, and to see if the size
2167 is derived from calling strlen() on the source argument, and if so,
2168 issue the appropriate warning. */
2171 handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*gsi
)
2173 if (!strlen_to_stridx
)
2176 gimple
*stmt
= gsi_stmt (*gsi
);
2178 tree dst
= gimple_call_arg (stmt
, 0);
2179 tree src
= gimple_call_arg (stmt
, 1);
2180 tree len
= gimple_call_arg (stmt
, 2);
2181 tree dstsize
= NULL_TREE
, srcsize
= NULL_TREE
;
2183 int didx
= get_stridx (dst
);
2184 if (strinfo
*sidst
= didx
> 0 ? get_strinfo (didx
) : NULL
)
2186 /* Compute the size of the destination string including the NUL. */
2187 if (sidst
->nonzero_chars
)
2189 tree type
= TREE_TYPE (sidst
->nonzero_chars
);
2190 dstsize
= fold_build2 (PLUS_EXPR
, type
, sidst
->nonzero_chars
,
2191 build_int_cst (type
, 1));
2196 int sidx
= get_stridx (src
);
2197 strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
;
2200 /* strncat() and strncpy() can modify the source string by writing
2201 over the terminating nul so SISRC->DONT_INVALIDATE must be left
2204 /* Compute the size of the source string including the NUL. */
2205 if (sisrc
->nonzero_chars
)
2207 tree type
= TREE_TYPE (sisrc
->nonzero_chars
);
2208 srcsize
= fold_build2 (PLUS_EXPR
, type
, sisrc
->nonzero_chars
,
2209 build_int_cst (type
, 1));
2215 srcsize
= NULL_TREE
;
2217 if (check_bounds_or_overlap (stmt
, dst
, src
, dstsize
, srcsize
))
2219 gimple_set_no_warning (stmt
, true);
2223 /* If the length argument was computed from strlen(S) for some string
2224 S retrieve the strinfo index for the string (PSS->FIRST) alonng with
2225 the location of the strlen() call (PSS->SECOND). */
2226 stridx_strlenloc
*pss
= strlen_to_stridx
->get (len
);
2227 if (!pss
|| pss
->first
<= 0)
2229 if (maybe_diag_stxncpy_trunc (*gsi
, src
, len
))
2230 gimple_set_no_warning (stmt
, true);
2235 /* Retrieve the strinfo data for the string S that LEN was computed
2236 from as some function F of strlen (S) (i.e., LEN need not be equal
2238 strinfo
*silen
= get_strinfo (pss
->first
);
2240 location_t callloc
= gimple_nonartificial_location (stmt
);
2241 callloc
= expansion_point_location_if_in_system_header (callloc
);
2243 tree func
= gimple_call_fndecl (stmt
);
2245 bool warned
= false;
2247 /* When -Wstringop-truncation is set, try to determine truncation
2248 before diagnosing possible overflow. Truncation is implied by
2249 the LEN argument being equal to strlen(SRC), regardless of
2250 whether its value is known. Otherwise, issue the more generic
2251 -Wstringop-overflow which triggers for LEN arguments that in
2252 any meaningful way depend on strlen(SRC). */
2254 && is_strlen_related_p (src
, len
)
2255 && warning_at (callloc
, OPT_Wstringop_truncation
,
2256 "%G%qD output truncated before terminating nul "
2257 "copying as many bytes from a string as its length",
2260 else if (silen
&& is_strlen_related_p (src
, silen
->ptr
))
2261 warned
= warning_at (callloc
, OPT_Wstringop_overflow_
,
2262 "%G%qD specified bound depends on the length "
2263 "of the source argument",
2267 location_t strlenloc
= pss
->second
;
2268 if (strlenloc
!= UNKNOWN_LOCATION
&& strlenloc
!= callloc
)
2269 inform (strlenloc
, "length computed here");
2273 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
2274 If strlen of the second argument is known and length of the third argument
2275 is that plus one, strlen of the first argument is the same after this
2279 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2282 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
2283 gimple
*stmt
= gsi_stmt (*gsi
);
2284 strinfo
*si
, *dsi
, *olddsi
;
2286 len
= gimple_call_arg (stmt
, 2);
2287 src
= gimple_call_arg (stmt
, 1);
2288 dst
= gimple_call_arg (stmt
, 0);
2289 idx
= get_stridx (src
);
2293 didx
= get_stridx (dst
);
2296 olddsi
= get_strinfo (didx
);
2301 && tree_fits_uhwi_p (len
)
2302 && !integer_zerop (len
))
2303 adjust_last_stmt (olddsi
, stmt
, false);
2310 /* Handle memcpy (x, y, l) where l's relationship with strlen (y)
2312 si
= get_strinfo (idx
);
2313 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
2315 if (TREE_CODE (len
) == INTEGER_CST
2316 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
2318 if (tree_int_cst_le (len
, si
->nonzero_chars
))
2320 /* Copying LEN nonzero characters, where LEN is constant. */
2322 full_string_p
= false;
2326 /* Copying the whole of the analyzed part of SI. */
2327 newlen
= si
->nonzero_chars
;
2328 full_string_p
= si
->full_string_p
;
2333 if (!si
->full_string_p
)
2335 if (TREE_CODE (len
) != SSA_NAME
)
2337 def_stmt
= SSA_NAME_DEF_STMT (len
);
2338 if (!is_gimple_assign (def_stmt
)
2339 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
2340 || gimple_assign_rhs1 (def_stmt
) != si
->nonzero_chars
2341 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
2343 /* Copying variable-length string SI (and no more). */
2344 newlen
= si
->nonzero_chars
;
2345 full_string_p
= true;
2351 /* Handle memcpy (x, "abcd", 5) or
2352 memcpy (x, "abc\0uvw", 7). */
2353 if (!tree_fits_uhwi_p (len
))
2356 unsigned HOST_WIDE_INT clen
= tree_to_uhwi (len
);
2357 unsigned HOST_WIDE_INT nonzero_chars
= ~idx
;
2358 newlen
= build_int_cst (size_type_node
, MIN (nonzero_chars
, clen
));
2359 full_string_p
= clen
> nonzero_chars
;
2364 && olddsi
->nonzero_chars
2365 && TREE_CODE (olddsi
->nonzero_chars
) == INTEGER_CST
2366 && tree_int_cst_le (newlen
, olddsi
->nonzero_chars
))
2368 /* The SRC substring being written strictly overlaps
2369 a subsequence of the existing string OLDDSI. */
2370 newlen
= olddsi
->nonzero_chars
;
2371 full_string_p
= olddsi
->full_string_p
;
2374 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
2375 adjust_last_stmt (olddsi
, stmt
, false);
2379 didx
= new_stridx (dst
);
2386 dsi
= unshare_strinfo (olddsi
);
2387 oldlen
= olddsi
->nonzero_chars
;
2388 dsi
->nonzero_chars
= newlen
;
2389 dsi
->full_string_p
= full_string_p
;
2390 /* Break the chain, so adjust_related_strinfo on later pointers in
2391 the chain won't adjust this one anymore. */
2394 dsi
->endptr
= NULL_TREE
;
2398 dsi
= new_strinfo (dst
, didx
, newlen
, full_string_p
);
2399 set_strinfo (didx
, dsi
);
2400 find_equal_ptrs (dst
, didx
);
2402 dsi
->writable
= true;
2403 dsi
->dont_invalidate
= true;
2406 tree adj
= NULL_TREE
;
2407 location_t loc
= gimple_location (stmt
);
2408 if (oldlen
== NULL_TREE
)
2410 else if (integer_zerop (oldlen
))
2412 else if (TREE_CODE (oldlen
) == INTEGER_CST
2413 || TREE_CODE (newlen
) == INTEGER_CST
)
2414 adj
= fold_build2_loc (loc
, MINUS_EXPR
, TREE_TYPE (newlen
), newlen
,
2415 fold_convert_loc (loc
, TREE_TYPE (newlen
),
2417 if (adj
!= NULL_TREE
)
2418 adjust_related_strinfos (loc
, dsi
, adj
);
2422 /* memcpy src may not overlap dst, so src doesn't need to be
2423 invalidated either. */
2425 si
->dont_invalidate
= true;
2429 lhs
= gimple_call_lhs (stmt
);
2432 case BUILT_IN_MEMCPY
:
2433 case BUILT_IN_MEMCPY_CHK
:
2434 /* Allow adjust_last_stmt to decrease this memcpy's size. */
2435 laststmt
.stmt
= stmt
;
2436 laststmt
.len
= dsi
->nonzero_chars
;
2437 laststmt
.stridx
= dsi
->idx
;
2439 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
2441 case BUILT_IN_MEMPCPY
:
2442 case BUILT_IN_MEMPCPY_CHK
:
2450 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
2451 If strlen of the second argument is known, strlen of the first argument
2452 is increased by the length of the second argument. Furthermore, attempt
2453 to convert it to memcpy/strcpy if the length of the first argument
2457 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2460 tree srclen
, args
, type
, fn
, objsz
, endptr
;
2462 gimple
*stmt
= gsi_stmt (*gsi
);
2464 location_t loc
= gimple_location (stmt
);
2466 tree src
= gimple_call_arg (stmt
, 1);
2467 tree dst
= gimple_call_arg (stmt
, 0);
2469 /* Bail if the source is the same as destination. It will be diagnosed
2471 if (operand_equal_p (src
, dst
, 0))
2474 tree lhs
= gimple_call_lhs (stmt
);
2476 didx
= get_stridx (dst
);
2482 dsi
= get_strinfo (didx
);
2486 idx
= get_stridx (src
);
2488 srclen
= build_int_cst (size_type_node
, ~idx
);
2491 si
= get_strinfo (idx
);
2493 srclen
= get_string_length (si
);
2496 /* Set the no-warning bit on the transformed statement? */
2497 bool set_no_warning
= false;
2499 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
2502 /* The concatenation always involves copying at least one byte
2503 (the terminating nul), even if the source string is empty.
2504 If the source is unknown assume it's one character long and
2505 used that as both sizes. */
2509 tree type
= TREE_TYPE (slen
);
2510 slen
= fold_build2 (PLUS_EXPR
, type
, slen
, build_int_cst (type
, 1));
2513 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2515 if (check_bounds_or_overlap (stmt
, dst
, sptr
, NULL_TREE
, slen
))
2517 gimple_set_no_warning (stmt
, true);
2518 set_no_warning
= true;
2522 /* strcat (p, q) can be transformed into
2523 tmp = p + strlen (p); endptr = stpcpy (tmp, q);
2524 with length endptr - p if we need to compute the length
2525 later on. Don't do this transformation if we don't need
2527 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
2531 didx
= new_stridx (dst
);
2537 dsi
= new_strinfo (dst
, didx
, NULL_TREE
, false);
2538 set_strinfo (didx
, dsi
);
2539 find_equal_ptrs (dst
, didx
);
2543 dsi
= unshare_strinfo (dsi
);
2544 dsi
->nonzero_chars
= NULL_TREE
;
2545 dsi
->full_string_p
= false;
2547 dsi
->endptr
= NULL_TREE
;
2549 dsi
->writable
= true;
2551 dsi
->dont_invalidate
= true;
2556 tree dstlen
= dsi
->nonzero_chars
;
2557 endptr
= dsi
->endptr
;
2559 dsi
= unshare_strinfo (dsi
);
2560 dsi
->endptr
= NULL_TREE
;
2562 dsi
->writable
= true;
2564 if (srclen
!= NULL_TREE
)
2566 dsi
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
2567 TREE_TYPE (dsi
->nonzero_chars
),
2568 dsi
->nonzero_chars
, srclen
);
2569 gcc_assert (dsi
->full_string_p
);
2570 adjust_related_strinfos (loc
, dsi
, srclen
);
2571 dsi
->dont_invalidate
= true;
2575 dsi
->nonzero_chars
= NULL
;
2576 dsi
->full_string_p
= false;
2577 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
2578 dsi
->dont_invalidate
= true;
2582 /* strcat src may not overlap dst, so src doesn't need to be
2583 invalidated either. */
2584 si
->dont_invalidate
= true;
2586 /* For now. Could remove the lhs from the call and add
2587 lhs = dst; afterwards. */
2595 case BUILT_IN_STRCAT
:
2596 if (srclen
!= NULL_TREE
)
2597 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
2599 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
2601 case BUILT_IN_STRCAT_CHK
:
2602 if (srclen
!= NULL_TREE
)
2603 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
2605 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
2606 objsz
= gimple_call_arg (stmt
, 2);
2612 if (fn
== NULL_TREE
)
2617 tree type
= TREE_TYPE (dstlen
);
2619 /* Compute the size of the source sequence, including the nul. */
2620 tree srcsize
= srclen
? srclen
: size_zero_node
;
2621 srcsize
= fold_build2 (PLUS_EXPR
, type
, srcsize
, build_int_cst (type
, 1));
2623 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2625 if (check_bounds_or_overlap (stmt
, dst
, sptr
, dstlen
, srcsize
))
2627 gimple_set_no_warning (stmt
, true);
2628 set_no_warning
= true;
2632 tree len
= NULL_TREE
;
2633 if (srclen
!= NULL_TREE
)
2635 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
2636 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
2638 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
2639 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
2640 build_int_cst (type
, 1));
2641 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
2645 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
2647 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
, TREE_TYPE (dst
), dst
,
2648 fold_convert_loc (loc
, sizetype
,
2649 unshare_expr (dstlen
)));
2650 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
2654 objsz
= fold_build2_loc (loc
, MINUS_EXPR
, TREE_TYPE (objsz
), objsz
,
2655 fold_convert_loc (loc
, TREE_TYPE (objsz
),
2656 unshare_expr (dstlen
)));
2657 objsz
= force_gimple_operand_gsi (gsi
, objsz
, true, NULL_TREE
, true,
2660 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2662 fprintf (dump_file
, "Optimizing: ");
2663 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2665 if (srclen
!= NULL_TREE
)
2666 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
2667 dst
, src
, len
, objsz
);
2669 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
2673 stmt
= gsi_stmt (*gsi
);
2675 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2677 fprintf (dump_file
, "into: ");
2678 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2680 /* If srclen == NULL, note that current string length can be
2681 computed by transforming this strcpy into stpcpy. */
2682 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
2684 adjust_last_stmt (dsi
, stmt
, true);
2685 if (srclen
!= NULL_TREE
)
2687 laststmt
.stmt
= stmt
;
2688 laststmt
.len
= srclen
;
2689 laststmt
.stridx
= dsi
->idx
;
2692 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2693 fprintf (dump_file
, "not possible.\n");
2696 gimple_set_no_warning (stmt
, true);
2699 /* Handle a call to malloc or calloc. */
2702 handle_builtin_malloc (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2704 gimple
*stmt
= gsi_stmt (*gsi
);
2705 tree lhs
= gimple_call_lhs (stmt
);
2706 if (lhs
== NULL_TREE
)
2709 gcc_assert (get_stridx (lhs
) == 0);
2710 int idx
= new_stridx (lhs
);
2711 tree length
= NULL_TREE
;
2712 if (bcode
== BUILT_IN_CALLOC
)
2713 length
= build_int_cst (size_type_node
, 0);
2714 strinfo
*si
= new_strinfo (lhs
, idx
, length
, length
!= NULL_TREE
);
2715 if (bcode
== BUILT_IN_CALLOC
)
2717 set_strinfo (idx
, si
);
2718 si
->writable
= true;
2720 si
->dont_invalidate
= true;
2723 /* Handle a call to memset.
2724 After a call to calloc, memset(,0,) is unnecessary.
2725 memset(malloc(n),0,n) is calloc(n,1).
2726 return true when the call is transfomred, false otherwise. */
2729 handle_builtin_memset (gimple_stmt_iterator
*gsi
)
2731 gimple
*stmt2
= gsi_stmt (*gsi
);
2732 if (!integer_zerop (gimple_call_arg (stmt2
, 1)))
2734 tree ptr
= gimple_call_arg (stmt2
, 0);
2735 int idx1
= get_stridx (ptr
);
2738 strinfo
*si1
= get_strinfo (idx1
);
2741 gimple
*stmt1
= si1
->stmt
;
2742 if (!stmt1
|| !is_gimple_call (stmt1
))
2744 tree callee1
= gimple_call_fndecl (stmt1
);
2745 if (!valid_builtin_call (stmt1
))
2747 enum built_in_function code1
= DECL_FUNCTION_CODE (callee1
);
2748 tree size
= gimple_call_arg (stmt2
, 2);
2749 if (code1
== BUILT_IN_CALLOC
)
2750 /* Not touching stmt1 */ ;
2751 else if (code1
== BUILT_IN_MALLOC
2752 && operand_equal_p (gimple_call_arg (stmt1
, 0), size
, 0))
2754 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt1
);
2755 update_gimple_call (&gsi1
, builtin_decl_implicit (BUILT_IN_CALLOC
), 2,
2756 size
, build_one_cst (size_type_node
));
2757 si1
->nonzero_chars
= build_int_cst (size_type_node
, 0);
2758 si1
->full_string_p
= true;
2759 si1
->stmt
= gsi_stmt (gsi1
);
2763 tree lhs
= gimple_call_lhs (stmt2
);
2764 unlink_stmt_vdef (stmt2
);
2767 gimple
*assign
= gimple_build_assign (lhs
, ptr
);
2768 gsi_replace (gsi
, assign
, false);
2772 gsi_remove (gsi
, true);
2773 release_defs (stmt2
);
2779 /* Handle a call to memcmp. We try to handle small comparisons by
2780 converting them to load and compare, and replacing the call to memcmp
2781 with a __builtin_memcmp_eq call where possible.
2782 return true when call is transformed, return false otherwise. */
2785 handle_builtin_memcmp (gimple_stmt_iterator
*gsi
)
2787 gcall
*stmt2
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2788 tree res
= gimple_call_lhs (stmt2
);
2789 tree arg1
= gimple_call_arg (stmt2
, 0);
2790 tree arg2
= gimple_call_arg (stmt2
, 1);
2791 tree len
= gimple_call_arg (stmt2
, 2);
2792 unsigned HOST_WIDE_INT leni
;
2793 use_operand_p use_p
;
2794 imm_use_iterator iter
;
2799 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
2801 gimple
*ustmt
= USE_STMT (use_p
);
2803 if (is_gimple_debug (ustmt
))
2805 if (gimple_code (ustmt
) == GIMPLE_ASSIGN
)
2807 gassign
*asgn
= as_a
<gassign
*> (ustmt
);
2808 tree_code code
= gimple_assign_rhs_code (asgn
);
2809 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2810 || !integer_zerop (gimple_assign_rhs2 (asgn
)))
2813 else if (gimple_code (ustmt
) == GIMPLE_COND
)
2815 tree_code code
= gimple_cond_code (ustmt
);
2816 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2817 || !integer_zerop (gimple_cond_rhs (ustmt
)))
2824 if (tree_fits_uhwi_p (len
)
2825 && (leni
= tree_to_uhwi (len
)) <= GET_MODE_SIZE (word_mode
)
2826 && pow2p_hwi (leni
))
2828 leni
*= CHAR_TYPE_SIZE
;
2829 unsigned align1
= get_pointer_alignment (arg1
);
2830 unsigned align2
= get_pointer_alignment (arg2
);
2831 unsigned align
= MIN (align1
, align2
);
2832 scalar_int_mode mode
;
2833 if (int_mode_for_size (leni
, 1).exists (&mode
)
2834 && (align
>= leni
|| !targetm
.slow_unaligned_access (mode
, align
)))
2836 location_t loc
= gimple_location (stmt2
);
2838 type
= build_nonstandard_integer_type (leni
, 1);
2839 gcc_assert (known_eq (GET_MODE_BITSIZE (TYPE_MODE (type
)), leni
));
2840 tree ptrtype
= build_pointer_type_for_mode (char_type_node
,
2842 off
= build_int_cst (ptrtype
, 0);
2843 arg1
= build2_loc (loc
, MEM_REF
, type
, arg1
, off
);
2844 arg2
= build2_loc (loc
, MEM_REF
, type
, arg2
, off
);
2845 tree tem1
= fold_const_aggregate_ref (arg1
);
2848 tree tem2
= fold_const_aggregate_ref (arg2
);
2851 res
= fold_convert_loc (loc
, TREE_TYPE (res
),
2852 fold_build2_loc (loc
, NE_EXPR
,
2855 gimplify_and_update_call_from_tree (gsi
, res
);
2860 gimple_call_set_fndecl (stmt2
, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ
));
2864 /* Given an index to the strinfo vector, compute the string length for the
2865 corresponding string. Return -1 when unknown. */
2867 static HOST_WIDE_INT
2868 compute_string_length (int idx
)
2870 HOST_WIDE_INT string_leni
= -1;
2871 gcc_assert (idx
!= 0);
2876 strinfo
*si
= get_strinfo (idx
);
2879 tree const_string_len
= get_string_length (si
);
2880 if (const_string_len
&& tree_fits_shwi_p (const_string_len
))
2881 string_leni
= tree_to_shwi (const_string_len
);
2884 if (string_leni
< 0)
2890 /* Determine the minimum size of the object referenced by DEST expression which
2891 must have a pointer type.
2892 Return the minimum size of the object if successful or NULL when the size
2893 cannot be determined. */
2895 determine_min_objsize (tree dest
)
2897 unsigned HOST_WIDE_INT size
= 0;
2899 if (compute_builtin_object_size (dest
, 2, &size
))
2900 return build_int_cst (sizetype
, size
);
2902 /* Try to determine the size of the object through the RHS of the
2903 assign statement. */
2904 if (TREE_CODE (dest
) == SSA_NAME
)
2906 gimple
*stmt
= SSA_NAME_DEF_STMT (dest
);
2907 if (!is_gimple_assign (stmt
))
2910 if (!gimple_assign_single_p (stmt
)
2911 && !gimple_assign_unary_nop_p (stmt
))
2914 dest
= gimple_assign_rhs1 (stmt
);
2915 return determine_min_objsize (dest
);
2918 /* Try to determine the size of the object from its type. */
2919 if (TREE_CODE (dest
) != ADDR_EXPR
)
2922 tree type
= TREE_TYPE (dest
);
2923 if (TREE_CODE (type
) == POINTER_TYPE
)
2924 type
= TREE_TYPE (type
);
2926 type
= TYPE_MAIN_VARIANT (type
);
2928 /* We cannot determine the size of the array if it's a flexible array,
2929 which is declared at the end of a structure. */
2930 if (TREE_CODE (type
) == ARRAY_TYPE
2931 && !array_at_struct_end_p (dest
))
2933 tree
size_t = TYPE_SIZE_UNIT (type
);
2934 if (size_t && TREE_CODE (size_t) == INTEGER_CST
2935 && !integer_zerop (size_t))
2942 /* Handle a call to strcmp or strncmp. When the result is ONLY used to do
2943 equality test against zero:
2945 A. When the lengths of both arguments are constant and it's a strcmp:
2946 * if the lengths are NOT equal, we can safely fold the call
2947 to a non-zero value.
2948 * otherwise, do nothing now.
2950 B. When the length of one argument is constant, try to replace the call with
2951 a __builtin_str(n)cmp_eq call where possible, i.e:
2953 strncmp (s, STR, C) (!)= 0 in which, s is a pointer to a string, STR is a
2954 string with constant length , C is a constant.
2955 if (C <= strlen(STR) && sizeof_array(s) > C)
2957 replace this call with
2958 strncmp_eq (s, STR, C) (!)= 0
2962 it can be safely treated as a call to strcmp (s, STR) (!)= 0
2963 can handled by the following strcmp.
2966 strcmp (s, STR) (!)= 0 in which, s is a pointer to a string, STR is a
2967 string with constant length.
2968 if (sizeof_array(s) > strlen(STR))
2970 replace this call with
2971 strcmp_eq (s, STR, strlen(STR)+1) (!)= 0
2974 Return true when the call is transformed, return false otherwise.
2978 handle_builtin_string_cmp (gimple_stmt_iterator
*gsi
)
2980 gcall
*stmt
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2981 tree res
= gimple_call_lhs (stmt
);
2982 use_operand_p use_p
;
2983 imm_use_iterator iter
;
2984 tree arg1
= gimple_call_arg (stmt
, 0);
2985 tree arg2
= gimple_call_arg (stmt
, 1);
2986 int idx1
= get_stridx (arg1
);
2987 int idx2
= get_stridx (arg2
);
2988 HOST_WIDE_INT length
= -1;
2989 bool is_ncmp
= false;
2994 /* When both arguments are unknown, do nothing. */
2995 if (idx1
== 0 && idx2
== 0)
2998 /* Handle strncmp function. */
2999 if (gimple_call_num_args (stmt
) == 3)
3001 tree len
= gimple_call_arg (stmt
, 2);
3002 if (tree_fits_shwi_p (len
))
3003 length
= tree_to_shwi (len
);
3008 /* For strncmp, if the length argument is NOT known, do nothing. */
3009 if (is_ncmp
&& length
< 0)
3012 /* When the result is ONLY used to do equality test against zero. */
3013 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
3015 gimple
*use_stmt
= USE_STMT (use_p
);
3017 if (is_gimple_debug (use_stmt
))
3019 if (gimple_code (use_stmt
) == GIMPLE_ASSIGN
)
3021 tree_code code
= gimple_assign_rhs_code (use_stmt
);
3022 if (code
== COND_EXPR
)
3024 tree cond_expr
= gimple_assign_rhs1 (use_stmt
);
3025 if ((TREE_CODE (cond_expr
) != EQ_EXPR
3026 && (TREE_CODE (cond_expr
) != NE_EXPR
))
3027 || !integer_zerop (TREE_OPERAND (cond_expr
, 1)))
3030 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3032 if (!integer_zerop (gimple_assign_rhs2 (use_stmt
)))
3038 else if (gimple_code (use_stmt
) == GIMPLE_COND
)
3040 tree_code code
= gimple_cond_code (use_stmt
);
3041 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
3042 || !integer_zerop (gimple_cond_rhs (use_stmt
)))
3049 /* When the lengths of both arguments are known, and they are unequal, we can
3050 safely fold the call to a non-zero value for strcmp;
3051 othewise, do nothing now. */
3052 if (idx1
!= 0 && idx2
!= 0)
3054 HOST_WIDE_INT const_string_leni1
= compute_string_length (idx1
);
3055 HOST_WIDE_INT const_string_leni2
= compute_string_length (idx2
);
3058 && const_string_leni1
!= -1
3059 && const_string_leni2
!= -1
3060 && const_string_leni1
!= const_string_leni2
)
3062 replace_call_with_value (gsi
, integer_one_node
);
3068 /* When the length of one argument is constant. */
3069 tree var_string
= NULL_TREE
;
3070 HOST_WIDE_INT const_string_leni
= -1;
3074 const_string_leni
= compute_string_length (idx1
);
3079 gcc_checking_assert (idx2
);
3080 const_string_leni
= compute_string_length (idx2
);
3084 if (const_string_leni
< 0)
3087 unsigned HOST_WIDE_INT var_sizei
= 0;
3088 /* try to determine the minimum size of the object pointed by var_string. */
3089 tree size
= determine_min_objsize (var_string
);
3094 if (tree_fits_uhwi_p (size
))
3095 var_sizei
= tree_to_uhwi (size
);
3100 /* For strncmp, if length > const_string_leni , this call can be safely
3101 transformed to a strcmp. */
3102 if (is_ncmp
&& length
> const_string_leni
)
3105 unsigned HOST_WIDE_INT final_length
3106 = is_ncmp
? length
: const_string_leni
+ 1;
3108 /* Replace strcmp or strncmp with the corresponding str(n)cmp_eq. */
3109 if (var_sizei
> final_length
)
3113 ? builtin_decl_implicit (BUILT_IN_STRNCMP_EQ
)
3114 : builtin_decl_implicit (BUILT_IN_STRCMP_EQ
));
3117 tree const_string_len
= build_int_cst (size_type_node
, final_length
);
3118 update_gimple_call (gsi
, fn
, 3, arg1
, arg2
, const_string_len
);
3126 /* Handle a POINTER_PLUS_EXPR statement.
3127 For p = "abcd" + 2; compute associated length, or if
3128 p = q + off is pointing to a '\0' character of a string, call
3129 zero_length_string on it. */
3132 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
3134 gimple
*stmt
= gsi_stmt (*gsi
);
3135 tree lhs
= gimple_assign_lhs (stmt
), off
;
3136 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
3144 tree off
= gimple_assign_rhs2 (stmt
);
3145 if (tree_fits_uhwi_p (off
)
3146 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
3147 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
3148 = ~(~idx
- (int) tree_to_uhwi (off
));
3152 si
= get_strinfo (idx
);
3153 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
3156 off
= gimple_assign_rhs2 (stmt
);
3158 if (si
->full_string_p
&& operand_equal_p (si
->nonzero_chars
, off
, 0))
3159 zsi
= zero_length_string (lhs
, si
);
3160 else if (TREE_CODE (off
) == SSA_NAME
)
3162 gimple
*def_stmt
= SSA_NAME_DEF_STMT (off
);
3163 if (gimple_assign_single_p (def_stmt
)
3164 && si
->full_string_p
3165 && operand_equal_p (si
->nonzero_chars
,
3166 gimple_assign_rhs1 (def_stmt
), 0))
3167 zsi
= zero_length_string (lhs
, si
);
3170 && si
->endptr
!= NULL_TREE
3171 && si
->endptr
!= lhs
3172 && TREE_CODE (si
->endptr
) == SSA_NAME
)
3174 enum tree_code rhs_code
3175 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
3176 ? SSA_NAME
: NOP_EXPR
;
3177 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
);
3178 gcc_assert (gsi_stmt (*gsi
) == stmt
);
3183 /* If RHS, either directly or indirectly, refers to a string of constant
3184 length, return the length. Otherwise, if it refers to a character
3185 constant, return 1 if the constant is non-zero and 0 if it is nul.
3186 Otherwise, return a negative value. */
3188 static HOST_WIDE_INT
3189 get_min_string_length (tree rhs
, bool *full_string_p
)
3191 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs
)))
3193 if (tree_expr_nonzero_p (rhs
))
3195 *full_string_p
= false;
3199 *full_string_p
= true;
3203 if (TREE_CODE (rhs
) == MEM_REF
3204 && integer_zerop (TREE_OPERAND (rhs
, 1)))
3206 rhs
= TREE_OPERAND (rhs
, 0);
3207 if (TREE_CODE (rhs
) == ADDR_EXPR
)
3209 tree rhs_addr
= rhs
;
3211 rhs
= TREE_OPERAND (rhs
, 0);
3212 if (TREE_CODE (rhs
) != STRING_CST
)
3214 int idx
= get_stridx (rhs_addr
);
3217 strinfo
*si
= get_strinfo (idx
);
3219 && tree_fits_shwi_p (si
->nonzero_chars
))
3221 *full_string_p
= si
->full_string_p
;
3222 return tree_to_shwi (si
->nonzero_chars
);
3229 if (TREE_CODE (rhs
) == VAR_DECL
3230 && TREE_READONLY (rhs
))
3231 rhs
= DECL_INITIAL (rhs
);
3233 if (rhs
&& TREE_CODE (rhs
) == STRING_CST
)
3235 HOST_WIDE_INT len
= strlen (TREE_STRING_POINTER (rhs
));
3236 *full_string_p
= len
< TREE_STRING_LENGTH (rhs
);
3243 /* Handle a single or multiple character store either by single
3244 character assignment or by multi-character assignment from
3248 handle_char_store (gimple_stmt_iterator
*gsi
)
3252 gimple
*stmt
= gsi_stmt (*gsi
);
3253 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
3254 tree rhs
= gimple_assign_rhs1 (stmt
);
3255 unsigned HOST_WIDE_INT offset
= 0;
3257 if (TREE_CODE (lhs
) == MEM_REF
3258 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
3260 tree mem_offset
= TREE_OPERAND (lhs
, 1);
3261 if (tree_fits_uhwi_p (mem_offset
))
3263 /* Get the strinfo for the base, and use it if it starts with at
3264 least OFFSET nonzero characters. This is trivially true if
3266 offset
= tree_to_uhwi (mem_offset
);
3267 idx
= get_stridx (TREE_OPERAND (lhs
, 0));
3269 si
= get_strinfo (idx
);
3271 ssaname
= TREE_OPERAND (lhs
, 0);
3272 else if (si
== NULL
|| compare_nonzero_chars (si
, offset
) < 0)
3278 idx
= get_addr_stridx (lhs
, NULL_TREE
, &offset
);
3280 si
= get_strinfo (idx
);
3283 /* STORING_NONZERO_P is true iff not all stored characters are zero.
3284 STORING_ALL_ZEROS_P is true iff all stored characters are zero.
3285 Both are false when it's impossible to determine which is true. */
3286 bool storing_nonzero_p
;
3287 bool storing_all_zeros_p
= initializer_zerop (rhs
, &storing_nonzero_p
);
3288 if (!storing_nonzero_p
)
3289 storing_nonzero_p
= tree_expr_nonzero_p (rhs
);
3290 bool full_string_p
= storing_all_zeros_p
;
3292 /* Set to the length of the string being assigned if known. */
3293 HOST_WIDE_INT rhslen
;
3297 int cmp
= compare_nonzero_chars (si
, offset
);
3298 gcc_assert (offset
== 0 || cmp
>= 0);
3299 if (storing_all_zeros_p
&& cmp
== 0 && si
->full_string_p
)
3301 /* When overwriting a '\0' with a '\0', the store can be removed
3302 if we know it has been stored in the current function. */
3303 if (!stmt_could_throw_p (cfun
, stmt
) && si
->writable
)
3305 unlink_stmt_vdef (stmt
);
3306 release_defs (stmt
);
3307 gsi_remove (gsi
, true);
3312 si
->writable
= true;
3317 /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0',
3318 and if we aren't storing '\0', we know that the length of the
3319 string and any other zero terminated string in memory remains
3320 the same. In that case we move to the next gimple statement and
3321 return to signal the caller that it shouldn't invalidate anything.
3323 This is benefical for cases like:
3328 strcpy (p, "foobar");
3329 size_t len = strlen (p); // This can be optimized into 6
3330 size_t len2 = strlen (q); // This has to be computed
3332 size_t len3 = strlen (p); // This can be optimized into 6
3333 size_t len4 = strlen (q); // This can be optimized into len2
3334 bar (len, len2, len3, len4);
3337 else if (storing_nonzero_p
&& cmp
> 0)
3342 else if (storing_all_zeros_p
|| storing_nonzero_p
|| (offset
!= 0 && cmp
> 0))
3344 /* When STORING_NONZERO_P, we know that the string will start
3345 with at least OFFSET + 1 nonzero characters. If storing
3346 a single character, set si->NONZERO_CHARS to the result.
3347 If storing multiple characters, try to determine the number
3348 of leading non-zero characters and set si->NONZERO_CHARS to
3351 When STORING_ALL_ZEROS_P, we know that the string is now
3352 OFFSET characters long.
3354 Otherwise, we're storing an unknown value at offset OFFSET,
3355 so need to clip the nonzero_chars to OFFSET. */
3356 bool full_string_p
= storing_all_zeros_p
;
3357 HOST_WIDE_INT len
= 1;
3358 if (storing_nonzero_p
)
3360 /* Try to get the minimum length of the string (or
3361 individual character) being stored. If it fails,
3362 STORING_NONZERO_P guarantees it's at least 1. */
3363 len
= get_min_string_length (rhs
, &full_string_p
);
3368 location_t loc
= gimple_location (stmt
);
3369 tree oldlen
= si
->nonzero_chars
;
3370 if (cmp
== 0 && si
->full_string_p
)
3371 /* We're overwriting the nul terminator with a nonzero or
3372 unknown character. If the previous stmt was a memcpy,
3373 its length may be decreased. */
3374 adjust_last_stmt (si
, stmt
, false);
3375 si
= unshare_strinfo (si
);
3376 if (storing_nonzero_p
)
3378 gcc_assert (len
>= 0);
3379 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
+ len
);
3382 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
);
3383 si
->full_string_p
= full_string_p
;
3384 if (storing_all_zeros_p
3386 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
3387 si
->endptr
= ssaname
;
3392 si
->writable
= true;
3393 si
->dont_invalidate
= true;
3396 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
3397 si
->nonzero_chars
, oldlen
);
3398 adjust_related_strinfos (loc
, si
, adj
);
3404 else if (idx
== 0 && (storing_all_zeros_p
|| storing_nonzero_p
))
3407 idx
= new_stridx (ssaname
);
3409 idx
= new_addr_stridx (lhs
);
3412 tree ptr
= (ssaname
? ssaname
: build_fold_addr_expr (lhs
));
3413 HOST_WIDE_INT slen
= (storing_all_zeros_p
3415 : (storing_nonzero_p
3416 ? get_min_string_length (rhs
, &full_string_p
)
3418 tree len
= (slen
<= 0
3420 : build_int_cst (size_type_node
, slen
));
3421 si
= new_strinfo (ptr
, idx
, len
, slen
>= 0 && full_string_p
);
3422 set_strinfo (idx
, si
);
3423 if (storing_all_zeros_p
3425 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
3426 si
->endptr
= ssaname
;
3427 si
->dont_invalidate
= true;
3428 si
->writable
= true;
3432 && (rhslen
= get_min_string_length (rhs
, &full_string_p
)) >= 0
3433 && ssaname
== NULL_TREE
3434 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
3436 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
3437 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> (unsigned HOST_WIDE_INT
) rhslen
)
3439 int idx
= new_addr_stridx (lhs
);
3442 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
3443 build_int_cst (size_type_node
, rhslen
),
3445 set_strinfo (idx
, si
);
3446 si
->dont_invalidate
= true;
3451 if (si
!= NULL
&& offset
== 0 && storing_all_zeros_p
)
3453 /* Allow adjust_last_stmt to remove it if the stored '\0'
3454 is immediately overwritten. */
3455 laststmt
.stmt
= stmt
;
3456 laststmt
.len
= build_int_cst (size_type_node
, 1);
3457 laststmt
.stridx
= si
->idx
;
3462 /* Try to fold strstr (s, t) eq/ne s to strncmp (s, t, strlen (t)) eq/ne 0. */
3465 fold_strstr_to_strncmp (tree rhs1
, tree rhs2
, gimple
*stmt
)
3467 if (TREE_CODE (rhs1
) != SSA_NAME
3468 || TREE_CODE (rhs2
) != SSA_NAME
)
3471 gimple
*call_stmt
= NULL
;
3472 for (int pass
= 0; pass
< 2; pass
++)
3474 gimple
*g
= SSA_NAME_DEF_STMT (rhs1
);
3475 if (gimple_call_builtin_p (g
, BUILT_IN_STRSTR
)
3476 && has_single_use (rhs1
)
3477 && gimple_call_arg (g
, 0) == rhs2
)
3482 std::swap (rhs1
, rhs2
);
3487 tree arg0
= gimple_call_arg (call_stmt
, 0);
3491 tree arg1
= gimple_call_arg (call_stmt
, 1);
3492 tree arg1_len
= NULL_TREE
;
3493 int idx
= get_stridx (arg1
);
3498 arg1_len
= build_int_cst (size_type_node
, ~idx
);
3501 strinfo
*si
= get_strinfo (idx
);
3503 arg1_len
= get_string_length (si
);
3507 if (arg1_len
!= NULL_TREE
)
3509 gimple_stmt_iterator gsi
= gsi_for_stmt (call_stmt
);
3510 tree strncmp_decl
= builtin_decl_explicit (BUILT_IN_STRNCMP
);
3512 if (!is_gimple_val (arg1_len
))
3514 tree arg1_len_tmp
= make_ssa_name (TREE_TYPE (arg1_len
));
3515 gassign
*arg1_stmt
= gimple_build_assign (arg1_len_tmp
,
3517 gsi_insert_before (&gsi
, arg1_stmt
, GSI_SAME_STMT
);
3518 arg1_len
= arg1_len_tmp
;
3521 gcall
*strncmp_call
= gimple_build_call (strncmp_decl
, 3,
3522 arg0
, arg1
, arg1_len
);
3523 tree strncmp_lhs
= make_ssa_name (integer_type_node
);
3524 gimple_set_vuse (strncmp_call
, gimple_vuse (call_stmt
));
3525 gimple_call_set_lhs (strncmp_call
, strncmp_lhs
);
3526 gsi_remove (&gsi
, true);
3527 gsi_insert_before (&gsi
, strncmp_call
, GSI_SAME_STMT
);
3528 tree zero
= build_zero_cst (TREE_TYPE (strncmp_lhs
));
3530 if (is_gimple_assign (stmt
))
3532 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
3534 tree cond
= gimple_assign_rhs1 (stmt
);
3535 TREE_OPERAND (cond
, 0) = strncmp_lhs
;
3536 TREE_OPERAND (cond
, 1) = zero
;
3540 gimple_assign_set_rhs1 (stmt
, strncmp_lhs
);
3541 gimple_assign_set_rhs2 (stmt
, zero
);
3546 gcond
*cond
= as_a
<gcond
*> (stmt
);
3547 gimple_cond_set_lhs (cond
, strncmp_lhs
);
3548 gimple_cond_set_rhs (cond
, zero
);
3556 /* Attempt to check for validity of the performed access a single statement
3557 at *GSI using string length knowledge, and to optimize it.
3558 If the given basic block needs clean-up of EH, CLEANUP_EH is set to
3562 strlen_check_and_optimize_stmt (gimple_stmt_iterator
*gsi
, bool *cleanup_eh
)
3564 gimple
*stmt
= gsi_stmt (*gsi
);
3566 if (is_gimple_call (stmt
))
3568 tree callee
= gimple_call_fndecl (stmt
);
3569 if (valid_builtin_call (stmt
))
3570 switch (DECL_FUNCTION_CODE (callee
))
3572 case BUILT_IN_STRLEN
:
3573 case BUILT_IN_STRNLEN
:
3574 handle_builtin_strlen (gsi
);
3576 case BUILT_IN_STRCHR
:
3577 handle_builtin_strchr (gsi
);
3579 case BUILT_IN_STRCPY
:
3580 case BUILT_IN_STRCPY_CHK
:
3581 case BUILT_IN_STPCPY
:
3582 case BUILT_IN_STPCPY_CHK
:
3583 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3586 case BUILT_IN_STRNCAT
:
3587 case BUILT_IN_STRNCAT_CHK
:
3588 handle_builtin_strncat (DECL_FUNCTION_CODE (callee
), gsi
);
3591 case BUILT_IN_STPNCPY
:
3592 case BUILT_IN_STPNCPY_CHK
:
3593 case BUILT_IN_STRNCPY
:
3594 case BUILT_IN_STRNCPY_CHK
:
3595 handle_builtin_stxncpy (DECL_FUNCTION_CODE (callee
), gsi
);
3598 case BUILT_IN_MEMCPY
:
3599 case BUILT_IN_MEMCPY_CHK
:
3600 case BUILT_IN_MEMPCPY
:
3601 case BUILT_IN_MEMPCPY_CHK
:
3602 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3604 case BUILT_IN_STRCAT
:
3605 case BUILT_IN_STRCAT_CHK
:
3606 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
3608 case BUILT_IN_MALLOC
:
3609 case BUILT_IN_CALLOC
:
3610 handle_builtin_malloc (DECL_FUNCTION_CODE (callee
), gsi
);
3612 case BUILT_IN_MEMSET
:
3613 if (handle_builtin_memset (gsi
))
3616 case BUILT_IN_MEMCMP
:
3617 if (handle_builtin_memcmp (gsi
))
3620 case BUILT_IN_STRCMP
:
3621 case BUILT_IN_STRNCMP
:
3622 if (handle_builtin_string_cmp (gsi
))
3629 else if (is_gimple_assign (stmt
) && !gimple_clobber_p (stmt
))
3631 tree lhs
= gimple_assign_lhs (stmt
);
3633 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
3635 if (gimple_assign_single_p (stmt
)
3636 || (gimple_assign_cast_p (stmt
)
3637 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
3639 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
3640 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
3642 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
3643 handle_pointer_plus (gsi
);
3645 else if (TREE_CODE (lhs
) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
3647 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3648 if (code
== COND_EXPR
)
3650 tree cond
= gimple_assign_rhs1 (stmt
);
3651 enum tree_code cond_code
= TREE_CODE (cond
);
3653 if (cond_code
== EQ_EXPR
|| cond_code
== NE_EXPR
)
3654 fold_strstr_to_strncmp (TREE_OPERAND (cond
, 0),
3655 TREE_OPERAND (cond
, 1), stmt
);
3657 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3658 fold_strstr_to_strncmp (gimple_assign_rhs1 (stmt
),
3659 gimple_assign_rhs2 (stmt
), stmt
);
3660 else if (gimple_assign_load_p (stmt
)
3661 && TREE_CODE (TREE_TYPE (lhs
)) == INTEGER_TYPE
3662 && TYPE_MODE (TREE_TYPE (lhs
)) == TYPE_MODE (char_type_node
)
3663 && (TYPE_PRECISION (TREE_TYPE (lhs
))
3664 == TYPE_PRECISION (char_type_node
))
3665 && !gimple_has_volatile_ops (stmt
))
3667 tree off
= integer_zero_node
;
3668 unsigned HOST_WIDE_INT coff
= 0;
3670 tree rhs1
= gimple_assign_rhs1 (stmt
);
3671 if (code
== MEM_REF
)
3673 idx
= get_stridx (TREE_OPERAND (rhs1
, 0));
3676 strinfo
*si
= get_strinfo (idx
);
3678 && si
->nonzero_chars
3679 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
3680 && (wi::to_widest (si
->nonzero_chars
)
3681 >= wi::to_widest (off
)))
3682 off
= TREE_OPERAND (rhs1
, 1);
3684 /* This case is not useful. See if get_addr_stridx
3685 returns something usable. */
3690 idx
= get_addr_stridx (rhs1
, NULL_TREE
, &coff
);
3693 strinfo
*si
= get_strinfo (idx
);
3695 && si
->nonzero_chars
3696 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
3698 widest_int w1
= wi::to_widest (si
->nonzero_chars
);
3699 widest_int w2
= wi::to_widest (off
) + coff
;
3701 && si
->full_string_p
)
3703 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3705 fprintf (dump_file
, "Optimizing: ");
3706 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3709 /* Reading the final '\0' character. */
3710 tree zero
= build_int_cst (TREE_TYPE (lhs
), 0);
3711 gimple_set_vuse (stmt
, NULL_TREE
);
3712 gimple_assign_set_rhs_from_tree (gsi
, zero
);
3714 |= maybe_clean_or_replace_eh_stmt (stmt
,
3716 stmt
= gsi_stmt (*gsi
);
3719 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3721 fprintf (dump_file
, "into: ");
3722 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3727 /* Reading a character before the final '\0'
3728 character. Just set the value range to ~[0, 0]
3729 if we don't have anything better. */
3731 tree type
= TREE_TYPE (lhs
);
3732 enum value_range_kind vr
3733 = get_range_info (lhs
, &min
, &max
);
3734 if (vr
== VR_VARYING
3736 && min
== wi::min_value (TYPE_PRECISION (type
),
3738 && max
== wi::max_value (TYPE_PRECISION (type
),
3740 set_range_info (lhs
, VR_ANTI_RANGE
,
3741 wi::zero (TYPE_PRECISION (type
)),
3742 wi::zero (TYPE_PRECISION (type
)));
3748 if (strlen_to_stridx
)
3750 tree rhs1
= gimple_assign_rhs1 (stmt
);
3751 if (stridx_strlenloc
*ps
= strlen_to_stridx
->get (rhs1
))
3752 strlen_to_stridx
->put (lhs
, stridx_strlenloc (*ps
));
3755 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
3757 tree type
= TREE_TYPE (lhs
);
3758 if (TREE_CODE (type
) == ARRAY_TYPE
)
3759 type
= TREE_TYPE (type
);
3760 if (TREE_CODE (type
) == INTEGER_TYPE
3761 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
3762 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
3764 if (! handle_char_store (gsi
))
3769 else if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
3771 enum tree_code code
= gimple_cond_code (cond
);
3772 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3773 fold_strstr_to_strncmp (gimple_cond_lhs (stmt
),
3774 gimple_cond_rhs (stmt
), stmt
);
3777 if (gimple_vdef (stmt
))
3778 maybe_invalidate (stmt
);
3782 /* Recursively call maybe_invalidate on stmts that might be executed
3783 in between dombb and current bb and that contain a vdef. Stop when
3784 *count stmts are inspected, or if the whole strinfo vector has
3785 been invalidated. */
3788 do_invalidate (basic_block dombb
, gimple
*phi
, bitmap visited
, int *count
)
3790 unsigned int i
, n
= gimple_phi_num_args (phi
);
3792 for (i
= 0; i
< n
; i
++)
3794 tree vuse
= gimple_phi_arg_def (phi
, i
);
3795 gimple
*stmt
= SSA_NAME_DEF_STMT (vuse
);
3796 basic_block bb
= gimple_bb (stmt
);
3799 || !bitmap_set_bit (visited
, bb
->index
)
3800 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3804 if (gimple_code (stmt
) == GIMPLE_PHI
)
3806 do_invalidate (dombb
, stmt
, visited
, count
);
3813 if (!maybe_invalidate (stmt
))
3818 vuse
= gimple_vuse (stmt
);
3819 stmt
= SSA_NAME_DEF_STMT (vuse
);
3820 if (gimple_bb (stmt
) != bb
)
3822 bb
= gimple_bb (stmt
);
3825 || !bitmap_set_bit (visited
, bb
->index
)
3826 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3833 class strlen_dom_walker
: public dom_walker
3836 strlen_dom_walker (cdi_direction direction
)
3837 : dom_walker (direction
), m_cleanup_cfg (false)
3840 virtual edge
before_dom_children (basic_block
);
3841 virtual void after_dom_children (basic_block
);
3843 /* Flag that will trigger TODO_cleanup_cfg to be returned in strlen
3844 execute function. */
3848 /* Callback for walk_dominator_tree. Attempt to optimize various
3849 string ops by remembering string lengths pointed by pointer SSA_NAMEs. */
3852 strlen_dom_walker::before_dom_children (basic_block bb
)
3854 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
3857 stridx_to_strinfo
= NULL
;
3860 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) dombb
->aux
);
3861 if (stridx_to_strinfo
)
3863 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3866 gphi
*phi
= gsi
.phi ();
3867 if (virtual_operand_p (gimple_phi_result (phi
)))
3869 bitmap visited
= BITMAP_ALLOC (NULL
);
3870 int count_vdef
= 100;
3871 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
3872 BITMAP_FREE (visited
);
3873 if (count_vdef
== 0)
3875 /* If there were too many vdefs in between immediate
3876 dominator and current bb, invalidate everything.
3877 If stridx_to_strinfo has been unshared, we need
3878 to free it, otherwise just set it to NULL. */
3879 if (!strinfo_shared ())
3885 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
3889 (*stridx_to_strinfo
)[i
] = NULL
;
3893 stridx_to_strinfo
= NULL
;
3901 /* If all PHI arguments have the same string index, the PHI result
3903 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3906 gphi
*phi
= gsi
.phi ();
3907 tree result
= gimple_phi_result (phi
);
3908 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
3910 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
3913 unsigned int i
, n
= gimple_phi_num_args (phi
);
3914 for (i
= 1; i
< n
; i
++)
3915 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
3918 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
3923 bool cleanup_eh
= false;
3925 /* Attempt to optimize individual statements. */
3926 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
3927 if (strlen_check_and_optimize_stmt (&gsi
, &cleanup_eh
))
3930 if (cleanup_eh
&& gimple_purge_dead_eh_edges (bb
))
3931 m_cleanup_cfg
= true;
3933 bb
->aux
= stridx_to_strinfo
;
3934 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
3935 (*stridx_to_strinfo
)[0] = (strinfo
*) bb
;
3939 /* Callback for walk_dominator_tree. Free strinfo vector if it is
3940 owned by the current bb, clear bb->aux. */
3943 strlen_dom_walker::after_dom_children (basic_block bb
)
3947 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) bb
->aux
);
3948 if (vec_safe_length (stridx_to_strinfo
)
3949 && (*stridx_to_strinfo
)[0] == (strinfo
*) bb
)
3954 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
3956 vec_free (stridx_to_strinfo
);
3962 /* Main entry point. */
3966 const pass_data pass_data_strlen
=
3968 GIMPLE_PASS
, /* type */
3969 "strlen", /* name */
3970 OPTGROUP_NONE
, /* optinfo_flags */
3971 TV_TREE_STRLEN
, /* tv_id */
3972 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3973 0, /* properties_provided */
3974 0, /* properties_destroyed */
3975 0, /* todo_flags_start */
3976 0, /* todo_flags_finish */
3979 class pass_strlen
: public gimple_opt_pass
3982 pass_strlen (gcc::context
*ctxt
)
3983 : gimple_opt_pass (pass_data_strlen
, ctxt
)
3986 /* opt_pass methods: */
3987 virtual bool gate (function
*) { return flag_optimize_strlen
!= 0; }
3988 virtual unsigned int execute (function
*);
3990 }; // class pass_strlen
3993 pass_strlen::execute (function
*fun
)
3995 gcc_assert (!strlen_to_stridx
);
3996 if (warn_stringop_overflow
|| warn_stringop_truncation
)
3997 strlen_to_stridx
= new hash_map
<tree
, stridx_strlenloc
> ();
3999 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
4002 calculate_dominance_info (CDI_DOMINATORS
);
4004 /* String length optimization is implemented as a walk of the dominator
4005 tree and a forward walk of statements within each block. */
4006 strlen_dom_walker
walker (CDI_DOMINATORS
);
4007 walker
.walk (fun
->cfg
->x_entry_block_ptr
);
4009 ssa_ver_to_stridx
.release ();
4010 strinfo_pool
.release ();
4011 if (decl_to_stridxlist_htab
)
4013 obstack_free (&stridx_obstack
, NULL
);
4014 delete decl_to_stridxlist_htab
;
4015 decl_to_stridxlist_htab
= NULL
;
4017 laststmt
.stmt
= NULL
;
4018 laststmt
.len
= NULL_TREE
;
4019 laststmt
.stridx
= 0;
4021 if (strlen_to_stridx
)
4023 strlen_to_stridx
->empty ();
4024 delete strlen_to_stridx
;
4025 strlen_to_stridx
= NULL
;
4028 return walker
.m_cleanup_cfg
? TODO_cleanup_cfg
: 0;
4034 make_pass_strlen (gcc::context
*ctxt
)
4036 return new pass_strlen (ctxt
);