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"
49 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
50 is an index into strinfo vector, negative value stands for
51 string length of a string literal (~strlen). */
52 static vec
<int> ssa_ver_to_stridx
;
54 /* Number of currently active string indexes plus one. */
55 static int max_stridx
;
57 /* String information record. */
60 /* String length of this string. */
62 /* Any of the corresponding pointers for querying alias oracle. */
64 /* This is used for two things:
66 - To record the statement that should be used for delayed length
67 computations. We maintain the invariant that all related strinfos
68 have delayed lengths or none do.
70 - To record the malloc or calloc call that produced this result. */
72 /* Pointer to '\0' if known, if NULL, it can be computed as
75 /* Reference count. Any changes to strinfo entry possibly shared
76 with dominating basic blocks need unshare_strinfo first, except
77 for dont_invalidate which affects only the immediately next
80 /* Copy of index. get_strinfo (si->idx) should return si; */
82 /* These 3 fields are for chaining related string pointers together.
84 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
85 strcpy (c, d); e = c + dl;
86 strinfo(a) -> strinfo(c) -> strinfo(e)
87 All have ->first field equal to strinfo(a)->idx and are doubly
88 chained through prev/next fields. The later strinfos are required
89 to point into the same string with zero or more bytes after
90 the previous pointer and all bytes in between the two pointers
91 must be non-zero. Functions like strcpy or memcpy are supposed
92 to adjust all previous strinfo lengths, but not following strinfo
93 lengths (those are uncertain, usually invalidated during
94 maybe_invalidate, except when the alias oracle knows better).
95 Functions like strcat on the other side adjust the whole
96 related strinfo chain.
97 They are updated lazily, so to use the chain the same first fields
98 and si->prev->next == si->idx needs to be verified. */
102 /* A flag whether the string is known to be written in the current
105 /* A flag for the next maybe_invalidate that this strinfo shouldn't
106 be invalidated. Always cleared by maybe_invalidate. */
107 bool dont_invalidate
;
110 /* Pool for allocating strinfo_struct entries. */
111 static object_allocator
<strinfo
> strinfo_pool ("strinfo pool");
113 /* Vector mapping positive string indexes to strinfo, for the
114 current basic block. The first pointer in the vector is special,
115 it is either NULL, meaning the vector isn't shared, or it is
116 a basic block pointer to the owner basic_block if shared.
117 If some other bb wants to modify the vector, the vector needs
118 to be unshared first, and only the owner bb is supposed to free it. */
119 static vec
<strinfo
*, va_heap
, vl_embed
> *stridx_to_strinfo
;
121 /* One OFFSET->IDX mapping. */
124 struct stridxlist
*next
;
125 HOST_WIDE_INT offset
;
129 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
130 struct decl_stridxlist_map
132 struct tree_map_base base
;
133 struct stridxlist list
;
136 /* Hash table for mapping decls to a chained list of offset -> idx
138 static hash_map
<tree_decl_hash
, stridxlist
> *decl_to_stridxlist_htab
;
140 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
141 static struct obstack stridx_obstack
;
143 /* Last memcpy statement if it could be adjusted if the trailing
144 '\0' written is immediately overwritten, or
145 *x = '\0' store that could be removed if it is immediately overwritten. */
146 struct laststmt_struct
153 static int get_stridx_plus_constant (strinfo
*, HOST_WIDE_INT
, tree
);
155 /* Return strinfo vector entry IDX. */
157 static inline strinfo
*
158 get_strinfo (int idx
)
160 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
162 return (*stridx_to_strinfo
)[idx
];
165 /* Get the next strinfo in the chain after SI, or null if none. */
167 static inline strinfo
*
168 get_next_strinfo (strinfo
*si
)
172 strinfo
*nextsi
= get_strinfo (si
->next
);
173 if (nextsi
== NULL
|| nextsi
->first
!= si
->first
|| nextsi
->prev
!= si
->idx
)
178 /* Helper function for get_stridx. */
181 get_addr_stridx (tree exp
, tree ptr
)
184 struct stridxlist
*list
, *last
= NULL
;
187 if (!decl_to_stridxlist_htab
)
190 base
= get_addr_base_and_unit_offset (exp
, &off
);
191 if (base
== NULL
|| !DECL_P (base
))
194 list
= decl_to_stridxlist_htab
->get (base
);
200 if (list
->offset
== off
)
202 if (list
->offset
> off
)
209 if (ptr
&& last
&& last
->idx
> 0)
211 strinfo
*si
= get_strinfo (last
->idx
);
214 && TREE_CODE (si
->length
) == INTEGER_CST
215 && compare_tree_int (si
->length
, off
- last
->offset
) != -1)
216 return get_stridx_plus_constant (si
, off
- last
->offset
, ptr
);
221 /* Return string index for EXP. */
224 get_stridx (tree exp
)
228 if (TREE_CODE (exp
) == SSA_NAME
)
230 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)])
231 return ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)];
234 HOST_WIDE_INT off
= 0;
235 for (i
= 0; i
< 5; i
++)
237 gimple
*def_stmt
= SSA_NAME_DEF_STMT (e
);
238 if (!is_gimple_assign (def_stmt
)
239 || gimple_assign_rhs_code (def_stmt
) != POINTER_PLUS_EXPR
)
241 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
242 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
243 if (TREE_CODE (rhs1
) != SSA_NAME
244 || !tree_fits_shwi_p (rhs2
))
246 HOST_WIDE_INT this_off
= tree_to_shwi (rhs2
);
249 off
= (unsigned HOST_WIDE_INT
) off
+ this_off
;
252 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)])
255 = get_strinfo (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)]);
258 && TREE_CODE (si
->length
) == INTEGER_CST
259 && compare_tree_int (si
->length
, off
) != -1)
260 return get_stridx_plus_constant (si
, off
, exp
);
267 if (TREE_CODE (exp
) == ADDR_EXPR
)
269 int idx
= get_addr_stridx (TREE_OPERAND (exp
, 0), exp
);
274 s
= string_constant (exp
, &o
);
276 && (o
== NULL_TREE
|| tree_fits_shwi_p (o
))
277 && TREE_STRING_LENGTH (s
) > 0)
279 HOST_WIDE_INT offset
= o
? tree_to_shwi (o
) : 0;
280 const char *p
= TREE_STRING_POINTER (s
);
281 int max
= TREE_STRING_LENGTH (s
) - 1;
283 if (p
[max
] == '\0' && offset
>= 0 && offset
<= max
)
284 return ~(int) strlen (p
+ offset
);
289 /* Return true if strinfo vector is shared with the immediate dominator. */
292 strinfo_shared (void)
294 return vec_safe_length (stridx_to_strinfo
)
295 && (*stridx_to_strinfo
)[0] != NULL
;
298 /* Unshare strinfo vector that is shared with the immediate dominator. */
301 unshare_strinfo_vec (void)
306 gcc_assert (strinfo_shared ());
307 stridx_to_strinfo
= vec_safe_copy (stridx_to_strinfo
);
308 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
311 (*stridx_to_strinfo
)[0] = NULL
;
314 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
315 Return a pointer to the location where the string index can
316 be stored (if 0) or is stored, or NULL if this can't be tracked. */
319 addr_stridxptr (tree exp
)
323 tree base
= get_addr_base_and_unit_offset (exp
, &off
);
324 if (base
== NULL_TREE
|| !DECL_P (base
))
327 if (!decl_to_stridxlist_htab
)
329 decl_to_stridxlist_htab
330 = new hash_map
<tree_decl_hash
, stridxlist
> (64);
331 gcc_obstack_init (&stridx_obstack
);
335 stridxlist
*list
= &decl_to_stridxlist_htab
->get_or_insert (base
, &existed
);
339 stridxlist
*before
= NULL
;
340 for (i
= 0; i
< 32; i
++)
342 if (list
->offset
== off
)
344 if (list
->offset
> off
&& before
== NULL
)
346 if (list
->next
== NULL
)
355 before
= XOBNEW (&stridx_obstack
, struct stridxlist
);
362 list
->next
= XOBNEW (&stridx_obstack
, struct stridxlist
);
372 /* Create a new string index, or return 0 if reached limit. */
375 new_stridx (tree exp
)
378 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
380 if (TREE_CODE (exp
) == SSA_NAME
)
382 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
385 ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)] = idx
;
388 if (TREE_CODE (exp
) == ADDR_EXPR
)
390 int *pidx
= addr_stridxptr (TREE_OPERAND (exp
, 0));
393 gcc_assert (*pidx
== 0);
394 *pidx
= max_stridx
++;
401 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
404 new_addr_stridx (tree exp
)
407 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
409 pidx
= addr_stridxptr (exp
);
412 gcc_assert (*pidx
== 0);
413 *pidx
= max_stridx
++;
419 /* Create a new strinfo. */
422 new_strinfo (tree ptr
, int idx
, tree length
)
424 strinfo
*si
= strinfo_pool
.allocate ();
428 si
->endptr
= NULL_TREE
;
434 si
->writable
= false;
435 si
->dont_invalidate
= false;
439 /* Decrease strinfo refcount and free it if not referenced anymore. */
442 free_strinfo (strinfo
*si
)
444 if (si
&& --si
->refcount
== 0)
445 strinfo_pool
.remove (si
);
448 /* Set strinfo in the vector entry IDX to SI. */
451 set_strinfo (int idx
, strinfo
*si
)
453 if (vec_safe_length (stridx_to_strinfo
) && (*stridx_to_strinfo
)[0])
454 unshare_strinfo_vec ();
455 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
456 vec_safe_grow_cleared (stridx_to_strinfo
, idx
+ 1);
457 (*stridx_to_strinfo
)[idx
] = si
;
460 /* Return the first strinfo in the related strinfo chain
461 if all strinfos in between belong to the chain, otherwise NULL. */
464 verify_related_strinfos (strinfo
*origsi
)
466 strinfo
*si
= origsi
, *psi
;
468 if (origsi
->first
== 0)
470 for (; si
->prev
; si
= psi
)
472 if (si
->first
!= origsi
->first
)
474 psi
= get_strinfo (si
->prev
);
477 if (psi
->next
!= si
->idx
)
480 if (si
->idx
!= si
->first
)
485 /* Set SI's endptr to ENDPTR and compute its length based on SI->ptr.
486 Use LOC for folding. */
489 set_endptr_and_length (location_t loc
, strinfo
*si
, tree endptr
)
493 tree start_as_size
= fold_convert_loc (loc
, size_type_node
, si
->ptr
);
494 tree end_as_size
= fold_convert_loc (loc
, size_type_node
, endptr
);
495 si
->length
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
496 end_as_size
, start_as_size
);
499 /* Return string length, or NULL if it can't be computed. */
502 get_string_length (strinfo
*si
)
509 gimple
*stmt
= si
->stmt
, *lenstmt
;
510 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
511 tree callee
, lhs
, fn
, tem
;
513 gimple_stmt_iterator gsi
;
515 gcc_assert (is_gimple_call (stmt
));
516 callee
= gimple_call_fndecl (stmt
);
517 gcc_assert (callee
&& DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
);
518 lhs
= gimple_call_lhs (stmt
);
519 /* unshare_strinfo is intentionally not called here. The (delayed)
520 transformation of strcpy or strcat into stpcpy is done at the place
521 of the former strcpy/strcat call and so can affect all the strinfos
522 with the same stmt. If they were unshared before and transformation
523 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
524 just compute the right length. */
525 switch (DECL_FUNCTION_CODE (callee
))
527 case BUILT_IN_STRCAT
:
528 case BUILT_IN_STRCAT_CHK
:
529 case BUILT_IN_STRCAT_CHKP
:
530 case BUILT_IN_STRCAT_CHK_CHKP
:
531 gsi
= gsi_for_stmt (stmt
);
532 fn
= builtin_decl_implicit (BUILT_IN_STRLEN
);
533 gcc_assert (lhs
== NULL_TREE
);
534 tem
= unshare_expr (gimple_call_arg (stmt
, 0));
537 lenstmt
= gimple_build_call (chkp_maybe_create_clone (fn
)->decl
,
538 2, tem
, gimple_call_arg (stmt
, 1));
539 gimple_call_set_with_bounds (lenstmt
, true);
542 lenstmt
= gimple_build_call (fn
, 1, tem
);
543 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), lenstmt
);
544 gimple_call_set_lhs (lenstmt
, lhs
);
545 gimple_set_vuse (lenstmt
, gimple_vuse (stmt
));
546 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
547 tem
= gimple_call_arg (stmt
, 0);
548 if (!ptrofftype_p (TREE_TYPE (lhs
)))
550 lhs
= convert_to_ptrofftype (lhs
);
551 lhs
= force_gimple_operand_gsi (&gsi
, lhs
, true, NULL_TREE
,
552 true, GSI_SAME_STMT
);
554 lenstmt
= gimple_build_assign
555 (make_ssa_name (TREE_TYPE (gimple_call_arg (stmt
, 0))),
556 POINTER_PLUS_EXPR
,tem
, lhs
);
557 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
558 gimple_call_set_arg (stmt
, 0, gimple_assign_lhs (lenstmt
));
561 case BUILT_IN_STRCPY
:
562 case BUILT_IN_STRCPY_CHK
:
563 case BUILT_IN_STRCPY_CHKP
:
564 case BUILT_IN_STRCPY_CHK_CHKP
:
565 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY
));
566 if (gimple_call_num_args (stmt
) == (with_bounds
? 4 : 2))
567 fn
= builtin_decl_implicit (BUILT_IN_STPCPY
);
569 fn
= builtin_decl_explicit (BUILT_IN_STPCPY_CHK
);
571 fn
= chkp_maybe_create_clone (fn
)->decl
;
572 gcc_assert (lhs
== NULL_TREE
);
573 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
575 fprintf (dump_file
, "Optimizing: ");
576 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
578 gimple_call_set_fndecl (stmt
, fn
);
579 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), stmt
);
580 gimple_call_set_lhs (stmt
, lhs
);
582 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
584 fprintf (dump_file
, "into: ");
585 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
588 case BUILT_IN_STPCPY
:
589 case BUILT_IN_STPCPY_CHK
:
590 case BUILT_IN_STPCPY_CHKP
:
591 case BUILT_IN_STPCPY_CHK_CHKP
:
592 gcc_assert (lhs
!= NULL_TREE
);
593 loc
= gimple_location (stmt
);
594 set_endptr_and_length (loc
, si
, lhs
);
595 for (strinfo
*chainsi
= verify_related_strinfos (si
);
597 chainsi
= get_next_strinfo (chainsi
))
598 if (chainsi
->length
== NULL
)
599 set_endptr_and_length (loc
, chainsi
, lhs
);
601 case BUILT_IN_MALLOC
:
603 /* BUILT_IN_CALLOC always has si->length set. */
613 /* Invalidate string length information for strings whose length
614 might change due to stores in stmt. */
617 maybe_invalidate (gimple
*stmt
)
621 bool nonempty
= false;
623 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
626 if (!si
->dont_invalidate
)
629 /* Do not use si->length. */
630 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, NULL_TREE
);
631 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
633 set_strinfo (i
, NULL
);
638 si
->dont_invalidate
= false;
644 /* Unshare strinfo record SI, if it has refcount > 1 or
645 if stridx_to_strinfo vector is shared with some other
649 unshare_strinfo (strinfo
*si
)
653 if (si
->refcount
== 1 && !strinfo_shared ())
656 nsi
= new_strinfo (si
->ptr
, si
->idx
, si
->length
);
657 nsi
->stmt
= si
->stmt
;
658 nsi
->endptr
= si
->endptr
;
659 nsi
->first
= si
->first
;
660 nsi
->prev
= si
->prev
;
661 nsi
->next
= si
->next
;
662 nsi
->writable
= si
->writable
;
663 set_strinfo (si
->idx
, nsi
);
668 /* Attempt to create a new strinfo for BASESI + OFF, or find existing
669 strinfo if there is any. Return it's idx, or 0 if no strinfo has
673 get_stridx_plus_constant (strinfo
*basesi
, HOST_WIDE_INT off
, tree ptr
)
675 if (TREE_CODE (ptr
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
678 if (basesi
->length
== NULL_TREE
679 || TREE_CODE (basesi
->length
) != INTEGER_CST
680 || compare_tree_int (basesi
->length
, off
) == -1
681 || !tree_fits_shwi_p (basesi
->length
))
684 HOST_WIDE_INT len
= tree_to_shwi (basesi
->length
) - off
;
685 strinfo
*si
= basesi
, *chainsi
;
686 if (si
->first
|| si
->prev
|| si
->next
)
687 si
= verify_related_strinfos (basesi
);
689 || si
->length
== NULL_TREE
690 || TREE_CODE (si
->length
) != INTEGER_CST
)
693 if (TREE_CODE (ptr
) == SSA_NAME
694 && ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
695 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
697 gcc_checking_assert (compare_tree_int (si
->length
, off
) != -1);
698 for (chainsi
= si
; chainsi
->next
; chainsi
= si
)
700 si
= get_strinfo (chainsi
->next
);
702 || si
->first
!= chainsi
->first
703 || si
->prev
!= chainsi
->idx
704 || si
->length
== NULL_TREE
705 || TREE_CODE (si
->length
) != INTEGER_CST
)
707 int r
= compare_tree_int (si
->length
, len
);
712 if (TREE_CODE (ptr
) == SSA_NAME
)
713 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = si
->idx
;
716 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
717 if (pidx
!= NULL
&& *pidx
== 0)
726 int idx
= new_stridx (ptr
);
729 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, len
));
730 set_strinfo (idx
, si
);
733 strinfo
*nextsi
= unshare_strinfo (get_strinfo (chainsi
->next
));
734 si
->next
= nextsi
->idx
;
737 chainsi
= unshare_strinfo (chainsi
);
738 if (chainsi
->first
== 0)
739 chainsi
->first
= chainsi
->idx
;
741 if (chainsi
->endptr
== NULL_TREE
&& len
== 0)
742 chainsi
->endptr
= ptr
;
743 si
->endptr
= chainsi
->endptr
;
744 si
->prev
= chainsi
->idx
;
745 si
->first
= chainsi
->first
;
746 si
->writable
= chainsi
->writable
;
750 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
751 to a zero-length string and if possible chain it to a related strinfo
752 chain whose part is or might be CHAINSI. */
755 zero_length_string (tree ptr
, strinfo
*chainsi
)
759 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
760 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
761 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
762 && ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] == 0);
764 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
768 si
= verify_related_strinfos (chainsi
);
772 for (; chainsi
->next
; chainsi
= si
)
774 if (chainsi
->endptr
== NULL_TREE
)
776 chainsi
= unshare_strinfo (chainsi
);
777 chainsi
->endptr
= ptr
;
779 si
= get_strinfo (chainsi
->next
);
781 || si
->first
!= chainsi
->first
782 || si
->prev
!= chainsi
->idx
)
785 gcc_assert (chainsi
->length
|| chainsi
->stmt
);
786 if (chainsi
->endptr
== NULL_TREE
)
788 chainsi
= unshare_strinfo (chainsi
);
789 chainsi
->endptr
= ptr
;
791 if (chainsi
->length
&& integer_zerop (chainsi
->length
))
795 chainsi
= unshare_strinfo (chainsi
);
798 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = chainsi
->idx
;
802 else if (chainsi
->first
|| chainsi
->prev
|| chainsi
->next
)
804 chainsi
= unshare_strinfo (chainsi
);
810 idx
= new_stridx (ptr
);
813 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, 0));
814 set_strinfo (idx
, si
);
818 chainsi
= unshare_strinfo (chainsi
);
819 if (chainsi
->first
== 0)
820 chainsi
->first
= chainsi
->idx
;
822 if (chainsi
->endptr
== NULL_TREE
)
823 chainsi
->endptr
= ptr
;
824 si
->prev
= chainsi
->idx
;
825 si
->first
= chainsi
->first
;
826 si
->writable
= chainsi
->writable
;
831 /* For strinfo ORIGSI whose length has been just updated
832 update also related strinfo lengths (add ADJ to each,
833 but don't adjust ORIGSI). */
836 adjust_related_strinfos (location_t loc
, strinfo
*origsi
, tree adj
)
838 strinfo
*si
= verify_related_strinfos (origsi
);
851 si
= unshare_strinfo (si
);
854 tem
= fold_convert_loc (loc
, TREE_TYPE (si
->length
), adj
);
855 si
->length
= fold_build2_loc (loc
, PLUS_EXPR
,
856 TREE_TYPE (si
->length
), si
->length
,
859 else if (si
->stmt
!= NULL
)
860 /* Delayed length computation is unaffected. */
865 si
->endptr
= NULL_TREE
;
866 si
->dont_invalidate
= true;
870 nsi
= get_strinfo (si
->next
);
872 || nsi
->first
!= si
->first
873 || nsi
->prev
!= si
->idx
)
879 /* Find if there are other SSA_NAME pointers equal to PTR
880 for which we don't track their string lengths yet. If so, use
884 find_equal_ptrs (tree ptr
, int idx
)
886 if (TREE_CODE (ptr
) != SSA_NAME
)
890 gimple
*stmt
= SSA_NAME_DEF_STMT (ptr
);
891 if (!is_gimple_assign (stmt
))
893 ptr
= gimple_assign_rhs1 (stmt
);
894 switch (gimple_assign_rhs_code (stmt
))
899 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)))
901 if (TREE_CODE (ptr
) == SSA_NAME
)
903 if (TREE_CODE (ptr
) != ADDR_EXPR
)
908 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
909 if (pidx
!= NULL
&& *pidx
== 0)
917 /* We might find an endptr created in this pass. Grow the
918 vector in that case. */
919 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
920 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
922 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] != 0)
924 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = idx
;
928 /* Return true if STMT is a call to a builtin function with the right
929 arguments and attributes that should be considered for optimization
933 valid_builtin_call (gimple
*stmt
)
935 if (!gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
938 tree callee
= gimple_call_fndecl (stmt
);
939 switch (DECL_FUNCTION_CODE (callee
))
941 case BUILT_IN_MEMCMP
:
942 case BUILT_IN_MEMCMP_EQ
:
943 case BUILT_IN_STRCHR
:
944 case BUILT_IN_STRCHR_CHKP
:
945 case BUILT_IN_STRLEN
:
946 case BUILT_IN_STRLEN_CHKP
:
947 /* The above functions should be pure. Punt if they aren't. */
948 if (gimple_vdef (stmt
) || gimple_vuse (stmt
) == NULL_TREE
)
952 case BUILT_IN_CALLOC
:
953 case BUILT_IN_MALLOC
:
954 case BUILT_IN_MEMCPY
:
955 case BUILT_IN_MEMCPY_CHK
:
956 case BUILT_IN_MEMCPY_CHKP
:
957 case BUILT_IN_MEMCPY_CHK_CHKP
:
958 case BUILT_IN_MEMPCPY
:
959 case BUILT_IN_MEMPCPY_CHK
:
960 case BUILT_IN_MEMPCPY_CHKP
:
961 case BUILT_IN_MEMPCPY_CHK_CHKP
:
962 case BUILT_IN_MEMSET
:
963 case BUILT_IN_STPCPY
:
964 case BUILT_IN_STPCPY_CHK
:
965 case BUILT_IN_STPCPY_CHKP
:
966 case BUILT_IN_STPCPY_CHK_CHKP
:
967 case BUILT_IN_STRCAT
:
968 case BUILT_IN_STRCAT_CHK
:
969 case BUILT_IN_STRCAT_CHKP
:
970 case BUILT_IN_STRCAT_CHK_CHKP
:
971 case BUILT_IN_STRCPY
:
972 case BUILT_IN_STRCPY_CHK
:
973 case BUILT_IN_STRCPY_CHKP
:
974 case BUILT_IN_STRCPY_CHK_CHKP
:
975 /* The above functions should be neither const nor pure. Punt if they
977 if (gimple_vdef (stmt
) == NULL_TREE
|| gimple_vuse (stmt
) == NULL_TREE
)
988 /* If the last .MEM setter statement before STMT is
989 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
990 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
991 just memcpy (x, y, strlen (y)). SI must be the zero length
995 adjust_last_stmt (strinfo
*si
, gimple
*stmt
, bool is_strcat
)
997 tree vuse
, callee
, len
;
998 struct laststmt_struct last
= laststmt
;
999 strinfo
*lastsi
, *firstsi
;
1000 unsigned len_arg_no
= 2;
1002 laststmt
.stmt
= NULL
;
1003 laststmt
.len
= NULL_TREE
;
1004 laststmt
.stridx
= 0;
1006 if (last
.stmt
== NULL
)
1009 vuse
= gimple_vuse (stmt
);
1010 if (vuse
== NULL_TREE
1011 || SSA_NAME_DEF_STMT (vuse
) != last
.stmt
1012 || !has_single_use (vuse
))
1015 gcc_assert (last
.stridx
> 0);
1016 lastsi
= get_strinfo (last
.stridx
);
1022 if (lastsi
->first
== 0 || lastsi
->first
!= si
->first
)
1025 firstsi
= verify_related_strinfos (si
);
1026 if (firstsi
== NULL
)
1028 while (firstsi
!= lastsi
)
1031 if (firstsi
->next
== 0)
1033 nextsi
= get_strinfo (firstsi
->next
);
1035 || nextsi
->prev
!= firstsi
->idx
1036 || nextsi
->first
!= si
->first
)
1044 if (si
->length
== NULL_TREE
|| !integer_zerop (si
->length
))
1048 if (is_gimple_assign (last
.stmt
))
1050 gimple_stmt_iterator gsi
;
1052 if (!integer_zerop (gimple_assign_rhs1 (last
.stmt
)))
1054 if (stmt_could_throw_p (last
.stmt
))
1056 gsi
= gsi_for_stmt (last
.stmt
);
1057 unlink_stmt_vdef (last
.stmt
);
1058 release_defs (last
.stmt
);
1059 gsi_remove (&gsi
, true);
1063 if (!valid_builtin_call (last
.stmt
))
1066 callee
= gimple_call_fndecl (last
.stmt
);
1067 switch (DECL_FUNCTION_CODE (callee
))
1069 case BUILT_IN_MEMCPY
:
1070 case BUILT_IN_MEMCPY_CHK
:
1072 case BUILT_IN_MEMCPY_CHKP
:
1073 case BUILT_IN_MEMCPY_CHK_CHKP
:
1080 len
= gimple_call_arg (last
.stmt
, len_arg_no
);
1081 if (tree_fits_uhwi_p (len
))
1083 if (!tree_fits_uhwi_p (last
.len
)
1084 || integer_zerop (len
)
1085 || tree_to_uhwi (len
) != tree_to_uhwi (last
.len
) + 1)
1087 /* Don't adjust the length if it is divisible by 4, it is more efficient
1088 to store the extra '\0' in that case. */
1089 if ((tree_to_uhwi (len
) & 3) == 0)
1092 else if (TREE_CODE (len
) == SSA_NAME
)
1094 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1095 if (!is_gimple_assign (def_stmt
)
1096 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1097 || gimple_assign_rhs1 (def_stmt
) != last
.len
1098 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1104 gimple_call_set_arg (last
.stmt
, len_arg_no
, last
.len
);
1105 update_stmt (last
.stmt
);
1108 /* Handle a strlen call. If strlen of the argument is known, replace
1109 the strlen call with the known value, otherwise remember that strlen
1110 of the argument is stored in the lhs SSA_NAME. */
1113 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
1117 gimple
*stmt
= gsi_stmt (*gsi
);
1118 tree lhs
= gimple_call_lhs (stmt
);
1120 if (lhs
== NULL_TREE
)
1123 src
= gimple_call_arg (stmt
, 0);
1124 idx
= get_stridx (src
);
1131 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
1135 si
= get_strinfo (idx
);
1137 rhs
= get_string_length (si
);
1139 if (rhs
!= NULL_TREE
)
1141 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1143 fprintf (dump_file
, "Optimizing: ");
1144 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1146 rhs
= unshare_expr (rhs
);
1147 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
1148 rhs
= fold_convert_loc (gimple_location (stmt
),
1149 TREE_TYPE (lhs
), rhs
);
1150 if (!update_call_from_tree (gsi
, rhs
))
1151 gimplify_and_update_call_from_tree (gsi
, rhs
);
1152 stmt
= gsi_stmt (*gsi
);
1154 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1156 fprintf (dump_file
, "into: ");
1157 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1160 && TREE_CODE (si
->length
) != SSA_NAME
1161 && TREE_CODE (si
->length
) != INTEGER_CST
1162 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1164 si
= unshare_strinfo (si
);
1170 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1173 idx
= new_stridx (src
);
1174 else if (get_strinfo (idx
) != NULL
)
1178 strinfo
*si
= new_strinfo (src
, idx
, lhs
);
1179 set_strinfo (idx
, si
);
1180 find_equal_ptrs (src
, idx
);
1184 /* Handle a strchr call. If strlen of the first argument is known, replace
1185 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
1186 that lhs of the call is endptr and strlen of the argument is endptr - x. */
1189 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
1193 gimple
*stmt
= gsi_stmt (*gsi
);
1194 tree lhs
= gimple_call_lhs (stmt
);
1195 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1197 if (lhs
== NULL_TREE
)
1200 if (!integer_zerop (gimple_call_arg (stmt
, with_bounds
? 2 : 1)))
1203 src
= gimple_call_arg (stmt
, 0);
1204 idx
= get_stridx (src
);
1211 rhs
= build_int_cst (size_type_node
, ~idx
);
1215 si
= get_strinfo (idx
);
1217 rhs
= get_string_length (si
);
1219 if (rhs
!= NULL_TREE
)
1221 location_t loc
= gimple_location (stmt
);
1223 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1225 fprintf (dump_file
, "Optimizing: ");
1226 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1228 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
1230 rhs
= unshare_expr (si
->endptr
);
1231 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1233 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1237 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1238 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1239 TREE_TYPE (src
), src
, rhs
);
1240 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1242 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1244 if (!update_call_from_tree (gsi
, rhs
))
1245 gimplify_and_update_call_from_tree (gsi
, rhs
);
1246 stmt
= gsi_stmt (*gsi
);
1248 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1250 fprintf (dump_file
, "into: ");
1251 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1254 && si
->endptr
== NULL_TREE
1255 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1257 si
= unshare_strinfo (si
);
1260 zero_length_string (lhs
, si
);
1264 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1266 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1269 idx
= new_stridx (src
);
1270 else if (get_strinfo (idx
) != NULL
)
1272 zero_length_string (lhs
, NULL
);
1277 location_t loc
= gimple_location (stmt
);
1278 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1279 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1280 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1281 size_type_node
, lhsu
, srcu
);
1282 strinfo
*si
= new_strinfo (src
, idx
, length
);
1284 set_strinfo (idx
, si
);
1285 find_equal_ptrs (src
, idx
);
1286 zero_length_string (lhs
, si
);
1290 zero_length_string (lhs
, NULL
);
1293 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1294 If strlen of the second argument is known, strlen of the first argument
1295 is the same after this call. Furthermore, attempt to convert it to
1299 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1302 tree src
, dst
, srclen
, len
, lhs
, args
, type
, fn
, oldlen
;
1304 gimple
*stmt
= gsi_stmt (*gsi
);
1305 strinfo
*si
, *dsi
, *olddsi
, *zsi
;
1307 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1309 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1310 dst
= gimple_call_arg (stmt
, 0);
1311 lhs
= gimple_call_lhs (stmt
);
1312 idx
= get_stridx (src
);
1315 si
= get_strinfo (idx
);
1317 didx
= get_stridx (dst
);
1321 olddsi
= get_strinfo (didx
);
1326 adjust_last_stmt (olddsi
, stmt
, false);
1330 srclen
= get_string_length (si
);
1332 srclen
= build_int_cst (size_type_node
, ~idx
);
1334 loc
= gimple_location (stmt
);
1335 if (srclen
== NULL_TREE
)
1338 case BUILT_IN_STRCPY
:
1339 case BUILT_IN_STRCPY_CHK
:
1340 case BUILT_IN_STRCPY_CHKP
:
1341 case BUILT_IN_STRCPY_CHK_CHKP
:
1342 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1345 case BUILT_IN_STPCPY
:
1346 case BUILT_IN_STPCPY_CHK
:
1347 case BUILT_IN_STPCPY_CHKP
:
1348 case BUILT_IN_STPCPY_CHK_CHKP
:
1349 if (lhs
== NULL_TREE
)
1353 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1354 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1355 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1365 didx
= new_stridx (dst
);
1371 oldlen
= olddsi
->length
;
1372 dsi
= unshare_strinfo (olddsi
);
1373 dsi
->length
= srclen
;
1374 /* Break the chain, so adjust_related_strinfo on later pointers in
1375 the chain won't adjust this one anymore. */
1378 dsi
->endptr
= NULL_TREE
;
1382 dsi
= new_strinfo (dst
, didx
, srclen
);
1383 set_strinfo (didx
, dsi
);
1384 find_equal_ptrs (dst
, didx
);
1386 dsi
->writable
= true;
1387 dsi
->dont_invalidate
= true;
1389 if (dsi
->length
== NULL_TREE
)
1393 /* If string length of src is unknown, use delayed length
1394 computation. If string lenth of dst will be needed, it
1395 can be computed by transforming this strcpy call into
1396 stpcpy and subtracting dst from the return value. */
1398 /* Look for earlier strings whose length could be determined if
1399 this strcpy is turned into an stpcpy. */
1401 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1403 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1405 /* When setting a stmt for delayed length computation
1406 prevent all strinfos through dsi from being
1408 chainsi
= unshare_strinfo (chainsi
);
1409 chainsi
->stmt
= stmt
;
1410 chainsi
->length
= NULL_TREE
;
1411 chainsi
->endptr
= NULL_TREE
;
1412 chainsi
->dont_invalidate
= true;
1421 tree adj
= NULL_TREE
;
1422 if (oldlen
== NULL_TREE
)
1424 else if (integer_zerop (oldlen
))
1426 else if (TREE_CODE (oldlen
) == INTEGER_CST
1427 || TREE_CODE (srclen
) == INTEGER_CST
)
1428 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1429 TREE_TYPE (srclen
), srclen
,
1430 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1432 if (adj
!= NULL_TREE
)
1433 adjust_related_strinfos (loc
, dsi
, adj
);
1437 /* strcpy src may not overlap dst, so src doesn't need to be
1438 invalidated either. */
1440 si
->dont_invalidate
= true;
1446 case BUILT_IN_STRCPY
:
1447 case BUILT_IN_STRCPY_CHKP
:
1448 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1450 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1452 case BUILT_IN_STRCPY_CHK
:
1453 case BUILT_IN_STRCPY_CHK_CHKP
:
1454 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1456 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1458 case BUILT_IN_STPCPY
:
1459 case BUILT_IN_STPCPY_CHKP
:
1460 /* This would need adjustment of the lhs (subtract one),
1461 or detection that the trailing '\0' doesn't need to be
1462 written, if it will be immediately overwritten.
1463 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1467 zsi
= zero_length_string (lhs
, dsi
);
1470 case BUILT_IN_STPCPY_CHK
:
1471 case BUILT_IN_STPCPY_CHK_CHKP
:
1472 /* This would need adjustment of the lhs (subtract one),
1473 or detection that the trailing '\0' doesn't need to be
1474 written, if it will be immediately overwritten.
1475 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1479 zsi
= zero_length_string (lhs
, dsi
);
1486 zsi
->dont_invalidate
= true;
1488 if (fn
== NULL_TREE
)
1491 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1492 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1494 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1495 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1496 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1498 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1500 fprintf (dump_file
, "Optimizing: ");
1501 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1505 fn
= chkp_maybe_create_clone (fn
)->decl
;
1506 if (gimple_call_num_args (stmt
) == 4)
1507 success
= update_gimple_call (gsi
, fn
, 5, dst
,
1508 gimple_call_arg (stmt
, 1),
1510 gimple_call_arg (stmt
, 3),
1513 success
= update_gimple_call (gsi
, fn
, 6, dst
,
1514 gimple_call_arg (stmt
, 1),
1516 gimple_call_arg (stmt
, 3),
1518 gimple_call_arg (stmt
, 4));
1521 if (gimple_call_num_args (stmt
) == 2)
1522 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1524 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1525 gimple_call_arg (stmt
, 2));
1528 stmt
= gsi_stmt (*gsi
);
1529 gimple_call_set_with_bounds (stmt
, with_bounds
);
1531 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1533 fprintf (dump_file
, "into: ");
1534 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1536 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1537 laststmt
.stmt
= stmt
;
1538 laststmt
.len
= srclen
;
1539 laststmt
.stridx
= dsi
->idx
;
1541 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1542 fprintf (dump_file
, "not possible.\n");
1545 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1546 If strlen of the second argument is known and length of the third argument
1547 is that plus one, strlen of the first argument is the same after this
1551 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1554 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
1555 gimple
*stmt
= gsi_stmt (*gsi
);
1556 strinfo
*si
, *dsi
, *olddsi
;
1557 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1559 len
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
1560 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1561 dst
= gimple_call_arg (stmt
, 0);
1562 idx
= get_stridx (src
);
1566 didx
= get_stridx (dst
);
1569 olddsi
= get_strinfo (didx
);
1574 && tree_fits_uhwi_p (len
)
1575 && !integer_zerop (len
))
1576 adjust_last_stmt (olddsi
, stmt
, false);
1582 /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */
1583 si
= get_strinfo (idx
);
1584 if (si
== NULL
|| si
->length
== NULL_TREE
)
1586 if (TREE_CODE (len
) != SSA_NAME
)
1588 def_stmt
= SSA_NAME_DEF_STMT (len
);
1589 if (!is_gimple_assign (def_stmt
)
1590 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1591 || gimple_assign_rhs1 (def_stmt
) != si
->length
1592 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1598 /* Handle memcpy (x, "abcd", 5) or
1599 memcpy (x, "abc\0uvw", 7). */
1600 if (!tree_fits_uhwi_p (len
)
1601 || tree_to_uhwi (len
) <= (unsigned HOST_WIDE_INT
) ~idx
)
1605 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
1606 adjust_last_stmt (olddsi
, stmt
, false);
1610 didx
= new_stridx (dst
);
1615 newlen
= si
->length
;
1617 newlen
= build_int_cst (size_type_node
, ~idx
);
1621 dsi
= unshare_strinfo (olddsi
);
1622 oldlen
= olddsi
->length
;
1623 dsi
->length
= newlen
;
1624 /* Break the chain, so adjust_related_strinfo on later pointers in
1625 the chain won't adjust this one anymore. */
1628 dsi
->endptr
= NULL_TREE
;
1632 dsi
= new_strinfo (dst
, didx
, newlen
);
1633 set_strinfo (didx
, dsi
);
1634 find_equal_ptrs (dst
, didx
);
1636 dsi
->writable
= true;
1637 dsi
->dont_invalidate
= true;
1640 tree adj
= NULL_TREE
;
1641 location_t loc
= gimple_location (stmt
);
1642 if (oldlen
== NULL_TREE
)
1644 else if (integer_zerop (oldlen
))
1646 else if (TREE_CODE (oldlen
) == INTEGER_CST
1647 || TREE_CODE (dsi
->length
) == INTEGER_CST
)
1648 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1649 TREE_TYPE (dsi
->length
), dsi
->length
,
1650 fold_convert_loc (loc
, TREE_TYPE (dsi
->length
),
1652 if (adj
!= NULL_TREE
)
1653 adjust_related_strinfos (loc
, dsi
, adj
);
1657 /* memcpy src may not overlap dst, so src doesn't need to be
1658 invalidated either. */
1660 si
->dont_invalidate
= true;
1662 lhs
= gimple_call_lhs (stmt
);
1665 case BUILT_IN_MEMCPY
:
1666 case BUILT_IN_MEMCPY_CHK
:
1667 case BUILT_IN_MEMCPY_CHKP
:
1668 case BUILT_IN_MEMCPY_CHK_CHKP
:
1669 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1670 laststmt
.stmt
= stmt
;
1671 laststmt
.len
= dsi
->length
;
1672 laststmt
.stridx
= dsi
->idx
;
1674 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1676 case BUILT_IN_MEMPCPY
:
1677 case BUILT_IN_MEMPCPY_CHK
:
1678 case BUILT_IN_MEMPCPY_CHKP
:
1679 case BUILT_IN_MEMPCPY_CHK_CHKP
:
1686 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
1687 If strlen of the second argument is known, strlen of the first argument
1688 is increased by the length of the second argument. Furthermore, attempt
1689 to convert it to memcpy/strcpy if the length of the first argument
1693 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1696 tree src
, dst
, srclen
, dstlen
, len
, lhs
, args
, type
, fn
, objsz
, endptr
;
1698 gimple
*stmt
= gsi_stmt (*gsi
);
1701 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1703 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1704 dst
= gimple_call_arg (stmt
, 0);
1705 lhs
= gimple_call_lhs (stmt
);
1707 didx
= get_stridx (dst
);
1713 dsi
= get_strinfo (didx
);
1714 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
1716 /* strcat (p, q) can be transformed into
1717 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
1718 with length endptr - p if we need to compute the length
1719 later on. Don't do this transformation if we don't need
1721 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
1725 didx
= new_stridx (dst
);
1731 dsi
= new_strinfo (dst
, didx
, NULL_TREE
);
1732 set_strinfo (didx
, dsi
);
1733 find_equal_ptrs (dst
, didx
);
1737 dsi
= unshare_strinfo (dsi
);
1738 dsi
->length
= NULL_TREE
;
1740 dsi
->endptr
= NULL_TREE
;
1742 dsi
->writable
= true;
1744 dsi
->dont_invalidate
= true;
1751 idx
= get_stridx (src
);
1753 srclen
= build_int_cst (size_type_node
, ~idx
);
1756 si
= get_strinfo (idx
);
1758 srclen
= get_string_length (si
);
1761 loc
= gimple_location (stmt
);
1762 dstlen
= dsi
->length
;
1763 endptr
= dsi
->endptr
;
1765 dsi
= unshare_strinfo (dsi
);
1766 dsi
->endptr
= NULL_TREE
;
1768 dsi
->writable
= true;
1770 if (srclen
!= NULL_TREE
)
1772 dsi
->length
= fold_build2_loc (loc
, PLUS_EXPR
, TREE_TYPE (dsi
->length
),
1773 dsi
->length
, srclen
);
1774 adjust_related_strinfos (loc
, dsi
, srclen
);
1775 dsi
->dont_invalidate
= true;
1780 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1781 dsi
->dont_invalidate
= true;
1785 /* strcat src may not overlap dst, so src doesn't need to be
1786 invalidated either. */
1787 si
->dont_invalidate
= true;
1789 /* For now. Could remove the lhs from the call and add
1790 lhs = dst; afterwards. */
1798 case BUILT_IN_STRCAT
:
1799 case BUILT_IN_STRCAT_CHKP
:
1800 if (srclen
!= NULL_TREE
)
1801 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1803 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
1805 case BUILT_IN_STRCAT_CHK
:
1806 case BUILT_IN_STRCAT_CHK_CHKP
:
1807 if (srclen
!= NULL_TREE
)
1808 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1810 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
1811 objsz
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
1817 if (fn
== NULL_TREE
)
1821 if (srclen
!= NULL_TREE
)
1823 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1824 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1826 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1827 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
1828 build_int_cst (type
, 1));
1829 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1833 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
1835 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1836 TREE_TYPE (dst
), unshare_expr (dst
),
1837 fold_convert_loc (loc
, sizetype
,
1838 unshare_expr (dstlen
)));
1839 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
1841 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1843 fprintf (dump_file
, "Optimizing: ");
1844 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1848 fn
= chkp_maybe_create_clone (fn
)->decl
;
1849 if (srclen
!= NULL_TREE
)
1850 success
= update_gimple_call (gsi
, fn
, 5 + (objsz
!= NULL_TREE
),
1852 gimple_call_arg (stmt
, 1),
1854 gimple_call_arg (stmt
, 3),
1857 success
= update_gimple_call (gsi
, fn
, 4 + (objsz
!= NULL_TREE
),
1859 gimple_call_arg (stmt
, 1),
1861 gimple_call_arg (stmt
, 3),
1865 if (srclen
!= NULL_TREE
)
1866 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
1867 dst
, src
, len
, objsz
);
1869 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
1873 stmt
= gsi_stmt (*gsi
);
1874 gimple_call_set_with_bounds (stmt
, with_bounds
);
1876 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1878 fprintf (dump_file
, "into: ");
1879 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1881 /* If srclen == NULL, note that current string length can be
1882 computed by transforming this strcpy into stpcpy. */
1883 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
1885 adjust_last_stmt (dsi
, stmt
, true);
1886 if (srclen
!= NULL_TREE
)
1888 laststmt
.stmt
= stmt
;
1889 laststmt
.len
= srclen
;
1890 laststmt
.stridx
= dsi
->idx
;
1893 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1894 fprintf (dump_file
, "not possible.\n");
1897 /* Handle a call to malloc or calloc. */
1900 handle_builtin_malloc (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1902 gimple
*stmt
= gsi_stmt (*gsi
);
1903 tree lhs
= gimple_call_lhs (stmt
);
1904 if (lhs
== NULL_TREE
)
1907 gcc_assert (get_stridx (lhs
) == 0);
1908 int idx
= new_stridx (lhs
);
1909 tree length
= NULL_TREE
;
1910 if (bcode
== BUILT_IN_CALLOC
)
1911 length
= build_int_cst (size_type_node
, 0);
1912 strinfo
*si
= new_strinfo (lhs
, idx
, length
);
1913 if (bcode
== BUILT_IN_CALLOC
)
1915 set_strinfo (idx
, si
);
1916 si
->writable
= true;
1918 si
->dont_invalidate
= true;
1921 /* Handle a call to memset.
1922 After a call to calloc, memset(,0,) is unnecessary.
1923 memset(malloc(n),0,n) is calloc(n,1). */
1926 handle_builtin_memset (gimple_stmt_iterator
*gsi
)
1928 gimple
*stmt2
= gsi_stmt (*gsi
);
1929 if (!integer_zerop (gimple_call_arg (stmt2
, 1)))
1931 tree ptr
= gimple_call_arg (stmt2
, 0);
1932 int idx1
= get_stridx (ptr
);
1935 strinfo
*si1
= get_strinfo (idx1
);
1938 gimple
*stmt1
= si1
->stmt
;
1939 if (!stmt1
|| !is_gimple_call (stmt1
))
1941 tree callee1
= gimple_call_fndecl (stmt1
);
1942 if (!valid_builtin_call (stmt1
))
1944 enum built_in_function code1
= DECL_FUNCTION_CODE (callee1
);
1945 tree size
= gimple_call_arg (stmt2
, 2);
1946 if (code1
== BUILT_IN_CALLOC
)
1947 /* Not touching stmt1 */ ;
1948 else if (code1
== BUILT_IN_MALLOC
1949 && operand_equal_p (gimple_call_arg (stmt1
, 0), size
, 0))
1951 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt1
);
1952 update_gimple_call (&gsi1
, builtin_decl_implicit (BUILT_IN_CALLOC
), 2,
1953 size
, build_one_cst (size_type_node
));
1954 si1
->length
= build_int_cst (size_type_node
, 0);
1955 si1
->stmt
= gsi_stmt (gsi1
);
1959 tree lhs
= gimple_call_lhs (stmt2
);
1960 unlink_stmt_vdef (stmt2
);
1963 gimple
*assign
= gimple_build_assign (lhs
, ptr
);
1964 gsi_replace (gsi
, assign
, false);
1968 gsi_remove (gsi
, true);
1969 release_defs (stmt2
);
1975 /* Handle a call to memcmp. We try to handle small comparisons by
1976 converting them to load and compare, and replacing the call to memcmp
1977 with a __builtin_memcmp_eq call where possible. */
1980 handle_builtin_memcmp (gimple_stmt_iterator
*gsi
)
1982 gcall
*stmt2
= as_a
<gcall
*> (gsi_stmt (*gsi
));
1983 tree res
= gimple_call_lhs (stmt2
);
1984 tree arg1
= gimple_call_arg (stmt2
, 0);
1985 tree arg2
= gimple_call_arg (stmt2
, 1);
1986 tree len
= gimple_call_arg (stmt2
, 2);
1987 unsigned HOST_WIDE_INT leni
;
1988 use_operand_p use_p
;
1989 imm_use_iterator iter
;
1994 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
1996 gimple
*ustmt
= USE_STMT (use_p
);
1998 if (is_gimple_debug (ustmt
))
2000 if (gimple_code (ustmt
) == GIMPLE_ASSIGN
)
2002 gassign
*asgn
= as_a
<gassign
*> (ustmt
);
2003 tree_code code
= gimple_assign_rhs_code (asgn
);
2004 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2005 || !integer_zerop (gimple_assign_rhs2 (asgn
)))
2008 else if (gimple_code (ustmt
) == GIMPLE_COND
)
2010 tree_code code
= gimple_cond_code (ustmt
);
2011 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2012 || !integer_zerop (gimple_cond_rhs (ustmt
)))
2019 if (tree_fits_uhwi_p (len
)
2020 && (leni
= tree_to_uhwi (len
)) <= GET_MODE_SIZE (word_mode
)
2021 && pow2p_hwi (leni
))
2023 leni
*= CHAR_TYPE_SIZE
;
2024 unsigned align1
= get_pointer_alignment (arg1
);
2025 unsigned align2
= get_pointer_alignment (arg2
);
2026 unsigned align
= MIN (align1
, align2
);
2027 machine_mode mode
= mode_for_size (leni
, MODE_INT
, 1);
2029 && (align
>= leni
|| !SLOW_UNALIGNED_ACCESS (mode
, align
)))
2031 location_t loc
= gimple_location (stmt2
);
2033 type
= build_nonstandard_integer_type (leni
, 1);
2034 gcc_assert (GET_MODE_BITSIZE (TYPE_MODE (type
)) == leni
);
2035 tree ptrtype
= build_pointer_type_for_mode (char_type_node
,
2037 off
= build_int_cst (ptrtype
, 0);
2038 arg1
= build2_loc (loc
, MEM_REF
, type
, arg1
, off
);
2039 arg2
= build2_loc (loc
, MEM_REF
, type
, arg2
, off
);
2040 tree tem1
= fold_const_aggregate_ref (arg1
);
2043 tree tem2
= fold_const_aggregate_ref (arg2
);
2046 res
= fold_convert_loc (loc
, TREE_TYPE (res
),
2047 fold_build2_loc (loc
, NE_EXPR
,
2050 gimplify_and_update_call_from_tree (gsi
, res
);
2055 gimple_call_set_fndecl (stmt2
, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ
));
2059 /* Handle a POINTER_PLUS_EXPR statement.
2060 For p = "abcd" + 2; compute associated length, or if
2061 p = q + off is pointing to a '\0' character of a string, call
2062 zero_length_string on it. */
2065 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
2067 gimple
*stmt
= gsi_stmt (*gsi
);
2068 tree lhs
= gimple_assign_lhs (stmt
), off
;
2069 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
2077 tree off
= gimple_assign_rhs2 (stmt
);
2078 if (tree_fits_uhwi_p (off
)
2079 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
2080 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
2081 = ~(~idx
- (int) tree_to_uhwi (off
));
2085 si
= get_strinfo (idx
);
2086 if (si
== NULL
|| si
->length
== NULL_TREE
)
2089 off
= gimple_assign_rhs2 (stmt
);
2091 if (operand_equal_p (si
->length
, off
, 0))
2092 zsi
= zero_length_string (lhs
, si
);
2093 else if (TREE_CODE (off
) == SSA_NAME
)
2095 gimple
*def_stmt
= SSA_NAME_DEF_STMT (off
);
2096 if (gimple_assign_single_p (def_stmt
)
2097 && operand_equal_p (si
->length
, gimple_assign_rhs1 (def_stmt
), 0))
2098 zsi
= zero_length_string (lhs
, si
);
2101 && si
->endptr
!= NULL_TREE
2102 && si
->endptr
!= lhs
2103 && TREE_CODE (si
->endptr
) == SSA_NAME
)
2105 enum tree_code rhs_code
2106 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
2107 ? SSA_NAME
: NOP_EXPR
;
2108 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
);
2109 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2114 /* Handle a single character store. */
2117 handle_char_store (gimple_stmt_iterator
*gsi
)
2121 gimple
*stmt
= gsi_stmt (*gsi
);
2122 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
2124 if (TREE_CODE (lhs
) == MEM_REF
2125 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
2127 if (integer_zerop (TREE_OPERAND (lhs
, 1)))
2129 ssaname
= TREE_OPERAND (lhs
, 0);
2130 idx
= get_stridx (ssaname
);
2134 idx
= get_addr_stridx (lhs
, NULL_TREE
);
2138 si
= get_strinfo (idx
);
2139 if (si
!= NULL
&& si
->length
!= NULL_TREE
&& integer_zerop (si
->length
))
2141 if (initializer_zerop (gimple_assign_rhs1 (stmt
)))
2143 /* When storing '\0', the store can be removed
2144 if we know it has been stored in the current function. */
2145 if (!stmt_could_throw_p (stmt
) && si
->writable
)
2147 unlink_stmt_vdef (stmt
);
2148 release_defs (stmt
);
2149 gsi_remove (gsi
, true);
2154 si
->writable
= true;
2160 /* Otherwise this statement overwrites the '\0' with
2161 something, if the previous stmt was a memcpy,
2162 its length may be decreased. */
2163 adjust_last_stmt (si
, stmt
, false);
2165 else if (si
!= NULL
&& integer_zerop (gimple_assign_rhs1 (stmt
)))
2167 si
= unshare_strinfo (si
);
2168 si
->length
= build_int_cst (size_type_node
, 0);
2174 si
->writable
= true;
2175 if (ssaname
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
2176 si
->endptr
= ssaname
;
2177 si
->dont_invalidate
= true;
2179 /* If si->length is non-zero constant, we aren't overwriting '\0',
2180 and if we aren't storing '\0', we know that the length of the
2181 string and any other zero terminated string in memory remains
2182 the same. In that case we move to the next gimple statement and
2183 return to signal the caller that it shouldn't invalidate anything.
2185 This is benefical for cases like:
2190 strcpy (p, "foobar");
2191 size_t len = strlen (p); // This can be optimized into 6
2192 size_t len2 = strlen (q); // This has to be computed
2194 size_t len3 = strlen (p); // This can be optimized into 6
2195 size_t len4 = strlen (q); // This can be optimized into len2
2196 bar (len, len2, len3, len4);
2199 else if (si
!= NULL
&& si
->length
!= NULL_TREE
2200 && TREE_CODE (si
->length
) == INTEGER_CST
2201 && integer_nonzerop (gimple_assign_rhs1 (stmt
)))
2207 else if (idx
== 0 && initializer_zerop (gimple_assign_rhs1 (stmt
)))
2211 si
= zero_length_string (ssaname
, NULL
);
2213 si
->dont_invalidate
= true;
2217 int idx
= new_addr_stridx (lhs
);
2220 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
2221 build_int_cst (size_type_node
, 0));
2222 set_strinfo (idx
, si
);
2223 si
->dont_invalidate
= true;
2227 si
->writable
= true;
2230 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == STRING_CST
2231 && ssaname
== NULL_TREE
2232 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
2234 size_t l
= strlen (TREE_STRING_POINTER (gimple_assign_rhs1 (stmt
)));
2235 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
2236 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> l
)
2238 int idx
= new_addr_stridx (lhs
);
2241 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
2242 build_int_cst (size_type_node
, l
));
2243 set_strinfo (idx
, si
);
2244 si
->dont_invalidate
= true;
2249 if (si
!= NULL
&& initializer_zerop (gimple_assign_rhs1 (stmt
)))
2251 /* Allow adjust_last_stmt to remove it if the stored '\0'
2252 is immediately overwritten. */
2253 laststmt
.stmt
= stmt
;
2254 laststmt
.len
= build_int_cst (size_type_node
, 1);
2255 laststmt
.stridx
= si
->idx
;
2260 /* Try to fold strstr (s, t) eq/ne s to strncmp (s, t, strlen (t)) eq/ne 0. */
2263 fold_strstr_to_strncmp (tree rhs1
, tree rhs2
, gimple
*stmt
)
2265 if (TREE_CODE (rhs1
) != SSA_NAME
2266 || TREE_CODE (rhs2
) != SSA_NAME
)
2269 gimple
*call_stmt
= NULL
;
2270 for (int pass
= 0; pass
< 2; pass
++)
2272 gimple
*g
= SSA_NAME_DEF_STMT (rhs1
);
2273 if (gimple_call_builtin_p (g
, BUILT_IN_STRSTR
)
2274 && has_single_use (rhs1
)
2275 && gimple_call_arg (g
, 0) == rhs2
)
2280 std::swap (rhs1
, rhs2
);
2285 tree arg0
= gimple_call_arg (call_stmt
, 0);
2289 tree arg1
= gimple_call_arg (call_stmt
, 1);
2290 tree arg1_len
= NULL_TREE
;
2291 int idx
= get_stridx (arg1
);
2296 arg1_len
= build_int_cst (size_type_node
, ~idx
);
2299 strinfo
*si
= get_strinfo (idx
);
2301 arg1_len
= get_string_length (si
);
2305 if (arg1_len
!= NULL_TREE
)
2307 gimple_stmt_iterator gsi
= gsi_for_stmt (call_stmt
);
2308 tree strncmp_decl
= builtin_decl_explicit (BUILT_IN_STRNCMP
);
2309 gcall
*strncmp_call
= gimple_build_call (strncmp_decl
, 3,
2310 arg0
, arg1
, arg1_len
);
2311 tree strncmp_lhs
= make_ssa_name (integer_type_node
);
2312 gimple_set_vuse (strncmp_call
, gimple_vuse (call_stmt
));
2313 gimple_call_set_lhs (strncmp_call
, strncmp_lhs
);
2314 gsi_remove (&gsi
, true);
2315 gsi_insert_before (&gsi
, strncmp_call
, GSI_SAME_STMT
);
2316 tree zero
= build_zero_cst (TREE_TYPE (strncmp_lhs
));
2318 if (is_gimple_assign (stmt
))
2320 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
2322 tree cond
= gimple_assign_rhs1 (stmt
);
2323 TREE_OPERAND (cond
, 0) = strncmp_lhs
;
2324 TREE_OPERAND (cond
, 1) = zero
;
2328 gimple_assign_set_rhs1 (stmt
, strncmp_lhs
);
2329 gimple_assign_set_rhs2 (stmt
, zero
);
2334 gcond
*cond
= as_a
<gcond
*> (stmt
);
2335 gimple_cond_set_lhs (cond
, strncmp_lhs
);
2336 gimple_cond_set_rhs (cond
, zero
);
2344 /* Attempt to optimize a single statement at *GSI using string length
2348 strlen_optimize_stmt (gimple_stmt_iterator
*gsi
)
2350 gimple
*stmt
= gsi_stmt (*gsi
);
2352 if (is_gimple_call (stmt
))
2354 tree callee
= gimple_call_fndecl (stmt
);
2355 if (valid_builtin_call (stmt
))
2356 switch (DECL_FUNCTION_CODE (callee
))
2358 case BUILT_IN_STRLEN
:
2359 case BUILT_IN_STRLEN_CHKP
:
2360 handle_builtin_strlen (gsi
);
2362 case BUILT_IN_STRCHR
:
2363 case BUILT_IN_STRCHR_CHKP
:
2364 handle_builtin_strchr (gsi
);
2366 case BUILT_IN_STRCPY
:
2367 case BUILT_IN_STRCPY_CHK
:
2368 case BUILT_IN_STPCPY
:
2369 case BUILT_IN_STPCPY_CHK
:
2370 case BUILT_IN_STRCPY_CHKP
:
2371 case BUILT_IN_STRCPY_CHK_CHKP
:
2372 case BUILT_IN_STPCPY_CHKP
:
2373 case BUILT_IN_STPCPY_CHK_CHKP
:
2374 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
2376 case BUILT_IN_MEMCPY
:
2377 case BUILT_IN_MEMCPY_CHK
:
2378 case BUILT_IN_MEMPCPY
:
2379 case BUILT_IN_MEMPCPY_CHK
:
2380 case BUILT_IN_MEMCPY_CHKP
:
2381 case BUILT_IN_MEMCPY_CHK_CHKP
:
2382 case BUILT_IN_MEMPCPY_CHKP
:
2383 case BUILT_IN_MEMPCPY_CHK_CHKP
:
2384 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
2386 case BUILT_IN_STRCAT
:
2387 case BUILT_IN_STRCAT_CHK
:
2388 case BUILT_IN_STRCAT_CHKP
:
2389 case BUILT_IN_STRCAT_CHK_CHKP
:
2390 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
2392 case BUILT_IN_MALLOC
:
2393 case BUILT_IN_CALLOC
:
2394 handle_builtin_malloc (DECL_FUNCTION_CODE (callee
), gsi
);
2396 case BUILT_IN_MEMSET
:
2397 if (!handle_builtin_memset (gsi
))
2400 case BUILT_IN_MEMCMP
:
2401 if (!handle_builtin_memcmp (gsi
))
2408 else if (is_gimple_assign (stmt
) && !gimple_clobber_p (stmt
))
2410 tree lhs
= gimple_assign_lhs (stmt
);
2412 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
2414 if (gimple_assign_single_p (stmt
)
2415 || (gimple_assign_cast_p (stmt
)
2416 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
2418 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
2419 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
2421 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
2422 handle_pointer_plus (gsi
);
2424 else if (TREE_CODE (lhs
) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
2426 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2427 if (code
== COND_EXPR
)
2429 tree cond
= gimple_assign_rhs1 (stmt
);
2430 enum tree_code cond_code
= TREE_CODE (cond
);
2432 if (cond_code
== EQ_EXPR
|| cond_code
== NE_EXPR
)
2433 fold_strstr_to_strncmp (TREE_OPERAND (cond
, 0),
2434 TREE_OPERAND (cond
, 1), stmt
);
2436 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
2437 fold_strstr_to_strncmp (gimple_assign_rhs1 (stmt
),
2438 gimple_assign_rhs2 (stmt
), stmt
);
2440 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
2442 tree type
= TREE_TYPE (lhs
);
2443 if (TREE_CODE (type
) == ARRAY_TYPE
)
2444 type
= TREE_TYPE (type
);
2445 if (TREE_CODE (type
) == INTEGER_TYPE
2446 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
2447 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
2449 if (! handle_char_store (gsi
))
2454 else if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
2456 enum tree_code code
= gimple_cond_code (cond
);
2457 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
2458 fold_strstr_to_strncmp (gimple_cond_lhs (stmt
),
2459 gimple_cond_rhs (stmt
), stmt
);
2462 if (gimple_vdef (stmt
))
2463 maybe_invalidate (stmt
);
2467 /* Recursively call maybe_invalidate on stmts that might be executed
2468 in between dombb and current bb and that contain a vdef. Stop when
2469 *count stmts are inspected, or if the whole strinfo vector has
2470 been invalidated. */
2473 do_invalidate (basic_block dombb
, gimple
*phi
, bitmap visited
, int *count
)
2475 unsigned int i
, n
= gimple_phi_num_args (phi
);
2477 for (i
= 0; i
< n
; i
++)
2479 tree vuse
= gimple_phi_arg_def (phi
, i
);
2480 gimple
*stmt
= SSA_NAME_DEF_STMT (vuse
);
2481 basic_block bb
= gimple_bb (stmt
);
2484 || !bitmap_set_bit (visited
, bb
->index
)
2485 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
2489 if (gimple_code (stmt
) == GIMPLE_PHI
)
2491 do_invalidate (dombb
, stmt
, visited
, count
);
2498 if (!maybe_invalidate (stmt
))
2503 vuse
= gimple_vuse (stmt
);
2504 stmt
= SSA_NAME_DEF_STMT (vuse
);
2505 if (gimple_bb (stmt
) != bb
)
2507 bb
= gimple_bb (stmt
);
2510 || !bitmap_set_bit (visited
, bb
->index
)
2511 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
2518 class strlen_dom_walker
: public dom_walker
2521 strlen_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
2523 virtual edge
before_dom_children (basic_block
);
2524 virtual void after_dom_children (basic_block
);
2527 /* Callback for walk_dominator_tree. Attempt to optimize various
2528 string ops by remembering string lengths pointed by pointer SSA_NAMEs. */
2531 strlen_dom_walker::before_dom_children (basic_block bb
)
2533 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
2536 stridx_to_strinfo
= NULL
;
2539 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) dombb
->aux
);
2540 if (stridx_to_strinfo
)
2542 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
2545 gphi
*phi
= gsi
.phi ();
2546 if (virtual_operand_p (gimple_phi_result (phi
)))
2548 bitmap visited
= BITMAP_ALLOC (NULL
);
2549 int count_vdef
= 100;
2550 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
2551 BITMAP_FREE (visited
);
2552 if (count_vdef
== 0)
2554 /* If there were too many vdefs in between immediate
2555 dominator and current bb, invalidate everything.
2556 If stridx_to_strinfo has been unshared, we need
2557 to free it, otherwise just set it to NULL. */
2558 if (!strinfo_shared ())
2564 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
2568 (*stridx_to_strinfo
)[i
] = NULL
;
2572 stridx_to_strinfo
= NULL
;
2580 /* If all PHI arguments have the same string index, the PHI result
2582 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
2585 gphi
*phi
= gsi
.phi ();
2586 tree result
= gimple_phi_result (phi
);
2587 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
2589 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
2592 unsigned int i
, n
= gimple_phi_num_args (phi
);
2593 for (i
= 1; i
< n
; i
++)
2594 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
2597 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
2602 /* Attempt to optimize individual statements. */
2603 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2604 if (strlen_optimize_stmt (&gsi
))
2607 bb
->aux
= stridx_to_strinfo
;
2608 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
2609 (*stridx_to_strinfo
)[0] = (strinfo
*) bb
;
2613 /* Callback for walk_dominator_tree. Free strinfo vector if it is
2614 owned by the current bb, clear bb->aux. */
2617 strlen_dom_walker::after_dom_children (basic_block bb
)
2621 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) bb
->aux
);
2622 if (vec_safe_length (stridx_to_strinfo
)
2623 && (*stridx_to_strinfo
)[0] == (strinfo
*) bb
)
2628 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
2630 vec_free (stridx_to_strinfo
);
2636 /* Main entry point. */
2640 const pass_data pass_data_strlen
=
2642 GIMPLE_PASS
, /* type */
2643 "strlen", /* name */
2644 OPTGROUP_NONE
, /* optinfo_flags */
2645 TV_TREE_STRLEN
, /* tv_id */
2646 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2647 0, /* properties_provided */
2648 0, /* properties_destroyed */
2649 0, /* todo_flags_start */
2650 0, /* todo_flags_finish */
2653 class pass_strlen
: public gimple_opt_pass
2656 pass_strlen (gcc::context
*ctxt
)
2657 : gimple_opt_pass (pass_data_strlen
, ctxt
)
2660 /* opt_pass methods: */
2661 virtual bool gate (function
*) { return flag_optimize_strlen
!= 0; }
2662 virtual unsigned int execute (function
*);
2664 }; // class pass_strlen
2667 pass_strlen::execute (function
*fun
)
2669 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
2672 calculate_dominance_info (CDI_DOMINATORS
);
2674 /* String length optimization is implemented as a walk of the dominator
2675 tree and a forward walk of statements within each block. */
2676 strlen_dom_walker (CDI_DOMINATORS
).walk (fun
->cfg
->x_entry_block_ptr
);
2678 ssa_ver_to_stridx
.release ();
2679 strinfo_pool
.release ();
2680 if (decl_to_stridxlist_htab
)
2682 obstack_free (&stridx_obstack
, NULL
);
2683 delete decl_to_stridxlist_htab
;
2684 decl_to_stridxlist_htab
= NULL
;
2686 laststmt
.stmt
= NULL
;
2687 laststmt
.len
= NULL_TREE
;
2688 laststmt
.stridx
= 0;
2696 make_pass_strlen (gcc::context
*ctxt
)
2698 return new pass_strlen (ctxt
);