[InstCombine] Propagate non-null facts to call parameters

[reames]

Summary

If a parameter to a function is known non-null, use the existing parameter attributes to record that fact at the call site. This has no optimization benefit by itself - that I know of - but is an enabling change for http://reviews.llvm.org/D9129.

[pete]

This is somewhat similar to what FunctionAttrs.cpp does, although nonnull is a parameter level instead of function level attribute.

Should this behavior be moved to FunctionAttrs.cpp instead of InstCombine, or vice-versa?

[nicholas]

Pete Cooper wrote:

This is somewhat similar to what FunctionAttrs.cpp does, although nonnull is a parameter level instead of function level attribute.

Should this behavior be moved to FunctionAttrs.cpp instead of InstCombine, or vice-versa?

It should probably go into FunctionAttrs.cpp which also computes
per-argument readonly/readnone/nocapture. One of the things to note is
that you can end up with an SCC between functions A and B where they
pass a parameter to each other which has no reason not to be nonnull
except for their mutual use of each other. FunctionAttrs builds up an
SCC graph of Arguments to solve this optimally and deterministically.

Nick

http://reviews.llvm.org/D9132

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[reames]

After thinking about this further and getting most of the way through an alternate implementation in FunctionAttr, I've come to the conclusion that FunctionAttr.cpp is not the right place for this.

For nonnull argument attributes, you have two separate inference problems to solve:

• If the callee provably dereferences or otherwise consumes a pointer in a way which implies it can't be null, you can propagate this outwards. This is a natural fit for FunctionAttr.cpp since it works bottom up.
• If all callers pass non-null values and the definition is private linkage, the function argument can be assumed to be non-null. This is inherently a top-down problem in that you need to have visited the callers before visiting the callees.

(In an ideal world, these two would run together and iterated to a fixed point. Let's assume we're not doing that for the moment.)

The current patch is arguably part of the second inference problem not the first. It doesn't implement the interprocedural part of the analysis - though arguably, that's what the specialization logic in InlineCost is doing - but it's solving the top down part of the problem. FunctionAttr.cpp (which is inherently bottom up) isn't really a good fit for this.

Now, InstCombine isn't really a great fit either - it's still run in a bottom up manner by the SCCCallGraphPass when inlining - but that's more of an implementation detail than an inherent part of the pass. As a practical matter, InstCombine will also get one chance to visit all functions before inlining begins. FunctionAttr doesn't get this chance, so even locally obvious non-null pointers couldn't be exploited without actually running analysis in the caller rather than relying on the call site attributes.

p.s. While looking into this, I ended up mostly implementing the returns-nonnull bottom up analysis mentioned above. I'll post that for review separately.

[reames]

As a follow on to my previous comment, Nick's comment about being able to handle SCCs in one go is completely valid. It's orthogonal to my point, and is out of scope for this patch. As I mentioned previously, this patch doesn't do *any* interprocedural attribute propagation. Adding the SCC aware logic - even if it mostly runs bottom up - would be useful, it's just a different patch.

[reames]

Nick, Pete - I'd like to go ahead and land this. Can I can a formal LGTM from one of you?

[pete]

Sorry, shouldn't have done that sooner. LGTM.

[nlewycky]

test/Transforms/InstCombine/nonnull-param.ll

1

Please use "opt -S -instcombine < %s" so that it doesn't emit a ModuleID comment with the filename.

[pete]

Sorry, Phab is acting up for me, hence email.

I think this line should actually set 'Changed = true;’ and not return. That way you can handle more than a single nonnull at a time.

+ return CS.getInstruction();

Otherwise LGTM.

Cheers,
Pete

include/llvm/IR/CallSite.h

 #define LLVM_IR_CALLSITE_H
 
 #include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/iterator_range.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/CallingConv.h"
 #include "llvm/IR/Instructions.h"

   }
 
   IterTy arg_end() const { return (*this)->op_end() - getArgumentEndOffset(); }
+  iterator_range<IterTy> args() const {
+    return iterator_range<IterTy>(arg_begin(), arg_end());
+  }
   bool arg_empty() const { return arg_end() == arg_begin(); }
   unsigned arg_size() const { return unsigned(arg_end() - arg_begin()); }
   

