1 /* String length optimization
2 Copyright (C) 2011-2019 Free Software Foundation, Inc.
3 Contributed by Jakub Jelinek <jakub@redhat.com>
4
5 This file is part of GCC.
6
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.
11
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.
16
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/>. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "backend.h"
25 #include "rtl.h"
26 #include "tree.h"
27 #include "gimple.h"
28 #include "alloc-pool.h"
29 #include "tree-pass.h"
30 #include "ssa.h"
31 #include "cgraph.h"
32 #include "gimple-pretty-print.h"
33 #include "gimple-ssa-warn-restrict.h"
34 #include "fold-const.h"
35 #include "stor-layout.h"
36 #include "gimple-fold.h"
37 #include "tree-eh.h"
38 #include "gimplify.h"
39 #include "gimple-iterator.h"
40 #include "gimplify-me.h"
41 #include "expr.h"
42 #include "tree-cfg.h"
43 #include "tree-dfa.h"
44 #include "domwalk.h"
45 #include "tree-ssa-alias.h"
46 #include "tree-ssa-propagate.h"
47 #include "tree-ssa-strlen.h"
48 #include "params.h"
49 #include "tree-hash-traits.h"
50 #include "tree-object-size.h"
51 #include "builtins.h"
52 #include "target.h"
53 #include "diagnostic-core.h"
54 #include "diagnostic.h"
55 #include "intl.h"
56 #include "attribs.h"
57 #include "calls.h"
58
59 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
60 is an index into strinfo vector, negative value stands for
61 string length of a string literal (~strlen). */
62 static vec<int> ssa_ver_to_stridx;
63
64 /* Number of currently active string indexes plus one. */
65 static int max_stridx;
66
67 /* String information record. */
68 struct strinfo
69 {
70 /* Number of leading characters that are known to be nonzero. This is
71 also the length of the string if FULL_STRING_P.
72
73 The values in a list of related string pointers must be consistent;
74 that is, if strinfo B comes X bytes after strinfo A, it must be
75 the case that A->nonzero_chars == X + B->nonzero_chars. */
76 tree nonzero_chars;
77 /* Any of the corresponding pointers for querying alias oracle. */
78 tree ptr;
79 /* This is used for two things:
80
81 - To record the statement that should be used for delayed length
82 computations. We maintain the invariant that all related strinfos
83 have delayed lengths or none do.
84
85 - To record the malloc or calloc call that produced this result. */
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 /* True if the string is known to be nul-terminated after NONZERO_CHARS
124 characters. False is useful when detecting strings that are built
125 up via successive memcpys. */
126 bool full_string_p;
127 };
128
129 /* Pool for allocating strinfo_struct entries. */
130 static object_allocator<strinfo> strinfo_pool ("strinfo pool");
131
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;
139
140 /* One OFFSET->IDX mapping. */
141 struct stridxlist
142 {
143 struct stridxlist *next;
144 HOST_WIDE_INT offset;
145 int idx;
146 };
147
148 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
149 struct decl_stridxlist_map
150 {
151 struct tree_map_base base;
152 struct stridxlist list;
153 };
154
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;
158
159 /* Hash table mapping strlen (or strnlen with constant bound and return
160 smaller than bound) calls to stridx instances describing
161 the calls' arguments. Non-null only when warn_stringop_truncation
162 is non-zero. */
163 typedef std::pair<int, location_t> stridx_strlenloc;
164 static hash_map<tree, stridx_strlenloc> *strlen_to_stridx;
165
166 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
167 static struct obstack stridx_obstack;
168
169 /* Last memcpy statement if it could be adjusted if the trailing
170 '\0' written is immediately overwritten, or
171 *x = '\0' store that could be removed if it is immediately overwritten. */
172 struct laststmt_struct
173 {
174 gimple *stmt;
175 tree len;
176 int stridx;
177 } laststmt;
178
179 static int get_stridx_plus_constant (strinfo *, unsigned HOST_WIDE_INT, tree);
180 static void handle_builtin_stxncpy (built_in_function, gimple_stmt_iterator *);
181
182 /* Return:
183
184 - 1 if SI is known to start with more than OFF nonzero characters.
185
186 - 0 if SI is known to start with OFF nonzero characters,
187 but is not known to start with more.
188
189 - -1 if SI might not start with OFF nonzero characters. */
190
191 static inline int
compare_nonzero_chars(strinfo * si,unsigned HOST_WIDE_INT off)192 compare_nonzero_chars (strinfo *si, unsigned HOST_WIDE_INT off)
193 {
194 if (si->nonzero_chars
195 && TREE_CODE (si->nonzero_chars) == INTEGER_CST)
196 return compare_tree_int (si->nonzero_chars, off);
197 else
198 return -1;
199 }
200
201 /* Return true if SI is known to be a zero-length string. */
202
203 static inline bool
zero_length_string_p(strinfo * si)204 zero_length_string_p (strinfo *si)
205 {
206 return si->full_string_p && integer_zerop (si->nonzero_chars);
207 }
208
209 /* Return strinfo vector entry IDX. */
210
211 static inline strinfo *
get_strinfo(int idx)212 get_strinfo (int idx)
213 {
214 if (vec_safe_length (stridx_to_strinfo) <= (unsigned int) idx)
215 return NULL;
216 return (*stridx_to_strinfo)[idx];
217 }
218
219 /* Get the next strinfo in the chain after SI, or null if none. */
220
221 static inline strinfo *
get_next_strinfo(strinfo * si)222 get_next_strinfo (strinfo *si)
223 {
224 if (si->next == 0)
225 return NULL;
226 strinfo *nextsi = get_strinfo (si->next);
227 if (nextsi == NULL || nextsi->first != si->first || nextsi->prev != si->idx)
228 return NULL;
229 return nextsi;
230 }
231
232 /* Helper function for get_stridx. Return the strinfo index of the address
233 of EXP, which is available in PTR if nonnull. If OFFSET_OUT, it is
234 OK to return the index for some X <= &EXP and store &EXP - X in
235 *OFFSET_OUT. */
236
237 static int
get_addr_stridx(tree exp,tree ptr,unsigned HOST_WIDE_INT * offset_out)238 get_addr_stridx (tree exp, tree ptr, unsigned HOST_WIDE_INT *offset_out)
239 {
240 HOST_WIDE_INT off;
241 struct stridxlist *list, *last = NULL;
242 tree base;
243
244 if (!decl_to_stridxlist_htab)
245 return 0;
246
247 poly_int64 poff;
248 base = get_addr_base_and_unit_offset (exp, &poff);
249 if (base == NULL || !DECL_P (base) || !poff.is_constant (&off))
250 return 0;
251
252 list = decl_to_stridxlist_htab->get (base);
253 if (list == NULL)
254 return 0;
255
256 do
257 {
258 if (list->offset == off)
259 {
260 if (offset_out)
261 *offset_out = 0;
262 return list->idx;
263 }
264 if (list->offset > off)
265 return 0;
266 last = list;
267 list = list->next;
268 }
269 while (list);
270
271 if ((offset_out || ptr) && last && last->idx > 0)
272 {
273 unsigned HOST_WIDE_INT rel_off
274 = (unsigned HOST_WIDE_INT) off - last->offset;
275 strinfo *si = get_strinfo (last->idx);
276 if (si && compare_nonzero_chars (si, rel_off) >= 0)
277 {
278 if (offset_out)
279 {
280 *offset_out = rel_off;
281 return last->idx;
282 }
283 else
284 return get_stridx_plus_constant (si, rel_off, ptr);
285 }
286 }
287 return 0;
288 }
289
290 /* Return string index for EXP. */
291
292 static int
get_stridx(tree exp)293 get_stridx (tree exp)
294 {
295 if (TREE_CODE (exp) == SSA_NAME)
296 {
297 if (ssa_ver_to_stridx[SSA_NAME_VERSION (exp)])
298 return ssa_ver_to_stridx[SSA_NAME_VERSION (exp)];
299 int i;
300 tree e = exp;
301 HOST_WIDE_INT off = 0;
302 for (i = 0; i < 5; i++)
303 {
304 gimple *def_stmt = SSA_NAME_DEF_STMT (e);
305 if (!is_gimple_assign (def_stmt)
306 || gimple_assign_rhs_code (def_stmt) != POINTER_PLUS_EXPR)
307 return 0;
308 tree rhs1 = gimple_assign_rhs1 (def_stmt);
309 tree rhs2 = gimple_assign_rhs2 (def_stmt);
310 if (TREE_CODE (rhs1) != SSA_NAME
311 || !tree_fits_shwi_p (rhs2))
312 return 0;
313 HOST_WIDE_INT this_off = tree_to_shwi (rhs2);
314 if (this_off < 0)
315 return 0;
316 off = (unsigned HOST_WIDE_INT) off + this_off;
317 if (off < 0)
318 return 0;
319 if (ssa_ver_to_stridx[SSA_NAME_VERSION (rhs1)])
320 {
321 strinfo *si
322 = get_strinfo (ssa_ver_to_stridx[SSA_NAME_VERSION (rhs1)]);
323 if (si && compare_nonzero_chars (si, off) >= 0)
324 return get_stridx_plus_constant (si, off, exp);
325 }
326 e = rhs1;
327 }
328 return 0;
329 }
330
331 if (TREE_CODE (exp) == ADDR_EXPR)
332 {
333 int idx = get_addr_stridx (TREE_OPERAND (exp, 0), exp, NULL);
334 if (idx != 0)
335 return idx;
336 }
337
338 const char *p = c_getstr (exp);
339 if (p)
340 return ~(int) strlen (p);
341
342 return 0;
343 }
344
345 /* Return true if strinfo vector is shared with the immediate dominator. */
346
347 static inline bool
strinfo_shared(void)348 strinfo_shared (void)
349 {
350 return vec_safe_length (stridx_to_strinfo)
351 && (*stridx_to_strinfo)[0] != NULL;
352 }
353
354 /* Unshare strinfo vector that is shared with the immediate dominator. */
355
356 static void
unshare_strinfo_vec(void)357 unshare_strinfo_vec (void)
358 {
359 strinfo *si;
360 unsigned int i = 0;
361
362 gcc_assert (strinfo_shared ());
363 stridx_to_strinfo = vec_safe_copy (stridx_to_strinfo);
364 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
365 if (si != NULL)
366 si->refcount++;
367 (*stridx_to_strinfo)[0] = NULL;
368 }
369
370 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
371 Return a pointer to the location where the string index can
372 be stored (if 0) or is stored, or NULL if this can't be tracked. */
373
374 static int *
addr_stridxptr(tree exp)375 addr_stridxptr (tree exp)
376 {
377 HOST_WIDE_INT off;
378
379 poly_int64 poff;
380 tree base = get_addr_base_and_unit_offset (exp, &poff);
381 if (base == NULL_TREE || !DECL_P (base) || !poff.is_constant (&off))
382 return NULL;
383
384 if (!decl_to_stridxlist_htab)
385 {
386 decl_to_stridxlist_htab
387 = new hash_map<tree_decl_hash, stridxlist> (64);
388 gcc_obstack_init (&stridx_obstack);
389 }
390
391 bool existed;
392 stridxlist *list = &decl_to_stridxlist_htab->get_or_insert (base, &existed);
393 if (existed)
394 {
395 int i;
396 stridxlist *before = NULL;
397 for (i = 0; i < 32; i++)
398 {
399 if (list->offset == off)
400 return &list->idx;
401 if (list->offset > off && before == NULL)
402 before = list;
403 if (list->next == NULL)
404 break;
405 list = list->next;
406 }
407 if (i == 32)
408 return NULL;
409 if (before)
410 {
411 list = before;
412 before = XOBNEW (&stridx_obstack, struct stridxlist);
413 *before = *list;
414 list->next = before;
415 list->offset = off;
416 list->idx = 0;
417 return &list->idx;
418 }
419 list->next = XOBNEW (&stridx_obstack, struct stridxlist);
420 list = list->next;
421 }
422
423 list->next = NULL;
424 list->offset = off;
425 list->idx = 0;
426 return &list->idx;
427 }
428
429 /* Create a new string index, or return 0 if reached limit. */
430
431 static int
new_stridx(tree exp)432 new_stridx (tree exp)
433 {
434 int idx;
435 if (max_stridx >= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS))
436 return 0;
437 if (TREE_CODE (exp) == SSA_NAME)
438 {
439 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp))
440 return 0;
441 idx = max_stridx++;
442 ssa_ver_to_stridx[SSA_NAME_VERSION (exp)] = idx;
443 return idx;
444 }
445 if (TREE_CODE (exp) == ADDR_EXPR)
446 {
447 int *pidx = addr_stridxptr (TREE_OPERAND (exp, 0));
448 if (pidx != NULL)
449 {
450 gcc_assert (*pidx == 0);
451 *pidx = max_stridx++;
452 return *pidx;
453 }
454 }
455 return 0;
456 }
457
458 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
459
460 static int
new_addr_stridx(tree exp)461 new_addr_stridx (tree exp)
462 {
463 int *pidx;
464 if (max_stridx >= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS))
465 return 0;
466 pidx = addr_stridxptr (exp);
467 if (pidx != NULL)
468 {
469 gcc_assert (*pidx == 0);
470 *pidx = max_stridx++;
471 return *pidx;
472 }
473 return 0;
474 }
475
476 /* Create a new strinfo. */
477
478 static strinfo *
new_strinfo(tree ptr,int idx,tree nonzero_chars,bool full_string_p)479 new_strinfo (tree ptr, int idx, tree nonzero_chars, bool full_string_p)
480 {
481 strinfo *si = strinfo_pool.allocate ();
482 si->nonzero_chars = nonzero_chars;
483 si->ptr = ptr;
484 si->stmt = NULL;
485 si->endptr = NULL_TREE;
486 si->refcount = 1;
487 si->idx = idx;
488 si->first = 0;
489 si->prev = 0;
490 si->next = 0;
491 si->writable = false;
492 si->dont_invalidate = false;
493 si->full_string_p = full_string_p;
494 return si;
495 }
496
497 /* Decrease strinfo refcount and free it if not referenced anymore. */
498
499 static inline void
free_strinfo(strinfo * si)500 free_strinfo (strinfo *si)
501 {
502 if (si && --si->refcount == 0)
503 strinfo_pool.remove (si);
504 }
505
506 /* Set strinfo in the vector entry IDX to SI. */
507
508 static inline void
set_strinfo(int idx,strinfo * si)509 set_strinfo (int idx, strinfo *si)
510 {
511 if (vec_safe_length (stridx_to_strinfo) && (*stridx_to_strinfo)[0])
512 unshare_strinfo_vec ();
513 if (vec_safe_length (stridx_to_strinfo) <= (unsigned int) idx)
514 vec_safe_grow_cleared (stridx_to_strinfo, idx + 1);
515 (*stridx_to_strinfo)[idx] = si;
516 }
517
518 /* Return the first strinfo in the related strinfo chain
519 if all strinfos in between belong to the chain, otherwise NULL. */
520
521 static strinfo *
verify_related_strinfos(strinfo * origsi)522 verify_related_strinfos (strinfo *origsi)
523 {
524 strinfo *si = origsi, *psi;
525
526 if (origsi->first == 0)
527 return NULL;
528 for (; si->prev; si = psi)
529 {
530 if (si->first != origsi->first)
531 return NULL;
532 psi = get_strinfo (si->prev);
533 if (psi == NULL)
534 return NULL;
535 if (psi->next != si->idx)
536 return NULL;
537 }
538 if (si->idx != si->first)
539 return NULL;
540 return si;
541 }
542
543 /* Set SI's endptr to ENDPTR and compute its length based on SI->ptr.
544 Use LOC for folding. */
545
546 static void
set_endptr_and_length(location_t loc,strinfo * si,tree endptr)547 set_endptr_and_length (location_t loc, strinfo *si, tree endptr)
548 {
549 si->endptr = endptr;
550 si->stmt = NULL;
551 tree start_as_size = fold_convert_loc (loc, size_type_node, si->ptr);
552 tree end_as_size = fold_convert_loc (loc, size_type_node, endptr);
553 si->nonzero_chars = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
554 end_as_size, start_as_size);
555 si->full_string_p = true;
556 }
557
558 /* Return string length, or NULL if it can't be computed. */
559
560 static tree
get_string_length(strinfo * si)561 get_string_length (strinfo *si)
562 {
563 if (si->nonzero_chars)
564 return si->full_string_p ? si->nonzero_chars : NULL;
565
566 if (si->stmt)
567 {
568 gimple *stmt = si->stmt, *lenstmt;
569 tree callee, lhs, fn, tem;
570 location_t loc;
571 gimple_stmt_iterator gsi;
572
573 gcc_assert (is_gimple_call (stmt));
574 callee = gimple_call_fndecl (stmt);
575 gcc_assert (callee && fndecl_built_in_p (callee, BUILT_IN_NORMAL));
576 lhs = gimple_call_lhs (stmt);
577 /* unshare_strinfo is intentionally not called here. The (delayed)
578 transformation of strcpy or strcat into stpcpy is done at the place
579 of the former strcpy/strcat call and so can affect all the strinfos
580 with the same stmt. If they were unshared before and transformation
581 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
582 just compute the right length. */
583 switch (DECL_FUNCTION_CODE (callee))
584 {
585 case BUILT_IN_STRCAT:
586 case BUILT_IN_STRCAT_CHK:
587 gsi = gsi_for_stmt (stmt);
588 fn = builtin_decl_implicit (BUILT_IN_STRLEN);
589 gcc_assert (lhs == NULL_TREE);
590 tem = unshare_expr (gimple_call_arg (stmt, 0));
591 lenstmt = gimple_build_call (fn, 1, tem);
592 lhs = make_ssa_name (TREE_TYPE (TREE_TYPE (fn)), lenstmt);
593 gimple_call_set_lhs (lenstmt, lhs);
594 gimple_set_vuse (lenstmt, gimple_vuse (stmt));
595 gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT);
596 tem = gimple_call_arg (stmt, 0);
597 if (!ptrofftype_p (TREE_TYPE (lhs)))
598 {
599 lhs = convert_to_ptrofftype (lhs);
600 lhs = force_gimple_operand_gsi (&gsi, lhs, true, NULL_TREE,
601 true, GSI_SAME_STMT);
602 }
603 lenstmt = gimple_build_assign
604 (make_ssa_name (TREE_TYPE (gimple_call_arg (stmt, 0))),
605 POINTER_PLUS_EXPR,tem, lhs);
606 gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT);
607 gimple_call_set_arg (stmt, 0, gimple_assign_lhs (lenstmt));
608 lhs = NULL_TREE;
609 /* FALLTHRU */
610 case BUILT_IN_STRCPY:
611 case BUILT_IN_STRCPY_CHK:
612 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY));
613 if (gimple_call_num_args (stmt) == 2)
614 fn = builtin_decl_implicit (BUILT_IN_STPCPY);
615 else
616 fn = builtin_decl_explicit (BUILT_IN_STPCPY_CHK);
617 gcc_assert (lhs == NULL_TREE);
618 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
619 {
620 fprintf (dump_file, "Optimizing: ");
621 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
622 }
623 gimple_call_set_fndecl (stmt, fn);
624 lhs = make_ssa_name (TREE_TYPE (TREE_TYPE (fn)), stmt);
625 gimple_call_set_lhs (stmt, lhs);
626 update_stmt (stmt);
627 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
628 {
629 fprintf (dump_file, "into: ");
630 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
631 }
632 /* FALLTHRU */
633 case BUILT_IN_STPCPY:
634 case BUILT_IN_STPCPY_CHK:
635 gcc_assert (lhs != NULL_TREE);
636 loc = gimple_location (stmt);
637 set_endptr_and_length (loc, si, lhs);
638 for (strinfo *chainsi = verify_related_strinfos (si);
639 chainsi != NULL;
640 chainsi = get_next_strinfo (chainsi))
641 if (chainsi->nonzero_chars == NULL)
642 set_endptr_and_length (loc, chainsi, lhs);
643 break;
644 case BUILT_IN_MALLOC:
645 break;
646 /* BUILT_IN_CALLOC always has si->nonzero_chars set. */
647 default:
648 gcc_unreachable ();
649 break;
650 }
651 }
652
653 return si->nonzero_chars;
654 }
655
656 /* Invalidate string length information for strings whose length
657 might change due to stores in stmt. */
658
659 static bool
maybe_invalidate(gimple * stmt)660 maybe_invalidate (gimple *stmt)
661 {
662 strinfo *si;
663 unsigned int i;
664 bool nonempty = false;
665
666 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
667 if (si != NULL)
668 {
669 if (!si->dont_invalidate)
670 {
671 ao_ref r;
672 /* Do not use si->nonzero_chars. */
673 ao_ref_init_from_ptr_and_size (&r, si->ptr, NULL_TREE);
674 if (stmt_may_clobber_ref_p_1 (stmt, &r))
675 {
676 set_strinfo (i, NULL);
677 free_strinfo (si);
678 continue;
679 }
680 }
681 si->dont_invalidate = false;
682 nonempty = true;
683 }
684 return nonempty;
685 }
686
687 /* Unshare strinfo record SI, if it has refcount > 1 or
688 if stridx_to_strinfo vector is shared with some other
689 bbs. */
690
691 static strinfo *
unshare_strinfo(strinfo * si)692 unshare_strinfo (strinfo *si)
693 {
694 strinfo *nsi;
695
696 if (si->refcount == 1 && !strinfo_shared ())
697 return si;
698
699 nsi = new_strinfo (si->ptr, si->idx, si->nonzero_chars, si->full_string_p);
700 nsi->stmt = si->stmt;
701 nsi->endptr = si->endptr;
702 nsi->first = si->first;
703 nsi->prev = si->prev;
704 nsi->next = si->next;
705 nsi->writable = si->writable;
706 set_strinfo (si->idx, nsi);
707 free_strinfo (si);
708 return nsi;
709 }
710
711 /* Attempt to create a new strinfo for BASESI + OFF, or find existing
712 strinfo if there is any. Return it's idx, or 0 if no strinfo has
713 been created. */
714
715 static int
get_stridx_plus_constant(strinfo * basesi,unsigned HOST_WIDE_INT off,tree ptr)716 get_stridx_plus_constant (strinfo *basesi, unsigned HOST_WIDE_INT off,
717 tree ptr)
718 {
719 if (TREE_CODE (ptr) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
720 return 0;
721
722 if (compare_nonzero_chars (basesi, off) < 0
723 || !tree_fits_uhwi_p (basesi->nonzero_chars))
724 return 0;
725
726 unsigned HOST_WIDE_INT nonzero_chars
727 = tree_to_uhwi (basesi->nonzero_chars) - off;
728 strinfo *si = basesi, *chainsi;
729 if (si->first || si->prev || si->next)
730 si = verify_related_strinfos (basesi);
731 if (si == NULL
732 || si->nonzero_chars == NULL_TREE
733 || TREE_CODE (si->nonzero_chars) != INTEGER_CST)
734 return 0;
735
736 if (TREE_CODE (ptr) == SSA_NAME
737 && ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
738 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
739
740 gcc_checking_assert (compare_tree_int (si->nonzero_chars, off) != -1);
741 for (chainsi = si; chainsi->next; chainsi = si)
742 {
743 si = get_next_strinfo (chainsi);
744 if (si == NULL
745 || si->nonzero_chars == NULL_TREE
746 || TREE_CODE (si->nonzero_chars) != INTEGER_CST)
747 break;
748 int r = compare_tree_int (si->nonzero_chars, nonzero_chars);
749 if (r != 1)
750 {
751 if (r == 0)
752 {
753 if (TREE_CODE (ptr) == SSA_NAME)
754 ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = si->idx;
755 else
756 {
757 int *pidx = addr_stridxptr (TREE_OPERAND (ptr, 0));
758 if (pidx != NULL && *pidx == 0)
759 *pidx = si->idx;
760 }
761 return si->idx;
762 }
763 break;
764 }
765 }
766
767 int idx = new_stridx (ptr);
768 if (idx == 0)
769 return 0;
770 si = new_strinfo (ptr, idx, build_int_cst (size_type_node, nonzero_chars),
771 basesi->full_string_p);
772 set_strinfo (idx, si);
773 if (strinfo *nextsi = get_strinfo (chainsi->next))
774 {
775 nextsi = unshare_strinfo (nextsi);
776 si->next = nextsi->idx;
777 nextsi->prev = idx;
778 }
779 chainsi = unshare_strinfo (chainsi);
780 if (chainsi->first == 0)
781 chainsi->first = chainsi->idx;
782 chainsi->next = idx;
783 if (chainsi->endptr == NULL_TREE && zero_length_string_p (si))
784 chainsi->endptr = ptr;
785 si->endptr = chainsi->endptr;
786 si->prev = chainsi->idx;
787 si->first = chainsi->first;
788 si->writable = chainsi->writable;
789 return si->idx;
790 }
791
792 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
793 to a zero-length string and if possible chain it to a related strinfo
794 chain whose part is or might be CHAINSI. */
795
796 static strinfo *
zero_length_string(tree ptr,strinfo * chainsi)797 zero_length_string (tree ptr, strinfo *chainsi)
798 {
799 strinfo *si;
800 int idx;
801 if (ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
802 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
803 gcc_checking_assert (TREE_CODE (ptr) == SSA_NAME
804 && ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] == 0);
805
806 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
807 return NULL;
808 if (chainsi != NULL)
809 {
810 si = verify_related_strinfos (chainsi);
811 if (si)
812 {
813 do
814 {
815 /* We shouldn't mix delayed and non-delayed lengths. */
816 gcc_assert (si->full_string_p);
817 if (si->endptr == NULL_TREE)
818 {
819 si = unshare_strinfo (si);
820 si->endptr = ptr;
821 }
822 chainsi = si;
823 si = get_next_strinfo (si);
824 }
825 while (si != NULL);
826 if (zero_length_string_p (chainsi))
827 {
828 if (chainsi->next)
829 {
830 chainsi = unshare_strinfo (chainsi);
831 chainsi->next = 0;
832 }
833 ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = chainsi->idx;
834 return chainsi;
835 }
836 }
837 else
838 {
839 /* We shouldn't mix delayed and non-delayed lengths. */
840 gcc_assert (chainsi->full_string_p);
841 if (chainsi->first || chainsi->prev || chainsi->next)
842 {
843 chainsi = unshare_strinfo (chainsi);
844 chainsi->first = 0;
845 chainsi->prev = 0;
846 chainsi->next = 0;
847 }
848 }
849 }
850 idx = new_stridx (ptr);
851 if (idx == 0)
852 return NULL;
853 si = new_strinfo (ptr, idx, build_int_cst (size_type_node, 0), true);
854 set_strinfo (idx, si);
855 si->endptr = ptr;
856 if (chainsi != NULL)
857 {
858 chainsi = unshare_strinfo (chainsi);
859 if (chainsi->first == 0)
860 chainsi->first = chainsi->idx;
861 chainsi->next = idx;
862 if (chainsi->endptr == NULL_TREE)
863 chainsi->endptr = ptr;
864 si->prev = chainsi->idx;
865 si->first = chainsi->first;
866 si->writable = chainsi->writable;
867 }
868 return si;
869 }
870
871 /* For strinfo ORIGSI whose length has been just updated, adjust other
872 related strinfos so that they match the new ORIGSI. This involves:
873
874 - adding ADJ to the nonzero_chars fields
875 - copying full_string_p from the new ORIGSI. */
876
877 static void
adjust_related_strinfos(location_t loc,strinfo * origsi,tree adj)878 adjust_related_strinfos (location_t loc, strinfo *origsi, tree adj)
879 {
880 strinfo *si = verify_related_strinfos (origsi);
881
882 if (si == NULL)
883 return;
884
885 while (1)
886 {
887 strinfo *nsi;
888
889 if (si != origsi)
890 {
891 tree tem;
892
893 si = unshare_strinfo (si);
894 /* We shouldn't see delayed lengths here; the caller must have
895 calculated the old length in order to calculate the
896 adjustment. */
897 gcc_assert (si->nonzero_chars);
898 tem = fold_convert_loc (loc, TREE_TYPE (si->nonzero_chars), adj);
899 si->nonzero_chars = fold_build2_loc (loc, PLUS_EXPR,
900 TREE_TYPE (si->nonzero_chars),
901 si->nonzero_chars, tem);
902 si->full_string_p = origsi->full_string_p;
903
904 si->endptr = NULL_TREE;
905 si->dont_invalidate = true;
906 }
907 nsi = get_next_strinfo (si);
908 if (nsi == NULL)
909 return;
910 si = nsi;
911 }
912 }
913
914 /* Find if there are other SSA_NAME pointers equal to PTR
915 for which we don't track their string lengths yet. If so, use
916 IDX for them. */
917
918 static void
find_equal_ptrs(tree ptr,int idx)919 find_equal_ptrs (tree ptr, int idx)
920 {
921 if (TREE_CODE (ptr) != SSA_NAME)
922 return;
923 while (1)
924 {
925 gimple *stmt = SSA_NAME_DEF_STMT (ptr);
926 if (!is_gimple_assign (stmt))
927 return;
928 ptr = gimple_assign_rhs1 (stmt);
929 switch (gimple_assign_rhs_code (stmt))
930 {
931 case SSA_NAME:
932 break;
933 CASE_CONVERT:
934 if (!POINTER_TYPE_P (TREE_TYPE (ptr)))
935 return;
936 if (TREE_CODE (ptr) == SSA_NAME)
937 break;
938 if (TREE_CODE (ptr) != ADDR_EXPR)
939 return;
940 /* FALLTHRU */
941 case ADDR_EXPR:
942 {
943 int *pidx = addr_stridxptr (TREE_OPERAND (ptr, 0));
944 if (pidx != NULL && *pidx == 0)
945 *pidx = idx;
946 return;
947 }
948 default:
949 return;
950 }
951
952 /* We might find an endptr created in this pass. Grow the
953 vector in that case. */
954 if (ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
955 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
956
957 if (ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] != 0)
958 return;
959 ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = idx;
960 }
961 }
962
963 /* Return true if STMT is a call to a builtin function with the right
964 arguments and attributes that should be considered for optimization
965 by this pass. */
966
967 static bool
valid_builtin_call(gimple * stmt)968 valid_builtin_call (gimple *stmt)
969 {
970 if (!gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
971 return false;
972
973 tree callee = gimple_call_fndecl (stmt);
974 tree decl = builtin_decl_explicit (DECL_FUNCTION_CODE (callee));
975 if (decl
976 && decl != callee
977 && !gimple_builtin_call_types_compatible_p (stmt, decl))
978 return false;
979
980 switch (DECL_FUNCTION_CODE (callee))
981 {
982 case BUILT_IN_MEMCMP:
983 case BUILT_IN_MEMCMP_EQ:
984 case BUILT_IN_STRCMP:
985 case BUILT_IN_STRNCMP:
986 case BUILT_IN_STRCHR:
987 case BUILT_IN_STRLEN:
988 case BUILT_IN_STRNLEN:
989 /* The above functions should be pure. Punt if they aren't. */
990 if (gimple_vdef (stmt) || gimple_vuse (stmt) == NULL_TREE)
991 return false;
992 break;
993
994 case BUILT_IN_CALLOC:
995 case BUILT_IN_MALLOC:
996 case BUILT_IN_MEMCPY:
997 case BUILT_IN_MEMCPY_CHK:
998 case BUILT_IN_MEMPCPY:
999 case BUILT_IN_MEMPCPY_CHK:
1000 case BUILT_IN_MEMSET:
1001 case BUILT_IN_STPCPY:
1002 case BUILT_IN_STPCPY_CHK:
1003 case BUILT_IN_STPNCPY:
1004 case BUILT_IN_STPNCPY_CHK:
1005 case BUILT_IN_STRCAT:
1006 case BUILT_IN_STRCAT_CHK:
1007 case BUILT_IN_STRCPY:
1008 case BUILT_IN_STRCPY_CHK:
1009 case BUILT_IN_STRNCAT:
1010 case BUILT_IN_STRNCAT_CHK:
1011 case BUILT_IN_STRNCPY:
1012 case BUILT_IN_STRNCPY_CHK:
1013 /* The above functions should be neither const nor pure. Punt if they
1014 aren't. */
1015 if (gimple_vdef (stmt) == NULL_TREE || gimple_vuse (stmt) == NULL_TREE)
1016 return false;
1017 break;
1018
1019 default:
1020 break;
1021 }
1022
1023 return true;
1024 }
1025
1026 /* If the last .MEM setter statement before STMT is
1027 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
1028 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
1029 just memcpy (x, y, strlen (y)). SI must be the zero length
1030 strinfo. */
1031
1032 static void
adjust_last_stmt(strinfo * si,gimple * stmt,bool is_strcat)1033 adjust_last_stmt (strinfo *si, gimple *stmt, bool is_strcat)
1034 {
1035 tree vuse, callee, len;
1036 struct laststmt_struct last = laststmt;
1037 strinfo *lastsi, *firstsi;
1038 unsigned len_arg_no = 2;
1039
1040 laststmt.stmt = NULL;
1041 laststmt.len = NULL_TREE;
1042 laststmt.stridx = 0;
1043
1044 if (last.stmt == NULL)
1045 return;
1046
1047 vuse = gimple_vuse (stmt);
1048 if (vuse == NULL_TREE
1049 || SSA_NAME_DEF_STMT (vuse) != last.stmt
1050 || !has_single_use (vuse))
1051 return;
1052
1053 gcc_assert (last.stridx > 0);
1054 lastsi = get_strinfo (last.stridx);
1055 if (lastsi == NULL)
1056 return;
1057
1058 if (lastsi != si)
1059 {
1060 if (lastsi->first == 0 || lastsi->first != si->first)
1061 return;
1062
1063 firstsi = verify_related_strinfos (si);
1064 if (firstsi == NULL)
1065 return;
1066 while (firstsi != lastsi)
1067 {
1068 firstsi = get_next_strinfo (firstsi);
1069 if (firstsi == NULL)
1070 return;
1071 }
1072 }
1073
1074 if (!is_strcat && !zero_length_string_p (si))
1075 return;
1076
1077 if (is_gimple_assign (last.stmt))
1078 {
1079 gimple_stmt_iterator gsi;
1080
1081 if (!integer_zerop (gimple_assign_rhs1 (last.stmt)))
1082 return;
1083 if (stmt_could_throw_p (cfun, last.stmt))
1084 return;
1085 gsi = gsi_for_stmt (last.stmt);
1086 unlink_stmt_vdef (last.stmt);
1087 release_defs (last.stmt);
1088 gsi_remove (&gsi, true);
1089 return;
1090 }
1091
1092 if (!valid_builtin_call (last.stmt))
1093 return;
1094
1095 callee = gimple_call_fndecl (last.stmt);
1096 switch (DECL_FUNCTION_CODE (callee))
1097 {
1098 case BUILT_IN_MEMCPY:
1099 case BUILT_IN_MEMCPY_CHK:
1100 break;
1101 default:
1102 return;
1103 }
1104
1105 len = gimple_call_arg (last.stmt, len_arg_no);
1106 if (tree_fits_uhwi_p (len))
1107 {
1108 if (!tree_fits_uhwi_p (last.len)
1109 || integer_zerop (len)
1110 || tree_to_uhwi (len) != tree_to_uhwi (last.len) + 1)
1111 return;
1112 /* Don't adjust the length if it is divisible by 4, it is more efficient
1113 to store the extra '\0' in that case. */
1114 if ((tree_to_uhwi (len) & 3) == 0)
1115 return;
1116
1117 /* Don't fold away an out of bounds access, as this defeats proper
1118 warnings. */
1119 tree dst = gimple_call_arg (last.stmt, 0);
1120 tree size = compute_objsize (dst, 0);
1121 if (size && tree_int_cst_lt (size, len))
1122 return;
1123 }
1124 else if (TREE_CODE (len) == SSA_NAME)
1125 {
1126 gimple *def_stmt = SSA_NAME_DEF_STMT (len);
1127 if (!is_gimple_assign (def_stmt)
1128 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
1129 || gimple_assign_rhs1 (def_stmt) != last.len
1130 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
1131 return;
1132 }
1133 else
1134 return;
1135
1136 gimple_call_set_arg (last.stmt, len_arg_no, last.len);
1137 update_stmt (last.stmt);
1138 }
1139
1140 /* For an LHS that is an SSA_NAME that is the result of a strlen()
1141 call, or when BOUND is non-null, of a strnlen() call, set LHS
1142 range info to [0, min (MAX, BOUND)] when the range includes more
1143 than one value and return LHS. Otherwise, when the range
1144 [MIN, MAX] is such that MIN == MAX, return the tree representation
1145 of (MIN). The latter allows callers to fold suitable strnlen() calls
1146 to constants. */
1147
1148 tree
set_strlen_range(tree lhs,wide_int max,tree bound)1149 set_strlen_range (tree lhs, wide_int max, tree bound /* = NULL_TREE */)
1150 {
1151 if (TREE_CODE (lhs) != SSA_NAME
1152 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
1153 return NULL_TREE;
1154
1155 wide_int min = wi::zero (max.get_precision ());
1156
1157 if (bound)
1158 {
1159 /* For strnlen, adjust MIN and MAX as necessary. If the bound
1160 is less than the size of the array set MAX to it. It it's
1161 greater than MAX and MAX is non-zero bump MAX down to account
1162 for the necessary terminating nul. Otherwise leave it alone. */
1163 if (TREE_CODE (bound) == INTEGER_CST)
1164 {
1165 wide_int wibnd = wi::to_wide (bound);
1166 int cmp = wi::cmpu (wibnd, max);
1167 if (cmp < 0)
1168 max = wibnd;
1169 else if (cmp && wi::ne_p (max, min))
1170 --max;
1171 }
1172 else if (TREE_CODE (bound) == SSA_NAME)
1173 {
1174 wide_int minbound, maxbound;
1175 value_range_kind rng = get_range_info (bound, &minbound, &maxbound);
1176 if (rng == VR_RANGE)
1177 {
1178 /* For a bound in a known range, adjust the range determined
1179 above as necessary. For a bound in some anti-range or
1180 in an unknown range, use the range determined by callers. */
1181 if (wi::ltu_p (minbound, min))
1182 min = minbound;
1183 if (wi::ltu_p (maxbound, max))
1184 max = maxbound;
1185 }
1186 }
1187 }
1188
1189 if (min == max)
1190 return wide_int_to_tree (size_type_node, min);
1191
1192 set_range_info (lhs, VR_RANGE, min, max);
1193 return lhs;
1194 }
1195
1196 /* For an LHS that is an SSA_NAME and for strlen() or strnlen() argument
1197 SRC, set LHS range info to [0, min (N, BOUND)] if SRC refers to
1198 a character array A[N] with unknown length bounded by N, and for
1199 strnlen(), by min (N, BOUND). */
1200
1201 static tree
maybe_set_strlen_range(tree lhs,tree src,tree bound)1202 maybe_set_strlen_range (tree lhs, tree src, tree bound)
1203 {
1204 if (TREE_CODE (lhs) != SSA_NAME
1205 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
1206 return NULL_TREE;
1207
1208 if (TREE_CODE (src) == SSA_NAME)
1209 {
1210 gimple *def = SSA_NAME_DEF_STMT (src);
1211 if (is_gimple_assign (def)
1212 && gimple_assign_rhs_code (def) == ADDR_EXPR)
1213 src = gimple_assign_rhs1 (def);
1214 }
1215
1216 /* The longest string is PTRDIFF_MAX - 1 bytes including the final
1217 NUL so that the difference between a pointer to just past it and
1218 one to its beginning is positive. */
1219 wide_int max = wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node)) - 2;
1220
1221 if (TREE_CODE (src) == ADDR_EXPR)
1222 {
1223 /* The last array member of a struct can be bigger than its size
1224 suggests if it's treated as a poor-man's flexible array member. */
1225 src = TREE_OPERAND (src, 0);
1226 if (TREE_CODE (src) != MEM_REF
1227 && !array_at_struct_end_p (src))
1228 {
1229 tree type = TREE_TYPE (src);
1230 tree size = TYPE_SIZE_UNIT (type);
1231 if (size
1232 && TREE_CODE (size) == INTEGER_CST
1233 && !integer_zerop (size))
1234 {
1235 /* Even though such uses of strlen would be undefined,
1236 avoid relying on arrays of arrays in case some genius
1237 decides to call strlen on an unterminated array element
1238 that's followed by a terminated one. Likewise, avoid
1239 assuming that a struct array member is necessarily
1240 nul-terminated (the nul may be in the member that
1241 follows). In those cases, assume that the length
1242 of the string stored in such an array is bounded
1243 by the size of the enclosing object if one can be
1244 determined. */
1245 tree base = get_base_address (src);
1246 if (VAR_P (base))
1247 {
1248 if (tree size = DECL_SIZE_UNIT (base))
1249 if (size
1250 && TREE_CODE (size) == INTEGER_CST
1251 && TREE_CODE (TREE_TYPE (base)) != POINTER_TYPE)
1252 max = wi::to_wide (size);
1253 }
1254 }
1255
1256 /* For strlen() the upper bound above is equal to
1257 the longest string that can be stored in the array
1258 (i.e., it accounts for the terminating nul. For
1259 strnlen() bump up the maximum by one since the array
1260 need not be nul-terminated. */
1261 if (!bound && max != 0)
1262 --max;
1263 }
1264 }
1265
1266 return set_strlen_range (lhs, max, bound);
1267 }
1268
1269 /* Handle a strlen call. If strlen of the argument is known, replace
1270 the strlen call with the known value, otherwise remember that strlen
1271 of the argument is stored in the lhs SSA_NAME. */
1272
1273 static void
handle_builtin_strlen(gimple_stmt_iterator * gsi)1274 handle_builtin_strlen (gimple_stmt_iterator *gsi)
1275 {
1276 gimple *stmt = gsi_stmt (*gsi);
1277 tree lhs = gimple_call_lhs (stmt);
1278
1279 if (lhs == NULL_TREE)
1280 return;
1281
1282 location_t loc = gimple_location (stmt);
1283 tree callee = gimple_call_fndecl (stmt);
1284 tree src = gimple_call_arg (stmt, 0);
1285 tree bound = (DECL_FUNCTION_CODE (callee) == BUILT_IN_STRNLEN
1286 ? gimple_call_arg (stmt, 1) : NULL_TREE);
1287 int idx = get_stridx (src);
1288 if (idx || (bound && integer_zerop (bound)))
1289 {
1290 strinfo *si = NULL;
1291 tree rhs;
1292
1293 if (idx < 0)
1294 rhs = build_int_cst (TREE_TYPE (lhs), ~idx);
1295 else if (idx == 0)
1296 rhs = bound;
1297 else
1298 {
1299 rhs = NULL_TREE;
1300 si = get_strinfo (idx);
1301 if (si != NULL)
1302 {
1303 rhs = get_string_length (si);
1304 /* For strnlen, if bound is constant, even if si is not known
1305 to be zero terminated, if we know at least bound bytes are
1306 not zero, the return value will be bound. */
1307 if (rhs == NULL_TREE
1308 && bound != NULL_TREE
1309 && TREE_CODE (bound) == INTEGER_CST
1310 && si->nonzero_chars != NULL_TREE
1311 && TREE_CODE (si->nonzero_chars) == INTEGER_CST
1312 && tree_int_cst_le (bound, si->nonzero_chars))
1313 rhs = bound;
1314 }
1315 }
1316 if (rhs != NULL_TREE)
1317 {
1318 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1319 {
1320 fprintf (dump_file, "Optimizing: ");
1321 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1322 }
1323 rhs = unshare_expr (rhs);
1324 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
1325 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
1326
1327 if (bound)
1328 rhs = fold_build2_loc (loc, MIN_EXPR, TREE_TYPE (rhs), rhs, bound);
1329
1330 if (!update_call_from_tree (gsi, rhs))
1331 gimplify_and_update_call_from_tree (gsi, rhs);
1332 stmt = gsi_stmt (*gsi);
1333 update_stmt (stmt);
1334 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1335 {
1336 fprintf (dump_file, "into: ");
1337 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1338 }
1339
1340 if (si != NULL
1341 /* Don't update anything for strnlen. */
1342 && bound == NULL_TREE
1343 && TREE_CODE (si->nonzero_chars) != SSA_NAME
1344 && TREE_CODE (si->nonzero_chars) != INTEGER_CST
1345 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1346 {
1347 si = unshare_strinfo (si);
1348 si->nonzero_chars = lhs;
1349 gcc_assert (si->full_string_p);
1350 }
1351
1352 if (strlen_to_stridx
1353 && (bound == NULL_TREE
1354 /* For strnlen record this only if the call is proven
1355 to return the same value as strlen would. */
1356 || (TREE_CODE (bound) == INTEGER_CST
1357 && TREE_CODE (rhs) == INTEGER_CST
1358 && tree_int_cst_lt (rhs, bound))))
1359 strlen_to_stridx->put (lhs, stridx_strlenloc (idx, loc));
1360
1361 return;
1362 }
1363 }
1364 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1365 return;
1366
1367 if (idx == 0)
1368 idx = new_stridx (src);
1369 else
1370 {
1371 strinfo *si = get_strinfo (idx);
1372 if (si != NULL)
1373 {
1374 if (!si->full_string_p && !si->stmt)
1375 {
1376 /* Until now we only had a lower bound on the string length.
1377 Install LHS as the actual length. */
1378 si = unshare_strinfo (si);
1379 tree old = si->nonzero_chars;
1380 si->nonzero_chars = lhs;
1381 si->full_string_p = true;
1382 if (TREE_CODE (old) == INTEGER_CST)
1383 {
1384 old = fold_convert_loc (loc, TREE_TYPE (lhs), old);
1385 tree adj = fold_build2_loc (loc, MINUS_EXPR,
1386 TREE_TYPE (lhs), lhs, old);
1387 adjust_related_strinfos (loc, si, adj);
1388 }
1389 else
1390 {
1391 si->first = 0;
1392 si->prev = 0;
1393 si->next = 0;
1394 }
1395 }
1396 return;
1397 }
1398 }
1399 if (idx)
1400 {
1401 if (!bound)
1402 {
1403 /* Only store the new length information for calls to strlen(),
1404 not for those to strnlen(). */
1405 strinfo *si = new_strinfo (src, idx, lhs, true);
1406 set_strinfo (idx, si);
1407 find_equal_ptrs (src, idx);
1408 }
1409
1410 /* For SRC that is an array of N elements, set LHS's range
1411 to [0, min (N, BOUND)]. A constant return value means
1412 the range would have consisted of a single value. In
1413 that case, fold the result into the returned constant. */
1414 if (tree ret = maybe_set_strlen_range (lhs, src, bound))
1415 if (TREE_CODE (ret) == INTEGER_CST)
1416 {
1417 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1418 {
1419 fprintf (dump_file, "Optimizing: ");
1420 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1421 }
1422 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (ret)))
1423 ret = fold_convert_loc (loc, TREE_TYPE (lhs), ret);
1424 if (!update_call_from_tree (gsi, ret))
1425 gimplify_and_update_call_from_tree (gsi, ret);
1426 stmt = gsi_stmt (*gsi);
1427 update_stmt (stmt);
1428 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1429 {
1430 fprintf (dump_file, "into: ");
1431 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1432 }
1433 }
1434
1435 if (strlen_to_stridx && !bound)
1436 strlen_to_stridx->put (lhs, stridx_strlenloc (idx, loc));
1437 }
1438 }
1439
1440 /* Handle a strchr call. If strlen of the first argument is known, replace
1441 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
1442 that lhs of the call is endptr and strlen of the argument is endptr - x. */
1443
1444 static void
handle_builtin_strchr(gimple_stmt_iterator * gsi)1445 handle_builtin_strchr (gimple_stmt_iterator *gsi)
1446 {
1447 int idx;
1448 tree src;
1449 gimple *stmt = gsi_stmt (*gsi);
1450 tree lhs = gimple_call_lhs (stmt);
1451
1452 if (lhs == NULL_TREE)
1453 return;
1454
1455 if (!integer_zerop (gimple_call_arg (stmt, 1)))
1456 return;
1457
1458 src = gimple_call_arg (stmt, 0);
1459 idx = get_stridx (src);
1460 if (idx)
1461 {
1462 strinfo *si = NULL;
1463 tree rhs;
1464
1465 if (idx < 0)
1466 rhs = build_int_cst (size_type_node, ~idx);
1467 else
1468 {
1469 rhs = NULL_TREE;
1470 si = get_strinfo (idx);
1471 if (si != NULL)
1472 rhs = get_string_length (si);
1473 }
1474 if (rhs != NULL_TREE)
1475 {
1476 location_t loc = gimple_location (stmt);
1477
1478 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1479 {
1480 fprintf (dump_file, "Optimizing: ");
1481 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1482 }
1483 if (si != NULL && si->endptr != NULL_TREE)
1484 {
1485 rhs = unshare_expr (si->endptr);
1486 if (!useless_type_conversion_p (TREE_TYPE (lhs),
1487 TREE_TYPE (rhs)))
1488 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
1489 }
1490 else
1491 {
1492 rhs = fold_convert_loc (loc, sizetype, unshare_expr (rhs));
1493 rhs = fold_build2_loc (loc, POINTER_PLUS_EXPR,
1494 TREE_TYPE (src), src, rhs);
1495 if (!useless_type_conversion_p (TREE_TYPE (lhs),
1496 TREE_TYPE (rhs)))
1497 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
1498 }
1499 if (!update_call_from_tree (gsi, rhs))
1500 gimplify_and_update_call_from_tree (gsi, rhs);
1501 stmt = gsi_stmt (*gsi);
1502 update_stmt (stmt);
1503 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1504 {
1505 fprintf (dump_file, "into: ");
1506 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1507 }
1508 if (si != NULL
1509 && si->endptr == NULL_TREE
1510 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1511 {
1512 si = unshare_strinfo (si);
1513 si->endptr = lhs;
1514 }
1515 zero_length_string (lhs, si);
1516 return;
1517 }
1518 }
1519 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1520 return;
1521 if (TREE_CODE (src) != SSA_NAME || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src))
1522 {
1523 if (idx == 0)
1524 idx = new_stridx (src);
1525 else if (get_strinfo (idx) != NULL)
1526 {
1527 zero_length_string (lhs, NULL);
1528 return;
1529 }
1530 if (idx)
1531 {
1532 location_t loc = gimple_location (stmt);
1533 tree lhsu = fold_convert_loc (loc, size_type_node, lhs);
1534 tree srcu = fold_convert_loc (loc, size_type_node, src);
1535 tree length = fold_build2_loc (loc, MINUS_EXPR,
1536 size_type_node, lhsu, srcu);
1537 strinfo *si = new_strinfo (src, idx, length, true);
1538 si->endptr = lhs;
1539 set_strinfo (idx, si);
1540 find_equal_ptrs (src, idx);
1541 zero_length_string (lhs, si);
1542 }
1543 }
1544 else
1545 zero_length_string (lhs, NULL);
1546 }
1547
1548 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1549 If strlen of the second argument is known, strlen of the first argument
1550 is the same after this call. Furthermore, attempt to convert it to
1551 memcpy. */
1552
1553 static void
handle_builtin_strcpy(enum built_in_function bcode,gimple_stmt_iterator * gsi)1554 handle_builtin_strcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1555 {
1556 int idx, didx;
1557 tree src, dst, srclen, len, lhs, type, fn, oldlen;
1558 bool success;
1559 gimple *stmt = gsi_stmt (*gsi);
1560 strinfo *si, *dsi, *olddsi, *zsi;
1561 location_t loc;
1562
1563 src = gimple_call_arg (stmt, 1);
1564 dst = gimple_call_arg (stmt, 0);
1565 lhs = gimple_call_lhs (stmt);
1566 idx = get_stridx (src);
1567 si = NULL;
1568 if (idx > 0)
1569 si = get_strinfo (idx);
1570
1571 didx = get_stridx (dst);
1572 olddsi = NULL;
1573 oldlen = NULL_TREE;
1574 if (didx > 0)
1575 olddsi = get_strinfo (didx);
1576 else if (didx < 0)
1577 return;
1578
1579 if (olddsi != NULL)
1580 adjust_last_stmt (olddsi, stmt, false);
1581
1582 srclen = NULL_TREE;
1583 if (si != NULL)
1584 srclen = get_string_length (si);
1585 else if (idx < 0)
1586 srclen = build_int_cst (size_type_node, ~idx);
1587
1588 loc = gimple_location (stmt);
1589 if (srclen == NULL_TREE)
1590 switch (bcode)
1591 {
1592 case BUILT_IN_STRCPY:
1593 case BUILT_IN_STRCPY_CHK:
1594 if (lhs != NULL_TREE || !builtin_decl_implicit_p (BUILT_IN_STPCPY))
1595 return;
1596 break;
1597 case BUILT_IN_STPCPY:
1598 case BUILT_IN_STPCPY_CHK:
1599 if (lhs == NULL_TREE)
1600 return;
1601 else
1602 {
1603 tree lhsuint = fold_convert_loc (loc, size_type_node, lhs);
1604 srclen = fold_convert_loc (loc, size_type_node, dst);
1605 srclen = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
1606 lhsuint, srclen);
1607 }
1608 break;
1609 default:
1610 gcc_unreachable ();
1611 }
1612
1613 if (didx == 0)
1614 {
1615 didx = new_stridx (dst);
1616 if (didx == 0)
1617 return;
1618 }
1619 if (olddsi != NULL)
1620 {
1621 oldlen = olddsi->nonzero_chars;
1622 dsi = unshare_strinfo (olddsi);
1623 dsi->nonzero_chars = srclen;
1624 dsi->full_string_p = (srclen != NULL_TREE);
1625 /* Break the chain, so adjust_related_strinfo on later pointers in
1626 the chain won't adjust this one anymore. */
1627 dsi->next = 0;
1628 dsi->stmt = NULL;
1629 dsi->endptr = NULL_TREE;
1630 }
1631 else
1632 {
1633 dsi = new_strinfo (dst, didx, srclen, srclen != NULL_TREE);
1634 set_strinfo (didx, dsi);
1635 find_equal_ptrs (dst, didx);
1636 }
1637 dsi->writable = true;
1638 dsi->dont_invalidate = true;
1639
1640 if (dsi->nonzero_chars == NULL_TREE)
1641 {
1642 strinfo *chainsi;
1643
1644 /* If string length of src is unknown, use delayed length
1645 computation. If string lenth of dst will be needed, it
1646 can be computed by transforming this strcpy call into
1647 stpcpy and subtracting dst from the return value. */
1648
1649 /* Look for earlier strings whose length could be determined if
1650 this strcpy is turned into an stpcpy. */
1651
1652 if (dsi->prev != 0 && (chainsi = verify_related_strinfos (dsi)) != NULL)
1653 {
1654 for (; chainsi && chainsi != dsi; chainsi = get_strinfo (chainsi->next))
1655 {
1656 /* When setting a stmt for delayed length computation
1657 prevent all strinfos through dsi from being
1658 invalidated. */
1659 chainsi = unshare_strinfo (chainsi);
1660 chainsi->stmt = stmt;
1661 chainsi->nonzero_chars = NULL_TREE;
1662 chainsi->full_string_p = false;
1663 chainsi->endptr = NULL_TREE;
1664 chainsi->dont_invalidate = true;
1665 }
1666 }
1667 dsi->stmt = stmt;
1668
1669 /* Try to detect overlap before returning. This catches cases
1670 like strcpy (d, d + n) where n is non-constant whose range
1671 is such that (n <= strlen (d) holds).
1672
1673 OLDDSI->NONZERO_chars may have been reset by this point with
1674 oldlen holding it original value. */
1675 if (olddsi && oldlen)
1676 {
1677 /* Add 1 for the terminating NUL. */
1678 tree type = TREE_TYPE (oldlen);
1679 oldlen = fold_build2 (PLUS_EXPR, type, oldlen,
1680 build_int_cst (type, 1));
1681 check_bounds_or_overlap (stmt, olddsi->ptr, src, oldlen, NULL_TREE);
1682 }
1683
1684 return;
1685 }
1686
1687 if (olddsi != NULL)
1688 {
1689 tree adj = NULL_TREE;
1690 if (oldlen == NULL_TREE)
1691 ;
1692 else if (integer_zerop (oldlen))
1693 adj = srclen;
1694 else if (TREE_CODE (oldlen) == INTEGER_CST
1695 || TREE_CODE (srclen) == INTEGER_CST)
1696 adj = fold_build2_loc (loc, MINUS_EXPR,
1697 TREE_TYPE (srclen), srclen,
1698 fold_convert_loc (loc, TREE_TYPE (srclen),
1699 oldlen));
1700 if (adj != NULL_TREE)
1701 adjust_related_strinfos (loc, dsi, adj);
1702 else
1703 dsi->prev = 0;
1704 }
1705 /* strcpy src may not overlap dst, so src doesn't need to be
1706 invalidated either. */
1707 if (si != NULL)
1708 si->dont_invalidate = true;
1709
1710 fn = NULL_TREE;
1711 zsi = NULL;
1712 switch (bcode)
1713 {
1714 case BUILT_IN_STRCPY:
1715 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1716 if (lhs)
1717 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
1718 break;
1719 case BUILT_IN_STRCPY_CHK:
1720 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK);
1721 if (lhs)
1722 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
1723 break;
1724 case BUILT_IN_STPCPY:
1725 /* This would need adjustment of the lhs (subtract one),
1726 or detection that the trailing '\0' doesn't need to be
1727 written, if it will be immediately overwritten.
1728 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1729 if (lhs)
1730 {
1731 dsi->endptr = lhs;
1732 zsi = zero_length_string (lhs, dsi);
1733 }
1734 break;
1735 case BUILT_IN_STPCPY_CHK:
1736 /* This would need adjustment of the lhs (subtract one),
1737 or detection that the trailing '\0' doesn't need to be
1738 written, if it will be immediately overwritten.
1739 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1740 if (lhs)
1741 {
1742 dsi->endptr = lhs;
1743 zsi = zero_length_string (lhs, dsi);
1744 }
1745 break;
1746 default:
1747 gcc_unreachable ();
1748 }
1749 if (zsi != NULL)
1750 zsi->dont_invalidate = true;
1751
1752 if (fn)
1753 {
1754 tree args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1755 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1756 }
1757 else
1758 type = size_type_node;
1759
1760 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1761 len = fold_build2_loc (loc, PLUS_EXPR, type, len, build_int_cst (type, 1));
1762
1763 /* Set the no-warning bit on the transformed statement? */
1764 bool set_no_warning = false;
1765
1766 if (const strinfo *chksi = olddsi ? olddsi : dsi)
1767 if (si
1768 && check_bounds_or_overlap (stmt, chksi->ptr, si->ptr, NULL_TREE, len))
1769 {
1770 gimple_set_no_warning (stmt, true);
1771 set_no_warning = true;
1772 }
1773
1774 if (fn == NULL_TREE)
1775 return;
1776
1777 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1778 GSI_SAME_STMT);
1779 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1780 {
1781 fprintf (dump_file, "Optimizing: ");
1782 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1783 }
1784 if (gimple_call_num_args (stmt) == 2)
1785 success = update_gimple_call (gsi, fn, 3, dst, src, len);
1786 else
1787 success = update_gimple_call (gsi, fn, 4, dst, src, len,
1788 gimple_call_arg (stmt, 2));
1789 if (success)
1790 {
1791 stmt = gsi_stmt (*gsi);
1792 update_stmt (stmt);
1793 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1794 {
1795 fprintf (dump_file, "into: ");
1796 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1797 }
1798 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1799 laststmt.stmt = stmt;
1800 laststmt.len = srclen;
1801 laststmt.stridx = dsi->idx;
1802 }
1803 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1804 fprintf (dump_file, "not possible.\n");
1805
1806 if (set_no_warning)
1807 gimple_set_no_warning (stmt, true);
1808 }
1809
1810 /* Check the size argument to the built-in forms of stpncpy and strncpy
1811 for out-of-bounds offsets or overlapping access, and to see if the
1812 size argument is derived from a call to strlen() on the source argument,
1813 and if so, issue an appropriate warning. */
1814
1815 static void
handle_builtin_strncat(built_in_function bcode,gimple_stmt_iterator * gsi)1816 handle_builtin_strncat (built_in_function bcode, gimple_stmt_iterator *gsi)
1817 {
1818 /* Same as stxncpy(). */
1819 handle_builtin_stxncpy (bcode, gsi);
1820 }
1821
1822 /* Return true if LEN depends on a call to strlen(SRC) in an interesting
1823 way. LEN can either be an integer expression, or a pointer (to char).
1824 When it is the latter (such as in recursive calls to self) is is
1825 assumed to be the argument in some call to strlen() whose relationship
1826 to SRC is being ascertained. */
1827
1828 bool
is_strlen_related_p(tree src,tree len)1829 is_strlen_related_p (tree src, tree len)
1830 {
1831 if (TREE_CODE (TREE_TYPE (len)) == POINTER_TYPE
1832 && operand_equal_p (src, len, 0))
1833 return true;
1834
1835 if (TREE_CODE (len) != SSA_NAME)
1836 return false;
1837
1838 gimple *def_stmt = SSA_NAME_DEF_STMT (len);
1839 if (!def_stmt)
1840 return false;
1841
1842 if (is_gimple_call (def_stmt))
1843 {
1844 tree func = gimple_call_fndecl (def_stmt);
1845 if (!valid_builtin_call (def_stmt)
1846 || DECL_FUNCTION_CODE (func) != BUILT_IN_STRLEN)
1847 return false;
1848
1849 tree arg = gimple_call_arg (def_stmt, 0);
1850 return is_strlen_related_p (src, arg);
1851 }
1852
1853 if (!is_gimple_assign (def_stmt))
1854 return false;
1855
1856 tree_code code = gimple_assign_rhs_code (def_stmt);
1857 tree rhs1 = gimple_assign_rhs1 (def_stmt);
1858 tree rhstype = TREE_TYPE (rhs1);
1859
1860 if ((TREE_CODE (rhstype) == POINTER_TYPE && code == POINTER_PLUS_EXPR)
1861 || (INTEGRAL_TYPE_P (rhstype)
1862 && (code == BIT_AND_EXPR
1863 || code == NOP_EXPR)))
1864 {
1865 /* Pointer plus (an integer), and truncation are considered among
1866 the (potentially) related expressions to strlen. */
1867 return is_strlen_related_p (src, rhs1);
1868 }
1869
1870 if (tree rhs2 = gimple_assign_rhs2 (def_stmt))
1871 {
1872 /* Integer subtraction is considered strlen-related when both
1873 arguments are integers and second one is strlen-related. */
1874 rhstype = TREE_TYPE (rhs2);
1875 if (INTEGRAL_TYPE_P (rhstype) && code == MINUS_EXPR)
1876 return is_strlen_related_p (src, rhs2);
1877 }
1878
1879 return false;
1880 }
1881
1882 /* Called by handle_builtin_stxncpy and by gimple_fold_builtin_strncpy
1883 in gimple-fold.c.
1884 Check to see if the specified bound is a) equal to the size of
1885 the destination DST and if so, b) if it's immediately followed by
1886 DST[CNT - 1] = '\0'. If a) holds and b) does not, warn. Otherwise,
1887 do nothing. Return true if diagnostic has been issued.
1888
1889 The purpose is to diagnose calls to strncpy and stpncpy that do
1890 not nul-terminate the copy while allowing for the idiom where
1891 such a call is immediately followed by setting the last element
1892 to nul, as in:
1893 char a[32];
1894 strncpy (a, s, sizeof a);
1895 a[sizeof a - 1] = '\0';
1896 */
1897
1898 bool
maybe_diag_stxncpy_trunc(gimple_stmt_iterator gsi,tree src,tree cnt)1899 maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi, tree src, tree cnt)
1900 {
1901 gimple *stmt = gsi_stmt (gsi);
1902 if (gimple_no_warning_p (stmt))
1903 return false;
1904
1905 wide_int cntrange[2];
1906
1907 if (TREE_CODE (cnt) == INTEGER_CST)
1908 cntrange[0] = cntrange[1] = wi::to_wide (cnt);
1909 else if (TREE_CODE (cnt) == SSA_NAME)
1910 {
1911 enum value_range_kind rng = get_range_info (cnt, cntrange, cntrange + 1);
1912 if (rng == VR_RANGE)
1913 ;
1914 else if (rng == VR_ANTI_RANGE)
1915 {
1916 wide_int maxobjsize = wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node));
1917
1918 if (wi::ltu_p (cntrange[1], maxobjsize))
1919 {
1920 cntrange[0] = cntrange[1] + 1;
1921 cntrange[1] = maxobjsize;
1922 }
1923 else
1924 {
1925 cntrange[1] = cntrange[0] - 1;
1926 cntrange[0] = wi::zero (TYPE_PRECISION (TREE_TYPE (cnt)));
1927 }
1928 }
1929 else
1930 return false;
1931 }
1932 else
1933 return false;
1934
1935 /* Negative value is the constant string length. If it's less than
1936 the lower bound there is no truncation. Avoid calling get_stridx()
1937 when ssa_ver_to_stridx is empty. That implies the caller isn't
1938 running under the control of this pass and ssa_ver_to_stridx hasn't
1939 been created yet. */
1940 int sidx = ssa_ver_to_stridx.length () ? get_stridx (src) : 0;
1941 if (sidx < 0 && wi::gtu_p (cntrange[0], ~sidx))
1942 return false;
1943
1944 tree dst = gimple_call_arg (stmt, 0);
1945 tree dstdecl = dst;
1946 if (TREE_CODE (dstdecl) == ADDR_EXPR)
1947 dstdecl = TREE_OPERAND (dstdecl, 0);
1948
1949 tree ref = NULL_TREE;
1950
1951 if (!sidx)
1952 {
1953 /* If the source is a non-string return early to avoid warning
1954 for possible truncation (if the truncation is certain SIDX
1955 is non-zero). */
1956 tree srcdecl = gimple_call_arg (stmt, 1);
1957 if (TREE_CODE (srcdecl) == ADDR_EXPR)
1958 srcdecl = TREE_OPERAND (srcdecl, 0);
1959 if (get_attr_nonstring_decl (srcdecl, &ref))
1960 return false;
1961 }
1962
1963 /* Likewise, if the destination refers to a an array/pointer declared
1964 nonstring return early. */
1965 if (get_attr_nonstring_decl (dstdecl, &ref))
1966 return false;
1967
1968 /* Look for dst[i] = '\0'; after the stxncpy() call and if found
1969 avoid the truncation warning. */
1970 gsi_next_nondebug (&gsi);
1971 gimple *next_stmt = gsi_stmt (gsi);
1972 if (!next_stmt)
1973 {
1974 /* When there is no statement in the same basic block check
1975 the immediate successor block. */
1976 if (basic_block bb = gimple_bb (stmt))
1977 {
1978 if (single_succ_p (bb))
1979 {
1980 /* For simplicity, ignore blocks with multiple outgoing
1981 edges for now and only consider successor blocks along
1982 normal edges. */
1983 edge e = EDGE_SUCC (bb, 0);
1984 if (!(e->flags & EDGE_ABNORMAL))
1985 {
1986 gsi = gsi_start_bb (e->dest);
1987 next_stmt = gsi_stmt (gsi);
1988 if (next_stmt && is_gimple_debug (next_stmt))
1989 {
1990 gsi_next_nondebug (&gsi);
1991 next_stmt = gsi_stmt (gsi);
1992 }
1993 }
1994 }
1995 }
1996 }
1997
1998 if (next_stmt && is_gimple_assign (next_stmt))
1999 {
2000 tree lhs = gimple_assign_lhs (next_stmt);
2001 tree_code code = TREE_CODE (lhs);
2002 if (code == ARRAY_REF || code == MEM_REF)
2003 lhs = TREE_OPERAND (lhs, 0);
2004
2005 tree func = gimple_call_fndecl (stmt);
2006 if (DECL_FUNCTION_CODE (func) == BUILT_IN_STPNCPY)
2007 {
2008 tree ret = gimple_call_lhs (stmt);
2009 if (ret && operand_equal_p (ret, lhs, 0))
2010 return false;
2011 }
2012
2013 /* Determine the base address and offset of the reference,
2014 ignoring the innermost array index. */
2015 if (TREE_CODE (ref) == ARRAY_REF)
2016 ref = TREE_OPERAND (ref, 0);
2017
2018 poly_int64 dstoff;
2019 tree dstbase = get_addr_base_and_unit_offset (ref, &dstoff);
2020
2021 poly_int64 lhsoff;
2022 tree lhsbase = get_addr_base_and_unit_offset (lhs, &lhsoff);
2023 if (lhsbase
2024 && dstbase
2025 && known_eq (dstoff, lhsoff)
2026 && operand_equal_p (dstbase, lhsbase, 0))
2027 return false;
2028 }
2029
2030 int prec = TYPE_PRECISION (TREE_TYPE (cnt));
2031 wide_int lenrange[2];
2032 if (strinfo *sisrc = sidx > 0 ? get_strinfo (sidx) : NULL)
2033 {
2034 lenrange[0] = (sisrc->nonzero_chars
2035 && TREE_CODE (sisrc->nonzero_chars) == INTEGER_CST
2036 ? wi::to_wide (sisrc->nonzero_chars)
2037 : wi::zero (prec));
2038 lenrange[1] = lenrange[0];
2039 }
2040 else if (sidx < 0)
2041 lenrange[0] = lenrange[1] = wi::shwi (~sidx, prec);
2042 else
2043 {
2044 c_strlen_data lendata = { };
2045 get_range_strlen (src, &lendata, /* eltsize = */1);
2046 if (TREE_CODE (lendata.minlen) == INTEGER_CST
2047 && TREE_CODE (lendata.maxbound) == INTEGER_CST)
2048 {
2049 /* When LENDATA.MAXLEN is unknown, reset LENDATA.MINLEN
2050 which stores the length of the shortest known string. */
2051 if (integer_all_onesp (lendata.maxlen))
2052 lenrange[0] = wi::shwi (0, prec);
2053 else
2054 lenrange[0] = wi::to_wide (lendata.minlen, prec);
2055 lenrange[1] = wi::to_wide (lendata.maxbound, prec);
2056 }
2057 else
2058 {
2059 lenrange[0] = wi::shwi (0, prec);
2060 lenrange[1] = wi::shwi (-1, prec);
2061 }
2062 }
2063
2064 location_t callloc = gimple_nonartificial_location (stmt);
2065 callloc = expansion_point_location_if_in_system_header (callloc);
2066
2067 tree func = gimple_call_fndecl (stmt);
2068
2069 if (lenrange[0] != 0 || !wi::neg_p (lenrange[1]))
2070 {
2071 /* If the longest source string is shorter than the lower bound
2072 of the specified count the copy is definitely nul-terminated. */
2073 if (wi::ltu_p (lenrange[1], cntrange[0]))
2074 return false;
2075
2076 if (wi::neg_p (lenrange[1]))
2077 {
2078 /* The length of one of the strings is unknown but at least
2079 one has non-zero length and that length is stored in
2080 LENRANGE[1]. Swap the bounds to force a "may be truncated"
2081 warning below. */
2082 lenrange[1] = lenrange[0];
2083 lenrange[0] = wi::shwi (0, prec);
2084 }
2085
2086 /* Set to true for strncat whose bound is derived from the length
2087 of the destination (the expected usage pattern). */
2088 bool cat_dstlen_bounded = false;
2089 if (DECL_FUNCTION_CODE (func) == BUILT_IN_STRNCAT)
2090 cat_dstlen_bounded = is_strlen_related_p (dst, cnt);
2091
2092 if (lenrange[0] == cntrange[1] && cntrange[0] == cntrange[1])
2093 return warning_n (callloc, OPT_Wstringop_truncation,
2094 cntrange[0].to_uhwi (),
2095 "%G%qD output truncated before terminating "
2096 "nul copying %E byte from a string of the "
2097 "same length",
2098 "%G%qD output truncated before terminating nul "
2099 "copying %E bytes from a string of the same "
2100 "length",
2101 stmt, func, cnt);
2102 else if (!cat_dstlen_bounded)
2103 {
2104 if (wi::geu_p (lenrange[0], cntrange[1]))
2105 {
2106 /* The shortest string is longer than the upper bound of
2107 the count so the truncation is certain. */
2108 if (cntrange[0] == cntrange[1])
2109 return warning_n (callloc, OPT_Wstringop_truncation,
2110 cntrange[0].to_uhwi (),
2111 "%G%qD output truncated copying %E byte "
2112 "from a string of length %wu",
2113 "%G%qD output truncated copying %E bytes "
2114 "from a string of length %wu",
2115 stmt, func, cnt, lenrange[0].to_uhwi ());
2116
2117 return warning_at (callloc, OPT_Wstringop_truncation,
2118 "%G%qD output truncated copying between %wu "
2119 "and %wu bytes from a string of length %wu",
2120 stmt, func, cntrange[0].to_uhwi (),
2121 cntrange[1].to_uhwi (), lenrange[0].to_uhwi ());
2122 }
2123 else if (wi::geu_p (lenrange[1], cntrange[1]))
2124 {
2125 /* The longest string is longer than the upper bound of
2126 the count so the truncation is possible. */
2127 if (cntrange[0] == cntrange[1])
2128 return warning_n (callloc, OPT_Wstringop_truncation,
2129 cntrange[0].to_uhwi (),
2130 "%G%qD output may be truncated copying %E "
2131 "byte from a string of length %wu",
2132 "%G%qD output may be truncated copying %E "
2133 "bytes from a string of length %wu",
2134 stmt, func, cnt, lenrange[1].to_uhwi ());
2135
2136 return warning_at (callloc, OPT_Wstringop_truncation,
2137 "%G%qD output may be truncated copying between "
2138 "%wu and %wu bytes from a string of length %wu",
2139 stmt, func, cntrange[0].to_uhwi (),
2140 cntrange[1].to_uhwi (), lenrange[1].to_uhwi ());
2141 }
2142 }
2143
2144 if (!cat_dstlen_bounded
2145 && cntrange[0] != cntrange[1]
2146 && wi::leu_p (cntrange[0], lenrange[0])
2147 && wi::leu_p (cntrange[1], lenrange[0] + 1))
2148 {
2149 /* If the source (including the terminating nul) is longer than
2150 the lower bound of the specified count but shorter than the
2151 upper bound the copy may (but need not) be truncated. */
2152 return warning_at (callloc, OPT_Wstringop_truncation,
2153 "%G%qD output may be truncated copying between "
2154 "%wu and %wu bytes from a string of length %wu",
2155 stmt, func, cntrange[0].to_uhwi (),
2156 cntrange[1].to_uhwi (), lenrange[0].to_uhwi ());
2157 }
2158 }
2159
2160 if (tree dstsize = compute_objsize (dst, 1))
2161 {
2162 /* The source length is uknown. Try to determine the destination
2163 size and see if it matches the specified bound. If not, bail.
2164 Otherwise go on to see if it should be diagnosed for possible
2165 truncation. */
2166 if (!dstsize)
2167 return false;
2168
2169 if (wi::to_wide (dstsize) != cntrange[1])
2170 return false;
2171
2172 /* Avoid warning for strncpy(a, b, N) calls where the following
2173 equalities hold:
2174 N == sizeof a && N == sizeof b */
2175 if (tree srcsize = compute_objsize (src, 1))
2176 if (wi::to_wide (srcsize) == cntrange[1])
2177 return false;
2178
2179 if (cntrange[0] == cntrange[1])
2180 return warning_at (callloc, OPT_Wstringop_truncation,
2181 "%G%qD specified bound %E equals destination size",
2182 stmt, func, cnt);
2183 }
2184
2185 return false;
2186 }
2187
2188 /* Check the arguments to the built-in forms of stpncpy and strncpy for
2189 out-of-bounds offsets or overlapping access, and to see if the size
2190 is derived from calling strlen() on the source argument, and if so,
2191 issue the appropriate warning. */
2192
2193 static void
handle_builtin_stxncpy(built_in_function,gimple_stmt_iterator * gsi)2194 handle_builtin_stxncpy (built_in_function, gimple_stmt_iterator *gsi)
2195 {
2196 if (!strlen_to_stridx)
2197 return;
2198
2199 gimple *stmt = gsi_stmt (*gsi);
2200
2201 tree dst = gimple_call_arg (stmt, 0);
2202 tree src = gimple_call_arg (stmt, 1);
2203 tree len = gimple_call_arg (stmt, 2);
2204 tree dstsize = NULL_TREE, srcsize = NULL_TREE;
2205
2206 int didx = get_stridx (dst);
2207 if (strinfo *sidst = didx > 0 ? get_strinfo (didx) : NULL)
2208 {
2209 /* Compute the size of the destination string including the nul
2210 if it is known to be nul-terminated. */
2211 if (sidst->nonzero_chars)
2212 {
2213 if (sidst->full_string_p)
2214 {
2215 /* String is known to be nul-terminated. */
2216 tree type = TREE_TYPE (sidst->nonzero_chars);
2217 dstsize = fold_build2 (PLUS_EXPR, type, sidst->nonzero_chars,
2218 build_int_cst (type, 1));
2219 }
2220 else
2221 dstsize = sidst->nonzero_chars;
2222 }
2223
2224 dst = sidst->ptr;
2225 }
2226
2227 int sidx = get_stridx (src);
2228 strinfo *sisrc = sidx > 0 ? get_strinfo (sidx) : NULL;
2229 if (sisrc)
2230 {
2231 /* strncat() and strncpy() can modify the source string by writing
2232 over the terminating nul so SISRC->DONT_INVALIDATE must be left
2233 clear. */
2234
2235 /* Compute the size of the source string including the terminating
2236 nul if its known to be nul-terminated. */
2237 if (sisrc->nonzero_chars)
2238 {
2239 if (sisrc->full_string_p)
2240 {
2241 tree type = TREE_TYPE (sisrc->nonzero_chars);
2242 srcsize = fold_build2 (PLUS_EXPR, type, sisrc->nonzero_chars,
2243 build_int_cst (type, 1));
2244 }
2245 else
2246 srcsize = sisrc->nonzero_chars;
2247 }
2248
2249 src = sisrc->ptr;
2250 }
2251 else
2252 srcsize = NULL_TREE;
2253
2254 if (check_bounds_or_overlap (stmt, dst, src, dstsize, srcsize))
2255 {
2256 gimple_set_no_warning (stmt, true);
2257 return;
2258 }
2259
2260 /* If the length argument was computed from strlen(S) for some string
2261 S retrieve the strinfo index for the string (PSS->FIRST) alonng with
2262 the location of the strlen() call (PSS->SECOND). */
2263 stridx_strlenloc *pss = strlen_to_stridx->get (len);
2264 if (!pss || pss->first <= 0)
2265 {
2266 if (maybe_diag_stxncpy_trunc (*gsi, src, len))
2267 gimple_set_no_warning (stmt, true);
2268
2269 return;
2270 }
2271
2272 /* Retrieve the strinfo data for the string S that LEN was computed
2273 from as some function F of strlen (S) (i.e., LEN need not be equal
2274 to strlen(S)). */
2275 strinfo *silen = get_strinfo (pss->first);
2276
2277 location_t callloc = gimple_nonartificial_location (stmt);
2278 callloc = expansion_point_location_if_in_system_header (callloc);
2279
2280 tree func = gimple_call_fndecl (stmt);
2281
2282 bool warned = false;
2283
2284 /* When -Wstringop-truncation is set, try to determine truncation
2285 before diagnosing possible overflow. Truncation is implied by
2286 the LEN argument being equal to strlen(SRC), regardless of
2287 whether its value is known. Otherwise, issue the more generic
2288 -Wstringop-overflow which triggers for LEN arguments that in
2289 any meaningful way depend on strlen(SRC). */
2290 if (sisrc == silen
2291 && is_strlen_related_p (src, len)
2292 && warning_at (callloc, OPT_Wstringop_truncation,
2293 "%G%qD output truncated before terminating nul "
2294 "copying as many bytes from a string as its length",
2295 stmt, func))
2296 warned = true;
2297 else if (silen && is_strlen_related_p (src, silen->ptr))
2298 warned = warning_at (callloc, OPT_Wstringop_overflow_,
2299 "%G%qD specified bound depends on the length "
2300 "of the source argument",
2301 stmt, func);
2302 if (warned)
2303 {
2304 location_t strlenloc = pss->second;
2305 if (strlenloc != UNKNOWN_LOCATION && strlenloc != callloc)
2306 inform (strlenloc, "length computed here");
2307 }
2308 }
2309
2310 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
2311 If strlen of the second argument is known and length of the third argument
2312 is that plus one, strlen of the first argument is the same after this
2313 call. */
2314
2315 static void
handle_builtin_memcpy(enum built_in_function bcode,gimple_stmt_iterator * gsi)2316 handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
2317 {
2318 int idx, didx;
2319 tree src, dst, len, lhs, oldlen, newlen;
2320 gimple *stmt = gsi_stmt (*gsi);
2321 strinfo *si, *dsi, *olddsi;
2322
2323 len = gimple_call_arg (stmt, 2);
2324 src = gimple_call_arg (stmt, 1);
2325 dst = gimple_call_arg (stmt, 0);
2326 idx = get_stridx (src);
2327 if (idx == 0)
2328 return;
2329
2330 didx = get_stridx (dst);
2331 olddsi = NULL;
2332 if (didx > 0)
2333 olddsi = get_strinfo (didx);
2334 else if (didx < 0)
2335 return;
2336
2337 if (olddsi != NULL
2338 && tree_fits_uhwi_p (len)
2339 && !integer_zerop (len))
2340 adjust_last_stmt (olddsi, stmt, false);
2341
2342 bool full_string_p;
2343 if (idx > 0)
2344 {
2345 gimple *def_stmt;
2346
2347 /* Handle memcpy (x, y, l) where l's relationship with strlen (y)
2348 is known. */
2349 si = get_strinfo (idx);
2350 if (si == NULL || si->nonzero_chars == NULL_TREE)
2351 return;
2352 if (TREE_CODE (len) == INTEGER_CST
2353 && TREE_CODE (si->nonzero_chars) == INTEGER_CST)
2354 {
2355 if (tree_int_cst_le (len, si->nonzero_chars))
2356 {
2357 /* Copying LEN nonzero characters, where LEN is constant. */
2358 newlen = len;
2359 full_string_p = false;
2360 }
2361 else
2362 {
2363 /* Copying the whole of the analyzed part of SI. */
2364 newlen = si->nonzero_chars;
2365 full_string_p = si->full_string_p;
2366 }
2367 }
2368 else
2369 {
2370 if (!si->full_string_p)
2371 return;
2372 if (TREE_CODE (len) != SSA_NAME)
2373 return;
2374 def_stmt = SSA_NAME_DEF_STMT (len);
2375 if (!is_gimple_assign (def_stmt)
2376 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
2377 || gimple_assign_rhs1 (def_stmt) != si->nonzero_chars
2378 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
2379 return;
2380 /* Copying variable-length string SI (and no more). */
2381 newlen = si->nonzero_chars;
2382 full_string_p = true;
2383 }
2384 }
2385 else
2386 {
2387 si = NULL;
2388 /* Handle memcpy (x, "abcd", 5) or
2389 memcpy (x, "abc\0uvw", 7). */
2390 if (!tree_fits_uhwi_p (len))
2391 return;
2392
2393 unsigned HOST_WIDE_INT clen = tree_to_uhwi (len);
2394 unsigned HOST_WIDE_INT nonzero_chars = ~idx;
2395 newlen = build_int_cst (size_type_node, MIN (nonzero_chars, clen));
2396 full_string_p = clen > nonzero_chars;
2397 }
2398
2399 if (!full_string_p
2400 && olddsi
2401 && olddsi->nonzero_chars
2402 && TREE_CODE (olddsi->nonzero_chars) == INTEGER_CST
2403 && tree_int_cst_le (newlen, olddsi->nonzero_chars))
2404 {
2405 /* The SRC substring being written strictly overlaps
2406 a subsequence of the existing string OLDDSI. */
2407 newlen = olddsi->nonzero_chars;
2408 full_string_p = olddsi->full_string_p;
2409 }
2410
2411 if (olddsi != NULL && TREE_CODE (len) == SSA_NAME)
2412 adjust_last_stmt (olddsi, stmt, false);
2413
2414 if (didx == 0)
2415 {
2416 didx = new_stridx (dst);
2417 if (didx == 0)
2418 return;
2419 }
2420 oldlen = NULL_TREE;
2421 if (olddsi != NULL)
2422 {
2423 dsi = unshare_strinfo (olddsi);
2424 oldlen = olddsi->nonzero_chars;
2425 dsi->nonzero_chars = newlen;
2426 dsi->full_string_p = full_string_p;
2427 /* Break the chain, so adjust_related_strinfo on later pointers in
2428 the chain won't adjust this one anymore. */
2429 dsi->next = 0;
2430 dsi->stmt = NULL;
2431 dsi->endptr = NULL_TREE;
2432 }
2433 else
2434 {
2435 dsi = new_strinfo (dst, didx, newlen, full_string_p);
2436 set_strinfo (didx, dsi);
2437 find_equal_ptrs (dst, didx);
2438 }
2439 dsi->writable = true;
2440 dsi->dont_invalidate = true;
2441 if (olddsi != NULL)
2442 {
2443 tree adj = NULL_TREE;
2444 location_t loc = gimple_location (stmt);
2445 if (oldlen == NULL_TREE)
2446 ;
2447 else if (integer_zerop (oldlen))
2448 adj = newlen;
2449 else if (TREE_CODE (oldlen) == INTEGER_CST
2450 || TREE_CODE (newlen) == INTEGER_CST)
2451 adj = fold_build2_loc (loc, MINUS_EXPR, TREE_TYPE (newlen), newlen,
2452 fold_convert_loc (loc, TREE_TYPE (newlen),
2453 oldlen));
2454 if (adj != NULL_TREE)
2455 adjust_related_strinfos (loc, dsi, adj);
2456 else
2457 dsi->prev = 0;
2458 }
2459 /* memcpy src may not overlap dst, so src doesn't need to be
2460 invalidated either. */
2461 if (si != NULL)
2462 si->dont_invalidate = true;
2463
2464 if (full_string_p)
2465 {
2466 lhs = gimple_call_lhs (stmt);
2467 switch (bcode)
2468 {
2469 case BUILT_IN_MEMCPY:
2470 case BUILT_IN_MEMCPY_CHK:
2471 /* Allow adjust_last_stmt to decrease this memcpy's size. */
2472 laststmt.stmt = stmt;
2473 laststmt.len = dsi->nonzero_chars;
2474 laststmt.stridx = dsi->idx;
2475 if (lhs)
2476 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
2477 break;
2478 case BUILT_IN_MEMPCPY:
2479 case BUILT_IN_MEMPCPY_CHK:
2480 break;
2481 default:
2482 gcc_unreachable ();
2483 }
2484 }
2485 }
2486
2487 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
2488 If strlen of the second argument is known, strlen of the first argument
2489 is increased by the length of the second argument. Furthermore, attempt
2490 to convert it to memcpy/strcpy if the length of the first argument
2491 is known. */
2492
2493 static void
handle_builtin_strcat(enum built_in_function bcode,gimple_stmt_iterator * gsi)2494 handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi)
2495 {
2496 int idx, didx;
2497 tree srclen, args, type, fn, objsz, endptr;
2498 bool success;
2499 gimple *stmt = gsi_stmt (*gsi);
2500 strinfo *si, *dsi;
2501 location_t loc = gimple_location (stmt);
2502
2503 tree src = gimple_call_arg (stmt, 1);
2504 tree dst = gimple_call_arg (stmt, 0);
2505
2506 /* Bail if the source is the same as destination. It will be diagnosed
2507 elsewhere. */
2508 if (operand_equal_p (src, dst, 0))
2509 return;
2510
2511 tree lhs = gimple_call_lhs (stmt);
2512
2513 didx = get_stridx (dst);
2514 if (didx < 0)
2515 return;
2516
2517 dsi = NULL;
2518 if (didx > 0)
2519 dsi = get_strinfo (didx);
2520
2521 srclen = NULL_TREE;
2522 si = NULL;
2523 idx = get_stridx (src);
2524 if (idx < 0)
2525 srclen = build_int_cst (size_type_node, ~idx);
2526 else if (idx > 0)
2527 {
2528 si = get_strinfo (idx);
2529 if (si != NULL)
2530 srclen = get_string_length (si);
2531 }
2532
2533 /* Set the no-warning bit on the transformed statement? */
2534 bool set_no_warning = false;
2535
2536 if (dsi == NULL || get_string_length (dsi) == NULL_TREE)
2537 {
2538 {
2539 /* The concatenation always involves copying at least one byte
2540 (the terminating nul), even if the source string is empty.
2541 If the source is unknown assume it's one character long and
2542 used that as both sizes. */
2543 tree slen = srclen;
2544 if (slen)
2545 {
2546 tree type = TREE_TYPE (slen);
2547 slen = fold_build2 (PLUS_EXPR, type, slen, build_int_cst (type, 1));
2548 }
2549
2550 tree sptr = si && si->ptr ? si->ptr : src;
2551
2552 if (check_bounds_or_overlap (stmt, dst, sptr, NULL_TREE, slen))
2553 {
2554 gimple_set_no_warning (stmt, true);
2555 set_no_warning = true;
2556 }
2557 }
2558
2559 /* strcat (p, q) can be transformed into
2560 tmp = p + strlen (p); endptr = stpcpy (tmp, q);
2561 with length endptr - p if we need to compute the length
2562 later on. Don't do this transformation if we don't need
2563 it. */
2564 if (builtin_decl_implicit_p (BUILT_IN_STPCPY) && lhs == NULL_TREE)
2565 {
2566 if (didx == 0)
2567 {
2568 didx = new_stridx (dst);
2569 if (didx == 0)
2570 return;
2571 }
2572 if (dsi == NULL)
2573 {
2574 dsi = new_strinfo (dst, didx, NULL_TREE, false);
2575 set_strinfo (didx, dsi);
2576 find_equal_ptrs (dst, didx);
2577 }
2578 else
2579 {
2580 dsi = unshare_strinfo (dsi);
2581 dsi->nonzero_chars = NULL_TREE;
2582 dsi->full_string_p = false;
2583 dsi->next = 0;
2584 dsi->endptr = NULL_TREE;
2585 }
2586 dsi->writable = true;
2587 dsi->stmt = stmt;
2588 dsi->dont_invalidate = true;
2589 }
2590 return;
2591 }
2592
2593 tree dstlen = dsi->nonzero_chars;
2594 endptr = dsi->endptr;
2595
2596 dsi = unshare_strinfo (dsi);
2597 dsi->endptr = NULL_TREE;
2598 dsi->stmt = NULL;
2599 dsi->writable = true;
2600
2601 if (srclen != NULL_TREE)
2602 {
2603 dsi->nonzero_chars = fold_build2_loc (loc, PLUS_EXPR,
2604 TREE_TYPE (dsi->nonzero_chars),
2605 dsi->nonzero_chars, srclen);
2606 gcc_assert (dsi->full_string_p);
2607 adjust_related_strinfos (loc, dsi, srclen);
2608 dsi->dont_invalidate = true;
2609 }
2610 else
2611 {
2612 dsi->nonzero_chars = NULL;
2613 dsi->full_string_p = false;
2614 if (lhs == NULL_TREE && builtin_decl_implicit_p (BUILT_IN_STPCPY))
2615 dsi->dont_invalidate = true;
2616 }
2617
2618 if (si != NULL)
2619 /* strcat src may not overlap dst, so src doesn't need to be
2620 invalidated either. */
2621 si->dont_invalidate = true;
2622
2623 /* For now. Could remove the lhs from the call and add
2624 lhs = dst; afterwards. */
2625 if (lhs)
2626 return;
2627
2628 fn = NULL_TREE;
2629 objsz = NULL_TREE;
2630 switch (bcode)
2631 {
2632 case BUILT_IN_STRCAT:
2633 if (srclen != NULL_TREE)
2634 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
2635 else
2636 fn = builtin_decl_implicit (BUILT_IN_STRCPY);
2637 break;
2638 case BUILT_IN_STRCAT_CHK:
2639 if (srclen != NULL_TREE)
2640 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK);
2641 else
2642 fn = builtin_decl_explicit (BUILT_IN_STRCPY_CHK);
2643 objsz = gimple_call_arg (stmt, 2);
2644 break;
2645 default:
2646 gcc_unreachable ();
2647 }
2648
2649 if (fn == NULL_TREE)
2650 return;
2651
2652 if (dsi && dstlen)
2653 {
2654 tree type = TREE_TYPE (dstlen);
2655
2656 /* Compute the size of the source sequence, including the nul. */
2657 tree srcsize = srclen ? srclen : size_zero_node;
2658 srcsize = fold_build2 (PLUS_EXPR, type, srcsize, build_int_cst (type, 1));
2659
2660 tree sptr = si && si->ptr ? si->ptr : src;
2661
2662 if (check_bounds_or_overlap (stmt, dst, sptr, dstlen, srcsize))
2663 {
2664 gimple_set_no_warning (stmt, true);
2665 set_no_warning = true;
2666 }
2667 }
2668
2669 tree len = NULL_TREE;
2670 if (srclen != NULL_TREE)
2671 {
2672 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
2673 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
2674
2675 len = fold_convert_loc (loc, type, unshare_expr (srclen));
2676 len = fold_build2_loc (loc, PLUS_EXPR, type, len,
2677 build_int_cst (type, 1));
2678 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
2679 GSI_SAME_STMT);
2680 }
2681 if (endptr)
2682 dst = fold_convert_loc (loc, TREE_TYPE (dst), unshare_expr (endptr));
2683 else
2684 dst = fold_build2_loc (loc, POINTER_PLUS_EXPR, TREE_TYPE (dst), dst,
2685 fold_convert_loc (loc, sizetype,
2686 unshare_expr (dstlen)));
2687 dst = force_gimple_operand_gsi (gsi, dst, true, NULL_TREE, true,
2688 GSI_SAME_STMT);
2689 if (objsz)
2690 {
2691 objsz = fold_build2_loc (loc, MINUS_EXPR, TREE_TYPE (objsz), objsz,
2692 fold_convert_loc (loc, TREE_TYPE (objsz),
2693 unshare_expr (dstlen)));
2694 objsz = force_gimple_operand_gsi (gsi, objsz, true, NULL_TREE, true,
2695 GSI_SAME_STMT);
2696 }
2697 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
2698 {
2699 fprintf (dump_file, "Optimizing: ");
2700 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2701 }
2702 if (srclen != NULL_TREE)
2703 success = update_gimple_call (gsi, fn, 3 + (objsz != NULL_TREE),
2704 dst, src, len, objsz);
2705 else
2706 success = update_gimple_call (gsi, fn, 2 + (objsz != NULL_TREE),
2707 dst, src, objsz);
2708 if (success)
2709 {
2710 stmt = gsi_stmt (*gsi);
2711 update_stmt (stmt);
2712 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
2713 {
2714 fprintf (dump_file, "into: ");
2715 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2716 }
2717 /* If srclen == NULL, note that current string length can be
2718 computed by transforming this strcpy into stpcpy. */
2719 if (srclen == NULL_TREE && dsi->dont_invalidate)
2720 dsi->stmt = stmt;
2721 adjust_last_stmt (dsi, stmt, true);
2722 if (srclen != NULL_TREE)
2723 {
2724 laststmt.stmt = stmt;
2725 laststmt.len = srclen;
2726 laststmt.stridx = dsi->idx;
2727 }
2728 }
2729 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
2730 fprintf (dump_file, "not possible.\n");
2731
2732 if (set_no_warning)
2733 gimple_set_no_warning (stmt, true);
2734 }
2735
2736 /* Handle a call to malloc or calloc. */
2737
2738 static void
handle_builtin_malloc(enum built_in_function bcode,gimple_stmt_iterator * gsi)2739 handle_builtin_malloc (enum built_in_function bcode, gimple_stmt_iterator *gsi)
2740 {
2741 gimple *stmt = gsi_stmt (*gsi);
2742 tree lhs = gimple_call_lhs (stmt);
2743 if (lhs == NULL_TREE)
2744 return;
2745
2746 gcc_assert (get_stridx (lhs) == 0);
2747 int idx = new_stridx (lhs);
2748 tree length = NULL_TREE;
2749 if (bcode == BUILT_IN_CALLOC)
2750 length = build_int_cst (size_type_node, 0);
2751 strinfo *si = new_strinfo (lhs, idx, length, length != NULL_TREE);
2752 if (bcode == BUILT_IN_CALLOC)
2753 si->endptr = lhs;
2754 set_strinfo (idx, si);
2755 si->writable = true;
2756 si->stmt = stmt;
2757 si->dont_invalidate = true;
2758 }
2759
2760 /* Handle a call to memset.
2761 After a call to calloc, memset(,0,) is unnecessary.
2762 memset(malloc(n),0,n) is calloc(n,1).
2763 return true when the call is transfomred, false otherwise. */
2764
2765 static bool
handle_builtin_memset(gimple_stmt_iterator * gsi)2766 handle_builtin_memset (gimple_stmt_iterator *gsi)
2767 {
2768 gimple *stmt2 = gsi_stmt (*gsi);
2769 if (!integer_zerop (gimple_call_arg (stmt2, 1)))
2770 return false;
2771 tree ptr = gimple_call_arg (stmt2, 0);
2772 int idx1 = get_stridx (ptr);
2773 if (idx1 <= 0)
2774 return false;
2775 strinfo *si1 = get_strinfo (idx1);
2776 if (!si1)
2777 return false;
2778 gimple *stmt1 = si1->stmt;
2779 if (!stmt1 || !is_gimple_call (stmt1))
2780 return false;
2781 tree callee1 = gimple_call_fndecl (stmt1);
2782 if (!valid_builtin_call (stmt1))
2783 return false;
2784 enum built_in_function code1 = DECL_FUNCTION_CODE (callee1);
2785 tree size = gimple_call_arg (stmt2, 2);
2786 if (code1 == BUILT_IN_CALLOC)
2787 /* Not touching stmt1 */ ;
2788 else if (code1 == BUILT_IN_MALLOC
2789 && operand_equal_p (gimple_call_arg (stmt1, 0), size, 0))
2790 {
2791 gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt1);
2792 update_gimple_call (&gsi1, builtin_decl_implicit (BUILT_IN_CALLOC), 2,
2793 size, build_one_cst (size_type_node));
2794 si1->nonzero_chars = build_int_cst (size_type_node, 0);
2795 si1->full_string_p = true;
2796 si1->stmt = gsi_stmt (gsi1);
2797 }
2798 else
2799 return false;
2800 tree lhs = gimple_call_lhs (stmt2);
2801 unlink_stmt_vdef (stmt2);
2802 if (lhs)
2803 {
2804 gimple *assign = gimple_build_assign (lhs, ptr);
2805 gsi_replace (gsi, assign, false);
2806 }
2807 else
2808 {
2809 gsi_remove (gsi, true);
2810 release_defs (stmt2);
2811 }
2812
2813 return true;
2814 }
2815
2816 /* Handle a call to memcmp. We try to handle small comparisons by
2817 converting them to load and compare, and replacing the call to memcmp
2818 with a __builtin_memcmp_eq call where possible.
2819 return true when call is transformed, return false otherwise. */
2820
2821 static bool
handle_builtin_memcmp(gimple_stmt_iterator * gsi)2822 handle_builtin_memcmp (gimple_stmt_iterator *gsi)
2823 {
2824 gcall *stmt2 = as_a <gcall *> (gsi_stmt (*gsi));
2825 tree res = gimple_call_lhs (stmt2);
2826 tree arg1 = gimple_call_arg (stmt2, 0);
2827 tree arg2 = gimple_call_arg (stmt2, 1);
2828 tree len = gimple_call_arg (stmt2, 2);
2829 unsigned HOST_WIDE_INT leni;
2830 use_operand_p use_p;
2831 imm_use_iterator iter;
2832
2833 if (!res)
2834 return false;
2835
2836 FOR_EACH_IMM_USE_FAST (use_p, iter, res)
2837 {
2838 gimple *ustmt = USE_STMT (use_p);
2839
2840 if (is_gimple_debug (ustmt))
2841 continue;
2842 if (gimple_code (ustmt) == GIMPLE_ASSIGN)
2843 {
2844 gassign *asgn = as_a <gassign *> (ustmt);
2845 tree_code code = gimple_assign_rhs_code (asgn);
2846 if ((code != EQ_EXPR && code != NE_EXPR)
2847 || !integer_zerop (gimple_assign_rhs2 (asgn)))
2848 return false;
2849 }
2850 else if (gimple_code (ustmt) == GIMPLE_COND)
2851 {
2852 tree_code code = gimple_cond_code (ustmt);
2853 if ((code != EQ_EXPR && code != NE_EXPR)
2854 || !integer_zerop (gimple_cond_rhs (ustmt)))
2855 return false;
2856 }
2857 else
2858 return false;
2859 }
2860
2861 if (tree_fits_uhwi_p (len)
2862 && (leni = tree_to_uhwi (len)) <= GET_MODE_SIZE (word_mode)
2863 && pow2p_hwi (leni))
2864 {
2865 leni *= CHAR_TYPE_SIZE;
2866 unsigned align1 = get_pointer_alignment (arg1);
2867 unsigned align2 = get_pointer_alignment (arg2);
2868 unsigned align = MIN (align1, align2);
2869 scalar_int_mode mode;
2870 if (int_mode_for_size (leni, 1).exists (&mode)
2871 && (align >= leni || !targetm.slow_unaligned_access (mode, align)))
2872 {
2873 location_t loc = gimple_location (stmt2);
2874 tree type, off;
2875 type = build_nonstandard_integer_type (leni, 1);
2876 gcc_assert (known_eq (GET_MODE_BITSIZE (TYPE_MODE (type)), leni));
2877 tree ptrtype = build_pointer_type_for_mode (char_type_node,
2878 ptr_mode, true);
2879 off = build_int_cst (ptrtype, 0);
2880 arg1 = build2_loc (loc, MEM_REF, type, arg1, off);
2881 arg2 = build2_loc (loc, MEM_REF, type, arg2, off);
2882 tree tem1 = fold_const_aggregate_ref (arg1);
2883 if (tem1)
2884 arg1 = tem1;
2885 tree tem2 = fold_const_aggregate_ref (arg2);
2886 if (tem2)
2887 arg2 = tem2;
2888 res = fold_convert_loc (loc, TREE_TYPE (res),
2889 fold_build2_loc (loc, NE_EXPR,
2890 boolean_type_node,
2891 arg1, arg2));
2892 gimplify_and_update_call_from_tree (gsi, res);
2893 return true;
2894 }
2895 }
2896
2897 gimple_call_set_fndecl (stmt2, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ));
2898 return true;
2899 }
2900
2901 /* Given an index to the strinfo vector, compute the string length for the
2902 corresponding string. Return -1 when unknown. */
2903
2904 static HOST_WIDE_INT
compute_string_length(int idx)2905 compute_string_length (int idx)
2906 {
2907 HOST_WIDE_INT string_leni = -1;
2908 gcc_assert (idx != 0);
2909
2910 if (idx < 0)
2911 return ~idx;
2912
2913 strinfo *si = get_strinfo (idx);
2914 if (si)
2915 {
2916 tree const_string_len = get_string_length (si);
2917 if (const_string_len && tree_fits_shwi_p (const_string_len))
2918 string_leni = tree_to_shwi (const_string_len);
2919 }
2920
2921 if (string_leni < 0)
2922 return -1;
2923
2924 return string_leni;
2925 }
2926
2927 /* Determine the minimum size of the object referenced by DEST expression which
2928 must have a pointer type.
2929 Return the minimum size of the object if successful or NULL when the size
2930 cannot be determined. */
2931 static tree
determine_min_objsize(tree dest)2932 determine_min_objsize (tree dest)
2933 {
2934 unsigned HOST_WIDE_INT size = 0;
2935
2936 if (compute_builtin_object_size (dest, 2, &size))
2937 return build_int_cst (sizetype, size);
2938
2939 /* Try to determine the size of the object through the RHS of the
2940 assign statement. */
2941 if (TREE_CODE (dest) == SSA_NAME)
2942 {
2943 gimple *stmt = SSA_NAME_DEF_STMT (dest);
2944 if (!is_gimple_assign (stmt))
2945 return NULL_TREE;
2946
2947 if (!gimple_assign_single_p (stmt)
2948 && !gimple_assign_unary_nop_p (stmt))
2949 return NULL_TREE;
2950
2951 dest = gimple_assign_rhs1 (stmt);
2952 return determine_min_objsize (dest);
2953 }
2954
2955 /* Try to determine the size of the object from its type. */
2956 if (TREE_CODE (dest) != ADDR_EXPR)
2957 return NULL_TREE;
2958
2959 tree type = TREE_TYPE (dest);
2960 if (TREE_CODE (type) == POINTER_TYPE)
2961 type = TREE_TYPE (type);
2962
2963 type = TYPE_MAIN_VARIANT (type);
2964
2965 /* We cannot determine the size of the array if it's a flexible array,
2966 which is declared at the end of a structure. */
2967 if (TREE_CODE (type) == ARRAY_TYPE
2968 && !array_at_struct_end_p (dest))
2969 {
2970 tree size_t = TYPE_SIZE_UNIT (type);
2971 if (size_t && TREE_CODE (size_t) == INTEGER_CST
2972 && !integer_zerop (size_t))
2973 return size_t;
2974 }
2975
2976 return NULL_TREE;
2977 }
2978
2979 /* Handle a call to strcmp or strncmp. When the result is ONLY used to do
2980 equality test against zero:
2981
2982 A. When the lengths of both arguments are constant and it's a strcmp:
2983 * if the lengths are NOT equal, we can safely fold the call
2984 to a non-zero value.
2985 * otherwise, do nothing now.
2986
2987 B. When the length of one argument is constant, try to replace the call with
2988 a __builtin_str(n)cmp_eq call where possible, i.e:
2989
2990 strncmp (s, STR, C) (!)= 0 in which, s is a pointer to a string, STR is a
2991 string with constant length , C is a constant.
2992 if (C <= strlen(STR) && sizeof_array(s) > C)
2993 {
2994 replace this call with
2995 strncmp_eq (s, STR, C) (!)= 0
2996 }
2997 if (C > strlen(STR)
2998 {
2999 it can be safely treated as a call to strcmp (s, STR) (!)= 0
3000 can handled by the following strcmp.
3001 }
3002
3003 strcmp (s, STR) (!)= 0 in which, s is a pointer to a string, STR is a
3004 string with constant length.
3005 if (sizeof_array(s) > strlen(STR))
3006 {
3007 replace this call with
3008 strcmp_eq (s, STR, strlen(STR)+1) (!)= 0
3009 }
3010
3011 Return true when the call is transformed, return false otherwise.
3012 */
3013
3014 static bool
handle_builtin_string_cmp(gimple_stmt_iterator * gsi)3015 handle_builtin_string_cmp (gimple_stmt_iterator *gsi)
3016 {
3017 gcall *stmt = as_a <gcall *> (gsi_stmt (*gsi));
3018 tree res = gimple_call_lhs (stmt);
3019 use_operand_p use_p;
3020 imm_use_iterator iter;
3021 tree arg1 = gimple_call_arg (stmt, 0);
3022 tree arg2 = gimple_call_arg (stmt, 1);
3023 int idx1 = get_stridx (arg1);
3024 int idx2 = get_stridx (arg2);
3025 HOST_WIDE_INT length = -1;
3026 bool is_ncmp = false;
3027
3028 if (!res)
3029 return false;
3030
3031 /* When both arguments are unknown, do nothing. */
3032 if (idx1 == 0 && idx2 == 0)
3033 return false;
3034
3035 /* Handle strncmp function. */
3036 if (gimple_call_num_args (stmt) == 3)
3037 {
3038 tree len = gimple_call_arg (stmt, 2);
3039 if (tree_fits_shwi_p (len))
3040 length = tree_to_shwi (len);
3041
3042 is_ncmp = true;
3043 }
3044
3045 /* For strncmp, if the length argument is NOT known, do nothing. */
3046 if (is_ncmp && length < 0)
3047 return false;
3048
3049 /* When the result is ONLY used to do equality test against zero. */
3050 FOR_EACH_IMM_USE_FAST (use_p, iter, res)
3051 {
3052 gimple *use_stmt = USE_STMT (use_p);
3053
3054 if (is_gimple_debug (use_stmt))
3055 continue;
3056 if (gimple_code (use_stmt) == GIMPLE_ASSIGN)
3057 {
3058 tree_code code = gimple_assign_rhs_code (use_stmt);
3059 if (code == COND_EXPR)
3060 {
3061 tree cond_expr = gimple_assign_rhs1 (use_stmt);
3062 if ((TREE_CODE (cond_expr) != EQ_EXPR
3063 && (TREE_CODE (cond_expr) != NE_EXPR))
3064 || !integer_zerop (TREE_OPERAND (cond_expr, 1)))
3065 return false;
3066 }
3067 else if (code == EQ_EXPR || code == NE_EXPR)
3068 {
3069 if (!integer_zerop (gimple_assign_rhs2 (use_stmt)))
3070 return false;
3071 }
3072 else
3073 return false;
3074 }
3075 else if (gimple_code (use_stmt) == GIMPLE_COND)
3076 {
3077 tree_code code = gimple_cond_code (use_stmt);
3078 if ((code != EQ_EXPR && code != NE_EXPR)
3079 || !integer_zerop (gimple_cond_rhs (use_stmt)))
3080 return false;
3081 }
3082 else
3083 return false;
3084 }
3085
3086 /* When the lengths of both arguments are known, and they are unequal, we can
3087 safely fold the call to a non-zero value for strcmp;
3088 othewise, do nothing now. */
3089 if (idx1 != 0 && idx2 != 0)
3090 {
3091 HOST_WIDE_INT const_string_leni1 = compute_string_length (idx1);
3092 HOST_WIDE_INT const_string_leni2 = compute_string_length (idx2);
3093
3094 if (!is_ncmp
3095 && const_string_leni1 != -1
3096 && const_string_leni2 != -1
3097 && const_string_leni1 != const_string_leni2)
3098 {
3099 replace_call_with_value (gsi, integer_one_node);
3100 return true;
3101 }
3102 return false;
3103 }
3104
3105 /* When the length of one argument is constant. */
3106 tree var_string = NULL_TREE;
3107 HOST_WIDE_INT const_string_leni = -1;
3108
3109 if (idx1)
3110 {
3111 const_string_leni = compute_string_length (idx1);
3112 var_string = arg2;
3113 }
3114 else
3115 {
3116 gcc_checking_assert (idx2);
3117 const_string_leni = compute_string_length (idx2);
3118 var_string = arg1;
3119 }
3120
3121 if (const_string_leni < 0)
3122 return false;
3123
3124 unsigned HOST_WIDE_INT var_sizei = 0;
3125 /* try to determine the minimum size of the object pointed by var_string. */
3126 tree size = determine_min_objsize (var_string);
3127
3128 if (!size)
3129 return false;
3130
3131 if (tree_fits_uhwi_p (size))
3132 var_sizei = tree_to_uhwi (size);
3133
3134 if (var_sizei == 0)
3135 return false;
3136
3137 /* For strncmp, if length > const_string_leni , this call can be safely
3138 transformed to a strcmp. */
3139 if (is_ncmp && length > const_string_leni)
3140 is_ncmp = false;
3141
3142 unsigned HOST_WIDE_INT final_length
3143 = is_ncmp ? length : const_string_leni + 1;
3144
3145 /* Replace strcmp or strncmp with the corresponding str(n)cmp_eq. */
3146 if (var_sizei > final_length)
3147 {
3148 tree fn
3149 = (is_ncmp
3150 ? builtin_decl_implicit (BUILT_IN_STRNCMP_EQ)
3151 : builtin_decl_implicit (BUILT_IN_STRCMP_EQ));
3152 if (!fn)
3153 return false;
3154 tree const_string_len = build_int_cst (size_type_node, final_length);
3155 update_gimple_call (gsi, fn, 3, arg1, arg2, const_string_len);
3156 }
3157 else
3158 return false;
3159
3160 return true;
3161 }
3162
3163 /* Handle a POINTER_PLUS_EXPR statement.
3164 For p = "abcd" + 2; compute associated length, or if
3165 p = q + off is pointing to a '\0' character of a string, call
3166 zero_length_string on it. */
3167
3168 static void
handle_pointer_plus(gimple_stmt_iterator * gsi)3169 handle_pointer_plus (gimple_stmt_iterator *gsi)
3170 {
3171 gimple *stmt = gsi_stmt (*gsi);
3172 tree lhs = gimple_assign_lhs (stmt), off;
3173 int idx = get_stridx (gimple_assign_rhs1 (stmt));
3174 strinfo *si, *zsi;
3175
3176 if (idx == 0)
3177 return;
3178
3179 if (idx < 0)
3180 {
3181 tree off = gimple_assign_rhs2 (stmt);
3182 if (tree_fits_uhwi_p (off)
3183 && tree_to_uhwi (off) <= (unsigned HOST_WIDE_INT) ~idx)
3184 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)]
3185 = ~(~idx - (int) tree_to_uhwi (off));
3186 return;
3187 }
3188
3189 si = get_strinfo (idx);
3190 if (si == NULL || si->nonzero_chars == NULL_TREE)
3191 return;
3192
3193 off = gimple_assign_rhs2 (stmt);
3194 zsi = NULL;
3195 if (si->full_string_p && operand_equal_p (si->nonzero_chars, off, 0))
3196 zsi = zero_length_string (lhs, si);
3197 else if (TREE_CODE (off) == SSA_NAME)
3198 {
3199 gimple *def_stmt = SSA_NAME_DEF_STMT (off);
3200 if (gimple_assign_single_p (def_stmt)
3201 && si->full_string_p
3202 && operand_equal_p (si->nonzero_chars,
3203 gimple_assign_rhs1 (def_stmt), 0))
3204 zsi = zero_length_string (lhs, si);
3205 }
3206 if (zsi != NULL
3207 && si->endptr != NULL_TREE
3208 && si->endptr != lhs
3209 && TREE_CODE (si->endptr) == SSA_NAME)
3210 {
3211 enum tree_code rhs_code
3212 = useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (si->endptr))
3213 ? SSA_NAME : NOP_EXPR;
3214 gimple_assign_set_rhs_with_ops (gsi, rhs_code, si->endptr);
3215 gcc_assert (gsi_stmt (*gsi) == stmt);
3216 update_stmt (stmt);
3217 }
3218 }
3219
3220 /* If RHS, either directly or indirectly, refers to a string of constant
3221 length, return the length. Otherwise, if it refers to a character
3222 constant, return 1 if the constant is non-zero and 0 if it is nul.
3223 Otherwise, return a negative value. */
3224
3225 static HOST_WIDE_INT
get_min_string_length(tree rhs,bool * full_string_p)3226 get_min_string_length (tree rhs, bool *full_string_p)
3227 {
3228 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs)))
3229 {
3230 if (tree_expr_nonzero_p (rhs))
3231 {
3232 *full_string_p = false;
3233 return 1;
3234 }
3235
3236 *full_string_p = true;
3237 return 0;
3238 }
3239
3240 if (TREE_CODE (rhs) == MEM_REF
3241 && integer_zerop (TREE_OPERAND (rhs, 1)))
3242 {
3243 rhs = TREE_OPERAND (rhs, 0);
3244 if (TREE_CODE (rhs) == ADDR_EXPR)
3245 {
3246 tree rhs_addr = rhs;
3247
3248 rhs = TREE_OPERAND (rhs, 0);
3249 if (TREE_CODE (rhs) != STRING_CST)
3250 {
3251 int idx = get_stridx (rhs_addr);
3252 if (idx > 0)
3253 {
3254 strinfo *si = get_strinfo (idx);
3255 if (si
3256 && tree_fits_shwi_p (si->nonzero_chars))
3257 {
3258 *full_string_p = si->full_string_p;
3259 return tree_to_shwi (si->nonzero_chars);
3260 }
3261 }
3262 }
3263 }
3264 }
3265
3266 if (TREE_CODE (rhs) == VAR_DECL
3267 && TREE_READONLY (rhs))
3268 rhs = DECL_INITIAL (rhs);
3269
3270 if (rhs && TREE_CODE (rhs) == STRING_CST)
3271 {
3272 HOST_WIDE_INT len = strlen (TREE_STRING_POINTER (rhs));
3273 *full_string_p = len < TREE_STRING_LENGTH (rhs);
3274 return len;
3275 }
3276
3277 return -1;
3278 }
3279
3280 /* Handle a single or multiple character store either by single
3281 character assignment or by multi-character assignment from
3282 MEM_REF. */
3283
3284 static bool
handle_char_store(gimple_stmt_iterator * gsi)3285 handle_char_store (gimple_stmt_iterator *gsi)
3286 {
3287 int idx = -1;
3288 strinfo *si = NULL;
3289 gimple *stmt = gsi_stmt (*gsi);
3290 tree ssaname = NULL_TREE, lhs = gimple_assign_lhs (stmt);
3291 tree rhs = gimple_assign_rhs1 (stmt);
3292 unsigned HOST_WIDE_INT offset = 0;
3293
3294 if (TREE_CODE (lhs) == MEM_REF
3295 && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME)
3296 {
3297 tree mem_offset = TREE_OPERAND (lhs, 1);
3298 if (tree_fits_uhwi_p (mem_offset))
3299 {
3300 /* Get the strinfo for the base, and use it if it starts with at
3301 least OFFSET nonzero characters. This is trivially true if
3302 OFFSET is zero. */
3303 offset = tree_to_uhwi (mem_offset);
3304 idx = get_stridx (TREE_OPERAND (lhs, 0));
3305 if (idx > 0)
3306 si = get_strinfo (idx);
3307 if (offset == 0)
3308 ssaname = TREE_OPERAND (lhs, 0);
3309 else if (si == NULL || compare_nonzero_chars (si, offset) < 0)
3310 return true;
3311 }
3312 }
3313 else
3314 {
3315 idx = get_addr_stridx (lhs, NULL_TREE, &offset);
3316 if (idx > 0)
3317 si = get_strinfo (idx);
3318 }
3319
3320 /* STORING_NONZERO_P is true iff not all stored characters are zero.
3321 STORING_ALL_ZEROS_P is true iff all stored characters are zero.
3322 Both are false when it's impossible to determine which is true. */
3323 bool storing_nonzero_p;
3324 bool storing_all_zeros_p = initializer_zerop (rhs, &storing_nonzero_p);
3325 if (!storing_nonzero_p)
3326 storing_nonzero_p = tree_expr_nonzero_p (rhs);
3327 bool full_string_p = storing_all_zeros_p;
3328
3329 /* Set to the length of the string being assigned if known. */
3330 HOST_WIDE_INT rhslen;
3331
3332 if (si != NULL)
3333 {
3334 int cmp = compare_nonzero_chars (si, offset);
3335 gcc_assert (offset == 0 || cmp >= 0);
3336 if (storing_all_zeros_p && cmp == 0 && si->full_string_p)
3337 {
3338 /* When overwriting a '\0' with a '\0', the store can be removed
3339 if we know it has been stored in the current function. */
3340 if (!stmt_could_throw_p (cfun, stmt) && si->writable)
3341 {
3342 unlink_stmt_vdef (stmt);
3343 release_defs (stmt);
3344 gsi_remove (gsi, true);
3345 return false;
3346 }
3347 else
3348 {
3349 si->writable = true;
3350 gsi_next (gsi);
3351 return false;
3352 }
3353 }
3354 if (cmp > 0
3355 && storing_nonzero_p
3356 && TREE_CODE (TREE_TYPE (rhs)) == INTEGER_TYPE)
3357 {
3358 /* Handle a single non-nul character store.
3359 If si->nonzero_chars > OFFSET, we aren't overwriting '\0',
3360 and if we aren't storing '\0', we know that the length of the
3361 string and any other zero terminated string in memory remains
3362 the same. In that case we move to the next gimple statement and
3363 return to signal the caller that it shouldn't invalidate anything.
3364 This is benefical for cases like:
3365
3366 char p[20];
3367 void foo (char *q)
3368 {
3369 strcpy (p, "foobar");
3370 size_t len = strlen (p); // can be folded to 6
3371 size_t len2 = strlen (q); // has to be computed
3372 p[0] = 'X';
3373 size_t len3 = strlen (p); // can be folded to 6
3374 size_t len4 = strlen (q); // can be folded to len2
3375 bar (len, len2, len3, len4);
3376 } */
3377 gsi_next (gsi);
3378 return false;
3379 }
3380
3381 if (storing_all_zeros_p
3382 || storing_nonzero_p
3383 || (offset != 0 && cmp > 0))
3384
3385 {
3386 /* When STORING_NONZERO_P, we know that the string will start
3387 with at least OFFSET + 1 nonzero characters. If storing
3388 a single character, set si->NONZERO_CHARS to the result.
3389 If storing multiple characters, try to determine the number
3390 of leading non-zero characters and set si->NONZERO_CHARS to
3391 the result instead.
3392
3393 When STORING_ALL_ZEROS_P, we know that the string is now
3394 OFFSET characters long.
3395
3396 Otherwise, we're storing an unknown value at offset OFFSET,
3397 so need to clip the nonzero_chars to OFFSET. */
3398 bool full_string_p = storing_all_zeros_p;
3399 HOST_WIDE_INT len = 1;
3400 if (storing_nonzero_p)
3401 {
3402 /* Try to get the minimum length of the string (or
3403 individual character) being stored. If it fails,
3404 STORING_NONZERO_P guarantees it's at least 1. */
3405 len = get_min_string_length (rhs, &full_string_p);
3406 if (len < 0)
3407 len = 1;
3408 }
3409
3410 location_t loc = gimple_location (stmt);
3411 tree oldlen = si->nonzero_chars;
3412 if (cmp == 0 && si->full_string_p)
3413 /* We're overwriting the nul terminator with a nonzero or
3414 unknown character. If the previous stmt was a memcpy,
3415 its length may be decreased. */
3416 adjust_last_stmt (si, stmt, false);
3417 si = unshare_strinfo (si);
3418 if (storing_nonzero_p)
3419 {
3420 gcc_assert (len >= 0);
3421 si->nonzero_chars = build_int_cst (size_type_node, offset + len);
3422 }
3423 else
3424 si->nonzero_chars = build_int_cst (size_type_node, offset);
3425 si->full_string_p = full_string_p;
3426 if (storing_all_zeros_p
3427 && ssaname
3428 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname))
3429 si->endptr = ssaname;
3430 else
3431 si->endptr = NULL;
3432 si->next = 0;
3433 si->stmt = NULL;
3434 si->writable = true;
3435 si->dont_invalidate = true;
3436 if (oldlen)
3437 {
3438 tree adj = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
3439 si->nonzero_chars, oldlen);
3440 adjust_related_strinfos (loc, si, adj);
3441 }
3442 else
3443 si->prev = 0;
3444 }
3445 }
3446 else if (idx == 0 && (storing_all_zeros_p || storing_nonzero_p))
3447 {
3448 if (ssaname)
3449 idx = new_stridx (ssaname);
3450 else
3451 idx = new_addr_stridx (lhs);
3452 if (idx != 0)
3453 {
3454 tree ptr = (ssaname ? ssaname : build_fold_addr_expr (lhs));
3455 HOST_WIDE_INT slen = (storing_all_zeros_p
3456 ? 0
3457 : (storing_nonzero_p
3458 ? get_min_string_length (rhs, &full_string_p)
3459 : -1));
3460 tree len = (slen <= 0
3461 ? size_zero_node
3462 : build_int_cst (size_type_node, slen));
3463 si = new_strinfo (ptr, idx, len, slen >= 0 && full_string_p);
3464 set_strinfo (idx, si);
3465 if (storing_all_zeros_p
3466 && ssaname
3467 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname))
3468 si->endptr = ssaname;
3469 si->dont_invalidate = true;
3470 si->writable = true;
3471 }
3472 }
3473 else if (idx == 0
3474 && (rhslen = get_min_string_length (rhs, &full_string_p)) >= 0
3475 && ssaname == NULL_TREE
3476 && TREE_CODE (TREE_TYPE (lhs)) == ARRAY_TYPE)
3477 {
3478 HOST_WIDE_INT a = int_size_in_bytes (TREE_TYPE (lhs));
3479 if (a > 0 && (unsigned HOST_WIDE_INT) a > (unsigned HOST_WIDE_INT) rhslen)
3480 {
3481 int idx = new_addr_stridx (lhs);
3482 if (idx != 0)
3483 {
3484 si = new_strinfo (build_fold_addr_expr (lhs), idx,
3485 build_int_cst (size_type_node, rhslen),
3486 full_string_p);
3487 set_strinfo (idx, si);
3488 si->dont_invalidate = true;
3489 }
3490 }
3491 }
3492
3493 if (si != NULL && offset == 0 && storing_all_zeros_p)
3494 {
3495 /* Allow adjust_last_stmt to remove it if the stored '\0'
3496 is immediately overwritten. */
3497 laststmt.stmt = stmt;
3498 laststmt.len = build_int_cst (size_type_node, 1);
3499 laststmt.stridx = si->idx;
3500 }
3501 return true;
3502 }
3503
3504 /* Try to fold strstr (s, t) eq/ne s to strncmp (s, t, strlen (t)) eq/ne 0. */
3505
3506 static void
fold_strstr_to_strncmp(tree rhs1,tree rhs2,gimple * stmt)3507 fold_strstr_to_strncmp (tree rhs1, tree rhs2, gimple *stmt)
3508 {
3509 if (TREE_CODE (rhs1) != SSA_NAME
3510 || TREE_CODE (rhs2) != SSA_NAME)
3511 return;
3512
3513 gimple *call_stmt = NULL;
3514 for (int pass = 0; pass < 2; pass++)
3515 {
3516 gimple *g = SSA_NAME_DEF_STMT (rhs1);
3517 if (gimple_call_builtin_p (g, BUILT_IN_STRSTR)
3518 && has_single_use (rhs1)
3519 && gimple_call_arg (g, 0) == rhs2)
3520 {
3521 call_stmt = g;
3522 break;
3523 }
3524 std::swap (rhs1, rhs2);
3525 }
3526
3527 if (call_stmt)
3528 {
3529 tree arg0 = gimple_call_arg (call_stmt, 0);
3530
3531 if (arg0 == rhs2)
3532 {
3533 tree arg1 = gimple_call_arg (call_stmt, 1);
3534 tree arg1_len = NULL_TREE;
3535 int idx = get_stridx (arg1);
3536
3537 if (idx)
3538 {
3539 if (idx < 0)
3540 arg1_len = build_int_cst (size_type_node, ~idx);
3541 else
3542 {
3543 strinfo *si = get_strinfo (idx);
3544 if (si)
3545 arg1_len = get_string_length (si);
3546 }
3547 }
3548
3549 if (arg1_len != NULL_TREE)
3550 {
3551 gimple_stmt_iterator gsi = gsi_for_stmt (call_stmt);
3552 tree strncmp_decl = builtin_decl_explicit (BUILT_IN_STRNCMP);
3553
3554 if (!is_gimple_val (arg1_len))
3555 {
3556 tree arg1_len_tmp = make_ssa_name (TREE_TYPE (arg1_len));
3557 gassign *arg1_stmt = gimple_build_assign (arg1_len_tmp,
3558 arg1_len);
3559 gsi_insert_before (&gsi, arg1_stmt, GSI_SAME_STMT);
3560 arg1_len = arg1_len_tmp;
3561 }
3562
3563 gcall *strncmp_call = gimple_build_call (strncmp_decl, 3,
3564 arg0, arg1, arg1_len);
3565 tree strncmp_lhs = make_ssa_name (integer_type_node);
3566 gimple_set_vuse (strncmp_call, gimple_vuse (call_stmt));
3567 gimple_call_set_lhs (strncmp_call, strncmp_lhs);
3568 gsi_remove (&gsi, true);
3569 gsi_insert_before (&gsi, strncmp_call, GSI_SAME_STMT);
3570 tree zero = build_zero_cst (TREE_TYPE (strncmp_lhs));
3571
3572 if (is_gimple_assign (stmt))
3573 {
3574 if (gimple_assign_rhs_code (stmt) == COND_EXPR)
3575 {
3576 tree cond = gimple_assign_rhs1 (stmt);
3577 TREE_OPERAND (cond, 0) = strncmp_lhs;
3578 TREE_OPERAND (cond, 1) = zero;
3579 }
3580 else
3581 {
3582 gimple_assign_set_rhs1 (stmt, strncmp_lhs);
3583 gimple_assign_set_rhs2 (stmt, zero);
3584 }
3585 }
3586 else
3587 {
3588 gcond *cond = as_a<gcond *> (stmt);
3589 gimple_cond_set_lhs (cond, strncmp_lhs);
3590 gimple_cond_set_rhs (cond, zero);
3591 }
3592 update_stmt (stmt);
3593 }
3594 }
3595 }
3596 }
3597
3598 /* Attempt to check for validity of the performed access a single statement
3599 at *GSI using string length knowledge, and to optimize it.
3600 If the given basic block needs clean-up of EH, CLEANUP_EH is set to
3601 true. */
3602
3603 static bool
strlen_check_and_optimize_stmt(gimple_stmt_iterator * gsi,bool * cleanup_eh)3604 strlen_check_and_optimize_stmt (gimple_stmt_iterator *gsi, bool *cleanup_eh)
3605 {
3606 gimple *stmt = gsi_stmt (*gsi);
3607
3608 if (is_gimple_call (stmt))
3609 {
3610 tree callee = gimple_call_fndecl (stmt);
3611 if (valid_builtin_call (stmt))
3612 switch (DECL_FUNCTION_CODE (callee))
3613 {
3614 case BUILT_IN_STRLEN:
3615 case BUILT_IN_STRNLEN:
3616 handle_builtin_strlen (gsi);
3617 break;
3618 case BUILT_IN_STRCHR:
3619 handle_builtin_strchr (gsi);
3620 break;
3621 case BUILT_IN_STRCPY:
3622 case BUILT_IN_STRCPY_CHK:
3623 case BUILT_IN_STPCPY:
3624 case BUILT_IN_STPCPY_CHK:
3625 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee), gsi);
3626 break;
3627
3628 case BUILT_IN_STRNCAT:
3629 case BUILT_IN_STRNCAT_CHK:
3630 handle_builtin_strncat (DECL_FUNCTION_CODE (callee), gsi);
3631 break;
3632
3633 case BUILT_IN_STPNCPY:
3634 case BUILT_IN_STPNCPY_CHK:
3635 case BUILT_IN_STRNCPY:
3636 case BUILT_IN_STRNCPY_CHK:
3637 handle_builtin_stxncpy (DECL_FUNCTION_CODE (callee), gsi);
3638 break;
3639
3640 case BUILT_IN_MEMCPY:
3641 case BUILT_IN_MEMCPY_CHK:
3642 case BUILT_IN_MEMPCPY:
3643 case BUILT_IN_MEMPCPY_CHK:
3644 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi);
3645 break;
3646 case BUILT_IN_STRCAT:
3647 case BUILT_IN_STRCAT_CHK:
3648 handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi);
3649 break;
3650 case BUILT_IN_MALLOC:
3651 case BUILT_IN_CALLOC:
3652 handle_builtin_malloc (DECL_FUNCTION_CODE (callee), gsi);
3653 break;
3654 case BUILT_IN_MEMSET:
3655 if (handle_builtin_memset (gsi))
3656 return false;
3657 break;
3658 case BUILT_IN_MEMCMP:
3659 if (handle_builtin_memcmp (gsi))
3660 return false;
3661 break;
3662 case BUILT_IN_STRCMP:
3663 case BUILT_IN_STRNCMP:
3664 if (handle_builtin_string_cmp (gsi))
3665 return false;
3666 break;
3667 default:
3668 break;
3669 }
3670 }
3671 else if (is_gimple_assign (stmt) && !gimple_clobber_p (stmt))
3672 {
3673 tree lhs = gimple_assign_lhs (stmt);
3674
3675 if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs)))
3676 {
3677 if (gimple_assign_single_p (stmt)
3678 || (gimple_assign_cast_p (stmt)
3679 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))))
3680 {
3681 int idx = get_stridx (gimple_assign_rhs1 (stmt));
3682 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = idx;
3683 }
3684 else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
3685 handle_pointer_plus (gsi);
3686 }
3687 else if (TREE_CODE (lhs) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
3688 {
3689 enum tree_code code = gimple_assign_rhs_code (stmt);
3690 if (code == COND_EXPR)
3691 {
3692 tree cond = gimple_assign_rhs1 (stmt);
3693 enum tree_code cond_code = TREE_CODE (cond);
3694
3695 if (cond_code == EQ_EXPR || cond_code == NE_EXPR)
3696 fold_strstr_to_strncmp (TREE_OPERAND (cond, 0),
3697 TREE_OPERAND (cond, 1), stmt);
3698 }
3699 else if (code == EQ_EXPR || code == NE_EXPR)
3700 fold_strstr_to_strncmp (gimple_assign_rhs1 (stmt),
3701 gimple_assign_rhs2 (stmt), stmt);
3702 else if (gimple_assign_load_p (stmt)
3703 && TREE_CODE (TREE_TYPE (lhs)) == INTEGER_TYPE
3704 && TYPE_MODE (TREE_TYPE (lhs)) == TYPE_MODE (char_type_node)
3705 && (TYPE_PRECISION (TREE_TYPE (lhs))
3706 == TYPE_PRECISION (char_type_node))
3707 && !gimple_has_volatile_ops (stmt))
3708 {
3709 tree off = integer_zero_node;
3710 unsigned HOST_WIDE_INT coff = 0;
3711 int idx = 0;
3712 tree rhs1 = gimple_assign_rhs1 (stmt);
3713 if (code == MEM_REF)
3714 {
3715 idx = get_stridx (TREE_OPERAND (rhs1, 0));
3716 if (idx > 0)
3717 {
3718 strinfo *si = get_strinfo (idx);
3719 if (si
3720 && si->nonzero_chars
3721 && TREE_CODE (si->nonzero_chars) == INTEGER_CST
3722 && (wi::to_widest (si->nonzero_chars)
3723 >= wi::to_widest (off)))
3724 off = TREE_OPERAND (rhs1, 1);
3725 else
3726 /* This case is not useful. See if get_addr_stridx
3727 returns something usable. */
3728 idx = 0;
3729 }
3730 }
3731 if (idx <= 0)
3732 idx = get_addr_stridx (rhs1, NULL_TREE, &coff);
3733 if (idx > 0)
3734 {
3735 strinfo *si = get_strinfo (idx);
3736 if (si
3737 && si->nonzero_chars
3738 && TREE_CODE (si->nonzero_chars) == INTEGER_CST)
3739 {
3740 widest_int w1 = wi::to_widest (si->nonzero_chars);
3741 widest_int w2 = wi::to_widest (off) + coff;
3742 if (w1 == w2
3743 && si->full_string_p)
3744 {
3745 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
3746 {
3747 fprintf (dump_file, "Optimizing: ");
3748 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
3749 }
3750
3751 /* Reading the final '\0' character. */
3752 tree zero = build_int_cst (TREE_TYPE (lhs), 0);
3753 gimple_set_vuse (stmt, NULL_TREE);
3754 gimple_assign_set_rhs_from_tree (gsi, zero);
3755 *cleanup_eh
3756 |= maybe_clean_or_replace_eh_stmt (stmt,
3757 gsi_stmt (*gsi));
3758 stmt = gsi_stmt (*gsi);
3759 update_stmt (stmt);
3760
3761 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
3762 {
3763 fprintf (dump_file, "into: ");
3764 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
3765 }
3766 }
3767 else if (w1 > w2)
3768 {
3769 /* Reading a character before the final '\0'
3770 character. Just set the value range to ~[0, 0]
3771 if we don't have anything better. */
3772 wide_int min, max;
3773 tree type = TREE_TYPE (lhs);
3774 enum value_range_kind vr
3775 = get_range_info (lhs, &min, &max);
3776 if (vr == VR_VARYING
3777 || (vr == VR_RANGE
3778 && min == wi::min_value (TYPE_PRECISION (type),
3779 TYPE_SIGN (type))
3780 && max == wi::max_value (TYPE_PRECISION (type),
3781 TYPE_SIGN (type))))
3782 set_range_info (lhs, VR_ANTI_RANGE,
3783 wi::zero (TYPE_PRECISION (type)),
3784 wi::zero (TYPE_PRECISION (type)));
3785 }
3786 }
3787 }
3788 }
3789
3790 if (strlen_to_stridx)
3791 {
3792 tree rhs1 = gimple_assign_rhs1 (stmt);
3793 if (stridx_strlenloc *ps = strlen_to_stridx->get (rhs1))
3794 strlen_to_stridx->put (lhs, stridx_strlenloc (*ps));
3795 }
3796 }
3797 else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
3798 {
3799 tree type = TREE_TYPE (lhs);
3800 if (TREE_CODE (type) == ARRAY_TYPE)
3801 type = TREE_TYPE (type);
3802 if (TREE_CODE (type) == INTEGER_TYPE
3803 && TYPE_MODE (type) == TYPE_MODE (char_type_node)
3804 && TYPE_PRECISION (type) == TYPE_PRECISION (char_type_node))
3805 {
3806 if (! handle_char_store (gsi))
3807 return false;
3808 }
3809 }
3810 }
3811 else if (gcond *cond = dyn_cast<gcond *> (stmt))
3812 {
3813 enum tree_code code = gimple_cond_code (cond);
3814 if (code == EQ_EXPR || code == NE_EXPR)
3815 fold_strstr_to_strncmp (gimple_cond_lhs (stmt),
3816 gimple_cond_rhs (stmt), stmt);
3817 }
3818
3819 if (gimple_vdef (stmt))
3820 maybe_invalidate (stmt);
3821 return true;
3822 }
3823
3824 /* Recursively call maybe_invalidate on stmts that might be executed
3825 in between dombb and current bb and that contain a vdef. Stop when
3826 *count stmts are inspected, or if the whole strinfo vector has
3827 been invalidated. */
3828
3829 static void
do_invalidate(basic_block dombb,gimple * phi,bitmap visited,int * count)3830 do_invalidate (basic_block dombb, gimple *phi, bitmap visited, int *count)
3831 {
3832 unsigned int i, n = gimple_phi_num_args (phi);
3833
3834 for (i = 0; i < n; i++)
3835 {
3836 tree vuse = gimple_phi_arg_def (phi, i);
3837 gimple *stmt = SSA_NAME_DEF_STMT (vuse);
3838 basic_block bb = gimple_bb (stmt);
3839 if (bb == NULL
3840 || bb == dombb
3841 || !bitmap_set_bit (visited, bb->index)
3842 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
3843 continue;
3844 while (1)
3845 {
3846 if (gimple_code (stmt) == GIMPLE_PHI)
3847 {
3848 do_invalidate (dombb, stmt, visited, count);
3849 if (*count == 0)
3850 return;
3851 break;
3852 }
3853 if (--*count == 0)
3854 return;
3855 if (!maybe_invalidate (stmt))
3856 {
3857 *count = 0;
3858 return;
3859 }
3860 vuse = gimple_vuse (stmt);
3861 stmt = SSA_NAME_DEF_STMT (vuse);
3862 if (gimple_bb (stmt) != bb)
3863 {
3864 bb = gimple_bb (stmt);
3865 if (bb == NULL
3866 || bb == dombb
3867 || !bitmap_set_bit (visited, bb->index)
3868 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
3869 break;
3870 }
3871 }
3872 }
3873 }
3874
3875 class strlen_dom_walker : public dom_walker
3876 {
3877 public:
strlen_dom_walker(cdi_direction direction)3878 strlen_dom_walker (cdi_direction direction)
3879 : dom_walker (direction), m_cleanup_cfg (false)
3880 {}
3881
3882 virtual edge before_dom_children (basic_block);
3883 virtual void after_dom_children (basic_block);
3884
3885 /* Flag that will trigger TODO_cleanup_cfg to be returned in strlen
3886 execute function. */
3887 bool m_cleanup_cfg;
3888 };
3889
3890 /* Callback for walk_dominator_tree. Attempt to optimize various
3891 string ops by remembering string lengths pointed by pointer SSA_NAMEs. */
3892
3893 edge
before_dom_children(basic_block bb)3894 strlen_dom_walker::before_dom_children (basic_block bb)
3895 {
3896 basic_block dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
3897
3898 if (dombb == NULL)
3899 stridx_to_strinfo = NULL;
3900 else
3901 {
3902 stridx_to_strinfo = ((vec<strinfo *, va_heap, vl_embed> *) dombb->aux);
3903 if (stridx_to_strinfo)
3904 {
3905 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
3906 gsi_next (&gsi))
3907 {
3908 gphi *phi = gsi.phi ();
3909 if (virtual_operand_p (gimple_phi_result (phi)))
3910 {
3911 bitmap visited = BITMAP_ALLOC (NULL);
3912 int count_vdef = 100;
3913 do_invalidate (dombb, phi, visited, &count_vdef);
3914 BITMAP_FREE (visited);
3915 if (count_vdef == 0)
3916 {
3917 /* If there were too many vdefs in between immediate
3918 dominator and current bb, invalidate everything.
3919 If stridx_to_strinfo has been unshared, we need
3920 to free it, otherwise just set it to NULL. */
3921 if (!strinfo_shared ())
3922 {
3923 unsigned int i;
3924 strinfo *si;
3925
3926 for (i = 1;
3927 vec_safe_iterate (stridx_to_strinfo, i, &si);
3928 ++i)
3929 {
3930 free_strinfo (si);
3931 (*stridx_to_strinfo)[i] = NULL;
3932 }
3933 }
3934 else
3935 stridx_to_strinfo = NULL;
3936 }
3937 break;
3938 }
3939 }
3940 }
3941 }
3942
3943 /* If all PHI arguments have the same string index, the PHI result
3944 has it as well. */
3945 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
3946 gsi_next (&gsi))
3947 {
3948 gphi *phi = gsi.phi ();
3949 tree result = gimple_phi_result (phi);
3950 if (!virtual_operand_p (result) && POINTER_TYPE_P (TREE_TYPE (result)))
3951 {
3952 int idx = get_stridx (gimple_phi_arg_def (phi, 0));
3953 if (idx != 0)
3954 {
3955 unsigned int i, n = gimple_phi_num_args (phi);
3956 for (i = 1; i < n; i++)
3957 if (idx != get_stridx (gimple_phi_arg_def (phi, i)))
3958 break;
3959 if (i == n)
3960 ssa_ver_to_stridx[SSA_NAME_VERSION (result)] = idx;
3961 }
3962 }
3963 }
3964
3965 bool cleanup_eh = false;
3966
3967 /* Attempt to optimize individual statements. */
3968 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
3969 if (strlen_check_and_optimize_stmt (&gsi, &cleanup_eh))
3970 gsi_next (&gsi);
3971
3972 if (cleanup_eh && gimple_purge_dead_eh_edges (bb))
3973 m_cleanup_cfg = true;
3974
3975 bb->aux = stridx_to_strinfo;
3976 if (vec_safe_length (stridx_to_strinfo) && !strinfo_shared ())
3977 (*stridx_to_strinfo)[0] = (strinfo *) bb;
3978 return NULL;
3979 }
3980
3981 /* Callback for walk_dominator_tree. Free strinfo vector if it is
3982 owned by the current bb, clear bb->aux. */
3983
3984 void
after_dom_children(basic_block bb)3985 strlen_dom_walker::after_dom_children (basic_block bb)
3986 {
3987 if (bb->aux)
3988 {
3989 stridx_to_strinfo = ((vec<strinfo *, va_heap, vl_embed> *) bb->aux);
3990 if (vec_safe_length (stridx_to_strinfo)
3991 && (*stridx_to_strinfo)[0] == (strinfo *) bb)
3992 {
3993 unsigned int i;
3994 strinfo *si;
3995
3996 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
3997 free_strinfo (si);
3998 vec_free (stridx_to_strinfo);
3999 }
4000 bb->aux = NULL;
4001 }
4002 }
4003
4004 /* Main entry point. */
4005
4006 namespace {
4007
4008 const pass_data pass_data_strlen =
4009 {
4010 GIMPLE_PASS, /* type */
4011 "strlen", /* name */
4012 OPTGROUP_NONE, /* optinfo_flags */
4013 TV_TREE_STRLEN, /* tv_id */
4014 ( PROP_cfg | PROP_ssa ), /* properties_required */
4015 0, /* properties_provided */
4016 0, /* properties_destroyed */
4017 0, /* todo_flags_start */
4018 0, /* todo_flags_finish */
4019 };
4020
4021 class pass_strlen : public gimple_opt_pass
4022 {
4023 public:
pass_strlen(gcc::context * ctxt)4024 pass_strlen (gcc::context *ctxt)
4025 : gimple_opt_pass (pass_data_strlen, ctxt)
4026 {}
4027
4028 /* opt_pass methods: */
gate(function *)4029 virtual bool gate (function *) { return flag_optimize_strlen != 0; }
4030 virtual unsigned int execute (function *);
4031
4032 }; // class pass_strlen
4033
4034 unsigned int
execute(function * fun)4035 pass_strlen::execute (function *fun)
4036 {
4037 gcc_assert (!strlen_to_stridx);
4038 if (warn_stringop_overflow || warn_stringop_truncation)
4039 strlen_to_stridx = new hash_map<tree, stridx_strlenloc> ();
4040
4041 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
4042 max_stridx = 1;
4043
4044 calculate_dominance_info (CDI_DOMINATORS);
4045
4046 /* String length optimization is implemented as a walk of the dominator
4047 tree and a forward walk of statements within each block. */
4048 strlen_dom_walker walker (CDI_DOMINATORS);
4049 walker.walk (fun->cfg->x_entry_block_ptr);
4050
4051 ssa_ver_to_stridx.release ();
4052 strinfo_pool.release ();
4053 if (decl_to_stridxlist_htab)
4054 {
4055 obstack_free (&stridx_obstack, NULL);
4056 delete decl_to_stridxlist_htab;
4057 decl_to_stridxlist_htab = NULL;
4058 }
4059 laststmt.stmt = NULL;
4060 laststmt.len = NULL_TREE;
4061 laststmt.stridx = 0;
4062
4063 if (strlen_to_stridx)
4064 {
4065 strlen_to_stridx->empty ();
4066 delete strlen_to_stridx;
4067 strlen_to_stridx = NULL;
4068 }
4069
4070 return walker.m_cleanup_cfg ? TODO_cleanup_cfg : 0;
4071 }
4072
4073 } // anon namespace
4074
4075 gimple_opt_pass *
make_pass_strlen(gcc::context * ctxt)4076 make_pass_strlen (gcc::context *ctxt)
4077 {
4078 return new pass_strlen (ctxt);
4079 }
4080