[WIP] Prototype outlined assumptions and operand bundle information attachment

[jdoerfert]

Summary

NOTE: This is a prototype not a finished patch!

Note: There is a mailing list discussion on this: http://lists.llvm.org/pipermail/llvm-dev/2019-December/137632.html

This patch introduces an assumption outliner, which is probably not here to
stay but helpful in creating operand bundle annotated llvm.assumes and
outlined assumption code.

Various passes, basically all that seemed interesting and deal with
assumptions, have been updated to work with outlined assumption code to
some degree.

AlignmentFromAssumptions is used to provide an additional operand bundle
for the llvm.assume that connects the outlined code with its original
location. The operand bundle has the form

`"align"(%ptr, %alignment, %offset)`

and that is the form we should generate in the first place.
The AlignmentFromAssumptionsPass is also able to read "align" operand
bundles on llvm.assume calls.

The other passes that deal with the outlined assumptions do violate
function pass rules but it should be sufficient to test this out.

Test for a few affected passes have been modified to run the outliner
first. While there are problems, overall most transformations are sill
possible and performed already.

A path forward could be to adopt (a clean version of) the outliner for
now but only run it if we can encode the information "natively" in an
operand bundle, e.g., as described for "align" above. We then would
start to emit information in this format in the frontends and decide how
we want to deal with outlining.

[merge_guards_bot]

Unit tests: fail. 60920 tests passed, 47 failed and 726 were skipped.

failed: LLVM-Unit.Transforms/Utils/_/UtilsTests/CodeExtractor.ExitStub
failed: LLVM-Unit.Transforms/Utils/_/UtilsTests/CodeExtractor.StoreOutputInvokeResultAfterEHPad
failed: Clang.CodeGen/align_value.cpp
failed: Clang.CodeGen/alloc-align-attr.c
failed: Clang.CodeGen/builtin-assume-aligned.c
failed: Clang.CodeGen/builtin-assume.c
failed: Clang.CodeGen/catch-alignment-assumption-attribute-align_value-on-lvalue.cpp
failed: Clang.CodeGen/catch-alignment-assumption-attribute-alloc_align-on-function-variable.cpp
failed: Clang.CodeGen/catch-alignment-assumption-attribute-alloc_align-on-function.cpp
failed: Clang.CodeGen/catch-alignment-assumption-attribute-assume_aligned-on-function-two-params.cpp
failed: Clang.CodeGen/catch-alignment-assumption-attribute-assume_aligned-on-function.cpp
failed: Clang.CodeGen/catch-alignment-assumption-builtin_assume_aligned-three-params-variable.cpp
failed: Clang.CodeGen/catch-alignment-assumption-builtin_assume_aligned-three-params.cpp
failed: Clang.CodeGen/catch-alignment-assumption-builtin_assume_aligned-two-params.cpp
failed: Clang.CodeGen/catch-alignment-assumption-openmp.cpp
failed: Clang.OpenMP/distribute_simd_codegen.cpp
failed: Clang.OpenMP/parallel_master_taskloop_simd_codegen.cpp
failed: Clang.OpenMP/simd_codegen.cpp
failed: Clang.OpenMP/simd_metadata.c
failed: Clang.OpenMP/target_teams_distribute_parallel_for_simd_codegen.cpp
failed: Clang-Unit.Frontend/_/FrontendTests/FrontendOutputTests.TestOutputStream
failed: LLVM.Other/opt-O0-pipeline.ll
failed: LLVM.Other/opt-O2-pipeline.ll
failed: LLVM.Other/opt-O3-pipeline.ll
failed: LLVM.Other/opt-Os-pipeline.ll
failed: LLVM.Other/pass-pipelines.ll
failed: LLVM.Transforms/BlockExtractor/extract-blocks-with-groups.ll
failed: LLVM.Transforms/BlockExtractor/extract-blocks.ll
failed: LLVM.Transforms/CodeExtractor/PartialInlineAnd.ll
failed: LLVM.Transforms/CodeExtractor/PartialInlineAttributes.ll
failed: LLVM.Transforms/CodeExtractor/PartialInlineDebug.ll
failed: LLVM.Transforms/CodeExtractor/PartialInlineHighCost.ll
failed: LLVM.Transforms/CodeExtractor/PartialInlineInvokeProducesOutVal.ll
failed: LLVM.Transforms/CodeExtractor/PartialInlineOrAnd.ll
failed: LLVM.Transforms/CodeExtractor/PartialInlineVarArgsDebug.ll
failed: LLVM.Transforms/CodeExtractor/X86/InheritTargetAttributes.ll
failed: LLVM.Transforms/DCE/guards.ll
failed: LLVM.Transforms/EarlyCSE/guards.ll
failed: LLVM.Transforms/HotColdSplit/duplicate-phi-preds-crash.ll
failed: LLVM.Transforms/HotColdSplit/phi-with-distinct-outlined-values.ll
failed: LLVM.Transforms/HotColdSplit/split-phis-in-exit-blocks.ll
failed: LLVM.Transforms/HotColdSplit/succ-block-with-self-edge.ll
failed: LLVM.Transforms/InstCombine/assume-redundant.ll
failed: LLVM.Transforms/InstCombine/assume.ll
failed: LLVM.Transforms/InstCombine/select.ll
failed: LLVM.Transforms/LICM/pr32129.ll
failed: LLVM.Transforms/LoopUnswitch/guards.ll

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[lebedev.ri]

With bundle patches landing, what's the status here?

[jdoerfert]

@lebedev.ri This was mostly outlining related code. While I still believe this is the right way to go, I want to focus on the operand bundle changes now and revisit this afterwards. I'll update the status so it's off your list.

llvm/include/llvm/Analysis/AssumptionCache.h

132

These are only needed for the outlining of side-effects.

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

llvm/include/llvm/Analysis/AssumptionCache.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_ASSUMPTIONCACHE_H
 #define LLVM_ANALYSIS_ASSUMPTIONCACHE_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include <memory>
 
 namespace llvm {
 
public:
   ///
   /// It will be re-scanned the next time it is requested.
   void clear() {
     AssumeHandles.clear();
     AffectedValues.clear();
     Scanned = false;
   }
 
+  /// TOOO
+  Value *getOriginalValue(CallInst &CI, Value &V);
+  CallInst *getReplacementAssumption(CallInst &CI);
+  CallInst *getReplacementAssumption(CallInst &CI, Value *&V);
+  CallInst *getReplacementAssumption(CallInst &CI,
+                                     DenseMap<const Value *, Value *> &Mapping);
+  CallInst *
+  getReplacementAssumption(CallInst &CI,
+                           SmallMapVector<Value *, Value *, 4> &Mapping);
+
   /// Access the list of assumption handles currently tracked for this
   /// function.
   ///
   /// Note that these produce weak handles that may be null. The caller must
   /// handle that case.
   /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>>
   /// when we can write that to filter out the null values. Then caller code
   /// will become simpler.

llvm/include/llvm/InitializePasses.h

 void initializeASanGlobalsMetadataWrapperPassPass(PassRegistry &);
 void initializeAddressSanitizerLegacyPassPass(PassRegistry &);
 void initializeAggressiveInstCombinerLegacyPassPass(PassRegistry&);
 void initializeAliasSetPrinterPass(PassRegistry&);
 void initializeAlignmentFromAssumptionsPass(PassRegistry&);
 void initializeAlwaysInlinerLegacyPassPass(PassRegistry&);
 void initializeArgPromotionPass(PassRegistry&);
 void initializeAssumptionCacheTrackerPass(PassRegistry&);
+void initializeAssumptionOutlinerPass(PassRegistry &);
 void initializeAtomicExpandPass(PassRegistry&);
 void initializeAttributorLegacyPassPass(PassRegistry&);
 void initializeBDCELegacyPassPass(PassRegistry&);
 void initializeBarrierNoopPass(PassRegistry&);
 void initializeBasicAAWrapperPassPass(PassRegistry&);
 void initializeBlockExtractorPass(PassRegistry &);
 void initializeBlockFrequencyInfoWrapperPassPass(PassRegistry&);
 void initializeBoundsCheckingLegacyPassPass(PassRegistry&);

llvm/lib/Analysis/AssumptionCache.cpp

 //===- AssumptionCache.cpp - Cache finding @llvm.assume calls -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains a pass that keeps track of @llvm.assume intrinsics in
 // the functions of a module.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/CodeExtractor.h"
 #include <algorithm>
 #include <cassert>
 #include <utility>
 
 using namespace llvm;
 using namespace llvm::PatternMatch;
 
 static cl::opt<bool>
if (isa<Argument>(V)) {
           match(I, m_PtrToInt(m_Value(Op))) ||
           match(I, m_Not(m_Value(Op)))) {
         if (isa<Instruction>(Op) || isa<Argument>(Op))
           Affected.push_back(Op);
       }
     }
   };
 
