[InlineCost] Adjust inlining cost for implicit null checks

[reames]

Summary

Implicit null check is a mechanism that fold null pointer checks into nearby memory operations. It simply means that for null pointer comparisons, the execution will unconditionally fall through the non-null branch and let the load of the pointer handle the false case (it can use store instruction as well but LLVM currently only supports load instruction). For more information, please refer http://llvm.org/docs/FaultMaps.html

Because implicit null checks act as unconditional branches, their inlining cost should be free.

[dblaikie]

Test case?

[reames]

lib/Analysis/InlineCost.cpp

622

It looks like this might be a partial diff? I don't see any changes in visitBranchInst?

[• chenli]

lib/Analysis/InlineCost.cpp

622

Apparently I uploaded the wrong diff. Will update soon.

[• chenli]

Update patch and test case.

[reames]

A a meta level, I feel this this patch is approaching the icmp part the wrong way. Rather than trying to determine if a particular comparison is a implicit null check, we should check to see if a particular *branch* is likely implicit and if so, discount the cost of both the branch and the icmp. I'm also not sure it's far to entirely discount the cost of both. We can't from the IR guarantee that the check will actually be made implicit.

Also, can you add a bit of context to your description of the change? I know what an implicit null check is, but not everyone will.

Chandler, since you're sure to have strong opinions, what do you feel is the right approach for framing this?

[• chenli]

In D13088#252355, @reames wrote:

A a meta level, I feel this this patch is approaching the icmp part the wrong way. Rather than trying to determine if a particular comparison is a implicit null check, we should check to see if a particular *branch* is likely implicit and if so, discount the cost of both the branch and the icmp. I'm also not sure it's far to entirely discount the cost of both. We can't from the IR guarantee that the check will actually be made implicit.

I dont feel like the icmp part should be handled in visitBranch. My reasoning is that the icmp might have other user as well. You should not treat it as free if only one of the users is implicit null check. You need to know all its users to decide whether it can be free. That's why I put the check in visitCmp instead of visitBranch.

I agree that it might not be proper to entirely discount the cost as there're chances the lowering part cannot make it implicit. I'd very like to hear more opinions on this.

Also, can you add a bit of context to your description of the change? I know what an implicit null check is, but not everyone will.

Thanks for mentioning. I will update the description.

Chandler, since you're sure to have strong opinions, what do you feel is the right approach for framing this?

[sanjoy]

I've mentioned this to Chen in person, but I'll repeat what I said:

I'm not sure I understand what the "cost" in this context is supposed
to model. If it is supposed to model code size then this change makes
sense completely. If it is supposed to model *compile time* then this
change is not in the right direction -- the implicit null checks stay
explicit throughout optimization, so they will extract the compile
time cost of a "normal" compare and branch.

lib/Analysis/InlineCost.cpp

 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/CallingConv.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/GlobalAlias.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Operator.h"
+#include "llvm/IR/LLVMContext.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "inline-cost"
 
 STATISTIC(NumCallsAnalyzed, "Number of call sites analyzed");
class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   /// 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);
 
+
+  /// Return true if all users of the comparison are marked as make_implicit.
+  bool isImplicitNullCheckCmp(CmpInst &I) ;
+
   // 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 &);
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::isImplicitNullCheckCmp(CmpInst &I) {
+  for (auto User : I.users()) {
+    if (auto Instr = dyn_cast<Instruction>(User))
+      if (Instr->getMetadata(LLVMContext::MD_make_implicit))
+        continue;
+
+    return false;
+  }
+  return true;
+}
+
 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 (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) {
     if (isa<ConstantPointerNull>(I.getOperand(1))) {
       accumulateSROACost(CostIt, InlineConstants::InstrCost);
       return true;
     }
 
     disableSROA(CostIt);
   }
 
+  // Implicit null checks act as unconditional branches, and
+  // their comparisons should be treated as simplified and
+  // free of cost. See the comments in visitBranchInst.
+  if (I.isEquality() && isa<ConstantPointerNull>(I.getOperand(1))
+      && isImplicitNullCheckCmp(I))
+    return true;
+
   return false;
 }
 
 bool CallAnalyzer::visitSub(BinaryOperator &I) {
   // Try to handle a special case: we can fold computing the difference of two
   // constant-related pointers.
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
   Value *LHSBase, *RHSBase;
bool CallAnalyzer::visitReturnInst(ReturnInst &RI) {
   return Free;
 }
 
 bool CallAnalyzer::visitBranchInst(BranchInst &BI) {
   // We model unconditional branches as essentially free -- they really
   // shouldn't exist at all, but handling them makes the behavior of the
   // inliner more regular and predictable. Interestingly, conditional branches
   // which will fold away are also free.
-  return BI.isUnconditional() || isa<ConstantInt>(BI.getCondition()) ||
-         dyn_cast_or_null<ConstantInt>(
-             SimplifiedValues.lookup(BI.getCondition()));
+  return BI.isUnconditional() || isa<ConstantInt>(BI.getCondition()) ||
+         BI.getMetadata(LLVMContext::MD_make_implicit) ||
+         dyn_cast_or_null<ConstantInt>(
+             SimplifiedValues.lookup(BI.getCondition()));
 }
 
 bool CallAnalyzer::visitSwitchInst(SwitchInst &SI) {
   // We model unconditional switches as free, see the comments on handling
   // branches.
   if (isa<ConstantInt>(SI.getCondition()))
     return true;
   if (Value *V = SimplifiedValues.lookup(SI.getCondition()))

test/Transforms/Inline/implicit_null_check.ll

+; RUN: opt < %s -inline -inline-threshold=6 -S | FileCheck %s
+
+define i32 @callee(i32* %x) {
+entry:
+; The comparison and implicit null check should be free.
+; The only cost is the load instruction and it is 5.
+  %cond = icmp eq i32* %x, null
+  br i1 %cond, label %is_null, label %not_null, !make.implicit !0
+
+is_null:
+  ret i32 42
+
+not_null:
+  %t = load i32, i32* %x
+  ret i32 %t
+}
+
+define i32 @caller(i32* %arg) {
+; CHECK-LABEL: @caller
+; CHECK: %cond.i = icmp eq i32* %arg, null
+  %r = call i32 @callee(i32* %arg)
+  ret i32 %r
+}
+
+!0 = !{}
+