| File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Transforms/Utils/AssumeBundleBuilder.cpp |
| Warning: | line 78, column 16 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 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" "assume-builder" | |||
| 41 | ||||
| 42 | STATISTIC(NumAssumeBuilt, "Number of assume built by the assume builder")static llvm::Statistic NumAssumeBuilt = {"assume-builder", "NumAssumeBuilt" , "Number of assume built by the assume builder"}; | |||
| 43 | STATISTIC(NumBundlesInAssumes, "Total number of Bundles in the assume built")static llvm::Statistic NumBundlesInAssumes = {"assume-builder" , "NumBundlesInAssumes", "Total number of Bundles in the assume built" }; | |||
| 44 | STATISTIC(NumAssumesMerged,static llvm::Statistic NumAssumesMerged = {"assume-builder", "NumAssumesMerged" , "Number of assume merged by the assume simplify pass"} | |||
| 45 | "Number of assume merged by the assume simplify pass")static llvm::Statistic NumAssumesMerged = {"assume-builder", "NumAssumesMerged" , "Number of assume merged by the assume simplify pass"}; | |||
| 46 | STATISTIC(NumAssumesRemoved,static llvm::Statistic NumAssumesRemoved = {"assume-builder", "NumAssumesRemoved", "Number of assume removed by the assume simplify pass" } | |||
| 47 | "Number of assume removed by the assume simplify pass")static llvm::Statistic NumAssumesRemoved = {"assume-builder", "NumAssumesRemoved", "Number of assume removed by the assume simplify pass" }; | |||
| 48 | ||||
| 49 | DEBUG_COUNTER(BuildAssumeCounter, "assume-builder-counter",static const unsigned BuildAssumeCounter = DebugCounter::registerCounter ("assume-builder-counter", "Controls which assumes gets created" ) | |||
| 50 | "Controls which assumes gets created")static const unsigned BuildAssumeCounter = DebugCounter::registerCounter ("assume-builder-counter", "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) ||((void)0) | |||
| 186 | (Lookup->second != 0 && RK.ArgValue != 0)) &&((void)0) | |||
| 187 | "inconsistent argument value")((void)0); | |||
| 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
| |||
| 270 | return addCall(Call); | |||
| 271 | if (auto *Load
| |||
| 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::isIntAttrKind(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",static void *initializeAssumeSimplifyPassLegacyPassPassOnce(PassRegistry &Registry) { | |||
| 601 | "Assume Simplify", false, false)static void *initializeAssumeSimplifyPassLegacyPassPassOnce(PassRegistry &Registry) { | |||
| 602 | INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry); | |||
| 603 | INITIALIZE_PASS_END(AssumeSimplifyPassLegacyPass, "assume-simplify",PassInfo *PI = new PassInfo( "Assume Simplify", "assume-simplify" , &AssumeSimplifyPassLegacyPass::ID, PassInfo::NormalCtor_t (callDefaultCtor<AssumeSimplifyPassLegacyPass>), false, false); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeAssumeSimplifyPassLegacyPassPassFlag ; void llvm::initializeAssumeSimplifyPassLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeAssumeSimplifyPassLegacyPassPassFlag , initializeAssumeSimplifyPassLegacyPassPassOnce, std::ref(Registry )); } | |||
| 604 | "Assume Simplify", false, false)PassInfo *PI = new PassInfo( "Assume Simplify", "assume-simplify" , &AssumeSimplifyPassLegacyPass::ID, PassInfo::NormalCtor_t (callDefaultCtor<AssumeSimplifyPassLegacyPass>), false, false); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeAssumeSimplifyPassLegacyPassPassFlag ; void llvm::initializeAssumeSimplifyPassLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeAssumeSimplifyPassLegacyPassPassFlag , initializeAssumeSimplifyPassLegacyPassPassOnce, std::ref(Registry )); } | |||
| 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",static void *initializeAssumeBuilderPassLegacyPassPassOnce(PassRegistry &Registry) { | |||
| 648 | "Assume Builder", false, false)static void *initializeAssumeBuilderPassLegacyPassPassOnce(PassRegistry &Registry) { | |||
| 649 | INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry); | |||
| 650 | INITIALIZE_PASS_END(AssumeBuilderPassLegacyPass, "assume-builder",PassInfo *PI = new PassInfo( "Assume Builder", "assume-builder" , &AssumeBuilderPassLegacyPass::ID, PassInfo::NormalCtor_t (callDefaultCtor<AssumeBuilderPassLegacyPass>), false, false ); Registry.registerPass(*PI, true); return PI; } static llvm ::once_flag InitializeAssumeBuilderPassLegacyPassPassFlag; void llvm::initializeAssumeBuilderPassLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeAssumeBuilderPassLegacyPassPassFlag , initializeAssumeBuilderPassLegacyPassPassOnce, std::ref(Registry )); } | |||
| 651 | "Assume Builder", false, false)PassInfo *PI = new PassInfo( "Assume Builder", "assume-builder" , &AssumeBuilderPassLegacyPass::ID, PassInfo::NormalCtor_t (callDefaultCtor<AssumeBuilderPassLegacyPass>), false, false ); Registry.registerPass(*PI, true); return PI; } static llvm ::once_flag InitializeAssumeBuilderPassLegacyPassPassFlag; void llvm::initializeAssumeBuilderPassLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeAssumeBuilderPassLegacyPassPassFlag , initializeAssumeBuilderPassLegacyPassPassOnce, std::ref(Registry )); } |