[GVNSink] Reuse value numbering from GVN

[hiraditya]

GVNSink has a custom gvn code see:

llvm-project/llvm/lib/Transforms/Scalar/GVNSink.cpp

Line 504 in 93b4705

hash_code H = exp->getHashValue([=](Value *V) { return lookupOrAdd(V); });

This is not maintainable, we can reuse the one from GVN similar to how GVNHoist does it https://llvm.org/doxygen/GVNHoist_8cpp_source.html#l00225.

[hiraditya]

This is a follow up from the discussion in #77852 (comment)

[mvvsmk]

Hey @hiraditya , I would like to take this issue up, as far as I understand it GVNSink uses it's own implimentation of lookupOrAdd and the complete value system is defined in GVNSink.cpp itself, on the other hand GVNHoist uses the implimentation in GVN.cpp, which I agree is a much more maintanable approach.

To solve this issue I would have to refactor all occurences of the implimentation of the value system by GVNSink and replace with calls to the GVN.cpp implimetations. Right?

If I understand this issue correctly could you assign it to me and I would get working on it. :)

PS : I am here after interacting with llvm-social bangalore group :)

[mvvsmk]

After further analysis , I have observed the following .

1. Even after the simple refactor of the numbering system to the one used by GVN.h , 11 tests of GVNSink did not pass.
2. Upon further inspection I found out it's method of counting takes a completely different approach which cannot be matched by GVN.h as concptually it's very different, as explained in the following lines by the Pass author.

llvm-project/llvm/lib/Transforms/Scalar/GVNSink.cpp

Lines 15 to 32 in 93b4705

	///
	/// [ %a1 = add i32 %b, 1 ] [ %c1 = add i32 %d, 1 ]
	/// [ %a2 = xor i32 %a1, 1 ] [ %c2 = xor i32 %c1, 1 ]
	/// \ /
	/// [ %e = phi i32 %a2, %c2 ]
	/// [ add i32 %e, 4 ]
	///
	///
	/// GVN would number %a1 and %c1 differently because they compute different
	/// results - the VN of an instruction is a function of its opcode and the
	/// transitive closure of its operands. This is the key property for hoisting
	/// and CSE.
	///
	/// What we want when sinking however is for a numbering that is a function of
	/// the *uses* of an instruction, which allows us to answer the question "if I
	/// replace %a1 with %c1, will it contribute in an equivalent way to all
	/// successive instructions?". The PostValueTable class in GVN provides this
	/// mapping.

How would you like me to proceed ?

1. Should I transfer the Value Numbering class fron Sink to GVN.h under a different name ?
2. Create a separate header to hold this implimentation of GVN so it can be used some place else too ?
3. I am open to any ideas you may have.

[mvvsmk]

Hey @hiraditya, would be very greatful if you could give me a direction on this, I have provide a snippet to what is the refactor I was refering to in my previous comment, but the fundametal problem remains the same, here is an example :

Example

example.ll

define zeroext i1 @test1(i1 zeroext %flag, i32 %blksA, i32 %blksB, i32 %nblks) {
entry:
  br i1 %flag, label %if.then, label %if.else

if.then:
  %cmp = icmp uge i32 %blksA, %nblks
  %frombool1 = zext i1 %cmp to i8                   # sink candidate 1
  br label %if.end

if.else:
  %add = add i32 %nblks, %blksB
  %cmp2 = icmp ule i32 %add, %blksA
  %frombool3 = zext i1 %cmp2 to i8                  # sink candidate 2
  br label %if.end

if.end:
  %obeys.0 = phi i8 [ %frombool1, %if.then ], [ %frombool3, %if.else ]
  %tobool4 = icmp ne i8 %obeys.0, 0
  ret i1 %tobool4
}

Case of GVNSink 's ValueTable

• value assigned to : sink candidate 1 = 2
• value assigned to : sink candidate 2 = 2

Case of GVN 's ValueTable

• value assigned to : sink candidate 1 = 8
• value assigned to : sink candidate 2 = 6

Possible Reason :

GVN Sink uses a variant of GVN bases on uses, than the actual value, the justification for this is given in the pass itself.

llvm-project/llvm/lib/Transforms/Scalar/GVNSink.cpp

Lines 9 to 32 in 93b4705

	/// \file GVNSink.cpp
	/// This pass attempts to sink instructions into successors, reducing static
	/// instruction count and enabling if-conversion.
	///
	/// We use a variant of global value numbering to decide what can be sunk.
	/// Consider:
	///
	/// [ %a1 = add i32 %b, 1 ] [ %c1 = add i32 %d, 1 ]
	/// [ %a2 = xor i32 %a1, 1 ] [ %c2 = xor i32 %c1, 1 ]
	/// \ /
	/// [ %e = phi i32 %a2, %c2 ]
	/// [ add i32 %e, 4 ]
	///
	///
	/// GVN would number %a1 and %c1 differently because they compute different
	/// results - the VN of an instruction is a function of its opcode and the
	/// transitive closure of its operands. This is the key property for hoisting
	/// and CSE.
	///
	/// What we want when sinking however is for a numbering that is a function of
	/// the *uses* of an instruction, which allows us to answer the question "if I
	/// replace %a1 with %c1, will it contribute in an equivalent way to all
	/// successive instructions?". The PostValueTable class in GVN provides this
	/// mapping.

Very Simple Refactor to replicate Observations

The simple refactor that compiles is , note this dosen't resolve the issue :

llvm-project/llvm/lib/Transforms/Scalar/GVNSink.cpp

Lines 571 to 586 in 93b4705

	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;

diff :

  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()));
+    // VN.setReachableBBs(BasicBlocksSet(RPOT.begin(), RPOT.end()));
    for (auto *N : RPOT)
      NumSunk += sinkBB(N);

    return NumSunk > 0;
  }
  
private:
-  ValueTable VN;
+  GVNPass::ValueTable VN;

[hiraditya]

As long as the same number of values are unique we should be fine. It could be that the current value numbering of GVN isn't powerful enough and maybe Newgvn has a better approach?

[mvvsmk]

I see, I will explore the new GVN 's Value Numbering too. As you correctly pointed out, the current model of GVN doesn't capture the "use" essence that the GVN Sink pass requires as GVNSink.cpp says, if that is solved in New GVN and we can get the numbering which is sutable for this pass, we'll be able to solve this issue.

Thank you for helping me out. :)