Subzero. Rematerializes shufflevector instructions.

Subzero. Rematerializes shufflevector instructions.

This CL is a first step towards optimizing vector shuffles in
Subzero.

PNaCl bitcode does not support the shufflevector instruction,
so pnacl-clang emits a series of extractelement/insertelement.
pnacl-llc is then responsible for performing a pattern match
on the output bitcode and rematerialize the shufflevector.

With this CL, we enable shufflevector rematerialization in
Subzero. To keep this CL simple, we introduce no efficient
shufflevector lowering. Instead, we scalarize the
rematerialized instructions.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4136
R=stichnot@chromium.org

Committed: https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a=commit;h=a47c11c7f17022050043d69c0802241e0747a056

[John, 2016-04-20 21:27:54]

jpp@chromium.org changed reviewers:
+ eholk@chromium.org, kschimpf@google.com, sehr@chromium.org,
stichnot@chromium.org

[John, 2016-04-20 21:27:54]

still running presubmit, but

(for t in smoke medium large; do
    for p in arm x86-32 x86-64; do
        ./scons platform=${p} bitcode=1 use_sz=1 -j40 \
            -k --verbose ${t}_tests || exit -1;
    done;
done) && echo "OK"

says OK. :)

[Jim Stichnoth, 2016-04-20 23:43:11]

The CL description should mention that this is only part 1 of the full solution.

Also, this *really* needs tests.  I guess it's OK to defer those to the later
CLs.  I would look to the LLVM lit tests for inspiration.

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.cpp#newcode844
src/IceCfg.cpp:844: // Matching agains undef is not really needed because the
value in Src(0)
against

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.cpp#newcode845
src/IceCfg.cpp:845: // will be totally overwritten. We still enforece it anyways
because the
enforce

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.cpp#newcode846
src/IceCfg.cpp:846: // pnacl toolchain generates the bitcode with it.
PNaCl

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.cpp#newcode849
src/IceCfg.cpp:849: OstreamLocker _(Ctx);
Instead of using OstreamLocker everywhere, you should just call Ctx->lockStr()
and unlockStr() around the entire analysis pass, similar to LinearScan::scan().

(of course, guarded by the Verbose flag, and perhaps wrapping that all up inside
an RAII object)

This way, you won't get the dump output for this pass interleaved with other
threads' dump output.

Of course if you run with -verbose and threads>1, you're gonna have a bad time,
but this will make it slightly less bad.

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.cpp#newcode860
src/IceCfg.cpp:860: // index appear excatly once, this chain is still a
candidate for becoming a
appears exactly

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.cpp#newcode925
src/IceCfg.cpp:925: // operates on at most two different sources, than the
instructions can be
operate

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.cpp#newcode1016
src/IceCfg.cpp:1016: // with the appropriate size, thus avoinding resize()
calls.
avoiding

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.cpp#newcode1066
src/IceCfg.cpp:1066: // on more than two different variables --, we stop the
optimization.
no comma

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.h
File src/IceCfg.h (right):

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.h#newcode209
src/IceCfg.h:209: /// Find clusters of insertelement/extractelements
instructions that can be
extractelement

https://codereview.chromium.org/1897243002/diff/70001/src/IceDefs.h
File src/IceDefs.h (right):

https://codereview.chromium.org/1897243002/diff/70001/src/IceDefs.h#newcode345
src/IceDefs.h:345: IceV_ShufMat = 2 << 25,
1 << 25

https://codereview.chromium.org/1897243002/diff/70001/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/1897243002/diff/70001/src/IceInst.h#newcode922
src/IceInst.h:922: /// ShuffleVector instructions. This represents a shuffle
operation on vector
s/instructions/instruction/
?

https://codereview.chromium.org/1897243002/diff/70001/src/IceInst.h#newcode923
src/IceInst.h:923: /// types. This instruction is not part of the LLVM/PNACL
bitcode: it is
PNaCl

[Jim Stichnoth, 2016-04-20 23:50:26]

https://codereview.chromium.org/1897243002/diff/70001/src/IceDefs.h
File src/IceDefs.h (right):

