[JumpThreading] Fix an incorrect Modified status

[dstenb]

Summary

This fixes PR47297.

When ProcessBlock() was able to constant fold the terminator's
condition, but not do any more transformations, the function would
return false, which would lead to the JumpThreading pass returning an
incorrect modified status. This patch makes so that ProcessBlock()
returns true in such cases. This will trigger an unnecessary invocation
of ProcessBlock() in such cases, but this should be rare to occur.

This was caught using the check introduced by D80916.

[efriedma]

I assume that we in such cases don't want to return true from ProcessBlock(), which would trigger another iteration of the function.

Theoretically, it's unnecessary, so we'd want to avoid it the extra analysis cost. But in practice this should be really rare, so I'd prefer to keep the code simpler and continue using a bool return.

[dstenb]

Continue using a bool return instead of a tri-state.

[efriedma]

LGTM

[dstenb]

Thanks for the review!

And for reference, I compiled 100,000 Csmith programs for x86-64 and I only ran into this case 15 times.

llvm/include/llvm/Transforms/Scalar/JumpThreading.h

public:
 
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   void releaseMemory() {
     BFI.reset();
     BPI.reset();
   }
 
+  enum class ProcessBlockResult {
+    Unmodified,
+    Modified,
+    Threaded,
+  };
+
   void FindLoopHeaders(Function &F);
