Index: llvm/include/llvm/Transforms/Utils/Cloning.h
===================================================================
--- llvm/include/llvm/Transforms/Utils/Cloning.h
+++ llvm/include/llvm/Transforms/Utils/Cloning.h
@@ -231,6 +231,27 @@
 void remapInstructionsInBlocks(const SmallVectorImpl<BasicBlock *> &Blocks,
                                ValueToValueMapTy &VMap);
 
+/// \brief 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 isSESE(const BasicBlock *Entry, const BasicBlock *Exit, DominatorTree *DT,
+            DominatorTree *PDT);
+
+/// \brief 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 isSEME(const BasicBlock *Entry, const BasicBlock *Exit, DominatorTree *DT);
+
+/// \brief Clones the basic blocks (\p Blocks) of an SEME bounded by \p
+/// Exits. The mapping between original BBs and correponding copied BBs are
+/// populated in \p VMap. During copy the DOM and LI of CFG is updated.
+/// \returns The entry point of the copied SEME. \p NameSuffix is used to suffix
+/// name of the copied BBs. The copied SEME is also an SEME.
+BasicBlock* copySEME(const SmallVectorImpl<BasicBlock *> &Blocks,
+                     const SmallPtrSetImpl<BasicBlock *> &Exits,
+                     ValueToValueMapTy &VMap, const Twine &NameSuffix,
+                     DominatorTree *DT, LoopInfo *LI);
 } // End llvm namespace
 
 #endif
Index: llvm/lib/Transforms/Utils/CloneFunction.cpp
===================================================================
--- llvm/lib/Transforms/Utils/CloneFunction.cpp
+++ llvm/lib/Transforms/Utils/CloneFunction.cpp
@@ -710,3 +710,139 @@
 
   return NewLoop;
 }
+
+bool llvm::isSESE(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::isSEME(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;
+}
+
+// Helper function for copySEME. Adjusts the PHIs of all the \p Exits bounding
+// an SEME. \p VMap contains mapping of original BB vs copied BB.
+static void adjustExitingPhis(ValueToValueMapTy &VMap,
+                              const SmallPtrSetImpl<BasicBlock *> &Exits) {
+  for (BasicBlock *BB : Exits) {
+    for (Instruction &Inst : *BB) {
+      PHINode *PN = dyn_cast<PHINode>(&Inst);
+      if (!PN)
+        break;
+      bool EdgeFromOrigBB = false;
+      for (unsigned i = 0, e = PN->getNumOperands(); i != e; ++i) {
+        Value *CopyB = VMap[PN->getIncomingBlock(i)];
+        if (!CopyB) // Skip args coming from outside the SEME.
+          continue;
+        BasicBlock *CopyBB = cast<BasicBlock>(CopyB);
+        EdgeFromOrigBB = true;
+        Value *Op = PN->getIncomingValue(i);
+        if (Value *RenamedVal = VMap[Op])
+          PN->addIncoming(RenamedVal, CopyBB);
+        else
+          // When no mapping is available it must be a constant.
+          PN->addIncoming(Op, CopyBB);
+      }
+      assert(EdgeFromOrigBB && "Illegal exit from SEME.");
+    }
+  }
+}
+
+BasicBlock* llvm::copySEME(const SmallVectorImpl<BasicBlock *> &Blocks,
+                           const SmallPtrSetImpl<BasicBlock *> &Exits,
+                           ValueToValueMapTy &VMap,
+                           const Twine &NameSuffix,
+                           DominatorTree *DT, LoopInfo *LI) {
+  // Step1: Clone the basic blocks and populate VMap.
+  BasicBlock *DomEntry = DT->getNode(Blocks[0])->getIDom()->getBlock();
+  assert(DomEntry && "no dominator");
+
+  Function *F = DomEntry->getParent();
+  BasicBlock *OrigH = Blocks[0];
+  SmallVector<BasicBlock *, 4> NewBlocks;
+  for (BasicBlock *BB : Blocks) {
+    BasicBlock *NewBB = CloneBasicBlock(BB, VMap, NameSuffix, F);
+    // Move them physically from the end of the block list.
+    F->getBasicBlockList().splice(OrigH->getIterator(), F->getBasicBlockList(),
+                                  NewBB);
+    Loop *BBLoop = LI->getLoopFor(BB);
+    Loop *BBParentLoop = BBLoop->getParentLoop();
+    if (BBParentLoop)
+      BBParentLoop->addBasicBlockToLoop(NewBB, *LI);
+    VMap[BB] = NewBB;
+    NewBlocks.push_back(NewBB);
+  }
+
+  // Step2: Remaps the names in copied BBs.
+  remapInstructionsInBlocks(NewBlocks, VMap);
+
+  // Step3: Redirect the edges.
+  for (BasicBlock *BB : Blocks) {
+    BasicBlock *NewBB = cast_or_null<BasicBlock>(VMap[BB]);
+    BranchInst *BI = dyn_cast<BranchInst>(NewBB->getTerminator());
+    if (!BI)
+      continue;
+
+    for (unsigned I = 0, E = BI->getNumSuccessors(); I < E; ++I) {
+      BasicBlock *NewSucc = cast_or_null<BasicBlock>(VMap[BI->getSuccessor(I)]);
+      if (!NewSucc)
+        continue;
+      BI->setSuccessor(I, NewSucc);
+    }
+  }
+
+  // Step4: Update the DOM of coppied SEME. Except for the entry block its tree
+  // structure is the same as of original SEME so the dominators also follow the
+  // same structural property. If the imm-dom of orig BB is not in SEME that
+  // means it is the entry block, in that case the new idom of the new BB must
+  // be its single predecessor because we are dealing with an SEME region.
+  BasicBlock *EntryNewSEME = nullptr;
+  for (BasicBlock *BB : Blocks) {
+    BasicBlock *NewBB = cast_or_null<BasicBlock>(VMap[BB]);
+    assert(NewBB);
+
+    BasicBlock *Dom = DT->getNode(BB)->getIDom()->getBlock();
+    BasicBlock *NewDom = cast_or_null<BasicBlock>(VMap[Dom]);
+    if (!NewDom) { // Dom does not belong to SEME => entry block.
+      EntryNewSEME = NewBB;
+      NewDom = Dom;
+      assert (Dom == DomEntry);
+    }
+    DT->addNewBlock(NewBB, NewDom);
+    DT->changeImmediateDominator(NewBB, NewDom);
+  }
+
+  // Step5: Adjust PHI nodes.
+  adjustExitingPhis(VMap, Exits);
+  return EntryNewSEME;
+}