lib/Transforms/InstCombine/InstCombineCalls.cpp

 // visitCallSite - Improvements for call and invoke instructions.
 //
 Instruction *InstCombiner::visitCallSite(CallSite CS) {
+
+  // Mark any parameters that are known to be non-null with the nonnull
+  // attribute.  This is helpful for inlining calls to functions with null
+  // checks on their arguments.
+  unsigned ArgNo = 0;
+  for (Value *V : CS.args()) {
+    if (!CS.paramHasAttr(ArgNo+1, Attribute::NonNull) &&
+        isKnownNonNull(V)) {
+      AttributeSet AS = CS.getAttributes();
+      AS = AS.addAttribute(CS.getInstruction()->getContext(), ArgNo+1,
+                           Attribute::NonNull);
+      CS.setAttributes(AS);
+      return CS.getInstruction();
+    }
+    ArgNo++;
+  }
+  assert(ArgNo == CS.arg_size() && "sanity check");
+  
   if (isAllocLikeFn(CS.getInstruction(), TLI))
     return visitAllocSite(*CS.getInstruction());
 

test/CodeGen/NVPTX/intrin-nocapture.ll

 ; CHECK: @bar
 define void @bar() {
   %t1 = alloca i32
-; CHECK: call i32 addrspace(1)* @llvm.nvvm.ptr.gen.to.global.p1i32.p0i32(i32* %t1)
+; CHECK: call i32 addrspace(1)* @llvm.nvvm.ptr.gen.to.global.p1i32.p0i32(i32* nonnull %t1)
 ; CHECK-NEXT: store i32 10, i32* %t1
   %t2 = call i32 addrspace(1)* @llvm.nvvm.ptr.gen.to.global.p1i32.p0i32(i32* %t1)
   store i32 10, i32* %t1

test/Transforms/Inline/byval-tail-call.ll

 ; CHECK: %[[POS:.*]] = alloca i32
 ; CHECK: %[[VAL:.*]] = load i32, i32* %x
 ; CHECK: store i32 %[[VAL]], i32* %[[POS]]
-; CHECK: {{^ *}}call void @ext(i32* %[[POS]]
+; CHECK: {{^ *}}call void @ext(i32* nonnull %[[POS]]
 ; CHECK: tail call void @ext(i32* null)
 ; CHECK: ret void
   tail call void @qux(i32* byval %x)

test/Transforms/InstCombine/nonnull-param.ll

+; RUN: opt -S -instcombine %s | FileCheck %s
+
+declare void @callee(i8* %arg)
+
+; Positive test - arg is known non null
+define void @test(i8* nonnull %arg) {
+; CHECK-LABEL: @test
+; CHECK: call void @callee(i8* nonnull %arg)
+  call void @callee(i8* %arg)
+  ret void
+}
+
+
+; Negative test - arg is not known to be non null
+define void @test2(i8* %arg) {
+; CHECK-LABEL: @test2
+; CHECK: call void @callee(i8* %arg)
+  call void @callee(i8* %arg)
+  ret void
+}
+
+declare void @callee2(i8*, i8*, i8*)
+
+; Sanity check arg indexing
+define void @test3(i8* %arg1, i8* nonnull %arg2, i8* %arg3) {
+; CHECK-LABEL: @test3
+; CHECK: call void @callee2(i8* %arg1, i8* nonnull %arg2, i8* %arg3)
+  call void @callee2(i8* %arg1, i8* %arg2, i8* %arg3)
+  ret void
+}
+
+; Self recursive call - Because of the way CallSite::paramHasAttribute looks at
+; the callee directly, we will not set the attribute on the CallSite.  That's 
+; fine as long as all consumers use the same check. 
+define void @test4(i8* nonnull %arg) {
+; CHECK-LABEL: @test4
+; CHECK: call void @test4(i8* %arg)
+  call void @test4(i8* %arg)
+  ret void
+}
+
+

test/Transforms/InstCombine/select.ll

 ; load does.
 ; CHECK-LABEL: @test77(
 ; CHECK: %[[A:.*]] = alloca i32, align 1
-; CHECK: call void @scribble_on_i32(i32* %[[A]])
+; CHECK: call void @scribble_on_i32(i32* nonnull %[[A]])
 ; CHECK: store i32 0, i32* %x
 ; CHECK: %[[P:.*]] = select i1 %flag, i32* %[[A]], i32* %x
 ; CHECK: load i32, i32* %[[P]]