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