Skip to content

Commit

Permalink
[ScopDetect] Reject loop with multiple exit blocks.
Browse files Browse the repository at this point in the history
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
This patch rejects loops with multiple exist blocks 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 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.

Differential Revision: https://reviews.llvm.org/D45649

llvm-svn: 330858
  • Loading branch information
Meinersbur committed Apr 25, 2018
1 parent d8803d3 commit beffdb9
Showing 15 changed files with 520 additions and 1 deletion.
29 changes: 29 additions & 0 deletions polly/include/polly/ScopDetectionDiagnostic.h
Original file line number Diff line number Diff line change
@@ -90,6 +90,7 @@ enum class RejectReasonKind {

LoopBound,
LoopHasNoExit,
LoopHasMultipleExits,
LoopOnlySomeLatches,

FuncCall,
@@ -584,6 +585,34 @@ class ReportLoopHasNoExit : public RejectReason {
//@}
};

//===----------------------------------------------------------------------===//
/// Captures errors when a loop has multiple exists.
class ReportLoopHasMultipleExits : public RejectReason {
/// The loop that has multiple exits.
Loop *L;

const DebugLoc Loc;

public:
ReportLoopHasMultipleExits(Loop *L)
: RejectReason(RejectReasonKind::LoopHasMultipleExits), L(L),
Loc(L->getStartLoc()) {}

/// @name LLVM-RTTI interface
//@{
static bool classof(const RejectReason *RR);
//@}

/// @name RejectReason interface
//@{
std::string getRemarkName() const override;
const Value *getRemarkBB() const override;
std::string getMessage() const override;
const DebugLoc &getDebugLoc() const override;
std::string getEndUserMessage() const override;
//@}
};

//===----------------------------------------------------------------------===//
/// Captures errors when not all loop latches are part of the scop.
class ReportLoopOnlySomeLatches : public RejectReason {
12 changes: 12 additions & 0 deletions polly/lib/Analysis/ScopDetection.cpp
Original file line number Diff line number Diff line change
@@ -1297,6 +1297,18 @@ bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const {
if (!hasExitingBlocks(L))
return invalid<ReportLoopHasNoExit>(Context, /*Assert=*/true, L);

// The algorithm for domain construction assumes that loops has only a single
// exit block (and hence corresponds to a subregion). Note that we cannot use
// L->getExitBlock() because it does not check whether all exiting edges point
// to the same BB.
SmallVector<BasicBlock *, 4> ExitBlocks;
L->getExitBlocks(ExitBlocks);
BasicBlock *TheExitBlock = ExitBlocks[0];
for (BasicBlock *ExitBB : ExitBlocks) {
if (TheExitBlock != ExitBB)
return invalid<ReportLoopHasMultipleExits>(Context, /*Assert=*/true, L);
}

if (canUseISLTripCount(L, Context))
return true;

26 changes: 26 additions & 0 deletions polly/lib/Analysis/ScopDetectionDiagnostic.cpp
Original file line number Diff line number Diff line change
@@ -71,6 +71,7 @@ Statistic RejectStatistics[] = {
SCOP_STAT(LastAffFunc, ""),
SCOP_STAT(LoopBound, "Uncomputable loop bounds"),
SCOP_STAT(LoopHasNoExit, "Loop without exit"),
SCOP_STAT(LoopHasMultipleExits, "Loop with multiple exits"),
SCOP_STAT(LoopOnlySomeLatches, "Not all loop latches in scop"),
SCOP_STAT(FuncCall, "Function call with side effects"),
SCOP_STAT(NonSimpleMemoryAccess,
@@ -495,6 +496,31 @@ std::string ReportLoopHasNoExit::getEndUserMessage() const {
return "Loop cannot be handled because it has no exit.";
}

//===----------------------------------------------------------------------===//
// ReportLoopHasMultipleExits.

std::string ReportLoopHasMultipleExits::getRemarkName() const {
return "ReportLoopHasMultipleExits";
}

const Value *ReportLoopHasMultipleExits::getRemarkBB() const {
return L->getHeader();
}

std::string ReportLoopHasMultipleExits::getMessage() const {
return "Loop " + L->getHeader()->getName() + " has multiple exits.";
}

bool ReportLoopHasMultipleExits::classof(const RejectReason *RR) {
return RR->getKind() == RejectReasonKind::LoopHasMultipleExits;
}

const DebugLoc &ReportLoopHasMultipleExits::getDebugLoc() const { return Loc; }

std::string ReportLoopHasMultipleExits::getEndUserMessage() const {
return "Loop cannot be handled because it has multiple exits.";
}

//===----------------------------------------------------------------------===//
// ReportLoopOnlySomeLatches

6 changes: 6 additions & 0 deletions polly/test/ScopDetect/index_from_unpredictable_loop.ll
Original file line number Diff line number Diff line change
@@ -1,6 +1,12 @@
; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s --check-prefix=AFFINE
; RUN: opt %loadPolly -polly-scops -polly-allow-nonaffine -analyze < %s | FileCheck %s --check-prefix=NONAFFINE

; The SCoP contains a loop with multiple exit blocks (BBs after leaving
; the loop). The current implementation of deriving their domain derives
; only a common domain for all of the exit blocks. We disabled loops with
; multiple exit blocks until this is fixed.
; XFAIL: *

; The loop for.body => for.inc has an unpredictable iteration count could due to
; the undef start value that it is compared to. Therefore the array element
; %arrayidx101 that depends on that exit value cannot be affine.
6 changes: 6 additions & 0 deletions polly/test/ScopDetect/index_from_unpredictable_loop2.ll
Original file line number Diff line number Diff line change
@@ -1,6 +1,12 @@
; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s --check-prefix=AFFINE
; RUN: opt %loadPolly -polly-scops -polly-allow-nonaffine -analyze < %s | FileCheck %s --check-prefix=NONAFFINE

; The SCoP contains a loop with multiple exit blocks (BBs after leaving
; the loop). The current implementation of deriving their domain derives
; only a common domain for all of the exit blocks. We disabled loops with
; multiple exit blocks until this is fixed.
; XFAIL: *

; The loop for.body => for.inc has an unpredictable iteration count could due to
; the undef start value that it is compared to. Therefore the array element
; %arrayidx101 that depends on that exit value cannot be affine.
386 changes: 386 additions & 0 deletions polly/test/ScopDetectionDiagnostics/loop_has_multiple_exits.ll

Large diffs are not rendered by default.

Original file line number Diff line number Diff line change
@@ -1,6 +1,12 @@
; RUN: opt %loadPolly -polly-detect -polly-scops -analyze \
; RUN: -polly-allow-nonaffine-loops < %s | FileCheck %s

; The SCoP contains a loop with multiple exit blocks (BBs after leaving
; the loop). The current implementation of deriving their domain derives
; only a common domain for all of the exit blocks. We disabled loops with
; multiple exit blocks until this is fixed.
; XFAIL: *

; The BasicBlock "guaranteed" is always executed inside the non-affine subregion
; region_entry->region_exit. As such, writes accesses in blocks that always
; execute are MustWriteAccesses. Before Polly commit r255473, we only assumed
8 changes: 7 additions & 1 deletion polly/test/ScopInfo/complex-loop-nesting.ll
Original file line number Diff line number Diff line change
@@ -1,5 +1,11 @@
; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s

;
; The SCoP contains a loop with multiple exit blocks (BBs after leaving
; the loop). The current implementation of deriving their domain derives
; only a common domain for all of the exit blocks. We disabled loops with
; multiple exit blocks until this is fixed.
; XFAIL: *
;
; CHECK: Statements {
; CHECK-NEXT: Stmt_for_body_outer
; CHECK-NEXT: Domain :=
6 changes: 6 additions & 0 deletions polly/test/ScopInfo/isl_trip_count_multiple_exiting_blocks.ll
Original file line number Diff line number Diff line change
@@ -1,5 +1,11 @@
; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
;
; The SCoP contains a loop with multiple exit blocks (BBs after leaving
; the loop). The current implementation of deriving their domain derives
; only a common domain for all of the exit blocks. We disabled loops with
; multiple exit blocks until this is fixed.
; XFAIL: *
;
; CHECK: Domain :=
; CHECK: { Stmt_if_end[i0] : 0 <= i0 <= 1024 };
;
6 changes: 6 additions & 0 deletions polly/test/ScopInfo/loop-multiexit-succ-cond.ll
Original file line number Diff line number Diff line change
@@ -1,6 +1,12 @@
; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s --check-prefix=IR
;
; The SCoP contains a loop with multiple exit blocks (BBs after leaving
; the loop). The current implementation of deriving their domain derives
; only a common domain for all of the exit blocks. We disabled loops with
; multiple exit blocks until this is fixed.
; XFAIL: *
;
; Check that we do not crash and generate valid IR.
;
; CHECK: Assumed Context:
6 changes: 6 additions & 0 deletions polly/test/ScopInfo/multiple_exiting_blocks.ll
Original file line number Diff line number Diff line change
@@ -1,5 +1,11 @@
; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
;
; The SCoP contains a loop with multiple exit blocks (BBs after leaving
; the loop). The current implementation of deriving their domain derives
; only a common domain for all of the exit blocks. We disabled loops with
; multiple exit blocks until this is fixed.
; XFAIL: *
;
; CHECK: Domain :=
; CHECK: [N, P, Q] -> { Stmt_if_end[i0] : 0 <= i0 <= 1 + Q and i0 < N and (i0 < P or (P < 0 and i0 >= 2 + P)); Stmt_if_end[0] : N > 0 and ((P <= -2 and Q <= -2) or (P > 0 and Q <= -2) or P = -1) };
;
6 changes: 6 additions & 0 deletions polly/test/ScopInfo/multiple_exiting_blocks_two_loop.ll
Original file line number Diff line number Diff line change
@@ -1,5 +1,11 @@
; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
;
; The SCoP contains a loop with multiple exit blocks (BBs after leaving
; the loop). The current implementation of deriving their domain derives
; only a common domain for all of the exit blocks. We disabled loops with
; multiple exit blocks until this is fixed.
; XFAIL: *
;
; void foo(long n, float A[100]) {
; for (long j = 0; j < n; j++) {
; for (long i = j; i < n; i++) {
6 changes: 6 additions & 0 deletions polly/test/ScopInfo/schedule-const-post-dominator-walk-2.ll
Original file line number Diff line number Diff line change
@@ -1,5 +1,11 @@
; RUN: opt %loadPolly -analyze -polly-scops < %s | FileCheck %s

; The SCoP contains a loop with multiple exit blocks (BBs after leaving
; the loop). The current implementation of deriving their domain derives
; only a common domain for all of the exit blocks. We disabled loops with
; multiple exit blocks until this is fixed.
; XFAIL: *

; CHECK: Stmt_loopA[i0] -> [0, 0, 0]
; CHECK-DAG: Stmt_loopB[i0] -> [0, 0, 1]
; CHECK-DAG: Stmt_bbB[] -> [1, 0, 0]
6 changes: 6 additions & 0 deletions polly/test/ScopInfo/schedule-const-post-dominator-walk.ll
Original file line number Diff line number Diff line change
@@ -1,5 +1,11 @@
; RUN: opt %loadPolly -analyze -polly-scops < %s | FileCheck %s

; The SCoP contains a loop with multiple exit blocks (BBs after leaving
; the loop). The current implementation of deriving their domain derives
; only a common domain for all of the exit blocks. We disabled loops with
; multiple exit blocks until this is fixed.
; XFAIL: *

; CHECK: { Stmt_bb3[i0] -> [0, 0] };
; CHECK: { Stmt_bb2[] -> [1, 0] };

6 changes: 6 additions & 0 deletions polly/test/ScopInfo/switch-5.ll
Original file line number Diff line number Diff line change
@@ -1,6 +1,12 @@
; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
; RUN: opt %loadPolly -polly-ast -analyze < %s | FileCheck %s --check-prefix=AST
;
; The SCoP contains a loop with multiple exit blocks (BBs after leaving
; the loop). The current implementation of deriving their domain derives
; only a common domain for all of the exit blocks. We disabled loops with
; multiple exit blocks until this is fixed.
; XFAIL: *
;
; void f(int *A, int *B, int N) {
; for (int i = 0; i < N; i++) {
; A[i]++;

0 comments on commit beffdb9

Please sign in to comment.