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"
49 #include "tree-hash-traits.h"
52 #include "diagnostic-core.h"
53 #include "diagnostic.h"
58 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
59 is an index into strinfo vector, negative value stands for
60 string length of a string literal (~strlen). */
61 static vec
<int> ssa_ver_to_stridx
;
63 /* Number of currently active string indexes plus one. */
64 static int max_stridx
;
66 /* String information record. */
69 /* Number of leading characters that are known to be nonzero. This is
70 also the length of the string if FULL_STRING_P.
72 The values in a list of related string pointers must be consistent;
73 that is, if strinfo B comes X bytes after strinfo A, it must be
74 the case that A->nonzero_chars == X + B->nonzero_chars. */
76 /* Any of the corresponding pointers for querying alias oracle. */
78 /* This is used for two things:
80 - To record the statement that should be used for delayed length
81 computations. We maintain the invariant that all related strinfos
82 have delayed lengths or none do.
84 - To record the malloc or calloc call that produced this result. */
86 /* Pointer to '\0' if known, if NULL, it can be computed as
89 /* Reference count. Any changes to strinfo entry possibly shared
90 with dominating basic blocks need unshare_strinfo first, except
91 for dont_invalidate which affects only the immediately next
94 /* Copy of index. get_strinfo (si->idx) should return si; */
96 /* These 3 fields are for chaining related string pointers together.
98 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
99 strcpy (c, d); e = c + dl;
100 strinfo(a) -> strinfo(c) -> strinfo(e)
101 All have ->first field equal to strinfo(a)->idx and are doubly
102 chained through prev/next fields. The later strinfos are required
103 to point into the same string with zero or more bytes after
104 the previous pointer and all bytes in between the two pointers
105 must be non-zero. Functions like strcpy or memcpy are supposed
106 to adjust all previous strinfo lengths, but not following strinfo
107 lengths (those are uncertain, usually invalidated during
108 maybe_invalidate, except when the alias oracle knows better).
109 Functions like strcat on the other side adjust the whole
110 related strinfo chain.
111 They are updated lazily, so to use the chain the same first fields
112 and si->prev->next == si->idx needs to be verified. */
116 /* A flag whether the string is known to be written in the current
119 /* A flag for the next maybe_invalidate that this strinfo shouldn't
120 be invalidated. Always cleared by maybe_invalidate. */
121 bool dont_invalidate
;
122 /* True if the string is known to be nul-terminated after NONZERO_CHARS
123 characters. False is useful when detecting strings that are built
124 up via successive memcpys. */
128 /* Pool for allocating strinfo_struct entries. */
129 static object_allocator
<strinfo
> strinfo_pool ("strinfo pool");
131 /* Vector mapping positive string indexes to strinfo, for the
132 current basic block. The first pointer in the vector is special,
133 it is either NULL, meaning the vector isn't shared, or it is
134 a basic block pointer to the owner basic_block if shared.
135 If some other bb wants to modify the vector, the vector needs
136 to be unshared first, and only the owner bb is supposed to free it. */
137 static vec
<strinfo
*, va_heap
, vl_embed
> *stridx_to_strinfo
;
139 /* One OFFSET->IDX mapping. */
142 struct stridxlist
*next
;
143 HOST_WIDE_INT offset
;
147 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
148 struct decl_stridxlist_map
150 struct tree_map_base base
;
151 struct stridxlist list
;
154 /* Hash table for mapping decls to a chained list of offset -> idx
156 static hash_map
<tree_decl_hash
, stridxlist
> *decl_to_stridxlist_htab
;
158 /* Hash table mapping strlen calls to stridx instances describing
159 the calls' arguments. Non-null only when warn_stringop_truncation
161 typedef std::pair
<int, location_t
> stridx_strlenloc
;
162 static hash_map
<tree
, stridx_strlenloc
> *strlen_to_stridx
;
164 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
165 static struct obstack stridx_obstack
;
167 /* Last memcpy statement if it could be adjusted if the trailing
168 '\0' written is immediately overwritten, or
169 *x = '\0' store that could be removed if it is immediately overwritten. */
170 struct laststmt_struct
177 static int get_stridx_plus_constant (strinfo
*, unsigned HOST_WIDE_INT
, tree
);
178 static void handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*);
182 - 1 if SI is known to start with more than OFF nonzero characters.
184 - 0 if SI is known to start with OFF nonzero characters,
185 but is not known to start with more.
187 - -1 if SI might not start with OFF nonzero characters. */
190 compare_nonzero_chars (strinfo
*si
, unsigned HOST_WIDE_INT off
)
192 if (si
->nonzero_chars
193 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
194 return compare_tree_int (si
->nonzero_chars
, off
);
199 /* Return true if SI is known to be a zero-length string. */
202 zero_length_string_p (strinfo
*si
)
204 return si
->full_string_p
&& integer_zerop (si
->nonzero_chars
);
207 /* Return strinfo vector entry IDX. */
209 static inline strinfo
*
210 get_strinfo (int idx
)
212 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
214 return (*stridx_to_strinfo
)[idx
];
217 /* Get the next strinfo in the chain after SI, or null if none. */
219 static inline strinfo
*
220 get_next_strinfo (strinfo
*si
)
224 strinfo
*nextsi
= get_strinfo (si
->next
);
225 if (nextsi
== NULL
|| nextsi
->first
!= si
->first
|| nextsi
->prev
!= si
->idx
)
230 /* Helper function for get_stridx. Return the strinfo index of the address
231 of EXP, which is available in PTR if nonnull. If OFFSET_OUT, it is
232 OK to return the index for some X <= &EXP and store &EXP - X in
236 get_addr_stridx (tree exp
, tree ptr
, unsigned HOST_WIDE_INT
*offset_out
)
239 struct stridxlist
*list
, *last
= NULL
;
242 if (!decl_to_stridxlist_htab
)
246 base
= get_addr_base_and_unit_offset (exp
, &poff
);
247 if (base
== NULL
|| !DECL_P (base
) || !poff
.is_constant (&off
))
250 list
= decl_to_stridxlist_htab
->get (base
);
256 if (list
->offset
== off
)
262 if (list
->offset
> off
)
269 if ((offset_out
|| ptr
) && last
&& last
->idx
> 0)
271 unsigned HOST_WIDE_INT rel_off
272 = (unsigned HOST_WIDE_INT
) off
- last
->offset
;
273 strinfo
*si
= get_strinfo (last
->idx
);
274 if (si
&& compare_nonzero_chars (si
, rel_off
) >= 0)
278 *offset_out
= rel_off
;
282 return get_stridx_plus_constant (si
, rel_off
, ptr
);
288 /* Return string index for EXP. */
291 get_stridx (tree exp
)
295 if (TREE_CODE (exp
) == SSA_NAME
)
297 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)])
298 return ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)];
301 HOST_WIDE_INT off
= 0;
302 for (i
= 0; i
< 5; i
++)
304 gimple
*def_stmt
= SSA_NAME_DEF_STMT (e
);
305 if (!is_gimple_assign (def_stmt
)
306 || gimple_assign_rhs_code (def_stmt
) != POINTER_PLUS_EXPR
)
308 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
309 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
310 if (TREE_CODE (rhs1
) != SSA_NAME
311 || !tree_fits_shwi_p (rhs2
))
313 HOST_WIDE_INT this_off
= tree_to_shwi (rhs2
);
316 off
= (unsigned HOST_WIDE_INT
) off
+ this_off
;
319 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)])
322 = get_strinfo (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)]);
323 if (si
&& compare_nonzero_chars (si
, off
) >= 0)
324 return get_stridx_plus_constant (si
, off
, exp
);
331 if (TREE_CODE (exp
) == ADDR_EXPR
)
333 int idx
= get_addr_stridx (TREE_OPERAND (exp
, 0), exp
, NULL
);
338 s
= string_constant (exp
, &o
);
340 && (o
== NULL_TREE
|| tree_fits_shwi_p (o
))
341 && TREE_STRING_LENGTH (s
) > 0)
343 HOST_WIDE_INT offset
= o
? tree_to_shwi (o
) : 0;
344 const char *p
= TREE_STRING_POINTER (s
);
345 int max
= TREE_STRING_LENGTH (s
) - 1;
347 if (p
[max
] == '\0' && offset
>= 0 && offset
<= max
)
348 return ~(int) strlen (p
+ offset
);
353 /* Return true if strinfo vector is shared with the immediate dominator. */
356 strinfo_shared (void)
358 return vec_safe_length (stridx_to_strinfo
)
359 && (*stridx_to_strinfo
)[0] != NULL
;
362 /* Unshare strinfo vector that is shared with the immediate dominator. */
365 unshare_strinfo_vec (void)
370 gcc_assert (strinfo_shared ());
371 stridx_to_strinfo
= vec_safe_copy (stridx_to_strinfo
);
372 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
375 (*stridx_to_strinfo
)[0] = NULL
;
378 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
379 Return a pointer to the location where the string index can
380 be stored (if 0) or is stored, or NULL if this can't be tracked. */
383 addr_stridxptr (tree exp
)
388 tree base
= get_addr_base_and_unit_offset (exp
, &poff
);
389 if (base
== NULL_TREE
|| !DECL_P (base
) || !poff
.is_constant (&off
))
392 if (!decl_to_stridxlist_htab
)
394 decl_to_stridxlist_htab
395 = new hash_map
<tree_decl_hash
, stridxlist
> (64);
396 gcc_obstack_init (&stridx_obstack
);
400 stridxlist
*list
= &decl_to_stridxlist_htab
->get_or_insert (base
, &existed
);
404 stridxlist
*before
= NULL
;
405 for (i
= 0; i
< 32; i
++)
407 if (list
->offset
== off
)
409 if (list
->offset
> off
&& before
== NULL
)
411 if (list
->next
== NULL
)
420 before
= XOBNEW (&stridx_obstack
, struct stridxlist
);
427 list
->next
= XOBNEW (&stridx_obstack
, struct stridxlist
);
437 /* Create a new string index, or return 0 if reached limit. */
440 new_stridx (tree exp
)
443 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
445 if (TREE_CODE (exp
) == SSA_NAME
)
447 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
450 ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)] = idx
;
453 if (TREE_CODE (exp
) == ADDR_EXPR
)
455 int *pidx
= addr_stridxptr (TREE_OPERAND (exp
, 0));
458 gcc_assert (*pidx
== 0);
459 *pidx
= max_stridx
++;
466 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
469 new_addr_stridx (tree exp
)
472 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
474 pidx
= addr_stridxptr (exp
);
477 gcc_assert (*pidx
== 0);
478 *pidx
= max_stridx
++;
484 /* Create a new strinfo. */
487 new_strinfo (tree ptr
, int idx
, tree nonzero_chars
, bool full_string_p
)
489 strinfo
*si
= strinfo_pool
.allocate ();
490 si
->nonzero_chars
= nonzero_chars
;
493 si
->endptr
= NULL_TREE
;
499 si
->writable
= false;
500 si
->dont_invalidate
= false;
501 si
->full_string_p
= full_string_p
;
505 /* Decrease strinfo refcount and free it if not referenced anymore. */
508 free_strinfo (strinfo
*si
)
510 if (si
&& --si
->refcount
== 0)
511 strinfo_pool
.remove (si
);
514 /* Set strinfo in the vector entry IDX to SI. */
517 set_strinfo (int idx
, strinfo
*si
)
519 if (vec_safe_length (stridx_to_strinfo
) && (*stridx_to_strinfo
)[0])
520 unshare_strinfo_vec ();
521 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
522 vec_safe_grow_cleared (stridx_to_strinfo
, idx
+ 1);
523 (*stridx_to_strinfo
)[idx
] = si
;
526 /* Return the first strinfo in the related strinfo chain
527 if all strinfos in between belong to the chain, otherwise NULL. */
530 verify_related_strinfos (strinfo
*origsi
)
532 strinfo
*si
= origsi
, *psi
;
534 if (origsi
->first
== 0)
536 for (; si
->prev
; si
= psi
)
538 if (si
->first
!= origsi
->first
)
540 psi
= get_strinfo (si
->prev
);
543 if (psi
->next
!= si
->idx
)
546 if (si
->idx
!= si
->first
)
551 /* Set SI's endptr to ENDPTR and compute its length based on SI->ptr.
552 Use LOC for folding. */
555 set_endptr_and_length (location_t loc
, strinfo
*si
, tree endptr
)
559 tree start_as_size
= fold_convert_loc (loc
, size_type_node
, si
->ptr
);
560 tree end_as_size
= fold_convert_loc (loc
, size_type_node
, endptr
);
561 si
->nonzero_chars
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
562 end_as_size
, start_as_size
);
563 si
->full_string_p
= true;
566 /* Return string length, or NULL if it can't be computed. */
569 get_string_length (strinfo
*si
)
571 if (si
->nonzero_chars
)
572 return si
->full_string_p
? si
->nonzero_chars
: NULL
;
576 gimple
*stmt
= si
->stmt
, *lenstmt
;
577 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
578 tree callee
, lhs
, fn
, tem
;
580 gimple_stmt_iterator gsi
;
582 gcc_assert (is_gimple_call (stmt
));
583 callee
= gimple_call_fndecl (stmt
);
584 gcc_assert (callee
&& DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
);
585 lhs
= gimple_call_lhs (stmt
);
586 /* unshare_strinfo is intentionally not called here. The (delayed)
587 transformation of strcpy or strcat into stpcpy is done at the place
588 of the former strcpy/strcat call and so can affect all the strinfos
589 with the same stmt. If they were unshared before and transformation
590 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
591 just compute the right length. */
592 switch (DECL_FUNCTION_CODE (callee
))
594 case BUILT_IN_STRCAT
:
595 case BUILT_IN_STRCAT_CHK
:
596 case BUILT_IN_STRCAT_CHKP
:
597 case BUILT_IN_STRCAT_CHK_CHKP
:
598 gsi
= gsi_for_stmt (stmt
);
599 fn
= builtin_decl_implicit (BUILT_IN_STRLEN
);
600 gcc_assert (lhs
== NULL_TREE
);
601 tem
= unshare_expr (gimple_call_arg (stmt
, 0));
604 lenstmt
= gimple_build_call (chkp_maybe_create_clone (fn
)->decl
,
605 2, tem
, gimple_call_arg (stmt
, 1));
606 gimple_call_set_with_bounds (lenstmt
, true);
609 lenstmt
= gimple_build_call (fn
, 1, tem
);
610 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), lenstmt
);
611 gimple_call_set_lhs (lenstmt
, lhs
);
612 gimple_set_vuse (lenstmt
, gimple_vuse (stmt
));
613 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
614 tem
= gimple_call_arg (stmt
, 0);
615 if (!ptrofftype_p (TREE_TYPE (lhs
)))
617 lhs
= convert_to_ptrofftype (lhs
);
618 lhs
= force_gimple_operand_gsi (&gsi
, lhs
, true, NULL_TREE
,
619 true, GSI_SAME_STMT
);
621 lenstmt
= gimple_build_assign
622 (make_ssa_name (TREE_TYPE (gimple_call_arg (stmt
, 0))),
623 POINTER_PLUS_EXPR
,tem
, lhs
);
624 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
625 gimple_call_set_arg (stmt
, 0, gimple_assign_lhs (lenstmt
));
628 case BUILT_IN_STRCPY
:
629 case BUILT_IN_STRCPY_CHK
:
630 case BUILT_IN_STRCPY_CHKP
:
631 case BUILT_IN_STRCPY_CHK_CHKP
:
632 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY
));
633 if (gimple_call_num_args (stmt
) == (with_bounds
? 4 : 2))
634 fn
= builtin_decl_implicit (BUILT_IN_STPCPY
);
636 fn
= builtin_decl_explicit (BUILT_IN_STPCPY_CHK
);
638 fn
= chkp_maybe_create_clone (fn
)->decl
;
639 gcc_assert (lhs
== NULL_TREE
);
640 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
642 fprintf (dump_file
, "Optimizing: ");
643 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
645 gimple_call_set_fndecl (stmt
, fn
);
646 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), stmt
);
647 gimple_call_set_lhs (stmt
, lhs
);
649 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
651 fprintf (dump_file
, "into: ");
652 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
655 case BUILT_IN_STPCPY
:
656 case BUILT_IN_STPCPY_CHK
:
657 case BUILT_IN_STPCPY_CHKP
:
658 case BUILT_IN_STPCPY_CHK_CHKP
:
659 gcc_assert (lhs
!= NULL_TREE
);
660 loc
= gimple_location (stmt
);
661 set_endptr_and_length (loc
, si
, lhs
);
662 for (strinfo
*chainsi
= verify_related_strinfos (si
);
664 chainsi
= get_next_strinfo (chainsi
))
665 if (chainsi
->nonzero_chars
== NULL
)
666 set_endptr_and_length (loc
, chainsi
, lhs
);
668 case BUILT_IN_MALLOC
:
670 /* BUILT_IN_CALLOC always has si->nonzero_chars set. */
677 return si
->nonzero_chars
;
680 /* Invalidate string length information for strings whose length
681 might change due to stores in stmt. */
684 maybe_invalidate (gimple
*stmt
)
688 bool nonempty
= false;
690 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
693 if (!si
->dont_invalidate
)
696 /* Do not use si->nonzero_chars. */
697 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, NULL_TREE
);
698 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
700 set_strinfo (i
, NULL
);
705 si
->dont_invalidate
= false;
711 /* Unshare strinfo record SI, if it has refcount > 1 or
712 if stridx_to_strinfo vector is shared with some other
716 unshare_strinfo (strinfo
*si
)
720 if (si
->refcount
== 1 && !strinfo_shared ())
723 nsi
= new_strinfo (si
->ptr
, si
->idx
, si
->nonzero_chars
, si
->full_string_p
);
724 nsi
->stmt
= si
->stmt
;
725 nsi
->endptr
= si
->endptr
;
726 nsi
->first
= si
->first
;
727 nsi
->prev
= si
->prev
;
728 nsi
->next
= si
->next
;
729 nsi
->writable
= si
->writable
;
730 set_strinfo (si
->idx
, nsi
);
735 /* Attempt to create a new strinfo for BASESI + OFF, or find existing
736 strinfo if there is any. Return it's idx, or 0 if no strinfo has
740 get_stridx_plus_constant (strinfo
*basesi
, unsigned HOST_WIDE_INT off
,
743 if (TREE_CODE (ptr
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
746 if (compare_nonzero_chars (basesi
, off
) < 0
747 || !tree_fits_uhwi_p (basesi
->nonzero_chars
))
750 unsigned HOST_WIDE_INT nonzero_chars
751 = tree_to_uhwi (basesi
->nonzero_chars
) - off
;
752 strinfo
*si
= basesi
, *chainsi
;
753 if (si
->first
|| si
->prev
|| si
->next
)
754 si
= verify_related_strinfos (basesi
);
756 || si
->nonzero_chars
== NULL_TREE
757 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
760 if (TREE_CODE (ptr
) == SSA_NAME
761 && ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
762 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
764 gcc_checking_assert (compare_tree_int (si
->nonzero_chars
, off
) != -1);
765 for (chainsi
= si
; chainsi
->next
; chainsi
= si
)
767 si
= get_next_strinfo (chainsi
);
769 || si
->nonzero_chars
== NULL_TREE
770 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
772 int r
= compare_tree_int (si
->nonzero_chars
, nonzero_chars
);
777 if (TREE_CODE (ptr
) == SSA_NAME
)
778 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = si
->idx
;
781 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
782 if (pidx
!= NULL
&& *pidx
== 0)
791 int idx
= new_stridx (ptr
);
794 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, nonzero_chars
),
795 basesi
->full_string_p
);
796 set_strinfo (idx
, si
);
799 strinfo
*nextsi
= unshare_strinfo (get_strinfo (chainsi
->next
));
800 si
->next
= nextsi
->idx
;
803 chainsi
= unshare_strinfo (chainsi
);
804 if (chainsi
->first
== 0)
805 chainsi
->first
= chainsi
->idx
;
807 if (chainsi
->endptr
== NULL_TREE
&& zero_length_string_p (si
))
808 chainsi
->endptr
= ptr
;
809 si
->endptr
= chainsi
->endptr
;
810 si
->prev
= chainsi
->idx
;
811 si
->first
= chainsi
->first
;
812 si
->writable
= chainsi
->writable
;
816 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
817 to a zero-length string and if possible chain it to a related strinfo
818 chain whose part is or might be CHAINSI. */
821 zero_length_string (tree ptr
, strinfo
*chainsi
)
825 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
826 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
827 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
828 && ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] == 0);
830 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
834 si
= verify_related_strinfos (chainsi
);
839 /* We shouldn't mix delayed and non-delayed lengths. */
840 gcc_assert (si
->full_string_p
);
841 if (si
->endptr
== NULL_TREE
)
843 si
= unshare_strinfo (si
);
847 si
= get_next_strinfo (si
);
850 if (zero_length_string_p (chainsi
))
854 chainsi
= unshare_strinfo (chainsi
);
857 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = chainsi
->idx
;
863 /* We shouldn't mix delayed and non-delayed lengths. */
864 gcc_assert (chainsi
->full_string_p
);
865 if (chainsi
->first
|| chainsi
->prev
|| chainsi
->next
)
867 chainsi
= unshare_strinfo (chainsi
);
874 idx
= new_stridx (ptr
);
877 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, 0), true);
878 set_strinfo (idx
, si
);
882 chainsi
= unshare_strinfo (chainsi
);
883 if (chainsi
->first
== 0)
884 chainsi
->first
= chainsi
->idx
;
886 if (chainsi
->endptr
== NULL_TREE
)
887 chainsi
->endptr
= ptr
;
888 si
->prev
= chainsi
->idx
;
889 si
->first
= chainsi
->first
;
890 si
->writable
= chainsi
->writable
;
895 /* For strinfo ORIGSI whose length has been just updated, adjust other
896 related strinfos so that they match the new ORIGSI. This involves:
898 - adding ADJ to the nonzero_chars fields
899 - copying full_string_p from the new ORIGSI. */
902 adjust_related_strinfos (location_t loc
, strinfo
*origsi
, tree adj
)
904 strinfo
*si
= verify_related_strinfos (origsi
);
917 si
= unshare_strinfo (si
);
918 /* We shouldn't see delayed lengths here; the caller must have
919 calculated the old length in order to calculate the
921 gcc_assert (si
->nonzero_chars
);
922 tem
= fold_convert_loc (loc
, TREE_TYPE (si
->nonzero_chars
), adj
);
923 si
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
924 TREE_TYPE (si
->nonzero_chars
),
925 si
->nonzero_chars
, tem
);
926 si
->full_string_p
= origsi
->full_string_p
;
928 si
->endptr
= NULL_TREE
;
929 si
->dont_invalidate
= true;
931 nsi
= get_next_strinfo (si
);
938 /* Find if there are other SSA_NAME pointers equal to PTR
939 for which we don't track their string lengths yet. If so, use
943 find_equal_ptrs (tree ptr
, int idx
)
945 if (TREE_CODE (ptr
) != SSA_NAME
)
949 gimple
*stmt
= SSA_NAME_DEF_STMT (ptr
);
950 if (!is_gimple_assign (stmt
))
952 ptr
= gimple_assign_rhs1 (stmt
);
953 switch (gimple_assign_rhs_code (stmt
))
958 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)))
960 if (TREE_CODE (ptr
) == SSA_NAME
)
962 if (TREE_CODE (ptr
) != ADDR_EXPR
)
967 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
968 if (pidx
!= NULL
&& *pidx
== 0)
976 /* We might find an endptr created in this pass. Grow the
977 vector in that case. */
978 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
979 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
981 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] != 0)
983 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = idx
;
987 /* Return true if STMT is a call to a builtin function with the right
988 arguments and attributes that should be considered for optimization
992 valid_builtin_call (gimple
*stmt
)
994 if (!gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
997 tree callee
= gimple_call_fndecl (stmt
);
998 switch (DECL_FUNCTION_CODE (callee
))
1000 case BUILT_IN_MEMCMP
:
1001 case BUILT_IN_MEMCMP_EQ
:
1002 case BUILT_IN_STRCHR
:
1003 case BUILT_IN_STRCHR_CHKP
:
1004 case BUILT_IN_STRLEN
:
1005 case BUILT_IN_STRLEN_CHKP
:
1006 /* The above functions should be pure. Punt if they aren't. */
1007 if (gimple_vdef (stmt
) || gimple_vuse (stmt
) == NULL_TREE
)
1011 case BUILT_IN_CALLOC
:
1012 case BUILT_IN_MALLOC
:
1013 case BUILT_IN_MEMCPY
:
1014 case BUILT_IN_MEMCPY_CHK
:
1015 case BUILT_IN_MEMCPY_CHKP
:
1016 case BUILT_IN_MEMCPY_CHK_CHKP
:
1017 case BUILT_IN_MEMPCPY
:
1018 case BUILT_IN_MEMPCPY_CHK
:
1019 case BUILT_IN_MEMPCPY_CHKP
:
1020 case BUILT_IN_MEMPCPY_CHK_CHKP
:
1021 case BUILT_IN_MEMSET
:
1022 case BUILT_IN_STPCPY
:
1023 case BUILT_IN_STPCPY_CHK
:
1024 case BUILT_IN_STPCPY_CHKP
:
1025 case BUILT_IN_STPCPY_CHK_CHKP
:
1026 case BUILT_IN_STRCAT
:
1027 case BUILT_IN_STRCAT_CHK
:
1028 case BUILT_IN_STRCAT_CHKP
:
1029 case BUILT_IN_STRCAT_CHK_CHKP
:
1030 case BUILT_IN_STRCPY
:
1031 case BUILT_IN_STRCPY_CHK
:
1032 case BUILT_IN_STRCPY_CHKP
:
1033 case BUILT_IN_STRCPY_CHK_CHKP
:
1034 /* The above functions should be neither const nor pure. Punt if they
1036 if (gimple_vdef (stmt
) == NULL_TREE
|| gimple_vuse (stmt
) == NULL_TREE
)
1047 /* If the last .MEM setter statement before STMT is
1048 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
1049 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
1050 just memcpy (x, y, strlen (y)). SI must be the zero length
1054 adjust_last_stmt (strinfo
*si
, gimple
*stmt
, bool is_strcat
)
1056 tree vuse
, callee
, len
;
1057 struct laststmt_struct last
= laststmt
;
1058 strinfo
*lastsi
, *firstsi
;
1059 unsigned len_arg_no
= 2;
1061 laststmt
.stmt
= NULL
;
1062 laststmt
.len
= NULL_TREE
;
1063 laststmt
.stridx
= 0;
1065 if (last
.stmt
== NULL
)
1068 vuse
= gimple_vuse (stmt
);
1069 if (vuse
== NULL_TREE
1070 || SSA_NAME_DEF_STMT (vuse
) != last
.stmt
1071 || !has_single_use (vuse
))
1074 gcc_assert (last
.stridx
> 0);
1075 lastsi
= get_strinfo (last
.stridx
);
1081 if (lastsi
->first
== 0 || lastsi
->first
!= si
->first
)
1084 firstsi
= verify_related_strinfos (si
);
1085 if (firstsi
== NULL
)
1087 while (firstsi
!= lastsi
)
1089 firstsi
= get_next_strinfo (firstsi
);
1090 if (firstsi
== NULL
)
1095 if (!is_strcat
&& !zero_length_string_p (si
))
1098 if (is_gimple_assign (last
.stmt
))
1100 gimple_stmt_iterator gsi
;
1102 if (!integer_zerop (gimple_assign_rhs1 (last
.stmt
)))
1104 if (stmt_could_throw_p (last
.stmt
))
1106 gsi
= gsi_for_stmt (last
.stmt
);
1107 unlink_stmt_vdef (last
.stmt
);
1108 release_defs (last
.stmt
);
1109 gsi_remove (&gsi
, true);
1113 if (!valid_builtin_call (last
.stmt
))
1116 callee
= gimple_call_fndecl (last
.stmt
);
1117 switch (DECL_FUNCTION_CODE (callee
))
1119 case BUILT_IN_MEMCPY
:
1120 case BUILT_IN_MEMCPY_CHK
:
1122 case BUILT_IN_MEMCPY_CHKP
:
1123 case BUILT_IN_MEMCPY_CHK_CHKP
:
1130 len
= gimple_call_arg (last
.stmt
, len_arg_no
);
1131 if (tree_fits_uhwi_p (len
))
1133 if (!tree_fits_uhwi_p (last
.len
)
1134 || integer_zerop (len
)
1135 || tree_to_uhwi (len
) != tree_to_uhwi (last
.len
) + 1)
1137 /* Don't adjust the length if it is divisible by 4, it is more efficient
1138 to store the extra '\0' in that case. */
1139 if ((tree_to_uhwi (len
) & 3) == 0)
1142 else if (TREE_CODE (len
) == SSA_NAME
)
1144 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1145 if (!is_gimple_assign (def_stmt
)
1146 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1147 || gimple_assign_rhs1 (def_stmt
) != last
.len
1148 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1154 gimple_call_set_arg (last
.stmt
, len_arg_no
, last
.len
);
1155 update_stmt (last
.stmt
);
1158 /* For an LHS that is an SSA_NAME and for strlen() argument SRC, set
1159 LHS range info to [0, N] if SRC refers to a character array A[N]
1160 with unknown length bounded by N. */
1163 maybe_set_strlen_range (tree lhs
, tree src
)
1165 if (TREE_CODE (lhs
) != SSA_NAME
)
1168 if (TREE_CODE (src
) == SSA_NAME
)
1170 gimple
*def
= SSA_NAME_DEF_STMT (src
);
1171 if (is_gimple_assign (def
)
1172 && gimple_assign_rhs_code (def
) == ADDR_EXPR
)
1173 src
= gimple_assign_rhs1 (def
);
1176 if (TREE_CODE (src
) != ADDR_EXPR
)
1179 /* The last array member of a struct can be bigger than its size
1180 suggests if it's treated as a poor-man's flexible array member. */
1181 src
= TREE_OPERAND (src
, 0);
1182 if (TREE_CODE (TREE_TYPE (src
)) != ARRAY_TYPE
1183 || array_at_struct_end_p (src
))
1186 tree type
= TREE_TYPE (src
);
1187 if (tree dom
= TYPE_DOMAIN (type
))
1188 if (tree maxval
= TYPE_MAX_VALUE (dom
))
1190 wide_int max
= wi::to_wide (maxval
);
1191 wide_int min
= wi::zero (max
.get_precision ());
1192 set_range_info (lhs
, VR_RANGE
, min
, max
);
1196 /* Handle a strlen call. If strlen of the argument is known, replace
1197 the strlen call with the known value, otherwise remember that strlen
1198 of the argument is stored in the lhs SSA_NAME. */
1201 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
1205 gimple
*stmt
= gsi_stmt (*gsi
);
1206 tree lhs
= gimple_call_lhs (stmt
);
1208 if (lhs
== NULL_TREE
)
1211 src
= gimple_call_arg (stmt
, 0);
1212 idx
= get_stridx (src
);
1219 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
1223 si
= get_strinfo (idx
);
1225 rhs
= get_string_length (si
);
1227 if (rhs
!= NULL_TREE
)
1229 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1231 fprintf (dump_file
, "Optimizing: ");
1232 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1234 rhs
= unshare_expr (rhs
);
1235 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
1236 rhs
= fold_convert_loc (gimple_location (stmt
),
1237 TREE_TYPE (lhs
), rhs
);
1238 if (!update_call_from_tree (gsi
, rhs
))
1239 gimplify_and_update_call_from_tree (gsi
, rhs
);
1240 stmt
= gsi_stmt (*gsi
);
1242 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1244 fprintf (dump_file
, "into: ");
1245 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1248 && TREE_CODE (si
->nonzero_chars
) != SSA_NAME
1249 && TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
1250 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1252 si
= unshare_strinfo (si
);
1253 si
->nonzero_chars
= lhs
;
1254 gcc_assert (si
->full_string_p
);
1257 if (strlen_to_stridx
)
1259 location_t loc
= gimple_location (stmt
);
1260 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1265 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1268 idx
= new_stridx (src
);
1271 strinfo
*si
= get_strinfo (idx
);
1274 if (!si
->full_string_p
&& !si
->stmt
)
1276 /* Until now we only had a lower bound on the string length.
1277 Install LHS as the actual length. */
1278 si
= unshare_strinfo (si
);
1279 tree old
= si
->nonzero_chars
;
1280 si
->nonzero_chars
= lhs
;
1281 si
->full_string_p
= true;
1282 if (TREE_CODE (old
) == INTEGER_CST
)
1284 location_t loc
= gimple_location (stmt
);
1285 old
= fold_convert_loc (loc
, TREE_TYPE (lhs
), old
);
1286 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1287 TREE_TYPE (lhs
), lhs
, old
);
1288 adjust_related_strinfos (loc
, si
, adj
);
1302 strinfo
*si
= new_strinfo (src
, idx
, lhs
, true);
1303 set_strinfo (idx
, si
);
1304 find_equal_ptrs (src
, idx
);
1306 /* For SRC that is an array of N elements, set LHS's range
1308 maybe_set_strlen_range (lhs
, src
);
1310 if (strlen_to_stridx
)
1312 location_t loc
= gimple_location (stmt
);
1313 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1318 /* Handle a strchr call. If strlen of the first argument is known, replace
1319 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
1320 that lhs of the call is endptr and strlen of the argument is endptr - x. */
1323 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
1327 gimple
*stmt
= gsi_stmt (*gsi
);
1328 tree lhs
= gimple_call_lhs (stmt
);
1329 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1331 if (lhs
== NULL_TREE
)
1334 if (!integer_zerop (gimple_call_arg (stmt
, with_bounds
? 2 : 1)))
1337 src
= gimple_call_arg (stmt
, 0);
1338 idx
= get_stridx (src
);
1345 rhs
= build_int_cst (size_type_node
, ~idx
);
1349 si
= get_strinfo (idx
);
1351 rhs
= get_string_length (si
);
1353 if (rhs
!= NULL_TREE
)
1355 location_t loc
= gimple_location (stmt
);
1357 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1359 fprintf (dump_file
, "Optimizing: ");
1360 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1362 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
1364 rhs
= unshare_expr (si
->endptr
);
1365 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1367 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1371 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1372 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1373 TREE_TYPE (src
), src
, rhs
);
1374 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1376 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1378 if (!update_call_from_tree (gsi
, rhs
))
1379 gimplify_and_update_call_from_tree (gsi
, rhs
);
1380 stmt
= gsi_stmt (*gsi
);
1382 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1384 fprintf (dump_file
, "into: ");
1385 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1388 && si
->endptr
== NULL_TREE
1389 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1391 si
= unshare_strinfo (si
);
1394 zero_length_string (lhs
, si
);
1398 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1400 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1403 idx
= new_stridx (src
);
1404 else if (get_strinfo (idx
) != NULL
)
1406 zero_length_string (lhs
, NULL
);
1411 location_t loc
= gimple_location (stmt
);
1412 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1413 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1414 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1415 size_type_node
, lhsu
, srcu
);
1416 strinfo
*si
= new_strinfo (src
, idx
, length
, true);
1418 set_strinfo (idx
, si
);
1419 find_equal_ptrs (src
, idx
);
1420 zero_length_string (lhs
, si
);
1424 zero_length_string (lhs
, NULL
);
1427 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1428 If strlen of the second argument is known, strlen of the first argument
1429 is the same after this call. Furthermore, attempt to convert it to
1433 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1436 tree src
, dst
, srclen
, len
, lhs
, type
, fn
, oldlen
;
1438 gimple
*stmt
= gsi_stmt (*gsi
);
1439 strinfo
*si
, *dsi
, *olddsi
, *zsi
;
1441 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1443 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1444 dst
= gimple_call_arg (stmt
, 0);
1445 lhs
= gimple_call_lhs (stmt
);
1446 idx
= get_stridx (src
);
1449 si
= get_strinfo (idx
);
1451 didx
= get_stridx (dst
);
1455 olddsi
= get_strinfo (didx
);
1460 adjust_last_stmt (olddsi
, stmt
, false);
1464 srclen
= get_string_length (si
);
1466 srclen
= build_int_cst (size_type_node
, ~idx
);
1468 loc
= gimple_location (stmt
);
1469 if (srclen
== NULL_TREE
)
1472 case BUILT_IN_STRCPY
:
1473 case BUILT_IN_STRCPY_CHK
:
1474 case BUILT_IN_STRCPY_CHKP
:
1475 case BUILT_IN_STRCPY_CHK_CHKP
:
1476 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1479 case BUILT_IN_STPCPY
:
1480 case BUILT_IN_STPCPY_CHK
:
1481 case BUILT_IN_STPCPY_CHKP
:
1482 case BUILT_IN_STPCPY_CHK_CHKP
:
1483 if (lhs
== NULL_TREE
)
1487 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1488 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1489 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1499 didx
= new_stridx (dst
);
1505 oldlen
= olddsi
->nonzero_chars
;
1506 dsi
= unshare_strinfo (olddsi
);
1507 dsi
->nonzero_chars
= srclen
;
1508 dsi
->full_string_p
= (srclen
!= NULL_TREE
);
1509 /* Break the chain, so adjust_related_strinfo on later pointers in
1510 the chain won't adjust this one anymore. */
1513 dsi
->endptr
= NULL_TREE
;
1517 dsi
= new_strinfo (dst
, didx
, srclen
, srclen
!= NULL_TREE
);
1518 set_strinfo (didx
, dsi
);
1519 find_equal_ptrs (dst
, didx
);
1521 dsi
->writable
= true;
1522 dsi
->dont_invalidate
= true;
1524 if (dsi
->nonzero_chars
== NULL_TREE
)
1528 /* If string length of src is unknown, use delayed length
1529 computation. If string lenth of dst will be needed, it
1530 can be computed by transforming this strcpy call into
1531 stpcpy and subtracting dst from the return value. */
1533 /* Look for earlier strings whose length could be determined if
1534 this strcpy is turned into an stpcpy. */
1536 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1538 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1540 /* When setting a stmt for delayed length computation
1541 prevent all strinfos through dsi from being
1543 chainsi
= unshare_strinfo (chainsi
);
1544 chainsi
->stmt
= stmt
;
1545 chainsi
->nonzero_chars
= NULL_TREE
;
1546 chainsi
->full_string_p
= false;
1547 chainsi
->endptr
= NULL_TREE
;
1548 chainsi
->dont_invalidate
= true;
1553 /* Try to detect overlap before returning. This catches cases
1554 like strcpy (d, d + n) where n is non-constant whose range
1555 is such that (n <= strlen (d) holds).
1557 OLDDSI->NONZERO_chars may have been reset by this point with
1558 oldlen holding it original value. */
1559 if (olddsi
&& oldlen
)
1561 /* Add 1 for the terminating NUL. */
1562 tree type
= TREE_TYPE (oldlen
);
1563 oldlen
= fold_build2 (PLUS_EXPR
, type
, oldlen
,
1564 build_int_cst (type
, 1));
1565 check_bounds_or_overlap (as_a
<gcall
*>(stmt
), olddsi
->ptr
, src
,
1574 tree adj
= NULL_TREE
;
1575 if (oldlen
== NULL_TREE
)
1577 else if (integer_zerop (oldlen
))
1579 else if (TREE_CODE (oldlen
) == INTEGER_CST
1580 || TREE_CODE (srclen
) == INTEGER_CST
)
1581 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1582 TREE_TYPE (srclen
), srclen
,
1583 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1585 if (adj
!= NULL_TREE
)
1586 adjust_related_strinfos (loc
, dsi
, adj
);
1590 /* strcpy src may not overlap dst, so src doesn't need to be
1591 invalidated either. */
1593 si
->dont_invalidate
= true;
1599 case BUILT_IN_STRCPY
:
1600 case BUILT_IN_STRCPY_CHKP
:
1601 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1603 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1605 case BUILT_IN_STRCPY_CHK
:
1606 case BUILT_IN_STRCPY_CHK_CHKP
:
1607 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1609 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1611 case BUILT_IN_STPCPY
:
1612 case BUILT_IN_STPCPY_CHKP
:
1613 /* This would need adjustment of the lhs (subtract one),
1614 or detection that the trailing '\0' doesn't need to be
1615 written, if it will be immediately overwritten.
1616 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1620 zsi
= zero_length_string (lhs
, dsi
);
1623 case BUILT_IN_STPCPY_CHK
:
1624 case BUILT_IN_STPCPY_CHK_CHKP
:
1625 /* This would need adjustment of the lhs (subtract one),
1626 or detection that the trailing '\0' doesn't need to be
1627 written, if it will be immediately overwritten.
1628 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1632 zsi
= zero_length_string (lhs
, dsi
);
1639 zsi
->dont_invalidate
= true;
1643 tree args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1644 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1647 type
= size_type_node
;
1649 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1650 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1652 /* Set the no-warning bit on the transformed statement? */
1653 bool set_no_warning
= false;
1655 if (const strinfo
*chksi
= olddsi
? olddsi
: dsi
)
1657 && !check_bounds_or_overlap (as_a
<gcall
*>(stmt
), chksi
->ptr
, si
->ptr
,
1660 gimple_set_no_warning (stmt
, true);
1661 set_no_warning
= true;
1664 if (fn
== NULL_TREE
)
1667 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1669 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1671 fprintf (dump_file
, "Optimizing: ");
1672 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1676 fn
= chkp_maybe_create_clone (fn
)->decl
;
1677 if (gimple_call_num_args (stmt
) == 4)
1678 success
= update_gimple_call (gsi
, fn
, 5, dst
,
1679 gimple_call_arg (stmt
, 1),
1681 gimple_call_arg (stmt
, 3),
1684 success
= update_gimple_call (gsi
, fn
, 6, dst
,
1685 gimple_call_arg (stmt
, 1),
1687 gimple_call_arg (stmt
, 3),
1689 gimple_call_arg (stmt
, 4));
1692 if (gimple_call_num_args (stmt
) == 2)
1693 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1695 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1696 gimple_call_arg (stmt
, 2));
1699 stmt
= gsi_stmt (*gsi
);
1700 gimple_call_set_with_bounds (stmt
, with_bounds
);
1702 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1704 fprintf (dump_file
, "into: ");
1705 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1707 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1708 laststmt
.stmt
= stmt
;
1709 laststmt
.len
= srclen
;
1710 laststmt
.stridx
= dsi
->idx
;
1712 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1713 fprintf (dump_file
, "not possible.\n");
1716 gimple_set_no_warning (stmt
, true);
1719 /* Check the size argument to the built-in forms of stpncpy and strncpy
1720 for out-of-bounds offsets or overlapping access, and to see if the
1721 size argument is derived from a call to strlen() on the source argument,
1722 and if so, issue an appropriate warning. */
1725 handle_builtin_strncat (built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1727 /* Same as stxncpy(). */
1728 handle_builtin_stxncpy (bcode
, gsi
);
1731 /* Return true if LEN depends on a call to strlen(SRC) in an interesting
1732 way. LEN can either be an integer expression, or a pointer (to char).
1733 When it is the latter (such as in recursive calls to self) is is
1734 assumed to be the argument in some call to strlen() whose relationship
1735 to SRC is being ascertained. */
1738 is_strlen_related_p (tree src
, tree len
)
1740 if (TREE_CODE (TREE_TYPE (len
)) == POINTER_TYPE
1741 && operand_equal_p (src
, len
, 0))
1744 if (TREE_CODE (len
) != SSA_NAME
)
1747 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1751 if (is_gimple_call (def_stmt
))
1753 tree func
= gimple_call_fndecl (def_stmt
);
1754 if (!valid_builtin_call (def_stmt
)
1755 || DECL_FUNCTION_CODE (func
) != BUILT_IN_STRLEN
)
1758 tree arg
= gimple_call_arg (def_stmt
, 0);
1759 return is_strlen_related_p (src
, arg
);
1762 if (!is_gimple_assign (def_stmt
))
1765 tree_code code
= gimple_assign_rhs_code (def_stmt
);
1766 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1767 tree rhstype
= TREE_TYPE (rhs1
);
1769 if ((TREE_CODE (rhstype
) == POINTER_TYPE
&& code
== POINTER_PLUS_EXPR
)
1770 || (INTEGRAL_TYPE_P (rhstype
)
1771 && (code
== BIT_AND_EXPR
1772 || code
== NOP_EXPR
)))
1774 /* Pointer plus (an integer) and integer cast or truncation are
1775 considered among the (potentially) related expressions to strlen.
1777 return is_strlen_related_p (src
, rhs1
);
1783 /* A helper of handle_builtin_stxncpy. Check to see if the specified
1784 bound is a) equal to the size of the destination DST and if so, b)
1785 if it's immediately followed by DST[CNT - 1] = '\0'. If a) holds
1786 and b) does not, warn. Otherwise, do nothing. Return true if
1787 diagnostic has been issued.
1789 The purpose is to diagnose calls to strncpy and stpncpy that do
1790 not nul-terminate the copy while allowing for the idiom where
1791 such a call is immediately followed by setting the last element
1794 strncpy (a, s, sizeof a);
1795 a[sizeof a - 1] = '\0';
1799 maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi
, tree src
, tree cnt
)
1801 gimple
*stmt
= gsi_stmt (gsi
);
1803 wide_int cntrange
[2];
1805 if (TREE_CODE (cnt
) == INTEGER_CST
)
1806 cntrange
[0] = cntrange
[1] = wi::to_wide (cnt
);
1807 else if (TREE_CODE (cnt
) == SSA_NAME
)
1809 enum value_range_type rng
= get_range_info (cnt
, cntrange
, cntrange
+ 1);
1810 if (rng
== VR_RANGE
)
1812 else if (rng
== VR_ANTI_RANGE
)
1814 wide_int maxobjsize
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
));
1816 if (wi::ltu_p (cntrange
[1], maxobjsize
))
1818 cntrange
[0] = cntrange
[1] + 1;
1819 cntrange
[1] = maxobjsize
;
1823 cntrange
[1] = cntrange
[0] - 1;
1824 cntrange
[0] = wi::zero (TYPE_PRECISION (TREE_TYPE (cnt
)));
1833 /* Negative value is the constant string length. If it's less than
1834 the lower bound there is no truncation. */
1835 int sidx
= get_stridx (src
);
1836 if (sidx
< 0 && wi::gtu_p (cntrange
[0], ~sidx
))
1839 tree dst
= gimple_call_arg (stmt
, 0);
1841 if (TREE_CODE (dstdecl
) == ADDR_EXPR
)
1842 dstdecl
= TREE_OPERAND (dstdecl
, 0);
1844 /* If the destination refers to a an array/pointer declared nonstring
1846 tree ref
= NULL_TREE
;
1847 if (get_attr_nonstring_decl (dstdecl
, &ref
))
1850 /* Look for dst[i] = '\0'; after the stxncpy() call and if found
1851 avoid the truncation warning. */
1852 gsi_next_nondebug (&gsi
);
1853 gimple
*next_stmt
= gsi_stmt (gsi
);
1855 if (!gsi_end_p (gsi
) && is_gimple_assign (next_stmt
))
1857 tree lhs
= gimple_assign_lhs (next_stmt
);
1858 tree_code code
= TREE_CODE (lhs
);
1859 if (code
== ARRAY_REF
|| code
== MEM_REF
)
1860 lhs
= TREE_OPERAND (lhs
, 0);
1862 tree func
= gimple_call_fndecl (stmt
);
1863 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STPNCPY
)
1865 tree ret
= gimple_call_lhs (stmt
);
1866 if (ret
&& operand_equal_p (ret
, lhs
, 0))
1870 /* Determine the base address and offset of the reference,
1871 ignoring the innermost array index. */
1872 if (TREE_CODE (ref
) == ARRAY_REF
)
1873 ref
= TREE_OPERAND (ref
, 0);
1876 tree dstbase
= get_addr_base_and_unit_offset (ref
, &dstoff
);
1879 tree lhsbase
= get_addr_base_and_unit_offset (lhs
, &lhsoff
);
1882 && known_eq (dstoff
, lhsoff
)
1883 && operand_equal_p (dstbase
, lhsbase
, 0))
1887 int prec
= TYPE_PRECISION (TREE_TYPE (cnt
));
1888 wide_int lenrange
[2];
1889 if (strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
)
1891 lenrange
[0] = (sisrc
->nonzero_chars
1892 && TREE_CODE (sisrc
->nonzero_chars
) == INTEGER_CST
1893 ? wi::to_wide (sisrc
->nonzero_chars
)
1895 lenrange
[1] = lenrange
[0];
1898 lenrange
[0] = lenrange
[1] = wi::shwi (~sidx
, prec
);
1902 get_range_strlen (src
, range
);
1903 if (range
[0] != NULL_TREE
1904 && TREE_CODE (range
[0]) == INTEGER_CST
1905 && range
[1] != NULL_TREE
1906 && TREE_CODE (range
[1]) == INTEGER_CST
)
1908 lenrange
[0] = wi::to_wide (range
[0], prec
);
1909 lenrange
[1] = wi::to_wide (range
[1], prec
);
1913 lenrange
[0] = wi::shwi (0, prec
);
1914 lenrange
[1] = wi::shwi (-1, prec
);
1918 location_t callloc
= gimple_location (stmt
);
1919 tree func
= gimple_call_fndecl (stmt
);
1921 if (lenrange
[0] != 0 || !wi::neg_p (lenrange
[1]))
1923 /* If the longest source string is shorter than the lower bound
1924 of the specified count the copy is definitely nul-terminated. */
1925 if (wi::ltu_p (lenrange
[1], cntrange
[0]))
1928 if (wi::neg_p (lenrange
[1]))
1930 /* The length of one of the strings is unknown but at least
1931 one has non-zero length and that length is stored in
1932 LENRANGE[1]. Swap the bounds to force a "may be truncated"
1934 lenrange
[1] = lenrange
[0];
1935 lenrange
[0] = wi::shwi (0, prec
);
1938 if (wi::geu_p (lenrange
[0], cntrange
[1]))
1940 /* The shortest string is longer than the upper bound of
1941 the count so the truncation is certain. */
1942 if (cntrange
[0] == cntrange
[1])
1943 return warning_at (callloc
, OPT_Wstringop_truncation
,
1945 ? G_("%qD output truncated copying %E byte "
1946 "from a string of length %wu")
1947 : G_("%qD output truncated copying %E bytes "
1948 "from a string of length %wu"),
1949 func
, cnt
, lenrange
[0].to_uhwi ());
1951 return warning_at (callloc
, OPT_Wstringop_truncation
,
1952 "%qD output truncated copying between %wu "
1953 "and %wu bytes from a string of length %wu",
1954 func
, cntrange
[0].to_uhwi (),
1955 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
1957 else if (wi::geu_p (lenrange
[1], cntrange
[1]))
1959 /* The longest string is longer than the upper bound of
1960 the count so the truncation is possible. */
1961 if (cntrange
[0] == cntrange
[1])
1962 return warning_at (callloc
, OPT_Wstringop_truncation
,
1964 ? G_("%qD output may be truncated copying %E "
1965 "byte from a string of length %wu")
1966 : G_("%qD output may be truncated copying %E "
1967 "bytes from a string of length %wu"),
1968 func
, cnt
, lenrange
[1].to_uhwi ());
1970 return warning_at (callloc
, OPT_Wstringop_truncation
,
1971 "%qD output may be truncated copying between %wu "
1972 "and %wu bytes from a string of length %wu",
1973 func
, cntrange
[0].to_uhwi (),
1974 cntrange
[1].to_uhwi (), lenrange
[1].to_uhwi ());
1977 if (cntrange
[0] != cntrange
[1]
1978 && wi::leu_p (cntrange
[0], lenrange
[0])
1979 && wi::leu_p (cntrange
[1], lenrange
[0] + 1))
1981 /* If the source (including the terminating nul) is longer than
1982 the lower bound of the specified count but shorter than the
1983 upper bound the copy may (but need not) be truncated. */
1984 return warning_at (callloc
, OPT_Wstringop_truncation
,
1985 "%qD output may be truncated copying between %wu "
1986 "and %wu bytes from a string of length %wu",
1987 func
, cntrange
[0].to_uhwi (),
1988 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
1992 if (tree dstsize
= compute_objsize (dst
, 1))
1994 /* The source length is uknown. Try to determine the destination
1995 size and see if it matches the specified bound. If not, bail.
1996 Otherwise go on to see if it should be diagnosed for possible
2001 if (wi::to_wide (dstsize
) != cntrange
[1])
2004 if (cntrange
[0] == cntrange
[1])
2005 return warning_at (callloc
, OPT_Wstringop_truncation
,
2006 "%qD specified bound %E equals destination size",
2013 /* Check the arguments to the built-in forms of stpncpy and strncpy for
2014 out-of-bounds offsets or overlapping access, and to see if the size
2015 is derived from calling strlen() on the source argument, and if so,
2016 issue the appropriate warning. */
2019 handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*gsi
)
2021 if (!strlen_to_stridx
)
2024 gimple
*stmt
= gsi_stmt (*gsi
);
2026 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
2028 tree dst
= gimple_call_arg (stmt
, with_bounds
? 1 : 0);
2029 tree src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
2030 tree len
= gimple_call_arg (stmt
, with_bounds
? 3 : 2);
2031 tree dstsize
= NULL_TREE
, srcsize
= NULL_TREE
;
2033 int didx
= get_stridx (dst
);
2034 if (strinfo
*sidst
= didx
> 0 ? get_strinfo (didx
) : NULL
)
2036 /* Compute the size of the destination string including the NUL. */
2037 if (sidst
->nonzero_chars
)
2039 tree type
= TREE_TYPE (sidst
->nonzero_chars
);
2040 dstsize
= fold_build2 (PLUS_EXPR
, type
, sidst
->nonzero_chars
,
2041 build_int_cst (type
, 1));
2046 int sidx
= get_stridx (src
);
2047 strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
;
2050 /* strncat() and strncpy() can modify the source string by writing
2051 over the terminating nul so SISRC->DONT_INVALIDATE must be left
2054 /* Compute the size of the source string including the NUL. */
2055 if (sisrc
->nonzero_chars
)
2057 tree type
= TREE_TYPE (sisrc
->nonzero_chars
);
2058 srcsize
= fold_build2 (PLUS_EXPR
, type
, sisrc
->nonzero_chars
,
2059 build_int_cst (type
, 1));
2065 srcsize
= NULL_TREE
;
2067 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, src
,
2070 gimple_set_no_warning (stmt
, true);
2074 /* If the length argument was computed from strlen(S) for some string
2075 S retrieve the strinfo index for the string (PSS->FIRST) alonng with
2076 the location of the strlen() call (PSS->SECOND). */
2077 stridx_strlenloc
*pss
= strlen_to_stridx
->get (len
);
2078 if (!pss
|| pss
->first
<= 0)
2080 if (maybe_diag_stxncpy_trunc (*gsi
, src
, len
))
2081 gimple_set_no_warning (stmt
, true);
2086 /* Retrieve the strinfo data for the string S that LEN was computed
2087 from as some function F of strlen (S) (i.e., LEN need not be equal
2089 strinfo
*silen
= get_strinfo (pss
->first
);
2091 location_t callloc
= gimple_location (stmt
);
2093 tree func
= gimple_call_fndecl (stmt
);
2095 bool warned
= false;
2097 /* When -Wstringop-truncation is set, try to determine truncation
2098 before diagnosing possible overflow. Truncation is implied by
2099 the LEN argument being equal to strlen(SRC), regardless of
2100 whether its value is known. Otherwise, issue the more generic
2101 -Wstringop-overflow which triggers for LEN arguments that in
2102 any meaningful way depend on strlen(SRC). */
2104 && is_strlen_related_p (src
, len
)
2105 && warning_at (callloc
, OPT_Wstringop_truncation
,
2106 "%qD output truncated before terminating nul "
2107 "copying as many bytes from a string as its length",
2110 else if (silen
&& is_strlen_related_p (src
, silen
->ptr
))
2111 warned
= warning_at (callloc
, OPT_Wstringop_overflow_
,
2112 "%qD specified bound depends on the length "
2113 "of the source argument", func
);
2116 location_t strlenloc
= pss
->second
;
2117 if (strlenloc
!= UNKNOWN_LOCATION
&& strlenloc
!= callloc
)
2118 inform (strlenloc
, "length computed here");
2122 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
2123 If strlen of the second argument is known and length of the third argument
2124 is that plus one, strlen of the first argument is the same after this
2128 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2131 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
2132 gimple
*stmt
= gsi_stmt (*gsi
);
2133 strinfo
*si
, *dsi
, *olddsi
;
2134 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
2136 len
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
2137 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
2138 dst
= gimple_call_arg (stmt
, 0);
2139 idx
= get_stridx (src
);
2143 didx
= get_stridx (dst
);
2146 olddsi
= get_strinfo (didx
);
2151 && tree_fits_uhwi_p (len
)
2152 && !integer_zerop (len
))
2153 adjust_last_stmt (olddsi
, stmt
, false);
2160 /* Handle memcpy (x, y, l) where l's relationship with strlen (y)
2162 si
= get_strinfo (idx
);
2163 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
2165 if (TREE_CODE (len
) == INTEGER_CST
2166 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
2168 if (tree_int_cst_le (len
, si
->nonzero_chars
))
2170 /* Copying LEN nonzero characters, where LEN is constant. */
2172 full_string_p
= false;
2176 /* Copying the whole of the analyzed part of SI. */
2177 newlen
= si
->nonzero_chars
;
2178 full_string_p
= si
->full_string_p
;
2183 if (!si
->full_string_p
)
2185 if (TREE_CODE (len
) != SSA_NAME
)
2187 def_stmt
= SSA_NAME_DEF_STMT (len
);
2188 if (!is_gimple_assign (def_stmt
)
2189 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
2190 || gimple_assign_rhs1 (def_stmt
) != si
->nonzero_chars
2191 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
2193 /* Copying variable-length string SI (and no more). */
2194 newlen
= si
->nonzero_chars
;
2195 full_string_p
= true;
2201 /* Handle memcpy (x, "abcd", 5) or
2202 memcpy (x, "abc\0uvw", 7). */
2203 if (!tree_fits_uhwi_p (len
))
2206 unsigned HOST_WIDE_INT clen
= tree_to_uhwi (len
);
2207 unsigned HOST_WIDE_INT nonzero_chars
= ~idx
;
2208 newlen
= build_int_cst (size_type_node
, MIN (nonzero_chars
, clen
));
2209 full_string_p
= clen
> nonzero_chars
;
2212 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
2213 adjust_last_stmt (olddsi
, stmt
, false);
2217 didx
= new_stridx (dst
);
2224 dsi
= unshare_strinfo (olddsi
);
2225 oldlen
= olddsi
->nonzero_chars
;
2226 dsi
->nonzero_chars
= newlen
;
2227 dsi
->full_string_p
= full_string_p
;
2228 /* Break the chain, so adjust_related_strinfo on later pointers in
2229 the chain won't adjust this one anymore. */
2232 dsi
->endptr
= NULL_TREE
;
2236 dsi
= new_strinfo (dst
, didx
, newlen
, full_string_p
);
2237 set_strinfo (didx
, dsi
);
2238 find_equal_ptrs (dst
, didx
);
2240 dsi
->writable
= true;
2241 dsi
->dont_invalidate
= true;
2244 tree adj
= NULL_TREE
;
2245 location_t loc
= gimple_location (stmt
);
2246 if (oldlen
== NULL_TREE
)
2248 else if (integer_zerop (oldlen
))
2250 else if (TREE_CODE (oldlen
) == INTEGER_CST
2251 || TREE_CODE (newlen
) == INTEGER_CST
)
2252 adj
= fold_build2_loc (loc
, MINUS_EXPR
, TREE_TYPE (newlen
), newlen
,
2253 fold_convert_loc (loc
, TREE_TYPE (newlen
),
2255 if (adj
!= NULL_TREE
)
2256 adjust_related_strinfos (loc
, dsi
, adj
);
2260 /* memcpy src may not overlap dst, so src doesn't need to be
2261 invalidated either. */
2263 si
->dont_invalidate
= true;
2267 lhs
= gimple_call_lhs (stmt
);
2270 case BUILT_IN_MEMCPY
:
2271 case BUILT_IN_MEMCPY_CHK
:
2272 case BUILT_IN_MEMCPY_CHKP
:
2273 case BUILT_IN_MEMCPY_CHK_CHKP
:
2274 /* Allow adjust_last_stmt to decrease this memcpy's size. */
2275 laststmt
.stmt
= stmt
;
2276 laststmt
.len
= dsi
->nonzero_chars
;
2277 laststmt
.stridx
= dsi
->idx
;
2279 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
2281 case BUILT_IN_MEMPCPY
:
2282 case BUILT_IN_MEMPCPY_CHK
:
2283 case BUILT_IN_MEMPCPY_CHKP
:
2284 case BUILT_IN_MEMPCPY_CHK_CHKP
:
2292 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
2293 If strlen of the second argument is known, strlen of the first argument
2294 is increased by the length of the second argument. Furthermore, attempt
2295 to convert it to memcpy/strcpy if the length of the first argument
2299 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2302 tree srclen
, args
, type
, fn
, objsz
, endptr
;
2304 gimple
*stmt
= gsi_stmt (*gsi
);
2306 location_t loc
= gimple_location (stmt
);
2307 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
2309 tree src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
2310 tree dst
= gimple_call_arg (stmt
, 0);
2312 /* Bail if the source is the same as destination. It will be diagnosed
2314 if (operand_equal_p (src
, dst
, 0))
2317 tree lhs
= gimple_call_lhs (stmt
);
2319 didx
= get_stridx (dst
);
2325 dsi
= get_strinfo (didx
);
2329 idx
= get_stridx (src
);
2331 srclen
= build_int_cst (size_type_node
, ~idx
);
2334 si
= get_strinfo (idx
);
2336 srclen
= get_string_length (si
);
2339 /* Set the no-warning bit on the transformed statement? */
2340 bool set_no_warning
= false;
2342 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
2345 /* The concatenation always involves copying at least one byte
2346 (the terminating nul), even if the source string is empty.
2347 If the source is unknown assume it's one character long and
2348 used that as both sizes. */
2352 tree type
= TREE_TYPE (slen
);
2353 slen
= fold_build2 (PLUS_EXPR
, type
, slen
, build_int_cst (type
, 1));
2356 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2358 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, sptr
,
2361 gimple_set_no_warning (stmt
, true);
2362 set_no_warning
= true;
2366 /* strcat (p, q) can be transformed into
2367 tmp = p + strlen (p); endptr = stpcpy (tmp, q);
2368 with length endptr - p if we need to compute the length
2369 later on. Don't do this transformation if we don't need
2371 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
2375 didx
= new_stridx (dst
);
2381 dsi
= new_strinfo (dst
, didx
, NULL_TREE
, false);
2382 set_strinfo (didx
, dsi
);
2383 find_equal_ptrs (dst
, didx
);
2387 dsi
= unshare_strinfo (dsi
);
2388 dsi
->nonzero_chars
= NULL_TREE
;
2389 dsi
->full_string_p
= false;
2391 dsi
->endptr
= NULL_TREE
;
2393 dsi
->writable
= true;
2395 dsi
->dont_invalidate
= true;
2400 tree dstlen
= dsi
->nonzero_chars
;
2401 endptr
= dsi
->endptr
;
2403 dsi
= unshare_strinfo (dsi
);
2404 dsi
->endptr
= NULL_TREE
;
2406 dsi
->writable
= true;
2408 if (srclen
!= NULL_TREE
)
2410 dsi
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
2411 TREE_TYPE (dsi
->nonzero_chars
),
2412 dsi
->nonzero_chars
, srclen
);
2413 gcc_assert (dsi
->full_string_p
);
2414 adjust_related_strinfos (loc
, dsi
, srclen
);
2415 dsi
->dont_invalidate
= true;
2419 dsi
->nonzero_chars
= NULL
;
2420 dsi
->full_string_p
= false;
2421 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
2422 dsi
->dont_invalidate
= true;
2426 /* strcat src may not overlap dst, so src doesn't need to be
2427 invalidated either. */
2428 si
->dont_invalidate
= true;
2430 /* For now. Could remove the lhs from the call and add
2431 lhs = dst; afterwards. */
2439 case BUILT_IN_STRCAT
:
2440 case BUILT_IN_STRCAT_CHKP
:
2441 if (srclen
!= NULL_TREE
)
2442 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
2444 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
2446 case BUILT_IN_STRCAT_CHK
:
2447 case BUILT_IN_STRCAT_CHK_CHKP
:
2448 if (srclen
!= NULL_TREE
)
2449 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
2451 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
2452 objsz
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
2458 if (fn
== NULL_TREE
)
2463 tree type
= TREE_TYPE (dstlen
);
2465 /* Compute the size of the source sequence, including the nul. */
2466 tree srcsize
= srclen
? srclen
: size_zero_node
;
2467 srcsize
= fold_build2 (PLUS_EXPR
, type
, srcsize
, build_int_cst (type
, 1));
2469 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2471 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, sptr
,
2474 gimple_set_no_warning (stmt
, true);
2475 set_no_warning
= true;
2479 tree len
= NULL_TREE
;
2480 if (srclen
!= NULL_TREE
)
2482 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
2483 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
2485 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
2486 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
2487 build_int_cst (type
, 1));
2488 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
2492 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
2494 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
2495 TREE_TYPE (dst
), unshare_expr (dst
),
2496 fold_convert_loc (loc
, sizetype
,
2497 unshare_expr (dstlen
)));
2498 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
2500 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2502 fprintf (dump_file
, "Optimizing: ");
2503 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2507 fn
= chkp_maybe_create_clone (fn
)->decl
;
2508 if (srclen
!= NULL_TREE
)
2509 success
= update_gimple_call (gsi
, fn
, 5 + (objsz
!= NULL_TREE
),
2511 gimple_call_arg (stmt
, 1),
2513 gimple_call_arg (stmt
, 3),
2516 success
= update_gimple_call (gsi
, fn
, 4 + (objsz
!= NULL_TREE
),
2518 gimple_call_arg (stmt
, 1),
2520 gimple_call_arg (stmt
, 3),
2524 if (srclen
!= NULL_TREE
)
2525 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
2526 dst
, src
, len
, objsz
);
2528 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
2532 stmt
= gsi_stmt (*gsi
);
2533 gimple_call_set_with_bounds (stmt
, with_bounds
);
2535 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2537 fprintf (dump_file
, "into: ");
2538 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2540 /* If srclen == NULL, note that current string length can be
2541 computed by transforming this strcpy into stpcpy. */
2542 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
2544 adjust_last_stmt (dsi
, stmt
, true);
2545 if (srclen
!= NULL_TREE
)
2547 laststmt
.stmt
= stmt
;
2548 laststmt
.len
= srclen
;
2549 laststmt
.stridx
= dsi
->idx
;
2552 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2553 fprintf (dump_file
, "not possible.\n");
2556 gimple_set_no_warning (stmt
, true);
2559 /* Handle a call to malloc or calloc. */
2562 handle_builtin_malloc (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2564 gimple
*stmt
= gsi_stmt (*gsi
);
2565 tree lhs
= gimple_call_lhs (stmt
);
2566 if (lhs
== NULL_TREE
)
2569 gcc_assert (get_stridx (lhs
) == 0);
2570 int idx
= new_stridx (lhs
);
2571 tree length
= NULL_TREE
;
2572 if (bcode
== BUILT_IN_CALLOC
)
2573 length
= build_int_cst (size_type_node
, 0);
2574 strinfo
*si
= new_strinfo (lhs
, idx
, length
, length
!= NULL_TREE
);
2575 if (bcode
== BUILT_IN_CALLOC
)
2577 set_strinfo (idx
, si
);
2578 si
->writable
= true;
2580 si
->dont_invalidate
= true;
2583 /* Handle a call to memset.
2584 After a call to calloc, memset(,0,) is unnecessary.
2585 memset(malloc(n),0,n) is calloc(n,1). */
2588 handle_builtin_memset (gimple_stmt_iterator
*gsi
)
2590 gimple
*stmt2
= gsi_stmt (*gsi
);
2591 if (!integer_zerop (gimple_call_arg (stmt2
, 1)))
2593 tree ptr
= gimple_call_arg (stmt2
, 0);
2594 int idx1
= get_stridx (ptr
);
2597 strinfo
*si1
= get_strinfo (idx1
);
2600 gimple
*stmt1
= si1
->stmt
;
2601 if (!stmt1
|| !is_gimple_call (stmt1
))
2603 tree callee1
= gimple_call_fndecl (stmt1
);
2604 if (!valid_builtin_call (stmt1
))
2606 enum built_in_function code1
= DECL_FUNCTION_CODE (callee1
);
2607 tree size
= gimple_call_arg (stmt2
, 2);
2608 if (code1
== BUILT_IN_CALLOC
)
2609 /* Not touching stmt1 */ ;
2610 else if (code1
== BUILT_IN_MALLOC
2611 && operand_equal_p (gimple_call_arg (stmt1
, 0), size
, 0))
2613 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt1
);
2614 update_gimple_call (&gsi1
, builtin_decl_implicit (BUILT_IN_CALLOC
), 2,
2615 size
, build_one_cst (size_type_node
));
2616 si1
->nonzero_chars
= build_int_cst (size_type_node
, 0);
2617 si1
->full_string_p
= true;
2618 si1
->stmt
= gsi_stmt (gsi1
);
2622 tree lhs
= gimple_call_lhs (stmt2
);
2623 unlink_stmt_vdef (stmt2
);
2626 gimple
*assign
= gimple_build_assign (lhs
, ptr
);
2627 gsi_replace (gsi
, assign
, false);
2631 gsi_remove (gsi
, true);
2632 release_defs (stmt2
);
2638 /* Handle a call to memcmp. We try to handle small comparisons by
2639 converting them to load and compare, and replacing the call to memcmp
2640 with a __builtin_memcmp_eq call where possible. */
2643 handle_builtin_memcmp (gimple_stmt_iterator
*gsi
)
2645 gcall
*stmt2
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2646 tree res
= gimple_call_lhs (stmt2
);
2647 tree arg1
= gimple_call_arg (stmt2
, 0);
2648 tree arg2
= gimple_call_arg (stmt2
, 1);
2649 tree len
= gimple_call_arg (stmt2
, 2);
2650 unsigned HOST_WIDE_INT leni
;
2651 use_operand_p use_p
;
2652 imm_use_iterator iter
;
2657 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
2659 gimple
*ustmt
= USE_STMT (use_p
);
2661 if (is_gimple_debug (ustmt
))
2663 if (gimple_code (ustmt
) == GIMPLE_ASSIGN
)
2665 gassign
*asgn
= as_a
<gassign
*> (ustmt
);
2666 tree_code code
= gimple_assign_rhs_code (asgn
);
2667 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2668 || !integer_zerop (gimple_assign_rhs2 (asgn
)))
2671 else if (gimple_code (ustmt
) == GIMPLE_COND
)
2673 tree_code code
= gimple_cond_code (ustmt
);
2674 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2675 || !integer_zerop (gimple_cond_rhs (ustmt
)))
2682 if (tree_fits_uhwi_p (len
)
2683 && (leni
= tree_to_uhwi (len
)) <= GET_MODE_SIZE (word_mode
)
2684 && pow2p_hwi (leni
))
2686 leni
*= CHAR_TYPE_SIZE
;
2687 unsigned align1
= get_pointer_alignment (arg1
);
2688 unsigned align2
= get_pointer_alignment (arg2
);
2689 unsigned align
= MIN (align1
, align2
);
2690 scalar_int_mode mode
;
2691 if (int_mode_for_size (leni
, 1).exists (&mode
)
2692 && (align
>= leni
|| !targetm
.slow_unaligned_access (mode
, align
)))
2694 location_t loc
= gimple_location (stmt2
);
2696 type
= build_nonstandard_integer_type (leni
, 1);
2697 gcc_assert (known_eq (GET_MODE_BITSIZE (TYPE_MODE (type
)), leni
));
2698 tree ptrtype
= build_pointer_type_for_mode (char_type_node
,
2700 off
= build_int_cst (ptrtype
, 0);
2701 arg1
= build2_loc (loc
, MEM_REF
, type
, arg1
, off
);
2702 arg2
= build2_loc (loc
, MEM_REF
, type
, arg2
, off
);
2703 tree tem1
= fold_const_aggregate_ref (arg1
);
2706 tree tem2
= fold_const_aggregate_ref (arg2
);
2709 res
= fold_convert_loc (loc
, TREE_TYPE (res
),
2710 fold_build2_loc (loc
, NE_EXPR
,
2713 gimplify_and_update_call_from_tree (gsi
, res
);
2718 gimple_call_set_fndecl (stmt2
, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ
));
2722 /* Handle a POINTER_PLUS_EXPR statement.
2723 For p = "abcd" + 2; compute associated length, or if
2724 p = q + off is pointing to a '\0' character of a string, call
2725 zero_length_string on it. */
2728 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
2730 gimple
*stmt
= gsi_stmt (*gsi
);
2731 tree lhs
= gimple_assign_lhs (stmt
), off
;
2732 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
2740 tree off
= gimple_assign_rhs2 (stmt
);
2741 if (tree_fits_uhwi_p (off
)
2742 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
2743 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
2744 = ~(~idx
- (int) tree_to_uhwi (off
));
2748 si
= get_strinfo (idx
);
2749 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
2752 off
= gimple_assign_rhs2 (stmt
);
2754 if (si
->full_string_p
&& operand_equal_p (si
->nonzero_chars
, off
, 0))
2755 zsi
= zero_length_string (lhs
, si
);
2756 else if (TREE_CODE (off
) == SSA_NAME
)
2758 gimple
*def_stmt
= SSA_NAME_DEF_STMT (off
);
2759 if (gimple_assign_single_p (def_stmt
)
2760 && si
->full_string_p
2761 && operand_equal_p (si
->nonzero_chars
,
2762 gimple_assign_rhs1 (def_stmt
), 0))
2763 zsi
= zero_length_string (lhs
, si
);
2766 && si
->endptr
!= NULL_TREE
2767 && si
->endptr
!= lhs
2768 && TREE_CODE (si
->endptr
) == SSA_NAME
)
2770 enum tree_code rhs_code
2771 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
2772 ? SSA_NAME
: NOP_EXPR
;
2773 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
);
2774 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2779 /* If RHS, either directly or indirectly, refers to a string of constant
2780 length, return it. Otherwise return a negative value. */
2782 static HOST_WIDE_INT
2783 get_string_cst_length (tree rhs
)
2785 if (TREE_CODE (rhs
) == MEM_REF
2786 && integer_zerop (TREE_OPERAND (rhs
, 1)))
2788 rhs
= TREE_OPERAND (rhs
, 0);
2789 if (TREE_CODE (rhs
) == ADDR_EXPR
)
2791 tree rhs_addr
= rhs
;
2793 rhs
= TREE_OPERAND (rhs
, 0);
2794 if (TREE_CODE (rhs
) != STRING_CST
)
2796 int idx
= get_stridx (rhs_addr
);
2799 strinfo
*si
= get_strinfo (idx
);
2801 && si
->full_string_p
2802 && tree_fits_shwi_p (si
->nonzero_chars
))
2803 return tree_to_shwi (si
->nonzero_chars
);
2809 if (TREE_CODE (rhs
) == VAR_DECL
2810 && TREE_READONLY (rhs
))
2811 rhs
= DECL_INITIAL (rhs
);
2813 if (rhs
&& TREE_CODE (rhs
) == STRING_CST
)
2814 return strlen (TREE_STRING_POINTER (rhs
));
2819 /* Handle a single character store. */
2822 handle_char_store (gimple_stmt_iterator
*gsi
)
2826 gimple
*stmt
= gsi_stmt (*gsi
);
2827 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
2828 tree rhs
= gimple_assign_rhs1 (stmt
);
2829 unsigned HOST_WIDE_INT offset
= 0;
2831 if (TREE_CODE (lhs
) == MEM_REF
2832 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
2834 tree mem_offset
= TREE_OPERAND (lhs
, 1);
2835 if (tree_fits_uhwi_p (mem_offset
))
2837 /* Get the strinfo for the base, and use it if it starts with at
2838 least OFFSET nonzero characters. This is trivially true if
2840 offset
= tree_to_uhwi (mem_offset
);
2841 idx
= get_stridx (TREE_OPERAND (lhs
, 0));
2843 si
= get_strinfo (idx
);
2845 ssaname
= TREE_OPERAND (lhs
, 0);
2846 else if (si
== NULL
|| compare_nonzero_chars (si
, offset
) < 0)
2852 idx
= get_addr_stridx (lhs
, NULL_TREE
, &offset
);
2854 si
= get_strinfo (idx
);
2857 bool storing_zero_p
= initializer_zerop (rhs
);
2858 bool storing_nonzero_p
= (!storing_zero_p
2859 && TREE_CODE (rhs
) == INTEGER_CST
2860 && integer_nonzerop (rhs
));
2861 /* Set to the length of the string being assigned if known. */
2862 HOST_WIDE_INT rhslen
;
2866 int cmp
= compare_nonzero_chars (si
, offset
);
2867 gcc_assert (offset
== 0 || cmp
>= 0);
2868 if (storing_zero_p
&& cmp
== 0 && si
->full_string_p
)
2870 /* When overwriting a '\0' with a '\0', the store can be removed
2871 if we know it has been stored in the current function. */
2872 if (!stmt_could_throw_p (stmt
) && si
->writable
)
2874 unlink_stmt_vdef (stmt
);
2875 release_defs (stmt
);
2876 gsi_remove (gsi
, true);
2881 si
->writable
= true;
2886 /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0',
2887 and if we aren't storing '\0', we know that the length of the
2888 string and any other zero terminated string in memory remains
2889 the same. In that case we move to the next gimple statement and
2890 return to signal the caller that it shouldn't invalidate anything.
2892 This is benefical for cases like:
2897 strcpy (p, "foobar");
2898 size_t len = strlen (p); // This can be optimized into 6
2899 size_t len2 = strlen (q); // This has to be computed
2901 size_t len3 = strlen (p); // This can be optimized into 6
2902 size_t len4 = strlen (q); // This can be optimized into len2
2903 bar (len, len2, len3, len4);
2906 else if (storing_nonzero_p
&& cmp
> 0)
2911 else if (storing_zero_p
|| storing_nonzero_p
|| (offset
!= 0 && cmp
> 0))
2913 /* When storing_nonzero_p, we know that the string now starts
2914 with OFFSET + 1 nonzero characters, but don't know whether
2915 there's a following nul terminator.
2917 When storing_zero_p, we know that the string is now OFFSET
2920 Otherwise, we're storing an unknown value at offset OFFSET,
2921 so need to clip the nonzero_chars to OFFSET. */
2922 location_t loc
= gimple_location (stmt
);
2923 tree oldlen
= si
->nonzero_chars
;
2924 if (cmp
== 0 && si
->full_string_p
)
2925 /* We're overwriting the nul terminator with a nonzero or
2926 unknown character. If the previous stmt was a memcpy,
2927 its length may be decreased. */
2928 adjust_last_stmt (si
, stmt
, false);
2929 si
= unshare_strinfo (si
);
2930 if (storing_nonzero_p
)
2931 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
+ 1);
2933 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
);
2934 si
->full_string_p
= storing_zero_p
;
2937 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
2938 si
->endptr
= ssaname
;
2943 si
->writable
= true;
2944 si
->dont_invalidate
= true;
2947 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
2948 si
->nonzero_chars
, oldlen
);
2949 adjust_related_strinfos (loc
, si
, adj
);
2955 else if (idx
== 0 && (storing_zero_p
|| storing_nonzero_p
))
2958 idx
= new_stridx (ssaname
);
2960 idx
= new_addr_stridx (lhs
);
2963 tree ptr
= (ssaname
? ssaname
: build_fold_addr_expr (lhs
));
2964 tree len
= storing_nonzero_p
? size_one_node
: size_zero_node
;
2965 si
= new_strinfo (ptr
, idx
, len
, storing_zero_p
);
2966 set_strinfo (idx
, si
);
2969 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
2970 si
->endptr
= ssaname
;
2971 si
->dont_invalidate
= true;
2972 si
->writable
= true;
2976 && (rhslen
= get_string_cst_length (gimple_assign_rhs1 (stmt
))) >= 0
2977 && ssaname
== NULL_TREE
2978 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
2980 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
2981 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> (unsigned HOST_WIDE_INT
) rhslen
)
2983 int idx
= new_addr_stridx (lhs
);
2986 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
2987 build_int_cst (size_type_node
, rhslen
), true);
2988 set_strinfo (idx
, si
);
2989 si
->dont_invalidate
= true;
2994 if (si
!= NULL
&& offset
== 0 && storing_zero_p
)
2996 /* Allow adjust_last_stmt to remove it if the stored '\0'
2997 is immediately overwritten. */
2998 laststmt
.stmt
= stmt
;
2999 laststmt
.len
= build_int_cst (size_type_node
, 1);
3000 laststmt
.stridx
= si
->idx
;
3005 /* Try to fold strstr (s, t) eq/ne s to strncmp (s, t, strlen (t)) eq/ne 0. */
3008 fold_strstr_to_strncmp (tree rhs1
, tree rhs2
, gimple
*stmt
)
3010 if (TREE_CODE (rhs1
) != SSA_NAME
3011 || TREE_CODE (rhs2
) != SSA_NAME
)
3014 gimple
*call_stmt
= NULL
;
3015 for (int pass
= 0; pass
< 2; pass
++)
3017 gimple
*g
= SSA_NAME_DEF_STMT (rhs1
);
3018 if (gimple_call_builtin_p (g
, BUILT_IN_STRSTR
)
3019 && has_single_use (rhs1
)
3020 && gimple_call_arg (g
, 0) == rhs2
)
3025 std::swap (rhs1
, rhs2
);
3030 tree arg0
= gimple_call_arg (call_stmt
, 0);
3034 tree arg1
= gimple_call_arg (call_stmt
, 1);
3035 tree arg1_len
= NULL_TREE
;
3036 int idx
= get_stridx (arg1
);
3041 arg1_len
= build_int_cst (size_type_node
, ~idx
);
3044 strinfo
*si
= get_strinfo (idx
);
3046 arg1_len
= get_string_length (si
);
3050 if (arg1_len
!= NULL_TREE
)
3052 gimple_stmt_iterator gsi
= gsi_for_stmt (call_stmt
);
3053 tree strncmp_decl
= builtin_decl_explicit (BUILT_IN_STRNCMP
);
3055 if (!is_gimple_val (arg1_len
))
3057 tree arg1_len_tmp
= make_ssa_name (TREE_TYPE (arg1_len
));
3058 gassign
*arg1_stmt
= gimple_build_assign (arg1_len_tmp
,
3060 gsi_insert_before (&gsi
, arg1_stmt
, GSI_SAME_STMT
);
3061 arg1_len
= arg1_len_tmp
;
3064 gcall
*strncmp_call
= gimple_build_call (strncmp_decl
, 3,
3065 arg0
, arg1
, arg1_len
);
3066 tree strncmp_lhs
= make_ssa_name (integer_type_node
);
3067 gimple_set_vuse (strncmp_call
, gimple_vuse (call_stmt
));
3068 gimple_call_set_lhs (strncmp_call
, strncmp_lhs
);
3069 gsi_remove (&gsi
, true);
3070 gsi_insert_before (&gsi
, strncmp_call
, GSI_SAME_STMT
);
3071 tree zero
= build_zero_cst (TREE_TYPE (strncmp_lhs
));
3073 if (is_gimple_assign (stmt
))
3075 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
3077 tree cond
= gimple_assign_rhs1 (stmt
);
3078 TREE_OPERAND (cond
, 0) = strncmp_lhs
;
3079 TREE_OPERAND (cond
, 1) = zero
;
3083 gimple_assign_set_rhs1 (stmt
, strncmp_lhs
);
3084 gimple_assign_set_rhs2 (stmt
, zero
);
3089 gcond
*cond
= as_a
<gcond
*> (stmt
);
3090 gimple_cond_set_lhs (cond
, strncmp_lhs
);
3091 gimple_cond_set_rhs (cond
, zero
);
3099 /* Attempt to check for validity of the performed access a single statement
3100 at *GSI using string length knowledge, and to optimize it.
3101 If the given basic block needs clean-up of EH, CLEANUP_EH is set to
3105 strlen_check_and_optimize_stmt (gimple_stmt_iterator
*gsi
, bool *cleanup_eh
)
3107 gimple
*stmt
= gsi_stmt (*gsi
);
3109 if (is_gimple_call (stmt
))
3111 tree callee
= gimple_call_fndecl (stmt
);
3112 if (valid_builtin_call (stmt
))
3113 switch (DECL_FUNCTION_CODE (callee
))
3115 case BUILT_IN_STRLEN
:
3116 case BUILT_IN_STRLEN_CHKP
:
3117 handle_builtin_strlen (gsi
);
3119 case BUILT_IN_STRCHR
:
3120 case BUILT_IN_STRCHR_CHKP
:
3121 handle_builtin_strchr (gsi
);
3123 case BUILT_IN_STRCPY
:
3124 case BUILT_IN_STRCPY_CHK
:
3125 case BUILT_IN_STPCPY
:
3126 case BUILT_IN_STPCPY_CHK
:
3127 case BUILT_IN_STRCPY_CHKP
:
3128 case BUILT_IN_STRCPY_CHK_CHKP
:
3129 case BUILT_IN_STPCPY_CHKP
:
3130 case BUILT_IN_STPCPY_CHK_CHKP
:
3131 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3134 case BUILT_IN_STRNCAT
:
3135 case BUILT_IN_STRNCAT_CHK
:
3136 handle_builtin_strncat (DECL_FUNCTION_CODE (callee
), gsi
);
3139 case BUILT_IN_STPNCPY
:
3140 case BUILT_IN_STPNCPY_CHK
:
3141 case BUILT_IN_STRNCPY
:
3142 case BUILT_IN_STRNCPY_CHK
:
3143 handle_builtin_stxncpy (DECL_FUNCTION_CODE (callee
), gsi
);
3146 case BUILT_IN_MEMCPY
:
3147 case BUILT_IN_MEMCPY_CHK
:
3148 case BUILT_IN_MEMPCPY
:
3149 case BUILT_IN_MEMPCPY_CHK
:
3150 case BUILT_IN_MEMCPY_CHKP
:
3151 case BUILT_IN_MEMCPY_CHK_CHKP
:
3152 case BUILT_IN_MEMPCPY_CHKP
:
3153 case BUILT_IN_MEMPCPY_CHK_CHKP
:
3154 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3156 case BUILT_IN_STRCAT
:
3157 case BUILT_IN_STRCAT_CHK
:
3158 case BUILT_IN_STRCAT_CHKP
:
3159 case BUILT_IN_STRCAT_CHK_CHKP
:
3160 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
3162 case BUILT_IN_MALLOC
:
3163 case BUILT_IN_CALLOC
:
3164 handle_builtin_malloc (DECL_FUNCTION_CODE (callee
), gsi
);
3166 case BUILT_IN_MEMSET
:
3167 if (!handle_builtin_memset (gsi
))
3170 case BUILT_IN_MEMCMP
:
3171 if (!handle_builtin_memcmp (gsi
))
3178 else if (is_gimple_assign (stmt
) && !gimple_clobber_p (stmt
))
3180 tree lhs
= gimple_assign_lhs (stmt
);
3182 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
3184 if (gimple_assign_single_p (stmt
)
3185 || (gimple_assign_cast_p (stmt
)
3186 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
3188 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
3189 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
3191 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
3192 handle_pointer_plus (gsi
);
3194 else if (TREE_CODE (lhs
) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
3196 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3197 if (code
== COND_EXPR
)
3199 tree cond
= gimple_assign_rhs1 (stmt
);
3200 enum tree_code cond_code
= TREE_CODE (cond
);
3202 if (cond_code
== EQ_EXPR
|| cond_code
== NE_EXPR
)
3203 fold_strstr_to_strncmp (TREE_OPERAND (cond
, 0),
3204 TREE_OPERAND (cond
, 1), stmt
);
3206 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3207 fold_strstr_to_strncmp (gimple_assign_rhs1 (stmt
),
3208 gimple_assign_rhs2 (stmt
), stmt
);
3209 else if (gimple_assign_load_p (stmt
)
3210 && TREE_CODE (TREE_TYPE (lhs
)) == INTEGER_TYPE
3211 && TYPE_MODE (TREE_TYPE (lhs
)) == TYPE_MODE (char_type_node
)
3212 && (TYPE_PRECISION (TREE_TYPE (lhs
))
3213 == TYPE_PRECISION (char_type_node
))
3214 && !gimple_has_volatile_ops (stmt
))
3216 tree off
= integer_zero_node
;
3217 unsigned HOST_WIDE_INT coff
= 0;
3219 tree rhs1
= gimple_assign_rhs1 (stmt
);
3220 if (code
== MEM_REF
)
3222 idx
= get_stridx (TREE_OPERAND (rhs1
, 0));
3225 strinfo
*si
= get_strinfo (idx
);
3227 && si
->nonzero_chars
3228 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
3229 && (wi::to_widest (si
->nonzero_chars
)
3230 >= wi::to_widest (off
)))
3231 off
= TREE_OPERAND (rhs1
, 1);
3233 /* This case is not useful. See if get_addr_stridx
3234 returns something usable. */
3239 idx
= get_addr_stridx (rhs1
, NULL_TREE
, &coff
);
3242 strinfo
*si
= get_strinfo (idx
);
3244 && si
->nonzero_chars
3245 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
3247 widest_int w1
= wi::to_widest (si
->nonzero_chars
);
3248 widest_int w2
= wi::to_widest (off
) + coff
;
3250 && si
->full_string_p
)
3252 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3254 fprintf (dump_file
, "Optimizing: ");
3255 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3258 /* Reading the final '\0' character. */
3259 tree zero
= build_int_cst (TREE_TYPE (lhs
), 0);
3260 gimple_set_vuse (stmt
, NULL_TREE
);
3261 gimple_assign_set_rhs_from_tree (gsi
, zero
);
3263 |= maybe_clean_or_replace_eh_stmt (stmt
,
3265 stmt
= gsi_stmt (*gsi
);
3268 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3270 fprintf (dump_file
, "into: ");
3271 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3276 /* Reading a character before the final '\0'
3277 character. Just set the value range to ~[0, 0]
3278 if we don't have anything better. */
3280 tree type
= TREE_TYPE (lhs
);
3281 enum value_range_type vr
3282 = get_range_info (lhs
, &min
, &max
);
3283 if (vr
== VR_VARYING
3285 && min
== wi::min_value (TYPE_PRECISION (type
),
3287 && max
== wi::max_value (TYPE_PRECISION (type
),
3289 set_range_info (lhs
, VR_ANTI_RANGE
,
3290 wi::zero (TYPE_PRECISION (type
)),
3291 wi::zero (TYPE_PRECISION (type
)));
3297 if (strlen_to_stridx
)
3299 tree rhs1
= gimple_assign_rhs1 (stmt
);
3300 if (stridx_strlenloc
*ps
= strlen_to_stridx
->get (rhs1
))
3301 strlen_to_stridx
->put (lhs
, stridx_strlenloc (*ps
));
3304 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
3306 tree type
= TREE_TYPE (lhs
);
3307 if (TREE_CODE (type
) == ARRAY_TYPE
)
3308 type
= TREE_TYPE (type
);
3309 if (TREE_CODE (type
) == INTEGER_TYPE
3310 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
3311 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
3313 if (! handle_char_store (gsi
))
3318 else if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
3320 enum tree_code code
= gimple_cond_code (cond
);
3321 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3322 fold_strstr_to_strncmp (gimple_cond_lhs (stmt
),
3323 gimple_cond_rhs (stmt
), stmt
);
3326 if (gimple_vdef (stmt
))
3327 maybe_invalidate (stmt
);
3331 /* Recursively call maybe_invalidate on stmts that might be executed
3332 in between dombb and current bb and that contain a vdef. Stop when
3333 *count stmts are inspected, or if the whole strinfo vector has
3334 been invalidated. */
3337 do_invalidate (basic_block dombb
, gimple
*phi
, bitmap visited
, int *count
)
3339 unsigned int i
, n
= gimple_phi_num_args (phi
);
3341 for (i
= 0; i
< n
; i
++)
3343 tree vuse
= gimple_phi_arg_def (phi
, i
);
3344 gimple
*stmt
= SSA_NAME_DEF_STMT (vuse
);
3345 basic_block bb
= gimple_bb (stmt
);
3348 || !bitmap_set_bit (visited
, bb
->index
)
3349 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3353 if (gimple_code (stmt
) == GIMPLE_PHI
)
3355 do_invalidate (dombb
, stmt
, visited
, count
);
3362 if (!maybe_invalidate (stmt
))
3367 vuse
= gimple_vuse (stmt
);
3368 stmt
= SSA_NAME_DEF_STMT (vuse
);
3369 if (gimple_bb (stmt
) != bb
)
3371 bb
= gimple_bb (stmt
);
3374 || !bitmap_set_bit (visited
, bb
->index
)
3375 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3382 class strlen_dom_walker
: public dom_walker
3385 strlen_dom_walker (cdi_direction direction
)
3386 : dom_walker (direction
), m_cleanup_cfg (false)
3389 virtual edge
before_dom_children (basic_block
);
3390 virtual void after_dom_children (basic_block
);
3392 /* Flag that will trigger TODO_cleanup_cfg to be returned in strlen
3393 execute function. */
3397 /* Callback for walk_dominator_tree. Attempt to optimize various
3398 string ops by remembering string lengths pointed by pointer SSA_NAMEs. */
3401 strlen_dom_walker::before_dom_children (basic_block bb
)
3403 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
3406 stridx_to_strinfo
= NULL
;
3409 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) dombb
->aux
);
3410 if (stridx_to_strinfo
)
3412 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3415 gphi
*phi
= gsi
.phi ();
3416 if (virtual_operand_p (gimple_phi_result (phi
)))
3418 bitmap visited
= BITMAP_ALLOC (NULL
);
3419 int count_vdef
= 100;
3420 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
3421 BITMAP_FREE (visited
);
3422 if (count_vdef
== 0)
3424 /* If there were too many vdefs in between immediate
3425 dominator and current bb, invalidate everything.
3426 If stridx_to_strinfo has been unshared, we need
3427 to free it, otherwise just set it to NULL. */
3428 if (!strinfo_shared ())
3434 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
3438 (*stridx_to_strinfo
)[i
] = NULL
;
3442 stridx_to_strinfo
= NULL
;
3450 /* If all PHI arguments have the same string index, the PHI result
3452 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3455 gphi
*phi
= gsi
.phi ();
3456 tree result
= gimple_phi_result (phi
);
3457 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
3459 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
3462 unsigned int i
, n
= gimple_phi_num_args (phi
);
3463 for (i
= 1; i
< n
; i
++)
3464 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
3467 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
3472 bool cleanup_eh
= false;
3474 /* Attempt to optimize individual statements. */
3475 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
3476 if (strlen_check_and_optimize_stmt (&gsi
, &cleanup_eh
))
3479 if (cleanup_eh
&& gimple_purge_dead_eh_edges (bb
))
3480 m_cleanup_cfg
= true;
3482 bb
->aux
= stridx_to_strinfo
;
3483 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
3484 (*stridx_to_strinfo
)[0] = (strinfo
*) bb
;
3488 /* Callback for walk_dominator_tree. Free strinfo vector if it is
3489 owned by the current bb, clear bb->aux. */
3492 strlen_dom_walker::after_dom_children (basic_block bb
)
3496 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) bb
->aux
);
3497 if (vec_safe_length (stridx_to_strinfo
)
3498 && (*stridx_to_strinfo
)[0] == (strinfo
*) bb
)
3503 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
3505 vec_free (stridx_to_strinfo
);
3511 /* Main entry point. */
3515 const pass_data pass_data_strlen
=
3517 GIMPLE_PASS
, /* type */
3518 "strlen", /* name */
3519 OPTGROUP_NONE
, /* optinfo_flags */
3520 TV_TREE_STRLEN
, /* tv_id */
3521 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3522 0, /* properties_provided */
3523 0, /* properties_destroyed */
3524 0, /* todo_flags_start */
3525 0, /* todo_flags_finish */
3528 class pass_strlen
: public gimple_opt_pass
3531 pass_strlen (gcc::context
*ctxt
)
3532 : gimple_opt_pass (pass_data_strlen
, ctxt
)
3535 /* opt_pass methods: */
3536 virtual bool gate (function
*) { return flag_optimize_strlen
!= 0; }
3537 virtual unsigned int execute (function
*);
3539 }; // class pass_strlen
3542 pass_strlen::execute (function
*fun
)
3544 gcc_assert (!strlen_to_stridx
);
3545 if (warn_stringop_overflow
|| warn_stringop_truncation
)
3546 strlen_to_stridx
= new hash_map
<tree
, stridx_strlenloc
> ();
3548 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
3551 calculate_dominance_info (CDI_DOMINATORS
);
3553 /* String length optimization is implemented as a walk of the dominator
3554 tree and a forward walk of statements within each block. */
3555 strlen_dom_walker
walker (CDI_DOMINATORS
);
3556 walker
.walk (fun
->cfg
->x_entry_block_ptr
);
3558 ssa_ver_to_stridx
.release ();
3559 strinfo_pool
.release ();
3560 if (decl_to_stridxlist_htab
)
3562 obstack_free (&stridx_obstack
, NULL
);
3563 delete decl_to_stridxlist_htab
;
3564 decl_to_stridxlist_htab
= NULL
;
3566 laststmt
.stmt
= NULL
;
3567 laststmt
.len
= NULL_TREE
;
3568 laststmt
.stridx
= 0;
3570 if (strlen_to_stridx
)
3572 strlen_to_stridx
->empty ();
3573 delete strlen_to_stridx
;
3574 strlen_to_stridx
= NULL
;
3577 return walker
.m_cleanup_cfg
? TODO_cleanup_cfg
: 0;
3583 make_pass_strlen (gcc::context
*ctxt
)
3585 return new pass_strlen (ctxt
);