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

class NewGVN {
   const DataLayout &DL;
   std::unique_ptr<PredicateInfo> PredInfo;
   BumpPtrAllocator ExpressionAllocator;
   ArrayRecycler<Value *> ArgRecycler;
 
   // 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;
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 *);

 // 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 (LookupResult != MemoryAccessToClass.end()) {
     }
   }
 
   return Changed;
 }
 
 // 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 can't ignore the undef when going over a backedge
+      // unless the value being propagated *is* undef itself, or the original
+      // phi operands were all constants.  This is because if they are all
+      // undef, they will not become less undef (and if they did, we will stop
+      // them here).  Note that NumOps does not include the undef itself.
+      if (!AllConstant && HasBackedge && NumOps > 0 && !isa<UndefValue>(AllSameValue))
+        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

 ; CHECK-NEXT:    [[TMP:%.*]] = getelementptr inbounds i32, i32* [[DATA:%.*]], i64 3
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[TMP]], align 4
 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i32, i32* [[DATA]], i64 4
 ; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* [[TMP2]], align 4
 ; CHECK-NEXT:    br label [[BB4:%.*]]
 ; CHECK:       bb4:
 ; CHECK-NEXT:    [[M_0:%.*]] = phi i32 [ [[TMP3]], [[BB:%.*]] ], [ [[TMP15:%.*]], [[BB19:%.*]] ]
 ; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[BB]] ], [ [[TMP20:%.*]], [[BB19]] ]
+; CHECK-NEXT:    [[P_0:%.*]] = phi i32 [ undef, [[BB]] ], [ 0, [[BB19]] ]
 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp slt i32 [[I_0]], [[TMP1]]
 ; CHECK-NEXT:    br i1 [[TMP5]], label [[BB6:%.*]], label [[BB21:%.*]]
 ; CHECK:       bb6:
 ; CHECK-NEXT:    [[TMP7:%.*]] = getelementptr inbounds i32, i32* [[DATA]], i64 2
 ; CHECK-NEXT:    [[TMP8:%.*]] = load i32, i32* [[TMP7]], align 4
 ; CHECK-NEXT:    [[TMP9:%.*]] = sext i32 [[TMP8]] to i64
 ; CHECK-NEXT:    [[TMP10:%.*]] = getelementptr inbounds i32, i32* [[DATA]], i64 [[TMP9]]
 ; CHECK-NEXT:    store i32 2, i32* [[TMP10]], align 4
 ; CHECK-NEXT:    store i32 0, i32* [[DATA]], align 4
 ; CHECK-NEXT:    [[TMP13:%.*]] = getelementptr inbounds i32, i32* [[DATA]], i64 1
 ; CHECK-NEXT:    [[TMP14:%.*]] = load i32, i32* [[TMP13]], align 4
 ; CHECK-NEXT:    [[TMP15]] = add nsw i32 [[M_0]], [[TMP14]]
 ; CHECK-NEXT:    br label [[BB19]]
 ; CHECK:       bb19:
 ; CHECK-NEXT:    [[TMP20]] = add nsw i32 [[I_0]], 1
 ; CHECK-NEXT:    br label [[BB4]]
 ; CHECK:       bb21:
-; CHECK-NEXT:    ret i32 0
+; CHECK-NEXT:    ret i32 [[P_0]]
 ;
 bb:
   %tmp = getelementptr inbounds i32, i32* %data, i64 3
   %tmp1 = load i32, i32* %tmp, align 4
   %tmp2 = getelementptr inbounds i32, i32* %data, i64 4
   %tmp3 = load i32, i32* %tmp2, align 4
   br label %bb4
 
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/pr31682.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -basicaa -newgvn -S | FileCheck %s
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 %struct.foo = type { i32, i32, [2 x [4 x [6 x [6 x i16]]]] }
 
 @global = external global %struct.foo*
 
 define void @bar() {
 ; CHECK-LABEL: @bar(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[TMP:%.*]] = load %struct.foo*, %struct.foo** @global
 ; CHECK-NEXT:    br label [[BB2:%.*]]
 ; CHECK:       bb2:
+; CHECK-NEXT:    [[TMP3:%.*]] = phi %struct.foo* [ undef, [[BB:%.*]] ], [ [[TMP]], [[BB2]] ]
+; CHECK-NEXT:    [[TMP4:%.*]] = getelementptr [[STRUCT_FOO:%.*]], %struct.foo* [[TMP3]], i64 0, i32 1
 ; CHECK-NEXT:    br i1 undef, label [[BB2]], label [[BB7:%.*]]
 ; CHECK:       bb7:
+; CHECK-NEXT:    [[TMP9:%.*]] = getelementptr [[STRUCT_FOO]], %struct.foo* [[TMP]], i64 0, i32 1
 ; CHECK-NEXT:    br label [[BB10:%.*]]
 ; CHECK:       bb10:
 ; CHECK-NEXT:    br label [[BB10]]
 ;
 bb:
   %tmp = load %struct.foo*, %struct.foo** @global
   %tmp1 = getelementptr %struct.foo, %struct.foo* %tmp
   br label %bb2

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
+}
+