Bug 14070 - Deeply nested struct types cause opt run time to explode

[iid_iunknown]

Summary

PROBLEM

The problem appears on deeply nested structures due to the getFoldedSizeOf implementation (lib/IR/ConstantFold.cpp), which is very ineffective on such data types.

getFoldedSizeOf runs through the structure's fields to find out if all the fields are of the same size. If the function finds they are of different size, it calls ConstantExpr::getSizeOf with the structure type as an argument. ConstantExpr::getSizeOf internally leads to getFoldedSizeOf call that iterates the structure's fields again calculating structure size.

Since getFoldedSizeOf has recursive nature, the number of its calls grows immensely with structure nesting depth increase. E.g., for the attached structure having nesting depth=21 it is called 31719423 times.

PROPOSED SOLUTION

getFoldedSizeOf is doing the same work twice:

1. when iterating the structure's fields to compare field sizes;
2. when finally calling ConstantExpr::getSizeOf to calculate structure size.

The idea is to eliminate the 2nd step and calculate the whole size at the 1st step by summarizing sizes of separate fields.

This solution reduces getFoldedSizeOf calls from over 31M to about 80. The structure is processed in a fraction of a second.

Regression and performance tests show no regression.

[chandlerc]

I suspect Nick is a better reviewer here than I am... The structure of this code makes zero sense to me and I suspect it should be refactored more heavily than just this point fix.... But he would know better.

You should at least fix the formatting errors. Run clang-format over the code maybe?

[chandlerc]

I suspect Nick is a better reviewer here than I am... The structure of this code makes zero sense to me and I suspect it should be refactored more heavily than just this point fix.... But he would know better.

You should at least fix the formatting errors. Run clang-format over the code maybe?

lib/IR/ConstantFold.cpp

static Constant *getFoldedSizeOf(Type *Ty, Type *DestTy,
 
   if (StructType *STy = dyn_cast<StructType>(Ty))
     if (!STy->isPacked()) {
       unsigned NumElems = STy->getNumElements();
       // An empty struct has size zero.
       if (NumElems == 0)
         return ConstantExpr::getNullValue(DestTy);
       // Check for a struct with all members having the same size.
-      Constant *MemberSize =
+      Constant *FirstMemberSize =
         getFoldedSizeOf(STy->getElementType(0), DestTy, true);
+      Constant *StructSize = FirstMemberSize;
+
       bool AllSame = true;
-      for (unsigned i = 1; i != NumElems; ++i)
-        if (MemberSize !=
-            getFoldedSizeOf(STy->getElementType(i), DestTy, true)) {
+      for (unsigned i = 1; i != NumElems; ++i){
+        Constant *MemberSize = getFoldedSizeOf(STy->getElementType(i), DestTy, true);
+        StructSize = ConstantExpr::getNUWAdd(StructSize, MemberSize);
+
+        if (FirstMemberSize != MemberSize){
+          if (!Folded)
+            return nullptr;
+
           AllSame = false;
-          break;
         }
+      }
+
       if (AllSame) {
         Constant *N = ConstantInt::get(DestTy, NumElems);
-        return ConstantExpr::getNUWMul(MemberSize, N);
+        return ConstantExpr::getNUWMul(FirstMemberSize, N);
       }
+
+      return ConstantExpr::getCast(CastInst::getCastOpcode(StructSize, false, DestTy, false), StructSize, DestTy);
     }
 
   // Pointer size doesn't depend on the pointee type, so canonicalize them
   // to an arbitrary pointee.
   if (PointerType *PTy = dyn_cast<PointerType>(Ty))
     if (!PTy->getElementType()->isIntegerTy(1))
       return
         getFoldedSizeOf(PointerType::get(IntegerType::get(PTy->getContext(), 1),