Domain adjustment needs to consider potentially entered loop even if multiple are left

[Quuxplusone]

Bugzilla Link	PR35434
Status	NEW
Importance	P enhancement
Reported by	Johannes Doerfert (jdoerfert@anl.gov)
Reported on	2017-11-27 07:01:24 -0800
Last modified on	2018-02-12 14:48:51 -0800
Version	unspecified
Hardware	PC Linux
CC	llvm-bugs@lists.llvm.org, llvm@meinersbur.de
Fixed by commit(s)
Attachments	0001-Fix-When-multiple-loops-are-left-a-loop-can-be-enter.patch (6097 bytes, text/plain)
Blocks
Blocked by
See also

Created attachment 19478
Test case + fix

The attached test case (see patch) shows how the domain generation uses domain
constraints of a non-related loop if multiple loops are left and one is entered
when traversing a single CFG edge. A potential fix is also included in the
patch. Unit tests pass but no other testing was performed.

[Quuxplusone]

Attached 0001-Fix-When-multiple-loops-are-left-a-loop-can-be-enter.patch (6097 bytes, text/plain): Test case + fix

[Quuxplusone]

Patch seems reasonable to me.

Is it correct that at most one loop can be entered at a time? Otherwise we have a few more cases to handle.

[Quuxplusone]

(In reply to Michael Kruse from comment #1)
> Patch seems reasonable to me.
>
> Is it correct that at most one loop can be entered at a time? Otherwise we
> have a few more cases to handle.

Since we only allow/deal with natural loops we can expect that yes.

Let's assume we could enter two natural loops at the same time. Since the two
loops have to be nested they form two SCCs in the CFG (one for the inner loop
and one for the whole loop nest). Note that the nesting implies that the outer
loop is reachable from the outside. Assuming now we have an edge that targets
the inner one but the source is not in the SCC of the whole loop nest
(otherwise the source would be, at least, in the outer loop, thus at most one
loop would be entered). This edge, creates a second entry block for the outer
loop (SCC) as the source is not in the outer loop (SCC) but the target is and
the outer loop (SCC) already had an entry block. This assums again the source
was reachable. Two entries for a single SCC should not form a natural loop
which contradicts our initial assumption.

Does that sound right?

[Quuxplusone]

I did not follow your argument. It shows that we cannot 'skip' the outer loop's header (with the additional assumption that the assumed edge's target is not the outer loop's header). This can also be shown given that a natural loop can only be entered by its header. What if the two loops share the same header?

@grosser: I think the patch is sound. How to proceed?

[Quuxplusone]

(In reply to Michael Kruse from comment #3)
> I did not follow your argument. It shows that we cannot 'skip' the outer
> loop's header (with the additional assumption that the assumed edge's target
> is not the outer loop's header). This can also be shown given that a natural
> loop can only be entered by its header.

I don't recall the details anymore, sorry.

> What if the two loops share the same header?

Same header <=> same natural loop.

[Quuxplusone]

> Same header <=> same natural loop.

Ok, I got confused by a comment in LoopInfo.cpp:

// Note that the
// loops identified may actually be several natural loops that share the same
// header node... not just a single natural loop.

[Quuxplusone]

(In reply to Michael Kruse from comment #5)
> > Same header <=> same natural loop.
>
> Ok, I got confused by a comment in LoopInfo.cpp:
>
> // Note that the
> // loops identified may actually be several natural loops that share the same
> // header node... not just a single natural loop.

Maybe it is a terminology problem on my side.

Regardless of the names, all that is needed, and all that LoopInfo provides, is
a strongly connected component which includes a block that dominates the
strongly connected component. This block is the loop header, all others are
contained in the loop. Each such strongly connected component is recognized as
a loop by LoopInfo, any other SCC is not (since it would be irreducible). Note
that neither LoopInfo nor me does require a single back edge or exiting edge.