Less conservative LoopSafetyInfo for headers

[Prazek]

Summary

LoopSafetyInfo, which is used in LICM was very conservative - whenever
there was an instruction that could have throw it assumed that
none of the instructions in the header is guaranteed to execute.
With this patch we are able to hoist instructions based on the stronger
execution guarantee, and preserve metadata.

[kuhar]

Looks good, but you may want to wait for a green flag from someone more familiar with loops.

[efriedma]

include/llvm/Analysis/MustExecute.h

45 ↗

(On Diff #140594)

AssertingVH<Instruction>, to catch any invalidation bugs.

[Prazek]

move to monorepo

[Prazek]

• Removed cache because of safety concerns

[Prazek]

include/llvm/Analysis/MustExecute.h

45 ↗

(On Diff #140594)

That is excellent comment, I haven't thought about possibility of moving and deleting the instructions from header.

[amharc]

llvm/include/llvm/Analysis/MustExecute.h

44

This still tracks neither deletions nor RAUWs.

50

nit: Guarantee -> Guaranteed

llvm/lib/Analysis/MustExecute.cpp

278

Wouldn't checking isGuaranteedToTransferExecutionToSuccessor(&HeaderInstr) be somewhat less error-prone wrt. deletions, RAUWs etc., especially since the header is already being scanned from the beginning?

[Prazek]

• Fixed cache

llvm/include/llvm/Analysis/MustExecute.h

44

I wanted to change it o AssertingVH, but as it turned out it is sometimes legal to remove the call that could throw, which would invalidate the cache. Went with your idea.

llvm/lib/Analysis/MustExecute.cpp

278

seems good, lowered the step count

[Prazek]

Philip, can you take a look at this since I saw you have made some improvements to this code recently?

[reames]

Specifically NOT okay to land as is. The quadratic complexity concern is a real one and the window chosen here is very likely too large.

And if you're concern is purely LICM, this patch is no longer needed at all. I introduced a surgical fix for LICM which solves this without the need for O(n^2) work. Unfortunately, that approach only works for LICM (not, store promotion or other users of MustExecute). Unfortunately, as you've found there don't appear to be any good cheap ways to ask ordering questions around instructions within a basic block. If there were, we could just keep track of the first throwing instruction.

You could consider trying to wire in the caching needed for OrderedBasicBlock, but again, that's only needed if you're concern is different consumer than LICM

llvm/lib/Analysis/MustExecute.cpp

263

Purely code style: this duplicates similar code in ValueTracking. Even if we were okay going this direction, we should merge not duplicate.

[• dberlin]

We created an abstraction for the ordered basic block caching that works and is used in a few passes.
Transforms/Utils/OrderedInstructions.h

I suspect it's in a bad place for people to find it, and should be next to OrderedBasicBlock (or just make OrderedBasicBlock a hidden implementation detail, since all uses i can find really are doing it for multiple BB's anyway)

[reames]

In D45150#1093889, @dberlin wrote:

We created an abstraction for the ordered basic block caching that works and is used in a few passes.
Transforms/Utils/OrderedInstructions.h

I suspect it's in a bad place for people to find it, and should be next to OrderedBasicBlock (or just make OrderedBasicBlock a hidden implementation detail, since all uses i can find really are doing it for multiple BB's anyway)

Hm, I hadn't been aware of that myself. Will have to take a look.

[Prazek]

In D45150#1093811, @reames wrote:

Specifically NOT okay to land as is. The quadratic complexity concern is a real one and the window chosen here is very likely too large.

And if you're concern is purely LICM, this patch is no longer needed at all. I introduced a surgical fix for LICM which solves this without the need for O(n^2) work. Unfortunately, that approach only works for LICM (not, store promotion or other users of MustExecute). Unfortunately, as you've found there don't appear to be any good cheap ways to ask ordering questions around instructions within a basic block. If there were, we could just keep track of the first throwing instruction.

You could consider trying to wire in the caching needed for OrderedBasicBlock, but again, that's only needed if you're concern is different consumer than LICM

This approach was to satisfy this patch:
https://reviews.llvm.org/D45151

I will check in the meantime if your fix is enough to fix it, but I am concerned that it might be not enough.

[Prazek]

