NewGVN: Don't propagate over phi backedges where undef causes us to have >1 value.

[• dberlin]

Summary

Fixes PR 32607 by only ignoring undef when we can prove the phi is cycle-free

[• dberlin]

Unfortunately, as you can see, we lose optimization in a few cases where the phis *are* cycle-free.
I could just bite the bullet and build scc's to determine cycle-freeness.
I'll do some performance testing.

[• dberlin]

• Add SCC finding to discover cycle-free phis

(I'm performance testing a bunch of versions of this patch)

[• dberlin]

Fix small issue in SCC impl.

[• dberlin]

So far, i can't find any measurable time spent in the SCC version, so i think we will go with that.

[davide]

LGTM. I'd split the SCC finder and move maybe to a separate file (as we may want to use it somewhere else), but we can move it later, so.

[• dberlin]

At some point i'm going to try to make the graph-traits'ish version work.
The main issue for us is that we have to iterate through all parts, because it's really stateless from our perspective.

IE every time you call scc_begin, it is starting the SCC finding from scratch.

That turned out to be pretty expensive for us vs doing this.

lib/Transforms/Scalar/NewGVN.cpp

 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/CFGPrinter.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryLocation.h"
+#include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Type.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/DebugCounter.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/GVNExpression.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
-#include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Transforms/Utils/PredicateInfo.h"
 #include "llvm/Transforms/Utils/VNCoercion.h"
 #include <numeric>
 #include <unordered_map>
 #include <utility>
 #include <vector>
 using namespace llvm;
 using namespace PatternMatch;

 CallExpression::~CallExpression() = default;
 LoadExpression::~LoadExpression() = default;
 StoreExpression::~StoreExpression() = default;
 AggregateValueExpression::~AggregateValueExpression() = default;
 PHIExpression::~PHIExpression() = default;
 }
 }
 
+// Tarjan's algorithm with Nuutila's improvements
+// SCCIterator is actually fairly complex for the simple thing we want.
+// It also wants to hand us SCC's that are unrelated to the phi node we ask
+// about, and have us process them there or risk redoing work.
+// Graph traits over a filter iterator also doesn't work that well here.
+struct TarjanSCC {
+
+  TarjanSCC() : Components(1) {}
+
+  void Start(const Instruction *Start) {
+    if (Root.lookup(Start) == 0)
+      FindSCC(Start);
+  }
+
+  const SmallPtrSetImpl<const Value *> &getComponentFor(const Value *V) const {
+    unsigned ComponentID = ValueToComponent.lookup(V);
+
+    assert(ComponentID > 0 &&
+           "Asking for a component for a value we never processed");
+    return Components[ComponentID];
+  }
+
+private:
+  void FindSCC(const Instruction *I) {
+    Root[I] = ++DFSNum;
+    // Store the DFS Number we had before it possibly gets incremented.
+    unsigned int OurDFS = DFSNum;
+    //    InComponent.erase(I);
+    for (auto &Op : I->operands()) {
+      if (auto *InstOp = dyn_cast<Instruction>(Op)) {
+        if (Root.lookup(Op) == 0)
+          FindSCC(InstOp);
+        if (!InComponent.count(Op))
+          Root[I] = std::min(Root.lookup(I), Root.lookup(Op));
+      }
+    }
+    // See if we really were the root, by seeing if we still have our DFSNumber,
+    // or something lower
+    if (Root.lookup(I) == OurDFS) {
+      unsigned ComponentID = Components.size();
+      Components.resize(Components.size() + 1);
+      auto &Component = Components.back();
+      Component.insert(I);
+      DEBUG(dbgs() << "Component root is " << *I << "\n");
+      InComponent.insert(I);
+      ValueToComponent[I] = ComponentID;
+      while (!Stack.empty() && Root.lookup(Stack.back()) >= OurDFS) {
+        auto *Member = Stack.back();
+        DEBUG(dbgs() << "Component member is " << *Member << "\n");
+        Component.insert(Member);
+        InComponent.insert(Member);
+        ValueToComponent[Member] = ComponentID;
+        Stack.pop_back();
+      }
+    } else {
+      // Part of a component, push to stack
+      Stack.push_back(I);
+    }
+  }
+  unsigned int DFSNum = 1;
+  SmallPtrSet<const Value *, 8> InComponent;
+  DenseMap<const Value *, unsigned int> Root;
+  SmallVector<const Value *, 8> Stack;
+  // Store the components as vector of ptr sets, because we need the topo order
+  // of SCC's, but not individual member order
+  SmallVector<SmallPtrSet<const Value *, 8>, 8> Components;
+  DenseMap<const Value *, unsigned> ValueToComponent;
+};
 // Congruence classes represent the set of expressions/instructions
 // that are all the same *during some scope in the function*.
 // That is, because of the way we perform equality propagation, and
 // because of memory value numbering, it is not correct to assume
 // you can willy-nilly replace any member with any other at any
 // point in the function.
 //
 // For any Value in the Member set, it is valid to replace any dominated member
