This is an archive of the discontinued LLVM Phabricator instance.

Helper functions to verify SESE, SEME
Needs ReviewPublic

Authored by hiraditya on Jul 19 2016, 7:23 PM.
This revision needs review, but there are no reviewers specified.

Details

Reviewers
None
Summary

Adding functionalities to verify

  1. if a region is Single Entry Single Exit (SESE),
  2. if a region is Single Entry Multiple Exit (SEME),

The test cases to exercise these functionality will be provided in subsequent patches of loop-rotation where these APIs are used.

Worked in collaboration with Sebastian Pop.

Diff Detail

Event Timeline

hiraditya updated this revision to Diff 64631.Jul 19 2016, 7:23 PM
hiraditya retitled this revision from to Helper functions to verify SESE, SEME and copySEME.
hiraditya updated this object.
hiraditya added reviewers: sanjoy, hfinkel.
hiraditya set the repository for this revision to rL LLVM.
anemet added a subscriber: anemet.Jul 21 2016, 11:02 AM
sanjoy requested changes to this revision.Sep 12 2016, 12:33 AM
sanjoy edited edge metadata.
sanjoy added inline comments.
llvm/include/llvm/Transforms/Utils/Cloning.h
238

This names are not helped by the fact that both Entry and Exit start with "E". :)

I'd suggest spelling them out in full, like isSingleEntrySingleExit.

Also, we don't use \brief in new doxygen comments, we build with autobrief now.

llvm/lib/Transforms/Utils/CloneFunction.cpp
795

Won't you also have to insert PHI nodes? If this depends on LCSSA somehow then that should be documented, and asserted if possible.

810

a constant or defined outside the SEME?

824

Are you assuming that Blocks[0] is the entry into the SEME? If so, then document that. Also, what if Blocks[0] is the function entry and has no IDom?

825

Not sure if getBlock actually ever returns null. Perhaps the assert should be on the result of getIDom?

837

Don't you sometimes have to _create_ a new loop? That is

for (;;)
  for (;;)  // SEME

Clone =>

for (;;) {
  for (;;)  // SEME.0
  for (;;)  // SEME.1 -> you need a new llvm::Loop for this
}
848

When can VMap[BB] be null?

850

What if NewBB->getTerminator() is a switch? If you don't handle that case yet, please add an assert that would fail with a switch.

855

Canonical LLVM form would be:

if (auto *NewSucc = ...)
  BI->setSuccessor(...);
861

*copied

863

Please spell out "orig" and "imm-dom".

868

Instead of asserting NewBB is not null, just use cast instead of cast_or_null.

873

I would not do this here -- I'd handle the entry block separately, and only handle non-entry blocks here. Then I'd change the cast_or_null above to cast to catch the (buggy) case where Dom is not in VMap.

883

It feels odd to have a separate function for just this one step. Is step 5 special in some way (e.g. maybe you're planning to re-use it)?

This revision now requires changes to proceed.Sep 12 2016, 12:33 AM
hiraditya updated this revision to Diff 72057.Sep 21 2016, 8:45 AM
hiraditya updated this object.
hiraditya edited edge metadata.
hiraditya removed rL LLVM as the repository for this revision.
hiraditya marked 5 inline comments as done.

Moved copyseme to loop-rotation D22630. loop-rotation requires copying blocks which is not exactly an SEME.

hiraditya retitled this revision from Helper functions to verify SESE, SEME and copySEME to Helper functions to verify SESE, SEME.Sep 21 2016, 8:45 AM
hiraditya edited edge metadata.
hiraditya marked an inline comment as done.
hfinkel edited edge metadata.Oct 3 2016, 1:12 PM

Ping

Can you please add these functions somewhere other than in Cloning.h. That's not an obvious place for them to be, and they don't have anything to do with cloning.

Maybe they should just be utility functions on DomTree itself?

Ping

Can you please add these functions somewhere other than in Cloning.h. That's not an obvious place for them to be, and they don't have anything to do with cloning.

Maybe they should just be utility functions on DomTree itself?

Ok, I'll move them to LoopRotation.cpp since that is the only pass using these.

hiraditya abandoned this revision.Oct 4 2016, 7:41 AM
hiraditya reclaimed this revision.Jul 25 2018, 11:28 AM
hiraditya removed reviewers: sanjoy, hfinkel.

Don't want to lose it, yet!