[MustExecute] Add backward exploration for must-be-executed-context

[uenoku]

Summary

As mentioned in D71974, it is useful for must-be-executed-context to explore CFG backwardly.
This patch is ported from parts of D64975. We use a dominator tree to find the previous context if
a dominator tree is available.

[jdoerfert]

Thank you for picking this up!

I inlined some minor comments but you can address them before commiting this.

LGTM.

llvm/include/llvm/Analysis/MustExecute.h

410

I think we should not set default values but force the user to decide.

llvm/lib/Analysis/MustExecute.cpp

362

"Unrelated": We have to make these unique_ptr so we can remove the delete at the end.

llvm/test/Analysis/MustExecute/must_be_executed_context.ll

27

We have backward exploration now.

232

Still missing F

[uenoku]

Address comments

[jdoerfert]

FWIW, the effect of this can be seen in D74888 pretty nicely. llvm.assume that must have been executed are used to improve the state :)

llvm/include/llvm/Analysis/MustExecute.h

public:
 
   ICFLoopSafetyInfo(DominatorTree *DT) : LoopSafetyInfo(), ICF(DT), MW(DT) {};
 
   virtual ~ICFLoopSafetyInfo() {};
 };
 
 struct MustBeExecutedContextExplorer;
 
+/// Enum that allows us to spell out the direction.
+enum class ExplorationDirection {
+  BACKWARD = 0,
+  FORWARD = 1,
+};
+
 /// Must be executed iterators visit stretches of instructions that are
 /// guaranteed to be executed together, potentially with other instruction
 /// executed in-between.
 ///
 /// Given the following code, and assuming all statements are single
 /// instructions which transfer execution to the successor (see
 /// isGuaranteedToTransferExecutionToSuccessor), there are two possible
 /// outcomes. If we start the iterator at A, B, or E, we will visit only A, B,
struct MustBeExecutedIterator {
   typedef const Instruction *&reference;
   typedef std::input_iterator_tag iterator_category;
   ///}
 
   using ExplorerTy = MustBeExecutedContextExplorer;
 
   MustBeExecutedIterator(const MustBeExecutedIterator &Other)
       : Visited(Other.Visited), Explorer(Other.Explorer),
-        CurInst(Other.CurInst) {}
+        CurInst(Other.CurInst), Head(Other.Head), Tail(Other.Tail) {}
 
   MustBeExecutedIterator(MustBeExecutedIterator &&Other)
       : Visited(std::move(Other.Visited)), Explorer(Other.Explorer),
-        CurInst(Other.CurInst) {}
+        CurInst(Other.CurInst), Head(Other.Head), Tail(Other.Tail) {}
 
   MustBeExecutedIterator &operator=(MustBeExecutedIterator &&Other) {
     if (this != &Other) {
       std::swap(Visited, Other.Visited);
       std::swap(CurInst, Other.CurInst);
+      std::swap(Head, Other.Head);
+      std::swap(Tail, Other.Tail);
     }
     return *this;
   }
 
   ~MustBeExecutedIterator() {}
 
   /// Pre- and post-increment operators.
   ///{
   MustBeExecutedIterator &operator++() {
     CurInst = advance();
     return *this;
   }
 
   MustBeExecutedIterator operator++(int) {
     MustBeExecutedIterator tmp(*this);
     operator++();
     return tmp;
   }
   ///}
 
   /// Equality and inequality operators. Note that we ignore the history here.
   ///{
   bool operator==(const MustBeExecutedIterator &Other) const {
-    return CurInst == Other.CurInst;
+    return CurInst == Other.CurInst && Head == Other.Head && Tail == Other.Tail;
   }
 
   bool operator!=(const MustBeExecutedIterator &Other) const {
     return !(*this == Other);
   }
   ///}
 
   /// Return the underlying instruction.
   const Instruction *&operator*() { return CurInst; }
   const Instruction *getCurrentInst() const { return CurInst; }
 
   /// Return true if \p I was encountered by this iterator already.
-  bool count(const Instruction *I) const { return Visited.count(I); }
+  bool count(const Instruction *I) const {
+    return Visited.count({I, ExplorationDirection::FORWARD}) ||
+           Visited.count({I, ExplorationDirection::BACKWARD});
+  }
 
 private:
-  using VisitedSetTy = DenseSet<const Instruction *>;
+  using VisitedSetTy =
+      DenseSet<PointerIntPair<const Instruction *, 1, ExplorationDirection>>;
 
   /// Private constructors.
   MustBeExecutedIterator(ExplorerTy &Explorer, const Instruction *I);
 
   /// Reset the iterator to its initial state pointing at \p I.
   void reset(const Instruction *I);
 
+  /// Reset the iterator to point at \p I, keep cached state.
+  void resetInstruction(const Instruction *I);
+
   /// Try to advance one of the underlying positions (Head or Tail).
   ///
   /// \return The next instruction in the must be executed context, or nullptr
   ///         if none was found.
   const Instruction *advance();
 
   /// A set to track the visited instructions in order to deal with endless
   /// loops and recursion.
   VisitedSetTy Visited;
 
   /// A reference to the explorer that created this iterator.
   ExplorerTy &Explorer;
 
