Re: [PATCH v3 1/6] ilog2: create truly constant version for sparse

[Rasmus Villemoes]

On 2018-04-18 23:21, Linus Torvalds wrote:
> On Wed, Apr 18, 2018 at 1:12 AM, Martin Wilck  wrote:
>>
>> No, it doesn't (gcc 7.3.0). -> https://paste.opensuse.org/27471594
>> It doesn't even warn on an expression like this:
>>
>>   #define SIZE (1<<10)
>>   static int foo[ilog2(SIZE)];
> 
> Ok, I think this is the "random gcc versions act differently" issue.
> 
> Sometimes __builtin_constant_p() to a ternary operation acts as a
> constant expression, and sometimes it doesn't.

So __builtin_constant_p on an actual ICE always fold immediately to 1.
Looking at the gcc history, that seems to have been there since at least
2000, but likely forever. And when it's the controlling expression of a
ternary, it's apparently a stronger 1 than a literal 1:

int foo(int);
#define SIZE (1<<10)
#define half(x) (__builtin_constant_p(x) ? (x)>>1 : foo(x))
int bla[half(SIZE)];
int bla2[1 ? 123 : foo(3)+2];

on godbolt.org, gcc 4.1 and gcc4.4 are perfectly happy with this, but
newer gccs complain

  error: variably modified 'bla2' at file scope.

Argh.

> I suspect using the __is_constexpr() trick would make it rather more
> technically correct, but would actually generate much worse code.
> 
> Because it would make us do that dynamic "__ilog2_uXX()" function call
> even when you have a compile-time constant value, if it wasn't
> actually a constant expression (ie a constant argument passed to an
> inline function, for example).

It's a bit ugly, but I suppose one could keep a __builtin_constant_p()
check in the not-ICE-branch, so there's really three cases (ICE,
constant due to various optimizations, really not known at compile
time). But don't we use gcc's intrinsics for fls when available, so that
gcc should be able to know the semantics of __builtin_fls(some-constant)
and hence evaluate that itself at compile time?

Somewhat unrelated, we should probably move the __is_constexpr helper
from kernel.h to some more basic compiler header, to avoid cyclic header
dependencies.

Rasmus

Re: [PATCH v3 1/6] ilog2: create truly constant version for sparse

[Linus Torvalds]

On Wed, Apr 18, 2018 at 1:12 AM, Martin Wilck  wrote:
>
> No, it doesn't (gcc 7.3.0). -> https://paste.opensuse.org/27471594
> It doesn't even warn on an expression like this:
>
>   #define SIZE (1<<10)
>   static int foo[ilog2(SIZE)];

Ok, I think this is the "random gcc versions act differently" issue.

Sometimes __builtin_constant_p() to a ternary operation acts as a
constant expression, and sometimes it doesn't.

Oh well.

> sparse 0.5.2 doesn't warn about that either.

Yeah, sparse doesn't get picky about "constant value" vs "constant
expression" normally. But some things do use the strict form, and
array index expressions is one of those cases.

> So maybe I was wrong, and this is actually a false positive in sparse.

No, it's correct, it's just that the semantics of exactly when
something is considered constant are a bit fluid.

> Do you want me to convert the patch to your approach anyway?

I suspect using the __is_constexpr() trick would make it rather more
technically correct, but would actually generate much worse code.

Because it would make us do that dynamic "__ilog2_uXX()" function call
even when you have a compile-time constant value, if it wasn't
actually a constant expression (ie a constant argument passed to an
inline function, for example).

So I guess your patch is fine, but I also wonder if we should just
default sparse to allow the good old non-strict "constant values are
ok" for indexes.

And turn on strict mode only with -pedantic or something.

 Linus

Re: [PATCH v3 1/6] ilog2: create truly constant version for sparse

[Luc Van Oostenryck]

On Wed, Apr 18, 2018 at 10:12:54AM +0200, Martin Wilck wrote:
> On Tue, 2018-04-17 at 17:07 -0700, Linus Torvalds wrote:
> > On Tue, Apr 17, 2018 at 4:35 PM, Martin Wilck 
> > wrote:
> > > Sparse emits errors about ilog2() in array indices because of the
> > > use of
> > > __ilog2_32() and __ilog2_64(),
> > 
> > If sparse warns about it, then presumably gcc with -Wvla warns about
> > it too?
> 
> No, it doesn't (gcc 7.3.0). -> https://paste.opensuse.org/27471594
> It doesn't even warn on an expression like this:
> 
>   #define SIZE (1<<10)
>   static int foo[ilog2(SIZE)];
> 
> sparse 0.5.2 doesn't warn about that either. It emits "error: bad
> integer constant expression" only if ilog2 is used in an array

sparse supports VLAs at syntaxic level but not much more. Anything
needing directly or indirectly the array size will give this error.

-- Luc Van Oostenryck

Re: [PATCH v3 1/6] ilog2: create truly constant version for sparse

[Martin Wilck]

