[NewGVN] add context instruction for SimplifyQuery

[bcl5980]

Summary

NewGVN will find operator from other context. ValueTracking currently doesn't have a way to run completely without context instruction.
So it will use operator itself as conext instruction.
If the operator in another branch will never be executed but it has an assume, it may caused value tracking use the assume to do wrong simpilfy.

Check useInstrInfo flag in value tracking, if we haven't set the flag we will not use valjue itself as context instruction to fix the issue.

Fix #56039

[nlopes]

Could you please explain what's the bug and why is this the right fix?

[bcl5980]

In D127942#3588216, @nlopes wrote:

Could you please explain what's the bug and why is this the right fix?

The min reproduce RI has two load %b at different basic blocks. %bb2 has assumption for load %b data.
When newgvn pass try to call simplifyCmpInst for %tobool3.not.i = icmp eq i8 %lb1, 0, operand 0 is replaced to %lb2 based on allocate BasicExpression code.
%lb2 has assumption lager than 0 cause %tobool3.not.i = icmp eq i8 %lb1, 0 replaced by constant false.
But if the icmp return false %bb2 will be a dead block cause assumption is also dead.
The root cause is NewGVN haven't pass context instruction to simplify function cause wrong transform happen.
So we need to pass context instruction to avoid simplifyCmpInst return false to fix the issue.

[nikic]

SimplifyContext is created with CxtI=nullptr though, so I would expect it to not use a context instruction. Is the problem here that InstSimplify calls into ValueTracking helps like isKnownNonZero, and those convert CxtI==nullptr into the passed instruction in safeCxtI?

[bcl5980]

In D127942#3588322, @nikic wrote:

SimplifyContext is created with CxtI=nullptr though, so I would expect it to not use a context instruction. Is the problem here that InstSimplify calls into ValueTracking helps like isKnownNonZero, and those convert CxtI==nullptr into the passed instruction in safeCxtI?

Yes, it call isKnownNonZero to fold %tobool3.not.i = icmp eq i8 %lb1, 0 to false.

[nikic]

LGTM, but please update the patch description with details. I think it would be better to make these simplification queries not use context at all, but that would require some API changes. For now, this does seem to be better than before.

[fhahn]

In D127942#3588327, @bcl5980 wrote:

In D127942#3588322, @nikic wrote:

SimplifyContext is created with CxtI=nullptr though, so I would expect it to not use a context instruction. Is the problem here that InstSimplify calls into ValueTracking helps like isKnownNonZero, and those convert CxtI==nullptr into the passed instruction in safeCxtI?

Yes, it call isKnownNonZero to fold %tobool3.not.i = icmp eq i8 %lb1, 0 to false.

I guess I am still not sure where and why a context instruction appears to be used here, as at the moment SQ never sets one and no instruction is passed to simplify*?

It's been a while since I had a close look at the code, but I *think* here we intentionally do not use any context information for instruction simplify (e.g. we also avoid using flags on instructions when looking through operands).Conceptually I think the expressions here are intended to be evaluated independently of their location. If we change that, I am worried that we will trade one bug for another, perhaps more subtle one. It *sounds* like it would be better to adjust the API to do not come up with a different context instruction, if no CxtI is added or UseInstrInfo is false.

[nikic]

In D127942#3598316, @fhahn wrote:

In D127942#3588327, @bcl5980 wrote:

In D127942#3588322, @nikic wrote:

SimplifyContext is created with CxtI=nullptr though, so I would expect it to not use a context instruction. Is the problem here that InstSimplify calls into ValueTracking helps like isKnownNonZero, and those convert CxtI==nullptr into the passed instruction in safeCxtI?

Yes, it call isKnownNonZero to fold %tobool3.not.i = icmp eq i8 %lb1, 0 to false.

I guess I am still not sure where and why a context instruction appears to be used here, as at the moment SQ never sets one and no instruction is passed to simplify*?