   /// The instruction we are currently exposing to the user. There is always an
   /// instruction that we know is executed with the given program point,
   /// initially the program point itself.
   const Instruction *CurInst;
 
+  /// Two positions that mark the program points where this iterator will look
+  /// for the next instruction. Note that the current instruction is either the
+  /// one pointed to by Head, Tail, or both.
+  const Instruction *Head, *Tail;
+
   friend struct MustBeExecutedContextExplorer;
 };
 
 /// A "must be executed context" for a given program point PP is the set of
 /// instructions, potentially before and after PP, that are executed always when
 /// PP is reached. The MustBeExecutedContextExplorer an interface to explore
 /// "must be executed contexts" in a module through the use of
 /// MustBeExecutedIterator.
 ///
 /// The explorer exposes "must be executed iterators" that traverse the must be
 /// executed context. There is little information sharing between iterators as
 /// the expected use case involves few iterators for "far apart" instructions.
 /// If that changes, we should consider caching more intermediate results.
 struct MustBeExecutedContextExplorer {
 
   /// In the description of the parameters we use PP to denote a program point
   /// for which the must be executed context is explored, or put differently,
   /// for which the MustBeExecutedIterator is created.
   ///
   /// \param ExploreInterBlock    Flag to indicate if instructions in blocks
   ///                             other than the parent of PP should be
   ///                             explored.
+  /// \param ExploreCFGForward    Flag to indicate if instructions located after
+  ///                             PP in the CFG, e.g., post-dominating PP,
+  ///                             should be explored.
+  /// \param ExploreCFGBackward   Flag to indicate if instructions located
+  ///                             before PP in the CFG, e.g., dominating PP,
+  ///                             should be explored.
   MustBeExecutedContextExplorer(
-      bool ExploreInterBlock,
+      bool ExploreInterBlock, bool ExploreCFGForward = true,
+      bool ExploreCFGBackward = true,
       GetterTy<const LoopInfo> LIGetter =
           [](const Function &) { return nullptr; },
+      GetterTy<const DominatorTree> DTGetter =
+          [](const Function &) { return nullptr; },
       GetterTy<const PostDominatorTree> PDTGetter =
           [](const Function &) { return nullptr; })
-      : ExploreInterBlock(ExploreInterBlock), LIGetter(LIGetter),
-        PDTGetter(PDTGetter), EndIterator(*this, nullptr) {}
+      : ExploreInterBlock(ExploreInterBlock),
+        ExploreCFGForward(ExploreCFGForward),
+        ExploreCFGBackward(ExploreCFGBackward), LIGetter(LIGetter),
+        DTGetter(DTGetter), PDTGetter(PDTGetter), EndIterator(*this, nullptr) {}
 
   /// Clean up the dynamically allocated iterators.
   ~MustBeExecutedContextExplorer() {
     DeleteContainerSeconds(InstructionIteratorMap);
   }
 
   /// Iterator-based interface. \see MustBeExecutedIterator.
   ///{
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;

llvm/lib/Analysis/MustExecute.cpp

ModulePass *llvm::createMustBeExecutedContextPrinter() {
   return new MustBeExecutedContextPrinter();
 }
 
 bool MustBeExecutedContextPrinter::runOnModule(Module &M) {
   // We provide non-PM analysis here because the old PM doesn't like to query
   // function passes from a module pass.
   SmallVector<PostDominatorTree *, 8> PDTs;
   SmallVector<DominatorTree *, 8> DTs;
   SmallVector<LoopInfo *, 8> LIs;
 
   GetterTy<LoopInfo> LIGetter = [&](const Function &F) {
     DominatorTree *DT = new DominatorTree(const_cast<Function &>(F));
     LoopInfo *LI = new LoopInfo(*DT);
     DTs.push_back(DT);
     LIs.push_back(LI);
     return LI;
   };
+  GetterTy<DominatorTree> DTGetter = [&](const Function &F) {
+    DominatorTree *DT = new DominatorTree(const_cast<Function &>(F));
+    DTs.push_back(DT);
+    return DT;
+  };
   GetterTy<PostDominatorTree> PDTGetter = [&](const Function &F) {
     PostDominatorTree *PDT = new PostDominatorTree(const_cast<Function &>(F));
     PDTs.push_back(PDT);
     return PDT;
   };
-  MustBeExecutedContextExplorer Explorer(true, LIGetter, PDTGetter);
+  MustBeExecutedContextExplorer Explorer(
+      /* ExploreInterBlock */ true,
+      /* ExploreCFGForward */ true,
+      /* ExploreCFGBackward */ true, LIGetter, DTGetter, PDTGetter);
+
   for (Function &F : M) {
     for (Instruction &I : instructions(F)) {
       dbgs() << "-- Explore context of: " << I << "\n";
       for (const Instruction *CI : Explorer.range(&I))
         dbgs() << "  [F: " << CI->getFunction()->getName() << "] " << *CI
                << "\n";
     }
   }
while (!Worklist.empty()) {
       for (const BasicBlock *AdjacentBB : successors(ToBB))
         Worklist.push_back(AdjacentBB);
     }
   }
 
   LLVM_DEBUG(dbgs() << "\tJoin block: " << JoinBB->getName() << "\n");
   return JoinBB;
 }
+const BasicBlock *
+MustBeExecutedContextExplorer::findBackwardJoinPoint(const BasicBlock *InitBB) {
+  const LoopInfo *LI = LIGetter(*InitBB->getParent());
+  const DominatorTree *DT = DTGetter(*InitBB->getParent());
+  LLVM_DEBUG(dbgs() << "\tFind backward join point for " << InitBB->getName()
+                    << (LI ? " [LI]" : "") << (DT ? " [DT]" : ""));
+
+  // Try to determine a join block through the help of the dominance tree. If no
+  // tree was provided, we perform simple pattern matching for one block
+  // conditionals only.
+  if (DT)
+    if (const auto *InitNode = DT->getNode(InitBB))
+      if (const auto *IDomNode = InitNode->getIDom())
+        return IDomNode->getBlock();
+
+  const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;
+  const BasicBlock *HeaderBB = L ? L->getHeader() : nullptr;
+
+  // Determine the predecessor blocks but ignore backedges.
+  SmallVector<const BasicBlock *, 8> Worklist;
+  for (const BasicBlock *PredBB : predecessors(InitBB)) {
+    bool IsBackedge =
+        (PredBB == InitBB) || (HeaderBB == InitBB && L->contains(PredBB));
+    // Loop backedges are ignored in backwards propagation: control has to come
+    // from somewhere.
+    if (!IsBackedge)
+      Worklist.push_back(PredBB);
+  }
+
+  // If there are no other predecessor blocks, there is no join point.
+  if (Worklist.empty())
+    return nullptr;
+
+  // If there is one predecessor block, it is the join point.
+  if (Worklist.size() == 1)
+    return Worklist[0];
+
+  const BasicBlock *JoinBB = nullptr;
+  if (Worklist.size() == 2) {
+    const BasicBlock *Pred0 = Worklist[0];
+    const BasicBlock *Pred1 = Worklist[1];
+    const BasicBlock *Pred0UniquePred = Pred0->getUniquePredecessor();
+    const BasicBlock *Pred1UniquePred = Pred1->getUniquePredecessor();
+    if (Pred0 == Pred1UniquePred) {
+      // InitBB <-          Pred0 = JoinBB
+      // InitBB <- Pred1 <- Pred0 = JoinBB
+      JoinBB = Pred0;
+    } else if (Pred1 == Pred0UniquePred) {
+      // InitBB <- Pred0 <- Pred1 = JoinBB
+      // InitBB <-          Pred1 = JoinBB
+      JoinBB = Pred1;
+    } else if (Pred0UniquePred == Pred1UniquePred) {
+      // InitBB <- Pred0 <- JoinBB
+      // InitBB <- Pred1 <- JoinBB
+      JoinBB = Pred0UniquePred;
+    }
+  }
+
+  if (!JoinBB && L)
+    JoinBB = L->getHeader();
+
+  // In backwards direction there is no need to show termination of previous
+  // instructions. If they do not terminate, the code afterward is dead, making
+  // any information/transformation correct anyway.
+  return JoinBB;
+}
 
 const Instruction *
 MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction(
     MustBeExecutedIterator &It, const Instruction *PP) {
   if (!PP)
     return PP;
   LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP << "\n");
 
MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction(
   // information about the function and helper analyses, if available.
   if (const BasicBlock *JoinBB = findForwardJoinPoint(PP->getParent()))
     return &JoinBB->front();
 
   LLVM_DEBUG(dbgs() << "\tNo join point found\n");
   return nullptr;
 }
 
