Fix dominator tree update in LoopVersioning

[sepavloff]

Summary

When LoopVersioning clones a loop, the original and cloned loops share the
same exit block. To make dominator tree in sync with CFG the pass sets the
immediate dominator of the exit block to memcheck block. It is however
incorrect if the versioned loop already shares the exit block with another
loop. With this change the dominator is changed only if the original loop
preheader dominates the exit block.

[anemet]

I believe that the change from today to require loop-simplify form for versioning (D27469) should fix this too. Can you please check?

[sepavloff]

Changes made in D27469 fix this problem too.

lib/Transforms/Utils/LoopVersioning.cpp

void LoopVersioning::versionLoop(
     const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
   Instruction *FirstCheckInst;
   Instruction *MemRuntimeCheck;
   Value *SCEVRuntimeCheck;
   Value *RuntimeCheck = nullptr;
 
   // Add the memcheck in the original preheader (this is empty initially).
   BasicBlock *RuntimeCheckBB = VersionedLoop->getLoopPreheader();
+  bool CheckDominatesExit = DT->dominates(RuntimeCheckBB,
+                                          VersionedLoop->getExitBlock());
   std::tie(FirstCheckInst, MemRuntimeCheck) =
       LAI.addRuntimeChecks(RuntimeCheckBB->getTerminator(), AliasChecks);
 
   const SCEVUnionPredicate &Pred = LAI.getPSE().getUnionPredicate();
   SCEVExpander Exp(*SE, RuntimeCheckBB->getModule()->getDataLayout(),
                    "scev.check");
   SCEVRuntimeCheck =
       Exp.expandCodeForPredicate(&Pred, RuntimeCheckBB->getTerminator());
void LoopVersioning::versionLoop(
   remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);
 
   // Insert the conditional branch based on the result of the memchecks.
   Instruction *OrigTerm = RuntimeCheckBB->getTerminator();
   BranchInst::Create(NonVersionedLoop->getLoopPreheader(),
                      VersionedLoop->getLoopPreheader(), RuntimeCheck, OrigTerm);
   OrigTerm->eraseFromParent();
 
-  // The loops merge in the original exit block.  This is now dominated by the
-  // memchecking block.
+  // The loops merge in the original exit block.  This should now be dominated
+  // by the memchecking block, but several loops may share the same exit block,
+  // so it may already be dominated by one of memcheck dominators.  Only if
+  // the exit block is dominated by memcheck block in original loop, update its
+  // idom.
+  if (CheckDominatesExit)
     DT->changeImmediateDominator(VersionedLoop->getExitBlock(), RuntimeCheckBB);
 
   // Adds the necessary PHI nodes for the versioned loops based on the
   // loop-defined values used outside of the loop.
   addPHINodes(DefsUsedOutside);
 }
 
 void LoopVersioning::addPHINodes(
     const SmallVectorImpl<Instruction *> &DefsUsedOutside) {

test/Transforms/LoopVersioning/noalias-version-twice.ll

-; RUN: opt -basicaa -loop-distribute -scoped-noalias -loop-versioning -S < %s | FileCheck %s
+; RUN: opt -basicaa -loop-distribute -scoped-noalias -loop-versioning -verify-dom-info -S < %s | FileCheck %s
 
 ; Test the metadata generated when versioning an already versioned loop.  Here
 ; we invoke loop distribution to perform the first round of versioning.  It
 ; adds memchecks for accesses that can alias across the distribution boundary.
 ; Then we further version the distributed loops to fully disambiguate accesses
 ; within each.
 ;
 ; So as an example, we add noalias between C and A during the versioning