[Attributor][Fix] Resolve various liveness issues

[jdoerfert]

Summary

This contains various fixes:

• Explicitly determine and return the next noreturn instruction.
• If an invoke calls a noreturn function which is not nounwind we keep the unwind destination live. This also means we require an invoke. Though we can still add the unreachable to the normal destination block.
• Check if the return instructions are dead after we look for calls to avoid triggering an optimistic fixpoint in the presence of assumed liveness information.
• Make the interface work with "const" pointers.
• Some simplifications

While additional tests are included, full coverage is achieved only with
D59978.

[sstefan1]

LGTM.

llvm/lib/Transforms/IPO/Attributor.cpp

608 ↗

(On Diff #213196)

I run the clang-format and committed today, so this is not necessary.

https://reviews.llvm.org/rG7849e4163583288ea53837a4e463af472bfe5f02

[thakis]

msan reports an uninitialized read: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/34088/steps/check-llvm%20msan/logs/stdio

FAIL: LLVM :: Transforms/FunctionAttrs/liveness.ll (26259 of 32933)
******************** TEST 'LLVM :: Transforms/FunctionAttrs/liveness.ll' FAILED ********************
Script:
--
: 'RUN: at line 1';   /b/sanitizer-x86_64-linux-fast/build/llvm_build_msan/bin/opt -attributor --attributor-disable=false -S < /b/sanitizer-x86_64-linux-fast/build/llvm/test/Transforms/FunctionAttrs/liveness.ll | /b/sanitizer-x86_64-linux-fast/build/llvm_build_msan/bin/FileCheck /b/sanitizer-x86_64-linux-fast/build/llvm/test/Transforms/FunctionAttrs/liveness.ll
--
Exit Code: 2

Command Output (stderr):
--
==43047==WARNING: MemorySanitizer: use-of-uninitialized-value
    #0 0xe558f2 in llvm::CallSiteBase<llvm::Function const, llvm::BasicBlock const, llvm::Value const, llvm::User const, llvm::Use const, llvm::Instruction const, llvm::CallInst const, llvm::InvokeInst const, llvm::CallBrInst const, llvm::Use const*>::get(llvm::Value const*) /b/sanitizer-x86_64-linux-fast/build/llvm/include/llvm/IR/CallSite.h:74:18
    #1 0x5652b4f in CallSiteBase /b/sanitizer-x86_64-linux-fast/build/llvm/include/llvm/IR/CallSite.h:66:46
    #2 0x5652b4f in ImmutableCallSite /b/sanitizer-x86_64-linux-fast/build/llvm/include/llvm/IR/CallSite.h:904
    #3 0x5652b4f in AAReturnedValuesImpl::checkForallReturnedValues(std::__1::function<bool (llvm::Value&, llvm::SmallPtrSetImpl<llvm::ReturnInst*> const&)>&) const /b/sanitizer-x86_64-linux-fast/build/llvm/lib/Transforms/IPO/Attributor.cpp:723
    #4 0x5651e4a in getAssumedUniqueReturnValue /b/sanitizer-x86_64-linux-fast/build/llvm/lib/Transforms/IPO/Attributor.cpp:705:8
    #5 0x5651e4a in AAReturnedValuesImpl::manifest(llvm::Attributor&) /b/sanitizer-x86_64-linux-fast/build/llvm/lib/Transforms/IPO/Attributor.cpp:649
    #6 0x566ed94 in llvm::Attributor::run() /b/sanitizer-x86_64-linux-fast/build/llvm/lib/Transforms/IPO/Attributor.cpp:2450:36
    #7 0x567d1d8 in runAttributorOnModule(llvm::Module&) /b/sanitizer-x86_64-linux-fast/build/llvm/lib/Transforms/IPO/Attributor.cpp:2687:12
    #8 0x5688e9c in (anonymous namespace)::AttributorLegacyPass::runOnModule(llvm::Module&) /b/sanitizer-x86_64-linux-fast/build/llvm/lib/Transforms/IPO/Attributor.cpp:2710:12
    #9 0x5420abd in runOnModule /b/sanitizer-x86_64-linux-fast/build/llvm/lib/IR/LegacyPassManager.cpp:1750:27
    #10 0x5420abd in llvm::legacy::PassManagerImpl::run(llvm::Module&) /b/sanitizer-x86_64-linux-fast/build/llvm/lib/IR/LegacyPassManager.cpp:1863
    #11 0x9d06a7 in main /b/sanitizer-x86_64-linux-fast/build/llvm/tools/opt/opt.cpp:892:12
    #12 0x7f4b2ca602e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
    #13 0x907c59 in _start (/b/sanitizer-x86_64-linux-fast/build/llvm_build_msan/bin/opt+0x907c59)

SUMMARY: MemorySanitizer: use-of-uninitialized-value /b/sanitizer-x86_64-linux-fast/build/llvm/include/llvm/IR/CallSite.h:74:18 in llvm::CallSiteBase<llvm::Function const, llvm::BasicBlock const, llvm::Value const, llvm::User const, llvm::Use const, llvm::Instruction const, llvm::CallInst const, llvm::InvokeInst const, llvm::CallBrInst const, llvm::Use const*>::get(llvm::Value const*)
Exiting

That run was at r367856 so it already had r367793 which maybe was supposed to fix this.

Please take a look!

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

struct AAIsDead : public AbstractAttribute {
 
   /// See AbstractAttribute::getAttrKind()
   Attribute::AttrKind getAttrKind() const override { return ID; }
 
   static constexpr Attribute::AttrKind ID =
       Attribute::AttrKind(Attribute::EndAttrKinds + 1);
 
   /// Returns true if \p BB is assumed dead.
-  virtual bool isAssumedDead(BasicBlock *BB) const = 0;
+  virtual bool isAssumedDead(const BasicBlock *BB) const = 0;
 
   /// Returns true if \p BB is known dead.
-  virtual bool isKnownDead(BasicBlock *BB) const = 0;
+  virtual bool isKnownDead(const BasicBlock *BB) const = 0;
 
   /// Returns true if \p I is assumed dead.
-  virtual bool isAssumedDead(Instruction *I) const = 0;
+  virtual bool isAssumedDead(const Instruction *I) const = 0;
 
   /// Returns true if \p I is known dead.
-  virtual bool isKnownDead(Instruction *I) const = 0;
+  virtual bool isKnownDead(const Instruction *I) const = 0;
 
   /// This method is used to check if at least one instruction in a collection
   /// of instructions is live.
   template <typename T> bool isLiveInstSet(T begin, T end) const {
-    for (T I = begin; I != end; ++I) {
-      assert(isa<Instruction>(*I) && "It has to be collection of Instructions");
-      assert((*I)->getParent()->getParent() == &getAnchorScope() &&
+    for (const auto &I : llvm::make_range(begin, end)) {
+      assert(I->getFunction() == &getAnchorScope() &&
              "Instruction must be in the same anchor scope function.");
 
-      if (!isAssumedDead(*I))
+      if (!isAssumedDead(I))
         return true;
     }
 
     return false;
   }
 };
 
 /// An abstract interface for all dereferenceable attribute.

llvm/trunk/lib/Transforms/IPO/Attributor.cpp

ChangeStatus AAReturnedValuesImpl::updateImpl(Attributor &A) {
 
   auto *LivenessAA = A.getAAFor<AAIsDead>(*this, getAnchorScope());
 
   // Look at all returned call sites.
   for (auto &It : ReturnedValues) {
     SmallPtrSet<ReturnInst *, 2> &ReturnInsts = It.second;
     Value *RV = It.first;
 
-    // Ignore dead ReturnValues.
-    if (LivenessAA &&
-        !LivenessAA->isLiveInstSet(ReturnInsts.begin(), ReturnInsts.end()))
-      continue;
-
     LLVM_DEBUG(dbgs() << "[AAReturnedValues] Potentially returned value " << *RV
                       << "\n");
 
     // Only call sites can change during an update, ignore the rest.
     CallSite RetCS(RV);
     if (!RetCS)
       continue;
 
     // For now, any call site we see will prevent us from directly fixing the
     // state. However, if the information on the callees is fixed, the call
     // sites will be removed and we will fix the information for this state.
     HasCallSite = true;
 
+    // Ignore dead ReturnValues.
+    if (LivenessAA &&
+        !LivenessAA->isLiveInstSet(ReturnInsts.begin(), ReturnInsts.end())) {
+      LLVM_DEBUG(dbgs() << "[AAReturnedValues] all returns are assumed dead, "
+                           "skip it for now\n");
+      continue;
+    }
+
     // Try to find a assumed unique return value for the called function.
     auto *RetCSAA = A.getAAFor<AAReturnedValuesImpl>(*this, *RV);
     if (!RetCSAA) {
       if (!HasOverdefinedReturnedCalls)
         Changed = ChangeStatus::CHANGED;
       HasOverdefinedReturnedCalls = true;
       LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned call site (" << *RV
                         << ") with " << (RetCSAA ? "invalid" : "no")
struct AAIsDeadFunction : AAIsDead, BooleanState {
   ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
 
   void initialize(Attributor &A) override {
     Function &F = getAnchorScope();
 
     ToBeExploredPaths.insert(&(F.getEntryBlock().front()));
     AssumedLiveBlocks.insert(&(F.getEntryBlock()));
     for (size_t i = 0; i < ToBeExploredPaths.size(); ++i)
-      explorePath(A, ToBeExploredPaths[i]);
+      if (const Instruction *NextNoReturnI =
+              findNextNoReturn(A, ToBeExploredPaths[i]))
+        NoReturnCalls.insert(NextNoReturnI);
   }
 
-  /// Explores new instructions starting from \p I. If instruction is dead, stop
-  /// and return true if it discovered a new instruction.
-  bool explorePath(Attributor &A, Instruction *I);
+  /// Find the next assumed noreturn instruction in the block of \p I starting
+  /// from, thus including, \p I.
+  ///
+  /// The caller is responsible to monitor the ToBeExploredPaths set as new
+  /// instructions discovered in other basic block will be placed in there.
+  ///
+  /// \returns The next assumed noreturn instructions in the block of \p I
+  ///          starting from, thus including, \p I.
+  const Instruction *findNextNoReturn(Attributor &A, const Instruction *I);
 
   const std::string getAsStr() const override {
     return "LiveBBs(" + std::to_string(AssumedLiveBlocks.size()) + "/" +
            std::to_string(getAnchorScope().size()) + ")";
   }
 
   /// See AbstractAttribute::manifest(...).
   ChangeStatus manifest(Attributor &A) override {
     assert(getState().isValidState() &&
            "Attempted to manifest an invalid state!");
 
     ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
 
-    for (Instruction *I : NoReturnCalls) {
+    for (const Instruction *NRC : NoReturnCalls) {
+      Instruction *I = const_cast<Instruction *>(NRC);
       BasicBlock *BB = I->getParent();
+      Instruction *SplitPos = I->getNextNode();
 
-      /// Invoke is replaced with a call and unreachable is placed after it.
       if (auto *II = dyn_cast<InvokeInst>(I)) {
+        /// Invoke is replaced with a call and unreachable is placed after it if
+        /// the callee is nounwind and noreturn. Otherwise, we keep the invoke
+        /// and only place an unreachable in the normal successor.
+        if (Function *Callee = II->getCalledFunction()) {
+          auto *AANoUnw = A.getAAFor<AANoUnwind>(*this, *Callee);
+          if (Callee->hasFnAttribute(Attribute::NoUnwind) ||
+              (AANoUnw && AANoUnw->isAssumedNoUnwind())) {
+            LLVM_DEBUG(dbgs() << "[AAIsDead] Replace invoke with call inst\n");
             changeToCall(II);
             changeToUnreachable(BB->getTerminator(), /* UseLLVMTrap */ false);
-        LLVM_DEBUG(dbgs() << "[AAIsDead] Replaced invoke with call inst\n");
             continue;
           }
+        }
 
-      SplitBlock(BB, I->getNextNode());
+        BB = II->getNormalDest();
+        SplitPos = &BB->front();
+      }
+
+      SplitBlock(BB, SplitPos);
       changeToUnreachable(BB->getTerminator(), /* UseLLVMTrap */ false);
       HasChanged = ChangeStatus::CHANGED;
     }
 
     return HasChanged;
   }
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override;
 
   /// See AAIsDead::isAssumedDead(BasicBlock *).
-  bool isAssumedDead(BasicBlock *BB) const override {
+  bool isAssumedDead(const BasicBlock *BB) const override {
     assert(BB->getParent() == &getAnchorScope() &&
            "BB must be in the same anchor scope function.");
 
     if (!getAssumed())
       return false;
     return !AssumedLiveBlocks.count(BB);
   }
 
   /// See AAIsDead::isKnownDead(BasicBlock *).
-  bool isKnownDead(BasicBlock *BB) const override {
+  bool isKnownDead(const BasicBlock *BB) const override {
     return getKnown() && isAssumedDead(BB);
   }
 
   /// See AAIsDead::isAssumed(Instruction *I).
-  bool isAssumedDead(Instruction *I) const override {
+  bool isAssumedDead(const Instruction *I) const override {
     assert(I->getParent()->getParent() == &getAnchorScope() &&
            "Instruction must be in the same anchor scope function.");
 
     if (!getAssumed())
       return false;
 
     // If it is not in AssumedLiveBlocks then it for sure dead.
     // Otherwise, it can still be after noreturn call in a live block.
     if (!AssumedLiveBlocks.count(I->getParent()))
       return true;
 
     // If it is not after a noreturn call, than it is live.
-    if (!isAfterNoReturn(I))
-      return false;
-
-    // Definitely dead.
-    return true;
+    return isAfterNoReturn(I);
   }
 
   /// See AAIsDead::isKnownDead(Instruction *I).
-  bool isKnownDead(Instruction *I) const override {
+  bool isKnownDead(const Instruction *I) const override {
     return getKnown() && isAssumedDead(I);
   }
 
   /// Check if instruction is after noreturn call, in other words, assumed dead.
-  bool isAfterNoReturn(Instruction *I) const;
+  bool isAfterNoReturn(const Instruction *I) const;
 
   /// Collection of to be explored paths.
-  SmallSetVector<Instruction *, 8> ToBeExploredPaths;
+  SmallSetVector<const Instruction *, 8> ToBeExploredPaths;
 
   /// Collection of all assumed live BasicBlocks.
-  DenseSet<BasicBlock *> AssumedLiveBlocks;
+  DenseSet<const BasicBlock *> AssumedLiveBlocks;
 
   /// Collection of calls with noreturn attribute, assumed or knwon.
-  SmallSetVector<Instruction *, 4> NoReturnCalls;
+  SmallSetVector<const Instruction *, 4> NoReturnCalls;
 };
 
-bool AAIsDeadFunction::isAfterNoReturn(Instruction *I) const {
-  Instruction *PrevI = I->getPrevNode();
+bool AAIsDeadFunction::isAfterNoReturn(const Instruction *I) const {
+  const Instruction *PrevI = I->getPrevNode();
   while (PrevI) {
     if (NoReturnCalls.count(PrevI))
       return true;
     PrevI = PrevI->getPrevNode();
   }
   return false;
 }
 
-bool AAIsDeadFunction::explorePath(Attributor &A, Instruction *I) {
-  BasicBlock *BB = I->getParent();
+const Instruction *AAIsDeadFunction::findNextNoReturn(Attributor &A,
+                                                      const Instruction *I) {
+  const BasicBlock *BB = I->getParent();
+
+  // TODO: We should have a function that determines if an "edge" is dead.
+  //       Edges could be from an instruction to the next or from a terminator
+  //       to the successor. For now, we need to special case the unwind block
+  //       of InvokeInst below.
 
   while (I) {
     ImmutableCallSite ICS(I);
 
     if (ICS) {
-      auto *NoReturnAA = A.getAAFor<AANoReturn>(*this, *I);
-
-      if (NoReturnAA && NoReturnAA->isAssumedNoReturn()) {
-        if (!NoReturnCalls.insert(I))
-          // If I is already in the NoReturnCalls set, then it stayed noreturn
-          // and we didn't discover any new instructions.
-          return false;
-
-        // Discovered new noreturn call, return true to indicate that I is not
-        // noreturn anymore and should be deleted from NoReturnCalls.
-        return true;
+      // Regarless of the no-return property of an invoke instruction we only
+      // learn that the regular successor is not reachable through this
+      // instruction but the unwind block might still be.
+      if (auto *Invoke = dyn_cast<InvokeInst>(I)) {
+        // Use nounwind to justify the unwind block is dead as well.
+        auto *AANoUnw = A.getAAFor<AANoUnwind>(*this, *Invoke);
+        if (!AANoUnw || !AANoUnw->isAssumedNoUnwind()) {
+          AssumedLiveBlocks.insert(Invoke->getUnwindDest());
+          ToBeExploredPaths.insert(&Invoke->getUnwindDest()->front());
         }
-
-      if (ICS.hasFnAttr(Attribute::NoReturn)) {
-        if (!NoReturnCalls.insert(I))
-          return false;
-
-        return true;
       }
+
+      auto *NoReturnAA = A.getAAFor<AANoReturn>(*this, *I);
+      if (ICS.hasFnAttr(Attribute::NoReturn) ||
+          (NoReturnAA && NoReturnAA->isAssumedNoReturn()))
+        return I;
     }
 
     I = I->getNextNode();
   }
 
   // get new paths (reachable blocks).
-  for (BasicBlock *SuccBB : successors(BB)) {
-    Instruction *Inst = &(SuccBB->front());
+  for (const BasicBlock *SuccBB : successors(BB)) {
     AssumedLiveBlocks.insert(SuccBB);
-    ToBeExploredPaths.insert(Inst);
+    ToBeExploredPaths.insert(&SuccBB->front());
   }
 
-  return true;
+  // No noreturn instruction found.
+  return nullptr;
 }
 
 ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) {
   // Temporary collection to iterate over existing noreturn instructions. This
   // will alow easier modification of NoReturnCalls collection
-  SmallVector<Instruction *, 8> NoReturnChanged;
+  SmallVector<const Instruction *, 8> NoReturnChanged;
   ChangeStatus Status = ChangeStatus::UNCHANGED;
 
-  for (Instruction *I : NoReturnCalls)
+  for (const Instruction *I : NoReturnCalls)
     NoReturnChanged.push_back(I);
 
-  for (Instruction *I : NoReturnChanged) {
+  for (const Instruction *I : NoReturnChanged) {
     size_t Size = ToBeExploredPaths.size();
 
-    // Still noreturn.
-    if (!explorePath(A, I))
-      continue;
-
+    const Instruction *NextNoReturnI = findNextNoReturn(A, I);
+    if (NextNoReturnI != I) {
+      Status = ChangeStatus::CHANGED;
       NoReturnCalls.remove(I);
+      if (NextNoReturnI)
+        NoReturnCalls.insert(NextNoReturnI);
+    }
 
-    // At least one new path.
+    // Explore new paths.
+    while (Size != ToBeExploredPaths.size()) {
       Status = ChangeStatus::CHANGED;
-
-    // No new paths.
-    if (Size == ToBeExploredPaths.size())
-      continue;
-
-    // explore new paths.
-    while (Size != ToBeExploredPaths.size())
-      explorePath(A, ToBeExploredPaths[Size++]);
+      if (const Instruction *NextNoReturnI =
+              findNextNoReturn(A, ToBeExploredPaths[Size++]))
+        NoReturnCalls.insert(NextNoReturnI);
+    }
   }
 
   LLVM_DEBUG(
       dbgs() << "[AAIsDead] AssumedLiveBlocks: " << AssumedLiveBlocks.size()
              << " Total number of blocks: " << getAnchorScope().size() << "\n");
 
   return Status;
 }

llvm/trunk/test/Transforms/FunctionAttrs/liveness.ll

 ; RUN: opt -attributor --attributor-disable=false -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
+
 declare i32 @foo_noreturn() noreturn
 
 declare i32 @bar() nosync readnone
 
 ; CHECK: Function Attrs: nofree norecurse nounwind uwtable willreturn
 define i32 @volatile_load(i32*) norecurse nounwind uwtable {
   %2 = load volatile i32, i32* %0, align 4
   ret i32 %2
cond.false:                                       ; preds = %entry
   %call1 = call i32 @bar()
   br label %cond.end
 
 cond.end:                                         ; preds = %cond.false, %cond.true
   %cond = phi i32 [ %call, %cond.true ], [ %call1, %cond.false ]
   ret i32 %cond
 }
 
-; TEST 5 noreturn invoke instruction replaced by a call and an unreachable instruction
-; put after it.
+; TEST 5 noreturn invoke instruction with a unreachable normal successor block.
 
 ; CHECK: define i32 @invoke_noreturn(i32 %a)
 define i32 @invoke_noreturn(i32 %a) personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
 entry:
   %cmp = icmp eq i32 %a, 0
   br i1 %cmp, label %cond.true, label %cond.false
 
 cond.true:                                        ; preds = %entry
   call void @normal_call()
   %call = invoke i32 @foo_noreturn() to label %continue
             unwind label %cleanup
-  ; CHECK: call i32 @foo_noreturn()
-  ; CHECK-NEXT unreachable
+  ; CHECK:      %call = invoke i32 @foo_noreturn()
+  ; CHECK-NEXT:         to label %continue unwind label %cleanup
+
+cond.false:                                       ; preds = %entry
+  call void @normal_call()
+  %call1 = call i32 @bar()
+  br label %cond.end
+
+cond.end:                                         ; preds = %cond.false, %continue
+  %cond = phi i32 [ %call, %continue ], [ %call1, %cond.false ]
+  ret i32 %cond
+
+continue:
+  ; CHECK:      continue:
+  ; CHECK-NEXT: unreachable
+  br label %cond.end
+
+cleanup:
+  %res = landingpad { i8*, i32 }
+  catch i8* null
+  ret i32 0
+}
+
+; TEST 4.1 noreturn invoke instruction replaced by a call and an unreachable instruction
+; put after it.
+
+; CHECK: define i32 @invoke_noreturn_nounwind(i32 %a)
+define i32 @invoke_noreturn_nounwind(i32 %a) personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
+entry:
+  %cmp = icmp eq i32 %a, 0
+  br i1 %cmp, label %cond.true, label %cond.false
+
+cond.true:                                        ; preds = %entry
+  call void @normal_call()
+  %call = invoke i32 @foo_noreturn_nounwind() to label %continue
+            unwind label %cleanup
+  ; CHECK:      call i32 @foo_noreturn_nounwind()
+  ; CHECK-NEXT: unreachable
 
 cond.false:                                       ; preds = %entry
   call void @normal_call()
   %call1 = call i32 @bar()
   br label %cond.end
 
 cond.end:                                         ; preds = %cond.false, %continue
   %cond = phi i32 [ %call, %continue ], [ %call1, %cond.false ]
   ret i32 %cond
 
 continue:
   br label %cond.end
 
 cleanup:
   %res = landingpad { i8*, i32 }
   catch i8* null
   ret i32 0
 }
 
 ; TEST 6: Undefined behvior, taken from LangRef.
 ; FIXME: Should be able to detect undefined behavior.
 
-; CHECK define @ub(i32)
-define void @ub(i32* ) {
+; CHECK: define void @ub(i32* %0)
+define void @ub(i32* %0) {
   %poison = sub nuw i32 0, 1           ; Results in a poison value.
   %still_poison = and i32 %poison, 0   ; 0, but also poison.
   %poison_yet_again = getelementptr i32, i32* %0, i32 %still_poison
   store i32 0, i32* %poison_yet_again  ; Undefined behavior due to store to poison.
   ret void
 }
 
 define void @inf_loop() #0 {