[v4,2/3] Add predict_doloop_p target hook

Hi,

Many thanks for all comments on previous versions.

Comparing with the previous version, I dropped the checks
on costly niter and invalid stmt scanning.  As Richard's
suggestion, keep this as simple as possible, refine it 
if finding any cases which matter later.

Bootstrapped and regression testing passed on powerpc64le.

Is it OK for trunk?  

Thanks,
Kewen


gcc/ChangeLog

2019-06-13  Kewen Lin  <linkw@gcc.gnu.org>

	PR middle-end/80791
	* target.def (predict_doloop_p): New hook.
	* targhooks.h (default_predict_doloop_p): New declaration.
	* targhooks.c (default_predict_doloop_p): New function.
	* doc/tm.texi.in (TARGET_PREDICT_DOLOOP_P): New hook.
	* doc/tm.texi: Regenerate.
	* config/rs6000/rs6000.c (rs6000_predict_doloop_p): New function.
	(TARGET_PREDICT_DOLOOP_P): New macro.
	* tree-ssa-loop-ivopts.c (generic_predict_doloop_p): New function.

Hi Kewen,

On Thu, Jun 13, 2019 at 01:50:05PM +0800, Kewen.Lin wrote:
> Comparing with the previous version, I dropped the checks
> on costly niter and invalid stmt scanning.  As Richard's
> suggestion, keep this as simple as possible, refine it 
> if finding any cases which matter later.

I think we'll want the invalid statement thing back pretty soon, it just
happens too often (20% of the time), and it makes ivopts make bad decisions.
It does not matter (much) for the performance of the generated code, but
still :-)

> +/* Predict whether the given loop in gimple will be transformed in the RTL
> +   doloop_optimize pass.  This is for rs6000 target specific.  */

Everything in rs6000/ is target-specific ;-)  Remove that part?

> +  /* On rs6000, targetm.can_use_doloop_p is actually
> +     can_use_doloop_if_innermost.  Just ensure it's innermost.  */

"the loop is innermost".

> +	fprintf (dump_file, "Predict doloop failure due to"
> +			    " no innermost.\n");

"due to no innermost" isn't great, but I don't know how th phrase it
better, either :-/  It's just debug output of course, so not so very
important.

> +This target hook is required only when the target supports low-overhead
> +loops, and will help some earlier middle-end passes to make some decisions.

Maybe just say it is for ivopts?  Or say that targets that do support
low-overhead loops *should* implement it?

> +/* True if we can predict this loop is possible to be transformed to a
> +   low-overhead loop, otherwise returns false.

"Return true if we predict the loop LOOP will be transformed to a
low-overhead loop, otherwise return false"?  Or mention doloop_optimize
like below:

> +/* Predict whether the given loop will be transformed in the RTL
> +   doloop_optimize pass.  Attempt to duplicate some doloop_optimize checks.
> +   This is only for target independent checks, see targetm.predict_doloop_p
> +   for the target dependent ones.
> +
> +   Note that according to some initial investigation, some checks like costly
> +   niter check and invalid stmt scanning don't have much gains among general
> +   cases, so keep this as simple as possible first.
> +
> +   Some RTL specific checks seems unable to be checked in gimple, if any new
> +   checks or easy checks _are_ missing here, please add them.  */

Good useful note, thanks :-)

The rs6000 part is okay for trunk.  Thanks!


Segher

On 6/14/19 4:53 PM, Segher Boessenkool wrote:
> Hi Kewen,
>
> On Thu, Jun 13, 2019 at 01:50:05PM +0800, Kewen.Lin wrote:
>> Comparing with the previous version, I dropped the checks
>> on costly niter and invalid stmt scanning.  As Richard's
>> suggestion, keep this as simple as possible, refine it 
>> if finding any cases which matter later.
> I think we'll want the invalid statement thing back pretty soon, it just
> happens too often (20% of the time), and it makes ivopts make bad decisions.
> It does not matter (much) for the performance of the generated code, but
> still :-)
>
>> +/* Predict whether the given loop in gimple will be transformed in the RTL
>> +   doloop_optimize pass.  This is for rs6000 target specific.  */
> Everything in rs6000/ is target-specific ;-)  Remove that part?
>
>> +  /* On rs6000, targetm.can_use_doloop_p is actually
>> +     can_use_doloop_if_innermost.  Just ensure it's innermost.  */
> "the loop is innermost".
>
>> +	fprintf (dump_file, "Predict doloop failure due to"
>> +			    " no innermost.\n");
> "due to no innermost" isn't great, but I don't know how th phrase it
> better, either :-/  It's just debug output of course, so not so very
> important.

