gcc/
[official-gcc.git] / gcc / tree-ssa-strlen.c
blob1cbcb011cb07604cf825f207fdcc01dc7b80f173
1 /* String length optimization
2 Copyright (C) 2011-2015 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 "alias.h"
25 #include "symtab.h"
26 #include "options.h"
27 #include "tree.h"
28 #include "fold-const.h"
29 #include "stor-layout.h"
30 #include "bitmap.h"
31 #include "predict.h"
32 #include "tm.h"
33 #include "hard-reg-set.h"
34 #include "function.h"
35 #include "dominance.h"
36 #include "cfg.h"
37 #include "basic-block.h"
38 #include "tree-ssa-alias.h"
39 #include "internal-fn.h"
40 #include "gimple-fold.h"
41 #include "tree-eh.h"
42 #include "gimple-expr.h"
43 #include "gimple.h"
44 #include "gimplify.h"
45 #include "gimple-iterator.h"
46 #include "gimplify-me.h"
47 #include "gimple-ssa.h"
48 #include "tree-phinodes.h"
49 #include "ssa-iterators.h"
50 #include "stringpool.h"
51 #include "tree-ssanames.h"
52 #include "rtl.h"
53 #include "flags.h"
54 #include "insn-config.h"
55 #include "expmed.h"
56 #include "dojump.h"
57 #include "explow.h"
58 #include "calls.h"
59 #include "emit-rtl.h"
60 #include "varasm.h"
61 #include "stmt.h"
62 #include "expr.h"
63 #include "tree-dfa.h"
64 #include "tree-pass.h"
65 #include "domwalk.h"
66 #include "alloc-pool.h"
67 #include "tree-ssa-propagate.h"
68 #include "gimple-pretty-print.h"
69 #include "params.h"
70 #include "cgraph.h"
71 #include "ipa-chkp.h"
72 #include "tree-hash-traits.h"
74 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
75 is an index into strinfo vector, negative value stands for
76 string length of a string literal (~strlen). */
77 static vec<int> ssa_ver_to_stridx;
79 /* Number of currently active string indexes plus one. */
80 static int max_stridx;
82 /* String information record. */
83 typedef struct strinfo_struct
85 /* String length of this string. */
86 tree length;
87 /* Any of the corresponding pointers for querying alias oracle. */
88 tree ptr;
89 /* Statement for delayed length computation. */
90 gimple stmt;
91 /* Pointer to '\0' if known, if NULL, it can be computed as
92 ptr + length. */
93 tree endptr;
94 /* Reference count. Any changes to strinfo entry possibly shared
95 with dominating basic blocks need unshare_strinfo first, except
96 for dont_invalidate which affects only the immediately next
97 maybe_invalidate. */
98 int refcount;
99 /* Copy of index. get_strinfo (si->idx) should return si; */
100 int idx;
101 /* These 3 fields are for chaining related string pointers together.
102 E.g. for
103 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
104 strcpy (c, d); e = c + dl;
105 strinfo(a) -> strinfo(c) -> strinfo(e)
106 All have ->first field equal to strinfo(a)->idx and are doubly
107 chained through prev/next fields. The later strinfos are required
108 to point into the same string with zero or more bytes after
109 the previous pointer and all bytes in between the two pointers
110 must be non-zero. Functions like strcpy or memcpy are supposed
111 to adjust all previous strinfo lengths, but not following strinfo
112 lengths (those are uncertain, usually invalidated during
113 maybe_invalidate, except when the alias oracle knows better).
114 Functions like strcat on the other side adjust the whole
115 related strinfo chain.
116 They are updated lazily, so to use the chain the same first fields
117 and si->prev->next == si->idx needs to be verified. */
118 int first;
119 int next;
120 int prev;
121 /* A flag whether the string is known to be written in the current
122 function. */
123 bool writable;
124 /* A flag for the next maybe_invalidate that this strinfo shouldn't
125 be invalidated. Always cleared by maybe_invalidate. */
126 bool dont_invalidate;
127 } *strinfo;
129 /* Pool for allocating strinfo_struct entries. */
130 static pool_allocator<strinfo_struct> strinfo_pool ("strinfo_struct pool", 64);
132 /* Vector mapping positive string indexes to strinfo, for the
133 current basic block. The first pointer in the vector is special,
134 it is either NULL, meaning the vector isn't shared, or it is
135 a basic block pointer to the owner basic_block if shared.
136 If some other bb wants to modify the vector, the vector needs
137 to be unshared first, and only the owner bb is supposed to free it. */
138 static vec<strinfo, va_heap, vl_embed> *stridx_to_strinfo;
140 /* One OFFSET->IDX mapping. */
141 struct stridxlist
143 struct stridxlist *next;
144 HOST_WIDE_INT offset;
145 int idx;
148 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
149 struct decl_stridxlist_map
151 struct tree_map_base base;
152 struct stridxlist list;
155 /* Hash table for mapping decls to a chained list of offset -> idx
156 mappings. */
157 static hash_map<tree_decl_hash, stridxlist> *decl_to_stridxlist_htab;
159 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
160 static struct obstack stridx_obstack;
162 /* Last memcpy statement if it could be adjusted if the trailing
163 '\0' written is immediately overwritten, or
164 *x = '\0' store that could be removed if it is immediately overwritten. */
165 struct laststmt_struct
167 gimple stmt;
168 tree len;
169 int stridx;
170 } laststmt;
172 static int get_stridx_plus_constant (strinfo, HOST_WIDE_INT, tree);
174 /* Return strinfo vector entry IDX. */
176 static inline strinfo
177 get_strinfo (int idx)
179 if (vec_safe_length (stridx_to_strinfo) <= (unsigned int) idx)
180 return NULL;
181 return (*stridx_to_strinfo)[idx];
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)
223 if (ssa_ver_to_stridx[SSA_NAME_VERSION (exp)])
224 return ssa_ver_to_stridx[SSA_NAME_VERSION (exp)];
225 int i;
226 tree e = exp;
227 HOST_WIDE_INT off = 0;
228 for (i = 0; i < 5; i++)
230 gimple def_stmt = SSA_NAME_DEF_STMT (e);
231 if (!is_gimple_assign (def_stmt)
232 || gimple_assign_rhs_code (def_stmt) != POINTER_PLUS_EXPR)
233 return 0;
234 tree rhs1 = gimple_assign_rhs1 (def_stmt);
235 tree rhs2 = gimple_assign_rhs2 (def_stmt);
236 if (TREE_CODE (rhs1) != SSA_NAME
237 || !tree_fits_shwi_p (rhs2))
238 return 0;
239 HOST_WIDE_INT this_off = tree_to_shwi (rhs2);
240 if (this_off < 0)
241 return 0;
242 off = (unsigned HOST_WIDE_INT) off + this_off;
243 if (off < 0)
244 return 0;
245 if (ssa_ver_to_stridx[SSA_NAME_VERSION (rhs1)])
247 strinfo si
248 = get_strinfo (ssa_ver_to_stridx[SSA_NAME_VERSION (rhs1)]);
249 if (si
250 && si->length
251 && TREE_CODE (si->length) == INTEGER_CST
252 && compare_tree_int (si->length, off) != -1)
253 return get_stridx_plus_constant (si, off, exp);
255 e = rhs1;
257 return 0;
260 if (TREE_CODE (exp) == ADDR_EXPR)
262 int idx = get_addr_stridx (TREE_OPERAND (exp, 0));
263 if (idx != 0)
264 return idx;
267 s = string_constant (exp, &o);
268 if (s != NULL_TREE
269 && (o == NULL_TREE || tree_fits_shwi_p (o))
270 && TREE_STRING_LENGTH (s) > 0)
272 HOST_WIDE_INT offset = o ? tree_to_shwi (o) : 0;
273 const char *p = TREE_STRING_POINTER (s);
274 int max = TREE_STRING_LENGTH (s) - 1;
276 if (p[max] == '\0' && offset >= 0 && offset <= max)
277 return ~(int) strlen (p + offset);
279 return 0;
282 /* Return true if strinfo vector is shared with the immediate dominator. */
284 static inline bool
285 strinfo_shared (void)
287 return vec_safe_length (stridx_to_strinfo)
288 && (*stridx_to_strinfo)[0] != NULL;
291 /* Unshare strinfo vector that is shared with the immediate dominator. */
293 static void
294 unshare_strinfo_vec (void)
296 strinfo si;
297 unsigned int i = 0;
299 gcc_assert (strinfo_shared ());
300 stridx_to_strinfo = vec_safe_copy (stridx_to_strinfo);
301 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
302 if (si != NULL)
303 si->refcount++;
304 (*stridx_to_strinfo)[0] = NULL;
307 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
308 Return a pointer to the location where the string index can
309 be stored (if 0) or is stored, or NULL if this can't be tracked. */
311 static int *
312 addr_stridxptr (tree exp)
314 HOST_WIDE_INT off;
316 tree base = get_addr_base_and_unit_offset (exp, &off);
317 if (base == NULL_TREE || !DECL_P (base))
318 return NULL;
320 if (!decl_to_stridxlist_htab)
322 decl_to_stridxlist_htab
323 = new hash_map<tree_decl_hash, stridxlist> (64);
324 gcc_obstack_init (&stridx_obstack);
327 bool existed;
328 stridxlist *list = &decl_to_stridxlist_htab->get_or_insert (base, &existed);
329 if (existed)
331 int i;
332 for (i = 0; i < 16; i++)
334 if (list->offset == off)
335 return &list->idx;
336 if (list->next == NULL)
337 break;
339 if (i == 16)
340 return NULL;
341 list->next = XOBNEW (&stridx_obstack, struct stridxlist);
342 list = list->next;
345 list->next = NULL;
346 list->offset = off;
347 list->idx = 0;
348 return &list->idx;
351 /* Create a new string index, or return 0 if reached limit. */
353 static int
354 new_stridx (tree exp)
356 int idx;
357 if (max_stridx >= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS))
358 return 0;
359 if (TREE_CODE (exp) == SSA_NAME)
361 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp))
362 return 0;
363 idx = max_stridx++;
364 ssa_ver_to_stridx[SSA_NAME_VERSION (exp)] = idx;
365 return idx;
367 if (TREE_CODE (exp) == ADDR_EXPR)
369 int *pidx = addr_stridxptr (TREE_OPERAND (exp, 0));
370 if (pidx != NULL)
372 gcc_assert (*pidx == 0);
373 *pidx = max_stridx++;
374 return *pidx;
377 return 0;
380 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
382 static int
383 new_addr_stridx (tree exp)
385 int *pidx;
386 if (max_stridx >= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS))
387 return 0;
388 pidx = addr_stridxptr (exp);
389 if (pidx != NULL)
391 gcc_assert (*pidx == 0);
392 *pidx = max_stridx++;
393 return *pidx;
395 return 0;
398 /* Create a new strinfo. */
400 static strinfo
401 new_strinfo (tree ptr, int idx, tree length)
403 strinfo si = strinfo_pool.allocate ();
404 si->length = length;
405 si->ptr = ptr;
406 si->stmt = NULL;
407 si->endptr = NULL_TREE;
408 si->refcount = 1;
409 si->idx = idx;
410 si->first = 0;
411 si->prev = 0;
412 si->next = 0;
413 si->writable = false;
414 si->dont_invalidate = false;
415 return si;
418 /* Decrease strinfo refcount and free it if not referenced anymore. */
420 static inline void
421 free_strinfo (strinfo si)
423 if (si && --si->refcount == 0)
424 strinfo_pool.remove (si);
427 /* Set strinfo in the vector entry IDX to SI. */
429 static inline void
430 set_strinfo (int idx, strinfo si)
432 if (vec_safe_length (stridx_to_strinfo) && (*stridx_to_strinfo)[0])
433 unshare_strinfo_vec ();
434 if (vec_safe_length (stridx_to_strinfo) <= (unsigned int) idx)
435 vec_safe_grow_cleared (stridx_to_strinfo, idx + 1);
436 (*stridx_to_strinfo)[idx] = si;
439 /* Return string length, or NULL if it can't be computed. */
441 static tree
442 get_string_length (strinfo si)
444 if (si->length)
445 return si->length;
447 if (si->stmt)
449 gimple stmt = si->stmt, lenstmt;
450 bool with_bounds = gimple_call_with_bounds_p (stmt);
451 tree callee, lhs, fn, tem;
452 location_t loc;
453 gimple_stmt_iterator gsi;
455 gcc_assert (is_gimple_call (stmt));
456 callee = gimple_call_fndecl (stmt);
457 gcc_assert (callee && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL);
458 lhs = gimple_call_lhs (stmt);
459 /* unshare_strinfo is intentionally not called here. The (delayed)
460 transformation of strcpy or strcat into stpcpy is done at the place
461 of the former strcpy/strcat call and so can affect all the strinfos
462 with the same stmt. If they were unshared before and transformation
463 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
464 just compute the right length. */
465 switch (DECL_FUNCTION_CODE (callee))
467 case BUILT_IN_STRCAT:
468 case BUILT_IN_STRCAT_CHK:
469 case BUILT_IN_STRCAT_CHKP:
470 case BUILT_IN_STRCAT_CHK_CHKP:
471 gsi = gsi_for_stmt (stmt);
472 fn = builtin_decl_implicit (BUILT_IN_STRLEN);
473 gcc_assert (lhs == NULL_TREE);
474 tem = unshare_expr (gimple_call_arg (stmt, 0));
475 if (with_bounds)
477 lenstmt = gimple_build_call (chkp_maybe_create_clone (fn)->decl,
478 2, tem, gimple_call_arg (stmt, 1));
479 gimple_call_set_with_bounds (lenstmt, true);
481 else
482 lenstmt = gimple_build_call (fn, 1, tem);
483 lhs = make_ssa_name (TREE_TYPE (TREE_TYPE (fn)), lenstmt);
484 gimple_call_set_lhs (lenstmt, lhs);
485 gimple_set_vuse (lenstmt, gimple_vuse (stmt));
486 gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT);
487 tem = gimple_call_arg (stmt, 0);
488 if (!ptrofftype_p (TREE_TYPE (lhs)))
490 lhs = convert_to_ptrofftype (lhs);
491 lhs = force_gimple_operand_gsi (&gsi, lhs, true, NULL_TREE,
492 true, GSI_SAME_STMT);
494 lenstmt = gimple_build_assign
495 (make_ssa_name (TREE_TYPE (gimple_call_arg (stmt, 0))),
496 POINTER_PLUS_EXPR,tem, lhs);
497 gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT);
498 gimple_call_set_arg (stmt, 0, gimple_assign_lhs (lenstmt));
499 lhs = NULL_TREE;
500 /* FALLTHRU */
501 case BUILT_IN_STRCPY:
502 case BUILT_IN_STRCPY_CHK:
503 case BUILT_IN_STRCPY_CHKP:
504 case BUILT_IN_STRCPY_CHK_CHKP:
505 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY));
506 if (gimple_call_num_args (stmt) == (with_bounds ? 4 : 2))
507 fn = builtin_decl_implicit (BUILT_IN_STPCPY);
508 else
509 fn = builtin_decl_explicit (BUILT_IN_STPCPY_CHK);
510 if (with_bounds)
511 fn = chkp_maybe_create_clone (fn)->decl;
512 gcc_assert (lhs == NULL_TREE);
513 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
515 fprintf (dump_file, "Optimizing: ");
516 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
518 gimple_call_set_fndecl (stmt, fn);
519 lhs = make_ssa_name (TREE_TYPE (TREE_TYPE (fn)), stmt);
520 gimple_call_set_lhs (stmt, lhs);
521 update_stmt (stmt);
522 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
524 fprintf (dump_file, "into: ");
525 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
527 /* FALLTHRU */
528 case BUILT_IN_STPCPY:
529 case BUILT_IN_STPCPY_CHK:
530 case BUILT_IN_STPCPY_CHKP:
531 case BUILT_IN_STPCPY_CHK_CHKP:
532 gcc_assert (lhs != NULL_TREE);
533 loc = gimple_location (stmt);
534 si->endptr = lhs;
535 si->stmt = NULL;
536 lhs = fold_convert_loc (loc, size_type_node, lhs);
537 si->length = fold_convert_loc (loc, size_type_node, si->ptr);
538 si->length = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
539 lhs, si->length);
540 break;
541 case BUILT_IN_MALLOC:
542 break;
543 /* BUILT_IN_CALLOC always has si->length set. */
544 default:
545 gcc_unreachable ();
546 break;
550 return si->length;
553 /* Invalidate string length information for strings whose length
554 might change due to stores in stmt. */
556 static bool
557 maybe_invalidate (gimple stmt)
559 strinfo si;
560 unsigned int i;
561 bool nonempty = false;
563 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
564 if (si != NULL)
566 if (!si->dont_invalidate)
568 ao_ref r;
569 /* Do not use si->length. */
570 ao_ref_init_from_ptr_and_size (&r, si->ptr, NULL_TREE);
571 if (stmt_may_clobber_ref_p_1 (stmt, &r))
573 set_strinfo (i, NULL);
574 free_strinfo (si);
575 continue;
578 si->dont_invalidate = false;
579 nonempty = true;
581 return nonempty;
584 /* Unshare strinfo record SI, if it has refcount > 1 or
585 if stridx_to_strinfo vector is shared with some other
586 bbs. */
588 static strinfo
589 unshare_strinfo (strinfo si)
591 strinfo nsi;
593 if (si->refcount == 1 && !strinfo_shared ())
594 return si;
596 nsi = new_strinfo (si->ptr, si->idx, si->length);
597 nsi->stmt = si->stmt;
598 nsi->endptr = si->endptr;
599 nsi->first = si->first;
600 nsi->prev = si->prev;
601 nsi->next = si->next;
602 nsi->writable = si->writable;
603 set_strinfo (si->idx, nsi);
604 free_strinfo (si);
605 return nsi;
608 /* Return first strinfo in the related strinfo chain
609 if all strinfos in between belong to the chain, otherwise
610 NULL. */
612 static strinfo
613 verify_related_strinfos (strinfo origsi)
615 strinfo si = origsi, psi;
617 if (origsi->first == 0)
618 return NULL;
619 for (; si->prev; si = psi)
621 if (si->first != origsi->first)
622 return NULL;
623 psi = get_strinfo (si->prev);
624 if (psi == NULL)
625 return NULL;
626 if (psi->next != si->idx)
627 return NULL;
629 if (si->idx != si->first)
630 return NULL;
631 return si;
634 /* Attempt to create a new strinfo for BASESI + OFF, or find existing
635 strinfo if there is any. Return it's idx, or 0 if no strinfo has
636 been created. */
638 static int
639 get_stridx_plus_constant (strinfo basesi, HOST_WIDE_INT off, tree ptr)
641 gcc_checking_assert (TREE_CODE (ptr) == SSA_NAME);
643 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
644 return 0;
646 if (basesi->length == NULL_TREE
647 || TREE_CODE (basesi->length) != INTEGER_CST
648 || compare_tree_int (basesi->length, off) == -1
649 || !tree_fits_shwi_p (basesi->length))
650 return 0;
652 HOST_WIDE_INT len = tree_to_shwi (basesi->length) - off;
653 strinfo si = basesi, chainsi;
654 if (si->first || si->prev || si->next)
655 si = verify_related_strinfos (basesi);
656 if (si == NULL
657 || si->length == NULL_TREE
658 || TREE_CODE (si->length) != INTEGER_CST)
659 return 0;
661 if (ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
662 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
664 gcc_checking_assert (compare_tree_int (si->length, off) != -1);
665 for (chainsi = si; chainsi->next; chainsi = si)
667 si = get_strinfo (chainsi->next);
668 if (si == NULL
669 || si->first != chainsi->first
670 || si->prev != chainsi->idx
671 || si->length == NULL_TREE
672 || TREE_CODE (si->length) != INTEGER_CST)
673 break;
674 int r = compare_tree_int (si->length, len);
675 if (r != 1)
677 if (r == 0)
679 ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = si->idx;
680 return si->idx;
682 break;
686 int idx = new_stridx (ptr);
687 if (idx == 0)
688 return 0;
689 si = new_strinfo (ptr, idx, build_int_cst (size_type_node, len));
690 set_strinfo (idx, si);
691 if (chainsi->next)
693 strinfo nextsi = unshare_strinfo (get_strinfo (chainsi->next));
694 si->next = nextsi->idx;
695 nextsi->prev = idx;
697 chainsi = unshare_strinfo (chainsi);
698 if (chainsi->first == 0)
699 chainsi->first = chainsi->idx;
700 chainsi->next = idx;
701 if (chainsi->endptr == NULL_TREE && len == 0)
702 chainsi->endptr = ptr;
703 si->endptr = chainsi->endptr;
704 si->prev = chainsi->idx;
705 si->first = chainsi->first;
706 si->writable = chainsi->writable;
707 return si->idx;
710 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
711 to a zero-length string and if possible chain it to a related strinfo
712 chain whose part is or might be CHAINSI. */
714 static strinfo
715 zero_length_string (tree ptr, strinfo chainsi)
717 strinfo si;
718 int idx;
719 if (ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
720 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
721 gcc_checking_assert (TREE_CODE (ptr) == SSA_NAME
722 && ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] == 0);
724 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
725 return NULL;
726 if (chainsi != NULL)
728 si = verify_related_strinfos (chainsi);
729 if (si)
731 chainsi = si;
732 for (; chainsi->next; chainsi = si)
734 if (chainsi->endptr == NULL_TREE)
736 chainsi = unshare_strinfo (chainsi);
737 chainsi->endptr = ptr;
739 si = get_strinfo (chainsi->next);
740 if (si == NULL
741 || si->first != chainsi->first
742 || si->prev != chainsi->idx)
743 break;
745 gcc_assert (chainsi->length || chainsi->stmt);
746 if (chainsi->endptr == NULL_TREE)
748 chainsi = unshare_strinfo (chainsi);
749 chainsi->endptr = ptr;
751 if (chainsi->length && integer_zerop (chainsi->length))
753 if (chainsi->next)
755 chainsi = unshare_strinfo (chainsi);
756 chainsi->next = 0;
758 ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = chainsi->idx;
759 return chainsi;
762 else if (chainsi->first || chainsi->prev || chainsi->next)
764 chainsi = unshare_strinfo (chainsi);
765 chainsi->first = 0;
766 chainsi->prev = 0;
767 chainsi->next = 0;
770 idx = new_stridx (ptr);
771 if (idx == 0)
772 return NULL;
773 si = new_strinfo (ptr, idx, build_int_cst (size_type_node, 0));
774 set_strinfo (idx, si);
775 si->endptr = ptr;
776 if (chainsi != NULL)
778 chainsi = unshare_strinfo (chainsi);
779 if (chainsi->first == 0)
780 chainsi->first = chainsi->idx;
781 chainsi->next = idx;
782 if (chainsi->endptr == NULL_TREE)
783 chainsi->endptr = ptr;
784 si->prev = chainsi->idx;
785 si->first = chainsi->first;
786 si->writable = chainsi->writable;
788 return si;
791 /* For strinfo ORIGSI whose length has been just updated
792 update also related strinfo lengths (add ADJ to each,
793 but don't adjust ORIGSI). */
795 static void
796 adjust_related_strinfos (location_t loc, strinfo origsi, tree adj)
798 strinfo si = verify_related_strinfos (origsi);
800 if (si == NULL)
801 return;
803 while (1)
805 strinfo nsi;
807 if (si != origsi)
809 tree tem;
811 si = unshare_strinfo (si);
812 if (si->length)
814 tem = fold_convert_loc (loc, TREE_TYPE (si->length), adj);
815 si->length = fold_build2_loc (loc, PLUS_EXPR,
816 TREE_TYPE (si->length), si->length,
817 tem);
819 else if (si->stmt != NULL)
820 /* Delayed length computation is unaffected. */
822 else
823 gcc_unreachable ();
825 si->endptr = NULL_TREE;
826 si->dont_invalidate = true;
828 if (si->next == 0)
829 return;
830 nsi = get_strinfo (si->next);
831 if (nsi == NULL
832 || nsi->first != si->first
833 || nsi->prev != si->idx)
834 return;
835 si = nsi;
839 /* Find if there are other SSA_NAME pointers equal to PTR
840 for which we don't track their string lengths yet. If so, use
841 IDX for them. */
843 static void
844 find_equal_ptrs (tree ptr, int idx)
846 if (TREE_CODE (ptr) != SSA_NAME)
847 return;
848 while (1)
850 gimple stmt = SSA_NAME_DEF_STMT (ptr);
851 if (!is_gimple_assign (stmt))
852 return;
853 ptr = gimple_assign_rhs1 (stmt);
854 switch (gimple_assign_rhs_code (stmt))
856 case SSA_NAME:
857 break;
858 CASE_CONVERT:
859 if (!POINTER_TYPE_P (TREE_TYPE (ptr)))
860 return;
861 if (TREE_CODE (ptr) == SSA_NAME)
862 break;
863 if (TREE_CODE (ptr) != ADDR_EXPR)
864 return;
865 /* FALLTHRU */
866 case ADDR_EXPR:
868 int *pidx = addr_stridxptr (TREE_OPERAND (ptr, 0));
869 if (pidx != NULL && *pidx == 0)
870 *pidx = idx;
871 return;
873 default:
874 return;
877 /* We might find an endptr created in this pass. Grow the
878 vector in that case. */
879 if (ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
880 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
882 if (ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] != 0)
883 return;
884 ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = idx;
888 /* If the last .MEM setter statement before STMT is
889 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
890 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
891 just memcpy (x, y, strlen (y)). SI must be the zero length
892 strinfo. */
894 static void
895 adjust_last_stmt (strinfo si, gimple stmt, bool is_strcat)
897 tree vuse, callee, len;
898 struct laststmt_struct last = laststmt;
899 strinfo lastsi, firstsi;
900 unsigned len_arg_no = 2;
902 laststmt.stmt = NULL;
903 laststmt.len = NULL_TREE;
904 laststmt.stridx = 0;
906 if (last.stmt == NULL)
907 return;
909 vuse = gimple_vuse (stmt);
910 if (vuse == NULL_TREE
911 || SSA_NAME_DEF_STMT (vuse) != last.stmt
912 || !has_single_use (vuse))
913 return;
915 gcc_assert (last.stridx > 0);
916 lastsi = get_strinfo (last.stridx);
917 if (lastsi == NULL)
918 return;
920 if (lastsi != si)
922 if (lastsi->first == 0 || lastsi->first != si->first)
923 return;
925 firstsi = verify_related_strinfos (si);
926 if (firstsi == NULL)
927 return;
928 while (firstsi != lastsi)
930 strinfo nextsi;
931 if (firstsi->next == 0)
932 return;
933 nextsi = get_strinfo (firstsi->next);
934 if (nextsi == NULL
935 || nextsi->prev != firstsi->idx
936 || nextsi->first != si->first)
937 return;
938 firstsi = nextsi;
942 if (!is_strcat)
944 if (si->length == NULL_TREE || !integer_zerop (si->length))
945 return;
948 if (is_gimple_assign (last.stmt))
950 gimple_stmt_iterator gsi;
952 if (!integer_zerop (gimple_assign_rhs1 (last.stmt)))
953 return;
954 if (stmt_could_throw_p (last.stmt))
955 return;
956 gsi = gsi_for_stmt (last.stmt);
957 unlink_stmt_vdef (last.stmt);
958 release_defs (last.stmt);
959 gsi_remove (&gsi, true);
960 return;
963 if (!gimple_call_builtin_p (last.stmt, BUILT_IN_NORMAL))
964 return;
966 callee = gimple_call_fndecl (last.stmt);
967 switch (DECL_FUNCTION_CODE (callee))
969 case BUILT_IN_MEMCPY:
970 case BUILT_IN_MEMCPY_CHK:
971 break;
972 case BUILT_IN_MEMCPY_CHKP:
973 case BUILT_IN_MEMCPY_CHK_CHKP:
974 len_arg_no = 4;
975 break;
976 default:
977 return;
980 len = gimple_call_arg (last.stmt, len_arg_no);
981 if (tree_fits_uhwi_p (len))
983 if (!tree_fits_uhwi_p (last.len)
984 || integer_zerop (len)
985 || tree_to_uhwi (len) != tree_to_uhwi (last.len) + 1)
986 return;
987 /* Don't adjust the length if it is divisible by 4, it is more efficient
988 to store the extra '\0' in that case. */
989 if ((tree_to_uhwi (len) & 3) == 0)
990 return;
992 else if (TREE_CODE (len) == SSA_NAME)
994 gimple def_stmt = SSA_NAME_DEF_STMT (len);
995 if (!is_gimple_assign (def_stmt)
996 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
997 || gimple_assign_rhs1 (def_stmt) != last.len
998 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
999 return;
1001 else
1002 return;
1004 gimple_call_set_arg (last.stmt, len_arg_no, last.len);
1005 update_stmt (last.stmt);
1008 /* Handle a strlen call. If strlen of the argument is known, replace
1009 the strlen call with the known value, otherwise remember that strlen
1010 of the argument is stored in the lhs SSA_NAME. */
1012 static void
1013 handle_builtin_strlen (gimple_stmt_iterator *gsi)
1015 int idx;
1016 tree src;
1017 gimple stmt = gsi_stmt (*gsi);
1018 tree lhs = gimple_call_lhs (stmt);
1020 if (lhs == NULL_TREE)
1021 return;
1023 src = gimple_call_arg (stmt, 0);
1024 idx = get_stridx (src);
1025 if (idx)
1027 strinfo si = NULL;
1028 tree rhs;
1030 if (idx < 0)
1031 rhs = build_int_cst (TREE_TYPE (lhs), ~idx);
1032 else
1034 rhs = NULL_TREE;
1035 si = get_strinfo (idx);
1036 if (si != NULL)
1037 rhs = get_string_length (si);
1039 if (rhs != NULL_TREE)
1041 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1043 fprintf (dump_file, "Optimizing: ");
1044 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1046 rhs = unshare_expr (rhs);
1047 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
1048 rhs = fold_convert_loc (gimple_location (stmt),
1049 TREE_TYPE (lhs), rhs);
1050 if (!update_call_from_tree (gsi, rhs))
1051 gimplify_and_update_call_from_tree (gsi, rhs);
1052 stmt = gsi_stmt (*gsi);
1053 update_stmt (stmt);
1054 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1056 fprintf (dump_file, "into: ");
1057 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1059 if (si != NULL
1060 && TREE_CODE (si->length) != SSA_NAME
1061 && TREE_CODE (si->length) != INTEGER_CST
1062 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1064 si = unshare_strinfo (si);
1065 si->length = lhs;
1067 return;
1070 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1071 return;
1072 if (idx == 0)
1073 idx = new_stridx (src);
1074 else if (get_strinfo (idx) != NULL)
1075 return;
1076 if (idx)
1078 strinfo si = new_strinfo (src, idx, lhs);
1079 set_strinfo (idx, si);
1080 find_equal_ptrs (src, idx);
1084 /* Handle a strchr call. If strlen of the first argument is known, replace
1085 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
1086 that lhs of the call is endptr and strlen of the argument is endptr - x. */
1088 static void
1089 handle_builtin_strchr (gimple_stmt_iterator *gsi)
1091 int idx;
1092 tree src;
1093 gimple stmt = gsi_stmt (*gsi);
1094 tree lhs = gimple_call_lhs (stmt);
1095 bool with_bounds = gimple_call_with_bounds_p (stmt);
1097 if (lhs == NULL_TREE)
1098 return;
1100 if (!integer_zerop (gimple_call_arg (stmt, with_bounds ? 2 : 1)))
1101 return;
1103 src = gimple_call_arg (stmt, 0);
1104 idx = get_stridx (src);
1105 if (idx)
1107 strinfo si = NULL;
1108 tree rhs;
1110 if (idx < 0)
1111 rhs = build_int_cst (size_type_node, ~idx);
1112 else
1114 rhs = NULL_TREE;
1115 si = get_strinfo (idx);
1116 if (si != NULL)
1117 rhs = get_string_length (si);
1119 if (rhs != NULL_TREE)
1121 location_t loc = gimple_location (stmt);
1123 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1125 fprintf (dump_file, "Optimizing: ");
1126 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1128 if (si != NULL && si->endptr != NULL_TREE)
1130 rhs = unshare_expr (si->endptr);
1131 if (!useless_type_conversion_p (TREE_TYPE (lhs),
1132 TREE_TYPE (rhs)))
1133 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
1135 else
1137 rhs = fold_convert_loc (loc, sizetype, unshare_expr (rhs));
1138 rhs = fold_build2_loc (loc, POINTER_PLUS_EXPR,
1139 TREE_TYPE (src), src, rhs);
1140 if (!useless_type_conversion_p (TREE_TYPE (lhs),
1141 TREE_TYPE (rhs)))
1142 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
1144 if (!update_call_from_tree (gsi, rhs))
1145 gimplify_and_update_call_from_tree (gsi, rhs);
1146 stmt = gsi_stmt (*gsi);
1147 update_stmt (stmt);
1148 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1150 fprintf (dump_file, "into: ");
1151 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1153 if (si != NULL
1154 && si->endptr == NULL_TREE
1155 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1157 si = unshare_strinfo (si);
1158 si->endptr = lhs;
1160 zero_length_string (lhs, si);
1161 return;
1164 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1165 return;
1166 if (TREE_CODE (src) != SSA_NAME || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src))
1168 if (idx == 0)
1169 idx = new_stridx (src);
1170 else if (get_strinfo (idx) != NULL)
1172 zero_length_string (lhs, NULL);
1173 return;
1175 if (idx)
1177 location_t loc = gimple_location (stmt);
1178 tree lhsu = fold_convert_loc (loc, size_type_node, lhs);
1179 tree srcu = fold_convert_loc (loc, size_type_node, src);
1180 tree length = fold_build2_loc (loc, MINUS_EXPR,
1181 size_type_node, lhsu, srcu);
1182 strinfo si = new_strinfo (src, idx, length);
1183 si->endptr = lhs;
1184 set_strinfo (idx, si);
1185 find_equal_ptrs (src, idx);
1186 zero_length_string (lhs, si);
1189 else
1190 zero_length_string (lhs, NULL);
1193 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1194 If strlen of the second argument is known, strlen of the first argument
1195 is the same after this call. Furthermore, attempt to convert it to
1196 memcpy. */
1198 static void
1199 handle_builtin_strcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1201 int idx, didx;
1202 tree src, dst, srclen, len, lhs, args, type, fn, oldlen;
1203 bool success;
1204 gimple stmt = gsi_stmt (*gsi);
1205 strinfo si, dsi, olddsi, zsi;
1206 location_t loc;
1207 bool with_bounds = gimple_call_with_bounds_p (stmt);
1209 src = gimple_call_arg (stmt, with_bounds ? 2 : 1);
1210 dst = gimple_call_arg (stmt, 0);
1211 lhs = gimple_call_lhs (stmt);
1212 idx = get_stridx (src);
1213 si = NULL;
1214 if (idx > 0)
1215 si = get_strinfo (idx);
1217 didx = get_stridx (dst);
1218 olddsi = NULL;
1219 oldlen = NULL_TREE;
1220 if (didx > 0)
1221 olddsi = get_strinfo (didx);
1222 else if (didx < 0)
1223 return;
1225 if (olddsi != NULL)
1226 adjust_last_stmt (olddsi, stmt, false);
1228 srclen = NULL_TREE;
1229 if (si != NULL)
1230 srclen = get_string_length (si);
1231 else if (idx < 0)
1232 srclen = build_int_cst (size_type_node, ~idx);
1234 loc = gimple_location (stmt);
1235 if (srclen == NULL_TREE)
1236 switch (bcode)
1238 case BUILT_IN_STRCPY:
1239 case BUILT_IN_STRCPY_CHK:
1240 case BUILT_IN_STRCPY_CHKP:
1241 case BUILT_IN_STRCPY_CHK_CHKP:
1242 if (lhs != NULL_TREE || !builtin_decl_implicit_p (BUILT_IN_STPCPY))
1243 return;
1244 break;
1245 case BUILT_IN_STPCPY:
1246 case BUILT_IN_STPCPY_CHK:
1247 case BUILT_IN_STPCPY_CHKP:
1248 case BUILT_IN_STPCPY_CHK_CHKP:
1249 if (lhs == NULL_TREE)
1250 return;
1251 else
1253 tree lhsuint = fold_convert_loc (loc, size_type_node, lhs);
1254 srclen = fold_convert_loc (loc, size_type_node, dst);
1255 srclen = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
1256 lhsuint, srclen);
1258 break;
1259 default:
1260 gcc_unreachable ();
1263 if (didx == 0)
1265 didx = new_stridx (dst);
1266 if (didx == 0)
1267 return;
1269 if (olddsi != NULL)
1271 oldlen = olddsi->length;
1272 dsi = unshare_strinfo (olddsi);
1273 dsi->length = srclen;
1274 /* Break the chain, so adjust_related_strinfo on later pointers in
1275 the chain won't adjust this one anymore. */
1276 dsi->next = 0;
1277 dsi->stmt = NULL;
1278 dsi->endptr = NULL_TREE;
1280 else
1282 dsi = new_strinfo (dst, didx, srclen);
1283 set_strinfo (didx, dsi);
1284 find_equal_ptrs (dst, didx);
1286 dsi->writable = true;
1287 dsi->dont_invalidate = true;
1289 if (dsi->length == NULL_TREE)
1291 strinfo chainsi;
1293 /* If string length of src is unknown, use delayed length
1294 computation. If string lenth of dst will be needed, it
1295 can be computed by transforming this strcpy call into
1296 stpcpy and subtracting dst from the return value. */
1298 /* Look for earlier strings whose length could be determined if
1299 this strcpy is turned into an stpcpy. */
1301 if (dsi->prev != 0 && (chainsi = verify_related_strinfos (dsi)) != NULL)
1303 for (; chainsi && chainsi != dsi; chainsi = get_strinfo (chainsi->next))
1305 /* When setting a stmt for delayed length computation
1306 prevent all strinfos through dsi from being
1307 invalidated. */
1308 chainsi = unshare_strinfo (chainsi);
1309 chainsi->stmt = stmt;
1310 chainsi->length = NULL_TREE;
1311 chainsi->endptr = NULL_TREE;
1312 chainsi->dont_invalidate = true;
1315 dsi->stmt = stmt;
1316 return;
1319 if (olddsi != NULL)
1321 tree adj = NULL_TREE;
1322 if (oldlen == NULL_TREE)
1324 else if (integer_zerop (oldlen))
1325 adj = srclen;
1326 else if (TREE_CODE (oldlen) == INTEGER_CST
1327 || TREE_CODE (srclen) == INTEGER_CST)
1328 adj = fold_build2_loc (loc, MINUS_EXPR,
1329 TREE_TYPE (srclen), srclen,
1330 fold_convert_loc (loc, TREE_TYPE (srclen),
1331 oldlen));
1332 if (adj != NULL_TREE)
1333 adjust_related_strinfos (loc, dsi, adj);
1334 else
1335 dsi->prev = 0;
1337 /* strcpy src may not overlap dst, so src doesn't need to be
1338 invalidated either. */
1339 if (si != NULL)
1340 si->dont_invalidate = true;
1342 fn = NULL_TREE;
1343 zsi = NULL;
1344 switch (bcode)
1346 case BUILT_IN_STRCPY:
1347 case BUILT_IN_STRCPY_CHKP:
1348 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1349 if (lhs)
1350 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
1351 break;
1352 case BUILT_IN_STRCPY_CHK:
1353 case BUILT_IN_STRCPY_CHK_CHKP:
1354 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK);
1355 if (lhs)
1356 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
1357 break;
1358 case BUILT_IN_STPCPY:
1359 case BUILT_IN_STPCPY_CHKP:
1360 /* This would need adjustment of the lhs (subtract one),
1361 or detection that the trailing '\0' doesn't need to be
1362 written, if it will be immediately overwritten.
1363 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1364 if (lhs)
1366 dsi->endptr = lhs;
1367 zsi = zero_length_string (lhs, dsi);
1369 break;
1370 case BUILT_IN_STPCPY_CHK:
1371 case BUILT_IN_STPCPY_CHK_CHKP:
1372 /* This would need adjustment of the lhs (subtract one),
1373 or detection that the trailing '\0' doesn't need to be
1374 written, if it will be immediately overwritten.
1375 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1376 if (lhs)
1378 dsi->endptr = lhs;
1379 zsi = zero_length_string (lhs, dsi);
1381 break;
1382 default:
1383 gcc_unreachable ();
1385 if (zsi != NULL)
1386 zsi->dont_invalidate = true;
1388 if (fn == NULL_TREE)
1389 return;
1391 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1392 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1394 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1395 len = fold_build2_loc (loc, PLUS_EXPR, type, len, build_int_cst (type, 1));
1396 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1397 GSI_SAME_STMT);
1398 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1400 fprintf (dump_file, "Optimizing: ");
1401 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1403 if (with_bounds)
1405 fn = chkp_maybe_create_clone (fn)->decl;
1406 if (gimple_call_num_args (stmt) == 4)
1407 success = update_gimple_call (gsi, fn, 5, dst,
1408 gimple_call_arg (stmt, 1),
1409 src,
1410 gimple_call_arg (stmt, 3),
1411 len);
1412 else
1413 success = update_gimple_call (gsi, fn, 6, dst,
1414 gimple_call_arg (stmt, 1),
1415 src,
1416 gimple_call_arg (stmt, 3),
1417 len,
1418 gimple_call_arg (stmt, 4));
1420 else
1421 if (gimple_call_num_args (stmt) == 2)
1422 success = update_gimple_call (gsi, fn, 3, dst, src, len);
1423 else
1424 success = update_gimple_call (gsi, fn, 4, dst, src, len,
1425 gimple_call_arg (stmt, 2));
1426 if (success)
1428 stmt = gsi_stmt (*gsi);
1429 gimple_call_set_with_bounds (stmt, with_bounds);
1430 update_stmt (stmt);
1431 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1433 fprintf (dump_file, "into: ");
1434 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1436 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1437 laststmt.stmt = stmt;
1438 laststmt.len = srclen;
1439 laststmt.stridx = dsi->idx;
1441 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1442 fprintf (dump_file, "not possible.\n");
1445 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1446 If strlen of the second argument is known and length of the third argument
1447 is that plus one, strlen of the first argument is the same after this
1448 call. */
1450 static void
1451 handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1453 int idx, didx;
1454 tree src, dst, len, lhs, oldlen, newlen;
1455 gimple stmt = gsi_stmt (*gsi);
1456 strinfo si, dsi, olddsi;
1457 bool with_bounds = gimple_call_with_bounds_p (stmt);
1459 len = gimple_call_arg (stmt, with_bounds ? 4 : 2);
1460 src = gimple_call_arg (stmt, with_bounds ? 2 : 1);
1461 dst = gimple_call_arg (stmt, 0);
1462 idx = get_stridx (src);
1463 if (idx == 0)
1464 return;
1466 didx = get_stridx (dst);
1467 olddsi = NULL;
1468 if (didx > 0)
1469 olddsi = get_strinfo (didx);
1470 else if (didx < 0)
1471 return;
1473 if (olddsi != NULL
1474 && tree_fits_uhwi_p (len)
1475 && !integer_zerop (len))
1476 adjust_last_stmt (olddsi, stmt, false);
1478 if (idx > 0)
1480 gimple def_stmt;
1482 /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */
1483 si = get_strinfo (idx);
1484 if (si == NULL || si->length == NULL_TREE)
1485 return;
1486 if (TREE_CODE (len) != SSA_NAME)
1487 return;
1488 def_stmt = SSA_NAME_DEF_STMT (len);
1489 if (!is_gimple_assign (def_stmt)
1490 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
1491 || gimple_assign_rhs1 (def_stmt) != si->length
1492 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
1493 return;
1495 else
1497 si = NULL;
1498 /* Handle memcpy (x, "abcd", 5) or
1499 memcpy (x, "abc\0uvw", 7). */
1500 if (!tree_fits_uhwi_p (len)
1501 || tree_to_uhwi (len) <= (unsigned HOST_WIDE_INT) ~idx)
1502 return;
1505 if (olddsi != NULL && TREE_CODE (len) == SSA_NAME)
1506 adjust_last_stmt (olddsi, stmt, false);
1508 if (didx == 0)
1510 didx = new_stridx (dst);
1511 if (didx == 0)
1512 return;
1514 if (si != NULL)
1515 newlen = si->length;
1516 else
1517 newlen = build_int_cst (size_type_node, ~idx);
1518 oldlen = NULL_TREE;
1519 if (olddsi != NULL)
1521 dsi = unshare_strinfo (olddsi);
1522 oldlen = olddsi->length;
1523 dsi->length = newlen;
1524 /* Break the chain, so adjust_related_strinfo on later pointers in
1525 the chain won't adjust this one anymore. */
1526 dsi->next = 0;
1527 dsi->stmt = NULL;
1528 dsi->endptr = NULL_TREE;
1530 else
1532 dsi = new_strinfo (dst, didx, newlen);
1533 set_strinfo (didx, dsi);
1534 find_equal_ptrs (dst, didx);
1536 dsi->writable = true;
1537 dsi->dont_invalidate = true;
1538 if (olddsi != NULL)
1540 tree adj = NULL_TREE;
1541 location_t loc = gimple_location (stmt);
1542 if (oldlen == NULL_TREE)
1544 else if (integer_zerop (oldlen))
1545 adj = dsi->length;
1546 else if (TREE_CODE (oldlen) == INTEGER_CST
1547 || TREE_CODE (dsi->length) == INTEGER_CST)
1548 adj = fold_build2_loc (loc, MINUS_EXPR,
1549 TREE_TYPE (dsi->length), dsi->length,
1550 fold_convert_loc (loc, TREE_TYPE (dsi->length),
1551 oldlen));
1552 if (adj != NULL_TREE)
1553 adjust_related_strinfos (loc, dsi, adj);
1554 else
1555 dsi->prev = 0;
1557 /* memcpy src may not overlap dst, so src doesn't need to be
1558 invalidated either. */
1559 if (si != NULL)
1560 si->dont_invalidate = true;
1562 lhs = gimple_call_lhs (stmt);
1563 switch (bcode)
1565 case BUILT_IN_MEMCPY:
1566 case BUILT_IN_MEMCPY_CHK:
1567 case BUILT_IN_MEMCPY_CHKP:
1568 case BUILT_IN_MEMCPY_CHK_CHKP:
1569 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1570 laststmt.stmt = stmt;
1571 laststmt.len = dsi->length;
1572 laststmt.stridx = dsi->idx;
1573 if (lhs)
1574 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
1575 break;
1576 case BUILT_IN_MEMPCPY:
1577 case BUILT_IN_MEMPCPY_CHK:
1578 case BUILT_IN_MEMPCPY_CHKP:
1579 case BUILT_IN_MEMPCPY_CHK_CHKP:
1580 break;
1581 default:
1582 gcc_unreachable ();
1586 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
1587 If strlen of the second argument is known, strlen of the first argument
1588 is increased by the length of the second argument. Furthermore, attempt
1589 to convert it to memcpy/strcpy if the length of the first argument
1590 is known. */
1592 static void
1593 handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1595 int idx, didx;
1596 tree src, dst, srclen, dstlen, len, lhs, args, type, fn, objsz, endptr;
1597 bool success;
1598 gimple stmt = gsi_stmt (*gsi);
1599 strinfo si, dsi;
1600 location_t loc;
1601 bool with_bounds = gimple_call_with_bounds_p (stmt);
1603 src = gimple_call_arg (stmt, with_bounds ? 2 : 1);
1604 dst = gimple_call_arg (stmt, 0);
1605 lhs = gimple_call_lhs (stmt);
1607 didx = get_stridx (dst);
1608 if (didx < 0)
1609 return;
1611 dsi = NULL;
1612 if (didx > 0)
1613 dsi = get_strinfo (didx);
1614 if (dsi == NULL || get_string_length (dsi) == NULL_TREE)
1616 /* strcat (p, q) can be transformed into
1617 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
1618 with length endptr - p if we need to compute the length
1619 later on. Don't do this transformation if we don't need
1620 it. */
1621 if (builtin_decl_implicit_p (BUILT_IN_STPCPY) && lhs == NULL_TREE)
1623 if (didx == 0)
1625 didx = new_stridx (dst);
1626 if (didx == 0)
1627 return;
1629 if (dsi == NULL)
1631 dsi = new_strinfo (dst, didx, NULL_TREE);
1632 set_strinfo (didx, dsi);
1633 find_equal_ptrs (dst, didx);
1635 else
1637 dsi = unshare_strinfo (dsi);
1638 dsi->length = NULL_TREE;
1639 dsi->next = 0;
1640 dsi->endptr = NULL_TREE;
1642 dsi->writable = true;
1643 dsi->stmt = stmt;
1644 dsi->dont_invalidate = true;
1646 return;
1649 srclen = NULL_TREE;
1650 si = NULL;
1651 idx = get_stridx (src);
1652 if (idx < 0)
1653 srclen = build_int_cst (size_type_node, ~idx);
1654 else if (idx > 0)
1656 si = get_strinfo (idx);
1657 if (si != NULL)
1658 srclen = get_string_length (si);
1661 loc = gimple_location (stmt);
1662 dstlen = dsi->length;
1663 endptr = dsi->endptr;
1665 dsi = unshare_strinfo (dsi);
1666 dsi->endptr = NULL_TREE;
1667 dsi->stmt = NULL;
1668 dsi->writable = true;
1670 if (srclen != NULL_TREE)
1672 dsi->length = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (dsi->length),
1673 dsi->length, srclen);
1674 adjust_related_strinfos (loc, dsi, srclen);
1675 dsi->dont_invalidate = true;
1677 else
1679 dsi->length = NULL;
1680 if (lhs == NULL_TREE && builtin_decl_implicit_p (BUILT_IN_STPCPY))
1681 dsi->dont_invalidate = true;
1684 if (si != NULL)
1685 /* strcat src may not overlap dst, so src doesn't need to be
1686 invalidated either. */
1687 si->dont_invalidate = true;
1689 /* For now. Could remove the lhs from the call and add
1690 lhs = dst; afterwards. */
1691 if (lhs)
1692 return;
1694 fn = NULL_TREE;
1695 objsz = NULL_TREE;
1696 switch (bcode)
1698 case BUILT_IN_STRCAT:
1699 case BUILT_IN_STRCAT_CHKP:
1700 if (srclen != NULL_TREE)
1701 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1702 else
1703 fn = builtin_decl_implicit (BUILT_IN_STRCPY);
1704 break;
1705 case BUILT_IN_STRCAT_CHK:
1706 case BUILT_IN_STRCAT_CHK_CHKP:
1707 if (srclen != NULL_TREE)
1708 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK);
1709 else
1710 fn = builtin_decl_explicit (BUILT_IN_STRCPY_CHK);
1711 objsz = gimple_call_arg (stmt, with_bounds ? 4 : 2);
1712 break;
1713 default:
1714 gcc_unreachable ();
1717 if (fn == NULL_TREE)
1718 return;
1720 len = NULL_TREE;
1721 if (srclen != NULL_TREE)
1723 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1724 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1726 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1727 len = fold_build2_loc (loc, PLUS_EXPR, type, len,
1728 build_int_cst (type, 1));
1729 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1730 GSI_SAME_STMT);
1732 if (endptr)
1733 dst = fold_convert_loc (loc, TREE_TYPE (dst), unshare_expr (endptr));
1734 else
1735 dst = fold_build2_loc (loc, POINTER_PLUS_EXPR,
1736 TREE_TYPE (dst), unshare_expr (dst),
1737 fold_convert_loc (loc, sizetype,
1738 unshare_expr (dstlen)));
1739 dst = force_gimple_operand_gsi (gsi, dst, true, NULL_TREE, true,
1740 GSI_SAME_STMT);
1741 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1743 fprintf (dump_file, "Optimizing: ");
1744 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1746 if (with_bounds)
1748 fn = chkp_maybe_create_clone (fn)->decl;
1749 if (srclen != NULL_TREE)
1750 success = update_gimple_call (gsi, fn, 5 + (objsz != NULL_TREE),
1751 dst,
1752 gimple_call_arg (stmt, 1),
1753 src,
1754 gimple_call_arg (stmt, 3),
1755 len, objsz);
1756 else
1757 success = update_gimple_call (gsi, fn, 4 + (objsz != NULL_TREE),
1758 dst,
1759 gimple_call_arg (stmt, 1),
1760 src,
1761 gimple_call_arg (stmt, 3),
1762 objsz);
1764 else
1765 if (srclen != NULL_TREE)
1766 success = update_gimple_call (gsi, fn, 3 + (objsz != NULL_TREE),
1767 dst, src, len, objsz);
1768 else
1769 success = update_gimple_call (gsi, fn, 2 + (objsz != NULL_TREE),
1770 dst, src, objsz);
1771 if (success)
1773 stmt = gsi_stmt (*gsi);
1774 gimple_call_set_with_bounds (stmt, with_bounds);
1775 update_stmt (stmt);
1776 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1778 fprintf (dump_file, "into: ");
1779 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1781 /* If srclen == NULL, note that current string length can be
1782 computed by transforming this strcpy into stpcpy. */
1783 if (srclen == NULL_TREE && dsi->dont_invalidate)
1784 dsi->stmt = stmt;
1785 adjust_last_stmt (dsi, stmt, true);
1786 if (srclen != NULL_TREE)
1788 laststmt.stmt = stmt;
1789 laststmt.len = srclen;
1790 laststmt.stridx = dsi->idx;
1793 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1794 fprintf (dump_file, "not possible.\n");
1797 /* Handle a call to malloc or calloc. */
1799 static void
1800 handle_builtin_malloc (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1802 gimple stmt = gsi_stmt (*gsi);
1803 tree lhs = gimple_call_lhs (stmt);
1804 gcc_assert (get_stridx (lhs) == 0);
1805 int idx = new_stridx (lhs);
1806 tree length = NULL_TREE;
1807 if (bcode == BUILT_IN_CALLOC)
1808 length = build_int_cst (size_type_node, 0);
1809 strinfo si = new_strinfo (lhs, idx, length);
1810 if (bcode == BUILT_IN_CALLOC)
1811 si->endptr = lhs;
1812 set_strinfo (idx, si);
1813 si->writable = true;
1814 si->stmt = stmt;
1815 si->dont_invalidate = true;
1818 /* Handle a call to memset.
1819 After a call to calloc, memset(,0,) is unnecessary.
1820 memset(malloc(n),0,n) is calloc(n,1). */
1822 static bool
1823 handle_builtin_memset (gimple_stmt_iterator *gsi)
1825 gimple stmt2 = gsi_stmt (*gsi);
1826 if (!integer_zerop (gimple_call_arg (stmt2, 1)))
1827 return true;
1828 tree ptr = gimple_call_arg (stmt2, 0);
1829 int idx1 = get_stridx (ptr);
1830 if (idx1 <= 0)
1831 return true;
1832 strinfo si1 = get_strinfo (idx1);
1833 if (!si1)
1834 return true;
1835 gimple stmt1 = si1->stmt;
1836 if (!stmt1 || !is_gimple_call (stmt1))
1837 return true;
1838 tree callee1 = gimple_call_fndecl (stmt1);
1839 if (!gimple_call_builtin_p (stmt1, BUILT_IN_NORMAL))
1840 return true;
1841 enum built_in_function code1 = DECL_FUNCTION_CODE (callee1);
1842 tree size = gimple_call_arg (stmt2, 2);
1843 if (code1 == BUILT_IN_CALLOC)
1844 /* Not touching stmt1 */ ;
1845 else if (code1 == BUILT_IN_MALLOC
1846 && operand_equal_p (gimple_call_arg (stmt1, 0), size, 0))
1848 gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt1);
1849 update_gimple_call (&gsi1, builtin_decl_implicit (BUILT_IN_CALLOC), 2,
1850 size, build_one_cst (size_type_node));
1851 si1->length = build_int_cst (size_type_node, 0);
1852 si1->stmt = gsi_stmt (gsi1);
1854 else
1855 return true;
1856 tree lhs = gimple_call_lhs (stmt2);
1857 unlink_stmt_vdef (stmt2);
1858 if (lhs)
1860 gimple assign = gimple_build_assign (lhs, ptr);
1861 gsi_replace (gsi, assign, false);
1863 else
1865 gsi_remove (gsi, true);
1866 release_defs (stmt2);
1869 return false;
1872 /* Handle a POINTER_PLUS_EXPR statement.
1873 For p = "abcd" + 2; compute associated length, or if
1874 p = q + off is pointing to a '\0' character of a string, call
1875 zero_length_string on it. */
1877 static void
1878 handle_pointer_plus (gimple_stmt_iterator *gsi)
1880 gimple stmt = gsi_stmt (*gsi);
1881 tree lhs = gimple_assign_lhs (stmt), off;
1882 int idx = get_stridx (gimple_assign_rhs1 (stmt));
1883 strinfo si, zsi;
1885 if (idx == 0)
1886 return;
1888 if (idx < 0)
1890 tree off = gimple_assign_rhs2 (stmt);
1891 if (tree_fits_uhwi_p (off)
1892 && tree_to_uhwi (off) <= (unsigned HOST_WIDE_INT) ~idx)
1893 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)]
1894 = ~(~idx - (int) tree_to_uhwi (off));
1895 return;
1898 si = get_strinfo (idx);
1899 if (si == NULL || si->length == NULL_TREE)
1900 return;
1902 off = gimple_assign_rhs2 (stmt);
1903 zsi = NULL;
1904 if (operand_equal_p (si->length, off, 0))
1905 zsi = zero_length_string (lhs, si);
1906 else if (TREE_CODE (off) == SSA_NAME)
1908 gimple def_stmt = SSA_NAME_DEF_STMT (off);
1909 if (gimple_assign_single_p (def_stmt)
1910 && operand_equal_p (si->length, gimple_assign_rhs1 (def_stmt), 0))
1911 zsi = zero_length_string (lhs, si);
1913 if (zsi != NULL
1914 && si->endptr != NULL_TREE
1915 && si->endptr != lhs
1916 && TREE_CODE (si->endptr) == SSA_NAME)
1918 enum tree_code rhs_code
1919 = useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (si->endptr))
1920 ? SSA_NAME : NOP_EXPR;
1921 gimple_assign_set_rhs_with_ops (gsi, rhs_code, si->endptr);
1922 gcc_assert (gsi_stmt (*gsi) == stmt);
1923 update_stmt (stmt);
1927 /* Handle a single character store. */
1929 static bool
1930 handle_char_store (gimple_stmt_iterator *gsi)
1932 int idx = -1;
1933 strinfo si = NULL;
1934 gimple stmt = gsi_stmt (*gsi);
1935 tree ssaname = NULL_TREE, lhs = gimple_assign_lhs (stmt);
1937 if (TREE_CODE (lhs) == MEM_REF
1938 && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME)
1940 if (integer_zerop (TREE_OPERAND (lhs, 1)))
1942 ssaname = TREE_OPERAND (lhs, 0);
1943 idx = get_stridx (ssaname);
1946 else
1947 idx = get_addr_stridx (lhs);
1949 if (idx > 0)
1951 si = get_strinfo (idx);
1952 if (si != NULL && si->length != NULL_TREE && integer_zerop (si->length))
1954 if (initializer_zerop (gimple_assign_rhs1 (stmt)))
1956 /* When storing '\0', the store can be removed
1957 if we know it has been stored in the current function. */
1958 if (!stmt_could_throw_p (stmt) && si->writable)
1960 unlink_stmt_vdef (stmt);
1961 release_defs (stmt);
1962 gsi_remove (gsi, true);
1963 return false;
1965 else
1967 si->writable = true;
1968 gsi_next (gsi);
1969 return false;
1972 else
1973 /* Otherwise this statement overwrites the '\0' with
1974 something, if the previous stmt was a memcpy,
1975 its length may be decreased. */
1976 adjust_last_stmt (si, stmt, false);
1978 else if (si != NULL && integer_zerop (gimple_assign_rhs1 (stmt)))
1980 si = unshare_strinfo (si);
1981 si->length = build_int_cst (size_type_node, 0);
1982 si->endptr = NULL;
1983 si->prev = 0;
1984 si->next = 0;
1985 si->stmt = NULL;
1986 si->first = 0;
1987 si->writable = true;
1988 if (ssaname && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname))
1989 si->endptr = ssaname;
1990 si->dont_invalidate = true;
1992 /* If si->length is non-zero constant, we aren't overwriting '\0',
1993 and if we aren't storing '\0', we know that the length of the
1994 string and any other zero terminated string in memory remains
1995 the same. In that case we move to the next gimple statement and
1996 return to signal the caller that it shouldn't invalidate anything.
1998 This is benefical for cases like:
2000 char p[20];
2001 void foo (char *q)
2003 strcpy (p, "foobar");
2004 size_t len = strlen (p); // This can be optimized into 6
2005 size_t len2 = strlen (q); // This has to be computed
2006 p[0] = 'X';
2007 size_t len3 = strlen (p); // This can be optimized into 6
2008 size_t len4 = strlen (q); // This can be optimized into len2
2009 bar (len, len2, len3, len4);
2012 else if (si != NULL && si->length != NULL_TREE
2013 && TREE_CODE (si->length) == INTEGER_CST
2014 && integer_nonzerop (gimple_assign_rhs1 (stmt)))
2016 gsi_next (gsi);
2017 return false;
2020 else if (idx == 0 && initializer_zerop (gimple_assign_rhs1 (stmt)))
2022 if (ssaname)
2024 si = zero_length_string (ssaname, NULL);
2025 if (si != NULL)
2026 si->dont_invalidate = true;
2028 else
2030 int idx = new_addr_stridx (lhs);
2031 if (idx != 0)
2033 si = new_strinfo (build_fold_addr_expr (lhs), idx,
2034 build_int_cst (size_type_node, 0));
2035 set_strinfo (idx, si);
2036 si->dont_invalidate = true;
2039 if (si != NULL)
2040 si->writable = true;
2042 else if (idx == 0
2043 && TREE_CODE (gimple_assign_rhs1 (stmt)) == STRING_CST
2044 && ssaname == NULL_TREE
2045 && TREE_CODE (TREE_TYPE (lhs)) == ARRAY_TYPE)
2047 size_t l = strlen (TREE_STRING_POINTER (gimple_assign_rhs1 (stmt)));
2048 HOST_WIDE_INT a = int_size_in_bytes (TREE_TYPE (lhs));
2049 if (a > 0 && (unsigned HOST_WIDE_INT) a > l)
2051 int idx = new_addr_stridx (lhs);
2052 if (idx != 0)
2054 si = new_strinfo (build_fold_addr_expr (lhs), idx,
2055 build_int_cst (size_type_node, l));
2056 set_strinfo (idx, si);
2057 si->dont_invalidate = true;
2062 if (si != NULL && initializer_zerop (gimple_assign_rhs1 (stmt)))
2064 /* Allow adjust_last_stmt to remove it if the stored '\0'
2065 is immediately overwritten. */
2066 laststmt.stmt = stmt;
2067 laststmt.len = build_int_cst (size_type_node, 1);
2068 laststmt.stridx = si->idx;
2070 return true;
2073 /* Attempt to optimize a single statement at *GSI using string length
2074 knowledge. */
2076 static bool
2077 strlen_optimize_stmt (gimple_stmt_iterator *gsi)
2079 gimple stmt = gsi_stmt (*gsi);
2081 if (is_gimple_call (stmt))
2083 tree callee = gimple_call_fndecl (stmt);
2084 if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
2085 switch (DECL_FUNCTION_CODE (callee))
2087 case BUILT_IN_STRLEN:
2088 case BUILT_IN_STRLEN_CHKP:
2089 handle_builtin_strlen (gsi);
2090 break;
2091 case BUILT_IN_STRCHR:
2092 case BUILT_IN_STRCHR_CHKP:
2093 handle_builtin_strchr (gsi);
2094 break;
2095 case BUILT_IN_STRCPY:
2096 case BUILT_IN_STRCPY_CHK:
2097 case BUILT_IN_STPCPY:
2098 case BUILT_IN_STPCPY_CHK:
2099 case BUILT_IN_STRCPY_CHKP:
2100 case BUILT_IN_STRCPY_CHK_CHKP:
2101 case BUILT_IN_STPCPY_CHKP:
2102 case BUILT_IN_STPCPY_CHK_CHKP:
2103 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee), gsi);
2104 break;
2105 case BUILT_IN_MEMCPY:
2106 case BUILT_IN_MEMCPY_CHK:
2107 case BUILT_IN_MEMPCPY:
2108 case BUILT_IN_MEMPCPY_CHK:
2109 case BUILT_IN_MEMCPY_CHKP:
2110 case BUILT_IN_MEMCPY_CHK_CHKP:
2111 case BUILT_IN_MEMPCPY_CHKP:
2112 case BUILT_IN_MEMPCPY_CHK_CHKP:
2113 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi);
2114 break;
2115 case BUILT_IN_STRCAT:
2116 case BUILT_IN_STRCAT_CHK:
2117 case BUILT_IN_STRCAT_CHKP:
2118 case BUILT_IN_STRCAT_CHK_CHKP:
2119 handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi);
2120 break;
2121 case BUILT_IN_MALLOC:
2122 case BUILT_IN_CALLOC:
2123 handle_builtin_malloc (DECL_FUNCTION_CODE (callee), gsi);
2124 break;
2125 case BUILT_IN_MEMSET:
2126 if (!handle_builtin_memset (gsi))
2127 return false;
2128 break;
2129 default:
2130 break;
2133 else if (is_gimple_assign (stmt) && !gimple_clobber_p (stmt))
2135 tree lhs = gimple_assign_lhs (stmt);
2137 if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs)))
2139 if (gimple_assign_single_p (stmt)
2140 || (gimple_assign_cast_p (stmt)
2141 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))))
2143 int idx = get_stridx (gimple_assign_rhs1 (stmt));
2144 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = idx;
2146 else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
2147 handle_pointer_plus (gsi);
2149 else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
2151 tree type = TREE_TYPE (lhs);
2152 if (TREE_CODE (type) == ARRAY_TYPE)
2153 type = TREE_TYPE (type);
2154 if (TREE_CODE (type) == INTEGER_TYPE
2155 && TYPE_MODE (type) == TYPE_MODE (char_type_node)
2156 && TYPE_PRECISION (type) == TYPE_PRECISION (char_type_node))
2158 if (! handle_char_store (gsi))
2159 return false;
2164 if (gimple_vdef (stmt))
2165 maybe_invalidate (stmt);
2166 return true;
2169 /* Recursively call maybe_invalidate on stmts that might be executed
2170 in between dombb and current bb and that contain a vdef. Stop when
2171 *count stmts are inspected, or if the whole strinfo vector has
2172 been invalidated. */
2174 static void
2175 do_invalidate (basic_block dombb, gimple phi, bitmap visited, int *count)
2177 unsigned int i, n = gimple_phi_num_args (phi);
2179 for (i = 0; i < n; i++)
2181 tree vuse = gimple_phi_arg_def (phi, i);
2182 gimple stmt = SSA_NAME_DEF_STMT (vuse);
2183 basic_block bb = gimple_bb (stmt);
2184 if (bb == NULL
2185 || bb == dombb
2186 || !bitmap_set_bit (visited, bb->index)
2187 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
2188 continue;
2189 while (1)
2191 if (gimple_code (stmt) == GIMPLE_PHI)
2193 do_invalidate (dombb, stmt, visited, count);
2194 if (*count == 0)
2195 return;
2196 break;
2198 if (--*count == 0)
2199 return;
2200 if (!maybe_invalidate (stmt))
2202 *count = 0;
2203 return;
2205 vuse = gimple_vuse (stmt);
2206 stmt = SSA_NAME_DEF_STMT (vuse);
2207 if (gimple_bb (stmt) != bb)
2209 bb = gimple_bb (stmt);
2210 if (bb == NULL
2211 || bb == dombb
2212 || !bitmap_set_bit (visited, bb->index)
2213 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
2214 break;
2220 class strlen_dom_walker : public dom_walker
2222 public:
2223 strlen_dom_walker (cdi_direction direction) : dom_walker (direction) {}
2225 virtual void before_dom_children (basic_block);
2226 virtual void after_dom_children (basic_block);
2229 /* Callback for walk_dominator_tree. Attempt to optimize various
2230 string ops by remembering string lenths pointed by pointer SSA_NAMEs. */
2232 void
2233 strlen_dom_walker::before_dom_children (basic_block bb)
2235 basic_block dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
2237 if (dombb == NULL)
2238 stridx_to_strinfo = NULL;
2239 else
2241 stridx_to_strinfo = ((vec<strinfo, va_heap, vl_embed> *) dombb->aux);
2242 if (stridx_to_strinfo)
2244 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
2245 gsi_next (&gsi))
2247 gphi *phi = gsi.phi ();
2248 if (virtual_operand_p (gimple_phi_result (phi)))
2250 bitmap visited = BITMAP_ALLOC (NULL);
2251 int count_vdef = 100;
2252 do_invalidate (dombb, phi, visited, &count_vdef);
2253 BITMAP_FREE (visited);
2254 if (count_vdef == 0)
2256 /* If there were too many vdefs in between immediate
2257 dominator and current bb, invalidate everything.
2258 If stridx_to_strinfo has been unshared, we need
2259 to free it, otherwise just set it to NULL. */
2260 if (!strinfo_shared ())
2262 unsigned int i;
2263 strinfo si;
2265 for (i = 1;
2266 vec_safe_iterate (stridx_to_strinfo, i, &si);
2267 ++i)
2269 free_strinfo (si);
2270 (*stridx_to_strinfo)[i] = NULL;
2273 else
2274 stridx_to_strinfo = NULL;
2276 break;
2282 /* If all PHI arguments have the same string index, the PHI result
2283 has it as well. */
2284 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
2285 gsi_next (&gsi))
2287 gphi *phi = gsi.phi ();
2288 tree result = gimple_phi_result (phi);
2289 if (!virtual_operand_p (result) && POINTER_TYPE_P (TREE_TYPE (result)))
2291 int idx = get_stridx (gimple_phi_arg_def (phi, 0));
2292 if (idx != 0)
2294 unsigned int i, n = gimple_phi_num_args (phi);
2295 for (i = 1; i < n; i++)
2296 if (idx != get_stridx (gimple_phi_arg_def (phi, i)))
2297 break;
2298 if (i == n)
2299 ssa_ver_to_stridx[SSA_NAME_VERSION (result)] = idx;
2304 /* Attempt to optimize individual statements. */
2305 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2306 if (strlen_optimize_stmt (&gsi))
2307 gsi_next (&gsi);
2309 bb->aux = stridx_to_strinfo;
2310 if (vec_safe_length (stridx_to_strinfo) && !strinfo_shared ())
2311 (*stridx_to_strinfo)[0] = (strinfo) bb;
2314 /* Callback for walk_dominator_tree. Free strinfo vector if it is
2315 owned by the current bb, clear bb->aux. */
2317 void
2318 strlen_dom_walker::after_dom_children (basic_block bb)
2320 if (bb->aux)
2322 stridx_to_strinfo = ((vec<strinfo, va_heap, vl_embed> *) bb->aux);
2323 if (vec_safe_length (stridx_to_strinfo)
2324 && (*stridx_to_strinfo)[0] == (strinfo) bb)
2326 unsigned int i;
2327 strinfo si;
2329 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
2330 free_strinfo (si);
2331 vec_free (stridx_to_strinfo);
2333 bb->aux = NULL;
2337 /* Main entry point. */
2339 namespace {
2341 const pass_data pass_data_strlen =
2343 GIMPLE_PASS, /* type */
2344 "strlen", /* name */
2345 OPTGROUP_NONE, /* optinfo_flags */
2346 TV_TREE_STRLEN, /* tv_id */
2347 ( PROP_cfg | PROP_ssa ), /* properties_required */
2348 0, /* properties_provided */
2349 0, /* properties_destroyed */
2350 0, /* todo_flags_start */
2351 0, /* todo_flags_finish */
2354 class pass_strlen : public gimple_opt_pass
2356 public:
2357 pass_strlen (gcc::context *ctxt)
2358 : gimple_opt_pass (pass_data_strlen, ctxt)
2361 /* opt_pass methods: */
2362 virtual bool gate (function *) { return flag_optimize_strlen != 0; }
2363 virtual unsigned int execute (function *);
2365 }; // class pass_strlen
2367 unsigned int
2368 pass_strlen::execute (function *fun)
2370 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
2371 max_stridx = 1;
2373 calculate_dominance_info (CDI_DOMINATORS);
2375 /* String length optimization is implemented as a walk of the dominator
2376 tree and a forward walk of statements within each block. */
2377 strlen_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr);
2379 ssa_ver_to_stridx.release ();
2380 strinfo_pool.release ();
2381 if (decl_to_stridxlist_htab)
2383 obstack_free (&stridx_obstack, NULL);
2384 delete decl_to_stridxlist_htab;
2385 decl_to_stridxlist_htab = NULL;
2387 laststmt.stmt = NULL;
2388 laststmt.len = NULL_TREE;
2389 laststmt.stridx = 0;
2391 return 0;
2394 } // anon namespace
2396 gimple_opt_pass *
2397 make_pass_strlen (gcc::context *ctxt)
2399 return new pass_strlen (ctxt);