Data Structures
struct	strinfo_struct
struct	stridxlist
struct	decl_stridxlist_map
struct	stridxlist_hasher
struct	laststmt_struct

Typedefs
typedef struct strinfo_struct *	strinfo

Functions
static int	get_addr_stridx ()
static int	get_stridx ()
static bool	strinfo_shared ()
static void	unshare_strinfo_vec ()
static int *	addr_stridxptr ()
static int	new_stridx ()
static int	new_addr_stridx ()
static strinfo	new_strinfo ()
static void	free_strinfo ()
static strinfo	get_strinfo ()
static void	set_strinfo ()
static tree	get_string_length ()
static bool	maybe_invalidate ()
static strinfo	unshare_strinfo ()
static strinfo	verify_related_strinfos ()
static strinfo	zero_length_string ()
static void	adjust_related_strinfos ()
static void	find_equal_ptrs ()
static void	adjust_last_stmt ()
static void	handle_builtin_strlen ()
static void	handle_builtin_strchr ()
static void	handle_builtin_strcpy ()
static void	handle_builtin_memcpy ()
static void	handle_builtin_strcat ()
static void	handle_pointer_plus ()
static bool	handle_char_store ()
static bool	strlen_optimize_stmt ()
static void	do_invalidate ()
static void	strlen_enter_block (struct dom_walk_data *walk_data, basic_block bb)
static void	strlen_leave_block (struct dom_walk_data *walk_data, basic_block bb)
static unsigned int	tree_ssa_strlen ()
static bool	gate_strlen ()
gimple_opt_pass *	make_pass_strlen ()

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 int* addr_stridxptr ( )

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.

References decl_stridxlist_map::base, hash_table< Descriptor, Allocator >::create(), hash_table< Descriptor, Allocator >::find_slot_with_hash(), tree_map_base::from, get_addr_base_and_unit_offset(), HOST_WIDE_INT, stridxlist::idx, hash_table< Descriptor, Allocator >::is_created(), decl_stridxlist_map::list, stridxlist::next, stridxlist::offset, and stridx_obstack.

Referenced by find_equal_ptrs(), new_addr_stridx(), and new_stridx().

static void adjust_last_stmt ( )

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.

