[Attributor][MustExecute] Use optimistic information in MustBeExecutedContextExplorer

[jdoerfert]

Summary

NOTE: This is a prototype. We need a way to keep MustBeExecutedContextExplorer updates separate from other updates so they can continue on, then this should help.

This allows optimistic information to be used to answer the question if
a call returns. This will also record dependences between attributes
using the explorer and AAWillReturn/AANoUnwind that are used to improve
the IR information. If the latter ever get fixed, the updates of the
former are triggered and we have better known information available.

llvm/include/llvm/Analysis/MustExecute.h

 
 #ifndef LLVM_ANALYSIS_MUSTEXECUTE_H
 #define LLVM_ANALYSIS_MUSTEXECUTE_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/Analysis/InstructionPrecedenceTracking.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instruction.h"
 
 namespace llvm {
 
 class Instruction;
 class DominatorTree;

 /// "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 {
+  using IsGuaranteedToTransferFnTy = std::function<bool(const Instruction *)>;
 
   /// 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.
   MustBeExecutedContextExplorer(bool ExploreInterBlock)
-      : ExploreInterBlock(ExploreInterBlock), EndIterator(*this, nullptr) {}
+      : ExploreInterBlock(ExploreInterBlock), EndIterator(*this, nullptr),
+        IsGuaranteedToTransferFn([](const Instruction *I) {
+          return isGuaranteedToTransferExecutionToSuccessor(I);
+        }) {}
 
   /// Clean up the dynamically allocated iterators.
   ~MustBeExecutedContextExplorer() {
     DeleteContainerSeconds(InstructionIteratorMap);
   }
 
   /// Iterator-based interface. \see MustBeExecutedIterator.
   ///{
getMustBeExecutedNextInstruction(MustBeExecutedIterator &It,
                                    const Instruction *PP);
 
   /// Parameter that limit the performed exploration. See the constructor for
   /// their meaning.
   ///{
   const bool ExploreInterBlock;
   ///}
 
+  /// Replace the function that determines if an instruction "terminates" with
+  /// \p IsGuaranteedToTransferFn.
+  void setIsGuaranteedToTransferFn(
+      IsGuaranteedToTransferFnTy IsGuaranteedToTransferFn) {
+    this->IsGuaranteedToTransferFn = IsGuaranteedToTransferFn;
+  }
+
 private:
   /// Map from instructions to associated must be executed iterators.
   DenseMap<const Instruction *, MustBeExecutedIterator *>
       InstructionIteratorMap;
 
   /// A unique end iterator.
   MustBeExecutedIterator EndIterator;
+
+  /// The callback to determines if a function *will* tranfer execution to its
+  /// successor. By default isGuaranteedToTransferExecutionToSuccessor(const
+  /// Instruction *) in ValueTracking.h.
+  IsGuaranteedToTransferFnTy IsGuaranteedToTransferFn;
 };
 
 } // namespace llvm
 
 #endif

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

struct AbstractState {
   /// if information changes as it cannot change itself.
   virtual bool isAtFixpoint() const = 0;
 
   /// Indicate that the abstract state should converge to the optimistic state.
   ///
   /// This will usually make the optimistically assumed state the known to be
   /// true state.
   ///
-  /// \returns ChangeStatus::UNCHANGED as the assumed value should not change.
+  /// \returns ChangeStatus::CHANGED as the known value should have changed.
   virtual ChangeStatus indicateOptimisticFixpoint() = 0;
 
   /// Indicate that the abstract state should converge to the pessimistic state.
   ///
   /// This will usually revert the optimistically assumed state to the known to
   /// be true state.
   ///
-  /// \returns ChangeStatus::CHANGED as the assumed value may change.
+  /// \returns ChangeStatus::CHANGED as the assumed value should have change.
   virtual ChangeStatus indicatePessimisticFixpoint() = 0;
 };
 
 /// Simple state with integers encoding.
 ///
 /// The interface ensures that the assumed bits are always a subset of the known
 /// bits. Users can only add known bits and, except through adding known bits,
 /// they can only remove assumed bits. This should guarantee monotoniticy and
struct IntegerState : public AbstractState {
   bool isValidState() const override { return Assumed != getWorstState(); }
 
   /// See AbstractState::isAtFixpoint()
   bool isAtFixpoint() const override { return Assumed == Known; }
 
   /// See AbstractState::indicateOptimisticFixpoint(...)
   ChangeStatus indicateOptimisticFixpoint() override {
     Known = Assumed;
-    return ChangeStatus::UNCHANGED;
+    return ChangeStatus::CHANGED;
   }
 
   /// See AbstractState::indicatePessimisticFixpoint(...)
   ChangeStatus indicatePessimisticFixpoint() override {
     Assumed = Known;
     return ChangeStatus::CHANGED;
   }
 
bool isAtFixpoint() const override {
     return !isValidState() ||
            (DerefBytesState.isAtFixpoint() && GlobalState.isAtFixpoint());
   }
 
   /// See AbstractState::indicateOptimisticFixpoint(...)
   ChangeStatus indicateOptimisticFixpoint() override {
     DerefBytesState.indicateOptimisticFixpoint();
     GlobalState.indicateOptimisticFixpoint();
-    return ChangeStatus::UNCHANGED;
+    return ChangeStatus::CHANGED;
   }
 
   /// See AbstractState::indicatePessimisticFixpoint(...)
   ChangeStatus indicatePessimisticFixpoint() override {
     DerefBytesState.indicatePessimisticFixpoint();
     GlobalState.indicatePessimisticFixpoint();
     return ChangeStatus::CHANGED;
   }

llvm/lib/Analysis/MustExecute.cpp

