[NewGVN] Add test with assume dominating an ICmp. NFC

[gandhi21299]

Summary

Inspired from https://github.com/llvm/llvm-project/issues/63337.

[nikic]

After @arsenm's change, InstSimplify should no longer work with instructions without parent. Can you explain how we end up working on an assume without parent in NewGVN? It's not really obvious to me.

[gandhi21299]

In D154307#4467219, @nikic wrote:

After @arsenm's change, InstSimplify should no longer work with instructions without parent. Can you explain how we end up working on an assume without parent in NewGVN? It's not really obvious to me.

I traced back the calls and they start from NewGVN::ExprResult NewGVN::performSymbolicEvaluation(Value *V, SmallPtrSetImpl<Value *> &Visited) const . I tried inserting the getParent() check in various places in NewGVN but it causes 5 LIT tests to fail for generating a few more basic blocks.

[nikic]

I believe this is related to the "phi of op" feature in NewGVN: https://github.com/llvm/llvm-project/blob/6954cb54252b50df95eea05c513e739b3ad2c8a0/llvm/lib/Transforms/Scalar/NewGVN.cpp#L2767 These cloned instructions won't have a parent.

I'm not entirely sure what to do here. I don't think that this fix is sufficient: If we need support for instructions without parent for NewGVN, then we need to revert @arsenm's change entirely, not just this part. Alternatively we need a different way to handle this on the NewGVN side. It may be possible to insert the instructions, as long as we are sure to later remove them again. I'm not sure if this would cause problems with NewGVNs design though, which is not supposed to do IR modifications during the analysis phase.

[fhahn]

In D154307#4467234, @nikic wrote:

I believe this is related to the "phi of op" feature in NewGVN: https://github.com/llvm/llvm-project/blob/6954cb54252b50df95eea05c513e739b3ad2c8a0/llvm/lib/Transforms/Scalar/NewGVN.cpp#L2767 These cloned instructions won't have a parent.

I'm not entirely sure what to do here. I don't think that this fix is sufficient: If we need support for instructions without parent for NewGVN, then we need to revert @arsenm's change entirely, not just this part. Alternatively we need a different way to handle this on the NewGVN side. It may be possible to insert the instructions, as long as we are sure to later remove them again. I'm not sure if this would cause problems with NewGVNs design though, which is not supposed to do IR modifications during the analysis phase.

NewGVN makes use of instructions without parents in multiple places; I'm surprised that there isn't more fallout from this. I am not sure if inserting the instructions in the existing IR would work well, but inserting them in a temporary block may work as workaround.

[nikic]

In D154307#4468201, @fhahn wrote:

In D154307#4467234, @nikic wrote:

I believe this is related to the "phi of op" feature in NewGVN: https://github.com/llvm/llvm-project/blob/6954cb54252b50df95eea05c513e739b3ad2c8a0/llvm/lib/Transforms/Scalar/NewGVN.cpp#L2767 These cloned instructions won't have a parent.

I'm not entirely sure what to do here. I don't think that this fix is sufficient: If we need support for instructions without parent for NewGVN, then we need to revert @arsenm's change entirely, not just this part. Alternatively we need a different way to handle this on the NewGVN side. It may be possible to insert the instructions, as long as we are sure to later remove them again. I'm not sure if this would cause problems with NewGVNs design though, which is not supposed to do IR modifications during the analysis phase.

NewGVN makes use of instructions without parents in multiple places; I'm surprised that there isn't more fallout from this.

This probably went unnoticed because we only assert that the instruction is inserted in the primary simplifyInstruction() entry point, but not the helpers for individual instruction types.

I am not sure if inserting the instructions in the existing IR would work well, but inserting them in a temporary block may work as workaround.

This seems like it might result in incorrect folds based on dominance relationships, especially is the temporary block is not connected to the CFG.

[arsenm]

The problems I ran into were from missing the parent context function. If we had the context function passed in separately from the instruction, I think it would matter less if they were attached to a block

[gandhi21299]

Inserting the cloned instruction ValueOp after I at https://github.com/llvm/llvm-project/blob/6954cb54252b50df95eea05c513e739b3ad2c8a0/llvm/lib/Transforms/Scalar/NewGVN.cpp#L2767 incorrectly deduces values in tests involving PHI of ops.

[ManuelJBrito]

Perhaps we could add this case as a check to OpIsSafeForPHIOfOps. While walking the operands we could check if they are used in an assume until we hit a dominator. Not sure this makes complete sense, but we already do something similar to prevent InstSimplify from code walking through non-dominating phis.

[gandhi21299]

@kmitropoulou noted that the PHI of ops transformation in the test is completely valid. This test might be a nice addition with llvm.assume() intrinsic in the LIT test suite.

[ManuelJBrito]

I don't think doing phi-of-ops on the following is valid :

