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
)
165 struct stridxlist
*list
;
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
)
189 /* Return string index for EXP. */
192 get_stridx (tree exp
)
196 if (TREE_CODE (exp
) == SSA_NAME
)
198 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)])
199 return ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)];
202 HOST_WIDE_INT off
= 0;
203 for (i
= 0; i
< 5; i
++)
205 gimple
*def_stmt
= SSA_NAME_DEF_STMT (e
);
206 if (!is_gimple_assign (def_stmt
)
207 || gimple_assign_rhs_code (def_stmt
) != POINTER_PLUS_EXPR
)
209 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
210 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
211 if (TREE_CODE (rhs1
) != SSA_NAME
212 || !tree_fits_shwi_p (rhs2
))
214 HOST_WIDE_INT this_off
= tree_to_shwi (rhs2
);
217 off
= (unsigned HOST_WIDE_INT
) off
+ this_off
;
220 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)])
223 = get_strinfo (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)]);
226 && TREE_CODE (si
->length
) == INTEGER_CST
227 && compare_tree_int (si
->length
, off
) != -1)
228 return get_stridx_plus_constant (si
, off
, exp
);
235 if (TREE_CODE (exp
) == ADDR_EXPR
)
237 int idx
= get_addr_stridx (TREE_OPERAND (exp
, 0));
242 s
= string_constant (exp
, &o
);
244 && (o
== NULL_TREE
|| tree_fits_shwi_p (o
))
245 && TREE_STRING_LENGTH (s
) > 0)
247 HOST_WIDE_INT offset
= o
? tree_to_shwi (o
) : 0;
248 const char *p
= TREE_STRING_POINTER (s
);
249 int max
= TREE_STRING_LENGTH (s
) - 1;
251 if (p
[max
] == '\0' && offset
>= 0 && offset
<= max
)
252 return ~(int) strlen (p
+ offset
);
257 /* Return true if strinfo vector is shared with the immediate dominator. */
260 strinfo_shared (void)
262 return vec_safe_length (stridx_to_strinfo
)
263 && (*stridx_to_strinfo
)[0] != NULL
;
266 /* Unshare strinfo vector that is shared with the immediate dominator. */
269 unshare_strinfo_vec (void)
274 gcc_assert (strinfo_shared ());
275 stridx_to_strinfo
= vec_safe_copy (stridx_to_strinfo
);
276 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
279 (*stridx_to_strinfo
)[0] = NULL
;
282 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
283 Return a pointer to the location where the string index can
284 be stored (if 0) or is stored, or NULL if this can't be tracked. */
287 addr_stridxptr (tree exp
)
291 tree base
= get_addr_base_and_unit_offset (exp
, &off
);
292 if (base
== NULL_TREE
|| !DECL_P (base
))
295 if (!decl_to_stridxlist_htab
)
297 decl_to_stridxlist_htab
298 = new hash_map
<tree_decl_hash
, stridxlist
> (64);
299 gcc_obstack_init (&stridx_obstack
);
303 stridxlist
*list
= &decl_to_stridxlist_htab
->get_or_insert (base
, &existed
);
307 for (i
= 0; i
< 16; i
++)
309 if (list
->offset
== off
)
311 if (list
->next
== NULL
)
316 list
->next
= XOBNEW (&stridx_obstack
, struct stridxlist
);
326 /* Create a new string index, or return 0 if reached limit. */
329 new_stridx (tree exp
)
332 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
334 if (TREE_CODE (exp
) == SSA_NAME
)
336 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
339 ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)] = idx
;
342 if (TREE_CODE (exp
) == ADDR_EXPR
)
344 int *pidx
= addr_stridxptr (TREE_OPERAND (exp
, 0));
347 gcc_assert (*pidx
== 0);
348 *pidx
= max_stridx
++;
355 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
358 new_addr_stridx (tree exp
)
361 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
363 pidx
= addr_stridxptr (exp
);
366 gcc_assert (*pidx
== 0);
367 *pidx
= max_stridx
++;
373 /* Create a new strinfo. */
376 new_strinfo (tree ptr
, int idx
, tree length
)
378 strinfo
*si
= strinfo_pool
.allocate ();
382 si
->endptr
= NULL_TREE
;
388 si
->writable
= false;
389 si
->dont_invalidate
= false;
393 /* Decrease strinfo refcount and free it if not referenced anymore. */
396 free_strinfo (strinfo
*si
)
398 if (si
&& --si
->refcount
== 0)
399 strinfo_pool
.remove (si
);
402 /* Set strinfo in the vector entry IDX to SI. */
405 set_strinfo (int idx
, strinfo
*si
)
407 if (vec_safe_length (stridx_to_strinfo
) && (*stridx_to_strinfo
)[0])
408 unshare_strinfo_vec ();
409 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
410 vec_safe_grow_cleared (stridx_to_strinfo
, idx
+ 1);
411 (*stridx_to_strinfo
)[idx
] = si
;
414 /* Return string length, or NULL if it can't be computed. */
417 get_string_length (strinfo
*si
)
424 gimple
*stmt
= si
->stmt
, *lenstmt
;
425 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
426 tree callee
, lhs
, fn
, tem
;
428 gimple_stmt_iterator gsi
;
430 gcc_assert (is_gimple_call (stmt
));
431 callee
= gimple_call_fndecl (stmt
);
432 gcc_assert (callee
&& DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
);
433 lhs
= gimple_call_lhs (stmt
);
434 /* unshare_strinfo is intentionally not called here. The (delayed)
435 transformation of strcpy or strcat into stpcpy is done at the place
436 of the former strcpy/strcat call and so can affect all the strinfos
437 with the same stmt. If they were unshared before and transformation
438 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
439 just compute the right length. */
440 switch (DECL_FUNCTION_CODE (callee
))
442 case BUILT_IN_STRCAT
:
443 case BUILT_IN_STRCAT_CHK
:
444 case BUILT_IN_STRCAT_CHKP
:
445 case BUILT_IN_STRCAT_CHK_CHKP
:
446 gsi
= gsi_for_stmt (stmt
);
447 fn
= builtin_decl_implicit (BUILT_IN_STRLEN
);
448 gcc_assert (lhs
== NULL_TREE
);
449 tem
= unshare_expr (gimple_call_arg (stmt
, 0));
452 lenstmt
= gimple_build_call (chkp_maybe_create_clone (fn
)->decl
,
453 2, tem
, gimple_call_arg (stmt
, 1));
454 gimple_call_set_with_bounds (lenstmt
, true);
457 lenstmt
= gimple_build_call (fn
, 1, tem
);
458 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), lenstmt
);
459 gimple_call_set_lhs (lenstmt
, lhs
);
460 gimple_set_vuse (lenstmt
, gimple_vuse (stmt
));
461 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
462 tem
= gimple_call_arg (stmt
, 0);
463 if (!ptrofftype_p (TREE_TYPE (lhs
)))
465 lhs
= convert_to_ptrofftype (lhs
);
466 lhs
= force_gimple_operand_gsi (&gsi
, lhs
, true, NULL_TREE
,
467 true, GSI_SAME_STMT
);
469 lenstmt
= gimple_build_assign
470 (make_ssa_name (TREE_TYPE (gimple_call_arg (stmt
, 0))),
471 POINTER_PLUS_EXPR
,tem
, lhs
);
472 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
473 gimple_call_set_arg (stmt
, 0, gimple_assign_lhs (lenstmt
));
476 case BUILT_IN_STRCPY
:
477 case BUILT_IN_STRCPY_CHK
:
478 case BUILT_IN_STRCPY_CHKP
:
479 case BUILT_IN_STRCPY_CHK_CHKP
:
480 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY
));
481 if (gimple_call_num_args (stmt
) == (with_bounds
? 4 : 2))
482 fn
= builtin_decl_implicit (BUILT_IN_STPCPY
);
484 fn
= builtin_decl_explicit (BUILT_IN_STPCPY_CHK
);
486 fn
= chkp_maybe_create_clone (fn
)->decl
;
487 gcc_assert (lhs
== NULL_TREE
);
488 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
490 fprintf (dump_file
, "Optimizing: ");
491 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
493 gimple_call_set_fndecl (stmt
, fn
);
494 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), stmt
);
495 gimple_call_set_lhs (stmt
, lhs
);
497 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
499 fprintf (dump_file
, "into: ");
500 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
503 case BUILT_IN_STPCPY
:
504 case BUILT_IN_STPCPY_CHK
:
505 case BUILT_IN_STPCPY_CHKP
:
506 case BUILT_IN_STPCPY_CHK_CHKP
:
507 gcc_assert (lhs
!= NULL_TREE
);
508 loc
= gimple_location (stmt
);
511 lhs
= fold_convert_loc (loc
, size_type_node
, lhs
);
512 si
->length
= fold_convert_loc (loc
, size_type_node
, si
->ptr
);
513 si
->length
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
516 case BUILT_IN_MALLOC
:
518 /* BUILT_IN_CALLOC always has si->length set. */
528 /* Invalidate string length information for strings whose length
529 might change due to stores in stmt. */
532 maybe_invalidate (gimple
*stmt
)
536 bool nonempty
= false;
538 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
541 if (!si
->dont_invalidate
)
544 /* Do not use si->length. */
545 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, NULL_TREE
);
546 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
548 set_strinfo (i
, NULL
);
553 si
->dont_invalidate
= false;
559 /* Unshare strinfo record SI, if it has refcount > 1 or
560 if stridx_to_strinfo vector is shared with some other
564 unshare_strinfo (strinfo
*si
)
568 if (si
->refcount
== 1 && !strinfo_shared ())
571 nsi
= new_strinfo (si
->ptr
, si
->idx
, si
->length
);
572 nsi
->stmt
= si
->stmt
;
573 nsi
->endptr
= si
->endptr
;
574 nsi
->first
= si
->first
;
575 nsi
->prev
= si
->prev
;
576 nsi
->next
= si
->next
;
577 nsi
->writable
= si
->writable
;
578 set_strinfo (si
->idx
, nsi
);
583 /* Return first strinfo in the related strinfo chain
584 if all strinfos in between belong to the chain, otherwise
588 verify_related_strinfos (strinfo
*origsi
)
590 strinfo
*si
= origsi
, *psi
;
592 if (origsi
->first
== 0)
594 for (; si
->prev
; si
= psi
)
596 if (si
->first
!= origsi
->first
)
598 psi
= get_strinfo (si
->prev
);
601 if (psi
->next
!= si
->idx
)
604 if (si
->idx
!= si
->first
)
609 /* Attempt to create a new strinfo for BASESI + OFF, or find existing
610 strinfo if there is any. Return it's idx, or 0 if no strinfo has
614 get_stridx_plus_constant (strinfo
*basesi
, HOST_WIDE_INT off
, tree ptr
)
616 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
);
618 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
621 if (basesi
->length
== NULL_TREE
622 || TREE_CODE (basesi
->length
) != INTEGER_CST
623 || compare_tree_int (basesi
->length
, off
) == -1
624 || !tree_fits_shwi_p (basesi
->length
))
627 HOST_WIDE_INT len
= tree_to_shwi (basesi
->length
) - off
;
628 strinfo
*si
= basesi
, *chainsi
;
629 if (si
->first
|| si
->prev
|| si
->next
)
630 si
= verify_related_strinfos (basesi
);
632 || si
->length
== NULL_TREE
633 || TREE_CODE (si
->length
) != INTEGER_CST
)
636 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
637 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
639 gcc_checking_assert (compare_tree_int (si
->length
, off
) != -1);
640 for (chainsi
= si
; chainsi
->next
; chainsi
= si
)
642 si
= get_strinfo (chainsi
->next
);
644 || si
->first
!= chainsi
->first
645 || si
->prev
!= chainsi
->idx
646 || si
->length
== NULL_TREE
647 || TREE_CODE (si
->length
) != INTEGER_CST
)
649 int r
= compare_tree_int (si
->length
, len
);
654 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = si
->idx
;
661 int idx
= new_stridx (ptr
);
664 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, len
));
665 set_strinfo (idx
, si
);
668 strinfo
*nextsi
= unshare_strinfo (get_strinfo (chainsi
->next
));
669 si
->next
= nextsi
->idx
;
672 chainsi
= unshare_strinfo (chainsi
);
673 if (chainsi
->first
== 0)
674 chainsi
->first
= chainsi
->idx
;
676 if (chainsi
->endptr
== NULL_TREE
&& len
== 0)
677 chainsi
->endptr
= ptr
;
678 si
->endptr
= chainsi
->endptr
;
679 si
->prev
= chainsi
->idx
;
680 si
->first
= chainsi
->first
;
681 si
->writable
= chainsi
->writable
;
685 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
686 to a zero-length string and if possible chain it to a related strinfo
687 chain whose part is or might be CHAINSI. */
690 zero_length_string (tree ptr
, strinfo
*chainsi
)
694 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
695 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
696 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
697 && ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] == 0);
699 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
703 si
= verify_related_strinfos (chainsi
);
707 for (; chainsi
->next
; chainsi
= si
)
709 if (chainsi
->endptr
== NULL_TREE
)
711 chainsi
= unshare_strinfo (chainsi
);
712 chainsi
->endptr
= ptr
;
714 si
= get_strinfo (chainsi
->next
);
716 || si
->first
!= chainsi
->first
717 || si
->prev
!= chainsi
->idx
)
720 gcc_assert (chainsi
->length
|| chainsi
->stmt
);
721 if (chainsi
->endptr
== NULL_TREE
)
723 chainsi
= unshare_strinfo (chainsi
);
724 chainsi
->endptr
= ptr
;
726 if (chainsi
->length
&& integer_zerop (chainsi
->length
))
730 chainsi
= unshare_strinfo (chainsi
);
733 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = chainsi
->idx
;
737 else if (chainsi
->first
|| chainsi
->prev
|| chainsi
->next
)
739 chainsi
= unshare_strinfo (chainsi
);
745 idx
= new_stridx (ptr
);
748 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, 0));
749 set_strinfo (idx
, si
);
753 chainsi
= unshare_strinfo (chainsi
);
754 if (chainsi
->first
== 0)
755 chainsi
->first
= chainsi
->idx
;
757 if (chainsi
->endptr
== NULL_TREE
)
758 chainsi
->endptr
= ptr
;
759 si
->prev
= chainsi
->idx
;
760 si
->first
= chainsi
->first
;
761 si
->writable
= chainsi
->writable
;
766 /* For strinfo ORIGSI whose length has been just updated
767 update also related strinfo lengths (add ADJ to each,
768 but don't adjust ORIGSI). */
771 adjust_related_strinfos (location_t loc
, strinfo
*origsi
, tree adj
)
773 strinfo
*si
= verify_related_strinfos (origsi
);
786 si
= unshare_strinfo (si
);
789 tem
= fold_convert_loc (loc
, TREE_TYPE (si
->length
), adj
);
790 si
->length
= fold_build2_loc (loc
, PLUS_EXPR
,
791 TREE_TYPE (si
->length
), si
->length
,
794 else if (si
->stmt
!= NULL
)
795 /* Delayed length computation is unaffected. */
800 si
->endptr
= NULL_TREE
;
801 si
->dont_invalidate
= true;
805 nsi
= get_strinfo (si
->next
);
807 || nsi
->first
!= si
->first
808 || nsi
->prev
!= si
->idx
)
814 /* Find if there are other SSA_NAME pointers equal to PTR
815 for which we don't track their string lengths yet. If so, use
819 find_equal_ptrs (tree ptr
, int idx
)
821 if (TREE_CODE (ptr
) != SSA_NAME
)
825 gimple
*stmt
= SSA_NAME_DEF_STMT (ptr
);
826 if (!is_gimple_assign (stmt
))
828 ptr
= gimple_assign_rhs1 (stmt
);
829 switch (gimple_assign_rhs_code (stmt
))
834 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)))
836 if (TREE_CODE (ptr
) == SSA_NAME
)
838 if (TREE_CODE (ptr
) != ADDR_EXPR
)
843 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
844 if (pidx
!= NULL
&& *pidx
== 0)
852 /* We might find an endptr created in this pass. Grow the
853 vector in that case. */
854 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
855 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
857 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] != 0)
859 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = idx
;
863 /* Return true if STMT is a call to a builtin function with the right
864 arguments and attributes that should be considered for optimization
868 valid_builtin_call (gimple
*stmt
)
870 if (!gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
873 tree callee
= gimple_call_fndecl (stmt
);
874 switch (DECL_FUNCTION_CODE (callee
))
876 case BUILT_IN_MEMCMP
:
877 case BUILT_IN_MEMCMP_EQ
:
878 case BUILT_IN_STRCHR
:
879 case BUILT_IN_STRCHR_CHKP
:
880 case BUILT_IN_STRLEN
:
881 case BUILT_IN_STRLEN_CHKP
:
882 /* The above functions should be pure. Punt if they aren't. */
883 if (gimple_vdef (stmt
) || gimple_vuse (stmt
) == NULL_TREE
)
887 case BUILT_IN_CALLOC
:
888 case BUILT_IN_MALLOC
:
889 case BUILT_IN_MEMCPY
:
890 case BUILT_IN_MEMCPY_CHK
:
891 case BUILT_IN_MEMCPY_CHKP
:
892 case BUILT_IN_MEMCPY_CHK_CHKP
:
893 case BUILT_IN_MEMPCPY
:
894 case BUILT_IN_MEMPCPY_CHK
:
895 case BUILT_IN_MEMPCPY_CHKP
:
896 case BUILT_IN_MEMPCPY_CHK_CHKP
:
897 case BUILT_IN_MEMSET
:
898 case BUILT_IN_STPCPY
:
899 case BUILT_IN_STPCPY_CHK
:
900 case BUILT_IN_STPCPY_CHKP
:
901 case BUILT_IN_STPCPY_CHK_CHKP
:
902 case BUILT_IN_STRCAT
:
903 case BUILT_IN_STRCAT_CHK
:
904 case BUILT_IN_STRCAT_CHKP
:
905 case BUILT_IN_STRCAT_CHK_CHKP
:
906 case BUILT_IN_STRCPY
:
907 case BUILT_IN_STRCPY_CHK
:
908 case BUILT_IN_STRCPY_CHKP
:
909 case BUILT_IN_STRCPY_CHK_CHKP
:
910 /* The above functions should be neither const nor pure. Punt if they
912 if (gimple_vdef (stmt
) == NULL_TREE
|| gimple_vuse (stmt
) == NULL_TREE
)
923 /* If the last .MEM setter statement before STMT is
924 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
925 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
926 just memcpy (x, y, strlen (y)). SI must be the zero length
930 adjust_last_stmt (strinfo
*si
, gimple
*stmt
, bool is_strcat
)
932 tree vuse
, callee
, len
;
933 struct laststmt_struct last
= laststmt
;
934 strinfo
*lastsi
, *firstsi
;
935 unsigned len_arg_no
= 2;
937 laststmt
.stmt
= NULL
;
938 laststmt
.len
= NULL_TREE
;
941 if (last
.stmt
== NULL
)
944 vuse
= gimple_vuse (stmt
);
945 if (vuse
== NULL_TREE
946 || SSA_NAME_DEF_STMT (vuse
) != last
.stmt
947 || !has_single_use (vuse
))
950 gcc_assert (last
.stridx
> 0);
951 lastsi
= get_strinfo (last
.stridx
);
957 if (lastsi
->first
== 0 || lastsi
->first
!= si
->first
)
960 firstsi
= verify_related_strinfos (si
);
963 while (firstsi
!= lastsi
)
966 if (firstsi
->next
== 0)
968 nextsi
= get_strinfo (firstsi
->next
);
970 || nextsi
->prev
!= firstsi
->idx
971 || nextsi
->first
!= si
->first
)
979 if (si
->length
== NULL_TREE
|| !integer_zerop (si
->length
))
983 if (is_gimple_assign (last
.stmt
))
985 gimple_stmt_iterator gsi
;
987 if (!integer_zerop (gimple_assign_rhs1 (last
.stmt
)))
989 if (stmt_could_throw_p (last
.stmt
))
991 gsi
= gsi_for_stmt (last
.stmt
);
992 unlink_stmt_vdef (last
.stmt
);
993 release_defs (last
.stmt
);
994 gsi_remove (&gsi
, true);
998 if (!valid_builtin_call (last
.stmt
))
1001 callee
= gimple_call_fndecl (last
.stmt
);
1002 switch (DECL_FUNCTION_CODE (callee
))
1004 case BUILT_IN_MEMCPY
:
1005 case BUILT_IN_MEMCPY_CHK
:
1007 case BUILT_IN_MEMCPY_CHKP
:
1008 case BUILT_IN_MEMCPY_CHK_CHKP
:
1015 len
= gimple_call_arg (last
.stmt
, len_arg_no
);
1016 if (tree_fits_uhwi_p (len
))
1018 if (!tree_fits_uhwi_p (last
.len
)
1019 || integer_zerop (len
)
1020 || tree_to_uhwi (len
) != tree_to_uhwi (last
.len
) + 1)
1022 /* Don't adjust the length if it is divisible by 4, it is more efficient
1023 to store the extra '\0' in that case. */
1024 if ((tree_to_uhwi (len
) & 3) == 0)
1027 else if (TREE_CODE (len
) == SSA_NAME
)
1029 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1030 if (!is_gimple_assign (def_stmt
)
1031 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1032 || gimple_assign_rhs1 (def_stmt
) != last
.len
1033 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1039 gimple_call_set_arg (last
.stmt
, len_arg_no
, last
.len
);
1040 update_stmt (last
.stmt
);
1043 /* Handle a strlen call. If strlen of the argument is known, replace
1044 the strlen call with the known value, otherwise remember that strlen
1045 of the argument is stored in the lhs SSA_NAME. */
1048 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
1052 gimple
*stmt
= gsi_stmt (*gsi
);
1053 tree lhs
= gimple_call_lhs (stmt
);
1055 if (lhs
== NULL_TREE
)
1058 src
= gimple_call_arg (stmt
, 0);
1059 idx
= get_stridx (src
);
1066 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
1070 si
= get_strinfo (idx
);
1072 rhs
= get_string_length (si
);
1074 if (rhs
!= NULL_TREE
)
1076 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1078 fprintf (dump_file
, "Optimizing: ");
1079 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1081 rhs
= unshare_expr (rhs
);
1082 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
1083 rhs
= fold_convert_loc (gimple_location (stmt
),
1084 TREE_TYPE (lhs
), rhs
);
1085 if (!update_call_from_tree (gsi
, rhs
))
1086 gimplify_and_update_call_from_tree (gsi
, rhs
);
1087 stmt
= gsi_stmt (*gsi
);
1089 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1091 fprintf (dump_file
, "into: ");
1092 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1095 && TREE_CODE (si
->length
) != SSA_NAME
1096 && TREE_CODE (si
->length
) != INTEGER_CST
1097 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1099 si
= unshare_strinfo (si
);
1105 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1108 idx
= new_stridx (src
);
1109 else if (get_strinfo (idx
) != NULL
)
1113 strinfo
*si
= new_strinfo (src
, idx
, lhs
);
1114 set_strinfo (idx
, si
);
1115 find_equal_ptrs (src
, idx
);
1119 /* Handle a strchr call. If strlen of the first argument is known, replace
1120 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
1121 that lhs of the call is endptr and strlen of the argument is endptr - x. */
1124 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
1128 gimple
*stmt
= gsi_stmt (*gsi
);
1129 tree lhs
= gimple_call_lhs (stmt
);
1130 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1132 if (lhs
== NULL_TREE
)
1135 if (!integer_zerop (gimple_call_arg (stmt
, with_bounds
? 2 : 1)))
1138 src
= gimple_call_arg (stmt
, 0);
1139 idx
= get_stridx (src
);
1146 rhs
= build_int_cst (size_type_node
, ~idx
);
1150 si
= get_strinfo (idx
);
1152 rhs
= get_string_length (si
);
1154 if (rhs
!= NULL_TREE
)
1156 location_t loc
= gimple_location (stmt
);
1158 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1160 fprintf (dump_file
, "Optimizing: ");
1161 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1163 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
1165 rhs
= unshare_expr (si
->endptr
);
1166 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1168 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1172 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1173 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1174 TREE_TYPE (src
), src
, rhs
);
1175 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1177 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1179 if (!update_call_from_tree (gsi
, rhs
))
1180 gimplify_and_update_call_from_tree (gsi
, rhs
);
1181 stmt
= gsi_stmt (*gsi
);
1183 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1185 fprintf (dump_file
, "into: ");
1186 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1189 && si
->endptr
== NULL_TREE
1190 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1192 si
= unshare_strinfo (si
);
1195 zero_length_string (lhs
, si
);
1199 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1201 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1204 idx
= new_stridx (src
);
1205 else if (get_strinfo (idx
) != NULL
)
1207 zero_length_string (lhs
, NULL
);
1212 location_t loc
= gimple_location (stmt
);
1213 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1214 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1215 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1216 size_type_node
, lhsu
, srcu
);
1217 strinfo
*si
= new_strinfo (src
, idx
, length
);
1219 set_strinfo (idx
, si
);
1220 find_equal_ptrs (src
, idx
);
1221 zero_length_string (lhs
, si
);
1225 zero_length_string (lhs
, NULL
);
1228 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1229 If strlen of the second argument is known, strlen of the first argument
1230 is the same after this call. Furthermore, attempt to convert it to
1234 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1237 tree src
, dst
, srclen
, len
, lhs
, args
, type
, fn
, oldlen
;
1239 gimple
*stmt
= gsi_stmt (*gsi
);
1240 strinfo
*si
, *dsi
, *olddsi
, *zsi
;
1242 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1244 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1245 dst
= gimple_call_arg (stmt
, 0);
1246 lhs
= gimple_call_lhs (stmt
);
1247 idx
= get_stridx (src
);
1250 si
= get_strinfo (idx
);
1252 didx
= get_stridx (dst
);
1256 olddsi
= get_strinfo (didx
);
1261 adjust_last_stmt (olddsi
, stmt
, false);
1265 srclen
= get_string_length (si
);
1267 srclen
= build_int_cst (size_type_node
, ~idx
);
1269 loc
= gimple_location (stmt
);
1270 if (srclen
== NULL_TREE
)
1273 case BUILT_IN_STRCPY
:
1274 case BUILT_IN_STRCPY_CHK
:
1275 case BUILT_IN_STRCPY_CHKP
:
1276 case BUILT_IN_STRCPY_CHK_CHKP
:
1277 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1280 case BUILT_IN_STPCPY
:
1281 case BUILT_IN_STPCPY_CHK
:
1282 case BUILT_IN_STPCPY_CHKP
:
1283 case BUILT_IN_STPCPY_CHK_CHKP
:
1284 if (lhs
== NULL_TREE
)
1288 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1289 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1290 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1300 didx
= new_stridx (dst
);
1306 oldlen
= olddsi
->length
;
1307 dsi
= unshare_strinfo (olddsi
);
1308 dsi
->length
= srclen
;
1309 /* Break the chain, so adjust_related_strinfo on later pointers in
1310 the chain won't adjust this one anymore. */
1313 dsi
->endptr
= NULL_TREE
;
1317 dsi
= new_strinfo (dst
, didx
, srclen
);
1318 set_strinfo (didx
, dsi
);
1319 find_equal_ptrs (dst
, didx
);
1321 dsi
->writable
= true;
1322 dsi
->dont_invalidate
= true;
1324 if (dsi
->length
== NULL_TREE
)
1328 /* If string length of src is unknown, use delayed length
1329 computation. If string lenth of dst will be needed, it
1330 can be computed by transforming this strcpy call into
1331 stpcpy and subtracting dst from the return value. */
1333 /* Look for earlier strings whose length could be determined if
1334 this strcpy is turned into an stpcpy. */
1336 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1338 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1340 /* When setting a stmt for delayed length computation
1341 prevent all strinfos through dsi from being
1343 chainsi
= unshare_strinfo (chainsi
);
1344 chainsi
->stmt
= stmt
;
1345 chainsi
->length
= NULL_TREE
;
1346 chainsi
->endptr
= NULL_TREE
;
1347 chainsi
->dont_invalidate
= true;
1356 tree adj
= NULL_TREE
;
1357 if (oldlen
== NULL_TREE
)
1359 else if (integer_zerop (oldlen
))
1361 else if (TREE_CODE (oldlen
) == INTEGER_CST
1362 || TREE_CODE (srclen
) == INTEGER_CST
)
1363 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1364 TREE_TYPE (srclen
), srclen
,
1365 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1367 if (adj
!= NULL_TREE
)
1368 adjust_related_strinfos (loc
, dsi
, adj
);
1372 /* strcpy src may not overlap dst, so src doesn't need to be
1373 invalidated either. */
1375 si
->dont_invalidate
= true;
1381 case BUILT_IN_STRCPY
:
1382 case BUILT_IN_STRCPY_CHKP
:
1383 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1385 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1387 case BUILT_IN_STRCPY_CHK
:
1388 case BUILT_IN_STRCPY_CHK_CHKP
:
1389 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1391 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1393 case BUILT_IN_STPCPY
:
1394 case BUILT_IN_STPCPY_CHKP
:
1395 /* This would need adjustment of the lhs (subtract one),
1396 or detection that the trailing '\0' doesn't need to be
1397 written, if it will be immediately overwritten.
1398 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1402 zsi
= zero_length_string (lhs
, dsi
);
1405 case BUILT_IN_STPCPY_CHK
:
1406 case BUILT_IN_STPCPY_CHK_CHKP
:
1407 /* This would need adjustment of the lhs (subtract one),
1408 or detection that the trailing '\0' doesn't need to be
1409 written, if it will be immediately overwritten.
1410 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1414 zsi
= zero_length_string (lhs
, dsi
);
1421 zsi
->dont_invalidate
= true;
1423 if (fn
== NULL_TREE
)
1426 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1427 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1429 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1430 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1431 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1433 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1435 fprintf (dump_file
, "Optimizing: ");
1436 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1440 fn
= chkp_maybe_create_clone (fn
)->decl
;
1441 if (gimple_call_num_args (stmt
) == 4)
1442 success
= update_gimple_call (gsi
, fn
, 5, dst
,
1443 gimple_call_arg (stmt
, 1),
1445 gimple_call_arg (stmt
, 3),
1448 success
= update_gimple_call (gsi
, fn
, 6, dst
,
1449 gimple_call_arg (stmt
, 1),
1451 gimple_call_arg (stmt
, 3),
1453 gimple_call_arg (stmt
, 4));
1456 if (gimple_call_num_args (stmt
) == 2)
1457 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1459 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1460 gimple_call_arg (stmt
, 2));
1463 stmt
= gsi_stmt (*gsi
);
1464 gimple_call_set_with_bounds (stmt
, with_bounds
);
1466 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1468 fprintf (dump_file
, "into: ");
1469 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1471 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1472 laststmt
.stmt
= stmt
;
1473 laststmt
.len
= srclen
;
1474 laststmt
.stridx
= dsi
->idx
;
1476 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1477 fprintf (dump_file
, "not possible.\n");
1480 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1481 If strlen of the second argument is known and length of the third argument
1482 is that plus one, strlen of the first argument is the same after this
1486 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1489 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
1490 gimple
*stmt
= gsi_stmt (*gsi
);
1491 strinfo
*si
, *dsi
, *olddsi
;
1492 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1494 len
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
1495 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1496 dst
= gimple_call_arg (stmt
, 0);
1497 idx
= get_stridx (src
);
1501 didx
= get_stridx (dst
);
1504 olddsi
= get_strinfo (didx
);
1509 && tree_fits_uhwi_p (len
)
1510 && !integer_zerop (len
))
1511 adjust_last_stmt (olddsi
, stmt
, false);
1517 /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */
1518 si
= get_strinfo (idx
);
1519 if (si
== NULL
|| si
->length
== NULL_TREE
)
1521 if (TREE_CODE (len
) != SSA_NAME
)
1523 def_stmt
= SSA_NAME_DEF_STMT (len
);
1524 if (!is_gimple_assign (def_stmt
)
1525 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1526 || gimple_assign_rhs1 (def_stmt
) != si
->length
1527 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1533 /* Handle memcpy (x, "abcd", 5) or
1534 memcpy (x, "abc\0uvw", 7). */
1535 if (!tree_fits_uhwi_p (len
)
1536 || tree_to_uhwi (len
) <= (unsigned HOST_WIDE_INT
) ~idx
)
1540 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
1541 adjust_last_stmt (olddsi
, stmt
, false);
1545 didx
= new_stridx (dst
);
1550 newlen
= si
->length
;
1552 newlen
= build_int_cst (size_type_node
, ~idx
);
1556 dsi
= unshare_strinfo (olddsi
);
1557 oldlen
= olddsi
->length
;
1558 dsi
->length
= newlen
;
1559 /* Break the chain, so adjust_related_strinfo on later pointers in
1560 the chain won't adjust this one anymore. */
1563 dsi
->endptr
= NULL_TREE
;
1567 dsi
= new_strinfo (dst
, didx
, newlen
);
1568 set_strinfo (didx
, dsi
);
1569 find_equal_ptrs (dst
, didx
);
1571 dsi
->writable
= true;
1572 dsi
->dont_invalidate
= true;
1575 tree adj
= NULL_TREE
;
1576 location_t loc
= gimple_location (stmt
);
1577 if (oldlen
== NULL_TREE
)
1579 else if (integer_zerop (oldlen
))
1581 else if (TREE_CODE (oldlen
) == INTEGER_CST
1582 || TREE_CODE (dsi
->length
) == INTEGER_CST
)
1583 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1584 TREE_TYPE (dsi
->length
), dsi
->length
,
1585 fold_convert_loc (loc
, TREE_TYPE (dsi
->length
),
1587 if (adj
!= NULL_TREE
)
1588 adjust_related_strinfos (loc
, dsi
, adj
);
1592 /* memcpy src may not overlap dst, so src doesn't need to be
1593 invalidated either. */
1595 si
->dont_invalidate
= true;
1597 lhs
= gimple_call_lhs (stmt
);
1600 case BUILT_IN_MEMCPY
:
1601 case BUILT_IN_MEMCPY_CHK
:
1602 case BUILT_IN_MEMCPY_CHKP
:
1603 case BUILT_IN_MEMCPY_CHK_CHKP
:
1604 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1605 laststmt
.stmt
= stmt
;
1606 laststmt
.len
= dsi
->length
;
1607 laststmt
.stridx
= dsi
->idx
;
1609 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1611 case BUILT_IN_MEMPCPY
:
1612 case BUILT_IN_MEMPCPY_CHK
:
1613 case BUILT_IN_MEMPCPY_CHKP
:
1614 case BUILT_IN_MEMPCPY_CHK_CHKP
:
1621 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
1622 If strlen of the second argument is known, strlen of the first argument
1623 is increased by the length of the second argument. Furthermore, attempt
1624 to convert it to memcpy/strcpy if the length of the first argument
1628 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1631 tree src
, dst
, srclen
, dstlen
, len
, lhs
, args
, type
, fn
, objsz
, endptr
;
1633 gimple
*stmt
= gsi_stmt (*gsi
);
1636 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1638 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1639 dst
= gimple_call_arg (stmt
, 0);
1640 lhs
= gimple_call_lhs (stmt
);
1642 didx
= get_stridx (dst
);
1648 dsi
= get_strinfo (didx
);
1649 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
1651 /* strcat (p, q) can be transformed into
1652 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
1653 with length endptr - p if we need to compute the length
1654 later on. Don't do this transformation if we don't need
1656 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
1660 didx
= new_stridx (dst
);
1666 dsi
= new_strinfo (dst
, didx
, NULL_TREE
);
1667 set_strinfo (didx
, dsi
);
1668 find_equal_ptrs (dst
, didx
);
1672 dsi
= unshare_strinfo (dsi
);
1673 dsi
->length
= NULL_TREE
;
1675 dsi
->endptr
= NULL_TREE
;
1677 dsi
->writable
= true;
1679 dsi
->dont_invalidate
= true;
1686 idx
= get_stridx (src
);
1688 srclen
= build_int_cst (size_type_node
, ~idx
);
1691 si
= get_strinfo (idx
);
1693 srclen
= get_string_length (si
);
1696 loc
= gimple_location (stmt
);
1697 dstlen
= dsi
->length
;
1698 endptr
= dsi
->endptr
;
1700 dsi
= unshare_strinfo (dsi
);
1701 dsi
->endptr
= NULL_TREE
;
1703 dsi
->writable
= true;
1705 if (srclen
!= NULL_TREE
)
1707 dsi
->length
= fold_build2_loc (loc
, PLUS_EXPR
, TREE_TYPE (dsi
->length
),
1708 dsi
->length
, srclen
);
1709 adjust_related_strinfos (loc
, dsi
, srclen
);
1710 dsi
->dont_invalidate
= true;
1715 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1716 dsi
->dont_invalidate
= true;
1720 /* strcat src may not overlap dst, so src doesn't need to be
1721 invalidated either. */
1722 si
->dont_invalidate
= true;
1724 /* For now. Could remove the lhs from the call and add
1725 lhs = dst; afterwards. */
1733 case BUILT_IN_STRCAT
:
1734 case BUILT_IN_STRCAT_CHKP
:
1735 if (srclen
!= NULL_TREE
)
1736 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1738 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
1740 case BUILT_IN_STRCAT_CHK
:
1741 case BUILT_IN_STRCAT_CHK_CHKP
:
1742 if (srclen
!= NULL_TREE
)
1743 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1745 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
1746 objsz
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
1752 if (fn
== NULL_TREE
)
1756 if (srclen
!= NULL_TREE
)
1758 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1759 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1761 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1762 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
1763 build_int_cst (type
, 1));
1764 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1768 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
1770 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1771 TREE_TYPE (dst
), unshare_expr (dst
),
1772 fold_convert_loc (loc
, sizetype
,
1773 unshare_expr (dstlen
)));
1774 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
1776 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1778 fprintf (dump_file
, "Optimizing: ");
1779 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1783 fn
= chkp_maybe_create_clone (fn
)->decl
;
1784 if (srclen
!= NULL_TREE
)
1785 success
= update_gimple_call (gsi
, fn
, 5 + (objsz
!= NULL_TREE
),
1787 gimple_call_arg (stmt
, 1),
1789 gimple_call_arg (stmt
, 3),
1792 success
= update_gimple_call (gsi
, fn
, 4 + (objsz
!= NULL_TREE
),
1794 gimple_call_arg (stmt
, 1),
1796 gimple_call_arg (stmt
, 3),
1800 if (srclen
!= NULL_TREE
)
1801 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
1802 dst
, src
, len
, objsz
);
1804 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
1808 stmt
= gsi_stmt (*gsi
);
1809 gimple_call_set_with_bounds (stmt
, with_bounds
);
1811 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1813 fprintf (dump_file
, "into: ");
1814 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1816 /* If srclen == NULL, note that current string length can be
1817 computed by transforming this strcpy into stpcpy. */
1818 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
1820 adjust_last_stmt (dsi
, stmt
, true);
1821 if (srclen
!= NULL_TREE
)
1823 laststmt
.stmt
= stmt
;
1824 laststmt
.len
= srclen
;
1825 laststmt
.stridx
= dsi
->idx
;
1828 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1829 fprintf (dump_file
, "not possible.\n");
1832 /* Handle a call to malloc or calloc. */
1835 handle_builtin_malloc (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1837 gimple
*stmt
= gsi_stmt (*gsi
);
1838 tree lhs
= gimple_call_lhs (stmt
);
1839 gcc_assert (get_stridx (lhs
) == 0);
1840 int idx
= new_stridx (lhs
);
1841 tree length
= NULL_TREE
;
1842 if (bcode
== BUILT_IN_CALLOC
)
1843 length
= build_int_cst (size_type_node
, 0);
1844 strinfo
*si
= new_strinfo (lhs
, idx
, length
);
1845 if (bcode
== BUILT_IN_CALLOC
)
1847 set_strinfo (idx
, si
);
1848 si
->writable
= true;
1850 si
->dont_invalidate
= true;
1853 /* Handle a call to memset.
1854 After a call to calloc, memset(,0,) is unnecessary.
1855 memset(malloc(n),0,n) is calloc(n,1). */
1858 handle_builtin_memset (gimple_stmt_iterator
*gsi
)
1860 gimple
*stmt2
= gsi_stmt (*gsi
);
1861 if (!integer_zerop (gimple_call_arg (stmt2
, 1)))
1863 tree ptr
= gimple_call_arg (stmt2
, 0);
1864 int idx1
= get_stridx (ptr
);
1867 strinfo
*si1
= get_strinfo (idx1
);
1870 gimple
*stmt1
= si1
->stmt
;
1871 if (!stmt1
|| !is_gimple_call (stmt1
))
1873 tree callee1
= gimple_call_fndecl (stmt1
);
1874 if (!valid_builtin_call (stmt1
))
1876 enum built_in_function code1
= DECL_FUNCTION_CODE (callee1
);
1877 tree size
= gimple_call_arg (stmt2
, 2);
1878 if (code1
== BUILT_IN_CALLOC
)
1879 /* Not touching stmt1 */ ;
1880 else if (code1
== BUILT_IN_MALLOC
1881 && operand_equal_p (gimple_call_arg (stmt1
, 0), size
, 0))
1883 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt1
);
1884 update_gimple_call (&gsi1
, builtin_decl_implicit (BUILT_IN_CALLOC
), 2,
1885 size
, build_one_cst (size_type_node
));
1886 si1
->length
= build_int_cst (size_type_node
, 0);
1887 si1
->stmt
= gsi_stmt (gsi1
);
1891 tree lhs
= gimple_call_lhs (stmt2
);
1892 unlink_stmt_vdef (stmt2
);
1895 gimple
*assign
= gimple_build_assign (lhs
, ptr
);
1896 gsi_replace (gsi
, assign
, false);
1900 gsi_remove (gsi
, true);
1901 release_defs (stmt2
);
1907 /* Handle a call to memcmp. We try to handle small comparisons by
1908 converting them to load and compare, and replacing the call to memcmp
1909 with a __builtin_memcmp_eq call where possible. */
1912 handle_builtin_memcmp (gimple_stmt_iterator
*gsi
)
1914 gcall
*stmt2
= as_a
<gcall
*> (gsi_stmt (*gsi
));
1915 tree res
= gimple_call_lhs (stmt2
);
1916 tree arg1
= gimple_call_arg (stmt2
, 0);
1917 tree arg2
= gimple_call_arg (stmt2
, 1);
1918 tree len
= gimple_call_arg (stmt2
, 2);
1919 unsigned HOST_WIDE_INT leni
;
1920 use_operand_p use_p
;
1921 imm_use_iterator iter
;
1926 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
1928 gimple
*ustmt
= USE_STMT (use_p
);
1930 if (is_gimple_debug (ustmt
))
1932 if (gimple_code (ustmt
) == GIMPLE_ASSIGN
)
1934 gassign
*asgn
= as_a
<gassign
*> (ustmt
);
1935 tree_code code
= gimple_assign_rhs_code (asgn
);
1936 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
1937 || !integer_zerop (gimple_assign_rhs2 (asgn
)))
1940 else if (gimple_code (ustmt
) == GIMPLE_COND
)
1942 tree_code code
= gimple_cond_code (ustmt
);
1943 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
1944 || !integer_zerop (gimple_cond_rhs (ustmt
)))
1951 if (tree_fits_uhwi_p (len
)
1952 && (leni
= tree_to_uhwi (len
)) <= GET_MODE_SIZE (word_mode
)
1953 && exact_log2 (leni
) != -1)
1955 leni
*= CHAR_TYPE_SIZE
;
1956 unsigned align1
= get_pointer_alignment (arg1
);
1957 unsigned align2
= get_pointer_alignment (arg2
);
1958 unsigned align
= MIN (align1
, align2
);
1959 machine_mode mode
= mode_for_size (leni
, MODE_INT
, 1);
1961 && (align
>= leni
|| !SLOW_UNALIGNED_ACCESS (mode
, align
)))
1963 location_t loc
= gimple_location (stmt2
);
1965 type
= build_nonstandard_integer_type (leni
, 1);
1966 gcc_assert (GET_MODE_BITSIZE (TYPE_MODE (type
)) == leni
);
1967 tree ptrtype
= build_pointer_type_for_mode (char_type_node
,
1969 off
= build_int_cst (ptrtype
, 0);
1970 arg1
= build2_loc (loc
, MEM_REF
, type
, arg1
, off
);
1971 arg2
= build2_loc (loc
, MEM_REF
, type
, arg2
, off
);
1972 tree tem1
= fold_const_aggregate_ref (arg1
);
1975 tree tem2
= fold_const_aggregate_ref (arg2
);
1978 res
= fold_convert_loc (loc
, TREE_TYPE (res
),
1979 fold_build2_loc (loc
, NE_EXPR
,
1982 gimplify_and_update_call_from_tree (gsi
, res
);
1987 gimple_call_set_fndecl (stmt2
, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ
));
1991 /* Handle a POINTER_PLUS_EXPR statement.
1992 For p = "abcd" + 2; compute associated length, or if
1993 p = q + off is pointing to a '\0' character of a string, call
1994 zero_length_string on it. */
1997 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
1999 gimple
*stmt
= gsi_stmt (*gsi
);
2000 tree lhs
= gimple_assign_lhs (stmt
), off
;
2001 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
2009 tree off
= gimple_assign_rhs2 (stmt
);
2010 if (tree_fits_uhwi_p (off
)
2011 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
2012 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
2013 = ~(~idx
- (int) tree_to_uhwi (off
));
2017 si
= get_strinfo (idx
);
2018 if (si
== NULL
|| si
->length
== NULL_TREE
)
2021 off
= gimple_assign_rhs2 (stmt
);
2023 if (operand_equal_p (si
->length
, off
, 0))
2024 zsi
= zero_length_string (lhs
, si
);
2025 else if (TREE_CODE (off
) == SSA_NAME
)
2027 gimple
*def_stmt
= SSA_NAME_DEF_STMT (off
);
2028 if (gimple_assign_single_p (def_stmt
)
2029 && operand_equal_p (si
->length
, gimple_assign_rhs1 (def_stmt
), 0))
2030 zsi
= zero_length_string (lhs
, si
);
2033 && si
->endptr
!= NULL_TREE
2034 && si
->endptr
!= lhs
2035 && TREE_CODE (si
->endptr
) == SSA_NAME
)
2037 enum tree_code rhs_code
2038 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
2039 ? SSA_NAME
: NOP_EXPR
;
2040 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
);
2041 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2046 /* Handle a single character store. */
2049 handle_char_store (gimple_stmt_iterator
*gsi
)
2053 gimple
*stmt
= gsi_stmt (*gsi
);
2054 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
2056 if (TREE_CODE (lhs
) == MEM_REF
2057 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
2059 if (integer_zerop (TREE_OPERAND (lhs
, 1)))
2061 ssaname
= TREE_OPERAND (lhs
, 0);
2062 idx
= get_stridx (ssaname
);
2066 idx
= get_addr_stridx (lhs
);
2070 si
= get_strinfo (idx
);
2071 if (si
!= NULL
&& si
->length
!= NULL_TREE
&& integer_zerop (si
->length
))
2073 if (initializer_zerop (gimple_assign_rhs1 (stmt
)))
2075 /* When storing '\0', the store can be removed
2076 if we know it has been stored in the current function. */
2077 if (!stmt_could_throw_p (stmt
) && si
->writable
)
2079 unlink_stmt_vdef (stmt
);
2080 release_defs (stmt
);
2081 gsi_remove (gsi
, true);
2086 si
->writable
= true;
2092 /* Otherwise this statement overwrites the '\0' with
2093 something, if the previous stmt was a memcpy,
2094 its length may be decreased. */
2095 adjust_last_stmt (si
, stmt
, false);
2097 else if (si
!= NULL
&& integer_zerop (gimple_assign_rhs1 (stmt
)))
2099 si
= unshare_strinfo (si
);
2100 si
->length
= build_int_cst (size_type_node
, 0);
2106 si
->writable
= true;
2107 if (ssaname
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
2108 si
->endptr
= ssaname
;
2109 si
->dont_invalidate
= true;
2111 /* If si->length is non-zero constant, we aren't overwriting '\0',
2112 and if we aren't storing '\0', we know that the length of the
2113 string and any other zero terminated string in memory remains
2114 the same. In that case we move to the next gimple statement and
2115 return to signal the caller that it shouldn't invalidate anything.
2117 This is benefical for cases like:
2122 strcpy (p, "foobar");
2123 size_t len = strlen (p); // This can be optimized into 6
2124 size_t len2 = strlen (q); // This has to be computed
2126 size_t len3 = strlen (p); // This can be optimized into 6
2127 size_t len4 = strlen (q); // This can be optimized into len2
2128 bar (len, len2, len3, len4);
2131 else if (si
!= NULL
&& si
->length
!= NULL_TREE
2132 && TREE_CODE (si
->length
) == INTEGER_CST
2133 && integer_nonzerop (gimple_assign_rhs1 (stmt
)))
2139 else if (idx
== 0 && initializer_zerop (gimple_assign_rhs1 (stmt
)))
2143 si
= zero_length_string (ssaname
, NULL
);
2145 si
->dont_invalidate
= true;
2149 int idx
= new_addr_stridx (lhs
);
2152 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
2153 build_int_cst (size_type_node
, 0));
2154 set_strinfo (idx
, si
);
2155 si
->dont_invalidate
= true;
2159 si
->writable
= true;
2162 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == STRING_CST
2163 && ssaname
== NULL_TREE
2164 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
2166 size_t l
= strlen (TREE_STRING_POINTER (gimple_assign_rhs1 (stmt
)));
2167 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
2168 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> l
)
2170 int idx
= new_addr_stridx (lhs
);
2173 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
2174 build_int_cst (size_type_node
, l
));
2175 set_strinfo (idx
, si
);
2176 si
->dont_invalidate
= true;
2181 if (si
!= NULL
&& initializer_zerop (gimple_assign_rhs1 (stmt
)))
2183 /* Allow adjust_last_stmt to remove it if the stored '\0'
2184 is immediately overwritten. */
2185 laststmt
.stmt
= stmt
;
2186 laststmt
.len
= build_int_cst (size_type_node
, 1);
2187 laststmt
.stridx
= si
->idx
;
2192 /* Attempt to optimize a single statement at *GSI using string length
2196 strlen_optimize_stmt (gimple_stmt_iterator
*gsi
)
2198 gimple
*stmt
= gsi_stmt (*gsi
);
2200 if (is_gimple_call (stmt
))
2202 tree callee
= gimple_call_fndecl (stmt
);
2203 if (valid_builtin_call (stmt
))
2204 switch (DECL_FUNCTION_CODE (callee
))
2206 case BUILT_IN_STRLEN
:
2207 case BUILT_IN_STRLEN_CHKP
:
2208 handle_builtin_strlen (gsi
);
2210 case BUILT_IN_STRCHR
:
2211 case BUILT_IN_STRCHR_CHKP
:
2212 handle_builtin_strchr (gsi
);
2214 case BUILT_IN_STRCPY
:
2215 case BUILT_IN_STRCPY_CHK
:
2216 case BUILT_IN_STPCPY
:
2217 case BUILT_IN_STPCPY_CHK
:
2218 case BUILT_IN_STRCPY_CHKP
:
2219 case BUILT_IN_STRCPY_CHK_CHKP
:
2220 case BUILT_IN_STPCPY_CHKP
:
2221 case BUILT_IN_STPCPY_CHK_CHKP
:
2222 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
2224 case BUILT_IN_MEMCPY
:
2225 case BUILT_IN_MEMCPY_CHK
:
2226 case BUILT_IN_MEMPCPY
:
2227 case BUILT_IN_MEMPCPY_CHK
:
2228 case BUILT_IN_MEMCPY_CHKP
:
2229 case BUILT_IN_MEMCPY_CHK_CHKP
:
2230 case BUILT_IN_MEMPCPY_CHKP
:
2231 case BUILT_IN_MEMPCPY_CHK_CHKP
:
2232 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
2234 case BUILT_IN_STRCAT
:
2235 case BUILT_IN_STRCAT_CHK
:
2236 case BUILT_IN_STRCAT_CHKP
:
2237 case BUILT_IN_STRCAT_CHK_CHKP
:
2238 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
2240 case BUILT_IN_MALLOC
:
2241 case BUILT_IN_CALLOC
:
2242 handle_builtin_malloc (DECL_FUNCTION_CODE (callee
), gsi
);
2244 case BUILT_IN_MEMSET
:
2245 if (!handle_builtin_memset (gsi
))
2248 case BUILT_IN_MEMCMP
:
2249 if (!handle_builtin_memcmp (gsi
))
2256 else if (is_gimple_assign (stmt
) && !gimple_clobber_p (stmt
))
2258 tree lhs
= gimple_assign_lhs (stmt
);
2260 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
2262 if (gimple_assign_single_p (stmt
)
2263 || (gimple_assign_cast_p (stmt
)
2264 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
2266 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
2267 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
2269 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
2270 handle_pointer_plus (gsi
);
2272 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
2274 tree type
= TREE_TYPE (lhs
);
2275 if (TREE_CODE (type
) == ARRAY_TYPE
)
2276 type
= TREE_TYPE (type
);
2277 if (TREE_CODE (type
) == INTEGER_TYPE
2278 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
2279 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
2281 if (! handle_char_store (gsi
))
2287 if (gimple_vdef (stmt
))
2288 maybe_invalidate (stmt
);
2292 /* Recursively call maybe_invalidate on stmts that might be executed
2293 in between dombb and current bb and that contain a vdef. Stop when
2294 *count stmts are inspected, or if the whole strinfo vector has
2295 been invalidated. */
2298 do_invalidate (basic_block dombb
, gimple
*phi
, bitmap visited
, int *count
)
2300 unsigned int i
, n
= gimple_phi_num_args (phi
);
2302 for (i
= 0; i
< n
; i
++)
2304 tree vuse
= gimple_phi_arg_def (phi
, i
);
2305 gimple
*stmt
= SSA_NAME_DEF_STMT (vuse
);
2306 basic_block bb
= gimple_bb (stmt
);
2309 || !bitmap_set_bit (visited
, bb
->index
)
2310 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
2314 if (gimple_code (stmt
) == GIMPLE_PHI
)
2316 do_invalidate (dombb
, stmt
, visited
, count
);
2323 if (!maybe_invalidate (stmt
))
2328 vuse
= gimple_vuse (stmt
);
2329 stmt
= SSA_NAME_DEF_STMT (vuse
);
2330 if (gimple_bb (stmt
) != bb
)
2332 bb
= gimple_bb (stmt
);
2335 || !bitmap_set_bit (visited
, bb
->index
)
2336 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
2343 class strlen_dom_walker
: public dom_walker
2346 strlen_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
2348 virtual edge
before_dom_children (basic_block
);
2349 virtual void after_dom_children (basic_block
);
2352 /* Callback for walk_dominator_tree. Attempt to optimize various
2353 string ops by remembering string lenths pointed by pointer SSA_NAMEs. */
2356 strlen_dom_walker::before_dom_children (basic_block bb
)
2358 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
2361 stridx_to_strinfo
= NULL
;
2364 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) dombb
->aux
);
2365 if (stridx_to_strinfo
)
2367 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
2370 gphi
*phi
= gsi
.phi ();
2371 if (virtual_operand_p (gimple_phi_result (phi
)))
2373 bitmap visited
= BITMAP_ALLOC (NULL
);
2374 int count_vdef
= 100;
2375 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
2376 BITMAP_FREE (visited
);
2377 if (count_vdef
== 0)
2379 /* If there were too many vdefs in between immediate
2380 dominator and current bb, invalidate everything.
2381 If stridx_to_strinfo has been unshared, we need
2382 to free it, otherwise just set it to NULL. */
2383 if (!strinfo_shared ())
2389 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
2393 (*stridx_to_strinfo
)[i
] = NULL
;
2397 stridx_to_strinfo
= NULL
;
2405 /* If all PHI arguments have the same string index, the PHI result
2407 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
2410 gphi
*phi
= gsi
.phi ();
2411 tree result
= gimple_phi_result (phi
);
2412 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
2414 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
2417 unsigned int i
, n
= gimple_phi_num_args (phi
);
2418 for (i
= 1; i
< n
; i
++)
2419 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
2422 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
2427 /* Attempt to optimize individual statements. */
2428 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2429 if (strlen_optimize_stmt (&gsi
))
2432 bb
->aux
= stridx_to_strinfo
;
2433 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
2434 (*stridx_to_strinfo
)[0] = (strinfo
*) bb
;
2438 /* Callback for walk_dominator_tree. Free strinfo vector if it is
2439 owned by the current bb, clear bb->aux. */
2442 strlen_dom_walker::after_dom_children (basic_block bb
)
2446 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) bb
->aux
);
2447 if (vec_safe_length (stridx_to_strinfo
)
2448 && (*stridx_to_strinfo
)[0] == (strinfo
*) bb
)
2453 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
2455 vec_free (stridx_to_strinfo
);
2461 /* Main entry point. */
2465 const pass_data pass_data_strlen
=
2467 GIMPLE_PASS
, /* type */
2468 "strlen", /* name */
2469 OPTGROUP_NONE
, /* optinfo_flags */
2470 TV_TREE_STRLEN
, /* tv_id */
2471 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2472 0, /* properties_provided */
2473 0, /* properties_destroyed */
2474 0, /* todo_flags_start */
2475 0, /* todo_flags_finish */
2478 class pass_strlen
: public gimple_opt_pass
2481 pass_strlen (gcc::context
*ctxt
)
2482 : gimple_opt_pass (pass_data_strlen
, ctxt
)
2485 /* opt_pass methods: */
2486 virtual bool gate (function
*) { return flag_optimize_strlen
!= 0; }
2487 virtual unsigned int execute (function
*);
2489 }; // class pass_strlen
2492 pass_strlen::execute (function
*fun
)
2494 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
2497 calculate_dominance_info (CDI_DOMINATORS
);
2499 /* String length optimization is implemented as a walk of the dominator
2500 tree and a forward walk of statements within each block. */
2501 strlen_dom_walker (CDI_DOMINATORS
).walk (fun
->cfg
->x_entry_block_ptr
);
2503 ssa_ver_to_stridx
.release ();
2504 strinfo_pool
.release ();
2505 if (decl_to_stridxlist_htab
)
2507 obstack_free (&stridx_obstack
, NULL
);
2508 delete decl_to_stridxlist_htab
;
2509 decl_to_stridxlist_htab
= NULL
;
2511 laststmt
.stmt
= NULL
;
2512 laststmt
.len
= NULL_TREE
;
2513 laststmt
.stridx
= 0;
2521 make_pass_strlen (gcc::context
*ctxt
)
2523 return new pass_strlen (ctxt
);