[tree-ssa] Prevent infinite loop in get_strlen

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

get_strlen in tree-ssa-ccp.c loops infinitely (well, until it runs out
of stack) when there is a nontrivial loop in phi nodes of the ssa graph.
This patch fixes it.  Bootstrapped & regtested on i686.

Zdenek

	* tree-ssa-ccp.c (get_strlen): Mark the visited variables.
	(ccp_fold_builtin): Changed due to the changed calling convention of
	get_strlen.

Testcase:

void foo(int i)
{
  char *s = "abcde";

  if (i)
    {
      s = "defgh";
      goto middle;
    }

start:

  bla ();

middle:

  if (bla ())
    goto start;

  bar (strlen (s));
}

Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-ccp.c,v
retrieving revision 1.1.2.117
diff -c -3 -p -r1.1.2.117 tree-ssa-ccp.c
*** tree-ssa-ccp.c	21 Nov 2003 23:12:35 -0000	1.1.2.117
--- tree-ssa-ccp.c	27 Nov 2003 10:45:33 -0000
*************** static void set_rhs (tree *, tree);
*** 122,128 ****
  static inline value *get_value (tree);
  static value get_default_value (tree);
  static tree ccp_fold_builtin (tree, tree);
! static tree get_strlen (tree);
  static inline bool cfg_blocks_empty_p (void);
  static void cfg_blocks_add (basic_block);
  static basic_block cfg_blocks_get (void);
--- 122,128 ----
  static inline value *get_value (tree);
  static value get_default_value (tree);
  static tree ccp_fold_builtin (tree, tree);
! static bool get_strlen (tree, tree *, bitmap);
  static inline bool cfg_blocks_empty_p (void);
  static void cfg_blocks_add (basic_block);
  static basic_block cfg_blocks_get (void);
*************** ccp_fold_builtin (tree stmt, tree fn)
*** 2027,2032 ****
--- 2027,2033 ----
    tree result;
    tree arglist = TREE_OPERAND (fn, 1);
    tree callee = get_callee_fndecl (fn);
+   bitmap visited;
  
    /* Ignore MD builtins.  */
    if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_MD)
