2014-12-20 Martin Uecker <uecker@eecs.berkeley.edu>
[official-gcc.git] / gcc / tree-ssa-strlen.c
blobc2f3493367f4c3a5e22e9e1ab9d6bc37816ec4ff
1 /* String length optimization
2 Copyright (C) 2011-2014 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 "stor-layout.h"
26 #include "hash-table.h"
27 #include "hash-map.h"
28 #include "bitmap.h"
29 #include "predict.h"
30 #include "vec.h"
31 #include "hashtab.h"
32 #include "hash-set.h"
33 #include "machmode.h"
34 #include "tm.h"
35 #include "hard-reg-set.h"
36 #include "input.h"
37 #include "function.h"
38 #include "dominance.h"
39 #include "cfg.h"
40 #include "basic-block.h"
41 #include "tree-ssa-alias.h"
42 #include "internal-fn.h"
43 #include "gimple-fold.h"
44 #include "tree-eh.h"
45 #include "gimple-expr.h"
46 #include "is-a.h"
47 #include "gimple.h"
48 #include "gimplify.h"
49 #include "gimple-iterator.h"
50 #include "gimplify-me.h"
51 #include "gimple-ssa.h"
52 #include "tree-phinodes.h"
53 #include "ssa-iterators.h"
54 #include "stringpool.h"
55 #include "tree-ssanames.h"
56 #include "expr.h"
57 #include "tree-dfa.h"
58 #include "tree-pass.h"
59 #include "domwalk.h"
60 #include "alloc-pool.h"
61 #include "tree-ssa-propagate.h"
62 #include "gimple-pretty-print.h"
63 #include "params.h"
64 #include "expr.h"
65 #include "plugin-api.h"
66 #include "ipa-ref.h"
67 #include "cgraph.h"
68 #include "ipa-chkp.h"
70 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
71 is an index into strinfo vector, negative value stands for
72 string length of a string literal (~strlen). */
73 static vec<int> ssa_ver_to_stridx;
75 /* Number of currently active string indexes plus one. */
76 static int max_stridx;
78 /* String information record. */
79 typedef struct strinfo_struct
81 /* String length of this string. */
82 tree length;
83 /* Any of the corresponding pointers for querying alias oracle. */
84 tree ptr;
85 /* Statement for delayed length computation. */
86 gimple stmt;
87 /* Pointer to '\0' if known, if NULL, it can be computed as
88 ptr + length. */
89 tree endptr;
90 /* Reference count. Any changes to strinfo entry possibly shared
91 with dominating basic blocks need unshare_strinfo first, except
92 for dont_invalidate which affects only the immediately next
93 maybe_invalidate. */
94 int refcount;
95 /* Copy of index. get_strinfo (si->idx) should return si; */
96 int idx;
97 /* These 3 fields are for chaining related string pointers together.
98 E.g. for
99 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
100 strcpy (c, d); e = c + dl;
101 strinfo(a) -> strinfo(c) -> strinfo(e)
102 All have ->first field equal to strinfo(a)->idx and are doubly
103 chained through prev/next fields. The later strinfos are required
104 to point into the same string with zero or more bytes after
105 the previous pointer and all bytes in between the two pointers
106 must be non-zero. Functions like strcpy or memcpy are supposed
107 to adjust all previous strinfo lengths, but not following strinfo
108 lengths (those are uncertain, usually invalidated during
109 maybe_invalidate, except when the alias oracle knows better).
110 Functions like strcat on the other side adjust the whole
111 related strinfo chain.
112 They are updated lazily, so to use the chain the same first fields
113 and si->prev->next == si->idx needs to be verified. */
114 int first;
115 int next;
116 int prev;
117 /* A flag whether the string is known to be written in the current
118 function. */
119 bool writable;
120 /* A flag for the next maybe_invalidate that this strinfo shouldn't
121 be invalidated. Always cleared by maybe_invalidate. */
122 bool dont_invalidate;
123 } *strinfo;
125 /* Pool for allocating strinfo_struct entries. */
126 static alloc_pool strinfo_pool;
128 /* Vector mapping positive string indexes to strinfo, for the
129 current basic block. The first pointer in the vector is special,
130 it is either NULL, meaning the vector isn't shared, or it is
131 a basic block pointer to the owner basic_block if shared.
132 If some other bb wants to modify the vector, the vector needs
133 to be unshared first, and only the owner bb is supposed to free it. */
134 static vec<strinfo, va_heap, vl_embed> *stridx_to_strinfo;
136 /* One OFFSET->IDX mapping. */
137 struct stridxlist
139 struct stridxlist *next;
140 HOST_WIDE_INT offset;
141 int idx;
144 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
145 struct decl_stridxlist_map
147 struct tree_map_base base;
148 struct stridxlist list;
151 /* stridxlist hashtable helpers. */
153 struct stridxlist_hash_traits : default_hashmap_traits
155 static inline hashval_t hash (tree);
158 /* Hash a from tree in a decl_stridxlist_map. */
160 inline hashval_t
161 stridxlist_hash_traits::hash (tree item)
163 return DECL_UID (item);
166 /* Hash table for mapping decls to a chained list of offset -> idx
167 mappings. */
168 static hash_map<tree, stridxlist, stridxlist_hash_traits>
169 *decl_to_stridxlist_htab;
171 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
172 static struct obstack stridx_obstack;
174 /* Last memcpy statement if it could be adjusted if the trailing
175 '\0' written is immediately overwritten, or
176 *x = '\0' store that could be removed if it is immediately overwritten. */
177 struct laststmt_struct
179 gimple stmt;
180 tree len;
181 int stridx;
182 } laststmt;
184 /* Helper function for get_stridx. */
186 static int
187 get_addr_stridx (tree exp)
189 HOST_WIDE_INT off;
190 struct stridxlist *list;
191 tree base;
193 if (!decl_to_stridxlist_htab)
194 return 0;
196 base = get_addr_base_and_unit_offset (exp, &off);
197 if (base == NULL || !DECL_P (base))
198 return 0;
200 list = decl_to_stridxlist_htab->get (base);
201 if (list == NULL)
202 return 0;
206 if (list->offset == off)
207 return list->idx;
208 list = list->next;
210 while (list);
211 return 0;
214 /* Return string index for EXP. */
216 static int
217 get_stridx (tree exp)
219 tree s, o;
221 if (TREE_CODE (exp) == SSA_NAME)
222 return ssa_ver_to_stridx[SSA_NAME_VERSION (exp)];
224 if (TREE_CODE (exp) == ADDR_EXPR)
226 int idx = get_addr_stridx (TREE_OPERAND (exp, 0));
227 if (idx != 0)
228 return idx;
231 s = string_constant (exp, &o);
232 if (s != NULL_TREE
233 && (o == NULL_TREE || tree_fits_shwi_p (o))
234 && TREE_STRING_LENGTH (s) > 0)
236 HOST_WIDE_INT offset = o ? tree_to_shwi (o) : 0;
237 const char *p = TREE_STRING_POINTER (s);
238 int max = TREE_STRING_LENGTH (s) - 1;
240 if (p[max] == '\0' && offset >= 0 && offset <= max)
241 return ~(int) strlen (p + offset);
243 return 0;
246 /* Return true if strinfo vector is shared with the immediate dominator. */
248 static inline bool
249 strinfo_shared (void)
251 return vec_safe_length (stridx_to_strinfo)
252 && (*stridx_to_strinfo)[0] != NULL;
255 /* Unshare strinfo vector that is shared with the immediate dominator. */
257 static void
258 unshare_strinfo_vec (void)
260 strinfo si;
261 unsigned int i = 0;
263 gcc_assert (strinfo_shared ());
264 stridx_to_strinfo = vec_safe_copy (stridx_to_strinfo);
265 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
266 if (si != NULL)
267 si->refcount++;
268 (*stridx_to_strinfo)[0] = NULL;
271 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
272 Return a pointer to the location where the string index can
273 be stored (if 0) or is stored, or NULL if this can't be tracked. */
275 static int *
276 addr_stridxptr (tree exp)
278 HOST_WIDE_INT off;
280 tree base = get_addr_base_and_unit_offset (exp, &off);
281 if (base == NULL_TREE || !DECL_P (base))
282 return NULL;
284 if (!decl_to_stridxlist_htab)
286 decl_to_stridxlist_htab
287 = new hash_map<tree, stridxlist, stridxlist_hash_traits> (64);
288 gcc_obstack_init (&stridx_obstack);
291 bool existed;
292 stridxlist *list = &decl_to_stridxlist_htab->get_or_insert (base, &existed);
293 if (existed)
295 int i;
296 for (i = 0; i < 16; i++)
298 if (list->offset == off)
299 return &list->idx;
300 if (list->next == NULL)
301 break;
303 if (i == 16)
304 return NULL;
305 list->next = XOBNEW (&stridx_obstack, struct stridxlist);
306 list = list->next;
309 list->next = NULL;
310 list->offset = off;
311 list->idx = 0;
312 return &list->idx;
315 /* Create a new string index, or return 0 if reached limit. */
317 static int
318 new_stridx (tree exp)
320 int idx;
321 if (max_stridx >= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS))
322 return 0;
323 if (TREE_CODE (exp) == SSA_NAME)
325 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp))
326 return 0;
327 idx = max_stridx++;
328 ssa_ver_to_stridx[SSA_NAME_VERSION (exp)] = idx;
329 return idx;
331 if (TREE_CODE (exp) == ADDR_EXPR)
333 int *pidx = addr_stridxptr (TREE_OPERAND (exp, 0));
334 if (pidx != NULL)
336 gcc_assert (*pidx == 0);
337 *pidx = max_stridx++;
338 return *pidx;
341 return 0;
344 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
346 static int
347 new_addr_stridx (tree exp)
349 int *pidx;
350 if (max_stridx >= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS))
351 return 0;
352 pidx = addr_stridxptr (exp);
353 if (pidx != NULL)
355 gcc_assert (*pidx == 0);
356 *pidx = max_stridx++;
357 return *pidx;
359 return 0;
362 /* Create a new strinfo. */
364 static strinfo
365 new_strinfo (tree ptr, int idx, tree length)
367 strinfo si = (strinfo) pool_alloc (strinfo_pool);
368 si->length = length;
369 si->ptr = ptr;
370 si->stmt = NULL;
371 si->endptr = NULL_TREE;
372 si->refcount = 1;
373 si->idx = idx;
374 si->first = 0;
375 si->prev = 0;
376 si->next = 0;
377 si->writable = false;
378 si->dont_invalidate = false;
379 return si;
382 /* Decrease strinfo refcount and free it if not referenced anymore. */
384 static inline void
385 free_strinfo (strinfo si)
387 if (si && --si->refcount == 0)
388 pool_free (strinfo_pool, si);
391 /* Return strinfo vector entry IDX. */
393 static inline strinfo
394 get_strinfo (int idx)
396 if (vec_safe_length (stridx_to_strinfo) <= (unsigned int) idx)
397 return NULL;
398 return (*stridx_to_strinfo)[idx];
401 /* Set strinfo in the vector entry IDX to SI. */
403 static inline void
404 set_strinfo (int idx, strinfo si)
406 if (vec_safe_length (stridx_to_strinfo) && (*stridx_to_strinfo)[0])
407 unshare_strinfo_vec ();
408 if (vec_safe_length (stridx_to_strinfo) <= (unsigned int) idx)
409 vec_safe_grow_cleared (stridx_to_strinfo, idx + 1);
410 (*stridx_to_strinfo)[idx] = si;
413 /* Return string length, or NULL if it can't be computed. */
415 static tree
416 get_string_length (strinfo si)
418 if (si->length)
419 return si->length;
421 if (si->stmt)
423 gimple stmt = si->stmt, lenstmt;
424 bool with_bounds = gimple_call_with_bounds_p (stmt);
425 tree callee, lhs, fn, tem;
426 location_t loc;
427 gimple_stmt_iterator gsi;
429 gcc_assert (is_gimple_call (stmt));
430 callee = gimple_call_fndecl (stmt);
431 gcc_assert (callee && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL);
432 lhs = gimple_call_lhs (stmt);
433 /* unshare_strinfo is intentionally not called here. The (delayed)
434 transformation of strcpy or strcat into stpcpy is done at the place
435 of the former strcpy/strcat call and so can affect all the strinfos
436 with the same stmt. If they were unshared before and transformation
437 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
438 just compute the right length. */
439 switch (DECL_FUNCTION_CODE (callee))
441 case BUILT_IN_STRCAT:
442 case BUILT_IN_STRCAT_CHK:
443 case BUILT_IN_STRCAT_CHKP:
444 case BUILT_IN_STRCAT_CHK_CHKP:
445 gsi = gsi_for_stmt (stmt);
446 fn = builtin_decl_implicit (BUILT_IN_STRLEN);
447 gcc_assert (lhs == NULL_TREE);
448 tem = unshare_expr (gimple_call_arg (stmt, 0));
449 if (with_bounds)
451 lenstmt = gimple_build_call (chkp_maybe_create_clone (fn)->decl,
452 2, tem, gimple_call_arg (stmt, 1));
453 gimple_call_set_with_bounds (lenstmt, true);
455 else
456 lenstmt = gimple_build_call (fn, 1, tem);
457 lhs = make_ssa_name (TREE_TYPE (TREE_TYPE (fn)), lenstmt);
458 gimple_call_set_lhs (lenstmt, lhs);
459 gimple_set_vuse (lenstmt, gimple_vuse (stmt));
460 gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT);
461 tem = gimple_call_arg (stmt, 0);
462 if (!ptrofftype_p (TREE_TYPE (lhs)))
464 lhs = convert_to_ptrofftype (lhs);
465 lhs = force_gimple_operand_gsi (&gsi, lhs, true, NULL_TREE,
466 true, GSI_SAME_STMT);
468 lenstmt = gimple_build_assign
469 (make_ssa_name (TREE_TYPE (gimple_call_arg (stmt, 0))),
470 POINTER_PLUS_EXPR,tem, lhs);
471 gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT);
472 gimple_call_set_arg (stmt, 0, gimple_assign_lhs (lenstmt));
473 lhs = NULL_TREE;
474 /* FALLTHRU */
475 case BUILT_IN_STRCPY:
476 case BUILT_IN_STRCPY_CHK:
477 case BUILT_IN_STRCPY_CHKP:
478 case BUILT_IN_STRCPY_CHK_CHKP:
479 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY));
480 if (gimple_call_num_args (stmt) == (with_bounds ? 4 : 2))
481 fn = builtin_decl_implicit (BUILT_IN_STPCPY);
482 else
483 fn = builtin_decl_explicit (BUILT_IN_STPCPY_CHK);
484 if (with_bounds)
485 fn = chkp_maybe_create_clone (fn)->decl;
486 gcc_assert (lhs == NULL_TREE);
487 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
489 fprintf (dump_file, "Optimizing: ");
490 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
492 gimple_call_set_fndecl (stmt, fn);
493 lhs = make_ssa_name (TREE_TYPE (TREE_TYPE (fn)), stmt);
494 gimple_call_set_lhs (stmt, lhs);
495 update_stmt (stmt);
496 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
498 fprintf (dump_file, "into: ");
499 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
501 /* FALLTHRU */
502 case BUILT_IN_STPCPY:
503 case BUILT_IN_STPCPY_CHK:
504 case BUILT_IN_STPCPY_CHKP:
505 case BUILT_IN_STPCPY_CHK_CHKP:
506 gcc_assert (lhs != NULL_TREE);
507 loc = gimple_location (stmt);
508 si->endptr = lhs;
509 si->stmt = NULL;
510 lhs = fold_convert_loc (loc, size_type_node, lhs);
511 si->length = fold_convert_loc (loc, size_type_node, si->ptr);
512 si->length = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
513 lhs, si->length);
514 break;
515 case BUILT_IN_MALLOC:
516 break;
517 /* BUILT_IN_CALLOC always has si->length set. */
518 default:
519 gcc_unreachable ();
520 break;
524 return si->length;
527 /* Invalidate string length information for strings whose length
528 might change due to stores in stmt. */
530 static bool
531 maybe_invalidate (gimple stmt)
533 strinfo si;
534 unsigned int i;
535 bool nonempty = false;
537 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
538 if (si != NULL)
540 if (!si->dont_invalidate)
542 ao_ref r;
543 /* Do not use si->length. */
544 ao_ref_init_from_ptr_and_size (&r, si->ptr, NULL_TREE);
545 if (stmt_may_clobber_ref_p_1 (stmt, &r))
547 set_strinfo (i, NULL);
548 free_strinfo (si);
549 continue;
552 si->dont_invalidate = false;
553 nonempty = true;
555 return nonempty;
558 /* Unshare strinfo record SI, if it has recount > 1 or
559 if stridx_to_strinfo vector is shared with some other
560 bbs. */
562 static strinfo
563 unshare_strinfo (strinfo si)
565 strinfo nsi;
567 if (si->refcount == 1 && !strinfo_shared ())
568 return si;
570 nsi = new_strinfo (si->ptr, si->idx, si->length);
571 nsi->stmt = si->stmt;
572 nsi->endptr = si->endptr;
573 nsi->first = si->first;
574 nsi->prev = si->prev;
575 nsi->next = si->next;
576 nsi->writable = si->writable;
577 set_strinfo (si->idx, nsi);
578 free_strinfo (si);
579 return nsi;
582 /* Return first strinfo in the related strinfo chain
583 if all strinfos in between belong to the chain, otherwise
584 NULL. */
586 static strinfo
587 verify_related_strinfos (strinfo origsi)
589 strinfo si = origsi, psi;
591 if (origsi->first == 0)
592 return NULL;
593 for (; si->prev; si = psi)
595 if (si->first != origsi->first)
596 return NULL;
597 psi = get_strinfo (si->prev);
598 if (psi == NULL)
599 return NULL;
600 if (psi->next != si->idx)
601 return NULL;
603 if (si->idx != si->first)
604 return NULL;
605 return si;
608 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
609 to a zero-length string and if possible chain it to a related strinfo
610 chain whose part is or might be CHAINSI. */
612 static strinfo
613 zero_length_string (tree ptr, strinfo chainsi)
615 strinfo si;
616 int idx;
617 gcc_checking_assert (TREE_CODE (ptr) == SSA_NAME
618 && get_stridx (ptr) == 0);
620 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
621 return NULL;
622 if (chainsi != NULL)
624 si = verify_related_strinfos (chainsi);
625 if (si)
627 chainsi = si;
628 for (; chainsi->next; chainsi = si)
630 if (chainsi->endptr == NULL_TREE)
632 chainsi = unshare_strinfo (chainsi);
633 chainsi->endptr = ptr;
635 si = get_strinfo (chainsi->next);
636 if (si == NULL
637 || si->first != chainsi->first
638 || si->prev != chainsi->idx)
639 break;
641 gcc_assert (chainsi->length || chainsi->stmt);
642 if (chainsi->endptr == NULL_TREE)
644 chainsi = unshare_strinfo (chainsi);
645 chainsi->endptr = ptr;
647 if (chainsi->length && integer_zerop (chainsi->length))
649 if (chainsi->next)
651 chainsi = unshare_strinfo (chainsi);
652 chainsi->next = 0;
654 ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = chainsi->idx;
655 return chainsi;
658 else if (chainsi->first || chainsi->prev || chainsi->next)
660 chainsi = unshare_strinfo (chainsi);
661 chainsi->first = 0;
662 chainsi->prev = 0;
663 chainsi->next = 0;
666 idx = new_stridx (ptr);
667 if (idx == 0)
668 return NULL;
669 si = new_strinfo (ptr, idx, build_int_cst (size_type_node, 0));
670 set_strinfo (idx, si);
671 si->endptr = ptr;
672 if (chainsi != NULL)
674 chainsi = unshare_strinfo (chainsi);
675 if (chainsi->first == 0)
676 chainsi->first = chainsi->idx;
677 chainsi->next = idx;
678 if (chainsi->endptr == NULL_TREE)
679 chainsi->endptr = ptr;
680 si->prev = chainsi->idx;
681 si->first = chainsi->first;
682 si->writable = chainsi->writable;
684 return si;
687 /* For strinfo ORIGSI whose length has been just updated
688 update also related strinfo lengths (add ADJ to each,
689 but don't adjust ORIGSI). */
691 static void
692 adjust_related_strinfos (location_t loc, strinfo origsi, tree adj)
694 strinfo si = verify_related_strinfos (origsi);
696 if (si == NULL)
697 return;
699 while (1)
701 strinfo nsi;
703 if (si != origsi)
705 tree tem;
707 si = unshare_strinfo (si);
708 if (si->length)
710 tem = fold_convert_loc (loc, TREE_TYPE (si->length), adj);
711 si->length = fold_build2_loc (loc, PLUS_EXPR,
712 TREE_TYPE (si->length), si->length,
713 tem);
715 else if (si->stmt != NULL)
716 /* Delayed length computation is unaffected. */
718 else
719 gcc_unreachable ();
721 si->endptr = NULL_TREE;
722 si->dont_invalidate = true;
724 if (si->next == 0)
725 return;
726 nsi = get_strinfo (si->next);
727 if (nsi == NULL
728 || nsi->first != si->first
729 || nsi->prev != si->idx)
730 return;
731 si = nsi;
735 /* Find if there are other SSA_NAME pointers equal to PTR
736 for which we don't track their string lengths yet. If so, use
737 IDX for them. */
739 static void
740 find_equal_ptrs (tree ptr, int idx)
742 if (TREE_CODE (ptr) != SSA_NAME)
743 return;
744 while (1)
746 gimple stmt = SSA_NAME_DEF_STMT (ptr);
747 if (!is_gimple_assign (stmt))
748 return;
749 ptr = gimple_assign_rhs1 (stmt);
750 switch (gimple_assign_rhs_code (stmt))
752 case SSA_NAME:
753 break;
754 CASE_CONVERT:
755 if (!POINTER_TYPE_P (TREE_TYPE (ptr)))
756 return;
757 if (TREE_CODE (ptr) == SSA_NAME)
758 break;
759 if (TREE_CODE (ptr) != ADDR_EXPR)
760 return;
761 /* FALLTHRU */
762 case ADDR_EXPR:
764 int *pidx = addr_stridxptr (TREE_OPERAND (ptr, 0));
765 if (pidx != NULL && *pidx == 0)
766 *pidx = idx;
767 return;
769 default:
770 return;
773 /* We might find an endptr created in this pass. Grow the
774 vector in that case. */
775 if (ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
776 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
778 if (ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] != 0)
779 return;
780 ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = idx;
784 /* If the last .MEM setter statement before STMT is
785 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
786 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
787 just memcpy (x, y, strlen (y)). SI must be the zero length
788 strinfo. */
790 static void
791 adjust_last_stmt (strinfo si, gimple stmt, bool is_strcat)
793 tree vuse, callee, len;
794 struct laststmt_struct last = laststmt;
795 strinfo lastsi, firstsi;
796 unsigned len_arg_no = 2;
798 laststmt.stmt = NULL;
799 laststmt.len = NULL_TREE;
800 laststmt.stridx = 0;
802 if (last.stmt == NULL)
803 return;
805 vuse = gimple_vuse (stmt);
806 if (vuse == NULL_TREE
807 || SSA_NAME_DEF_STMT (vuse) != last.stmt
808 || !has_single_use (vuse))
809 return;
811 gcc_assert (last.stridx > 0);
812 lastsi = get_strinfo (last.stridx);
813 if (lastsi == NULL)
814 return;
816 if (lastsi != si)
818 if (lastsi->first == 0 || lastsi->first != si->first)
819 return;
821 firstsi = verify_related_strinfos (si);
822 if (firstsi == NULL)
823 return;
824 while (firstsi != lastsi)
826 strinfo nextsi;
827 if (firstsi->next == 0)
828 return;
829 nextsi = get_strinfo (firstsi->next);
830 if (nextsi == NULL
831 || nextsi->prev != firstsi->idx
832 || nextsi->first != si->first)
833 return;
834 firstsi = nextsi;
838 if (!is_strcat)
840 if (si->length == NULL_TREE || !integer_zerop (si->length))
841 return;
844 if (is_gimple_assign (last.stmt))
846 gimple_stmt_iterator gsi;
848 if (!integer_zerop (gimple_assign_rhs1 (last.stmt)))
849 return;
850 if (stmt_could_throw_p (last.stmt))
851 return;
852 gsi = gsi_for_stmt (last.stmt);
853 unlink_stmt_vdef (last.stmt);
854 release_defs (last.stmt);
855 gsi_remove (&gsi, true);
856 return;
859 if (!gimple_call_builtin_p (last.stmt, BUILT_IN_NORMAL))
860 return;
862 callee = gimple_call_fndecl (last.stmt);
863 switch (DECL_FUNCTION_CODE (callee))
865 case BUILT_IN_MEMCPY:
866 case BUILT_IN_MEMCPY_CHK:
867 break;
868 case BUILT_IN_MEMCPY_CHKP:
869 case BUILT_IN_MEMCPY_CHK_CHKP:
870 len_arg_no = 4;
871 break;
872 default:
873 return;
876 len = gimple_call_arg (last.stmt, len_arg_no);
877 if (tree_fits_uhwi_p (len))
879 if (!tree_fits_uhwi_p (last.len)
880 || integer_zerop (len)
881 || tree_to_uhwi (len) != tree_to_uhwi (last.len) + 1)
882 return;
883 /* Don't adjust the length if it is divisible by 4, it is more efficient
884 to store the extra '\0' in that case. */
885 if ((tree_to_uhwi (len) & 3) == 0)
886 return;
888 else if (TREE_CODE (len) == SSA_NAME)
890 gimple def_stmt = SSA_NAME_DEF_STMT (len);
891 if (!is_gimple_assign (def_stmt)
892 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
893 || gimple_assign_rhs1 (def_stmt) != last.len
894 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
895 return;
897 else
898 return;
900 gimple_call_set_arg (last.stmt, len_arg_no, last.len);
901 update_stmt (last.stmt);
904 /* Handle a strlen call. If strlen of the argument is known, replace
905 the strlen call with the known value, otherwise remember that strlen
906 of the argument is stored in the lhs SSA_NAME. */
908 static void
909 handle_builtin_strlen (gimple_stmt_iterator *gsi)
911 int idx;
912 tree src;
913 gimple stmt = gsi_stmt (*gsi);
914 tree lhs = gimple_call_lhs (stmt);
916 if (lhs == NULL_TREE)
917 return;
919 src = gimple_call_arg (stmt, 0);
920 idx = get_stridx (src);
921 if (idx)
923 strinfo si = NULL;
924 tree rhs;
926 if (idx < 0)
927 rhs = build_int_cst (TREE_TYPE (lhs), ~idx);
928 else
930 rhs = NULL_TREE;
931 si = get_strinfo (idx);
932 if (si != NULL)
933 rhs = get_string_length (si);
935 if (rhs != NULL_TREE)
937 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
939 fprintf (dump_file, "Optimizing: ");
940 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
942 rhs = unshare_expr (rhs);
943 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
944 rhs = fold_convert_loc (gimple_location (stmt),
945 TREE_TYPE (lhs), rhs);
946 if (!update_call_from_tree (gsi, rhs))
947 gimplify_and_update_call_from_tree (gsi, rhs);
948 stmt = gsi_stmt (*gsi);
949 update_stmt (stmt);
950 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
952 fprintf (dump_file, "into: ");
953 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
955 if (si != NULL
956 && TREE_CODE (si->length) != SSA_NAME
957 && TREE_CODE (si->length) != INTEGER_CST
958 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
960 si = unshare_strinfo (si);
961 si->length = lhs;
963 return;
966 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
967 return;
968 if (idx == 0)
969 idx = new_stridx (src);
970 else if (get_strinfo (idx) != NULL)
971 return;
972 if (idx)
974 strinfo si = new_strinfo (src, idx, lhs);
975 set_strinfo (idx, si);
976 find_equal_ptrs (src, idx);
980 /* Handle a strchr call. If strlen of the first argument is known, replace
981 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
982 that lhs of the call is endptr and strlen of the argument is endptr - x. */
984 static void
985 handle_builtin_strchr (gimple_stmt_iterator *gsi)
987 int idx;
988 tree src;
989 gimple stmt = gsi_stmt (*gsi);
990 tree lhs = gimple_call_lhs (stmt);
991 bool with_bounds = gimple_call_with_bounds_p (stmt);
993 if (lhs == NULL_TREE)
994 return;
996 if (!integer_zerop (gimple_call_arg (stmt, with_bounds ? 2 : 1)))
997 return;
999 src = gimple_call_arg (stmt, 0);
1000 idx = get_stridx (src);
1001 if (idx)
1003 strinfo si = NULL;
1004 tree rhs;
1006 if (idx < 0)
1007 rhs = build_int_cst (size_type_node, ~idx);
1008 else
1010 rhs = NULL_TREE;
1011 si = get_strinfo (idx);
1012 if (si != NULL)
1013 rhs = get_string_length (si);
1015 if (rhs != NULL_TREE)
1017 location_t loc = gimple_location (stmt);
1019 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1021 fprintf (dump_file, "Optimizing: ");
1022 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1024 if (si != NULL && si->endptr != NULL_TREE)
1026 rhs = unshare_expr (si->endptr);
1027 if (!useless_type_conversion_p (TREE_TYPE (lhs),
1028 TREE_TYPE (rhs)))
1029 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
1031 else
1033 rhs = fold_convert_loc (loc, sizetype, unshare_expr (rhs));
1034 rhs = fold_build2_loc (loc, POINTER_PLUS_EXPR,
1035 TREE_TYPE (src), src, rhs);
1036 if (!useless_type_conversion_p (TREE_TYPE (lhs),
1037 TREE_TYPE (rhs)))
1038 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
1040 if (!update_call_from_tree (gsi, rhs))
1041 gimplify_and_update_call_from_tree (gsi, rhs);
1042 stmt = gsi_stmt (*gsi);
1043 update_stmt (stmt);
1044 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1046 fprintf (dump_file, "into: ");
1047 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1049 if (si != NULL
1050 && si->endptr == NULL_TREE
1051 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1053 si = unshare_strinfo (si);
1054 si->endptr = lhs;
1056 zero_length_string (lhs, si);
1057 return;
1060 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1061 return;
1062 if (TREE_CODE (src) != SSA_NAME || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src))
1064 if (idx == 0)
1065 idx = new_stridx (src);
1066 else if (get_strinfo (idx) != NULL)
1068 zero_length_string (lhs, NULL);
1069 return;
1071 if (idx)
1073 location_t loc = gimple_location (stmt);
1074 tree lhsu = fold_convert_loc (loc, size_type_node, lhs);
1075 tree srcu = fold_convert_loc (loc, size_type_node, src);
1076 tree length = fold_build2_loc (loc, MINUS_EXPR,
1077 size_type_node, lhsu, srcu);
1078 strinfo si = new_strinfo (src, idx, length);
1079 si->endptr = lhs;
1080 set_strinfo (idx, si);
1081 find_equal_ptrs (src, idx);
1082 zero_length_string (lhs, si);
1085 else
1086 zero_length_string (lhs, NULL);
1089 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1090 If strlen of the second argument is known, strlen of the first argument
1091 is the same after this call. Furthermore, attempt to convert it to
1092 memcpy. */
1094 static void
1095 handle_builtin_strcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1097 int idx, didx;
1098 tree src, dst, srclen, len, lhs, args, type, fn, oldlen;
1099 bool success;
1100 gimple stmt = gsi_stmt (*gsi);
1101 strinfo si, dsi, olddsi, zsi;
1102 location_t loc;
1103 bool with_bounds = gimple_call_with_bounds_p (stmt);
1105 src = gimple_call_arg (stmt, with_bounds ? 2 : 1);
1106 dst = gimple_call_arg (stmt, 0);
1107 lhs = gimple_call_lhs (stmt);
1108 idx = get_stridx (src);
1109 si = NULL;
1110 if (idx > 0)
1111 si = get_strinfo (idx);
1113 didx = get_stridx (dst);
1114 olddsi = NULL;
1115 oldlen = NULL_TREE;
1116 if (didx > 0)
1117 olddsi = get_strinfo (didx);
1118 else if (didx < 0)
1119 return;
1121 if (olddsi != NULL)
1122 adjust_last_stmt (olddsi, stmt, false);
1124 srclen = NULL_TREE;
1125 if (si != NULL)
1126 srclen = get_string_length (si);
1127 else if (idx < 0)
1128 srclen = build_int_cst (size_type_node, ~idx);
1130 loc = gimple_location (stmt);
1131 if (srclen == NULL_TREE)
1132 switch (bcode)
1134 case BUILT_IN_STRCPY:
1135 case BUILT_IN_STRCPY_CHK:
1136 case BUILT_IN_STRCPY_CHKP:
1137 case BUILT_IN_STRCPY_CHK_CHKP:
1138 if (lhs != NULL_TREE || !builtin_decl_implicit_p (BUILT_IN_STPCPY))
1139 return;
1140 break;
1141 case BUILT_IN_STPCPY:
1142 case BUILT_IN_STPCPY_CHK:
1143 case BUILT_IN_STPCPY_CHKP:
1144 case BUILT_IN_STPCPY_CHK_CHKP:
1145 if (lhs == NULL_TREE)
1146 return;
1147 else
1149 tree lhsuint = fold_convert_loc (loc, size_type_node, lhs);
1150 srclen = fold_convert_loc (loc, size_type_node, dst);
1151 srclen = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
1152 lhsuint, srclen);
1154 break;
1155 default:
1156 gcc_unreachable ();
1159 if (didx == 0)
1161 didx = new_stridx (dst);
1162 if (didx == 0)
1163 return;
1165 if (olddsi != NULL)
1167 oldlen = olddsi->length;
1168 dsi = unshare_strinfo (olddsi);
1169 dsi->length = srclen;
1170 /* Break the chain, so adjust_related_strinfo on later pointers in
1171 the chain won't adjust this one anymore. */
1172 dsi->next = 0;
1173 dsi->stmt = NULL;
1174 dsi->endptr = NULL_TREE;
1176 else
1178 dsi = new_strinfo (dst, didx, srclen);
1179 set_strinfo (didx, dsi);
1180 find_equal_ptrs (dst, didx);
1182 dsi->writable = true;
1183 dsi->dont_invalidate = true;
1185 if (dsi->length == NULL_TREE)
1187 strinfo chainsi;
1189 /* If string length of src is unknown, use delayed length
1190 computation. If string lenth of dst will be needed, it
1191 can be computed by transforming this strcpy call into
1192 stpcpy and subtracting dst from the return value. */
1194 /* Look for earlier strings whose length could be determined if
1195 this strcpy is turned into an stpcpy. */
1197 if (dsi->prev != 0 && (chainsi = verify_related_strinfos (dsi)) != NULL)
1199 for (; chainsi && chainsi != dsi; chainsi = get_strinfo (chainsi->next))
1201 /* When setting a stmt for delayed length computation
1202 prevent all strinfos through dsi from being
1203 invalidated. */
1204 chainsi = unshare_strinfo (chainsi);
1205 chainsi->stmt = stmt;
1206 chainsi->length = NULL_TREE;
1207 chainsi->endptr = NULL_TREE;
1208 chainsi->dont_invalidate = true;
1211 dsi->stmt = stmt;
1212 return;
1215 if (olddsi != NULL)
1217 tree adj = NULL_TREE;
1218 if (oldlen == NULL_TREE)
1220 else if (integer_zerop (oldlen))
1221 adj = srclen;
1222 else if (TREE_CODE (oldlen) == INTEGER_CST
1223 || TREE_CODE (srclen) == INTEGER_CST)
1224 adj = fold_build2_loc (loc, MINUS_EXPR,
1225 TREE_TYPE (srclen), srclen,
1226 fold_convert_loc (loc, TREE_TYPE (srclen),
1227 oldlen));
1228 if (adj != NULL_TREE)
1229 adjust_related_strinfos (loc, dsi, adj);
1230 else
1231 dsi->prev = 0;
1233 /* strcpy src may not overlap dst, so src doesn't need to be
1234 invalidated either. */
1235 if (si != NULL)
1236 si->dont_invalidate = true;
1238 fn = NULL_TREE;
1239 zsi = NULL;
1240 switch (bcode)
1242 case BUILT_IN_STRCPY:
1243 case BUILT_IN_STRCPY_CHKP:
1244 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1245 if (lhs)
1246 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
1247 break;
1248 case BUILT_IN_STRCPY_CHK:
1249 case BUILT_IN_STRCPY_CHK_CHKP:
1250 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK);
1251 if (lhs)
1252 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
1253 break;
1254 case BUILT_IN_STPCPY:
1255 case BUILT_IN_STPCPY_CHKP:
1256 /* This would need adjustment of the lhs (subtract one),
1257 or detection that the trailing '\0' doesn't need to be
1258 written, if it will be immediately overwritten.
1259 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1260 if (lhs)
1262 dsi->endptr = lhs;
1263 zsi = zero_length_string (lhs, dsi);
1265 break;
1266 case BUILT_IN_STPCPY_CHK:
1267 case BUILT_IN_STPCPY_CHK_CHKP:
1268 /* This would need adjustment of the lhs (subtract one),
1269 or detection that the trailing '\0' doesn't need to be
1270 written, if it will be immediately overwritten.
1271 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1272 if (lhs)
1274 dsi->endptr = lhs;
1275 zsi = zero_length_string (lhs, dsi);
1277 break;
1278 default:
1279 gcc_unreachable ();
1281 if (zsi != NULL)
1282 zsi->dont_invalidate = true;
1284 if (fn == NULL_TREE)
1285 return;
1287 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1288 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1290 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1291 len = fold_build2_loc (loc, PLUS_EXPR, type, len, build_int_cst (type, 1));
1292 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1293 GSI_SAME_STMT);
1294 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1296 fprintf (dump_file, "Optimizing: ");
1297 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1299 if (with_bounds)
1301 fn = chkp_maybe_create_clone (fn)->decl;
1302 if (gimple_call_num_args (stmt) == 4)
1303 success = update_gimple_call (gsi, fn, 5, dst,
1304 gimple_call_arg (stmt, 1),
1305 src,
1306 gimple_call_arg (stmt, 3),
1307 len);
1308 else
1309 success = update_gimple_call (gsi, fn, 6, dst,
1310 gimple_call_arg (stmt, 1),
1311 src,
1312 gimple_call_arg (stmt, 3),
1313 len,
1314 gimple_call_arg (stmt, 4));
1316 else
1317 if (gimple_call_num_args (stmt) == 2)
1318 success = update_gimple_call (gsi, fn, 3, dst, src, len);
1319 else
1320 success = update_gimple_call (gsi, fn, 4, dst, src, len,
1321 gimple_call_arg (stmt, 2));
1322 if (success)
1324 stmt = gsi_stmt (*gsi);
1325 gimple_call_set_with_bounds (stmt, with_bounds);
1326 update_stmt (stmt);
1327 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1329 fprintf (dump_file, "into: ");
1330 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1332 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1333 laststmt.stmt = stmt;
1334 laststmt.len = srclen;
1335 laststmt.stridx = dsi->idx;
1337 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1338 fprintf (dump_file, "not possible.\n");
1341 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1342 If strlen of the second argument is known and length of the third argument
1343 is that plus one, strlen of the first argument is the same after this
1344 call. */
1346 static void
1347 handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1349 int idx, didx;
1350 tree src, dst, len, lhs, oldlen, newlen;
1351 gimple stmt = gsi_stmt (*gsi);
1352 strinfo si, dsi, olddsi;
1353 bool with_bounds = gimple_call_with_bounds_p (stmt);
1355 len = gimple_call_arg (stmt, with_bounds ? 4 : 2);
1356 src = gimple_call_arg (stmt, with_bounds ? 2 : 1);
1357 dst = gimple_call_arg (stmt, 0);
1358 idx = get_stridx (src);
1359 if (idx == 0)
1360 return;
1362 didx = get_stridx (dst);
1363 olddsi = NULL;
1364 if (didx > 0)
1365 olddsi = get_strinfo (didx);
1366 else if (didx < 0)
1367 return;
1369 if (olddsi != NULL
1370 && tree_fits_uhwi_p (len)
1371 && !integer_zerop (len))
1372 adjust_last_stmt (olddsi, stmt, false);
1374 if (idx > 0)
1376 gimple def_stmt;
1378 /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */
1379 si = get_strinfo (idx);
1380 if (si == NULL || si->length == NULL_TREE)
1381 return;
1382 if (TREE_CODE (len) != SSA_NAME)
1383 return;
1384 def_stmt = SSA_NAME_DEF_STMT (len);
1385 if (!is_gimple_assign (def_stmt)
1386 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
1387 || gimple_assign_rhs1 (def_stmt) != si->length
1388 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
1389 return;
1391 else
1393 si = NULL;
1394 /* Handle memcpy (x, "abcd", 5) or
1395 memcpy (x, "abc\0uvw", 7). */
1396 if (!tree_fits_uhwi_p (len)
1397 || tree_to_uhwi (len) <= (unsigned HOST_WIDE_INT) ~idx)
1398 return;
1401 if (olddsi != NULL && TREE_CODE (len) == SSA_NAME)
1402 adjust_last_stmt (olddsi, stmt, false);
1404 if (didx == 0)
1406 didx = new_stridx (dst);
1407 if (didx == 0)
1408 return;
1410 if (si != NULL)
1411 newlen = si->length;
1412 else
1413 newlen = build_int_cst (size_type_node, ~idx);
1414 oldlen = NULL_TREE;
1415 if (olddsi != NULL)
1417 dsi = unshare_strinfo (olddsi);
1418 oldlen = olddsi->length;
1419 dsi->length = newlen;
1420 /* Break the chain, so adjust_related_strinfo on later pointers in
1421 the chain won't adjust this one anymore. */
1422 dsi->next = 0;
1423 dsi->stmt = NULL;
1424 dsi->endptr = NULL_TREE;
1426 else
1428 dsi = new_strinfo (dst, didx, newlen);
1429 set_strinfo (didx, dsi);
1430 find_equal_ptrs (dst, didx);
1432 dsi->writable = true;
1433 dsi->dont_invalidate = true;
1434 if (olddsi != NULL)
1436 tree adj = NULL_TREE;
1437 location_t loc = gimple_location (stmt);
1438 if (oldlen == NULL_TREE)
1440 else if (integer_zerop (oldlen))
1441 adj = dsi->length;
1442 else if (TREE_CODE (oldlen) == INTEGER_CST
1443 || TREE_CODE (dsi->length) == INTEGER_CST)
1444 adj = fold_build2_loc (loc, MINUS_EXPR,
1445 TREE_TYPE (dsi->length), dsi->length,
1446 fold_convert_loc (loc, TREE_TYPE (dsi->length),
1447 oldlen));
1448 if (adj != NULL_TREE)
1449 adjust_related_strinfos (loc, dsi, adj);
1450 else
1451 dsi->prev = 0;
1453 /* memcpy src may not overlap dst, so src doesn't need to be
1454 invalidated either. */
1455 if (si != NULL)
1456 si->dont_invalidate = true;
1458 lhs = gimple_call_lhs (stmt);
1459 switch (bcode)
1461 case BUILT_IN_MEMCPY:
1462 case BUILT_IN_MEMCPY_CHK:
1463 case BUILT_IN_MEMCPY_CHKP:
1464 case BUILT_IN_MEMCPY_CHK_CHKP:
1465 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1466 laststmt.stmt = stmt;
1467 laststmt.len = dsi->length;
1468 laststmt.stridx = dsi->idx;
1469 if (lhs)
1470 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
1471 break;
1472 case BUILT_IN_MEMPCPY:
1473 case BUILT_IN_MEMPCPY_CHK:
1474 case BUILT_IN_MEMPCPY_CHKP:
1475 case BUILT_IN_MEMPCPY_CHK_CHKP:
1476 break;
1477 default:
1478 gcc_unreachable ();
1482 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
1483 If strlen of the second argument is known, strlen of the first argument
1484 is increased by the length of the second argument. Furthermore, attempt
1485 to convert it to memcpy/strcpy if the length of the first argument
1486 is known. */
1488 static void
1489 handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1491 int idx, didx;
1492 tree src, dst, srclen, dstlen, len, lhs, args, type, fn, objsz, endptr;
1493 bool success;
1494 gimple stmt = gsi_stmt (*gsi);
1495 strinfo si, dsi;
1496 location_t loc;
1497 bool with_bounds = gimple_call_with_bounds_p (stmt);
1499 src = gimple_call_arg (stmt, with_bounds ? 2 : 1);
1500 dst = gimple_call_arg (stmt, 0);
1501 lhs = gimple_call_lhs (stmt);
1503 didx = get_stridx (dst);
1504 if (didx < 0)
1505 return;
1507 dsi = NULL;
1508 if (didx > 0)
1509 dsi = get_strinfo (didx);
1510 if (dsi == NULL || get_string_length (dsi) == NULL_TREE)
1512 /* strcat (p, q) can be transformed into
1513 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
1514 with length endptr - p if we need to compute the length
1515 later on. Don't do this transformation if we don't need
1516 it. */
1517 if (builtin_decl_implicit_p (BUILT_IN_STPCPY) && lhs == NULL_TREE)
1519 if (didx == 0)
1521 didx = new_stridx (dst);
1522 if (didx == 0)
1523 return;
1525 if (dsi == NULL)
1527 dsi = new_strinfo (dst, didx, NULL_TREE);
1528 set_strinfo (didx, dsi);
1529 find_equal_ptrs (dst, didx);
1531 else
1533 dsi = unshare_strinfo (dsi);
1534 dsi->length = NULL_TREE;
1535 dsi->next = 0;
1536 dsi->endptr = NULL_TREE;
1538 dsi->writable = true;
1539 dsi->stmt = stmt;
1540 dsi->dont_invalidate = true;
1542 return;
1545 srclen = NULL_TREE;
1546 si = NULL;
1547 idx = get_stridx (src);
1548 if (idx < 0)
1549 srclen = build_int_cst (size_type_node, ~idx);
1550 else if (idx > 0)
1552 si = get_strinfo (idx);
1553 if (si != NULL)
1554 srclen = get_string_length (si);
1557 loc = gimple_location (stmt);
1558 dstlen = dsi->length;
1559 endptr = dsi->endptr;
1561 dsi = unshare_strinfo (dsi);
1562 dsi->endptr = NULL_TREE;
1563 dsi->stmt = NULL;
1564 dsi->writable = true;
1566 if (srclen != NULL_TREE)
1568 dsi->length = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (dsi->length),
1569 dsi->length, srclen);
1570 adjust_related_strinfos (loc, dsi, srclen);
1571 dsi->dont_invalidate = true;
1573 else
1575 dsi->length = NULL;
1576 if (lhs == NULL_TREE && builtin_decl_implicit_p (BUILT_IN_STPCPY))
1577 dsi->dont_invalidate = true;
1580 if (si != NULL)
1581 /* strcat src may not overlap dst, so src doesn't need to be
1582 invalidated either. */
1583 si->dont_invalidate = true;
1585 /* For now. Could remove the lhs from the call and add
1586 lhs = dst; afterwards. */
1587 if (lhs)
1588 return;
1590 fn = NULL_TREE;
1591 objsz = NULL_TREE;
1592 switch (bcode)
1594 case BUILT_IN_STRCAT:
1595 case BUILT_IN_STRCAT_CHKP:
1596 if (srclen != NULL_TREE)
1597 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1598 else
1599 fn = builtin_decl_implicit (BUILT_IN_STRCPY);
1600 break;
1601 case BUILT_IN_STRCAT_CHK:
1602 case BUILT_IN_STRCAT_CHK_CHKP:
1603 if (srclen != NULL_TREE)
1604 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK);
1605 else
1606 fn = builtin_decl_explicit (BUILT_IN_STRCPY_CHK);
1607 objsz = gimple_call_arg (stmt, with_bounds ? 4 : 2);
1608 break;
1609 default:
1610 gcc_unreachable ();
1613 if (fn == NULL_TREE)
1614 return;
1616 len = NULL_TREE;
1617 if (srclen != NULL_TREE)
1619 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1620 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1622 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1623 len = fold_build2_loc (loc, PLUS_EXPR, type, len,
1624 build_int_cst (type, 1));
1625 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1626 GSI_SAME_STMT);
1628 if (endptr)
1629 dst = fold_convert_loc (loc, TREE_TYPE (dst), unshare_expr (endptr));
1630 else
1631 dst = fold_build2_loc (loc, POINTER_PLUS_EXPR,
1632 TREE_TYPE (dst), unshare_expr (dst),
1633 fold_convert_loc (loc, sizetype,
1634 unshare_expr (dstlen)));
1635 dst = force_gimple_operand_gsi (gsi, dst, true, NULL_TREE, true,
1636 GSI_SAME_STMT);
1637 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1639 fprintf (dump_file, "Optimizing: ");
1640 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1642 if (with_bounds)
1644 fn = chkp_maybe_create_clone (fn)->decl;
1645 if (srclen != NULL_TREE)
1646 success = update_gimple_call (gsi, fn, 5 + (objsz != NULL_TREE),
1647 dst,
1648 gimple_call_arg (stmt, 1),
1649 src,
1650 gimple_call_arg (stmt, 3),
1651 len, objsz);
1652 else
1653 success = update_gimple_call (gsi, fn, 4 + (objsz != NULL_TREE),
1654 dst,
1655 gimple_call_arg (stmt, 1),
1656 src,
1657 gimple_call_arg (stmt, 3),
1658 objsz);
1660 else
1661 if (srclen != NULL_TREE)
1662 success = update_gimple_call (gsi, fn, 3 + (objsz != NULL_TREE),
1663 dst, src, len, objsz);
1664 else
1665 success = update_gimple_call (gsi, fn, 2 + (objsz != NULL_TREE),
1666 dst, src, objsz);
1667 if (success)
1669 stmt = gsi_stmt (*gsi);
1670 gimple_call_set_with_bounds (stmt, with_bounds);
1671 update_stmt (stmt);
1672 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1674 fprintf (dump_file, "into: ");
1675 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1677 /* If srclen == NULL, note that current string length can be
1678 computed by transforming this strcpy into stpcpy. */
1679 if (srclen == NULL_TREE && dsi->dont_invalidate)
1680 dsi->stmt = stmt;
1681 adjust_last_stmt (dsi, stmt, true);
1682 if (srclen != NULL_TREE)
1684 laststmt.stmt = stmt;
1685 laststmt.len = srclen;
1686 laststmt.stridx = dsi->idx;
1689 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1690 fprintf (dump_file, "not possible.\n");
1693 /* Handle a call to malloc or calloc. */
1695 static void
1696 handle_builtin_malloc (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1698 gimple stmt = gsi_stmt (*gsi);
1699 tree lhs = gimple_call_lhs (stmt);
1700 gcc_assert (get_stridx (lhs) == 0);
1701 int idx = new_stridx (lhs);
1702 tree length = NULL_TREE;
1703 if (bcode == BUILT_IN_CALLOC)
1704 length = build_int_cst (size_type_node, 0);
1705 strinfo si = new_strinfo (lhs, idx, length);
1706 if (bcode == BUILT_IN_CALLOC)
1707 si->endptr = lhs;
1708 set_strinfo (idx, si);
1709 si->writable = true;
1710 si->stmt = stmt;
1711 si->dont_invalidate = true;
1714 /* Handle a call to memset.
1715 After a call to calloc, memset(,0,) is unnecessary.
1716 memset(malloc(n),0,n) is calloc(n,1). */
1718 static bool
1719 handle_builtin_memset (gimple_stmt_iterator *gsi)
1721 gimple stmt2 = gsi_stmt (*gsi);
1722 if (!integer_zerop (gimple_call_arg (stmt2, 1)))
1723 return true;
1724 tree ptr = gimple_call_arg (stmt2, 0);
1725 int idx1 = get_stridx (ptr);
1726 if (idx1 <= 0)
1727 return true;
1728 strinfo si1 = get_strinfo (idx1);
1729 if (!si1)
1730 return true;
1731 gimple stmt1 = si1->stmt;
1732 if (!stmt1 || !is_gimple_call (stmt1))
1733 return true;
1734 tree callee1 = gimple_call_fndecl (stmt1);
1735 if (!gimple_call_builtin_p (stmt1, BUILT_IN_NORMAL))
1736 return true;
1737 enum built_in_function code1 = DECL_FUNCTION_CODE (callee1);
1738 tree size = gimple_call_arg (stmt2, 2);
1739 if (code1 == BUILT_IN_CALLOC)
1740 /* Not touching stmt1 */ ;
1741 else if (code1 == BUILT_IN_MALLOC
1742 && operand_equal_p (gimple_call_arg (stmt1, 0), size, 0))
1744 gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt1);
1745 update_gimple_call (&gsi1, builtin_decl_implicit (BUILT_IN_CALLOC), 2,
1746 size, build_one_cst (size_type_node));
1747 si1->length = build_int_cst (size_type_node, 0);
1748 si1->stmt = gsi_stmt (gsi1);
1750 else
1751 return true;
1752 tree lhs = gimple_call_lhs (stmt2);
1753 unlink_stmt_vdef (stmt2);
1754 if (lhs)
1756 gimple assign = gimple_build_assign (lhs, ptr);
1757 gsi_replace (gsi, assign, false);
1759 else
1761 gsi_remove (gsi, true);
1762 release_defs (stmt2);
1765 return false;
1768 /* Handle a POINTER_PLUS_EXPR statement.
1769 For p = "abcd" + 2; compute associated length, or if
1770 p = q + off is pointing to a '\0' character of a string, call
1771 zero_length_string on it. */
1773 static void
1774 handle_pointer_plus (gimple_stmt_iterator *gsi)
1776 gimple stmt = gsi_stmt (*gsi);
1777 tree lhs = gimple_assign_lhs (stmt), off;
1778 int idx = get_stridx (gimple_assign_rhs1 (stmt));
1779 strinfo si, zsi;
1781 if (idx == 0)
1782 return;
1784 if (idx < 0)
1786 tree off = gimple_assign_rhs2 (stmt);
1787 if (tree_fits_uhwi_p (off)
1788 && tree_to_uhwi (off) <= (unsigned HOST_WIDE_INT) ~idx)
1789 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)]
1790 = ~(~idx - (int) tree_to_uhwi (off));
1791 return;
1794 si = get_strinfo (idx);
1795 if (si == NULL || si->length == NULL_TREE)
1796 return;
1798 off = gimple_assign_rhs2 (stmt);
1799 zsi = NULL;
1800 if (operand_equal_p (si->length, off, 0))
1801 zsi = zero_length_string (lhs, si);
1802 else if (TREE_CODE (off) == SSA_NAME)
1804 gimple def_stmt = SSA_NAME_DEF_STMT (off);
1805 if (gimple_assign_single_p (def_stmt)
1806 && operand_equal_p (si->length, gimple_assign_rhs1 (def_stmt), 0))
1807 zsi = zero_length_string (lhs, si);
1809 if (zsi != NULL
1810 && si->endptr != NULL_TREE
1811 && si->endptr != lhs
1812 && TREE_CODE (si->endptr) == SSA_NAME)
1814 enum tree_code rhs_code
1815 = useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (si->endptr))
1816 ? SSA_NAME : NOP_EXPR;
1817 gimple_assign_set_rhs_with_ops (gsi, rhs_code, si->endptr);
1818 gcc_assert (gsi_stmt (*gsi) == stmt);
1819 update_stmt (stmt);
1823 /* Handle a single character store. */
1825 static bool
1826 handle_char_store (gimple_stmt_iterator *gsi)
1828 int idx = -1;
1829 strinfo si = NULL;
1830 gimple stmt = gsi_stmt (*gsi);
1831 tree ssaname = NULL_TREE, lhs = gimple_assign_lhs (stmt);
1833 if (TREE_CODE (lhs) == MEM_REF
1834 && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME)
1836 if (integer_zerop (TREE_OPERAND (lhs, 1)))
1838 ssaname = TREE_OPERAND (lhs, 0);
1839 idx = get_stridx (ssaname);
1842 else
1843 idx = get_addr_stridx (lhs);
1845 if (idx > 0)
1847 si = get_strinfo (idx);
1848 if (si != NULL && si->length != NULL_TREE && integer_zerop (si->length))
1850 if (initializer_zerop (gimple_assign_rhs1 (stmt)))
1852 /* When storing '\0', the store can be removed
1853 if we know it has been stored in the current function. */
1854 if (!stmt_could_throw_p (stmt) && si->writable)
1856 unlink_stmt_vdef (stmt);
1857 release_defs (stmt);
1858 gsi_remove (gsi, true);
1859 return false;
1861 else
1863 si->writable = true;
1864 gsi_next (gsi);
1865 return false;
1868 else
1869 /* Otherwise this statement overwrites the '\0' with
1870 something, if the previous stmt was a memcpy,
1871 its length may be decreased. */
1872 adjust_last_stmt (si, stmt, false);
1874 else if (si != NULL && integer_zerop (gimple_assign_rhs1 (stmt)))
1876 si = unshare_strinfo (si);
1877 si->length = build_int_cst (size_type_node, 0);
1878 si->endptr = NULL;
1879 si->prev = 0;
1880 si->next = 0;
1881 si->stmt = NULL;
1882 si->first = 0;
1883 si->writable = true;
1884 if (ssaname && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname))
1885 si->endptr = ssaname;
1886 si->dont_invalidate = true;
1888 /* If si->length is non-zero constant, we aren't overwriting '\0',
1889 and if we aren't storing '\0', we know that the length of the
1890 string and any other zero terminated string in memory remains
1891 the same. In that case we move to the next gimple statement and
1892 return to signal the caller that it shouldn't invalidate anything.
1894 This is benefical for cases like:
1896 char p[20];
1897 void foo (char *q)
1899 strcpy (p, "foobar");
1900 size_t len = strlen (p); // This can be optimized into 6
1901 size_t len2 = strlen (q); // This has to be computed
1902 p[0] = 'X';
1903 size_t len3 = strlen (p); // This can be optimized into 6
1904 size_t len4 = strlen (q); // This can be optimized into len2
1905 bar (len, len2, len3, len4);
1908 else if (si != NULL && si->length != NULL_TREE
1909 && TREE_CODE (si->length) == INTEGER_CST
1910 && integer_nonzerop (gimple_assign_rhs1 (stmt)))
1912 gsi_next (gsi);
1913 return false;
1916 else if (idx == 0 && initializer_zerop (gimple_assign_rhs1 (stmt)))
1918 if (ssaname)
1920 si = zero_length_string (ssaname, NULL);
1921 if (si != NULL)
1922 si->dont_invalidate = true;
1924 else
1926 int idx = new_addr_stridx (lhs);
1927 if (idx != 0)
1929 si = new_strinfo (build_fold_addr_expr (lhs), idx,
1930 build_int_cst (size_type_node, 0));
1931 set_strinfo (idx, si);
1932 si->dont_invalidate = true;
1935 if (si != NULL)
1936 si->writable = true;
1938 else if (idx == 0
1939 && TREE_CODE (gimple_assign_rhs1 (stmt)) == STRING_CST
1940 && ssaname == NULL_TREE
1941 && TREE_CODE (TREE_TYPE (lhs)) == ARRAY_TYPE)
1943 size_t l = strlen (TREE_STRING_POINTER (gimple_assign_rhs1 (stmt)));
1944 HOST_WIDE_INT a = int_size_in_bytes (TREE_TYPE (lhs));
1945 if (a > 0 && (unsigned HOST_WIDE_INT) a > l)
1947 int idx = new_addr_stridx (lhs);
1948 if (idx != 0)
1950 si = new_strinfo (build_fold_addr_expr (lhs), idx,
1951 build_int_cst (size_type_node, l));
1952 set_strinfo (idx, si);
1953 si->dont_invalidate = true;
1958 if (si != NULL && initializer_zerop (gimple_assign_rhs1 (stmt)))
1960 /* Allow adjust_last_stmt to remove it if the stored '\0'
1961 is immediately overwritten. */
1962 laststmt.stmt = stmt;
1963 laststmt.len = build_int_cst (size_type_node, 1);
1964 laststmt.stridx = si->idx;
1966 return true;
1969 /* Attempt to optimize a single statement at *GSI using string length
1970 knowledge. */
1972 static bool
1973 strlen_optimize_stmt (gimple_stmt_iterator *gsi)
1975 gimple stmt = gsi_stmt (*gsi);
1977 if (is_gimple_call (stmt))
1979 tree callee = gimple_call_fndecl (stmt);
1980 if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
1981 switch (DECL_FUNCTION_CODE (callee))
1983 case BUILT_IN_STRLEN:
1984 case BUILT_IN_STRLEN_CHKP:
1985 handle_builtin_strlen (gsi);
1986 break;
1987 case BUILT_IN_STRCHR:
1988 case BUILT_IN_STRCHR_CHKP:
1989 handle_builtin_strchr (gsi);
1990 break;
1991 case BUILT_IN_STRCPY:
1992 case BUILT_IN_STRCPY_CHK:
1993 case BUILT_IN_STPCPY:
1994 case BUILT_IN_STPCPY_CHK:
1995 case BUILT_IN_STRCPY_CHKP:
1996 case BUILT_IN_STRCPY_CHK_CHKP:
1997 case BUILT_IN_STPCPY_CHKP:
1998 case BUILT_IN_STPCPY_CHK_CHKP:
1999 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee), gsi);
2000 break;
2001 case BUILT_IN_MEMCPY:
2002 case BUILT_IN_MEMCPY_CHK:
2003 case BUILT_IN_MEMPCPY:
2004 case BUILT_IN_MEMPCPY_CHK:
2005 case BUILT_IN_MEMCPY_CHKP:
2006 case BUILT_IN_MEMCPY_CHK_CHKP:
2007 case BUILT_IN_MEMPCPY_CHKP:
2008 case BUILT_IN_MEMPCPY_CHK_CHKP:
2009 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi);
2010 break;
2011 case BUILT_IN_STRCAT:
2012 case BUILT_IN_STRCAT_CHK:
2013 case BUILT_IN_STRCAT_CHKP:
2014 case BUILT_IN_STRCAT_CHK_CHKP:
2015 handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi);
2016 break;
2017 case BUILT_IN_MALLOC:
2018 case BUILT_IN_CALLOC:
2019 handle_builtin_malloc (DECL_FUNCTION_CODE (callee), gsi);
2020 break;
2021 case BUILT_IN_MEMSET:
2022 if (!handle_builtin_memset (gsi))
2023 return false;
2024 break;
2025 default:
2026 break;
2029 else if (is_gimple_assign (stmt) && !gimple_clobber_p (stmt))
2031 tree lhs = gimple_assign_lhs (stmt);
2033 if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs)))
2035 if (gimple_assign_single_p (stmt)
2036 || (gimple_assign_cast_p (stmt)
2037 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))))
2039 int idx = get_stridx (gimple_assign_rhs1 (stmt));
2040 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = idx;
2042 else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
2043 handle_pointer_plus (gsi);
2045 else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
2047 tree type = TREE_TYPE (lhs);
2048 if (TREE_CODE (type) == ARRAY_TYPE)
2049 type = TREE_TYPE (type);
2050 if (TREE_CODE (type) == INTEGER_TYPE
2051 && TYPE_MODE (type) == TYPE_MODE (char_type_node)
2052 && TYPE_PRECISION (type) == TYPE_PRECISION (char_type_node))
2054 if (! handle_char_store (gsi))
2055 return false;
2060 if (gimple_vdef (stmt))
2061 maybe_invalidate (stmt);
2062 return true;
2065 /* Recursively call maybe_invalidate on stmts that might be executed
2066 in between dombb and current bb and that contain a vdef. Stop when
2067 *count stmts are inspected, or if the whole strinfo vector has
2068 been invalidated. */
2070 static void
2071 do_invalidate (basic_block dombb, gimple phi, bitmap visited, int *count)
2073 unsigned int i, n = gimple_phi_num_args (phi);
2075 for (i = 0; i < n; i++)
2077 tree vuse = gimple_phi_arg_def (phi, i);
2078 gimple stmt = SSA_NAME_DEF_STMT (vuse);
2079 basic_block bb = gimple_bb (stmt);
2080 if (bb == NULL
2081 || bb == dombb
2082 || !bitmap_set_bit (visited, bb->index)
2083 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
2084 continue;
2085 while (1)
2087 if (gimple_code (stmt) == GIMPLE_PHI)
2089 do_invalidate (dombb, stmt, visited, count);
2090 if (*count == 0)
2091 return;
2092 break;
2094 if (--*count == 0)
2095 return;
2096 if (!maybe_invalidate (stmt))
2098 *count = 0;
2099 return;
2101 vuse = gimple_vuse (stmt);
2102 stmt = SSA_NAME_DEF_STMT (vuse);
2103 if (gimple_bb (stmt) != bb)
2105 bb = gimple_bb (stmt);
2106 if (bb == NULL
2107 || bb == dombb
2108 || !bitmap_set_bit (visited, bb->index)
2109 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
2110 break;
2116 class strlen_dom_walker : public dom_walker
2118 public:
2119 strlen_dom_walker (cdi_direction direction) : dom_walker (direction) {}
2121 virtual void before_dom_children (basic_block);
2122 virtual void after_dom_children (basic_block);
2125 /* Callback for walk_dominator_tree. Attempt to optimize various
2126 string ops by remembering string lenths pointed by pointer SSA_NAMEs. */
2128 void
2129 strlen_dom_walker::before_dom_children (basic_block bb)
2131 basic_block dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
2133 if (dombb == NULL)
2134 stridx_to_strinfo = NULL;
2135 else
2137 stridx_to_strinfo = ((vec<strinfo, va_heap, vl_embed> *) dombb->aux);
2138 if (stridx_to_strinfo)
2140 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
2141 gsi_next (&gsi))
2143 gphi *phi = gsi.phi ();
2144 if (virtual_operand_p (gimple_phi_result (phi)))
2146 bitmap visited = BITMAP_ALLOC (NULL);
2147 int count_vdef = 100;
2148 do_invalidate (dombb, phi, visited, &count_vdef);
2149 BITMAP_FREE (visited);
2150 if (count_vdef == 0)
2152 /* If there were too many vdefs in between immediate
2153 dominator and current bb, invalidate everything.
2154 If stridx_to_strinfo has been unshared, we need
2155 to free it, otherwise just set it to NULL. */
2156 if (!strinfo_shared ())
2158 unsigned int i;
2159 strinfo si;
2161 for (i = 1;
2162 vec_safe_iterate (stridx_to_strinfo, i, &si);
2163 ++i)
2165 free_strinfo (si);
2166 (*stridx_to_strinfo)[i] = NULL;
2169 else
2170 stridx_to_strinfo = NULL;
2172 break;
2178 /* If all PHI arguments have the same string index, the PHI result
2179 has it as well. */
2180 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
2181 gsi_next (&gsi))
2183 gphi *phi = gsi.phi ();
2184 tree result = gimple_phi_result (phi);
2185 if (!virtual_operand_p (result) && POINTER_TYPE_P (TREE_TYPE (result)))
2187 int idx = get_stridx (gimple_phi_arg_def (phi, 0));
2188 if (idx != 0)
2190 unsigned int i, n = gimple_phi_num_args (phi);
2191 for (i = 1; i < n; i++)
2192 if (idx != get_stridx (gimple_phi_arg_def (phi, i)))
2193 break;
2194 if (i == n)
2195 ssa_ver_to_stridx[SSA_NAME_VERSION (result)] = idx;
2200 /* Attempt to optimize individual statements. */
2201 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2202 if (strlen_optimize_stmt (&gsi))
2203 gsi_next (&gsi);
2205 bb->aux = stridx_to_strinfo;
2206 if (vec_safe_length (stridx_to_strinfo) && !strinfo_shared ())
2207 (*stridx_to_strinfo)[0] = (strinfo) bb;
2210 /* Callback for walk_dominator_tree. Free strinfo vector if it is
2211 owned by the current bb, clear bb->aux. */
2213 void
2214 strlen_dom_walker::after_dom_children (basic_block bb)
2216 if (bb->aux)
2218 stridx_to_strinfo = ((vec<strinfo, va_heap, vl_embed> *) bb->aux);
2219 if (vec_safe_length (stridx_to_strinfo)
2220 && (*stridx_to_strinfo)[0] == (strinfo) bb)
2222 unsigned int i;
2223 strinfo si;
2225 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
2226 free_strinfo (si);
2227 vec_free (stridx_to_strinfo);
2229 bb->aux = NULL;
2233 /* Main entry point. */
2235 namespace {
2237 const pass_data pass_data_strlen =
2239 GIMPLE_PASS, /* type */
2240 "strlen", /* name */
2241 OPTGROUP_NONE, /* optinfo_flags */
2242 TV_TREE_STRLEN, /* tv_id */
2243 ( PROP_cfg | PROP_ssa ), /* properties_required */
2244 0, /* properties_provided */
2245 0, /* properties_destroyed */
2246 0, /* todo_flags_start */
2247 0, /* todo_flags_finish */
2250 class pass_strlen : public gimple_opt_pass
2252 public:
2253 pass_strlen (gcc::context *ctxt)
2254 : gimple_opt_pass (pass_data_strlen, ctxt)
2257 /* opt_pass methods: */
2258 virtual bool gate (function *) { return flag_optimize_strlen != 0; }
2259 virtual unsigned int execute (function *);
2261 }; // class pass_strlen
2263 unsigned int
2264 pass_strlen::execute (function *fun)
2266 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
2267 max_stridx = 1;
2268 strinfo_pool = create_alloc_pool ("strinfo_struct pool",
2269 sizeof (struct strinfo_struct), 64);
2271 calculate_dominance_info (CDI_DOMINATORS);
2273 /* String length optimization is implemented as a walk of the dominator
2274 tree and a forward walk of statements within each block. */
2275 strlen_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr);
2277 ssa_ver_to_stridx.release ();
2278 free_alloc_pool (strinfo_pool);
2279 if (decl_to_stridxlist_htab)
2281 obstack_free (&stridx_obstack, NULL);
2282 delete decl_to_stridxlist_htab;
2283 decl_to_stridxlist_htab = NULL;
2285 laststmt.stmt = NULL;
2286 laststmt.len = NULL_TREE;
2287 laststmt.stridx = 0;
2289 return 0;
2292 } // anon namespace
2294 gimple_opt_pass *
2295 make_pass_strlen (gcc::context *ctxt)
2297 return new pass_strlen (ctxt);