[Attributor] Deduction based on recursive path exploration

[uenoku]

Summary

This is the next patch of D65593. This patch enables us to explore must-be-executed-context recursively.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

1067

Nit: Move right after follow uses in ctx.

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

451

We should investigate if it is sound to use assumed information in the exploration to catch this case.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

1064

What happens if there is a different terminator here? I mean do we handle them all correctly?

[uenoku]

llvm/lib/Transforms/IPO/Attributor.cpp

1064

Does "different terminator" mean like switch or other terminator? If you mean so, I think it can handle such cases.

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

451

I feel it is difficult to use assumed information in this deduction scheme.
I'll investigate more but I think it would be really complex reasoning to maintain the soundness.

If we don't consider the cost, I think running Attributor twice will be bug free and effective solution because we can easily use assume information of 1st iteration as known information of 2nd iteration.

[uenoku]

This patch traverses the same context multiple times so the cost might get huge.
I'll create something like a cache.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

1064

Yes, switch, ret, ..., need to be handled correctly

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

451

If we don't consider the cost, I think running Attributor twice will be bug free and effective solution because we can easily use assume information of 1st iteration as known information of 2nd iteration.

I'm not sure I follow but re-running does generally not solve the problem. We need optimistic initialization to solve problems, e.g., the dereferenceable deduction in this test case.

llvm/lib/Transforms/IPO/Attributor.cpp

static cl::opt<unsigned> DepRecInterval(
     cl::init(4));
 
 static cl::opt<bool> EnableHeapToStack("enable-heap-to-stack-conversion",
                                        cl::init(true), cl::Hidden);
 
 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.
 ///
 ///{
 ChangeStatus llvm::operator|(ChangeStatus l, ChangeStatus r) {
   return l == ChangeStatus::CHANGED ? l : r;
 }
 ChangeStatus llvm::operator&(ChangeStatus l, ChangeStatus r) {
   return l == ChangeStatus::UNCHANGED ? l : r;
for (unsigned u = 0; u < Uses.size(); ++u) {
         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();
-
-    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
     // context. ChildStates are created for its successors respectively.
     //
     // ParentS_1 = ChildS_{1, 1} /\ ChildS_{1, 2} /\ ... /\ ChildS_{1, n_1}
     // ParentS_2 = ChildS_{2, 1} /\ ChildS_{2, 2} /\ ... /\ ChildS_{2, n_2}
     //      ...
     // ParentS_m = ChildS_{m, 1} /\ ChildS_{m, 2} /\ ... /\ ChildS_{m, n_m}
     //
     // 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)
+    //    /* 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;
     //      }
-    //    else {
-    //      if (b) {
-    //        *ptr = 0;
-    //      } else {
-    //        *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;
 
       // 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);
+        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);
 
         ParentState &= ChildState;
       }
 
       // 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;
   }
 
 private:
   /// Container for (transitive) uses of the associated value.
   SetVector<const Use *> Uses;
 };

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

 ;    } else {
 ;      if (c)
 ;        *ptr = 3;
 ;      else
 ;        *ptr = 4;
 ;    }
 ;  }
 ;
-; 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
   br i1 %tobool, label %if.else3, label %if.then
 
 if.then:                                          ; preds = %entry
   %tobool1 = icmp eq i32 %b, 0
   br i1 %tobool1, label %if.else, label %if.then2
if.else3:                                         ; preds = %entry
   br i1 %tobool4, label %if.else6, label %if.then5
 
 if.then5:                                         ; preds = %if.else3
   store i32 3, i32* %ptr, align 4
   br label %if.end8
 
 if.else6:                                         ; preds = %if.else3
   tail call void @rec-branch-2(i32 1, i32 1, i32 1, i32* %ptr)
   br label %if.end8
 
 if.end8:                                          ; preds = %if.then5, %if.else6, %if.then2, %if.else
   ret void
 }
 
 !0 = !{i64 10, i64 100}
 

llvm/test/Transforms/Attributor/nonnull.ll

 ; 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
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 declare nonnull i8* @ret_nonnull()