[Attributor] Deduction based on path exploration

[uenoku]

Summary

This patch introduces the propagation of known information based on path exploration.
For example,

int u(int c, int *p){
  if(c) {
     return *p;
  } else {
     return *p + 1;
  }
}

An argument p is dereferenced whatever c's value is.

For an instruction CtxI, we accumulate branch instructions in the must-be-executed-context of CtxI and then, we take the conjunction of the successors' known state.

[uenoku]

Fix typo.

[jdoerfert]

I only reviewed the MustExecute parts as the Attributor part probably needs a rebase. I think this is needed and I'll be more responsive this time.

llvm/include/llvm/Analysis/MustExecute.h

509

Newline before and comment describing this struct and its use briefly.

525

I would not call it Multiplicative/Additive identity, nor Top/Bottom. I would stick to the Attributor spellings of "best/worst state". The others are overloaded too often (IMHO).

543

If you keep pointer values, this is shorter: if (AState *State = MemoizeResult.lookup(PPBegin)) return *State;

566

I think I would prefer that we first explore range completely and only collect branch instructions. If range was not enough to cause stopExplore to trigger, we start exploring branches. The reason is that range information is "better" than child information as it holds without the need to explore a second path. We should also have a parameter to limit the search.

568

Is it wise to store the address of the local object AS here? Maybe we need the map to own the state.

[uenoku]

Rebased. I simply use AbstractState to accumulate the known information.

[baziotis]

That's very interesting, I hope I'll have time to come back with a better review.

llvm/lib/Transforms/IPO/Attributor.cpp

1050–1051

This UsesInChild I think is not used anywhere. Probably put there since something has to be passed to the function. Can we do something to avoid inserting to it and deleting in every loop? (If I haven't missed something)

[jdoerfert]

Thanks for resurrecting this patch. This gives us really interesting opportunities as we can already see with the nonnull and deref changes :)
I will need to look over everything, maybe next week (I'm on travel again). A first comment inlined though.

llvm/include/llvm/Analysis/MustExecute.h

473

My first impression is that we might want to shift the burden of collecting instructions to the user and just do the iterating here. The benefit is that we could use the return of Pred to indicate that we want to stop. I think we want to have a way to stop the search of the context if we don't expect to find better results anymore.

[uenoku]

Address comments

[uenoku]

llvm/include/llvm/Analysis/MustExecute.h

473

Addressed.

llvm/lib/Transforms/IPO/Attributor.cpp

1050–1051

Yes, that's right.

[baziotis]

llvm/lib/Transforms/IPO/Attributor.cpp

1050–1051

Thanks for addressing this. I think it still isn't used though right? i.e. With your update, it seems you can just remove UsesInChild declaration completely.

[uenoku]

llvm/lib/Transforms/IPO/Attributor.cpp

1050–1051

Oh, I forgot to remove it ;)

[jdoerfert]

llvm/include/llvm/Transforms/IPO/Attributor.h

1342

We need Documentation for this.

llvm/lib/Transforms/IPO/Attributor.cpp

1062

Can you explain the NOTE further and why we cannot make it "right"?

---

Do you really want to delete UsesInChild or do you want to use it in the followUsesInContext call such that Uses is not modifed here.

[baziotis]

llvm/lib/Transforms/IPO/Attributor.cpp

1062

Do you really want to delete UsesInChild or do you want to use it in the followUsesInContext call such that Uses is not modifed here.

Hmm, that was my initial assumption as well:

Probably put there since something has to be passed to the function

but I thought I was wrong.

[uenoku]

Simplify implementation.

[uenoku]

llvm/lib/Transforms/IPO/Attributor.cpp

1062

Can you explain the NOTE further and why we cannot make it "right"?

I didn't have a brain;) I have implemented in a simpler way so NOTE is removed.

Do you really want to delete UsesInChild or do you want to use it in the followUsesInContext call such that Uses is not modifed here.

