[InlineCost] model calls to llvm.is.constant* more carefully

[nickdesaulniers]

Summary

llvm.is.constant* intrinsics are evaluated to 0 or 1 integral values.

A common use case for llvm.is.constant comes from the higher level
builtin_constant_p. A common usage pattern of builtin_constant_p in
the Linux kernel is:

void foo (int bar) {
  if (__builtin_constant_p(bar)) {
    // lots of code that will fold away to a constant.
  } else {
    // a little bit of code, usually a libcall.
  }
}

A minor issue in InlineCost calculations is when bar is _not_ Constant
and still will not be after inlining, we don't discount the true branch
and the inline cost of foo ends up being the cost of both branches
together, rather than just the false branch.

This leads to code like the above where inlining will not help prove bar
Constant, but it still would be beneficial to inline foo, because the
"true" branch is irrelevant from a cost perspective.

For example, IPSCCP can sink a passed constant argument to foo:

const int x = 42;
void bar (void) { foo(x); }

This improves our inlining decisions, and fixes a few head scratching
cases were the disassembly shows a relatively small foo not inlined
into a lone caller.

We could further improve this modeling by tracking whether the argument
to llvm.is.constant* is a parameter of the function, and if inlining
would allow that parameter to become Constant. This idea is noted in a
FIXME comment.

Link: https://github.com/ClangBuiltLinux/linux/issues/1302

[nickdesaulniers]

• cut test size in half by marking hweight_long internal rather than hidden; we don't care about the leaf function

[nickdesaulniers]

• add comment to test about it's intent

[nickdesaulniers]

Looks like I need to fix up a flang and an openmp test:

flang-OldUnit :: Evaluate/intrinsics.test
libarcher :: races/task-dependency.c

[nickdesaulniers]

• rebase; test failures were due to unlucky checkout

[nickdesaulniers]

llvm/lib/Analysis/InlineCost.cpp

1546

auto *C = ...

[nickdesaulniers]

In D111272#3046672, @nickdesaulniers wrote:

• cut test size in half by marking hweight_long internal rather than hidden; we don't care about the leaf function

This had the unintended side effect of giving the callee a significant discount on inline cost LastCallToStaticBonus; I should revert that change. Otherwise I suspect the test is green after BUT ALSO BEFORE (bad) this change.

[nickdesaulniers]

• auto *, aggressive reduce test case size via -inline-threshold, ensure test is red BEFORE patch

[kazu]

Hi Nick,

I really like the idea of evaluating __builin_constant_p. If it evaluates to true, we are all good. Now, if it evaluates to false for now but later evaluates to true after some inlining, the cost may be wrong. Should we worry about that? I am guessing that's OK because statements inside the "then" clause of __builtin_constant_p tend to fold very well in most real world code.

By the way, could we have a shorter test? If we just want to see the effect of __builtin_constant_p being folded to false, two function definitions should suffice like so:

; RUN: opt %s -passes=inline -inline-threshold=20 -S | FileCheck %s

declare void @foo()

define void @callee(i64 %val) {
entry:
  %cond = call i1 @llvm.is.constant.i64(i64 %val)
  br i1 %cond, label %cond.true, label %cond.false

cond.true:                                        ; preds = %entry
; Rack up costs with a couple of function calls so that this function
; gets inlined only when @llvm.is.constant.i64 is folded.  In reality,
; the "then" clause of __builtin_constant_p tends to have statements
; that fold very well, so the cost of the "then" clause is not a huge
; concern.
  call void @foo()
  call void @foo()
  ret void

cond.false:                                       ; preds = %entry
  ret void
}

define void @caller(i64 %val) {
; CHECK-LABEL: @caller(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[COND_I:%.*]] = call i1 @llvm.is.constant.i64(i64 [[VAL:%.*]])
; CHECK-NEXT:    br i1 [[COND_I]], label %[[COND_TRUE_I:.*]], label %[[COND_FALSE_I:.*]]
; CHECK:       [[COND_TRUE_I]]:
; CHECK-NEXT:    call void @foo()
; CHECK-NEXT:    call void @foo()
; CHECK-NEXT:    br label %[[CALLEE_EXIT:.*]]
; CHECK:       [[COND_FALSE_I]]:
; CHECK-NEXT:    br label %[[CALLEE_EXIT]]
; CHECK:       [[CALLEE_EXIT]]:
; CHECK-NEXT:    ret void
entry:
  call void @callee(i64 %val)
  ret void
}

