#include "config.h"#include "system.h"#include "coretypes.h"#include "tree.h"#include "hash-table.h"#include "bitmap.h"#include "gimple.h"#include "gimple-ssa.h"#include "tree-phinodes.h"#include "ssa-iterators.h"#include "tree-ssanames.h"#include "tree-dfa.h"#include "tree-pass.h"#include "domwalk.h"#include "alloc-pool.h"#include "tree-ssa-propagate.h"#include "gimple-pretty-print.h"#include "params.h"#include "expr.h"
Data Structures | |
| struct | strinfo_struct |
| struct | stridxlist |
| struct | decl_stridxlist_map |
| struct | stridxlist_hasher |
| struct | laststmt_struct |
| class | strlen_dom_walker |
Typedefs | |
| typedef struct strinfo_struct * | strinfo |
Variables | |
| static vec< int > | ssa_ver_to_stridx |
| static int | max_stridx |
| static alloc_pool | strinfo_pool |
| static vec< strinfo, va_heap, vl_embed > * | stridx_to_strinfo |
| static hash_table < stridxlist_hasher > | decl_to_stridxlist_htab |
| static struct obstack | stridx_obstack |
| struct laststmt_struct | laststmt |
Typedef Documentation
| typedef struct strinfo_struct * strinfo |
String information record.
Function Documentation
|
static |
Attempt to create a string index for exp, ADDR_EXPR's operand. Return a pointer to the location where the string index can be stored (if 0) or is stored, or NULL if this can't be tracked.
Referenced by adjust_related_strinfos(), and new_stridx().
|
static |
If the last .MEM setter statement before STMT is memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to just memcpy (x, y, strlen (y)). SI must be the zero length strinfo.
Don't adjust the length if it is divisible by 4, it is more efficient to store the extra '\0' in that case.
References integer_zerop(), strinfo_struct::length, and NULL_TREE.
Referenced by handle_pointer_plus().
|
static |
For strinfo ORIGSI whose length has been just updated update also related strinfo lengths (add ADJ to each, but don't adjust ORIGSI).
Delayed length computation is unaffected.
References addr_stridxptr(), CASE_CONVERT, gimple_assign_rhs1(), gimple_assign_rhs_code(), is_gimple_assign(), NULL, num_ssa_names, POINTER_TYPE_P, SSA_NAME_DEF_STMT, SSA_NAME_VERSION, TREE_CODE, TREE_OPERAND, and TREE_TYPE.
|
static |
Recursively call maybe_invalidate on stmts that might be executed in between dombb and current bb and that contain a vdef. Stop when *count stmts are inspected, or if the whole strinfo vector has been invalidated.
Referenced by strlen_optimize_stmt().
|
static |
Find if there are other SSA_NAME pointers equal to PTR for which we don't track their string lengths yet. If so, use IDX for them.
FALLTHRU
We might find an endptr created in this pass. Grow the vector in that case.
References strinfo_struct::first, gcc_assert, get_strinfo(), gimple_vuse(), has_single_use(), strinfo_struct::idx, laststmt, laststmt_struct::len, strinfo_struct::next, NULL, NULL_TREE, strinfo_struct::prev, SSA_NAME_DEF_STMT, laststmt_struct::stmt, laststmt_struct::stridx, and verify_related_strinfos().
|
inlinestatic |
Decrease strinfo refcount and free it if not referenced anymore.
References strinfo_struct::length, and strinfo_struct::stmt.
Referenced by strlen_dom_walker::before_dom_children().
|
static |
|
static |
Helper function for get_stridx.
|
static |
Return string index for EXP.
|
inlinestatic |
Return strinfo vector entry IDX.
Referenced by find_equal_ptrs(), handle_pointer_plus(), and verify_related_strinfos().
|
static |
Return string length, or NULL if it can't be computed.
unshare_strinfo is intentionally not called here. The (delayed)
transformation of strcpy or strcat into stpcpy is done at the place
of the former strcpy/strcat call and so can affect all the strinfos
with the same stmt. If they were unshared before and transformation
has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
just compute the right length.
FALLTHRU
FALLTHRU
|
static |
Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call. If strlen of the second argument is known and length of the third argument is that plus one, strlen of the first argument is the same after this call.
Handle memcpy (x, y, l) where l is strlen (y) + 1.
Handle memcpy (x, "abcd", 5) or
memcpy (x, "abc\0uvw", 7). Break the chain, so adjust_related_strinfo on later pointers in
the chain won't adjust this one anymore. memcpy src may not overlap dst, so src doesn't need to be invalidated either.
Allow adjust_last_stmt to decrease this memcpy's size.
|
static |
Handle a strcat-like ({strcat,__strcat_chk}) call. If strlen of the second argument is known, strlen of the first argument is increased by the length of the second argument. Furthermore, attempt to convert it to memcpy/strcpy if the length of the first argument is known.
strcat (p, q) can be transformed into
tmp = p + strlen (p); endptr = strpcpy (tmp, q);
with length endptr - p if we need to compute the length
later on. Don't do this transformation if we don't need
it.
strcat src may not overlap dst, so src doesn't need to be invalidated either.
For now. Could remove the lhs from the call and add lhs = dst; afterwards.
If srclen == NULL, note that current string length can be
computed by transforming this strcpy into stpcpy.
|
static |
Handle a strchr call. If strlen of the first argument is known, replace the strchr (x, 0) call with the endptr or x + strlen, otherwise remember that lhs of the call is endptr and strlen of the argument is endptr - x.
|
static |
Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call. If strlen of the second argument is known, strlen of the first argument is the same after this call. Furthermore, attempt to convert it to memcpy.
Break the chain, so adjust_related_strinfo on later pointers in
the chain won't adjust this one anymore.
If string length of src is unknown, use delayed length
computation. If string lenth of dst will be needed, it
can be computed by transforming this strcpy call into
stpcpy and subtracting dst from the return value. Look for earlier strings whose length could be determined if
this strcpy is turned into an stpcpy. When setting a stmt for delayed length computation
prevent all strinfos through dsi from being
invalidated. strcpy src may not overlap dst, so src doesn't need to be invalidated either.
This would need adjustment of the lhs (subtract one),
or detection that the trailing '\0' doesn't need to be
written, if it will be immediately overwritten.
fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); This would need adjustment of the lhs (subtract one),
or detection that the trailing '\0' doesn't need to be
written, if it will be immediately overwritten.
fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); Allow adjust_last_stmt to decrease this memcpy's size.
|
static |
Handle a strlen call. If strlen of the argument is known, replace the strlen call with the known value, otherwise remember that strlen of the argument is stored in the lhs SSA_NAME.
References strinfo_struct::length, and unshare_strinfo().
|
static |
Handle a single character store.
When storing '\0', the store can be removed
if we know it has been stored in the current function.
Otherwise this statement overwrites the '\0' with
something, if the previous stmt was a memcpy,
its length may be decreased. If si->length is non-zero constant, we aren't overwriting '\0',
and if we aren't storing '\0', we know that the length of the
string and any other zero terminated string in memory remains
the same. In that case we move to the next gimple statement and
return to signal the caller that it shouldn't invalidate anything.
This is benefical for cases like:
char p[20];
void foo (char *q)
{
strcpy (p, "foobar");
size_t len = strlen (p); // This can be optimized into 6
size_t len2 = strlen (q); // This has to be computed
p[0] = 'X';
size_t len3 = strlen (p); // This can be optimized into 6
size_t len4 = strlen (q); // This can be optimized into len2
bar (len, len2, len3, len4);
} Allow adjust_last_stmt to remove it if the stored '\0'
is immediately overwritten.
References gsi_next().
|
static |
Handle a POINTER_PLUS_EXPR statement. For p = "abcd" + 2; compute associated length, or if p = q + off is pointing to a '\0' character of a string, call zero_length_string on it.
References adjust_last_stmt(), build_int_cst(), strinfo_struct::dont_invalidate, strinfo_struct::endptr, strinfo_struct::first, get_strinfo(), gimple_assign_rhs1(), gsi_next(), gsi_remove(), initializer_zerop(), integer_zerop(), strinfo_struct::length, strinfo_struct::next, NULL, NULL_TREE, strinfo_struct::prev, release_defs(), size_type_node, SSA_NAME_OCCURS_IN_ABNORMAL_PHI, strinfo_struct::stmt, stmt_could_throw_p(), unlink_stmt_vdef(), unshare_strinfo(), and strinfo_struct::writable.
| gimple_opt_pass* make_pass_strlen | ( | ) |
|
static |
Invalidate string length information for strings whose length might change due to stores in stmt.
Referenced by strlen_optimize_stmt().
|
static |
Like new_stridx, but for ADDR_EXPR's operand instead.
|
static |
Create a new string index, or return 0 if reached limit.
References addr_stridxptr(), gcc_assert, max_stridx, NULL, and PARAM_VALUE.
|
static |
Create a new strinfo.
References NULL, and vec_safe_length().
|
inlinestatic |
Set strinfo in the vector entry IDX to SI.
References builtin_decl_implicit(), gcc_assert, gimple_build_call(), gimple_call_arg(), gimple_call_set_lhs(), gsi_for_stmt(), make_ssa_name(), NULL_TREE, TREE_TYPE, and unshare_expr().
|
inlinestatic |
Return true if strinfo vector is shared with the immediate dominator.
References get_addr_base_and_unit_offset(), and HOST_WIDE_INT.
|
static |
Attempt to optimize a single statement at *GSI using string length knowledge.
References bitmap_set_bit, CDI_DOMINATORS, do_invalidate(), dominated_by_p(), gimple_bb(), gimple_phi_arg_def(), gimple_phi_num_args(), gimple_vuse(), basic_block_def::index, maybe_invalidate(), NULL, and SSA_NAME_DEF_STMT.
|
static |
Main entry point.
String length optimization is implemented as a walk of the dominator tree and a forward walk of statements within each block.
|
static |
Unshare strinfo record SI, if it has recount > 1 or if stridx_to_strinfo vector is shared with some other bbs.
Referenced by handle_builtin_strlen(), handle_pointer_plus(), and verify_related_strinfos().
|
static |
Unshare strinfo vector that is shared with the immediate dominator.
References hash_table< Descriptor, Allocator >::create(), gcc_obstack_init, and stridx_obstack.
|
static |
Return first strinfo in the related strinfo chain if all strinfos in between belong to the chain, otherwise NULL.
References strinfo_struct::endptr, strinfo_struct::first, get_strinfo(), strinfo_struct::idx, strinfo_struct::next, NULL, NULL_TREE, strinfo_struct::prev, and unshare_strinfo().
Referenced by find_equal_ptrs().
|
static |
Note that PTR, a pointer SSA_NAME initialized in the current stmt, points to a zero-length string and if possible chain it to a related strinfo chain whose part is or might be CHAINSI.
Variable Documentation
|
static |
Hash table for mapping decls to a chained list of offset -> idx mappings.
| struct laststmt_struct laststmt |
Referenced by find_equal_ptrs().
|
static |
Number of currently active string indexes plus one.
Referenced by new_stridx().
|
static |
String length optimization Copyright (C) 2011-2013 Free Software Foundation, Inc. Contributed by Jakub Jelinek jakub@redhat.com
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see http://www.gnu.org/licenses/. A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value is an index into strinfo vector, negative value stands for string length of a string literal (~strlen).
|
static |
Obstack for struct stridxlist and struct decl_stridxlist_map.
Referenced by unshare_strinfo_vec().
Vector mapping positive string indexes to strinfo, for the current basic block. The first pointer in the vector is special, it is either NULL, meaning the vector isn't shared, or it is a basic block pointer to the owner basic_block if shared. If some other bb wants to modify the vector, the vector needs to be unshared first, and only the owner bb is supposed to free it.
|
static |
Pool for allocating strinfo_struct entries.
