The current statement domain derivation algorithm does not (always) consider that different exit blocks of a loop can have different conditions to be reached.
From the code
for (int i = n; ; i-=2) {
if (i <= 0) goto even;
if (i <= 1) goto odd;
A[i] = i;
}
even:
A[0] = 42;
return;
odd:
A[1] = 21;
return;Polly currently derives the following domains:
Stmt_even_critedge
Domain :=
[n] -> { Stmt_even_critedge[] };
Stmt_odd
Domain :=
[n] -> { Stmt_odd[] : (1 + n) mod 2 = 0 and n > 0 };while the domain for the odd case is correct, Stmt_even is assumed to be executed unconditionally, which is obviously wrong. While projecting out the loop dimension in adjustDomainDimensions, it does not consider that there are other exit condition that have matched before.
I don't know a how to fix this without changing a lot of code. Therefore I suggest to disable multiple loop exits to fix the miscompile of test-suite's uuencode.
The odd condition is transformed by LLVM to %cmp1 = icmp eq i64 %indvars.iv, 1 such that the project_out in adjustDomainDimensions indeed only matches for odd n (using this condition only, we'd have an infinite loop otherwise).
The even condition manifests as %cmp = icmp slt i64 %indvars.iv, 3. Because buildDomainsWithBranchConstraints does not consider other exit conditions, it has to assume that the induction variable will eventually be lower than 3 and taking this exit.
IMHO we need to reuse the algorithm that determines the number of iterations (addLoopBoundsToHeaderDomain) to determine which exit condition applies first. It has to happen in buildDomainsWithBranchConstraints because the result will need to propagate to successor BBs. Currently addLoopBoundsToHeaderDomain just look for union of all backedge conditions (which means leaving not the loop here). The patch in [[ llvm.org/PR35465 | PR35465 ]] changes it to look for exit conditions instead. This is required because there might be other exit conditions that do not alternatively go back to the loop header.