Fix for bug 8281 - Extremely slow assembling and disassembling of ptrtoint

[wecing]

Summary

The current getFoldedSizeOf() implementation uses naive recursion, which could be really slow when the input structure type is too complex.

This issue was first brought up in http://llvm.org/bugs/show_bug.cgi?id=8281; this change fixes it by adding memoization.

[wecing]

Ping.

[jdoerfert]

Could you add the test as well. Also, include the context in the patch. See https://llvm.org/docs/Phabricator.html#phabricator-request-review-web

llvm/lib/IR/LLVMContextImpl.h

1418 ↗

(On Diff #313905)

Documentation missing.

[wecing]

Update implementation to use local cache and add unit tests.

[wecing]

Include more commits.

[wecing]

include all commits.

[wecing]

remove unused include

[wecing]

remove unused cast

[wecing]

update comment

[wecing]

Sorry about the commit spam.

Not sure what would be the best way to set a deadline for the tests, so I made the test run (almost) forever if not properly optimized.
The latest version also changed Cache to be a local map, instead of a shared instance within type context. This allows us to assume the cached result will always have the correct DestTy (it doesn't really make much difference, though).

PTAL, @jdoerfert

[wecing]

ping.

[wecing]

ping... PTAL, @jdoerfert

[jdoerfert]

LGTM, one nit.

llvm/lib/IR/ConstantFold.cpp

359

This looks up Ty in cache twice, you can do it once, e.g., remember the find result.

[wecing]

Avoid redundant map indexing.

[wecing]

diff against main branch

[timshen]

llvm/lib/IR/ConstantFold.cpp

364

This is correct today, but newly added return statements in the future might miss the Cache[Ty] = part.

Do you mind doing the following:

static Constant *getFoldedSizeOfImpl(Type *Ty, Type *DestTy, bool Folded,
                                 DenseMap<Type *, Constant *> &Cache) {
  // The actual implementation, no explicit caching.
  // It recursively calls into getFoldedSizeOf below.
}

static Constant *getFoldedSizeOf(Type *Ty, Type *DestTy, bool Folded,
                                 DenseMap<Type *, Constant *> &Cache) {
  Constant*& V = Cache[Ty];
  if (V == nullptr)
    V = getFoldedSizeOfImpl(...);
  return V;
}

[timshen]

llvm/lib/IR/ConstantFold.cpp

364

Constant*& V = Cache[Ty];
if (V == nullptr)

Actually we should use result = Cache.insert(...); if (result.second) ... instead, since nullptr might be a valid cached value.

[wecing]

llvm/lib/IR/ConstantFold.cpp

364

Thank you @timshen ! I think you made a good point, but your proposal introduces another problem: now within getFoldedSizeOfImpl(), people must be very careful to always call getFoldedSizeOf() instead of getFoldedSizeOfImpl() to get the caching behavior, which is also pretty error-prone.

A better solution might be to create a wrapper type for the Constant *, so getFoldedSizeOf() would be something like:

#define CACHE_VALUE(v) (new cached_val<Constant *>(Cache[Ty] = v))

static cached_val<Constant *> getFoldedSizeOf(..., DenseMap<...> *Cache) {
  ...
  if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
    Constant *N = ConstantInt::get(DestTy, ATy->getNumElements());
    cached_val<Constant *>E = getFoldedSizeOf(ATy->getElementType(), DestTy, true, Cache);
    return CACHE_VALUE(ConstantExpr::getNUWMul(E.value, N));
  }
  ...
}

static Constant *getFoldedSizeOf(...) {
  return getFoldedSizeOf(...).value;
}

But that is obviously an overkill for the problem, so I would rather keep it simple here. WDYT?

[timshen]

llvm/lib/IR/ConstantFold.cpp

364

Yes, I agree that using cached_value would be an overkill. I would say adding a comment about the recursive call target is sufficient.

[wecing]

• add wrapper method for caching

[wecing]

llvm/lib/IR/ConstantFold.cpp

364

I see. Done, PTAL.

[timshen]

Nicely done!

[mstorsjo]

This triggers a failed assert in certain cases, please see https://bugs.llvm.org/show_bug.cgi?id=51232.

[wecing]

Thanks for the report, @mstorsjo . I do not have time to work on this right now, but I am okay with rolling it back as a temporary workaround.

[mstorsjo]

In D6594#2911977, @wecing wrote:

Thanks for the report, @mstorsjo . I do not have time to work on this right now, but I am okay with rolling it back as a temporary workaround.

Oh, ok, thanks for letting me know. What about the other reviewers involved in the patch, @jdoerfert or @timshen, would you have time to look into the bug so we won't have to resort to reverting the patch after it being merged for 5 months?

[mstorsjo]

In D6594#2914348, @mstorsjo wrote:

In D6594#2911977, @wecing wrote:

Thanks for the report, @mstorsjo . I do not have time to work on this right now, but I am okay with rolling it back as a temporary workaround.

Oh, ok, thanks for letting me know. What about the other reviewers involved in the patch, @jdoerfert or @timshen, would you have time to look into the bug so we won't have to resort to reverting the patch after it being merged for 5 months?

FWIW, this was fixed by D107116.

llvm/lib/IR/ConstantFold.cpp

static Constant *ExtractConstantBytes(Constant *C, unsigned ByteStart,
   }
   }
 }
 
 /// Return a ConstantExpr with type DestTy for sizeof on Ty, with any known
 /// factors factored out. If Folded is false, return null if no factoring was
 /// possible, to avoid endlessly bouncing an unfoldable expression back into the
 /// top-level folder.
