533546 - LIR_quad emits suboptimal code for x86

Status: RESOLVED FIXED

(Core Graveyard :: Nanojit, defect)

Description

[Steven Johnson]

Loading an arbitrary FP constant into an SSE2 register is generally done by storing two 32-bit constants in the local frame, then loading into an SSE2 reg. Unfortunately there doesn't seem to be any smarts about hoisting these out of loops, so a constant used in an inner loop does this store-and-reload each time thru the loop. There ought to be a way to hoist this out of loops (assuming adequate register supply, which is often the case)

Comment 1

[Steven Johnson]

FYI: I hacked the code so that testcase where I first noticed this (SciMark SOR) would always special-case the magic constants that we need, to avoid the redundant store everytime thru the inner loop

Comment 2

[Steven Johnson]

(trying again)

FYI: I hacked the code so that testcase where I first noticed this (SciMark SOR) would always special-case the magic constants that we need, to avoid the redundant store everytime thru the inner loop, and the overall speed rating doubled. So this is *definitely* worth solving!

Comment 3

[Edwin Smith]

the easiest fix i can think of would be having the backend create a literal pool for each method (similar to what we do for ARM) so all constants that can't be used with immediate mode instructions live in the pool, and the code only ever loads them (never stores them).  

this approach would avoid having to deal with lifetime-range extension logic that would be needed for "true" hoisting.

presumably this would apply to all cpu's for double literals since none support immediate-mode 64bit doubles, and so maybe literal-pool-management has some shareable parts.  (or at least ARM stops being a special case).

Comment 4

[Steven Johnson]

(In reply to comment #3)
> presumably this would apply to all cpu's for double literals since none support
> immediate-mode 64bit doubles, and so maybe literal-pool-management has some
> shareable parts.  (or at least ARM stops being a special case).

maybe, maybe not... IIRC x64 supports 64-bit int literals for GPR registers; it may or may not be a perf win to do a load-double-from-mem vs. a load-immediate followed by a reg-reg move.

Comment 5

[Steven Johnson]

Attachment: Patch

Here's a patch with one approach: it allocates quad constants from dataAlloc and emits loads for those, so no stack space is needed for LIR_quad/LIR_float. 

Drawbacks:
-- the patch needed to intrude on core code a bit... partly because we need a new invariant that findMemFor() should never be called for LIR_quad/LIR_float in this mode, and partly because I suspect (without proof) that other architectures may benefit from a similar pooling as well.
-- avoids the redundant stores, but still doesn't do anything to hoist the original load out of a loop when possible. 

Still, the above patch makes a substantial perf improvement on code doing lots of fp-const usage in inner loops; a variant of SciMark/SOR nearly doubled in speed with this patch in place.

Comment 6

[Steven Johnson]

Also: this patch assumes that dataAlloc always returns 8-byte aligned pointers, which I haven't taken the time to verify. (8-aligned doubles aren't required for x86, but there is a nontrivial performance penalty otherwise)

Comment 7

[Nicholas Nethercote [inactive]]

Comment on attachment 417562 [details] [diff] [review]
Patch

