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 switch (DECL_FUNCTION_CODE (callee)) 1000 { 1001 case BUILT_IN_MEMCMP: 1002 case BUILT_IN_MEMCMP_EQ: 1003 case BUILT_IN_STRCHR: 1004 case BUILT_IN_STRCHR_CHKP: 1005 case BUILT_IN_STRLEN: 1006 case BUILT_IN_STRLEN_CHKP: 1007 /* The above functions should be pure. Punt if they aren't. */ 1008 if (gimple_vdef (stmt) || gimple_vuse (stmt) == NULL_TREE) 1009 return false; 1010 break; 1011 1012 case BUILT_IN_CALLOC: 1013 case BUILT_IN_MALLOC: 1014 case BUILT_IN_MEMCPY: 1015 case BUILT_IN_MEMCPY_CHK: 1016 case BUILT_IN_MEMCPY_CHKP: 1017 case BUILT_IN_MEMCPY_CHK_CHKP: 1018 case BUILT_IN_MEMPCPY: 1019 case BUILT_IN_MEMPCPY_CHK: 1020 case BUILT_IN_MEMPCPY_CHKP: 1021 case BUILT_IN_MEMPCPY_CHK_CHKP: 1022 case BUILT_IN_MEMSET: 1023 case BUILT_IN_STPCPY: 1024 case BUILT_IN_STPCPY_CHK: 1025 case BUILT_IN_STPCPY_CHKP: 1026 case BUILT_IN_STPCPY_CHK_CHKP: 1027 case BUILT_IN_STRCAT: 1028 case BUILT_IN_STRCAT_CHK: 1029 case BUILT_IN_STRCAT_CHKP: 1030 case BUILT_IN_STRCAT_CHK_CHKP: 1031 case BUILT_IN_STRCPY: 1032 case BUILT_IN_STRCPY_CHK: 1033 case BUILT_IN_STRCPY_CHKP: 1034 case BUILT_IN_STRCPY_CHK_CHKP: 1035 /* The above functions should be neither const nor pure. Punt if they 1036 aren't. */ 1037 if (gimple_vdef (stmt) == NULL_TREE || gimple_vuse (stmt) == NULL_TREE) 1038 return false; 1039 break; 1040 1041 default: 1042 break; 1043 } 1044 1045 return true; 1046 } 1047 1048 /* If the last .MEM setter statement before STMT is 1049 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT 1050 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to 1051 just memcpy (x, y, strlen (y)). SI must be the zero length 1052 strinfo. */ 1053 1054 static void 1055 adjust_last_stmt (strinfo *si, gimple *stmt, bool is_strcat) 1056 { 1057 tree vuse, callee, len; 1058 struct laststmt_struct last = laststmt; 1059 strinfo *lastsi, *firstsi; 1060 unsigned len_arg_no = 2; 1061 1062 laststmt.stmt = NULL; 1063 laststmt.len = NULL_TREE; 1064 laststmt.stridx = 0; 1065 1066 if (last.stmt == NULL) 1067 return; 1068 1069 vuse = gimple_vuse (stmt); 1070 if (vuse == NULL_TREE 1071 || SSA_NAME_DEF_STMT (vuse) != last.stmt 1072 || !has_single_use (vuse)) 1073 return; 1074 1075 gcc_assert (last.stridx > 0); 1076 lastsi = get_strinfo (last.stridx); 1077 if (lastsi == NULL) 1078 return; 1079 1080 if (lastsi != si) 1081 { 1082 if (lastsi->first == 0 || lastsi->first != si->first) 1083 return; 1084 1085 firstsi = verify_related_strinfos (si); 1086 if (firstsi == NULL) 1087 return; 1088 while (firstsi != lastsi) 1089 { 1090 firstsi = get_next_strinfo (firstsi); 1091 if (firstsi == NULL) 1092 return; 1093 } 1094 } 1095 1096 if (!is_strcat && !zero_length_string_p (si)) 1097 return; 1098 1099 if (is_gimple_assign (last.stmt)) 1100 { 1101 gimple_stmt_iterator gsi; 1102 1103 if (!integer_zerop (gimple_assign_rhs1 (last.stmt))) 1104 return; 1105 if (stmt_could_throw_p (last.stmt)) 1106 return; 1107 gsi = gsi_for_stmt (last.stmt); 1108 unlink_stmt_vdef (last.stmt); 1109 release_defs (last.stmt); 1110 gsi_remove (&gsi, true); 1111 return; 1112 } 1113 1114 if (!valid_builtin_call (last.stmt)) 1115 return; 1116 1117 callee = gimple_call_fndecl (last.stmt); 1118 switch (DECL_FUNCTION_CODE (callee)) 1119 { 1120 case BUILT_IN_MEMCPY: 1121 case BUILT_IN_MEMCPY_CHK: 1122 break; 1123 case BUILT_IN_MEMCPY_CHKP: 1124 case BUILT_IN_MEMCPY_CHK_CHKP: 1125 len_arg_no = 4; 1126 break; 1127 default: 1128 return; 1129 } 1130 1131 len = gimple_call_arg (last.stmt, len_arg_no); 1132 if (tree_fits_uhwi_p (len)) 1133 { 1134 if (!tree_fits_uhwi_p (last.len) 1135 || integer_zerop (len) 1136 || tree_to_uhwi (len) != tree_to_uhwi (last.len) + 1) 1137 return; 1138 /* Don't adjust the length if it is divisible by 4, it is more efficient 1139 to store the extra '\0' in that case. */ 1140 if ((tree_to_uhwi (len) & 3) == 0) 1141 return; 1142 } 1143 else if (TREE_CODE (len) == SSA_NAME) 1144 { 1145 gimple *def_stmt = SSA_NAME_DEF_STMT (len); 1146 if (!is_gimple_assign (def_stmt) 1147 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR 1148 || gimple_assign_rhs1 (def_stmt) != last.len 1149 || !integer_onep (gimple_assign_rhs2 (def_stmt))) 1150 return; 1151 } 1152 else 1153 return; 1154 1155 gimple_call_set_arg (last.stmt, len_arg_no, last.len); 1156 update_stmt (last.stmt); 1157 } 1158 1159 /* For an LHS that is an SSA_NAME with integer type and for strlen() 1160 argument SRC, set LHS range info to [0, N] if SRC refers to 1161 a character array A[N] with unknown length bounded by N. */ 1162 1163 static void 1164 maybe_set_strlen_range (tree lhs, tree src) 1165 { 1166 if (TREE_CODE (lhs) != SSA_NAME 1167 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs))) 1168 return; 1169 1170 if (TREE_CODE (src) == SSA_NAME) 1171 { 1172 gimple *def = SSA_NAME_DEF_STMT (src); 1173 if (is_gimple_assign (def) 1174 && gimple_assign_rhs_code (def) == ADDR_EXPR) 1175 src = gimple_assign_rhs1 (def); 1176 } 1177 1178 if (TREE_CODE (src) != ADDR_EXPR) 1179 return; 1180 1181 /* The last array member of a struct can be bigger than its size 1182 suggests if it's treated as a poor-man's flexible array member. */ 1183 src = TREE_OPERAND (src, 0); 1184 if (TREE_CODE (TREE_TYPE (src)) != ARRAY_TYPE 1185 || TREE_CODE (src) == MEM_REF 1186 || array_at_struct_end_p (src)) 1187 return; 1188 1189 tree type = TREE_TYPE (src); 1190 if (tree size = TYPE_SIZE_UNIT (type)) 1191 if (size && TREE_CODE (size) == INTEGER_CST) 1192 { 1193 wide_int max = wi::to_wide (size); 1194 wide_int min = wi::zero (max.get_precision ()); 1195 if (max != 0) 1196 --max; 1197 set_range_info (lhs, VR_RANGE, min, max); 1198 } 1199 } 1200 1201 /* Handle a strlen call. If strlen of the argument is known, replace 1202 the strlen call with the known value, otherwise remember that strlen 1203 of the argument is stored in the lhs SSA_NAME. */ 1204 1205 static void 1206 handle_builtin_strlen (gimple_stmt_iterator *gsi) 1207 { 1208 int idx; 1209 tree src; 1210 gimple *stmt = gsi_stmt (*gsi); 1211 tree lhs = gimple_call_lhs (stmt); 1212 1213 if (lhs == NULL_TREE) 1214 return; 1215 1216 src = gimple_call_arg (stmt, 0); 1217 idx = get_stridx (src); 1218 if (idx) 1219 { 1220 strinfo *si = NULL; 1221 tree rhs; 1222 1223 if (idx < 0) 1224 rhs = build_int_cst (TREE_TYPE (lhs), ~idx); 1225 else 1226 { 1227 rhs = NULL_TREE; 1228 si = get_strinfo (idx); 1229 if (si != NULL) 1230 rhs = get_string_length (si); 1231 } 1232 if (rhs != NULL_TREE) 1233 { 1234 if (dump_file && (dump_flags & TDF_DETAILS) != 0) 1235 { 1236 fprintf (dump_file, "Optimizing: "); 1237 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1238 } 1239 rhs = unshare_expr (rhs); 1240 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs))) 1241 rhs = fold_convert_loc (gimple_location (stmt), 1242 TREE_TYPE (lhs), rhs); 1243 if (!update_call_from_tree (gsi, rhs)) 1244 gimplify_and_update_call_from_tree (gsi, rhs); 1245 stmt = gsi_stmt (*gsi); 1246 update_stmt (stmt); 1247 if (dump_file && (dump_flags & TDF_DETAILS) != 0) 1248 { 1249 fprintf (dump_file, "into: "); 1250 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1251 } 1252 if (si != NULL 1253 && TREE_CODE (si->nonzero_chars) != SSA_NAME 1254 && TREE_CODE (si->nonzero_chars) != INTEGER_CST 1255 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) 1256 { 1257 si = unshare_strinfo (si); 1258 si->nonzero_chars = lhs; 1259 gcc_assert (si->full_string_p); 1260 } 1261 1262 if (strlen_to_stridx) 1263 { 1264 location_t loc = gimple_location (stmt); 1265 strlen_to_stridx->put (lhs, stridx_strlenloc (idx, loc)); 1266 } 1267 return; 1268 } 1269 } 1270 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) 1271 return; 1272 if (idx == 0) 1273 idx = new_stridx (src); 1274 else 1275 { 1276 strinfo *si = get_strinfo (idx); 1277 if (si != NULL) 1278 { 1279 if (!si->full_string_p && !si->stmt) 1280 { 1281 /* Until now we only had a lower bound on the string length. 1282 Install LHS as the actual length. */ 1283 si = unshare_strinfo (si); 1284 tree old = si->nonzero_chars; 1285 si->nonzero_chars = lhs; 1286 si->full_string_p = true; 1287 if (TREE_CODE (old) == INTEGER_CST) 1288 { 1289 location_t loc = gimple_location (stmt); 1290 old = fold_convert_loc (loc, TREE_TYPE (lhs), old); 1291 tree adj = fold_build2_loc (loc, MINUS_EXPR, 1292 TREE_TYPE (lhs), lhs, old); 1293 adjust_related_strinfos (loc, si, adj); 1294 } 1295 else 1296 { 1297 si->first = 0; 1298 si->prev = 0; 1299 si->next = 0; 1300 } 1301 } 1302 return; 1303 } 1304 } 1305 if (idx) 1306 { 1307 strinfo *si = new_strinfo (src, idx, lhs, true); 1308 set_strinfo (idx, si); 1309 find_equal_ptrs (src, idx); 1310 1311 /* For SRC that is an array of N elements, set LHS's range 1312 to [0, N]. */ 1313 maybe_set_strlen_range (lhs, src); 1314 1315 if (strlen_to_stridx) 1316 { 1317 location_t loc = gimple_location (stmt); 1318 strlen_to_stridx->put (lhs, stridx_strlenloc (idx, loc)); 1319 } 1320 } 1321 } 1322 1323 /* Handle a strchr call. If strlen of the first argument is known, replace 1324 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember 1325 that lhs of the call is endptr and strlen of the argument is endptr - x. */ 1326 1327 static void 1328 handle_builtin_strchr (gimple_stmt_iterator *gsi) 1329 { 1330 int idx; 1331 tree src; 1332 gimple *stmt = gsi_stmt (*gsi); 1333 tree lhs = gimple_call_lhs (stmt); 1334 bool with_bounds = gimple_call_with_bounds_p (stmt); 1335 1336 if (lhs == NULL_TREE) 1337 return; 1338 1339 if (!integer_zerop (gimple_call_arg (stmt, with_bounds ? 2 : 1))) 1340 return; 1341 1342 src = gimple_call_arg (stmt, 0); 1343 idx = get_stridx (src); 1344 if (idx) 1345 { 1346 strinfo *si = NULL; 1347 tree rhs; 1348 1349 if (idx < 0) 1350 rhs = build_int_cst (size_type_node, ~idx); 1351 else 1352 { 1353 rhs = NULL_TREE; 1354 si = get_strinfo (idx); 1355 if (si != NULL) 1356 rhs = get_string_length (si); 1357 } 1358 if (rhs != NULL_TREE) 1359 { 1360 location_t loc = gimple_location (stmt); 1361 1362 if (dump_file && (dump_flags & TDF_DETAILS) != 0) 1363 { 1364 fprintf (dump_file, "Optimizing: "); 1365 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1366 } 1367 if (si != NULL && si->endptr != NULL_TREE) 1368 { 1369 rhs = unshare_expr (si->endptr); 1370 if (!useless_type_conversion_p (TREE_TYPE (lhs), 1371 TREE_TYPE (rhs))) 1372 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs); 1373 } 1374 else 1375 { 1376 rhs = fold_convert_loc (loc, sizetype, unshare_expr (rhs)); 1377 rhs = fold_build2_loc (loc, POINTER_PLUS_EXPR, 1378 TREE_TYPE (src), src, rhs); 1379 if (!useless_type_conversion_p (TREE_TYPE (lhs), 1380 TREE_TYPE (rhs))) 1381 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs); 1382 } 1383 if (!update_call_from_tree (gsi, rhs)) 1384 gimplify_and_update_call_from_tree (gsi, rhs); 1385 stmt = gsi_stmt (*gsi); 1386 update_stmt (stmt); 1387 if (dump_file && (dump_flags & TDF_DETAILS) != 0) 1388 { 1389 fprintf (dump_file, "into: "); 1390 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1391 } 1392 if (si != NULL 1393 && si->endptr == NULL_TREE 1394 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) 1395 { 1396 si = unshare_strinfo (si); 1397 si->endptr = lhs; 1398 } 1399 zero_length_string (lhs, si); 1400 return; 1401 } 1402 } 1403 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) 1404 return; 1405 if (TREE_CODE (src) != SSA_NAME || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src)) 1406 { 1407 if (idx == 0) 1408 idx = new_stridx (src); 1409 else if (get_strinfo (idx) != NULL) 1410 { 1411 zero_length_string (lhs, NULL); 1412 return; 1413 } 1414 if (idx) 1415 { 1416 location_t loc = gimple_location (stmt); 1417 tree lhsu = fold_convert_loc (loc, size_type_node, lhs); 1418 tree srcu = fold_convert_loc (loc, size_type_node, src); 1419 tree length = fold_build2_loc (loc, MINUS_EXPR, 1420 size_type_node, lhsu, srcu); 1421 strinfo *si = new_strinfo (src, idx, length, true); 1422 si->endptr = lhs; 1423 set_strinfo (idx, si); 1424 find_equal_ptrs (src, idx); 1425 zero_length_string (lhs, si); 1426 } 1427 } 1428 else 1429 zero_length_string (lhs, NULL); 1430 } 1431 1432 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call. 1433 If strlen of the second argument is known, strlen of the first argument 1434 is the same after this call. Furthermore, attempt to convert it to 1435 memcpy. */ 1436 1437 static void 1438 handle_builtin_strcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi) 1439 { 1440 int idx, didx; 1441 tree src, dst, srclen, len, lhs, type, fn, oldlen; 1442 bool success; 1443 gimple *stmt = gsi_stmt (*gsi); 1444 strinfo *si, *dsi, *olddsi, *zsi; 1445 location_t loc; 1446 bool with_bounds = gimple_call_with_bounds_p (stmt); 1447 1448 src = gimple_call_arg (stmt, with_bounds ? 2 : 1); 1449 dst = gimple_call_arg (stmt, 0); 1450 lhs = gimple_call_lhs (stmt); 1451 idx = get_stridx (src); 1452 si = NULL; 1453 if (idx > 0) 1454 si = get_strinfo (idx); 1455 1456 didx = get_stridx (dst); 1457 olddsi = NULL; 1458 oldlen = NULL_TREE; 1459 if (didx > 0) 1460 olddsi = get_strinfo (didx); 1461 else if (didx < 0) 1462 return; 1463 1464 if (olddsi != NULL) 1465 adjust_last_stmt (olddsi, stmt, false); 1466 1467 srclen = NULL_TREE; 1468 if (si != NULL) 1469 srclen = get_string_length (si); 1470 else if (idx < 0) 1471 srclen = build_int_cst (size_type_node, ~idx); 1472 1473 loc = gimple_location (stmt); 1474 if (srclen == NULL_TREE) 1475 switch (bcode) 1476 { 1477 case BUILT_IN_STRCPY: 1478 case BUILT_IN_STRCPY_CHK: 1479 case BUILT_IN_STRCPY_CHKP: 1480 case BUILT_IN_STRCPY_CHK_CHKP: 1481 if (lhs != NULL_TREE || !builtin_decl_implicit_p (BUILT_IN_STPCPY)) 1482 return; 1483 break; 1484 case BUILT_IN_STPCPY: 1485 case BUILT_IN_STPCPY_CHK: 1486 case BUILT_IN_STPCPY_CHKP: 1487 case BUILT_IN_STPCPY_CHK_CHKP: 1488 if (lhs == NULL_TREE) 1489 return; 1490 else 1491 { 1492 tree lhsuint = fold_convert_loc (loc, size_type_node, lhs); 1493 srclen = fold_convert_loc (loc, size_type_node, dst); 1494 srclen = fold_build2_loc (loc, MINUS_EXPR, size_type_node, 1495 lhsuint, srclen); 1496 } 1497 break; 1498 default: 1499 gcc_unreachable (); 1500 } 1501 1502 if (didx == 0) 1503 { 1504 didx = new_stridx (dst); 1505 if (didx == 0) 1506 return; 1507 } 1508 if (olddsi != NULL) 1509 { 1510 oldlen = olddsi->nonzero_chars; 1511 dsi = unshare_strinfo (olddsi); 1512 dsi->nonzero_chars = srclen; 1513 dsi->full_string_p = (srclen != NULL_TREE); 1514 /* Break the chain, so adjust_related_strinfo on later pointers in 1515 the chain won't adjust this one anymore. */ 1516 dsi->next = 0; 1517 dsi->stmt = NULL; 1518 dsi->endptr = NULL_TREE; 1519 } 1520 else 1521 { 1522 dsi = new_strinfo (dst, didx, srclen, srclen != NULL_TREE); 1523 set_strinfo (didx, dsi); 1524 find_equal_ptrs (dst, didx); 1525 } 1526 dsi->writable = true; 1527 dsi->dont_invalidate = true; 1528 1529 if (dsi->nonzero_chars == NULL_TREE) 1530 { 1531 strinfo *chainsi; 1532 1533 /* If string length of src is unknown, use delayed length 1534 computation. If string lenth of dst will be needed, it 1535 can be computed by transforming this strcpy call into 1536 stpcpy and subtracting dst from the return value. */ 1537 1538 /* Look for earlier strings whose length could be determined if 1539 this strcpy is turned into an stpcpy. */ 1540 1541 if (dsi->prev != 0 && (chainsi = verify_related_strinfos (dsi)) != NULL) 1542 { 1543 for (; chainsi && chainsi != dsi; chainsi = get_strinfo (chainsi->next)) 1544 { 1545 /* When setting a stmt for delayed length computation 1546 prevent all strinfos through dsi from being 1547 invalidated. */ 1548 chainsi = unshare_strinfo (chainsi); 1549 chainsi->stmt = stmt; 1550 chainsi->nonzero_chars = NULL_TREE; 1551 chainsi->full_string_p = false; 1552 chainsi->endptr = NULL_TREE; 1553 chainsi->dont_invalidate = true; 1554 } 1555 } 1556 dsi->stmt = stmt; 1557 1558 /* Try to detect overlap before returning. This catches cases 1559 like strcpy (d, d + n) where n is non-constant whose range 1560 is such that (n <= strlen (d) holds). 1561 1562 OLDDSI->NONZERO_chars may have been reset by this point with 1563 oldlen holding it original value. */ 1564 if (olddsi && oldlen) 1565 { 1566 /* Add 1 for the terminating NUL. */ 1567 tree type = TREE_TYPE (oldlen); 1568 oldlen = fold_build2 (PLUS_EXPR, type, oldlen, 1569 build_int_cst (type, 1)); 1570 check_bounds_or_overlap (as_a <gcall *>(stmt), olddsi->ptr, src, 1571 oldlen, NULL_TREE); 1572 } 1573 1574 return; 1575 } 1576 1577 if (olddsi != NULL) 1578 { 1579 tree adj = NULL_TREE; 1580 if (oldlen == NULL_TREE) 1581 ; 1582 else if (integer_zerop (oldlen)) 1583 adj = srclen; 1584 else if (TREE_CODE (oldlen) == INTEGER_CST 1585 || TREE_CODE (srclen) == INTEGER_CST) 1586 adj = fold_build2_loc (loc, MINUS_EXPR, 1587 TREE_TYPE (srclen), srclen, 1588 fold_convert_loc (loc, TREE_TYPE (srclen), 1589 oldlen)); 1590 if (adj != NULL_TREE) 1591 adjust_related_strinfos (loc, dsi, adj); 1592 else 1593 dsi->prev = 0; 1594 } 1595 /* strcpy src may not overlap dst, so src doesn't need to be 1596 invalidated either. */ 1597 if (si != NULL) 1598 si->dont_invalidate = true; 1599 1600 fn = NULL_TREE; 1601 zsi = NULL; 1602 switch (bcode) 1603 { 1604 case BUILT_IN_STRCPY: 1605 case BUILT_IN_STRCPY_CHKP: 1606 fn = builtin_decl_implicit (BUILT_IN_MEMCPY); 1607 if (lhs) 1608 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx; 1609 break; 1610 case BUILT_IN_STRCPY_CHK: 1611 case BUILT_IN_STRCPY_CHK_CHKP: 1612 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK); 1613 if (lhs) 1614 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx; 1615 break; 1616 case BUILT_IN_STPCPY: 1617 case BUILT_IN_STPCPY_CHKP: 1618 /* This would need adjustment of the lhs (subtract one), 1619 or detection that the trailing '\0' doesn't need to be 1620 written, if it will be immediately overwritten. 1621 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */ 1622 if (lhs) 1623 { 1624 dsi->endptr = lhs; 1625 zsi = zero_length_string (lhs, dsi); 1626 } 1627 break; 1628 case BUILT_IN_STPCPY_CHK: 1629 case BUILT_IN_STPCPY_CHK_CHKP: 1630 /* This would need adjustment of the lhs (subtract one), 1631 or detection that the trailing '\0' doesn't need to be 1632 written, if it will be immediately overwritten. 1633 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */ 1634 if (lhs) 1635 { 1636 dsi->endptr = lhs; 1637 zsi = zero_length_string (lhs, dsi); 1638 } 1639 break; 1640 default: 1641 gcc_unreachable (); 1642 } 1643 if (zsi != NULL) 1644 zsi->dont_invalidate = true; 1645 1646 if (fn) 1647 { 1648 tree args = TYPE_ARG_TYPES (TREE_TYPE (fn)); 1649 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args))); 1650 } 1651 else 1652 type = size_type_node; 1653 1654 len = fold_convert_loc (loc, type, unshare_expr (srclen)); 1655 len = fold_build2_loc (loc, PLUS_EXPR, type, len, build_int_cst (type, 1)); 1656 1657 /* Set the no-warning bit on the transformed statement? */ 1658 bool set_no_warning = false; 1659 1660 if (const strinfo *chksi = olddsi ? olddsi : dsi) 1661 if (si 1662 && !check_bounds_or_overlap (as_a <gcall *>(stmt), chksi->ptr, si->ptr, 1663 NULL_TREE, len)) 1664 { 1665 gimple_set_no_warning (stmt, true); 1666 set_no_warning = true; 1667 } 1668 1669 if (fn == NULL_TREE) 1670 return; 1671 1672 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true, 1673 GSI_SAME_STMT); 1674 if (dump_file && (dump_flags & TDF_DETAILS) != 0) 1675 { 1676 fprintf (dump_file, "Optimizing: "); 1677 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1678 } 1679 if (with_bounds) 1680 { 1681 fn = chkp_maybe_create_clone (fn)->decl; 1682 if (gimple_call_num_args (stmt) == 4) 1683 success = update_gimple_call (gsi, fn, 5, dst, 1684 gimple_call_arg (stmt, 1), 1685 src, 1686 gimple_call_arg (stmt, 3), 1687 len); 1688 else 1689 success = update_gimple_call (gsi, fn, 6, dst, 1690 gimple_call_arg (stmt, 1), 1691 src, 1692 gimple_call_arg (stmt, 3), 1693 len, 1694 gimple_call_arg (stmt, 4)); 1695 } 1696 else 1697 if (gimple_call_num_args (stmt) == 2) 1698 success = update_gimple_call (gsi, fn, 3, dst, src, len); 1699 else 1700 success = update_gimple_call (gsi, fn, 4, dst, src, len, 1701 gimple_call_arg (stmt, 2)); 1702 if (success) 1703 { 1704 stmt = gsi_stmt (*gsi); 1705 gimple_call_set_with_bounds (stmt, with_bounds); 1706 update_stmt (stmt); 1707 if (dump_file && (dump_flags & TDF_DETAILS) != 0) 1708 { 1709 fprintf (dump_file, "into: "); 1710 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1711 } 1712 /* Allow adjust_last_stmt to decrease this memcpy's size. */ 1713 laststmt.stmt = stmt; 1714 laststmt.len = srclen; 1715 laststmt.stridx = dsi->idx; 1716 } 1717 else if (dump_file && (dump_flags & TDF_DETAILS) != 0) 1718 fprintf (dump_file, "not possible.\n"); 1719 1720 if (set_no_warning) 1721 gimple_set_no_warning (stmt, true); 1722 } 1723 1724 /* Check the size argument to the built-in forms of stpncpy and strncpy 1725 for out-of-bounds offsets or overlapping access, and to see if the 1726 size argument is derived from a call to strlen() on the source argument, 1727 and if so, issue an appropriate warning. */ 1728 1729 static void 1730 handle_builtin_strncat (built_in_function bcode, gimple_stmt_iterator *gsi) 1731 { 1732 /* Same as stxncpy(). */ 1733 handle_builtin_stxncpy (bcode, gsi); 1734 } 1735 1736 /* Return true if LEN depends on a call to strlen(SRC) in an interesting 1737 way. LEN can either be an integer expression, or a pointer (to char). 1738 When it is the latter (such as in recursive calls to self) is is 1739 assumed to be the argument in some call to strlen() whose relationship 1740 to SRC is being ascertained. */ 1741 1742 bool 1743 is_strlen_related_p (tree src, tree len) 1744 { 1745 if (TREE_CODE (TREE_TYPE (len)) == POINTER_TYPE 1746 && operand_equal_p (src, len, 0)) 1747 return true; 1748 1749 if (TREE_CODE (len) != SSA_NAME) 1750 return false; 1751 1752 gimple *def_stmt = SSA_NAME_DEF_STMT (len); 1753 if (!def_stmt) 1754 return false; 1755 1756 if (is_gimple_call (def_stmt)) 1757 { 1758 tree func = gimple_call_fndecl (def_stmt); 1759 if (!valid_builtin_call (def_stmt) 1760 || DECL_FUNCTION_CODE (func) != BUILT_IN_STRLEN) 1761 return false; 1762 1763 tree arg = gimple_call_arg (def_stmt, 0); 1764 return is_strlen_related_p (src, arg); 1765 } 1766 1767 if (!is_gimple_assign (def_stmt)) 1768 return false; 1769 1770 tree_code code = gimple_assign_rhs_code (def_stmt); 1771 tree rhs1 = gimple_assign_rhs1 (def_stmt); 1772 tree rhstype = TREE_TYPE (rhs1); 1773 1774 if ((TREE_CODE (rhstype) == POINTER_TYPE && code == POINTER_PLUS_EXPR) 1775 || (INTEGRAL_TYPE_P (rhstype) 1776 && (code == BIT_AND_EXPR 1777 || code == NOP_EXPR))) 1778 { 1779 /* Pointer plus (an integer), and truncation are considered among 1780 the (potentially) related expressions to strlen. */ 1781 return is_strlen_related_p (src, rhs1); 1782 } 1783 1784 if (tree rhs2 = gimple_assign_rhs2 (def_stmt)) 1785 { 1786 /* Integer subtraction is considered strlen-related when both 1787 arguments are integers and second one is strlen-related. */ 1788 rhstype = TREE_TYPE (rhs2); 1789 if (INTEGRAL_TYPE_P (rhstype) && code == MINUS_EXPR) 1790 return is_strlen_related_p (src, rhs2); 1791 } 1792 1793 return false; 1794 } 1795 1796 /* Called by handle_builtin_stxncpy and by gimple_fold_builtin_strncpy 1797 in gimple-fold.c. 1798 Check to see if the specified bound is a) equal to the size of 1799 the destination DST and if so, b) if it's immediately followed by 1800 DST[CNT - 1] = '\0'. If a) holds and b) does not, warn. Otherwise, 1801 do nothing. Return true if diagnostic has been issued. 1802 1803 The purpose is to diagnose calls to strncpy and stpncpy that do 1804 not nul-terminate the copy while allowing for the idiom where 1805 such a call is immediately followed by setting the last element 1806 to nul, as in: 1807 char a[32]; 1808 strncpy (a, s, sizeof a); 1809 a[sizeof a - 1] = '\0'; 1810 */ 1811 1812 bool 1813 maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi, tree src, tree cnt) 1814 { 1815 gimple *stmt = gsi_stmt (gsi); 1816 if (gimple_no_warning_p (stmt)) 1817 return false; 1818 1819 wide_int cntrange[2]; 1820 1821 if (TREE_CODE (cnt) == INTEGER_CST) 1822 cntrange[0] = cntrange[1] = wi::to_wide (cnt); 1823 else if (TREE_CODE (cnt) == SSA_NAME) 1824 { 1825 enum value_range_type rng = get_range_info (cnt, cntrange, cntrange + 1); 1826 if (rng == VR_RANGE) 1827 ; 1828 else if (rng == VR_ANTI_RANGE) 1829 { 1830 wide_int maxobjsize = wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node)); 1831 1832 if (wi::ltu_p (cntrange[1], maxobjsize)) 1833 { 1834 cntrange[0] = cntrange[1] + 1; 1835 cntrange[1] = maxobjsize; 1836 } 1837 else 1838 { 1839 cntrange[1] = cntrange[0] - 1; 1840 cntrange[0] = wi::zero (TYPE_PRECISION (TREE_TYPE (cnt))); 1841 } 1842 } 1843 else 1844 return false; 1845 } 1846 else 1847 return false; 1848 1849 /* Negative value is the constant string length. If it's less than 1850 the lower bound there is no truncation. Avoid calling get_stridx() 1851 when ssa_ver_to_stridx is empty. That implies the caller isn't 1852 running under the control of this pass and ssa_ver_to_stridx hasn't 1853 been created yet. */ 1854 int sidx = ssa_ver_to_stridx.length () ? get_stridx (src) : 0; 1855 if (sidx < 0 && wi::gtu_p (cntrange[0], ~sidx)) 1856 return false; 1857 1858 tree dst = gimple_call_arg (stmt, 0); 1859 tree dstdecl = dst; 1860 if (TREE_CODE (dstdecl) == ADDR_EXPR) 1861 dstdecl = TREE_OPERAND (dstdecl, 0); 1862 1863 tree ref = NULL_TREE; 1864 1865 if (!sidx) 1866 { 1867 /* If the source is a non-string return early to avoid warning 1868 for possible truncation (if the truncation is certain SIDX 1869 is non-zero). */ 1870 tree srcdecl = gimple_call_arg (stmt, 1); 1871 if (TREE_CODE (srcdecl) == ADDR_EXPR) 1872 srcdecl = TREE_OPERAND (srcdecl, 0); 1873 if (get_attr_nonstring_decl (srcdecl, &ref)) 1874 return false; 1875 } 1876 1877 /* Likewise, if the destination refers to a an array/pointer declared 1878 nonstring return early. */ 1879 if (get_attr_nonstring_decl (dstdecl, &ref)) 1880 return false; 1881 1882 /* Look for dst[i] = '\0'; after the stxncpy() call and if found 1883 avoid the truncation warning. */ 1884 gsi_next_nondebug (&gsi); 1885 gimple *next_stmt = gsi_stmt (gsi); 1886 if (!next_stmt) 1887 { 1888 /* When there is no statement in the same basic block check 1889 the immediate successor block. */ 1890 if (basic_block bb = gimple_bb (stmt)) 1891 { 1892 if (single_succ_p (bb)) 1893 { 1894 /* For simplicity, ignore blocks with multiple outgoing 1895 edges for now and only consider successor blocks along 1896 normal edges. */ 1897 edge e = EDGE_SUCC (bb, 0); 1898 if (!(e->flags & EDGE_ABNORMAL)) 1899 { 1900 gsi = gsi_start_bb (e->dest); 1901 next_stmt = gsi_stmt (gsi); 1902 if (next_stmt && is_gimple_debug (next_stmt)) 1903 { 1904 gsi_next_nondebug (&gsi); 1905 next_stmt = gsi_stmt (gsi); 1906 } 1907 } 1908 } 1909 } 1910 } 1911 1912 if (next_stmt && is_gimple_assign (next_stmt)) 1913 { 1914 tree lhs = gimple_assign_lhs (next_stmt); 1915 tree_code code = TREE_CODE (lhs); 1916 if (code == ARRAY_REF || code == MEM_REF) 1917 lhs = TREE_OPERAND (lhs, 0); 1918 1919 tree func = gimple_call_fndecl (stmt); 1920 if (DECL_FUNCTION_CODE (func) == BUILT_IN_STPNCPY) 1921 { 1922 tree ret = gimple_call_lhs (stmt); 1923 if (ret && operand_equal_p (ret, lhs, 0)) 1924 return false; 1925 } 1926 1927 /* Determine the base address and offset of the reference, 1928 ignoring the innermost array index. */ 1929 if (TREE_CODE (ref) == ARRAY_REF) 1930 ref = TREE_OPERAND (ref, 0); 1931 1932 poly_int64 dstoff; 1933 tree dstbase = get_addr_base_and_unit_offset (ref, &dstoff); 1934 1935 poly_int64 lhsoff; 1936 tree lhsbase = get_addr_base_and_unit_offset (lhs, &lhsoff); 1937 if (lhsbase 1938 && dstbase 1939 && known_eq (dstoff, lhsoff) 1940 && operand_equal_p (dstbase, lhsbase, 0)) 1941 return false; 1942 } 1943 1944 int prec = TYPE_PRECISION (TREE_TYPE (cnt)); 1945 wide_int lenrange[2]; 1946 if (strinfo *sisrc = sidx > 0 ? get_strinfo (sidx) : NULL) 1947 { 1948 lenrange[0] = (sisrc->nonzero_chars 1949 && TREE_CODE (sisrc->nonzero_chars) == INTEGER_CST 1950 ? wi::to_wide (sisrc->nonzero_chars) 1951 : wi::zero (prec)); 1952 lenrange[1] = lenrange[0]; 1953 } 1954 else if (sidx < 0) 1955 lenrange[0] = lenrange[1] = wi::shwi (~sidx, prec); 1956 else 1957 { 1958 tree range[2]; 1959 get_range_strlen (src, range); 1960 if (range[0] != NULL_TREE 1961 && TREE_CODE (range[0]) == INTEGER_CST 1962 && range[1] != NULL_TREE 1963 && TREE_CODE (range[1]) == INTEGER_CST) 1964 { 1965 lenrange[0] = wi::to_wide (range[0], prec); 1966 lenrange[1] = wi::to_wide (range[1], prec); 1967 } 1968 else 1969 { 1970 lenrange[0] = wi::shwi (0, prec); 1971 lenrange[1] = wi::shwi (-1, prec); 1972 } 1973 } 1974 1975 location_t callloc = gimple_location (stmt); 1976 tree func = gimple_call_fndecl (stmt); 1977 1978 if (lenrange[0] != 0 || !wi::neg_p (lenrange[1])) 1979 { 1980 /* If the longest source string is shorter than the lower bound 1981 of the specified count the copy is definitely nul-terminated. */ 1982 if (wi::ltu_p (lenrange[1], cntrange[0])) 1983 return false; 1984 1985 if (wi::neg_p (lenrange[1])) 1986 { 1987 /* The length of one of the strings is unknown but at least 1988 one has non-zero length and that length is stored in 1989 LENRANGE[1]. Swap the bounds to force a "may be truncated" 1990 warning below. */ 1991 lenrange[1] = lenrange[0]; 1992 lenrange[0] = wi::shwi (0, prec); 1993 } 1994 1995 gcall *call = as_a <gcall *> (stmt); 1996 1997 if (lenrange[0] == cntrange[1] && cntrange[0] == cntrange[1]) 1998 return warning_n (callloc, OPT_Wstringop_truncation, 1999 cntrange[0].to_uhwi (), 2000 "%G%qD output truncated before terminating " 2001 "nul copying %E byte from a string of the " 2002 "same length", 2003 "%G%qD output truncated before terminating nul " 2004 "copying %E bytes from a string of the same " 2005 "length", 2006 call, func, cnt); 2007 else if (wi::geu_p (lenrange[0], cntrange[1])) 2008 { 2009 /* The shortest string is longer than the upper bound of 2010 the count so the truncation is certain. */ 2011 if (cntrange[0] == cntrange[1]) 2012 return warning_n (callloc, OPT_Wstringop_truncation, 2013 cntrange[0].to_uhwi (), 2014 "%G%qD output truncated copying %E byte " 2015 "from a string of length %wu", 2016 "%G%qD output truncated copying %E bytes " 2017 "from a string of length %wu", 2018 call, func, cnt, lenrange[0].to_uhwi ()); 2019 2020 return warning_at (callloc, OPT_Wstringop_truncation, 2021 "%G%qD output truncated copying between %wu " 2022 "and %wu bytes from a string of length %wu", 2023 call, func, cntrange[0].to_uhwi (), 2024 cntrange[1].to_uhwi (), lenrange[0].to_uhwi ()); 2025 } 2026 else if (wi::geu_p (lenrange[1], cntrange[1])) 2027 { 2028 /* The longest string is longer than the upper bound of 2029 the count so the truncation is possible. */ 2030 if (cntrange[0] == cntrange[1]) 2031 return warning_n (callloc, OPT_Wstringop_truncation, 2032 cntrange[0].to_uhwi (), 2033 "%G%qD output may be truncated copying %E " 2034 "byte from a string of length %wu", 2035 "%G%qD output may be truncated copying %E " 2036 "bytes from a string of length %wu", 2037 call, func, cnt, lenrange[1].to_uhwi ()); 2038 2039 return warning_at (callloc, OPT_Wstringop_truncation, 2040 "%G%qD output may be truncated copying between %wu " 2041 "and %wu bytes from a string of length %wu", 2042 call, func, cntrange[0].to_uhwi (), 2043 cntrange[1].to_uhwi (), lenrange[1].to_uhwi ()); 2044 } 2045 2046 if (cntrange[0] != cntrange[1] 2047 && wi::leu_p (cntrange[0], lenrange[0]) 2048 && wi::leu_p (cntrange[1], lenrange[0] + 1)) 2049 { 2050 /* If the source (including the terminating nul) is longer than 2051 the lower bound of the specified count but shorter than the 2052 upper bound the copy may (but need not) be truncated. */ 2053 return warning_at (callloc, OPT_Wstringop_truncation, 2054 "%G%qD output may be truncated copying between " 2055 "%wu and %wu bytes from a string of length %wu", 2056 call, func, cntrange[0].to_uhwi (), 2057 cntrange[1].to_uhwi (), lenrange[0].to_uhwi ()); 2058 } 2059 } 2060 2061 if (tree dstsize = compute_objsize (dst, 1)) 2062 { 2063 /* The source length is uknown. Try to determine the destination 2064 size and see if it matches the specified bound. If not, bail. 2065 Otherwise go on to see if it should be diagnosed for possible 2066 truncation. */ 2067 if (!dstsize) 2068 return false; 2069 2070 if (wi::to_wide (dstsize) != cntrange[1]) 2071 return false; 2072 2073 if (cntrange[0] == cntrange[1]) 2074 return warning_at (callloc, OPT_Wstringop_truncation, 2075 "%G%qD specified bound %E equals destination size", 2076 as_a <gcall *> (stmt), func, cnt); 2077 } 2078 2079 return false; 2080 } 2081 2082 /* Check the arguments to the built-in forms of stpncpy and strncpy for 2083 out-of-bounds offsets or overlapping access, and to see if the size 2084 is derived from calling strlen() on the source argument, and if so, 2085 issue the appropriate warning. */ 2086 2087 static void 2088 handle_builtin_stxncpy (built_in_function, gimple_stmt_iterator *gsi) 2089 { 2090 if (!strlen_to_stridx) 2091 return; 2092 2093 gimple *stmt = gsi_stmt (*gsi); 2094 2095 bool with_bounds = gimple_call_with_bounds_p (stmt); 2096 2097 tree dst = gimple_call_arg (stmt, with_bounds ? 1 : 0); 2098 tree src = gimple_call_arg (stmt, with_bounds ? 2 : 1); 2099 tree len = gimple_call_arg (stmt, with_bounds ? 3 : 2); 2100 tree dstsize = NULL_TREE, srcsize = NULL_TREE; 2101 2102 int didx = get_stridx (dst); 2103 if (strinfo *sidst = didx > 0 ? get_strinfo (didx) : NULL) 2104 { 2105 /* Compute the size of the destination string including the NUL. */ 2106 if (sidst->nonzero_chars) 2107 { 2108 tree type = TREE_TYPE (sidst->nonzero_chars); 2109 dstsize = fold_build2 (PLUS_EXPR, type, sidst->nonzero_chars, 2110 build_int_cst (type, 1)); 2111 } 2112 dst = sidst->ptr; 2113 } 2114 2115 int sidx = get_stridx (src); 2116 strinfo *sisrc = sidx > 0 ? get_strinfo (sidx) : NULL; 2117 if (sisrc) 2118 { 2119 /* strncat() and strncpy() can modify the source string by writing 2120 over the terminating nul so SISRC->DONT_INVALIDATE must be left 2121 clear. */ 2122 2123 /* Compute the size of the source string including the NUL. */ 2124 if (sisrc->nonzero_chars) 2125 { 2126 tree type = TREE_TYPE (sisrc->nonzero_chars); 2127 srcsize = fold_build2 (PLUS_EXPR, type, sisrc->nonzero_chars, 2128 build_int_cst (type, 1)); 2129 } 2130 2131 src = sisrc->ptr; 2132 } 2133 else 2134 srcsize = NULL_TREE; 2135 2136 if (!check_bounds_or_overlap (as_a <gcall *>(stmt), dst, src, 2137 dstsize, srcsize)) 2138 { 2139 gimple_set_no_warning (stmt, true); 2140 return; 2141 } 2142 2143 /* If the length argument was computed from strlen(S) for some string 2144 S retrieve the strinfo index for the string (PSS->FIRST) alonng with 2145 the location of the strlen() call (PSS->SECOND). */ 2146 stridx_strlenloc *pss = strlen_to_stridx->get (len); 2147 if (!pss || pss->first <= 0) 2148 { 2149 if (maybe_diag_stxncpy_trunc (*gsi, src, len)) 2150 gimple_set_no_warning (stmt, true); 2151 2152 return; 2153 } 2154 2155 /* Retrieve the strinfo data for the string S that LEN was computed 2156 from as some function F of strlen (S) (i.e., LEN need not be equal 2157 to strlen(S)). */ 2158 strinfo *silen = get_strinfo (pss->first); 2159 2160 location_t callloc = gimple_location (stmt); 2161 2162 tree func = gimple_call_fndecl (stmt); 2163 2164 bool warned = false; 2165 2166 /* When -Wstringop-truncation is set, try to determine truncation 2167 before diagnosing possible overflow. Truncation is implied by 2168 the LEN argument being equal to strlen(SRC), regardless of 2169 whether its value is known. Otherwise, issue the more generic 2170 -Wstringop-overflow which triggers for LEN arguments that in 2171 any meaningful way depend on strlen(SRC). */ 2172 if (sisrc == silen 2173 && is_strlen_related_p (src, len) 2174 && warning_at (callloc, OPT_Wstringop_truncation, 2175 "%G%qD output truncated before terminating nul " 2176 "copying as many bytes from a string as its length", 2177 as_a <gcall *>(stmt), func)) 2178 warned = true; 2179 else if (silen && is_strlen_related_p (src, silen->ptr)) 2180 warned = warning_at (callloc, OPT_Wstringop_overflow_, 2181 "%G%qD specified bound depends on the length " 2182 "of the source argument", 2183 as_a <gcall *>(stmt), func); 2184 if (warned) 2185 { 2186 location_t strlenloc = pss->second; 2187 if (strlenloc != UNKNOWN_LOCATION && strlenloc != callloc) 2188 inform (strlenloc, "length computed here"); 2189 } 2190 } 2191 2192 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call. 2193 If strlen of the second argument is known and length of the third argument 2194 is that plus one, strlen of the first argument is the same after this 2195 call. */ 2196 2197 static void 2198 handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi) 2199 { 2200 int idx, didx; 2201 tree src, dst, len, lhs, oldlen, newlen; 2202 gimple *stmt = gsi_stmt (*gsi); 2203 strinfo *si, *dsi, *olddsi; 2204 bool with_bounds = gimple_call_with_bounds_p (stmt); 2205 2206 len = gimple_call_arg (stmt, with_bounds ? 4 : 2); 2207 src = gimple_call_arg (stmt, with_bounds ? 2 : 1); 2208 dst = gimple_call_arg (stmt, 0); 2209 idx = get_stridx (src); 2210 if (idx == 0) 2211 return; 2212 2213 didx = get_stridx (dst); 2214 olddsi = NULL; 2215 if (didx > 0) 2216 olddsi = get_strinfo (didx); 2217 else if (didx < 0) 2218 return; 2219 2220 if (olddsi != NULL 2221 && tree_fits_uhwi_p (len) 2222 && !integer_zerop (len)) 2223 adjust_last_stmt (olddsi, stmt, false); 2224 2225 bool full_string_p; 2226 if (idx > 0) 2227 { 2228 gimple *def_stmt; 2229 2230 /* Handle memcpy (x, y, l) where l's relationship with strlen (y) 2231 is known. */ 2232 si = get_strinfo (idx); 2233 if (si == NULL || si->nonzero_chars == NULL_TREE) 2234 return; 2235 if (TREE_CODE (len) == INTEGER_CST 2236 && TREE_CODE (si->nonzero_chars) == INTEGER_CST) 2237 { 2238 if (tree_int_cst_le (len, si->nonzero_chars)) 2239 { 2240 /* Copying LEN nonzero characters, where LEN is constant. */ 2241 newlen = len; 2242 full_string_p = false; 2243 } 2244 else 2245 { 2246 /* Copying the whole of the analyzed part of SI. */ 2247 newlen = si->nonzero_chars; 2248 full_string_p = si->full_string_p; 2249 } 2250 } 2251 else 2252 { 2253 if (!si->full_string_p) 2254 return; 2255 if (TREE_CODE (len) != SSA_NAME) 2256 return; 2257 def_stmt = SSA_NAME_DEF_STMT (len); 2258 if (!is_gimple_assign (def_stmt) 2259 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR 2260 || gimple_assign_rhs1 (def_stmt) != si->nonzero_chars 2261 || !integer_onep (gimple_assign_rhs2 (def_stmt))) 2262 return; 2263 /* Copying variable-length string SI (and no more). */ 2264 newlen = si->nonzero_chars; 2265 full_string_p = true; 2266 } 2267 } 2268 else 2269 { 2270 si = NULL; 2271 /* Handle memcpy (x, "abcd", 5) or 2272 memcpy (x, "abc\0uvw", 7). */ 2273 if (!tree_fits_uhwi_p (len)) 2274 return; 2275 2276 unsigned HOST_WIDE_INT clen = tree_to_uhwi (len); 2277 unsigned HOST_WIDE_INT nonzero_chars = ~idx; 2278 newlen = build_int_cst (size_type_node, MIN (nonzero_chars, clen)); 2279 full_string_p = clen > nonzero_chars; 2280 } 2281 2282 if (olddsi != NULL && TREE_CODE (len) == SSA_NAME) 2283 adjust_last_stmt (olddsi, stmt, false); 2284 2285 if (didx == 0) 2286 { 2287 didx = new_stridx (dst); 2288 if (didx == 0) 2289 return; 2290 } 2291 oldlen = NULL_TREE; 2292 if (olddsi != NULL) 2293 { 2294 dsi = unshare_strinfo (olddsi); 2295 oldlen = olddsi->nonzero_chars; 2296 dsi->nonzero_chars = newlen; 2297 dsi->full_string_p = full_string_p; 2298 /* Break the chain, so adjust_related_strinfo on later pointers in 2299 the chain won't adjust this one anymore. */ 2300 dsi->next = 0; 2301 dsi->stmt = NULL; 2302 dsi->endptr = NULL_TREE; 2303 } 2304 else 2305 { 2306 dsi = new_strinfo (dst, didx, newlen, full_string_p); 2307 set_strinfo (didx, dsi); 2308 find_equal_ptrs (dst, didx); 2309 } 2310 dsi->writable = true; 2311 dsi->dont_invalidate = true; 2312 if (olddsi != NULL) 2313 { 2314 tree adj = NULL_TREE; 2315 location_t loc = gimple_location (stmt); 2316 if (oldlen == NULL_TREE) 2317 ; 2318 else if (integer_zerop (oldlen)) 2319 adj = newlen; 2320 else if (TREE_CODE (oldlen) == INTEGER_CST 2321 || TREE_CODE (newlen) == INTEGER_CST) 2322 adj = fold_build2_loc (loc, MINUS_EXPR, TREE_TYPE (newlen), newlen, 2323 fold_convert_loc (loc, TREE_TYPE (newlen), 2324 oldlen)); 2325 if (adj != NULL_TREE) 2326 adjust_related_strinfos (loc, dsi, adj); 2327 else 2328 dsi->prev = 0; 2329 } 2330 /* memcpy src may not overlap dst, so src doesn't need to be 2331 invalidated either. */ 2332 if (si != NULL) 2333 si->dont_invalidate = true; 2334 2335 if (full_string_p) 2336 { 2337 lhs = gimple_call_lhs (stmt); 2338 switch (bcode) 2339 { 2340 case BUILT_IN_MEMCPY: 2341 case BUILT_IN_MEMCPY_CHK: 2342 case BUILT_IN_MEMCPY_CHKP: 2343 case BUILT_IN_MEMCPY_CHK_CHKP: 2344 /* Allow adjust_last_stmt to decrease this memcpy's size. */ 2345 laststmt.stmt = stmt; 2346 laststmt.len = dsi->nonzero_chars; 2347 laststmt.stridx = dsi->idx; 2348 if (lhs) 2349 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx; 2350 break; 2351 case BUILT_IN_MEMPCPY: 2352 case BUILT_IN_MEMPCPY_CHK: 2353 case BUILT_IN_MEMPCPY_CHKP: 2354 case BUILT_IN_MEMPCPY_CHK_CHKP: 2355 break; 2356 default: 2357 gcc_unreachable (); 2358 } 2359 } 2360 } 2361 2362 /* Handle a strcat-like ({strcat,__strcat_chk}) call. 2363 If strlen of the second argument is known, strlen of the first argument 2364 is increased by the length of the second argument. Furthermore, attempt 2365 to convert it to memcpy/strcpy if the length of the first argument 2366 is known. */ 2367 2368 static void 2369 handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi) 2370 { 2371 int idx, didx; 2372 tree srclen, args, type, fn, objsz, endptr; 2373 bool success; 2374 gimple *stmt = gsi_stmt (*gsi); 2375 strinfo *si, *dsi; 2376 location_t loc = gimple_location (stmt); 2377 bool with_bounds = gimple_call_with_bounds_p (stmt); 2378 2379 tree src = gimple_call_arg (stmt, with_bounds ? 2 : 1); 2380 tree dst = gimple_call_arg (stmt, 0); 2381 2382 /* Bail if the source is the same as destination. It will be diagnosed 2383 elsewhere. */ 2384 if (operand_equal_p (src, dst, 0)) 2385 return; 2386 2387 tree lhs = gimple_call_lhs (stmt); 2388 2389 didx = get_stridx (dst); 2390 if (didx < 0) 2391 return; 2392 2393 dsi = NULL; 2394 if (didx > 0) 2395 dsi = get_strinfo (didx); 2396 2397 srclen = NULL_TREE; 2398 si = NULL; 2399 idx = get_stridx (src); 2400 if (idx < 0) 2401 srclen = build_int_cst (size_type_node, ~idx); 2402 else if (idx > 0) 2403 { 2404 si = get_strinfo (idx); 2405 if (si != NULL) 2406 srclen = get_string_length (si); 2407 } 2408 2409 /* Set the no-warning bit on the transformed statement? */ 2410 bool set_no_warning = false; 2411 2412 if (dsi == NULL || get_string_length (dsi) == NULL_TREE) 2413 { 2414 { 2415 /* The concatenation always involves copying at least one byte 2416 (the terminating nul), even if the source string is empty. 2417 If the source is unknown assume it's one character long and 2418 used that as both sizes. */ 2419 tree slen = srclen; 2420 if (slen) 2421 { 2422 tree type = TREE_TYPE (slen); 2423 slen = fold_build2 (PLUS_EXPR, type, slen, build_int_cst (type, 1)); 2424 } 2425 2426 tree sptr = si && si->ptr ? si->ptr : src; 2427 2428 if (!check_bounds_or_overlap (as_a <gcall *>(stmt), dst, sptr, 2429 NULL_TREE, slen)) 2430 { 2431 gimple_set_no_warning (stmt, true); 2432 set_no_warning = true; 2433 } 2434 } 2435 2436 /* strcat (p, q) can be transformed into 2437 tmp = p + strlen (p); endptr = stpcpy (tmp, q); 2438 with length endptr - p if we need to compute the length 2439 later on. Don't do this transformation if we don't need 2440 it. */ 2441 if (builtin_decl_implicit_p (BUILT_IN_STPCPY) && lhs == NULL_TREE) 2442 { 2443 if (didx == 0) 2444 { 2445 didx = new_stridx (dst); 2446 if (didx == 0) 2447 return; 2448 } 2449 if (dsi == NULL) 2450 { 2451 dsi = new_strinfo (dst, didx, NULL_TREE, false); 2452 set_strinfo (didx, dsi); 2453 find_equal_ptrs (dst, didx); 2454 } 2455 else 2456 { 2457 dsi = unshare_strinfo (dsi); 2458 dsi->nonzero_chars = NULL_TREE; 2459 dsi->full_string_p = false; 2460 dsi->next = 0; 2461 dsi->endptr = NULL_TREE; 2462 } 2463 dsi->writable = true; 2464 dsi->stmt = stmt; 2465 dsi->dont_invalidate = true; 2466 } 2467 return; 2468 } 2469 2470 tree dstlen = dsi->nonzero_chars; 2471 endptr = dsi->endptr; 2472 2473 dsi = unshare_strinfo (dsi); 2474 dsi->endptr = NULL_TREE; 2475 dsi->stmt = NULL; 2476 dsi->writable = true; 2477 2478 if (srclen != NULL_TREE) 2479 { 2480 dsi->nonzero_chars = fold_build2_loc (loc, PLUS_EXPR, 2481 TREE_TYPE (dsi->nonzero_chars), 2482 dsi->nonzero_chars, srclen); 2483 gcc_assert (dsi->full_string_p); 2484 adjust_related_strinfos (loc, dsi, srclen); 2485 dsi->dont_invalidate = true; 2486 } 2487 else 2488 { 2489 dsi->nonzero_chars = NULL; 2490 dsi->full_string_p = false; 2491 if (lhs == NULL_TREE && builtin_decl_implicit_p (BUILT_IN_STPCPY)) 2492 dsi->dont_invalidate = true; 2493 } 2494 2495 if (si != NULL) 2496 /* strcat src may not overlap dst, so src doesn't need to be 2497 invalidated either. */ 2498 si->dont_invalidate = true; 2499 2500 /* For now. Could remove the lhs from the call and add 2501 lhs = dst; afterwards. */ 2502 if (lhs) 2503 return; 2504 2505 fn = NULL_TREE; 2506 objsz = NULL_TREE; 2507 switch (bcode) 2508 { 2509 case BUILT_IN_STRCAT: 2510 case BUILT_IN_STRCAT_CHKP: 2511 if (srclen != NULL_TREE) 2512 fn = builtin_decl_implicit (BUILT_IN_MEMCPY); 2513 else 2514 fn = builtin_decl_implicit (BUILT_IN_STRCPY); 2515 break; 2516 case BUILT_IN_STRCAT_CHK: 2517 case BUILT_IN_STRCAT_CHK_CHKP: 2518 if (srclen != NULL_TREE) 2519 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK); 2520 else 2521 fn = builtin_decl_explicit (BUILT_IN_STRCPY_CHK); 2522 objsz = gimple_call_arg (stmt, with_bounds ? 4 : 2); 2523 break; 2524 default: 2525 gcc_unreachable (); 2526 } 2527 2528 if (fn == NULL_TREE) 2529 return; 2530 2531 if (dsi && dstlen) 2532 { 2533 tree type = TREE_TYPE (dstlen); 2534 2535 /* Compute the size of the source sequence, including the nul. */ 2536 tree srcsize = srclen ? srclen : size_zero_node; 2537 srcsize = fold_build2 (PLUS_EXPR, type, srcsize, build_int_cst (type, 1)); 2538 2539 tree sptr = si && si->ptr ? si->ptr : src; 2540 2541 if (!check_bounds_or_overlap (as_a <gcall *>(stmt), dst, sptr, 2542 dstlen, srcsize)) 2543 { 2544 gimple_set_no_warning (stmt, true); 2545 set_no_warning = true; 2546 } 2547 } 2548 2549 tree len = NULL_TREE; 2550 if (srclen != NULL_TREE) 2551 { 2552 args = TYPE_ARG_TYPES (TREE_TYPE (fn)); 2553 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args))); 2554 2555 len = fold_convert_loc (loc, type, unshare_expr (srclen)); 2556 len = fold_build2_loc (loc, PLUS_EXPR, type, len, 2557 build_int_cst (type, 1)); 2558 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true, 2559 GSI_SAME_STMT); 2560 } 2561 if (endptr) 2562 dst = fold_convert_loc (loc, TREE_TYPE (dst), unshare_expr (endptr)); 2563 else 2564 dst = fold_build2_loc (loc, POINTER_PLUS_EXPR, 2565 TREE_TYPE (dst), unshare_expr (dst), 2566 fold_convert_loc (loc, sizetype, 2567 unshare_expr (dstlen))); 2568 dst = force_gimple_operand_gsi (gsi, dst, true, NULL_TREE, true, 2569 GSI_SAME_STMT); 2570 if (dump_file && (dump_flags & TDF_DETAILS) != 0) 2571 { 2572 fprintf (dump_file, "Optimizing: "); 2573 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 2574 } 2575 if (with_bounds) 2576 { 2577 fn = chkp_maybe_create_clone (fn)->decl; 2578 if (srclen != NULL_TREE) 2579 success = update_gimple_call (gsi, fn, 5 + (objsz != NULL_TREE), 2580 dst, 2581 gimple_call_arg (stmt, 1), 2582 src, 2583 gimple_call_arg (stmt, 3), 2584 len, objsz); 2585 else 2586 success = update_gimple_call (gsi, fn, 4 + (objsz != NULL_TREE), 2587 dst, 2588 gimple_call_arg (stmt, 1), 2589 src, 2590 gimple_call_arg (stmt, 3), 2591 objsz); 2592 } 2593 else 2594 if (srclen != NULL_TREE) 2595 success = update_gimple_call (gsi, fn, 3 + (objsz != NULL_TREE), 2596 dst, src, len, objsz); 2597 else 2598 success = update_gimple_call (gsi, fn, 2 + (objsz != NULL_TREE), 2599 dst, src, objsz); 2600 if (success) 2601 { 2602 stmt = gsi_stmt (*gsi); 2603 gimple_call_set_with_bounds (stmt, with_bounds); 2604 update_stmt (stmt); 2605 if (dump_file && (dump_flags & TDF_DETAILS) != 0) 2606 { 2607 fprintf (dump_file, "into: "); 2608 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 2609 } 2610 /* If srclen == NULL, note that current string length can be 2611 computed by transforming this strcpy into stpcpy. */ 2612 if (srclen == NULL_TREE && dsi->dont_invalidate) 2613 dsi->stmt = stmt; 2614 adjust_last_stmt (dsi, stmt, true); 2615 if (srclen != NULL_TREE) 2616 { 2617 laststmt.stmt = stmt; 2618 laststmt.len = srclen; 2619 laststmt.stridx = dsi->idx; 2620 } 2621 } 2622 else if (dump_file && (dump_flags & TDF_DETAILS) != 0) 2623 fprintf (dump_file, "not possible.\n"); 2624 2625 if (set_no_warning) 2626 gimple_set_no_warning (stmt, true); 2627 } 2628 2629 /* Handle a call to malloc or calloc. */ 2630 2631 static void 2632 handle_builtin_malloc (enum built_in_function bcode, gimple_stmt_iterator *gsi) 2633 { 2634 gimple *stmt = gsi_stmt (*gsi); 2635 tree lhs = gimple_call_lhs (stmt); 2636 if (lhs == NULL_TREE) 2637 return; 2638 2639 gcc_assert (get_stridx (lhs) == 0); 2640 int idx = new_stridx (lhs); 2641 tree length = NULL_TREE; 2642 if (bcode == BUILT_IN_CALLOC) 2643 length = build_int_cst (size_type_node, 0); 2644 strinfo *si = new_strinfo (lhs, idx, length, length != NULL_TREE); 2645 if (bcode == BUILT_IN_CALLOC) 2646 si->endptr = lhs; 2647 set_strinfo (idx, si); 2648 si->writable = true; 2649 si->stmt = stmt; 2650 si->dont_invalidate = true; 2651 } 2652 2653 /* Handle a call to memset. 2654 After a call to calloc, memset(,0,) is unnecessary. 2655 memset(malloc(n),0,n) is calloc(n,1). */ 2656 2657 static bool 2658 handle_builtin_memset (gimple_stmt_iterator *gsi) 2659 { 2660 gimple *stmt2 = gsi_stmt (*gsi); 2661 if (!integer_zerop (gimple_call_arg (stmt2, 1))) 2662 return true; 2663 tree ptr = gimple_call_arg (stmt2, 0); 2664 int idx1 = get_stridx (ptr); 2665 if (idx1 <= 0) 2666 return true; 2667 strinfo *si1 = get_strinfo (idx1); 2668 if (!si1) 2669 return true; 2670 gimple *stmt1 = si1->stmt; 2671 if (!stmt1 || !is_gimple_call (stmt1)) 2672 return true; 2673 tree callee1 = gimple_call_fndecl (stmt1); 2674 if (!valid_builtin_call (stmt1)) 2675 return true; 2676 enum built_in_function code1 = DECL_FUNCTION_CODE (callee1); 2677 tree size = gimple_call_arg (stmt2, 2); 2678 if (code1 == BUILT_IN_CALLOC) 2679 /* Not touching stmt1 */ ; 2680 else if (code1 == BUILT_IN_MALLOC 2681 && operand_equal_p (gimple_call_arg (stmt1, 0), size, 0)) 2682 { 2683 gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt1); 2684 update_gimple_call (&gsi1, builtin_decl_implicit (BUILT_IN_CALLOC), 2, 2685 size, build_one_cst (size_type_node)); 2686 si1->nonzero_chars = build_int_cst (size_type_node, 0); 2687 si1->full_string_p = true; 2688 si1->stmt = gsi_stmt (gsi1); 2689 } 2690 else 2691 return true; 2692 tree lhs = gimple_call_lhs (stmt2); 2693 unlink_stmt_vdef (stmt2); 2694 if (lhs) 2695 { 2696 gimple *assign = gimple_build_assign (lhs, ptr); 2697 gsi_replace (gsi, assign, false); 2698 } 2699 else 2700 { 2701 gsi_remove (gsi, true); 2702 release_defs (stmt2); 2703 } 2704 2705 return false; 2706 } 2707 2708 /* Handle a call to memcmp. We try to handle small comparisons by 2709 converting them to load and compare, and replacing the call to memcmp 2710 with a __builtin_memcmp_eq call where possible. */ 2711 2712 static bool 2713 handle_builtin_memcmp (gimple_stmt_iterator *gsi) 2714 { 2715 gcall *stmt2 = as_a <gcall *> (gsi_stmt (*gsi)); 2716 tree res = gimple_call_lhs (stmt2); 2717 tree arg1 = gimple_call_arg (stmt2, 0); 2718 tree arg2 = gimple_call_arg (stmt2, 1); 2719 tree len = gimple_call_arg (stmt2, 2); 2720 unsigned HOST_WIDE_INT leni; 2721 use_operand_p use_p; 2722 imm_use_iterator iter; 2723 2724 if (!res) 2725 return true; 2726 2727 FOR_EACH_IMM_USE_FAST (use_p, iter, res) 2728 { 2729 gimple *ustmt = USE_STMT (use_p); 2730 2731 if (is_gimple_debug (ustmt)) 2732 continue; 2733 if (gimple_code (ustmt) == GIMPLE_ASSIGN) 2734 { 2735 gassign *asgn = as_a <gassign *> (ustmt); 2736 tree_code code = gimple_assign_rhs_code (asgn); 2737 if ((code != EQ_EXPR && code != NE_EXPR) 2738 || !integer_zerop (gimple_assign_rhs2 (asgn))) 2739 return true; 2740 } 2741 else if (gimple_code (ustmt) == GIMPLE_COND) 2742 { 2743 tree_code code = gimple_cond_code (ustmt); 2744 if ((code != EQ_EXPR && code != NE_EXPR) 2745 || !integer_zerop (gimple_cond_rhs (ustmt))) 2746 return true; 2747 } 2748 else 2749 return true; 2750 } 2751 2752 if (tree_fits_uhwi_p (len) 2753 && (leni = tree_to_uhwi (len)) <= GET_MODE_SIZE (word_mode) 2754 && pow2p_hwi (leni)) 2755 { 2756 leni *= CHAR_TYPE_SIZE; 2757 unsigned align1 = get_pointer_alignment (arg1); 2758 unsigned align2 = get_pointer_alignment (arg2); 2759 unsigned align = MIN (align1, align2); 2760 scalar_int_mode mode; 2761 if (int_mode_for_size (leni, 1).exists (&mode) 2762 && (align >= leni || !targetm.slow_unaligned_access (mode, align))) 2763 { 2764 location_t loc = gimple_location (stmt2); 2765 tree type, off; 2766 type = build_nonstandard_integer_type (leni, 1); 2767 gcc_assert (known_eq (GET_MODE_BITSIZE (TYPE_MODE (type)), leni)); 2768 tree ptrtype = build_pointer_type_for_mode (char_type_node, 2769 ptr_mode, true); 2770 off = build_int_cst (ptrtype, 0); 2771 arg1 = build2_loc (loc, MEM_REF, type, arg1, off); 2772 arg2 = build2_loc (loc, MEM_REF, type, arg2, off); 2773 tree tem1 = fold_const_aggregate_ref (arg1); 2774 if (tem1) 2775 arg1 = tem1; 2776 tree tem2 = fold_const_aggregate_ref (arg2); 2777 if (tem2) 2778 arg2 = tem2; 2779 res = fold_convert_loc (loc, TREE_TYPE (res), 2780 fold_build2_loc (loc, NE_EXPR, 2781 boolean_type_node, 2782 arg1, arg2)); 2783 gimplify_and_update_call_from_tree (gsi, res); 2784 return false; 2785 } 2786 } 2787 2788 gimple_call_set_fndecl (stmt2, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ)); 2789 return false; 2790 } 2791 2792 /* Handle a POINTER_PLUS_EXPR statement. 2793 For p = "abcd" + 2; compute associated length, or if 2794 p = q + off is pointing to a '\0' character of a string, call 2795 zero_length_string on it. */ 2796 2797 static void 2798 handle_pointer_plus (gimple_stmt_iterator *gsi) 2799 { 2800 gimple *stmt = gsi_stmt (*gsi); 2801 tree lhs = gimple_assign_lhs (stmt), off; 2802 int idx = get_stridx (gimple_assign_rhs1 (stmt)); 2803 strinfo *si, *zsi; 2804 2805 if (idx == 0) 2806 return; 2807 2808 if (idx < 0) 2809 { 2810 tree off = gimple_assign_rhs2 (stmt); 2811 if (tree_fits_uhwi_p (off) 2812 && tree_to_uhwi (off) <= (unsigned HOST_WIDE_INT) ~idx) 2813 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] 2814 = ~(~idx - (int) tree_to_uhwi (off)); 2815 return; 2816 } 2817 2818 si = get_strinfo (idx); 2819 if (si == NULL || si->nonzero_chars == NULL_TREE) 2820 return; 2821 2822 off = gimple_assign_rhs2 (stmt); 2823 zsi = NULL; 2824 if (si->full_string_p && operand_equal_p (si->nonzero_chars, off, 0)) 2825 zsi = zero_length_string (lhs, si); 2826 else if (TREE_CODE (off) == SSA_NAME) 2827 { 2828 gimple *def_stmt = SSA_NAME_DEF_STMT (off); 2829 if (gimple_assign_single_p (def_stmt) 2830 && si->full_string_p 2831 && operand_equal_p (si->nonzero_chars, 2832 gimple_assign_rhs1 (def_stmt), 0)) 2833 zsi = zero_length_string (lhs, si); 2834 } 2835 if (zsi != NULL 2836 && si->endptr != NULL_TREE 2837 && si->endptr != lhs 2838 && TREE_CODE (si->endptr) == SSA_NAME) 2839 { 2840 enum tree_code rhs_code 2841 = useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (si->endptr)) 2842 ? SSA_NAME : NOP_EXPR; 2843 gimple_assign_set_rhs_with_ops (gsi, rhs_code, si->endptr); 2844 gcc_assert (gsi_stmt (*gsi) == stmt); 2845 update_stmt (stmt); 2846 } 2847 } 2848 2849 /* If RHS, either directly or indirectly, refers to a string of constant 2850 length, return it. Otherwise return a negative value. */ 2851 2852 static HOST_WIDE_INT 2853 get_string_cst_length (tree rhs) 2854 { 2855 if (TREE_CODE (rhs) == MEM_REF 2856 && integer_zerop (TREE_OPERAND (rhs, 1))) 2857 { 2858 rhs = TREE_OPERAND (rhs, 0); 2859 if (TREE_CODE (rhs) == ADDR_EXPR) 2860 { 2861 tree rhs_addr = rhs; 2862 2863 rhs = TREE_OPERAND (rhs, 0); 2864 if (TREE_CODE (rhs) != STRING_CST) 2865 { 2866 int idx = get_stridx (rhs_addr); 2867 if (idx > 0) 2868 { 2869 strinfo *si = get_strinfo (idx); 2870 if (si 2871 && si->full_string_p 2872 && tree_fits_shwi_p (si->nonzero_chars)) 2873 return tree_to_shwi (si->nonzero_chars); 2874 } 2875 } 2876 } 2877 } 2878 2879 if (TREE_CODE (rhs) == VAR_DECL 2880 && TREE_READONLY (rhs)) 2881 rhs = DECL_INITIAL (rhs); 2882 2883 if (rhs && TREE_CODE (rhs) == STRING_CST) 2884 return strlen (TREE_STRING_POINTER (rhs)); 2885 2886 return -1; 2887 } 2888 2889 /* Handle a single character store. */ 2890 2891 static bool 2892 handle_char_store (gimple_stmt_iterator *gsi) 2893 { 2894 int idx = -1; 2895 strinfo *si = NULL; 2896 gimple *stmt = gsi_stmt (*gsi); 2897 tree ssaname = NULL_TREE, lhs = gimple_assign_lhs (stmt); 2898 tree rhs = gimple_assign_rhs1 (stmt); 2899 unsigned HOST_WIDE_INT offset = 0; 2900 2901 if (TREE_CODE (lhs) == MEM_REF 2902 && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME) 2903 { 2904 tree mem_offset = TREE_OPERAND (lhs, 1); 2905 if (tree_fits_uhwi_p (mem_offset)) 2906 { 2907 /* Get the strinfo for the base, and use it if it starts with at 2908 least OFFSET nonzero characters. This is trivially true if 2909 OFFSET is zero. */ 2910 offset = tree_to_uhwi (mem_offset); 2911 idx = get_stridx (TREE_OPERAND (lhs, 0)); 2912 if (idx > 0) 2913 si = get_strinfo (idx); 2914 if (offset == 0) 2915 ssaname = TREE_OPERAND (lhs, 0); 2916 else if (si == NULL || compare_nonzero_chars (si, offset) < 0) 2917 return true; 2918 } 2919 } 2920 else 2921 { 2922 idx = get_addr_stridx (lhs, NULL_TREE, &offset); 2923 if (idx > 0) 2924 si = get_strinfo (idx); 2925 } 2926 2927 bool storing_zero_p = initializer_zerop (rhs); 2928 bool storing_nonzero_p = (!storing_zero_p 2929 && TREE_CODE (rhs) == INTEGER_CST 2930 && integer_nonzerop (rhs)); 2931 /* Set to the length of the string being assigned if known. */ 2932 HOST_WIDE_INT rhslen; 2933 2934 if (si != NULL) 2935 { 2936 int cmp = compare_nonzero_chars (si, offset); 2937 gcc_assert (offset == 0 || cmp >= 0); 2938 if (storing_zero_p && cmp == 0 && si->full_string_p) 2939 { 2940 /* When overwriting a '\0' with a '\0', the store can be removed 2941 if we know it has been stored in the current function. */ 2942 if (!stmt_could_throw_p (stmt) && si->writable) 2943 { 2944 unlink_stmt_vdef (stmt); 2945 release_defs (stmt); 2946 gsi_remove (gsi, true); 2947 return false; 2948 } 2949 else 2950 { 2951 si->writable = true; 2952 gsi_next (gsi); 2953 return false; 2954 } 2955 } 2956 /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0', 2957 and if we aren't storing '\0', we know that the length of the 2958 string and any other zero terminated string in memory remains 2959 the same. In that case we move to the next gimple statement and 2960 return to signal the caller that it shouldn't invalidate anything. 2961 2962 This is benefical for cases like: 2963 2964 char p[20]; 2965 void foo (char *q) 2966 { 2967 strcpy (p, "foobar"); 2968 size_t len = strlen (p); // This can be optimized into 6 2969 size_t len2 = strlen (q); // This has to be computed 2970 p[0] = 'X'; 2971 size_t len3 = strlen (p); // This can be optimized into 6 2972 size_t len4 = strlen (q); // This can be optimized into len2 2973 bar (len, len2, len3, len4); 2974 } 2975 */ 2976 else if (storing_nonzero_p && cmp > 0) 2977 { 2978 gsi_next (gsi); 2979 return false; 2980 } 2981 else if (storing_zero_p || storing_nonzero_p || (offset != 0 && cmp > 0)) 2982 { 2983 /* When storing_nonzero_p, we know that the string now starts 2984 with OFFSET + 1 nonzero characters, but don't know whether 2985 there's a following nul terminator. 2986 2987 When storing_zero_p, we know that the string is now OFFSET 2988 characters long. 2989 2990 Otherwise, we're storing an unknown value at offset OFFSET, 2991 so need to clip the nonzero_chars to OFFSET. */ 2992 location_t loc = gimple_location (stmt); 2993 tree oldlen = si->nonzero_chars; 2994 if (cmp == 0 && si->full_string_p) 2995 /* We're overwriting the nul terminator with a nonzero or 2996 unknown character. If the previous stmt was a memcpy, 2997 its length may be decreased. */ 2998 adjust_last_stmt (si, stmt, false); 2999 si = unshare_strinfo (si); 3000 if (storing_nonzero_p) 3001 si->nonzero_chars = build_int_cst (size_type_node, offset + 1); 3002 else 3003 si->nonzero_chars = build_int_cst (size_type_node, offset); 3004 si->full_string_p = storing_zero_p; 3005 if (storing_zero_p 3006 && ssaname 3007 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname)) 3008 si->endptr = ssaname; 3009 else 3010 si->endptr = NULL; 3011 si->next = 0; 3012 si->stmt = NULL; 3013 si->writable = true; 3014 si->dont_invalidate = true; 3015 if (oldlen) 3016 { 3017 tree adj = fold_build2_loc (loc, MINUS_EXPR, size_type_node, 3018 si->nonzero_chars, oldlen); 3019 adjust_related_strinfos (loc, si, adj); 3020 } 3021 else 3022 si->prev = 0; 3023 } 3024 } 3025 else if (idx == 0 && (storing_zero_p || storing_nonzero_p)) 3026 { 3027 if (ssaname) 3028 idx = new_stridx (ssaname); 3029 else 3030 idx = new_addr_stridx (lhs); 3031 if (idx != 0) 3032 { 3033 tree ptr = (ssaname ? ssaname : build_fold_addr_expr (lhs)); 3034 tree len = storing_nonzero_p ? size_one_node : size_zero_node; 3035 si = new_strinfo (ptr, idx, len, storing_zero_p); 3036 set_strinfo (idx, si); 3037 if (storing_zero_p 3038 && ssaname 3039 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname)) 3040 si->endptr = ssaname; 3041 si->dont_invalidate = true; 3042 si->writable = true; 3043 } 3044 } 3045 else if (idx == 0 3046 && (rhslen = get_string_cst_length (gimple_assign_rhs1 (stmt))) >= 0 3047 && ssaname == NULL_TREE 3048 && TREE_CODE (TREE_TYPE (lhs)) == ARRAY_TYPE) 3049 { 3050 HOST_WIDE_INT a = int_size_in_bytes (TREE_TYPE (lhs)); 3051 if (a > 0 && (unsigned HOST_WIDE_INT) a > (unsigned HOST_WIDE_INT) rhslen) 3052 { 3053 int idx = new_addr_stridx (lhs); 3054 if (idx != 0) 3055 { 3056 si = new_strinfo (build_fold_addr_expr (lhs), idx, 3057 build_int_cst (size_type_node, rhslen), true); 3058 set_strinfo (idx, si); 3059 si->dont_invalidate = true; 3060 } 3061 } 3062 } 3063 3064 if (si != NULL && offset == 0 && storing_zero_p) 3065 { 3066 /* Allow adjust_last_stmt to remove it if the stored '\0' 3067 is immediately overwritten. */ 3068 laststmt.stmt = stmt; 3069 laststmt.len = build_int_cst (size_type_node, 1); 3070 laststmt.stridx = si->idx; 3071 } 3072 return true; 3073 } 3074 3075 /* Try to fold strstr (s, t) eq/ne s to strncmp (s, t, strlen (t)) eq/ne 0. */ 3076 3077 static void 3078 fold_strstr_to_strncmp (tree rhs1, tree rhs2, gimple *stmt) 3079 { 3080 if (TREE_CODE (rhs1) != SSA_NAME 3081 || TREE_CODE (rhs2) != SSA_NAME) 3082 return; 3083 3084 gimple *call_stmt = NULL; 3085 for (int pass = 0; pass < 2; pass++) 3086 { 3087 gimple *g = SSA_NAME_DEF_STMT (rhs1); 3088 if (gimple_call_builtin_p (g, BUILT_IN_STRSTR) 3089 && has_single_use (rhs1) 3090 && gimple_call_arg (g, 0) == rhs2) 3091 { 3092 call_stmt = g; 3093 break; 3094 } 3095 std::swap (rhs1, rhs2); 3096 } 3097 3098 if (call_stmt) 3099 { 3100 tree arg0 = gimple_call_arg (call_stmt, 0); 3101 3102 if (arg0 == rhs2) 3103 { 3104 tree arg1 = gimple_call_arg (call_stmt, 1); 3105 tree arg1_len = NULL_TREE; 3106 int idx = get_stridx (arg1); 3107 3108 if (idx) 3109 { 3110 if (idx < 0) 3111 arg1_len = build_int_cst (size_type_node, ~idx); 3112 else 3113 { 3114 strinfo *si = get_strinfo (idx); 3115 if (si) 3116 arg1_len = get_string_length (si); 3117 } 3118 } 3119 3120 if (arg1_len != NULL_TREE) 3121 { 3122 gimple_stmt_iterator gsi = gsi_for_stmt (call_stmt); 3123 tree strncmp_decl = builtin_decl_explicit (BUILT_IN_STRNCMP); 3124 3125 if (!is_gimple_val (arg1_len)) 3126 { 3127 tree arg1_len_tmp = make_ssa_name (TREE_TYPE (arg1_len)); 3128 gassign *arg1_stmt = gimple_build_assign (arg1_len_tmp, 3129 arg1_len); 3130 gsi_insert_before (&gsi, arg1_stmt, GSI_SAME_STMT); 3131 arg1_len = arg1_len_tmp; 3132 } 3133 3134 gcall *strncmp_call = gimple_build_call (strncmp_decl, 3, 3135 arg0, arg1, arg1_len); 3136 tree strncmp_lhs = make_ssa_name (integer_type_node); 3137 gimple_set_vuse (strncmp_call, gimple_vuse (call_stmt)); 3138 gimple_call_set_lhs (strncmp_call, strncmp_lhs); 3139 gsi_remove (&gsi, true); 3140 gsi_insert_before (&gsi, strncmp_call, GSI_SAME_STMT); 3141 tree zero = build_zero_cst (TREE_TYPE (strncmp_lhs)); 3142 3143 if (is_gimple_assign (stmt)) 3144 { 3145 if (gimple_assign_rhs_code (stmt) == COND_EXPR) 3146 { 3147 tree cond = gimple_assign_rhs1 (stmt); 3148 TREE_OPERAND (cond, 0) = strncmp_lhs; 3149 TREE_OPERAND (cond, 1) = zero; 3150 } 3151 else 3152 { 3153 gimple_assign_set_rhs1 (stmt, strncmp_lhs); 3154 gimple_assign_set_rhs2 (stmt, zero); 3155 } 3156 } 3157 else 3158 { 3159 gcond *cond = as_a<gcond *> (stmt); 3160 gimple_cond_set_lhs (cond, strncmp_lhs); 3161 gimple_cond_set_rhs (cond, zero); 3162 } 3163 update_stmt (stmt); 3164 } 3165 } 3166 } 3167 } 3168 3169 /* Attempt to check for validity of the performed access a single statement 3170 at *GSI using string length knowledge, and to optimize it. 3171 If the given basic block needs clean-up of EH, CLEANUP_EH is set to 3172 true. */ 3173 3174 static bool 3175 strlen_check_and_optimize_stmt (gimple_stmt_iterator *gsi, bool *cleanup_eh) 3176 { 3177 gimple *stmt = gsi_stmt (*gsi); 3178 3179 if (is_gimple_call (stmt)) 3180 { 3181 tree callee = gimple_call_fndecl (stmt); 3182 if (valid_builtin_call (stmt)) 3183 switch (DECL_FUNCTION_CODE (callee)) 3184 { 3185 case BUILT_IN_STRLEN: 3186 case BUILT_IN_STRLEN_CHKP: 3187 handle_builtin_strlen (gsi); 3188 break; 3189 case BUILT_IN_STRCHR: 3190 case BUILT_IN_STRCHR_CHKP: 3191 handle_builtin_strchr (gsi); 3192 break; 3193 case BUILT_IN_STRCPY: 3194 case BUILT_IN_STRCPY_CHK: 3195 case BUILT_IN_STPCPY: 3196 case BUILT_IN_STPCPY_CHK: 3197 case BUILT_IN_STRCPY_CHKP: 3198 case BUILT_IN_STRCPY_CHK_CHKP: 3199 case BUILT_IN_STPCPY_CHKP: 3200 case BUILT_IN_STPCPY_CHK_CHKP: 3201 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee), gsi); 3202 break; 3203 3204 case BUILT_IN_STRNCAT: 3205 case BUILT_IN_STRNCAT_CHK: 3206 handle_builtin_strncat (DECL_FUNCTION_CODE (callee), gsi); 3207 break; 3208 3209 case BUILT_IN_STPNCPY: 3210 case BUILT_IN_STPNCPY_CHK: 3211 case BUILT_IN_STRNCPY: 3212 case BUILT_IN_STRNCPY_CHK: 3213 handle_builtin_stxncpy (DECL_FUNCTION_CODE (callee), gsi); 3214 break; 3215 3216 case BUILT_IN_MEMCPY: 3217 case BUILT_IN_MEMCPY_CHK: 3218 case BUILT_IN_MEMPCPY: 3219 case BUILT_IN_MEMPCPY_CHK: 3220 case BUILT_IN_MEMCPY_CHKP: 3221 case BUILT_IN_MEMCPY_CHK_CHKP: 3222 case BUILT_IN_MEMPCPY_CHKP: 3223 case BUILT_IN_MEMPCPY_CHK_CHKP: 3224 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi); 3225 break; 3226 case BUILT_IN_STRCAT: 3227 case BUILT_IN_STRCAT_CHK: 3228 case BUILT_IN_STRCAT_CHKP: 3229 case BUILT_IN_STRCAT_CHK_CHKP: 3230 handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi); 3231 break; 3232 case BUILT_IN_MALLOC: 3233 case BUILT_IN_CALLOC: 3234 handle_builtin_malloc (DECL_FUNCTION_CODE (callee), gsi); 3235 break; 3236 case BUILT_IN_MEMSET: 3237 if (!handle_builtin_memset (gsi)) 3238 return false; 3239 break; 3240 case BUILT_IN_MEMCMP: 3241 if (!handle_builtin_memcmp (gsi)) 3242 return false; 3243 break; 3244 default: 3245 break; 3246 } 3247 } 3248 else if (is_gimple_assign (stmt) && !gimple_clobber_p (stmt)) 3249 { 3250 tree lhs = gimple_assign_lhs (stmt); 3251 3252 if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs))) 3253 { 3254 if (gimple_assign_single_p (stmt) 3255 || (gimple_assign_cast_p (stmt) 3256 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt))))) 3257 { 3258 int idx = get_stridx (gimple_assign_rhs1 (stmt)); 3259 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = idx; 3260 } 3261 else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR) 3262 handle_pointer_plus (gsi); 3263 } 3264 else if (TREE_CODE (lhs) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (lhs))) 3265 { 3266 enum tree_code code = gimple_assign_rhs_code (stmt); 3267 if (code == COND_EXPR) 3268 { 3269 tree cond = gimple_assign_rhs1 (stmt); 3270 enum tree_code cond_code = TREE_CODE (cond); 3271 3272 if (cond_code == EQ_EXPR || cond_code == NE_EXPR) 3273 fold_strstr_to_strncmp (TREE_OPERAND (cond, 0), 3274 TREE_OPERAND (cond, 1), stmt); 3275 } 3276 else if (code == EQ_EXPR || code == NE_EXPR) 3277 fold_strstr_to_strncmp (gimple_assign_rhs1 (stmt), 3278 gimple_assign_rhs2 (stmt), stmt); 3279 else if (gimple_assign_load_p (stmt) 3280 && TREE_CODE (TREE_TYPE (lhs)) == INTEGER_TYPE 3281 && TYPE_MODE (TREE_TYPE (lhs)) == TYPE_MODE (char_type_node) 3282 && (TYPE_PRECISION (TREE_TYPE (lhs)) 3283 == TYPE_PRECISION (char_type_node)) 3284 && !gimple_has_volatile_ops (stmt)) 3285 { 3286 tree off = integer_zero_node; 3287 unsigned HOST_WIDE_INT coff = 0; 3288 int idx = 0; 3289 tree rhs1 = gimple_assign_rhs1 (stmt); 3290 if (code == MEM_REF) 3291 { 3292 idx = get_stridx (TREE_OPERAND (rhs1, 0)); 3293 if (idx > 0) 3294 { 3295 strinfo *si = get_strinfo (idx); 3296 if (si 3297 && si->nonzero_chars 3298 && TREE_CODE (si->nonzero_chars) == INTEGER_CST 3299 && (wi::to_widest (si->nonzero_chars) 3300 >= wi::to_widest (off))) 3301 off = TREE_OPERAND (rhs1, 1); 3302 else 3303 /* This case is not useful. See if get_addr_stridx 3304 returns something usable. */ 3305 idx = 0; 3306 } 3307 } 3308 if (idx <= 0) 3309 idx = get_addr_stridx (rhs1, NULL_TREE, &coff); 3310 if (idx > 0) 3311 { 3312 strinfo *si = get_strinfo (idx); 3313 if (si 3314 && si->nonzero_chars 3315 && TREE_CODE (si->nonzero_chars) == INTEGER_CST) 3316 { 3317 widest_int w1 = wi::to_widest (si->nonzero_chars); 3318 widest_int w2 = wi::to_widest (off) + coff; 3319 if (w1 == w2 3320 && si->full_string_p) 3321 { 3322 if (dump_file && (dump_flags & TDF_DETAILS) != 0) 3323 { 3324 fprintf (dump_file, "Optimizing: "); 3325 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 3326 } 3327 3328 /* Reading the final '\0' character. */ 3329 tree zero = build_int_cst (TREE_TYPE (lhs), 0); 3330 gimple_set_vuse (stmt, NULL_TREE); 3331 gimple_assign_set_rhs_from_tree (gsi, zero); 3332 *cleanup_eh 3333 |= maybe_clean_or_replace_eh_stmt (stmt, 3334 gsi_stmt (*gsi)); 3335 stmt = gsi_stmt (*gsi); 3336 update_stmt (stmt); 3337 3338 if (dump_file && (dump_flags & TDF_DETAILS) != 0) 3339 { 3340 fprintf (dump_file, "into: "); 3341 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 3342 } 3343 } 3344 else if (w1 > w2) 3345 { 3346 /* Reading a character before the final '\0' 3347 character. Just set the value range to ~[0, 0] 3348 if we don't have anything better. */ 3349 wide_int min, max; 3350 tree type = TREE_TYPE (lhs); 3351 enum value_range_type vr 3352 = get_range_info (lhs, &min, &max); 3353 if (vr == VR_VARYING 3354 || (vr == VR_RANGE 3355 && min == wi::min_value (TYPE_PRECISION (type), 3356 TYPE_SIGN (type)) 3357 && max == wi::max_value (TYPE_PRECISION (type), 3358 TYPE_SIGN (type)))) 3359 set_range_info (lhs, VR_ANTI_RANGE, 3360 wi::zero (TYPE_PRECISION (type)), 3361 wi::zero (TYPE_PRECISION (type))); 3362 } 3363 } 3364 } 3365 } 3366 3367 if (strlen_to_stridx) 3368 { 3369 tree rhs1 = gimple_assign_rhs1 (stmt); 3370 if (stridx_strlenloc *ps = strlen_to_stridx->get (rhs1)) 3371 strlen_to_stridx->put (lhs, stridx_strlenloc (*ps)); 3372 } 3373 } 3374 else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs)) 3375 { 3376 tree type = TREE_TYPE (lhs); 3377 if (TREE_CODE (type) == ARRAY_TYPE) 3378 type = TREE_TYPE (type); 3379 if (TREE_CODE (type) == INTEGER_TYPE 3380 && TYPE_MODE (type) == TYPE_MODE (char_type_node) 3381 && TYPE_PRECISION (type) == TYPE_PRECISION (char_type_node)) 3382 { 3383 if (! handle_char_store (gsi)) 3384 return false; 3385 } 3386 } 3387 } 3388 else if (gcond *cond = dyn_cast<gcond *> (stmt)) 3389 { 3390 enum tree_code code = gimple_cond_code (cond); 3391 if (code == EQ_EXPR || code == NE_EXPR) 3392 fold_strstr_to_strncmp (gimple_cond_lhs (stmt), 3393 gimple_cond_rhs (stmt), stmt); 3394 } 3395 3396 if (gimple_vdef (stmt)) 3397 maybe_invalidate (stmt); 3398 return true; 3399 } 3400 3401 /* Recursively call maybe_invalidate on stmts that might be executed 3402 in between dombb and current bb and that contain a vdef. Stop when 3403 *count stmts are inspected, or if the whole strinfo vector has 3404 been invalidated. */ 3405 3406 static void 3407 do_invalidate (basic_block dombb, gimple *phi, bitmap visited, int *count) 3408 { 3409 unsigned int i, n = gimple_phi_num_args (phi); 3410 3411 for (i = 0; i < n; i++) 3412 { 3413 tree vuse = gimple_phi_arg_def (phi, i); 3414 gimple *stmt = SSA_NAME_DEF_STMT (vuse); 3415 basic_block bb = gimple_bb (stmt); 3416 if (bb == NULL 3417 || bb == dombb 3418 || !bitmap_set_bit (visited, bb->index) 3419 || !dominated_by_p (CDI_DOMINATORS, bb, dombb)) 3420 continue; 3421 while (1) 3422 { 3423 if (gimple_code (stmt) == GIMPLE_PHI) 3424 { 3425 do_invalidate (dombb, stmt, visited, count); 3426 if (*count == 0) 3427 return; 3428 break; 3429 } 3430 if (--*count == 0) 3431 return; 3432 if (!maybe_invalidate (stmt)) 3433 { 3434 *count = 0; 3435 return; 3436 } 3437 vuse = gimple_vuse (stmt); 3438 stmt = SSA_NAME_DEF_STMT (vuse); 3439 if (gimple_bb (stmt) != bb) 3440 { 3441 bb = gimple_bb (stmt); 3442 if (bb == NULL 3443 || bb == dombb 3444 || !bitmap_set_bit (visited, bb->index) 3445 || !dominated_by_p (CDI_DOMINATORS, bb, dombb)) 3446 break; 3447 } 3448 } 3449 } 3450 } 3451 3452 class strlen_dom_walker : public dom_walker 3453 { 3454 public: 3455 strlen_dom_walker (cdi_direction direction) 3456 : dom_walker (direction), m_cleanup_cfg (false) 3457 {} 3458 3459 virtual edge before_dom_children (basic_block); 3460 virtual void after_dom_children (basic_block); 3461 3462 /* Flag that will trigger TODO_cleanup_cfg to be returned in strlen 3463 execute function. */ 3464 bool m_cleanup_cfg; 3465 }; 3466 3467 /* Callback for walk_dominator_tree. Attempt to optimize various 3468 string ops by remembering string lengths pointed by pointer SSA_NAMEs. */ 3469 3470 edge 3471 strlen_dom_walker::before_dom_children (basic_block bb) 3472 { 3473 basic_block dombb = get_immediate_dominator (CDI_DOMINATORS, bb); 3474 3475 if (dombb == NULL) 3476 stridx_to_strinfo = NULL; 3477 else 3478 { 3479 stridx_to_strinfo = ((vec<strinfo *, va_heap, vl_embed> *) dombb->aux); 3480 if (stridx_to_strinfo) 3481 { 3482 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); 3483 gsi_next (&gsi)) 3484 { 3485 gphi *phi = gsi.phi (); 3486 if (virtual_operand_p (gimple_phi_result (phi))) 3487 { 3488 bitmap visited = BITMAP_ALLOC (NULL); 3489 int count_vdef = 100; 3490 do_invalidate (dombb, phi, visited, &count_vdef); 3491 BITMAP_FREE (visited); 3492 if (count_vdef == 0) 3493 { 3494 /* If there were too many vdefs in between immediate 3495 dominator and current bb, invalidate everything. 3496 If stridx_to_strinfo has been unshared, we need 3497 to free it, otherwise just set it to NULL. */ 3498 if (!strinfo_shared ()) 3499 { 3500 unsigned int i; 3501 strinfo *si; 3502 3503 for (i = 1; 3504 vec_safe_iterate (stridx_to_strinfo, i, &si); 3505 ++i) 3506 { 3507 free_strinfo (si); 3508 (*stridx_to_strinfo)[i] = NULL; 3509 } 3510 } 3511 else 3512 stridx_to_strinfo = NULL; 3513 } 3514 break; 3515 } 3516 } 3517 } 3518 } 3519 3520 /* If all PHI arguments have the same string index, the PHI result 3521 has it as well. */ 3522 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); 3523 gsi_next (&gsi)) 3524 { 3525 gphi *phi = gsi.phi (); 3526 tree result = gimple_phi_result (phi); 3527 if (!virtual_operand_p (result) && POINTER_TYPE_P (TREE_TYPE (result))) 3528 { 3529 int idx = get_stridx (gimple_phi_arg_def (phi, 0)); 3530 if (idx != 0) 3531 { 3532 unsigned int i, n = gimple_phi_num_args (phi); 3533 for (i = 1; i < n; i++) 3534 if (idx != get_stridx (gimple_phi_arg_def (phi, i))) 3535 break; 3536 if (i == n) 3537 ssa_ver_to_stridx[SSA_NAME_VERSION (result)] = idx; 3538 } 3539 } 3540 } 3541 3542 bool cleanup_eh = false; 3543 3544 /* Attempt to optimize individual statements. */ 3545 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) 3546 if (strlen_check_and_optimize_stmt (&gsi, &cleanup_eh)) 3547 gsi_next (&gsi); 3548 3549 if (cleanup_eh && gimple_purge_dead_eh_edges (bb)) 3550 m_cleanup_cfg = true; 3551 3552 bb->aux = stridx_to_strinfo; 3553 if (vec_safe_length (stridx_to_strinfo) && !strinfo_shared ()) 3554 (*stridx_to_strinfo)[0] = (strinfo *) bb; 3555 return NULL; 3556 } 3557 3558 /* Callback for walk_dominator_tree. Free strinfo vector if it is 3559 owned by the current bb, clear bb->aux. */ 3560 3561 void 3562 strlen_dom_walker::after_dom_children (basic_block bb) 3563 { 3564 if (bb->aux) 3565 { 3566 stridx_to_strinfo = ((vec<strinfo *, va_heap, vl_embed> *) bb->aux); 3567 if (vec_safe_length (stridx_to_strinfo) 3568 && (*stridx_to_strinfo)[0] == (strinfo *) bb) 3569 { 3570 unsigned int i; 3571 strinfo *si; 3572 3573 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i) 3574 free_strinfo (si); 3575 vec_free (stridx_to_strinfo); 3576 } 3577 bb->aux = NULL; 3578 } 3579 } 3580 3581 /* Main entry point. */ 3582 3583 namespace { 3584 3585 const pass_data pass_data_strlen = 3586 { 3587 GIMPLE_PASS, /* type */ 3588 "strlen", /* name */ 3589 OPTGROUP_NONE, /* optinfo_flags */ 3590 TV_TREE_STRLEN, /* tv_id */ 3591 ( PROP_cfg | PROP_ssa ), /* properties_required */ 3592 0, /* properties_provided */ 3593 0, /* properties_destroyed */ 3594 0, /* todo_flags_start */ 3595 0, /* todo_flags_finish */ 3596 }; 3597 3598 class pass_strlen : public gimple_opt_pass 3599 { 3600 public: 3601 pass_strlen (gcc::context *ctxt) 3602 : gimple_opt_pass (pass_data_strlen, ctxt) 3603 {} 3604 3605 /* opt_pass methods: */ 3606 virtual bool gate (function *) { return flag_optimize_strlen != 0; } 3607 virtual unsigned int execute (function *); 3608 3609 }; // class pass_strlen 3610 3611 unsigned int 3612 pass_strlen::execute (function *fun) 3613 { 3614 gcc_assert (!strlen_to_stridx); 3615 if (warn_stringop_overflow || warn_stringop_truncation) 3616 strlen_to_stridx = new hash_map<tree, stridx_strlenloc> (); 3617 3618 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names); 3619 max_stridx = 1; 3620 3621 calculate_dominance_info (CDI_DOMINATORS); 3622 3623 /* String length optimization is implemented as a walk of the dominator 3624 tree and a forward walk of statements within each block. */ 3625 strlen_dom_walker walker (CDI_DOMINATORS); 3626 walker.walk (fun->cfg->x_entry_block_ptr); 3627 3628 ssa_ver_to_stridx.release (); 3629 strinfo_pool.release (); 3630 if (decl_to_stridxlist_htab) 3631 { 3632 obstack_free (&stridx_obstack, NULL); 3633 delete decl_to_stridxlist_htab; 3634 decl_to_stridxlist_htab = NULL; 3635 } 3636 laststmt.stmt = NULL; 3637 laststmt.len = NULL_TREE; 3638 laststmt.stridx = 0; 3639 3640 if (strlen_to_stridx) 3641 { 3642 strlen_to_stridx->empty (); 3643 delete strlen_to_stridx; 3644 strlen_to_stridx = NULL; 3645 } 3646 3647 return walker.m_cleanup_cfg ? TODO_cleanup_cfg : 0; 3648 } 3649 3650 } // anon namespace 3651 3652 gimple_opt_pass * 3653 make_pass_strlen (gcc::context *ctxt) 3654 { 3655 return new pass_strlen (ctxt); 3656 } 3657