+const Instruction *
+MustBeExecutedContextExplorer::getMustBeExecutedPrevInstruction(
+    MustBeExecutedIterator &It, const Instruction *PP) {
+  if (!PP)
+    return PP;
+
+  bool IsFirst = !(PP->getPrevNode());
+  LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP
+                    << (IsFirst ? " [IsFirst]" : "") << "\n");
+
+  // If we explore only inside a given basic block we stop at the first
+  // instruction.
+  if (!ExploreInterBlock && IsFirst) {
+    LLVM_DEBUG(dbgs() << "\tReached block front in intra-block mode, done\n");
+    return nullptr;
+  }
+
+  // The block and function that contains the current position.
+  const BasicBlock *PPBlock = PP->getParent();
+
+  // If we are inside a block we know what instruction was executed before, the
+  // previous one.
+  if (!IsFirst) {
+    const Instruction *PrevPP = PP->getPrevNode();
+    LLVM_DEBUG(
+        dbgs() << "\tIntermediate instruction, continue with previous\n");
+    // We did not enter a callee so we simply return the previous instruction.
+    return PrevPP;
+  }
+
+  // Finally, we have to handle the case where the program point is the first in
+  // a block but not in the function. We use the findBackwardJoinPoint helper
+  // function with information about the function and helper analyses, if
+  // available.
+  if (const BasicBlock *JoinBB = findBackwardJoinPoint(PPBlock))
+    return &JoinBB->back();
+
+  LLVM_DEBUG(dbgs() << "\tNo join point found\n");
+  return nullptr;
+}
+
 MustBeExecutedIterator::MustBeExecutedIterator(
     MustBeExecutedContextExplorer &Explorer, const Instruction *I)
     : Explorer(Explorer), CurInst(I) {
   reset(I);
 }
 
 void MustBeExecutedIterator::reset(const Instruction *I) {
-  CurInst = I;
   Visited.clear();
-  Visited.insert(I);
+  resetInstruction(I);
+}
+
+void MustBeExecutedIterator::resetInstruction(const Instruction *I) {
+  CurInst = I;
+  Head = Tail = nullptr;
+  Visited.insert({I, ExplorationDirection::FORWARD});
+  Visited.insert({I, ExplorationDirection::BACKWARD});
+  if (Explorer.ExploreCFGForward)
+    Head = I;
+  if (Explorer.ExploreCFGBackward)
+    Tail = I;
 }
 
 const Instruction *MustBeExecutedIterator::advance() {
   assert(CurInst && "Cannot advance an end iterator!");
-  const Instruction *Next =
-      Explorer.getMustBeExecutedNextInstruction(*this, CurInst);
-  if (Next && !Visited.insert(Next).second)
-    Next = nullptr;
-  return Next;
+  Head = Explorer.getMustBeExecutedNextInstruction(*this, Head);
+  if (Head && Visited.insert({Head, ExplorationDirection ::FORWARD}).second)
+    return Head;
+  Head = nullptr;
+
+  Tail = Explorer.getMustBeExecutedPrevInstruction(*this, Tail);
+  if (Tail && Visited.insert({Tail, ExplorationDirection ::BACKWARD}).second)
+    return Tail;
+  Tail = nullptr;
+  return nullptr;
 }