I want to modify Uses in followUsesInContext so I'm fine with removing UsesInChild.

[jdoerfert]

I have not convinced myself that this covers the recursive case properly, maybe that was never the intend though. Can we have a test like this:

void foo(int a, int b, int c, int *ptr) {
  if (a) {
    if (b)
      *ptr = 1;
    else
      *ptr = 2;
  } else {
    if (c)
      *ptr = 3;
    else
      *ptr = 4;
  }
}

and maybe also

void foo(int a, int b, int c, int *ptr) {
  if (a) {
    if (b)
      *ptr = 1;
    else
      *ptr = 2;
  } else {
    if (c)
      *ptr = 3;
    else
      foo(1, 1, 1, ptr);
  }
}

llvm/lib/Transforms/IPO/Attributor.cpp

1032

I don't get the comment. What are the two indices of ChildState and why is the second ChildState "out-of-sync"?

[uenoku]

Fix comment and add test.

[uenoku]

I have not convinced myself that this covers the recursive case properly, maybe that was never the intend though. Can we have a test like this:

Yes, recursive branches are not handled in this patch to simplify. I'll add on a later patch.

llvm/lib/Transforms/IPO/Attributor.cpp

1032

It was broken. Sorry for the confusion.

[jdoerfert]

LGTM. We need a recursive lookup that tracks paths up to a given depth next.

llvm/include/llvm/Analysis/MustExecute.h

struct MustBeExecutedContextExplorer {
   }
 
   /// Return an iterator range to explore the cached context around \p PP.
   llvm::iterator_range<const_iterator> range(const Instruction *PP) const {
     return llvm::make_range(begin(PP), end(PP));
   }
   ///}
 
+  /// Check \p Pred on all instructions in the context.
+  ///
+  /// This method will evaluate \p Pred and return
+  /// true if \p Pred holds in every instruction.
+  bool checkForAllContext(const Instruction *PP,
+                          const function_ref<bool(const Instruction *)> &Pred) {
+    for (auto EIt = begin(PP), EEnd = end(PP); EIt != EEnd; EIt++)
+      if (!Pred(*EIt))
+        return false;
+    return true;
+  }
+
   /// Helper to look for \p I in the context of \p PP.
   ///
   /// The context is expanded until \p I was found or no more expansion is
   /// possible.
   ///
   /// \returns True, iff \p I was found.
   bool findInContextOf(const Instruction *I, const Instruction *PP) {
     auto EIt = begin(PP), EEnd = end(PP);
struct MustBeExecutedContextExplorer {
   ///
   /// \param It              The iterator that is used to traverse the must be
   ///                        executed context.
   /// \param PP              The program point for which the next instruction
   ///                        that is guaranteed to execute is determined.
   const Instruction *
   getMustBeExecutedNextInstruction(MustBeExecutedIterator &It,
                                    const Instruction *PP);
   /// Return the previous instr. that is guaranteed to be executed before \p PP.
   ///
   /// \param It              The iterator that is used to traverse the must be
   ///                        executed context.
   /// \param PP              The program point for which the previous instr.
   ///                        that is guaranteed to execute is determined.
   const Instruction *
   getMustBeExecutedPrevInstruction(MustBeExecutedIterator &It,
                                    const Instruction *PP);
 
   /// Find the next join point from \p InitBB in forward direction.
   const BasicBlock *findForwardJoinPoint(const BasicBlock *InitBB);
 
   /// Find the next join point from \p InitBB in backward direction.
   const BasicBlock *findBackwardJoinPoint(const BasicBlock *InitBB);
 
   /// Parameter that limit the performed exploration. See the constructor for
   /// their meaning.
   ///{
   const bool ExploreInterBlock;
   const bool ExploreCFGForward;
   const bool ExploreCFGBackward;
   ///}
 
 private:
   /// Getters for common CFG analyses: LoopInfo, DominatorTree, and
   /// PostDominatorTree.
   ///{
   GetterTy<const LoopInfo> LIGetter;
   GetterTy<const DominatorTree> DTGetter;
   GetterTy<const PostDominatorTree> PDTGetter;
   ///}
 
   /// Map to cache isGuaranteedToTransferExecutionToSuccessor results.
   DenseMap<const BasicBlock *, Optional<bool>> BlockTransferMap;
 
   /// Map to cache containsIrreducibleCFG results.
   DenseMap<const Function*, Optional<bool>> IrreducibleControlMap;
 
   /// Map from instructions to associated must be executed iterators.
   DenseMap<const Instruction *, MustBeExecutedIterator *>
       InstructionIteratorMap;
 
   /// A unique end iterator.
   MustBeExecutedIterator EndIterator;
 };
 
 } // namespace llvm
 
 #endif

