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