class NewGVN {
   const TargetLibraryInfo *TLI;
   AliasAnalysis *AA;
   MemorySSA *MSSA;
   MemorySSAWalker *MSSAWalker;
   const DataLayout &DL;
   std::unique_ptr<PredicateInfo> PredInfo;
   BumpPtrAllocator ExpressionAllocator;
   ArrayRecycler<Value *> ArgRecycler;
+  TarjanSCC SCCFinder;
 
   // Number of function arguments, used by ranking
   unsigned int NumFuncArgs;
 
+  // RPOOrdering of basic blocks
+  DenseMap<const DomTreeNode *, unsigned> RPOOrdering;
+
   // Congruence class info.
 
   // This class is called INITIAL in the paper. It is the class everything
   // startsout in, and represents any value. Being an optimistic analysis,
   // anything in the TOP class has the value TOP, which is indeterminate and
   // equivalent to everything.
   CongruenceClass *TOPClass;
   std::vector<CongruenceClass *> CongruenceClasses;
class NewGVN {
   // create expressions for them, we need to simulate leader change not just
   // when they change class, but when they change state.  Note: We can do the
   // same thing for phis, and avoid having phi expressions if we wanted, We
   // should eventually unify in one direction or the other, so this is a little
   // bit of an experiment in which turns out easier to maintain.
   enum MemoryPhiState { MPS_Invalid, MPS_TOP, MPS_Equivalent, MPS_Unique };
   DenseMap<const MemoryPhi *, MemoryPhiState> MemoryPhiState;
 
+  enum PhiCycleState { PCS_Unknown, PCS_CycleFree, PCS_Cycle };
+  DenseMap<const PHINode *, PhiCycleState> PhiCycleState;
   // Expression to class mapping.
   using ExpressionClassMap = DenseMap<const Expression *, CongruenceClass *>;
   ExpressionClassMap ExpressionToClass;
 
   // Which values have changed as a result of leader changes.
   SmallPtrSet<Value *, 8> LeaderChanges;
 
   // Reachability info.
NewGVN(Function &F, DominatorTree *DT, AssumptionCache *AC,
       : F(F), DT(DT), AC(AC), TLI(TLI), AA(AA), MSSA(MSSA), DL(DL),
         PredInfo(make_unique<PredicateInfo>(F, *DT, *AC)) {}
   bool runGVN();
 
 private:
   // Expression handling.
   const Expression *createExpression(Instruction *);
   const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *);
-  PHIExpression *createPHIExpression(Instruction *);
+  PHIExpression *createPHIExpression(Instruction *, bool &HasBackedge,
+                                     bool &AllConstant);
   const VariableExpression *createVariableExpression(Value *);
   const ConstantExpression *createConstantExpression(Constant *);
   const Expression *createVariableOrConstant(Value *V);
   const UnknownExpression *createUnknownExpression(Instruction *);
   const StoreExpression *createStoreExpression(StoreInst *,
                                                const MemoryAccess *);
   LoadExpression *createLoadExpression(Type *, Value *, LoadInst *,
                                        const MemoryAccess *);
private:
   // auto-convert to Value's but not to MemoryAccess's.
   unsigned MemoryToDFSNum(const Value *MA) const {
     assert(isa<MemoryAccess>(MA) &&
            "This should not be used with instructions");
     return isa<MemoryUseOrDef>(MA)
                ? InstrToDFSNum(cast<MemoryUseOrDef>(MA)->getMemoryInst())
                : InstrDFS.lookup(MA);
   }
-
+  bool isCycleFree(const PHINode *PN);
   template <class T, class Range> T *getMinDFSOfRange(const Range &) const;
   // Debug counter info.  When verifying, we have to reset the value numbering
   // debug counter to the same state it started in to get the same results.
   std::pair<int, int> StartingVNCounter;
 };
 } // end anonymous namespace
 
 template <typename T>

 // const versions.
 void NewGVN::deleteExpression(const Expression *E) {
   assert(isa<BasicExpression>(E));
   auto *BE = cast<BasicExpression>(E);
   const_cast<BasicExpression *>(BE)->deallocateOperands(ArgRecycler);
   ExpressionAllocator.Deallocate(E);
 }
 
