Subject: Re: [PATCH v2] tile: avoid using clocksource_cyc2ns with absolute
 cycle count
To: Peter Zijlstra <peterz@infradead.org>
References: <bf36c76f-b26f-8d17-b951-f6b919845172@mellanox.com>
 <1479324933-8161-1-git-send-email-cmetcalf@mellanox.com>
 <CALAqxLWemyrZPjERPW0vMQ+iti0zfX+nLrvgyj4vW76MW2yTig@mail.gmail.com>
 <c656758a-8299-0b96-6d87-23f9beafc481@mellanox.com>
 <20161117095343.GF3142@twins.programming.kicks-ass.net>
CC: John Stultz <john.stultz@linaro.org>,
        Thomas Gleixner <tglx@linutronix.de>, Salman Qazi <sqazi@google.com>,
        Paul Turner <pjt@google.com>, Tony Lindgren <tony@atomide.com>,
        Steven Miao <realmz6@gmail.com>, lkml <linux-kernel@vger.kernel.org>
From: Chris Metcalf <cmetcalf@mellanox.com>
Message-ID: <d7a8a75d-ddc3-a408-dc6c-c0225c824dc2@mellanox.com>
Date: Thu, 17 Nov 2016 15:00:14 -0500
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:45.0) Gecko/20100101
 Thunderbird/45.4.0
MIME-Version: 1.0
In-Reply-To: <20161117095343.GF3142@twins.programming.kicks-ass.net>
Content-Type: text/plain; charset="windows-1252"; format=flowed
Content-Transfer-Encoding: 7bit
SpamDiagnosticOutput: 1:99
SpamDiagnosticMetadata: NSPM
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 17 Nov 2016 20:00:22.2197 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB6PR0501MB2760
Sender: linux-kernel-owner@vger.kernel.org
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org
Content-Length: 3343
Lines: 66

On 11/17/2016 4:53 AM, Peter Zijlstra wrote:
> On Wed, Nov 16, 2016 at 03:16:59PM -0500, Chris Metcalf wrote:
>> PeterZ (cc'ed) then improved it to use __int128 math via
>> mul_u64_u32_shr(), but that doesn't help tile; we only do one multiply
>> instead of two, but the multiply is handled by an out-of-line call to
>> __multi3, and the sched_clock() function ends up about 2.5x slower as
>> a result.
> Well, only if you set CONFIG_ARCH_SUPPORTS_INT128, otherwise it reduces
> to 2 32x23->64 multiplications, of which one if conditional on there
> actually being bits set in the high word of the u64 argument.

I didn't notice that.  It took me down an interesting rathole.

Obviously the branch optimization won't help on cycle counter values,
since we blow out of the low 32 bits in the first few seconds of
uptime.  So the conditional test won't help, but the 32x32
multiply optimizations should.

However, I was surprised to discover that the compiler doesn't always
catch the 32x32 case.  It does for simple cases on gcc 4.4, but if
you change the compiler version or the complexity of the code, it can
lose sight of the optimization opportunity, and in fact that happens
in mul_u64_u32_shr(), and we get 64x64 multiplies.  I passed this
along to our compiler team as an optimization bug.

Given that, it turns out it's always faster to do the unconditional
path on tilegx.  The basic machine instruction is a 32x32
multiply-accumulate, but unlike most tilegx instructions, it causes a
1-cycle RAW hazard stall if you try to use the result in the next
instruction.  Similarly, mispredicted branches take a 1-cycle stall.
The unconditional code pipelines the multiplies completely and runs in
10 cycles; the conditional code has two RAW hazard stalls and a branch
stall, so it takes 12 cycles even when it skips the second multiply.

Working around the missed compiler optimization by taking the existing
mul_u64_u32_shr() and replacing "*" with calls to __insn_mul_lu_lu()
to use the compiler builtin gives a 10-cycle function (assuming we
have to do both multiplies).  So this is the same performance as the
pipelined mult_frac() that does the overlapping 64x64 multiplies.

We can do better by providing a completely hand-rolled version of the
function, either using "*" if the compiler optimization is fixed, or
__insn_mul_lu_lu() if it isn't, that doesn't do a conditional branch:

static inline u64 mul_u64_u32_shr(u64 a, u64 mul, unsigned int shift)
{
     return (__insn_mul_lu_lu(a, mul) >> shift) +
         (__insn_mul_lu_lu(a >> 32, mul) << (32 - shift));
}

This compiles down to 5 cycles with no hazard stalls.  It's not
completely clear where I'd put this to override the <linux/math64.h>
version; presumably in <asm/div64.h>?  Of course I'd then also have to
make it conditional on __tilegx__, since tilepro has a different set
of multiply instructions, as it's an ILP32 ISA.

I'm a little dubious that it's worth the investment in build
scaffolding to do this to save 5 cycles, so I think for now I will
just keep the mult_frac() version, and push it to stable to fix the
bug with the cycle counter overflowing.  Depending on
what/when I hear back from the compiler team, I will think about
saving those few extra cycles with a custom mul_u64_u32_shr().

-- 
Chris Metcalf, Mellanox Technologies
http://www.mellanox.com