llvm/include/llvm/Transforms/IPO/Attributor.h

struct IntegerStateBase : public AbstractState {
 
   /// "Clamp" this state with \p R. The result is subtype dependent but it is
   /// intended that only information assumed in both states will be assumed in
   /// this one afterwards.
   void operator^=(const IntegerStateBase<base_t, BestState, WorstState> &R) {
     handleNewAssumedValue(R.getAssumed());
   }
 
+  /// "Clamp" this state with \p R. The result is subtype dependent but it is
+  /// intended that information known in either state will be known in
+  /// this one afterwards.
+  void operator+=(const IntegerStateBase<base_t, BestState, WorstState> &R) {
+    handleNewKnownValue(R.getKnown());
+  }
+
   void operator|=(const IntegerStateBase<base_t, BestState, WorstState> &R) {
     joinOR(R.getAssumed(), R.getKnown());
   }
 
   void operator&=(const IntegerStateBase<base_t, BestState, WorstState> &R) {
     joinAND(R.getAssumed(), R.getKnown());
   }
 
struct DerefState : AbstractState {
 
   /// See IntegerStateBase::operator^=
   DerefState operator^=(const DerefState &R) {
     DerefBytesState ^= R.DerefBytesState;
     GlobalState ^= R.GlobalState;
     return *this;
   }
 
+  /// See IntegerStateBase::operator+=
+  DerefState operator+=(const DerefState &R) {
+    DerefBytesState += R.DerefBytesState;
+    GlobalState += R.GlobalState;
+    return *this;
+  }
+
   /// See IntegerStateBase::operator&=
   DerefState operator&=(const DerefState &R) {
     DerefBytesState &= R.DerefBytesState;
     GlobalState &= R.GlobalState;
     return *this;
   }
 
   /// See IntegerStateBase::operator|=

llvm/lib/Transforms/IPO/Attributor.cpp

void initialize(Attributor &A) override {
 
     if (!CtxI)
       return;
 
     for (const Use &U : IRP.getAssociatedValue().uses())
       Uses.insert(&U);
   }
 
+  /// Helper function to accumulate uses.
+  void followUsesInContext(Attributor &A,
+                           MustBeExecutedContextExplorer &Explorer,
+                           const Instruction *CtxI,
+                           SetVector<const Use *> &Uses, StateType &State) {
+    auto EIt = Explorer.begin(CtxI), EEnd = Explorer.end(CtxI);
+    for (unsigned u = 0; u < Uses.size(); ++u) {
+      const Use *U = Uses[u];
+      if (const Instruction *UserI = dyn_cast<Instruction>(U->getUser())) {
+        bool Found = Explorer.findInContextOf(UserI, EIt, EEnd);
+        if (Found && Base::followUse(A, U, UserI, State))
+          for (const Use &Us : UserI->uses())
+            Uses.insert(&Us);
+      }
+    }
+  }
+
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
     auto BeforeState = this->getState();
     auto &S = this->getState();
     Instruction *CtxI = this->getIRPosition().getCtxI();
     if (!CtxI)
       return ChangeStatus::UNCHANGED;
 
