[ValueTracking] improve reverse assumption inference

[nikic]

Summary

Use isGuaranteedToTransferExecutionToSuccessor instead of
isSafeToSpeculativelyExecute when seeing whether we can propagate the
information in an assume backwards in isValidAssumeForContext. The
latter is more general - it also allows arbitrary loads/stores - and is
also the condition we want: if our assume is guaranteed to execute, it
condition not holding would be UB.

[hfinkel]

This looks good, however, you need to either:

1. Don't remove isAssumeLikeIntrinsic, but instead, update isGuaranteedToTransferExecutionToSuccessor to call it.
2. Update isGuaranteedToTransferExecutionToSuccessor to have the complete list from isAssumeLikeIntrinsic.

Right now, isGuaranteedToTransferExecutionToSuccessor only checks:

return CS.onlyReadsMemory() || CS.onlyAccessesArgMemory() ||
       match(I, m_Intrinsic<Intrinsic::assume>());

[• dberlin]

(At some point, now that we could use post-dominance, you may want to see if it helps. For starters, anything if control dependent on the entry block is guaranteed to execute)

[arielb1]

add annotations to isGuaranteedToTransferExecutionToSuccessor (they were present in isAssumeLikeIntrinsic, which was *another* orthogonal method that tried to obtain the same result)

[hfinkel]

