[JumpThreading] Ignore free instructions

[nikic]

Summary

This is basically D108837 but for jump threading. Free instructions should be ignored for the threading decision. JumpThreading already skips some free instructions (like pointer bitcasts), but does not skip various free intrinsics -- in fact, it currently gives them a fairly large cost of 2.

[lebedev.ri]

If desired, I could reduce this patch to just the TCC_Free check though.

Yes, please.

[nikic]

Only check TCC_Free, otherwise keep previous cost model.

[lebedev.ri]

This LG.

I can see why it may be good to migrate to proper TTI costs here,
but the main question that raises are:

1. in -Oz, should we be checking codesize cost?
2. Changing heuristics will obviously affect optimization power. What does this does to the budget? Should we increase it to retain most of the current optimization power?

[hans]

This caused compiler crash when building Chromium. See https://bugs.chromium.org/p/chromium/issues/detail?id=1252762#c8 for a reproducer, and the top of that bug for the stack dump.

I've reverted in 4604695d7c20e72b551a1a5224f3de877cb41bd3 in the meantime.

[nikic]

@hans Do I understand correctly that this change was mistakenly reverted and can be reapplied now that the DSE issue is fixed?

[hans]

In D110290#3021030, @nikic wrote:

@hans Do I understand correctly that this change was mistakenly reverted and can be reapplied now that the DSE issue is fixed?

Yes, it looks like the DSE change was the real issue. Sorry for the noise. I'll re-apply this one unless you beat me to it.

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

 class Instruction;
 class IntrinsicInst;
 class LazyValueInfo;
 class LoadInst;
 class PHINode;
 class SelectInst;
 class SwitchInst;
 class TargetLibraryInfo;
