Teach poison value tracking that certain calls always terminate

[sanjoy]

Summary

This makes our poison value analysis a little smarter.

[majnemer]

lib/Analysis/ValueTracking.cpp

3289

Couldn't this just be !I->mayHaveSideEffects() ?

[sanjoy]

lib/Analysis/ValueTracking.cpp

3289

Yeah, but I didn't want to write it that way -- IMO it is only "incidental" that mayHaveSideEffects and what I'm computing here are the same implementation. IOW, the predicate in the two cases (mayHaveSideEffects vs. "guaranteed to transfer control flow to successor") are quite different, even if they have the same implementation.

[broune]

lib/Analysis/ValueTracking.cpp

3288

This seems unfortunate given that, as I understand it, we then can't compile C11 correctly:

http://stackoverflow.com/questions/16436237/is-while1-undefined-behavior-in-c

Go ahead and submit this if you're sure that the consensus is that this is how LLVM ought to behave. I'd be more comfortable if the langref stated that infinite side-effect free loops are not allowed, but I couldn't find anything about that in there.

[sanjoy]

lib/Analysis/ValueTracking.cpp

3288

I'm going to look at http://stackoverflow.com/questions/16436237/is-while1-undefined-behavior-in-c , but assuming that's accurate (i.e. while (1); is well defined) I'll redact this patch. It's not really an option (IMO) to miscompile C11. :)

[hfinkel]

lib/Analysis/ValueTracking.cpp

3288

As I understand it, LLVM is not really self-consistent on this point. As you point out, we we will DCE readnone and readonly calls. We should be, however, because we have frontends for languages with well-defined infinite loops (Java?, and apparently C11), and those without well-defined infinite loops (C++), and we'd like to do the best job on all of them. I think we need a new function-level attribute that controls whether we get to assume that loops terminate, and then we can make a consistent decision everywhere.

[sanjoy]

The "icmp propagages poison" bit has been checked in in rL271150. The "branch on poison is UB" bit is incorrect, and has been abandoned.

lib/Analysis/ValueTracking.cpp

OverflowResult llvm::computeOverflowForSignedAdd(Value *LHS, Value *RHS,
   return ::computeOverflowForSignedAdd(LHS, RHS, nullptr, DL, AC, CxtI, DT);
 }
 
 bool llvm::isGuaranteedToTransferExecutionToSuccessor(const Instruction *I) {
   // FIXME: This conservative implementation can be relaxed. E.g. most
   // atomic operations are guaranteed to terminate on most platforms
   // and most functions terminate.
 
+  if (ImmutableCallSite CS = ImmutableCallSite(I))
+    // NB! This assumes that a function cannot have an infinite loop that does
+    // not contain side effects.  As far as I can tell, this isn't a new
+    // assumption (e.g. we will DCE readnone and readonly calls).
+    return CS.doesNotThrow() && CS.onlyReadsMemory();
+
+  if (auto *II = dyn_cast<IntrinsicInst>(I))
+    if (II->getIntrinsicID() == Intrinsic::dbg_value)
+      return true;
+
   return !I->isAtomic() &&       // atomics may never succeed on some platforms
-         !isa<CallInst>(I) &&    // could throw and might not terminate
-         !isa<InvokeInst>(I) &&  // might not terminate and could throw to
-                                 //   non-successor (see bug 24185 for details).
          !isa<ResumeInst>(I) &&  // has no successors
          !isa<ReturnInst>(I);    // has no successors
 }
 
 bool llvm::isGuaranteedToExecuteForEveryIteration(const Instruction *I,
                                                   const Loop *L) {
   // The loop header is guaranteed to be executed for every iteration.
   //

test/Analysis/ScalarEvolution/flags-from-poison.ll

 ; RUN: opt < %s -S -analyze -scalar-evolution | FileCheck %s
 
+declare void @unknown()
+
 ; Positive and negative tests for inferring flags like nsw from
 ; reasoning about how a poison value from overflow would trigger
 ; undefined behavior.
 
 define void @foo() {
   ret void
 }
 
; CHECK: --> {(sext i32 %offset to i64),+,1}<nsw>
   %f = load float, float* %ptr, align 4
   call void @foo()
   %exitcond = icmp eq i32 %nexti, %numIterations
   br i1 %exitcond, label %exit, label %loop
 exit:
   ret void
 }
 
+define void @test-add-nsw-callinst-0(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-nsw-callinst-0
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+  ; We do not know whether @unknown() will return or throw or
+  ; infinitely loop, so we cannot infer undefined behavior if %index32
+  ; is poison.
+  call void @unknown()
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nw>
+  %index32 = add nsw i32 %i, %offset
+
+; CHECK: %index64 =
+; CHECK: --> (sext i32 {%offset,+,1}<nw><%loop> to i64)
+  %index64 = sext i32 %index32 to i64
+
+  %ptr = getelementptr inbounds float, float* %input, i64 %index64
+  %nexti = add nsw i32 %i, 1
+  %f = load float, float* %ptr, align 4
+  call void @foo()
+  %exitcond = icmp eq i32 %nexti, %numIterations
+  br i1 %exitcond, label %exit, label %loop
+exit:
+  ret void
+}
+
+define void @test-add-nsw-callinst-1(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-nsw-callinst-1
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+  ; We know that the call to @unknown will not throw or have an
+  ; infinite loop, so we can conclude UB if %index32 is poison.
+  call void @unknown() nounwind readonly
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nsw>
+  %index32 = add nsw i32 %i, %offset
+
+; CHECK: %index64 =
+; CHECK: --> {(sext i32 %offset to i64),+,1}<nsw>
+  %index64 = sext i32 %index32 to i64
+
+  %ptr = getelementptr inbounds float, float* %input, i64 %index64
+  %nexti = add nsw i32 %i, 1
+  %f = load float, float* %ptr, align 4
+  call void @foo()
+  %exitcond = icmp eq i32 %nexti, %numIterations
+  br i1 %exitcond, label %exit, label %loop
+exit:
+  ret void
+}
+
 ; Example where an add should get the nuw flag.
 define void @test-add-nuw(float* %input, i32 %offset, i32 %numIterations) {
 ; CHECK-LABEL: @test-add-nuw
 entry:
   br label %loop
 loop:
   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]