https://codereview.chromium.org/1897243002/diff/70001/src/IceDefs.h#newcode345
src/IceDefs.h:345: IceV_ShufMat = 2 << 25,
Also, add this to IceClFlags.def ?

[Jim Stichnoth, 2016-04-20 23:52:35]

otherwise lgtm

[John, 2016-04-21 00:02:18]

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.cpp#newcode844
src/IceCfg.cpp:844: // Matching agains undef is not really needed because the
value in Src(0)
On 2016/04/20 23:43:11, stichnot wrote:
> against

Done.

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.cpp#newcode845
src/IceCfg.cpp:845: // will be totally overwritten. We still enforece it anyways
because the
On 2016/04/20 23:43:11, stichnot wrote:
> enforce

Done.

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.cpp#newcode846
src/IceCfg.cpp:846: // pnacl toolchain generates the bitcode with it.
On 2016/04/20 23:43:10, stichnot wrote:
> PNaCl

Done.

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.cpp#newcode849
src/IceCfg.cpp:849: OstreamLocker _(Ctx);
On 2016/04/20 23:43:11, stichnot wrote:
> Instead of using OstreamLocker everywhere, you should just call Ctx->lockStr()
> and unlockStr() around the entire analysis pass, similar to
LinearScan::scan().
> 
> (of course, guarded by the Verbose flag, and perhaps wrapping that all up
inside
> an RAII object)
> 
> This way, you won't get the dump output for this pass interleaved with other
> threads' dump output.
> 
> Of course if you run with -verbose and threads>1, you're gonna have a bad
time,
> but this will make it slightly less bad.

see if the solution works.

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.cpp#newcode860
src/IceCfg.cpp:860: // index appear excatly once, this chain is still a
candidate for becoming a
On 2016/04/20 23:43:10, stichnot wrote:
> appears exactly

Done.

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.cpp#newcode925
src/IceCfg.cpp:925: // operates on at most two different sources, than the
instructions can be
On 2016/04/20 23:43:11, stichnot wrote:
> operate

Done.

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.cpp#newcode1016
src/IceCfg.cpp:1016: // with the appropriate size, thus avoinding resize()
calls.
On 2016/04/20 23:43:11, stichnot wrote:
> avoiding

Done.

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.cpp#newcode1066
src/IceCfg.cpp:1066: // on more than two different variables --, we stop the
optimization.
On 2016/04/20 23:43:11, stichnot wrote:
> no comma

Done.

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.h
File src/IceCfg.h (right):

https://codereview.chromium.org/1897243002/diff/70001/src/IceCfg.h#newcode209
src/IceCfg.h:209: /// Find clusters of insertelement/extractelements
instructions that can be
On 2016/04/20 23:43:11, stichnot wrote:
> extractelement

Done.

https://codereview.chromium.org/1897243002/diff/70001/src/IceDefs.h
File src/IceDefs.h (right):

https://codereview.chromium.org/1897243002/diff/70001/src/IceDefs.h#newcode345
src/IceDefs.h:345: IceV_ShufMat = 2 << 25,
On 2016/04/20 23:43:11, stichnot wrote:
> 1 << 25

Done.

https://codereview.chromium.org/1897243002/diff/70001/src/IceDefs.h#newcode345
src/IceDefs.h:345: IceV_ShufMat = 2 << 25,
On 2016/04/20 23:50:26, stichnot wrote:
> Also, add this to IceClFlags.def ?

Done.

https://codereview.chromium.org/1897243002/diff/70001/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/1897243002/diff/70001/src/IceInst.h#newcode922
src/IceInst.h:922: /// ShuffleVector instructions. This represents a shuffle
operation on vector
On 2016/04/20 23:43:11, stichnot wrote:
> s/instructions/instruction/
> ?

Done.

https://codereview.chromium.org/1897243002/diff/70001/src/IceInst.h#newcode923
src/IceInst.h:923: /// types. This instruction is not part of the LLVM/PNACL
bitcode: it is
On 2016/04/20 23:43:11, stichnot wrote:
> PNaCl

Done.

[John, 2016-04-21 00:07:24]

