[PATCH 1/2] PR gcc/98350:Add a param to control the length of the chain with FMA in reassoc pass

[Cui, Lili]

> ISTR there were no sufficient comments in the code explaining why
> rewrite_expr_tree_parallel_for_fma is better by design.  In fact ...
> 
> >
> > >
> > > >                   if (!reassoc_insert_powi_p
> > > > -                     && ops.length () > 3
> > > > +                     && len > 3
> > > > +                     && (!keep_fma_chain
> > > > +                         || (keep_fma_chain
> > > > +                             && len >
> > > > + param_reassoc_max_chain_length_with_fma))
> > >
> > > in the case len < param_reassoc_max_chain_length_with_fma we have
> > > the chain re-sorted but fall through to non-parallel rewrite.  I
> > > wonder if we do not want to instead adjust the reassociation width?
> > > I'd say it depends on the number of mult cases in the chain (sth the re-
> sorting could have computed).
> > > Why do we have two completely independent --params here?  Can you
> > > give an example --param value combination that makes "sense" and
> > > show how it is beneficial?
> >
> > For this small case https://godbolt.org/z/Pxczrre8P a * b + c * d + e
> > * f  + j
> >
> > GCC trunk: ops_num = 4, targetm.sched.reassociation_width is 4 (scalar fp
> cost is 4). Calculated: Width = 2. we can get 2 FMAs.
> > ----------------------------------
> >   _1 = a_6(D) * b_7(D);
> >   _2 = c_8(D) * d_9(D);
> >   _5 = _1 + _2;
> >   _4 = e_10(D) * f_11(D);
> >   _3 = _4 + j_12(D);
> >   _13 = _3 + _5;
> > --------------------------------------------------------
> >   _2 = c_8(D) * d_9(D);
> >   _5 = .FMA (a_6(D), b_7(D), _2);
> >   _3 = .FMA (e_10(D), f_11(D), j_12(D));
> >   _13 = _3 + _5;
> > --------------------------------------------------------
> > New patch: If just rearrange ops and fall through to parallel rewrite to
> break the chain with width = 2.
> >
> > ---------------------------------------------------------
> >   _1 = a_6(D) * b_7(D);
> >   _2 = j + _1;          -----> put j at the first.
> >   _3 = c_8(D) * d_9(D);
> >   _4 = e_10(D) * f_11(D);
> >   _5 = _3 + _4;       -----> break chain with width = 2. we lost a FMA here.
> >   _13 = _2 + 5;
> >
> > -------------------------------------------------------
> >   _3 = c_8(D) * d_9(D);
> >   _2 = .FMA (a_6(D), b_7(D), j);
> >   _5 = .FMA (e_10(D), f_11(D), _3);
> >   _13 = _2 + _5;
> > --------------------------------------------------------
> > Sometimes break chain will lose FMA( break chain needs put two
> > mult-ops together, which will lose one FMA ), we can only get 2 FMAs
> > here, if we want to get 3 FMAs, we need to keep the chain and not
> > break it. So I added a param to control chain length
> > "param_reassoc_max_chain_length_with_fma = 4" (For the small case in
> > Bugzilla 98350, we need to keep the chain to generate 6 FMAs.)
> > -------------------------------------------------------
> >   _1 = a_6(D) * b_7(D);
> >   _2 = c_8(D) * d_9(D);
> >   _4 = e_10(D) * f_11(D);
> >   _15 = _4 + j_12(D);
> >   _16 = _15 + _2;
> >   _13 = _16 + _1;
> > -------------------------------------------------------
> >   _15 = .FMA (e_10(D), f_11(D), j_12(D));
> >   _16 = .FMA (c_8(D), d_9(D), _15);
> >   _13 = .FMA (a_6(D), b_7(D), _16);
> > -------------------------------------------------------
> > In some case we want to break the chain with width, we can set
> "param_reassoc_max_chain_length_with_fma = 2", it will rearrange ops and
> break the chain with width.
> 
> ... it sounds like the problem could be fully addressed by sorting the chain
> with reassoc-width in mind?
> Wouldn't it be preferable if rewrite_expr_tree_parallel would get a vector of
> mul and a vector of non-mul ops so it can pick from the optimal candidate?
> 
> That said, I think rewrite_expr_tree_parallel_for_fma at least needs more
> comments.
> 
Sorry for not writing note clearly enough, I'll add more. 
I have two places that need to be clarified.

1. For some case we need to keep chain to generate more FMAs, because break chain will lose FMA.
   for example  g + a * b + c * d + e * f,
   Keep chain can get 3 FMAs, break chain can get 2 FMAs. It's hard to say which one is better, so we provide a param for users to customize.
   
2. when the chain has FMAs and need to break the chain with width,
for example l + a * b + c * d + e * f + g * h + j * k;(we already put non-mul first)
rewrite_expr_tree_parallel :
when width = 2, it will break the chain like this. actually it break the chain in to 3. It ignores the width and adds all ops two by two. it will lose FMA.  

ssa1 = l + a * b;
ssa2 = c * d + e * f;
ssa3 = g * h + j * k;
ssa4 = ssa1 + ssa2;
ssa5 = ssa4 + ssa3;

rewrite_expr_tree_parallel_for_fma
when width = 2, we break the chain into two like this.

ssa1 = l + a * b; 
ssa2 = c * d + e * f;
ssa3 = ssa1 + g * h;
ssa4 = ssa2 + j * k;
ssa5 = ssa3 +ssa4;

I think it's okay to remove or keep rewrite_expr_tree_parallel_for_fma. More FMAs are generated only for some special cases.
I'm not sure whether the new method is better than the old one. I created a small case the execution time of the two sequences is almost the same on SPR and ICX.

Thanks,
Lili.