commit 24350b8dcb6db79b73f0d9fa4a9403771477d5f2
author Nicolas Capens <capn@google.com> Sat Nov 21 01:00:55 2020 -0500
committer Nicolas Capens <nicolascapens@google.com> Mon Nov 23 20:09:16 2020 +0000
tree 93988107a402778ae3b2ddeb93140ff3ddff0341
parent 88e698a4f3e35f509ac80d9ffed8a4e0bbe3a85a

Limit the recursion depth of llvm::SelectionDAG::isSplatValue()

This method previously always recursively checked both the left-hand
side and right-hand side of binary operations for splatted (broadcast)
values to determine if the parent DAG node is a splat. For chained
operations, such as the 10,000 adds of the dEQP-VK.spirv_assembly.
instruction.graphics.spirv_ids_abuse.lots_ids_frag/vert tests,
very deep recursion could result in stack overflow.

Like several other SelectionDAG methods, limit the recursion depth to
MaxRecursionDepth (6).

Bug: b/173785481
Change-Id: I22ee0453db7cf1311267291a331ad8fa3b57b1d9
Reviewed-on: https://swiftshader-review.googlesource.com/c/SwiftShader/+/50672
Presubmit-Ready: Nicolas Capens <nicolascapens@google.com>
Reviewed-by: Jason Macnak <natsu@google.com>
Reviewed-by: Antonio Maiorano <amaiorano@google.com>
Tested-by: Jason Macnak <natsu@google.com>

third_party/llvm-10.0/llvm/include/llvm/CodeGen/SelectionDAG.h

diff --git a/third_party/llvm-10.0/llvm/include/llvm/CodeGen/SelectionDAG.h b/third_party/llvm-10.0/llvm/include/llvm/CodeGen/SelectionDAG.h
index 3bfde5b..845c5c1 100644
--- a/third_party/llvm-10.0/llvm/include/llvm/CodeGen/SelectionDAG.h
+++ b/third_party/llvm-10.0/llvm/include/llvm/CodeGen/SelectionDAG.h
@@ -1618,7 +1618,8 @@
   /// for \p DemandedElts.
   ///
   /// NOTE: The function will return true for a demanded splat of UNDEF values.
-  bool isSplatValue(SDValue V, const APInt &DemandedElts, APInt &UndefElts);
+  bool isSplatValue(SDValue V, const APInt &DemandedElts, APInt &UndefElts,
+                    unsigned Depth = 0);
 
   /// Test whether \p V has a splatted value.
   bool isSplatValue(SDValue V, bool AllowUndefs = false);

third_party/llvm-10.0/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

diff --git a/third_party/llvm-10.0/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/third_party/llvm-10.0/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index 313e07b..f1c6794 100644
--- a/third_party/llvm-10.0/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/third_party/llvm-10.0/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -2278,10 +2278,13 @@
 /// isSplatValue - Return true if the vector V has the same value
 /// across all DemandedElts.
 bool SelectionDAG::isSplatValue(SDValue V, const APInt &DemandedElts,
-                                APInt &UndefElts) {
+                                APInt &UndefElts, unsigned Depth) {
   if (!DemandedElts)
     return false; // No demanded elts, better to assume we don't know anything.
 
+  if (Depth >= MaxRecursionDepth)
+      return false;  // Limit search depth.
+
   EVT VT = V.getValueType();
   assert(VT.isVector() && "Vector type expected");
 
@@ -2334,7 +2337,7 @@
       uint64_t Idx = SubIdx->getZExtValue();
       APInt UndefSrcElts;
       APInt DemandedSrc = DemandedElts.zextOrSelf(NumSrcElts).shl(Idx);
-      if (isSplatValue(Src, DemandedSrc, UndefSrcElts)) {
+      if (isSplatValue(Src, DemandedSrc, UndefSrcElts, Depth + 1)) {
         UndefElts = UndefSrcElts.extractBits(NumElts, Idx);
         return true;
       }
@@ -2347,8 +2350,8 @@
     APInt UndefLHS, UndefRHS;
     SDValue LHS = V.getOperand(0);
     SDValue RHS = V.getOperand(1);
-    if (isSplatValue(LHS, DemandedElts, UndefLHS) &&
-        isSplatValue(RHS, DemandedElts, UndefRHS)) {
+    if (isSplatValue(LHS, DemandedElts, UndefLHS, Depth + 1) &&
+        isSplatValue(RHS, DemandedElts, UndefRHS, Depth + 1)) {
       UndefElts = UndefLHS | UndefRHS;
       return true;
     }