[GVNSink] Make GVNSink resistant against self referencing instructions (PR36954)

[yurai007]

Summary

Before this change GVNSink pass suffers from stack overflow while processing self referenced instruction in unreachable basic block.
According [1] and [2] it's reasonable to make pass resistant against self referencing instructions.
To fix issue we skip sinking analysis when we reach instruction coming from unreachable block.

[1] https://groups.google.com/g/llvm-dev/c/843Tig9IzwA
[2] https://lists.llvm.org/pipermail/llvm-dev/2015-February/082629.html

[xbolva00]

Skip analysis for unreachable BBs?

[nikic]

llvm/lib/Transforms/Scalar/GVNSink.cpp

364

This checks for a directly self-referential instruction, but the references may also be cyclic across multiple instructions.

As @xbolva00 mentioned, it may be simpler/cleaner to skip unreachable blocks.

llvm/test/Transforms/GVNSink/sink-common-code.ll

775

Can this test be further reduced?

[yurai007]

llvm/lib/Transforms/Scalar/GVNSink.cpp

364

Yes, and that's what I proposed as alternative solution: https://bugs.llvm.org/show_bug.cgi?id=36954#c9 It would save some work and resolve cycles problem. The only drawback I see now is need of giving GVNSink access to DT since we need isReachableFromEntry or analogous machinery for checking reachability. I started with first, simpler approach because it was preferred by @jeroen.dobbelaere, however checking cycles with this idea during lookupOrAdd run seem to be nontrivial. So yes, I can switch to second approach and check where it leads.

[yurai007]

Looks like problem still occurs: https://github.com/llvm/llvm-project/issues/36302 and https://godbolt.org/z/ofGW3zzaG . After rebasing I'm gonna move on with patch.

[yurai007]

Addressed all comments.

[nikic]

We don't strictly need a dominator tree here, it's possible to collect unreachable blocks upfront. It seems a bit odd to require dominator tree just for this purpose.

[yurai007]

In D113897#3485511, @nikic wrote:

We don't strictly need a dominator tree here, it's possible to collect unreachable blocks upfront. It seems a bit odd to require dominator tree just for this purpose.

Ok. I will get rid of it.

[yurai007]

Now basic blocks reachable from entry are collected up front only once before function sinking.
Another option would be doing it in flight but now we are processing instructions in reverse order starting from bottom block via ReversePostOrderTraversal.
I guess it would make collecting visited and reachable BBs from entry less straightforward than there is now.

[nikic]

llvm/lib/Transforms/Scalar/GVNSink.cpp

393

Is the optional here needed? Don't we expect this to always be set before it gets used?

582

Can't you just reuse RPOT here? That is, iterate it into a set? RPOT doesn't visit unreachable blocks, and it is cached, so reusing it is fine.

[yurai007]

llvm/lib/Transforms/Scalar/GVNSink.cpp

582

Thanks for pointing this out. I had to have some kind of mental block to not see how RPOT could be reused in such obvious way.

[yurai007]

llvm/lib/Transforms/Scalar/GVNSink.cpp

393

Technically it's possible to use ValueTable without ReachableBBs being set. But for now we always set it before sinking so yes - Optional can be simply removed.

[nikic]

LGTM, though it would be good to further reduce the test case if that's possible.

[yurai007]

Reduce test case even further.

[yurai007]

In D113897#3498760, @nikic wrote:

LGTM, though it would be good to further reduce the test case if that's possible.

Thanks a lot for review!

llvm/lib/Transforms/Scalar/GVNSink.cpp

InstructionUseExpr(Instruction *I, ArrayRecycler<Value *> &R,
     setOpcode(I->getOpcode());
     setType(I->getType());
 
     if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I))
       ShuffleMask = SVI->getShuffleMask().copy(A);
 
     for (auto &U : I->uses())
       op_push_back(U.getUser());
     llvm::sort(op_begin(), op_end());
   }
 
   void setMemoryUseOrder(unsigned MUO) { MemoryUseOrder = MUO; }
   void setVolatile(bool V) { Volatile = V; }
 
   hash_code getHashValue() const override {
     return hash_combine(GVNExpression::BasicExpression::getHashValue(),
                         MemoryUseOrder, Volatile, ShuffleMask);
   }
 
   template <typename Function> hash_code getHashValue(Function MapFn) {
     hash_code H = hash_combine(getOpcode(), getType(), MemoryUseOrder, Volatile,
                                ShuffleMask);
     for (auto *V : operands())
       H = hash_combine(H, MapFn(V));
     return H;
   }
 };
 