Description was changed from

==========
Subzero. Rematerializes shufflevector instructions.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4136
==========

to

==========
Subzero. Rematerializes shufflevector instructions.

This CL is a first step towards optimizing vector shuffles in
Subzero.

PNaCl bitcode does not support the shufflevector instruction,
so pnacl-clang emits a series of extractelement/insertelement.
pnacl-llc is then responsible for performing a pattern match
on the output bitcode and rematerialize the shufflevector.

With this CL, we enable shufflevector rematerialization in
Subzero. To keep this CL simple, we introduce no efficient
shufflevector lowering. Instead, we scalarize the
rematerialized instructions.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4136
==========

[Jim Stichnoth, 2016-04-21 00:29:26]

lgtm-er

https://codereview.chromium.org/1897243002/diff/90001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1897243002/diff/90001/src/IceCfg.cpp#newcode988
src/IceCfg.cpp:988: // If a second source was not seeing, then we just make Src1
= Src0 to
seen

https://codereview.chromium.org/1897243002/diff/90001/src/IceCfg.cpp#newcode1024
src/IceCfg.cpp:1024: // To avoid waisting time, we only start the pattern match
at the last
wasting

https://codereview.chromium.org/1897243002/diff/90001/src/IceClFlags.def
File src/IceClFlags.def (right):

https://codereview.chromium.org/1897243002/diff/90001/src/IceClFlags.def#newc...
src/IceClFlags.def:331: "shufflevector rematerialization"),                     
   \
I would capitalize the first letter for consistency with the other options.

[John, 2016-04-21 00:40:51]

https://codereview.chromium.org/1897243002/diff/90001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1897243002/diff/90001/src/IceCfg.cpp#newcode988
src/IceCfg.cpp:988: // If a second source was not seeing, then we just make Src1
= Src0 to
On 2016/04/21 00:29:25, stichnot wrote:
> seen

Done.

https://codereview.chromium.org/1897243002/diff/90001/src/IceCfg.cpp#newcode1024
src/IceCfg.cpp:1024: // To avoid waisting time, we only start the pattern match
at the last
On 2016/04/21 00:29:25, stichnot wrote:
> wasting

Done.

https://codereview.chromium.org/1897243002/diff/90001/src/IceClFlags.def
File src/IceClFlags.def (right):

https://codereview.chromium.org/1897243002/diff/90001/src/IceClFlags.def#newc...
src/IceClFlags.def:331: "shufflevector rematerialization"),                     
   \
On 2016/04/21 00:29:26, stichnot wrote:
> I would capitalize the first letter for consistency with the other options.

Done.

shufflevector is an inst name, so I figured I would keep it lower case, but I
agree with you.

[John, 2016-04-21 12:53:46]

Description was changed from

==========
Subzero. Rematerializes shufflevector instructions.

This CL is a first step towards optimizing vector shuffles in
Subzero.

PNaCl bitcode does not support the shufflevector instruction,
so pnacl-clang emits a series of extractelement/insertelement.
pnacl-llc is then responsible for performing a pattern match
on the output bitcode and rematerialize the shufflevector.

With this CL, we enable shufflevector rematerialization in
Subzero. To keep this CL simple, we introduce no efficient
shufflevector lowering. Instead, we scalarize the
rematerialized instructions.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4136
==========

to

==========
Subzero. Rematerializes shufflevector instructions.

This CL is a first step towards optimizing vector shuffles in
Subzero.

PNaCl bitcode does not support the shufflevector instruction,
so pnacl-clang emits a series of extractelement/insertelement.
pnacl-llc is then responsible for performing a pattern match
on the output bitcode and rematerialize the shufflevector.

With this CL, we enable shufflevector rematerialization in
Subzero. To keep this CL simple, we introduce no efficient
shufflevector lowering. Instead, we scalarize the
rematerialized instructions.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4136
R=stichnot@chromium.org

Committed:
https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a...
==========

[John, 2016-04-21 12:53:47]

Committed patchset #7 (id:110001) manually as
a47c11c7f17022050043d69c0802241e0747a056 (presubmit successful).