-PHIExpression *NewGVN::createPHIExpression(Instruction *I) {
+PHIExpression *NewGVN::createPHIExpression(Instruction *I, bool &HasBackedge,
+                                           bool &AllConstant) {
   BasicBlock *PHIBlock = I->getParent();
   auto *PN = cast<PHINode>(I);
   auto *E =
       new (ExpressionAllocator) PHIExpression(PN->getNumOperands(), PHIBlock);
 
   E->allocateOperands(ArgRecycler, ExpressionAllocator);
   E->setType(I->getType());
   E->setOpcode(I->getOpcode());
 
+  unsigned PHIRPO = RPOOrdering.lookup(DT->getNode(PHIBlock));
+
   // Filter out unreachable phi operands.
   auto Filtered = make_filter_range(PN->operands(), [&](const Use &U) {
     return ReachableEdges.count({PN->getIncomingBlock(U), PHIBlock});
   });
 
   std::transform(Filtered.begin(), Filtered.end(), op_inserter(E),
                  [&](const Use &U) -> Value * {
+                   auto *BB = PN->getIncomingBlock(U);
+                   auto *DTN = DT->getNode(BB);
+                   if (RPOOrdering.lookup(DTN) >= PHIRPO)
+                     HasBackedge = true;
+                   AllConstant &= isa<UndefValue>(U) || isa<Constant>(U);
+
                    // Don't try to transform self-defined phis.
                    if (U == PN)
                      return PN;
                    return lookupOperandLeader(U);
                  });
   return E;
 }
 
if (OldClass != NewClass) {
       // It wasn't equivalent before, and now it is.
       LookupResult->second = NewClass;
       Changed = true;
     }
   }
 
   return Changed;
 }
