[PR20893] Change SelectionDAG's DbgValueMap to have set semantics (NFC)

[aprantl]

Summary

The attached patch changes the DbgValMap to have set semantics, which fixes the excessive memory allocation followed by a crash reported in PR20893. (http://llvm.org/bugs/show_bug.cgi?id=20893)
When SelectionDAG is combining two SDNodes and then merging their DbgValues via DAG.TransferDbgValues(), SelectionDAG::AddDbgValue() doesn't check whether a DbgValue is already in that SDNode's list of DbgValues and happily adds all of them. In cases like the one in the PR, this can lead to a pathological situation where — when dagcombining a long chain of instructions — the SDNode's DbgValMap is growing exponentially.

[dblaikie]

as for testing - assuming these duplicates get deduplicated elsewhere (could you explain where?) then I doubt there's much to test - this is then just a perf optimization, not a change in any semantics. Maybe dumping MI could be testable, but I'm not sure what the dumping options (& whether they're available in non-asserts builds, etc) are like.

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

6180

Could 'Vals' be an actual set of SDDbgValue*s?

Are SDDbgValue*s inherently uniqued such that pointer identity would be sufficient? (or do you need that equality comparison added above? Which could hopefully be adjusted to < comparison (or hashing) for a set-like structure)

[dim]

Just as a remark, this patch seems to work for fixing the OOM issue occuring in certain FreeBSD ports here: http://docs.freebsd.org/cgi/mid.cgi?542105A3.4090507

So it would be nice if it can go in. :-)

[aprantl]

Fred found an even better fix for this.

include/llvm/CodeGen/SelectionDAG.h

 public:
   SDDbgInfo() {}
 
-  void add(SDDbgValue *V, const SDNode *Node, bool isParameter) {
-    if (isParameter) {
-      ByvalParmDbgValues.push_back(V);
-    } else     DbgValues.push_back(V);
-    if (Node)
-      DbgValMap[Node].push_back(V);
-  }
+  void add(SDDbgValue *V, const SDNode *Node, bool isParameter);
 
   void clear() {
     DbgValMap.clear();

lib/CodeGen/SelectionDAG/SDNodeDbgValue.h

   }
 
   // Returns the kind.
-  DbgValueKind getKind() { return kind; }
+  DbgValueKind getKind() const { return kind; }
 
   // Returns the MDNode pointer.
-  MDNode *getMDPtr() { return mdPtr; }
+  MDNode *getMDPtr() const { return mdPtr; }
 
   // Returns the SDNode* for a register ref
-  SDNode *getSDNode() { assert (kind==SDNODE); return u.s.Node; }
+  SDNode *getSDNode() const { assert (kind==SDNODE); return u.s.Node; }
 
   // Returns the ResNo for a register ref
-  unsigned getResNo() { assert (kind==SDNODE); return u.s.ResNo; }
+  unsigned getResNo() const { assert (kind==SDNODE); return u.s.ResNo; }
 
   // Returns the Value* for a constant
-  const Value *getConst() { assert (kind==CONST); return u.Const; }
+  const Value *getConst() const { assert (kind==CONST); return u.Const; }
 
   // Returns the FrameIx for a stack object
-  unsigned getFrameIx() { assert (kind==FRAMEIX); return u.FrameIx; }
+  unsigned getFrameIx() const { assert (kind==FRAMEIX); return u.FrameIx; }
 
   // Returns whether this is an indirect value.
-  bool isIndirect() { return IsIndirect; }
+  bool isIndirect() const { return IsIndirect; }
 
   // Returns the offset.
-  uint64_t getOffset() { return Offset; }
+  uint64_t getOffset() const { return Offset; }
 
   // Returns the DebugLoc.
-  DebugLoc getDebugLoc() { return DL; }
+  DebugLoc getDebugLoc() const { return DL; }
 
   // Returns the SDNodeOrder.  This is the order of the preceding node in the
   // input.
-  unsigned getOrder() { return Order; }
+  unsigned getOrder() const { return Order; }
 
   // setIsInvalidated / isInvalidated - Setter / getter of the "Invalidated"
   // property. A SDDbgValue is invalid if the SDNode that produces the value is
   // deleted.
   void setIsInvalidated() { Invalid = true; }
-  bool isInvalidated() { return Invalid; }
+  bool isInvalidated() const { return Invalid; }
 };
 
+inline bool operator==(const SDDbgValue &a, const SDDbgValue &b) {
+  if (a.getKind() == b.getKind() &&
+      a.getMDPtr() == b.getMDPtr() &&
+      a.isIndirect() == b.isIndirect() &&
+      a.getOffset() == b.getOffset() &&
+      a.getDebugLoc() == b.getDebugLoc() &&
+      a.getOrder() == b.getOrder() &&
+      a.isInvalidated() == b.isInvalidated())
+    switch (a.getKind()) {
+    case SDDbgValue::SDNODE:
+      return a.getSDNode() == b.getSDNode() && a.getResNo() == b.getResNo();
+    case SDDbgValue::CONST:
+      return a.getConst() == b.getConst();
+    case SDDbgValue::FRAMEIX:
+      return a.getFrameIx() == b.getFrameIx();
+    }
+  return false;
+}
+
+  
 } // end llvm namespace
 
 #endif

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

   return DAGSize;
 }
 
+void SDDbgInfo::add(SDDbgValue *V, const SDNode *Node, bool isParameter) {
+  if (isParameter) {
+    ByvalParmDbgValues.push_back(V);
+  } else     DbgValues.push_back(V);
+  if (Node) {
+    auto &Vals = DbgValMap[Node];
+    for (auto *Val : Vals)
+      if (*Val == *V) return;
+    Vals.push_back(V);
+  }
+}
+
 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
 /// value is produced by SD.
 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {