1 /* String length optimization
2 Copyright (C) 2011-2018 Free Software Foundation, Inc.
3 Contributed by Jakub Jelinek <jakub@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "alloc-pool.h"
29 #include "tree-pass.h"
32 #include "gimple-pretty-print.h"
33 #include "gimple-ssa-warn-restrict.h"
34 #include "fold-const.h"
35 #include "stor-layout.h"
36 #include "gimple-fold.h"
39 #include "gimple-iterator.h"
40 #include "gimplify-me.h"
45 #include "tree-ssa-alias.h"
46 #include "tree-ssa-propagate.h"
47 #include "tree-ssa-strlen.h"
49 #include "tree-hash-traits.h"
50 #include "tree-object-size.h"
53 #include "diagnostic-core.h"
54 #include "diagnostic.h"
59 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
60 is an index into strinfo vector, negative value stands for
61 string length of a string literal (~strlen). */
62 static vec
<int> ssa_ver_to_stridx
;
64 /* Number of currently active string indexes plus one. */
65 static int max_stridx
;
67 /* String information record. */
70 /* Number of leading characters that are known to be nonzero. This is
71 also the length of the string if FULL_STRING_P.
73 The values in a list of related string pointers must be consistent;
74 that is, if strinfo B comes X bytes after strinfo A, it must be
75 the case that A->nonzero_chars == X + B->nonzero_chars. */
77 /* Any of the corresponding pointers for querying alias oracle. */
79 /* This is used for two things:
81 - To record the statement that should be used for delayed length
82 computations. We maintain the invariant that all related strinfos
83 have delayed lengths or none do.
85 - To record the malloc or calloc call that produced this result. */
87 /* Pointer to '\0' if known, if NULL, it can be computed as
90 /* Reference count. Any changes to strinfo entry possibly shared
91 with dominating basic blocks need unshare_strinfo first, except
92 for dont_invalidate which affects only the immediately next
95 /* Copy of index. get_strinfo (si->idx) should return si; */
97 /* These 3 fields are for chaining related string pointers together.
99 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
100 strcpy (c, d); e = c + dl;
101 strinfo(a) -> strinfo(c) -> strinfo(e)
102 All have ->first field equal to strinfo(a)->idx and are doubly
103 chained through prev/next fields. The later strinfos are required
104 to point into the same string with zero or more bytes after
105 the previous pointer and all bytes in between the two pointers
106 must be non-zero. Functions like strcpy or memcpy are supposed
107 to adjust all previous strinfo lengths, but not following strinfo
108 lengths (those are uncertain, usually invalidated during
109 maybe_invalidate, except when the alias oracle knows better).
110 Functions like strcat on the other side adjust the whole
111 related strinfo chain.
112 They are updated lazily, so to use the chain the same first fields
113 and si->prev->next == si->idx needs to be verified. */
117 /* A flag whether the string is known to be written in the current
120 /* A flag for the next maybe_invalidate that this strinfo shouldn't
121 be invalidated. Always cleared by maybe_invalidate. */
122 bool dont_invalidate
;
123 /* True if the string is known to be nul-terminated after NONZERO_CHARS
124 characters. False is useful when detecting strings that are built
125 up via successive memcpys. */
129 /* Pool for allocating strinfo_struct entries. */
130 static object_allocator
<strinfo
> strinfo_pool ("strinfo pool");
132 /* Vector mapping positive string indexes to strinfo, for the
133 current basic block. The first pointer in the vector is special,
134 it is either NULL, meaning the vector isn't shared, or it is
135 a basic block pointer to the owner basic_block if shared.
136 If some other bb wants to modify the vector, the vector needs
137 to be unshared first, and only the owner bb is supposed to free it. */
138 static vec
<strinfo
*, va_heap
, vl_embed
> *stridx_to_strinfo
;
140 /* One OFFSET->IDX mapping. */
143 struct stridxlist
*next
;
144 HOST_WIDE_INT offset
;
148 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
149 struct decl_stridxlist_map
151 struct tree_map_base base
;
152 struct stridxlist list
;
155 /* Hash table for mapping decls to a chained list of offset -> idx
157 static hash_map
<tree_decl_hash
, stridxlist
> *decl_to_stridxlist_htab
;
159 /* Hash table mapping strlen calls to stridx instances describing
160 the calls' arguments. Non-null only when warn_stringop_truncation
162 typedef std::pair
<int, location_t
> stridx_strlenloc
;
163 static hash_map
<tree
, stridx_strlenloc
> *strlen_to_stridx
;
165 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
166 static struct obstack stridx_obstack
;
168 /* Last memcpy statement if it could be adjusted if the trailing
169 '\0' written is immediately overwritten, or
170 *x = '\0' store that could be removed if it is immediately overwritten. */
171 struct laststmt_struct
178 static int get_stridx_plus_constant (strinfo
*, unsigned HOST_WIDE_INT
, tree
);
179 static void handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*);
183 - 1 if SI is known to start with more than OFF nonzero characters.
185 - 0 if SI is known to start with OFF nonzero characters,
186 but is not known to start with more.
188 - -1 if SI might not start with OFF nonzero characters. */
191 compare_nonzero_chars (strinfo
*si
, unsigned HOST_WIDE_INT off
)
193 if (si
->nonzero_chars
194 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
195 return compare_tree_int (si
->nonzero_chars
, off
);
200 /* Return true if SI is known to be a zero-length string. */
203 zero_length_string_p (strinfo
*si
)
205 return si
->full_string_p
&& integer_zerop (si
->nonzero_chars
);
208 /* Return strinfo vector entry IDX. */
210 static inline strinfo
*
211 get_strinfo (int idx
)
213 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
215 return (*stridx_to_strinfo
)[idx
];
218 /* Get the next strinfo in the chain after SI, or null if none. */
220 static inline strinfo
*
221 get_next_strinfo (strinfo
*si
)
225 strinfo
*nextsi
= get_strinfo (si
->next
);
226 if (nextsi
== NULL
|| nextsi
->first
!= si
->first
|| nextsi
->prev
!= si
->idx
)
231 /* Helper function for get_stridx. Return the strinfo index of the address
232 of EXP, which is available in PTR if nonnull. If OFFSET_OUT, it is
233 OK to return the index for some X <= &EXP and store &EXP - X in
237 get_addr_stridx (tree exp
, tree ptr
, unsigned HOST_WIDE_INT
*offset_out
)
240 struct stridxlist
*list
, *last
= NULL
;
243 if (!decl_to_stridxlist_htab
)
247 base
= get_addr_base_and_unit_offset (exp
, &poff
);
248 if (base
== NULL
|| !DECL_P (base
) || !poff
.is_constant (&off
))
251 list
= decl_to_stridxlist_htab
->get (base
);
257 if (list
->offset
== off
)
263 if (list
->offset
> off
)
270 if ((offset_out
|| ptr
) && last
&& last
->idx
> 0)
272 unsigned HOST_WIDE_INT rel_off
273 = (unsigned HOST_WIDE_INT
) off
- last
->offset
;
274 strinfo
*si
= get_strinfo (last
->idx
);
275 if (si
&& compare_nonzero_chars (si
, rel_off
) >= 0)
279 *offset_out
= rel_off
;
283 return get_stridx_plus_constant (si
, rel_off
, ptr
);
289 /* Return string index for EXP. */
292 get_stridx (tree exp
)
296 if (TREE_CODE (exp
) == SSA_NAME
)
298 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)])
299 return ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)];
302 HOST_WIDE_INT off
= 0;
303 for (i
= 0; i
< 5; i
++)
305 gimple
*def_stmt
= SSA_NAME_DEF_STMT (e
);
306 if (!is_gimple_assign (def_stmt
)
307 || gimple_assign_rhs_code (def_stmt
) != POINTER_PLUS_EXPR
)
309 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
310 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
311 if (TREE_CODE (rhs1
) != SSA_NAME
312 || !tree_fits_shwi_p (rhs2
))
314 HOST_WIDE_INT this_off
= tree_to_shwi (rhs2
);
317 off
= (unsigned HOST_WIDE_INT
) off
+ this_off
;
320 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)])
323 = get_strinfo (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)]);
324 if (si
&& compare_nonzero_chars (si
, off
) >= 0)
325 return get_stridx_plus_constant (si
, off
, exp
);
332 if (TREE_CODE (exp
) == ADDR_EXPR
)
334 int idx
= get_addr_stridx (TREE_OPERAND (exp
, 0), exp
, NULL
);
339 s
= string_constant (exp
, &o
);
341 && (o
== NULL_TREE
|| tree_fits_shwi_p (o
))
342 && TREE_STRING_LENGTH (s
) > 0)
344 HOST_WIDE_INT offset
= o
? tree_to_shwi (o
) : 0;
345 const char *p
= TREE_STRING_POINTER (s
);
346 int max
= TREE_STRING_LENGTH (s
) - 1;
348 if (p
[max
] == '\0' && offset
>= 0 && offset
<= max
)
349 return ~(int) strlen (p
+ offset
);
354 /* Return true if strinfo vector is shared with the immediate dominator. */
357 strinfo_shared (void)
359 return vec_safe_length (stridx_to_strinfo
)
360 && (*stridx_to_strinfo
)[0] != NULL
;
363 /* Unshare strinfo vector that is shared with the immediate dominator. */
366 unshare_strinfo_vec (void)
371 gcc_assert (strinfo_shared ());
372 stridx_to_strinfo
= vec_safe_copy (stridx_to_strinfo
);
373 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
376 (*stridx_to_strinfo
)[0] = NULL
;
379 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
380 Return a pointer to the location where the string index can
381 be stored (if 0) or is stored, or NULL if this can't be tracked. */
384 addr_stridxptr (tree exp
)
389 tree base
= get_addr_base_and_unit_offset (exp
, &poff
);
390 if (base
== NULL_TREE
|| !DECL_P (base
) || !poff
.is_constant (&off
))
393 if (!decl_to_stridxlist_htab
)
395 decl_to_stridxlist_htab
396 = new hash_map
<tree_decl_hash
, stridxlist
> (64);
397 gcc_obstack_init (&stridx_obstack
);
401 stridxlist
*list
= &decl_to_stridxlist_htab
->get_or_insert (base
, &existed
);
405 stridxlist
*before
= NULL
;
406 for (i
= 0; i
< 32; i
++)
408 if (list
->offset
== off
)
410 if (list
->offset
> off
&& before
== NULL
)
412 if (list
->next
== NULL
)
421 before
= XOBNEW (&stridx_obstack
, struct stridxlist
);
428 list
->next
= XOBNEW (&stridx_obstack
, struct stridxlist
);
438 /* Create a new string index, or return 0 if reached limit. */
441 new_stridx (tree exp
)
444 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
446 if (TREE_CODE (exp
) == SSA_NAME
)
448 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
451 ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)] = idx
;
454 if (TREE_CODE (exp
) == ADDR_EXPR
)
456 int *pidx
= addr_stridxptr (TREE_OPERAND (exp
, 0));
459 gcc_assert (*pidx
== 0);
460 *pidx
= max_stridx
++;
467 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
470 new_addr_stridx (tree exp
)
473 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
475 pidx
= addr_stridxptr (exp
);
478 gcc_assert (*pidx
== 0);
479 *pidx
= max_stridx
++;
485 /* Create a new strinfo. */
488 new_strinfo (tree ptr
, int idx
, tree nonzero_chars
, bool full_string_p
)
490 strinfo
*si
= strinfo_pool
.allocate ();
491 si
->nonzero_chars
= nonzero_chars
;
494 si
->endptr
= NULL_TREE
;
500 si
->writable
= false;
501 si
->dont_invalidate
= false;
502 si
->full_string_p
= full_string_p
;
506 /* Decrease strinfo refcount and free it if not referenced anymore. */
509 free_strinfo (strinfo
*si
)
511 if (si
&& --si
->refcount
== 0)
512 strinfo_pool
.remove (si
);
515 /* Set strinfo in the vector entry IDX to SI. */
518 set_strinfo (int idx
, strinfo
*si
)
520 if (vec_safe_length (stridx_to_strinfo
) && (*stridx_to_strinfo
)[0])
521 unshare_strinfo_vec ();
522 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
523 vec_safe_grow_cleared (stridx_to_strinfo
, idx
+ 1);
524 (*stridx_to_strinfo
)[idx
] = si
;
527 /* Return the first strinfo in the related strinfo chain
528 if all strinfos in between belong to the chain, otherwise NULL. */
531 verify_related_strinfos (strinfo
*origsi
)
533 strinfo
*si
= origsi
, *psi
;
535 if (origsi
->first
== 0)
537 for (; si
->prev
; si
= psi
)
539 if (si
->first
!= origsi
->first
)
541 psi
= get_strinfo (si
->prev
);
544 if (psi
->next
!= si
->idx
)
547 if (si
->idx
!= si
->first
)
552 /* Set SI's endptr to ENDPTR and compute its length based on SI->ptr.
553 Use LOC for folding. */
556 set_endptr_and_length (location_t loc
, strinfo
*si
, tree endptr
)
560 tree start_as_size
= fold_convert_loc (loc
, size_type_node
, si
->ptr
);
561 tree end_as_size
= fold_convert_loc (loc
, size_type_node
, endptr
);
562 si
->nonzero_chars
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
563 end_as_size
, start_as_size
);
564 si
->full_string_p
= true;
567 /* Return string length, or NULL if it can't be computed. */
570 get_string_length (strinfo
*si
)
572 if (si
->nonzero_chars
)
573 return si
->full_string_p
? si
->nonzero_chars
: NULL
;
577 gimple
*stmt
= si
->stmt
, *lenstmt
;
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 gsi
= gsi_for_stmt (stmt
);
597 fn
= builtin_decl_implicit (BUILT_IN_STRLEN
);
598 gcc_assert (lhs
== NULL_TREE
);
599 tem
= unshare_expr (gimple_call_arg (stmt
, 0));
600 lenstmt
= gimple_build_call (fn
, 1, tem
);
601 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), lenstmt
);
602 gimple_call_set_lhs (lenstmt
, lhs
);
603 gimple_set_vuse (lenstmt
, gimple_vuse (stmt
));
604 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
605 tem
= gimple_call_arg (stmt
, 0);
606 if (!ptrofftype_p (TREE_TYPE (lhs
)))
608 lhs
= convert_to_ptrofftype (lhs
);
609 lhs
= force_gimple_operand_gsi (&gsi
, lhs
, true, NULL_TREE
,
610 true, GSI_SAME_STMT
);
612 lenstmt
= gimple_build_assign
613 (make_ssa_name (TREE_TYPE (gimple_call_arg (stmt
, 0))),
614 POINTER_PLUS_EXPR
,tem
, lhs
);
615 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
616 gimple_call_set_arg (stmt
, 0, gimple_assign_lhs (lenstmt
));
619 case BUILT_IN_STRCPY
:
620 case BUILT_IN_STRCPY_CHK
:
621 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY
));
622 if (gimple_call_num_args (stmt
) == 2)
623 fn
= builtin_decl_implicit (BUILT_IN_STPCPY
);
625 fn
= builtin_decl_explicit (BUILT_IN_STPCPY_CHK
);
626 gcc_assert (lhs
== NULL_TREE
);
627 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
629 fprintf (dump_file
, "Optimizing: ");
630 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
632 gimple_call_set_fndecl (stmt
, fn
);
633 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), stmt
);
634 gimple_call_set_lhs (stmt
, lhs
);
636 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
638 fprintf (dump_file
, "into: ");
639 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
642 case BUILT_IN_STPCPY
:
643 case BUILT_IN_STPCPY_CHK
:
644 gcc_assert (lhs
!= NULL_TREE
);
645 loc
= gimple_location (stmt
);
646 set_endptr_and_length (loc
, si
, lhs
);
647 for (strinfo
*chainsi
= verify_related_strinfos (si
);
649 chainsi
= get_next_strinfo (chainsi
))
650 if (chainsi
->nonzero_chars
== NULL
)
651 set_endptr_and_length (loc
, chainsi
, lhs
);
653 case BUILT_IN_MALLOC
:
655 /* BUILT_IN_CALLOC always has si->nonzero_chars set. */
662 return si
->nonzero_chars
;
665 /* Invalidate string length information for strings whose length
666 might change due to stores in stmt. */
669 maybe_invalidate (gimple
*stmt
)
673 bool nonempty
= false;
675 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
678 if (!si
->dont_invalidate
)
681 /* Do not use si->nonzero_chars. */
682 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, NULL_TREE
);
683 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
685 set_strinfo (i
, NULL
);
690 si
->dont_invalidate
= false;
696 /* Unshare strinfo record SI, if it has refcount > 1 or
697 if stridx_to_strinfo vector is shared with some other
701 unshare_strinfo (strinfo
*si
)
705 if (si
->refcount
== 1 && !strinfo_shared ())
708 nsi
= new_strinfo (si
->ptr
, si
->idx
, si
->nonzero_chars
, si
->full_string_p
);
709 nsi
->stmt
= si
->stmt
;
710 nsi
->endptr
= si
->endptr
;
711 nsi
->first
= si
->first
;
712 nsi
->prev
= si
->prev
;
713 nsi
->next
= si
->next
;
714 nsi
->writable
= si
->writable
;
715 set_strinfo (si
->idx
, nsi
);
720 /* Attempt to create a new strinfo for BASESI + OFF, or find existing
721 strinfo if there is any. Return it's idx, or 0 if no strinfo has
725 get_stridx_plus_constant (strinfo
*basesi
, unsigned HOST_WIDE_INT off
,
728 if (TREE_CODE (ptr
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
731 if (compare_nonzero_chars (basesi
, off
) < 0
732 || !tree_fits_uhwi_p (basesi
->nonzero_chars
))
735 unsigned HOST_WIDE_INT nonzero_chars
736 = tree_to_uhwi (basesi
->nonzero_chars
) - off
;
737 strinfo
*si
= basesi
, *chainsi
;
738 if (si
->first
|| si
->prev
|| si
->next
)
739 si
= verify_related_strinfos (basesi
);
741 || si
->nonzero_chars
== NULL_TREE
742 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
745 if (TREE_CODE (ptr
) == SSA_NAME
746 && ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
747 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
749 gcc_checking_assert (compare_tree_int (si
->nonzero_chars
, off
) != -1);
750 for (chainsi
= si
; chainsi
->next
; chainsi
= si
)
752 si
= get_next_strinfo (chainsi
);
754 || si
->nonzero_chars
== NULL_TREE
755 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
757 int r
= compare_tree_int (si
->nonzero_chars
, nonzero_chars
);
762 if (TREE_CODE (ptr
) == SSA_NAME
)
763 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = si
->idx
;
766 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
767 if (pidx
!= NULL
&& *pidx
== 0)
776 int idx
= new_stridx (ptr
);
779 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, nonzero_chars
),
780 basesi
->full_string_p
);
781 set_strinfo (idx
, si
);
782 if (strinfo
*nextsi
= get_strinfo (chainsi
->next
))
784 nextsi
= unshare_strinfo (nextsi
);
785 si
->next
= nextsi
->idx
;
788 chainsi
= unshare_strinfo (chainsi
);
789 if (chainsi
->first
== 0)
790 chainsi
->first
= chainsi
->idx
;
792 if (chainsi
->endptr
== NULL_TREE
&& zero_length_string_p (si
))
793 chainsi
->endptr
= ptr
;
794 si
->endptr
= chainsi
->endptr
;
795 si
->prev
= chainsi
->idx
;
796 si
->first
= chainsi
->first
;
797 si
->writable
= chainsi
->writable
;
801 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
802 to a zero-length string and if possible chain it to a related strinfo
803 chain whose part is or might be CHAINSI. */
806 zero_length_string (tree ptr
, strinfo
*chainsi
)
810 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
811 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
812 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
813 && ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] == 0);
815 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
819 si
= verify_related_strinfos (chainsi
);
824 /* We shouldn't mix delayed and non-delayed lengths. */
825 gcc_assert (si
->full_string_p
);
826 if (si
->endptr
== NULL_TREE
)
828 si
= unshare_strinfo (si
);
832 si
= get_next_strinfo (si
);
835 if (zero_length_string_p (chainsi
))
839 chainsi
= unshare_strinfo (chainsi
);
842 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = chainsi
->idx
;
848 /* We shouldn't mix delayed and non-delayed lengths. */
849 gcc_assert (chainsi
->full_string_p
);
850 if (chainsi
->first
|| chainsi
->prev
|| chainsi
->next
)
852 chainsi
= unshare_strinfo (chainsi
);
859 idx
= new_stridx (ptr
);
862 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, 0), true);
863 set_strinfo (idx
, si
);
867 chainsi
= unshare_strinfo (chainsi
);
868 if (chainsi
->first
== 0)
869 chainsi
->first
= chainsi
->idx
;
871 if (chainsi
->endptr
== NULL_TREE
)
872 chainsi
->endptr
= ptr
;
873 si
->prev
= chainsi
->idx
;
874 si
->first
= chainsi
->first
;
875 si
->writable
= chainsi
->writable
;
880 /* For strinfo ORIGSI whose length has been just updated, adjust other
881 related strinfos so that they match the new ORIGSI. This involves:
883 - adding ADJ to the nonzero_chars fields
884 - copying full_string_p from the new ORIGSI. */
887 adjust_related_strinfos (location_t loc
, strinfo
*origsi
, tree adj
)
889 strinfo
*si
= verify_related_strinfos (origsi
);
902 si
= unshare_strinfo (si
);
903 /* We shouldn't see delayed lengths here; the caller must have
904 calculated the old length in order to calculate the
906 gcc_assert (si
->nonzero_chars
);
907 tem
= fold_convert_loc (loc
, TREE_TYPE (si
->nonzero_chars
), adj
);
908 si
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
909 TREE_TYPE (si
->nonzero_chars
),
910 si
->nonzero_chars
, tem
);
911 si
->full_string_p
= origsi
->full_string_p
;
913 si
->endptr
= NULL_TREE
;
914 si
->dont_invalidate
= true;
916 nsi
= get_next_strinfo (si
);
923 /* Find if there are other SSA_NAME pointers equal to PTR
924 for which we don't track their string lengths yet. If so, use
928 find_equal_ptrs (tree ptr
, int idx
)
930 if (TREE_CODE (ptr
) != SSA_NAME
)
934 gimple
*stmt
= SSA_NAME_DEF_STMT (ptr
);
935 if (!is_gimple_assign (stmt
))
937 ptr
= gimple_assign_rhs1 (stmt
);
938 switch (gimple_assign_rhs_code (stmt
))
943 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)))
945 if (TREE_CODE (ptr
) == SSA_NAME
)
947 if (TREE_CODE (ptr
) != ADDR_EXPR
)
952 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
953 if (pidx
!= NULL
&& *pidx
== 0)
961 /* We might find an endptr created in this pass. Grow the
962 vector in that case. */
963 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
964 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
966 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] != 0)
968 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = idx
;
972 /* Return true if STMT is a call to a builtin function with the right
973 arguments and attributes that should be considered for optimization
977 valid_builtin_call (gimple
*stmt
)
979 if (!gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
982 tree callee
= gimple_call_fndecl (stmt
);
983 switch (DECL_FUNCTION_CODE (callee
))
985 case BUILT_IN_MEMCMP
:
986 case BUILT_IN_MEMCMP_EQ
:
987 case BUILT_IN_STRCHR
:
988 case BUILT_IN_STRLEN
:
989 /* The above functions should be pure. Punt if they aren't. */
990 if (gimple_vdef (stmt
) || gimple_vuse (stmt
) == NULL_TREE
)
994 case BUILT_IN_CALLOC
:
995 case BUILT_IN_MALLOC
:
996 case BUILT_IN_MEMCPY
:
997 case BUILT_IN_MEMCPY_CHK
:
998 case BUILT_IN_MEMPCPY
:
999 case BUILT_IN_MEMPCPY_CHK
:
1000 case BUILT_IN_MEMSET
:
1001 case BUILT_IN_STPCPY
:
1002 case BUILT_IN_STPCPY_CHK
:
1003 case BUILT_IN_STRCAT
:
1004 case BUILT_IN_STRCAT_CHK
:
1005 case BUILT_IN_STRCPY
:
1006 case BUILT_IN_STRCPY_CHK
:
1007 /* The above functions should be neither const nor pure. Punt if they
1009 if (gimple_vdef (stmt
) == NULL_TREE
|| gimple_vuse (stmt
) == NULL_TREE
)
1020 /* If the last .MEM setter statement before STMT is
1021 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
1022 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
1023 just memcpy (x, y, strlen (y)). SI must be the zero length
1027 adjust_last_stmt (strinfo
*si
, gimple
*stmt
, bool is_strcat
)
1029 tree vuse
, callee
, len
;
1030 struct laststmt_struct last
= laststmt
;
1031 strinfo
*lastsi
, *firstsi
;
1032 unsigned len_arg_no
= 2;
1034 laststmt
.stmt
= NULL
;
1035 laststmt
.len
= NULL_TREE
;
1036 laststmt
.stridx
= 0;
1038 if (last
.stmt
== NULL
)
1041 vuse
= gimple_vuse (stmt
);
1042 if (vuse
== NULL_TREE
1043 || SSA_NAME_DEF_STMT (vuse
) != last
.stmt
1044 || !has_single_use (vuse
))
1047 gcc_assert (last
.stridx
> 0);
1048 lastsi
= get_strinfo (last
.stridx
);
1054 if (lastsi
->first
== 0 || lastsi
->first
!= si
->first
)
1057 firstsi
= verify_related_strinfos (si
);
1058 if (firstsi
== NULL
)
1060 while (firstsi
!= lastsi
)
1062 firstsi
= get_next_strinfo (firstsi
);
1063 if (firstsi
== NULL
)
1068 if (!is_strcat
&& !zero_length_string_p (si
))
1071 if (is_gimple_assign (last
.stmt
))
1073 gimple_stmt_iterator gsi
;
1075 if (!integer_zerop (gimple_assign_rhs1 (last
.stmt
)))
1077 if (stmt_could_throw_p (last
.stmt
))
1079 gsi
= gsi_for_stmt (last
.stmt
);
1080 unlink_stmt_vdef (last
.stmt
);
1081 release_defs (last
.stmt
);
1082 gsi_remove (&gsi
, true);
1086 if (!valid_builtin_call (last
.stmt
))
1089 callee
= gimple_call_fndecl (last
.stmt
);
1090 switch (DECL_FUNCTION_CODE (callee
))
1092 case BUILT_IN_MEMCPY
:
1093 case BUILT_IN_MEMCPY_CHK
:
1099 len
= gimple_call_arg (last
.stmt
, len_arg_no
);
1100 if (tree_fits_uhwi_p (len
))
1102 if (!tree_fits_uhwi_p (last
.len
)
1103 || integer_zerop (len
)
1104 || tree_to_uhwi (len
) != tree_to_uhwi (last
.len
) + 1)
1106 /* Don't adjust the length if it is divisible by 4, it is more efficient
1107 to store the extra '\0' in that case. */
1108 if ((tree_to_uhwi (len
) & 3) == 0)
1111 /* Don't fold away an out of bounds access, as this defeats proper
1113 tree dst
= gimple_call_arg (last
.stmt
, 0);
1114 tree size
= compute_objsize (dst
, 0);
1115 if (size
&& tree_int_cst_lt (size
, len
))
1118 else if (TREE_CODE (len
) == SSA_NAME
)
1120 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1121 if (!is_gimple_assign (def_stmt
)
1122 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1123 || gimple_assign_rhs1 (def_stmt
) != last
.len
1124 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1130 gimple_call_set_arg (last
.stmt
, len_arg_no
, last
.len
);
1131 update_stmt (last
.stmt
);
1134 /* For an LHS that is an SSA_NAME and for strlen() or strnlen() argument
1135 SRC, set LHS range info to [0, min (N, BOUND)] if SRC refers to
1136 a character array A[N] with unknown length bounded by N, and for
1137 strnlen(), by min (N, BOUND). */
1140 maybe_set_strlen_range (tree lhs
, tree src
, tree bound
)
1142 if (TREE_CODE (lhs
) != SSA_NAME
1143 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
1146 if (TREE_CODE (src
) == SSA_NAME
)
1148 gimple
*def
= SSA_NAME_DEF_STMT (src
);
1149 if (is_gimple_assign (def
)
1150 && gimple_assign_rhs_code (def
) == ADDR_EXPR
)
1151 src
= gimple_assign_rhs1 (def
);
1154 wide_int max
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
));
1155 wide_int min
= wi::zero (max
.get_precision ());
1157 if (TREE_CODE (src
) == ADDR_EXPR
)
1159 /* The last array member of a struct can be bigger than its size
1160 suggests if it's treated as a poor-man's flexible array member. */
1161 src
= TREE_OPERAND (src
, 0);
1162 bool src_is_array
= TREE_CODE (TREE_TYPE (src
)) == ARRAY_TYPE
;
1163 if (src_is_array
&& !array_at_struct_end_p (src
))
1165 tree type
= TREE_TYPE (src
);
1166 if (tree size
= TYPE_SIZE_UNIT (type
))
1167 if (size
&& TREE_CODE (size
) == INTEGER_CST
)
1168 max
= wi::to_wide (size
);
1170 /* For strlen() the upper bound above is equal to
1171 the longest string that can be stored in the array
1172 (i.e., it accounts for the terminating nul. For
1173 strnlen() bump up the maximum by one since the array
1174 need not be nul-terminated. */
1175 if (!bound
&& max
!= 0)
1180 if (TREE_CODE (src
) == COMPONENT_REF
&& !src_is_array
)
1181 src
= TREE_OPERAND (src
, 1);
1184 /* Handle the unlikely case of strlen (&c) where c is some
1186 if (tree size
= DECL_SIZE_UNIT (src
))
1187 if (TREE_CODE (size
) == INTEGER_CST
)
1188 max
= wi::to_wide (size
);
1195 /* For strnlen, adjust MIN and MAX as necessary. If the bound
1196 is less than the size of the array set MAX to it. It it's
1197 greater than MAX and MAX is non-zero bump MAX down to account
1198 for the necessary terminating nul. Otherwise leave it alone. */
1199 if (TREE_CODE (bound
) == INTEGER_CST
)
1201 wide_int wibnd
= wi::to_wide (bound
);
1202 int cmp
= wi::cmpu (wibnd
, max
);
1205 else if (cmp
&& wi::ne_p (max
, min
))
1208 else if (TREE_CODE (bound
) == SSA_NAME
)
1210 wide_int minbound
, maxbound
;
1211 value_range_type rng
= get_range_info (bound
, &minbound
, &maxbound
);
1212 if (rng
== VR_RANGE
)
1214 /* For a bound in a known range, adjust the range determined
1215 above as necessary. For a bound in some anti-range or
1216 in an unknown range, use the range determined above. */
1217 if (wi::ltu_p (minbound
, min
))
1219 if (wi::ltu_p (maxbound
, max
))
1226 return wide_int_to_tree (size_type_node
, min
);
1228 set_range_info (lhs
, VR_RANGE
, min
, max
);
1232 /* Handle a strlen call. If strlen of the argument is known, replace
1233 the strlen call with the known value, otherwise remember that strlen
1234 of the argument is stored in the lhs SSA_NAME. */
1237 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
1239 gimple
*stmt
= gsi_stmt (*gsi
);
1240 tree lhs
= gimple_call_lhs (stmt
);
1242 if (lhs
== NULL_TREE
)
1245 location_t loc
= gimple_location (stmt
);
1246 tree callee
= gimple_call_fndecl (stmt
);
1247 tree src
= gimple_call_arg (stmt
, 0);
1248 tree bound
= (DECL_FUNCTION_CODE (callee
) == BUILT_IN_STRNLEN
1249 ? gimple_call_arg (stmt
, 1) : NULL_TREE
);
1250 int idx
= get_stridx (src
);
1257 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
1261 si
= get_strinfo (idx
);
1263 rhs
= get_string_length (si
);
1265 if (rhs
!= NULL_TREE
)
1267 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1269 fprintf (dump_file
, "Optimizing: ");
1270 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1272 rhs
= unshare_expr (rhs
);
1273 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
1274 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1276 /* Set for strnlen() calls with a non-constant bound. */
1277 bool noncst_bound
= false;
1281 = fold_build2_loc (loc
, MIN_EXPR
, TREE_TYPE (rhs
), rhs
, bound
);
1283 noncst_bound
= (TREE_CODE (new_rhs
) != INTEGER_CST
1284 || tree_int_cst_lt (new_rhs
, rhs
));
1289 if (!update_call_from_tree (gsi
, rhs
))
1290 gimplify_and_update_call_from_tree (gsi
, rhs
);
1291 stmt
= gsi_stmt (*gsi
);
1293 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1295 fprintf (dump_file
, "into: ");
1296 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1299 /* Avoid storing the length for calls to strnlen() with
1300 a non-constant bound. */
1305 && TREE_CODE (si
->nonzero_chars
) != SSA_NAME
1306 && TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
1307 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1309 si
= unshare_strinfo (si
);
1310 si
->nonzero_chars
= lhs
;
1311 gcc_assert (si
->full_string_p
);
1314 if (strlen_to_stridx
)
1315 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1320 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1324 idx
= new_stridx (src
);
1327 strinfo
*si
= get_strinfo (idx
);
1330 if (!si
->full_string_p
&& !si
->stmt
)
1332 /* Until now we only had a lower bound on the string length.
1333 Install LHS as the actual length. */
1334 si
= unshare_strinfo (si
);
1335 tree old
= si
->nonzero_chars
;
1336 si
->nonzero_chars
= lhs
;
1337 si
->full_string_p
= true;
1338 if (TREE_CODE (old
) == INTEGER_CST
)
1340 old
= fold_convert_loc (loc
, TREE_TYPE (lhs
), old
);
1341 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1342 TREE_TYPE (lhs
), lhs
, old
);
1343 adjust_related_strinfos (loc
, si
, adj
);
1359 /* Only store the new length information for calls to strlen(),
1360 not for those to strnlen(). */
1361 strinfo
*si
= new_strinfo (src
, idx
, lhs
, true);
1362 set_strinfo (idx
, si
);
1363 find_equal_ptrs (src
, idx
);
1366 /* For SRC that is an array of N elements, set LHS's range
1367 to [0, min (N, BOUND)]. A constant return value means
1368 the range would have consisted of a single value. In
1369 that case, fold the result into the returned constant. */
1370 if (tree ret
= maybe_set_strlen_range (lhs
, src
, bound
))
1371 if (TREE_CODE (ret
) == INTEGER_CST
)
1373 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1375 fprintf (dump_file
, "Optimizing: ");
1376 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1378 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (ret
)))
1379 ret
= fold_convert_loc (loc
, TREE_TYPE (lhs
), ret
);
1380 if (!update_call_from_tree (gsi
, ret
))
1381 gimplify_and_update_call_from_tree (gsi
, ret
);
1382 stmt
= gsi_stmt (*gsi
);
1384 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1386 fprintf (dump_file
, "into: ");
1387 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1391 if (strlen_to_stridx
&& !bound
)
1392 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1396 /* Handle a strchr call. If strlen of the first argument is known, replace
1397 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
1398 that lhs of the call is endptr and strlen of the argument is endptr - x. */
1401 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
1405 gimple
*stmt
= gsi_stmt (*gsi
);
1406 tree lhs
= gimple_call_lhs (stmt
);
1408 if (lhs
== NULL_TREE
)
1411 if (!integer_zerop (gimple_call_arg (stmt
, 1)))
1414 src
= gimple_call_arg (stmt
, 0);
1415 idx
= get_stridx (src
);
1422 rhs
= build_int_cst (size_type_node
, ~idx
);
1426 si
= get_strinfo (idx
);
1428 rhs
= get_string_length (si
);
1430 if (rhs
!= NULL_TREE
)
1432 location_t loc
= gimple_location (stmt
);
1434 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1436 fprintf (dump_file
, "Optimizing: ");
1437 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1439 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
1441 rhs
= unshare_expr (si
->endptr
);
1442 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1444 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1448 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1449 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1450 TREE_TYPE (src
), src
, rhs
);
1451 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1453 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1455 if (!update_call_from_tree (gsi
, rhs
))
1456 gimplify_and_update_call_from_tree (gsi
, rhs
);
1457 stmt
= gsi_stmt (*gsi
);
1459 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1461 fprintf (dump_file
, "into: ");
1462 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1465 && si
->endptr
== NULL_TREE
1466 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1468 si
= unshare_strinfo (si
);
1471 zero_length_string (lhs
, si
);
1475 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1477 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1480 idx
= new_stridx (src
);
1481 else if (get_strinfo (idx
) != NULL
)
1483 zero_length_string (lhs
, NULL
);
1488 location_t loc
= gimple_location (stmt
);
1489 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1490 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1491 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1492 size_type_node
, lhsu
, srcu
);
1493 strinfo
*si
= new_strinfo (src
, idx
, length
, true);
1495 set_strinfo (idx
, si
);
1496 find_equal_ptrs (src
, idx
);
1497 zero_length_string (lhs
, si
);
1501 zero_length_string (lhs
, NULL
);
1504 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1505 If strlen of the second argument is known, strlen of the first argument
1506 is the same after this call. Furthermore, attempt to convert it to
1510 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1513 tree src
, dst
, srclen
, len
, lhs
, type
, fn
, oldlen
;
1515 gimple
*stmt
= gsi_stmt (*gsi
);
1516 strinfo
*si
, *dsi
, *olddsi
, *zsi
;
1519 src
= gimple_call_arg (stmt
, 1);
1520 dst
= gimple_call_arg (stmt
, 0);
1521 lhs
= gimple_call_lhs (stmt
);
1522 idx
= get_stridx (src
);
1525 si
= get_strinfo (idx
);
1527 didx
= get_stridx (dst
);
1531 olddsi
= get_strinfo (didx
);
1536 adjust_last_stmt (olddsi
, stmt
, false);
1540 srclen
= get_string_length (si
);
1542 srclen
= build_int_cst (size_type_node
, ~idx
);
1544 loc
= gimple_location (stmt
);
1545 if (srclen
== NULL_TREE
)
1548 case BUILT_IN_STRCPY
:
1549 case BUILT_IN_STRCPY_CHK
:
1550 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1553 case BUILT_IN_STPCPY
:
1554 case BUILT_IN_STPCPY_CHK
:
1555 if (lhs
== NULL_TREE
)
1559 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1560 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1561 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1571 didx
= new_stridx (dst
);
1577 oldlen
= olddsi
->nonzero_chars
;
1578 dsi
= unshare_strinfo (olddsi
);
1579 dsi
->nonzero_chars
= srclen
;
1580 dsi
->full_string_p
= (srclen
!= NULL_TREE
);
1581 /* Break the chain, so adjust_related_strinfo on later pointers in
1582 the chain won't adjust this one anymore. */
1585 dsi
->endptr
= NULL_TREE
;
1589 dsi
= new_strinfo (dst
, didx
, srclen
, srclen
!= NULL_TREE
);
1590 set_strinfo (didx
, dsi
);
1591 find_equal_ptrs (dst
, didx
);
1593 dsi
->writable
= true;
1594 dsi
->dont_invalidate
= true;
1596 if (dsi
->nonzero_chars
== NULL_TREE
)
1600 /* If string length of src is unknown, use delayed length
1601 computation. If string lenth of dst will be needed, it
1602 can be computed by transforming this strcpy call into
1603 stpcpy and subtracting dst from the return value. */
1605 /* Look for earlier strings whose length could be determined if
1606 this strcpy is turned into an stpcpy. */
1608 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1610 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1612 /* When setting a stmt for delayed length computation
1613 prevent all strinfos through dsi from being
1615 chainsi
= unshare_strinfo (chainsi
);
1616 chainsi
->stmt
= stmt
;
1617 chainsi
->nonzero_chars
= NULL_TREE
;
1618 chainsi
->full_string_p
= false;
1619 chainsi
->endptr
= NULL_TREE
;
1620 chainsi
->dont_invalidate
= true;
1625 /* Try to detect overlap before returning. This catches cases
1626 like strcpy (d, d + n) where n is non-constant whose range
1627 is such that (n <= strlen (d) holds).
1629 OLDDSI->NONZERO_chars may have been reset by this point with
1630 oldlen holding it original value. */
1631 if (olddsi
&& oldlen
)
1633 /* Add 1 for the terminating NUL. */
1634 tree type
= TREE_TYPE (oldlen
);
1635 oldlen
= fold_build2 (PLUS_EXPR
, type
, oldlen
,
1636 build_int_cst (type
, 1));
1637 check_bounds_or_overlap (stmt
, olddsi
->ptr
, src
, oldlen
, NULL_TREE
);
1645 tree adj
= NULL_TREE
;
1646 if (oldlen
== NULL_TREE
)
1648 else if (integer_zerop (oldlen
))
1650 else if (TREE_CODE (oldlen
) == INTEGER_CST
1651 || TREE_CODE (srclen
) == INTEGER_CST
)
1652 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1653 TREE_TYPE (srclen
), srclen
,
1654 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1656 if (adj
!= NULL_TREE
)
1657 adjust_related_strinfos (loc
, dsi
, adj
);
1661 /* strcpy src may not overlap dst, so src doesn't need to be
1662 invalidated either. */
1664 si
->dont_invalidate
= true;
1670 case BUILT_IN_STRCPY
:
1671 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1673 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1675 case BUILT_IN_STRCPY_CHK
:
1676 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1678 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1680 case BUILT_IN_STPCPY
:
1681 /* This would need adjustment of the lhs (subtract one),
1682 or detection that the trailing '\0' doesn't need to be
1683 written, if it will be immediately overwritten.
1684 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1688 zsi
= zero_length_string (lhs
, dsi
);
1691 case BUILT_IN_STPCPY_CHK
:
1692 /* This would need adjustment of the lhs (subtract one),
1693 or detection that the trailing '\0' doesn't need to be
1694 written, if it will be immediately overwritten.
1695 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1699 zsi
= zero_length_string (lhs
, dsi
);
1706 zsi
->dont_invalidate
= true;
1710 tree args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1711 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1714 type
= size_type_node
;
1716 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1717 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1719 /* Set the no-warning bit on the transformed statement? */
1720 bool set_no_warning
= false;
1722 if (const strinfo
*chksi
= olddsi
? olddsi
: dsi
)
1724 && !check_bounds_or_overlap (stmt
, chksi
->ptr
, si
->ptr
, NULL_TREE
, len
))
1726 gimple_set_no_warning (stmt
, true);
1727 set_no_warning
= true;
1730 if (fn
== NULL_TREE
)
1733 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1735 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1737 fprintf (dump_file
, "Optimizing: ");
1738 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1740 if (gimple_call_num_args (stmt
) == 2)
1741 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1743 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1744 gimple_call_arg (stmt
, 2));
1747 stmt
= gsi_stmt (*gsi
);
1749 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1751 fprintf (dump_file
, "into: ");
1752 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1754 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1755 laststmt
.stmt
= stmt
;
1756 laststmt
.len
= srclen
;
1757 laststmt
.stridx
= dsi
->idx
;
1759 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1760 fprintf (dump_file
, "not possible.\n");
1763 gimple_set_no_warning (stmt
, true);
1766 /* Check the size argument to the built-in forms of stpncpy and strncpy
1767 for out-of-bounds offsets or overlapping access, and to see if the
1768 size argument is derived from a call to strlen() on the source argument,
1769 and if so, issue an appropriate warning. */
1772 handle_builtin_strncat (built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1774 /* Same as stxncpy(). */
1775 handle_builtin_stxncpy (bcode
, gsi
);
1778 /* Return true if LEN depends on a call to strlen(SRC) in an interesting
1779 way. LEN can either be an integer expression, or a pointer (to char).
1780 When it is the latter (such as in recursive calls to self) is is
1781 assumed to be the argument in some call to strlen() whose relationship
1782 to SRC is being ascertained. */
1785 is_strlen_related_p (tree src
, tree len
)
1787 if (TREE_CODE (TREE_TYPE (len
)) == POINTER_TYPE
1788 && operand_equal_p (src
, len
, 0))
1791 if (TREE_CODE (len
) != SSA_NAME
)
1794 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1798 if (is_gimple_call (def_stmt
))
1800 tree func
= gimple_call_fndecl (def_stmt
);
1801 if (!valid_builtin_call (def_stmt
)
1802 || DECL_FUNCTION_CODE (func
) != BUILT_IN_STRLEN
)
1805 tree arg
= gimple_call_arg (def_stmt
, 0);
1806 return is_strlen_related_p (src
, arg
);
1809 if (!is_gimple_assign (def_stmt
))
1812 tree_code code
= gimple_assign_rhs_code (def_stmt
);
1813 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1814 tree rhstype
= TREE_TYPE (rhs1
);
1816 if ((TREE_CODE (rhstype
) == POINTER_TYPE
&& code
== POINTER_PLUS_EXPR
)
1817 || (INTEGRAL_TYPE_P (rhstype
)
1818 && (code
== BIT_AND_EXPR
1819 || code
== NOP_EXPR
)))
1821 /* Pointer plus (an integer), and truncation are considered among
1822 the (potentially) related expressions to strlen. */
1823 return is_strlen_related_p (src
, rhs1
);
1826 if (tree rhs2
= gimple_assign_rhs2 (def_stmt
))
1828 /* Integer subtraction is considered strlen-related when both
1829 arguments are integers and second one is strlen-related. */
1830 rhstype
= TREE_TYPE (rhs2
);
1831 if (INTEGRAL_TYPE_P (rhstype
) && code
== MINUS_EXPR
)
1832 return is_strlen_related_p (src
, rhs2
);
1838 /* Called by handle_builtin_stxncpy and by gimple_fold_builtin_strncpy
1840 Check to see if the specified bound is a) equal to the size of
1841 the destination DST and if so, b) if it's immediately followed by
1842 DST[CNT - 1] = '\0'. If a) holds and b) does not, warn. Otherwise,
1843 do nothing. Return true if diagnostic has been issued.
1845 The purpose is to diagnose calls to strncpy and stpncpy that do
1846 not nul-terminate the copy while allowing for the idiom where
1847 such a call is immediately followed by setting the last element
1850 strncpy (a, s, sizeof a);
1851 a[sizeof a - 1] = '\0';
1855 maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi
, tree src
, tree cnt
)
1857 gimple
*stmt
= gsi_stmt (gsi
);
1858 if (gimple_no_warning_p (stmt
))
1861 wide_int cntrange
[2];
1863 if (TREE_CODE (cnt
) == INTEGER_CST
)
1864 cntrange
[0] = cntrange
[1] = wi::to_wide (cnt
);
1865 else if (TREE_CODE (cnt
) == SSA_NAME
)
1867 enum value_range_type rng
= get_range_info (cnt
, cntrange
, cntrange
+ 1);
1868 if (rng
== VR_RANGE
)
1870 else if (rng
== VR_ANTI_RANGE
)
1872 wide_int maxobjsize
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
));
1874 if (wi::ltu_p (cntrange
[1], maxobjsize
))
1876 cntrange
[0] = cntrange
[1] + 1;
1877 cntrange
[1] = maxobjsize
;
1881 cntrange
[1] = cntrange
[0] - 1;
1882 cntrange
[0] = wi::zero (TYPE_PRECISION (TREE_TYPE (cnt
)));
1891 /* Negative value is the constant string length. If it's less than
1892 the lower bound there is no truncation. Avoid calling get_stridx()
1893 when ssa_ver_to_stridx is empty. That implies the caller isn't
1894 running under the control of this pass and ssa_ver_to_stridx hasn't
1895 been created yet. */
1896 int sidx
= ssa_ver_to_stridx
.length () ? get_stridx (src
) : 0;
1897 if (sidx
< 0 && wi::gtu_p (cntrange
[0], ~sidx
))
1900 tree dst
= gimple_call_arg (stmt
, 0);
1902 if (TREE_CODE (dstdecl
) == ADDR_EXPR
)
1903 dstdecl
= TREE_OPERAND (dstdecl
, 0);
1905 tree ref
= NULL_TREE
;
1909 /* If the source is a non-string return early to avoid warning
1910 for possible truncation (if the truncation is certain SIDX
1912 tree srcdecl
= gimple_call_arg (stmt
, 1);
1913 if (TREE_CODE (srcdecl
) == ADDR_EXPR
)
1914 srcdecl
= TREE_OPERAND (srcdecl
, 0);
1915 if (get_attr_nonstring_decl (srcdecl
, &ref
))
1919 /* Likewise, if the destination refers to a an array/pointer declared
1920 nonstring return early. */
1921 if (get_attr_nonstring_decl (dstdecl
, &ref
))
1924 /* Look for dst[i] = '\0'; after the stxncpy() call and if found
1925 avoid the truncation warning. */
1926 gsi_next_nondebug (&gsi
);
1927 gimple
*next_stmt
= gsi_stmt (gsi
);
1930 /* When there is no statement in the same basic block check
1931 the immediate successor block. */
1932 if (basic_block bb
= gimple_bb (stmt
))
1934 if (single_succ_p (bb
))
1936 /* For simplicity, ignore blocks with multiple outgoing
1937 edges for now and only consider successor blocks along
1939 edge e
= EDGE_SUCC (bb
, 0);
1940 if (!(e
->flags
& EDGE_ABNORMAL
))
1942 gsi
= gsi_start_bb (e
->dest
);
1943 next_stmt
= gsi_stmt (gsi
);
1944 if (next_stmt
&& is_gimple_debug (next_stmt
))
1946 gsi_next_nondebug (&gsi
);
1947 next_stmt
= gsi_stmt (gsi
);
1954 if (next_stmt
&& is_gimple_assign (next_stmt
))
1956 tree lhs
= gimple_assign_lhs (next_stmt
);
1957 tree_code code
= TREE_CODE (lhs
);
1958 if (code
== ARRAY_REF
|| code
== MEM_REF
)
1959 lhs
= TREE_OPERAND (lhs
, 0);
1961 tree func
= gimple_call_fndecl (stmt
);
1962 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STPNCPY
)
1964 tree ret
= gimple_call_lhs (stmt
);
1965 if (ret
&& operand_equal_p (ret
, lhs
, 0))
1969 /* Determine the base address and offset of the reference,
1970 ignoring the innermost array index. */
1971 if (TREE_CODE (ref
) == ARRAY_REF
)
1972 ref
= TREE_OPERAND (ref
, 0);
1975 tree dstbase
= get_addr_base_and_unit_offset (ref
, &dstoff
);
1978 tree lhsbase
= get_addr_base_and_unit_offset (lhs
, &lhsoff
);
1981 && known_eq (dstoff
, lhsoff
)
1982 && operand_equal_p (dstbase
, lhsbase
, 0))
1986 int prec
= TYPE_PRECISION (TREE_TYPE (cnt
));
1987 wide_int lenrange
[2];
1988 if (strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
)
1990 lenrange
[0] = (sisrc
->nonzero_chars
1991 && TREE_CODE (sisrc
->nonzero_chars
) == INTEGER_CST
1992 ? wi::to_wide (sisrc
->nonzero_chars
)
1994 lenrange
[1] = lenrange
[0];
1997 lenrange
[0] = lenrange
[1] = wi::shwi (~sidx
, prec
);
2001 get_range_strlen (src
, range
);
2002 if (range
[0] != NULL_TREE
2003 && TREE_CODE (range
[0]) == INTEGER_CST
2004 && range
[1] != NULL_TREE
2005 && TREE_CODE (range
[1]) == INTEGER_CST
)
2007 lenrange
[0] = wi::to_wide (range
[0], prec
);
2008 lenrange
[1] = wi::to_wide (range
[1], prec
);
2012 lenrange
[0] = wi::shwi (0, prec
);
2013 lenrange
[1] = wi::shwi (-1, prec
);
2017 location_t callloc
= gimple_nonartificial_location (stmt
);
2018 callloc
= expansion_point_location_if_in_system_header (callloc
);
2020 tree func
= gimple_call_fndecl (stmt
);
2022 if (lenrange
[0] != 0 || !wi::neg_p (lenrange
[1]))
2024 /* If the longest source string is shorter than the lower bound
2025 of the specified count the copy is definitely nul-terminated. */
2026 if (wi::ltu_p (lenrange
[1], cntrange
[0]))
2029 if (wi::neg_p (lenrange
[1]))
2031 /* The length of one of the strings is unknown but at least
2032 one has non-zero length and that length is stored in
2033 LENRANGE[1]. Swap the bounds to force a "may be truncated"
2035 lenrange
[1] = lenrange
[0];
2036 lenrange
[0] = wi::shwi (0, prec
);
2039 /* Set to true for strncat whose bound is derived from the length
2040 of the destination (the expected usage pattern). */
2041 bool cat_dstlen_bounded
= false;
2042 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STRNCAT
)
2043 cat_dstlen_bounded
= is_strlen_related_p (dst
, cnt
);
2045 if (lenrange
[0] == cntrange
[1] && cntrange
[0] == cntrange
[1])
2046 return warning_n (callloc
, OPT_Wstringop_truncation
,
2047 cntrange
[0].to_uhwi (),
2048 "%G%qD output truncated before terminating "
2049 "nul copying %E byte from a string of the "
2051 "%G%qD output truncated before terminating nul "
2052 "copying %E bytes from a string of the same "
2055 else if (!cat_dstlen_bounded
)
2057 if (wi::geu_p (lenrange
[0], cntrange
[1]))
2059 /* The shortest string is longer than the upper bound of
2060 the count so the truncation is certain. */
2061 if (cntrange
[0] == cntrange
[1])
2062 return warning_n (callloc
, OPT_Wstringop_truncation
,
2063 cntrange
[0].to_uhwi (),
2064 "%G%qD output truncated copying %E byte "
2065 "from a string of length %wu",
2066 "%G%qD output truncated copying %E bytes "
2067 "from a string of length %wu",
2068 stmt
, func
, cnt
, lenrange
[0].to_uhwi ());
2070 return warning_at (callloc
, OPT_Wstringop_truncation
,
2071 "%G%qD output truncated copying between %wu "
2072 "and %wu bytes from a string of length %wu",
2073 stmt
, func
, cntrange
[0].to_uhwi (),
2074 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
2076 else if (wi::geu_p (lenrange
[1], cntrange
[1]))
2078 /* The longest string is longer than the upper bound of
2079 the count so the truncation is possible. */
2080 if (cntrange
[0] == cntrange
[1])
2081 return warning_n (callloc
, OPT_Wstringop_truncation
,
2082 cntrange
[0].to_uhwi (),
2083 "%G%qD output may be truncated copying %E "
2084 "byte from a string of length %wu",
2085 "%G%qD output may be truncated copying %E "
2086 "bytes from a string of length %wu",
2087 stmt
, func
, cnt
, lenrange
[1].to_uhwi ());
2089 return warning_at (callloc
, OPT_Wstringop_truncation
,
2090 "%G%qD output may be truncated copying between "
2091 "%wu and %wu bytes from a string of length %wu",
2092 stmt
, func
, cntrange
[0].to_uhwi (),
2093 cntrange
[1].to_uhwi (), lenrange
[1].to_uhwi ());
2097 if (!cat_dstlen_bounded
2098 && cntrange
[0] != cntrange
[1]
2099 && wi::leu_p (cntrange
[0], lenrange
[0])
2100 && wi::leu_p (cntrange
[1], lenrange
[0] + 1))
2102 /* If the source (including the terminating nul) is longer than
2103 the lower bound of the specified count but shorter than the
2104 upper bound the copy may (but need not) be truncated. */
2105 return warning_at (callloc
, OPT_Wstringop_truncation
,
2106 "%G%qD output may be truncated copying between "
2107 "%wu and %wu bytes from a string of length %wu",
2108 stmt
, func
, cntrange
[0].to_uhwi (),
2109 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
2113 if (tree dstsize
= compute_objsize (dst
, 1))
2115 /* The source length is uknown. Try to determine the destination
2116 size and see if it matches the specified bound. If not, bail.
2117 Otherwise go on to see if it should be diagnosed for possible
2122 if (wi::to_wide (dstsize
) != cntrange
[1])
2125 if (cntrange
[0] == cntrange
[1])
2126 return warning_at (callloc
, OPT_Wstringop_truncation
,
2127 "%G%qD specified bound %E equals destination size",
2134 /* Check the arguments to the built-in forms of stpncpy and strncpy for
2135 out-of-bounds offsets or overlapping access, and to see if the size
2136 is derived from calling strlen() on the source argument, and if so,
2137 issue the appropriate warning. */
2140 handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*gsi
)
2142 if (!strlen_to_stridx
)
2145 gimple
*stmt
= gsi_stmt (*gsi
);
2147 tree dst
= gimple_call_arg (stmt
, 0);
2148 tree src
= gimple_call_arg (stmt
, 1);
2149 tree len
= gimple_call_arg (stmt
, 2);
2150 tree dstsize
= NULL_TREE
, srcsize
= NULL_TREE
;
2152 int didx
= get_stridx (dst
);
2153 if (strinfo
*sidst
= didx
> 0 ? get_strinfo (didx
) : NULL
)
2155 /* Compute the size of the destination string including the NUL. */
2156 if (sidst
->nonzero_chars
)
2158 tree type
= TREE_TYPE (sidst
->nonzero_chars
);
2159 dstsize
= fold_build2 (PLUS_EXPR
, type
, sidst
->nonzero_chars
,
2160 build_int_cst (type
, 1));
2165 int sidx
= get_stridx (src
);
2166 strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
;
2169 /* strncat() and strncpy() can modify the source string by writing
2170 over the terminating nul so SISRC->DONT_INVALIDATE must be left
2173 /* Compute the size of the source string including the NUL. */
2174 if (sisrc
->nonzero_chars
)
2176 tree type
= TREE_TYPE (sisrc
->nonzero_chars
);
2177 srcsize
= fold_build2 (PLUS_EXPR
, type
, sisrc
->nonzero_chars
,
2178 build_int_cst (type
, 1));
2184 srcsize
= NULL_TREE
;
2186 if (!check_bounds_or_overlap (stmt
, dst
, src
, dstsize
, srcsize
))
2188 gimple_set_no_warning (stmt
, true);
2192 /* If the length argument was computed from strlen(S) for some string
2193 S retrieve the strinfo index for the string (PSS->FIRST) alonng with
2194 the location of the strlen() call (PSS->SECOND). */
2195 stridx_strlenloc
*pss
= strlen_to_stridx
->get (len
);
2196 if (!pss
|| pss
->first
<= 0)
2198 if (maybe_diag_stxncpy_trunc (*gsi
, src
, len
))
2199 gimple_set_no_warning (stmt
, true);
2204 /* Retrieve the strinfo data for the string S that LEN was computed
2205 from as some function F of strlen (S) (i.e., LEN need not be equal
2207 strinfo
*silen
= get_strinfo (pss
->first
);
2209 location_t callloc
= gimple_nonartificial_location (stmt
);
2210 callloc
= expansion_point_location_if_in_system_header (callloc
);
2212 tree func
= gimple_call_fndecl (stmt
);
2214 bool warned
= false;
2216 /* When -Wstringop-truncation is set, try to determine truncation
2217 before diagnosing possible overflow. Truncation is implied by
2218 the LEN argument being equal to strlen(SRC), regardless of
2219 whether its value is known. Otherwise, issue the more generic
2220 -Wstringop-overflow which triggers for LEN arguments that in
2221 any meaningful way depend on strlen(SRC). */
2223 && is_strlen_related_p (src
, len
)
2224 && warning_at (callloc
, OPT_Wstringop_truncation
,
2225 "%G%qD output truncated before terminating nul "
2226 "copying as many bytes from a string as its length",
2229 else if (silen
&& is_strlen_related_p (src
, silen
->ptr
))
2230 warned
= warning_at (callloc
, OPT_Wstringop_overflow_
,
2231 "%G%qD specified bound depends on the length "
2232 "of the source argument",
2236 location_t strlenloc
= pss
->second
;
2237 if (strlenloc
!= UNKNOWN_LOCATION
&& strlenloc
!= callloc
)
2238 inform (strlenloc
, "length computed here");
2242 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
2243 If strlen of the second argument is known and length of the third argument
2244 is that plus one, strlen of the first argument is the same after this
2248 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2251 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
2252 gimple
*stmt
= gsi_stmt (*gsi
);
2253 strinfo
*si
, *dsi
, *olddsi
;
2255 len
= gimple_call_arg (stmt
, 2);
2256 src
= gimple_call_arg (stmt
, 1);
2257 dst
= gimple_call_arg (stmt
, 0);
2258 idx
= get_stridx (src
);
2262 didx
= get_stridx (dst
);
2265 olddsi
= get_strinfo (didx
);
2270 && tree_fits_uhwi_p (len
)
2271 && !integer_zerop (len
))
2272 adjust_last_stmt (olddsi
, stmt
, false);
2279 /* Handle memcpy (x, y, l) where l's relationship with strlen (y)
2281 si
= get_strinfo (idx
);
2282 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
2284 if (TREE_CODE (len
) == INTEGER_CST
2285 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
2287 if (tree_int_cst_le (len
, si
->nonzero_chars
))
2289 /* Copying LEN nonzero characters, where LEN is constant. */
2291 full_string_p
= false;
2295 /* Copying the whole of the analyzed part of SI. */
2296 newlen
= si
->nonzero_chars
;
2297 full_string_p
= si
->full_string_p
;
2302 if (!si
->full_string_p
)
2304 if (TREE_CODE (len
) != SSA_NAME
)
2306 def_stmt
= SSA_NAME_DEF_STMT (len
);
2307 if (!is_gimple_assign (def_stmt
)
2308 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
2309 || gimple_assign_rhs1 (def_stmt
) != si
->nonzero_chars
2310 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
2312 /* Copying variable-length string SI (and no more). */
2313 newlen
= si
->nonzero_chars
;
2314 full_string_p
= true;
2320 /* Handle memcpy (x, "abcd", 5) or
2321 memcpy (x, "abc\0uvw", 7). */
2322 if (!tree_fits_uhwi_p (len
))
2325 unsigned HOST_WIDE_INT clen
= tree_to_uhwi (len
);
2326 unsigned HOST_WIDE_INT nonzero_chars
= ~idx
;
2327 newlen
= build_int_cst (size_type_node
, MIN (nonzero_chars
, clen
));
2328 full_string_p
= clen
> nonzero_chars
;
2333 && olddsi
->nonzero_chars
2334 && TREE_CODE (olddsi
->nonzero_chars
) == INTEGER_CST
2335 && tree_int_cst_le (newlen
, olddsi
->nonzero_chars
))
2337 /* The SRC substring being written strictly overlaps
2338 a subsequence of the existing string OLDDSI. */
2339 newlen
= olddsi
->nonzero_chars
;
2340 full_string_p
= olddsi
->full_string_p
;
2343 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
2344 adjust_last_stmt (olddsi
, stmt
, false);
2348 didx
= new_stridx (dst
);
2355 dsi
= unshare_strinfo (olddsi
);
2356 oldlen
= olddsi
->nonzero_chars
;
2357 dsi
->nonzero_chars
= newlen
;
2358 dsi
->full_string_p
= full_string_p
;
2359 /* Break the chain, so adjust_related_strinfo on later pointers in
2360 the chain won't adjust this one anymore. */
2363 dsi
->endptr
= NULL_TREE
;
2367 dsi
= new_strinfo (dst
, didx
, newlen
, full_string_p
);
2368 set_strinfo (didx
, dsi
);
2369 find_equal_ptrs (dst
, didx
);
2371 dsi
->writable
= true;
2372 dsi
->dont_invalidate
= true;
2375 tree adj
= NULL_TREE
;
2376 location_t loc
= gimple_location (stmt
);
2377 if (oldlen
== NULL_TREE
)
2379 else if (integer_zerop (oldlen
))
2381 else if (TREE_CODE (oldlen
) == INTEGER_CST
2382 || TREE_CODE (newlen
) == INTEGER_CST
)
2383 adj
= fold_build2_loc (loc
, MINUS_EXPR
, TREE_TYPE (newlen
), newlen
,
2384 fold_convert_loc (loc
, TREE_TYPE (newlen
),
2386 if (adj
!= NULL_TREE
)
2387 adjust_related_strinfos (loc
, dsi
, adj
);
2391 /* memcpy src may not overlap dst, so src doesn't need to be
2392 invalidated either. */
2394 si
->dont_invalidate
= true;
2398 lhs
= gimple_call_lhs (stmt
);
2401 case BUILT_IN_MEMCPY
:
2402 case BUILT_IN_MEMCPY_CHK
:
2403 /* Allow adjust_last_stmt to decrease this memcpy's size. */
2404 laststmt
.stmt
= stmt
;
2405 laststmt
.len
= dsi
->nonzero_chars
;
2406 laststmt
.stridx
= dsi
->idx
;
2408 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
2410 case BUILT_IN_MEMPCPY
:
2411 case BUILT_IN_MEMPCPY_CHK
:
2419 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
2420 If strlen of the second argument is known, strlen of the first argument
2421 is increased by the length of the second argument. Furthermore, attempt
2422 to convert it to memcpy/strcpy if the length of the first argument
2426 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2429 tree srclen
, args
, type
, fn
, objsz
, endptr
;
2431 gimple
*stmt
= gsi_stmt (*gsi
);
2433 location_t loc
= gimple_location (stmt
);
2435 tree src
= gimple_call_arg (stmt
, 1);
2436 tree dst
= gimple_call_arg (stmt
, 0);
2438 /* Bail if the source is the same as destination. It will be diagnosed
2440 if (operand_equal_p (src
, dst
, 0))
2443 tree lhs
= gimple_call_lhs (stmt
);
2445 didx
= get_stridx (dst
);
2451 dsi
= get_strinfo (didx
);
2455 idx
= get_stridx (src
);
2457 srclen
= build_int_cst (size_type_node
, ~idx
);
2460 si
= get_strinfo (idx
);
2462 srclen
= get_string_length (si
);
2465 /* Set the no-warning bit on the transformed statement? */
2466 bool set_no_warning
= false;
2468 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
2471 /* The concatenation always involves copying at least one byte
2472 (the terminating nul), even if the source string is empty.
2473 If the source is unknown assume it's one character long and
2474 used that as both sizes. */
2478 tree type
= TREE_TYPE (slen
);
2479 slen
= fold_build2 (PLUS_EXPR
, type
, slen
, build_int_cst (type
, 1));
2482 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2484 if (!check_bounds_or_overlap (stmt
, dst
, sptr
, NULL_TREE
, slen
))
2486 gimple_set_no_warning (stmt
, true);
2487 set_no_warning
= true;
2491 /* strcat (p, q) can be transformed into
2492 tmp = p + strlen (p); endptr = stpcpy (tmp, q);
2493 with length endptr - p if we need to compute the length
2494 later on. Don't do this transformation if we don't need
2496 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
2500 didx
= new_stridx (dst
);
2506 dsi
= new_strinfo (dst
, didx
, NULL_TREE
, false);
2507 set_strinfo (didx
, dsi
);
2508 find_equal_ptrs (dst
, didx
);
2512 dsi
= unshare_strinfo (dsi
);
2513 dsi
->nonzero_chars
= NULL_TREE
;
2514 dsi
->full_string_p
= false;
2516 dsi
->endptr
= NULL_TREE
;
2518 dsi
->writable
= true;
2520 dsi
->dont_invalidate
= true;
2525 tree dstlen
= dsi
->nonzero_chars
;
2526 endptr
= dsi
->endptr
;
2528 dsi
= unshare_strinfo (dsi
);
2529 dsi
->endptr
= NULL_TREE
;
2531 dsi
->writable
= true;
2533 if (srclen
!= NULL_TREE
)
2535 dsi
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
2536 TREE_TYPE (dsi
->nonzero_chars
),
2537 dsi
->nonzero_chars
, srclen
);
2538 gcc_assert (dsi
->full_string_p
);
2539 adjust_related_strinfos (loc
, dsi
, srclen
);
2540 dsi
->dont_invalidate
= true;
2544 dsi
->nonzero_chars
= NULL
;
2545 dsi
->full_string_p
= false;
2546 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
2547 dsi
->dont_invalidate
= true;
2551 /* strcat src may not overlap dst, so src doesn't need to be
2552 invalidated either. */
2553 si
->dont_invalidate
= true;
2555 /* For now. Could remove the lhs from the call and add
2556 lhs = dst; afterwards. */
2564 case BUILT_IN_STRCAT
:
2565 if (srclen
!= NULL_TREE
)
2566 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
2568 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
2570 case BUILT_IN_STRCAT_CHK
:
2571 if (srclen
!= NULL_TREE
)
2572 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
2574 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
2575 objsz
= gimple_call_arg (stmt
, 2);
2581 if (fn
== NULL_TREE
)
2586 tree type
= TREE_TYPE (dstlen
);
2588 /* Compute the size of the source sequence, including the nul. */
2589 tree srcsize
= srclen
? srclen
: size_zero_node
;
2590 srcsize
= fold_build2 (PLUS_EXPR
, type
, srcsize
, build_int_cst (type
, 1));
2592 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2594 if (!check_bounds_or_overlap (stmt
, dst
, sptr
, dstlen
, srcsize
))
2596 gimple_set_no_warning (stmt
, true);
2597 set_no_warning
= true;
2601 tree len
= NULL_TREE
;
2602 if (srclen
!= NULL_TREE
)
2604 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
2605 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
2607 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
2608 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
2609 build_int_cst (type
, 1));
2610 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
2614 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
2616 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
2617 TREE_TYPE (dst
), unshare_expr (dst
),
2618 fold_convert_loc (loc
, sizetype
,
2619 unshare_expr (dstlen
)));
2620 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
2622 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2624 fprintf (dump_file
, "Optimizing: ");
2625 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2627 if (srclen
!= NULL_TREE
)
2628 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
2629 dst
, src
, len
, objsz
);
2631 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
2635 stmt
= gsi_stmt (*gsi
);
2637 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2639 fprintf (dump_file
, "into: ");
2640 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2642 /* If srclen == NULL, note that current string length can be
2643 computed by transforming this strcpy into stpcpy. */
2644 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
2646 adjust_last_stmt (dsi
, stmt
, true);
2647 if (srclen
!= NULL_TREE
)
2649 laststmt
.stmt
= stmt
;
2650 laststmt
.len
= srclen
;
2651 laststmt
.stridx
= dsi
->idx
;
2654 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2655 fprintf (dump_file
, "not possible.\n");
2658 gimple_set_no_warning (stmt
, true);
2661 /* Handle a call to malloc or calloc. */
2664 handle_builtin_malloc (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2666 gimple
*stmt
= gsi_stmt (*gsi
);
2667 tree lhs
= gimple_call_lhs (stmt
);
2668 if (lhs
== NULL_TREE
)
2671 gcc_assert (get_stridx (lhs
) == 0);
2672 int idx
= new_stridx (lhs
);
2673 tree length
= NULL_TREE
;
2674 if (bcode
== BUILT_IN_CALLOC
)
2675 length
= build_int_cst (size_type_node
, 0);
2676 strinfo
*si
= new_strinfo (lhs
, idx
, length
, length
!= NULL_TREE
);
2677 if (bcode
== BUILT_IN_CALLOC
)
2679 set_strinfo (idx
, si
);
2680 si
->writable
= true;
2682 si
->dont_invalidate
= true;
2685 /* Handle a call to memset.
2686 After a call to calloc, memset(,0,) is unnecessary.
2687 memset(malloc(n),0,n) is calloc(n,1).
2688 return true when the call is transfomred, false otherwise. */
2691 handle_builtin_memset (gimple_stmt_iterator
*gsi
)
2693 gimple
*stmt2
= gsi_stmt (*gsi
);
2694 if (!integer_zerop (gimple_call_arg (stmt2
, 1)))
2696 tree ptr
= gimple_call_arg (stmt2
, 0);
2697 int idx1
= get_stridx (ptr
);
2700 strinfo
*si1
= get_strinfo (idx1
);
2703 gimple
*stmt1
= si1
->stmt
;
2704 if (!stmt1
|| !is_gimple_call (stmt1
))
2706 tree callee1
= gimple_call_fndecl (stmt1
);
2707 if (!valid_builtin_call (stmt1
))
2709 enum built_in_function code1
= DECL_FUNCTION_CODE (callee1
);
2710 tree size
= gimple_call_arg (stmt2
, 2);
2711 if (code1
== BUILT_IN_CALLOC
)
2712 /* Not touching stmt1 */ ;
2713 else if (code1
== BUILT_IN_MALLOC
2714 && operand_equal_p (gimple_call_arg (stmt1
, 0), size
, 0))
2716 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt1
);
2717 update_gimple_call (&gsi1
, builtin_decl_implicit (BUILT_IN_CALLOC
), 2,
2718 size
, build_one_cst (size_type_node
));
2719 si1
->nonzero_chars
= build_int_cst (size_type_node
, 0);
2720 si1
->full_string_p
= true;
2721 si1
->stmt
= gsi_stmt (gsi1
);
2725 tree lhs
= gimple_call_lhs (stmt2
);
2726 unlink_stmt_vdef (stmt2
);
2729 gimple
*assign
= gimple_build_assign (lhs
, ptr
);
2730 gsi_replace (gsi
, assign
, false);
2734 gsi_remove (gsi
, true);
2735 release_defs (stmt2
);
2741 /* Handle a call to memcmp. We try to handle small comparisons by
2742 converting them to load and compare, and replacing the call to memcmp
2743 with a __builtin_memcmp_eq call where possible.
2744 return true when call is transformed, return false otherwise. */
2747 handle_builtin_memcmp (gimple_stmt_iterator
*gsi
)
2749 gcall
*stmt2
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2750 tree res
= gimple_call_lhs (stmt2
);
2751 tree arg1
= gimple_call_arg (stmt2
, 0);
2752 tree arg2
= gimple_call_arg (stmt2
, 1);
2753 tree len
= gimple_call_arg (stmt2
, 2);
2754 unsigned HOST_WIDE_INT leni
;
2755 use_operand_p use_p
;
2756 imm_use_iterator iter
;
2761 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
2763 gimple
*ustmt
= USE_STMT (use_p
);
2765 if (is_gimple_debug (ustmt
))
2767 if (gimple_code (ustmt
) == GIMPLE_ASSIGN
)
2769 gassign
*asgn
= as_a
<gassign
*> (ustmt
);
2770 tree_code code
= gimple_assign_rhs_code (asgn
);
2771 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2772 || !integer_zerop (gimple_assign_rhs2 (asgn
)))
2775 else if (gimple_code (ustmt
) == GIMPLE_COND
)
2777 tree_code code
= gimple_cond_code (ustmt
);
2778 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2779 || !integer_zerop (gimple_cond_rhs (ustmt
)))
2786 if (tree_fits_uhwi_p (len
)
2787 && (leni
= tree_to_uhwi (len
)) <= GET_MODE_SIZE (word_mode
)
2788 && pow2p_hwi (leni
))
2790 leni
*= CHAR_TYPE_SIZE
;
2791 unsigned align1
= get_pointer_alignment (arg1
);
2792 unsigned align2
= get_pointer_alignment (arg2
);
2793 unsigned align
= MIN (align1
, align2
);
2794 scalar_int_mode mode
;
2795 if (int_mode_for_size (leni
, 1).exists (&mode
)
2796 && (align
>= leni
|| !targetm
.slow_unaligned_access (mode
, align
)))
2798 location_t loc
= gimple_location (stmt2
);
2800 type
= build_nonstandard_integer_type (leni
, 1);
2801 gcc_assert (known_eq (GET_MODE_BITSIZE (TYPE_MODE (type
)), leni
));
2802 tree ptrtype
= build_pointer_type_for_mode (char_type_node
,
2804 off
= build_int_cst (ptrtype
, 0);
2805 arg1
= build2_loc (loc
, MEM_REF
, type
, arg1
, off
);
2806 arg2
= build2_loc (loc
, MEM_REF
, type
, arg2
, off
);
2807 tree tem1
= fold_const_aggregate_ref (arg1
);
2810 tree tem2
= fold_const_aggregate_ref (arg2
);
2813 res
= fold_convert_loc (loc
, TREE_TYPE (res
),
2814 fold_build2_loc (loc
, NE_EXPR
,
2817 gimplify_and_update_call_from_tree (gsi
, res
);
2822 gimple_call_set_fndecl (stmt2
, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ
));
2826 /* Given an index to the strinfo vector, compute the string length for the
2827 corresponding string. Return -1 when unknown. */
2829 static HOST_WIDE_INT
2830 compute_string_length (int idx
)
2832 HOST_WIDE_INT string_leni
= -1;
2833 gcc_assert (idx
!= 0);
2838 strinfo
*si
= get_strinfo (idx
);
2841 tree const_string_len
= get_string_length (si
);
2842 if (const_string_len
&& tree_fits_shwi_p (const_string_len
))
2843 string_leni
= tree_to_shwi (const_string_len
);
2846 if (string_leni
< 0)
2852 /* Determine the minimum size of the object referenced by DEST expression which
2853 must have a pointer type.
2854 Return the minimum size of the object if successful or NULL when the size
2855 cannot be determined. */
2857 determine_min_objsize (tree dest
)
2859 unsigned HOST_WIDE_INT size
= 0;
2861 if (compute_builtin_object_size (dest
, 2, &size
))
2862 return build_int_cst (sizetype
, size
);
2864 /* Try to determine the size of the object through the RHS of the
2865 assign statement. */
2866 if (TREE_CODE (dest
) == SSA_NAME
)
2868 gimple
*stmt
= SSA_NAME_DEF_STMT (dest
);
2869 if (!is_gimple_assign (stmt
))
2872 if (!gimple_assign_single_p (stmt
)
2873 && !gimple_assign_unary_nop_p (stmt
))
2876 dest
= gimple_assign_rhs1 (stmt
);
2877 return determine_min_objsize (dest
);
2880 /* Try to determine the size of the object from its type. */
2881 if (TREE_CODE (dest
) != ADDR_EXPR
)
2884 tree type
= TREE_TYPE (dest
);
2885 if (TREE_CODE (type
) == POINTER_TYPE
)
2886 type
= TREE_TYPE (type
);
2888 type
= TYPE_MAIN_VARIANT (type
);
2890 /* We cannot determine the size of the array if it's a flexible array,
2891 which is declared at the end of a structure. */
2892 if (TREE_CODE (type
) == ARRAY_TYPE
2893 && !array_at_struct_end_p (dest
))
2895 tree
size_t = TYPE_SIZE_UNIT (type
);
2896 if (size_t && TREE_CODE (size_t) == INTEGER_CST
2897 && !integer_zerop (size_t))
2904 /* Handle a call to strcmp or strncmp. When the result is ONLY used to do
2905 equality test against zero:
2907 A. When the lengths of both arguments are constant and it's a strcmp:
2908 * if the lengths are NOT equal, we can safely fold the call
2909 to a non-zero value.
2910 * otherwise, do nothing now.
2912 B. When the length of one argument is constant, try to replace the call with
2913 a __builtin_str(n)cmp_eq call where possible, i.e:
2915 strncmp (s, STR, C) (!)= 0 in which, s is a pointer to a string, STR is a
2916 string with constant length , C is a constant.
2917 if (C <= strlen(STR) && sizeof_array(s) > C)
2919 replace this call with
2920 strncmp_eq (s, STR, C) (!)= 0
2924 it can be safely treated as a call to strcmp (s, STR) (!)= 0
2925 can handled by the following strcmp.
2928 strcmp (s, STR) (!)= 0 in which, s is a pointer to a string, STR is a
2929 string with constant length.
2930 if (sizeof_array(s) > strlen(STR))
2932 replace this call with
2933 strcmp_eq (s, STR, strlen(STR)+1) (!)= 0
2936 Return true when the call is transformed, return false otherwise.
2940 handle_builtin_string_cmp (gimple_stmt_iterator
*gsi
)
2942 gcall
*stmt
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2943 tree res
= gimple_call_lhs (stmt
);
2944 use_operand_p use_p
;
2945 imm_use_iterator iter
;
2946 tree arg1
= gimple_call_arg (stmt
, 0);
2947 tree arg2
= gimple_call_arg (stmt
, 1);
2948 int idx1
= get_stridx (arg1
);
2949 int idx2
= get_stridx (arg2
);
2950 HOST_WIDE_INT length
= -1;
2951 bool is_ncmp
= false;
2956 /* When both arguments are unknown, do nothing. */
2957 if (idx1
== 0 && idx2
== 0)
2960 /* Handle strncmp function. */
2961 if (gimple_call_num_args (stmt
) == 3)
2963 tree len
= gimple_call_arg (stmt
, 2);
2964 if (tree_fits_shwi_p (len
))
2965 length
= tree_to_shwi (len
);
2970 /* For strncmp, if the length argument is NOT known, do nothing. */
2971 if (is_ncmp
&& length
< 0)
2974 /* When the result is ONLY used to do equality test against zero. */
2975 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
2977 gimple
*use_stmt
= USE_STMT (use_p
);
2979 if (is_gimple_debug (use_stmt
))
2981 if (gimple_code (use_stmt
) == GIMPLE_ASSIGN
)
2983 tree_code code
= gimple_assign_rhs_code (use_stmt
);
2984 if (code
== COND_EXPR
)
2986 tree cond_expr
= gimple_assign_rhs1 (use_stmt
);
2987 if ((TREE_CODE (cond_expr
) != EQ_EXPR
2988 && (TREE_CODE (cond_expr
) != NE_EXPR
))
2989 || !integer_zerop (TREE_OPERAND (cond_expr
, 1)))
2992 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
2994 if (!integer_zerop (gimple_assign_rhs2 (use_stmt
)))
3000 else if (gimple_code (use_stmt
) == GIMPLE_COND
)
3002 tree_code code
= gimple_cond_code (use_stmt
);
3003 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
3004 || !integer_zerop (gimple_cond_rhs (use_stmt
)))
3011 /* When the lengths of both arguments are known, and they are unequal, we can
3012 safely fold the call to a non-zero value for strcmp;
3013 othewise, do nothing now. */
3014 if (idx1
!= 0 && idx2
!= 0)
3016 HOST_WIDE_INT const_string_leni1
= compute_string_length (idx1
);
3017 HOST_WIDE_INT const_string_leni2
= compute_string_length (idx2
);
3020 && const_string_leni1
!= -1
3021 && const_string_leni2
!= -1
3022 && const_string_leni1
!= const_string_leni2
)
3024 replace_call_with_value (gsi
, integer_one_node
);
3030 /* When the length of one argument is constant. */
3031 tree var_string
= NULL_TREE
;
3032 HOST_WIDE_INT const_string_leni
= -1;
3036 const_string_leni
= compute_string_length (idx1
);
3041 gcc_checking_assert (idx2
);
3042 const_string_leni
= compute_string_length (idx2
);
3046 if (const_string_leni
< 0)
3049 unsigned HOST_WIDE_INT var_sizei
= 0;
3050 /* try to determine the minimum size of the object pointed by var_string. */
3051 tree size
= determine_min_objsize (var_string
);
3056 if (tree_fits_uhwi_p (size
))
3057 var_sizei
= tree_to_uhwi (size
);
3062 /* For strncmp, if length > const_string_leni , this call can be safely
3063 transformed to a strcmp. */
3064 if (is_ncmp
&& length
> const_string_leni
)
3067 unsigned HOST_WIDE_INT final_length
3068 = is_ncmp
? length
: const_string_leni
+ 1;
3070 /* Replace strcmp or strncmp with the corresponding str(n)cmp_eq. */
3071 if (var_sizei
> final_length
)
3075 ? builtin_decl_implicit (BUILT_IN_STRNCMP_EQ
)
3076 : builtin_decl_implicit (BUILT_IN_STRCMP_EQ
));
3079 tree const_string_len
= build_int_cst (size_type_node
, final_length
);
3080 update_gimple_call (gsi
, fn
, 3, arg1
, arg2
, const_string_len
);
3088 /* Handle a POINTER_PLUS_EXPR statement.
3089 For p = "abcd" + 2; compute associated length, or if
3090 p = q + off is pointing to a '\0' character of a string, call
3091 zero_length_string on it. */
3094 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
3096 gimple
*stmt
= gsi_stmt (*gsi
);
3097 tree lhs
= gimple_assign_lhs (stmt
), off
;
3098 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
3106 tree off
= gimple_assign_rhs2 (stmt
);
3107 if (tree_fits_uhwi_p (off
)
3108 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
3109 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
3110 = ~(~idx
- (int) tree_to_uhwi (off
));
3114 si
= get_strinfo (idx
);
3115 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
3118 off
= gimple_assign_rhs2 (stmt
);
3120 if (si
->full_string_p
&& operand_equal_p (si
->nonzero_chars
, off
, 0))
3121 zsi
= zero_length_string (lhs
, si
);
3122 else if (TREE_CODE (off
) == SSA_NAME
)
3124 gimple
*def_stmt
= SSA_NAME_DEF_STMT (off
);
3125 if (gimple_assign_single_p (def_stmt
)
3126 && si
->full_string_p
3127 && operand_equal_p (si
->nonzero_chars
,
3128 gimple_assign_rhs1 (def_stmt
), 0))
3129 zsi
= zero_length_string (lhs
, si
);
3132 && si
->endptr
!= NULL_TREE
3133 && si
->endptr
!= lhs
3134 && TREE_CODE (si
->endptr
) == SSA_NAME
)
3136 enum tree_code rhs_code
3137 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
3138 ? SSA_NAME
: NOP_EXPR
;
3139 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
);
3140 gcc_assert (gsi_stmt (*gsi
) == stmt
);
3145 /* If RHS, either directly or indirectly, refers to a string of constant
3146 length, return the length. Otherwise, if it refers to a character
3147 constant, return 1 if the constant is non-zero and 0 if it is nul.
3148 Otherwise, return a negative value. */
3150 static HOST_WIDE_INT
3151 get_min_string_length (tree rhs
, bool *full_string_p
)
3153 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs
)))
3155 if (tree_expr_nonzero_p (rhs
))
3157 *full_string_p
= false;
3161 *full_string_p
= true;
3165 if (TREE_CODE (rhs
) == MEM_REF
3166 && integer_zerop (TREE_OPERAND (rhs
, 1)))
3168 rhs
= TREE_OPERAND (rhs
, 0);
3169 if (TREE_CODE (rhs
) == ADDR_EXPR
)
3171 tree rhs_addr
= rhs
;
3173 rhs
= TREE_OPERAND (rhs
, 0);
3174 if (TREE_CODE (rhs
) != STRING_CST
)
3176 int idx
= get_stridx (rhs_addr
);
3179 strinfo
*si
= get_strinfo (idx
);
3181 && tree_fits_shwi_p (si
->nonzero_chars
))
3183 *full_string_p
= si
->full_string_p
;
3184 return tree_to_shwi (si
->nonzero_chars
);
3191 if (TREE_CODE (rhs
) == VAR_DECL
3192 && TREE_READONLY (rhs
))
3193 rhs
= DECL_INITIAL (rhs
);
3195 if (rhs
&& TREE_CODE (rhs
) == STRING_CST
)
3197 *full_string_p
= true;
3198 return strlen (TREE_STRING_POINTER (rhs
));
3204 /* Handle a single or multiple character store either by single
3205 character assignment or by multi-character assignment from
3209 handle_char_store (gimple_stmt_iterator
*gsi
)
3213 gimple
*stmt
= gsi_stmt (*gsi
);
3214 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
3215 tree rhs
= gimple_assign_rhs1 (stmt
);
3216 unsigned HOST_WIDE_INT offset
= 0;
3218 if (TREE_CODE (lhs
) == MEM_REF
3219 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
3221 tree mem_offset
= TREE_OPERAND (lhs
, 1);
3222 if (tree_fits_uhwi_p (mem_offset
))
3224 /* Get the strinfo for the base, and use it if it starts with at
3225 least OFFSET nonzero characters. This is trivially true if
3227 offset
= tree_to_uhwi (mem_offset
);
3228 idx
= get_stridx (TREE_OPERAND (lhs
, 0));
3230 si
= get_strinfo (idx
);
3232 ssaname
= TREE_OPERAND (lhs
, 0);
3233 else if (si
== NULL
|| compare_nonzero_chars (si
, offset
) < 0)
3239 idx
= get_addr_stridx (lhs
, NULL_TREE
, &offset
);
3241 si
= get_strinfo (idx
);
3244 /* STORING_NONZERO_P is true iff not all stored characters are zero.
3245 STORING_ALL_ZEROS_P is true iff all stored characters are zero.
3246 Both are false when it's impossible to determine which is true. */
3247 bool storing_nonzero_p
;
3248 bool storing_all_zeros_p
= initializer_zerop (rhs
, &storing_nonzero_p
);
3249 if (!storing_nonzero_p
)
3250 storing_nonzero_p
= tree_expr_nonzero_p (rhs
);
3251 bool full_string_p
= storing_all_zeros_p
;
3253 /* Set to the length of the string being assigned if known. */
3254 HOST_WIDE_INT rhslen
;
3258 int cmp
= compare_nonzero_chars (si
, offset
);
3259 gcc_assert (offset
== 0 || cmp
>= 0);
3260 if (storing_all_zeros_p
&& cmp
== 0 && si
->full_string_p
)
3262 /* When overwriting a '\0' with a '\0', the store can be removed
3263 if we know it has been stored in the current function. */
3264 if (!stmt_could_throw_p (stmt
) && si
->writable
)
3266 unlink_stmt_vdef (stmt
);
3267 release_defs (stmt
);
3268 gsi_remove (gsi
, true);
3273 si
->writable
= true;
3278 /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0',
3279 and if we aren't storing '\0', we know that the length of the
3280 string and any other zero terminated string in memory remains
3281 the same. In that case we move to the next gimple statement and
3282 return to signal the caller that it shouldn't invalidate anything.
3284 This is benefical for cases like:
3289 strcpy (p, "foobar");
3290 size_t len = strlen (p); // This can be optimized into 6
3291 size_t len2 = strlen (q); // This has to be computed
3293 size_t len3 = strlen (p); // This can be optimized into 6
3294 size_t len4 = strlen (q); // This can be optimized into len2
3295 bar (len, len2, len3, len4);
3298 else if (storing_nonzero_p
&& cmp
> 0)
3303 else if (storing_all_zeros_p
|| storing_nonzero_p
|| (offset
!= 0 && cmp
> 0))
3305 /* When STORING_NONZERO_P, we know that the string will start
3306 with at least OFFSET + 1 nonzero characters. If storing
3307 a single character, set si->NONZERO_CHARS to the result.
3308 If storing multiple characters, try to determine the number
3309 of leading non-zero characters and set si->NONZERO_CHARS to
3312 When STORING_ALL_ZEROS_P, we know that the string is now
3313 OFFSET characters long.
3315 Otherwise, we're storing an unknown value at offset OFFSET,
3316 so need to clip the nonzero_chars to OFFSET. */
3317 bool full_string_p
= storing_all_zeros_p
;
3318 HOST_WIDE_INT len
= 1;
3319 if (storing_nonzero_p
)
3321 /* Try to get the minimum length of the string (or
3322 individual character) being stored. If it fails,
3323 STORING_NONZERO_P guarantees it's at least 1. */
3324 len
= get_min_string_length (rhs
, &full_string_p
);
3329 location_t loc
= gimple_location (stmt
);
3330 tree oldlen
= si
->nonzero_chars
;
3331 if (cmp
== 0 && si
->full_string_p
)
3332 /* We're overwriting the nul terminator with a nonzero or
3333 unknown character. If the previous stmt was a memcpy,
3334 its length may be decreased. */
3335 adjust_last_stmt (si
, stmt
, false);
3336 si
= unshare_strinfo (si
);
3337 if (storing_nonzero_p
)
3339 gcc_assert (len
>= 0);
3340 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
+ len
);
3343 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
);
3344 si
->full_string_p
= full_string_p
;
3345 if (storing_all_zeros_p
3347 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
3348 si
->endptr
= ssaname
;
3353 si
->writable
= true;
3354 si
->dont_invalidate
= true;
3357 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
3358 si
->nonzero_chars
, oldlen
);
3359 adjust_related_strinfos (loc
, si
, adj
);
3365 else if (idx
== 0 && (storing_all_zeros_p
|| storing_nonzero_p
))
3368 idx
= new_stridx (ssaname
);
3370 idx
= new_addr_stridx (lhs
);
3373 tree ptr
= (ssaname
? ssaname
: build_fold_addr_expr (lhs
));
3374 HOST_WIDE_INT slen
= (storing_all_zeros_p
3376 : (storing_nonzero_p
3377 ? get_min_string_length (rhs
, &full_string_p
)
3379 tree len
= (slen
<= 0
3381 : build_int_cst (size_type_node
, slen
));
3382 si
= new_strinfo (ptr
, idx
, len
, slen
>= 0 && full_string_p
);
3383 set_strinfo (idx
, si
);
3384 if (storing_all_zeros_p
3386 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
3387 si
->endptr
= ssaname
;
3388 si
->dont_invalidate
= true;
3389 si
->writable
= true;
3393 && (rhslen
= get_min_string_length (rhs
, &full_string_p
)) >= 0
3394 && ssaname
== NULL_TREE
3395 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
3397 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
3398 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> (unsigned HOST_WIDE_INT
) rhslen
)
3400 int idx
= new_addr_stridx (lhs
);
3403 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
3404 build_int_cst (size_type_node
, rhslen
),
3406 set_strinfo (idx
, si
);
3407 si
->dont_invalidate
= true;
3412 if (si
!= NULL
&& offset
== 0 && storing_all_zeros_p
)
3414 /* Allow adjust_last_stmt to remove it if the stored '\0'
3415 is immediately overwritten. */
3416 laststmt
.stmt
= stmt
;
3417 laststmt
.len
= build_int_cst (size_type_node
, 1);
3418 laststmt
.stridx
= si
->idx
;
3423 /* Try to fold strstr (s, t) eq/ne s to strncmp (s, t, strlen (t)) eq/ne 0. */
3426 fold_strstr_to_strncmp (tree rhs1
, tree rhs2
, gimple
*stmt
)
3428 if (TREE_CODE (rhs1
) != SSA_NAME
3429 || TREE_CODE (rhs2
) != SSA_NAME
)
3432 gimple
*call_stmt
= NULL
;
3433 for (int pass
= 0; pass
< 2; pass
++)
3435 gimple
*g
= SSA_NAME_DEF_STMT (rhs1
);
3436 if (gimple_call_builtin_p (g
, BUILT_IN_STRSTR
)
3437 && has_single_use (rhs1
)
3438 && gimple_call_arg (g
, 0) == rhs2
)
3443 std::swap (rhs1
, rhs2
);
3448 tree arg0
= gimple_call_arg (call_stmt
, 0);
3452 tree arg1
= gimple_call_arg (call_stmt
, 1);
3453 tree arg1_len
= NULL_TREE
;
3454 int idx
= get_stridx (arg1
);
3459 arg1_len
= build_int_cst (size_type_node
, ~idx
);
3462 strinfo
*si
= get_strinfo (idx
);
3464 arg1_len
= get_string_length (si
);
3468 if (arg1_len
!= NULL_TREE
)
3470 gimple_stmt_iterator gsi
= gsi_for_stmt (call_stmt
);
3471 tree strncmp_decl
= builtin_decl_explicit (BUILT_IN_STRNCMP
);
3473 if (!is_gimple_val (arg1_len
))
3475 tree arg1_len_tmp
= make_ssa_name (TREE_TYPE (arg1_len
));
3476 gassign
*arg1_stmt
= gimple_build_assign (arg1_len_tmp
,
3478 gsi_insert_before (&gsi
, arg1_stmt
, GSI_SAME_STMT
);
3479 arg1_len
= arg1_len_tmp
;
3482 gcall
*strncmp_call
= gimple_build_call (strncmp_decl
, 3,
3483 arg0
, arg1
, arg1_len
);
3484 tree strncmp_lhs
= make_ssa_name (integer_type_node
);
3485 gimple_set_vuse (strncmp_call
, gimple_vuse (call_stmt
));
3486 gimple_call_set_lhs (strncmp_call
, strncmp_lhs
);
3487 gsi_remove (&gsi
, true);
3488 gsi_insert_before (&gsi
, strncmp_call
, GSI_SAME_STMT
);
3489 tree zero
= build_zero_cst (TREE_TYPE (strncmp_lhs
));
3491 if (is_gimple_assign (stmt
))
3493 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
3495 tree cond
= gimple_assign_rhs1 (stmt
);
3496 TREE_OPERAND (cond
, 0) = strncmp_lhs
;
3497 TREE_OPERAND (cond
, 1) = zero
;
3501 gimple_assign_set_rhs1 (stmt
, strncmp_lhs
);
3502 gimple_assign_set_rhs2 (stmt
, zero
);
3507 gcond
*cond
= as_a
<gcond
*> (stmt
);
3508 gimple_cond_set_lhs (cond
, strncmp_lhs
);
3509 gimple_cond_set_rhs (cond
, zero
);
3517 /* Attempt to check for validity of the performed access a single statement
3518 at *GSI using string length knowledge, and to optimize it.
3519 If the given basic block needs clean-up of EH, CLEANUP_EH is set to
3523 strlen_check_and_optimize_stmt (gimple_stmt_iterator
*gsi
, bool *cleanup_eh
)
3525 gimple
*stmt
= gsi_stmt (*gsi
);
3527 if (is_gimple_call (stmt
))
3529 tree callee
= gimple_call_fndecl (stmt
);
3530 if (valid_builtin_call (stmt
))
3531 switch (DECL_FUNCTION_CODE (callee
))
3533 case BUILT_IN_STRLEN
:
3534 case BUILT_IN_STRNLEN
:
3535 handle_builtin_strlen (gsi
);
3537 case BUILT_IN_STRCHR
:
3538 handle_builtin_strchr (gsi
);
3540 case BUILT_IN_STRCPY
:
3541 case BUILT_IN_STRCPY_CHK
:
3542 case BUILT_IN_STPCPY
:
3543 case BUILT_IN_STPCPY_CHK
:
3544 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3547 case BUILT_IN_STRNCAT
:
3548 case BUILT_IN_STRNCAT_CHK
:
3549 handle_builtin_strncat (DECL_FUNCTION_CODE (callee
), gsi
);
3552 case BUILT_IN_STPNCPY
:
3553 case BUILT_IN_STPNCPY_CHK
:
3554 case BUILT_IN_STRNCPY
:
3555 case BUILT_IN_STRNCPY_CHK
:
3556 handle_builtin_stxncpy (DECL_FUNCTION_CODE (callee
), gsi
);
3559 case BUILT_IN_MEMCPY
:
3560 case BUILT_IN_MEMCPY_CHK
:
3561 case BUILT_IN_MEMPCPY
:
3562 case BUILT_IN_MEMPCPY_CHK
:
3563 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3565 case BUILT_IN_STRCAT
:
3566 case BUILT_IN_STRCAT_CHK
:
3567 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
3569 case BUILT_IN_MALLOC
:
3570 case BUILT_IN_CALLOC
:
3571 handle_builtin_malloc (DECL_FUNCTION_CODE (callee
), gsi
);
3573 case BUILT_IN_MEMSET
:
3574 if (handle_builtin_memset (gsi
))
3577 case BUILT_IN_MEMCMP
:
3578 if (handle_builtin_memcmp (gsi
))
3581 case BUILT_IN_STRCMP
:
3582 case BUILT_IN_STRNCMP
:
3583 if (handle_builtin_string_cmp (gsi
))
3590 else if (is_gimple_assign (stmt
) && !gimple_clobber_p (stmt
))
3592 tree lhs
= gimple_assign_lhs (stmt
);
3594 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
3596 if (gimple_assign_single_p (stmt
)
3597 || (gimple_assign_cast_p (stmt
)
3598 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
3600 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
3601 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
3603 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
3604 handle_pointer_plus (gsi
);
3606 else if (TREE_CODE (lhs
) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
3608 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3609 if (code
== COND_EXPR
)
3611 tree cond
= gimple_assign_rhs1 (stmt
);
3612 enum tree_code cond_code
= TREE_CODE (cond
);
3614 if (cond_code
== EQ_EXPR
|| cond_code
== NE_EXPR
)
3615 fold_strstr_to_strncmp (TREE_OPERAND (cond
, 0),
3616 TREE_OPERAND (cond
, 1), stmt
);
3618 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3619 fold_strstr_to_strncmp (gimple_assign_rhs1 (stmt
),
3620 gimple_assign_rhs2 (stmt
), stmt
);
3621 else if (gimple_assign_load_p (stmt
)
3622 && TREE_CODE (TREE_TYPE (lhs
)) == INTEGER_TYPE
3623 && TYPE_MODE (TREE_TYPE (lhs
)) == TYPE_MODE (char_type_node
)
3624 && (TYPE_PRECISION (TREE_TYPE (lhs
))
3625 == TYPE_PRECISION (char_type_node
))
3626 && !gimple_has_volatile_ops (stmt
))
3628 tree off
= integer_zero_node
;
3629 unsigned HOST_WIDE_INT coff
= 0;
3631 tree rhs1
= gimple_assign_rhs1 (stmt
);
3632 if (code
== MEM_REF
)
3634 idx
= get_stridx (TREE_OPERAND (rhs1
, 0));
3637 strinfo
*si
= get_strinfo (idx
);
3639 && si
->nonzero_chars
3640 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
3641 && (wi::to_widest (si
->nonzero_chars
)
3642 >= wi::to_widest (off
)))
3643 off
= TREE_OPERAND (rhs1
, 1);
3645 /* This case is not useful. See if get_addr_stridx
3646 returns something usable. */
3651 idx
= get_addr_stridx (rhs1
, NULL_TREE
, &coff
);
3654 strinfo
*si
= get_strinfo (idx
);
3656 && si
->nonzero_chars
3657 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
3659 widest_int w1
= wi::to_widest (si
->nonzero_chars
);
3660 widest_int w2
= wi::to_widest (off
) + coff
;
3662 && si
->full_string_p
)
3664 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3666 fprintf (dump_file
, "Optimizing: ");
3667 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3670 /* Reading the final '\0' character. */
3671 tree zero
= build_int_cst (TREE_TYPE (lhs
), 0);
3672 gimple_set_vuse (stmt
, NULL_TREE
);
3673 gimple_assign_set_rhs_from_tree (gsi
, zero
);
3675 |= maybe_clean_or_replace_eh_stmt (stmt
,
3677 stmt
= gsi_stmt (*gsi
);
3680 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3682 fprintf (dump_file
, "into: ");
3683 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3688 /* Reading a character before the final '\0'
3689 character. Just set the value range to ~[0, 0]
3690 if we don't have anything better. */
3692 tree type
= TREE_TYPE (lhs
);
3693 enum value_range_type vr
3694 = get_range_info (lhs
, &min
, &max
);
3695 if (vr
== VR_VARYING
3697 && min
== wi::min_value (TYPE_PRECISION (type
),
3699 && max
== wi::max_value (TYPE_PRECISION (type
),
3701 set_range_info (lhs
, VR_ANTI_RANGE
,
3702 wi::zero (TYPE_PRECISION (type
)),
3703 wi::zero (TYPE_PRECISION (type
)));
3709 if (strlen_to_stridx
)
3711 tree rhs1
= gimple_assign_rhs1 (stmt
);
3712 if (stridx_strlenloc
*ps
= strlen_to_stridx
->get (rhs1
))
3713 strlen_to_stridx
->put (lhs
, stridx_strlenloc (*ps
));
3716 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
3718 tree type
= TREE_TYPE (lhs
);
3719 if (TREE_CODE (type
) == ARRAY_TYPE
)
3720 type
= TREE_TYPE (type
);
3721 if (TREE_CODE (type
) == INTEGER_TYPE
3722 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
3723 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
3725 if (! handle_char_store (gsi
))
3730 else if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
3732 enum tree_code code
= gimple_cond_code (cond
);
3733 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3734 fold_strstr_to_strncmp (gimple_cond_lhs (stmt
),
3735 gimple_cond_rhs (stmt
), stmt
);
3738 if (gimple_vdef (stmt
))
3739 maybe_invalidate (stmt
);
3743 /* Recursively call maybe_invalidate on stmts that might be executed
3744 in between dombb and current bb and that contain a vdef. Stop when
3745 *count stmts are inspected, or if the whole strinfo vector has
3746 been invalidated. */
3749 do_invalidate (basic_block dombb
, gimple
*phi
, bitmap visited
, int *count
)
3751 unsigned int i
, n
= gimple_phi_num_args (phi
);
3753 for (i
= 0; i
< n
; i
++)
3755 tree vuse
= gimple_phi_arg_def (phi
, i
);
3756 gimple
*stmt
= SSA_NAME_DEF_STMT (vuse
);
3757 basic_block bb
= gimple_bb (stmt
);
3760 || !bitmap_set_bit (visited
, bb
->index
)
3761 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3765 if (gimple_code (stmt
) == GIMPLE_PHI
)
3767 do_invalidate (dombb
, stmt
, visited
, count
);
3774 if (!maybe_invalidate (stmt
))
3779 vuse
= gimple_vuse (stmt
);
3780 stmt
= SSA_NAME_DEF_STMT (vuse
);
3781 if (gimple_bb (stmt
) != bb
)
3783 bb
= gimple_bb (stmt
);
3786 || !bitmap_set_bit (visited
, bb
->index
)
3787 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3794 class strlen_dom_walker
: public dom_walker
3797 strlen_dom_walker (cdi_direction direction
)
3798 : dom_walker (direction
), m_cleanup_cfg (false)
3801 virtual edge
before_dom_children (basic_block
);
3802 virtual void after_dom_children (basic_block
);
3804 /* Flag that will trigger TODO_cleanup_cfg to be returned in strlen
3805 execute function. */
3809 /* Callback for walk_dominator_tree. Attempt to optimize various
3810 string ops by remembering string lengths pointed by pointer SSA_NAMEs. */
3813 strlen_dom_walker::before_dom_children (basic_block bb
)
3815 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
3818 stridx_to_strinfo
= NULL
;
3821 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) dombb
->aux
);
3822 if (stridx_to_strinfo
)
3824 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3827 gphi
*phi
= gsi
.phi ();
3828 if (virtual_operand_p (gimple_phi_result (phi
)))
3830 bitmap visited
= BITMAP_ALLOC (NULL
);
3831 int count_vdef
= 100;
3832 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
3833 BITMAP_FREE (visited
);
3834 if (count_vdef
== 0)
3836 /* If there were too many vdefs in between immediate
3837 dominator and current bb, invalidate everything.
3838 If stridx_to_strinfo has been unshared, we need
3839 to free it, otherwise just set it to NULL. */
3840 if (!strinfo_shared ())
3846 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
3850 (*stridx_to_strinfo
)[i
] = NULL
;
3854 stridx_to_strinfo
= NULL
;
3862 /* If all PHI arguments have the same string index, the PHI result
3864 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3867 gphi
*phi
= gsi
.phi ();
3868 tree result
= gimple_phi_result (phi
);
3869 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
3871 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
3874 unsigned int i
, n
= gimple_phi_num_args (phi
);
3875 for (i
= 1; i
< n
; i
++)
3876 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
3879 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
3884 bool cleanup_eh
= false;
3886 /* Attempt to optimize individual statements. */
3887 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
3888 if (strlen_check_and_optimize_stmt (&gsi
, &cleanup_eh
))
3891 if (cleanup_eh
&& gimple_purge_dead_eh_edges (bb
))
3892 m_cleanup_cfg
= true;
3894 bb
->aux
= stridx_to_strinfo
;
3895 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
3896 (*stridx_to_strinfo
)[0] = (strinfo
*) bb
;
3900 /* Callback for walk_dominator_tree. Free strinfo vector if it is
3901 owned by the current bb, clear bb->aux. */
3904 strlen_dom_walker::after_dom_children (basic_block bb
)
3908 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) bb
->aux
);
3909 if (vec_safe_length (stridx_to_strinfo
)
3910 && (*stridx_to_strinfo
)[0] == (strinfo
*) bb
)
3915 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
3917 vec_free (stridx_to_strinfo
);
3923 /* Main entry point. */
3927 const pass_data pass_data_strlen
=
3929 GIMPLE_PASS
, /* type */
3930 "strlen", /* name */
3931 OPTGROUP_NONE
, /* optinfo_flags */
3932 TV_TREE_STRLEN
, /* tv_id */
3933 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3934 0, /* properties_provided */
3935 0, /* properties_destroyed */
3936 0, /* todo_flags_start */
3937 0, /* todo_flags_finish */
3940 class pass_strlen
: public gimple_opt_pass
3943 pass_strlen (gcc::context
*ctxt
)
3944 : gimple_opt_pass (pass_data_strlen
, ctxt
)
3947 /* opt_pass methods: */
3948 virtual bool gate (function
*) { return flag_optimize_strlen
!= 0; }
3949 virtual unsigned int execute (function
*);
3951 }; // class pass_strlen
3954 pass_strlen::execute (function
*fun
)
3956 gcc_assert (!strlen_to_stridx
);
3957 if (warn_stringop_overflow
|| warn_stringop_truncation
)
3958 strlen_to_stridx
= new hash_map
<tree
, stridx_strlenloc
> ();
3960 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
3963 calculate_dominance_info (CDI_DOMINATORS
);
3965 /* String length optimization is implemented as a walk of the dominator
3966 tree and a forward walk of statements within each block. */
3967 strlen_dom_walker
walker (CDI_DOMINATORS
);
3968 walker
.walk (fun
->cfg
->x_entry_block_ptr
);
3970 ssa_ver_to_stridx
.release ();
3971 strinfo_pool
.release ();
3972 if (decl_to_stridxlist_htab
)
3974 obstack_free (&stridx_obstack
, NULL
);
3975 delete decl_to_stridxlist_htab
;
3976 decl_to_stridxlist_htab
= NULL
;
3978 laststmt
.stmt
= NULL
;
3979 laststmt
.len
= NULL_TREE
;
3980 laststmt
.stridx
= 0;
3982 if (strlen_to_stridx
)
3984 strlen_to_stridx
->empty ();
3985 delete strlen_to_stridx
;
3986 strlen_to_stridx
= NULL
;
3989 return walker
.m_cleanup_cfg
? TODO_cleanup_cfg
: 0;
3995 make_pass_strlen (gcc::context
*ctxt
)
3997 return new pass_strlen (ctxt
);