+bool NewGVN::isCycleFree(const PHINode *PN) {
+  auto PCS = PhiCycleState.lookup(PN);
+  if (PCS == PCS_Unknown) {
+    SCCFinder.Start(PN);
+    auto &SCC = SCCFinder.getComponentFor(PN);
+    // It's cycle free if it's size 1 or or the SCC is *only* phi nodes.
+    if (SCC.size() == 1)
+      PhiCycleState.insert({PN, PCS_CycleFree});
+    else {
+      bool AllPhis =
+          llvm::all_of(SCC, [](const Value *V) { return isa<PHINode>(V); });
+      PCS = AllPhis ? PCS_CycleFree : PCS_Cycle;
+      for (auto *Member : SCC)
+        if (auto *MemberPhi = dyn_cast<PHINode>(Member))
+          PhiCycleState.insert({MemberPhi, PCS});
+    }
+  }
+  if (PCS == PCS_Cycle)
+    return false;
+  return true;
+}
 
 // Evaluate PHI nodes symbolically, and create an expression result.
 const Expression *NewGVN::performSymbolicPHIEvaluation(Instruction *I) {
-  auto *E = cast<PHIExpression>(createPHIExpression(I));
+  // True if one of the incoming phi edges is a backedge.
+  bool HasBackedge = false;
+  // All constant tracks the state of whether all the *original* phi operands
+  // were constant.
+  // This is really shorthand for "this phi cannot cycle due to forward
+  // propagation", as any
+  // change in value of the phi is guaranteed not to later change the value of
+  // the phi.
+  // IE it can't be v = phi(undef, v+1)
+  bool AllConstant = true;
+  auto *E =
+      cast<PHIExpression>(createPHIExpression(I, HasBackedge, AllConstant));
   // We match the semantics of SimplifyPhiNode from InstructionSimplify here.
 
   // See if all arguaments are the same.
   // We track if any were undef because they need special handling.
   bool HasUndef = false;
   auto Filtered = make_filter_range(E->operands(), [&](const Value *Arg) {
     if (Arg == I)
       return false;
     if (isa<UndefValue>(Arg)) {
       HasUndef = true;
       return false;
     }
     return true;
   });
   // If we are left with no operands, it's undef
   if (Filtered.begin() == Filtered.end()) {
     DEBUG(dbgs() << "Simplified PHI node " << *I << " to undef"
                  << "\n");
     deleteExpression(E);
     return createConstantExpression(UndefValue::get(I->getType()));
   }
+  unsigned NumOps = 0;
   Value *AllSameValue = *(Filtered.begin());
   ++Filtered.begin();
   // Can't use std::equal here, sadly, because filter.begin moves.
-  if (llvm::all_of(Filtered, [AllSameValue](const Value *V) {
+  if (llvm::all_of(Filtered, [AllSameValue, &NumOps](const Value *V) {
+        ++NumOps;
         return V == AllSameValue;
       })) {
     // In LLVM's non-standard representation of phi nodes, it's possible to have
     // phi nodes with cycles (IE dependent on other phis that are .... dependent
     // on the original phi node), especially in weird CFG's where some arguments
     // are unreachable, or uninitialized along certain paths.  This can cause
     // infinite loops during evaluation. We work around this by not trying to
     // really evaluate them independently, but instead using a variable
     // expression to say if one is equivalent to the other.
     // We also special case undef, so that if we have an undef, we can't use the
     // common value unless it dominates the phi block.
     if (HasUndef) {
+      // If we have undef and at least one other value, this is really a
+      // multivalued phi.
+
+      // We need to know if it's cycle free in order to evaluate whether we can
+      // ignore the undef.
+      if (!AllConstant && HasBackedge && NumOps > 0 &&
+          !isa<UndefValue>(AllSameValue) && !isCycleFree(cast<PHINode>(I)))
+        return E;
+
       // Only have to check for instructions
       if (auto *AllSameInst = dyn_cast<Instruction>(AllSameValue))
         if (!someEquivalentDominates(AllSameInst, I))
           return E;
     }
 
     NumGVNPhisAllSame++;
     DEBUG(dbgs() << "Simplified PHI node " << *I << " to " << *AllSameValue
bool NewGVN::runGVN() {
   // Note: We want ideal RPO traversal of the blocks, which is not quite the
   // same as dominator tree order, particularly with regard whether backedges
   // get visited first or second, given a block with multiple successors.
   // If we visit in the wrong order, we will end up performing N times as many
   // iterations.
   // The dominator tree does guarantee that, for a given dom tree node, it's
   // parent must occur before it in the RPO ordering. Thus, we only need to sort
   // the siblings.
-  DenseMap<const DomTreeNode *, unsigned> RPOOrdering;
   ReversePostOrderTraversal<Function *> RPOT(&F);
   unsigned Counter = 0;
   for (auto &B : RPOT) {
     auto *Node = DT->getNode(B);
     assert(Node && "RPO and Dominator tree should have same reachability");
     RPOOrdering[Node] = ++Counter;
   }
   // Sort dominator tree children arrays into RPO.
   for (auto &B : RPOT) {
     auto *Node = DT->getNode(B);
     if (Node->getChildren().size() > 1)
       std::sort(Node->begin(), Node->end(),
-                [&RPOOrdering](const DomTreeNode *A, const DomTreeNode *B) {
+                [&](const DomTreeNode *A, const DomTreeNode *B) {
                   return RPOOrdering[A] < RPOOrdering[B];
                 });
   }
 
   // Now a standard depth first ordering of the domtree is equivalent to RPO.
   auto DFI = df_begin(DT->getRootNode());
   for (auto DFE = df_end(DT->getRootNode()); DFI != DFE; ++DFI) {
     BasicBlock *B = DFI->getBlock();

test/Transforms/NewGVN/basic-cyclic-opt.ll

bb6:                                              ; preds = %bb4
   %tmp18 = load i32, i32* %tmp17, align 4
   br label %bb19
 
 bb19:                                             ; preds = %bb6
   %tmp20 = add nsw i32 %i.0, 1
   br label %bb4
 
 bb21:                                             ; preds = %bb4
+;; We should be able to prove p.0 is 0, but because we do not try to determine
+;; whether the phi p.0 is cycle-free (IE not dependent on itself), it takes
+;; two passes of newgvn, one to replace the phi with phi(undef, 0), one to
+;; simplify it to 0.
   ret i32 %p.0
 }
 
 
 ; Function Attrs: nounwind ssp uwtable
 ;; Same as test 2, with a conditional store of m-n, so it has to also discover
 ;; that data ends up with the same value no matter what branch is taken.
 define i32 @vnum_test3(i32* %data) #0 {

test/Transforms/NewGVN/pr32607.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -newgvn %s -S -o - | FileCheck %s
+define hidden void @foo() {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  top:
+; CHECK-NEXT:    br label [[IF:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi double [ [[TMP1:%.*]], [[IF]] ], [ undef, [[TOP:%.*]] ]
+; CHECK-NEXT:    [[TMP1]] = fadd double [[TMP0]], undef
+; CHECK-NEXT:    br i1 false, label [[L50:%.*]], label [[IF]]
+; CHECK:       L50:
+; CHECK-NEXT:    store i8 undef, i8* null
+; CHECK-NEXT:    ret void
+;
+top:
+  %.promoted = load double, double* undef, align 8
+  br label %if
+
+;; This is really a multi-valued phi, because the phi is defined by an expression of the phi.
+;; This means that we can't propagate the value over the backedge, because we'll just cycle
+;; through every value.
+
+if:                                               ; preds = %if, %top
+  %0 = phi double [ %1, %if ], [ %.promoted, %top ]
+  %1 = fadd double %0, undef
+  br i1 false, label %L50, label %if
+
+L50:                                              ; preds = %if
+  %.lcssa = phi double [ %1, %if ]
+  store double %.lcssa, double* undef, align 8
+  ret void
+}
+