[ValueTracking] Let isGuaranteedNotToBeUndefOrPoison look into branch conditions of dominating blocks' terminators

[aqjune]

Summary

  br i1 c, BB1, BB2:
BB1:
  use1(c)
BB2:
  use2(c)

In BB1 and BB2, c is never undef or poison because otherwise the branch would have triggered UB.

Checked with Alive2

[lebedev.ri]

I agree this is correct, but this seems rather pessimistic.
Don't we want to look at every br that dominates Q.CxtI?

[jdoerfert]

Wouldn't we want something like this instead:

// Use a utility function defined in ValueTracking.
if (llvm::isGuaranteedNotToBeUndefOrPoison(Op0))
  return Op0;
// Use a utility function defined in ValueTracking.
if (llvm::isGuaranteedToBeUBIfUndefOrPoisonAt(Op0, Q.CtxI))
  return Op0;

And then centralized collect known UB cases?

[sanjoy]

I don't remember this code very well but can there be an exit(0) between the freeze and branch?

[sanjoy]

In D75401#1899675, @sanjoy wrote:

I don't remember this code very well but can there be an exit(0) between the freeze and branch?

Never mind, the example looks correct so I think I'm just misremembering how this works.

[aqjune]

In D75401#1899675, @sanjoy wrote:

I don't remember this code very well but can there be an exit(0) between the freeze and branch?

Hi, I guess the condition was needed for loop unswitching:

for (..) {
  g();
  if(b) { A } else { B }
}

When unswitching if(b), g() might exit or throw an exception, so b should be freezed.

[aqjune]

In D75401#1899543, @lebedev.ri wrote:

Don't we want to look at every br that dominates Q.CxtI?

In D75401#1899594, @jdoerfert wrote:

And then centralized collect known UB cases?

Makes sense, I'll make isGuaranteedNotToBeUndefOrPoison take the CxtI.

[aqjune]

Let ValueTracking::isGuaranteedNotToBeUndefOrPoison look into branch conditions of dominating blocks' terminators

[aqjune]

clang-format

[jdoerfert]

You might need to check if the branch "must-be-executed" from the CtxI. See the example.

llvm/lib/Analysis/ValueTracking.cpp

4563

Style: early exit !CtxI.

llvm/test/Transforms/InstSimplify/freeze.ll

58

@sanjoy Did have a point (I think). What happens if you have:

declare void @use(i1 %f) willreturn nounwind
declare void @exit()
define i1 @brcond_never_reached(i1 %c, i1 %c2) {
  %f = freeze i1 %c
  call void @use(i1 %f)
  call void exit();
  call void @use(i1 %f)
  br i1 %c, label %A, label %B
A:
  br i1 %c2, label %A2, label %B
A2:
  ret i1 %f
B:
  ret i1 %f
}

[reames]

llvm/lib/Analysis/ValueTracking.cpp

4563

This should probably be inside programUndefinedIfFullPoison

4579

This is incorrect. Consider:
b = freeze a
throw_if_a_would_be_poison()
if (a == 5) {}

You can only use branches which either a) dominate the freeze's uses, or b) are guaranteed to execute if any of those uses execute. (a) is a subcase of (b) which happens to be cheap to check. Note that phrasing in terms of "uses" here, not the freeze def.

[aqjune]

• Address comments
• Update test

[aqjune]

llvm/lib/Analysis/ValueTracking.cpp

4563

I think the current one is more general than programUndefinedIfFullPoison(I) in that it takes only instructions as input whereas this code can take the case when V is a constant expression into account as well.

4579

You're right, so at least I should have seen idom(CxtI->getParent()), but not CxtI->getParent().
To clarify, CxtI is the location where we'd like to check whether V is poison or not, I left it as a comment at the declaration of isGuaranteedNotToBeUndefOrPoison. I used the text from isSafeToSpeculativelyExecute()

[aqjune]

llvm/test/Transforms/InstSimplify/freeze.ll

58

The first use(f) cannot be optimized use(c). I added a test for this case.

[aqjune]

In the brcond_switch and brcond tests, freezes are moved into the block because simply InstSimplify is not recursively looking into operands of ret instructions. Even if freezes are outside the branches (as shown in the previous patch), the optimization is still correct.

