Instruction selection gives "LLVM ERROR: Cannot select"

Hello.
     I'm writing a back end for a RISC processor (similar to BPF) with a large SIMD unit.

     I tried in the last days to make llc compile to SIMD code the following LLVM program:
define i32 @foo(i32* %A, i32* %B, i32* %C, i32 %N) #0 {
entry: ;vector.body: ; preds = %vector.body, %vector.body.preheader.split.split
%0 = getelementptr inbounds i32, i32* %A, i64 0 ; i64 %index ; Alex: I guess this is useless, since offset is 0 - but we keep this redundancy
%1 = bitcast i32* %0 to <16 x i32>*
%wide.load = load <16 x i32>, <16 x i32>* %1, align 4
%2 = getelementptr inbounds i32, i32* %B, i64 0 ; i64 %index ; Alex: I guess this is useless, since offset is 0 - but we keep this redundancy
%3 = bitcast i32* %2 to <16 x i32>*
%wide.load17 = load <16 x i32>, <16 x i32>* %3, align 4
%4 = add nsw <16 x i32> %wide.load17, %wide.load

%5 = getelementptr inbounds i32, i32* %C, i64 0
%6 = bitcast i32* %5 to <16 x i32>*
store <16 x i32> %4, <16 x i32>* %6, align 4

%res = load i32, i32* %C, align 4
ret i32 %res
}
!llvm.ident = !{!0}
!0 = !{!"clang version 3.8.0 (trunk 253324)"}
!1 = distinct !{!1, !2}
!2 = !{!"llvm.loop.unroll.disable"}
!3 = distinct !{!3, !4, !5}
!4 = !{!"llvm.loop.vectorize.width", i32 1}
!5 = !{!"llvm.loop.interleave.count", i32 1}
!6 = distinct !{!6, !2}
!7 = distinct !{!7, !4, !5}

     I get the following error:
       LLVM ERROR: Cannot select: t21: ch = store<ST64[%6](align=4)> t20, t19, t6, undef:i64

     I don't understand why because it seems to me store is specified well in [MyTarget]InstrInfo.td .

     Can somebody help with an idea? Myself I will try to debug the code generated with TableGen, implementing the function SelectCode() .

   Best regards,
     Alex

We'd need to see at least the pattern in your .td file. More of the
DAG would also be helpful (try "llc -debug") since we've got not idea
what t20, t19 or t6 are.

About all I can suggest at the moment is following each step of the
"llc -debug" output while it's trying to select this store, referring
to build/lib/Target/MyTarget/MyTargetGenDAGISel.inc. You should be
able to work out which predicate on the way to the instruction you
expected to be used failed, which often makes it obvious what was
wrong with the pattern.

Cheers.

Tim.

Hello, Tim,
     Thank you for your advice.
     Indeed, the problem with "LLVM ERROR: Cannot select" was a false predicate that should have been true. I solved the problem by simply making the C++ function implementing the TableGen predicate used in my store instruction (very similar to the selectIntAddrMSA predicate from the Mips back end) return true instead of false.

     But now I bumped into another serious problem: llc gives segmentation fault while doing instruction select on the store. More exactly, the vector store instruction (very similar to the MSA vector store from Mips) during selection gets modified during the combine or lowering (I guess) and when instruction selection reaches the store it has one input that is NULL (hence the segfault). More exactly, if we use GDB we see that at the i-sel of the store we have:
    ┌──/home/asusu/LLVM/llvm38Nov2016/llvm/include/llvm/CodeGen/SelectionDAGNodes.h
    │858 /// Initialize the operands list of this with N operands.│
    │859 void InitOperands(SDUse *Ops, const SDValue *Vals, unsigned N) {│
    │860 for (unsigned i = 0; i != N; ++i) {│
    │861 Ops[i].setUser(this);│
   >│862 Ops[i].setInitial(Vals[i]);│
    │863 }

  Here N = 4 and the Ops are:
   {Val = {Node = 0x6e5610, ResNo = 0}, User = 0x6e6940, Prev = 0x6e5640, Next = 0x0}
   {Val = {Node = 0x0, ResNo = 0}, User = 0x6e6940, Prev = 0x0, Next = 0x0} <-- THIS IS THE PROBLEM, the reason for segfault. (in frame 2 we do *this, where this is Ops[1])
   {Val = {Node = 0x6e6940, ResNo = 7231040}, User = 0x0, Prev = 0x0, Next = 0x0}
   {Val = {Node = 0x6e6940, ResNo = 7236320}, User = 0x0, Prev = 0x0, Next = 0x0}}
  (gdb) print Vals[1]