Can you please add some test cases for this? From the description, it seems like making a variant of the first test in test/Transforms/InstCombine/assume.ll would work (with some load, etc. that isSafeToSpeculativelyExecute won't handle but`isGuaranteedToTransferExecutionToSuccessor`. Also, adding tests for all of the intrinsics in isAssumeLikeIntrinsic would be really helpful (because at some point we'll need to fix the semantics in isGuaranteedToTransferExecutionToSuccessor and we'd like not to regress).

[arielb1]

Added test

[hfinkel]

In D37215#859925, @arielb1 wrote:

Added test

Thanks, LGTM.

[nikic]

Looks like this never landed...

[nikic]

Rebase.

[lebedev.ri]

test/Transforms/InstCombine/inevitable.ll

1 ↗

(On Diff #113697)

Precommit using utils/update_test_checks tool?

[nikic]

In the meantime additional users of isAssumeLikeIntrinsic() have been added, so I've switched this to call isAssumeLikeIntrinsic() from isGuaranteedToTransferExecutionToSuccessor() instead. Does this still look good?

[nikic]

Rebase over baseline tests.

[nikic]

test/Transforms/InstCombine/inevitable.ll

1 ↗

(On Diff #113697)

Done!

[jdoerfert]

@uenoku This looks like sth. the Attributor should do as well (at some point), I mean use llvm.assume information

[uenoku]

In D37215#1605735, @jdoerfert wrote:

@uenoku This looks like sth. the Attributor should do as well (at some point), I mean use llvm.assume information

It seems interesting.

llvm/lib/Analysis/ValueTracking.cpp

567

MustBeExecutedContextExplorer (in D65186) can simplify this check.

4273

D65455 gives annotation for AssumeLikeInst so you will be able to remove this check.

[nikic]

Remove isAssumeLikeIntrinsic handling, this is now handled by willreturn attributes on intrinsics.

[lebedev.ri]

I suspect that if this is rewritten with MustBeExecutedContextExplorer, @jdoerfert would review.

[jdoerfert]

In D37215#1624744, @lebedev.ri wrote:

I suspect that if this is rewritten with MustBeExecutedContextExplorer, @jdoerfert would review.

That depends on the use case. I think we should use the explorer either way but initially in "block-only" mode, which is what is happening here.
One can then decide if more elaborate modes make sense.

For now, I'd be fine with not using the explorer to not block this. In fact, this looks good to me.

llvm/lib/Analysis/ValueTracking.cpp

if (!DT) {
     // Search forward from the assume until we reach the context (or the end
     // of the block); the common case is that the assume will come first.
     for (auto I = std::next(BasicBlock::const_iterator(Inv)),
          IE = Inv->getParent()->end(); I != IE; ++I)
       if (&*I == CxtI)
         return true;
   }
 
+  // Don't let an assume affect itself - this would cause the problems
+  // `isEphemeralValueOf` is trying to prevent, and it would also make
+  // the loop below go out of bounds.
+  if (Inv == CxtI)
+    return false;
+
   // The context comes first, but they're both in the same block. Make sure
   // there is nothing in between that might interrupt the control flow.
   for (BasicBlock::const_iterator I =
          std::next(BasicBlock::const_iterator(CxtI)), IE(Inv);
        I != IE; ++I)
-    if (!isSafeToSpeculativelyExecute(&*I) && !isAssumeLikeIntrinsic(&*I))
+    if (!isGuaranteedToTransferExecutionToSuccessor(&*I))
       return false;
 
   return !isEphemeralValueOf(Inv, CxtI);
 }
 
 static void computeKnownBitsFromAssume(const Value *V, KnownBits &Known,
                                        unsigned Depth, const Query &Q) {
   // Use of assumptions is context-sensitive. If we don't have a context, we
if (auto CS = ImmutableCallSite(I)) {
     //    Furthermore IO itself is also modeled as writes to memory invisible to
     //    the program.
     //
     // We rely on those assumptions here, and use the memory effects of the call
     // target as a proxy for checking that it always returns.
 
     // FIXME: This isn't aggressive enough; a call which only writes to a global
     // is guaranteed to return.
     return CS.onlyReadsMemory() || CS.onlyAccessesArgMemory();
   }
 
   // Other instructions return normally.
   return true;
 }
 
 bool llvm::isGuaranteedToTransferExecutionToSuccessor(const BasicBlock *BB) {
   // TODO: This is slightly conservative for invoke instruction since exiting

llvm/test/Transforms/InstCombine/assume_inevitable.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 ; Check that assume is propagated backwards through all
 ; operations that are `isGuaranteedToTransferExecutionToSuccessor`
 ; (it should reach the load and mark it as `align 32`).
 define i32 @assume_inevitable(i32* %a, i32* %b, i8* %c) {
 ; CHECK-LABEL: @assume_inevitable(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[M:%.*]] = alloca i64, align 8
-; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[A:%.*]], align 4
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[A:%.*]], align 32
 ; CHECK-NEXT:    [[LOADRES:%.*]] = load i32, i32* [[B:%.*]], align 4
 ; CHECK-NEXT:    [[LOADRES2:%.*]] = call i32 @llvm.annotation.i32(i32 [[LOADRES]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str1, i64 0, i64 0), i32 2)
-; CHECK-NEXT:    store i32 [[LOADRES2]], i32* [[A]], align 4
+; CHECK-NEXT:    store i32 [[LOADRES2]], i32* [[A]], align 32
 ; CHECK-NEXT:    [[DUMMY_EQ:%.*]] = icmp ugt i32 [[LOADRES]], 42
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[DUMMY_EQ]])
 ; CHECK-NEXT:    [[M_I8:%.*]] = bitcast i64* [[M]] to i8*
 ; CHECK-NEXT:    [[M_A:%.*]] = call i8* @llvm.ptr.annotation.p0i8(i8* nonnull [[M_I8]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str1, i64 0, i64 0), i32 2)
 ; CHECK-NEXT:    [[M_X:%.*]] = bitcast i8* [[M_A]] to i64*
 ; CHECK-NEXT:    [[OBJSZ:%.*]] = call i64 @llvm.objectsize.i64.p0i8(i8* [[C:%.*]], i1 false, i1 false, i1 false)
 ; CHECK-NEXT:    store i64 [[OBJSZ]], i64* [[M_X]], align 4
 ; CHECK-NEXT:    [[PTRINT:%.*]] = ptrtoint i32* [[A]] to i64