1 /* String length optimization
2 Copyright (C) 2011-2017 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"
44 #include "tree-ssa-alias.h"
45 #include "tree-ssa-propagate.h"
48 #include "tree-hash-traits.h"
51 #include "diagnostic-core.h"
52 #include "diagnostic.h"
57 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
58 is an index into strinfo vector, negative value stands for
59 string length of a string literal (~strlen). */
60 static vec
<int> ssa_ver_to_stridx
;
62 /* Number of currently active string indexes plus one. */
63 static int max_stridx
;
65 /* String information record. */
68 /* Number of leading characters that are known to be nonzero. This is
69 also the length of the string if FULL_STRING_P.
71 The values in a list of related string pointers must be consistent;
72 that is, if strinfo B comes X bytes after strinfo A, it must be
73 the case that A->nonzero_chars == X + B->nonzero_chars. */
75 /* Any of the corresponding pointers for querying alias oracle. */
77 /* This is used for two things:
79 - To record the statement that should be used for delayed length
80 computations. We maintain the invariant that all related strinfos
81 have delayed lengths or none do.
83 - To record the malloc or calloc call that produced this result. */
85 /* Pointer to '\0' if known, if NULL, it can be computed as
88 /* Reference count. Any changes to strinfo entry possibly shared
89 with dominating basic blocks need unshare_strinfo first, except
90 for dont_invalidate which affects only the immediately next
93 /* Copy of index. get_strinfo (si->idx) should return si; */
95 /* These 3 fields are for chaining related string pointers together.
97 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
98 strcpy (c, d); e = c + dl;
99 strinfo(a) -> strinfo(c) -> strinfo(e)
100 All have ->first field equal to strinfo(a)->idx and are doubly
101 chained through prev/next fields. The later strinfos are required
102 to point into the same string with zero or more bytes after
103 the previous pointer and all bytes in between the two pointers
104 must be non-zero. Functions like strcpy or memcpy are supposed
105 to adjust all previous strinfo lengths, but not following strinfo
106 lengths (those are uncertain, usually invalidated during
107 maybe_invalidate, except when the alias oracle knows better).
108 Functions like strcat on the other side adjust the whole
109 related strinfo chain.
110 They are updated lazily, so to use the chain the same first fields
111 and si->prev->next == si->idx needs to be verified. */
115 /* A flag whether the string is known to be written in the current
118 /* A flag for the next maybe_invalidate that this strinfo shouldn't
119 be invalidated. Always cleared by maybe_invalidate. */
120 bool dont_invalidate
;
121 /* True if the string is known to be nul-terminated after NONZERO_CHARS
122 characters. False is useful when detecting strings that are built
123 up via successive memcpys. */
127 /* Pool for allocating strinfo_struct entries. */
128 static object_allocator
<strinfo
> strinfo_pool ("strinfo pool");
130 /* Vector mapping positive string indexes to strinfo, for the
131 current basic block. The first pointer in the vector is special,
132 it is either NULL, meaning the vector isn't shared, or it is
133 a basic block pointer to the owner basic_block if shared.
134 If some other bb wants to modify the vector, the vector needs
135 to be unshared first, and only the owner bb is supposed to free it. */
136 static vec
<strinfo
*, va_heap
, vl_embed
> *stridx_to_strinfo
;
138 /* One OFFSET->IDX mapping. */
141 struct stridxlist
*next
;
142 HOST_WIDE_INT offset
;
146 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
147 struct decl_stridxlist_map
149 struct tree_map_base base
;
150 struct stridxlist list
;
153 /* Hash table for mapping decls to a chained list of offset -> idx
155 static hash_map
<tree_decl_hash
, stridxlist
> *decl_to_stridxlist_htab
;
157 /* Hash table mapping strlen calls to stridx instances describing
158 the calls' arguments. Non-null only when warn_stringop_truncation
160 typedef std::pair
<int, location_t
> stridx_strlenloc
;
161 static hash_map
<tree
, stridx_strlenloc
> *strlen_to_stridx
;
163 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
164 static struct obstack stridx_obstack
;
166 /* Last memcpy statement if it could be adjusted if the trailing
167 '\0' written is immediately overwritten, or
168 *x = '\0' store that could be removed if it is immediately overwritten. */
169 struct laststmt_struct
176 static int get_stridx_plus_constant (strinfo
*, unsigned HOST_WIDE_INT
, tree
);
177 static void handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*);
181 - 1 if SI is known to start with more than OFF nonzero characters.
183 - 0 if SI is known to start with OFF nonzero characters,
184 but is not known to start with more.
186 - -1 if SI might not start with OFF nonzero characters. */
189 compare_nonzero_chars (strinfo
*si
, unsigned HOST_WIDE_INT off
)
191 if (si
->nonzero_chars
192 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
193 return compare_tree_int (si
->nonzero_chars
, off
);
198 /* Return true if SI is known to be a zero-length string. */
201 zero_length_string_p (strinfo
*si
)
203 return si
->full_string_p
&& integer_zerop (si
->nonzero_chars
);
206 /* Return strinfo vector entry IDX. */
208 static inline strinfo
*
209 get_strinfo (int idx
)
211 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
213 return (*stridx_to_strinfo
)[idx
];
216 /* Get the next strinfo in the chain after SI, or null if none. */
218 static inline strinfo
*
219 get_next_strinfo (strinfo
*si
)
223 strinfo
*nextsi
= get_strinfo (si
->next
);
224 if (nextsi
== NULL
|| nextsi
->first
!= si
->first
|| nextsi
->prev
!= si
->idx
)
229 /* Helper function for get_stridx. Return the strinfo index of the address
230 of EXP, which is available in PTR if nonnull. If OFFSET_OUT, it is
231 OK to return the index for some X <= &EXP and store &EXP - X in
235 get_addr_stridx (tree exp
, tree ptr
, unsigned HOST_WIDE_INT
*offset_out
)
238 struct stridxlist
*list
, *last
= NULL
;
241 if (!decl_to_stridxlist_htab
)
244 base
= get_addr_base_and_unit_offset (exp
, &off
);
245 if (base
== NULL
|| !DECL_P (base
))
248 list
= decl_to_stridxlist_htab
->get (base
);
254 if (list
->offset
== off
)
260 if (list
->offset
> off
)
267 if ((offset_out
|| ptr
) && last
&& last
->idx
> 0)
269 unsigned HOST_WIDE_INT rel_off
270 = (unsigned HOST_WIDE_INT
) off
- last
->offset
;
271 strinfo
*si
= get_strinfo (last
->idx
);
272 if (si
&& compare_nonzero_chars (si
, rel_off
) >= 0)
276 *offset_out
= rel_off
;
280 return get_stridx_plus_constant (si
, rel_off
, ptr
);
286 /* Return string index for EXP. */
289 get_stridx (tree exp
)
293 if (TREE_CODE (exp
) == SSA_NAME
)
295 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)])
296 return ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)];
299 HOST_WIDE_INT off
= 0;
300 for (i
= 0; i
< 5; i
++)
302 gimple
*def_stmt
= SSA_NAME_DEF_STMT (e
);
303 if (!is_gimple_assign (def_stmt
)
304 || gimple_assign_rhs_code (def_stmt
) != POINTER_PLUS_EXPR
)
306 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
307 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
308 if (TREE_CODE (rhs1
) != SSA_NAME
309 || !tree_fits_shwi_p (rhs2
))
311 HOST_WIDE_INT this_off
= tree_to_shwi (rhs2
);
314 off
= (unsigned HOST_WIDE_INT
) off
+ this_off
;
317 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)])
320 = get_strinfo (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)]);
321 if (si
&& compare_nonzero_chars (si
, off
) >= 0)
322 return get_stridx_plus_constant (si
, off
, exp
);
329 if (TREE_CODE (exp
) == ADDR_EXPR
)
331 int idx
= get_addr_stridx (TREE_OPERAND (exp
, 0), exp
, NULL
);
336 s
= string_constant (exp
, &o
);
338 && (o
== NULL_TREE
|| tree_fits_shwi_p (o
))
339 && TREE_STRING_LENGTH (s
) > 0)
341 HOST_WIDE_INT offset
= o
? tree_to_shwi (o
) : 0;
342 const char *p
= TREE_STRING_POINTER (s
);
343 int max
= TREE_STRING_LENGTH (s
) - 1;
345 if (p
[max
] == '\0' && offset
>= 0 && offset
<= max
)
346 return ~(int) strlen (p
+ offset
);
351 /* Return true if strinfo vector is shared with the immediate dominator. */
354 strinfo_shared (void)
356 return vec_safe_length (stridx_to_strinfo
)
357 && (*stridx_to_strinfo
)[0] != NULL
;
360 /* Unshare strinfo vector that is shared with the immediate dominator. */
363 unshare_strinfo_vec (void)
368 gcc_assert (strinfo_shared ());
369 stridx_to_strinfo
= vec_safe_copy (stridx_to_strinfo
);
370 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
373 (*stridx_to_strinfo
)[0] = NULL
;
376 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
377 Return a pointer to the location where the string index can
378 be stored (if 0) or is stored, or NULL if this can't be tracked. */
381 addr_stridxptr (tree exp
)
385 tree base
= get_addr_base_and_unit_offset (exp
, &off
);
386 if (base
== NULL_TREE
|| !DECL_P (base
))
389 if (!decl_to_stridxlist_htab
)
391 decl_to_stridxlist_htab
392 = new hash_map
<tree_decl_hash
, stridxlist
> (64);
393 gcc_obstack_init (&stridx_obstack
);
397 stridxlist
*list
= &decl_to_stridxlist_htab
->get_or_insert (base
, &existed
);
401 stridxlist
*before
= NULL
;
402 for (i
= 0; i
< 32; i
++)
404 if (list
->offset
== off
)
406 if (list
->offset
> off
&& before
== NULL
)
408 if (list
->next
== NULL
)
417 before
= XOBNEW (&stridx_obstack
, struct stridxlist
);
424 list
->next
= XOBNEW (&stridx_obstack
, struct stridxlist
);
434 /* Create a new string index, or return 0 if reached limit. */
437 new_stridx (tree exp
)
440 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
442 if (TREE_CODE (exp
) == SSA_NAME
)
444 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
447 ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)] = idx
;
450 if (TREE_CODE (exp
) == ADDR_EXPR
)
452 int *pidx
= addr_stridxptr (TREE_OPERAND (exp
, 0));
455 gcc_assert (*pidx
== 0);
456 *pidx
= max_stridx
++;
463 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
466 new_addr_stridx (tree exp
)
469 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
471 pidx
= addr_stridxptr (exp
);
474 gcc_assert (*pidx
== 0);
475 *pidx
= max_stridx
++;
481 /* Create a new strinfo. */
484 new_strinfo (tree ptr
, int idx
, tree nonzero_chars
, bool full_string_p
)
486 strinfo
*si
= strinfo_pool
.allocate ();
487 si
->nonzero_chars
= nonzero_chars
;
490 si
->endptr
= NULL_TREE
;
496 si
->writable
= false;
497 si
->dont_invalidate
= false;
498 si
->full_string_p
= full_string_p
;
502 /* Decrease strinfo refcount and free it if not referenced anymore. */
505 free_strinfo (strinfo
*si
)
507 if (si
&& --si
->refcount
== 0)
508 strinfo_pool
.remove (si
);
511 /* Set strinfo in the vector entry IDX to SI. */
514 set_strinfo (int idx
, strinfo
*si
)
516 if (vec_safe_length (stridx_to_strinfo
) && (*stridx_to_strinfo
)[0])
517 unshare_strinfo_vec ();
518 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
519 vec_safe_grow_cleared (stridx_to_strinfo
, idx
+ 1);
520 (*stridx_to_strinfo
)[idx
] = si
;
523 /* Return the first strinfo in the related strinfo chain
524 if all strinfos in between belong to the chain, otherwise NULL. */
527 verify_related_strinfos (strinfo
*origsi
)
529 strinfo
*si
= origsi
, *psi
;
531 if (origsi
->first
== 0)
533 for (; si
->prev
; si
= psi
)
535 if (si
->first
!= origsi
->first
)
537 psi
= get_strinfo (si
->prev
);
540 if (psi
->next
!= si
->idx
)
543 if (si
->idx
!= si
->first
)
548 /* Set SI's endptr to ENDPTR and compute its length based on SI->ptr.
549 Use LOC for folding. */
552 set_endptr_and_length (location_t loc
, strinfo
*si
, tree endptr
)
556 tree start_as_size
= fold_convert_loc (loc
, size_type_node
, si
->ptr
);
557 tree end_as_size
= fold_convert_loc (loc
, size_type_node
, endptr
);
558 si
->nonzero_chars
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
559 end_as_size
, start_as_size
);
560 si
->full_string_p
= true;
563 /* Return string length, or NULL if it can't be computed. */
566 get_string_length (strinfo
*si
)
568 if (si
->nonzero_chars
)
569 return si
->full_string_p
? si
->nonzero_chars
: NULL
;
573 gimple
*stmt
= si
->stmt
, *lenstmt
;
574 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
575 tree callee
, lhs
, fn
, tem
;
577 gimple_stmt_iterator gsi
;
579 gcc_assert (is_gimple_call (stmt
));
580 callee
= gimple_call_fndecl (stmt
);
581 gcc_assert (callee
&& DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
);
582 lhs
= gimple_call_lhs (stmt
);
583 /* unshare_strinfo is intentionally not called here. The (delayed)
584 transformation of strcpy or strcat into stpcpy is done at the place
585 of the former strcpy/strcat call and so can affect all the strinfos
586 with the same stmt. If they were unshared before and transformation
587 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
588 just compute the right length. */
589 switch (DECL_FUNCTION_CODE (callee
))
591 case BUILT_IN_STRCAT
:
592 case BUILT_IN_STRCAT_CHK
:
593 case BUILT_IN_STRCAT_CHKP
:
594 case BUILT_IN_STRCAT_CHK_CHKP
:
595 gsi
= gsi_for_stmt (stmt
);
596 fn
= builtin_decl_implicit (BUILT_IN_STRLEN
);
597 gcc_assert (lhs
== NULL_TREE
);
598 tem
= unshare_expr (gimple_call_arg (stmt
, 0));
601 lenstmt
= gimple_build_call (chkp_maybe_create_clone (fn
)->decl
,
602 2, tem
, gimple_call_arg (stmt
, 1));
603 gimple_call_set_with_bounds (lenstmt
, true);
606 lenstmt
= gimple_build_call (fn
, 1, tem
);
607 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), lenstmt
);
608 gimple_call_set_lhs (lenstmt
, lhs
);
609 gimple_set_vuse (lenstmt
, gimple_vuse (stmt
));
610 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
611 tem
= gimple_call_arg (stmt
, 0);
612 if (!ptrofftype_p (TREE_TYPE (lhs
)))
614 lhs
= convert_to_ptrofftype (lhs
);
615 lhs
= force_gimple_operand_gsi (&gsi
, lhs
, true, NULL_TREE
,
616 true, GSI_SAME_STMT
);
618 lenstmt
= gimple_build_assign
619 (make_ssa_name (TREE_TYPE (gimple_call_arg (stmt
, 0))),
620 POINTER_PLUS_EXPR
,tem
, lhs
);
621 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
622 gimple_call_set_arg (stmt
, 0, gimple_assign_lhs (lenstmt
));
625 case BUILT_IN_STRCPY
:
626 case BUILT_IN_STRCPY_CHK
:
627 case BUILT_IN_STRCPY_CHKP
:
628 case BUILT_IN_STRCPY_CHK_CHKP
:
629 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY
));
630 if (gimple_call_num_args (stmt
) == (with_bounds
? 4 : 2))
631 fn
= builtin_decl_implicit (BUILT_IN_STPCPY
);
633 fn
= builtin_decl_explicit (BUILT_IN_STPCPY_CHK
);
635 fn
= chkp_maybe_create_clone (fn
)->decl
;
636 gcc_assert (lhs
== NULL_TREE
);
637 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
639 fprintf (dump_file
, "Optimizing: ");
640 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
642 gimple_call_set_fndecl (stmt
, fn
);
643 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), stmt
);
644 gimple_call_set_lhs (stmt
, lhs
);
646 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
648 fprintf (dump_file
, "into: ");
649 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
652 case BUILT_IN_STPCPY
:
653 case BUILT_IN_STPCPY_CHK
:
654 case BUILT_IN_STPCPY_CHKP
:
655 case BUILT_IN_STPCPY_CHK_CHKP
:
656 gcc_assert (lhs
!= NULL_TREE
);
657 loc
= gimple_location (stmt
);
658 set_endptr_and_length (loc
, si
, lhs
);
659 for (strinfo
*chainsi
= verify_related_strinfos (si
);
661 chainsi
= get_next_strinfo (chainsi
))
662 if (chainsi
->nonzero_chars
== NULL
)
663 set_endptr_and_length (loc
, chainsi
, lhs
);
665 case BUILT_IN_MALLOC
:
667 /* BUILT_IN_CALLOC always has si->nonzero_chars set. */
674 return si
->nonzero_chars
;
677 /* Invalidate string length information for strings whose length
678 might change due to stores in stmt. */
681 maybe_invalidate (gimple
*stmt
)
685 bool nonempty
= false;
687 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
690 if (!si
->dont_invalidate
)
693 /* Do not use si->nonzero_chars. */
694 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, NULL_TREE
);
695 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
697 set_strinfo (i
, NULL
);
702 si
->dont_invalidate
= false;
708 /* Unshare strinfo record SI, if it has refcount > 1 or
709 if stridx_to_strinfo vector is shared with some other
713 unshare_strinfo (strinfo
*si
)
717 if (si
->refcount
== 1 && !strinfo_shared ())
720 nsi
= new_strinfo (si
->ptr
, si
->idx
, si
->nonzero_chars
, si
->full_string_p
);
721 nsi
->stmt
= si
->stmt
;
722 nsi
->endptr
= si
->endptr
;
723 nsi
->first
= si
->first
;
724 nsi
->prev
= si
->prev
;
725 nsi
->next
= si
->next
;
726 nsi
->writable
= si
->writable
;
727 set_strinfo (si
->idx
, nsi
);
732 /* Attempt to create a new strinfo for BASESI + OFF, or find existing
733 strinfo if there is any. Return it's idx, or 0 if no strinfo has
737 get_stridx_plus_constant (strinfo
*basesi
, unsigned HOST_WIDE_INT off
,
740 if (TREE_CODE (ptr
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
743 if (compare_nonzero_chars (basesi
, off
) < 0
744 || !tree_fits_uhwi_p (basesi
->nonzero_chars
))
747 unsigned HOST_WIDE_INT nonzero_chars
748 = tree_to_uhwi (basesi
->nonzero_chars
) - off
;
749 strinfo
*si
= basesi
, *chainsi
;
750 if (si
->first
|| si
->prev
|| si
->next
)
751 si
= verify_related_strinfos (basesi
);
753 || si
->nonzero_chars
== NULL_TREE
754 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
757 if (TREE_CODE (ptr
) == SSA_NAME
758 && ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
759 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
761 gcc_checking_assert (compare_tree_int (si
->nonzero_chars
, off
) != -1);
762 for (chainsi
= si
; chainsi
->next
; chainsi
= si
)
764 si
= get_next_strinfo (chainsi
);
766 || si
->nonzero_chars
== NULL_TREE
767 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
769 int r
= compare_tree_int (si
->nonzero_chars
, nonzero_chars
);
774 if (TREE_CODE (ptr
) == SSA_NAME
)
775 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = si
->idx
;
778 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
779 if (pidx
!= NULL
&& *pidx
== 0)
788 int idx
= new_stridx (ptr
);
791 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, nonzero_chars
),
792 basesi
->full_string_p
);
793 set_strinfo (idx
, si
);
796 strinfo
*nextsi
= unshare_strinfo (get_strinfo (chainsi
->next
));
797 si
->next
= nextsi
->idx
;
800 chainsi
= unshare_strinfo (chainsi
);
801 if (chainsi
->first
== 0)
802 chainsi
->first
= chainsi
->idx
;
804 if (chainsi
->endptr
== NULL_TREE
&& zero_length_string_p (si
))
805 chainsi
->endptr
= ptr
;
806 si
->endptr
= chainsi
->endptr
;
807 si
->prev
= chainsi
->idx
;
808 si
->first
= chainsi
->first
;
809 si
->writable
= chainsi
->writable
;
813 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
814 to a zero-length string and if possible chain it to a related strinfo
815 chain whose part is or might be CHAINSI. */
818 zero_length_string (tree ptr
, strinfo
*chainsi
)
822 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
823 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
824 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
825 && ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] == 0);
827 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
831 si
= verify_related_strinfos (chainsi
);
836 /* We shouldn't mix delayed and non-delayed lengths. */
837 gcc_assert (si
->full_string_p
);
838 if (si
->endptr
== NULL_TREE
)
840 si
= unshare_strinfo (si
);
844 si
= get_next_strinfo (si
);
847 if (zero_length_string_p (chainsi
))
851 chainsi
= unshare_strinfo (chainsi
);
854 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = chainsi
->idx
;
860 /* We shouldn't mix delayed and non-delayed lengths. */
861 gcc_assert (chainsi
->full_string_p
);
862 if (chainsi
->first
|| chainsi
->prev
|| chainsi
->next
)
864 chainsi
= unshare_strinfo (chainsi
);
871 idx
= new_stridx (ptr
);
874 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, 0), true);
875 set_strinfo (idx
, si
);
879 chainsi
= unshare_strinfo (chainsi
);
880 if (chainsi
->first
== 0)
881 chainsi
->first
= chainsi
->idx
;
883 if (chainsi
->endptr
== NULL_TREE
)
884 chainsi
->endptr
= ptr
;
885 si
->prev
= chainsi
->idx
;
886 si
->first
= chainsi
->first
;
887 si
->writable
= chainsi
->writable
;
892 /* For strinfo ORIGSI whose length has been just updated, adjust other
893 related strinfos so that they match the new ORIGSI. This involves:
895 - adding ADJ to the nonzero_chars fields
896 - copying full_string_p from the new ORIGSI. */
899 adjust_related_strinfos (location_t loc
, strinfo
*origsi
, tree adj
)
901 strinfo
*si
= verify_related_strinfos (origsi
);
914 si
= unshare_strinfo (si
);
915 /* We shouldn't see delayed lengths here; the caller must have
916 calculated the old length in order to calculate the
918 gcc_assert (si
->nonzero_chars
);
919 tem
= fold_convert_loc (loc
, TREE_TYPE (si
->nonzero_chars
), adj
);
920 si
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
921 TREE_TYPE (si
->nonzero_chars
),
922 si
->nonzero_chars
, tem
);
923 si
->full_string_p
= origsi
->full_string_p
;
925 si
->endptr
= NULL_TREE
;
926 si
->dont_invalidate
= true;
928 nsi
= get_next_strinfo (si
);
935 /* Find if there are other SSA_NAME pointers equal to PTR
936 for which we don't track their string lengths yet. If so, use
940 find_equal_ptrs (tree ptr
, int idx
)
942 if (TREE_CODE (ptr
) != SSA_NAME
)
946 gimple
*stmt
= SSA_NAME_DEF_STMT (ptr
);
947 if (!is_gimple_assign (stmt
))
949 ptr
= gimple_assign_rhs1 (stmt
);
950 switch (gimple_assign_rhs_code (stmt
))
955 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)))
957 if (TREE_CODE (ptr
) == SSA_NAME
)
959 if (TREE_CODE (ptr
) != ADDR_EXPR
)
964 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
965 if (pidx
!= NULL
&& *pidx
== 0)
973 /* We might find an endptr created in this pass. Grow the
974 vector in that case. */
975 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
976 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
978 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] != 0)
980 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = idx
;
984 /* Return true if STMT is a call to a builtin function with the right
985 arguments and attributes that should be considered for optimization
989 valid_builtin_call (gimple
*stmt
)
991 if (!gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
994 tree callee
= gimple_call_fndecl (stmt
);
995 switch (DECL_FUNCTION_CODE (callee
))
997 case BUILT_IN_MEMCMP
:
998 case BUILT_IN_MEMCMP_EQ
:
999 case BUILT_IN_STRCHR
:
1000 case BUILT_IN_STRCHR_CHKP
:
1001 case BUILT_IN_STRLEN
:
1002 case BUILT_IN_STRLEN_CHKP
:
1003 /* The above functions should be pure. Punt if they aren't. */
1004 if (gimple_vdef (stmt
) || gimple_vuse (stmt
) == NULL_TREE
)
1008 case BUILT_IN_CALLOC
:
1009 case BUILT_IN_MALLOC
:
1010 case BUILT_IN_MEMCPY
:
1011 case BUILT_IN_MEMCPY_CHK
:
1012 case BUILT_IN_MEMCPY_CHKP
:
1013 case BUILT_IN_MEMCPY_CHK_CHKP
:
1014 case BUILT_IN_MEMPCPY
:
1015 case BUILT_IN_MEMPCPY_CHK
:
1016 case BUILT_IN_MEMPCPY_CHKP
:
1017 case BUILT_IN_MEMPCPY_CHK_CHKP
:
1018 case BUILT_IN_MEMSET
:
1019 case BUILT_IN_STPCPY
:
1020 case BUILT_IN_STPCPY_CHK
:
1021 case BUILT_IN_STPCPY_CHKP
:
1022 case BUILT_IN_STPCPY_CHK_CHKP
:
1023 case BUILT_IN_STRCAT
:
1024 case BUILT_IN_STRCAT_CHK
:
1025 case BUILT_IN_STRCAT_CHKP
:
1026 case BUILT_IN_STRCAT_CHK_CHKP
:
1027 case BUILT_IN_STRCPY
:
1028 case BUILT_IN_STRCPY_CHK
:
1029 case BUILT_IN_STRCPY_CHKP
:
1030 case BUILT_IN_STRCPY_CHK_CHKP
:
1031 /* The above functions should be neither const nor pure. Punt if they
1033 if (gimple_vdef (stmt
) == NULL_TREE
|| gimple_vuse (stmt
) == NULL_TREE
)
1044 /* If the last .MEM setter statement before STMT is
1045 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
1046 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
1047 just memcpy (x, y, strlen (y)). SI must be the zero length
1051 adjust_last_stmt (strinfo
*si
, gimple
*stmt
, bool is_strcat
)
1053 tree vuse
, callee
, len
;
1054 struct laststmt_struct last
= laststmt
;
1055 strinfo
*lastsi
, *firstsi
;
1056 unsigned len_arg_no
= 2;
1058 laststmt
.stmt
= NULL
;
1059 laststmt
.len
= NULL_TREE
;
1060 laststmt
.stridx
= 0;
1062 if (last
.stmt
== NULL
)
1065 vuse
= gimple_vuse (stmt
);
1066 if (vuse
== NULL_TREE
1067 || SSA_NAME_DEF_STMT (vuse
) != last
.stmt
1068 || !has_single_use (vuse
))
1071 gcc_assert (last
.stridx
> 0);
1072 lastsi
= get_strinfo (last
.stridx
);
1078 if (lastsi
->first
== 0 || lastsi
->first
!= si
->first
)
1081 firstsi
= verify_related_strinfos (si
);
1082 if (firstsi
== NULL
)
1084 while (firstsi
!= lastsi
)
1086 firstsi
= get_next_strinfo (firstsi
);
1087 if (firstsi
== NULL
)
1092 if (!is_strcat
&& !zero_length_string_p (si
))
1095 if (is_gimple_assign (last
.stmt
))
1097 gimple_stmt_iterator gsi
;
1099 if (!integer_zerop (gimple_assign_rhs1 (last
.stmt
)))
1101 if (stmt_could_throw_p (last
.stmt
))
1103 gsi
= gsi_for_stmt (last
.stmt
);
1104 unlink_stmt_vdef (last
.stmt
);
1105 release_defs (last
.stmt
);
1106 gsi_remove (&gsi
, true);
1110 if (!valid_builtin_call (last
.stmt
))
1113 callee
= gimple_call_fndecl (last
.stmt
);
1114 switch (DECL_FUNCTION_CODE (callee
))
1116 case BUILT_IN_MEMCPY
:
1117 case BUILT_IN_MEMCPY_CHK
:
1119 case BUILT_IN_MEMCPY_CHKP
:
1120 case BUILT_IN_MEMCPY_CHK_CHKP
:
1127 len
= gimple_call_arg (last
.stmt
, len_arg_no
);
1128 if (tree_fits_uhwi_p (len
))
1130 if (!tree_fits_uhwi_p (last
.len
)
1131 || integer_zerop (len
)
1132 || tree_to_uhwi (len
) != tree_to_uhwi (last
.len
) + 1)
1134 /* Don't adjust the length if it is divisible by 4, it is more efficient
1135 to store the extra '\0' in that case. */
1136 if ((tree_to_uhwi (len
) & 3) == 0)
1139 else if (TREE_CODE (len
) == SSA_NAME
)
1141 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1142 if (!is_gimple_assign (def_stmt
)
1143 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1144 || gimple_assign_rhs1 (def_stmt
) != last
.len
1145 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1151 gimple_call_set_arg (last
.stmt
, len_arg_no
, last
.len
);
1152 update_stmt (last
.stmt
);
1155 /* For an LHS that is an SSA_NAME and for strlen() argument SRC, set
1156 LHS range info to [0, N] if SRC refers to a character array A[N]
1157 with unknown length bounded by N. */
1160 maybe_set_strlen_range (tree lhs
, tree src
)
1162 if (TREE_CODE (lhs
) != SSA_NAME
)
1165 if (TREE_CODE (src
) == SSA_NAME
)
1167 gimple
*def
= SSA_NAME_DEF_STMT (src
);
1168 if (is_gimple_assign (def
)
1169 && gimple_assign_rhs_code (def
) == ADDR_EXPR
)
1170 src
= gimple_assign_rhs1 (def
);
1173 if (TREE_CODE (src
) != ADDR_EXPR
)
1176 /* The last array member of a struct can be bigger than its size
1177 suggests if it's treated as a poor-man's flexible array member. */
1178 src
= TREE_OPERAND (src
, 0);
1179 if (TREE_CODE (TREE_TYPE (src
)) != ARRAY_TYPE
1180 || array_at_struct_end_p (src
))
1183 tree type
= TREE_TYPE (src
);
1184 if (tree dom
= TYPE_DOMAIN (type
))
1185 if (tree maxval
= TYPE_MAX_VALUE (dom
))
1187 wide_int max
= wi::to_wide (maxval
);
1188 wide_int min
= wi::zero (max
.get_precision ());
1189 set_range_info (lhs
, VR_RANGE
, min
, max
);
1193 /* Handle a strlen call. If strlen of the argument is known, replace
1194 the strlen call with the known value, otherwise remember that strlen
1195 of the argument is stored in the lhs SSA_NAME. */
1198 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
1202 gimple
*stmt
= gsi_stmt (*gsi
);
1203 tree lhs
= gimple_call_lhs (stmt
);
1205 if (lhs
== NULL_TREE
)
1208 src
= gimple_call_arg (stmt
, 0);
1209 idx
= get_stridx (src
);
1216 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
1220 si
= get_strinfo (idx
);
1222 rhs
= get_string_length (si
);
1224 if (rhs
!= NULL_TREE
)
1226 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1228 fprintf (dump_file
, "Optimizing: ");
1229 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1231 rhs
= unshare_expr (rhs
);
1232 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
1233 rhs
= fold_convert_loc (gimple_location (stmt
),
1234 TREE_TYPE (lhs
), rhs
);
1235 if (!update_call_from_tree (gsi
, rhs
))
1236 gimplify_and_update_call_from_tree (gsi
, rhs
);
1237 stmt
= gsi_stmt (*gsi
);
1239 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1241 fprintf (dump_file
, "into: ");
1242 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1245 && TREE_CODE (si
->nonzero_chars
) != SSA_NAME
1246 && TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
1247 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1249 si
= unshare_strinfo (si
);
1250 si
->nonzero_chars
= lhs
;
1251 gcc_assert (si
->full_string_p
);
1254 if (strlen_to_stridx
)
1256 location_t loc
= gimple_location (stmt
);
1257 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1262 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1265 idx
= new_stridx (src
);
1268 strinfo
*si
= get_strinfo (idx
);
1271 if (!si
->full_string_p
&& !si
->stmt
)
1273 /* Until now we only had a lower bound on the string length.
1274 Install LHS as the actual length. */
1275 si
= unshare_strinfo (si
);
1276 tree old
= si
->nonzero_chars
;
1277 si
->nonzero_chars
= lhs
;
1278 si
->full_string_p
= true;
1279 if (TREE_CODE (old
) == INTEGER_CST
)
1281 location_t loc
= gimple_location (stmt
);
1282 old
= fold_convert_loc (loc
, TREE_TYPE (lhs
), old
);
1283 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1284 TREE_TYPE (lhs
), lhs
, old
);
1285 adjust_related_strinfos (loc
, si
, adj
);
1299 strinfo
*si
= new_strinfo (src
, idx
, lhs
, true);
1300 set_strinfo (idx
, si
);
1301 find_equal_ptrs (src
, idx
);
1303 /* For SRC that is an array of N elements, set LHS's range
1305 maybe_set_strlen_range (lhs
, src
);
1307 if (strlen_to_stridx
)
1309 location_t loc
= gimple_location (stmt
);
1310 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1315 /* Handle a strchr call. If strlen of the first argument is known, replace
1316 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
1317 that lhs of the call is endptr and strlen of the argument is endptr - x. */
1320 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
1324 gimple
*stmt
= gsi_stmt (*gsi
);
1325 tree lhs
= gimple_call_lhs (stmt
);
1326 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1328 if (lhs
== NULL_TREE
)
1331 if (!integer_zerop (gimple_call_arg (stmt
, with_bounds
? 2 : 1)))
1334 src
= gimple_call_arg (stmt
, 0);
1335 idx
= get_stridx (src
);
1342 rhs
= build_int_cst (size_type_node
, ~idx
);
1346 si
= get_strinfo (idx
);
1348 rhs
= get_string_length (si
);
1350 if (rhs
!= NULL_TREE
)
1352 location_t loc
= gimple_location (stmt
);
1354 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1356 fprintf (dump_file
, "Optimizing: ");
1357 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1359 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
1361 rhs
= unshare_expr (si
->endptr
);
1362 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1364 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1368 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1369 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1370 TREE_TYPE (src
), src
, rhs
);
1371 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1373 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1375 if (!update_call_from_tree (gsi
, rhs
))
1376 gimplify_and_update_call_from_tree (gsi
, rhs
);
1377 stmt
= gsi_stmt (*gsi
);
1379 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1381 fprintf (dump_file
, "into: ");
1382 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1385 && si
->endptr
== NULL_TREE
1386 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1388 si
= unshare_strinfo (si
);
1391 zero_length_string (lhs
, si
);
1395 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1397 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1400 idx
= new_stridx (src
);
1401 else if (get_strinfo (idx
) != NULL
)
1403 zero_length_string (lhs
, NULL
);
1408 location_t loc
= gimple_location (stmt
);
1409 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1410 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1411 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1412 size_type_node
, lhsu
, srcu
);
1413 strinfo
*si
= new_strinfo (src
, idx
, length
, true);
1415 set_strinfo (idx
, si
);
1416 find_equal_ptrs (src
, idx
);
1417 zero_length_string (lhs
, si
);
1421 zero_length_string (lhs
, NULL
);
1424 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1425 If strlen of the second argument is known, strlen of the first argument
1426 is the same after this call. Furthermore, attempt to convert it to
1430 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1433 tree src
, dst
, srclen
, len
, lhs
, type
, fn
, oldlen
;
1435 gimple
*stmt
= gsi_stmt (*gsi
);
1436 strinfo
*si
, *dsi
, *olddsi
, *zsi
;
1438 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1440 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1441 dst
= gimple_call_arg (stmt
, 0);
1442 lhs
= gimple_call_lhs (stmt
);
1443 idx
= get_stridx (src
);
1446 si
= get_strinfo (idx
);
1448 didx
= get_stridx (dst
);
1452 olddsi
= get_strinfo (didx
);
1457 adjust_last_stmt (olddsi
, stmt
, false);
1461 srclen
= get_string_length (si
);
1463 srclen
= build_int_cst (size_type_node
, ~idx
);
1465 loc
= gimple_location (stmt
);
1466 if (srclen
== NULL_TREE
)
1469 case BUILT_IN_STRCPY
:
1470 case BUILT_IN_STRCPY_CHK
:
1471 case BUILT_IN_STRCPY_CHKP
:
1472 case BUILT_IN_STRCPY_CHK_CHKP
:
1473 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1476 case BUILT_IN_STPCPY
:
1477 case BUILT_IN_STPCPY_CHK
:
1478 case BUILT_IN_STPCPY_CHKP
:
1479 case BUILT_IN_STPCPY_CHK_CHKP
:
1480 if (lhs
== NULL_TREE
)
1484 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1485 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1486 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1496 didx
= new_stridx (dst
);
1502 oldlen
= olddsi
->nonzero_chars
;
1503 dsi
= unshare_strinfo (olddsi
);
1504 dsi
->nonzero_chars
= srclen
;
1505 dsi
->full_string_p
= (srclen
!= NULL_TREE
);
1506 /* Break the chain, so adjust_related_strinfo on later pointers in
1507 the chain won't adjust this one anymore. */
1510 dsi
->endptr
= NULL_TREE
;
1514 dsi
= new_strinfo (dst
, didx
, srclen
, srclen
!= NULL_TREE
);
1515 set_strinfo (didx
, dsi
);
1516 find_equal_ptrs (dst
, didx
);
1518 dsi
->writable
= true;
1519 dsi
->dont_invalidate
= true;
1521 if (dsi
->nonzero_chars
== NULL_TREE
)
1525 /* If string length of src is unknown, use delayed length
1526 computation. If string lenth of dst will be needed, it
1527 can be computed by transforming this strcpy call into
1528 stpcpy and subtracting dst from the return value. */
1530 /* Look for earlier strings whose length could be determined if
1531 this strcpy is turned into an stpcpy. */
1533 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1535 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1537 /* When setting a stmt for delayed length computation
1538 prevent all strinfos through dsi from being
1540 chainsi
= unshare_strinfo (chainsi
);
1541 chainsi
->stmt
= stmt
;
1542 chainsi
->nonzero_chars
= NULL_TREE
;
1543 chainsi
->full_string_p
= false;
1544 chainsi
->endptr
= NULL_TREE
;
1545 chainsi
->dont_invalidate
= true;
1550 /* Try to detect overlap before returning. This catches cases
1551 like strcpy (d, d + n) where n is non-constant whose range
1552 is such that (n <= strlen (d) holds).
1554 OLDDSI->NONZERO_chars may have been reset by this point with
1555 oldlen holding it original value. */
1556 if (olddsi
&& oldlen
)
1558 /* Add 1 for the terminating NUL. */
1559 tree type
= TREE_TYPE (oldlen
);
1560 oldlen
= fold_build2 (PLUS_EXPR
, type
, oldlen
,
1561 build_int_cst (type
, 1));
1562 check_bounds_or_overlap (as_a
<gcall
*>(stmt
), olddsi
->ptr
, src
,
1571 tree adj
= NULL_TREE
;
1572 if (oldlen
== NULL_TREE
)
1574 else if (integer_zerop (oldlen
))
1576 else if (TREE_CODE (oldlen
) == INTEGER_CST
1577 || TREE_CODE (srclen
) == INTEGER_CST
)
1578 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1579 TREE_TYPE (srclen
), srclen
,
1580 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1582 if (adj
!= NULL_TREE
)
1583 adjust_related_strinfos (loc
, dsi
, adj
);
1587 /* strcpy src may not overlap dst, so src doesn't need to be
1588 invalidated either. */
1590 si
->dont_invalidate
= true;
1596 case BUILT_IN_STRCPY
:
1597 case BUILT_IN_STRCPY_CHKP
:
1598 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1600 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1602 case BUILT_IN_STRCPY_CHK
:
1603 case BUILT_IN_STRCPY_CHK_CHKP
:
1604 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1606 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1608 case BUILT_IN_STPCPY
:
1609 case BUILT_IN_STPCPY_CHKP
:
1610 /* This would need adjustment of the lhs (subtract one),
1611 or detection that the trailing '\0' doesn't need to be
1612 written, if it will be immediately overwritten.
1613 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1617 zsi
= zero_length_string (lhs
, dsi
);
1620 case BUILT_IN_STPCPY_CHK
:
1621 case BUILT_IN_STPCPY_CHK_CHKP
:
1622 /* This would need adjustment of the lhs (subtract one),
1623 or detection that the trailing '\0' doesn't need to be
1624 written, if it will be immediately overwritten.
1625 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1629 zsi
= zero_length_string (lhs
, dsi
);
1636 zsi
->dont_invalidate
= true;
1640 tree args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1641 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1644 type
= size_type_node
;
1646 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1647 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1649 /* Set the no-warning bit on the transformed statement? */
1650 bool set_no_warning
= false;
1652 if (const strinfo
*chksi
= olddsi
? olddsi
: dsi
)
1654 && !check_bounds_or_overlap (as_a
<gcall
*>(stmt
), chksi
->ptr
, si
->ptr
,
1657 gimple_set_no_warning (stmt
, true);
1658 set_no_warning
= true;
1661 if (fn
== NULL_TREE
)
1664 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1666 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1668 fprintf (dump_file
, "Optimizing: ");
1669 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1673 fn
= chkp_maybe_create_clone (fn
)->decl
;
1674 if (gimple_call_num_args (stmt
) == 4)
1675 success
= update_gimple_call (gsi
, fn
, 5, dst
,
1676 gimple_call_arg (stmt
, 1),
1678 gimple_call_arg (stmt
, 3),
1681 success
= update_gimple_call (gsi
, fn
, 6, dst
,
1682 gimple_call_arg (stmt
, 1),
1684 gimple_call_arg (stmt
, 3),
1686 gimple_call_arg (stmt
, 4));
1689 if (gimple_call_num_args (stmt
) == 2)
1690 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1692 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1693 gimple_call_arg (stmt
, 2));
1696 stmt
= gsi_stmt (*gsi
);
1697 gimple_call_set_with_bounds (stmt
, with_bounds
);
1699 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1701 fprintf (dump_file
, "into: ");
1702 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1704 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1705 laststmt
.stmt
= stmt
;
1706 laststmt
.len
= srclen
;
1707 laststmt
.stridx
= dsi
->idx
;
1709 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1710 fprintf (dump_file
, "not possible.\n");
1713 gimple_set_no_warning (stmt
, true);
1716 /* Check the size argument to the built-in forms of stpncpy and strncpy
1717 for out-of-bounds offsets or overlapping access, and to see if the
1718 size argument is derived from a call to strlen() on the source argument,
1719 and if so, issue an appropriate warning. */
1722 handle_builtin_strncat (built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1724 /* Same as stxncpy(). */
1725 handle_builtin_stxncpy (bcode
, gsi
);
1728 /* Return true if LEN depends on a call to strlen(SRC) in an interesting
1729 way. LEN can either be an integer expression, or a pointer (to char).
1730 When it is the latter (such as in recursive calls to self) is is
1731 assumed to be the argument in some call to strlen() whose relationship
1732 to SRC is being ascertained. */
1735 is_strlen_related_p (tree src
, tree len
)
1737 if (TREE_CODE (TREE_TYPE (len
)) == POINTER_TYPE
1738 && operand_equal_p (src
, len
, 0))
1741 if (TREE_CODE (len
) != SSA_NAME
)
1744 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1748 if (is_gimple_call (def_stmt
))
1750 tree func
= gimple_call_fndecl (def_stmt
);
1751 if (!valid_builtin_call (def_stmt
)
1752 || DECL_FUNCTION_CODE (func
) != BUILT_IN_STRLEN
)
1755 tree arg
= gimple_call_arg (def_stmt
, 0);
1756 return is_strlen_related_p (src
, arg
);
1759 if (!is_gimple_assign (def_stmt
))
1762 tree_code code
= gimple_assign_rhs_code (def_stmt
);
1763 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1764 tree rhstype
= TREE_TYPE (rhs1
);
1766 if ((TREE_CODE (rhstype
) == POINTER_TYPE
&& code
== POINTER_PLUS_EXPR
)
1767 || (INTEGRAL_TYPE_P (rhstype
)
1768 && (code
== BIT_AND_EXPR
1769 || code
== NOP_EXPR
)))
1771 /* Pointer plus (an integer) and integer cast or truncation are
1772 considered among the (potentially) related expressions to strlen.
1774 return is_strlen_related_p (src
, rhs1
);
1780 /* A helper of handle_builtin_stxncpy. Check to see if the specified
1781 bound is a) equal to the size of the destination DST and if so, b)
1782 if it's immediately followed by DST[CNT - 1] = '\0'. If a) holds
1783 and b) does not, warn. Otherwise, do nothing. Return true if
1784 diagnostic has been issued.
1786 The purpose is to diagnose calls to strncpy and stpncpy that do
1787 not nul-terminate the copy while allowing for the idiom where
1788 such a call is immediately followed by setting the last element
1791 strncpy (a, s, sizeof a);
1792 a[sizeof a - 1] = '\0';
1796 maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi
, tree src
, tree cnt
)
1798 gimple
*stmt
= gsi_stmt (gsi
);
1800 wide_int cntrange
[2];
1802 if (TREE_CODE (cnt
) == INTEGER_CST
)
1803 cntrange
[0] = cntrange
[1] = wi::to_wide (cnt
);
1804 else if (TREE_CODE (cnt
) == SSA_NAME
)
1806 enum value_range_type rng
= get_range_info (cnt
, cntrange
, cntrange
+ 1);
1807 if (rng
== VR_RANGE
)
1809 else if (rng
== VR_ANTI_RANGE
)
1811 wide_int maxobjsize
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
));
1813 if (wi::ltu_p (cntrange
[1], maxobjsize
))
1815 cntrange
[0] = cntrange
[1] + 1;
1816 cntrange
[1] = maxobjsize
;
1820 cntrange
[1] = cntrange
[0] - 1;
1821 cntrange
[0] = wi::zero (TYPE_PRECISION (TREE_TYPE (cnt
)));
1830 /* Negative value is the constant string length. If it's less than
1831 the lower bound there is no truncation. */
1832 int sidx
= get_stridx (src
);
1833 if (sidx
< 0 && wi::gtu_p (cntrange
[0], ~sidx
))
1836 tree dst
= gimple_call_arg (stmt
, 0);
1838 if (TREE_CODE (dstdecl
) == ADDR_EXPR
)
1839 dstdecl
= TREE_OPERAND (dstdecl
, 0);
1841 /* If the destination refers to a an array/pointer declared nonstring
1843 tree ref
= NULL_TREE
;
1844 if (get_attr_nonstring_decl (dstdecl
, &ref
))
1847 /* Look for dst[i] = '\0'; after the stxncpy() call and if found
1848 avoid the truncation warning. */
1850 gimple
*next_stmt
= gsi_stmt (gsi
);
1852 if (!gsi_end_p (gsi
) && is_gimple_assign (next_stmt
))
1854 tree lhs
= gimple_assign_lhs (next_stmt
);
1855 tree_code code
= TREE_CODE (lhs
);
1856 if (code
== ARRAY_REF
|| code
== MEM_REF
)
1857 lhs
= TREE_OPERAND (lhs
, 0);
1859 tree func
= gimple_call_fndecl (stmt
);
1860 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STPNCPY
)
1862 tree ret
= gimple_call_lhs (stmt
);
1863 if (ret
&& operand_equal_p (ret
, lhs
, 0))
1867 /* Determine the base address and offset of the reference,
1868 ignoring the innermost array index. */
1869 if (TREE_CODE (ref
) == ARRAY_REF
)
1870 ref
= TREE_OPERAND (ref
, 0);
1872 HOST_WIDE_INT dstoff
;
1873 tree dstbase
= get_addr_base_and_unit_offset (ref
, &dstoff
);
1875 HOST_WIDE_INT lhsoff
;
1876 tree lhsbase
= get_addr_base_and_unit_offset (lhs
, &lhsoff
);
1879 && operand_equal_p (dstbase
, lhsbase
, 0))
1883 int prec
= TYPE_PRECISION (TREE_TYPE (cnt
));
1884 wide_int lenrange
[2];
1885 if (strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
)
1887 lenrange
[0] = (sisrc
->nonzero_chars
1888 && TREE_CODE (sisrc
->nonzero_chars
) == INTEGER_CST
1889 ? wi::to_wide (sisrc
->nonzero_chars
)
1891 lenrange
[1] = lenrange
[0];
1894 lenrange
[0] = lenrange
[1] = wi::shwi (~sidx
, prec
);
1898 get_range_strlen (src
, range
);
1901 lenrange
[0] = wi::to_wide (range
[0], prec
);
1902 lenrange
[1] = wi::to_wide (range
[1], prec
);
1906 lenrange
[0] = wi::shwi (0, prec
);
1907 lenrange
[1] = wi::shwi (-1, prec
);
1911 location_t callloc
= gimple_location (stmt
);
1912 tree func
= gimple_call_fndecl (stmt
);
1914 if (lenrange
[0] != 0 || !wi::neg_p (lenrange
[1]))
1916 /* If the longest source string is shorter than the lower bound
1917 of the specified count the copy is definitely nul-terminated. */
1918 if (wi::ltu_p (lenrange
[1], cntrange
[0]))
1921 if (wi::neg_p (lenrange
[1]))
1923 /* The length of one of the strings is unknown but at least
1924 one has non-zero length and that length is stored in
1925 LENRANGE[1]. Swap the bounds to force a "may be truncated"
1927 lenrange
[1] = lenrange
[0];
1928 lenrange
[0] = wi::shwi (0, prec
);
1931 if (wi::geu_p (lenrange
[0], cntrange
[1]))
1933 /* The shortest string is longer than the upper bound of
1934 the count so the truncation is certain. */
1935 if (cntrange
[0] == cntrange
[1])
1936 return warning_at (callloc
, OPT_Wstringop_truncation
,
1938 ? G_("%qD output truncated copying %E byte "
1939 "from a string of length %wu")
1940 : G_("%qD output truncated copying %E bytes "
1941 "from a string of length %wu"),
1942 func
, cnt
, lenrange
[0].to_uhwi ());
1944 return warning_at (callloc
, OPT_Wstringop_truncation
,
1945 "%qD output truncated copying between %wu "
1946 "and %wu bytes from a string of length %wu",
1947 func
, cntrange
[0].to_uhwi (),
1948 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
1950 else if (wi::geu_p (lenrange
[1], cntrange
[1]))
1952 /* The longest string is longer than the upper bound of
1953 the count so the truncation is possible. */
1954 if (cntrange
[0] == cntrange
[1])
1955 return warning_at (callloc
, OPT_Wstringop_truncation
,
1957 ? G_("%qD output may be truncated copying %E "
1958 "byte from a string of length %wu")
1959 : G_("%qD output may be truncated copying %E "
1960 "bytes from a string of length %wu"),
1961 func
, cnt
, lenrange
[1].to_uhwi ());
1963 return warning_at (callloc
, OPT_Wstringop_truncation
,
1964 "%qD output may be truncated copying between %wu "
1965 "and %wu bytes from a string of length %wu",
1966 func
, cntrange
[0].to_uhwi (),
1967 cntrange
[1].to_uhwi (), lenrange
[1].to_uhwi ());
1970 if (cntrange
[0] != cntrange
[1]
1971 && wi::leu_p (cntrange
[0], lenrange
[0])
1972 && wi::leu_p (cntrange
[1], lenrange
[0] + 1))
1974 /* If the source (including the terminating nul) is longer than
1975 the lower bound of the specified count but shorter than the
1976 upper bound the copy may (but need not) be truncated. */
1977 return warning_at (callloc
, OPT_Wstringop_truncation
,
1978 "%qD output may be truncated copying between %wu "
1979 "and %wu bytes from a string of length %wu",
1980 func
, cntrange
[0].to_uhwi (),
1981 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
1985 if (tree dstsize
= compute_objsize (dst
, 1))
1987 /* The source length is uknown. Try to determine the destination
1988 size and see if it matches the specified bound. If not, bail.
1989 Otherwise go on to see if it should be diagnosed for possible
1994 if (wi::to_wide (dstsize
) != cntrange
[1])
1997 if (cntrange
[0] == cntrange
[1])
1998 return warning_at (callloc
, OPT_Wstringop_truncation
,
1999 "%qD specified bound %E equals destination size",
2006 /* Check the arguments to the built-in forms of stpncpy and strncpy for
2007 out-of-bounds offsets or overlapping access, and to see if the size
2008 is derived from calling strlen() on the source argument, and if so,
2009 issue the appropriate warning. */
2012 handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*gsi
)
2014 if (!strlen_to_stridx
)
2017 gimple
*stmt
= gsi_stmt (*gsi
);
2019 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
2021 tree dst
= gimple_call_arg (stmt
, with_bounds
? 1 : 0);
2022 tree src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
2023 tree len
= gimple_call_arg (stmt
, with_bounds
? 3 : 2);
2024 tree dstsize
= NULL_TREE
, srcsize
= NULL_TREE
;
2026 int didx
= get_stridx (dst
);
2027 if (strinfo
*sidst
= didx
> 0 ? get_strinfo (didx
) : NULL
)
2029 /* Compute the size of the destination string including the NUL. */
2030 if (sidst
->nonzero_chars
)
2032 tree type
= TREE_TYPE (sidst
->nonzero_chars
);
2033 dstsize
= fold_build2 (PLUS_EXPR
, type
, sidst
->nonzero_chars
,
2034 build_int_cst (type
, 1));
2039 int sidx
= get_stridx (src
);
2040 strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
;
2043 /* strncat() and strncpy() can modify the source string by writing
2044 over the terminating nul so SISRC->DONT_INVALIDATE must be left
2047 /* Compute the size of the source string including the NUL. */
2048 if (sisrc
->nonzero_chars
)
2050 tree type
= TREE_TYPE (sisrc
->nonzero_chars
);
2051 srcsize
= fold_build2 (PLUS_EXPR
, type
, sisrc
->nonzero_chars
,
2052 build_int_cst (type
, 1));
2058 srcsize
= NULL_TREE
;
2060 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, src
,
2063 gimple_set_no_warning (stmt
, true);
2067 /* If the length argument was computed from strlen(S) for some string
2068 S retrieve the strinfo index for the string (PSS->FIRST) alonng with
2069 the location of the strlen() call (PSS->SECOND). */
2070 stridx_strlenloc
*pss
= strlen_to_stridx
->get (len
);
2071 if (!pss
|| pss
->first
<= 0)
2073 if (maybe_diag_stxncpy_trunc (*gsi
, src
, len
))
2074 gimple_set_no_warning (stmt
, true);
2079 /* Retrieve the strinfo data for the string S that LEN was computed
2080 from as some function F of strlen (S) (i.e., LEN need not be equal
2082 strinfo
*silen
= get_strinfo (pss
->first
);
2084 location_t callloc
= gimple_location (stmt
);
2086 tree func
= gimple_call_fndecl (stmt
);
2088 bool warned
= false;
2090 /* When -Wstringop-truncation is set, try to determine truncation
2091 before diagnosing possible overflow. Truncation is implied by
2092 the LEN argument being equal to strlen(SRC), regardless of
2093 whether its value is known. Otherwise, issue the more generic
2094 -Wstringop-overflow which triggers for LEN arguments that in
2095 any meaningful way depend on strlen(SRC). */
2097 && is_strlen_related_p (src
, len
)
2098 && warning_at (callloc
, OPT_Wstringop_truncation
,
2099 "%qD output truncated before terminating nul "
2100 "copying as many bytes from a string as its length",
2103 else if (silen
&& is_strlen_related_p (src
, silen
->ptr
))
2104 warned
= warning_at (callloc
, OPT_Wstringop_overflow_
,
2105 "%qD specified bound depends on the length "
2106 "of the source argument", func
);
2109 location_t strlenloc
= pss
->second
;
2110 if (strlenloc
!= UNKNOWN_LOCATION
&& strlenloc
!= callloc
)
2111 inform (strlenloc
, "length computed here");
2115 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
2116 If strlen of the second argument is known and length of the third argument
2117 is that plus one, strlen of the first argument is the same after this
2121 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2124 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
2125 gimple
*stmt
= gsi_stmt (*gsi
);
2126 strinfo
*si
, *dsi
, *olddsi
;
2127 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
2129 len
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
2130 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
2131 dst
= gimple_call_arg (stmt
, 0);
2132 idx
= get_stridx (src
);
2136 didx
= get_stridx (dst
);
2139 olddsi
= get_strinfo (didx
);
2144 && tree_fits_uhwi_p (len
)
2145 && !integer_zerop (len
))
2146 adjust_last_stmt (olddsi
, stmt
, false);
2153 /* Handle memcpy (x, y, l) where l's relationship with strlen (y)
2155 si
= get_strinfo (idx
);
2156 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
2158 if (TREE_CODE (len
) == INTEGER_CST
2159 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
2161 if (tree_int_cst_le (len
, si
->nonzero_chars
))
2163 /* Copying LEN nonzero characters, where LEN is constant. */
2165 full_string_p
= false;
2169 /* Copying the whole of the analyzed part of SI. */
2170 newlen
= si
->nonzero_chars
;
2171 full_string_p
= si
->full_string_p
;
2176 if (!si
->full_string_p
)
2178 if (TREE_CODE (len
) != SSA_NAME
)
2180 def_stmt
= SSA_NAME_DEF_STMT (len
);
2181 if (!is_gimple_assign (def_stmt
)
2182 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
2183 || gimple_assign_rhs1 (def_stmt
) != si
->nonzero_chars
2184 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
2186 /* Copying variable-length string SI (and no more). */
2187 newlen
= si
->nonzero_chars
;
2188 full_string_p
= true;
2194 /* Handle memcpy (x, "abcd", 5) or
2195 memcpy (x, "abc\0uvw", 7). */
2196 if (!tree_fits_uhwi_p (len
))
2199 unsigned HOST_WIDE_INT clen
= tree_to_uhwi (len
);
2200 unsigned HOST_WIDE_INT nonzero_chars
= ~idx
;
2201 newlen
= build_int_cst (size_type_node
, MIN (nonzero_chars
, clen
));
2202 full_string_p
= clen
> nonzero_chars
;
2205 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
2206 adjust_last_stmt (olddsi
, stmt
, false);
2210 didx
= new_stridx (dst
);
2217 dsi
= unshare_strinfo (olddsi
);
2218 oldlen
= olddsi
->nonzero_chars
;
2219 dsi
->nonzero_chars
= newlen
;
2220 dsi
->full_string_p
= full_string_p
;
2221 /* Break the chain, so adjust_related_strinfo on later pointers in
2222 the chain won't adjust this one anymore. */
2225 dsi
->endptr
= NULL_TREE
;
2229 dsi
= new_strinfo (dst
, didx
, newlen
, full_string_p
);
2230 set_strinfo (didx
, dsi
);
2231 find_equal_ptrs (dst
, didx
);
2233 dsi
->writable
= true;
2234 dsi
->dont_invalidate
= true;
2237 tree adj
= NULL_TREE
;
2238 location_t loc
= gimple_location (stmt
);
2239 if (oldlen
== NULL_TREE
)
2241 else if (integer_zerop (oldlen
))
2243 else if (TREE_CODE (oldlen
) == INTEGER_CST
2244 || TREE_CODE (newlen
) == INTEGER_CST
)
2245 adj
= fold_build2_loc (loc
, MINUS_EXPR
, TREE_TYPE (newlen
), newlen
,
2246 fold_convert_loc (loc
, TREE_TYPE (newlen
),
2248 if (adj
!= NULL_TREE
)
2249 adjust_related_strinfos (loc
, dsi
, adj
);
2253 /* memcpy src may not overlap dst, so src doesn't need to be
2254 invalidated either. */
2256 si
->dont_invalidate
= true;
2260 lhs
= gimple_call_lhs (stmt
);
2263 case BUILT_IN_MEMCPY
:
2264 case BUILT_IN_MEMCPY_CHK
:
2265 case BUILT_IN_MEMCPY_CHKP
:
2266 case BUILT_IN_MEMCPY_CHK_CHKP
:
2267 /* Allow adjust_last_stmt to decrease this memcpy's size. */
2268 laststmt
.stmt
= stmt
;
2269 laststmt
.len
= dsi
->nonzero_chars
;
2270 laststmt
.stridx
= dsi
->idx
;
2272 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
2274 case BUILT_IN_MEMPCPY
:
2275 case BUILT_IN_MEMPCPY_CHK
:
2276 case BUILT_IN_MEMPCPY_CHKP
:
2277 case BUILT_IN_MEMPCPY_CHK_CHKP
:
2285 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
2286 If strlen of the second argument is known, strlen of the first argument
2287 is increased by the length of the second argument. Furthermore, attempt
2288 to convert it to memcpy/strcpy if the length of the first argument
2292 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2295 tree srclen
, args
, type
, fn
, objsz
, endptr
;
2297 gimple
*stmt
= gsi_stmt (*gsi
);
2299 location_t loc
= gimple_location (stmt
);
2300 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
2302 tree src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
2303 tree dst
= gimple_call_arg (stmt
, 0);
2305 /* Bail if the source is the same as destination. It will be diagnosed
2307 if (operand_equal_p (src
, dst
, 0))
2310 tree lhs
= gimple_call_lhs (stmt
);
2312 didx
= get_stridx (dst
);
2318 dsi
= get_strinfo (didx
);
2322 idx
= get_stridx (src
);
2324 srclen
= build_int_cst (size_type_node
, ~idx
);
2327 si
= get_strinfo (idx
);
2329 srclen
= get_string_length (si
);
2332 /* Set the no-warning bit on the transformed statement? */
2333 bool set_no_warning
= false;
2335 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
2338 /* The concatenation always involves copying at least one byte
2339 (the terminating nul), even if the source string is empty.
2340 If the source is unknown assume it's one character long and
2341 used that as both sizes. */
2345 tree type
= TREE_TYPE (slen
);
2346 slen
= fold_build2 (PLUS_EXPR
, type
, slen
, build_int_cst (type
, 1));
2349 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2351 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, sptr
,
2354 gimple_set_no_warning (stmt
, true);
2355 set_no_warning
= true;
2359 /* strcat (p, q) can be transformed into
2360 tmp = p + strlen (p); endptr = stpcpy (tmp, q);
2361 with length endptr - p if we need to compute the length
2362 later on. Don't do this transformation if we don't need
2364 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
2368 didx
= new_stridx (dst
);
2374 dsi
= new_strinfo (dst
, didx
, NULL_TREE
, false);
2375 set_strinfo (didx
, dsi
);
2376 find_equal_ptrs (dst
, didx
);
2380 dsi
= unshare_strinfo (dsi
);
2381 dsi
->nonzero_chars
= NULL_TREE
;
2382 dsi
->full_string_p
= false;
2384 dsi
->endptr
= NULL_TREE
;
2386 dsi
->writable
= true;
2388 dsi
->dont_invalidate
= true;
2393 tree dstlen
= dsi
->nonzero_chars
;
2394 endptr
= dsi
->endptr
;
2396 dsi
= unshare_strinfo (dsi
);
2397 dsi
->endptr
= NULL_TREE
;
2399 dsi
->writable
= true;
2401 if (srclen
!= NULL_TREE
)
2403 dsi
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
2404 TREE_TYPE (dsi
->nonzero_chars
),
2405 dsi
->nonzero_chars
, srclen
);
2406 gcc_assert (dsi
->full_string_p
);
2407 adjust_related_strinfos (loc
, dsi
, srclen
);
2408 dsi
->dont_invalidate
= true;
2412 dsi
->nonzero_chars
= NULL
;
2413 dsi
->full_string_p
= false;
2414 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
2415 dsi
->dont_invalidate
= true;
2419 /* strcat src may not overlap dst, so src doesn't need to be
2420 invalidated either. */
2421 si
->dont_invalidate
= true;
2423 /* For now. Could remove the lhs from the call and add
2424 lhs = dst; afterwards. */
2432 case BUILT_IN_STRCAT
:
2433 case BUILT_IN_STRCAT_CHKP
:
2434 if (srclen
!= NULL_TREE
)
2435 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
2437 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
2439 case BUILT_IN_STRCAT_CHK
:
2440 case BUILT_IN_STRCAT_CHK_CHKP
:
2441 if (srclen
!= NULL_TREE
)
2442 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
2444 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
2445 objsz
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
2451 if (fn
== NULL_TREE
)
2456 tree type
= TREE_TYPE (dstlen
);
2458 /* Compute the size of the source sequence, including the nul. */
2459 tree srcsize
= srclen
? srclen
: size_zero_node
;
2460 srcsize
= fold_build2 (PLUS_EXPR
, type
, srcsize
, build_int_cst (type
, 1));
2462 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2464 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, sptr
,
2467 gimple_set_no_warning (stmt
, true);
2468 set_no_warning
= true;
2472 tree len
= NULL_TREE
;
2473 if (srclen
!= NULL_TREE
)
2475 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
2476 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
2478 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
2479 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
2480 build_int_cst (type
, 1));
2481 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
2485 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
2487 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
2488 TREE_TYPE (dst
), unshare_expr (dst
),
2489 fold_convert_loc (loc
, sizetype
,
2490 unshare_expr (dstlen
)));
2491 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
2493 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2495 fprintf (dump_file
, "Optimizing: ");
2496 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2500 fn
= chkp_maybe_create_clone (fn
)->decl
;
2501 if (srclen
!= NULL_TREE
)
2502 success
= update_gimple_call (gsi
, fn
, 5 + (objsz
!= NULL_TREE
),
2504 gimple_call_arg (stmt
, 1),
2506 gimple_call_arg (stmt
, 3),
2509 success
= update_gimple_call (gsi
, fn
, 4 + (objsz
!= NULL_TREE
),
2511 gimple_call_arg (stmt
, 1),
2513 gimple_call_arg (stmt
, 3),
2517 if (srclen
!= NULL_TREE
)
2518 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
2519 dst
, src
, len
, objsz
);
2521 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
2525 stmt
= gsi_stmt (*gsi
);
2526 gimple_call_set_with_bounds (stmt
, with_bounds
);
2528 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2530 fprintf (dump_file
, "into: ");
2531 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2533 /* If srclen == NULL, note that current string length can be
2534 computed by transforming this strcpy into stpcpy. */
2535 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
2537 adjust_last_stmt (dsi
, stmt
, true);
2538 if (srclen
!= NULL_TREE
)
2540 laststmt
.stmt
= stmt
;
2541 laststmt
.len
= srclen
;
2542 laststmt
.stridx
= dsi
->idx
;
2545 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2546 fprintf (dump_file
, "not possible.\n");
2549 gimple_set_no_warning (stmt
, true);
2552 /* Handle a call to malloc or calloc. */
2555 handle_builtin_malloc (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2557 gimple
*stmt
= gsi_stmt (*gsi
);
2558 tree lhs
= gimple_call_lhs (stmt
);
2559 if (lhs
== NULL_TREE
)
2562 gcc_assert (get_stridx (lhs
) == 0);
2563 int idx
= new_stridx (lhs
);
2564 tree length
= NULL_TREE
;
2565 if (bcode
== BUILT_IN_CALLOC
)
2566 length
= build_int_cst (size_type_node
, 0);
2567 strinfo
*si
= new_strinfo (lhs
, idx
, length
, length
!= NULL_TREE
);
2568 if (bcode
== BUILT_IN_CALLOC
)
2570 set_strinfo (idx
, si
);
2571 si
->writable
= true;
2573 si
->dont_invalidate
= true;
2576 /* Handle a call to memset.
2577 After a call to calloc, memset(,0,) is unnecessary.
2578 memset(malloc(n),0,n) is calloc(n,1). */
2581 handle_builtin_memset (gimple_stmt_iterator
*gsi
)
2583 gimple
*stmt2
= gsi_stmt (*gsi
);
2584 if (!integer_zerop (gimple_call_arg (stmt2
, 1)))
2586 tree ptr
= gimple_call_arg (stmt2
, 0);
2587 int idx1
= get_stridx (ptr
);
2590 strinfo
*si1
= get_strinfo (idx1
);
2593 gimple
*stmt1
= si1
->stmt
;
2594 if (!stmt1
|| !is_gimple_call (stmt1
))
2596 tree callee1
= gimple_call_fndecl (stmt1
);
2597 if (!valid_builtin_call (stmt1
))
2599 enum built_in_function code1
= DECL_FUNCTION_CODE (callee1
);
2600 tree size
= gimple_call_arg (stmt2
, 2);
2601 if (code1
== BUILT_IN_CALLOC
)
2602 /* Not touching stmt1 */ ;
2603 else if (code1
== BUILT_IN_MALLOC
2604 && operand_equal_p (gimple_call_arg (stmt1
, 0), size
, 0))
2606 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt1
);
2607 update_gimple_call (&gsi1
, builtin_decl_implicit (BUILT_IN_CALLOC
), 2,
2608 size
, build_one_cst (size_type_node
));
2609 si1
->nonzero_chars
= build_int_cst (size_type_node
, 0);
2610 si1
->full_string_p
= true;
2611 si1
->stmt
= gsi_stmt (gsi1
);
2615 tree lhs
= gimple_call_lhs (stmt2
);
2616 unlink_stmt_vdef (stmt2
);
2619 gimple
*assign
= gimple_build_assign (lhs
, ptr
);
2620 gsi_replace (gsi
, assign
, false);
2624 gsi_remove (gsi
, true);
2625 release_defs (stmt2
);
2631 /* Handle a call to memcmp. We try to handle small comparisons by
2632 converting them to load and compare, and replacing the call to memcmp
2633 with a __builtin_memcmp_eq call where possible. */
2636 handle_builtin_memcmp (gimple_stmt_iterator
*gsi
)
2638 gcall
*stmt2
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2639 tree res
= gimple_call_lhs (stmt2
);
2640 tree arg1
= gimple_call_arg (stmt2
, 0);
2641 tree arg2
= gimple_call_arg (stmt2
, 1);
2642 tree len
= gimple_call_arg (stmt2
, 2);
2643 unsigned HOST_WIDE_INT leni
;
2644 use_operand_p use_p
;
2645 imm_use_iterator iter
;
2650 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
2652 gimple
*ustmt
= USE_STMT (use_p
);
2654 if (is_gimple_debug (ustmt
))
2656 if (gimple_code (ustmt
) == GIMPLE_ASSIGN
)
2658 gassign
*asgn
= as_a
<gassign
*> (ustmt
);
2659 tree_code code
= gimple_assign_rhs_code (asgn
);
2660 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2661 || !integer_zerop (gimple_assign_rhs2 (asgn
)))
2664 else if (gimple_code (ustmt
) == GIMPLE_COND
)
2666 tree_code code
= gimple_cond_code (ustmt
);
2667 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2668 || !integer_zerop (gimple_cond_rhs (ustmt
)))
2675 if (tree_fits_uhwi_p (len
)
2676 && (leni
= tree_to_uhwi (len
)) <= GET_MODE_SIZE (word_mode
)
2677 && pow2p_hwi (leni
))
2679 leni
*= CHAR_TYPE_SIZE
;
2680 unsigned align1
= get_pointer_alignment (arg1
);
2681 unsigned align2
= get_pointer_alignment (arg2
);
2682 unsigned align
= MIN (align1
, align2
);
2683 scalar_int_mode mode
;
2684 if (int_mode_for_size (leni
, 1).exists (&mode
)
2685 && (align
>= leni
|| !targetm
.slow_unaligned_access (mode
, align
)))
2687 location_t loc
= gimple_location (stmt2
);
2689 type
= build_nonstandard_integer_type (leni
, 1);
2690 gcc_assert (GET_MODE_BITSIZE (TYPE_MODE (type
)) == leni
);
2691 tree ptrtype
= build_pointer_type_for_mode (char_type_node
,
2693 off
= build_int_cst (ptrtype
, 0);
2694 arg1
= build2_loc (loc
, MEM_REF
, type
, arg1
, off
);
2695 arg2
= build2_loc (loc
, MEM_REF
, type
, arg2
, off
);
2696 tree tem1
= fold_const_aggregate_ref (arg1
);
2699 tree tem2
= fold_const_aggregate_ref (arg2
);
2702 res
= fold_convert_loc (loc
, TREE_TYPE (res
),
2703 fold_build2_loc (loc
, NE_EXPR
,
2706 gimplify_and_update_call_from_tree (gsi
, res
);
2711 gimple_call_set_fndecl (stmt2
, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ
));
2715 /* Handle a POINTER_PLUS_EXPR statement.
2716 For p = "abcd" + 2; compute associated length, or if
2717 p = q + off is pointing to a '\0' character of a string, call
2718 zero_length_string on it. */
2721 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
2723 gimple
*stmt
= gsi_stmt (*gsi
);
2724 tree lhs
= gimple_assign_lhs (stmt
), off
;
2725 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
2733 tree off
= gimple_assign_rhs2 (stmt
);
2734 if (tree_fits_uhwi_p (off
)
2735 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
2736 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
2737 = ~(~idx
- (int) tree_to_uhwi (off
));
2741 si
= get_strinfo (idx
);
2742 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
2745 off
= gimple_assign_rhs2 (stmt
);
2747 if (si
->full_string_p
&& operand_equal_p (si
->nonzero_chars
, off
, 0))
2748 zsi
= zero_length_string (lhs
, si
);
2749 else if (TREE_CODE (off
) == SSA_NAME
)
2751 gimple
*def_stmt
= SSA_NAME_DEF_STMT (off
);
2752 if (gimple_assign_single_p (def_stmt
)
2753 && si
->full_string_p
2754 && operand_equal_p (si
->nonzero_chars
,
2755 gimple_assign_rhs1 (def_stmt
), 0))
2756 zsi
= zero_length_string (lhs
, si
);
2759 && si
->endptr
!= NULL_TREE
2760 && si
->endptr
!= lhs
2761 && TREE_CODE (si
->endptr
) == SSA_NAME
)
2763 enum tree_code rhs_code
2764 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
2765 ? SSA_NAME
: NOP_EXPR
;
2766 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
);
2767 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2772 /* Handle a single character store. */
2775 handle_char_store (gimple_stmt_iterator
*gsi
)
2779 gimple
*stmt
= gsi_stmt (*gsi
);
2780 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
2781 tree rhs
= gimple_assign_rhs1 (stmt
);
2782 unsigned HOST_WIDE_INT offset
= 0;
2784 if (TREE_CODE (lhs
) == MEM_REF
2785 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
2787 tree mem_offset
= TREE_OPERAND (lhs
, 1);
2788 if (tree_fits_uhwi_p (mem_offset
))
2790 /* Get the strinfo for the base, and use it if it starts with at
2791 least OFFSET nonzero characters. This is trivially true if
2793 offset
= tree_to_uhwi (mem_offset
);
2794 idx
= get_stridx (TREE_OPERAND (lhs
, 0));
2796 si
= get_strinfo (idx
);
2798 ssaname
= TREE_OPERAND (lhs
, 0);
2799 else if (si
== NULL
|| compare_nonzero_chars (si
, offset
) < 0)
2805 idx
= get_addr_stridx (lhs
, NULL_TREE
, &offset
);
2807 si
= get_strinfo (idx
);
2810 bool storing_zero_p
= initializer_zerop (rhs
);
2811 bool storing_nonzero_p
= (!storing_zero_p
2812 && TREE_CODE (rhs
) == INTEGER_CST
2813 && integer_nonzerop (rhs
));
2817 int cmp
= compare_nonzero_chars (si
, offset
);
2818 gcc_assert (offset
== 0 || cmp
>= 0);
2819 if (storing_zero_p
&& cmp
== 0 && si
->full_string_p
)
2821 /* When overwriting a '\0' with a '\0', the store can be removed
2822 if we know it has been stored in the current function. */
2823 if (!stmt_could_throw_p (stmt
) && si
->writable
)
2825 unlink_stmt_vdef (stmt
);
2826 release_defs (stmt
);
2827 gsi_remove (gsi
, true);
2832 si
->writable
= true;
2837 /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0',
2838 and if we aren't storing '\0', we know that the length of the
2839 string and any other zero terminated string in memory remains
2840 the same. In that case we move to the next gimple statement and
2841 return to signal the caller that it shouldn't invalidate anything.
2843 This is benefical for cases like:
2848 strcpy (p, "foobar");
2849 size_t len = strlen (p); // This can be optimized into 6
2850 size_t len2 = strlen (q); // This has to be computed
2852 size_t len3 = strlen (p); // This can be optimized into 6
2853 size_t len4 = strlen (q); // This can be optimized into len2
2854 bar (len, len2, len3, len4);
2857 else if (storing_nonzero_p
&& cmp
> 0)
2862 else if (storing_zero_p
|| storing_nonzero_p
|| (offset
!= 0 && cmp
> 0))
2864 /* When storing_nonzero_p, we know that the string now starts
2865 with OFFSET + 1 nonzero characters, but don't know whether
2866 there's a following nul terminator.
2868 When storing_zero_p, we know that the string is now OFFSET
2871 Otherwise, we're storing an unknown value at offset OFFSET,
2872 so need to clip the nonzero_chars to OFFSET. */
2873 location_t loc
= gimple_location (stmt
);
2874 tree oldlen
= si
->nonzero_chars
;
2875 if (cmp
== 0 && si
->full_string_p
)
2876 /* We're overwriting the nul terminator with a nonzero or
2877 unknown character. If the previous stmt was a memcpy,
2878 its length may be decreased. */
2879 adjust_last_stmt (si
, stmt
, false);
2880 si
= unshare_strinfo (si
);
2881 if (storing_nonzero_p
)
2882 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
+ 1);
2884 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
);
2885 si
->full_string_p
= storing_zero_p
;
2888 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
2889 si
->endptr
= ssaname
;
2894 si
->writable
= true;
2895 si
->dont_invalidate
= true;
2898 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
2899 si
->nonzero_chars
, oldlen
);
2900 adjust_related_strinfos (loc
, si
, adj
);
2906 else if (idx
== 0 && (storing_zero_p
|| storing_nonzero_p
))
2909 idx
= new_stridx (ssaname
);
2911 idx
= new_addr_stridx (lhs
);
2914 tree ptr
= (ssaname
? ssaname
: build_fold_addr_expr (lhs
));
2915 tree len
= storing_nonzero_p
? size_one_node
: size_zero_node
;
2916 si
= new_strinfo (ptr
, idx
, len
, storing_zero_p
);
2917 set_strinfo (idx
, si
);
2920 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
2921 si
->endptr
= ssaname
;
2922 si
->dont_invalidate
= true;
2923 si
->writable
= true;
2927 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == STRING_CST
2928 && ssaname
== NULL_TREE
2929 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
2931 size_t l
= strlen (TREE_STRING_POINTER (gimple_assign_rhs1 (stmt
)));
2932 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
2933 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> l
)
2935 int idx
= new_addr_stridx (lhs
);
2938 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
2939 build_int_cst (size_type_node
, l
), true);
2940 set_strinfo (idx
, si
);
2941 si
->dont_invalidate
= true;
2946 if (si
!= NULL
&& offset
== 0 && storing_zero_p
)
2948 /* Allow adjust_last_stmt to remove it if the stored '\0'
2949 is immediately overwritten. */
2950 laststmt
.stmt
= stmt
;
2951 laststmt
.len
= build_int_cst (size_type_node
, 1);
2952 laststmt
.stridx
= si
->idx
;
2957 /* Try to fold strstr (s, t) eq/ne s to strncmp (s, t, strlen (t)) eq/ne 0. */
2960 fold_strstr_to_strncmp (tree rhs1
, tree rhs2
, gimple
*stmt
)
2962 if (TREE_CODE (rhs1
) != SSA_NAME
2963 || TREE_CODE (rhs2
) != SSA_NAME
)
2966 gimple
*call_stmt
= NULL
;
2967 for (int pass
= 0; pass
< 2; pass
++)
2969 gimple
*g
= SSA_NAME_DEF_STMT (rhs1
);
2970 if (gimple_call_builtin_p (g
, BUILT_IN_STRSTR
)
2971 && has_single_use (rhs1
)
2972 && gimple_call_arg (g
, 0) == rhs2
)
2977 std::swap (rhs1
, rhs2
);
2982 tree arg0
= gimple_call_arg (call_stmt
, 0);
2986 tree arg1
= gimple_call_arg (call_stmt
, 1);
2987 tree arg1_len
= NULL_TREE
;
2988 int idx
= get_stridx (arg1
);
2993 arg1_len
= build_int_cst (size_type_node
, ~idx
);
2996 strinfo
*si
= get_strinfo (idx
);
2998 arg1_len
= get_string_length (si
);
3002 if (arg1_len
!= NULL_TREE
)
3004 gimple_stmt_iterator gsi
= gsi_for_stmt (call_stmt
);
3005 tree strncmp_decl
= builtin_decl_explicit (BUILT_IN_STRNCMP
);
3006 gcall
*strncmp_call
= gimple_build_call (strncmp_decl
, 3,
3007 arg0
, arg1
, arg1_len
);
3008 tree strncmp_lhs
= make_ssa_name (integer_type_node
);
3009 gimple_set_vuse (strncmp_call
, gimple_vuse (call_stmt
));
3010 gimple_call_set_lhs (strncmp_call
, strncmp_lhs
);
3011 gsi_remove (&gsi
, true);
3012 gsi_insert_before (&gsi
, strncmp_call
, GSI_SAME_STMT
);
3013 tree zero
= build_zero_cst (TREE_TYPE (strncmp_lhs
));
3015 if (is_gimple_assign (stmt
))
3017 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
3019 tree cond
= gimple_assign_rhs1 (stmt
);
3020 TREE_OPERAND (cond
, 0) = strncmp_lhs
;
3021 TREE_OPERAND (cond
, 1) = zero
;
3025 gimple_assign_set_rhs1 (stmt
, strncmp_lhs
);
3026 gimple_assign_set_rhs2 (stmt
, zero
);
3031 gcond
*cond
= as_a
<gcond
*> (stmt
);
3032 gimple_cond_set_lhs (cond
, strncmp_lhs
);
3033 gimple_cond_set_rhs (cond
, zero
);
3041 /* Attempt to check for validity of the performed access a single statement
3042 at *GSI using string length knowledge, and to optimize it. */
3045 strlen_check_and_optimize_stmt (gimple_stmt_iterator
*gsi
)
3047 gimple
*stmt
= gsi_stmt (*gsi
);
3049 if (is_gimple_call (stmt
))
3051 tree callee
= gimple_call_fndecl (stmt
);
3052 if (valid_builtin_call (stmt
))
3053 switch (DECL_FUNCTION_CODE (callee
))
3055 case BUILT_IN_STRLEN
:
3056 case BUILT_IN_STRLEN_CHKP
:
3057 handle_builtin_strlen (gsi
);
3059 case BUILT_IN_STRCHR
:
3060 case BUILT_IN_STRCHR_CHKP
:
3061 handle_builtin_strchr (gsi
);
3063 case BUILT_IN_STRCPY
:
3064 case BUILT_IN_STRCPY_CHK
:
3065 case BUILT_IN_STPCPY
:
3066 case BUILT_IN_STPCPY_CHK
:
3067 case BUILT_IN_STRCPY_CHKP
:
3068 case BUILT_IN_STRCPY_CHK_CHKP
:
3069 case BUILT_IN_STPCPY_CHKP
:
3070 case BUILT_IN_STPCPY_CHK_CHKP
:
3071 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3074 case BUILT_IN_STRNCAT
:
3075 case BUILT_IN_STRNCAT_CHK
:
3076 handle_builtin_strncat (DECL_FUNCTION_CODE (callee
), gsi
);
3079 case BUILT_IN_STPNCPY
:
3080 case BUILT_IN_STPNCPY_CHK
:
3081 case BUILT_IN_STRNCPY
:
3082 case BUILT_IN_STRNCPY_CHK
:
3083 handle_builtin_stxncpy (DECL_FUNCTION_CODE (callee
), gsi
);
3086 case BUILT_IN_MEMCPY
:
3087 case BUILT_IN_MEMCPY_CHK
:
3088 case BUILT_IN_MEMPCPY
:
3089 case BUILT_IN_MEMPCPY_CHK
:
3090 case BUILT_IN_MEMCPY_CHKP
:
3091 case BUILT_IN_MEMCPY_CHK_CHKP
:
3092 case BUILT_IN_MEMPCPY_CHKP
:
3093 case BUILT_IN_MEMPCPY_CHK_CHKP
:
3094 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3096 case BUILT_IN_STRCAT
:
3097 case BUILT_IN_STRCAT_CHK
:
3098 case BUILT_IN_STRCAT_CHKP
:
3099 case BUILT_IN_STRCAT_CHK_CHKP
:
3100 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
3102 case BUILT_IN_MALLOC
:
3103 case BUILT_IN_CALLOC
:
3104 handle_builtin_malloc (DECL_FUNCTION_CODE (callee
), gsi
);
3106 case BUILT_IN_MEMSET
:
3107 if (!handle_builtin_memset (gsi
))
3110 case BUILT_IN_MEMCMP
:
3111 if (!handle_builtin_memcmp (gsi
))
3118 else if (is_gimple_assign (stmt
) && !gimple_clobber_p (stmt
))
3120 tree lhs
= gimple_assign_lhs (stmt
);
3122 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
3124 if (gimple_assign_single_p (stmt
)
3125 || (gimple_assign_cast_p (stmt
)
3126 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
3128 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
3129 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
3131 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
3132 handle_pointer_plus (gsi
);
3134 else if (TREE_CODE (lhs
) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
3136 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3137 if (code
== COND_EXPR
)
3139 tree cond
= gimple_assign_rhs1 (stmt
);
3140 enum tree_code cond_code
= TREE_CODE (cond
);
3142 if (cond_code
== EQ_EXPR
|| cond_code
== NE_EXPR
)
3143 fold_strstr_to_strncmp (TREE_OPERAND (cond
, 0),
3144 TREE_OPERAND (cond
, 1), stmt
);
3146 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3147 fold_strstr_to_strncmp (gimple_assign_rhs1 (stmt
),
3148 gimple_assign_rhs2 (stmt
), stmt
);
3149 else if (gimple_assign_load_p (stmt
)
3150 && TREE_CODE (TREE_TYPE (lhs
)) == INTEGER_TYPE
3151 && TYPE_MODE (TREE_TYPE (lhs
)) == TYPE_MODE (char_type_node
)
3152 && (TYPE_PRECISION (TREE_TYPE (lhs
))
3153 == TYPE_PRECISION (char_type_node
))
3154 && !gimple_has_volatile_ops (stmt
))
3156 tree off
= integer_zero_node
;
3157 unsigned HOST_WIDE_INT coff
= 0;
3159 tree rhs1
= gimple_assign_rhs1 (stmt
);
3160 if (code
== MEM_REF
)
3162 idx
= get_stridx (TREE_OPERAND (rhs1
, 0));
3165 strinfo
*si
= get_strinfo (idx
);
3167 && si
->nonzero_chars
3168 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
3169 && (wi::to_widest (si
->nonzero_chars
)
3170 >= wi::to_widest (off
)))
3171 off
= TREE_OPERAND (rhs1
, 1);
3173 /* This case is not useful. See if get_addr_stridx
3174 returns something usable. */
3179 idx
= get_addr_stridx (rhs1
, NULL_TREE
, &coff
);
3182 strinfo
*si
= get_strinfo (idx
);
3184 && si
->nonzero_chars
3185 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
3187 widest_int w1
= wi::to_widest (si
->nonzero_chars
);
3188 widest_int w2
= wi::to_widest (off
) + coff
;
3190 && si
->full_string_p
)
3192 /* Reading the final '\0' character. */
3193 tree zero
= build_int_cst (TREE_TYPE (lhs
), 0);
3194 gimple_set_vuse (stmt
, NULL_TREE
);
3195 gimple_assign_set_rhs_from_tree (gsi
, zero
);
3196 update_stmt (gsi_stmt (*gsi
));
3200 /* Reading a character before the final '\0'
3201 character. Just set the value range to ~[0, 0]
3202 if we don't have anything better. */
3204 tree type
= TREE_TYPE (lhs
);
3205 enum value_range_type vr
3206 = get_range_info (lhs
, &min
, &max
);
3207 if (vr
== VR_VARYING
3209 && min
== wi::min_value (TYPE_PRECISION (type
),
3211 && max
== wi::max_value (TYPE_PRECISION (type
),
3213 set_range_info (lhs
, VR_ANTI_RANGE
,
3214 wi::zero (TYPE_PRECISION (type
)),
3215 wi::zero (TYPE_PRECISION (type
)));
3221 if (strlen_to_stridx
)
3223 tree rhs1
= gimple_assign_rhs1 (stmt
);
3224 if (stridx_strlenloc
*ps
= strlen_to_stridx
->get (rhs1
))
3225 strlen_to_stridx
->put (lhs
, stridx_strlenloc (*ps
));
3228 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
3230 tree type
= TREE_TYPE (lhs
);
3231 if (TREE_CODE (type
) == ARRAY_TYPE
)
3232 type
= TREE_TYPE (type
);
3233 if (TREE_CODE (type
) == INTEGER_TYPE
3234 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
3235 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
3237 if (! handle_char_store (gsi
))
3242 else if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
3244 enum tree_code code
= gimple_cond_code (cond
);
3245 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3246 fold_strstr_to_strncmp (gimple_cond_lhs (stmt
),
3247 gimple_cond_rhs (stmt
), stmt
);
3250 if (gimple_vdef (stmt
))
3251 maybe_invalidate (stmt
);
3255 /* Recursively call maybe_invalidate on stmts that might be executed
3256 in between dombb and current bb and that contain a vdef. Stop when
3257 *count stmts are inspected, or if the whole strinfo vector has
3258 been invalidated. */
3261 do_invalidate (basic_block dombb
, gimple
*phi
, bitmap visited
, int *count
)
3263 unsigned int i
, n
= gimple_phi_num_args (phi
);
3265 for (i
= 0; i
< n
; i
++)
3267 tree vuse
= gimple_phi_arg_def (phi
, i
);
3268 gimple
*stmt
= SSA_NAME_DEF_STMT (vuse
);
3269 basic_block bb
= gimple_bb (stmt
);
3272 || !bitmap_set_bit (visited
, bb
->index
)
3273 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3277 if (gimple_code (stmt
) == GIMPLE_PHI
)
3279 do_invalidate (dombb
, stmt
, visited
, count
);
3286 if (!maybe_invalidate (stmt
))
3291 vuse
= gimple_vuse (stmt
);
3292 stmt
= SSA_NAME_DEF_STMT (vuse
);
3293 if (gimple_bb (stmt
) != bb
)
3295 bb
= gimple_bb (stmt
);
3298 || !bitmap_set_bit (visited
, bb
->index
)
3299 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3306 class strlen_dom_walker
: public dom_walker
3309 strlen_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
3311 virtual edge
before_dom_children (basic_block
);
3312 virtual void after_dom_children (basic_block
);
3315 /* Callback for walk_dominator_tree. Attempt to optimize various
3316 string ops by remembering string lengths pointed by pointer SSA_NAMEs. */
3319 strlen_dom_walker::before_dom_children (basic_block bb
)
3321 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
3324 stridx_to_strinfo
= NULL
;
3327 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) dombb
->aux
);
3328 if (stridx_to_strinfo
)
3330 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3333 gphi
*phi
= gsi
.phi ();
3334 if (virtual_operand_p (gimple_phi_result (phi
)))
3336 bitmap visited
= BITMAP_ALLOC (NULL
);
3337 int count_vdef
= 100;
3338 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
3339 BITMAP_FREE (visited
);
3340 if (count_vdef
== 0)
3342 /* If there were too many vdefs in between immediate
3343 dominator and current bb, invalidate everything.
3344 If stridx_to_strinfo has been unshared, we need
3345 to free it, otherwise just set it to NULL. */
3346 if (!strinfo_shared ())
3352 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
3356 (*stridx_to_strinfo
)[i
] = NULL
;
3360 stridx_to_strinfo
= NULL
;
3368 /* If all PHI arguments have the same string index, the PHI result
3370 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3373 gphi
*phi
= gsi
.phi ();
3374 tree result
= gimple_phi_result (phi
);
3375 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
3377 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
3380 unsigned int i
, n
= gimple_phi_num_args (phi
);
3381 for (i
= 1; i
< n
; i
++)
3382 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
3385 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
3390 /* Attempt to optimize individual statements. */
3391 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
3392 if (strlen_check_and_optimize_stmt (&gsi
))
3395 bb
->aux
= stridx_to_strinfo
;
3396 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
3397 (*stridx_to_strinfo
)[0] = (strinfo
*) bb
;
3401 /* Callback for walk_dominator_tree. Free strinfo vector if it is
3402 owned by the current bb, clear bb->aux. */
3405 strlen_dom_walker::after_dom_children (basic_block bb
)
3409 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) bb
->aux
);
3410 if (vec_safe_length (stridx_to_strinfo
)
3411 && (*stridx_to_strinfo
)[0] == (strinfo
*) bb
)
3416 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
3418 vec_free (stridx_to_strinfo
);
3424 /* Main entry point. */
3428 const pass_data pass_data_strlen
=
3430 GIMPLE_PASS
, /* type */
3431 "strlen", /* name */
3432 OPTGROUP_NONE
, /* optinfo_flags */
3433 TV_TREE_STRLEN
, /* tv_id */
3434 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3435 0, /* properties_provided */
3436 0, /* properties_destroyed */
3437 0, /* todo_flags_start */
3438 0, /* todo_flags_finish */
3441 class pass_strlen
: public gimple_opt_pass
3444 pass_strlen (gcc::context
*ctxt
)
3445 : gimple_opt_pass (pass_data_strlen
, ctxt
)
3448 /* opt_pass methods: */
3449 virtual bool gate (function
*) { return flag_optimize_strlen
!= 0; }
3450 virtual unsigned int execute (function
*);
3452 }; // class pass_strlen
3455 pass_strlen::execute (function
*fun
)
3457 gcc_assert (!strlen_to_stridx
);
3458 if (warn_stringop_overflow
|| warn_stringop_truncation
)
3459 strlen_to_stridx
= new hash_map
<tree
, stridx_strlenloc
> ();
3461 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
3464 calculate_dominance_info (CDI_DOMINATORS
);
3466 /* String length optimization is implemented as a walk of the dominator
3467 tree and a forward walk of statements within each block. */
3468 strlen_dom_walker (CDI_DOMINATORS
).walk (fun
->cfg
->x_entry_block_ptr
);
3470 ssa_ver_to_stridx
.release ();
3471 strinfo_pool
.release ();
3472 if (decl_to_stridxlist_htab
)
3474 obstack_free (&stridx_obstack
, NULL
);
3475 delete decl_to_stridxlist_htab
;
3476 decl_to_stridxlist_htab
= NULL
;
3478 laststmt
.stmt
= NULL
;
3479 laststmt
.len
= NULL_TREE
;
3480 laststmt
.stridx
= 0;
3482 if (strlen_to_stridx
)
3484 strlen_to_stridx
->empty ();
3485 delete strlen_to_stridx
;
3486 strlen_to_stridx
= NULL
;
3495 make_pass_strlen (gcc::context
*ctxt
)
3497 return new pass_strlen (ctxt
);