OK, so it seems that at least the tests in the second patch passes without this patch, so I am fine with committing it without this one for one (also Philip if you could take a look at that patch I would be grateful)
I am worried about cases, where the first instruction does not throw, but it we can't hoist it (e.g. it depends on the loop phi) and after that, there is an instruction that can be hoisted.

Right now we bail out if we reach more than 66 instructions. Is there a lower number that is greater than 1 that you think would be small enough to slow down the compilation imperceptibly, like 10?

[xbolva00]

llvm/lib/Analysis/MustExecute.cpp

278

Maybe introduce constant like "unsigned XZThreshoild = 66" with comment why 66 instead of a magic number?

llvm/include/llvm/Analysis/MustExecute.h

 /// common example is an instruction within a loop being provably executed if we
 /// branch to the header of it's containing loop.  
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_MUSTEXECUTE_H
 #define LLVM_ANALYSIS_MUSTEXECUTE_H
 
+#include <llvm/IR/ValueHandle.h>
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instruction.h"
 
 namespace llvm {
 
 class Instruction;
 class DominatorTree;
 class Loop;
 
 /// \brief Captures loop safety information.
 /// It keep information for loop & its header may throw exception or otherwise
 /// exit abnormaly on any iteration of the loop which might actually execute
 /// at runtime.  The primary way to consume this infromation is via
 /// isGuaranteedToExecute below, but some callers bailout or fallback to
 /// alternate reasoning if a loop contains any implicit control flow.
 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
+  bool HeaderMayThrow = false;
+
   // Used to update funclet bundle operands.
   DenseMap<BasicBlock *, ColorVector> BlockColors;
 
   LoopSafetyInfo() = default;
+
+  bool isHeaderInstructionGuaranteedToExecute(const Instruction *Instr,
+                                              const Loop *CurLoop) const;
+
 };
 
 /// \brief Computes safety information for a loop checks loop body & header for
 /// the possibility of may throw exception, it takes LoopSafetyInfo and loop as
 /// argument. Updates safety information in LoopSafetyInfo argument.
 /// Note: This is defined to clear and reinitialize an already initialized
 /// LoopSafetyInfo.  Some callers rely on this fact.
 void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *);

llvm/lib/Analysis/MustExecute.cpp

 
 /// 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;
+  SafetyInfo->MayThrow = false;
+  SafetyInfo->BlockColors.clear();
+
   // Iterate over header and compute safety info.
-  SafetyInfo->HeaderMayThrow =
+  SafetyInfo->HeaderMayThrow |=
       !isGuaranteedToTransferExecutionToSuccessor(Header);
 
   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()),
