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 "fold-const.h"
34 #include "stor-layout.h"
35 #include "gimple-fold.h"
38 #include "gimple-iterator.h"
39 #include "gimplify-me.h"
43 #include "tree-ssa-alias.h"
44 #include "tree-ssa-propagate.h"
47 #include "tree-hash-traits.h"
50 #include "diagnostic-core.h"
51 #include "diagnostic.h"
56 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
57 is an index into strinfo vector, negative value stands for
58 string length of a string literal (~strlen). */
59 static vec
<int> ssa_ver_to_stridx
;
61 /* Number of currently active string indexes plus one. */
62 static int max_stridx
;
64 /* String information record. */
67 /* Number of leading characters that are known to be nonzero. This is
68 also the length of the string if FULL_STRING_P.
70 The values in a list of related string pointers must be consistent;
71 that is, if strinfo B comes X bytes after strinfo A, it must be
72 the case that A->nonzero_chars == X + B->nonzero_chars. */
74 /* Any of the corresponding pointers for querying alias oracle. */
76 /* This is used for two things:
78 - To record the statement that should be used for delayed length
79 computations. We maintain the invariant that all related strinfos
80 have delayed lengths or none do.
82 - To record the malloc or calloc call that produced this result. */
84 /* Pointer to '\0' if known, if NULL, it can be computed as
87 /* Reference count. Any changes to strinfo entry possibly shared
88 with dominating basic blocks need unshare_strinfo first, except
89 for dont_invalidate which affects only the immediately next
92 /* Copy of index. get_strinfo (si->idx) should return si; */
94 /* These 3 fields are for chaining related string pointers together.
96 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
97 strcpy (c, d); e = c + dl;
98 strinfo(a) -> strinfo(c) -> strinfo(e)
99 All have ->first field equal to strinfo(a)->idx and are doubly
100 chained through prev/next fields. The later strinfos are required
101 to point into the same string with zero or more bytes after
102 the previous pointer and all bytes in between the two pointers
103 must be non-zero. Functions like strcpy or memcpy are supposed
104 to adjust all previous strinfo lengths, but not following strinfo
105 lengths (those are uncertain, usually invalidated during
106 maybe_invalidate, except when the alias oracle knows better).
107 Functions like strcat on the other side adjust the whole
108 related strinfo chain.
109 They are updated lazily, so to use the chain the same first fields
110 and si->prev->next == si->idx needs to be verified. */
114 /* A flag whether the string is known to be written in the current
117 /* A flag for the next maybe_invalidate that this strinfo shouldn't
118 be invalidated. Always cleared by maybe_invalidate. */
119 bool dont_invalidate
;
120 /* True if the string is known to be nul-terminated after NONZERO_CHARS
121 characters. False is useful when detecting strings that are built
122 up via successive memcpys. */
126 /* Pool for allocating strinfo_struct entries. */
127 static object_allocator
<strinfo
> strinfo_pool ("strinfo pool");
129 /* Vector mapping positive string indexes to strinfo, for the
130 current basic block. The first pointer in the vector is special,
131 it is either NULL, meaning the vector isn't shared, or it is
132 a basic block pointer to the owner basic_block if shared.
133 If some other bb wants to modify the vector, the vector needs
134 to be unshared first, and only the owner bb is supposed to free it. */
135 static vec
<strinfo
*, va_heap
, vl_embed
> *stridx_to_strinfo
;
137 /* One OFFSET->IDX mapping. */
140 struct stridxlist
*next
;
141 HOST_WIDE_INT offset
;
145 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
146 struct decl_stridxlist_map
148 struct tree_map_base base
;
149 struct stridxlist list
;
152 /* Hash table for mapping decls to a chained list of offset -> idx
154 static hash_map
<tree_decl_hash
, stridxlist
> *decl_to_stridxlist_htab
;
156 /* Hash table mapping strlen calls to stridx instances describing
157 the calls' arguments. Non-null only when warn_stringop_truncation
159 typedef std::pair
<int, location_t
> stridx_strlenloc
;
160 static hash_map
<tree
, stridx_strlenloc
> *strlen_to_stridx
;
162 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
163 static struct obstack stridx_obstack
;
165 /* Last memcpy statement if it could be adjusted if the trailing
166 '\0' written is immediately overwritten, or
167 *x = '\0' store that could be removed if it is immediately overwritten. */
168 struct laststmt_struct
175 static int get_stridx_plus_constant (strinfo
*, unsigned HOST_WIDE_INT
, tree
);
179 - 1 if SI is known to start with more than OFF nonzero characters.
181 - 0 if SI is known to start with OFF nonzero characters,
182 but is not known to start with more.
184 - -1 if SI might not start with OFF nonzero characters. */
187 compare_nonzero_chars (strinfo
*si
, unsigned HOST_WIDE_INT off
)
189 if (si
->nonzero_chars
190 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
191 return compare_tree_int (si
->nonzero_chars
, off
);
196 /* Return true if SI is known to be a zero-length string. */
199 zero_length_string_p (strinfo
*si
)
201 return si
->full_string_p
&& integer_zerop (si
->nonzero_chars
);
204 /* Return strinfo vector entry IDX. */
206 static inline strinfo
*
207 get_strinfo (int idx
)
209 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
211 return (*stridx_to_strinfo
)[idx
];
214 /* Get the next strinfo in the chain after SI, or null if none. */
216 static inline strinfo
*
217 get_next_strinfo (strinfo
*si
)
221 strinfo
*nextsi
= get_strinfo (si
->next
);
222 if (nextsi
== NULL
|| nextsi
->first
!= si
->first
|| nextsi
->prev
!= si
->idx
)
227 /* Helper function for get_stridx. Return the strinfo index of the address
228 of EXP, which is available in PTR if nonnull. If OFFSET_OUT, it is
229 OK to return the index for some X <= &EXP and store &EXP - X in
233 get_addr_stridx (tree exp
, tree ptr
, unsigned HOST_WIDE_INT
*offset_out
)
236 struct stridxlist
*list
, *last
= NULL
;
239 if (!decl_to_stridxlist_htab
)
242 base
= get_addr_base_and_unit_offset (exp
, &off
);
243 if (base
== NULL
|| !DECL_P (base
))
246 list
= decl_to_stridxlist_htab
->get (base
);
252 if (list
->offset
== off
)
258 if (list
->offset
> off
)
265 if ((offset_out
|| ptr
) && last
&& last
->idx
> 0)
267 unsigned HOST_WIDE_INT rel_off
268 = (unsigned HOST_WIDE_INT
) off
- last
->offset
;
269 strinfo
*si
= get_strinfo (last
->idx
);
270 if (si
&& compare_nonzero_chars (si
, rel_off
) >= 0)
274 *offset_out
= rel_off
;
278 return get_stridx_plus_constant (si
, rel_off
, ptr
);
284 /* Return string index for EXP. */
287 get_stridx (tree exp
)
291 if (TREE_CODE (exp
) == SSA_NAME
)
293 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)])
294 return ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)];
297 HOST_WIDE_INT off
= 0;
298 for (i
= 0; i
< 5; i
++)
300 gimple
*def_stmt
= SSA_NAME_DEF_STMT (e
);
301 if (!is_gimple_assign (def_stmt
)
302 || gimple_assign_rhs_code (def_stmt
) != POINTER_PLUS_EXPR
)
304 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
305 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
306 if (TREE_CODE (rhs1
) != SSA_NAME
307 || !tree_fits_shwi_p (rhs2
))
309 HOST_WIDE_INT this_off
= tree_to_shwi (rhs2
);
312 off
= (unsigned HOST_WIDE_INT
) off
+ this_off
;
315 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)])
318 = get_strinfo (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)]);
319 if (si
&& compare_nonzero_chars (si
, off
) >= 0)
320 return get_stridx_plus_constant (si
, off
, exp
);
327 if (TREE_CODE (exp
) == ADDR_EXPR
)
329 int idx
= get_addr_stridx (TREE_OPERAND (exp
, 0), exp
, NULL
);
334 s
= string_constant (exp
, &o
);
336 && (o
== NULL_TREE
|| tree_fits_shwi_p (o
))
337 && TREE_STRING_LENGTH (s
) > 0)
339 HOST_WIDE_INT offset
= o
? tree_to_shwi (o
) : 0;
340 const char *p
= TREE_STRING_POINTER (s
);
341 int max
= TREE_STRING_LENGTH (s
) - 1;
343 if (p
[max
] == '\0' && offset
>= 0 && offset
<= max
)
344 return ~(int) strlen (p
+ offset
);
349 /* Return true if strinfo vector is shared with the immediate dominator. */
352 strinfo_shared (void)
354 return vec_safe_length (stridx_to_strinfo
)
355 && (*stridx_to_strinfo
)[0] != NULL
;
358 /* Unshare strinfo vector that is shared with the immediate dominator. */
361 unshare_strinfo_vec (void)
366 gcc_assert (strinfo_shared ());
367 stridx_to_strinfo
= vec_safe_copy (stridx_to_strinfo
);
368 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
371 (*stridx_to_strinfo
)[0] = NULL
;
374 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
375 Return a pointer to the location where the string index can
376 be stored (if 0) or is stored, or NULL if this can't be tracked. */
379 addr_stridxptr (tree exp
)
383 tree base
= get_addr_base_and_unit_offset (exp
, &off
);
384 if (base
== NULL_TREE
|| !DECL_P (base
))
387 if (!decl_to_stridxlist_htab
)
389 decl_to_stridxlist_htab
390 = new hash_map
<tree_decl_hash
, stridxlist
> (64);
391 gcc_obstack_init (&stridx_obstack
);
395 stridxlist
*list
= &decl_to_stridxlist_htab
->get_or_insert (base
, &existed
);
399 stridxlist
*before
= NULL
;
400 for (i
= 0; i
< 32; i
++)
402 if (list
->offset
== off
)
404 if (list
->offset
> off
&& before
== NULL
)
406 if (list
->next
== NULL
)
415 before
= XOBNEW (&stridx_obstack
, struct stridxlist
);
422 list
->next
= XOBNEW (&stridx_obstack
, struct stridxlist
);
432 /* Create a new string index, or return 0 if reached limit. */
435 new_stridx (tree exp
)
438 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
440 if (TREE_CODE (exp
) == SSA_NAME
)
442 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
445 ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)] = idx
;
448 if (TREE_CODE (exp
) == ADDR_EXPR
)
450 int *pidx
= addr_stridxptr (TREE_OPERAND (exp
, 0));
453 gcc_assert (*pidx
== 0);
454 *pidx
= max_stridx
++;
461 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
464 new_addr_stridx (tree exp
)
467 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
469 pidx
= addr_stridxptr (exp
);
472 gcc_assert (*pidx
== 0);
473 *pidx
= max_stridx
++;
479 /* Create a new strinfo. */
482 new_strinfo (tree ptr
, int idx
, tree nonzero_chars
, bool full_string_p
)
484 strinfo
*si
= strinfo_pool
.allocate ();
485 si
->nonzero_chars
= nonzero_chars
;
488 si
->endptr
= NULL_TREE
;
494 si
->writable
= false;
495 si
->dont_invalidate
= false;
496 si
->full_string_p
= full_string_p
;
500 /* Decrease strinfo refcount and free it if not referenced anymore. */
503 free_strinfo (strinfo
*si
)
505 if (si
&& --si
->refcount
== 0)
506 strinfo_pool
.remove (si
);
509 /* Set strinfo in the vector entry IDX to SI. */
512 set_strinfo (int idx
, strinfo
*si
)
514 if (vec_safe_length (stridx_to_strinfo
) && (*stridx_to_strinfo
)[0])
515 unshare_strinfo_vec ();
516 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
517 vec_safe_grow_cleared (stridx_to_strinfo
, idx
+ 1);
518 (*stridx_to_strinfo
)[idx
] = si
;
521 /* Return the first strinfo in the related strinfo chain
522 if all strinfos in between belong to the chain, otherwise NULL. */
525 verify_related_strinfos (strinfo
*origsi
)
527 strinfo
*si
= origsi
, *psi
;
529 if (origsi
->first
== 0)
531 for (; si
->prev
; si
= psi
)
533 if (si
->first
!= origsi
->first
)
535 psi
= get_strinfo (si
->prev
);
538 if (psi
->next
!= si
->idx
)
541 if (si
->idx
!= si
->first
)
546 /* Set SI's endptr to ENDPTR and compute its length based on SI->ptr.
547 Use LOC for folding. */
550 set_endptr_and_length (location_t loc
, strinfo
*si
, tree endptr
)
554 tree start_as_size
= fold_convert_loc (loc
, size_type_node
, si
->ptr
);
555 tree end_as_size
= fold_convert_loc (loc
, size_type_node
, endptr
);
556 si
->nonzero_chars
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
557 end_as_size
, start_as_size
);
558 si
->full_string_p
= true;
561 /* Return string length, or NULL if it can't be computed. */
564 get_string_length (strinfo
*si
)
566 if (si
->nonzero_chars
)
567 return si
->full_string_p
? si
->nonzero_chars
: NULL
;
571 gimple
*stmt
= si
->stmt
, *lenstmt
;
572 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
573 tree callee
, lhs
, fn
, tem
;
575 gimple_stmt_iterator gsi
;
577 gcc_assert (is_gimple_call (stmt
));
578 callee
= gimple_call_fndecl (stmt
);
579 gcc_assert (callee
&& DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
);
580 lhs
= gimple_call_lhs (stmt
);
581 /* unshare_strinfo is intentionally not called here. The (delayed)
582 transformation of strcpy or strcat into stpcpy is done at the place
583 of the former strcpy/strcat call and so can affect all the strinfos
584 with the same stmt. If they were unshared before and transformation
585 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
586 just compute the right length. */
587 switch (DECL_FUNCTION_CODE (callee
))
589 case BUILT_IN_STRCAT
:
590 case BUILT_IN_STRCAT_CHK
:
591 case BUILT_IN_STRCAT_CHKP
:
592 case BUILT_IN_STRCAT_CHK_CHKP
:
593 gsi
= gsi_for_stmt (stmt
);
594 fn
= builtin_decl_implicit (BUILT_IN_STRLEN
);
595 gcc_assert (lhs
== NULL_TREE
);
596 tem
= unshare_expr (gimple_call_arg (stmt
, 0));
599 lenstmt
= gimple_build_call (chkp_maybe_create_clone (fn
)->decl
,
600 2, tem
, gimple_call_arg (stmt
, 1));
601 gimple_call_set_with_bounds (lenstmt
, true);
604 lenstmt
= gimple_build_call (fn
, 1, tem
);
605 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), lenstmt
);
606 gimple_call_set_lhs (lenstmt
, lhs
);
607 gimple_set_vuse (lenstmt
, gimple_vuse (stmt
));
608 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
609 tem
= gimple_call_arg (stmt
, 0);
610 if (!ptrofftype_p (TREE_TYPE (lhs
)))
612 lhs
= convert_to_ptrofftype (lhs
);
613 lhs
= force_gimple_operand_gsi (&gsi
, lhs
, true, NULL_TREE
,
614 true, GSI_SAME_STMT
);
616 lenstmt
= gimple_build_assign
617 (make_ssa_name (TREE_TYPE (gimple_call_arg (stmt
, 0))),
618 POINTER_PLUS_EXPR
,tem
, lhs
);
619 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
620 gimple_call_set_arg (stmt
, 0, gimple_assign_lhs (lenstmt
));
623 case BUILT_IN_STRCPY
:
624 case BUILT_IN_STRCPY_CHK
:
625 case BUILT_IN_STRCPY_CHKP
:
626 case BUILT_IN_STRCPY_CHK_CHKP
:
627 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY
));
628 if (gimple_call_num_args (stmt
) == (with_bounds
? 4 : 2))
629 fn
= builtin_decl_implicit (BUILT_IN_STPCPY
);
631 fn
= builtin_decl_explicit (BUILT_IN_STPCPY_CHK
);
633 fn
= chkp_maybe_create_clone (fn
)->decl
;
634 gcc_assert (lhs
== NULL_TREE
);
635 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
637 fprintf (dump_file
, "Optimizing: ");
638 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
640 gimple_call_set_fndecl (stmt
, fn
);
641 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), stmt
);
642 gimple_call_set_lhs (stmt
, lhs
);
644 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
646 fprintf (dump_file
, "into: ");
647 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
650 case BUILT_IN_STPCPY
:
651 case BUILT_IN_STPCPY_CHK
:
652 case BUILT_IN_STPCPY_CHKP
:
653 case BUILT_IN_STPCPY_CHK_CHKP
:
654 gcc_assert (lhs
!= NULL_TREE
);
655 loc
= gimple_location (stmt
);
656 set_endptr_and_length (loc
, si
, lhs
);
657 for (strinfo
*chainsi
= verify_related_strinfos (si
);
659 chainsi
= get_next_strinfo (chainsi
))
660 if (chainsi
->nonzero_chars
== NULL
)
661 set_endptr_and_length (loc
, chainsi
, lhs
);
663 case BUILT_IN_MALLOC
:
665 /* BUILT_IN_CALLOC always has si->nonzero_chars set. */
672 return si
->nonzero_chars
;
675 /* Invalidate string length information for strings whose length
676 might change due to stores in stmt. */
679 maybe_invalidate (gimple
*stmt
)
683 bool nonempty
= false;
685 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
688 if (!si
->dont_invalidate
)
691 /* Do not use si->nonzero_chars. */
692 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, NULL_TREE
);
693 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
695 set_strinfo (i
, NULL
);
700 si
->dont_invalidate
= false;
706 /* Unshare strinfo record SI, if it has refcount > 1 or
707 if stridx_to_strinfo vector is shared with some other
711 unshare_strinfo (strinfo
*si
)
715 if (si
->refcount
== 1 && !strinfo_shared ())
718 nsi
= new_strinfo (si
->ptr
, si
->idx
, si
->nonzero_chars
, si
->full_string_p
);
719 nsi
->stmt
= si
->stmt
;
720 nsi
->endptr
= si
->endptr
;
721 nsi
->first
= si
->first
;
722 nsi
->prev
= si
->prev
;
723 nsi
->next
= si
->next
;
724 nsi
->writable
= si
->writable
;
725 set_strinfo (si
->idx
, nsi
);
730 /* Attempt to create a new strinfo for BASESI + OFF, or find existing
731 strinfo if there is any. Return it's idx, or 0 if no strinfo has
735 get_stridx_plus_constant (strinfo
*basesi
, unsigned HOST_WIDE_INT off
,
738 if (TREE_CODE (ptr
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
741 if (compare_nonzero_chars (basesi
, off
) < 0
742 || !tree_fits_uhwi_p (basesi
->nonzero_chars
))
745 unsigned HOST_WIDE_INT nonzero_chars
746 = tree_to_uhwi (basesi
->nonzero_chars
) - off
;
747 strinfo
*si
= basesi
, *chainsi
;
748 if (si
->first
|| si
->prev
|| si
->next
)
749 si
= verify_related_strinfos (basesi
);
751 || si
->nonzero_chars
== NULL_TREE
752 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
755 if (TREE_CODE (ptr
) == SSA_NAME
756 && ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
757 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
759 gcc_checking_assert (compare_tree_int (si
->nonzero_chars
, off
) != -1);
760 for (chainsi
= si
; chainsi
->next
; chainsi
= si
)
762 si
= get_next_strinfo (chainsi
);
764 || si
->nonzero_chars
== NULL_TREE
765 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
767 int r
= compare_tree_int (si
->nonzero_chars
, nonzero_chars
);
772 if (TREE_CODE (ptr
) == SSA_NAME
)
773 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = si
->idx
;
776 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
777 if (pidx
!= NULL
&& *pidx
== 0)
786 int idx
= new_stridx (ptr
);
789 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, nonzero_chars
),
790 basesi
->full_string_p
);
791 set_strinfo (idx
, si
);
794 strinfo
*nextsi
= unshare_strinfo (get_strinfo (chainsi
->next
));
795 si
->next
= nextsi
->idx
;
798 chainsi
= unshare_strinfo (chainsi
);
799 if (chainsi
->first
== 0)
800 chainsi
->first
= chainsi
->idx
;
802 if (chainsi
->endptr
== NULL_TREE
&& zero_length_string_p (si
))
803 chainsi
->endptr
= ptr
;
804 si
->endptr
= chainsi
->endptr
;
805 si
->prev
= chainsi
->idx
;
806 si
->first
= chainsi
->first
;
807 si
->writable
= chainsi
->writable
;
811 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
812 to a zero-length string and if possible chain it to a related strinfo
813 chain whose part is or might be CHAINSI. */
816 zero_length_string (tree ptr
, strinfo
*chainsi
)
820 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
821 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
822 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
823 && ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] == 0);
825 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
829 si
= verify_related_strinfos (chainsi
);
834 /* We shouldn't mix delayed and non-delayed lengths. */
835 gcc_assert (si
->full_string_p
);
836 if (si
->endptr
== NULL_TREE
)
838 si
= unshare_strinfo (si
);
842 si
= get_next_strinfo (si
);
845 if (zero_length_string_p (chainsi
))
849 chainsi
= unshare_strinfo (chainsi
);
852 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = chainsi
->idx
;
858 /* We shouldn't mix delayed and non-delayed lengths. */
859 gcc_assert (chainsi
->full_string_p
);
860 if (chainsi
->first
|| chainsi
->prev
|| chainsi
->next
)
862 chainsi
= unshare_strinfo (chainsi
);
869 idx
= new_stridx (ptr
);
872 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, 0), true);
873 set_strinfo (idx
, si
);
877 chainsi
= unshare_strinfo (chainsi
);
878 if (chainsi
->first
== 0)
879 chainsi
->first
= chainsi
->idx
;
881 if (chainsi
->endptr
== NULL_TREE
)
882 chainsi
->endptr
= ptr
;
883 si
->prev
= chainsi
->idx
;
884 si
->first
= chainsi
->first
;
885 si
->writable
= chainsi
->writable
;
890 /* For strinfo ORIGSI whose length has been just updated, adjust other
891 related strinfos so that they match the new ORIGSI. This involves:
893 - adding ADJ to the nonzero_chars fields
894 - copying full_string_p from the new ORIGSI. */
897 adjust_related_strinfos (location_t loc
, strinfo
*origsi
, tree adj
)
899 strinfo
*si
= verify_related_strinfos (origsi
);
912 si
= unshare_strinfo (si
);
913 /* We shouldn't see delayed lengths here; the caller must have
914 calculated the old length in order to calculate the
916 gcc_assert (si
->nonzero_chars
);
917 tem
= fold_convert_loc (loc
, TREE_TYPE (si
->nonzero_chars
), adj
);
918 si
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
919 TREE_TYPE (si
->nonzero_chars
),
920 si
->nonzero_chars
, tem
);
921 si
->full_string_p
= origsi
->full_string_p
;
923 si
->endptr
= NULL_TREE
;
924 si
->dont_invalidate
= true;
926 nsi
= get_next_strinfo (si
);
933 /* Find if there are other SSA_NAME pointers equal to PTR
934 for which we don't track their string lengths yet. If so, use
938 find_equal_ptrs (tree ptr
, int idx
)
940 if (TREE_CODE (ptr
) != SSA_NAME
)
944 gimple
*stmt
= SSA_NAME_DEF_STMT (ptr
);
945 if (!is_gimple_assign (stmt
))
947 ptr
= gimple_assign_rhs1 (stmt
);
948 switch (gimple_assign_rhs_code (stmt
))
953 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)))
955 if (TREE_CODE (ptr
) == SSA_NAME
)
957 if (TREE_CODE (ptr
) != ADDR_EXPR
)
962 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
963 if (pidx
!= NULL
&& *pidx
== 0)
971 /* We might find an endptr created in this pass. Grow the
972 vector in that case. */
973 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
974 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
976 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] != 0)
978 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = idx
;
982 /* Return true if STMT is a call to a builtin function with the right
983 arguments and attributes that should be considered for optimization
987 valid_builtin_call (gimple
*stmt
)
989 if (!gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
992 tree callee
= gimple_call_fndecl (stmt
);
993 switch (DECL_FUNCTION_CODE (callee
))
995 case BUILT_IN_MEMCMP
:
996 case BUILT_IN_MEMCMP_EQ
:
997 case BUILT_IN_STRCHR
:
998 case BUILT_IN_STRCHR_CHKP
:
999 case BUILT_IN_STRLEN
:
1000 case BUILT_IN_STRLEN_CHKP
:
1001 /* The above functions should be pure. Punt if they aren't. */
1002 if (gimple_vdef (stmt
) || gimple_vuse (stmt
) == NULL_TREE
)
1006 case BUILT_IN_CALLOC
:
1007 case BUILT_IN_MALLOC
:
1008 case BUILT_IN_MEMCPY
:
1009 case BUILT_IN_MEMCPY_CHK
:
1010 case BUILT_IN_MEMCPY_CHKP
:
1011 case BUILT_IN_MEMCPY_CHK_CHKP
:
1012 case BUILT_IN_MEMPCPY
:
1013 case BUILT_IN_MEMPCPY_CHK
:
1014 case BUILT_IN_MEMPCPY_CHKP
:
1015 case BUILT_IN_MEMPCPY_CHK_CHKP
:
1016 case BUILT_IN_MEMSET
:
1017 case BUILT_IN_STPCPY
:
1018 case BUILT_IN_STPCPY_CHK
:
1019 case BUILT_IN_STPCPY_CHKP
:
1020 case BUILT_IN_STPCPY_CHK_CHKP
:
1021 case BUILT_IN_STRCAT
:
1022 case BUILT_IN_STRCAT_CHK
:
1023 case BUILT_IN_STRCAT_CHKP
:
1024 case BUILT_IN_STRCAT_CHK_CHKP
:
1025 case BUILT_IN_STRCPY
:
1026 case BUILT_IN_STRCPY_CHK
:
1027 case BUILT_IN_STRCPY_CHKP
:
1028 case BUILT_IN_STRCPY_CHK_CHKP
:
1029 /* The above functions should be neither const nor pure. Punt if they
1031 if (gimple_vdef (stmt
) == NULL_TREE
|| gimple_vuse (stmt
) == NULL_TREE
)
1042 /* If the last .MEM setter statement before STMT is
1043 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
1044 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
1045 just memcpy (x, y, strlen (y)). SI must be the zero length
1049 adjust_last_stmt (strinfo
*si
, gimple
*stmt
, bool is_strcat
)
1051 tree vuse
, callee
, len
;
1052 struct laststmt_struct last
= laststmt
;
1053 strinfo
*lastsi
, *firstsi
;
1054 unsigned len_arg_no
= 2;
1056 laststmt
.stmt
= NULL
;
1057 laststmt
.len
= NULL_TREE
;
1058 laststmt
.stridx
= 0;
1060 if (last
.stmt
== NULL
)
1063 vuse
= gimple_vuse (stmt
);
1064 if (vuse
== NULL_TREE
1065 || SSA_NAME_DEF_STMT (vuse
) != last
.stmt
1066 || !has_single_use (vuse
))
1069 gcc_assert (last
.stridx
> 0);
1070 lastsi
= get_strinfo (last
.stridx
);
1076 if (lastsi
->first
== 0 || lastsi
->first
!= si
->first
)
1079 firstsi
= verify_related_strinfos (si
);
1080 if (firstsi
== NULL
)
1082 while (firstsi
!= lastsi
)
1084 firstsi
= get_next_strinfo (firstsi
);
1085 if (firstsi
== NULL
)
1090 if (!is_strcat
&& !zero_length_string_p (si
))
1093 if (is_gimple_assign (last
.stmt
))
1095 gimple_stmt_iterator gsi
;
1097 if (!integer_zerop (gimple_assign_rhs1 (last
.stmt
)))
1099 if (stmt_could_throw_p (last
.stmt
))
1101 gsi
= gsi_for_stmt (last
.stmt
);
1102 unlink_stmt_vdef (last
.stmt
);
1103 release_defs (last
.stmt
);
1104 gsi_remove (&gsi
, true);
1108 if (!valid_builtin_call (last
.stmt
))
1111 callee
= gimple_call_fndecl (last
.stmt
);
1112 switch (DECL_FUNCTION_CODE (callee
))
1114 case BUILT_IN_MEMCPY
:
1115 case BUILT_IN_MEMCPY_CHK
:
1117 case BUILT_IN_MEMCPY_CHKP
:
1118 case BUILT_IN_MEMCPY_CHK_CHKP
:
1125 len
= gimple_call_arg (last
.stmt
, len_arg_no
);
1126 if (tree_fits_uhwi_p (len
))
1128 if (!tree_fits_uhwi_p (last
.len
)
1129 || integer_zerop (len
)
1130 || tree_to_uhwi (len
) != tree_to_uhwi (last
.len
) + 1)
1132 /* Don't adjust the length if it is divisible by 4, it is more efficient
1133 to store the extra '\0' in that case. */
1134 if ((tree_to_uhwi (len
) & 3) == 0)
1137 else if (TREE_CODE (len
) == SSA_NAME
)
1139 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1140 if (!is_gimple_assign (def_stmt
)
1141 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1142 || gimple_assign_rhs1 (def_stmt
) != last
.len
1143 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1149 gimple_call_set_arg (last
.stmt
, len_arg_no
, last
.len
);
1150 update_stmt (last
.stmt
);
1153 /* Handle a strlen call. If strlen of the argument is known, replace
1154 the strlen call with the known value, otherwise remember that strlen
1155 of the argument is stored in the lhs SSA_NAME. */
1158 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
1162 gimple
*stmt
= gsi_stmt (*gsi
);
1163 tree lhs
= gimple_call_lhs (stmt
);
1165 if (lhs
== NULL_TREE
)
1168 src
= gimple_call_arg (stmt
, 0);
1169 idx
= get_stridx (src
);
1176 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
1180 si
= get_strinfo (idx
);
1182 rhs
= get_string_length (si
);
1184 if (rhs
!= NULL_TREE
)
1186 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1188 fprintf (dump_file
, "Optimizing: ");
1189 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1191 rhs
= unshare_expr (rhs
);
1192 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
1193 rhs
= fold_convert_loc (gimple_location (stmt
),
1194 TREE_TYPE (lhs
), rhs
);
1195 if (!update_call_from_tree (gsi
, rhs
))
1196 gimplify_and_update_call_from_tree (gsi
, rhs
);
1197 stmt
= gsi_stmt (*gsi
);
1199 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1201 fprintf (dump_file
, "into: ");
1202 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1205 && TREE_CODE (si
->nonzero_chars
) != SSA_NAME
1206 && TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
1207 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1209 si
= unshare_strinfo (si
);
1210 si
->nonzero_chars
= lhs
;
1211 gcc_assert (si
->full_string_p
);
1214 if (strlen_to_stridx
)
1216 location_t loc
= gimple_location (stmt
);
1217 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1222 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1225 idx
= new_stridx (src
);
1228 strinfo
*si
= get_strinfo (idx
);
1231 if (!si
->full_string_p
&& !si
->stmt
)
1233 /* Until now we only had a lower bound on the string length.
1234 Install LHS as the actual length. */
1235 si
= unshare_strinfo (si
);
1236 tree old
= si
->nonzero_chars
;
1237 si
->nonzero_chars
= lhs
;
1238 si
->full_string_p
= true;
1239 if (TREE_CODE (old
) == INTEGER_CST
)
1241 location_t loc
= gimple_location (stmt
);
1242 old
= fold_convert_loc (loc
, TREE_TYPE (lhs
), old
);
1243 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1244 TREE_TYPE (lhs
), lhs
, old
);
1245 adjust_related_strinfos (loc
, si
, adj
);
1259 strinfo
*si
= new_strinfo (src
, idx
, lhs
, true);
1260 set_strinfo (idx
, si
);
1261 find_equal_ptrs (src
, idx
);
1263 if (strlen_to_stridx
)
1265 location_t loc
= gimple_location (stmt
);
1266 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1271 /* Handle a strchr call. If strlen of the first argument is known, replace
1272 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
1273 that lhs of the call is endptr and strlen of the argument is endptr - x. */
1276 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
1280 gimple
*stmt
= gsi_stmt (*gsi
);
1281 tree lhs
= gimple_call_lhs (stmt
);
1282 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1284 if (lhs
== NULL_TREE
)
1287 if (!integer_zerop (gimple_call_arg (stmt
, with_bounds
? 2 : 1)))
1290 src
= gimple_call_arg (stmt
, 0);
1291 idx
= get_stridx (src
);
1298 rhs
= build_int_cst (size_type_node
, ~idx
);
1302 si
= get_strinfo (idx
);
1304 rhs
= get_string_length (si
);
1306 if (rhs
!= NULL_TREE
)
1308 location_t loc
= gimple_location (stmt
);
1310 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1312 fprintf (dump_file
, "Optimizing: ");
1313 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1315 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
1317 rhs
= unshare_expr (si
->endptr
);
1318 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1320 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1324 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1325 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1326 TREE_TYPE (src
), src
, rhs
);
1327 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1329 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1331 if (!update_call_from_tree (gsi
, rhs
))
1332 gimplify_and_update_call_from_tree (gsi
, rhs
);
1333 stmt
= gsi_stmt (*gsi
);
1335 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1337 fprintf (dump_file
, "into: ");
1338 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1341 && si
->endptr
== NULL_TREE
1342 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1344 si
= unshare_strinfo (si
);
1347 zero_length_string (lhs
, si
);
1351 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1353 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1356 idx
= new_stridx (src
);
1357 else if (get_strinfo (idx
) != NULL
)
1359 zero_length_string (lhs
, NULL
);
1364 location_t loc
= gimple_location (stmt
);
1365 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1366 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1367 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1368 size_type_node
, lhsu
, srcu
);
1369 strinfo
*si
= new_strinfo (src
, idx
, length
, true);
1371 set_strinfo (idx
, si
);
1372 find_equal_ptrs (src
, idx
);
1373 zero_length_string (lhs
, si
);
1377 zero_length_string (lhs
, NULL
);
1380 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1381 If strlen of the second argument is known, strlen of the first argument
1382 is the same after this call. Furthermore, attempt to convert it to
1386 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1389 tree src
, dst
, srclen
, len
, lhs
, args
, type
, fn
, oldlen
;
1391 gimple
*stmt
= gsi_stmt (*gsi
);
1392 strinfo
*si
, *dsi
, *olddsi
, *zsi
;
1394 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1396 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1397 dst
= gimple_call_arg (stmt
, 0);
1398 lhs
= gimple_call_lhs (stmt
);
1399 idx
= get_stridx (src
);
1402 si
= get_strinfo (idx
);
1404 didx
= get_stridx (dst
);
1408 olddsi
= get_strinfo (didx
);
1413 adjust_last_stmt (olddsi
, stmt
, false);
1417 srclen
= get_string_length (si
);
1419 srclen
= build_int_cst (size_type_node
, ~idx
);
1421 loc
= gimple_location (stmt
);
1422 if (srclen
== NULL_TREE
)
1425 case BUILT_IN_STRCPY
:
1426 case BUILT_IN_STRCPY_CHK
:
1427 case BUILT_IN_STRCPY_CHKP
:
1428 case BUILT_IN_STRCPY_CHK_CHKP
:
1429 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1432 case BUILT_IN_STPCPY
:
1433 case BUILT_IN_STPCPY_CHK
:
1434 case BUILT_IN_STPCPY_CHKP
:
1435 case BUILT_IN_STPCPY_CHK_CHKP
:
1436 if (lhs
== NULL_TREE
)
1440 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1441 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1442 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1452 didx
= new_stridx (dst
);
1458 oldlen
= olddsi
->nonzero_chars
;
1459 dsi
= unshare_strinfo (olddsi
);
1460 dsi
->nonzero_chars
= srclen
;
1461 dsi
->full_string_p
= (srclen
!= NULL_TREE
);
1462 /* Break the chain, so adjust_related_strinfo on later pointers in
1463 the chain won't adjust this one anymore. */
1466 dsi
->endptr
= NULL_TREE
;
1470 dsi
= new_strinfo (dst
, didx
, srclen
, srclen
!= NULL_TREE
);
1471 set_strinfo (didx
, dsi
);
1472 find_equal_ptrs (dst
, didx
);
1474 dsi
->writable
= true;
1475 dsi
->dont_invalidate
= true;
1477 if (dsi
->nonzero_chars
== NULL_TREE
)
1481 /* If string length of src is unknown, use delayed length
1482 computation. If string lenth of dst will be needed, it
1483 can be computed by transforming this strcpy call into
1484 stpcpy and subtracting dst from the return value. */
1486 /* Look for earlier strings whose length could be determined if
1487 this strcpy is turned into an stpcpy. */
1489 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1491 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1493 /* When setting a stmt for delayed length computation
1494 prevent all strinfos through dsi from being
1496 chainsi
= unshare_strinfo (chainsi
);
1497 chainsi
->stmt
= stmt
;
1498 chainsi
->nonzero_chars
= NULL_TREE
;
1499 chainsi
->full_string_p
= false;
1500 chainsi
->endptr
= NULL_TREE
;
1501 chainsi
->dont_invalidate
= true;
1510 tree adj
= NULL_TREE
;
1511 if (oldlen
== NULL_TREE
)
1513 else if (integer_zerop (oldlen
))
1515 else if (TREE_CODE (oldlen
) == INTEGER_CST
1516 || TREE_CODE (srclen
) == INTEGER_CST
)
1517 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1518 TREE_TYPE (srclen
), srclen
,
1519 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1521 if (adj
!= NULL_TREE
)
1522 adjust_related_strinfos (loc
, dsi
, adj
);
1526 /* strcpy src may not overlap dst, so src doesn't need to be
1527 invalidated either. */
1529 si
->dont_invalidate
= true;
1535 case BUILT_IN_STRCPY
:
1536 case BUILT_IN_STRCPY_CHKP
:
1537 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1539 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1541 case BUILT_IN_STRCPY_CHK
:
1542 case BUILT_IN_STRCPY_CHK_CHKP
:
1543 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1545 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1547 case BUILT_IN_STPCPY
:
1548 case BUILT_IN_STPCPY_CHKP
:
1549 /* This would need adjustment of the lhs (subtract one),
1550 or detection that the trailing '\0' doesn't need to be
1551 written, if it will be immediately overwritten.
1552 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1556 zsi
= zero_length_string (lhs
, dsi
);
1559 case BUILT_IN_STPCPY_CHK
:
1560 case BUILT_IN_STPCPY_CHK_CHKP
:
1561 /* This would need adjustment of the lhs (subtract one),
1562 or detection that the trailing '\0' doesn't need to be
1563 written, if it will be immediately overwritten.
1564 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1568 zsi
= zero_length_string (lhs
, dsi
);
1575 zsi
->dont_invalidate
= true;
1577 if (fn
== NULL_TREE
)
1580 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1581 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1583 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1584 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1585 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1587 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1589 fprintf (dump_file
, "Optimizing: ");
1590 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1594 fn
= chkp_maybe_create_clone (fn
)->decl
;
1595 if (gimple_call_num_args (stmt
) == 4)
1596 success
= update_gimple_call (gsi
, fn
, 5, dst
,
1597 gimple_call_arg (stmt
, 1),
1599 gimple_call_arg (stmt
, 3),
1602 success
= update_gimple_call (gsi
, fn
, 6, dst
,
1603 gimple_call_arg (stmt
, 1),
1605 gimple_call_arg (stmt
, 3),
1607 gimple_call_arg (stmt
, 4));
1610 if (gimple_call_num_args (stmt
) == 2)
1611 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1613 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1614 gimple_call_arg (stmt
, 2));
1617 stmt
= gsi_stmt (*gsi
);
1618 gimple_call_set_with_bounds (stmt
, with_bounds
);
1620 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1622 fprintf (dump_file
, "into: ");
1623 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1625 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1626 laststmt
.stmt
= stmt
;
1627 laststmt
.len
= srclen
;
1628 laststmt
.stridx
= dsi
->idx
;
1630 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1631 fprintf (dump_file
, "not possible.\n");
1634 /* Return true if LEN depends on a call to strlen(SRC) in an interesting
1635 way. LEN can either be an integer expression, or a pointer (to char).
1636 When it is the latter (such as in recursive calls to self) is is
1637 assumed to be the argument in some call to strlen() whose relationship
1638 to SRC is being ascertained. */
1641 is_strlen_related_p (tree src
, tree len
)
1643 if (TREE_CODE (TREE_TYPE (len
)) == POINTER_TYPE
1644 && operand_equal_p (src
, len
, 0))
1647 if (TREE_CODE (len
) != SSA_NAME
)
1650 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1654 if (is_gimple_call (def_stmt
))
1656 tree func
= gimple_call_fndecl (def_stmt
);
1657 if (!valid_builtin_call (def_stmt
)
1658 || DECL_FUNCTION_CODE (func
) != BUILT_IN_STRLEN
)
1661 tree arg
= gimple_call_arg (def_stmt
, 0);
1662 return is_strlen_related_p (src
, arg
);
1665 if (!is_gimple_assign (def_stmt
))
1668 tree_code code
= gimple_assign_rhs_code (def_stmt
);
1669 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1670 tree rhstype
= TREE_TYPE (rhs1
);
1672 if ((TREE_CODE (rhstype
) == POINTER_TYPE
&& code
== POINTER_PLUS_EXPR
)
1673 || (INTEGRAL_TYPE_P (rhstype
)
1674 && (code
== BIT_AND_EXPR
1675 || code
== NOP_EXPR
)))
1677 /* Pointer plus (an integer) and integer cast or truncation are
1678 considered among the (potentially) related expressions to strlen.
1680 return is_strlen_related_p (src
, rhs1
);
1686 /* A helper of handle_builtin_stxncpy. Check to see if the specified
1687 bound is a) equal to the size of the destination DST and if so, b)
1688 if it's immediately followed by DST[CNT - 1] = '\0'. If a) holds
1689 and b) does not, warn. Otherwise, do nothing. Return true if
1690 diagnostic has been issued.
1692 The purpose is to diagnose calls to strncpy and stpncpy that do
1693 not nul-terminate the copy while allowing for the idiom where
1694 such a call is immediately followed by setting the last element
1697 strncpy (a, s, sizeof a);
1698 a[sizeof a - 1] = '\0';
1702 maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi
, tree src
, tree cnt
)
1704 gimple
*stmt
= gsi_stmt (gsi
);
1706 wide_int cntrange
[2];
1708 if (TREE_CODE (cnt
) == INTEGER_CST
)
1709 cntrange
[0] = cntrange
[1] = wi::to_wide (cnt
);
1710 else if (TREE_CODE (cnt
) == SSA_NAME
)
1712 enum value_range_type rng
= get_range_info (cnt
, cntrange
, cntrange
+ 1);
1713 if (rng
== VR_RANGE
)
1715 else if (rng
== VR_ANTI_RANGE
)
1717 wide_int maxobjsize
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
));
1719 if (wi::ltu_p (cntrange
[1], maxobjsize
))
1721 cntrange
[0] = cntrange
[1] + 1;
1722 cntrange
[1] = maxobjsize
;
1726 cntrange
[1] = cntrange
[0] - 1;
1727 cntrange
[0] = wi::zero (TYPE_PRECISION (TREE_TYPE (cnt
)));
1736 /* Negative value is the constant string length. If it's less than
1737 the lower bound there is no truncation. */
1738 int sidx
= get_stridx (src
);
1739 if (sidx
< 0 && wi::gtu_p (cntrange
[0], ~sidx
))
1742 tree dst
= gimple_call_arg (stmt
, 0);
1744 if (TREE_CODE (dstdecl
) == ADDR_EXPR
)
1745 dstdecl
= TREE_OPERAND (dstdecl
, 0);
1747 /* If the destination refers to a an array/pointer declared nonstring
1749 tree ref
= NULL_TREE
;
1750 if (get_attr_nonstring_decl (dstdecl
, &ref
))
1753 /* Look for dst[i] = '\0'; after the stxncpy() call and if found
1754 avoid the truncation warning. */
1756 gimple
*next_stmt
= gsi_stmt (gsi
);
1758 if (!gsi_end_p (gsi
) && is_gimple_assign (next_stmt
))
1760 tree lhs
= gimple_assign_lhs (next_stmt
);
1761 tree_code code
= TREE_CODE (lhs
);
1762 if (code
== ARRAY_REF
|| code
== MEM_REF
)
1763 lhs
= TREE_OPERAND (lhs
, 0);
1765 tree func
= gimple_call_fndecl (stmt
);
1766 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STPNCPY
)
1768 tree ret
= gimple_call_lhs (stmt
);
1769 if (ret
&& operand_equal_p (ret
, lhs
, 0))
1773 /* Determine the base address and offset of the reference,
1774 ignoring the innermost array index. */
1775 if (TREE_CODE (ref
) == ARRAY_REF
)
1776 ref
= TREE_OPERAND (ref
, 0);
1778 HOST_WIDE_INT dstoff
;
1779 tree dstbase
= get_addr_base_and_unit_offset (ref
, &dstoff
);
1781 HOST_WIDE_INT lhsoff
;
1782 tree lhsbase
= get_addr_base_and_unit_offset (lhs
, &lhsoff
);
1785 && operand_equal_p (dstbase
, lhsbase
, 0))
1789 int prec
= TYPE_PRECISION (TREE_TYPE (cnt
));
1790 wide_int lenrange
[2];
1791 if (strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
)
1793 lenrange
[0] = (sisrc
->nonzero_chars
1794 && TREE_CODE (sisrc
->nonzero_chars
) == INTEGER_CST
1795 ? wi::to_wide (sisrc
->nonzero_chars
)
1797 lenrange
[1] = lenrange
[0];
1800 lenrange
[0] = lenrange
[1] = wi::shwi (~sidx
, prec
);
1804 get_range_strlen (src
, range
);
1807 lenrange
[0] = wi::to_wide (range
[0], prec
);
1808 lenrange
[1] = wi::to_wide (range
[1], prec
);
1812 lenrange
[0] = wi::shwi (0, prec
);
1813 lenrange
[1] = wi::shwi (-1, prec
);
1817 location_t callloc
= gimple_location (stmt
);
1818 tree func
= gimple_call_fndecl (stmt
);
1820 if (lenrange
[0] != 0 || !wi::neg_p (lenrange
[1]))
1822 /* If the longest source string is shorter than the lower bound
1823 of the specified count the copy is definitely nul-terminated. */
1824 if (wi::ltu_p (lenrange
[1], cntrange
[0]))
1827 if (wi::neg_p (lenrange
[1]))
1829 /* The length of one of the strings is unknown but at least
1830 one has non-zero length and that length is stored in
1831 LENRANGE[1]. Swap the bounds to force a "may be truncated"
1833 lenrange
[1] = lenrange
[0];
1834 lenrange
[0] = wi::shwi (0, prec
);
1837 if (wi::geu_p (lenrange
[0], cntrange
[1]))
1839 /* The shortest string is longer than the upper bound of
1840 the count so the truncation is certain. */
1841 if (cntrange
[0] == cntrange
[1])
1842 return warning_at (callloc
, OPT_Wstringop_truncation
,
1844 ? G_("%qD output truncated copying %E byte "
1845 "from a string of length %wu")
1846 : G_("%qD output truncated copying %E bytes "
1847 "from a string of length %wu"),
1848 func
, cnt
, lenrange
[0].to_uhwi ());
1850 return warning_at (callloc
, OPT_Wstringop_truncation
,
1851 "%qD output truncated copying between %wu "
1852 "and %wu bytes from a string of length %wu",
1853 func
, cntrange
[0].to_uhwi (),
1854 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
1856 else if (wi::geu_p (lenrange
[1], cntrange
[1]))
1858 /* The longest string is longer than the upper bound of
1859 the count so the truncation is possible. */
1860 if (cntrange
[0] == cntrange
[1])
1861 return warning_at (callloc
, OPT_Wstringop_truncation
,
1863 ? G_("%qD output may be truncated copying %E "
1864 "byte from a string of length %wu")
1865 : G_("%qD output may be truncated copying %E "
1866 "bytes from a string of length %wu"),
1867 func
, cnt
, lenrange
[1].to_uhwi ());
1869 return warning_at (callloc
, OPT_Wstringop_truncation
,
1870 "%qD output may be truncated copying between %wu "
1871 "and %wu bytes from a string of length %wu",
1872 func
, cntrange
[0].to_uhwi (),
1873 cntrange
[1].to_uhwi (), lenrange
[1].to_uhwi ());
1876 if (cntrange
[0] != cntrange
[1]
1877 && wi::leu_p (cntrange
[0], lenrange
[0])
1878 && wi::leu_p (cntrange
[1], lenrange
[0] + 1))
1880 /* If the source (including the terminating nul) is longer than
1881 the lower bound of the specified count but shorter than the
1882 upper bound the copy may (but need not) be truncated. */
1883 return warning_at (callloc
, OPT_Wstringop_truncation
,
1884 "%qD output may be truncated copying between %wu "
1885 "and %wu bytes from a string of length %wu",
1886 func
, cntrange
[0].to_uhwi (),
1887 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
1891 if (tree dstsize
= compute_objsize (dst
, 1))
1893 /* The source length is uknown. Try to determine the destination
1894 size and see if it matches the specified bound. If not, bail.
1895 Otherwise go on to see if it should be diagnosed for possible
1900 if (wi::to_wide (dstsize
) != cntrange
[1])
1903 if (cntrange
[0] == cntrange
[1])
1904 return warning_at (callloc
, OPT_Wstringop_truncation
,
1905 "%qD specified bound %E equals destination size",
1912 /* Check the size argument to the built-in forms of stpncpy and strncpy
1913 to see if it's derived from calling strlen() on the source argument
1914 and if so, issue a warning. */
1917 handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*gsi
)
1919 if (!strlen_to_stridx
)
1922 gimple
*stmt
= gsi_stmt (*gsi
);
1924 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1926 tree src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1927 tree len
= gimple_call_arg (stmt
, with_bounds
? 3 : 2);
1929 /* If the length argument was computed from strlen(S) for some string
1930 S retrieve the strinfo index for the string (PSS->FIRST) alonng with
1931 the location of the strlen() call (PSS->SECOND). */
1932 stridx_strlenloc
*pss
= strlen_to_stridx
->get (len
);
1933 if (!pss
|| pss
->first
<= 0)
1935 if (maybe_diag_stxncpy_trunc (*gsi
, src
, len
))
1936 gimple_set_no_warning (stmt
, true);
1941 int sidx
= get_stridx (src
);
1942 strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
;
1944 /* strncat() and strncpy() can modify the source string by writing
1945 over the terminating nul so SISRC->DONT_INVALIDATE must be left
1948 /* Retrieve the strinfo data for the string S that LEN was computed
1949 from as some function F of strlen (S) (i.e., LEN need not be equal
1951 strinfo
*silen
= get_strinfo (pss
->first
);
1953 location_t callloc
= gimple_location (stmt
);
1955 tree func
= gimple_call_fndecl (stmt
);
1957 bool warned
= false;
1959 /* When -Wstringop-truncation is set, try to determine truncation
1960 before diagnosing possible overflow. Truncation is implied by
1961 the LEN argument being equal to strlen(SRC), regardless of
1962 whether its value is known. Otherwise, issue the more generic
1963 -Wstringop-overflow which triggers for LEN arguments that in
1964 any meaningful way depend on strlen(SRC). */
1966 && is_strlen_related_p (src
, len
)
1967 && warning_at (callloc
, OPT_Wstringop_truncation
,
1968 "%qD output truncated before terminating nul "
1969 "copying as many bytes from a string as its length",
1972 else if (silen
&& is_strlen_related_p (src
, silen
->ptr
))
1973 warned
= warning_at (callloc
, OPT_Wstringop_overflow_
,
1974 "%qD specified bound depends on the length "
1975 "of the source argument", func
);
1978 location_t strlenloc
= pss
->second
;
1979 if (strlenloc
!= UNKNOWN_LOCATION
&& strlenloc
!= callloc
)
1980 inform (strlenloc
, "length computed here");
1984 /* Check the size argument to the built-in forms of strncat to see if
1985 it's derived from calling strlen() on the source argument and if so,
1989 handle_builtin_strncat (built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1991 /* Same as stxncpy(). */
1992 handle_builtin_stxncpy (bcode
, gsi
);
1995 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1996 If strlen of the second argument is known and length of the third argument
1997 is that plus one, strlen of the first argument is the same after this
2001 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2004 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
2005 gimple
*stmt
= gsi_stmt (*gsi
);
2006 strinfo
*si
, *dsi
, *olddsi
;
2007 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
2009 len
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
2010 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
2011 dst
= gimple_call_arg (stmt
, 0);
2012 idx
= get_stridx (src
);
2016 didx
= get_stridx (dst
);
2019 olddsi
= get_strinfo (didx
);
2024 && tree_fits_uhwi_p (len
)
2025 && !integer_zerop (len
))
2026 adjust_last_stmt (olddsi
, stmt
, false);
2033 /* Handle memcpy (x, y, l) where l's relationship with strlen (y)
2035 si
= get_strinfo (idx
);
2036 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
2038 if (TREE_CODE (len
) == INTEGER_CST
2039 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
2041 if (tree_int_cst_le (len
, si
->nonzero_chars
))
2043 /* Copying LEN nonzero characters, where LEN is constant. */
2045 full_string_p
= false;
2049 /* Copying the whole of the analyzed part of SI. */
2050 newlen
= si
->nonzero_chars
;
2051 full_string_p
= si
->full_string_p
;
2056 if (!si
->full_string_p
)
2058 if (TREE_CODE (len
) != SSA_NAME
)
2060 def_stmt
= SSA_NAME_DEF_STMT (len
);
2061 if (!is_gimple_assign (def_stmt
)
2062 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
2063 || gimple_assign_rhs1 (def_stmt
) != si
->nonzero_chars
2064 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
2066 /* Copying variable-length string SI (and no more). */
2067 newlen
= si
->nonzero_chars
;
2068 full_string_p
= true;
2074 /* Handle memcpy (x, "abcd", 5) or
2075 memcpy (x, "abc\0uvw", 7). */
2076 if (!tree_fits_uhwi_p (len
))
2079 unsigned HOST_WIDE_INT clen
= tree_to_uhwi (len
);
2080 unsigned HOST_WIDE_INT nonzero_chars
= ~idx
;
2081 newlen
= build_int_cst (size_type_node
, MIN (nonzero_chars
, clen
));
2082 full_string_p
= clen
> nonzero_chars
;
2085 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
2086 adjust_last_stmt (olddsi
, stmt
, false);
2090 didx
= new_stridx (dst
);
2097 dsi
= unshare_strinfo (olddsi
);
2098 oldlen
= olddsi
->nonzero_chars
;
2099 dsi
->nonzero_chars
= newlen
;
2100 dsi
->full_string_p
= full_string_p
;
2101 /* Break the chain, so adjust_related_strinfo on later pointers in
2102 the chain won't adjust this one anymore. */
2105 dsi
->endptr
= NULL_TREE
;
2109 dsi
= new_strinfo (dst
, didx
, newlen
, full_string_p
);
2110 set_strinfo (didx
, dsi
);
2111 find_equal_ptrs (dst
, didx
);
2113 dsi
->writable
= true;
2114 dsi
->dont_invalidate
= true;
2117 tree adj
= NULL_TREE
;
2118 location_t loc
= gimple_location (stmt
);
2119 if (oldlen
== NULL_TREE
)
2121 else if (integer_zerop (oldlen
))
2123 else if (TREE_CODE (oldlen
) == INTEGER_CST
2124 || TREE_CODE (newlen
) == INTEGER_CST
)
2125 adj
= fold_build2_loc (loc
, MINUS_EXPR
, TREE_TYPE (newlen
), newlen
,
2126 fold_convert_loc (loc
, TREE_TYPE (newlen
),
2128 if (adj
!= NULL_TREE
)
2129 adjust_related_strinfos (loc
, dsi
, adj
);
2133 /* memcpy src may not overlap dst, so src doesn't need to be
2134 invalidated either. */
2136 si
->dont_invalidate
= true;
2140 lhs
= gimple_call_lhs (stmt
);
2143 case BUILT_IN_MEMCPY
:
2144 case BUILT_IN_MEMCPY_CHK
:
2145 case BUILT_IN_MEMCPY_CHKP
:
2146 case BUILT_IN_MEMCPY_CHK_CHKP
:
2147 /* Allow adjust_last_stmt to decrease this memcpy's size. */
2148 laststmt
.stmt
= stmt
;
2149 laststmt
.len
= dsi
->nonzero_chars
;
2150 laststmt
.stridx
= dsi
->idx
;
2152 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
2154 case BUILT_IN_MEMPCPY
:
2155 case BUILT_IN_MEMPCPY_CHK
:
2156 case BUILT_IN_MEMPCPY_CHKP
:
2157 case BUILT_IN_MEMPCPY_CHK_CHKP
:
2165 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
2166 If strlen of the second argument is known, strlen of the first argument
2167 is increased by the length of the second argument. Furthermore, attempt
2168 to convert it to memcpy/strcpy if the length of the first argument
2172 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2175 tree src
, dst
, srclen
, dstlen
, len
, lhs
, args
, type
, fn
, objsz
, endptr
;
2177 gimple
*stmt
= gsi_stmt (*gsi
);
2180 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
2182 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
2183 dst
= gimple_call_arg (stmt
, 0);
2184 lhs
= gimple_call_lhs (stmt
);
2186 didx
= get_stridx (dst
);
2192 dsi
= get_strinfo (didx
);
2193 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
2195 /* strcat (p, q) can be transformed into
2196 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
2197 with length endptr - p if we need to compute the length
2198 later on. Don't do this transformation if we don't need
2200 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
2204 didx
= new_stridx (dst
);
2210 dsi
= new_strinfo (dst
, didx
, NULL_TREE
, false);
2211 set_strinfo (didx
, dsi
);
2212 find_equal_ptrs (dst
, didx
);
2216 dsi
= unshare_strinfo (dsi
);
2217 dsi
->nonzero_chars
= NULL_TREE
;
2218 dsi
->full_string_p
= false;
2220 dsi
->endptr
= NULL_TREE
;
2222 dsi
->writable
= true;
2224 dsi
->dont_invalidate
= true;
2231 idx
= get_stridx (src
);
2233 srclen
= build_int_cst (size_type_node
, ~idx
);
2236 si
= get_strinfo (idx
);
2238 srclen
= get_string_length (si
);
2241 loc
= gimple_location (stmt
);
2242 dstlen
= dsi
->nonzero_chars
;
2243 endptr
= dsi
->endptr
;
2245 dsi
= unshare_strinfo (dsi
);
2246 dsi
->endptr
= NULL_TREE
;
2248 dsi
->writable
= true;
2250 if (srclen
!= NULL_TREE
)
2252 dsi
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
2253 TREE_TYPE (dsi
->nonzero_chars
),
2254 dsi
->nonzero_chars
, srclen
);
2255 gcc_assert (dsi
->full_string_p
);
2256 adjust_related_strinfos (loc
, dsi
, srclen
);
2257 dsi
->dont_invalidate
= true;
2261 dsi
->nonzero_chars
= NULL
;
2262 dsi
->full_string_p
= false;
2263 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
2264 dsi
->dont_invalidate
= true;
2268 /* strcat src may not overlap dst, so src doesn't need to be
2269 invalidated either. */
2270 si
->dont_invalidate
= true;
2272 /* For now. Could remove the lhs from the call and add
2273 lhs = dst; afterwards. */
2281 case BUILT_IN_STRCAT
:
2282 case BUILT_IN_STRCAT_CHKP
:
2283 if (srclen
!= NULL_TREE
)
2284 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
2286 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
2288 case BUILT_IN_STRCAT_CHK
:
2289 case BUILT_IN_STRCAT_CHK_CHKP
:
2290 if (srclen
!= NULL_TREE
)
2291 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
2293 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
2294 objsz
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
2300 if (fn
== NULL_TREE
)
2304 if (srclen
!= NULL_TREE
)
2306 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
2307 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
2309 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
2310 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
2311 build_int_cst (type
, 1));
2312 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
2316 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
2318 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
2319 TREE_TYPE (dst
), unshare_expr (dst
),
2320 fold_convert_loc (loc
, sizetype
,
2321 unshare_expr (dstlen
)));
2322 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
2324 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2326 fprintf (dump_file
, "Optimizing: ");
2327 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2331 fn
= chkp_maybe_create_clone (fn
)->decl
;
2332 if (srclen
!= NULL_TREE
)
2333 success
= update_gimple_call (gsi
, fn
, 5 + (objsz
!= NULL_TREE
),
2335 gimple_call_arg (stmt
, 1),
2337 gimple_call_arg (stmt
, 3),
2340 success
= update_gimple_call (gsi
, fn
, 4 + (objsz
!= NULL_TREE
),
2342 gimple_call_arg (stmt
, 1),
2344 gimple_call_arg (stmt
, 3),
2348 if (srclen
!= NULL_TREE
)
2349 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
2350 dst
, src
, len
, objsz
);
2352 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
2356 stmt
= gsi_stmt (*gsi
);
2357 gimple_call_set_with_bounds (stmt
, with_bounds
);
2359 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2361 fprintf (dump_file
, "into: ");
2362 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2364 /* If srclen == NULL, note that current string length can be
2365 computed by transforming this strcpy into stpcpy. */
2366 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
2368 adjust_last_stmt (dsi
, stmt
, true);
2369 if (srclen
!= NULL_TREE
)
2371 laststmt
.stmt
= stmt
;
2372 laststmt
.len
= srclen
;
2373 laststmt
.stridx
= dsi
->idx
;
2376 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2377 fprintf (dump_file
, "not possible.\n");
2380 /* Handle a call to malloc or calloc. */
2383 handle_builtin_malloc (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2385 gimple
*stmt
= gsi_stmt (*gsi
);
2386 tree lhs
= gimple_call_lhs (stmt
);
2387 if (lhs
== NULL_TREE
)
2390 gcc_assert (get_stridx (lhs
) == 0);
2391 int idx
= new_stridx (lhs
);
2392 tree length
= NULL_TREE
;
2393 if (bcode
== BUILT_IN_CALLOC
)
2394 length
= build_int_cst (size_type_node
, 0);
2395 strinfo
*si
= new_strinfo (lhs
, idx
, length
, length
!= NULL_TREE
);
2396 if (bcode
== BUILT_IN_CALLOC
)
2398 set_strinfo (idx
, si
);
2399 si
->writable
= true;
2401 si
->dont_invalidate
= true;
2404 /* Handle a call to memset.
2405 After a call to calloc, memset(,0,) is unnecessary.
2406 memset(malloc(n),0,n) is calloc(n,1). */
2409 handle_builtin_memset (gimple_stmt_iterator
*gsi
)
2411 gimple
*stmt2
= gsi_stmt (*gsi
);
2412 if (!integer_zerop (gimple_call_arg (stmt2
, 1)))
2414 tree ptr
= gimple_call_arg (stmt2
, 0);
2415 int idx1
= get_stridx (ptr
);
2418 strinfo
*si1
= get_strinfo (idx1
);
2421 gimple
*stmt1
= si1
->stmt
;
2422 if (!stmt1
|| !is_gimple_call (stmt1
))
2424 tree callee1
= gimple_call_fndecl (stmt1
);
2425 if (!valid_builtin_call (stmt1
))
2427 enum built_in_function code1
= DECL_FUNCTION_CODE (callee1
);
2428 tree size
= gimple_call_arg (stmt2
, 2);
2429 if (code1
== BUILT_IN_CALLOC
)
2430 /* Not touching stmt1 */ ;
2431 else if (code1
== BUILT_IN_MALLOC
2432 && operand_equal_p (gimple_call_arg (stmt1
, 0), size
, 0))
2434 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt1
);
2435 update_gimple_call (&gsi1
, builtin_decl_implicit (BUILT_IN_CALLOC
), 2,
2436 size
, build_one_cst (size_type_node
));
2437 si1
->nonzero_chars
= build_int_cst (size_type_node
, 0);
2438 si1
->full_string_p
= true;
2439 si1
->stmt
= gsi_stmt (gsi1
);
2443 tree lhs
= gimple_call_lhs (stmt2
);
2444 unlink_stmt_vdef (stmt2
);
2447 gimple
*assign
= gimple_build_assign (lhs
, ptr
);
2448 gsi_replace (gsi
, assign
, false);
2452 gsi_remove (gsi
, true);
2453 release_defs (stmt2
);
2459 /* Handle a call to memcmp. We try to handle small comparisons by
2460 converting them to load and compare, and replacing the call to memcmp
2461 with a __builtin_memcmp_eq call where possible. */
2464 handle_builtin_memcmp (gimple_stmt_iterator
*gsi
)
2466 gcall
*stmt2
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2467 tree res
= gimple_call_lhs (stmt2
);
2468 tree arg1
= gimple_call_arg (stmt2
, 0);
2469 tree arg2
= gimple_call_arg (stmt2
, 1);
2470 tree len
= gimple_call_arg (stmt2
, 2);
2471 unsigned HOST_WIDE_INT leni
;
2472 use_operand_p use_p
;
2473 imm_use_iterator iter
;
2478 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
2480 gimple
*ustmt
= USE_STMT (use_p
);
2482 if (is_gimple_debug (ustmt
))
2484 if (gimple_code (ustmt
) == GIMPLE_ASSIGN
)
2486 gassign
*asgn
= as_a
<gassign
*> (ustmt
);
2487 tree_code code
= gimple_assign_rhs_code (asgn
);
2488 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2489 || !integer_zerop (gimple_assign_rhs2 (asgn
)))
2492 else if (gimple_code (ustmt
) == GIMPLE_COND
)
2494 tree_code code
= gimple_cond_code (ustmt
);
2495 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2496 || !integer_zerop (gimple_cond_rhs (ustmt
)))
2503 if (tree_fits_uhwi_p (len
)
2504 && (leni
= tree_to_uhwi (len
)) <= GET_MODE_SIZE (word_mode
)
2505 && pow2p_hwi (leni
))
2507 leni
*= CHAR_TYPE_SIZE
;
2508 unsigned align1
= get_pointer_alignment (arg1
);
2509 unsigned align2
= get_pointer_alignment (arg2
);
2510 unsigned align
= MIN (align1
, align2
);
2511 scalar_int_mode mode
;
2512 if (int_mode_for_size (leni
, 1).exists (&mode
)
2513 && (align
>= leni
|| !targetm
.slow_unaligned_access (mode
, align
)))
2515 location_t loc
= gimple_location (stmt2
);
2517 type
= build_nonstandard_integer_type (leni
, 1);
2518 gcc_assert (GET_MODE_BITSIZE (TYPE_MODE (type
)) == leni
);
2519 tree ptrtype
= build_pointer_type_for_mode (char_type_node
,
2521 off
= build_int_cst (ptrtype
, 0);
2522 arg1
= build2_loc (loc
, MEM_REF
, type
, arg1
, off
);
2523 arg2
= build2_loc (loc
, MEM_REF
, type
, arg2
, off
);
2524 tree tem1
= fold_const_aggregate_ref (arg1
);
2527 tree tem2
= fold_const_aggregate_ref (arg2
);
2530 res
= fold_convert_loc (loc
, TREE_TYPE (res
),
2531 fold_build2_loc (loc
, NE_EXPR
,
2534 gimplify_and_update_call_from_tree (gsi
, res
);
2539 gimple_call_set_fndecl (stmt2
, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ
));
2543 /* Handle a POINTER_PLUS_EXPR statement.
2544 For p = "abcd" + 2; compute associated length, or if
2545 p = q + off is pointing to a '\0' character of a string, call
2546 zero_length_string on it. */
2549 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
2551 gimple
*stmt
= gsi_stmt (*gsi
);
2552 tree lhs
= gimple_assign_lhs (stmt
), off
;
2553 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
2561 tree off
= gimple_assign_rhs2 (stmt
);
2562 if (tree_fits_uhwi_p (off
)
2563 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
2564 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
2565 = ~(~idx
- (int) tree_to_uhwi (off
));
2569 si
= get_strinfo (idx
);
2570 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
2573 off
= gimple_assign_rhs2 (stmt
);
2575 if (si
->full_string_p
&& operand_equal_p (si
->nonzero_chars
, off
, 0))
2576 zsi
= zero_length_string (lhs
, si
);
2577 else if (TREE_CODE (off
) == SSA_NAME
)
2579 gimple
*def_stmt
= SSA_NAME_DEF_STMT (off
);
2580 if (gimple_assign_single_p (def_stmt
)
2581 && si
->full_string_p
2582 && operand_equal_p (si
->nonzero_chars
,
2583 gimple_assign_rhs1 (def_stmt
), 0))
2584 zsi
= zero_length_string (lhs
, si
);
2587 && si
->endptr
!= NULL_TREE
2588 && si
->endptr
!= lhs
2589 && TREE_CODE (si
->endptr
) == SSA_NAME
)
2591 enum tree_code rhs_code
2592 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
2593 ? SSA_NAME
: NOP_EXPR
;
2594 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
);
2595 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2600 /* Handle a single character store. */
2603 handle_char_store (gimple_stmt_iterator
*gsi
)
2607 gimple
*stmt
= gsi_stmt (*gsi
);
2608 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
2609 tree rhs
= gimple_assign_rhs1 (stmt
);
2610 unsigned HOST_WIDE_INT offset
= 0;
2612 if (TREE_CODE (lhs
) == MEM_REF
2613 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
2615 tree mem_offset
= TREE_OPERAND (lhs
, 1);
2616 if (tree_fits_uhwi_p (mem_offset
))
2618 /* Get the strinfo for the base, and use it if it starts with at
2619 least OFFSET nonzero characters. This is trivially true if
2621 offset
= tree_to_uhwi (mem_offset
);
2622 idx
= get_stridx (TREE_OPERAND (lhs
, 0));
2624 si
= get_strinfo (idx
);
2626 ssaname
= TREE_OPERAND (lhs
, 0);
2627 else if (si
== NULL
|| compare_nonzero_chars (si
, offset
) < 0)
2633 idx
= get_addr_stridx (lhs
, NULL_TREE
, &offset
);
2635 si
= get_strinfo (idx
);
2638 bool storing_zero_p
= initializer_zerop (rhs
);
2639 bool storing_nonzero_p
= (!storing_zero_p
2640 && TREE_CODE (rhs
) == INTEGER_CST
2641 && integer_nonzerop (rhs
));
2645 int cmp
= compare_nonzero_chars (si
, offset
);
2646 gcc_assert (offset
== 0 || cmp
>= 0);
2647 if (storing_zero_p
&& cmp
== 0 && si
->full_string_p
)
2649 /* When overwriting a '\0' with a '\0', the store can be removed
2650 if we know it has been stored in the current function. */
2651 if (!stmt_could_throw_p (stmt
) && si
->writable
)
2653 unlink_stmt_vdef (stmt
);
2654 release_defs (stmt
);
2655 gsi_remove (gsi
, true);
2660 si
->writable
= true;
2665 /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0',
2666 and if we aren't storing '\0', we know that the length of the
2667 string and any other zero terminated string in memory remains
2668 the same. In that case we move to the next gimple statement and
2669 return to signal the caller that it shouldn't invalidate anything.
2671 This is benefical for cases like:
2676 strcpy (p, "foobar");
2677 size_t len = strlen (p); // This can be optimized into 6
2678 size_t len2 = strlen (q); // This has to be computed
2680 size_t len3 = strlen (p); // This can be optimized into 6
2681 size_t len4 = strlen (q); // This can be optimized into len2
2682 bar (len, len2, len3, len4);
2685 else if (storing_nonzero_p
&& cmp
> 0)
2690 else if (storing_zero_p
|| storing_nonzero_p
|| (offset
!= 0 && cmp
> 0))
2692 /* When storing_nonzero_p, we know that the string now starts
2693 with OFFSET + 1 nonzero characters, but don't know whether
2694 there's a following nul terminator.
2696 When storing_zero_p, we know that the string is now OFFSET
2699 Otherwise, we're storing an unknown value at offset OFFSET,
2700 so need to clip the nonzero_chars to OFFSET. */
2701 location_t loc
= gimple_location (stmt
);
2702 tree oldlen
= si
->nonzero_chars
;
2703 if (cmp
== 0 && si
->full_string_p
)
2704 /* We're overwriting the nul terminator with a nonzero or
2705 unknown character. If the previous stmt was a memcpy,
2706 its length may be decreased. */
2707 adjust_last_stmt (si
, stmt
, false);
2708 si
= unshare_strinfo (si
);
2709 if (storing_nonzero_p
)
2710 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
+ 1);
2712 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
);
2713 si
->full_string_p
= storing_zero_p
;
2716 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
2717 si
->endptr
= ssaname
;
2722 si
->writable
= true;
2723 si
->dont_invalidate
= true;
2726 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
2727 si
->nonzero_chars
, oldlen
);
2728 adjust_related_strinfos (loc
, si
, adj
);
2734 else if (idx
== 0 && (storing_zero_p
|| storing_nonzero_p
))
2737 idx
= new_stridx (ssaname
);
2739 idx
= new_addr_stridx (lhs
);
2742 tree ptr
= (ssaname
? ssaname
: build_fold_addr_expr (lhs
));
2743 tree len
= storing_nonzero_p
? size_one_node
: size_zero_node
;
2744 si
= new_strinfo (ptr
, idx
, len
, storing_zero_p
);
2745 set_strinfo (idx
, si
);
2748 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
2749 si
->endptr
= ssaname
;
2750 si
->dont_invalidate
= true;
2751 si
->writable
= true;
2755 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == STRING_CST
2756 && ssaname
== NULL_TREE
2757 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
2759 size_t l
= strlen (TREE_STRING_POINTER (gimple_assign_rhs1 (stmt
)));
2760 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
2761 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> l
)
2763 int idx
= new_addr_stridx (lhs
);
2766 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
2767 build_int_cst (size_type_node
, l
), true);
2768 set_strinfo (idx
, si
);
2769 si
->dont_invalidate
= true;
2774 if (si
!= NULL
&& offset
== 0 && storing_zero_p
)
2776 /* Allow adjust_last_stmt to remove it if the stored '\0'
2777 is immediately overwritten. */
2778 laststmt
.stmt
= stmt
;
2779 laststmt
.len
= build_int_cst (size_type_node
, 1);
2780 laststmt
.stridx
= si
->idx
;
2785 /* Try to fold strstr (s, t) eq/ne s to strncmp (s, t, strlen (t)) eq/ne 0. */
2788 fold_strstr_to_strncmp (tree rhs1
, tree rhs2
, gimple
*stmt
)
2790 if (TREE_CODE (rhs1
) != SSA_NAME
2791 || TREE_CODE (rhs2
) != SSA_NAME
)
2794 gimple
*call_stmt
= NULL
;
2795 for (int pass
= 0; pass
< 2; pass
++)
2797 gimple
*g
= SSA_NAME_DEF_STMT (rhs1
);
2798 if (gimple_call_builtin_p (g
, BUILT_IN_STRSTR
)
2799 && has_single_use (rhs1
)
2800 && gimple_call_arg (g
, 0) == rhs2
)
2805 std::swap (rhs1
, rhs2
);
2810 tree arg0
= gimple_call_arg (call_stmt
, 0);
2814 tree arg1
= gimple_call_arg (call_stmt
, 1);
2815 tree arg1_len
= NULL_TREE
;
2816 int idx
= get_stridx (arg1
);
2821 arg1_len
= build_int_cst (size_type_node
, ~idx
);
2824 strinfo
*si
= get_strinfo (idx
);
2826 arg1_len
= get_string_length (si
);
2830 if (arg1_len
!= NULL_TREE
)
2832 gimple_stmt_iterator gsi
= gsi_for_stmt (call_stmt
);
2833 tree strncmp_decl
= builtin_decl_explicit (BUILT_IN_STRNCMP
);
2834 gcall
*strncmp_call
= gimple_build_call (strncmp_decl
, 3,
2835 arg0
, arg1
, arg1_len
);
2836 tree strncmp_lhs
= make_ssa_name (integer_type_node
);
2837 gimple_set_vuse (strncmp_call
, gimple_vuse (call_stmt
));
2838 gimple_call_set_lhs (strncmp_call
, strncmp_lhs
);
2839 gsi_remove (&gsi
, true);
2840 gsi_insert_before (&gsi
, strncmp_call
, GSI_SAME_STMT
);
2841 tree zero
= build_zero_cst (TREE_TYPE (strncmp_lhs
));
2843 if (is_gimple_assign (stmt
))
2845 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
2847 tree cond
= gimple_assign_rhs1 (stmt
);
2848 TREE_OPERAND (cond
, 0) = strncmp_lhs
;
2849 TREE_OPERAND (cond
, 1) = zero
;
2853 gimple_assign_set_rhs1 (stmt
, strncmp_lhs
);
2854 gimple_assign_set_rhs2 (stmt
, zero
);
2859 gcond
*cond
= as_a
<gcond
*> (stmt
);
2860 gimple_cond_set_lhs (cond
, strncmp_lhs
);
2861 gimple_cond_set_rhs (cond
, zero
);
2869 /* Attempt to optimize a single statement at *GSI using string length
2873 strlen_optimize_stmt (gimple_stmt_iterator
*gsi
)
2875 gimple
*stmt
= gsi_stmt (*gsi
);
2877 if (is_gimple_call (stmt
))
2879 tree callee
= gimple_call_fndecl (stmt
);
2880 if (valid_builtin_call (stmt
))
2881 switch (DECL_FUNCTION_CODE (callee
))
2883 case BUILT_IN_STRLEN
:
2884 case BUILT_IN_STRLEN_CHKP
:
2885 handle_builtin_strlen (gsi
);
2887 case BUILT_IN_STRCHR
:
2888 case BUILT_IN_STRCHR_CHKP
:
2889 handle_builtin_strchr (gsi
);
2891 case BUILT_IN_STRCPY
:
2892 case BUILT_IN_STRCPY_CHK
:
2893 case BUILT_IN_STPCPY
:
2894 case BUILT_IN_STPCPY_CHK
:
2895 case BUILT_IN_STRCPY_CHKP
:
2896 case BUILT_IN_STRCPY_CHK_CHKP
:
2897 case BUILT_IN_STPCPY_CHKP
:
2898 case BUILT_IN_STPCPY_CHK_CHKP
:
2899 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
2902 case BUILT_IN_STRNCAT
:
2903 case BUILT_IN_STRNCAT_CHK
:
2904 handle_builtin_strncat (DECL_FUNCTION_CODE (callee
), gsi
);
2907 case BUILT_IN_STPNCPY
:
2908 case BUILT_IN_STPNCPY_CHK
:
2909 case BUILT_IN_STRNCPY
:
2910 case BUILT_IN_STRNCPY_CHK
:
2911 handle_builtin_stxncpy (DECL_FUNCTION_CODE (callee
), gsi
);
2914 case BUILT_IN_MEMCPY
:
2915 case BUILT_IN_MEMCPY_CHK
:
2916 case BUILT_IN_MEMPCPY
:
2917 case BUILT_IN_MEMPCPY_CHK
:
2918 case BUILT_IN_MEMCPY_CHKP
:
2919 case BUILT_IN_MEMCPY_CHK_CHKP
:
2920 case BUILT_IN_MEMPCPY_CHKP
:
2921 case BUILT_IN_MEMPCPY_CHK_CHKP
:
2922 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
2924 case BUILT_IN_STRCAT
:
2925 case BUILT_IN_STRCAT_CHK
:
2926 case BUILT_IN_STRCAT_CHKP
:
2927 case BUILT_IN_STRCAT_CHK_CHKP
:
2928 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
2930 case BUILT_IN_MALLOC
:
2931 case BUILT_IN_CALLOC
:
2932 handle_builtin_malloc (DECL_FUNCTION_CODE (callee
), gsi
);
2934 case BUILT_IN_MEMSET
:
2935 if (!handle_builtin_memset (gsi
))
2938 case BUILT_IN_MEMCMP
:
2939 if (!handle_builtin_memcmp (gsi
))
2946 else if (is_gimple_assign (stmt
) && !gimple_clobber_p (stmt
))
2948 tree lhs
= gimple_assign_lhs (stmt
);
2950 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
2952 if (gimple_assign_single_p (stmt
)
2953 || (gimple_assign_cast_p (stmt
)
2954 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
2956 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
2957 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
2959 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
2960 handle_pointer_plus (gsi
);
2962 else if (TREE_CODE (lhs
) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
2964 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2965 if (code
== COND_EXPR
)
2967 tree cond
= gimple_assign_rhs1 (stmt
);
2968 enum tree_code cond_code
= TREE_CODE (cond
);
2970 if (cond_code
== EQ_EXPR
|| cond_code
== NE_EXPR
)
2971 fold_strstr_to_strncmp (TREE_OPERAND (cond
, 0),
2972 TREE_OPERAND (cond
, 1), stmt
);
2974 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
2975 fold_strstr_to_strncmp (gimple_assign_rhs1 (stmt
),
2976 gimple_assign_rhs2 (stmt
), stmt
);
2978 if (strlen_to_stridx
)
2980 tree rhs1
= gimple_assign_rhs1 (stmt
);
2981 if (stridx_strlenloc
*ps
= strlen_to_stridx
->get (rhs1
))
2982 strlen_to_stridx
->put (lhs
, stridx_strlenloc (*ps
));
2985 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
2987 tree type
= TREE_TYPE (lhs
);
2988 if (TREE_CODE (type
) == ARRAY_TYPE
)
2989 type
= TREE_TYPE (type
);
2990 if (TREE_CODE (type
) == INTEGER_TYPE
2991 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
2992 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
2994 if (! handle_char_store (gsi
))
2999 else if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
3001 enum tree_code code
= gimple_cond_code (cond
);
3002 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3003 fold_strstr_to_strncmp (gimple_cond_lhs (stmt
),
3004 gimple_cond_rhs (stmt
), stmt
);
3007 if (gimple_vdef (stmt
))
3008 maybe_invalidate (stmt
);
3012 /* Recursively call maybe_invalidate on stmts that might be executed
3013 in between dombb and current bb and that contain a vdef. Stop when
3014 *count stmts are inspected, or if the whole strinfo vector has
3015 been invalidated. */
3018 do_invalidate (basic_block dombb
, gimple
*phi
, bitmap visited
, int *count
)
3020 unsigned int i
, n
= gimple_phi_num_args (phi
);
3022 for (i
= 0; i
< n
; i
++)
3024 tree vuse
= gimple_phi_arg_def (phi
, i
);
3025 gimple
*stmt
= SSA_NAME_DEF_STMT (vuse
);
3026 basic_block bb
= gimple_bb (stmt
);
3029 || !bitmap_set_bit (visited
, bb
->index
)
3030 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3034 if (gimple_code (stmt
) == GIMPLE_PHI
)
3036 do_invalidate (dombb
, stmt
, visited
, count
);
3043 if (!maybe_invalidate (stmt
))
3048 vuse
= gimple_vuse (stmt
);
3049 stmt
= SSA_NAME_DEF_STMT (vuse
);
3050 if (gimple_bb (stmt
) != bb
)
3052 bb
= gimple_bb (stmt
);
3055 || !bitmap_set_bit (visited
, bb
->index
)
3056 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3063 class strlen_dom_walker
: public dom_walker
3066 strlen_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
3068 virtual edge
before_dom_children (basic_block
);
3069 virtual void after_dom_children (basic_block
);
3072 /* Callback for walk_dominator_tree. Attempt to optimize various
3073 string ops by remembering string lengths pointed by pointer SSA_NAMEs. */
3076 strlen_dom_walker::before_dom_children (basic_block bb
)
3078 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
3081 stridx_to_strinfo
= NULL
;
3084 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) dombb
->aux
);
3085 if (stridx_to_strinfo
)
3087 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3090 gphi
*phi
= gsi
.phi ();
3091 if (virtual_operand_p (gimple_phi_result (phi
)))
3093 bitmap visited
= BITMAP_ALLOC (NULL
);
3094 int count_vdef
= 100;
3095 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
3096 BITMAP_FREE (visited
);
3097 if (count_vdef
== 0)
3099 /* If there were too many vdefs in between immediate
3100 dominator and current bb, invalidate everything.
3101 If stridx_to_strinfo has been unshared, we need
3102 to free it, otherwise just set it to NULL. */
3103 if (!strinfo_shared ())
3109 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
3113 (*stridx_to_strinfo
)[i
] = NULL
;
3117 stridx_to_strinfo
= NULL
;
3125 /* If all PHI arguments have the same string index, the PHI result
3127 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3130 gphi
*phi
= gsi
.phi ();
3131 tree result
= gimple_phi_result (phi
);
3132 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
3134 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
3137 unsigned int i
, n
= gimple_phi_num_args (phi
);
3138 for (i
= 1; i
< n
; i
++)
3139 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
3142 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
3147 /* Attempt to optimize individual statements. */
3148 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
3149 if (strlen_optimize_stmt (&gsi
))
3152 bb
->aux
= stridx_to_strinfo
;
3153 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
3154 (*stridx_to_strinfo
)[0] = (strinfo
*) bb
;
3158 /* Callback for walk_dominator_tree. Free strinfo vector if it is
3159 owned by the current bb, clear bb->aux. */
3162 strlen_dom_walker::after_dom_children (basic_block bb
)
3166 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) bb
->aux
);
3167 if (vec_safe_length (stridx_to_strinfo
)
3168 && (*stridx_to_strinfo
)[0] == (strinfo
*) bb
)
3173 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
3175 vec_free (stridx_to_strinfo
);
3181 /* Main entry point. */
3185 const pass_data pass_data_strlen
=
3187 GIMPLE_PASS
, /* type */
3188 "strlen", /* name */
3189 OPTGROUP_NONE
, /* optinfo_flags */
3190 TV_TREE_STRLEN
, /* tv_id */
3191 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3192 0, /* properties_provided */
3193 0, /* properties_destroyed */
3194 0, /* todo_flags_start */
3195 0, /* todo_flags_finish */
3198 class pass_strlen
: public gimple_opt_pass
3201 pass_strlen (gcc::context
*ctxt
)
3202 : gimple_opt_pass (pass_data_strlen
, ctxt
)
3205 /* opt_pass methods: */
3206 virtual bool gate (function
*) { return flag_optimize_strlen
!= 0; }
3207 virtual unsigned int execute (function
*);
3209 }; // class pass_strlen
3212 pass_strlen::execute (function
*fun
)
3214 gcc_assert (!strlen_to_stridx
);
3215 if (warn_stringop_overflow
|| warn_stringop_truncation
)
3216 strlen_to_stridx
= new hash_map
<tree
, stridx_strlenloc
> ();
3218 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
3221 calculate_dominance_info (CDI_DOMINATORS
);
3223 /* String length optimization is implemented as a walk of the dominator
3224 tree and a forward walk of statements within each block. */
3225 strlen_dom_walker (CDI_DOMINATORS
).walk (fun
->cfg
->x_entry_block_ptr
);
3227 ssa_ver_to_stridx
.release ();
3228 strinfo_pool
.release ();
3229 if (decl_to_stridxlist_htab
)
3231 obstack_free (&stridx_obstack
, NULL
);
3232 delete decl_to_stridxlist_htab
;
3233 decl_to_stridxlist_htab
= NULL
;
3235 laststmt
.stmt
= NULL
;
3236 laststmt
.len
= NULL_TREE
;
3237 laststmt
.stridx
= 0;
3239 if (strlen_to_stridx
)
3241 strlen_to_stridx
->empty ();
3242 delete strlen_to_stridx
;
3243 strlen_to_stridx
= NULL
;
3252 make_pass_strlen (gcc::context
*ctxt
)
3254 return new pass_strlen (ctxt
);