1/* String length optimization 2 Copyright (C) 2011-2015 Free Software Foundation, Inc. 3 Contributed by Jakub Jelinek <jakub@redhat.com> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 3, or (at your option) 10any later version. 11 12GCC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along 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). */ 92static vec<int> ssa_ver_to_stridx; 93 94/* Number of currently active string indexes plus one. */ 95static int max_stridx; 96 97/* String information record. */ 98typedef 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. */ 145static 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. */ 153static vec<strinfo, va_heap, vl_embed> *stridx_to_strinfo; 154 155/* One OFFSET->IDX mapping. */ 156struct 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. */ 164struct decl_stridxlist_map 165{ 166 struct tree_map_base base; 167 struct stridxlist list; 168}; 169 170/* stridxlist hashtable helpers. */ 171 172struct 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 179inline hashval_t 180stridxlist_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. */ 187static hash_map<tree, stridxlist, stridxlist_hash_traits> 188 *decl_to_stridxlist_htab; 189 190/* Obstack for struct stridxlist and struct decl_stridxlist_map. */ 191static 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. */ 196struct laststmt_struct 197{ 198 gimple stmt; 199 tree len; 200 int stridx; 201} laststmt; 202 203static int get_stridx_plus_constant (strinfo, HOST_WIDE_INT, tree); 204 205/* Return strinfo vector entry IDX. */ 206 207static inline strinfo 208get_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 217static int 218get_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 247static int 248get_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 315static inline bool 316strinfo_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 324static void 325unshare_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 342static int * 343addr_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 384static int 385new_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 413static int 414new_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 431static strinfo 432new_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 451static inline void 452free_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 460static inline void 461set_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 472static tree 473get_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 587static bool 588maybe_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 619static strinfo 620unshare_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 643static strinfo 644verify_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 669static int 670get_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 745static strinfo 746zero_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 826static void 827adjust_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 874static void 875find_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/* If the last .MEM setter statement before STMT is 920 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT 921 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to 922 just memcpy (x, y, strlen (y)). SI must be the zero length 923 strinfo. */ 924 925static void 926adjust_last_stmt (strinfo si, gimple stmt, bool is_strcat) 927{ 928 tree vuse, callee, len; 929 struct laststmt_struct last = laststmt; 930 strinfo lastsi, firstsi; 931 unsigned len_arg_no = 2; 932 933 laststmt.stmt = NULL; 934 laststmt.len = NULL_TREE; 935 laststmt.stridx = 0; 936 937 if (last.stmt == NULL) 938 return; 939 940 vuse = gimple_vuse (stmt); 941 if (vuse == NULL_TREE 942 || SSA_NAME_DEF_STMT (vuse) != last.stmt 943 || !has_single_use (vuse)) 944 return; 945 946 gcc_assert (last.stridx > 0); 947 lastsi = get_strinfo (last.stridx); 948 if (lastsi == NULL) 949 return; 950 951 if (lastsi != si) 952 { 953 if (lastsi->first == 0 || lastsi->first != si->first) 954 return; 955 956 firstsi = verify_related_strinfos (si); 957 if (firstsi == NULL) 958 return; 959 while (firstsi != lastsi) 960 { 961 strinfo nextsi; 962 if (firstsi->next == 0) 963 return; 964 nextsi = get_strinfo (firstsi->next); 965 if (nextsi == NULL 966 || nextsi->prev != firstsi->idx 967 || nextsi->first != si->first) 968 return; 969 firstsi = nextsi; 970 } 971 } 972 973 if (!is_strcat) 974 { 975 if (si->length == NULL_TREE || !integer_zerop (si->length)) 976 return; 977 } 978 979 if (is_gimple_assign (last.stmt)) 980 { 981 gimple_stmt_iterator gsi; 982 983 if (!integer_zerop (gimple_assign_rhs1 (last.stmt))) 984 return; 985 if (stmt_could_throw_p (last.stmt)) 986 return; 987 gsi = gsi_for_stmt (last.stmt); 988 unlink_stmt_vdef (last.stmt); 989 release_defs (last.stmt); 990 gsi_remove (&gsi, true); 991 return; 992 } 993 994 if (!gimple_call_builtin_p (last.stmt, BUILT_IN_NORMAL)) 995 return; 996 997 callee = gimple_call_fndecl (last.stmt); 998 switch (DECL_FUNCTION_CODE (callee)) 999 { 1000 case BUILT_IN_MEMCPY: 1001 case BUILT_IN_MEMCPY_CHK: 1002 break; 1003 case BUILT_IN_MEMCPY_CHKP: 1004 case BUILT_IN_MEMCPY_CHK_CHKP: 1005 len_arg_no = 4; 1006 break; 1007 default: 1008 return; 1009 } 1010 1011 len = gimple_call_arg (last.stmt, len_arg_no); 1012 if (tree_fits_uhwi_p (len)) 1013 { 1014 if (!tree_fits_uhwi_p (last.len) 1015 || integer_zerop (len) 1016 || tree_to_uhwi (len) != tree_to_uhwi (last.len) + 1) 1017 return; 1018 /* Don't adjust the length if it is divisible by 4, it is more efficient 1019 to store the extra '\0' in that case. */ 1020 if ((tree_to_uhwi (len) & 3) == 0) 1021 return; 1022 } 1023 else if (TREE_CODE (len) == SSA_NAME) 1024 { 1025 gimple def_stmt = SSA_NAME_DEF_STMT (len); 1026 if (!is_gimple_assign (def_stmt) 1027 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR 1028 || gimple_assign_rhs1 (def_stmt) != last.len 1029 || !integer_onep (gimple_assign_rhs2 (def_stmt))) 1030 return; 1031 } 1032 else 1033 return; 1034 1035 gimple_call_set_arg (last.stmt, len_arg_no, last.len); 1036 update_stmt (last.stmt); 1037} 1038 1039/* Handle a strlen call. If strlen of the argument is known, replace 1040 the strlen call with the known value, otherwise remember that strlen 1041 of the argument is stored in the lhs SSA_NAME. */ 1042 1043static void 1044handle_builtin_strlen (gimple_stmt_iterator *gsi) 1045{ 1046 int idx; 1047 tree src; 1048 gimple stmt = gsi_stmt (*gsi); 1049 tree lhs = gimple_call_lhs (stmt); 1050 1051 if (lhs == NULL_TREE) 1052 return; 1053 1054 src = gimple_call_arg (stmt, 0); 1055 idx = get_stridx (src); 1056 if (idx) 1057 { 1058 strinfo si = NULL; 1059 tree rhs; 1060 1061 if (idx < 0) 1062 rhs = build_int_cst (TREE_TYPE (lhs), ~idx); 1063 else 1064 { 1065 rhs = NULL_TREE; 1066 si = get_strinfo (idx); 1067 if (si != NULL) 1068 rhs = get_string_length (si); 1069 } 1070 if (rhs != NULL_TREE) 1071 { 1072 if (dump_file && (dump_flags & TDF_DETAILS) != 0) 1073 { 1074 fprintf (dump_file, "Optimizing: "); 1075 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1076 } 1077 rhs = unshare_expr (rhs); 1078 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs))) 1079 rhs = fold_convert_loc (gimple_location (stmt), 1080 TREE_TYPE (lhs), rhs); 1081 if (!update_call_from_tree (gsi, rhs)) 1082 gimplify_and_update_call_from_tree (gsi, rhs); 1083 stmt = gsi_stmt (*gsi); 1084 update_stmt (stmt); 1085 if (dump_file && (dump_flags & TDF_DETAILS) != 0) 1086 { 1087 fprintf (dump_file, "into: "); 1088 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1089 } 1090 if (si != NULL 1091 && TREE_CODE (si->length) != SSA_NAME 1092 && TREE_CODE (si->length) != INTEGER_CST 1093 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) 1094 { 1095 si = unshare_strinfo (si); 1096 si->length = lhs; 1097 } 1098 return; 1099 } 1100 } 1101 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) 1102 return; 1103 if (idx == 0) 1104 idx = new_stridx (src); 1105 else if (get_strinfo (idx) != NULL) 1106 return; 1107 if (idx) 1108 { 1109 strinfo si = new_strinfo (src, idx, lhs); 1110 set_strinfo (idx, si); 1111 find_equal_ptrs (src, idx); 1112 } 1113} 1114 1115/* Handle a strchr call. If strlen of the first argument is known, replace 1116 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember 1117 that lhs of the call is endptr and strlen of the argument is endptr - x. */ 1118 1119static void 1120handle_builtin_strchr (gimple_stmt_iterator *gsi) 1121{ 1122 int idx; 1123 tree src; 1124 gimple stmt = gsi_stmt (*gsi); 1125 tree lhs = gimple_call_lhs (stmt); 1126 bool with_bounds = gimple_call_with_bounds_p (stmt); 1127 1128 if (lhs == NULL_TREE) 1129 return; 1130 1131 if (!integer_zerop (gimple_call_arg (stmt, with_bounds ? 2 : 1))) 1132 return; 1133 1134 src = gimple_call_arg (stmt, 0); 1135 idx = get_stridx (src); 1136 if (idx) 1137 { 1138 strinfo si = NULL; 1139 tree rhs; 1140 1141 if (idx < 0) 1142 rhs = build_int_cst (size_type_node, ~idx); 1143 else 1144 { 1145 rhs = NULL_TREE; 1146 si = get_strinfo (idx); 1147 if (si != NULL) 1148 rhs = get_string_length (si); 1149 } 1150 if (rhs != NULL_TREE) 1151 { 1152 location_t loc = gimple_location (stmt); 1153 1154 if (dump_file && (dump_flags & TDF_DETAILS) != 0) 1155 { 1156 fprintf (dump_file, "Optimizing: "); 1157 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1158 } 1159 if (si != NULL && si->endptr != NULL_TREE) 1160 { 1161 rhs = unshare_expr (si->endptr); 1162 if (!useless_type_conversion_p (TREE_TYPE (lhs), 1163 TREE_TYPE (rhs))) 1164 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs); 1165 } 1166 else 1167 { 1168 rhs = fold_convert_loc (loc, sizetype, unshare_expr (rhs)); 1169 rhs = fold_build2_loc (loc, POINTER_PLUS_EXPR, 1170 TREE_TYPE (src), src, rhs); 1171 if (!useless_type_conversion_p (TREE_TYPE (lhs), 1172 TREE_TYPE (rhs))) 1173 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs); 1174 } 1175 if (!update_call_from_tree (gsi, rhs)) 1176 gimplify_and_update_call_from_tree (gsi, rhs); 1177 stmt = gsi_stmt (*gsi); 1178 update_stmt (stmt); 1179 if (dump_file && (dump_flags & TDF_DETAILS) != 0) 1180 { 1181 fprintf (dump_file, "into: "); 1182 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1183 } 1184 if (si != NULL 1185 && si->endptr == NULL_TREE 1186 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) 1187 { 1188 si = unshare_strinfo (si); 1189 si->endptr = lhs; 1190 } 1191 zero_length_string (lhs, si); 1192 return; 1193 } 1194 } 1195 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) 1196 return; 1197 if (TREE_CODE (src) != SSA_NAME || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src)) 1198 { 1199 if (idx == 0) 1200 idx = new_stridx (src); 1201 else if (get_strinfo (idx) != NULL) 1202 { 1203 zero_length_string (lhs, NULL); 1204 return; 1205 } 1206 if (idx) 1207 { 1208 location_t loc = gimple_location (stmt); 1209 tree lhsu = fold_convert_loc (loc, size_type_node, lhs); 1210 tree srcu = fold_convert_loc (loc, size_type_node, src); 1211 tree length = fold_build2_loc (loc, MINUS_EXPR, 1212 size_type_node, lhsu, srcu); 1213 strinfo si = new_strinfo (src, idx, length); 1214 si->endptr = lhs; 1215 set_strinfo (idx, si); 1216 find_equal_ptrs (src, idx); 1217 zero_length_string (lhs, si); 1218 } 1219 } 1220 else 1221 zero_length_string (lhs, NULL); 1222} 1223 1224/* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call. 1225 If strlen of the second argument is known, strlen of the first argument 1226 is the same after this call. Furthermore, attempt to convert it to 1227 memcpy. */ 1228 1229static void 1230handle_builtin_strcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi) 1231{ 1232 int idx, didx; 1233 tree src, dst, srclen, len, lhs, args, type, fn, oldlen; 1234 bool success; 1235 gimple stmt = gsi_stmt (*gsi); 1236 strinfo si, dsi, olddsi, zsi; 1237 location_t loc; 1238 bool with_bounds = gimple_call_with_bounds_p (stmt); 1239 1240 src = gimple_call_arg (stmt, with_bounds ? 2 : 1); 1241 dst = gimple_call_arg (stmt, 0); 1242 lhs = gimple_call_lhs (stmt); 1243 idx = get_stridx (src); 1244 si = NULL; 1245 if (idx > 0) 1246 si = get_strinfo (idx); 1247 1248 didx = get_stridx (dst); 1249 olddsi = NULL; 1250 oldlen = NULL_TREE; 1251 if (didx > 0) 1252 olddsi = get_strinfo (didx); 1253 else if (didx < 0) 1254 return; 1255 1256 if (olddsi != NULL) 1257 adjust_last_stmt (olddsi, stmt, false); 1258 1259 srclen = NULL_TREE; 1260 if (si != NULL) 1261 srclen = get_string_length (si); 1262 else if (idx < 0) 1263 srclen = build_int_cst (size_type_node, ~idx); 1264 1265 loc = gimple_location (stmt); 1266 if (srclen == NULL_TREE) 1267 switch (bcode) 1268 { 1269 case BUILT_IN_STRCPY: 1270 case BUILT_IN_STRCPY_CHK: 1271 case BUILT_IN_STRCPY_CHKP: 1272 case BUILT_IN_STRCPY_CHK_CHKP: 1273 if (lhs != NULL_TREE || !builtin_decl_implicit_p (BUILT_IN_STPCPY)) 1274 return; 1275 break; 1276 case BUILT_IN_STPCPY: 1277 case BUILT_IN_STPCPY_CHK: 1278 case BUILT_IN_STPCPY_CHKP: 1279 case BUILT_IN_STPCPY_CHK_CHKP: 1280 if (lhs == NULL_TREE) 1281 return; 1282 else 1283 { 1284 tree lhsuint = fold_convert_loc (loc, size_type_node, lhs); 1285 srclen = fold_convert_loc (loc, size_type_node, dst); 1286 srclen = fold_build2_loc (loc, MINUS_EXPR, size_type_node, 1287 lhsuint, srclen); 1288 } 1289 break; 1290 default: 1291 gcc_unreachable (); 1292 } 1293 1294 if (didx == 0) 1295 { 1296 didx = new_stridx (dst); 1297 if (didx == 0) 1298 return; 1299 } 1300 if (olddsi != NULL) 1301 { 1302 oldlen = olddsi->length; 1303 dsi = unshare_strinfo (olddsi); 1304 dsi->length = srclen; 1305 /* Break the chain, so adjust_related_strinfo on later pointers in 1306 the chain won't adjust this one anymore. */ 1307 dsi->next = 0; 1308 dsi->stmt = NULL; 1309 dsi->endptr = NULL_TREE; 1310 } 1311 else 1312 { 1313 dsi = new_strinfo (dst, didx, srclen); 1314 set_strinfo (didx, dsi); 1315 find_equal_ptrs (dst, didx); 1316 } 1317 dsi->writable = true; 1318 dsi->dont_invalidate = true; 1319 1320 if (dsi->length == NULL_TREE) 1321 { 1322 strinfo chainsi; 1323 1324 /* If string length of src is unknown, use delayed length 1325 computation. If string lenth of dst will be needed, it 1326 can be computed by transforming this strcpy call into 1327 stpcpy and subtracting dst from the return value. */ 1328 1329 /* Look for earlier strings whose length could be determined if 1330 this strcpy is turned into an stpcpy. */ 1331 1332 if (dsi->prev != 0 && (chainsi = verify_related_strinfos (dsi)) != NULL) 1333 { 1334 for (; chainsi && chainsi != dsi; chainsi = get_strinfo (chainsi->next)) 1335 { 1336 /* When setting a stmt for delayed length computation 1337 prevent all strinfos through dsi from being 1338 invalidated. */ 1339 chainsi = unshare_strinfo (chainsi); 1340 chainsi->stmt = stmt; 1341 chainsi->length = NULL_TREE; 1342 chainsi->endptr = NULL_TREE; 1343 chainsi->dont_invalidate = true; 1344 } 1345 } 1346 dsi->stmt = stmt; 1347 return; 1348 } 1349 1350 if (olddsi != NULL) 1351 { 1352 tree adj = NULL_TREE; 1353 if (oldlen == NULL_TREE) 1354 ; 1355 else if (integer_zerop (oldlen)) 1356 adj = srclen; 1357 else if (TREE_CODE (oldlen) == INTEGER_CST 1358 || TREE_CODE (srclen) == INTEGER_CST) 1359 adj = fold_build2_loc (loc, MINUS_EXPR, 1360 TREE_TYPE (srclen), srclen, 1361 fold_convert_loc (loc, TREE_TYPE (srclen), 1362 oldlen)); 1363 if (adj != NULL_TREE) 1364 adjust_related_strinfos (loc, dsi, adj); 1365 else 1366 dsi->prev = 0; 1367 } 1368 /* strcpy src may not overlap dst, so src doesn't need to be 1369 invalidated either. */ 1370 if (si != NULL) 1371 si->dont_invalidate = true; 1372 1373 fn = NULL_TREE; 1374 zsi = NULL; 1375 switch (bcode) 1376 { 1377 case BUILT_IN_STRCPY: 1378 case BUILT_IN_STRCPY_CHKP: 1379 fn = builtin_decl_implicit (BUILT_IN_MEMCPY); 1380 if (lhs) 1381 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx; 1382 break; 1383 case BUILT_IN_STRCPY_CHK: 1384 case BUILT_IN_STRCPY_CHK_CHKP: 1385 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK); 1386 if (lhs) 1387 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx; 1388 break; 1389 case BUILT_IN_STPCPY: 1390 case BUILT_IN_STPCPY_CHKP: 1391 /* This would need adjustment of the lhs (subtract one), 1392 or detection that the trailing '\0' doesn't need to be 1393 written, if it will be immediately overwritten. 1394 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */ 1395 if (lhs) 1396 { 1397 dsi->endptr = lhs; 1398 zsi = zero_length_string (lhs, dsi); 1399 } 1400 break; 1401 case BUILT_IN_STPCPY_CHK: 1402 case BUILT_IN_STPCPY_CHK_CHKP: 1403 /* This would need adjustment of the lhs (subtract one), 1404 or detection that the trailing '\0' doesn't need to be 1405 written, if it will be immediately overwritten. 1406 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */ 1407 if (lhs) 1408 { 1409 dsi->endptr = lhs; 1410 zsi = zero_length_string (lhs, dsi); 1411 } 1412 break; 1413 default: 1414 gcc_unreachable (); 1415 } 1416 if (zsi != NULL) 1417 zsi->dont_invalidate = true; 1418 1419 if (fn == NULL_TREE) 1420 return; 1421 1422 args = TYPE_ARG_TYPES (TREE_TYPE (fn)); 1423 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args))); 1424 1425 len = fold_convert_loc (loc, type, unshare_expr (srclen)); 1426 len = fold_build2_loc (loc, PLUS_EXPR, type, len, build_int_cst (type, 1)); 1427 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true, 1428 GSI_SAME_STMT); 1429 if (dump_file && (dump_flags & TDF_DETAILS) != 0) 1430 { 1431 fprintf (dump_file, "Optimizing: "); 1432 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1433 } 1434 if (with_bounds) 1435 { 1436 fn = chkp_maybe_create_clone (fn)->decl; 1437 if (gimple_call_num_args (stmt) == 4) 1438 success = update_gimple_call (gsi, fn, 5, dst, 1439 gimple_call_arg (stmt, 1), 1440 src, 1441 gimple_call_arg (stmt, 3), 1442 len); 1443 else 1444 success = update_gimple_call (gsi, fn, 6, dst, 1445 gimple_call_arg (stmt, 1), 1446 src, 1447 gimple_call_arg (stmt, 3), 1448 len, 1449 gimple_call_arg (stmt, 4)); 1450 } 1451 else 1452 if (gimple_call_num_args (stmt) == 2) 1453 success = update_gimple_call (gsi, fn, 3, dst, src, len); 1454 else 1455 success = update_gimple_call (gsi, fn, 4, dst, src, len, 1456 gimple_call_arg (stmt, 2)); 1457 if (success) 1458 { 1459 stmt = gsi_stmt (*gsi); 1460 gimple_call_set_with_bounds (stmt, with_bounds); 1461 update_stmt (stmt); 1462 if (dump_file && (dump_flags & TDF_DETAILS) != 0) 1463 { 1464 fprintf (dump_file, "into: "); 1465 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1466 } 1467 /* Allow adjust_last_stmt to decrease this memcpy's size. */ 1468 laststmt.stmt = stmt; 1469 laststmt.len = srclen; 1470 laststmt.stridx = dsi->idx; 1471 } 1472 else if (dump_file && (dump_flags & TDF_DETAILS) != 0) 1473 fprintf (dump_file, "not possible.\n"); 1474} 1475 1476/* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call. 1477 If strlen of the second argument is known and length of the third argument 1478 is that plus one, strlen of the first argument is the same after this 1479 call. */ 1480 1481static void 1482handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi) 1483{ 1484 int idx, didx; 1485 tree src, dst, len, lhs, oldlen, newlen; 1486 gimple stmt = gsi_stmt (*gsi); 1487 strinfo si, dsi, olddsi; 1488 bool with_bounds = gimple_call_with_bounds_p (stmt); 1489 1490 len = gimple_call_arg (stmt, with_bounds ? 4 : 2); 1491 src = gimple_call_arg (stmt, with_bounds ? 2 : 1); 1492 dst = gimple_call_arg (stmt, 0); 1493 idx = get_stridx (src); 1494 if (idx == 0) 1495 return; 1496 1497 didx = get_stridx (dst); 1498 olddsi = NULL; 1499 if (didx > 0) 1500 olddsi = get_strinfo (didx); 1501 else if (didx < 0) 1502 return; 1503 1504 if (olddsi != NULL 1505 && tree_fits_uhwi_p (len) 1506 && !integer_zerop (len)) 1507 adjust_last_stmt (olddsi, stmt, false); 1508 1509 if (idx > 0) 1510 { 1511 gimple def_stmt; 1512 1513 /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */ 1514 si = get_strinfo (idx); 1515 if (si == NULL || si->length == NULL_TREE) 1516 return; 1517 if (TREE_CODE (len) != SSA_NAME) 1518 return; 1519 def_stmt = SSA_NAME_DEF_STMT (len); 1520 if (!is_gimple_assign (def_stmt) 1521 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR 1522 || gimple_assign_rhs1 (def_stmt) != si->length 1523 || !integer_onep (gimple_assign_rhs2 (def_stmt))) 1524 return; 1525 } 1526 else 1527 { 1528 si = NULL; 1529 /* Handle memcpy (x, "abcd", 5) or 1530 memcpy (x, "abc\0uvw", 7). */ 1531 if (!tree_fits_uhwi_p (len) 1532 || tree_to_uhwi (len) <= (unsigned HOST_WIDE_INT) ~idx) 1533 return; 1534 } 1535 1536 if (olddsi != NULL && TREE_CODE (len) == SSA_NAME) 1537 adjust_last_stmt (olddsi, stmt, false); 1538 1539 if (didx == 0) 1540 { 1541 didx = new_stridx (dst); 1542 if (didx == 0) 1543 return; 1544 } 1545 if (si != NULL) 1546 newlen = si->length; 1547 else 1548 newlen = build_int_cst (size_type_node, ~idx); 1549 oldlen = NULL_TREE; 1550 if (olddsi != NULL) 1551 { 1552 dsi = unshare_strinfo (olddsi); 1553 oldlen = olddsi->length; 1554 dsi->length = newlen; 1555 /* Break the chain, so adjust_related_strinfo on later pointers in 1556 the chain won't adjust this one anymore. */ 1557 dsi->next = 0; 1558 dsi->stmt = NULL; 1559 dsi->endptr = NULL_TREE; 1560 } 1561 else 1562 { 1563 dsi = new_strinfo (dst, didx, newlen); 1564 set_strinfo (didx, dsi); 1565 find_equal_ptrs (dst, didx); 1566 } 1567 dsi->writable = true; 1568 dsi->dont_invalidate = true; 1569 if (olddsi != NULL) 1570 { 1571 tree adj = NULL_TREE; 1572 location_t loc = gimple_location (stmt); 1573 if (oldlen == NULL_TREE) 1574 ; 1575 else if (integer_zerop (oldlen)) 1576 adj = dsi->length; 1577 else if (TREE_CODE (oldlen) == INTEGER_CST 1578 || TREE_CODE (dsi->length) == INTEGER_CST) 1579 adj = fold_build2_loc (loc, MINUS_EXPR, 1580 TREE_TYPE (dsi->length), dsi->length, 1581 fold_convert_loc (loc, TREE_TYPE (dsi->length), 1582 oldlen)); 1583 if (adj != NULL_TREE) 1584 adjust_related_strinfos (loc, dsi, adj); 1585 else 1586 dsi->prev = 0; 1587 } 1588 /* memcpy src may not overlap dst, so src doesn't need to be 1589 invalidated either. */ 1590 if (si != NULL) 1591 si->dont_invalidate = true; 1592 1593 lhs = gimple_call_lhs (stmt); 1594 switch (bcode) 1595 { 1596 case BUILT_IN_MEMCPY: 1597 case BUILT_IN_MEMCPY_CHK: 1598 case BUILT_IN_MEMCPY_CHKP: 1599 case BUILT_IN_MEMCPY_CHK_CHKP: 1600 /* Allow adjust_last_stmt to decrease this memcpy's size. */ 1601 laststmt.stmt = stmt; 1602 laststmt.len = dsi->length; 1603 laststmt.stridx = dsi->idx; 1604 if (lhs) 1605 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx; 1606 break; 1607 case BUILT_IN_MEMPCPY: 1608 case BUILT_IN_MEMPCPY_CHK: 1609 case BUILT_IN_MEMPCPY_CHKP: 1610 case BUILT_IN_MEMPCPY_CHK_CHKP: 1611 break; 1612 default: 1613 gcc_unreachable (); 1614 } 1615} 1616 1617/* Handle a strcat-like ({strcat,__strcat_chk}) call. 1618 If strlen of the second argument is known, strlen of the first argument 1619 is increased by the length of the second argument. Furthermore, attempt 1620 to convert it to memcpy/strcpy if the length of the first argument 1621 is known. */ 1622 1623static void 1624handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi) 1625{ 1626 int idx, didx; 1627 tree src, dst, srclen, dstlen, len, lhs, args, type, fn, objsz, endptr; 1628 bool success; 1629 gimple stmt = gsi_stmt (*gsi); 1630 strinfo si, dsi; 1631 location_t loc; 1632 bool with_bounds = gimple_call_with_bounds_p (stmt); 1633 1634 src = gimple_call_arg (stmt, with_bounds ? 2 : 1); 1635 dst = gimple_call_arg (stmt, 0); 1636 lhs = gimple_call_lhs (stmt); 1637 1638 didx = get_stridx (dst); 1639 if (didx < 0) 1640 return; 1641 1642 dsi = NULL; 1643 if (didx > 0) 1644 dsi = get_strinfo (didx); 1645 if (dsi == NULL || get_string_length (dsi) == NULL_TREE) 1646 { 1647 /* strcat (p, q) can be transformed into 1648 tmp = p + strlen (p); endptr = strpcpy (tmp, q); 1649 with length endptr - p if we need to compute the length 1650 later on. Don't do this transformation if we don't need 1651 it. */ 1652 if (builtin_decl_implicit_p (BUILT_IN_STPCPY) && lhs == NULL_TREE) 1653 { 1654 if (didx == 0) 1655 { 1656 didx = new_stridx (dst); 1657 if (didx == 0) 1658 return; 1659 } 1660 if (dsi == NULL) 1661 { 1662 dsi = new_strinfo (dst, didx, NULL_TREE); 1663 set_strinfo (didx, dsi); 1664 find_equal_ptrs (dst, didx); 1665 } 1666 else 1667 { 1668 dsi = unshare_strinfo (dsi); 1669 dsi->length = NULL_TREE; 1670 dsi->next = 0; 1671 dsi->endptr = NULL_TREE; 1672 } 1673 dsi->writable = true; 1674 dsi->stmt = stmt; 1675 dsi->dont_invalidate = true; 1676 } 1677 return; 1678 } 1679 1680 srclen = NULL_TREE; 1681 si = NULL; 1682 idx = get_stridx (src); 1683 if (idx < 0) 1684 srclen = build_int_cst (size_type_node, ~idx); 1685 else if (idx > 0) 1686 { 1687 si = get_strinfo (idx); 1688 if (si != NULL) 1689 srclen = get_string_length (si); 1690 } 1691 1692 loc = gimple_location (stmt); 1693 dstlen = dsi->length; 1694 endptr = dsi->endptr; 1695 1696 dsi = unshare_strinfo (dsi); 1697 dsi->endptr = NULL_TREE; 1698 dsi->stmt = NULL; 1699 dsi->writable = true; 1700 1701 if (srclen != NULL_TREE) 1702 { 1703 dsi->length = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (dsi->length), 1704 dsi->length, srclen); 1705 adjust_related_strinfos (loc, dsi, srclen); 1706 dsi->dont_invalidate = true; 1707 } 1708 else 1709 { 1710 dsi->length = NULL; 1711 if (lhs == NULL_TREE && builtin_decl_implicit_p (BUILT_IN_STPCPY)) 1712 dsi->dont_invalidate = true; 1713 } 1714 1715 if (si != NULL) 1716 /* strcat src may not overlap dst, so src doesn't need to be 1717 invalidated either. */ 1718 si->dont_invalidate = true; 1719 1720 /* For now. Could remove the lhs from the call and add 1721 lhs = dst; afterwards. */ 1722 if (lhs) 1723 return; 1724 1725 fn = NULL_TREE; 1726 objsz = NULL_TREE; 1727 switch (bcode) 1728 { 1729 case BUILT_IN_STRCAT: 1730 case BUILT_IN_STRCAT_CHKP: 1731 if (srclen != NULL_TREE) 1732 fn = builtin_decl_implicit (BUILT_IN_MEMCPY); 1733 else 1734 fn = builtin_decl_implicit (BUILT_IN_STRCPY); 1735 break; 1736 case BUILT_IN_STRCAT_CHK: 1737 case BUILT_IN_STRCAT_CHK_CHKP: 1738 if (srclen != NULL_TREE) 1739 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK); 1740 else 1741 fn = builtin_decl_explicit (BUILT_IN_STRCPY_CHK); 1742 objsz = gimple_call_arg (stmt, with_bounds ? 4 : 2); 1743 break; 1744 default: 1745 gcc_unreachable (); 1746 } 1747 1748 if (fn == NULL_TREE) 1749 return; 1750 1751 len = NULL_TREE; 1752 if (srclen != NULL_TREE) 1753 { 1754 args = TYPE_ARG_TYPES (TREE_TYPE (fn)); 1755 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args))); 1756 1757 len = fold_convert_loc (loc, type, unshare_expr (srclen)); 1758 len = fold_build2_loc (loc, PLUS_EXPR, type, len, 1759 build_int_cst (type, 1)); 1760 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true, 1761 GSI_SAME_STMT); 1762 } 1763 if (endptr) 1764 dst = fold_convert_loc (loc, TREE_TYPE (dst), unshare_expr (endptr)); 1765 else 1766 dst = fold_build2_loc (loc, POINTER_PLUS_EXPR, 1767 TREE_TYPE (dst), unshare_expr (dst), 1768 fold_convert_loc (loc, sizetype, 1769 unshare_expr (dstlen))); 1770 dst = force_gimple_operand_gsi (gsi, dst, true, NULL_TREE, true, 1771 GSI_SAME_STMT); 1772 if (dump_file && (dump_flags & TDF_DETAILS) != 0) 1773 { 1774 fprintf (dump_file, "Optimizing: "); 1775 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1776 } 1777 if (with_bounds) 1778 { 1779 fn = chkp_maybe_create_clone (fn)->decl; 1780 if (srclen != NULL_TREE) 1781 success = update_gimple_call (gsi, fn, 5 + (objsz != NULL_TREE), 1782 dst, 1783 gimple_call_arg (stmt, 1), 1784 src, 1785 gimple_call_arg (stmt, 3), 1786 len, objsz); 1787 else 1788 success = update_gimple_call (gsi, fn, 4 + (objsz != NULL_TREE), 1789 dst, 1790 gimple_call_arg (stmt, 1), 1791 src, 1792 gimple_call_arg (stmt, 3), 1793 objsz); 1794 } 1795 else 1796 if (srclen != NULL_TREE) 1797 success = update_gimple_call (gsi, fn, 3 + (objsz != NULL_TREE), 1798 dst, src, len, objsz); 1799 else 1800 success = update_gimple_call (gsi, fn, 2 + (objsz != NULL_TREE), 1801 dst, src, objsz); 1802 if (success) 1803 { 1804 stmt = gsi_stmt (*gsi); 1805 gimple_call_set_with_bounds (stmt, with_bounds); 1806 update_stmt (stmt); 1807 if (dump_file && (dump_flags & TDF_DETAILS) != 0) 1808 { 1809 fprintf (dump_file, "into: "); 1810 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1811 } 1812 /* If srclen == NULL, note that current string length can be 1813 computed by transforming this strcpy into stpcpy. */ 1814 if (srclen == NULL_TREE && dsi->dont_invalidate) 1815 dsi->stmt = stmt; 1816 adjust_last_stmt (dsi, stmt, true); 1817 if (srclen != NULL_TREE) 1818 { 1819 laststmt.stmt = stmt; 1820 laststmt.len = srclen; 1821 laststmt.stridx = dsi->idx; 1822 } 1823 } 1824 else if (dump_file && (dump_flags & TDF_DETAILS) != 0) 1825 fprintf (dump_file, "not possible.\n"); 1826} 1827 1828/* Handle a call to malloc or calloc. */ 1829 1830static void 1831handle_builtin_malloc (enum built_in_function bcode, gimple_stmt_iterator *gsi) 1832{ 1833 gimple stmt = gsi_stmt (*gsi); 1834 tree lhs = gimple_call_lhs (stmt); 1835 gcc_assert (get_stridx (lhs) == 0); 1836 int idx = new_stridx (lhs); 1837 tree length = NULL_TREE; 1838 if (bcode == BUILT_IN_CALLOC) 1839 length = build_int_cst (size_type_node, 0); 1840 strinfo si = new_strinfo (lhs, idx, length); 1841 if (bcode == BUILT_IN_CALLOC) 1842 si->endptr = lhs; 1843 set_strinfo (idx, si); 1844 si->writable = true; 1845 si->stmt = stmt; 1846 si->dont_invalidate = true; 1847} 1848 1849/* Handle a call to memset. 1850 After a call to calloc, memset(,0,) is unnecessary. 1851 memset(malloc(n),0,n) is calloc(n,1). */ 1852 1853static bool 1854handle_builtin_memset (gimple_stmt_iterator *gsi) 1855{ 1856 gimple stmt2 = gsi_stmt (*gsi); 1857 if (!integer_zerop (gimple_call_arg (stmt2, 1))) 1858 return true; 1859 tree ptr = gimple_call_arg (stmt2, 0); 1860 int idx1 = get_stridx (ptr); 1861 if (idx1 <= 0) 1862 return true; 1863 strinfo si1 = get_strinfo (idx1); 1864 if (!si1) 1865 return true; 1866 gimple stmt1 = si1->stmt; 1867 if (!stmt1 || !is_gimple_call (stmt1)) 1868 return true; 1869 tree callee1 = gimple_call_fndecl (stmt1); 1870 if (!gimple_call_builtin_p (stmt1, BUILT_IN_NORMAL)) 1871 return true; 1872 enum built_in_function code1 = DECL_FUNCTION_CODE (callee1); 1873 tree size = gimple_call_arg (stmt2, 2); 1874 if (code1 == BUILT_IN_CALLOC) 1875 /* Not touching stmt1 */ ; 1876 else if (code1 == BUILT_IN_MALLOC 1877 && operand_equal_p (gimple_call_arg (stmt1, 0), size, 0)) 1878 { 1879 gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt1); 1880 update_gimple_call (&gsi1, builtin_decl_implicit (BUILT_IN_CALLOC), 2, 1881 size, build_one_cst (size_type_node)); 1882 si1->length = build_int_cst (size_type_node, 0); 1883 si1->stmt = gsi_stmt (gsi1); 1884 } 1885 else 1886 return true; 1887 tree lhs = gimple_call_lhs (stmt2); 1888 unlink_stmt_vdef (stmt2); 1889 if (lhs) 1890 { 1891 gimple assign = gimple_build_assign (lhs, ptr); 1892 gsi_replace (gsi, assign, false); 1893 } 1894 else 1895 { 1896 gsi_remove (gsi, true); 1897 release_defs (stmt2); 1898 } 1899 1900 return false; 1901} 1902 1903/* Handle a POINTER_PLUS_EXPR statement. 1904 For p = "abcd" + 2; compute associated length, or if 1905 p = q + off is pointing to a '\0' character of a string, call 1906 zero_length_string on it. */ 1907 1908static void 1909handle_pointer_plus (gimple_stmt_iterator *gsi) 1910{ 1911 gimple stmt = gsi_stmt (*gsi); 1912 tree lhs = gimple_assign_lhs (stmt), off; 1913 int idx = get_stridx (gimple_assign_rhs1 (stmt)); 1914 strinfo si, zsi; 1915 1916 if (idx == 0) 1917 return; 1918 1919 if (idx < 0) 1920 { 1921 tree off = gimple_assign_rhs2 (stmt); 1922 if (tree_fits_uhwi_p (off) 1923 && tree_to_uhwi (off) <= (unsigned HOST_WIDE_INT) ~idx) 1924 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] 1925 = ~(~idx - (int) tree_to_uhwi (off)); 1926 return; 1927 } 1928 1929 si = get_strinfo (idx); 1930 if (si == NULL || si->length == NULL_TREE) 1931 return; 1932 1933 off = gimple_assign_rhs2 (stmt); 1934 zsi = NULL; 1935 if (operand_equal_p (si->length, off, 0)) 1936 zsi = zero_length_string (lhs, si); 1937 else if (TREE_CODE (off) == SSA_NAME) 1938 { 1939 gimple def_stmt = SSA_NAME_DEF_STMT (off); 1940 if (gimple_assign_single_p (def_stmt) 1941 && operand_equal_p (si->length, gimple_assign_rhs1 (def_stmt), 0)) 1942 zsi = zero_length_string (lhs, si); 1943 } 1944 if (zsi != NULL 1945 && si->endptr != NULL_TREE 1946 && si->endptr != lhs 1947 && TREE_CODE (si->endptr) == SSA_NAME) 1948 { 1949 enum tree_code rhs_code 1950 = useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (si->endptr)) 1951 ? SSA_NAME : NOP_EXPR; 1952 gimple_assign_set_rhs_with_ops (gsi, rhs_code, si->endptr); 1953 gcc_assert (gsi_stmt (*gsi) == stmt); 1954 update_stmt (stmt); 1955 } 1956} 1957 1958/* Handle a single character store. */ 1959 1960static bool 1961handle_char_store (gimple_stmt_iterator *gsi) 1962{ 1963 int idx = -1; 1964 strinfo si = NULL; 1965 gimple stmt = gsi_stmt (*gsi); 1966 tree ssaname = NULL_TREE, lhs = gimple_assign_lhs (stmt); 1967 1968 if (TREE_CODE (lhs) == MEM_REF 1969 && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME) 1970 { 1971 if (integer_zerop (TREE_OPERAND (lhs, 1))) 1972 { 1973 ssaname = TREE_OPERAND (lhs, 0); 1974 idx = get_stridx (ssaname); 1975 } 1976 } 1977 else 1978 idx = get_addr_stridx (lhs); 1979 1980 if (idx > 0) 1981 { 1982 si = get_strinfo (idx); 1983 if (si != NULL && si->length != NULL_TREE && integer_zerop (si->length)) 1984 { 1985 if (initializer_zerop (gimple_assign_rhs1 (stmt))) 1986 { 1987 /* When storing '\0', the store can be removed 1988 if we know it has been stored in the current function. */ 1989 if (!stmt_could_throw_p (stmt) && si->writable) 1990 { 1991 unlink_stmt_vdef (stmt); 1992 release_defs (stmt); 1993 gsi_remove (gsi, true); 1994 return false; 1995 } 1996 else 1997 { 1998 si->writable = true; 1999 gsi_next (gsi); 2000 return false; 2001 } 2002 } 2003 else 2004 /* Otherwise this statement overwrites the '\0' with 2005 something, if the previous stmt was a memcpy, 2006 its length may be decreased. */ 2007 adjust_last_stmt (si, stmt, false); 2008 } 2009 else if (si != NULL && integer_zerop (gimple_assign_rhs1 (stmt))) 2010 { 2011 si = unshare_strinfo (si); 2012 si->length = build_int_cst (size_type_node, 0); 2013 si->endptr = NULL; 2014 si->prev = 0; 2015 si->next = 0; 2016 si->stmt = NULL; 2017 si->first = 0; 2018 si->writable = true; 2019 if (ssaname && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname)) 2020 si->endptr = ssaname; 2021 si->dont_invalidate = true; 2022 } 2023 /* If si->length is non-zero constant, we aren't overwriting '\0', 2024 and if we aren't storing '\0', we know that the length of the 2025 string and any other zero terminated string in memory remains 2026 the same. In that case we move to the next gimple statement and 2027 return to signal the caller that it shouldn't invalidate anything. 2028 2029 This is benefical for cases like: 2030 2031 char p[20]; 2032 void foo (char *q) 2033 { 2034 strcpy (p, "foobar"); 2035 size_t len = strlen (p); // This can be optimized into 6 2036 size_t len2 = strlen (q); // This has to be computed 2037 p[0] = 'X'; 2038 size_t len3 = strlen (p); // This can be optimized into 6 2039 size_t len4 = strlen (q); // This can be optimized into len2 2040 bar (len, len2, len3, len4); 2041 } 2042 */ 2043 else if (si != NULL && si->length != NULL_TREE 2044 && TREE_CODE (si->length) == INTEGER_CST 2045 && integer_nonzerop (gimple_assign_rhs1 (stmt))) 2046 { 2047 gsi_next (gsi); 2048 return false; 2049 } 2050 } 2051 else if (idx == 0 && initializer_zerop (gimple_assign_rhs1 (stmt))) 2052 { 2053 if (ssaname) 2054 { 2055 si = zero_length_string (ssaname, NULL); 2056 if (si != NULL) 2057 si->dont_invalidate = true; 2058 } 2059 else 2060 { 2061 int idx = new_addr_stridx (lhs); 2062 if (idx != 0) 2063 { 2064 si = new_strinfo (build_fold_addr_expr (lhs), idx, 2065 build_int_cst (size_type_node, 0)); 2066 set_strinfo (idx, si); 2067 si->dont_invalidate = true; 2068 } 2069 } 2070 if (si != NULL) 2071 si->writable = true; 2072 } 2073 else if (idx == 0 2074 && TREE_CODE (gimple_assign_rhs1 (stmt)) == STRING_CST 2075 && ssaname == NULL_TREE 2076 && TREE_CODE (TREE_TYPE (lhs)) == ARRAY_TYPE) 2077 { 2078 size_t l = strlen (TREE_STRING_POINTER (gimple_assign_rhs1 (stmt))); 2079 HOST_WIDE_INT a = int_size_in_bytes (TREE_TYPE (lhs)); 2080 if (a > 0 && (unsigned HOST_WIDE_INT) a > l) 2081 { 2082 int idx = new_addr_stridx (lhs); 2083 if (idx != 0) 2084 { 2085 si = new_strinfo (build_fold_addr_expr (lhs), idx, 2086 build_int_cst (size_type_node, l)); 2087 set_strinfo (idx, si); 2088 si->dont_invalidate = true; 2089 } 2090 } 2091 } 2092 2093 if (si != NULL && initializer_zerop (gimple_assign_rhs1 (stmt))) 2094 { 2095 /* Allow adjust_last_stmt to remove it if the stored '\0' 2096 is immediately overwritten. */ 2097 laststmt.stmt = stmt; 2098 laststmt.len = build_int_cst (size_type_node, 1); 2099 laststmt.stridx = si->idx; 2100 } 2101 return true; 2102} 2103 2104/* Attempt to optimize a single statement at *GSI using string length 2105 knowledge. */ 2106 2107static bool 2108strlen_optimize_stmt (gimple_stmt_iterator *gsi) 2109{ 2110 gimple stmt = gsi_stmt (*gsi); 2111 2112 if (is_gimple_call (stmt)) 2113 { 2114 tree callee = gimple_call_fndecl (stmt); 2115 if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) 2116 switch (DECL_FUNCTION_CODE (callee)) 2117 { 2118 case BUILT_IN_STRLEN: 2119 case BUILT_IN_STRLEN_CHKP: 2120 handle_builtin_strlen (gsi); 2121 break; 2122 case BUILT_IN_STRCHR: 2123 case BUILT_IN_STRCHR_CHKP: 2124 handle_builtin_strchr (gsi); 2125 break; 2126 case BUILT_IN_STRCPY: 2127 case BUILT_IN_STRCPY_CHK: 2128 case BUILT_IN_STPCPY: 2129 case BUILT_IN_STPCPY_CHK: 2130 case BUILT_IN_STRCPY_CHKP: 2131 case BUILT_IN_STRCPY_CHK_CHKP: 2132 case BUILT_IN_STPCPY_CHKP: 2133 case BUILT_IN_STPCPY_CHK_CHKP: 2134 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee), gsi); 2135 break; 2136 case BUILT_IN_MEMCPY: 2137 case BUILT_IN_MEMCPY_CHK: 2138 case BUILT_IN_MEMPCPY: 2139 case BUILT_IN_MEMPCPY_CHK: 2140 case BUILT_IN_MEMCPY_CHKP: 2141 case BUILT_IN_MEMCPY_CHK_CHKP: 2142 case BUILT_IN_MEMPCPY_CHKP: 2143 case BUILT_IN_MEMPCPY_CHK_CHKP: 2144 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi); 2145 break; 2146 case BUILT_IN_STRCAT: 2147 case BUILT_IN_STRCAT_CHK: 2148 case BUILT_IN_STRCAT_CHKP: 2149 case BUILT_IN_STRCAT_CHK_CHKP: 2150 handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi); 2151 break; 2152 case BUILT_IN_MALLOC: 2153 case BUILT_IN_CALLOC: 2154 handle_builtin_malloc (DECL_FUNCTION_CODE (callee), gsi); 2155 break; 2156 case BUILT_IN_MEMSET: 2157 if (!handle_builtin_memset (gsi)) 2158 return false; 2159 break; 2160 default: 2161 break; 2162 } 2163 } 2164 else if (is_gimple_assign (stmt) && !gimple_clobber_p (stmt)) 2165 { 2166 tree lhs = gimple_assign_lhs (stmt); 2167 2168 if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs))) 2169 { 2170 if (gimple_assign_single_p (stmt) 2171 || (gimple_assign_cast_p (stmt) 2172 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt))))) 2173 { 2174 int idx = get_stridx (gimple_assign_rhs1 (stmt)); 2175 ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = idx; 2176 } 2177 else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR) 2178 handle_pointer_plus (gsi); 2179 } 2180 else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs)) 2181 { 2182 tree type = TREE_TYPE (lhs); 2183 if (TREE_CODE (type) == ARRAY_TYPE) 2184 type = TREE_TYPE (type); 2185 if (TREE_CODE (type) == INTEGER_TYPE 2186 && TYPE_MODE (type) == TYPE_MODE (char_type_node) 2187 && TYPE_PRECISION (type) == TYPE_PRECISION (char_type_node)) 2188 { 2189 if (! handle_char_store (gsi)) 2190 return false; 2191 } 2192 } 2193 } 2194 2195 if (gimple_vdef (stmt)) 2196 maybe_invalidate (stmt); 2197 return true; 2198} 2199 2200/* Recursively call maybe_invalidate on stmts that might be executed 2201 in between dombb and current bb and that contain a vdef. Stop when 2202 *count stmts are inspected, or if the whole strinfo vector has 2203 been invalidated. */ 2204 2205static void 2206do_invalidate (basic_block dombb, gimple phi, bitmap visited, int *count) 2207{ 2208 unsigned int i, n = gimple_phi_num_args (phi); 2209 2210 for (i = 0; i < n; i++) 2211 { 2212 tree vuse = gimple_phi_arg_def (phi, i); 2213 gimple stmt = SSA_NAME_DEF_STMT (vuse); 2214 basic_block bb = gimple_bb (stmt); 2215 if (bb == NULL 2216 || bb == dombb 2217 || !bitmap_set_bit (visited, bb->index) 2218 || !dominated_by_p (CDI_DOMINATORS, bb, dombb)) 2219 continue; 2220 while (1) 2221 { 2222 if (gimple_code (stmt) == GIMPLE_PHI) 2223 { 2224 do_invalidate (dombb, stmt, visited, count); 2225 if (*count == 0) 2226 return; 2227 break; 2228 } 2229 if (--*count == 0) 2230 return; 2231 if (!maybe_invalidate (stmt)) 2232 { 2233 *count = 0; 2234 return; 2235 } 2236 vuse = gimple_vuse (stmt); 2237 stmt = SSA_NAME_DEF_STMT (vuse); 2238 if (gimple_bb (stmt) != bb) 2239 { 2240 bb = gimple_bb (stmt); 2241 if (bb == NULL 2242 || bb == dombb 2243 || !bitmap_set_bit (visited, bb->index) 2244 || !dominated_by_p (CDI_DOMINATORS, bb, dombb)) 2245 break; 2246 } 2247 } 2248 } 2249} 2250 2251class strlen_dom_walker : public dom_walker 2252{ 2253public: 2254 strlen_dom_walker (cdi_direction direction) : dom_walker (direction) {} 2255 2256 virtual void before_dom_children (basic_block); 2257 virtual void after_dom_children (basic_block); 2258}; 2259 2260/* Callback for walk_dominator_tree. Attempt to optimize various 2261 string ops by remembering string lenths pointed by pointer SSA_NAMEs. */ 2262 2263void 2264strlen_dom_walker::before_dom_children (basic_block bb) 2265{ 2266 basic_block dombb = get_immediate_dominator (CDI_DOMINATORS, bb); 2267 2268 if (dombb == NULL) 2269 stridx_to_strinfo = NULL; 2270 else 2271 { 2272 stridx_to_strinfo = ((vec<strinfo, va_heap, vl_embed> *) dombb->aux); 2273 if (stridx_to_strinfo) 2274 { 2275 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); 2276 gsi_next (&gsi)) 2277 { 2278 gphi *phi = gsi.phi (); 2279 if (virtual_operand_p (gimple_phi_result (phi))) 2280 { 2281 bitmap visited = BITMAP_ALLOC (NULL); 2282 int count_vdef = 100; 2283 do_invalidate (dombb, phi, visited, &count_vdef); 2284 BITMAP_FREE (visited); 2285 if (count_vdef == 0) 2286 { 2287 /* If there were too many vdefs in between immediate 2288 dominator and current bb, invalidate everything. 2289 If stridx_to_strinfo has been unshared, we need 2290 to free it, otherwise just set it to NULL. */ 2291 if (!strinfo_shared ()) 2292 { 2293 unsigned int i; 2294 strinfo si; 2295 2296 for (i = 1; 2297 vec_safe_iterate (stridx_to_strinfo, i, &si); 2298 ++i) 2299 { 2300 free_strinfo (si); 2301 (*stridx_to_strinfo)[i] = NULL; 2302 } 2303 } 2304 else 2305 stridx_to_strinfo = NULL; 2306 } 2307 break; 2308 } 2309 } 2310 } 2311 } 2312 2313 /* If all PHI arguments have the same string index, the PHI result 2314 has it as well. */ 2315 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); 2316 gsi_next (&gsi)) 2317 { 2318 gphi *phi = gsi.phi (); 2319 tree result = gimple_phi_result (phi); 2320 if (!virtual_operand_p (result) && POINTER_TYPE_P (TREE_TYPE (result))) 2321 { 2322 int idx = get_stridx (gimple_phi_arg_def (phi, 0)); 2323 if (idx != 0) 2324 { 2325 unsigned int i, n = gimple_phi_num_args (phi); 2326 for (i = 1; i < n; i++) 2327 if (idx != get_stridx (gimple_phi_arg_def (phi, i))) 2328 break; 2329 if (i == n) 2330 ssa_ver_to_stridx[SSA_NAME_VERSION (result)] = idx; 2331 } 2332 } 2333 } 2334 2335 /* Attempt to optimize individual statements. */ 2336 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) 2337 if (strlen_optimize_stmt (&gsi)) 2338 gsi_next (&gsi); 2339 2340 bb->aux = stridx_to_strinfo; 2341 if (vec_safe_length (stridx_to_strinfo) && !strinfo_shared ()) 2342 (*stridx_to_strinfo)[0] = (strinfo) bb; 2343} 2344 2345/* Callback for walk_dominator_tree. Free strinfo vector if it is 2346 owned by the current bb, clear bb->aux. */ 2347 2348void 2349strlen_dom_walker::after_dom_children (basic_block bb) 2350{ 2351 if (bb->aux) 2352 { 2353 stridx_to_strinfo = ((vec<strinfo, va_heap, vl_embed> *) bb->aux); 2354 if (vec_safe_length (stridx_to_strinfo) 2355 && (*stridx_to_strinfo)[0] == (strinfo) bb) 2356 { 2357 unsigned int i; 2358 strinfo si; 2359 2360 for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i) 2361 free_strinfo (si); 2362 vec_free (stridx_to_strinfo); 2363 } 2364 bb->aux = NULL; 2365 } 2366} 2367 2368/* Main entry point. */ 2369 2370namespace { 2371 2372const pass_data pass_data_strlen = 2373{ 2374 GIMPLE_PASS, /* type */ 2375 "strlen", /* name */ 2376 OPTGROUP_NONE, /* optinfo_flags */ 2377 TV_TREE_STRLEN, /* tv_id */ 2378 ( PROP_cfg | PROP_ssa ), /* properties_required */ 2379 0, /* properties_provided */ 2380 0, /* properties_destroyed */ 2381 0, /* todo_flags_start */ 2382 0, /* todo_flags_finish */ 2383}; 2384 2385class pass_strlen : public gimple_opt_pass 2386{ 2387public: 2388 pass_strlen (gcc::context *ctxt) 2389 : gimple_opt_pass (pass_data_strlen, ctxt) 2390 {} 2391 2392 /* opt_pass methods: */ 2393 virtual bool gate (function *) { return flag_optimize_strlen != 0; } 2394 virtual unsigned int execute (function *); 2395 2396}; // class pass_strlen 2397 2398unsigned int 2399pass_strlen::execute (function *fun) 2400{ 2401 ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names); 2402 max_stridx = 1; 2403 strinfo_pool = create_alloc_pool ("strinfo_struct pool", 2404 sizeof (struct strinfo_struct), 64); 2405 2406 calculate_dominance_info (CDI_DOMINATORS); 2407 2408 /* String length optimization is implemented as a walk of the dominator 2409 tree and a forward walk of statements within each block. */ 2410 strlen_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr); 2411 2412 ssa_ver_to_stridx.release (); 2413 free_alloc_pool (strinfo_pool); 2414 if (decl_to_stridxlist_htab) 2415 { 2416 obstack_free (&stridx_obstack, NULL); 2417 delete decl_to_stridxlist_htab; 2418 decl_to_stridxlist_htab = NULL; 2419 } 2420 laststmt.stmt = NULL; 2421 laststmt.len = NULL_TREE; 2422 laststmt.stridx = 0; 2423 2424 return 0; 2425} 2426 2427} // anon namespace 2428 2429gimple_opt_pass * 2430make_pass_strlen (gcc::context *ctxt) 2431{ 2432 return new pass_strlen (ctxt); 2433} 2434