[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

459

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

480

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

483

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

91

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

99

Naming suggestion:
wouldInstructionBeTriviallyDeadAlongUnusedPath

llvm/lib/Transforms/Utils/Local.cpp

447

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

447

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

459

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

 /// 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);
 
+/// 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 
+/// wouldInstructionBeTriviallyDead 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 wouldInstructionBeTriviallyDeadOnUnusedPaths(
+    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 =
         std::function<void(Value *)>());

llvm/lib/Transforms/Utils/Local.cpp

 ///
 bool llvm::isInstructionTriviallyDead(Instruction *I,
                                       const TargetLibraryInfo *TLI) {
   if (!I->use_empty())
     return false;
   return wouldInstructionBeTriviallyDead(I, TLI);
 }
 
+bool llvm::wouldInstructionBeTriviallyDeadOnUnusedPaths(
+    Instruction *I, const TargetLibraryInfo *TLI) {
+  // Instructions that are "markers" and have implied meaning on code around
+  // them (without explicit uses), are not dead on unused paths.
+  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
+    if (II->getIntrinsicID() == Intrinsic::stacksave ||
+        II->getIntrinsicID() == Intrinsic::launder_invariant_group ||
+        II->isLifetimeStartOrEnd())
+      return false;
+  return wouldInstructionBeTriviallyDead(I, TLI);
+}
+
 bool llvm::wouldInstructionBeTriviallyDead(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())
bool llvm::wouldInstructionBeTriviallyDead(Instruction *I,
   if (DbgLabelInst *DLI = dyn_cast<DbgLabelInst>(I)) {
     if (DLI->getLabel())
       return false;
     return true;
   }
 
   if (!I->willReturn())
     return false;
 
   if (!I->mayHaveSideEffects())
     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()) {
       auto *Arg = II->getArgOperand(1);
       // Lifetime intrinsics are dead when their right-hand is undef.
       if (isa<UndefValue>(Arg))
         return true;
       // If the right-hand is an alloc, global, or argument and the only uses
       // are lifetime intrinsics then the intrinsics are dead.
       if (isa<AllocaInst>(Arg) || isa<GlobalValue>(Arg) || isa<Argument>(Arg))
         return llvm::all_of(Arg->uses(), [](Use &Use) {
           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;