%f.0 = phi i32 [ undef, %entry ], [ %xor, %if.then ], [ %xor, %if.then2 ]
...
%tobool9.not = icmp eq i32 %f.0, 0

entry:
%tobool9.not = icmp eq i32 undef, 0 -> undef 

if.then:
%tobool9.not = icmp eq i32 %xor, 0 -> false (wrong! No way of knowing this!)

if.then2:
%tobool9.not = icmp eq i32 %xor, 0 -> false ( correct!! From the assume)


%tobool9.not -> phi [undef, false, false] -> false ( wrong because of if.then value)

Alive2 proof: https://alive2.llvm.org/ce/z/V5ANuZ
Am I misunderstanding something?

[arsenm]

llvm/test/Transforms/NewGVN/assume-dominating-icmp.ll

5

Do you need the local_unnamed_addr and dso_local?

[gandhi21299]

@kmitropoulou will take over with a new revision.

[kmitropoulou]

@ManuelJBrito You are right :) I missed this. NewGVN checks if it can simplify icmp eq i32 %xor, 0. For this reason, it calls simplifyICmpInst() from InstructionSimplify.cpp. This function tries to find if the compare is dependent on a llvm.assume() intrinsic. Hence, it calls isValidAssumeForContext() which returns true for both cases! The isValidAssumeForContext() checks if the llvm.assume() dominates the icmp eq i32 %xor, 0. The problem is that icmp eq i32 %xor, 0 does not have a parent. Because of that, dominates() get confused that icmp eq i32 %xor, 0 is part of an unreachable block and it returns true.

llvm/test/Transforms/NewGVN/assume-dominating-icmp.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
+; RUN: opt -passes=newgvn -S < %s | FileCheck %s
+
+@c = dso_local local_unnamed_addr global i32 0, align 4
+
+; Function Attrs: nounwind optsize uwtable
+define dso_local i32 @main(i1 %cond, i32 %0, i32 %1) {
+; CHECK-LABEL: define dso_local i32 @main
+; CHECK-SAME: (i1 [[COND:%.*]], i32 [[TMP0:%.*]], i32 [[TMP1:%.*]]) {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND]], label [[IF_THEN:%.*]], label [[IF_END6:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[TMP0]], 1
+; CHECK-NEXT:    [[TOBOOL1_NOT:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL1_NOT]], label [[IF_END6]], label [[IF_THEN2:%.*]]
+; CHECK:       if.then2:
+; CHECK-NEXT:    [[TOBOOL3_NOT:%.*]] = icmp ne i32 [[XOR]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[TOBOOL3_NOT]])
+; CHECK-NEXT:    br label [[IF_END6]]
+; CHECK:       if.end6:
+; CHECK-NEXT:    [[F_0:%.*]] = phi i32 [ undef, [[ENTRY:%.*]] ], [ [[XOR]], [[IF_THEN]] ], [ [[XOR]], [[IF_THEN2]] ]
+; CHECK-NEXT:    [[NOT:%.*]] = xor i32 [[F_0]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, ptr @c, align 4
+; CHECK-NEXT:    [[OR:%.*]] = or i32 [[TMP2]], [[NOT]]
+; CHECK-NEXT:    [[TOBOOL7_NOT:%.*]] = icmp eq i32 [[OR]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL7_NOT]], label [[IF_END10:%.*]], label [[WHILE_COND_PREHEADER:%.*]]
+; CHECK:       while.cond.preheader:
+; CHECK-NEXT:    ret i32 1
+; CHECK:       if.end10:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  br i1 %cond, label %if.then, label %if.end6
+
+if.then:                                          ; preds = %entry
+  %xor = xor i32 %0, 1
+  %tobool1.not = icmp eq i32 %1, 0
+  br i1 %tobool1.not, label %if.end6, label %if.then2
+
+if.then2:                                         ; preds = %if.then
+  %tobool3.not = icmp ne i32 %xor, 0
+  tail call void @llvm.assume(i1 %tobool3.not)
+  br label %if.end6
+
+if.end6:                                          ; preds = %if.then2, %if.then, %entry
+  %f.0 = phi i32 [ undef, %entry ], [ %xor, %if.then ], [ %xor, %if.then2 ]
+  %not = xor i32 %f.0, -1
+  %2 = load i32, ptr @c, align 4
+  %or = or i32 %2, %not
+  %tobool7.not = icmp eq i32 %or, 0
+  %tobool9.not = icmp eq i32 %f.0, 0
+  %or.cond = or i1 %tobool7.not, %tobool9.not
+  br i1 %or.cond, label %if.end10, label %while.cond.preheader
+
+while.cond.preheader:                             ; preds = %if.end6
+  ret i32 1
+
+if.end10:                                         ; preds = %if.end6
+  ret i32 0
+}
+
+declare void @llvm.assume(i1 noundef)