     MustBeExecutedContextExplorer &Explorer =
         A.getInfoCache().getMustBeExecutedContextExplorer();
 
-    auto EIt = Explorer.begin(CtxI), EEnd = Explorer.end(CtxI);
-    for (unsigned u = 0; u < Uses.size(); ++u) {
-      const Use *U = Uses[u];
-      if (const Instruction *UserI = dyn_cast<Instruction>(U->getUser())) {
-        bool Found = Explorer.findInContextOf(UserI, EIt, EEnd);
-        if (Found && Base::followUse(A, U, UserI))
-          for (const Use &Us : UserI->uses())
-            Uses.insert(&Us);
+    followUsesInContext(A, Explorer, CtxI, Uses, S);
+
+    if (this->isAtFixpoint())
+      return ChangeStatus::CHANGED;
+
+    SmallVector<const BranchInst *, 4> BrInsts;
+    auto Pred = [&](const Instruction *I) {
+      if (const BranchInst *Br = dyn_cast<BranchInst>(I))
+        if (Br->isConditional())
+          BrInsts.push_back(Br);
+      return true;
+    };
+
+    // Here, accumulate conditional branch instructions in the context. We
+    // explore the child paths and collect the known states. The disjunction of
+    // those states can be merged to its own state.
+    //
+    // ParentState_1 = ChildState_{1, 1} /\ ChildState_{1, 2} /\ ... /\
+    // ChildState_{1, n_1}
+    //      ...
+    // ParentState_m = ChildState_{m, 1} /\ ChildState_{2, 2} /\ ... /\
+    // ChildState_{1, n_m}
+    //
+    // Known State |= ParentState_1 \/ ... \/ ParentState_m
+
+    Explorer.checkForAllContext(CtxI, Pred);
+    for (const BranchInst *Br : BrInsts) {
+      StateType ParentState;
+
+      // The known state of the parent state is a conjunction of children's
+      // known states so it is initialized with a best state.
+      ParentState.indicateOptimisticFixpoint();
+
+      for (const BasicBlock *BB : Br->successors()) {
+        StateType ChildState;
+
+        size_t BeforeSize = Uses.size();
+        followUsesInContext(A, Explorer, &BB->front(), Uses, ChildState);
+
+        // Erase uses which only appear in the child.
+        for (auto It = Uses.begin() + BeforeSize; It != Uses.end();)
+          It = Uses.erase(It);
+
+        ParentState &= ChildState;
       }
+
+      // Use only known state.
+      S += ParentState;
     }
 
     return BeforeState == S ? ChangeStatus::UNCHANGED : ChangeStatus::CHANGED;
   }
 
 private:
   /// Container for (transitive) uses of the associated value.
   SetVector<const Use *> Uses;
 };
 
