[SCEVExpander] Have hoistIVInc preserve LCSSA

[sanjoy]

Summary

(Note: the problematic invocation of hoistIVInc that caused PR24804 came
from IndVarSimplify, not from SCEVExpander itself)

Fixes PR24804. Test case by David Majnemer.

[mzolotukhin]

Hi Sanjoy,

A couple of comments inline, otherwise the patch looks good to me.

Thanks,
Michael

lib/Analysis/ScalarEvolutionExpander.cpp

936–938

With this change we should become more conservative in some cases; did you see any effect on the testsuite? E.g. how many tests would crash if we replace with condition with an assert?

lib/IR/Instruction.cpp

65–70

This should probably go in a separate patch.

test/Transforms/IndVarSimplify/pr24804.ll

14–15

Maybe run instnamer on the test?

[sanjoy]

lib/Analysis/ScalarEvolutionExpander.cpp

936–938

Turning this into an assert does not fail any test in the current llvm test suite (i.e. the tests/ directory) except the newly added pr24804.ll. I haven't run this over any other IR corpus.

Having said that, I'm not too worried -- even in the "worst case", this will replace a correctness issue with a performance issue.

[sanjoy]

• address review

[mzolotukhin]

Having said that, I'm not too worried -- even in the "worst case", this will replace a correctness issue with a performance issue.

Yes, I agree. I actually meant LNT testsuite or any other real-world test-suite - I was just curious if it had any effect at all there.