-  bool ProcessBlock(BasicBlock *BB);
+  ProcessBlockResult ProcessBlock(BasicBlock *BB);
   bool MaybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB);
   void UpdateSSA(BasicBlock *BB, BasicBlock *NewBB,
                  DenseMap<Instruction *, Value *> &ValueMapping);
   DenseMap<Instruction *, Value *> CloneInstructions(BasicBlock::iterator BI,
                                                      BasicBlock::iterator BE,
                                                      BasicBlock *NewBB,
                                                      BasicBlock *PredBB);
   bool TryThreadEdge(BasicBlock *BB,

llvm/lib/Transforms/Scalar/JumpThreading.cpp

bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
 
   bool EverChanged = false;
   bool Changed;
   do {
     Changed = false;
     for (auto &BB : F) {
       if (Unreachable.count(&BB))
         continue;
-      while (ProcessBlock(&BB)) // Thread all of the branches we can over BB.
-        Changed = true;
+      // Thread all of the branches we can over BB.
+      ProcessBlockResult Result;
+      do {
+        Result = ProcessBlock(&BB);
+        Changed |= Result != ProcessBlockResult::Unmodified;
+      } while (Result == ProcessBlockResult::Threaded);
 
       // Jump threading may have introduced redundant debug values into BB
       // which should be removed.
       if (Changed)
         RemoveRedundantDbgInstrs(&BB);
 
       // Stop processing BB if it's the entry or is now deleted. The following
       // routines attempt to eliminate BB and locating a suitable replacement
static bool hasAddressTakenAndUsed(BasicBlock *BB) {
   // hanging off of it.  These shouldn't keep the block alive.
   BlockAddress *BA = BlockAddress::get(BB);
   BA->removeDeadConstantUsers();
   return !BA->use_empty();
 }
 
 /// ProcessBlock - If there are any predecessors whose control can be threaded
 /// through to a successor, transform them now.
-bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) {
+JumpThreadingPass::ProcessBlockResult
+JumpThreadingPass::ProcessBlock(BasicBlock *BB) {
   // If the block is trivially dead, just return and let the caller nuke it.
   // This simplifies other transformations.
   if (DTU->isBBPendingDeletion(BB) ||
       (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()))
-    return false;
+    return ProcessBlockResult::Unmodified;
 
   // If this block has a single predecessor, and if that pred has a single
   // successor, merge the blocks.  This encourages recursive jump threading
   // because now the condition in this block can be threaded through
   // predecessors of our predecessor block.
   if (MaybeMergeBasicBlockIntoOnlyPred(BB))
-    return true;
+    return ProcessBlockResult::Threaded;
 
   if (TryToUnfoldSelectInCurrBB(BB))
-    return true;
+    return ProcessBlockResult::Threaded;
 
   // Look if we can propagate guards to predecessors.
   if (HasGuards && ProcessGuards(BB))
-    return true;
+    return ProcessBlockResult::Threaded;
 
   // What kind of constant we're looking for.
   ConstantPreference Preference = WantInteger;
 
   // Look to see if the terminator is a conditional branch, switch or indirect
   // branch, if not we can't thread it.
   Value *Condition;
   Instruction *Terminator = BB->getTerminator();
   if (BranchInst *BI = dyn_cast<BranchInst>(Terminator)) {
     // Can't thread an unconditional jump.
-    if (BI->isUnconditional()) return false;
+    if (BI->isUnconditional())
+      return ProcessBlockResult::Unmodified;
     Condition = BI->getCondition();
   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(Terminator)) {
     Condition = SI->getCondition();
   } else if (IndirectBrInst *IB = dyn_cast<IndirectBrInst>(Terminator)) {
     // Can't thread indirect branch with no successors.
-    if (IB->getNumSuccessors() == 0) return false;
+    if (IB->getNumSuccessors() == 0)
+      return ProcessBlockResult::Unmodified;
     Condition = IB->getAddress()->stripPointerCasts();
     Preference = WantBlockAddress;
   } else {
-    return false; // Must be an invoke or callbr.
+    return ProcessBlockResult::Unmodified; // Must be an invoke or callbr.
   }
 
+  // Keep track if we constant folded the condition in this invocation.
+  bool ConstantFolded = false;
+
   // Run constant folding to see if we can reduce the condition to a simple
   // constant.
   if (Instruction *I = dyn_cast<Instruction>(Condition)) {
     Value *SimpleVal =
         ConstantFoldInstruction(I, BB->getModule()->getDataLayout(), TLI);
     if (SimpleVal) {
       I->replaceAllUsesWith(SimpleVal);
       if (isInstructionTriviallyDead(I, TLI))
         I->eraseFromParent();
       Condition = SimpleVal;
+      ConstantFolded = true;
     }
   }
 
   // If the terminator is branching on an undef or freeze undef, we can pick any
   // of the successors to branch to.  Let GetBestDestForJumpOnUndef decide.
   auto *FI = dyn_cast<FreezeInst>(Condition);
   if (isa<UndefValue>(Condition) ||
       (FI && isa<UndefValue>(FI->getOperand(0)) && FI->hasOneUse())) {
if (isa<UndefValue>(Condition) ||
 
     LLVM_DEBUG(dbgs() << "  In block '" << BB->getName()
                       << "' folding undef terminator: " << *BBTerm << '\n');
     BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm);
     BBTerm->eraseFromParent();
     DTU->applyUpdatesPermissive(Updates);
     if (FI)
       FI->eraseFromParent();
-    return true;
+    return ProcessBlockResult::Threaded;
   }
 
   // If the terminator of this block is branching on a constant, simplify the
   // terminator to an unconditional branch.  This can occur due to threading in
   // other blocks.
   if (getKnownConstant(Condition, Preference)) {
     LLVM_DEBUG(dbgs() << "  In block '" << BB->getName()
                       << "' folding terminator: " << *BB->getTerminator()
                       << '\n');
     ++NumFolds;
     ConstantFoldTerminator(BB, true, nullptr, DTU);
-    return true;
+    return ProcessBlockResult::Threaded;
   }
 
   Instruction *CondInst = dyn_cast<Instruction>(Condition);
 
   // All the rest of our checks depend on the condition being an instruction.
   if (!CondInst) {
     // FIXME: Unify this with code below.
     if (ProcessThreadableEdges(Condition, BB, Preference, Terminator))
-      return true;
-    return false;
+      return ProcessBlockResult::Threaded;
+    return ConstantFolded ? ProcessBlockResult::Modified
+                          : ProcessBlockResult::Unmodified;
   }
 
   if (CmpInst *CondCmp = dyn_cast<CmpInst>(CondInst)) {
     // If we're branching on a conditional, LVI might be able to determine
     // it's value at the branch instruction.  We only handle comparisons
     // against a constant at this time.
     // TODO: This should be extended to handle switches as well.
     BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
if (CondBr && CondConst) {
         else if (CondCmp->getParent() == BB) {
           auto *CI = Ret == LazyValueInfo::True ?
             ConstantInt::getTrue(CondCmp->getType()) :
             ConstantInt::getFalse(CondCmp->getType());
           ReplaceFoldableUses(CondCmp, CI);
         }
         DTU->applyUpdatesPermissive(
             {{DominatorTree::Delete, BB, ToRemoveSucc}});
-        return true;
+        return ProcessBlockResult::Threaded;
       }
 
       // We did not manage to simplify this branch, try to see whether
       // CondCmp depends on a known phi-select pattern.
       if (TryToUnfoldSelect(CondCmp, BB))
-        return true;
+        return ProcessBlockResult::Threaded;
     }
   }
 
   if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator()))
     if (TryToUnfoldSelect(SI, BB))
-      return true;
+      return ProcessBlockResult::Threaded;
 
   // Check for some cases that are worth simplifying.  Right now we want to look
   // for loads that are used by a switch or by the condition for the branch.  If
   // we see one, check to see if it's partially redundant.  If so, insert a PHI
   // which can then be used to thread the values.
   Value *SimplifyValue = CondInst;
 
   if (auto *FI = dyn_cast<FreezeInst>(SimplifyValue))
     // Look into freeze's operand
     SimplifyValue = FI->getOperand(0);
 
   if (CmpInst *CondCmp = dyn_cast<CmpInst>(SimplifyValue))
     if (isa<Constant>(CondCmp->getOperand(1)))
       SimplifyValue = CondCmp->getOperand(0);
 
   // TODO: There are other places where load PRE would be profitable, such as
   // more complex comparisons.
   if (LoadInst *LoadI = dyn_cast<LoadInst>(SimplifyValue))
     if (SimplifyPartiallyRedundantLoad(LoadI))
-      return true;
+      return ProcessBlockResult::Threaded;
 
   // Before threading, try to propagate profile data backwards:
   if (PHINode *PN = dyn_cast<PHINode>(CondInst))
     if (PN->getParent() == BB && isa<BranchInst>(BB->getTerminator()))
       updatePredecessorProfileMetadata(PN, BB);
 
   // Handle a variety of cases where we are branching on something derived from
   // a PHI node in the current block.  If we can prove that any predecessors
   // compute a predictable value based on a PHI node, thread those predecessors.
   if (ProcessThreadableEdges(CondInst, BB, Preference, Terminator))
-    return true;
+    return ProcessBlockResult::Threaded;
 
   // If this is an otherwise-unfoldable branch on a phi node or freeze(phi) in
   // the current block, see if we can simplify.
   PHINode *PN = dyn_cast<PHINode>(
       isa<FreezeInst>(CondInst) ? cast<FreezeInst>(CondInst)->getOperand(0)
                                 : CondInst);
 
   if (PN && PN->getParent() == BB && isa<BranchInst>(BB->getTerminator()))
-    return ProcessBranchOnPHI(PN);
+    return ProcessBranchOnPHI(PN) ? ProcessBlockResult::Threaded
+                                  : ProcessBlockResult::Unmodified;
 
   // If this is an otherwise-unfoldable branch on a XOR, see if we can simplify.
   if (CondInst->getOpcode() == Instruction::Xor &&
       CondInst->getParent() == BB && isa<BranchInst>(BB->getTerminator()))
-    return ProcessBranchOnXOR(cast<BinaryOperator>(CondInst));
+    return ProcessBranchOnXOR(cast<BinaryOperator>(CondInst))
+               ? ProcessBlockResult::Threaded
+               : ProcessBlockResult::Unmodified;
 
   // Search for a stronger dominating condition that can be used to simplify a
   // conditional branch leaving BB.
   if (ProcessImpliedCondition(BB))
-    return true;
+    return ProcessBlockResult::Threaded;
 
-  return false;
+  return ProcessBlockResult::Unmodified;
 }
 
 bool JumpThreadingPass::ProcessImpliedCondition(BasicBlock *BB) {
   auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
   if (!BI || !BI->isConditional())
     return false;
 
   Value *Cond = BI->getCondition();

llvm/test/Transforms/JumpThreading/constant-fold-status.ll

+; RUN: opt -jump-threading < %s -S -o - | FileCheck %s
+
+; Reproducer for PR47297.
+
+; The pass did previously not report a correct Modified status in the case
+; where a terminator's condition was successfully constant folded, but there
+; were no other transformations done. This was caught by the pass return
+; status check that is hidden under EXPENSIVE_CHECKS.
+
+; CHECK-LABEL: entry:
+; CHECK-NEXT: br i1 icmp eq (i32 ptrtoint (i16* @a to i32), i32 0), label %overflow, label %cont
+
+@a = internal global i16 0
+
+define void @foo(i16 %d) {
+entry:
+  %.not = icmp eq i16 zext (i1 icmp ne (i32 ptrtoint (i16* @a to i32), i32 0) to i16), 0
+  br i1 %.not, label %overflow, label %cont
+
+overflow:                                         ; preds = %entry
+  call void @bar()
+  br label %cont
+
+cont:                                             ; preds = %overflow, %entry
+  ret void
+}
+
+declare void @bar()