From owner-freebsd-mips@FreeBSD.ORG  Thu Nov 15 22:11:07 2012
Return-Path: <owner-freebsd-mips@FreeBSD.ORG>
Delivered-To: mips@freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52])
 by hub.freebsd.org (Postfix) with ESMTP id 829302DB;
 Thu, 15 Nov 2012 22:11:07 +0000 (UTC)
 (envelope-from pkelsey@gmail.com)
Received: from mail-vb0-f54.google.com (mail-vb0-f54.google.com
 [209.85.212.54])
 by mx1.freebsd.org (Postfix) with ESMTP id 790EB8FC08;
 Thu, 15 Nov 2012 22:11:06 +0000 (UTC)
Received: by mail-vb0-f54.google.com with SMTP id l1so2810376vba.13
 for <multiple recipients>; Thu, 15 Nov 2012 14:11:05 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
 h=mime-version:sender:in-reply-to:references:date
 :x-google-sender-auth:message-id:subject:from:to:cc:content-type;
 bh=iF7sP3X/OHLY1NAqRiToWicVAZPsZ1oks5jIAt5G9Nk=;
 b=MsLRIyTlnrcHet+YjpEsTiAYi6o57b0y80F2FgAAliv+7ZaT3X4QzA2YuaAmOZSLqb
 twAkj4P50+H0kf+C/E6MuZ+4kWbR26EWp+TL5EuxoVMNLj7mRfIkZ9KsKYLo9CHKBjgd
 4nC87MbILmKsF5DFp2GBzTFWspqIvXuM6d73RfBQwuL1xjVy23h+4LPOeNYRwcDG2CJ9
 CGteMkEIK25bNOiPdsLgESAsw5lToj1wbM2KYsCaA3LGD9ftFC95hujM+6hxGN+XCzl9
 qYpm8FTrVVbVWL8HjWq2BdRCoHD0qIEZHYb0DS9F1wP3CZsQPOsavJsWA3sxpuB1EP7K
 VsGQ==
MIME-Version: 1.0
Received: by 10.220.40.16 with SMTP id i16mr3503033vce.31.1353017465472; Thu,
 15 Nov 2012 14:11:05 -0800 (PST)
Sender: pkelsey@gmail.com
Received: by 10.59.5.38 with HTTP; Thu, 15 Nov 2012 14:11:05 -0800 (PST)
In-Reply-To: <CACVs6=9ZiVeWcJUoeNU_Mybn5WgZ2edUkx4ERPEXD+PODp8gKw@mail.gmail.com>
References: <50A53391.4080909@rice.edu>
 <CAJ-Vmon-v3K7012ti_L6ao3wQHfQ99Jau1kJ+GhumbPjAuSDww@mail.gmail.com>
 <50A54CCD.8070409@rice.edu>
 <DF2CB7FC-C1ED-4F4C-A39A-60B5E7FC566D@bsdimp.com>
 <CACVs6=9ZiVeWcJUoeNU_Mybn5WgZ2edUkx4ERPEXD+PODp8gKw@mail.gmail.com>
Date: Thu, 15 Nov 2012 17:11:05 -0500
X-Google-Sender-Auth: bRZ3vreJ3TGJlJxGnZB9kgEWcyM
Message-ID: <CAD44qMVVq2nassx7fFai9s=zsiZVPBSFdef87UbMZ4j3PNGkMg@mail.gmail.com>
Subject: Re: ZERO_REGION_SIZE
From: Patrick Kelsey <kelsey@ieee.org>
To: Juli Mallett <jmallett@freebsd.org>
Content-Type: text/plain; charset=ISO-8859-1
Cc: "Jayachandran C." <jchandra@freebsd.org>,
 "freebsd-mips@FreeBSD.org" <mips@freebsd.org>, Alan Cox <alc@rice.edu>
X-BeenThere: freebsd-mips@freebsd.org
X-Mailman-Version: 2.1.14
Precedence: list
List-Id: Porting FreeBSD to MIPS <freebsd-mips.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/options/freebsd-mips>,
 <mailto:freebsd-mips-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-mips>
List-Post: <mailto:freebsd-mips@freebsd.org>
List-Help: <mailto:freebsd-mips-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-mips>,
 <mailto:freebsd-mips-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Thu, 15 Nov 2012 22:11:07 -0000

On Thu, Nov 15, 2012 at 5:02 PM, Juli Mallett <jmallett@freebsd.org> wrote:
> On Thu, Nov 15, 2012 at 1:07 PM, Warner Losh <imp@bsdimp.com> wrote:
>
>>
>> On Nov 15, 2012, at 1:13 PM, Alan Cox wrote:
>> > P.S. I would encourage someone with hardware to look into implementing a
>> > non-iterative ffs*() using (d)clz.  The MIPS pmap would benefit from
>> > this.  Basically, most pmap_enter() calls are doing an ffs*().
>>
>> ffs finds the first bit set. clz counts the number of leading zeros and
>> thus finds the last bit set.  Would a non-iterative fls* be helpful?
>>
>
> Right.  And no widespread ctz/ffs MIPS instructions as far as I know.  We
> could use pop/dpop on processors that support them to do non-iterative
> ffs*, with a few additional instructions, though.

I was thinking something like this might work:

value to ffs is in r1, MSB is the index of the MSB (so, 31 or 63):

if (0 == r1) return(your_choice);
r2 = r1 - 1;
r2 = r1 ^ r2;
return (MSB - clz(r2));

-Patrick