Moved array notation helper functions from c/ to c-family/ files.

2013-06-07  Balaji V. Iyer  <balaji.v.iyer@intel.com>

        * c-array-notation.c (length_mismatch_in_expr_p): Moved this
        function to c-family/array-notation-common.c.
        (is_cilkplus_reduce_builtin): Likewise.
        (find_rank): Likewise.
        (extract_array_notation_exprs): Likewise.
        (replace_array_notations): Likewise.
        (find_inv_trees): Likewise.
        (replace_inv_trees): Likewise.
        (contains_array_notation_expr): Likewise.
        (find_correct_array_notation_type): Likewise.
        (replace_invariant_exprs): Initialized additional_tcodes to NULL.
        (struct inv_list): Moved this to c-family/array-notation-common.c.
        * c-tree.h (is_cilkplus_builtin_reduce): Remove prototype.

2013-06-07  Balaji V. Iyer  <balaji.v.iyer@intel.com>

        * array-notation-common.c (length_mismatch_in_expr_p): Moved this
        function from c/c-array-notation.c.
        (is_cilkplus_reduce_builtin): Likewise.
        (find_rank): Likewise.
        (extract_array_notation_exprs): Likewise.
        (replace_array_notations): Likewise.
        (find_inv_trees): Likewise.
        (replace_inv_trees): Likewise.
        (contains_array_notation_expr): Likewise.
        (find_correct_array_notation_type): Likewise.
        * c-common.h (struct inv_list): Moved this struct from the file
        c/c-array-notation.c and added a new field called additional tcodes.
        (length_mismatch_in_expr_p): New prototype.
        (is_cilkplus_reduce_builtin): Likewise.
        (find_rank): Likewise.
        (extract_array_notation_exprs): Likewise.
        (replace_array_notation): Likewise.
        (find_inv_trees): Likewise.
        (replace_inv_trees): Likewise.

From-SVN: r199825

1 files changed, 487 insertions, 1 deletions

diff --git a/gcc/c-family/array-notation-common.c b/gcc/c-family/array-notation-common.c
index 1d28846..489b67c 100644
--- a/gcc/c-family/array-notation-common.c
+++ b/gcc/c-family/array-notation-common.c
@@ -27,9 +27,9 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree.h"
 #include "langhooks.h" 
 #include "tree-iterator.h"
+#include "c-family/c-common.h"
 #include "diagnostic-core.h"
 
-
 /* Returns true if the function call in FNDECL is  __sec_implicit_index.  */
 
 bool
@@ -74,3 +74,489 @@ extract_sec_implicit_index_arg (location_t location, tree fn)
     }
   return return_int;
 }
