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