How about "due to loop nesting?"

Bill
>
>> +This target hook is required only when the target supports low-overhead
>> +loops, and will help some earlier middle-end passes to make some decisions.
> Maybe just say it is for ivopts?  Or say that targets that do support
> low-overhead loops *should* implement it?
>
>> +/* True if we can predict this loop is possible to be transformed to a
>> +   low-overhead loop, otherwise returns false.
> "Return true if we predict the loop LOOP will be transformed to a
> low-overhead loop, otherwise return false"?  Or mention doloop_optimize
> like below:
>
>> +/* Predict whether the given loop will be transformed in the RTL
>> +   doloop_optimize pass.  Attempt to duplicate some doloop_optimize checks.
>> +   This is only for target independent checks, see targetm.predict_doloop_p
>> +   for the target dependent ones.
>> +
>> +   Note that according to some initial investigation, some checks like costly
>> +   niter check and invalid stmt scanning don't have much gains among general
>> +   cases, so keep this as simple as possible first.
>> +
>> +   Some RTL specific checks seems unable to be checked in gimple, if any new
>> +   checks or easy checks _are_ missing here, please add them.  */
> Good useful note, thanks :-)
>
> The rs6000 part is okay for trunk.  Thanks!
>
>
> Segher
>

Hi Segher and Bill,

Thanks a lot for your review comments! I've updated the patch accordingly.

The updated one attached.
diff --git a/gcc/config/rs6000/rs6000.c b/gcc/config/rs6000/rs6000.c
index 91fafc4e766..6667cd03042 100644
--- a/gcc/config/rs6000/rs6000.c
+++ b/gcc/config/rs6000/rs6000.c
@@ -1909,6 +1909,9 @@ static const struct attribute_spec rs6000_attribute_table[] =
 #undef TARGET_CAN_USE_DOLOOP_P
 #define TARGET_CAN_USE_DOLOOP_P can_use_doloop_if_innermost
 
+#undef TARGET_PREDICT_DOLOOP_P
+#define TARGET_PREDICT_DOLOOP_P rs6000_predict_doloop_p
+
 #undef TARGET_ATOMIC_ASSIGN_EXPAND_FENV
 #define TARGET_ATOMIC_ASSIGN_EXPAND_FENV rs6000_atomic_assign_expand_fenv
 
@@ -39413,7 +39416,27 @@ rs6000_mangle_decl_assembler_name (tree decl, tree id)
   return id;
 }
 
-
+/* Predict whether the given loop in gimple will be transformed in the RTL
+   doloop_optimize pass.  */
+
+static bool
+rs6000_predict_doloop_p (struct loop *loop)
+{
+  gcc_assert (loop);
+
+  /* On rs6000, targetm.can_use_doloop_p is actually
+     can_use_doloop_if_innermost.  Just ensure the loop is innermost.  */
+  if (loop->inner != NULL)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Predict doloop failure due to"
+			    " loop nesting.\n");
+      return false;
+    }
+
+  return true;
+}
+
 struct gcc_target targetm = TARGET_INITIALIZER;
 
 #include "gt-rs6000.h"
diff --git a/gcc/doc/tm.texi b/gcc/doc/tm.texi
index 622e8cf240f..c2aa4d04777 100644
--- a/gcc/doc/tm.texi
+++ b/gcc/doc/tm.texi
@@ -11610,6 +11610,14 @@ function version at run-time for a given set of function versions.
 body must be generated.
 @end deftypefn
 
+@deftypefn {Target Hook} bool TARGET_PREDICT_DOLOOP_P (struct loop *@var{loop})
+Return true if we can predict it is possible to use a low-overhead loop
+for a particular loop.  The parameter @var{loop} is a pointer to the loop.
+This target hook is required only when the target supports low-overhead
+loops, and will help ivopts to make some decisions.
+The default version of this hook returns false.
+@end deftypefn
+
 @deftypefn {Target Hook} bool TARGET_CAN_USE_DOLOOP_P (const widest_int @var{&iterations}, const widest_int @var{&iterations_max}, unsigned int @var{loop_depth}, bool @var{entered_at_top})
 Return true if it is possible to use low-overhead loops (@code{doloop_end}
 and @code{doloop_begin}) for a particular loop.  @var{iterations} gives the
