Page MenuHomePhabricator

[LoopNest] Allow empty basic blocks without loops
ClosedPublic

Authored by Whitney on Mon, Dec 21, 2:00 PM.

Diff Detail

Event Timeline

Whitney created this revision.Mon, Dec 21, 2:00 PM
Whitney requested review of this revision.Mon, Dec 21, 2:00 PM

Alternatively, we could rely on SimplifyCFG to remote such empty BBs?

Would we want to allow such empty blocks between outer header and inner preheader as well?

llvm/lib/Analysis/LoopNestAnalysis.cpp
215

I'd prefer them as separate asserts.

224

To clarify: the Visited set is used to detect an infinite loop?

227
Whitney updated this revision to Diff 313443.Tue, Dec 22, 3:26 PM
Whitney marked 3 inline comments as done.
  • Addressed review comments
  • Moved skipEmptyBlockUntil to BasicBlockUtils, because it is not specific to loop nest.

Alternatively, we could rely on SimplifyCFG to remote such empty BBs?

SimplifyCFG could be used to fold empty blocks, but we may want to know if the loop nest is perfect in between SimplifyCFG invocations.
And there are times where we intentionally have empty blocks, e.g. dedicated exits.

Would we want to allow such empty blocks between outer header and inner preheader as well?

It is being allowed in this patch,

if (OuterLoopHeader != InnerLoopPreHeader) {
  const BasicBlock &SingleSucc =
      skipEmptyBlockUntil(OuterLoopHeader, InnerLoopPreHeader);

  // no conditional branch present
  if (&SingleSucc != InnerLoopPreHeader) {
llvm/lib/Analysis/LoopNestAnalysis.cpp
224

Yes, to avoid running into an infinite loop.

Whitney updated this revision to Diff 313472.Tue, Dec 22, 7:42 PM

Allow empty blocks between inner loop guard successor to inner loop preheader or inner loop guard successor the outer loop latch.

Meinersbur accepted this revision.Mon, Jan 4, 10:06 AM

LGTM

llvm/lib/Analysis/LoopNestAnalysis.cpp
224

Could you add a comment to clarify?

This revision is now accepted and ready to land.Mon, Jan 4, 10:06 AM
Whitney updated this revision to Diff 314408.Mon, Jan 4, 10:47 AM

Added comment to clarify Visited.

Whitney marked an inline comment as done.Mon, Jan 4, 10:50 AM
This revision was automatically updated to reflect the committed changes.
This revision is now accepted and ready to land.Mon, Jan 4, 12:43 PM
Whitney updated this revision to Diff 314477.Mon, Jan 4, 3:59 PM

Fix BUILD_SHARED_LIBS build failure.

This revision was automatically updated to reflect the committed changes.
dblaikie added inline comments.
llvm/lib/Analysis/LoopNestAnalysis.cpp
19

While not, I think, technically impossible - this is a rather "interesting" dependency to add. (generally Analysis can't depend on Transforms, because Transforms depend on Analysis - though Transforms/Utils doesn't depend on Transforms, so we can have the diamond of Analysis depends on Transforms and Transforms and Analysis depend on Transforms/Utils)

But this is missing the CMakeLists.txt update to indicate that Analysis depends on TransformUtils.

While the dependency is technically possible, I think it might be better to revert this patch (& later ones in the series) before having a broader discussion (possibly on llvm-dev) about this new dependency due to its subtlety. Perhaps some utilities should move to Analysis or an Analysis/Utils, or an IR/Utils instead of living in Transforms/Utils, if they aren't actually doing transformations?

Meinersbur added inline comments.Tue, Jan 5, 11:45 AM
llvm/lib/Analysis/LoopNestAnalysis.cpp
19

I think this header is not needed anymore. It was included for skipEmptyBlockUntil, but this function has been moved to Analysis/LoopNestAnalysis.h because of the BUILD_SHARED_LIBS build failure which resultet from the layering violation you are referring to.

@Whitney Can you remove this #include in trunk/main?

Whitney marked an inline comment as done.Tue, Jan 5, 12:00 PM
Whitney added inline comments.
llvm/lib/Analysis/LoopNestAnalysis.cpp
19

opps, this include is no longer needed, I just forgot to remove it.
Thanks for pointing it out.

Whitney marked an inline comment as done.Tue, Jan 5, 12:03 PM
Whitney added inline comments.
llvm/lib/Analysis/LoopNestAnalysis.cpp
19

@Meinersbur Yes, you beat me to it.