Compute safety information in a much finer granularity.

[trentxintong]

Summary

Instead of keeping a variable indicating whether there are early exits
in the loop. We keep all the early exits. This improves LICM's ability to
move instructions out of the loop based on is-guaranteed-to-execute.

I measured noise-level compilation time difference on SPECINT2006.

[trentxintong]

Update test case.

[hfinkel]

LGTM

include/llvm/Transforms/Utils/LoopUtils.h

49 ↗

(On Diff #96394)

The comment here should explain that these are calls that might throw, etc.

[trentxintong]

Address comment

[sanjoy]

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

482

This can be a range for over blocks().

485

This can be a range for also.

487

This is subjective, but in this kind of situation, I tend to avoid early exits since you just have one line after the early exit.

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

1049

Note: you could use all_of here, but this is fine too.

[efriedma]

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

1050

This could be slow: if the two instructions are in the same basic block, dominates() will iterate over the whole block. And you don't attempt to prune the EarlyExits list, which could make LICM O(N^3) overall for a large loop with a single basic block.

I guess we'll see if it matters in practice.

[• dberlin]

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

1050

Two fixes, one short term we should do, one longer term

1. Let that dominates call take an OBB as an optional argument

2. Just provide global + local dominance ordering as an analysis that encapsulates both the OBB + DT solution, and remove that use of dominates in favor of the analysis.

[hfinkel]

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

1050

Ack; I forgot about that scanning behavior. Using an OBB is right here. Right now, you need to do:

if (I1->getParent() == I2->getParent())
  return OBB->dominates(I1, I2);
else
  return DT->dominates(I1, I2);

I don't think we can yet hand an OBB directly to the DT (although that would certainly be a nice enhancement). I presume that we'd actually need a map of OBBs, as in Utils/PredicateInfo.h. Maybe stick it into LoopSafetyInfo?

[• dberlin]

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

1050

That is right, we can't do it yet, but seems simple enough.
We'd need a map.
Either add to loop safety info, or just define a struct that has the right properties and pass it along.

llvm/trunk/include/llvm/Transforms/Utils/LoopUtils.h

 class PredIteratorCache;
 class ScalarEvolution;
 class SCEV;
 class TargetLibraryInfo;
 
 /// \brief Captures loop safety information.
 /// It keep information for loop & its header may throw exception.
 struct LoopSafetyInfo {
-  bool MayThrow = false;       // The current loop contains an instruction which
-                               // may throw.
-  bool HeaderMayThrow = false; // Same as previous, but specific to loop header
+  // The early exits in the loop, excluding loop exits.
+  // These are calls that might throw, infinite loop, etc.
+  SmallVector<Instruction *, 4> EarlyExits;
   // Used to update funclet bundle operands.
   DenseMap<BasicBlock *, ColorVector> BlockColors;
 
   LoopSafetyInfo() = default;
 };
 
 /// The RecurrenceDescriptor is used to identify recurrences variables in a
 /// loop. Reduction is a special case of recurrence that has uses of the

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

bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
   return Changed;
 }
 
 /// Computes loop safety information, checks loop body & header
 /// for the possibility of may throw exception.
 ///
 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 |=