 //===- MustExecute.cpp - Printer for isGuaranteedToExecute ----------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/MustExecute.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/Passes.h"
-#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/AssemblyAnnotationWriter.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/FormattedStream.h"
 #include "llvm/Support/raw_ostream.h"
MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction(
   if (!ExploreInterBlock && PP->isTerminator()) {
     LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n");
     return nullptr;
   }
 
   // If we do not traverse the call graph we check if we can make progress in
   // the current function. First, check if the instruction is guaranteed to
   // transfer execution to the successor.
-  bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(PP);
+  bool TransfersExecution = IsGuaranteedToTransferFn(PP);
   if (!TransfersExecution)
     return nullptr;
 
   // If this is not a terminator we know that there is a single instruction
   // after this one that is executed next if control is transfered. If not,
   // we can try to go back to a call site we entered earlier. If none exists, we
   // do not know any instruction that has to be executd next.
   if (!PP->isTerminator()) {

llvm/lib/Transforms/IPO/Attributor.cpp

ChangeStatus updateImpl(Attributor &A) override {
     auto &S = this->getState();
     Instruction *CtxI = this->getIRPosition().getCtxI();
     if (!CtxI)
       return ChangeStatus::UNCHANGED;
 
     MustBeExecutedContextExplorer &Explorer =
         A.getInfoCache().getMustBeExecutedContextExplorer();
 
+    Explorer.setIsGuaranteedToTransferFn([&](const Instruction *I) {
+      if (isGuaranteedToTransferExecutionToSuccessor(I))
+        return true;
+      ImmutableCallSite ICS(I);
+      if (!ICS)
+        return false;
+      // We do look at known information not yet in the IR but we also establish
+      // a dependence which will trigger this update again if the information
+      // changed.
+      const IRPosition &CSPos = IRPosition::callsite_function(ICS);
+      bool WillReturn = ICS.hasFnAttr(Attribute::WillReturn);
+      if (!WillReturn)
+        WillReturn = A.getAAFor<AAWillReturn>(*this, CSPos).isKnownWillReturn();
+      bool NoUnwind = ICS.hasFnAttr(Attribute::NoUnwind);
+      if (!NoUnwind)
+        NoUnwind = A.getAAFor<AANoUnwind>(*this, CSPos).isKnownNoUnwind();
+      return WillReturn && NoUnwind;
+    });
+
     SetVector<const Use *> NextUses;
 
     for (const Use *U : Uses) {
       if (const Instruction *UserI = dyn_cast<Instruction>(U->getUser())) {
         auto EIt = Explorer.begin(CtxI), EEnd = Explorer.end(CtxI);
         bool Found = EIt.count(UserI);
         while (!Found && ++EIt != EEnd)
           Found = EIt.getCurrentInst() == UserI;
public:
   bool isAtFixpoint() const override { return IsFixed; }
 
   /// See AbstractState::isValidState().
   bool isValidState() const override { return IsValidState; }
 
   /// See AbstractState::indicateOptimisticFixpoint(...).
   ChangeStatus indicateOptimisticFixpoint() override {
     IsFixed = true;
-    return ChangeStatus::UNCHANGED;
+    return ChangeStatus::CHANGED;
   }
 
   ChangeStatus indicatePessimisticFixpoint() override {
     IsFixed = true;
     IsValidState = false;
     return ChangeStatus::CHANGED;
   }
 };

llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll

 
 ; TEST captured through write
 ;
 ; void negative_test_not_captured_but_returned_call_0b(long *a) {
 ;   *a = (long)not_captured_but_returned_0(a);
 ; }
 ;
 ; There should *not* be a no-capture attribute on %a
-; CHECK: define void @negative_test_not_captured_but_returned_call_0b(i64* writeonly %a)
+; CHECK: define void @negative_test_not_captured_but_returned_call_0b(i64* nonnull writeonly dereferenceable(8) %a)
 define void @negative_test_not_captured_but_returned_call_0b(i64* %a) #0 {
 entry:
   %call = call i64* @not_captured_but_returned_0(i64* %a)
   %0 = ptrtoint i64* %call to i64
   store i64 %0, i64* %a, align 8
   ret void
 }
 

llvm/test/Transforms/FunctionAttrs/liveness.ll

-; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=5 -S < %s | FileCheck %s
+; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=6 -S < %s | FileCheck %s
 
 declare void @no_return_call() nofree noreturn nounwind readnone
 
 declare void @normal_call() readnone
 
 declare i32 @foo()
 
 declare i32 @foo_noreturn_nounwind() noreturn nounwind

llvm/test/Transforms/FunctionAttrs/nonnull.ll

 }
 define void @make_live(i32* nonnull dereferenceable(8) %a) {
   call void @naked(i32* nonnull dereferenceable(8) align 16 %a)
   call void @control(i32* nonnull dereferenceable(8) align 16 %a)
   call void @optnone(i32* nonnull dereferenceable(8) align 16 %a)
   ret void
 }
 
+declare void @unknown_willreturn() willreturn nounwind
+define void @step_willreturn() {
+  call void @unknown_willreturn()
+  ret void
+}
+; ATTRIBUTOR: define internal i32 @deref_arg_delayed(i32* nocapture nonnull readonly dereferenceable(4) %D)
+define internal i32 @deref_arg_delayed(i32* %D) {
+  call void @step_willreturn()
+  %v = load i32, i32* %D
+  ret i32 %v
+}
+; FIXME: We should do arg -> call site arg deduction *for known information*
+; ATTRIBUTOR: define i32 @extern_deref_arg_use(i32* nocapture readonly %P)
+define i32 @extern_deref_arg_use(i32* %P) {
+  %v = call i32 @deref_arg_delayed(i32* %P)
+  ret i32 %v
+}
+
 attributes #0 = { "null-pointer-is-valid"="true" }
 attributes #1 = { nounwind willreturn}