1 /* String length optimization
2 Copyright (C) 2011-2018 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 and for strlen() or strnlen() argument
1125 SRC, set LHS range info to [0, min (N, BOUND)] if SRC refers to
1126 a character array A[N] with unknown length bounded by N, and for
1127 strnlen(), by min (N, BOUND). */
1130 maybe_set_strlen_range (tree lhs
, tree src
, tree bound
)
1132 if (TREE_CODE (lhs
) != SSA_NAME
1133 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
1136 if (TREE_CODE (src
) == SSA_NAME
)
1138 gimple
*def
= SSA_NAME_DEF_STMT (src
);
1139 if (is_gimple_assign (def
)
1140 && gimple_assign_rhs_code (def
) == ADDR_EXPR
)
1141 src
= gimple_assign_rhs1 (def
);
1144 wide_int max
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
));
1145 wide_int min
= wi::zero (max
.get_precision ());
1147 if (TREE_CODE (src
) == ADDR_EXPR
)
1149 /* The last array member of a struct can be bigger than its size
1150 suggests if it's treated as a poor-man's flexible array member. */
1151 src
= TREE_OPERAND (src
, 0);
1152 bool src_is_array
= TREE_CODE (TREE_TYPE (src
)) == ARRAY_TYPE
;
1154 && TREE_CODE (src
) != MEM_REF
1155 && !array_at_struct_end_p (src
))
1157 tree type
= TREE_TYPE (src
);
1158 if (tree size
= TYPE_SIZE_UNIT (type
))
1159 if (size
&& TREE_CODE (size
) == INTEGER_CST
)
1160 max
= wi::to_wide (size
);
1162 /* For strlen() the upper bound above is equal to
1163 the longest string that can be stored in the array
1164 (i.e., it accounts for the terminating nul. For
1165 strnlen() bump up the maximum by one since the array
1166 need not be nul-terminated. */
1167 if (!bound
&& max
!= 0)
1172 if (TREE_CODE (src
) == COMPONENT_REF
&& !src_is_array
)
1173 src
= TREE_OPERAND (src
, 1);
1176 /* Handle the unlikely case of strlen (&c) where c is some
1178 if (tree size
= DECL_SIZE_UNIT (src
))
1179 if (TREE_CODE (size
) == INTEGER_CST
)
1180 max
= wi::to_wide (size
);
1187 /* For strnlen, adjust MIN and MAX as necessary. If the bound
1188 is less than the size of the array set MAX to it. It it's
1189 greater than MAX and MAX is non-zero bump MAX down to account
1190 for the necessary terminating nul. Otherwise leave it alone. */
1191 if (TREE_CODE (bound
) == INTEGER_CST
)
1193 wide_int wibnd
= wi::to_wide (bound
);
1194 int cmp
= wi::cmpu (wibnd
, max
);
1197 else if (cmp
&& wi::ne_p (max
, min
))
1200 else if (TREE_CODE (bound
) == SSA_NAME
)
1202 wide_int minbound
, maxbound
;
1203 value_range_kind rng
= get_range_info (bound
, &minbound
, &maxbound
);
1204 if (rng
== VR_RANGE
)
1206 /* For a bound in a known range, adjust the range determined
1207 above as necessary. For a bound in some anti-range or
1208 in an unknown range, use the range determined above. */
1209 if (wi::ltu_p (minbound
, min
))
1211 if (wi::ltu_p (maxbound
, max
))
1218 return wide_int_to_tree (size_type_node
, min
);
1220 set_range_info (lhs
, VR_RANGE
, min
, max
);
1224 /* Handle a strlen call. If strlen of the argument is known, replace
1225 the strlen call with the known value, otherwise remember that strlen
1226 of the argument is stored in the lhs SSA_NAME. */
1229 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
1231 gimple
*stmt
= gsi_stmt (*gsi
);
1232 tree lhs
= gimple_call_lhs (stmt
);
1234 if (lhs
== NULL_TREE
)
1237 location_t loc
= gimple_location (stmt
);
1238 tree callee
= gimple_call_fndecl (stmt
);
1239 tree src
= gimple_call_arg (stmt
, 0);
1240 tree bound
= (DECL_FUNCTION_CODE (callee
) == BUILT_IN_STRNLEN
1241 ? gimple_call_arg (stmt
, 1) : NULL_TREE
);
1242 int idx
= get_stridx (src
);
1249 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
1253 si
= get_strinfo (idx
);
1255 rhs
= get_string_length (si
);
1257 if (rhs
!= NULL_TREE
)
1259 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1261 fprintf (dump_file
, "Optimizing: ");
1262 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1264 rhs
= unshare_expr (rhs
);
1265 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
1266 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1268 /* Set for strnlen() calls with a non-constant bound. */
1269 bool noncst_bound
= false;
1273 = fold_build2_loc (loc
, MIN_EXPR
, TREE_TYPE (rhs
), rhs
, bound
);
1275 noncst_bound
= (TREE_CODE (new_rhs
) != INTEGER_CST
1276 || tree_int_cst_lt (new_rhs
, rhs
));
1281 if (!update_call_from_tree (gsi
, rhs
))
1282 gimplify_and_update_call_from_tree (gsi
, rhs
);
1283 stmt
= gsi_stmt (*gsi
);
1285 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1287 fprintf (dump_file
, "into: ");
1288 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1291 /* Avoid storing the length for calls to strnlen() with
1292 a non-constant bound. */
1297 && TREE_CODE (si
->nonzero_chars
) != SSA_NAME
1298 && TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
1299 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1301 si
= unshare_strinfo (si
);
1302 si
->nonzero_chars
= lhs
;
1303 gcc_assert (si
->full_string_p
);
1306 if (strlen_to_stridx
)
1307 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1312 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1316 idx
= new_stridx (src
);
1319 strinfo
*si
= get_strinfo (idx
);
1322 if (!si
->full_string_p
&& !si
->stmt
)
1324 /* Until now we only had a lower bound on the string length.
1325 Install LHS as the actual length. */
1326 si
= unshare_strinfo (si
);
1327 tree old
= si
->nonzero_chars
;
1328 si
->nonzero_chars
= lhs
;
1329 si
->full_string_p
= true;
1330 if (TREE_CODE (old
) == INTEGER_CST
)
1332 old
= fold_convert_loc (loc
, TREE_TYPE (lhs
), old
);
1333 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1334 TREE_TYPE (lhs
), lhs
, old
);
1335 adjust_related_strinfos (loc
, si
, adj
);
1351 /* Only store the new length information for calls to strlen(),
1352 not for those to strnlen(). */
1353 strinfo
*si
= new_strinfo (src
, idx
, lhs
, true);
1354 set_strinfo (idx
, si
);
1355 find_equal_ptrs (src
, idx
);
1358 /* For SRC that is an array of N elements, set LHS's range
1359 to [0, min (N, BOUND)]. A constant return value means
1360 the range would have consisted of a single value. In
1361 that case, fold the result into the returned constant. */
1362 if (tree ret
= maybe_set_strlen_range (lhs
, src
, bound
))
1363 if (TREE_CODE (ret
) == INTEGER_CST
)
1365 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1367 fprintf (dump_file
, "Optimizing: ");
1368 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1370 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (ret
)))
1371 ret
= fold_convert_loc (loc
, TREE_TYPE (lhs
), ret
);
1372 if (!update_call_from_tree (gsi
, ret
))
1373 gimplify_and_update_call_from_tree (gsi
, ret
);
1374 stmt
= gsi_stmt (*gsi
);
1376 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1378 fprintf (dump_file
, "into: ");
1379 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1383 if (strlen_to_stridx
&& !bound
)
1384 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1388 /* Handle a strchr call. If strlen of the first argument is known, replace
1389 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
1390 that lhs of the call is endptr and strlen of the argument is endptr - x. */
1393 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
1397 gimple
*stmt
= gsi_stmt (*gsi
);
1398 tree lhs
= gimple_call_lhs (stmt
);
1400 if (lhs
== NULL_TREE
)
1403 if (!integer_zerop (gimple_call_arg (stmt
, 1)))
1406 src
= gimple_call_arg (stmt
, 0);
1407 idx
= get_stridx (src
);
1414 rhs
= build_int_cst (size_type_node
, ~idx
);
1418 si
= get_strinfo (idx
);
1420 rhs
= get_string_length (si
);
1422 if (rhs
!= NULL_TREE
)
1424 location_t loc
= gimple_location (stmt
);
1426 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1428 fprintf (dump_file
, "Optimizing: ");
1429 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1431 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
1433 rhs
= unshare_expr (si
->endptr
);
1434 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1436 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1440 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1441 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1442 TREE_TYPE (src
), src
, rhs
);
1443 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1445 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1447 if (!update_call_from_tree (gsi
, rhs
))
1448 gimplify_and_update_call_from_tree (gsi
, rhs
);
1449 stmt
= gsi_stmt (*gsi
);
1451 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1453 fprintf (dump_file
, "into: ");
1454 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1457 && si
->endptr
== NULL_TREE
1458 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1460 si
= unshare_strinfo (si
);
1463 zero_length_string (lhs
, si
);
1467 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1469 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1472 idx
= new_stridx (src
);
1473 else if (get_strinfo (idx
) != NULL
)
1475 zero_length_string (lhs
, NULL
);
1480 location_t loc
= gimple_location (stmt
);
1481 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1482 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1483 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1484 size_type_node
, lhsu
, srcu
);
1485 strinfo
*si
= new_strinfo (src
, idx
, length
, true);
1487 set_strinfo (idx
, si
);
1488 find_equal_ptrs (src
, idx
);
1489 zero_length_string (lhs
, si
);
1493 zero_length_string (lhs
, NULL
);
1496 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1497 If strlen of the second argument is known, strlen of the first argument
1498 is the same after this call. Furthermore, attempt to convert it to
1502 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1505 tree src
, dst
, srclen
, len
, lhs
, type
, fn
, oldlen
;
1507 gimple
*stmt
= gsi_stmt (*gsi
);
1508 strinfo
*si
, *dsi
, *olddsi
, *zsi
;
1511 src
= gimple_call_arg (stmt
, 1);
1512 dst
= gimple_call_arg (stmt
, 0);
1513 lhs
= gimple_call_lhs (stmt
);
1514 idx
= get_stridx (src
);
1517 si
= get_strinfo (idx
);
1519 didx
= get_stridx (dst
);
1523 olddsi
= get_strinfo (didx
);
1528 adjust_last_stmt (olddsi
, stmt
, false);
1532 srclen
= get_string_length (si
);
1534 srclen
= build_int_cst (size_type_node
, ~idx
);
1536 loc
= gimple_location (stmt
);
1537 if (srclen
== NULL_TREE
)
1540 case BUILT_IN_STRCPY
:
1541 case BUILT_IN_STRCPY_CHK
:
1542 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1545 case BUILT_IN_STPCPY
:
1546 case BUILT_IN_STPCPY_CHK
:
1547 if (lhs
== NULL_TREE
)
1551 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1552 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1553 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1563 didx
= new_stridx (dst
);
1569 oldlen
= olddsi
->nonzero_chars
;
1570 dsi
= unshare_strinfo (olddsi
);
1571 dsi
->nonzero_chars
= srclen
;
1572 dsi
->full_string_p
= (srclen
!= NULL_TREE
);
1573 /* Break the chain, so adjust_related_strinfo on later pointers in
1574 the chain won't adjust this one anymore. */
1577 dsi
->endptr
= NULL_TREE
;
1581 dsi
= new_strinfo (dst
, didx
, srclen
, srclen
!= NULL_TREE
);
1582 set_strinfo (didx
, dsi
);
1583 find_equal_ptrs (dst
, didx
);
1585 dsi
->writable
= true;
1586 dsi
->dont_invalidate
= true;
1588 if (dsi
->nonzero_chars
== NULL_TREE
)
1592 /* If string length of src is unknown, use delayed length
1593 computation. If string lenth of dst will be needed, it
1594 can be computed by transforming this strcpy call into
1595 stpcpy and subtracting dst from the return value. */
1597 /* Look for earlier strings whose length could be determined if
1598 this strcpy is turned into an stpcpy. */
1600 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1602 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1604 /* When setting a stmt for delayed length computation
1605 prevent all strinfos through dsi from being
1607 chainsi
= unshare_strinfo (chainsi
);
1608 chainsi
->stmt
= stmt
;
1609 chainsi
->nonzero_chars
= NULL_TREE
;
1610 chainsi
->full_string_p
= false;
1611 chainsi
->endptr
= NULL_TREE
;
1612 chainsi
->dont_invalidate
= true;
1617 /* Try to detect overlap before returning. This catches cases
1618 like strcpy (d, d + n) where n is non-constant whose range
1619 is such that (n <= strlen (d) holds).
1621 OLDDSI->NONZERO_chars may have been reset by this point with
1622 oldlen holding it original value. */
1623 if (olddsi
&& oldlen
)
1625 /* Add 1 for the terminating NUL. */
1626 tree type
= TREE_TYPE (oldlen
);
1627 oldlen
= fold_build2 (PLUS_EXPR
, type
, oldlen
,
1628 build_int_cst (type
, 1));
1629 check_bounds_or_overlap (stmt
, olddsi
->ptr
, src
, oldlen
, NULL_TREE
);
1637 tree adj
= NULL_TREE
;
1638 if (oldlen
== NULL_TREE
)
1640 else if (integer_zerop (oldlen
))
1642 else if (TREE_CODE (oldlen
) == INTEGER_CST
1643 || TREE_CODE (srclen
) == INTEGER_CST
)
1644 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1645 TREE_TYPE (srclen
), srclen
,
1646 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1648 if (adj
!= NULL_TREE
)
1649 adjust_related_strinfos (loc
, dsi
, adj
);
1653 /* strcpy src may not overlap dst, so src doesn't need to be
1654 invalidated either. */
1656 si
->dont_invalidate
= true;
1662 case BUILT_IN_STRCPY
:
1663 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1665 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1667 case BUILT_IN_STRCPY_CHK
:
1668 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1670 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1672 case BUILT_IN_STPCPY
:
1673 /* This would need adjustment of the lhs (subtract one),
1674 or detection that the trailing '\0' doesn't need to be
1675 written, if it will be immediately overwritten.
1676 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1680 zsi
= zero_length_string (lhs
, dsi
);
1683 case BUILT_IN_STPCPY_CHK
:
1684 /* This would need adjustment of the lhs (subtract one),
1685 or detection that the trailing '\0' doesn't need to be
1686 written, if it will be immediately overwritten.
1687 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1691 zsi
= zero_length_string (lhs
, dsi
);
1698 zsi
->dont_invalidate
= true;
1702 tree args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1703 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1706 type
= size_type_node
;
1708 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1709 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1711 /* Set the no-warning bit on the transformed statement? */
1712 bool set_no_warning
= false;
1714 if (const strinfo
*chksi
= olddsi
? olddsi
: dsi
)
1716 && !check_bounds_or_overlap (stmt
, chksi
->ptr
, si
->ptr
, NULL_TREE
, len
))
1718 gimple_set_no_warning (stmt
, true);
1719 set_no_warning
= true;
1722 if (fn
== NULL_TREE
)
1725 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1727 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1729 fprintf (dump_file
, "Optimizing: ");
1730 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1732 if (gimple_call_num_args (stmt
) == 2)
1733 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1735 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1736 gimple_call_arg (stmt
, 2));
1739 stmt
= gsi_stmt (*gsi
);
1741 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1743 fprintf (dump_file
, "into: ");
1744 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1746 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1747 laststmt
.stmt
= stmt
;
1748 laststmt
.len
= srclen
;
1749 laststmt
.stridx
= dsi
->idx
;
1751 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1752 fprintf (dump_file
, "not possible.\n");
1755 gimple_set_no_warning (stmt
, true);
1758 /* Check the size argument to the built-in forms of stpncpy and strncpy
1759 for out-of-bounds offsets or overlapping access, and to see if the
1760 size argument is derived from a call to strlen() on the source argument,
1761 and if so, issue an appropriate warning. */
1764 handle_builtin_strncat (built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1766 /* Same as stxncpy(). */
1767 handle_builtin_stxncpy (bcode
, gsi
);
1770 /* Return true if LEN depends on a call to strlen(SRC) in an interesting
1771 way. LEN can either be an integer expression, or a pointer (to char).
1772 When it is the latter (such as in recursive calls to self) is is
1773 assumed to be the argument in some call to strlen() whose relationship
1774 to SRC is being ascertained. */
1777 is_strlen_related_p (tree src
, tree len
)
1779 if (TREE_CODE (TREE_TYPE (len
)) == POINTER_TYPE
1780 && operand_equal_p (src
, len
, 0))
1783 if (TREE_CODE (len
) != SSA_NAME
)
1786 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1790 if (is_gimple_call (def_stmt
))
1792 tree func
= gimple_call_fndecl (def_stmt
);
1793 if (!valid_builtin_call (def_stmt
)
1794 || DECL_FUNCTION_CODE (func
) != BUILT_IN_STRLEN
)
1797 tree arg
= gimple_call_arg (def_stmt
, 0);
1798 return is_strlen_related_p (src
, arg
);
1801 if (!is_gimple_assign (def_stmt
))
1804 tree_code code
= gimple_assign_rhs_code (def_stmt
);
1805 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1806 tree rhstype
= TREE_TYPE (rhs1
);
1808 if ((TREE_CODE (rhstype
) == POINTER_TYPE
&& code
== POINTER_PLUS_EXPR
)
1809 || (INTEGRAL_TYPE_P (rhstype
)
1810 && (code
== BIT_AND_EXPR
1811 || code
== NOP_EXPR
)))
1813 /* Pointer plus (an integer), and truncation are considered among
1814 the (potentially) related expressions to strlen. */
1815 return is_strlen_related_p (src
, rhs1
);
1818 if (tree rhs2
= gimple_assign_rhs2 (def_stmt
))
1820 /* Integer subtraction is considered strlen-related when both
1821 arguments are integers and second one is strlen-related. */
1822 rhstype
= TREE_TYPE (rhs2
);
1823 if (INTEGRAL_TYPE_P (rhstype
) && code
== MINUS_EXPR
)
1824 return is_strlen_related_p (src
, rhs2
);
1830 /* Called by handle_builtin_stxncpy and by gimple_fold_builtin_strncpy
1832 Check to see if the specified bound is a) equal to the size of
1833 the destination DST and if so, b) if it's immediately followed by
1834 DST[CNT - 1] = '\0'. If a) holds and b) does not, warn. Otherwise,
1835 do nothing. Return true if diagnostic has been issued.
1837 The purpose is to diagnose calls to strncpy and stpncpy that do
1838 not nul-terminate the copy while allowing for the idiom where
1839 such a call is immediately followed by setting the last element
1842 strncpy (a, s, sizeof a);
1843 a[sizeof a - 1] = '\0';
1847 maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi
, tree src
, tree cnt
)
1849 gimple
*stmt
= gsi_stmt (gsi
);
1850 if (gimple_no_warning_p (stmt
))
1853 wide_int cntrange
[2];
1855 if (TREE_CODE (cnt
) == INTEGER_CST
)
1856 cntrange
[0] = cntrange
[1] = wi::to_wide (cnt
);
1857 else if (TREE_CODE (cnt
) == SSA_NAME
)
1859 enum value_range_kind rng
= get_range_info (cnt
, cntrange
, cntrange
+ 1);
1860 if (rng
== VR_RANGE
)
1862 else if (rng
== VR_ANTI_RANGE
)
1864 wide_int maxobjsize
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
));
1866 if (wi::ltu_p (cntrange
[1], maxobjsize
))
1868 cntrange
[0] = cntrange
[1] + 1;
1869 cntrange
[1] = maxobjsize
;
1873 cntrange
[1] = cntrange
[0] - 1;
1874 cntrange
[0] = wi::zero (TYPE_PRECISION (TREE_TYPE (cnt
)));
1883 /* Negative value is the constant string length. If it's less than
1884 the lower bound there is no truncation. Avoid calling get_stridx()
1885 when ssa_ver_to_stridx is empty. That implies the caller isn't
1886 running under the control of this pass and ssa_ver_to_stridx hasn't
1887 been created yet. */
1888 int sidx
= ssa_ver_to_stridx
.length () ? get_stridx (src
) : 0;
1889 if (sidx
< 0 && wi::gtu_p (cntrange
[0], ~sidx
))
1892 tree dst
= gimple_call_arg (stmt
, 0);
1894 if (TREE_CODE (dstdecl
) == ADDR_EXPR
)
1895 dstdecl
= TREE_OPERAND (dstdecl
, 0);
1897 tree ref
= NULL_TREE
;
1901 /* If the source is a non-string return early to avoid warning
1902 for possible truncation (if the truncation is certain SIDX
1904 tree srcdecl
= gimple_call_arg (stmt
, 1);
1905 if (TREE_CODE (srcdecl
) == ADDR_EXPR
)
1906 srcdecl
= TREE_OPERAND (srcdecl
, 0);
1907 if (get_attr_nonstring_decl (srcdecl
, &ref
))
1911 /* Likewise, if the destination refers to a an array/pointer declared
1912 nonstring return early. */
1913 if (get_attr_nonstring_decl (dstdecl
, &ref
))
1916 /* Look for dst[i] = '\0'; after the stxncpy() call and if found
1917 avoid the truncation warning. */
1918 gsi_next_nondebug (&gsi
);
1919 gimple
*next_stmt
= gsi_stmt (gsi
);
1922 /* When there is no statement in the same basic block check
1923 the immediate successor block. */
1924 if (basic_block bb
= gimple_bb (stmt
))
1926 if (single_succ_p (bb
))
1928 /* For simplicity, ignore blocks with multiple outgoing
1929 edges for now and only consider successor blocks along
1931 edge e
= EDGE_SUCC (bb
, 0);
1932 if (!(e
->flags
& EDGE_ABNORMAL
))
1934 gsi
= gsi_start_bb (e
->dest
);
1935 next_stmt
= gsi_stmt (gsi
);
1936 if (next_stmt
&& is_gimple_debug (next_stmt
))
1938 gsi_next_nondebug (&gsi
);
1939 next_stmt
= gsi_stmt (gsi
);
1946 if (next_stmt
&& is_gimple_assign (next_stmt
))
1948 tree lhs
= gimple_assign_lhs (next_stmt
);
1949 tree_code code
= TREE_CODE (lhs
);
1950 if (code
== ARRAY_REF
|| code
== MEM_REF
)
1951 lhs
= TREE_OPERAND (lhs
, 0);
1953 tree func
= gimple_call_fndecl (stmt
);
1954 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STPNCPY
)
1956 tree ret
= gimple_call_lhs (stmt
);
1957 if (ret
&& operand_equal_p (ret
, lhs
, 0))
1961 /* Determine the base address and offset of the reference,
1962 ignoring the innermost array index. */
1963 if (TREE_CODE (ref
) == ARRAY_REF
)
1964 ref
= TREE_OPERAND (ref
, 0);
1967 tree dstbase
= get_addr_base_and_unit_offset (ref
, &dstoff
);
1970 tree lhsbase
= get_addr_base_and_unit_offset (lhs
, &lhsoff
);
1973 && known_eq (dstoff
, lhsoff
)
1974 && operand_equal_p (dstbase
, lhsbase
, 0))
1978 int prec
= TYPE_PRECISION (TREE_TYPE (cnt
));
1979 wide_int lenrange
[2];
1980 if (strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
)
1982 lenrange
[0] = (sisrc
->nonzero_chars
1983 && TREE_CODE (sisrc
->nonzero_chars
) == INTEGER_CST
1984 ? wi::to_wide (sisrc
->nonzero_chars
)
1986 lenrange
[1] = lenrange
[0];
1989 lenrange
[0] = lenrange
[1] = wi::shwi (~sidx
, prec
);
1993 get_range_strlen (src
, range
);
1994 if (range
[0] != NULL_TREE
1995 && TREE_CODE (range
[0]) == INTEGER_CST
1996 && range
[1] != NULL_TREE
1997 && TREE_CODE (range
[1]) == INTEGER_CST
)
1999 lenrange
[0] = wi::to_wide (range
[0], prec
);
2000 lenrange
[1] = wi::to_wide (range
[1], prec
);
2004 lenrange
[0] = wi::shwi (0, prec
);
2005 lenrange
[1] = wi::shwi (-1, prec
);
2009 location_t callloc
= gimple_nonartificial_location (stmt
);
2010 callloc
= expansion_point_location_if_in_system_header (callloc
);
2012 tree func
= gimple_call_fndecl (stmt
);
2014 if (lenrange
[0] != 0 || !wi::neg_p (lenrange
[1]))
2016 /* If the longest source string is shorter than the lower bound
2017 of the specified count the copy is definitely nul-terminated. */
2018 if (wi::ltu_p (lenrange
[1], cntrange
[0]))
2021 if (wi::neg_p (lenrange
[1]))
2023 /* The length of one of the strings is unknown but at least
2024 one has non-zero length and that length is stored in
2025 LENRANGE[1]. Swap the bounds to force a "may be truncated"
2027 lenrange
[1] = lenrange
[0];
2028 lenrange
[0] = wi::shwi (0, prec
);
2031 /* Set to true for strncat whose bound is derived from the length
2032 of the destination (the expected usage pattern). */
2033 bool cat_dstlen_bounded
= false;
2034 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STRNCAT
)
2035 cat_dstlen_bounded
= is_strlen_related_p (dst
, cnt
);
2037 if (lenrange
[0] == cntrange
[1] && cntrange
[0] == cntrange
[1])
2038 return warning_n (callloc
, OPT_Wstringop_truncation
,
2039 cntrange
[0].to_uhwi (),
2040 "%G%qD output truncated before terminating "
2041 "nul copying %E byte from a string of the "
2043 "%G%qD output truncated before terminating nul "
2044 "copying %E bytes from a string of the same "
2047 else if (!cat_dstlen_bounded
)
2049 if (wi::geu_p (lenrange
[0], cntrange
[1]))
2051 /* The shortest string is longer than the upper bound of
2052 the count so the truncation is certain. */
2053 if (cntrange
[0] == cntrange
[1])
2054 return warning_n (callloc
, OPT_Wstringop_truncation
,
2055 cntrange
[0].to_uhwi (),
2056 "%G%qD output truncated copying %E byte "
2057 "from a string of length %wu",
2058 "%G%qD output truncated copying %E bytes "
2059 "from a string of length %wu",
2060 stmt
, func
, cnt
, lenrange
[0].to_uhwi ());
2062 return warning_at (callloc
, OPT_Wstringop_truncation
,
2063 "%G%qD output truncated copying between %wu "
2064 "and %wu bytes from a string of length %wu",
2065 stmt
, func
, cntrange
[0].to_uhwi (),
2066 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
2068 else if (wi::geu_p (lenrange
[1], cntrange
[1]))
2070 /* The longest string is longer than the upper bound of
2071 the count so the truncation is possible. */
2072 if (cntrange
[0] == cntrange
[1])
2073 return warning_n (callloc
, OPT_Wstringop_truncation
,
2074 cntrange
[0].to_uhwi (),
2075 "%G%qD output may be truncated copying %E "
2076 "byte from a string of length %wu",
2077 "%G%qD output may be truncated copying %E "
2078 "bytes from a string of length %wu",
2079 stmt
, func
, cnt
, lenrange
[1].to_uhwi ());
2081 return warning_at (callloc
, OPT_Wstringop_truncation
,
2082 "%G%qD output may be truncated copying between "
2083 "%wu and %wu bytes from a string of length %wu",
2084 stmt
, func
, cntrange
[0].to_uhwi (),
2085 cntrange
[1].to_uhwi (), lenrange
[1].to_uhwi ());
2089 if (!cat_dstlen_bounded
2090 && cntrange
[0] != cntrange
[1]
2091 && wi::leu_p (cntrange
[0], lenrange
[0])
2092 && wi::leu_p (cntrange
[1], lenrange
[0] + 1))
2094 /* If the source (including the terminating nul) is longer than
2095 the lower bound of the specified count but shorter than the
2096 upper bound the copy may (but need not) be truncated. */
2097 return warning_at (callloc
, OPT_Wstringop_truncation
,
2098 "%G%qD output may be truncated copying between "
2099 "%wu and %wu bytes from a string of length %wu",
2100 stmt
, func
, cntrange
[0].to_uhwi (),
2101 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
2105 if (tree dstsize
= compute_objsize (dst
, 1))
2107 /* The source length is uknown. Try to determine the destination
2108 size and see if it matches the specified bound. If not, bail.
2109 Otherwise go on to see if it should be diagnosed for possible
2114 if (wi::to_wide (dstsize
) != cntrange
[1])
2117 /* Avoid warning for strncpy(a, b, N) calls where the following
2119 N == sizeof a && N == sizeof b */
2120 if (tree srcsize
= compute_objsize (src
, 1))
2121 if (wi::to_wide (srcsize
) == cntrange
[1])
2124 if (cntrange
[0] == cntrange
[1])
2125 return warning_at (callloc
, OPT_Wstringop_truncation
,
2126 "%G%qD specified bound %E equals destination size",
2133 /* Check the arguments to the built-in forms of stpncpy and strncpy for
2134 out-of-bounds offsets or overlapping access, and to see if the size
2135 is derived from calling strlen() on the source argument, and if so,
2136 issue the appropriate warning. */
2139 handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*gsi
)
2141 if (!strlen_to_stridx
)
2144 gimple
*stmt
= gsi_stmt (*gsi
);
2146 tree dst
= gimple_call_arg (stmt
, 0);
2147 tree src
= gimple_call_arg (stmt
, 1);
2148 tree len
= gimple_call_arg (stmt
, 2);
2149 tree dstsize
= NULL_TREE
, srcsize
= NULL_TREE
;
2151 int didx
= get_stridx (dst
);
2152 if (strinfo
*sidst
= didx
> 0 ? get_strinfo (didx
) : NULL
)
2154 /* Compute the size of the destination string including the NUL. */
2155 if (sidst
->nonzero_chars
)
2157 tree type
= TREE_TYPE (sidst
->nonzero_chars
);
2158 dstsize
= fold_build2 (PLUS_EXPR
, type
, sidst
->nonzero_chars
,
2159 build_int_cst (type
, 1));
2164 int sidx
= get_stridx (src
);
2165 strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
;
2168 /* strncat() and strncpy() can modify the source string by writing
2169 over the terminating nul so SISRC->DONT_INVALIDATE must be left
2172 /* Compute the size of the source string including the NUL. */
2173 if (sisrc
->nonzero_chars
)
2175 tree type
= TREE_TYPE (sisrc
->nonzero_chars
);
2176 srcsize
= fold_build2 (PLUS_EXPR
, type
, sisrc
->nonzero_chars
,
2177 build_int_cst (type
, 1));
2183 srcsize
= NULL_TREE
;
2185 if (!check_bounds_or_overlap (stmt
, dst
, src
, dstsize
, srcsize
))
2187 gimple_set_no_warning (stmt
, true);
2191 /* If the length argument was computed from strlen(S) for some string
2192 S retrieve the strinfo index for the string (PSS->FIRST) alonng with
2193 the location of the strlen() call (PSS->SECOND). */
2194 stridx_strlenloc
*pss
= strlen_to_stridx
->get (len
);
2195 if (!pss
|| pss
->first
<= 0)
2197 if (maybe_diag_stxncpy_trunc (*gsi
, src
, len
))
2198 gimple_set_no_warning (stmt
, true);
2203 /* Retrieve the strinfo data for the string S that LEN was computed
2204 from as some function F of strlen (S) (i.e., LEN need not be equal
2206 strinfo
*silen
= get_strinfo (pss
->first
);
2208 location_t callloc
= gimple_nonartificial_location (stmt
);
2209 callloc
= expansion_point_location_if_in_system_header (callloc
);
2211 tree func
= gimple_call_fndecl (stmt
);
2213 bool warned
= false;
2215 /* When -Wstringop-truncation is set, try to determine truncation
2216 before diagnosing possible overflow. Truncation is implied by
2217 the LEN argument being equal to strlen(SRC), regardless of
2218 whether its value is known. Otherwise, issue the more generic
2219 -Wstringop-overflow which triggers for LEN arguments that in
2220 any meaningful way depend on strlen(SRC). */
2222 && is_strlen_related_p (src
, len
)
2223 && warning_at (callloc
, OPT_Wstringop_truncation
,
2224 "%G%qD output truncated before terminating nul "
2225 "copying as many bytes from a string as its length",
2228 else if (silen
&& is_strlen_related_p (src
, silen
->ptr
))
2229 warned
= warning_at (callloc
, OPT_Wstringop_overflow_
,
2230 "%G%qD specified bound depends on the length "
2231 "of the source argument",
2235 location_t strlenloc
= pss
->second
;
2236 if (strlenloc
!= UNKNOWN_LOCATION
&& strlenloc
!= callloc
)
2237 inform (strlenloc
, "length computed here");
2241 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
2242 If strlen of the second argument is known and length of the third argument
2243 is that plus one, strlen of the first argument is the same after this
2247 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2250 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
2251 gimple
*stmt
= gsi_stmt (*gsi
);
2252 strinfo
*si
, *dsi
, *olddsi
;
2254 len
= gimple_call_arg (stmt
, 2);
2255 src
= gimple_call_arg (stmt
, 1);
2256 dst
= gimple_call_arg (stmt
, 0);
2257 idx
= get_stridx (src
);
2261 didx
= get_stridx (dst
);
2264 olddsi
= get_strinfo (didx
);
2269 && tree_fits_uhwi_p (len
)
2270 && !integer_zerop (len
))
2271 adjust_last_stmt (olddsi
, stmt
, false);
2278 /* Handle memcpy (x, y, l) where l's relationship with strlen (y)
2280 si
= get_strinfo (idx
);
2281 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
2283 if (TREE_CODE (len
) == INTEGER_CST
2284 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
2286 if (tree_int_cst_le (len
, si
->nonzero_chars
))
2288 /* Copying LEN nonzero characters, where LEN is constant. */
2290 full_string_p
= false;
2294 /* Copying the whole of the analyzed part of SI. */
2295 newlen
= si
->nonzero_chars
;
2296 full_string_p
= si
->full_string_p
;
2301 if (!si
->full_string_p
)
2303 if (TREE_CODE (len
) != SSA_NAME
)
2305 def_stmt
= SSA_NAME_DEF_STMT (len
);
2306 if (!is_gimple_assign (def_stmt
)
2307 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
2308 || gimple_assign_rhs1 (def_stmt
) != si
->nonzero_chars
2309 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
2311 /* Copying variable-length string SI (and no more). */
2312 newlen
= si
->nonzero_chars
;
2313 full_string_p
= true;
2319 /* Handle memcpy (x, "abcd", 5) or
2320 memcpy (x, "abc\0uvw", 7). */
2321 if (!tree_fits_uhwi_p (len
))
2324 unsigned HOST_WIDE_INT clen
= tree_to_uhwi (len
);
2325 unsigned HOST_WIDE_INT nonzero_chars
= ~idx
;
2326 newlen
= build_int_cst (size_type_node
, MIN (nonzero_chars
, clen
));
2327 full_string_p
= clen
> nonzero_chars
;
2332 && olddsi
->nonzero_chars
2333 && TREE_CODE (olddsi
->nonzero_chars
) == INTEGER_CST
2334 && tree_int_cst_le (newlen
, olddsi
->nonzero_chars
))
2336 /* The SRC substring being written strictly overlaps
2337 a subsequence of the existing string OLDDSI. */
2338 newlen
= olddsi
->nonzero_chars
;
2339 full_string_p
= olddsi
->full_string_p
;
2342 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
2343 adjust_last_stmt (olddsi
, stmt
, false);
2347 didx
= new_stridx (dst
);
2354 dsi
= unshare_strinfo (olddsi
);
2355 oldlen
= olddsi
->nonzero_chars
;
2356 dsi
->nonzero_chars
= newlen
;
2357 dsi
->full_string_p
= full_string_p
;
2358 /* Break the chain, so adjust_related_strinfo on later pointers in
2359 the chain won't adjust this one anymore. */
2362 dsi
->endptr
= NULL_TREE
;
2366 dsi
= new_strinfo (dst
, didx
, newlen
, full_string_p
);
2367 set_strinfo (didx
, dsi
);
2368 find_equal_ptrs (dst
, didx
);
2370 dsi
->writable
= true;
2371 dsi
->dont_invalidate
= true;
2374 tree adj
= NULL_TREE
;
2375 location_t loc
= gimple_location (stmt
);
2376 if (oldlen
== NULL_TREE
)
2378 else if (integer_zerop (oldlen
))
2380 else if (TREE_CODE (oldlen
) == INTEGER_CST
2381 || TREE_CODE (newlen
) == INTEGER_CST
)
2382 adj
= fold_build2_loc (loc
, MINUS_EXPR
, TREE_TYPE (newlen
), newlen
,
2383 fold_convert_loc (loc
, TREE_TYPE (newlen
),
2385 if (adj
!= NULL_TREE
)
2386 adjust_related_strinfos (loc
, dsi
, adj
);
2390 /* memcpy src may not overlap dst, so src doesn't need to be
2391 invalidated either. */
2393 si
->dont_invalidate
= true;
2397 lhs
= gimple_call_lhs (stmt
);
2400 case BUILT_IN_MEMCPY
:
2401 case BUILT_IN_MEMCPY_CHK
:
2402 /* Allow adjust_last_stmt to decrease this memcpy's size. */
2403 laststmt
.stmt
= stmt
;
2404 laststmt
.len
= dsi
->nonzero_chars
;
2405 laststmt
.stridx
= dsi
->idx
;
2407 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
2409 case BUILT_IN_MEMPCPY
:
2410 case BUILT_IN_MEMPCPY_CHK
:
2418 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
2419 If strlen of the second argument is known, strlen of the first argument
2420 is increased by the length of the second argument. Furthermore, attempt
2421 to convert it to memcpy/strcpy if the length of the first argument
2425 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2428 tree srclen
, args
, type
, fn
, objsz
, endptr
;
2430 gimple
*stmt
= gsi_stmt (*gsi
);
2432 location_t loc
= gimple_location (stmt
);
2434 tree src
= gimple_call_arg (stmt
, 1);
2435 tree dst
= gimple_call_arg (stmt
, 0);
2437 /* Bail if the source is the same as destination. It will be diagnosed
2439 if (operand_equal_p (src
, dst
, 0))
2442 tree lhs
= gimple_call_lhs (stmt
);
2444 didx
= get_stridx (dst
);
2450 dsi
= get_strinfo (didx
);
2454 idx
= get_stridx (src
);
2456 srclen
= build_int_cst (size_type_node
, ~idx
);
2459 si
= get_strinfo (idx
);
2461 srclen
= get_string_length (si
);
2464 /* Set the no-warning bit on the transformed statement? */
2465 bool set_no_warning
= false;
2467 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
2470 /* The concatenation always involves copying at least one byte
2471 (the terminating nul), even if the source string is empty.
2472 If the source is unknown assume it's one character long and
2473 used that as both sizes. */
2477 tree type
= TREE_TYPE (slen
);
2478 slen
= fold_build2 (PLUS_EXPR
, type
, slen
, build_int_cst (type
, 1));
2481 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2483 if (!check_bounds_or_overlap (stmt
, dst
, sptr
, NULL_TREE
, slen
))
2485 gimple_set_no_warning (stmt
, true);
2486 set_no_warning
= true;
2490 /* strcat (p, q) can be transformed into
2491 tmp = p + strlen (p); endptr = stpcpy (tmp, q);
2492 with length endptr - p if we need to compute the length
2493 later on. Don't do this transformation if we don't need
2495 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
2499 didx
= new_stridx (dst
);
2505 dsi
= new_strinfo (dst
, didx
, NULL_TREE
, false);
2506 set_strinfo (didx
, dsi
);
2507 find_equal_ptrs (dst
, didx
);
2511 dsi
= unshare_strinfo (dsi
);
2512 dsi
->nonzero_chars
= NULL_TREE
;
2513 dsi
->full_string_p
= false;
2515 dsi
->endptr
= NULL_TREE
;
2517 dsi
->writable
= true;
2519 dsi
->dont_invalidate
= true;
2524 tree dstlen
= dsi
->nonzero_chars
;
2525 endptr
= dsi
->endptr
;
2527 dsi
= unshare_strinfo (dsi
);
2528 dsi
->endptr
= NULL_TREE
;
2530 dsi
->writable
= true;
2532 if (srclen
!= NULL_TREE
)
2534 dsi
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
2535 TREE_TYPE (dsi
->nonzero_chars
),
2536 dsi
->nonzero_chars
, srclen
);
2537 gcc_assert (dsi
->full_string_p
);
2538 adjust_related_strinfos (loc
, dsi
, srclen
);
2539 dsi
->dont_invalidate
= true;
2543 dsi
->nonzero_chars
= NULL
;
2544 dsi
->full_string_p
= false;
2545 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
2546 dsi
->dont_invalidate
= true;
2550 /* strcat src may not overlap dst, so src doesn't need to be
2551 invalidated either. */
2552 si
->dont_invalidate
= true;
2554 /* For now. Could remove the lhs from the call and add
2555 lhs = dst; afterwards. */
2563 case BUILT_IN_STRCAT
:
2564 if (srclen
!= NULL_TREE
)
2565 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
2567 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
2569 case BUILT_IN_STRCAT_CHK
:
2570 if (srclen
!= NULL_TREE
)
2571 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
2573 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
2574 objsz
= gimple_call_arg (stmt
, 2);
2580 if (fn
== NULL_TREE
)
2585 tree type
= TREE_TYPE (dstlen
);
2587 /* Compute the size of the source sequence, including the nul. */
2588 tree srcsize
= srclen
? srclen
: size_zero_node
;
2589 srcsize
= fold_build2 (PLUS_EXPR
, type
, srcsize
, build_int_cst (type
, 1));
2591 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2593 if (!check_bounds_or_overlap (stmt
, dst
, sptr
, dstlen
, srcsize
))
2595 gimple_set_no_warning (stmt
, true);
2596 set_no_warning
= true;
2600 tree len
= NULL_TREE
;
2601 if (srclen
!= NULL_TREE
)
2603 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
2604 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
2606 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
2607 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
2608 build_int_cst (type
, 1));
2609 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
2613 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
2615 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
, TREE_TYPE (dst
), dst
,
2616 fold_convert_loc (loc
, sizetype
,
2617 unshare_expr (dstlen
)));
2618 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
2622 objsz
= fold_build2_loc (loc
, MINUS_EXPR
, TREE_TYPE (objsz
), objsz
,
2623 fold_convert_loc (loc
, TREE_TYPE (objsz
),
2624 unshare_expr (dstlen
)));
2625 objsz
= force_gimple_operand_gsi (gsi
, objsz
, true, NULL_TREE
, true,
2628 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2630 fprintf (dump_file
, "Optimizing: ");
2631 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2633 if (srclen
!= NULL_TREE
)
2634 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
2635 dst
, src
, len
, objsz
);
2637 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
2641 stmt
= gsi_stmt (*gsi
);
2643 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2645 fprintf (dump_file
, "into: ");
2646 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2648 /* If srclen == NULL, note that current string length can be
2649 computed by transforming this strcpy into stpcpy. */
2650 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
2652 adjust_last_stmt (dsi
, stmt
, true);
2653 if (srclen
!= NULL_TREE
)
2655 laststmt
.stmt
= stmt
;
2656 laststmt
.len
= srclen
;
2657 laststmt
.stridx
= dsi
->idx
;
2660 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2661 fprintf (dump_file
, "not possible.\n");
2664 gimple_set_no_warning (stmt
, true);
2667 /* Handle a call to malloc or calloc. */
2670 handle_builtin_malloc (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2672 gimple
*stmt
= gsi_stmt (*gsi
);
2673 tree lhs
= gimple_call_lhs (stmt
);
2674 if (lhs
== NULL_TREE
)
2677 gcc_assert (get_stridx (lhs
) == 0);
2678 int idx
= new_stridx (lhs
);
2679 tree length
= NULL_TREE
;
2680 if (bcode
== BUILT_IN_CALLOC
)
2681 length
= build_int_cst (size_type_node
, 0);
2682 strinfo
*si
= new_strinfo (lhs
, idx
, length
, length
!= NULL_TREE
);
2683 if (bcode
== BUILT_IN_CALLOC
)
2685 set_strinfo (idx
, si
);
2686 si
->writable
= true;
2688 si
->dont_invalidate
= true;
2691 /* Handle a call to memset.
2692 After a call to calloc, memset(,0,) is unnecessary.
2693 memset(malloc(n),0,n) is calloc(n,1).
2694 return true when the call is transfomred, false otherwise. */
2697 handle_builtin_memset (gimple_stmt_iterator
*gsi
)
2699 gimple
*stmt2
= gsi_stmt (*gsi
);
2700 if (!integer_zerop (gimple_call_arg (stmt2
, 1)))
2702 tree ptr
= gimple_call_arg (stmt2
, 0);
2703 int idx1
= get_stridx (ptr
);
2706 strinfo
*si1
= get_strinfo (idx1
);
2709 gimple
*stmt1
= si1
->stmt
;
2710 if (!stmt1
|| !is_gimple_call (stmt1
))
2712 tree callee1
= gimple_call_fndecl (stmt1
);
2713 if (!valid_builtin_call (stmt1
))
2715 enum built_in_function code1
= DECL_FUNCTION_CODE (callee1
);
2716 tree size
= gimple_call_arg (stmt2
, 2);
2717 if (code1
== BUILT_IN_CALLOC
)
2718 /* Not touching stmt1 */ ;
2719 else if (code1
== BUILT_IN_MALLOC
2720 && operand_equal_p (gimple_call_arg (stmt1
, 0), size
, 0))
2722 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt1
);
2723 update_gimple_call (&gsi1
, builtin_decl_implicit (BUILT_IN_CALLOC
), 2,
2724 size
, build_one_cst (size_type_node
));
2725 si1
->nonzero_chars
= build_int_cst (size_type_node
, 0);
2726 si1
->full_string_p
= true;
2727 si1
->stmt
= gsi_stmt (gsi1
);
2731 tree lhs
= gimple_call_lhs (stmt2
);
2732 unlink_stmt_vdef (stmt2
);
2735 gimple
*assign
= gimple_build_assign (lhs
, ptr
);
2736 gsi_replace (gsi
, assign
, false);
2740 gsi_remove (gsi
, true);
2741 release_defs (stmt2
);
2747 /* Handle a call to memcmp. We try to handle small comparisons by
2748 converting them to load and compare, and replacing the call to memcmp
2749 with a __builtin_memcmp_eq call where possible.
2750 return true when call is transformed, return false otherwise. */
2753 handle_builtin_memcmp (gimple_stmt_iterator
*gsi
)
2755 gcall
*stmt2
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2756 tree res
= gimple_call_lhs (stmt2
);
2757 tree arg1
= gimple_call_arg (stmt2
, 0);
2758 tree arg2
= gimple_call_arg (stmt2
, 1);
2759 tree len
= gimple_call_arg (stmt2
, 2);
2760 unsigned HOST_WIDE_INT leni
;
2761 use_operand_p use_p
;
2762 imm_use_iterator iter
;
2767 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
2769 gimple
*ustmt
= USE_STMT (use_p
);
2771 if (is_gimple_debug (ustmt
))
2773 if (gimple_code (ustmt
) == GIMPLE_ASSIGN
)
2775 gassign
*asgn
= as_a
<gassign
*> (ustmt
);
2776 tree_code code
= gimple_assign_rhs_code (asgn
);
2777 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2778 || !integer_zerop (gimple_assign_rhs2 (asgn
)))
2781 else if (gimple_code (ustmt
) == GIMPLE_COND
)
2783 tree_code code
= gimple_cond_code (ustmt
);
2784 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2785 || !integer_zerop (gimple_cond_rhs (ustmt
)))
2792 if (tree_fits_uhwi_p (len
)
2793 && (leni
= tree_to_uhwi (len
)) <= GET_MODE_SIZE (word_mode
)
2794 && pow2p_hwi (leni
))
2796 leni
*= CHAR_TYPE_SIZE
;
2797 unsigned align1
= get_pointer_alignment (arg1
);
2798 unsigned align2
= get_pointer_alignment (arg2
);
2799 unsigned align
= MIN (align1
, align2
);
2800 scalar_int_mode mode
;
2801 if (int_mode_for_size (leni
, 1).exists (&mode
)
2802 && (align
>= leni
|| !targetm
.slow_unaligned_access (mode
, align
)))
2804 location_t loc
= gimple_location (stmt2
);
2806 type
= build_nonstandard_integer_type (leni
, 1);
2807 gcc_assert (known_eq (GET_MODE_BITSIZE (TYPE_MODE (type
)), leni
));
2808 tree ptrtype
= build_pointer_type_for_mode (char_type_node
,
2810 off
= build_int_cst (ptrtype
, 0);
2811 arg1
= build2_loc (loc
, MEM_REF
, type
, arg1
, off
);
2812 arg2
= build2_loc (loc
, MEM_REF
, type
, arg2
, off
);
2813 tree tem1
= fold_const_aggregate_ref (arg1
);
2816 tree tem2
= fold_const_aggregate_ref (arg2
);
2819 res
= fold_convert_loc (loc
, TREE_TYPE (res
),
2820 fold_build2_loc (loc
, NE_EXPR
,
2823 gimplify_and_update_call_from_tree (gsi
, res
);
2828 gimple_call_set_fndecl (stmt2
, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ
));
2832 /* Given an index to the strinfo vector, compute the string length for the
2833 corresponding string. Return -1 when unknown. */
2835 static HOST_WIDE_INT
2836 compute_string_length (int idx
)
2838 HOST_WIDE_INT string_leni
= -1;
2839 gcc_assert (idx
!= 0);
2844 strinfo
*si
= get_strinfo (idx
);
2847 tree const_string_len
= get_string_length (si
);
2848 if (const_string_len
&& tree_fits_shwi_p (const_string_len
))
2849 string_leni
= tree_to_shwi (const_string_len
);
2852 if (string_leni
< 0)
2858 /* Determine the minimum size of the object referenced by DEST expression which
2859 must have a pointer type.
2860 Return the minimum size of the object if successful or NULL when the size
2861 cannot be determined. */
2863 determine_min_objsize (tree dest
)
2865 unsigned HOST_WIDE_INT size
= 0;
2867 if (compute_builtin_object_size (dest
, 2, &size
))
2868 return build_int_cst (sizetype
, size
);
2870 /* Try to determine the size of the object through the RHS of the
2871 assign statement. */
2872 if (TREE_CODE (dest
) == SSA_NAME
)
2874 gimple
*stmt
= SSA_NAME_DEF_STMT (dest
);
2875 if (!is_gimple_assign (stmt
))
2878 if (!gimple_assign_single_p (stmt
)
2879 && !gimple_assign_unary_nop_p (stmt
))
2882 dest
= gimple_assign_rhs1 (stmt
);
2883 return determine_min_objsize (dest
);
2886 /* Try to determine the size of the object from its type. */
2887 if (TREE_CODE (dest
) != ADDR_EXPR
)
2890 tree type
= TREE_TYPE (dest
);
2891 if (TREE_CODE (type
) == POINTER_TYPE
)
2892 type
= TREE_TYPE (type
);
2894 type
= TYPE_MAIN_VARIANT (type
);
2896 /* We cannot determine the size of the array if it's a flexible array,
2897 which is declared at the end of a structure. */
2898 if (TREE_CODE (type
) == ARRAY_TYPE
2899 && !array_at_struct_end_p (dest
))
2901 tree
size_t = TYPE_SIZE_UNIT (type
);
2902 if (size_t && TREE_CODE (size_t) == INTEGER_CST
2903 && !integer_zerop (size_t))
2910 /* Handle a call to strcmp or strncmp. When the result is ONLY used to do
2911 equality test against zero:
2913 A. When the lengths of both arguments are constant and it's a strcmp:
2914 * if the lengths are NOT equal, we can safely fold the call
2915 to a non-zero value.
2916 * otherwise, do nothing now.
2918 B. When the length of one argument is constant, try to replace the call with
2919 a __builtin_str(n)cmp_eq call where possible, i.e:
2921 strncmp (s, STR, C) (!)= 0 in which, s is a pointer to a string, STR is a
2922 string with constant length , C is a constant.
2923 if (C <= strlen(STR) && sizeof_array(s) > C)
2925 replace this call with
2926 strncmp_eq (s, STR, C) (!)= 0
2930 it can be safely treated as a call to strcmp (s, STR) (!)= 0
2931 can handled by the following strcmp.
2934 strcmp (s, STR) (!)= 0 in which, s is a pointer to a string, STR is a
2935 string with constant length.
2936 if (sizeof_array(s) > strlen(STR))
2938 replace this call with
2939 strcmp_eq (s, STR, strlen(STR)+1) (!)= 0
2942 Return true when the call is transformed, return false otherwise.
2946 handle_builtin_string_cmp (gimple_stmt_iterator
*gsi
)
2948 gcall
*stmt
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2949 tree res
= gimple_call_lhs (stmt
);
2950 use_operand_p use_p
;
2951 imm_use_iterator iter
;
2952 tree arg1
= gimple_call_arg (stmt
, 0);
2953 tree arg2
= gimple_call_arg (stmt
, 1);
2954 int idx1
= get_stridx (arg1
);
2955 int idx2
= get_stridx (arg2
);
2956 HOST_WIDE_INT length
= -1;
2957 bool is_ncmp
= false;
2962 /* When both arguments are unknown, do nothing. */
2963 if (idx1
== 0 && idx2
== 0)
2966 /* Handle strncmp function. */
2967 if (gimple_call_num_args (stmt
) == 3)
2969 tree len
= gimple_call_arg (stmt
, 2);
2970 if (tree_fits_shwi_p (len
))
2971 length
= tree_to_shwi (len
);
2976 /* For strncmp, if the length argument is NOT known, do nothing. */
2977 if (is_ncmp
&& length
< 0)
2980 /* When the result is ONLY used to do equality test against zero. */
2981 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
2983 gimple
*use_stmt
= USE_STMT (use_p
);
2985 if (is_gimple_debug (use_stmt
))
2987 if (gimple_code (use_stmt
) == GIMPLE_ASSIGN
)
2989 tree_code code
= gimple_assign_rhs_code (use_stmt
);
2990 if (code
== COND_EXPR
)
2992 tree cond_expr
= gimple_assign_rhs1 (use_stmt
);
2993 if ((TREE_CODE (cond_expr
) != EQ_EXPR
2994 && (TREE_CODE (cond_expr
) != NE_EXPR
))
2995 || !integer_zerop (TREE_OPERAND (cond_expr
, 1)))
2998 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3000 if (!integer_zerop (gimple_assign_rhs2 (use_stmt
)))
3006 else if (gimple_code (use_stmt
) == GIMPLE_COND
)
3008 tree_code code
= gimple_cond_code (use_stmt
);
3009 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
3010 || !integer_zerop (gimple_cond_rhs (use_stmt
)))
3017 /* When the lengths of both arguments are known, and they are unequal, we can
3018 safely fold the call to a non-zero value for strcmp;
3019 othewise, do nothing now. */
3020 if (idx1
!= 0 && idx2
!= 0)
3022 HOST_WIDE_INT const_string_leni1
= compute_string_length (idx1
);
3023 HOST_WIDE_INT const_string_leni2
= compute_string_length (idx2
);
3026 && const_string_leni1
!= -1
3027 && const_string_leni2
!= -1
3028 && const_string_leni1
!= const_string_leni2
)
3030 replace_call_with_value (gsi
, integer_one_node
);
3036 /* When the length of one argument is constant. */
3037 tree var_string
= NULL_TREE
;
3038 HOST_WIDE_INT const_string_leni
= -1;
3042 const_string_leni
= compute_string_length (idx1
);
3047 gcc_checking_assert (idx2
);
3048 const_string_leni
= compute_string_length (idx2
);
3052 if (const_string_leni
< 0)
3055 unsigned HOST_WIDE_INT var_sizei
= 0;
3056 /* try to determine the minimum size of the object pointed by var_string. */
3057 tree size
= determine_min_objsize (var_string
);
3062 if (tree_fits_uhwi_p (size
))
3063 var_sizei
= tree_to_uhwi (size
);
3068 /* For strncmp, if length > const_string_leni , this call can be safely
3069 transformed to a strcmp. */
3070 if (is_ncmp
&& length
> const_string_leni
)
3073 unsigned HOST_WIDE_INT final_length
3074 = is_ncmp
? length
: const_string_leni
+ 1;
3076 /* Replace strcmp or strncmp with the corresponding str(n)cmp_eq. */
3077 if (var_sizei
> final_length
)
3081 ? builtin_decl_implicit (BUILT_IN_STRNCMP_EQ
)
3082 : builtin_decl_implicit (BUILT_IN_STRCMP_EQ
));
3085 tree const_string_len
= build_int_cst (size_type_node
, final_length
);
3086 update_gimple_call (gsi
, fn
, 3, arg1
, arg2
, const_string_len
);
3094 /* Handle a POINTER_PLUS_EXPR statement.
3095 For p = "abcd" + 2; compute associated length, or if
3096 p = q + off is pointing to a '\0' character of a string, call
3097 zero_length_string on it. */
3100 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
3102 gimple
*stmt
= gsi_stmt (*gsi
);
3103 tree lhs
= gimple_assign_lhs (stmt
), off
;
3104 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
3112 tree off
= gimple_assign_rhs2 (stmt
);
3113 if (tree_fits_uhwi_p (off
)
3114 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
3115 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
3116 = ~(~idx
- (int) tree_to_uhwi (off
));
3120 si
= get_strinfo (idx
);
3121 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
3124 off
= gimple_assign_rhs2 (stmt
);
3126 if (si
->full_string_p
&& operand_equal_p (si
->nonzero_chars
, off
, 0))
3127 zsi
= zero_length_string (lhs
, si
);
3128 else if (TREE_CODE (off
) == SSA_NAME
)
3130 gimple
*def_stmt
= SSA_NAME_DEF_STMT (off
);
3131 if (gimple_assign_single_p (def_stmt
)
3132 && si
->full_string_p
3133 && operand_equal_p (si
->nonzero_chars
,
3134 gimple_assign_rhs1 (def_stmt
), 0))
3135 zsi
= zero_length_string (lhs
, si
);
3138 && si
->endptr
!= NULL_TREE
3139 && si
->endptr
!= lhs
3140 && TREE_CODE (si
->endptr
) == SSA_NAME
)
3142 enum tree_code rhs_code
3143 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
3144 ? SSA_NAME
: NOP_EXPR
;
3145 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
);
3146 gcc_assert (gsi_stmt (*gsi
) == stmt
);
3151 /* If RHS, either directly or indirectly, refers to a string of constant
3152 length, return the length. Otherwise, if it refers to a character
3153 constant, return 1 if the constant is non-zero and 0 if it is nul.
3154 Otherwise, return a negative value. */
3156 static HOST_WIDE_INT
3157 get_min_string_length (tree rhs
, bool *full_string_p
)
3159 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs
)))
3161 if (tree_expr_nonzero_p (rhs
))
3163 *full_string_p
= false;
3167 *full_string_p
= true;
3171 if (TREE_CODE (rhs
) == MEM_REF
3172 && integer_zerop (TREE_OPERAND (rhs
, 1)))
3174 rhs
= TREE_OPERAND (rhs
, 0);
3175 if (TREE_CODE (rhs
) == ADDR_EXPR
)
3177 tree rhs_addr
= rhs
;
3179 rhs
= TREE_OPERAND (rhs
, 0);
3180 if (TREE_CODE (rhs
) != STRING_CST
)
3182 int idx
= get_stridx (rhs_addr
);
3185 strinfo
*si
= get_strinfo (idx
);
3187 && tree_fits_shwi_p (si
->nonzero_chars
))
3189 *full_string_p
= si
->full_string_p
;
3190 return tree_to_shwi (si
->nonzero_chars
);
3197 if (TREE_CODE (rhs
) == VAR_DECL
3198 && TREE_READONLY (rhs
))
3199 rhs
= DECL_INITIAL (rhs
);
3201 if (rhs
&& TREE_CODE (rhs
) == STRING_CST
)
3203 *full_string_p
= true;
3204 return strlen (TREE_STRING_POINTER (rhs
));
3210 /* Handle a single or multiple character store either by single
3211 character assignment or by multi-character assignment from
3215 handle_char_store (gimple_stmt_iterator
*gsi
)
3219 gimple
*stmt
= gsi_stmt (*gsi
);
3220 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
3221 tree rhs
= gimple_assign_rhs1 (stmt
);
3222 unsigned HOST_WIDE_INT offset
= 0;
3224 if (TREE_CODE (lhs
) == MEM_REF
3225 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
3227 tree mem_offset
= TREE_OPERAND (lhs
, 1);
3228 if (tree_fits_uhwi_p (mem_offset
))
3230 /* Get the strinfo for the base, and use it if it starts with at
3231 least OFFSET nonzero characters. This is trivially true if
3233 offset
= tree_to_uhwi (mem_offset
);
3234 idx
= get_stridx (TREE_OPERAND (lhs
, 0));
3236 si
= get_strinfo (idx
);
3238 ssaname
= TREE_OPERAND (lhs
, 0);
3239 else if (si
== NULL
|| compare_nonzero_chars (si
, offset
) < 0)
3245 idx
= get_addr_stridx (lhs
, NULL_TREE
, &offset
);
3247 si
= get_strinfo (idx
);
3250 /* STORING_NONZERO_P is true iff not all stored characters are zero.
3251 STORING_ALL_ZEROS_P is true iff all stored characters are zero.
3252 Both are false when it's impossible to determine which is true. */
3253 bool storing_nonzero_p
;
3254 bool storing_all_zeros_p
= initializer_zerop (rhs
, &storing_nonzero_p
);
3255 if (!storing_nonzero_p
)
3256 storing_nonzero_p
= tree_expr_nonzero_p (rhs
);
3257 bool full_string_p
= storing_all_zeros_p
;
3259 /* Set to the length of the string being assigned if known. */
3260 HOST_WIDE_INT rhslen
;
3264 int cmp
= compare_nonzero_chars (si
, offset
);
3265 gcc_assert (offset
== 0 || cmp
>= 0);
3266 if (storing_all_zeros_p
&& cmp
== 0 && si
->full_string_p
)
3268 /* When overwriting a '\0' with a '\0', the store can be removed
3269 if we know it has been stored in the current function. */
3270 if (!stmt_could_throw_p (cfun
, stmt
) && si
->writable
)
3272 unlink_stmt_vdef (stmt
);
3273 release_defs (stmt
);
3274 gsi_remove (gsi
, true);
3279 si
->writable
= true;
3284 /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0',
3285 and if we aren't storing '\0', we know that the length of the
3286 string and any other zero terminated string in memory remains
3287 the same. In that case we move to the next gimple statement and
3288 return to signal the caller that it shouldn't invalidate anything.
3290 This is benefical for cases like:
3295 strcpy (p, "foobar");
3296 size_t len = strlen (p); // This can be optimized into 6
3297 size_t len2 = strlen (q); // This has to be computed
3299 size_t len3 = strlen (p); // This can be optimized into 6
3300 size_t len4 = strlen (q); // This can be optimized into len2
3301 bar (len, len2, len3, len4);
3304 else if (storing_nonzero_p
&& cmp
> 0)
3309 else if (storing_all_zeros_p
|| storing_nonzero_p
|| (offset
!= 0 && cmp
> 0))
3311 /* When STORING_NONZERO_P, we know that the string will start
3312 with at least OFFSET + 1 nonzero characters. If storing
3313 a single character, set si->NONZERO_CHARS to the result.
3314 If storing multiple characters, try to determine the number
3315 of leading non-zero characters and set si->NONZERO_CHARS to
3318 When STORING_ALL_ZEROS_P, we know that the string is now
3319 OFFSET characters long.
3321 Otherwise, we're storing an unknown value at offset OFFSET,
3322 so need to clip the nonzero_chars to OFFSET. */
3323 bool full_string_p
= storing_all_zeros_p
;
3324 HOST_WIDE_INT len
= 1;
3325 if (storing_nonzero_p
)
3327 /* Try to get the minimum length of the string (or
3328 individual character) being stored. If it fails,
3329 STORING_NONZERO_P guarantees it's at least 1. */
3330 len
= get_min_string_length (rhs
, &full_string_p
);
3335 location_t loc
= gimple_location (stmt
);
3336 tree oldlen
= si
->nonzero_chars
;
3337 if (cmp
== 0 && si
->full_string_p
)
3338 /* We're overwriting the nul terminator with a nonzero or
3339 unknown character. If the previous stmt was a memcpy,
3340 its length may be decreased. */
3341 adjust_last_stmt (si
, stmt
, false);
3342 si
= unshare_strinfo (si
);
3343 if (storing_nonzero_p
)
3345 gcc_assert (len
>= 0);
3346 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
+ len
);
3349 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
);
3350 si
->full_string_p
= full_string_p
;
3351 if (storing_all_zeros_p
3353 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
3354 si
->endptr
= ssaname
;
3359 si
->writable
= true;
3360 si
->dont_invalidate
= true;
3363 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
3364 si
->nonzero_chars
, oldlen
);
3365 adjust_related_strinfos (loc
, si
, adj
);
3371 else if (idx
== 0 && (storing_all_zeros_p
|| storing_nonzero_p
))
3374 idx
= new_stridx (ssaname
);
3376 idx
= new_addr_stridx (lhs
);
3379 tree ptr
= (ssaname
? ssaname
: build_fold_addr_expr (lhs
));
3380 HOST_WIDE_INT slen
= (storing_all_zeros_p
3382 : (storing_nonzero_p
3383 ? get_min_string_length (rhs
, &full_string_p
)
3385 tree len
= (slen
<= 0
3387 : build_int_cst (size_type_node
, slen
));
3388 si
= new_strinfo (ptr
, idx
, len
, slen
>= 0 && full_string_p
);
3389 set_strinfo (idx
, si
);
3390 if (storing_all_zeros_p
3392 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
3393 si
->endptr
= ssaname
;
3394 si
->dont_invalidate
= true;
3395 si
->writable
= true;
3399 && (rhslen
= get_min_string_length (rhs
, &full_string_p
)) >= 0
3400 && ssaname
== NULL_TREE
3401 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
3403 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
3404 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> (unsigned HOST_WIDE_INT
) rhslen
)
3406 int idx
= new_addr_stridx (lhs
);
3409 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
3410 build_int_cst (size_type_node
, rhslen
),
3412 set_strinfo (idx
, si
);
3413 si
->dont_invalidate
= true;
3418 if (si
!= NULL
&& offset
== 0 && storing_all_zeros_p
)
3420 /* Allow adjust_last_stmt to remove it if the stored '\0'
3421 is immediately overwritten. */
3422 laststmt
.stmt
= stmt
;
3423 laststmt
.len
= build_int_cst (size_type_node
, 1);
3424 laststmt
.stridx
= si
->idx
;
3429 /* Try to fold strstr (s, t) eq/ne s to strncmp (s, t, strlen (t)) eq/ne 0. */
3432 fold_strstr_to_strncmp (tree rhs1
, tree rhs2
, gimple
*stmt
)
3434 if (TREE_CODE (rhs1
) != SSA_NAME
3435 || TREE_CODE (rhs2
) != SSA_NAME
)
3438 gimple
*call_stmt
= NULL
;
3439 for (int pass
= 0; pass
< 2; pass
++)
3441 gimple
*g
= SSA_NAME_DEF_STMT (rhs1
);
3442 if (gimple_call_builtin_p (g
, BUILT_IN_STRSTR
)
3443 && has_single_use (rhs1
)
3444 && gimple_call_arg (g
, 0) == rhs2
)
3449 std::swap (rhs1
, rhs2
);
3454 tree arg0
= gimple_call_arg (call_stmt
, 0);
3458 tree arg1
= gimple_call_arg (call_stmt
, 1);
3459 tree arg1_len
= NULL_TREE
;
3460 int idx
= get_stridx (arg1
);
3465 arg1_len
= build_int_cst (size_type_node
, ~idx
);
3468 strinfo
*si
= get_strinfo (idx
);
3470 arg1_len
= get_string_length (si
);
3474 if (arg1_len
!= NULL_TREE
)
3476 gimple_stmt_iterator gsi
= gsi_for_stmt (call_stmt
);
3477 tree strncmp_decl
= builtin_decl_explicit (BUILT_IN_STRNCMP
);
3479 if (!is_gimple_val (arg1_len
))
3481 tree arg1_len_tmp
= make_ssa_name (TREE_TYPE (arg1_len
));
3482 gassign
*arg1_stmt
= gimple_build_assign (arg1_len_tmp
,
3484 gsi_insert_before (&gsi
, arg1_stmt
, GSI_SAME_STMT
);
3485 arg1_len
= arg1_len_tmp
;
3488 gcall
*strncmp_call
= gimple_build_call (strncmp_decl
, 3,
3489 arg0
, arg1
, arg1_len
);
3490 tree strncmp_lhs
= make_ssa_name (integer_type_node
);
3491 gimple_set_vuse (strncmp_call
, gimple_vuse (call_stmt
));
3492 gimple_call_set_lhs (strncmp_call
, strncmp_lhs
);
3493 gsi_remove (&gsi
, true);
3494 gsi_insert_before (&gsi
, strncmp_call
, GSI_SAME_STMT
);
3495 tree zero
= build_zero_cst (TREE_TYPE (strncmp_lhs
));
3497 if (is_gimple_assign (stmt
))
3499 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
3501 tree cond
= gimple_assign_rhs1 (stmt
);
3502 TREE_OPERAND (cond
, 0) = strncmp_lhs
;
3503 TREE_OPERAND (cond
, 1) = zero
;
3507 gimple_assign_set_rhs1 (stmt
, strncmp_lhs
);
3508 gimple_assign_set_rhs2 (stmt
, zero
);
3513 gcond
*cond
= as_a
<gcond
*> (stmt
);
3514 gimple_cond_set_lhs (cond
, strncmp_lhs
);
3515 gimple_cond_set_rhs (cond
, zero
);
3523 /* Attempt to check for validity of the performed access a single statement
3524 at *GSI using string length knowledge, and to optimize it.
3525 If the given basic block needs clean-up of EH, CLEANUP_EH is set to
3529 strlen_check_and_optimize_stmt (gimple_stmt_iterator
*gsi
, bool *cleanup_eh
)
3531 gimple
*stmt
= gsi_stmt (*gsi
);
3533 if (is_gimple_call (stmt
))
3535 tree callee
= gimple_call_fndecl (stmt
);
3536 if (valid_builtin_call (stmt
))
3537 switch (DECL_FUNCTION_CODE (callee
))
3539 case BUILT_IN_STRLEN
:
3540 case BUILT_IN_STRNLEN
:
3541 handle_builtin_strlen (gsi
);
3543 case BUILT_IN_STRCHR
:
3544 handle_builtin_strchr (gsi
);
3546 case BUILT_IN_STRCPY
:
3547 case BUILT_IN_STRCPY_CHK
:
3548 case BUILT_IN_STPCPY
:
3549 case BUILT_IN_STPCPY_CHK
:
3550 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3553 case BUILT_IN_STRNCAT
:
3554 case BUILT_IN_STRNCAT_CHK
:
3555 handle_builtin_strncat (DECL_FUNCTION_CODE (callee
), gsi
);
3558 case BUILT_IN_STPNCPY
:
3559 case BUILT_IN_STPNCPY_CHK
:
3560 case BUILT_IN_STRNCPY
:
3561 case BUILT_IN_STRNCPY_CHK
:
3562 handle_builtin_stxncpy (DECL_FUNCTION_CODE (callee
), gsi
);
3565 case BUILT_IN_MEMCPY
:
3566 case BUILT_IN_MEMCPY_CHK
:
3567 case BUILT_IN_MEMPCPY
:
3568 case BUILT_IN_MEMPCPY_CHK
:
3569 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3571 case BUILT_IN_STRCAT
:
3572 case BUILT_IN_STRCAT_CHK
:
3573 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
3575 case BUILT_IN_MALLOC
:
3576 case BUILT_IN_CALLOC
:
3577 handle_builtin_malloc (DECL_FUNCTION_CODE (callee
), gsi
);
3579 case BUILT_IN_MEMSET
:
3580 if (handle_builtin_memset (gsi
))
3583 case BUILT_IN_MEMCMP
:
3584 if (handle_builtin_memcmp (gsi
))
3587 case BUILT_IN_STRCMP
:
3588 case BUILT_IN_STRNCMP
:
3589 if (handle_builtin_string_cmp (gsi
))
3596 else if (is_gimple_assign (stmt
) && !gimple_clobber_p (stmt
))
3598 tree lhs
= gimple_assign_lhs (stmt
);
3600 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
3602 if (gimple_assign_single_p (stmt
)
3603 || (gimple_assign_cast_p (stmt
)
3604 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
3606 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
3607 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
3609 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
3610 handle_pointer_plus (gsi
);
3612 else if (TREE_CODE (lhs
) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
3614 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3615 if (code
== COND_EXPR
)
3617 tree cond
= gimple_assign_rhs1 (stmt
);
3618 enum tree_code cond_code
= TREE_CODE (cond
);
3620 if (cond_code
== EQ_EXPR
|| cond_code
== NE_EXPR
)
3621 fold_strstr_to_strncmp (TREE_OPERAND (cond
, 0),
3622 TREE_OPERAND (cond
, 1), stmt
);
3624 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3625 fold_strstr_to_strncmp (gimple_assign_rhs1 (stmt
),
3626 gimple_assign_rhs2 (stmt
), stmt
);
3627 else if (gimple_assign_load_p (stmt
)
3628 && TREE_CODE (TREE_TYPE (lhs
)) == INTEGER_TYPE
3629 && TYPE_MODE (TREE_TYPE (lhs
)) == TYPE_MODE (char_type_node
)
3630 && (TYPE_PRECISION (TREE_TYPE (lhs
))
3631 == TYPE_PRECISION (char_type_node
))
3632 && !gimple_has_volatile_ops (stmt
))
3634 tree off
= integer_zero_node
;
3635 unsigned HOST_WIDE_INT coff
= 0;
3637 tree rhs1
= gimple_assign_rhs1 (stmt
);
3638 if (code
== MEM_REF
)
3640 idx
= get_stridx (TREE_OPERAND (rhs1
, 0));
3643 strinfo
*si
= get_strinfo (idx
);
3645 && si
->nonzero_chars
3646 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
3647 && (wi::to_widest (si
->nonzero_chars
)
3648 >= wi::to_widest (off
)))
3649 off
= TREE_OPERAND (rhs1
, 1);
3651 /* This case is not useful. See if get_addr_stridx
3652 returns something usable. */
3657 idx
= get_addr_stridx (rhs1
, NULL_TREE
, &coff
);
3660 strinfo
*si
= get_strinfo (idx
);
3662 && si
->nonzero_chars
3663 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
3665 widest_int w1
= wi::to_widest (si
->nonzero_chars
);
3666 widest_int w2
= wi::to_widest (off
) + coff
;
3668 && si
->full_string_p
)
3670 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3672 fprintf (dump_file
, "Optimizing: ");
3673 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3676 /* Reading the final '\0' character. */
3677 tree zero
= build_int_cst (TREE_TYPE (lhs
), 0);
3678 gimple_set_vuse (stmt
, NULL_TREE
);
3679 gimple_assign_set_rhs_from_tree (gsi
, zero
);
3681 |= maybe_clean_or_replace_eh_stmt (stmt
,
3683 stmt
= gsi_stmt (*gsi
);
3686 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3688 fprintf (dump_file
, "into: ");
3689 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3694 /* Reading a character before the final '\0'
3695 character. Just set the value range to ~[0, 0]
3696 if we don't have anything better. */
3698 tree type
= TREE_TYPE (lhs
);
3699 enum value_range_kind vr
3700 = get_range_info (lhs
, &min
, &max
);
3701 if (vr
== VR_VARYING
3703 && min
== wi::min_value (TYPE_PRECISION (type
),
3705 && max
== wi::max_value (TYPE_PRECISION (type
),
3707 set_range_info (lhs
, VR_ANTI_RANGE
,
3708 wi::zero (TYPE_PRECISION (type
)),
3709 wi::zero (TYPE_PRECISION (type
)));
3715 if (strlen_to_stridx
)
3717 tree rhs1
= gimple_assign_rhs1 (stmt
);
3718 if (stridx_strlenloc
*ps
= strlen_to_stridx
->get (rhs1
))
3719 strlen_to_stridx
->put (lhs
, stridx_strlenloc (*ps
));
3722 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
3724 tree type
= TREE_TYPE (lhs
);
3725 if (TREE_CODE (type
) == ARRAY_TYPE
)
3726 type
= TREE_TYPE (type
);
3727 if (TREE_CODE (type
) == INTEGER_TYPE
3728 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
3729 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
3731 if (! handle_char_store (gsi
))
3736 else if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
3738 enum tree_code code
= gimple_cond_code (cond
);
3739 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3740 fold_strstr_to_strncmp (gimple_cond_lhs (stmt
),
3741 gimple_cond_rhs (stmt
), stmt
);
3744 if (gimple_vdef (stmt
))
3745 maybe_invalidate (stmt
);
3749 /* Recursively call maybe_invalidate on stmts that might be executed
3750 in between dombb and current bb and that contain a vdef. Stop when
3751 *count stmts are inspected, or if the whole strinfo vector has
3752 been invalidated. */
3755 do_invalidate (basic_block dombb
, gimple
*phi
, bitmap visited
, int *count
)
3757 unsigned int i
, n
= gimple_phi_num_args (phi
);
3759 for (i
= 0; i
< n
; i
++)
3761 tree vuse
= gimple_phi_arg_def (phi
, i
);
3762 gimple
*stmt
= SSA_NAME_DEF_STMT (vuse
);
3763 basic_block bb
= gimple_bb (stmt
);
3766 || !bitmap_set_bit (visited
, bb
->index
)
3767 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3771 if (gimple_code (stmt
) == GIMPLE_PHI
)
3773 do_invalidate (dombb
, stmt
, visited
, count
);
3780 if (!maybe_invalidate (stmt
))
3785 vuse
= gimple_vuse (stmt
);
3786 stmt
= SSA_NAME_DEF_STMT (vuse
);
3787 if (gimple_bb (stmt
) != bb
)
3789 bb
= gimple_bb (stmt
);
3792 || !bitmap_set_bit (visited
, bb
->index
)
3793 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3800 class strlen_dom_walker
: public dom_walker
3803 strlen_dom_walker (cdi_direction direction
)
3804 : dom_walker (direction
), m_cleanup_cfg (false)
3807 virtual edge
before_dom_children (basic_block
);
3808 virtual void after_dom_children (basic_block
);
3810 /* Flag that will trigger TODO_cleanup_cfg to be returned in strlen
3811 execute function. */
3815 /* Callback for walk_dominator_tree. Attempt to optimize various
3816 string ops by remembering string lengths pointed by pointer SSA_NAMEs. */
3819 strlen_dom_walker::before_dom_children (basic_block bb
)
3821 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
3824 stridx_to_strinfo
= NULL
;
3827 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) dombb
->aux
);
3828 if (stridx_to_strinfo
)
3830 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3833 gphi
*phi
= gsi
.phi ();
3834 if (virtual_operand_p (gimple_phi_result (phi
)))
3836 bitmap visited
= BITMAP_ALLOC (NULL
);
3837 int count_vdef
= 100;
3838 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
3839 BITMAP_FREE (visited
);
3840 if (count_vdef
== 0)
3842 /* If there were too many vdefs in between immediate
3843 dominator and current bb, invalidate everything.
3844 If stridx_to_strinfo has been unshared, we need
3845 to free it, otherwise just set it to NULL. */
3846 if (!strinfo_shared ())
3852 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
3856 (*stridx_to_strinfo
)[i
] = NULL
;
3860 stridx_to_strinfo
= NULL
;
3868 /* If all PHI arguments have the same string index, the PHI result
3870 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3873 gphi
*phi
= gsi
.phi ();
3874 tree result
= gimple_phi_result (phi
);
3875 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
3877 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
3880 unsigned int i
, n
= gimple_phi_num_args (phi
);
3881 for (i
= 1; i
< n
; i
++)
3882 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
3885 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
3890 bool cleanup_eh
= false;
3892 /* Attempt to optimize individual statements. */
3893 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
3894 if (strlen_check_and_optimize_stmt (&gsi
, &cleanup_eh
))
3897 if (cleanup_eh
&& gimple_purge_dead_eh_edges (bb
))
3898 m_cleanup_cfg
= true;
3900 bb
->aux
= stridx_to_strinfo
;
3901 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
3902 (*stridx_to_strinfo
)[0] = (strinfo
*) bb
;
3906 /* Callback for walk_dominator_tree. Free strinfo vector if it is
3907 owned by the current bb, clear bb->aux. */
3910 strlen_dom_walker::after_dom_children (basic_block bb
)
3914 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) bb
->aux
);
3915 if (vec_safe_length (stridx_to_strinfo
)
3916 && (*stridx_to_strinfo
)[0] == (strinfo
*) bb
)
3921 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
3923 vec_free (stridx_to_strinfo
);
3929 /* Main entry point. */
3933 const pass_data pass_data_strlen
=
3935 GIMPLE_PASS
, /* type */
3936 "strlen", /* name */
3937 OPTGROUP_NONE
, /* optinfo_flags */
3938 TV_TREE_STRLEN
, /* tv_id */
3939 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3940 0, /* properties_provided */
3941 0, /* properties_destroyed */
3942 0, /* todo_flags_start */
3943 0, /* todo_flags_finish */
3946 class pass_strlen
: public gimple_opt_pass
3949 pass_strlen (gcc::context
*ctxt
)
3950 : gimple_opt_pass (pass_data_strlen
, ctxt
)
3953 /* opt_pass methods: */
3954 virtual bool gate (function
*) { return flag_optimize_strlen
!= 0; }
3955 virtual unsigned int execute (function
*);
3957 }; // class pass_strlen
3960 pass_strlen::execute (function
*fun
)
3962 gcc_assert (!strlen_to_stridx
);
3963 if (warn_stringop_overflow
|| warn_stringop_truncation
)
3964 strlen_to_stridx
= new hash_map
<tree
, stridx_strlenloc
> ();
3966 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
3969 calculate_dominance_info (CDI_DOMINATORS
);
3971 /* String length optimization is implemented as a walk of the dominator
3972 tree and a forward walk of statements within each block. */
3973 strlen_dom_walker
walker (CDI_DOMINATORS
);
3974 walker
.walk (fun
->cfg
->x_entry_block_ptr
);
3976 ssa_ver_to_stridx
.release ();
3977 strinfo_pool
.release ();
3978 if (decl_to_stridxlist_htab
)
3980 obstack_free (&stridx_obstack
, NULL
);
3981 delete decl_to_stridxlist_htab
;
3982 decl_to_stridxlist_htab
= NULL
;
3984 laststmt
.stmt
= NULL
;
3985 laststmt
.len
= NULL_TREE
;
3986 laststmt
.stridx
= 0;
3988 if (strlen_to_stridx
)
3990 strlen_to_stridx
->empty ();
3991 delete strlen_to_stridx
;
3992 strlen_to_stridx
= NULL
;
3995 return walker
.m_cleanup_cfg
? TODO_cleanup_cfg
: 0;
4001 make_pass_strlen (gcc::context
*ctxt
)
4003 return new pass_strlen (ctxt
);