-        !isGuaranteedToTransferExecutionToSuccessor(&*I);
-
-  SafetyInfo->MayThrow = SafetyInfo->HeaderMayThrow;
-  // Iterate over loop instructions and compute safety info.
-  // Skip header as it has been computed and stored in HeaderMayThrow.
-  // The first block in loopinfo.Blocks is guaranteed to be the header.
-  assert(Header == *CurLoop->getBlocks().begin() && "First block must be header");
-  for (Loop::block_iterator BB = std::next(CurLoop->block_begin()),
+  // Iterate over loop instructions and compute early exit points.
+  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 |= !isGuaranteedToTransferExecutionToSuccessor(&*I);
+       BB != BBE; ++BB) {
+    for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E;
+         ++I) {
+      if (isGuaranteedToTransferExecutionToSuccessor(&*I))
+        continue;
+      SafetyInfo->EarlyExits.push_back(&*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);
bool llvm::promoteLoopAccessesToScalars(
   bool SawUnorderedAtomic = false; 
   bool SawNotAtomic = false;
   AAMDNodes AATags;
 
   const DataLayout &MDL = Preheader->getModule()->getDataLayout();
 
   // Do we know this object does not escape ?
   bool IsKnownNonEscapingObject = false;
-  if (SafetyInfo->MayThrow) {
+  if (!SafetyInfo->EarlyExits.empty()) {
     // If a loop can throw, we have to insert a store along each unwind edge.
     // That said, we can't actually make the unwind edge explicit. Therefore,
     // we have to prove that the store is dead along the unwind edge.
     //
     // If the underlying object is not an alloca, nor a pointer that does not
     // escape, then we can not effectively prove that the store is dead along
     // the unwind edge. i.e. the caller of this function could have ways to
     // access the pointed object.

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

DEBUG(dbgs() << "loop-idiom Scanning: F["
                << CurLoop->getHeader()->getName() << "\n");
 
   bool MadeChange = false;
 
   // The following transforms hoist stores/memsets into the loop pre-header.
   // Give up if the loop has instructions may throw.
   LoopSafetyInfo SafetyInfo;
   computeLoopSafetyInfo(&SafetyInfo, CurLoop);
-  if (SafetyInfo.MayThrow)
+  if (!SafetyInfo.EarlyExits.empty())
     return MadeChange;
 
   // Scan all the blocks in the loop that are not in subloops.
   for (auto *BB : CurLoop->getBlocks()) {
     // Ignore blocks in subloops.
     if (LI->getLoopFor(BB) != CurLoop)
       continue;
 

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

 }
 
 /// Returns true if the instruction in a loop is guaranteed to execute at least
 /// once.
 bool llvm::isGuaranteedToExecute(const Instruction &Inst,
                                  const DominatorTree *DT, const Loop *CurLoop,
                                  const LoopSafetyInfo *SafetyInfo) {
   // We have to check to make sure that the instruction dominates all
-  // of the exit blocks.  If it doesn't, then there is a path out of the loop
-  // which does not execute this instruction, so we can't hoist it.
-
-  // If the instruction is in the header block for the loop (which is very
-  // common), it is always guaranteed to dominate the exit blocks.  Since this
-  // is a common case, and can save some work, check it now.
-  if (Inst.getParent() == CurLoop->getHeader())
-    // If there's a throw in the header block, we can't guarantee we'll reach
-    // Inst.
-    return !SafetyInfo->HeaderMayThrow;
-
-  // Somewhere in this loop there is an instruction which may throw and make us
-  // exit the loop.
-  if (SafetyInfo->MayThrow)
+  // of the exit points.  If it doesn't, then there is a path out of the loop
+  // which does not execute this instruction and its not guaranteed to execute.
+  for (Instruction *ExitInst : SafetyInfo->EarlyExits)
+    if (!DT->dominates(&Inst, ExitInst))
       return false;
 
   // Get the exit blocks for the current loop.
   SmallVector<BasicBlock *, 8> ExitBlocks;
   CurLoop->getExitBlocks(ExitBlocks);
 
   // Verify that the block dominates each of the exit blocks of the loop.
   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())
+  // However, we also special case instruction from the header as the header
+  // is always guaranteed to execute.
+  if (ExitBlocks.empty() && Inst.getParent() != CurLoop->getHeader())
     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/loop-early-exits.ll

+; RUN: opt -S -licm < %s | FileCheck %s
+
+declare void @use(i64 %a)
+declare void @use_nothrow(i64 %a) nounwind
+declare void @use_nothing()
+
+; We can move this udiv out of the loop as it comes before 
+; the call instruction that may throw.
+define void @throw_header1(i64 %x, i64 %y, i1* %cond) {
+; CHECK-LABEL: throw_header1
+; CHECK: %div = udiv i64 %x, %y
+; CHECK-LABEL: loop
+; CHECK: call void @use(i64 %div)
+entry:
+  br label %loop
+
+loop:                                         ; preds = %entry, %for.inc
+  %div = udiv i64 %x, %y
+  call void @use(i64 %div)
+  br label %loop
+}
+
+; We can not move this udiv out of the loop as it comes after 
+; the call instruction that may throw.
+define void @throw_header2(i64 %x, i64 %y, i1* %cond) {
+; CHECK-LABEL: throw_header2
+; CHECK-LABEL: loop
+; CHECK: call void @use_nothing()
+; CHECK: %div = udiv i64 %x, %y
+entry:
+  br label %loop
+
+loop:                                         ; preds = %entry, %for.inc
+  call void @use_nothing()
+  %div = udiv i64 %x, %y
+  call void @use_nothrow(i64 %div)
+  br label %loop
+}
+
+; We can move this udiv out of the loop as it comes before 
+; the call instruction that may throw.
+define void @throw_body1(i64 %x, i64 %y, i1* %cond) {
+; CHECK-LABEL: throw_body1
+; CHECK: %div = udiv i64 %x, %y
+; CHECK-LABEL: loop
+entry:
+  br label %loop
+
+loop:                                         ; preds = %entry, %for.inc
+  br label %body
+
+body:
+  %div = udiv i64 %x, %y
+  call void @use(i64 %div)
+  br i1 undef, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; We can not move this udiv out of the loop as it comes after 
+; the call instruction that may throw.
+define void @throw_body2(i64 %x, i64 %y, i1* %cond) {
+; CHECK-LABEL: throw_body2
+; CHECK-LABEL: loop
+; CHECK: call void @use_nothing()
+; CHECK: %div = udiv i64 %x, %y
+entry:
+  br label %loop
+
+loop:                                         ; preds = %entry, %for.inc
+  br label %body
+
+body:
+  call void @use_nothing()
+  %div = udiv i64 %x, %y
+  call void @use_nothrow(i64 %div)
+  br i1 undef, label %loop, label %exit
+
+exit:
+  ret void
+}

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

 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
-; CHECK: call void @use(i64 %div)
-entry:
-  br label %loop
-
-loop:                                         ; preds = %entry, %for.inc
-  %div = udiv i64 %x, %y
-  call void @use(i64 %div)
-  br label %loop
-}
 
 ; The header is known no throw, but the loop is not.  We can
 ; still lift out of the header.
 define void @nothrow_header(i64 %x, i64 %y, i1 %cond) {
 ; CHECK-LABEL: nothrow_header
 ; CHECK-LABEL: entry
 ; CHECK: %div = udiv i64 %x, %y
 ; CHECK-LABEL: loop