llvm/test/Analysis/MustExecute/must_be_executed_context.ll

 ; A                   | A, B,       E, F
 ;    B                | A, B,       E, F
 ;       C             | A, B, C, D, E, F
 ;          D          | A, B, C, D, E, F
 ;             E       | A, B,       E, F
 ;                F    | A, B,       E, F
 ;                   G | A, B,       E, F, G
 ;
 ; FIXME: We miss the B -> E and backward exploration.
 ;
 ; There are no loops so print-mustexec will not do anything.
 ; ME-NOT: mustexec
 ;
 define void @simple_conditional(i32 %arg) {
 bb:
   call void @A()
 ; MBEC:      -- Explore context of:   call void @A()
 ; MBEC-NEXT:   [F: simple_conditional]   call void @A()
 ; MBEC-NEXT:   [F: simple_conditional]   call void @B()
 ; MBEC-NEXT:   [F: simple_conditional]   %tmp = icmp eq i32 %arg, 0
 ; MBEC-NEXT:   [F: simple_conditional]   br i1 %tmp, label %bb2, label %bb1
 ; MBEC-NEXT:   [F: simple_conditional]   call void @E()
 ; MBEC-NEXT:   [F: simple_conditional]   call void @F()
 ; MBEC-NOT:    call
 
   call void @B()
 ; MBEC:      -- Explore context of:   call void @B()
 ; MBEC-NEXT:   [F: simple_conditional]   call void @B()
 ; MBEC-NEXT:   [F: simple_conditional]   %tmp = icmp eq i32 %arg, 0
 ; MBEC-NEXT:   [F: simple_conditional]   br i1 %tmp, label %bb2, label %bb1
 ; MBEC-NEXT:   [F: simple_conditional]   call void @E()
 ; MBEC-NEXT:   [F: simple_conditional]   call void @F()
+; MBEC-NEXT:   [F: simple_conditional]   call void @A()
 ; MBEC-NOT:    call
 ; MBEC:      -- Explore context of: %tmp
 
   %tmp = icmp eq i32 %arg, 0
   br i1 %tmp, label %bb2, label %bb1
 
 bb1:                                              ; preds = %bb
   call void @C()
 ; MBEC:      -- Explore context of:   call void @C()
 ; MBEC-NEXT:   [F: simple_conditional]   call void @C()
 ; MBEC-NEXT:   [F: simple_conditional]   call void @D()
 ; MBEC-NEXT:   [F: simple_conditional]   br label %bb2
 ; MBEC-NEXT:   [F: simple_conditional]   call void @E()
 ; MBEC-NEXT:   [F: simple_conditional]   call void @F()
+; MBEC-NEXT:   [F: simple_conditional]   br i1 %tmp, label %bb2, label %bb1
+; MBEC-NEXT:   [F: simple_conditional]   %tmp = icmp eq i32 %arg, 0
+; MBEC-NEXT:   [F: simple_conditional]   call void @B()
+; MBEC-NEXT:   [F: simple_conditional]   call void @A()
 ; MBEC-NOT:    call
 
   call void @D()
 ; MBEC:      -- Explore context of:   call void @D()
 ; MBEC-NEXT:   [F: simple_conditional]   call void @D()
 ; MBEC-NEXT:   [F: simple_conditional]   br label %bb2
 ; MBEC-NEXT:   [F: simple_conditional]   call void @E()
 ; MBEC-NEXT:   [F: simple_conditional]   call void @F()
+; MBEC-NEXT:   [F: simple_conditional]   call void @C()
+; MBEC-NEXT:   [F: simple_conditional]   br i1 %tmp, label %bb2, label %bb1
+; MBEC-NEXT:   [F: simple_conditional]   %tmp = icmp eq i32 %arg, 0
+; MBEC-NEXT:   [F: simple_conditional]   call void @B()
+; MBEC-NEXT:   [F: simple_conditional]   call void @A()
 ; MBEC-NOT:    call
 ; MBEC:      -- Explore context of: br
 
   br label %bb2
 
 bb2:                                              ; preds = %bb, %bb1
   call void @E()
 ; MBEC:      -- Explore context of:   call void @E()
 ; MBEC-NEXT:   [F: simple_conditional]   call void @E()
 ; MBEC-NEXT:   [F: simple_conditional]   call void @F()
+; MBEC-NEXT:   [F: simple_conditional]   br i1 %tmp, label %bb2, label %bb1
+; MBEC-NEXT:   [F: simple_conditional]   %tmp = icmp eq i32 %arg, 0
+; MBEC-NEXT:   [F: simple_conditional]   call void @B()
+; MBEC-NEXT:   [F: simple_conditional]   call void @A()
 ; MBEC-NOT:    call
 
   call void @F() ; might not return!
 ; MBEC:      -- Explore context of:   call void @F()
 ; MBEC-NEXT:   [F: simple_conditional]   call void @F()
+; MBEC-NEXT:   [F: simple_conditional]   call void @E()
+; MBEC-NEXT:   [F: simple_conditional]   br i1 %tmp, label %bb2, label %bb1
+; MBEC-NEXT:   [F: simple_conditional]   %tmp = icmp eq i32 %arg, 0
+; MBEC-NEXT:   [F: simple_conditional]   call void @B()
+; MBEC-NEXT:   [F: simple_conditional]   call void @A()
 ; MBEC-NOT:    call
 
   call void @G()
 ; MBEC:      -- Explore context of:   call void @G()
 ; MBEC-NEXT:   [F: simple_conditional]   call void @G()
 ; MBEC-NEXT:   [F: simple_conditional]   ret void
+; MBEC-NEXT:   [F: simple_conditional]   call void @F()
+; MBEC-NEXT:   [F: simple_conditional]   call void @E()
+; MBEC-NEXT:   [F: simple_conditional]   br i1 %tmp, label %bb2, label %bb1
+; MBEC-NEXT:   [F: simple_conditional]   %tmp = icmp eq i32 %arg, 0
+; MBEC-NEXT:   [F: simple_conditional]   call void @B()
+; MBEC-NEXT:   [F: simple_conditional]   call void @A()
 ; MBEC-NOT:    call
 ; MBEC:      -- Explore context of: ret
 
   ret void
 }
 
 
 ;    void complex_loops_and_control(int c, int d) {
bb2:                                              ; preds = %.backedge, %bb
   %.0 = phi i32 [ %arg, %bb ], [ %.0.be, %.backedge ]
   call void @B()
 ; ME: call void @B() ; (mustexec in: bb2)
 ; MBEC:      -- Explore context of:   call void @B()
 ; MBEC-NEXT:   [F: complex_loops_and_control]   call void @B()
 ; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp = add nsw i32 %.0, 1
 ; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp3 = icmp eq i32 %tmp, %arg1
 ; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp3, label %bb4, label %bb5
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp6 = add nsw i32 %.0, 2
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp7 = icmp eq i32 %tmp6, %arg1
+; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp7, label %bb8, label %bb9
+; MBEC-NEXT:   [F: complex_loops_and_control]   %.0 = phi i32 [ %arg, %bb ], [ %.0.be, %.backedge ]
+; MBEC-NEXT:   [F: complex_loops_and_control]   br label %bb2
+; MBEC-NEXT:   [F: complex_loops_and_control]   call void @A()
 ; MBEC-NOT:    call
 ; MBEC:      -- Explore context of: %tmp
   %tmp = add nsw i32 %.0, 1
   %tmp3 = icmp eq i32 %tmp, %arg1
   br i1 %tmp3, label %bb4, label %bb5
 
 bb4:                                              ; preds = %bb2
   call void @C()
 ; ME: call void @C()
 ; ME-NOT: mustexec
 ; ME-NEXT: br
 ; FIXME: Missing A and B (backward)
 ; MBEC:      -- Explore context of:   call void @C()
 ; MBEC-NEXT:   [F: complex_loops_and_control]   call void @C()
 ; MBEC-NEXT:   [F: complex_loops_and_control]   br label %bb5
 ; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp6 = add nsw i32 %.0, 2
 ; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp7 = icmp eq i32 %tmp6, %arg1
 ; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp7, label %bb8, label %bb9
+; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp3, label %bb4, label %bb5
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp3 = icmp eq i32 %tmp, %arg1
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp = add nsw i32 %.0, 1
+; MBEC-NEXT:   [F: complex_loops_and_control]   call void @B()
+; MBEC-NEXT:   [F: complex_loops_and_control]   %.0 = phi i32 [ %arg, %bb ], [ %.0.be, %.backedge ]
+; MBEC-NEXT:   [F: complex_loops_and_control]   br label %bb2
+; MBEC-NEXT:   [F: complex_loops_and_control]   call void @A()
 ; MBEC-NOT:    call
 ; MBEC:      -- Explore context of: br
   br label %bb5
 
 bb5:                                              ; preds = %bb4, %bb2
   %tmp6 = add nsw i32 %.0, 2
   %tmp7 = icmp eq i32 %tmp6, %arg1
   br i1 %tmp7, label %bb8, label %bb9
 
 bb8:                                              ; preds = %bb5
   br label %.backedge
 
 .backedge:                                        ; preds = %bb8, %bb22
   %.0.be = phi i32 [ %tmp6, %bb8 ], [ %.lcssa, %bb22 ]
   br label %bb2
 
 bb9:                                              ; preds = %bb5
   call void @D()
 ; ME: call void @D()
 ; ME-NOT: mustexec
 ; ME-NEXT: %tmp10
-; FIXME: Missing A and B (backward)
 ; MBEC:      -- Explore context of:   call void @D()
 ; MBEC-NEXT:   [F: complex_loops_and_control]   call void @D()
 ; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp10 = add nsw i32 %.0, 3
 ; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp11 = icmp eq i32 %tmp10, %arg1
 ; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp11, label %bb12, label %bb13
+; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp7, label %bb8, label %bb9
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp7 = icmp eq i32 %tmp6, %arg1
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp6 = add nsw i32 %.0, 2
+; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp3, label %bb4, label %bb5
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp3 = icmp eq i32 %tmp, %arg1
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp = add nsw i32 %.0, 1
+; MBEC-NEXT:   [F: complex_loops_and_control]   call void @B()
+; MBEC-NEXT:   [F: complex_loops_and_control]   %.0 = phi i32 [ %arg, %bb ], [ %.0.be, %.backedge ]
+; MBEC-NEXT:   [F: complex_loops_and_control]   br label %bb2
+; MBEC-NEXT:   [F: complex_loops_and_control]   call void @A()
 ; MBEC-NOT:    call
 ; MBEC:      -- Explore context of: %tmp10
   %tmp10 = add nsw i32 %.0, 3
   %tmp11 = icmp eq i32 %tmp10, %arg1
   br i1 %tmp11, label %bb12, label %bb13
 
 bb12:                                             ; preds = %bb9
   br label %bb23

 bb17:                                             ; preds = %bb14
   br label %bb19
 
 bb18:                                             ; preds = %bb14
   call void @E()
 ; ME: call void @E()
 ; ME-NOT: mustexec
 ; ME-NEXT: br
-; FIXME: Missing A, B, and D (backward), as well as F
 ; MBEC:      -- Explore context of:   call void @E()
-; MBEC-NEXT:   [F: complex_loops_and_control]   call void @E()
-; MBEC-NEXT:   [F: complex_loops_and_control]   br label %bb19
-; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp20 = add nsw i32 %.1, 2
-; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp21 = icmp eq i32 %tmp20, %arg1
-; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp21, label %bb14, label %bb22
+; MBEC-NEXT:  [F: complex_loops_and_control]   call void @E()
+; MBEC-NEXT:  [F: complex_loops_and_control]   br label %bb19
+; MBEC-NEXT:  [F: complex_loops_and_control]   %tmp20 = add nsw i32 %.1, 2
+; MBEC-NEXT:  [F: complex_loops_and_control]   %tmp21 = icmp eq i32 %tmp20, %arg1
+; MBEC-NEXT:  [F: complex_loops_and_control]   br i1 %tmp21, label %bb14, label %bb22
+; MBEC-NEXT:  [F: complex_loops_and_control]   br i1 %tmp16, label %bb17, label %bb18
+; MBEC-NEXT:  [F: complex_loops_and_control]   %tmp16 = icmp eq i32 %tmp15, %arg1
+; MBEC-NEXT:  [F: complex_loops_and_control]   %tmp15 = add nsw i32 %.1, 1
+; MBEC-NEXT:  [F: complex_loops_and_control]   %.1 = phi i32 [ %tmp10, %bb13 ], [ %tmp20, %bb19 ]
+; MBEC-NEXT:  [F: complex_loops_and_control]   br label %bb14
+; MBEC-NEXT:  [F: complex_loops_and_control]   br i1 %tmp11, label %bb12, label %bb13
+; MBEC-NEXT:  [F: complex_loops_and_control]   %tmp11 = icmp eq i32 %tmp10, %arg1
+; MBEC-NEXT:  [F: complex_loops_and_control]   %tmp10 = add nsw i32 %.0, 3
+; MBEC-NEXT:  [F: complex_loops_and_control]   call void @D()
+; MBEC-NEXT:  [F: complex_loops_and_control]   br i1 %tmp7, label %bb8, label %bb9
+; MBEC-NEXT:  [F: complex_loops_and_control]   %tmp7 = icmp eq i32 %tmp6, %arg1
+; MBEC-NEXT:  [F: complex_loops_and_control]   %tmp6 = add nsw i32 %.0, 2
+; MBEC-NEXT:  [F: complex_loops_and_control]   br i1 %tmp3, label %bb4, label %bb5
+; MBEC-NEXT:  [F: complex_loops_and_control]   %tmp3 = icmp eq i32 %tmp, %arg1
+; MBEC-NEXT:  [F: complex_loops_and_control]   %tmp = add nsw i32 %.0, 1
+; MBEC-NEXT:  [F: complex_loops_and_control]   call void @B()
+; MBEC-NEXT:  [F: complex_loops_and_control]   %.0 = phi i32 [ %arg, %bb ], [ %.0.be, %.backedge ]
+; MBEC-NEXT:  [F: complex_loops_and_control]   br label %bb2
+; MBEC-NEXT:  [F: complex_loops_and_control]   call void @A()
 ; MBEC-NOT:    call
 ; MBEC:      -- Explore context of: br
   br label %bb19
 
 bb19:                                             ; preds = %bb18, %bb17
   %tmp20 = add nsw i32 %.1, 2
   %tmp21 = icmp eq i32 %tmp20, %arg1
   br i1 %tmp21, label %bb14, label %bb22
 
 bb22:                                             ; preds = %bb19
   %.lcssa = phi i32 [ %tmp20, %bb19 ]
   call void @F()
 ; ME: call void @F()
 ; ME-NOT: mustexec
 ; ME-NEXT: br
-; FIXME: Missing A, B, and D (backward)
 ; MBEC:      -- Explore context of:   call void @F()
 ; MBEC-NEXT:   [F: complex_loops_and_control]   call void @F()
+; MBEC-NEXT:   [F: complex_loops_and_control]   %.lcssa = phi i32 [ %tmp20, %bb19 ]
+; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp21, label %bb14, label %bb22
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp21 = icmp eq i32 %tmp20, %arg1
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp20 = add nsw i32 %.1, 2
+; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp16, label %bb17, label %bb18
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp16 = icmp eq i32 %tmp15, %arg1
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp15 = add nsw i32 %.1, 1
+; MBEC-NEXT:   [F: complex_loops_and_control]   %.1 = phi i32 [ %tmp10, %bb13 ], [ %tmp20, %bb19 ]
+; MBEC-NEXT:   [F: complex_loops_and_control]   br label %bb14
+; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp11, label %bb12, label %bb13
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp11 = icmp eq i32 %tmp10, %arg1
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp10 = add nsw i32 %.0, 3
+; MBEC-NEXT:   [F: complex_loops_and_control]   call void @D()
+; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp7, label %bb8, label %bb9
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp7 = icmp eq i32 %tmp6, %arg1
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp6 = add nsw i32 %.0, 2
+; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp3, label %bb4, label %bb5
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp3 = icmp eq i32 %tmp, %arg1
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp = add nsw i32 %.0, 1
+; MBEC-NEXT:   [F: complex_loops_and_control]   call void @B()
+; MBEC-NEXT:   [F: complex_loops_and_control]   %.0 = phi i32 [ %arg, %bb ], [ %.0.be, %.backedge ]
+; MBEC-NEXT:   [F: complex_loops_and_control]   br label %bb2
+; MBEC-NEXT:   [F: complex_loops_and_control]   call void @A()
 ; MBEC-NOT:    call
 ; MBEC:      -- Explore context of: br
   br label %.backedge
 
 bb23:                                             ; preds = %bb12
   call void @G()
 ; ME: call void @G()
 ; ME-NOT: mustexec
 ; ME-NEXT: ret
-; FIXME: Missing A, B, and D (backward)
 ; MBEC:      -- Explore context of:   call void @G()
 ; MBEC-NEXT:   [F: complex_loops_and_control]   call void @G()
 ; MBEC-NEXT:   [F: complex_loops_and_control]   ret void
+; MBEC-NEXT:   [F: complex_loops_and_control]   br label %bb23
+; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp11, label %bb12, label %bb13
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp11 = icmp eq i32 %tmp10, %arg1
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp10 = add nsw i32 %.0, 3
+; MBEC-NEXT:   [F: complex_loops_and_control]   call void @D()
+; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp7, label %bb8, label %bb9
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp7 = icmp eq i32 %tmp6, %arg1
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp6 = add nsw i32 %.0, 2
+; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp3, label %bb4, label %bb5
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp3 = icmp eq i32 %tmp, %arg1
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp = add nsw i32 %.0, 1
+; MBEC-NEXT:   [F: complex_loops_and_control]   call void @B()
+; MBEC-NEXT:   [F: complex_loops_and_control]   %.0 = phi i32 [ %arg, %bb ], [ %.0.be, %.backedge ]
+; MBEC-NEXT:   [F: complex_loops_and_control]   br label %bb2
+; MBEC-NEXT:   [F: complex_loops_and_control]   call void @A()
 ; MBEC-NOT:    call
 ; MBEC:      -- Explore context of: ret
   ret void
 }
 
 declare void @A() nounwind willreturn
 
 declare void @B() nounwind willreturn
 
 declare void @C() nounwind willreturn
 
 declare void @D() nounwind willreturn
 
 declare void @E() nounwind willreturn
 
 declare void @F() nounwind
 
 declare void @G() nounwind willreturn
 
 declare i32 @g(i32*) nounwind willreturn
 
 declare void @h(i32*) nounwind willreturn
 
 define i32 @nonnull_exec_ctx_1(i32* %a, i32 %b) {
-; MBEC:      -- Explore context of:   %tmp3 = icmp eq i32 %b, 0
+; MBEC: -- Explore context of:   %tmp3 = icmp eq i32 %b, 0
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp3 = icmp eq i32 %b, 0
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   br i1 %tmp3, label %ex, label %hd
 ; MBEC-NEXT: -- Explore context of:   br i1 %tmp3, label %ex, label %hd
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   br i1 %tmp3, label %ex, label %hd
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp3 = icmp eq i32 %b, 0
 ; MBEC-NEXT: -- Explore context of:   %tmp5 = tail call i32 @g(i32* nonnull %a)
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp5 = tail call i32 @g(i32* nonnull %a)
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   ret i32 %tmp5
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   br i1 %tmp3, label %ex, label %hd
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp3 = icmp eq i32 %b, 0
 ; MBEC-NEXT: -- Explore context of:   ret i32 %tmp5
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   ret i32 %tmp5
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp5 = tail call i32 @g(i32* nonnull %a)
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   br i1 %tmp3, label %ex, label %hd
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp3 = icmp eq i32 %b, 0
 ; MBEC-NEXT: -- Explore context of:   %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ]
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ]
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   tail call void @h(i32* %a)
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp8 = add nuw i32 %tmp7, 1
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp9 = icmp eq i32 %tmp8, %b
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   br i1 %tmp9, label %ex, label %hd
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   br i1 %tmp3, label %ex, label %hd
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp3 = icmp eq i32 %b, 0
 ; MBEC-NEXT: -- Explore context of:   tail call void @h(i32* %a)
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   tail call void @h(i32* %a)
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp8 = add nuw i32 %tmp7, 1
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp9 = icmp eq i32 %tmp8, %b
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   br i1 %tmp9, label %ex, label %hd
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ]
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   br i1 %tmp3, label %ex, label %hd
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp3 = icmp eq i32 %b, 0
 ; MBEC-NEXT: -- Explore context of:   %tmp8 = add nuw i32 %tmp7, 1
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp8 = add nuw i32 %tmp7, 1
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp9 = icmp eq i32 %tmp8, %b
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   br i1 %tmp9, label %ex, label %hd
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   tail call void @h(i32* %a)
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ]
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   br i1 %tmp3, label %ex, label %hd
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp3 = icmp eq i32 %b, 0
 ; MBEC-NEXT: -- Explore context of:   %tmp9 = icmp eq i32 %tmp8, %b
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp9 = icmp eq i32 %tmp8, %b
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   br i1 %tmp9, label %ex, label %hd
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp8 = add nuw i32 %tmp7, 1
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   tail call void @h(i32* %a)
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ]
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   br i1 %tmp3, label %ex, label %hd
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp3 = icmp eq i32 %b, 0
 ; MBEC-NEXT: -- Explore context of:   br i1 %tmp9, label %ex, label %hd
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   br i1 %tmp9, label %ex, label %hd
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp9 = icmp eq i32 %tmp8, %b
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp8 = add nuw i32 %tmp7, 1
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   tail call void @h(i32* %a)
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ]
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   br i1 %tmp3, label %ex, label %hd
+; MBEC-NEXT:   [F: nonnull_exec_ctx_1]   %tmp3 = icmp eq i32 %b, 0
 en:
   %tmp3 = icmp eq i32 %b, 0
   br i1 %tmp3, label %ex, label %hd
 
 ex:
   %tmp5 = tail call i32 @g(i32* nonnull %a)
   ret i32 %tmp5
 
 hd:
   %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ]
   tail call void @h(i32* %a)
   %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) nounwind willreturn {
-; MBEC:      -- Explore context of:   %tmp3 = icmp eq i32 %b, 0
+; MBEC: -- Explore context of:   %tmp3 = icmp eq i32 %b, 0
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp3 = icmp eq i32 %b, 0
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   br i1 %tmp3, label %ex, label %hd
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp5 = tail call i32 @g(i32* nonnull %a)
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   ret i32 %tmp5
 ; MBEC-NEXT: -- Explore context of:   br i1 %tmp3, label %ex, label %hd
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   br i1 %tmp3, label %ex, label %hd
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp5 = tail call i32 @g(i32* nonnull %a)
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   ret i32 %tmp5
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp3 = icmp eq i32 %b, 0
 ; MBEC-NEXT: -- Explore context of:   %tmp5 = tail call i32 @g(i32* nonnull %a)
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp5 = tail call i32 @g(i32* nonnull %a)
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   ret i32 %tmp5
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   br i1 %tmp3, label %ex, label %hd
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp3 = icmp eq i32 %b, 0
 ; MBEC-NEXT: -- Explore context of:   ret i32 %tmp5
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   ret i32 %tmp5
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp5 = tail call i32 @g(i32* nonnull %a)
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   br i1 %tmp3, label %ex, label %hd
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp3 = icmp eq i32 %b, 0
 ; MBEC-NEXT: -- Explore context of:   %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ]
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ]
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   tail call void @h(i32* %a)
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp8 = add nuw i32 %tmp7, 1
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp9 = icmp eq i32 %tmp8, %b
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   br i1 %tmp9, label %ex, label %hd
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp5 = tail call i32 @g(i32* nonnull %a)
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   ret i32 %tmp5
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   br i1 %tmp3, label %ex, label %hd
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp3 = icmp eq i32 %b, 0
 ; MBEC-NEXT: -- Explore context of:   tail call void @h(i32* %a)
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   tail call void @h(i32* %a)
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp8 = add nuw i32 %tmp7, 1
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp9 = icmp eq i32 %tmp8, %b
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   br i1 %tmp9, label %ex, label %hd
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp5 = tail call i32 @g(i32* nonnull %a)
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   ret i32 %tmp5
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ]
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   br i1 %tmp3, label %ex, label %hd
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp3 = icmp eq i32 %b, 0
 ; MBEC-NEXT: -- Explore context of:   %tmp8 = add nuw i32 %tmp7, 1
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp8 = add nuw i32 %tmp7, 1
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp9 = icmp eq i32 %tmp8, %b
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   br i1 %tmp9, label %ex, label %hd
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp5 = tail call i32 @g(i32* nonnull %a)
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   ret i32 %tmp5
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   tail call void @h(i32* %a)
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ]
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   br i1 %tmp3, label %ex, label %hd
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp3 = icmp eq i32 %b, 0
 ; MBEC-NEXT: -- Explore context of:   %tmp9 = icmp eq i32 %tmp8, %b
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp9 = icmp eq i32 %tmp8, %b
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   br i1 %tmp9, label %ex, label %hd
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp5 = tail call i32 @g(i32* nonnull %a)
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   ret i32 %tmp5
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp8 = add nuw i32 %tmp7, 1
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   tail call void @h(i32* %a)
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ]
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   br i1 %tmp3, label %ex, label %hd
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp3 = icmp eq i32 %b, 0
 ; MBEC-NEXT: -- Explore context of:   br i1 %tmp9, label %ex, label %hd
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   br i1 %tmp9, label %ex, label %hd
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp5 = tail call i32 @g(i32* nonnull %a)
 ; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   ret i32 %tmp5
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp9 = icmp eq i32 %tmp8, %b
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp8 = add nuw i32 %tmp7, 1
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   tail call void @h(i32* %a)
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ]
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   br i1 %tmp3, label %ex, label %hd
+; MBEC-NEXT:   [F: nonnull_exec_ctx_2]   %tmp3 = icmp eq i32 %b, 0
 en:
   %tmp3 = icmp eq i32 %b, 0
   br i1 %tmp3, label %ex, label %hd
 
 ex:
   %tmp5 = tail call i32 @g(i32* nonnull %a)
   ret i32 %tmp5
 
 hd:
   %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ]
   tail call void @h(i32* %a)
   %tmp8 = add nuw i32 %tmp7, 1
   %tmp9 = icmp eq i32 %tmp8, %b
   br i1 %tmp9, label %ex, label %hd
 }

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

