RyuJIT generates redundant code when inlining string.IsNullOrEmpty

[mikedn]

C# code:

static int Main(string[] args) {
    return string.IsNullOrEmpty(args[0]) ? 42 : 0;
}

ASM code:

G_M1504_IG02:
       83790800             cmp      dword ptr [rcx+8], 0
       7628                 jbe      SHORT G_M1504_IG06
       488B4110             mov      rax, gword ptr [rcx+16]
       4885C0               test     rax, rax
       7415                 je       SHORT G_M1504_IG04
       83780800             cmp      dword ptr [rax+8], 0
       0F94C0               sete     al          ; redundant
       0FB6C0               movzx    rax, al     ; redundant
       85C0                 test     eax, eax    ; redundant
       7507                 jne      SHORT G_M1504_IG04
       33C0                 xor      eax, eax

Basically the IL code after inline contains a ceq followed by a brtrue and the JIT compiler doesn't seem capable of folding them.

category:cq
theme:optimization
skill-level:expert
cost:large

[schellap]

Good find.

The problem is we have a side effecting dereference of the array in a dead assignment, which couldn't be removed as a dead store (see below). We should be able to remove this by teaching ValueNumber::GetArrForLenVn($280) how to retrieve the array reference out of a pointer to the first element and in AssertionProp comparing the retrieved reference($80) against the non-null assertion from the bound check (OAK_NO_THROW($80,$40)) to remove the side-effect.

Specifically, this bounds check can be used:

***** BB01, stmt 1 (top level)
     ( 10, 15) [000045] ------------             *  stmtExpr  void  (top level) (IL 0x000...  ???)
