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

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

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 don't fully understand this area but from reading the code, I think
the invariants are:

* "Loop" instances are only created for reachable loops. This is
because the loops are gathered by doing a traversal from the dom tree
node and this traversal won't see any unreachable loops.

* If your pass breaks / modifies edges in the CFG, it must cause a
recomputation of the loop nest. IOW, if you are able to hit this
assert, then it means you have somehow ended up with a "stale" Loop
instance.

-- Sanjoy