llvm dev - Jul 2015 - [LLVMdev] 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  







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

On Wed, Jul 22, 2015 at 9:47 PM, Chen Li <meloli87 at gmail.com>
wrote:
> 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
>
> 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
>
>
>
>
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>