If a region does not have more than one loop, we do not identify it as a Scop in ScopDetection. The main optimizations Polly is currently performing (tiling, preparation for outer-loop vectorization and loop fusion) are unlikely to have a positive impact on individual loops. In some cases, Polly's run-time alias checks or conditional hoisting may still have a positive impact, but those are mostly enabling transformations which LLVM already performs for individual loops. As we do not focus on individual loops, we leave them untouched to not introduce compile time regressions and execution time noise. This results in good compile time reduction (oourafft: -73.99%, smg2000: -56.25%).
Details
Details
Diff Detail
Diff Detail
Event Timeline
Comment Actions
Hi Pratik,
very good. Only minor comment. Could you extend the commit message to explain why individual loops are not interesting to us. Something like:
"The main optimizations Polly is currently performing (tiling, preparation for outer-loop vectorization and loop fusion) are unlikely to have a positive impact on individual loops. In some cases, Polly's run-time alias checks or conditional hoisting may still have a positive impact, but those are mostly enabling transformations which LLVM already performs for individual loops. As we do not focus on individual loops, we leave them untouched to not introduce compile time regressions and execution time noise."
| lib/Analysis/ScopDetection.cpp | ||
|---|---|---|
| 1041 | Please move the check before isValidExit and allBlocksValid. The new check is a lot cheaper and does not depend on Context information, so we should execute it early. (Leave the Context.hasStore && Context.hasLoad where they are). | |
| 1045 | This won't have an effect any more. Please drop this code, the corresponding option as well as the Context.hasAffineLoops variable. (I don't think it makes sense to have 'detect-unprofitable' options for each reason a scop can be unprofitable.) | |
Comment Actions
Removal of -polly-detect-scops-in-regions-without-loops causes these test-cases to fail.
Polly :: Isl/CodeGen/20120316-InvalidCast.ll Polly :: Isl/CodeGen/constant_condition.ll Polly :: Isl/CodeGen/simple_non_single_entry.ll Polly :: ScopDetect/parametric-multiply-in-scev.ll Polly :: ScopDetect/simple_non_single_entry.ll Polly :: ScopDetectionDiagnostics/ReportLoopBound-01.ll
Polly :: ScopDetect/non-affine-loop.ll:
Removal of -polly-detect-unprofitable in ALLOWNONAFFINELOOPSANDACCESSES case seems to fix it though I am not sure this is the correct way.
Comment Actions
Hi Pratik,
it seems we some minor things still need to be changed:
+bool ScopDetection::hasMoreThanOneLoop(Region *R) const {
+ Loop *EntryLoop = LI->getLoopFor(R->getEntry());
+ if (!EntryLoop)
+ return false;
+
+ if (!EntryLoop->getSubLoops().empty())
+ return true;
+
+ for (pred_iterator PI = pred_begin(R->getExit()), PE = pred_end(R->getExit());
+ PI != PE; ++PI)
+ if (R->contains(*PI))
+ if (EntryLoop != LI->getLoopFor(*PI))
+ return true;
+
+ return false;
+}
+Region *ScopDetection::expandRegion(Region &R) { // Initial no valid region was found (greater than R) std::unique_ptr<Region> LastValidRegion;@@ -823,7 +833,7 @@
false /*verifying*/); bool RegionIsValid = false;
- if (!DetectRegionsWithoutLoops && regionWithoutLoops(R, LI))
+ if (regionWithoutLoops(R, LI))
invalid<ReportUnprofitable>(Context, /*Assert=*/true, &R);
This causes most of the failures, i think this should be:
if (!DetectRegionsWithoutLoops && hasMoreThanOneLoop(&R))
...
we can do not need the later call to hasMoreThanOneLoop.
else RegionIsValid = isValidRegion(Context);@@ -956,6 +966,9 @@
if (CurRegion.getEntry() == &(CurRegion.getEntry()->getParent()->getEntryBlock())) return invalid<ReportEntry>(Context, /*Assert=*/true, CurRegion.getEntry());+
+ if(!DetectUnprofitable && !hasMoreThanOneLoop(&CurRegion))
+ invalid<ReportUnprofitable>(Context, /*Assert=*/true, &CurRegion);
This is now probably redundant.
if (!isValidExit(Context)) return false;@@ -968,11 +981,6 @@
if (!DetectUnprofitable && (!Context.hasStores || !Context.hasLoads)) invalid<ReportUnprofitable>(Context, /*Assert=*/true, &CurRegion);
- // Check if there was at least one non-overapproximated loop in the region or
- // we allow regions without loops.
- if (!DetectRegionsWithoutLoops && !Context.hasAffineLoops)
- invalid<ReportUnprofitable>(Context, /*Assert=*/true, &CurRegion);
And I am afraid, this and the related code can not be dropped. I forgot the case
that some of the loops we detect may indeed be non-affine, so even though the
region has two loops, some of them may be non-affine, such that the final number
of loops that are actually visible to us may be lower. So the hasAffineLoops still
can probably not be removed. Sorry for the unnecessary changes I asked for earlier.
Best,
Tobias
Comment Actions
Hi Pratik,
I just realized your review did not include the relevant mailing lists. Please include the 'polly' group in subsequent submissions.
Tobias
Comment Actions
Also, please consider contributing a follow-up patch that removes the flag:
-polly-detect-scops-in-regions-without-loops
This does not seem to be needed any more and its remaining functionality could likely be covered by -polly-detect-unprofitable
Please move the check before isValidExit and allBlocksValid. The new check is a lot cheaper and does not depend on Context information, so we should execute it early. (Leave the Context.hasStore && Context.hasLoad where they are).