bool llvm::isGuaranteedToExecute(const Instruction &Inst,
                                  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;
+  if (Inst.getParent() == CurLoop->getHeader()) {
+    return SafetyInfo->isHeaderInstructionGuaranteedToExecute(&Inst, CurLoop);
+  }
 
   // Somewhere in this loop there is an instruction which may throw and make us
   // exit the loop.
   if (SafetyInfo->MayThrow)
     return false;
 
   // Note: There are two styles of reasoning intermixed below for
   // implementation efficiency reasons.  They are:
bool MustExecutePrinter::runOnFunction(Function &F) {
   auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 
   MustExecuteAnnotatedWriter Writer(F, DT, LI);
   F.print(dbgs(), &Writer);
   
   return false;
 }
+
+bool LoopSafetyInfo::isHeaderInstructionGuaranteedToExecute(
+    const Instruction *Instr, const Loop *CurLoop) const {
+
+  assert(Instr->getParent() == CurLoop->getHeader());
+  if (!HeaderMayThrow)
+    return true;
+
+  unsigned Steps = 0;
+  for (const auto &HeaderInstr : *CurLoop->getHeader()) {
+    if (&HeaderInstr == Instr)
+      return true;
+    if (!isGuaranteedToTransferExecutionToSuccessor(&HeaderInstr))
+      return false;
+
+    // Limit search to avoid quadratic complexity.
+    if (++Steps > 66)
+      return false;
+  }
+
+  llvm_unreachable("Should have found something or reach steps limit");
+}

llvm/test/Transforms/LICM/hoist-invariant-load.ll

 ; REQUIRES: asserts
-; RUN: opt < %s -licm -disable-basicaa -stats -S 2>&1 | grep "1 licm"
+; RUN: opt < %s -licm -disable-basicaa -stats -S 2>&1 | grep "2 licm"
+; RUN: opt < %s -licm -disable-basicaa -S | FileCheck %s
 
 @"\01L_OBJC_METH_VAR_NAME_" = internal global [4 x i8] c"foo\00", section "__TEXT,__objc_methname,cstring_literals", align 1
 @"\01L_OBJC_SELECTOR_REFERENCES_" = internal global i8* getelementptr inbounds ([4 x i8], [4 x i8]* @"\01L_OBJC_METH_VAR_NAME_", i32 0, i32 0), section "__DATA, __objc_selrefs, literal_pointers, no_dead_strip"
 @"\01L_OBJC_IMAGE_INFO" = internal constant [2 x i32] [i32 0, i32 16], section "__DATA, __objc_imageinfo, regular, no_dead_strip"
 @llvm.used = appending global [3 x i8*] [i8* getelementptr inbounds ([4 x i8], [4 x i8]* @"\01L_OBJC_METH_VAR_NAME_", i32 0, i32 0), i8* bitcast (i8** @"\01L_OBJC_SELECTOR_REFERENCES_" to i8*), i8* bitcast ([2 x i32]* @"\01L_OBJC_IMAGE_INFO" to i8*)], section "llvm.metadata"
-
+; CHECK-LABEL: define void @test(
 define void @test(i8* %x) uwtable ssp {
 entry:
   %x.addr = alloca i8*, align 8
   %i = alloca i32, align 4
   store i8* %x, i8** %x.addr, align 8
   store i32 0, i32* %i, align 4
+; CHECK: load i8*, i8** @"\01L_OBJC_SELECTOR_REFERENCES_"{{$}}
   br label %for.cond
-
+; CHECK: for.cond:
 for.cond:                                         ; preds = %for.inc, %entry
   %0 = load i32, i32* %i, align 4
   %cmp = icmp ult i32 %0, 10000
   br i1 %cmp, label %for.body, label %for.end
-
 for.body:                                         ; preds = %for.cond
   %1 = load i8*, i8** %x.addr, align 8
   %2 = load i8*, i8** @"\01L_OBJC_SELECTOR_REFERENCES_", !invariant.load !0
   %call = call i8* bitcast (i8* (i8*, i8*, ...)* @objc_msgSend to i8* (i8*, i8*)*)(i8* %1, i8* %2)
   br label %for.inc
 
 for.inc:                                          ; preds = %for.body
   %3 = load i32, i32* %i, align 4
   %inc = add i32 %3, 1
   store i32 %inc, i32* %i, align 4
   br label %for.cond
 
 for.end:                                          ; preds = %for.cond
   ret void
 }
 
+; This test checks if we keep !invariant.load metadata on the instruction after
+; hoisting.
+; CHECK-LABEL: @keep_metadata(
+define void @keep_metadata(i8** dereferenceable(8) %arg) {
+entry:
+
+  br i1 undef, label %while.end, label %while.body.lr.ph
+; CHECK: while.body.lr.ph:
+while.body.lr.ph:                                 ; preds = %entry
+; CHECK: load i8*, i8** %{{...}}, align 8, !invariant.load
+  br label %while.body
+; CHECK:       while.body:
+while.body:                                       ; preds = %while.body, %while.body.lr.ph
+
+  %x = load i8*, i8** %arg, align 8, !invariant.load !0
+  call void @foo(i8* %x)
+
+  br i1 undef, label %while.end.loopexit, label %while.body
+
+while.end.loopexit:                               ; preds = %while.body
+  br label %while.end
+
+while.end:                                        ; preds = %while.end.loopexit, %entry
+  ret void
+}
+
 declare i8* @objc_msgSend(i8*, i8*, ...) nonlazybind
+declare void @foo(i8*)
 
 !0 = !{}

llvm/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) {
+
+define void @throw_header_after(i64 %x, i64 %y, i1* %cond) {
+; CHECK-LABEL: throw_header_after
+; 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
+}
+
+define void @throw_header_before(i64 %x, i64 %y, i1* %cond) {
 ; CHECK-LABEL: throw_header
 ; CHECK-LABEL: loop
+; CHECK: call void @use(i64 0)
 ; CHECK: %div = udiv i64 %x, %y
 ; CHECK: call void @use(i64 %div)
 entry:
   br label %loop
 
 loop:                                         ; preds = %entry, %for.inc
+  call void @use(i64 0) ; this may throw
   %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) {