Home | History | Annotate | Line # | Download | only in Utils 
      1 //===- AssumeBundleBuilder.cpp - tools to preserve informations -*- C++ -*-===//
      2 //
      3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
      4 // See https://llvm.org/LICENSE.txt for license information.
      5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
      6 //
      7 //===----------------------------------------------------------------------===//
      8 
      9 #include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
     10 #include "llvm/ADT/DepthFirstIterator.h"
     11 #include "llvm/ADT/MapVector.h"
     12 #include "llvm/ADT/Statistic.h"
     13 #include "llvm/Analysis/AssumeBundleQueries.h"
     14 #include "llvm/Analysis/AssumptionCache.h"
     15 #include "llvm/Analysis/ValueTracking.h"
     16 #include "llvm/IR/Dominators.h"
     17 #include "llvm/IR/Function.h"
     18 #include "llvm/IR/InstIterator.h"
     19 #include "llvm/IR/IntrinsicInst.h"
     20 #include "llvm/IR/Module.h"
     21 #include "llvm/InitializePasses.h"
     22 #include "llvm/Support/CommandLine.h"
     23 #include "llvm/Support/DebugCounter.h"
     24 #include "llvm/Transforms/Utils/Local.h"
     25 
     26 using namespace llvm;
     27 
     28 namespace llvm {
     29 cl::opt<bool> ShouldPreserveAllAttributes(
     30     "assume-preserve-all", cl::init(false), cl::Hidden,
     31     cl::desc("enable preservation of all attrbitues. even those that are "
     32              "unlikely to be usefull"));
     33 
     34 cl::opt<bool> EnableKnowledgeRetention(
     35     "enable-knowledge-retention", cl::init(false), cl::Hidden,
     36     cl::desc(
     37         "enable preservation of attributes throughout code transformation"));
     38 } // namespace llvm
     39 
     40 #define DEBUG_TYPE "assume-builder"
     41 
     42 STATISTIC(NumAssumeBuilt, "Number of assume built by the assume builder");
     43 STATISTIC(NumBundlesInAssumes, "Total number of Bundles in the assume built");
     44 STATISTIC(NumAssumesMerged,
     45           "Number of assume merged by the assume simplify pass");
     46 STATISTIC(NumAssumesRemoved,
     47           "Number of assume removed by the assume simplify pass");
     48 
     49 DEBUG_COUNTER(BuildAssumeCounter, "assume-builder-counter",
     50               "Controls which assumes gets created");
     51 
     52 namespace {
     53 
     54 bool isUsefullToPreserve(Attribute::AttrKind Kind) {
     55   switch (Kind) {
     56     case Attribute::NonNull:
     57     case Attribute::NoUndef:
     58     case Attribute::Alignment:
     59     case Attribute::Dereferenceable:
     60     case Attribute::DereferenceableOrNull:
     61     case Attribute::Cold:
     62       return true;
     63     default:
     64       return false;
     65   }
     66 }
     67 
     68 /// This function will try to transform the given knowledge into a more
     69 /// canonical one. the canonical knowledge maybe the given one.
     70 RetainedKnowledge canonicalizedKnowledge(RetainedKnowledge RK, DataLayout DL) {
     71   switch (RK.AttrKind) {
     72   default:
     73     return RK;
     74   case Attribute::NonNull:
     75     RK.WasOn = getUnderlyingObject(RK.WasOn);
     76     return RK;
     77   case Attribute::Alignment: {
     78     Value *V = RK.WasOn->stripInBoundsOffsets([&](const Value *Strip) {
     79       if (auto *GEP = dyn_cast<GEPOperator>(Strip))
     80         RK.ArgValue =
     81             MinAlign(RK.ArgValue, GEP->getMaxPreservedAlignment(DL).value());
     82     });
     83     RK.WasOn = V;
     84     return RK;
     85   }
     86   case Attribute::Dereferenceable:
     87   case Attribute::DereferenceableOrNull: {
     88     int64_t Offset = 0;
     89     Value *V = GetPointerBaseWithConstantOffset(RK.WasOn, Offset, DL,
     90                                                 /*AllowNonInBounds*/ false);
     91     if (Offset < 0)
     92       return RK;
     93     RK.ArgValue = RK.ArgValue + Offset;
     94     RK.WasOn = V;
     95   }
     96   }
     97   return RK;
     98 }
     99 
    100 /// This class contain all knowledge that have been gather while building an
    101 /// llvm.assume and the function to manipulate it.
    102 struct AssumeBuilderState {
    103   Module *M;
    104 
    105   using MapKey = std::pair<Value *, Attribute::AttrKind>;
    106   SmallMapVector<MapKey, unsigned, 8> AssumedKnowledgeMap;
    107   Instruction *InstBeingModified = nullptr;
    108   AssumptionCache* AC = nullptr;
    109   DominatorTree* DT = nullptr;
    110 
    111   AssumeBuilderState(Module *M, Instruction *I = nullptr,
    112                      AssumptionCache *AC = nullptr, DominatorTree *DT = nullptr)
    113       : M(M), InstBeingModified(I), AC(AC), DT(DT) {}
    114 
    115   bool tryToPreserveWithoutAddingAssume(RetainedKnowledge RK) {
    116     if (!InstBeingModified || !RK.WasOn)
    117       return false;
    118     bool HasBeenPreserved = false;
    119     Use* ToUpdate = nullptr;
    120     getKnowledgeForValue(
    121         RK.WasOn, {RK.AttrKind}, AC,
    122         [&](RetainedKnowledge RKOther, Instruction *Assume,
    123             const CallInst::BundleOpInfo *Bundle) {
    124           if (!isValidAssumeForContext(Assume, InstBeingModified, DT))
    125             return false;
    126           if (RKOther.ArgValue >= RK.ArgValue) {
    127             HasBeenPreserved = true;
    128             return true;
    129           } else if (isValidAssumeForContext(InstBeingModified, Assume, DT)) {
    130             HasBeenPreserved = true;
    131             IntrinsicInst *Intr = cast<IntrinsicInst>(Assume);
    132             ToUpdate = &Intr->op_begin()[Bundle->Begin + ABA_Argument];
    133             return true;
    134           }
    135           return false;
    136         });
    137     if (ToUpdate)
    138       ToUpdate->set(
    139           ConstantInt::get(Type::getInt64Ty(M->getContext()), RK.ArgValue));
    140     return HasBeenPreserved;
    141   }
    142 
    143   bool isKnowledgeWorthPreserving(RetainedKnowledge RK) {
    144     if (!RK)
    145       return false;
    146     if (!RK.WasOn)
    147       return true;
    148     if (RK.WasOn->getType()->isPointerTy()) {
    149       Value *UnderlyingPtr = getUnderlyingObject(RK.WasOn);
    150       if (isa<AllocaInst>(UnderlyingPtr) || isa<GlobalValue>(UnderlyingPtr))
    151         return false;
    152     }
    153     if (auto *Arg = dyn_cast<Argument>(RK.WasOn)) {
    154       if (Arg->hasAttribute(RK.AttrKind) &&
    155           (!Attribute::doesAttrKindHaveArgument(RK.AttrKind) ||
    156            Arg->getAttribute(RK.AttrKind).getValueAsInt() >= RK.ArgValue))
    157         return false;
    158       return true;
    159     }
    160     if (auto *Inst = dyn_cast<Instruction>(RK.WasOn))
    161       if (wouldInstructionBeTriviallyDead(Inst)) {
    162         if (RK.WasOn->use_empty())
    163           return false;
    164         Use *SingleUse = RK.WasOn->getSingleUndroppableUse();
    165         if (SingleUse && SingleUse->getUser() == InstBeingModified)
    166           return false;
    167       }
    168     return true;
    169   }
    170 
    171   void addKnowledge(RetainedKnowledge RK) {
    172     RK = canonicalizedKnowledge(RK, M->getDataLayout());
    173 
    174     if (!isKnowledgeWorthPreserving(RK))
    175       return;
    176 
    177     if (tryToPreserveWithoutAddingAssume(RK))
    178       return;
    179     MapKey Key{RK.WasOn, RK.AttrKind};
    180     auto Lookup = AssumedKnowledgeMap.find(Key);
    181     if (Lookup == AssumedKnowledgeMap.end()) {
    182       AssumedKnowledgeMap[Key] = RK.ArgValue;
    183       return;
    184     }
    185     assert(((Lookup->second == 0 && RK.ArgValue == 0) ||
    186             (Lookup->second != 0 && RK.ArgValue != 0)) &&
    187            "inconsistent argument value");
    188 
    189     /// This is only desirable because for all attributes taking an argument
    190     /// higher is better.
    191     Lookup->second = std::max(Lookup->second, RK.ArgValue);
    192   }
    193 
    194   void addAttribute(Attribute Attr, Value *WasOn) {
    195     if (Attr.isTypeAttribute() || Attr.isStringAttribute() ||
    196         (!ShouldPreserveAllAttributes &&
    197          !isUsefullToPreserve(Attr.getKindAsEnum())))
    198       return;
    199     unsigned AttrArg = 0;
    200     if (Attr.isIntAttribute())
    201       AttrArg = Attr.getValueAsInt();
    202     addKnowledge({Attr.getKindAsEnum(), AttrArg, WasOn});
    203   }
    204 
    205   void addCall(const CallBase *Call) {
    206     auto addAttrList = [&](AttributeList AttrList) {
    207       for (unsigned Idx = AttributeList::FirstArgIndex;
    208            Idx < AttrList.getNumAttrSets(); Idx++)
    209         for (Attribute Attr : AttrList.getAttributes(Idx)) {
    210           bool IsPoisonAttr = Attr.hasAttribute(Attribute::NonNull) ||
    211                               Attr.hasAttribute(Attribute::Alignment);
    212           if (!IsPoisonAttr || Call->isPassingUndefUB(Idx - 1))
    213             addAttribute(Attr, Call->getArgOperand(Idx - 1));
    214         }
    215       for (Attribute Attr : AttrList.getFnAttributes())
    216         addAttribute(Attr, nullptr);
    217     };
    218     addAttrList(Call->getAttributes());
    219     if (Function *Fn = Call->getCalledFunction())
    220       addAttrList(Fn->getAttributes());
    221   }
    222 
    223   AssumeInst *build() {
    224     if (AssumedKnowledgeMap.empty())
    225       return nullptr;
    226     if (!DebugCounter::shouldExecute(BuildAssumeCounter))
    227       return nullptr;
    228     Function *FnAssume = Intrinsic::getDeclaration(M, Intrinsic::assume);
    229     LLVMContext &C = M->getContext();
    230     SmallVector<OperandBundleDef, 8> OpBundle;
    231     for (auto &MapElem : AssumedKnowledgeMap) {
    232       SmallVector<Value *, 2> Args;
    233       if (MapElem.first.first)
    234         Args.push_back(MapElem.first.first);
    235 
    236       /// This is only valid because for all attribute that currently exist a
    237       /// value of 0 is useless. and should not be preserved.
    238       if (MapElem.second)
    239         Args.push_back(ConstantInt::get(Type::getInt64Ty(M->getContext()),
    240                                         MapElem.second));
    241       OpBundle.push_back(OperandBundleDefT<Value *>(
    242           std::string(Attribute::getNameFromAttrKind(MapElem.first.second)),
    243           Args));
    244       NumBundlesInAssumes++;
    245     }
    246     NumAssumeBuilt++;
    247     return cast<AssumeInst>(CallInst::Create(
    248         FnAssume, ArrayRef<Value *>({ConstantInt::getTrue(C)}), OpBundle));
    249   }
    250 
    251   void addAccessedPtr(Instruction *MemInst, Value *Pointer, Type *AccType,
    252                       MaybeAlign MA) {
    253     unsigned DerefSize = MemInst->getModule()
    254                              ->getDataLayout()
    255                              .getTypeStoreSize(AccType)
    256                              .getKnownMinSize();
    257     if (DerefSize != 0) {
    258       addKnowledge({Attribute::Dereferenceable, DerefSize, Pointer});
    259       if (!NullPointerIsDefined(MemInst->getFunction(),
    260                                 Pointer->getType()->getPointerAddressSpace()))
    261         addKnowledge({Attribute::NonNull, 0u, Pointer});
    262     }
    263     if (MA.valueOrOne() > 1)
    264       addKnowledge(
    265           {Attribute::Alignment, unsigned(MA.valueOrOne().value()), Pointer});
    266   }
    267 
    268   void addInstruction(Instruction *I) {
    269     if (auto *Call = dyn_cast<CallBase>(I))
    270       return addCall(Call);
    271     if (auto *Load = dyn_cast<LoadInst>(I))
    272       return addAccessedPtr(I, Load->getPointerOperand(), Load->getType(),
    273                             Load->getAlign());
    274     if (auto *Store = dyn_cast<StoreInst>(I))
    275       return addAccessedPtr(I, Store->getPointerOperand(),
    276                             Store->getValueOperand()->getType(),
    277                             Store->getAlign());
    278     // TODO: Add support for the other Instructions.
    279     // TODO: Maybe we should look around and merge with other llvm.assume.
    280   }
    281 };
    282 
    283 } // namespace
    284 
    285 AssumeInst *llvm::buildAssumeFromInst(Instruction *I) {
    286   if (!EnableKnowledgeRetention)
    287     return nullptr;
    288   AssumeBuilderState Builder(I->getModule());
    289   Builder.addInstruction(I);
    290   return Builder.build();
    291 }
    292 
    293 void llvm::salvageKnowledge(Instruction *I, AssumptionCache *AC,
    294                             DominatorTree *DT) {
    295   if (!EnableKnowledgeRetention || I->isTerminator())
    296     return;
    297   AssumeBuilderState Builder(I->getModule(), I, AC, DT);
    298   Builder.addInstruction(I);
    299   if (auto *Intr = Builder.build()) {
    300     Intr->insertBefore(I);
    301     if (AC)
    302       AC->registerAssumption(Intr);
    303   }
    304 }
    305 
    306 AssumeInst *
    307 llvm::buildAssumeFromKnowledge(ArrayRef<RetainedKnowledge> Knowledge,
    308                                Instruction *CtxI, AssumptionCache *AC,
    309                                DominatorTree *DT) {
    310   AssumeBuilderState Builder(CtxI->getModule(), CtxI, AC, DT);
    311   for (const RetainedKnowledge &RK : Knowledge)
    312     Builder.addKnowledge(RK);
    313   return Builder.build();
    314 }
    315 
    316 RetainedKnowledge llvm::simplifyRetainedKnowledge(AssumeInst *Assume,
    317                                                   RetainedKnowledge RK,
    318                                                   AssumptionCache *AC,
    319                                                   DominatorTree *DT) {
    320   AssumeBuilderState Builder(Assume->getModule(), Assume, AC, DT);
    321   RK = canonicalizedKnowledge(RK, Assume->getModule()->getDataLayout());
    322 
    323   if (!Builder.isKnowledgeWorthPreserving(RK))
    324     return RetainedKnowledge::none();
    325 
    326   if (Builder.tryToPreserveWithoutAddingAssume(RK))
    327     return RetainedKnowledge::none();
    328   return RK;
    329 }
    330 
    331 namespace {
    332 
    333 struct AssumeSimplify {
    334   Function &F;
    335   AssumptionCache &AC;
    336   DominatorTree *DT;
    337   LLVMContext &C;
    338   SmallDenseSet<IntrinsicInst *> CleanupToDo;
    339   StringMapEntry<uint32_t> *IgnoreTag;
    340   SmallDenseMap<BasicBlock *, SmallVector<IntrinsicInst *, 4>, 8> BBToAssume;
    341   bool MadeChange = false;
    342 
    343   AssumeSimplify(Function &F, AssumptionCache &AC, DominatorTree *DT,
    344                  LLVMContext &C)
    345       : F(F), AC(AC), DT(DT), C(C),
    346         IgnoreTag(C.getOrInsertBundleTag(IgnoreBundleTag)) {}
    347 
    348   void buildMapping(bool FilterBooleanArgument) {
    349     BBToAssume.clear();
    350     for (Value *V : AC.assumptions()) {
    351       if (!V)
    352         continue;
    353       IntrinsicInst *Assume = cast<IntrinsicInst>(V);
    354       if (FilterBooleanArgument) {
    355         auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0));
    356         if (!Arg || Arg->isZero())
    357           continue;
    358       }
    359       BBToAssume[Assume->getParent()].push_back(Assume);
    360     }
    361 
    362     for (auto &Elem : BBToAssume) {
    363       llvm::sort(Elem.second,
    364                  [](const IntrinsicInst *LHS, const IntrinsicInst *RHS) {
    365                    return LHS->comesBefore(RHS);
    366                  });
    367     }
    368   }
    369 
    370   /// Remove all asumes in CleanupToDo if there boolean argument is true and
    371   /// ForceCleanup is set or the assume doesn't hold valuable knowledge.
    372   void RunCleanup(bool ForceCleanup) {
    373     for (IntrinsicInst *Assume : CleanupToDo) {
    374       auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0));
    375       if (!Arg || Arg->isZero() ||
    376           (!ForceCleanup &&
    377            !isAssumeWithEmptyBundle(cast<AssumeInst>(*Assume))))
    378         continue;
    379       MadeChange = true;
    380       if (ForceCleanup)
    381         NumAssumesMerged++;
    382       else
    383         NumAssumesRemoved++;
    384       Assume->eraseFromParent();
    385     }
    386     CleanupToDo.clear();
    387   }
    388 
    389   /// Remove knowledge stored in assume when it is already know by an attribute
    390   /// or an other assume. This can when valid update an existing knowledge in an
    391   /// attribute or an other assume.
    392   void dropRedundantKnowledge() {
    393     struct MapValue {
    394       IntrinsicInst *Assume;
    395       unsigned ArgValue;
    396       CallInst::BundleOpInfo *BOI;
    397     };
    398     buildMapping(false);
    399     SmallDenseMap<std::pair<Value *, Attribute::AttrKind>,
    400                   SmallVector<MapValue, 2>, 16>
    401         Knowledge;
    402     for (BasicBlock *BB : depth_first(&F))
    403       for (Value *V : BBToAssume[BB]) {
    404         if (!V)
    405           continue;
    406         IntrinsicInst *Assume = cast<IntrinsicInst>(V);
    407         for (CallInst::BundleOpInfo &BOI : Assume->bundle_op_infos()) {
    408           auto RemoveFromAssume = [&]() {
    409             CleanupToDo.insert(Assume);
    410             if (BOI.Begin != BOI.End) {
    411               Use *U = &Assume->op_begin()[BOI.Begin + ABA_WasOn];
    412               U->set(UndefValue::get(U->get()->getType()));
    413             }
    414             BOI.Tag = IgnoreTag;
    415           };
    416           if (BOI.Tag == IgnoreTag) {
    417             CleanupToDo.insert(Assume);
    418             continue;
    419           }
    420           RetainedKnowledge RK =
    421             getKnowledgeFromBundle(cast<AssumeInst>(*Assume), BOI);
    422           if (auto *Arg = dyn_cast_or_null<Argument>(RK.WasOn)) {
    423             bool HasSameKindAttr = Arg->hasAttribute(RK.AttrKind);
    424             if (HasSameKindAttr)
    425               if (!Attribute::doesAttrKindHaveArgument(RK.AttrKind) ||
    426                   Arg->getAttribute(RK.AttrKind).getValueAsInt() >=
    427                       RK.ArgValue) {
    428                 RemoveFromAssume();
    429                 continue;
    430               }
    431             if (isValidAssumeForContext(
    432                     Assume, &*F.getEntryBlock().getFirstInsertionPt()) ||
    433                 Assume == &*F.getEntryBlock().getFirstInsertionPt()) {
    434               if (HasSameKindAttr)
    435                 Arg->removeAttr(RK.AttrKind);
    436               Arg->addAttr(Attribute::get(C, RK.AttrKind, RK.ArgValue));
    437               MadeChange = true;
    438               RemoveFromAssume();
    439               continue;
    440             }
    441           }
    442           auto &Lookup = Knowledge[{RK.WasOn, RK.AttrKind}];
    443           for (MapValue &Elem : Lookup) {
    444             if (!isValidAssumeForContext(Elem.Assume, Assume, DT))
    445               continue;
    446             if (Elem.ArgValue >= RK.ArgValue) {
    447               RemoveFromAssume();
    448               continue;
    449             } else if (isValidAssumeForContext(Assume, Elem.Assume, DT)) {
    450               Elem.Assume->op_begin()[Elem.BOI->Begin + ABA_Argument].set(
    451                   ConstantInt::get(Type::getInt64Ty(C), RK.ArgValue));
    452               MadeChange = true;
    453               RemoveFromAssume();
    454               continue;
    455             }
    456           }
    457           Lookup.push_back({Assume, RK.ArgValue, &BOI});
    458         }
    459       }
    460   }
    461 
    462   using MergeIterator = SmallVectorImpl<IntrinsicInst *>::iterator;
    463 
    464   /// Merge all Assumes from Begin to End in and insert the resulting assume as
    465   /// high as possible in the basicblock.
    466   void mergeRange(BasicBlock *BB, MergeIterator Begin, MergeIterator End) {
    467     if (Begin == End || std::next(Begin) == End)
    468       return;
    469     /// Provide no additional information so that AssumeBuilderState doesn't
    470     /// try to do any punning since it already has been done better.
    471     AssumeBuilderState Builder(F.getParent());
    472 
    473     /// For now it is initialized to the best value it could have
    474     Instruction *InsertPt = BB->getFirstNonPHI();
    475     if (isa<LandingPadInst>(InsertPt))
    476       InsertPt = InsertPt->getNextNode();
    477     for (IntrinsicInst *I : make_range(Begin, End)) {
    478       CleanupToDo.insert(I);
    479       for (CallInst::BundleOpInfo &BOI : I->bundle_op_infos()) {
    480         RetainedKnowledge RK =
    481           getKnowledgeFromBundle(cast<AssumeInst>(*I), BOI);
    482         if (!RK)
    483           continue;
    484         Builder.addKnowledge(RK);
    485         if (auto *I = dyn_cast_or_null<Instruction>(RK.WasOn))
    486           if (I->getParent() == InsertPt->getParent() &&
    487               (InsertPt->comesBefore(I) || InsertPt == I))
    488             InsertPt = I->getNextNode();
    489       }
    490     }
    491 
    492     /// Adjust InsertPt if it is before Begin, since mergeAssumes only
    493     /// guarantees we can place the resulting assume between Begin and End.
    494     if (InsertPt->comesBefore(*Begin))
    495       for (auto It = (*Begin)->getIterator(), E = InsertPt->getIterator();
    496            It != E; --It)
    497         if (!isGuaranteedToTransferExecutionToSuccessor(&*It)) {
    498           InsertPt = It->getNextNode();
    499           break;
    500         }
    501     auto *MergedAssume = Builder.build();
    502     if (!MergedAssume)
    503       return;
    504     MadeChange = true;
    505     MergedAssume->insertBefore(InsertPt);
    506     AC.registerAssumption(MergedAssume);
    507   }
    508 
    509   /// Merge assume when they are in the same BasicBlock and for all instruction
    510   /// between them isGuaranteedToTransferExecutionToSuccessor returns true.
    511   void mergeAssumes() {
    512     buildMapping(true);
    513 
    514     SmallVector<MergeIterator, 4> SplitPoints;
    515     for (auto &Elem : BBToAssume) {
    516       SmallVectorImpl<IntrinsicInst *> &AssumesInBB = Elem.second;
    517       if (AssumesInBB.size() < 2)
    518         continue;
    519       /// AssumesInBB is already sorted by order in the block.
    520 
    521       BasicBlock::iterator It = AssumesInBB.front()->getIterator();
    522       BasicBlock::iterator E = AssumesInBB.back()->getIterator();
    523       SplitPoints.push_back(AssumesInBB.begin());
    524       MergeIterator LastSplit = AssumesInBB.begin();
    525       for (; It != E; ++It)
    526         if (!isGuaranteedToTransferExecutionToSuccessor(&*It)) {
    527           for (; (*LastSplit)->comesBefore(&*It); ++LastSplit)
    528             ;
    529           if (SplitPoints.back() != LastSplit)
    530             SplitPoints.push_back(LastSplit);
    531         }
    532       SplitPoints.push_back(AssumesInBB.end());
    533       for (auto SplitIt = SplitPoints.begin();
    534            SplitIt != std::prev(SplitPoints.end()); SplitIt++) {
    535         mergeRange(Elem.first, *SplitIt, *(SplitIt + 1));
    536       }
    537       SplitPoints.clear();
    538     }
    539   }
    540 };
    541 
    542 bool simplifyAssumes(Function &F, AssumptionCache *AC, DominatorTree *DT) {
    543   AssumeSimplify AS(F, *AC, DT, F.getContext());
    544 
    545   /// Remove knowledge that is already known by a dominating other assume or an
    546   /// attribute.
    547   AS.dropRedundantKnowledge();
    548 
    549   /// Remove assume that are empty.
    550   AS.RunCleanup(false);
    551 
    552   /// Merge assume in the same basicblock when possible.
    553   AS.mergeAssumes();
    554 
    555   /// Remove assume that were merged.
    556   AS.RunCleanup(true);
    557   return AS.MadeChange;
    558 }
    559 
    560 } // namespace
    561 
    562 PreservedAnalyses AssumeSimplifyPass::run(Function &F,
    563                                           FunctionAnalysisManager &AM) {
    564   if (!EnableKnowledgeRetention)
    565     return PreservedAnalyses::all();
    566   simplifyAssumes(F, &AM.getResult<AssumptionAnalysis>(F),
    567                   AM.getCachedResult<DominatorTreeAnalysis>(F));
    568   return PreservedAnalyses::all();
    569 }
    570 
    571 namespace {
    572 class AssumeSimplifyPassLegacyPass : public FunctionPass {
    573 public:
    574   static char ID;
    575 
    576   AssumeSimplifyPassLegacyPass() : FunctionPass(ID) {
    577     initializeAssumeSimplifyPassLegacyPassPass(
    578         *PassRegistry::getPassRegistry());
    579   }
    580   bool runOnFunction(Function &F) override {
    581     if (skipFunction(F) || !EnableKnowledgeRetention)
    582       return false;
    583     AssumptionCache &AC =
    584         getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
    585     DominatorTreeWrapperPass *DTWP =
    586         getAnalysisIfAvailable<DominatorTreeWrapperPass>();
    587     return simplifyAssumes(F, &AC, DTWP ? &DTWP->getDomTree() : nullptr);
    588   }
    589 
    590   void getAnalysisUsage(AnalysisUsage &AU) const override {
    591     AU.addRequired<AssumptionCacheTracker>();
    592 
    593     AU.setPreservesAll();
    594   }
    595 };
    596 } // namespace
    597 
    598 char AssumeSimplifyPassLegacyPass::ID = 0;
    599 
    600 INITIALIZE_PASS_BEGIN(AssumeSimplifyPassLegacyPass, "assume-simplify",
    601                       "Assume Simplify", false, false)
    602 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
    603 INITIALIZE_PASS_END(AssumeSimplifyPassLegacyPass, "assume-simplify",
    604                     "Assume Simplify", false, false)
    605 
    606 FunctionPass *llvm::createAssumeSimplifyPass() {
    607   return new AssumeSimplifyPassLegacyPass();
    608 }
    609 
    610 PreservedAnalyses AssumeBuilderPass::run(Function &F,
    611                                          FunctionAnalysisManager &AM) {
    612   AssumptionCache *AC = &AM.getResult<AssumptionAnalysis>(F);
    613   DominatorTree* DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
    614   for (Instruction &I : instructions(F))
    615     salvageKnowledge(&I, AC, DT);
    616   return PreservedAnalyses::all();
    617 }
    618 
    619 namespace {
    620 class AssumeBuilderPassLegacyPass : public FunctionPass {
    621 public:
    622   static char ID;
    623 
    624   AssumeBuilderPassLegacyPass() : FunctionPass(ID) {
    625     initializeAssumeBuilderPassLegacyPassPass(*PassRegistry::getPassRegistry());
    626   }
    627   bool runOnFunction(Function &F) override {
    628     AssumptionCache &AC =
    629         getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
    630     DominatorTreeWrapperPass *DTWP =
    631         getAnalysisIfAvailable<DominatorTreeWrapperPass>();
    632     for (Instruction &I : instructions(F))
    633       salvageKnowledge(&I, &AC, DTWP ? &DTWP->getDomTree() : nullptr);
    634     return true;
    635   }
    636 
    637   void getAnalysisUsage(AnalysisUsage &AU) const override {
    638     AU.addRequired<AssumptionCacheTracker>();
    639 
    640     AU.setPreservesAll();
    641   }
    642 };
    643 } // namespace
    644 
    645 char AssumeBuilderPassLegacyPass::ID = 0;
    646 
    647 INITIALIZE_PASS_BEGIN(AssumeBuilderPassLegacyPass, "assume-builder",
    648                       "Assume Builder", false, false)
    649 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
    650 INITIALIZE_PASS_END(AssumeBuilderPassLegacyPass, "assume-builder",
    651                     "Assume Builder", false, false)
    652