Index: llvm/lib/Transforms/IPO/Attributor.cpp
===================================================================
--- llvm/lib/Transforms/IPO/Attributor.cpp
+++ llvm/lib/Transforms/IPO/Attributor.cpp
@@ -183,6 +183,10 @@
 static cl::opt<int> MaxHeapToStackSize("max-heap-to-stack-size", cl::init(128),
                                        cl::Hidden);
 
+static cl::opt<unsigned>
+    MaxPathExplorationRecursionDepth("max-path-exploration-recursion-depth",
+                                     cl::init(3), cl::Hidden);
+
 /// Logic operators for the change status enum class.
 ///
 ///{
@@ -997,31 +1001,14 @@
     }
   }
 
-  /// 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();
-
-    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
+  /// Modify State \p S according to the known information in
+  /// must-be-executed-context of \p CtxI.
+  void explorePathRecursively(Attributor &A,
+                              MustBeExecutedContextExplorer &Explorer,
+                              const Instruction *CtxI, StateType &S,
+                              SetVector<const Use *> Uses,
+                              unsigned RecursionDepth) {
+    // Here, we 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. Let ParentState_i be a state
     // to indicate the known information for an i-th branch instruction in the
@@ -1034,25 +1021,51 @@
     //
     // Known State |= ParentS_1 \/ ParentS_2 \/... \/ ParentS_m
     //
-    // FIXME: Currently, recursive branches are not handled. For example, we
-    // can't deduce that ptr must be dereferenced in below function.
+    // We recursively apply this function for branches in the child context.
     //
+    // For example,
     // void f(int a, int c, int *ptr) {
-    //    if(a)
-    //      if (b) {
-    //        *ptr = 0;
-    //      } else {
-    //        *ptr = 1;
-    //      }
-    //    else {
+    //    /* State P */
+    //    if(a) {
+    //      /* State P_1 */
     //      if (b) {
-    //        *ptr = 0;
+    //        /* State P_{1, 1} := ptr is dereferenceable(8) */
+    //        ptr[0] = 0;
+    //        ptr[1] = 1;
     //      } else {
+    //        /* State P_{1, 2} := ptr is dereferenceable(4) */
     //        *ptr = 1;
     //      }
+    //      /* P_1 = P_{1, 1} /\ P_{1, 2}
+    //             := ptr is dereferenceable(4) */
+    //    } else {
+    //      /* State P_2 */
+    //      ptr[0] = 0;
+    //      ptr[1] = 0;
+    //      /* P_2 := ptr is dereferenceable(8) */
     //    }
+    //    /* P = P_1 /\ P2
+    //        := ptr is dereferenceable(4)
     // }
 
+    if (RecursionDepth == MaxPathExplorationRecursionDepth) {
+      S.indicatePessimisticFixpoint();
+      return;
+    }
+
+    followUsesInContext(A, Explorer, CtxI, Uses, S);
+
+    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;
+    };
+
+    if (S.isAtFixpoint())
+      return;
+
     Explorer.checkForAllContext(CtxI, Pred);
     for (const BranchInst *Br : BrInsts) {
       StateType ParentState;
@@ -1065,9 +1078,10 @@
         StateType ChildState;
 
         size_t BeforeSize = Uses.size();
-        followUsesInContext(A, Explorer, &BB->front(), Uses, ChildState);
+        explorePathRecursively(A, Explorer, &BB->front(), ChildState, Uses,
+                               RecursionDepth + 1);
 
-        // Erase uses which only appear in the child.
+        // Erase uses which only appear in the child path.
         for (auto It = Uses.begin() + BeforeSize; It != Uses.end();)
           It = Uses.erase(It);
 
@@ -1077,6 +1091,21 @@
       // Use only known state.
       S += ParentState;
     }
+  }
+
+  /// 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();
+
+    explorePathRecursively(A, Explorer, CtxI, S, Uses,
+                           /* RecursionDepth */ 0);
 
     return BeforeState == S ? ChangeStatus::UNCHANGED : ChangeStatus::CHANGED;
   }
Index: llvm/test/Transforms/Attributor/dereferenceable-1.ll
===================================================================
--- llvm/test/Transforms/Attributor/dereferenceable-1.ll
+++ llvm/test/Transforms/Attributor/dereferenceable-1.ll
@@ -372,8 +372,7 @@
 ;    }
 ;  }
 ;
-; FIXME: %ptr should be dereferenceable(4)
-; ATTRIBUTOR: define dso_local void @rec-branch-1(i32 %a, i32 %b, i32 %c, i32* nocapture nofree writeonly %ptr)
+; ATTRIBUTOR: define dso_local void @rec-branch-1(i32 %a, i32 %b, i32 %c, i32* nocapture nofree nonnull writeonly align 4 dereferenceable(4) %ptr)
 define dso_local void @rec-branch-1(i32 %a, i32 %b, i32 %c, i32* %ptr) {
 entry:
   %tobool = icmp eq i32 %a, 0
Index: llvm/test/Transforms/Attributor/nonnull.ll
===================================================================
--- llvm/test/Transforms/Attributor/nonnull.ll
+++ llvm/test/Transforms/Attributor/nonnull.ll
@@ -1,6 +1,6 @@
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes
-; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=4 -S < %s | FileCheck %s --check-prefixes=ATTRIBUTOR,ATTRIBUTOR_OPM
-; RUN: opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=5 -S < %s | FileCheck %s --check-prefixes=ATTRIBUTOR,ATTRIBUTOR_NPM
+; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=6 -S < %s | FileCheck %s --check-prefixes=ATTRIBUTOR,ATTRIBUTOR_OPM
+; RUN: opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=6 -S < %s | FileCheck %s --check-prefixes=ATTRIBUTOR,ATTRIBUTOR_NPM
 ; Copied from Transforms/FunctoinAttrs/nonnull.ll
 
 ; UTC_ARGS: --disable