[Attributor] Liveness analysis.

[sstefan1]

Summary

Liveness analysis abstract attribute used to indicate which BasicBlocks are dead and can therefore be ignored.
Right now we are only looking at noreturn calls.

[sstefan1]

I'm going to add tests tomorrow morning. Posted without so you can have a chance to take a look, as this is not yet complete in my opinion.

[jdoerfert]

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

727

Put that as a class comment.

731

Leftover /

735

I think we can/should use EndAttrKinds + X from now on.

738

You should probably take a basic block here and below with a description that says the beginning (or end) of that block is assumed dead.

llvm/lib/Transforms/IPO/Attributor.cpp

1030

We do not want an attribute. Later we might want to place llvm_unreachables but first we need to get the logic right.

1043

Asssumed dead!

1052

If we want to get loop info, we should get it through the attributor/infocache. For now, I'd not do any of this "infinite loop logic".

1101

Erasing while iterating will eventually explode. Keep a second set with "now life" blocks that need to be replaced or a new "StillAssumedDead" set.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

1019

While I proposed this method I think we can do something smarter. We can scan the function from the entry block (put the functionality somewhere as you need it again below) and mark blocks life that are reached on a path without a assumed or known noreturn function call. While doing so you want to record these function calls as well so we know what to look for in the update.

1083

This iteration order is expensive and not strictly necessary, in the worst case the first block has a noreturn call and you still make everything life.

I think you should perform a bit more analysis in the initialize (see above) and then:

• Check all calls we stopped at before because they had an assumed or known noreturn. If they still do, skip them.
• If they lost the assumed noreturn make every block reachable from the call life but stop at calls that are assumed or known noreturn and at already assumed life blocks. The calls that stopped the traversal go into the set that we traverse in the next update.

If I'm not mistaken, that should limit the traversal of this attribute to at most two visit of each instruction in the function.

1118

There is no optimistic fixpoint after a single update call because the information used above, e.g., isAssumedNoReturn, might change over time.

[sstefan1]

Addressed comments

[jdoerfert]

I guess we need to implement a manifest to make testing easier.

I'd propose the following in the manifest method:
Split the block that is dead after the phi-nodes (see splitBasicBlock) and replace the unconditional jump with a llvm_unreachable.

On second thought, maybe manifest should go through the list of noreturn calls and place llvm_unreachable after them. Later, we will
have more "sources" in addition to noreturn and then we introduce the unreachable after all of them.

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

723

I think these methods need to take a basic block and/or instruction.

llvm/lib/Transforms/IPO/Attributor.cpp

1018

You need to explore the function in a different way:
Keep a list of "to be expored" paths defined by instructions.
Start with the first instruction in the entry block as a first "to be explored path".
Continue to the next instruction if it is not a noreturn call.
If it is the last in the block, add all successors instructions to the "to be explored" path list.
Make sure you never follow a path/instruction twice.

The functionality above should live in a separate function as it will be needed in the update method as well.
Basically, update is the same thing but the start points are all noreturn calls that are not noreturn anymore.

1028

The code after the noreturn call is assumed dead but not the block.

[sstefan1]

• Change initialize, explore paths.

[jdoerfert]

This looks close to what I was hoping for. Some comments inlined.

llvm/lib/Transforms/IPO/Attributor.cpp

1024

I think the return value should indicate if you explored new instructions or not.

1058

I think they have a count method.

1088

You don't need to look at the whole block if you want to start at I.
You can go from instruction to instruction with I->getNextNode().

1096

known always implies assumed. So it is sufficient to check for assumed.

1108

