[MemorySSA] Pass (for update) MSSAU when hoisting instructions.

[asbirlea]

Summary

Pass MSSAU to makeLoopInvariant in order to properly update MSSA.

[george.burgess.iv]

Thanks for this!

Just a general style nit, and LGTM

lib/Transforms/Scalar/LoopUnswitch.cpp

424

nit: generally unique_ptr<T>& is only used when you want to update what the unique_ptr itself is pointing to. if you just want to use *MSSAU from the function, please pass it as a MemorySSAUpdater & (or MemorySSAUpdater * if it's potentially null)

506

same nit

[asbirlea]

Thank you for the suggestion and review.

lib/Transforms/Scalar/LoopUnswitch.cpp

 /// the operator chain. If the chain is AND-only or OR-only, we can use 0 or ~0
 /// to simplify the chain.
 ///
 /// NOTE: In case a partial LIV and a mixed operator chain, we may be able to
 /// simplify the condition itself to a loop variant condition, but at the
 /// cost of creating an entirely new loop.
 static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed,
                                    OperatorChain &ParentChain,
-                                   DenseMap<Value *, Value *> &Cache) {
+                                   DenseMap<Value *, Value *> &Cache,
+                                   MemorySSAUpdater *MSSAU) {
   auto CacheIt = Cache.find(Cond);
   if (CacheIt != Cache.end())
     return CacheIt->second;
 
   // We started analyze new instruction, increment scanned instructions counter.
   ++TotalInsts;
 
   // We can never unswitch on vector conditions.
   if (Cond->getType()->isVectorTy())
     return nullptr;
 
   // Constants should be folded, not unswitched on!
   if (isa<Constant>(Cond)) return nullptr;
 
   // TODO: Handle: br (VARIANT|INVARIANT).
 
   // Hoist simple values out.
-  if (L->makeLoopInvariant(Cond, Changed)) {
+  if (L->makeLoopInvariant(Cond, Changed, nullptr, MSSAU)) {
     Cache[Cond] = Cond;
     return Cond;
   }
 
   // Walk up the operator chain to find partial invariant conditions.
   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond))
     if (BO->getOpcode() == Instruction::And ||
         BO->getOpcode() == Instruction::Or) {
if (BO->getOpcode() == Instruction::And ||
       // either backtrack to find partial LIV in other operand or return null.
       if (NewChain != OC_OpChainMixed) {
         // Update the current operator chain type before we search up the chain.
         ParentChain = NewChain;
         // If either the left or right side is invariant, we can unswitch on this,
         // which will cause the branch to go away in one loop and the condition to
         // simplify in the other one.
         if (Value *LHS = FindLIVLoopCondition(BO->getOperand(0), L, Changed,
-                                              ParentChain, Cache)) {
+                                              ParentChain, Cache, MSSAU)) {
           Cache[Cond] = LHS;
           return LHS;
         }
         // We did not manage to find a partial LIV in operand(0). Backtrack and try
         // operand(1).
         ParentChain = NewChain;
         if (Value *RHS = FindLIVLoopCondition(BO->getOperand(1), L, Changed,
-                                              ParentChain, Cache)) {
+                                              ParentChain, Cache, MSSAU)) {
           Cache[Cond] = RHS;
           return RHS;
         }
       }
     }
 
   Cache[Cond] = nullptr;
   return nullptr;
 }
 
 /// Cond is a condition that occurs in L. If it is invariant in the loop, or has
 /// an invariant piece, return the invariant along with the operator chain type.
 /// Otherwise, return null.
-static std::pair<Value *, OperatorChain> FindLIVLoopCondition(Value *Cond,
-                                                              Loop *L,
-                                                              bool &Changed) {
+static std::pair<Value *, OperatorChain>
+FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed,
+                     MemorySSAUpdater *MSSAU) {
   DenseMap<Value *, Value *> Cache;
   OperatorChain OpChain = OC_OpChainNone;
-  Value *FCond = FindLIVLoopCondition(Cond, L, Changed, OpChain, Cache);
+  Value *FCond = FindLIVLoopCondition(Cond, L, Changed, OpChain, Cache, MSSAU);
 
   // In case we do find a LIV, it can not be obtained by walking up a mixed
   // operator chain.
   assert((!FCond || OpChain != OC_OpChainMixed) &&
         "Do not expect a partial LIV with mixed operator chain");
   return {FCond, OpChain};
 }
 
for (auto &I : *BB) {
           return false;
       if (auto *II = dyn_cast<IntrinsicInst>(&I))
         if (II->getIntrinsicID() == Intrinsic::experimental_guard)
           Guards.push_back(II);
     }
   }
 
   for (IntrinsicInst *Guard : Guards) {
-    Value *LoopCond =
-        FindLIVLoopCondition(Guard->getOperand(0), currentLoop, Changed).first;
+    Value *LoopCond = FindLIVLoopCondition(Guard->getOperand(0), currentLoop,
+                                           Changed, MSSAU.get())
+                          .first;
     if (LoopCond &&
         UnswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context))) {
       // NB! Unswitching (if successful) could have erased some of the
       // instructions in Guards leaving dangling pointers there.  This is fine
       // because we're returning now, and won't look at Guards again.
       ++NumGuards;
       return true;
     }