*************** ccp_fold_builtin (tree stmt, tree fn)
*** 2040,2058 ****
  
    /* Otherwise, try to use the dataflow information gathered by the CCP
       process.  */
    switch (DECL_FUNCTION_CODE (callee))
      {
        case BUILT_IN_STRLEN:
! 	return get_strlen (TREE_VALUE (arglist));
  
        case BUILT_IN_FPUTS:
  	return simplify_builtin_fputs (arglist,
  				       TREE_CODE (stmt) != MODIFY_EXPR, 0,
! 				       get_strlen (TREE_VALUE (arglist)));
        case BUILT_IN_FPUTS_UNLOCKED:
  	return simplify_builtin_fputs (arglist,
  				       TREE_CODE (stmt) != MODIFY_EXPR, 1,
! 				       get_strlen (TREE_VALUE (arglist)));
  
        default:
  	break;
--- 2041,2064 ----
  
    /* Otherwise, try to use the dataflow information gathered by the CCP
       process.  */
+   visited = BITMAP_XMALLOC ();
+   if (!get_strlen (TREE_VALUE (arglist), &result, visited))
+     result = NULL_TREE;
+   BITMAP_XFREE (visited);
+ 
    switch (DECL_FUNCTION_CODE (callee))
      {
        case BUILT_IN_STRLEN:
! 	return result;
  
        case BUILT_IN_FPUTS:
  	return simplify_builtin_fputs (arglist,
  				       TREE_CODE (stmt) != MODIFY_EXPR, 0,
! 				       result);
        case BUILT_IN_FPUTS_UNLOCKED:
  	return simplify_builtin_fputs (arglist,
  				       TREE_CODE (stmt) != MODIFY_EXPR, 1,
! 				       result);
  
        default:
  	break;
*************** ccp_fold_builtin (tree stmt, tree fn)
*** 2063,2080 ****
  }
  
  
! /* Return the string length of ARG.  If ARG is an SSA name variable, follow
!    its use-def chains.  If all the reaching definitions for VAR have the
!    same length L, this function returns L.  Otherwise, it returns NULL_TREE
!    indicating that the length cannot be determined statically.  */
  
! static tree
! get_strlen (tree arg)
  {
!   tree var, def_stmt;
    
    if (TREE_CODE (arg) != SSA_NAME)
!     return c_strlen (arg, 1);
  
    var = arg;
    def_stmt = SSA_NAME_DEF_STMT (var);
--- 2069,2105 ----
  }
  
  
! /* Return the string length of ARG in LENGTH.  If ARG is an SSA name variable,
!    follow its use-def chains.  If LENGTH is not NULL and its value is not
!    equal to the length we determine, or if we are unable to determine the
!    length, return false.  VISITED is a bitmap of visited variables.  */
  
! static bool
! get_strlen (tree arg, tree *length, bitmap visited)
  {
!   tree var, def_stmt, val;
    
    if (TREE_CODE (arg) != SSA_NAME)
!     {
!       val = c_strlen (arg, 1);
!       if (!val)
! 	return false;
! 
!       /* Convert from the internal "sizetype" type to "size_t".  */
!       if (size_type_node)
! 	val = convert (size_type_node, val);
!       if (*length
! 	  && simple_cst_equal (val, *length) != 1)
! 	return false;
! 
!       *length = val;
!       return true;
!     }
! 
!   /* If we were already here, break the infinite cycle.  */
!   if (bitmap_bit_p (visited, SSA_NAME_VERSION (arg)))
!     return true;
!   bitmap_set_bit (visited, SSA_NAME_VERSION (arg));
  
    var = arg;
    def_stmt = SSA_NAME_DEF_STMT (var);
*************** get_strlen (tree arg)
*** 2091,2097 ****
  	  rhs = TREE_OPERAND (def_stmt, 1);
  	  STRIP_NOPS (rhs);
  	  if (TREE_CODE (rhs) == SSA_NAME)
! 	    return get_strlen (rhs);
  
  	  /* See if the RHS is a constant length.  */
  	  len = c_strlen (rhs, 1);
--- 2116,2122 ----
  	  rhs = TREE_OPERAND (def_stmt, 1);
  	  STRIP_NOPS (rhs);
  	  if (TREE_CODE (rhs) == SSA_NAME)
! 	    return get_strlen (rhs, length, visited);
  
  	  /* See if the RHS is a constant length.  */
  	  len = c_strlen (rhs, 1);
*************** get_strlen (tree arg)
*** 2100,2106 ****
  	      /* Convert from the internal "sizetype" type to "size_t".  */
  	      if (size_type_node)
  		len = convert (size_type_node, len);
! 	      return len;
  	    }
  
  	  break;
--- 2125,2136 ----
  	      /* Convert from the internal "sizetype" type to "size_t".  */
  	      if (size_type_node)
  		len = convert (size_type_node, len);
! 	      if (*length
! 		  && simple_cst_equal (len, *length) != 1)
! 		return false;
! 
! 	      *length = len;
! 	      return true;
  	    }
  
  	  break;
*************** get_strlen (tree arg)
*** 2111,2119 ****
  	  /* All the arguments of the PHI node must have the same constant
  	     length.  */
  	  int i;
- 	  tree arg_len, prev_arg_len;
  
- 	  arg_len = prev_arg_len = NULL_TREE;
  	  for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
  	    {
  	      tree arg = PHI_ARG_DEF (def_stmt, i);
--- 2141,2147 ----
*************** get_strlen (tree arg)
*** 2127,2144 ****
  	      if (arg == PHI_RESULT (def_stmt))
  		continue;
  
! 	      arg_len = get_strlen (arg);
! 	      if (arg_len == NULL_TREE)
! 		return NULL_TREE;
! 
! 	      if (prev_arg_len
! 		  && simple_cst_equal (prev_arg_len, arg_len) != 1)
! 		return NULL_TREE;
! 
! 	      prev_arg_len = arg_len;
  	    }
  
! 	  return arg_len;
  	}
  
        default:
--- 2155,2165 ----
  	      if (arg == PHI_RESULT (def_stmt))
  		continue;
  
! 	      if (!get_strlen (arg, length, visited))
! 		return false;
  	    }
  
! 	  return true;
  	}
  
        default:
*************** get_strlen (tree arg)
*** 2146,2152 ****
      }
  
  
!   return NULL_TREE;
  }
  
  #include "gt-tree-ssa-ccp.h"
--- 2167,2173 ----
      }
  
  
!   return false;
  }
  
  #include "gt-tree-ssa-ccp.h"