Helper functions to verify SESE, SEME

[hiraditya]

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.

[sanjoy]

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)?

[hiraditya]

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

[hiraditya]

Ping

[hfinkel]

In D22558#559429, @hiraditya wrote:

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?

[hiraditya]

In D22558#559647, @hfinkel wrote:

In D22558#559429, @hiraditya wrote:

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]

Merged the changes with D22630

[hiraditya]

Don't want to lose it, yet!

llvm/include/llvm/Transforms/Utils/Cloning.h

Loop *cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB,
                              const Twine &NameSuffix, LoopInfo *LI,
                              DominatorTree *DT,
                              SmallVectorImpl<BasicBlock *> &Blocks);
 
 /// \brief Remaps instructions in \p Blocks using the mapping in \p VMap.
 void remapInstructionsInBlocks(const SmallVectorImpl<BasicBlock *> &Blocks,
                                ValueToValueMapTy &VMap);
 
+/// Returns true of the region formed by [Entry, Exit] is a
+/// single-entry-single-exit (SESE) region. All the traces from \p Entry to
+/// \p Exit should be dominated by \p Entry and post-dominated by \p Exit.
+bool isSingleEntrySingleExit(const BasicBlock *Entry, const BasicBlock *Exit,
+                             DominatorTree *DT, DominatorTree *PDT);
+
+/// Returns true of the region formed by [Entry, Exit] is a
+/// single-entry-multiple-exit (SEME) region. All the traces from \p Entry
+/// which leads to the \p Exit are analyzed.
+bool isSingleEntryMultipleExit(const BasicBlock *Entry, const BasicBlock *Exit,
+                               DominatorTree *DT);
 } // End llvm namespace
 
 #endif

llvm/lib/Transforms/Utils/CloneFunction.cpp

Loop *llvm::cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB,
   // Move them physically from the end of the block list.
   F->getBasicBlockList().splice(Before->getIterator(), F->getBasicBlockList(),
                                 NewPH);
   F->getBasicBlockList().splice(Before->getIterator(), F->getBasicBlockList(),
                                 NewLoop->getHeader()->getIterator(), F->end());
 
   return NewLoop;
 }
+
+bool llvm::isSingleEntrySingleExit(const BasicBlock *Entry,
+                                   const BasicBlock *Exit,
+                                   DominatorTree *DT, DominatorTree *PDT) {
+  if (!DT->dominates(Entry, Exit))
+    return false;
+
+  if (!PDT->dominates(Exit, Entry))
+    return false;
+
+  for (auto I = df_begin(Entry), E = df_end(Entry); I != E;) {
+    if (*I == Exit) {
+      I.skipChildren();
+      continue;
+    }
+    if (!DT->dominates(Entry, *I))
+      return false;
+    ++I;
+  }
+  return true;
+}
+
+bool llvm::isSingleEntryMultipleExit(const BasicBlock *Entry,
+                                     const BasicBlock *Exit,
+                                     DominatorTree *DT) {
+  if (!DT->dominates(Entry, Exit))
+    return false;
+
+  for (auto I = idf_begin(Exit), E = idf_end(Exit); I != E;) {
+    if (*I == Entry) {
+      I.skipChildren();
+      continue;
+    }
+
+    if (!DT->dominates(Entry, *I))
+      return false;
+
+    ++I;
+  }
+  return true;
+}