llvm/lib/Transforms/Utils/AssumeBundleBuilder.cpp

   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::isIntAttrKind(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, unsigned NumArgs) {
 207       for (unsigned Idx = 0; Idx < NumArgs; Idx++)
 208         for (Attribute Attr : AttrList.getParamAttrs(Idx)) {
 209           bool IsPoisonAttr = Attr.hasAttribute(Attribute::NonNull) ||
 210                               Attr.hasAttribute(Attribute::Alignment);
 211           if (!IsPoisonAttr || Call->isPassingUndefUB(Idx))
 212             addAttribute(Attr, Call->getArgOperand(Idx));
 213         }
 214       for (Attribute Attr : AttrList.getFnAttrs())
 215         addAttribute(Attr, nullptr);
 216     };
 217     addAttrList(Call->getAttributes(), Call->arg_size());
 218     if (Function *Fn = Call->getCalledFunction())
 219       addAttrList(Fn->getAttributes(), Fn->arg_size());
 220   }
 221
 222   AssumeInst *build() {
 223     if (AssumedKnowledgeMap.empty())
 224       return nullptr;
 225     if (!DebugCounter::shouldExecute(BuildAssumeCounter))
 226       return nullptr;
 227     Function *FnAssume = Intrinsic::getDeclaration(M, Intrinsic::assume);
 228     LLVMContext &C = M->getContext();
 229     SmallVector<OperandBundleDef, 8> OpBundle;
 230     for (auto &MapElem : AssumedKnowledgeMap) {
 231       SmallVector<Value *, 2> Args;
 232       if (MapElem.first.first)
 233         Args.push_back(MapElem.first.first);
 234
 235       /// This is only valid because for all attribute that currently exist a
 236       /// value of 0 is useless. and should not be preserved.
 237       if (MapElem.second)
 238         Args.push_back(ConstantInt::get(Type::getInt64Ty(M->getContext()),
 239                                         MapElem.second));
 240       OpBundle.push_back(OperandBundleDefT<Value *>(
 241           std::string(Attribute::getNameFromAttrKind(MapElem.first.second)),
 242           Args));
 243       NumBundlesInAssumes++;
 244     }
 245     NumAssumeBuilt++;
 246     return cast<AssumeInst>(CallInst::Create(
 247         FnAssume, ArrayRef<Value *>({ConstantInt::getTrue(C)}), OpBundle));
 248   }
 249
 250   void addAccessedPtr(Instruction *MemInst, Value *Pointer, Type *AccType,
 251                       MaybeAlign MA) {
 252     unsigned DerefSize = MemInst->getModule()
 253                              ->getDataLayout()
 254                              .getTypeStoreSize(AccType)
 255                              .getKnownMinSize();
 256     if (DerefSize != 0) {
 257       addKnowledge({Attribute::Dereferenceable, DerefSize, Pointer});
 258       if (!NullPointerIsDefined(MemInst->getFunction(),
 259                                 Pointer->getType()->getPointerAddressSpace()))
 260         addKnowledge({Attribute::NonNull, 0u, Pointer});
 261     }
 262     if (MA.valueOrOne() > 1)
 263       addKnowledge(
 264           {Attribute::Alignment, unsigned(MA.valueOrOne().value()), Pointer});
 265   }
 266
 267   void addInstruction(Instruction *I) {
 268     if (auto *Call = dyn_cast<CallBase>(I))
 269       return addCall(Call);
 270     if (auto *Load = dyn_cast<LoadInst>(I))
 271       return addAccessedPtr(I, Load->getPointerOperand(), Load->getType(),
 272                             Load->getAlign());
 273     if (auto *Store = dyn_cast<StoreInst>(I))
 274       return addAccessedPtr(I, Store->getPointerOperand(),
 275                             Store->getValueOperand()->getType(),
 276                             Store->getAlign());
 277     // TODO: Add support for the other Instructions.
 278     // TODO: Maybe we should look around and merge with other llvm.assume.
 279   }
 280 };
 281
 282 } // namespace
 283
 284 AssumeInst *llvm::buildAssumeFromInst(Instruction *I) {
 285   if (!EnableKnowledgeRetention)
 286     return nullptr;
 287   AssumeBuilderState Builder(I->getModule());
 288   Builder.addInstruction(I);
 289   return Builder.build();
 290 }
 291
 292 void llvm::salvageKnowledge(Instruction *I, AssumptionCache *AC,
 293                             DominatorTree *DT) {
 294   if (!EnableKnowledgeRetention || I->isTerminator())
 295     return;
 296   AssumeBuilderState Builder(I->getModule(), I, AC, DT);
 297   Builder.addInstruction(I);
 298   if (auto *Intr = Builder.build()) {
 299     Intr->insertBefore(I);
 300     if (AC)
 301       AC->registerAssumption(Intr);
 302   }
 303 }
 304
 305 AssumeInst *
 306 llvm::buildAssumeFromKnowledge(ArrayRef<RetainedKnowledge> Knowledge,
 307                                Instruction *CtxI, AssumptionCache *AC,
 308                                DominatorTree *DT) {
 309   AssumeBuilderState Builder(CtxI->getModule(), CtxI, AC, DT);
 310   for (const RetainedKnowledge &RK : Knowledge)
 311     Builder.addKnowledge(RK);
 312   return Builder.build();
 313 }
 314
 315 RetainedKnowledge llvm::simplifyRetainedKnowledge(AssumeInst *Assume,
 316                                                   RetainedKnowledge RK,
 317                                                   AssumptionCache *AC,
 318                                                   DominatorTree *DT) {
 319   AssumeBuilderState Builder(Assume->getModule(), Assume, AC, DT);
 320   RK = canonicalizedKnowledge(RK, Assume->getModule()->getDataLayout());
 321
 322   if (!Builder.isKnowledgeWorthPreserving(RK))
 323     return RetainedKnowledge::none();
 324
 325   if (Builder.tryToPreserveWithoutAddingAssume(RK))
 326     return RetainedKnowledge::none();
 327   return RK;
 328 }
 329
 330 namespace {
 331
 332 struct AssumeSimplify {
 333   Function &F;
 334   AssumptionCache &AC;
 335   DominatorTree *DT;
 336   LLVMContext &C;
 337   SmallDenseSet<IntrinsicInst *> CleanupToDo;
 338   StringMapEntry<uint32_t> *IgnoreTag;
 339   SmallDenseMap<BasicBlock *, SmallVector<IntrinsicInst *, 4>, 8> BBToAssume;
 340   bool MadeChange = false;
 341
 342   AssumeSimplify(Function &F, AssumptionCache &AC, DominatorTree *DT,
 343                  LLVMContext &C)
 344       : F(F), AC(AC), DT(DT), C(C),
 345         IgnoreTag(C.getOrInsertBundleTag(IgnoreBundleTag)) {}
 346
 347   void buildMapping(bool FilterBooleanArgument) {
 348     BBToAssume.clear();
 349     for (Value *V : AC.assumptions()) {
 350       if (!V)
 351         continue;
 352       IntrinsicInst *Assume = cast<IntrinsicInst>(V);
 353       if (FilterBooleanArgument) {
 354         auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0));
 355         if (!Arg || Arg->isZero())
 356           continue;
 357       }
 358       BBToAssume[Assume->getParent()].push_back(Assume);
 359     }
 360
 361     for (auto &Elem : BBToAssume) {
 362       llvm::sort(Elem.second,
 363                  [](const IntrinsicInst *LHS, const IntrinsicInst *RHS) {
 364                    return LHS->comesBefore(RHS);
 365                  });
 366     }
 367   }
 368
 369   /// Remove all asumes in CleanupToDo if there boolean argument is true and
 370   /// ForceCleanup is set or the assume doesn't hold valuable knowledge.
 371   void RunCleanup(bool ForceCleanup) {
 372     for (IntrinsicInst *Assume : CleanupToDo) {
 373       auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0));
 374       if (!Arg || Arg->isZero() ||
 375           (!ForceCleanup &&
 376            !isAssumeWithEmptyBundle(cast<AssumeInst>(*Assume))))
 377         continue;
 378       MadeChange = true;
 379       if (ForceCleanup)
 380         NumAssumesMerged++;
 381       else
 382         NumAssumesRemoved++;
 383       Assume->eraseFromParent();
 384     }
 385     CleanupToDo.clear();
 386   }
 387
 388   /// Remove knowledge stored in assume when it is already know by an attribute
 389   /// or an other assume. This can when valid update an existing knowledge in an
 390   /// attribute or an other assume.
 391   void dropRedundantKnowledge() {
 392     struct MapValue {
 393       IntrinsicInst *Assume;
 394       unsigned ArgValue;
 395       CallInst::BundleOpInfo *BOI;
 396     };
 397     buildMapping(false);
 398     SmallDenseMap<std::pair<Value *, Attribute::AttrKind>,
 399                   SmallVector<MapValue, 2>, 16>
 400         Knowledge;
 401     for (BasicBlock *BB : depth_first(&F))
 402       for (Value *V : BBToAssume[BB]) {
 403         if (!V)
 404           continue;
 405         IntrinsicInst *Assume = cast<IntrinsicInst>(V);
 406         for (CallInst::BundleOpInfo &BOI : Assume->bundle_op_infos()) {
 407           auto RemoveFromAssume = [&]() {
 408             CleanupToDo.insert(Assume);
 409             if (BOI.Begin != BOI.End) {
 410               Use *U = &Assume->op_begin()[BOI.Begin + ABA_WasOn];
 411               U->set(UndefValue::get(U->get()->getType()));
 412             }
 413             BOI.Tag = IgnoreTag;
 414           };
 415           if (BOI.Tag == IgnoreTag) {
 416             CleanupToDo.insert(Assume);
 417             continue;
 418           }
 419           RetainedKnowledge RK =
 420             getKnowledgeFromBundle(cast<AssumeInst>(*Assume), BOI);
 421           if (auto *Arg = dyn_cast_or_null<Argument>(RK.WasOn)) {
 422             bool HasSameKindAttr = Arg->hasAttribute(RK.AttrKind);
 423             if (HasSameKindAttr)
 424               if (!Attribute::isIntAttrKind(RK.AttrKind) ||
 425                   Arg->getAttribute(RK.AttrKind).getValueAsInt() >=
 426                       RK.ArgValue) {
 427                 RemoveFromAssume();
 428                 continue;
 429               }
 430             if (isValidAssumeForContext(
 431                     Assume, &*F.getEntryBlock().getFirstInsertionPt()) ||
 432                 Assume == &*F.getEntryBlock().getFirstInsertionPt()) {
 433               if (HasSameKindAttr)
 434                 Arg->removeAttr(RK.AttrKind);
 435               Arg->addAttr(Attribute::get(C, RK.AttrKind, RK.ArgValue));
 436               MadeChange = true;
 437               RemoveFromAssume();
 438               continue;
 439             }
 440           }
 441           auto &Lookup = Knowledge[{RK.WasOn, RK.AttrKind}];
 442           for (MapValue &Elem : Lookup) {
 443             if (!isValidAssumeForContext(Elem.Assume, Assume, DT))
 444               continue;
 445             if (Elem.ArgValue >= RK.ArgValue) {
 446               RemoveFromAssume();
 447               continue;
 448             } else if (isValidAssumeForContext(Assume, Elem.Assume, DT)) {
 449               Elem.Assume->op_begin()[Elem.BOI->Begin + ABA_Argument].set(
 450                   ConstantInt::get(Type::getInt64Ty(C), RK.ArgValue));
 451               MadeChange = true;
 452               RemoveFromAssume();
 453               continue;
 454             }
 455           }
 456           Lookup.push_back({Assume, RK.ArgValue, &BOI});
 457         }
 458       }
 459   }
 460
 461   using MergeIterator = SmallVectorImpl<IntrinsicInst *>::iterator;
 462
 463   /// Merge all Assumes from Begin to End in and insert the resulting assume as
 464   /// high as possible in the basicblock.
 465   void mergeRange(BasicBlock *BB, MergeIterator Begin, MergeIterator End) {
 466     if (Begin == End || std::next(Begin) == End)
 467       return;
 468     /// Provide no additional information so that AssumeBuilderState doesn't
 469     /// try to do any punning since it already has been done better.
 470     AssumeBuilderState Builder(F.getParent());
 471
 472     /// For now it is initialized to the best value it could have
 473     Instruction *InsertPt = BB->getFirstNonPHI();
 474     if (isa<LandingPadInst>(InsertPt))
 475       InsertPt = InsertPt->getNextNode();
 476     for (IntrinsicInst *I : make_range(Begin, End)) {
 477       CleanupToDo.insert(I);
 478       for (CallInst::BundleOpInfo &BOI : I->bundle_op_infos()) {
 479         RetainedKnowledge RK =
 480           getKnowledgeFromBundle(cast<AssumeInst>(*I), BOI);
 481         if (!RK)
 482           continue;
 483         Builder.addKnowledge(RK);
 484         if (auto *I = dyn_cast_or_null<Instruction>(RK.WasOn))
 485           if (I->getParent() == InsertPt->getParent() &&
 486               (InsertPt->comesBefore(I) || InsertPt == I))
 487             InsertPt = I->getNextNode();
 488       }
 489     }
 490
 491     /// Adjust InsertPt if it is before Begin, since mergeAssumes only
 492     /// guarantees we can place the resulting assume between Begin and End.
 493     if (InsertPt->comesBefore(*Begin))
 494       for (auto It = (*Begin)->getIterator(), E = InsertPt->getIterator();
 495            It != E; --It)
 496         if (!isGuaranteedToTransferExecutionToSuccessor(&*It)) {
 497           InsertPt = It->getNextNode();
 498           break;
 499         }
 500     auto *MergedAssume = Builder.build();
 501     if (!MergedAssume)
 502       return;
 503     MadeChange = true;
 504     MergedAssume->insertBefore(InsertPt);
 505     AC.registerAssumption(MergedAssume);
 506   }
 507
 508   /// Merge assume when they are in the same BasicBlock and for all instruction
 509   /// between them isGuaranteedToTransferExecutionToSuccessor returns true.
 510   void mergeAssumes() {
 511     buildMapping(true);
 512
 513     SmallVector<MergeIterator, 4> SplitPoints;
 514     for (auto &Elem : BBToAssume) {
 515       SmallVectorImpl<IntrinsicInst *> &AssumesInBB = Elem.second;
 516       if (AssumesInBB.size() < 2)
 517         continue;
 518       /// AssumesInBB is already sorted by order in the block.
 519
 520       BasicBlock::iterator It = AssumesInBB.front()->getIterator();
 521       BasicBlock::iterator E = AssumesInBB.back()->getIterator();
 522       SplitPoints.push_back(AssumesInBB.begin());
 523       MergeIterator LastSplit = AssumesInBB.begin();
 524       for (; It != E; ++It)
 525         if (!isGuaranteedToTransferExecutionToSuccessor(&*It)) {
 526           for (; (*LastSplit)->comesBefore(&*It); ++LastSplit)
 527             ;
 528           if (SplitPoints.back() != LastSplit)
 529             SplitPoints.push_back(LastSplit);
 530         }
 531       SplitPoints.push_back(AssumesInBB.end());
 532       for (auto SplitIt = SplitPoints.begin();
 533            SplitIt != std::prev(SplitPoints.end()); SplitIt++) {
 534         mergeRange(Elem.first, *SplitIt, *(SplitIt + 1));
 535       }
 536       SplitPoints.clear();
 537     }
 538   }
 539 };
 540
 541 bool simplifyAssumes(Function &F, AssumptionCache *AC, DominatorTree *DT) {
 542   AssumeSimplify AS(F, *AC, DT, F.getContext());
 543
 544   /// Remove knowledge that is already known by a dominating other assume or an
 545   /// attribute.
 546   AS.dropRedundantKnowledge();
 547
 548   /// Remove assume that are empty.
 549   AS.RunCleanup(false);
 550
 551   /// Merge assume in the same basicblock when possible.
 552   AS.mergeAssumes();
 553
 554   /// Remove assume that were merged.
 555   AS.RunCleanup(true);
 556   return AS.MadeChange;
 557 }
 558
 559 } // namespace
 560
 561 PreservedAnalyses AssumeSimplifyPass::run(Function &F,
 562                                           FunctionAnalysisManager &AM) {
 563   if (!EnableKnowledgeRetention)
 564     return PreservedAnalyses::all();
 565   simplifyAssumes(F, &AM.getResult<AssumptionAnalysis>(F),
 566                   AM.getCachedResult<DominatorTreeAnalysis>(F));
 567   return PreservedAnalyses::all();
 568 }
 569
 570 namespace {
 571 class AssumeSimplifyPassLegacyPass : public FunctionPass {
 572 public:
 573   static char ID;
 574
 575   AssumeSimplifyPassLegacyPass() : FunctionPass(ID) {
 576     initializeAssumeSimplifyPassLegacyPassPass(
 577         *PassRegistry::getPassRegistry());
 578   }
 579   bool runOnFunction(Function &F) override {
 580     if (skipFunction(F) || !EnableKnowledgeRetention)
 581       return false;
 582     AssumptionCache &AC =
 583         getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
 584     DominatorTreeWrapperPass *DTWP =
 585         getAnalysisIfAvailable<DominatorTreeWrapperPass>();
 586     return simplifyAssumes(F, &AC, DTWP ? &DTWP->getDomTree() : nullptr);
 587   }
 588
 589   void getAnalysisUsage(AnalysisUsage &AU) const override {
 590     AU.addRequired<AssumptionCacheTracker>();
 591
 592     AU.setPreservesAll();
 593   }
 594 };
 595 } // namespace
 596
 597 char AssumeSimplifyPassLegacyPass::ID = 0;
 598
 599 INITIALIZE_PASS_BEGIN(AssumeSimplifyPassLegacyPass, "assume-simplify",
 600                       "Assume Simplify", false, false)
 601 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 602 INITIALIZE_PASS_END(AssumeSimplifyPassLegacyPass, "assume-simplify",
 603                     "Assume Simplify", false, false)
 604
 605 FunctionPass *llvm::createAssumeSimplifyPass() {
 606   return new AssumeSimplifyPassLegacyPass();
 607 }
 608
 609 PreservedAnalyses AssumeBuilderPass::run(Function &F,
 610                                          FunctionAnalysisManager &AM) {
 611   AssumptionCache *AC = &AM.getResult<AssumptionAnalysis>(F);
 612   DominatorTree* DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
 613   for (Instruction &I : instructions(F))
 614     salvageKnowledge(&I, AC, DT);
 615   return PreservedAnalyses::all();
 616 }
 617
 618 namespace {
 619 class AssumeBuilderPassLegacyPass : public FunctionPass {
 620 public:
 621   static char ID;
 622
 623   AssumeBuilderPassLegacyPass() : FunctionPass(ID) {
 624     initializeAssumeBuilderPassLegacyPassPass(*PassRegistry::getPassRegistry());
 625   }
 626   bool runOnFunction(Function &F) override {
 627     AssumptionCache &AC =
 628         getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
 629     DominatorTreeWrapperPass *DTWP =
 630         getAnalysisIfAvailable<DominatorTreeWrapperPass>();
 631     for (Instruction &I : instructions(F))
 632       salvageKnowledge(&I, &AC, DTWP ? &DTWP->getDomTree() : nullptr);
 633     return true;
 634   }
 635
 636   void getAnalysisUsage(AnalysisUsage &AU) const override {
 637     AU.addRequired<AssumptionCacheTracker>();
 638
 639     AU.setPreservesAll();
 640   }
 641 };
 642 } // namespace
 643
 644 char AssumeBuilderPassLegacyPass::ID = 0;
 645
 646 INITIALIZE_PASS_BEGIN(AssumeBuilderPassLegacyPass, "assume-builder",
 647                       "Assume Builder", false, false)
 648 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 649 INITIALIZE_PASS_END(AssumeBuilderPassLegacyPass, "assume-builder",
 650                     "Assume Builder", false, false)