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