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"
50 #include "tree-hash-traits.h"
51 #include "tree-object-size.h"
54 #include "diagnostic-core.h"
55 #include "diagnostic.h"
60 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
61 is an index into strinfo vector, negative value stands for
62 string length of a string literal (~strlen). */
63 static vec
<int> ssa_ver_to_stridx
;
65 /* Number of currently active string indexes plus one. */
66 static int max_stridx
;
68 /* String information record. */
71 /* Number of leading characters that are known to be nonzero. This is
72 also the length of the string if FULL_STRING_P.
74 The values in a list of related string pointers must be consistent;
75 that is, if strinfo B comes X bytes after strinfo A, it must be
76 the case that A->nonzero_chars == X + B->nonzero_chars. */
78 /* Any of the corresponding pointers for querying alias oracle. */
80 /* This is used for two things:
82 - To record the statement that should be used for delayed length
83 computations. We maintain the invariant that all related strinfos
84 have delayed lengths or none do.
86 - To record the malloc or calloc call that produced this result. */
88 /* Pointer to '\0' if known, if NULL, it can be computed as
91 /* Reference count. Any changes to strinfo entry possibly shared
92 with dominating basic blocks need unshare_strinfo first, except
93 for dont_invalidate which affects only the immediately next
96 /* Copy of index. get_strinfo (si->idx) should return si; */
98 /* These 3 fields are for chaining related string pointers together.
100 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
101 strcpy (c, d); e = c + dl;
102 strinfo(a) -> strinfo(c) -> strinfo(e)
103 All have ->first field equal to strinfo(a)->idx and are doubly
104 chained through prev/next fields. The later strinfos are required
105 to point into the same string with zero or more bytes after
106 the previous pointer and all bytes in between the two pointers
107 must be non-zero. Functions like strcpy or memcpy are supposed
108 to adjust all previous strinfo lengths, but not following strinfo
109 lengths (those are uncertain, usually invalidated during
110 maybe_invalidate, except when the alias oracle knows better).
111 Functions like strcat on the other side adjust the whole
112 related strinfo chain.
113 They are updated lazily, so to use the chain the same first fields
114 and si->prev->next == si->idx needs to be verified. */
118 /* A flag whether the string is known to be written in the current
121 /* A flag for the next maybe_invalidate that this strinfo shouldn't
122 be invalidated. Always cleared by maybe_invalidate. */
123 bool dont_invalidate
;
124 /* True if the string is known to be nul-terminated after NONZERO_CHARS
125 characters. False is useful when detecting strings that are built
126 up via successive memcpys. */
130 /* Pool for allocating strinfo_struct entries. */
131 static object_allocator
<strinfo
> strinfo_pool ("strinfo pool");
133 /* Vector mapping positive string indexes to strinfo, for the
134 current basic block. The first pointer in the vector is special,
135 it is either NULL, meaning the vector isn't shared, or it is
136 a basic block pointer to the owner basic_block if shared.
137 If some other bb wants to modify the vector, the vector needs
138 to be unshared first, and only the owner bb is supposed to free it. */
139 static vec
<strinfo
*, va_heap
, vl_embed
> *stridx_to_strinfo
;
141 /* One OFFSET->IDX mapping. */
144 struct stridxlist
*next
;
145 HOST_WIDE_INT offset
;
149 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
150 struct decl_stridxlist_map
152 struct tree_map_base base
;
153 struct stridxlist list
;
156 /* Hash table for mapping decls to a chained list of offset -> idx
158 static hash_map
<tree_decl_hash
, stridxlist
> *decl_to_stridxlist_htab
;
160 /* Hash table mapping strlen calls to stridx instances describing
161 the calls' arguments. Non-null only when warn_stringop_truncation
163 typedef std::pair
<int, location_t
> stridx_strlenloc
;
164 static hash_map
<tree
, stridx_strlenloc
> *strlen_to_stridx
;
166 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
167 static struct obstack stridx_obstack
;
169 /* Last memcpy statement if it could be adjusted if the trailing
170 '\0' written is immediately overwritten, or
171 *x = '\0' store that could be removed if it is immediately overwritten. */
172 struct laststmt_struct
179 static int get_stridx_plus_constant (strinfo
*, unsigned HOST_WIDE_INT
, tree
);
180 static void handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*);
184 - 1 if SI is known to start with more than OFF nonzero characters.
186 - 0 if SI is known to start with OFF nonzero characters,
187 but is not known to start with more.
189 - -1 if SI might not start with OFF nonzero characters. */
192 compare_nonzero_chars (strinfo
*si
, unsigned HOST_WIDE_INT off
)
194 if (si
->nonzero_chars
195 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
196 return compare_tree_int (si
->nonzero_chars
, off
);
201 /* Return true if SI is known to be a zero-length string. */
204 zero_length_string_p (strinfo
*si
)
206 return si
->full_string_p
&& integer_zerop (si
->nonzero_chars
);
209 /* Return strinfo vector entry IDX. */
211 static inline strinfo
*
212 get_strinfo (int idx
)
214 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
216 return (*stridx_to_strinfo
)[idx
];
219 /* Get the next strinfo in the chain after SI, or null if none. */
221 static inline strinfo
*
222 get_next_strinfo (strinfo
*si
)
226 strinfo
*nextsi
= get_strinfo (si
->next
);
227 if (nextsi
== NULL
|| nextsi
->first
!= si
->first
|| nextsi
->prev
!= si
->idx
)
232 /* Helper function for get_stridx. Return the strinfo index of the address
233 of EXP, which is available in PTR if nonnull. If OFFSET_OUT, it is
234 OK to return the index for some X <= &EXP and store &EXP - X in
238 get_addr_stridx (tree exp
, tree ptr
, unsigned HOST_WIDE_INT
*offset_out
)
241 struct stridxlist
*list
, *last
= NULL
;
244 if (!decl_to_stridxlist_htab
)
248 base
= get_addr_base_and_unit_offset (exp
, &poff
);
249 if (base
== NULL
|| !DECL_P (base
) || !poff
.is_constant (&off
))
252 list
= decl_to_stridxlist_htab
->get (base
);
258 if (list
->offset
== off
)
264 if (list
->offset
> off
)
271 if ((offset_out
|| ptr
) && last
&& last
->idx
> 0)
273 unsigned HOST_WIDE_INT rel_off
274 = (unsigned HOST_WIDE_INT
) off
- last
->offset
;
275 strinfo
*si
= get_strinfo (last
->idx
);
276 if (si
&& compare_nonzero_chars (si
, rel_off
) >= 0)
280 *offset_out
= rel_off
;
284 return get_stridx_plus_constant (si
, rel_off
, ptr
);
290 /* Return string index for EXP. */
293 get_stridx (tree exp
)
297 if (TREE_CODE (exp
) == SSA_NAME
)
299 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)])
300 return ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)];
303 HOST_WIDE_INT off
= 0;
304 for (i
= 0; i
< 5; i
++)
306 gimple
*def_stmt
= SSA_NAME_DEF_STMT (e
);
307 if (!is_gimple_assign (def_stmt
)
308 || gimple_assign_rhs_code (def_stmt
) != POINTER_PLUS_EXPR
)
310 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
311 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
312 if (TREE_CODE (rhs1
) != SSA_NAME
313 || !tree_fits_shwi_p (rhs2
))
315 HOST_WIDE_INT this_off
= tree_to_shwi (rhs2
);
318 off
= (unsigned HOST_WIDE_INT
) off
+ this_off
;
321 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)])
324 = get_strinfo (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)]);
325 if (si
&& compare_nonzero_chars (si
, off
) >= 0)
326 return get_stridx_plus_constant (si
, off
, exp
);
333 if (TREE_CODE (exp
) == ADDR_EXPR
)
335 int idx
= get_addr_stridx (TREE_OPERAND (exp
, 0), exp
, NULL
);
340 s
= string_constant (exp
, &o
);
342 && (o
== NULL_TREE
|| tree_fits_shwi_p (o
))
343 && TREE_STRING_LENGTH (s
) > 0)
345 HOST_WIDE_INT offset
= o
? tree_to_shwi (o
) : 0;
346 const char *p
= TREE_STRING_POINTER (s
);
347 int max
= TREE_STRING_LENGTH (s
) - 1;
349 if (p
[max
] == '\0' && offset
>= 0 && offset
<= max
)
350 return ~(int) strlen (p
+ offset
);
355 /* Return true if strinfo vector is shared with the immediate dominator. */
358 strinfo_shared (void)
360 return vec_safe_length (stridx_to_strinfo
)
361 && (*stridx_to_strinfo
)[0] != NULL
;
364 /* Unshare strinfo vector that is shared with the immediate dominator. */
367 unshare_strinfo_vec (void)
372 gcc_assert (strinfo_shared ());
373 stridx_to_strinfo
= vec_safe_copy (stridx_to_strinfo
);
374 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
377 (*stridx_to_strinfo
)[0] = NULL
;
380 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
381 Return a pointer to the location where the string index can
382 be stored (if 0) or is stored, or NULL if this can't be tracked. */
385 addr_stridxptr (tree exp
)
390 tree base
= get_addr_base_and_unit_offset (exp
, &poff
);
391 if (base
== NULL_TREE
|| !DECL_P (base
) || !poff
.is_constant (&off
))
394 if (!decl_to_stridxlist_htab
)
396 decl_to_stridxlist_htab
397 = new hash_map
<tree_decl_hash
, stridxlist
> (64);
398 gcc_obstack_init (&stridx_obstack
);
402 stridxlist
*list
= &decl_to_stridxlist_htab
->get_or_insert (base
, &existed
);
406 stridxlist
*before
= NULL
;
407 for (i
= 0; i
< 32; i
++)
409 if (list
->offset
== off
)
411 if (list
->offset
> off
&& before
== NULL
)
413 if (list
->next
== NULL
)
422 before
= XOBNEW (&stridx_obstack
, struct stridxlist
);
429 list
->next
= XOBNEW (&stridx_obstack
, struct stridxlist
);
439 /* Create a new string index, or return 0 if reached limit. */
442 new_stridx (tree exp
)
445 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
447 if (TREE_CODE (exp
) == SSA_NAME
)
449 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
452 ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)] = idx
;
455 if (TREE_CODE (exp
) == ADDR_EXPR
)
457 int *pidx
= addr_stridxptr (TREE_OPERAND (exp
, 0));
460 gcc_assert (*pidx
== 0);
461 *pidx
= max_stridx
++;
468 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
471 new_addr_stridx (tree exp
)
474 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
476 pidx
= addr_stridxptr (exp
);
479 gcc_assert (*pidx
== 0);
480 *pidx
= max_stridx
++;
486 /* Create a new strinfo. */
489 new_strinfo (tree ptr
, int idx
, tree nonzero_chars
, bool full_string_p
)
491 strinfo
*si
= strinfo_pool
.allocate ();
492 si
->nonzero_chars
= nonzero_chars
;
495 si
->endptr
= NULL_TREE
;
501 si
->writable
= false;
502 si
->dont_invalidate
= false;
503 si
->full_string_p
= full_string_p
;
507 /* Decrease strinfo refcount and free it if not referenced anymore. */
510 free_strinfo (strinfo
*si
)
512 if (si
&& --si
->refcount
== 0)
513 strinfo_pool
.remove (si
);
516 /* Set strinfo in the vector entry IDX to SI. */
519 set_strinfo (int idx
, strinfo
*si
)
521 if (vec_safe_length (stridx_to_strinfo
) && (*stridx_to_strinfo
)[0])
522 unshare_strinfo_vec ();
523 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
524 vec_safe_grow_cleared (stridx_to_strinfo
, idx
+ 1);
525 (*stridx_to_strinfo
)[idx
] = si
;
528 /* Return the first strinfo in the related strinfo chain
529 if all strinfos in between belong to the chain, otherwise NULL. */
532 verify_related_strinfos (strinfo
*origsi
)
534 strinfo
*si
= origsi
, *psi
;
536 if (origsi
->first
== 0)
538 for (; si
->prev
; si
= psi
)
540 if (si
->first
!= origsi
->first
)
542 psi
= get_strinfo (si
->prev
);
545 if (psi
->next
!= si
->idx
)
548 if (si
->idx
!= si
->first
)
553 /* Set SI's endptr to ENDPTR and compute its length based on SI->ptr.
554 Use LOC for folding. */
557 set_endptr_and_length (location_t loc
, strinfo
*si
, tree endptr
)
561 tree start_as_size
= fold_convert_loc (loc
, size_type_node
, si
->ptr
);
562 tree end_as_size
= fold_convert_loc (loc
, size_type_node
, endptr
);
563 si
->nonzero_chars
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
564 end_as_size
, start_as_size
);
565 si
->full_string_p
= true;
568 /* Return string length, or NULL if it can't be computed. */
571 get_string_length (strinfo
*si
)
573 if (si
->nonzero_chars
)
574 return si
->full_string_p
? si
->nonzero_chars
: NULL
;
578 gimple
*stmt
= si
->stmt
, *lenstmt
;
579 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
580 tree callee
, lhs
, fn
, tem
;
582 gimple_stmt_iterator gsi
;
584 gcc_assert (is_gimple_call (stmt
));
585 callee
= gimple_call_fndecl (stmt
);
586 gcc_assert (callee
&& DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
);
587 lhs
= gimple_call_lhs (stmt
);
588 /* unshare_strinfo is intentionally not called here. The (delayed)
589 transformation of strcpy or strcat into stpcpy is done at the place
590 of the former strcpy/strcat call and so can affect all the strinfos
591 with the same stmt. If they were unshared before and transformation
592 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
593 just compute the right length. */
594 switch (DECL_FUNCTION_CODE (callee
))
596 case BUILT_IN_STRCAT
:
597 case BUILT_IN_STRCAT_CHK
:
598 case BUILT_IN_STRCAT_CHKP
:
599 case BUILT_IN_STRCAT_CHK_CHKP
:
600 gsi
= gsi_for_stmt (stmt
);
601 fn
= builtin_decl_implicit (BUILT_IN_STRLEN
);
602 gcc_assert (lhs
== NULL_TREE
);
603 tem
= unshare_expr (gimple_call_arg (stmt
, 0));
606 lenstmt
= gimple_build_call (chkp_maybe_create_clone (fn
)->decl
,
607 2, tem
, gimple_call_arg (stmt
, 1));
608 gimple_call_set_with_bounds (lenstmt
, true);
611 lenstmt
= gimple_build_call (fn
, 1, tem
);
612 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), lenstmt
);
613 gimple_call_set_lhs (lenstmt
, lhs
);
614 gimple_set_vuse (lenstmt
, gimple_vuse (stmt
));
615 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
616 tem
= gimple_call_arg (stmt
, 0);
617 if (!ptrofftype_p (TREE_TYPE (lhs
)))
619 lhs
= convert_to_ptrofftype (lhs
);
620 lhs
= force_gimple_operand_gsi (&gsi
, lhs
, true, NULL_TREE
,
621 true, GSI_SAME_STMT
);
623 lenstmt
= gimple_build_assign
624 (make_ssa_name (TREE_TYPE (gimple_call_arg (stmt
, 0))),
625 POINTER_PLUS_EXPR
,tem
, lhs
);
626 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
627 gimple_call_set_arg (stmt
, 0, gimple_assign_lhs (lenstmt
));
630 case BUILT_IN_STRCPY
:
631 case BUILT_IN_STRCPY_CHK
:
632 case BUILT_IN_STRCPY_CHKP
:
633 case BUILT_IN_STRCPY_CHK_CHKP
:
634 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY
));
635 if (gimple_call_num_args (stmt
) == (with_bounds
? 4 : 2))
636 fn
= builtin_decl_implicit (BUILT_IN_STPCPY
);
638 fn
= builtin_decl_explicit (BUILT_IN_STPCPY_CHK
);
640 fn
= chkp_maybe_create_clone (fn
)->decl
;
641 gcc_assert (lhs
== NULL_TREE
);
642 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
644 fprintf (dump_file
, "Optimizing: ");
645 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
647 gimple_call_set_fndecl (stmt
, fn
);
648 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), stmt
);
649 gimple_call_set_lhs (stmt
, lhs
);
651 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
653 fprintf (dump_file
, "into: ");
654 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
657 case BUILT_IN_STPCPY
:
658 case BUILT_IN_STPCPY_CHK
:
659 case BUILT_IN_STPCPY_CHKP
:
660 case BUILT_IN_STPCPY_CHK_CHKP
:
661 gcc_assert (lhs
!= NULL_TREE
);
662 loc
= gimple_location (stmt
);
663 set_endptr_and_length (loc
, si
, lhs
);
664 for (strinfo
*chainsi
= verify_related_strinfos (si
);
666 chainsi
= get_next_strinfo (chainsi
))
667 if (chainsi
->nonzero_chars
== NULL
)
668 set_endptr_and_length (loc
, chainsi
, lhs
);
670 case BUILT_IN_MALLOC
:
672 /* BUILT_IN_CALLOC always has si->nonzero_chars set. */
679 return si
->nonzero_chars
;
682 /* Invalidate string length information for strings whose length
683 might change due to stores in stmt. */
686 maybe_invalidate (gimple
*stmt
)
690 bool nonempty
= false;
692 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
695 if (!si
->dont_invalidate
)
698 /* Do not use si->nonzero_chars. */
699 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, NULL_TREE
);
700 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
702 set_strinfo (i
, NULL
);
707 si
->dont_invalidate
= false;
713 /* Unshare strinfo record SI, if it has refcount > 1 or
714 if stridx_to_strinfo vector is shared with some other
718 unshare_strinfo (strinfo
*si
)
722 if (si
->refcount
== 1 && !strinfo_shared ())
725 nsi
= new_strinfo (si
->ptr
, si
->idx
, si
->nonzero_chars
, si
->full_string_p
);
726 nsi
->stmt
= si
->stmt
;
727 nsi
->endptr
= si
->endptr
;
728 nsi
->first
= si
->first
;
729 nsi
->prev
= si
->prev
;
730 nsi
->next
= si
->next
;
731 nsi
->writable
= si
->writable
;
732 set_strinfo (si
->idx
, nsi
);
737 /* Attempt to create a new strinfo for BASESI + OFF, or find existing
738 strinfo if there is any. Return it's idx, or 0 if no strinfo has
742 get_stridx_plus_constant (strinfo
*basesi
, unsigned HOST_WIDE_INT off
,
745 if (TREE_CODE (ptr
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
748 if (compare_nonzero_chars (basesi
, off
) < 0
749 || !tree_fits_uhwi_p (basesi
->nonzero_chars
))
752 unsigned HOST_WIDE_INT nonzero_chars
753 = tree_to_uhwi (basesi
->nonzero_chars
) - off
;
754 strinfo
*si
= basesi
, *chainsi
;
755 if (si
->first
|| si
->prev
|| si
->next
)
756 si
= verify_related_strinfos (basesi
);
758 || si
->nonzero_chars
== NULL_TREE
759 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
762 if (TREE_CODE (ptr
) == SSA_NAME
763 && ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
764 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
766 gcc_checking_assert (compare_tree_int (si
->nonzero_chars
, off
) != -1);
767 for (chainsi
= si
; chainsi
->next
; chainsi
= si
)
769 si
= get_next_strinfo (chainsi
);
771 || si
->nonzero_chars
== NULL_TREE
772 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
774 int r
= compare_tree_int (si
->nonzero_chars
, nonzero_chars
);
779 if (TREE_CODE (ptr
) == SSA_NAME
)
780 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = si
->idx
;
783 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
784 if (pidx
!= NULL
&& *pidx
== 0)
793 int idx
= new_stridx (ptr
);
796 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, nonzero_chars
),
797 basesi
->full_string_p
);
798 set_strinfo (idx
, si
);
799 if (strinfo
*nextsi
= get_strinfo (chainsi
->next
))
801 nextsi
= unshare_strinfo (nextsi
);
802 si
->next
= nextsi
->idx
;
805 chainsi
= unshare_strinfo (chainsi
);
806 if (chainsi
->first
== 0)
807 chainsi
->first
= chainsi
->idx
;
809 if (chainsi
->endptr
== NULL_TREE
&& zero_length_string_p (si
))
810 chainsi
->endptr
= ptr
;
811 si
->endptr
= chainsi
->endptr
;
812 si
->prev
= chainsi
->idx
;
813 si
->first
= chainsi
->first
;
814 si
->writable
= chainsi
->writable
;
818 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
819 to a zero-length string and if possible chain it to a related strinfo
820 chain whose part is or might be CHAINSI. */
823 zero_length_string (tree ptr
, strinfo
*chainsi
)
827 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
828 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
829 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
830 && ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] == 0);
832 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
836 si
= verify_related_strinfos (chainsi
);
841 /* We shouldn't mix delayed and non-delayed lengths. */
842 gcc_assert (si
->full_string_p
);
843 if (si
->endptr
== NULL_TREE
)
845 si
= unshare_strinfo (si
);
849 si
= get_next_strinfo (si
);
852 if (zero_length_string_p (chainsi
))
856 chainsi
= unshare_strinfo (chainsi
);
859 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = chainsi
->idx
;
865 /* We shouldn't mix delayed and non-delayed lengths. */
866 gcc_assert (chainsi
->full_string_p
);
867 if (chainsi
->first
|| chainsi
->prev
|| chainsi
->next
)
869 chainsi
= unshare_strinfo (chainsi
);
876 idx
= new_stridx (ptr
);
879 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, 0), true);
880 set_strinfo (idx
, si
);
884 chainsi
= unshare_strinfo (chainsi
);
885 if (chainsi
->first
== 0)
886 chainsi
->first
= chainsi
->idx
;
888 if (chainsi
->endptr
== NULL_TREE
)
889 chainsi
->endptr
= ptr
;
890 si
->prev
= chainsi
->idx
;
891 si
->first
= chainsi
->first
;
892 si
->writable
= chainsi
->writable
;
897 /* For strinfo ORIGSI whose length has been just updated, adjust other
898 related strinfos so that they match the new ORIGSI. This involves:
900 - adding ADJ to the nonzero_chars fields
901 - copying full_string_p from the new ORIGSI. */
904 adjust_related_strinfos (location_t loc
, strinfo
*origsi
, tree adj
)
906 strinfo
*si
= verify_related_strinfos (origsi
);
919 si
= unshare_strinfo (si
);
920 /* We shouldn't see delayed lengths here; the caller must have
921 calculated the old length in order to calculate the
923 gcc_assert (si
->nonzero_chars
);
924 tem
= fold_convert_loc (loc
, TREE_TYPE (si
->nonzero_chars
), adj
);
925 si
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
926 TREE_TYPE (si
->nonzero_chars
),
927 si
->nonzero_chars
, tem
);
928 si
->full_string_p
= origsi
->full_string_p
;
930 si
->endptr
= NULL_TREE
;
931 si
->dont_invalidate
= true;
933 nsi
= get_next_strinfo (si
);
940 /* Find if there are other SSA_NAME pointers equal to PTR
941 for which we don't track their string lengths yet. If so, use
945 find_equal_ptrs (tree ptr
, int idx
)
947 if (TREE_CODE (ptr
) != SSA_NAME
)
951 gimple
*stmt
= SSA_NAME_DEF_STMT (ptr
);
952 if (!is_gimple_assign (stmt
))
954 ptr
= gimple_assign_rhs1 (stmt
);
955 switch (gimple_assign_rhs_code (stmt
))
960 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)))
962 if (TREE_CODE (ptr
) == SSA_NAME
)
964 if (TREE_CODE (ptr
) != ADDR_EXPR
)
969 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
970 if (pidx
!= NULL
&& *pidx
== 0)
978 /* We might find an endptr created in this pass. Grow the
979 vector in that case. */
980 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
981 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
983 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] != 0)
985 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = idx
;
989 /* Return true if STMT is a call to a builtin function with the right
990 arguments and attributes that should be considered for optimization
994 valid_builtin_call (gimple
*stmt
)
996 if (!gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
999 tree callee
= gimple_call_fndecl (stmt
);
1000 switch (DECL_FUNCTION_CODE (callee
))
1002 case BUILT_IN_MEMCMP
:
1003 case BUILT_IN_MEMCMP_EQ
:
1004 case BUILT_IN_STRCHR
:
1005 case BUILT_IN_STRCHR_CHKP
:
1006 case BUILT_IN_STRLEN
:
1007 case BUILT_IN_STRLEN_CHKP
:
1008 /* The above functions should be pure. Punt if they aren't. */
1009 if (gimple_vdef (stmt
) || gimple_vuse (stmt
) == NULL_TREE
)
1013 case BUILT_IN_CALLOC
:
1014 case BUILT_IN_MALLOC
:
1015 case BUILT_IN_MEMCPY
:
1016 case BUILT_IN_MEMCPY_CHK
:
1017 case BUILT_IN_MEMCPY_CHKP
:
1018 case BUILT_IN_MEMCPY_CHK_CHKP
:
1019 case BUILT_IN_MEMPCPY
:
1020 case BUILT_IN_MEMPCPY_CHK
:
1021 case BUILT_IN_MEMPCPY_CHKP
:
1022 case BUILT_IN_MEMPCPY_CHK_CHKP
:
1023 case BUILT_IN_MEMSET
:
1024 case BUILT_IN_STPCPY
:
1025 case BUILT_IN_STPCPY_CHK
:
1026 case BUILT_IN_STPCPY_CHKP
:
1027 case BUILT_IN_STPCPY_CHK_CHKP
:
1028 case BUILT_IN_STRCAT
:
1029 case BUILT_IN_STRCAT_CHK
:
1030 case BUILT_IN_STRCAT_CHKP
:
1031 case BUILT_IN_STRCAT_CHK_CHKP
:
1032 case BUILT_IN_STRCPY
:
1033 case BUILT_IN_STRCPY_CHK
:
1034 case BUILT_IN_STRCPY_CHKP
:
1035 case BUILT_IN_STRCPY_CHK_CHKP
:
1036 /* The above functions should be neither const nor pure. Punt if they
1038 if (gimple_vdef (stmt
) == NULL_TREE
|| gimple_vuse (stmt
) == NULL_TREE
)
1049 /* If the last .MEM setter statement before STMT is
1050 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
1051 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
1052 just memcpy (x, y, strlen (y)). SI must be the zero length
1056 adjust_last_stmt (strinfo
*si
, gimple
*stmt
, bool is_strcat
)
1058 tree vuse
, callee
, len
;
1059 struct laststmt_struct last
= laststmt
;
1060 strinfo
*lastsi
, *firstsi
;
1061 unsigned len_arg_no
= 2;
1063 laststmt
.stmt
= NULL
;
1064 laststmt
.len
= NULL_TREE
;
1065 laststmt
.stridx
= 0;
1067 if (last
.stmt
== NULL
)
1070 vuse
= gimple_vuse (stmt
);
1071 if (vuse
== NULL_TREE
1072 || SSA_NAME_DEF_STMT (vuse
) != last
.stmt
1073 || !has_single_use (vuse
))
1076 gcc_assert (last
.stridx
> 0);
1077 lastsi
= get_strinfo (last
.stridx
);
1083 if (lastsi
->first
== 0 || lastsi
->first
!= si
->first
)
1086 firstsi
= verify_related_strinfos (si
);
1087 if (firstsi
== NULL
)
1089 while (firstsi
!= lastsi
)
1091 firstsi
= get_next_strinfo (firstsi
);
1092 if (firstsi
== NULL
)
1097 if (!is_strcat
&& !zero_length_string_p (si
))
1100 if (is_gimple_assign (last
.stmt
))
1102 gimple_stmt_iterator gsi
;
1104 if (!integer_zerop (gimple_assign_rhs1 (last
.stmt
)))
1106 if (stmt_could_throw_p (last
.stmt
))
1108 gsi
= gsi_for_stmt (last
.stmt
);
1109 unlink_stmt_vdef (last
.stmt
);
1110 release_defs (last
.stmt
);
1111 gsi_remove (&gsi
, true);
1115 if (!valid_builtin_call (last
.stmt
))
1118 callee
= gimple_call_fndecl (last
.stmt
);
1119 switch (DECL_FUNCTION_CODE (callee
))
1121 case BUILT_IN_MEMCPY
:
1122 case BUILT_IN_MEMCPY_CHK
:
1124 case BUILT_IN_MEMCPY_CHKP
:
1125 case BUILT_IN_MEMCPY_CHK_CHKP
:
1132 len
= gimple_call_arg (last
.stmt
, len_arg_no
);
1133 if (tree_fits_uhwi_p (len
))
1135 if (!tree_fits_uhwi_p (last
.len
)
1136 || integer_zerop (len
)
1137 || tree_to_uhwi (len
) != tree_to_uhwi (last
.len
) + 1)
1139 /* Don't adjust the length if it is divisible by 4, it is more efficient
1140 to store the extra '\0' in that case. */
1141 if ((tree_to_uhwi (len
) & 3) == 0)
1144 else if (TREE_CODE (len
) == SSA_NAME
)
1146 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1147 if (!is_gimple_assign (def_stmt
)
1148 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1149 || gimple_assign_rhs1 (def_stmt
) != last
.len
1150 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1156 gimple_call_set_arg (last
.stmt
, len_arg_no
, last
.len
);
1157 update_stmt (last
.stmt
);
1160 /* For an LHS that is an SSA_NAME and for strlen() argument SRC, set
1161 LHS range info to [0, N] if SRC refers to a character array A[N]
1162 with unknown length bounded by N. */
1165 maybe_set_strlen_range (tree lhs
, tree src
)
1167 if (TREE_CODE (lhs
) != SSA_NAME
)
1170 if (TREE_CODE (src
) == SSA_NAME
)
1172 gimple
*def
= SSA_NAME_DEF_STMT (src
);
1173 if (is_gimple_assign (def
)
1174 && gimple_assign_rhs_code (def
) == ADDR_EXPR
)
1175 src
= gimple_assign_rhs1 (def
);
1178 if (TREE_CODE (src
) != ADDR_EXPR
)
1181 /* The last array member of a struct can be bigger than its size
1182 suggests if it's treated as a poor-man's flexible array member. */
1183 src
= TREE_OPERAND (src
, 0);
1184 if (TREE_CODE (TREE_TYPE (src
)) != ARRAY_TYPE
1185 || array_at_struct_end_p (src
))
1188 tree type
= TREE_TYPE (src
);
1189 if (tree dom
= TYPE_DOMAIN (type
))
1190 if (tree maxval
= TYPE_MAX_VALUE (dom
))
1192 wide_int max
= wi::to_wide (maxval
);
1193 wide_int min
= wi::zero (max
.get_precision ());
1194 set_range_info (lhs
, VR_RANGE
, min
, max
);
1198 /* Handle a strlen call. If strlen of the argument is known, replace
1199 the strlen call with the known value, otherwise remember that strlen
1200 of the argument is stored in the lhs SSA_NAME. */
1203 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
1207 gimple
*stmt
= gsi_stmt (*gsi
);
1208 tree lhs
= gimple_call_lhs (stmt
);
1210 if (lhs
== NULL_TREE
)
1213 src
= gimple_call_arg (stmt
, 0);
1214 idx
= get_stridx (src
);
1221 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
1225 si
= get_strinfo (idx
);
1227 rhs
= get_string_length (si
);
1229 if (rhs
!= NULL_TREE
)
1231 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1233 fprintf (dump_file
, "Optimizing: ");
1234 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1236 rhs
= unshare_expr (rhs
);
1237 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
1238 rhs
= fold_convert_loc (gimple_location (stmt
),
1239 TREE_TYPE (lhs
), rhs
);
1240 if (!update_call_from_tree (gsi
, rhs
))
1241 gimplify_and_update_call_from_tree (gsi
, rhs
);
1242 stmt
= gsi_stmt (*gsi
);
1244 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1246 fprintf (dump_file
, "into: ");
1247 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1250 && TREE_CODE (si
->nonzero_chars
) != SSA_NAME
1251 && TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
1252 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1254 si
= unshare_strinfo (si
);
1255 si
->nonzero_chars
= lhs
;
1256 gcc_assert (si
->full_string_p
);
1259 if (strlen_to_stridx
)
1261 location_t loc
= gimple_location (stmt
);
1262 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1267 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1270 idx
= new_stridx (src
);
1273 strinfo
*si
= get_strinfo (idx
);
1276 if (!si
->full_string_p
&& !si
->stmt
)
1278 /* Until now we only had a lower bound on the string length.
1279 Install LHS as the actual length. */
1280 si
= unshare_strinfo (si
);
1281 tree old
= si
->nonzero_chars
;
1282 si
->nonzero_chars
= lhs
;
1283 si
->full_string_p
= true;
1284 if (TREE_CODE (old
) == INTEGER_CST
)
1286 location_t loc
= gimple_location (stmt
);
1287 old
= fold_convert_loc (loc
, TREE_TYPE (lhs
), old
);
1288 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1289 TREE_TYPE (lhs
), lhs
, old
);
1290 adjust_related_strinfos (loc
, si
, adj
);
1304 strinfo
*si
= new_strinfo (src
, idx
, lhs
, true);
1305 set_strinfo (idx
, si
);
1306 find_equal_ptrs (src
, idx
);
1308 /* For SRC that is an array of N elements, set LHS's range
1310 maybe_set_strlen_range (lhs
, src
);
1312 if (strlen_to_stridx
)
1314 location_t loc
= gimple_location (stmt
);
1315 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1320 /* Handle a strchr call. If strlen of the first argument is known, replace
1321 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
1322 that lhs of the call is endptr and strlen of the argument is endptr - x. */
1325 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
1329 gimple
*stmt
= gsi_stmt (*gsi
);
1330 tree lhs
= gimple_call_lhs (stmt
);
1331 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1333 if (lhs
== NULL_TREE
)
1336 if (!integer_zerop (gimple_call_arg (stmt
, with_bounds
? 2 : 1)))
1339 src
= gimple_call_arg (stmt
, 0);
1340 idx
= get_stridx (src
);
1347 rhs
= build_int_cst (size_type_node
, ~idx
);
1351 si
= get_strinfo (idx
);
1353 rhs
= get_string_length (si
);
1355 if (rhs
!= NULL_TREE
)
1357 location_t loc
= gimple_location (stmt
);
1359 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1361 fprintf (dump_file
, "Optimizing: ");
1362 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1364 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
1366 rhs
= unshare_expr (si
->endptr
);
1367 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1369 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1373 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1374 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1375 TREE_TYPE (src
), src
, rhs
);
1376 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1378 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1380 if (!update_call_from_tree (gsi
, rhs
))
1381 gimplify_and_update_call_from_tree (gsi
, rhs
);
1382 stmt
= gsi_stmt (*gsi
);
1384 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1386 fprintf (dump_file
, "into: ");
1387 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1390 && si
->endptr
== NULL_TREE
1391 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1393 si
= unshare_strinfo (si
);
1396 zero_length_string (lhs
, si
);
1400 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1402 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1405 idx
= new_stridx (src
);
1406 else if (get_strinfo (idx
) != NULL
)
1408 zero_length_string (lhs
, NULL
);
1413 location_t loc
= gimple_location (stmt
);
1414 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1415 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1416 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1417 size_type_node
, lhsu
, srcu
);
1418 strinfo
*si
= new_strinfo (src
, idx
, length
, true);
1420 set_strinfo (idx
, si
);
1421 find_equal_ptrs (src
, idx
);
1422 zero_length_string (lhs
, si
);
1426 zero_length_string (lhs
, NULL
);
1429 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1430 If strlen of the second argument is known, strlen of the first argument
1431 is the same after this call. Furthermore, attempt to convert it to
1435 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1438 tree src
, dst
, srclen
, len
, lhs
, type
, fn
, oldlen
;
1440 gimple
*stmt
= gsi_stmt (*gsi
);
1441 strinfo
*si
, *dsi
, *olddsi
, *zsi
;
1443 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1445 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1446 dst
= gimple_call_arg (stmt
, 0);
1447 lhs
= gimple_call_lhs (stmt
);
1448 idx
= get_stridx (src
);
1451 si
= get_strinfo (idx
);
1453 didx
= get_stridx (dst
);
1457 olddsi
= get_strinfo (didx
);
1462 adjust_last_stmt (olddsi
, stmt
, false);
1466 srclen
= get_string_length (si
);
1468 srclen
= build_int_cst (size_type_node
, ~idx
);
1470 loc
= gimple_location (stmt
);
1471 if (srclen
== NULL_TREE
)
1474 case BUILT_IN_STRCPY
:
1475 case BUILT_IN_STRCPY_CHK
:
1476 case BUILT_IN_STRCPY_CHKP
:
1477 case BUILT_IN_STRCPY_CHK_CHKP
:
1478 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1481 case BUILT_IN_STPCPY
:
1482 case BUILT_IN_STPCPY_CHK
:
1483 case BUILT_IN_STPCPY_CHKP
:
1484 case BUILT_IN_STPCPY_CHK_CHKP
:
1485 if (lhs
== NULL_TREE
)
1489 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1490 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1491 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1501 didx
= new_stridx (dst
);
1507 oldlen
= olddsi
->nonzero_chars
;
1508 dsi
= unshare_strinfo (olddsi
);
1509 dsi
->nonzero_chars
= srclen
;
1510 dsi
->full_string_p
= (srclen
!= NULL_TREE
);
1511 /* Break the chain, so adjust_related_strinfo on later pointers in
1512 the chain won't adjust this one anymore. */
1515 dsi
->endptr
= NULL_TREE
;
1519 dsi
= new_strinfo (dst
, didx
, srclen
, srclen
!= NULL_TREE
);
1520 set_strinfo (didx
, dsi
);
1521 find_equal_ptrs (dst
, didx
);
1523 dsi
->writable
= true;
1524 dsi
->dont_invalidate
= true;
1526 if (dsi
->nonzero_chars
== NULL_TREE
)
1530 /* If string length of src is unknown, use delayed length
1531 computation. If string lenth of dst will be needed, it
1532 can be computed by transforming this strcpy call into
1533 stpcpy and subtracting dst from the return value. */
1535 /* Look for earlier strings whose length could be determined if
1536 this strcpy is turned into an stpcpy. */
1538 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1540 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1542 /* When setting a stmt for delayed length computation
1543 prevent all strinfos through dsi from being
1545 chainsi
= unshare_strinfo (chainsi
);
1546 chainsi
->stmt
= stmt
;
1547 chainsi
->nonzero_chars
= NULL_TREE
;
1548 chainsi
->full_string_p
= false;
1549 chainsi
->endptr
= NULL_TREE
;
1550 chainsi
->dont_invalidate
= true;
1555 /* Try to detect overlap before returning. This catches cases
1556 like strcpy (d, d + n) where n is non-constant whose range
1557 is such that (n <= strlen (d) holds).
1559 OLDDSI->NONZERO_chars may have been reset by this point with
1560 oldlen holding it original value. */
1561 if (olddsi
&& oldlen
)
1563 /* Add 1 for the terminating NUL. */
1564 tree type
= TREE_TYPE (oldlen
);
1565 oldlen
= fold_build2 (PLUS_EXPR
, type
, oldlen
,
1566 build_int_cst (type
, 1));
1567 check_bounds_or_overlap (as_a
<gcall
*>(stmt
), olddsi
->ptr
, src
,
1576 tree adj
= NULL_TREE
;
1577 if (oldlen
== NULL_TREE
)
1579 else if (integer_zerop (oldlen
))
1581 else if (TREE_CODE (oldlen
) == INTEGER_CST
1582 || TREE_CODE (srclen
) == INTEGER_CST
)
1583 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1584 TREE_TYPE (srclen
), srclen
,
1585 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1587 if (adj
!= NULL_TREE
)
1588 adjust_related_strinfos (loc
, dsi
, adj
);
1592 /* strcpy src may not overlap dst, so src doesn't need to be
1593 invalidated either. */
1595 si
->dont_invalidate
= true;
1601 case BUILT_IN_STRCPY
:
1602 case BUILT_IN_STRCPY_CHKP
:
1603 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1605 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1607 case BUILT_IN_STRCPY_CHK
:
1608 case BUILT_IN_STRCPY_CHK_CHKP
:
1609 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1611 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1613 case BUILT_IN_STPCPY
:
1614 case BUILT_IN_STPCPY_CHKP
:
1615 /* This would need adjustment of the lhs (subtract one),
1616 or detection that the trailing '\0' doesn't need to be
1617 written, if it will be immediately overwritten.
1618 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1622 zsi
= zero_length_string (lhs
, dsi
);
1625 case BUILT_IN_STPCPY_CHK
:
1626 case BUILT_IN_STPCPY_CHK_CHKP
:
1627 /* This would need adjustment of the lhs (subtract one),
1628 or detection that the trailing '\0' doesn't need to be
1629 written, if it will be immediately overwritten.
1630 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1634 zsi
= zero_length_string (lhs
, dsi
);
1641 zsi
->dont_invalidate
= true;
1645 tree args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1646 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1649 type
= size_type_node
;
1651 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1652 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1654 /* Set the no-warning bit on the transformed statement? */
1655 bool set_no_warning
= false;
1657 if (const strinfo
*chksi
= olddsi
? olddsi
: dsi
)
1659 && !check_bounds_or_overlap (as_a
<gcall
*>(stmt
), chksi
->ptr
, si
->ptr
,
1662 gimple_set_no_warning (stmt
, true);
1663 set_no_warning
= true;
1666 if (fn
== NULL_TREE
)
1669 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1671 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1673 fprintf (dump_file
, "Optimizing: ");
1674 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1678 fn
= chkp_maybe_create_clone (fn
)->decl
;
1679 if (gimple_call_num_args (stmt
) == 4)
1680 success
= update_gimple_call (gsi
, fn
, 5, dst
,
1681 gimple_call_arg (stmt
, 1),
1683 gimple_call_arg (stmt
, 3),
1686 success
= update_gimple_call (gsi
, fn
, 6, dst
,
1687 gimple_call_arg (stmt
, 1),
1689 gimple_call_arg (stmt
, 3),
1691 gimple_call_arg (stmt
, 4));
1694 if (gimple_call_num_args (stmt
) == 2)
1695 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1697 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1698 gimple_call_arg (stmt
, 2));
1701 stmt
= gsi_stmt (*gsi
);
1702 gimple_call_set_with_bounds (stmt
, with_bounds
);
1704 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1706 fprintf (dump_file
, "into: ");
1707 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1709 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1710 laststmt
.stmt
= stmt
;
1711 laststmt
.len
= srclen
;
1712 laststmt
.stridx
= dsi
->idx
;
1714 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1715 fprintf (dump_file
, "not possible.\n");
1718 gimple_set_no_warning (stmt
, true);
1721 /* Check the size argument to the built-in forms of stpncpy and strncpy
1722 for out-of-bounds offsets or overlapping access, and to see if the
1723 size argument is derived from a call to strlen() on the source argument,
1724 and if so, issue an appropriate warning. */
1727 handle_builtin_strncat (built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1729 /* Same as stxncpy(). */
1730 handle_builtin_stxncpy (bcode
, gsi
);
1733 /* Return true if LEN depends on a call to strlen(SRC) in an interesting
1734 way. LEN can either be an integer expression, or a pointer (to char).
1735 When it is the latter (such as in recursive calls to self) is is
1736 assumed to be the argument in some call to strlen() whose relationship
1737 to SRC is being ascertained. */
1740 is_strlen_related_p (tree src
, tree len
)
1742 if (TREE_CODE (TREE_TYPE (len
)) == POINTER_TYPE
1743 && operand_equal_p (src
, len
, 0))
1746 if (TREE_CODE (len
) != SSA_NAME
)
1749 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1753 if (is_gimple_call (def_stmt
))
1755 tree func
= gimple_call_fndecl (def_stmt
);
1756 if (!valid_builtin_call (def_stmt
)
1757 || DECL_FUNCTION_CODE (func
) != BUILT_IN_STRLEN
)
1760 tree arg
= gimple_call_arg (def_stmt
, 0);
1761 return is_strlen_related_p (src
, arg
);
1764 if (!is_gimple_assign (def_stmt
))
1767 tree_code code
= gimple_assign_rhs_code (def_stmt
);
1768 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1769 tree rhstype
= TREE_TYPE (rhs1
);
1771 if ((TREE_CODE (rhstype
) == POINTER_TYPE
&& code
== POINTER_PLUS_EXPR
)
1772 || (INTEGRAL_TYPE_P (rhstype
)
1773 && (code
== BIT_AND_EXPR
1774 || code
== NOP_EXPR
)))
1776 /* Pointer plus (an integer) and integer cast or truncation are
1777 considered among the (potentially) related expressions to strlen.
1779 return is_strlen_related_p (src
, rhs1
);
1785 /* Called by handle_builtin_stxncpy and by gimple_fold_builtin_strncpy
1787 Check to see if the specified bound is a) equal to the size of
1788 the destination DST and if so, b) if it's immediately followed by
1789 DST[CNT - 1] = '\0'. If a) holds and b) does not, warn. Otherwise,
1790 do nothing. Return true if diagnostic has been issued.
1792 The purpose is to diagnose calls to strncpy and stpncpy that do
1793 not nul-terminate the copy while allowing for the idiom where
1794 such a call is immediately followed by setting the last element
1797 strncpy (a, s, sizeof a);
1798 a[sizeof a - 1] = '\0';
1802 maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi
, tree src
, tree cnt
)
1804 gimple
*stmt
= gsi_stmt (gsi
);
1805 if (gimple_no_warning_p (stmt
))
1808 wide_int cntrange
[2];
1810 if (TREE_CODE (cnt
) == INTEGER_CST
)
1811 cntrange
[0] = cntrange
[1] = wi::to_wide (cnt
);
1812 else if (TREE_CODE (cnt
) == SSA_NAME
)
1814 enum value_range_type rng
= get_range_info (cnt
, cntrange
, cntrange
+ 1);
1815 if (rng
== VR_RANGE
)
1817 else if (rng
== VR_ANTI_RANGE
)
1819 wide_int maxobjsize
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
));
1821 if (wi::ltu_p (cntrange
[1], maxobjsize
))
1823 cntrange
[0] = cntrange
[1] + 1;
1824 cntrange
[1] = maxobjsize
;
1828 cntrange
[1] = cntrange
[0] - 1;
1829 cntrange
[0] = wi::zero (TYPE_PRECISION (TREE_TYPE (cnt
)));
1838 /* Negative value is the constant string length. If it's less than
1839 the lower bound there is no truncation. Avoid calling get_stridx()
1840 when ssa_ver_to_stridx is empty. That implies the caller isn't
1841 running under the control of this pass and ssa_ver_to_stridx hasn't
1842 been created yet. */
1843 int sidx
= ssa_ver_to_stridx
.length () ? get_stridx (src
) : 0;
1844 if (sidx
< 0 && wi::gtu_p (cntrange
[0], ~sidx
))
1847 tree dst
= gimple_call_arg (stmt
, 0);
1849 if (TREE_CODE (dstdecl
) == ADDR_EXPR
)
1850 dstdecl
= TREE_OPERAND (dstdecl
, 0);
1852 /* If the destination refers to a an array/pointer declared nonstring
1854 tree ref
= NULL_TREE
;
1855 if (get_attr_nonstring_decl (dstdecl
, &ref
))
1858 /* Look for dst[i] = '\0'; after the stxncpy() call and if found
1859 avoid the truncation warning. */
1860 gsi_next_nondebug (&gsi
);
1861 gimple
*next_stmt
= gsi_stmt (gsi
);
1864 /* When there is no statement in the same basic block check
1865 the immediate successor block. */
1866 if (basic_block bb
= gimple_bb (stmt
))
1868 if (single_succ_p (bb
))
1870 /* For simplicity, ignore blocks with multiple outgoing
1871 edges for now and only consider successor blocks along
1873 edge e
= EDGE_SUCC (bb
, 0);
1874 if (!(e
->flags
& EDGE_ABNORMAL
))
1876 gsi
= gsi_start_bb (e
->dest
);
1877 next_stmt
= gsi_stmt (gsi
);
1878 if (next_stmt
&& is_gimple_debug (next_stmt
))
1880 gsi_next_nondebug (&gsi
);
1881 next_stmt
= gsi_stmt (gsi
);
1888 if (next_stmt
&& is_gimple_assign (next_stmt
))
1890 tree lhs
= gimple_assign_lhs (next_stmt
);
1891 tree_code code
= TREE_CODE (lhs
);
1892 if (code
== ARRAY_REF
|| code
== MEM_REF
)
1893 lhs
= TREE_OPERAND (lhs
, 0);
1895 tree func
= gimple_call_fndecl (stmt
);
1896 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STPNCPY
)
1898 tree ret
= gimple_call_lhs (stmt
);
1899 if (ret
&& operand_equal_p (ret
, lhs
, 0))
1903 /* Determine the base address and offset of the reference,
1904 ignoring the innermost array index. */
1905 if (TREE_CODE (ref
) == ARRAY_REF
)
1906 ref
= TREE_OPERAND (ref
, 0);
1909 tree dstbase
= get_addr_base_and_unit_offset (ref
, &dstoff
);
1912 tree lhsbase
= get_addr_base_and_unit_offset (lhs
, &lhsoff
);
1915 && known_eq (dstoff
, lhsoff
)
1916 && operand_equal_p (dstbase
, lhsbase
, 0))
1920 int prec
= TYPE_PRECISION (TREE_TYPE (cnt
));
1921 wide_int lenrange
[2];
1922 if (strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
)
1924 lenrange
[0] = (sisrc
->nonzero_chars
1925 && TREE_CODE (sisrc
->nonzero_chars
) == INTEGER_CST
1926 ? wi::to_wide (sisrc
->nonzero_chars
)
1928 lenrange
[1] = lenrange
[0];
1931 lenrange
[0] = lenrange
[1] = wi::shwi (~sidx
, prec
);
1935 get_range_strlen (src
, range
);
1936 if (range
[0] != NULL_TREE
1937 && TREE_CODE (range
[0]) == INTEGER_CST
1938 && range
[1] != NULL_TREE
1939 && TREE_CODE (range
[1]) == INTEGER_CST
)
1941 lenrange
[0] = wi::to_wide (range
[0], prec
);
1942 lenrange
[1] = wi::to_wide (range
[1], prec
);
1946 lenrange
[0] = wi::shwi (0, prec
);
1947 lenrange
[1] = wi::shwi (-1, prec
);
1951 location_t callloc
= gimple_location (stmt
);
1952 tree func
= gimple_call_fndecl (stmt
);
1954 if (lenrange
[0] != 0 || !wi::neg_p (lenrange
[1]))
1956 /* If the longest source string is shorter than the lower bound
1957 of the specified count the copy is definitely nul-terminated. */
1958 if (wi::ltu_p (lenrange
[1], cntrange
[0]))
1961 if (wi::neg_p (lenrange
[1]))
1963 /* The length of one of the strings is unknown but at least
1964 one has non-zero length and that length is stored in
1965 LENRANGE[1]. Swap the bounds to force a "may be truncated"
1967 lenrange
[1] = lenrange
[0];
1968 lenrange
[0] = wi::shwi (0, prec
);
1971 gcall
*call
= as_a
<gcall
*> (stmt
);
1973 if (lenrange
[0] == cntrange
[1] && cntrange
[0] == cntrange
[1])
1974 return warning_n (callloc
, OPT_Wstringop_truncation
,
1975 cntrange
[0].to_uhwi (),
1976 "%G%qD output truncated before terminating "
1977 "nul copying %E byte from a string of the "
1979 "%G%qD output truncated before terminating nul "
1980 "copying %E bytes from a string of the same "
1983 else if (wi::geu_p (lenrange
[0], cntrange
[1]))
1985 /* The shortest string is longer than the upper bound of
1986 the count so the truncation is certain. */
1987 if (cntrange
[0] == cntrange
[1])
1988 return warning_n (callloc
, OPT_Wstringop_truncation
,
1989 cntrange
[0].to_uhwi (),
1990 "%G%qD output truncated copying %E byte "
1991 "from a string of length %wu",
1992 "%G%qD output truncated copying %E bytes "
1993 "from a string of length %wu",
1994 call
, func
, cnt
, lenrange
[0].to_uhwi ());
1996 return warning_at (callloc
, OPT_Wstringop_truncation
,
1997 "%G%qD output truncated copying between %wu "
1998 "and %wu bytes from a string of length %wu",
1999 call
, func
, cntrange
[0].to_uhwi (),
2000 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
2002 else if (wi::geu_p (lenrange
[1], cntrange
[1]))
2004 /* The longest string is longer than the upper bound of
2005 the count so the truncation is possible. */
2006 if (cntrange
[0] == cntrange
[1])
2007 return warning_n (callloc
, OPT_Wstringop_truncation
,
2008 cntrange
[0].to_uhwi (),
2009 "%G%qD output may be truncated copying %E "
2010 "byte from a string of length %wu",
2011 "%G%qD output may be truncated copying %E "
2012 "bytes from a string of length %wu",
2013 call
, func
, cnt
, lenrange
[1].to_uhwi ());
2015 return warning_at (callloc
, OPT_Wstringop_truncation
,
2016 "%G%qD output may be truncated copying between %wu "
2017 "and %wu bytes from a string of length %wu",
2018 call
, func
, cntrange
[0].to_uhwi (),
2019 cntrange
[1].to_uhwi (), lenrange
[1].to_uhwi ());
2022 if (cntrange
[0] != cntrange
[1]
2023 && wi::leu_p (cntrange
[0], lenrange
[0])
2024 && wi::leu_p (cntrange
[1], lenrange
[0] + 1))
2026 /* If the source (including the terminating nul) is longer than
2027 the lower bound of the specified count but shorter than the
2028 upper bound the copy may (but need not) be truncated. */
2029 return warning_at (callloc
, OPT_Wstringop_truncation
,
2030 "%G%qD output may be truncated copying between "
2031 "%wu and %wu bytes from a string of length %wu",
2032 call
, func
, cntrange
[0].to_uhwi (),
2033 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
2037 if (tree dstsize
= compute_objsize (dst
, 1))
2039 /* The source length is uknown. Try to determine the destination
2040 size and see if it matches the specified bound. If not, bail.
2041 Otherwise go on to see if it should be diagnosed for possible
2046 if (wi::to_wide (dstsize
) != cntrange
[1])
2049 if (cntrange
[0] == cntrange
[1])
2050 return warning_at (callloc
, OPT_Wstringop_truncation
,
2051 "%G%qD specified bound %E equals destination size",
2052 as_a
<gcall
*> (stmt
), func
, cnt
);
2058 /* Check the arguments to the built-in forms of stpncpy and strncpy for
2059 out-of-bounds offsets or overlapping access, and to see if the size
2060 is derived from calling strlen() on the source argument, and if so,
2061 issue the appropriate warning. */
2064 handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*gsi
)
2066 if (!strlen_to_stridx
)
2069 gimple
*stmt
= gsi_stmt (*gsi
);
2071 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
2073 tree dst
= gimple_call_arg (stmt
, with_bounds
? 1 : 0);
2074 tree src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
2075 tree len
= gimple_call_arg (stmt
, with_bounds
? 3 : 2);
2076 tree dstsize
= NULL_TREE
, srcsize
= NULL_TREE
;
2078 int didx
= get_stridx (dst
);
2079 if (strinfo
*sidst
= didx
> 0 ? get_strinfo (didx
) : NULL
)
2081 /* Compute the size of the destination string including the NUL. */
2082 if (sidst
->nonzero_chars
)
2084 tree type
= TREE_TYPE (sidst
->nonzero_chars
);
2085 dstsize
= fold_build2 (PLUS_EXPR
, type
, sidst
->nonzero_chars
,
2086 build_int_cst (type
, 1));
2091 int sidx
= get_stridx (src
);
2092 strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
;
2095 /* strncat() and strncpy() can modify the source string by writing
2096 over the terminating nul so SISRC->DONT_INVALIDATE must be left
2099 /* Compute the size of the source string including the NUL. */
2100 if (sisrc
->nonzero_chars
)
2102 tree type
= TREE_TYPE (sisrc
->nonzero_chars
);
2103 srcsize
= fold_build2 (PLUS_EXPR
, type
, sisrc
->nonzero_chars
,
2104 build_int_cst (type
, 1));
2110 srcsize
= NULL_TREE
;
2112 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, src
,
2115 gimple_set_no_warning (stmt
, true);
2119 /* If the length argument was computed from strlen(S) for some string
2120 S retrieve the strinfo index for the string (PSS->FIRST) alonng with
2121 the location of the strlen() call (PSS->SECOND). */
2122 stridx_strlenloc
*pss
= strlen_to_stridx
->get (len
);
2123 if (!pss
|| pss
->first
<= 0)
2125 if (maybe_diag_stxncpy_trunc (*gsi
, src
, len
))
2126 gimple_set_no_warning (stmt
, true);
2131 /* Retrieve the strinfo data for the string S that LEN was computed
2132 from as some function F of strlen (S) (i.e., LEN need not be equal
2134 strinfo
*silen
= get_strinfo (pss
->first
);
2136 location_t callloc
= gimple_location (stmt
);
2138 tree func
= gimple_call_fndecl (stmt
);
2140 bool warned
= false;
2142 /* When -Wstringop-truncation is set, try to determine truncation
2143 before diagnosing possible overflow. Truncation is implied by
2144 the LEN argument being equal to strlen(SRC), regardless of
2145 whether its value is known. Otherwise, issue the more generic
2146 -Wstringop-overflow which triggers for LEN arguments that in
2147 any meaningful way depend on strlen(SRC). */
2149 && is_strlen_related_p (src
, len
)
2150 && warning_at (callloc
, OPT_Wstringop_truncation
,
2151 "%G%qD output truncated before terminating nul "
2152 "copying as many bytes from a string as its length",
2153 as_a
<gcall
*>(stmt
), func
))
2155 else if (silen
&& is_strlen_related_p (src
, silen
->ptr
))
2156 warned
= warning_at (callloc
, OPT_Wstringop_overflow_
,
2157 "%G%qD specified bound depends on the length "
2158 "of the source argument",
2159 as_a
<gcall
*>(stmt
), func
);
2162 location_t strlenloc
= pss
->second
;
2163 if (strlenloc
!= UNKNOWN_LOCATION
&& strlenloc
!= callloc
)
2164 inform (strlenloc
, "length computed here");
2168 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
2169 If strlen of the second argument is known and length of the third argument
2170 is that plus one, strlen of the first argument is the same after this
2174 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2177 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
2178 gimple
*stmt
= gsi_stmt (*gsi
);
2179 strinfo
*si
, *dsi
, *olddsi
;
2180 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
2182 len
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
2183 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
2184 dst
= gimple_call_arg (stmt
, 0);
2185 idx
= get_stridx (src
);
2189 didx
= get_stridx (dst
);
2192 olddsi
= get_strinfo (didx
);
2197 && tree_fits_uhwi_p (len
)
2198 && !integer_zerop (len
))
2199 adjust_last_stmt (olddsi
, stmt
, false);
2206 /* Handle memcpy (x, y, l) where l's relationship with strlen (y)
2208 si
= get_strinfo (idx
);
2209 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
2211 if (TREE_CODE (len
) == INTEGER_CST
2212 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
2214 if (tree_int_cst_le (len
, si
->nonzero_chars
))
2216 /* Copying LEN nonzero characters, where LEN is constant. */
2218 full_string_p
= false;
2222 /* Copying the whole of the analyzed part of SI. */
2223 newlen
= si
->nonzero_chars
;
2224 full_string_p
= si
->full_string_p
;
2229 if (!si
->full_string_p
)
2231 if (TREE_CODE (len
) != SSA_NAME
)
2233 def_stmt
= SSA_NAME_DEF_STMT (len
);
2234 if (!is_gimple_assign (def_stmt
)
2235 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
2236 || gimple_assign_rhs1 (def_stmt
) != si
->nonzero_chars
2237 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
2239 /* Copying variable-length string SI (and no more). */
2240 newlen
= si
->nonzero_chars
;
2241 full_string_p
= true;
2247 /* Handle memcpy (x, "abcd", 5) or
2248 memcpy (x, "abc\0uvw", 7). */
2249 if (!tree_fits_uhwi_p (len
))
2252 unsigned HOST_WIDE_INT clen
= tree_to_uhwi (len
);
2253 unsigned HOST_WIDE_INT nonzero_chars
= ~idx
;
2254 newlen
= build_int_cst (size_type_node
, MIN (nonzero_chars
, clen
));
2255 full_string_p
= clen
> nonzero_chars
;
2258 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
2259 adjust_last_stmt (olddsi
, stmt
, false);
2263 didx
= new_stridx (dst
);
2270 dsi
= unshare_strinfo (olddsi
);
2271 oldlen
= olddsi
->nonzero_chars
;
2272 dsi
->nonzero_chars
= newlen
;
2273 dsi
->full_string_p
= full_string_p
;
2274 /* Break the chain, so adjust_related_strinfo on later pointers in
2275 the chain won't adjust this one anymore. */
2278 dsi
->endptr
= NULL_TREE
;
2282 dsi
= new_strinfo (dst
, didx
, newlen
, full_string_p
);
2283 set_strinfo (didx
, dsi
);
2284 find_equal_ptrs (dst
, didx
);
2286 dsi
->writable
= true;
2287 dsi
->dont_invalidate
= true;
2290 tree adj
= NULL_TREE
;
2291 location_t loc
= gimple_location (stmt
);
2292 if (oldlen
== NULL_TREE
)
2294 else if (integer_zerop (oldlen
))
2296 else if (TREE_CODE (oldlen
) == INTEGER_CST
2297 || TREE_CODE (newlen
) == INTEGER_CST
)
2298 adj
= fold_build2_loc (loc
, MINUS_EXPR
, TREE_TYPE (newlen
), newlen
,
2299 fold_convert_loc (loc
, TREE_TYPE (newlen
),
2301 if (adj
!= NULL_TREE
)
2302 adjust_related_strinfos (loc
, dsi
, adj
);
2306 /* memcpy src may not overlap dst, so src doesn't need to be
2307 invalidated either. */
2309 si
->dont_invalidate
= true;
2313 lhs
= gimple_call_lhs (stmt
);
2316 case BUILT_IN_MEMCPY
:
2317 case BUILT_IN_MEMCPY_CHK
:
2318 case BUILT_IN_MEMCPY_CHKP
:
2319 case BUILT_IN_MEMCPY_CHK_CHKP
:
2320 /* Allow adjust_last_stmt to decrease this memcpy's size. */
2321 laststmt
.stmt
= stmt
;
2322 laststmt
.len
= dsi
->nonzero_chars
;
2323 laststmt
.stridx
= dsi
->idx
;
2325 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
2327 case BUILT_IN_MEMPCPY
:
2328 case BUILT_IN_MEMPCPY_CHK
:
2329 case BUILT_IN_MEMPCPY_CHKP
:
2330 case BUILT_IN_MEMPCPY_CHK_CHKP
:
2338 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
2339 If strlen of the second argument is known, strlen of the first argument
2340 is increased by the length of the second argument. Furthermore, attempt
2341 to convert it to memcpy/strcpy if the length of the first argument
2345 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2348 tree srclen
, args
, type
, fn
, objsz
, endptr
;
2350 gimple
*stmt
= gsi_stmt (*gsi
);
2352 location_t loc
= gimple_location (stmt
);
2353 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
2355 tree src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
2356 tree dst
= gimple_call_arg (stmt
, 0);
2358 /* Bail if the source is the same as destination. It will be diagnosed
2360 if (operand_equal_p (src
, dst
, 0))
2363 tree lhs
= gimple_call_lhs (stmt
);
2365 didx
= get_stridx (dst
);
2371 dsi
= get_strinfo (didx
);
2375 idx
= get_stridx (src
);
2377 srclen
= build_int_cst (size_type_node
, ~idx
);
2380 si
= get_strinfo (idx
);
2382 srclen
= get_string_length (si
);
2385 /* Set the no-warning bit on the transformed statement? */
2386 bool set_no_warning
= false;
2388 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
2391 /* The concatenation always involves copying at least one byte
2392 (the terminating nul), even if the source string is empty.
2393 If the source is unknown assume it's one character long and
2394 used that as both sizes. */
2398 tree type
= TREE_TYPE (slen
);
2399 slen
= fold_build2 (PLUS_EXPR
, type
, slen
, build_int_cst (type
, 1));
2402 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2404 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, sptr
,
2407 gimple_set_no_warning (stmt
, true);
2408 set_no_warning
= true;
2412 /* strcat (p, q) can be transformed into
2413 tmp = p + strlen (p); endptr = stpcpy (tmp, q);
2414 with length endptr - p if we need to compute the length
2415 later on. Don't do this transformation if we don't need
2417 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
2421 didx
= new_stridx (dst
);
2427 dsi
= new_strinfo (dst
, didx
, NULL_TREE
, false);
2428 set_strinfo (didx
, dsi
);
2429 find_equal_ptrs (dst
, didx
);
2433 dsi
= unshare_strinfo (dsi
);
2434 dsi
->nonzero_chars
= NULL_TREE
;
2435 dsi
->full_string_p
= false;
2437 dsi
->endptr
= NULL_TREE
;
2439 dsi
->writable
= true;
2441 dsi
->dont_invalidate
= true;
2446 tree dstlen
= dsi
->nonzero_chars
;
2447 endptr
= dsi
->endptr
;
2449 dsi
= unshare_strinfo (dsi
);
2450 dsi
->endptr
= NULL_TREE
;
2452 dsi
->writable
= true;
2454 if (srclen
!= NULL_TREE
)
2456 dsi
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
2457 TREE_TYPE (dsi
->nonzero_chars
),
2458 dsi
->nonzero_chars
, srclen
);
2459 gcc_assert (dsi
->full_string_p
);
2460 adjust_related_strinfos (loc
, dsi
, srclen
);
2461 dsi
->dont_invalidate
= true;
2465 dsi
->nonzero_chars
= NULL
;
2466 dsi
->full_string_p
= false;
2467 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
2468 dsi
->dont_invalidate
= true;
2472 /* strcat src may not overlap dst, so src doesn't need to be
2473 invalidated either. */
2474 si
->dont_invalidate
= true;
2476 /* For now. Could remove the lhs from the call and add
2477 lhs = dst; afterwards. */
2485 case BUILT_IN_STRCAT
:
2486 case BUILT_IN_STRCAT_CHKP
:
2487 if (srclen
!= NULL_TREE
)
2488 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
2490 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
2492 case BUILT_IN_STRCAT_CHK
:
2493 case BUILT_IN_STRCAT_CHK_CHKP
:
2494 if (srclen
!= NULL_TREE
)
2495 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
2497 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
2498 objsz
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
2504 if (fn
== NULL_TREE
)
2509 tree type
= TREE_TYPE (dstlen
);
2511 /* Compute the size of the source sequence, including the nul. */
2512 tree srcsize
= srclen
? srclen
: size_zero_node
;
2513 srcsize
= fold_build2 (PLUS_EXPR
, type
, srcsize
, build_int_cst (type
, 1));
2515 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2517 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, sptr
,
2520 gimple_set_no_warning (stmt
, true);
2521 set_no_warning
= true;
2525 tree len
= NULL_TREE
;
2526 if (srclen
!= NULL_TREE
)
2528 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
2529 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
2531 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
2532 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
2533 build_int_cst (type
, 1));
2534 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
2538 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
2540 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
2541 TREE_TYPE (dst
), unshare_expr (dst
),
2542 fold_convert_loc (loc
, sizetype
,
2543 unshare_expr (dstlen
)));
2544 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
2546 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2548 fprintf (dump_file
, "Optimizing: ");
2549 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2553 fn
= chkp_maybe_create_clone (fn
)->decl
;
2554 if (srclen
!= NULL_TREE
)
2555 success
= update_gimple_call (gsi
, fn
, 5 + (objsz
!= NULL_TREE
),
2557 gimple_call_arg (stmt
, 1),
2559 gimple_call_arg (stmt
, 3),
2562 success
= update_gimple_call (gsi
, fn
, 4 + (objsz
!= NULL_TREE
),
2564 gimple_call_arg (stmt
, 1),
2566 gimple_call_arg (stmt
, 3),
2570 if (srclen
!= NULL_TREE
)
2571 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
2572 dst
, src
, len
, objsz
);
2574 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
2578 stmt
= gsi_stmt (*gsi
);
2579 gimple_call_set_with_bounds (stmt
, with_bounds
);
2581 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2583 fprintf (dump_file
, "into: ");
2584 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2586 /* If srclen == NULL, note that current string length can be
2587 computed by transforming this strcpy into stpcpy. */
2588 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
2590 adjust_last_stmt (dsi
, stmt
, true);
2591 if (srclen
!= NULL_TREE
)
2593 laststmt
.stmt
= stmt
;
2594 laststmt
.len
= srclen
;
2595 laststmt
.stridx
= dsi
->idx
;
2598 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2599 fprintf (dump_file
, "not possible.\n");
2602 gimple_set_no_warning (stmt
, true);
2605 /* Handle a call to malloc or calloc. */
2608 handle_builtin_malloc (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2610 gimple
*stmt
= gsi_stmt (*gsi
);
2611 tree lhs
= gimple_call_lhs (stmt
);
2612 if (lhs
== NULL_TREE
)
2615 gcc_assert (get_stridx (lhs
) == 0);
2616 int idx
= new_stridx (lhs
);
2617 tree length
= NULL_TREE
;
2618 if (bcode
== BUILT_IN_CALLOC
)
2619 length
= build_int_cst (size_type_node
, 0);
2620 strinfo
*si
= new_strinfo (lhs
, idx
, length
, length
!= NULL_TREE
);
2621 if (bcode
== BUILT_IN_CALLOC
)
2623 set_strinfo (idx
, si
);
2624 si
->writable
= true;
2626 si
->dont_invalidate
= true;
2629 /* Handle a call to memset.
2630 After a call to calloc, memset(,0,) is unnecessary.
2631 memset(malloc(n),0,n) is calloc(n,1).
2632 return true when the call is transfomred, false otherwise. */
2635 handle_builtin_memset (gimple_stmt_iterator
*gsi
)
2637 gimple
*stmt2
= gsi_stmt (*gsi
);
2638 if (!integer_zerop (gimple_call_arg (stmt2
, 1)))
2640 tree ptr
= gimple_call_arg (stmt2
, 0);
2641 int idx1
= get_stridx (ptr
);
2644 strinfo
*si1
= get_strinfo (idx1
);
2647 gimple
*stmt1
= si1
->stmt
;
2648 if (!stmt1
|| !is_gimple_call (stmt1
))
2650 tree callee1
= gimple_call_fndecl (stmt1
);
2651 if (!valid_builtin_call (stmt1
))
2653 enum built_in_function code1
= DECL_FUNCTION_CODE (callee1
);
2654 tree size
= gimple_call_arg (stmt2
, 2);
2655 if (code1
== BUILT_IN_CALLOC
)
2656 /* Not touching stmt1 */ ;
2657 else if (code1
== BUILT_IN_MALLOC
2658 && operand_equal_p (gimple_call_arg (stmt1
, 0), size
, 0))
2660 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt1
);
2661 update_gimple_call (&gsi1
, builtin_decl_implicit (BUILT_IN_CALLOC
), 2,
2662 size
, build_one_cst (size_type_node
));
2663 si1
->nonzero_chars
= build_int_cst (size_type_node
, 0);
2664 si1
->full_string_p
= true;
2665 si1
->stmt
= gsi_stmt (gsi1
);
2669 tree lhs
= gimple_call_lhs (stmt2
);
2670 unlink_stmt_vdef (stmt2
);
2673 gimple
*assign
= gimple_build_assign (lhs
, ptr
);
2674 gsi_replace (gsi
, assign
, false);
2678 gsi_remove (gsi
, true);
2679 release_defs (stmt2
);
2685 /* Handle a call to memcmp. We try to handle small comparisons by
2686 converting them to load and compare, and replacing the call to memcmp
2687 with a __builtin_memcmp_eq call where possible.
2688 return true when call is transformed, return false otherwise. */
2691 handle_builtin_memcmp (gimple_stmt_iterator
*gsi
)
2693 gcall
*stmt2
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2694 tree res
= gimple_call_lhs (stmt2
);
2695 tree arg1
= gimple_call_arg (stmt2
, 0);
2696 tree arg2
= gimple_call_arg (stmt2
, 1);
2697 tree len
= gimple_call_arg (stmt2
, 2);
2698 unsigned HOST_WIDE_INT leni
;
2699 use_operand_p use_p
;
2700 imm_use_iterator iter
;
2705 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
2707 gimple
*ustmt
= USE_STMT (use_p
);
2709 if (is_gimple_debug (ustmt
))
2711 if (gimple_code (ustmt
) == GIMPLE_ASSIGN
)
2713 gassign
*asgn
= as_a
<gassign
*> (ustmt
);
2714 tree_code code
= gimple_assign_rhs_code (asgn
);
2715 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2716 || !integer_zerop (gimple_assign_rhs2 (asgn
)))
2719 else if (gimple_code (ustmt
) == GIMPLE_COND
)
2721 tree_code code
= gimple_cond_code (ustmt
);
2722 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2723 || !integer_zerop (gimple_cond_rhs (ustmt
)))
2730 if (tree_fits_uhwi_p (len
)
2731 && (leni
= tree_to_uhwi (len
)) <= GET_MODE_SIZE (word_mode
)
2732 && pow2p_hwi (leni
))
2734 leni
*= CHAR_TYPE_SIZE
;
2735 unsigned align1
= get_pointer_alignment (arg1
);
2736 unsigned align2
= get_pointer_alignment (arg2
);
2737 unsigned align
= MIN (align1
, align2
);
2738 scalar_int_mode mode
;
2739 if (int_mode_for_size (leni
, 1).exists (&mode
)
2740 && (align
>= leni
|| !targetm
.slow_unaligned_access (mode
, align
)))
2742 location_t loc
= gimple_location (stmt2
);
2744 type
= build_nonstandard_integer_type (leni
, 1);
2745 gcc_assert (known_eq (GET_MODE_BITSIZE (TYPE_MODE (type
)), leni
));
2746 tree ptrtype
= build_pointer_type_for_mode (char_type_node
,
2748 off
= build_int_cst (ptrtype
, 0);
2749 arg1
= build2_loc (loc
, MEM_REF
, type
, arg1
, off
);
2750 arg2
= build2_loc (loc
, MEM_REF
, type
, arg2
, off
);
2751 tree tem1
= fold_const_aggregate_ref (arg1
);
2754 tree tem2
= fold_const_aggregate_ref (arg2
);
2757 res
= fold_convert_loc (loc
, TREE_TYPE (res
),
2758 fold_build2_loc (loc
, NE_EXPR
,
2761 gimplify_and_update_call_from_tree (gsi
, res
);
2766 gimple_call_set_fndecl (stmt2
, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ
));
2770 /* Given an index to the strinfo vector, compute the string length for the
2771 corresponding string. Return -1 when unknown. */
2773 static HOST_WIDE_INT
2774 compute_string_length (int idx
)
2776 HOST_WIDE_INT string_leni
= -1;
2777 gcc_assert (idx
!= 0);
2782 strinfo
*si
= get_strinfo (idx
);
2785 tree const_string_len
= get_string_length (si
);
2786 if (const_string_len
&& tree_fits_shwi_p (const_string_len
))
2787 string_leni
= tree_to_shwi (const_string_len
);
2790 if (string_leni
< 0)
2796 /* Determine the minimum size of the object referenced by DEST expression which
2797 must have a pointer type.
2798 Return the minimum size of the object if successful or NULL when the size
2799 cannot be determined. */
2801 determine_min_objsize (tree dest
)
2803 unsigned HOST_WIDE_INT size
= 0;
2805 if (compute_builtin_object_size (dest
, 2, &size
))
2806 return build_int_cst (sizetype
, size
);
2808 /* Try to determine the size of the object through the RHS of the
2809 assign statement. */
2810 if (TREE_CODE (dest
) == SSA_NAME
)
2812 gimple
*stmt
= SSA_NAME_DEF_STMT (dest
);
2813 if (!is_gimple_assign (stmt
))
2816 if (!gimple_assign_single_p (stmt
)
2817 && !gimple_assign_unary_nop_p (stmt
))
2820 dest
= gimple_assign_rhs1 (stmt
);
2821 return determine_min_objsize (dest
);
2824 /* Try to determine the size of the object from its type. */
2825 if (TREE_CODE (dest
) != ADDR_EXPR
)
2828 tree type
= TREE_TYPE (dest
);
2829 if (TREE_CODE (type
) == POINTER_TYPE
)
2830 type
= TREE_TYPE (type
);
2832 type
= TYPE_MAIN_VARIANT (type
);
2834 /* We cannot determine the size of the array if it's a flexible array,
2835 which is declared at the end of a structure. */
2836 if (TREE_CODE (type
) == ARRAY_TYPE
2837 && !array_at_struct_end_p (dest
))
2839 tree
size_t = TYPE_SIZE_UNIT (type
);
2840 if (size_t && TREE_CODE (size_t) == INTEGER_CST
2841 && !integer_zerop (size_t))
2848 /* Handle a call to strcmp or strncmp. When the result is ONLY used to do
2849 equality test against zero:
2851 A. When the lengths of both arguments are constant and it's a strcmp:
2852 * if the lengths are NOT equal, we can safely fold the call
2853 to a non-zero value.
2854 * otherwise, do nothing now.
2856 B. When the length of one argument is constant, try to replace the call with
2857 a __builtin_str(n)cmp_eq call where possible, i.e:
2859 strncmp (s, STR, C) (!)= 0 in which, s is a pointer to a string, STR is a
2860 string with constant length , C is a constant.
2861 if (C <= strlen(STR) && sizeof_array(s) > C)
2863 replace this call with
2864 strncmp_eq (s, STR, C) (!)= 0
2868 it can be safely treated as a call to strcmp (s, STR) (!)= 0
2869 can handled by the following strcmp.
2872 strcmp (s, STR) (!)= 0 in which, s is a pointer to a string, STR is a
2873 string with constant length.
2874 if (sizeof_array(s) > strlen(STR))
2876 replace this call with
2877 strcmp_eq (s, STR, strlen(STR)+1) (!)= 0
2880 Return true when the call is transformed, return false otherwise.
2884 handle_builtin_string_cmp (gimple_stmt_iterator
*gsi
)
2886 gcall
*stmt
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2887 tree res
= gimple_call_lhs (stmt
);
2888 use_operand_p use_p
;
2889 imm_use_iterator iter
;
2890 tree arg1
= gimple_call_arg (stmt
, 0);
2891 tree arg2
= gimple_call_arg (stmt
, 1);
2892 int idx1
= get_stridx (arg1
);
2893 int idx2
= get_stridx (arg2
);
2894 HOST_WIDE_INT length
= -1;
2895 bool is_ncmp
= false;
2900 /* When both arguments are unknown, do nothing. */
2901 if (idx1
== 0 && idx2
== 0)
2904 /* Handle strncmp function. */
2905 if (gimple_call_num_args (stmt
) == 3)
2907 tree len
= gimple_call_arg (stmt
, 2);
2908 if (tree_fits_shwi_p (len
))
2909 length
= tree_to_shwi (len
);
2914 /* For strncmp, if the length argument is NOT known, do nothing. */
2915 if (is_ncmp
&& length
< 0)
2918 /* When the result is ONLY used to do equality test against zero. */
2919 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
2921 gimple
*use_stmt
= USE_STMT (use_p
);
2923 if (is_gimple_debug (use_stmt
))
2925 if (gimple_code (use_stmt
) == GIMPLE_ASSIGN
)
2927 tree_code code
= gimple_assign_rhs_code (use_stmt
);
2928 if (code
== COND_EXPR
)
2930 tree cond_expr
= gimple_assign_rhs1 (use_stmt
);
2931 if ((TREE_CODE (cond_expr
) != EQ_EXPR
2932 && (TREE_CODE (cond_expr
) != NE_EXPR
))
2933 || !integer_zerop (TREE_OPERAND (cond_expr
, 1)))
2936 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
2938 if (!integer_zerop (gimple_assign_rhs2 (use_stmt
)))
2944 else if (gimple_code (use_stmt
) == GIMPLE_COND
)
2946 tree_code code
= gimple_cond_code (use_stmt
);
2947 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2948 || !integer_zerop (gimple_cond_rhs (use_stmt
)))
2955 /* When the lengths of both arguments are known, and they are unequal, we can
2956 safely fold the call to a non-zero value for strcmp;
2957 othewise, do nothing now. */
2958 if (idx1
!= 0 && idx2
!= 0)
2960 HOST_WIDE_INT const_string_leni1
= compute_string_length (idx1
);
2961 HOST_WIDE_INT const_string_leni2
= compute_string_length (idx2
);
2964 && const_string_leni1
!= -1
2965 && const_string_leni2
!= -1
2966 && const_string_leni1
!= const_string_leni2
)
2968 replace_call_with_value (gsi
, integer_one_node
);
2974 /* When the length of one argument is constant. */
2975 tree var_string
= NULL_TREE
;
2976 HOST_WIDE_INT const_string_leni
= -1;
2980 const_string_leni
= compute_string_length (idx1
);
2985 gcc_checking_assert (idx2
);
2986 const_string_leni
= compute_string_length (idx2
);
2990 if (const_string_leni
< 0)
2993 unsigned HOST_WIDE_INT var_sizei
= 0;
2994 /* try to determine the minimum size of the object pointed by var_string. */
2995 tree size
= determine_min_objsize (var_string
);
3000 if (tree_fits_uhwi_p (size
))
3001 var_sizei
= tree_to_uhwi (size
);
3006 /* For strncmp, if length > const_string_leni , this call can be safely
3007 transformed to a strcmp. */
3008 if (is_ncmp
&& length
> const_string_leni
)
3011 unsigned HOST_WIDE_INT final_length
3012 = is_ncmp
? length
: const_string_leni
+ 1;
3014 /* Replace strcmp or strncmp with the corresponding str(n)cmp_eq. */
3015 if (var_sizei
> final_length
)
3019 ? builtin_decl_implicit (BUILT_IN_STRNCMP_EQ
)
3020 : builtin_decl_implicit (BUILT_IN_STRCMP_EQ
));
3023 tree const_string_len
= build_int_cst (size_type_node
, final_length
);
3024 update_gimple_call (gsi
, fn
, 3, arg1
, arg2
, const_string_len
);
3032 /* Handle a POINTER_PLUS_EXPR statement.
3033 For p = "abcd" + 2; compute associated length, or if
3034 p = q + off is pointing to a '\0' character of a string, call
3035 zero_length_string on it. */
3038 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
3040 gimple
*stmt
= gsi_stmt (*gsi
);
3041 tree lhs
= gimple_assign_lhs (stmt
), off
;
3042 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
3050 tree off
= gimple_assign_rhs2 (stmt
);
3051 if (tree_fits_uhwi_p (off
)
3052 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
3053 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
3054 = ~(~idx
- (int) tree_to_uhwi (off
));
3058 si
= get_strinfo (idx
);
3059 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
3062 off
= gimple_assign_rhs2 (stmt
);
3064 if (si
->full_string_p
&& operand_equal_p (si
->nonzero_chars
, off
, 0))
3065 zsi
= zero_length_string (lhs
, si
);
3066 else if (TREE_CODE (off
) == SSA_NAME
)
3068 gimple
*def_stmt
= SSA_NAME_DEF_STMT (off
);
3069 if (gimple_assign_single_p (def_stmt
)
3070 && si
->full_string_p
3071 && operand_equal_p (si
->nonzero_chars
,
3072 gimple_assign_rhs1 (def_stmt
), 0))
3073 zsi
= zero_length_string (lhs
, si
);
3076 && si
->endptr
!= NULL_TREE
3077 && si
->endptr
!= lhs
3078 && TREE_CODE (si
->endptr
) == SSA_NAME
)
3080 enum tree_code rhs_code
3081 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
3082 ? SSA_NAME
: NOP_EXPR
;
3083 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
);
3084 gcc_assert (gsi_stmt (*gsi
) == stmt
);
3089 /* If RHS, either directly or indirectly, refers to a string of constant
3090 length, return it. Otherwise return a negative value. */
3092 static HOST_WIDE_INT
3093 get_string_cst_length (tree rhs
)
3095 if (TREE_CODE (rhs
) == MEM_REF
3096 && integer_zerop (TREE_OPERAND (rhs
, 1)))
3098 rhs
= TREE_OPERAND (rhs
, 0);
3099 if (TREE_CODE (rhs
) == ADDR_EXPR
)
3101 tree rhs_addr
= rhs
;
3103 rhs
= TREE_OPERAND (rhs
, 0);
3104 if (TREE_CODE (rhs
) != STRING_CST
)
3106 int idx
= get_stridx (rhs_addr
);
3109 strinfo
*si
= get_strinfo (idx
);
3111 && si
->full_string_p
3112 && tree_fits_shwi_p (si
->nonzero_chars
))
3113 return tree_to_shwi (si
->nonzero_chars
);
3119 if (TREE_CODE (rhs
) == VAR_DECL
3120 && TREE_READONLY (rhs
))
3121 rhs
= DECL_INITIAL (rhs
);
3123 if (rhs
&& TREE_CODE (rhs
) == STRING_CST
)
3124 return strlen (TREE_STRING_POINTER (rhs
));
3129 /* Handle a single character store. */
3132 handle_char_store (gimple_stmt_iterator
*gsi
)
3136 gimple
*stmt
= gsi_stmt (*gsi
);
3137 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
3138 tree rhs
= gimple_assign_rhs1 (stmt
);
3139 unsigned HOST_WIDE_INT offset
= 0;
3141 if (TREE_CODE (lhs
) == MEM_REF
3142 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
3144 tree mem_offset
= TREE_OPERAND (lhs
, 1);
3145 if (tree_fits_uhwi_p (mem_offset
))
3147 /* Get the strinfo for the base, and use it if it starts with at
3148 least OFFSET nonzero characters. This is trivially true if
3150 offset
= tree_to_uhwi (mem_offset
);
3151 idx
= get_stridx (TREE_OPERAND (lhs
, 0));
3153 si
= get_strinfo (idx
);
3155 ssaname
= TREE_OPERAND (lhs
, 0);
3156 else if (si
== NULL
|| compare_nonzero_chars (si
, offset
) < 0)
3162 idx
= get_addr_stridx (lhs
, NULL_TREE
, &offset
);
3164 si
= get_strinfo (idx
);
3167 bool storing_zero_p
= initializer_zerop (rhs
);
3168 bool storing_nonzero_p
= (!storing_zero_p
3169 && TREE_CODE (rhs
) == INTEGER_CST
3170 && integer_nonzerop (rhs
));
3171 /* Set to the length of the string being assigned if known. */
3172 HOST_WIDE_INT rhslen
;
3176 int cmp
= compare_nonzero_chars (si
, offset
);
3177 gcc_assert (offset
== 0 || cmp
>= 0);
3178 if (storing_zero_p
&& cmp
== 0 && si
->full_string_p
)
3180 /* When overwriting a '\0' with a '\0', the store can be removed
3181 if we know it has been stored in the current function. */
3182 if (!stmt_could_throw_p (stmt
) && si
->writable
)
3184 unlink_stmt_vdef (stmt
);
3185 release_defs (stmt
);
3186 gsi_remove (gsi
, true);
3191 si
->writable
= true;
3196 /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0',
3197 and if we aren't storing '\0', we know that the length of the
3198 string and any other zero terminated string in memory remains
3199 the same. In that case we move to the next gimple statement and
3200 return to signal the caller that it shouldn't invalidate anything.
3202 This is benefical for cases like:
3207 strcpy (p, "foobar");
3208 size_t len = strlen (p); // This can be optimized into 6
3209 size_t len2 = strlen (q); // This has to be computed
3211 size_t len3 = strlen (p); // This can be optimized into 6
3212 size_t len4 = strlen (q); // This can be optimized into len2
3213 bar (len, len2, len3, len4);
3216 else if (storing_nonzero_p
&& cmp
> 0)
3221 else if (storing_zero_p
|| storing_nonzero_p
|| (offset
!= 0 && cmp
> 0))
3223 /* When storing_nonzero_p, we know that the string now starts
3224 with OFFSET + 1 nonzero characters, but don't know whether
3225 there's a following nul terminator.
3227 When storing_zero_p, we know that the string is now OFFSET
3230 Otherwise, we're storing an unknown value at offset OFFSET,
3231 so need to clip the nonzero_chars to OFFSET. */
3232 location_t loc
= gimple_location (stmt
);
3233 tree oldlen
= si
->nonzero_chars
;
3234 if (cmp
== 0 && si
->full_string_p
)
3235 /* We're overwriting the nul terminator with a nonzero or
3236 unknown character. If the previous stmt was a memcpy,
3237 its length may be decreased. */
3238 adjust_last_stmt (si
, stmt
, false);
3239 si
= unshare_strinfo (si
);
3240 if (storing_nonzero_p
)
3241 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
+ 1);
3243 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
);
3244 si
->full_string_p
= storing_zero_p
;
3247 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
3248 si
->endptr
= ssaname
;
3253 si
->writable
= true;
3254 si
->dont_invalidate
= true;
3257 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
3258 si
->nonzero_chars
, oldlen
);
3259 adjust_related_strinfos (loc
, si
, adj
);
3265 else if (idx
== 0 && (storing_zero_p
|| storing_nonzero_p
))
3268 idx
= new_stridx (ssaname
);
3270 idx
= new_addr_stridx (lhs
);
3273 tree ptr
= (ssaname
? ssaname
: build_fold_addr_expr (lhs
));
3274 tree len
= storing_nonzero_p
? size_one_node
: size_zero_node
;
3275 si
= new_strinfo (ptr
, idx
, len
, storing_zero_p
);
3276 set_strinfo (idx
, si
);
3279 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
3280 si
->endptr
= ssaname
;
3281 si
->dont_invalidate
= true;
3282 si
->writable
= true;
3286 && (rhslen
= get_string_cst_length (gimple_assign_rhs1 (stmt
))) >= 0
3287 && ssaname
== NULL_TREE
3288 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
3290 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
3291 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> (unsigned HOST_WIDE_INT
) rhslen
)
3293 int idx
= new_addr_stridx (lhs
);
3296 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
3297 build_int_cst (size_type_node
, rhslen
), true);
3298 set_strinfo (idx
, si
);
3299 si
->dont_invalidate
= true;
3304 if (si
!= NULL
&& offset
== 0 && storing_zero_p
)
3306 /* Allow adjust_last_stmt to remove it if the stored '\0'
3307 is immediately overwritten. */
3308 laststmt
.stmt
= stmt
;
3309 laststmt
.len
= build_int_cst (size_type_node
, 1);
3310 laststmt
.stridx
= si
->idx
;
3315 /* Try to fold strstr (s, t) eq/ne s to strncmp (s, t, strlen (t)) eq/ne 0. */
3318 fold_strstr_to_strncmp (tree rhs1
, tree rhs2
, gimple
*stmt
)
3320 if (TREE_CODE (rhs1
) != SSA_NAME
3321 || TREE_CODE (rhs2
) != SSA_NAME
)
3324 gimple
*call_stmt
= NULL
;
3325 for (int pass
= 0; pass
< 2; pass
++)
3327 gimple
*g
= SSA_NAME_DEF_STMT (rhs1
);
3328 if (gimple_call_builtin_p (g
, BUILT_IN_STRSTR
)
3329 && has_single_use (rhs1
)
3330 && gimple_call_arg (g
, 0) == rhs2
)
3335 std::swap (rhs1
, rhs2
);
3340 tree arg0
= gimple_call_arg (call_stmt
, 0);
3344 tree arg1
= gimple_call_arg (call_stmt
, 1);
3345 tree arg1_len
= NULL_TREE
;
3346 int idx
= get_stridx (arg1
);
3351 arg1_len
= build_int_cst (size_type_node
, ~idx
);
3354 strinfo
*si
= get_strinfo (idx
);
3356 arg1_len
= get_string_length (si
);
3360 if (arg1_len
!= NULL_TREE
)
3362 gimple_stmt_iterator gsi
= gsi_for_stmt (call_stmt
);
3363 tree strncmp_decl
= builtin_decl_explicit (BUILT_IN_STRNCMP
);
3365 if (!is_gimple_val (arg1_len
))
3367 tree arg1_len_tmp
= make_ssa_name (TREE_TYPE (arg1_len
));
3368 gassign
*arg1_stmt
= gimple_build_assign (arg1_len_tmp
,
3370 gsi_insert_before (&gsi
, arg1_stmt
, GSI_SAME_STMT
);
3371 arg1_len
= arg1_len_tmp
;
3374 gcall
*strncmp_call
= gimple_build_call (strncmp_decl
, 3,
3375 arg0
, arg1
, arg1_len
);
3376 tree strncmp_lhs
= make_ssa_name (integer_type_node
);
3377 gimple_set_vuse (strncmp_call
, gimple_vuse (call_stmt
));
3378 gimple_call_set_lhs (strncmp_call
, strncmp_lhs
);
3379 gsi_remove (&gsi
, true);
3380 gsi_insert_before (&gsi
, strncmp_call
, GSI_SAME_STMT
);
3381 tree zero
= build_zero_cst (TREE_TYPE (strncmp_lhs
));
3383 if (is_gimple_assign (stmt
))
3385 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
3387 tree cond
= gimple_assign_rhs1 (stmt
);
3388 TREE_OPERAND (cond
, 0) = strncmp_lhs
;
3389 TREE_OPERAND (cond
, 1) = zero
;
3393 gimple_assign_set_rhs1 (stmt
, strncmp_lhs
);
3394 gimple_assign_set_rhs2 (stmt
, zero
);
3399 gcond
*cond
= as_a
<gcond
*> (stmt
);
3400 gimple_cond_set_lhs (cond
, strncmp_lhs
);
3401 gimple_cond_set_rhs (cond
, zero
);
3409 /* Attempt to check for validity of the performed access a single statement
3410 at *GSI using string length knowledge, and to optimize it.
3411 If the given basic block needs clean-up of EH, CLEANUP_EH is set to
3415 strlen_check_and_optimize_stmt (gimple_stmt_iterator
*gsi
, bool *cleanup_eh
)
3417 gimple
*stmt
= gsi_stmt (*gsi
);
3419 if (is_gimple_call (stmt
))
3421 tree callee
= gimple_call_fndecl (stmt
);
3422 if (valid_builtin_call (stmt
))
3423 switch (DECL_FUNCTION_CODE (callee
))
3425 case BUILT_IN_STRLEN
:
3426 case BUILT_IN_STRLEN_CHKP
:
3427 handle_builtin_strlen (gsi
);
3429 case BUILT_IN_STRCHR
:
3430 case BUILT_IN_STRCHR_CHKP
:
3431 handle_builtin_strchr (gsi
);
3433 case BUILT_IN_STRCPY
:
3434 case BUILT_IN_STRCPY_CHK
:
3435 case BUILT_IN_STPCPY
:
3436 case BUILT_IN_STPCPY_CHK
:
3437 case BUILT_IN_STRCPY_CHKP
:
3438 case BUILT_IN_STRCPY_CHK_CHKP
:
3439 case BUILT_IN_STPCPY_CHKP
:
3440 case BUILT_IN_STPCPY_CHK_CHKP
:
3441 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3444 case BUILT_IN_STRNCAT
:
3445 case BUILT_IN_STRNCAT_CHK
:
3446 handle_builtin_strncat (DECL_FUNCTION_CODE (callee
), gsi
);
3449 case BUILT_IN_STPNCPY
:
3450 case BUILT_IN_STPNCPY_CHK
:
3451 case BUILT_IN_STRNCPY
:
3452 case BUILT_IN_STRNCPY_CHK
:
3453 handle_builtin_stxncpy (DECL_FUNCTION_CODE (callee
), gsi
);
3456 case BUILT_IN_MEMCPY
:
3457 case BUILT_IN_MEMCPY_CHK
:
3458 case BUILT_IN_MEMPCPY
:
3459 case BUILT_IN_MEMPCPY_CHK
:
3460 case BUILT_IN_MEMCPY_CHKP
:
3461 case BUILT_IN_MEMCPY_CHK_CHKP
:
3462 case BUILT_IN_MEMPCPY_CHKP
:
3463 case BUILT_IN_MEMPCPY_CHK_CHKP
:
3464 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3466 case BUILT_IN_STRCAT
:
3467 case BUILT_IN_STRCAT_CHK
:
3468 case BUILT_IN_STRCAT_CHKP
:
3469 case BUILT_IN_STRCAT_CHK_CHKP
:
3470 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
3472 case BUILT_IN_MALLOC
:
3473 case BUILT_IN_CALLOC
:
3474 handle_builtin_malloc (DECL_FUNCTION_CODE (callee
), gsi
);
3476 case BUILT_IN_MEMSET
:
3477 if (handle_builtin_memset (gsi
))
3480 case BUILT_IN_MEMCMP
:
3481 if (handle_builtin_memcmp (gsi
))
3484 case BUILT_IN_STRCMP
:
3485 case BUILT_IN_STRNCMP
:
3486 if (handle_builtin_string_cmp (gsi
))
3493 else if (is_gimple_assign (stmt
) && !gimple_clobber_p (stmt
))
3495 tree lhs
= gimple_assign_lhs (stmt
);
3497 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
3499 if (gimple_assign_single_p (stmt
)
3500 || (gimple_assign_cast_p (stmt
)
3501 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
3503 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
3504 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
3506 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
3507 handle_pointer_plus (gsi
);
3509 else if (TREE_CODE (lhs
) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
3511 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3512 if (code
== COND_EXPR
)
3514 tree cond
= gimple_assign_rhs1 (stmt
);
3515 enum tree_code cond_code
= TREE_CODE (cond
);
3517 if (cond_code
== EQ_EXPR
|| cond_code
== NE_EXPR
)
3518 fold_strstr_to_strncmp (TREE_OPERAND (cond
, 0),
3519 TREE_OPERAND (cond
, 1), stmt
);
3521 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3522 fold_strstr_to_strncmp (gimple_assign_rhs1 (stmt
),
3523 gimple_assign_rhs2 (stmt
), stmt
);
3524 else if (gimple_assign_load_p (stmt
)
3525 && TREE_CODE (TREE_TYPE (lhs
)) == INTEGER_TYPE
3526 && TYPE_MODE (TREE_TYPE (lhs
)) == TYPE_MODE (char_type_node
)
3527 && (TYPE_PRECISION (TREE_TYPE (lhs
))
3528 == TYPE_PRECISION (char_type_node
))
3529 && !gimple_has_volatile_ops (stmt
))
3531 tree off
= integer_zero_node
;
3532 unsigned HOST_WIDE_INT coff
= 0;
3534 tree rhs1
= gimple_assign_rhs1 (stmt
);
3535 if (code
== MEM_REF
)
3537 idx
= get_stridx (TREE_OPERAND (rhs1
, 0));
3540 strinfo
*si
= get_strinfo (idx
);
3542 && si
->nonzero_chars
3543 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
3544 && (wi::to_widest (si
->nonzero_chars
)
3545 >= wi::to_widest (off
)))
3546 off
= TREE_OPERAND (rhs1
, 1);
3548 /* This case is not useful. See if get_addr_stridx
3549 returns something usable. */
3554 idx
= get_addr_stridx (rhs1
, NULL_TREE
, &coff
);
3557 strinfo
*si
= get_strinfo (idx
);
3559 && si
->nonzero_chars
3560 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
3562 widest_int w1
= wi::to_widest (si
->nonzero_chars
);
3563 widest_int w2
= wi::to_widest (off
) + coff
;
3565 && si
->full_string_p
)
3567 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3569 fprintf (dump_file
, "Optimizing: ");
3570 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3573 /* Reading the final '\0' character. */
3574 tree zero
= build_int_cst (TREE_TYPE (lhs
), 0);
3575 gimple_set_vuse (stmt
, NULL_TREE
);
3576 gimple_assign_set_rhs_from_tree (gsi
, zero
);
3578 |= maybe_clean_or_replace_eh_stmt (stmt
,
3580 stmt
= gsi_stmt (*gsi
);
3583 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3585 fprintf (dump_file
, "into: ");
3586 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3591 /* Reading a character before the final '\0'
3592 character. Just set the value range to ~[0, 0]
3593 if we don't have anything better. */
3595 tree type
= TREE_TYPE (lhs
);
3596 enum value_range_type vr
3597 = get_range_info (lhs
, &min
, &max
);
3598 if (vr
== VR_VARYING
3600 && min
== wi::min_value (TYPE_PRECISION (type
),
3602 && max
== wi::max_value (TYPE_PRECISION (type
),
3604 set_range_info (lhs
, VR_ANTI_RANGE
,
3605 wi::zero (TYPE_PRECISION (type
)),
3606 wi::zero (TYPE_PRECISION (type
)));
3612 if (strlen_to_stridx
)
3614 tree rhs1
= gimple_assign_rhs1 (stmt
);
3615 if (stridx_strlenloc
*ps
= strlen_to_stridx
->get (rhs1
))
3616 strlen_to_stridx
->put (lhs
, stridx_strlenloc (*ps
));
3619 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
3621 tree type
= TREE_TYPE (lhs
);
3622 if (TREE_CODE (type
) == ARRAY_TYPE
)
3623 type
= TREE_TYPE (type
);
3624 if (TREE_CODE (type
) == INTEGER_TYPE
3625 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
3626 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
3628 if (! handle_char_store (gsi
))
3633 else if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
3635 enum tree_code code
= gimple_cond_code (cond
);
3636 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3637 fold_strstr_to_strncmp (gimple_cond_lhs (stmt
),
3638 gimple_cond_rhs (stmt
), stmt
);
3641 if (gimple_vdef (stmt
))
3642 maybe_invalidate (stmt
);
3646 /* Recursively call maybe_invalidate on stmts that might be executed
3647 in between dombb and current bb and that contain a vdef. Stop when
3648 *count stmts are inspected, or if the whole strinfo vector has
3649 been invalidated. */
3652 do_invalidate (basic_block dombb
, gimple
*phi
, bitmap visited
, int *count
)
3654 unsigned int i
, n
= gimple_phi_num_args (phi
);
3656 for (i
= 0; i
< n
; i
++)
3658 tree vuse
= gimple_phi_arg_def (phi
, i
);
3659 gimple
*stmt
= SSA_NAME_DEF_STMT (vuse
);
3660 basic_block bb
= gimple_bb (stmt
);
3663 || !bitmap_set_bit (visited
, bb
->index
)
3664 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3668 if (gimple_code (stmt
) == GIMPLE_PHI
)
3670 do_invalidate (dombb
, stmt
, visited
, count
);
3677 if (!maybe_invalidate (stmt
))
3682 vuse
= gimple_vuse (stmt
);
3683 stmt
= SSA_NAME_DEF_STMT (vuse
);
3684 if (gimple_bb (stmt
) != bb
)
3686 bb
= gimple_bb (stmt
);
3689 || !bitmap_set_bit (visited
, bb
->index
)
3690 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3697 class strlen_dom_walker
: public dom_walker
3700 strlen_dom_walker (cdi_direction direction
)
3701 : dom_walker (direction
), m_cleanup_cfg (false)
3704 virtual edge
before_dom_children (basic_block
);
3705 virtual void after_dom_children (basic_block
);
3707 /* Flag that will trigger TODO_cleanup_cfg to be returned in strlen
3708 execute function. */
3712 /* Callback for walk_dominator_tree. Attempt to optimize various
3713 string ops by remembering string lengths pointed by pointer SSA_NAMEs. */
3716 strlen_dom_walker::before_dom_children (basic_block bb
)
3718 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
3721 stridx_to_strinfo
= NULL
;
3724 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) dombb
->aux
);
3725 if (stridx_to_strinfo
)
3727 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3730 gphi
*phi
= gsi
.phi ();
3731 if (virtual_operand_p (gimple_phi_result (phi
)))
3733 bitmap visited
= BITMAP_ALLOC (NULL
);
3734 int count_vdef
= 100;
3735 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
3736 BITMAP_FREE (visited
);
3737 if (count_vdef
== 0)
3739 /* If there were too many vdefs in between immediate
3740 dominator and current bb, invalidate everything.
3741 If stridx_to_strinfo has been unshared, we need
3742 to free it, otherwise just set it to NULL. */
3743 if (!strinfo_shared ())
3749 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
3753 (*stridx_to_strinfo
)[i
] = NULL
;
3757 stridx_to_strinfo
= NULL
;
3765 /* If all PHI arguments have the same string index, the PHI result
3767 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3770 gphi
*phi
= gsi
.phi ();
3771 tree result
= gimple_phi_result (phi
);
3772 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
3774 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
3777 unsigned int i
, n
= gimple_phi_num_args (phi
);
3778 for (i
= 1; i
< n
; i
++)
3779 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
3782 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
3787 bool cleanup_eh
= false;
3789 /* Attempt to optimize individual statements. */
3790 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
3791 if (strlen_check_and_optimize_stmt (&gsi
, &cleanup_eh
))
3794 if (cleanup_eh
&& gimple_purge_dead_eh_edges (bb
))
3795 m_cleanup_cfg
= true;
3797 bb
->aux
= stridx_to_strinfo
;
3798 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
3799 (*stridx_to_strinfo
)[0] = (strinfo
*) bb
;
3803 /* Callback for walk_dominator_tree. Free strinfo vector if it is
3804 owned by the current bb, clear bb->aux. */
3807 strlen_dom_walker::after_dom_children (basic_block bb
)
3811 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) bb
->aux
);
3812 if (vec_safe_length (stridx_to_strinfo
)
3813 && (*stridx_to_strinfo
)[0] == (strinfo
*) bb
)
3818 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
3820 vec_free (stridx_to_strinfo
);
3826 /* Main entry point. */
3830 const pass_data pass_data_strlen
=
3832 GIMPLE_PASS
, /* type */
3833 "strlen", /* name */
3834 OPTGROUP_NONE
, /* optinfo_flags */
3835 TV_TREE_STRLEN
, /* tv_id */
3836 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3837 0, /* properties_provided */
3838 0, /* properties_destroyed */
3839 0, /* todo_flags_start */
3840 0, /* todo_flags_finish */
3843 class pass_strlen
: public gimple_opt_pass
3846 pass_strlen (gcc::context
*ctxt
)
3847 : gimple_opt_pass (pass_data_strlen
, ctxt
)
3850 /* opt_pass methods: */
3851 virtual bool gate (function
*) { return flag_optimize_strlen
!= 0; }
3852 virtual unsigned int execute (function
*);
3854 }; // class pass_strlen
3857 pass_strlen::execute (function
*fun
)
3859 gcc_assert (!strlen_to_stridx
);
3860 if (warn_stringop_overflow
|| warn_stringop_truncation
)
3861 strlen_to_stridx
= new hash_map
<tree
, stridx_strlenloc
> ();
3863 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
3866 calculate_dominance_info (CDI_DOMINATORS
);
3868 /* String length optimization is implemented as a walk of the dominator
3869 tree and a forward walk of statements within each block. */
3870 strlen_dom_walker
walker (CDI_DOMINATORS
);
3871 walker
.walk (fun
->cfg
->x_entry_block_ptr
);
3873 ssa_ver_to_stridx
.release ();
3874 strinfo_pool
.release ();
3875 if (decl_to_stridxlist_htab
)
3877 obstack_free (&stridx_obstack
, NULL
);
3878 delete decl_to_stridxlist_htab
;
3879 decl_to_stridxlist_htab
= NULL
;
3881 laststmt
.stmt
= NULL
;
3882 laststmt
.len
= NULL_TREE
;
3883 laststmt
.stridx
= 0;
3885 if (strlen_to_stridx
)
3887 strlen_to_stridx
->empty ();
3888 delete strlen_to_stridx
;
3889 strlen_to_stridx
= NULL
;
3892 return walker
.m_cleanup_cfg
? TODO_cleanup_cfg
: 0;
3898 make_pass_strlen (gcc::context
*ctxt
)
3900 return new pass_strlen (ctxt
);