declare i1 @llvm.is.constant.i64(i64)

[nickdesaulniers]

• use @kazu's much more concise test case

[nickdesaulniers]

In D111272#3049590, @kazu wrote:

Hi Nick,

I really like the idea of evaluating __builin_constant_p. If it evaluates to true, we are all good. Now, if it evaluates to false for now but later evaluates to true after some inlining, the cost may be wrong. Should we worry about that? I am guessing that's OK because statements inside the "then" clause of __builtin_constant_p tend to fold very well in most real world code.

Correct; that's what the added FIXME in the code is alluding to. While one could manually construct adversarial examples, I don't expect __builtin_constant_p to be used in other ways in the wild. That said, it would be even more precise to peek and see if inlining would change how __builtin_constant_p would evaluate. I'm not sure yet how to do that in LLVM, but this patch is meant to "be less wrong" when __builtin_constant_p will NEVER be true regardless of inlining AND add a method where we can explore modeling the cost of this builtin/intrinsic more in the future.

Right now, when the parameter to the builtin/intrinsic is "locally not constant" we compute the cost as if it was a runtime libcall, keeping all possible resulting computations. That's super wrong; it's one, or the other. This patch picks one, with a FIXME on how to choose the right one even more precisely.

By the way, could we have a shorter test? If we just want to see the effect of __builtin_constant_p being folded to false, two function definitions should suffice like so:

Thanks, I've adopted your test wholesale.

[kazu]

Correct; that's what the added FIXME in the code is alluding to. While one could manually construct adversarial examples, I don't expect __builtin_constant_p to be used in other ways in the wild. That said, it would be even more precise to peek and see if inlining would change how __builtin_constant_p would evaluate. I'm not sure yet how to do that in LLVM, but this patch is meant to "be less wrong" when __builtin_constant_p will NEVER be true regardless of inlining AND add a method where we can explore modeling the cost of this builtin/intrinsic more in the future.

We could take a max of the "then" and "else clauses, but that's probably an overkill. I agree your patch also serves as a reminder about __builtin_constant_p.

Please see some nit comments about the test.

LGTM. Thanks!

llvm/test/Transforms/Inline/call-intrinsic-is-constant.ll

11

Nit: I understand that you used utils/update_test_checks.py to generate the assertions, but could we hoist out % from the regular expression like so?

%[[COND_TRUE:.*]]

This way, we can say [[COND_TRUE]]: in place of the label. The same applies to COND_FALSE.

Alternatively, you might just drop the assertions for @callee. All the interesting things are happening in @caller.

12

[[COND_TRUE]]:

41

The same comment as above.

[nickdesaulniers]

Thanks for the review; I will post a fix for your latest feedback by EOD.

Right now I'm playing with use-def chains; I suspect that if the operand to @llvm.is.constant.* is not Constant, we can build the list of Arguments from F that the operand depends on, then scan the use-def chains of the corresponding arguments in F to see if they would be Constant (ie. inlining would be beneficial; or more precisely at least we can evaluate @llvm.is.constant.* precisely).

[nickdesaulniers]

• further reduce test case, refine regex matches

[kazu]

Thank you for updating the patch!

[nickdesaulniers]

• rewrite FIXME

[nickdesaulniers]

• remove spurring '/' from comment

[echristo]

I think this makes sense if you want the second review :)

llvm/lib/Analysis/InlineCost.cpp

protected:
   void findDeadBlocks(BasicBlock *CurrBB, BasicBlock *NextBB);
   void disableLoadElimination();
   bool isGEPFree(GetElementPtrInst &GEP);
   bool canFoldInboundsGEP(GetElementPtrInst &I);
   bool accumulateGEPOffset(GEPOperator &GEP, APInt &Offset);
   bool simplifyCallSite(Function *F, CallBase &Call);
   template <typename Callable>
   bool simplifyInstruction(Instruction &I, Callable Evaluate);
