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

[Sanjoy Das]

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
>