See https://github.com/llvm/llvm-project/blob/ae76b2f455016efb8cac5519d382be575b2d2edc/llvm/lib/Analysis/ValueTracking.cpp#L133. ValueTracking currently doesn't have a way to run completely without context instruction.

In D127942#3598316, @fhahn wrote:

It's been a while since I had a close look at the code, but I *think* here we intentionally do not use any context information for instruction simplify (e.g. we also avoid using flags on instructions when looking through operands).Conceptually I think the expressions here are intended to be evaluated independently of their location. If we change that, I am worried that we will trade one bug for another, perhaps more subtle one. It *sounds* like it would be better to adjust the API to do not come up with a different context instruction, if no CxtI is added or UseInstrInfo is false.

I'm also somewhat apprehensive here -- the reason why I thought this would be safe is that this is part of the computation a specific instruction -- we don't fold every place where the same expression is used. However, the operands might come from a different context (which is why we also can't UseInstrInfo). In theory, I don't think that should be an issue, but in practice it may well be.

[fhahn]

In D127942#3598337, @nikic wrote:

See https://github.com/llvm/llvm-project/blob/ae76b2f455016efb8cac5519d382be575b2d2edc/llvm/lib/Analysis/ValueTracking.cpp#L133. ValueTracking currently doesn't have a way to run completely without context instruction.

I'm also somewhat apprehensive here -- the reason why I thought this would be safe is that this is part of the computation a specific instruction -- we don't fold every place where the same expression is used. However, the operands might come from a different context (which is why we also can't UseInstrInfo). In theory, I don't think that should be an issue, but in practice it may well be.

Ah right, so it sounds a better fix would be to update ValueTracking to respect UseInstrInfo (only set by NewGVN AFAIK, so we could also rename it/update the documentation) when picking a safe context instruction, by moving the static function to SimplifyQuery?

[bcl5980]

In D127942#3601587, @fhahn wrote:

In D127942#3598337, @nikic wrote:

See https://github.com/llvm/llvm-project/blob/ae76b2f455016efb8cac5519d382be575b2d2edc/llvm/lib/Analysis/ValueTracking.cpp#L133. ValueTracking currently doesn't have a way to run completely without context instruction.

I'm also somewhat apprehensive here -- the reason why I thought this would be safe is that this is part of the computation a specific instruction -- we don't fold every place where the same expression is used. However, the operands might come from a different context (which is why we also can't UseInstrInfo). In theory, I don't think that should be an issue, but in practice it may well be.

Ah right, so it sounds a better fix would be to update ValueTracking to respect UseInstrInfo (only set by NewGVN AFAIK, so we could also rename it/update the documentation) when picking a safe context instruction, by moving the static function to SimplifyQuery?

Do I need to revert current code now ?

[bcl5980]

do not use value as context if UseInstrInfo is false.

[bcl5980]

@fhahn, is this the better way you say?

[fhahn]

llvm/lib/Analysis/ValueTracking.cpp

134 ↗

(On Diff #439005)

it seems it would be slightly simpler to move safeCxtI to SimplifyQuery?

[fhahn]

Also, it would probably be good to have this patch as a separate one, with an updated title/description

[bcl5980]

In D127942#3607373, @fhahn wrote:

Also, it would probably be good to have this patch as a separate one, with an updated title/description

OK. I will try to work on it on another patch.

[bcl5980]

llvm/lib/Analysis/ValueTracking.cpp

134 ↗

(On Diff #439005)

Just a idea to make sure
How about just set CxtI to nullptr when UseInstrInfo is false? @fhahn @nikic

@@ -115,8 +116,8 @@ struct SimplifyQuery {
                 AssumptionCache *AC = nullptr,
                 const Instruction *CXTI = nullptr, bool UseInstrInfo = true,
                 bool CanUseUndef = true)
-      : DL(DL), TLI(TLI), DT(DT), AC(AC), CxtI(CXTI), IIQ(UseInstrInfo),
-        CanUseUndef(CanUseUndef) {}
+      : DL(DL), TLI(TLI), DT(DT), AC(AC), IIQ(UseInstrInfo),
+        CxtI(UseInstrInfo ? CxtI : nullptr), CanUseUndef(CanUseUndef) {}

   Query(const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI,
         const DominatorTree *DT, bool UseInstrInfo,
         OptimizationRemarkEmitter *ORE = nullptr)
-      : DL(DL), AC(AC), CxtI(CxtI), DT(DT), ORE(ORE), IIQ(UseInstrInfo) {}
+      : DL(DL), AC(AC), IIQ(UseInstrInfo), CxtI(UseInstrInfo ? CxtI : nullptr),
+        DT(DT), ORE(ORE) {}

llvm/lib/Transforms/Scalar/NewGVN.cpp

bool NewGVN::setBasicExpressionInfo(Instruction *I, BasicExpression *E) const {
 
   return AllConstant;
 }
 
 const Expression *NewGVN::createBinaryExpression(unsigned Opcode, Type *T,
                                                  Value *Arg1, Value *Arg2,
                                                  Instruction *I) const {
   auto *E = new (ExpressionAllocator) BasicExpression(2);
+  const SimplifyQuery Q = SQ.getWithInstruction(I);
 
   E->setType(T);
   E->setOpcode(Opcode);
   E->allocateOperands(ArgRecycler, ExpressionAllocator);
   if (Instruction::isCommutative(Opcode)) {
     // Ensure that commutative instructions that only differ by a permutation
     // of their operands get the same value number by sorting the operand value
     // numbers.  Since all commutative instructions have two operands it is more
     // efficient to sort by hand rather than using, say, std::sort.
     if (shouldSwapOperands(Arg1, Arg2))
       std::swap(Arg1, Arg2);
   }
   E->op_push_back(lookupOperandLeader(Arg1));
   E->op_push_back(lookupOperandLeader(Arg2));
 
-  Value *V = simplifyBinOp(Opcode, E->getOperand(0), E->getOperand(1), SQ);
+  Value *V = simplifyBinOp(Opcode, E->getOperand(0), E->getOperand(1), Q);
   if (auto Simplified = checkExprResults(E, I, V)) {
     addAdditionalUsers(Simplified, I);
     return Simplified.Expr;
   }
   return E;
 }
 
 // Take a Value returned by simplification of Expression E/Instruction
NewGVN::ExprResult NewGVN::checkExprResults(Expression *E, Instruction *I,
   return ExprResult::none();
 }
 
 // Create a value expression from the instruction I, replacing operands with
 // their leaders.
 
 NewGVN::ExprResult NewGVN::createExpression(Instruction *I) const {
   auto *E = new (ExpressionAllocator) BasicExpression(I->getNumOperands());
+  const SimplifyQuery Q = SQ.getWithInstruction(I);
 
   bool AllConstant = setBasicExpressionInfo(I, E);
 
   if (I->isCommutative()) {
     // Ensure that commutative instructions that only differ by a permutation
     // of their operands get the same value number by sorting the operand value
     // numbers.  Since all commutative instructions have two operands it is more
     // efficient to sort by hand rather than using, say, std::sort.
if (auto *CI = dyn_cast<CmpInst>(I)) {
     }
     E->setOpcode((CI->getOpcode() << 8) | Predicate);
     // TODO: 25% of our time is spent in simplifyCmpInst with pointer operands
     assert(I->getOperand(0)->getType() == I->getOperand(1)->getType() &&
            "Wrong types on cmp instruction");
     assert((E->getOperand(0)->getType() == I->getOperand(0)->getType() &&
             E->getOperand(1)->getType() == I->getOperand(1)->getType()));
     Value *V =
-        simplifyCmpInst(Predicate, E->getOperand(0), E->getOperand(1), SQ);
+        simplifyCmpInst(Predicate, E->getOperand(0), E->getOperand(1), Q);
     if (auto Simplified = checkExprResults(E, I, V))
       return Simplified;
   } else if (isa<SelectInst>(I)) {
     if (isa<Constant>(E->getOperand(0)) ||
         E->getOperand(1) == E->getOperand(2)) {
       assert(E->getOperand(1)->getType() == I->getOperand(1)->getType() &&
              E->getOperand(2)->getType() == I->getOperand(2)->getType());
       Value *V = simplifySelectInst(E->getOperand(0), E->getOperand(1),
-                                    E->getOperand(2), SQ);
+                                    E->getOperand(2), Q);
       if (auto Simplified = checkExprResults(E, I, V))
         return Simplified;
     }
   } else if (I->isBinaryOp()) {
     Value *V =
-        simplifyBinOp(E->getOpcode(), E->getOperand(0), E->getOperand(1), SQ);
+        simplifyBinOp(E->getOpcode(), E->getOperand(0), E->getOperand(1), Q);
     if (auto Simplified = checkExprResults(E, I, V))
       return Simplified;
   } else if (auto *CI = dyn_cast<CastInst>(I)) {
     Value *V =
-        simplifyCastInst(CI->getOpcode(), E->getOperand(0), CI->getType(), SQ);
+        simplifyCastInst(CI->getOpcode(), E->getOperand(0), CI->getType(), Q);
     if (auto Simplified = checkExprResults(E, I, V))
       return Simplified;
   } else if (auto *GEPI = dyn_cast<GetElementPtrInst>(I)) {
     Value *V =
         simplifyGEPInst(GEPI->getSourceElementType(), *E->op_begin(),
                         makeArrayRef(std::next(E->op_begin()), E->op_end()),
-                        GEPI->isInBounds(), SQ);
+                        GEPI->isInBounds(), Q);
     if (auto Simplified = checkExprResults(E, I, V))
       return Simplified;
   } else if (AllConstant) {
     // We don't bother trying to simplify unless all of the operands
     // were constant.
     // TODO: There are a lot of Simplify*'s we could call here, if we
     // wanted to.  The original motivating case for this code was a
     // zext i1 false to i8, which we don't have an interface to

llvm/test/Transforms/NewGVN/sq-ctxi.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes=newgvn -S | FileCheck %s
+
+; github issue #56039
+define i8 @src(i8* %a, i8* %b, i1 %c) {
+; CHECK-LABEL: @src(
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[LB1:%.*]] = load i8, i8* [[B:%.*]], align 1
+; CHECK-NEXT:    [[TOBOOL3_NOT_I:%.*]] = icmp eq i8 [[LB1]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL3_NOT_I]], label [[BB4:%.*]], label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[LB2:%.*]] = load i8, i8* [[B]], align 1
+; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult i8 0, [[LB2]]
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT_I]])
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[LA:%.*]] = load i8, i8* [[A:%.*]], align 1
+; CHECK-NEXT:    br label [[BB4]]
+; CHECK:       bb4:
+; CHECK-NEXT:    ret i8 0
+;
+  br i1 %c, label %bb1, label %bb2
+
+bb1:
+  %lb1 = load i8, i8* %b
+  %tobool3.not.i = icmp eq i8 %lb1, 0
+  br i1 %tobool3.not.i, label %bb4, label %bb3
+
+bb2:
+  %lb2 = load i8, i8* %b
+  %cmp.not.i = icmp ult i8 0, %lb2
+  tail call void @llvm.assume(i1 %cmp.not.i)
+  br label %bb3
+
+bb3:
+  %p = phi i8 [ %lb1, %bb1 ], [ %lb2, %bb2 ]
+  %la = load i8, i8* %a
+  %xor = xor i8 %la, %p
+  br label %bb4
+
+bb4:
+  ret i8 0
+}
+
+declare void @llvm.assume(i1)