[SelectionDAG] CSE nodes with differing SDNodeFlags

[sunfish]

Summary

In the optimizer (GVN etc.) when eliminating redundant nodes with different flags, the flags are ignored for the purposes of testing for congruence, and then intersected for the purposes of producing a result that supports the union of all the uses. Attached is a rough patch which implements the same policy for SelectionDAG's CSE, which fixed the testcases in PR26063 and which I'm posting now to get feedback on the approach.

[hfinkel]

This seems like the most-useful approach (LGTM).

test/CodeGen/ARM/cse-flags.ll

54 ↗

(On Diff #44227)

Please cleanup the unneeded function attributes and metadata.

llvm/trunk/include/llvm/CodeGen/SelectionDAGNodes.h

public:
 
   /// Return a raw encoding of the flags.
   /// This function should only be used to add data to the NodeID value.
   unsigned getRawFlags() const {
     return (NoUnsignedWrap << 0) | (NoSignedWrap << 1) | (Exact << 2) |
     (UnsafeAlgebra << 3) | (NoNaNs << 4) | (NoInfs << 5) |
     (NoSignedZeros << 6) | (AllowReciprocal << 7);
   }
+
+  /// Clear any flags in this flag set that aren't also set in Flags.
+  void intersectWith(const SDNodeFlags *Flags) {
+    NoUnsignedWrap &= Flags->NoUnsignedWrap;
+    NoSignedWrap &= Flags->NoSignedWrap;
+    Exact &= Flags->Exact;
+    UnsafeAlgebra &= Flags->UnsafeAlgebra;
+    NoNaNs &= Flags->NoNaNs;
+    NoInfs &= Flags->NoInfs;
+    NoSignedZeros &= Flags->NoSignedZeros;
+    AllowReciprocal &= Flags->AllowReciprocal;
+  }
 };
 
 /// Represents one node in the SelectionDAG.
 ///
 class SDNode : public FoldingSetNode, public ilist_node<SDNode> {
 private:
   /// The operation that this node performs.
   int16_t NodeType;
for (use_iterator UI = use_begin(), UE = use_end(); UI != UE; ++UI)
         return *UI;
     return nullptr;
   }
 
   /// This could be defined as a virtual function and implemented more simply
   /// and directly, but it is not to avoid creating a vtable for this class.
   const SDNodeFlags *getFlags() const;
 
+  /// Clear any flags in this node that aren't also set in Flags.
+  void intersectFlagsWith(const SDNodeFlags *Flags);
+
   /// Return the number of values defined/returned by this operator.
   unsigned getNumValues() const { return NumValues; }
 
   /// Return the type of a specified result.
   EVT getValueType(unsigned ResNo) const {
     assert(ResNo < NumValues && "Illegal result number!");
     return ValueList[ResNo];
   }

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

 static void AddNodeIDOperands(FoldingSetNodeID &ID,
                               ArrayRef<SDUse> Ops) {
   for (auto& Op : Ops) {
     ID.AddPointer(Op.getNode());
     ID.AddInteger(Op.getResNo());
   }
 }
 
-/// Add logical or fast math flag values to FoldingSetNodeID value.
-static void AddNodeIDFlags(FoldingSetNodeID &ID, unsigned Opcode,
-                           const SDNodeFlags *Flags) {
-  if (!isBinOpWithFlags(Opcode))
-    return;
-
-  unsigned RawFlags = 0;
-  if (Flags)
-    RawFlags = Flags->getRawFlags();
-  ID.AddInteger(RawFlags);
-}
-
-static void AddNodeIDFlags(FoldingSetNodeID &ID, const SDNode *N) {
-  AddNodeIDFlags(ID, N->getOpcode(), N->getFlags());
-}
-
 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
                           SDVTList VTList, ArrayRef<SDValue> OpList) {
   AddNodeIDOpcode(ID, OpC);
   AddNodeIDValueTypes(ID, VTList);
   AddNodeIDOperands(ID, OpList);
 }
 
 /// If this is an SDNode with special info, add this info to the NodeID data.
