1 /* String length optimization
2 Copyright (C) 2011-2017 Free Software Foundation, Inc.
3 Contributed by Jakub Jelinek <jakub@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "alloc-pool.h"
29 #include "tree-pass.h"
32 #include "gimple-pretty-print.h"
33 #include "fold-const.h"
34 #include "stor-layout.h"
35 #include "gimple-fold.h"
38 #include "gimple-iterator.h"
39 #include "gimplify-me.h"
43 #include "tree-ssa-propagate.h"
46 #include "tree-hash-traits.h"
50 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
51 is an index into strinfo vector, negative value stands for
52 string length of a string literal (~strlen). */
53 static vec
<int> ssa_ver_to_stridx
;
55 /* Number of currently active string indexes plus one. */
56 static int max_stridx
;
58 /* String information record. */
61 /* Number of leading characters that are known to be nonzero. This is
62 also the length of the string if FULL_STRING_P.
64 The values in a list of related string pointers must be consistent;
65 that is, if strinfo B comes X bytes after strinfo A, it must be
66 the case that A->nonzero_chars == X + B->nonzero_chars. */
68 /* Any of the corresponding pointers for querying alias oracle. */
70 /* This is used for two things:
72 - To record the statement that should be used for delayed length
73 computations. We maintain the invariant that all related strinfos
74 have delayed lengths or none do.
76 - To record the malloc or calloc call that produced this result. */
78 /* Pointer to '\0' if known, if NULL, it can be computed as
81 /* Reference count. Any changes to strinfo entry possibly shared
82 with dominating basic blocks need unshare_strinfo first, except
83 for dont_invalidate which affects only the immediately next
86 /* Copy of index. get_strinfo (si->idx) should return si; */
88 /* These 3 fields are for chaining related string pointers together.
90 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
91 strcpy (c, d); e = c + dl;
92 strinfo(a) -> strinfo(c) -> strinfo(e)
93 All have ->first field equal to strinfo(a)->idx and are doubly
94 chained through prev/next fields. The later strinfos are required
95 to point into the same string with zero or more bytes after
96 the previous pointer and all bytes in between the two pointers
97 must be non-zero. Functions like strcpy or memcpy are supposed
98 to adjust all previous strinfo lengths, but not following strinfo
99 lengths (those are uncertain, usually invalidated during
100 maybe_invalidate, except when the alias oracle knows better).
101 Functions like strcat on the other side adjust the whole
102 related strinfo chain.
103 They are updated lazily, so to use the chain the same first fields
104 and si->prev->next == si->idx needs to be verified. */
108 /* A flag whether the string is known to be written in the current
111 /* A flag for the next maybe_invalidate that this strinfo shouldn't
112 be invalidated. Always cleared by maybe_invalidate. */
113 bool dont_invalidate
;
114 /* True if the string is known to be nul-terminated after NONZERO_CHARS
115 characters. False is useful when detecting strings that are built
116 up via successive memcpys. */
120 /* Pool for allocating strinfo_struct entries. */
121 static object_allocator
<strinfo
> strinfo_pool ("strinfo pool");
123 /* Vector mapping positive string indexes to strinfo, for the
124 current basic block. The first pointer in the vector is special,
125 it is either NULL, meaning the vector isn't shared, or it is
126 a basic block pointer to the owner basic_block if shared.
127 If some other bb wants to modify the vector, the vector needs
128 to be unshared first, and only the owner bb is supposed to free it. */
129 static vec
<strinfo
*, va_heap
, vl_embed
> *stridx_to_strinfo
;
131 /* One OFFSET->IDX mapping. */
134 struct stridxlist
*next
;
135 HOST_WIDE_INT offset
;
139 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
140 struct decl_stridxlist_map
142 struct tree_map_base base
;
143 struct stridxlist list
;
146 /* Hash table for mapping decls to a chained list of offset -> idx
148 static hash_map
<tree_decl_hash
, stridxlist
> *decl_to_stridxlist_htab
;
150 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
151 static struct obstack stridx_obstack
;
153 /* Last memcpy statement if it could be adjusted if the trailing
154 '\0' written is immediately overwritten, or
155 *x = '\0' store that could be removed if it is immediately overwritten. */
156 struct laststmt_struct
163 static int get_stridx_plus_constant (strinfo
*, unsigned HOST_WIDE_INT
, tree
);
167 - 1 if SI is known to start with more than OFF nonzero characters.
169 - 0 if SI is known to start with OFF nonzero characters,
170 but is not known to start with more.
172 - -1 if SI might not start with OFF nonzero characters. */
175 compare_nonzero_chars (strinfo
*si
, unsigned HOST_WIDE_INT off
)
177 if (si
->nonzero_chars
178 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
179 return compare_tree_int (si
->nonzero_chars
, off
);
184 /* Return true if SI is known to be a zero-length string. */
187 zero_length_string_p (strinfo
*si
)
189 return si
->full_string_p
&& integer_zerop (si
->nonzero_chars
);
192 /* Return strinfo vector entry IDX. */
194 static inline strinfo
*
195 get_strinfo (int idx
)
197 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
199 return (*stridx_to_strinfo
)[idx
];
202 /* Get the next strinfo in the chain after SI, or null if none. */
204 static inline strinfo
*
205 get_next_strinfo (strinfo
*si
)
209 strinfo
*nextsi
= get_strinfo (si
->next
);
210 if (nextsi
== NULL
|| nextsi
->first
!= si
->first
|| nextsi
->prev
!= si
->idx
)
215 /* Helper function for get_stridx. Return the strinfo index of the address
216 of EXP, which is available in PTR if nonnull. If OFFSET_OUT, it is
217 OK to return the index for some X <= &EXP and store &EXP - X in
221 get_addr_stridx (tree exp
, tree ptr
, unsigned HOST_WIDE_INT
*offset_out
)
224 struct stridxlist
*list
, *last
= NULL
;
227 if (!decl_to_stridxlist_htab
)
230 base
= get_addr_base_and_unit_offset (exp
, &off
);
231 if (base
== NULL
|| !DECL_P (base
))
234 list
= decl_to_stridxlist_htab
->get (base
);
240 if (list
->offset
== off
)
246 if (list
->offset
> off
)
253 if ((offset_out
|| ptr
) && last
&& last
->idx
> 0)
255 unsigned HOST_WIDE_INT rel_off
256 = (unsigned HOST_WIDE_INT
) off
- last
->offset
;
257 strinfo
*si
= get_strinfo (last
->idx
);
258 if (si
&& compare_nonzero_chars (si
, rel_off
) >= 0)
262 *offset_out
= rel_off
;
266 return get_stridx_plus_constant (si
, rel_off
, ptr
);
272 /* Return string index for EXP. */
275 get_stridx (tree exp
)
279 if (TREE_CODE (exp
) == SSA_NAME
)
281 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)])
282 return ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)];
285 HOST_WIDE_INT off
= 0;
286 for (i
= 0; i
< 5; i
++)
288 gimple
*def_stmt
= SSA_NAME_DEF_STMT (e
);
289 if (!is_gimple_assign (def_stmt
)
290 || gimple_assign_rhs_code (def_stmt
) != POINTER_PLUS_EXPR
)
292 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
293 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
294 if (TREE_CODE (rhs1
) != SSA_NAME
295 || !tree_fits_shwi_p (rhs2
))
297 HOST_WIDE_INT this_off
= tree_to_shwi (rhs2
);
300 off
= (unsigned HOST_WIDE_INT
) off
+ this_off
;
303 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)])
306 = get_strinfo (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)]);
307 if (si
&& compare_nonzero_chars (si
, off
) >= 0)
308 return get_stridx_plus_constant (si
, off
, exp
);
315 if (TREE_CODE (exp
) == ADDR_EXPR
)
317 int idx
= get_addr_stridx (TREE_OPERAND (exp
, 0), exp
, NULL
);
322 s
= string_constant (exp
, &o
);
324 && (o
== NULL_TREE
|| tree_fits_shwi_p (o
))
325 && TREE_STRING_LENGTH (s
) > 0)
327 HOST_WIDE_INT offset
= o
? tree_to_shwi (o
) : 0;
328 const char *p
= TREE_STRING_POINTER (s
);
329 int max
= TREE_STRING_LENGTH (s
) - 1;
331 if (p
[max
] == '\0' && offset
>= 0 && offset
<= max
)
332 return ~(int) strlen (p
+ offset
);
337 /* Return true if strinfo vector is shared with the immediate dominator. */
340 strinfo_shared (void)
342 return vec_safe_length (stridx_to_strinfo
)
343 && (*stridx_to_strinfo
)[0] != NULL
;
346 /* Unshare strinfo vector that is shared with the immediate dominator. */
349 unshare_strinfo_vec (void)
354 gcc_assert (strinfo_shared ());
355 stridx_to_strinfo
= vec_safe_copy (stridx_to_strinfo
);
356 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
359 (*stridx_to_strinfo
)[0] = NULL
;
362 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
363 Return a pointer to the location where the string index can
364 be stored (if 0) or is stored, or NULL if this can't be tracked. */
367 addr_stridxptr (tree exp
)
371 tree base
= get_addr_base_and_unit_offset (exp
, &off
);
372 if (base
== NULL_TREE
|| !DECL_P (base
))
375 if (!decl_to_stridxlist_htab
)
377 decl_to_stridxlist_htab
378 = new hash_map
<tree_decl_hash
, stridxlist
> (64);
379 gcc_obstack_init (&stridx_obstack
);
383 stridxlist
*list
= &decl_to_stridxlist_htab
->get_or_insert (base
, &existed
);
387 stridxlist
*before
= NULL
;
388 for (i
= 0; i
< 32; i
++)
390 if (list
->offset
== off
)
392 if (list
->offset
> off
&& before
== NULL
)
394 if (list
->next
== NULL
)
403 before
= XOBNEW (&stridx_obstack
, struct stridxlist
);
410 list
->next
= XOBNEW (&stridx_obstack
, struct stridxlist
);
420 /* Create a new string index, or return 0 if reached limit. */
423 new_stridx (tree exp
)
426 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
428 if (TREE_CODE (exp
) == SSA_NAME
)
430 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
433 ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)] = idx
;
436 if (TREE_CODE (exp
) == ADDR_EXPR
)
438 int *pidx
= addr_stridxptr (TREE_OPERAND (exp
, 0));
441 gcc_assert (*pidx
== 0);
442 *pidx
= max_stridx
++;
449 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
452 new_addr_stridx (tree exp
)
455 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
457 pidx
= addr_stridxptr (exp
);
460 gcc_assert (*pidx
== 0);
461 *pidx
= max_stridx
++;
467 /* Create a new strinfo. */
470 new_strinfo (tree ptr
, int idx
, tree nonzero_chars
, bool full_string_p
)
472 strinfo
*si
= strinfo_pool
.allocate ();
473 si
->nonzero_chars
= nonzero_chars
;
476 si
->endptr
= NULL_TREE
;
482 si
->writable
= false;
483 si
->dont_invalidate
= false;
484 si
->full_string_p
= full_string_p
;
488 /* Decrease strinfo refcount and free it if not referenced anymore. */
491 free_strinfo (strinfo
*si
)
493 if (si
&& --si
->refcount
== 0)
494 strinfo_pool
.remove (si
);
497 /* Set strinfo in the vector entry IDX to SI. */
500 set_strinfo (int idx
, strinfo
*si
)
502 if (vec_safe_length (stridx_to_strinfo
) && (*stridx_to_strinfo
)[0])
503 unshare_strinfo_vec ();
504 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
505 vec_safe_grow_cleared (stridx_to_strinfo
, idx
+ 1);
506 (*stridx_to_strinfo
)[idx
] = si
;
509 /* Return the first strinfo in the related strinfo chain
510 if all strinfos in between belong to the chain, otherwise NULL. */
513 verify_related_strinfos (strinfo
*origsi
)
515 strinfo
*si
= origsi
, *psi
;
517 if (origsi
->first
== 0)
519 for (; si
->prev
; si
= psi
)
521 if (si
->first
!= origsi
->first
)
523 psi
= get_strinfo (si
->prev
);
526 if (psi
->next
!= si
->idx
)
529 if (si
->idx
!= si
->first
)
534 /* Set SI's endptr to ENDPTR and compute its length based on SI->ptr.
535 Use LOC for folding. */
538 set_endptr_and_length (location_t loc
, strinfo
*si
, tree endptr
)
542 tree start_as_size
= fold_convert_loc (loc
, size_type_node
, si
->ptr
);
543 tree end_as_size
= fold_convert_loc (loc
, size_type_node
, endptr
);
544 si
->nonzero_chars
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
545 end_as_size
, start_as_size
);
546 si
->full_string_p
= true;
549 /* Return string length, or NULL if it can't be computed. */
552 get_string_length (strinfo
*si
)
554 if (si
->nonzero_chars
)
555 return si
->full_string_p
? si
->nonzero_chars
: NULL
;
559 gimple
*stmt
= si
->stmt
, *lenstmt
;
560 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
561 tree callee
, lhs
, fn
, tem
;
563 gimple_stmt_iterator gsi
;
565 gcc_assert (is_gimple_call (stmt
));
566 callee
= gimple_call_fndecl (stmt
);
567 gcc_assert (callee
&& DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
);
568 lhs
= gimple_call_lhs (stmt
);
569 /* unshare_strinfo is intentionally not called here. The (delayed)
570 transformation of strcpy or strcat into stpcpy is done at the place
571 of the former strcpy/strcat call and so can affect all the strinfos
572 with the same stmt. If they were unshared before and transformation
573 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
574 just compute the right length. */
575 switch (DECL_FUNCTION_CODE (callee
))
577 case BUILT_IN_STRCAT
:
578 case BUILT_IN_STRCAT_CHK
:
579 case BUILT_IN_STRCAT_CHKP
:
580 case BUILT_IN_STRCAT_CHK_CHKP
:
581 gsi
= gsi_for_stmt (stmt
);
582 fn
= builtin_decl_implicit (BUILT_IN_STRLEN
);
583 gcc_assert (lhs
== NULL_TREE
);
584 tem
= unshare_expr (gimple_call_arg (stmt
, 0));
587 lenstmt
= gimple_build_call (chkp_maybe_create_clone (fn
)->decl
,
588 2, tem
, gimple_call_arg (stmt
, 1));
589 gimple_call_set_with_bounds (lenstmt
, true);
592 lenstmt
= gimple_build_call (fn
, 1, tem
);
593 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), lenstmt
);
594 gimple_call_set_lhs (lenstmt
, lhs
);
595 gimple_set_vuse (lenstmt
, gimple_vuse (stmt
));
596 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
597 tem
= gimple_call_arg (stmt
, 0);
598 if (!ptrofftype_p (TREE_TYPE (lhs
)))
600 lhs
= convert_to_ptrofftype (lhs
);
601 lhs
= force_gimple_operand_gsi (&gsi
, lhs
, true, NULL_TREE
,
602 true, GSI_SAME_STMT
);
604 lenstmt
= gimple_build_assign
605 (make_ssa_name (TREE_TYPE (gimple_call_arg (stmt
, 0))),
606 POINTER_PLUS_EXPR
,tem
, lhs
);
607 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
608 gimple_call_set_arg (stmt
, 0, gimple_assign_lhs (lenstmt
));
611 case BUILT_IN_STRCPY
:
612 case BUILT_IN_STRCPY_CHK
:
613 case BUILT_IN_STRCPY_CHKP
:
614 case BUILT_IN_STRCPY_CHK_CHKP
:
615 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY
));
616 if (gimple_call_num_args (stmt
) == (with_bounds
? 4 : 2))
617 fn
= builtin_decl_implicit (BUILT_IN_STPCPY
);
619 fn
= builtin_decl_explicit (BUILT_IN_STPCPY_CHK
);
621 fn
= chkp_maybe_create_clone (fn
)->decl
;
622 gcc_assert (lhs
== NULL_TREE
);
623 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
625 fprintf (dump_file
, "Optimizing: ");
626 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
628 gimple_call_set_fndecl (stmt
, fn
);
629 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), stmt
);
630 gimple_call_set_lhs (stmt
, lhs
);
632 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
634 fprintf (dump_file
, "into: ");
635 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
638 case BUILT_IN_STPCPY
:
639 case BUILT_IN_STPCPY_CHK
:
640 case BUILT_IN_STPCPY_CHKP
:
641 case BUILT_IN_STPCPY_CHK_CHKP
:
642 gcc_assert (lhs
!= NULL_TREE
);
643 loc
= gimple_location (stmt
);
644 set_endptr_and_length (loc
, si
, lhs
);
645 for (strinfo
*chainsi
= verify_related_strinfos (si
);
647 chainsi
= get_next_strinfo (chainsi
))
648 if (chainsi
->nonzero_chars
== NULL
)
649 set_endptr_and_length (loc
, chainsi
, lhs
);
651 case BUILT_IN_MALLOC
:
653 /* BUILT_IN_CALLOC always has si->nonzero_chars set. */
660 return si
->nonzero_chars
;
663 /* Invalidate string length information for strings whose length
664 might change due to stores in stmt. */
667 maybe_invalidate (gimple
*stmt
)
671 bool nonempty
= false;
673 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
676 if (!si
->dont_invalidate
)
679 /* Do not use si->nonzero_chars. */
680 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, NULL_TREE
);
681 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
683 set_strinfo (i
, NULL
);
688 si
->dont_invalidate
= false;
694 /* Unshare strinfo record SI, if it has refcount > 1 or
695 if stridx_to_strinfo vector is shared with some other
699 unshare_strinfo (strinfo
*si
)
703 if (si
->refcount
== 1 && !strinfo_shared ())
706 nsi
= new_strinfo (si
->ptr
, si
->idx
, si
->nonzero_chars
, si
->full_string_p
);
707 nsi
->stmt
= si
->stmt
;
708 nsi
->endptr
= si
->endptr
;
709 nsi
->first
= si
->first
;
710 nsi
->prev
= si
->prev
;
711 nsi
->next
= si
->next
;
712 nsi
->writable
= si
->writable
;
713 set_strinfo (si
->idx
, nsi
);
718 /* Attempt to create a new strinfo for BASESI + OFF, or find existing
719 strinfo if there is any. Return it's idx, or 0 if no strinfo has
723 get_stridx_plus_constant (strinfo
*basesi
, unsigned HOST_WIDE_INT off
,
726 if (TREE_CODE (ptr
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
729 if (compare_nonzero_chars (basesi
, off
) < 0
730 || !tree_fits_uhwi_p (basesi
->nonzero_chars
))
733 unsigned HOST_WIDE_INT nonzero_chars
734 = tree_to_uhwi (basesi
->nonzero_chars
) - off
;
735 strinfo
*si
= basesi
, *chainsi
;
736 if (si
->first
|| si
->prev
|| si
->next
)
737 si
= verify_related_strinfos (basesi
);
739 || si
->nonzero_chars
== NULL_TREE
740 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
743 if (TREE_CODE (ptr
) == SSA_NAME
744 && ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
745 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
747 gcc_checking_assert (compare_tree_int (si
->nonzero_chars
, off
) != -1);
748 for (chainsi
= si
; chainsi
->next
; chainsi
= si
)
750 si
= get_next_strinfo (chainsi
);
752 || si
->nonzero_chars
== NULL_TREE
753 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
755 int r
= compare_tree_int (si
->nonzero_chars
, nonzero_chars
);
760 if (TREE_CODE (ptr
) == SSA_NAME
)
761 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = si
->idx
;
764 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
765 if (pidx
!= NULL
&& *pidx
== 0)
774 int idx
= new_stridx (ptr
);
777 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, nonzero_chars
),
778 basesi
->full_string_p
);
779 set_strinfo (idx
, si
);
782 strinfo
*nextsi
= unshare_strinfo (get_strinfo (chainsi
->next
));
783 si
->next
= nextsi
->idx
;
786 chainsi
= unshare_strinfo (chainsi
);
787 if (chainsi
->first
== 0)
788 chainsi
->first
= chainsi
->idx
;
790 if (chainsi
->endptr
== NULL_TREE
&& zero_length_string_p (si
))
791 chainsi
->endptr
= ptr
;
792 si
->endptr
= chainsi
->endptr
;
793 si
->prev
= chainsi
->idx
;
794 si
->first
= chainsi
->first
;
795 si
->writable
= chainsi
->writable
;
799 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
800 to a zero-length string and if possible chain it to a related strinfo
801 chain whose part is or might be CHAINSI. */
804 zero_length_string (tree ptr
, strinfo
*chainsi
)
808 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
809 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
810 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
811 && ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] == 0);
813 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
817 si
= verify_related_strinfos (chainsi
);
822 /* We shouldn't mix delayed and non-delayed lengths. */
823 gcc_assert (si
->full_string_p
);
824 if (si
->endptr
== NULL_TREE
)
826 si
= unshare_strinfo (si
);
830 si
= get_next_strinfo (si
);
833 if (zero_length_string_p (chainsi
))
837 chainsi
= unshare_strinfo (chainsi
);
840 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = chainsi
->idx
;
846 /* We shouldn't mix delayed and non-delayed lengths. */
847 gcc_assert (chainsi
->full_string_p
);
848 if (chainsi
->first
|| chainsi
->prev
|| chainsi
->next
)
850 chainsi
= unshare_strinfo (chainsi
);
857 idx
= new_stridx (ptr
);
860 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, 0), true);
861 set_strinfo (idx
, si
);
865 chainsi
= unshare_strinfo (chainsi
);
866 if (chainsi
->first
== 0)
867 chainsi
->first
= chainsi
->idx
;
869 if (chainsi
->endptr
== NULL_TREE
)
870 chainsi
->endptr
= ptr
;
871 si
->prev
= chainsi
->idx
;
872 si
->first
= chainsi
->first
;
873 si
->writable
= chainsi
->writable
;
878 /* For strinfo ORIGSI whose length has been just updated, adjust other
879 related strinfos so that they match the new ORIGSI. This involves:
881 - adding ADJ to the nonzero_chars fields
882 - copying full_string_p from the new ORIGSI. */
885 adjust_related_strinfos (location_t loc
, strinfo
*origsi
, tree adj
)
887 strinfo
*si
= verify_related_strinfos (origsi
);
900 si
= unshare_strinfo (si
);
901 /* We shouldn't see delayed lengths here; the caller must have
902 calculated the old length in order to calculate the
904 gcc_assert (si
->nonzero_chars
);
905 tem
= fold_convert_loc (loc
, TREE_TYPE (si
->nonzero_chars
), adj
);
906 si
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
907 TREE_TYPE (si
->nonzero_chars
),
908 si
->nonzero_chars
, tem
);
909 si
->full_string_p
= origsi
->full_string_p
;
911 si
->endptr
= NULL_TREE
;
912 si
->dont_invalidate
= true;
914 nsi
= get_next_strinfo (si
);
921 /* Find if there are other SSA_NAME pointers equal to PTR
922 for which we don't track their string lengths yet. If so, use
926 find_equal_ptrs (tree ptr
, int idx
)
928 if (TREE_CODE (ptr
) != SSA_NAME
)
932 gimple
*stmt
= SSA_NAME_DEF_STMT (ptr
);
933 if (!is_gimple_assign (stmt
))
935 ptr
= gimple_assign_rhs1 (stmt
);
936 switch (gimple_assign_rhs_code (stmt
))
941 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)))
943 if (TREE_CODE (ptr
) == SSA_NAME
)
945 if (TREE_CODE (ptr
) != ADDR_EXPR
)
950 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
951 if (pidx
!= NULL
&& *pidx
== 0)
959 /* We might find an endptr created in this pass. Grow the
960 vector in that case. */
961 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
962 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
964 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] != 0)
966 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = idx
;
970 /* Return true if STMT is a call to a builtin function with the right
971 arguments and attributes that should be considered for optimization
975 valid_builtin_call (gimple
*stmt
)
977 if (!gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
980 tree callee
= gimple_call_fndecl (stmt
);
981 switch (DECL_FUNCTION_CODE (callee
))
983 case BUILT_IN_MEMCMP
:
984 case BUILT_IN_MEMCMP_EQ
:
985 case BUILT_IN_STRCHR
:
986 case BUILT_IN_STRCHR_CHKP
:
987 case BUILT_IN_STRLEN
:
988 case BUILT_IN_STRLEN_CHKP
:
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_MEMCPY_CHKP
:
999 case BUILT_IN_MEMCPY_CHK_CHKP
:
1000 case BUILT_IN_MEMPCPY
:
1001 case BUILT_IN_MEMPCPY_CHK
:
1002 case BUILT_IN_MEMPCPY_CHKP
:
1003 case BUILT_IN_MEMPCPY_CHK_CHKP
:
1004 case BUILT_IN_MEMSET
:
1005 case BUILT_IN_STPCPY
:
1006 case BUILT_IN_STPCPY_CHK
:
1007 case BUILT_IN_STPCPY_CHKP
:
1008 case BUILT_IN_STPCPY_CHK_CHKP
:
1009 case BUILT_IN_STRCAT
:
1010 case BUILT_IN_STRCAT_CHK
:
1011 case BUILT_IN_STRCAT_CHKP
:
1012 case BUILT_IN_STRCAT_CHK_CHKP
:
1013 case BUILT_IN_STRCPY
:
1014 case BUILT_IN_STRCPY_CHK
:
1015 case BUILT_IN_STRCPY_CHKP
:
1016 case BUILT_IN_STRCPY_CHK_CHKP
:
1017 /* The above functions should be neither const nor pure. Punt if they
1019 if (gimple_vdef (stmt
) == NULL_TREE
|| gimple_vuse (stmt
) == NULL_TREE
)
1030 /* If the last .MEM setter statement before STMT is
1031 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
1032 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
1033 just memcpy (x, y, strlen (y)). SI must be the zero length
1037 adjust_last_stmt (strinfo
*si
, gimple
*stmt
, bool is_strcat
)
1039 tree vuse
, callee
, len
;
1040 struct laststmt_struct last
= laststmt
;
1041 strinfo
*lastsi
, *firstsi
;
1042 unsigned len_arg_no
= 2;
1044 laststmt
.stmt
= NULL
;
1045 laststmt
.len
= NULL_TREE
;
1046 laststmt
.stridx
= 0;
1048 if (last
.stmt
== NULL
)
1051 vuse
= gimple_vuse (stmt
);
1052 if (vuse
== NULL_TREE
1053 || SSA_NAME_DEF_STMT (vuse
) != last
.stmt
1054 || !has_single_use (vuse
))
1057 gcc_assert (last
.stridx
> 0);
1058 lastsi
= get_strinfo (last
.stridx
);
1064 if (lastsi
->first
== 0 || lastsi
->first
!= si
->first
)
1067 firstsi
= verify_related_strinfos (si
);
1068 if (firstsi
== NULL
)
1070 while (firstsi
!= lastsi
)
1072 firstsi
= get_next_strinfo (firstsi
);
1073 if (firstsi
== NULL
)
1078 if (!is_strcat
&& !zero_length_string_p (si
))
1081 if (is_gimple_assign (last
.stmt
))
1083 gimple_stmt_iterator gsi
;
1085 if (!integer_zerop (gimple_assign_rhs1 (last
.stmt
)))
1087 if (stmt_could_throw_p (last
.stmt
))
1089 gsi
= gsi_for_stmt (last
.stmt
);
1090 unlink_stmt_vdef (last
.stmt
);
1091 release_defs (last
.stmt
);
1092 gsi_remove (&gsi
, true);
1096 if (!valid_builtin_call (last
.stmt
))
1099 callee
= gimple_call_fndecl (last
.stmt
);
1100 switch (DECL_FUNCTION_CODE (callee
))
1102 case BUILT_IN_MEMCPY
:
1103 case BUILT_IN_MEMCPY_CHK
:
1105 case BUILT_IN_MEMCPY_CHKP
:
1106 case BUILT_IN_MEMCPY_CHK_CHKP
:
1113 len
= gimple_call_arg (last
.stmt
, len_arg_no
);
1114 if (tree_fits_uhwi_p (len
))
1116 if (!tree_fits_uhwi_p (last
.len
)
1117 || integer_zerop (len
)
1118 || tree_to_uhwi (len
) != tree_to_uhwi (last
.len
) + 1)
1120 /* Don't adjust the length if it is divisible by 4, it is more efficient
1121 to store the extra '\0' in that case. */
1122 if ((tree_to_uhwi (len
) & 3) == 0)
1125 else if (TREE_CODE (len
) == SSA_NAME
)
1127 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1128 if (!is_gimple_assign (def_stmt
)
1129 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1130 || gimple_assign_rhs1 (def_stmt
) != last
.len
1131 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1137 gimple_call_set_arg (last
.stmt
, len_arg_no
, last
.len
);
1138 update_stmt (last
.stmt
);
1141 /* Handle a strlen call. If strlen of the argument is known, replace
1142 the strlen call with the known value, otherwise remember that strlen
1143 of the argument is stored in the lhs SSA_NAME. */
1146 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
1150 gimple
*stmt
= gsi_stmt (*gsi
);
1151 tree lhs
= gimple_call_lhs (stmt
);
1153 if (lhs
== NULL_TREE
)
1156 src
= gimple_call_arg (stmt
, 0);
1157 idx
= get_stridx (src
);
1164 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
1168 si
= get_strinfo (idx
);
1170 rhs
= get_string_length (si
);
1172 if (rhs
!= NULL_TREE
)
1174 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1176 fprintf (dump_file
, "Optimizing: ");
1177 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1179 rhs
= unshare_expr (rhs
);
1180 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
1181 rhs
= fold_convert_loc (gimple_location (stmt
),
1182 TREE_TYPE (lhs
), rhs
);
1183 if (!update_call_from_tree (gsi
, rhs
))
1184 gimplify_and_update_call_from_tree (gsi
, rhs
);
1185 stmt
= gsi_stmt (*gsi
);
1187 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1189 fprintf (dump_file
, "into: ");
1190 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1193 && TREE_CODE (si
->nonzero_chars
) != SSA_NAME
1194 && TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
1195 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1197 si
= unshare_strinfo (si
);
1198 si
->nonzero_chars
= lhs
;
1199 gcc_assert (si
->full_string_p
);
1204 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1207 idx
= new_stridx (src
);
1210 strinfo
*si
= get_strinfo (idx
);
1213 if (!si
->full_string_p
&& !si
->stmt
)
1215 /* Until now we only had a lower bound on the string length.
1216 Install LHS as the actual length. */
1217 si
= unshare_strinfo (si
);
1218 tree old
= si
->nonzero_chars
;
1219 si
->nonzero_chars
= lhs
;
1220 si
->full_string_p
= true;
1221 if (TREE_CODE (old
) == INTEGER_CST
)
1223 location_t loc
= gimple_location (stmt
);
1224 old
= fold_convert_loc (loc
, TREE_TYPE (lhs
), old
);
1225 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1226 TREE_TYPE (lhs
), lhs
, old
);
1227 adjust_related_strinfos (loc
, si
, adj
);
1241 strinfo
*si
= new_strinfo (src
, idx
, lhs
, true);
1242 set_strinfo (idx
, si
);
1243 find_equal_ptrs (src
, idx
);
1247 /* Handle a strchr call. If strlen of the first argument is known, replace
1248 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
1249 that lhs of the call is endptr and strlen of the argument is endptr - x. */
1252 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
1256 gimple
*stmt
= gsi_stmt (*gsi
);
1257 tree lhs
= gimple_call_lhs (stmt
);
1258 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1260 if (lhs
== NULL_TREE
)
1263 if (!integer_zerop (gimple_call_arg (stmt
, with_bounds
? 2 : 1)))
1266 src
= gimple_call_arg (stmt
, 0);
1267 idx
= get_stridx (src
);
1274 rhs
= build_int_cst (size_type_node
, ~idx
);
1278 si
= get_strinfo (idx
);
1280 rhs
= get_string_length (si
);
1282 if (rhs
!= NULL_TREE
)
1284 location_t loc
= gimple_location (stmt
);
1286 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1288 fprintf (dump_file
, "Optimizing: ");
1289 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1291 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
1293 rhs
= unshare_expr (si
->endptr
);
1294 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1296 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1300 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1301 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1302 TREE_TYPE (src
), src
, rhs
);
1303 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1305 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1307 if (!update_call_from_tree (gsi
, rhs
))
1308 gimplify_and_update_call_from_tree (gsi
, rhs
);
1309 stmt
= gsi_stmt (*gsi
);
1311 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1313 fprintf (dump_file
, "into: ");
1314 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1317 && si
->endptr
== NULL_TREE
1318 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1320 si
= unshare_strinfo (si
);
1323 zero_length_string (lhs
, si
);
1327 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1329 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1332 idx
= new_stridx (src
);
1333 else if (get_strinfo (idx
) != NULL
)
1335 zero_length_string (lhs
, NULL
);
1340 location_t loc
= gimple_location (stmt
);
1341 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1342 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1343 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1344 size_type_node
, lhsu
, srcu
);
1345 strinfo
*si
= new_strinfo (src
, idx
, length
, true);
1347 set_strinfo (idx
, si
);
1348 find_equal_ptrs (src
, idx
);
1349 zero_length_string (lhs
, si
);
1353 zero_length_string (lhs
, NULL
);
1356 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1357 If strlen of the second argument is known, strlen of the first argument
1358 is the same after this call. Furthermore, attempt to convert it to
1362 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1365 tree src
, dst
, srclen
, len
, lhs
, args
, type
, fn
, oldlen
;
1367 gimple
*stmt
= gsi_stmt (*gsi
);
1368 strinfo
*si
, *dsi
, *olddsi
, *zsi
;
1370 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1372 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1373 dst
= gimple_call_arg (stmt
, 0);
1374 lhs
= gimple_call_lhs (stmt
);
1375 idx
= get_stridx (src
);
1378 si
= get_strinfo (idx
);
1380 didx
= get_stridx (dst
);
1384 olddsi
= get_strinfo (didx
);
1389 adjust_last_stmt (olddsi
, stmt
, false);
1393 srclen
= get_string_length (si
);
1395 srclen
= build_int_cst (size_type_node
, ~idx
);
1397 loc
= gimple_location (stmt
);
1398 if (srclen
== NULL_TREE
)
1401 case BUILT_IN_STRCPY
:
1402 case BUILT_IN_STRCPY_CHK
:
1403 case BUILT_IN_STRCPY_CHKP
:
1404 case BUILT_IN_STRCPY_CHK_CHKP
:
1405 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1408 case BUILT_IN_STPCPY
:
1409 case BUILT_IN_STPCPY_CHK
:
1410 case BUILT_IN_STPCPY_CHKP
:
1411 case BUILT_IN_STPCPY_CHK_CHKP
:
1412 if (lhs
== NULL_TREE
)
1416 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1417 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1418 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1428 didx
= new_stridx (dst
);
1434 oldlen
= olddsi
->nonzero_chars
;
1435 dsi
= unshare_strinfo (olddsi
);
1436 dsi
->nonzero_chars
= srclen
;
1437 dsi
->full_string_p
= (srclen
!= NULL_TREE
);
1438 /* Break the chain, so adjust_related_strinfo on later pointers in
1439 the chain won't adjust this one anymore. */
1442 dsi
->endptr
= NULL_TREE
;
1446 dsi
= new_strinfo (dst
, didx
, srclen
, srclen
!= NULL_TREE
);
1447 set_strinfo (didx
, dsi
);
1448 find_equal_ptrs (dst
, didx
);
1450 dsi
->writable
= true;
1451 dsi
->dont_invalidate
= true;
1453 if (dsi
->nonzero_chars
== NULL_TREE
)
1457 /* If string length of src is unknown, use delayed length
1458 computation. If string lenth of dst will be needed, it
1459 can be computed by transforming this strcpy call into
1460 stpcpy and subtracting dst from the return value. */
1462 /* Look for earlier strings whose length could be determined if
1463 this strcpy is turned into an stpcpy. */
1465 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1467 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1469 /* When setting a stmt for delayed length computation
1470 prevent all strinfos through dsi from being
1472 chainsi
= unshare_strinfo (chainsi
);
1473 chainsi
->stmt
= stmt
;
1474 chainsi
->nonzero_chars
= NULL_TREE
;
1475 chainsi
->full_string_p
= false;
1476 chainsi
->endptr
= NULL_TREE
;
1477 chainsi
->dont_invalidate
= true;
1486 tree adj
= NULL_TREE
;
1487 if (oldlen
== NULL_TREE
)
1489 else if (integer_zerop (oldlen
))
1491 else if (TREE_CODE (oldlen
) == INTEGER_CST
1492 || TREE_CODE (srclen
) == INTEGER_CST
)
1493 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1494 TREE_TYPE (srclen
), srclen
,
1495 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1497 if (adj
!= NULL_TREE
)
1498 adjust_related_strinfos (loc
, dsi
, adj
);
1502 /* strcpy src may not overlap dst, so src doesn't need to be
1503 invalidated either. */
1505 si
->dont_invalidate
= true;
1511 case BUILT_IN_STRCPY
:
1512 case BUILT_IN_STRCPY_CHKP
:
1513 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1515 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1517 case BUILT_IN_STRCPY_CHK
:
1518 case BUILT_IN_STRCPY_CHK_CHKP
:
1519 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1521 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1523 case BUILT_IN_STPCPY
:
1524 case BUILT_IN_STPCPY_CHKP
:
1525 /* This would need adjustment of the lhs (subtract one),
1526 or detection that the trailing '\0' doesn't need to be
1527 written, if it will be immediately overwritten.
1528 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1532 zsi
= zero_length_string (lhs
, dsi
);
1535 case BUILT_IN_STPCPY_CHK
:
1536 case BUILT_IN_STPCPY_CHK_CHKP
:
1537 /* This would need adjustment of the lhs (subtract one),
1538 or detection that the trailing '\0' doesn't need to be
1539 written, if it will be immediately overwritten.
1540 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1544 zsi
= zero_length_string (lhs
, dsi
);
1551 zsi
->dont_invalidate
= true;
1553 if (fn
== NULL_TREE
)
1556 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1557 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1559 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1560 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1561 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1563 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1565 fprintf (dump_file
, "Optimizing: ");
1566 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1570 fn
= chkp_maybe_create_clone (fn
)->decl
;
1571 if (gimple_call_num_args (stmt
) == 4)
1572 success
= update_gimple_call (gsi
, fn
, 5, dst
,
1573 gimple_call_arg (stmt
, 1),
1575 gimple_call_arg (stmt
, 3),
1578 success
= update_gimple_call (gsi
, fn
, 6, dst
,
1579 gimple_call_arg (stmt
, 1),
1581 gimple_call_arg (stmt
, 3),
1583 gimple_call_arg (stmt
, 4));
1586 if (gimple_call_num_args (stmt
) == 2)
1587 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1589 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1590 gimple_call_arg (stmt
, 2));
1593 stmt
= gsi_stmt (*gsi
);
1594 gimple_call_set_with_bounds (stmt
, with_bounds
);
1596 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1598 fprintf (dump_file
, "into: ");
1599 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1601 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1602 laststmt
.stmt
= stmt
;
1603 laststmt
.len
= srclen
;
1604 laststmt
.stridx
= dsi
->idx
;
1606 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1607 fprintf (dump_file
, "not possible.\n");
1610 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1611 If strlen of the second argument is known and length of the third argument
1612 is that plus one, strlen of the first argument is the same after this
1616 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1619 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
1620 gimple
*stmt
= gsi_stmt (*gsi
);
1621 strinfo
*si
, *dsi
, *olddsi
;
1622 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1624 len
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
1625 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1626 dst
= gimple_call_arg (stmt
, 0);
1627 idx
= get_stridx (src
);
1631 didx
= get_stridx (dst
);
1634 olddsi
= get_strinfo (didx
);
1639 && tree_fits_uhwi_p (len
)
1640 && !integer_zerop (len
))
1641 adjust_last_stmt (olddsi
, stmt
, false);
1648 /* Handle memcpy (x, y, l) where l's relationship with strlen (y)
1650 si
= get_strinfo (idx
);
1651 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
1653 if (TREE_CODE (len
) == INTEGER_CST
1654 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
1656 if (tree_int_cst_le (len
, si
->nonzero_chars
))
1658 /* Copying LEN nonzero characters, where LEN is constant. */
1660 full_string_p
= false;
1664 /* Copying the whole of the analyzed part of SI. */
1665 newlen
= si
->nonzero_chars
;
1666 full_string_p
= si
->full_string_p
;
1671 if (!si
->full_string_p
)
1673 if (TREE_CODE (len
) != SSA_NAME
)
1675 def_stmt
= SSA_NAME_DEF_STMT (len
);
1676 if (!is_gimple_assign (def_stmt
)
1677 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1678 || gimple_assign_rhs1 (def_stmt
) != si
->nonzero_chars
1679 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1681 /* Copying variable-length string SI (and no more). */
1682 newlen
= si
->nonzero_chars
;
1683 full_string_p
= true;
1689 /* Handle memcpy (x, "abcd", 5) or
1690 memcpy (x, "abc\0uvw", 7). */
1691 if (!tree_fits_uhwi_p (len
))
1694 unsigned HOST_WIDE_INT clen
= tree_to_uhwi (len
);
1695 unsigned HOST_WIDE_INT nonzero_chars
= ~idx
;
1696 newlen
= build_int_cst (size_type_node
, MIN (nonzero_chars
, clen
));
1697 full_string_p
= clen
> nonzero_chars
;
1700 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
1701 adjust_last_stmt (olddsi
, stmt
, false);
1705 didx
= new_stridx (dst
);
1712 dsi
= unshare_strinfo (olddsi
);
1713 oldlen
= olddsi
->nonzero_chars
;
1714 dsi
->nonzero_chars
= newlen
;
1715 dsi
->full_string_p
= full_string_p
;
1716 /* Break the chain, so adjust_related_strinfo on later pointers in
1717 the chain won't adjust this one anymore. */
1720 dsi
->endptr
= NULL_TREE
;
1724 dsi
= new_strinfo (dst
, didx
, newlen
, full_string_p
);
1725 set_strinfo (didx
, dsi
);
1726 find_equal_ptrs (dst
, didx
);
1728 dsi
->writable
= true;
1729 dsi
->dont_invalidate
= true;
1732 tree adj
= NULL_TREE
;
1733 location_t loc
= gimple_location (stmt
);
1734 if (oldlen
== NULL_TREE
)
1736 else if (integer_zerop (oldlen
))
1738 else if (TREE_CODE (oldlen
) == INTEGER_CST
1739 || TREE_CODE (newlen
) == INTEGER_CST
)
1740 adj
= fold_build2_loc (loc
, MINUS_EXPR
, TREE_TYPE (newlen
), newlen
,
1741 fold_convert_loc (loc
, TREE_TYPE (newlen
),
1743 if (adj
!= NULL_TREE
)
1744 adjust_related_strinfos (loc
, dsi
, adj
);
1748 /* memcpy src may not overlap dst, so src doesn't need to be
1749 invalidated either. */
1751 si
->dont_invalidate
= true;
1755 lhs
= gimple_call_lhs (stmt
);
1758 case BUILT_IN_MEMCPY
:
1759 case BUILT_IN_MEMCPY_CHK
:
1760 case BUILT_IN_MEMCPY_CHKP
:
1761 case BUILT_IN_MEMCPY_CHK_CHKP
:
1762 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1763 laststmt
.stmt
= stmt
;
1764 laststmt
.len
= dsi
->nonzero_chars
;
1765 laststmt
.stridx
= dsi
->idx
;
1767 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1769 case BUILT_IN_MEMPCPY
:
1770 case BUILT_IN_MEMPCPY_CHK
:
1771 case BUILT_IN_MEMPCPY_CHKP
:
1772 case BUILT_IN_MEMPCPY_CHK_CHKP
:
1780 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
1781 If strlen of the second argument is known, strlen of the first argument
1782 is increased by the length of the second argument. Furthermore, attempt
1783 to convert it to memcpy/strcpy if the length of the first argument
1787 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1790 tree src
, dst
, srclen
, dstlen
, len
, lhs
, args
, type
, fn
, objsz
, endptr
;
1792 gimple
*stmt
= gsi_stmt (*gsi
);
1795 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1797 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1798 dst
= gimple_call_arg (stmt
, 0);
1799 lhs
= gimple_call_lhs (stmt
);
1801 didx
= get_stridx (dst
);
1807 dsi
= get_strinfo (didx
);
1808 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
1810 /* strcat (p, q) can be transformed into
1811 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
1812 with length endptr - p if we need to compute the length
1813 later on. Don't do this transformation if we don't need
1815 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
1819 didx
= new_stridx (dst
);
1825 dsi
= new_strinfo (dst
, didx
, NULL_TREE
, false);
1826 set_strinfo (didx
, dsi
);
1827 find_equal_ptrs (dst
, didx
);
1831 dsi
= unshare_strinfo (dsi
);
1832 dsi
->nonzero_chars
= NULL_TREE
;
1833 dsi
->full_string_p
= false;
1835 dsi
->endptr
= NULL_TREE
;
1837 dsi
->writable
= true;
1839 dsi
->dont_invalidate
= true;
1846 idx
= get_stridx (src
);
1848 srclen
= build_int_cst (size_type_node
, ~idx
);
1851 si
= get_strinfo (idx
);
1853 srclen
= get_string_length (si
);
1856 loc
= gimple_location (stmt
);
1857 dstlen
= dsi
->nonzero_chars
;
1858 endptr
= dsi
->endptr
;
1860 dsi
= unshare_strinfo (dsi
);
1861 dsi
->endptr
= NULL_TREE
;
1863 dsi
->writable
= true;
1865 if (srclen
!= NULL_TREE
)
1867 dsi
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
1868 TREE_TYPE (dsi
->nonzero_chars
),
1869 dsi
->nonzero_chars
, srclen
);
1870 gcc_assert (dsi
->full_string_p
);
1871 adjust_related_strinfos (loc
, dsi
, srclen
);
1872 dsi
->dont_invalidate
= true;
1876 dsi
->nonzero_chars
= NULL
;
1877 dsi
->full_string_p
= false;
1878 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1879 dsi
->dont_invalidate
= true;
1883 /* strcat src may not overlap dst, so src doesn't need to be
1884 invalidated either. */
1885 si
->dont_invalidate
= true;
1887 /* For now. Could remove the lhs from the call and add
1888 lhs = dst; afterwards. */
1896 case BUILT_IN_STRCAT
:
1897 case BUILT_IN_STRCAT_CHKP
:
1898 if (srclen
!= NULL_TREE
)
1899 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1901 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
1903 case BUILT_IN_STRCAT_CHK
:
1904 case BUILT_IN_STRCAT_CHK_CHKP
:
1905 if (srclen
!= NULL_TREE
)
1906 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1908 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
1909 objsz
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
1915 if (fn
== NULL_TREE
)
1919 if (srclen
!= NULL_TREE
)
1921 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1922 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1924 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1925 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
1926 build_int_cst (type
, 1));
1927 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1931 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
1933 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1934 TREE_TYPE (dst
), unshare_expr (dst
),
1935 fold_convert_loc (loc
, sizetype
,
1936 unshare_expr (dstlen
)));
1937 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
1939 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1941 fprintf (dump_file
, "Optimizing: ");
1942 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1946 fn
= chkp_maybe_create_clone (fn
)->decl
;
1947 if (srclen
!= NULL_TREE
)
1948 success
= update_gimple_call (gsi
, fn
, 5 + (objsz
!= NULL_TREE
),
1950 gimple_call_arg (stmt
, 1),
1952 gimple_call_arg (stmt
, 3),
1955 success
= update_gimple_call (gsi
, fn
, 4 + (objsz
!= NULL_TREE
),
1957 gimple_call_arg (stmt
, 1),
1959 gimple_call_arg (stmt
, 3),
1963 if (srclen
!= NULL_TREE
)
1964 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
1965 dst
, src
, len
, objsz
);
1967 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
1971 stmt
= gsi_stmt (*gsi
);
1972 gimple_call_set_with_bounds (stmt
, with_bounds
);
1974 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1976 fprintf (dump_file
, "into: ");
1977 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1979 /* If srclen == NULL, note that current string length can be
1980 computed by transforming this strcpy into stpcpy. */
1981 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
1983 adjust_last_stmt (dsi
, stmt
, true);
1984 if (srclen
!= NULL_TREE
)
1986 laststmt
.stmt
= stmt
;
1987 laststmt
.len
= srclen
;
1988 laststmt
.stridx
= dsi
->idx
;
1991 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1992 fprintf (dump_file
, "not possible.\n");
1995 /* Handle a call to malloc or calloc. */
1998 handle_builtin_malloc (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2000 gimple
*stmt
= gsi_stmt (*gsi
);
2001 tree lhs
= gimple_call_lhs (stmt
);
2002 if (lhs
== NULL_TREE
)
2005 gcc_assert (get_stridx (lhs
) == 0);
2006 int idx
= new_stridx (lhs
);
2007 tree length
= NULL_TREE
;
2008 if (bcode
== BUILT_IN_CALLOC
)
2009 length
= build_int_cst (size_type_node
, 0);
2010 strinfo
*si
= new_strinfo (lhs
, idx
, length
, length
!= NULL_TREE
);
2011 if (bcode
== BUILT_IN_CALLOC
)
2013 set_strinfo (idx
, si
);
2014 si
->writable
= true;
2016 si
->dont_invalidate
= true;
2019 /* Handle a call to memset.
2020 After a call to calloc, memset(,0,) is unnecessary.
2021 memset(malloc(n),0,n) is calloc(n,1). */
2024 handle_builtin_memset (gimple_stmt_iterator
*gsi
)
2026 gimple
*stmt2
= gsi_stmt (*gsi
);
2027 if (!integer_zerop (gimple_call_arg (stmt2
, 1)))
2029 tree ptr
= gimple_call_arg (stmt2
, 0);
2030 int idx1
= get_stridx (ptr
);
2033 strinfo
*si1
= get_strinfo (idx1
);
2036 gimple
*stmt1
= si1
->stmt
;
2037 if (!stmt1
|| !is_gimple_call (stmt1
))
2039 tree callee1
= gimple_call_fndecl (stmt1
);
2040 if (!valid_builtin_call (stmt1
))
2042 enum built_in_function code1
= DECL_FUNCTION_CODE (callee1
);
2043 tree size
= gimple_call_arg (stmt2
, 2);
2044 if (code1
== BUILT_IN_CALLOC
)
2045 /* Not touching stmt1 */ ;
2046 else if (code1
== BUILT_IN_MALLOC
2047 && operand_equal_p (gimple_call_arg (stmt1
, 0), size
, 0))
2049 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt1
);
2050 update_gimple_call (&gsi1
, builtin_decl_implicit (BUILT_IN_CALLOC
), 2,
2051 size
, build_one_cst (size_type_node
));
2052 si1
->nonzero_chars
= build_int_cst (size_type_node
, 0);
2053 si1
->full_string_p
= true;
2054 si1
->stmt
= gsi_stmt (gsi1
);
2058 tree lhs
= gimple_call_lhs (stmt2
);
2059 unlink_stmt_vdef (stmt2
);
2062 gimple
*assign
= gimple_build_assign (lhs
, ptr
);
2063 gsi_replace (gsi
, assign
, false);
2067 gsi_remove (gsi
, true);
2068 release_defs (stmt2
);
2074 /* Handle a call to memcmp. We try to handle small comparisons by
2075 converting them to load and compare, and replacing the call to memcmp
2076 with a __builtin_memcmp_eq call where possible. */
2079 handle_builtin_memcmp (gimple_stmt_iterator
*gsi
)
2081 gcall
*stmt2
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2082 tree res
= gimple_call_lhs (stmt2
);
2083 tree arg1
= gimple_call_arg (stmt2
, 0);
2084 tree arg2
= gimple_call_arg (stmt2
, 1);
2085 tree len
= gimple_call_arg (stmt2
, 2);
2086 unsigned HOST_WIDE_INT leni
;
2087 use_operand_p use_p
;
2088 imm_use_iterator iter
;
2093 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
2095 gimple
*ustmt
= USE_STMT (use_p
);
2097 if (is_gimple_debug (ustmt
))
2099 if (gimple_code (ustmt
) == GIMPLE_ASSIGN
)
2101 gassign
*asgn
= as_a
<gassign
*> (ustmt
);
2102 tree_code code
= gimple_assign_rhs_code (asgn
);
2103 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2104 || !integer_zerop (gimple_assign_rhs2 (asgn
)))
2107 else if (gimple_code (ustmt
) == GIMPLE_COND
)
2109 tree_code code
= gimple_cond_code (ustmt
);
2110 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2111 || !integer_zerop (gimple_cond_rhs (ustmt
)))
2118 if (tree_fits_uhwi_p (len
)
2119 && (leni
= tree_to_uhwi (len
)) <= GET_MODE_SIZE (word_mode
)
2120 && pow2p_hwi (leni
))
2122 leni
*= CHAR_TYPE_SIZE
;
2123 unsigned align1
= get_pointer_alignment (arg1
);
2124 unsigned align2
= get_pointer_alignment (arg2
);
2125 unsigned align
= MIN (align1
, align2
);
2126 scalar_int_mode mode
;
2127 if (int_mode_for_size (leni
, 1).exists (&mode
)
2128 && (align
>= leni
|| !targetm
.slow_unaligned_access (mode
, align
)))
2130 location_t loc
= gimple_location (stmt2
);
2132 type
= build_nonstandard_integer_type (leni
, 1);
2133 gcc_assert (GET_MODE_BITSIZE (TYPE_MODE (type
)) == leni
);
2134 tree ptrtype
= build_pointer_type_for_mode (char_type_node
,
2136 off
= build_int_cst (ptrtype
, 0);
2137 arg1
= build2_loc (loc
, MEM_REF
, type
, arg1
, off
);
2138 arg2
= build2_loc (loc
, MEM_REF
, type
, arg2
, off
);
2139 tree tem1
= fold_const_aggregate_ref (arg1
);
2142 tree tem2
= fold_const_aggregate_ref (arg2
);
2145 res
= fold_convert_loc (loc
, TREE_TYPE (res
),
2146 fold_build2_loc (loc
, NE_EXPR
,
2149 gimplify_and_update_call_from_tree (gsi
, res
);
2154 gimple_call_set_fndecl (stmt2
, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ
));
2158 /* Handle a POINTER_PLUS_EXPR statement.
2159 For p = "abcd" + 2; compute associated length, or if
2160 p = q + off is pointing to a '\0' character of a string, call
2161 zero_length_string on it. */
2164 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
2166 gimple
*stmt
= gsi_stmt (*gsi
);
2167 tree lhs
= gimple_assign_lhs (stmt
), off
;
2168 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
2176 tree off
= gimple_assign_rhs2 (stmt
);
2177 if (tree_fits_uhwi_p (off
)
2178 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
2179 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
2180 = ~(~idx
- (int) tree_to_uhwi (off
));
2184 si
= get_strinfo (idx
);
2185 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
2188 off
= gimple_assign_rhs2 (stmt
);
2190 if (si
->full_string_p
&& operand_equal_p (si
->nonzero_chars
, off
, 0))
2191 zsi
= zero_length_string (lhs
, si
);
2192 else if (TREE_CODE (off
) == SSA_NAME
)
2194 gimple
*def_stmt
= SSA_NAME_DEF_STMT (off
);
2195 if (gimple_assign_single_p (def_stmt
)
2196 && si
->full_string_p
2197 && operand_equal_p (si
->nonzero_chars
,
2198 gimple_assign_rhs1 (def_stmt
), 0))
2199 zsi
= zero_length_string (lhs
, si
);
2202 && si
->endptr
!= NULL_TREE
2203 && si
->endptr
!= lhs
2204 && TREE_CODE (si
->endptr
) == SSA_NAME
)
2206 enum tree_code rhs_code
2207 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
2208 ? SSA_NAME
: NOP_EXPR
;
2209 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
);
2210 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2215 /* Handle a single character store. */
2218 handle_char_store (gimple_stmt_iterator
*gsi
)
2222 gimple
*stmt
= gsi_stmt (*gsi
);
2223 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
2224 tree rhs
= gimple_assign_rhs1 (stmt
);
2225 unsigned HOST_WIDE_INT offset
= 0;
2227 if (TREE_CODE (lhs
) == MEM_REF
2228 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
2230 tree mem_offset
= TREE_OPERAND (lhs
, 1);
2231 if (tree_fits_uhwi_p (mem_offset
))
2233 /* Get the strinfo for the base, and use it if it starts with at
2234 least OFFSET nonzero characters. This is trivially true if
2236 offset
= tree_to_uhwi (mem_offset
);
2237 idx
= get_stridx (TREE_OPERAND (lhs
, 0));
2239 si
= get_strinfo (idx
);
2241 ssaname
= TREE_OPERAND (lhs
, 0);
2242 else if (si
== NULL
|| compare_nonzero_chars (si
, offset
) < 0)
2248 idx
= get_addr_stridx (lhs
, NULL_TREE
, &offset
);
2250 si
= get_strinfo (idx
);
2253 bool storing_zero_p
= initializer_zerop (rhs
);
2254 bool storing_nonzero_p
= (!storing_zero_p
2255 && TREE_CODE (rhs
) == INTEGER_CST
2256 && integer_nonzerop (rhs
));
2260 int cmp
= compare_nonzero_chars (si
, offset
);
2261 gcc_assert (offset
== 0 || cmp
>= 0);
2262 if (storing_zero_p
&& cmp
== 0 && si
->full_string_p
)
2264 /* When overwriting a '\0' with a '\0', the store can be removed
2265 if we know it has been stored in the current function. */
2266 if (!stmt_could_throw_p (stmt
) && si
->writable
)
2268 unlink_stmt_vdef (stmt
);
2269 release_defs (stmt
);
2270 gsi_remove (gsi
, true);
2275 si
->writable
= true;
2280 /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0',
2281 and if we aren't storing '\0', we know that the length of the
2282 string and any other zero terminated string in memory remains
2283 the same. In that case we move to the next gimple statement and
2284 return to signal the caller that it shouldn't invalidate anything.
2286 This is benefical for cases like:
2291 strcpy (p, "foobar");
2292 size_t len = strlen (p); // This can be optimized into 6
2293 size_t len2 = strlen (q); // This has to be computed
2295 size_t len3 = strlen (p); // This can be optimized into 6
2296 size_t len4 = strlen (q); // This can be optimized into len2
2297 bar (len, len2, len3, len4);
2300 else if (storing_nonzero_p
&& cmp
> 0)
2305 else if (storing_zero_p
|| storing_nonzero_p
|| (offset
!= 0 && cmp
> 0))
2307 /* When storing_nonzero_p, we know that the string now starts
2308 with OFFSET + 1 nonzero characters, but don't know whether
2309 there's a following nul terminator.
2311 When storing_zero_p, we know that the string is now OFFSET
2314 Otherwise, we're storing an unknown value at offset OFFSET,
2315 so need to clip the nonzero_chars to OFFSET. */
2316 location_t loc
= gimple_location (stmt
);
2317 tree oldlen
= si
->nonzero_chars
;
2318 if (cmp
== 0 && si
->full_string_p
)
2319 /* We're overwriting the nul terminator with a nonzero or
2320 unknown character. If the previous stmt was a memcpy,
2321 its length may be decreased. */
2322 adjust_last_stmt (si
, stmt
, false);
2323 si
= unshare_strinfo (si
);
2324 if (storing_nonzero_p
)
2325 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
+ 1);
2327 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
);
2328 si
->full_string_p
= storing_zero_p
;
2331 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
2332 si
->endptr
= ssaname
;
2337 si
->writable
= true;
2338 si
->dont_invalidate
= true;
2341 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
2342 si
->nonzero_chars
, oldlen
);
2343 adjust_related_strinfos (loc
, si
, adj
);
2349 else if (idx
== 0 && (storing_zero_p
|| storing_nonzero_p
))
2352 idx
= new_stridx (ssaname
);
2354 idx
= new_addr_stridx (lhs
);
2357 tree ptr
= (ssaname
? ssaname
: build_fold_addr_expr (lhs
));
2358 tree len
= storing_nonzero_p
? size_one_node
: size_zero_node
;
2359 si
= new_strinfo (ptr
, idx
, len
, storing_zero_p
);
2360 set_strinfo (idx
, si
);
2363 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
2364 si
->endptr
= ssaname
;
2365 si
->dont_invalidate
= true;
2366 si
->writable
= true;
2370 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == STRING_CST
2371 && ssaname
== NULL_TREE
2372 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
2374 size_t l
= strlen (TREE_STRING_POINTER (gimple_assign_rhs1 (stmt
)));
2375 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
2376 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> l
)
2378 int idx
= new_addr_stridx (lhs
);
2381 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
2382 build_int_cst (size_type_node
, l
), true);
2383 set_strinfo (idx
, si
);
2384 si
->dont_invalidate
= true;
2389 if (si
!= NULL
&& offset
== 0 && storing_zero_p
)
2391 /* Allow adjust_last_stmt to remove it if the stored '\0'
2392 is immediately overwritten. */
2393 laststmt
.stmt
= stmt
;
2394 laststmt
.len
= build_int_cst (size_type_node
, 1);
2395 laststmt
.stridx
= si
->idx
;
2400 /* Try to fold strstr (s, t) eq/ne s to strncmp (s, t, strlen (t)) eq/ne 0. */
2403 fold_strstr_to_strncmp (tree rhs1
, tree rhs2
, gimple
*stmt
)
2405 if (TREE_CODE (rhs1
) != SSA_NAME
2406 || TREE_CODE (rhs2
) != SSA_NAME
)
2409 gimple
*call_stmt
= NULL
;
2410 for (int pass
= 0; pass
< 2; pass
++)
2412 gimple
*g
= SSA_NAME_DEF_STMT (rhs1
);
2413 if (gimple_call_builtin_p (g
, BUILT_IN_STRSTR
)
2414 && has_single_use (rhs1
)
2415 && gimple_call_arg (g
, 0) == rhs2
)
2420 std::swap (rhs1
, rhs2
);
2425 tree arg0
= gimple_call_arg (call_stmt
, 0);
2429 tree arg1
= gimple_call_arg (call_stmt
, 1);
2430 tree arg1_len
= NULL_TREE
;
2431 int idx
= get_stridx (arg1
);
2436 arg1_len
= build_int_cst (size_type_node
, ~idx
);
2439 strinfo
*si
= get_strinfo (idx
);
2441 arg1_len
= get_string_length (si
);
2445 if (arg1_len
!= NULL_TREE
)
2447 gimple_stmt_iterator gsi
= gsi_for_stmt (call_stmt
);
2448 tree strncmp_decl
= builtin_decl_explicit (BUILT_IN_STRNCMP
);
2449 gcall
*strncmp_call
= gimple_build_call (strncmp_decl
, 3,
2450 arg0
, arg1
, arg1_len
);
2451 tree strncmp_lhs
= make_ssa_name (integer_type_node
);
2452 gimple_set_vuse (strncmp_call
, gimple_vuse (call_stmt
));
2453 gimple_call_set_lhs (strncmp_call
, strncmp_lhs
);
2454 gsi_remove (&gsi
, true);
2455 gsi_insert_before (&gsi
, strncmp_call
, GSI_SAME_STMT
);
2456 tree zero
= build_zero_cst (TREE_TYPE (strncmp_lhs
));
2458 if (is_gimple_assign (stmt
))
2460 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
2462 tree cond
= gimple_assign_rhs1 (stmt
);
2463 TREE_OPERAND (cond
, 0) = strncmp_lhs
;
2464 TREE_OPERAND (cond
, 1) = zero
;
2468 gimple_assign_set_rhs1 (stmt
, strncmp_lhs
);
2469 gimple_assign_set_rhs2 (stmt
, zero
);
2474 gcond
*cond
= as_a
<gcond
*> (stmt
);
2475 gimple_cond_set_lhs (cond
, strncmp_lhs
);
2476 gimple_cond_set_rhs (cond
, zero
);
2484 /* Attempt to optimize a single statement at *GSI using string length
2488 strlen_optimize_stmt (gimple_stmt_iterator
*gsi
)
2490 gimple
*stmt
= gsi_stmt (*gsi
);
2492 if (is_gimple_call (stmt
))
2494 tree callee
= gimple_call_fndecl (stmt
);
2495 if (valid_builtin_call (stmt
))
2496 switch (DECL_FUNCTION_CODE (callee
))
2498 case BUILT_IN_STRLEN
:
2499 case BUILT_IN_STRLEN_CHKP
:
2500 handle_builtin_strlen (gsi
);
2502 case BUILT_IN_STRCHR
:
2503 case BUILT_IN_STRCHR_CHKP
:
2504 handle_builtin_strchr (gsi
);
2506 case BUILT_IN_STRCPY
:
2507 case BUILT_IN_STRCPY_CHK
:
2508 case BUILT_IN_STPCPY
:
2509 case BUILT_IN_STPCPY_CHK
:
2510 case BUILT_IN_STRCPY_CHKP
:
2511 case BUILT_IN_STRCPY_CHK_CHKP
:
2512 case BUILT_IN_STPCPY_CHKP
:
2513 case BUILT_IN_STPCPY_CHK_CHKP
:
2514 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
2516 case BUILT_IN_MEMCPY
:
2517 case BUILT_IN_MEMCPY_CHK
:
2518 case BUILT_IN_MEMPCPY
:
2519 case BUILT_IN_MEMPCPY_CHK
:
2520 case BUILT_IN_MEMCPY_CHKP
:
2521 case BUILT_IN_MEMCPY_CHK_CHKP
:
2522 case BUILT_IN_MEMPCPY_CHKP
:
2523 case BUILT_IN_MEMPCPY_CHK_CHKP
:
2524 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
2526 case BUILT_IN_STRCAT
:
2527 case BUILT_IN_STRCAT_CHK
:
2528 case BUILT_IN_STRCAT_CHKP
:
2529 case BUILT_IN_STRCAT_CHK_CHKP
:
2530 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
2532 case BUILT_IN_MALLOC
:
2533 case BUILT_IN_CALLOC
:
2534 handle_builtin_malloc (DECL_FUNCTION_CODE (callee
), gsi
);
2536 case BUILT_IN_MEMSET
:
2537 if (!handle_builtin_memset (gsi
))
2540 case BUILT_IN_MEMCMP
:
2541 if (!handle_builtin_memcmp (gsi
))
2548 else if (is_gimple_assign (stmt
) && !gimple_clobber_p (stmt
))
2550 tree lhs
= gimple_assign_lhs (stmt
);
2552 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
2554 if (gimple_assign_single_p (stmt
)
2555 || (gimple_assign_cast_p (stmt
)
2556 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
2558 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
2559 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
2561 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
2562 handle_pointer_plus (gsi
);
2564 else if (TREE_CODE (lhs
) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
2566 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2567 if (code
== COND_EXPR
)
2569 tree cond
= gimple_assign_rhs1 (stmt
);
2570 enum tree_code cond_code
= TREE_CODE (cond
);
2572 if (cond_code
== EQ_EXPR
|| cond_code
== NE_EXPR
)
2573 fold_strstr_to_strncmp (TREE_OPERAND (cond
, 0),
2574 TREE_OPERAND (cond
, 1), stmt
);
2576 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
2577 fold_strstr_to_strncmp (gimple_assign_rhs1 (stmt
),
2578 gimple_assign_rhs2 (stmt
), stmt
);
2580 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
2582 tree type
= TREE_TYPE (lhs
);
2583 if (TREE_CODE (type
) == ARRAY_TYPE
)
2584 type
= TREE_TYPE (type
);
2585 if (TREE_CODE (type
) == INTEGER_TYPE
2586 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
2587 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
2589 if (! handle_char_store (gsi
))
2594 else if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
2596 enum tree_code code
= gimple_cond_code (cond
);
2597 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
2598 fold_strstr_to_strncmp (gimple_cond_lhs (stmt
),
2599 gimple_cond_rhs (stmt
), stmt
);
2602 if (gimple_vdef (stmt
))
2603 maybe_invalidate (stmt
);
2607 /* Recursively call maybe_invalidate on stmts that might be executed
2608 in between dombb and current bb and that contain a vdef. Stop when
2609 *count stmts are inspected, or if the whole strinfo vector has
2610 been invalidated. */
2613 do_invalidate (basic_block dombb
, gimple
*phi
, bitmap visited
, int *count
)
2615 unsigned int i
, n
= gimple_phi_num_args (phi
);
2617 for (i
= 0; i
< n
; i
++)
2619 tree vuse
= gimple_phi_arg_def (phi
, i
);
2620 gimple
*stmt
= SSA_NAME_DEF_STMT (vuse
);
2621 basic_block bb
= gimple_bb (stmt
);
2624 || !bitmap_set_bit (visited
, bb
->index
)
2625 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
2629 if (gimple_code (stmt
) == GIMPLE_PHI
)
2631 do_invalidate (dombb
, stmt
, visited
, count
);
2638 if (!maybe_invalidate (stmt
))
2643 vuse
= gimple_vuse (stmt
);
2644 stmt
= SSA_NAME_DEF_STMT (vuse
);
2645 if (gimple_bb (stmt
) != bb
)
2647 bb
= gimple_bb (stmt
);
2650 || !bitmap_set_bit (visited
, bb
->index
)
2651 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
2658 class strlen_dom_walker
: public dom_walker
2661 strlen_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
2663 virtual edge
before_dom_children (basic_block
);
2664 virtual void after_dom_children (basic_block
);
2667 /* Callback for walk_dominator_tree. Attempt to optimize various
2668 string ops by remembering string lengths pointed by pointer SSA_NAMEs. */
2671 strlen_dom_walker::before_dom_children (basic_block bb
)
2673 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
2676 stridx_to_strinfo
= NULL
;
2679 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) dombb
->aux
);
2680 if (stridx_to_strinfo
)
2682 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
2685 gphi
*phi
= gsi
.phi ();
2686 if (virtual_operand_p (gimple_phi_result (phi
)))
2688 bitmap visited
= BITMAP_ALLOC (NULL
);
2689 int count_vdef
= 100;
2690 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
2691 BITMAP_FREE (visited
);
2692 if (count_vdef
== 0)
2694 /* If there were too many vdefs in between immediate
2695 dominator and current bb, invalidate everything.
2696 If stridx_to_strinfo has been unshared, we need
2697 to free it, otherwise just set it to NULL. */
2698 if (!strinfo_shared ())
2704 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
2708 (*stridx_to_strinfo
)[i
] = NULL
;
2712 stridx_to_strinfo
= NULL
;
2720 /* If all PHI arguments have the same string index, the PHI result
2722 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
2725 gphi
*phi
= gsi
.phi ();
2726 tree result
= gimple_phi_result (phi
);
2727 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
2729 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
2732 unsigned int i
, n
= gimple_phi_num_args (phi
);
2733 for (i
= 1; i
< n
; i
++)
2734 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
2737 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
2742 /* Attempt to optimize individual statements. */
2743 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2744 if (strlen_optimize_stmt (&gsi
))
2747 bb
->aux
= stridx_to_strinfo
;
2748 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
2749 (*stridx_to_strinfo
)[0] = (strinfo
*) bb
;
2753 /* Callback for walk_dominator_tree. Free strinfo vector if it is
2754 owned by the current bb, clear bb->aux. */
2757 strlen_dom_walker::after_dom_children (basic_block bb
)
2761 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) bb
->aux
);
2762 if (vec_safe_length (stridx_to_strinfo
)
2763 && (*stridx_to_strinfo
)[0] == (strinfo
*) bb
)
2768 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
2770 vec_free (stridx_to_strinfo
);
2776 /* Main entry point. */
2780 const pass_data pass_data_strlen
=
2782 GIMPLE_PASS
, /* type */
2783 "strlen", /* name */
2784 OPTGROUP_NONE
, /* optinfo_flags */
2785 TV_TREE_STRLEN
, /* tv_id */
2786 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2787 0, /* properties_provided */
2788 0, /* properties_destroyed */
2789 0, /* todo_flags_start */
2790 0, /* todo_flags_finish */
2793 class pass_strlen
: public gimple_opt_pass
2796 pass_strlen (gcc::context
*ctxt
)
2797 : gimple_opt_pass (pass_data_strlen
, ctxt
)
2800 /* opt_pass methods: */
2801 virtual bool gate (function
*) { return flag_optimize_strlen
!= 0; }
2802 virtual unsigned int execute (function
*);
2804 }; // class pass_strlen
2807 pass_strlen::execute (function
*fun
)
2809 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
2812 calculate_dominance_info (CDI_DOMINATORS
);
2814 /* String length optimization is implemented as a walk of the dominator
2815 tree and a forward walk of statements within each block. */
2816 strlen_dom_walker (CDI_DOMINATORS
).walk (fun
->cfg
->x_entry_block_ptr
);
2818 ssa_ver_to_stridx
.release ();
2819 strinfo_pool
.release ();
2820 if (decl_to_stridxlist_htab
)
2822 obstack_free (&stridx_obstack
, NULL
);
2823 delete decl_to_stridxlist_htab
;
2824 decl_to_stridxlist_htab
= NULL
;
2826 laststmt
.stmt
= NULL
;
2827 laststmt
.len
= NULL_TREE
;
2828 laststmt
.stridx
= 0;
2836 make_pass_strlen (gcc::context
*ctxt
)
2838 return new pass_strlen (ctxt
);