-  Value *Cond = CI->getArgOperand(0), *A, *B;
-  AddAffected(Cond);
+
+  if (CI->hasOperandBundles())
+    for (auto *V : CI->operand_values())
+      AddAffected(V);
 
   CmpInst::Predicate Pred;
+  Value *Cond = CI->getArgOperand(0), *A, *B;
   if (match(Cond, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
     AddAffected(A);
     AddAffected(B);
 
     if (Pred == ICmpInst::ICMP_EQ) {
       // For equality comparisons, we handle the case of bit inversion.
       auto AddAffectedFromEq = [&AddAffected](Value *V) {
         Value *A;
for (auto &VH : AssumeHandles) {
     assert(AssumptionSet.insert(VH).second &&
            "Cache contains multiple copies of a call!");
   }
 #endif
 
   updateAffectedValues(CI);
 }
 
+template <typename MappingT>
+static CallInst *getReplacementAssumption(CallInst &CI, Value **V,
+                                          MappingT *Mapping) {
+  Optional<OperandBundleUse> OpB = CI.getOperandBundle("assume_fn");
+  if (!OpB.hasValue())
+    return &CI;
+
+  ArrayRef<Use> Inputs = OpB.getValue().Inputs;
+  Function *AssumeFn = cast<Function>(Inputs.front().get());
+
+  CallInst *ReplCI =
+      cast<CallInst>(AssumeFn->getEntryBlock().back().getPrevNode());
+  if (!V && !Mapping)
+    return ReplCI;
+
+  CI.dump();
+  if (V)
+    (*V)->dump();
+  int Idx = -1;
+  for (unsigned i = 1; i < Inputs.size(); ++i) {
+    const Use &U = Inputs[i];
+    errs() << i << " : " << *U.get() << "\n";
+    if (Mapping)
+      Mapping->insert({AssumeFn->getArg(i - 1), U.get()});
+    if (!V || U.get() != *V)
+      continue;
+    assert(Idx == -1);
+    Idx = i - 1;
+  }
+
+  if (V && Idx >= 0)
+    *V = AssumeFn->getArg(Idx);
+
+  return ReplCI;
+}
+
+CallInst *AssumptionCache::getReplacementAssumption(CallInst &CI, Value *&V) {
+  DenseMap<const Value *, Value *> *M = nullptr;
+  return ::getReplacementAssumption(CI, &V, M);
+}
+CallInst *AssumptionCache::getReplacementAssumption(
+    CallInst &CI, DenseMap<const Value *, Value *> &Mapping) {
+  return ::getReplacementAssumption(CI, nullptr, &Mapping);
+}
+CallInst *AssumptionCache::getReplacementAssumption(
+    CallInst &CI, SmallMapVector<Value *, Value *, 4> &Mapping) {
+  return ::getReplacementAssumption(CI, nullptr, &Mapping);
+}
+CallInst *AssumptionCache::getReplacementAssumption(CallInst &CI) {
+  DenseMap<const Value *, Value *> *M = nullptr;
+  return ::getReplacementAssumption(CI, nullptr, M);
+}
+
+Value *AssumptionCache::getOriginalValue(CallInst &CI, Value &V) {
+  Argument *Arg = dyn_cast<Argument>(&V);
+  if (!Arg)
+    return &V;
+
+  Optional<OperandBundleUse> OpB = CI.getOperandBundle("assume_fn");
+  if (!OpB.hasValue())
+    return &V;
+
+  Function *Fn = Arg->getParent();
+  ArrayRef<Use> Inputs = OpB.getValue().Inputs;
+  if (Fn != cast<Function>(Inputs.front().get()))
+    return &V;
+
+  return Inputs[Arg->getArgNo() + 1].get();
+}
+
 AnalysisKey AssumptionAnalysis::Key;
 
 PreservedAnalyses AssumptionPrinterPass::run(Function &F,
                                              FunctionAnalysisManager &AM) {
   AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F);
 
   OS << "Cached assumptions for function: " << F.getName() << "\n";
   for (auto &VH : AC.assumptions())

llvm/lib/Analysis/LazyValueInfo.cpp

void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
 
   for (auto &AssumeVH : AC->assumptionsFor(Val)) {
     if (!AssumeVH)
       continue;
     auto *I = cast<CallInst>(AssumeVH);
     if (!isValidAssumeForContext(I, BBI, DT))
       continue;
 
+    // Replace the assumption with an outlined one if applicable.
+    I = AC->getReplacementAssumption(*I, Val);
+
     BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
   }
 
   // If guards are not used in the module, don't spend time looking for them
   auto *GuardDecl = BBI->getModule()->getFunction(
           Intrinsic::getName(Intrinsic::experimental_guard));
   if (GuardDecl && !GuardDecl->use_empty()) {
     if (BBI->getIterator() == BBI->getParent()->begin())

llvm/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::getSmallConstantTripMultiple(const Loop *L,
 
   return (unsigned)Result->getZExtValue();
 }
 
 const SCEV *ScalarEvolution::getExitCount(const Loop *L,
                                           BasicBlock *ExitingBlock,
                                           ExitCountKind Kind) {
   switch (Kind) {
-  case Exact: 
+  case Exact:
     return getBackedgeTakenInfo(L).getExact(ExitingBlock, this);
   case ConstantMaximum:
     return getBackedgeTakenInfo(L).getMax(ExitingBlock, this);
   };
   llvm_unreachable("Invalid ExitCountKind!");
 }
 
 const SCEV *
 ScalarEvolution::getPredicatedBackedgeTakenCount(const Loop *L,
                                                  SCEVUnionPredicate &Preds) {
   return getPredicatedBackedgeTakenInfo(L).getExact(L, this, &Preds);
 }
 
 const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L,
                                                    ExitCountKind Kind) {
   switch (Kind) {
-  case Exact: 
+  case Exact:
     return getBackedgeTakenInfo(L).getExact(L, this);
   case ConstantMaximum:
     return getBackedgeTakenInfo(L).getMax(this);
   };
   llvm_unreachable("Invalid ExitCountKind!");
 }
 
 bool ScalarEvolution::isBackedgeTakenCountMaxOrZero(const Loop *L) {
ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L,
   // Check conditions due to any @llvm.assume intrinsics.
   for (auto &AssumeVH : AC.assumptions()) {
     if (!AssumeVH)
       continue;
     auto *CI = cast<CallInst>(AssumeVH);
     if (!DT.dominates(CI, Latch->getTerminator()))
       continue;
 
-    if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0), false))
+    // Replace the assumption with an outlined one if applicable.
+    const SCEV *ReplLHS = LHS, *ReplRHS = RHS;
+    ValueToValueMap RewriteMap;
+    CallInst *ReplCI = AC.getReplacementAssumption(*CI, RewriteMap);
+    if (ReplCI != CI) {
+      ReplLHS = SCEVParameterRewriter::rewrite(LHS, *this, RewriteMap, false);
+      ReplRHS = SCEVParameterRewriter::rewrite(RHS, *this, RewriteMap, false);
+    }
+
+    if (isImpliedCond(Pred, ReplLHS, ReplRHS, CI->getArgOperand(0), false))
       return true;
   }
 
   // If the loop is not reachable from the entry block, we risk running into an
   // infinite loop as we walk up into the dom tree.  These loops do not matter
   // anyway, so we just return a conservative answer when we see them.
   if (!DT.isReachableFromEntry(L->getHeader()))
     return false;
if (ProvingStrictComparison) {
             isImpliedViaGuard(Block, ICmpInst::ICMP_NE, LHS, RHS);
       if (ProvedNonStrictComparison && ProvedNonEquality)
         return true;
     }
     return false;
   };
 
   // Try to prove (Pred, LHS, RHS) using isImpliedCond.