diff --git a/gcc/doc/tm.texi.in b/gcc/doc/tm.texi.in
index 17560fce6b7..b4d57b86e2f 100644
--- a/gcc/doc/tm.texi.in
+++ b/gcc/doc/tm.texi.in
@@ -7944,6 +7944,8 @@ to by @var{ce_info}.
 
 @hook TARGET_GENERATE_VERSION_DISPATCHER_BODY
 
+@hook TARGET_PREDICT_DOLOOP_P
+
 @hook TARGET_CAN_USE_DOLOOP_P
 
 @hook TARGET_INVALID_WITHIN_DOLOOP
diff --git a/gcc/target.def b/gcc/target.def
index 7d52102c815..71b69723b75 100644
--- a/gcc/target.def
+++ b/gcc/target.def
@@ -4236,6 +4236,15 @@ DEFHOOK
 rtx, (machine_mode mode, rtx result, rtx val, rtx failval),
  default_speculation_safe_value)
  
+DEFHOOK
+(predict_doloop_p,
+ "Return true if we can predict it is possible to use a low-overhead loop\n\
+for a particular loop.  The parameter @var{loop} is a pointer to the loop.\n\
+This target hook is required only when the target supports low-overhead\n\
+loops, and will help ivopts to make some decisions.\n\
+The default version of this hook returns false.",
+ bool, (struct loop *loop),
+ default_predict_doloop_p)
 
 DEFHOOK
 (can_use_doloop_p,
diff --git a/gcc/targhooks.c b/gcc/targhooks.c
index b27111639f4..0da885ec152 100644
--- a/gcc/targhooks.c
+++ b/gcc/targhooks.c
@@ -643,6 +643,19 @@ default_has_ifunc_p (void)
   return HAVE_GNU_INDIRECT_FUNCTION;
 }
 
+/* Return true if we predict the loop LOOP will be transformed to a
+   low-overhead loop, otherwise return false.
+
+   By default, false is returned, as this hook's applicability should be
+   verified for each target.  Target maintainers should re-define the hook
+   if the target can take advantage of it.  */
+
+bool
+default_predict_doloop_p (struct loop *loop ATTRIBUTE_UNUSED)
+{
+  return false;
+}
+
 /* NULL if INSN insn is valid within a low-overhead loop, otherwise returns
    an error message.
 
diff --git a/gcc/targhooks.h b/gcc/targhooks.h
index 229aacd7b65..50b03ce3aa0 100644
--- a/gcc/targhooks.h
+++ b/gcc/targhooks.h
@@ -85,6 +85,7 @@ extern bool default_fixed_point_supported_p (void);
 
 extern bool default_has_ifunc_p (void);
 
+extern bool default_predict_doloop_p (struct loop *);
 extern const char * default_invalid_within_doloop (const rtx_insn *);
 
 extern tree default_builtin_vectorized_function (unsigned int, tree, tree);
diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
index 890f9b788b4..530ea4ae343 100644
--- a/gcc/tree-ssa-loop-ivopts.c
+++ b/gcc/tree-ssa-loop-ivopts.c
@@ -3712,6 +3712,63 @@ prepare_decl_rtl (tree *expr_p, int *ws, void *data)
   return NULL_TREE;
 }
 
+/* Predict whether the given loop will be transformed in the RTL
+   doloop_optimize pass.  Attempt to duplicate some doloop_optimize checks.
+   This is only for target independent checks, see targetm.predict_doloop_p
+   for the target dependent ones.
+
+   Note that according to some initial investigation, some checks like costly
+   niter check and invalid stmt scanning don't have much gains among general
+   cases, so keep this as simple as possible first.
+
+   Some RTL specific checks seems unable to be checked in gimple, if any new
+   checks or easy checks _are_ missing here, please add them.  */
+
+static bool ATTRIBUTE_UNUSED
+generic_predict_doloop_p (struct ivopts_data *data)
+{
+  struct loop *loop = data->current_loop;
+
+  /* Call target hook for target dependent checks.  */
+  if (!targetm.predict_doloop_p (loop))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Predict doloop failure due to"
+			    " target specific checks.\n");
+      return false;
+    }
+
+  /* Similar to doloop_optimize, check iteration description to know it's
+     suitable or not.  Keep it as simple as possible, feel free to extend it
+     if you find any multiple exits cases matter.  */
+  edge exit = single_dom_exit (loop);
+  struct tree_niter_desc *niter_desc;
+  if (!exit || !(niter_desc = niter_for_exit (data, exit)))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Predict doloop failure due to"
+			    " unexpected niters.\n");
+      return false;
+    }
+
+  /* Similar to doloop_optimize, check whether iteration count too small
+     and not profitable.  */
+  HOST_WIDE_INT est_niter = get_estimated_loop_iterations_int (loop);
+  if (est_niter == -1)
+    est_niter = get_likely_max_loop_iterations_int (loop);
+  if (est_niter >= 0 && est_niter < 3)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file,
+		 "Predict doloop failure due to"
+		 " too few iterations (%u).\n",
+		 (unsigned int) est_niter);
+      return false;
+    }
+
+  return true;
+}
+
 /* Determines cost of the computation of EXPR.  */
 
 static unsigned

