Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[Polly] Schedule does not model irreducible control flow #26283

Closed
tobiasgrosser opened this issue Dec 21, 2015 · 4 comments
Closed

[Polly] Schedule does not model irreducible control flow #26283

tobiasgrosser opened this issue Dec 21, 2015 · 4 comments
Labels
bugzilla Issues migrated from bugzilla polly

Comments

@tobiasgrosser
Copy link
Contributor

Bugzilla Link 25909
Resolution FIXED
Resolved on Jan 22, 2016 03:52
Version unspecified
OS Linux
Attachments Irredubicle control flow
CC @jdoerfert

Extended Description

For a test cast that contains irregular control flow with loops (attached)
we do not generate loop dimensions in the schedule:

	Stmt_start_split
        Domain :=
            [p] -> { Stmt_start_split[] };
        Schedule :=
            [p] -> { Stmt_start_split[] -> [0] };
        MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 1]
            [p] -> { Stmt_start_split[] -> MemRef_cmp[] };
	Stmt_S1
        Domain :=
            [p] -> { Stmt_S1[] : p <= 0 };
        Schedule :=
            [p] -> { Stmt_S1[] -> [1] };
        MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 0]
            [p] -> { Stmt_S1[] -> MemRef_A[0] };
	Stmt_S2
        Domain :=
            [p] -> { Stmt_S2[] : p >= 1 };
        Schedule :=
            [p] -> { Stmt_S2[] -> [2] };
        MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 0]
            [p] -> { Stmt_S2[] -> MemRef_A[0] };

This is likely to be wrong and we should probably just detect irregular control flow and bail out if found.

@jdoerfert
Copy link
Member

There has to be a LLVM method to detect irreducible control... other passes should face similar problems when they rely on LoopInfo.

@tobiasgrosser
Copy link
Contributor Author

Johannes is right. We should use (or add) some functionality to LLVM to do so.

I investigated this a little a couple of weeks ago and there is currently no LLVM method that allows us to detect irreducible control flow. However if you grep for 'irreducible' in LLVM a couple of passes detect themselves irreducible control flow.

The implementation in lib/Analysis/BlockFrequencyInfoImpl.cpp seems to be at least partially independent of the rest of the pass. We might be able to split
it out in a helper routine and then just call it in ScopDetection.

One could claim that this functionality belongs into the LoopInfo pass, but keeping this information up to date (and the cost of doing so) might add cost and complexity that others won't appreciate. By calling a routine that identifies irreducible control in ScopDetection we could avoid this overhead

@tlattner
Copy link
Contributor

Move bugs to Polly product.

@tobiasgrosser
Copy link
Contributor Author

Since r258497 Polly refuses irregular control flow.

@llvmbot llvmbot transferred this issue from llvm/llvm-bugzilla-archive Dec 10, 2021
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bugzilla Issues migrated from bugzilla polly
Projects
None yet
Development

No branches or pull requests

3 participants