 template <typename AAType, typename Base,
           typename StateType = typename AAType::StateType>
ChangeStatus manifest(Attributor &A) override {
     return ChangeStatus::UNCHANGED;
   }
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(nofree) }
 };
 
 /// ------------------------ NonNull Argument Attribute ------------------------
 static int64_t getKnownNonNullAndDerefBytesForUse(
-    Attributor &A, AbstractAttribute &QueryingAA, Value &AssociatedValue,
+    Attributor &A, const AbstractAttribute &QueryingAA, Value &AssociatedValue,
     const Use *U, const Instruction *I, bool &IsNonNull, bool &TrackUse) {
   TrackUse = false;
 
   const Value *UseV = U->get();
   if (!UseV->getType()->isPointerTy())
     return 0;
 
   Type *PtrTy = UseV->getType();
if (!NullIsDefined &&
       indicateOptimisticFixpoint();
     else if (isa<ConstantPointerNull>(getAssociatedValue()))
       indicatePessimisticFixpoint();
     else
       AANonNull::initialize(A);
   }
 
   /// See AAFromMustBeExecutedContext
-  bool followUse(Attributor &A, const Use *U, const Instruction *I) {
+  bool followUse(Attributor &A, const Use *U, const Instruction *I,
+                 AANonNull::StateType &State) {
     bool IsNonNull = false;
     bool TrackUse = false;
     getKnownNonNullAndDerefBytesForUse(A, *this, getAssociatedValue(), U, I,
                                        IsNonNull, TrackUse);
-    setKnown(IsNonNull);
+    State.setKnown(IsNonNull);
     return TrackUse;
   }
 
   /// See AbstractAttribute::getAsStr().
   const std::string getAsStr() const override {
     return getAssumed() ? "nonnull" : "may-null";
   }
 
struct AADereferenceableImpl : AADereferenceable {
 
   /// See AbstractAttribute::getState()
   /// {
   StateType &getState() override { return *this; }
   const StateType &getState() const override { return *this; }
   /// }
 
   /// Helper function for collecting accessed bytes in must-be-executed-context
-  void addAccessedBytesForUse(Attributor &A, const Use *U,
-                              const Instruction *I) {
+  void addAccessedBytesForUse(Attributor &A, const Use *U, const Instruction *I,
+                              DerefState &State) {
     const Value *UseV = U->get();
     if (!UseV->getType()->isPointerTy())
       return;
 
     Type *PtrTy = UseV->getType();
     const DataLayout &DL = A.getDataLayout();
     int64_t Offset;
     if (const Value *Base = getBasePointerOfAccessPointerOperand(
             I, Offset, DL, /*AllowNonInbounds*/ true)) {
       if (Base == &getAssociatedValue() &&
           getPointerOperand(I, /* AllowVolatile */ false) == UseV) {
         uint64_t Size = DL.getTypeStoreSize(PtrTy->getPointerElementType());
-        addAccessedBytes(Offset, Size);
+        State.addAccessedBytes(Offset, Size);
       }
     }
     return;
   }
 
   /// See AAFromMustBeExecutedContext
-  bool followUse(Attributor &A, const Use *U, const Instruction *I) {
+  bool followUse(Attributor &A, const Use *U, const Instruction *I,
+                 AADereferenceable::StateType &State) {
     bool IsNonNull = false;
     bool TrackUse = false;
     int64_t DerefBytes = getKnownNonNullAndDerefBytesForUse(
         A, *this, getAssociatedValue(), U, I, IsNonNull, TrackUse);
 
-    addAccessedBytesForUse(A, U, I);
-    takeKnownDerefBytesMaximum(DerefBytes);
+    addAccessedBytesForUse(A, U, I, State);
+    State.takeKnownDerefBytesMaximum(DerefBytes);
     return TrackUse;
   }
 
   /// See AbstractAttribute::manifest(...).
   ChangeStatus manifest(Attributor &A) override {
     ChangeStatus Change = AADereferenceable::manifest(A);
     if (isAssumedNonNull() && hasAttr(Attribute::DereferenceableOrNull)) {
       removeAttrs({Attribute::DereferenceableOrNull});
struct AAAlignImpl : AAAlign {
   virtual void
   getDeducedAttributes(LLVMContext &Ctx,
                        SmallVectorImpl<Attribute> &Attrs) const override {
     if (getAssumedAlign() > 1)
       Attrs.emplace_back(
           Attribute::getWithAlignment(Ctx, Align(getAssumedAlign())));
   }
   /// See AAFromMustBeExecutedContext
-  bool followUse(Attributor &A, const Use *U, const Instruction *I) {
+  bool followUse(Attributor &A, const Use *U, const Instruction *I,
+                 AAAlign::StateType &State) {
     bool TrackUse = false;
 
     unsigned int KnownAlign =
         getKnownAlignForUse(A, *this, getAssociatedValue(), U, I, TrackUse);
-    takeKnownMaximum(KnownAlign);
+    State.takeKnownMaximum(KnownAlign);
 
     return TrackUse;
   }
 
   /// See AbstractAttribute::getAsStr().
   const std::string getAsStr() const override {
     return getAssumedAlign() ? ("align<" + std::to_string(getKnownAlign()) +
                                 "-" + std::to_string(getAssumedAlign()) + ">")

llvm/test/Transforms/Attributor/IPConstantProp/openmp_parallel_for.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes
-; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=1 < %s | FileCheck %s
+; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 < %s | FileCheck %s
 ;
 ;    void bar(int, float, double);
 ;
 ;    void foo(int N) {
 ;      float p = 3;
 ;      double q = 5;
 ;      N = 7;
 ;

llvm/test/Transforms/Attributor/dereferenceable-1.ll

 ;
 entry:
   %0 = load i64, i64* %range, align 8, !range !0
   tail call void @fill_range_inbounds(i32* %p, i64 %0)
   tail call void @fill_range_not_inbounds(i32* %p, i64 %0)
   ret void
 }
 
+declare void @use0() #0
+declare void @use1(i8*) #0
+declare void @use2(i8*, i8*) #0
+declare void @use3(i8*, i8*, i8*) #0
+; simple path test
+; if(..)
+;   fun2(dereferenceable(8) %a, dereferenceable(8) %b)
+; else
+;   fun2(dereferenceable(4) %a, %b)
+; We can say that %a is dereferenceable(4) but %b is not.
+define void @simple-path(i8* %a, i8 * %b, i8 %c) {
+; ATTRIBUTOR: define void @simple-path(i8* nonnull dereferenceable(4) %a, i8* %b, i8 %c)
+  %cmp = icmp eq i8 %c, 0
+  br i1 %cmp, label %if.then, label %if.else
+if.then:
+  tail call void @use2(i8* dereferenceable(8) %a, i8* dereferenceable(8) %b)
+  ret void
+if.else:
+  tail call void @use2(i8* dereferenceable(4) %a, i8* %b)
+  ret void
+}
+; More complex test
+; {
+; fun1(dereferenceable(4) %a)
+; if(..)
+;    ... (willreturn & nounwind)
+;    fun1(dereferenceable(12) %a)
+; else
+;    ... (willreturn & nounwind)
+;    fun1(dereferenceable(16) %a)
+; fun1(dereferenceable(8) %a)
+; }
+; %a is dereferenceable(12)
+
+define void @complex-path(i8* %a, i8* %b, i8 %c) {
+; ATTRIBUTOR: define void @complex-path(i8* nonnull dereferenceable(12) %a, i8* nocapture nofree readnone %b, i8 %c)
+  %cmp = icmp eq i8 %c, 0
+  tail call void @use1(i8* dereferenceable(4) %a)
+  br i1 %cmp, label %cont.then, label %cont.else
+cont.then:
+  tail call void @use1(i8* dereferenceable(12) %a)
+  br label %cont2
+cont.else:
+  tail call void @use1(i8* dereferenceable(16) %a)
+  br label %cont2
+cont2:
+  tail call void @use1(i8* dereferenceable(8) %a)
+  ret void
+}
+
+attributes #0 = { nounwind willreturn}
+
 !0 = !{i64 10, i64 100}
 

llvm/test/Transforms/Attributor/nonnull.ll

 declare void @fun3(i8*, i8*, i8*) #1
 ; TEST 16 simple path test
 ; if(..)
 ;   fun2(nonnull %a, nonnull %b)
 ; else
 ;   fun2(nonnull %a, %b)
 ; We can say that %a is nonnull but %b is not.
 define void @f16(i8* %a, i8 * %b, i8 %c) {
-; FIXME: missing nonnull on %a
-; ATTRIBUTOR: define void @f16(i8* %a, i8* %b, i8 %c)
+; ATTRIBUTOR: define void @f16(i8* nonnull %a, i8* %b, i8 %c)
   %cmp = icmp eq i8 %c, 0
   br i1 %cmp, label %if.then, label %if.else
 if.then:
   tail call void @fun2(i8* nonnull %a, i8* nonnull %b)
   ret void
 if.else:
   tail call void @fun2(i8* nonnull %a, i8* %b)
   ret void

 cont2:
   tail call void @fun1(i8* nonnull %a)
   ret void
 }
 
 ; TEST 19: Loop
 
 define void @f19(i8* %a, i8* %b, i8 %c) {
-; FIXME: missing nonnull on %b
-; ATTRIBUTOR: define void @f19(i8* %a, i8* %b, i8 %c)
+; ATTRIBUTOR: define void @f19(i8* %a, i8* nonnull %b, i8 %c)
   br label %loop.header
 loop.header:
   %cmp2 = icmp eq i8 %c, 0
   br i1 %cmp2, label %loop.body, label %loop.exit
 loop.body:
   tail call void @fun1(i8* nonnull %b)
   tail call void @fun1(i8* nonnull %a)
   br label %loop.header
hd2:
   %tmp8 = add nuw i32 %tmp7, 1
   %tmp9 = icmp eq i32 %tmp8, %b
   br i1 %tmp9, label %ex, label %hd
 }
 
 define i32 @nonnull_exec_ctx_2(i32* %a, i32 %b) willreturn nounwind {
 ;
 ; ATTRIBUTOR-LABEL: define {{[^@]+}}@nonnull_exec_ctx_2
-; ATTRIBUTOR-SAME: (i32* [[A:%.*]], i32 [[B:%.*]])
+; ATTRIBUTOR-SAME: (i32* nonnull [[A:%.*]], i32 [[B:%.*]])
 ; ATTRIBUTOR-NEXT:  en:
 ; ATTRIBUTOR-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[B]], 0
 ; ATTRIBUTOR-NEXT:    br i1 [[TMP3]], label [[EX:%.*]], label [[HD:%.*]]
 ; ATTRIBUTOR:       ex:
 ; ATTRIBUTOR-NEXT:    [[TMP5:%.*]] = tail call i32 @g(i32* nonnull [[A]])
 ; ATTRIBUTOR-NEXT:    ret i32 [[TMP5]]
 ; ATTRIBUTOR:       hd:
 ; ATTRIBUTOR-NEXT:    [[TMP7:%.*]] = phi i32 [ [[TMP8:%.*]], [[HD]] ], [ 0, [[EN:%.*]] ]
hd:
   %tmp8 = add nuw i32 %tmp7, 1
   %tmp9 = icmp eq i32 %tmp8, %b
   br i1 %tmp9, label %ex, label %hd
 }
 
 define i32 @nonnull_exec_ctx_2b(i32* %a, i32 %b) willreturn nounwind {
 ;
 ; ATTRIBUTOR-LABEL: define {{[^@]+}}@nonnull_exec_ctx_2b
-; ATTRIBUTOR-SAME: (i32* [[A:%.*]], i32 [[B:%.*]])
+; ATTRIBUTOR-SAME: (i32* nonnull [[A:%.*]], i32 [[B:%.*]])
 ; ATTRIBUTOR-NEXT:  en:
 ; ATTRIBUTOR-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[B]], 0
 ; ATTRIBUTOR-NEXT:    br i1 [[TMP3]], label [[EX:%.*]], label [[HD:%.*]]
 ; ATTRIBUTOR:       ex:
 ; ATTRIBUTOR-NEXT:    [[TMP5:%.*]] = tail call i32 @g(i32* nonnull [[A]])
 ; ATTRIBUTOR-NEXT:    ret i32 [[TMP5]]
 ; ATTRIBUTOR:       hd:
 ; ATTRIBUTOR-NEXT:    [[TMP7:%.*]] = phi i32 [ [[TMP8:%.*]], [[HD2:%.*]] ], [ 0, [[EN:%.*]] ]