[DAG, X86] Fix ISel-time node insertion ids

[niravd]

Summary

As in SystemZ backend, correctly propagate node ids when inserting new
unselected nodes into the DAG during instruction Seleciton for X86
target.

Fixes PR36865.

[niravd]

Remove unrelated fixup.

[jyknight]

LG after resolving comment.

llvm/include/llvm/CodeGen/SelectionDAGISel.h

113

Some comments about what these are for would be good to have here.

llvm/include/llvm/CodeGen/SelectionDAGISel.h

public:
   /// IsLegalToFold - Returns true if the specific operand node N of
   /// U can be folded during instruction selection that starts at Root.
   /// FIXME: This is a static member function because the MSP430/X86
   /// targets, which uses it during isel.  This could become a proper member.
   static bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
                             CodeGenOpt::Level OptLevel,
                             bool IgnoreChains = false);
 
+  static void InvalidateNodeId(SDNode *N);
+  static int getUninvalidatedNodeId(SDNode *N);
+
   static void EnforceNodeIdInvariant(SDNode *N);
 
   // Opcodes used by the DAG state machine:
   enum BuiltinOpcodes {
     OPC_Scope,
     OPC_RecordNode,
     OPC_RecordChild0, OPC_RecordChild1, OPC_RecordChild2, OPC_RecordChild3,
     OPC_RecordChild4, OPC_RecordChild5, OPC_RecordChild6, OPC_RecordChild7,

llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

void SelectionDAGISel::EnforceNodeIdInvariant(SDNode *Node) {
   SmallVector<SDNode *, 4> Nodes;
   Nodes.push_back(Node);
 
   while (!Nodes.empty()) {
     SDNode *N = Nodes.pop_back_val();
     for (auto *U : N->uses()) {
       auto UId = U->getNodeId();
       if (UId > 0) {
-        int InvalidatedUId = -UId + 1;
-        U->setNodeId(InvalidatedUId);
+        InvalidateNodeId(U);
         Nodes.push_back(U);
       }
     }
   }
 }
 
+void SelectionDAGISel::InvalidateNodeId(SDNode *N) {
+  int InvalidId = -N->getNodeId() + 1;
+  N->setNodeId(InvalidId);
+}
+
+int SelectionDAGISel::getUninvalidatedNodeId(SDNode *N) {
+  int Id = N->getNodeId();
+  if (Id < 0)
+    return -Id + 1;
+  return Id;
+}
+
 void SelectionDAGISel::DoInstructionSelection() {
   DEBUG(dbgs() << "===== Instruction selection begins: "
                << printMBBReference(*FuncInfo->MBB) << " '"
                << FuncInfo->MBB->getName() << "'\n");
 
   PreprocessISelDAG();
 
   // Select target instructions for the DAG.

llvm/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp

 }
 
 // Insert a node into the DAG at least before Pos.  This will reposition
 // the node as needed, and will assign it a node ID that is <= Pos's ID.
 // Note that this does *not* preserve the uniqueness of node IDs!
 // The selection DAG must no longer depend on their uniqueness when this
 // function is used.
 static void insertDAGNode(SelectionDAG *DAG, SDNode *Pos, SDValue N) {
-  if (N.getNode()->getNodeId() == -1 ||
-      N.getNode()->getNodeId() > Pos->getNodeId()) {
+  if (N->getNodeId() == -1 ||
+      (SelectionDAGISel::getUninvalidatedNodeId(N.getNode()) >
+       SelectionDAGISel::getUninvalidatedNodeId(Pos))) {
     DAG->RepositionNode(Pos->getIterator(), N.getNode());
     // Mark Node as invalid for pruning as after this it may be a successor to a
     // selected node but otherwise be in the same position of Pos.
     // Conservatively mark it with the same -abs(Id) to assure node id
     // invariant is preserved.
-    int PId = Pos->getNodeId();
-    int InvalidatedPId = -(PId + 1);
-    N->setNodeId((PId > 0) ? InvalidatedPId : PId);
+    N->setNodeId(Pos->getNodeId());
+    SelectionDAGISel::InvalidateNodeId(N.getNode());
   }
 }
 
 void SystemZDAGToDAGISel::getAddressOperands(const SystemZAddressingMode &AM,
                                              EVT VT, SDValue &Base,
                                              SDValue &Disp) const {
   Base = AM.Base;
   if (!Base.getNode())

llvm/lib/Target/X86/AsmParser/X86AsmParser.cpp

if (getLexer().is(AsmToken::Percent)) {
       if (IndexReg == X86::RIP) {
         Error(IndexLoc, "%rip is not allowed as an index register");
         return nullptr;
       }
 
       if (getLexer().isNot(AsmToken::RParen)) {
         // Parse the scale amount:
         //  ::= ',' [scale-expression]
-        if (getLexer().isNot(AsmToken::Comma)) {
-          Error(Parser.getTok().getLoc(),
-                "expected comma in scale expression");
+        if (parseToken(AsmToken::Comma, "expected comma in scale expression"))
           return nullptr;
-        }
-        Parser.Lex(); // Eat the comma.
 
         if (getLexer().isNot(AsmToken::RParen)) {
           SMLoc Loc = Parser.getTok().getLoc();
 
           int64_t ScaleVal;
           if (getParser().parseAbsoluteExpression(ScaleVal)){
             Error(Loc, "expected scale expression");
             return nullptr;
if (getLexer().is(AsmToken::Percent)) {
 
       if (Value != 1)
         Warning(Loc, "scale factor without index register is ignored");
       Scale = 1;
     }
   }
 
   // Ok, we've eaten the memory operand, verify we have a ')' and eat it too.
-  if (getLexer().isNot(AsmToken::RParen)) {
-    Error(Parser.getTok().getLoc(), "unexpected token in memory operand");
-    return nullptr;
-  }
   SMLoc MemEnd = Parser.getTok().getEndLoc();
-  Parser.Lex(); // Eat the ')'.
+  if (parseToken(AsmToken::RParen, "unexpected token in memory operand"))
+    return nullptr;
 
   // Check for use of invalid 16-bit registers. Only BX/BP/SI/DI are allowed,
   // and then only in non-64-bit modes. Except for DX, which is a special case
   // because an unofficial form of in/out instructions uses it.
   if (X86MCRegisterClasses[X86::GR16RegClassID].contains(BaseReg) &&
       (is64BitMode() || (BaseReg != X86::BX && BaseReg != X86::BP &&
                          BaseReg != X86::SI && BaseReg != X86::DI)) &&
       BaseReg != X86::DX) {
else if (IDVal == ".cv_fpo_endproc")
     return parseDirectiveFPOEndProc(DirectiveID.getLoc());
 
   return true;
 }
 
 /// parseDirectiveEven
 ///  ::= .even
 bool X86AsmParser::parseDirectiveEven(SMLoc L) {
-  if (getLexer().isNot(AsmToken::EndOfStatement)) {
-    TokError("unexpected token in directive");
-    return false;  
-  }
+  if (parseToken(AsmToken::EndOfStatement, "unexpected token in directive"))
+    return false;
+
   const MCSection *Section = getStreamer().getCurrentSectionOnly();
   if (!Section) {
     getStreamer().InitSections(false);
     Section = getStreamer().getCurrentSectionOnly();
   }
   if (Section->UseCodeAlign())
     getStreamer().EmitCodeAlignment(2, 0);
   else
     getStreamer().EmitValueToAlignment(2, 0, 1, 0);
   return false;
 }
 /// ParseDirectiveWord
 ///  ::= .word [ expression (, expression)* ]
 bool X86AsmParser::ParseDirectiveWord(unsigned Size, SMLoc L) {
-  MCAsmParser &Parser = getParser();
-  if (getLexer().isNot(AsmToken::EndOfStatement)) {
-    for (;;) {
-      const MCExpr *Value;
-      SMLoc ExprLoc = getLexer().getLoc();
-      if (getParser().parseExpression(Value))
-        return false;
-
-      if (const auto *MCE = dyn_cast<MCConstantExpr>(Value)) {
-        assert(Size <= 8 && "Invalid size");
-        uint64_t IntValue = MCE->getValue();
-        if (!isUIntN(8 * Size, IntValue) && !isIntN(8 * Size, IntValue))
-          return Error(ExprLoc, "literal value out of range for directive");
-        getStreamer().EmitIntValue(IntValue, Size);
-      } else {
-        getStreamer().EmitValue(Value, Size, ExprLoc);
-      }
-
-      if (getLexer().is(AsmToken::EndOfStatement))
-        break;
-
-      // FIXME: Improve diagnostic.
-      if (getLexer().isNot(AsmToken::Comma)) {
-        Error(L, "unexpected token in directive");
-        return false;
-      }
-      Parser.Lex();
-    }
-  }
-
-  Parser.Lex();
+  auto parseOp = [&]() -> bool {
+      return true;
+    } else
+  };
+  parseMany(parseOp);
   return false;
 }
 
 /// ParseDirectiveCode
 ///  ::= .code16 | .code32 | .code64
 bool X86AsmParser::ParseDirectiveCode(StringRef IDVal, SMLoc L) {
   MCAsmParser &Parser = getParser();
   Code16GCC = false;

llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

 }
 
 // Insert a node into the DAG at least before the Pos node's position. This
 // will reposition the node as needed, and will assign it a node ID that is <=
 // the Pos node's ID. Note that this does *not* preserve the uniqueness of node
 // IDs! The selection DAG must no longer depend on their uniqueness when this
 // is used.
 static void insertDAGNode(SelectionDAG &DAG, SDValue Pos, SDValue N) {
-  if (N.getNode()->getNodeId() == -1 ||
-      N.getNode()->getNodeId() > Pos.getNode()->getNodeId()) {
-    DAG.RepositionNode(Pos.getNode()->getIterator(), N.getNode());
-    N.getNode()->setNodeId(Pos.getNode()->getNodeId());
+  if (N->getNodeId() == -1 ||
+      (SelectionDAGISel::getUninvalidatedNodeId(N.getNode()) >
+       SelectionDAGISel::getUninvalidatedNodeId(Pos.getNode()))) {
+    DAG.RepositionNode(Pos->getIterator(), N.getNode());
+    // Mark Node as invalid for pruning as after this it may be a successor to a
+    // selected node but otherwise be in the same position of Pos.
+    // Conservatively mark it with the same -abs(Id) to assure node id
+    // invariant is preserved.
+    N->setNodeId(Pos->getNodeId());
+    SelectionDAGISel::InvalidateNodeId(N.getNode());
   }
 }
 
 // Transform "(X >> (8-C1)) & (0xff << C1)" to "((X >> 8) & 0xff) << C1" if
 // safe. This allows us to convert the shift and and into an h-register
 // extract and a scaled index. Returns false if the simplification is
 // performed.
 static bool foldMaskAndShiftToExtract(SelectionDAG &DAG, SDValue N,

llvm/test/CodeGen/X86/pr36865.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple x86_64-unknown-linux-gnu < %s | FileCheck %s
+
+define void @main() {
+; CHECK-LABEL: main:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    subq $424, %rsp # imm = 0x1A8
+; CHECK-NEXT:    .cfi_def_cfa_offset 432
+; CHECK-NEXT:    leaq {{[0-9]+}}(%rsp), %rdi
+; CHECK-NEXT:    xorl %esi, %esi
+; CHECK-NEXT:    movl $400, %edx # imm = 0x190
+; CHECK-NEXT:    callq memset
+; CHECK-NEXT:    movl {{[0-9]+}}(%rsp), %eax
+; CHECK-NEXT:    movl (%rax), %ecx
+; CHECK-NEXT:    addl 0, %eax
+; CHECK-NEXT:    addl %ecx, %eax
+; CHECK-NEXT:    addl %ecx, %eax
+; CHECK-NEXT:    addl {{[0-9]+}}(%rsp), %eax
+; CHECK-NEXT:    movl %eax, {{[0-9]+}}(%rsp)
+; CHECK-NEXT:    movl {{[0-9]+}}(%rsp), %eax
+; CHECK-NEXT:    movl %eax, %ecx
+; CHECK-NEXT:    imull %eax, %ecx
+; CHECK-NEXT:    subl %ecx, %eax
+; CHECK-NEXT:    movl %eax, (%rax)
+entry:
+  %k = alloca i32, align 4
+  %m = alloca i32, align 4
+  %a = alloca [100 x i32], align 16
+  %0 = bitcast [100 x i32]* %a to i8*
+  call void @llvm.memset.p0i8.i64(i8* nonnull align 16 %0, i8 0, i64 400, i1 false)
+  %arrayidx = getelementptr inbounds [100 x i32], [100 x i32]* %a, i64 0, i64 34
+  %add = load i32, i32* %k
+  %1 = load i32, i32* null
+  %2 = load i32, i32* undef
+  %3 = load i32, i32* undef
+  %4 = load i32, i32* %arrayidx
+  %5 = load i32, i32* undef
+  %6 = load i32, i32* undef
+  %7 = load i32, i32* undef
+  %8 = load i32, i32* undef
+  %9 = load i32, i32* undef
+  %10 = load i32, i32* undef
+  %11 = load i32, i32* undef
+  %12 = load i32, i32* undef
+  %13 = load i32, i32* undef
+  %14 = load i32, i32* undef
+  %15 = load i32, i32* undef
+  %16 = load i32, i32* undef
+  %add.1 = add i32 %add, %1
+  %add.2 = add i32 %add.1, %2
+  %add.3 = add i32 %add.2, %3
+  %add.4 = add i32 %add.3, %4
+  store i32 %add.4, i32* %k
+  %17 = load i32, i32* %m
+  %mul = mul i32 %17, %17
+  %sub = sub i32 %17, %mul
+  store i32 %sub, i32* undef
+  unreachable
+}
+
+declare void @llvm.memset.p0i8.i64(i8* nocapture writeonly, i8, i64, i1) #0
+
+attributes #0 = { argmemonly nounwind }