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