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