[ScopDetection] Remove redundant checks for endless loops
authorTobias Grosser <tobias@grosser.es>
Tue, 20 Sep 2016 17:05:22 +0000 (17:05 +0000)
committerTobias Grosser <tobias@grosser.es>
Tue, 20 Sep 2016 17:05:22 +0000 (17:05 +0000)
commit349d1c33685b47e14477763ef1530a6395171f4e
tree91644098aa211222858ae43f6c57e95fe371de3c
parent03ffa797ad4fe8f85da532aa3f687841a60b4c0c
[ScopDetection] Remove redundant checks for endless loops

Summary:
Both `canUseISLTripCount()` and `addOverApproximatedRegion()` contained checks
to reject endless loops which are now removed and replaced by a single check
in `isValidLoop()`.

For reporting such loops the `ReportLoopOverlapWithNonAffineSubRegion` is
renamed to `ReportLoopHasNoExit`. The test case
`ReportLoopOverlapWithNonAffineSubRegion.ll` is adapted and renamed as well.

The schedule generation in `buildSchedule()` is based on the following
assumption:

Given some block B that is contained in a loop L and a SESE region R,
we assume that L is contained in R or the other way around.

However, this assumption is broken in the presence of endless loops that are
nested inside other loops. Therefore, in order to prevent erroneous behavior
in `buildSchedule()`, r265280 introduced a corresponding check in
`canUseISLTripCount()` to reject endless loops. Unfortunately, it was possible
to bypass this check with -polly-allow-nonaffine-loops which was fixed by adding
another check to reject endless loops in `allowOverApproximatedRegion()` in
r273905. Hence there existed two separate locations that handled this case.

Thank you Johannes Doerfert for helping to provide the above background
information.

Reviewers: Meinersbur, grosser

Subscribers: _jdoerfert, pollydev

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

Contributed-by: Matthias Reisinger <d412vv1n@gmail.com>
llvm-svn: 281987
polly/include/polly/ScopDetectionDiagnostic.h
polly/lib/Analysis/ScopDetection.cpp
polly/lib/Analysis/ScopDetectionDiagnostic.cpp
polly/test/ScopDetectionDiagnostics/ReportLoopHasNoExit.ll [moved from polly/test/ScopDetectionDiagnostics/ReportLoopOverlapWithNonAffineSubRegion.ll with 76% similarity]