-  auto ProveViaCond = [&](Value *Condition, bool Inverse) {
+  auto ProveViaCond = [&](Value *Condition, bool Inverse, const SCEV *LHS,
+                          const SCEV *RHS) {
     if (isImpliedCond(Pred, LHS, RHS, Condition, Inverse))
       return true;
     if (ProvingStrictComparison) {
       if (!ProvedNonStrictComparison)
         ProvedNonStrictComparison =
             isImpliedCond(NonStrictPredicate, LHS, RHS, Condition, Inverse);
       if (!ProvedNonEquality)
         ProvedNonEquality =
for (std::pair<BasicBlock *, BasicBlock *>
 
     BranchInst *LoopEntryPredicate =
       dyn_cast<BranchInst>(Pair.first->getTerminator());
     if (!LoopEntryPredicate ||
         LoopEntryPredicate->isUnconditional())
       continue;
 
     if (ProveViaCond(LoopEntryPredicate->getCondition(),
-                     LoopEntryPredicate->getSuccessor(0) != Pair.second))
+                     LoopEntryPredicate->getSuccessor(0) != Pair.second, LHS,
+                     RHS))
       return true;
   }
 
   // Check conditions due to any @llvm.assume intrinsics.
   for (auto &AssumeVH : AC.assumptions()) {
     if (!AssumeVH)
       continue;
     auto *CI = cast<CallInst>(AssumeVH);
     if (!DT.dominates(CI, L->getHeader()))
       continue;
 
-    if (ProveViaCond(CI->getArgOperand(0), false))
+    // Replace the assumption with an outlined one if applicable.
+    const SCEV *ReplLHS = LHS, *ReplRHS = RHS;
+    ValueToValueMap RewriteMap;
+    CallInst *ReplCI = AC.getReplacementAssumption(*CI, RewriteMap);
+    if (ReplCI != CI) {
+      ReplLHS = SCEVParameterRewriter::rewrite(LHS, *this, RewriteMap, false);
+      ReplRHS = SCEVParameterRewriter::rewrite(RHS, *this, RewriteMap, false);
+    }
+
+    if (ProveViaCond(CI->getArgOperand(0), false, ReplLHS, ReplRHS))
       return true;
   }
 
   return false;
 }
 
 bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred,
                                     const SCEV *LHS, const SCEV *RHS,

llvm/lib/Analysis/ValueTracking.cpp