On Mon, 17 Jun 2019, Kewen.Lin wrote:

> Hi Segher and Bill,
> 
> Thanks a lot for your review comments! I've updated the patch accordingly.
> 
> The updated one attached.

OK.  I suppose all low-overhead loop instructions use a decrement to zero
style iterator?

Thanks,
Richard.

on 2019/6/17 下午4:51, Richard Biener wrote:
> On Mon, 17 Jun 2019, Kewen.Lin wrote:
> 
>> Hi Segher and Bill,
>>
>> Thanks a lot for your review comments! I've updated the patch accordingly.
>>
>> The updated one attached.
> 
> OK.  I suppose all low-overhead loop instructions use a decrement to zero
> style iterator?
> 

Thanks Richard!

Yes, I think so.  As the function doloop_condition_get, it checks a decrement
and branch jump patterns.


Thanks, 
Kewen

On Mon, Jun 17, 2019 at 10:51:49AM +0200, Richard Biener wrote:
> On Mon, 17 Jun 2019, Kewen.Lin wrote:
> 
> > Hi Segher and Bill,
> > 
> > Thanks a lot for your review comments! I've updated the patch accordingly.
> > 
> > The updated one attached.
> 
> OK.  I suppose all low-overhead loop instructions use a decrement to zero
> style iterator?

The documentation says decrement to 0, decrement to -1, and decrement to
any negative are all supported.  But all are decrement, yes.


Segher

On June 17, 2019 11:59:30 AM GMT+02:00, Segher Boessenkool <segher@kernel.crashing.org> wrote:
>On Mon, Jun 17, 2019 at 10:51:49AM +0200, Richard Biener wrote:
>> On Mon, 17 Jun 2019, Kewen.Lin wrote:
>> 
>> > Hi Segher and Bill,
>> > 
>> > Thanks a lot for your review comments! I've updated the patch
>accordingly.
>> > 
>> > The updated one attached.
>> 
>> OK.  I suppose all low-overhead loop instructions use a decrement to
>zero
>> style iterator?
>
>The documentation says decrement to 0, decrement to -1, and decrement
>to
>any negative are all supported.  But all are decrement, yes.

Hmm, so I wonder if we should tell IVOPTS the kind because the IV generated has to match RTL doloops expectations? Thus return an enum value from the hook? 

Richard. 

>
>Segher

on 2019/6/17 下午8:08, Richard Biener wrote:
> On June 17, 2019 11:59:30 AM GMT+02:00, Segher Boessenkool <segher@kernel.crashing.org> wrote:
>> On Mon, Jun 17, 2019 at 10:51:49AM +0200, Richard Biener wrote:
>>> On Mon, 17 Jun 2019, Kewen.Lin wrote:
>>>
>>>> Hi Segher and Bill,
>>>>
>>>> Thanks a lot for your review comments! I've updated the patch
>> accordingly.
>>>>
>>>> The updated one attached.
>>>
>>> OK.  I suppose all low-overhead loop instructions use a decrement to
>> zero
>>> style iterator?
>>
>> The documentation says decrement to 0, decrement to -1, and decrement
>> to
>> any negative are all supported.  But all are decrement, yes.
> 
> Hmm, so I wonder if we should tell IVOPTS the kind because the IV generated has to match RTL doloops expectations? Thus return an enum value from the hook? 
> 

