589 lines · 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-exception6//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/IR/Operator.h"22#include "llvm/Support/CommandLine.h"23#include "llvm/Support/Compiler.h"24#include "llvm/Support/DebugCounter.h"25#include "llvm/Transforms/Utils/Local.h"26 27using namespace llvm;28 29namespace llvm {30LLVM_ABI cl::opt<bool> ShouldPreserveAllAttributes(31 "assume-preserve-all", cl::init(false), cl::Hidden,32 cl::desc("enable preservation of all attributes. even those that are "33 "unlikely to be useful"));34 35cl::opt<bool> EnableKnowledgeRetention(36 "enable-knowledge-retention", cl::init(false), cl::Hidden,37 cl::desc(38 "enable preservation of attributes throughout code transformation"));39} // namespace llvm40 41#define DEBUG_TYPE "assume-builder"42 43STATISTIC(NumAssumeBuilt, "Number of assume built by the assume builder");44STATISTIC(NumBundlesInAssumes, "Total number of Bundles in the assume built");45STATISTIC(NumAssumesMerged,46 "Number of assume merged by the assume simplify pass");47STATISTIC(NumAssumesRemoved,48 "Number of assume removed by the assume simplify pass");49 50DEBUG_COUNTER(BuildAssumeCounter, "assume-builder-counter",51 "Controls which assumes gets created");52 53namespace {54 55bool isUsefullToPreserve(Attribute::AttrKind Kind) {56 switch (Kind) {57 case Attribute::NonNull:58 case Attribute::NoUndef:59 case Attribute::Alignment:60 case Attribute::Dereferenceable:61 case Attribute::DereferenceableOrNull:62 case Attribute::Cold:63 return true;64 default:65 return false;66 }67}68 69/// This function will try to transform the given knowledge into a more70/// canonical one. the canonical knowledge maybe the given one.71RetainedKnowledge canonicalizedKnowledge(RetainedKnowledge RK,72 const DataLayout &DL) {73 switch (RK.AttrKind) {74 default:75 return RK;76 case Attribute::NonNull:77 RK.WasOn = getUnderlyingObject(RK.WasOn);78 return RK;79 case Attribute::Alignment: {80 Value *V = RK.WasOn->stripInBoundsOffsets([&](const Value *Strip) {81 if (auto *GEP = dyn_cast<GEPOperator>(Strip))82 RK.ArgValue =83 MinAlign(RK.ArgValue, GEP->getMaxPreservedAlignment(DL).value());84 });85 RK.WasOn = V;86 return RK;87 }88 case Attribute::Dereferenceable:89 case Attribute::DereferenceableOrNull: {90 int64_t Offset = 0;91 Value *V = GetPointerBaseWithConstantOffset(RK.WasOn, Offset, DL,92 /*AllowNonInBounds*/ false);93 if (Offset < 0)94 return RK;95 RK.ArgValue = RK.ArgValue + Offset;96 RK.WasOn = V;97 }98 }99 return RK;100}101 102/// This class contain all knowledge that have been gather while building an103/// llvm.assume and the function to manipulate it.104struct AssumeBuilderState {105 Module *M;106 107 using MapKey = std::pair<Value *, Attribute::AttrKind>;108 SmallMapVector<MapKey, uint64_t, 8> AssumedKnowledgeMap;109 Instruction *InstBeingModified = nullptr;110 AssumptionCache* AC = nullptr;111 DominatorTree* DT = nullptr;112 113 AssumeBuilderState(Module *M, Instruction *I = nullptr,114 AssumptionCache *AC = nullptr, DominatorTree *DT = nullptr)115 : M(M), InstBeingModified(I), AC(AC), DT(DT) {}116 117 bool tryToPreserveWithoutAddingAssume(RetainedKnowledge RK) {118 if (!InstBeingModified || !RK.WasOn || !AC)119 return false;120 bool HasBeenPreserved = false;121 Use* ToUpdate = nullptr;122 getKnowledgeForValue(123 RK.WasOn, {RK.AttrKind}, *AC,124 [&](RetainedKnowledge RKOther, Instruction *Assume,125 const CallInst::BundleOpInfo *Bundle) {126 if (!isValidAssumeForContext(Assume, InstBeingModified, DT))127 return false;128 if (RKOther.ArgValue >= RK.ArgValue) {129 HasBeenPreserved = true;130 return true;131 } else if (isValidAssumeForContext(InstBeingModified, Assume, DT)) {132 HasBeenPreserved = true;133 IntrinsicInst *Intr = cast<IntrinsicInst>(Assume);134 ToUpdate = &Intr->op_begin()[Bundle->Begin + ABA_Argument];135 return true;136 }137 return false;138 });139 if (ToUpdate)140 ToUpdate->set(141 ConstantInt::get(Type::getInt64Ty(M->getContext()), RK.ArgValue));142 return HasBeenPreserved;143 }144 145 bool isKnowledgeWorthPreserving(RetainedKnowledge RK) {146 if (!RK)147 return false;148 if (!RK.WasOn)149 return true;150 if (RK.WasOn->getType()->isPointerTy()) {151 Value *UnderlyingPtr = getUnderlyingObject(RK.WasOn);152 if (isa<AllocaInst>(UnderlyingPtr) || isa<GlobalValue>(UnderlyingPtr))153 return false;154 }155 if (auto *Arg = dyn_cast<Argument>(RK.WasOn)) {156 if (Arg->hasAttribute(RK.AttrKind) &&157 (!Attribute::isIntAttrKind(RK.AttrKind) ||158 Arg->getAttribute(RK.AttrKind).getValueAsInt() >= RK.ArgValue))159 return false;160 return true;161 }162 if (auto *Inst = dyn_cast<Instruction>(RK.WasOn))163 if (wouldInstructionBeTriviallyDead(Inst)) {164 if (RK.WasOn->use_empty())165 return false;166 Use *SingleUse = RK.WasOn->getSingleUndroppableUse();167 if (SingleUse && SingleUse->getUser() == InstBeingModified)168 return false;169 }170 return true;171 }172 173 void addKnowledge(RetainedKnowledge RK) {174 RK = canonicalizedKnowledge(RK, M->getDataLayout());175 176 if (!isKnowledgeWorthPreserving(RK))177 return;178 179 if (tryToPreserveWithoutAddingAssume(RK))180 return;181 MapKey Key{RK.WasOn, RK.AttrKind};182 auto [Lookup, Inserted] = AssumedKnowledgeMap.try_emplace(Key, RK.ArgValue);183 if (Inserted)184 return;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 argument190 /// 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 uint64_t 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 =228 Intrinsic::getOrInsertDeclaration(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 a237 /// 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 .getKnownMinValue();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({Attribute::Alignment, 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} // namespace283 284AssumeInst *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 292bool llvm::salvageKnowledge(Instruction *I, AssumptionCache *AC,293 DominatorTree *DT) {294 if (!EnableKnowledgeRetention || I->isTerminator())295 return false;296 bool Changed = false;297 AssumeBuilderState Builder(I->getModule(), I, AC, DT);298 Builder.addInstruction(I);299 if (auto *Intr = Builder.build()) {300 Intr->insertBefore(I->getIterator());301 Changed = true;302 if (AC)303 AC->registerAssumption(Intr);304 }305 return Changed;306}307 308AssumeInst *309llvm::buildAssumeFromKnowledge(ArrayRef<RetainedKnowledge> Knowledge,310 Instruction *CtxI, AssumptionCache *AC,311 DominatorTree *DT) {312 AssumeBuilderState Builder(CtxI->getModule(), CtxI, AC, DT);313 for (const RetainedKnowledge &RK : Knowledge)314 Builder.addKnowledge(RK);315 return Builder.build();316}317 318RetainedKnowledge llvm::simplifyRetainedKnowledge(AssumeInst *Assume,319 RetainedKnowledge RK,320 AssumptionCache *AC,321 DominatorTree *DT) {322 AssumeBuilderState Builder(Assume->getModule(), Assume, AC, DT);323 RK = canonicalizedKnowledge(RK, Assume->getDataLayout());324 325 if (!Builder.isKnowledgeWorthPreserving(RK))326 return RetainedKnowledge::none();327 328 if (Builder.tryToPreserveWithoutAddingAssume(RK))329 return RetainedKnowledge::none();330 return RK;331}332 333namespace {334 335struct AssumeSimplify {336 Function &F;337 AssumptionCache &AC;338 DominatorTree *DT;339 LLVMContext &C;340 SmallDenseSet<IntrinsicInst *> CleanupToDo;341 StringMapEntry<uint32_t> *IgnoreTag;342 SmallDenseMap<BasicBlock *, SmallVector<IntrinsicInst *, 4>, 8> BBToAssume;343 bool MadeChange = false;344 345 AssumeSimplify(Function &F, AssumptionCache &AC, DominatorTree *DT,346 LLVMContext &C)347 : F(F), AC(AC), DT(DT), C(C),348 IgnoreTag(C.getOrInsertBundleTag(IgnoreBundleTag)) {}349 350 void buildMapping(bool FilterBooleanArgument) {351 BBToAssume.clear();352 for (Value *V : AC.assumptions()) {353 if (!V)354 continue;355 IntrinsicInst *Assume = cast<IntrinsicInst>(V);356 if (FilterBooleanArgument) {357 auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0));358 if (!Arg || Arg->isZero())359 continue;360 }361 BBToAssume[Assume->getParent()].push_back(Assume);362 }363 364 for (auto &Elem : BBToAssume) {365 llvm::sort(Elem.second,366 [](const IntrinsicInst *LHS, const IntrinsicInst *RHS) {367 return LHS->comesBefore(RHS);368 });369 }370 }371 372 /// Remove all asumes in CleanupToDo if there boolean argument is true and373 /// ForceCleanup is set or the assume doesn't hold valuable knowledge.374 void RunCleanup(bool ForceCleanup) {375 for (IntrinsicInst *Assume : CleanupToDo) {376 auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0));377 if (!Arg || Arg->isZero() ||378 (!ForceCleanup &&379 !isAssumeWithEmptyBundle(cast<AssumeInst>(*Assume))))380 continue;381 MadeChange = true;382 if (ForceCleanup)383 NumAssumesMerged++;384 else385 NumAssumesRemoved++;386 Assume->eraseFromParent();387 }388 CleanupToDo.clear();389 }390 391 /// Remove knowledge stored in assume when it is already know by an attribute392 /// or an other assume. This can when valid update an existing knowledge in an393 /// attribute or an other assume.394 void dropRedundantKnowledge() {395 struct MapValue {396 IntrinsicInst *Assume;397 uint64_t ArgValue;398 CallInst::BundleOpInfo *BOI;399 };400 buildMapping(false);401 SmallDenseMap<std::pair<Value *, Attribute::AttrKind>,402 SmallVector<MapValue, 2>, 16>403 Knowledge;404 for (BasicBlock *BB : depth_first(&F))405 for (Value *V : BBToAssume[BB]) {406 if (!V)407 continue;408 IntrinsicInst *Assume = cast<IntrinsicInst>(V);409 for (CallInst::BundleOpInfo &BOI : Assume->bundle_op_infos()) {410 auto RemoveFromAssume = [&]() {411 CleanupToDo.insert(Assume);412 if (BOI.Begin != BOI.End) {413 Use *U = &Assume->op_begin()[BOI.Begin + ABA_WasOn];414 U->set(PoisonValue::get(U->get()->getType()));415 }416 BOI.Tag = IgnoreTag;417 };418 if (BOI.Tag == IgnoreTag) {419 CleanupToDo.insert(Assume);420 continue;421 }422 RetainedKnowledge RK =423 getKnowledgeFromBundle(cast<AssumeInst>(*Assume), BOI);424 if (auto *Arg = dyn_cast_or_null<Argument>(RK.WasOn)) {425 bool HasSameKindAttr = Arg->hasAttribute(RK.AttrKind);426 if (HasSameKindAttr)427 if (!Attribute::isIntAttrKind(RK.AttrKind) ||428 Arg->getAttribute(RK.AttrKind).getValueAsInt() >=429 RK.ArgValue) {430 RemoveFromAssume();431 continue;432 }433 if (isValidAssumeForContext(434 Assume, &*F.getEntryBlock().getFirstInsertionPt()) ||435 Assume == &*F.getEntryBlock().getFirstInsertionPt()) {436 if (HasSameKindAttr)437 Arg->removeAttr(RK.AttrKind);438 Arg->addAttr(Attribute::get(C, RK.AttrKind, RK.ArgValue));439 MadeChange = true;440 RemoveFromAssume();441 continue;442 }443 }444 auto &Lookup = Knowledge[{RK.WasOn, RK.AttrKind}];445 for (MapValue &Elem : Lookup) {446 if (!isValidAssumeForContext(Elem.Assume, Assume, DT))447 continue;448 if (Elem.ArgValue >= RK.ArgValue) {449 RemoveFromAssume();450 continue;451 } else if (isValidAssumeForContext(Assume, Elem.Assume, DT)) {452 Elem.Assume->op_begin()[Elem.BOI->Begin + ABA_Argument].set(453 ConstantInt::get(Type::getInt64Ty(C), RK.ArgValue));454 MadeChange = true;455 RemoveFromAssume();456 continue;457 }458 }459 Lookup.push_back({Assume, RK.ArgValue, &BOI});460 }461 }462 }463 464 using MergeIterator = SmallVectorImpl<IntrinsicInst *>::iterator;465 466 /// Merge all Assumes from Begin to End in and insert the resulting assume as467 /// high as possible in the basicblock.468 void mergeRange(BasicBlock *BB, MergeIterator Begin, MergeIterator End) {469 if (Begin == End || std::next(Begin) == End)470 return;471 /// Provide no additional information so that AssumeBuilderState doesn't472 /// try to do any punning since it already has been done better.473 AssumeBuilderState Builder(F.getParent());474 475 /// For now it is initialized to the best value it could have476 BasicBlock::iterator InsertPt = BB->getFirstNonPHIIt();477 if (isa<LandingPadInst>(InsertPt))478 InsertPt = std::next(InsertPt);479 for (IntrinsicInst *I : make_range(Begin, End)) {480 CleanupToDo.insert(I);481 for (CallInst::BundleOpInfo &BOI : I->bundle_op_infos()) {482 RetainedKnowledge RK =483 getKnowledgeFromBundle(cast<AssumeInst>(*I), BOI);484 if (!RK)485 continue;486 Builder.addKnowledge(RK);487 if (auto *I = dyn_cast_or_null<Instruction>(RK.WasOn))488 if (I->getParent() == InsertPt->getParent() &&489 (InsertPt->comesBefore(I) || &*InsertPt == I))490 InsertPt = I->getNextNode()->getIterator();491 }492 }493 494 /// Adjust InsertPt if it is before Begin, since mergeAssumes only495 /// guarantees we can place the resulting assume between Begin and End.496 if (InsertPt->comesBefore(*Begin))497 for (auto It = (*Begin)->getIterator(), E = InsertPt->getIterator();498 It != E; --It)499 if (!isGuaranteedToTransferExecutionToSuccessor(&*It)) {500 InsertPt = std::next(It);501 break;502 }503 auto *MergedAssume = Builder.build();504 if (!MergedAssume)505 return;506 MadeChange = true;507 MergedAssume->insertBefore(InsertPt);508 AC.registerAssumption(MergedAssume);509 }510 511 /// Merge assume when they are in the same BasicBlock and for all instruction512 /// between them isGuaranteedToTransferExecutionToSuccessor returns true.513 void mergeAssumes() {514 buildMapping(true);515 516 SmallVector<MergeIterator, 4> SplitPoints;517 for (auto &Elem : BBToAssume) {518 SmallVectorImpl<IntrinsicInst *> &AssumesInBB = Elem.second;519 if (AssumesInBB.size() < 2)520 continue;521 /// AssumesInBB is already sorted by order in the block.522 523 BasicBlock::iterator It = AssumesInBB.front()->getIterator();524 BasicBlock::iterator E = AssumesInBB.back()->getIterator();525 SplitPoints.push_back(AssumesInBB.begin());526 MergeIterator LastSplit = AssumesInBB.begin();527 for (; It != E; ++It)528 if (!isGuaranteedToTransferExecutionToSuccessor(&*It)) {529 for (; (*LastSplit)->comesBefore(&*It); ++LastSplit)530 ;531 if (SplitPoints.back() != LastSplit)532 SplitPoints.push_back(LastSplit);533 }534 SplitPoints.push_back(AssumesInBB.end());535 for (auto SplitIt = SplitPoints.begin();536 SplitIt != std::prev(SplitPoints.end()); SplitIt++) {537 mergeRange(Elem.first, *SplitIt, *(SplitIt + 1));538 }539 SplitPoints.clear();540 }541 }542};543 544bool simplifyAssumes(Function &F, AssumptionCache *AC, DominatorTree *DT) {545 AssumeSimplify AS(F, *AC, DT, F.getContext());546 547 /// Remove knowledge that is already known by a dominating other assume or an548 /// attribute.549 AS.dropRedundantKnowledge();550 551 /// Remove assume that are empty.552 AS.RunCleanup(false);553 554 /// Merge assume in the same basicblock when possible.555 AS.mergeAssumes();556 557 /// Remove assume that were merged.558 AS.RunCleanup(true);559 return AS.MadeChange;560}561 562} // namespace563 564PreservedAnalyses AssumeSimplifyPass::run(Function &F,565 FunctionAnalysisManager &AM) {566 if (!EnableKnowledgeRetention)567 return PreservedAnalyses::all();568 if (!simplifyAssumes(F, &AM.getResult<AssumptionAnalysis>(F),569 AM.getCachedResult<DominatorTreeAnalysis>(F)))570 return PreservedAnalyses::all();571 PreservedAnalyses PA;572 PA.preserveSet<CFGAnalyses>();573 return PA;574}575 576PreservedAnalyses AssumeBuilderPass::run(Function &F,577 FunctionAnalysisManager &AM) {578 AssumptionCache *AC = &AM.getResult<AssumptionAnalysis>(F);579 DominatorTree* DT = AM.getCachedResult<DominatorTreeAnalysis>(F);580 bool Changed = false;581 for (Instruction &I : instructions(F))582 Changed |= salvageKnowledge(&I, AC, DT);583 if (!Changed)584 PreservedAnalyses::all();585 PreservedAnalyses PA;586 PA.preserveSet<CFGAnalyses>();587 return PA;588}589