for (auto &AssumeVH : Q.AC->assumptionsFor(V)) {
     if (!AssumeVH)
       continue;
     CallInst *I = cast<CallInst>(AssumeVH);
     assert(I->getParent()->getParent() == Q.CxtI->getParent()->getParent() &&
            "Got assumption for the wrong function!");
     if (Q.isExcluded(I))
       continue;
 
+    // Replace the assumption with an outlined one if applicable.
+    Value *VV = const_cast<Value *>(V);
+    CallInst *ReplI = Q.AC->getReplacementAssumption(*I, VV);
+    if (ReplI != I) {
+      I = ReplI;
+      V = VV;
+    }
+
     // Warning: This loop can end up being somewhat performance sensitive.
     // We're running this loop for once for each value queried resulting in a
     // runtime of ~O(#assumes * #values).
 
     assert(I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume &&
            "must be an assume intrinsic");
 
     Value *Arg = I->getArgOperand(0);

llvm/lib/LTO/LTOCodeGenerator.cpp

void LTOCodeGenerator::initializeLTOPasses() {
   initializeInstructionCombiningPassPass(R);
   initializeSimpleInlinerPass(R);
   initializePruneEHPass(R);
   initializeGlobalDCELegacyPassPass(R);
   initializeArgPromotionPass(R);
   initializeJumpThreadingPass(R);
   initializeSROALegacyPassPass(R);
   initializeAttributorLegacyPassPass(R);
+  initializeAssumptionOutlinerPass(R);
   initializePostOrderFunctionAttrsLegacyPassPass(R);
   initializeReversePostOrderFunctionAttrsLegacyPassPass(R);
   initializeGlobalsAAWrapperPassPass(R);
   initializeLegacyLICMPassPass(R);
   initializeMergedLoadStoreMotionLegacyPassPass(R);
   initializeGVNLegacyPassPass(R);
   initializeMemCpyOptLegacyPassPass(R);
   initializeDCELegacyPassPass(R);

llvm/lib/Transforms/IPO/AssumptionOutliner.cpp

+//===- AssumptionOutliner.cpp - Extract assumptions into own functions ----===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/ScalarEvolutionExpander.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/InstrTypes.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/IR/Verifier.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Scalar/AlignmentFromAssumptions.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/CodeExtractor.h"
+
+using namespace llvm;
+
+static cl::opt<bool> DuplicateInst("assumption-outliner-duplicate-inst",
+                                   cl::Hidden, cl::init(false));
+static cl::opt<bool> Aggressive("assumption-outliner-aggressive", cl::Hidden,
+                                cl::init(true));
+
+static void markAsOutlined(Instruction &OutlinedI,
+                           SmallVectorImpl<Instruction *> &OutlinedInstsOrdered,
+                           DenseMap<Instruction *, int> &NonOutlinedUsesMap) {
+  assert(NonOutlinedUsesMap[&OutlinedI] == 0);
+  SmallVector<Instruction *, 8> Worklist;
+  Worklist.push_back(&OutlinedI);
+
+  while (!Worklist.empty()) {
+    Instruction *I = Worklist.pop_back_val();
+    if (isa<PHINode>(I))
+      continue;
+    OutlinedInstsOrdered.push_back(I);
+    for (Value *Op : I->operands())
+      if (auto *OpI = dyn_cast<Instruction>(Op)) {
+        int &NonOutlinedUses = NonOutlinedUsesMap[OpI];
+        if (NonOutlinedUses == 0)
+          NonOutlinedUses += OpI->getNumUses();
+        NonOutlinedUses -= 1;
+        if (NonOutlinedUses == 0)
+          Worklist.push_back(OpI);
+      }
+  }
+}
+static Instruction *duplicateInsts(IntrinsicInst &AssumeCall,
+                                   Instruction *OutlinedI) {
+  SmallPtrSet<Instruction *, 8> Visisted;
+  Visisted.insert(&AssumeCall);
+  SmallVector<Instruction *, 8> Worklist;
+  Worklist.push_back(OutlinedI);
+
+  while (!Worklist.empty()) {
+    Instruction *I = Worklist.pop_back_val();
+    if (isa<PHINode>(I) || I->isTerminator() || isa<AllocaInst>(I))
+      continue;
+    if (!Visisted.insert(I).second)
+      continue;
+    for (Value *Op : I->operands())
+      if (auto *OpI = dyn_cast<Instruction>(Op))
+        Worklist.push_back(OpI);
+  }
+
+  SmallPtrSet<Instruction *, 8> Cloned;
+  SmallPtrSet<Instruction *, 8> Clones;
+  for (Instruction *I : Visisted) {
+    Worklist.clear();
+    Instruction *Clone = nullptr;
+    for (User *Usr : I->users())
+      if (Instruction *UserI = dyn_cast<Instruction>(Usr)) {
+        if (!Cloned.count(UserI) && Visisted.count(UserI))
+          Worklist.push_back(UserI);
+        else if (!Clone)
+          Clone = I->clone();
+        if (Clones.count(UserI))
+          Worklist.push_back(UserI);
+      }
+    if (!Clone)
+      continue;
+    Clones.insert(Clone);
+    Cloned.insert(I);
+    Clone->insertAfter(I);
+    Clone->setName(I->getName() + ".clone");
+    if (OutlinedI == I)
+      OutlinedI = Clone;
+    while (!Worklist.empty())
+      Worklist.pop_back_val()->replaceUsesOfWith(I, Clone);
+  }
+  return OutlinedI;
+}
+
+static bool outline(IntrinsicInst &AssumeCall, AssumptionCache &AC,
+                    AlignmentFromAssumptionsPass &AFAP) {
+  Instruction *Op = dyn_cast<Instruction>(AssumeCall.getOperand(0));
+  if (!Op || (!DuplicateInst && Op->getNumUses() > 1) ||
+      (isa<IntrinsicInst>(Op) &&
+       cast<IntrinsicInst>(Op)->getIntrinsicID() == Intrinsic::type_test))
+    return false;
+
+  SmallVector<OperandBundleDefT<Value *>, 4> OpBundleOps;
+  SmallVector<Value *, 8> Operands;
+
+  Value *AAPtr;
+  const SCEV *AlignSCEV, *OffSCEV;
+  if (AFAP.extractAlignmentInfo(&AssumeCall, AAPtr, AlignSCEV, OffSCEV)) {
+    Operands.push_back(AAPtr);
+    SCEVExpander Expander(*AFAP.SE, AssumeCall.getModule()->getDataLayout(),
+                          "");
+    Expander.setInsertPoint(&AssumeCall);
+    Operands.push_back(Expander.expandCodeFor(AlignSCEV));
+    Operands.push_back(Expander.expandCodeFor(OffSCEV));
+    OperandBundleDefT<Value *> AlignOpB("align", Operands);
+    OpBundleOps.push_back(AlignOpB);
+  } else if (!Aggressive)
+    return false;
+
+  AC.unregisterAssumption(&AssumeCall);
+
+  // Find the instructions we want to outline and an order in which we can put
+  // them later.
+  SmallVector<Instruction *, 32> OutlinedInstsOrdered;
+  DenseMap<Instruction *, int> NonOutlinedUsesMap;
+  if (DuplicateInst)
+    Op = duplicateInsts(AssumeCall, Op);
+  markAsOutlined(*Op, OutlinedInstsOrdered, NonOutlinedUsesMap);
+  assert(!OutlinedInstsOrdered.empty());
+
+  // Isolate the call into its own basic block.
+  SplitBlock(AssumeCall.getParent(), &AssumeCall);
+  SplitBlock(AssumeCall.getParent(), AssumeCall.getNextNode());
+
+  // Move the instruction into the new block and order them.
+  while (!OutlinedInstsOrdered.empty()) {
+    Instruction *I = OutlinedInstsOrdered.pop_back_val();
+    I->moveBefore(&AssumeCall);
+  }
+
+  CodeExtractorAnalysisCache CEAC(*AssumeCall.getFunction());
+  CodeExtractor CE(ArrayRef<BasicBlock *>({AssumeCall.getParent()}));
+
+  Function *OutlinedFn = CE.extractCodeRegion(CEAC);
+
+  assert(OutlinedFn->getNumUses() == 1);
+  CallInst *DirectCall = cast<CallInst>(OutlinedFn->user_back());
+  OutlinedFn->setName("__assumption_in_" + DirectCall->getCaller()->getName());
+
+  Operands.clear();
+  Operands.push_back(OutlinedFn);
+  Operands.append(DirectCall->value_op_begin(), --DirectCall->value_op_end());
+  OperandBundleDefT<Value *> AssumeFnOpB("assume_fn", Operands);
+  OpBundleOps.push_back(AssumeFnOpB);
+
+  LLVMContext &Ctx = OutlinedFn->getContext();
+  CallInst *NewAssumeCall = CallInst::Create(AssumeCall.getCalledFunction(),
+                                             {ConstantInt::getTrue(Ctx)},
+                                             OpBundleOps, "", DirectCall);
+
+  unsigned Merged = 0;
+  Merged += MergeBlockIntoPredecessor(
+      NewAssumeCall->getParent()->getUniqueSuccessor());
+  Merged += MergeBlockIntoPredecessor(NewAssumeCall->getParent());
+  Merged +=
+      MergeBlockIntoPredecessor(AssumeCall.getParent()->getUniqueSuccessor());
+  Merged += MergeBlockIntoPredecessor(AssumeCall.getParent());
+  assert(Merged == 4);
+
+  // Remove the direct call.
+  DirectCall->eraseFromParent();
+  assert(OutlinedFn->getNumUses() == 1);
+
+  AC.registerAssumption(NewAssumeCall);
+  assert(NewAssumeCall->hasOperandBundles());
+
+  return true;
+}
+
+namespace {
+struct AssumptionOutliner : public ModulePass {
+  AssumptionOutliner() : ModulePass(ID) {}
+  bool runOnModule(Module &M) override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
+    AU.addRequired<AssumptionCacheTracker>();
+  }
+  static char ID;
+};
+} // namespace
+
+bool AssumptionOutliner::runOnModule(Module &M) {
+  Function *Assume = M.getFunction("llvm.assume");
+  if (!Assume)
+    return false;
+  SmallVector<IntrinsicInst *, 8> Uses;
+  for (Use &U : Assume->uses())
+    if (auto *II = dyn_cast<IntrinsicInst>(U.getUser()))
+      Uses.push_back(II);
+
+  bool Changed = false;
+  for (IntrinsicInst *II : Uses) {
+    Function *Fn = II->getFunction();
+    auto &ACU = getAnalysis<AssumptionCacheTracker>();
+    ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>(*Fn).getSE();
+    AlignmentFromAssumptionsPass AFAP;
+    AFAP.SE = SE;
+
+    auto &AC = ACU.getAssumptionCache(*Fn);
+    Changed |= outline(*II, AC, AFAP);
+  }
+
+  assert(!verifyModule(M, &errs()));
+  return Changed;
+}
+
+char AssumptionOutliner::ID = 0;
+
+namespace llvm {
+ModulePass *createAssumptionOutlinerPass() { return new AssumptionOutliner(); }
+} // namespace llvm
+
+INITIALIZE_PASS_BEGIN(AssumptionOutliner, "assumption-outliner",
+                      "Assumption outliner", false, false)
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
+INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
+INITIALIZE_PASS_END(AssumptionOutliner, "assumption-outliner",
+                    "Assumption outliner", false, false)

llvm/lib/Transforms/IPO/CMakeLists.txt

 add_llvm_component_library(LLVMipo
   AlwaysInliner.cpp
   ArgumentPromotion.cpp
+  AssumptionOutliner.cpp
   Attributor.cpp
   BarrierNoopPass.cpp
   BlockExtractor.cpp
   CalledValuePropagation.cpp
   ConstantMerge.cpp
   CrossDSOCFI.cpp
   DeadArgumentElimination.cpp
   ElimAvailExtern.cpp

llvm/lib/Transforms/IPO/IPO.cpp

void llvm::initializeIPO(PassRegistry &Registry) {
   initializeInternalizeLegacyPassPass(Registry);
   initializeLoopExtractorPass(Registry);
   initializeBlockExtractorPass(Registry);
   initializeSingleLoopExtractorPass(Registry);
   initializeLowerTypeTestsPass(Registry);
   initializeMergeFunctionsPass(Registry);
   initializePartialInlinerLegacyPassPass(Registry);
   initializeAttributorLegacyPassPass(Registry);
+  initializeAssumptionOutlinerPass(Registry);
   initializePostOrderFunctionAttrsLegacyPassPass(Registry);
   initializeReversePostOrderFunctionAttrsLegacyPassPass(Registry);
   initializePruneEHPass(Registry);
   initializeIPSCCPLegacyPassPass(Registry);
   initializeStripDeadPrototypesLegacyPassPass(Registry);
   initializeStripSymbolsPass(Registry);
   initializeStripDebugDeclarePass(Registry);
   initializeStripDeadDebugInfoPass(Registry);

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

 #include "llvm/Transforms/Scalar/LICM.h"
 #include "llvm/Transforms/Scalar/LoopUnrollPass.h"
 #include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h"
 #include "llvm/Transforms/Utils.h"
 #include "llvm/Transforms/Vectorize.h"
 #include "llvm/Transforms/Vectorize/LoopVectorize.h"
 #include "llvm/Transforms/Vectorize/SLPVectorizer.h"
 
+namespace llvm {
+ModulePass *createAssumptionOutlinerPass();
+}
+
 using namespace llvm;
 
 static cl::opt<bool>
     RunPartialInlining("enable-partial-inlining", cl::init(false), cl::Hidden,
                        cl::ZeroOrMore, cl::desc("Run Partial inlinining pass"));
 
 static cl::opt<bool>
 UseGVNAfterVectorization("use-gvn-after-vectorization",
void PassManagerBuilder::addFunctionSimplificationPasses(
 
   if (EnableCHR && OptLevel >= 3 &&
       (!PGOInstrUse.empty() || !PGOSampleUse.empty() || EnablePGOCSInstrGen))
     MPM.add(createControlHeightReductionLegacyPass());
 }
 
 void PassManagerBuilder::populateModulePassManager(
     legacy::PassManagerBase &MPM) {
+  MPM.add(createAssumptionOutlinerPass());
+
   // Whether this is a default or *LTO pre-link pipeline. The FullLTO post-link
   // is handled separately, so just check this is not the ThinLTO post-link.
   bool DefaultOrPreLinkPipeline = !PerformThinLTO;
 
   if (!PGOSampleUse.empty()) {
     MPM.add(createPruneEHPass());
     // In ThinLTO mode, when flattened profile is used, all the available
     // profile information will be annotated in PreLink phase so there is

llvm/lib/Transforms/Scalar/AlignmentFromAssumptions.cpp

static unsigned getNewAlignment(const SCEV *AASCEV, const SCEV *AlignSCEV,
 
   return 0;
 }
 
 bool AlignmentFromAssumptionsPass::extractAlignmentInfo(CallInst *I,
                                                         Value *&AAPtr,
                                                         const SCEV *&AlignSCEV,
                                                         const SCEV *&OffSCEV) {
+  Type *Int64Ty = Type::getInt64Ty(I->getContext());
+  Optional<OperandBundleUse> AlignOB = I->getOperandBundle("align");
+  if (AlignOB.hasValue()) {
+    assert(AlignOB.getValue().Inputs.size() >= 2);
+    AAPtr = AlignOB.getValue().Inputs[0].get();
+    AlignSCEV = SE->getSCEV(AlignOB.getValue().Inputs[1].get());
+    if (AlignOB.getValue().Inputs.size() == 3)
+      OffSCEV = SE->getSCEV(AlignOB.getValue().Inputs[2].get());
+    else
+      OffSCEV = SE->getZero(Int64Ty);
+    return true;
+  }
+
   // An alignment assume must be a statement about the least-significant
   // bits of the pointer being zero, possibly with some offset.
   ICmpInst *ICI = dyn_cast<ICmpInst>(I->getArgOperand(0));
   if (!ICI)
     return false;
 
   // This must be an expression of the form: x & m == 0.
   if (ICI->getPredicate() != ICmpInst::ICMP_EQ)
bool AlignmentFromAssumptionsPass::extractAlignmentInfo(CallInst *I,
 
   // Cap the alignment at the maximum with which LLVM can deal (and make sure
   // we don't overflow the shift).
   uint64_t Alignment;
   TrailingOnes = std::min(TrailingOnes,
     unsigned(sizeof(unsigned) * CHAR_BIT - 1));
   Alignment = std::min(1u << TrailingOnes, +Value::MaximumAlignment);
 
-  Type *Int64Ty = Type::getInt64Ty(I->getParent()->getParent()->getContext());
   AlignSCEV = SE->getConstant(Int64Ty, Alignment);
 
   // The LHS might be a ptrtoint instruction, or it might be the pointer
   // with an offset.
   AAPtr = nullptr;
   OffSCEV = nullptr;
   if (PtrToIntInst *PToI = dyn_cast<PtrToIntInst>(AndLHS)) {
     AAPtr = PToI->getPointerOperand();
     OffSCEV = SE->getZero(Int64Ty);
   } else if (const SCEVAddExpr* AndLHSAddSCEV =
              dyn_cast<SCEVAddExpr>(AndLHSSCEV)) {
     // Try to find the ptrtoint; subtract it and the rest is the offset.
     for (SCEVAddExpr::op_iterator J = AndLHSAddSCEV->op_begin(),
-         JE = AndLHSAddSCEV->op_end(); J != JE; ++J)
+                                  JE = AndLHSAddSCEV->op_end();
+         J != JE; ++J)
       if (const SCEVUnknown *OpUnk = dyn_cast<SCEVUnknown>(*J))
         if (PtrToIntInst *PToI = dyn_cast<PtrToIntInst>(OpUnk->getValue())) {
           AAPtr = PToI->getPointerOperand();
           OffSCEV = SE->getMinusSCEV(AndLHSAddSCEV, *J);
           break;
         }
   }
 

llvm/lib/Transforms/Scalar/GVN.cpp

if (isa<Instruction>(U) &&
         cast<Instruction>(U)->getParent() == BB)
       return true;
   return false;
 }
 
 bool GVN::processAssumeIntrinsic(IntrinsicInst *IntrinsicI) {
   assert(IntrinsicI->getIntrinsicID() == Intrinsic::assume &&
          "This function can only be called with llvm.assume intrinsic");
-  Value *V = IntrinsicI->getArgOperand(0);
+  auto *ReplIntrinsicI = cast<IntrinsicInst>(
+      AC->getReplacementAssumption(*IntrinsicI, ReplaceOperandsWithMap));
+  Value *V = ReplIntrinsicI->getArgOperand(0);
 
   if (ConstantInt *Cond = dyn_cast<ConstantInt>(V)) {
     if (Cond->isZero()) {
       Type *Int8Ty = Type::getInt8Ty(V->getContext());
       // Insert a new store to null instruction before the load to indicate that
       // this code is not reachable.  FIXME: We could insert unreachable
       // instruction directly because we can modify the CFG.
       new StoreInst(UndefValue::get(Int8Ty),
                     Constant::getNullValue(Int8Ty->getPointerTo()),
                     IntrinsicI);
     }
+    if (!IntrinsicI->hasOperandBundles())
       markInstructionForDeletion(IntrinsicI);
     return false;
   } else if (isa<Constant>(V)) {
     // If it's not false, and constant, it must evaluate to true. This means our
     // assume is assume(true), and thus, pointless, and we don't want to do
     // anything more here.
     return false;
   }
 
if (CmpI->getPredicate() == CmpInst::Predicate::ICMP_EQ ||
         return Changed;
 
       // +0.0 and -0.0 compare equal, but do not imply equivalence.  Unless we
       // can prove equivalence, bail.
       if (CmpRHS->getType()->isFloatTy() &&
           (!isa<ConstantFP>(CmpRHS) || cast<ConstantFP>(CmpRHS)->isZero()))
         return Changed;
 
-      LLVM_DEBUG(dbgs() << "Replacing dominated uses of "
-                 << *CmpLHS << " with "
+      if (ReplIntrinsicI != IntrinsicI && ReplaceOperandsWithMap.lookup(CmpLHS))
+        CmpLHS = ReplaceOperandsWithMap[CmpLHS];
+
+      LLVM_DEBUG(dbgs() << "Replacing dominated uses of " << *CmpLHS << " with "
                         << *CmpRHS << " in block "
                         << IntrinsicI->getParent()->getName() << "\n");
-      
-
       // Setup the replacement map - this handles uses within the same block
       if (hasUsersIn(CmpLHS, IntrinsicI->getParent()))
         ReplaceOperandsWithMap[CmpLHS] = CmpRHS;
 
       // NOTE: The non-block local cases are handled by the call to
       // propagateEquality above; this block is just about handling the block
       // local cases.  TODO: There's a bunch of logic in propagateEqualiy which
       // isn't duplicated for the block local case, can we share it somehow?
bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
   // For speed, compute a conservative fast approximation to
   // DT->dominates(Root, Root.getEnd());
   const bool RootDominatesEnd = isOnlyReachableViaThisEdge(Root, DT);
 
   while (!Worklist.empty()) {
     std::pair<Value*, Value*> Item = Worklist.pop_back_val();
     LHS = Item.first; RHS = Item.second;
 
+    if (Value *ReplLHS = ReplaceOperandsWithMap.lookup(LHS))
+      LHS = ReplLHS;
+    if (Value *ReplRHS = ReplaceOperandsWithMap.lookup(RHS))
+      RHS = ReplRHS;
+
     if (LHS == RHS)
       continue;
     assert(LHS->getType() == RHS->getType() && "Equality but unequal types!");
 
     // Don't try to propagate equalities between constants.
     if (isa<Constant>(LHS) && isa<Constant>(RHS))
       continue;
 

llvm/lib/Transforms/Utils/CodeExtractor.cpp

 }
 
 /// emitCallAndSwitchStatement - This method sets up the caller side by adding
 /// the call instruction, splitting any PHI nodes in the header block as
 /// necessary.
 CallInst *CodeExtractor::emitCallAndSwitchStatement(Function *newFunction,
                                                     BasicBlock *codeReplacer,
                                                     ValueSet &inputs,
                                                     ValueSet &outputs) {
   // Emit a call to the new function, passing in: *pointer to struct (if
   // aggregating parameters), or plan inputs and allocated memory for outputs
-  std::vector<Value *> params, StructValues, ReloadOutputs, Reloads;
+  std::vector<Value *> params, StructValues, ReloadOutputs;
 
   Module *M = newFunction->getParent();
   LLVMContext &Context = M->getContext();
   const DataLayout &DL = M->getDataLayout();
   CallInst *call = nullptr;
 
   // Add inputs as params, or to be filled into the struct
   unsigned ArgNo = 0;
if (AggregateArgs) {
       Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i);
       GetElementPtrInst *GEP = GetElementPtrInst::Create(
           StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName());
       codeReplacer->getInstList().push_back(GEP);
       Output = GEP;
     } else {
       Output = ReloadOutputs[i];
     }
-    LoadInst *load = new LoadInst(outputs[i]->getType(), Output,
-                                  outputs[i]->getName() + ".reload");
-    Reloads.push_back(load);
-    codeReplacer->getInstList().push_back(load);
     std::vector<User *> Users(outputs[i]->user_begin(), outputs[i]->user_end());
     for (unsigned u = 0, e = Users.size(); u != e; ++u) {
       Instruction *inst = cast<Instruction>(Users[u]);
-      if (!Blocks.count(inst->getParent()))
-        inst->replaceUsesOfWith(outputs[i], load);
+      if (Blocks.count(inst->getParent()))
+        continue;
+      LoadInst *load = new LoadInst(outputs[i]->getType(), Output,
+                                    outputs[i]->getName() + ".reload", inst);
     }
   }
 
   // Now we can emit a switch statement using the call as a value.
   SwitchInst *TheSwitch =
       SwitchInst::Create(Constant::getNullValue(Type::getInt16Ty(Context)),
                          codeReplacer, 0, codeReplacer);
 

llvm/lib/Transforms/Utils/Local.cpp

if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
 
     // Assumptions are dead if their condition is trivially true.  Guards on
     // true are operationally no-ops.  In the future we can consider more
     // sophisticated tradeoffs for guards considering potential for check
     // widening, but for now we keep things simple.
     if (II->getIntrinsicID() == Intrinsic::assume ||
         II->getIntrinsicID() == Intrinsic::experimental_guard) {
       if (ConstantInt *Cond = dyn_cast<ConstantInt>(II->getArgOperand(0)))
-        return !Cond->isZero();
+        return !Cond->isZero() && !II->hasOperandBundles();
 
       return false;
     }
   }
 
   if (isAllocLikeFn(I, TLI))
     return true;
 

llvm/test/Transforms/AlignmentFromAssumptions/simple.ll

 target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128"
 ; RUN: opt < %s -alignment-from-assumptions -S | FileCheck %s
+; RUN: opt < %s -assumption-outliner -assumption-outliner-aggressive=false -alignment-from-assumptions -S | FileCheck %s
+; RUN: opt < %s -assumption-outliner -assumption-outliner-aggressive=true -alignment-from-assumptions -S | FileCheck %s
 ; RUN: opt < %s -passes=alignment-from-assumptions -S | FileCheck %s
 
 define i32 @foo(i32* nocapture %a) nounwind uwtable readonly {
 entry:
   %ptrint = ptrtoint i32* %a to i64
   %maskedptr = and i64 %ptrint, 31
   %maskcond = icmp eq i64 %maskedptr, 0
   tail call void @llvm.assume(i1 %maskcond)

llvm/test/Transforms/AlignmentFromAssumptions/simple32.ll

 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
 ; RUN: opt < %s -alignment-from-assumptions -S | FileCheck %s
+; RUN: opt < %s -assumption-outliner -assumption-outliner-aggressive=false -alignment-from-assumptions -S | FileCheck %s
+; RUN: opt < %s -assumption-outliner -assumption-outliner-aggressive=true -alignment-from-assumptions -S | FileCheck %s
 ; RUN: opt < %s -passes=alignment-from-assumptions -S | FileCheck %s
 
 define i32 @foo(i32* nocapture %a) nounwind uwtable readonly {
 entry:
   %ptrint = ptrtoint i32* %a to i64
   %maskedptr = and i64 %ptrint, 31
   %maskcond = icmp eq i64 %maskedptr, 0
   tail call void @llvm.assume(i1 %maskcond)

llvm/test/Transforms/GVN/assume-equal.ll

-; RUN: opt < %s -gvn -S | FileCheck %s
+; RUN: opt < %s -gvn -S | FileCheck %s --check-prefixes=CHECK,INLINED
+; RUN: opt < %s -assumption-outliner -gvn -S | FileCheck %s
 
 %struct.A = type { i32 (...)** }
 @_ZTV1A = available_externally unnamed_addr constant [4 x i8*] [i8* null, i8* bitcast (i8** @_ZTI1A to i8*), i8* bitcast (i32 (%struct.A*)* @_ZN1A3fooEv to i8*), i8* bitcast (i32 (%struct.A*)* @_ZN1A3barEv to i8*)], align 8
 @_ZTI1A = external constant i8*
 
 ; Checks if indirect calls can be replaced with direct
 ; assuming that %vtable == @_ZTV1A (with alignment).
 ; Checking const propagation across other BBs
entry:
   store float %p, float* %p.addr, align 4
   
   store float 3.000000e+00, float* %f, align 4
   %0 = load float, float* %p.addr, align 4
   %1 = load float, float* %f, align 4
   %cmp = fcmp oeq float %1, %0 ; note const on lhs
   call void @llvm.assume(i1 %cmp)
   
-  ; CHECK: ret float 3.000000e+00
+  ; INLINED: ret float 3.000000e+00
   ret float %0
 }
 
 ; CHECK-LABEL: define float @_Z1hf(float %p)
 
 define float @_Z1hf(float %p) {
 entry:
   %p.addr = alloca float, align 4
entry:
   %cmp = icmp eq i32 %p, 42
   call void @llvm.assume(i1 %cmp)
   
   ; CHECK: br i1 true, label %bb2, label %bb2
   br i1 %cmp, label %bb2, label %bb2
 bb2:
    ; CHECK-NOT: %cmp2 = 
   %cmp2 = icmp eq i32 %p, 42
-  ; CHECK-NOT: call void @llvm.assume(
+  ; INLINED-NOT: call void @llvm.assume(
   call void @llvm.assume(i1 %cmp2)
   
   ; CHECK: br i1 true, label %bb2, label %bb2
   br i1 %cmp, label %bb2, label %bb2
   
   ; CHECK: ret i32 42
   ret i32 %p
 }
 
 ; CHECK-LABEL: define i32 @_Z1ik(i32 %p)
 define i32 @_Z1ik(i32 %p) {
 entry:
   %cmp = icmp eq i32 %p, 42
   call void @llvm.assume(i1 %cmp)
   
   ; CHECK: br i1 true, label %bb2, label %bb3
   br i1 %cmp, label %bb2, label %bb3
 bb2:
   ; CHECK-NOT: %cmp3 = 
   %cmp3 = icmp eq i32 %p, 43
-  ; CHECK: store i8 undef, i8* null
+  ; INLINED: store i8 undef, i8* null
   call void @llvm.assume(i1 %cmp3)
   ret i32 15
 bb3:
   ret i32 17
 }
 
 ; This test checks if GVN can do the constant propagation correctly
 ; when there are multiple uses of the same assume value in the 

llvm/test/Transforms/InstCombine/assume.ll

 ; RUN: opt < %s -instcombine -S | FileCheck %s
+; RUN: opt < %s -assumption-outliner -instcombine -S | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define i32 @foo1(i32* %a) #0 {
 entry:
   %0 = load i32, i32* %a, align 4
 
 ; Check that the alignment has been upgraded and that the assume has not

llvm/test/Transforms/InstSimplify/assume.ll

 ; NOTE: Assertions have been autogenerated by update_test_checks.py
 ; RUN: opt -instsimplify -S < %s 2>&1 -pass-remarks-analysis=.* | FileCheck %s
+; RUN: opt -assumption-outliner -instsimplify -S < %s 2>&1 -pass-remarks-analysis=.* | FileCheck %s
 
 ; Verify that warnings are emitted for the 2nd and 3rd tests.
 
-; CHECK: remark: /tmp/s.c:1:13: Detected conflicting code assumptions.
-; CHECK: remark: /tmp/s.c:4:10: Detected conflicting code assumptions.
-; CHECK: remark: /tmp/s.c:5:50: Detected conflicting code assumptions.
 
 define void @test1() {
 ; CHECK-LABEL: @test1(
 ; CHECK:         ret void
 ;
   call void @llvm.assume(i1 1)
   ret void
 
 }
 
 ; The alloca guarantees that the low bits of %a are zero because of alignment.
 ; The assume says the opposite. The assume is processed last, so that's the 
 ; return value. There's no way to win (we can't undo transforms that happened
 ; based on half-truths), so just don't crash.
 
 define i64 @PR31809() !dbg !7 {
 ; CHECK-LABEL: @PR31809(
-; CHECK-NEXT:    ret i64 3
+; CHECK:    ret i64 
 ;
   %a = alloca i32
   %t1 = ptrtoint i32* %a to i64, !dbg !9
   %cond = icmp eq i64 %t1, 3
   call void @llvm.assume(i1 %cond)
   ret i64 %t1
 }
 
 ; Similar to above: there's no way to know which assumption is truthful,
 ; so just don't crash.
 
 define i8 @conflicting_assumptions(i8 %x) !dbg !10 {
 ; CHECK-LABEL: @conflicting_assumptions(
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[X:%.*]], 1, !dbg !10
-; CHECK-NEXT:    call void @llvm.assume(i1 false)
-; CHECK-NEXT:    [[COND2:%.*]] = icmp eq i8 [[X]], 4
-; CHECK-NEXT:    call void @llvm.assume(i1 [[COND2]])
+; CHECK:    [[ADD:%.*]] = add i8 [[X:%.*]], 1, !dbg
+; CHECK-NEXT:    call void @llvm.assume(
+; CHECK:    call void @llvm.assume(
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %add = add i8 %x, 1, !dbg !11
   %cond1 = icmp eq i8 %x, 3
   call void @llvm.assume(i1 %cond1)
   %cond2 = icmp eq i8 %x, 4
   call void @llvm.assume(i1 %cond2)
   ret i8 %add
 }
 
 ; Another case of conflicting assumptions. This would crash because we'd
 ; try to set more known bits than existed in the known bits struct.
 
 define void @PR36270(i32 %b) !dbg !13 {
 ; CHECK-LABEL: @PR36270(
-; CHECK-NEXT:    tail call void @llvm.assume(i1 false)
-; CHECK-NEXT:    unreachable
+; CHECK:    call void @llvm.assume(
+; CHECK:    unreachable
 ;
   %B7 = xor i32 -1, 2147483647
   %and1 = and i32 %b, 3
   %B12 = lshr i32 %B7, %and1, !dbg !14
   %C1 = icmp ult i32 %and1, %B12
   tail call void @llvm.assume(i1 %C1)
   %cmp2 = icmp eq i32 0, %B12
   tail call void @llvm.assume(i1 %cmp2)

llvm/test/Transforms/JumpThreading/assume-edge-dom.ll

 ; RUN: opt -S -jump-threading < %s | FileCheck %s
+; RUN: opt -S -assumption-outliner -jump-threading < %s | FileCheck %s
 
 declare i8* @escape()
 declare void @llvm.assume(i1)
 
 define i1 @test1(i1 %cond) {
 entry:
     br i1 %cond, label %taken, label %not_taken
 

llvm/test/Transforms/JumpThreading/assume.ll

 ; RUN: opt -S -jump-threading -dce < %s | FileCheck %s
+; RUN: opt -S -assumption-outliner -jump-threading -dce < %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Function Attrs: nounwind uwtable
 define i32 @test1(i32 %a, i32 %b) #0 {
 entry:
   %cmp = icmp sgt i32 %a, 5
   tail call void @llvm.assume(i1 %cmp)
   %cmp1 = icmp sgt i32 %b, 1234
   br i1 %cmp1, label %if.then, label %if.else
 
 ; CHECK-LABEL: @test1
-; CHECK: icmp sgt i32 %a, 5
 ; CHECK: call void @llvm.assume
 ; CHECK-NOT: icmp sgt i32 %a, 3
 ; CHECK: ret i32
 
 if.then:                                          ; preds = %entry
   %cmp2 = icmp sgt i32 %a, 3
   br i1 %cmp2, label %if.then3, label %return
 

 define i32 @test2(i32 %a) #0 {
 entry:
   %cmp = icmp sgt i32 %a, 5
   tail call void @llvm.assume(i1 %cmp)
   %cmp1 = icmp sgt i32 %a, 3
   br i1 %cmp1, label %if.then, label %return
 
 ; CHECK-LABEL: @test2
-; CHECK: icmp sgt i32 %a, 5
-; CHECK: tail call void @llvm.assume
+; CHECK: call void @llvm.assume
 ; CHECK: tail call void (...) @bar()
 ; CHECK: ret i32 1
 
 
 if.then:                                          ; preds = %entry
   tail call void (...) @bar() #1
   br label %return
 
 return:                                           ; preds = %entry, %if.then
   %retval.0 = phi i32 [ 1, %if.then ], [ 0, %entry ]
   ret i32 %retval.0
 }
 
 @g = external global i32
 
 ; Check that we do prove a fact using an assume within the block.
 ; We can fold the assume based on the semantics of assume.
 define void @can_fold_assume(i32* %array) {
 ; CHECK-LABEL: @can_fold_assume
-; CHECK-NOT: call void @llvm.assume
 ; CHECK-NOT: br
 ; CHECK: ret void
   %notnull = icmp ne i32* %array, null
   call void @llvm.assume(i1 %notnull)
   br i1 %notnull, label %normal, label %error
 
 normal:
   ret void
 
 error:
   store atomic i32 0, i32* @g unordered, align 4
   ret void
 }
 
 declare void @f(i1)
 declare void @exit()
 ; We can fold the assume but not the uses before the assume.
 define void @cannot_fold_use_before_assume(i32* %array) {
 ; CHECK-LABEL:@cannot_fold_use_before_assume
 ; CHECK: @f(i1 %notnull)
 ; CHECK-NEXT: exit()
-; CHECK-NOT: assume
-; CHECK-NEXT: ret void
+; CHECK-NOT: notnull
+; CHECK: ret void
+; CHECK-NOT: notnull
   %notnull = icmp ne i32* %array, null
   call void @f(i1 %notnull)
   call void @exit()
   call void @llvm.assume(i1 %notnull)
   br i1 %notnull, label %normal, label %error
 
 normal:
   ret void
 
 error:
   store atomic i32 0, i32* @g unordered, align 4
   ret void
 }
 
 declare void @dummy(i1) nounwind argmemonly
 define void @can_fold_some_use_before_assume(i32* %array) {
 
 ; CHECK-LABEL:@can_fold_some_use_before_assume
 ; CHECK: @f(i1 %notnull)
 ; CHECK-NEXT: @dummy(i1 true)
-; CHECK-NOT: assume
-; CHECK-NEXT: ret void
+; CHECK-NOT: notnull
+; CHECK: ret void
+; CHECK-NOT: notnull
   %notnull = icmp ne i32* %array, null
   call void @f(i1 %notnull)
   call void @dummy(i1 %notnull)
   call void @llvm.assume(i1 %notnull)
   br i1 %notnull, label %normal, label %error
 
 normal:
   ret void
 
 error:
   store atomic i32 0, i32* @g unordered, align 4
   ret void
 
 }
 
 ; FIXME: can fold assume and all uses before/after assume.
 ; because the trapping exit call is after the assume.
 define void @can_fold_assume_and_all_uses(i32* %array) {
 ; CHECK-LABEL:@can_fold_assume_and_all_uses
 ; CHECK: @dummy(i1 %notnull)
-; CHECK-NEXT: assume(i1 %notnull)
+; CHECK-NEXT: assume
 ; CHECK-NEXT: exit()
 ; CHECK-NEXT: %notnull2 = or i1 true, false
 ; CHECK-NEXT: @f(i1 %notnull2)
 ; CHECK-NEXT: ret void
   %notnull = icmp ne i32* %array, null
   call void @dummy(i1 %notnull)
   call void @llvm.assume(i1 %notnull)
   call void @exit()

 
 declare void @fz(i8)
 ; FIXME: We can fold assume to true, and the use after assume, but we do not do so
 ; currently, because of the function call after the assume.
 define void @can_fold_assume2(i32* %array) {
 
 ; CHECK-LABEL:@can_fold_assume2
 ; CHECK: @f(i1 %notnull)
-; CHECK-NEXT: assume(i1 %notnull)
+; CHECK-NEXT: assume
 ; CHECK-NEXT: znotnull = zext i1 %notnull to i8
 ; CHECK-NEXT: @f(i1 %notnull)
 ; CHECK-NEXT: @f(i1 true)
 ; CHECK-NEXT: @fz(i8 %znotnull)
 ; CHECK-NEXT: ret void
   %notnull = icmp ne i32* %array, null
   call void @f(i1 %notnull)
   call void @llvm.assume(i1 %notnull)

 
 declare void @llvm.experimental.guard(i1, ...)
 ; FIXME: We can fold assume to true, but we do not do so
 ; because of the guard following the assume.
 define void @can_fold_assume3(i32* %array){
 
 ; CHECK-LABEL:@can_fold_assume3
 ; CHECK: @f(i1 %notnull)
-; CHECK-NEXT: assume(i1 %notnull)
+; CHECK-NEXT: assume
 ; CHECK-NEXT: guard(i1 %notnull)
 ; CHECK-NEXT: znotnull = zext i1 true to i8
 ; CHECK-NEXT: @f(i1 true)
 ; CHECK-NEXT: @fz(i8 %znotnull)
 ; CHECK-NEXT: ret void
   %notnull = icmp ne i32* %array, null
   call void @f(i1 %notnull)
   call void @llvm.assume(i1 %notnull)
error:
   ret void
 }
 
 
 ; can fold all uses and remove the cond
 define void @can_fold_assume4(i32* %array) {
 ; CHECK-LABEL: can_fold_assume4
 ; CHECK-NOT: notnull
+; CHECK: exit
+; CHECK-NOT: notnull
 ; CHECK: dummy(i1 true)
-; CHECK-NEXT: ret void
+; CHECK-NOT: notnull
+; CHECK: ret void
   %notnull = icmp ne i32* %array, null
   call void @exit()
   call void @dummy(i1 %notnull)
   call void @llvm.assume(i1 %notnull)
   br i1 %notnull, label %normal, label %error
 
 normal:
   ret void

llvm/test/Transforms/JumpThreading/pr33917.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -jump-threading -correlated-propagation %s -S | FileCheck %s
+; RUN: opt -assumption-outliner -jump-threading -correlated-propagation %s -S | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 declare i8* @foo()
 
 declare i32 @rust_eh_personality() unnamed_addr
 

llvm/test/Transforms/JumpThreading/pr36133.ll

 ; RUN: opt -jump-threading -S < %s | FileCheck %s
+; RUN: opt -assumption-outliner -jump-threading -S < %s | FileCheck %s
 @global = external global i8*, align 8
 
 define i32 @foo(i32 %arg) {
 ; CHECK-LABEL: @foo
 ; CHECK-LABEL: bb:
 ; CHECK: icmp eq
 ; CHECK-NEXT: br i1 %tmp1, label %bb7, label %bb7
 bb:

llvm/test/Transforms/LoopVectorize/X86/assume.ll

 ; RUN: opt < %s  -loop-vectorize -mtriple=x86_64-apple-macosx10.8.0 -mcpu=corei7 -S | FileCheck %s
+; RUN: opt < %s -assumption-outliner -loop-vectorize -mtriple=x86_64-apple-macosx10.8.0 -mcpu=corei7 -S | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Function Attrs: nounwind uwtable
 define void @test1(float* noalias nocapture %a, float* noalias nocapture readonly %b) #0 {
 entry:
   br label %for.body
 

llvm/test/Transforms/NewGVN/assumes.ll

 ; RUN: opt < %s -newgvn -S | FileCheck %s
+; RUN: opt < %s -assumption-outliner -newgvn -S | FileCheck %s
 
 ; CHECK-LABEL: @test1
 ; CHECK: ret i32 %arg
 define i32 @test1(i32 %arg) {
   %cmp = icmp sge i32 %arg, 5
   call void @llvm.assume(i1 %cmp)
   ret i32 %arg
 }

llvm/test/Transforms/WholeProgramDevirt/branch-funnel.ll

 ; RUN: opt -S -wholeprogramdevirt %s | FileCheck --check-prefixes=CHECK,RETP %s
+; RUN: opt -S -assumption-outliner -wholeprogramdevirt %s | FileCheck --check-prefixes=CHECK,RETP %s
 ; RUN: sed -e 's,+retpoline,-retpoline,g' %s | opt -S -wholeprogramdevirt | FileCheck --check-prefixes=CHECK,NORETP %s
 
 ; RUN: opt -wholeprogramdevirt -wholeprogramdevirt-summary-action=export -wholeprogramdevirt-read-summary=%S/Inputs/export.yaml -wholeprogramdevirt-write-summary=%t -S -o - %s | FileCheck --check-prefixes=CHECK,RETP %s
+; RUN: opt -assumption-outliner -wholeprogramdevirt -wholeprogramdevirt-summary-action=export -wholeprogramdevirt-read-summary=%S/Inputs/export.yaml -wholeprogramdevirt-write-summary=%t -S -o - %s | FileCheck --check-prefixes=CHECK,RETP %s
 
 ; RUN: opt -wholeprogramdevirt -wholeprogramdevirt-summary-action=export -wholeprogramdevirt-read-summary=%S/Inputs/export.yaml -wholeprogramdevirt-write-summary=%t  -O3 -S -o - %s | FileCheck --check-prefixes=CHECK %s
+; RUN: opt --assumption-outliner -wholeprogramdevirt -wholeprogramdevirt-summary-action=export -wholeprogramdevirt-read-summary=%S/Inputs/export.yaml -wholeprogramdevirt-write-summary=%t  -O3 -S -o - %s | FileCheck --check-prefixes=CHECK %s
 
 ; RUN: FileCheck --check-prefix=SUMMARY %s < %t
 
 ; SUMMARY:      TypeIdMap:       
 ; SUMMARY-NEXT:   typeid3:
 ; SUMMARY-NEXT:     TTRes:           
 ; SUMMARY-NEXT:       Kind:            Unsat
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0

llvm/test/Transforms/WholeProgramDevirt/virtual-const-prop-end.ll

 ; RUN: opt -S -wholeprogramdevirt %s | FileCheck %s
+; RUN: opt -S -assumption-outliner -wholeprogramdevirt %s | FileCheck %s
 
 target datalayout = "e-p:64:64"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; CHECK: [[VT1DATA:@[^ ]*]] = private constant { [0 x i8], [4 x i8*], [5 x i8] } { [0 x i8] zeroinitializer, [4 x i8*] [i8* null, i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i32 (i8*)* @vf1i32 to i8*)], [5 x i8] c"\01\00\00\00\01" }, !type [[T8:![0-9]+]]
 @vt1 = constant [4 x i8*] [
 i8* null,
 i8* bitcast (i1 (i8*)* @vf0i1 to i8*),