Restrict the definition of loop preheader to avoid special blocks

[andrew.w.kaylor]

Summary

This patch modifies the LoopBase::getLoopPreheader() so that it will not identify blocks as preheaders if instructions cannot legally be hoisted into the block. This currently just eliminates special Windows EH blocks to avoid hoisting instructions into funclets.

This change was motivated by a bug a found in loop rotate and the discussion in the comments of that bug (https://bugs.llvm.org/show_bug.cgi?id=33393).

Because getLoopPreheader() is in the LoopBase<BlockT*> template class and we can't examine terminator instructions from there I couldn't simply check the predecessor block's terminator for side effects as suggested. Looking at the uses of getLoopPreheader() it seemed that it is generally used to find a place to hoist instructions, and so I decided to add a method that would check for the legality of doing so.

[majnemer]

lib/IR/BasicBlock.cpp

364–371 ↗

(On Diff #103492)

It should be impossible to get here if Term has no successors, no? Couldn't we assert(Term->getNumSuccessors > 0)?

Also, could we simplify this by just returning return !Term->IsExceptional() ?

[andrew.w.kaylor]

lib/IR/BasicBlock.cpp

364–371 ↗

(On Diff #103492)

I wanted to write this as a generic function that could be used from anywhere. It is difficult to imagine why anyone would ever call it for a block without successors, but it seems cheap and easy to give a sensible answer in that case. I don't have strong feelings about it either way. The assertion would serve as a useful flag to callers that they are doing something nonsensical.

You're right that I could use IsExceptional() here. I guess my implementation reflects my thought process while writing the function a little more directly than it ought to.

[andrew.w.kaylor]

Addressed initial review feedback

[majnemer]

LGTM

[davide]

LGTM

llvm/trunk/lib/CodeGen/MachineBasicBlock.cpp

232–234

nit, you can simplify return !isReturnBlock() && !hasEHPadSuccessors()

llvm/trunk/include/llvm/Analysis/LoopInfoImpl.h

for (const auto BB : blocks())
     for (const auto &Succ : children<BlockT*>(BB))
       if (!contains(Succ))
         // Not in current loop? It must be an exit block.
         ExitEdges.emplace_back(BB, Succ);
 }
 
 /// getLoopPreheader - If there is a preheader for this loop, return it.  A
 /// loop has a preheader if there is only one edge to the header of the loop
-/// from outside of the loop.  If this is the case, the block branching to the
-/// header of the loop is the preheader node.
+/// from outside of the loop and it is legal to hoist instructions into the
+/// predecessor. If this is the case, the block branching to the header of the
+/// loop is the preheader node.
 ///
 /// This method returns null if there is no preheader for the loop.
 ///
 template<class BlockT, class LoopT>
 BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {
   // Keep track of nodes outside the loop branching to the header...
   BlockT *Out = getLoopPredecessor();
   if (!Out) return nullptr;
 
+  // Make sure we are allowed to hoist instructions into the predecessor.
+  if (!Out->isLegalToHoistInto())
+    return nullptr;
+
   // Make sure there is only one exit out of the preheader.
   typedef GraphTraits<BlockT*> BlockTraits;
   typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
   ++SI;
   if (SI != BlockTraits::child_end(Out))
     return nullptr;  // Multiple exits from the block, must not be a preheader.
 
   // The predecessor has exactly one successor, so it is a preheader.

llvm/trunk/include/llvm/CodeGen/MachineBasicBlock.h

#endif
   void setIsEHFuncletEntry(bool V = true) { IsEHFuncletEntry = V; }
 
   /// Returns true if this is the entry block of a cleanup funclet.
   bool isCleanupFuncletEntry() const { return IsCleanupFuncletEntry; }
 
   /// Indicates if this is the entry block of a cleanup funclet.
   void setIsCleanupFuncletEntry(bool V = true) { IsCleanupFuncletEntry = V; }
 
+  /// Returns true if it is legal to hoist instructions into this block.
+  bool isLegalToHoistInto() const;
+
   // Code Layout methods.
 
   /// Move 'this' block before or after the specified block.  This only moves
   /// the block, it does not modify the CFG or adjust potential fall-throughs at
   /// the end of the block.
   void moveBefore(MachineBasicBlock *NewAfter);
   void moveAfter(MachineBasicBlock *NewBefore);
 

llvm/trunk/include/llvm/IR/BasicBlock.h

public:
 
   /// \brief Return the landingpad instruction associated with the landing pad.
   const LandingPadInst *getLandingPadInst() const;
   LandingPadInst *getLandingPadInst() {
     return const_cast<LandingPadInst *>(
                     static_cast<const BasicBlock *>(this)->getLandingPadInst());
   }
 
+  /// \brief Return true if it is legal to hoist instructions into this block.
+  bool isLegalToHoistInto() const;
+
 private:
   /// \brief Increment the internal refcount of the number of BlockAddresses
   /// referencing this BasicBlock by \p Amt.
   ///
   /// This is almost always 0, sometimes one possibly, but almost never 2, and
   /// inconceivably 3 or more.
   void AdjustBlockAddressRefCount(int Amt) {
     setValueSubclassData(getSubclassDataFromValue()+Amt);

llvm/trunk/lib/CodeGen/MachineBasicBlock.cpp

 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void MachineBasicBlock::dump() const {
   print(dbgs());
 }
 #endif
 
+bool MachineBasicBlock::isLegalToHoistInto() const {
+  if (isReturnBlock() || hasEHPadSuccessor())
+    return false;
+  return true;
+}
+
 StringRef MachineBasicBlock::getName() const {
   if (const BasicBlock *LBB = getBasicBlock())
     return LBB->getName();
   else
     return StringRef("", 0);
 }
 
 /// Return a hopefully unique identifier for this block.

llvm/trunk/lib/IR/BasicBlock.cpp

bool BasicBlock::canSplitPredecessors() const {
   // This is perhaps a little conservative because constructs like
   // CleanupBlockInst are pretty easy to split.  However, SplitBlockPredecessors
   // cannot handle such things just yet.
   if (FirstNonPHI->isEHPad())
     return false;
   return true;
 }
 
+bool BasicBlock::isLegalToHoistInto() const {
+  auto *Term = getTerminator();
+  // No terminator means the block is under construction.
+  if (!Term)
+    return true;
+
+  // If the block has no successors, there can be no instructions to hoist.
+  assert(Term->getNumSuccessors() > 0);
+
+  // Instructions should not be hoisted across exception handling boundaries.
+  return !Term->isExceptional();
+}
+
 /// This splits a basic block into two at the specified
 /// instruction.  Note that all instructions BEFORE the specified iterator stay
 /// as part of the original basic block, an unconditional branch is added to
 /// the new BB, and the rest of the instructions in the BB are moved to the new
 /// BB, including the old terminator.  This invalidates the iterator.
 ///
 /// Note that this only works on well formed basic blocks (must have a
 /// terminator), and 'I' must not be the end of instruction list (which would

llvm/trunk/test/Transforms/LoopRotate/catchret.ll

+; RUN: opt < %s -loop-rotate -S | FileCheck %s
+
+target triple = "x86_64-pc-windows-msvc"
+
+declare void @always_throws()
+
+define i32 @test() personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*) {
+entry:
+  invoke void @always_throws()
+          to label %continue unwind label %catch.dispatch
+
+continue:
+  unreachable
+
+catch.dispatch:
+  %t0 = catchswitch within none [label %catch] unwind to caller
+
+catch:
+  %t1 = catchpad within %t0 [i8* null, i32 64, i8* null]
+  catchret from %t1 to label %for.cond
+
+for.cond:
+  %sum = phi i32 [ %add, %for.body ], [ 0, %catch ]
+  %i = phi i32 [ %inc, %for.body ], [ 0, %catch ]
+  %cmp = icmp slt i32 %i, 1
+  br i1 %cmp, label %for.body, label %return
+
+for.body:
+  %add = add nsw i32 1, %sum
+  %inc = add nsw i32 %i, 1
+  br label %for.cond
+
+return:
+  ret i32 0
+}
+
+; CHECK: catch:
+; CHECK-NEXT: catchpad
+; CHECK-NEXT: catchret
+
+declare i32 @__CxxFrameHandler3(...)