$2 = {Node = 0x0, ResNo = 0}
  (gdb) print Vals[2]
$3 = {Node = 0x0, ResNo = 0}
(gdb) print Vals[3]
$4 = {Node = 0x6c18b0, ResNo = 0}

  Before i-sel started, store had as inputs a TokenFactor, an add, a CopyFromReg (I can provide the entire DOT output with -view-isel-dags) and an undef. If we give during i-sel, at InitOperands():
   (gdb) print Ops[0].Val.Node->dump()t19: v8i64 = add t18, t17
        So, Ops[0] is add.

   So, the problem is that after instruction selection of a RET, CopyToReg and TokenFactor I have a messed-up SelectionDAG, with the problems mentioned above for the select instruction that cause the segfault.

   Did anybody encounter a similar problem before?

   Thank you,
     Alex

     I don't understand why because it seems to me store is specified well in
[MyTarget]InstrInfo.td .

     Can somebody help with an idea? Myself I will try to debug the code
generated with TableGen, implementing the function SelectCode() .

     I get the following error:
       LLVM ERROR: Cannot select: t21: ch = store<ST64[%6](align=4)> t20, t19, t6,

undef:i64

Hi Alex,

But now I bumped into another serious problem: llc gives segmentation
fault while doing instruction select on the store.

Are you building with assertions enabled? You can get segfaults still,
but they're much rarer.

Other than that, I'm afraid I don't know what the problem is. If
you've got custom C++ to handle stores in some way, that would be the
first place to look. It seems to be happening while creating a node,
so it's obviously also worth investigating where Ops comes from there.

I can provide the entire DOT output with -view-isel-dags

I'd certainly be willing to look at that file for anything malformed or odd.

Cheers.

Tim.

Hello, Tim,
     I have attached the DOT file of the DAG before instruction selection starts.

     I found that the error with the NULL operand seems to be given by this code from lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp .
2737 case OPC_RecordNode: {
2738 // Remember this node, it may end up being an operand in the pattern.
2739 SDNode *Parent = nullptr;
2740 if (NodeStack.size() > 1)
2741 Parent = NodeStack[NodeStack.size()-2].getNode();
2742 RecordedNodes.push_back(std::make_pair(N, Parent));
2743 continue;
2744 }

   Thank you,
     Alex

dag.foo-19000b_before_instr_sel.dot (3.22 KB)

Hello.
     Just wanted to tell you that I found the bug in my back end.

     Turned out that the problem was that I implemented just as a "return false" the method:
       bool [MyTarget]DAGToDAGISel::selectIntAddrMSA(SDValue Addr, SDValue &Base,
                                               SDValue &Offset) const {
     Note that the Base and Offset arguments are references. And they have to get changed - see the equivalent method in the Mips back end in MipsSEIselDAGToDAG.cpp.
     So, these parameters were not set in my back end's selectIntAddrMSA() method and this was upsetting the DoInstructionSelect().

     I've spent quite a bit of time debugging llc to find the bug - it's not really obvious to find.
     Maybe somebody would be able to improve llc to prevent these kind of errors in the future - I guess Base and Offset can be checked somewhere in the caller chain of selectIntAddrMSA() and have an assert if it is not of the right value.
     Can somebody help with this?

   Best regards,
     Alex