-static Constant *getFoldedSizeOf(Type *Ty, Type *DestTy, bool Folded) {
+static Constant *getFoldedSizeOf(Type *Ty, Type *DestTy, bool Folded,
+                                 DenseMap<Type *, Constant *> &Cache) {
+  // check for previously generated folded size Constant.
+  if (Cache.find(Ty) != Cache.end())
+    return ConstantExpr::getIntegerCast(Cache[Ty], DestTy, false);
+
   if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
     Constant *N = ConstantInt::get(DestTy, ATy->getNumElements());
-    Constant *E = getFoldedSizeOf(ATy->getElementType(), DestTy, true);
-    return ConstantExpr::getNUWMul(E, N);
+    Constant *E = getFoldedSizeOf(ATy->getElementType(), DestTy, true, Cache);
+    return Cache[Ty] = ConstantExpr::getNUWMul(E, N);
   }
 
   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);
+        return Cache[Ty] = ConstantExpr::getNullValue(DestTy);
       // Check for a struct with all members having the same size.
       Constant *MemberSize =
-        getFoldedSizeOf(STy->getElementType(0), DestTy, true);
+          getFoldedSizeOf(STy->getElementType(0), DestTy, true, Cache);
       bool AllSame = true;
       for (unsigned i = 1; i != NumElems; ++i)
         if (MemberSize !=
-            getFoldedSizeOf(STy->getElementType(i), DestTy, true)) {
+            getFoldedSizeOf(STy->getElementType(i), DestTy, true, Cache)) {
           AllSame = false;
           break;
         }
       if (AllSame) {
         Constant *N = ConstantInt::get(DestTy, NumElems);
-        return ConstantExpr::getNUWMul(MemberSize, N);
+        return Cache[Ty] = ConstantExpr::getNUWMul(MemberSize, N);
       }
     }
 
   // 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),
-                                         PTy->getAddressSpace()),
-                        DestTy, true);
+      return Cache[Ty] = getFoldedSizeOf(
+                 PointerType::get(IntegerType::get(PTy->getContext(), 1),
+                 DestTy, true, Cache);
 
   // If there's no interesting folding happening, bail so that we don't create
   // a constant that looks like it needs folding but really doesn't.
   if (!Folded)
-    return nullptr;
+    return Cache[Ty] = nullptr;
 
   // Base case: Get a regular sizeof expression.
   Constant *C = ConstantExpr::getSizeOf(Ty);
   C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false,
                                                     DestTy, false),
                             C, DestTy);
-  return C;
+  return Cache[Ty] = C;
+}
+
+static Constant *getFoldedSizeOf(Type *Ty, Type *DestTy, bool Folded) {
+  DenseMap<Type *, Constant *> Cache;
+  return getFoldedSizeOf(Ty, DestTy, Folded, Cache);
 }
 
 /// Return a ConstantExpr with type DestTy for alignof on Ty, with any known
 /// factors factored out. If Folded is false, return null if no factoring was
 /// possible, to avoid endlessly bouncing an unfoldable expression back into the
 /// top-level folder.
 static Constant *getFoldedAlignOf(Type *Ty, Type *DestTy, bool Folded) {
   // The alignment of an array is equal to the alignment of the

llvm/test/tools/llvm-as/slow-ptrtoint.ll

+; RUN: llvm-as %s -o - | llvm-dis -o - | FileCheck %s
+
+%0 = type { %1, %1, %1, %1, %1, %1, %1, %1 }
+%1 = type { %2, %2, %2, %2, %2, %2, %2, %2 }
+%2 = type { %3, %3, %3, %3, %3, %3, %3, %3 }
+%3 = type { %4, %4, %4, %4, %4, %4, %4, %4 }
+%4 = type { %5, %5, %5, %5, %5, %5, %5, %5 }
+%5 = type { %6, %6, %6, %6, %6, %6, %6, %6 }
+%6 = type { %7, %7, %7, %7, %7, %7, %7, %7 }
+%7 = type { %8, %8, %8, %8, %8, %8, %8, %8 }
+%8 = type { %9, %9, %9, %9, %9, %9, %9, %9 }
+%9 = type { %10, %10, %10, %10, %10, %10, %10, %10 }
+%10 = type { %11, %11, %11, %11, %11, %11, %11, %11 }
+%11 = type { %12, %12, %12, %12, %12, %12, %12, %12 }
+%12 = type { %13, %13, %13, %13, %13, %13, %13, %13 }
+%13 = type { i32, i32 }
+
+; it would take a naive recursive implementation ~4 days
+; to constant fold the size of %0
+define i64 @f_i64() {
+; CHECK-LABEL: @f_i64
+; CHECK:         ret i64 mul (i64 ptrtoint (i32* getelementptr (i32, i32* null, i32 1) to i64), i64 1099511627776)
+  ret i64 ptrtoint (%0* getelementptr (%0, %0* null, i32 1) to i64)
+}
+
+define i32 @f_i32() {
+; CHECK-LABEL: @f_i32
+; CHECK:         ret i32 mul (i32 ptrtoint (i32* getelementptr (i32, i32* null, i32 1) to i32), i32 -2147483648)
+  ret i32 ptrtoint (%3* getelementptr (%3, %3* null, i32 1) to i32)
+}