tree-ssa-ccp.c (canonicalize_float_value): Rename to ...
[official-gcc.git] / gcc / tree-ssa-strlen.c
blobea73179eea88030aef25c6bb6fc3282f1a0c04bd
1 /* String length optimization
2 Copyright (C) 2011-2013 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.h"
25 #include "hash-table.h"
26 #include "bitmap.h"
27 #include "gimple.h"
28 #include "gimple-ssa.h"
29 #include "tree-phinodes.h"
30 #include "ssa-iterators.h"
31 #include "tree-ssanames.h"
32 #include "tree-dfa.h"
33 #include "tree-pass.h"
34 #include "domwalk.h"
35 #include "alloc-pool.h"
36 #include "tree-ssa-propagate.h"
37 #include "gimple-pretty-print.h"
38 #include "params.h"
39 #include "expr.h"
41 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
42 is an index into strinfo vector, negative value stands for
43 string length of a string literal (~strlen). */
44 static vec<int> ssa_ver_to_stridx;
46 /* Number of currently active string indexes plus one. */
47 static int max_stridx;
49 /* String information record. */
50 typedef struct strinfo_struct
52 /* String length of this string. */
53 tree length;
54 /* Any of the corresponding pointers for querying alias oracle. */
55 tree ptr;
56 /* Statement for delayed length computation. */
57 gimple stmt;
58 /* Pointer to '\0' if known, if NULL, it can be computed as
59 ptr + length. */
60 tree endptr;
61 /* Reference count. Any changes to strinfo entry possibly shared
62 with dominating basic blocks need unshare_strinfo first, except
63 for dont_invalidate which affects only the immediately next
64 maybe_invalidate. */
65 int refcount;
66 /* Copy of index. get_strinfo (si->idx) should return si; */
67 int idx;
68 /* These 3 fields are for chaining related string pointers together.
69 E.g. for
70 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
71 strcpy (c, d); e = c + dl;
72 strinfo(a) -> strinfo(c) -> strinfo(e)
73 All have ->first field equal to strinfo(a)->idx and are doubly
74 chained through prev/next fields. The later strinfos are required
75 to point into the same string with zero or more bytes after
76 the previous pointer and all bytes in between the two pointers
77 must be non-zero. Functions like strcpy or memcpy are supposed
78 to adjust all previous strinfo lengths, but not following strinfo
79 lengths (those are uncertain, usually invalidated during
80 maybe_invalidate, except when the alias oracle knows better).
81 Functions like strcat on the other side adjust the whole
82 related strinfo chain.
83 They are updated lazily, so to use the chain the same first fields
84 and si->prev->next == si->idx needs to be verified. */
85 int first;
86 int next;
87 int prev;
88 /* A flag whether the string is known to be written in the current
89 function. */
90 bool writable;
91 /* A flag for the next maybe_invalidate that this strinfo shouldn't
92 be invalidated. Always cleared by maybe_invalidate. */
93 bool dont_invalidate;
94 } *strinfo;
96 /* Pool for allocating strinfo_struct entries. */
97 static alloc_pool strinfo_pool;
99 /* Vector mapping positive string indexes to strinfo, for the
100 current basic block. The first pointer in the vector is special,
101 it is either NULL, meaning the vector isn't shared, or it is
102 a basic block pointer to the owner basic_block if shared.
103 If some other bb wants to modify the vector, the vector needs
104 to be unshared first, and only the owner bb is supposed to free it. */
105 static vec<strinfo, va_heap, vl_embed> *stridx_to_strinfo;
107 /* One OFFSET->IDX mapping. */
108 struct stridxlist
110 struct stridxlist *next;
111 HOST_WIDE_INT offset;
112 int idx;
115 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
116 struct decl_stridxlist_map
118 struct tree_map_base base;
119 struct stridxlist list;
122 /* stridxlist hashtable helpers. */
124 struct stridxlist_hasher : typed_noop_remove <decl_stridxlist_map>
126 typedef decl_stridxlist_map value_type;
127 typedef decl_stridxlist_map compare_type;
128 static inline hashval_t hash (const value_type *);
129 static inline bool equal (const value_type *, const compare_type *);
132 /* Hash a from tree in a decl_stridxlist_map. */
134 inline hashval_t
135 stridxlist_hasher::hash (const value_type *item)
137 return DECL_UID (item->base.from);
140 inline bool
141 stridxlist_hasher::equal (const value_type *v, const compare_type *c)
143 return tree_map_base_eq (&v->base, &c->base);
146 /* Hash table for mapping decls to a chained list of offset -> idx
147 mappings. */
148 static hash_table <stridxlist_hasher> decl_to_stridxlist_htab;
150 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
151 static struct obstack stridx_obstack;
153 /* Last memcpy statement if it could be adjusted if the trailing
154 '\0' written is immediately overwritten, or
155 *x = '\0' store that could be removed if it is immediately overwritten. */
156 struct laststmt_struct
158 gimple stmt;
159 tree len;
160 int stridx;
161 } laststmt;
163 /* Helper function for get_stridx. */
165 static int
166 get_addr_stridx (tree exp)
168 HOST_WIDE_INT off;
169 struct decl_stridxlist_map ent, *e;
170 struct stridxlist *list;
171 tree base;
173 if (!decl_to_stridxlist_htab.is_created ())
174 return 0;
176 base = get_addr_base_and_unit_offset (exp, &off);
177 if (base == NULL || !DECL_P (base))
178 return 0;
180 ent.base.from = base;
181 e = decl_to_stridxlist_htab.find_with_hash (&ent, DECL_UID (base));
182 if (e == NULL)
183 return 0;
185 list = &e->list;
188 if (list->offset == off)
189 return list->idx;
190 list = list->next;
192 while (list);
193 return 0;
196 /* Return string index for EXP. */
198 static int
199 get_stridx (tree exp)
201 tree s, o;
203 if (TREE_CODE (exp) == SSA_NAME)
204 return ssa_ver_to_stridx[SSA_NAME_VERSION (exp)];
206 if (TREE_CODE (exp) == ADDR_EXPR)
208 int idx = get_addr_stridx (TREE_OPERAND (exp, 0));
209 if (idx != 0)
210 return idx;
213 s = string_constant (exp, &o);
214 if (s != NULL_TREE
215 && (o == NULL_TREE || host_integerp (o, 0))
216 && TREE_STRING_LENGTH (s) > 0)
218 HOST_WIDE_INT offset = o ? tree_low_cst (o, 0) : 0;
219 const char *p = TREE_STRING_POINTER (s);
220 int max = TREE_STRING_LENGTH (s) - 1;
222 if (p[max] == '\0' && offset >= 0 && offset <= max)
223 return ~(int) strlen (p + offset);
225 return 0;
228 /* Return true if strinfo vector is shared with the immediate dominator. */
230 static inline bool
231 strinfo_shared (void)
233 return vec_safe_length (stridx_to_strinfo)
234 && (*stridx_to_strinfo)[0] != NULL;
237 /* Unshare strinfo vector that is shared with the immediate dominator. */
239 static void
240 unshare_strinfo_vec (void)
242 strinfo si;
243 unsigned int i = 0;
245 gcc_assert (strinfo_shared ());
246 stridx_to_strinfo = vec_safe_copy (stridx_to_strinfo);
247 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
248 if (si != NULL)
249 si->refcount++;
250 (*stridx_to_strinfo)[0] = NULL;
253 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
254 Return a pointer to the location where the string index can
255 be stored (if 0) or is stored, or NULL if this can't be tracked. */
257 static int *
258 addr_stridxptr (tree exp)
260 decl_stridxlist_map **slot;
261 struct decl_stridxlist_map ent;
262 struct stridxlist *list;
263 HOST_WIDE_INT off;
265 tree base = get_addr_base_and_unit_offset (exp, &off);
266 if (base == NULL_TREE || !DECL_P (base))
267 return NULL;
269 if (!decl_to_stridxlist_htab.is_created ())
271 decl_to_stridxlist_htab.create (64);
272 gcc_obstack_init (&stridx_obstack);
274 ent.base.from = base;
275 slot = decl_to_stridxlist_htab.find_slot_with_hash (&ent, DECL_UID (base),
276 INSERT);
277 if (*slot)
279 int i;
280 list = &(*slot)->list;
281 for (i = 0; i < 16; i++)
283 if (list->offset == off)
284 return &list->idx;
285 if (list->next == NULL)
286 break;
288 if (i == 16)
289 return NULL;
290 list->next = XOBNEW (&stridx_obstack, struct stridxlist);
291 list = list->next;
293 else
295 struct decl_stridxlist_map *e
296 = XOBNEW (&stridx_obstack, struct decl_stridxlist_map);
297 e->base.from = base;
298 *slot = e;
299 list = &e->list;
301 list->next = NULL;
302 list->offset = off;
303 list->idx = 0;
304 return &list->idx;
307 /* Create a new string index, or return 0 if reached limit. */
309 static int
310 new_stridx (tree exp)
312 int idx;
313 if (max_stridx >= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS))
314 return 0;
315 if (TREE_CODE (exp) == SSA_NAME)
317 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp))
318 return 0;
319 idx = max_stridx++;
320 ssa_ver_to_stridx[SSA_NAME_VERSION (exp)] = idx;
321 return idx;
323 if (TREE_CODE (exp) == ADDR_EXPR)
325 int *pidx = addr_stridxptr (TREE_OPERAND (exp, 0));
326 if (pidx != NULL)
328 gcc_assert (*pidx == 0);
329 *pidx = max_stridx++;
330 return *pidx;
333 return 0;
336 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
338 static int
339 new_addr_stridx (tree exp)
341 int *pidx;
342 if (max_stridx >= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS))
343 return 0;
344 pidx = addr_stridxptr (exp);
345 if (pidx != NULL)
347 gcc_assert (*pidx == 0);
348 *pidx = max_stridx++;
349 return *pidx;
351 return 0;
354 /* Create a new strinfo. */
356 static strinfo
357 new_strinfo (tree ptr, int idx, tree length)
359 strinfo si = (strinfo) pool_alloc (strinfo_pool);
360 si->length = length;
361 si->ptr = ptr;
362 si->stmt = NULL;
363 si->endptr = NULL_TREE;
364 si->refcount = 1;
365 si->idx = idx;
366 si->first = 0;
367 si->prev = 0;
368 si->next = 0;
369 si->writable = false;
370 si->dont_invalidate = false;
371 return si;
374 /* Decrease strinfo refcount and free it if not referenced anymore. */
376 static inline void
377 free_strinfo (strinfo si)
379 if (si && --si->refcount == 0)
380 pool_free (strinfo_pool, si);
383 /* Return strinfo vector entry IDX. */
385 static inline strinfo
386 get_strinfo (int idx)
388 if (vec_safe_length (stridx_to_strinfo) <= (unsigned int) idx)
389 return NULL;
390 return (*stridx_to_strinfo)[idx];
393 /* Set strinfo in the vector entry IDX to SI. */
395 static inline void
396 set_strinfo (int idx, strinfo si)
398 if (vec_safe_length (stridx_to_strinfo) && (*stridx_to_strinfo)[0])
399 unshare_strinfo_vec ();
400 if (vec_safe_length (stridx_to_strinfo) <= (unsigned int) idx)
401 vec_safe_grow_cleared (stridx_to_strinfo, idx + 1);
402 (*stridx_to_strinfo)[idx] = si;
405 /* Return string length, or NULL if it can't be computed. */
407 static tree
408 get_string_length (strinfo si)
410 if (si->length)
411 return si->length;
413 if (si->stmt)
415 gimple stmt = si->stmt, lenstmt;
416 tree callee, lhs, fn, tem;
417 location_t loc;
418 gimple_stmt_iterator gsi;
420 gcc_assert (is_gimple_call (stmt));
421 callee = gimple_call_fndecl (stmt);
422 gcc_assert (callee && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL);
423 lhs = gimple_call_lhs (stmt);
424 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY));
425 /* unshare_strinfo is intentionally not called here. The (delayed)
426 transformation of strcpy or strcat into stpcpy is done at the place
427 of the former strcpy/strcat call and so can affect all the strinfos
428 with the same stmt. If they were unshared before and transformation
429 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
430 just compute the right length. */
431 switch (DECL_FUNCTION_CODE (callee))
433 case BUILT_IN_STRCAT:
434 case BUILT_IN_STRCAT_CHK:
435 gsi = gsi_for_stmt (stmt);
436 fn = builtin_decl_implicit (BUILT_IN_STRLEN);
437 gcc_assert (lhs == NULL_TREE);
438 tem = unshare_expr (gimple_call_arg (stmt, 0));
439 lenstmt = gimple_build_call (fn, 1, tem);
440 lhs = make_ssa_name (TREE_TYPE (TREE_TYPE (fn)), lenstmt);
441 gimple_call_set_lhs (lenstmt, lhs);
442 gimple_set_vuse (lenstmt, gimple_vuse (stmt));
443 gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT);
444 tem = gimple_call_arg (stmt, 0);
445 if (!ptrofftype_p (TREE_TYPE (lhs)))
447 lhs = convert_to_ptrofftype (lhs);
448 lhs = force_gimple_operand_gsi (&gsi, lhs, true, NULL_TREE,
449 true, GSI_SAME_STMT);
451 lenstmt
452 = gimple_build_assign_with_ops
453 (POINTER_PLUS_EXPR,
454 make_ssa_name (TREE_TYPE (gimple_call_arg (stmt, 0)), NULL),
455 tem, lhs);
456 gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT);
457 gimple_call_set_arg (stmt, 0, gimple_assign_lhs (lenstmt));
458 lhs = NULL_TREE;
459 /* FALLTHRU */
460 case BUILT_IN_STRCPY:
461 case BUILT_IN_STRCPY_CHK:
462 if (gimple_call_num_args (stmt) == 2)
463 fn = builtin_decl_implicit (BUILT_IN_STPCPY);
464 else
465 fn = builtin_decl_explicit (BUILT_IN_STPCPY_CHK);
466 gcc_assert (lhs == NULL_TREE);
467 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
469 fprintf (dump_file, "Optimizing: ");
470 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
472 gimple_call_set_fndecl (stmt, fn);
473 lhs = make_ssa_name (TREE_TYPE (TREE_TYPE (fn)), stmt);
474 gimple_call_set_lhs (stmt, lhs);
475 update_stmt (stmt);
476 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
478 fprintf (dump_file, "into: ");
479 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
481 /* FALLTHRU */
482 case BUILT_IN_STPCPY:
483 case BUILT_IN_STPCPY_CHK:
484 gcc_assert (lhs != NULL_TREE);
485 loc = gimple_location (stmt);
486 si->endptr = lhs;
487 si->stmt = NULL;
488 lhs = fold_convert_loc (loc, size_type_node, lhs);
489 si->length = fold_convert_loc (loc, size_type_node, si->ptr);
490 si->length = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
491 lhs, si->length);
492 break;
493 default:
494 gcc_unreachable ();
495 break;
499 return si->length;
502 /* Invalidate string length information for strings whose length
503 might change due to stores in stmt. */
505 static bool
506 maybe_invalidate (gimple stmt)
508 strinfo si;
509 unsigned int i;
510 bool nonempty = false;
512 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
513 if (si != NULL)
515 if (!si->dont_invalidate)
517 ao_ref r;
518 ao_ref_init_from_ptr_and_size (&r, si->ptr, NULL_TREE);
519 if (stmt_may_clobber_ref_p_1 (stmt, &r))
521 set_strinfo (i, NULL);
522 free_strinfo (si);
523 continue;
526 si->dont_invalidate = false;
527 nonempty = true;
529 return nonempty;
532 /* Unshare strinfo record SI, if it has recount > 1 or
533 if stridx_to_strinfo vector is shared with some other
534 bbs. */
536 static strinfo
537 unshare_strinfo (strinfo si)
539 strinfo nsi;
541 if (si->refcount == 1 && !strinfo_shared ())
542 return si;
544 nsi = new_strinfo (si->ptr, si->idx, si->length);
545 nsi->stmt = si->stmt;
546 nsi->endptr = si->endptr;
547 nsi->first = si->first;
548 nsi->prev = si->prev;
549 nsi->next = si->next;
550 nsi->writable = si->writable;
551 set_strinfo (si->idx, nsi);
552 free_strinfo (si);
553 return nsi;
556 /* Return first strinfo in the related strinfo chain
557 if all strinfos in between belong to the chain, otherwise
558 NULL. */
560 static strinfo
561 verify_related_strinfos (strinfo origsi)
563 strinfo si = origsi, psi;
565 if (origsi->first == 0)
566 return NULL;
567 for (; si->prev; si = psi)
569 if (si->first != origsi->first)
570 return NULL;
571 psi = get_strinfo (si->prev);
572 if (psi == NULL)
573 return NULL;
574 if (psi->next != si->idx)
575 return NULL;
577 if (si->idx != si->first)
578 return NULL;
579 return si;
582 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
583 to a zero-length string and if possible chain it to a related strinfo
584 chain whose part is or might be CHAINSI. */
586 static strinfo
587 zero_length_string (tree ptr, strinfo chainsi)
589 strinfo si;
590 int idx;
591 gcc_checking_assert (TREE_CODE (ptr) == SSA_NAME
592 && get_stridx (ptr) == 0);
594 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
595 return NULL;
596 if (chainsi != NULL)
598 si = verify_related_strinfos (chainsi);
599 if (si)
601 chainsi = si;
602 for (; chainsi->next; chainsi = si)
604 if (chainsi->endptr == NULL_TREE)
606 chainsi = unshare_strinfo (chainsi);
607 chainsi->endptr = ptr;
609 si = get_strinfo (chainsi->next);
610 if (si == NULL
611 || si->first != chainsi->first
612 || si->prev != chainsi->idx)
613 break;
615 gcc_assert (chainsi->length || chainsi->stmt);
616 if (chainsi->endptr == NULL_TREE)
618 chainsi = unshare_strinfo (chainsi);
619 chainsi->endptr = ptr;
621 if (chainsi->length && integer_zerop (chainsi->length))
623 if (chainsi->next)
625 chainsi = unshare_strinfo (chainsi);
626 chainsi->next = 0;
628 ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = chainsi->idx;
629 return chainsi;
632 else if (chainsi->first || chainsi->prev || chainsi->next)
634 chainsi = unshare_strinfo (chainsi);
635 chainsi->first = 0;
636 chainsi->prev = 0;
637 chainsi->next = 0;
640 idx = new_stridx (ptr);
641 if (idx == 0)
642 return NULL;
643 si = new_strinfo (ptr, idx, build_int_cst (size_type_node, 0));
644 set_strinfo (idx, si);
645 si->endptr = ptr;
646 if (chainsi != NULL)
648 chainsi = unshare_strinfo (chainsi);
649 if (chainsi->first == 0)
650 chainsi->first = chainsi->idx;
651 chainsi->next = idx;
652 if (chainsi->endptr == NULL_TREE)
653 chainsi->endptr = ptr;
654 si->prev = chainsi->idx;
655 si->first = chainsi->first;
656 si->writable = chainsi->writable;
658 return si;
661 /* For strinfo ORIGSI whose length has been just updated
662 update also related strinfo lengths (add ADJ to each,
663 but don't adjust ORIGSI). */
665 static void
666 adjust_related_strinfos (location_t loc, strinfo origsi, tree adj)
668 strinfo si = verify_related_strinfos (origsi);
670 if (si == NULL)
671 return;
673 while (1)
675 strinfo nsi;
677 if (si != origsi)
679 tree tem;
681 si = unshare_strinfo (si);
682 if (si->length)
684 tem = fold_convert_loc (loc, TREE_TYPE (si->length), adj);
685 si->length = fold_build2_loc (loc, PLUS_EXPR,
686 TREE_TYPE (si->length), si->length,
687 tem);
689 else if (si->stmt != NULL)
690 /* Delayed length computation is unaffected. */
692 else
693 gcc_unreachable ();
695 si->endptr = NULL_TREE;
696 si->dont_invalidate = true;
698 if (si->next == 0)
699 return;
700 nsi = get_strinfo (si->next);
701 if (nsi == NULL
702 || nsi->first != si->first
703 || nsi->prev != si->idx)
704 return;
705 si = nsi;
709 /* Find if there are other SSA_NAME pointers equal to PTR
710 for which we don't track their string lengths yet. If so, use
711 IDX for them. */
713 static void
714 find_equal_ptrs (tree ptr, int idx)
716 if (TREE_CODE (ptr) != SSA_NAME)
717 return;
718 while (1)
720 gimple stmt = SSA_NAME_DEF_STMT (ptr);
721 if (!is_gimple_assign (stmt))
722 return;
723 ptr = gimple_assign_rhs1 (stmt);
724 switch (gimple_assign_rhs_code (stmt))
726 case SSA_NAME:
727 break;
728 CASE_CONVERT:
729 if (!POINTER_TYPE_P (TREE_TYPE (ptr)))
730 return;
731 if (TREE_CODE (ptr) == SSA_NAME)
732 break;
733 if (TREE_CODE (ptr) != ADDR_EXPR)
734 return;
735 /* FALLTHRU */
736 case ADDR_EXPR:
738 int *pidx = addr_stridxptr (TREE_OPERAND (ptr, 0));
739 if (pidx != NULL && *pidx == 0)
740 *pidx = idx;
741 return;
743 default:
744 return;
747 /* We might find an endptr created in this pass. Grow the
748 vector in that case. */
749 if (ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
750 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
752 if (ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] != 0)
753 return;
754 ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = idx;
758 /* If the last .MEM setter statement before STMT is
759 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
760 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
761 just memcpy (x, y, strlen (y)). SI must be the zero length
762 strinfo. */
764 static void
765 adjust_last_stmt (strinfo si, gimple stmt, bool is_strcat)
767 tree vuse, callee, len;
768 struct laststmt_struct last = laststmt;
769 strinfo lastsi, firstsi;
771 laststmt.stmt = NULL;
772 laststmt.len = NULL_TREE;
773 laststmt.stridx = 0;
775 if (last.stmt == NULL)
776 return;
778 vuse = gimple_vuse (stmt);
779 if (vuse == NULL_TREE
780 || SSA_NAME_DEF_STMT (vuse) != last.stmt
781 || !has_single_use (vuse))
782 return;
784 gcc_assert (last.stridx > 0);
785 lastsi = get_strinfo (last.stridx);
786 if (lastsi == NULL)
787 return;
789 if (lastsi != si)
791 if (lastsi->first == 0 || lastsi->first != si->first)
792 return;
794 firstsi = verify_related_strinfos (si);
795 if (firstsi == NULL)
796 return;
797 while (firstsi != lastsi)
799 strinfo nextsi;
800 if (firstsi->next == 0)
801 return;
802 nextsi = get_strinfo (firstsi->next);
803 if (nextsi == NULL
804 || nextsi->prev != firstsi->idx
805 || nextsi->first != si->first)
806 return;
807 firstsi = nextsi;
811 if (!is_strcat)
813 if (si->length == NULL_TREE || !integer_zerop (si->length))
814 return;
817 if (is_gimple_assign (last.stmt))
819 gimple_stmt_iterator gsi;
821 if (!integer_zerop (gimple_assign_rhs1 (last.stmt)))
822 return;
823 if (stmt_could_throw_p (last.stmt))
824 return;
825 gsi = gsi_for_stmt (last.stmt);
826 unlink_stmt_vdef (last.stmt);
827 release_defs (last.stmt);
828 gsi_remove (&gsi, true);
829 return;
832 if (!gimple_call_builtin_p (last.stmt, BUILT_IN_NORMAL))
833 return;
835 callee = gimple_call_fndecl (last.stmt);
836 switch (DECL_FUNCTION_CODE (callee))
838 case BUILT_IN_MEMCPY:
839 case BUILT_IN_MEMCPY_CHK:
840 break;
841 default:
842 return;
845 len = gimple_call_arg (last.stmt, 2);
846 if (host_integerp (len, 1))
848 if (!host_integerp (last.len, 1)
849 || integer_zerop (len)
850 || (unsigned HOST_WIDE_INT) tree_low_cst (len, 1)
851 != (unsigned HOST_WIDE_INT) tree_low_cst (last.len, 1) + 1)
852 return;
853 /* Don't adjust the length if it is divisible by 4, it is more efficient
854 to store the extra '\0' in that case. */
855 if ((((unsigned HOST_WIDE_INT) tree_low_cst (len, 1)) & 3) == 0)
856 return;
858 else if (TREE_CODE (len) == SSA_NAME)
860 gimple def_stmt = SSA_NAME_DEF_STMT (len);
861 if (!is_gimple_assign (def_stmt)
862 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
863 || gimple_assign_rhs1 (def_stmt) != last.len
864 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
865 return;
867 else
868 return;
870 gimple_call_set_arg (last.stmt, 2, last.len);
871 update_stmt (last.stmt);
874 /* Handle a strlen call. If strlen of the argument is known, replace
875 the strlen call with the known value, otherwise remember that strlen
876 of the argument is stored in the lhs SSA_NAME. */
878 static void
879 handle_builtin_strlen (gimple_stmt_iterator *gsi)
881 int idx;
882 tree src;
883 gimple stmt = gsi_stmt (*gsi);
884 tree lhs = gimple_call_lhs (stmt);
886 if (lhs == NULL_TREE)
887 return;
889 src = gimple_call_arg (stmt, 0);
890 idx = get_stridx (src);
891 if (idx)
893 strinfo si = NULL;
894 tree rhs;
896 if (idx < 0)
897 rhs = build_int_cst (TREE_TYPE (lhs), ~idx);
898 else
900 rhs = NULL_TREE;
901 si = get_strinfo (idx);
902 if (si != NULL)
903 rhs = get_string_length (si);
905 if (rhs != NULL_TREE)
907 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
909 fprintf (dump_file, "Optimizing: ");
910 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
912 rhs = unshare_expr (rhs);
913 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
914 rhs = fold_convert_loc (gimple_location (stmt),
915 TREE_TYPE (lhs), rhs);
916 if (!update_call_from_tree (gsi, rhs))
917 gimplify_and_update_call_from_tree (gsi, rhs);
918 stmt = gsi_stmt (*gsi);
919 update_stmt (stmt);
920 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
922 fprintf (dump_file, "into: ");
923 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
925 if (si != NULL
926 && TREE_CODE (si->length) != SSA_NAME
927 && TREE_CODE (si->length) != INTEGER_CST
928 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
930 si = unshare_strinfo (si);
931 si->length = lhs;
933 return;
936 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
937 return;
938 if (idx == 0)
939 idx = new_stridx (src);
940 else if (get_strinfo (idx) != NULL)
941 return;
942 if (idx)
944 strinfo si = new_strinfo (src, idx, lhs);
945 set_strinfo (idx, si);
946 find_equal_ptrs (src, idx);
950 /* Handle a strchr call. If strlen of the first argument is known, replace
951 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
952 that lhs of the call is endptr and strlen of the argument is endptr - x. */
954 static void
955 handle_builtin_strchr (gimple_stmt_iterator *gsi)
957 int idx;
958 tree src;
959 gimple stmt = gsi_stmt (*gsi);
960 tree lhs = gimple_call_lhs (stmt);
962 if (lhs == NULL_TREE)
963 return;
965 if (!integer_zerop (gimple_call_arg (stmt, 1)))
966 return;
968 src = gimple_call_arg (stmt, 0);
969 idx = get_stridx (src);
970 if (idx)
972 strinfo si = NULL;
973 tree rhs;
975 if (idx < 0)
976 rhs = build_int_cst (size_type_node, ~idx);
977 else
979 rhs = NULL_TREE;
980 si = get_strinfo (idx);
981 if (si != NULL)
982 rhs = get_string_length (si);
984 if (rhs != NULL_TREE)
986 location_t loc = gimple_location (stmt);
988 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
990 fprintf (dump_file, "Optimizing: ");
991 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
993 if (si != NULL && si->endptr != NULL_TREE)
995 rhs = unshare_expr (si->endptr);
996 if (!useless_type_conversion_p (TREE_TYPE (lhs),
997 TREE_TYPE (rhs)))
998 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
1000 else
1002 rhs = fold_convert_loc (loc, sizetype, unshare_expr (rhs));
1003 rhs = fold_build2_loc (loc, POINTER_PLUS_EXPR,
1004 TREE_TYPE (src), src, rhs);
1005 if (!useless_type_conversion_p (TREE_TYPE (lhs),
1006 TREE_TYPE (rhs)))
1007 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
1009 if (!update_call_from_tree (gsi, rhs))
1010 gimplify_and_update_call_from_tree (gsi, rhs);
1011 stmt = gsi_stmt (*gsi);
1012 update_stmt (stmt);
1013 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1015 fprintf (dump_file, "into: ");
1016 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1018 if (si != NULL
1019 && si->endptr == NULL_TREE
1020 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1022 si = unshare_strinfo (si);
1023 si->endptr = lhs;
1025 zero_length_string (lhs, si);
1026 return;
1029 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1030 return;
1031 if (TREE_CODE (src) != SSA_NAME || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src))
1033 if (idx == 0)
1034 idx = new_stridx (src);
1035 else if (get_strinfo (idx) != NULL)
1037 zero_length_string (lhs, NULL);
1038 return;
1040 if (idx)
1042 location_t loc = gimple_location (stmt);
1043 tree lhsu = fold_convert_loc (loc, size_type_node, lhs);
1044 tree srcu = fold_convert_loc (loc, size_type_node, src);
1045 tree length = fold_build2_loc (loc, MINUS_EXPR,
1046 size_type_node, lhsu, srcu);
1047 strinfo si = new_strinfo (src, idx, length);
1048 si->endptr = lhs;
1049 set_strinfo (idx, si);
1050 find_equal_ptrs (src, idx);
1051 zero_length_string (lhs, si);
1054 else
1055 zero_length_string (lhs, NULL);
1058 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1059 If strlen of the second argument is known, strlen of the first argument
1060 is the same after this call. Furthermore, attempt to convert it to
1061 memcpy. */
1063 static void
1064 handle_builtin_strcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1066 int idx, didx;
1067 tree src, dst, srclen, len, lhs, args, type, fn, oldlen;
1068 bool success;
1069 gimple stmt = gsi_stmt (*gsi);
1070 strinfo si, dsi, olddsi, zsi;
1071 location_t loc;
1073 src = gimple_call_arg (stmt, 1);
1074 dst = gimple_call_arg (stmt, 0);
1075 lhs = gimple_call_lhs (stmt);
1076 idx = get_stridx (src);
1077 si = NULL;
1078 if (idx > 0)
1079 si = get_strinfo (idx);
1081 didx = get_stridx (dst);
1082 olddsi = NULL;
1083 oldlen = NULL_TREE;
1084 if (didx > 0)
1085 olddsi = get_strinfo (didx);
1086 else if (didx < 0)
1087 return;
1089 if (olddsi != NULL)
1090 adjust_last_stmt (olddsi, stmt, false);
1092 srclen = NULL_TREE;
1093 if (si != NULL)
1094 srclen = get_string_length (si);
1095 else if (idx < 0)
1096 srclen = build_int_cst (size_type_node, ~idx);
1098 loc = gimple_location (stmt);
1099 if (srclen == NULL_TREE)
1100 switch (bcode)
1102 case BUILT_IN_STRCPY:
1103 case BUILT_IN_STRCPY_CHK:
1104 if (lhs != NULL_TREE || !builtin_decl_implicit_p (BUILT_IN_STPCPY))
1105 return;
1106 break;
1107 case BUILT_IN_STPCPY:
1108 case BUILT_IN_STPCPY_CHK:
1109 if (lhs == NULL_TREE)
1110 return;
1111 else
1113 tree lhsuint = fold_convert_loc (loc, size_type_node, lhs);
1114 srclen = fold_convert_loc (loc, size_type_node, dst);
1115 srclen = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
1116 lhsuint, srclen);
1118 break;
1119 default:
1120 gcc_unreachable ();
1123 if (didx == 0)
1125 didx = new_stridx (dst);
1126 if (didx == 0)
1127 return;
1129 if (olddsi != NULL)
1131 oldlen = olddsi->length;
1132 dsi = unshare_strinfo (olddsi);
1133 dsi->length = srclen;
1134 /* Break the chain, so adjust_related_strinfo on later pointers in
1135 the chain won't adjust this one anymore. */
1136 dsi->next = 0;
1137 dsi->stmt = NULL;
1138 dsi->endptr = NULL_TREE;
1140 else
1142 dsi = new_strinfo (dst, didx, srclen);
1143 set_strinfo (didx, dsi);
1144 find_equal_ptrs (dst, didx);
1146 dsi->writable = true;
1147 dsi->dont_invalidate = true;
1149 if (dsi->length == NULL_TREE)
1151 strinfo chainsi;
1153 /* If string length of src is unknown, use delayed length
1154 computation. If string lenth of dst will be needed, it
1155 can be computed by transforming this strcpy call into
1156 stpcpy and subtracting dst from the return value. */
1158 /* Look for earlier strings whose length could be determined if
1159 this strcpy is turned into an stpcpy. */
1161 if (dsi->prev != 0 && (chainsi = verify_related_strinfos (dsi)) != NULL)
1163 for (; chainsi && chainsi != dsi; chainsi = get_strinfo (chainsi->next))
1165 /* When setting a stmt for delayed length computation
1166 prevent all strinfos through dsi from being
1167 invalidated. */
1168 chainsi = unshare_strinfo (chainsi);
1169 chainsi->stmt = stmt;
1170 chainsi->length = NULL_TREE;
1171 chainsi->endptr = NULL_TREE;
1172 chainsi->dont_invalidate = true;
1175 dsi->stmt = stmt;
1176 return;
1179 if (olddsi != NULL)
1181 tree adj = NULL_TREE;
1182 if (oldlen == NULL_TREE)
1184 else if (integer_zerop (oldlen))
1185 adj = srclen;
1186 else if (TREE_CODE (oldlen) == INTEGER_CST
1187 || TREE_CODE (srclen) == INTEGER_CST)
1188 adj = fold_build2_loc (loc, MINUS_EXPR,
1189 TREE_TYPE (srclen), srclen,
1190 fold_convert_loc (loc, TREE_TYPE (srclen),
1191 oldlen));
1192 if (adj != NULL_TREE)
1193 adjust_related_strinfos (loc, dsi, adj);
1194 else
1195 dsi->prev = 0;
1197 /* strcpy src may not overlap dst, so src doesn't need to be
1198 invalidated either. */
1199 if (si != NULL)
1200 si->dont_invalidate = true;
1202 fn = NULL_TREE;
1203 zsi = NULL;
1204 switch (bcode)
1206 case BUILT_IN_STRCPY:
1207 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1208 if (lhs)
1209 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
1210 break;
1211 case BUILT_IN_STRCPY_CHK:
1212 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK);
1213 if (lhs)
1214 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
1215 break;
1216 case BUILT_IN_STPCPY:
1217 /* This would need adjustment of the lhs (subtract one),
1218 or detection that the trailing '\0' doesn't need to be
1219 written, if it will be immediately overwritten.
1220 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1221 if (lhs)
1223 dsi->endptr = lhs;
1224 zsi = zero_length_string (lhs, dsi);
1226 break;
1227 case BUILT_IN_STPCPY_CHK:
1228 /* This would need adjustment of the lhs (subtract one),
1229 or detection that the trailing '\0' doesn't need to be
1230 written, if it will be immediately overwritten.
1231 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1232 if (lhs)
1234 dsi->endptr = lhs;
1235 zsi = zero_length_string (lhs, dsi);
1237 break;
1238 default:
1239 gcc_unreachable ();
1241 if (zsi != NULL)
1242 zsi->dont_invalidate = true;
1244 if (fn == NULL_TREE)
1245 return;
1247 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1248 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1250 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1251 len = fold_build2_loc (loc, PLUS_EXPR, type, len, build_int_cst (type, 1));
1252 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1253 GSI_SAME_STMT);
1254 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1256 fprintf (dump_file, "Optimizing: ");
1257 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1259 if (gimple_call_num_args (stmt) == 2)
1260 success = update_gimple_call (gsi, fn, 3, dst, src, len);
1261 else
1262 success = update_gimple_call (gsi, fn, 4, dst, src, len,
1263 gimple_call_arg (stmt, 2));
1264 if (success)
1266 stmt = gsi_stmt (*gsi);
1267 update_stmt (stmt);
1268 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1270 fprintf (dump_file, "into: ");
1271 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1273 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1274 laststmt.stmt = stmt;
1275 laststmt.len = srclen;
1276 laststmt.stridx = dsi->idx;
1278 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1279 fprintf (dump_file, "not possible.\n");
1282 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1283 If strlen of the second argument is known and length of the third argument
1284 is that plus one, strlen of the first argument is the same after this
1285 call. */
1287 static void
1288 handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1290 int idx, didx;
1291 tree src, dst, len, lhs, oldlen, newlen;
1292 gimple stmt = gsi_stmt (*gsi);
1293 strinfo si, dsi, olddsi;
1295 len = gimple_call_arg (stmt, 2);
1296 src = gimple_call_arg (stmt, 1);
1297 dst = gimple_call_arg (stmt, 0);
1298 idx = get_stridx (src);
1299 if (idx == 0)
1300 return;
1302 didx = get_stridx (dst);
1303 olddsi = NULL;
1304 if (didx > 0)
1305 olddsi = get_strinfo (didx);
1306 else if (didx < 0)
1307 return;
1309 if (olddsi != NULL
1310 && host_integerp (len, 1)
1311 && !integer_zerop (len))
1312 adjust_last_stmt (olddsi, stmt, false);
1314 if (idx > 0)
1316 gimple def_stmt;
1318 /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */
1319 si = get_strinfo (idx);
1320 if (si == NULL || si->length == NULL_TREE)
1321 return;
1322 if (TREE_CODE (len) != SSA_NAME)
1323 return;
1324 def_stmt = SSA_NAME_DEF_STMT (len);
1325 if (!is_gimple_assign (def_stmt)
1326 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
1327 || gimple_assign_rhs1 (def_stmt) != si->length
1328 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
1329 return;
1331 else
1333 si = NULL;
1334 /* Handle memcpy (x, "abcd", 5) or
1335 memcpy (x, "abc\0uvw", 7). */
1336 if (!host_integerp (len, 1)
1337 || (unsigned HOST_WIDE_INT) tree_low_cst (len, 1)
1338 <= (unsigned HOST_WIDE_INT) ~idx)
1339 return;
1342 if (olddsi != NULL && TREE_CODE (len) == SSA_NAME)
1343 adjust_last_stmt (olddsi, stmt, false);
1345 if (didx == 0)
1347 didx = new_stridx (dst);
1348 if (didx == 0)
1349 return;
1351 if (si != NULL)
1352 newlen = si->length;
1353 else
1354 newlen = build_int_cst (size_type_node, ~idx);
1355 oldlen = NULL_TREE;
1356 if (olddsi != NULL)
1358 dsi = unshare_strinfo (olddsi);
1359 oldlen = olddsi->length;
1360 dsi->length = newlen;
1361 /* Break the chain, so adjust_related_strinfo on later pointers in
1362 the chain won't adjust this one anymore. */
1363 dsi->next = 0;
1364 dsi->stmt = NULL;
1365 dsi->endptr = NULL_TREE;
1367 else
1369 dsi = new_strinfo (dst, didx, newlen);
1370 set_strinfo (didx, dsi);
1371 find_equal_ptrs (dst, didx);
1373 dsi->writable = true;
1374 dsi->dont_invalidate = true;
1375 if (olddsi != NULL)
1377 tree adj = NULL_TREE;
1378 location_t loc = gimple_location (stmt);
1379 if (oldlen == NULL_TREE)
1381 else if (integer_zerop (oldlen))
1382 adj = dsi->length;
1383 else if (TREE_CODE (oldlen) == INTEGER_CST
1384 || TREE_CODE (dsi->length) == INTEGER_CST)
1385 adj = fold_build2_loc (loc, MINUS_EXPR,
1386 TREE_TYPE (dsi->length), dsi->length,
1387 fold_convert_loc (loc, TREE_TYPE (dsi->length),
1388 oldlen));
1389 if (adj != NULL_TREE)
1390 adjust_related_strinfos (loc, dsi, adj);
1391 else
1392 dsi->prev = 0;
1394 /* memcpy src may not overlap dst, so src doesn't need to be
1395 invalidated either. */
1396 if (si != NULL)
1397 si->dont_invalidate = true;
1399 lhs = gimple_call_lhs (stmt);
1400 switch (bcode)
1402 case BUILT_IN_MEMCPY:
1403 case BUILT_IN_MEMCPY_CHK:
1404 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1405 laststmt.stmt = stmt;
1406 laststmt.len = dsi->length;
1407 laststmt.stridx = dsi->idx;
1408 if (lhs)
1409 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
1410 break;
1411 case BUILT_IN_MEMPCPY:
1412 case BUILT_IN_MEMPCPY_CHK:
1413 break;
1414 default:
1415 gcc_unreachable ();
1419 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
1420 If strlen of the second argument is known, strlen of the first argument
1421 is increased by the length of the second argument. Furthermore, attempt
1422 to convert it to memcpy/strcpy if the length of the first argument
1423 is known. */
1425 static void
1426 handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1428 int idx, didx;
1429 tree src, dst, srclen, dstlen, len, lhs, args, type, fn, objsz, endptr;
1430 bool success;
1431 gimple stmt = gsi_stmt (*gsi);
1432 strinfo si, dsi;
1433 location_t loc;
1435 src = gimple_call_arg (stmt, 1);
1436 dst = gimple_call_arg (stmt, 0);
1437 lhs = gimple_call_lhs (stmt);
1439 didx = get_stridx (dst);
1440 if (didx < 0)
1441 return;
1443 dsi = NULL;
1444 if (didx > 0)
1445 dsi = get_strinfo (didx);
1446 if (dsi == NULL || get_string_length (dsi) == NULL_TREE)
1448 /* strcat (p, q) can be transformed into
1449 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
1450 with length endptr - p if we need to compute the length
1451 later on. Don't do this transformation if we don't need
1452 it. */
1453 if (builtin_decl_implicit_p (BUILT_IN_STPCPY) && lhs == NULL_TREE)
1455 if (didx == 0)
1457 didx = new_stridx (dst);
1458 if (didx == 0)
1459 return;
1461 if (dsi == NULL)
1463 dsi = new_strinfo (dst, didx, NULL_TREE);
1464 set_strinfo (didx, dsi);
1465 find_equal_ptrs (dst, didx);
1467 else
1469 dsi = unshare_strinfo (dsi);
1470 dsi->length = NULL_TREE;
1471 dsi->next = 0;
1472 dsi->endptr = NULL_TREE;
1474 dsi->writable = true;
1475 dsi->stmt = stmt;
1476 dsi->dont_invalidate = true;
1478 return;
1481 srclen = NULL_TREE;
1482 si = NULL;
1483 idx = get_stridx (src);
1484 if (idx < 0)
1485 srclen = build_int_cst (size_type_node, ~idx);
1486 else if (idx > 0)
1488 si = get_strinfo (idx);
1489 if (si != NULL)
1490 srclen = get_string_length (si);
1493 loc = gimple_location (stmt);
1494 dstlen = dsi->length;
1495 endptr = dsi->endptr;
1497 dsi = unshare_strinfo (dsi);
1498 dsi->endptr = NULL_TREE;
1499 dsi->stmt = NULL;
1500 dsi->writable = true;
1502 if (srclen != NULL_TREE)
1504 dsi->length = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (dsi->length),
1505 dsi->length, srclen);
1506 adjust_related_strinfos (loc, dsi, srclen);
1507 dsi->dont_invalidate = true;
1509 else
1511 dsi->length = NULL;
1512 if (lhs == NULL_TREE && builtin_decl_implicit_p (BUILT_IN_STPCPY))
1513 dsi->dont_invalidate = true;
1516 if (si != NULL)
1517 /* strcat src may not overlap dst, so src doesn't need to be
1518 invalidated either. */
1519 si->dont_invalidate = true;
1521 /* For now. Could remove the lhs from the call and add
1522 lhs = dst; afterwards. */
1523 if (lhs)
1524 return;
1526 fn = NULL_TREE;
1527 objsz = NULL_TREE;
1528 switch (bcode)
1530 case BUILT_IN_STRCAT:
1531 if (srclen != NULL_TREE)
1532 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1533 else
1534 fn = builtin_decl_implicit (BUILT_IN_STRCPY);
1535 break;
1536 case BUILT_IN_STRCAT_CHK:
1537 if (srclen != NULL_TREE)
1538 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK);
1539 else
1540 fn = builtin_decl_explicit (BUILT_IN_STRCPY_CHK);
1541 objsz = gimple_call_arg (stmt, 2);
1542 break;
1543 default:
1544 gcc_unreachable ();
1547 if (fn == NULL_TREE)
1548 return;
1550 len = NULL_TREE;
1551 if (srclen != NULL_TREE)
1553 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1554 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1556 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1557 len = fold_build2_loc (loc, PLUS_EXPR, type, len,
1558 build_int_cst (type, 1));
1559 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1560 GSI_SAME_STMT);
1562 if (endptr)
1563 dst = fold_convert_loc (loc, TREE_TYPE (dst), unshare_expr (endptr));
1564 else
1565 dst = fold_build2_loc (loc, POINTER_PLUS_EXPR,
1566 TREE_TYPE (dst), unshare_expr (dst),
1567 fold_convert_loc (loc, sizetype,
1568 unshare_expr (dstlen)));
1569 dst = force_gimple_operand_gsi (gsi, dst, true, NULL_TREE, true,
1570 GSI_SAME_STMT);
1571 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1573 fprintf (dump_file, "Optimizing: ");
1574 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1576 if (srclen != NULL_TREE)
1577 success = update_gimple_call (gsi, fn, 3 + (objsz != NULL_TREE),
1578 dst, src, len, objsz);
1579 else
1580 success = update_gimple_call (gsi, fn, 2 + (objsz != NULL_TREE),
1581 dst, src, objsz);
1582 if (success)
1584 stmt = gsi_stmt (*gsi);
1585 update_stmt (stmt);
1586 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1588 fprintf (dump_file, "into: ");
1589 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1591 /* If srclen == NULL, note that current string length can be
1592 computed by transforming this strcpy into stpcpy. */
1593 if (srclen == NULL_TREE && dsi->dont_invalidate)
1594 dsi->stmt = stmt;
1595 adjust_last_stmt (dsi, stmt, true);
1596 if (srclen != NULL_TREE)
1598 laststmt.stmt = stmt;
1599 laststmt.len = srclen;
1600 laststmt.stridx = dsi->idx;
1603 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1604 fprintf (dump_file, "not possible.\n");
1607 /* Handle a POINTER_PLUS_EXPR statement.
1608 For p = "abcd" + 2; compute associated length, or if
1609 p = q + off is pointing to a '\0' character of a string, call
1610 zero_length_string on it. */
1612 static void
1613 handle_pointer_plus (gimple_stmt_iterator *gsi)
1615 gimple stmt = gsi_stmt (*gsi);
1616 tree lhs = gimple_assign_lhs (stmt), off;
1617 int idx = get_stridx (gimple_assign_rhs1 (stmt));
1618 strinfo si, zsi;
1620 if (idx == 0)
1621 return;
1623 if (idx < 0)
1625 tree off = gimple_assign_rhs2 (stmt);
1626 if (host_integerp (off, 1)
1627 && (unsigned HOST_WIDE_INT) tree_low_cst (off, 1)
1628 <= (unsigned HOST_WIDE_INT) ~idx)
1629 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)]
1630 = ~(~idx - (int) tree_low_cst (off, 1));
1631 return;
1634 si = get_strinfo (idx);
1635 if (si == NULL || si->length == NULL_TREE)
1636 return;
1638 off = gimple_assign_rhs2 (stmt);
1639 zsi = NULL;
1640 if (operand_equal_p (si->length, off, 0))
1641 zsi = zero_length_string (lhs, si);
1642 else if (TREE_CODE (off) == SSA_NAME)
1644 gimple def_stmt = SSA_NAME_DEF_STMT (off);
1645 if (gimple_assign_single_p (def_stmt)
1646 && operand_equal_p (si->length, gimple_assign_rhs1 (def_stmt), 0))
1647 zsi = zero_length_string (lhs, si);
1649 if (zsi != NULL
1650 && si->endptr != NULL_TREE
1651 && si->endptr != lhs
1652 && TREE_CODE (si->endptr) == SSA_NAME)
1654 enum tree_code rhs_code
1655 = useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (si->endptr))
1656 ? SSA_NAME : NOP_EXPR;
1657 gimple_assign_set_rhs_with_ops (gsi, rhs_code, si->endptr, NULL_TREE);
1658 gcc_assert (gsi_stmt (*gsi) == stmt);
1659 update_stmt (stmt);
1663 /* Handle a single character store. */
1665 static bool
1666 handle_char_store (gimple_stmt_iterator *gsi)
1668 int idx = -1;
1669 strinfo si = NULL;
1670 gimple stmt = gsi_stmt (*gsi);
1671 tree ssaname = NULL_TREE, lhs = gimple_assign_lhs (stmt);
1673 if (TREE_CODE (lhs) == MEM_REF
1674 && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME)
1676 if (integer_zerop (TREE_OPERAND (lhs, 1)))
1678 ssaname = TREE_OPERAND (lhs, 0);
1679 idx = get_stridx (ssaname);
1682 else
1683 idx = get_addr_stridx (lhs);
1685 if (idx > 0)
1687 si = get_strinfo (idx);
1688 if (si != NULL && si->length != NULL_TREE && integer_zerop (si->length))
1690 if (initializer_zerop (gimple_assign_rhs1 (stmt)))
1692 /* When storing '\0', the store can be removed
1693 if we know it has been stored in the current function. */
1694 if (!stmt_could_throw_p (stmt) && si->writable)
1696 unlink_stmt_vdef (stmt);
1697 release_defs (stmt);
1698 gsi_remove (gsi, true);
1699 return false;
1701 else
1703 si->writable = true;
1704 gsi_next (gsi);
1705 return false;
1708 else
1709 /* Otherwise this statement overwrites the '\0' with
1710 something, if the previous stmt was a memcpy,
1711 its length may be decreased. */
1712 adjust_last_stmt (si, stmt, false);
1714 else if (si != NULL && integer_zerop (gimple_assign_rhs1 (stmt)))
1716 si = unshare_strinfo (si);
1717 si->length = build_int_cst (size_type_node, 0);
1718 si->endptr = NULL;
1719 si->prev = 0;
1720 si->next = 0;
1721 si->stmt = NULL;
1722 si->first = 0;
1723 si->writable = true;
1724 if (ssaname && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname))
1725 si->endptr = ssaname;
1726 si->dont_invalidate = true;
1728 /* If si->length is non-zero constant, we aren't overwriting '\0',
1729 and if we aren't storing '\0', we know that the length of the
1730 string and any other zero terminated string in memory remains
1731 the same. In that case we move to the next gimple statement and
1732 return to signal the caller that it shouldn't invalidate anything.
1734 This is benefical for cases like:
1736 char p[20];
1737 void foo (char *q)
1739 strcpy (p, "foobar");
1740 size_t len = strlen (p); // This can be optimized into 6
1741 size_t len2 = strlen (q); // This has to be computed
1742 p[0] = 'X';
1743 size_t len3 = strlen (p); // This can be optimized into 6
1744 size_t len4 = strlen (q); // This can be optimized into len2
1745 bar (len, len2, len3, len4);
1748 else if (si != NULL && si->length != NULL_TREE
1749 && TREE_CODE (si->length) == INTEGER_CST
1750 && integer_nonzerop (gimple_assign_rhs1 (stmt)))
1752 gsi_next (gsi);
1753 return false;
1756 else if (idx == 0 && initializer_zerop (gimple_assign_rhs1 (stmt)))
1758 if (ssaname)
1760 si = zero_length_string (ssaname, NULL);
1761 if (si != NULL)
1762 si->dont_invalidate = true;
1764 else
1766 int idx = new_addr_stridx (lhs);
1767 if (idx != 0)
1769 si = new_strinfo (build_fold_addr_expr (lhs), idx,
1770 build_int_cst (size_type_node, 0));
1771 set_strinfo (idx, si);
1772 si->dont_invalidate = true;
1775 if (si != NULL)
1776 si->writable = true;
1778 else if (idx == 0
1779 && TREE_CODE (gimple_assign_rhs1 (stmt)) == STRING_CST
1780 && ssaname == NULL_TREE
1781 && TREE_CODE (TREE_TYPE (lhs)) == ARRAY_TYPE)
1783 size_t l = strlen (TREE_STRING_POINTER (gimple_assign_rhs1 (stmt)));
1784 HOST_WIDE_INT a = int_size_in_bytes (TREE_TYPE (lhs));
1785 if (a > 0 && (unsigned HOST_WIDE_INT) a > l)
1787 int idx = new_addr_stridx (lhs);
1788 if (idx != 0)
1790 si = new_strinfo (build_fold_addr_expr (lhs), idx,
1791 build_int_cst (size_type_node, l));
1792 set_strinfo (idx, si);
1793 si->dont_invalidate = true;
1798 if (si != NULL && initializer_zerop (gimple_assign_rhs1 (stmt)))
1800 /* Allow adjust_last_stmt to remove it if the stored '\0'
1801 is immediately overwritten. */
1802 laststmt.stmt = stmt;
1803 laststmt.len = build_int_cst (size_type_node, 1);
1804 laststmt.stridx = si->idx;
1806 return true;
1809 /* Attempt to optimize a single statement at *GSI using string length
1810 knowledge. */
1812 static bool
1813 strlen_optimize_stmt (gimple_stmt_iterator *gsi)
1815 gimple stmt = gsi_stmt (*gsi);
1817 if (is_gimple_call (stmt))
1819 tree callee = gimple_call_fndecl (stmt);
1820 if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
1821 switch (DECL_FUNCTION_CODE (callee))
1823 case BUILT_IN_STRLEN:
1824 handle_builtin_strlen (gsi);
1825 break;
1826 case BUILT_IN_STRCHR:
1827 handle_builtin_strchr (gsi);
1828 break;
1829 case BUILT_IN_STRCPY:
1830 case BUILT_IN_STRCPY_CHK:
1831 case BUILT_IN_STPCPY:
1832 case BUILT_IN_STPCPY_CHK:
1833 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee), gsi);
1834 break;
1835 case BUILT_IN_MEMCPY:
1836 case BUILT_IN_MEMCPY_CHK:
1837 case BUILT_IN_MEMPCPY:
1838 case BUILT_IN_MEMPCPY_CHK:
1839 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi);
1840 break;
1841 case BUILT_IN_STRCAT:
1842 case BUILT_IN_STRCAT_CHK:
1843 handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi);
1844 break;
1845 default:
1846 break;
1849 else if (is_gimple_assign (stmt))
1851 tree lhs = gimple_assign_lhs (stmt);
1853 if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs)))
1855 if (gimple_assign_single_p (stmt)
1856 || (gimple_assign_cast_p (stmt)
1857 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))))
1859 int idx = get_stridx (gimple_assign_rhs1 (stmt));
1860 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = idx;
1862 else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
1863 handle_pointer_plus (gsi);
1865 else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
1867 tree type = TREE_TYPE (lhs);
1868 if (TREE_CODE (type) == ARRAY_TYPE)
1869 type = TREE_TYPE (type);
1870 if (TREE_CODE (type) == INTEGER_TYPE
1871 && TYPE_MODE (type) == TYPE_MODE (char_type_node)
1872 && TYPE_PRECISION (type) == TYPE_PRECISION (char_type_node))
1874 if (! handle_char_store (gsi))
1875 return false;
1880 if (gimple_vdef (stmt))
1881 maybe_invalidate (stmt);
1882 return true;
1885 /* Recursively call maybe_invalidate on stmts that might be executed
1886 in between dombb and current bb and that contain a vdef. Stop when
1887 *count stmts are inspected, or if the whole strinfo vector has
1888 been invalidated. */
1890 static void
1891 do_invalidate (basic_block dombb, gimple phi, bitmap visited, int *count)
1893 unsigned int i, n = gimple_phi_num_args (phi);
1895 for (i = 0; i < n; i++)
1897 tree vuse = gimple_phi_arg_def (phi, i);
1898 gimple stmt = SSA_NAME_DEF_STMT (vuse);
1899 basic_block bb = gimple_bb (stmt);
1900 if (bb == NULL
1901 || bb == dombb
1902 || !bitmap_set_bit (visited, bb->index)
1903 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
1904 continue;
1905 while (1)
1907 if (gimple_code (stmt) == GIMPLE_PHI)
1909 do_invalidate (dombb, stmt, visited, count);
1910 if (*count == 0)
1911 return;
1912 break;
1914 if (--*count == 0)
1915 return;
1916 if (!maybe_invalidate (stmt))
1918 *count = 0;
1919 return;
1921 vuse = gimple_vuse (stmt);
1922 stmt = SSA_NAME_DEF_STMT (vuse);
1923 if (gimple_bb (stmt) != bb)
1925 bb = gimple_bb (stmt);
1926 if (bb == NULL
1927 || bb == dombb
1928 || !bitmap_set_bit (visited, bb->index)
1929 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
1930 break;
1936 class strlen_dom_walker : public dom_walker
1938 public:
1939 strlen_dom_walker (cdi_direction direction) : dom_walker (direction) {}
1941 virtual void before_dom_children (basic_block);
1942 virtual void after_dom_children (basic_block);
1945 /* Callback for walk_dominator_tree. Attempt to optimize various
1946 string ops by remembering string lenths pointed by pointer SSA_NAMEs. */
1948 void
1949 strlen_dom_walker::before_dom_children (basic_block bb)
1951 gimple_stmt_iterator gsi;
1952 basic_block dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
1954 if (dombb == NULL)
1955 stridx_to_strinfo = NULL;
1956 else
1958 stridx_to_strinfo = ((vec<strinfo, va_heap, vl_embed> *) dombb->aux);
1959 if (stridx_to_strinfo)
1961 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1963 gimple phi = gsi_stmt (gsi);
1964 if (virtual_operand_p (gimple_phi_result (phi)))
1966 bitmap visited = BITMAP_ALLOC (NULL);
1967 int count_vdef = 100;
1968 do_invalidate (dombb, phi, visited, &count_vdef);
1969 BITMAP_FREE (visited);
1970 if (count_vdef == 0)
1972 /* If there were too many vdefs in between immediate
1973 dominator and current bb, invalidate everything.
1974 If stridx_to_strinfo has been unshared, we need
1975 to free it, otherwise just set it to NULL. */
1976 if (!strinfo_shared ())
1978 unsigned int i;
1979 strinfo si;
1981 for (i = 1;
1982 vec_safe_iterate (stridx_to_strinfo, i, &si);
1983 ++i)
1985 free_strinfo (si);
1986 (*stridx_to_strinfo)[i] = NULL;
1989 else
1990 stridx_to_strinfo = NULL;
1992 break;
1998 /* If all PHI arguments have the same string index, the PHI result
1999 has it as well. */
2000 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2002 gimple phi = gsi_stmt (gsi);
2003 tree result = gimple_phi_result (phi);
2004 if (!virtual_operand_p (result) && POINTER_TYPE_P (TREE_TYPE (result)))
2006 int idx = get_stridx (gimple_phi_arg_def (phi, 0));
2007 if (idx != 0)
2009 unsigned int i, n = gimple_phi_num_args (phi);
2010 for (i = 1; i < n; i++)
2011 if (idx != get_stridx (gimple_phi_arg_def (phi, i)))
2012 break;
2013 if (i == n)
2014 ssa_ver_to_stridx[SSA_NAME_VERSION (result)] = idx;
2019 /* Attempt to optimize individual statements. */
2020 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2021 if (strlen_optimize_stmt (&gsi))
2022 gsi_next (&gsi);
2024 bb->aux = stridx_to_strinfo;
2025 if (vec_safe_length (stridx_to_strinfo) && !strinfo_shared ())
2026 (*stridx_to_strinfo)[0] = (strinfo) bb;
2029 /* Callback for walk_dominator_tree. Free strinfo vector if it is
2030 owned by the current bb, clear bb->aux. */
2032 void
2033 strlen_dom_walker::after_dom_children (basic_block bb)
2035 if (bb->aux)
2037 stridx_to_strinfo = ((vec<strinfo, va_heap, vl_embed> *) bb->aux);
2038 if (vec_safe_length (stridx_to_strinfo)
2039 && (*stridx_to_strinfo)[0] == (strinfo) bb)
2041 unsigned int i;
2042 strinfo si;
2044 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
2045 free_strinfo (si);
2046 vec_free (stridx_to_strinfo);
2048 bb->aux = NULL;
2052 /* Main entry point. */
2054 static unsigned int
2055 tree_ssa_strlen (void)
2057 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
2058 max_stridx = 1;
2059 strinfo_pool = create_alloc_pool ("strinfo_struct pool",
2060 sizeof (struct strinfo_struct), 64);
2062 calculate_dominance_info (CDI_DOMINATORS);
2064 /* String length optimization is implemented as a walk of the dominator
2065 tree and a forward walk of statements within each block. */
2066 strlen_dom_walker (CDI_DOMINATORS).walk (cfun->cfg->x_entry_block_ptr);
2068 ssa_ver_to_stridx.release ();
2069 free_alloc_pool (strinfo_pool);
2070 if (decl_to_stridxlist_htab.is_created ())
2072 obstack_free (&stridx_obstack, NULL);
2073 decl_to_stridxlist_htab.dispose ();
2075 laststmt.stmt = NULL;
2076 laststmt.len = NULL_TREE;
2077 laststmt.stridx = 0;
2079 return 0;
2082 static bool
2083 gate_strlen (void)
2085 return flag_optimize_strlen != 0;
2088 namespace {
2090 const pass_data pass_data_strlen =
2092 GIMPLE_PASS, /* type */
2093 "strlen", /* name */
2094 OPTGROUP_NONE, /* optinfo_flags */
2095 true, /* has_gate */
2096 true, /* has_execute */
2097 TV_TREE_STRLEN, /* tv_id */
2098 ( PROP_cfg | PROP_ssa ), /* properties_required */
2099 0, /* properties_provided */
2100 0, /* properties_destroyed */
2101 0, /* todo_flags_start */
2102 TODO_verify_ssa, /* todo_flags_finish */
2105 class pass_strlen : public gimple_opt_pass
2107 public:
2108 pass_strlen (gcc::context *ctxt)
2109 : gimple_opt_pass (pass_data_strlen, ctxt)
2112 /* opt_pass methods: */
2113 bool gate () { return gate_strlen (); }
2114 unsigned int execute () { return tree_ssa_strlen (); }
2116 }; // class pass_strlen
2118 } // anon namespace
2120 gimple_opt_pass *
2121 make_pass_strlen (gcc::context *ctxt)
2123 return new pass_strlen (ctxt);