[CodeMetrics] Don't require speculatability for ephemeral values

[nikic]

Summary

As discussed in D112016, our current requirement of speculatability for ephemeral is overly strict: What we really care about is that the instruction will be DCEd once the assume is dropped. For that it is sufficient that the instruction is side-effect free and not a terminator.

In particular, this allows non-dereferenceable loads to be ephemeral values.

[aeubanks]

llvm/lib/Analysis/ValueTracking.cpp

497–499

it'd be nice to a have a test case for this, but that might be hard to come up with

llvm/test/Transforms/Inline/ephemeral.ll

28–30

the comment doesn't really make sense, it now is considered ephemeral
ditto in the other test

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

497–499

Most likely this change doesn't have an observable effect. I mainly changed it for the sake of consistency.

llvm/lib/Analysis/CodeMetrics.cpp

appendSpeculatableOperands(const Value *V,
                            SmallPtrSetImpl<const Value *> &Visited,
                            SmallVectorImpl<const Value *> &Worklist) {
   const User *U = dyn_cast<User>(V);
   if (!U)
     return;
 
   for (const Value *Operand : U->operands())
     if (Visited.insert(Operand).second)
-      if (isSafeToSpeculativelyExecute(Operand))
-        Worklist.push_back(Operand);
+      if (const auto *I = dyn_cast<Instruction>(Operand))
+        if (!I->mayHaveSideEffects() && !I->isTerminator())
+          Worklist.push_back(I);
 }
 
 static void completeEphemeralValues(SmallPtrSetImpl<const Value *> &Visited,
                                     SmallVectorImpl<const Value *> &Worklist,
                                     SmallPtrSetImpl<const Value *> &EphValues) {
   // Note: We don't speculate PHIs here, so we'll miss instruction chains kept
   // alive only by ephemeral values.
 

llvm/lib/Analysis/ValueTracking.cpp

while (!WorkSet.empty()) {
 
     // If all uses of this value are ephemeral, then so is this value.
     if (llvm::all_of(V->users(), [&](const User *U) {
                                    return EphValues.count(U);
                                  })) {
       if (V == E)
         return true;
 
-      if (V == I || isSafeToSpeculativelyExecute(V)) {
+      if (V == I || (isa<Instruction>(V) &&
+                     !cast<Instruction>(V)->mayHaveSideEffects() &&
+                     !cast<Instruction>(V)->isTerminator())) {
        EphValues.insert(V);
        if (const User *U = dyn_cast<User>(V))
          append_range(WorkSet, U->operands());
       }
     }
   }
 
   return false;

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

bool SimplifyCFGOpt::SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB,
   return true;
 }
 
 /// Return true if we can thread a branch across this block.
 static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) {
   int Size = 0;
 
   SmallPtrSet<const Value *, 32> EphValues;
-  auto IsEphemeral = [&](const Value *V) {
-    if (isa<AssumeInst>(V))
+  auto IsEphemeral = [&](const Instruction *I) {
+    if (isa<AssumeInst>(I))
       return true;
-    return isSafeToSpeculativelyExecute(V) &&
-           all_of(V->users(),
+    return !I->mayHaveSideEffects() && !I->isTerminator() &&
+           all_of(I->users(),
                   [&](const User *U) { return EphValues.count(U); });
   };
 
   // Walk the loop in reverse so that we can identify ephemeral values properly
   // (values only feeding assumes).
   for (Instruction &I : reverse(BB->instructionsWithoutDebug(false))) {
     // Can't fold blocks that contain noduplicate or convergent calls.
     if (CallInst *CI = dyn_cast<CallInst>(&I))

llvm/test/Transforms/Inline/ephemeral.ll

define i32 @inner(i8* %y) {
   %a6 = add i32 %a5, %a5
   %ca = icmp sgt i32 %a6, -7
   %r = call i1 @llvm.type.test(i8* %y, metadata !0)
   %ca2 = icmp eq i1 %ca, %r
   tail call void @llvm.assume(i1 %ca2)
 
   ret i32 %a1
 }
 
-; TODO: The load should be considered ephemeral here, even though it is not
-; speculatable.
+; Only the ret should be included in the instruction count, the load and icmp
+; are both ephemeral.
 ; CHECK: Analyzing call of inner2...
-; CHECK: NumInstructions: 2
+; CHECK: NumInstructions: 1
 define void @inner2(i8* %y) {
   %v = load i8, i8* %y
   %c = icmp eq i8 %v, 42
   call void @llvm.assume(i1 %c)
   ret void
 }
 
 define i32 @outer(i8* %y) optsize {

llvm/test/Transforms/SimplifyCFG/unprofitable-pr.ll

true2:                                            ; preds = %true1
   store volatile i64 2, i64* %ptr, align 8
   ret void
 
 false2:                                           ; preds = %true1
   store volatile i64 3, i64* %ptr, align 8
   ret void
 }
 
-; TODO: The load should be considered ephemeral here, even though it is not
-; speculatable.
+; The load, icmp and assume should not count towards the limit, they are
+; ephemeral.
 define void @test_non_speculatable(i1 %c, i64* align 1 %ptr, i8* %ptr2) local_unnamed_addr #0 {
 ; CHECK-LABEL: @test_non_speculatable(
-; CHECK-NEXT:    br i1 [[C:%.*]], label [[TRUE1:%.*]], label [[FALSE1:%.*]]
-; CHECK:       true1:
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[TRUE2_CRITEDGE:%.*]], label [[FALSE1:%.*]]
+; CHECK:       false1:
+; CHECK-NEXT:    store volatile i64 1, i64* [[PTR:%.*]], align 4
 ; CHECK-NEXT:    [[V:%.*]] = load i8, i8* [[PTR2:%.*]], align 1
 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V]], 42
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C2]])
-; CHECK-NEXT:    store volatile i64 0, i64* [[PTR:%.*]], align 8
+; CHECK-NEXT:    store volatile i64 0, i64* [[PTR]], align 8
 ; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
 ; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
 ; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
 ; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
 ; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
-; CHECK-NEXT:    br i1 [[C]], label [[TRUE2:%.*]], label [[FALSE2:%.*]]
-; CHECK:       false1:
-; CHECK-NEXT:    store volatile i64 1, i64* [[PTR]], align 4
-; CHECK-NEXT:    br label [[TRUE1]]
+; CHECK-NEXT:    store volatile i64 3, i64* [[PTR]], align 8
+; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 ; CHECK:       common.ret:
 ; CHECK-NEXT:    ret void
-; CHECK:       true2:
+; CHECK:       true2.critedge:
+; CHECK-NEXT:    [[V_C:%.*]] = load i8, i8* [[PTR2]], align 1
+; CHECK-NEXT:    [[C2_C:%.*]] = icmp eq i8 [[V_C]], 42
+; CHECK-NEXT:    call void @llvm.assume(i1 [[C2_C]])
+; CHECK-NEXT:    store volatile i64 0, i64* [[PTR]], align 8
+; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
+; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
+; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
+; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
+; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
 ; CHECK-NEXT:    store volatile i64 2, i64* [[PTR]], align 8
-; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
-; CHECK:       false2:
-; CHECK-NEXT:    store volatile i64 3, i64* [[PTR]], align 8
 ; CHECK-NEXT:    br label [[COMMON_RET]]
 ;
   br i1 %c, label %true1, label %false1
 
 true1:                                            ; preds = %false1, %0
   %v = load i8, i8* %ptr2
   %c2 = icmp eq i8 %v, 42
   call void @llvm.assume(i1 %c2)