N008 (  4,  4) [000003] R--XG-------             |     /--*  indir     ref    <l:$105, c:$280>
N006 (  1,  1) [000054] ------------             |     |  |  /--*  const     long   16 Fseq[#FirstElem] $140
N007 (  3,  3) [000055] -------N----             |     |  \--*  +         byref  <l:$200, c:$240>
N005 (  1,  1) [000047] ------------             |     |     \--*  lclVar    ref    V00 arg0         u:2 (last use) $80
N009 ( 10, 15) [000058] ---XG-------             |  /--*  comma     ref    <l:$107, c:$106>
N004 (  6, 11) [000050] ---X--------             |  |  \--*  arrBndsChk void   $102
N002 (  3,  3) [000049] ---X--------             |  |     +--*  arrLen    int    $c0
N001 (  1,  1) [000001] ------------             |  |     |  \--*  lclVar    ref    V00 arg0         u:2 $80
N003 (  1,  1) [000002] ------------             |  |     \--*  const     int    0 $40
N011 ( 10, 15) [000044] -A-XG---R---             \--*  =         ref    <l:$107, c:$106>
N010 (  1,  1) [000043] D------N----                \--*  lclVar    ref    V02 tmp1         d:2 <l:$105, c:$280>

to eliminate the side-effect (the X flag on the arrLen)

***** BB02, stmt 3 (top level)
     ( 12,  8) [000041] ------------             *  stmtExpr  void  (top level) (IL 0x000...  ???)
N003 (  1,  1) [000037] ------------             |     /--*  const     int    0 $40
N004 (  8,  5) [000038] ---X--------             |  /--*  ==        int    <l:$2c3, c:$2c2>
N002 (  3,  3) [000036] ---X--------             |  |  \--*  arrLen    int    <l:$c2, c:$c1>
N001 (  1,  1) [000035] ------------             |  |     \--*  lclVar    ref    V02 tmp1         u:2 (last use) <l:$105, c:$280>
N006 ( 12,  8) [000040] -A-X----R---             \--*  =         bool   <l:$2c3, c:$2c2>
N005 (  3,  2) [000039] D------N----                \--*  lclVar    int    V01 tmp0         d:3 <l:$2c3, c:$2c2>

And then, given that there is no longer any side-effects post AssertionProp, going into Liveness the dead assignment to V01 can be removed as there is no further "use" anywhere else.

[mikedn]

Sorry but I don't follow. The problem occurs even if no array bound checks are involved:

static bool foobar(int x) {
    return x != 1 && x != 2;
}

static int Main(string[] args) {
    return foobar(args.Length) ? 42 : 0;
}

ASM code:

00007FFC1B234490  mov         eax,dword ptr [rcx+8]  
00007FFC1B234493  cmp         eax,1  
00007FFC1B234496  je          00007FFC1B2344A5  
00007FFC1B234498  cmp         eax,2  
00007FFC1B23449B  setne       al  
00007FFC1B23449E  movzx       eax,al  
00007FFC1B2344A1  test        eax,eax  
00007FFC1B2344A3  jne         00007FFC1B2344A8  
00007FFC1B2344A5  xor         eax,eax  
00007FFC1B2344A7  ret  
00007FFC1B2344A8  mov         eax,2Ah  
00007FFC1B2344AD  ret  

For better clarity here's the expected ASM code:

00007FFC1B234490  mov         eax,dword ptr [rcx+8]  
00007FFC1B234493  cmp         eax,1  
00007FFC1B234496  je          00007FFC1B2344A5  
00007FFC1B234498  cmp         eax,2  
00007FFC1B2344A3  jne         00007FFC1B2344A8  
00007FFC1B2344A5  xor         eax,eax  
00007FFC1B2344A7  ret  
00007FFC1B2344A8  mov         eax,2Ah  
00007FFC1B2344AD  ret

[schellap]

There are two issues here. One is the previous one and the other is because we have the IR as:

bool x = (y != 2);
if (x)

and we end up with redundant code. This should definitely be optimized better -- I will look into this.

[mikedn]

In case anyone cares I stumbled upon a funny workaround:

static bool foobar(int x) {
    return (x != 1 && x != 2) ? true : false;
}
static int Main(string[] args) {
    return foobar(args.Length) ? 42 : 0;
}

00007FFEE1310480  mov         eax,dword ptr [rcx+8]  
00007FFEE1310483  cmp         eax,1  
00007FFEE1310486  je          00007FFEE131048D  
00007FFEE1310488  cmp         eax,2  
00007FFEE131048B  jne         00007FFEE1310490  
00007FFEE131048D  xor         eax,eax  
00007FFEE131048F  ret  
00007FFEE1310490  mov         eax,2Ah  
00007FFEE1310495  ret  

Who'd have thought that more complex C# code will produce better assembly code? 😄

[omariom]

It also happens when a boolean value passed to an inlined method.

[mikedn]

This keeps popping up... let's what the problem is. After inlining we have IR like:

***** BB04, stmt 1
               [000022] ------------              *  STMT      void  (IL 0x000...  ???)
               [000021] ------------              \--*  JTRUE     void  
               [000019] ------------                 |  /--*  CNS_INT   ref    null
               [000020] ------------                 \--*  EQ        int   
               [000001] ------------                    \--*  LCL_VAR   ref    V03 arg3         

------------ BB05 [000..001) -> BB07 (always), preds={} succs={BB07}

***** BB05, stmt 2
               [000037] ------------              *  STMT      void  (IL 0x000...  ???)
               [000033] ------------              |     /--*  CNS_INT   int    0
               [000034] ---X--------              |  /--*  EQ        int   
               [000032] ---X--------              |  |  \--*  ARR_LENGTH int   
               [000031] ------------              |  |     \--*  LCL_VAR   ref    V03 arg3         
               [000036] -A-X--------              \--*  ASG       bool  
               [000035] D------N----                 \--*  LCL_VAR   bool   V07 tmp1         

------------ BB06 [000..001), preds={} succs={BB07}

***** BB06, stmt 3
               [000028] ------------              *  STMT      void  (IL 0x000...  ???)
               [000025] ------------              |  /--*  CAST      int <- bool <- int
               [000024] ------------              |  |  \--*  CNS_INT   int    1
               [000027] -A----------              \--*  ASG       bool  
               [000026] D------N----                 \--*  LCL_VAR   bool   V07 tmp1         

------------ BB07 [???..???) -> BB03 (cond), preds={} succs={BB02,BB03}

***** BB07, stmt 4
               [000009] ------------              *  STMT      void  (IL   ???...  ???)
               [000008] --C---------              \--*  JTRUE     void  
               [000006] ------------                 |  /--*  CNS_INT   int    0
               [000007] --C---------                 \--*  NE        int   
               [000038] ------------                    \--*  LCL_VAR   int    V07 tmp1         

This is pretty bad.
After morphing, before SSA, it's a bit better. The branch node of interest has been duplicated so it's closer to the "detached" relop node:

------------ BB01 [000..008) -> BB04 (cond), preds={} succs={BB02,BB04}

***** BB01, stmt 1
     (  5,  5) [000022] ------------              *  STMT      void  (IL 0x000...  ???)
N004 (  5,  5) [000021] ------------              \--*  JTRUE     void  
N002 (  1,  1) [000019] ------------                 |  /--*  CNS_INT   ref    null
N003 (  3,  3) [000020] J------N----                 \--*  EQ        int   
N001 (  1,  1) [000001] ------------                    \--*  LCL_VAR   ref    V03 arg3         u:1

------------ BB02 [000..001) -> BB06 (cond), preds={BB01} succs={BB03,BB06}

***** BB02, stmt 2
     ( 12,  8) [000037] ------------              *  STMT      void  (IL 0x000...  ???)
N003 (  1,  1) [000033] ------------              |     /--*  CNS_INT   int    0
N004 (  8,  5) [000034] ---X--------              |  /--*  EQ        int   
N002 (  3,  3) [000032] ---X--------              |  |  \--*  ARR_LENGTH int   
N001 (  1,  1) [000031] ------------              |  |     \--*  LCL_VAR   ref    V03 arg3         u:1 (last use)
N006 ( 12,  8) [000036] -A-X----R---              \--*  ASG       bool  
N005 (  3,  2) [000035] D------N----                 \--*  LCL_VAR   int    V07 tmp1         d:2

***** BB02, stmt 3
     (  7,  6) [000044] ------------              *  STMT      void  (IL   ???...  ???)
N004 (  7,  6) [000040] ------------              \--*  JTRUE     void  
N002 (  1,  1) [000043] ------------                 |  /--*  CNS_INT   int    0
N003 (  5,  4) [000041] J------N----                 \--*  NE        int   
N001 (  3,  2) [000042] ------------                    \--*  LCL_VAR   int    V07 tmp1         u:2 (last use)

------------ BB03 [???..???) -> BB05 (always), preds={BB02} succs={BB05}

------------ BB04 [000..001) -> BB06 (cond), preds={BB01} succs={BB05,BB06}

***** BB04, stmt 4
     (  5,  4) [000028] ------------              *  STMT      void  (IL 0x000...  ???)
N001 (  1,  1) [000024] ------------              |  /--*  CNS_INT   int    1
N003 (  5,  4) [000027] -A------R---              \--*  ASG       bool  
N002 (  3,  2) [000026] D------N----                 \--*  LCL_VAR   int    V07 tmp1         d:1

***** BB04, stmt 5
     (  7,  6) [000009] ------------              *  STMT      void  (IL   ???...  ???)
N004 (  7,  6) [000008] ------------              \--*  JTRUE     void  
N002 (  1,  1) [000006] ------------                 |  /--*  CNS_INT   int    0
N003 (  5,  4) [000007] J------N----                 \--*  NE        int   
N001 (  3,  2) [000038] ------------                    \--*  LCL_VAR   int    V07 tmp1         u:1 (last use)

One of the duplicated branch nodes will go away, thanks to VN/assertion propagation that detects that it has a constant operand. The problem is the other branch node, that looks as expected:

***** BB02, stmt 2
     ( 12,  8) [000037] ------------              *  STMT      void  (IL 0x000...  ???)
N003 (  1,  1) [000033] ------------              |     /--*  CNS_INT   int    0 $43
N004 (  8,  5) [000034] ---X--------              |  /--*  EQ        int    $c3
N002 (  3,  3) [000032] ---X--------              |  |  \--*  ARR_LENGTH int    $c1
N001 (  1,  1) [000031] ------------              |  |     \--*  LCL_VAR   ref    V03 arg3         u:1 (last use) $80
N006 ( 12,  8) [000036] -A-X----R---              \--*  ASG       bool   $c3
N005 (  3,  2) [000035] D------N----                 \--*  LCL_VAR   int    V07 tmp1         d:2 $c2

***** BB02, stmt 3
     (  7,  6) [000044] ------------              *  STMT      void  (IL   ???...  ???)
N004 (  7,  6) [000040] ------------              \--*  JTRUE     void  
N002 (  1,  1) [000043] ------------                 |  /--*  CNS_INT   int    0 $43
N003 (  5,  4) [000041] J------N----                 \--*  NE        int    $c4
N001 (  3,  2) [000042] ------------                    \--*  LCL_VAR   int    V07 tmp1         u:2 (last use) $c2

Basically, the relevant relop node remains detached from the branch tree so codegen has to materialize the bool value produced by the relop, instead of just relying on the flags that the relop sets.

One obvious solution is forward substitution. Unfortunately that's not something one can implement overnight.

Still, perhaps some targeted forward substitution can be done, just for this case. The basic ingredient, SSA, already exists. The only potential problem is that it does not track the users of a node so there's no way to know if a node is single use or not. But that's not so difficult to add.

The bigger problem is that this also typically requires some code motion and that's more difficult to do right. We could probably get away with moving only the relop and spilling its (non-constant) operands to lclvars so we don't have to move those as well. That is, if we have

bool b = a.Length == 0;
if (b)

just make it

int l = a.Length;
if (l == 0)

I suppose early prop could be used for something like this. And considering that branch nodes aren't that common (at one point I think I counted ~50,000 in corelib) the impact on throughput should be small.

So if we have

bool b = a.Length == 0;
if (b)

and early prop finds that b has a single use then it's pretty simple:

• retype b to int (it's single-use so that shouldn't be problematic)
• assign a.Length to the retyped variable
• replace that single use of b with b == 0.

This avoids another SSA limitation that the JIT currently has - if you introduce a new lclvar after SSA, there's no mechanism to add it to the SSA graph.

[mikedn]

retype b to int (it's single-use so that shouldn't be problematic)

Yeah, except that it's not also single-def so you have to create a new lclvar. Oh well, let's do that and see how it goes.

Quick and dirty implementation produces this diff:

Total bytes of diff: -7768 (-0.04% of base)
    diff is an improvement.
Top file improvements by size (bytes):
       -1872 : Microsoft.CodeAnalysis.CSharp.dasm (-0.09% of base)
       -1825 : System.Private.CoreLib.dasm (-0.05% of base)
       -1326 : Microsoft.CodeAnalysis.VisualBasic.dasm (-0.06% of base)
       -1165 : System.Private.Xml.dasm (-0.04% of base)
        -302 : System.Private.DataContractSerialization.dasm (-0.04% of base)
38 total files with size differences (38 improved, 0 regressed), 91 unchanged.
Top method regressions by size (bytes):
          33 ( 0.81% of base) : System.Private.Xml.dasm - XmlSerializationWriterILGen:GenerateMembersElement(ref):ref:this
          32 ( 1.35% of base) : Microsoft.CodeAnalysis.VisualBasic.dasm - Binder:ComputeVariableType(ref,ref,ref,ref,byref,byref,ref):ref:this
          16 ( 0.28% of base) : Microsoft.CodeAnalysis.VisualBasic.dasm - AbstractFlowPass`1:VisitTryStatement(ref):ref:this (3 methods)
          13 ( 8.90% of base) : Microsoft.CodeAnalysis.VisualBasic.dasm - SourceMemberContainerTypeSymbol:ComparePartialMethodSignatures(ref,ref):bool:this
           6 ( 1.05% of base) : Microsoft.CodeAnalysis.CSharp.dasm - Binder:ShouldAddWinRTMembersForInterface(ref,ref,ref,ref,ref,ref,ref):bool
Top method improvements by size (bytes):
        -120 (-2.94% of base) : System.Private.DataContractSerialization.dasm - XmlBinaryReader:ReadArray(ref,ref,ref,int,int):int:this (20 methods)
         -80 (-4.84% of base) : System.Private.Xml.dasm - Parser:Parse(ref,int):bool:this
         -72 (-14.72% of base) : System.Private.CoreLib.dasm - PathInternal:NormalizeDirectorySeparators(ref):ref
         -68 (-3.85% of base) : System.Private.CoreLib.dasm - SpanHelpers:SequenceEqual(byref,byref,int):bool (2 methods)
         -62 (-2.31% of base) : System.Text.Encoding.CodePages.dasm - GB18030Encoding:GetChars(long,int,long,int,ref):int:this
Top method regressions by size (percentage):
          13 ( 8.90% of base) : Microsoft.CodeAnalysis.VisualBasic.dasm - SourceMemberContainerTypeSymbol:ComparePartialMethodSignatures(ref,ref):bool:this
           5 ( 4.85% of base) : Microsoft.CodeAnalysis.VisualBasic.dasm - BoundExpressionExtensions:ToStatement(ref):ref
           4 ( 3.51% of base) : System.Private.Xml.dasm - SourceInfo:Equals(ref):bool:this
           5 ( 3.33% of base) : System.Private.Xml.dasm - XmlDoubleSortKey:.ctor(double,ref):this
           4 ( 2.00% of base) : System.Private.Xml.dasm - QilTypeChecker:CheckFilter(ref):ref:this
Top method improvements by size (percentage):
         -56 (-19.38% of base) : System.Private.Xml.dasm - XmlILOptimizerVisitor:IsPrimitiveNumeric(ref):bool:this
         -56 (-19.38% of base) : System.Private.Xml.dasm - XmlILOptimizerVisitor:MatchesContentTest(ref):bool:this
         -19 (-18.63% of base) : System.Private.CoreLib.dasm - Delegate:RemoveAll(ref,ref):ref
          -8 (-17.78% of base) : Microsoft.CodeAnalysis.CSharp.dasm - <>c:<Analyze>b__4_0(struct):bool:this
          -8 (-17.39% of base) : System.Private.Xml.dasm - XPathConvert:SkipWhitespace(long):long
810 total methods with size differences (792 improved, 18 regressed), 112056 unchanged.

Typical diff looks as expected:

        call     Number:TryParseInt32IntegerStyle(struct,int,ref,byref):int
        test     eax, eax
-       sete     al
-       movzx    rax, al
-       test     eax, eax
-       jne      SHORT G_M8084_IG04
+       je       SHORT G_M8084_IG04 
 G_M8084_IG03:
        xor      eax, eax

[mikedn]

Throughput impact of my lousy implementation is practically non-existent: 0.06%. I have pending PRs that save 10 times that.

[mikedn]

Being overly conservative and forwarding only the relop doesn't seem to be necessary. In many cases the SSA def is in the immediately preceding tree so you can just stitch the two trees together without the typical code motion worries. That nearly doubles the diff improvement. Mostly due to containment and/or compare narrowing:

        mov      r14d, dword ptr [rbp-3CH]
-       movzx    rcx, byte  ptr [rdi+59]
-       cmp      ecx, 2
+       cmp      byte  ptr [rdi+59], 2
        jne      SHORT G_M6012_IG06
        mov      rcx, rsi

Also, it's may be worth pointing out that this problem affects float comparisons as well. And in that case the impact is higher due to the increased complexity of float comparison bool result materialization:

        movss    xmm0, dword ptr [rdi+8]
        ucomiss  xmm0, xmm2
-       setpo    al
-       jpe      SHORT G_M23365_IG03
-       sete     al
+       jpe      SHORT G_M23365_IG05
-G_M23365_IG03:
-       movzx    rax, al
-       test     eax, eax
-       je       SHORT G_M23365_IG06
+       jne      SHORT G_M23365_IG05
        movss    xmm0, dword ptr [rdi+12]

Anyway, this seems pretty doable overall. Now I need to figure out how safe is it to rely on SSA use counts computed by SsaBuilder, considering that nothing in the JIT will update these counts once they're computed. But since early prop runs right after SsaBuilder this should probably be fine, so far I haven't encountered any situation where the use count is wrong during early prop.

In the worst case, morphing invoked during early prop could theoretically add new uses. But then morph doesn't quite know about SSA so it's unlikely that it ever does this. At the very least it will need to set the SSA number on new LclVar uses and there's no trace of that.

[mikedn]

Still WIP but good for a discussion, I hope - https://github.com/mikedn/coreclr/commits/relop-subst

cc @AndyAyersMS

Quick summary:

• compute SSA use counts in SSA builder
• traverse basic block list in earlyprop (well, actually right before it) and attempt to do basic forward substitution of JTRUE's relop operands

This reduces FX diff by 14423 bytes (affects some 1600 methods). There are a few regressions as well. The largest one, 150 bytes, is caused by changes in register allocation that somehow increase the frame size. That results in more 32 bit address mode displacements being needed.

Strangely, in the original implementation PIN showed a 0.06% regression and now it shows a 0.2% improvement. I'll have to double check that. Though it's not impossible that doing extra work to simplify the IR ends up resulting in throughput improvement, it seems a bit too good to be true. Anyway, throughput impact is low.

My main concern is that I need to morph the trees and morph could add new SSA uses, at least in theory. That would invalidate the computed use count. But then I don't see morph setting the SSA number on new lclvar nodes anywhere, that would imply that if morph does actually add new uses then we're already in a bad state because existing early prop code does already call morph.

Anyway, if this is a problem then I think there's a simple solution - put statements needing morphing in a list and morph only after earlyprop is complete.