Re: Illegal optimization in LLVM 2.8 during SelectionDAG? (Re: comparison pattern trouble - might be a bug in LLVM 2.8?)
Bill Wendling <wendling <at> apple.com>
2010-10-01 10:35:44 GMT
On Sep 30, 2010, at 2:13 AM, Heikki Kultala wrote:
> 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:
[snip]
> 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:
[snip]
> 0x248d280: <multiple use>
> 0x248d980: <multiple use>
> 0x25bb7f0: i32 = xor 0x248d280, 0x248d980 [ORD=3] [ID=15]
>
> 0x25bbbf0: i1 = truncate 0x25bb7f0 [ID=18]
This truncate is weird to me. If anything, it should be an "and" instruction. I have a feeling that your
back-end is telling instruction selection and the type legalizer that it's okay to replace the normal
"and" with this truncate call, which leads to your troubles later on.
I would suggest running this same code through another back-end to see if there's anything different going
on. For instance, both ARM and X86 keep the "and" around...
-bw
> 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.
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev <at> cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
RSS Feed