for (BasicBlock *SuccBB : successors(BB)) {

1111

Keep an additional set or a SetVector to make this lookup cheap.

1139

I'm unsure if we need two sets here. I was hoping: "not in AssumedLive" means "assumed dead".

1170

Why do we need this logic. Above, you already explore exhaustively starting from old assumed noreturn instructions. I hoped that was enough.

1172

For now, I'd just return changed/unchanged. That can be determined by the return values of explorePath, e.g., if we did not explore any new instruction nothing has changed.

[sstefan1]

llvm/lib/Transforms/IPO/Attributor.cpp

1139

Agreed.

1170

This was mainly left over code from last diff. Should have been removed.

1172

I'm not sure I can just return unchanged after one false explore. I'd stick with this for now.

[sstefan1]

• addressing comments

[jdoerfert]

We need more tests, including but not limited to:

• Unreachable blocks.
• Dead blocks caused by something other than noreturn, e.g., infinite loops, recursion, undefined behavior etc. (these will be "FIXME" tests)
• An assumed noreturn call that is later not assumed noreturn anymore. (I'll work basic on no-return deduction now.)

llvm/lib/Transforms/IPO/Attributor.cpp

1103

I think any advance above, e.g., any new live instruction, should result in a ChangeStatus::CHANGED result from updateImpl.

1108

if (ToBeExploredPaths.insert(Inst).second)
 HasNewPath = true;

1130

You need to update the NoReturnCalls set. However, now you modify it while iterating, that is a problem.

1138

You can have new live blocks even if not all blocks are live.

[sstefan1]

• More tests.
• Small changes.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

1018

For now, we should mark the entry as live. (It would not if it contained a noreturn call right now -> test case)

1077

Leftover.

1094

Maybe make this two or three conditionals so it is easier to read. First exclude non call sites, then the ones marked noreturn, then the ones assumed noreturn.

1096

See the comment at the declaration. Basically, whenever we explored at least one instruction we have to report that back, e.g., to remove the NoReturnCall from the set.

1108

You do not need the count. Just insert it and check the return value if it was already there or if it was actually added.

1123

Do not use auto here. Not needed and not clear.

The NoReturnCalls are updated in explorePath so iterating over them while updating them is bad and will explode.

1135

Haven't we changed the "AssumedLiveSet" here already, when the size is different I mean.

1144

Just erase, no count necessary.

llvm/test/Transforms/FunctionAttrs/liveness.ll

15

Then do it and add the appropriate check lines :), here and in the other tests. It is an indirect test but it is better than nothing. So you will also need to use the liveness AA in the nosync AA.

92

I'm not sure what undefined behavior (UB) you mean here. Generally, we need something undefined that has a side-effect, e.g., a load null, or br undef.

148

you mean rec(). Also add this test again and do not call rec but testX where X is the number.

[sstefan1]

llvm/lib/Transforms/IPO/Attributor.cpp

1096

This is checked and removed in updateImpl. In other words, when starting point is a noreturn instruction and we found a new live instruction, that call is deleted from NoReturnCalls as it is not noreturn anymore.

1123

I Changed this a bit now to avoid updating while iterating.

1135

Good point. State should already be CHANGED at this point.

llvm/test/Transforms/FunctionAttrs/liveness.ll

15

Is it ok if I do this in a separate patch, once this and noreturn go in? In that patch I can update all attributes to use AAIsDead and update these tests accordingly.

This test is kind of already present in the cond.true block. foo which is not nosync is called after noreturn call. I'm just proposing to add CHECK lines and liveness usage to other attributes in separate patch.

92

This is supposed to be signed overflow. It is not called anywhere, but I agree it is not the best test case.

[sstefan1]

• addressing comments

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

999

I guess that calling this a function attribute (here and elsewhere) is not really the right thing to do but we do not have any concept that would fit better right now.

1028

maybe print something like:
"LiveBBs(" << AssumedLiveBlocks.size() << "/" << getAnchoredScope().size() << ")"

1103

Let's assume you get in here for an assumed noreturn call NC which is not assume noreturn anymore, you iterate over the block until you find one that is noreturn. In that case you return false above which would *not* remove the former assumed noreturn call NC from the NoReturnCalls set, causing us to introduce an unreachable at the end! You have to return true whenever the original instruction I is not assumed noreturn anymore, e.g., one you call I->getNextNode we cannot return false anymore

test case sketch

bb:
  call %assumed_noreturn_but_actually_return
  call %noreturn

[sstefan1]

llvm/lib/Transforms/IPO/Attributor.cpp

1103

Ok, I was wrong about this. Now it will return false only if we are looking at a noreturn call that is already in NoReturnCalls, in other words, still noreturn.

[sstefan1]

• explorePath now returns false only if starting point is a noreturn call that is still noreturn.

[jdoerfert]

Almost there, I think the tests need to be improved (check lines as noted below). Also, do we add the entry block to the live blocks?

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

723

Improve the comments of these functions (mention BB)

llvm/lib/Transforms/IPO/Attributor.cpp

1024

Improve the description and make sure it is actually what happens

1037

I don't think you should check the second condition because the associated value is not really important here anyway.

1044

We need a check with a noreturn invoke as it is a terminator that does not have a next node. Does this work?

1069

if known is true, assumed is true so no need for this second conditional.
The count condition here and above could just be: return !AssumedLiveBlocks.count(BB);

1090

Move the getAAFor into if (ICS) {

llvm/test/Transforms/FunctionAttrs/liveness.ll

15

OK.

One thing though: do not only check for the existence of an unreachable, it could be anywhere. Check the surroundings (function name, then basic block name, etc.) and use CHECK-NEXT: to make sure the CFG looks as expected.

[sstefan1]

• addressing comments.

[sstefan1]

• Rebased and added AANoReturn declaration.
• ninja check-all & test-suite passed fine.

[jdoerfert]

This looks generally fine to me. Some small comments that are easy to fix but on bigger request wrt. Invokes. After thinking about this I realized it is not as simple, and the code that already deals with this proved me right. We should reuse that logic to replace Invokes, or even better, to insert unreachables where possible. Take a look at the inlined comments and let me know if you encounter problems.

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

728

Remove the BooleanState part.

758

Just before you commit, make sure this is unique, thus no other attribute we comited in the meantime has EndAttrKinds + 1 as ID. I will come up with a "better" system soon.

llvm/lib/Transforms/IPO/Attributor.cpp

1045

Please make changeToCall(..) in llvm/lib/Transforms/Utils/Local.cpp visible to the outside (also rename it properly) and then use it. We do want to avoid duplication and changing invoke to call is not as simple as this.
We could even go further and expose the "insert unreachable" logic that is present in the Local.cpp such that you could call it here for each I.

1070

Get rid of these comments, also below.

1090

Make this a (Small)SetVector to ensure deterministic exploration. It is not strictly necessary for correctness but confusing if we get different results on a timeout. It also makes it harder to debug.

Also consider making the three members above private.

[sstefan1]

• Make changeToCall available from Local.h
• address comments

[jdoerfert]

Assuming you pass the llvm test suite and ninja check-all, this LGTM.

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

struct AANoAlias : public AbstractAttribute {
 
   /// See AbastractState::getAttrKind().
   Attribute::AttrKind getAttrKind() const override { return ID; }
 
   /// The identifier used by the Attributor for this class of attributes.
   static constexpr Attribute::AttrKind ID = Attribute::NoAlias;
 };
 
-struct AANoUnwind : public AbstractAttribute {
-    /// An abstract interface for all nosync attributes.
-    AANoUnwind(Value &V, InformationCache &InfoCache)
-        : AbstractAttribute(V, InfoCache) {}
+struct AANoUnwind : public AbstractAttribute {
+
+  /// See AbstractAttribute::AbstractAttribute(...).
 
-    /// See AbstractAttribute::getAttrKind()/
-    virtual Attribute::AttrKind getAttrKind() const override { return ID; }
 
-    static constexpr Attribute::AttrKind ID =
-        Attribute::AttrKind(Attribute::NoUnwind);
 
-    /// Returns true if nounwind is assumed.
-    virtual bool isAssumedNoUnwind() const = 0;
 
-    /// Returns true if nounwind is known.
-    virtual bool isKnownNoUnwind() const = 0;
 };
 
+/// An abstract interface for liveness abstract attribute.
+struct AAIsDead : public AbstractAttribute {
+
+  /// See AbstractAttribute::AbstractAttribute(...).
+  AAIsDead(Value &V, InformationCache &InfoCache)
+      : AbstractAttribute(V, InfoCache) {}
+
+  /// See AbstractAttribute::getAttrKind()
+  virtual Attribute::AttrKind getAttrKind() const override { return ID; }
+
+  static constexpr Attribute::AttrKind ID =
+      Attribute::AttrKind(Attribute::EndAttrKinds + 1);
+
+  /// Returns true if nounwind is assumed.
+  virtual bool isAssumedDead(BasicBlock *BB) const = 0;
+
+  /// Returns true if nounwind is known.
+  virtual bool isKnownDead(BasicBlock *BB) const = 0;
+};
+
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H

llvm/lib/Transforms/IPO/Attributor.cpp

 // attributes. This is done in an abstract interpretation style fixpoint
 // iteration. See the Attributor.h file comment and the class descriptions in
 // that file for more information.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/Attributor.h"
 
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include <cassert>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "attributor"
 
 STATISTIC(NumFnWithExactDefinition,
           "Number of function with exact definitions");
struct AANoReturnFunction final : public AANoReturn {
   }
 
   /// See AbstractAttribute::getManifestPosition().
   virtual ManifestPosition getManifestPosition() const override {
     return MP_FUNCTION;
   }
 };
 
+/// -------------------AAIsDead Function Attribute-----------------------
+
+struct AAIsDeadFunction : AAIsDead, BooleanState {
+
+  AAIsDeadFunction(Function &F, InformationCache &InfoCache)
+      : AAIsDead(F, InfoCache) {}
+
+  /// See AbstractAttribute::getState()
+  /// {
+  AbstractState &getState() override { return *this; }
+  const AbstractState &getState() const override { return *this; }
+  /// }
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    return MP_FUNCTION;
+  }
+
+  void initialize(Attributor &A) override {
+    Function &F = getAnchorScope();
+
+    ToBeExploredPaths.push_back(&(F.getEntryBlock().front()));
+    for (size_t i = 0; i < ToBeExploredPaths.size(); ++i)
+      explorePath(A, ToBeExploredPaths[i]);
+  }
+
+  /// True if path had no dead instructions.
+  bool explorePath(Attributor &A, Instruction *I);
+
+  const std::string getAsStr() const override {
+    return getAssumed() ? "dead" : "maybe-dead";
+  }
+
+  /// See AbstractAttribute::manifest(...).
+  ChangeStatus manifest(Attributor &A) override {
+    assert(getState().isValidState() &&
+           "Attempted to manifest an invalid state!");
+    assert(getAssociatedValue() &&
+           "Attempted to manifest an attribute without associated value!");
+
+    ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
+
+    for (Instruction *I : NoReturnCalls) {
+      auto *Unreachable = new UnreachableInst(I->getContext());
+      // Unreachable->insertAfter(I);
+      BasicBlock *BB = I->getParent();
+      SplitBlock(BB, I->getNextNode());
+      ReplaceInstWithInst(BB->getTerminator(), Unreachable);
+      HasChanged = ChangeStatus::CHANGED;
+    }
+
+    return HasChanged;
+  }
+
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override;
+
+  /// See AAIsDead::isAssumedDead().
+  bool isAssumedDead(BasicBlock *BB) const override {
+    if (!getAssumed())
+      return false;
+    if (AssumedDeadBlocks.find(BB) != AssumedDeadBlocks.end())
+      return true;
+    return false;
+  }
+
+  /// See AAIsDead::isKnownDead().
+  bool isKnownDead(BasicBlock *BB) const override {
+    if (!getKnown())
+      return false;
+    if (getKnown() != getAssumed())
+      return false;
+    if (AssumedDeadBlocks.find(BB) != AssumedDeadBlocks.end())
+      return true;
+    return false;
+  }
+
+  /// Map of to be explored paths.
+  SmallVector<Instruction *, 8> ToBeExploredPaths;
+
+  /// Collection of all assumed dead BasicBlocks.
+  DenseSet<BasicBlock *> AssumedDeadBlocks;
+
+  /// Collection of all assumed live BasicBlocks.
+  DenseSet<BasicBlock *> AssumedLiveBlocks;
+
+  /// Collection of calls with noreturn attribute, assumed or knwon.
+  DenseSet<Instruction *> NoReturnCalls;
+};
+
+bool AAIsDeadFunction::explorePath(Attributor &A, Instruction *I) {
+  BasicBlock *BB = I->getParent();
+
+  for (Instruction &Inst : *BB) {
+    ImmutableCallSite ICS(&Inst);
+    auto *NoReturnAA = A.getAAFor<AANoReturnFunction>(*this, Inst);
+
+    if (ICS) {
+      if ((NoReturnAA && (NoReturnAA->isAssumedNoReturn() ||
+                          NoReturnAA->isKnownNoReturn())) ||
+          ICS.hasFnAttr(Attribute::NoReturn)) {
+        NoReturnCalls.insert(&Inst);
+        return false;
+      }
+    }
+  }
+
+  // get new paths (reachable blocks).
+  Instruction *Terminator = BB->getTerminator();
+  unsigned NumSucc = Terminator->getNumSuccessors();
+
+  for (unsigned i = 0; i < NumSucc; ++i) {
+    Instruction *Inst = &(Terminator->getSuccessor(i)->front());
+    AssumedLiveBlocks.insert(Terminator->getSuccessor(i));
+    if (!is_contained(ToBeExploredPaths, Inst))
+      ToBeExploredPaths.push_back(Inst);
+  }
+  return true;
+}
+
+ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) {
+  Function &F = getAnchorScope();
+
+  for (auto *I : NoReturnCalls) {
+    size_t Size = ToBeExploredPaths.size();
+
+    // Still noreturn.
+    if (explorePath(A, I))
+      continue;
+
+    // No new paths.
+    if ((Size - ToBeExploredPaths.size()) == 0)
+      continue;
+
+    while(Size != ToBeExploredPaths.size())
+      explorePath(A, ToBeExploredPaths[Size++]);
+  }
+
+  // Remember DeadBlocks.
+  for (BasicBlock &BB : F)
+    if (AssumedLiveBlocks.find(&BB) == AssumedLiveBlocks.end())
+      // If it is not in live set, then it is dead.
+      AssumedDeadBlocks.insert(&BB);
+
+  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
+  auto Opcodes = {(unsigned)Instruction::Invoke, (unsigned)Instruction::Call,
+                  (unsigned)Instruction::CallBr};
+
+  /// Check if some other calls became noreturn in the mean time.
+  for (unsigned Opcode : Opcodes) {
+    for (Instruction *I : OpcodeInstMap[Opcode]) {
+      if (NoReturnCalls.find(I) != NoReturnCalls.end())
+        continue;
+
+      ImmutableCallSite ICS(I);
+      auto *NoReturnAA = A.getAAFor<AANoReturnFunction>(*this, *I);
+
+      if (ICS &&
+          (!NoReturnAA || !NoReturnAA->isAssumedNoReturn() ||
+           !NoReturnAA->isKnownNoReturn()) &&
+          !ICS.hasFnAttr(Attribute::NoReturn))
+        continue;
+
+      /// Check if we can assume this block to be live.
+      BasicBlock *BB = I->getParent();
+      for (BasicBlock *PredBB : predecessors(BB)) {
+        /// If atleast one block is live, current block is also live.
+        if (AssumedDeadBlocks.find(PredBB) != AssumedDeadBlocks.end()) {
+          AssumedDeadBlocks.erase(BB);
+          AssumedLiveBlocks.insert(BB);
+        }
+      }
+    }
+  }
+
+  if (AssumedDeadBlocks.size() != 0) {
+    indicateOptimisticFixpoint();
+    return ChangeStatus::CHANGED;
+  }
+
+  return ChangeStatus::UNCHANGED;
+}
+
 /// ----------------------------------------------------------------------------
 ///                               Attributor
 /// ----------------------------------------------------------------------------
 
 ChangeStatus Attributor::run() {
   // Initialize all abstract attributes.
   for (AbstractAttribute *AA : AllAbstractAttributes)
     AA->initialize(*this);
ChangeStatus Attributor::run() {
 
   return ManifestChange;
 }
 
 void Attributor::identifyDefaultAbstractAttributes(
     Function &F, InformationCache &InfoCache,
     DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist) {
 
+  // Check for dead BasicBlocks in every function.
+  registerAA(*new AAIsDeadFunction(F, InfoCache));
+
   // Return attributes are only appropriate if the return type is non void.
   Type *ReturnType = F.getReturnType();
   if (!ReturnType->isVoidTy()) {
     // Argument attribute "returned" --- Create only one per function even
     // though it is an argument attribute.
     if (!Whitelist || Whitelist->count(AAReturnedValues::ID))
       registerAA(*new AAReturnedValuesImpl(F, InfoCache));
 

llvm/test/Transforms/FunctionAttrs/liveness.ll

+; RUN: opt -attributor --attributor-disable=false -S < %s | FileCheck %s
+
+declare void @no_return_call() noreturn
+
+declare void @normal_call()
+
+declare i32 @foo()
+
+declare i32 @bar()
+
+; TEST 1: cond.true is dead, but cond.end is not, since cond.false is live
+
+; This is just an example. For example we can put a sync call in a
+; dead block and check if it is deduced.
+
+define i32 @dead_block_present(i32 %a) #0 {
+entry:
+  %cmp = icmp eq i32 %a, 0
+  br i1 %cmp, label %cond.true, label %cond.false
+
+cond.true:                                        ; preds = %entry
+  call void @no_return_call()
+  ; CHECK: unreachable
+  %call = call i32 @foo()
+  br label %cond.end
+
+cond.false:                                       ; preds = %entry
+  call void @normal_call()
+  %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 2: both cond.true and cond.false are dead, therfore cond.end is dead as well.
+
+define i32 @all_dead(i32 %a) #0 {
+entry:
+  %cmp = icmp eq i32 %a, 0
+  br i1 %cmp, label %cond.true, label %cond.false
+
+cond.true:                                        ; preds = %entry
+  call void @no_return_call()
+  ; CHECK: unreachable
+  %call = call i32 @foo()
+  br label %cond.end
+
+cond.false:                                       ; preds = %entry
+  call void @no_return_call()
+  ; CHECK: unreachable
+  %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
+}