References BUILT_IN_NORMAL, strinfo_struct::first, get_strinfo(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_call_arg(), gimple_call_builtin_p(), gimple_call_fndecl(), gimple_call_set_arg(), gimple_vuse(), gsi_for_stmt(), gsi_remove(), has_single_use(), host_integerp(), HOST_WIDE_INT, strinfo_struct::idx, integer_onep(), integer_zerop(), is_gimple_assign(), laststmt, laststmt_struct::len, len, strinfo_struct::length, strinfo_struct::next, strinfo_struct::prev, release_defs(), laststmt_struct::stmt, stmt_could_throw_p(), laststmt_struct::stridx, tree_low_cst(), unlink_stmt_vdef(), update_stmt(), and verify_related_strinfos().

Referenced by handle_builtin_memcpy(), handle_builtin_strcat(), handle_builtin_strcpy(), and handle_char_store().

static void adjust_related_strinfos ( )

static

For strinfo ORIGSI whose length has been just updated
   update also related strinfo lengths (add ADJ to each,
   but don't adjust ORIGSI).

References strinfo_struct::dont_invalidate, strinfo_struct::endptr, strinfo_struct::first, fold_convert_loc(), get_strinfo(), strinfo_struct::idx, strinfo_struct::length, strinfo_struct::next, strinfo_struct::prev, si, strinfo_struct::stmt, unshare_strinfo(), and verify_related_strinfos().

Referenced by handle_builtin_memcpy(), handle_builtin_strcat(), and handle_builtin_strcpy().

static void do_invalidate ( )

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.

References bitmap_set_bit(), CDI_DOMINATORS, dominated_by_p(), gimple_bb(), gimple_phi_arg_def(), gimple_phi_num_args(), gimple_vuse(), basic_block_def::index, maybe_invalidate(), and laststmt_struct::stmt.

Referenced by strlen_enter_block().

static void find_equal_ptrs ( )

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.

References addr_stridxptr(), gimple_assign_rhs1(), gimple_assign_rhs_code(), and is_gimple_assign().

Referenced by handle_builtin_memcpy(), handle_builtin_strcat(), handle_builtin_strchr(), handle_builtin_strcpy(), and handle_builtin_strlen().

static void free_strinfo ( )

inlinestatic

Decrease strinfo refcount and free it if not referenced anymore.

References pool_free(), and strinfo_struct::refcount.

Referenced by maybe_invalidate(), strlen_leave_block(), and unshare_strinfo().

static bool gate_strlen ( )

static

static int get_addr_stridx ( )

static

Helper function for get_stridx.

References decl_stridxlist_map::base, hash_table< Descriptor, Allocator >::find_with_hash(), tree_map_base::from, get_addr_base_and_unit_offset(), HOST_WIDE_INT, stridxlist::idx, hash_table< Descriptor, Allocator >::is_created(), decl_stridxlist_map::list, stridxlist::next, and stridxlist::offset.

Referenced by get_stridx(), and handle_char_store().

static int get_stridx ( )

static

Return string index for EXP.

References get_addr_stridx(), host_integerp(), HOST_WIDE_INT, stridxlist::idx, offset, string_constant(), strlen(), and tree_low_cst().

Referenced by handle_builtin_memcpy(), handle_builtin_strcat(), handle_builtin_strchr(), handle_builtin_strcpy(), handle_builtin_strlen(), handle_char_store(), handle_pointer_plus(), strlen_enter_block(), strlen_optimize_stmt(), and zero_length_string().

static strinfo get_strinfo ( )

inlinestatic

Return strinfo vector entry IDX.

References vec_safe_length().

Referenced by adjust_last_stmt(), adjust_related_strinfos(), handle_builtin_memcpy(), handle_builtin_strcat(), handle_builtin_strchr(), handle_builtin_strcpy(), handle_builtin_strlen(), handle_char_store(), handle_pointer_plus(), verify_related_strinfos(), and zero_length_string().

static tree get_string_length ( )

static

Return string length, or NULL if it can't be computed.

References BUILT_IN_NORMAL, builtin_decl_explicit(), builtin_decl_implicit(), builtin_decl_implicit_p(), dump_file, dump_flags, strinfo_struct::endptr, fold_convert_loc(), force_gimple_operand_gsi(), gimple_assign_lhs(), gimple_build_assign_with_ops(), gimple_build_call(), gimple_call_arg(), gimple_call_fndecl(), gimple_call_lhs(), gimple_call_num_args(), gimple_call_set_arg(), gimple_call_set_fndecl(), gimple_call_set_lhs(), gimple_location(), gimple_set_vuse(), gimple_vuse(), gsi_for_stmt(), gsi_insert_before(), GSI_SAME_STMT, is_gimple_call(), strinfo_struct::length, make_ssa_name(), print_gimple_stmt(), strinfo_struct::ptr, ptrofftype_p(), strinfo_struct::stmt, unshare_expr(), and update_stmt().

Referenced by handle_builtin_strcat(), handle_builtin_strchr(), handle_builtin_strcpy(), and handle_builtin_strlen().

static void handle_builtin_memcpy ( )

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.

References adjust_last_stmt(), adjust_related_strinfos(), build_int_cst(), strinfo_struct::dont_invalidate, strinfo_struct::endptr, find_equal_ptrs(), fold_convert_loc(), get_stridx(), get_strinfo(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_call_arg(), gimple_call_lhs(), gimple_location(), gsi_stmt(), host_integerp(), HOST_WIDE_INT, strinfo_struct::idx, integer_onep(), integer_zerop(), is_gimple_assign(), laststmt, laststmt_struct::len, len, strinfo_struct::length, new_stridx(), new_strinfo(), strinfo_struct::next, strinfo_struct::prev, set_strinfo(), si, strinfo_struct::stmt, laststmt_struct::stmt, laststmt_struct::stridx, tree_low_cst(), unshare_strinfo(), and strinfo_struct::writable.

Referenced by strlen_optimize_stmt().

static void handle_builtin_strcat ( )

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.

References adjust_last_stmt(), adjust_related_strinfos(), build_int_cst(), builtin_decl_explicit(), builtin_decl_implicit(), builtin_decl_implicit_p(), strinfo_struct::dont_invalidate, dump_file, dump_flags, strinfo_struct::endptr, find_equal_ptrs(), fold_convert_loc(), force_gimple_operand_gsi(), get_stridx(), get_strinfo(), get_string_length(), gimple_call_arg(), gimple_call_lhs(), gimple_location(), GSI_SAME_STMT, gsi_stmt(), strinfo_struct::idx, laststmt, laststmt_struct::len, len, strinfo_struct::length, new_stridx(), new_strinfo(), strinfo_struct::next, print_gimple_stmt(), set_strinfo(), si, strinfo_struct::stmt, laststmt_struct::stmt, laststmt_struct::stridx, type(), unshare_expr(), unshare_strinfo(), update_gimple_call(), update_stmt(), and strinfo_struct::writable.

Referenced by strlen_optimize_stmt().

static void handle_builtin_strchr ( )

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.

References build_int_cst(), dump_file, dump_flags, strinfo_struct::endptr, find_equal_ptrs(), fold_convert_loc(), get_stridx(), get_strinfo(), get_string_length(), gimple_call_arg(), gimple_call_lhs(), gimple_location(), gimplify_and_update_call_from_tree(), gsi_stmt(), integer_zerop(), new_stridx(), new_strinfo(), print_gimple_stmt(), set_strinfo(), si, laststmt_struct::stmt, unshare_expr(), unshare_strinfo(), update_call_from_tree(), update_stmt(), useless_type_conversion_p(), and zero_length_string().

Referenced by strlen_optimize_stmt().

static void handle_builtin_strcpy ( )

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.

References adjust_last_stmt(), adjust_related_strinfos(), build_int_cst(), builtin_decl_explicit(), builtin_decl_implicit(), builtin_decl_implicit_p(), strinfo_struct::dont_invalidate, dump_file, dump_flags, strinfo_struct::endptr, find_equal_ptrs(), fold_convert_loc(), force_gimple_operand_gsi(), get_stridx(), get_strinfo(), get_string_length(), gimple_call_arg(), gimple_call_lhs(), gimple_call_num_args(), gimple_location(), GSI_SAME_STMT, gsi_stmt(), strinfo_struct::idx, integer_zerop(), laststmt, laststmt_struct::len, len, strinfo_struct::length, new_stridx(), new_strinfo(), strinfo_struct::next, strinfo_struct::prev, print_gimple_stmt(), set_strinfo(), si, strinfo_struct::stmt, laststmt_struct::stmt, laststmt_struct::stridx, type(), unshare_expr(), unshare_strinfo(), update_gimple_call(), update_stmt(), verify_related_strinfos(), strinfo_struct::writable, and zero_length_string().

Referenced by strlen_optimize_stmt().

static void handle_builtin_strlen ( )

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 build_int_cst(), dump_file, dump_flags, find_equal_ptrs(), fold_convert_loc(), get_stridx(), get_strinfo(), get_string_length(), gimple_call_arg(), gimple_call_lhs(), gimple_location(), gimplify_and_update_call_from_tree(), gsi_stmt(), strinfo_struct::length, new_stridx(), new_strinfo(), print_gimple_stmt(), set_strinfo(), si, laststmt_struct::stmt, unshare_expr(), unshare_strinfo(), update_call_from_tree(), update_stmt(), and useless_type_conversion_p().

Referenced by strlen_optimize_stmt().

static bool handle_char_store ( )

static

Handle a single character store.

References adjust_last_stmt(), build_int_cst(), strinfo_struct::dont_invalidate, strinfo_struct::endptr, strinfo_struct::first, get_addr_stridx(), get_stridx(), get_strinfo(), gimple_assign_lhs(), gimple_assign_rhs1(), gsi_next(), gsi_remove(), gsi_stmt(), HOST_WIDE_INT, strinfo_struct::idx, initializer_zerop(), int_size_in_bytes(), integer_nonzerop(), integer_zerop(), laststmt, laststmt_struct::len, strinfo_struct::length, new_addr_stridx(), new_strinfo(), strinfo_struct::next, strinfo_struct::prev, release_defs(), set_strinfo(), si, strinfo_struct::stmt, laststmt_struct::stmt, stmt_could_throw_p(), laststmt_struct::stridx, strlen(), unlink_stmt_vdef(), unshare_strinfo(), strinfo_struct::writable, and zero_length_string().

Referenced by strlen_optimize_stmt().

static void handle_pointer_plus ( )

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 strinfo_struct::endptr, get_stridx(), get_strinfo(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_set_rhs_with_ops(), gimple_assign_single_p(), gsi_stmt(), host_integerp(), HOST_WIDE_INT, strinfo_struct::length, operand_equal_p(), si, laststmt_struct::stmt, tree_low_cst(), update_stmt(), useless_type_conversion_p(), and zero_length_string().

Referenced by strlen_optimize_stmt().

gimple_opt_pass* make_pass_strlen ( )

static bool maybe_invalidate ( )

static

Invalidate string length information for strings whose length
   might change due to stores in stmt.

References ao_ref_init_from_ptr_and_size(), strinfo_struct::dont_invalidate, free_strinfo(), strinfo_struct::ptr, set_strinfo(), si, stmt_may_clobber_ref_p_1(), and vec_safe_iterate().

Referenced by do_invalidate(), and strlen_optimize_stmt().

static int new_addr_stridx ( )

static

Like new_stridx, but for ADDR_EXPR's operand instead.

References addr_stridxptr(), and max_stridx.

Referenced by handle_char_store().

static int new_stridx ( )

static

Create a new string index, or return 0 if reached limit.

References addr_stridxptr(), and max_stridx.

Referenced by handle_builtin_memcpy(), handle_builtin_strcat(), handle_builtin_strchr(), handle_builtin_strcpy(), handle_builtin_strlen(), and zero_length_string().

static strinfo new_strinfo ( )

static

Create a new strinfo.

References strinfo_struct::dont_invalidate, strinfo_struct::endptr, strinfo_struct::first, strinfo_struct::idx, strinfo_struct::length, strinfo_struct::next, pool_alloc(), strinfo_struct::prev, strinfo_struct::ptr, strinfo_struct::refcount, si, strinfo_struct::stmt, and strinfo_struct::writable.

Referenced by handle_builtin_memcpy(), handle_builtin_strcat(), handle_builtin_strchr(), handle_builtin_strcpy(), handle_builtin_strlen(), handle_char_store(), unshare_strinfo(), and zero_length_string().

static void set_strinfo ( )

inlinestatic

Set strinfo in the vector entry IDX to SI.

References si, unshare_strinfo_vec(), vec_safe_grow_cleared(), and vec_safe_length().

Referenced by handle_builtin_memcpy(), handle_builtin_strcat(), handle_builtin_strchr(), handle_builtin_strcpy(), handle_builtin_strlen(), handle_char_store(), maybe_invalidate(), unshare_strinfo(), and zero_length_string().

static bool strinfo_shared ( )

inlinestatic

Return true if strinfo vector is shared with the immediate dominator.

References vec_safe_length().

Referenced by strlen_enter_block(), unshare_strinfo(), and unshare_strinfo_vec().

static void strlen_enter_block	(	struct dom_walk_data *	walk_data,
		basic_block	bb
	)

static

Callback for walk_dominator_tree.  Attempt to optimize various
   string ops by remembering string lenths pointed by pointer SSA_NAMEs.

References basic_block_def::aux, CDI_DOMINATORS, do_invalidate(), get_immediate_dominator(), get_stridx(), gimple_phi_arg_def(), gimple_phi_num_args(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), stridx_to_strinfo, strinfo_shared(), strlen_optimize_stmt(), vec_safe_length(), virtual_operand_p(), and visited.

Referenced by tree_ssa_strlen().

static void strlen_leave_block	(	struct dom_walk_data *	walk_data,
		basic_block	bb
	)

static

Callback for walk_dominator_tree.  Free strinfo vector if it is
   owned by the current bb, clear bb->aux.

References basic_block_def::aux, free_strinfo(), si, vec_free(), vec_safe_iterate(), and vec_safe_length().

Referenced by tree_ssa_strlen().

static bool strlen_optimize_stmt ( )

static

Attempt to optimize a single statement at *GSI using string length
   knowledge.

References BUILT_IN_NORMAL, get_stridx(), gimple_assign_cast_p(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs_code(), gimple_assign_single_p(), gimple_call_builtin_p(), gimple_call_fndecl(), gimple_vdef(), gsi_stmt(), handle_builtin_memcpy(), handle_builtin_strcat(), handle_builtin_strchr(), handle_builtin_strcpy(), handle_builtin_strlen(), handle_char_store(), handle_pointer_plus(), is_gimple_assign(), is_gimple_call(), maybe_invalidate(), and laststmt_struct::stmt.

Referenced by strlen_enter_block().

static strinfo unshare_strinfo ( )

static

Unshare strinfo record SI, if it has recount > 1 or
   if stridx_to_strinfo vector is shared with some other
   bbs.

References strinfo_struct::endptr, strinfo_struct::first, free_strinfo(), strinfo_struct::idx, strinfo_struct::length, new_strinfo(), strinfo_struct::next, strinfo_struct::prev, strinfo_struct::ptr, strinfo_struct::refcount, set_strinfo(), si, strinfo_struct::stmt, strinfo_shared(), and strinfo_struct::writable.

Referenced by adjust_related_strinfos(), handle_builtin_memcpy(), handle_builtin_strcat(), handle_builtin_strchr(), handle_builtin_strcpy(), handle_builtin_strlen(), handle_char_store(), and zero_length_string().

static void unshare_strinfo_vec ( )

static

Unshare strinfo vector that is shared with the immediate dominator.

References strinfo_struct::refcount, si, strinfo_shared(), vec_safe_copy(), and vec_safe_iterate().

Referenced by set_strinfo().

static strinfo verify_related_strinfos ( )

static

Return first strinfo in the related strinfo chain
   if all strinfos in between belong to the chain, otherwise
   NULL.

References strinfo_struct::first, get_strinfo(), strinfo_struct::idx, strinfo_struct::prev, and si.

Referenced by adjust_last_stmt(), adjust_related_strinfos(), handle_builtin_strcpy(), and zero_length_string().

static strinfo zero_length_string ( )

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.

References build_int_cst(), strinfo_struct::endptr, strinfo_struct::first, get_stridx(), get_strinfo(), strinfo_struct::idx, integer_zerop(), strinfo_struct::length, new_stridx(), new_strinfo(), strinfo_struct::next, strinfo_struct::prev, set_strinfo(), si, strinfo_struct::stmt, unshare_strinfo(), verify_related_strinfos(), and strinfo_struct::writable.

Referenced by handle_builtin_strchr(), handle_builtin_strcpy(), handle_char_store(), and handle_pointer_plus().

Variable Documentation

hash_table<stridxlist_hasher> decl_to_stridxlist_htab

static

Hash table for mapping decls to a chained list of offset -> idx
   mappings.

struct laststmt_struct laststmt

Referenced by adjust_last_stmt(), handle_builtin_memcpy(), handle_builtin_strcat(), handle_builtin_strcpy(), handle_char_store(), and tree_ssa_strlen().

int max_stridx

static

Number of currently active string indexes plus one.

Referenced by new_addr_stridx(), new_stridx(), and tree_ssa_strlen().

vec<int> ssa_ver_to_stridx

static

@verbatim String length optimization

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).

struct obstack stridx_obstack

static

Obstack for struct stridxlist and struct decl_stridxlist_map.

Referenced by addr_stridxptr(), and tree_ssa_strlen().

vec<strinfo, va_heap, vl_embed>* stridx_to_strinfo

static

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.

Referenced by strlen_enter_block().

alloc_pool strinfo_pool

static

Pool for allocating strinfo_struct entries.

Data Structures

Typedefs

Functions

Variables

Typedef Documentation

Function Documentation

Variable Documentation