Skip to contentSkip to conversation

ilog2: Improve ilog2 for constant arguments

PATCH Applied Peter Zijlstra 3 participants 4 messages Nov 20, 2020 – Nov 21, 2020

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 ilog2: Improve ilog2 for constant arguments

From: Jakub Jelinek <[email protected]>

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.

---
 include/linux/log2.h |    3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
include/linux/log2.h +2 -1
@@ -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)			\
#1 lore raw
Quoted 5 lines · Peter Zijlstra

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

#2 lore raw
Quoted 9 lines · Luc Van Oostenryck
Quoted 5 lines · Peter Zijlstra

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

#3 lore raw
Quoted 11 lines · Jakub Jelinek
Quoted 9 lines · Luc Van Oostenryck
Quoted 5 lines · Peter Zijlstra

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)

Quoted 10 lines

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