[LICM] Make isGuaranteedToExecute more accurate.

[eli.friedman]

Summary

Make isGuaranteedToExecute use the
isGuaranteedToTransferExecutionToSuccessor helper, and make that helper
a bit more accurate.

There's a potential performance impact here from assuming that arbitrary
calls might not return. This probably has little impact on loads and
stores to a pointer because most things alias analysis can reason about
are dereferenceable anyway. The other impacts, like less aggressive
hoisting of sdiv by a variable and less aggressive hoisting around
volatile memory operations, are unlikely to matter for real code.

This also impacts SCEV, which uses the same helper. It's a minor
improvement there because we can tell that, for example, memcpy always
returns normally. Strictly speaking, it's also introducing
a bug, but it's not any worse than everywhere else we assume readonly
functions terminate.

Fixes http://llvm.org/PR27857.

[sanjoy]

I have some minor nits inline. However, I think before adding Yet Another Special Case(TM) for the "readonly implies termination" rule we should at least try to scope out how much work it will be to do this right and introduce a "halting" or "always_returns" attribute, and infer them for trivially halting functions.

lib/Analysis/ValueTracking.cpp

3448 ↗

(On Diff #60131)

I don't think we model trapping memory operations in the IR at all (volatile or not).

3481 ↗

(On Diff #60131)

I'm not sure onlyAccessesArgMemory is correct. What about:

void f(volatile int* ptr) {
  while (true) *ptr = 1;
}

lib/IR/Instruction.cpp

15 ↗

(On Diff #60131)

Why do you need this?

lib/Transforms/Scalar/LICM.cpp

401 ↗

(On Diff #60131)

As a later change, can I ask you to please change these loops to use all_of or any_of?

776 ↗

(On Diff #60131)

Nit: http:// or just PR....

[eli.friedman]

I don't think anything has changed for "halting" since the last time it was discussed, about a year ago. I mean, we probably get a lot of the benefit by just marking all the LLVM intrinsics and libcalls halting (which is straightfoward, but tedious to go through and find the exceptions). We can add some additional markings in clang for stuff marked pure. Beyond that, for a function definition, the rules are that it doesn't unwind, doesn't call any non-halting function, and doesn't have any infinite loops. Finding calls to non-halting functions is easy. Not sure how we solve whether whether a function has an infinite loop; I think that was still up in the air the last time it was discussed. I think there's still some sort of pass manager problem that prevents accessing SCEV from functionattrs? Also, some people would prefer to assume side-effect-free loops terminate in C/C++, and it isn't clear exactly what accommodations we have to make for that.

I'm not actually 100% sure about the "doesn't unwind" bit; it might make sense to compute a "doesn't call longjmp" bit separately.

lib/Analysis/ValueTracking.cpp

3481 ↗

(On Diff #60131)

I don't think volatile stores are allowed in "argmemonly" methods. It would be like allowing volatile loads in a "readonly" method. If we say argmemonly functions are allowed to use volatile stores, from an optimization perspective the attribute is exactly equivalent to inaccessiblemem_or_argmemonly.

lib/IR/Instruction.cpp

15 ↗

(On Diff #60131)

Oops, leftover from an older version.

[sanjoy]

I had intended to add this myself in D19210 (so I don't have fundamental issues with the change) but decided against it when @broune pointed out that while(1); is well defined C11. But given that D19210 was also LGTM'ed (I was misremembering this earlier), I think this can go in.

I think there's still some sort of pass manager problem that prevents accessing SCEV from functionattrs?

It is even worse, I think, since not all infinite control flow will show up as llvm::Loop instances, so even if you could use SCEV, that won't be enough -- we'd have to conservative in the face of any cyclic control flow we couldn't fully understand.

lib/Analysis/ValueTracking.cpp

3481 ↗

(On Diff #60131)

SGTM

llvm/trunk/lib/Analysis/ValueTracking.cpp

OverflowResult llvm::computeOverflowForSignedAdd(Value *LHS, Value *RHS,
                                                  const DataLayout &DL,
                                                  AssumptionCache *AC,
                                                  const Instruction *CxtI,
                                                  const DominatorTree *DT) {
   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.
-
-  // Calls can throw and thus not terminate, and invokes may not terminate and
-  // could throw to non-successor (see bug 24185 for details).
-  if (isa<CallInst>(I) || isa<InvokeInst>(I))
-    // However, llvm.dbg intrinsics are safe, since they're no-ops.
-    return isa<DbgInfoIntrinsic>(I);
-
-  return !I->isAtomic() &&       // atomics may never succeed on some platforms
-         !isa<ResumeInst>(I) &&  // has no successors
-         !isa<ReturnInst>(I);    // has no successors
+  // A memory operation returns normally if it isn't volatile. A volatile
+  // operation is allowed to trap.
+  //
+  // An atomic operation isn't guaranteed to return in a reasonable amount of
+  // time because it's possible for another thread to interfere with it for an
+  // arbitrary length of time, but programs aren't allowed to rely on that.
+  if (const LoadInst *LI = dyn_cast<LoadInst>(I))
+    return !LI->isVolatile();
+  if (const StoreInst *SI = dyn_cast<StoreInst>(I))
+    return !SI->isVolatile();
+  if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(I))
+    return !CXI->isVolatile();
+  if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I))
+    return !RMWI->isVolatile();
+  if (const MemIntrinsic *MII = dyn_cast<MemIntrinsic>(I))
+    return !MII->isVolatile();
+
+  // If there is no successor, then execution can't transfer to it.
+  if (const auto *CRI = dyn_cast<CleanupReturnInst>(I))
+    return !CRI->unwindsToCaller();
+  if (const auto *CatchSwitch = dyn_cast<CatchSwitchInst>(I))
+    return !CatchSwitch->unwindsToCaller();
+  if (isa<ResumeInst>(I))
+    return false;
+  if (isa<ReturnInst>(I))
+    return false;
+
+  // Calls can throw, or contain an infinite loop, or kill the process.
+  if (CallSite CS = CallSite(const_cast<Instruction*>(I))) {
+    // Calls which don't write to arbitrary memory are safe.
+    // FIXME: Ignoring infinite loops without any side-effects is too aggressive,
+    // but it's consistent with other passes. See http://llvm.org/PR965 .
+    // 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::isGuaranteedToExecuteForEveryIteration(const Instruction *I,
                                                   const Loop *L) {
   // The loop header is guaranteed to be executed for every iteration.
   //
   // FIXME: Relax this constraint to cover all basic blocks that are
   // guaranteed to be executed at every iteration.

llvm/trunk/lib/Transforms/Scalar/LICM.cpp

void llvm::computeLoopSafetyInfo(LoopSafetyInfo *SafetyInfo, Loop *CurLoop) {
   assert(CurLoop != nullptr && "CurLoop cant be null");
   BasicBlock *Header = CurLoop->getHeader();
   // Setting default safety values.
   SafetyInfo->MayThrow = false;
   SafetyInfo->HeaderMayThrow = false;
   // Iterate over header and compute safety info.
   for (BasicBlock::iterator I = Header->begin(), E = Header->end();
        (I != E) && !SafetyInfo->HeaderMayThrow; ++I)
-    SafetyInfo->HeaderMayThrow |= I->mayThrow();
+    SafetyInfo->HeaderMayThrow |= !isGuaranteedToTransferExecutionToSuccessor(&*I);
 
   SafetyInfo->MayThrow = SafetyInfo->HeaderMayThrow;
   // Iterate over loop instructions and compute safety info.
   for (Loop::block_iterator BB = CurLoop->block_begin(),
                             BBE = CurLoop->block_end();
        (BB != BBE) && !SafetyInfo->MayThrow; ++BB)
     for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end();
          (I != E) && !SafetyInfo->MayThrow; ++I)
-      SafetyInfo->MayThrow |= I->mayThrow();
+      SafetyInfo->MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(&*I);
 
   // Compute funclet colors if we might sink/hoist in a function with a funclet
   // personality routine.
   Function *Fn = CurLoop->getHeader()->getParent();
   if (Fn->hasPersonalityFn())
     if (Constant *PersonalityFn = Fn->getPersonalityFn())
       if (isFuncletEHPersonality(classifyEHPersonality(PersonalityFn)))
         SafetyInfo->BlockColors = colorEHFunclets(*Fn);

llvm/trunk/lib/Transforms/Utils/LoopUtils.cpp

for (BasicBlock *ExitBlock : ExitBlocks)
     if (!DT->dominates(Inst.getParent(), ExitBlock))
       return false;
 
   // As a degenerate case, if the loop is statically infinite then we haven't
   // proven anything since there are no exit blocks.
   if (ExitBlocks.empty())
     return false;
 
+  // FIXME: In general, we have to prove that the loop isn't an infinite loop.
+  // See http::llvm.org/PR24078 .  (The "ExitBlocks.empty()" check above is
+  // just a special case of this.)
   return true;
 }

llvm/trunk/test/Transforms/LICM/hoist-nounwind.ll

+; RUN: opt -S -basicaa -licm < %s | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @f() nounwind
+
+; Don't hoist load past nounwind call.
+define i32 @test1(i32* noalias nocapture readonly %a) nounwind uwtable {
+; CHECK-LABEL: @test1(
+entry:
+  br label %for.body
+
+; CHECK: tail call void @f()
+; CHECK-NEXT: load i32
+for.body:
+  %i.06 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %x.05 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  tail call void @f() nounwind
+  %i1 = load i32, i32* %a, align 4
+  %add = add nsw i32 %i1, %x.05
+  %inc = add nuw nsw i32 %i.06, 1
+  %exitcond = icmp eq i32 %inc, 1000
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+
+for.cond.cleanup:
+  ret i32 %add
+}
+
+; Don't hoist division past nounwind call.
+define i32 @test2(i32 %N, i32 %c) nounwind uwtable {
+; CHECK-LABEL: @test2(
+entry:
+  %cmp4 = icmp sgt i32 %N, 0
+  br i1 %cmp4, label %for.body, label %for.cond.cleanup
+
+; CHECK: tail call void @f()
+; CHECK-NEXT: sdiv i32
+for.body:
+  %i.05 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  tail call void @f() nounwind
+  %div = sdiv i32 5, %c
+  %add = add i32 %i.05, 1
+  %inc = add i32 %add, %div
+  %cmp = icmp slt i32 %inc, %N
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:
+  ret i32 0
+}
+
+; Don't hoist load past volatile load.
+define i32 @test3(i32* noalias nocapture readonly %a, i32* %v) nounwind uwtable {
+; CHECK-LABEL: @test3(
+entry:
+  br label %for.body
+
+; CHECK: load volatile i32
+; CHECK-NEXT: load i32
+for.body:
+  %i.06 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %x.05 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %xxx = load volatile i32, i32* %v, align 4
+  %i1 = load i32, i32* %a, align 4
+  %add = add nsw i32 %i1, %x.05
+  %inc = add nuw nsw i32 %i.06, 1
+  %exitcond = icmp eq i32 %inc, 1000
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+
+for.cond.cleanup:
+  ret i32 %add
+}

llvm/trunk/test/Transforms/LICM/hoisting.ll

 declare void @foo2(i32) nounwind
 
 
 ;; It is ok and desirable to hoist this potentially trapping instruction.
 define i32 @test2(i1 %c) {
 ; CHECK-LABEL: @test2(
 ; CHECK-NEXT: load i32, i32* @X
 ; CHECK-NEXT: %B = sdiv i32 4, %A
-  %A = load i32, i32* @X    ; <i32> [#uses=2]
-  br label %Loop
+  %A = load i32, i32* @X
+  br label %Loop
+
 Loop:
-        ;; Should have hoisted this div!
-  %B = sdiv i32 4, %A    ; <i32> [#uses=2]
-  call void @foo2( i32 %B )
-  br i1 %c, label %Loop, label %Out
-Out:    ; preds = %Loop
-  %C = sub i32 %A, %B    ; <i32> [#uses=1]
-  ret i32 %C
+  %B = sdiv i32 4, %A
+  br label %loop2
+
+loop2:
+  call void @foo2( i32 %B )
+  br i1 %c, label %Loop, label %Out
+
+Out:
+  %C = sub i32 %A, %B
+  ret i32 %C
 }
 
 
 ; This loop invariant instruction should be constant folded, not hoisted.
 define i32 @test3(i1 %c) {
 ; CHECK-LABEL: define i32 @test3(
 ; CHECK: call void @foo2(i32 6)
   %A = load i32, i32* @X    ; <i32> [#uses=2]

llvm/trunk/test/Transforms/LICM/preheader-safe.ll

 ; RUN: opt -S -licm < %s | FileCheck %s
 
 declare void @use_nothrow(i64 %a) nounwind
 declare void @use(i64 %a)
 
 define void @nothrow(i64 %x, i64 %y, i1* %cond) {
 ; CHECK-LABEL: nothrow
 ; CHECK-LABEL: entry
 ; CHECK: %div = udiv i64 %x, %y
 ; CHECK-LABEL: loop
 ; CHECK: call void @use_nothrow(i64 %div)
 entry:
   br label %loop
 
 loop:                                         ; preds = %entry, %for.inc
   %div = udiv i64 %x, %y
+  br label %loop2
+
+loop2:
   call void @use_nothrow(i64 %div)
   br label %loop
 }
 ; Negative test
 define void @throw_header(i64 %x, i64 %y, i1* %cond) {
 ; CHECK-LABEL: throw_header
 ; CHECK-LABEL: loop
 ; CHECK: %div = udiv i64 %x, %y

llvm/trunk/test/Transforms/LICM/promote-tls.ll

 
 for.body.lr.ph:                                   ; preds = %entry
   br label %for.header
 
 for.header:
   %i.02 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.body ]
   %old = load i32, i32* %addr, align 4
   ; deliberate impossible to analyze branch
-  %guard = load volatile i8*, i8** @p
+  %guard = load atomic i8*, i8** @p monotonic, align 8
   %exitcmp = icmp eq i8* %guard, null
   br i1 %exitcmp, label %for.body, label %early-exit
 
 early-exit:
 ; CHECK-LABEL: early-exit:
 ; CHECK: store i32 %new1.lcssa, i32* %addr, align 1
   ret i32* null
 

llvm/trunk/test/Transforms/LICM/scalar_promote.ll

 
 
 Loop:   ; preds = %Loop, %0
   %j = phi i32 [ 0, %Entry ], [ %Next, %Loop ]    ; <i32> [#uses=1]
   %x = load i32, i32* @X   ; <i32> [#uses=1]
   %x2 = add i32 %x, 1   ; <i32> [#uses=1]
   store i32 %x2, i32* @X
 
-        store volatile i32* @X, i32** %P2
+        store atomic i32* @X, i32** %P2 monotonic, align 8
 
   %Next = add i32 %j, 1   ; <i32> [#uses=2]
   %cond = icmp eq i32 %Next, 0    ; <i1> [#uses=1]
   br i1 %cond, label %Out, label %Loop
 
 Out:
   ret void
 ; CHECK: Out:

llvm/trunk/test/Transforms/LICM/volatile-alias.ll

 ; RUN: opt -basicaa -sroa -loop-rotate -licm -S < %s | FileCheck %s
 ; The objects *p and *q are aliased to each other, but even though *q is
 ; volatile, *p can be considered invariant in the loop. Check if it is moved
 ; out of the loop.
 ; CHECK: load i32, i32* %p
 ; CHECK: for.body:
 ; CHECK: load volatile i32, i32* %q
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 
 ; Function Attrs: nounwind uwtable
-define i32 @foo(i32* %p, i32* %q, i32 %n) #0 {
+define i32 @foo(i32* dereferenceable(4) nonnull %p, i32* %q, i32 %n) #0 {
 entry:
   %p.addr = alloca i32*, align 8
   %q.addr = alloca i32*, align 8
   %n.addr = alloca i32, align 4
   %i = alloca i32, align 4
   %s = alloca i32, align 4
   store i32* %p, i32** %p.addr, align 8
   store i32* %q, i32** %q.addr, align 8