[X86] Delay creating index register negations during address matching until after we know for sure the match will succeed

[craig.topper]

Summary

If we're trying to match an LEA, its possible the LEA match will be deemed unprofitable. In which case the negation we created in matchAddress would be left dangling in the SelectionDAG. This could artificially increase use counts for other nodes in the DAG. Though I don't have an example of that. But it just seems like bad form to have dangling nodes in isel.

[spatel]

llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

267

Can we deal with negation here rather than duplicating code in the callers?

[craig.topper]

llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

267

We're missing the address root we would need for the insertDAGNode calls, but I can add it.

[craig.topper]

-Move into getAddressOperands.
-Emit the NEG machine directly as I'm not sure I trust accessing N at this point in the code to use insertDAGNode. N can be changed by CSEing and other DAG modifications that can occur during address matching.
-Add -pre-RA-sched=linearize to one test that would fail previously due to the dangling sub node getting left behind when LEA costing failed.

[RKSimon]

Is PR39452 related to this?

[craig.topper]

In D61047#1500367, @RKSimon wrote:

Is PR39452 related to this?

I don't think so. I was tracking other ways to trigger the assert from PR22614.

[spatel]

LGTM

llvm/test/CodeGen/X86/imul.ll

6

Is it worth doing FileCheck on this run too? Either it's the same as the others or different in some way that is interesting?

llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

struct X86ISelAddressMode {
     const GlobalValue *GV;
     const Constant *CP;
     const BlockAddress *BlockAddr;
     const char *ES;
     MCSymbol *MCSym;
     int JT;
     unsigned Align;    // CP alignment.
     unsigned char SymbolFlags;  // X86II::MO_*
+    bool NegateIndex = false;
 
     X86ISelAddressMode()
         : BaseType(RegBase), Base_FrameIndex(0), Scale(1), IndexReg(), Disp(0),
           Segment(), GV(nullptr), CP(nullptr), BlockAddr(nullptr), ES(nullptr),
           MCSym(nullptr), JT(-1), Align(0), SymbolFlags(X86II::MO_NO_FLAG) {}
 
     bool hasSymbolicDisplacement() const {
       return GV != nullptr || CP != nullptr || ES != nullptr ||
void dump(SelectionDAG *DAG = nullptr) {
       if (Base_Reg.getNode())
         Base_Reg.getNode()->dump(DAG);
       else
         dbgs() << "nul\n";
       if (BaseType == FrameIndexBase)
         dbgs() << " Base.FrameIndex " << Base_FrameIndex << '\n';
       dbgs() << " Scale " << Scale << '\n'
              << "IndexReg ";
+      if (NegateIndex)
+        dbgs() << "negate ";
       if (IndexReg.getNode())
         IndexReg.getNode()->dump(DAG);
       else
         dbgs() << "nul\n";
       dbgs() << " Disp " << Disp << '\n'
              << "GV ";
       if (GV)
         GV->dump();
bool SelectInlineAsmMemoryOperand(const SDValue &Op,
                                       std::vector<SDValue> &OutOps) override;
 
     void emitSpecialCodeForMain();
 
     inline void getAddressOperands(X86ISelAddressMode &AM, const SDLoc &DL,
                                    MVT VT, SDValue &Base, SDValue &Scale,
                                    SDValue &Index, SDValue &Disp,
                                    SDValue &Segment) {
       if (AM.BaseType == X86ISelAddressMode::FrameIndexBase)
         Base = CurDAG->getTargetFrameIndex(
             AM.Base_FrameIndex, TLI->getPointerTy(CurDAG->getDataLayout()));
       else if (AM.Base_Reg.getNode())
         Base = AM.Base_Reg;
       else
         Base = CurDAG->getRegister(0, VT);
 
       Scale = getI8Imm(AM.Scale, DL);
 
+      // Negate the index if needed.
+      if (AM.NegateIndex) {
+        unsigned NegOpc = VT == MVT::i64 ? X86::NEG64r : X86::NEG32r;
+        SDValue Neg = SDValue(CurDAG->getMachineNode(NegOpc, DL, VT, MVT::i32,
+                                                     AM.IndexReg), 0);
+        AM.IndexReg = Neg;
+      }
+
       if (AM.IndexReg.getNode())
         Index = AM.IndexReg;
       else
         Index = CurDAG->getRegister(0, VT);
 
       // These are 32-bit even in 64-bit mode since RIP-relative offset
       // is 32-bit.
       if (AM.GV)
if ((AM.hasSymbolicDisplacement() && !Backup.hasSymbolicDisplacement()) +
       --Cost;
     // If it doesn't look like it may be an overall win, don't do it.
     if (Cost >= 0) {
       AM = Backup;
       break;
     }
 
     // Ok, the transformation is legal and appears profitable. Go for it.
-    SDValue Zero = CurDAG->getConstant(0, dl, N.getValueType());
-    SDValue Neg = CurDAG->getNode(ISD::SUB, dl, N.getValueType(), Zero, RHS);
-    AM.IndexReg = Neg;
+    // Negation will be emitted later to avoid creating dangling nodes if this
+    // was an unprofitable LEA.
+    AM.IndexReg = RHS;
+    AM.NegateIndex = true;
     AM.Scale = 1;
-
-    // Insert the new nodes into the topological ordering.
-    insertDAGNode(*CurDAG, N, Zero);
-    insertDAGNode(*CurDAG, N, Neg);
     return false;
   }
 
   case ISD::ADD:
     if (!matchAdd(N, AM, Depth))
       return false;
     break;
 

llvm/test/CodeGen/X86/imul.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-pc-linux-gnu | FileCheck %s --check-prefix=X64
 ; RUN: llc < %s -mtriple=x86_64-pc-linux-gnux32 | FileCheck %s --check-prefix=X64
 ; RUN: llc < %s -mtriple=i686-pc-linux | FileCheck %s --check-prefix=X86
+; At least one of the test cases in here crashed when linearizing the DAG.
+; RUN: llc < %s -mtriple=x86_64-pc-linux-gnu -pre-RA-sched=linearize
 
 define i32 @mul4_32(i32 %A) {
 ; X64-LABEL: mul4_32:
 ; X64:       # %bb.0:
 ; X64-NEXT:    # kill: def $edi killed $edi def $rdi
 ; X64-NEXT:    leal (,%rdi,4), %eax
 ; X64-NEXT:    retq
 ;