missing Changelog
[official-gcc.git] / gcc / tree-ssa-strlen.c
blobaa8b3d69164fa8c55b1a2915a232c7c1cd507fcb
1 /* String length optimization
2 Copyright (C) 2011 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 "tree-flow.h"
25 #include "tree-pass.h"
26 #include "domwalk.h"
27 #include "alloc-pool.h"
28 #include "tree-ssa-propagate.h"
29 #include "gimple-pretty-print.h"
30 #include "params.h"
31 #include "expr.h"
33 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
34 is an index into strinfo vector, negative value stands for
35 string length of a string literal (~strlen). */
36 static vec<int> ssa_ver_to_stridx;
38 /* Number of currently active string indexes plus one. */
39 static int max_stridx;
41 /* String information record. */
42 typedef struct strinfo_struct
44 /* String length of this string. */
45 tree length;
46 /* Any of the corresponding pointers for querying alias oracle. */
47 tree ptr;
48 /* Statement for delayed length computation. */
49 gimple stmt;
50 /* Pointer to '\0' if known, if NULL, it can be computed as
51 ptr + length. */
52 tree endptr;
53 /* Reference count. Any changes to strinfo entry possibly shared
54 with dominating basic blocks need unshare_strinfo first, except
55 for dont_invalidate which affects only the immediately next
56 maybe_invalidate. */
57 int refcount;
58 /* Copy of index. get_strinfo (si->idx) should return si; */
59 int idx;
60 /* These 3 fields are for chaining related string pointers together.
61 E.g. for
62 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
63 strcpy (c, d); e = c + dl;
64 strinfo(a) -> strinfo(c) -> strinfo(e)
65 All have ->first field equal to strinfo(a)->idx and are doubly
66 chained through prev/next fields. The later strinfos are required
67 to point into the same string with zero or more bytes after
68 the previous pointer and all bytes in between the two pointers
69 must be non-zero. Functions like strcpy or memcpy are supposed
70 to adjust all previous strinfo lengths, but not following strinfo
71 lengths (those are uncertain, usually invalidated during
72 maybe_invalidate, except when the alias oracle knows better).
73 Functions like strcat on the other side adjust the whole
74 related strinfo chain.
75 They are updated lazily, so to use the chain the same first fields
76 and si->prev->next == si->idx needs to be verified. */
77 int first;
78 int next;
79 int prev;
80 /* A flag whether the string is known to be written in the current
81 function. */
82 bool writable;
83 /* A flag for the next maybe_invalidate that this strinfo shouldn't
84 be invalidated. Always cleared by maybe_invalidate. */
85 bool dont_invalidate;
86 } *strinfo;
88 /* Pool for allocating strinfo_struct entries. */
89 static alloc_pool strinfo_pool;
91 /* Vector mapping positive string indexes to strinfo, for the
92 current basic block. The first pointer in the vector is special,
93 it is either NULL, meaning the vector isn't shared, or it is
94 a basic block pointer to the owner basic_block if shared.
95 If some other bb wants to modify the vector, the vector needs
96 to be unshared first, and only the owner bb is supposed to free it. */
97 static vec<strinfo, va_heap, vl_embed> *stridx_to_strinfo;
99 /* One OFFSET->IDX mapping. */
100 struct stridxlist
102 struct stridxlist *next;
103 HOST_WIDE_INT offset;
104 int idx;
107 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
108 struct decl_stridxlist_map
110 struct tree_map_base base;
111 struct stridxlist list;
114 /* Hash table for mapping decls to a chained list of offset -> idx
115 mappings. */
116 static htab_t decl_to_stridxlist_htab;
118 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
119 static struct obstack stridx_obstack;
121 /* Last memcpy statement if it could be adjusted if the trailing
122 '\0' written is immediately overwritten, or
123 *x = '\0' store that could be removed if it is immediately overwritten. */
124 struct laststmt_struct
126 gimple stmt;
127 tree len;
128 int stridx;
129 } laststmt;
131 /* Hash a from tree in a decl_stridxlist_map. */
133 static unsigned int
134 decl_to_stridxlist_hash (const void *item)
136 return DECL_UID (((const struct decl_stridxlist_map *) item)->base.from);
139 /* Helper function for get_stridx. */
141 static int
142 get_addr_stridx (tree exp)
144 HOST_WIDE_INT off;
145 struct decl_stridxlist_map ent, *e;
146 struct stridxlist *list;
147 tree base;
149 if (decl_to_stridxlist_htab == NULL)
150 return 0;
152 base = get_addr_base_and_unit_offset (exp, &off);
153 if (base == NULL || !DECL_P (base))
154 return 0;
156 ent.base.from = base;
157 e = (struct decl_stridxlist_map *)
158 htab_find_with_hash (decl_to_stridxlist_htab, &ent, DECL_UID (base));
159 if (e == NULL)
160 return 0;
162 list = &e->list;
165 if (list->offset == off)
166 return list->idx;
167 list = list->next;
169 while (list);
170 return 0;
173 /* Return string index for EXP. */
175 static int
176 get_stridx (tree exp)
178 tree s, o;
180 if (TREE_CODE (exp) == SSA_NAME)
181 return ssa_ver_to_stridx[SSA_NAME_VERSION (exp)];
183 if (TREE_CODE (exp) == ADDR_EXPR)
185 int idx = get_addr_stridx (TREE_OPERAND (exp, 0));
186 if (idx != 0)
187 return idx;
190 s = string_constant (exp, &o);
191 if (s != NULL_TREE
192 && (o == NULL_TREE || host_integerp (o, 0))
193 && TREE_STRING_LENGTH (s) > 0)
195 HOST_WIDE_INT offset = o ? tree_low_cst (o, 0) : 0;
196 const char *p = TREE_STRING_POINTER (s);
197 int max = TREE_STRING_LENGTH (s) - 1;
199 if (p[max] == '\0' && offset >= 0 && offset <= max)
200 return ~(int) strlen (p + offset);
202 return 0;
205 /* Return true if strinfo vector is shared with the immediate dominator. */
207 static inline bool
208 strinfo_shared (void)
210 return vec_safe_length (stridx_to_strinfo)
211 && (*stridx_to_strinfo)[0] != NULL;
214 /* Unshare strinfo vector that is shared with the immediate dominator. */
216 static void
217 unshare_strinfo_vec (void)
219 strinfo si;
220 unsigned int i = 0;
222 gcc_assert (strinfo_shared ());
223 stridx_to_strinfo = vec_safe_copy (stridx_to_strinfo);
224 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
225 if (si != NULL)
226 si->refcount++;
227 (*stridx_to_strinfo)[0] = NULL;
230 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
231 Return a pointer to the location where the string index can
232 be stored (if 0) or is stored, or NULL if this can't be tracked. */
234 static int *
235 addr_stridxptr (tree exp)
237 void **slot;
238 struct decl_stridxlist_map ent;
239 struct stridxlist *list;
240 HOST_WIDE_INT off;
242 tree base = get_addr_base_and_unit_offset (exp, &off);
243 if (base == NULL_TREE || !DECL_P (base))
244 return NULL;
246 if (decl_to_stridxlist_htab == NULL)
248 decl_to_stridxlist_htab
249 = htab_create (64, decl_to_stridxlist_hash, tree_map_base_eq, NULL);
250 gcc_obstack_init (&stridx_obstack);
252 ent.base.from = base;
253 slot = htab_find_slot_with_hash (decl_to_stridxlist_htab, &ent,
254 DECL_UID (base), INSERT);
255 if (*slot)
257 int i;
258 list = &((struct decl_stridxlist_map *)*slot)->list;
259 for (i = 0; i < 16; i++)
261 if (list->offset == off)
262 return &list->idx;
263 if (list->next == NULL)
264 break;
266 if (i == 16)
267 return NULL;
268 list->next = XOBNEW (&stridx_obstack, struct stridxlist);
269 list = list->next;
271 else
273 struct decl_stridxlist_map *e
274 = XOBNEW (&stridx_obstack, struct decl_stridxlist_map);
275 e->base.from = base;
276 *slot = (void *) e;
277 list = &e->list;
279 list->next = NULL;
280 list->offset = off;
281 list->idx = 0;
282 return &list->idx;
285 /* Create a new string index, or return 0 if reached limit. */
287 static int
288 new_stridx (tree exp)
290 int idx;
291 if (max_stridx >= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS))
292 return 0;
293 if (TREE_CODE (exp) == SSA_NAME)
295 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp))
296 return 0;
297 idx = max_stridx++;
298 ssa_ver_to_stridx[SSA_NAME_VERSION (exp)] = idx;
299 return idx;
301 if (TREE_CODE (exp) == ADDR_EXPR)
303 int *pidx = addr_stridxptr (TREE_OPERAND (exp, 0));
304 if (pidx != NULL)
306 gcc_assert (*pidx == 0);
307 *pidx = max_stridx++;
308 return *pidx;
311 return 0;
314 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
316 static int
317 new_addr_stridx (tree exp)
319 int *pidx;
320 if (max_stridx >= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS))
321 return 0;
322 pidx = addr_stridxptr (exp);
323 if (pidx != NULL)
325 gcc_assert (*pidx == 0);
326 *pidx = max_stridx++;
327 return *pidx;
329 return 0;
332 /* Create a new strinfo. */
334 static strinfo
335 new_strinfo (tree ptr, int idx, tree length)
337 strinfo si = (strinfo) pool_alloc (strinfo_pool);
338 si->length = length;
339 si->ptr = ptr;
340 si->stmt = NULL;
341 si->endptr = NULL_TREE;
342 si->refcount = 1;
343 si->idx = idx;
344 si->first = 0;
345 si->prev = 0;
346 si->next = 0;
347 si->writable = false;
348 si->dont_invalidate = false;
349 return si;
352 /* Decrease strinfo refcount and free it if not referenced anymore. */
354 static inline void
355 free_strinfo (strinfo si)
357 if (si && --si->refcount == 0)
358 pool_free (strinfo_pool, si);
361 /* Return strinfo vector entry IDX. */
363 static inline strinfo
364 get_strinfo (int idx)
366 if (vec_safe_length (stridx_to_strinfo) <= (unsigned int) idx)
367 return NULL;
368 return (*stridx_to_strinfo)[idx];
371 /* Set strinfo in the vector entry IDX to SI. */
373 static inline void
374 set_strinfo (int idx, strinfo si)
376 if (vec_safe_length (stridx_to_strinfo) && (*stridx_to_strinfo)[0])
377 unshare_strinfo_vec ();
378 if (vec_safe_length (stridx_to_strinfo) <= (unsigned int) idx)
379 vec_safe_grow_cleared (stridx_to_strinfo, idx + 1);
380 (*stridx_to_strinfo)[idx] = si;
383 /* Return string length, or NULL if it can't be computed. */
385 static tree
386 get_string_length (strinfo si)
388 if (si->length)
389 return si->length;
391 if (si->stmt)
393 gimple stmt = si->stmt, lenstmt;
394 tree callee, lhs, fn, tem;
395 location_t loc;
396 gimple_stmt_iterator gsi;
398 gcc_assert (is_gimple_call (stmt));
399 callee = gimple_call_fndecl (stmt);
400 gcc_assert (callee && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL);
401 lhs = gimple_call_lhs (stmt);
402 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY));
403 /* unshare_strinfo is intentionally not called here. The (delayed)
404 transformation of strcpy or strcat into stpcpy is done at the place
405 of the former strcpy/strcat call and so can affect all the strinfos
406 with the same stmt. If they were unshared before and transformation
407 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
408 just compute the right length. */
409 switch (DECL_FUNCTION_CODE (callee))
411 case BUILT_IN_STRCAT:
412 case BUILT_IN_STRCAT_CHK:
413 gsi = gsi_for_stmt (stmt);
414 fn = builtin_decl_implicit (BUILT_IN_STRLEN);
415 gcc_assert (lhs == NULL_TREE);
416 tem = unshare_expr (gimple_call_arg (stmt, 0));
417 lenstmt = gimple_build_call (fn, 1, tem);
418 lhs = make_ssa_name (TREE_TYPE (TREE_TYPE (fn)), lenstmt);
419 gimple_call_set_lhs (lenstmt, lhs);
420 gimple_set_vuse (lenstmt, gimple_vuse (stmt));
421 gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT);
422 tem = gimple_call_arg (stmt, 0);
423 if (!ptrofftype_p (TREE_TYPE (lhs)))
425 lhs = convert_to_ptrofftype (lhs);
426 lhs = force_gimple_operand_gsi (&gsi, lhs, true, NULL_TREE,
427 true, GSI_SAME_STMT);
429 lenstmt
430 = gimple_build_assign_with_ops
431 (POINTER_PLUS_EXPR,
432 make_ssa_name (TREE_TYPE (gimple_call_arg (stmt, 0)), NULL),
433 tem, lhs);
434 gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT);
435 gimple_call_set_arg (stmt, 0, gimple_assign_lhs (lenstmt));
436 lhs = NULL_TREE;
437 /* FALLTHRU */
438 case BUILT_IN_STRCPY:
439 case BUILT_IN_STRCPY_CHK:
440 if (gimple_call_num_args (stmt) == 2)
441 fn = builtin_decl_implicit (BUILT_IN_STPCPY);
442 else
443 fn = builtin_decl_explicit (BUILT_IN_STPCPY_CHK);
444 gcc_assert (lhs == NULL_TREE);
445 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
447 fprintf (dump_file, "Optimizing: ");
448 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
450 gimple_call_set_fndecl (stmt, fn);
451 lhs = make_ssa_name (TREE_TYPE (TREE_TYPE (fn)), stmt);
452 gimple_call_set_lhs (stmt, lhs);
453 update_stmt (stmt);
454 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
456 fprintf (dump_file, "into: ");
457 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
459 /* FALLTHRU */
460 case BUILT_IN_STPCPY:
461 case BUILT_IN_STPCPY_CHK:
462 gcc_assert (lhs != NULL_TREE);
463 loc = gimple_location (stmt);
464 si->endptr = lhs;
465 si->stmt = NULL;
466 lhs = fold_convert_loc (loc, size_type_node, lhs);
467 si->length = fold_convert_loc (loc, size_type_node, si->ptr);
468 si->length = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
469 lhs, si->length);
470 break;
471 default:
472 gcc_unreachable ();
473 break;
477 return si->length;
480 /* Invalidate string length information for strings whose length
481 might change due to stores in stmt. */
483 static bool
484 maybe_invalidate (gimple stmt)
486 strinfo si;
487 unsigned int i;
488 bool nonempty = false;
490 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
491 if (si != NULL)
493 if (!si->dont_invalidate)
495 ao_ref r;
496 ao_ref_init_from_ptr_and_size (&r, si->ptr, NULL_TREE);
497 if (stmt_may_clobber_ref_p_1 (stmt, &r))
499 set_strinfo (i, NULL);
500 free_strinfo (si);
501 continue;
504 si->dont_invalidate = false;
505 nonempty = true;
507 return nonempty;
510 /* Unshare strinfo record SI, if it has recount > 1 or
511 if stridx_to_strinfo vector is shared with some other
512 bbs. */
514 static strinfo
515 unshare_strinfo (strinfo si)
517 strinfo nsi;
519 if (si->refcount == 1 && !strinfo_shared ())
520 return si;
522 nsi = new_strinfo (si->ptr, si->idx, si->length);
523 nsi->stmt = si->stmt;
524 nsi->endptr = si->endptr;
525 nsi->first = si->first;
526 nsi->prev = si->prev;
527 nsi->next = si->next;
528 nsi->writable = si->writable;
529 set_strinfo (si->idx, nsi);
530 free_strinfo (si);
531 return nsi;
534 /* Return first strinfo in the related strinfo chain
535 if all strinfos in between belong to the chain, otherwise
536 NULL. */
538 static strinfo
539 verify_related_strinfos (strinfo origsi)
541 strinfo si = origsi, psi;
543 if (origsi->first == 0)
544 return NULL;
545 for (; si->prev; si = psi)
547 if (si->first != origsi->first)
548 return NULL;
549 psi = get_strinfo (si->prev);
550 if (psi == NULL)
551 return NULL;
552 if (psi->next != si->idx)
553 return NULL;
555 if (si->idx != si->first)
556 return NULL;
557 return si;
560 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
561 to a zero-length string and if possible chain it to a related strinfo
562 chain whose part is or might be CHAINSI. */
564 static strinfo
565 zero_length_string (tree ptr, strinfo chainsi)
567 strinfo si;
568 int idx;
569 gcc_checking_assert (TREE_CODE (ptr) == SSA_NAME
570 && get_stridx (ptr) == 0);
572 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
573 return NULL;
574 if (chainsi != NULL)
576 si = verify_related_strinfos (chainsi);
577 if (si)
579 chainsi = si;
580 for (; chainsi->next; chainsi = si)
582 if (chainsi->endptr == NULL_TREE)
584 chainsi = unshare_strinfo (chainsi);
585 chainsi->endptr = ptr;
587 si = get_strinfo (chainsi->next);
588 if (si == NULL
589 || si->first != chainsi->first
590 || si->prev != chainsi->idx)
591 break;
593 gcc_assert (chainsi->length || chainsi->stmt);
594 if (chainsi->endptr == NULL_TREE)
596 chainsi = unshare_strinfo (chainsi);
597 chainsi->endptr = ptr;
599 if (chainsi->length && integer_zerop (chainsi->length))
601 if (chainsi->next)
603 chainsi = unshare_strinfo (chainsi);
604 chainsi->next = 0;
606 ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = chainsi->idx;
607 return chainsi;
610 else if (chainsi->first || chainsi->prev || chainsi->next)
612 chainsi = unshare_strinfo (chainsi);
613 chainsi->first = 0;
614 chainsi->prev = 0;
615 chainsi->next = 0;
618 idx = new_stridx (ptr);
619 if (idx == 0)
620 return NULL;
621 si = new_strinfo (ptr, idx, build_int_cst (size_type_node, 0));
622 set_strinfo (idx, si);
623 si->endptr = ptr;
624 if (chainsi != NULL)
626 chainsi = unshare_strinfo (chainsi);
627 if (chainsi->first == 0)
628 chainsi->first = chainsi->idx;
629 chainsi->next = idx;
630 if (chainsi->endptr == NULL_TREE)
631 chainsi->endptr = ptr;
632 si->prev = chainsi->idx;
633 si->first = chainsi->first;
634 si->writable = chainsi->writable;
636 return si;
639 /* For strinfo ORIGSI whose length has been just updated
640 update also related strinfo lengths (add ADJ to each,
641 but don't adjust ORIGSI). */
643 static void
644 adjust_related_strinfos (location_t loc, strinfo origsi, tree adj)
646 strinfo si = verify_related_strinfos (origsi);
648 if (si == NULL)
649 return;
651 while (1)
653 strinfo nsi;
655 if (si != origsi)
657 tree tem;
659 si = unshare_strinfo (si);
660 if (si->length)
662 tem = fold_convert_loc (loc, TREE_TYPE (si->length), adj);
663 si->length = fold_build2_loc (loc, PLUS_EXPR,
664 TREE_TYPE (si->length), si->length,
665 tem);
667 else if (si->stmt != NULL)
668 /* Delayed length computation is unaffected. */
670 else
671 gcc_unreachable ();
673 si->endptr = NULL_TREE;
674 si->dont_invalidate = true;
676 if (si->next == 0)
677 return;
678 nsi = get_strinfo (si->next);
679 if (nsi == NULL
680 || nsi->first != si->first
681 || nsi->prev != si->idx)
682 return;
683 si = nsi;
687 /* Find if there are other SSA_NAME pointers equal to PTR
688 for which we don't track their string lengths yet. If so, use
689 IDX for them. */
691 static void
692 find_equal_ptrs (tree ptr, int idx)
694 if (TREE_CODE (ptr) != SSA_NAME)
695 return;
696 while (1)
698 gimple stmt = SSA_NAME_DEF_STMT (ptr);
699 if (!is_gimple_assign (stmt))
700 return;
701 ptr = gimple_assign_rhs1 (stmt);
702 switch (gimple_assign_rhs_code (stmt))
704 case SSA_NAME:
705 break;
706 CASE_CONVERT:
707 if (!POINTER_TYPE_P (TREE_TYPE (ptr)))
708 return;
709 if (TREE_CODE (ptr) == SSA_NAME)
710 break;
711 if (TREE_CODE (ptr) != ADDR_EXPR)
712 return;
713 /* FALLTHRU */
714 case ADDR_EXPR:
716 int *pidx = addr_stridxptr (TREE_OPERAND (ptr, 0));
717 if (pidx != NULL && *pidx == 0)
718 *pidx = idx;
719 return;
721 default:
722 return;
725 /* We might find an endptr created in this pass. Grow the
726 vector in that case. */
727 if (ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
728 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
730 if (ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] != 0)
731 return;
732 ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = idx;
736 /* If the last .MEM setter statement before STMT is
737 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
738 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
739 just memcpy (x, y, strlen (y)). SI must be the zero length
740 strinfo. */
742 static void
743 adjust_last_stmt (strinfo si, gimple stmt, bool is_strcat)
745 tree vuse, callee, len;
746 struct laststmt_struct last = laststmt;
747 strinfo lastsi, firstsi;
749 laststmt.stmt = NULL;
750 laststmt.len = NULL_TREE;
751 laststmt.stridx = 0;
753 if (last.stmt == NULL)
754 return;
756 vuse = gimple_vuse (stmt);
757 if (vuse == NULL_TREE
758 || SSA_NAME_DEF_STMT (vuse) != last.stmt
759 || !has_single_use (vuse))
760 return;
762 gcc_assert (last.stridx > 0);
763 lastsi = get_strinfo (last.stridx);
764 if (lastsi == NULL)
765 return;
767 if (lastsi != si)
769 if (lastsi->first == 0 || lastsi->first != si->first)
770 return;
772 firstsi = verify_related_strinfos (si);
773 if (firstsi == NULL)
774 return;
775 while (firstsi != lastsi)
777 strinfo nextsi;
778 if (firstsi->next == 0)
779 return;
780 nextsi = get_strinfo (firstsi->next);
781 if (nextsi == NULL
782 || nextsi->prev != firstsi->idx
783 || nextsi->first != si->first)
784 return;
785 firstsi = nextsi;
789 if (!is_strcat)
791 if (si->length == NULL_TREE || !integer_zerop (si->length))
792 return;
795 if (is_gimple_assign (last.stmt))
797 gimple_stmt_iterator gsi;
799 if (!integer_zerop (gimple_assign_rhs1 (last.stmt)))
800 return;
801 if (stmt_could_throw_p (last.stmt))
802 return;
803 gsi = gsi_for_stmt (last.stmt);
804 unlink_stmt_vdef (last.stmt);
805 release_defs (last.stmt);
806 gsi_remove (&gsi, true);
807 return;
810 if (!is_gimple_call (last.stmt))
811 return;
812 callee = gimple_call_fndecl (last.stmt);
813 if (callee == NULL_TREE || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
814 return;
816 switch (DECL_FUNCTION_CODE (callee))
818 case BUILT_IN_MEMCPY:
819 case BUILT_IN_MEMCPY_CHK:
820 break;
821 default:
822 return;
825 len = gimple_call_arg (last.stmt, 2);
826 if (host_integerp (len, 1))
828 if (!host_integerp (last.len, 1)
829 || integer_zerop (len)
830 || (unsigned HOST_WIDE_INT) tree_low_cst (len, 1)
831 != (unsigned HOST_WIDE_INT) tree_low_cst (last.len, 1) + 1)
832 return;
833 /* Don't adjust the length if it is divisible by 4, it is more efficient
834 to store the extra '\0' in that case. */
835 if ((((unsigned HOST_WIDE_INT) tree_low_cst (len, 1)) & 3) == 0)
836 return;
838 else if (TREE_CODE (len) == SSA_NAME)
840 gimple def_stmt = SSA_NAME_DEF_STMT (len);
841 if (!is_gimple_assign (def_stmt)
842 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
843 || gimple_assign_rhs1 (def_stmt) != last.len
844 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
845 return;
847 else
848 return;
850 gimple_call_set_arg (last.stmt, 2, last.len);
851 update_stmt (last.stmt);
854 /* Handle a strlen call. If strlen of the argument is known, replace
855 the strlen call with the known value, otherwise remember that strlen
856 of the argument is stored in the lhs SSA_NAME. */
858 static void
859 handle_builtin_strlen (gimple_stmt_iterator *gsi)
861 int idx;
862 tree src;
863 gimple stmt = gsi_stmt (*gsi);
864 tree lhs = gimple_call_lhs (stmt);
866 if (lhs == NULL_TREE)
867 return;
869 src = gimple_call_arg (stmt, 0);
870 idx = get_stridx (src);
871 if (idx)
873 strinfo si = NULL;
874 tree rhs;
876 if (idx < 0)
877 rhs = build_int_cst (TREE_TYPE (lhs), ~idx);
878 else
880 rhs = NULL_TREE;
881 si = get_strinfo (idx);
882 if (si != NULL)
883 rhs = get_string_length (si);
885 if (rhs != NULL_TREE)
887 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
889 fprintf (dump_file, "Optimizing: ");
890 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
892 rhs = unshare_expr (rhs);
893 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
894 rhs = fold_convert_loc (gimple_location (stmt),
895 TREE_TYPE (lhs), rhs);
896 if (!update_call_from_tree (gsi, rhs))
897 gimplify_and_update_call_from_tree (gsi, rhs);
898 stmt = gsi_stmt (*gsi);
899 update_stmt (stmt);
900 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
902 fprintf (dump_file, "into: ");
903 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
905 if (si != NULL
906 && TREE_CODE (si->length) != SSA_NAME
907 && TREE_CODE (si->length) != INTEGER_CST
908 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
910 si = unshare_strinfo (si);
911 si->length = lhs;
913 return;
916 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
917 return;
918 if (idx == 0)
919 idx = new_stridx (src);
920 else if (get_strinfo (idx) != NULL)
921 return;
922 if (idx)
924 strinfo si = new_strinfo (src, idx, lhs);
925 set_strinfo (idx, si);
926 find_equal_ptrs (src, idx);
930 /* Handle a strchr call. If strlen of the first argument is known, replace
931 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
932 that lhs of the call is endptr and strlen of the argument is endptr - x. */
934 static void
935 handle_builtin_strchr (gimple_stmt_iterator *gsi)
937 int idx;
938 tree src;
939 gimple stmt = gsi_stmt (*gsi);
940 tree lhs = gimple_call_lhs (stmt);
942 if (lhs == NULL_TREE)
943 return;
945 if (!integer_zerop (gimple_call_arg (stmt, 1)))
946 return;
948 src = gimple_call_arg (stmt, 0);
949 idx = get_stridx (src);
950 if (idx)
952 strinfo si = NULL;
953 tree rhs;
955 if (idx < 0)
956 rhs = build_int_cst (size_type_node, ~idx);
957 else
959 rhs = NULL_TREE;
960 si = get_strinfo (idx);
961 if (si != NULL)
962 rhs = get_string_length (si);
964 if (rhs != NULL_TREE)
966 location_t loc = gimple_location (stmt);
968 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
970 fprintf (dump_file, "Optimizing: ");
971 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
973 if (si != NULL && si->endptr != NULL_TREE)
975 rhs = unshare_expr (si->endptr);
976 if (!useless_type_conversion_p (TREE_TYPE (lhs),
977 TREE_TYPE (rhs)))
978 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
980 else
982 rhs = fold_convert_loc (loc, sizetype, unshare_expr (rhs));
983 rhs = fold_build2_loc (loc, POINTER_PLUS_EXPR,
984 TREE_TYPE (src), src, rhs);
985 if (!useless_type_conversion_p (TREE_TYPE (lhs),
986 TREE_TYPE (rhs)))
987 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
989 if (!update_call_from_tree (gsi, rhs))
990 gimplify_and_update_call_from_tree (gsi, rhs);
991 stmt = gsi_stmt (*gsi);
992 update_stmt (stmt);
993 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
995 fprintf (dump_file, "into: ");
996 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
998 if (si != NULL
999 && si->endptr == NULL_TREE
1000 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1002 si = unshare_strinfo (si);
1003 si->endptr = lhs;
1005 zero_length_string (lhs, si);
1006 return;
1009 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1010 return;
1011 if (TREE_CODE (src) != SSA_NAME || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src))
1013 if (idx == 0)
1014 idx = new_stridx (src);
1015 else if (get_strinfo (idx) != NULL)
1017 zero_length_string (lhs, NULL);
1018 return;
1020 if (idx)
1022 location_t loc = gimple_location (stmt);
1023 tree lhsu = fold_convert_loc (loc, size_type_node, lhs);
1024 tree srcu = fold_convert_loc (loc, size_type_node, src);
1025 tree length = fold_build2_loc (loc, MINUS_EXPR,
1026 size_type_node, lhsu, srcu);
1027 strinfo si = new_strinfo (src, idx, length);
1028 si->endptr = lhs;
1029 set_strinfo (idx, si);
1030 find_equal_ptrs (src, idx);
1031 zero_length_string (lhs, si);
1034 else
1035 zero_length_string (lhs, NULL);
1038 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1039 If strlen of the second argument is known, strlen of the first argument
1040 is the same after this call. Furthermore, attempt to convert it to
1041 memcpy. */
1043 static void
1044 handle_builtin_strcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1046 int idx, didx;
1047 tree src, dst, srclen, len, lhs, args, type, fn, oldlen;
1048 bool success;
1049 gimple stmt = gsi_stmt (*gsi);
1050 strinfo si, dsi, olddsi, zsi;
1051 location_t loc;
1053 src = gimple_call_arg (stmt, 1);
1054 dst = gimple_call_arg (stmt, 0);
1055 lhs = gimple_call_lhs (stmt);
1056 idx = get_stridx (src);
1057 si = NULL;
1058 if (idx > 0)
1059 si = get_strinfo (idx);
1061 didx = get_stridx (dst);
1062 olddsi = NULL;
1063 oldlen = NULL_TREE;
1064 if (didx > 0)
1065 olddsi = get_strinfo (didx);
1066 else if (didx < 0)
1067 return;
1069 if (olddsi != NULL)
1070 adjust_last_stmt (olddsi, stmt, false);
1072 srclen = NULL_TREE;
1073 if (si != NULL)
1074 srclen = get_string_length (si);
1075 else if (idx < 0)
1076 srclen = build_int_cst (size_type_node, ~idx);
1078 loc = gimple_location (stmt);
1079 if (srclen == NULL_TREE)
1080 switch (bcode)
1082 case BUILT_IN_STRCPY:
1083 case BUILT_IN_STRCPY_CHK:
1084 if (lhs != NULL_TREE || !builtin_decl_implicit_p (BUILT_IN_STPCPY))
1085 return;
1086 break;
1087 case BUILT_IN_STPCPY:
1088 case BUILT_IN_STPCPY_CHK:
1089 if (lhs == NULL_TREE)
1090 return;
1091 else
1093 tree lhsuint = fold_convert_loc (loc, size_type_node, lhs);
1094 srclen = fold_convert_loc (loc, size_type_node, dst);
1095 srclen = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
1096 lhsuint, srclen);
1098 break;
1099 default:
1100 gcc_unreachable ();
1103 if (didx == 0)
1105 didx = new_stridx (dst);
1106 if (didx == 0)
1107 return;
1109 if (olddsi != NULL)
1111 oldlen = olddsi->length;
1112 dsi = unshare_strinfo (olddsi);
1113 dsi->length = srclen;
1114 /* Break the chain, so adjust_related_strinfo on later pointers in
1115 the chain won't adjust this one anymore. */
1116 dsi->next = 0;
1117 dsi->stmt = NULL;
1118 dsi->endptr = NULL_TREE;
1120 else
1122 dsi = new_strinfo (dst, didx, srclen);
1123 set_strinfo (didx, dsi);
1124 find_equal_ptrs (dst, didx);
1126 dsi->writable = true;
1127 dsi->dont_invalidate = true;
1129 if (dsi->length == NULL_TREE)
1131 strinfo chainsi;
1133 /* If string length of src is unknown, use delayed length
1134 computation. If string lenth of dst will be needed, it
1135 can be computed by transforming this strcpy call into
1136 stpcpy and subtracting dst from the return value. */
1138 /* Look for earlier strings whose length could be determined if
1139 this strcpy is turned into an stpcpy. */
1141 if (dsi->prev != 0 && (chainsi = verify_related_strinfos (dsi)) != NULL)
1143 for (; chainsi && chainsi != dsi; chainsi = get_strinfo (chainsi->next))
1145 /* When setting a stmt for delayed length computation
1146 prevent all strinfos through dsi from being
1147 invalidated. */
1148 chainsi = unshare_strinfo (chainsi);
1149 chainsi->stmt = stmt;
1150 chainsi->length = NULL_TREE;
1151 chainsi->endptr = NULL_TREE;
1152 chainsi->dont_invalidate = true;
1155 dsi->stmt = stmt;
1156 return;
1159 if (olddsi != NULL)
1161 tree adj = NULL_TREE;
1162 if (oldlen == NULL_TREE)
1164 else if (integer_zerop (oldlen))
1165 adj = srclen;
1166 else if (TREE_CODE (oldlen) == INTEGER_CST
1167 || TREE_CODE (srclen) == INTEGER_CST)
1168 adj = fold_build2_loc (loc, MINUS_EXPR,
1169 TREE_TYPE (srclen), srclen,
1170 fold_convert_loc (loc, TREE_TYPE (srclen),
1171 oldlen));
1172 if (adj != NULL_TREE)
1173 adjust_related_strinfos (loc, dsi, adj);
1174 else
1175 dsi->prev = 0;
1177 /* strcpy src may not overlap dst, so src doesn't need to be
1178 invalidated either. */
1179 if (si != NULL)
1180 si->dont_invalidate = true;
1182 fn = NULL_TREE;
1183 zsi = NULL;
1184 switch (bcode)
1186 case BUILT_IN_STRCPY:
1187 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1188 if (lhs)
1189 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
1190 break;
1191 case BUILT_IN_STRCPY_CHK:
1192 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK);
1193 if (lhs)
1194 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
1195 break;
1196 case BUILT_IN_STPCPY:
1197 /* This would need adjustment of the lhs (subtract one),
1198 or detection that the trailing '\0' doesn't need to be
1199 written, if it will be immediately overwritten.
1200 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1201 if (lhs)
1203 dsi->endptr = lhs;
1204 zsi = zero_length_string (lhs, dsi);
1206 break;
1207 case BUILT_IN_STPCPY_CHK:
1208 /* This would need adjustment of the lhs (subtract one),
1209 or detection that the trailing '\0' doesn't need to be
1210 written, if it will be immediately overwritten.
1211 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1212 if (lhs)
1214 dsi->endptr = lhs;
1215 zsi = zero_length_string (lhs, dsi);
1217 break;
1218 default:
1219 gcc_unreachable ();
1221 if (zsi != NULL)
1222 zsi->dont_invalidate = true;
1224 if (fn == NULL_TREE)
1225 return;
1227 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1228 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1230 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1231 len = fold_build2_loc (loc, PLUS_EXPR, type, len, build_int_cst (type, 1));
1232 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1233 GSI_SAME_STMT);
1234 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1236 fprintf (dump_file, "Optimizing: ");
1237 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1239 if (gimple_call_num_args (stmt) == 2)
1240 success = update_gimple_call (gsi, fn, 3, dst, src, len);
1241 else
1242 success = update_gimple_call (gsi, fn, 4, dst, src, len,
1243 gimple_call_arg (stmt, 2));
1244 if (success)
1246 stmt = gsi_stmt (*gsi);
1247 update_stmt (stmt);
1248 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1250 fprintf (dump_file, "into: ");
1251 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1253 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1254 laststmt.stmt = stmt;
1255 laststmt.len = srclen;
1256 laststmt.stridx = dsi->idx;
1258 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1259 fprintf (dump_file, "not possible.\n");
1262 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1263 If strlen of the second argument is known and length of the third argument
1264 is that plus one, strlen of the first argument is the same after this
1265 call. */
1267 static void
1268 handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1270 int idx, didx;
1271 tree src, dst, len, lhs, oldlen, newlen;
1272 gimple stmt = gsi_stmt (*gsi);
1273 strinfo si, dsi, olddsi;
1275 len = gimple_call_arg (stmt, 2);
1276 src = gimple_call_arg (stmt, 1);
1277 dst = gimple_call_arg (stmt, 0);
1278 idx = get_stridx (src);
1279 if (idx == 0)
1280 return;
1282 didx = get_stridx (dst);
1283 olddsi = NULL;
1284 if (didx > 0)
1285 olddsi = get_strinfo (didx);
1286 else if (didx < 0)
1287 return;
1289 if (olddsi != NULL
1290 && host_integerp (len, 1)
1291 && !integer_zerop (len))
1292 adjust_last_stmt (olddsi, stmt, false);
1294 if (idx > 0)
1296 gimple def_stmt;
1298 /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */
1299 si = get_strinfo (idx);
1300 if (si == NULL || si->length == NULL_TREE)
1301 return;
1302 if (TREE_CODE (len) != SSA_NAME)
1303 return;
1304 def_stmt = SSA_NAME_DEF_STMT (len);
1305 if (!is_gimple_assign (def_stmt)
1306 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
1307 || gimple_assign_rhs1 (def_stmt) != si->length
1308 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
1309 return;
1311 else
1313 si = NULL;
1314 /* Handle memcpy (x, "abcd", 5) or
1315 memcpy (x, "abc\0uvw", 7). */
1316 if (!host_integerp (len, 1)
1317 || (unsigned HOST_WIDE_INT) tree_low_cst (len, 1)
1318 <= (unsigned HOST_WIDE_INT) ~idx)
1319 return;
1322 if (olddsi != NULL && TREE_CODE (len) == SSA_NAME)
1323 adjust_last_stmt (olddsi, stmt, false);
1325 if (didx == 0)
1327 didx = new_stridx (dst);
1328 if (didx == 0)
1329 return;
1331 if (si != NULL)
1332 newlen = si->length;
1333 else
1334 newlen = build_int_cst (size_type_node, ~idx);
1335 oldlen = NULL_TREE;
1336 if (olddsi != NULL)
1338 dsi = unshare_strinfo (olddsi);
1339 oldlen = olddsi->length;
1340 dsi->length = newlen;
1341 /* Break the chain, so adjust_related_strinfo on later pointers in
1342 the chain won't adjust this one anymore. */
1343 dsi->next = 0;
1344 dsi->stmt = NULL;
1345 dsi->endptr = NULL_TREE;
1347 else
1349 dsi = new_strinfo (dst, didx, newlen);
1350 set_strinfo (didx, dsi);
1351 find_equal_ptrs (dst, didx);
1353 dsi->writable = true;
1354 dsi->dont_invalidate = true;
1355 if (olddsi != NULL)
1357 tree adj = NULL_TREE;
1358 location_t loc = gimple_location (stmt);
1359 if (oldlen == NULL_TREE)
1361 else if (integer_zerop (oldlen))
1362 adj = dsi->length;
1363 else if (TREE_CODE (oldlen) == INTEGER_CST
1364 || TREE_CODE (dsi->length) == INTEGER_CST)
1365 adj = fold_build2_loc (loc, MINUS_EXPR,
1366 TREE_TYPE (dsi->length), dsi->length,
1367 fold_convert_loc (loc, TREE_TYPE (dsi->length),
1368 oldlen));
1369 if (adj != NULL_TREE)
1370 adjust_related_strinfos (loc, dsi, adj);
1371 else
1372 dsi->prev = 0;
1374 /* memcpy src may not overlap dst, so src doesn't need to be
1375 invalidated either. */
1376 if (si != NULL)
1377 si->dont_invalidate = true;
1379 lhs = gimple_call_lhs (stmt);
1380 switch (bcode)
1382 case BUILT_IN_MEMCPY:
1383 case BUILT_IN_MEMCPY_CHK:
1384 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1385 laststmt.stmt = stmt;
1386 laststmt.len = dsi->length;
1387 laststmt.stridx = dsi->idx;
1388 if (lhs)
1389 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
1390 break;
1391 case BUILT_IN_MEMPCPY:
1392 case BUILT_IN_MEMPCPY_CHK:
1393 break;
1394 default:
1395 gcc_unreachable ();
1399 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
1400 If strlen of the second argument is known, strlen of the first argument
1401 is increased by the length of the second argument. Furthermore, attempt
1402 to convert it to memcpy/strcpy if the length of the first argument
1403 is known. */
1405 static void
1406 handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1408 int idx, didx;
1409 tree src, dst, srclen, dstlen, len, lhs, args, type, fn, objsz, endptr;
1410 bool success;
1411 gimple stmt = gsi_stmt (*gsi);
1412 strinfo si, dsi;
1413 location_t loc;
1415 src = gimple_call_arg (stmt, 1);
1416 dst = gimple_call_arg (stmt, 0);
1417 lhs = gimple_call_lhs (stmt);
1419 didx = get_stridx (dst);
1420 if (didx < 0)
1421 return;
1423 dsi = NULL;
1424 if (didx > 0)
1425 dsi = get_strinfo (didx);
1426 if (dsi == NULL || get_string_length (dsi) == NULL_TREE)
1428 /* strcat (p, q) can be transformed into
1429 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
1430 with length endptr - p if we need to compute the length
1431 later on. Don't do this transformation if we don't need
1432 it. */
1433 if (builtin_decl_implicit_p (BUILT_IN_STPCPY) && lhs == NULL_TREE)
1435 if (didx == 0)
1437 didx = new_stridx (dst);
1438 if (didx == 0)
1439 return;
1441 if (dsi == NULL)
1443 dsi = new_strinfo (dst, didx, NULL_TREE);
1444 set_strinfo (didx, dsi);
1445 find_equal_ptrs (dst, didx);
1447 else
1449 dsi = unshare_strinfo (dsi);
1450 dsi->length = NULL_TREE;
1451 dsi->next = 0;
1452 dsi->endptr = NULL_TREE;
1454 dsi->writable = true;
1455 dsi->stmt = stmt;
1456 dsi->dont_invalidate = true;
1458 return;
1461 srclen = NULL_TREE;
1462 si = NULL;
1463 idx = get_stridx (src);
1464 if (idx < 0)
1465 srclen = build_int_cst (size_type_node, ~idx);
1466 else if (idx > 0)
1468 si = get_strinfo (idx);
1469 if (si != NULL)
1470 srclen = get_string_length (si);
1473 loc = gimple_location (stmt);
1474 dstlen = dsi->length;
1475 endptr = dsi->endptr;
1477 dsi = unshare_strinfo (dsi);
1478 dsi->endptr = NULL_TREE;
1479 dsi->stmt = NULL;
1480 dsi->writable = true;
1482 if (srclen != NULL_TREE)
1484 dsi->length = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (dsi->length),
1485 dsi->length, srclen);
1486 adjust_related_strinfos (loc, dsi, srclen);
1487 dsi->dont_invalidate = true;
1489 else
1491 dsi->length = NULL;
1492 if (lhs == NULL_TREE && builtin_decl_implicit_p (BUILT_IN_STPCPY))
1493 dsi->dont_invalidate = true;
1496 if (si != NULL)
1497 /* strcat src may not overlap dst, so src doesn't need to be
1498 invalidated either. */
1499 si->dont_invalidate = true;
1501 /* For now. Could remove the lhs from the call and add
1502 lhs = dst; afterwards. */
1503 if (lhs)
1504 return;
1506 fn = NULL_TREE;
1507 objsz = NULL_TREE;
1508 switch (bcode)
1510 case BUILT_IN_STRCAT:
1511 if (srclen != NULL_TREE)
1512 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1513 else
1514 fn = builtin_decl_implicit (BUILT_IN_STRCPY);
1515 break;
1516 case BUILT_IN_STRCAT_CHK:
1517 if (srclen != NULL_TREE)
1518 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK);
1519 else
1520 fn = builtin_decl_explicit (BUILT_IN_STRCPY_CHK);
1521 objsz = gimple_call_arg (stmt, 2);
1522 break;
1523 default:
1524 gcc_unreachable ();
1527 if (fn == NULL_TREE)
1528 return;
1530 len = NULL_TREE;
1531 if (srclen != NULL_TREE)
1533 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1534 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1536 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1537 len = fold_build2_loc (loc, PLUS_EXPR, type, len,
1538 build_int_cst (type, 1));
1539 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1540 GSI_SAME_STMT);
1542 if (endptr)
1543 dst = fold_convert_loc (loc, TREE_TYPE (dst), unshare_expr (endptr));
1544 else
1545 dst = fold_build2_loc (loc, POINTER_PLUS_EXPR,
1546 TREE_TYPE (dst), unshare_expr (dst),
1547 fold_convert_loc (loc, sizetype,
1548 unshare_expr (dstlen)));
1549 dst = force_gimple_operand_gsi (gsi, dst, true, NULL_TREE, true,
1550 GSI_SAME_STMT);
1551 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1553 fprintf (dump_file, "Optimizing: ");
1554 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1556 if (srclen != NULL_TREE)
1557 success = update_gimple_call (gsi, fn, 3 + (objsz != NULL_TREE),
1558 dst, src, len, objsz);
1559 else
1560 success = update_gimple_call (gsi, fn, 2 + (objsz != NULL_TREE),
1561 dst, src, objsz);
1562 if (success)
1564 stmt = gsi_stmt (*gsi);
1565 update_stmt (stmt);
1566 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1568 fprintf (dump_file, "into: ");
1569 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1571 /* If srclen == NULL, note that current string length can be
1572 computed by transforming this strcpy into stpcpy. */
1573 if (srclen == NULL_TREE && dsi->dont_invalidate)
1574 dsi->stmt = stmt;
1575 adjust_last_stmt (dsi, stmt, true);
1576 if (srclen != NULL_TREE)
1578 laststmt.stmt = stmt;
1579 laststmt.len = srclen;
1580 laststmt.stridx = dsi->idx;
1583 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1584 fprintf (dump_file, "not possible.\n");
1587 /* Handle a POINTER_PLUS_EXPR statement.
1588 For p = "abcd" + 2; compute associated length, or if
1589 p = q + off is pointing to a '\0' character of a string, call
1590 zero_length_string on it. */
1592 static void
1593 handle_pointer_plus (gimple_stmt_iterator *gsi)
1595 gimple stmt = gsi_stmt (*gsi);
1596 tree lhs = gimple_assign_lhs (stmt), off;
1597 int idx = get_stridx (gimple_assign_rhs1 (stmt));
1598 strinfo si, zsi;
1600 if (idx == 0)
1601 return;
1603 if (idx < 0)
1605 tree off = gimple_assign_rhs2 (stmt);
1606 if (host_integerp (off, 1)
1607 && (unsigned HOST_WIDE_INT) tree_low_cst (off, 1)
1608 <= (unsigned HOST_WIDE_INT) ~idx)
1609 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)]
1610 = ~(~idx - (int) tree_low_cst (off, 1));
1611 return;
1614 si = get_strinfo (idx);
1615 if (si == NULL || si->length == NULL_TREE)
1616 return;
1618 off = gimple_assign_rhs2 (stmt);
1619 zsi = NULL;
1620 if (operand_equal_p (si->length, off, 0))
1621 zsi = zero_length_string (lhs, si);
1622 else if (TREE_CODE (off) == SSA_NAME)
1624 gimple def_stmt = SSA_NAME_DEF_STMT (off);
1625 if (gimple_assign_single_p (def_stmt)
1626 && operand_equal_p (si->length, gimple_assign_rhs1 (def_stmt), 0))
1627 zsi = zero_length_string (lhs, si);
1629 if (zsi != NULL
1630 && si->endptr != NULL_TREE
1631 && si->endptr != lhs
1632 && TREE_CODE (si->endptr) == SSA_NAME)
1634 enum tree_code rhs_code
1635 = useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (si->endptr))
1636 ? SSA_NAME : NOP_EXPR;
1637 gimple_assign_set_rhs_with_ops (gsi, rhs_code, si->endptr, NULL_TREE);
1638 gcc_assert (gsi_stmt (*gsi) == stmt);
1639 update_stmt (stmt);
1643 /* Handle a single character store. */
1645 static bool
1646 handle_char_store (gimple_stmt_iterator *gsi)
1648 int idx = -1;
1649 strinfo si = NULL;
1650 gimple stmt = gsi_stmt (*gsi);
1651 tree ssaname = NULL_TREE, lhs = gimple_assign_lhs (stmt);
1653 if (TREE_CODE (lhs) == MEM_REF
1654 && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME)
1656 if (integer_zerop (TREE_OPERAND (lhs, 1)))
1658 ssaname = TREE_OPERAND (lhs, 0);
1659 idx = get_stridx (ssaname);
1662 else
1663 idx = get_addr_stridx (lhs);
1665 if (idx > 0)
1667 si = get_strinfo (idx);
1668 if (si != NULL && si->length != NULL_TREE && integer_zerop (si->length))
1670 if (initializer_zerop (gimple_assign_rhs1 (stmt)))
1672 /* When storing '\0', the store can be removed
1673 if we know it has been stored in the current function. */
1674 if (!stmt_could_throw_p (stmt) && si->writable)
1676 unlink_stmt_vdef (stmt);
1677 release_defs (stmt);
1678 gsi_remove (gsi, true);
1679 return false;
1681 else
1683 si->writable = true;
1684 si->dont_invalidate = true;
1687 else
1688 /* Otherwise this statement overwrites the '\0' with
1689 something, if the previous stmt was a memcpy,
1690 its length may be decreased. */
1691 adjust_last_stmt (si, stmt, false);
1693 else if (si != NULL)
1695 si = unshare_strinfo (si);
1696 si->length = build_int_cst (size_type_node, 0);
1697 si->endptr = NULL;
1698 si->prev = 0;
1699 si->next = 0;
1700 si->stmt = NULL;
1701 si->first = 0;
1702 si->writable = true;
1703 if (ssaname && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname))
1704 si->endptr = ssaname;
1705 si->dont_invalidate = true;
1708 else if (idx == 0 && initializer_zerop (gimple_assign_rhs1 (stmt)))
1710 if (ssaname)
1712 si = zero_length_string (ssaname, NULL);
1713 if (si != NULL)
1714 si->dont_invalidate = true;
1716 else
1718 int idx = new_addr_stridx (lhs);
1719 if (idx != 0)
1721 si = new_strinfo (build_fold_addr_expr (lhs), idx,
1722 build_int_cst (size_type_node, 0));
1723 set_strinfo (idx, si);
1724 si->dont_invalidate = true;
1727 if (si != NULL)
1728 si->writable = true;
1731 if (si != NULL && initializer_zerop (gimple_assign_rhs1 (stmt)))
1733 /* Allow adjust_last_stmt to remove it if the stored '\0'
1734 is immediately overwritten. */
1735 laststmt.stmt = stmt;
1736 laststmt.len = build_int_cst (size_type_node, 1);
1737 laststmt.stridx = si->idx;
1739 return true;
1742 /* Attempt to optimize a single statement at *GSI using string length
1743 knowledge. */
1745 static bool
1746 strlen_optimize_stmt (gimple_stmt_iterator *gsi)
1748 gimple stmt = gsi_stmt (*gsi);
1750 if (is_gimple_call (stmt))
1752 tree callee = gimple_call_fndecl (stmt);
1753 if (callee && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
1754 switch (DECL_FUNCTION_CODE (callee))
1756 case BUILT_IN_STRLEN:
1757 handle_builtin_strlen (gsi);
1758 break;
1759 case BUILT_IN_STRCHR:
1760 handle_builtin_strchr (gsi);
1761 break;
1762 case BUILT_IN_STRCPY:
1763 case BUILT_IN_STRCPY_CHK:
1764 case BUILT_IN_STPCPY:
1765 case BUILT_IN_STPCPY_CHK:
1766 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee), gsi);
1767 break;
1768 case BUILT_IN_MEMCPY:
1769 case BUILT_IN_MEMCPY_CHK:
1770 case BUILT_IN_MEMPCPY:
1771 case BUILT_IN_MEMPCPY_CHK:
1772 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi);
1773 break;
1774 case BUILT_IN_STRCAT:
1775 case BUILT_IN_STRCAT_CHK:
1776 handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi);
1777 break;
1778 default:
1779 break;
1782 else if (is_gimple_assign (stmt))
1784 tree lhs = gimple_assign_lhs (stmt);
1786 if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs)))
1788 if (gimple_assign_single_p (stmt)
1789 || (gimple_assign_cast_p (stmt)
1790 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))))
1792 int idx = get_stridx (gimple_assign_rhs1 (stmt));
1793 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = idx;
1795 else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
1796 handle_pointer_plus (gsi);
1798 else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
1800 tree type = TREE_TYPE (lhs);
1801 if (TREE_CODE (type) == ARRAY_TYPE)
1802 type = TREE_TYPE (type);
1803 if (TREE_CODE (type) == INTEGER_TYPE
1804 && TYPE_MODE (type) == TYPE_MODE (char_type_node)
1805 && TYPE_PRECISION (type) == TYPE_PRECISION (char_type_node))
1807 if (! handle_char_store (gsi))
1808 return false;
1813 if (gimple_vdef (stmt))
1814 maybe_invalidate (stmt);
1815 return true;
1818 /* Recursively call maybe_invalidate on stmts that might be executed
1819 in between dombb and current bb and that contain a vdef. Stop when
1820 *count stmts are inspected, or if the whole strinfo vector has
1821 been invalidated. */
1823 static void
1824 do_invalidate (basic_block dombb, gimple phi, bitmap visited, int *count)
1826 unsigned int i, n = gimple_phi_num_args (phi);
1828 for (i = 0; i < n; i++)
1830 tree vuse = gimple_phi_arg_def (phi, i);
1831 gimple stmt = SSA_NAME_DEF_STMT (vuse);
1832 basic_block bb = gimple_bb (stmt);
1833 if (bb == NULL
1834 || bb == dombb
1835 || !bitmap_set_bit (visited, bb->index)
1836 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
1837 continue;
1838 while (1)
1840 if (gimple_code (stmt) == GIMPLE_PHI)
1842 do_invalidate (dombb, stmt, visited, count);
1843 if (*count == 0)
1844 return;
1845 break;
1847 if (--*count == 0)
1848 return;
1849 if (!maybe_invalidate (stmt))
1851 *count = 0;
1852 return;
1854 vuse = gimple_vuse (stmt);
1855 stmt = SSA_NAME_DEF_STMT (vuse);
1856 if (gimple_bb (stmt) != bb)
1858 bb = gimple_bb (stmt);
1859 if (bb == NULL
1860 || bb == dombb
1861 || !bitmap_set_bit (visited, bb->index)
1862 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
1863 break;
1869 /* Callback for walk_dominator_tree. Attempt to optimize various
1870 string ops by remembering string lenths pointed by pointer SSA_NAMEs. */
1872 static void
1873 strlen_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1874 basic_block bb)
1876 gimple_stmt_iterator gsi;
1877 basic_block dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
1879 if (dombb == NULL)
1880 stridx_to_strinfo = NULL;
1881 else
1883 stridx_to_strinfo = ((vec<strinfo, va_heap, vl_embed> *) dombb->aux);
1884 if (stridx_to_strinfo)
1886 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1888 gimple phi = gsi_stmt (gsi);
1889 if (virtual_operand_p (gimple_phi_result (phi)))
1891 bitmap visited = BITMAP_ALLOC (NULL);
1892 int count_vdef = 100;
1893 do_invalidate (dombb, phi, visited, &count_vdef);
1894 BITMAP_FREE (visited);
1895 break;
1901 /* If all PHI arguments have the same string index, the PHI result
1902 has it as well. */
1903 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1905 gimple phi = gsi_stmt (gsi);
1906 tree result = gimple_phi_result (phi);
1907 if (!virtual_operand_p (result) && POINTER_TYPE_P (TREE_TYPE (result)))
1909 int idx = get_stridx (gimple_phi_arg_def (phi, 0));
1910 if (idx != 0)
1912 unsigned int i, n = gimple_phi_num_args (phi);
1913 for (i = 1; i < n; i++)
1914 if (idx != get_stridx (gimple_phi_arg_def (phi, i)))
1915 break;
1916 if (i == n)
1917 ssa_ver_to_stridx[SSA_NAME_VERSION (result)] = idx;
1922 /* Attempt to optimize individual statements. */
1923 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
1924 if (strlen_optimize_stmt (&gsi))
1925 gsi_next (&gsi);
1927 bb->aux = stridx_to_strinfo;
1928 if (vec_safe_length (stridx_to_strinfo) && !strinfo_shared ())
1929 (*stridx_to_strinfo)[0] = (strinfo) bb;
1932 /* Callback for walk_dominator_tree. Free strinfo vector if it is
1933 owned by the current bb, clear bb->aux. */
1935 static void
1936 strlen_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1937 basic_block bb)
1939 if (bb->aux)
1941 stridx_to_strinfo = ((vec<strinfo, va_heap, vl_embed> *) bb->aux);
1942 if (vec_safe_length (stridx_to_strinfo)
1943 && (*stridx_to_strinfo)[0] == (strinfo) bb)
1945 unsigned int i;
1946 strinfo si;
1948 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
1949 free_strinfo (si);
1950 vec_free (stridx_to_strinfo);
1952 bb->aux = NULL;
1956 /* Main entry point. */
1958 static unsigned int
1959 tree_ssa_strlen (void)
1961 struct dom_walk_data walk_data;
1963 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
1964 max_stridx = 1;
1965 strinfo_pool = create_alloc_pool ("strinfo_struct pool",
1966 sizeof (struct strinfo_struct), 64);
1968 calculate_dominance_info (CDI_DOMINATORS);
1970 /* String length optimization is implemented as a walk of the dominator
1971 tree and a forward walk of statements within each block. */
1972 walk_data.dom_direction = CDI_DOMINATORS;
1973 walk_data.initialize_block_local_data = NULL;
1974 walk_data.before_dom_children = strlen_enter_block;
1975 walk_data.after_dom_children = strlen_leave_block;
1976 walk_data.block_local_data_size = 0;
1977 walk_data.global_data = NULL;
1979 /* Initialize the dominator walker. */
1980 init_walk_dominator_tree (&walk_data);
1982 /* Recursively walk the dominator tree. */
1983 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1985 /* Finalize the dominator walker. */
1986 fini_walk_dominator_tree (&walk_data);
1988 ssa_ver_to_stridx.release ();
1989 free_alloc_pool (strinfo_pool);
1990 if (decl_to_stridxlist_htab)
1992 obstack_free (&stridx_obstack, NULL);
1993 htab_delete (decl_to_stridxlist_htab);
1994 decl_to_stridxlist_htab = NULL;
1996 laststmt.stmt = NULL;
1997 laststmt.len = NULL_TREE;
1998 laststmt.stridx = 0;
2000 return 0;
2003 static bool
2004 gate_strlen (void)
2006 return flag_optimize_strlen != 0;
2009 struct gimple_opt_pass pass_strlen =
2012 GIMPLE_PASS,
2013 "strlen", /* name */
2014 OPTGROUP_NONE, /* optinfo_flags */
2015 gate_strlen, /* gate */
2016 tree_ssa_strlen, /* execute */
2017 NULL, /* sub */
2018 NULL, /* next */
2019 0, /* static_pass_number */
2020 TV_TREE_STRLEN, /* tv_id */
2021 PROP_cfg | PROP_ssa, /* properties_required */
2022 0, /* properties_provided */
2023 0, /* properties_destroyed */
2024 0, /* todo_flags_start */
2025 TODO_ggc_collect
2026 | TODO_verify_ssa /* todo_flags_finish */