case ISD::BlockAddress: {
     const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
     ID.AddPointer(BA->getBlockAddress());
     ID.AddInteger(BA->getOffset());
     ID.AddInteger(BA->getTargetFlags());
     break;
   }
   } // end switch (N->getOpcode())
 
-  AddNodeIDFlags(ID, N);
-
   // Target specific memory nodes could also have address spaces to check.
   if (N->isTargetMemoryOpcode())
     ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
 }
 
 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
 /// data.
 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
   if (doNotCSE(N))
     return nullptr;
 
   SDValue Ops[] = { Op };
   FoldingSetNodeID ID;
   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
   AddNodeIDCustom(ID, N);
   SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
+  if (Node)
+    if (const SDNodeFlags *Flags = N->getFlags())
+      Node->intersectFlagsWith(Flags);
   return Node;
 }
 
 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
 /// were replaced with those specified.  If this node is never memoized,
 /// return null, otherwise return a pointer to the slot it would take.  If a
 /// node already exists with these operands, the slot will be non-null.
 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
                                            SDValue Op1, SDValue Op2,
                                            void *&InsertPos) {
   if (doNotCSE(N))
     return nullptr;
 
   SDValue Ops[] = { Op1, Op2 };
   FoldingSetNodeID ID;
   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
   AddNodeIDCustom(ID, N);
   SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
+  if (Node)
+    if (const SDNodeFlags *Flags = N->getFlags())
+      Node->intersectFlagsWith(Flags);
   return Node;
 }
 
 
 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
 /// were replaced with those specified.  If this node is never memoized,
 /// return null, otherwise return a pointer to the slot it would take.  If a
 /// node already exists with these operands, the slot will be non-null.
 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
                                            void *&InsertPos) {
   if (doNotCSE(N))
     return nullptr;
 
   FoldingSetNodeID ID;
   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
   AddNodeIDCustom(ID, N);
   SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
+  if (Node)
+    if (const SDNodeFlags *Flags = N->getFlags())
+      Node->intersectFlagsWith(Flags);
   return Node;
 }
 
 /// getEVTAlignment - Compute the default alignment value for the
 /// given type.
 ///
 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
   Type *Ty = VT == MVT::iPTR ?
SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
 
   // Memoize this node if possible.
   BinarySDNode *N;
   SDVTList VTs = getVTList(VT);
   if (VT != MVT::Glue) {
     SDValue Ops[] = {N1, N2};
     FoldingSetNodeID ID;
     AddNodeIDNode(ID, Opcode, VTs, Ops);
-    AddNodeIDFlags(ID, Opcode, Flags);
     void *IP = nullptr;
-    if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
+    if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
+      if (Flags)
+        E->intersectFlagsWith(Flags);
       return SDValue(E, 0);
+    }
 
     N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
 
     CSEMap.InsertNode(N, IP);
   } else {
     N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
   }
 

 /// getNodeIfExists - Get the specified node if it's already available, or
 /// else return NULL.
 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
                                       ArrayRef<SDValue> Ops,
                                       const SDNodeFlags *Flags) {
   if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
     FoldingSetNodeID ID;
     AddNodeIDNode(ID, Opcode, VTList, Ops);
-    AddNodeIDFlags(ID, Opcode, Flags);
     void *IP = nullptr;
-    if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
+    if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP)) {
+      if (Flags)
+        E->intersectFlagsWith(Flags);
       return E;
     }
+  }
   return nullptr;
 }
 
 /// getDbgValue - Creates a SDDbgValue node.
 ///
 /// SDNode
 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
                                       unsigned R, bool IsIndirect, uint64_t Off,

 }
 
 const SDNodeFlags *SDNode::getFlags() const {
   if (auto *FlagsNode = dyn_cast<BinaryWithFlagsSDNode>(this))
     return &FlagsNode->Flags;
   return nullptr;
 }
 