[jdoerfert]

llvm/include/llvm/Analysis/ValueTracking.h

575

If CtxI and DT are specified...

llvm/lib/Analysis/ValueTracking.cpp

4585

Style: Remove hasCond (which should be HasCond btw.) and just return true in the conditionals. Remove the else to.

Nit: N -> Dominator (or similar),

[aqjune]

Address comments

[aqjune]

Revert whitespace diff

[reames]

LGTM

Long term, I think we'll want something more general, but for the moment, this is a lot better than nothing.

[DaniilSuchkov]

Hi! Unfortunately I had to revert this patch, see my comment here: https://reviews.llvm.org/rG952ad4701cf0d8da79789f6b83ddaa386c60d535

[aqjune]

Fixed ( https://github.com/llvm/llvm-project/commit/d7267ee1941668d7e985681e29d10983799811a0 )
The reason was that LoopRotate was calling SimplifyInstruction(I) where I is a cloned instruction. CtxI is set as I by SimplifyInstruction, causing getting dom node from CtxI->getParent() to crash.

llvm/include/llvm/Analysis/ValueTracking.h

class Value;
   /// trigger undefined behavior.
   ///
   /// Note that this currently only considers the basic block that is
   /// the parent of I.
   bool programUndefinedIfFullPoison(const Instruction *PoisonI);
 
   /// Return true if this function can prove that V is never undef value
   /// or poison value.
-  bool isGuaranteedNotToBeUndefOrPoison(const Value *V);
+  //
+  /// If CtxI and DT are specified this method performs flow-sensitive analysis
+  /// and returns true if it is guaranteed to be never undef or poison
+  /// immediately before the CtxI.
+  bool isGuaranteedNotToBeUndefOrPoison(const Value *V,
+                                        const Instruction *CtxI = nullptr,
+                                        const DominatorTree *DT = nullptr);
 
   /// Specific patterns of select instructions we can match.
   enum SelectPatternFlavor {
     SPF_UNKNOWN = 0,
     SPF_SMIN,                   /// Signed minimum
     SPF_UMIN,                   /// Unsigned minimum
     SPF_SMAX,                   /// Signed maximum
     SPF_UMAX,                   /// Unsigned maximum

llvm/lib/Analysis/InstructionSimplify.cpp

if (!C)
       return nullptr;
     ConstantArgs.push_back(C);
   }
 
   return ConstantFoldCall(Call, F, ConstantArgs, Q.TLI);
 }
 
 /// Given operands for a Freeze, see if we can fold the result.
-static Value *SimplifyFreezeInst(Value *Op0) {
+static Value *SimplifyFreezeInst(Value *Op0, const SimplifyQuery &Q) {
   // Use a utility function defined in ValueTracking.
-  if (llvm::isGuaranteedNotToBeUndefOrPoison(Op0))
+  if (llvm::isGuaranteedNotToBeUndefOrPoison(Op0, Q.CxtI, Q.DT))
     return Op0;
+
   // We have room for improvement.
   return nullptr;
 }
 
 Value *llvm::SimplifyFreezeInst(Value *Op0, const SimplifyQuery &Q) {
-  return ::SimplifyFreezeInst(Op0);
+  return ::SimplifyFreezeInst(Op0, Q);
 }
 
 /// See if we can compute a simplified version of this instruction.
 /// If not, this returns null.
 
 Value *llvm::SimplifyInstruction(Instruction *I, const SimplifyQuery &SQ,
                                  OptimizationRemarkEmitter *ORE) {
   const SimplifyQuery Q = SQ.CxtI ? SQ : SQ.getWithInstruction(I);

llvm/lib/Analysis/ValueTracking.cpp

auto AllUsesGuardedByBranch = [&](const BranchInst *BI) {
     }
 
     return true;
   };
 
   return llvm::any_of(GuardingBranches, AllUsesGuardedByBranch);
 }
 