include/llvm/Analysis/LoopInfo.h

 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
 #include "llvm/Pass.h"
 #include <algorithm>
 
 namespace llvm {
 
 // FIXME: Replace this brittle forward declaration with the include of the new
 // PassManager.h when doing so doesn't break the PassManagerBuilder.
 template <typename IRUnitT> class AnalysisManager;
bool replacementPreservesLCSSAForm(Instruction *From, Value *To) {
     // anything.
     Loop *ToLoop = getLoopFor(I->getParent());
     if (!ToLoop) return true;
     // If the replacing instruction is defined in the same loop as the original
     // instruction, or in a loop that contains it as an inner loop, then using
     // it as a replacement will not break LCSSA form.
     return ToLoop->contains(getLoopFor(From->getParent()));
   }
+
+  /// \brief Checks if moving a specific instruction can break LCSSA in any
+  /// loop.
+  ///
+  /// Return true if moving \p Inst to before \p NewLoc will break LCSSA,
+  /// assuming that the function containing \p Inst and \p NewLoc is currently
+  /// in LCSSA form.
+  bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc) {
+    assert(Inst->getFunction() == NewLoc->getFunction() &&
+           "Can't reason about IPO!");
+
+    auto *OldBB = Inst->getParent();
+    auto *NewBB = NewLoc->getParent();
+
+    // Movement within the same loop does not break LCSSA (the equality check is
+    // to avoid doing a hashtable lookup in case of intra-block movement).
+    if (OldBB == NewBB)
+      return true;
+
+    auto *OldLoop = getLoopFor(OldBB);
+    auto *NewLoop = getLoopFor(NewBB);
+
+    if (OldLoop == NewLoop)
+      return true;
+
+    // Check if Outer contains Inner; with the null loop counting as the
+    // "outermost" loop.
+    auto Contains = [](const Loop *Outer, const Loop *Inner) {
+      return !Outer || Outer->contains(Inner);
+    };
+
+    // To check that the movement of Inst to before NewLoc does not break LCSSA,
+    // we need to check two sets of uses for possible LCSSA violations at
+    // NewLoc: the users of NewInst, and the operands of NewInst.
+
+    // If we know we're hoisting Inst out of an inner loop to an outer loop,
+    // then the uses *of* Inst don't need to be checked.
+
+    if (!Contains(NewLoop, OldLoop)) {
+      for (Use &U : Inst->uses()) {
+        auto *UI = cast<Instruction>(U.getUser());
+        auto *UBB = isa<PHINode>(UI) ? cast<PHINode>(UI)->getIncomingBlock(U)
+                                     : UI->getParent();
+        if (UBB != NewBB && getLoopFor(UBB) != NewLoop)
+          return false;
+      }
+    }
+
+    // If we know we're sinking Inst from an outer loop into an inner loop, then
+    // the *operands* of Inst don't need to be checked.
+
+    if (!Contains(OldLoop, NewLoop)) {
+      // See below on why we can't handle phi nodes here.
+      if (isa<PHINode>(Inst))
+        return false;
+
+      for (Use &U : Inst->operands()) {
+        auto *DefI = dyn_cast<Instruction>(U.get());
+        if (!DefI)
+          return false;
+
+        // This would need adjustment if we allow Inst to be a phi node -- the
+        // new use block won't simply be NewBB.
+
+        auto *DefBlock = DefI->getParent();
+        if (DefBlock != NewBB && getLoopFor(DefBlock) != NewLoop)
+          return false;
+      }
+    }
+
+    return true;
+  }
 };
 
 // Allow clients to walk the list of nested loops...
 template <> struct GraphTraits<const Loop*> {
   typedef const Loop NodeType;
   typedef LoopInfo::iterator ChildIteratorType;
 
   static NodeType *getEntryNode(const Loop *L) { return L; }

include/llvm/IR/Instruction.h

public:
   /// \brief Return the module owning the function this instruction belongs to
   /// or nullptr it the function does not have a module.
   ///
   /// Note: this is undefined behavior if the instruction does not have a
   /// parent, or the parent basic block does not have a parent function.
   const Module *getModule() const;
   Module *getModule();
 
+  /// \brief Return the function this instruction belongs to.
+  ///
+  /// Note: it is undefined behavior to call this on an instruction not
+  /// currently inserted into a function.
+  const Function *getFunction() const;
+  Function *getFunction();
+
   /// removeFromParent - This method unlinks 'this' from the containing basic
   /// block, but does not delete it.
   ///
   void removeFromParent();
 
   /// eraseFromParent - This method unlinks 'this' from the containing basic
   /// block and deletes it.
   ///

lib/Analysis/ScalarEvolutionExpander.cpp

if (SE.DT.dominates(IncV, InsertPos))
       return true;
 
   // InsertPos must itself dominate IncV so that IncV's new position satisfies
   // its existing users.
   if (isa<PHINode>(InsertPos) ||
       !SE.DT.dominates(InsertPos->getParent(), IncV->getParent()))
     return false;
 
+  if (!SE.LI.movementPreservesLCSSAForm(IncV, InsertPos))
+    return false;
+
   // Check that the chain of IV operands leading back to Phi can be hoisted.
   SmallVector<Instruction*, 4> IVIncs;
   for(;;) {
     Instruction *Oper = getIVIncOperand(IncV, InsertPos, /*allowScale*/true);
     if (!Oper)
       return false;
     // IncV is safe to hoist.
     IVIncs.push_back(IncV);

lib/IR/Instruction.cpp

 const Module *Instruction::getModule() const {
   return getParent()->getModule();
 }
 
 Module *Instruction::getModule() {
   return getParent()->getModule();
 }
 
+Function *Instruction::getFunction() { return getParent()->getParent(); }
+
+const Function *Instruction::getFunction() const {
+  return getParent()->getParent();
+}
 
 void Instruction::removeFromParent() {
   getParent()->getInstList().remove(getIterator());
 }
 
 iplist<Instruction>::iterator Instruction::eraseFromParent() {
   return getParent()->getInstList().erase(getIterator());
 }
 

test/Transforms/IndVarSimplify/pr24804.ll

+; RUN: opt -indvars -loop-idiom -loop-deletion -S < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Checking for a crash
+
+define void @f(i32* %a) {
+; CHECK-LABEL: @f(
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %for.cond, %entry
+  %0 = phi i32 [ 0, %entry ], [ %add, %for.inc ], [ %0, %for.cond ]
+  %add = add nsw i32 %0, 1
+  %idxprom = sext i32 %add to i64
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom
+  br i1 undef, label %for.cond, label %for.inc
+
+for.inc:                                          ; preds = %for.cond
+  br i1 undef, label %for.cond, label %for.end
+
+for.end:                                          ; preds = %for.inc
+  ret void
+}