+using BasicBlocksSet = SmallPtrSet<const BasicBlock *, 32>;
+
 class ValueTable {
   DenseMap<Value *, uint32_t> ValueNumbering;
   DenseMap<GVNExpression::Expression *, uint32_t> ExpressionNumbering;
   DenseMap<size_t, uint32_t> HashNumbering;
   BumpPtrAllocator Allocator;
   ArrayRecycler<Value *> Recycler;
   uint32_t nextValueNumber = 1;
+  BasicBlocksSet ReachableBBs;
 
   /// Create an expression for I based on its opcode and its uses. If I
   /// touches or reads memory, the expression is also based upon its memory
   /// order - see \c getMemoryUseOrder().
   InstructionUseExpr *createExpr(Instruction *I) {
     InstructionUseExpr *E =
         new (Allocator) InstructionUseExpr(I, Recycler, Allocator);
     if (isMemoryInst(I))
template <class Inst> InstructionUseExpr *createMemoryExpr(Inst *I) {
     InstructionUseExpr *E = createExpr(I);
     E->setVolatile(I->isVolatile());
     return E;
   }
 
 public:
   ValueTable() = default;
 
+  /// Set basic blocks reachable from entry block.
+  void setReachableBBs(const BasicBlocksSet &ReachableBBs) {
+    this->ReachableBBs = ReachableBBs;
+  }
+
   /// Returns the value number for the specified value, assigning
   /// it a new number if it did not have one before.
   uint32_t lookupOrAdd(Value *V) {
     auto VI = ValueNumbering.find(V);
     if (VI != ValueNumbering.end())
       return VI->second;
 
     if (!isa<Instruction>(V)) {
       ValueNumbering[V] = nextValueNumber;
       return nextValueNumber++;
     }
 
     Instruction *I = cast<Instruction>(V);
+    if (!ReachableBBs.contains(I->getParent()))
+      return ~0U;
+
     InstructionUseExpr *exp = nullptr;
     switch (I->getOpcode()) {
     case Instruction::Load:
       exp = createMemoryExpr(cast<LoadInst>(I));
       break;
     case Instruction::Store:
       exp = createMemoryExpr(cast<StoreInst>(I));
       break;
public:
   GVNSink() = default;
 
   bool run(Function &F) {
     LLVM_DEBUG(dbgs() << "GVNSink: running on function @" << F.getName()
                       << "\n");
 
     unsigned NumSunk = 0;
     ReversePostOrderTraversal<Function*> RPOT(&F);
+    VN.setReachableBBs(BasicBlocksSet(RPOT.begin(), RPOT.end()));
     for (auto *N : RPOT)
       NumSunk += sinkBB(N);
 
     return NumSunk > 0;
   }
 
 private:
   ValueTable VN;

llvm/test/Transforms/GVNSink/sink-common-code.ll

if.else:
   %b = addrspacecast i32* %x to i32 addrspace(3)*
   store i32 10, i32 addrspace(3)* %b
   br label %if.end
 
 if.end:
   ret i32 1
 }
 
+; CHECK-LABEL: test_pr36954
+; CHECK-NOT: xor
+; PR36954 reproducer containing self referencing instruction shouldn't crash GVNSink pass.
+define void @test_pr36954() {
+bb1:
+  %i2 = trunc i32 undef to i8
+  br label %bb2
+
+bb2:
+  br i1 undef, label %bb2, label %exit
+
+bb4.critedge:
+  %i6 = sub i8 %i2, undef
+  %i7 = zext i8 %i6 to i32
+  %i8 = xor i32 %i8, %i7
+  br i1 false, label %exit, label %bb4.critedge
+
+exit:
+  ret void
+}
+
 ; CHECK: !0 = !{!1, !1, i64 0}
 ; CHECK: !1 = !{!"float", !2}
 ; CHECK: !2 = !{!"an example type tree"}