+class TargetTransformInfo;
 class Value;
 
 /// A private "module" namespace for types and utilities used by
 /// JumpThreading.
 /// These are implementation details and should not be used by clients.
 namespace jumpthreading {
 
 // These are at global scope so static functions can use them too.

 ///     X = 4;
 ///   }
 ///   if (X < 3) {
 ///
 /// In this case, the unconditional branch at the end of the first if can be
 /// revectored to the false side of the second if.
 class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
   TargetLibraryInfo *TLI;
+  TargetTransformInfo *TTI;
   LazyValueInfo *LVI;
   AAResults *AA;
   DomTreeUpdater *DTU;
   std::unique_ptr<BlockFrequencyInfo> BFI;
   std::unique_ptr<BranchProbabilityInfo> BPI;
   bool HasProfileData = false;
   bool HasGuards = false;
 #ifndef LLVM_ENABLE_ABI_BREAKING_CHECKS
   SmallPtrSet<const BasicBlock *, 16> LoopHeaders;
 #else
   SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders;
 #endif
 
   unsigned BBDupThreshold;
   unsigned DefaultBBDupThreshold;
   bool InsertFreezeWhenUnfoldingSelect;
 
 public:
   JumpThreadingPass(bool InsertFreezeWhenUnfoldingSelect = false, int T = -1);
 
   // Glue for old PM.
-  bool runImpl(Function &F, TargetLibraryInfo *TLI, LazyValueInfo *LVI,
-               AAResults *AA, DomTreeUpdater *DTU, bool HasProfileData,
-               std::unique_ptr<BlockFrequencyInfo> BFI,
+  bool runImpl(Function &F, TargetLibraryInfo *TLI, TargetTransformInfo *TTI,
+               LazyValueInfo *LVI, AAResults *AA, DomTreeUpdater *DTU,
+               bool HasProfileData, std::unique_ptr<BlockFrequencyInfo> BFI,
                std::unique_ptr<BranchProbabilityInfo> BPI);
 
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   void releaseMemory() {
     BFI.reset();
     BPI.reset();
   }

llvm/lib/Transforms/Scalar/JumpThreading.cpp

bool JumpThreading::runOnFunction(Function &F) {
   std::unique_ptr<BlockFrequencyInfo> BFI;
   std::unique_ptr<BranchProbabilityInfo> BPI;
   if (F.hasProfileData()) {
     LoopInfo LI{DominatorTree(F)};
     BPI.reset(new BranchProbabilityInfo(F, LI, TLI));
     BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
   }
 
-  bool Changed = Impl.runImpl(F, TLI, LVI, AA, &DTU, F.hasProfileData(),
+  bool Changed = Impl.runImpl(F, TLI, TTI, LVI, AA, &DTU, F.hasProfileData(),
                               std::move(BFI), std::move(BPI));
   if (PrintLVIAfterJumpThreading) {
     dbgs() << "LVI for function '" << F.getName() << "':\n";
     LVI->printLVI(F, DTU.getDomTree(), dbgs());
   }
   return Changed;
 }
 
PreservedAnalyses JumpThreadingPass::run(Function &F,
   std::unique_ptr<BlockFrequencyInfo> BFI;
   std::unique_ptr<BranchProbabilityInfo> BPI;
   if (F.hasProfileData()) {
     LoopInfo LI{DominatorTree(F)};
     BPI.reset(new BranchProbabilityInfo(F, LI, &TLI));
     BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
   }
 
-  bool Changed = runImpl(F, &TLI, &LVI, &AA, &DTU, F.hasProfileData(),
+  bool Changed = runImpl(F, &TLI, &TTI, &LVI, &AA, &DTU, F.hasProfileData(),
                          std::move(BFI), std::move(BPI));
 
   if (PrintLVIAfterJumpThreading) {
     dbgs() << "LVI for function '" << F.getName() << "':\n";
     LVI.printLVI(F, DTU.getDomTree(), dbgs());
   }
 
   if (!Changed)
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<LazyValueAnalysis>();
   return PA;
 }
 
 bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
-                                LazyValueInfo *LVI_, AliasAnalysis *AA_,
-                                DomTreeUpdater *DTU_, bool HasProfileData_,
+                                TargetTransformInfo *TTI_, LazyValueInfo *LVI_,
+                                AliasAnalysis *AA_, DomTreeUpdater *DTU_,
+                                bool HasProfileData_,
                                 std::unique_ptr<BlockFrequencyInfo> BFI_,
                                 std::unique_ptr<BranchProbabilityInfo> BPI_) {
   LLVM_DEBUG(dbgs() << "Jump threading on function '" << F.getName() << "'\n");
   TLI = TLI_;
+  TTI = TTI_;
   LVI = LVI_;
   AA = AA_;
   DTU = DTU_;
   BFI.reset();
   BPI.reset();
   // When profile data is available, we need to update edge weights after
   // successful jump threading, which requires both BPI and BFI being available.
   HasProfileData = HasProfileData_;
static void replaceFoldableUses(Instruction *Cond, Value *ToVal) {
   }
   if (Cond->use_empty() && !Cond->mayHaveSideEffects())
     Cond->eraseFromParent();
 }
 
 /// Return the cost of duplicating a piece of this block from first non-phi
 /// and before StopAt instruction to thread across it. Stop scanning the block
 /// when exceeding the threshold. If duplication is impossible, returns ~0U.
-static unsigned getJumpThreadDuplicationCost(BasicBlock *BB,
+static unsigned getJumpThreadDuplicationCost(const TargetTransformInfo *TTI,
+                                             BasicBlock *BB,
                                              Instruction *StopAt,
                                              unsigned Threshold) {
   assert(StopAt->getParent() == BB && "Not an instruction from proper BB?");
   /// Ignore PHI nodes, these will be flattened when duplication happens.
   BasicBlock::const_iterator I(BB->getFirstNonPHI());
 
   // FIXME: THREADING will delete values that are just used to compute the
   // branch, so they shouldn't count against the duplication cost.
static unsigned getJumpThreadDuplicationCost(const TargetTransformInfo *TTI,
   // include the terminator because the copy won't include it.
   unsigned Size = 0;
   for (; &*I != StopAt; ++I) {
 
     // Stop scanning the block if we've reached the threshold.
     if (Size > Threshold)
       return Size;
 
-    // Debugger intrinsics don't incur code size.
-    if (isa<DbgInfoIntrinsic>(I)) continue;
-
-    // Pseudo-probes don't incur code size.
-    if (isa<PseudoProbeInst>(I))
-      continue;
-
-    // If this is a pointer->pointer bitcast, it is free.
-    if (isa<BitCastInst>(I) && I->getType()->isPointerTy())
-      continue;
-
-    // Freeze instruction is free, too.
-    if (isa<FreezeInst>(I))
-      continue;
-
     // Bail out if this instruction gives back a token type, it is not possible
     // to duplicate it if it is used outside this BB.
     if (I->getType()->isTokenTy() && I->isUsedOutsideOfBlock(BB))
       return ~0U;
 
+    // Blocks with NoDuplicate are modelled as having infinite cost, so they
+    // are never duplicated.
+    if (const CallInst *CI = dyn_cast<CallInst>(I))
+      if (CI->cannotDuplicate() || CI->isConvergent())
+        return ~0U;
+
+    if (TTI->getUserCost(&*I, TargetTransformInfo::TCK_SizeAndLatency)
+            == TargetTransformInfo::TCC_Free)
+      continue;
+
     // All other instructions count for at least one unit.
     ++Size;
 
     // Calls are more expensive.  If they are non-intrinsic calls, we model them
     // as having cost of 4.  If they are a non-vector intrinsic, we model them
     // as having cost of 2 total, and if they are a vector intrinsic, we model
     // them as having cost 1.
     if (const CallInst *CI = dyn_cast<CallInst>(I)) {
-      if (CI->cannotDuplicate() || CI->isConvergent())
-        // Blocks with NoDuplicate are modelled as having infinite cost, so they
-        // are never duplicated.
-        return ~0U;
-      else if (!isa<IntrinsicInst>(CI))
+      if (!isa<IntrinsicInst>(CI))
         Size += 3;
       else if (!CI->getType()->isVectorTy())
         Size += 1;
     }
   }
 
   return Size > Bonus ? Size - Bonus : 0;
 }
LLVM_DEBUG({
              << (SuccIsHeader ? "loop header BB '" : "block BB '")
              << SuccBB->getName()
              << "' - it might create an irreducible loop!\n";
     });
     return false;
   }
 
   // Compute the cost of duplicating BB and PredBB.
-  unsigned BBCost =
-      getJumpThreadDuplicationCost(BB, BB->getTerminator(), BBDupThreshold);
+  unsigned BBCost = getJumpThreadDuplicationCost(
+      TTI, BB, BB->getTerminator(), BBDupThreshold);
   unsigned PredBBCost = getJumpThreadDuplicationCost(
-      PredBB, PredBB->getTerminator(), BBDupThreshold);
+      TTI, PredBB, PredBB->getTerminator(), BBDupThreshold);
 
   // Give up if costs are too high.  We need to check BBCost and PredBBCost
   // individually before checking their sum because getJumpThreadDuplicationCost
   // return (unsigned)~0 for those basic blocks that cannot be duplicated.
   if (BBCost > BBDupThreshold || PredBBCost > BBDupThreshold ||
       BBCost + PredBBCost > BBDupThreshold) {
     LLVM_DEBUG(dbgs() << "  Not threading BB '" << BB->getName()
                       << "' - Cost is too high: " << PredBBCost
LLVM_DEBUG({
       dbgs() << "  Not threading across "
           << (BBIsHeader ? "loop header BB '" : "block BB '") << BB->getName()
           << "' to dest " << (SuccIsHeader ? "loop header BB '" : "block BB '")
           << SuccBB->getName() << "' - it might create an irreducible loop!\n";
     });
     return false;
   }
 
-  unsigned JumpThreadCost =
-      getJumpThreadDuplicationCost(BB, BB->getTerminator(), BBDupThreshold);
+  unsigned JumpThreadCost = getJumpThreadDuplicationCost(
+      TTI, BB, BB->getTerminator(), BBDupThreshold);
   if (JumpThreadCost > BBDupThreshold) {
     LLVM_DEBUG(dbgs() << "  Not threading BB '" << BB->getName()
                       << "' - Cost is too high: " << JumpThreadCost << "\n");
     return false;
   }
 
   threadEdge(BB, PredBBs, SuccBB);
   return true;
bool JumpThreadingPass::duplicateCondBranchOnPHIIntoPred(
   // See the comments above findLoopHeaders for justifications and caveats.
   if (LoopHeaders.count(BB)) {
     LLVM_DEBUG(dbgs() << "  Not duplicating loop header '" << BB->getName()
                       << "' into predecessor block '" << PredBBs[0]->getName()
                       << "' - it might create an irreducible loop!\n");
     return false;
   }
 
-  unsigned DuplicationCost =
-      getJumpThreadDuplicationCost(BB, BB->getTerminator(), BBDupThreshold);
+  unsigned DuplicationCost = getJumpThreadDuplicationCost(
+      TTI, BB, BB->getTerminator(), BBDupThreshold);
   if (DuplicationCost > BBDupThreshold) {
     LLVM_DEBUG(dbgs() << "  Not duplicating BB '" << BB->getName()
                       << "' - Cost is too high: " << DuplicationCost << "\n");
     return false;
   }
 
   // And finally, do it!  Start by factoring the predecessors if needed.
   std::vector<DominatorTree::UpdateType> Updates;
bool JumpThreadingPass::threadGuard(BasicBlock *BB, IntrinsicInst *Guard,
   if (!TrueDestIsSafe && !FalseDestIsSafe)
     return false;
 
   BasicBlock *PredUnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;
   BasicBlock *PredGuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;
 
   ValueToValueMapTy UnguardedMapping, GuardedMapping;
   Instruction *AfterGuard = Guard->getNextNode();
-  unsigned Cost = getJumpThreadDuplicationCost(BB, AfterGuard, BBDupThreshold);
+  unsigned Cost =
+      getJumpThreadDuplicationCost(TTI, BB, AfterGuard, BBDupThreshold);
   if (Cost > BBDupThreshold)
     return false;
   // Duplicate all instructions before the guard and the guard itself to the
   // branch where implication is not proved.
   BasicBlock *GuardedBlock = DuplicateInstructionsInSplitBetween(
       BB, PredGuardedBlock, AfterGuard, GuardedMapping, *DTU);
   assert(GuardedBlock && "Could not create the guarded block?");
   // Duplicate all instructions before the guard in the unguarded branch.

llvm/test/Transforms/JumpThreading/free_instructions.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -jump-threading -jump-threading-threshold=3 < %s | FileCheck %s
 
 ; TODO: In this test case, only the stores in %join should cound towards
 ; the jump threading threshold, as everything else are free instructions.
 define i32 @free_instructions(i1 %c, i32* %p) {
 ; CHECK-LABEL: @free_instructions(
-; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF:%.*]], label [[ELSE:%.*]]
-; CHECK:       if:
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF2:%.*]], label [[ELSE2:%.*]]
+; CHECK:       if2:
 ; CHECK-NEXT:    store i32 -1, i32* [[P:%.*]], align 4
-; CHECK-NEXT:    br label [[JOIN:%.*]]
-; CHECK:       else:
-; CHECK-NEXT:    store i32 -2, i32* [[P]], align 4
-; CHECK-NEXT:    br label [[JOIN]]
-; CHECK:       join:
 ; CHECK-NEXT:    call void @llvm.experimental.noalias.scope.decl(metadata [[META0:![0-9]+]])
 ; CHECK-NEXT:    store i32 1, i32* [[P]], align 4, !noalias !0
 ; CHECK-NEXT:    call void @llvm.assume(i1 true) [ "align"(i32* [[P]], i64 32) ]
 ; CHECK-NEXT:    store i32 2, i32* [[P]], align 4
+; CHECK-NEXT:    [[P21:%.*]] = bitcast i32* [[P]] to i8*
+; CHECK-NEXT:    [[P32:%.*]] = call i8* @llvm.launder.invariant.group.p0i8(i8* [[P21]])
+; CHECK-NEXT:    [[P43:%.*]] = bitcast i8* [[P32]] to i32*
+; CHECK-NEXT:    store i32 3, i32* [[P43]], align 4, !invariant.group !3
+; CHECK-NEXT:    ret i32 0
+; CHECK:       else2:
+; CHECK-NEXT:    store i32 -2, i32* [[P]], align 4
+; CHECK-NEXT:    call void @llvm.experimental.noalias.scope.decl(metadata [[META4:![0-9]+]])
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4, !noalias !4
+; CHECK-NEXT:    call void @llvm.assume(i1 true) [ "align"(i32* [[P]], i64 32) ]
+; CHECK-NEXT:    store i32 2, i32* [[P]], align 4
 ; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P]] to i8*
 ; CHECK-NEXT:    [[P3:%.*]] = call i8* @llvm.launder.invariant.group.p0i8(i8* [[P2]])
 ; CHECK-NEXT:    [[P4:%.*]] = bitcast i8* [[P3]] to i32*
 ; CHECK-NEXT:    store i32 3, i32* [[P4]], align 4, !invariant.group !3
-; CHECK-NEXT:    br i1 [[C]], label [[IF2:%.*]], label [[ELSE2:%.*]]
-; CHECK:       if2:
-; CHECK-NEXT:    ret i32 0
-; CHECK:       else2:
 ; CHECK-NEXT:    ret i32 1
 ;
   br i1 %c, label %if, label %else
 
 if:
   store i32 -1, i32* %p
   br label %join
 

llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll

 ; ASSUMPTIONS-OFF-NEXT:    store volatile i64 -1, i64* [[PTR]], align 4
 ; ASSUMPTIONS-OFF-NEXT:    store volatile i64 [[DOTSINK]], i64* [[PTR]], align 4
 ; ASSUMPTIONS-OFF-NEXT:    ret void
 ; ASSUMPTIONS-OFF:       false2:
 ; ASSUMPTIONS-OFF-NEXT:    store volatile i64 1, i64* [[PTR]], align 4
 ; ASSUMPTIONS-OFF-NEXT:    br label [[COMMON_RET]]
 ;
 ; ASSUMPTIONS-ON-LABEL: @caller1(
-; ASSUMPTIONS-ON-NEXT:    br i1 [[C:%.*]], label [[COMMON_RET:%.*]], label [[FALSE1:%.*]]
-; ASSUMPTIONS-ON:       false1:
-; ASSUMPTIONS-ON-NEXT:    store volatile i64 1, i64* [[PTR:%.*]], align 4
-; ASSUMPTIONS-ON-NEXT:    br label [[COMMON_RET]]
+; ASSUMPTIONS-ON-NEXT:    br i1 [[C:%.*]], label [[COMMON_RET:%.*]], label [[FALSE2:%.*]]
 ; ASSUMPTIONS-ON:       common.ret:
-; ASSUMPTIONS-ON-NEXT:    [[DOTSINK:%.*]] = phi i64 [ 3, [[FALSE1]] ], [ 2, [[TMP0:%.*]] ]
-; ASSUMPTIONS-ON-NEXT:    call void @llvm.assume(i1 true) [ "align"(i64* [[PTR]], i64 8) ]
+; ASSUMPTIONS-ON-NEXT:    [[DOTSINK:%.*]] = phi i64 [ 3, [[FALSE2]] ], [ 2, [[TMP0:%.*]] ]
+; ASSUMPTIONS-ON-NEXT:    call void @llvm.assume(i1 true) [ "align"(i64* [[PTR:%.*]], i64 8) ]
 ; ASSUMPTIONS-ON-NEXT:    store volatile i64 0, i64* [[PTR]], align 8
 ; ASSUMPTIONS-ON-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
 ; ASSUMPTIONS-ON-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
 ; ASSUMPTIONS-ON-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
 ; ASSUMPTIONS-ON-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
 ; ASSUMPTIONS-ON-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
 ; ASSUMPTIONS-ON-NEXT:    store volatile i64 [[DOTSINK]], i64* [[PTR]], align 8
 ; ASSUMPTIONS-ON-NEXT:    ret void
+; ASSUMPTIONS-ON:       false2:
+; ASSUMPTIONS-ON-NEXT:    store volatile i64 1, i64* [[PTR]], align 4
+; ASSUMPTIONS-ON-NEXT:    br label [[COMMON_RET]]
 ;
   br i1 %c, label %true1, label %false1
 
 true1:
   %c2 = call i1 @callee1(i1 %c, i64* %ptr)
   store volatile i64 -1, i64* %ptr
   store volatile i64 -1, i64* %ptr
   store volatile i64 -1, i64* %ptr