Teach InlineCost to account for a null check which can be folded away

[reames]

Summary

If we have a caller that knows a particular argument can never be null, we can exploit this fact while simplifying values in the inline cost analysis. This has the effect of reducing the cost for inlining when a null check is present in the callee, but the value is known non null in the caller. In particular, any dependent control flow can be discounted from the cost estimate.

Note that this is only adjusting the inline cost analysis. As separate changes, I'm going to add support for propagating the null attribute to the call site. An alternate approach would be the have the inline cost analysis ask a ValueTracking question about the caller's formal argument. Separating this into two pieces using the already existing nonnull attribute seemed preferable.

Does anyone think I need to teach InlineFunction to exploit the attribute in the same way? Or are we willing to assume this will happen correctly after inlining?

[sanjoy]

Minor comment inline. Other than that I don't see any issues with this change, but I also don't know this area of code well enough to LGTM this.

lib/Analysis/IPA/InlineCost.cpp

568 ↗

(On Diff #24065)

There is an Argument::getArgNo.

[reames]

Addressing Sanjoys comment. Thanks! I figured that had to exist, but wasn't finding it on Function. Turns out it was on Argument instead. :)

[reames]

ping.

[chandlerc]

FYI, returning from vacs and travel next week. This will be on my queue.

[reames]

ping

[reames]

ping x3

[reames]

ping x4.

Chandler, I'd really like to commit this, any chance you could take a look?

[reames]

ping x 5 (this has been open for over a month)

[reames]

Two weeks ago, I brought a copy of this review to the social and got review comments from Chandler in person.

He mentioned two minor issues:

1. A helper function should be abstracted for the non-null handling since it now makes up a large part of the function.
2. The comments need to emphasize that this is about accessing attributes at the *callsite* more clearly.

I'm about to upload a patch with both of these addressed.

He also expressed concern over the fact that the CallSite (and thus possibly the caller) was exposed to ICA. His concern wasn't w.r.t. to this change per se, but whether a future change might build on this one in a way which would make caching inline cost analysis in the future more difficult. He stated he needed more time to consider the mater before making up his mind on review feedback.

Chandler - Have you come to any conclusions?

[reames]

Addressing review comments.

[chandlerc]

FWIW, I've spent a *lot* of time thinking about this patch. I'm slowly becoming more OK with it. I still have some concerns, but thinking a lot more about the nature of a call site and how we're using it is making me more comfortable.

Two minor points below I'd like your thoughts on...

lib/Analysis/IPA/InlineCost.cpp

525 ↗

(On Diff #27725)

What do you think about making this a generic wrapper around CS.paramHasAttr rather than a not-null specific wrapper? We should be careful to *always* use this method to query for attributes, and I'm not sure we do today.

537–542 ↗

(On Diff #27725)

Actually, why do we need this at all?

Shouldn't we synthesize a non-null argument attribute given an alloca argument? That would then allow us to propagate it to a non-null parameter attribute if *all* calls have it. That would in turn trip all the optimization opportunities that happen when we *can't* inline. Anyways, somewhat separate from this patch. But if you agree that this should be superfluous, perhaps add a FIXME to remove this code when we DTRT?

Oh no, oh no, never mind. We would still miss cases where we don't re-construct argument attributes on call instructions we've inlined into new callers... There is so much work needed to remove this.

[reames]

Responding to Chandler's questions.

lib/Analysis/IPA/InlineCost.cpp

525 ↗

(On Diff #27725)

I'm not sure what the point of this would be. Are you looking for something to limit access to the CallSite variable? Or something else?

Just to make sure I read your question right, you were asking about a wrapper of the form:
bool CallAnalyzer::hasParamAttr(Value *V, Attributes::AttributeKind Attr)

Right?

(I'm not *opposed* to this; I just don't see the point of the extra abstraction.)

537–542 ↗

(On Diff #27725)

I was with you until your last paragraph where you pointed out a case I hadn't thought of. Just to make sure I'm clear, you concerned about something like this right?
a() { alloca a; b(a ) }
b(ptr) { c(ptr) }
c(ptr) { if ptr != null: do_x() }

With the scheme you proposed, we'd have:
inline b into a
reanalyze b's callsite to c in a
inline c into a

It's the need for the reanalyze step your concerned about right? In particular, whether this could happen within the inliner itself without running additional passes?

[chandlerc]

lib/Analysis/IPA/InlineCost.cpp

525 ↗

(On Diff #27725)

The reason for suggesting this is that it makes it obvious how the next person should query some *other* attribute off of the call site in the CallAnalyzer. It also (IMO) makes it less likely that they'll do so incorrectly.

Essentially, I'm trying to separate the non-null property testing from the callsite attribute querying.

I would probably name it 'isArgumentWithAttribute(Value *V, Attributes::AttributeKind Attr)' or something along those lines.

537–542 ↗

(On Diff #27725)

Yes, exactly.

[reames]

lib/Analysis/IPA/InlineCost.cpp

525 ↗

(On Diff #27725)

I'm fine with this proposal and will upload a patch tomorrow with it done.

p.s. Given I like the removal of copied code the isKnownNonNull extraction resulted in, I plan to keep both.

[davidxl]

A general comment: null check code is pretty common, so this patch will be very useful in those scenarios to get better inline cost estimate.

[reames]

Address review comment by Chandler. Also, rename CS to CandidateCS to reduce ambiguity with common parameter name in the file.

[chandlerc]

Sorry I didn't cycle back to this more quickly. LGTM, thanks for the minor refactorings to make things more clear. I like both the names and the resulting code structure a lot.

llvm/trunk/lib/Analysis/IPA/InlineCost.cpp

class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   const TargetTransformInfo &TTI;
 
   /// The cache of @llvm.assume intrinsics.
   AssumptionCacheTracker *ACT;
 
   // The called function.
   Function &F;
 
+  // The candidate callsite being analyzed. Please do not use this to do
+  // analysis in the caller function; we want the inline cost query to be
+  // easily cacheable. Instead, use the cover function paramHasAttr.
+  CallSite CandidateCS;
+
   int Threshold;
   int Cost;
 
   bool IsCallerRecursive;
   bool IsRecursiveCall;
   bool ExposesReturnsTwice;
   bool HasDynamicAlloca;
   bool ContainsNoDuplicateCall;
class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   void disableSROA(Value *V);
   void accumulateSROACost(DenseMap<Value *, int>::iterator CostIt,
                           int InstructionCost);
   bool isGEPOffsetConstant(GetElementPtrInst &GEP);
   bool accumulateGEPOffset(GEPOperator &GEP, APInt &Offset);
   bool simplifyCallSite(Function *F, CallSite CS);
   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);
+  
+  /// Return true if the given value is known non null within the callee if
+  /// inlined through this particular callsite. 
+  bool isKnownNonNullInCallee(Value *V);
+
   // Custom analysis routines.
   bool analyzeBlock(BasicBlock *BB, SmallPtrSetImpl<const Value *> &EphValues);
 
   // Disable several entry points to the visitor so we don't accidentally use
   // them by declaring but not defining them here.
   void visit(Module *);     void visit(Module &);
   void visit(Function *);   void visit(Function &);
   void visit(BasicBlock *); void visit(BasicBlock &);
class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   bool visitBranchInst(BranchInst &BI);
   bool visitSwitchInst(SwitchInst &SI);
   bool visitIndirectBrInst(IndirectBrInst &IBI);
   bool visitResumeInst(ResumeInst &RI);
   bool visitUnreachableInst(UnreachableInst &I);
 
 public:
   CallAnalyzer(const TargetTransformInfo &TTI, AssumptionCacheTracker *ACT,
-               Function &Callee, int Threshold)
-      : TTI(TTI), ACT(ACT), F(Callee), Threshold(Threshold), Cost(0),
-        IsCallerRecursive(false), IsRecursiveCall(false),
+               Function &Callee, int Threshold, CallSite CSArg)
+    : TTI(TTI), ACT(ACT), F(Callee), CandidateCS(CSArg), Threshold(Threshold),
+        Cost(0), IsCallerRecursive(false), IsRecursiveCall(false),
         ExposesReturnsTwice(false), HasDynamicAlloca(false),
         ContainsNoDuplicateCall(false), HasReturn(false), HasIndirectBr(false),
         HasFrameEscape(false), AllocatedSize(0), NumInstructions(0),
         NumVectorInstructions(0), FiftyPercentVectorBonus(0),
         TenPercentVectorBonus(0), VectorBonus(0), NumConstantArgs(0),
         NumConstantOffsetPtrArgs(0), NumAllocaArgs(0), NumConstantPtrCmps(0),
         NumConstantPtrDiffs(0), NumInstructionsSimplified(0),
         SROACostSavings(0), SROACostSavingsLost(0) {}
bool CallAnalyzer::visitUnaryInstruction(UnaryInstruction &I) {
   }
 
   // Disable any SROA on the argument to arbitrary unary operators.
   disableSROA(Operand);
 
   return false;
 }
 
+bool CallAnalyzer::paramHasAttr(Argument *A, Attribute::AttrKind Attr) {
+  unsigned ArgNo = A->getArgNo();
+  return CandidateCS.paramHasAttr(ArgNo+1, Attr);
+}
+
+bool CallAnalyzer::isKnownNonNullInCallee(Value *V) {
+  // Does the *call site* have the NonNull attribute set on an argument?  We
+  // use the attribute on the call site to memoize any analysis done in the
+  // caller. This will also trip if the callee function has a non-null
+  // parameter attribute, but that's a less interesting case because hopefully
+  // the callee would already have been simplified based on that.
+  if (Argument *A = dyn_cast<Argument>(V))
+    if (paramHasAttr(A, Attribute::NonNull))
+      return true;
+  
+  // Is this an alloca in the caller?  This is distinct from the attribute case
+  // above because attributes aren't updated within the inliner itself and we
+  // always want to catch the alloca derived case.
+  if (isAllocaDerivedArg(V))
+    // We can actually predict the result of comparisons between an
+    // alloca-derived value and null. Note that this fires regardless of
+    // SROA firing.
+    return true;
+  
+  return false;
+}
+
 bool CallAnalyzer::visitCmpInst(CmpInst &I) {
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
   // First try to handle simplified comparisons.
   if (!isa<Constant>(LHS))
     if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
       LHS = SimpleLHS;
   if (!isa<Constant>(RHS))
     if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
if (RHSBase && LHSBase == RHSBase) {
         SimplifiedValues[&I] = C;
         ++NumConstantPtrCmps;
         return true;
       }
     }
   }
 
   // If the comparison is an equality comparison with null, we can simplify it
-  // for any alloca-derived argument.
-  if (I.isEquality() && isa<ConstantPointerNull>(I.getOperand(1)))
-    if (isAllocaDerivedArg(I.getOperand(0))) {
-      // We can actually predict the result of comparisons between an
-      // alloca-derived value and null. Note that this fires regardless of
-      // SROA firing.
-      bool IsNotEqual = I.getPredicate() == CmpInst::ICMP_NE;
-      SimplifiedValues[&I] = IsNotEqual ? ConstantInt::getTrue(I.getType())
-                                        : ConstantInt::getFalse(I.getType());
-      return true;
-    }
-
+  // if we know the value (argument) can't be null
+  if (I.isEquality() && isa<ConstantPointerNull>(I.getOperand(1)) &&
+      isKnownNonNullInCallee(I.getOperand(0))) {
   // Finally check for SROA candidates in comparisons.
   Value *SROAArg;
   DenseMap<Value *, int>::iterator CostIt;
   if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) {
     if (isa<ConstantPointerNull>(I.getOperand(1))) {
       accumulateSROACost(CostIt, InlineConstants::InstrCost);
       return true;
     }
bool CallAnalyzer::visitCallSite(CallSite CS) {
   if (!F)
     return Base::visitCallSite(CS);
 
   // If we have a constant that we are calling as a function, we can peer
   // through it and see the function target. This happens not infrequently
   // during devirtualization and so we want to give it a hefty bonus for
   // inlining, but cap that bonus in the event that inlining wouldn't pan
   // out. Pretend to inline the function, with a custom threshold.
-  CallAnalyzer CA(TTI, ACT, *F, InlineConstants::IndirectCallThreshold);
+  CallAnalyzer CA(TTI, ACT, *F, InlineConstants::IndirectCallThreshold, CS);
   if (CA.analyzeCall(CS)) {
     // We were able to inline the indirect call! Subtract the cost from the
     // bonus we want to apply, but don't go below zero.
     Cost -= std::max(0, InlineConstants::IndirectCallThreshold - CA.getCost());
   }
 
   return Base::visitCallSite(CS);
 }
InlineCost InlineCostAnalysis::getInlineCost(CallSite CS, Function *Callee,
   // marked noinline.
   if (Callee->mayBeOverridden() ||
       Callee->hasFnAttribute(Attribute::NoInline) || CS.isNoInline())
     return llvm::InlineCost::getNever();
 
   DEBUG(llvm::dbgs() << "      Analyzing call of " << Callee->getName()
         << "...\n");
 
-  CallAnalyzer CA(TTIWP->getTTI(*Callee), ACT, *Callee, Threshold);
+  CallAnalyzer CA(TTIWP->getTTI(*Callee), ACT, *Callee, Threshold, CS);
   bool ShouldInline = CA.analyzeCall(CS);
 
   DEBUG(CA.dump());
 
   // Check if there was a reason to force inlining or no inlining.
   if (!ShouldInline && CA.getCost() < CA.getThreshold())
     return InlineCost::getNever();
   if (ShouldInline && CA.getCost() >= CA.getThreshold())

llvm/trunk/test/Transforms/Inline/nonnull.ll

+; RUN: opt -S -inline %s | FileCheck %s
+
+declare void @foo()
+declare void @bar()
+
+define void @callee(i8* %arg) {
+  %cmp = icmp eq i8* %arg, null
+  br i1 %cmp, label %expensive, label %done
+
+; This block is designed to be too expensive to inline.  We can only inline
+; callee if this block is known to be dead.
+expensive:
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  ret void
+
+done:
+  call void @bar()
+  ret void
+}
+
+; Positive test - arg is known non null
+define void @caller(i8* nonnull %arg) {
+; CHECK-LABEL: @caller
+; CHECK: call void @bar()
+  call void @callee(i8* nonnull %arg)
+  ret void
+}
+
+; Negative test - arg is not known to be non null
+define void @caller2(i8* %arg) {
+; CHECK-LABEL: @caller2
+; CHECK: call void @callee(
+  call void @callee(i8* %arg)
+  ret void
+}
+