[LLVMdev] Is loop header required to have at least one predecessor outside the loop?

[Chen Li]

Hi, 

I was reading some loop related code and I don’t quite understand an assertion in LoopBase<BlockT, LoopT>::getLoopPredecessor().

/// getLoopPredecessor - If the given loop's header has exactly one unique
/// predecessor outside the loop, return it. Otherwise return null.
/// This is less strict that the loop "preheader" concept, which requires
/// the predecessor to have exactly one successor.
///
template<class BlockT, class LoopT>
BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
  // Keep track of nodes outside the loop branching to the header...
  BlockT *Out = nullptr;

  // Loop over the predecessors of the header node...
  BlockT *Header = getHeader();
  typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
  for (typename InvBlockTraits::ChildIteratorType PI =
         InvBlockTraits::child_begin(Header),
         PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) {
    typename InvBlockTraits::NodeType *N = *PI;
    if (!contains(N)) {     // If the block is not in the loop...
      if (Out && Out != N)
        return nullptr;     // Multiple predecessors outside the loop
      Out = N;
    }
  }

  // Make sure there is only one exit out of the preheader.
  assert(Out && "Header of loop has no predecessors from outside loop?");
  return Out;
}

The function tries to find if there’s an unique predecessor outside of the loop for the loop header. At the very bottom, it asserts the loop header must have at least one such predecessor outside the loop (there’s an early return for cases there are more than one predecessors). But is it correct? For normal cases, I think it is. But what if the loop is dead code and unreachable? If you call this function in the middle of some kind dead code elimination, there are chances you will hit the assertion (in fact, I did hit it and crash the compiler). 

I removed this assertion and the build still passed all make check-all tests. So I don’t think there is anything depend on this or llvm has missed some test cases here. Does anyone know if there is a specific reason to have this assertion?

thanks,
chen  







-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150722/365c10c9/attachment.html>