New pass: guard widening

[sanjoy]

Summary

Implement guard widening in LLVM. Description from GuardWidening.cpp:

The semantics of the @llvm.experimental.guard intrinsic lets LLVM
transform it so that it fails more often that it did before the
transform. This optimization is called "widening" and can be used hoist
and common runtime checks in situations like these:

%cmp0 = 7 u< Length
call @llvm.experimental.guard(i1 %cmp0) [ "deopt"(...) ]
call @unknown_side_effects()
%cmp1 = 9 u< Length
call @llvm.experimental.guard(i1 %cmp1) [ "deopt"(...) ]
...

to

%cmp0 = 9 u< Length
call @llvm.experimental.guard(i1 %cmp0) [ "deopt"(...) ]
call @unknown_side_effects()
...

If %cmp0 is false, @llvm.experimental.guard will "deoptimize" back
to a generic implementation of the same function, which will have the
correct semantics from that point onward. It is always _legal_ to
deoptimize (so replacing %cmp0 with false is "correct"), though it may
not always be profitable to do so.

[reames]

A few initial comments mostly looking at the test cases. I'll take a look at the actual code separately.

My meta concern here is that I think you're trying to be way too aggressive here. "One pass to rule them all" is not generally a good approach. I suspect that smaller changes to InstCombine, EarlyCSE, GVN, and LICM would end up covering most of the interesting cases. Even if we decide to go with a single check widening pass, I'd prefer to see it start dead simple and evolve.

test/Transforms/GuardWidening/basic.ll

26 ↗

