[MustExec] Add simple backward support to MustBeExecutedContextExplorer

[uenoku]

Summary

This patch introduces backward support to MustBeExecutedContext. For a given program point P, MustBeExecutedContextExplorer will explore until one can't go backward(In this patch, the condition is that predecessor block is only one). While exploration, store the instruction to stack.

[jdoerfert]

This is not (a stripped down version of) the code in D64975 which does the same thing, correct?

[uenoku]

In D66753#1645572, @jdoerfert wrote:

This is not (a stripped down version of) the code in D64975 which does the same thing, correct?

Oh, I missed it;) That's fine.

llvm/include/llvm/Analysis/MustExecute.h

struct MustBeExecutedIterator {
   typedef const Instruction **pointer;
   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) {}
+      : Visited(Other.Visited), Backward(Other.Backward),
+        Explorer(Other.Explorer), CurInst(Other.CurInst) {}
 
   MustBeExecutedIterator(MustBeExecutedIterator &&Other)
-      : Visited(std::move(Other.Visited)), Explorer(Other.Explorer),
-        CurInst(Other.CurInst) {}
+      : Visited(std::move(Other.Visited)), Backward(std::move(Other.Backward)),
+        Explorer(Other.Explorer), CurInst(Other.CurInst) {}
 
   MustBeExecutedIterator &operator=(MustBeExecutedIterator &&Other) {
     if (this != &Other) {
       std::swap(Visited, Other.Visited);
+      std::swap(Backward, Other.Backward);
       std::swap(CurInst, Other.CurInst);
     }
     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.
+  /// Equality and inequality operators.
   ///{
   bool operator==(const MustBeExecutedIterator &Other) const {
-    return CurInst == Other.CurInst;
+    return CurInst == Other.CurInst && Backward == Other.Backward;
   }
 
   bool operator!=(const MustBeExecutedIterator &Other) const {
     return !(*this == Other);
   }
   ///}
 
   /// Return the underlying instruction.
private:
   /// \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 backward history from given program point to current instruction.
+  SmallVector<const Instruction *, 4> Backward;
+
   /// 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;
 
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 instruction 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 instruction
+  ///                        that is guaranteed to execute is determined.
+  const Instruction *
+  getMustBeExecutedPrevInstruction(MustBeExecutedIterator &It,
+                                   const Instruction *PP);
+
+
+  /// Store the instructions 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 traced backward.
+  void backwardToMustBeExecutedStartPoint(MustBeExecutedIterator &It,
+                                          const Instruction *PP);
+
   /// Parameter that limit the performed exploration. See the constructor for
   /// their meaning.
   ///{
   const bool ExploreInterBlock;
   ///}
 
 private:
   /// Map from instructions to associated must be executed iterators.

llvm/lib/Analysis/MustExecute.cpp

LLVM_DEBUG(
         dbgs() << "\tUnconditional terminator, continue with successor\n");
     return &PP->getSuccessor(0)->front();
   }
 
   LLVM_DEBUG(dbgs() << "\tNo join point found\n");
   return nullptr;
 }
 
