1 /* String length optimization
2 Copyright (C) 2011-2016 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 "fold-const.h"
34 #include "stor-layout.h"
35 #include "gimple-fold.h"
36 #include "tree-eh.h"
37 #include "gimplify.h"
38 #include "gimple-iterator.h"
39 #include "gimplify-me.h"
40 #include "expr.h"
41 #include "tree-dfa.h"
42 #include "domwalk.h"
43 #include "tree-ssa-propagate.h"
44 #include "params.h"
45 #include "ipa-chkp.h"
46 #include "tree-hash-traits.h"
47
48 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
49 is an index into strinfo vector, negative value stands for
50 string length of a string literal (~strlen). */
51 static vec<int> ssa_ver_to_stridx;
52
53 /* Number of currently active string indexes plus one. */
54 static int max_stridx;
55
56 /* String information record. */
57 struct strinfo
58 {
59 /* String length of this string. */
60 tree length;
61 /* Any of the corresponding pointers for querying alias oracle. */
62 tree ptr;
63 /* Statement for delayed length computation. */
64 gimple *stmt;
65 /* Pointer to '\0' if known, if NULL, it can be computed as
66 ptr + length. */
67 tree endptr;
68 /* Reference count. Any changes to strinfo entry possibly shared
69 with dominating basic blocks need unshare_strinfo first, except
70 for dont_invalidate which affects only the immediately next
71 maybe_invalidate. */
72 int refcount;
73 /* Copy of index. get_strinfo (si->idx) should return si; */
74 int idx;
75 /* These 3 fields are for chaining related string pointers together.
76 E.g. for
77 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
78 strcpy (c, d); e = c + dl;
79 strinfo(a) -> strinfo(c) -> strinfo(e)
80 All have ->first field equal to strinfo(a)->idx and are doubly
81 chained through prev/next fields. The later strinfos are required
82 to point into the same string with zero or more bytes after
83 the previous pointer and all bytes in between the two pointers
84 must be non-zero. Functions like strcpy or memcpy are supposed
85 to adjust all previous strinfo lengths, but not following strinfo
86 lengths (those are uncertain, usually invalidated during
87 maybe_invalidate, except when the alias oracle knows better).
88 Functions like strcat on the other side adjust the whole
89 related strinfo chain.
90 They are updated lazily, so to use the chain the same first fields
91 and si->prev->next == si->idx needs to be verified. */
92 int first;
93 int next;
94 int prev;
95 /* A flag whether the string is known to be written in the current
96 function. */
97 bool writable;
98 /* A flag for the next maybe_invalidate that this strinfo shouldn't
99 be invalidated. Always cleared by maybe_invalidate. */
100 bool dont_invalidate;
101 };
102
103 /* Pool for allocating strinfo_struct entries. */
104 static object_allocator<strinfo> strinfo_pool ("strinfo pool");
105
106 /* Vector mapping positive string indexes to strinfo, for the
107 current basic block. The first pointer in the vector is special,
108 it is either NULL, meaning the vector isn't shared, or it is
109 a basic block pointer to the owner basic_block if shared.
110 If some other bb wants to modify the vector, the vector needs
111 to be unshared first, and only the owner bb is supposed to free it. */
112 static vec<strinfo *, va_heap, vl_embed> *stridx_to_strinfo;
113
114 /* One OFFSET->IDX mapping. */
115 struct stridxlist
116 {
117 struct stridxlist *next;
118 HOST_WIDE_INT offset;
119 int idx;
120 };
121
122 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
123 struct decl_stridxlist_map
124 {
125 struct tree_map_base base;
126 struct stridxlist list;
127 };
128
129 /* Hash table for mapping decls to a chained list of offset -> idx
130 mappings. */
131 static hash_map<tree_decl_hash, stridxlist> *decl_to_stridxlist_htab;
132
133 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
134 static struct obstack stridx_obstack;
135
136 /* Last memcpy statement if it could be adjusted if the trailing
137 '\0' written is immediately overwritten, or
138 *x = '\0' store that could be removed if it is immediately overwritten. */
139 struct laststmt_struct
140 {
141 gimple *stmt;
142 tree len;
143 int stridx;
144 } laststmt;
145
146 static int get_stridx_plus_constant (strinfo *, HOST_WIDE_INT, tree);
147
148 /* Return strinfo vector entry IDX. */
149
150 static inline strinfo *
get_strinfo(int idx)151 get_strinfo (int idx)
152 {
153 if (vec_safe_length (stridx_to_strinfo) <= (unsigned int) idx)
154 return NULL;
155 return (*stridx_to_strinfo)[idx];
156 }
157
158 /* Helper function for get_stridx. */
159
160 static int
get_addr_stridx(tree exp)161 get_addr_stridx (tree exp)
162 {
163 HOST_WIDE_INT off;
164 struct stridxlist *list;
165 tree base;
166
167 if (!decl_to_stridxlist_htab)
168 return 0;
169
170 base = get_addr_base_and_unit_offset (exp, &off);
171 if (base == NULL || !DECL_P (base))
172 return 0;
173
174 list = decl_to_stridxlist_htab->get (base);
175 if (list == NULL)
176 return 0;
177
178 do
179 {
180 if (list->offset == off)
181 return list->idx;
182 list = list->next;
183 }
184 while (list);
185 return 0;
186 }
187
188 /* Return string index for EXP. */
189
190 static int
get_stridx(tree exp)191 get_stridx (tree exp)
192 {
193 tree s, o;
194
195 if (TREE_CODE (exp) == SSA_NAME)
196 {
197 if (ssa_ver_to_stridx[SSA_NAME_VERSION (exp)])
198 return ssa_ver_to_stridx[SSA_NAME_VERSION (exp)];
199 int i;
200 tree e = exp;
201 HOST_WIDE_INT off = 0;
202 for (i = 0; i < 5; i++)
203 {
204 gimple *def_stmt = SSA_NAME_DEF_STMT (e);
205 if (!is_gimple_assign (def_stmt)
206 || gimple_assign_rhs_code (def_stmt) != POINTER_PLUS_EXPR)
207 return 0;
208 tree rhs1 = gimple_assign_rhs1 (def_stmt);
209 tree rhs2 = gimple_assign_rhs2 (def_stmt);
210 if (TREE_CODE (rhs1) != SSA_NAME
211 || !tree_fits_shwi_p (rhs2))
212 return 0;
213 HOST_WIDE_INT this_off = tree_to_shwi (rhs2);
214 if (this_off < 0)
215 return 0;
216 off = (unsigned HOST_WIDE_INT) off + this_off;
217 if (off < 0)
218 return 0;
219 if (ssa_ver_to_stridx[SSA_NAME_VERSION (rhs1)])
220 {
221 strinfo *si
222 = get_strinfo (ssa_ver_to_stridx[SSA_NAME_VERSION (rhs1)]);
223 if (si
224 && si->length
225 && TREE_CODE (si->length) == INTEGER_CST
226 && compare_tree_int (si->length, off) != -1)
227 return get_stridx_plus_constant (si, off, exp);
228 }
229 e = rhs1;
230 }
231 return 0;
232 }
233
234 if (TREE_CODE (exp) == ADDR_EXPR)
235 {
236 int idx = get_addr_stridx (TREE_OPERAND (exp, 0));
237 if (idx != 0)
238 return idx;
239 }
240
241 s = string_constant (exp, &o);
242 if (s != NULL_TREE
243 && (o == NULL_TREE || tree_fits_shwi_p (o))
244 && TREE_STRING_LENGTH (s) > 0)
245 {
246 HOST_WIDE_INT offset = o ? tree_to_shwi (o) : 0;
247 const char *p = TREE_STRING_POINTER (s);
248 int max = TREE_STRING_LENGTH (s) - 1;
249
250 if (p[max] == '\0' && offset >= 0 && offset <= max)
251 return ~(int) strlen (p + offset);
252 }
253 return 0;
254 }
255
256 /* Return true if strinfo vector is shared with the immediate dominator. */
257
258 static inline bool
strinfo_shared(void)259 strinfo_shared (void)
260 {
261 return vec_safe_length (stridx_to_strinfo)
262 && (*stridx_to_strinfo)[0] != NULL;
263 }
264
265 /* Unshare strinfo vector that is shared with the immediate dominator. */
266
267 static void
unshare_strinfo_vec(void)268 unshare_strinfo_vec (void)
269 {
270 strinfo *si;
271 unsigned int i = 0;
272
273 gcc_assert (strinfo_shared ());
274 stridx_to_strinfo = vec_safe_copy (stridx_to_strinfo);
275 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
276 if (si != NULL)
277 si->refcount++;
278 (*stridx_to_strinfo)[0] = NULL;
279 }
280
281 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
282 Return a pointer to the location where the string index can
283 be stored (if 0) or is stored, or NULL if this can't be tracked. */
284
285 static int *
addr_stridxptr(tree exp)286 addr_stridxptr (tree exp)
287 {
288 HOST_WIDE_INT off;
289
290 tree base = get_addr_base_and_unit_offset (exp, &off);
291 if (base == NULL_TREE || !DECL_P (base))
292 return NULL;
293
294 if (!decl_to_stridxlist_htab)
295 {
296 decl_to_stridxlist_htab
297 = new hash_map<tree_decl_hash, stridxlist> (64);
298 gcc_obstack_init (&stridx_obstack);
299 }
300
301 bool existed;
302 stridxlist *list = &decl_to_stridxlist_htab->get_or_insert (base, &existed);
303 if (existed)
304 {
305 int i;
306 for (i = 0; i < 16; i++)
307 {
308 if (list->offset == off)
309 return &list->idx;
310 if (list->next == NULL)
311 break;
312 }
313 if (i == 16)
314 return NULL;
315 list->next = XOBNEW (&stridx_obstack, struct stridxlist);
316 list = list->next;
317 }
318
319 list->next = NULL;
320 list->offset = off;
321 list->idx = 0;
322 return &list->idx;
323 }
324
325 /* Create a new string index, or return 0 if reached limit. */
326
327 static int
new_stridx(tree exp)328 new_stridx (tree exp)
329 {
330 int idx;
331 if (max_stridx >= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS))
332 return 0;
333 if (TREE_CODE (exp) == SSA_NAME)
334 {
335 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp))
336 return 0;
337 idx = max_stridx++;
338 ssa_ver_to_stridx[SSA_NAME_VERSION (exp)] = idx;
339 return idx;
340 }
341 if (TREE_CODE (exp) == ADDR_EXPR)
342 {
343 int *pidx = addr_stridxptr (TREE_OPERAND (exp, 0));
344 if (pidx != NULL)
345 {
346 gcc_assert (*pidx == 0);
347 *pidx = max_stridx++;
348 return *pidx;
349 }
350 }
351 return 0;
352 }
353
354 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
355
356 static int
new_addr_stridx(tree exp)357 new_addr_stridx (tree exp)
358 {
359 int *pidx;
360 if (max_stridx >= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS))
361 return 0;
362 pidx = addr_stridxptr (exp);
363 if (pidx != NULL)
364 {
365 gcc_assert (*pidx == 0);
366 *pidx = max_stridx++;
367 return *pidx;
368 }
369 return 0;
370 }
371
372 /* Create a new strinfo. */
373
374 static strinfo *
new_strinfo(tree ptr,int idx,tree length)375 new_strinfo (tree ptr, int idx, tree length)
376 {
377 strinfo *si = strinfo_pool.allocate ();
378 si->length = length;
379 si->ptr = ptr;
380 si->stmt = NULL;
381 si->endptr = NULL_TREE;
382 si->refcount = 1;
383 si->idx = idx;
384 si->first = 0;
385 si->prev = 0;
386 si->next = 0;
387 si->writable = false;
388 si->dont_invalidate = false;
389 return si;
390 }
391
392 /* Decrease strinfo refcount and free it if not referenced anymore. */
393
394 static inline void
free_strinfo(strinfo * si)395 free_strinfo (strinfo *si)
396 {
397 if (si && --si->refcount == 0)
398 strinfo_pool.remove (si);
399 }
400
401 /* Set strinfo in the vector entry IDX to SI. */
402
403 static inline void
set_strinfo(int idx,strinfo * si)404 set_strinfo (int idx, strinfo *si)
405 {
406 if (vec_safe_length (stridx_to_strinfo) && (*stridx_to_strinfo)[0])
407 unshare_strinfo_vec ();
408 if (vec_safe_length (stridx_to_strinfo) <= (unsigned int) idx)
409 vec_safe_grow_cleared (stridx_to_strinfo, idx + 1);
410 (*stridx_to_strinfo)[idx] = si;
411 }
412
413 /* Return string length, or NULL if it can't be computed. */
414
415 static tree
get_string_length(strinfo * si)416 get_string_length (strinfo *si)
417 {
418 if (si->length)
419 return si->length;
420
421 if (si->stmt)
422 {
423 gimple *stmt = si->stmt, *lenstmt;
424 bool with_bounds = gimple_call_with_bounds_p (stmt);
425 tree callee, lhs, fn, tem;
426 location_t loc;
427 gimple_stmt_iterator gsi;
428
429 gcc_assert (is_gimple_call (stmt));
430 callee = gimple_call_fndecl (stmt);
431 gcc_assert (callee && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL);
432 lhs = gimple_call_lhs (stmt);
433 /* unshare_strinfo is intentionally not called here. The (delayed)
434 transformation of strcpy or strcat into stpcpy is done at the place
435 of the former strcpy/strcat call and so can affect all the strinfos
436 with the same stmt. If they were unshared before and transformation
437 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
438 just compute the right length. */
439 switch (DECL_FUNCTION_CODE (callee))
440 {
441 case BUILT_IN_STRCAT:
442 case BUILT_IN_STRCAT_CHK:
443 case BUILT_IN_STRCAT_CHKP:
444 case BUILT_IN_STRCAT_CHK_CHKP:
445 gsi = gsi_for_stmt (stmt);
446 fn = builtin_decl_implicit (BUILT_IN_STRLEN);
447 gcc_assert (lhs == NULL_TREE);
448 tem = unshare_expr (gimple_call_arg (stmt, 0));
449 if (with_bounds)
450 {
451 lenstmt = gimple_build_call (chkp_maybe_create_clone (fn)->decl,
452 2, tem, gimple_call_arg (stmt, 1));
453 gimple_call_set_with_bounds (lenstmt, true);
454 }
455 else
456 lenstmt = gimple_build_call (fn, 1, tem);
457 lhs = make_ssa_name (TREE_TYPE (TREE_TYPE (fn)), lenstmt);
458 gimple_call_set_lhs (lenstmt, lhs);
459 gimple_set_vuse (lenstmt, gimple_vuse (stmt));
460 gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT);
461 tem = gimple_call_arg (stmt, 0);
462 if (!ptrofftype_p (TREE_TYPE (lhs)))
463 {
464 lhs = convert_to_ptrofftype (lhs);
465 lhs = force_gimple_operand_gsi (&gsi, lhs, true, NULL_TREE,
466 true, GSI_SAME_STMT);
467 }
468 lenstmt = gimple_build_assign
469 (make_ssa_name (TREE_TYPE (gimple_call_arg (stmt, 0))),
470 POINTER_PLUS_EXPR,tem, lhs);
471 gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT);
472 gimple_call_set_arg (stmt, 0, gimple_assign_lhs (lenstmt));
473 lhs = NULL_TREE;
474 /* FALLTHRU */
475 case BUILT_IN_STRCPY:
476 case BUILT_IN_STRCPY_CHK:
477 case BUILT_IN_STRCPY_CHKP:
478 case BUILT_IN_STRCPY_CHK_CHKP:
479 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY));
480 if (gimple_call_num_args (stmt) == (with_bounds ? 4 : 2))
481 fn = builtin_decl_implicit (BUILT_IN_STPCPY);
482 else
483 fn = builtin_decl_explicit (BUILT_IN_STPCPY_CHK);
484 if (with_bounds)
485 fn = chkp_maybe_create_clone (fn)->decl;
486 gcc_assert (lhs == NULL_TREE);
487 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
488 {
489 fprintf (dump_file, "Optimizing: ");
490 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
491 }
492 gimple_call_set_fndecl (stmt, fn);
493 lhs = make_ssa_name (TREE_TYPE (TREE_TYPE (fn)), stmt);
494 gimple_call_set_lhs (stmt, lhs);
495 update_stmt (stmt);
496 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
497 {
498 fprintf (dump_file, "into: ");
499 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
500 }
501 /* FALLTHRU */
502 case BUILT_IN_STPCPY:
503 case BUILT_IN_STPCPY_CHK:
504 case BUILT_IN_STPCPY_CHKP:
505 case BUILT_IN_STPCPY_CHK_CHKP:
506 gcc_assert (lhs != NULL_TREE);
507 loc = gimple_location (stmt);
508 si->endptr = lhs;
509 si->stmt = NULL;
510 lhs = fold_convert_loc (loc, size_type_node, lhs);
511 si->length = fold_convert_loc (loc, size_type_node, si->ptr);
512 si->length = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
513 lhs, si->length);
514 break;
515 case BUILT_IN_MALLOC:
516 break;
517 /* BUILT_IN_CALLOC always has si->length set. */
518 default:
519 gcc_unreachable ();
520 break;
521 }
522 }
523
524 return si->length;
525 }
526
527 /* Invalidate string length information for strings whose length
528 might change due to stores in stmt. */
529
530 static bool
maybe_invalidate(gimple * stmt)531 maybe_invalidate (gimple *stmt)
532 {
533 strinfo *si;
534 unsigned int i;
535 bool nonempty = false;
536
537 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
538 if (si != NULL)
539 {
540 if (!si->dont_invalidate)
541 {
542 ao_ref r;
543 /* Do not use si->length. */
544 ao_ref_init_from_ptr_and_size (&r, si->ptr, NULL_TREE);
545 if (stmt_may_clobber_ref_p_1 (stmt, &r))
546 {
547 set_strinfo (i, NULL);
548 free_strinfo (si);
549 continue;
550 }
551 }
552 si->dont_invalidate = false;
553 nonempty = true;
554 }
555 return nonempty;
556 }
557
558 /* Unshare strinfo record SI, if it has refcount > 1 or
559 if stridx_to_strinfo vector is shared with some other
560 bbs. */
561
562 static strinfo *
unshare_strinfo(strinfo * si)563 unshare_strinfo (strinfo *si)
564 {
565 strinfo *nsi;
566
567 if (si->refcount == 1 && !strinfo_shared ())
568 return si;
569
570 nsi = new_strinfo (si->ptr, si->idx, si->length);
571 nsi->stmt = si->stmt;
572 nsi->endptr = si->endptr;
573 nsi->first = si->first;
574 nsi->prev = si->prev;
575 nsi->next = si->next;
576 nsi->writable = si->writable;
577 set_strinfo (si->idx, nsi);
578 free_strinfo (si);
579 return nsi;
580 }
581
582 /* Return first strinfo in the related strinfo chain
583 if all strinfos in between belong to the chain, otherwise
584 NULL. */
585
586 static strinfo *
verify_related_strinfos(strinfo * origsi)587 verify_related_strinfos (strinfo *origsi)
588 {
589 strinfo *si = origsi, *psi;
590
591 if (origsi->first == 0)
592 return NULL;
593 for (; si->prev; si = psi)
594 {
595 if (si->first != origsi->first)
596 return NULL;
597 psi = get_strinfo (si->prev);
598 if (psi == NULL)
599 return NULL;
600 if (psi->next != si->idx)
601 return NULL;
602 }
603 if (si->idx != si->first)
604 return NULL;
605 return si;
606 }
607
608 /* Attempt to create a new strinfo for BASESI + OFF, or find existing
609 strinfo if there is any. Return it's idx, or 0 if no strinfo has
610 been created. */
611
612 static int
get_stridx_plus_constant(strinfo * basesi,HOST_WIDE_INT off,tree ptr)613 get_stridx_plus_constant (strinfo *basesi, HOST_WIDE_INT off, tree ptr)
614 {
615 gcc_checking_assert (TREE_CODE (ptr) == SSA_NAME);
616
617 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
618 return 0;
619
620 if (basesi->length == NULL_TREE
621 || TREE_CODE (basesi->length) != INTEGER_CST
622 || compare_tree_int (basesi->length, off) == -1
623 || !tree_fits_shwi_p (basesi->length))
624 return 0;
625
626 HOST_WIDE_INT len = tree_to_shwi (basesi->length) - off;
627 strinfo *si = basesi, *chainsi;
628 if (si->first || si->prev || si->next)
629 si = verify_related_strinfos (basesi);
630 if (si == NULL
631 || si->length == NULL_TREE
632 || TREE_CODE (si->length) != INTEGER_CST)
633 return 0;
634
635 if (ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
636 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
637
638 gcc_checking_assert (compare_tree_int (si->length, off) != -1);
639 for (chainsi = si; chainsi->next; chainsi = si)
640 {
641 si = get_strinfo (chainsi->next);
642 if (si == NULL
643 || si->first != chainsi->first
644 || si->prev != chainsi->idx
645 || si->length == NULL_TREE
646 || TREE_CODE (si->length) != INTEGER_CST)
647 break;
648 int r = compare_tree_int (si->length, len);
649 if (r != 1)
650 {
651 if (r == 0)
652 {
653 ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = si->idx;
654 return si->idx;
655 }
656 break;
657 }
658 }
659
660 int idx = new_stridx (ptr);
661 if (idx == 0)
662 return 0;
663 si = new_strinfo (ptr, idx, build_int_cst (size_type_node, len));
664 set_strinfo (idx, si);
665 if (chainsi->next)
666 {
667 strinfo *nextsi = unshare_strinfo (get_strinfo (chainsi->next));
668 si->next = nextsi->idx;
669 nextsi->prev = idx;
670 }
671 chainsi = unshare_strinfo (chainsi);
672 if (chainsi->first == 0)
673 chainsi->first = chainsi->idx;
674 chainsi->next = idx;
675 if (chainsi->endptr == NULL_TREE && len == 0)
676 chainsi->endptr = ptr;
677 si->endptr = chainsi->endptr;
678 si->prev = chainsi->idx;
679 si->first = chainsi->first;
680 si->writable = chainsi->writable;
681 return si->idx;
682 }
683
684 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
685 to a zero-length string and if possible chain it to a related strinfo
686 chain whose part is or might be CHAINSI. */
687
688 static strinfo *
zero_length_string(tree ptr,strinfo * chainsi)689 zero_length_string (tree ptr, strinfo *chainsi)
690 {
691 strinfo *si;
692 int idx;
693 if (ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
694 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
695 gcc_checking_assert (TREE_CODE (ptr) == SSA_NAME
696 && ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] == 0);
697
698 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
699 return NULL;
700 if (chainsi != NULL)
701 {
702 si = verify_related_strinfos (chainsi);
703 if (si)
704 {
705 chainsi = si;
706 for (; chainsi->next; chainsi = si)
707 {
708 if (chainsi->endptr == NULL_TREE)
709 {
710 chainsi = unshare_strinfo (chainsi);
711 chainsi->endptr = ptr;
712 }
713 si = get_strinfo (chainsi->next);
714 if (si == NULL
715 || si->first != chainsi->first
716 || si->prev != chainsi->idx)
717 break;
718 }
719 gcc_assert (chainsi->length || chainsi->stmt);
720 if (chainsi->endptr == NULL_TREE)
721 {
722 chainsi = unshare_strinfo (chainsi);
723 chainsi->endptr = ptr;
724 }
725 if (chainsi->length && integer_zerop (chainsi->length))
726 {
727 if (chainsi->next)
728 {
729 chainsi = unshare_strinfo (chainsi);
730 chainsi->next = 0;
731 }
732 ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = chainsi->idx;
733 return chainsi;
734 }
735 }
736 else if (chainsi->first || chainsi->prev || chainsi->next)
737 {
738 chainsi = unshare_strinfo (chainsi);
739 chainsi->first = 0;
740 chainsi->prev = 0;
741 chainsi->next = 0;
742 }
743 }
744 idx = new_stridx (ptr);
745 if (idx == 0)
746 return NULL;
747 si = new_strinfo (ptr, idx, build_int_cst (size_type_node, 0));
748 set_strinfo (idx, si);
749 si->endptr = ptr;
750 if (chainsi != NULL)
751 {
752 chainsi = unshare_strinfo (chainsi);
753 if (chainsi->first == 0)
754 chainsi->first = chainsi->idx;
755 chainsi->next = idx;
756 if (chainsi->endptr == NULL_TREE)
757 chainsi->endptr = ptr;
758 si->prev = chainsi->idx;
759 si->first = chainsi->first;
760 si->writable = chainsi->writable;
761 }
762 return si;
763 }
764
765 /* For strinfo ORIGSI whose length has been just updated
766 update also related strinfo lengths (add ADJ to each,
767 but don't adjust ORIGSI). */
768
769 static void
adjust_related_strinfos(location_t loc,strinfo * origsi,tree adj)770 adjust_related_strinfos (location_t loc, strinfo *origsi, tree adj)
771 {
772 strinfo *si = verify_related_strinfos (origsi);
773
774 if (si == NULL)
775 return;
776
777 while (1)
778 {
779 strinfo *nsi;
780
781 if (si != origsi)
782 {
783 tree tem;
784
785 si = unshare_strinfo (si);
786 if (si->length)
787 {
788 tem = fold_convert_loc (loc, TREE_TYPE (si->length), adj);
789 si->length = fold_build2_loc (loc, PLUS_EXPR,
790 TREE_TYPE (si->length), si->length,
791 tem);
792 }
793 else if (si->stmt != NULL)
794 /* Delayed length computation is unaffected. */
795 ;
796 else
797 gcc_unreachable ();
798
799 si->endptr = NULL_TREE;
800 si->dont_invalidate = true;
801 }
802 if (si->next == 0)
803 return;
804 nsi = get_strinfo (si->next);
805 if (nsi == NULL
806 || nsi->first != si->first
807 || nsi->prev != si->idx)
808 return;
809 si = nsi;
810 }
811 }
812
813 /* Find if there are other SSA_NAME pointers equal to PTR
814 for which we don't track their string lengths yet. If so, use
815 IDX for them. */
816
817 static void
find_equal_ptrs(tree ptr,int idx)818 find_equal_ptrs (tree ptr, int idx)
819 {
820 if (TREE_CODE (ptr) != SSA_NAME)
821 return;
822 while (1)
823 {
824 gimple *stmt = SSA_NAME_DEF_STMT (ptr);
825 if (!is_gimple_assign (stmt))
826 return;
827 ptr = gimple_assign_rhs1 (stmt);
828 switch (gimple_assign_rhs_code (stmt))
829 {
830 case SSA_NAME:
831 break;
832 CASE_CONVERT:
833 if (!POINTER_TYPE_P (TREE_TYPE (ptr)))
834 return;
835 if (TREE_CODE (ptr) == SSA_NAME)
836 break;
837 if (TREE_CODE (ptr) != ADDR_EXPR)
838 return;
839 /* FALLTHRU */
840 case ADDR_EXPR:
841 {
842 int *pidx = addr_stridxptr (TREE_OPERAND (ptr, 0));
843 if (pidx != NULL && *pidx == 0)
844 *pidx = idx;
845 return;
846 }
847 default:
848 return;
849 }
850
851 /* We might find an endptr created in this pass. Grow the
852 vector in that case. */
853 if (ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
854 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
855
856 if (ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] != 0)
857 return;
858 ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = idx;
859 }
860 }
861
862 /* Return true if STMT is a call to a builtin function with the right
863 arguments and attributes that should be considered for optimization
864 by this pass. */
865
866 static bool
valid_builtin_call(gimple * stmt)867 valid_builtin_call (gimple *stmt)
868 {
869 if (!gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
870 return false;
871
872 tree callee = gimple_call_fndecl (stmt);
873 switch (DECL_FUNCTION_CODE (callee))
874 {
875 case BUILT_IN_MEMCMP:
876 case BUILT_IN_STRCHR:
877 case BUILT_IN_STRCHR_CHKP:
878 case BUILT_IN_STRLEN:
879 case BUILT_IN_STRLEN_CHKP:
880 /* The above functions should be pure. Punt if they aren't. */
881 if (gimple_vdef (stmt) || gimple_vuse (stmt) == NULL_TREE)
882 return false;
883 break;
884
885 case BUILT_IN_CALLOC:
886 case BUILT_IN_MALLOC:
887 case BUILT_IN_MEMCPY:
888 case BUILT_IN_MEMCPY_CHK:
889 case BUILT_IN_MEMCPY_CHKP:
890 case BUILT_IN_MEMCPY_CHK_CHKP:
891 case BUILT_IN_MEMPCPY:
892 case BUILT_IN_MEMPCPY_CHK:
893 case BUILT_IN_MEMPCPY_CHKP:
894 case BUILT_IN_MEMPCPY_CHK_CHKP:
895 case BUILT_IN_MEMSET:
896 case BUILT_IN_STPCPY:
897 case BUILT_IN_STPCPY_CHK:
898 case BUILT_IN_STPCPY_CHKP:
899 case BUILT_IN_STPCPY_CHK_CHKP:
900 case BUILT_IN_STRCAT:
901 case BUILT_IN_STRCAT_CHK:
902 case BUILT_IN_STRCAT_CHKP:
903 case BUILT_IN_STRCAT_CHK_CHKP:
904 case BUILT_IN_STRCPY:
905 case BUILT_IN_STRCPY_CHK:
906 case BUILT_IN_STRCPY_CHKP:
907 case BUILT_IN_STRCPY_CHK_CHKP:
908 /* The above functions should be neither const nor pure. Punt if they
909 aren't. */
910 if (gimple_vdef (stmt) == NULL_TREE || gimple_vuse (stmt) == NULL_TREE)
911 return false;
912 break;
913
914 default:
915 break;
916 }
917
918 return true;
919 }
920
921 /* If the last .MEM setter statement before STMT is
922 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
923 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
924 just memcpy (x, y, strlen (y)). SI must be the zero length
925 strinfo. */
926
927 static void
adjust_last_stmt(strinfo * si,gimple * stmt,bool is_strcat)928 adjust_last_stmt (strinfo *si, gimple *stmt, bool is_strcat)
929 {
930 tree vuse, callee, len;
931 struct laststmt_struct last = laststmt;
932 strinfo *lastsi, *firstsi;
933 unsigned len_arg_no = 2;
934
935 laststmt.stmt = NULL;
936 laststmt.len = NULL_TREE;
937 laststmt.stridx = 0;
938
939 if (last.stmt == NULL)
940 return;
941
942 vuse = gimple_vuse (stmt);
943 if (vuse == NULL_TREE
944 || SSA_NAME_DEF_STMT (vuse) != last.stmt
945 || !has_single_use (vuse))
946 return;
947
948 gcc_assert (last.stridx > 0);
949 lastsi = get_strinfo (last.stridx);
950 if (lastsi == NULL)
951 return;
952
953 if (lastsi != si)
954 {
955 if (lastsi->first == 0 || lastsi->first != si->first)
956 return;
957
958 firstsi = verify_related_strinfos (si);
959 if (firstsi == NULL)
960 return;
961 while (firstsi != lastsi)
962 {
963 strinfo *nextsi;
964 if (firstsi->next == 0)
965 return;
966 nextsi = get_strinfo (firstsi->next);
967 if (nextsi == NULL
968 || nextsi->prev != firstsi->idx
969 || nextsi->first != si->first)
970 return;
971 firstsi = nextsi;
972 }
973 }
974
975 if (!is_strcat)
976 {
977 if (si->length == NULL_TREE || !integer_zerop (si->length))
978 return;
979 }
980
981 if (is_gimple_assign (last.stmt))
982 {
983 gimple_stmt_iterator gsi;
984
985 if (!integer_zerop (gimple_assign_rhs1 (last.stmt)))
986 return;
987 if (stmt_could_throw_p (last.stmt))
988 return;
989 gsi = gsi_for_stmt (last.stmt);
990 unlink_stmt_vdef (last.stmt);
991 release_defs (last.stmt);
992 gsi_remove (&gsi, true);
993 return;
994 }
995
996 if (!valid_builtin_call (last.stmt))
997 return;
998
999 callee = gimple_call_fndecl (last.stmt);
1000 switch (DECL_FUNCTION_CODE (callee))
1001 {
1002 case BUILT_IN_MEMCPY:
1003 case BUILT_IN_MEMCPY_CHK:
1004 break;
1005 case BUILT_IN_MEMCPY_CHKP:
1006 case BUILT_IN_MEMCPY_CHK_CHKP:
1007 len_arg_no = 4;
1008 break;
1009 default:
1010 return;
1011 }
1012
1013 len = gimple_call_arg (last.stmt, len_arg_no);
1014 if (tree_fits_uhwi_p (len))
1015 {
1016 if (!tree_fits_uhwi_p (last.len)
1017 || integer_zerop (len)
1018 || tree_to_uhwi (len) != tree_to_uhwi (last.len) + 1)
1019 return;
1020 /* Don't adjust the length if it is divisible by 4, it is more efficient
1021 to store the extra '\0' in that case. */
1022 if ((tree_to_uhwi (len) & 3) == 0)
1023 return;
1024 }
1025 else if (TREE_CODE (len) == SSA_NAME)
1026 {
1027 gimple *def_stmt = SSA_NAME_DEF_STMT (len);
1028 if (!is_gimple_assign (def_stmt)
1029 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
1030 || gimple_assign_rhs1 (def_stmt) != last.len
1031 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
1032 return;
1033 }
1034 else
1035 return;
1036
1037 gimple_call_set_arg (last.stmt, len_arg_no, last.len);
1038 update_stmt (last.stmt);
1039 }
1040
1041 /* Handle a strlen call. If strlen of the argument is known, replace
1042 the strlen call with the known value, otherwise remember that strlen
1043 of the argument is stored in the lhs SSA_NAME. */
1044
1045 static void
handle_builtin_strlen(gimple_stmt_iterator * gsi)1046 handle_builtin_strlen (gimple_stmt_iterator *gsi)
1047 {
1048 int idx;
1049 tree src;
1050 gimple *stmt = gsi_stmt (*gsi);
1051 tree lhs = gimple_call_lhs (stmt);
1052
1053 if (lhs == NULL_TREE)
1054 return;
1055
1056 src = gimple_call_arg (stmt, 0);
1057 idx = get_stridx (src);
1058 if (idx)
1059 {
1060 strinfo *si = NULL;
1061 tree rhs;
1062
1063 if (idx < 0)
1064 rhs = build_int_cst (TREE_TYPE (lhs), ~idx);
1065 else
1066 {
1067 rhs = NULL_TREE;
1068 si = get_strinfo (idx);
1069 if (si != NULL)
1070 rhs = get_string_length (si);
1071 }
1072 if (rhs != NULL_TREE)
1073 {
1074 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1075 {
1076 fprintf (dump_file, "Optimizing: ");
1077 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1078 }
1079 rhs = unshare_expr (rhs);
1080 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
1081 rhs = fold_convert_loc (gimple_location (stmt),
1082 TREE_TYPE (lhs), rhs);
1083 if (!update_call_from_tree (gsi, rhs))
1084 gimplify_and_update_call_from_tree (gsi, rhs);
1085 stmt = gsi_stmt (*gsi);
1086 update_stmt (stmt);
1087 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1088 {
1089 fprintf (dump_file, "into: ");
1090 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1091 }
1092 if (si != NULL
1093 && TREE_CODE (si->length) != SSA_NAME
1094 && TREE_CODE (si->length) != INTEGER_CST
1095 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1096 {
1097 si = unshare_strinfo (si);
1098 si->length = lhs;
1099 }
1100 return;
1101 }
1102 }
1103 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1104 return;
1105 if (idx == 0)
1106 idx = new_stridx (src);
1107 else if (get_strinfo (idx) != NULL)
1108 return;
1109 if (idx)
1110 {
1111 strinfo *si = new_strinfo (src, idx, lhs);
1112 set_strinfo (idx, si);
1113 find_equal_ptrs (src, idx);
1114 }
1115 }
1116
1117 /* Handle a strchr call. If strlen of the first argument is known, replace
1118 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
1119 that lhs of the call is endptr and strlen of the argument is endptr - x. */
1120
1121 static void
handle_builtin_strchr(gimple_stmt_iterator * gsi)1122 handle_builtin_strchr (gimple_stmt_iterator *gsi)
1123 {
1124 int idx;
1125 tree src;
1126 gimple *stmt = gsi_stmt (*gsi);
1127 tree lhs = gimple_call_lhs (stmt);
1128 bool with_bounds = gimple_call_with_bounds_p (stmt);
1129
1130 if (lhs == NULL_TREE)
1131 return;
1132
1133 if (!integer_zerop (gimple_call_arg (stmt, with_bounds ? 2 : 1)))
1134 return;
1135
1136 src = gimple_call_arg (stmt, 0);
1137 idx = get_stridx (src);
1138 if (idx)
1139 {
1140 strinfo *si = NULL;
1141 tree rhs;
1142
1143 if (idx < 0)
1144 rhs = build_int_cst (size_type_node, ~idx);
1145 else
1146 {
1147 rhs = NULL_TREE;
1148 si = get_strinfo (idx);
1149 if (si != NULL)
1150 rhs = get_string_length (si);
1151 }
1152 if (rhs != NULL_TREE)
1153 {
1154 location_t loc = gimple_location (stmt);
1155
1156 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1157 {
1158 fprintf (dump_file, "Optimizing: ");
1159 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1160 }
1161 if (si != NULL && si->endptr != NULL_TREE)
1162 {
1163 rhs = unshare_expr (si->endptr);
1164 if (!useless_type_conversion_p (TREE_TYPE (lhs),
1165 TREE_TYPE (rhs)))
1166 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
1167 }
1168 else
1169 {
1170 rhs = fold_convert_loc (loc, sizetype, unshare_expr (rhs));
1171 rhs = fold_build2_loc (loc, POINTER_PLUS_EXPR,
1172 TREE_TYPE (src), src, rhs);
1173 if (!useless_type_conversion_p (TREE_TYPE (lhs),
1174 TREE_TYPE (rhs)))
1175 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
1176 }
1177 if (!update_call_from_tree (gsi, rhs))
1178 gimplify_and_update_call_from_tree (gsi, rhs);
1179 stmt = gsi_stmt (*gsi);
1180 update_stmt (stmt);
1181 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1182 {
1183 fprintf (dump_file, "into: ");
1184 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1185 }
1186 if (si != NULL
1187 && si->endptr == NULL_TREE
1188 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1189 {
1190 si = unshare_strinfo (si);
1191 si->endptr = lhs;
1192 }
1193 zero_length_string (lhs, si);
1194 return;
1195 }
1196 }
1197 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1198 return;
1199 if (TREE_CODE (src) != SSA_NAME || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src))
1200 {
1201 if (idx == 0)
1202 idx = new_stridx (src);
1203 else if (get_strinfo (idx) != NULL)
1204 {
1205 zero_length_string (lhs, NULL);
1206 return;
1207 }
1208 if (idx)
1209 {
1210 location_t loc = gimple_location (stmt);
1211 tree lhsu = fold_convert_loc (loc, size_type_node, lhs);
1212 tree srcu = fold_convert_loc (loc, size_type_node, src);
1213 tree length = fold_build2_loc (loc, MINUS_EXPR,
1214 size_type_node, lhsu, srcu);
1215 strinfo *si = new_strinfo (src, idx, length);
1216 si->endptr = lhs;
1217 set_strinfo (idx, si);
1218 find_equal_ptrs (src, idx);
1219 zero_length_string (lhs, si);
1220 }
1221 }
1222 else
1223 zero_length_string (lhs, NULL);
1224 }
1225
1226 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1227 If strlen of the second argument is known, strlen of the first argument
1228 is the same after this call. Furthermore, attempt to convert it to
1229 memcpy. */
1230
1231 static void
handle_builtin_strcpy(enum built_in_function bcode,gimple_stmt_iterator * gsi)1232 handle_builtin_strcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1233 {
1234 int idx, didx;
1235 tree src, dst, srclen, len, lhs, args, type, fn, oldlen;
1236 bool success;
1237 gimple *stmt = gsi_stmt (*gsi);
1238 strinfo *si, *dsi, *olddsi, *zsi;
1239 location_t loc;
1240 bool with_bounds = gimple_call_with_bounds_p (stmt);
1241
1242 src = gimple_call_arg (stmt, with_bounds ? 2 : 1);
1243 dst = gimple_call_arg (stmt, 0);
1244 lhs = gimple_call_lhs (stmt);
1245 idx = get_stridx (src);
1246 si = NULL;
1247 if (idx > 0)
1248 si = get_strinfo (idx);
1249
1250 didx = get_stridx (dst);
1251 olddsi = NULL;
1252 oldlen = NULL_TREE;
1253 if (didx > 0)
1254 olddsi = get_strinfo (didx);
1255 else if (didx < 0)
1256 return;
1257
1258 if (olddsi != NULL)
1259 adjust_last_stmt (olddsi, stmt, false);
1260
1261 srclen = NULL_TREE;
1262 if (si != NULL)
1263 srclen = get_string_length (si);
1264 else if (idx < 0)
1265 srclen = build_int_cst (size_type_node, ~idx);
1266
1267 loc = gimple_location (stmt);
1268 if (srclen == NULL_TREE)
1269 switch (bcode)
1270 {
1271 case BUILT_IN_STRCPY:
1272 case BUILT_IN_STRCPY_CHK:
1273 case BUILT_IN_STRCPY_CHKP:
1274 case BUILT_IN_STRCPY_CHK_CHKP:
1275 if (lhs != NULL_TREE || !builtin_decl_implicit_p (BUILT_IN_STPCPY))
1276 return;
1277 break;
1278 case BUILT_IN_STPCPY:
1279 case BUILT_IN_STPCPY_CHK:
1280 case BUILT_IN_STPCPY_CHKP:
1281 case BUILT_IN_STPCPY_CHK_CHKP:
1282 if (lhs == NULL_TREE)
1283 return;
1284 else
1285 {
1286 tree lhsuint = fold_convert_loc (loc, size_type_node, lhs);
1287 srclen = fold_convert_loc (loc, size_type_node, dst);
1288 srclen = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
1289 lhsuint, srclen);
1290 }
1291 break;
1292 default:
1293 gcc_unreachable ();
1294 }
1295
1296 if (didx == 0)
1297 {
1298 didx = new_stridx (dst);
1299 if (didx == 0)
1300 return;
1301 }
1302 if (olddsi != NULL)
1303 {
1304 oldlen = olddsi->length;
1305 dsi = unshare_strinfo (olddsi);
1306 dsi->length = srclen;
1307 /* Break the chain, so adjust_related_strinfo on later pointers in
1308 the chain won't adjust this one anymore. */
1309 dsi->next = 0;
1310 dsi->stmt = NULL;
1311 dsi->endptr = NULL_TREE;
1312 }
1313 else
1314 {
1315 dsi = new_strinfo (dst, didx, srclen);
1316 set_strinfo (didx, dsi);
1317 find_equal_ptrs (dst, didx);
1318 }
1319 dsi->writable = true;
1320 dsi->dont_invalidate = true;
1321
1322 if (dsi->length == NULL_TREE)
1323 {
1324 strinfo *chainsi;
1325
1326 /* If string length of src is unknown, use delayed length
1327 computation. If string lenth of dst will be needed, it
1328 can be computed by transforming this strcpy call into
1329 stpcpy and subtracting dst from the return value. */
1330
1331 /* Look for earlier strings whose length could be determined if
1332 this strcpy is turned into an stpcpy. */
1333
1334 if (dsi->prev != 0 && (chainsi = verify_related_strinfos (dsi)) != NULL)
1335 {
1336 for (; chainsi && chainsi != dsi; chainsi = get_strinfo (chainsi->next))
1337 {
1338 /* When setting a stmt for delayed length computation
1339 prevent all strinfos through dsi from being
1340 invalidated. */
1341 chainsi = unshare_strinfo (chainsi);
1342 chainsi->stmt = stmt;
1343 chainsi->length = NULL_TREE;
1344 chainsi->endptr = NULL_TREE;
1345 chainsi->dont_invalidate = true;
1346 }
1347 }
1348 dsi->stmt = stmt;
1349 return;
1350 }
1351
1352 if (olddsi != NULL)
1353 {
1354 tree adj = NULL_TREE;
1355 if (oldlen == NULL_TREE)
1356 ;
1357 else if (integer_zerop (oldlen))
1358 adj = srclen;
1359 else if (TREE_CODE (oldlen) == INTEGER_CST
1360 || TREE_CODE (srclen) == INTEGER_CST)
1361 adj = fold_build2_loc (loc, MINUS_EXPR,
1362 TREE_TYPE (srclen), srclen,
1363 fold_convert_loc (loc, TREE_TYPE (srclen),
1364 oldlen));
1365 if (adj != NULL_TREE)
1366 adjust_related_strinfos (loc, dsi, adj);
1367 else
1368 dsi->prev = 0;
1369 }
1370 /* strcpy src may not overlap dst, so src doesn't need to be
1371 invalidated either. */
1372 if (si != NULL)
1373 si->dont_invalidate = true;
1374
1375 fn = NULL_TREE;
1376 zsi = NULL;
1377 switch (bcode)
1378 {
1379 case BUILT_IN_STRCPY:
1380 case BUILT_IN_STRCPY_CHKP:
1381 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1382 if (lhs)
1383 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
1384 break;
1385 case BUILT_IN_STRCPY_CHK:
1386 case BUILT_IN_STRCPY_CHK_CHKP:
1387 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK);
1388 if (lhs)
1389 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
1390 break;
1391 case BUILT_IN_STPCPY:
1392 case BUILT_IN_STPCPY_CHKP:
1393 /* This would need adjustment of the lhs (subtract one),
1394 or detection that the trailing '\0' doesn't need to be
1395 written, if it will be immediately overwritten.
1396 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1397 if (lhs)
1398 {
1399 dsi->endptr = lhs;
1400 zsi = zero_length_string (lhs, dsi);
1401 }
1402 break;
1403 case BUILT_IN_STPCPY_CHK:
1404 case BUILT_IN_STPCPY_CHK_CHKP:
1405 /* This would need adjustment of the lhs (subtract one),
1406 or detection that the trailing '\0' doesn't need to be
1407 written, if it will be immediately overwritten.
1408 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1409 if (lhs)
1410 {
1411 dsi->endptr = lhs;
1412 zsi = zero_length_string (lhs, dsi);
1413 }
1414 break;
1415 default:
1416 gcc_unreachable ();
1417 }
1418 if (zsi != NULL)
1419 zsi->dont_invalidate = true;
1420
1421 if (fn == NULL_TREE)
1422 return;
1423
1424 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1425 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1426
1427 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1428 len = fold_build2_loc (loc, PLUS_EXPR, type, len, build_int_cst (type, 1));
1429 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1430 GSI_SAME_STMT);
1431 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1432 {
1433 fprintf (dump_file, "Optimizing: ");
1434 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1435 }
1436 if (with_bounds)
1437 {
1438 fn = chkp_maybe_create_clone (fn)->decl;
1439 if (gimple_call_num_args (stmt) == 4)
1440 success = update_gimple_call (gsi, fn, 5, dst,
1441 gimple_call_arg (stmt, 1),
1442 src,
1443 gimple_call_arg (stmt, 3),
1444 len);
1445 else
1446 success = update_gimple_call (gsi, fn, 6, dst,
1447 gimple_call_arg (stmt, 1),
1448 src,
1449 gimple_call_arg (stmt, 3),
1450 len,
1451 gimple_call_arg (stmt, 4));
1452 }
1453 else
1454 if (gimple_call_num_args (stmt) == 2)
1455 success = update_gimple_call (gsi, fn, 3, dst, src, len);
1456 else
1457 success = update_gimple_call (gsi, fn, 4, dst, src, len,
1458 gimple_call_arg (stmt, 2));
1459 if (success)
1460 {
1461 stmt = gsi_stmt (*gsi);
1462 gimple_call_set_with_bounds (stmt, with_bounds);
1463 update_stmt (stmt);
1464 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1465 {
1466 fprintf (dump_file, "into: ");
1467 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1468 }
1469 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1470 laststmt.stmt = stmt;
1471 laststmt.len = srclen;
1472 laststmt.stridx = dsi->idx;
1473 }
1474 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1475 fprintf (dump_file, "not possible.\n");
1476 }
1477
1478 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1479 If strlen of the second argument is known and length of the third argument
1480 is that plus one, strlen of the first argument is the same after this
1481 call. */
1482
1483 static void
handle_builtin_memcpy(enum built_in_function bcode,gimple_stmt_iterator * gsi)1484 handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1485 {
1486 int idx, didx;
1487 tree src, dst, len, lhs, oldlen, newlen;
1488 gimple *stmt = gsi_stmt (*gsi);
1489 strinfo *si, *dsi, *olddsi;
1490 bool with_bounds = gimple_call_with_bounds_p (stmt);
1491
1492 len = gimple_call_arg (stmt, with_bounds ? 4 : 2);
1493 src = gimple_call_arg (stmt, with_bounds ? 2 : 1);
1494 dst = gimple_call_arg (stmt, 0);
1495 idx = get_stridx (src);
1496 if (idx == 0)
1497 return;
1498
1499 didx = get_stridx (dst);
1500 olddsi = NULL;
1501 if (didx > 0)
1502 olddsi = get_strinfo (didx);
1503 else if (didx < 0)
1504 return;
1505
1506 if (olddsi != NULL
1507 && tree_fits_uhwi_p (len)
1508 && !integer_zerop (len))
1509 adjust_last_stmt (olddsi, stmt, false);
1510
1511 if (idx > 0)
1512 {
1513 gimple *def_stmt;
1514
1515 /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */
1516 si = get_strinfo (idx);
1517 if (si == NULL || si->length == NULL_TREE)
1518 return;
1519 if (TREE_CODE (len) != SSA_NAME)
1520 return;
1521 def_stmt = SSA_NAME_DEF_STMT (len);
1522 if (!is_gimple_assign (def_stmt)
1523 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
1524 || gimple_assign_rhs1 (def_stmt) != si->length
1525 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
1526 return;
1527 }
1528 else
1529 {
1530 si = NULL;
1531 /* Handle memcpy (x, "abcd", 5) or
1532 memcpy (x, "abc\0uvw", 7). */
1533 if (!tree_fits_uhwi_p (len)
1534 || tree_to_uhwi (len) <= (unsigned HOST_WIDE_INT) ~idx)
1535 return;
1536 }
1537
1538 if (olddsi != NULL && TREE_CODE (len) == SSA_NAME)
1539 adjust_last_stmt (olddsi, stmt, false);
1540
1541 if (didx == 0)
1542 {
1543 didx = new_stridx (dst);
1544 if (didx == 0)
1545 return;
1546 }
1547 if (si != NULL)
1548 newlen = si->length;
1549 else
1550 newlen = build_int_cst (size_type_node, ~idx);
1551 oldlen = NULL_TREE;
1552 if (olddsi != NULL)
1553 {
1554 dsi = unshare_strinfo (olddsi);
1555 oldlen = olddsi->length;
1556 dsi->length = newlen;
1557 /* Break the chain, so adjust_related_strinfo on later pointers in
1558 the chain won't adjust this one anymore. */
1559 dsi->next = 0;
1560 dsi->stmt = NULL;
1561 dsi->endptr = NULL_TREE;
1562 }
1563 else
1564 {
1565 dsi = new_strinfo (dst, didx, newlen);
1566 set_strinfo (didx, dsi);
1567 find_equal_ptrs (dst, didx);
1568 }
1569 dsi->writable = true;
1570 dsi->dont_invalidate = true;
1571 if (olddsi != NULL)
1572 {
1573 tree adj = NULL_TREE;
1574 location_t loc = gimple_location (stmt);
1575 if (oldlen == NULL_TREE)
1576 ;
1577 else if (integer_zerop (oldlen))
1578 adj = dsi->length;
1579 else if (TREE_CODE (oldlen) == INTEGER_CST
1580 || TREE_CODE (dsi->length) == INTEGER_CST)
1581 adj = fold_build2_loc (loc, MINUS_EXPR,
1582 TREE_TYPE (dsi->length), dsi->length,
1583 fold_convert_loc (loc, TREE_TYPE (dsi->length),
1584 oldlen));
1585 if (adj != NULL_TREE)
1586 adjust_related_strinfos (loc, dsi, adj);
1587 else
1588 dsi->prev = 0;
1589 }
1590 /* memcpy src may not overlap dst, so src doesn't need to be
1591 invalidated either. */
1592 if (si != NULL)
1593 si->dont_invalidate = true;
1594
1595 lhs = gimple_call_lhs (stmt);
1596 switch (bcode)
1597 {
1598 case BUILT_IN_MEMCPY:
1599 case BUILT_IN_MEMCPY_CHK:
1600 case BUILT_IN_MEMCPY_CHKP:
1601 case BUILT_IN_MEMCPY_CHK_CHKP:
1602 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1603 laststmt.stmt = stmt;
1604 laststmt.len = dsi->length;
1605 laststmt.stridx = dsi->idx;
1606 if (lhs)
1607 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx;
1608 break;
1609 case BUILT_IN_MEMPCPY:
1610 case BUILT_IN_MEMPCPY_CHK:
1611 case BUILT_IN_MEMPCPY_CHKP:
1612 case BUILT_IN_MEMPCPY_CHK_CHKP:
1613 break;
1614 default:
1615 gcc_unreachable ();
1616 }
1617 }
1618
1619 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
1620 If strlen of the second argument is known, strlen of the first argument
1621 is increased by the length of the second argument. Furthermore, attempt
1622 to convert it to memcpy/strcpy if the length of the first argument
1623 is known. */
1624
1625 static void
handle_builtin_strcat(enum built_in_function bcode,gimple_stmt_iterator * gsi)1626 handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1627 {
1628 int idx, didx;
1629 tree src, dst, srclen, dstlen, len, lhs, args, type, fn, objsz, endptr;
1630 bool success;
1631 gimple *stmt = gsi_stmt (*gsi);
1632 strinfo *si, *dsi;
1633 location_t loc;
1634 bool with_bounds = gimple_call_with_bounds_p (stmt);
1635
1636 src = gimple_call_arg (stmt, with_bounds ? 2 : 1);
1637 dst = gimple_call_arg (stmt, 0);
1638 lhs = gimple_call_lhs (stmt);
1639
1640 didx = get_stridx (dst);
1641 if (didx < 0)
1642 return;
1643
1644 dsi = NULL;
1645 if (didx > 0)
1646 dsi = get_strinfo (didx);
1647 if (dsi == NULL || get_string_length (dsi) == NULL_TREE)
1648 {
1649 /* strcat (p, q) can be transformed into
1650 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
1651 with length endptr - p if we need to compute the length
1652 later on. Don't do this transformation if we don't need
1653 it. */
1654 if (builtin_decl_implicit_p (BUILT_IN_STPCPY) && lhs == NULL_TREE)
1655 {
1656 if (didx == 0)
1657 {
1658 didx = new_stridx (dst);
1659 if (didx == 0)
1660 return;
1661 }
1662 if (dsi == NULL)
1663 {
1664 dsi = new_strinfo (dst, didx, NULL_TREE);
1665 set_strinfo (didx, dsi);
1666 find_equal_ptrs (dst, didx);
1667 }
1668 else
1669 {
1670 dsi = unshare_strinfo (dsi);
1671 dsi->length = NULL_TREE;
1672 dsi->next = 0;
1673 dsi->endptr = NULL_TREE;
1674 }
1675 dsi->writable = true;
1676 dsi->stmt = stmt;
1677 dsi->dont_invalidate = true;
1678 }
1679 return;
1680 }
1681
1682 srclen = NULL_TREE;
1683 si = NULL;
1684 idx = get_stridx (src);
1685 if (idx < 0)
1686 srclen = build_int_cst (size_type_node, ~idx);
1687 else if (idx > 0)
1688 {
1689 si = get_strinfo (idx);
1690 if (si != NULL)
1691 srclen = get_string_length (si);
1692 }
1693
1694 loc = gimple_location (stmt);
1695 dstlen = dsi->length;
1696 endptr = dsi->endptr;
1697
1698 dsi = unshare_strinfo (dsi);
1699 dsi->endptr = NULL_TREE;
1700 dsi->stmt = NULL;
1701 dsi->writable = true;
1702
1703 if (srclen != NULL_TREE)
1704 {
1705 dsi->length = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (dsi->length),
1706 dsi->length, srclen);
1707 adjust_related_strinfos (loc, dsi, srclen);
1708 dsi->dont_invalidate = true;
1709 }
1710 else
1711 {
1712 dsi->length = NULL;
1713 if (lhs == NULL_TREE && builtin_decl_implicit_p (BUILT_IN_STPCPY))
1714 dsi->dont_invalidate = true;
1715 }
1716
1717 if (si != NULL)
1718 /* strcat src may not overlap dst, so src doesn't need to be
1719 invalidated either. */
1720 si->dont_invalidate = true;
1721
1722 /* For now. Could remove the lhs from the call and add
1723 lhs = dst; afterwards. */
1724 if (lhs)
1725 return;
1726
1727 fn = NULL_TREE;
1728 objsz = NULL_TREE;
1729 switch (bcode)
1730 {
1731 case BUILT_IN_STRCAT:
1732 case BUILT_IN_STRCAT_CHKP:
1733 if (srclen != NULL_TREE)
1734 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1735 else
1736 fn = builtin_decl_implicit (BUILT_IN_STRCPY);
1737 break;
1738 case BUILT_IN_STRCAT_CHK:
1739 case BUILT_IN_STRCAT_CHK_CHKP:
1740 if (srclen != NULL_TREE)
1741 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK);
1742 else
1743 fn = builtin_decl_explicit (BUILT_IN_STRCPY_CHK);
1744 objsz = gimple_call_arg (stmt, with_bounds ? 4 : 2);
1745 break;
1746 default:
1747 gcc_unreachable ();
1748 }
1749
1750 if (fn == NULL_TREE)
1751 return;
1752
1753 len = NULL_TREE;
1754 if (srclen != NULL_TREE)
1755 {
1756 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1757 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1758
1759 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1760 len = fold_build2_loc (loc, PLUS_EXPR, type, len,
1761 build_int_cst (type, 1));
1762 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1763 GSI_SAME_STMT);
1764 }
1765 if (endptr)
1766 dst = fold_convert_loc (loc, TREE_TYPE (dst), unshare_expr (endptr));
1767 else
1768 dst = fold_build2_loc (loc, POINTER_PLUS_EXPR,
1769 TREE_TYPE (dst), unshare_expr (dst),
1770 fold_convert_loc (loc, sizetype,
1771 unshare_expr (dstlen)));
1772 dst = force_gimple_operand_gsi (gsi, dst, true, NULL_TREE, true,
1773 GSI_SAME_STMT);
1774 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1775 {
1776 fprintf (dump_file, "Optimizing: ");
1777 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1778 }
1779 if (with_bounds)
1780 {
1781 fn = chkp_maybe_create_clone (fn)->decl;
1782 if (srclen != NULL_TREE)
1783 success = update_gimple_call (gsi, fn, 5 + (objsz != NULL_TREE),
1784 dst,
1785 gimple_call_arg (stmt, 1),
1786 src,
1787 gimple_call_arg (stmt, 3),
1788 len, objsz);
1789 else
1790 success = update_gimple_call (gsi, fn, 4 + (objsz != NULL_TREE),
1791 dst,
1792 gimple_call_arg (stmt, 1),
1793 src,
1794 gimple_call_arg (stmt, 3),
1795 objsz);
1796 }
1797 else
1798 if (srclen != NULL_TREE)
1799 success = update_gimple_call (gsi, fn, 3 + (objsz != NULL_TREE),
1800 dst, src, len, objsz);
1801 else
1802 success = update_gimple_call (gsi, fn, 2 + (objsz != NULL_TREE),
1803 dst, src, objsz);
1804 if (success)
1805 {
1806 stmt = gsi_stmt (*gsi);
1807 gimple_call_set_with_bounds (stmt, with_bounds);
1808 update_stmt (stmt);
1809 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1810 {
1811 fprintf (dump_file, "into: ");
1812 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1813 }
1814 /* If srclen == NULL, note that current string length can be
1815 computed by transforming this strcpy into stpcpy. */
1816 if (srclen == NULL_TREE && dsi->dont_invalidate)
1817 dsi->stmt = stmt;
1818 adjust_last_stmt (dsi, stmt, true);
1819 if (srclen != NULL_TREE)
1820 {
1821 laststmt.stmt = stmt;
1822 laststmt.len = srclen;
1823 laststmt.stridx = dsi->idx;
1824 }
1825 }
1826 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1827 fprintf (dump_file, "not possible.\n");
1828 }
1829
1830 /* Handle a call to malloc or calloc. */
1831
1832 static void
handle_builtin_malloc(enum built_in_function bcode,gimple_stmt_iterator * gsi)1833 handle_builtin_malloc (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1834 {
1835 gimple *stmt = gsi_stmt (*gsi);
1836 tree lhs = gimple_call_lhs (stmt);
1837 if (lhs == NULL_TREE)
1838 return;
1839
1840 gcc_assert (get_stridx (lhs) == 0);
1841 int idx = new_stridx (lhs);
1842 tree length = NULL_TREE;
1843 if (bcode == BUILT_IN_CALLOC)
1844 length = build_int_cst (size_type_node, 0);
1845 strinfo *si = new_strinfo (lhs, idx, length);
1846 if (bcode == BUILT_IN_CALLOC)
1847 si->endptr = lhs;
1848 set_strinfo (idx, si);
1849 si->writable = true;
1850 si->stmt = stmt;
1851 si->dont_invalidate = true;
1852 }
1853
1854 /* Handle a call to memset.
1855 After a call to calloc, memset(,0,) is unnecessary.
1856 memset(malloc(n),0,n) is calloc(n,1). */
1857
1858 static bool
handle_builtin_memset(gimple_stmt_iterator * gsi)1859 handle_builtin_memset (gimple_stmt_iterator *gsi)
1860 {
1861 gimple *stmt2 = gsi_stmt (*gsi);
1862 if (!integer_zerop (gimple_call_arg (stmt2, 1)))
1863 return true;
1864 tree ptr = gimple_call_arg (stmt2, 0);
1865 int idx1 = get_stridx (ptr);
1866 if (idx1 <= 0)
1867 return true;
1868 strinfo *si1 = get_strinfo (idx1);
1869 if (!si1)
1870 return true;
1871 gimple *stmt1 = si1->stmt;
1872 if (!stmt1 || !is_gimple_call (stmt1))
1873 return true;
1874 tree callee1 = gimple_call_fndecl (stmt1);
1875 if (!valid_builtin_call (stmt1))
1876 return true;
1877 enum built_in_function code1 = DECL_FUNCTION_CODE (callee1);
1878 tree size = gimple_call_arg (stmt2, 2);
1879 if (code1 == BUILT_IN_CALLOC)
1880 /* Not touching stmt1 */ ;
1881 else if (code1 == BUILT_IN_MALLOC
1882 && operand_equal_p (gimple_call_arg (stmt1, 0), size, 0))
1883 {
1884 gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt1);
1885 update_gimple_call (&gsi1, builtin_decl_implicit (BUILT_IN_CALLOC), 2,
1886 size, build_one_cst (size_type_node));
1887 si1->length = build_int_cst (size_type_node, 0);
1888 si1->stmt = gsi_stmt (gsi1);
1889 }
1890 else
1891 return true;
1892 tree lhs = gimple_call_lhs (stmt2);
1893 unlink_stmt_vdef (stmt2);
1894 if (lhs)
1895 {
1896 gimple *assign = gimple_build_assign (lhs, ptr);
1897 gsi_replace (gsi, assign, false);
1898 }
1899 else
1900 {
1901 gsi_remove (gsi, true);
1902 release_defs (stmt2);
1903 }
1904
1905 return false;
1906 }
1907
1908 /* Handle a POINTER_PLUS_EXPR statement.
1909 For p = "abcd" + 2; compute associated length, or if
1910 p = q + off is pointing to a '\0' character of a string, call
1911 zero_length_string on it. */
1912
1913 static void
handle_pointer_plus(gimple_stmt_iterator * gsi)1914 handle_pointer_plus (gimple_stmt_iterator *gsi)
1915 {
1916 gimple *stmt = gsi_stmt (*gsi);
1917 tree lhs = gimple_assign_lhs (stmt), off;
1918 int idx = get_stridx (gimple_assign_rhs1 (stmt));
1919 strinfo *si, *zsi;
1920
1921 if (idx == 0)
1922 return;
1923
1924 if (idx < 0)
1925 {
1926 tree off = gimple_assign_rhs2 (stmt);
1927 if (tree_fits_uhwi_p (off)
1928 && tree_to_uhwi (off) <= (unsigned HOST_WIDE_INT) ~idx)
1929 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)]
1930 = ~(~idx - (int) tree_to_uhwi (off));
1931 return;
1932 }
1933
1934 si = get_strinfo (idx);
1935 if (si == NULL || si->length == NULL_TREE)
1936 return;
1937
1938 off = gimple_assign_rhs2 (stmt);
1939 zsi = NULL;
1940 if (operand_equal_p (si->length, off, 0))
1941 zsi = zero_length_string (lhs, si);
1942 else if (TREE_CODE (off) == SSA_NAME)
1943 {
1944 gimple *def_stmt = SSA_NAME_DEF_STMT (off);
1945 if (gimple_assign_single_p (def_stmt)
1946 && operand_equal_p (si->length, gimple_assign_rhs1 (def_stmt), 0))
1947 zsi = zero_length_string (lhs, si);
1948 }
1949 if (zsi != NULL
1950 && si->endptr != NULL_TREE
1951 && si->endptr != lhs
1952 && TREE_CODE (si->endptr) == SSA_NAME)
1953 {
1954 enum tree_code rhs_code
1955 = useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (si->endptr))
1956 ? SSA_NAME : NOP_EXPR;
1957 gimple_assign_set_rhs_with_ops (gsi, rhs_code, si->endptr);
1958 gcc_assert (gsi_stmt (*gsi) == stmt);
1959 update_stmt (stmt);
1960 }
1961 }
1962
1963 /* Handle a single character store. */
1964
1965 static bool
handle_char_store(gimple_stmt_iterator * gsi)1966 handle_char_store (gimple_stmt_iterator *gsi)
1967 {
1968 int idx = -1;
1969 strinfo *si = NULL;
1970 gimple *stmt = gsi_stmt (*gsi);
1971 tree ssaname = NULL_TREE, lhs = gimple_assign_lhs (stmt);
1972
1973 if (TREE_CODE (lhs) == MEM_REF
1974 && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME)
1975 {
1976 if (integer_zerop (TREE_OPERAND (lhs, 1)))
1977 {
1978 ssaname = TREE_OPERAND (lhs, 0);
1979 idx = get_stridx (ssaname);
1980 }
1981 }
1982 else
1983 idx = get_addr_stridx (lhs);
1984
1985 if (idx > 0)
1986 {
1987 si = get_strinfo (idx);
1988 if (si != NULL && si->length != NULL_TREE && integer_zerop (si->length))
1989 {
1990 if (initializer_zerop (gimple_assign_rhs1 (stmt)))
1991 {
1992 /* When storing '\0', the store can be removed
1993 if we know it has been stored in the current function. */
1994 if (!stmt_could_throw_p (stmt) && si->writable)
1995 {
1996 unlink_stmt_vdef (stmt);
1997 release_defs (stmt);
1998 gsi_remove (gsi, true);
1999 return false;
2000 }
2001 else
2002 {
2003 si->writable = true;
2004 gsi_next (gsi);
2005 return false;
2006 }
2007 }
2008 else
2009 /* Otherwise this statement overwrites the '\0' with
2010 something, if the previous stmt was a memcpy,
2011 its length may be decreased. */
2012 adjust_last_stmt (si, stmt, false);
2013 }
2014 else if (si != NULL && integer_zerop (gimple_assign_rhs1 (stmt)))
2015 {
2016 si = unshare_strinfo (si);
2017 si->length = build_int_cst (size_type_node, 0);
2018 si->endptr = NULL;
2019 si->prev = 0;
2020 si->next = 0;
2021 si->stmt = NULL;
2022 si->first = 0;
2023 si->writable = true;
2024 if (ssaname && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname))
2025 si->endptr = ssaname;
2026 si->dont_invalidate = true;
2027 }
2028 /* If si->length is non-zero constant, we aren't overwriting '\0',
2029 and if we aren't storing '\0', we know that the length of the
2030 string and any other zero terminated string in memory remains
2031 the same. In that case we move to the next gimple statement and
2032 return to signal the caller that it shouldn't invalidate anything.
2033
2034 This is benefical for cases like:
2035
2036 char p[20];
2037 void foo (char *q)
2038 {
2039 strcpy (p, "foobar");
2040 size_t len = strlen (p); // This can be optimized into 6
2041 size_t len2 = strlen (q); // This has to be computed
2042 p[0] = 'X';
2043 size_t len3 = strlen (p); // This can be optimized into 6
2044 size_t len4 = strlen (q); // This can be optimized into len2
2045 bar (len, len2, len3, len4);
2046 }
2047 */
2048 else if (si != NULL && si->length != NULL_TREE
2049 && TREE_CODE (si->length) == INTEGER_CST
2050 && integer_nonzerop (gimple_assign_rhs1 (stmt)))
2051 {
2052 gsi_next (gsi);
2053 return false;
2054 }
2055 }
2056 else if (idx == 0 && initializer_zerop (gimple_assign_rhs1 (stmt)))
2057 {
2058 if (ssaname)
2059 {
2060 si = zero_length_string (ssaname, NULL);
2061 if (si != NULL)
2062 si->dont_invalidate = true;
2063 }
2064 else
2065 {
2066 int idx = new_addr_stridx (lhs);
2067 if (idx != 0)
2068 {
2069 si = new_strinfo (build_fold_addr_expr (lhs), idx,
2070 build_int_cst (size_type_node, 0));
2071 set_strinfo (idx, si);
2072 si->dont_invalidate = true;
2073 }
2074 }
2075 if (si != NULL)
2076 si->writable = true;
2077 }
2078 else if (idx == 0
2079 && TREE_CODE (gimple_assign_rhs1 (stmt)) == STRING_CST
2080 && ssaname == NULL_TREE
2081 && TREE_CODE (TREE_TYPE (lhs)) == ARRAY_TYPE)
2082 {
2083 size_t l = strlen (TREE_STRING_POINTER (gimple_assign_rhs1 (stmt)));
2084 HOST_WIDE_INT a = int_size_in_bytes (TREE_TYPE (lhs));
2085 if (a > 0 && (unsigned HOST_WIDE_INT) a > l)
2086 {
2087 int idx = new_addr_stridx (lhs);
2088 if (idx != 0)
2089 {
2090 si = new_strinfo (build_fold_addr_expr (lhs), idx,
2091 build_int_cst (size_type_node, l));
2092 set_strinfo (idx, si);
2093 si->dont_invalidate = true;
2094 }
2095 }
2096 }
2097
2098 if (si != NULL && initializer_zerop (gimple_assign_rhs1 (stmt)))
2099 {
2100 /* Allow adjust_last_stmt to remove it if the stored '\0'
2101 is immediately overwritten. */
2102 laststmt.stmt = stmt;
2103 laststmt.len = build_int_cst (size_type_node, 1);
2104 laststmt.stridx = si->idx;
2105 }
2106 return true;
2107 }
2108
2109 /* Attempt to optimize a single statement at *GSI using string length
2110 knowledge. */
2111
2112 static bool
strlen_optimize_stmt(gimple_stmt_iterator * gsi)2113 strlen_optimize_stmt (gimple_stmt_iterator *gsi)
2114 {
2115 gimple *stmt = gsi_stmt (*gsi);
2116
2117 if (is_gimple_call (stmt))
2118 {
2119 tree callee = gimple_call_fndecl (stmt);
2120 if (valid_builtin_call (stmt))
2121 switch (DECL_FUNCTION_CODE (callee))
2122 {
2123 case BUILT_IN_STRLEN:
2124 case BUILT_IN_STRLEN_CHKP:
2125 handle_builtin_strlen (gsi);
2126 break;
2127 case BUILT_IN_STRCHR:
2128 case BUILT_IN_STRCHR_CHKP:
2129 handle_builtin_strchr (gsi);
2130 break;
2131 case BUILT_IN_STRCPY:
2132 case BUILT_IN_STRCPY_CHK:
2133 case BUILT_IN_STPCPY:
2134 case BUILT_IN_STPCPY_CHK:
2135 case BUILT_IN_STRCPY_CHKP:
2136 case BUILT_IN_STRCPY_CHK_CHKP:
2137 case BUILT_IN_STPCPY_CHKP:
2138 case BUILT_IN_STPCPY_CHK_CHKP:
2139 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee), gsi);
2140 break;
2141 case BUILT_IN_MEMCPY:
2142 case BUILT_IN_MEMCPY_CHK:
2143 case BUILT_IN_MEMPCPY:
2144 case BUILT_IN_MEMPCPY_CHK:
2145 case BUILT_IN_MEMCPY_CHKP:
2146 case BUILT_IN_MEMCPY_CHK_CHKP:
2147 case BUILT_IN_MEMPCPY_CHKP:
2148 case BUILT_IN_MEMPCPY_CHK_CHKP:
2149 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi);
2150 break;
2151 case BUILT_IN_STRCAT:
2152 case BUILT_IN_STRCAT_CHK:
2153 case BUILT_IN_STRCAT_CHKP:
2154 case BUILT_IN_STRCAT_CHK_CHKP:
2155 handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi);
2156 break;
2157 case BUILT_IN_MALLOC:
2158 case BUILT_IN_CALLOC:
2159 handle_builtin_malloc (DECL_FUNCTION_CODE (callee), gsi);
2160 break;
2161 case BUILT_IN_MEMSET:
2162 if (!handle_builtin_memset (gsi))
2163 return false;
2164 break;
2165 default:
2166 break;
2167 }
2168 }
2169 else if (is_gimple_assign (stmt) && !gimple_clobber_p (stmt))
2170 {
2171 tree lhs = gimple_assign_lhs (stmt);
2172
2173 if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs)))
2174 {
2175 if (gimple_assign_single_p (stmt)
2176 || (gimple_assign_cast_p (stmt)
2177 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))))
2178 {
2179 int idx = get_stridx (gimple_assign_rhs1 (stmt));
2180 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = idx;
2181 }
2182 else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
2183 handle_pointer_plus (gsi);
2184 }
2185 else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
2186 {
2187 tree type = TREE_TYPE (lhs);
2188 if (TREE_CODE (type) == ARRAY_TYPE)
2189 type = TREE_TYPE (type);
2190 if (TREE_CODE (type) == INTEGER_TYPE
2191 && TYPE_MODE (type) == TYPE_MODE (char_type_node)
2192 && TYPE_PRECISION (type) == TYPE_PRECISION (char_type_node))
2193 {
2194 if (! handle_char_store (gsi))
2195 return false;
2196 }
2197 }
2198 }
2199
2200 if (gimple_vdef (stmt))
2201 maybe_invalidate (stmt);
2202 return true;
2203 }
2204
2205 /* Recursively call maybe_invalidate on stmts that might be executed
2206 in between dombb and current bb and that contain a vdef. Stop when
2207 *count stmts are inspected, or if the whole strinfo vector has
2208 been invalidated. */
2209
2210 static void
do_invalidate(basic_block dombb,gimple * phi,bitmap visited,int * count)2211 do_invalidate (basic_block dombb, gimple *phi, bitmap visited, int *count)
2212 {
2213 unsigned int i, n = gimple_phi_num_args (phi);
2214
2215 for (i = 0; i < n; i++)
2216 {
2217 tree vuse = gimple_phi_arg_def (phi, i);
2218 gimple *stmt = SSA_NAME_DEF_STMT (vuse);
2219 basic_block bb = gimple_bb (stmt);
2220 if (bb == NULL
2221 || bb == dombb
2222 || !bitmap_set_bit (visited, bb->index)
2223 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
2224 continue;
2225 while (1)
2226 {
2227 if (gimple_code (stmt) == GIMPLE_PHI)
2228 {
2229 do_invalidate (dombb, stmt, visited, count);
2230 if (*count == 0)
2231 return;
2232 break;
2233 }
2234 if (--*count == 0)
2235 return;
2236 if (!maybe_invalidate (stmt))
2237 {
2238 *count = 0;
2239 return;
2240 }
2241 vuse = gimple_vuse (stmt);
2242 stmt = SSA_NAME_DEF_STMT (vuse);
2243 if (gimple_bb (stmt) != bb)
2244 {
2245 bb = gimple_bb (stmt);
2246 if (bb == NULL
2247 || bb == dombb
2248 || !bitmap_set_bit (visited, bb->index)
2249 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
2250 break;
2251 }
2252 }
2253 }
2254 }
2255
2256 class strlen_dom_walker : public dom_walker
2257 {
2258 public:
strlen_dom_walker(cdi_direction direction)2259 strlen_dom_walker (cdi_direction direction) : dom_walker (direction) {}
2260
2261 virtual edge before_dom_children (basic_block);
2262 virtual void after_dom_children (basic_block);
2263 };
2264
2265 /* Callback for walk_dominator_tree. Attempt to optimize various
2266 string ops by remembering string lenths pointed by pointer SSA_NAMEs. */
2267
2268 edge
before_dom_children(basic_block bb)2269 strlen_dom_walker::before_dom_children (basic_block bb)
2270 {
2271 basic_block dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
2272
2273 if (dombb == NULL)
2274 stridx_to_strinfo = NULL;
2275 else
2276 {
2277 stridx_to_strinfo = ((vec<strinfo *, va_heap, vl_embed> *) dombb->aux);
2278 if (stridx_to_strinfo)
2279 {
2280 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
2281 gsi_next (&gsi))
2282 {
2283 gphi *phi = gsi.phi ();
2284 if (virtual_operand_p (gimple_phi_result (phi)))
2285 {
2286 bitmap visited = BITMAP_ALLOC (NULL);
2287 int count_vdef = 100;
2288 do_invalidate (dombb, phi, visited, &count_vdef);
2289 BITMAP_FREE (visited);
2290 if (count_vdef == 0)
2291 {
2292 /* If there were too many vdefs in between immediate
2293 dominator and current bb, invalidate everything.
2294 If stridx_to_strinfo has been unshared, we need
2295 to free it, otherwise just set it to NULL. */
2296 if (!strinfo_shared ())
2297 {
2298 unsigned int i;
2299 strinfo *si;
2300
2301 for (i = 1;
2302 vec_safe_iterate (stridx_to_strinfo, i, &si);
2303 ++i)
2304 {
2305 free_strinfo (si);
2306 (*stridx_to_strinfo)[i] = NULL;
2307 }
2308 }
2309 else
2310 stridx_to_strinfo = NULL;
2311 }
2312 break;
2313 }
2314 }
2315 }
2316 }
2317
2318 /* If all PHI arguments have the same string index, the PHI result
2319 has it as well. */
2320 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
2321 gsi_next (&gsi))
2322 {
2323 gphi *phi = gsi.phi ();
2324 tree result = gimple_phi_result (phi);
2325 if (!virtual_operand_p (result) && POINTER_TYPE_P (TREE_TYPE (result)))
2326 {
2327 int idx = get_stridx (gimple_phi_arg_def (phi, 0));
2328 if (idx != 0)
2329 {
2330 unsigned int i, n = gimple_phi_num_args (phi);
2331 for (i = 1; i < n; i++)
2332 if (idx != get_stridx (gimple_phi_arg_def (phi, i)))
2333 break;
2334 if (i == n)
2335 ssa_ver_to_stridx[SSA_NAME_VERSION (result)] = idx;
2336 }
2337 }
2338 }
2339
2340 /* Attempt to optimize individual statements. */
2341 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2342 if (strlen_optimize_stmt (&gsi))
2343 gsi_next (&gsi);
2344
2345 bb->aux = stridx_to_strinfo;
2346 if (vec_safe_length (stridx_to_strinfo) && !strinfo_shared ())
2347 (*stridx_to_strinfo)[0] = (strinfo *) bb;
2348 return NULL;
2349 }
2350
2351 /* Callback for walk_dominator_tree. Free strinfo vector if it is
2352 owned by the current bb, clear bb->aux. */
2353
2354 void
after_dom_children(basic_block bb)2355 strlen_dom_walker::after_dom_children (basic_block bb)
2356 {
2357 if (bb->aux)
2358 {
2359 stridx_to_strinfo = ((vec<strinfo *, va_heap, vl_embed> *) bb->aux);
2360 if (vec_safe_length (stridx_to_strinfo)
2361 && (*stridx_to_strinfo)[0] == (strinfo *) bb)
2362 {
2363 unsigned int i;
2364 strinfo *si;
2365
2366 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
2367 free_strinfo (si);
2368 vec_free (stridx_to_strinfo);
2369 }
2370 bb->aux = NULL;
2371 }
2372 }
2373
2374 /* Main entry point. */
2375
2376 namespace {
2377
2378 const pass_data pass_data_strlen =
2379 {
2380 GIMPLE_PASS, /* type */
2381 "strlen", /* name */
2382 OPTGROUP_NONE, /* optinfo_flags */
2383 TV_TREE_STRLEN, /* tv_id */
2384 ( PROP_cfg | PROP_ssa ), /* properties_required */
2385 0, /* properties_provided */
2386 0, /* properties_destroyed */
2387 0, /* todo_flags_start */
2388 0, /* todo_flags_finish */
2389 };
2390
2391 class pass_strlen : public gimple_opt_pass
2392 {
2393 public:
pass_strlen(gcc::context * ctxt)2394 pass_strlen (gcc::context *ctxt)
2395 : gimple_opt_pass (pass_data_strlen, ctxt)
2396 {}
2397
2398 /* opt_pass methods: */
gate(function *)2399 virtual bool gate (function *) { return flag_optimize_strlen != 0; }
2400 virtual unsigned int execute (function *);
2401
2402 }; // class pass_strlen
2403
2404 unsigned int
execute(function * fun)2405 pass_strlen::execute (function *fun)
2406 {
2407 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
2408 max_stridx = 1;
2409
2410 calculate_dominance_info (CDI_DOMINATORS);
2411
2412 /* String length optimization is implemented as a walk of the dominator
2413 tree and a forward walk of statements within each block. */
2414 strlen_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr);
2415
2416 ssa_ver_to_stridx.release ();
2417 strinfo_pool.release ();
2418 if (decl_to_stridxlist_htab)
2419 {
2420 obstack_free (&stridx_obstack, NULL);
2421 delete decl_to_stridxlist_htab;
2422 decl_to_stridxlist_htab = NULL;
2423 }
2424 laststmt.stmt = NULL;
2425 laststmt.len = NULL_TREE;
2426 laststmt.stridx = 0;
2427
2428 return 0;
2429 }
2430
2431 } // anon namespace
2432
2433 gimple_opt_pass *
make_pass_strlen(gcc::context * ctxt)2434 make_pass_strlen (gcc::context *ctxt)
2435 {
2436 return new pass_strlen (ctxt);
2437 }
2438