Cilk Plus Array Notation for C++

Hi Jason,
	Please see below for my responses to your questions. I am also attaching a fixed patch (diffed with trunk's head) and Changelog entries.

Thanks,

Balaji V. Iyer.

> -----Original Message-----
> From: Jason Merrill [mailto:jason@redhat.com]
> Sent: Saturday, June 22, 2013 12:20 PM
> To: Iyer, Balaji V; Richard Henderson
> Cc: Aldy Hernandez; gcc-patches@gcc.gnu.org
> Subject: Re: [PATCH] Cilk Plus Array Notation for C++
> 
> Hmm, seems like I should have sent this yesterday even though I hadn't made it
> through the whole patch.  But I suppose it doesn't hurt to fix it after checkin.
> 
> On 06/20/2013 07:39 PM, Iyer, Balaji V wrote:
> > diff --git a/gcc/c-family/ChangeLog b/gcc/c-family/ChangeLog old mode
> > 100644 new mode 100755 index a0f195b..fb70520 Binary files
> > a/gcc/c-family/ChangeLog and b/gcc/c-family/ChangeLog differ
> 
> Why are you marking lots of files as executable?

I think the reason why this is happening is that I use emacs on my windows machine and it is doing some conversion. Is there a way to tell emacs not to do this?

> 
> In the future please filter out ChangeLogs entirely from diffs.  I use
> 
>    filterdiff -x '*/ChangeLog' | sed -e '/^diff.*ChangeLog/{N;d}'
> 
> for my own patches.

OK. I generally don't include the changelog entries, but the last one was a mistake. I will make sure it doesn't happen again.

> 
> > +      if (flag_enable_cilkplus
> > +         && (contains_array_notation_expr (expr)
> > +             || contains_array_notation_expr (fn)))
> 
> Looking at "fn" here doesn't make sense; it's only used for diagnostics.

Fixed!

> 
> > +       /* If we are using array notations, we fix them up at a later stage
> > +          and we will do these checks then.  */
> > +       ;
> 
> And please don't mess with the overload resolution code directly to handle this
> case differently.

Fixed! Removed the code. It was an artifact of a previous implementation. Things works fine even without it.

> 
> This seems to be a general problem with the patch; you are special-casing array
> notation all through the compiler rather than making it work with the existing
> mechanisms.
> 
> In this case, an ARRAY_NOTATION_REF should have a type that participates
> normally with conversions.

Yep, it is done that way.

> 
> >> +      /* If the function call is builtin array notation function then no need
> >> +        to do any type conversion.  */
> 
> And here, instead of changing build_over_call, you can use the existing
> magic_varargs_p mechanism.

Fixed!

> 
> > +/* This function parses Cilk Plus array notations.  The starting index is
> > +   passed in INIT_INDEX and the array name is passed in ARRAY_VALUE.  If the
> > +   INIT_INDEX is NULL, then we have special case were the entire
> > +array is
> 
> "where"

Fixed!

> 
> > +   accessed (e.g. A[:]).  The return value of this function is a tree node
> > +   called VALUE_TREE of type ARRAY_NOTATION_REF.  If some error
> > + occurred it
> 
> Drop "called VALUE_TREE"; the function comment shouldn't talk about local
> variables.

Fixed!

> 
> > +  cp_token *token = NULL;
> > +  tree start_index = NULL_TREE, length_index = NULL_TREE, stride =
> > + NULL_TREE;  tree value_tree, type, array_type, array_type_domain;
> > + double_int x;  bool saved_colon_corrects_to_scope_p =
> > + parser->colon_corrects_to_scope_p;
> 
> Now that the compiler is built as C++, variables should be defined at the point of
> first use, rather than at the top of the function.
> 

Fixed!

> > +         if (TREE_CODE (array_type) == RECORD_TYPE
> > +             || TREE_CODE (array_type) == POINTER_TYPE)
> > +           {
> > +             error_at (loc, "start-index and length fields necessary for "
> > +                       "using array notations in pointers or
> > + records");
> 
> I think this should handle all non-array types, rather than just pointers and
> classes.
> 
> Let's say "notation" rather than "notations" in all diagnostics.

I think I have fixed them all.

> 
> > +                     error_at (loc, "array notations cannot be used with"
> > +                               " function pointer arrays");
> 
> I don't see this restriction in any of the documentation.  What's the rationale?
> 

Sorry, that was a mistake on my part. I have fixed it.

> > +             error_at (loc, "start-index and length fields necessary for "
> > +                       "using array notations in dimensionless
> > + arrays");
> 
> Let's say "...with array of unknown bound"

Fixed!

> 
> > +         start_index = fold_build1 (CONVERT_EXPR, ptrdiff_type_node,
> > +                                    start_index);
> 
> Use cp_fold_convert rather than fold_build1.

Fixed!

> 
> > +         x = TREE_INT_CST (TYPE_MAXVAL (array_type_domain));
> > +         x.low++;
> > +         length_index = double_int_to_tree (integer_type_node, x);
> 
> This assumes a constant length array.  Use size_binop instead.

Fixed!

> 
> > +         stride = build_int_cst (integer_type_node, 1);
> > +         stride = fold_build1 (CONVERT_EXPR, ptrdiff_type_node,
> > + stride);
> 
> Build the constant in ptrdiff_type_node rather than build it in integer_type_node
> and then convert.

Fixed!
> 
> > +             /* Disable correcting single colon correcting to scope.  */
> > +             parser->colon_corrects_to_scope_p = false;
> > +             stride = cp_parser_expression (parser, false, NULL);
> > +             parser->colon_corrects_to_scope_p =
> > +               saved_colon_corrects_to_scope_p;
> 
> Why do you do this for the stride?  We've already seen both array-notation
> colons at this point.
> 
I removed it.

> > +  /* We fold all 3 of the values to make things easier when we transform
> > +     them later.  */
> 
> Why is this better than folding at transformation time?

Fixed! We are already folding before transformation.

> 
> > +    /* If we are here, then we have something like this:
> > +       ARRAY[:]
> > +    */
> 
> The */ should go at the end of the last line in all comments.

Fixed!

> 
> > -  if (for_offsetof)
> > -    index = cp_parser_constant_expression (parser, false, NULL);
> ...
> >    else
> >      {
> > -      if (cp_lexer_next_token_is (parser->lexer, CPP_OPEN_BRACE))
> ...
> > +      if (for_offsetof)
> > +       index = cp_parser_constant_expression (parser, false, NULL);
> > +      else
> 
> Please try to avoid re-indenting code when possible, to make history annotation
> simpler.
> 

OK. 

> Actually, to reduce the amount of changes to non-AN code, let's put the AN case
> third, after the offset and {} cases, so you get something like
> 
> else if (flag_enable_cilkplus)
>    {
>      tree an = cp_parser_array_notation (loc, parser, &index,
> 				        postfix_expression);
>      if (an)
>        return an;
>      /* Otherwise, cp_parser_array_notation set 'index'. */
>    }
> else
>    index = cp_parser_expression (parser, /*cast_p=*/false, NULL);
> 
> this way the change is just a few added lines, and everything else is in
> cp_parser_array_notation.

If I do it this way, then I don't think I will be able to handle a normal array reference when cilk plus is enabled. One thing I could do is to assume that people won't use array notations in braced list. I had it like this a while back but I made the change to make sure I have covered more cases. Please let me know if that is OK and I will fix it.

> 
> > +  if (flag_enable_cilkplus && contains_array_notation_expr
> (compound_stmt))
> > +    compound_stmt = expand_array_notation_exprs (compound_stmt);
> ...
> > +  /* Transform all array notations to the equivalent array refs and
> > + loop.  */  if (flag_enable_cilkplus && contains_array_notation_expr (body))
> > +    body = expand_array_notation_exprs (body);
> ...
> > +  /* Expand all array notation expressions here.  */  if
> > + (flag_enable_cilkplus && current_function_decl
> > +      && contains_array_notation_expr (DECL_SAVED_TREE
> (current_function_decl)))
> > +    DECL_SAVED_TREE (current_function_decl) =
> > +      expand_array_notation_exprs (DECL_SAVED_TREE
> > + (current_function_decl));
> 
> Let's do the transformation in cp_genericize rather than in these places.
> 
> Perhaps moving the expansion to gimplification time would also help with
> sharing code between C and C++, since you don't have to worry about templates
> at that point.

I moved the array notation expansion to cp_generize_tree function. I have also removed the expansion in pt.c

> 
> > +           if (flag_enable_cilkplus
> > +               && contains_array_notation_expr (condition))
> > +             {
> > +               error_at (EXPR_LOCATION (condition),
> > +                         "array notations cannot be used as a condition for "
> > +                         "switch statement");
> > +               statement = error_mark_node;
> > +             }
> [etc]
> 
> I'd prefer to give diagnostics about uses that don't make sense at
> transformation time, rather than parsing time.

Fixed!

> 
> > +             if (flag_enable_cilkplus
> > +                 && cp_lexer_next_token_is (parser->lexer, CPP_COLON))
> > +               {
> > +                 bounds = error_mark_node;
> > +                 error_at (cp_lexer_peek_token (parser->lexer)->location,
> > +                           "array notations cannot be used in declaration");
> > +                 cp_lexer_consume_token (parser->lexer);
> > +               }
> 
> I'm concerned about this causing trouble with tentative parsing, and I think that
> people are unlikely to try to write a declaration using array notation, so let's
> leave out the changes to cp_parser_direct_declarator.

Ok. I have removed it.

> 
> > @@ -15758,6 +15772,9 @@ type_unification_real (tree tparms,
> > +      if (flag_enable_cilkplus && TREE_CODE (arg) == ARRAY_NOTATION_REF)
> > +       return 1;
> 
> Again, an ARRAY_NOTATION_REF should have a type like any other expression;
> we don't need to prevent it from participating in type deduction.

Yep. This is fixed also.

> 
> > @@ -8073,6 +8089,7 @@ cxx_eval_constant_expression (const
> > constexpr_call *call, tree t,
> > +    case ARRAY_NOTATION_REF:
> > @@ -8884,6 +8901,7 @@ potential_constant_expression_1 (tree t, bool
> > want_rval, tsubst_flags_t flags)
> > +    case ARRAY_NOTATION_REF:
> 
> cxx_eval_array_reference doesn't know how to deal with
> ARRAY_NOTATION_REF, so let's not add it to cxx_eval_constant_expression,
> and return false for it from potential_constant_expression_1.

Fixed as you suggested.

> 
> > +  if (flag_enable_cilkplus
> > +      && is_cilkplus_reduce_builtin (fndecl) != BUILT_IN_NONE)
> > +    nargs = (*params)->length ();
> > +  else
> > +    nargs = convert_arguments (parm_types, params, fndecl,
> LOOKUP_NORMAL,
> > +                              complain);
> 
> Another change that should be replaced by addition to magic_varargs_p, though
> it looks like convert_arguments needs to be updated to use magic_varargs_p
> rather than checking specifically for BUILT_IN_CONSTANT_P.

I looked into this. But, magic_varargs_p is static to call.c. Should I make it non-static? After making it non-static I was planning to do something like this:

if (magic_varargs_p (fndecl)
  Nargs = (*params)->length ();
else
   nargs = convert_arguments (...)

Is that OK with you?

> 
> > +  for (size_t ii = 0; ii < size; ii++)
> > +    for (size_t jj = 0; jj < rank; jj++)
> > +      {
> > +       (*node)[ii].safe_push (init);
> > +       array_exprs[ii].safe_push (NULL_TREE);
> > +      }
> 
> Why not use safe_grow_cleared for the sub-vecs as well?

Fixed!

> 
> > +      while (ii_tree)
> > +       if (TREE_CODE (ii_tree) == ARRAY_NOTATION_REF)
> 
> Wrap the sub-statement of the 'while' in { }.
> 

Fixed!

> > +       else if (TREE_CODE (ii_tree) == VAR_DECL
> > +                || TREE_CODE (ii_tree) == CALL_EXPR
> > +                || TREE_CODE (ii_tree) == PARM_DECL)
> > +         break;
> > +       else
> > +         gcc_unreachable ();
> e
> There are lots of other ways to gt an expression of array type, why are only
> these allowed?
>

Sorry, it was a mistake as well. The main point of that loop was to allow array refs intermingling with array notations.

> > +      if (TREE_CODE ((*list)[ii]) == ARRAY_NOTATION_REF)
> > +       for (size_t jj = 0; jj < rank; jj++)
> > +         if (TREE_CODE (array_exprs[ii][jj]) == ARRAY_NOTATION_REF)
> 
> How could the array_exprs element be anything other than an
> ARRAY_NOTATION_REF?  That's all you put in when you were building it.
> 

Fixed!

> By the way, why are you breaking out the elements of the
> ARRAY_NOTATION_REF into a cilkplus_an_parts rather than using the _REF
> directly?
> 

I use the different parts of array notations for error checking and to create the outer for-loop. Also, to create the ARRAY_REF I need the induction variable.

> > +    if (TREE_CODE ((*list)[ii]) == CALL_EXPR
> > +       && TREE_CODE (CALL_EXPR_FN ((*list)[ii])) == ADDR_EXPR
> > +       && is_sec_implicit_index_fn (CALL_EXPR_FN ((*list)[ii])))
> 
> Why check for ADDR_EXPR here?  Better for is_sec_implicit_index_fn to return
> false if its argument isn't what's desired.

Fixed!

> 
> > +       if (idx < (int) rank && idx >= 0)
> > +         vec_safe_push (array_operand, an_loop_info[idx].var);
> > +       else if (idx == -1)
> > +         /* In this case, the returning function would have emitted an
> > +            error thus it is not necessary to do so again.  */
> > +         return NULL;
> 
> Reorder these cases so you don't need to check idx >= 0.

Fixed!

> 
> > +   same dimension and one the same side of the equal sign.  The Array
> > + notation
> 
> "on the same side"

Fixed! (Sorry for the stupid mistake).

> 
> > +                 l_node = int_cst_value (list[ii][jj].length);
> > +                 l_length = int_cst_value (length);
> > +                 if (absu_hwi (l_length) != absu_hwi (l_node))
> 
> Use tree_int_cst_equal instead.

Fixed!

> 
> > +  for (jj = 0; jj < y; jj++)
> > +    {
> > +      length = NULL_TREE;
> > +      for (ii = 0; ii < x; ii++)
> 
> Why did you switch the outer/inner iteration variables for this loop compared to
> others?

The y axis represents the rank and  x-axis represents the expressions in the polynomial. So, for-each rank I go through all the expressions  to make sure the lengths are the same.

> 
> > +           /* We set the length node as the current node just in case it turns
> > +              out to be an integer.  */
> > +           length = list[ii][jj].length;
> 
> How could it "turn out" to be an integer?  We just checked, and it isn't one.
> 

We have not checked list[ii][jj].length is an integer. I agree that I should clarify the comment. I have fixed that.

> > +      var = build_decl (loc, VAR_DECL, NULL_TREE, integer_type_node);
> > +      finish_expr_stmt (build_x_modify_expr (loc, var, NOP_EXPR,
> > + *value, cry));
> 
> This should use get_temp_regvar.
> 
> We shouldn't need to pass tsubst_flags_t around, since we will never be
> expanding array notation in SFINAE context.

Fixed! By the way, what is SFINAE?

> 
> > +           /* If stride and start are of same type and the induction var
> > +              is not, convert induction variable to stride's type.  */
> > +           if (TREE_TYPE (start) == TREE_TYPE (stride)
> > +               && TREE_TYPE (stride) != TREE_TYPE (var))
> 
> This seems impossible, since 'var' is created to have the same type as 'start'.

As you suggested further in the email, I have made var of type ptrdiff_type, so I think I should keep this.

> 
> > +               /* If we reach here, then the stride and start are of
> > +                  different types, and so it doesn't really matter what
> > +                  the induction variable type is, convert everything to
> > +                  integer.  The reason why we pick an integer
> > +                  instead of something like size_t is because the stride
> > +                  and length can be + or -.  */
> 
> Maybe the induction variable should always be ptrdiff_type_node.

Yep. Fixed!

> 
> Jason

COPY- PASTING your  last responde from  thread (http://gcc.gnu.org/ml/gcc-patches/2013-06/msg01385.html) below:

> A few more comments:
> 
> > +         if (processing_template_decl || !TREE_TYPE (t))
> > +           new_var = build_min_nt_loc (EXPR_LOCATION (t), VAR_DECL,
> NULL_TREE,
> > +                                       NULL_TREE);
> 
> Again, we shouldn't be trying to expand array notation during template parsing.

Fixed!

> 
> And replace_invariant_exprs should also use get_temp_regvar, as should most
> of the places you create temporary variables.

Fixed!

> 
> > +      /* We need to do this because we are "faking" the builtin function types,
> > +        so the compiler does a bunch of typecasts and this will get rid of
> > +        all that!  */
> 
> Again, magic_varargs_p can avoid any gratuitous type conversions.
> 

Please see my comment above about magic_varargs_p.

> > +    case BUILT_IN_CILKPLUS_SEC_REDUCE_ALL_ZERO:
> > +    case BUILT_IN_CILKPLUS_SEC_REDUCE_ANY_ZERO:
> > +    case BUILT_IN_CILKPLUS_SEC_REDUCE_ANY_NONZERO:
> > +    case BUILT_IN_CILKPLUS_SEC_REDUCE_ALL_NONZERO:
> > +      new_var_type = integer_type_node;
> 
> I would expect boolean_type_node.

Yep. Fixed!
> 
> > +      an_loop_info[ii].var = build_decl (location, VAR_DECL, NULL_TREE,
> > +                                 TREE_TYPE (an_info[0][ii].start));
> 
> Here you can use create_temporary_var.
> 

Fixed!

> > +      an_loop_info[ii].ind_init = build_x_modify_expr
> > +       (location, an_loop_info[ii].var, NOP_EXPR,
> > +        build_zero_cst (TREE_TYPE (an_loop_info[ii].var)),
> > +        tf_warning_or_error);
> 
> Here and in other calls to build_x_modify_expr for initialization, use INIT_EXPR
> rather than NOP_EXPR.
> 
Fixed!

> > +       *new_var = create_tmp_var (new_var_type, NULL);
> 
> create_tmp_var is part of gimplification; it might be appropriate to use it when
> you move lowering to happen later in the compilation, but it seems wrong in the
> current code.

Removed and replaced it with create_temporary_var.

> 
> > +      code = (an_type == BUILT_IN_CILKPLUS_SEC_REDUCE_ANY_ZERO) ?
> EQ_EXPR
> > +       : NE_EXPR;
> 
> A ?: expression split across multiple lines should have parens around it.
> 

Fixed!

> > +  /* If both are scalar, then the only reason why we will get this far is if
> > +     there is some array notations inside it and was using a builtin array
> > +     notation functions.  If so, we have already broken those guys up and now
> > +     a simple build_x_modify_expr would do.  */  if (lhs_rank == 0 &&
> > + rhs_rank == 0)
> > +    {
> > +      if (found_builtin_fn)
> > +       {
> > +         new_modify_expr = build_x_modify_expr (location, lhs,
> > +                                                modifycode, rhs, complain);
> > +         finish_expr_stmt (new_modify_expr);
> > +         pop_stmt_list (an_init);
> > +         return an_init;
> > +       }
> > +      else
> > +       {
> > +         pop_stmt_list (an_init);
> > +         return NULL_TREE;
> > +       }
> > +    }
> 
> The comment makes it sound like the else should be gcc_unreachable.
> 

Yes, I added gcc_unreachable there.

> > +      if (location == UNKNOWN_LOCATION && EXPR_HAS_LOCATION (rhs))
> > +       location = EXPR_LOCATION (rhs);
> 
> This is redundant with code a few lines above.

Fixed!

> 
> > +         append_to_statement_list_force (lhs_an_loop_info[ii].ind_init,
> > +                                         &init_list);
> 
> Why do you need _force?
> 

No reason. Just wanted to make sure it surely gets in. I have removed it.

> Jason
gcc/ChangeLog
2013-06-24  Balaji V. Iyer  <balaji.v.iyer@intel.com>

        * builtins.def: Fixed the function type of CILKPLUS_BUILTIN.

gcc/c/ChangeLog
2013-06-24  Balaji V. Iyer  <balaji.v.iyer@intel.com>

        * c-parser.c (c_parser_array_notation): Removed rejection of array
        notations in an array of function pointers.

gcc/c-family/ChangeLog
2013-06-24  Balaji V. Iyer  <balaji.v.iyer@intel.com>

        * array-notation-common.c (length_mismatch_in_expr_p): Collapsed two
        if-statements and compared the trees directly using tree_int_cst_equal.
        (find_rank): Checked for array notations in function name to handle
        array notations in function pointers.
        (extract_array_notation_exprs): Likewise.
        (cilkplus_extract_an_triplets): Removed restriction of array notations
        having just VAR, PARM DECL or CALL exprs.
        (replace_array_notations): Likewise.
        (cilkplus_extract_an_triplets): Replaced safe_push with
        safe_grow_cleared.  Also removed an unnecessary check to see if the
        node is of type ARRAY_NOTATION_REF.
        (fix_sec_implicit_args): Removed an unnecessary check for ADDR_EXPR.
        Also switched two if-statements to remove an unnecessary comparison.

gcc/cp/ChangeLog
2013-06-24  Balaji V. Iyer  <balaji.v.iyer@intel.com>

        * parser.c (cp_parser_array_notation): Removed rejection array notation
        of type function pointers.  Used cp_fold_convert instead of fold_build1.
        Moved variable that saves colon corrects variable into the if-statement.
        (cp_parser_compound_statement): Removed expansion of array notations.
        (cp_parser_ctor_initializer_opt_and_function_body): Likewise.
        (cp_parser_function_definition_after_declarator): Likewise.
        (cp_parser_selection_statement): Removed error reporting.
        (cp_parser_iteration_statement): Likewise.
        (cp_parser_direct_declarator): Removed error checking/reporting if
        array notations are used in the declarator.
        * pt.c (instantiate_decl): Likewise.
        (type_unification_real): Removed a check for ARRAY_NOTATION_REF.
        (cxx_eval_constant_expression): Removed ARRAY_NOTATION_REF case.
        (potential_constant_expression_1): Returned false for ARRAY_NOTATION_REF
        case.
        * cp-gimplify.c (cp_genericize): Added expansion of array notation
        expressions here.
        * cp-array-notation.c (cp_length_mismatch_in_expr_p): Combined two
        if statements into one and compared integers using tree_int_cst_equal.
        (make_triplet_val_inv): Removed loc and cry parameters.  Also, replaced
        build_decls with get_temp_regvar.
        (replace_invariant_var): Replaced build_decl and build_min_nt_loc with
        get_temp_regvar.
        (expand_an_in_modify_expr): Ditto. Replaced body of redundant else with
        gcc_unreachable.  Removed few unwanted checks. Made induction variable
        type as ptrdiff_type.  Removed loc and complain arguments passed into
        make_triplet_val_inv.  Replaced all modify expression's code from NOP
        EXPR to INIT EXPR.  Replaced all forceful appending into stmt. list
        with the non-forceful one.
        (expand_reduce_builtin): All changes mentioned in above function
        expand_an_in_modify_expr.  Made the new variable type of
        SEC_REDUCE_ANY/ALL_{NON}ZERO intrinsic functions as bool.
        (expand_array_notation_exprs): Removed SWITCH_EXPR case.  Moved all
        the error reporting from parser to this function.
        (cilkplus_an_triplet_types_ok_p): Removed rejection of array notation
        in function pointers.
        * call.c (convert_like_real): Removed a check for array notation
        expression in a function.
        (build_over_call): Likewise.
        (magic_varargs_p): Added a check for builtin array notation function.

Cilk Plus Array Notation for C++

Commit Message

Comments

Patch