llvm dev - Sep 2010 - [LLVMdev] Illegal optimization in LLVM 2.8 during SelectionDAG? (Re: comparison pattern trouble - might be a bug in LLVM 2.8?)

On 29 Sep 2010, at 06:25, Heikki Kultala wrote:
> Our architecture has 1-bit boolean predicate registers.
> 
> I've defined comparison
> 
> 
> def NErrb : InstTCE<(outs I1Regs:$op3), (ins I32Regs:$op1,I32Regs:$op2),
"", [(set I1Regs:$op3, (setne I32Regs:$op1, I32Regs:$op2))]>;
> 
> 
> 
> 
> But then I end up having the following bug:
> 
> 
> Code
> 
> 
>  %0 = zext i8 %data to i32
>  %1 = zext i16 %crc to i32
>  %2 = xor i32 %1, %0
>  %3 = and i32 %2, 1
>  %4 = icmp eq i32 %3, 0
> 
> 
> which compares the lowest bits of the 2 variables
> 
> 
> ends up being compiled as
> 
> 
>        %reg16384<def> = LDWi <fi#-2>, 0; mem:LD4[FixedStack-2]
I32Regs:%reg16384
>        %reg16385<def> = LDWi <fi#-1>, 0; mem:LD4[FixedStack-1]
I32Regs:%reg16385
>        %reg16386<def> = COPY %reg16384; I32Regs:%reg16386,16384
>        %reg16390<def> = NErrb %reg16384, %reg16385; I1Regs:%reg16390
I32Regs:%reg16384,16385
> 
> 
> which just compares ALL BITS of the variables.



I also have a pattern:

def XORrrb : InstTCE<(outs I1Regs:$op3), (ins I32Regs:$op1,I32Regs:$op2),
"", [(set I1Regs:$op3, (trunc (xor I32Regs:$op1, I32Regs:$op2)))]>;

Which can do the whole 3-operation code sequence correctly with one operation.

With LLVM 2.7 this correct operation is selected, with LLVM 2.8 the wrong
operation(which compares all bits) is chosen

So this looks like a bug in LLVM 2.8 isel?

Bill Wendling wrote:
> On Sep 29, 2010, at 12:36 AM, Heikki Kultala wrote:
> 
>> On 29 Sep 2010, at 06:25, Heikki Kultala wrote:
>>
>>> Our architecture has 1-bit boolean predicate registers.
>>>
>>> I've defined comparison
>>>
>>> def NErrb : InstTCE<(outs I1Regs:$op3), (ins
I32Regs:$op1,I32Regs:$op2), "", [(set I1Regs:$op3, (setne
I32Regs:$op1, I32Regs:$op2))]>;
>>>
>>> But then I end up having the following bug:
>>>
>>> Code
>>>
>>> %0 = zext i8 %data to i32
>>> %1 = zext i16 %crc to i32
>>> %2 = xor i32 %1, %0
>>> %3 = and i32 %2, 1
>>> %4 = icmp eq i32 %3, 0
>>>
>>> which compares the lowest bits of the 2 variables
>>> ends up being compiled as
>>>
>>>       %reg16384<def> = LDWi <fi#-2>, 0;
mem:LD4[FixedStack-2] I32Regs:%reg16384
>>>       %reg16385<def> = LDWi <fi#-1>, 0;
mem:LD4[FixedStack-1] I32Regs:%reg16385
>>>       %reg16386<def> = COPY %reg16384;
I32Regs:%reg16386,16384
>>>       %reg16390<def> = NErrb %reg16384, %reg16385;
I1Regs:%reg16390 I32Regs:%reg16384,16385
>>>
>>> which just compares ALL BITS of the variables.
>> I also have a pattern:
>>
>> def XORrrb : InstTCE<(outs I1Regs:$op3), (ins
I32Regs:$op1,I32Regs:$op2), "", [(set I1Regs:$op3, (trunc (xor
I32Regs:$op1, I32Regs:$op2)))]>;
>>
>> Which can do the whole 3-operation code sequence correctly with one
operation.
>>
>> With LLVM 2.7 this correct operation is selected, with LLVM 2.8 the
wrong operation(which compares all bits) is chosen
>>
>> So this looks like a bug in LLVM 2.8 isel?
>>
> Hi Heikki,
> 
> We need a better example of what's going on. What's the original
code? Also, I don't have access to your back-end's code so it's hard
to tell just from these snippets what's going on. For instance, it's not
clear whether it's the instruction selector that's at fault or if your
.td files have a bug in them somewhere.
The original code is:




#include <stdio.h>
typedef unsigned char e_u8;
typedef unsigned short e_u16;
e_u16 Calc_crc8(e_u8 data, e_u16 crc ) __attribute((__noinline__));

e_u16 Calc_crc8(e_u8 data, e_u16 crc )
{
         e_u8 i,x16,carry;

         for (i = 0; i < 2; i++)
             {
                 x16 = (e_u8)(((data) ^ ((e_u8)crc))&1);
                 if (x16 == 1)
                 {
                    crc ^= 0x4002;
                    carry = 1;
                 }
                 else {
                     carry = 0;
                 }
                 if (carry) {
                    crc |= 0x8000;
                 }
                    else {
                    crc &= 0x7fff;
                    }
     }
         return crc;
}