+const Instruction *
+MustBeExecutedContextExplorer::getMustBeExecutedPrevInstruction(
+    MustBeExecutedIterator &It, const Instruction *PP) {
+  if (!PP)
+    return PP;
+  LLVM_DEBUG(dbgs() << "Find previous instruction for " << *PP << "\n");
+
+  // If we explore only inside a given basic block we stop at front of the
+  // block.
+  if (!ExploreInterBlock && &PP->getParent()->front() == PP) {
+    LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n");
+    return nullptr;
+  }
+
+  if (&PP->getParent()->front() == PP) {
+    if (const BasicBlock *PrevBB = PP->getParent()->getSinglePredecessor())
+      return PrevBB->getTerminator();
+
+    LLVM_DEBUG(dbgs() << "\tNot found single predecessor, done\n");
+
+    return nullptr;
+  }
+
+  const Instruction *PrevPP = PP->getPrevNode();
+
+  // Check if the previous instruction is guaranteed to transfer execution to
+  // the successor.
+  bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(PrevPP);
+  if (!TransfersExecution)
+    return nullptr;
+
+  return PrevPP;
+}
+
+void MustBeExecutedContextExplorer::backwardToMustBeExecutedStartPoint(
+    llvm::MustBeExecutedIterator &It, const llvm::Instruction *I) {
+  const Instruction *SuccInst;
+  DenseSet<const Instruction *> Visited;
+
+  do {
+    It.Backward.push_back(I);
+    SuccInst = I;
+    Visited.insert(SuccInst);
+    I = getMustBeExecutedPrevInstruction(It, I);
+  } while (I && !Visited.count(I));
+}
+
 MustBeExecutedIterator::MustBeExecutedIterator(
     MustBeExecutedContextExplorer &Explorer, const Instruction *I)
     : Explorer(Explorer), CurInst(I) {
   reset(I);
 }
 
 void MustBeExecutedIterator::reset(const Instruction *I) {
-  CurInst = I;
+
+  Backward.clear();
+  Explorer.backwardToMustBeExecutedStartPoint(*this, I);
+  CurInst = Backward.pop_back_val();
   Visited.clear();
-  Visited.insert(I);
+  Visited.insert(CurInst);
 }
 
 const Instruction *MustBeExecutedIterator::advance() {
   assert(CurInst && "Cannot advance an end iterator!");
   const Instruction *Next =
-      Explorer.getMustBeExecutedNextInstruction(*this, CurInst);
+      Backward.size()
+          ? Backward.pop_back_val()
+          : Explorer.getMustBeExecutedNextInstruction(*this, CurInst);
   if (Next && !Visited.insert(Next).second)
     Next = nullptr;
   return Next;
 }

llvm/test/Analysis/MustExecute/must_be_executed_context.ll

 ; 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-NOT:    call
 
   call void @B()
 ; MBEC:      -- Explore context of:   call void @B()
+; 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-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 @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 @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-NOT:    call
 
   call void @D()
 ; MBEC:      -- Explore context of:   call void @D()
+; 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 @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-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-NOT:    call
 
   call void @F() ; might not return!
 ; MBEC:      -- Explore context of:   call void @F()
+; MBEC-NEXT:   [F: simple_conditional]   call void @E()
 ; MBEC-NEXT:   [F: simple_conditional]   call void @F()
 ; 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-NOT:    call

 ; MBEC:      -- Explore context of: br
   br label %bb2
 
 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]   %.0 = phi i32 [ %arg, %bb ], [ %.0.be, %.backedge ]
 ; 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-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)
+; FIXME: Missing A (backward)
+
 ; MBEC:      -- Explore context of:   call void @C()
+; MBEC-NEXT:   [F: complex_loops_and_control]   %.0 = phi i32 [ %arg, %bb ], [ %.0.be, %.backedge ]
+; 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]   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-NOT:    call
 ; MBEC:      -- Explore context of: br
   br label %bb5

 
 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]   %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]   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-NOT:    call
 ; MBEC:      -- Explore context of: %tmp10
   %tmp10 = add nsw i32 %.0, 3
   %tmp11 = icmp eq i32 %tmp10, %arg1

 
 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]   %.1 = phi i32 [ %tmp10, %bb13 ], [ %tmp20, %bb19 ]
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp15 = add nsw i32 %.1, 1
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp16 = icmp eq i32 %tmp15, %arg1
+; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp16, label %bb17, label %bb18
 ; 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-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]   %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]   %.lcssa = phi i32 [ %tmp20, %bb19 ]
 ; MBEC-NEXT:   [F: complex_loops_and_control]   call void @F()
 ; 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)
+; FIXME: Missing A and B (backward)
 ; MBEC:      -- Explore context of:   call void @G()
+; 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]   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 label %bb23
 ; MBEC-NEXT:   [F: complex_loops_and_control]   call void @G()
 ; MBEC-NEXT:   [F: complex_loops_and_control]   ret void
 ; MBEC-NOT:    call
 ; MBEC:      -- Explore context of: ret
   ret void
 }
 
 declare void @A() nounwind willreturn