+
+/* Returns true if there is length mismatch among expressions
+   on the same dimension and on the same side of the equal sign.  The
+   expressions (or ARRAY_NOTATION lengths) are passed in through 2-D array
+   **LIST where X and Y indicate first and second dimension sizes of LIST,
+   respectively.  */
+
+bool
+length_mismatch_in_expr_p (location_t loc, tree **list, size_t x, size_t y)
+{
+  size_t ii, jj;
+  tree start = NULL_TREE;
+  HOST_WIDE_INT l_start, l_node;
+  for (jj = 0; jj < y; jj++)
+    {
+      start = NULL_TREE;
+      for (ii = 0; ii < x; ii++)
+	{
+	  if (!start)
+	    start = list[ii][jj];
+	  else if (TREE_CODE (start) == INTEGER_CST)
+	    {
+	      /* If start is a INTEGER, and list[ii][jj] is an integer then
+		 check if they are equal.  If they are not equal then return
+		 true.  */
+	      if (TREE_CODE (list[ii][jj]) == INTEGER_CST)
+		{
+		  l_node = int_cst_value (list[ii][jj]);
+		  l_start = int_cst_value (start);
+		  if (absu_hwi (l_start) != absu_hwi (l_node))
+		    {
+		      error_at (loc, "length mismatch in expression");
+		      return true;
+		    }
+		}
+	    }
+	  else
+	    /* We set the start node as the current node just in case it turns
+	       out to be an integer.  */
+	    start = list[ii][jj];
+	}
+    }
+  return false;
+}
+
+/* Given an FNDECL of type FUNCTION_DECL or ADDR_EXPR, return the corresponding
+   BUILT_IN_CILKPLUS_SEC_REDUCE_* being called.  If none, return
+   BUILT_IN_NONE.  */
+
+enum built_in_function
+is_cilkplus_reduce_builtin (tree fndecl)
+{
+  if (!fndecl)
+    return BUILT_IN_NONE;
+  if (TREE_CODE (fndecl) == ADDR_EXPR)
+    fndecl = TREE_OPERAND (fndecl, 0);
+
+  if (TREE_CODE (fndecl) == FUNCTION_DECL
+      && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
+    switch (DECL_FUNCTION_CODE (fndecl))
+      {
+      case BUILT_IN_CILKPLUS_SEC_REDUCE_ADD:
+      case BUILT_IN_CILKPLUS_SEC_REDUCE_MUL:
+      case BUILT_IN_CILKPLUS_SEC_REDUCE_ALL_ZERO:
+      case BUILT_IN_CILKPLUS_SEC_REDUCE_ANY_ZERO:
+      case BUILT_IN_CILKPLUS_SEC_REDUCE_MAX:
+      case BUILT_IN_CILKPLUS_SEC_REDUCE_MIN:
+      case BUILT_IN_CILKPLUS_SEC_REDUCE_MIN_IND:
+      case BUILT_IN_CILKPLUS_SEC_REDUCE_MAX_IND:
+      case BUILT_IN_CILKPLUS_SEC_REDUCE_ANY_NONZERO:
+      case BUILT_IN_CILKPLUS_SEC_REDUCE_ALL_NONZERO:
+      case BUILT_IN_CILKPLUS_SEC_REDUCE:
+      case BUILT_IN_CILKPLUS_SEC_REDUCE_MUTATING:
+	return DECL_FUNCTION_CODE (fndecl);
+      default:
+	break;
+      }
+
+  return BUILT_IN_NONE;
+}
+
+/* This function will recurse into EXPR finding any
+   ARRAY_NOTATION_EXPRs and calculate the overall rank of EXPR,
+   storing it in *RANK. LOC is the location of the original expression.
+
+   ORIG_EXPR is the original expression used to display if any rank
+   mismatch errors are found.
+
+   Upon entry, *RANK must be either 0, or the rank of a parent
+   expression that must have the same rank as the one being
+   calculated.  It is illegal to have multiple array notation with different
+   rank in the same expression (see examples below for clarification).
+
+   If there were any rank mismatches while calculating the rank, an
+   error will be issued, and FALSE will be returned.  Otherwise, TRUE
+   is returned.  
+
+   If IGNORE_BUILTIN_FN is TRUE, ignore array notation specific
+   built-in functions (__sec_reduce_*, etc).
+
+   Here are some examples of array notations and their rank:
+
+   Expression			    RANK
+   5				    0
+   X (a variable)		    0
+   *Y (a pointer)		    0
+   A[5]				    0
+   B[5][10]			    0
+   A[:]				    1 
+   B[0:10]			    1
+   C[0:10:2]			    1
+   D[5][0:10:2]			    1 (since D[5] is considered "scalar")
+   D[5][:][10]			    1 
+   E[:] + 5			    1 
+   F[:][:][:] + 5 + X		    3
+   F[:][:][:] + E[:] + 5 + X	    RANKMISMATCH-ERROR since rank (E[:]) = 1 and
+                                    rank (F[:][:][:]) = 3.  They must be equal 
+				    or have a rank of zero.
+   F[:][5][10] + E[:] * 5 + *Y      1
+
+   int func (int);
+   func (A[:])			    1
+   func (B[:][:][:][:])             4 
+   
+   int func2 (int, int)
+   func2 (A[:], B[:][:][:][:])	    RANKMISMATCH-ERROR -- Since Rank (A[:]) = 1 
+				    and Rank (B[:][:][:][:]) = 4
+
+   A[:] + func (B[:][:][:][:])	    RANKMISMATCH-ERROR
+   func2 (A[:], B[:]) + func (A)    1 
+
+ */
+
+bool
+find_rank (location_t loc, tree orig_expr, tree expr, bool ignore_builtin_fn,
+	   size_t *rank)
+{
+  tree ii_tree;
+  size_t ii = 0, current_rank = 0;
+
+  if (TREE_CODE (expr) == ARRAY_NOTATION_REF)
+    {
+      ii_tree = expr;
+      while (ii_tree)
+	{
+	  if (TREE_CODE (ii_tree) == ARRAY_NOTATION_REF)
+	    {
+	      current_rank++;
+	      ii_tree = ARRAY_NOTATION_ARRAY (ii_tree);
+	    }
+	  else if (TREE_CODE (ii_tree) == ARRAY_REF)
+	    ii_tree = TREE_OPERAND (ii_tree, 0);
+	  else if (TREE_CODE (ii_tree) == PARM_DECL
+		   || TREE_CODE (ii_tree) == VAR_DECL)
+	    break;
+	}
+      if (*rank == 0)
+	/* In this case, all the expressions this function has encountered thus
+	   far have been scalars or expressions with zero rank.  Please see
+	   header comment for examples of such expression.  */
+	*rank = current_rank;
+      else if (*rank != current_rank)
+	{
+	  /* In this case, find rank is being recursed through a set of 
+	     expression of the form A <OPERATION> B, where A and B both have
+	     array notations in them and the rank of A is not equal to rank of
+	     B.  
+	     A simple example of such case is the following: X[:] + Y[:][:] */ 
+	  *rank = current_rank;
+	  return false;
+	}
+    }
+  else if (TREE_CODE (expr) == STATEMENT_LIST)
+    {
+      tree_stmt_iterator ii_tsi;
+      for (ii_tsi = tsi_start (expr); !tsi_end_p (ii_tsi);
+	   tsi_next (&ii_tsi))
+	if (!find_rank (loc, orig_expr, *tsi_stmt_ptr (ii_tsi),
+			ignore_builtin_fn, rank))
+	  return false;
+    }
+  else
+    {
+      if (TREE_CODE (expr) == CALL_EXPR)
+	{
+	  tree func_name = CALL_EXPR_FN (expr);
+	  tree prev_arg = NULL_TREE, arg;
+	  call_expr_arg_iterator iter;
+	  size_t prev_rank = 0;
+	  if (TREE_CODE (func_name) == ADDR_EXPR)
+	    if (!ignore_builtin_fn)
+	      if (is_cilkplus_reduce_builtin (func_name))
+		/* If it is a built-in function, then we know it returns a 
+		   scalar.  */
+		return true;
+	  FOR_EACH_CALL_EXPR_ARG (arg, iter, expr)
+	    {
+	      if (!find_rank (loc, orig_expr, arg, ignore_builtin_fn, rank))
+		{
+		  if (prev_arg && EXPR_HAS_LOCATION (prev_arg)
+		      && prev_rank != *rank)
+		    error_at (EXPR_LOCATION (prev_arg),
+			      "rank mismatch between %qE and %qE", prev_arg,
+			      arg);
+		  else if (prev_arg && prev_rank != *rank)
+		    /* Here the original expression is printed as a "heads-up"
+		       to the programmer.  This is because since there is no 
+		       location information for the offending argument, the 
+		       error could be in some internally generated code that is
+		       not visible for the programmer.  Thus, the correct fix
+		       may lie in the original expression.  */
+		    error_at (loc, "rank mismatch in expression %qE",
+			      orig_expr);
+		  return false;
+		}
+	      prev_arg = arg;
+	      prev_rank = *rank;
+	    }	
+	}
+      else
+	{
+	  tree prev_arg = NULL_TREE;
+	  for (ii = 0; ii < TREE_CODE_LENGTH (TREE_CODE (expr)); ii++)
+	    {
+	      if (TREE_OPERAND (expr, ii)
+		  && !find_rank (loc, orig_expr, TREE_OPERAND (expr, ii),
+				 ignore_builtin_fn, rank))
+		{
+		  if (prev_arg && EXPR_HAS_LOCATION (prev_arg))
+		    error_at (EXPR_LOCATION (prev_arg),
+			      "rank mismatch between %qE and %qE", prev_arg,
+			      TREE_OPERAND (expr, ii));
+		  return false;
+		}
+	      prev_arg = TREE_OPERAND (expr, ii);
+	    }
+	}
+    }
+  return true;
+}
+
+/* Extracts all array notations in NODE and stores them in ARRAY_LIST.  If 
+   IGNORE_BUILTIN_FN is set, then array notations inside array notation
+   specific built-in functions are ignored.  The NODE can be constants,
+   VAR_DECL, PARM_DECLS, STATEMENT_LISTS or full expressions.   */
+
+void
+extract_array_notation_exprs (tree node, bool ignore_builtin_fn,
+			      vec<tree, va_gc> **array_list)
+{
+  size_t ii = 0;  
+  if (TREE_CODE (node) == ARRAY_NOTATION_REF)
+    {
+      vec_safe_push (*array_list, node);
+      return;
+    }
+  else if (TREE_CODE (node) == STATEMENT_LIST)
+    {
+      tree_stmt_iterator ii_tsi;
+      for (ii_tsi = tsi_start (node); !tsi_end_p (ii_tsi); tsi_next (&ii_tsi))
+	extract_array_notation_exprs (*tsi_stmt_ptr (ii_tsi),
+				      ignore_builtin_fn, array_list);
+    }
+  else if (TREE_CODE (node) == CALL_EXPR)
+    {
+      tree arg;
+      call_expr_arg_iterator iter;
+      if (is_cilkplus_reduce_builtin (CALL_EXPR_FN (node)))
+	{
+	  if (ignore_builtin_fn)
+	    return;
+	  else
+	    {
+	      vec_safe_push (*array_list, node);
+	      return;
+	    }
+	}
+      if (is_sec_implicit_index_fn (CALL_EXPR_FN (node)))
+	{
+	  vec_safe_push (*array_list, node);
+	  return;
+	}
+      FOR_EACH_CALL_EXPR_ARG (arg, iter, node)
+	extract_array_notation_exprs (arg, ignore_builtin_fn, array_list);
+    } 
+  else 
+    for (ii = 0; ii < TREE_CODE_LENGTH (TREE_CODE (node)); ii++) 
+      if (TREE_OPERAND (node, ii))
+	extract_array_notation_exprs (TREE_OPERAND (node, ii),
+				      ignore_builtin_fn, array_list);
+  return;
+}
+
+/* LIST contains all the array notations found in *ORIG and ARRAY_OPERAND
+   contains the expanded ARRAY_REF.  E.g., if LIST[<some_index>] contains
+   an array_notation expression, then ARRAY_OPERAND[<some_index>] contains its
+   expansion.  If *ORIG matches LIST[<some_index>] then *ORIG is set to
+   ARRAY_OPERAND[<some_index>].  This function recursively steps through
+   all the sub-trees of *ORIG, if it is larger than a single
+   ARRAY_NOTATION_REF.  */
+
+void
+replace_array_notations (tree *orig, bool ignore_builtin_fn,
+			 vec<tree, va_gc> *list,
+			 vec<tree, va_gc> *array_operand)
+{
+  size_t ii = 0;
+  extern tree build_c_cast (location_t, tree, tree);
+  tree node = NULL_TREE, node_replacement = NULL_TREE;
+  
+  if (vec_safe_length (list) == 0)
+    return;
+
+  if (TREE_CODE (*orig) == ARRAY_NOTATION_REF)
+    {
+      for (ii = 0; vec_safe_iterate (list, ii, &node); ii++) 
+	if (*orig == node)
+	  {
+	    node_replacement = (*array_operand)[ii];
+	    *orig = node_replacement;
+	  }
+    }
+  else if (TREE_CODE (*orig) == STATEMENT_LIST)
+    {
+      tree_stmt_iterator ii_tsi;
+      for (ii_tsi = tsi_start (*orig); !tsi_end_p (ii_tsi); tsi_next (&ii_tsi))
+	replace_array_notations (tsi_stmt_ptr (ii_tsi), ignore_builtin_fn, list,
+				 array_operand);
+    }
+  else if (TREE_CODE (*orig) == CALL_EXPR)
+    {
+      tree arg;
+      call_expr_arg_iterator iter;
+      if (is_cilkplus_reduce_builtin (CALL_EXPR_FN (*orig)))
+	{
+	  if (!ignore_builtin_fn)
+	    {
+	      for (ii = 0; vec_safe_iterate (list, ii, &node); ii++) 
+		if (*orig == node)
+		  {
+		    node_replacement = (*array_operand)[ii];
+		    *orig = node_replacement;
+		  }
+	    }
+	  return;
+	}
+      if (is_sec_implicit_index_fn (CALL_EXPR_FN (*orig)))
+	{
+	  for (ii = 0; vec_safe_iterate (list, ii, &node); ii++)
+	    if (*orig == node)
+	      {
+		node_replacement = (*array_operand)[ii];
+		*orig = build_c_cast (EXPR_LOCATION (*orig),
+				      TREE_TYPE (*orig), node_replacement);
+	      }
+	  return;
+	}
+      ii = 0;
+      FOR_EACH_CALL_EXPR_ARG (arg, iter, *orig)
+	{
+	  replace_array_notations (&arg, ignore_builtin_fn, list,
+				   array_operand);
+	  CALL_EXPR_ARG (*orig, ii) = arg;
+	  ii++;
+	}     
+    }
+  else
+    {
+      for (ii = 0; ii < (size_t) TREE_CODE_LENGTH (TREE_CODE (*orig)); ii++) 
+	if (TREE_OPERAND (*orig, ii))
+	  replace_array_notations (&TREE_OPERAND (*orig, ii), ignore_builtin_fn,
+				   list, array_operand);
+    }
+  return;
+}
+
+/* Callback for walk_tree.  Find all the scalar expressions in *TP and push 
+   them in DATA struct, typecasted to (void *).  If *WALK_SUBTREES is set to 0 
+   then do not go into the *TP's subtrees.  Since this function steps through 
+   all the subtrees, *TP and TP can be NULL_TREE and NULL, respectively.  The 
+   function returns NULL_TREE unconditionally.  */
+
+tree
+find_inv_trees (tree *tp, int *walk_subtrees, void *data)
+{
+  struct inv_list *i_list = (struct inv_list *) data;
+  unsigned int ii = 0;
+
+  if (!tp || !*tp)
+    return NULL_TREE;
+  if (TREE_CONSTANT (*tp))
+    return NULL_TREE; /* No need to save constant to a variable.  */
+  if (TREE_CODE (*tp) != COMPOUND_EXPR && !contains_array_notation_expr (*tp))
+    {
+      vec_safe_push (i_list->list_values, *tp);
+      *walk_subtrees = 0;
+    }
+  else if (TREE_CODE (*tp) == ARRAY_NOTATION_REF
+	   || TREE_CODE (*tp) == ARRAY_REF
+	   || TREE_CODE (*tp) == CALL_EXPR)
+    /* No need to step through the internals of array notation.  */
+    *walk_subtrees = 0;
+  else
+    {
+      *walk_subtrees = 1;
+
+      /* This function is used by C and C++ front-ends.  In C++, additional
+	 tree codes such as TARGET_EXPR must be eliminated.  These codes are
+	 passed into additional_tcodes and are walked through and checked.  */
+      for (ii = 0; ii < vec_safe_length (i_list->additional_tcodes); ii++)
+	if (TREE_CODE (*tp) == (enum rid)(*(i_list->additional_tcodes))[ii])
+	  *walk_subtrees = 0;
+    }
+  return NULL_TREE;
+}
+
+/* Callback for walk_tree.  Replace all the scalar expressions in *TP with the 
+   appropriate replacement stored in the struct *DATA (typecasted to void*).  
+   The subtrees are not touched if *WALK_SUBTREES is set to zero.  */
+
+tree
+replace_inv_trees (tree *tp, int *walk_subtrees, void *data)
+{
+  size_t ii = 0;
+  tree t, r;
+  struct inv_list *i_list = (struct inv_list *) data;
+
+  if (vec_safe_length (i_list->list_values))
+    {
+      for (ii = 0; vec_safe_iterate (i_list->list_values, ii, &t); ii++)
+	if (simple_cst_equal (*tp, t) == 1)
+	  {
+	    vec_safe_iterate (i_list->replacement, ii, &r);
+	    gcc_assert (r != NULL_TREE);
+	    *tp = r;
+	    *walk_subtrees = 0;
+	  }
+    }
+  else
+    *walk_subtrees = 0;
+  return NULL_TREE;
+}
+
+/* Returns true if EXPR or any of its subtrees contain ARRAY_NOTATION_EXPR 
+   node.  */
+
+bool
+contains_array_notation_expr (tree expr)
+{
+  vec<tree, va_gc> *array_list = NULL;
+
+  if (!expr)
+    return false;
+  if (TREE_CODE (expr) == FUNCTION_DECL)
+    if (is_cilkplus_reduce_builtin (expr))
+      return true;
+  
+  extract_array_notation_exprs (expr, false, &array_list);
+  if (vec_safe_length (array_list) == 0)
+    return false;
+  else
+    return true;
+}
+
+/* This function will check if OP is a CALL_EXPR that is a built-in array 
+   notation function.  If so, then we will return its type to be the type of
+   the array notation inside.  */
+
+tree
+find_correct_array_notation_type (tree op)
+{
+  tree fn_arg, return_type = NULL_TREE;
+
+  if (op)
+    {
+      return_type = TREE_TYPE (op); /* This is the default case.  */
+      if (TREE_CODE (op) == CALL_EXPR) 
+	if (is_cilkplus_reduce_builtin (CALL_EXPR_FN (op))) 
+	  { 
+	    fn_arg = CALL_EXPR_ARG (op, 0); 
+	    if (fn_arg) 
+	      return_type = TREE_TYPE (fn_arg); 
+	  }
+    } 
+  return return_type;
+}