GCC Middle and Back End API Reference
tree-ssa-strlen.c File Reference

Data Structures

struct  strinfo_struct
struct  stridxlist
struct  decl_stridxlist_map
struct  stridxlist_hasher
struct  laststmt_struct
class  strlen_dom_walker


typedef struct strinfo_structstrinfo


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_passmake_pass_strlen ()


static vec< int > ssa_ver_to_stridx
static int max_stridx
static alloc_pool strinfo_pool
static vec< strinfo, va_heap,
vl_embed > * 
static hash_table
< stridxlist_hasher
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 ( )
   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 ( )
   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
         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 ( )
   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 ( )
   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 ( )
   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.  
         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 ( )
   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 int get_addr_stridx ( )
   Helper function for get_stridx.  
static int get_stridx ( )
   Return string index for EXP.  
static strinfo get_strinfo ( )
   Return strinfo vector entry IDX.  

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

static tree get_string_length ( )
   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.  
static void handle_builtin_memcpy ( )
   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
         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 ( )
   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
       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 ( )
   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 ( )
   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
         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
     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 ( )
   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 ( )
   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 ( )
gimple_opt_pass* make_pass_strlen ( )
static bool maybe_invalidate ( )
   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 ( )
   Like new_stridx, but for ADDR_EXPR's operand instead.  
static int new_stridx ( )
   Create a new string index, or return 0 if reached limit.  

References addr_stridxptr(), and max_stridx.

static strinfo new_strinfo ( )
   Create a new strinfo.  

References vec_safe_length().

static void set_strinfo ( )
static bool strinfo_shared ( )
   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 ( )
   Attempt to optimize a single statement at *GSI using string length

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 ( )
   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 ( )
   Unshare strinfo record SI, if it has recount > 1 or
   if stridx_to_strinfo vector is shared with some other

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

static void unshare_strinfo_vec ( )
   Unshare strinfo vector that is shared with the immediate dominator.  

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

static strinfo verify_related_strinfos ( )
   Return first strinfo in the related strinfo chain
   if all strinfos in between belong to the chain, otherwise

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 ( )
   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
   Hash table for mapping decls to a chained list of offset -> idx
struct laststmt_struct laststmt

Referenced by find_equal_ptrs().

int max_stridx
   Number of currently active string indexes plus one.  

Referenced by new_stridx().

vec<int> ssa_ver_to_stridx

String length optimization Copyright (C) 2011-2013 Free Software Foundation, Inc. Contributed by Jakub Jelinek jakub.nosp@m.@red.nosp@m.hat.c.nosp@m.om

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
   Obstack for struct stridxlist and struct decl_stridxlist_map.  

Referenced by unshare_strinfo_vec().

vec<strinfo, va_heap, vl_embed>* stridx_to_strinfo
   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
   Pool for allocating strinfo_struct entries.