[ConstantFolding] Small fix to prevent constant folding having to repeatedly scan operands.

[dmgreen]

Summary

We are seeing a case where after the unroll threshold was increased in
295538, a loop is fully unrolled into very large constant expression
chains. These are recursively scanned, leading to timeouts and hence
failures. This prevents having to rescan already scanned operands.

[dmgreen]

I've put together a little reproducer. The original case was from the preprocessed CSiBE lwip-0.5.3.preproc/src/core/memp.i source file, this shows the same thing going on:

struct ST {
    struct ST* next;
};
static char global[LOOP*sizeof(struct ST)+1];
#define ALIGN(m, y) (m + ((m%y==0) ? 0 : m%y))
void func(void)
{
    struct ST* s = (struct ST*)&global;
    for(int j = 0; j < LOOP; j++) {
        s->next = (struct ST*)ALIGN((unsigned)((char*)s+sizeof(struct ST)), 2);
        s = s->next;
    }
    s->next = 0;
}

Compiling with something like "clang -c simple.c -O3 -DLOOP=X" I get these compile times for various values of LOOP:

10 0.2
12 0.3
14 0.6
16 1.2
18 8.6
20 33.9
22 215.0

[jmolloy]

The original code looks significantly dodgy to me. From a read of the code and the intent, I think your change is right (the original code always added {FoldedC, FoldedC} which is totally bogus).

However, I think a testcase should be possible?

James

[dmgreen]

Hello,

Thanks for taking a look. The only test I could come up with would be one that times out given a high enough LOOP define in the above reproducer. This patch should otherwise be an NFC.

I don't see any other examples of tests we have that are expected to not timeout, but I've come up with something that should, with the patch, compile fine. I'm not sure if it's a great test (without the fix it will just hang) but at least it's something.

Dave

[jmolloy]

Hi David,

I agree that a hanging test is not ideal. However, if it's a choice between that or silently regressing, I'd prefer a hanging test. At least people will *notice* if it starts taking an ice age to complete.

LGTM, but can you double check that the test is actually run? I thought LIT only inspected the top rows for RUN: lines and stopped when it found a non-RUN: line.

James

[sanjoy]

Would a C++ test case (like the ones in unittests/) be better for this?

[dmgreen]

Sorry for the delay, I was obtaining commit access and then busy with a few other things.

Adding a unittest is an interesting idea. I'm not sure if it would be a lot better though, as it would be testing a fairly minor implementation detail of the Constant Folding interface. The results of the constant folding should be the same, it will just be recursively called a lot less. This test case also has the advantage of making sure nothing else causes the same kind of execution time blow-up.

Unless you have any objections, I'll commit this later today. Let me know.
Dave

llvm/trunk/lib/Analysis/ConstantFolding.cpp

for (const Use &NewU : C->operands()) {
     auto *NewC = cast<Constant>(&NewU);
     // Recursively fold the ConstantExpr's operands. If we have already folded
     // a ConstantExpr, we don't have to process it again.
     if (isa<ConstantVector>(NewC) || isa<ConstantExpr>(NewC)) {
       auto It = FoldedOps.find(NewC);
       if (It == FoldedOps.end()) {
         if (auto *FoldedC =
                 ConstantFoldConstantImpl(NewC, DL, TLI, FoldedOps)) {
-          NewC = FoldedC;
           FoldedOps.insert({NewC, FoldedC});
+          NewC = FoldedC;
         } else {
           FoldedOps.insert({NewC, NewC});
         }
       } else {
         NewC = It->second;
       }
     }
     Ops.push_back(NewC);

llvm/trunk/test/Analysis/ConstantFolding/timeout.ll

+; NOTE: This is a timeout test for some O(something silly) constant folding behaviour. It may not be the best test. Providing it finishes, it passes.
+; RUN: opt < %s -O3 -S | FileCheck %s
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "armv8-none-eabi"
+
+%struct.ST = type { %struct.ST* }
+
+@global = internal global [121 x i8] zeroinitializer, align 1
+
+define void @func() #0 {
+;CHECK-LABEL: func
+entry:
+  %s = alloca %struct.ST*, align 4
+  %j = alloca i32, align 4
+  store %struct.ST* bitcast ([121 x i8]* @global to %struct.ST*), %struct.ST** %s, align 4
+  store i32 0, i32* %j, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %0 = load i32, i32* %j, align 4
+  %cmp = icmp slt i32 %0, 30
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %1 = load %struct.ST*, %struct.ST** %s, align 4
+  %2 = bitcast %struct.ST* %1 to i8*
+  %add.ptr = getelementptr inbounds i8, i8* %2, i32 4
+  %3 = ptrtoint i8* %add.ptr to i32
+  %4 = load %struct.ST*, %struct.ST** %s, align 4
+  %5 = bitcast %struct.ST* %4 to i8*
+  %add.ptr1 = getelementptr inbounds i8, i8* %5, i32 4
+  %6 = ptrtoint i8* %add.ptr1 to i32
+  %rem = urem i32 %6, 2
+  %cmp2 = icmp eq i32 %rem, 0
+  br i1 %cmp2, label %cond.true, label %cond.false
+
+cond.true:                                        ; preds = %for.body
+  br label %cond.end
+
+cond.false:                                       ; preds = %for.body
+  %7 = load %struct.ST*, %struct.ST** %s, align 4
+  %8 = bitcast %struct.ST* %7 to i8*
+  %add.ptr3 = getelementptr inbounds i8, i8* %8, i32 4
+  %9 = ptrtoint i8* %add.ptr3 to i32
+  %rem4 = urem i32 %9, 2
+  br label %cond.end
+
+cond.end:                                         ; preds = %cond.false, %cond.true
+  %cond = phi i32 [ 0, %cond.true ], [ %rem4, %cond.false ]
+  %add = add i32 %3, %cond
+  %10 = inttoptr i32 %add to %struct.ST*
+  %11 = load %struct.ST*, %struct.ST** %s, align 4
+  %next = getelementptr inbounds %struct.ST, %struct.ST* %11, i32 0, i32 0
+  store %struct.ST* %10, %struct.ST** %next, align 4
+  %12 = load %struct.ST*, %struct.ST** %s, align 4
+  %next5 = getelementptr inbounds %struct.ST, %struct.ST* %12, i32 0, i32 0
+  %13 = load %struct.ST*, %struct.ST** %next5, align 4
+  store %struct.ST* %13, %struct.ST** %s, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %cond.end
+  %14 = load i32, i32* %j, align 4
+  %inc = add nsw i32 %14, 1
+  store i32 %inc, i32* %j, align 4
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  %15 = load %struct.ST*, %struct.ST** %s, align 4
+  %next6 = getelementptr inbounds %struct.ST, %struct.ST* %15, i32 0, i32 0
+  store %struct.ST* null, %struct.ST** %next6, align 4
+  ret void
+}
+