(On Diff #56840)

Add a check not to show the second one being removed.

42 ↗

(On Diff #56840)

Did you mean trivial here? An icmp is pretty easy to move around...

97 ↗

(On Diff #56840)

Doing this here feels weird. This should be an addition to loop unswitching or possibly even LICM itself.

121 ↗

(On Diff #56840)

Note sure what you're getting at here. The branch condition could still correlate. Are you assuming healing? If so, comment.

166 ↗

(On Diff #56840)

Wait what? A would absolutely expect cond_1 and cond_2 to be combined here. Why would I ever want to not do that?

[sanjoy]

In D20143#426695, @reames wrote:

A few initial comments mostly looking at the test cases. I'll take a look at the actual code separately.

My meta concern here is that I think you're trying to be way too aggressive here. "One pass to rule them all" is not generally a good approach. I suspect that smaller changes to InstCombine, EarlyCSE, GVN, and LICM would end up covering most of the interesting cases. Even if we decide to go with a single check widening pass, I'd prefer to see it start dead simple and evolve.

I'd say the pass in its current form is already fairly simple (~200 LOC, if you don't count the administrative overhead). There may be more optimal ways of spreading out the logic across other passes, but before I do that I want to be clear about what works and what doesn't, from a performance standpoint. Having a separate pass also lets me avoid making other passes pay the compile-time costs associated with widening (e.g. if I wanted to do cross-block widening in GVN/EarlyCSE, I'd have to compute the post-dom tree and loop info in GVN/EarlyCSE, something it doesn't do today).

test/Transforms/GuardWidening/basic.ll

26 ↗

(On Diff #56840)

Will do.

42 ↗

(On Diff #56840)

No, I did mean "non-trivial" (with "trivial" meaning "nothing needs to be moved"), but I see why that can sound weird. I'll s/non-trivial/trivial/ :)

97 ↗

(On Diff #56840)

This bit falls out of the cost/benefit logic we already have. We can consider doing better / more nuanced version of widening in LICM and LoopUnswitch if needed.

121 ↗

(On Diff #56840)

Yes, I've assumed healing (not yet implemented); will add a comment.

166 ↗

(On Diff #56840)

cond_1 and cond_2 are (intentionally) volatile loads, so you cannot hoist the computation producing cond_2 to before the first guard (and hence can't widen the first one to check cond_1).

[majnemer]

lib/Transforms/Scalar/GuardWidening.cpp

81–95 ↗

(On Diff #56840)

Your enum is defined in a class, I think you can forgo the WS prefix if you'd like.

185–186 ↗

(On Diff #56840)

match(&I, m_Intrinsic<Intrinsic::experimental_guard>()) ?

357–358 ↗

(On Diff #56840)

Is this saving anything over BinaryOperator::CreateAnd(Cond0, Cond1, "wide.chk", InsertPt);?

[sanjoy]

• Address review

[sanjoy]

Realized I had an unsubmitted comment

lib/Transforms/Scalar/GuardWidening.cpp

81–95 ↗

(On Diff #56840)

I think I'll keep it for now, it reads a little better when I use it without qualification.

[atrick]

I did a fairly quick review. Your pass looks pretty great.

I don't like to see unbounded recursion through multiple operands:

+ return all_of(Inst->operands(), [&](Value *Op) {
+ return isAvailableAt(Op, Loc);
+ });

...having had to fix many of these problems in LLVM when a
pathological case leads to exponential compile time. As a rule, I
think you either need a very small limit on the recursion, or a
visited set.

You're evaluating every guard against all dominating guard intrinsics:

+ for (unsigned i = 0, e = DFSI.getPathLength(); i != e; ++i) {
+ const auto &GuardsInCurBB = GuardsInBlock.find(CurBB)->second;
+ auto I = GuardsInCurBB.begin();
+ auto E = GuardsInCurBB.end();
+ for (auto *Candidate : make_range(I, E)) {

It's a nice simple design, but I wonder how well it scales (with
massive inlining). Since you're only matching guards with the same LHS
cmp operand, you could use a scoped hashtable instead. That way most
guards don't need to be searched. OTOH you would be maintaining a
complex side data structure.

[sanjoy]

In D20143#431592, @atrick wrote:

I did a fairly quick review. Your pass looks pretty great.

I don't like to see unbounded recursion through multiple operands:

+ return all_of(Inst->operands(), [&](Value *Op) {
+ return isAvailableAt(Op, Loc);
+ });

...having had to fix many of these problems in LLVM when a
pathological case leads to exponential compile time. As a rule, I
think you either need a very small limit on the recursion, or a
visited set.

For now I'll add a cap on the recursion. This is something I expect
to revisit once I have this running over Real Code(TM).

You're evaluating every guard against all dominating guard intrinsics:

+ for (unsigned i = 0, e = DFSI.getPathLength(); i != e; ++i) {
+ const auto &GuardsInCurBB = GuardsInBlock.find(CurBB)->second;
+ auto I = GuardsInCurBB.begin();
+ auto E = GuardsInCurBB.end();
+ for (auto *Candidate : make_range(I, E)) {

It's a nice simple design, but I wonder how well it scales (with
massive inlining). Since you're only matching guards with the same LHS

Honestly, I suspect it won't scale very well. My priority now is to run some
real world code through this, and get a stronger sense of what
matters; and use that information to help drive improvements here.

cmp operand, you could use a scoped hashtable instead. That way most
guards don't need to be searched. OTOH you would be maintaining a
complex side data structure.

[reames]

include/llvm/Transforms/Scalar/GuardWidening.h

12 ↗

(On Diff #56953)

You should expand this comment. Specifically, clarify exceptions around re-execution and healing.

Actually, never mind. This is available in the source.

lib/Transforms/Scalar/GuardWidening.cpp

120 ↗

(On Diff #56953)

Interface wise, this might be clearer as returning an optional<Value*> or just a Value* which can be null.

126 ↗

(On Diff #56953)

Generating extra IR just for checking profitability seems less than idea. Could this be combined into a single function which does the replacement if profitable and nothing otherwise?

213 ↗

(On Diff #56953)

Please add an assert that curBB has been populated in GuardsInBlock. Your lazy population scheme is fine, but the code doesn't make it *obvious* that's it correct.

225 ↗

(On Diff #56953)

You have an assumption here that the guards are recorded in the order they appeared in the original basic block. Please document that near the definition of the data structure.

229 ↗

(On Diff #56953)

As far as I understand it, there is never a case where widening one pair of guards would prevent you from merging that widened guard into another. You code is structured as if this is a possibility and it results in excessive generality.

The excess generality here is causing you to implement an O(G^2) algorithm for something which should be a collection of a O(N) algorithms. This is unacceptable.

253 ↗

(On Diff #56953)

In general, you *should* be able to simply delete the second guard here. The fact you can't, indicates there's a problem with the algorithm you've chosen.

287 ↗

(On Diff #56953)

This really seems likely to be excessive generality again. You don't need a generic hoisting algorithm.

300 ↗

(On Diff #56953)

Buggy in the face of unreachable code:
%a = add i32 %a, 1

358 ↗

(On Diff #56953)

Is there possibly a missing return here?

[reames]

Sanjoy and I talked about this one offline and I wanted to highlight a key point which is not obvious from the review thread:

This code is not intended to be long term solution to guard widening. This is essentially an experimental piece of code whose purposes is to inform what real optimization passes need to be extended to handle the majority of cases which arrive in practice. It was deliberately designed to be simple and effective at the cost of compile time.

My own review was from the perspective of this being a "real" optimization pass. I don't know if we have a history of landing and evolving such experimental pieces of code in tree. I certainly wouldn't feel comfortable approving such a thing since I have a clear conflict of interest, but I'm also not opposed to the notion either.

What do others think? Is having a pass that is expected to be experimental and unlikely to survive in its current form in tree a good idea?

[atrick]

IMO this seems as good a form as any for being in-tree, and I think it makes sense to have in-tree given that it's really part of the implementation of the guard intrinsic. You could "hide" the code in other passes, but it's still specific to your compiler until others start using the intrinsic. This way, the experimental feature is self-contained.

Also, I'm curious how integrating it with other passes would actually improve the compile time.

If you're talking about adding this pass to the standard pipeline, that's a different story.

[sanjoy]

The non- O(n^2) bits have been addressed. As discussed above, there still is pending work to make this scale well with production ready workloads (I've noted this in the pass itself).

lib/Transforms/Scalar/GuardWidening.cpp

120 ↗

(On Diff #56953)

That won't work (the return value does not indicate if Result was set) -- there really are two independent results.

126 ↗

(On Diff #56953)

It doesn't generate extra IR if InsertPt is nullptr.

225 ↗

(On Diff #56953)

That was obvious at the construction site, so I've added an assert here.

300 ↗

(On Diff #56953)

Added an assert.

358 ↗

(On Diff #56953)

No, we're falling through to the return false; below.

[sanjoy]

• Address review comments

[atrick]

For the record, even for an experimental pass, I'm objecting to O(2^n) recursion not O(n^2).

[sanjoy]

• Address review: add a fairly low cutoff to makeAvailableAt
• Fix a missing check on Index in the assert checking that GuardsInCurBB is in order

[atrick]

That really is a low threshold :) LLVM likes to use #6 to limit search depth in other places.

[sanjoy]

In D20143#432381, @atrick wrote:

That really is a low threshold :) LLVM likes to use #6 to limit search depth in other places.

I'd say it is sufficient for now; I'll bump it a bit higher if needed later, or do something more targeted (e.g. only hoist icmp's and arithmetic, since that's the only bits the rest of the pass can handle).

[chandlerc]

In D20143#431619, @reames wrote:

Sanjoy and I talked about this one offline and I wanted to highlight a key point which is not obvious from the review thread:

This code is not intended to be long term solution to guard widening. This is essentially an experimental piece of code whose purposes is to inform what real optimization passes need to be extended to handle the majority of cases which arrive in practice. It was deliberately designed to be simple and effective at the cost of compile time.

My own review was from the perspective of this being a "real" optimization pass. I don't know if we have a history of landing and evolving such experimental pieces of code in tree. I certainly wouldn't feel comfortable approving such a thing since I have a clear conflict of interest, but I'm also not opposed to the notion either.

What do others think? Is having a pass that is expected to be experimental and unlikely to survive in its current form in tree a good idea?

I think this is fine. We have several passes in-tree that are not realistic passes to add to the default pipeline:

• reg2mem
• mem2reg
• bb-vectorize

Probably others that I'm forgetting. Some of these are testing or experimentation passes. Some are prototypes that help us understand a problem. I think bb-vectorize is a great example of this. Maybe it doesn't fit the cost model for the majority of targets and/or users, or the compile time hit is just too significant, but it teaches us about how to do non-loop vectorization and is valuable to have in tree IMO as a consequence.

I'm perfectly happy with this pass going in in just such a fashion. I would carefully document at the top of the file and elsewhere that this is *not* intended to be a practical or production-ready pass, but is intended to somewhat brute force expose opportunities to make it clear where we should focus other efforts.

-Chandler

[chandlerc]

In D20143#432389, @sanjoy wrote:

In D20143#432381, @atrick wrote:

That really is a low threshold :) LLVM likes to use #6 to limit search depth in other places.

I'd say it is sufficient for now; I'll bump it a bit higher if needed later, or do something more targeted (e.g. only hoist icmp's and arithmetic, since that's the only bits the rest of the pass can handle).

Personally, I find it odd that you don't want a set as opposed to a limit...

(Peanut gallery comment -- shouldn't impact the progress of the patch)

[atrick]

With SmallPtrSet you don't have to worry much about the overhead of the visited set. But I understand keeping the code super simple in situations like this when you're really just pattern matching your bounds checks.

[sanjoy]

Just to make the picture I have in my head explicit, ideally, the path forward will be:

1. Figure out what cases actually matter in practice
2. Write test cases for those, and add logic as needed

Repeat (1) and (2) till we think we have adequate coverage.

3. Trim down the brute-force O(N^2) algorithm to something nicer while still making sure we get the important cases

[sanjoy]

Use ptrset to avoid exponential behavior, and add test case for it.

(The motivation being that I very quickly ran into a case where a
hoisting threshold of 2 was too small :) )

[reames]

LGTM given the previous discussion about this being an experimental pass.

lib/Transforms/Scalar/GuardWidening.cpp

37 ↗

(On Diff #57689)

Extend: In particular, it is known to have O(N^2) running time and will not scale to large numbers of guards.

llvm/trunk/include/llvm/InitializePasses.h

 void initializeEfficiencySanitizerPass(PassRegistry&);
 void initializeScalarizerPass(PassRegistry&);
 void initializeEarlyCSELegacyPassPass(PassRegistry &);
 void initializeEliminateAvailableExternallyLegacyPassPass(PassRegistry &);
 void initializeExpandISelPseudosPass(PassRegistry&);
 void initializeForceFunctionAttrsLegacyPassPass(PassRegistry&);
 void initializeGCMachineCodeAnalysisPass(PassRegistry&);
 void initializeGCModuleInfoPass(PassRegistry&);
+void initializeGuardWideningLegacyPassPass(PassRegistry&);
 void initializeGVNLegacyPassPass(PassRegistry&);
 void initializeGlobalDCELegacyPassPass(PassRegistry&);
 void initializeGlobalOptLegacyPassPass(PassRegistry&);
 void initializeGlobalsAAWrapperPassPass(PassRegistry&);
 void initializeIPCPPass(PassRegistry&);
 void initializeIPSCCPLegacyPassPass(PassRegistry &);
 void initializeIVUsersPass(PassRegistry&);
 void initializeIfConverterPass(PassRegistry&);

llvm/trunk/include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createPGOIndirectCallPromotionLegacyPass();
       (void) llvm::createInstrProfilingLegacyPass();
       (void) llvm::createFunctionImportPass();
       (void) llvm::createFunctionInliningPass();
       (void) llvm::createAlwaysInlinerPass();
       (void) llvm::createGlobalDCEPass();
       (void) llvm::createGlobalOptimizerPass();
       (void) llvm::createGlobalsAAWrapperPass();
+      (void) llvm::createGuardWideningPass();
       (void) llvm::createIPConstantPropagationPass();
       (void) llvm::createIPSCCPPass();
       (void) llvm::createInductiveRangeCheckEliminationPass();
       (void) llvm::createIndVarSimplifyPass();
       (void) llvm::createInstructionCombiningPass();
       (void) llvm::createInternalizePass();
       (void) llvm::createLCSSAPass();
       (void) llvm::createLICMPass();

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

 //===----------------------------------------------------------------------===//
 //
 // AggressiveDCE - This pass uses the SSA based Aggressive DCE algorithm.  This
 // algorithm assumes instructions are dead until proven otherwise, which makes
 // it more successful are removing non-obviously dead instructions.
 //
 FunctionPass *createAggressiveDCEPass();
 
+
+//===----------------------------------------------------------------------===//
+//
+// GuardWidening - An optimization over the @llvm.experimental.guard intrinsic
+// that (optimistically) combines multiple guards into one to have fewer checks
+// at runtime.
+//
+FunctionPass *createGuardWideningPass();
+
+
 //===----------------------------------------------------------------------===//
 //
 // BitTrackingDCE - This pass uses a bit-tracking DCE algorithm in order to
 // remove computations of dead bits.
 //
 FunctionPass *createBitTrackingDCEPass();
 
 //===----------------------------------------------------------------------===//

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

+//===- GuardWidening.h - ----------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Guard widening is an optimization over the @llvm.experimental.guard intrinsic
+// that (optimistically) combines multiple guards into one to have fewer checks
+// at runtime.
+//
+//===----------------------------------------------------------------------===//
+
+
+#ifndef LLVM_TRANSFORMS_SCALAR_GUARD_WIDENING_H
+#define LLVM_TRANSFORMS_SCALAR_GUARD_WIDENING_H
+
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+class Function;
+
+struct GuardWideningPass : public PassInfoMixin<GuardWideningPass> {
+  PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM);
+};
+}
+
+
+#endif  // LLVM_TRANSFORMS_SCALAR_GUARD_WIDENING_H

llvm/trunk/lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/IPO/StripDeadPrototypes.h"
 #include "llvm/Transforms/InstCombine/InstCombine.h"
 #include "llvm/Transforms/InstrProfiling.h"
 #include "llvm/Transforms/PGOInstrumentation.h"
 #include "llvm/Transforms/Scalar/ADCE.h"
 #include "llvm/Transforms/Scalar/DCE.h"
 #include "llvm/Transforms/Scalar/DeadStoreElimination.h"
 #include "llvm/Transforms/Scalar/EarlyCSE.h"
+#include "llvm/Transforms/Scalar/GuardWidening.h"
 #include "llvm/Transforms/Scalar/GVN.h"
 #include "llvm/Transforms/Scalar/LoopRotation.h"
 #include "llvm/Transforms/Scalar/LoopSimplifyCFG.h"
 #include "llvm/Transforms/Scalar/LowerAtomic.h"
 #include "llvm/Transforms/Scalar/LowerExpectIntrinsic.h"
 #include "llvm/Transforms/Scalar/Reassociate.h"
 #include "llvm/Transforms/Scalar/SCCP.h"
 #include "llvm/Transforms/Scalar/SROA.h"

llvm/trunk/lib/Passes/PassRegistry.def

 FUNCTION_PASS("dce", DCEPass())
 FUNCTION_PASS("dse", DSEPass())
 FUNCTION_PASS("early-cse", EarlyCSEPass())
 FUNCTION_PASS("instcombine", InstCombinePass())
 FUNCTION_PASS("invalidate<all>", InvalidateAllAnalysesPass())
 FUNCTION_PASS("no-op-function", NoOpFunctionPass())
 FUNCTION_PASS("loweratomic", LowerAtomicPass())
 FUNCTION_PASS("lower-expect", LowerExpectIntrinsicPass())
+FUNCTION_PASS("guard-widening", GuardWideningPass())
 FUNCTION_PASS("gvn", GVN())
 FUNCTION_PASS("print", PrintFunctionPass(dbgs()))
 FUNCTION_PASS("print<assumptions>", AssumptionPrinterPass(dbgs()))
 FUNCTION_PASS("print<block-freq>", BlockFrequencyPrinterPass(dbgs()))
 FUNCTION_PASS("print<branch-prob>", BranchProbabilityPrinterPass(dbgs()))
 FUNCTION_PASS("print<domtree>", DominatorTreePrinterPass(dbgs()))
 FUNCTION_PASS("print<postdomtree>", PostDominatorTreePrinterPass(dbgs()))
 FUNCTION_PASS("print<demanded-bits>", DemandedBitsPrinterPass(dbgs()))

llvm/trunk/lib/Transforms/Scalar/CMakeLists.txt

 add_llvm_library(LLVMScalarOpts
   ADCE.cpp
   AlignmentFromAssumptions.cpp
   BDCE.cpp
   ConstantHoisting.cpp
   ConstantProp.cpp
   CorrelatedValuePropagation.cpp
   DCE.cpp
   DeadStoreElimination.cpp
   EarlyCSE.cpp
   FlattenCFGPass.cpp
   Float2Int.cpp
+  GuardWidening.cpp
   GVN.cpp
   InductiveRangeCheckElimination.cpp
   IndVarSimplify.cpp
   JumpThreading.cpp
   LICM.cpp
   LoadCombine.cpp
   LoopDeletion.cpp
   LoopDataPrefetch.cpp

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

+//===- GuardWidening.cpp - ---- Guard widening ----------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the guard widening pass.  The semantics of the
+// @llvm.experimental.guard intrinsic lets LLVM transform it so that it fails
+// more often that it did before the transform.  This optimization is called
+// "widening" and can be used hoist and common runtime checks in situations like
+// these:
+//
+//    %cmp0 = 7 u< Length
+//    call @llvm.experimental.guard(i1 %cmp0) [ "deopt"(...) ]
+//    call @unknown_side_effects()
+//    %cmp1 = 9 u< Length
+//    call @llvm.experimental.guard(i1 %cmp1) [ "deopt"(...) ]
+//    ...
+//
+// =>
+//
+//    %cmp0 = 9 u< Length
+//    call @llvm.experimental.guard(i1 %cmp0) [ "deopt"(...) ]
+//    call @unknown_side_effects()
+//    ...
+//
+// If %cmp0 is false, @llvm.experimental.guard will "deoptimize" back to a
+// generic implementation of the same function, which will have the correct
+// semantics from that point onward.  It is always _legal_ to deoptimize (so
+// replacing %cmp0 with false is "correct"), though it may not always be
+// profitable to do so.
+//
+// NB! This pass is a work in progress.  It hasn't been tuned to be "production
+// ready" yet.  It is known to have quadriatic running time and will not scale
+// to large numbers of guards
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Scalar/GuardWidening.h"
+#include "llvm/Pass.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/PatternMatch.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Transforms/Scalar.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "guard-widening"
+
+namespace {
+
+class GuardWideningImpl {
+  DominatorTree &DT;
+  PostDominatorTree &PDT;
+  LoopInfo &LI;
+
+  /// The set of guards whose conditions have been widened into dominating
+  /// guards.
+  SmallVector<IntrinsicInst *, 16> EliminatedGuards;
+
+  /// The set of guards which have been widened to include conditions to other
+  /// guards.
+  DenseSet<IntrinsicInst *> WidenedGuards;
+
+  /// Try to eliminate guard \p Guard by widening it into an earlier dominating
+  /// guard.  \p DFSI is the DFS iterator on the dominator tree that is
+  /// currently visiting the block containing \p Guard, and \p GuardsPerBlock
+  /// maps BasicBlocks to the set of guards seen in that block.
+  bool eliminateGuardViaWidening(
+      IntrinsicInst *Guard, const df_iterator<DomTreeNode *> &DFSI,
+      const DenseMap<BasicBlock *, SmallVector<IntrinsicInst *, 8>> &
+          GuardsPerBlock);
+
+  /// Used to keep track of which widening potential is more effective.
+  enum WideningScore {
+    /// Don't widen.
+    WS_IllegalOrNegative,
+
+    /// Widening is performance neutral as far as the cycles spent in check
+    /// conditions goes (but can still help, e.g., code layout, having less
+    /// deopt state).
+    WS_Neutral,
+
+    /// Widening is profitable.
+    WS_Positive,
+
+    /// Widening is very profitable.  Not significantly different from \c
+    /// WS_Positive, except by the order.
+    WS_VeryPositive
+  };
+
+  static StringRef scoreTypeToString(WideningScore WS);
+
+  /// Compute the score for widening the condition in \p DominatedGuard
+  /// (contained in \p DominatedGuardLoop) into \p DominatingGuard (contained in
+  /// \p DominatingGuardLoop).
+  WideningScore computeWideningScore(IntrinsicInst *DominatedGuard,
+                                     Loop *DominatedGuardLoop,
+                                     IntrinsicInst *DominatingGuard,
+                                     Loop *DominatingGuardLoop);
+
+  /// Helper to check if \p V can be hoisted to \p InsertPos.
+  bool isAvailableAt(Value *V, Instruction *InsertPos) {
+    SmallPtrSet<Instruction *, 8> Visited;
+    return isAvailableAt(V, InsertPos, Visited);
+  }
+
+  bool isAvailableAt(Value *V, Instruction *InsertPos,
+                     SmallPtrSetImpl<Instruction *> &Visited);
+
+  /// Helper to hoist \p V to \p InsertPos.  Guaranteed to succeed if \c
+  /// isAvailableAt returned true.
+  void makeAvailableAt(Value *V, Instruction *InsertPos);
+
+  /// Common helper used by \c widenGuard and \c isWideningCondProfitable.  Try
+  /// to generate an expression computing the logical AND of \p Cond0 and \p
+  /// Cond1.  Return true if the expression computing the AND is only as
+  /// expensive as computing one of the two. If \p InsertPt is true then
+  /// actually generate the resulting expression, make it available at \p
+  /// InsertPt and return it in \p Result (else no change to the IR is made).
+  bool widenCondCommon(Value *Cond0, Value *Cond1, Instruction *InsertPt,
+                       Value *&Result);
+
+  /// Can we compute the logical AND of \p Cond0 and \p Cond1 for the price of
+  /// computing only one of the two expressions?
+  bool isWideningCondProfitable(Value *Cond0, Value *Cond1) {
+    Value *ResultUnused;
+    return widenCondCommon(Cond0, Cond1, /*InsertPt=*/nullptr, ResultUnused);
+  }
+
+  /// Widen \p ToWiden to fail if \p NewCondition is false (in addition to
+  /// whatever it is already checking).
+  void widenGuard(IntrinsicInst *ToWiden, Value *NewCondition) {
+    Value *Result;
+    widenCondCommon(ToWiden->getArgOperand(0), NewCondition, ToWiden, Result);
+    ToWiden->setArgOperand(0, Result);
+  }
+
+public:
+  explicit GuardWideningImpl(DominatorTree &DT, PostDominatorTree &PDT,
+                             LoopInfo &LI)
+      : DT(DT), PDT(PDT), LI(LI) {}
+
+  /// The entry point for this pass.
+  bool run();
+};
+
+struct GuardWideningLegacyPass : public FunctionPass {
+  static char ID;
+  GuardWideningPass Impl;
+
+  GuardWideningLegacyPass() : FunctionPass(ID) {
+    initializeGuardWideningLegacyPassPass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnFunction(Function &F) override {
+    if (skipFunction(F))
+      return false;
+    return GuardWideningImpl(
+               getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
+               getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree(),
+               getAnalysis<LoopInfoWrapperPass>().getLoopInfo()).run();
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesCFG();
+    AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addRequired<PostDominatorTreeWrapperPass>();
+    AU.addRequired<LoopInfoWrapperPass>();
+  }
+};
+
+}
+
+bool GuardWideningImpl::run() {
+  using namespace llvm::PatternMatch;
+
+  DenseMap<BasicBlock *, SmallVector<IntrinsicInst *, 8>> GuardsInBlock;
+  bool Changed = false;
+
+  for (auto DFI = df_begin(DT.getRootNode()), DFE = df_end(DT.getRootNode());
+       DFI != DFE; ++DFI) {
+    auto *BB = (*DFI)->getBlock();
+    auto &CurrentList = GuardsInBlock[BB];
+
+    for (auto &I : *BB)
+      if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>()))
+        CurrentList.push_back(cast<IntrinsicInst>(&I));
+
+    for (auto *II : CurrentList)
+      Changed |= eliminateGuardViaWidening(II, DFI, GuardsInBlock);
+  }
+
+  for (auto *II : EliminatedGuards)
+    if (!WidenedGuards.count(II))
+      II->eraseFromParent();
+
+  return Changed;
+}
+
+bool GuardWideningImpl::eliminateGuardViaWidening(
+    IntrinsicInst *GuardInst, const df_iterator<DomTreeNode *> &DFSI,
+    const DenseMap<BasicBlock *, SmallVector<IntrinsicInst *, 8>> &
+        GuardsInBlock) {
+  IntrinsicInst *BestSoFar = nullptr;
+  auto BestScoreSoFar = WS_IllegalOrNegative;
+  auto *GuardInstLoop = LI.getLoopFor(GuardInst->getParent());
+
+  // In the set of dominating guards, find the one we can merge GuardInst with
+  // for the most profit.
+  for (unsigned i = 0, e = DFSI.getPathLength(); i != e; ++i) {
+    auto *CurBB = DFSI.getPath(i)->getBlock();
+    auto *CurLoop = LI.getLoopFor(CurBB);
+    assert(GuardsInBlock.count(CurBB) && "Must have been populated by now!");
+    const auto &GuardsInCurBB = GuardsInBlock.find(CurBB)->second;
+
+    auto I = GuardsInCurBB.begin();
+    auto E = GuardsInCurBB.end();
+
+#ifndef NDEBUG
+    {
+      unsigned Index = 0;
+      for (auto &I : *CurBB) {
+        if (Index == GuardsInCurBB.size())
+          break;
+        if (GuardsInCurBB[Index] == &I)
+          Index++;
+      }
+      assert(Index == GuardsInCurBB.size() &&
+             "Guards expected to be in order!");
+    }
+#endif
+
+    assert((i == (e - 1)) == (GuardInst->getParent() == CurBB) && "Bad DFS?");
+
+    if (i == (e - 1)) {
+      // Corner case: make sure we're only looking at guards strictly dominating
+      // GuardInst when visiting GuardInst->getParent().
+      auto NewEnd = std::find(I, E, GuardInst);
+      assert(NewEnd != E && "GuardInst not in its own block?");
+      E = NewEnd;
+    }
+
+    for (auto *Candidate : make_range(I, E)) {
+      auto Score =
+          computeWideningScore(GuardInst, GuardInstLoop, Candidate, CurLoop);
+      DEBUG(dbgs() << "Score between " << *GuardInst->getArgOperand(0)
+                   << " and " << *Candidate->getArgOperand(0) << " is "
+                   << scoreTypeToString(Score) << "\n");
+      if (Score > BestScoreSoFar) {
+        BestScoreSoFar = Score;
+        BestSoFar = Candidate;
+      }
+    }
+  }
+
+  if (BestScoreSoFar == WS_IllegalOrNegative) {
+    DEBUG(dbgs() << "Did not eliminate guard " << *GuardInst << "\n");
+    return false;
+  }
+
+  assert(BestSoFar != GuardInst && "Should have never visited same guard!");
+  assert(DT.dominates(BestSoFar, GuardInst) && "Should be!");
+
+  DEBUG(dbgs() << "Widening " << *GuardInst << " into " << *BestSoFar
+               << " with score " << scoreTypeToString(BestScoreSoFar) << "\n");
+  widenGuard(BestSoFar, GuardInst->getArgOperand(0));
+  GuardInst->setArgOperand(0, ConstantInt::getTrue(GuardInst->getContext()));
+  EliminatedGuards.push_back(GuardInst);
+  WidenedGuards.insert(BestSoFar);
+  return true;
+}
+
+GuardWideningImpl::WideningScore GuardWideningImpl::computeWideningScore(
+    IntrinsicInst *DominatedGuard, Loop *DominatedGuardLoop,
+    IntrinsicInst *DominatingGuard, Loop *DominatingGuardLoop) {
+  bool HoistingOutOfLoop = false;
+
+  if (DominatingGuardLoop != DominatedGuardLoop) {
+    if (DominatingGuardLoop &&
+        !DominatingGuardLoop->contains(DominatedGuardLoop))
+      return WS_IllegalOrNegative;
+
+    HoistingOutOfLoop = true;
+  }
+
+  if (!isAvailableAt(DominatedGuard->getArgOperand(0), DominatingGuard))
+    return WS_IllegalOrNegative;
+
+  bool HoistingOutOfIf =
+      !PDT.dominates(DominatedGuard->getParent(), DominatingGuard->getParent());
+
+  if (isWideningCondProfitable(DominatedGuard->getArgOperand(0),
+                               DominatingGuard->getArgOperand(0)))
+    return HoistingOutOfLoop ? WS_VeryPositive : WS_Positive;
+
+  if (HoistingOutOfLoop)
+    return WS_Positive;
+
+  return HoistingOutOfIf ? WS_IllegalOrNegative : WS_Neutral;
+}
+
+bool GuardWideningImpl::isAvailableAt(Value *V, Instruction *Loc,
+                                      SmallPtrSetImpl<Instruction *> &Visited) {
+  auto *Inst = dyn_cast<Instruction>(V);
+  if (!Inst || DT.dominates(Inst, Loc) || Visited.count(Inst))
+    return true;
+
+  if (!isSafeToSpeculativelyExecute(Inst, Loc, &DT) ||
+      Inst->mayReadFromMemory())
+    return false;
+
+  Visited.insert(Inst);
+
+  // We only want to go _up_ the dominance chain when recursing.
+  assert(!isa<PHINode>(Loc) &&
+         "PHIs should return false for isSafeToSpeculativelyExecute");
+  assert(DT.isReachableFromEntry(Inst->getParent()) &&
+         "We did a DFS from the block entry!");
+  return all_of(Inst->operands(),
+                [&](Value *Op) { return isAvailableAt(Op, Loc, Visited); });
+}
+
+void GuardWideningImpl::makeAvailableAt(Value *V, Instruction *Loc) {
+  auto *Inst = dyn_cast<Instruction>(V);
+  if (!Inst || DT.dominates(Inst, Loc))
+    return;
+
+  assert(isSafeToSpeculativelyExecute(Inst, Loc, &DT) &&
+         !Inst->mayReadFromMemory() && "Should've checked with isAvailableAt!");
+
+  for (Value *Op : Inst->operands())
+    makeAvailableAt(Op, Loc);
+
+  Inst->moveBefore(Loc);
+}
+
+bool GuardWideningImpl::widenCondCommon(Value *Cond0, Value *Cond1,
+                                        Instruction *InsertPt, Value *&Result) {
+  using namespace llvm::PatternMatch;
+
+  {
+    // L >u C0 && L >u C1  ->  L >u max(C0, C1)
+    ConstantInt *RHS0, *RHS1;
+    Value *LHS;
+    ICmpInst::Predicate Pred0, Pred1;
+    if (match(Cond0, m_ICmp(Pred0, m_Value(LHS), m_ConstantInt(RHS0))) &&
+        match(Cond1, m_ICmp(Pred1, m_Specific(LHS), m_ConstantInt(RHS1)))) {
+
+      // TODO: This logic should be generalized and refactored into a new
+      // Constant::getEquivalentICmp helper.
+      if (Pred0 == ICmpInst::ICMP_NE && RHS0->isZero())
+        Pred0 = ICmpInst::ICMP_UGT;
+      if (Pred1 == ICmpInst::ICMP_NE && RHS1->isZero())
+        Pred1 = ICmpInst::ICMP_UGT;
+
+      if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_UGT) {
+        if (InsertPt) {
+          ConstantInt *NewRHS =
+              RHS0->getValue().ugt(RHS1->getValue()) ? RHS0 : RHS1;
+          Result = new ICmpInst(InsertPt, ICmpInst::ICMP_UGT, LHS, NewRHS,
+                                "wide.chk");
+        }
+
+        return true;
+      }
+    }
+  }
+
+  // Base case -- just logical-and the two conditions together.
+
+  if (InsertPt) {
+    makeAvailableAt(Cond0, InsertPt);
+    makeAvailableAt(Cond1, InsertPt);
+
+    Result = BinaryOperator::CreateAnd(Cond0, Cond1, "wide.chk", InsertPt);
+  }
+
+  // We were not able to compute Cond0 AND Cond1 for the price of one.
+  return false;
+}
+
+PreservedAnalyses GuardWideningPass::run(Function &F,
+                                         AnalysisManager<Function> &AM) {
+  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
+  auto &LI = AM.getResult<LoopAnalysis>(F);
+  auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
+  bool Changed = GuardWideningImpl(DT, PDT, LI).run();
+  return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
+}
+
+StringRef GuardWideningImpl::scoreTypeToString(WideningScore WS) {
+  switch (WS) {
+  case WS_IllegalOrNegative:
+    return "IllegalOrNegative";
+  case WS_Neutral:
+    return "Neutral";
+  case WS_Positive:
+    return "Positive";
+  case WS_VeryPositive:
+    return "VeryPositive";
+  }
+
+  llvm_unreachable("Fully covered switch above!");
+}
+
+char GuardWideningLegacyPass::ID = 0;
+
+INITIALIZE_PASS_BEGIN(GuardWideningLegacyPass, "guard-widening", "Widen guards",
+                      false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+INITIALIZE_PASS_END(GuardWideningLegacyPass, "guard-widening", "Widen guards",
+                    false, false)
+
+FunctionPass *llvm::createGuardWideningPass() {
+  return new GuardWideningLegacyPass();
+}

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

void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeAlignmentFromAssumptionsPass(Registry);
   initializeConstantHoistingPass(Registry);
   initializeConstantPropagationPass(Registry);
   initializeCorrelatedValuePropagationPass(Registry);
   initializeDCELegacyPassPass(Registry);
   initializeDeadInstEliminationPass(Registry);
   initializeScalarizerPass(Registry);
   initializeDSELegacyPassPass(Registry);
+  initializeGuardWideningLegacyPassPass(Registry);
   initializeGVNLegacyPassPass(Registry);
   initializeEarlyCSELegacyPassPass(Registry);
   initializeFlattenCFGPassPass(Registry);
   initializeInductiveRangeCheckEliminationPass(Registry);
   initializeIndVarSimplifyPass(Registry);
   initializeJumpThreadingPass(Registry);
   initializeLICMPass(Registry);
   initializeLoopDataPrefetchPass(Registry);

llvm/trunk/test/Transforms/GuardWidening/basic.ll

+; RUN: opt -S -guard-widening < %s        | FileCheck %s
+; RUN: opt -S -passes=guard-widening < %s | FileCheck %s
+
+declare void @llvm.experimental.guard(i1,...)
+
+; Basic test case: we wide the first check to check both the
+; conditions.
+define void @f_0(i1 %cond_0, i1 %cond_1) {
+; CHECK-LABEL: @f_0(
+entry:
+; CHECK:  %wide.chk = and i1 %cond_0, %cond_1
+; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
+; CHECK:  ret void
+
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
+  ret void
+}
+
+; Same as @f_0, but with using a more general notion of postdominance.
+define void @f_1(i1 %cond_0, i1 %cond_1) {
+; CHECK-LABEL: @f_1(
+entry:
+; CHECK:  %wide.chk = and i1 %cond_0, %cond_1
+; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
+; CHECK:  br i1 undef, label %left, label %right
+
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  br i1 undef, label %left, label %right
+
+left:
+  br label %merge
+
+right:
+  br label %merge
+
+merge:
+; CHECK: merge:
+; CHECK-NOT: call void (i1, ...) @llvm.experimental.guard(
+; CHECK: ret void
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
+  ret void
+}
+
+; Like @f_1, but we have some code we need to hoist before we can
+; widen a dominanting check.
+define void @f_2(i32 %a, i32 %b) {
+; CHECK-LABEL: @f_2(
+entry:
+; CHECK:  %cond_0 = icmp ult i32 %a, 10
+; CHECK:  %cond_1 = icmp ult i32 %b, 10
+; CHECK:  %wide.chk = and i1 %cond_0, %cond_1
+; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
+; CHECK:  br i1 undef, label %left, label %right
+
+  %cond_0 = icmp ult i32 %a, 10
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  br i1 undef, label %left, label %right
+
+left:
+  br label %merge
+
+right:
+  br label %merge
+
+merge:
+  %cond_1 = icmp ult i32 %b, 10
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
+  ret void
+}
+
+; Negative test: don't hoist stuff out of control flow
+; indiscriminately, since that can make us do more work than needed.
+define void @f_3(i32 %a, i32 %b) {
+; CHECK-LABEL: @f_3(
+entry:
+; CHECK:  %cond_0 = icmp ult i32 %a, 10
+; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+; CHECK:  br i1 undef, label %left, label %right
+
+  %cond_0 = icmp ult i32 %a, 10
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  br i1 undef, label %left, label %right
+
+left:
+; CHECK: left:
+; CHECK:   %cond_1 = icmp ult i32 %b, 10
+; CHECK:   call void (i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
+; CHECK:   ret void
+
+  %cond_1 = icmp ult i32 %b, 10
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
+  ret void
+
+right:
+  ret void
+}
+
+; But hoisting out of control flow is fine if it makes a loop computed
+; condition loop invariant.  This behavior may require some tuning in
+; the future.
+define void @f_4(i32 %a, i32 %b) {
+; CHECK-LABEL: @f_4(
+entry:
+; CHECK:  %cond_0 = icmp ult i32 %a, 10
+; CHECK:  %cond_1 = icmp ult i32 %b, 10
+; CHECK:  %wide.chk = and i1 %cond_0, %cond_1
+; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
+; CHECK:  br i1 undef, label %loop, label %leave
+
+  %cond_0 = icmp ult i32 %a, 10
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  br i1 undef, label %loop, label %leave
+
+loop:
+  %cond_1 = icmp ult i32 %b, 10
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
+  br i1 undef, label %loop, label %leave
+
+leave:
+  ret void
+}
+
+; Hoisting out of control flow is also fine if we can widen the
+; dominating check without doing any extra work.
+define void @f_5(i32 %a) {
+; CHECK-LABEL: @f_5(
+entry:
+; CHECK:  %wide.chk = icmp ugt i32 %a, 10
+; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
+; CHECK:  br i1 undef, label %left, label %right
+
+  %cond_0 = icmp ugt i32 %a, 7
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  br i1 undef, label %left, label %right
+
+left:
+  %cond_1 = icmp ugt i32 %a, 10
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
+  ret void
+
+right:
+  ret void
+}
+
+; Negative test: the load from %a can be safely speculated to before
+; the first guard, but there is no guarantee that it will produce the
+; same value.
+define void @f_6(i1* dereferenceable(32) %a, i1* %b, i1 %unknown) {
+; CHECK-LABEL: @f_6(
+; CHECK: call void (i1, ...) @llvm.experimental.guard(
+; CHECK: call void (i1, ...) @llvm.experimental.guard(
+; CHECK: ret void
+entry:
+  %cond_0 = load i1, i1* %a
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  store i1 %unknown, i1* %b
+  %cond_1 = load i1, i1* %a
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
+  ret void
+}
+
+; All else equal, we try to widen the earliest guard we can.  This
+; heuristic can use some tuning.
+define void @f_7(i32 %a, i1* %cond_buf) {
+; CHECK-LABEL: @f_7(
+entry:
+; CHECK:  %cond_1 = load volatile i1, i1* %cond_buf
+; CHECK:  %cond_3 = icmp ult i32 %a, 7
+; CHECK:  %wide.chk = and i1 %cond_1, %cond_3
+; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
+; CHECK:  %cond_2 = load volatile i1, i1* %cond_buf
+; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %cond_2) [ "deopt"() ]
+; CHECK:  br i1 undef, label %left, label %right
+
+  %cond_1 = load volatile i1, i1* %cond_buf
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
+  %cond_2 = load volatile i1, i1* %cond_buf
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_2) [ "deopt"() ]
+  br i1 undef, label %left, label %right
+
+left:
+  %cond_3 = icmp ult i32 %a, 7
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_3) [ "deopt"() ]
+  br label %left
+
+right:
+  ret void
+}
+
+; In this case the earliest dominating guard is in a loop, and we
+; don't want to put extra work in there.  This heuristic can use some
+; tuning.
+define void @f_8(i32 %a, i1 %cond_1, i1 %cond_2) {
+; CHECK-LABEL: @f_8(
+entry:
+  br label %loop
+
+loop:
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
+  br i1 undef, label %loop, label %leave
+
+leave:
+; CHECK: leave:
+; CHECK:  %cond_3 = icmp ult i32 %a, 7
+; CHECK:  %wide.chk = and i1 %cond_2, %cond_3
+; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
+; CHECK:  br i1 undef, label %loop2, label %leave2
+
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_2) [ "deopt"() ]
+  br i1 undef, label %loop2, label %leave2
+
+loop2:
+  %cond_3 = icmp ult i32 %a, 7
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_3) [ "deopt"() ]
+  br label %loop2
+
+leave2:
+  ret void
+}
+
+; In cases like these where there isn't any "obviously profitable"
+; widening sites, we refuse to do anything.
+define void @f_9(i32 %a, i1 %cond_0, i1 %cond_1) {
+; CHECK-LABEL: @f_9(
+entry:
+  br label %first_loop
+
+first_loop:
+; CHECK: first_loop:
+; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+; CHECK:  br i1 undef, label %first_loop, label %second_loop
+
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  br i1 undef, label %first_loop, label %second_loop
+
+second_loop:
+; CHECK: second_loop:
+; CHECK:   call void (i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
+; CHECK:   br label %second_loop
+
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
+  br label %second_loop
+}
+
+; Same situation as in @f_9: no "obviously profitable" widening sites,
+; so we refuse to do anything.
+define void @f_10(i32 %a, i1 %cond_0, i1 %cond_1) {
+; CHECK-LABEL: @f_10(
+entry:
+  br label %loop
+
+loop:
+; CHECK: loop:
+; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+; CHECK:  br i1 undef, label %loop, label %no_loop
+
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  br i1 undef, label %loop, label %no_loop
+
+no_loop:
+; CHECK: no_loop:
+; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
+; CHECK:  ret void
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
+  ret void
+}
+
+; With guards in loops, we're okay hoisting out the guard into the
+; containing loop.
+define void @f_11(i32 %a, i1 %cond_0, i1 %cond_1) {
+; CHECK-LABEL: @f_11(
+entry:
+  br label %inner
+
+inner:
+; CHECK: inner:
+; CHECK:  %wide.chk = and i1 %cond_0, %cond_1
+; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
+; CHECK:  br i1 undef, label %inner, label %outer
+
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  br i1 undef, label %inner, label %outer
+
+outer:
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
+  br label %inner
+}
+
+; Checks that we are adequately guarded against exponential-time
+; behavior when hoisting code.
+define void @f_12(i32 %a0) {
+; CHECK-LABEL: @f_12
+
+; Eliding the earlier 29 multiplications for brevity
+; CHECK:  %a30 = mul i32 %a29, %a29
+; CHECK-NEXT:  %cond = trunc i32 %a30 to i1
+; CHECK-NEXT:  %wide.chk = and i1 true, %cond
+; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
+; CHECK-NEXT:  ret void
+
+entry:
+  call void(i1, ...) @llvm.experimental.guard(i1 true) [ "deopt"() ]
+  %a1 = mul i32 %a0, %a0
+  %a2 = mul i32 %a1, %a1
+  %a3 = mul i32 %a2, %a2
+  %a4 = mul i32 %a3, %a3
+  %a5 = mul i32 %a4, %a4
+  %a6 = mul i32 %a5, %a5
+  %a7 = mul i32 %a6, %a6
+  %a8 = mul i32 %a7, %a7
+  %a9 = mul i32 %a8, %a8
+  %a10 = mul i32 %a9, %a9
+  %a11 = mul i32 %a10, %a10
+  %a12 = mul i32 %a11, %a11
+  %a13 = mul i32 %a12, %a12
+  %a14 = mul i32 %a13, %a13
+  %a15 = mul i32 %a14, %a14
+  %a16 = mul i32 %a15, %a15
+  %a17 = mul i32 %a16, %a16
+  %a18 = mul i32 %a17, %a17
+  %a19 = mul i32 %a18, %a18
+  %a20 = mul i32 %a19, %a19
+  %a21 = mul i32 %a20, %a20
+  %a22 = mul i32 %a21, %a21
+  %a23 = mul i32 %a22, %a22
+  %a24 = mul i32 %a23, %a23
+  %a25 = mul i32 %a24, %a24
+  %a26 = mul i32 %a25, %a25
+  %a27 = mul i32 %a26, %a26
+  %a28 = mul i32 %a27, %a27
+  %a29 = mul i32 %a28, %a28
+  %a30 = mul i32 %a29, %a29
+  %cond = trunc i32 %a30 to i1
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond) [ "deopt"() ]
+  ret void
+}