[PATCH] ilog2: Improve ilog2 for constant arguments

[PATCH] ilog2: Improve ilog2 for constant arguments

[Peter Zijlstra]

From:   Jakub Jelinek <jakub@redhat.com>

As discussed in https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97445
the const_ilog2 macro generates a lot of code which interferes badly
with GCC inlining heuristics, until it can be proven that the ilog2
argument can or can't be simplified into a constant.

It can be expressed using __builtin_clzll builtin which is supported
by GCC 3.4 and later and when used only in the __builtin_constant_p guarded
code it ought to always fold back to a constant.
Other compilers support the same builtin for many years too.

Other option would be to change the const_ilog2 macro, though as the
description says it is meant to be used also in C constant expressions,
and while GCC will fold it to constant with constant argument even in
those, perhaps it is better to avoid using extensions in that case.

Signed-off-by: Jakub Jelinek <jakub@redhat.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Link: https://lkml.kernel.org/r/20201021132718.GB2176@tucnak
---
 include/linux/log2.h |    3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

--- a/include/linux/log2.h
+++ b/include/linux/log2.h
@@ -156,7 +156,8 @@ unsigned long __rounddown_pow_of_two(uns
 #define ilog2(n) \
 ( \
 	__builtin_constant_p(n) ?	\
-	const_ilog2(n) :		\
+	((n) < 2 ? 0 :			\
+	 63 - __builtin_clzll (n)) :	\
 	(sizeof(n) <= 4) ?		\
 	__ilog2_u32(n) :		\
 	__ilog2_u64(n)			\

Re: [PATCH] ilog2: Improve ilog2 for constant arguments

[Luc Van Oostenryck]

On Fri, Nov 20, 2020 at 01:51:54PM +0100, Peter Zijlstra wrote:
> 
> Other option would be to change the const_ilog2 macro, though as the
> description says it is meant to be used also in C constant expressions,
> and while GCC will fold it to constant with constant argument even in
> those, perhaps it is better to avoid using extensions in that case.

Just for info, the description is outdated and Sparse is just fine with
__builtin_clzll() and friends in constant expressions (since Feb 2017)
 
-- Luc

Re: [PATCH] ilog2: Improve ilog2 for constant arguments

[Jakub Jelinek]

On Sat, Nov 21, 2020 at 09:23:10PM +0100, Luc Van Oostenryck wrote:
> On Fri, Nov 20, 2020 at 01:51:54PM +0100, Peter Zijlstra wrote:
> > 
> > Other option would be to change the const_ilog2 macro, though as the
> > description says it is meant to be used also in C constant expressions,
> > and while GCC will fold it to constant with constant argument even in
> > those, perhaps it is better to avoid using extensions in that case.
> 
> Just for info, the description is outdated and Sparse is just fine with
> __builtin_clzll() and friends in constant expressions (since Feb 2017)

Why is the description outdated?  It is still an extension that not every
compiler might fold in constant expressions.  And, the large expressions
aren't really a problem in constant expressions, they will be folded there
to constant or error.
The problem the patch was trying to solve is that the large expressions are
a problem at least for GCC in runtime code when guarded by
__builtin_constant_p, because __builtin_constant_p is folded quite late
(intentionally so, so that more constants can be propagated into it, e.g.
after inlining etc.), and the large expressions might confuse inliner
heuristics.

	Jakub

Re: [PATCH] ilog2: Improve ilog2 for constant arguments

[Luc Van Oostenryck]

On Sat, Nov 21, 2020 at 09:29:54PM +0100, Jakub Jelinek wrote:
> On Sat, Nov 21, 2020 at 09:23:10PM +0100, Luc Van Oostenryck wrote:
> > On Fri, Nov 20, 2020 at 01:51:54PM +0100, Peter Zijlstra wrote:
> > > 
> > > Other option would be to change the const_ilog2 macro, though as the
> > > description says it is meant to be used also in C constant expressions,
> > > and while GCC will fold it to constant with constant argument even in
> > > those, perhaps it is better to avoid using extensions in that case.
> > 
> > Just for info, the description is outdated and Sparse is just fine with
> > __builtin_clzll() and friends in constant expressions (since Feb 2017)
> 
> Why is the description outdated?  It is still an extension that not every
> compiler might fold in constant expressions.  And, the large expressions
> aren't really a problem in constant expressions, they will be folded there
> to constant or error.
> The problem the patch was trying to solve is that the large expressions are
> a problem at least for GCC in runtime code when guarded by
> __builtin_constant_p, because __builtin_constant_p is folded quite late
> (intentionally so, so that more constants can be propagated into it, e.g.
> after inlining etc.), and the large expressions might confuse inliner
> heuristics.

I was only talking about the part "Use this where *sparse* expects a true
constant expression, e.g. for array 75 indices." and wanted to say that 
__builtin_clzll() with a constant argument is now also expanded to a
constant, like GCC does (it wasn't the case before 2017 and I think
it was the main reason why const_ilog2() is written as it is).

-- Luc

[PATCH] ilog2: improve ilog2 for constant arguments

[Eric Lin]

Commit 2f78788b55ba ("ilog2: improve ilog2 for constant arguments")
used __builtin_clzll builtin to avoid generating a lot of code
which interferes badly with GCC inlining heuristics.

Cc: Jakub Jelinek <jakub@redhat.com>
Cc: linux-kernel@vger.kernel.org
Signed-off-by: Eric Lin <ericlinsechs@gmail.com>
---
 tools/include/linux/log2.h | 78 ++++----------------------------------
 1 file changed, 8 insertions(+), 70 deletions(-)

diff --git a/tools/include/linux/log2.h b/tools/include/linux/log2.h
index e20a67d538b8..6180e8f879c4 100644
--- a/tools/include/linux/log2.h
+++ b/tools/include/linux/log2.h
@@ -68,76 +68,14 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  *
  * selects the appropriately-sized optimised version depending on sizeof(n)
  */
-#define ilog2(n)				\
-(						\
-	__builtin_constant_p(n) ? (		\
-		(n) < 2 ? 0 :			\
-		(n) & (1ULL << 63) ? 63 :	\
-		(n) & (1ULL << 62) ? 62 :	\
-		(n) & (1ULL << 61) ? 61 :	\
-		(n) & (1ULL << 60) ? 60 :	\
-		(n) & (1ULL << 59) ? 59 :	\
-		(n) & (1ULL << 58) ? 58 :	\
-		(n) & (1ULL << 57) ? 57 :	\
-		(n) & (1ULL << 56) ? 56 :	\
-		(n) & (1ULL << 55) ? 55 :	\
-		(n) & (1ULL << 54) ? 54 :	\
-		(n) & (1ULL << 53) ? 53 :	\
-		(n) & (1ULL << 52) ? 52 :	\
-		(n) & (1ULL << 51) ? 51 :	\
-		(n) & (1ULL << 50) ? 50 :	\
-		(n) & (1ULL << 49) ? 49 :	\
-		(n) & (1ULL << 48) ? 48 :	\
-		(n) & (1ULL << 47) ? 47 :	\
-		(n) & (1ULL << 46) ? 46 :	\
-		(n) & (1ULL << 45) ? 45 :	\
-		(n) & (1ULL << 44) ? 44 :	\
-		(n) & (1ULL << 43) ? 43 :	\
-		(n) & (1ULL << 42) ? 42 :	\
-		(n) & (1ULL << 41) ? 41 :	\
-		(n) & (1ULL << 40) ? 40 :	\
-		(n) & (1ULL << 39) ? 39 :	\
-		(n) & (1ULL << 38) ? 38 :	\
-		(n) & (1ULL << 37) ? 37 :	\
-		(n) & (1ULL << 36) ? 36 :	\
-		(n) & (1ULL << 35) ? 35 :	\
-		(n) & (1ULL << 34) ? 34 :	\
-		(n) & (1ULL << 33) ? 33 :	\
-		(n) & (1ULL << 32) ? 32 :	\
-		(n) & (1ULL << 31) ? 31 :	\
-		(n) & (1ULL << 30) ? 30 :	\
-		(n) & (1ULL << 29) ? 29 :	\
-		(n) & (1ULL << 28) ? 28 :	\
-		(n) & (1ULL << 27) ? 27 :	\
-		(n) & (1ULL << 26) ? 26 :	\
-		(n) & (1ULL << 25) ? 25 :	\
-		(n) & (1ULL << 24) ? 24 :	\
-		(n) & (1ULL << 23) ? 23 :	\
-		(n) & (1ULL << 22) ? 22 :	\
-		(n) & (1ULL << 21) ? 21 :	\
-		(n) & (1ULL << 20) ? 20 :	\
-		(n) & (1ULL << 19) ? 19 :	\
-		(n) & (1ULL << 18) ? 18 :	\
-		(n) & (1ULL << 17) ? 17 :	\
-		(n) & (1ULL << 16) ? 16 :	\
-		(n) & (1ULL << 15) ? 15 :	\
-		(n) & (1ULL << 14) ? 14 :	\
-		(n) & (1ULL << 13) ? 13 :	\
-		(n) & (1ULL << 12) ? 12 :	\
-		(n) & (1ULL << 11) ? 11 :	\
-		(n) & (1ULL << 10) ? 10 :	\
-		(n) & (1ULL <<  9) ?  9 :	\
-		(n) & (1ULL <<  8) ?  8 :	\
-		(n) & (1ULL <<  7) ?  7 :	\
-		(n) & (1ULL <<  6) ?  6 :	\
-		(n) & (1ULL <<  5) ?  5 :	\
-		(n) & (1ULL <<  4) ?  4 :	\
-		(n) & (1ULL <<  3) ?  3 :	\
-		(n) & (1ULL <<  2) ?  2 :	\
-		1 ) :				\
-	(sizeof(n) <= 4) ?			\
-	__ilog2_u32(n) :			\
-	__ilog2_u64(n)				\
+#define ilog2(n) \
+( \
+	__builtin_constant_p(n) ?	\
+	((n) < 2 ? 0 :			\
+	 63 - __builtin_clzll(n)) :	\
+	(sizeof(n) <= 4) ?		\
+	__ilog2_u32(n) :		\
+	__ilog2_u64(n)			\
  )
 
 /**
-- 
2.43.0