[TrivialDeadness] Introduce API separating two different usages

[anna]

Summary

The earlier usage of wouldInstructionBeTriviallyDead is based on the
assumption that the use_count of that instruction being checked will be
zero. This patch separates the API into two different ones:

1. The strictly conservative one where the instruction is trivially dead iff the uses are dead.
2. The slightly relaxed form, where an instruction is dead along paths where it is not used.

The second form can be used in identifying instructions that are valid
to sink down to uses (patch to be updated in D109917).

[mkazantsev]

I think most of this logic really belongs to isGuaranteedToTransferExecutionToSuccessor. I also think that wouldInstructionBeTriviallyDeadOnPathsWithoutUse should simply be isGuaranteedToTransferExecutionToSuccessor && !mayHaveSideEffects (maybe with filtering out terminators, ehpads and stuff like this), unless you have a counter-test.

llvm/lib/Transforms/Utils/Local.cpp

447

This also looks like it can be made a part of isGuaranteedToTransferExecutionToSuccessor.

468

Please remove this check. You may think that assume always passes execution, because it is either a NOOP or entire program is undefined.

471

This should really be a part of isGuaranteedToTransferExecutionToSuccessor. I suggest to check it instead of I->willReturn().

[mkazantsev]

One more point is that the name wouldInstructionBeTriviallyDeadOnPathsWithoutUse is not entirely clear. Does true here mean that at least one path without uses exists, or it is something that we need to check separately?

[reames]

See inline comments.

llvm/include/llvm/Transforms/Utils/Local.h

90

I'd leave off the naming suffix here. I think the original name is sufficiently clear.

(i.e. "trivial dead" continues to mean "along all paths")

98

Naming suggestion:
wouldInstructionBeTriviallyDeadAlongUnusedPath

llvm/lib/Transforms/Utils/Local.cpp

435

I would suggest an alternate implementation strategy here.

Leave the "along all paths" version unchanged.

Add the new "along unused path" version, with explicitly early returns for a couple of cases, then default to calling the "along all paths" variant.

This should be lower risk and easier to review. Then later, if you think it makes sense to invert the implementation, we can do that in a single NFC with tests for both in tree.

[anna]

llvm/lib/Transforms/Utils/Local.cpp

435

I really like this suggestion. It shows the "added API".

447

yes, can be done in a separate patch without increasing the scope here.

[anna]

addressed review comments

[anna]

rebased

[anna]

updated to correct diff.

[reames]

LGTM

llvm/include/llvm/Transforms/Utils/Local.h

 /// instruction will return. Certain side-effecting instructions are also
 /// considered dead if there are no uses of the instruction.
 bool isInstructionTriviallyDead(Instruction *I,
                                 const TargetLibraryInfo *TLI = nullptr);
 
 /// Return true if the result produced by the instruction would have no side
 /// effects if it was not used. This is equivalent to checking whether
 /// isInstructionTriviallyDead would be true if the use count was 0.