>diff -r 9d15d6f4868e nanojit/Nativei386.cpp
>--- a/nanojit/Nativei386.cpp	Mon Dec 14 13:50:10 2009 -0800
>+++ b/nanojit/Nativei386.cpp	Mon Dec 14 14:12:24 2009 -0800
>@@ -466,7 +466,9 @@
>             int d = (arg - abi_regcount) * sizeof(intptr_t) + 8;
>             LD(r, d, FP);
>         }
>-        else {
>+        else if (i->isconstq()) {
>+            asm_quad(r, i->imm64());
>+        } else {
>             int d = findMemFor(i);
>             asm_load(d,r);
>         }

Might as well put this case just after the isconst() case.


>+    void Assembler::asm_quad(Register r, uint64_t q)
>+    {
>+        if (rmask(r) & XmmRegs) {
>+            if (q == 0) {
>+                // test (int64)0 since -0.0 == 0.0
>+                SSE_XORPDr(r, r);
>+            } else if (q == 0x3FF0000000000000LL) {
>+                // 1.0 is extremely frequent and worth special-casing!
>+                static const double k_ONE = 1.0;
>+                LDSDm(r, &k_ONE);
>+            } else {
>+                const uint64_t* p = findQuadConstant(q);
>+                LDSDm(r, (const double*)p);
>+            }
>+        } else {
>+            if (q == 0) {
>+                // test (int64)0 since -0.0 == 0.0
>+                FLDZ();
>+            } else if (q ==0x3FF0000000000000LL ) {
>+                FLD1();
>+            } else {
>+                const uint64_t* p = findQuadConstant(q);
>+                FLDQdm((const double*)p);
>+            }
>+        }
>+    }

I hate that you've written out 1.0 as 0x3FF0000000000000LL.  It shouldn't be necessary now anyway, right?  Just put it into the constant pool with all the others.

Can you add a NanoAssert(r == FST0) in the else branch?

You've removed the "can fit in 32bits" case -- was that deliberate?  That's an important case in the old code.  Would a mov/xorpd/cvtsi2sd be faster than a load from memory?  To do it safely requires propagating 'canClobberCCs' into asm_quad().


>+#define FLDQdm(m)   do { const double* const dm = m; count_ldq(); FPUdm(0xdd00, dm); asm_output("fldq (#%p)",dm); fpu_push();} while(0)

I don't think the '#' is necessary.  I'm in the process of removing them elsewhere (bug 532566).

Comment 8

[Nicholas Nethercote [inactive]]

Attachment: alternative patch

Here's a version that implements most of my suggestions, most notably the "can fit in 32-bits" case.  I didn't see any notable difference between your version and my version but it might be worth trying my version on your tests.

BTW, I got a 3x speedup on a microbenchmark that has a quad constant in the main loop with both patches.

Is there any way to hoist things out of loops in Nanojit?  Doesn't seem like it, and that's a big shortcoming.

Comment 9

[Edwin Smith]

where there's a will, there's a way, right?

here's a sketch may seem weird at first but doesn't require code motion or any new passes.  (but does add one more reader to the pipeline).

1. make a LirFilter subclass for const hoisting, and inside keep a list of LIns* for constants we have seen so far.

2. read() will call in->read().  when we see a const, add it to our list and skip it, which pulls the const out of the instruction sequence we see it in, and saves it for later.

3. when we see LIR_start, switch modes, and return one saved constant.  keep doing this until we're out, then return the saved LIR_start.  (maybe this mode-switch needs to happen when we see the first LIR_param).

the effect is all immediates get lifted out of the code stream and stuck at the top.

In principle a reader like this could be aware of block boundaries and could read ahead, buffer instructions, reorder them, etc.  It could even generate new instructions if it keeps a LirBuffer squirreled away internally for its own use.  (write the new instruction to the buffer, then return a pointer to it.  or heck, if traversing these manufactured instructions isn't required, we could use Allocator to new them up as needed, from an appropriately-long-lived allocator of course).

Comment 10

[Steven Johnson]

(In reply to comment #7)

> I hate that you've written out 1.0 as 0x3FF0000000000000LL. 

it's ugly, but avoids a possible reload or reg-reg move for the compare... but...

> It shouldn't be
> necessary now anyway, right?  Just put it into the constant pool with all the
> others.

bingo, so above is moot
 
> Can you add a NanoAssert(r == FST0) in the else branch?

sure, but that's the only x87 reg that the 386 backend knows about -- what else could it be? :-)

> You've removed the "can fit in 32bits" case -- was that deliberate?  That's an
> important case in the old code.  Would a mov/xorpd/cvtsi2sd be faster than a
> load from memory?  

Good question. My (foolish, untested) assumption was "no". One way to find out.

Comment 11

[Steven Johnson]

(In reply to comment #8)
> Here's a version that implements most of my suggestions, most notably the "can
> fit in 32-bits" case.  I didn't see any notable difference between your version
> and my version but it might be worth trying my version on your tests.

not a big diff, but on my SciMark test yours seems possibly faster... composite score of ~199 vs ~197 for my patch, fairly consistent across multiple runs. So I vote for yours.

should we move ahead with pushing it as-is or do we want to do more work first? (IMHO it seems pretty safe and the speed improvement is significant)

BTW: is it the case that dataAlloc always returns 8-byte-aligned pointers? If not, there's more optimization awaiting us.

Comment 12

[Steven Johnson]

Also: I wonder if x86-64 might benefit from this. (Probably much less, but who knows)

Comment 13

[Nicholas Nethercote [inactive]]

(In reply to comment #10)
> > Can you add a NanoAssert(r == FST0) in the else branch?
> 
> sure, but that's the only x87 reg that the 386 backend knows about -- what else
> could it be? :-)

That's what assertions are for -- testing assumptions.

(In reply to comment #11)
>
> should we move ahead with pushing it as-is or do we want to do more work first?
> (IMHO it seems pretty safe and the speed improvement is significant)

I want the debug output to be fixed up at least.  And I'm not all that happy with my approach in the "can fit in 32 bits" case -- using cvt for cases where the condition codes can be clobbered and constant pools for other cases is a bit odd.

> BTW: is it the case that dataAlloc always returns 8-byte-aligned pointers? If
> not, there's more optimization awaiting us.

I don't know.  That would be good to test.  It's possible that TM and TR have different dataAllocs, too.

Comment 14

[Edwin Smith]

nanojit::Allocator returns 8-aligned blocks as long as its underlying provider does.  we should add an assert to check that in Allocator::allocSlow().

Comment 15

[Steven Johnson]

(In reply to comment #13)
> (In reply to comment #11)
> > should we move ahead with pushing it as-is or do we want to do more work 
> 
> I want the debug output to be fixed up at least.  And I'm not all that happy
> with my approach in the "can fit in 32 bits" case -- using cvt for cases where
> the condition codes can be clobbered and constant pools for other cases is a
> bit odd.

OK -- do you want to nurse it thru to completion with a subsequent patch, or shall I?

Comment 16

[Nicholas Nethercote [inactive]]

I can take over if you're happy to wait a bit for it to go in -- I have a stack of things I'm trying to get in and this conflicts with some of them (eg. bug 516347)... we manage to keep treading on each other's toes.

Comment 17

[Steven Johnson]

(In reply to comment #16)
> I can take over if you're happy to wait a bit for it to go in -- I have a stack
> of things I'm trying to get in and this conflicts with some of them (eg. bug
> 516347)... we manage to keep treading on each other's toes.

Let's see who gets to it first... I have various higher-priority items on my plate at the moment so probably won't get to it for a few days (possibly till after the holidays).

Comment 18

[Steven Johnson]

(In reply to comment #14)
> nanojit::Allocator returns 8-aligned blocks as long as its underlying provider
> does.  we should add an assert to check that in Allocator::allocSlow().

Adding such an assert fails massively. New bug: https://bugzilla.mozilla.org/show_bug.cgi?id=536568

Comment 19

[Steven Johnson]

Attachment: Updated patch

Updated/rebased version of Nick's patch.

> I want the debug output to be fixed up at least. 

In what way? Granted the current output is a little iffy (basically emitting a comment about a quad constant being generated at a specific address) but presumably you have something better in mind?

> And I'm not all that happy
> with my approach in the "can fit in 32 bits" case -- using cvt for cases where
> the condition codes can be clobbered and constant pools for other cases is a
> bit odd.

Yeah, it's a bit odd, but I'm not sure there's a clearly better approach for x86.

Comment 20

[Edwin Smith]

Comment on attachment 419020 [details] [diff] [review]
Updated patch

once njn is happy, i'm happy

Comment 21

[Nicholas Nethercote [inactive]]

Attachment: my patch

I didn't like that the quad comment got between the instruction and any "<= restore" suffix.  So I just got rid of it, the constant printed after the movsd is good enough IMO.  I also got rid of some unnecessary '#'s before addresses.

Comment 22

[Nicholas Nethercote [inactive]]

Attachment: my patch v2

attach the right patch this time

Comment 23

[Steven Johnson]

Comment on attachment 419054 [details] [diff] [review]
my patch v2

Looks good. I think we should experiment with Edwin's idea about hoisting the constants too, but that can come in a subsequent patch.

Comment 24

[Steven Johnson]

After-holidays ping... are we ready to land the existing patch?

Comment 25

[Nicholas Nethercote [inactive]]

Yep!

Comment 26

[Steven Johnson]

Attachment: nick's patch, with non-sse2 goodness

Applying Nick's patch to current NJ tip fails current lirasm --random when sse2 is disabled: asm_fop asserts since it calls findMemFor erroneously. This addes direct-memory versions of the x87 operations to deal with this case.

Comment 27

[Steven Johnson]

FYI, this passes NJ sanities, but I am going to do futher torture-testing in Flash and TM... if those pass (with sse2 disabled) then I will commit.

Comment 28

[Steven Johnson]

Attachment: nick's patch, with non-sse2 goodness (v2)

asm_fcmp also wasn't happy in non-sse2 mode (lirasm --random didn't trigger it for me, but some FP-heavy code in Flash did).

Comment 29

[Nicholas Nethercote [inactive]]

Comment on attachment 419997 [details] [diff] [review]
nick's patch, with non-sse2 goodness (v2)

Have you looked through all the affected asm_* functions to see that the x87 case has been handled?  Better to do it via inspection than by waiting for tests to trigger it...

Comment 30

[Steven Johnson]

(In reply to comment #29)
> (From update of attachment 419997 [details] [diff] [review])
> Have you looked through all the affected asm_* functions to see that the x87
> case has been handled?  

Yep, but I missed this one. I'm going to make a second pass. Not sure if there's a good way to restructure the code to make it harder to do incorrectly (at least not without major pain.)

Comment 31

[Steven Johnson]

Attachment: nick's patch, with non-sse2 goodness (v3)

Further inspection shows that it could be possible for an inappropriate call to findMemFor() in asm_arg, and also asm_qlo/asm_qhi (but only if ExprFilter isn't in use)... I can't find a way to trigger these cases in TR, TM, Flash, or lirasm, so the fixes are a bit theoretical.

Comment 32

[Steven Johnson]

http://hg.mozilla.org/projects/nanojit-central/rev/42048199209f

Comment 33

[Steven Johnson]

See https://bugzilla.mozilla.org/show_bug.cgi?id=538000 for an approach that might be useful for hoisting the constants.

Comment 34

[Steven Johnson]

TR: http://hg.mozilla.org/tamarin-redux/rev/ef2d26853c39

Comment 35

[Nicholas Nethercote [inactive]]

http://hg.mozilla.org/tracemonkey/rev/73c2a104de25

Comment 36

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/73c2a104de25