+void SDNode::intersectFlagsWith(const SDNodeFlags *Flags) {
+  if (auto *FlagsNode = dyn_cast<BinaryWithFlagsSDNode>(this))
+    FlagsNode->Flags.intersectWith(Flags);
+}
+
 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
   assert(N->getNumValues() == 1 &&
          "Can't unroll a vector with multiple results!");
 
   EVT VT = N->getValueType(0);
   unsigned NE = VT.getVectorNumElements();
   EVT EltVT = VT.getVectorElementType();
   SDLoc dl(N);

llvm/trunk/test/CodeGen/ARM/cse-flags.ll

+; RUN: llc -asm-verbose=false < %s | FileCheck %s
+; PR26063
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "armv7--linux-gnueabihf"
+
+; CHECK: .LBB0_1:
+; CHECK-NEXT: bl      f{{$}}
+; CHECK-NEXT: ldrb    r[[T0:[0-9]+]], [r{{[0-9]+}}, #1]!{{$}}
+; CHECK-NEXT: cmp     r{{[0-9]+}}, #1{{$}}
+; CHECK-NEXT: cmpne   r[[T0]], #0{{$}}
+; CHECK-NEXT: bne     .LBB0_1{{$}}
+define i8* @h(i8* readonly %a, i32 %b, i32 %c) {
+entry:
+  %0 = load i8, i8* %a, align 1
+  %tobool4 = icmp ne i8 %0, 0
+  %cmp5 = icmp ne i32 %b, 1
+  %1 = and i1 %cmp5, %tobool4
+  br i1 %1, label %while.body.preheader, label %while.end
+
+while.body.preheader:                             ; preds = %entry
+  br label %while.body
+
+while.body:                                       ; preds = %while.body.preheader, %while.body
+  %a.addr.06 = phi i8* [ %incdec.ptr, %while.body ], [ %a, %while.body.preheader ]
+  %call = tail call i32 bitcast (i32 (...)* @f to i32 ()*)()
+  %incdec.ptr = getelementptr inbounds i8, i8* %a.addr.06, i32 1
+  %2 = load i8, i8* %incdec.ptr, align 1
+  %tobool = icmp ne i8 %2, 0
+  %cmp = icmp ne i32 %call, 1
+  %3 = and i1 %cmp, %tobool
+  br i1 %3, label %while.body, label %while.end.loopexit
+
+while.end.loopexit:                               ; preds = %while.body
+  %incdec.ptr.lcssa = phi i8* [ %incdec.ptr, %while.body ]
+  br label %while.end
+
+while.end:                                        ; preds = %while.end.loopexit, %entry
+  %a.addr.0.lcssa = phi i8* [ %a, %entry ], [ %incdec.ptr.lcssa, %while.end.loopexit ]
+  ret i8* %a.addr.0.lcssa
+}
+
+declare i32 @f(...)

llvm/trunk/test/CodeGen/X86/2014-05-30-CombineAddNSW.ll

-; RUN: llc < %s -march=x86-64 | FileCheck %s
-; CHECK: addl
-
-; The two additions are the same , but have different flags.
-; In theory this code should never be generated by the frontend, but this 
-; tries to test that two identical instructions with two different flags
-; actually generate two different nodes.
-;
-; Normally the combiner would see this condition without the flags 
-; and optimize the result of the sub into a register clear
-; (the final result would be 0). With the different flags though the combiner 
-; needs to keep the add + sub nodes, because the two nodes result as different
-; nodes and so cannot assume that the subtraction of the two nodes
-; generates 0 as result
-define i32 @foo(i32 %a, i32 %b) {
-  %1 = add i32 %a, %b
-  %2 = add nsw i32 %a, %b
-  %3 = sub i32 %1, %2
-  ret i32 %3
-}