-bool wouldInstructionBeTriviallyDead(Instruction *I,
-                                     const TargetLibraryInfo *TLI = nullptr);
+bool wouldInstructionBeTriviallyDeadIfUsesDead(
+    Instruction *I, const TargetLibraryInfo *TLI = nullptr);
+
+/// Return true if the result produced by the instruction has no side effects on
+/// any paths other than where it is used. This is less conservative than 
+/// wouldInstructionBeTriviallyDeadIfUsesDead which is based on the assumption
+/// that the use count will be 0. An example usage of this API is for
+/// identifying instructions that can be sunk down to use(s).
+bool wouldInstructionBeTriviallyDeadOnPathsWithoutUse(
+    Instruction *I, const TargetLibraryInfo *TLI = nullptr);
 
 /// If the specified value is a trivially dead instruction, delete it.
 /// If that makes any of its operands trivially dead, delete them too,
 /// recursively. Return true if any instructions were deleted.
 bool RecursivelyDeleteTriviallyDeadInstructions(
     Value *V, const TargetLibraryInfo *TLI = nullptr,
     MemorySSAUpdater *MSSAU = nullptr,
     std::function<void(Value *)> AboutToDeleteCallback =

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

bool areAllUsesAssumedDead(Attributor &A, Value &V) {
     // without going through N update cycles. This is not required for
     // correctness.
     return A.checkForAllUses(UsePred, *this, V, /* CheckBBLivenessOnly */ false,
                              DepClassTy::REQUIRED);
   }
 
   /// Determine if \p I is assumed to be side-effect free.
   bool isAssumedSideEffectFree(Attributor &A, Instruction *I) {
-    if (!I || wouldInstructionBeTriviallyDead(I))
+    if (!I || wouldInstructionBeTriviallyDeadIfUsesDead(I))
       return true;
 
     auto *CB = dyn_cast<CallBase>(I);
     if (!CB || isa<IntrinsicInst>(CB))
       return false;
 
     const IRPosition &CallIRP = IRPosition::callsite_function(*CB);
     const auto &NoUnwindAA =

llvm/lib/Transforms/Scalar/BDCE.cpp

for (Instruction &I : instructions(F)) {
     // that will not help us.
     if (I.mayHaveSideEffects() && I.use_empty())
       continue;
 
     // Remove instructions that are dead, either because they were not reached
     // during analysis or have no demanded bits.
     if (DB.isInstructionDead(&I) ||
         (I.getType()->isIntOrIntVectorTy() && DB.getDemandedBits(&I).isZero() &&
-         wouldInstructionBeTriviallyDead(&I))) {
+         wouldInstructionBeTriviallyDeadIfUsesDead(&I))) {
       Worklist.push_back(&I);
       Changed = true;
       continue;
     }
 
     // Convert SExt into ZExt if none of the extension bits is required
     if (SExtInst *SE = dyn_cast<SExtInst>(&I)) {
       APInt Demanded = DB.getDemandedBits(SE);

llvm/lib/Transforms/Scalar/NewGVN.cpp

if (alwaysAvailable(Leader)) {
           AnythingReplaced = true;
         }
       }
     }
 
     // At this point, anything still in the ProbablyDead set is actually dead if
     // would be trivially dead.
     for (auto *I : ProbablyDead)
-      if (wouldInstructionBeTriviallyDead(I))
+      if (wouldInstructionBeTriviallyDeadIfUsesDead(I))
         markInstructionForDeletion(I);
 
     // Cleanup the congruence class.
     CongruenceClass::MemberSet MembersLeft;
     for (auto *Member : *CC)
       if (!isa<Instruction>(Member) ||
           !InstructionsToErase.count(cast<Instruction>(Member)))
         MembersLeft.insert(Member);

llvm/lib/Transforms/Utils/AssumeBundleBuilder.cpp

bool isKnowledgeWorthPreserving(RetainedKnowledge RK) {
     if (auto *Arg = dyn_cast<Argument>(RK.WasOn)) {
       if (Arg->hasAttribute(RK.AttrKind) &&
           (!Attribute::isIntAttrKind(RK.AttrKind) ||
            Arg->getAttribute(RK.AttrKind).getValueAsInt() >= RK.ArgValue))
         return false;
       return true;
     }
     if (auto *Inst = dyn_cast<Instruction>(RK.WasOn))
-      if (wouldInstructionBeTriviallyDead(Inst)) {
+      if (wouldInstructionBeTriviallyDeadIfUsesDead(Inst)) {
         if (RK.WasOn->use_empty())
           return false;
         Use *SingleUse = RK.WasOn->getSingleUndroppableUse();
         if (SingleUse && SingleUse->getUser() == InstBeingModified)
           return false;
       }
     return true;
   }

llvm/lib/Transforms/Utils/Local.cpp

 
 /// isInstructionTriviallyDead - Return true if the result produced by the
 /// instruction is not used, and the instruction has no side effects.
 ///
 bool llvm::isInstructionTriviallyDead(Instruction *I,
                                       const TargetLibraryInfo *TLI) {
   if (!I->use_empty())
     return false;
-  return wouldInstructionBeTriviallyDead(I, TLI);
+  return wouldInstructionBeTriviallyDeadIfUsesDead(I, TLI);
 }
 
-bool llvm::wouldInstructionBeTriviallyDead(Instruction *I,
-                                           const TargetLibraryInfo *TLI) {
+bool llvm::wouldInstructionBeTriviallyDeadOnPathsWithoutUse(
+    Instruction *I, const TargetLibraryInfo *TLI) {
   if (I->isTerminator())
     return false;
 
   // We don't want the landingpad-like instructions removed by anything this
   // general.
   if (I->isEHPad())
     return false;
 
bool llvm::wouldInstructionBeTriviallyDeadOnPathsWithoutUse(
   if (DbgLabelInst *DLI = dyn_cast<DbgLabelInst>(I)) {
     if (DLI->getLabel())
       return false;
     return true;
   }
 
   if (!I->willReturn())
     return false;
 
   if (!I->mayHaveSideEffects())
     return true;
 
+  if (isAllocLikeFn(I, TLI))
+    return true;
+
+  if (CallInst *CI = isFreeCall(I, TLI))
+    if (Constant *C = dyn_cast<Constant>(CI->getArgOperand(0)))
+      return C->isNullValue() || isa<UndefValue>(C);
+
+  if (auto *Call = dyn_cast<CallBase>(I))
+    if (isMathLibCallNoop(Call, TLI))
+      return true;
+
+  // To express possible interaction with floating point environment constrained
+  // intrinsics are described as if they access memory. So they look like having
+  // side effect but actually do not have it unless they raise floating point
+  // exception. If FP exceptions are ignored, the intrinsic may be deleted.
+  if (auto *CI = dyn_cast<ConstrainedFPIntrinsic>(I)) {
+    Optional<fp::ExceptionBehavior> EB = CI->getExceptionBehavior();
+    if (!EB || *EB == fp::ExceptionBehavior::ebIgnore)
+      return true;
+  }
+
+  // Intrinsics that do not return a value and are "no-op"
+  // as well, imply they are trivially dead on all paths.
+  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
+    // Assumptions are dead if their condition is trivially true.  Guards on
+    // true are operationally no-ops.  In the future we can consider more
+    // sophisticated tradeoffs for guards considering potential for check
+    // widening, but for now we keep things simple.
+    if ((II->getIntrinsicID() == Intrinsic::assume &&
+         isAssumeWithEmptyBundle(cast<AssumeInst>(*II))) ||
+        II->getIntrinsicID() == Intrinsic::experimental_guard) {
+      if (ConstantInt *Cond = dyn_cast<ConstantInt>(II->getArgOperand(0)))
+        return !Cond->isZero();
+
+      return false;
+    }
+  }
+
+  return false;
+}
+
+bool llvm::wouldInstructionBeTriviallyDeadIfUsesDead(
+    Instruction *I, const TargetLibraryInfo *TLI) {
+
+  // I would automatically be dead on all paths since there are no
+  // uses.
+  if (wouldInstructionBeTriviallyDeadOnPathsWithoutUse(I, TLI))
+    return true;
+
   // Special case intrinsics that "may have side effects" but can be deleted
   // when dead.
   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
     // Safe to delete llvm.stacksave and launder.invariant.group if dead.
     if (II->getIntrinsicID() == Intrinsic::stacksave ||
         II->getIntrinsicID() == Intrinsic::launder_invariant_group)
       return true;
 
if (II->isLifetimeStartOrEnd()) {
           if (IntrinsicInst *IntrinsicUse =
                   dyn_cast<IntrinsicInst>(Use.getUser()))
             return IntrinsicUse->isLifetimeStartOrEnd();
           return false;
         });
       return false;
     }
 
-    // Assumptions are dead if their condition is trivially true.  Guards on
-    // true are operationally no-ops.  In the future we can consider more
-    // sophisticated tradeoffs for guards considering potential for check
-    // widening, but for now we keep things simple.
-    if ((II->getIntrinsicID() == Intrinsic::assume &&
-         isAssumeWithEmptyBundle(cast<AssumeInst>(*II))) ||
-        II->getIntrinsicID() == Intrinsic::experimental_guard) {
-      if (ConstantInt *Cond = dyn_cast<ConstantInt>(II->getArgOperand(0)))
-        return !Cond->isZero();
-
-      return false;
-    }
-
     if (auto *FPI = dyn_cast<ConstrainedFPIntrinsic>(I)) {
       Optional<fp::ExceptionBehavior> ExBehavior = FPI->getExceptionBehavior();
       return ExBehavior.getValue() != fp::ebStrict;
     }
   }
 
-  if (isAllocLikeFn(I, TLI))
-    return true;
-
-  if (CallInst *CI = isFreeCall(I, TLI))
-    if (Constant *C = dyn_cast<Constant>(CI->getArgOperand(0)))
-      return C->isNullValue() || isa<UndefValue>(C);
-
-  if (auto *Call = dyn_cast<CallBase>(I))
-    if (isMathLibCallNoop(Call, TLI))
-      return true;
-
-  // To express possible interaction with floating point environment constrained
-  // intrinsics are described as if they access memory. So they look like having
-  // side effect but actually do not have it unless they raise floating point
-  // exception. If FP exceptions are ignored, the intrinsic may be deleted.
-  if (auto *CI = dyn_cast<ConstrainedFPIntrinsic>(I)) {
-    Optional<fp::ExceptionBehavior> EB = CI->getExceptionBehavior();
-    if (!EB || *EB == fp::ExceptionBehavior::ebIgnore)
-      return true;
-  }
-
   return false;
 }
 
 /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
 /// trivially dead instruction, delete it.  If that makes any of its operands
 /// trivially dead, delete them too, recursively.  Return true if any
 /// instructions were deleted.
 bool llvm::RecursivelyDeleteTriviallyDeadInstructions(