-bool llvm::isGuaranteedNotToBeUndefOrPoison(const Value *V) {
+bool llvm::isGuaranteedNotToBeUndefOrPoison(const Value *V,
+                                            const Instruction *CtxI,
+                                            const DominatorTree *DT) {
   // If the value is a freeze instruction, then it can never
   // be undef or poison.
   if (isa<FreezeInst>(V))
     return true;
   // TODO: Some instructions are guaranteed to return neither undef
   // nor poison if their arguments are not poison/undef.
 
   // TODO: Deal with other Constant subclasses.
bool llvm::isGuaranteedNotToBeUndefOrPoison(const Value *V,
 
   if (auto I = dyn_cast<Instruction>(V)) {
     if (programUndefinedIfFullPoison(I) && I->getType()->isIntegerTy(1))
       // Note: once we have an agreement that poison is a value-wise concept,
       // we can remove the isIntegerTy(1) constraint.
       return true;
   }
 
+  if (!CtxI || !DT)
+    return false;
+
+  // If V is used as a branch condition before reaching CtxI, V cannot be
+  // undef or poison.
+  //   br V, BB1, BB2
+  // BB1:
+  //   CtxI ; V cannot be undef or poison here
+  auto Dominator = DT->getNode(CtxI->getParent())->getIDom();
+  while (Dominator) {
+    auto *TI = Dominator->getBlock()->getTerminator();
+
+    if (auto BI = dyn_cast<BranchInst>(TI)) {
+      if (BI->isConditional() && BI->getCondition() == V)
+        return true;
+    } else if (auto SI = dyn_cast<SwitchInst>(TI)) {
+      if (SI->getCondition() == V)
+        return true;
+    }
+
+    Dominator = Dominator->getIDom();
+  }
+
   return false;
 }
 
 OverflowResult llvm::computeOverflowForSignedAdd(const AddOperator *Add,
                                                  const DataLayout &DL,
                                                  AssumptionCache *AC,
                                                  const Instruction *CxtI,
                                                  const DominatorTree *DT) {

llvm/test/Transforms/InstSimplify/freeze.ll

 
 define i32 @make_const() {
 ; CHECK-LABEL: @make_const(
 ; CHECK-NEXT:    ret i32 10
 ;
   %x = freeze i32 10
   ret i32 %x
 }
+
+define i1 @brcond(i1 %c, i1 %c2) {
+; CHECK-LABEL: @brcond(
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[A:%.*]], label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[A2:%.*]], label [[B]]
+; CHECK:       A2:
+; CHECK-NEXT:    ret i1 [[C]]
+; CHECK:       B:
+; CHECK-NEXT:    ret i1 [[C]]
+;
+  br i1 %c, label %A, label %B
+A:
+  br i1 %c2, label %A2, label %B
+A2:
+  %f1 = freeze i1 %c
+  ret i1 %f1
+B:
+  %f2 = freeze i1 %c
+  ret i1 %f2
+}
+
+define i32 @brcond_switch(i32 %x) {
+; CHECK-LABEL: @brcond_switch(
+; CHECK-NEXT:    switch i32 [[X:%.*]], label [[EXIT:%.*]] [
+; CHECK-NEXT:    i32 0, label [[A:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       A:
+; CHECK-NEXT:    ret i32 [[X]]
+; CHECK:       EXIT:
+; CHECK-NEXT:    ret i32 [[X]]
+;
+  switch i32 %x, label %EXIT [ i32 0, label %A ]
+A:
+  %fr1 = freeze i32 %x
+  ret i32 %fr1
+EXIT:
+  %fr2 = freeze i32 %x
+  ret i32 %fr2
+}
+
+define i1 @brcond_noopt(i1 %c, i1 %c2) {
+; CHECK-LABEL: @brcond_noopt(
+; CHECK-NEXT:    [[F:%.*]] = freeze i1 [[C:%.*]]
+; CHECK-NEXT:    call void @f1(i1 [[F]])
+; CHECK-NEXT:    call void @f2()
+; CHECK-NEXT:    br i1 [[C]], label [[A:%.*]], label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    ret i1 false
+; CHECK:       B:
+; CHECK-NEXT:    ret i1 true
+;
+  %f = freeze i1 %c
+  call void @f1(i1 %f) ; cannot optimize i1 %f to %c
+  call void @f2()      ; .. because if f2() exits, `br %c` cannot be reached
+  br i1 %c, label %A, label %B
+A:
+  ret i1 0
+B:
+  ret i1 1
+}
+declare void @f1(i1)
+declare void @f2()