int main(void) {
     char *foo = "foobar";
     volatile short zero = 0;
     volatile int crc = Calc_crc8(foo[0],zero);
/*
#ifdef __TCE__
     iprintf("Crc8 at middle is %d\n", crc);
#else
     printf("Crc8 at middle is %d\n", crc);
#endif
*/
     crc = Calc_crc8(foo[1],crc);
/*
#ifdef __TCE__
     iprintf("Crc8 is %d\n", crc);
#else
     printf("Crc8 is %d\n", crc);
#endif
*/
     if (crc != 32768) {
         putchar('0');
     } else {
         putchar('1');
     }

     putchar('\n');
}

where the interesting lines are lines 12-13:

                 x16 = (e_u8)(((data) ^ ((e_u8)crc))&1);
                 if (x16 == 1)




The code which goes into isel is:

bb.nph:
   %0 = zext i8 %data to i32
   %1 = zext i16 %crc to i32
   %2 = xor i32 %1, %0
   %3 = and i32 %2, 1
   %4 = icmp eq i32 %3, 0
   br i1 %4, label %bb.nph._crit_edge, label %5

inside selectiondag this becomes:




Legalized selection DAG:
SelectionDAG has 21 nodes:
   0x2536968: ch = EntryToken [ORD=1] [ID=0]

   0x248da80: i32 = undef [ORD=1] [ID=2]

       0x263e968: <multiple use>
       0x248db80: i32 = FrameIndex<-1> [ORD=1] [ID=1]

       0x248da80: <multiple use>
     0x248d580: i32,ch = load 0x263e968, 0x248db80, 
0x248da80<LD4[FixedStack-1]> [ORD=1] [ID=10]

     0x248d480: ch = ValueType:i8 [ORD=1] [ID=4]

   0x248d980: i32 = AssertZext 0x248d580, 0x248d480 [ORD=1] [ID=12]

       0x263e968: <multiple use>
       0x248d680: i32 = FrameIndex<-2> [ORD=2] [ID=3]

       0x248da80: <multiple use>
     0x248dc80: i32,ch = load 0x263e968, 0x248d680, 
0x248da80<LD4[FixedStack-2]> [ORD=2] [ID=11]

     0x248d380: ch = ValueType:i16 [ORD=2] [ID=5]

   0x248d280: i32 = AssertZext 0x248dc80, 0x248d380 [ORD=2] [ID=13]

         0x263e968: <multiple use>
         0x248dd80: i32 = Register %reg16384 [ID=6]

         0x248d280: <multiple use>
       0x248de80: ch = CopyToReg 0x263e968, 0x248dd80, 0x248d280 [ID=17]

         0x263e968: <multiple use>
         0x248e080: i32 = Register %reg16385 [ID=7]

         0x248d980: <multiple use>
       0x25bb3f0: ch = CopyToReg 0x263e968, 0x248e080, 0x248d980 [ID=14]

         0x263e968: <multiple use>
         0x25bb5f0: i32 = Register %reg16386 [ID=8]

         0x248d280: <multiple use>
       0x25bb6f0: ch = CopyToReg 0x263e968, 0x25bb5f0, 0x248d280 [ID=16]

     0x25bc0f0: ch = TokenFactor 0x248de80, 0x25bb3f0, 0x25bb6f0 [ID=19]

         0x248d280: <multiple use>
         0x248d980: <multiple use>
       0x25bb7f0: i32 = xor 0x248d280, 0x248d980 [ORD=3] [ID=15]

     0x25bbbf0: i1 = truncate 0x25bb7f0 [ID=18]

     0x25bbff0: ch = BasicBlock< 0x2685718> [ID=9]

   0x25bc1f0: ch = brcond 0x25bc0f0, 0x25bbbf0, 0x25bbff0 [ID=20]



What is interesting is the 5 last lines..

There is xor, then trunc, taking only the lowest bit, and then brcond, 
jumping on condition based on the lowest bit.



This routine then goes to SelectionDAG:Combine() which runs 
DAGCombiner::visitBRCOND().



DAGCombiner::visitBRCOND() has code:

   SDValue N1 = N->getOperand(1);
   SDValue N2 = N->getOperand(2);

...

   SDNode *Trunc = 0;
   if (N1.getOpcode() == ISD::TRUNCATE && N1.hasOneUse()) {
     // Look past truncate.
     Trunc = N1.getNode();
     N1 = N1.getOperand(0);
   }

