Compute safety information in a much finer granularity.

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 am going to update compilation time as well soon.

Reviewers: hfinkel, sanjoy, efriedma, mkuper

Reviewed By: hfinkel

Subscribers: llvm-commits, mzolotukhin

Differential Revision: https://reviews.llvm.org/D32433

llvm-svn: 301196

3 files changed, 20 insertions, 38 deletions

diff --git a/llvm/lib/Transforms/Scalar/LICM.cpp b/llvm/lib/Transforms/Scalar/LICM.cpp
index 340c81fed0f..2b84150a000 100644
--- a/llvm/lib/Transforms/Scalar/LICM.cpp
+++ b/llvm/lib/Transforms/Scalar/LICM.cpp
@@ -478,27 +478,17 @@ bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
 ///
 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.
@@ -1094,7 +1084,7 @@ bool llvm::promoteLoopAccessesToScalars(
 
   // 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.
diff --git a/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp b/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
index 946d85d7360..a6c1669c14d 100644
--- a/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
@@ -272,7 +272,7 @@ bool LoopIdiomRecognize::runOnCountableLoop() {
   // 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.
diff --git a/llvm/lib/Transforms/Utils/LoopUtils.cpp b/llvm/lib/Transforms/Utils/LoopUtils.cpp
index 175d013a011..062432fe084 100644
--- a/llvm/lib/Transforms/Utils/LoopUtils.cpp
+++ b/llvm/lib/Transforms/Utils/LoopUtils.cpp
@@ -1044,21 +1044,11 @@ 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)
-    return false;
+  // 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;
@@ -1071,7 +1061,9 @@ bool llvm::isGuaranteedToExecute(const Instruction &Inst,
 
   // 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.