This is an archive of the discontinued LLVM Phabricator instance.

[Polly] Fix assertion due to loop overlap with nonaffine region.
ClosedPublic

Authored by huihuiz on Jun 13 2016, 3:41 PM.

Details

Summary

Reject and report regions that contains loops overlapping nonaffine region.
This situation typically happens in the presence of inifinite loops.

This addresses bug PR28071.

Diff Detail

Repository
rL LLVM

Event Timeline

huihuiz updated this revision to Diff 60620.Jun 13 2016, 3:41 PM
huihuiz retitled this revision from to Fix assertion due to loop overlap with nonaffine region. .
huihuiz updated this object.
huihuiz added reviewers: grosser, Meinersbur, Unknown Object (User).
huihuiz set the repository for this revision to rL LLVM.
huihuiz added a project: Restricted Project.
huihuiz added a reviewer: zinob.
huihuiz added a subscriber: pollydev.
Meinersbur edited reviewers, added: jdoerfert; removed: Unknown Object (User).Jun 14 2016, 11:15 AM
Meinersbur edited edge metadata.

Thank you for submitting the patch

Some remarks for submitting Polly patches:

  • Johannes' username is "jdoerfert" (Without leading underscore)
  • Prefix the title with "[Polly] " (but not when committing)
  • Also add "llvm-commits" to subscribers

Such non-properly nested loops and regions are strange and we maybe should those generally. This is Johannes' code and therefore I'd wait for his response.

include/polly/ScopDetectionDiagnostic.h
520

If L and R do not overlap, there isn't even a reason to create a ReportLoopOverlapWithNonAffineRegion object, ie. are always set.

Try to give L and R independent descriptions.

lib/Analysis/ScopDetection.cpp
308–309

Reject if the surrounding loop does not entirely contain the nonaffine region.

310

This condition seems unnecessary. Surrounding loops should generally entirely contain all its statements.

1061–1062

addOverApproximatedRegion also returns false if all boxed loops are disallowed using -polly-allow-nonaffine-loops=false. We'd get a false invalid report in this case.

lib/Analysis/ScopDetectionDiagnostic.cpp
343

overlaps

356

Loop overlaps with nonaffine subregion.

test/ScopDetectionDiagnostics/ReportLoopOverlapWithNonAffineRegion.ll
100–150 ↗(On Diff #60620)

Remove unnecessary lines: debug info, attributes

jdoerfert edited edge metadata.Jun 15 2016, 2:16 AM

Such non-properly nested loops and regions are strange and we maybe should those generally. This is Johannes' code and therefore I'd wait for his response.

I agree with the first part but not with the second. Please feel free to decide on your own. Thanks for the patch and the review!

hiraditya added inline comments.Jun 15 2016, 10:47 AM
lib/Analysis/ScopDetection.cpp
1060

No need to add else after 'return true'.

test/ScopDetectionDiagnostics/ReportLoopOverlapWithNonAffineRegion.ll
150 ↗(On Diff #60620)

You can use opt -strip-debug, see opt --help for more info.

Meinersbur added inline comments.Jun 15 2016, 11:01 AM
lib/Analysis/ScopDetection.cpp
316–317

Since Regions are Single-Entry Single-Exit, checking the Entry and Exit (Exiting) nodes should be enough.

Think about ranges: A range a subrange the other if both ends are within the other range. It might be possible to iterate over the region's Exiting nodes by exploiting properties the Exit node in the DominatorTree (see Region::contains).

huihuiz updated this revision to Diff 60941.Jun 15 2016, 5:57 PM
huihuiz retitled this revision from Fix assertion due to loop overlap with nonaffine region. to [Polly] Fix assertion due to loop overlap with nonaffine region. .
huihuiz added a subscriber: llvm-commits.

Refine the logic of checking loop overlap with nonaffine subregion.

Thank you for the update.

You changed the contains test to only check contained Loop. Are you sure this is sufficient? The Region might contain a single non-loop BasicBlock that is outside of the surrounding loop. Or is there a reason why this cannot happen?

Huihui is right, just checking Entry and Exiting blocks is not enough.

The loop is:
Loop at depth 1 containing: %for.cond<header><exiting>,%for.body<exiting>,%if.else,%if.end,%for.inc<latch>

The region is:

[2] for.body => if.else

Due to how a region is interpreted, %if.then and %while.body belong to the region, even though there is no path from the blocks to the exit node, it just loops infinitely. Loops exclude such dead-end blocks.

Naively, I'd assume regions being 'single entry - single exit' parts that each of the blocks in a region has a path to the exit region. This might be due to the definition of Region::contains
``
return (DT->dominates(entry, BB) && !(DT->dominates(exit, BB) && DT->dominates(entry, exit)));
``
to get around using the postdominator tree. It also means that the definition of Region::contains(Loop *) is wrong(!), ie. this behaviour doesn't seem to be intended. For fixing this, either Regions::contains(Loop*) must be changed or the defintion of what we undesrstand by a region.

For this patch I'd prefer checking all BBs instead of only the loops. Not only infinite loops can be dead-ends, but also Unreachable instructions. These are currently caught by polly::isErrorBlock, but maybe isErrorBlock could/should also be extended to recognize dead-end loops. I'd prefer a single mechanism for such cases instead of multiple in different parts of the code.

Huihui, can you add a descriptive comment about these findings into this patch (that is, why a region is not entirely contained in a loop)? I'd accept it even when only checking boxed loops, assuming that the UnreachableInst case will be caught by isErrorBlock().

test/ScopDetectionDiagnostics/ReportLoopOverlapWithNonAffineSubRegion.ll
2–3

Please use %loadPolly. It allows unit testing when using -load LLVMPolly.so. -polly-process-unprofitable is automatically added with it.

Ie.

; RUN: opt %loadPolly -pass-remarks-missed="polly-detect" -polly-allow-nonaffine-loops -analyze  -polly-detect < %s 2>&1 | FileCheck %s --check-prefix=REJECTLOOPOVERLAPREGION
; RUN: opt %loadPolly -pass-remarks-missed="polly-detect" -polly-allow-nonaffine-loops=false -analyze  -polly-detect < %s 2>&1 | FileCheck %s --check-prefix=REJECTNONAFFINELOOPS

Sorry for not noticing earlier.

Thanks for the review and comments!

For cases where loop overlap with nonaffine subregion, typically happens in the presence of infinite loop. That neither the surrounding loop contains the nonaffine subregion, nor the nonaffine subregion contains the surrounding loop. That said, the surrounding loop does not entirely contain the nonaffine subregion.

When presence with infinite loop, using entry and existing bb of nonaffine subregion to check if surrounding loop contains this region is not sufficient.
In this case, for nonaffine subregion, the entry (for.body) and existing block (for.body) are contained in the surrounding loop (%for.cond<header><exiting>,%for.body<exiting>,%if.else,%if.end,%for.inc<latch>). However, there exist other basic blocks not contained in the surrounding loop. We use the set of nonaffine loops of this nonaffine subregion for checking, to save compile time overhead.

This patch handles cases with dead-end loops, assuming cases of UnreachableInst caught by isErrorBlock().

I have updated this patch with fix for the test case, please help commit and merge this patch, thanks!

huihuiz updated this revision to Diff 61392.Jun 21 2016, 9:38 AM
Meinersbur accepted this revision.Jun 27 2016, 12:11 PM
Meinersbur edited edge metadata.

Committed in r273905.

This revision is now accepted and ready to land.Jun 27 2016, 12:11 PM
Meinersbur closed this revision.Jun 27 2016, 12:11 PM