I guess we don't need to make it in IVOPTs, since doloop_optimize can transform the loop closing to
its expected pattern once it gets the iteration count, with target hook doloop_end.
It's to modify the original closing into:
  niter   -> 0
  niter-1 -> -1
  niter-n -> -n


Thanks,
Kewen

> Richard. 
> 
>>
>> Segher
>

On Mon, 17 Jun 2019, Kewen.Lin wrote:

> on 2019/6/17 下午8:08, Richard Biener wrote:
> > On June 17, 2019 11:59:30 AM GMT+02:00, Segher Boessenkool <segher@kernel.crashing.org> wrote:
> >> On Mon, Jun 17, 2019 at 10:51:49AM +0200, Richard Biener wrote:
> >>> On Mon, 17 Jun 2019, Kewen.Lin wrote:
> >>>
> >>>> Hi Segher and Bill,
> >>>>
> >>>> Thanks a lot for your review comments! I've updated the patch
> >> accordingly.
> >>>>
> >>>> The updated one attached.
> >>>
> >>> OK.  I suppose all low-overhead loop instructions use a decrement to
> >> zero
> >>> style iterator?
> >>
> >> The documentation says decrement to 0, decrement to -1, and decrement
> >> to
> >> any negative are all supported.  But all are decrement, yes.
> > 
> > Hmm, so I wonder if we should tell IVOPTS the kind because the IV generated has to match RTL doloops expectations? Thus return an enum value from the hook? 
> > 
> 
> I guess we don't need to make it in IVOPTs, since doloop_optimize can transform the loop closing to
> its expected pattern once it gets the iteration count, with target hook doloop_end.
> It's to modify the original closing into:
>   niter   -> 0
>   niter-1 -> -1
>   niter-n -> -n

True, but this IV may affect other IVs choice (well, at least if it is
"cheap" to use the doloop IV in derived IVs which it is not for power).

Richard.

on 2019/6/17 下午9:44, Richard Biener wrote:
> On Mon, 17 Jun 2019, Kewen.Lin wrote:
> 
>> on 2019/6/17 下午8:08, Richard Biener wrote:
>>> On June 17, 2019 11:59:30 AM GMT+02:00, Segher Boessenkool <segher@kernel.crashing.org> wrote:
>>>> On Mon, Jun 17, 2019 at 10:51:49AM +0200, Richard Biener wrote:
>>>>> On Mon, 17 Jun 2019, Kewen.Lin wrote:
>>>>>
>>>>>> Hi Segher and Bill,
>>>>>>
>>>>>> Thanks a lot for your review comments! I've updated the patch
>>>> accordingly.
>>>>>>
>>>>>> The updated one attached.
>>>>>
>>>>> OK.  I suppose all low-overhead loop instructions use a decrement to
>>>> zero
>>>>> style iterator?
>>>>
>>>> The documentation says decrement to 0, decrement to -1, and decrement
>>>> to
>>>> any negative are all supported.  But all are decrement, yes.
>>>
>>> Hmm, so I wonder if we should tell IVOPTS the kind because the IV generated has to match RTL doloops expectations? Thus return an enum value from the hook? 
>>>
>>
>> I guess we don't need to make it in IVOPTs, since doloop_optimize can transform the loop closing to
>> its expected pattern once it gets the iteration count, with target hook doloop_end.
>> It's to modify the original closing into:
>>   niter   -> 0
>>   niter-1 -> -1
>>   niter-n -> -n
> 
> True, but this IV may affect other IVs choice (well, at least if it is
> "cheap" to use the doloop IV in derived IVs which it is not for power).
> 

Good point!  For those targets like power having counter register, it would be fine.
For the other, I'm sorry that I'm not sure how the sequence looks like.
All decrement/cmp kept?  Just like normal but it has hardware fusion support?
Maybe we can add one more iv cand specific for this kind of use, assign negative cost
for this specific pair (group/cand), it can give chances to be selected for other uses
if it's better?


Thanks,
Kewen

> Richard.
>