[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 ↗

(On Diff #199301)

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,
                                    SDValue &Base, SDValue &Scale,
                                    SDValue &Index, SDValue &Disp,
                                    SDValue &Segment) {
+      assert(!AM.NegateIndex && "Index should have been negated!");
       Base = (AM.BaseType == X86ISelAddressMode::FrameIndexBase)
                  ? CurDAG->getTargetFrameIndex(
                        AM.Base_FrameIndex,
                        TLI->getPointerTy(CurDAG->getDataLayout()))
                  : AM.Base_Reg;
       Scale = getI8Imm(AM.Scale, DL);
       Index = AM.IndexReg;
       // These are 32-bit even in 64-bit mode since RIP-relative offset
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;
 
bool X86DAGToDAGISel::selectAddr(SDNode *Parent, SDValue N, SDValue &Base,
   if (AM.BaseType == X86ISelAddressMode::RegBase) {
     if (!AM.Base_Reg.getNode())
       AM.Base_Reg = CurDAG->getRegister(0, VT);
   }
 
   if (!AM.IndexReg.getNode())
     AM.IndexReg = CurDAG->getRegister(0, VT);
 
+  // Negate the index if needed.
+  if (AM.NegateIndex) {
+    SDLoc dl(N);
+    SDValue Zero = CurDAG->getConstant(0, dl, N.getValueType());
+    SDValue Neg = CurDAG->getNode(ISD::SUB, dl, N.getValueType(), Zero,
+                                  AM.IndexReg);
+    AM.IndexReg = Neg;
+    AM.NegateIndex = false;
+    insertDAGNode(*CurDAG, N, Zero);
+    insertDAGNode(*CurDAG, N, Neg);
+  }
+
   getAddressOperands(AM, SDLoc(N), Base, Scale, Index, Disp, Segment);
   return true;
 }
 
 // We can only fold a load if all nodes between it and the root node have a
 // single use. If there are additional uses, we could end up duplicating the
 // load.
 static bool hasSingleUsesFromRoot(SDNode *Root, SDNode *User) {
bool X86DAGToDAGISel::selectLEAAddr(SDValue N,
 
   if (AM.Disp && (AM.Base_Reg.getNode() || AM.IndexReg.getNode()))
     Complexity++;
 
   // If it isn't worth using an LEA, reject it.
   if (Complexity <= 2)
     return false;
 
+  // Negate the index if needed.
+  if (AM.NegateIndex) {
+    SDLoc dl(N);
+    SDValue Zero = CurDAG->getConstant(0, dl, N.getValueType());
+    SDValue Neg = CurDAG->getNode(ISD::SUB, dl, N.getValueType(), Zero,
+                                  AM.IndexReg);
+    AM.IndexReg = Neg;
+    AM.NegateIndex = false;
+    insertDAGNode(*CurDAG, N, Zero);
+    insertDAGNode(*CurDAG, N, Neg);
+  }
+
   getAddressOperands(AM, DL, Base, Scale, Index, Disp, Segment);
   return true;
 }
 
 /// This is only run on TargetGlobalTLSAddress nodes.
 bool X86DAGToDAGISel::selectTLSADDRAddr(SDValue N, SDValue &Base,
                                         SDValue &Scale, SDValue &Index,
                                         SDValue &Disp, SDValue &Segment) {