From: Rasmus Villemoes <linux@rasmusvillemoes.dk>
To: "George Spelvin" <linux@horizon.com>
Cc: akpm@linux-foundation.org, chris@chris-wilson.co.uk, davem@davemloft.net,
        dborkman@redhat.com, hannes@stressinduktion.org,
        klimov.linux@gmail.com, laijs@cn.fujitsu.com,
        linux-kernel@vger.kernel.org, msalter@redhat.com,
        takahiro.akashi@linaro.org, tgraf@suug.ch, valentinrothberg@gmail.com,
        yury.norov@gmail.com
Subject: Re: [PATCH v3 1/3] lib: find_*_bit reimplementation
Organization: D03
References: <87zj8jzc11.fsf@rasmusvillemoes.dk>
	<20150212234603.30908.qmail@ns.horizon.com>
Date: Fri, 13 Feb 2015 11:13:43 +0100
In-Reply-To: <20150212234603.30908.qmail@ns.horizon.com> (George Spelvin's
	message of "12 Feb 2015 18:46:03 -0500")
Message-ID: <87386ayv8o.fsf@rasmusvillemoes.dk>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 1531
Lines: 54

On Fri, Feb 13 2015, "George Spelvin" <linux@horizon.com> wrote:

>> the main loop is 20--3b. The test instruction at 2e seems to be
>> redundant. The same at 37: the sub instruction already sets plenty of
>> flags that could be used, so explicitly comparing %rbx to -1 seems
>> redundant.
>
> Er... I think you hand-edited that code; it's wrong.  The loop assumes that
> %rbx is in units of words, but the prologue sets it up in units of bits.

No, but I messed up the source by hand :-) My DIV_ROUND_UP macro was
bogus. Well spotted. Fixing that I still see the redundant cmp and
test, though.

> The mov to %rcx is also redundant, since it could be eliminated with
> some minor rescheduling.
>
> The code generation I *want* for that function is:
>
> # addr in %rdi, size in %rsi
> 	movl	%esi, %ecx
> 	leaq	0x3f(%rsi), %rax
> 	negl	%ecx
> 	movq	$-1, %rdx
>         shrq	$6, %rax
> 	shrq	%cl, %rdx
> 	jmp	2f
> 1:
> 	movq	$-1, %rdx
> 2:
> 	subq	$1, %rax
> 	jc	3f
> 	andq	(%rdi,%rax,8), %rdx
> 	jeq	1b
>
> 	bsrq	%rdx, %rdx
>         salq    $6, %rax
> 	addq	%rdx, %rax
>         ret
> 3:
> 	movq	%rsi, %rax
> 	retq

Nice. But I don't think find_last_bit is important enough to warrant
arch-specific versions.

So, where are we with this? Have we reached some kind of consensus?

Rasmus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/