[GVN] do not repeat PRE on failure to split critical edge

[nickdesaulniers]

Summary

Fixes an infinite loop encountered in GVN.

GVN will delay PRE if it encounters critical edges, attempt to split
them later via calls to SplitCriticalEdge(), then restart.

The caller of GVN::splitCriticalEdges() assumed a return value of true
meant that critical edges were split, that the IR had changed, and that
PRE should be re-attempted, upon which we loop infinitely.

This was exposed after D88438, by compiling the Linux kernel for s390,
but the test case is reproducible on x86.

Fixes: https://github.com/ClangBuiltLinux/linux/issues/1261

[nickdesaulniers]

• fix comment in test

[nickdesaulniers]

• drop test metadata and fn attrs, unnecessary.

[fhahn]

llvm/lib/Transforms/Scalar/GVN.cpp

2693–2695

do we need !! here?

2698

This code seems redundant, right, because it is already done by splitCriticalEdges?

llvm/test/Transforms/GVN/critical-edge-split-failure.ll

14

is this function needed?

[nickdesaulniers]

• remove dead function from test

[nickdesaulniers]

llvm/lib/Transforms/Scalar/GVN.cpp

2693–2695

unless you'd prefer a comparison != nullptr? Otherwise:

../lib/Transforms/Scalar/GVN.cpp:2695:13: error: invalid operands to binary expression ('bool' and 'llvm::BasicBlock *')
    Changed |= SplitCriticalEdge(Edge.first, Edge.second,
    ~~~~~~~ ^  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

2698

Different code paths; the method GVN::splitCriticalEdges that accepts arguments is called from different places at different points during GVN.

That method is used to splitting individual edges eagerly, then invalidating cached predecessors.

This method is for splitting a list of edges that were deferred, then invalidating cached predecessors.

llvm/test/Transforms/GVN/critical-edge-split-failure.ll

3

This is yet another case where NPM test passes before/after a patch that would be red with LPM. cc @aeubanks

I don't know if this test should be under

llvm/test/Transforms/GVN/PRE/
rather than
llvm/test/Transforms/GVN/
?

14

This is what was produced by running both llvm-reduce and bugpoint; I wonder if they don't remove functions referred to by block addresses? (Cycle counter/cycle breaker problem). Removed.

[aeubanks]

llvm/test/Transforms/GVN/critical-edge-split-failure.ll

3

This one is much more surprising, I can't think of anything off the top of my head that would cause the output of running GVN to change between the two pass managers.

[nickdesaulniers]

@nathanchance verified this patch fixes the regression and doesn't appear to regress any of our other builds in https://github.com/ClangBuiltLinux/linux/issues/1261#issuecomment-763904779.

[nickdesaulniers]

llvm/lib/Transforms/Scalar/GVN.cpp

2698

The other method probably shouldn't be plural. s/splitCriticalEdges/splitCriticalEdge/

[fhahn]

llvm/lib/Transforms/Scalar/GVN.cpp

2693–2695

oh right, != nullptr seems clearer to me.

2698

ah right, this doesn't actually call GVN::splitCriticalEdges. Nevermind then.

llvm/test/Transforms/GVN/critical-edge-split-failure.ll

3

missing aa-pipeline option?

[aeubanks]

llvm/test/Transforms/GVN/critical-edge-split-failure.ll

3

Haha I just sent out https://reviews.llvm.org/D95117 to use the "default" AA pipeline by default and still forgot about it here. Seems like the likely culprit.

[nickdesaulniers]

• replace double negation with explicit not nullptr comparison

[nickdesaulniers]

llvm/test/Transforms/GVN/critical-edge-split-failure.ll

3

Adding -aa-pipeline=default (or -aa-pipeline=) doesn't seem to cause the NPM RUN line to fail (before adding this patch). Am I holding it wrong, or is there still more to this difference?

llvm/lib/Transforms/Scalar/GVN.cpp

 /// Split the critical edge connecting the given two blocks, and return
 /// the block inserted to the critical edge.
 BasicBlock *GVN::splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ) {
   // GVN does not require loop-simplify, do not try to preserve it if it is not
   // possible.
   BasicBlock *BB = SplitCriticalEdge(
       Pred, Succ,
       CriticalEdgeSplittingOptions(DT, LI, MSSAU).unsetPreserveLoopSimplify());
+  if (BB) {
     if (MD)
       MD->invalidateCachedPredecessors();
     InvalidBlockRPONumbers = true;
+  }
   return BB;
 }
 
 /// Split critical edges found during the previous
 /// iteration that may enable further optimization.
 bool GVN::splitCriticalEdges() {
   if (toSplit.empty())
     return false;
+
+  bool Changed = false;
   do {
     std::pair<Instruction *, unsigned> Edge = toSplit.pop_back_val();
-    SplitCriticalEdge(Edge.first, Edge.second,
-                      CriticalEdgeSplittingOptions(DT, LI, MSSAU));
+    Changed |= SplitCriticalEdge(Edge.first, Edge.second,
+                                 CriticalEdgeSplittingOptions(DT, LI, MSSAU)) !=
+               nullptr;
   } while (!toSplit.empty());
-  if (MD) MD->invalidateCachedPredecessors();
+  if (Changed) {
+    if (MD)
+      MD->invalidateCachedPredecessors();
     InvalidBlockRPONumbers = true;
-  return true;
+  }
+  return Changed;
 }
 
 /// Executes one iteration of GVN
 bool GVN::iterateOnFunction(Function &F) {
   cleanupGlobalSets();
 
   // Top-down walk of the dominator tree
   bool Changed = false;

llvm/test/Transforms/GVN/critical-edge-split-failure.ll

+; RUN: opt -gvn -S -o - %s | FileCheck %s
+; RUN: opt -passes=gvn -S -o - %s | FileCheck %s
+
+%struct.sk_buff = type opaque
+
+@l2tp_recv_dequeue_session = external dso_local local_unnamed_addr global i32, align 4
+@l2tp_recv_dequeue_skb = external dso_local local_unnamed_addr global %struct.sk_buff*, align 8
+@l2tp_recv_dequeue_session_2 = external dso_local local_unnamed_addr global i32, align 4
+@l2tp_recv_dequeue_session_0 = external dso_local local_unnamed_addr global i32, align 4
+
+declare void @llvm.assume(i1 noundef)
+
+define dso_local void @l2tp_recv_dequeue() local_unnamed_addr {
+entry:
+  %0 = load i32, i32* @l2tp_recv_dequeue_session, align 4
+  %conv = sext i32 %0 to i64
+  %1 = inttoptr i64 %conv to %struct.sk_buff*
+  %2 = load i32, i32* @l2tp_recv_dequeue_session_2, align 4
+  %tobool.not = icmp eq i32 %2, 0
+  br label %for.cond
+
+for.cond:                                         ; preds = %if.end, %entry
+  %storemerge = phi %struct.sk_buff* [ %1, %entry ], [ null, %if.end ]
+  store %struct.sk_buff* %storemerge, %struct.sk_buff** @l2tp_recv_dequeue_skb, align 8
+  br i1 %tobool.not, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.cond
+  %ns = bitcast %struct.sk_buff* %storemerge to i32*
+  %3 = load i32, i32* %ns, align 4
+  store i32 %3, i32* @l2tp_recv_dequeue_session_0, align 4
+; Splitting the critical edge from if.then to if.end will fail, but should not
+; cause an infinite loop in GVN. If we can one day split edges of callbr
+; indirect targets, great!
+; CHECK: callbr void asm sideeffect "", "X,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@l2tp_recv_dequeue, %if.end))
+; CHECK-NEXT: to label %asm.fallthrough.i [label %if.end]
+  callbr void asm sideeffect "", "X,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@l2tp_recv_dequeue, %if.end))
+          to label %asm.fallthrough.i [label %if.end]
+
+asm.fallthrough.i:                                ; preds = %if.then
+  br label %if.end
+
+if.end:                                           ; preds = %asm.fallthrough.i, %if.then, %for.cond
+  %ns1 = bitcast %struct.sk_buff* %storemerge to i32*
+  %4 = load i32, i32* %ns1, align 4
+  %tobool2.not = icmp eq i32 %4, 0
+  tail call void @llvm.assume(i1 %tobool2.not)
+  br label %for.cond
+}
+