1 /* String length optimization
2 Copyright (C) 2011-2016 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 /* Statement for delayed length computation. */
66 /* Pointer to '\0' if known, if NULL, it can be computed as
69 /* Reference count. Any changes to strinfo entry possibly shared
70 with dominating basic blocks need unshare_strinfo first, except
71 for dont_invalidate which affects only the immediately next
74 /* Copy of index. get_strinfo (si->idx) should return si; */
76 /* These 3 fields are for chaining related string pointers together.
78 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
79 strcpy (c, d); e = c + dl;
80 strinfo(a) -> strinfo(c) -> strinfo(e)
81 All have ->first field equal to strinfo(a)->idx and are doubly
82 chained through prev/next fields. The later strinfos are required
83 to point into the same string with zero or more bytes after
84 the previous pointer and all bytes in between the two pointers
85 must be non-zero. Functions like strcpy or memcpy are supposed
86 to adjust all previous strinfo lengths, but not following strinfo
87 lengths (those are uncertain, usually invalidated during
88 maybe_invalidate, except when the alias oracle knows better).
89 Functions like strcat on the other side adjust the whole
90 related strinfo chain.
91 They are updated lazily, so to use the chain the same first fields
92 and si->prev->next == si->idx needs to be verified. */
96 /* A flag whether the string is known to be written in the current
99 /* A flag for the next maybe_invalidate that this strinfo shouldn't
100 be invalidated. Always cleared by maybe_invalidate. */
101 bool dont_invalidate
;
104 /* Pool for allocating strinfo_struct entries. */
105 static object_allocator
<strinfo
> strinfo_pool ("strinfo pool");
107 /* Vector mapping positive string indexes to strinfo, for the
108 current basic block. The first pointer in the vector is special,
109 it is either NULL, meaning the vector isn't shared, or it is
110 a basic block pointer to the owner basic_block if shared.
111 If some other bb wants to modify the vector, the vector needs
112 to be unshared first, and only the owner bb is supposed to free it. */
113 static vec
<strinfo
*, va_heap
, vl_embed
> *stridx_to_strinfo
;
115 /* One OFFSET->IDX mapping. */
118 struct stridxlist
*next
;
119 HOST_WIDE_INT offset
;
123 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
124 struct decl_stridxlist_map
126 struct tree_map_base base
;
127 struct stridxlist list
;
130 /* Hash table for mapping decls to a chained list of offset -> idx
132 static hash_map
<tree_decl_hash
, stridxlist
> *decl_to_stridxlist_htab
;
134 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
135 static struct obstack stridx_obstack
;
137 /* Last memcpy statement if it could be adjusted if the trailing
138 '\0' written is immediately overwritten, or
139 *x = '\0' store that could be removed if it is immediately overwritten. */
140 struct laststmt_struct
147 static int get_stridx_plus_constant (strinfo
*, HOST_WIDE_INT
, tree
);
149 /* Return strinfo vector entry IDX. */
151 static inline strinfo
*
152 get_strinfo (int idx
)
154 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
156 return (*stridx_to_strinfo
)[idx
];
159 /* Helper function for get_stridx. */
162 get_addr_stridx (tree exp
, tree ptr
)
165 struct stridxlist
*list
, *last
= NULL
;
168 if (!decl_to_stridxlist_htab
)
171 base
= get_addr_base_and_unit_offset (exp
, &off
);
172 if (base
== NULL
|| !DECL_P (base
))
175 list
= decl_to_stridxlist_htab
->get (base
);
181 if (list
->offset
== off
)
183 if (list
->offset
> off
)
190 if (ptr
&& last
&& last
->idx
> 0)
192 strinfo
*si
= get_strinfo (last
->idx
);
195 && TREE_CODE (si
->length
) == INTEGER_CST
196 && compare_tree_int (si
->length
, off
- last
->offset
) != -1)
197 return get_stridx_plus_constant (si
, off
- last
->offset
, ptr
);
202 /* Return string index for EXP. */
205 get_stridx (tree exp
)
209 if (TREE_CODE (exp
) == SSA_NAME
)
211 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)])
212 return ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)];
215 HOST_WIDE_INT off
= 0;
216 for (i
= 0; i
< 5; i
++)
218 gimple
*def_stmt
= SSA_NAME_DEF_STMT (e
);
219 if (!is_gimple_assign (def_stmt
)
220 || gimple_assign_rhs_code (def_stmt
) != POINTER_PLUS_EXPR
)
222 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
223 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
224 if (TREE_CODE (rhs1
) != SSA_NAME
225 || !tree_fits_shwi_p (rhs2
))
227 HOST_WIDE_INT this_off
= tree_to_shwi (rhs2
);
230 off
= (unsigned HOST_WIDE_INT
) off
+ this_off
;
233 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)])
236 = get_strinfo (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)]);
239 && TREE_CODE (si
->length
) == INTEGER_CST
240 && compare_tree_int (si
->length
, off
) != -1)
241 return get_stridx_plus_constant (si
, off
, exp
);
248 if (TREE_CODE (exp
) == ADDR_EXPR
)
250 int idx
= get_addr_stridx (TREE_OPERAND (exp
, 0), exp
);
255 s
= string_constant (exp
, &o
);
257 && (o
== NULL_TREE
|| tree_fits_shwi_p (o
))
258 && TREE_STRING_LENGTH (s
) > 0)
260 HOST_WIDE_INT offset
= o
? tree_to_shwi (o
) : 0;
261 const char *p
= TREE_STRING_POINTER (s
);
262 int max
= TREE_STRING_LENGTH (s
) - 1;
264 if (p
[max
] == '\0' && offset
>= 0 && offset
<= max
)
265 return ~(int) strlen (p
+ offset
);
270 /* Return true if strinfo vector is shared with the immediate dominator. */
273 strinfo_shared (void)
275 return vec_safe_length (stridx_to_strinfo
)
276 && (*stridx_to_strinfo
)[0] != NULL
;
279 /* Unshare strinfo vector that is shared with the immediate dominator. */
282 unshare_strinfo_vec (void)
287 gcc_assert (strinfo_shared ());
288 stridx_to_strinfo
= vec_safe_copy (stridx_to_strinfo
);
289 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
292 (*stridx_to_strinfo
)[0] = NULL
;
295 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
296 Return a pointer to the location where the string index can
297 be stored (if 0) or is stored, or NULL if this can't be tracked. */
300 addr_stridxptr (tree exp
)
304 tree base
= get_addr_base_and_unit_offset (exp
, &off
);
305 if (base
== NULL_TREE
|| !DECL_P (base
))
308 if (!decl_to_stridxlist_htab
)
310 decl_to_stridxlist_htab
311 = new hash_map
<tree_decl_hash
, stridxlist
> (64);
312 gcc_obstack_init (&stridx_obstack
);
316 stridxlist
*list
= &decl_to_stridxlist_htab
->get_or_insert (base
, &existed
);
320 stridxlist
*before
= NULL
;
321 for (i
= 0; i
< 32; i
++)
323 if (list
->offset
== off
)
325 if (list
->offset
> off
&& before
== NULL
)
327 if (list
->next
== NULL
)
336 before
= XOBNEW (&stridx_obstack
, struct stridxlist
);
343 list
->next
= XOBNEW (&stridx_obstack
, struct stridxlist
);
353 /* Create a new string index, or return 0 if reached limit. */
356 new_stridx (tree exp
)
359 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
361 if (TREE_CODE (exp
) == SSA_NAME
)
363 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
366 ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)] = idx
;
369 if (TREE_CODE (exp
) == ADDR_EXPR
)
371 int *pidx
= addr_stridxptr (TREE_OPERAND (exp
, 0));
374 gcc_assert (*pidx
== 0);
375 *pidx
= max_stridx
++;
382 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
385 new_addr_stridx (tree exp
)
388 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
390 pidx
= addr_stridxptr (exp
);
393 gcc_assert (*pidx
== 0);
394 *pidx
= max_stridx
++;
400 /* Create a new strinfo. */
403 new_strinfo (tree ptr
, int idx
, tree length
)
405 strinfo
*si
= strinfo_pool
.allocate ();
409 si
->endptr
= NULL_TREE
;
415 si
->writable
= false;
416 si
->dont_invalidate
= false;
420 /* Decrease strinfo refcount and free it if not referenced anymore. */
423 free_strinfo (strinfo
*si
)
425 if (si
&& --si
->refcount
== 0)
426 strinfo_pool
.remove (si
);
429 /* Set strinfo in the vector entry IDX to SI. */
432 set_strinfo (int idx
, strinfo
*si
)
434 if (vec_safe_length (stridx_to_strinfo
) && (*stridx_to_strinfo
)[0])
435 unshare_strinfo_vec ();
436 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
437 vec_safe_grow_cleared (stridx_to_strinfo
, idx
+ 1);
438 (*stridx_to_strinfo
)[idx
] = si
;
441 /* Return string length, or NULL if it can't be computed. */
444 get_string_length (strinfo
*si
)
451 gimple
*stmt
= si
->stmt
, *lenstmt
;
452 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
453 tree callee
, lhs
, fn
, tem
;
455 gimple_stmt_iterator gsi
;
457 gcc_assert (is_gimple_call (stmt
));
458 callee
= gimple_call_fndecl (stmt
);
459 gcc_assert (callee
&& DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
);
460 lhs
= gimple_call_lhs (stmt
);
461 /* unshare_strinfo is intentionally not called here. The (delayed)
462 transformation of strcpy or strcat into stpcpy is done at the place
463 of the former strcpy/strcat call and so can affect all the strinfos
464 with the same stmt. If they were unshared before and transformation
465 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
466 just compute the right length. */
467 switch (DECL_FUNCTION_CODE (callee
))
469 case BUILT_IN_STRCAT
:
470 case BUILT_IN_STRCAT_CHK
:
471 case BUILT_IN_STRCAT_CHKP
:
472 case BUILT_IN_STRCAT_CHK_CHKP
:
473 gsi
= gsi_for_stmt (stmt
);
474 fn
= builtin_decl_implicit (BUILT_IN_STRLEN
);
475 gcc_assert (lhs
== NULL_TREE
);
476 tem
= unshare_expr (gimple_call_arg (stmt
, 0));
479 lenstmt
= gimple_build_call (chkp_maybe_create_clone (fn
)->decl
,
480 2, tem
, gimple_call_arg (stmt
, 1));
481 gimple_call_set_with_bounds (lenstmt
, true);
484 lenstmt
= gimple_build_call (fn
, 1, tem
);
485 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), lenstmt
);
486 gimple_call_set_lhs (lenstmt
, lhs
);
487 gimple_set_vuse (lenstmt
, gimple_vuse (stmt
));
488 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
489 tem
= gimple_call_arg (stmt
, 0);
490 if (!ptrofftype_p (TREE_TYPE (lhs
)))
492 lhs
= convert_to_ptrofftype (lhs
);
493 lhs
= force_gimple_operand_gsi (&gsi
, lhs
, true, NULL_TREE
,
494 true, GSI_SAME_STMT
);
496 lenstmt
= gimple_build_assign
497 (make_ssa_name (TREE_TYPE (gimple_call_arg (stmt
, 0))),
498 POINTER_PLUS_EXPR
,tem
, lhs
);
499 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
500 gimple_call_set_arg (stmt
, 0, gimple_assign_lhs (lenstmt
));
503 case BUILT_IN_STRCPY
:
504 case BUILT_IN_STRCPY_CHK
:
505 case BUILT_IN_STRCPY_CHKP
:
506 case BUILT_IN_STRCPY_CHK_CHKP
:
507 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY
));
508 if (gimple_call_num_args (stmt
) == (with_bounds
? 4 : 2))
509 fn
= builtin_decl_implicit (BUILT_IN_STPCPY
);
511 fn
= builtin_decl_explicit (BUILT_IN_STPCPY_CHK
);
513 fn
= chkp_maybe_create_clone (fn
)->decl
;
514 gcc_assert (lhs
== NULL_TREE
);
515 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
517 fprintf (dump_file
, "Optimizing: ");
518 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
520 gimple_call_set_fndecl (stmt
, fn
);
521 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), stmt
);
522 gimple_call_set_lhs (stmt
, lhs
);
524 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
526 fprintf (dump_file
, "into: ");
527 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
530 case BUILT_IN_STPCPY
:
531 case BUILT_IN_STPCPY_CHK
:
532 case BUILT_IN_STPCPY_CHKP
:
533 case BUILT_IN_STPCPY_CHK_CHKP
:
534 gcc_assert (lhs
!= NULL_TREE
);
535 loc
= gimple_location (stmt
);
538 lhs
= fold_convert_loc (loc
, size_type_node
, lhs
);
539 si
->length
= fold_convert_loc (loc
, size_type_node
, si
->ptr
);
540 si
->length
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
543 case BUILT_IN_MALLOC
:
545 /* BUILT_IN_CALLOC always has si->length set. */
555 /* Invalidate string length information for strings whose length
556 might change due to stores in stmt. */
559 maybe_invalidate (gimple
*stmt
)
563 bool nonempty
= false;
565 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
568 if (!si
->dont_invalidate
)
571 /* Do not use si->length. */
572 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, NULL_TREE
);
573 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
575 set_strinfo (i
, NULL
);
580 si
->dont_invalidate
= false;
586 /* Unshare strinfo record SI, if it has refcount > 1 or
587 if stridx_to_strinfo vector is shared with some other
591 unshare_strinfo (strinfo
*si
)
595 if (si
->refcount
== 1 && !strinfo_shared ())
598 nsi
= new_strinfo (si
->ptr
, si
->idx
, si
->length
);
599 nsi
->stmt
= si
->stmt
;
600 nsi
->endptr
= si
->endptr
;
601 nsi
->first
= si
->first
;
602 nsi
->prev
= si
->prev
;
603 nsi
->next
= si
->next
;
604 nsi
->writable
= si
->writable
;
605 set_strinfo (si
->idx
, nsi
);
610 /* Return first strinfo in the related strinfo chain
611 if all strinfos in between belong to the chain, otherwise
615 verify_related_strinfos (strinfo
*origsi
)
617 strinfo
*si
= origsi
, *psi
;
619 if (origsi
->first
== 0)
621 for (; si
->prev
; si
= psi
)
623 if (si
->first
!= origsi
->first
)
625 psi
= get_strinfo (si
->prev
);
628 if (psi
->next
!= si
->idx
)
631 if (si
->idx
!= si
->first
)
636 /* Attempt to create a new strinfo for BASESI + OFF, or find existing
637 strinfo if there is any. Return it's idx, or 0 if no strinfo has
641 get_stridx_plus_constant (strinfo
*basesi
, HOST_WIDE_INT off
, tree ptr
)
643 if (TREE_CODE (ptr
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
646 if (basesi
->length
== NULL_TREE
647 || TREE_CODE (basesi
->length
) != INTEGER_CST
648 || compare_tree_int (basesi
->length
, off
) == -1
649 || !tree_fits_shwi_p (basesi
->length
))
652 HOST_WIDE_INT len
= tree_to_shwi (basesi
->length
) - off
;
653 strinfo
*si
= basesi
, *chainsi
;
654 if (si
->first
|| si
->prev
|| si
->next
)
655 si
= verify_related_strinfos (basesi
);
657 || si
->length
== NULL_TREE
658 || TREE_CODE (si
->length
) != INTEGER_CST
)
661 if (TREE_CODE (ptr
) == SSA_NAME
662 && ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
663 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
665 gcc_checking_assert (compare_tree_int (si
->length
, off
) != -1);
666 for (chainsi
= si
; chainsi
->next
; chainsi
= si
)
668 si
= get_strinfo (chainsi
->next
);
670 || si
->first
!= chainsi
->first
671 || si
->prev
!= chainsi
->idx
672 || si
->length
== NULL_TREE
673 || TREE_CODE (si
->length
) != INTEGER_CST
)
675 int r
= compare_tree_int (si
->length
, len
);
680 if (TREE_CODE (ptr
) == SSA_NAME
)
681 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = si
->idx
;
684 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
685 if (pidx
!= NULL
&& *pidx
== 0)
694 int idx
= new_stridx (ptr
);
697 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, len
));
698 set_strinfo (idx
, si
);
701 strinfo
*nextsi
= unshare_strinfo (get_strinfo (chainsi
->next
));
702 si
->next
= nextsi
->idx
;
705 chainsi
= unshare_strinfo (chainsi
);
706 if (chainsi
->first
== 0)
707 chainsi
->first
= chainsi
->idx
;
709 if (chainsi
->endptr
== NULL_TREE
&& len
== 0)
710 chainsi
->endptr
= ptr
;
711 si
->endptr
= chainsi
->endptr
;
712 si
->prev
= chainsi
->idx
;
713 si
->first
= chainsi
->first
;
714 si
->writable
= chainsi
->writable
;
718 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
719 to a zero-length string and if possible chain it to a related strinfo
720 chain whose part is or might be CHAINSI. */
723 zero_length_string (tree ptr
, strinfo
*chainsi
)
727 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
728 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
729 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
730 && ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] == 0);
732 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
736 si
= verify_related_strinfos (chainsi
);
740 for (; chainsi
->next
; chainsi
= si
)
742 if (chainsi
->endptr
== NULL_TREE
)
744 chainsi
= unshare_strinfo (chainsi
);
745 chainsi
->endptr
= ptr
;
747 si
= get_strinfo (chainsi
->next
);
749 || si
->first
!= chainsi
->first
750 || si
->prev
!= chainsi
->idx
)
753 gcc_assert (chainsi
->length
|| chainsi
->stmt
);
754 if (chainsi
->endptr
== NULL_TREE
)
756 chainsi
= unshare_strinfo (chainsi
);
757 chainsi
->endptr
= ptr
;
759 if (chainsi
->length
&& integer_zerop (chainsi
->length
))
763 chainsi
= unshare_strinfo (chainsi
);
766 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = chainsi
->idx
;
770 else if (chainsi
->first
|| chainsi
->prev
|| chainsi
->next
)
772 chainsi
= unshare_strinfo (chainsi
);
778 idx
= new_stridx (ptr
);
781 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, 0));
782 set_strinfo (idx
, si
);
786 chainsi
= unshare_strinfo (chainsi
);
787 if (chainsi
->first
== 0)
788 chainsi
->first
= chainsi
->idx
;
790 if (chainsi
->endptr
== NULL_TREE
)
791 chainsi
->endptr
= ptr
;
792 si
->prev
= chainsi
->idx
;
793 si
->first
= chainsi
->first
;
794 si
->writable
= chainsi
->writable
;
799 /* For strinfo ORIGSI whose length has been just updated
800 update also related strinfo lengths (add ADJ to each,
801 but don't adjust ORIGSI). */
804 adjust_related_strinfos (location_t loc
, strinfo
*origsi
, tree adj
)
806 strinfo
*si
= verify_related_strinfos (origsi
);
819 si
= unshare_strinfo (si
);
822 tem
= fold_convert_loc (loc
, TREE_TYPE (si
->length
), adj
);
823 si
->length
= fold_build2_loc (loc
, PLUS_EXPR
,
824 TREE_TYPE (si
->length
), si
->length
,
827 else if (si
->stmt
!= NULL
)
828 /* Delayed length computation is unaffected. */
833 si
->endptr
= NULL_TREE
;
834 si
->dont_invalidate
= true;
838 nsi
= get_strinfo (si
->next
);
840 || nsi
->first
!= si
->first
841 || nsi
->prev
!= si
->idx
)
847 /* Find if there are other SSA_NAME pointers equal to PTR
848 for which we don't track their string lengths yet. If so, use
852 find_equal_ptrs (tree ptr
, int idx
)
854 if (TREE_CODE (ptr
) != SSA_NAME
)
858 gimple
*stmt
= SSA_NAME_DEF_STMT (ptr
);
859 if (!is_gimple_assign (stmt
))
861 ptr
= gimple_assign_rhs1 (stmt
);
862 switch (gimple_assign_rhs_code (stmt
))
867 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)))
869 if (TREE_CODE (ptr
) == SSA_NAME
)
871 if (TREE_CODE (ptr
) != ADDR_EXPR
)
876 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
877 if (pidx
!= NULL
&& *pidx
== 0)
885 /* We might find an endptr created in this pass. Grow the
886 vector in that case. */
887 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
888 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
890 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] != 0)
892 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = idx
;
896 /* Return true if STMT is a call to a builtin function with the right
897 arguments and attributes that should be considered for optimization
901 valid_builtin_call (gimple
*stmt
)
903 if (!gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
906 tree callee
= gimple_call_fndecl (stmt
);
907 switch (DECL_FUNCTION_CODE (callee
))
909 case BUILT_IN_MEMCMP
:
910 case BUILT_IN_MEMCMP_EQ
:
911 case BUILT_IN_STRCHR
:
912 case BUILT_IN_STRCHR_CHKP
:
913 case BUILT_IN_STRLEN
:
914 case BUILT_IN_STRLEN_CHKP
:
915 /* The above functions should be pure. Punt if they aren't. */
916 if (gimple_vdef (stmt
) || gimple_vuse (stmt
) == NULL_TREE
)
920 case BUILT_IN_CALLOC
:
921 case BUILT_IN_MALLOC
:
922 case BUILT_IN_MEMCPY
:
923 case BUILT_IN_MEMCPY_CHK
:
924 case BUILT_IN_MEMCPY_CHKP
:
925 case BUILT_IN_MEMCPY_CHK_CHKP
:
926 case BUILT_IN_MEMPCPY
:
927 case BUILT_IN_MEMPCPY_CHK
:
928 case BUILT_IN_MEMPCPY_CHKP
:
929 case BUILT_IN_MEMPCPY_CHK_CHKP
:
930 case BUILT_IN_MEMSET
:
931 case BUILT_IN_STPCPY
:
932 case BUILT_IN_STPCPY_CHK
:
933 case BUILT_IN_STPCPY_CHKP
:
934 case BUILT_IN_STPCPY_CHK_CHKP
:
935 case BUILT_IN_STRCAT
:
936 case BUILT_IN_STRCAT_CHK
:
937 case BUILT_IN_STRCAT_CHKP
:
938 case BUILT_IN_STRCAT_CHK_CHKP
:
939 case BUILT_IN_STRCPY
:
940 case BUILT_IN_STRCPY_CHK
:
941 case BUILT_IN_STRCPY_CHKP
:
942 case BUILT_IN_STRCPY_CHK_CHKP
:
943 /* The above functions should be neither const nor pure. Punt if they
945 if (gimple_vdef (stmt
) == NULL_TREE
|| gimple_vuse (stmt
) == NULL_TREE
)
956 /* If the last .MEM setter statement before STMT is
957 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
958 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
959 just memcpy (x, y, strlen (y)). SI must be the zero length
963 adjust_last_stmt (strinfo
*si
, gimple
*stmt
, bool is_strcat
)
965 tree vuse
, callee
, len
;
966 struct laststmt_struct last
= laststmt
;
967 strinfo
*lastsi
, *firstsi
;
968 unsigned len_arg_no
= 2;
970 laststmt
.stmt
= NULL
;
971 laststmt
.len
= NULL_TREE
;
974 if (last
.stmt
== NULL
)
977 vuse
= gimple_vuse (stmt
);
978 if (vuse
== NULL_TREE
979 || SSA_NAME_DEF_STMT (vuse
) != last
.stmt
980 || !has_single_use (vuse
))
983 gcc_assert (last
.stridx
> 0);
984 lastsi
= get_strinfo (last
.stridx
);
990 if (lastsi
->first
== 0 || lastsi
->first
!= si
->first
)
993 firstsi
= verify_related_strinfos (si
);
996 while (firstsi
!= lastsi
)
999 if (firstsi
->next
== 0)
1001 nextsi
= get_strinfo (firstsi
->next
);
1003 || nextsi
->prev
!= firstsi
->idx
1004 || nextsi
->first
!= si
->first
)
1012 if (si
->length
== NULL_TREE
|| !integer_zerop (si
->length
))
1016 if (is_gimple_assign (last
.stmt
))
1018 gimple_stmt_iterator gsi
;
1020 if (!integer_zerop (gimple_assign_rhs1 (last
.stmt
)))
1022 if (stmt_could_throw_p (last
.stmt
))
1024 gsi
= gsi_for_stmt (last
.stmt
);
1025 unlink_stmt_vdef (last
.stmt
);
1026 release_defs (last
.stmt
);
1027 gsi_remove (&gsi
, true);
1031 if (!valid_builtin_call (last
.stmt
))
1034 callee
= gimple_call_fndecl (last
.stmt
);
1035 switch (DECL_FUNCTION_CODE (callee
))
1037 case BUILT_IN_MEMCPY
:
1038 case BUILT_IN_MEMCPY_CHK
:
1040 case BUILT_IN_MEMCPY_CHKP
:
1041 case BUILT_IN_MEMCPY_CHK_CHKP
:
1048 len
= gimple_call_arg (last
.stmt
, len_arg_no
);
1049 if (tree_fits_uhwi_p (len
))
1051 if (!tree_fits_uhwi_p (last
.len
)
1052 || integer_zerop (len
)
1053 || tree_to_uhwi (len
) != tree_to_uhwi (last
.len
) + 1)
1055 /* Don't adjust the length if it is divisible by 4, it is more efficient
1056 to store the extra '\0' in that case. */
1057 if ((tree_to_uhwi (len
) & 3) == 0)
1060 else if (TREE_CODE (len
) == SSA_NAME
)
1062 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1063 if (!is_gimple_assign (def_stmt
)
1064 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1065 || gimple_assign_rhs1 (def_stmt
) != last
.len
1066 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1072 gimple_call_set_arg (last
.stmt
, len_arg_no
, last
.len
);
1073 update_stmt (last
.stmt
);
1076 /* Handle a strlen call. If strlen of the argument is known, replace
1077 the strlen call with the known value, otherwise remember that strlen
1078 of the argument is stored in the lhs SSA_NAME. */
1081 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
1085 gimple
*stmt
= gsi_stmt (*gsi
);
1086 tree lhs
= gimple_call_lhs (stmt
);
1088 if (lhs
== NULL_TREE
)
1091 src
= gimple_call_arg (stmt
, 0);
1092 idx
= get_stridx (src
);
1099 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
1103 si
= get_strinfo (idx
);
1105 rhs
= get_string_length (si
);
1107 if (rhs
!= NULL_TREE
)
1109 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1111 fprintf (dump_file
, "Optimizing: ");
1112 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1114 rhs
= unshare_expr (rhs
);
1115 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
1116 rhs
= fold_convert_loc (gimple_location (stmt
),
1117 TREE_TYPE (lhs
), rhs
);
1118 if (!update_call_from_tree (gsi
, rhs
))
1119 gimplify_and_update_call_from_tree (gsi
, rhs
);
1120 stmt
= gsi_stmt (*gsi
);
1122 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1124 fprintf (dump_file
, "into: ");
1125 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1128 && TREE_CODE (si
->length
) != SSA_NAME
1129 && TREE_CODE (si
->length
) != INTEGER_CST
1130 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1132 si
= unshare_strinfo (si
);
1138 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1141 idx
= new_stridx (src
);
1142 else if (get_strinfo (idx
) != NULL
)
1146 strinfo
*si
= new_strinfo (src
, idx
, lhs
);
1147 set_strinfo (idx
, si
);
1148 find_equal_ptrs (src
, idx
);
1152 /* Handle a strchr call. If strlen of the first argument is known, replace
1153 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
1154 that lhs of the call is endptr and strlen of the argument is endptr - x. */
1157 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
1161 gimple
*stmt
= gsi_stmt (*gsi
);
1162 tree lhs
= gimple_call_lhs (stmt
);
1163 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1165 if (lhs
== NULL_TREE
)
1168 if (!integer_zerop (gimple_call_arg (stmt
, with_bounds
? 2 : 1)))
1171 src
= gimple_call_arg (stmt
, 0);
1172 idx
= get_stridx (src
);
1179 rhs
= build_int_cst (size_type_node
, ~idx
);
1183 si
= get_strinfo (idx
);
1185 rhs
= get_string_length (si
);
1187 if (rhs
!= NULL_TREE
)
1189 location_t loc
= gimple_location (stmt
);
1191 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1193 fprintf (dump_file
, "Optimizing: ");
1194 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1196 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
1198 rhs
= unshare_expr (si
->endptr
);
1199 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1201 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1205 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1206 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1207 TREE_TYPE (src
), src
, rhs
);
1208 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1210 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1212 if (!update_call_from_tree (gsi
, rhs
))
1213 gimplify_and_update_call_from_tree (gsi
, rhs
);
1214 stmt
= gsi_stmt (*gsi
);
1216 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1218 fprintf (dump_file
, "into: ");
1219 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1222 && si
->endptr
== NULL_TREE
1223 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1225 si
= unshare_strinfo (si
);
1228 zero_length_string (lhs
, si
);
1232 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1234 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1237 idx
= new_stridx (src
);
1238 else if (get_strinfo (idx
) != NULL
)
1240 zero_length_string (lhs
, NULL
);
1245 location_t loc
= gimple_location (stmt
);
1246 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1247 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1248 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1249 size_type_node
, lhsu
, srcu
);
1250 strinfo
*si
= new_strinfo (src
, idx
, length
);
1252 set_strinfo (idx
, si
);
1253 find_equal_ptrs (src
, idx
);
1254 zero_length_string (lhs
, si
);
1258 zero_length_string (lhs
, NULL
);
1261 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1262 If strlen of the second argument is known, strlen of the first argument
1263 is the same after this call. Furthermore, attempt to convert it to
1267 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1270 tree src
, dst
, srclen
, len
, lhs
, args
, type
, fn
, oldlen
;
1272 gimple
*stmt
= gsi_stmt (*gsi
);
1273 strinfo
*si
, *dsi
, *olddsi
, *zsi
;
1275 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1277 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1278 dst
= gimple_call_arg (stmt
, 0);
1279 lhs
= gimple_call_lhs (stmt
);
1280 idx
= get_stridx (src
);
1283 si
= get_strinfo (idx
);
1285 didx
= get_stridx (dst
);
1289 olddsi
= get_strinfo (didx
);
1294 adjust_last_stmt (olddsi
, stmt
, false);
1298 srclen
= get_string_length (si
);
1300 srclen
= build_int_cst (size_type_node
, ~idx
);
1302 loc
= gimple_location (stmt
);
1303 if (srclen
== NULL_TREE
)
1306 case BUILT_IN_STRCPY
:
1307 case BUILT_IN_STRCPY_CHK
:
1308 case BUILT_IN_STRCPY_CHKP
:
1309 case BUILT_IN_STRCPY_CHK_CHKP
:
1310 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1313 case BUILT_IN_STPCPY
:
1314 case BUILT_IN_STPCPY_CHK
:
1315 case BUILT_IN_STPCPY_CHKP
:
1316 case BUILT_IN_STPCPY_CHK_CHKP
:
1317 if (lhs
== NULL_TREE
)
1321 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1322 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1323 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1333 didx
= new_stridx (dst
);
1339 oldlen
= olddsi
->length
;
1340 dsi
= unshare_strinfo (olddsi
);
1341 dsi
->length
= srclen
;
1342 /* Break the chain, so adjust_related_strinfo on later pointers in
1343 the chain won't adjust this one anymore. */
1346 dsi
->endptr
= NULL_TREE
;
1350 dsi
= new_strinfo (dst
, didx
, srclen
);
1351 set_strinfo (didx
, dsi
);
1352 find_equal_ptrs (dst
, didx
);
1354 dsi
->writable
= true;
1355 dsi
->dont_invalidate
= true;
1357 if (dsi
->length
== NULL_TREE
)
1361 /* If string length of src is unknown, use delayed length
1362 computation. If string lenth of dst will be needed, it
1363 can be computed by transforming this strcpy call into
1364 stpcpy and subtracting dst from the return value. */
1366 /* Look for earlier strings whose length could be determined if
1367 this strcpy is turned into an stpcpy. */
1369 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1371 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1373 /* When setting a stmt for delayed length computation
1374 prevent all strinfos through dsi from being
1376 chainsi
= unshare_strinfo (chainsi
);
1377 chainsi
->stmt
= stmt
;
1378 chainsi
->length
= NULL_TREE
;
1379 chainsi
->endptr
= NULL_TREE
;
1380 chainsi
->dont_invalidate
= true;
1389 tree adj
= NULL_TREE
;
1390 if (oldlen
== NULL_TREE
)
1392 else if (integer_zerop (oldlen
))
1394 else if (TREE_CODE (oldlen
) == INTEGER_CST
1395 || TREE_CODE (srclen
) == INTEGER_CST
)
1396 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1397 TREE_TYPE (srclen
), srclen
,
1398 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1400 if (adj
!= NULL_TREE
)
1401 adjust_related_strinfos (loc
, dsi
, adj
);
1405 /* strcpy src may not overlap dst, so src doesn't need to be
1406 invalidated either. */
1408 si
->dont_invalidate
= true;
1414 case BUILT_IN_STRCPY
:
1415 case BUILT_IN_STRCPY_CHKP
:
1416 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1418 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1420 case BUILT_IN_STRCPY_CHK
:
1421 case BUILT_IN_STRCPY_CHK_CHKP
:
1422 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1424 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1426 case BUILT_IN_STPCPY
:
1427 case BUILT_IN_STPCPY_CHKP
:
1428 /* This would need adjustment of the lhs (subtract one),
1429 or detection that the trailing '\0' doesn't need to be
1430 written, if it will be immediately overwritten.
1431 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1435 zsi
= zero_length_string (lhs
, dsi
);
1438 case BUILT_IN_STPCPY_CHK
:
1439 case BUILT_IN_STPCPY_CHK_CHKP
:
1440 /* This would need adjustment of the lhs (subtract one),
1441 or detection that the trailing '\0' doesn't need to be
1442 written, if it will be immediately overwritten.
1443 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1447 zsi
= zero_length_string (lhs
, dsi
);
1454 zsi
->dont_invalidate
= true;
1456 if (fn
== NULL_TREE
)
1459 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1460 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1462 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1463 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1464 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1466 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1468 fprintf (dump_file
, "Optimizing: ");
1469 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1473 fn
= chkp_maybe_create_clone (fn
)->decl
;
1474 if (gimple_call_num_args (stmt
) == 4)
1475 success
= update_gimple_call (gsi
, fn
, 5, dst
,
1476 gimple_call_arg (stmt
, 1),
1478 gimple_call_arg (stmt
, 3),
1481 success
= update_gimple_call (gsi
, fn
, 6, dst
,
1482 gimple_call_arg (stmt
, 1),
1484 gimple_call_arg (stmt
, 3),
1486 gimple_call_arg (stmt
, 4));
1489 if (gimple_call_num_args (stmt
) == 2)
1490 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1492 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1493 gimple_call_arg (stmt
, 2));
1496 stmt
= gsi_stmt (*gsi
);
1497 gimple_call_set_with_bounds (stmt
, with_bounds
);
1499 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1501 fprintf (dump_file
, "into: ");
1502 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1504 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1505 laststmt
.stmt
= stmt
;
1506 laststmt
.len
= srclen
;
1507 laststmt
.stridx
= dsi
->idx
;
1509 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1510 fprintf (dump_file
, "not possible.\n");
1513 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1514 If strlen of the second argument is known and length of the third argument
1515 is that plus one, strlen of the first argument is the same after this
1519 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1522 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
1523 gimple
*stmt
= gsi_stmt (*gsi
);
1524 strinfo
*si
, *dsi
, *olddsi
;
1525 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1527 len
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
1528 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1529 dst
= gimple_call_arg (stmt
, 0);
1530 idx
= get_stridx (src
);
1534 didx
= get_stridx (dst
);
1537 olddsi
= get_strinfo (didx
);
1542 && tree_fits_uhwi_p (len
)
1543 && !integer_zerop (len
))
1544 adjust_last_stmt (olddsi
, stmt
, false);
1550 /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */
1551 si
= get_strinfo (idx
);
1552 if (si
== NULL
|| si
->length
== NULL_TREE
)
1554 if (TREE_CODE (len
) != SSA_NAME
)
1556 def_stmt
= SSA_NAME_DEF_STMT (len
);
1557 if (!is_gimple_assign (def_stmt
)
1558 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1559 || gimple_assign_rhs1 (def_stmt
) != si
->length
1560 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1566 /* Handle memcpy (x, "abcd", 5) or
1567 memcpy (x, "abc\0uvw", 7). */
1568 if (!tree_fits_uhwi_p (len
)
1569 || tree_to_uhwi (len
) <= (unsigned HOST_WIDE_INT
) ~idx
)
1573 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
1574 adjust_last_stmt (olddsi
, stmt
, false);
1578 didx
= new_stridx (dst
);
1583 newlen
= si
->length
;
1585 newlen
= build_int_cst (size_type_node
, ~idx
);
1589 dsi
= unshare_strinfo (olddsi
);
1590 oldlen
= olddsi
->length
;
1591 dsi
->length
= newlen
;
1592 /* Break the chain, so adjust_related_strinfo on later pointers in
1593 the chain won't adjust this one anymore. */
1596 dsi
->endptr
= NULL_TREE
;
1600 dsi
= new_strinfo (dst
, didx
, newlen
);
1601 set_strinfo (didx
, dsi
);
1602 find_equal_ptrs (dst
, didx
);
1604 dsi
->writable
= true;
1605 dsi
->dont_invalidate
= true;
1608 tree adj
= NULL_TREE
;
1609 location_t loc
= gimple_location (stmt
);
1610 if (oldlen
== NULL_TREE
)
1612 else if (integer_zerop (oldlen
))
1614 else if (TREE_CODE (oldlen
) == INTEGER_CST
1615 || TREE_CODE (dsi
->length
) == INTEGER_CST
)
1616 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1617 TREE_TYPE (dsi
->length
), dsi
->length
,
1618 fold_convert_loc (loc
, TREE_TYPE (dsi
->length
),
1620 if (adj
!= NULL_TREE
)
1621 adjust_related_strinfos (loc
, dsi
, adj
);
1625 /* memcpy src may not overlap dst, so src doesn't need to be
1626 invalidated either. */
1628 si
->dont_invalidate
= true;
1630 lhs
= gimple_call_lhs (stmt
);
1633 case BUILT_IN_MEMCPY
:
1634 case BUILT_IN_MEMCPY_CHK
:
1635 case BUILT_IN_MEMCPY_CHKP
:
1636 case BUILT_IN_MEMCPY_CHK_CHKP
:
1637 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1638 laststmt
.stmt
= stmt
;
1639 laststmt
.len
= dsi
->length
;
1640 laststmt
.stridx
= dsi
->idx
;
1642 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1644 case BUILT_IN_MEMPCPY
:
1645 case BUILT_IN_MEMPCPY_CHK
:
1646 case BUILT_IN_MEMPCPY_CHKP
:
1647 case BUILT_IN_MEMPCPY_CHK_CHKP
:
1654 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
1655 If strlen of the second argument is known, strlen of the first argument
1656 is increased by the length of the second argument. Furthermore, attempt
1657 to convert it to memcpy/strcpy if the length of the first argument
1661 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1664 tree src
, dst
, srclen
, dstlen
, len
, lhs
, args
, type
, fn
, objsz
, endptr
;
1666 gimple
*stmt
= gsi_stmt (*gsi
);
1669 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1671 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1672 dst
= gimple_call_arg (stmt
, 0);
1673 lhs
= gimple_call_lhs (stmt
);
1675 didx
= get_stridx (dst
);
1681 dsi
= get_strinfo (didx
);
1682 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
1684 /* strcat (p, q) can be transformed into
1685 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
1686 with length endptr - p if we need to compute the length
1687 later on. Don't do this transformation if we don't need
1689 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
1693 didx
= new_stridx (dst
);
1699 dsi
= new_strinfo (dst
, didx
, NULL_TREE
);
1700 set_strinfo (didx
, dsi
);
1701 find_equal_ptrs (dst
, didx
);
1705 dsi
= unshare_strinfo (dsi
);
1706 dsi
->length
= NULL_TREE
;
1708 dsi
->endptr
= NULL_TREE
;
1710 dsi
->writable
= true;
1712 dsi
->dont_invalidate
= true;
1719 idx
= get_stridx (src
);
1721 srclen
= build_int_cst (size_type_node
, ~idx
);
1724 si
= get_strinfo (idx
);
1726 srclen
= get_string_length (si
);
1729 loc
= gimple_location (stmt
);
1730 dstlen
= dsi
->length
;
1731 endptr
= dsi
->endptr
;
1733 dsi
= unshare_strinfo (dsi
);
1734 dsi
->endptr
= NULL_TREE
;
1736 dsi
->writable
= true;
1738 if (srclen
!= NULL_TREE
)
1740 dsi
->length
= fold_build2_loc (loc
, PLUS_EXPR
, TREE_TYPE (dsi
->length
),
1741 dsi
->length
, srclen
);
1742 adjust_related_strinfos (loc
, dsi
, srclen
);
1743 dsi
->dont_invalidate
= true;
1748 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1749 dsi
->dont_invalidate
= true;
1753 /* strcat src may not overlap dst, so src doesn't need to be
1754 invalidated either. */
1755 si
->dont_invalidate
= true;
1757 /* For now. Could remove the lhs from the call and add
1758 lhs = dst; afterwards. */
1766 case BUILT_IN_STRCAT
:
1767 case BUILT_IN_STRCAT_CHKP
:
1768 if (srclen
!= NULL_TREE
)
1769 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1771 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
1773 case BUILT_IN_STRCAT_CHK
:
1774 case BUILT_IN_STRCAT_CHK_CHKP
:
1775 if (srclen
!= NULL_TREE
)
1776 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1778 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
1779 objsz
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
1785 if (fn
== NULL_TREE
)
1789 if (srclen
!= NULL_TREE
)
1791 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1792 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1794 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1795 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
1796 build_int_cst (type
, 1));
1797 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1801 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
1803 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1804 TREE_TYPE (dst
), unshare_expr (dst
),
1805 fold_convert_loc (loc
, sizetype
,
1806 unshare_expr (dstlen
)));
1807 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
1809 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1811 fprintf (dump_file
, "Optimizing: ");
1812 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1816 fn
= chkp_maybe_create_clone (fn
)->decl
;
1817 if (srclen
!= NULL_TREE
)
1818 success
= update_gimple_call (gsi
, fn
, 5 + (objsz
!= NULL_TREE
),
1820 gimple_call_arg (stmt
, 1),
1822 gimple_call_arg (stmt
, 3),
1825 success
= update_gimple_call (gsi
, fn
, 4 + (objsz
!= NULL_TREE
),
1827 gimple_call_arg (stmt
, 1),
1829 gimple_call_arg (stmt
, 3),
1833 if (srclen
!= NULL_TREE
)
1834 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
1835 dst
, src
, len
, objsz
);
1837 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
1841 stmt
= gsi_stmt (*gsi
);
1842 gimple_call_set_with_bounds (stmt
, with_bounds
);
1844 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1846 fprintf (dump_file
, "into: ");
1847 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1849 /* If srclen == NULL, note that current string length can be
1850 computed by transforming this strcpy into stpcpy. */
1851 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
1853 adjust_last_stmt (dsi
, stmt
, true);
1854 if (srclen
!= NULL_TREE
)
1856 laststmt
.stmt
= stmt
;
1857 laststmt
.len
= srclen
;
1858 laststmt
.stridx
= dsi
->idx
;
1861 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1862 fprintf (dump_file
, "not possible.\n");
1865 /* Handle a call to malloc or calloc. */
1868 handle_builtin_malloc (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1870 gimple
*stmt
= gsi_stmt (*gsi
);
1871 tree lhs
= gimple_call_lhs (stmt
);
1872 gcc_assert (get_stridx (lhs
) == 0);
1873 int idx
= new_stridx (lhs
);
1874 tree length
= NULL_TREE
;
1875 if (bcode
== BUILT_IN_CALLOC
)
1876 length
= build_int_cst (size_type_node
, 0);
1877 strinfo
*si
= new_strinfo (lhs
, idx
, length
);
1878 if (bcode
== BUILT_IN_CALLOC
)
1880 set_strinfo (idx
, si
);
1881 si
->writable
= true;
1883 si
->dont_invalidate
= true;
1886 /* Handle a call to memset.
1887 After a call to calloc, memset(,0,) is unnecessary.
1888 memset(malloc(n),0,n) is calloc(n,1). */
1891 handle_builtin_memset (gimple_stmt_iterator
*gsi
)
1893 gimple
*stmt2
= gsi_stmt (*gsi
);
1894 if (!integer_zerop (gimple_call_arg (stmt2
, 1)))
1896 tree ptr
= gimple_call_arg (stmt2
, 0);
1897 int idx1
= get_stridx (ptr
);
1900 strinfo
*si1
= get_strinfo (idx1
);
1903 gimple
*stmt1
= si1
->stmt
;
1904 if (!stmt1
|| !is_gimple_call (stmt1
))
1906 tree callee1
= gimple_call_fndecl (stmt1
);
1907 if (!valid_builtin_call (stmt1
))
1909 enum built_in_function code1
= DECL_FUNCTION_CODE (callee1
);
1910 tree size
= gimple_call_arg (stmt2
, 2);
1911 if (code1
== BUILT_IN_CALLOC
)
1912 /* Not touching stmt1 */ ;
1913 else if (code1
== BUILT_IN_MALLOC
1914 && operand_equal_p (gimple_call_arg (stmt1
, 0), size
, 0))
1916 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt1
);
1917 update_gimple_call (&gsi1
, builtin_decl_implicit (BUILT_IN_CALLOC
), 2,
1918 size
, build_one_cst (size_type_node
));
1919 si1
->length
= build_int_cst (size_type_node
, 0);
1920 si1
->stmt
= gsi_stmt (gsi1
);
1924 tree lhs
= gimple_call_lhs (stmt2
);
1925 unlink_stmt_vdef (stmt2
);
1928 gimple
*assign
= gimple_build_assign (lhs
, ptr
);
1929 gsi_replace (gsi
, assign
, false);
1933 gsi_remove (gsi
, true);
1934 release_defs (stmt2
);
1940 /* Handle a call to memcmp. We try to handle small comparisons by
1941 converting them to load and compare, and replacing the call to memcmp
1942 with a __builtin_memcmp_eq call where possible. */
1945 handle_builtin_memcmp (gimple_stmt_iterator
*gsi
)
1947 gcall
*stmt2
= as_a
<gcall
*> (gsi_stmt (*gsi
));
1948 tree res
= gimple_call_lhs (stmt2
);
1949 tree arg1
= gimple_call_arg (stmt2
, 0);
1950 tree arg2
= gimple_call_arg (stmt2
, 1);
1951 tree len
= gimple_call_arg (stmt2
, 2);
1952 unsigned HOST_WIDE_INT leni
;
1953 use_operand_p use_p
;
1954 imm_use_iterator iter
;
1959 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
1961 gimple
*ustmt
= USE_STMT (use_p
);
1963 if (is_gimple_debug (ustmt
))
1965 if (gimple_code (ustmt
) == GIMPLE_ASSIGN
)
1967 gassign
*asgn
= as_a
<gassign
*> (ustmt
);
1968 tree_code code
= gimple_assign_rhs_code (asgn
);
1969 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
1970 || !integer_zerop (gimple_assign_rhs2 (asgn
)))
1973 else if (gimple_code (ustmt
) == GIMPLE_COND
)
1975 tree_code code
= gimple_cond_code (ustmt
);
1976 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
1977 || !integer_zerop (gimple_cond_rhs (ustmt
)))
1984 if (tree_fits_uhwi_p (len
)
1985 && (leni
= tree_to_uhwi (len
)) <= GET_MODE_SIZE (word_mode
)
1986 && pow2p_hwi (leni
))
1988 leni
*= CHAR_TYPE_SIZE
;
1989 unsigned align1
= get_pointer_alignment (arg1
);
1990 unsigned align2
= get_pointer_alignment (arg2
);
1991 unsigned align
= MIN (align1
, align2
);
1992 machine_mode mode
= mode_for_size (leni
, MODE_INT
, 1);
1994 && (align
>= leni
|| !SLOW_UNALIGNED_ACCESS (mode
, align
)))
1996 location_t loc
= gimple_location (stmt2
);
1998 type
= build_nonstandard_integer_type (leni
, 1);
1999 gcc_assert (GET_MODE_BITSIZE (TYPE_MODE (type
)) == leni
);
2000 tree ptrtype
= build_pointer_type_for_mode (char_type_node
,
2002 off
= build_int_cst (ptrtype
, 0);
2003 arg1
= build2_loc (loc
, MEM_REF
, type
, arg1
, off
);
2004 arg2
= build2_loc (loc
, MEM_REF
, type
, arg2
, off
);
2005 tree tem1
= fold_const_aggregate_ref (arg1
);
2008 tree tem2
= fold_const_aggregate_ref (arg2
);
2011 res
= fold_convert_loc (loc
, TREE_TYPE (res
),
2012 fold_build2_loc (loc
, NE_EXPR
,
2015 gimplify_and_update_call_from_tree (gsi
, res
);
2020 gimple_call_set_fndecl (stmt2
, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ
));
2024 /* Handle a POINTER_PLUS_EXPR statement.
2025 For p = "abcd" + 2; compute associated length, or if
2026 p = q + off is pointing to a '\0' character of a string, call
2027 zero_length_string on it. */
2030 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
2032 gimple
*stmt
= gsi_stmt (*gsi
);
2033 tree lhs
= gimple_assign_lhs (stmt
), off
;
2034 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
2042 tree off
= gimple_assign_rhs2 (stmt
);
2043 if (tree_fits_uhwi_p (off
)
2044 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
2045 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
2046 = ~(~idx
- (int) tree_to_uhwi (off
));
2050 si
= get_strinfo (idx
);
2051 if (si
== NULL
|| si
->length
== NULL_TREE
)
2054 off
= gimple_assign_rhs2 (stmt
);
2056 if (operand_equal_p (si
->length
, off
, 0))
2057 zsi
= zero_length_string (lhs
, si
);
2058 else if (TREE_CODE (off
) == SSA_NAME
)
2060 gimple
*def_stmt
= SSA_NAME_DEF_STMT (off
);
2061 if (gimple_assign_single_p (def_stmt
)
2062 && operand_equal_p (si
->length
, gimple_assign_rhs1 (def_stmt
), 0))
2063 zsi
= zero_length_string (lhs
, si
);
2066 && si
->endptr
!= NULL_TREE
2067 && si
->endptr
!= lhs
2068 && TREE_CODE (si
->endptr
) == SSA_NAME
)
2070 enum tree_code rhs_code
2071 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
2072 ? SSA_NAME
: NOP_EXPR
;
2073 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
);
2074 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2079 /* Handle a single character store. */
2082 handle_char_store (gimple_stmt_iterator
*gsi
)
2086 gimple
*stmt
= gsi_stmt (*gsi
);
2087 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
2089 if (TREE_CODE (lhs
) == MEM_REF
2090 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
2092 if (integer_zerop (TREE_OPERAND (lhs
, 1)))
2094 ssaname
= TREE_OPERAND (lhs
, 0);
2095 idx
= get_stridx (ssaname
);
2099 idx
= get_addr_stridx (lhs
, NULL_TREE
);
2103 si
= get_strinfo (idx
);
2104 if (si
!= NULL
&& si
->length
!= NULL_TREE
&& integer_zerop (si
->length
))
2106 if (initializer_zerop (gimple_assign_rhs1 (stmt
)))
2108 /* When storing '\0', the store can be removed
2109 if we know it has been stored in the current function. */
2110 if (!stmt_could_throw_p (stmt
) && si
->writable
)
2112 unlink_stmt_vdef (stmt
);
2113 release_defs (stmt
);
2114 gsi_remove (gsi
, true);
2119 si
->writable
= true;
2125 /* Otherwise this statement overwrites the '\0' with
2126 something, if the previous stmt was a memcpy,
2127 its length may be decreased. */
2128 adjust_last_stmt (si
, stmt
, false);
2130 else if (si
!= NULL
&& integer_zerop (gimple_assign_rhs1 (stmt
)))
2132 si
= unshare_strinfo (si
);
2133 si
->length
= build_int_cst (size_type_node
, 0);
2139 si
->writable
= true;
2140 if (ssaname
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
2141 si
->endptr
= ssaname
;
2142 si
->dont_invalidate
= true;
2144 /* If si->length is non-zero constant, we aren't overwriting '\0',
2145 and if we aren't storing '\0', we know that the length of the
2146 string and any other zero terminated string in memory remains
2147 the same. In that case we move to the next gimple statement and
2148 return to signal the caller that it shouldn't invalidate anything.
2150 This is benefical for cases like:
2155 strcpy (p, "foobar");
2156 size_t len = strlen (p); // This can be optimized into 6
2157 size_t len2 = strlen (q); // This has to be computed
2159 size_t len3 = strlen (p); // This can be optimized into 6
2160 size_t len4 = strlen (q); // This can be optimized into len2
2161 bar (len, len2, len3, len4);
2164 else if (si
!= NULL
&& si
->length
!= NULL_TREE
2165 && TREE_CODE (si
->length
) == INTEGER_CST
2166 && integer_nonzerop (gimple_assign_rhs1 (stmt
)))
2172 else if (idx
== 0 && initializer_zerop (gimple_assign_rhs1 (stmt
)))
2176 si
= zero_length_string (ssaname
, NULL
);
2178 si
->dont_invalidate
= true;
2182 int idx
= new_addr_stridx (lhs
);
2185 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
2186 build_int_cst (size_type_node
, 0));
2187 set_strinfo (idx
, si
);
2188 si
->dont_invalidate
= true;
2192 si
->writable
= true;
2195 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == STRING_CST
2196 && ssaname
== NULL_TREE
2197 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
2199 size_t l
= strlen (TREE_STRING_POINTER (gimple_assign_rhs1 (stmt
)));
2200 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
2201 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> l
)
2203 int idx
= new_addr_stridx (lhs
);
2206 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
2207 build_int_cst (size_type_node
, l
));
2208 set_strinfo (idx
, si
);
2209 si
->dont_invalidate
= true;
2214 if (si
!= NULL
&& initializer_zerop (gimple_assign_rhs1 (stmt
)))
2216 /* Allow adjust_last_stmt to remove it if the stored '\0'
2217 is immediately overwritten. */
2218 laststmt
.stmt
= stmt
;
2219 laststmt
.len
= build_int_cst (size_type_node
, 1);
2220 laststmt
.stridx
= si
->idx
;
2225 /* Try to fold strstr (s, t) eq/ne s to memcmp (s, t, strlen (t)) eq/ne 0. */
2228 fold_strstr_to_memcmp (tree rhs1
, tree rhs2
, gimple
*stmt
)
2230 if (TREE_CODE (rhs1
) != SSA_NAME
2231 || TREE_CODE (rhs2
) != SSA_NAME
)
2234 gimple
*call_stmt
= NULL
;
2235 for (int pass
= 0; pass
< 2; pass
++)
2237 gimple
*g
= SSA_NAME_DEF_STMT (rhs1
);
2238 if (gimple_call_builtin_p (g
, BUILT_IN_STRSTR
)
2239 && has_single_use (rhs1
)
2240 && gimple_call_arg (g
, 0) == rhs2
)
2245 std::swap (rhs1
, rhs2
);
2250 tree arg0
= gimple_call_arg (call_stmt
, 0);
2254 tree arg1
= gimple_call_arg (call_stmt
, 1);
2255 tree arg1_len
= NULL_TREE
;
2256 int idx
= get_stridx (arg1
);
2261 arg1_len
= build_int_cst (size_type_node
, ~idx
);
2264 strinfo
*si
= get_strinfo (idx
);
2266 arg1_len
= get_string_length (si
);
2270 if (arg1_len
!= NULL_TREE
)
2272 gimple_stmt_iterator gsi
= gsi_for_stmt (call_stmt
);
2273 tree memcmp_decl
= builtin_decl_explicit (BUILT_IN_MEMCMP
);
2274 gcall
*memcmp_call
= gimple_build_call (memcmp_decl
, 3,
2275 arg0
, arg1
, arg1_len
);
2276 tree memcmp_lhs
= make_ssa_name (integer_type_node
);
2277 gimple_set_vuse (memcmp_call
, gimple_vuse (call_stmt
));
2278 gimple_call_set_lhs (memcmp_call
, memcmp_lhs
);
2279 gsi_remove (&gsi
, true);
2280 gsi_insert_before (&gsi
, memcmp_call
, GSI_SAME_STMT
);
2281 tree zero
= build_zero_cst (TREE_TYPE (memcmp_lhs
));
2283 if (is_gimple_assign (stmt
))
2285 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
2287 tree cond
= gimple_assign_rhs1 (stmt
);
2288 TREE_OPERAND (cond
, 0) = memcmp_lhs
;
2289 TREE_OPERAND (cond
, 1) = zero
;
2293 gimple_assign_set_rhs1 (stmt
, memcmp_lhs
);
2294 gimple_assign_set_rhs2 (stmt
, zero
);
2299 gcond
*cond
= as_a
<gcond
*> (stmt
);
2300 gimple_cond_set_lhs (cond
, memcmp_lhs
);
2301 gimple_cond_set_rhs (cond
, zero
);
2309 /* Attempt to optimize a single statement at *GSI using string length
2313 strlen_optimize_stmt (gimple_stmt_iterator
*gsi
)
2315 gimple
*stmt
= gsi_stmt (*gsi
);
2317 if (is_gimple_call (stmt
))
2319 tree callee
= gimple_call_fndecl (stmt
);
2320 if (valid_builtin_call (stmt
))
2321 switch (DECL_FUNCTION_CODE (callee
))
2323 case BUILT_IN_STRLEN
:
2324 case BUILT_IN_STRLEN_CHKP
:
2325 handle_builtin_strlen (gsi
);
2327 case BUILT_IN_STRCHR
:
2328 case BUILT_IN_STRCHR_CHKP
:
2329 handle_builtin_strchr (gsi
);
2331 case BUILT_IN_STRCPY
:
2332 case BUILT_IN_STRCPY_CHK
:
2333 case BUILT_IN_STPCPY
:
2334 case BUILT_IN_STPCPY_CHK
:
2335 case BUILT_IN_STRCPY_CHKP
:
2336 case BUILT_IN_STRCPY_CHK_CHKP
:
2337 case BUILT_IN_STPCPY_CHKP
:
2338 case BUILT_IN_STPCPY_CHK_CHKP
:
2339 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
2341 case BUILT_IN_MEMCPY
:
2342 case BUILT_IN_MEMCPY_CHK
:
2343 case BUILT_IN_MEMPCPY
:
2344 case BUILT_IN_MEMPCPY_CHK
:
2345 case BUILT_IN_MEMCPY_CHKP
:
2346 case BUILT_IN_MEMCPY_CHK_CHKP
:
2347 case BUILT_IN_MEMPCPY_CHKP
:
2348 case BUILT_IN_MEMPCPY_CHK_CHKP
:
2349 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
2351 case BUILT_IN_STRCAT
:
2352 case BUILT_IN_STRCAT_CHK
:
2353 case BUILT_IN_STRCAT_CHKP
:
2354 case BUILT_IN_STRCAT_CHK_CHKP
:
2355 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
2357 case BUILT_IN_MALLOC
:
2358 case BUILT_IN_CALLOC
:
2359 handle_builtin_malloc (DECL_FUNCTION_CODE (callee
), gsi
);
2361 case BUILT_IN_MEMSET
:
2362 if (!handle_builtin_memset (gsi
))
2365 case BUILT_IN_MEMCMP
:
2366 if (!handle_builtin_memcmp (gsi
))
2373 else if (is_gimple_assign (stmt
) && !gimple_clobber_p (stmt
))
2375 tree lhs
= gimple_assign_lhs (stmt
);
2377 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
2379 if (gimple_assign_single_p (stmt
)
2380 || (gimple_assign_cast_p (stmt
)
2381 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
2383 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
2384 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
2386 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
2387 handle_pointer_plus (gsi
);
2389 else if (TREE_CODE (lhs
) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
2391 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2392 if (code
== COND_EXPR
)
2394 tree cond
= gimple_assign_rhs1 (stmt
);
2395 enum tree_code cond_code
= TREE_CODE (cond
);
2397 if (cond_code
== EQ_EXPR
|| cond_code
== NE_EXPR
)
2398 fold_strstr_to_memcmp (TREE_OPERAND (cond
, 0),
2399 TREE_OPERAND (cond
, 1), stmt
);
2401 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
2402 fold_strstr_to_memcmp (gimple_assign_rhs1 (stmt
),
2403 gimple_assign_rhs2 (stmt
), stmt
);
2405 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
2407 tree type
= TREE_TYPE (lhs
);
2408 if (TREE_CODE (type
) == ARRAY_TYPE
)
2409 type
= TREE_TYPE (type
);
2410 if (TREE_CODE (type
) == INTEGER_TYPE
2411 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
2412 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
2414 if (! handle_char_store (gsi
))
2419 else if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
2421 enum tree_code code
= gimple_cond_code (cond
);
2422 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
2423 fold_strstr_to_memcmp (gimple_cond_lhs (stmt
),
2424 gimple_cond_rhs (stmt
), stmt
);
2427 if (gimple_vdef (stmt
))
2428 maybe_invalidate (stmt
);
2432 /* Recursively call maybe_invalidate on stmts that might be executed
2433 in between dombb and current bb and that contain a vdef. Stop when
2434 *count stmts are inspected, or if the whole strinfo vector has
2435 been invalidated. */
2438 do_invalidate (basic_block dombb
, gimple
*phi
, bitmap visited
, int *count
)
2440 unsigned int i
, n
= gimple_phi_num_args (phi
);
2442 for (i
= 0; i
< n
; i
++)
2444 tree vuse
= gimple_phi_arg_def (phi
, i
);
2445 gimple
*stmt
= SSA_NAME_DEF_STMT (vuse
);
2446 basic_block bb
= gimple_bb (stmt
);
2449 || !bitmap_set_bit (visited
, bb
->index
)
2450 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
2454 if (gimple_code (stmt
) == GIMPLE_PHI
)
2456 do_invalidate (dombb
, stmt
, visited
, count
);
2463 if (!maybe_invalidate (stmt
))
2468 vuse
= gimple_vuse (stmt
);
2469 stmt
= SSA_NAME_DEF_STMT (vuse
);
2470 if (gimple_bb (stmt
) != bb
)
2472 bb
= gimple_bb (stmt
);
2475 || !bitmap_set_bit (visited
, bb
->index
)
2476 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
2483 class strlen_dom_walker
: public dom_walker
2486 strlen_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
2488 virtual edge
before_dom_children (basic_block
);
2489 virtual void after_dom_children (basic_block
);
2492 /* Callback for walk_dominator_tree. Attempt to optimize various
2493 string ops by remembering string lengths pointed by pointer SSA_NAMEs. */
2496 strlen_dom_walker::before_dom_children (basic_block bb
)
2498 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
2501 stridx_to_strinfo
= NULL
;
2504 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) dombb
->aux
);
2505 if (stridx_to_strinfo
)
2507 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
2510 gphi
*phi
= gsi
.phi ();
2511 if (virtual_operand_p (gimple_phi_result (phi
)))
2513 bitmap visited
= BITMAP_ALLOC (NULL
);
2514 int count_vdef
= 100;
2515 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
2516 BITMAP_FREE (visited
);
2517 if (count_vdef
== 0)
2519 /* If there were too many vdefs in between immediate
2520 dominator and current bb, invalidate everything.
2521 If stridx_to_strinfo has been unshared, we need
2522 to free it, otherwise just set it to NULL. */
2523 if (!strinfo_shared ())
2529 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
2533 (*stridx_to_strinfo
)[i
] = NULL
;
2537 stridx_to_strinfo
= NULL
;
2545 /* If all PHI arguments have the same string index, the PHI result
2547 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
2550 gphi
*phi
= gsi
.phi ();
2551 tree result
= gimple_phi_result (phi
);
2552 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
2554 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
2557 unsigned int i
, n
= gimple_phi_num_args (phi
);
2558 for (i
= 1; i
< n
; i
++)
2559 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
2562 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
2567 /* Attempt to optimize individual statements. */
2568 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2569 if (strlen_optimize_stmt (&gsi
))
2572 bb
->aux
= stridx_to_strinfo
;
2573 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
2574 (*stridx_to_strinfo
)[0] = (strinfo
*) bb
;
2578 /* Callback for walk_dominator_tree. Free strinfo vector if it is
2579 owned by the current bb, clear bb->aux. */
2582 strlen_dom_walker::after_dom_children (basic_block bb
)
2586 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) bb
->aux
);
2587 if (vec_safe_length (stridx_to_strinfo
)
2588 && (*stridx_to_strinfo
)[0] == (strinfo
*) bb
)
2593 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
2595 vec_free (stridx_to_strinfo
);
2601 /* Main entry point. */
2605 const pass_data pass_data_strlen
=
2607 GIMPLE_PASS
, /* type */
2608 "strlen", /* name */
2609 OPTGROUP_NONE
, /* optinfo_flags */
2610 TV_TREE_STRLEN
, /* tv_id */
2611 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2612 0, /* properties_provided */
2613 0, /* properties_destroyed */
2614 0, /* todo_flags_start */
2615 0, /* todo_flags_finish */
2618 class pass_strlen
: public gimple_opt_pass
2621 pass_strlen (gcc::context
*ctxt
)
2622 : gimple_opt_pass (pass_data_strlen
, ctxt
)
2625 /* opt_pass methods: */
2626 virtual bool gate (function
*) { return flag_optimize_strlen
!= 0; }
2627 virtual unsigned int execute (function
*);
2629 }; // class pass_strlen
2632 pass_strlen::execute (function
*fun
)
2634 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
2637 calculate_dominance_info (CDI_DOMINATORS
);
2639 /* String length optimization is implemented as a walk of the dominator
2640 tree and a forward walk of statements within each block. */
2641 strlen_dom_walker (CDI_DOMINATORS
).walk (fun
->cfg
->x_entry_block_ptr
);
2643 ssa_ver_to_stridx
.release ();
2644 strinfo_pool
.release ();
2645 if (decl_to_stridxlist_htab
)
2647 obstack_free (&stridx_obstack
, NULL
);
2648 delete decl_to_stridxlist_htab
;
2649 decl_to_stridxlist_htab
= NULL
;
2651 laststmt
.stmt
= NULL
;
2652 laststmt
.len
= NULL_TREE
;
2653 laststmt
.stridx
= 0;
2661 make_pass_strlen (gcc::context
*ctxt
)
2663 return new pass_strlen (ctxt
);