1 /* String length optimization
2 Copyright (C) 2011-2018 Free Software Foundation, Inc.
3 Contributed by Jakub Jelinek <jakub@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "alloc-pool.h"
29 #include "tree-pass.h"
32 #include "gimple-pretty-print.h"
33 #include "gimple-ssa-warn-restrict.h"
34 #include "fold-const.h"
35 #include "stor-layout.h"
36 #include "gimple-fold.h"
39 #include "gimple-iterator.h"
40 #include "gimplify-me.h"
45 #include "tree-ssa-alias.h"
46 #include "tree-ssa-propagate.h"
47 #include "tree-ssa-strlen.h"
49 #include "tree-hash-traits.h"
50 #include "tree-object-size.h"
53 #include "diagnostic-core.h"
54 #include "diagnostic.h"
59 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
60 is an index into strinfo vector, negative value stands for
61 string length of a string literal (~strlen). */
62 static vec
<int> ssa_ver_to_stridx
;
64 /* Number of currently active string indexes plus one. */
65 static int max_stridx
;
67 /* String information record. */
70 /* Number of leading characters that are known to be nonzero. This is
71 also the length of the string if FULL_STRING_P.
73 The values in a list of related string pointers must be consistent;
74 that is, if strinfo B comes X bytes after strinfo A, it must be
75 the case that A->nonzero_chars == X + B->nonzero_chars. */
77 /* Any of the corresponding pointers for querying alias oracle. */
79 /* This is used for two things:
81 - To record the statement that should be used for delayed length
82 computations. We maintain the invariant that all related strinfos
83 have delayed lengths or none do.
85 - To record the malloc or calloc call that produced this result. */
87 /* Pointer to '\0' if known, if NULL, it can be computed as
90 /* Reference count. Any changes to strinfo entry possibly shared
91 with dominating basic blocks need unshare_strinfo first, except
92 for dont_invalidate which affects only the immediately next
95 /* Copy of index. get_strinfo (si->idx) should return si; */
97 /* These 3 fields are for chaining related string pointers together.
99 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
100 strcpy (c, d); e = c + dl;
101 strinfo(a) -> strinfo(c) -> strinfo(e)
102 All have ->first field equal to strinfo(a)->idx and are doubly
103 chained through prev/next fields. The later strinfos are required
104 to point into the same string with zero or more bytes after
105 the previous pointer and all bytes in between the two pointers
106 must be non-zero. Functions like strcpy or memcpy are supposed
107 to adjust all previous strinfo lengths, but not following strinfo
108 lengths (those are uncertain, usually invalidated during
109 maybe_invalidate, except when the alias oracle knows better).
110 Functions like strcat on the other side adjust the whole
111 related strinfo chain.
112 They are updated lazily, so to use the chain the same first fields
113 and si->prev->next == si->idx needs to be verified. */
117 /* A flag whether the string is known to be written in the current
120 /* A flag for the next maybe_invalidate that this strinfo shouldn't
121 be invalidated. Always cleared by maybe_invalidate. */
122 bool dont_invalidate
;
123 /* True if the string is known to be nul-terminated after NONZERO_CHARS
124 characters. False is useful when detecting strings that are built
125 up via successive memcpys. */
129 /* Pool for allocating strinfo_struct entries. */
130 static object_allocator
<strinfo
> strinfo_pool ("strinfo pool");
132 /* Vector mapping positive string indexes to strinfo, for the
133 current basic block. The first pointer in the vector is special,
134 it is either NULL, meaning the vector isn't shared, or it is
135 a basic block pointer to the owner basic_block if shared.
136 If some other bb wants to modify the vector, the vector needs
137 to be unshared first, and only the owner bb is supposed to free it. */
138 static vec
<strinfo
*, va_heap
, vl_embed
> *stridx_to_strinfo
;
140 /* One OFFSET->IDX mapping. */
143 struct stridxlist
*next
;
144 HOST_WIDE_INT offset
;
148 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
149 struct decl_stridxlist_map
151 struct tree_map_base base
;
152 struct stridxlist list
;
155 /* Hash table for mapping decls to a chained list of offset -> idx
157 static hash_map
<tree_decl_hash
, stridxlist
> *decl_to_stridxlist_htab
;
159 /* Hash table mapping strlen calls to stridx instances describing
160 the calls' arguments. Non-null only when warn_stringop_truncation
162 typedef std::pair
<int, location_t
> stridx_strlenloc
;
163 static hash_map
<tree
, stridx_strlenloc
> *strlen_to_stridx
;
165 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
166 static struct obstack stridx_obstack
;
168 /* Last memcpy statement if it could be adjusted if the trailing
169 '\0' written is immediately overwritten, or
170 *x = '\0' store that could be removed if it is immediately overwritten. */
171 struct laststmt_struct
178 static int get_stridx_plus_constant (strinfo
*, unsigned HOST_WIDE_INT
, tree
);
179 static void handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*);
183 - 1 if SI is known to start with more than OFF nonzero characters.
185 - 0 if SI is known to start with OFF nonzero characters,
186 but is not known to start with more.
188 - -1 if SI might not start with OFF nonzero characters. */
191 compare_nonzero_chars (strinfo
*si
, unsigned HOST_WIDE_INT off
)
193 if (si
->nonzero_chars
194 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
195 return compare_tree_int (si
->nonzero_chars
, off
);
200 /* Return true if SI is known to be a zero-length string. */
203 zero_length_string_p (strinfo
*si
)
205 return si
->full_string_p
&& integer_zerop (si
->nonzero_chars
);
208 /* Return strinfo vector entry IDX. */
210 static inline strinfo
*
211 get_strinfo (int idx
)
213 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
215 return (*stridx_to_strinfo
)[idx
];
218 /* Get the next strinfo in the chain after SI, or null if none. */
220 static inline strinfo
*
221 get_next_strinfo (strinfo
*si
)
225 strinfo
*nextsi
= get_strinfo (si
->next
);
226 if (nextsi
== NULL
|| nextsi
->first
!= si
->first
|| nextsi
->prev
!= si
->idx
)
231 /* Helper function for get_stridx. Return the strinfo index of the address
232 of EXP, which is available in PTR if nonnull. If OFFSET_OUT, it is
233 OK to return the index for some X <= &EXP and store &EXP - X in
237 get_addr_stridx (tree exp
, tree ptr
, unsigned HOST_WIDE_INT
*offset_out
)
240 struct stridxlist
*list
, *last
= NULL
;
243 if (!decl_to_stridxlist_htab
)
247 base
= get_addr_base_and_unit_offset (exp
, &poff
);
248 if (base
== NULL
|| !DECL_P (base
) || !poff
.is_constant (&off
))
251 list
= decl_to_stridxlist_htab
->get (base
);
257 if (list
->offset
== off
)
263 if (list
->offset
> off
)
270 if ((offset_out
|| ptr
) && last
&& last
->idx
> 0)
272 unsigned HOST_WIDE_INT rel_off
273 = (unsigned HOST_WIDE_INT
) off
- last
->offset
;
274 strinfo
*si
= get_strinfo (last
->idx
);
275 if (si
&& compare_nonzero_chars (si
, rel_off
) >= 0)
279 *offset_out
= rel_off
;
283 return get_stridx_plus_constant (si
, rel_off
, ptr
);
289 /* Return string index for EXP. */
292 get_stridx (tree exp
)
296 if (TREE_CODE (exp
) == SSA_NAME
)
298 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)])
299 return ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)];
302 HOST_WIDE_INT off
= 0;
303 for (i
= 0; i
< 5; i
++)
305 gimple
*def_stmt
= SSA_NAME_DEF_STMT (e
);
306 if (!is_gimple_assign (def_stmt
)
307 || gimple_assign_rhs_code (def_stmt
) != POINTER_PLUS_EXPR
)
309 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
310 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
311 if (TREE_CODE (rhs1
) != SSA_NAME
312 || !tree_fits_shwi_p (rhs2
))
314 HOST_WIDE_INT this_off
= tree_to_shwi (rhs2
);
317 off
= (unsigned HOST_WIDE_INT
) off
+ this_off
;
320 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)])
323 = get_strinfo (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)]);
324 if (si
&& compare_nonzero_chars (si
, off
) >= 0)
325 return get_stridx_plus_constant (si
, off
, exp
);
332 if (TREE_CODE (exp
) == ADDR_EXPR
)
334 int idx
= get_addr_stridx (TREE_OPERAND (exp
, 0), exp
, NULL
);
339 s
= string_constant (exp
, &o
);
341 && (o
== NULL_TREE
|| tree_fits_shwi_p (o
))
342 && TREE_STRING_LENGTH (s
) > 0)
344 HOST_WIDE_INT offset
= o
? tree_to_shwi (o
) : 0;
345 const char *p
= TREE_STRING_POINTER (s
);
346 int max
= TREE_STRING_LENGTH (s
) - 1;
348 if (p
[max
] == '\0' && offset
>= 0 && offset
<= max
)
349 return ~(int) strlen (p
+ offset
);
354 /* Return true if strinfo vector is shared with the immediate dominator. */
357 strinfo_shared (void)
359 return vec_safe_length (stridx_to_strinfo
)
360 && (*stridx_to_strinfo
)[0] != NULL
;
363 /* Unshare strinfo vector that is shared with the immediate dominator. */
366 unshare_strinfo_vec (void)
371 gcc_assert (strinfo_shared ());
372 stridx_to_strinfo
= vec_safe_copy (stridx_to_strinfo
);
373 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
376 (*stridx_to_strinfo
)[0] = NULL
;
379 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
380 Return a pointer to the location where the string index can
381 be stored (if 0) or is stored, or NULL if this can't be tracked. */
384 addr_stridxptr (tree exp
)
389 tree base
= get_addr_base_and_unit_offset (exp
, &poff
);
390 if (base
== NULL_TREE
|| !DECL_P (base
) || !poff
.is_constant (&off
))
393 if (!decl_to_stridxlist_htab
)
395 decl_to_stridxlist_htab
396 = new hash_map
<tree_decl_hash
, stridxlist
> (64);
397 gcc_obstack_init (&stridx_obstack
);
401 stridxlist
*list
= &decl_to_stridxlist_htab
->get_or_insert (base
, &existed
);
405 stridxlist
*before
= NULL
;
406 for (i
= 0; i
< 32; i
++)
408 if (list
->offset
== off
)
410 if (list
->offset
> off
&& before
== NULL
)
412 if (list
->next
== NULL
)
421 before
= XOBNEW (&stridx_obstack
, struct stridxlist
);
428 list
->next
= XOBNEW (&stridx_obstack
, struct stridxlist
);
438 /* Create a new string index, or return 0 if reached limit. */
441 new_stridx (tree exp
)
444 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
446 if (TREE_CODE (exp
) == SSA_NAME
)
448 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
451 ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)] = idx
;
454 if (TREE_CODE (exp
) == ADDR_EXPR
)
456 int *pidx
= addr_stridxptr (TREE_OPERAND (exp
, 0));
459 gcc_assert (*pidx
== 0);
460 *pidx
= max_stridx
++;
467 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
470 new_addr_stridx (tree exp
)
473 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
475 pidx
= addr_stridxptr (exp
);
478 gcc_assert (*pidx
== 0);
479 *pidx
= max_stridx
++;
485 /* Create a new strinfo. */
488 new_strinfo (tree ptr
, int idx
, tree nonzero_chars
, bool full_string_p
)
490 strinfo
*si
= strinfo_pool
.allocate ();
491 si
->nonzero_chars
= nonzero_chars
;
494 si
->endptr
= NULL_TREE
;
500 si
->writable
= false;
501 si
->dont_invalidate
= false;
502 si
->full_string_p
= full_string_p
;
506 /* Decrease strinfo refcount and free it if not referenced anymore. */
509 free_strinfo (strinfo
*si
)
511 if (si
&& --si
->refcount
== 0)
512 strinfo_pool
.remove (si
);
515 /* Set strinfo in the vector entry IDX to SI. */
518 set_strinfo (int idx
, strinfo
*si
)
520 if (vec_safe_length (stridx_to_strinfo
) && (*stridx_to_strinfo
)[0])
521 unshare_strinfo_vec ();
522 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
523 vec_safe_grow_cleared (stridx_to_strinfo
, idx
+ 1);
524 (*stridx_to_strinfo
)[idx
] = si
;
527 /* Return the first strinfo in the related strinfo chain
528 if all strinfos in between belong to the chain, otherwise NULL. */
531 verify_related_strinfos (strinfo
*origsi
)
533 strinfo
*si
= origsi
, *psi
;
535 if (origsi
->first
== 0)
537 for (; si
->prev
; si
= psi
)
539 if (si
->first
!= origsi
->first
)
541 psi
= get_strinfo (si
->prev
);
544 if (psi
->next
!= si
->idx
)
547 if (si
->idx
!= si
->first
)
552 /* Set SI's endptr to ENDPTR and compute its length based on SI->ptr.
553 Use LOC for folding. */
556 set_endptr_and_length (location_t loc
, strinfo
*si
, tree endptr
)
560 tree start_as_size
= fold_convert_loc (loc
, size_type_node
, si
->ptr
);
561 tree end_as_size
= fold_convert_loc (loc
, size_type_node
, endptr
);
562 si
->nonzero_chars
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
563 end_as_size
, start_as_size
);
564 si
->full_string_p
= true;
567 /* Return string length, or NULL if it can't be computed. */
570 get_string_length (strinfo
*si
)
572 if (si
->nonzero_chars
)
573 return si
->full_string_p
? si
->nonzero_chars
: NULL
;
577 gimple
*stmt
= si
->stmt
, *lenstmt
;
578 tree callee
, lhs
, fn
, tem
;
580 gimple_stmt_iterator gsi
;
582 gcc_assert (is_gimple_call (stmt
));
583 callee
= gimple_call_fndecl (stmt
);
584 gcc_assert (callee
&& DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
);
585 lhs
= gimple_call_lhs (stmt
);
586 /* unshare_strinfo is intentionally not called here. The (delayed)
587 transformation of strcpy or strcat into stpcpy is done at the place
588 of the former strcpy/strcat call and so can affect all the strinfos
589 with the same stmt. If they were unshared before and transformation
590 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
591 just compute the right length. */
592 switch (DECL_FUNCTION_CODE (callee
))
594 case BUILT_IN_STRCAT
:
595 case BUILT_IN_STRCAT_CHK
:
596 gsi
= gsi_for_stmt (stmt
);
597 fn
= builtin_decl_implicit (BUILT_IN_STRLEN
);
598 gcc_assert (lhs
== NULL_TREE
);
599 tem
= unshare_expr (gimple_call_arg (stmt
, 0));
600 lenstmt
= gimple_build_call (fn
, 1, tem
);
601 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), lenstmt
);
602 gimple_call_set_lhs (lenstmt
, lhs
);
603 gimple_set_vuse (lenstmt
, gimple_vuse (stmt
));
604 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
605 tem
= gimple_call_arg (stmt
, 0);
606 if (!ptrofftype_p (TREE_TYPE (lhs
)))
608 lhs
= convert_to_ptrofftype (lhs
);
609 lhs
= force_gimple_operand_gsi (&gsi
, lhs
, true, NULL_TREE
,
610 true, GSI_SAME_STMT
);
612 lenstmt
= gimple_build_assign
613 (make_ssa_name (TREE_TYPE (gimple_call_arg (stmt
, 0))),
614 POINTER_PLUS_EXPR
,tem
, lhs
);
615 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
616 gimple_call_set_arg (stmt
, 0, gimple_assign_lhs (lenstmt
));
619 case BUILT_IN_STRCPY
:
620 case BUILT_IN_STRCPY_CHK
:
621 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY
));
622 if (gimple_call_num_args (stmt
) == 2)
623 fn
= builtin_decl_implicit (BUILT_IN_STPCPY
);
625 fn
= builtin_decl_explicit (BUILT_IN_STPCPY_CHK
);
626 gcc_assert (lhs
== NULL_TREE
);
627 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
629 fprintf (dump_file
, "Optimizing: ");
630 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
632 gimple_call_set_fndecl (stmt
, fn
);
633 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), stmt
);
634 gimple_call_set_lhs (stmt
, lhs
);
636 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
638 fprintf (dump_file
, "into: ");
639 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
642 case BUILT_IN_STPCPY
:
643 case BUILT_IN_STPCPY_CHK
:
644 gcc_assert (lhs
!= NULL_TREE
);
645 loc
= gimple_location (stmt
);
646 set_endptr_and_length (loc
, si
, lhs
);
647 for (strinfo
*chainsi
= verify_related_strinfos (si
);
649 chainsi
= get_next_strinfo (chainsi
))
650 if (chainsi
->nonzero_chars
== NULL
)
651 set_endptr_and_length (loc
, chainsi
, lhs
);
653 case BUILT_IN_MALLOC
:
655 /* BUILT_IN_CALLOC always has si->nonzero_chars set. */
662 return si
->nonzero_chars
;
665 /* Invalidate string length information for strings whose length
666 might change due to stores in stmt. */
669 maybe_invalidate (gimple
*stmt
)
673 bool nonempty
= false;
675 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
678 if (!si
->dont_invalidate
)
681 /* Do not use si->nonzero_chars. */
682 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, NULL_TREE
);
683 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
685 set_strinfo (i
, NULL
);
690 si
->dont_invalidate
= false;
696 /* Unshare strinfo record SI, if it has refcount > 1 or
697 if stridx_to_strinfo vector is shared with some other
701 unshare_strinfo (strinfo
*si
)
705 if (si
->refcount
== 1 && !strinfo_shared ())
708 nsi
= new_strinfo (si
->ptr
, si
->idx
, si
->nonzero_chars
, si
->full_string_p
);
709 nsi
->stmt
= si
->stmt
;
710 nsi
->endptr
= si
->endptr
;
711 nsi
->first
= si
->first
;
712 nsi
->prev
= si
->prev
;
713 nsi
->next
= si
->next
;
714 nsi
->writable
= si
->writable
;
715 set_strinfo (si
->idx
, nsi
);
720 /* Attempt to create a new strinfo for BASESI + OFF, or find existing
721 strinfo if there is any. Return it's idx, or 0 if no strinfo has
725 get_stridx_plus_constant (strinfo
*basesi
, unsigned HOST_WIDE_INT off
,
728 if (TREE_CODE (ptr
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
731 if (compare_nonzero_chars (basesi
, off
) < 0
732 || !tree_fits_uhwi_p (basesi
->nonzero_chars
))
735 unsigned HOST_WIDE_INT nonzero_chars
736 = tree_to_uhwi (basesi
->nonzero_chars
) - off
;
737 strinfo
*si
= basesi
, *chainsi
;
738 if (si
->first
|| si
->prev
|| si
->next
)
739 si
= verify_related_strinfos (basesi
);
741 || si
->nonzero_chars
== NULL_TREE
742 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
745 if (TREE_CODE (ptr
) == SSA_NAME
746 && ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
747 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
749 gcc_checking_assert (compare_tree_int (si
->nonzero_chars
, off
) != -1);
750 for (chainsi
= si
; chainsi
->next
; chainsi
= si
)
752 si
= get_next_strinfo (chainsi
);
754 || si
->nonzero_chars
== NULL_TREE
755 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
757 int r
= compare_tree_int (si
->nonzero_chars
, nonzero_chars
);
762 if (TREE_CODE (ptr
) == SSA_NAME
)
763 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = si
->idx
;
766 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
767 if (pidx
!= NULL
&& *pidx
== 0)
776 int idx
= new_stridx (ptr
);
779 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, nonzero_chars
),
780 basesi
->full_string_p
);
781 set_strinfo (idx
, si
);
782 if (strinfo
*nextsi
= get_strinfo (chainsi
->next
))
784 nextsi
= unshare_strinfo (nextsi
);
785 si
->next
= nextsi
->idx
;
788 chainsi
= unshare_strinfo (chainsi
);
789 if (chainsi
->first
== 0)
790 chainsi
->first
= chainsi
->idx
;
792 if (chainsi
->endptr
== NULL_TREE
&& zero_length_string_p (si
))
793 chainsi
->endptr
= ptr
;
794 si
->endptr
= chainsi
->endptr
;
795 si
->prev
= chainsi
->idx
;
796 si
->first
= chainsi
->first
;
797 si
->writable
= chainsi
->writable
;
801 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
802 to a zero-length string and if possible chain it to a related strinfo
803 chain whose part is or might be CHAINSI. */
806 zero_length_string (tree ptr
, strinfo
*chainsi
)
810 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
811 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
812 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
813 && ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] == 0);
815 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
819 si
= verify_related_strinfos (chainsi
);
824 /* We shouldn't mix delayed and non-delayed lengths. */
825 gcc_assert (si
->full_string_p
);
826 if (si
->endptr
== NULL_TREE
)
828 si
= unshare_strinfo (si
);
832 si
= get_next_strinfo (si
);
835 if (zero_length_string_p (chainsi
))
839 chainsi
= unshare_strinfo (chainsi
);
842 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = chainsi
->idx
;
848 /* We shouldn't mix delayed and non-delayed lengths. */
849 gcc_assert (chainsi
->full_string_p
);
850 if (chainsi
->first
|| chainsi
->prev
|| chainsi
->next
)
852 chainsi
= unshare_strinfo (chainsi
);
859 idx
= new_stridx (ptr
);
862 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, 0), true);
863 set_strinfo (idx
, si
);
867 chainsi
= unshare_strinfo (chainsi
);
868 if (chainsi
->first
== 0)
869 chainsi
->first
= chainsi
->idx
;
871 if (chainsi
->endptr
== NULL_TREE
)
872 chainsi
->endptr
= ptr
;
873 si
->prev
= chainsi
->idx
;
874 si
->first
= chainsi
->first
;
875 si
->writable
= chainsi
->writable
;
880 /* For strinfo ORIGSI whose length has been just updated, adjust other
881 related strinfos so that they match the new ORIGSI. This involves:
883 - adding ADJ to the nonzero_chars fields
884 - copying full_string_p from the new ORIGSI. */
887 adjust_related_strinfos (location_t loc
, strinfo
*origsi
, tree adj
)
889 strinfo
*si
= verify_related_strinfos (origsi
);
902 si
= unshare_strinfo (si
);
903 /* We shouldn't see delayed lengths here; the caller must have
904 calculated the old length in order to calculate the
906 gcc_assert (si
->nonzero_chars
);
907 tem
= fold_convert_loc (loc
, TREE_TYPE (si
->nonzero_chars
), adj
);
908 si
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
909 TREE_TYPE (si
->nonzero_chars
),
910 si
->nonzero_chars
, tem
);
911 si
->full_string_p
= origsi
->full_string_p
;
913 si
->endptr
= NULL_TREE
;
914 si
->dont_invalidate
= true;
916 nsi
= get_next_strinfo (si
);
923 /* Find if there are other SSA_NAME pointers equal to PTR
924 for which we don't track their string lengths yet. If so, use
928 find_equal_ptrs (tree ptr
, int idx
)
930 if (TREE_CODE (ptr
) != SSA_NAME
)
934 gimple
*stmt
= SSA_NAME_DEF_STMT (ptr
);
935 if (!is_gimple_assign (stmt
))
937 ptr
= gimple_assign_rhs1 (stmt
);
938 switch (gimple_assign_rhs_code (stmt
))
943 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)))
945 if (TREE_CODE (ptr
) == SSA_NAME
)
947 if (TREE_CODE (ptr
) != ADDR_EXPR
)
952 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
953 if (pidx
!= NULL
&& *pidx
== 0)
961 /* We might find an endptr created in this pass. Grow the
962 vector in that case. */
963 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
964 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
966 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] != 0)
968 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = idx
;
972 /* Return true if STMT is a call to a builtin function with the right
973 arguments and attributes that should be considered for optimization
977 valid_builtin_call (gimple
*stmt
)
979 if (!gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
982 tree callee
= gimple_call_fndecl (stmt
);
983 switch (DECL_FUNCTION_CODE (callee
))
985 case BUILT_IN_MEMCMP
:
986 case BUILT_IN_MEMCMP_EQ
:
987 case BUILT_IN_STRCHR
:
988 case BUILT_IN_STRLEN
:
989 /* The above functions should be pure. Punt if they aren't. */
990 if (gimple_vdef (stmt
) || gimple_vuse (stmt
) == NULL_TREE
)
994 case BUILT_IN_CALLOC
:
995 case BUILT_IN_MALLOC
:
996 case BUILT_IN_MEMCPY
:
997 case BUILT_IN_MEMCPY_CHK
:
998 case BUILT_IN_MEMPCPY
:
999 case BUILT_IN_MEMPCPY_CHK
:
1000 case BUILT_IN_MEMSET
:
1001 case BUILT_IN_STPCPY
:
1002 case BUILT_IN_STPCPY_CHK
:
1003 case BUILT_IN_STRCAT
:
1004 case BUILT_IN_STRCAT_CHK
:
1005 case BUILT_IN_STRCPY
:
1006 case BUILT_IN_STRCPY_CHK
:
1007 /* The above functions should be neither const nor pure. Punt if they
1009 if (gimple_vdef (stmt
) == NULL_TREE
|| gimple_vuse (stmt
) == NULL_TREE
)
1020 /* If the last .MEM setter statement before STMT is
1021 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
1022 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
1023 just memcpy (x, y, strlen (y)). SI must be the zero length
1027 adjust_last_stmt (strinfo
*si
, gimple
*stmt
, bool is_strcat
)
1029 tree vuse
, callee
, len
;
1030 struct laststmt_struct last
= laststmt
;
1031 strinfo
*lastsi
, *firstsi
;
1032 unsigned len_arg_no
= 2;
1034 laststmt
.stmt
= NULL
;
1035 laststmt
.len
= NULL_TREE
;
1036 laststmt
.stridx
= 0;
1038 if (last
.stmt
== NULL
)
1041 vuse
= gimple_vuse (stmt
);
1042 if (vuse
== NULL_TREE
1043 || SSA_NAME_DEF_STMT (vuse
) != last
.stmt
1044 || !has_single_use (vuse
))
1047 gcc_assert (last
.stridx
> 0);
1048 lastsi
= get_strinfo (last
.stridx
);
1054 if (lastsi
->first
== 0 || lastsi
->first
!= si
->first
)
1057 firstsi
= verify_related_strinfos (si
);
1058 if (firstsi
== NULL
)
1060 while (firstsi
!= lastsi
)
1062 firstsi
= get_next_strinfo (firstsi
);
1063 if (firstsi
== NULL
)
1068 if (!is_strcat
&& !zero_length_string_p (si
))
1071 if (is_gimple_assign (last
.stmt
))
1073 gimple_stmt_iterator gsi
;
1075 if (!integer_zerop (gimple_assign_rhs1 (last
.stmt
)))
1077 if (stmt_could_throw_p (last
.stmt
))
1079 gsi
= gsi_for_stmt (last
.stmt
);
1080 unlink_stmt_vdef (last
.stmt
);
1081 release_defs (last
.stmt
);
1082 gsi_remove (&gsi
, true);
1086 if (!valid_builtin_call (last
.stmt
))
1089 callee
= gimple_call_fndecl (last
.stmt
);
1090 switch (DECL_FUNCTION_CODE (callee
))
1092 case BUILT_IN_MEMCPY
:
1093 case BUILT_IN_MEMCPY_CHK
:
1099 len
= gimple_call_arg (last
.stmt
, len_arg_no
);
1100 if (tree_fits_uhwi_p (len
))
1102 if (!tree_fits_uhwi_p (last
.len
)
1103 || integer_zerop (len
)
1104 || tree_to_uhwi (len
) != tree_to_uhwi (last
.len
) + 1)
1106 /* Don't adjust the length if it is divisible by 4, it is more efficient
1107 to store the extra '\0' in that case. */
1108 if ((tree_to_uhwi (len
) & 3) == 0)
1111 else if (TREE_CODE (len
) == SSA_NAME
)
1113 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1114 if (!is_gimple_assign (def_stmt
)
1115 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1116 || gimple_assign_rhs1 (def_stmt
) != last
.len
1117 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1123 gimple_call_set_arg (last
.stmt
, len_arg_no
, last
.len
);
1124 update_stmt (last
.stmt
);
1127 /* For an LHS that is an SSA_NAME and for strlen() or strnlen() argument
1128 SRC, set LHS range info to [0, min (N, BOUND)] if SRC refers to
1129 a character array A[N] with unknown length bounded by N, and for
1130 strnlen(), by min (N, BOUND). */
1133 maybe_set_strlen_range (tree lhs
, tree src
, tree bound
)
1135 if (TREE_CODE (lhs
) != SSA_NAME
1136 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
1139 if (TREE_CODE (src
) == SSA_NAME
)
1141 gimple
*def
= SSA_NAME_DEF_STMT (src
);
1142 if (is_gimple_assign (def
)
1143 && gimple_assign_rhs_code (def
) == ADDR_EXPR
)
1144 src
= gimple_assign_rhs1 (def
);
1147 wide_int max
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
));
1148 wide_int min
= wi::zero (max
.get_precision ());
1150 if (TREE_CODE (src
) == ADDR_EXPR
)
1152 /* The last array member of a struct can be bigger than its size
1153 suggests if it's treated as a poor-man's flexible array member. */
1154 src
= TREE_OPERAND (src
, 0);
1155 bool src_is_array
= TREE_CODE (TREE_TYPE (src
)) == ARRAY_TYPE
;
1156 if (src_is_array
&& !array_at_struct_end_p (src
))
1158 tree type
= TREE_TYPE (src
);
1159 if (tree size
= TYPE_SIZE_UNIT (type
))
1160 if (size
&& TREE_CODE (size
) == INTEGER_CST
)
1161 max
= wi::to_wide (size
);
1163 /* For strlen() the upper bound above is equal to
1164 the longest string that can be stored in the array
1165 (i.e., it accounts for the terminating nul. For
1166 strnlen() bump up the maximum by one since the array
1167 need not be nul-terminated. */
1168 if (!bound
&& max
!= 0)
1173 if (TREE_CODE (src
) == COMPONENT_REF
&& !src_is_array
)
1174 src
= TREE_OPERAND (src
, 1);
1177 /* Handle the unlikely case of strlen (&c) where c is some
1179 if (tree size
= DECL_SIZE_UNIT (src
))
1180 if (TREE_CODE (size
) == INTEGER_CST
)
1181 max
= wi::to_wide (size
);
1188 /* For strnlen, adjust MIN and MAX as necessary. If the bound
1189 is less than the size of the array set MAX to it. It it's
1190 greater than MAX and MAX is non-zero bump MAX down to account
1191 for the necessary terminating nul. Otherwise leave it alone. */
1192 if (TREE_CODE (bound
) == INTEGER_CST
)
1194 wide_int wibnd
= wi::to_wide (bound
);
1195 int cmp
= wi::cmpu (wibnd
, max
);
1198 else if (cmp
&& wi::ne_p (max
, min
))
1201 else if (TREE_CODE (bound
) == SSA_NAME
)
1203 wide_int minbound
, maxbound
;
1204 value_range_type rng
= get_range_info (bound
, &minbound
, &maxbound
);
1205 if (rng
== VR_RANGE
)
1207 /* For a bound in a known range, adjust the range determined
1208 above as necessary. For a bound in some anti-range or
1209 in an unknown range, use the range determined above. */
1210 if (wi::ltu_p (minbound
, min
))
1212 if (wi::ltu_p (maxbound
, max
))
1219 return wide_int_to_tree (size_type_node
, min
);
1221 set_range_info (lhs
, VR_RANGE
, min
, max
);
1225 /* Handle a strlen call. If strlen of the argument is known, replace
1226 the strlen call with the known value, otherwise remember that strlen
1227 of the argument is stored in the lhs SSA_NAME. */
1230 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
1232 gimple
*stmt
= gsi_stmt (*gsi
);
1233 tree lhs
= gimple_call_lhs (stmt
);
1235 if (lhs
== NULL_TREE
)
1238 location_t loc
= gimple_location (stmt
);
1239 tree callee
= gimple_call_fndecl (stmt
);
1240 tree src
= gimple_call_arg (stmt
, 0);
1241 tree bound
= (DECL_FUNCTION_CODE (callee
) == BUILT_IN_STRNLEN
1242 ? gimple_call_arg (stmt
, 1) : NULL_TREE
);
1243 int idx
= get_stridx (src
);
1250 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
1254 si
= get_strinfo (idx
);
1256 rhs
= get_string_length (si
);
1258 if (rhs
!= NULL_TREE
)
1260 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1262 fprintf (dump_file
, "Optimizing: ");
1263 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1265 rhs
= unshare_expr (rhs
);
1266 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
1267 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1269 /* Set for strnlen() calls with a non-constant bound. */
1270 bool noncst_bound
= false;
1274 = fold_build2_loc (loc
, MIN_EXPR
, TREE_TYPE (rhs
), rhs
, bound
);
1276 noncst_bound
= (TREE_CODE (new_rhs
) != INTEGER_CST
1277 || tree_int_cst_lt (new_rhs
, rhs
));
1282 if (!update_call_from_tree (gsi
, rhs
))
1283 gimplify_and_update_call_from_tree (gsi
, rhs
);
1284 stmt
= gsi_stmt (*gsi
);
1286 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1288 fprintf (dump_file
, "into: ");
1289 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1292 /* Avoid storing the length for calls to strnlen() with
1293 a non-constant bound. */
1298 && TREE_CODE (si
->nonzero_chars
) != SSA_NAME
1299 && TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
1300 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1302 si
= unshare_strinfo (si
);
1303 si
->nonzero_chars
= lhs
;
1304 gcc_assert (si
->full_string_p
);
1307 if (strlen_to_stridx
)
1308 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1313 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1317 idx
= new_stridx (src
);
1320 strinfo
*si
= get_strinfo (idx
);
1323 if (!si
->full_string_p
&& !si
->stmt
)
1325 /* Until now we only had a lower bound on the string length.
1326 Install LHS as the actual length. */
1327 si
= unshare_strinfo (si
);
1328 tree old
= si
->nonzero_chars
;
1329 si
->nonzero_chars
= lhs
;
1330 si
->full_string_p
= true;
1331 if (TREE_CODE (old
) == INTEGER_CST
)
1333 old
= fold_convert_loc (loc
, TREE_TYPE (lhs
), old
);
1334 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1335 TREE_TYPE (lhs
), lhs
, old
);
1336 adjust_related_strinfos (loc
, si
, adj
);
1352 /* Only store the new length information for calls to strlen(),
1353 not for those to strnlen(). */
1354 strinfo
*si
= new_strinfo (src
, idx
, lhs
, true);
1355 set_strinfo (idx
, si
);
1356 find_equal_ptrs (src
, idx
);
1359 /* For SRC that is an array of N elements, set LHS's range
1360 to [0, min (N, BOUND)]. A constant return value means
1361 the range would have consisted of a single value. In
1362 that case, fold the result into the returned constant. */
1363 if (tree ret
= maybe_set_strlen_range (lhs
, src
, bound
))
1364 if (TREE_CODE (ret
) == INTEGER_CST
)
1366 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1368 fprintf (dump_file
, "Optimizing: ");
1369 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1371 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (ret
)))
1372 ret
= fold_convert_loc (loc
, TREE_TYPE (lhs
), ret
);
1373 if (!update_call_from_tree (gsi
, ret
))
1374 gimplify_and_update_call_from_tree (gsi
, ret
);
1375 stmt
= gsi_stmt (*gsi
);
1377 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1379 fprintf (dump_file
, "into: ");
1380 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1384 if (strlen_to_stridx
&& !bound
)
1385 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1389 /* Handle a strchr call. If strlen of the first argument is known, replace
1390 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
1391 that lhs of the call is endptr and strlen of the argument is endptr - x. */
1394 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
1398 gimple
*stmt
= gsi_stmt (*gsi
);
1399 tree lhs
= gimple_call_lhs (stmt
);
1401 if (lhs
== NULL_TREE
)
1404 if (!integer_zerop (gimple_call_arg (stmt
, 1)))
1407 src
= gimple_call_arg (stmt
, 0);
1408 idx
= get_stridx (src
);
1415 rhs
= build_int_cst (size_type_node
, ~idx
);
1419 si
= get_strinfo (idx
);
1421 rhs
= get_string_length (si
);
1423 if (rhs
!= NULL_TREE
)
1425 location_t loc
= gimple_location (stmt
);
1427 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1429 fprintf (dump_file
, "Optimizing: ");
1430 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1432 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
1434 rhs
= unshare_expr (si
->endptr
);
1435 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1437 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1441 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1442 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1443 TREE_TYPE (src
), src
, rhs
);
1444 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1446 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1448 if (!update_call_from_tree (gsi
, rhs
))
1449 gimplify_and_update_call_from_tree (gsi
, rhs
);
1450 stmt
= gsi_stmt (*gsi
);
1452 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1454 fprintf (dump_file
, "into: ");
1455 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1458 && si
->endptr
== NULL_TREE
1459 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1461 si
= unshare_strinfo (si
);
1464 zero_length_string (lhs
, si
);
1468 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1470 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1473 idx
= new_stridx (src
);
1474 else if (get_strinfo (idx
) != NULL
)
1476 zero_length_string (lhs
, NULL
);
1481 location_t loc
= gimple_location (stmt
);
1482 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1483 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1484 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1485 size_type_node
, lhsu
, srcu
);
1486 strinfo
*si
= new_strinfo (src
, idx
, length
, true);
1488 set_strinfo (idx
, si
);
1489 find_equal_ptrs (src
, idx
);
1490 zero_length_string (lhs
, si
);
1494 zero_length_string (lhs
, NULL
);
1497 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1498 If strlen of the second argument is known, strlen of the first argument
1499 is the same after this call. Furthermore, attempt to convert it to
1503 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1506 tree src
, dst
, srclen
, len
, lhs
, type
, fn
, oldlen
;
1508 gimple
*stmt
= gsi_stmt (*gsi
);
1509 strinfo
*si
, *dsi
, *olddsi
, *zsi
;
1512 src
= gimple_call_arg (stmt
, 1);
1513 dst
= gimple_call_arg (stmt
, 0);
1514 lhs
= gimple_call_lhs (stmt
);
1515 idx
= get_stridx (src
);
1518 si
= get_strinfo (idx
);
1520 didx
= get_stridx (dst
);
1524 olddsi
= get_strinfo (didx
);
1529 adjust_last_stmt (olddsi
, stmt
, false);
1533 srclen
= get_string_length (si
);
1535 srclen
= build_int_cst (size_type_node
, ~idx
);
1537 loc
= gimple_location (stmt
);
1538 if (srclen
== NULL_TREE
)
1541 case BUILT_IN_STRCPY
:
1542 case BUILT_IN_STRCPY_CHK
:
1543 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1546 case BUILT_IN_STPCPY
:
1547 case BUILT_IN_STPCPY_CHK
:
1548 if (lhs
== NULL_TREE
)
1552 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1553 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1554 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1564 didx
= new_stridx (dst
);
1570 oldlen
= olddsi
->nonzero_chars
;
1571 dsi
= unshare_strinfo (olddsi
);
1572 dsi
->nonzero_chars
= srclen
;
1573 dsi
->full_string_p
= (srclen
!= NULL_TREE
);
1574 /* Break the chain, so adjust_related_strinfo on later pointers in
1575 the chain won't adjust this one anymore. */
1578 dsi
->endptr
= NULL_TREE
;
1582 dsi
= new_strinfo (dst
, didx
, srclen
, srclen
!= NULL_TREE
);
1583 set_strinfo (didx
, dsi
);
1584 find_equal_ptrs (dst
, didx
);
1586 dsi
->writable
= true;
1587 dsi
->dont_invalidate
= true;
1589 if (dsi
->nonzero_chars
== NULL_TREE
)
1593 /* If string length of src is unknown, use delayed length
1594 computation. If string lenth of dst will be needed, it
1595 can be computed by transforming this strcpy call into
1596 stpcpy and subtracting dst from the return value. */
1598 /* Look for earlier strings whose length could be determined if
1599 this strcpy is turned into an stpcpy. */
1601 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1603 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1605 /* When setting a stmt for delayed length computation
1606 prevent all strinfos through dsi from being
1608 chainsi
= unshare_strinfo (chainsi
);
1609 chainsi
->stmt
= stmt
;
1610 chainsi
->nonzero_chars
= NULL_TREE
;
1611 chainsi
->full_string_p
= false;
1612 chainsi
->endptr
= NULL_TREE
;
1613 chainsi
->dont_invalidate
= true;
1618 /* Try to detect overlap before returning. This catches cases
1619 like strcpy (d, d + n) where n is non-constant whose range
1620 is such that (n <= strlen (d) holds).
1622 OLDDSI->NONZERO_chars may have been reset by this point with
1623 oldlen holding it original value. */
1624 if (olddsi
&& oldlen
)
1626 /* Add 1 for the terminating NUL. */
1627 tree type
= TREE_TYPE (oldlen
);
1628 oldlen
= fold_build2 (PLUS_EXPR
, type
, oldlen
,
1629 build_int_cst (type
, 1));
1630 check_bounds_or_overlap (as_a
<gcall
*>(stmt
), olddsi
->ptr
, src
,
1639 tree adj
= NULL_TREE
;
1640 if (oldlen
== NULL_TREE
)
1642 else if (integer_zerop (oldlen
))
1644 else if (TREE_CODE (oldlen
) == INTEGER_CST
1645 || TREE_CODE (srclen
) == INTEGER_CST
)
1646 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1647 TREE_TYPE (srclen
), srclen
,
1648 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1650 if (adj
!= NULL_TREE
)
1651 adjust_related_strinfos (loc
, dsi
, adj
);
1655 /* strcpy src may not overlap dst, so src doesn't need to be
1656 invalidated either. */
1658 si
->dont_invalidate
= true;
1664 case BUILT_IN_STRCPY
:
1665 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1667 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1669 case BUILT_IN_STRCPY_CHK
:
1670 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1672 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1674 case BUILT_IN_STPCPY
:
1675 /* This would need adjustment of the lhs (subtract one),
1676 or detection that the trailing '\0' doesn't need to be
1677 written, if it will be immediately overwritten.
1678 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1682 zsi
= zero_length_string (lhs
, dsi
);
1685 case BUILT_IN_STPCPY_CHK
:
1686 /* This would need adjustment of the lhs (subtract one),
1687 or detection that the trailing '\0' doesn't need to be
1688 written, if it will be immediately overwritten.
1689 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1693 zsi
= zero_length_string (lhs
, dsi
);
1700 zsi
->dont_invalidate
= true;
1704 tree args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1705 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1708 type
= size_type_node
;
1710 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1711 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1713 /* Set the no-warning bit on the transformed statement? */
1714 bool set_no_warning
= false;
1716 if (const strinfo
*chksi
= olddsi
? olddsi
: dsi
)
1718 && !check_bounds_or_overlap (as_a
<gcall
*>(stmt
), chksi
->ptr
, si
->ptr
,
1721 gimple_set_no_warning (stmt
, true);
1722 set_no_warning
= true;
1725 if (fn
== NULL_TREE
)
1728 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1730 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1732 fprintf (dump_file
, "Optimizing: ");
1733 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1735 if (gimple_call_num_args (stmt
) == 2)
1736 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1738 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1739 gimple_call_arg (stmt
, 2));
1742 stmt
= gsi_stmt (*gsi
);
1744 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1746 fprintf (dump_file
, "into: ");
1747 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1749 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1750 laststmt
.stmt
= stmt
;
1751 laststmt
.len
= srclen
;
1752 laststmt
.stridx
= dsi
->idx
;
1754 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1755 fprintf (dump_file
, "not possible.\n");
1758 gimple_set_no_warning (stmt
, true);
1761 /* Check the size argument to the built-in forms of stpncpy and strncpy
1762 for out-of-bounds offsets or overlapping access, and to see if the
1763 size argument is derived from a call to strlen() on the source argument,
1764 and if so, issue an appropriate warning. */
1767 handle_builtin_strncat (built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1769 /* Same as stxncpy(). */
1770 handle_builtin_stxncpy (bcode
, gsi
);
1773 /* Return true if LEN depends on a call to strlen(SRC) in an interesting
1774 way. LEN can either be an integer expression, or a pointer (to char).
1775 When it is the latter (such as in recursive calls to self) is is
1776 assumed to be the argument in some call to strlen() whose relationship
1777 to SRC is being ascertained. */
1780 is_strlen_related_p (tree src
, tree len
)
1782 if (TREE_CODE (TREE_TYPE (len
)) == POINTER_TYPE
1783 && operand_equal_p (src
, len
, 0))
1786 if (TREE_CODE (len
) != SSA_NAME
)
1789 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1793 if (is_gimple_call (def_stmt
))
1795 tree func
= gimple_call_fndecl (def_stmt
);
1796 if (!valid_builtin_call (def_stmt
)
1797 || DECL_FUNCTION_CODE (func
) != BUILT_IN_STRLEN
)
1800 tree arg
= gimple_call_arg (def_stmt
, 0);
1801 return is_strlen_related_p (src
, arg
);
1804 if (!is_gimple_assign (def_stmt
))
1807 tree_code code
= gimple_assign_rhs_code (def_stmt
);
1808 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1809 tree rhstype
= TREE_TYPE (rhs1
);
1811 if ((TREE_CODE (rhstype
) == POINTER_TYPE
&& code
== POINTER_PLUS_EXPR
)
1812 || (INTEGRAL_TYPE_P (rhstype
)
1813 && (code
== BIT_AND_EXPR
1814 || code
== NOP_EXPR
)))
1816 /* Pointer plus (an integer), and truncation are considered among
1817 the (potentially) related expressions to strlen. */
1818 return is_strlen_related_p (src
, rhs1
);
1821 if (tree rhs2
= gimple_assign_rhs2 (def_stmt
))
1823 /* Integer subtraction is considered strlen-related when both
1824 arguments are integers and second one is strlen-related. */
1825 rhstype
= TREE_TYPE (rhs2
);
1826 if (INTEGRAL_TYPE_P (rhstype
) && code
== MINUS_EXPR
)
1827 return is_strlen_related_p (src
, rhs2
);
1833 /* Called by handle_builtin_stxncpy and by gimple_fold_builtin_strncpy
1835 Check to see if the specified bound is a) equal to the size of
1836 the destination DST and if so, b) if it's immediately followed by
1837 DST[CNT - 1] = '\0'. If a) holds and b) does not, warn. Otherwise,
1838 do nothing. Return true if diagnostic has been issued.
1840 The purpose is to diagnose calls to strncpy and stpncpy that do
1841 not nul-terminate the copy while allowing for the idiom where
1842 such a call is immediately followed by setting the last element
1845 strncpy (a, s, sizeof a);
1846 a[sizeof a - 1] = '\0';
1850 maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi
, tree src
, tree cnt
)
1852 gimple
*stmt
= gsi_stmt (gsi
);
1853 if (gimple_no_warning_p (stmt
))
1856 wide_int cntrange
[2];
1858 if (TREE_CODE (cnt
) == INTEGER_CST
)
1859 cntrange
[0] = cntrange
[1] = wi::to_wide (cnt
);
1860 else if (TREE_CODE (cnt
) == SSA_NAME
)
1862 enum value_range_type rng
= get_range_info (cnt
, cntrange
, cntrange
+ 1);
1863 if (rng
== VR_RANGE
)
1865 else if (rng
== VR_ANTI_RANGE
)
1867 wide_int maxobjsize
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
));
1869 if (wi::ltu_p (cntrange
[1], maxobjsize
))
1871 cntrange
[0] = cntrange
[1] + 1;
1872 cntrange
[1] = maxobjsize
;
1876 cntrange
[1] = cntrange
[0] - 1;
1877 cntrange
[0] = wi::zero (TYPE_PRECISION (TREE_TYPE (cnt
)));
1886 /* Negative value is the constant string length. If it's less than
1887 the lower bound there is no truncation. Avoid calling get_stridx()
1888 when ssa_ver_to_stridx is empty. That implies the caller isn't
1889 running under the control of this pass and ssa_ver_to_stridx hasn't
1890 been created yet. */
1891 int sidx
= ssa_ver_to_stridx
.length () ? get_stridx (src
) : 0;
1892 if (sidx
< 0 && wi::gtu_p (cntrange
[0], ~sidx
))
1895 tree dst
= gimple_call_arg (stmt
, 0);
1897 if (TREE_CODE (dstdecl
) == ADDR_EXPR
)
1898 dstdecl
= TREE_OPERAND (dstdecl
, 0);
1900 tree ref
= NULL_TREE
;
1904 /* If the source is a non-string return early to avoid warning
1905 for possible truncation (if the truncation is certain SIDX
1907 tree srcdecl
= gimple_call_arg (stmt
, 1);
1908 if (TREE_CODE (srcdecl
) == ADDR_EXPR
)
1909 srcdecl
= TREE_OPERAND (srcdecl
, 0);
1910 if (get_attr_nonstring_decl (srcdecl
, &ref
))
1914 /* Likewise, if the destination refers to a an array/pointer declared
1915 nonstring return early. */
1916 if (get_attr_nonstring_decl (dstdecl
, &ref
))
1919 /* Look for dst[i] = '\0'; after the stxncpy() call and if found
1920 avoid the truncation warning. */
1921 gsi_next_nondebug (&gsi
);
1922 gimple
*next_stmt
= gsi_stmt (gsi
);
1925 /* When there is no statement in the same basic block check
1926 the immediate successor block. */
1927 if (basic_block bb
= gimple_bb (stmt
))
1929 if (single_succ_p (bb
))
1931 /* For simplicity, ignore blocks with multiple outgoing
1932 edges for now and only consider successor blocks along
1934 edge e
= EDGE_SUCC (bb
, 0);
1935 if (!(e
->flags
& EDGE_ABNORMAL
))
1937 gsi
= gsi_start_bb (e
->dest
);
1938 next_stmt
= gsi_stmt (gsi
);
1939 if (next_stmt
&& is_gimple_debug (next_stmt
))
1941 gsi_next_nondebug (&gsi
);
1942 next_stmt
= gsi_stmt (gsi
);
1949 if (next_stmt
&& is_gimple_assign (next_stmt
))
1951 tree lhs
= gimple_assign_lhs (next_stmt
);
1952 tree_code code
= TREE_CODE (lhs
);
1953 if (code
== ARRAY_REF
|| code
== MEM_REF
)
1954 lhs
= TREE_OPERAND (lhs
, 0);
1956 tree func
= gimple_call_fndecl (stmt
);
1957 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STPNCPY
)
1959 tree ret
= gimple_call_lhs (stmt
);
1960 if (ret
&& operand_equal_p (ret
, lhs
, 0))
1964 /* Determine the base address and offset of the reference,
1965 ignoring the innermost array index. */
1966 if (TREE_CODE (ref
) == ARRAY_REF
)
1967 ref
= TREE_OPERAND (ref
, 0);
1970 tree dstbase
= get_addr_base_and_unit_offset (ref
, &dstoff
);
1973 tree lhsbase
= get_addr_base_and_unit_offset (lhs
, &lhsoff
);
1976 && known_eq (dstoff
, lhsoff
)
1977 && operand_equal_p (dstbase
, lhsbase
, 0))
1981 int prec
= TYPE_PRECISION (TREE_TYPE (cnt
));
1982 wide_int lenrange
[2];
1983 if (strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
)
1985 lenrange
[0] = (sisrc
->nonzero_chars
1986 && TREE_CODE (sisrc
->nonzero_chars
) == INTEGER_CST
1987 ? wi::to_wide (sisrc
->nonzero_chars
)
1989 lenrange
[1] = lenrange
[0];
1992 lenrange
[0] = lenrange
[1] = wi::shwi (~sidx
, prec
);
1996 get_range_strlen (src
, range
);
1997 if (range
[0] != NULL_TREE
1998 && TREE_CODE (range
[0]) == INTEGER_CST
1999 && range
[1] != NULL_TREE
2000 && TREE_CODE (range
[1]) == INTEGER_CST
)
2002 lenrange
[0] = wi::to_wide (range
[0], prec
);
2003 lenrange
[1] = wi::to_wide (range
[1], prec
);
2007 lenrange
[0] = wi::shwi (0, prec
);
2008 lenrange
[1] = wi::shwi (-1, prec
);
2012 location_t callloc
= gimple_nonartificial_location (stmt
);
2013 callloc
= expansion_point_location_if_in_system_header (callloc
);
2015 tree func
= gimple_call_fndecl (stmt
);
2017 if (lenrange
[0] != 0 || !wi::neg_p (lenrange
[1]))
2019 /* If the longest source string is shorter than the lower bound
2020 of the specified count the copy is definitely nul-terminated. */
2021 if (wi::ltu_p (lenrange
[1], cntrange
[0]))
2024 if (wi::neg_p (lenrange
[1]))
2026 /* The length of one of the strings is unknown but at least
2027 one has non-zero length and that length is stored in
2028 LENRANGE[1]. Swap the bounds to force a "may be truncated"
2030 lenrange
[1] = lenrange
[0];
2031 lenrange
[0] = wi::shwi (0, prec
);
2034 gcall
*call
= as_a
<gcall
*> (stmt
);
2036 /* Set to true for strncat whose bound is derived from the length
2037 of the destination (the expected usage pattern). */
2038 bool cat_dstlen_bounded
= false;
2039 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STRNCAT
)
2040 cat_dstlen_bounded
= is_strlen_related_p (dst
, cnt
);
2042 if (lenrange
[0] == cntrange
[1] && cntrange
[0] == cntrange
[1])
2043 return warning_n (callloc
, OPT_Wstringop_truncation
,
2044 cntrange
[0].to_uhwi (),
2045 "%G%qD output truncated before terminating "
2046 "nul copying %E byte from a string of the "
2048 "%G%qD output truncated before terminating nul "
2049 "copying %E bytes from a string of the same "
2052 else if (!cat_dstlen_bounded
)
2054 if (wi::geu_p (lenrange
[0], cntrange
[1]))
2056 /* The shortest string is longer than the upper bound of
2057 the count so the truncation is certain. */
2058 if (cntrange
[0] == cntrange
[1])
2059 return warning_n (callloc
, OPT_Wstringop_truncation
,
2060 cntrange
[0].to_uhwi (),
2061 "%G%qD output truncated copying %E byte "
2062 "from a string of length %wu",
2063 "%G%qD output truncated copying %E bytes "
2064 "from a string of length %wu",
2065 call
, func
, cnt
, lenrange
[0].to_uhwi ());
2067 return warning_at (callloc
, OPT_Wstringop_truncation
,
2068 "%G%qD output truncated copying between %wu "
2069 "and %wu bytes from a string of length %wu",
2070 call
, func
, cntrange
[0].to_uhwi (),
2071 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
2073 else if (wi::geu_p (lenrange
[1], cntrange
[1]))
2075 /* The longest string is longer than the upper bound of
2076 the count so the truncation is possible. */
2077 if (cntrange
[0] == cntrange
[1])
2078 return warning_n (callloc
, OPT_Wstringop_truncation
,
2079 cntrange
[0].to_uhwi (),
2080 "%G%qD output may be truncated copying %E "
2081 "byte from a string of length %wu",
2082 "%G%qD output may be truncated copying %E "
2083 "bytes from a string of length %wu",
2084 call
, func
, cnt
, lenrange
[1].to_uhwi ());
2086 return warning_at (callloc
, OPT_Wstringop_truncation
,
2087 "%G%qD output may be truncated copying between "
2088 "%wu and %wu bytes from a string of length %wu",
2089 call
, func
, cntrange
[0].to_uhwi (),
2090 cntrange
[1].to_uhwi (), lenrange
[1].to_uhwi ());
2094 if (!cat_dstlen_bounded
2095 && cntrange
[0] != cntrange
[1]
2096 && wi::leu_p (cntrange
[0], lenrange
[0])
2097 && wi::leu_p (cntrange
[1], lenrange
[0] + 1))
2099 /* If the source (including the terminating nul) is longer than
2100 the lower bound of the specified count but shorter than the
2101 upper bound the copy may (but need not) be truncated. */
2102 return warning_at (callloc
, OPT_Wstringop_truncation
,
2103 "%G%qD output may be truncated copying between "
2104 "%wu and %wu bytes from a string of length %wu",
2105 call
, func
, cntrange
[0].to_uhwi (),
2106 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
2110 if (tree dstsize
= compute_objsize (dst
, 1))
2112 /* The source length is uknown. Try to determine the destination
2113 size and see if it matches the specified bound. If not, bail.
2114 Otherwise go on to see if it should be diagnosed for possible
2119 if (wi::to_wide (dstsize
) != cntrange
[1])
2122 if (cntrange
[0] == cntrange
[1])
2123 return warning_at (callloc
, OPT_Wstringop_truncation
,
2124 "%G%qD specified bound %E equals destination size",
2125 as_a
<gcall
*> (stmt
), func
, cnt
);
2131 /* Check the arguments to the built-in forms of stpncpy and strncpy for
2132 out-of-bounds offsets or overlapping access, and to see if the size
2133 is derived from calling strlen() on the source argument, and if so,
2134 issue the appropriate warning. */
2137 handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*gsi
)
2139 if (!strlen_to_stridx
)
2142 gimple
*stmt
= gsi_stmt (*gsi
);
2144 tree dst
= gimple_call_arg (stmt
, 0);
2145 tree src
= gimple_call_arg (stmt
, 1);
2146 tree len
= gimple_call_arg (stmt
, 2);
2147 tree dstsize
= NULL_TREE
, srcsize
= NULL_TREE
;
2149 int didx
= get_stridx (dst
);
2150 if (strinfo
*sidst
= didx
> 0 ? get_strinfo (didx
) : NULL
)
2152 /* Compute the size of the destination string including the NUL. */
2153 if (sidst
->nonzero_chars
)
2155 tree type
= TREE_TYPE (sidst
->nonzero_chars
);
2156 dstsize
= fold_build2 (PLUS_EXPR
, type
, sidst
->nonzero_chars
,
2157 build_int_cst (type
, 1));
2162 int sidx
= get_stridx (src
);
2163 strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
;
2166 /* strncat() and strncpy() can modify the source string by writing
2167 over the terminating nul so SISRC->DONT_INVALIDATE must be left
2170 /* Compute the size of the source string including the NUL. */
2171 if (sisrc
->nonzero_chars
)
2173 tree type
= TREE_TYPE (sisrc
->nonzero_chars
);
2174 srcsize
= fold_build2 (PLUS_EXPR
, type
, sisrc
->nonzero_chars
,
2175 build_int_cst (type
, 1));
2181 srcsize
= NULL_TREE
;
2183 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, src
,
2186 gimple_set_no_warning (stmt
, true);
2190 /* If the length argument was computed from strlen(S) for some string
2191 S retrieve the strinfo index for the string (PSS->FIRST) alonng with
2192 the location of the strlen() call (PSS->SECOND). */
2193 stridx_strlenloc
*pss
= strlen_to_stridx
->get (len
);
2194 if (!pss
|| pss
->first
<= 0)
2196 if (maybe_diag_stxncpy_trunc (*gsi
, src
, len
))
2197 gimple_set_no_warning (stmt
, true);
2202 /* Retrieve the strinfo data for the string S that LEN was computed
2203 from as some function F of strlen (S) (i.e., LEN need not be equal
2205 strinfo
*silen
= get_strinfo (pss
->first
);
2207 location_t callloc
= gimple_nonartificial_location (stmt
);
2208 callloc
= expansion_point_location_if_in_system_header (callloc
);
2210 tree func
= gimple_call_fndecl (stmt
);
2212 bool warned
= false;
2214 /* When -Wstringop-truncation is set, try to determine truncation
2215 before diagnosing possible overflow. Truncation is implied by
2216 the LEN argument being equal to strlen(SRC), regardless of
2217 whether its value is known. Otherwise, issue the more generic
2218 -Wstringop-overflow which triggers for LEN arguments that in
2219 any meaningful way depend on strlen(SRC). */
2221 && is_strlen_related_p (src
, len
)
2222 && warning_at (callloc
, OPT_Wstringop_truncation
,
2223 "%G%qD output truncated before terminating nul "
2224 "copying as many bytes from a string as its length",
2225 as_a
<gcall
*>(stmt
), func
))
2227 else if (silen
&& is_strlen_related_p (src
, silen
->ptr
))
2228 warned
= warning_at (callloc
, OPT_Wstringop_overflow_
,
2229 "%G%qD specified bound depends on the length "
2230 "of the source argument",
2231 as_a
<gcall
*>(stmt
), func
);
2234 location_t strlenloc
= pss
->second
;
2235 if (strlenloc
!= UNKNOWN_LOCATION
&& strlenloc
!= callloc
)
2236 inform (strlenloc
, "length computed here");
2240 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
2241 If strlen of the second argument is known and length of the third argument
2242 is that plus one, strlen of the first argument is the same after this
2246 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2249 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
2250 gimple
*stmt
= gsi_stmt (*gsi
);
2251 strinfo
*si
, *dsi
, *olddsi
;
2253 len
= gimple_call_arg (stmt
, 2);
2254 src
= gimple_call_arg (stmt
, 1);
2255 dst
= gimple_call_arg (stmt
, 0);
2256 idx
= get_stridx (src
);
2260 didx
= get_stridx (dst
);
2263 olddsi
= get_strinfo (didx
);
2268 && tree_fits_uhwi_p (len
)
2269 && !integer_zerop (len
))
2270 adjust_last_stmt (olddsi
, stmt
, false);
2277 /* Handle memcpy (x, y, l) where l's relationship with strlen (y)
2279 si
= get_strinfo (idx
);
2280 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
2282 if (TREE_CODE (len
) == INTEGER_CST
2283 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
2285 if (tree_int_cst_le (len
, si
->nonzero_chars
))
2287 /* Copying LEN nonzero characters, where LEN is constant. */
2289 full_string_p
= false;
2293 /* Copying the whole of the analyzed part of SI. */
2294 newlen
= si
->nonzero_chars
;
2295 full_string_p
= si
->full_string_p
;
2300 if (!si
->full_string_p
)
2302 if (TREE_CODE (len
) != SSA_NAME
)
2304 def_stmt
= SSA_NAME_DEF_STMT (len
);
2305 if (!is_gimple_assign (def_stmt
)
2306 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
2307 || gimple_assign_rhs1 (def_stmt
) != si
->nonzero_chars
2308 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
2310 /* Copying variable-length string SI (and no more). */
2311 newlen
= si
->nonzero_chars
;
2312 full_string_p
= true;
2318 /* Handle memcpy (x, "abcd", 5) or
2319 memcpy (x, "abc\0uvw", 7). */
2320 if (!tree_fits_uhwi_p (len
))
2323 unsigned HOST_WIDE_INT clen
= tree_to_uhwi (len
);
2324 unsigned HOST_WIDE_INT nonzero_chars
= ~idx
;
2325 newlen
= build_int_cst (size_type_node
, MIN (nonzero_chars
, clen
));
2326 full_string_p
= clen
> nonzero_chars
;
2329 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
2330 adjust_last_stmt (olddsi
, stmt
, false);
2334 didx
= new_stridx (dst
);
2341 dsi
= unshare_strinfo (olddsi
);
2342 oldlen
= olddsi
->nonzero_chars
;
2343 dsi
->nonzero_chars
= newlen
;
2344 dsi
->full_string_p
= full_string_p
;
2345 /* Break the chain, so adjust_related_strinfo on later pointers in
2346 the chain won't adjust this one anymore. */
2349 dsi
->endptr
= NULL_TREE
;
2353 dsi
= new_strinfo (dst
, didx
, newlen
, full_string_p
);
2354 set_strinfo (didx
, dsi
);
2355 find_equal_ptrs (dst
, didx
);
2357 dsi
->writable
= true;
2358 dsi
->dont_invalidate
= true;
2361 tree adj
= NULL_TREE
;
2362 location_t loc
= gimple_location (stmt
);
2363 if (oldlen
== NULL_TREE
)
2365 else if (integer_zerop (oldlen
))
2367 else if (TREE_CODE (oldlen
) == INTEGER_CST
2368 || TREE_CODE (newlen
) == INTEGER_CST
)
2369 adj
= fold_build2_loc (loc
, MINUS_EXPR
, TREE_TYPE (newlen
), newlen
,
2370 fold_convert_loc (loc
, TREE_TYPE (newlen
),
2372 if (adj
!= NULL_TREE
)
2373 adjust_related_strinfos (loc
, dsi
, adj
);
2377 /* memcpy src may not overlap dst, so src doesn't need to be
2378 invalidated either. */
2380 si
->dont_invalidate
= true;
2384 lhs
= gimple_call_lhs (stmt
);
2387 case BUILT_IN_MEMCPY
:
2388 case BUILT_IN_MEMCPY_CHK
:
2389 /* Allow adjust_last_stmt to decrease this memcpy's size. */
2390 laststmt
.stmt
= stmt
;
2391 laststmt
.len
= dsi
->nonzero_chars
;
2392 laststmt
.stridx
= dsi
->idx
;
2394 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
2396 case BUILT_IN_MEMPCPY
:
2397 case BUILT_IN_MEMPCPY_CHK
:
2405 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
2406 If strlen of the second argument is known, strlen of the first argument
2407 is increased by the length of the second argument. Furthermore, attempt
2408 to convert it to memcpy/strcpy if the length of the first argument
2412 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2415 tree srclen
, args
, type
, fn
, objsz
, endptr
;
2417 gimple
*stmt
= gsi_stmt (*gsi
);
2419 location_t loc
= gimple_location (stmt
);
2421 tree src
= gimple_call_arg (stmt
, 1);
2422 tree dst
= gimple_call_arg (stmt
, 0);
2424 /* Bail if the source is the same as destination. It will be diagnosed
2426 if (operand_equal_p (src
, dst
, 0))
2429 tree lhs
= gimple_call_lhs (stmt
);
2431 didx
= get_stridx (dst
);
2437 dsi
= get_strinfo (didx
);
2441 idx
= get_stridx (src
);
2443 srclen
= build_int_cst (size_type_node
, ~idx
);
2446 si
= get_strinfo (idx
);
2448 srclen
= get_string_length (si
);
2451 /* Set the no-warning bit on the transformed statement? */
2452 bool set_no_warning
= false;
2454 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
2457 /* The concatenation always involves copying at least one byte
2458 (the terminating nul), even if the source string is empty.
2459 If the source is unknown assume it's one character long and
2460 used that as both sizes. */
2464 tree type
= TREE_TYPE (slen
);
2465 slen
= fold_build2 (PLUS_EXPR
, type
, slen
, build_int_cst (type
, 1));
2468 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2470 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, sptr
,
2473 gimple_set_no_warning (stmt
, true);
2474 set_no_warning
= true;
2478 /* strcat (p, q) can be transformed into
2479 tmp = p + strlen (p); endptr = stpcpy (tmp, q);
2480 with length endptr - p if we need to compute the length
2481 later on. Don't do this transformation if we don't need
2483 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
2487 didx
= new_stridx (dst
);
2493 dsi
= new_strinfo (dst
, didx
, NULL_TREE
, false);
2494 set_strinfo (didx
, dsi
);
2495 find_equal_ptrs (dst
, didx
);
2499 dsi
= unshare_strinfo (dsi
);
2500 dsi
->nonzero_chars
= NULL_TREE
;
2501 dsi
->full_string_p
= false;
2503 dsi
->endptr
= NULL_TREE
;
2505 dsi
->writable
= true;
2507 dsi
->dont_invalidate
= true;
2512 tree dstlen
= dsi
->nonzero_chars
;
2513 endptr
= dsi
->endptr
;
2515 dsi
= unshare_strinfo (dsi
);
2516 dsi
->endptr
= NULL_TREE
;
2518 dsi
->writable
= true;
2520 if (srclen
!= NULL_TREE
)
2522 dsi
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
2523 TREE_TYPE (dsi
->nonzero_chars
),
2524 dsi
->nonzero_chars
, srclen
);
2525 gcc_assert (dsi
->full_string_p
);
2526 adjust_related_strinfos (loc
, dsi
, srclen
);
2527 dsi
->dont_invalidate
= true;
2531 dsi
->nonzero_chars
= NULL
;
2532 dsi
->full_string_p
= false;
2533 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
2534 dsi
->dont_invalidate
= true;
2538 /* strcat src may not overlap dst, so src doesn't need to be
2539 invalidated either. */
2540 si
->dont_invalidate
= true;
2542 /* For now. Could remove the lhs from the call and add
2543 lhs = dst; afterwards. */
2551 case BUILT_IN_STRCAT
:
2552 if (srclen
!= NULL_TREE
)
2553 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
2555 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
2557 case BUILT_IN_STRCAT_CHK
:
2558 if (srclen
!= NULL_TREE
)
2559 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
2561 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
2562 objsz
= gimple_call_arg (stmt
, 2);
2568 if (fn
== NULL_TREE
)
2573 tree type
= TREE_TYPE (dstlen
);
2575 /* Compute the size of the source sequence, including the nul. */
2576 tree srcsize
= srclen
? srclen
: size_zero_node
;
2577 srcsize
= fold_build2 (PLUS_EXPR
, type
, srcsize
, build_int_cst (type
, 1));
2579 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2581 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, sptr
,
2584 gimple_set_no_warning (stmt
, true);
2585 set_no_warning
= true;
2589 tree len
= NULL_TREE
;
2590 if (srclen
!= NULL_TREE
)
2592 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
2593 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
2595 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
2596 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
2597 build_int_cst (type
, 1));
2598 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
2602 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
2604 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
2605 TREE_TYPE (dst
), unshare_expr (dst
),
2606 fold_convert_loc (loc
, sizetype
,
2607 unshare_expr (dstlen
)));
2608 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
2610 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2612 fprintf (dump_file
, "Optimizing: ");
2613 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2615 if (srclen
!= NULL_TREE
)
2616 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
2617 dst
, src
, len
, objsz
);
2619 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
2623 stmt
= gsi_stmt (*gsi
);
2625 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2627 fprintf (dump_file
, "into: ");
2628 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2630 /* If srclen == NULL, note that current string length can be
2631 computed by transforming this strcpy into stpcpy. */
2632 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
2634 adjust_last_stmt (dsi
, stmt
, true);
2635 if (srclen
!= NULL_TREE
)
2637 laststmt
.stmt
= stmt
;
2638 laststmt
.len
= srclen
;
2639 laststmt
.stridx
= dsi
->idx
;
2642 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2643 fprintf (dump_file
, "not possible.\n");
2646 gimple_set_no_warning (stmt
, true);
2649 /* Handle a call to malloc or calloc. */
2652 handle_builtin_malloc (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2654 gimple
*stmt
= gsi_stmt (*gsi
);
2655 tree lhs
= gimple_call_lhs (stmt
);
2656 if (lhs
== NULL_TREE
)
2659 gcc_assert (get_stridx (lhs
) == 0);
2660 int idx
= new_stridx (lhs
);
2661 tree length
= NULL_TREE
;
2662 if (bcode
== BUILT_IN_CALLOC
)
2663 length
= build_int_cst (size_type_node
, 0);
2664 strinfo
*si
= new_strinfo (lhs
, idx
, length
, length
!= NULL_TREE
);
2665 if (bcode
== BUILT_IN_CALLOC
)
2667 set_strinfo (idx
, si
);
2668 si
->writable
= true;
2670 si
->dont_invalidate
= true;
2673 /* Handle a call to memset.
2674 After a call to calloc, memset(,0,) is unnecessary.
2675 memset(malloc(n),0,n) is calloc(n,1).
2676 return true when the call is transfomred, false otherwise. */
2679 handle_builtin_memset (gimple_stmt_iterator
*gsi
)
2681 gimple
*stmt2
= gsi_stmt (*gsi
);
2682 if (!integer_zerop (gimple_call_arg (stmt2
, 1)))
2684 tree ptr
= gimple_call_arg (stmt2
, 0);
2685 int idx1
= get_stridx (ptr
);
2688 strinfo
*si1
= get_strinfo (idx1
);
2691 gimple
*stmt1
= si1
->stmt
;
2692 if (!stmt1
|| !is_gimple_call (stmt1
))
2694 tree callee1
= gimple_call_fndecl (stmt1
);
2695 if (!valid_builtin_call (stmt1
))
2697 enum built_in_function code1
= DECL_FUNCTION_CODE (callee1
);
2698 tree size
= gimple_call_arg (stmt2
, 2);
2699 if (code1
== BUILT_IN_CALLOC
)
2700 /* Not touching stmt1 */ ;
2701 else if (code1
== BUILT_IN_MALLOC
2702 && operand_equal_p (gimple_call_arg (stmt1
, 0), size
, 0))
2704 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt1
);
2705 update_gimple_call (&gsi1
, builtin_decl_implicit (BUILT_IN_CALLOC
), 2,
2706 size
, build_one_cst (size_type_node
));
2707 si1
->nonzero_chars
= build_int_cst (size_type_node
, 0);
2708 si1
->full_string_p
= true;
2709 si1
->stmt
= gsi_stmt (gsi1
);
2713 tree lhs
= gimple_call_lhs (stmt2
);
2714 unlink_stmt_vdef (stmt2
);
2717 gimple
*assign
= gimple_build_assign (lhs
, ptr
);
2718 gsi_replace (gsi
, assign
, false);
2722 gsi_remove (gsi
, true);
2723 release_defs (stmt2
);
2729 /* Handle a call to memcmp. We try to handle small comparisons by
2730 converting them to load and compare, and replacing the call to memcmp
2731 with a __builtin_memcmp_eq call where possible.
2732 return true when call is transformed, return false otherwise. */
2735 handle_builtin_memcmp (gimple_stmt_iterator
*gsi
)
2737 gcall
*stmt2
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2738 tree res
= gimple_call_lhs (stmt2
);
2739 tree arg1
= gimple_call_arg (stmt2
, 0);
2740 tree arg2
= gimple_call_arg (stmt2
, 1);
2741 tree len
= gimple_call_arg (stmt2
, 2);
2742 unsigned HOST_WIDE_INT leni
;
2743 use_operand_p use_p
;
2744 imm_use_iterator iter
;
2749 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
2751 gimple
*ustmt
= USE_STMT (use_p
);
2753 if (is_gimple_debug (ustmt
))
2755 if (gimple_code (ustmt
) == GIMPLE_ASSIGN
)
2757 gassign
*asgn
= as_a
<gassign
*> (ustmt
);
2758 tree_code code
= gimple_assign_rhs_code (asgn
);
2759 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2760 || !integer_zerop (gimple_assign_rhs2 (asgn
)))
2763 else if (gimple_code (ustmt
) == GIMPLE_COND
)
2765 tree_code code
= gimple_cond_code (ustmt
);
2766 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2767 || !integer_zerop (gimple_cond_rhs (ustmt
)))
2774 if (tree_fits_uhwi_p (len
)
2775 && (leni
= tree_to_uhwi (len
)) <= GET_MODE_SIZE (word_mode
)
2776 && pow2p_hwi (leni
))
2778 leni
*= CHAR_TYPE_SIZE
;
2779 unsigned align1
= get_pointer_alignment (arg1
);
2780 unsigned align2
= get_pointer_alignment (arg2
);
2781 unsigned align
= MIN (align1
, align2
);
2782 scalar_int_mode mode
;
2783 if (int_mode_for_size (leni
, 1).exists (&mode
)
2784 && (align
>= leni
|| !targetm
.slow_unaligned_access (mode
, align
)))
2786 location_t loc
= gimple_location (stmt2
);
2788 type
= build_nonstandard_integer_type (leni
, 1);
2789 gcc_assert (known_eq (GET_MODE_BITSIZE (TYPE_MODE (type
)), leni
));
2790 tree ptrtype
= build_pointer_type_for_mode (char_type_node
,
2792 off
= build_int_cst (ptrtype
, 0);
2793 arg1
= build2_loc (loc
, MEM_REF
, type
, arg1
, off
);
2794 arg2
= build2_loc (loc
, MEM_REF
, type
, arg2
, off
);
2795 tree tem1
= fold_const_aggregate_ref (arg1
);
2798 tree tem2
= fold_const_aggregate_ref (arg2
);
2801 res
= fold_convert_loc (loc
, TREE_TYPE (res
),
2802 fold_build2_loc (loc
, NE_EXPR
,
2805 gimplify_and_update_call_from_tree (gsi
, res
);
2810 gimple_call_set_fndecl (stmt2
, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ
));
2814 /* Given an index to the strinfo vector, compute the string length for the
2815 corresponding string. Return -1 when unknown. */
2817 static HOST_WIDE_INT
2818 compute_string_length (int idx
)
2820 HOST_WIDE_INT string_leni
= -1;
2821 gcc_assert (idx
!= 0);
2826 strinfo
*si
= get_strinfo (idx
);
2829 tree const_string_len
= get_string_length (si
);
2830 if (const_string_len
&& tree_fits_shwi_p (const_string_len
))
2831 string_leni
= tree_to_shwi (const_string_len
);
2834 if (string_leni
< 0)
2840 /* Determine the minimum size of the object referenced by DEST expression which
2841 must have a pointer type.
2842 Return the minimum size of the object if successful or NULL when the size
2843 cannot be determined. */
2845 determine_min_objsize (tree dest
)
2847 unsigned HOST_WIDE_INT size
= 0;
2849 if (compute_builtin_object_size (dest
, 2, &size
))
2850 return build_int_cst (sizetype
, size
);
2852 /* Try to determine the size of the object through the RHS of the
2853 assign statement. */
2854 if (TREE_CODE (dest
) == SSA_NAME
)
2856 gimple
*stmt
= SSA_NAME_DEF_STMT (dest
);
2857 if (!is_gimple_assign (stmt
))
2860 if (!gimple_assign_single_p (stmt
)
2861 && !gimple_assign_unary_nop_p (stmt
))
2864 dest
= gimple_assign_rhs1 (stmt
);
2865 return determine_min_objsize (dest
);
2868 /* Try to determine the size of the object from its type. */
2869 if (TREE_CODE (dest
) != ADDR_EXPR
)
2872 tree type
= TREE_TYPE (dest
);
2873 if (TREE_CODE (type
) == POINTER_TYPE
)
2874 type
= TREE_TYPE (type
);
2876 type
= TYPE_MAIN_VARIANT (type
);
2878 /* We cannot determine the size of the array if it's a flexible array,
2879 which is declared at the end of a structure. */
2880 if (TREE_CODE (type
) == ARRAY_TYPE
2881 && !array_at_struct_end_p (dest
))
2883 tree
size_t = TYPE_SIZE_UNIT (type
);
2884 if (size_t && TREE_CODE (size_t) == INTEGER_CST
2885 && !integer_zerop (size_t))
2892 /* Handle a call to strcmp or strncmp. When the result is ONLY used to do
2893 equality test against zero:
2895 A. When the lengths of both arguments are constant and it's a strcmp:
2896 * if the lengths are NOT equal, we can safely fold the call
2897 to a non-zero value.
2898 * otherwise, do nothing now.
2900 B. When the length of one argument is constant, try to replace the call with
2901 a __builtin_str(n)cmp_eq call where possible, i.e:
2903 strncmp (s, STR, C) (!)= 0 in which, s is a pointer to a string, STR is a
2904 string with constant length , C is a constant.
2905 if (C <= strlen(STR) && sizeof_array(s) > C)
2907 replace this call with
2908 strncmp_eq (s, STR, C) (!)= 0
2912 it can be safely treated as a call to strcmp (s, STR) (!)= 0
2913 can handled by the following strcmp.
2916 strcmp (s, STR) (!)= 0 in which, s is a pointer to a string, STR is a
2917 string with constant length.
2918 if (sizeof_array(s) > strlen(STR))
2920 replace this call with
2921 strcmp_eq (s, STR, strlen(STR)+1) (!)= 0
2924 Return true when the call is transformed, return false otherwise.
2928 handle_builtin_string_cmp (gimple_stmt_iterator
*gsi
)
2930 gcall
*stmt
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2931 tree res
= gimple_call_lhs (stmt
);
2932 use_operand_p use_p
;
2933 imm_use_iterator iter
;
2934 tree arg1
= gimple_call_arg (stmt
, 0);
2935 tree arg2
= gimple_call_arg (stmt
, 1);
2936 int idx1
= get_stridx (arg1
);
2937 int idx2
= get_stridx (arg2
);
2938 HOST_WIDE_INT length
= -1;
2939 bool is_ncmp
= false;
2944 /* When both arguments are unknown, do nothing. */
2945 if (idx1
== 0 && idx2
== 0)
2948 /* Handle strncmp function. */
2949 if (gimple_call_num_args (stmt
) == 3)
2951 tree len
= gimple_call_arg (stmt
, 2);
2952 if (tree_fits_shwi_p (len
))
2953 length
= tree_to_shwi (len
);
2958 /* For strncmp, if the length argument is NOT known, do nothing. */
2959 if (is_ncmp
&& length
< 0)
2962 /* When the result is ONLY used to do equality test against zero. */
2963 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
2965 gimple
*use_stmt
= USE_STMT (use_p
);
2967 if (is_gimple_debug (use_stmt
))
2969 if (gimple_code (use_stmt
) == GIMPLE_ASSIGN
)
2971 tree_code code
= gimple_assign_rhs_code (use_stmt
);
2972 if (code
== COND_EXPR
)
2974 tree cond_expr
= gimple_assign_rhs1 (use_stmt
);
2975 if ((TREE_CODE (cond_expr
) != EQ_EXPR
2976 && (TREE_CODE (cond_expr
) != NE_EXPR
))
2977 || !integer_zerop (TREE_OPERAND (cond_expr
, 1)))
2980 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
2982 if (!integer_zerop (gimple_assign_rhs2 (use_stmt
)))
2988 else if (gimple_code (use_stmt
) == GIMPLE_COND
)
2990 tree_code code
= gimple_cond_code (use_stmt
);
2991 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2992 || !integer_zerop (gimple_cond_rhs (use_stmt
)))
2999 /* When the lengths of both arguments are known, and they are unequal, we can
3000 safely fold the call to a non-zero value for strcmp;
3001 othewise, do nothing now. */
3002 if (idx1
!= 0 && idx2
!= 0)
3004 HOST_WIDE_INT const_string_leni1
= compute_string_length (idx1
);
3005 HOST_WIDE_INT const_string_leni2
= compute_string_length (idx2
);
3008 && const_string_leni1
!= -1
3009 && const_string_leni2
!= -1
3010 && const_string_leni1
!= const_string_leni2
)
3012 replace_call_with_value (gsi
, integer_one_node
);
3018 /* When the length of one argument is constant. */
3019 tree var_string
= NULL_TREE
;
3020 HOST_WIDE_INT const_string_leni
= -1;
3024 const_string_leni
= compute_string_length (idx1
);
3029 gcc_checking_assert (idx2
);
3030 const_string_leni
= compute_string_length (idx2
);
3034 if (const_string_leni
< 0)
3037 unsigned HOST_WIDE_INT var_sizei
= 0;
3038 /* try to determine the minimum size of the object pointed by var_string. */
3039 tree size
= determine_min_objsize (var_string
);
3044 if (tree_fits_uhwi_p (size
))
3045 var_sizei
= tree_to_uhwi (size
);
3050 /* For strncmp, if length > const_string_leni , this call can be safely
3051 transformed to a strcmp. */
3052 if (is_ncmp
&& length
> const_string_leni
)
3055 unsigned HOST_WIDE_INT final_length
3056 = is_ncmp
? length
: const_string_leni
+ 1;
3058 /* Replace strcmp or strncmp with the corresponding str(n)cmp_eq. */
3059 if (var_sizei
> final_length
)
3063 ? builtin_decl_implicit (BUILT_IN_STRNCMP_EQ
)
3064 : builtin_decl_implicit (BUILT_IN_STRCMP_EQ
));
3067 tree const_string_len
= build_int_cst (size_type_node
, final_length
);
3068 update_gimple_call (gsi
, fn
, 3, arg1
, arg2
, const_string_len
);
3076 /* Handle a POINTER_PLUS_EXPR statement.
3077 For p = "abcd" + 2; compute associated length, or if
3078 p = q + off is pointing to a '\0' character of a string, call
3079 zero_length_string on it. */
3082 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
3084 gimple
*stmt
= gsi_stmt (*gsi
);
3085 tree lhs
= gimple_assign_lhs (stmt
), off
;
3086 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
3094 tree off
= gimple_assign_rhs2 (stmt
);
3095 if (tree_fits_uhwi_p (off
)
3096 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
3097 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
3098 = ~(~idx
- (int) tree_to_uhwi (off
));
3102 si
= get_strinfo (idx
);
3103 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
3106 off
= gimple_assign_rhs2 (stmt
);
3108 if (si
->full_string_p
&& operand_equal_p (si
->nonzero_chars
, off
, 0))
3109 zsi
= zero_length_string (lhs
, si
);
3110 else if (TREE_CODE (off
) == SSA_NAME
)
3112 gimple
*def_stmt
= SSA_NAME_DEF_STMT (off
);
3113 if (gimple_assign_single_p (def_stmt
)
3114 && si
->full_string_p
3115 && operand_equal_p (si
->nonzero_chars
,
3116 gimple_assign_rhs1 (def_stmt
), 0))
3117 zsi
= zero_length_string (lhs
, si
);
3120 && si
->endptr
!= NULL_TREE
3121 && si
->endptr
!= lhs
3122 && TREE_CODE (si
->endptr
) == SSA_NAME
)
3124 enum tree_code rhs_code
3125 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
3126 ? SSA_NAME
: NOP_EXPR
;
3127 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
);
3128 gcc_assert (gsi_stmt (*gsi
) == stmt
);
3133 /* If RHS, either directly or indirectly, refers to a string of constant
3134 length, return it. Otherwise return a negative value. */
3136 static HOST_WIDE_INT
3137 get_string_cst_length (tree rhs
)
3139 if (TREE_CODE (rhs
) == MEM_REF
3140 && integer_zerop (TREE_OPERAND (rhs
, 1)))
3142 rhs
= TREE_OPERAND (rhs
, 0);
3143 if (TREE_CODE (rhs
) == ADDR_EXPR
)
3145 tree rhs_addr
= rhs
;
3147 rhs
= TREE_OPERAND (rhs
, 0);
3148 if (TREE_CODE (rhs
) != STRING_CST
)
3150 int idx
= get_stridx (rhs_addr
);
3153 strinfo
*si
= get_strinfo (idx
);
3155 && si
->full_string_p
3156 && tree_fits_shwi_p (si
->nonzero_chars
))
3157 return tree_to_shwi (si
->nonzero_chars
);
3163 if (TREE_CODE (rhs
) == VAR_DECL
3164 && TREE_READONLY (rhs
))
3165 rhs
= DECL_INITIAL (rhs
);
3167 if (rhs
&& TREE_CODE (rhs
) == STRING_CST
)
3168 return strlen (TREE_STRING_POINTER (rhs
));
3173 /* Handle a single character store. */
3176 handle_char_store (gimple_stmt_iterator
*gsi
)
3180 gimple
*stmt
= gsi_stmt (*gsi
);
3181 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
3182 tree rhs
= gimple_assign_rhs1 (stmt
);
3183 unsigned HOST_WIDE_INT offset
= 0;
3185 if (TREE_CODE (lhs
) == MEM_REF
3186 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
3188 tree mem_offset
= TREE_OPERAND (lhs
, 1);
3189 if (tree_fits_uhwi_p (mem_offset
))
3191 /* Get the strinfo for the base, and use it if it starts with at
3192 least OFFSET nonzero characters. This is trivially true if
3194 offset
= tree_to_uhwi (mem_offset
);
3195 idx
= get_stridx (TREE_OPERAND (lhs
, 0));
3197 si
= get_strinfo (idx
);
3199 ssaname
= TREE_OPERAND (lhs
, 0);
3200 else if (si
== NULL
|| compare_nonzero_chars (si
, offset
) < 0)
3206 idx
= get_addr_stridx (lhs
, NULL_TREE
, &offset
);
3208 si
= get_strinfo (idx
);
3211 bool storing_zero_p
= initializer_zerop (rhs
);
3212 bool storing_nonzero_p
= !storing_zero_p
&& tree_expr_nonzero_p (rhs
);
3213 /* Set to the length of the string being assigned if known. */
3214 HOST_WIDE_INT rhslen
;
3218 int cmp
= compare_nonzero_chars (si
, offset
);
3219 gcc_assert (offset
== 0 || cmp
>= 0);
3220 if (storing_zero_p
&& cmp
== 0 && si
->full_string_p
)
3222 /* When overwriting a '\0' with a '\0', the store can be removed
3223 if we know it has been stored in the current function. */
3224 if (!stmt_could_throw_p (stmt
) && si
->writable
)
3226 unlink_stmt_vdef (stmt
);
3227 release_defs (stmt
);
3228 gsi_remove (gsi
, true);
3233 si
->writable
= true;
3238 /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0',
3239 and if we aren't storing '\0', we know that the length of the
3240 string and any other zero terminated string in memory remains
3241 the same. In that case we move to the next gimple statement and
3242 return to signal the caller that it shouldn't invalidate anything.
3244 This is benefical for cases like:
3249 strcpy (p, "foobar");
3250 size_t len = strlen (p); // This can be optimized into 6
3251 size_t len2 = strlen (q); // This has to be computed
3253 size_t len3 = strlen (p); // This can be optimized into 6
3254 size_t len4 = strlen (q); // This can be optimized into len2
3255 bar (len, len2, len3, len4);
3258 else if (storing_nonzero_p
&& cmp
> 0)
3263 else if (storing_zero_p
|| storing_nonzero_p
|| (offset
!= 0 && cmp
> 0))
3265 /* When storing_nonzero_p, we know that the string now starts
3266 with OFFSET + 1 nonzero characters, but don't know whether
3267 there's a following nul terminator.
3269 When storing_zero_p, we know that the string is now OFFSET
3272 Otherwise, we're storing an unknown value at offset OFFSET,
3273 so need to clip the nonzero_chars to OFFSET. */
3274 location_t loc
= gimple_location (stmt
);
3275 tree oldlen
= si
->nonzero_chars
;
3276 if (cmp
== 0 && si
->full_string_p
)
3277 /* We're overwriting the nul terminator with a nonzero or
3278 unknown character. If the previous stmt was a memcpy,
3279 its length may be decreased. */
3280 adjust_last_stmt (si
, stmt
, false);
3281 si
= unshare_strinfo (si
);
3282 if (storing_nonzero_p
)
3283 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
+ 1);
3285 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
);
3286 si
->full_string_p
= storing_zero_p
;
3289 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
3290 si
->endptr
= ssaname
;
3295 si
->writable
= true;
3296 si
->dont_invalidate
= true;
3299 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
3300 si
->nonzero_chars
, oldlen
);
3301 adjust_related_strinfos (loc
, si
, adj
);
3307 else if (idx
== 0 && (storing_zero_p
|| storing_nonzero_p
))
3310 idx
= new_stridx (ssaname
);
3312 idx
= new_addr_stridx (lhs
);
3315 tree ptr
= (ssaname
? ssaname
: build_fold_addr_expr (lhs
));
3316 tree len
= storing_nonzero_p
? size_one_node
: size_zero_node
;
3317 si
= new_strinfo (ptr
, idx
, len
, storing_zero_p
);
3318 set_strinfo (idx
, si
);
3321 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
3322 si
->endptr
= ssaname
;
3323 si
->dont_invalidate
= true;
3324 si
->writable
= true;
3328 && (rhslen
= get_string_cst_length (gimple_assign_rhs1 (stmt
))) >= 0
3329 && ssaname
== NULL_TREE
3330 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
3332 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
3333 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> (unsigned HOST_WIDE_INT
) rhslen
)
3335 int idx
= new_addr_stridx (lhs
);
3338 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
3339 build_int_cst (size_type_node
, rhslen
), true);
3340 set_strinfo (idx
, si
);
3341 si
->dont_invalidate
= true;
3346 if (si
!= NULL
&& offset
== 0 && storing_zero_p
)
3348 /* Allow adjust_last_stmt to remove it if the stored '\0'
3349 is immediately overwritten. */
3350 laststmt
.stmt
= stmt
;
3351 laststmt
.len
= build_int_cst (size_type_node
, 1);
3352 laststmt
.stridx
= si
->idx
;
3357 /* Try to fold strstr (s, t) eq/ne s to strncmp (s, t, strlen (t)) eq/ne 0. */
3360 fold_strstr_to_strncmp (tree rhs1
, tree rhs2
, gimple
*stmt
)
3362 if (TREE_CODE (rhs1
) != SSA_NAME
3363 || TREE_CODE (rhs2
) != SSA_NAME
)
3366 gimple
*call_stmt
= NULL
;
3367 for (int pass
= 0; pass
< 2; pass
++)
3369 gimple
*g
= SSA_NAME_DEF_STMT (rhs1
);
3370 if (gimple_call_builtin_p (g
, BUILT_IN_STRSTR
)
3371 && has_single_use (rhs1
)
3372 && gimple_call_arg (g
, 0) == rhs2
)
3377 std::swap (rhs1
, rhs2
);
3382 tree arg0
= gimple_call_arg (call_stmt
, 0);
3386 tree arg1
= gimple_call_arg (call_stmt
, 1);
3387 tree arg1_len
= NULL_TREE
;
3388 int idx
= get_stridx (arg1
);
3393 arg1_len
= build_int_cst (size_type_node
, ~idx
);
3396 strinfo
*si
= get_strinfo (idx
);
3398 arg1_len
= get_string_length (si
);
3402 if (arg1_len
!= NULL_TREE
)
3404 gimple_stmt_iterator gsi
= gsi_for_stmt (call_stmt
);
3405 tree strncmp_decl
= builtin_decl_explicit (BUILT_IN_STRNCMP
);
3407 if (!is_gimple_val (arg1_len
))
3409 tree arg1_len_tmp
= make_ssa_name (TREE_TYPE (arg1_len
));
3410 gassign
*arg1_stmt
= gimple_build_assign (arg1_len_tmp
,
3412 gsi_insert_before (&gsi
, arg1_stmt
, GSI_SAME_STMT
);
3413 arg1_len
= arg1_len_tmp
;
3416 gcall
*strncmp_call
= gimple_build_call (strncmp_decl
, 3,
3417 arg0
, arg1
, arg1_len
);
3418 tree strncmp_lhs
= make_ssa_name (integer_type_node
);
3419 gimple_set_vuse (strncmp_call
, gimple_vuse (call_stmt
));
3420 gimple_call_set_lhs (strncmp_call
, strncmp_lhs
);
3421 gsi_remove (&gsi
, true);
3422 gsi_insert_before (&gsi
, strncmp_call
, GSI_SAME_STMT
);
3423 tree zero
= build_zero_cst (TREE_TYPE (strncmp_lhs
));
3425 if (is_gimple_assign (stmt
))
3427 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
3429 tree cond
= gimple_assign_rhs1 (stmt
);
3430 TREE_OPERAND (cond
, 0) = strncmp_lhs
;
3431 TREE_OPERAND (cond
, 1) = zero
;
3435 gimple_assign_set_rhs1 (stmt
, strncmp_lhs
);
3436 gimple_assign_set_rhs2 (stmt
, zero
);
3441 gcond
*cond
= as_a
<gcond
*> (stmt
);
3442 gimple_cond_set_lhs (cond
, strncmp_lhs
);
3443 gimple_cond_set_rhs (cond
, zero
);
3451 /* Attempt to check for validity of the performed access a single statement
3452 at *GSI using string length knowledge, and to optimize it.
3453 If the given basic block needs clean-up of EH, CLEANUP_EH is set to
3457 strlen_check_and_optimize_stmt (gimple_stmt_iterator
*gsi
, bool *cleanup_eh
)
3459 gimple
*stmt
= gsi_stmt (*gsi
);
3461 if (is_gimple_call (stmt
))
3463 tree callee
= gimple_call_fndecl (stmt
);
3464 if (valid_builtin_call (stmt
))
3465 switch (DECL_FUNCTION_CODE (callee
))
3467 case BUILT_IN_STRLEN
:
3468 case BUILT_IN_STRNLEN
:
3469 handle_builtin_strlen (gsi
);
3471 case BUILT_IN_STRCHR
:
3472 handle_builtin_strchr (gsi
);
3474 case BUILT_IN_STRCPY
:
3475 case BUILT_IN_STRCPY_CHK
:
3476 case BUILT_IN_STPCPY
:
3477 case BUILT_IN_STPCPY_CHK
:
3478 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3481 case BUILT_IN_STRNCAT
:
3482 case BUILT_IN_STRNCAT_CHK
:
3483 handle_builtin_strncat (DECL_FUNCTION_CODE (callee
), gsi
);
3486 case BUILT_IN_STPNCPY
:
3487 case BUILT_IN_STPNCPY_CHK
:
3488 case BUILT_IN_STRNCPY
:
3489 case BUILT_IN_STRNCPY_CHK
:
3490 handle_builtin_stxncpy (DECL_FUNCTION_CODE (callee
), gsi
);
3493 case BUILT_IN_MEMCPY
:
3494 case BUILT_IN_MEMCPY_CHK
:
3495 case BUILT_IN_MEMPCPY
:
3496 case BUILT_IN_MEMPCPY_CHK
:
3497 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3499 case BUILT_IN_STRCAT
:
3500 case BUILT_IN_STRCAT_CHK
:
3501 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
3503 case BUILT_IN_MALLOC
:
3504 case BUILT_IN_CALLOC
:
3505 handle_builtin_malloc (DECL_FUNCTION_CODE (callee
), gsi
);
3507 case BUILT_IN_MEMSET
:
3508 if (handle_builtin_memset (gsi
))
3511 case BUILT_IN_MEMCMP
:
3512 if (handle_builtin_memcmp (gsi
))
3515 case BUILT_IN_STRCMP
:
3516 case BUILT_IN_STRNCMP
:
3517 if (handle_builtin_string_cmp (gsi
))
3524 else if (is_gimple_assign (stmt
) && !gimple_clobber_p (stmt
))
3526 tree lhs
= gimple_assign_lhs (stmt
);
3528 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
3530 if (gimple_assign_single_p (stmt
)
3531 || (gimple_assign_cast_p (stmt
)
3532 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
3534 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
3535 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
3537 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
3538 handle_pointer_plus (gsi
);
3540 else if (TREE_CODE (lhs
) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
3542 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3543 if (code
== COND_EXPR
)
3545 tree cond
= gimple_assign_rhs1 (stmt
);
3546 enum tree_code cond_code
= TREE_CODE (cond
);
3548 if (cond_code
== EQ_EXPR
|| cond_code
== NE_EXPR
)
3549 fold_strstr_to_strncmp (TREE_OPERAND (cond
, 0),
3550 TREE_OPERAND (cond
, 1), stmt
);
3552 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3553 fold_strstr_to_strncmp (gimple_assign_rhs1 (stmt
),
3554 gimple_assign_rhs2 (stmt
), stmt
);
3555 else if (gimple_assign_load_p (stmt
)
3556 && TREE_CODE (TREE_TYPE (lhs
)) == INTEGER_TYPE
3557 && TYPE_MODE (TREE_TYPE (lhs
)) == TYPE_MODE (char_type_node
)
3558 && (TYPE_PRECISION (TREE_TYPE (lhs
))
3559 == TYPE_PRECISION (char_type_node
))
3560 && !gimple_has_volatile_ops (stmt
))
3562 tree off
= integer_zero_node
;
3563 unsigned HOST_WIDE_INT coff
= 0;
3565 tree rhs1
= gimple_assign_rhs1 (stmt
);
3566 if (code
== MEM_REF
)
3568 idx
= get_stridx (TREE_OPERAND (rhs1
, 0));
3571 strinfo
*si
= get_strinfo (idx
);
3573 && si
->nonzero_chars
3574 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
3575 && (wi::to_widest (si
->nonzero_chars
)
3576 >= wi::to_widest (off
)))
3577 off
= TREE_OPERAND (rhs1
, 1);
3579 /* This case is not useful. See if get_addr_stridx
3580 returns something usable. */
3585 idx
= get_addr_stridx (rhs1
, NULL_TREE
, &coff
);
3588 strinfo
*si
= get_strinfo (idx
);
3590 && si
->nonzero_chars
3591 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
3593 widest_int w1
= wi::to_widest (si
->nonzero_chars
);
3594 widest_int w2
= wi::to_widest (off
) + coff
;
3596 && si
->full_string_p
)
3598 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3600 fprintf (dump_file
, "Optimizing: ");
3601 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3604 /* Reading the final '\0' character. */
3605 tree zero
= build_int_cst (TREE_TYPE (lhs
), 0);
3606 gimple_set_vuse (stmt
, NULL_TREE
);
3607 gimple_assign_set_rhs_from_tree (gsi
, zero
);
3609 |= maybe_clean_or_replace_eh_stmt (stmt
,
3611 stmt
= gsi_stmt (*gsi
);
3614 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3616 fprintf (dump_file
, "into: ");
3617 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3622 /* Reading a character before the final '\0'
3623 character. Just set the value range to ~[0, 0]
3624 if we don't have anything better. */
3626 tree type
= TREE_TYPE (lhs
);
3627 enum value_range_type vr
3628 = get_range_info (lhs
, &min
, &max
);
3629 if (vr
== VR_VARYING
3631 && min
== wi::min_value (TYPE_PRECISION (type
),
3633 && max
== wi::max_value (TYPE_PRECISION (type
),
3635 set_range_info (lhs
, VR_ANTI_RANGE
,
3636 wi::zero (TYPE_PRECISION (type
)),
3637 wi::zero (TYPE_PRECISION (type
)));
3643 if (strlen_to_stridx
)
3645 tree rhs1
= gimple_assign_rhs1 (stmt
);
3646 if (stridx_strlenloc
*ps
= strlen_to_stridx
->get (rhs1
))
3647 strlen_to_stridx
->put (lhs
, stridx_strlenloc (*ps
));
3650 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
3652 tree type
= TREE_TYPE (lhs
);
3653 if (TREE_CODE (type
) == ARRAY_TYPE
)
3654 type
= TREE_TYPE (type
);
3655 if (TREE_CODE (type
) == INTEGER_TYPE
3656 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
3657 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
3659 if (! handle_char_store (gsi
))
3664 else if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
3666 enum tree_code code
= gimple_cond_code (cond
);
3667 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3668 fold_strstr_to_strncmp (gimple_cond_lhs (stmt
),
3669 gimple_cond_rhs (stmt
), stmt
);
3672 if (gimple_vdef (stmt
))
3673 maybe_invalidate (stmt
);
3677 /* Recursively call maybe_invalidate on stmts that might be executed
3678 in between dombb and current bb and that contain a vdef. Stop when
3679 *count stmts are inspected, or if the whole strinfo vector has
3680 been invalidated. */
3683 do_invalidate (basic_block dombb
, gimple
*phi
, bitmap visited
, int *count
)
3685 unsigned int i
, n
= gimple_phi_num_args (phi
);
3687 for (i
= 0; i
< n
; i
++)
3689 tree vuse
= gimple_phi_arg_def (phi
, i
);
3690 gimple
*stmt
= SSA_NAME_DEF_STMT (vuse
);
3691 basic_block bb
= gimple_bb (stmt
);
3694 || !bitmap_set_bit (visited
, bb
->index
)
3695 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3699 if (gimple_code (stmt
) == GIMPLE_PHI
)
3701 do_invalidate (dombb
, stmt
, visited
, count
);
3708 if (!maybe_invalidate (stmt
))
3713 vuse
= gimple_vuse (stmt
);
3714 stmt
= SSA_NAME_DEF_STMT (vuse
);
3715 if (gimple_bb (stmt
) != bb
)
3717 bb
= gimple_bb (stmt
);
3720 || !bitmap_set_bit (visited
, bb
->index
)
3721 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3728 class strlen_dom_walker
: public dom_walker
3731 strlen_dom_walker (cdi_direction direction
)
3732 : dom_walker (direction
), m_cleanup_cfg (false)
3735 virtual edge
before_dom_children (basic_block
);
3736 virtual void after_dom_children (basic_block
);
3738 /* Flag that will trigger TODO_cleanup_cfg to be returned in strlen
3739 execute function. */
3743 /* Callback for walk_dominator_tree. Attempt to optimize various
3744 string ops by remembering string lengths pointed by pointer SSA_NAMEs. */
3747 strlen_dom_walker::before_dom_children (basic_block bb
)
3749 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
3752 stridx_to_strinfo
= NULL
;
3755 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) dombb
->aux
);
3756 if (stridx_to_strinfo
)
3758 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3761 gphi
*phi
= gsi
.phi ();
3762 if (virtual_operand_p (gimple_phi_result (phi
)))
3764 bitmap visited
= BITMAP_ALLOC (NULL
);
3765 int count_vdef
= 100;
3766 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
3767 BITMAP_FREE (visited
);
3768 if (count_vdef
== 0)
3770 /* If there were too many vdefs in between immediate
3771 dominator and current bb, invalidate everything.
3772 If stridx_to_strinfo has been unshared, we need
3773 to free it, otherwise just set it to NULL. */
3774 if (!strinfo_shared ())
3780 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
3784 (*stridx_to_strinfo
)[i
] = NULL
;
3788 stridx_to_strinfo
= NULL
;
3796 /* If all PHI arguments have the same string index, the PHI result
3798 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3801 gphi
*phi
= gsi
.phi ();
3802 tree result
= gimple_phi_result (phi
);
3803 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
3805 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
3808 unsigned int i
, n
= gimple_phi_num_args (phi
);
3809 for (i
= 1; i
< n
; i
++)
3810 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
3813 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
3818 bool cleanup_eh
= false;
3820 /* Attempt to optimize individual statements. */
3821 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
3822 if (strlen_check_and_optimize_stmt (&gsi
, &cleanup_eh
))
3825 if (cleanup_eh
&& gimple_purge_dead_eh_edges (bb
))
3826 m_cleanup_cfg
= true;
3828 bb
->aux
= stridx_to_strinfo
;
3829 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
3830 (*stridx_to_strinfo
)[0] = (strinfo
*) bb
;
3834 /* Callback for walk_dominator_tree. Free strinfo vector if it is
3835 owned by the current bb, clear bb->aux. */
3838 strlen_dom_walker::after_dom_children (basic_block bb
)
3842 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) bb
->aux
);
3843 if (vec_safe_length (stridx_to_strinfo
)
3844 && (*stridx_to_strinfo
)[0] == (strinfo
*) bb
)
3849 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
3851 vec_free (stridx_to_strinfo
);
3857 /* Main entry point. */
3861 const pass_data pass_data_strlen
=
3863 GIMPLE_PASS
, /* type */
3864 "strlen", /* name */
3865 OPTGROUP_NONE
, /* optinfo_flags */
3866 TV_TREE_STRLEN
, /* tv_id */
3867 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3868 0, /* properties_provided */
3869 0, /* properties_destroyed */
3870 0, /* todo_flags_start */
3871 0, /* todo_flags_finish */
3874 class pass_strlen
: public gimple_opt_pass
3877 pass_strlen (gcc::context
*ctxt
)
3878 : gimple_opt_pass (pass_data_strlen
, ctxt
)
3881 /* opt_pass methods: */
3882 virtual bool gate (function
*) { return flag_optimize_strlen
!= 0; }
3883 virtual unsigned int execute (function
*);
3885 }; // class pass_strlen
3888 pass_strlen::execute (function
*fun
)
3890 gcc_assert (!strlen_to_stridx
);
3891 if (warn_stringop_overflow
|| warn_stringop_truncation
)
3892 strlen_to_stridx
= new hash_map
<tree
, stridx_strlenloc
> ();
3894 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
3897 calculate_dominance_info (CDI_DOMINATORS
);
3899 /* String length optimization is implemented as a walk of the dominator
3900 tree and a forward walk of statements within each block. */
3901 strlen_dom_walker
walker (CDI_DOMINATORS
);
3902 walker
.walk (fun
->cfg
->x_entry_block_ptr
);
3904 ssa_ver_to_stridx
.release ();
3905 strinfo_pool
.release ();
3906 if (decl_to_stridxlist_htab
)
3908 obstack_free (&stridx_obstack
, NULL
);
3909 delete decl_to_stridxlist_htab
;
3910 decl_to_stridxlist_htab
= NULL
;
3912 laststmt
.stmt
= NULL
;
3913 laststmt
.len
= NULL_TREE
;
3914 laststmt
.stridx
= 0;
3916 if (strlen_to_stridx
)
3918 strlen_to_stridx
->empty ();
3919 delete strlen_to_stridx
;
3920 strlen_to_stridx
= NULL
;
3923 return walker
.m_cleanup_cfg
? TODO_cleanup_cfg
: 0;
3929 make_pass_strlen (gcc::context
*ctxt
)
3931 return new pass_strlen (ctxt
);