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 else if (TREE_CODE (len
) == SSA_NAME
)
1113 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1114 if (!is_gimple_assign (def_stmt
)
1115 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1116 || gimple_assign_rhs1 (def_stmt
) != last
.len
1117 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1123 gimple_call_set_arg (last
.stmt
, len_arg_no
, last
.len
);
1124 update_stmt (last
.stmt
);
1127 /* For an LHS that is an SSA_NAME and for strlen() or strnlen() argument
1128 SRC, set LHS range info to [0, min (N, BOUND)] if SRC refers to
1129 a character array A[N] with unknown length bounded by N, and for
1130 strnlen(), by min (N, BOUND). */
1133 maybe_set_strlen_range (tree lhs
, tree src
, tree bound
)
1135 if (TREE_CODE (lhs
) != SSA_NAME
1136 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
1139 if (TREE_CODE (src
) == SSA_NAME
)
1141 gimple
*def
= SSA_NAME_DEF_STMT (src
);
1142 if (is_gimple_assign (def
)
1143 && gimple_assign_rhs_code (def
) == ADDR_EXPR
)
1144 src
= gimple_assign_rhs1 (def
);
1147 wide_int max
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
));
1148 wide_int min
= wi::zero (max
.get_precision ());
1150 if (TREE_CODE (src
) == ADDR_EXPR
)
1152 /* The last array member of a struct can be bigger than its size
1153 suggests if it's treated as a poor-man's flexible array member. */
1154 src
= TREE_OPERAND (src
, 0);
1155 bool src_is_array
= TREE_CODE (TREE_TYPE (src
)) == ARRAY_TYPE
;
1156 if (src_is_array
&& !array_at_struct_end_p (src
))
1158 tree type
= TREE_TYPE (src
);
1159 if (tree dom
= TYPE_DOMAIN (type
))
1161 tree maxval
= TYPE_MAX_VALUE (dom
);
1163 max
= wi::to_wide (maxval
);
1165 max
= wi::zero (min
.get_precision ());
1167 /* For strlen() the upper bound above is equal to
1168 the longest string that can be stored in the array
1169 (i.e., it accounts for the terminating nul. For
1170 strnlen() bump up the maximum by one since the array
1171 need not be nul-terminated. */
1178 if (TREE_CODE (src
) == COMPONENT_REF
&& !src_is_array
)
1179 src
= TREE_OPERAND (src
, 1);
1182 /* Handle the unlikely case of strlen (&c) where c is some
1184 if (tree size
= DECL_SIZE_UNIT (src
))
1185 if (TREE_CODE (size
) == INTEGER_CST
)
1186 max
= wi::to_wide (size
);
1193 /* For strnlen, adjust MIN and MAX as necessary. If the bound
1194 is less than the size of the array set MAX to it. It it's
1195 greater than MAX and MAX is non-zero bump MAX down to account
1196 for the necessary terminating nul. Otherwise leave it alone. */
1197 if (TREE_CODE (bound
) == INTEGER_CST
)
1199 wide_int wibnd
= wi::to_wide (bound
);
1200 int cmp
= wi::cmpu (wibnd
, max
);
1203 else if (cmp
&& wi::ne_p (max
, min
))
1206 else if (TREE_CODE (bound
) == SSA_NAME
)
1208 wide_int minbound
, maxbound
;
1209 value_range_type rng
= get_range_info (bound
, &minbound
, &maxbound
);
1210 if (rng
== VR_RANGE
)
1212 /* For a bound in a known range, adjust the range determined
1213 above as necessary. For a bound in some anti-range or
1214 in an unknown range, use the range determined above. */
1215 if (wi::ltu_p (minbound
, min
))
1217 if (wi::ltu_p (maxbound
, max
))
1224 return wide_int_to_tree (size_type_node
, min
);
1226 set_range_info (lhs
, VR_RANGE
, min
, max
);
1230 /* Handle a strlen call. If strlen of the argument is known, replace
1231 the strlen call with the known value, otherwise remember that strlen
1232 of the argument is stored in the lhs SSA_NAME. */
1235 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
1237 gimple
*stmt
= gsi_stmt (*gsi
);
1238 tree lhs
= gimple_call_lhs (stmt
);
1240 if (lhs
== NULL_TREE
)
1243 location_t loc
= gimple_location (stmt
);
1244 tree callee
= gimple_call_fndecl (stmt
);
1245 tree src
= gimple_call_arg (stmt
, 0);
1246 tree bound
= (DECL_FUNCTION_CODE (callee
) == BUILT_IN_STRNLEN
1247 ? gimple_call_arg (stmt
, 1) : NULL_TREE
);
1248 int idx
= get_stridx (src
);
1255 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
1259 si
= get_strinfo (idx
);
1261 rhs
= get_string_length (si
);
1263 if (rhs
!= NULL_TREE
)
1265 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1267 fprintf (dump_file
, "Optimizing: ");
1268 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1270 rhs
= unshare_expr (rhs
);
1271 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
1272 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1274 rhs
= fold_build2_loc (loc
, MIN_EXPR
, TREE_TYPE (rhs
), rhs
, bound
);
1275 if (!update_call_from_tree (gsi
, rhs
))
1276 gimplify_and_update_call_from_tree (gsi
, rhs
);
1277 stmt
= gsi_stmt (*gsi
);
1279 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1281 fprintf (dump_file
, "into: ");
1282 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1285 && TREE_CODE (si
->nonzero_chars
) != SSA_NAME
1286 && TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
1287 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1289 si
= unshare_strinfo (si
);
1290 si
->nonzero_chars
= lhs
;
1291 gcc_assert (si
->full_string_p
);
1294 if (strlen_to_stridx
)
1295 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1300 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1303 idx
= new_stridx (src
);
1306 strinfo
*si
= get_strinfo (idx
);
1309 if (!si
->full_string_p
&& !si
->stmt
)
1311 /* Until now we only had a lower bound on the string length.
1312 Install LHS as the actual length. */
1313 si
= unshare_strinfo (si
);
1314 tree old
= si
->nonzero_chars
;
1315 si
->nonzero_chars
= lhs
;
1316 si
->full_string_p
= true;
1317 if (TREE_CODE (old
) == INTEGER_CST
)
1319 old
= fold_convert_loc (loc
, TREE_TYPE (lhs
), old
);
1320 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1321 TREE_TYPE (lhs
), lhs
, old
);
1322 adjust_related_strinfos (loc
, si
, adj
);
1336 strinfo
*si
= new_strinfo (src
, idx
, lhs
, true);
1337 set_strinfo (idx
, si
);
1338 find_equal_ptrs (src
, idx
);
1340 /* For SRC that is an array of N elements, set LHS's range
1341 to [0, min (N, BOUND)]. A constant return value means
1342 the range would have consisted of a single value. In
1343 that case, fold the result into the returned constant. */
1344 if (tree ret
= maybe_set_strlen_range (lhs
, src
, bound
))
1345 if (TREE_CODE (ret
) == INTEGER_CST
)
1347 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1349 fprintf (dump_file
, "Optimizing: ");
1350 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1352 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (ret
)))
1353 ret
= fold_convert_loc (loc
, TREE_TYPE (lhs
), ret
);
1354 if (!update_call_from_tree (gsi
, ret
))
1355 gimplify_and_update_call_from_tree (gsi
, ret
);
1356 stmt
= gsi_stmt (*gsi
);
1358 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1360 fprintf (dump_file
, "into: ");
1361 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1365 if (strlen_to_stridx
)
1366 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1370 /* Handle a strchr call. If strlen of the first argument is known, replace
1371 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
1372 that lhs of the call is endptr and strlen of the argument is endptr - x. */
1375 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
1379 gimple
*stmt
= gsi_stmt (*gsi
);
1380 tree lhs
= gimple_call_lhs (stmt
);
1382 if (lhs
== NULL_TREE
)
1385 if (!integer_zerop (gimple_call_arg (stmt
, 1)))
1388 src
= gimple_call_arg (stmt
, 0);
1389 idx
= get_stridx (src
);
1396 rhs
= build_int_cst (size_type_node
, ~idx
);
1400 si
= get_strinfo (idx
);
1402 rhs
= get_string_length (si
);
1404 if (rhs
!= NULL_TREE
)
1406 location_t loc
= gimple_location (stmt
);
1408 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1410 fprintf (dump_file
, "Optimizing: ");
1411 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1413 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
1415 rhs
= unshare_expr (si
->endptr
);
1416 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1418 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1422 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1423 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1424 TREE_TYPE (src
), src
, rhs
);
1425 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1427 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1429 if (!update_call_from_tree (gsi
, rhs
))
1430 gimplify_and_update_call_from_tree (gsi
, rhs
);
1431 stmt
= gsi_stmt (*gsi
);
1433 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1435 fprintf (dump_file
, "into: ");
1436 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1439 && si
->endptr
== NULL_TREE
1440 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1442 si
= unshare_strinfo (si
);
1445 zero_length_string (lhs
, si
);
1449 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1451 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1454 idx
= new_stridx (src
);
1455 else if (get_strinfo (idx
) != NULL
)
1457 zero_length_string (lhs
, NULL
);
1462 location_t loc
= gimple_location (stmt
);
1463 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1464 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1465 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1466 size_type_node
, lhsu
, srcu
);
1467 strinfo
*si
= new_strinfo (src
, idx
, length
, true);
1469 set_strinfo (idx
, si
);
1470 find_equal_ptrs (src
, idx
);
1471 zero_length_string (lhs
, si
);
1475 zero_length_string (lhs
, NULL
);
1478 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1479 If strlen of the second argument is known, strlen of the first argument
1480 is the same after this call. Furthermore, attempt to convert it to
1484 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1487 tree src
, dst
, srclen
, len
, lhs
, type
, fn
, oldlen
;
1489 gimple
*stmt
= gsi_stmt (*gsi
);
1490 strinfo
*si
, *dsi
, *olddsi
, *zsi
;
1493 src
= gimple_call_arg (stmt
, 1);
1494 dst
= gimple_call_arg (stmt
, 0);
1495 lhs
= gimple_call_lhs (stmt
);
1496 idx
= get_stridx (src
);
1499 si
= get_strinfo (idx
);
1501 didx
= get_stridx (dst
);
1505 olddsi
= get_strinfo (didx
);
1510 adjust_last_stmt (olddsi
, stmt
, false);
1514 srclen
= get_string_length (si
);
1516 srclen
= build_int_cst (size_type_node
, ~idx
);
1518 loc
= gimple_location (stmt
);
1519 if (srclen
== NULL_TREE
)
1522 case BUILT_IN_STRCPY
:
1523 case BUILT_IN_STRCPY_CHK
:
1524 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1527 case BUILT_IN_STPCPY
:
1528 case BUILT_IN_STPCPY_CHK
:
1529 if (lhs
== NULL_TREE
)
1533 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1534 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1535 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1545 didx
= new_stridx (dst
);
1551 oldlen
= olddsi
->nonzero_chars
;
1552 dsi
= unshare_strinfo (olddsi
);
1553 dsi
->nonzero_chars
= srclen
;
1554 dsi
->full_string_p
= (srclen
!= NULL_TREE
);
1555 /* Break the chain, so adjust_related_strinfo on later pointers in
1556 the chain won't adjust this one anymore. */
1559 dsi
->endptr
= NULL_TREE
;
1563 dsi
= new_strinfo (dst
, didx
, srclen
, srclen
!= NULL_TREE
);
1564 set_strinfo (didx
, dsi
);
1565 find_equal_ptrs (dst
, didx
);
1567 dsi
->writable
= true;
1568 dsi
->dont_invalidate
= true;
1570 if (dsi
->nonzero_chars
== NULL_TREE
)
1574 /* If string length of src is unknown, use delayed length
1575 computation. If string lenth of dst will be needed, it
1576 can be computed by transforming this strcpy call into
1577 stpcpy and subtracting dst from the return value. */
1579 /* Look for earlier strings whose length could be determined if
1580 this strcpy is turned into an stpcpy. */
1582 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1584 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1586 /* When setting a stmt for delayed length computation
1587 prevent all strinfos through dsi from being
1589 chainsi
= unshare_strinfo (chainsi
);
1590 chainsi
->stmt
= stmt
;
1591 chainsi
->nonzero_chars
= NULL_TREE
;
1592 chainsi
->full_string_p
= false;
1593 chainsi
->endptr
= NULL_TREE
;
1594 chainsi
->dont_invalidate
= true;
1599 /* Try to detect overlap before returning. This catches cases
1600 like strcpy (d, d + n) where n is non-constant whose range
1601 is such that (n <= strlen (d) holds).
1603 OLDDSI->NONZERO_chars may have been reset by this point with
1604 oldlen holding it original value. */
1605 if (olddsi
&& oldlen
)
1607 /* Add 1 for the terminating NUL. */
1608 tree type
= TREE_TYPE (oldlen
);
1609 oldlen
= fold_build2 (PLUS_EXPR
, type
, oldlen
,
1610 build_int_cst (type
, 1));
1611 check_bounds_or_overlap (as_a
<gcall
*>(stmt
), olddsi
->ptr
, src
,
1620 tree adj
= NULL_TREE
;
1621 if (oldlen
== NULL_TREE
)
1623 else if (integer_zerop (oldlen
))
1625 else if (TREE_CODE (oldlen
) == INTEGER_CST
1626 || TREE_CODE (srclen
) == INTEGER_CST
)
1627 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1628 TREE_TYPE (srclen
), srclen
,
1629 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1631 if (adj
!= NULL_TREE
)
1632 adjust_related_strinfos (loc
, dsi
, adj
);
1636 /* strcpy src may not overlap dst, so src doesn't need to be
1637 invalidated either. */
1639 si
->dont_invalidate
= true;
1645 case BUILT_IN_STRCPY
:
1646 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1648 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1650 case BUILT_IN_STRCPY_CHK
:
1651 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1653 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1655 case BUILT_IN_STPCPY
:
1656 /* This would need adjustment of the lhs (subtract one),
1657 or detection that the trailing '\0' doesn't need to be
1658 written, if it will be immediately overwritten.
1659 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1663 zsi
= zero_length_string (lhs
, dsi
);
1666 case BUILT_IN_STPCPY_CHK
:
1667 /* This would need adjustment of the lhs (subtract one),
1668 or detection that the trailing '\0' doesn't need to be
1669 written, if it will be immediately overwritten.
1670 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1674 zsi
= zero_length_string (lhs
, dsi
);
1681 zsi
->dont_invalidate
= true;
1685 tree args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1686 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1689 type
= size_type_node
;
1691 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1692 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1694 /* Set the no-warning bit on the transformed statement? */
1695 bool set_no_warning
= false;
1697 if (const strinfo
*chksi
= olddsi
? olddsi
: dsi
)
1699 && !check_bounds_or_overlap (as_a
<gcall
*>(stmt
), chksi
->ptr
, si
->ptr
,
1702 gimple_set_no_warning (stmt
, true);
1703 set_no_warning
= true;
1706 if (fn
== NULL_TREE
)
1709 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1711 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1713 fprintf (dump_file
, "Optimizing: ");
1714 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1716 if (gimple_call_num_args (stmt
) == 2)
1717 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1719 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1720 gimple_call_arg (stmt
, 2));
1723 stmt
= gsi_stmt (*gsi
);
1725 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1727 fprintf (dump_file
, "into: ");
1728 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1730 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1731 laststmt
.stmt
= stmt
;
1732 laststmt
.len
= srclen
;
1733 laststmt
.stridx
= dsi
->idx
;
1735 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1736 fprintf (dump_file
, "not possible.\n");
1739 gimple_set_no_warning (stmt
, true);
1742 /* Check the size argument to the built-in forms of stpncpy and strncpy
1743 for out-of-bounds offsets or overlapping access, and to see if the
1744 size argument is derived from a call to strlen() on the source argument,
1745 and if so, issue an appropriate warning. */
1748 handle_builtin_strncat (built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1750 /* Same as stxncpy(). */
1751 handle_builtin_stxncpy (bcode
, gsi
);
1754 /* Return true if LEN depends on a call to strlen(SRC) in an interesting
1755 way. LEN can either be an integer expression, or a pointer (to char).
1756 When it is the latter (such as in recursive calls to self) is is
1757 assumed to be the argument in some call to strlen() whose relationship
1758 to SRC is being ascertained. */
1761 is_strlen_related_p (tree src
, tree len
)
1763 if (TREE_CODE (TREE_TYPE (len
)) == POINTER_TYPE
1764 && operand_equal_p (src
, len
, 0))
1767 if (TREE_CODE (len
) != SSA_NAME
)
1770 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1774 if (is_gimple_call (def_stmt
))
1776 tree func
= gimple_call_fndecl (def_stmt
);
1777 if (!valid_builtin_call (def_stmt
)
1778 || DECL_FUNCTION_CODE (func
) != BUILT_IN_STRLEN
)
1781 tree arg
= gimple_call_arg (def_stmt
, 0);
1782 return is_strlen_related_p (src
, arg
);
1785 if (!is_gimple_assign (def_stmt
))
1788 tree_code code
= gimple_assign_rhs_code (def_stmt
);
1789 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1790 tree rhstype
= TREE_TYPE (rhs1
);
1792 if ((TREE_CODE (rhstype
) == POINTER_TYPE
&& code
== POINTER_PLUS_EXPR
)
1793 || (INTEGRAL_TYPE_P (rhstype
)
1794 && (code
== BIT_AND_EXPR
1795 || code
== NOP_EXPR
)))
1797 /* Pointer plus (an integer), and truncation are considered among
1798 the (potentially) related expressions to strlen. */
1799 return is_strlen_related_p (src
, rhs1
);
1802 if (tree rhs2
= gimple_assign_rhs2 (def_stmt
))
1804 /* Integer subtraction is considered strlen-related when both
1805 arguments are integers and second one is strlen-related. */
1806 rhstype
= TREE_TYPE (rhs2
);
1807 if (INTEGRAL_TYPE_P (rhstype
) && code
== MINUS_EXPR
)
1808 return is_strlen_related_p (src
, rhs2
);
1814 /* Called by handle_builtin_stxncpy and by gimple_fold_builtin_strncpy
1816 Check to see if the specified bound is a) equal to the size of
1817 the destination DST and if so, b) if it's immediately followed by
1818 DST[CNT - 1] = '\0'. If a) holds and b) does not, warn. Otherwise,
1819 do nothing. Return true if diagnostic has been issued.
1821 The purpose is to diagnose calls to strncpy and stpncpy that do
1822 not nul-terminate the copy while allowing for the idiom where
1823 such a call is immediately followed by setting the last element
1826 strncpy (a, s, sizeof a);
1827 a[sizeof a - 1] = '\0';
1831 maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi
, tree src
, tree cnt
)
1833 gimple
*stmt
= gsi_stmt (gsi
);
1834 if (gimple_no_warning_p (stmt
))
1837 wide_int cntrange
[2];
1839 if (TREE_CODE (cnt
) == INTEGER_CST
)
1840 cntrange
[0] = cntrange
[1] = wi::to_wide (cnt
);
1841 else if (TREE_CODE (cnt
) == SSA_NAME
)
1843 enum value_range_type rng
= get_range_info (cnt
, cntrange
, cntrange
+ 1);
1844 if (rng
== VR_RANGE
)
1846 else if (rng
== VR_ANTI_RANGE
)
1848 wide_int maxobjsize
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
));
1850 if (wi::ltu_p (cntrange
[1], maxobjsize
))
1852 cntrange
[0] = cntrange
[1] + 1;
1853 cntrange
[1] = maxobjsize
;
1857 cntrange
[1] = cntrange
[0] - 1;
1858 cntrange
[0] = wi::zero (TYPE_PRECISION (TREE_TYPE (cnt
)));
1867 /* Negative value is the constant string length. If it's less than
1868 the lower bound there is no truncation. Avoid calling get_stridx()
1869 when ssa_ver_to_stridx is empty. That implies the caller isn't
1870 running under the control of this pass and ssa_ver_to_stridx hasn't
1871 been created yet. */
1872 int sidx
= ssa_ver_to_stridx
.length () ? get_stridx (src
) : 0;
1873 if (sidx
< 0 && wi::gtu_p (cntrange
[0], ~sidx
))
1876 tree dst
= gimple_call_arg (stmt
, 0);
1878 if (TREE_CODE (dstdecl
) == ADDR_EXPR
)
1879 dstdecl
= TREE_OPERAND (dstdecl
, 0);
1881 tree ref
= NULL_TREE
;
1885 /* If the source is a non-string return early to avoid warning
1886 for possible truncation (if the truncation is certain SIDX
1888 tree srcdecl
= gimple_call_arg (stmt
, 1);
1889 if (TREE_CODE (srcdecl
) == ADDR_EXPR
)
1890 srcdecl
= TREE_OPERAND (srcdecl
, 0);
1891 if (get_attr_nonstring_decl (srcdecl
, &ref
))
1895 /* Likewise, if the destination refers to a an array/pointer declared
1896 nonstring return early. */
1897 if (get_attr_nonstring_decl (dstdecl
, &ref
))
1900 /* Look for dst[i] = '\0'; after the stxncpy() call and if found
1901 avoid the truncation warning. */
1902 gsi_next_nondebug (&gsi
);
1903 gimple
*next_stmt
= gsi_stmt (gsi
);
1906 /* When there is no statement in the same basic block check
1907 the immediate successor block. */
1908 if (basic_block bb
= gimple_bb (stmt
))
1910 if (single_succ_p (bb
))
1912 /* For simplicity, ignore blocks with multiple outgoing
1913 edges for now and only consider successor blocks along
1915 edge e
= EDGE_SUCC (bb
, 0);
1916 if (!(e
->flags
& EDGE_ABNORMAL
))
1918 gsi
= gsi_start_bb (e
->dest
);
1919 next_stmt
= gsi_stmt (gsi
);
1920 if (next_stmt
&& is_gimple_debug (next_stmt
))
1922 gsi_next_nondebug (&gsi
);
1923 next_stmt
= gsi_stmt (gsi
);
1930 if (next_stmt
&& is_gimple_assign (next_stmt
))
1932 tree lhs
= gimple_assign_lhs (next_stmt
);
1933 tree_code code
= TREE_CODE (lhs
);
1934 if (code
== ARRAY_REF
|| code
== MEM_REF
)
1935 lhs
= TREE_OPERAND (lhs
, 0);
1937 tree func
= gimple_call_fndecl (stmt
);
1938 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STPNCPY
)
1940 tree ret
= gimple_call_lhs (stmt
);
1941 if (ret
&& operand_equal_p (ret
, lhs
, 0))
1945 /* Determine the base address and offset of the reference,
1946 ignoring the innermost array index. */
1947 if (TREE_CODE (ref
) == ARRAY_REF
)
1948 ref
= TREE_OPERAND (ref
, 0);
1951 tree dstbase
= get_addr_base_and_unit_offset (ref
, &dstoff
);
1954 tree lhsbase
= get_addr_base_and_unit_offset (lhs
, &lhsoff
);
1957 && known_eq (dstoff
, lhsoff
)
1958 && operand_equal_p (dstbase
, lhsbase
, 0))
1962 int prec
= TYPE_PRECISION (TREE_TYPE (cnt
));
1963 wide_int lenrange
[2];
1964 if (strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
)
1966 lenrange
[0] = (sisrc
->nonzero_chars
1967 && TREE_CODE (sisrc
->nonzero_chars
) == INTEGER_CST
1968 ? wi::to_wide (sisrc
->nonzero_chars
)
1970 lenrange
[1] = lenrange
[0];
1973 lenrange
[0] = lenrange
[1] = wi::shwi (~sidx
, prec
);
1977 get_range_strlen (src
, range
);
1978 if (range
[0] != NULL_TREE
1979 && TREE_CODE (range
[0]) == INTEGER_CST
1980 && range
[1] != NULL_TREE
1981 && TREE_CODE (range
[1]) == INTEGER_CST
)
1983 lenrange
[0] = wi::to_wide (range
[0], prec
);
1984 lenrange
[1] = wi::to_wide (range
[1], prec
);
1988 lenrange
[0] = wi::shwi (0, prec
);
1989 lenrange
[1] = wi::shwi (-1, prec
);
1993 location_t callloc
= gimple_nonartificial_location (stmt
);
1994 callloc
= expansion_point_location_if_in_system_header (callloc
);
1996 tree func
= gimple_call_fndecl (stmt
);
1998 if (lenrange
[0] != 0 || !wi::neg_p (lenrange
[1]))
2000 /* If the longest source string is shorter than the lower bound
2001 of the specified count the copy is definitely nul-terminated. */
2002 if (wi::ltu_p (lenrange
[1], cntrange
[0]))
2005 if (wi::neg_p (lenrange
[1]))
2007 /* The length of one of the strings is unknown but at least
2008 one has non-zero length and that length is stored in
2009 LENRANGE[1]. Swap the bounds to force a "may be truncated"
2011 lenrange
[1] = lenrange
[0];
2012 lenrange
[0] = wi::shwi (0, prec
);
2015 gcall
*call
= as_a
<gcall
*> (stmt
);
2017 /* Set to true for strncat whose bound is derived from the length
2018 of the destination (the expected usage pattern). */
2019 bool cat_dstlen_bounded
= false;
2020 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STRNCAT
)
2021 cat_dstlen_bounded
= is_strlen_related_p (dst
, cnt
);
2023 if (lenrange
[0] == cntrange
[1] && cntrange
[0] == cntrange
[1])
2024 return warning_n (callloc
, OPT_Wstringop_truncation
,
2025 cntrange
[0].to_uhwi (),
2026 "%G%qD output truncated before terminating "
2027 "nul copying %E byte from a string of the "
2029 "%G%qD output truncated before terminating nul "
2030 "copying %E bytes from a string of the same "
2033 else if (!cat_dstlen_bounded
)
2035 if (wi::geu_p (lenrange
[0], cntrange
[1]))
2037 /* The shortest string is longer than the upper bound of
2038 the count so the truncation is certain. */
2039 if (cntrange
[0] == cntrange
[1])
2040 return warning_n (callloc
, OPT_Wstringop_truncation
,
2041 cntrange
[0].to_uhwi (),
2042 "%G%qD output truncated copying %E byte "
2043 "from a string of length %wu",
2044 "%G%qD output truncated copying %E bytes "
2045 "from a string of length %wu",
2046 call
, func
, cnt
, lenrange
[0].to_uhwi ());
2048 return warning_at (callloc
, OPT_Wstringop_truncation
,
2049 "%G%qD output truncated copying between %wu "
2050 "and %wu bytes from a string of length %wu",
2051 call
, func
, cntrange
[0].to_uhwi (),
2052 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
2054 else if (wi::geu_p (lenrange
[1], cntrange
[1]))
2056 /* The longest string is longer than the upper bound of
2057 the count so the truncation is possible. */
2058 if (cntrange
[0] == cntrange
[1])
2059 return warning_n (callloc
, OPT_Wstringop_truncation
,
2060 cntrange
[0].to_uhwi (),
2061 "%G%qD output may be truncated copying %E "
2062 "byte from a string of length %wu",
2063 "%G%qD output may be truncated copying %E "
2064 "bytes from a string of length %wu",
2065 call
, func
, cnt
, lenrange
[1].to_uhwi ());
2067 return warning_at (callloc
, OPT_Wstringop_truncation
,
2068 "%G%qD output may be truncated copying between "
2069 "%wu and %wu bytes from a string of length %wu",
2070 call
, func
, cntrange
[0].to_uhwi (),
2071 cntrange
[1].to_uhwi (), lenrange
[1].to_uhwi ());
2075 if (!cat_dstlen_bounded
2076 && cntrange
[0] != cntrange
[1]
2077 && wi::leu_p (cntrange
[0], lenrange
[0])
2078 && wi::leu_p (cntrange
[1], lenrange
[0] + 1))
2080 /* If the source (including the terminating nul) is longer than
2081 the lower bound of the specified count but shorter than the
2082 upper bound the copy may (but need not) be truncated. */
2083 return warning_at (callloc
, OPT_Wstringop_truncation
,
2084 "%G%qD output may be truncated copying between "
2085 "%wu and %wu bytes from a string of length %wu",
2086 call
, func
, cntrange
[0].to_uhwi (),
2087 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
2091 if (tree dstsize
= compute_objsize (dst
, 1))
2093 /* The source length is uknown. Try to determine the destination
2094 size and see if it matches the specified bound. If not, bail.
2095 Otherwise go on to see if it should be diagnosed for possible
2100 if (wi::to_wide (dstsize
) != cntrange
[1])
2103 if (cntrange
[0] == cntrange
[1])
2104 return warning_at (callloc
, OPT_Wstringop_truncation
,
2105 "%G%qD specified bound %E equals destination size",
2106 as_a
<gcall
*> (stmt
), func
, cnt
);
2112 /* Check the arguments to the built-in forms of stpncpy and strncpy for
2113 out-of-bounds offsets or overlapping access, and to see if the size
2114 is derived from calling strlen() on the source argument, and if so,
2115 issue the appropriate warning. */
2118 handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*gsi
)
2120 if (!strlen_to_stridx
)
2123 gimple
*stmt
= gsi_stmt (*gsi
);
2125 tree dst
= gimple_call_arg (stmt
, 0);
2126 tree src
= gimple_call_arg (stmt
, 1);
2127 tree len
= gimple_call_arg (stmt
, 2);
2128 tree dstsize
= NULL_TREE
, srcsize
= NULL_TREE
;
2130 int didx
= get_stridx (dst
);
2131 if (strinfo
*sidst
= didx
> 0 ? get_strinfo (didx
) : NULL
)
2133 /* Compute the size of the destination string including the NUL. */
2134 if (sidst
->nonzero_chars
)
2136 tree type
= TREE_TYPE (sidst
->nonzero_chars
);
2137 dstsize
= fold_build2 (PLUS_EXPR
, type
, sidst
->nonzero_chars
,
2138 build_int_cst (type
, 1));
2143 int sidx
= get_stridx (src
);
2144 strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
;
2147 /* strncat() and strncpy() can modify the source string by writing
2148 over the terminating nul so SISRC->DONT_INVALIDATE must be left
2151 /* Compute the size of the source string including the NUL. */
2152 if (sisrc
->nonzero_chars
)
2154 tree type
= TREE_TYPE (sisrc
->nonzero_chars
);
2155 srcsize
= fold_build2 (PLUS_EXPR
, type
, sisrc
->nonzero_chars
,
2156 build_int_cst (type
, 1));
2162 srcsize
= NULL_TREE
;
2164 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, src
,
2167 gimple_set_no_warning (stmt
, true);
2171 /* If the length argument was computed from strlen(S) for some string
2172 S retrieve the strinfo index for the string (PSS->FIRST) alonng with
2173 the location of the strlen() call (PSS->SECOND). */
2174 stridx_strlenloc
*pss
= strlen_to_stridx
->get (len
);
2175 if (!pss
|| pss
->first
<= 0)
2177 if (maybe_diag_stxncpy_trunc (*gsi
, src
, len
))
2178 gimple_set_no_warning (stmt
, true);
2183 /* Retrieve the strinfo data for the string S that LEN was computed
2184 from as some function F of strlen (S) (i.e., LEN need not be equal
2186 strinfo
*silen
= get_strinfo (pss
->first
);
2188 location_t callloc
= gimple_nonartificial_location (stmt
);
2189 callloc
= expansion_point_location_if_in_system_header (callloc
);
2191 tree func
= gimple_call_fndecl (stmt
);
2193 bool warned
= false;
2195 /* When -Wstringop-truncation is set, try to determine truncation
2196 before diagnosing possible overflow. Truncation is implied by
2197 the LEN argument being equal to strlen(SRC), regardless of
2198 whether its value is known. Otherwise, issue the more generic
2199 -Wstringop-overflow which triggers for LEN arguments that in
2200 any meaningful way depend on strlen(SRC). */
2202 && is_strlen_related_p (src
, len
)
2203 && warning_at (callloc
, OPT_Wstringop_truncation
,
2204 "%G%qD output truncated before terminating nul "
2205 "copying as many bytes from a string as its length",
2206 as_a
<gcall
*>(stmt
), func
))
2208 else if (silen
&& is_strlen_related_p (src
, silen
->ptr
))
2209 warned
= warning_at (callloc
, OPT_Wstringop_overflow_
,
2210 "%G%qD specified bound depends on the length "
2211 "of the source argument",
2212 as_a
<gcall
*>(stmt
), func
);
2215 location_t strlenloc
= pss
->second
;
2216 if (strlenloc
!= UNKNOWN_LOCATION
&& strlenloc
!= callloc
)
2217 inform (strlenloc
, "length computed here");
2221 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
2222 If strlen of the second argument is known and length of the third argument
2223 is that plus one, strlen of the first argument is the same after this
2227 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2230 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
2231 gimple
*stmt
= gsi_stmt (*gsi
);
2232 strinfo
*si
, *dsi
, *olddsi
;
2234 len
= gimple_call_arg (stmt
, 2);
2235 src
= gimple_call_arg (stmt
, 1);
2236 dst
= gimple_call_arg (stmt
, 0);
2237 idx
= get_stridx (src
);
2241 didx
= get_stridx (dst
);
2244 olddsi
= get_strinfo (didx
);
2249 && tree_fits_uhwi_p (len
)
2250 && !integer_zerop (len
))
2251 adjust_last_stmt (olddsi
, stmt
, false);
2258 /* Handle memcpy (x, y, l) where l's relationship with strlen (y)
2260 si
= get_strinfo (idx
);
2261 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
2263 if (TREE_CODE (len
) == INTEGER_CST
2264 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
2266 if (tree_int_cst_le (len
, si
->nonzero_chars
))
2268 /* Copying LEN nonzero characters, where LEN is constant. */
2270 full_string_p
= false;
2274 /* Copying the whole of the analyzed part of SI. */
2275 newlen
= si
->nonzero_chars
;
2276 full_string_p
= si
->full_string_p
;
2281 if (!si
->full_string_p
)
2283 if (TREE_CODE (len
) != SSA_NAME
)
2285 def_stmt
= SSA_NAME_DEF_STMT (len
);
2286 if (!is_gimple_assign (def_stmt
)
2287 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
2288 || gimple_assign_rhs1 (def_stmt
) != si
->nonzero_chars
2289 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
2291 /* Copying variable-length string SI (and no more). */
2292 newlen
= si
->nonzero_chars
;
2293 full_string_p
= true;
2299 /* Handle memcpy (x, "abcd", 5) or
2300 memcpy (x, "abc\0uvw", 7). */
2301 if (!tree_fits_uhwi_p (len
))
2304 unsigned HOST_WIDE_INT clen
= tree_to_uhwi (len
);
2305 unsigned HOST_WIDE_INT nonzero_chars
= ~idx
;
2306 newlen
= build_int_cst (size_type_node
, MIN (nonzero_chars
, clen
));
2307 full_string_p
= clen
> nonzero_chars
;
2310 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
2311 adjust_last_stmt (olddsi
, stmt
, false);
2315 didx
= new_stridx (dst
);
2322 dsi
= unshare_strinfo (olddsi
);
2323 oldlen
= olddsi
->nonzero_chars
;
2324 dsi
->nonzero_chars
= newlen
;
2325 dsi
->full_string_p
= full_string_p
;
2326 /* Break the chain, so adjust_related_strinfo on later pointers in
2327 the chain won't adjust this one anymore. */
2330 dsi
->endptr
= NULL_TREE
;
2334 dsi
= new_strinfo (dst
, didx
, newlen
, full_string_p
);
2335 set_strinfo (didx
, dsi
);
2336 find_equal_ptrs (dst
, didx
);
2338 dsi
->writable
= true;
2339 dsi
->dont_invalidate
= true;
2342 tree adj
= NULL_TREE
;
2343 location_t loc
= gimple_location (stmt
);
2344 if (oldlen
== NULL_TREE
)
2346 else if (integer_zerop (oldlen
))
2348 else if (TREE_CODE (oldlen
) == INTEGER_CST
2349 || TREE_CODE (newlen
) == INTEGER_CST
)
2350 adj
= fold_build2_loc (loc
, MINUS_EXPR
, TREE_TYPE (newlen
), newlen
,
2351 fold_convert_loc (loc
, TREE_TYPE (newlen
),
2353 if (adj
!= NULL_TREE
)
2354 adjust_related_strinfos (loc
, dsi
, adj
);
2358 /* memcpy src may not overlap dst, so src doesn't need to be
2359 invalidated either. */
2361 si
->dont_invalidate
= true;
2365 lhs
= gimple_call_lhs (stmt
);
2368 case BUILT_IN_MEMCPY
:
2369 case BUILT_IN_MEMCPY_CHK
:
2370 /* Allow adjust_last_stmt to decrease this memcpy's size. */
2371 laststmt
.stmt
= stmt
;
2372 laststmt
.len
= dsi
->nonzero_chars
;
2373 laststmt
.stridx
= dsi
->idx
;
2375 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
2377 case BUILT_IN_MEMPCPY
:
2378 case BUILT_IN_MEMPCPY_CHK
:
2386 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
2387 If strlen of the second argument is known, strlen of the first argument
2388 is increased by the length of the second argument. Furthermore, attempt
2389 to convert it to memcpy/strcpy if the length of the first argument
2393 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2396 tree srclen
, args
, type
, fn
, objsz
, endptr
;
2398 gimple
*stmt
= gsi_stmt (*gsi
);
2400 location_t loc
= gimple_location (stmt
);
2402 tree src
= gimple_call_arg (stmt
, 1);
2403 tree dst
= gimple_call_arg (stmt
, 0);
2405 /* Bail if the source is the same as destination. It will be diagnosed
2407 if (operand_equal_p (src
, dst
, 0))
2410 tree lhs
= gimple_call_lhs (stmt
);
2412 didx
= get_stridx (dst
);
2418 dsi
= get_strinfo (didx
);
2422 idx
= get_stridx (src
);
2424 srclen
= build_int_cst (size_type_node
, ~idx
);
2427 si
= get_strinfo (idx
);
2429 srclen
= get_string_length (si
);
2432 /* Set the no-warning bit on the transformed statement? */
2433 bool set_no_warning
= false;
2435 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
2438 /* The concatenation always involves copying at least one byte
2439 (the terminating nul), even if the source string is empty.
2440 If the source is unknown assume it's one character long and
2441 used that as both sizes. */
2445 tree type
= TREE_TYPE (slen
);
2446 slen
= fold_build2 (PLUS_EXPR
, type
, slen
, build_int_cst (type
, 1));
2449 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2451 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, sptr
,
2454 gimple_set_no_warning (stmt
, true);
2455 set_no_warning
= true;
2459 /* strcat (p, q) can be transformed into
2460 tmp = p + strlen (p); endptr = stpcpy (tmp, q);
2461 with length endptr - p if we need to compute the length
2462 later on. Don't do this transformation if we don't need
2464 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
2468 didx
= new_stridx (dst
);
2474 dsi
= new_strinfo (dst
, didx
, NULL_TREE
, false);
2475 set_strinfo (didx
, dsi
);
2476 find_equal_ptrs (dst
, didx
);
2480 dsi
= unshare_strinfo (dsi
);
2481 dsi
->nonzero_chars
= NULL_TREE
;
2482 dsi
->full_string_p
= false;
2484 dsi
->endptr
= NULL_TREE
;
2486 dsi
->writable
= true;
2488 dsi
->dont_invalidate
= true;
2493 tree dstlen
= dsi
->nonzero_chars
;
2494 endptr
= dsi
->endptr
;
2496 dsi
= unshare_strinfo (dsi
);
2497 dsi
->endptr
= NULL_TREE
;
2499 dsi
->writable
= true;
2501 if (srclen
!= NULL_TREE
)
2503 dsi
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
2504 TREE_TYPE (dsi
->nonzero_chars
),
2505 dsi
->nonzero_chars
, srclen
);
2506 gcc_assert (dsi
->full_string_p
);
2507 adjust_related_strinfos (loc
, dsi
, srclen
);
2508 dsi
->dont_invalidate
= true;
2512 dsi
->nonzero_chars
= NULL
;
2513 dsi
->full_string_p
= false;
2514 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
2515 dsi
->dont_invalidate
= true;
2519 /* strcat src may not overlap dst, so src doesn't need to be
2520 invalidated either. */
2521 si
->dont_invalidate
= true;
2523 /* For now. Could remove the lhs from the call and add
2524 lhs = dst; afterwards. */
2532 case BUILT_IN_STRCAT
:
2533 if (srclen
!= NULL_TREE
)
2534 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
2536 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
2538 case BUILT_IN_STRCAT_CHK
:
2539 if (srclen
!= NULL_TREE
)
2540 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
2542 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
2543 objsz
= gimple_call_arg (stmt
, 2);
2549 if (fn
== NULL_TREE
)
2554 tree type
= TREE_TYPE (dstlen
);
2556 /* Compute the size of the source sequence, including the nul. */
2557 tree srcsize
= srclen
? srclen
: size_zero_node
;
2558 srcsize
= fold_build2 (PLUS_EXPR
, type
, srcsize
, build_int_cst (type
, 1));
2560 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2562 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, sptr
,
2565 gimple_set_no_warning (stmt
, true);
2566 set_no_warning
= true;
2570 tree len
= NULL_TREE
;
2571 if (srclen
!= NULL_TREE
)
2573 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
2574 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
2576 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
2577 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
2578 build_int_cst (type
, 1));
2579 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
2583 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
2585 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
2586 TREE_TYPE (dst
), unshare_expr (dst
),
2587 fold_convert_loc (loc
, sizetype
,
2588 unshare_expr (dstlen
)));
2589 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
2591 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2593 fprintf (dump_file
, "Optimizing: ");
2594 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2596 if (srclen
!= NULL_TREE
)
2597 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
2598 dst
, src
, len
, objsz
);
2600 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
2604 stmt
= gsi_stmt (*gsi
);
2606 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2608 fprintf (dump_file
, "into: ");
2609 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2611 /* If srclen == NULL, note that current string length can be
2612 computed by transforming this strcpy into stpcpy. */
2613 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
2615 adjust_last_stmt (dsi
, stmt
, true);
2616 if (srclen
!= NULL_TREE
)
2618 laststmt
.stmt
= stmt
;
2619 laststmt
.len
= srclen
;
2620 laststmt
.stridx
= dsi
->idx
;
2623 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2624 fprintf (dump_file
, "not possible.\n");
2627 gimple_set_no_warning (stmt
, true);
2630 /* Handle a call to malloc or calloc. */
2633 handle_builtin_malloc (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2635 gimple
*stmt
= gsi_stmt (*gsi
);
2636 tree lhs
= gimple_call_lhs (stmt
);
2637 if (lhs
== NULL_TREE
)
2640 gcc_assert (get_stridx (lhs
) == 0);
2641 int idx
= new_stridx (lhs
);
2642 tree length
= NULL_TREE
;
2643 if (bcode
== BUILT_IN_CALLOC
)
2644 length
= build_int_cst (size_type_node
, 0);
2645 strinfo
*si
= new_strinfo (lhs
, idx
, length
, length
!= NULL_TREE
);
2646 if (bcode
== BUILT_IN_CALLOC
)
2648 set_strinfo (idx
, si
);
2649 si
->writable
= true;
2651 si
->dont_invalidate
= true;
2654 /* Handle a call to memset.
2655 After a call to calloc, memset(,0,) is unnecessary.
2656 memset(malloc(n),0,n) is calloc(n,1).
2657 return true when the call is transfomred, false otherwise. */
2660 handle_builtin_memset (gimple_stmt_iterator
*gsi
)
2662 gimple
*stmt2
= gsi_stmt (*gsi
);
2663 if (!integer_zerop (gimple_call_arg (stmt2
, 1)))
2665 tree ptr
= gimple_call_arg (stmt2
, 0);
2666 int idx1
= get_stridx (ptr
);
2669 strinfo
*si1
= get_strinfo (idx1
);
2672 gimple
*stmt1
= si1
->stmt
;
2673 if (!stmt1
|| !is_gimple_call (stmt1
))
2675 tree callee1
= gimple_call_fndecl (stmt1
);
2676 if (!valid_builtin_call (stmt1
))
2678 enum built_in_function code1
= DECL_FUNCTION_CODE (callee1
);
2679 tree size
= gimple_call_arg (stmt2
, 2);
2680 if (code1
== BUILT_IN_CALLOC
)
2681 /* Not touching stmt1 */ ;
2682 else if (code1
== BUILT_IN_MALLOC
2683 && operand_equal_p (gimple_call_arg (stmt1
, 0), size
, 0))
2685 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt1
);
2686 update_gimple_call (&gsi1
, builtin_decl_implicit (BUILT_IN_CALLOC
), 2,
2687 size
, build_one_cst (size_type_node
));
2688 si1
->nonzero_chars
= build_int_cst (size_type_node
, 0);
2689 si1
->full_string_p
= true;
2690 si1
->stmt
= gsi_stmt (gsi1
);
2694 tree lhs
= gimple_call_lhs (stmt2
);
2695 unlink_stmt_vdef (stmt2
);
2698 gimple
*assign
= gimple_build_assign (lhs
, ptr
);
2699 gsi_replace (gsi
, assign
, false);
2703 gsi_remove (gsi
, true);
2704 release_defs (stmt2
);
2710 /* Handle a call to memcmp. We try to handle small comparisons by
2711 converting them to load and compare, and replacing the call to memcmp
2712 with a __builtin_memcmp_eq call where possible.
2713 return true when call is transformed, return false otherwise. */
2716 handle_builtin_memcmp (gimple_stmt_iterator
*gsi
)
2718 gcall
*stmt2
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2719 tree res
= gimple_call_lhs (stmt2
);
2720 tree arg1
= gimple_call_arg (stmt2
, 0);
2721 tree arg2
= gimple_call_arg (stmt2
, 1);
2722 tree len
= gimple_call_arg (stmt2
, 2);
2723 unsigned HOST_WIDE_INT leni
;
2724 use_operand_p use_p
;
2725 imm_use_iterator iter
;
2730 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
2732 gimple
*ustmt
= USE_STMT (use_p
);
2734 if (is_gimple_debug (ustmt
))
2736 if (gimple_code (ustmt
) == GIMPLE_ASSIGN
)
2738 gassign
*asgn
= as_a
<gassign
*> (ustmt
);
2739 tree_code code
= gimple_assign_rhs_code (asgn
);
2740 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2741 || !integer_zerop (gimple_assign_rhs2 (asgn
)))
2744 else if (gimple_code (ustmt
) == GIMPLE_COND
)
2746 tree_code code
= gimple_cond_code (ustmt
);
2747 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2748 || !integer_zerop (gimple_cond_rhs (ustmt
)))
2755 if (tree_fits_uhwi_p (len
)
2756 && (leni
= tree_to_uhwi (len
)) <= GET_MODE_SIZE (word_mode
)
2757 && pow2p_hwi (leni
))
2759 leni
*= CHAR_TYPE_SIZE
;
2760 unsigned align1
= get_pointer_alignment (arg1
);
2761 unsigned align2
= get_pointer_alignment (arg2
);
2762 unsigned align
= MIN (align1
, align2
);
2763 scalar_int_mode mode
;
2764 if (int_mode_for_size (leni
, 1).exists (&mode
)
2765 && (align
>= leni
|| !targetm
.slow_unaligned_access (mode
, align
)))
2767 location_t loc
= gimple_location (stmt2
);
2769 type
= build_nonstandard_integer_type (leni
, 1);
2770 gcc_assert (known_eq (GET_MODE_BITSIZE (TYPE_MODE (type
)), leni
));
2771 tree ptrtype
= build_pointer_type_for_mode (char_type_node
,
2773 off
= build_int_cst (ptrtype
, 0);
2774 arg1
= build2_loc (loc
, MEM_REF
, type
, arg1
, off
);
2775 arg2
= build2_loc (loc
, MEM_REF
, type
, arg2
, off
);
2776 tree tem1
= fold_const_aggregate_ref (arg1
);
2779 tree tem2
= fold_const_aggregate_ref (arg2
);
2782 res
= fold_convert_loc (loc
, TREE_TYPE (res
),
2783 fold_build2_loc (loc
, NE_EXPR
,
2786 gimplify_and_update_call_from_tree (gsi
, res
);
2791 gimple_call_set_fndecl (stmt2
, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ
));
2795 /* Given an index to the strinfo vector, compute the string length for the
2796 corresponding string. Return -1 when unknown. */
2798 static HOST_WIDE_INT
2799 compute_string_length (int idx
)
2801 HOST_WIDE_INT string_leni
= -1;
2802 gcc_assert (idx
!= 0);
2807 strinfo
*si
= get_strinfo (idx
);
2810 tree const_string_len
= get_string_length (si
);
2811 if (const_string_len
&& tree_fits_shwi_p (const_string_len
))
2812 string_leni
= tree_to_shwi (const_string_len
);
2815 if (string_leni
< 0)
2821 /* Determine the minimum size of the object referenced by DEST expression which
2822 must have a pointer type.
2823 Return the minimum size of the object if successful or NULL when the size
2824 cannot be determined. */
2826 determine_min_objsize (tree dest
)
2828 unsigned HOST_WIDE_INT size
= 0;
2830 if (compute_builtin_object_size (dest
, 2, &size
))
2831 return build_int_cst (sizetype
, size
);
2833 /* Try to determine the size of the object through the RHS of the
2834 assign statement. */
2835 if (TREE_CODE (dest
) == SSA_NAME
)
2837 gimple
*stmt
= SSA_NAME_DEF_STMT (dest
);
2838 if (!is_gimple_assign (stmt
))
2841 if (!gimple_assign_single_p (stmt
)
2842 && !gimple_assign_unary_nop_p (stmt
))
2845 dest
= gimple_assign_rhs1 (stmt
);
2846 return determine_min_objsize (dest
);
2849 /* Try to determine the size of the object from its type. */
2850 if (TREE_CODE (dest
) != ADDR_EXPR
)
2853 tree type
= TREE_TYPE (dest
);
2854 if (TREE_CODE (type
) == POINTER_TYPE
)
2855 type
= TREE_TYPE (type
);
2857 type
= TYPE_MAIN_VARIANT (type
);
2859 /* We cannot determine the size of the array if it's a flexible array,
2860 which is declared at the end of a structure. */
2861 if (TREE_CODE (type
) == ARRAY_TYPE
2862 && !array_at_struct_end_p (dest
))
2864 tree
size_t = TYPE_SIZE_UNIT (type
);
2865 if (size_t && TREE_CODE (size_t) == INTEGER_CST
2866 && !integer_zerop (size_t))
2873 /* Handle a call to strcmp or strncmp. When the result is ONLY used to do
2874 equality test against zero:
2876 A. When the lengths of both arguments are constant and it's a strcmp:
2877 * if the lengths are NOT equal, we can safely fold the call
2878 to a non-zero value.
2879 * otherwise, do nothing now.
2881 B. When the length of one argument is constant, try to replace the call with
2882 a __builtin_str(n)cmp_eq call where possible, i.e:
2884 strncmp (s, STR, C) (!)= 0 in which, s is a pointer to a string, STR is a
2885 string with constant length , C is a constant.
2886 if (C <= strlen(STR) && sizeof_array(s) > C)
2888 replace this call with
2889 strncmp_eq (s, STR, C) (!)= 0
2893 it can be safely treated as a call to strcmp (s, STR) (!)= 0
2894 can handled by the following strcmp.
2897 strcmp (s, STR) (!)= 0 in which, s is a pointer to a string, STR is a
2898 string with constant length.
2899 if (sizeof_array(s) > strlen(STR))
2901 replace this call with
2902 strcmp_eq (s, STR, strlen(STR)+1) (!)= 0
2905 Return true when the call is transformed, return false otherwise.
2909 handle_builtin_string_cmp (gimple_stmt_iterator
*gsi
)
2911 gcall
*stmt
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2912 tree res
= gimple_call_lhs (stmt
);
2913 use_operand_p use_p
;
2914 imm_use_iterator iter
;
2915 tree arg1
= gimple_call_arg (stmt
, 0);
2916 tree arg2
= gimple_call_arg (stmt
, 1);
2917 int idx1
= get_stridx (arg1
);
2918 int idx2
= get_stridx (arg2
);
2919 HOST_WIDE_INT length
= -1;
2920 bool is_ncmp
= false;
2925 /* When both arguments are unknown, do nothing. */
2926 if (idx1
== 0 && idx2
== 0)
2929 /* Handle strncmp function. */
2930 if (gimple_call_num_args (stmt
) == 3)
2932 tree len
= gimple_call_arg (stmt
, 2);
2933 if (tree_fits_shwi_p (len
))
2934 length
= tree_to_shwi (len
);
2939 /* For strncmp, if the length argument is NOT known, do nothing. */
2940 if (is_ncmp
&& length
< 0)
2943 /* When the result is ONLY used to do equality test against zero. */
2944 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
2946 gimple
*use_stmt
= USE_STMT (use_p
);
2948 if (is_gimple_debug (use_stmt
))
2950 if (gimple_code (use_stmt
) == GIMPLE_ASSIGN
)
2952 tree_code code
= gimple_assign_rhs_code (use_stmt
);
2953 if (code
== COND_EXPR
)
2955 tree cond_expr
= gimple_assign_rhs1 (use_stmt
);
2956 if ((TREE_CODE (cond_expr
) != EQ_EXPR
2957 && (TREE_CODE (cond_expr
) != NE_EXPR
))
2958 || !integer_zerop (TREE_OPERAND (cond_expr
, 1)))
2961 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
2963 if (!integer_zerop (gimple_assign_rhs2 (use_stmt
)))
2969 else if (gimple_code (use_stmt
) == GIMPLE_COND
)
2971 tree_code code
= gimple_cond_code (use_stmt
);
2972 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2973 || !integer_zerop (gimple_cond_rhs (use_stmt
)))
2980 /* When the lengths of both arguments are known, and they are unequal, we can
2981 safely fold the call to a non-zero value for strcmp;
2982 othewise, do nothing now. */
2983 if (idx1
!= 0 && idx2
!= 0)
2985 HOST_WIDE_INT const_string_leni1
= compute_string_length (idx1
);
2986 HOST_WIDE_INT const_string_leni2
= compute_string_length (idx2
);
2989 && const_string_leni1
!= -1
2990 && const_string_leni2
!= -1
2991 && const_string_leni1
!= const_string_leni2
)
2993 replace_call_with_value (gsi
, integer_one_node
);
2999 /* When the length of one argument is constant. */
3000 tree var_string
= NULL_TREE
;
3001 HOST_WIDE_INT const_string_leni
= -1;
3005 const_string_leni
= compute_string_length (idx1
);
3010 gcc_checking_assert (idx2
);
3011 const_string_leni
= compute_string_length (idx2
);
3015 if (const_string_leni
< 0)
3018 unsigned HOST_WIDE_INT var_sizei
= 0;
3019 /* try to determine the minimum size of the object pointed by var_string. */
3020 tree size
= determine_min_objsize (var_string
);
3025 if (tree_fits_uhwi_p (size
))
3026 var_sizei
= tree_to_uhwi (size
);
3031 /* For strncmp, if length > const_string_leni , this call can be safely
3032 transformed to a strcmp. */
3033 if (is_ncmp
&& length
> const_string_leni
)
3036 unsigned HOST_WIDE_INT final_length
3037 = is_ncmp
? length
: const_string_leni
+ 1;
3039 /* Replace strcmp or strncmp with the corresponding str(n)cmp_eq. */
3040 if (var_sizei
> final_length
)
3044 ? builtin_decl_implicit (BUILT_IN_STRNCMP_EQ
)
3045 : builtin_decl_implicit (BUILT_IN_STRCMP_EQ
));
3048 tree const_string_len
= build_int_cst (size_type_node
, final_length
);
3049 update_gimple_call (gsi
, fn
, 3, arg1
, arg2
, const_string_len
);
3057 /* Handle a POINTER_PLUS_EXPR statement.
3058 For p = "abcd" + 2; compute associated length, or if
3059 p = q + off is pointing to a '\0' character of a string, call
3060 zero_length_string on it. */
3063 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
3065 gimple
*stmt
= gsi_stmt (*gsi
);
3066 tree lhs
= gimple_assign_lhs (stmt
), off
;
3067 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
3075 tree off
= gimple_assign_rhs2 (stmt
);
3076 if (tree_fits_uhwi_p (off
)
3077 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
3078 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
3079 = ~(~idx
- (int) tree_to_uhwi (off
));
3083 si
= get_strinfo (idx
);
3084 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
3087 off
= gimple_assign_rhs2 (stmt
);
3089 if (si
->full_string_p
&& operand_equal_p (si
->nonzero_chars
, off
, 0))
3090 zsi
= zero_length_string (lhs
, si
);
3091 else if (TREE_CODE (off
) == SSA_NAME
)
3093 gimple
*def_stmt
= SSA_NAME_DEF_STMT (off
);
3094 if (gimple_assign_single_p (def_stmt
)
3095 && si
->full_string_p
3096 && operand_equal_p (si
->nonzero_chars
,
3097 gimple_assign_rhs1 (def_stmt
), 0))
3098 zsi
= zero_length_string (lhs
, si
);
3101 && si
->endptr
!= NULL_TREE
3102 && si
->endptr
!= lhs
3103 && TREE_CODE (si
->endptr
) == SSA_NAME
)
3105 enum tree_code rhs_code
3106 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
3107 ? SSA_NAME
: NOP_EXPR
;
3108 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
);
3109 gcc_assert (gsi_stmt (*gsi
) == stmt
);
3114 /* If RHS, either directly or indirectly, refers to a string of constant
3115 length, return it. Otherwise return a negative value. */
3117 static HOST_WIDE_INT
3118 get_string_cst_length (tree rhs
)
3120 if (TREE_CODE (rhs
) == MEM_REF
3121 && integer_zerop (TREE_OPERAND (rhs
, 1)))
3123 rhs
= TREE_OPERAND (rhs
, 0);
3124 if (TREE_CODE (rhs
) == ADDR_EXPR
)
3126 tree rhs_addr
= rhs
;
3128 rhs
= TREE_OPERAND (rhs
, 0);
3129 if (TREE_CODE (rhs
) != STRING_CST
)
3131 int idx
= get_stridx (rhs_addr
);
3134 strinfo
*si
= get_strinfo (idx
);
3136 && si
->full_string_p
3137 && tree_fits_shwi_p (si
->nonzero_chars
))
3138 return tree_to_shwi (si
->nonzero_chars
);
3144 if (TREE_CODE (rhs
) == VAR_DECL
3145 && TREE_READONLY (rhs
))
3146 rhs
= DECL_INITIAL (rhs
);
3148 if (rhs
&& TREE_CODE (rhs
) == STRING_CST
)
3149 return strlen (TREE_STRING_POINTER (rhs
));
3154 /* Handle a single character store. */
3157 handle_char_store (gimple_stmt_iterator
*gsi
)
3161 gimple
*stmt
= gsi_stmt (*gsi
);
3162 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
3163 tree rhs
= gimple_assign_rhs1 (stmt
);
3164 unsigned HOST_WIDE_INT offset
= 0;
3166 if (TREE_CODE (lhs
) == MEM_REF
3167 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
3169 tree mem_offset
= TREE_OPERAND (lhs
, 1);
3170 if (tree_fits_uhwi_p (mem_offset
))
3172 /* Get the strinfo for the base, and use it if it starts with at
3173 least OFFSET nonzero characters. This is trivially true if
3175 offset
= tree_to_uhwi (mem_offset
);
3176 idx
= get_stridx (TREE_OPERAND (lhs
, 0));
3178 si
= get_strinfo (idx
);
3180 ssaname
= TREE_OPERAND (lhs
, 0);
3181 else if (si
== NULL
|| compare_nonzero_chars (si
, offset
) < 0)
3187 idx
= get_addr_stridx (lhs
, NULL_TREE
, &offset
);
3189 si
= get_strinfo (idx
);
3192 bool storing_zero_p
= initializer_zerop (rhs
);
3193 bool storing_nonzero_p
= !storing_zero_p
&& tree_expr_nonzero_p (rhs
);
3194 /* Set to the length of the string being assigned if known. */
3195 HOST_WIDE_INT rhslen
;
3199 int cmp
= compare_nonzero_chars (si
, offset
);
3200 gcc_assert (offset
== 0 || cmp
>= 0);
3201 if (storing_zero_p
&& cmp
== 0 && si
->full_string_p
)
3203 /* When overwriting a '\0' with a '\0', the store can be removed
3204 if we know it has been stored in the current function. */
3205 if (!stmt_could_throw_p (stmt
) && si
->writable
)
3207 unlink_stmt_vdef (stmt
);
3208 release_defs (stmt
);
3209 gsi_remove (gsi
, true);
3214 si
->writable
= true;
3219 /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0',
3220 and if we aren't storing '\0', we know that the length of the
3221 string and any other zero terminated string in memory remains
3222 the same. In that case we move to the next gimple statement and
3223 return to signal the caller that it shouldn't invalidate anything.
3225 This is benefical for cases like:
3230 strcpy (p, "foobar");
3231 size_t len = strlen (p); // This can be optimized into 6
3232 size_t len2 = strlen (q); // This has to be computed
3234 size_t len3 = strlen (p); // This can be optimized into 6
3235 size_t len4 = strlen (q); // This can be optimized into len2
3236 bar (len, len2, len3, len4);
3239 else if (storing_nonzero_p
&& cmp
> 0)
3244 else if (storing_zero_p
|| storing_nonzero_p
|| (offset
!= 0 && cmp
> 0))
3246 /* When storing_nonzero_p, we know that the string now starts
3247 with OFFSET + 1 nonzero characters, but don't know whether
3248 there's a following nul terminator.
3250 When storing_zero_p, we know that the string is now OFFSET
3253 Otherwise, we're storing an unknown value at offset OFFSET,
3254 so need to clip the nonzero_chars to OFFSET. */
3255 location_t loc
= gimple_location (stmt
);
3256 tree oldlen
= si
->nonzero_chars
;
3257 if (cmp
== 0 && si
->full_string_p
)
3258 /* We're overwriting the nul terminator with a nonzero or
3259 unknown character. If the previous stmt was a memcpy,
3260 its length may be decreased. */
3261 adjust_last_stmt (si
, stmt
, false);
3262 si
= unshare_strinfo (si
);
3263 if (storing_nonzero_p
)
3264 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
+ 1);
3266 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
);
3267 si
->full_string_p
= storing_zero_p
;
3270 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
3271 si
->endptr
= ssaname
;
3276 si
->writable
= true;
3277 si
->dont_invalidate
= true;
3280 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
3281 si
->nonzero_chars
, oldlen
);
3282 adjust_related_strinfos (loc
, si
, adj
);
3288 else if (idx
== 0 && (storing_zero_p
|| storing_nonzero_p
))
3291 idx
= new_stridx (ssaname
);
3293 idx
= new_addr_stridx (lhs
);
3296 tree ptr
= (ssaname
? ssaname
: build_fold_addr_expr (lhs
));
3297 tree len
= storing_nonzero_p
? size_one_node
: size_zero_node
;
3298 si
= new_strinfo (ptr
, idx
, len
, storing_zero_p
);
3299 set_strinfo (idx
, si
);
3302 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
3303 si
->endptr
= ssaname
;
3304 si
->dont_invalidate
= true;
3305 si
->writable
= true;
3309 && (rhslen
= get_string_cst_length (gimple_assign_rhs1 (stmt
))) >= 0
3310 && ssaname
== NULL_TREE
3311 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
3313 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
3314 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> (unsigned HOST_WIDE_INT
) rhslen
)
3316 int idx
= new_addr_stridx (lhs
);
3319 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
3320 build_int_cst (size_type_node
, rhslen
), true);
3321 set_strinfo (idx
, si
);
3322 si
->dont_invalidate
= true;
3327 if (si
!= NULL
&& offset
== 0 && storing_zero_p
)
3329 /* Allow adjust_last_stmt to remove it if the stored '\0'
3330 is immediately overwritten. */
3331 laststmt
.stmt
= stmt
;
3332 laststmt
.len
= build_int_cst (size_type_node
, 1);
3333 laststmt
.stridx
= si
->idx
;
3338 /* Try to fold strstr (s, t) eq/ne s to strncmp (s, t, strlen (t)) eq/ne 0. */
3341 fold_strstr_to_strncmp (tree rhs1
, tree rhs2
, gimple
*stmt
)
3343 if (TREE_CODE (rhs1
) != SSA_NAME
3344 || TREE_CODE (rhs2
) != SSA_NAME
)
3347 gimple
*call_stmt
= NULL
;
3348 for (int pass
= 0; pass
< 2; pass
++)
3350 gimple
*g
= SSA_NAME_DEF_STMT (rhs1
);
3351 if (gimple_call_builtin_p (g
, BUILT_IN_STRSTR
)
3352 && has_single_use (rhs1
)
3353 && gimple_call_arg (g
, 0) == rhs2
)
3358 std::swap (rhs1
, rhs2
);
3363 tree arg0
= gimple_call_arg (call_stmt
, 0);
3367 tree arg1
= gimple_call_arg (call_stmt
, 1);
3368 tree arg1_len
= NULL_TREE
;
3369 int idx
= get_stridx (arg1
);
3374 arg1_len
= build_int_cst (size_type_node
, ~idx
);
3377 strinfo
*si
= get_strinfo (idx
);
3379 arg1_len
= get_string_length (si
);
3383 if (arg1_len
!= NULL_TREE
)
3385 gimple_stmt_iterator gsi
= gsi_for_stmt (call_stmt
);
3386 tree strncmp_decl
= builtin_decl_explicit (BUILT_IN_STRNCMP
);
3388 if (!is_gimple_val (arg1_len
))
3390 tree arg1_len_tmp
= make_ssa_name (TREE_TYPE (arg1_len
));
3391 gassign
*arg1_stmt
= gimple_build_assign (arg1_len_tmp
,
3393 gsi_insert_before (&gsi
, arg1_stmt
, GSI_SAME_STMT
);
3394 arg1_len
= arg1_len_tmp
;
3397 gcall
*strncmp_call
= gimple_build_call (strncmp_decl
, 3,
3398 arg0
, arg1
, arg1_len
);
3399 tree strncmp_lhs
= make_ssa_name (integer_type_node
);
3400 gimple_set_vuse (strncmp_call
, gimple_vuse (call_stmt
));
3401 gimple_call_set_lhs (strncmp_call
, strncmp_lhs
);
3402 gsi_remove (&gsi
, true);
3403 gsi_insert_before (&gsi
, strncmp_call
, GSI_SAME_STMT
);
3404 tree zero
= build_zero_cst (TREE_TYPE (strncmp_lhs
));
3406 if (is_gimple_assign (stmt
))
3408 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
3410 tree cond
= gimple_assign_rhs1 (stmt
);
3411 TREE_OPERAND (cond
, 0) = strncmp_lhs
;
3412 TREE_OPERAND (cond
, 1) = zero
;
3416 gimple_assign_set_rhs1 (stmt
, strncmp_lhs
);
3417 gimple_assign_set_rhs2 (stmt
, zero
);
3422 gcond
*cond
= as_a
<gcond
*> (stmt
);
3423 gimple_cond_set_lhs (cond
, strncmp_lhs
);
3424 gimple_cond_set_rhs (cond
, zero
);
3432 /* Attempt to check for validity of the performed access a single statement
3433 at *GSI using string length knowledge, and to optimize it.
3434 If the given basic block needs clean-up of EH, CLEANUP_EH is set to
3438 strlen_check_and_optimize_stmt (gimple_stmt_iterator
*gsi
, bool *cleanup_eh
)
3440 gimple
*stmt
= gsi_stmt (*gsi
);
3442 if (is_gimple_call (stmt
))
3444 tree callee
= gimple_call_fndecl (stmt
);
3445 if (valid_builtin_call (stmt
))
3446 switch (DECL_FUNCTION_CODE (callee
))
3448 case BUILT_IN_STRLEN
:
3449 case BUILT_IN_STRNLEN
:
3450 handle_builtin_strlen (gsi
);
3452 case BUILT_IN_STRCHR
:
3453 handle_builtin_strchr (gsi
);
3455 case BUILT_IN_STRCPY
:
3456 case BUILT_IN_STRCPY_CHK
:
3457 case BUILT_IN_STPCPY
:
3458 case BUILT_IN_STPCPY_CHK
:
3459 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3462 case BUILT_IN_STRNCAT
:
3463 case BUILT_IN_STRNCAT_CHK
:
3464 handle_builtin_strncat (DECL_FUNCTION_CODE (callee
), gsi
);
3467 case BUILT_IN_STPNCPY
:
3468 case BUILT_IN_STPNCPY_CHK
:
3469 case BUILT_IN_STRNCPY
:
3470 case BUILT_IN_STRNCPY_CHK
:
3471 handle_builtin_stxncpy (DECL_FUNCTION_CODE (callee
), gsi
);
3474 case BUILT_IN_MEMCPY
:
3475 case BUILT_IN_MEMCPY_CHK
:
3476 case BUILT_IN_MEMPCPY
:
3477 case BUILT_IN_MEMPCPY_CHK
:
3478 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3480 case BUILT_IN_STRCAT
:
3481 case BUILT_IN_STRCAT_CHK
:
3482 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
3484 case BUILT_IN_MALLOC
:
3485 case BUILT_IN_CALLOC
:
3486 handle_builtin_malloc (DECL_FUNCTION_CODE (callee
), gsi
);
3488 case BUILT_IN_MEMSET
:
3489 if (handle_builtin_memset (gsi
))
3492 case BUILT_IN_MEMCMP
:
3493 if (handle_builtin_memcmp (gsi
))
3496 case BUILT_IN_STRCMP
:
3497 case BUILT_IN_STRNCMP
:
3498 if (handle_builtin_string_cmp (gsi
))
3505 else if (is_gimple_assign (stmt
) && !gimple_clobber_p (stmt
))
3507 tree lhs
= gimple_assign_lhs (stmt
);
3509 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
3511 if (gimple_assign_single_p (stmt
)
3512 || (gimple_assign_cast_p (stmt
)
3513 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
3515 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
3516 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
3518 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
3519 handle_pointer_plus (gsi
);
3521 else if (TREE_CODE (lhs
) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
3523 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3524 if (code
== COND_EXPR
)
3526 tree cond
= gimple_assign_rhs1 (stmt
);
3527 enum tree_code cond_code
= TREE_CODE (cond
);
3529 if (cond_code
== EQ_EXPR
|| cond_code
== NE_EXPR
)
3530 fold_strstr_to_strncmp (TREE_OPERAND (cond
, 0),
3531 TREE_OPERAND (cond
, 1), stmt
);
3533 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3534 fold_strstr_to_strncmp (gimple_assign_rhs1 (stmt
),
3535 gimple_assign_rhs2 (stmt
), stmt
);
3536 else if (gimple_assign_load_p (stmt
)
3537 && TREE_CODE (TREE_TYPE (lhs
)) == INTEGER_TYPE
3538 && TYPE_MODE (TREE_TYPE (lhs
)) == TYPE_MODE (char_type_node
)
3539 && (TYPE_PRECISION (TREE_TYPE (lhs
))
3540 == TYPE_PRECISION (char_type_node
))
3541 && !gimple_has_volatile_ops (stmt
))
3543 tree off
= integer_zero_node
;
3544 unsigned HOST_WIDE_INT coff
= 0;
3546 tree rhs1
= gimple_assign_rhs1 (stmt
);
3547 if (code
== MEM_REF
)
3549 idx
= get_stridx (TREE_OPERAND (rhs1
, 0));
3552 strinfo
*si
= get_strinfo (idx
);
3554 && si
->nonzero_chars
3555 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
3556 && (wi::to_widest (si
->nonzero_chars
)
3557 >= wi::to_widest (off
)))
3558 off
= TREE_OPERAND (rhs1
, 1);
3560 /* This case is not useful. See if get_addr_stridx
3561 returns something usable. */
3566 idx
= get_addr_stridx (rhs1
, NULL_TREE
, &coff
);
3569 strinfo
*si
= get_strinfo (idx
);
3571 && si
->nonzero_chars
3572 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
3574 widest_int w1
= wi::to_widest (si
->nonzero_chars
);
3575 widest_int w2
= wi::to_widest (off
) + coff
;
3577 && si
->full_string_p
)
3579 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3581 fprintf (dump_file
, "Optimizing: ");
3582 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3585 /* Reading the final '\0' character. */
3586 tree zero
= build_int_cst (TREE_TYPE (lhs
), 0);
3587 gimple_set_vuse (stmt
, NULL_TREE
);
3588 gimple_assign_set_rhs_from_tree (gsi
, zero
);
3590 |= maybe_clean_or_replace_eh_stmt (stmt
,
3592 stmt
= gsi_stmt (*gsi
);
3595 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3597 fprintf (dump_file
, "into: ");
3598 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3603 /* Reading a character before the final '\0'
3604 character. Just set the value range to ~[0, 0]
3605 if we don't have anything better. */
3607 tree type
= TREE_TYPE (lhs
);
3608 enum value_range_type vr
3609 = get_range_info (lhs
, &min
, &max
);
3610 if (vr
== VR_VARYING
3612 && min
== wi::min_value (TYPE_PRECISION (type
),
3614 && max
== wi::max_value (TYPE_PRECISION (type
),
3616 set_range_info (lhs
, VR_ANTI_RANGE
,
3617 wi::zero (TYPE_PRECISION (type
)),
3618 wi::zero (TYPE_PRECISION (type
)));
3624 if (strlen_to_stridx
)
3626 tree rhs1
= gimple_assign_rhs1 (stmt
);
3627 if (stridx_strlenloc
*ps
= strlen_to_stridx
->get (rhs1
))
3628 strlen_to_stridx
->put (lhs
, stridx_strlenloc (*ps
));
3631 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
3633 tree type
= TREE_TYPE (lhs
);
3634 if (TREE_CODE (type
) == ARRAY_TYPE
)
3635 type
= TREE_TYPE (type
);
3636 if (TREE_CODE (type
) == INTEGER_TYPE
3637 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
3638 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
3640 if (! handle_char_store (gsi
))
3645 else if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
3647 enum tree_code code
= gimple_cond_code (cond
);
3648 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3649 fold_strstr_to_strncmp (gimple_cond_lhs (stmt
),
3650 gimple_cond_rhs (stmt
), stmt
);
3653 if (gimple_vdef (stmt
))
3654 maybe_invalidate (stmt
);
3658 /* Recursively call maybe_invalidate on stmts that might be executed
3659 in between dombb and current bb and that contain a vdef. Stop when
3660 *count stmts are inspected, or if the whole strinfo vector has
3661 been invalidated. */
3664 do_invalidate (basic_block dombb
, gimple
*phi
, bitmap visited
, int *count
)
3666 unsigned int i
, n
= gimple_phi_num_args (phi
);
3668 for (i
= 0; i
< n
; i
++)
3670 tree vuse
= gimple_phi_arg_def (phi
, i
);
3671 gimple
*stmt
= SSA_NAME_DEF_STMT (vuse
);
3672 basic_block bb
= gimple_bb (stmt
);
3675 || !bitmap_set_bit (visited
, bb
->index
)
3676 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3680 if (gimple_code (stmt
) == GIMPLE_PHI
)
3682 do_invalidate (dombb
, stmt
, visited
, count
);
3689 if (!maybe_invalidate (stmt
))
3694 vuse
= gimple_vuse (stmt
);
3695 stmt
= SSA_NAME_DEF_STMT (vuse
);
3696 if (gimple_bb (stmt
) != bb
)
3698 bb
= gimple_bb (stmt
);
3701 || !bitmap_set_bit (visited
, bb
->index
)
3702 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3709 class strlen_dom_walker
: public dom_walker
3712 strlen_dom_walker (cdi_direction direction
)
3713 : dom_walker (direction
), m_cleanup_cfg (false)
3716 virtual edge
before_dom_children (basic_block
);
3717 virtual void after_dom_children (basic_block
);
3719 /* Flag that will trigger TODO_cleanup_cfg to be returned in strlen
3720 execute function. */
3724 /* Callback for walk_dominator_tree. Attempt to optimize various
3725 string ops by remembering string lengths pointed by pointer SSA_NAMEs. */
3728 strlen_dom_walker::before_dom_children (basic_block bb
)
3730 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
3733 stridx_to_strinfo
= NULL
;
3736 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) dombb
->aux
);
3737 if (stridx_to_strinfo
)
3739 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3742 gphi
*phi
= gsi
.phi ();
3743 if (virtual_operand_p (gimple_phi_result (phi
)))
3745 bitmap visited
= BITMAP_ALLOC (NULL
);
3746 int count_vdef
= 100;
3747 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
3748 BITMAP_FREE (visited
);
3749 if (count_vdef
== 0)
3751 /* If there were too many vdefs in between immediate
3752 dominator and current bb, invalidate everything.
3753 If stridx_to_strinfo has been unshared, we need
3754 to free it, otherwise just set it to NULL. */
3755 if (!strinfo_shared ())
3761 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
3765 (*stridx_to_strinfo
)[i
] = NULL
;
3769 stridx_to_strinfo
= NULL
;
3777 /* If all PHI arguments have the same string index, the PHI result
3779 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3782 gphi
*phi
= gsi
.phi ();
3783 tree result
= gimple_phi_result (phi
);
3784 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
3786 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
3789 unsigned int i
, n
= gimple_phi_num_args (phi
);
3790 for (i
= 1; i
< n
; i
++)
3791 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
3794 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
3799 bool cleanup_eh
= false;
3801 /* Attempt to optimize individual statements. */
3802 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
3803 if (strlen_check_and_optimize_stmt (&gsi
, &cleanup_eh
))
3806 if (cleanup_eh
&& gimple_purge_dead_eh_edges (bb
))
3807 m_cleanup_cfg
= true;
3809 bb
->aux
= stridx_to_strinfo
;
3810 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
3811 (*stridx_to_strinfo
)[0] = (strinfo
*) bb
;
3815 /* Callback for walk_dominator_tree. Free strinfo vector if it is
3816 owned by the current bb, clear bb->aux. */
3819 strlen_dom_walker::after_dom_children (basic_block bb
)
3823 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) bb
->aux
);
3824 if (vec_safe_length (stridx_to_strinfo
)
3825 && (*stridx_to_strinfo
)[0] == (strinfo
*) bb
)
3830 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
3832 vec_free (stridx_to_strinfo
);
3838 /* Main entry point. */
3842 const pass_data pass_data_strlen
=
3844 GIMPLE_PASS
, /* type */
3845 "strlen", /* name */
3846 OPTGROUP_NONE
, /* optinfo_flags */
3847 TV_TREE_STRLEN
, /* tv_id */
3848 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3849 0, /* properties_provided */
3850 0, /* properties_destroyed */
3851 0, /* todo_flags_start */
3852 0, /* todo_flags_finish */
3855 class pass_strlen
: public gimple_opt_pass
3858 pass_strlen (gcc::context
*ctxt
)
3859 : gimple_opt_pass (pass_data_strlen
, ctxt
)
3862 /* opt_pass methods: */
3863 virtual bool gate (function
*) { return flag_optimize_strlen
!= 0; }
3864 virtual unsigned int execute (function
*);
3866 }; // class pass_strlen
3869 pass_strlen::execute (function
*fun
)
3871 gcc_assert (!strlen_to_stridx
);
3872 if (warn_stringop_overflow
|| warn_stringop_truncation
)
3873 strlen_to_stridx
= new hash_map
<tree
, stridx_strlenloc
> ();
3875 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
3878 calculate_dominance_info (CDI_DOMINATORS
);
3880 /* String length optimization is implemented as a walk of the dominator
3881 tree and a forward walk of statements within each block. */
3882 strlen_dom_walker
walker (CDI_DOMINATORS
);
3883 walker
.walk (fun
->cfg
->x_entry_block_ptr
);
3885 ssa_ver_to_stridx
.release ();
3886 strinfo_pool
.release ();
3887 if (decl_to_stridxlist_htab
)
3889 obstack_free (&stridx_obstack
, NULL
);
3890 delete decl_to_stridxlist_htab
;
3891 decl_to_stridxlist_htab
= NULL
;
3893 laststmt
.stmt
= NULL
;
3894 laststmt
.len
= NULL_TREE
;
3895 laststmt
.stridx
= 0;
3897 if (strlen_to_stridx
)
3899 strlen_to_stridx
->empty ();
3900 delete strlen_to_stridx
;
3901 strlen_to_stridx
= NULL
;
3904 return walker
.m_cleanup_cfg
? TODO_cleanup_cfg
: 0;
3910 make_pass_strlen (gcc::context
*ctxt
)
3912 return new pass_strlen (ctxt
);