Daily bump.
[official-gcc.git] / gcc / tree-ssa-strlen.c
blobb0563fe7c324001bc606b680e5ac24856b7d1d86
1 /* String length optimization
2 Copyright (C) 2011-2017 Free Software Foundation, Inc.
3 Contributed by Jakub Jelinek <jakub@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "backend.h"
25 #include "rtl.h"
26 #include "tree.h"
27 #include "gimple.h"
28 #include "alloc-pool.h"
29 #include "tree-pass.h"
30 #include "ssa.h"
31 #include "cgraph.h"
32 #include "gimple-pretty-print.h"
33 #include "fold-const.h"
34 #include "stor-layout.h"
35 #include "gimple-fold.h"
36 #include "tree-eh.h"
37 #include "gimplify.h"
38 #include "gimple-iterator.h"
39 #include "gimplify-me.h"
40 #include "expr.h"
41 #include "tree-dfa.h"
42 #include "domwalk.h"
43 #include "tree-ssa-propagate.h"
44 #include "params.h"
45 #include "ipa-chkp.h"
46 #include "tree-hash-traits.h"
47 #include "builtins.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. */
58 struct strinfo
60 /* Number of leading characters that are known to be nonzero. This is
61 also the length of the string if FULL_STRING_P.
63 The values in a list of related string pointers must be consistent;
64 that is, if strinfo B comes X bytes after strinfo A, it must be
65 the case that A->nonzero_chars == X + B->nonzero_chars. */
66 tree nonzero_chars;
67 /* Any of the corresponding pointers for querying alias oracle. */
68 tree ptr;
69 /* This is used for two things:
71 - To record the statement that should be used for delayed length
72 computations. We maintain the invariant that all related strinfos
73 have delayed lengths or none do.
75 - To record the malloc or calloc call that produced this result. */
76 gimple *stmt;
77 /* Pointer to '\0' if known, if NULL, it can be computed as
78 ptr + length. */
79 tree endptr;
80 /* Reference count. Any changes to strinfo entry possibly shared
81 with dominating basic blocks need unshare_strinfo first, except
82 for dont_invalidate which affects only the immediately next
83 maybe_invalidate. */
84 int refcount;
85 /* Copy of index. get_strinfo (si->idx) should return si; */
86 int idx;
87 /* These 3 fields are for chaining related string pointers together.
88 E.g. for
89 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
90 strcpy (c, d); e = c + dl;
91 strinfo(a) -> strinfo(c) -> strinfo(e)
92 All have ->first field equal to strinfo(a)->idx and are doubly
93 chained through prev/next fields. The later strinfos are required
94 to point into the same string with zero or more bytes after
95 the previous pointer and all bytes in between the two pointers
96 must be non-zero. Functions like strcpy or memcpy are supposed
97 to adjust all previous strinfo lengths, but not following strinfo
98 lengths (those are uncertain, usually invalidated during
99 maybe_invalidate, except when the alias oracle knows better).
100 Functions like strcat on the other side adjust the whole
101 related strinfo chain.
102 They are updated lazily, so to use the chain the same first fields
103 and si->prev->next == si->idx needs to be verified. */
104 int first;
105 int next;
106 int prev;
107 /* A flag whether the string is known to be written in the current
108 function. */
109 bool writable;
110 /* A flag for the next maybe_invalidate that this strinfo shouldn't
111 be invalidated. Always cleared by maybe_invalidate. */
112 bool dont_invalidate;
113 /* True if the string is known to be nul-terminated after NONZERO_CHARS
114 characters. False is useful when detecting strings that are built
115 up via successive memcpys. */
116 bool full_string_p;
119 /* Pool for allocating strinfo_struct entries. */
120 static object_allocator<strinfo> strinfo_pool ("strinfo pool");
122 /* Vector mapping positive string indexes to strinfo, for the
123 current basic block. The first pointer in the vector is special,
124 it is either NULL, meaning the vector isn't shared, or it is
125 a basic block pointer to the owner basic_block if shared.
126 If some other bb wants to modify the vector, the vector needs
127 to be unshared first, and only the owner bb is supposed to free it. */
128 static vec<strinfo *, va_heap, vl_embed> *stridx_to_strinfo;
130 /* One OFFSET->IDX mapping. */
131 struct stridxlist
133 struct stridxlist *next;
134 HOST_WIDE_INT offset;
135 int idx;
138 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
139 struct decl_stridxlist_map
141 struct tree_map_base base;
142 struct stridxlist list;
145 /* Hash table for mapping decls to a chained list of offset -> idx
146 mappings. */
147 static hash_map<tree_decl_hash, stridxlist> *decl_to_stridxlist_htab;
149 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
150 static struct obstack stridx_obstack;
152 /* Last memcpy statement if it could be adjusted if the trailing
153 '\0' written is immediately overwritten, or
154 *x = '\0' store that could be removed if it is immediately overwritten. */
155 struct laststmt_struct
157 gimple *stmt;
158 tree len;
159 int stridx;
160 } laststmt;
162 static int get_stridx_plus_constant (strinfo *, unsigned HOST_WIDE_INT, tree);
164 /* Return:
166 - 1 if SI is known to start with more than OFF nonzero characters.
168 - 0 if SI is known to start with OFF nonzero characters,
169 but is not known to start with more.
171 - -1 if SI might not start with OFF nonzero characters. */
173 static inline int
174 compare_nonzero_chars (strinfo *si, unsigned HOST_WIDE_INT off)
176 if (si->nonzero_chars
177 && TREE_CODE (si->nonzero_chars) == INTEGER_CST)
178 return compare_tree_int (si->nonzero_chars, off);
179 else
180 return -1;
183 /* Return true if SI is known to be a zero-length string. */
185 static inline bool
186 zero_length_string_p (strinfo *si)
188 return si->full_string_p && integer_zerop (si->nonzero_chars);
191 /* Return strinfo vector entry IDX. */
193 static inline strinfo *
194 get_strinfo (int idx)
196 if (vec_safe_length (stridx_to_strinfo) <= (unsigned int) idx)
197 return NULL;
198 return (*stridx_to_strinfo)[idx];
201 /* Get the next strinfo in the chain after SI, or null if none. */
203 static inline strinfo *
204 get_next_strinfo (strinfo *si)
206 if (si->next == 0)
207 return NULL;
208 strinfo *nextsi = get_strinfo (si->next);
209 if (nextsi == NULL || nextsi->first != si->first || nextsi->prev != si->idx)
210 return NULL;
211 return nextsi;
214 /* Helper function for get_stridx. Return the strinfo index of the address
215 of EXP, which is available in PTR if nonnull. If OFFSET_OUT, it is
216 OK to return the index for some X <= &EXP and store &EXP - X in
217 *OFFSET_OUT. */
219 static int
220 get_addr_stridx (tree exp, tree ptr, unsigned HOST_WIDE_INT *offset_out)
222 HOST_WIDE_INT off;
223 struct stridxlist *list, *last = NULL;
224 tree base;
226 if (!decl_to_stridxlist_htab)
227 return 0;
229 base = get_addr_base_and_unit_offset (exp, &off);
230 if (base == NULL || !DECL_P (base))
231 return 0;
233 list = decl_to_stridxlist_htab->get (base);
234 if (list == NULL)
235 return 0;
239 if (list->offset == off)
241 if (offset_out)
242 *offset_out = 0;
243 return list->idx;
245 if (list->offset > off)
246 return 0;
247 last = list;
248 list = list->next;
250 while (list);
252 if ((offset_out || ptr) && last && last->idx > 0)
254 unsigned HOST_WIDE_INT rel_off
255 = (unsigned HOST_WIDE_INT) off - last->offset;
256 strinfo *si = get_strinfo (last->idx);
257 if (si && compare_nonzero_chars (si, rel_off) >= 0)
259 if (offset_out)
261 *offset_out = rel_off;
262 return last->idx;
264 else
265 return get_stridx_plus_constant (si, rel_off, ptr);
268 return 0;
271 /* Return string index for EXP. */
273 static int
274 get_stridx (tree exp)
276 tree s, o;
278 if (TREE_CODE (exp) == SSA_NAME)
280 if (ssa_ver_to_stridx[SSA_NAME_VERSION (exp)])
281 return ssa_ver_to_stridx[SSA_NAME_VERSION (exp)];
282 int i;
283 tree e = exp;
284 HOST_WIDE_INT off = 0;
285 for (i = 0; i < 5; i++)
287 gimple *def_stmt = SSA_NAME_DEF_STMT (e);
288 if (!is_gimple_assign (def_stmt)
289 || gimple_assign_rhs_code (def_stmt) != POINTER_PLUS_EXPR)
290 return 0;
291 tree rhs1 = gimple_assign_rhs1 (def_stmt);
292 tree rhs2 = gimple_assign_rhs2 (def_stmt);
293 if (TREE_CODE (rhs1) != SSA_NAME
294 || !tree_fits_shwi_p (rhs2))
295 return 0;
296 HOST_WIDE_INT this_off = tree_to_shwi (rhs2);
297 if (this_off < 0)
298 return 0;
299 off = (unsigned HOST_WIDE_INT) off + this_off;
300 if (off < 0)
301 return 0;
302 if (ssa_ver_to_stridx[SSA_NAME_VERSION (rhs1)])
304 strinfo *si
305 = get_strinfo (ssa_ver_to_stridx[SSA_NAME_VERSION (rhs1)]);
306 if (si && compare_nonzero_chars (si, off) >= 0)
307 return get_stridx_plus_constant (si, off, exp);
309 e = rhs1;
311 return 0;
314 if (TREE_CODE (exp) == ADDR_EXPR)
316 int idx = get_addr_stridx (TREE_OPERAND (exp, 0), exp, NULL);
317 if (idx != 0)
318 return idx;
321 s = string_constant (exp, &o);
322 if (s != NULL_TREE
323 && (o == NULL_TREE || tree_fits_shwi_p (o))
324 && TREE_STRING_LENGTH (s) > 0)
326 HOST_WIDE_INT offset = o ? tree_to_shwi (o) : 0;
327 const char *p = TREE_STRING_POINTER (s);
328 int max = TREE_STRING_LENGTH (s) - 1;
330 if (p[max] == '\0' && offset >= 0 && offset <= max)
331 return ~(int) strlen (p + offset);
333 return 0;
336 /* Return true if strinfo vector is shared with the immediate dominator. */
338 static inline bool
339 strinfo_shared (void)
341 return vec_safe_length (stridx_to_strinfo)
342 && (*stridx_to_strinfo)[0] != NULL;
345 /* Unshare strinfo vector that is shared with the immediate dominator. */
347 static void
348 unshare_strinfo_vec (void)
350 strinfo *si;
351 unsigned int i = 0;
353 gcc_assert (strinfo_shared ());
354 stridx_to_strinfo = vec_safe_copy (stridx_to_strinfo);
355 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
356 if (si != NULL)
357 si->refcount++;
358 (*stridx_to_strinfo)[0] = NULL;
361 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
362 Return a pointer to the location where the string index can
363 be stored (if 0) or is stored, or NULL if this can't be tracked. */
365 static int *
366 addr_stridxptr (tree exp)
368 HOST_WIDE_INT off;
370 tree base = get_addr_base_and_unit_offset (exp, &off);
371 if (base == NULL_TREE || !DECL_P (base))
372 return NULL;
374 if (!decl_to_stridxlist_htab)
376 decl_to_stridxlist_htab
377 = new hash_map<tree_decl_hash, stridxlist> (64);
378 gcc_obstack_init (&stridx_obstack);
381 bool existed;
382 stridxlist *list = &decl_to_stridxlist_htab->get_or_insert (base, &existed);
383 if (existed)
385 int i;
386 stridxlist *before = NULL;
387 for (i = 0; i < 32; i++)
389 if (list->offset == off)
390 return &list->idx;
391 if (list->offset > off && before == NULL)
392 before = list;
393 if (list->next == NULL)
394 break;
395 list = list->next;
397 if (i == 32)
398 return NULL;
399 if (before)
401 list = before;
402 before = XOBNEW (&stridx_obstack, struct stridxlist);
403 *before = *list;
404 list->next = before;
405 list->offset = off;
406 list->idx = 0;
407 return &list->idx;
409 list->next = XOBNEW (&stridx_obstack, struct stridxlist);
410 list = list->next;
413 list->next = NULL;
414 list->offset = off;
415 list->idx = 0;
416 return &list->idx;
419 /* Create a new string index, or return 0 if reached limit. */
421 static int
422 new_stridx (tree exp)
424 int idx;
425 if (max_stridx >= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS))
426 return 0;
427 if (TREE_CODE (exp) == SSA_NAME)
429 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp))
430 return 0;
431 idx = max_stridx++;
432 ssa_ver_to_stridx[SSA_NAME_VERSION (exp)] = idx;
433 return idx;
435 if (TREE_CODE (exp) == ADDR_EXPR)
437 int *pidx = addr_stridxptr (TREE_OPERAND (exp, 0));
438 if (pidx != NULL)
440 gcc_assert (*pidx == 0);
441 *pidx = max_stridx++;
442 return *pidx;
445 return 0;
448 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
450 static int
451 new_addr_stridx (tree exp)
453 int *pidx;
454 if (max_stridx >= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS))
455 return 0;
456 pidx = addr_stridxptr (exp);
457 if (pidx != NULL)
459 gcc_assert (*pidx == 0);
460 *pidx = max_stridx++;
461 return *pidx;
463 return 0;
466 /* Create a new strinfo. */
468 static strinfo *
469 new_strinfo (tree ptr, int idx, tree nonzero_chars, bool full_string_p)
471 strinfo *si = strinfo_pool.allocate ();
472 si->nonzero_chars = nonzero_chars;
473 si->ptr = ptr;
474 si->stmt = NULL;
475 si->endptr = NULL_TREE;
476 si->refcount = 1;
477 si->idx = idx;
478 si->first = 0;
479 si->prev = 0;
480 si->next = 0;
481 si->writable = false;
482 si->dont_invalidate = false;
483 si->full_string_p = full_string_p;
484 return si;
487 /* Decrease strinfo refcount and free it if not referenced anymore. */
489 static inline void
490 free_strinfo (strinfo *si)
492 if (si && --si->refcount == 0)
493 strinfo_pool.remove (si);
496 /* Set strinfo in the vector entry IDX to SI. */
498 static inline void
499 set_strinfo (int idx, strinfo *si)
501 if (vec_safe_length (stridx_to_strinfo) && (*stridx_to_strinfo)[0])
502 unshare_strinfo_vec ();
503 if (vec_safe_length (stridx_to_strinfo) <= (unsigned int) idx)
504 vec_safe_grow_cleared (stridx_to_strinfo, idx + 1);
505 (*stridx_to_strinfo)[idx] = si;
508 /* Return the first strinfo in the related strinfo chain
509 if all strinfos in between belong to the chain, otherwise NULL. */
511 static strinfo *
512 verify_related_strinfos (strinfo *origsi)
514 strinfo *si = origsi, *psi;
516 if (origsi->first == 0)
517 return NULL;
518 for (; si->prev; si = psi)
520 if (si->first != origsi->first)
521 return NULL;
522 psi = get_strinfo (si->prev);
523 if (psi == NULL)
524 return NULL;
525 if (psi->next != si->idx)
526 return NULL;
528 if (si->idx != si->first)
529 return NULL;
530 return si;
533 /* Set SI's endptr to ENDPTR and compute its length based on SI->ptr.
534 Use LOC for folding. */
536 static void
537 set_endptr_and_length (location_t loc, strinfo *si, tree endptr)
539 si->endptr = endptr;
540 si->stmt = NULL;
541 tree start_as_size = fold_convert_loc (loc, size_type_node, si->ptr);
542 tree end_as_size = fold_convert_loc (loc, size_type_node, endptr);
543 si->nonzero_chars = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
544 end_as_size, start_as_size);
545 si->full_string_p = true;
548 /* Return string length, or NULL if it can't be computed. */
550 static tree
551 get_string_length (strinfo *si)
553 if (si->nonzero_chars)
554 return si->full_string_p ? si->nonzero_chars : NULL;
556 if (si->stmt)
558 gimple *stmt = si->stmt, *lenstmt;
559 bool with_bounds = gimple_call_with_bounds_p (stmt);
560 tree callee, lhs, fn, tem;
561 location_t loc;
562 gimple_stmt_iterator gsi;
564 gcc_assert (is_gimple_call (stmt));
565 callee = gimple_call_fndecl (stmt);
566 gcc_assert (callee && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL);
567 lhs = gimple_call_lhs (stmt);
568 /* unshare_strinfo is intentionally not called here. The (delayed)
569 transformation of strcpy or strcat into stpcpy is done at the place
570 of the former strcpy/strcat call and so can affect all the strinfos
571 with the same stmt. If they were unshared before and transformation
572 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
573 just compute the right length. */
574 switch (DECL_FUNCTION_CODE (callee))
576 case BUILT_IN_STRCAT:
577 case BUILT_IN_STRCAT_CHK:
578 case BUILT_IN_STRCAT_CHKP:
579 case BUILT_IN_STRCAT_CHK_CHKP:
580 gsi = gsi_for_stmt (stmt);
581 fn = builtin_decl_implicit (BUILT_IN_STRLEN);
582 gcc_assert (lhs == NULL_TREE);
583 tem = unshare_expr (gimple_call_arg (stmt, 0));
584 if (with_bounds)
586 lenstmt = gimple_build_call (chkp_maybe_create_clone (fn)->decl,
587 2, tem, gimple_call_arg (stmt, 1));
588 gimple_call_set_with_bounds (lenstmt, true);
590 else
591 lenstmt = gimple_build_call (fn, 1, tem);
592 lhs = make_ssa_name (TREE_TYPE (TREE_TYPE (fn)), lenstmt);
593 gimple_call_set_lhs (lenstmt, lhs);
594 gimple_set_vuse (lenstmt, gimple_vuse (stmt));
595 gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT);
596 tem = gimple_call_arg (stmt, 0);
597 if (!ptrofftype_p (TREE_TYPE (lhs)))
599 lhs = convert_to_ptrofftype (lhs);
600 lhs = force_gimple_operand_gsi (&gsi, lhs, true, NULL_TREE,
601 true, GSI_SAME_STMT);
603 lenstmt = gimple_build_assign
604 (make_ssa_name (TREE_TYPE (gimple_call_arg (stmt, 0))),
605 POINTER_PLUS_EXPR,tem, lhs);
606 gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT);
607 gimple_call_set_arg (stmt, 0, gimple_assign_lhs (lenstmt));
608 lhs = NULL_TREE;
609 /* FALLTHRU */
610 case BUILT_IN_STRCPY:
611 case BUILT_IN_STRCPY_CHK:
612 case BUILT_IN_STRCPY_CHKP:
613 case BUILT_IN_STRCPY_CHK_CHKP:
614 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY));
615 if (gimple_call_num_args (stmt) == (with_bounds ? 4 : 2))
616 fn = builtin_decl_implicit (BUILT_IN_STPCPY);
617 else
618 fn = builtin_decl_explicit (BUILT_IN_STPCPY_CHK);
619 if (with_bounds)
620 fn = chkp_maybe_create_clone (fn)->decl;
621 gcc_assert (lhs == NULL_TREE);
622 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
624 fprintf (dump_file, "Optimizing: ");
625 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
627 gimple_call_set_fndecl (stmt, fn);
628 lhs = make_ssa_name (TREE_TYPE (TREE_TYPE (fn)), stmt);
629 gimple_call_set_lhs (stmt, lhs);
630 update_stmt (stmt);
631 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
633 fprintf (dump_file, "into: ");
634 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
636 /* FALLTHRU */
637 case BUILT_IN_STPCPY:
638 case BUILT_IN_STPCPY_CHK:
639 case BUILT_IN_STPCPY_CHKP:
640 case BUILT_IN_STPCPY_CHK_CHKP:
641 gcc_assert (lhs != NULL_TREE);
642 loc = gimple_location (stmt);
643 set_endptr_and_length (loc, si, lhs);
644 for (strinfo *chainsi = verify_related_strinfos (si);
645 chainsi != NULL;
646 chainsi = get_next_strinfo (chainsi))
647 if (chainsi->nonzero_chars == NULL)
648 set_endptr_and_length (loc, chainsi, lhs);
649 break;
650 case BUILT_IN_MALLOC:
651 break;
652 /* BUILT_IN_CALLOC always has si->nonzero_chars set. */
653 default:
654 gcc_unreachable ();
655 break;
659 return si->nonzero_chars;
662 /* Invalidate string length information for strings whose length
663 might change due to stores in stmt. */
665 static bool
666 maybe_invalidate (gimple *stmt)
668 strinfo *si;
669 unsigned int i;
670 bool nonempty = false;
672 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
673 if (si != NULL)
675 if (!si->dont_invalidate)
677 ao_ref r;
678 /* Do not use si->nonzero_chars. */
679 ao_ref_init_from_ptr_and_size (&r, si->ptr, NULL_TREE);
680 if (stmt_may_clobber_ref_p_1 (stmt, &r))
682 set_strinfo (i, NULL);
683 free_strinfo (si);
684 continue;
687 si->dont_invalidate = false;
688 nonempty = true;
690 return nonempty;
693 /* Unshare strinfo record SI, if it has refcount > 1 or
694 if stridx_to_strinfo vector is shared with some other
695 bbs. */
697 static strinfo *
698 unshare_strinfo (strinfo *si)
700 strinfo *nsi;
702 if (si->refcount == 1 && !strinfo_shared ())
703 return si;
705 nsi = new_strinfo (si->ptr, si->idx, si->nonzero_chars, si->full_string_p);
706 nsi->stmt = si->stmt;
707 nsi->endptr = si->endptr;
708 nsi->first = si->first;
709 nsi->prev = si->prev;
710 nsi->next = si->next;
711 nsi->writable = si->writable;
712 set_strinfo (si->idx, nsi);
713 free_strinfo (si);
714 return nsi;
717 /* Attempt to create a new strinfo for BASESI + OFF, or find existing
718 strinfo if there is any. Return it's idx, or 0 if no strinfo has
719 been created. */
721 static int
722 get_stridx_plus_constant (strinfo *basesi, unsigned HOST_WIDE_INT off,
723 tree ptr)
725 if (TREE_CODE (ptr) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
726 return 0;
728 if (compare_nonzero_chars (basesi, off) < 0
729 || !tree_fits_uhwi_p (basesi->nonzero_chars))
730 return 0;
732 unsigned HOST_WIDE_INT nonzero_chars
733 = tree_to_uhwi (basesi->nonzero_chars) - off;
734 strinfo *si = basesi, *chainsi;
735 if (si->first || si->prev || si->next)
736 si = verify_related_strinfos (basesi);
737 if (si == NULL
738 || si->nonzero_chars == NULL_TREE
739 || TREE_CODE (si->nonzero_chars) != INTEGER_CST)
740 return 0;
742 if (TREE_CODE (ptr) == SSA_NAME
743 && ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
744 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
746 gcc_checking_assert (compare_tree_int (si->nonzero_chars, off) != -1);
747 for (chainsi = si; chainsi->next; chainsi = si)
749 si = get_next_strinfo (chainsi);
750 if (si == NULL
751 || si->nonzero_chars == NULL_TREE
752 || TREE_CODE (si->nonzero_chars) != INTEGER_CST)
753 break;
754 int r = compare_tree_int (si->nonzero_chars, nonzero_chars);
755 if (r != 1)
757 if (r == 0)
759 if (TREE_CODE (ptr) == SSA_NAME)
760 ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = si->idx;
761 else
763 int *pidx = addr_stridxptr (TREE_OPERAND (ptr, 0));
764 if (pidx != NULL && *pidx == 0)
765 *pidx = si->idx;
767 return si->idx;
769 break;
773 int idx = new_stridx (ptr);
774 if (idx == 0)
775 return 0;
776 si = new_strinfo (ptr, idx, build_int_cst (size_type_node, nonzero_chars),
777 basesi->full_string_p);
778 set_strinfo (idx, si);
779 if (chainsi->next)
781 strinfo *nextsi = unshare_strinfo (get_strinfo (chainsi->next));
782 si->next = nextsi->idx;
783 nextsi->prev = idx;
785 chainsi = unshare_strinfo (chainsi);
786 if (chainsi->first == 0)
787 chainsi->first = chainsi->idx;
788 chainsi->next = idx;
789 if (chainsi->endptr == NULL_TREE && zero_length_string_p (si))
790 chainsi->endptr = ptr;
791 si->endptr = chainsi->endptr;
792 si->prev = chainsi->idx;
793 si->first = chainsi->first;
794 si->writable = chainsi->writable;
795 return si->idx;
798 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
799 to a zero-length string and if possible chain it to a related strinfo
800 chain whose part is or might be CHAINSI. */
802 static strinfo *
803 zero_length_string (tree ptr, strinfo *chainsi)
805 strinfo *si;
806 int idx;
807 if (ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
808 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
809 gcc_checking_assert (TREE_CODE (ptr) == SSA_NAME
810 && ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] == 0);
812 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
813 return NULL;
814 if (chainsi != NULL)
816 si = verify_related_strinfos (chainsi);
817 if (si)
821 /* We shouldn't mix delayed and non-delayed lengths. */
822 gcc_assert (si->full_string_p);
823 if (si->endptr == NULL_TREE)
825 si = unshare_strinfo (si);
826 si->endptr = ptr;
828 chainsi = si;
829 si = get_next_strinfo (si);
831 while (si != NULL);
832 if (zero_length_string_p (chainsi))
834 if (chainsi->next)
836 chainsi = unshare_strinfo (chainsi);
837 chainsi->next = 0;
839 ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = chainsi->idx;
840 return chainsi;
843 else
845 /* We shouldn't mix delayed and non-delayed lengths. */
846 gcc_assert (chainsi->full_string_p);
847 if (chainsi->first || chainsi->prev || chainsi->next)
849 chainsi = unshare_strinfo (chainsi);
850 chainsi->first = 0;
851 chainsi->prev = 0;
852 chainsi->next = 0;
856 idx = new_stridx (ptr);
857 if (idx == 0)
858 return NULL;
859 si = new_strinfo (ptr, idx, build_int_cst (size_type_node, 0), true);
860 set_strinfo (idx, si);
861 si->endptr = ptr;
862 if (chainsi != NULL)
864 chainsi = unshare_strinfo (chainsi);
865 if (chainsi->first == 0)
866 chainsi->first = chainsi->idx;
867 chainsi->next = idx;
868 if (chainsi->endptr == NULL_TREE)
869 chainsi->endptr = ptr;
870 si->prev = chainsi->idx;
871 si->first = chainsi->first;
872 si->writable = chainsi->writable;
874 return si;
877 /* For strinfo ORIGSI whose length has been just updated, adjust other
878 related strinfos so that they match the new ORIGSI. This involves:
880 - adding ADJ to the nonzero_chars fields
881 - copying full_string_p from the new ORIGSI. */
883 static void
884 adjust_related_strinfos (location_t loc, strinfo *origsi, tree adj)
886 strinfo *si = verify_related_strinfos (origsi);
888 if (si == NULL)
889 return;
891 while (1)
893 strinfo *nsi;
895 if (si != origsi)
897 tree tem;
899 si = unshare_strinfo (si);
900 /* We shouldn't see delayed lengths here; the caller must have
901 calculated the old length in order to calculate the
902 adjustment. */
903 gcc_assert (si->nonzero_chars);
904 tem = fold_convert_loc (loc, TREE_TYPE (si->nonzero_chars), adj);
905 si->nonzero_chars = fold_build2_loc (loc, PLUS_EXPR,
906 TREE_TYPE (si->nonzero_chars),
907 si->nonzero_chars, tem);
908 si->full_string_p = origsi->full_string_p;
910 si->endptr = NULL_TREE;
911 si->dont_invalidate = true;
913 nsi = get_next_strinfo (si);
914 if (nsi == NULL)
915 return;
916 si = nsi;
920 /* Find if there are other SSA_NAME pointers equal to PTR
921 for which we don't track their string lengths yet. If so, use
922 IDX for them. */
924 static void
925 find_equal_ptrs (tree ptr, int idx)
927 if (TREE_CODE (ptr) != SSA_NAME)
928 return;
929 while (1)
931 gimple *stmt = SSA_NAME_DEF_STMT (ptr);
932 if (!is_gimple_assign (stmt))
933 return;
934 ptr = gimple_assign_rhs1 (stmt);
935 switch (gimple_assign_rhs_code (stmt))
937 case SSA_NAME:
938 break;
939 CASE_CONVERT:
940 if (!POINTER_TYPE_P (TREE_TYPE (ptr)))
941 return;
942 if (TREE_CODE (ptr) == SSA_NAME)
943 break;
944 if (TREE_CODE (ptr) != ADDR_EXPR)
945 return;
946 /* FALLTHRU */
947 case ADDR_EXPR:
949 int *pidx = addr_stridxptr (TREE_OPERAND (ptr, 0));
950 if (pidx != NULL && *pidx == 0)
951 *pidx = idx;
952 return;
954 default:
955 return;
958 /* We might find an endptr created in this pass. Grow the
959 vector in that case. */
960 if (ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
961 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
963 if (ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] != 0)
964 return;
965 ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = idx;
969 /* Return true if STMT is a call to a builtin function with the right
970 arguments and attributes that should be considered for optimization
971 by this pass. */
973 static bool
974 valid_builtin_call (gimple *stmt)
976 if (!gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
977 return false;
979 tree callee = gimple_call_fndecl (stmt);
980 switch (DECL_FUNCTION_CODE (callee))
982 case BUILT_IN_MEMCMP:
983 case BUILT_IN_MEMCMP_EQ:
984 case BUILT_IN_STRCHR:
985 case BUILT_IN_STRCHR_CHKP:
986 case BUILT_IN_STRLEN:
987 case BUILT_IN_STRLEN_CHKP:
988 /* The above functions should be pure. Punt if they aren't. */
989 if (gimple_vdef (stmt) || gimple_vuse (stmt) == NULL_TREE)
990 return false;
991 break;
993 case BUILT_IN_CALLOC:
994 case BUILT_IN_MALLOC:
995 case BUILT_IN_MEMCPY:
996 case BUILT_IN_MEMCPY_CHK:
997 case BUILT_IN_MEMCPY_CHKP:
998 case BUILT_IN_MEMCPY_CHK_CHKP:
999 case BUILT_IN_MEMPCPY:
1000 case BUILT_IN_MEMPCPY_CHK:
1001 case BUILT_IN_MEMPCPY_CHKP:
1002 case BUILT_IN_MEMPCPY_CHK_CHKP:
1003 case BUILT_IN_MEMSET:
1004 case BUILT_IN_STPCPY:
1005 case BUILT_IN_STPCPY_CHK:
1006 case BUILT_IN_STPCPY_CHKP:
1007 case BUILT_IN_STPCPY_CHK_CHKP:
1008 case BUILT_IN_STRCAT:
1009 case BUILT_IN_STRCAT_CHK:
1010 case BUILT_IN_STRCAT_CHKP:
1011 case BUILT_IN_STRCAT_CHK_CHKP:
1012 case BUILT_IN_STRCPY:
1013 case BUILT_IN_STRCPY_CHK:
1014 case BUILT_IN_STRCPY_CHKP:
1015 case BUILT_IN_STRCPY_CHK_CHKP:
1016 /* The above functions should be neither const nor pure. Punt if they
1017 aren't. */
1018 if (gimple_vdef (stmt) == NULL_TREE || gimple_vuse (stmt) == NULL_TREE)
1019 return false;
1020 break;
1022 default:
1023 break;
1026 return true;
1029 /* If the last .MEM setter statement before STMT is
1030 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
1031 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
1032 just memcpy (x, y, strlen (y)). SI must be the zero length
1033 strinfo. */
1035 static void
1036 adjust_last_stmt (strinfo *si, gimple *stmt, bool is_strcat)
1038 tree vuse, callee, len;
1039 struct laststmt_struct last = laststmt;
1040 strinfo *lastsi, *firstsi;
1041 unsigned len_arg_no = 2;
1043 laststmt.stmt = NULL;
1044 laststmt.len = NULL_TREE;
1045 laststmt.stridx = 0;
1047 if (last.stmt == NULL)
1048 return;
1050 vuse = gimple_vuse (stmt);
1051 if (vuse == NULL_TREE
1052 || SSA_NAME_DEF_STMT (vuse) != last.stmt
1053 || !has_single_use (vuse))
1054 return;
1056 gcc_assert (last.stridx > 0);
1057 lastsi = get_strinfo (last.stridx);
1058 if (lastsi == NULL)
1059 return;
1061 if (lastsi != si)
1063 if (lastsi->first == 0 || lastsi->first != si->first)
1064 return;
1066 firstsi = verify_related_strinfos (si);
1067 if (firstsi == NULL)
1068 return;
1069 while (firstsi != lastsi)
1071 firstsi = get_next_strinfo (firstsi);
1072 if (firstsi == NULL)
1073 return;
1077 if (!is_strcat && !zero_length_string_p (si))
1078 return;
1080 if (is_gimple_assign (last.stmt))
1082 gimple_stmt_iterator gsi;
1084 if (!integer_zerop (gimple_assign_rhs1 (last.stmt)))
1085 return;
1086 if (stmt_could_throw_p (last.stmt))
1087 return;
1088 gsi = gsi_for_stmt (last.stmt);
1089 unlink_stmt_vdef (last.stmt);
1090 release_defs (last.stmt);
1091 gsi_remove (&gsi, true);
1092 return;
1095 if (!valid_builtin_call (last.stmt))
1096 return;
1098 callee = gimple_call_fndecl (last.stmt);
1099 switch (DECL_FUNCTION_CODE (callee))
1101 case BUILT_IN_MEMCPY:
1102 case BUILT_IN_MEMCPY_CHK:
1103 break;
1104 case BUILT_IN_MEMCPY_CHKP:
1105 case BUILT_IN_MEMCPY_CHK_CHKP:
1106 len_arg_no = 4;
1107 break;
1108 default:
1109 return;
1112 len = gimple_call_arg (last.stmt, len_arg_no);
1113 if (tree_fits_uhwi_p (len))
1115 if (!tree_fits_uhwi_p (last.len)
1116 || integer_zerop (len)
1117 || tree_to_uhwi (len) != tree_to_uhwi (last.len) + 1)
1118 return;
1119 /* Don't adjust the length if it is divisible by 4, it is more efficient
1120 to store the extra '\0' in that case. */
1121 if ((tree_to_uhwi (len) & 3) == 0)
1122 return;
1124 else if (TREE_CODE (len) == SSA_NAME)
1126 gimple *def_stmt = SSA_NAME_DEF_STMT (len);
1127 if (!is_gimple_assign (def_stmt)
1128 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
1129 || gimple_assign_rhs1 (def_stmt) != last.len
1130 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
1131 return;
1133 else
1134 return;
1136 gimple_call_set_arg (last.stmt, len_arg_no, last.len);
1137 update_stmt (last.stmt);
1140 /* Handle a strlen call. If strlen of the argument is known, replace
1141 the strlen call with the known value, otherwise remember that strlen
1142 of the argument is stored in the lhs SSA_NAME. */
1144 static void
1145 handle_builtin_strlen (gimple_stmt_iterator *gsi)
1147 int idx;
1148 tree src;
1149 gimple *stmt = gsi_stmt (*gsi);
1150 tree lhs = gimple_call_lhs (stmt);
1152 if (lhs == NULL_TREE)
1153 return;
1155 src = gimple_call_arg (stmt, 0);
1156 idx = get_stridx (src);
1157 if (idx)
1159 strinfo *si = NULL;
1160 tree rhs;
1162 if (idx < 0)
1163 rhs = build_int_cst (TREE_TYPE (lhs), ~idx);
1164 else
1166 rhs = NULL_TREE;
1167 si = get_strinfo (idx);
1168 if (si != NULL)
1169 rhs = get_string_length (si);
1171 if (rhs != NULL_TREE)
1173 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1175 fprintf (dump_file, "Optimizing: ");
1176 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1178 rhs = unshare_expr (rhs);
1179 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
1180 rhs = fold_convert_loc (gimple_location (stmt),
1181 TREE_TYPE (lhs), rhs);
1182 if (!update_call_from_tree (gsi, rhs))
1183 gimplify_and_update_call_from_tree (gsi, rhs);
1184 stmt = gsi_stmt (*gsi);
1185 update_stmt (stmt);
1186 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1188 fprintf (dump_file, "into: ");
1189 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1191 if (si != NULL
1192 && TREE_CODE (si->nonzero_chars) != SSA_NAME
1193 && TREE_CODE (si->nonzero_chars) != INTEGER_CST
1194 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1196 si = unshare_strinfo (si);
1197 si->nonzero_chars = lhs;
1198 gcc_assert (si->full_string_p);
1200 return;
1203 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1204 return;
1205 if (idx == 0)
1206 idx = new_stridx (src);
1207 else
1209 strinfo *si = get_strinfo (idx);
1210 if (si != NULL)
1212 if (!si->full_string_p && !si->stmt)
1214 /* Until now we only had a lower bound on the string length.
1215 Install LHS as the actual length. */
1216 si = unshare_strinfo (si);
1217 tree old = si->nonzero_chars;
1218 si->nonzero_chars = lhs;
1219 si->full_string_p = true;
1220 if (TREE_CODE (old) == INTEGER_CST)
1222 location_t loc = gimple_location (stmt);
1223 old = fold_convert_loc (loc, TREE_TYPE (lhs), old);
1224 tree adj = fold_build2_loc (loc, MINUS_EXPR,
1225 TREE_TYPE (lhs), lhs, old);
1226 adjust_related_strinfos (loc, si, adj);
1228 else
1230 si->first = 0;
1231 si->prev = 0;
1232 si->next = 0;
1235 return;
1238 if (idx)
1240 strinfo *si = new_strinfo (src, idx, lhs, true);
1241 set_strinfo (idx, si);
1242 find_equal_ptrs (src, idx);
1246 /* Handle a strchr call. If strlen of the first argument is known, replace
1247 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
1248 that lhs of the call is endptr and strlen of the argument is endptr - x. */
1250 static void
1251 handle_builtin_strchr (gimple_stmt_iterator *gsi)
1253 int idx;
1254 tree src;
1255 gimple *stmt = gsi_stmt (*gsi);
1256 tree lhs = gimple_call_lhs (stmt);
1257 bool with_bounds = gimple_call_with_bounds_p (stmt);
1259 if (lhs == NULL_TREE)
1260 return;
1262 if (!integer_zerop (gimple_call_arg (stmt, with_bounds ? 2 : 1)))
1263 return;
1265 src = gimple_call_arg (stmt, 0);
1266 idx = get_stridx (src);
1267 if (idx)
1269 strinfo *si = NULL;
1270 tree rhs;
1272 if (idx < 0)
1273 rhs = build_int_cst (size_type_node, ~idx);
1274 else
1276 rhs = NULL_TREE;
1277 si = get_strinfo (idx);
1278 if (si != NULL)
1279 rhs = get_string_length (si);
1281 if (rhs != NULL_TREE)
1283 location_t loc = gimple_location (stmt);
1285 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1287 fprintf (dump_file, "Optimizing: ");
1288 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1290 if (si != NULL && si->endptr != NULL_TREE)
1292 rhs = unshare_expr (si->endptr);
1293 if (!useless_type_conversion_p (TREE_TYPE (lhs),
1294 TREE_TYPE (rhs)))
1295 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
1297 else
1299 rhs = fold_convert_loc (loc, sizetype, unshare_expr (rhs));
1300 rhs = fold_build2_loc (loc, POINTER_PLUS_EXPR,
1301 TREE_TYPE (src), src, rhs);
1302 if (!useless_type_conversion_p (TREE_TYPE (lhs),
1303 TREE_TYPE (rhs)))
1304 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
1306 if (!update_call_from_tree (gsi, rhs))
1307 gimplify_and_update_call_from_tree (gsi, rhs);
1308 stmt = gsi_stmt (*gsi);
1309 update_stmt (stmt);
1310 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1312 fprintf (dump_file, "into: ");
1313 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1315 if (si != NULL
1316 && si->endptr == NULL_TREE
1317 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1319 si = unshare_strinfo (si);
1320 si->endptr = lhs;
1322 zero_length_string (lhs, si);
1323 return;
1326 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1327 return;
1328 if (TREE_CODE (src) != SSA_NAME || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src))
1330 if (idx == 0)
1331 idx = new_stridx (src);
1332 else if (get_strinfo (idx) != NULL)
1334 zero_length_string (lhs, NULL);
1335 return;
1337 if (idx)
1339 location_t loc = gimple_location (stmt);
1340 tree lhsu = fold_convert_loc (loc, size_type_node, lhs);
1341 tree srcu = fold_convert_loc (loc, size_type_node, src);
1342 tree length = fold_build2_loc (loc, MINUS_EXPR,
1343 size_type_node, lhsu, srcu);
1344 strinfo *si = new_strinfo (src, idx, length, true);
1345 si->endptr = lhs;
1346 set_strinfo (idx, si);
1347 find_equal_ptrs (src, idx);
1348 zero_length_string (lhs, si);
1351 else
1352 zero_length_string (lhs, NULL);
1355 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1356 If strlen of the second argument is known, strlen of the first argument
1357 is the same after this call. Furthermore, attempt to convert it to
1358 memcpy. */
1360 static void
1361 handle_builtin_strcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1363 int idx, didx;
1364 tree src, dst, srclen, len, lhs, args, type, fn, oldlen;
1365 bool success;
1366 gimple *stmt = gsi_stmt (*gsi);
1367 strinfo *si, *dsi, *olddsi, *zsi;
1368 location_t loc;
1369 bool with_bounds = gimple_call_with_bounds_p (stmt);
1371 src = gimple_call_arg (stmt, with_bounds ? 2 : 1);
1372 dst = gimple_call_arg (stmt, 0);
1373 lhs = gimple_call_lhs (stmt);
1374 idx = get_stridx (src);
1375 si = NULL;
1376 if (idx > 0)
1377 si = get_strinfo (idx);
1379 didx = get_stridx (dst);
1380 olddsi = NULL;
1381 oldlen = NULL_TREE;
1382 if (didx > 0)
1383 olddsi = get_strinfo (didx);
1384 else if (didx < 0)
1385 return;
1387 if (olddsi != NULL)
1388 adjust_last_stmt (olddsi, stmt, false);
1390 srclen = NULL_TREE;
1391 if (si != NULL)
1392 srclen = get_string_length (si);
1393 else if (idx < 0)
1394 srclen = build_int_cst (size_type_node, ~idx);
1396 loc = gimple_location (stmt);
1397 if (srclen == NULL_TREE)
1398 switch (bcode)
1400 case BUILT_IN_STRCPY:
1401 case BUILT_IN_STRCPY_CHK:
1402 case BUILT_IN_STRCPY_CHKP:
1403 case BUILT_IN_STRCPY_CHK_CHKP:
1404 if (lhs != NULL_TREE || !builtin_decl_implicit_p (BUILT_IN_STPCPY))
1405 return;
1406 break;
1407 case BUILT_IN_STPCPY:
1408 case BUILT_IN_STPCPY_CHK:
1409 case BUILT_IN_STPCPY_CHKP:
1410 case BUILT_IN_STPCPY_CHK_CHKP:
1411 if (lhs == NULL_TREE)
1412 return;
1413 else
1415 tree lhsuint = fold_convert_loc (loc, size_type_node, lhs);
1416 srclen = fold_convert_loc (loc, size_type_node, dst);
1417 srclen = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
1418 lhsuint, srclen);
1420 break;
1421 default:
1422 gcc_unreachable ();
1425 if (didx == 0)
1427 didx = new_stridx (dst);
1428 if (didx == 0)
1429 return;
1431 if (olddsi != NULL)
1433 oldlen = olddsi->nonzero_chars;
1434 dsi = unshare_strinfo (olddsi);
1435 dsi->nonzero_chars = srclen;
1436 dsi->full_string_p = (srclen != NULL_TREE);
1437 /* Break the chain, so adjust_related_strinfo on later pointers in
1438 the chain won't adjust this one anymore. */
1439 dsi->next = 0;
1440 dsi->stmt = NULL;
1441 dsi->endptr = NULL_TREE;
1443 else
1445 dsi = new_strinfo (dst, didx, srclen, srclen != NULL_TREE);
1446 set_strinfo (didx, dsi);
1447 find_equal_ptrs (dst, didx);
1449 dsi->writable = true;
1450 dsi->dont_invalidate = true;
1452 if (dsi->nonzero_chars == NULL_TREE)
1454 strinfo *chainsi;
1456 /* If string length of src is unknown, use delayed length
1457 computation. If string lenth of dst will be needed, it
1458 can be computed by transforming this strcpy call into
1459 stpcpy and subtracting dst from the return value. */
1461 /* Look for earlier strings whose length could be determined if
1462 this strcpy is turned into an stpcpy. */
1464 if (dsi->prev != 0 && (chainsi = verify_related_strinfos (dsi)) != NULL)
1466 for (; chainsi && chainsi != dsi; chainsi = get_strinfo (chainsi->next))
1468 /* When setting a stmt for delayed length computation
1469 prevent all strinfos through dsi from being
1470 invalidated. */
1471 chainsi = unshare_strinfo (chainsi);
1472 chainsi->stmt = stmt;
1473 chainsi->nonzero_chars = NULL_TREE;
1474 chainsi->full_string_p = false;
1475 chainsi->endptr = NULL_TREE;
1476 chainsi->dont_invalidate = true;
1479 dsi->stmt = stmt;
1480 return;
1483 if (olddsi != NULL)
1485 tree adj = NULL_TREE;
1486 if (oldlen == NULL_TREE)
1488 else if (integer_zerop (oldlen))
1489 adj = srclen;
1490 else if (TREE_CODE (oldlen) == INTEGER_CST
1491 || TREE_CODE (srclen) == INTEGER_CST)
1492 adj = fold_build2_loc (loc, MINUS_EXPR,
1493 TREE_TYPE (srclen), srclen,
1494 fold_convert_loc (loc, TREE_TYPE (srclen),
1495 oldlen));
1496 if (adj != NULL_TREE)
1497 adjust_related_strinfos (loc, dsi, adj);
1498 else
1499 dsi->prev = 0;
1501 /* strcpy src may not overlap dst, so src doesn't need to be
1502 invalidated either. */
1503 if (si != NULL)
1504 si->dont_invalidate = true;
1506 fn = NULL_TREE;
1507 zsi = NULL;
1508 switch (bcode)
1510 case BUILT_IN_STRCPY:
1511 case BUILT_IN_STRCPY_CHKP:
1512 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1513 if (lhs)
1514 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
1515 break;
1516 case BUILT_IN_STRCPY_CHK:
1517 case BUILT_IN_STRCPY_CHK_CHKP:
1518 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK);
1519 if (lhs)
1520 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
1521 break;
1522 case BUILT_IN_STPCPY:
1523 case BUILT_IN_STPCPY_CHKP:
1524 /* This would need adjustment of the lhs (subtract one),
1525 or detection that the trailing '\0' doesn't need to be
1526 written, if it will be immediately overwritten.
1527 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1528 if (lhs)
1530 dsi->endptr = lhs;
1531 zsi = zero_length_string (lhs, dsi);
1533 break;
1534 case BUILT_IN_STPCPY_CHK:
1535 case BUILT_IN_STPCPY_CHK_CHKP:
1536 /* This would need adjustment of the lhs (subtract one),
1537 or detection that the trailing '\0' doesn't need to be
1538 written, if it will be immediately overwritten.
1539 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1540 if (lhs)
1542 dsi->endptr = lhs;
1543 zsi = zero_length_string (lhs, dsi);
1545 break;
1546 default:
1547 gcc_unreachable ();
1549 if (zsi != NULL)
1550 zsi->dont_invalidate = true;
1552 if (fn == NULL_TREE)
1553 return;
1555 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1556 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1558 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1559 len = fold_build2_loc (loc, PLUS_EXPR, type, len, build_int_cst (type, 1));
1560 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1561 GSI_SAME_STMT);
1562 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1564 fprintf (dump_file, "Optimizing: ");
1565 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1567 if (with_bounds)
1569 fn = chkp_maybe_create_clone (fn)->decl;
1570 if (gimple_call_num_args (stmt) == 4)
1571 success = update_gimple_call (gsi, fn, 5, dst,
1572 gimple_call_arg (stmt, 1),
1573 src,
1574 gimple_call_arg (stmt, 3),
1575 len);
1576 else
1577 success = update_gimple_call (gsi, fn, 6, dst,
1578 gimple_call_arg (stmt, 1),
1579 src,
1580 gimple_call_arg (stmt, 3),
1581 len,
1582 gimple_call_arg (stmt, 4));
1584 else
1585 if (gimple_call_num_args (stmt) == 2)
1586 success = update_gimple_call (gsi, fn, 3, dst, src, len);
1587 else
1588 success = update_gimple_call (gsi, fn, 4, dst, src, len,
1589 gimple_call_arg (stmt, 2));
1590 if (success)
1592 stmt = gsi_stmt (*gsi);
1593 gimple_call_set_with_bounds (stmt, with_bounds);
1594 update_stmt (stmt);
1595 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1597 fprintf (dump_file, "into: ");
1598 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1600 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1601 laststmt.stmt = stmt;
1602 laststmt.len = srclen;
1603 laststmt.stridx = dsi->idx;
1605 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1606 fprintf (dump_file, "not possible.\n");
1609 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1610 If strlen of the second argument is known and length of the third argument
1611 is that plus one, strlen of the first argument is the same after this
1612 call. */
1614 static void
1615 handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1617 int idx, didx;
1618 tree src, dst, len, lhs, oldlen, newlen;
1619 gimple *stmt = gsi_stmt (*gsi);
1620 strinfo *si, *dsi, *olddsi;
1621 bool with_bounds = gimple_call_with_bounds_p (stmt);
1623 len = gimple_call_arg (stmt, with_bounds ? 4 : 2);
1624 src = gimple_call_arg (stmt, with_bounds ? 2 : 1);
1625 dst = gimple_call_arg (stmt, 0);
1626 idx = get_stridx (src);
1627 if (idx == 0)
1628 return;
1630 didx = get_stridx (dst);
1631 olddsi = NULL;
1632 if (didx > 0)
1633 olddsi = get_strinfo (didx);
1634 else if (didx < 0)
1635 return;
1637 if (olddsi != NULL
1638 && tree_fits_uhwi_p (len)
1639 && !integer_zerop (len))
1640 adjust_last_stmt (olddsi, stmt, false);
1642 bool full_string_p;
1643 if (idx > 0)
1645 gimple *def_stmt;
1647 /* Handle memcpy (x, y, l) where l's relationship with strlen (y)
1648 is known. */
1649 si = get_strinfo (idx);
1650 if (si == NULL || si->nonzero_chars == NULL_TREE)
1651 return;
1652 if (TREE_CODE (len) == INTEGER_CST
1653 && TREE_CODE (si->nonzero_chars) == INTEGER_CST)
1655 if (tree_int_cst_le (len, si->nonzero_chars))
1657 /* Copying LEN nonzero characters, where LEN is constant. */
1658 newlen = len;
1659 full_string_p = false;
1661 else
1663 /* Copying the whole of the analyzed part of SI. */
1664 newlen = si->nonzero_chars;
1665 full_string_p = si->full_string_p;
1668 else
1670 if (!si->full_string_p)
1671 return;
1672 if (TREE_CODE (len) != SSA_NAME)
1673 return;
1674 def_stmt = SSA_NAME_DEF_STMT (len);
1675 if (!is_gimple_assign (def_stmt)
1676 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
1677 || gimple_assign_rhs1 (def_stmt) != si->nonzero_chars
1678 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
1679 return;
1680 /* Copying variable-length string SI (and no more). */
1681 newlen = si->nonzero_chars;
1682 full_string_p = true;
1685 else
1687 si = NULL;
1688 /* Handle memcpy (x, "abcd", 5) or
1689 memcpy (x, "abc\0uvw", 7). */
1690 if (!tree_fits_uhwi_p (len))
1691 return;
1693 unsigned HOST_WIDE_INT clen = tree_to_uhwi (len);
1694 unsigned HOST_WIDE_INT nonzero_chars = ~idx;
1695 newlen = build_int_cst (size_type_node, MIN (nonzero_chars, clen));
1696 full_string_p = clen > nonzero_chars;
1699 if (olddsi != NULL && TREE_CODE (len) == SSA_NAME)
1700 adjust_last_stmt (olddsi, stmt, false);
1702 if (didx == 0)
1704 didx = new_stridx (dst);
1705 if (didx == 0)
1706 return;
1708 oldlen = NULL_TREE;
1709 if (olddsi != NULL)
1711 dsi = unshare_strinfo (olddsi);
1712 oldlen = olddsi->nonzero_chars;
1713 dsi->nonzero_chars = newlen;
1714 dsi->full_string_p = full_string_p;
1715 /* Break the chain, so adjust_related_strinfo on later pointers in
1716 the chain won't adjust this one anymore. */
1717 dsi->next = 0;
1718 dsi->stmt = NULL;
1719 dsi->endptr = NULL_TREE;
1721 else
1723 dsi = new_strinfo (dst, didx, newlen, full_string_p);
1724 set_strinfo (didx, dsi);
1725 find_equal_ptrs (dst, didx);
1727 dsi->writable = true;
1728 dsi->dont_invalidate = true;
1729 if (olddsi != NULL)
1731 tree adj = NULL_TREE;
1732 location_t loc = gimple_location (stmt);
1733 if (oldlen == NULL_TREE)
1735 else if (integer_zerop (oldlen))
1736 adj = newlen;
1737 else if (TREE_CODE (oldlen) == INTEGER_CST
1738 || TREE_CODE (newlen) == INTEGER_CST)
1739 adj = fold_build2_loc (loc, MINUS_EXPR, TREE_TYPE (newlen), newlen,
1740 fold_convert_loc (loc, TREE_TYPE (newlen),
1741 oldlen));
1742 if (adj != NULL_TREE)
1743 adjust_related_strinfos (loc, dsi, adj);
1744 else
1745 dsi->prev = 0;
1747 /* memcpy src may not overlap dst, so src doesn't need to be
1748 invalidated either. */
1749 if (si != NULL)
1750 si->dont_invalidate = true;
1752 if (full_string_p)
1754 lhs = gimple_call_lhs (stmt);
1755 switch (bcode)
1757 case BUILT_IN_MEMCPY:
1758 case BUILT_IN_MEMCPY_CHK:
1759 case BUILT_IN_MEMCPY_CHKP:
1760 case BUILT_IN_MEMCPY_CHK_CHKP:
1761 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1762 laststmt.stmt = stmt;
1763 laststmt.len = dsi->nonzero_chars;
1764 laststmt.stridx = dsi->idx;
1765 if (lhs)
1766 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
1767 break;
1768 case BUILT_IN_MEMPCPY:
1769 case BUILT_IN_MEMPCPY_CHK:
1770 case BUILT_IN_MEMPCPY_CHKP:
1771 case BUILT_IN_MEMPCPY_CHK_CHKP:
1772 break;
1773 default:
1774 gcc_unreachable ();
1779 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
1780 If strlen of the second argument is known, strlen of the first argument
1781 is increased by the length of the second argument. Furthermore, attempt
1782 to convert it to memcpy/strcpy if the length of the first argument
1783 is known. */
1785 static void
1786 handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1788 int idx, didx;
1789 tree src, dst, srclen, dstlen, len, lhs, args, type, fn, objsz, endptr;
1790 bool success;
1791 gimple *stmt = gsi_stmt (*gsi);
1792 strinfo *si, *dsi;
1793 location_t loc;
1794 bool with_bounds = gimple_call_with_bounds_p (stmt);
1796 src = gimple_call_arg (stmt, with_bounds ? 2 : 1);
1797 dst = gimple_call_arg (stmt, 0);
1798 lhs = gimple_call_lhs (stmt);
1800 didx = get_stridx (dst);
1801 if (didx < 0)
1802 return;
1804 dsi = NULL;
1805 if (didx > 0)
1806 dsi = get_strinfo (didx);
1807 if (dsi == NULL || get_string_length (dsi) == NULL_TREE)
1809 /* strcat (p, q) can be transformed into
1810 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
1811 with length endptr - p if we need to compute the length
1812 later on. Don't do this transformation if we don't need
1813 it. */
1814 if (builtin_decl_implicit_p (BUILT_IN_STPCPY) && lhs == NULL_TREE)
1816 if (didx == 0)
1818 didx = new_stridx (dst);
1819 if (didx == 0)
1820 return;
1822 if (dsi == NULL)
1824 dsi = new_strinfo (dst, didx, NULL_TREE, false);
1825 set_strinfo (didx, dsi);
1826 find_equal_ptrs (dst, didx);
1828 else
1830 dsi = unshare_strinfo (dsi);
1831 dsi->nonzero_chars = NULL_TREE;
1832 dsi->full_string_p = false;
1833 dsi->next = 0;
1834 dsi->endptr = NULL_TREE;
1836 dsi->writable = true;
1837 dsi->stmt = stmt;
1838 dsi->dont_invalidate = true;
1840 return;
1843 srclen = NULL_TREE;
1844 si = NULL;
1845 idx = get_stridx (src);
1846 if (idx < 0)
1847 srclen = build_int_cst (size_type_node, ~idx);
1848 else if (idx > 0)
1850 si = get_strinfo (idx);
1851 if (si != NULL)
1852 srclen = get_string_length (si);
1855 loc = gimple_location (stmt);
1856 dstlen = dsi->nonzero_chars;
1857 endptr = dsi->endptr;
1859 dsi = unshare_strinfo (dsi);
1860 dsi->endptr = NULL_TREE;
1861 dsi->stmt = NULL;
1862 dsi->writable = true;
1864 if (srclen != NULL_TREE)
1866 dsi->nonzero_chars = fold_build2_loc (loc, PLUS_EXPR,
1867 TREE_TYPE (dsi->nonzero_chars),
1868 dsi->nonzero_chars, srclen);
1869 gcc_assert (dsi->full_string_p);
1870 adjust_related_strinfos (loc, dsi, srclen);
1871 dsi->dont_invalidate = true;
1873 else
1875 dsi->nonzero_chars = NULL;
1876 dsi->full_string_p = false;
1877 if (lhs == NULL_TREE && builtin_decl_implicit_p (BUILT_IN_STPCPY))
1878 dsi->dont_invalidate = true;
1881 if (si != NULL)
1882 /* strcat src may not overlap dst, so src doesn't need to be
1883 invalidated either. */
1884 si->dont_invalidate = true;
1886 /* For now. Could remove the lhs from the call and add
1887 lhs = dst; afterwards. */
1888 if (lhs)
1889 return;
1891 fn = NULL_TREE;
1892 objsz = NULL_TREE;
1893 switch (bcode)
1895 case BUILT_IN_STRCAT:
1896 case BUILT_IN_STRCAT_CHKP:
1897 if (srclen != NULL_TREE)
1898 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1899 else
1900 fn = builtin_decl_implicit (BUILT_IN_STRCPY);
1901 break;
1902 case BUILT_IN_STRCAT_CHK:
1903 case BUILT_IN_STRCAT_CHK_CHKP:
1904 if (srclen != NULL_TREE)
1905 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK);
1906 else
1907 fn = builtin_decl_explicit (BUILT_IN_STRCPY_CHK);
1908 objsz = gimple_call_arg (stmt, with_bounds ? 4 : 2);
1909 break;
1910 default:
1911 gcc_unreachable ();
1914 if (fn == NULL_TREE)
1915 return;
1917 len = NULL_TREE;
1918 if (srclen != NULL_TREE)
1920 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1921 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1923 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1924 len = fold_build2_loc (loc, PLUS_EXPR, type, len,
1925 build_int_cst (type, 1));
1926 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1927 GSI_SAME_STMT);
1929 if (endptr)
1930 dst = fold_convert_loc (loc, TREE_TYPE (dst), unshare_expr (endptr));
1931 else
1932 dst = fold_build2_loc (loc, POINTER_PLUS_EXPR,
1933 TREE_TYPE (dst), unshare_expr (dst),
1934 fold_convert_loc (loc, sizetype,
1935 unshare_expr (dstlen)));
1936 dst = force_gimple_operand_gsi (gsi, dst, true, NULL_TREE, true,
1937 GSI_SAME_STMT);
1938 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1940 fprintf (dump_file, "Optimizing: ");
1941 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1943 if (with_bounds)
1945 fn = chkp_maybe_create_clone (fn)->decl;
1946 if (srclen != NULL_TREE)
1947 success = update_gimple_call (gsi, fn, 5 + (objsz != NULL_TREE),
1948 dst,
1949 gimple_call_arg (stmt, 1),
1950 src,
1951 gimple_call_arg (stmt, 3),
1952 len, objsz);
1953 else
1954 success = update_gimple_call (gsi, fn, 4 + (objsz != NULL_TREE),
1955 dst,
1956 gimple_call_arg (stmt, 1),
1957 src,
1958 gimple_call_arg (stmt, 3),
1959 objsz);
1961 else
1962 if (srclen != NULL_TREE)
1963 success = update_gimple_call (gsi, fn, 3 + (objsz != NULL_TREE),
1964 dst, src, len, objsz);
1965 else
1966 success = update_gimple_call (gsi, fn, 2 + (objsz != NULL_TREE),
1967 dst, src, objsz);
1968 if (success)
1970 stmt = gsi_stmt (*gsi);
1971 gimple_call_set_with_bounds (stmt, with_bounds);
1972 update_stmt (stmt);
1973 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1975 fprintf (dump_file, "into: ");
1976 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1978 /* If srclen == NULL, note that current string length can be
1979 computed by transforming this strcpy into stpcpy. */
1980 if (srclen == NULL_TREE && dsi->dont_invalidate)
1981 dsi->stmt = stmt;
1982 adjust_last_stmt (dsi, stmt, true);
1983 if (srclen != NULL_TREE)
1985 laststmt.stmt = stmt;
1986 laststmt.len = srclen;
1987 laststmt.stridx = dsi->idx;
1990 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1991 fprintf (dump_file, "not possible.\n");
1994 /* Handle a call to malloc or calloc. */
1996 static void
1997 handle_builtin_malloc (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1999 gimple *stmt = gsi_stmt (*gsi);
2000 tree lhs = gimple_call_lhs (stmt);
2001 if (lhs == NULL_TREE)
2002 return;
2004 gcc_assert (get_stridx (lhs) == 0);
2005 int idx = new_stridx (lhs);
2006 tree length = NULL_TREE;
2007 if (bcode == BUILT_IN_CALLOC)
2008 length = build_int_cst (size_type_node, 0);
2009 strinfo *si = new_strinfo (lhs, idx, length, length != NULL_TREE);
2010 if (bcode == BUILT_IN_CALLOC)
2011 si->endptr = lhs;
2012 set_strinfo (idx, si);
2013 si->writable = true;
2014 si->stmt = stmt;
2015 si->dont_invalidate = true;
2018 /* Handle a call to memset.
2019 After a call to calloc, memset(,0,) is unnecessary.
2020 memset(malloc(n),0,n) is calloc(n,1). */
2022 static bool
2023 handle_builtin_memset (gimple_stmt_iterator *gsi)
2025 gimple *stmt2 = gsi_stmt (*gsi);
2026 if (!integer_zerop (gimple_call_arg (stmt2, 1)))
2027 return true;
2028 tree ptr = gimple_call_arg (stmt2, 0);
2029 int idx1 = get_stridx (ptr);
2030 if (idx1 <= 0)
2031 return true;
2032 strinfo *si1 = get_strinfo (idx1);
2033 if (!si1)
2034 return true;
2035 gimple *stmt1 = si1->stmt;
2036 if (!stmt1 || !is_gimple_call (stmt1))
2037 return true;
2038 tree callee1 = gimple_call_fndecl (stmt1);
2039 if (!valid_builtin_call (stmt1))
2040 return true;
2041 enum built_in_function code1 = DECL_FUNCTION_CODE (callee1);
2042 tree size = gimple_call_arg (stmt2, 2);
2043 if (code1 == BUILT_IN_CALLOC)
2044 /* Not touching stmt1 */ ;
2045 else if (code1 == BUILT_IN_MALLOC
2046 && operand_equal_p (gimple_call_arg (stmt1, 0), size, 0))
2048 gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt1);
2049 update_gimple_call (&gsi1, builtin_decl_implicit (BUILT_IN_CALLOC), 2,
2050 size, build_one_cst (size_type_node));
2051 si1->nonzero_chars = build_int_cst (size_type_node, 0);
2052 si1->full_string_p = true;
2053 si1->stmt = gsi_stmt (gsi1);
2055 else
2056 return true;
2057 tree lhs = gimple_call_lhs (stmt2);
2058 unlink_stmt_vdef (stmt2);
2059 if (lhs)
2061 gimple *assign = gimple_build_assign (lhs, ptr);
2062 gsi_replace (gsi, assign, false);
2064 else
2066 gsi_remove (gsi, true);
2067 release_defs (stmt2);
2070 return false;
2073 /* Handle a call to memcmp. We try to handle small comparisons by
2074 converting them to load and compare, and replacing the call to memcmp
2075 with a __builtin_memcmp_eq call where possible. */
2077 static bool
2078 handle_builtin_memcmp (gimple_stmt_iterator *gsi)
2080 gcall *stmt2 = as_a <gcall *> (gsi_stmt (*gsi));
2081 tree res = gimple_call_lhs (stmt2);
2082 tree arg1 = gimple_call_arg (stmt2, 0);
2083 tree arg2 = gimple_call_arg (stmt2, 1);
2084 tree len = gimple_call_arg (stmt2, 2);
2085 unsigned HOST_WIDE_INT leni;
2086 use_operand_p use_p;
2087 imm_use_iterator iter;
2089 if (!res)
2090 return true;
2092 FOR_EACH_IMM_USE_FAST (use_p, iter, res)
2094 gimple *ustmt = USE_STMT (use_p);
2096 if (is_gimple_debug (ustmt))
2097 continue;
2098 if (gimple_code (ustmt) == GIMPLE_ASSIGN)
2100 gassign *asgn = as_a <gassign *> (ustmt);
2101 tree_code code = gimple_assign_rhs_code (asgn);
2102 if ((code != EQ_EXPR && code != NE_EXPR)
2103 || !integer_zerop (gimple_assign_rhs2 (asgn)))
2104 return true;
2106 else if (gimple_code (ustmt) == GIMPLE_COND)
2108 tree_code code = gimple_cond_code (ustmt);
2109 if ((code != EQ_EXPR && code != NE_EXPR)
2110 || !integer_zerop (gimple_cond_rhs (ustmt)))
2111 return true;
2113 else
2114 return true;
2117 if (tree_fits_uhwi_p (len)
2118 && (leni = tree_to_uhwi (len)) <= GET_MODE_SIZE (word_mode)
2119 && pow2p_hwi (leni))
2121 leni *= CHAR_TYPE_SIZE;
2122 unsigned align1 = get_pointer_alignment (arg1);
2123 unsigned align2 = get_pointer_alignment (arg2);
2124 unsigned align = MIN (align1, align2);
2125 machine_mode mode = mode_for_size (leni, MODE_INT, 1);
2126 if (mode != BLKmode
2127 && (align >= leni || !SLOW_UNALIGNED_ACCESS (mode, align)))
2129 location_t loc = gimple_location (stmt2);
2130 tree type, off;
2131 type = build_nonstandard_integer_type (leni, 1);
2132 gcc_assert (GET_MODE_BITSIZE (TYPE_MODE (type)) == leni);
2133 tree ptrtype = build_pointer_type_for_mode (char_type_node,
2134 ptr_mode, true);
2135 off = build_int_cst (ptrtype, 0);
2136 arg1 = build2_loc (loc, MEM_REF, type, arg1, off);
2137 arg2 = build2_loc (loc, MEM_REF, type, arg2, off);
2138 tree tem1 = fold_const_aggregate_ref (arg1);
2139 if (tem1)
2140 arg1 = tem1;
2141 tree tem2 = fold_const_aggregate_ref (arg2);
2142 if (tem2)
2143 arg2 = tem2;
2144 res = fold_convert_loc (loc, TREE_TYPE (res),
2145 fold_build2_loc (loc, NE_EXPR,
2146 boolean_type_node,
2147 arg1, arg2));
2148 gimplify_and_update_call_from_tree (gsi, res);
2149 return false;
2153 gimple_call_set_fndecl (stmt2, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ));
2154 return false;
2157 /* Handle a POINTER_PLUS_EXPR statement.
2158 For p = "abcd" + 2; compute associated length, or if
2159 p = q + off is pointing to a '\0' character of a string, call
2160 zero_length_string on it. */
2162 static void
2163 handle_pointer_plus (gimple_stmt_iterator *gsi)
2165 gimple *stmt = gsi_stmt (*gsi);
2166 tree lhs = gimple_assign_lhs (stmt), off;
2167 int idx = get_stridx (gimple_assign_rhs1 (stmt));
2168 strinfo *si, *zsi;
2170 if (idx == 0)
2171 return;
2173 if (idx < 0)
2175 tree off = gimple_assign_rhs2 (stmt);
2176 if (tree_fits_uhwi_p (off)
2177 && tree_to_uhwi (off) <= (unsigned HOST_WIDE_INT) ~idx)
2178 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)]
2179 = ~(~idx - (int) tree_to_uhwi (off));
2180 return;
2183 si = get_strinfo (idx);
2184 if (si == NULL || si->nonzero_chars == NULL_TREE)
2185 return;
2187 off = gimple_assign_rhs2 (stmt);
2188 zsi = NULL;
2189 if (si->full_string_p && operand_equal_p (si->nonzero_chars, off, 0))
2190 zsi = zero_length_string (lhs, si);
2191 else if (TREE_CODE (off) == SSA_NAME)
2193 gimple *def_stmt = SSA_NAME_DEF_STMT (off);
2194 if (gimple_assign_single_p (def_stmt)
2195 && si->full_string_p
2196 && operand_equal_p (si->nonzero_chars,
2197 gimple_assign_rhs1 (def_stmt), 0))
2198 zsi = zero_length_string (lhs, si);
2200 if (zsi != NULL
2201 && si->endptr != NULL_TREE
2202 && si->endptr != lhs
2203 && TREE_CODE (si->endptr) == SSA_NAME)
2205 enum tree_code rhs_code
2206 = useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (si->endptr))
2207 ? SSA_NAME : NOP_EXPR;
2208 gimple_assign_set_rhs_with_ops (gsi, rhs_code, si->endptr);
2209 gcc_assert (gsi_stmt (*gsi) == stmt);
2210 update_stmt (stmt);
2214 /* Handle a single character store. */
2216 static bool
2217 handle_char_store (gimple_stmt_iterator *gsi)
2219 int idx = -1;
2220 strinfo *si = NULL;
2221 gimple *stmt = gsi_stmt (*gsi);
2222 tree ssaname = NULL_TREE, lhs = gimple_assign_lhs (stmt);
2223 tree rhs = gimple_assign_rhs1 (stmt);
2224 unsigned HOST_WIDE_INT offset = 0;
2226 if (TREE_CODE (lhs) == MEM_REF
2227 && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME)
2229 tree mem_offset = TREE_OPERAND (lhs, 1);
2230 if (tree_fits_uhwi_p (mem_offset))
2232 /* Get the strinfo for the base, and use it if it starts with at
2233 least OFFSET nonzero characters. This is trivially true if
2234 OFFSET is zero. */
2235 offset = tree_to_uhwi (mem_offset);
2236 idx = get_stridx (TREE_OPERAND (lhs, 0));
2237 if (idx > 0)
2238 si = get_strinfo (idx);
2239 if (offset == 0)
2240 ssaname = TREE_OPERAND (lhs, 0);
2241 else if (si == NULL || compare_nonzero_chars (si, offset) < 0)
2242 return true;
2245 else
2247 idx = get_addr_stridx (lhs, NULL_TREE, &offset);
2248 if (idx > 0)
2249 si = get_strinfo (idx);
2252 bool storing_zero_p = initializer_zerop (rhs);
2253 bool storing_nonzero_p = (!storing_zero_p
2254 && TREE_CODE (rhs) == INTEGER_CST
2255 && integer_nonzerop (rhs));
2257 if (si != NULL)
2259 int cmp = compare_nonzero_chars (si, offset);
2260 gcc_assert (offset == 0 || cmp >= 0);
2261 if (storing_zero_p && cmp == 0 && si->full_string_p)
2263 /* When overwriting a '\0' with a '\0', the store can be removed
2264 if we know it has been stored in the current function. */
2265 if (!stmt_could_throw_p (stmt) && si->writable)
2267 unlink_stmt_vdef (stmt);
2268 release_defs (stmt);
2269 gsi_remove (gsi, true);
2270 return false;
2272 else
2274 si->writable = true;
2275 gsi_next (gsi);
2276 return false;
2279 /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0',
2280 and if we aren't storing '\0', we know that the length of the
2281 string and any other zero terminated string in memory remains
2282 the same. In that case we move to the next gimple statement and
2283 return to signal the caller that it shouldn't invalidate anything.
2285 This is benefical for cases like:
2287 char p[20];
2288 void foo (char *q)
2290 strcpy (p, "foobar");
2291 size_t len = strlen (p); // This can be optimized into 6
2292 size_t len2 = strlen (q); // This has to be computed
2293 p[0] = 'X';
2294 size_t len3 = strlen (p); // This can be optimized into 6
2295 size_t len4 = strlen (q); // This can be optimized into len2
2296 bar (len, len2, len3, len4);
2299 else if (storing_nonzero_p && cmp > 0)
2301 gsi_next (gsi);
2302 return false;
2304 else if (storing_zero_p || storing_nonzero_p || (offset != 0 && cmp > 0))
2306 /* When storing_nonzero_p, we know that the string now starts
2307 with OFFSET + 1 nonzero characters, but don't know whether
2308 there's a following nul terminator.
2310 When storing_zero_p, we know that the string is now OFFSET
2311 characters long.
2313 Otherwise, we're storing an unknown value at offset OFFSET,
2314 so need to clip the nonzero_chars to OFFSET. */
2315 location_t loc = gimple_location (stmt);
2316 tree oldlen = si->nonzero_chars;
2317 if (cmp == 0 && si->full_string_p)
2318 /* We're overwriting the nul terminator with a nonzero or
2319 unknown character. If the previous stmt was a memcpy,
2320 its length may be decreased. */
2321 adjust_last_stmt (si, stmt, false);
2322 si = unshare_strinfo (si);
2323 if (storing_nonzero_p)
2324 si->nonzero_chars = build_int_cst (size_type_node, offset + 1);
2325 else
2326 si->nonzero_chars = build_int_cst (size_type_node, offset);
2327 si->full_string_p = storing_zero_p;
2328 if (storing_zero_p
2329 && ssaname
2330 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname))
2331 si->endptr = ssaname;
2332 else
2333 si->endptr = NULL;
2334 si->next = 0;
2335 si->stmt = NULL;
2336 si->writable = true;
2337 si->dont_invalidate = true;
2338 if (oldlen)
2340 tree adj = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
2341 si->nonzero_chars, oldlen);
2342 adjust_related_strinfos (loc, si, adj);
2344 else
2345 si->prev = 0;
2348 else if (idx == 0 && (storing_zero_p || storing_nonzero_p))
2350 if (ssaname)
2351 idx = new_stridx (ssaname);
2352 else
2353 idx = new_addr_stridx (lhs);
2354 if (idx != 0)
2356 tree ptr = (ssaname ? ssaname : build_fold_addr_expr (lhs));
2357 tree len = storing_nonzero_p ? size_one_node : size_zero_node;
2358 si = new_strinfo (ptr, idx, len, storing_zero_p);
2359 set_strinfo (idx, si);
2360 if (storing_zero_p
2361 && ssaname
2362 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname))
2363 si->endptr = ssaname;
2364 si->dont_invalidate = true;
2365 si->writable = true;
2368 else if (idx == 0
2369 && TREE_CODE (gimple_assign_rhs1 (stmt)) == STRING_CST
2370 && ssaname == NULL_TREE
2371 && TREE_CODE (TREE_TYPE (lhs)) == ARRAY_TYPE)
2373 size_t l = strlen (TREE_STRING_POINTER (gimple_assign_rhs1 (stmt)));
2374 HOST_WIDE_INT a = int_size_in_bytes (TREE_TYPE (lhs));
2375 if (a > 0 && (unsigned HOST_WIDE_INT) a > l)
2377 int idx = new_addr_stridx (lhs);
2378 if (idx != 0)
2380 si = new_strinfo (build_fold_addr_expr (lhs), idx,
2381 build_int_cst (size_type_node, l), true);
2382 set_strinfo (idx, si);
2383 si->dont_invalidate = true;
2388 if (si != NULL && offset == 0 && storing_zero_p)
2390 /* Allow adjust_last_stmt to remove it if the stored '\0'
2391 is immediately overwritten. */
2392 laststmt.stmt = stmt;
2393 laststmt.len = build_int_cst (size_type_node, 1);
2394 laststmt.stridx = si->idx;
2396 return true;
2399 /* Try to fold strstr (s, t) eq/ne s to strncmp (s, t, strlen (t)) eq/ne 0. */
2401 static void
2402 fold_strstr_to_strncmp (tree rhs1, tree rhs2, gimple *stmt)
2404 if (TREE_CODE (rhs1) != SSA_NAME
2405 || TREE_CODE (rhs2) != SSA_NAME)
2406 return;
2408 gimple *call_stmt = NULL;
2409 for (int pass = 0; pass < 2; pass++)
2411 gimple *g = SSA_NAME_DEF_STMT (rhs1);
2412 if (gimple_call_builtin_p (g, BUILT_IN_STRSTR)
2413 && has_single_use (rhs1)
2414 && gimple_call_arg (g, 0) == rhs2)
2416 call_stmt = g;
2417 break;
2419 std::swap (rhs1, rhs2);
2422 if (call_stmt)
2424 tree arg0 = gimple_call_arg (call_stmt, 0);
2426 if (arg0 == rhs2)
2428 tree arg1 = gimple_call_arg (call_stmt, 1);
2429 tree arg1_len = NULL_TREE;
2430 int idx = get_stridx (arg1);
2432 if (idx)
2434 if (idx < 0)
2435 arg1_len = build_int_cst (size_type_node, ~idx);
2436 else
2438 strinfo *si = get_strinfo (idx);
2439 if (si)
2440 arg1_len = get_string_length (si);
2444 if (arg1_len != NULL_TREE)
2446 gimple_stmt_iterator gsi = gsi_for_stmt (call_stmt);
2447 tree strncmp_decl = builtin_decl_explicit (BUILT_IN_STRNCMP);
2448 gcall *strncmp_call = gimple_build_call (strncmp_decl, 3,
2449 arg0, arg1, arg1_len);
2450 tree strncmp_lhs = make_ssa_name (integer_type_node);
2451 gimple_set_vuse (strncmp_call, gimple_vuse (call_stmt));
2452 gimple_call_set_lhs (strncmp_call, strncmp_lhs);
2453 gsi_remove (&gsi, true);
2454 gsi_insert_before (&gsi, strncmp_call, GSI_SAME_STMT);
2455 tree zero = build_zero_cst (TREE_TYPE (strncmp_lhs));
2457 if (is_gimple_assign (stmt))
2459 if (gimple_assign_rhs_code (stmt) == COND_EXPR)
2461 tree cond = gimple_assign_rhs1 (stmt);
2462 TREE_OPERAND (cond, 0) = strncmp_lhs;
2463 TREE_OPERAND (cond, 1) = zero;
2465 else
2467 gimple_assign_set_rhs1 (stmt, strncmp_lhs);
2468 gimple_assign_set_rhs2 (stmt, zero);
2471 else
2473 gcond *cond = as_a<gcond *> (stmt);
2474 gimple_cond_set_lhs (cond, strncmp_lhs);
2475 gimple_cond_set_rhs (cond, zero);
2477 update_stmt (stmt);
2483 /* Attempt to optimize a single statement at *GSI using string length
2484 knowledge. */
2486 static bool
2487 strlen_optimize_stmt (gimple_stmt_iterator *gsi)
2489 gimple *stmt = gsi_stmt (*gsi);
2491 if (is_gimple_call (stmt))
2493 tree callee = gimple_call_fndecl (stmt);
2494 if (valid_builtin_call (stmt))
2495 switch (DECL_FUNCTION_CODE (callee))
2497 case BUILT_IN_STRLEN:
2498 case BUILT_IN_STRLEN_CHKP:
2499 handle_builtin_strlen (gsi);
2500 break;
2501 case BUILT_IN_STRCHR:
2502 case BUILT_IN_STRCHR_CHKP:
2503 handle_builtin_strchr (gsi);
2504 break;
2505 case BUILT_IN_STRCPY:
2506 case BUILT_IN_STRCPY_CHK:
2507 case BUILT_IN_STPCPY:
2508 case BUILT_IN_STPCPY_CHK:
2509 case BUILT_IN_STRCPY_CHKP:
2510 case BUILT_IN_STRCPY_CHK_CHKP:
2511 case BUILT_IN_STPCPY_CHKP:
2512 case BUILT_IN_STPCPY_CHK_CHKP:
2513 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee), gsi);
2514 break;
2515 case BUILT_IN_MEMCPY:
2516 case BUILT_IN_MEMCPY_CHK:
2517 case BUILT_IN_MEMPCPY:
2518 case BUILT_IN_MEMPCPY_CHK:
2519 case BUILT_IN_MEMCPY_CHKP:
2520 case BUILT_IN_MEMCPY_CHK_CHKP:
2521 case BUILT_IN_MEMPCPY_CHKP:
2522 case BUILT_IN_MEMPCPY_CHK_CHKP:
2523 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi);
2524 break;
2525 case BUILT_IN_STRCAT:
2526 case BUILT_IN_STRCAT_CHK:
2527 case BUILT_IN_STRCAT_CHKP:
2528 case BUILT_IN_STRCAT_CHK_CHKP:
2529 handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi);
2530 break;
2531 case BUILT_IN_MALLOC:
2532 case BUILT_IN_CALLOC:
2533 handle_builtin_malloc (DECL_FUNCTION_CODE (callee), gsi);
2534 break;
2535 case BUILT_IN_MEMSET:
2536 if (!handle_builtin_memset (gsi))
2537 return false;
2538 break;
2539 case BUILT_IN_MEMCMP:
2540 if (!handle_builtin_memcmp (gsi))
2541 return false;
2542 break;
2543 default:
2544 break;
2547 else if (is_gimple_assign (stmt) && !gimple_clobber_p (stmt))
2549 tree lhs = gimple_assign_lhs (stmt);
2551 if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs)))
2553 if (gimple_assign_single_p (stmt)
2554 || (gimple_assign_cast_p (stmt)
2555 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))))
2557 int idx = get_stridx (gimple_assign_rhs1 (stmt));
2558 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = idx;
2560 else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
2561 handle_pointer_plus (gsi);
2563 else if (TREE_CODE (lhs) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
2565 enum tree_code code = gimple_assign_rhs_code (stmt);
2566 if (code == COND_EXPR)
2568 tree cond = gimple_assign_rhs1 (stmt);
2569 enum tree_code cond_code = TREE_CODE (cond);
2571 if (cond_code == EQ_EXPR || cond_code == NE_EXPR)
2572 fold_strstr_to_strncmp (TREE_OPERAND (cond, 0),
2573 TREE_OPERAND (cond, 1), stmt);
2575 else if (code == EQ_EXPR || code == NE_EXPR)
2576 fold_strstr_to_strncmp (gimple_assign_rhs1 (stmt),
2577 gimple_assign_rhs2 (stmt), stmt);
2579 else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
2581 tree type = TREE_TYPE (lhs);
2582 if (TREE_CODE (type) == ARRAY_TYPE)
2583 type = TREE_TYPE (type);
2584 if (TREE_CODE (type) == INTEGER_TYPE
2585 && TYPE_MODE (type) == TYPE_MODE (char_type_node)
2586 && TYPE_PRECISION (type) == TYPE_PRECISION (char_type_node))
2588 if (! handle_char_store (gsi))
2589 return false;
2593 else if (gcond *cond = dyn_cast<gcond *> (stmt))
2595 enum tree_code code = gimple_cond_code (cond);
2596 if (code == EQ_EXPR || code == NE_EXPR)
2597 fold_strstr_to_strncmp (gimple_cond_lhs (stmt),
2598 gimple_cond_rhs (stmt), stmt);
2601 if (gimple_vdef (stmt))
2602 maybe_invalidate (stmt);
2603 return true;
2606 /* Recursively call maybe_invalidate on stmts that might be executed
2607 in between dombb and current bb and that contain a vdef. Stop when
2608 *count stmts are inspected, or if the whole strinfo vector has
2609 been invalidated. */
2611 static void
2612 do_invalidate (basic_block dombb, gimple *phi, bitmap visited, int *count)
2614 unsigned int i, n = gimple_phi_num_args (phi);
2616 for (i = 0; i < n; i++)
2618 tree vuse = gimple_phi_arg_def (phi, i);
2619 gimple *stmt = SSA_NAME_DEF_STMT (vuse);
2620 basic_block bb = gimple_bb (stmt);
2621 if (bb == NULL
2622 || bb == dombb
2623 || !bitmap_set_bit (visited, bb->index)
2624 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
2625 continue;
2626 while (1)
2628 if (gimple_code (stmt) == GIMPLE_PHI)
2630 do_invalidate (dombb, stmt, visited, count);
2631 if (*count == 0)
2632 return;
2633 break;
2635 if (--*count == 0)
2636 return;
2637 if (!maybe_invalidate (stmt))
2639 *count = 0;
2640 return;
2642 vuse = gimple_vuse (stmt);
2643 stmt = SSA_NAME_DEF_STMT (vuse);
2644 if (gimple_bb (stmt) != bb)
2646 bb = gimple_bb (stmt);
2647 if (bb == NULL
2648 || bb == dombb
2649 || !bitmap_set_bit (visited, bb->index)
2650 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
2651 break;
2657 class strlen_dom_walker : public dom_walker
2659 public:
2660 strlen_dom_walker (cdi_direction direction) : dom_walker (direction) {}
2662 virtual edge before_dom_children (basic_block);
2663 virtual void after_dom_children (basic_block);
2666 /* Callback for walk_dominator_tree. Attempt to optimize various
2667 string ops by remembering string lengths pointed by pointer SSA_NAMEs. */
2669 edge
2670 strlen_dom_walker::before_dom_children (basic_block bb)
2672 basic_block dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
2674 if (dombb == NULL)
2675 stridx_to_strinfo = NULL;
2676 else
2678 stridx_to_strinfo = ((vec<strinfo *, va_heap, vl_embed> *) dombb->aux);
2679 if (stridx_to_strinfo)
2681 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
2682 gsi_next (&gsi))
2684 gphi *phi = gsi.phi ();
2685 if (virtual_operand_p (gimple_phi_result (phi)))
2687 bitmap visited = BITMAP_ALLOC (NULL);
2688 int count_vdef = 100;
2689 do_invalidate (dombb, phi, visited, &count_vdef);
2690 BITMAP_FREE (visited);
2691 if (count_vdef == 0)
2693 /* If there were too many vdefs in between immediate
2694 dominator and current bb, invalidate everything.
2695 If stridx_to_strinfo has been unshared, we need
2696 to free it, otherwise just set it to NULL. */
2697 if (!strinfo_shared ())
2699 unsigned int i;
2700 strinfo *si;
2702 for (i = 1;
2703 vec_safe_iterate (stridx_to_strinfo, i, &si);
2704 ++i)
2706 free_strinfo (si);
2707 (*stridx_to_strinfo)[i] = NULL;
2710 else
2711 stridx_to_strinfo = NULL;
2713 break;
2719 /* If all PHI arguments have the same string index, the PHI result
2720 has it as well. */
2721 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
2722 gsi_next (&gsi))
2724 gphi *phi = gsi.phi ();
2725 tree result = gimple_phi_result (phi);
2726 if (!virtual_operand_p (result) && POINTER_TYPE_P (TREE_TYPE (result)))
2728 int idx = get_stridx (gimple_phi_arg_def (phi, 0));
2729 if (idx != 0)
2731 unsigned int i, n = gimple_phi_num_args (phi);
2732 for (i = 1; i < n; i++)
2733 if (idx != get_stridx (gimple_phi_arg_def (phi, i)))
2734 break;
2735 if (i == n)
2736 ssa_ver_to_stridx[SSA_NAME_VERSION (result)] = idx;
2741 /* Attempt to optimize individual statements. */
2742 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2743 if (strlen_optimize_stmt (&gsi))
2744 gsi_next (&gsi);
2746 bb->aux = stridx_to_strinfo;
2747 if (vec_safe_length (stridx_to_strinfo) && !strinfo_shared ())
2748 (*stridx_to_strinfo)[0] = (strinfo *) bb;
2749 return NULL;
2752 /* Callback for walk_dominator_tree. Free strinfo vector if it is
2753 owned by the current bb, clear bb->aux. */
2755 void
2756 strlen_dom_walker::after_dom_children (basic_block bb)
2758 if (bb->aux)
2760 stridx_to_strinfo = ((vec<strinfo *, va_heap, vl_embed> *) bb->aux);
2761 if (vec_safe_length (stridx_to_strinfo)
2762 && (*stridx_to_strinfo)[0] == (strinfo *) bb)
2764 unsigned int i;
2765 strinfo *si;
2767 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
2768 free_strinfo (si);
2769 vec_free (stridx_to_strinfo);
2771 bb->aux = NULL;
2775 /* Main entry point. */
2777 namespace {
2779 const pass_data pass_data_strlen =
2781 GIMPLE_PASS, /* type */
2782 "strlen", /* name */
2783 OPTGROUP_NONE, /* optinfo_flags */
2784 TV_TREE_STRLEN, /* tv_id */
2785 ( PROP_cfg | PROP_ssa ), /* properties_required */
2786 0, /* properties_provided */
2787 0, /* properties_destroyed */
2788 0, /* todo_flags_start */
2789 0, /* todo_flags_finish */
2792 class pass_strlen : public gimple_opt_pass
2794 public:
2795 pass_strlen (gcc::context *ctxt)
2796 : gimple_opt_pass (pass_data_strlen, ctxt)
2799 /* opt_pass methods: */
2800 virtual bool gate (function *) { return flag_optimize_strlen != 0; }
2801 virtual unsigned int execute (function *);
2803 }; // class pass_strlen
2805 unsigned int
2806 pass_strlen::execute (function *fun)
2808 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
2809 max_stridx = 1;
2811 calculate_dominance_info (CDI_DOMINATORS);
2813 /* String length optimization is implemented as a walk of the dominator
2814 tree and a forward walk of statements within each block. */
2815 strlen_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr);
2817 ssa_ver_to_stridx.release ();
2818 strinfo_pool.release ();
2819 if (decl_to_stridxlist_htab)
2821 obstack_free (&stridx_obstack, NULL);
2822 delete decl_to_stridxlist_htab;
2823 decl_to_stridxlist_htab = NULL;
2825 laststmt.stmt = NULL;
2826 laststmt.len = NULL_TREE;
2827 laststmt.stridx = 0;
2829 return 0;
2832 } // anon namespace
2834 gimple_opt_pass *
2835 make_pass_strlen (gcc::context *ctxt)
2837 return new pass_strlen (ctxt);