From owner-freebsd-mips@FreeBSD.ORG  Thu Nov 15 22:41:18 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 D00D7B7E;
 Thu, 15 Nov 2012 22:41:18 +0000 (UTC)
 (envelope-from pkelsey@gmail.com)
Received: from mail-vc0-f182.google.com (mail-vc0-f182.google.com
 [209.85.220.182])
 by mx1.freebsd.org (Postfix) with ESMTP id 23DEA8FC12;
 Thu, 15 Nov 2012 22:41:18 +0000 (UTC)
Received: by mail-vc0-f182.google.com with SMTP id fo13so2944229vcb.13
 for <multiple recipients>; Thu, 15 Nov 2012 14:41:16 -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=sAG8Yk+qBstAKKBr6Kg1gwtI0iGyUP0c5Gfti08na5M=;
 b=B2r7E1MKt1/yuV5bkTLk4grecZNYtsG9s5mrGcqtEHhm11v2PpkjGy3q4US++QNlAj
 wcsZxYneFENmnY0wdFO4jnLbdeJnOusO8joHHnOFhdF5UbDj1+K6qDhyr9UbbplkLJio
 Zc4jRAiHH9pqvMYztp0jXMgG8nrwH1H8LAUGN/QD38L3T0SYb6URQoWk5+bdfrcwL5B/
 KxFmqYwN2Q3MmcVmIdwQpBn8SyRRSEw34bOgSURp2wJOQQfJsmxw2p7vr53Q3qtFNHfR
 9pk+u96zYhb5m+JypiG+TXFTQ+Z7nYbyDNkcEMwEX5GRwgrQZs/NHPBZ27uenThX75Cg
 PNZw==
MIME-Version: 1.0
Received: by 10.52.75.70 with SMTP id a6mr3200707vdw.5.1353019276624; Thu, 15
 Nov 2012 14:41:16 -0800 (PST)
Sender: pkelsey@gmail.com
Received: by 10.59.5.38 with HTTP; Thu, 15 Nov 2012 14:41:16 -0800 (PST)
In-Reply-To: <953A0D95-54E1-4023-A1F5-A4A7DE1C6175@bsdimp.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>
 <CAD44qMVVq2nassx7fFai9s=zsiZVPBSFdef87UbMZ4j3PNGkMg@mail.gmail.com>
 <953A0D95-54E1-4023-A1F5-A4A7DE1C6175@bsdimp.com>
Date: Thu, 15 Nov 2012 17:41:16 -0500
X-Google-Sender-Auth: ilJ7oCPdO7uTe1iwm8Acd8Dn-do
Message-ID: <CAD44qMUGAGvGpY_jRWG71VChkOUDn-_dgcopt-uNx6FAmdfUHA@mail.gmail.com>
Subject: Re: ZERO_REGION_SIZE
From: Patrick Kelsey <kelsey@ieee.org>
To: Warner Losh <imp@bsdimp.com>
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:41:19 -0000

On Thu, Nov 15, 2012 at 5:25 PM, Warner Losh <imp@bsdimp.com> wrote:
>
> On Nov 15, 2012, at 3:11 PM, Patrick Kelsey wrote:
>
>> 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));
>
>
> Turns out NetBSD has one that does exactly this...
>

And now that I've gotten away from silly pencil and paper and back to
the glare of the internet, I see gcc has had __builtin_ffs for some
time...