; ATTRIBUTOR:   %B = tail call i32 @unkown_f(i32* nonnull dereferenceable(4) %ptr)
   br i1%c, label %if.true, label %if.false
 if.true:
 ; ATTRIBUTOR:   %C = tail call i32 @unkown_f(i32* nonnull dereferenceable(8) %ptr) 
   %C = tail call i32 @unkown_f(i32* %ptr)
 
 ; ATTRIBUTOR:   %D = tail call i32 @unkown_f(i32* nonnull dereferenceable(8) %ptr) 
   %D = tail call i32 @unkown_f(i32* dereferenceable(8) %ptr)
 
-; FIXME: This should be tail call i32 @unkown_f(i32* nonnull dereferenceable(8) %ptr) 
-;        Making must-be-executed-context backward exploration will fix this.
-; ATTRIBUTOR:   %E = tail call i32 @unkown_f(i32* nonnull dereferenceable(4) %ptr) 
+; ATTRIBUTOR:   %E = tail call i32 @unkown_f(i32* nonnull dereferenceable(8) %ptr)
   %E = tail call i32 @unkown_f(i32* %ptr)
 
   ret void
 
 if.false:
   ret void
 }
 

 
 ; ATTRIBUTOR:   %C = tail call i32 @unkown_f(i32* nonnull dereferenceable(8) %ptr) 
   %C = tail call i32 @unkown_f(i32* %ptr)
 
 ; ATTRIBUTOR:   %D = tail call i32 @unkown_f(i32* nonnull dereferenceable(8) %ptr) 
   %D = tail call i32 @unkown_f(i32* dereferenceable(8) %ptr)
 
   %E = tail call i32 @unkown_f(i32* %ptr)
