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

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

Referenced by adjust_related_strinfos(), 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.

         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(), and strinfo_struct::length.

Referenced by handle_pointer_plus().

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

               Delayed length computation is unaffected.

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

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.

Referenced by strlen_optimize_stmt().

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.

             FALLTHRU

         We might find an endptr created in this pass.  Grow the
         vector in that case.

References strinfo_struct::first, get_strinfo(), gimple_vuse(), has_single_use(), strinfo_struct::idx, laststmt, laststmt_struct::len, len, strinfo_struct::next, strinfo_struct::prev, laststmt_struct::stmt, laststmt_struct::stridx, and verify_related_strinfos().

static void free_strinfo ( )

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 bool gate_strlen ( )

static

static int get_addr_stridx ( )

static

   Helper function for get_stridx.

static int get_stridx ( )

static

   Return string index for EXP.

static strinfo get_strinfo ( )

inlinestatic

   Return strinfo vector entry IDX.

Referenced by find_equal_ptrs(), handle_pointer_plus(), and verify_related_strinfos().

static tree get_string_length ( )

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

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

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

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.

         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 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 strinfo_struct::length, and unshare_strinfo().

static bool handle_char_store ( )

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 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 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, strinfo_struct::prev, release_defs(), strinfo_struct::stmt, stmt_could_throw_p(), unlink_stmt_vdef(), unshare_strinfo(), and strinfo_struct::writable.

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.

Referenced by strlen_optimize_stmt().

static int new_addr_stridx ( )

static

   Like new_stridx, but for ADDR_EXPR's operand instead.

static int new_stridx ( )

static

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

References addr_stridxptr(), and max_stridx.

static strinfo new_strinfo ( )

static

   Create a new strinfo.

References vec_safe_length().

static void set_strinfo ( )

inlinestatic

   Set strinfo in the vector entry IDX to SI.

References builtin_decl_implicit(), gimple_build_call(), gimple_call_arg(), gimple_call_set_lhs(), gsi_for_stmt(), make_ssa_name(), and unshare_expr().

static bool strinfo_shared ( )

inlinestatic

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

References get_addr_base_and_unit_offset(), and HOST_WIDE_INT.

static bool strlen_optimize_stmt ( )

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, and maybe_invalidate().

static unsigned int tree_ssa_strlen ( )

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

Referenced by handle_builtin_strlen(), handle_pointer_plus(), and verify_related_strinfos().

static void unshare_strinfo_vec ( )

static

   Unshare strinfo vector that is shared with the immediate dominator.

References hash_table< Descriptor, Allocator >::create(), and stridx_obstack.

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::endptr, strinfo_struct::first, get_strinfo(), strinfo_struct::idx, strinfo_struct::next, strinfo_struct::prev, and unshare_strinfo().

Referenced by find_equal_ptrs().

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.

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

int max_stridx

static

   Number of currently active string indexes plus one.

Referenced by new_stridx().

vec<int> ssa_ver_to_stridx

static

@verbatim

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

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.

alloc_pool strinfo_pool

static

   Pool for allocating strinfo_struct entries.

Data Structures

Typedefs

Functions

Variables

Typedef Documentation

Function Documentation

Variable Documentation