+  bool simplifyIntrinsicCallIsConstant(CallBase &CB);
   ConstantInt *stripAndComputeInBoundsConstantOffsets(Value *&V);
 
   /// Return true if the given argument to the function being considered for
   /// inlining has the given attribute set either at the call site or the
   /// function declaration.  Primarily used to inspect call site specific
   /// attributes since these can be more precise than the ones on the callee
   /// itself.
   bool paramHasAttr(Argument *A, Attribute::AttrKind Attr);
bool CallAnalyzer::simplifyInstruction(Instruction &I, Callable Evaluate) {
   }
   auto *C = Evaluate(COps);
   if (!C)
     return false;
   SimplifiedValues[&I] = C;
   return true;
 }
 
+/// Try to simplify a call to llvm.is.constant.
+///
+/// Duplicate the argument checking from CallAnalyzer::simplifyCallSite since
+/// we expect calls of this specific intrinsic to be infrequent.
+///
+/// FIXME: Given that we know CB's parent (F) caller
+/// (CandidateCall->getParent()->getParent()), we might be able to determine
+/// whether inlining F into F's caller would change how the call to
+/// llvm.is.constant would evaluate.
+bool CallAnalyzer::simplifyIntrinsicCallIsConstant(CallBase &CB) {
+  Value *Arg = CB.getArgOperand(0);
+  auto *C = dyn_cast<Constant>(Arg);
+
+  if (!C)
+    C = dyn_cast_or_null<Constant>(SimplifiedValues.lookup(Arg));
+
+  Type *RT = CB.getFunctionType()->getReturnType();
+  SimplifiedValues[&CB] = ConstantInt::get(RT, C ? 1 : 0);
+  return true;
+}
+
 bool CallAnalyzer::visitBitCast(BitCastInst &I) {
   // Propagate constants through bitcasts.
   if (simplifyInstruction(I, [&](SmallVectorImpl<Constant *> &COps) {
         return ConstantExpr::getBitCast(COps[0], I.getType());
       }))
     return true;
 
   // Track base/offsets through casts
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&Call)) {
     case Intrinsic::vastart:
       InitsVargArgs = true;
       return false;
     case Intrinsic::launder_invariant_group:
     case Intrinsic::strip_invariant_group:
       if (auto *SROAArg = getSROAArgForValueOrNull(II->getOperand(0)))
         SROAArgValues[II] = SROAArg;
       return true;
+    case Intrinsic::is_constant:
+      return simplifyIntrinsicCallIsConstant(Call);
     }
   }
 
   if (F == Call.getFunction()) {
     // This flag will fully abort the analysis, so don't bother with anything
     // else.
     IsRecursiveCall = true;
     if (!AllowRecursiveCall)

llvm/test/Transforms/Inline/call-intrinsic-is-constant.ll

+; RUN: opt %s -passes=inline -inline-threshold=20 -S | FileCheck %s
+
+declare i1 @llvm.is.constant.i64(i64)
+declare void @foo()
+
+define void @callee(i64 %val) {
+  %cond = call i1 @llvm.is.constant.i64(i64 %val)
+  br i1 %cond, label %cond.true, label %cond.false
+
+cond.true:
+; Rack up costs with a couple of function calls so that this function
+; gets inlined only when @llvm.is.constant.i64 is folded.  In reality,
+; the "then" clause of __builtin_constant_p tends to have statements
+; that fold very well, so the cost of the "then" clause is not a huge
+; concern.
+  call void @foo()
+  call void @foo()
+  ret void
+
+cond.false:
+  ret void
+}
+
+define void @caller(i64 %val) {
+; CHECK-LABEL: @caller(
+; CHECK-NEXT:    [[COND_I:%.*]] = call i1 @llvm.is.constant.i64(i64 [[VAL:%.*]])
+; CHECK-NEXT:    br i1 [[COND_I]], label %[[COND_TRUE_I:.*]], label %[[COND_FALSE_I:.*]]
+; CHECK:       [[COND_TRUE_I]]:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label %[[CALLEE_EXIT:.*]]
+; CHECK:       [[COND_FALSE_I]]:
+; CHECK-NEXT:    br label %[[CALLEE_EXIT]]
+; CHECK:       [[CALLEE_EXIT]]:
+; CHECK-NEXT:    ret void
+;
+  call void @callee(i64 %val)
+  ret void
+}