[JumpThreading] Thread through guards

[mkazantsev]

Summary

This patch allows JumpThreading also thread through guards.
Virtually, guard(cond) is equivalent to the following construction:

if (cond) { do something } else {deoptimize}

Yet it is not explicitly converted into IFs before lowering.
This patch enables early threading through guards in simple cases.
Currently it covers the following situation:

if (cond1) {
  // code A
} else {
  // code B
}
// code C
guard(cond2)
// code D

If there is implication cond1 => cond2 or !cond1 => cond2, we can transform
this construction into the following:

if (cond1) {
  // code A
  // code C
} else {
  // code B
  // code C
  guard(cond2)
}
// code D

Thus, removing the guard from one of execution branches.

[sanjoy]

Comments inline.

lib/Transforms/Scalar/JumpThreading.cpp

2053 ↗

(On Diff #87370)

This matching is a bit odd -- how about:

BasicBlock *Pred0, *Pred1;
auto PI = pred_beg(BB), PE = pred_end(BB);
if (PI == PE)
  return false;
Pred0 = *PI++;
if (PI == PE)
  return false;
Pred1 = *PI++;
if (PI != PE)
  return false;

2060 ↗

(On Diff #87370)

I think you also need to check that these preds have only one successor.

2084 ↗

(On Diff #87370)

Let's call these TrueDest and FalseDest. TrueBranch sounds like it is a BranchInst.

2095 ↗

(On Diff #87370)

I'm not sure this is correct if ImpliedTrueBranch is false. By contract, ImpliedTrueBranch being false means: BranchCond ==> NOT(GuardCond), but here you're using it as NOT(BranchCond) ==> GuardCond, which isn't the same thing.

For instance, say BranchCond is A < 10, and GuardCond is A > 20. Then NOT(GuardCond) is A <= 20, and BranchCond ==> NOT(GuardCond). But that does not mean that you can eilde the guard on the false destination of the branch -- on the false destination all you know is NOT(A < 10) == A >= 10, but that's not sufficient to elide a guard on A > 20 since A could be 11.

2104 ↗

(On Diff #87370)

I think we need a cap on how many instructions we duplicate this way.

2110 ↗

(On Diff #87370)

There are certain instructions that cannot be duplicated (see CallInst::cannotDuplicate), so you should bail out if you see one of those here.

2140 ↗

(On Diff #87370)

In a later change, let's add this to Cloning.h with some unit tests of its own.

[mkazantsev]

Preparing fixes.

lib/Transforms/Scalar/JumpThreading.cpp

2060 ↗

(On Diff #87370)

This is not required. Imagine

       A
     /    \
    B      C
  /  \    /  \
D      E       F

Hoisting instructions before guards to split blocks between B-E, C-E looks valid. We don't break any look structures in this case. It is kinda equivalent to splitting E into 2 parts (E1 and E2) and then duplicating E1 to E1a and E1b. As result, we have something like

        A
     /      \
    B         C
  /  \      /  \
D     E1a E1b   F
        \ /
         E2

That looks valid for me. Please let me know if you see a problem in doing so.

2095 ↗

(On Diff #87370)

You're right, it is only valid to do that if BranchCond = NOT(GuardCond). Thanks for noticing this!

[sanjoy]

Looks almost good to go. I have some minor comments.

lib/Transforms/Scalar/JumpThreading.cpp

2060 ↗

(On Diff #87370)

SGTM!

46 ↗

(On Diff #87599)

The general idiom I've seen used in LLVM is to open the PatternMatch namespace in the functions that use it (so for here only JumpThreadingPass::ProcessGuards).

719 ↗

(On Diff #87599)

As an optimization for frontends which do not emit guards, I think we should make this optimization conditional under the Module having a llvm.experimental_guard declaration that has uses (see HasGuards is ScalarEvolution, for instance).

2064 ↗

(On Diff #87599)

Use a range for here for (auto &I : *BB).

2066 ↗

(On Diff #87599)

Can we do these three checks on before we loop over the instructions in BB? If they don't pass then there's no need to look for guards.

if (auto Parent = Pred1->getSinglePredecessor())
  if (Parent == Pred2->getSinglePredecessor())
    if (BranchInst *BI = dyn_cast<BranchInst>(Parent->getTerminator()))

2095 ↗

(On Diff #87599)

Add a /*InvertAPred*/ marker here.

2109 ↗

(On Diff #87599)

Where is BBDupThreshold defined? That needs to be a cl::opt.

2118 ↗

(On Diff #87599)

Right now it is possible for this transform to bail out after cloning some instructions if the first DuplicateInstructionsInSplitBetween passes but the second one fails. I'd restructure this a little differently: I'd first clone GuardedBlock and then UnguardedBlock; with an assert checking that if cloning GuardedBlock was successful, so was UnguardedBlock, since the latter clones fewer instructions.

2131 ↗

(On Diff #87599)

Can we filter out PHI nodes here? That is:

for (auto BI = BB->begin(); &*BI != AfterGuard; ++BI)
  if (!isa<PHINode>(&*BI))
    ToRemove.push_back(&*BI);

2134 ↗

(On Diff #87599)

You can do:

for (auto *Inst : reverse(ToRemove))

2140 ↗

(On Diff #87599)

Stylistically, I'd have preferred NewPN->insertBefore(BB->getFirstInsertionPt()); (with the call to getFirstInsertionPt() hoisted out of the loop to avoid wasted work).

What you have here is correct though, so I'll leave it to you to make a judgement call.

lib/Transforms/Utils/CloneFunction.cpp

751 ↗

(On Diff #87599)

Add a note that (here or in the header) you're not simply dropping PHIs, but are specializing them as necessary. IOW, this function will do the thing you expect with uses of PHI nodes in the cloned instructions.

754 ↗

(On Diff #87599)

This needs a unit test in unittests/Transforms/Utils/Cloning.cpp

765 ↗

(On Diff #87599)

Use isa<> here.

767 ↗

(On Diff #87599)

Use auto *CI: http://llvm.org/docs/CodingStandards.html#beware-unnecessary-copies-with-auto

769 ↗

(On Diff #87599)

I think you need to bail out here on an instruction with uses that returns a value of token type (otherwise you may have to insert PHIs of token type later).

[mkazantsev]

lib/Transforms/Scalar/JumpThreading.cpp

2109 ↗

(On Diff #87599)

It already is, see line 53

static cl::opt<unsigned>
BBDuplicateThreshold("jump-threading-threshold",
          cl::desc("Max block size to duplicate for jump threading"),
          cl::init(6), cl::Hidden);

And then line 67

BBDupThreshold = (T == -1) ? BBDuplicateThreshold : unsigned(T);

It is used in getJumpThreadDuplicationCost calculation. Actually this function does pretty much what we want. I reused it to avoid duplication of its logic.

2118 ↗

(On Diff #87599)

I hoisted instruction count check out of the method and only invoke it for guarded branch.

lib/Transforms/Utils/CloneFunction.cpp

765 ↗

(On Diff #87599)

This code is no more, replaced with calculation function call.

[sanjoy]

lgtm! Checking in.

[reames]

Nice! Two ideas for future enhancements:

1. This should really handle more than two predecessors where the condition is known along some subset of them. Preferably by using the full power of LVI.
2. The organization of this transform would also be applicable to select instructions. Generalizing it to replace the dedicated select logic in this pass would be good. Less code, more testing.

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

2074

minor: using an early return here would be easier to follow

[mkazantsev]

Yes, I plan to make these improvements in follow-up patches in future. Thanks!

[anna]

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

2076

Hi Max, I think you need to check that branch is a conditional branch. Otherwise we can fail while trying to get the condition for the branch in ThreadGuard at line 2091.

[mkazantsev]

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

2076

You're right, I need to add this check here.

[sanjoy]

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

2076

I guess this is possible when Pred1 and Pred2 are the same, like:

Parent:
  br label %pred

pred:
  switch ... 4 -> BB; 5 -> BB; ...

BB:
  ...

Are there other bits in this patch that are wrong in that situation?

[mkazantsev]

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

2076

I think another example could be

Parent:
  br %cond Pred, Pred

Pred:
  br BB

BB
  ...

So I would rather add both checks "branch is conditional" and pred1 != pred2.

[anna]

Patch reverted at https://reviews.llvm.org/rL295200

[sanjoy]

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

2076

I think getSinglePredecessor on Pred will return nullptr in that case. getUniquePredecessor would have returned Parent.

[sanjoy]

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

2076

Also, you would not have had two preds for BB.

[mkazantsev]

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

2076

Agreed. However, in your example the discussed situation doesn't happen as well. The thing is that JumpTheading will merge Parent and pred blocks before it gets to BB and runs into that crash. I will try to construct a test that reproduces the problem.

Anna, do you have a simple test where this crash happens? I'd appreciate if you provided it.

[mkazantsev]

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

2076

I was able to create a test that looks like

define i32 @not_a_diamond1(i32 %a, i1 %cond1) {
  br i1 %cond1, label %Pred, label %Exit
Pred:
  switch i32 %a, label %Exit [
    i32 10, label %Merge
    i32 20, label %Merge
  ]
Merge:
  call void(i1, ...) @llvm.experimental.guard( i1 %cond1 )[ "deopt"() ]
  br label %Exit
Exit:
  ret i32 %a
}

Despite the condition is conditional, here pred1 = pred2, and the test is buggy.

[sanjoy]

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

2076

It is easy to fool JumpThreading's block ordering though, to prevent it from collapsing blocks:

declare void @llvm.experimental.guard(i1, ...)

define void @f(i32 %a, i1 %c) {
entry:
  br label %parent

merge:
  call void(i1, ...) @llvm.experimental.guard(i1 %c)[ "deopt"() ]
  ret void

pred:
  switch i32 %a, label %exit [
    i32 10, label %merge
    i32 20, label %merge
  ]

parent:
  br label %pred

exit:
  ret void
}

on ./bin/opt -jump-threading with @anna 's revert reverted crashes as:

Assertion failed: (isConditional() && "Cannot get condition of an uncond branch!"), function getCondition, file ../../include/llvm/IR/Instructions.h, line 2989.
0  opt                      0x00000001044890bc llvm::sys::PrintStackTrace(llvm::raw_ostream&) + 60
1  opt                      0x0000000104489639 PrintStackTraceSignalHandler(void*) + 25
2  opt                      0x00000001044856a9 llvm::sys::RunSignalHandlers() + 425
3  opt                      0x0000000104489b72 SignalHandler(int) + 354
4  libsystem_platform.dylib 0x00007fffdfc3ebba _sigtramp + 26
5  libsystem_platform.dylib 000000000000000000 _sigtramp + 540808288
6  libsystem_c.dylib        0x00007fffdfac5420 abort + 129
7  libsystem_c.dylib        0x00007fffdfa8c893 basename_r + 0
8  opt                      0x0000000103e82db8 llvm::BranchInst::getCondition() const + 104
9  opt                      0x00000001040d4b39 llvm::JumpThreadingPass::ThreadGuard(llvm::BasicBlock*, llvm::IntrinsicInst*, llvm::BranchInst*) + 105
10 opt                      0x00000001040cd17f llvm::JumpThreadingPass::ProcessGuards(llvm::BasicBlock*) + 479
11 opt                      0x00000001040c8ecd llvm::JumpThreadingPass::ProcessBlock(llvm::BasicBlock*) + 541
12 opt                      0x00000001040c87a7 llvm::JumpThreadingPass::runImpl(llvm::Function&, llvm::TargetLibraryInfo*, llvm::LazyValueInfo*, bool, std::__1::unique_ptr<llvm::BlockFrequencyInfo, std::__1::default_delete<llvm::BlockFrequencyInfo> >, std::__1::unique_ptr<llvm::BranchProbabilityInfo, std::__1::default_delete<llvm::BranchProbabilityInfo> >) + 1959
13 opt                      0x00000001040d5e21 (anonymous namespace)::JumpThreading::runOnFunction(llvm::Function&) +2161

[mkazantsev]

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

2076

Thanks! The fix I've prepared passes both tests. I will add them to the test suite.

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

 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/ValueHandle.h"
 
 namespace llvm {
 
 /// A private "module" namespace for types and utilities used by
 /// JumpThreading.
 /// These are implementation details and should not be used by clients.
 namespace jumpthreading {

 /// revectored to the false side of the second if.
 ///
 class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
   TargetLibraryInfo *TLI;
   LazyValueInfo *LVI;
   std::unique_ptr<BlockFrequencyInfo> BFI;
   std::unique_ptr<BranchProbabilityInfo> BPI;
   bool HasProfileData = false;
+  bool HasGuards = false;
 #ifdef NDEBUG
   SmallPtrSet<const BasicBlock *, 16> LoopHeaders;
 #else
   SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders;
 #endif
   DenseSet<std::pair<Value *, BasicBlock *>> RecursionSet;
 
   unsigned BBDupThreshold;
public:
   bool ProcessBranchOnPHI(PHINode *PN);
   bool ProcessBranchOnXOR(BinaryOperator *BO);
   bool ProcessImpliedCondition(BasicBlock *BB);
 
   bool SimplifyPartiallyRedundantLoad(LoadInst *LI);
   bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
   bool TryToUnfoldSelectInCurrBB(BasicBlock *BB);
 
+  bool ProcessGuards(BasicBlock *BB);
+  bool ThreadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI);
+
 private:
   BasicBlock *SplitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
                               const char *Suffix);
   void UpdateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB,
                                     BasicBlock *NewBB, BasicBlock *SuccBB);
   /// Check if the block has profile metadata for its outgoing edges.
   bool doesBlockHaveProfileData(BasicBlock *BB);
 };
 
 } // end namespace llvm
 
 #endif

llvm/trunk/include/llvm/Transforms/Utils/Cloning.h

Loop *cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB,
                              const Twine &NameSuffix, LoopInfo *LI,
                              DominatorTree *DT,
                              SmallVectorImpl<BasicBlock *> &Blocks);
 
 /// \brief Remaps instructions in \p Blocks using the mapping in \p VMap.
 void remapInstructionsInBlocks(const SmallVectorImpl<BasicBlock *> &Blocks,
                                ValueToValueMapTy &VMap);
 
+/// Split edge between BB and PredBB and duplicate all non-Phi instructions
+/// from BB between its beginning and the StopAt instruction into the split
+/// block. Phi nodes are not duplicated, but their uses are handled correctly:
+/// we replace them with the uses of corresponding Phi inputs. ValueMapping
+/// is used to map the original instructions from BB to their newly-created
+/// copies. Returns the split block.
+BasicBlock *
+DuplicateInstructionsInSplitBetween(BasicBlock *BB, BasicBlock *PredBB,
+                                    Instruction *StopAt,
+                                    ValueToValueMapTy &ValueMapping);
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_CLONING_H

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/Metadata.h"
+#include "llvm/IR/PatternMatch.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 #include <algorithm>
 #include <memory>
 using namespace llvm;
 using namespace jumpthreading;
 
 #define DEBUG_TYPE "jump-threading"
bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
   DEBUG(dbgs() << "Jump threading on function '" << F.getName() << "'\n");
   TLI = TLI_;
   LVI = LVI_;
   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_;
+  auto *GuardDecl = F.getParent()->getFunction(
+      Intrinsic::getName(Intrinsic::experimental_guard));
+  HasGuards = GuardDecl && !GuardDecl->use_empty();
   if (HasProfileData) {
     BPI = std::move(BPI_);
     BFI = std::move(BFI_);
   }
 
   // Remove unreachable blocks from function as they may result in infinite
   // loop. We do threading if we found something profitable. Jump threading a
   // branch can create other opportunities. If these opportunities form a cycle
do {
     }
     EverChanged |= Changed;
   } while (Changed);
 
   LoopHeaders.clear();
   return EverChanged;
 }
 
-/// getJumpThreadDuplicationCost - Return the cost of duplicating this block to
-/// thread across it. Stop scanning the block when passing the threshold.
-static unsigned getJumpThreadDuplicationCost(const BasicBlock *BB,
+/// 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,
+                                             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.
 
   unsigned Bonus = 0;
-  const TerminatorInst *BBTerm = BB->getTerminator();
+  if (BB->getTerminator() == StopAt) {
     // Threading through a switch statement is particularly profitable.  If this
-  // block ends in a switch, decrease its cost to make it more likely to happen.
-  if (isa<SwitchInst>(BBTerm))
+    // block ends in a switch, decrease its cost to make it more likely to
+    // happen.
+    if (isa<SwitchInst>(StopAt))
       Bonus = 6;
 
     // The same holds for indirect branches, but slightly more so.
-  if (isa<IndirectBrInst>(BBTerm))
+    if (isa<IndirectBrInst>(StopAt))
       Bonus = 8;
+  }
 
   // Bump the threshold up so the early exit from the loop doesn't skip the
   // terminator-based Size adjustment at the end.
   Threshold += Bonus;
 
   // Sum up the cost of each instruction until we get to the terminator.  Don't
   // include the terminator because the copy won't include it.
   unsigned Size = 0;
-  for (; !isa<TerminatorInst>(I); ++I) {
+  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;
 
if (!TI->isExceptional() && TI->getNumSuccessors() == 1 &&
 
       return true;
     }
   }
 
   if (TryToUnfoldSelectInCurrBB(BB))
     return true;
 
+  // Look if we can propagate guards to predecessors.
+  if (HasGuards && ProcessGuards(BB))
+    return true;
+
   // 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)) {
bool JumpThreadingPass::ThreadEdge(BasicBlock *BB,
   // See the comments above FindLoopHeaders for justifications and caveats.
   if (LoopHeaders.count(BB)) {
     DEBUG(dbgs() << "  Not threading across loop header BB '" << BB->getName()
           << "' to dest BB '" << SuccBB->getName()
           << "' - it might create an irreducible loop!\n");
     return false;
   }
 
-  unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB, BBDupThreshold);
+  unsigned JumpThreadCost =
+      getJumpThreadDuplicationCost(BB, BB->getTerminator(), BBDupThreshold);
   if (JumpThreadCost > BBDupThreshold) {
     DEBUG(dbgs() << "  Not threading BB '" << BB->getName()
           << "' - Cost is too high: " << JumpThreadCost << "\n");
     return false;
   }
 
   // And finally, do it!  Start by factoring the predecessors if needed.
   BasicBlock *PredBB;
bool JumpThreadingPass::DuplicateCondBranchOnPHIIntoPred(
   // See the comments above FindLoopHeaders for justifications and caveats.
   if (LoopHeaders.count(BB)) {
     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, BBDupThreshold);
+  unsigned DuplicationCost =
+      getJumpThreadDuplicationCost(BB, BB->getTerminator(), BBDupThreshold);
   if (DuplicationCost > BBDupThreshold) {
     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.
   BasicBlock *PredBB;
if (HasConst) {
       SI->replaceAllUsesWith(NewPN);
       SI->eraseFromParent();
       return true;
     }
   }
   
   return false;
 }
+
+/// Try to propagate a guard from the current BB into one of its predecessors
+/// in case if another branch of execution implies that the condition of this
+/// guard is always true. Currently we only process the simplest case that
+/// looks like:
+///
+/// Start:
+///   %cond = ...
+///   br i1 %cond, label %T1, label %F1
+/// T1:
+///   br label %Merge
+/// F1:
+///   br label %Merge
+/// Merge:
+///   %condGuard = ...
+///   call void(i1, ...) @llvm.experimental.guard( i1 %condGuard )[ "deopt"() ]
+///
+/// And cond either implies condGuard or !condGuard. In this case all the
+/// instructions before the guard can be duplicated in both branches, and the
+/// guard is then threaded to one of them.
+bool JumpThreadingPass::ProcessGuards(BasicBlock *BB) {
+  using namespace PatternMatch;
+  // We only want to deal with two predecessors.
+  BasicBlock *Pred1, *Pred2;
+  auto PI = pred_begin(BB), PE = pred_end(BB);
+  if (PI == PE)
+    return false;
+  Pred1 = *PI++;
+  if (PI == PE)
+    return false;
+  Pred2 = *PI++;
+  if (PI != PE)
+    return false;
+
+  // Try to thread one of the guards of the block.
+  // TODO: Look up deeper than to immediate predecessor?
+  if (auto Parent = Pred1->getSinglePredecessor())
+    if (Parent == Pred2->getSinglePredecessor())
+      if (BranchInst *BI = dyn_cast<BranchInst>(Parent->getTerminator()))
+        for (auto &I : *BB)
+          if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>()))
+            if (ThreadGuard(BB, cast<IntrinsicInst>(&I), BI))
+              return true;
+
+  return false;
+}
+
+/// Try to propagate the guard from BB which is the lower block of a diamond
+/// to one of its branches, in case if diamond's condition implies guard's
+/// condition.
+bool JumpThreadingPass::ThreadGuard(BasicBlock *BB, IntrinsicInst *Guard,
+                                    BranchInst *BI) {
+  Value *GuardCond = Guard->getArgOperand(0);
+  Value *BranchCond = BI->getCondition();
+  BasicBlock *TrueDest = BI->getSuccessor(0);
+  BasicBlock *FalseDest = BI->getSuccessor(1);
+
+  auto &DL = BB->getModule()->getDataLayout();
+  bool TrueDestIsSafe = false;
+  bool FalseDestIsSafe = false;
+
+  // True dest is safe if BranchCond => GuardCond.
+  auto Impl = isImpliedCondition(BranchCond, GuardCond, DL);
+  if (Impl && *Impl)
+    TrueDestIsSafe = true;
+  else {
+    // False dest is safe if !BranchCond => GuardCond.
+    Impl =
+        isImpliedCondition(BranchCond, GuardCond, DL, /* InvertAPred */ true);
+    if (Impl && *Impl)
+      FalseDestIsSafe = true;
+  }
+
+  if (!TrueDestIsSafe && !FalseDestIsSafe)
+    return false;
+
+  BasicBlock *UnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;
+  BasicBlock *GuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;
+
+  ValueToValueMapTy UnguardedMapping, GuardedMapping;
+  Instruction *AfterGuard = Guard->getNextNode();
+  unsigned Cost = getJumpThreadDuplicationCost(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.
+  GuardedBlock = DuplicateInstructionsInSplitBetween(
+      BB, GuardedBlock, AfterGuard, GuardedMapping);
+  assert(GuardedBlock && "Could not create the guarded block?");
+  // Duplicate all instructions before the guard in the unguarded branch.
+  // Since we have successfully duplicated the guarded block and this block
+  // has fewer instructions, we expect it to succeed.
+  UnguardedBlock = DuplicateInstructionsInSplitBetween(BB, UnguardedBlock,
+                                                       Guard, UnguardedMapping);
+  assert(UnguardedBlock && "Could not create the unguarded block?");
+  DEBUG(dbgs() << "Moved guard " << *Guard << " to block "
+               << GuardedBlock->getName() << "\n");
+
+  // Some instructions before the guard may still have uses. For them, we need
+  // to create Phi nodes merging their copies in both guarded and unguarded
+  // branches. Those instructions that have no uses can be just removed.
+  SmallVector<Instruction *, 4> ToRemove;
+  for (auto BI = BB->begin(); &*BI != AfterGuard; ++BI)
+    if (!isa<PHINode>(&*BI))
+      ToRemove.push_back(&*BI);
+
+  Instruction *InsertionPoint = &*BB->getFirstInsertionPt();
+  assert(InsertionPoint && "Empty block?");
+  // Substitute with Phis & remove.
+  for (auto *Inst : reverse(ToRemove)) {
+    if (!Inst->use_empty()) {
+      PHINode *NewPN = PHINode::Create(Inst->getType(), 2);
+      NewPN->addIncoming(UnguardedMapping[Inst], UnguardedBlock);
+      NewPN->addIncoming(GuardedMapping[Inst], GuardedBlock);
+      NewPN->insertBefore(InsertionPoint);
+      Inst->replaceAllUsesWith(NewPN);
+    }
+    Inst->eraseFromParent();
+  }
+  return true;
+}

llvm/trunk/lib/Transforms/Utils/CloneFunction.cpp

Loop *llvm::cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB,
   // Move them physically from the end of the block list.
   F->getBasicBlockList().splice(Before->getIterator(), F->getBasicBlockList(),
                                 NewPH);
   F->getBasicBlockList().splice(Before->getIterator(), F->getBasicBlockList(),
                                 NewLoop->getHeader()->getIterator(), F->end());
 
   return NewLoop;
 }
+
+/// \brief Duplicate non-Phi instructions from the beginning of block up to
+/// StopAt instruction into a split block between BB and its predecessor.
+BasicBlock *
+llvm::DuplicateInstructionsInSplitBetween(BasicBlock *BB, BasicBlock *PredBB,
+                                          Instruction *StopAt,
+                                          ValueToValueMapTy &ValueMapping) {
+  // We are going to have to map operands from the original BB block to the new
+  // copy of the block 'NewBB'.  If there are PHI nodes in BB, evaluate them to
+  // account for entry from PredBB.
+  BasicBlock::iterator BI = BB->begin();
+  for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
+    ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB);
+
+  BasicBlock *NewBB = SplitEdge(PredBB, BB);
+  NewBB->setName(PredBB->getName() + ".split");
+  Instruction *NewTerm = NewBB->getTerminator();
+
+  // Clone the non-phi instructions of BB into NewBB, keeping track of the
+  // mapping and using it to remap operands in the cloned instructions.
+  for (; StopAt != &*BI; ++BI) {
+    Instruction *New = BI->clone();
+    New->setName(BI->getName());
+    New->insertBefore(NewTerm);
+    ValueMapping[&*BI] = New;
+
+    // Remap operands to patch up intra-block references.
+    for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
+      if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
+        auto I = ValueMapping.find(Inst);
+        if (I != ValueMapping.end())
+          New->setOperand(i, I->second);
+      }
+  }
+
+  return NewBB;
+}

llvm/trunk/test/Transforms/JumpThreading/guards.ll

+; RUN: opt < %s -jump-threading -dce -S | FileCheck %s
+
+declare void @llvm.experimental.guard(i1, ...)
+
+declare i32 @f1()
+declare i32 @f2()
+
+define i32 @branch_implies_guard(i32 %a) {
+; CHECK-LABEL: @branch_implies_guard(
+  %cond = icmp slt i32 %a, 10
+  br i1 %cond, label %T1, label %F1
+
+T1:
+; CHECK:       T1.split
+; CHECK:         %v1 = call i32 @f1()
+; CHECK-NEXT:    %retVal
+; CHECK-NEXT:    br label %Merge
+  %v1 = call i32 @f1()
+  br label %Merge
+
+F1:
+; CHECK:       F1.split
+; CHECK:         %v2 = call i32 @f2()
+; CHECK-NEXT:    %retVal
+; CHECK-NEXT:    %condGuard
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %condGuard
+; CHECK-NEXT:    br label %Merge
+  %v2 = call i32 @f2()
+  br label %Merge
+
+Merge:
+; CHECK:       Merge
+; CHECK-NOT:     call void(i1, ...) @llvm.experimental.guard(
+  %retPhi = phi i32 [ %v1, %T1 ], [ %v2, %F1 ]
+  %retVal = add i32 %retPhi, 10
+  %condGuard = icmp slt i32 %a, 20
+  call void(i1, ...) @llvm.experimental.guard( i1 %condGuard )[ "deopt"() ]
+  ret i32 %retVal
+}
+
+define i32 @not_branch_implies_guard(i32 %a) {
+; CHECK-LABEL: @not_branch_implies_guard(
+  %cond = icmp slt i32 %a, 20
+  br i1 %cond, label %T1, label %F1
+
+T1:
+; CHECK:       T1.split:
+; CHECK-NEXT:    %v1 = call i32 @f1()
+; CHECK-NEXT:    %retVal
+; CHECK-NEXT:    %condGuard
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %condGuard
+; CHECK-NEXT:    br label %Merge
+  %v1 = call i32 @f1()
+  br label %Merge
+
+F1:
+; CHECK:       F1.split:
+; CHECK-NEXT:   %v2 = call i32 @f2()
+; CHECK-NEXT:   %retVal
+; CHECK-NEXT:   br label %Merge
+  %v2 = call i32 @f2()
+  br label %Merge
+
+Merge:
+; CHECK:       Merge
+; CHECK-NOT:     call void(i1, ...) @llvm.experimental.guard(
+  %retPhi = phi i32 [ %v1, %T1 ], [ %v2, %F1 ]
+  %retVal = add i32 %retPhi, 10
+  %condGuard = icmp sgt i32 %a, 10
+  call void(i1, ...) @llvm.experimental.guard( i1 %condGuard )[ "deopt"() ]
+  ret i32 %retVal
+}
+
+define i32 @branch_overlaps_guard(i32 %a) {
+; CHECK-LABEL: @branch_overlaps_guard(
+  %cond = icmp slt i32 %a, 20
+  br i1 %cond, label %T1, label %F1
+
+T1:
+; CHECK:        T1:
+; CHECK-NEXT:      %v1 = call i32 @f1()
+; CHECK-NEXT:      br label %Merge
+  %v1 = call i32 @f1()
+  br label %Merge
+
+F1:
+; CHECK:        F1:
+; CHECK-NEXT:     %v2 = call i32 @f2()
+; CHECK-NEXT:     br label %Merge
+  %v2 = call i32 @f2()
+  br label %Merge
+
+Merge:
+; CHECK:       Merge
+; CHECK:         %condGuard = icmp slt i32 %a, 10
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %condGuard) [ "deopt"() ]
+  %retPhi = phi i32 [ %v1, %T1 ], [ %v2, %F1 ]
+  %retVal = add i32 %retPhi, 10
+  %condGuard = icmp slt i32 %a, 10
+  call void(i1, ...) @llvm.experimental.guard( i1 %condGuard )[ "deopt"() ]
+  ret i32 %retVal
+}
+
+define i32 @branch_doesnt_overlap_guard(i32 %a) {
+; CHECK-LABEL: @branch_doesnt_overlap_guard(
+  %cond = icmp slt i32 %a, 10
+  br i1 %cond, label %T1, label %F1
+
+T1:
+; CHECK:        T1:
+; CHECK-NEXT:      %v1 = call i32 @f1()
+; CHECK-NEXT:      br label %Merge
+  %v1 = call i32 @f1()
+  br label %Merge
+
+F1:
+; CHECK:        F1:
+; CHECK-NEXT:     %v2 = call i32 @f2()
+; CHECK-NEXT:     br label %Merge
+  %v2 = call i32 @f2()
+  br label %Merge
+
+Merge:
+; CHECK:       Merge
+; CHECK:         %condGuard = icmp sgt i32 %a, 20
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %condGuard) [ "deopt"() ]
+  %retPhi = phi i32 [ %v1, %T1 ], [ %v2, %F1 ]
+  %retVal = add i32 %retPhi, 10
+  %condGuard = icmp sgt i32 %a, 20
+  call void(i1, ...) @llvm.experimental.guard( i1 %condGuard )[ "deopt"() ]
+  ret i32 %retVal
+}

llvm/trunk/unittests/Transforms/Utils/Cloning.cpp

TEST_F(CloneInstruction, CallingConvention) {
 
   CloneFunctionInto(F2, F1, VMap, false, Returns);
   EXPECT_EQ(CallingConv::Cold, F2->getCallingConv());
 
   delete F1;
   delete F2;
 }
 
+TEST_F(CloneInstruction, DuplicateInstructionsToSplit) {
+  Type *ArgTy1[] = {Type::getInt32PtrTy(context)};
+  FunctionType *FT = FunctionType::get(Type::getVoidTy(context), ArgTy1, false);
+  V = new Argument(Type::getInt32Ty(context));
+
+  Function *F = Function::Create(FT, Function::ExternalLinkage);
+
+  BasicBlock *BB1 = BasicBlock::Create(context, "", F);
+  IRBuilder<> Builder1(BB1);
+
+  BasicBlock *BB2 = BasicBlock::Create(context, "", F);
+  IRBuilder<> Builder2(BB2);
+
+  Builder1.CreateBr(BB2);
+
+  Instruction *AddInst = cast<Instruction>(Builder2.CreateAdd(V, V));
+  Instruction *MulInst = cast<Instruction>(Builder2.CreateMul(AddInst, V));
+  Instruction *SubInst = cast<Instruction>(Builder2.CreateSub(MulInst, V));
+  Builder2.CreateRetVoid();
+
+  ValueToValueMapTy Mapping;
+
+  auto Split = DuplicateInstructionsInSplitBetween(BB2, BB1, SubInst, Mapping);
+
+  EXPECT_TRUE(Split);
+  EXPECT_EQ(Mapping.size(), 2u);
+  EXPECT_TRUE(Mapping.find(AddInst) != Mapping.end());
+  EXPECT_TRUE(Mapping.find(MulInst) != Mapping.end());
+
+  auto AddSplit = dyn_cast<Instruction>(Mapping[AddInst]);
+  EXPECT_TRUE(AddSplit);
+  EXPECT_EQ(AddSplit->getOperand(0), V);
+  EXPECT_EQ(AddSplit->getOperand(1), V);
+  EXPECT_EQ(AddSplit->getParent(), Split);
+
+  auto MulSplit = dyn_cast<Instruction>(Mapping[MulInst]);
+  EXPECT_TRUE(MulSplit);
+  EXPECT_EQ(MulSplit->getOperand(0), AddSplit);
+  EXPECT_EQ(MulSplit->getOperand(1), V);
+  EXPECT_EQ(MulSplit->getParent(), Split);
+
+  EXPECT_EQ(AddSplit->getNextNode(), MulSplit);
+  EXPECT_EQ(MulSplit->getNextNode(), Split->getTerminator());
+
+  delete F;
+}
+
 class CloneFunc : public ::testing::Test {
 protected:
   void SetUp() override {
     SetupModule();
     CreateOldFunc();
     CreateNewFunc();
     SetupFinder();
   }