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