search

llvm / llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.
http://llvm.org
Other
28.03k stars 11.58k forks source link

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

Open jdoerfert opened 6 years ago

jdoerfert commented 6 years ago
Bugzilla Link 35434
Version unspecified
OS Linux
Attachments Test case + fix
CC @Meinersbur

Extended Description

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.

jdoerfert commented 6 years ago

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.

Meinersbur commented 6 years ago

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.

jdoerfert commented 6 years ago

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.

Meinersbur commented 6 years ago

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?

jdoerfert commented 6 years ago

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?

Meinersbur commented 6 years ago

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.