which just drops the truncate away..
then there is another optimization afterwards..

   // Transform br(xor(x, y)) -> br(x != y)
   // Transform br(xor(xor(x,y), 1)) -> br (x == y)
   if (N1.hasOneUse() && N1.getOpcode() == ISD::XOR) {
     SDNode *TheXor = N1.getNode();
     SDValue Op0 = TheXor->getOperand(0);
     SDValue Op1 = TheXor->getOperand(1);
     if (Op0.getOpcode() == Op1.getOpcode()) {
       // Avoid missing important xor optimizations.
       SDValue Tmp = visitXOR(TheXor);
       if (Tmp.getNode() && Tmp.getNode() != TheXor) {
         DEBUG(dbgs() << "\nReplacing.8 ";
               TheXor->dump(&DAG);
               dbgs() << "\nWith: ";
               Tmp.getNode()->dump(&DAG);
               dbgs() << '\n');
         WorkListRemover DeadNodes(*this);
         DAG.ReplaceAllUsesOfValueWith(N1, Tmp, &DeadNodes);
         removeFromWorkList(TheXor);
         DAG.DeleteNode(TheXor);
         return DAG.getNode(ISD::BRCOND, N->getDebugLoc(),
                            MVT::Other, Chain, Tmp, N2);
       }
     }

     if (Op0.getOpcode() != ISD::SETCC && Op1.getOpcode() != ISD::SETCC)
{
       bool Equal = false;
       if (ConstantSDNode *RHSCI = dyn_cast<ConstantSDNode>(Op0))
         if (RHSCI->getAPIntValue() == 1 && Op0.hasOneUse()
&&
             Op0.getOpcode() == ISD::XOR) {
           TheXor = Op0.getNode();
           Equal = true;
         }

       SDValue NodeToReplace = Trunc ? SDValue(Trunc, 0) : N1;

       EVT SetCCVT = NodeToReplace.getValueType();
       if (LegalTypes)
         SetCCVT = TLI.getSetCCResultType(SetCCVT);
       SDValue SetCC = DAG.getSetCC(TheXor->getDebugLoc(),
                                    SetCCVT,
                                    Op0, Op1,
                                    Equal ? ISD::SETEQ : ISD::SETNE);
       // Replace the uses of XOR with SETCC
       WorkListRemover DeadNodes(*this);
       DAG.ReplaceAllUsesOfValueWith(NodeToReplace, SetCC, &DeadNodes);
       removeFromWorkList(NodeToReplace.getNode());
       DAG.DeleteNode(NodeToReplace.getNode());
       return DAG.getNode(ISD::BRCOND, N->getDebugLoc(),
                          MVT::Other, Chain, SetCC, N2);
     }
   }
}


Which then optimizes the xor into setcc which looks ALL bits, not just 
the lowest bit.




Optimized legalized selection DAG:
SelectionDAG has 21 nodes:
   0x2536968: ch = EntryToken [ORD=1] [ID=0]

   0x2384a70: i32 = undef [ORD=1] [ID=2]

       0x2536968: <multiple use>
       0x2384b70: i32 = FrameIndex<-1> [ORD=1] [ID=1]

       0x2384a70: <multiple use>
     0x2384570: i32,ch = load 0x2536968, 0x2384b70, 
0x2384a70<LD4[FixedStack-1]> [ORD=1] [ID=10]

     0x2384470: ch = ValueType:i8 [ORD=1] [ID=4]

   0x2384970: i32 = AssertZext 0x2384570, 0x2384470 [ORD=1] [ID=12]

       0x2536968: <multiple use>
       0x2384670: i32 = FrameIndex<-2> [ORD=2] [ID=3]

       0x2384a70: <multiple use>
     0x2384c70: i32,ch = load 0x2536968, 0x2384670, 
0x2384a70<LD4[FixedStack-2]> [ORD=2] [ID=11]

     0x2384370: ch = ValueType:i16 [ORD=2] [ID=5]

   0x2384270: i32 = AssertZext 0x2384c70, 0x2384370 [ORD=2] [ID=13]

         0x2536968: <multiple use>
         0x2384d70: i32 = Register %reg16384 [ID=6]

         0x2384270: <multiple use>
       0x2384e70: ch = CopyToReg 0x2536968, 0x2384d70, 0x2384270 [ID=17]

         0x2536968: <multiple use>
         0x2385070: i32 = Register %reg16385 [ID=7]

         0x2384970: <multiple use>
       0x24b33f0: ch = CopyToReg 0x2536968, 0x2385070, 0x2384970 [ID=14]

         0x2536968: <multiple use>
         0x24b35f0: i32 = Register %reg16386 [ID=8]

         0x2384270: <multiple use>
       0x24b36f0: ch = CopyToReg 0x2536968, 0x24b35f0, 0x2384270 [ID=16]

     0x24b40f0: ch = TokenFactor 0x2384e70, 0x24b33f0, 0x24b36f0 [ID=19]

       0x2384270: <multiple use>
       0x2384970: <multiple use>
       0x24b38f0: ch = setne

     0x24b39f0: i1 = setcc 0x2384270, 0x2384970, 0x24b38f0

     0x24b3ff0: ch = BasicBlock< 0x25c5ff8> [ID=9]

   0x24b41f0: ch = brcond 0x24b40f0, 0x24b39f0, 0x24b3ff0 [ID=20]




Here we have lost the information that we are only comparing the lowest 
bits, as the trunc is gone, and the setcc is done with 32-bit 
comparison, comparing all bits.



The way our backend is dynamically generated and loaded from a dynamic 
library into custom executable which also links to llvm makes it a bit 
hard to send a "easy to test" backend package for this situation.