On Tue, 2018-04-17 at 17:07 -0700, Linus Torvalds wrote:
> On Tue, Apr 17, 2018 at 4:35 PM, Martin Wilck 
> wrote:
> > Sparse emits errors about ilog2() in array indices because of the
> > use of
> > __ilog2_32() and __ilog2_64(),
> 
> If sparse warns about it, then presumably gcc with -Wvla warns about
> it too?

No, it doesn't (gcc 7.3.0). -> https://paste.opensuse.org/27471594
It doesn't even warn on an expression like this:

  #define SIZE (1<<10)
  static int foo[ilog2(SIZE)];

sparse 0.5.2 doesn't warn about that either. It emits "error: bad
integer constant expression" only if ilog2 is used in an array
initializer, like this:

  #define SIZE (1<<10)
  #define SUBS (1<<5)
  static int foo [ilog2(SIZE)] = {
  [ilog2(SUBS)] = 0,
  };

So maybe I was wrong, and this is actually a false positive in sparse.

> So I suspect that what you'd want is
> 
>   #define ilog2(n) \
> __builtin_choose_expr(__is_constexpr(n), \
> const_ilog2(n), \
> __builtin_choose_expr(sizeof(n) <= 4, \
> __ilog2_u32(n), \
> __ilog2_u64(n)))
> 
> or something. Hmm?

Do you want me to convert the patch to your approach anyway?
Or should I throw this away and report to sparse?

Regards and thanks,
Martin

PS: apologies to all recipients for the broken cc list in my post.
-- 
Dr. Martin Wilck , Tel. +49 (0)911 74053 2107
SUSE Linux GmbH, GF: Felix Imendörffer, Jane Smithard, Graham Norton
HRB 21284 (AG Nürnberg)

Re: [PATCH v3 1/6] ilog2: create truly constant version for sparse

[Linus Torvalds]

On Tue, Apr 17, 2018 at 4:35 PM, Martin Wilck  wrote:
> Sparse emits errors about ilog2() in array indices because of the use of
> __ilog2_32() and __ilog2_64(),

If sparse warns about it, then presumably gcc with -Wvla warns about it too?

And if thats the case, then __builtin_constant_p() and a ternary
operation isn't good enough, because gcc -Wvla is even more anal than
sparse is.

Which is why we have that __is_constexpr() magic for min/max().

So I suspect that what you'd want is

  #define ilog2(n) \
__builtin_choose_expr(__is_constexpr(n), \
const_ilog2(n), \
__builtin_choose_expr(sizeof(n) <= 4, \
__ilog2_u32(n), \
__ilog2_u64(n)))

or something. Hmm?

   Linus

[PATCH v3 1/6] ilog2: create truly constant version for sparse

[Martin Wilck]

Sparse emits errors about ilog2() in array indices because of the use of
__ilog2_32() and __ilog2_64(), rightly so
(https://www.spinics.net/lists/linux-sparse/msg03471.html).

Create a const_ilog2() variant that works with sparse for this
scenario.

(Note: checkpatch.pl complains about missing parentheses, but that appears
to be a false positive. I can get rid of the warning simply by inserting
whitespace, making checkpatch "see" the whole macro).

Signed-off-by: Martin Wilck 
---
 include/linux/log2.h | 35 ---
 1 file changed, 24 insertions(+), 11 deletions(-)

diff --git a/include/linux/log2.h b/include/linux/log2.h
index 41a1ae0..2af7f778 100644
--- a/include/linux/log2.h
+++ b/include/linux/log2.h
@@ -72,16 +72,13 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
 }
 
 /**
- * ilog2 - log base 2 of 32-bit or a 64-bit unsigned value
+ * const_ilog2 - log base 2 of 32-bit or a 64-bit constant unsigned value
  * @n: parameter
  *
- * constant-capable log of base 2 calculation
- * - this can be used to initialise global variables from constant data, hence
- * the massive ternary operator construction
- *
- * selects the appropriately-sized optimised version depending on sizeof(n)
+ * Use this where sparse expects a true constant expression, e.g. for array
+ * indices.
  */
-#define ilog2(n)   \
+#define const_ilog2(n) \
 (  \
__builtin_constant_p(n) ? ( \
(n) < 2 ? 0 :   \
@@ -147,10 +144,26 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
(n) & (1ULL <<  4) ?  4 :   \
(n) & (1ULL <<  3) ?  3 :   \
(n) & (1ULL <<  2) ?  2 :   \
-   1 ) :   \
-   (sizeof(n) <= 4) ?  \
-   __ilog2_u32(n) :\
-   __ilog2_u64(n)  \
+   1) :\
+   -1)
+
+/**
+ * ilog2 - log base 2 of 32-bit or a 64-bit unsigned value
+ * @n: parameter
+ *
+ * constant-capable log of base 2 calculation
+ * - this can be used to initialise global variables from constant data, hence
+ * the massive ternary operator construction
+ *
+ * selects the appropriately-sized optimised version depending on sizeof(n)
+ */
+#define ilog2(n) \
+( \
+   __builtin_constant_p(n) ?   \
+   const_ilog2(n) :\
+   (sizeof(n) <= 4) ?  \
+   __ilog2_u32(n) :\
+   __ilog2_u64(n)  \
  )
 
 /**
-- 
2.16.1