if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
       if (isUnreachableDueToPreviousUnswitching(*I))
         continue;
 
       // If this isn't branching on an invariant condition, we can't unswitch
       // it.
       if (BI->isConditional()) {
         // See if this, or some part of it, is loop invariant.  If so, we can
         // unswitch on it if we desire.
-        Value *LoopCond = FindLIVLoopCondition(BI->getCondition(),
-                                               currentLoop, Changed).first;
+        Value *LoopCond = FindLIVLoopCondition(BI->getCondition(), currentLoop,
+                                               Changed, MSSAU.get())
+                              .first;
         if (LoopCond && !EqualityPropUnSafe(*LoopCond) &&
             UnswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context), TI)) {
           ++NumBranches;
           return true;
         }
       }
     } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
       Value *SC = SI->getCondition();
       Value *LoopCond;
       OperatorChain OpChain;
       std::tie(LoopCond, OpChain) =
-        FindLIVLoopCondition(SC, currentLoop, Changed);
+          FindLIVLoopCondition(SC, currentLoop, Changed, MSSAU.get());
 
       unsigned NumCases = SI->getNumCases();
       if (LoopCond && NumCases) {
         // Find a value to unswitch on:
         // FIXME: this should chose the most expensive case!
         // FIXME: scan for a case with a non-critical edge?
         Constant *UnswitchVal = nullptr;
         // Find a case value such that at least one case value is unswitched
if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
         }
       }
     }
 
     // Scan the instructions to check for unswitchable values.
     for (BasicBlock::iterator BBI = (*I)->begin(), E = (*I)->end();
          BBI != E; ++BBI)
       if (SelectInst *SI = dyn_cast<SelectInst>(BBI)) {
-        Value *LoopCond = FindLIVLoopCondition(SI->getCondition(),
-                                               currentLoop, Changed).first;
+        Value *LoopCond = FindLIVLoopCondition(SI->getCondition(), currentLoop,
+                                               Changed, MSSAU.get())
+                              .first;
         if (LoopCond && UnswitchIfProfitable(LoopCond,
                                              ConstantInt::getTrue(Context))) {
           ++NumSelects;
           return true;
         }
       }
   }
   return Changed;
bool LoopUnswitch::TryTrivialLoopUnswitch(bool &Changed) {
   Constant *CondVal = nullptr;
   BasicBlock *LoopExitBB = nullptr;
 
   if (BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) {
     // If this isn't branching on an invariant condition, we can't unswitch it.
     if (!BI->isConditional())
       return false;
 
-    Value *LoopCond = FindLIVLoopCondition(BI->getCondition(),
-                                           currentLoop, Changed).first;
+    Value *LoopCond = FindLIVLoopCondition(BI->getCondition(), currentLoop,
+                                           Changed, MSSAU.get())
+                          .first;
 
     // Unswitch only if the trivial condition itself is an LIV (not
     // partial LIV which could occur in and/or)
     if (!LoopCond || LoopCond != BI->getCondition())
       return false;
 
     // Check to see if a successor of the branch is guaranteed to
     // exit through a unique exit block without having any
if (EqualityPropUnSafe(*LoopCond))
       return false;
 
     UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, LoopExitBB,
                              CurrentTerm);
     ++NumBranches;
     return true;
   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurrentTerm)) {
     // If this isn't switching on an invariant condition, we can't unswitch it.
-    Value *LoopCond = FindLIVLoopCondition(SI->getCondition(),
-                                           currentLoop, Changed).first;
+    Value *LoopCond = FindLIVLoopCondition(SI->getCondition(), currentLoop,
+                                           Changed, MSSAU.get())
+                          .first;
 
     // Unswitch only if the trivial condition itself is an LIV (not
     // partial LIV which could occur in and/or)
     if (!LoopCond || LoopCond != SI->getCondition())
       return false;
 
     // Check to see if a successor of the switch is guaranteed to go to the
     // latch block or exit through a one exit block without having any
void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
   // We are going to make essential changes to CFG. This may invalidate cached
   // information for L or one of its parent loops in SCEV.
   if (auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>())
     SEWP->getSE().forgetTopmostLoop(L);
 
   LoopBlocks.clear();
   NewBlocks.clear();
 
+  if (MSSAU && VerifyMemorySSA)
+    MSSA->verifyMemorySSA();
+
   // First step, split the preheader and exit blocks, and add these blocks to
   // the LoopBlocks list.
   BasicBlock *NewPreheader =
       SplitEdge(loopPreheader, loopHeader, DT, LI, MSSAU.get());
   LoopBlocks.push_back(NewPreheader);
 
   // We want the loop to come after the preheader, but before the exit blocks.
   LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end());

test/Analysis/MemorySSA/loop-unswitch.ll

+; RUN: opt -S -loop-unswitch -disable-basicaa -enable-mssa-loop-dependency -verify-memoryssa < %s | FileCheck %s
+; REQUIRES: asserts
+
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK-LABEL:  @foo()
+; Function Attrs: readnone speculatable
+declare i32 @foo() #0
+
+define void @main() {
+entry:
+  br label %for.cond2682
+
+for.cond2682:                                     ; preds = %if.then2712, %entry
+  %mul2708 = call i32 @foo()
+  %tobool2709 = icmp ne i32 %mul2708, 0
+  br i1 %tobool2709, label %if.then2712, label %lor.lhs.false2710
+
+lor.lhs.false2710:                                ; preds = %for.cond2682
+  unreachable
+
+if.then2712:                                      ; preds = %for.cond2682
+  br label %for.cond2682
+}
+
+attributes #0 = { readnone speculatable }