[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

705

Put that as a class comment.

709

Leftover /

713

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

716

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

1028

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

1041

Asssumed dead!

1050

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".

1099

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

1017

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.

1081

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.

1116

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

702

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

llvm/lib/Transforms/IPO/Attributor.cpp

1016

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.

1026

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

1022

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

1056

I think they have a count method.

1086

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().

1094

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

1106

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

1109

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

1137

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

1168

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

1170

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

1137

Agreed.

1168

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

1170

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

1101

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

1106

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

1128

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

1136

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

1016

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

1075

Leftover.

1092

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.

1094

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.

1106

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.

1121

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.

1133

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

1142

Just erase, no count necessary.

llvm/test/Transforms/FunctionAttrs/liveness.ll

14 ↗

(On Diff #209982)

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.

91 ↗

(On Diff #209982)

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.

147 ↗

(On Diff #209982)

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

1094

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.

1121

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

1133

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

llvm/test/Transforms/FunctionAttrs/liveness.ll

14 ↗

(On Diff #209982)

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.

91 ↗

(On Diff #209982)

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

997

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.

1026

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

1101

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

1101

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

702

Improve the comments of these functions (mention BB)

llvm/lib/Transforms/IPO/Attributor.cpp

1022

Improve the description and make sure it is actually what happens

1035

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

1042

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

1067

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);

1088

Move the getAAFor into if (ICS) {

llvm/test/Transforms/FunctionAttrs/liveness.ll

14 ↗

(On Diff #209982)

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

706

Remove the BooleanState part.

736

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

1043

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.

1068

Get rid of these comments, also below.

1088

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 AANoUnwind : public AbstractAttribute {
     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;
 };
 
+struct AAIsDead : public AbstractAttribute {
+    /// An abstract interface for liveness abstract attribute.
+    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::None + 1);
+
+    /// Returns true if nounwind is assumed.
+    virtual bool isAssumedDead() const = 0;
+
+    /// Returns true if nounwind is known.
+    virtual bool isKnownDead() const = 0;
+};
+
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H

llvm/lib/Transforms/IPO/Attributor.cpp

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();
+
+    for (BasicBlock &BB : F)
+      DeadBlocks.push_back(&BB);
+  }
+
+  virtual const std::string getAsStr() const override {
+    return getAssumed() ? "dead" : "maybe-dead";
+  }
+
+  /// Return deduced attributes in \p Attrs.
+  virtual void
+  getDeducedAttributes(SmallVectorImpl<Attribute> &Attrs) const override {
+    LLVMContext &Ctx = AnchoredVal.getContext();
+    Attrs.emplace_back(Attribute::get(Ctx, "assumeddead"));
+  }
+
+  /// See AbstractAttribute::updateImpl(...).
+  virtual ChangeStatus updateImpl(Attributor &A) override;
+
+  /// See AAIsDead::isAssumedDead().
+  virtual bool isAssumedDead() const override { return getAssumed(); }
+
+  /// See AAIsDead::isKnownDead().
+  virtual bool isKnownDead() const override { return getKnown(); }
+
+  /// Collection of all dead BasicBlocks.
+  SmallVector<BasicBlock *, 8> DeadBlocks;
+
+  /// Helper function to get LoopInfo for a Function.
+  static LoopInfoBase<BasicBlock, Loop> getLoopInfo(Function &F);
+
+  /// Get first infinite loop in a funciton, if it exists.
+  static Loop *getInfLoop(LoopInfoBase<BasicBlock, Loop> LoopInfo);
+};
+
+LoopInfoBase<BasicBlock, Loop> AAIsDeadFunction::getLoopInfo(Function &F) {
+  auto DT = DominatorTree();
+  DT.recalculate(F);
+
+  auto LoopInfo = LoopInfoBase<BasicBlock, Loop>();
+  LoopInfo.releaseMemory();
+  LoopInfo.analyze(DT);
+  return LoopInfo;
+}
+
+Loop *AAIsDeadFunction::getInfLoop(LoopInfoBase<BasicBlock, Loop> LoopInfo){
+  for (auto *L : LoopInfo) {
+    SmallVector<BasicBlock *, 4> ExitBlocks;
+    L->getExitBlocks(ExitBlocks);
+
+    // Not an infinite loop.
+    if (ExitBlocks.size() != 0)
+      continue;
+
+    // infinite loop.
+    return L;
+  }
+  return nullptr;
+}
+
+ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) {
+  Function &F = getAnchorScope();
+
+  Loop *InfLoop = getInfLoop(getLoopInfo(F));
+  bool HasNoReturn = false;
+
+  for (auto BB = DeadBlocks.begin(); BB != DeadBlocks.end(); ++BB) {
+    for (BasicBlock *PredBB : predecessors(*BB)) {
+     for (Instruction &I : *PredBB) {
+        ImmutableCallSite ICS(&I);
+        auto *NoReturnAA = A.getAAFor<AANoReturnFunction>(*this, I);
+
+        if (ICS && (!NoReturnAA || !NoReturnAA->isAssumedNoReturn()) &&
+            !ICS.hasFnAttr(Attribute::NoReturn))
+          continue;
+
+        /// This block is dead.
+        HasNoReturn = true;
+        break;
+      }
+
+      // if at least one predecessor doesn't have noreturn call and function
+      // does not have an infinite loop, the current block is not dead
+      if (!HasNoReturn && !InfLoop)
+        DeadBlocks.erase(BB);
+
+      // if we have an infinite loop, make sure the current BB is before the
+      // loop, therefore not dead.
+      if (!HasNoReturn && InfLoop)
+        for (auto *LoopPredBB : predecessors(*(InfLoop->block_begin())))
+          if (LoopPredBB == *BB)
+            DeadBlocks.erase(BB);
+    }
+  }
+
+  // No dead code, no need for AAIsDead.
+  if (DeadBlocks.size() == 0) {
+    indicatePessimisticFixpoint();
+    return ChangeStatus::CHANGED;
+  }
+
+  indicateOptimisticFixpoint();
+  return ChangeStatus::UNCHANGED;
+}
+
 /// ----------------------------------------------------------------------------
 ///                               Attributor
 /// ----------------------------------------------------------------------------
 
 ChangeStatus Attributor::run() {
   // Initialize all abstract attributes.
   for (AbstractAttribute *AA : AllAbstractAttributes)
     AA->initialize(*this);
 
   LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "
                     << AllAbstractAttributes.size()
                     << " abstract attributes.\n");
 
   // Now that all abstract attributes are collected and initialized we start the
   // abstract analysis.
 
   unsigned IterationCounter = 1;
 
   SmallVector<AbstractAttribute *, 64> ChangedAAs;
   SetVector<AbstractAttribute *> Worklist;
   Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end());
 
   do {
     LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
                       << ", Worklist size: " << Worklist.size() << "\n");
 
     // Add all abstract attributes that are potentially dependent on one that
     // changed to the work list.
     for (AbstractAttribute *ChangedAA : ChangedAAs) {
       auto &QuerriedAAs = QueryMap[ChangedAA];
       Worklist.insert(QuerriedAAs.begin(), QuerriedAAs.end());
for (AbstractAttribute *AA : Worklist)
         ChangedAAs.push_back(AA);
 
     // Reset the work list and repopulate with the changed abstract attributes.
     // Note that dependent ones are added above.
     Worklist.clear();
     Worklist.insert(ChangedAAs.begin(), ChangedAAs.end());
 
   } while (!Worklist.empty() && ++IterationCounter < MaxFixpointIterations);
 
   LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: "
                     << IterationCounter << "/" << MaxFixpointIterations
                     << " iterations\n");
 
   bool FinishedAtFixpoint = Worklist.empty();
 
   // Reset abstract arguments not settled in a sound fixpoint by now. This
   // happens when we stopped the fixpoint iteration early. Note that only the
   // ones marked as "changed" *and* the ones transitively depending on them
   // need to be reverted to a pessimistic state. Others might not be in a
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));