-; FIXME: This should be @unkown_f(i32* nonnull dereferenceable(8) %ptr) 
-;        Making must-be-executed-context backward exploration will fix this.
-; ATTRIBUTOR:   %E = tail call i32 @unkown_f(i32* nonnull dereferenceable(4) %ptr)
+; ATTRIBUTOR:   %E = tail call i32 @unkown_f(i32* nonnull dereferenceable(8) %ptr)
 
   ret void
 
 if.false:
   ret void
 }
 
 define i32* @f7_3() {

llvm/test/Transforms/Attributor/heap_to_stack.ll

define void @test8() {
   %1 = tail call noalias i8* @malloc(i64 4)
   ; CHECK: %1 = tail call noalias i8* @malloc(i64 4)
   ; CHECK-NEXT: @no_sync_func(i8* nocapture nofree %1)
   tail call void @no_sync_func(i8* %1)
   %2 = bitcast i8* %1 to i32*
   store i32 10, i32* %2
   %3 = load i32, i32* %2
   tail call void @foo(i32* %2)
-  ; CHECK: @free(i8* %1)
+  ; CHECK: @free(i8* nonnull dereferenceable(4) %1)
   tail call void @free(i8* %1)
   ret void
 }
 
 ; TEST 9 - FIXME: malloc should be converted.
 define void @test9() {
   %1 = tail call noalias i8* @malloc(i64 4)
   ; CHECK: %1 = tail call noalias i8* @malloc(i64 4)
   ; CHECK-NEXT: @no_sync_func(i8* nocapture nofree %1)
   tail call void @no_sync_func(i8* %1)
   %2 = bitcast i8* %1 to i32*
   store i32 10, i32* %2
   %3 = load i32, i32* %2
   tail call void @foo_nounw(i32* %2)
-  ; CHECK: @free(i8* %1)
+  ; CHECK: @free(i8* nonnull dereferenceable(4) %1)
   tail call void @free(i8* %1)
   ret void
 }
 
 ; TEST 10 - 1 malloc, 1 free
 
 define i32 @test10() {
   %1 = tail call noalias i8* @malloc(i64 4)
define i32 @test13() {
   %1 = tail call noalias i8* @malloc(i64 256)
   ; CHECK: %1 = tail call noalias i8* @malloc(i64 256)
   ; CHECK-NEXT: @no_sync_func(i8* noalias nofree %1)
   tail call void @no_sync_func(i8* %1)
   %2 = bitcast i8* %1 to i32*
   store i32 10, i32* %2
   %3 = load i32, i32* %2
   tail call void @free(i8* %1)
-  ; CHECK: tail call void @free(i8* noalias %1)
+  ; CHECK: tail call void @free(i8* noalias nonnull dereferenceable(4) %1)
   ret i32 %3
 }
 
 define i32 @test_sle() {
   %1 = tail call noalias i8* @malloc(i64 -1)
   ; CHECK: %1 = tail call noalias i8* @malloc(i64 -1)
   ; CHECK-NEXT: @no_sync_func(i8* noalias nofree %1)
   tail call void @no_sync_func(i8* %1)
   %2 = bitcast i8* %1 to i32*
   store i32 10, i32* %2
   %3 = load i32, i32* %2
   tail call void @free(i8* %1)
-  ; CHECK: tail call void @free(i8* noalias %1)
+  ; CHECK: tail call void @free(i8* noalias nonnull dereferenceable(4) %1)
   ret i32 %3
 }
 
 define i32 @test_overflow() {
   %1 = tail call noalias i8* @calloc(i64 65537, i64 65537)
   ; CHECK: %1 = tail call noalias i8* @calloc(i64 65537, i64 65537)
   ; CHECK-NEXT: @no_sync_func(i8* noalias nofree %1)
   tail call void @no_sync_func(i8* %1)
   %2 = bitcast i8* %1 to i32*
   store i32 10, i32* %2
   %3 = load i32, i32* %2
   tail call void @free(i8* %1)
-  ; CHECK: tail call void @free(i8* noalias %1)
+  ; CHECK: tail call void @free(i8* noalias nonnull dereferenceable(4) %1)
   ret i32 %3
 }
 
 define void @test14() {
   %1 = tail call noalias i8* @calloc(i64 64, i64 4)
   ; CHECK: %1 = tail call noalias i8* @calloc(i64 64, i64 4)
   ; CHECK-NEXT: @no_sync_func(i8* noalias nofree %1)
   tail call void @no_sync_func(i8* %1)
define void @test15(i64 %S) {
   ret void
 }
 
 define void @test16a(i8 %v, i8** %P) {
   ; CHECK: %1 = alloca
   %1 = tail call noalias i8* @malloc(i64 4)
   ; CHECK-NEXT: store i8 %v, i8* %1
   store i8 %v, i8* %1
-  ; CHECK-NEXT: @no_sync_func(i8* noalias nocapture nofree %1)
+  ; CHECK-NEXT: @no_sync_func(i8* noalias nocapture nofree nonnull dereferenceable(1) %1)
   tail call void @no_sync_func(i8* %1)
   ; CHECK-NOT: @free(i8* %1)
-  tail call void @free(i8* %1)
+  tail call void @free(i8* nonnull dereferenceable(1) %1)
   ret void
 }
 
 define void @test16b(i8 %v, i8** %P) {
   ; CHECK: %1 = tail call noalias i8* @malloc(i64 4)
   %1 = tail call noalias i8* @malloc(i64 4)
   ; CHECK-NEXT: store i8* %1, i8** %P
   store i8* %1, i8** %P

llvm/test/Transforms/Attributor/misc.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes
 ; RUN: opt -S -attributor -attributor-disable=false < %s | FileCheck %s --check-prefixes=ALL,CHECK
 ; RUN: opt -S -aa-pipeline='basic-aa' -passes=attributor -attributor-disable=false -attributor-annotate-decl-cs < %s | FileCheck %s --check-prefixes=ALL,DECL_CS
 ;
 ; Mostly check we do not crash on these uses
 
 define internal void @internal(void (i8*)* %fp) {
 ; CHECK-LABEL: define {{[^@]+}}@internal
-; CHECK-SAME: (void (i8*)* [[FP:%.*]])
+; CHECK-SAME: (void (i8*)* nonnull [[FP:%.*]])
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    call void @foo(i32* nocapture nofree nonnull writeonly align 4 dereferenceable(4) [[A]])
 ; CHECK-NEXT:    call void [[FP]](i8* bitcast (void (i32*)* @foo to i8*))
 ; CHECK-NEXT:    call void @callback1(void (i32*)* nonnull @foo)
 ; CHECK-NEXT:    call void @callback2(void (i8*)* bitcast (void (i32*)* @foo to void (i8*)*))
 ; CHECK-NEXT:    call void @callback2(void (i8*)* [[FP]])
 ; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i32* [[A]] to i8*
 ; CHECK-NEXT:    call void [[FP]](i8* [[TMP1]])
 ; CHECK-NEXT:    ret void
 ;
 ; DECL_CS-LABEL: define {{[^@]+}}@internal
-; DECL_CS-SAME: (void (i8*)* [[FP:%.*]])
+; DECL_CS-SAME: (void (i8*)* nonnull [[FP:%.*]])
 ; DECL_CS-NEXT:  entry:
 ; DECL_CS-NEXT:    [[A:%.*]] = alloca i32, align 4
 ; DECL_CS-NEXT:    call void @foo(i32* nocapture nofree nonnull writeonly align 4 dereferenceable(4) [[A]])
 ; DECL_CS-NEXT:    call void [[FP]](i8* bitcast (void (i32*)* @foo to i8*))
 ; DECL_CS-NEXT:    call void @callback1(void (i32*)* nonnull @foo)
 ; DECL_CS-NEXT:    call void @callback2(void (i8*)* nonnull bitcast (void (i32*)* @foo to void (i8*)*))
-; DECL_CS-NEXT:    call void @callback2(void (i8*)* [[FP]])
+; DECL_CS-NEXT:    call void @callback2(void (i8*)* nonnull [[FP]])
 ; DECL_CS-NEXT:    [[TMP1:%.*]] = bitcast i32* [[A]] to i8*
 ; DECL_CS-NEXT:    call void [[FP]](i8* [[TMP1]])
 ; DECL_CS-NEXT:    ret void
 ;
 entry:
   %a = alloca i32, align 4
   %tmp = bitcast i32* %a to i8*
   call void @foo(i32* nonnull %a)

 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    call void @foo(i32* nocapture nofree nonnull writeonly align 4 dereferenceable(4) [[A]])
 ; CHECK-NEXT:    call void @callback1(void (i32*)* nonnull @foo)
 ; CHECK-NEXT:    call void @callback2(void (i8*)* bitcast (void (i32*)* @foo to void (i8*)*))
 ; CHECK-NEXT:    call void @callback2(void (i8*)* [[FP]])
 ; CHECK-NEXT:    call void [[FP]](i8* bitcast (void (i32*)* @foo to i8*))
 ; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i32* [[A]] to i8*
 ; CHECK-NEXT:    call void [[FP]](i8* [[TMP1]])
-; CHECK-NEXT:    call void @internal(void (i8*)* [[FP]])
+; CHECK-NEXT:    call void @internal(void (i8*)* nonnull [[FP]])
 ; CHECK-NEXT:    ret void
 ;
 ; DECL_CS-LABEL: define {{[^@]+}}@external
 ; DECL_CS-SAME: (void (i8*)* [[FP:%.*]])
 ; DECL_CS-NEXT:  entry:
 ; DECL_CS-NEXT:    [[A:%.*]] = alloca i32, align 4
 ; DECL_CS-NEXT:    call void @foo(i32* nocapture nofree nonnull writeonly align 4 dereferenceable(4) [[A]])
 ; DECL_CS-NEXT:    call void @callback1(void (i32*)* nonnull @foo)
 ; DECL_CS-NEXT:    call void @callback2(void (i8*)* nonnull bitcast (void (i32*)* @foo to void (i8*)*))
 ; DECL_CS-NEXT:    call void @callback2(void (i8*)* [[FP]])
 ; DECL_CS-NEXT:    call void [[FP]](i8* bitcast (void (i32*)* @foo to i8*))
 ; DECL_CS-NEXT:    [[TMP1:%.*]] = bitcast i32* [[A]] to i8*
 ; DECL_CS-NEXT:    call void [[FP]](i8* [[TMP1]])
-; DECL_CS-NEXT:    call void @internal(void (i8*)* [[FP]])
+; DECL_CS-NEXT:    call void @internal(void (i8*)* nonnull [[FP]])
 ; DECL_CS-NEXT:    ret void
 ;
 entry:
   %a = alloca i32, align 4
   %tmp = bitcast i32* %a to i8*
   call void @foo(i32* nonnull %a)
   call void @callback1(void (i32*)* nonnull @foo)
   call void @callback2(void (i8*)* bitcast (void (i32*)* @foo to void (i8*)*))

llvm/test/Transforms/Attributor/nonnull.ll

 bb4:                                              ; preds = %bb1
   %tmp5 = getelementptr inbounds i32, i32* %arg, i64 1
 ; ATTRIBUTOR: %tmp5b = tail call nonnull i32* @f3(i32* nofree nonnull readonly %tmp5)
   %tmp5b = tail call i32* @f3(i32* %tmp5)
   %tmp5c = getelementptr inbounds i32, i32* %tmp5b, i64 -1
   br label %bb9
 
 bb6:                                              ; preds = %bb1
-; FIXME: missing nonnull. It should be @f2(i32* nonnull %arg)
-; ATTRIBUTOR: %tmp7 = tail call nonnull i32* @f2(i32* nofree readonly %arg)
+; ATTRIBUTOR: %tmp7 = tail call nonnull i32* @f2(i32* nofree nonnull readonly align 4 dereferenceable(4) %arg)
   %tmp7 = tail call i32* @f2(i32* %arg)
   ret i32* %tmp7
 
 bb9:                                              ; preds = %bb4, %bb
   %tmp10 = phi i32* [ %tmp5c, %bb4 ], [ inttoptr (i64 4 to i32*), %bb ]
   ret i32* %tmp10
 }
 
 define internal i32* @f2(i32* %arg) {
-; FIXME: missing nonnull. It should be nonnull @f2(i32* nonnull %arg)
-; ATTRIBUTOR: define internal nonnull i32* @f2(i32* nofree readonly %arg)
+; ATTRIBUTOR: define internal nonnull i32* @f2(i32* nofree nonnull readonly align 4 dereferenceable(4) %arg)
 bb:
-
-; FIXME: missing nonnull. It should be @f1(i32* nonnull readonly %arg)
-; ATTRIBUTOR:   %tmp = tail call nonnull i32* @f1(i32* nofree readonly %arg)
+; ATTRIBUTOR:   %tmp = tail call nonnull i32* @f1(i32* nofree nonnull readonly align 4 dereferenceable(4) %arg)
   %tmp = tail call i32* @f1(i32* %arg)
   ret i32* %tmp
 }
 
 define dso_local noalias i32* @f3(i32* %arg) {
 ; FIXME: missing nonnull. It should be nonnull @f3(i32* nonnull readonly %arg)
 ; ATTRIBUTOR: define dso_local noalias nonnull i32* @f3(i32* nofree readonly %arg)
 bb: